001package daikon; 002 003import java.io.IOException; 004import java.io.ObjectStreamException; 005import java.io.Reader; 006import java.io.Serializable; 007import java.io.StreamTokenizer; 008import java.io.StringReader; 009import java.util.ArrayList; 010import java.util.HashMap; 011import java.util.Map; 012import java.util.Objects; 013import java.util.logging.Level; 014import java.util.logging.Logger; 015import org.checkerframework.checker.interning.qual.Interned; 016import org.checkerframework.checker.lock.qual.GuardSatisfied; 017import org.checkerframework.checker.nullness.qual.EnsuresKeyForIf; 018import org.checkerframework.checker.nullness.qual.EnsuresNonNullIf; 019import org.checkerframework.checker.nullness.qual.KeyFor; 020import org.checkerframework.checker.nullness.qual.MonotonicNonNull; 021import org.checkerframework.checker.nullness.qual.Nullable; 022import org.checkerframework.checker.signedness.qual.Signed; 023import org.checkerframework.checker.signedness.qual.UnknownSignedness; 024import org.checkerframework.dataflow.qual.Pure; 025import org.checkerframework.dataflow.qual.SideEffectFree; 026 027/** 028 * Represents additional information about a VarInfo that front ends tell Daikon. For example, 029 * whether order matters in a collection. This is immutable and interned. 030 */ 031public final class VarInfoAux implements Cloneable, Serializable { 032 // We are Serializable, so we specify a version to allow changes to 033 // method signatures without breaking serialization. If you add or 034 // remove fields, you should change this number to the current date. 035 static final long serialVersionUID = 20020614L; 036 037 /** General debug tracer. */ 038 public static final Logger debug = Logger.getLogger("daikon.VarInfoAux"); 039 040 public static final String TRUE = "true"; 041 public static final String FALSE = "false"; 042 043 // The below are all the possible keys for the map, and values tend to be 044 // binary. So could we make it a packed binary array? 045 046 // All of the keys below should be @KeyFor("this.map") but that isn't a valid expression. 047 // See https://tinyurl.com/cfissue/877 048 049 /** 050 * Whether the elements in this collection are all the meaningful elements, or whether there is a 051 * null at the end of this collection that ends the collection. 052 */ 053 public static final String NULL_TERMINATING = "nullTerminating"; 054 055 /** 056 * Whether this variable is a parameter to a method, or derived from a parameter to a method. By 057 * default, if p is a parameter, then some EXIT invariants related to p aren't printed. However, 058 * this does not affect the computation of invariants. 059 * 060 * <p>Frontends are responsible for setting if p is a parameter and if p.a is a parameter. In 061 * Java, p.a is not a parameter, whereas in IOA, it is. 062 */ 063 public static final String IS_PARAM = "isParam"; 064 065 /** Whether repeated elements can exist in this collection. */ 066 public static final String HAS_DUPLICATES = "hasDuplicates"; 067 068 /** Whether order matters. */ 069 public static final String HAS_ORDER = "hasOrder"; 070 071 /** Whether taking the size of this matters. */ 072 public static final String HAS_SIZE = "hasSize"; 073 074 /** Whether null has a special meaning for this variable or its members. */ 075 public static final String HAS_NULL = "hasNull"; 076 077 /** Indicates the minimum size of the vector, if there's any. */ 078 public static final String MINIMUM_LENGTH = "minlength"; 079 080 /** Indicates the maximum size of the vector, if there's any. */ 081 public static final String MAXIMUM_LENGTH = "maxlength"; 082 083 /** Indicates the minimum value of the scalar variable or the vector elements, if there's any. */ 084 public static final String MINIMUM_VALUE = "minvalue"; 085 086 /** Indicates the maximum value of the scalar variable or the vector elements, if there's any. */ 087 public static final String MAXIMUM_VALUE = "maxvalue"; 088 089 /** 090 * Indicates the valid values (using string representation) for the elements of the vector, if 091 * there's any. Values are enclosed in square brackets, and each element is quoted separately, 092 * e.g.: ["a" "b"]. Parsing will be done upon call of the getList() method. 093 * 094 * @see #getList(String) 095 */ 096 public static final String VALID_VALUES = "validvalues"; 097 098 /** 099 * Whether this variable is an inline structure. By default, a variable is a reference to a 100 * structure (class). If it is an inlined structure (or array), it doesn't make sense to look for 101 * invariants over its hashcode. Front ends include references to inlined structures as variables 102 * because some tools that follow daikon need other information about the variable. 103 */ 104 public static final String IS_STRUCT = "isStruct"; 105 106 /** Whether this variable is known to be non-null, such as "this" in a Java program. */ 107 public static final String IS_NON_NULL = "isNonNull"; 108 109 /** 110 * Java-specific. The package name of the class that declares this variable, if the variable is a 111 * field. If it's not a field of some class, the value of this key is "no_package_name_string". 112 */ 113 public static final String PACKAGE_NAME = "declaringClassPackageName"; 114 115 /** See {@link #PACKAGE_NAME}. */ 116 public static final String NO_PACKAGE_NAME = "no_package_name_string"; 117 118 /** Interned default options. */ 119 private static @Interned VarInfoAux theDefault = new VarInfoAux().intern(); 120 121 /** Contains the actual hashMap for this. */ 122 @SuppressWarnings("serial") 123 private Map<@Interned String, @Interned String> map; 124 125 /** Whether this is interned. */ 126 private boolean isInterned = false; 127 128 /** Make the default map here. */ 129 private VarInfoAux() { 130 HashMap<@Interned String, @Interned String> defaultMap = new HashMap<>(); 131 // The following are default values. 132 defaultMap.put(HAS_DUPLICATES, TRUE); 133 defaultMap.put(HAS_ORDER, TRUE); 134 defaultMap.put(HAS_SIZE, TRUE); 135 defaultMap.put(HAS_NULL, TRUE); 136 defaultMap.put(NULL_TERMINATING, TRUE); 137 defaultMap.put(IS_PARAM, FALSE); 138 defaultMap.put(PACKAGE_NAME, NO_PACKAGE_NAME); 139 defaultMap.put(IS_STRUCT, FALSE); 140 defaultMap.put(IS_NON_NULL, FALSE); 141 this.map = defaultMap; 142 this.isInterned = false; 143 } 144 145 /** 146 * Create a new VarInfoAux with default options. 147 * 148 * @param map the map from property names to values 149 */ 150 private VarInfoAux(Map<@Interned String, @Interned String> map) { 151 this.map = map; 152 this.isInterned = false; 153 } 154 155 /** 156 * Return an interned VarInfoAux that represents a given string. Elements are separated by commas, 157 * in the form: 158 * 159 * <p>x = a, "a key" = "a value" 160 * 161 * <p>Parse allow for quoted elements. White space to the left and right of keys and values do not 162 * matter, but inbetween does. 163 */ 164 public static @Interned VarInfoAux parse(String inString) throws IOException { 165 Reader inStringReader = new StringReader(inString); 166 StreamTokenizer tok = new StreamTokenizer(inStringReader); 167 tok.resetSyntax(); 168 tok.wordChars(0, Integer.MAX_VALUE); 169 tok.quoteChar('\"'); 170 tok.whitespaceChars(' ', ' '); 171 tok.ordinaryChar('['); 172 tok.ordinaryChar(']'); 173 tok.ordinaryChars(',', ','); 174 tok.ordinaryChars('=', '='); 175 @SuppressWarnings("serial") 176 Map<@Interned String, @Interned String> map = theDefault.map; 177 178 String key = ""; 179 String value = ""; 180 boolean seenEqual = false; 181 boolean insideVector = false; 182 for (int tokInfo = tok.nextToken(); 183 tokInfo != StreamTokenizer.TT_EOF; 184 tokInfo = tok.nextToken()) { 185 @SuppressWarnings("interning") // initialization-checking pattern 186 boolean mapUnchanged = (map == theDefault.map); 187 if (mapUnchanged) { 188 // We use default values if none are specified. We initialize 189 // here rather than above to save time when there are no tokens. 190 191 map = new HashMap<>(theDefault.map); 192 } 193 194 @Interned String token; 195 if (tok.ttype == StreamTokenizer.TT_WORD || tok.ttype == '\"') { 196 assert tok.sval != null 197 : "@AssumeAssertion(nullness): representation invariant of StreamTokenizer"; 198 token = tok.sval.trim().intern(); 199 } else { 200 token = ((@Signed char) tok.ttype + "").intern(); 201 } 202 203 debug.fine("Token info: " + tokInfo + " " + token); 204 205 if (token == "[") { // interned 206 if (!seenEqual) throw new IOException("Aux option did not contain an '='"); 207 if (insideVector) throw new IOException("Vectors cannot be nested in an aux option"); 208 if (value.length() > 0) { 209 throw new IOException("Cannot mix scalar and vector values"); 210 } 211 212 insideVector = true; 213 value = ""; 214 } else if (token == "]") { // interned 215 if (!insideVector) throw new IOException("']' without preceding '['"); 216 insideVector = false; 217 } else if (token == ",") { // interned 218 if (!seenEqual) throw new IOException("Aux option did not contain an '='"); 219 if (insideVector) throw new IOException("',' cannot be used inside a vector"); 220 map.put(key.intern(), value.intern()); 221 key = ""; 222 value = ""; 223 seenEqual = false; 224 } else if (token == "=") { // interned 225 if (seenEqual) throw new IOException("Aux option contained more than one '='"); 226 if (insideVector) throw new IOException("'=' cannot be used inside a vector"); 227 seenEqual = true; 228 } else { 229 if (!seenEqual) { 230 key = (key + " " + token).trim(); 231 } else if (insideVector) { 232 value = value + " \"" + token.trim() + "\""; 233 } else { 234 value = (value + " " + token).trim(); 235 } 236 } 237 } 238 239 if (seenEqual) { 240 map.put(key.intern(), value.intern()); 241 } 242 243 // Interning 244 VarInfoAux result = new VarInfoAux(map).intern(); 245 assert interningMap != null 246 : "@AssumeAssertion(nullness): application invariant: postcondition of intern(), which" 247 + " was just called"; 248 if (debug.isLoggable(Level.FINE)) { 249 debug.fine("New parse " + result); 250 debug.fine("Intern table size: " + interningMap.size()); 251 } 252 return result; 253 } 254 255 /** 256 * Create a new VarInfoAux with default options. 257 * 258 * @return a new VarInfoAux with default options 259 */ 260 public static @Interned VarInfoAux getDefault() { 261 return theDefault; 262 } 263 264 /** Map for interning. */ 265 private static @MonotonicNonNull Map<VarInfoAux, @Interned VarInfoAux> interningMap = 266 // Static fields might not be initialized before static methods (which 267 // call instance methods) are called, so don't bother to initialize here. 268 null; 269 270 /** Special handler for deserialization. */ 271 private @Interned Object readResolve() throws ObjectStreamException { 272 isInterned = false; 273 Map<@Interned String, @Interned String> newMap = new HashMap<>(); 274 for (String key : map.keySet()) { 275 newMap.put(key.intern(), map.get(key).intern()); 276 } 277 map = newMap; 278 return this.intern(); 279 } 280 281 /** Creates and returns a copy of this. */ 282 // Default implementation to quiet Findbugs. 283 @SideEffectFree 284 @Override 285 public VarInfoAux clone(@GuardSatisfied VarInfoAux this) throws CloneNotSupportedException { 286 VarInfoAux result = (VarInfoAux) super.clone(); 287 result.isInterned = false; 288 return result; 289 } 290 291 @SideEffectFree 292 @Override 293 public String toString(@GuardSatisfied VarInfoAux this) { 294 return map.toString(); 295 } 296 297 @Pure 298 @Override 299 public int hashCode(@GuardSatisfied @UnknownSignedness VarInfoAux this) { 300 return map.hashCode(); 301 } 302 303 @EnsuresNonNullIf(result = true, expression = "#1") 304 @Pure 305 @Override 306 public boolean equals(@GuardSatisfied VarInfoAux this, @GuardSatisfied @Nullable Object o) { 307 if (o instanceof VarInfoAux) { 308 return equalsVarInfoAux((VarInfoAux) o); 309 } else { 310 return false; 311 } 312 } 313 314 @Pure 315 public boolean equalsVarInfoAux(@GuardSatisfied VarInfoAux this, @GuardSatisfied VarInfoAux o) { 316 return this.map.equals(o.map); 317 } 318 319 // Two variables should not be put in the same equality set unless they have the same flags. For 320 // example, suppose that variable "this" is known to be non-null, but it is initially equal to 321 // another variable. Then NonZero will not be instantiated over "this", and when the equality set 322 // is broken, there will be no NonZero invariant to copy to the other variable. We only need to 323 // check equality for every aux field that might affect methods such as instantiate_ok. 324 @SuppressWarnings("keyfor") // https://tinyurl.com/cfissue/877 325 @Pure 326 public boolean equals_for_instantiation( 327 @GuardSatisfied VarInfoAux this, @GuardSatisfied VarInfoAux o) { 328 return this.getValue(HAS_DUPLICATES).equals(o.getValue(HAS_DUPLICATES)) 329 && this.getValue(HAS_ORDER).equals(o.getValue(HAS_ORDER)) 330 && this.getValue(HAS_SIZE).equals(o.getValue(HAS_SIZE)) 331 && this.getValue(HAS_NULL).equals(o.getValue(HAS_NULL)) 332 && Objects.equals(this.getValueOrNull(MINIMUM_LENGTH), o.getValueOrNull(MINIMUM_LENGTH)) 333 && Objects.equals(this.getValueOrNull(MAXIMUM_LENGTH), o.getValueOrNull(MAXIMUM_LENGTH)) 334 && Objects.equals(this.getValueOrNull(MINIMUM_VALUE), o.getValueOrNull(MINIMUM_VALUE)) 335 && Objects.equals(this.getValueOrNull(MAXIMUM_VALUE), o.getValueOrNull(MAXIMUM_VALUE)) 336 && Objects.equals(this.getValueOrNull(VALID_VALUES), o.getValueOrNull(VALID_VALUES)) 337 && this.getValue(IS_STRUCT).equals(o.getValue(IS_STRUCT)) 338 && this.getValue(IS_NON_NULL).equals(o.getValue(IS_NON_NULL)); 339 } 340 341 /** 342 * Returns canonical representation of this. Doesn't need to be called by outside classes because 343 * these are always interned. 344 */ 345 @SuppressWarnings({"interning", "cast"}) // intern method 346 private @Interned VarInfoAux intern() { 347 348 for (@Interned String key : map.keySet()) { 349 assert key == key.intern(); 350 assert map.get(key) == map.get(key).intern(); 351 } 352 353 if (this.isInterned) { 354 return (@Interned VarInfoAux) this; // cast is redundant (except in JSR 308) 355 } 356 357 // Necessary because various static methods call intern(), possibly before static field 358 // interningMap's initializer would be executed. 359 if (interningMap == null) { 360 interningMap = new HashMap<>(); 361 } 362 363 @Interned VarInfoAux result; 364 if (interningMap.containsKey(this)) { 365 result = interningMap.get(this); 366 } else { 367 // Intern values in map 368 interningMap.put(this, (@Interned VarInfoAux) this); // cast is redundant (except in JSR 308) 369 result = (@Interned VarInfoAux) this; // cast is redundant (except in JSR 308) 370 this.isInterned = true; 371 } 372 return result; 373 } 374 375 /** 376 * Returns the integer value associated with a key, assuming it is defined. It is recommended to 377 * check that it is defined first with {@link #hasValue(String)}. 378 * 379 * @throws RuntimeException if the key is not defined 380 * @throws NumberFormatException if the value of the key cannot be parsed as an integer 381 * @see #hasValue(String) 382 */ 383 @Pure 384 public int getInt(@KeyFor("this.map") String key) { 385 if (!hasValue(key)) { 386 throw new RuntimeException(String.format("Key '%s' is not defined", key)); 387 } 388 return Integer.parseInt(getValue(key)); 389 } 390 391 /** 392 * Returns the string array associated with a key, assuming it is defined. It is recommended to 393 * check that it is defined first with {@link #hasValue(String)}. 394 * 395 * @throws RuntimeException if the key is not defined 396 * @see #hasValue(String) 397 */ 398 public String[] getList(@KeyFor("this.map") String key) { 399 try { 400 if (!hasValue(key)) { 401 throw new RuntimeException(String.format("Key '%s' is not defined", key)); 402 } 403 final String sValue = getValue(key); 404 StreamTokenizer tok = new StreamTokenizer(new StringReader(sValue)); 405 tok.quoteChar('"'); 406 tok.whitespaceChars(' ', ' '); 407 ArrayList<String> lValues = new ArrayList<>(); 408 409 int tokInfo = tok.nextToken(); 410 while (tokInfo != StreamTokenizer.TT_EOF) { 411 if (tok.ttype != '"') { 412 continue; 413 } 414 assert tok.sval != null 415 : "@AssumeAssertion(nullness)"; // tok.type == '"' guarantees not null 416 lValues.add(tok.sval.trim()); 417 tokInfo = tok.nextToken(); 418 } 419 return lValues.toArray(new String[] {}); 420 } catch (IOException ex) { 421 throw new RuntimeException(String.format("Parsing for key '%s' failed", key), ex); 422 } 423 } 424 425 /** Returns the value for the given key, which must be present in the map. */ 426 public String getValue(@GuardSatisfied VarInfoAux this, @KeyFor("this.map") String key) { 427 return map.get(key); 428 } 429 430 /** Returns the value for the given key, or null if it is not present. */ 431 public @Nullable String getValueOrNull(@GuardSatisfied VarInfoAux this, String key) { 432 return map.get(key); 433 } 434 435 /** Return {@code true} if the value for the given key is defined, and {@code false} otherwise. */ 436 @Pure 437 @EnsuresKeyForIf(result = true, expression = "#1", map = "map") 438 public boolean hasValue(String key) { 439 return map.containsKey(key); 440 } 441 442 public boolean getFlag(@KeyFor("this.map") String key) { 443 assert map.containsKey(key); 444 Object value = map.get(key); 445 assert value == TRUE || value == FALSE; 446 return value.equals(TRUE); 447 } 448 449 /** Return a new VarInfoAux with the desired value set. Does not modify this. */ 450 public @Interned VarInfoAux setValue(String key, String value) { 451 HashMap<@Interned String, @Interned String> newMap = new HashMap<>(this.map); 452 newMap.put(key.intern(), value.intern()); 453 return new VarInfoAux(newMap).intern(); 454 } 455 456 /** 457 * Converts the integer {@code value} to a String before invoking {@link #setValue(String, 458 * String)}. 459 */ 460 public VarInfoAux setInt(String key, int value) { 461 return setValue(key, Integer.toString(value)); 462 } 463 464 /** 465 * See {@link #NULL_TERMINATING}. 466 * 467 * @see #NULL_TERMINATING 468 */ 469 @SuppressWarnings("keyfor") // NULL_TERMINATING is always a key 470 @Pure 471 public boolean nullTerminating() { 472 return getFlag(NULL_TERMINATING); 473 } 474 475 /** 476 * See {@link #IS_PARAM}. 477 * 478 * @see #IS_PARAM 479 */ 480 @SuppressWarnings("keyfor") // IS_PARAM is always a key 481 @Pure 482 public boolean isParam() { 483 return getFlag(IS_PARAM); 484 } 485 486 /** 487 * See {@link #PACKAGE_NAME}. 488 * 489 * @see #PACKAGE_NAME 490 */ 491 @SuppressWarnings("keyfor") // PACKAGE_NAME is always a key 492 @Pure 493 public boolean packageName() { 494 return getFlag(PACKAGE_NAME); 495 } 496 497 /** 498 * See {@link #HAS_DUPLICATES}. 499 * 500 * @see #HAS_DUPLICATES 501 */ 502 @SuppressWarnings("keyfor") // HAS_DUPLICATES is always a key 503 @Pure 504 public boolean hasDuplicates() { 505 return getFlag(HAS_DUPLICATES); 506 } 507 508 /** 509 * See {@link #HAS_ORDER}. 510 * 511 * @see #HAS_ORDER 512 */ 513 @SuppressWarnings("keyfor") // HAS_ORDER is always a key 514 @Pure 515 public boolean hasOrder() { 516 return getFlag(HAS_ORDER); 517 } 518 519 /** 520 * See {@link #HAS_SIZE}. 521 * 522 * @see #HAS_SIZE 523 */ 524 @SuppressWarnings("keyfor") // HAS_SIZE is always a key 525 @Pure 526 public boolean hasSize() { 527 return getFlag(HAS_SIZE); 528 } 529 530 /** 531 * See {@link #HAS_NULL}. 532 * 533 * @see #HAS_NULL 534 */ 535 @SuppressWarnings("keyfor") // HAS_NULL is always a key 536 @Pure 537 public boolean hasNull() { 538 return getFlag(HAS_NULL); 539 } 540 541 /** 542 * See {@link #IS_STRUCT}. 543 * 544 * @see #IS_STRUCT 545 */ 546 @SuppressWarnings("keyfor") // IS_STRUCT is always a key 547 @Pure 548 public boolean isStruct() { 549 return getFlag(IS_STRUCT); 550 } 551 552 /** 553 * See {@link #IS_NON_NULL}. 554 * 555 * @see #IS_NON_NULL 556 */ 557 @SuppressWarnings("keyfor") // IS_NON_NULL is always a key 558 @Pure 559 public boolean isNonNull() { 560 return getFlag(IS_NON_NULL); 561 } 562}