001package daikon; 002 003import daikon.chicory.DaikonVariableInfo; 004import daikon.derive.Derivation; 005import daikon.derive.binary.BinaryDerivation; 006import daikon.derive.binary.SequenceFloatSubscript; 007import daikon.derive.binary.SequenceScalarSubscript; 008import daikon.derive.binary.SequenceStringSubscript; 009import daikon.derive.binary.SequenceSubsequence; 010import daikon.derive.ternary.SequenceFloatArbitrarySubsequence; 011import daikon.derive.ternary.SequenceScalarArbitrarySubsequence; 012import daikon.derive.ternary.SequenceStringArbitrarySubsequence; 013import daikon.derive.unary.SequenceLength; 014import daikon.derive.unary.UnaryDerivation; 015import daikon.inv.OutputFormat; 016import java.io.IOException; 017import java.io.ObjectInputStream; 018import java.io.Serializable; 019import java.lang.ref.WeakReference; 020import java.util.ArrayList; 021import java.util.Arrays; 022import java.util.Collection; 023import java.util.Collections; 024import java.util.Comparator; 025import java.util.HashSet; 026import java.util.List; 027import java.util.ListIterator; 028import java.util.Set; 029import java.util.WeakHashMap; 030import java.util.logging.Level; 031import java.util.logging.Logger; 032import org.checkerframework.checker.interning.qual.InternMethod; 033import org.checkerframework.checker.interning.qual.Interned; 034import org.checkerframework.checker.lock.qual.GuardSatisfied; 035import org.checkerframework.checker.nullness.qual.EnsuresNonNullIf; 036import org.checkerframework.checker.nullness.qual.Nullable; 037import org.checkerframework.checker.signedness.qual.UnknownSignedness; 038import org.checkerframework.dataflow.qual.Pure; 039import org.checkerframework.dataflow.qual.SideEffectFree; 040import org.plumelib.util.StringsPlume; 041 042// This class is deprecated. It should be removed as soon as Daikon no 043// longer supports the old decl format. 044 045// If you change this file, also change class daikon.test.VarInfoNameTest. 046 047/** 048 * VarInfoName represents the "name" of a variable. Calling it a "name", however, is somewhat 049 * misleading. It can be some expression that includes more than one variable, term, etc. We 050 * separate this from the VarInfo itself because clients wish to manipulate names into new 051 * expressions independent of the VarInfo that they might be associated with. VarInfoName's child 052 * classes are specific types of names, like applying a function to something. For example, "a" is a 053 * name, and "sin(a)" is a name that is the name "a" with the function "sin" applied to it. 054 */ 055@SuppressWarnings({"nullness", "interning"}) // deprecated file 056public abstract @Interned class VarInfoName implements Serializable, Comparable<VarInfoName> { 057 058 /** Debugging Logger. */ 059 public static Logger debug = Logger.getLogger("daikon.VarInfoName"); 060 061 // We are Serializable, so we specify a version to allow changes to 062 // method signatures without breaking serialization. If you add or 063 // remove fields, you should change this number to the current date. 064 static final long serialVersionUID = 20020614L; 065 066 /** 067 * When true, apply orig directly to variables, do not apply orig to derived variables. For 068 * example, create 'size(orig(a[]))' rather than 'orig(size(a[]))'. 069 */ 070 public static boolean dkconfig_direct_orig = false; 071 072 /** 073 * Given the standard String representation of a variable name (like what appears in the normal 074 * output format), return the corresponding VarInfoName. This method can't parse all the strings 075 * that the VarInfoName name() method might produce, but it should be able to handle anything that 076 * appears in a decls file. Specifically, it can only handle a subset of the grammar of derived 077 * variables. For some values of "name", "name.equals(parse(e.name()))" might throw an exception, 078 * but if it completes normally, the result should be true. 079 */ 080 public static VarInfoName parse(String name) { 081 082 // Remove the array indication from the new decl format 083 name = name.replace("[..]", "[]"); 084 085 // orig(x) 086 if (name.startsWith("orig(")) { 087 // throw new Error("orig() variables shouldn't appear in .decls files"); 088 assert name.endsWith(")") : name; 089 return parse(name.substring(5, name.length() - 1)).applyPrestate(); 090 } 091 092 // x.class 093 if (name.endsWith(DaikonVariableInfo.class_suffix)) { 094 return parse(name.substring(0, name.length() - DaikonVariableInfo.class_suffix.length())) 095 .applyTypeOf(); 096 } 097 098 // a quoted string 099 if (name.startsWith("\"") && name.endsWith("\"")) { 100 String content = name.substring(1, name.length() - 1); 101 if (content.equals(StringsPlume.escapeJava(StringsPlume.unescapeJava(content)))) { 102 return new Simple(name).intern(); 103 } 104 } 105 106 // x or this.x 107 if ((name.indexOf('[') == -1) && (name.indexOf('(') == -1)) { 108 // checking for only legal characters would be more robust 109 int dot = name.lastIndexOf('.'); 110 int arrow = name.lastIndexOf("->"); 111 if (dot >= 0 && dot > arrow) { 112 String first = name.substring(0, dot); 113 String field = name.substring(dot + 1); 114 return parse(first).applyField(field); 115 } else if (arrow >= 0 && arrow > dot) { 116 String first = name.substring(0, arrow); 117 String field = name.substring(arrow + 2); 118 return parse(first).applyField(field); 119 } else { 120 return new Simple(name).intern(); 121 } 122 } 123 124 // a[] 125 if (name.endsWith("[]")) { 126 return parse(name.substring(0, name.length() - 2)).applyElements(); 127 } 128 129 // foo[bar] -- IOA input only (pre-derived) 130 if (name.endsWith("]")) { 131 // This isn't quite right: we really want the matching open bracket, 132 // not the last open bracket. 133 int lbracket = name.lastIndexOf("["); 134 if (lbracket >= 0) { 135 String seqname = name.substring(0, lbracket) + "[]"; 136 String idxname = name.substring(lbracket + 1, name.length() - 1); 137 VarInfoName seq = parse(seqname); 138 VarInfoName idx = parse(idxname); 139 return seq.applySubscript(idx); 140 } 141 } 142 143 // a[].foo or a[].foo.bar 144 if (name.indexOf("[]") >= 0) { 145 int brackets = name.lastIndexOf("[]"); 146 int dot = name.lastIndexOf('.'); 147 int arrow = name.lastIndexOf("->"); 148 if (dot >= brackets && dot > arrow) { 149 String first = name.substring(0, dot); 150 String field = name.substring(dot + 1); 151 return parse(first).applyField(field); 152 } else if (arrow >= brackets && arrow > dot) { 153 String first = name.substring(0, arrow); 154 String field = name.substring(arrow + 2); 155 return parse(first).applyField(field); 156 } 157 } 158 159 // A.B, where A is complex: foo(x).y, x[7].y, etc. 160 int dot = name.lastIndexOf('.'); 161 int arrow = name.lastIndexOf("->"); 162 if (dot >= 0 && dot > arrow) { 163 String first = name.substring(0, dot); 164 String field = name.substring(dot + 1); 165 return parse(first).applyField(field); 166 } 167 168 // A->B, where A is complex: foo(x)->y, x[7]->y, etc. 169 if (arrow >= 0 && arrow > dot) { 170 String first = name.substring(0, arrow); 171 String field = name.substring(arrow + 2); 172 return parse(first).applyField(field); 173 } 174 175 // New decl format permits arbitrary uninterpreted strings as names 176 if (FileIO.new_decl_format) { 177 return new Simple(name).intern(); 178 } else { 179 throw new UnsupportedOperationException("parse error: '" + name + "'"); 180 } 181 } 182 183 /** 184 * Return the String representation of this name in the default output format. 185 * 186 * @return the string representation (interned) of this name, in the default output format 187 */ 188 @Pure 189 public @Interned String name(@GuardSatisfied VarInfoName this) { 190 if (name_cached == null) { 191 try { 192 name_cached = name_impl().intern(); 193 } catch (RuntimeException e) { 194 System.err.println("repr = " + repr()); 195 throw e; 196 } 197 } 198 return name_cached; 199 } 200 201 private @Interned String name_cached = null; // interned 202 203 /** 204 * Returns the String representation of this name in the default output format. Result is not 205 * interned; the client (name()) does so, then caches the interned value. 206 */ 207 protected abstract String name_impl(@GuardSatisfied VarInfoName this); 208 209 /** 210 * Return the String representation of this name in the esc style output format. 211 * 212 * @return the string representation (interned) of this name, in the esc style output format 213 */ 214 public @Interned String esc_name() { 215 if (esc_name_cached == null) { 216 try { 217 esc_name_cached = esc_name_impl().intern(); 218 } catch (RuntimeException e) { 219 System.err.println("repr = " + repr()); 220 throw e; 221 } 222 } 223 // System.out.println("esc_name = " + esc_name_cached + " for " + name() + " of class " + 224 // this.getClass().getName()); 225 return esc_name_cached; 226 } 227 228 private @Interned String esc_name_cached = null; // interned 229 230 /** 231 * Returns the String representation of this name in the ESC style output format. Cached by {@link 232 * #esc_name()}. 233 */ 234 protected abstract String esc_name_impl(); 235 236 /** 237 * Returns the string representation (interned) of this name, in the Simplify tool output format 238 * in the pre-state context. 239 * 240 * @return the string representation (interned) of this name, in the Simplify tool output format 241 * in the pre-state context 242 */ 243 public @Interned String simplify_name() { 244 return simplify_name(false); 245 } 246 247 /** 248 * Returns the string representation (interned) of this name, in the Simplify tool output format, 249 * in the given pre/post-state context. 250 * 251 * @param prestate if true, return the variable in a prestate context; if false, return the 252 * variable in a poststate context 253 * @return the string representation (interned) of this name, in the Simplify tool output format, 254 * in the given pre/post-state context 255 */ 256 protected @Interned String simplify_name(boolean prestate) { 257 int which = prestate ? 0 : 1; 258 if (simplify_name_cached[which] == null) { 259 try { 260 simplify_name_cached[which] = simplify_name_impl(prestate).intern(); 261 } catch (RuntimeException e) { 262 System.err.println("repr = " + repr()); 263 throw e; 264 } 265 } 266 return simplify_name_cached[which]; 267 } 268 269 // each element is interned 270 private @Interned String[] simplify_name_cached = new @Interned String[2]; 271 272 /** 273 * Returns the String representation of this name in the simplify output format in either prestate 274 * or poststate context. 275 */ 276 protected abstract String simplify_name_impl(boolean prestate); 277 278 /** 279 * Return the String representation of this name in the java style output format. 280 * 281 * @return the string representation (interned) of this name, in the java style output format 282 */ 283 public @Interned String java_name(VarInfo v) { 284 if (java_name_cached == null) { 285 try { 286 java_name_cached = java_name_impl(v).intern(); 287 } catch (RuntimeException e) { 288 System.err.println("repr = " + repr()); 289 throw e; 290 } 291 } 292 return java_name_cached; 293 } 294 295 private @Interned String java_name_cached = null; // interned 296 297 /** 298 * Return the String representation of this name in java format. Cached and interned by {@link 299 * #java_name}. 300 */ 301 protected abstract String java_name_impl(VarInfo v); 302 303 /** Return the String representation of this name in the JML style output format. */ 304 public @Interned String jml_name(VarInfo v) { 305 if (jml_name_cached == null) { 306 try { 307 jml_name_cached = jml_name_impl(v).intern(); 308 } catch (RuntimeException e) { 309 System.err.println("repr = " + repr()); 310 throw e; 311 } 312 } 313 // System.out.println("jml_name = " + jml_name_cached + " for " + name() + " of class " + 314 // this.getClass().getName()); 315 return jml_name_cached; 316 } 317 318 private @Interned String jml_name_cached = null; // interned 319 320 /** Returns the name in JML style output format. Cached and interned by {@link #jml_name}. */ 321 protected abstract String jml_name_impl(VarInfo v); 322 323 // For DBC, Java and JML formats, the formatting methods take as 324 // argument the VarInfo related to the VarInfoName in question. This 325 // causes trouble with VarInfoNameDriver (a class for testing 326 // VarInfoName), because there are no VarInfo's to pass to the 327 // formatting methods. So in places where the VarInfo argument is 328 // required by the formatting code, we use this variable to check 329 // whether we're doing testing. If we are, then we know that the 330 // VarInfo being passed is probably null, and we do something other 331 // than the normal thing (which would probably be to signal an 332 // error). Unfortunately, this prevents testing of some of those 333 // formats that make use of VarInfo information. 334 public static boolean testCall = false; 335 336 /** 337 * Return the String representation of this name in the dbc style output format. 338 * 339 * @param var the VarInfo which goes along with this VarInfoName. Used to determine the type of 340 * the variable. 341 * <p>If var is null, the only repercussion is that if `this' is an "orig(x)" expression, it 342 * will be formatted in jml-style, something like "\old(x)". 343 * <p>If var is not null and `this' is an "orig(x)" expressions, it will be formatted in 344 * Jtest's DBC style, as "$pre(<em>type</em>, x)". 345 * @return the string representation (interned) of this name, in the dbc style output format 346 */ 347 public @Interned String dbc_name(VarInfo var) { 348 if (dbc_name_cached == null) { 349 try { 350 dbc_name_cached = dbc_name_impl(var).intern(); 351 } catch (RuntimeException e) { 352 System.err.println("repr = " + repr()); 353 throw e; 354 } 355 } 356 return dbc_name_cached; 357 } 358 359 private @Interned String dbc_name_cached = null; // interned 360 361 /** 362 * Return the name in the DBC style output format. If v is null, uses JML style instead. Cached 363 * and interned by {@link #dbc_name}. 364 */ 365 protected abstract String dbc_name_impl(VarInfo v); 366 367 /** Return the String representation of this name using only letters, numbers, and underscores. */ 368 public @Interned String identifier_name() { 369 if (identifier_name_cached == null) { 370 try { 371 identifier_name_cached = identifier_name_impl().intern(); 372 } catch (RuntimeException e) { 373 System.err.println("repr = " + repr()); 374 throw e; 375 } 376 } 377 // System.out.println("identifier_name = " + identifier_name_cached + " for " + name() + " of 378 // class " + this.getClass().getName()); 379 return identifier_name_cached; 380 } 381 382 private @Interned String identifier_name_cached = null; // interned 383 384 /** 385 * Returns the name using only letters, numbers, and underscores. Cached and interned by {@link 386 * #identifier_name()}. 387 * 388 * @return the name using only letters, numbers, and underscores 389 */ 390 protected abstract String identifier_name_impl(); 391 392 /** 393 * Returns name of this in the specified format. 394 * 395 * @param format the format in which to return this variable name 396 * @param vi the VarInfo for this variable name 397 * @return name of this in the specified format 398 */ 399 public String name_using(OutputFormat format, VarInfo vi) { 400 401 if (format == OutputFormat.DAIKON) { 402 return name(); 403 } 404 if (format == OutputFormat.SIMPLIFY) { 405 return simplify_name(); 406 } 407 if (format == OutputFormat.ESCJAVA) { 408 return esc_name(); 409 } 410 if (format == OutputFormat.JAVA) { 411 return java_name(vi); 412 } 413 if (format == OutputFormat.JML) { 414 return jml_name(vi); 415 } 416 if (format == OutputFormat.DBCJAVA) { 417 return dbc_name(vi); 418 } 419 throw new UnsupportedOperationException("Unknown format requested: " + format); 420 } 421 422 /** 423 * Returns the name, in a debugging format. 424 * 425 * @return the name, in a debugging format 426 */ 427 public String repr(@GuardSatisfied @UnknownSignedness VarInfoName this) { 428 // AAD: Used to be interned for space reasons, but removed during 429 // profiling when it was determined that the interns are unique 430 // anyway. 431 if (repr_cached == null) { 432 repr_cached = repr_impl(); // .intern(); 433 } 434 return repr_cached; 435 } 436 437 /** The cached output of {@link #repr_impl}, or null. */ 438 private String repr_cached = null; 439 440 /** 441 * Returns the name in a verbose debugging format. Cached by {@link #repr}. 442 * 443 * @return the name in a verbose debugging format 444 */ 445 protected abstract String repr_impl(@GuardSatisfied @UnknownSignedness VarInfoName this); 446 447 // It would be nice if a generalized form of the mechanics of 448 // interning were abstracted out somewhere. 449 private static final WeakHashMap<VarInfoName, WeakReference<VarInfoName>> internTable = 450 new WeakHashMap<>(); 451 452 // This does not make any guarantee that the components of the 453 // VarInfoName are themselves interned. Should it? (I suspect so...) 454 @InternMethod 455 public VarInfoName intern() { 456 WeakReference<VarInfoName> ref = internTable.get(this); 457 if (ref != null) { 458 VarInfoName result = ref.get(); 459 return result; 460 } else { 461 @SuppressWarnings("interning") // intern method 462 @Interned VarInfoName this_interned = this; 463 internTable.put(this_interned, new WeakReference<>(this_interned)); 464 return this_interned; 465 } 466 } 467 468 // ============================================================ 469 // Constants 470 471 public static final VarInfoName ZERO = parse("0"); 472 public static final VarInfoName THIS = parse("this"); 473 public static final VarInfoName ORIG_THIS = parse("this").applyPrestate(); 474 475 // ============================================================ 476 // Observers 477 478 /** 479 * Returns true when this is "0", "-1", "1", etc. 480 * 481 * @return true when this is "0", "-1", "1", etc 482 */ 483 @Pure 484 public boolean isLiteralConstant() { 485 return false; 486 } 487 488 /** 489 * Returns the nodes of this, as given by an inorder traversal. 490 * 491 * @return the nodes of this, as given by an inorder traversal 492 */ 493 public Collection<VarInfoName> inOrderTraversal(@Interned VarInfoName this) { 494 return Collections.unmodifiableCollection(new InorderFlattener(this).nodes()); 495 } 496 497 /** 498 * Returns true iff the given node can be found in this. If the node has children, the whole 499 * subtree must match. 500 * 501 * @param node a variable name 502 * @return true iff the given node can be found in this. If the node has children, the whole 503 * subtree must match 504 */ 505 public boolean hasNode(VarInfoName node) { 506 return inOrderTraversal().contains(node); 507 } 508 509 /** 510 * Returns true iff a node of the given type exists in this. 511 * 512 * @param type the type to search for 513 * @return true iff a node of the given type exists in this 514 */ 515 public boolean hasNodeOfType(Class<?> type) { 516 for (VarInfoName vin : inOrderTraversal()) { 517 if (type.equals(vin.getClass())) { 518 return true; 519 } 520 } 521 return false; 522 } 523 524 /** 525 * Returns true iff a TypeOf node exists in this. 526 * 527 * @return true iff a TypeOf node exists in this 528 */ 529 public boolean hasTypeOf() { 530 return hasNodeOfType(VarInfoName.TypeOf.class); 531 } 532 533 /** 534 * Returns whether or not this name refers to the 'this' variable of a class. True for both normal 535 * and prestate versions of the variable. 536 */ 537 @Pure 538 public boolean isThis() { 539 if (name() == "this") { // interned 540 return true; 541 } 542 if (this instanceof VarInfoName.Prestate 543 && ((VarInfoName.Prestate) this).term.name() == "this") { // interned 544 return true; 545 } 546 547 return false; 548 } 549 550 /** 551 * Returns true if the given node is in a prestate context within this tree. 552 * 553 * @param node a member of this tree 554 * @return true if the given node is in a prestate context within this tree 555 */ 556 public boolean inPrestateContext(@Interned VarInfoName this, VarInfoName node) { 557 return new NodeFinder(this, node).inPre(); 558 } 559 560 /** 561 * Returns true if every variable in the name is an orig(...) variable. 562 * 563 * @return true if every variable in the name is an orig(...) variable 564 */ 565 @Pure 566 public boolean isAllPrestate(@Interned VarInfoName this) { 567 return new IsAllPrestateVisitor(this).result(); 568 } 569 570 /** 571 * Returns true if this VarInfoName contains a simple variable whose name is NAME. 572 * 573 * @param name the name to search for in this VarInfoName 574 * @return true if this VarInfoName contains a simple variable whose name is NAME 575 */ 576 public boolean includesSimpleName(@Interned VarInfoName this, String name) { 577 return new SimpleNamesVisitor(this).simples().contains(name); 578 } 579 580 // ============================================================ 581 // Special producers, or other helpers 582 583 /** Replace the first instance of node by replacement, in the data structure rooted at this. */ 584 public VarInfoName replace( 585 @Interned VarInfoName this, VarInfoName node, VarInfoName replacement) { 586 if (node == replacement) // "interned": equality optimization pattern 587 return this; 588 Replacer r = new Replacer(node, replacement); 589 return r.replace(this).intern(); 590 } 591 592 /** Replace all instances of node by replacement, in the data structure rooted at this. */ 593 public VarInfoName replaceAll( 594 @Interned VarInfoName this, VarInfoName node, VarInfoName replacement) { 595 if (node == replacement) // "interned": equality optimization pattern 596 return this; 597 598 // assert ! replacement.hasNode(node); // no infinite loop 599 600 // It doesn't make sense to assert this as we have plenty of times when 601 // we want to replace x by y where y may contain x. 602 603 Replacer r = new Replacer(node, replacement); 604 605 // This code used to loop as long as node was in result, but this isn't 606 // necessary -- all occurances are replaced by replacer. 607 608 VarInfoName result = r.replace(this).intern(); 609 return result; 610 } 611 612 // ============================================================ 613 // The usual Object methods 614 615 @EnsuresNonNullIf(result = true, expression = "#1") 616 @Pure 617 @Override 618 public boolean equals(@GuardSatisfied VarInfoName this, @GuardSatisfied @Nullable Object o) { 619 return (o instanceof VarInfoName) && equalsVarInfoName((VarInfoName) o); 620 } 621 622 @EnsuresNonNullIf(result = true, expression = "#1") 623 @Pure 624 public boolean equalsVarInfoName( 625 @GuardSatisfied @Interned VarInfoName this, @GuardSatisfied VarInfoName other) { 626 return ((other == this) // "interned": equality optimization pattern 627 || ((other != null) && this.repr().equals(other.repr()))); 628 } 629 630 // This should be safe even in the absence of caching, because "repr()" 631 // returns a new string each time, but it is equal() to any other 632 // returned string, so their hashCode()s should be the same. 633 @Pure 634 @Override 635 public int hashCode(@GuardSatisfied @UnknownSignedness VarInfoName this) { 636 return repr().hashCode(); 637 } 638 639 @Pure 640 @Override 641 public int compareTo(@GuardSatisfied VarInfoName this, VarInfoName other) { 642 int nameCmp = name().compareTo(other.name()); 643 if (nameCmp != 0) { 644 return nameCmp; 645 } 646 int reprCmp = repr().compareTo(other.repr()); 647 return reprCmp; 648 } 649 650 // This is a debugging method, not intended for ordinary output. 651 // Code producing output should usually call name() rather than 652 // calling toString (perhaps implicitly). 653 @SideEffectFree 654 @Override 655 public String toString(@GuardSatisfied VarInfoName this) { 656 return repr(); 657 } 658 659 // Interning is lost when an object is serialized and deserialized. 660 // Manually re-intern any interned fields upon deserialization. 661 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 662 in.defaultReadObject(); 663 if (name_cached != null) name_cached = name_cached.intern(); 664 if (esc_name_cached != null) esc_name_cached = esc_name_cached.intern(); 665 if (simplify_name_cached[0] != null) simplify_name_cached[0] = simplify_name_cached[0].intern(); 666 if (simplify_name_cached[1] != null) simplify_name_cached[1] = simplify_name_cached[1].intern(); 667 if (java_name_cached != null) java_name_cached = java_name_cached.intern(); 668 if (jml_name_cached != null) jml_name_cached = jml_name_cached.intern(); 669 if (dbc_name_cached != null) dbc_name_cached = dbc_name_cached.intern(); 670 } 671 672 // ============================================================ 673 // Static inner classes that form the expression langugage 674 675 /** A simple identifier like "a", etc. */ 676 public static @Interned class Simple extends VarInfoName { 677 // We are Serializable, so we specify a version to allow changes to 678 // method signatures without breaking serialization. If you add or 679 // remove fields, you should change this number to the current date. 680 static final long serialVersionUID = 20020130L; 681 682 public final String name; 683 684 public Simple(String name) { 685 assert name != null; 686 this.name = name; 687 } 688 689 @Pure 690 @Override 691 public boolean isLiteralConstant() { 692 try { 693 Integer.parseInt(name); 694 return true; 695 } catch (NumberFormatException e) { 696 return false; 697 } 698 } 699 700 @Override 701 protected String repr_impl(@GuardSatisfied @UnknownSignedness Simple this) { 702 return name; 703 } 704 705 @Override 706 protected String name_impl(@GuardSatisfied Simple this) { 707 return name; 708 } 709 710 @Override 711 protected String esc_name_impl() { 712 return "return".equals(name) ? "\\result" : name; 713 } 714 715 @Override 716 protected String simplify_name_impl(boolean prestate) { 717 if (isLiteralConstant()) { 718 return name; 719 } else { 720 return simplify_name_impl(name, prestate); 721 } 722 } 723 724 // Names must be either a legal C/Java style identifier, or 725 // surrounded by vertical bars (Simplify's quoting mechanism); 726 // other than that, they only have to be consistent within one 727 // execution of Daikon. 728 protected static String simplify_name_impl(String s, boolean prestate) { 729 if (s.startsWith("~") && s.endsWith("~")) { 730 s = s.substring(1, s.length() - 2) + ":closure"; 731 } 732 if (prestate) { 733 s = "__orig__" + s; 734 } 735 return "|" + s + "|"; 736 } 737 738 @Override 739 protected String java_name_impl(VarInfo v) { 740 return "return".equals(name) ? "\\result" : name; 741 } 742 743 @Override 744 protected String jml_name_impl(VarInfo v) { 745 return "return".equals(name) ? "\\result" : name; 746 } 747 748 @Override 749 protected String dbc_name_impl(VarInfo v) { 750 if (name.equals("return")) { 751 return "$result"; 752 } else { 753 return name; 754 } 755 } 756 757 @Override 758 protected String identifier_name_impl() { 759 if (name.equals("return")) { 760 return "Daikon_return"; 761 } else if (name.equals("this")) { 762 return "Daikon_this"; 763 } else { 764 StringBuilder buf = new StringBuilder(); 765 for (int i = 0; i < name.length(); i++) { 766 char c = name.charAt(i); 767 if (Character.isLetterOrDigit(c)) buf.append(c); 768 else if (c == '_') buf.append("__"); 769 else if (c == '$') buf.append("_dollar_"); 770 else if (c == ':') buf.append("_colon_"); 771 else if (c == '*') buf.append("star_"); 772 else { 773 throw new Error("Unexpected character in VarInfoName$Simple"); 774 } 775 } 776 return buf.toString(); 777 } 778 } 779 780 @Override 781 public <T> T accept(Visitor<T> v) { 782 return v.visitSimple(this); 783 } 784 } 785 786 /** 787 * Returns true iff applySize will not throw an exception. 788 * 789 * @return true iff applySize will not throw an exception 790 * @see #applySize 791 */ 792 @Pure 793 public boolean isApplySizeSafe() { 794 return new ElementsFinder(this).elems() != null; 795 } 796 797 /** 798 * Returns a name for the size of this (this object should be a sequence). Form is like 799 * "size(a[])" or "a.length". 800 * 801 * @return a name for the size of this 802 */ 803 public VarInfoName applySize(@Interned VarInfoName this) { 804 // The simple approach: 805 // return new SizeOf((Elements) this).intern(); 806 // is wrong because this might be "orig(a[])". 807 if (dkconfig_direct_orig) { 808 return new SizeOf(this).intern(); 809 } else { 810 Elements elems = new ElementsFinder(this).elems(); 811 if (elems == null) { 812 throw new Error( 813 "applySize should have elements to use in " 814 + name() 815 + ";" 816 + Global.lineSep 817 + "that is, " 818 + name() 819 + " does not appear to be a sequence/collection." 820 + Global.lineSep 821 + "Perhaps its name should be suffixed by \"[]\"?" 822 + Global.lineSep 823 + " this.class = " 824 + getClass().getName()); 825 } 826 827 // If this is orig, replace the elems with sizeof, leaving orig 828 // where it is. If it is not orig, simply return the sizeof the 829 // elems (ignoring anthing outside of the elems (like additional 830 // fields or typeof)). This allows this code to work correctly 831 // for variables such as a[].b.c (returns size(a[])) or 832 // a[].getClass().getName() (returns size(a[])) 833 if (this instanceof Prestate) { 834 VarInfoName size = new SizeOf(elems).intern(); 835 return new Prestate(size).intern(); 836 // Replacer r = new Replacer(elems, new SizeOf(elems).intern()); 837 // return r.replace(this).intern(); 838 } else { 839 return new SizeOf(elems).intern(); 840 } 841 } 842 } 843 844 /** 845 * If this is a slice, (potentially in pre-state), return its lower and upper bounds, which can be 846 * subtracted to get one less than its size. 847 */ 848 public @Interned VarInfoName[] getSliceBounds(@Interned VarInfoName this) { 849 VarInfoName vin = this; 850 boolean inPrestate = false; 851 if (vin instanceof Prestate) { 852 inPrestate = true; 853 vin = ((Prestate) vin).term; 854 } 855 while (vin instanceof Field) { 856 vin = ((Field) vin).term; 857 } 858 if (!(vin instanceof Slice)) { 859 return null; 860 } 861 Slice slice = (Slice) vin; 862 @Interned VarInfoName[] ret = new @Interned VarInfoName[2]; 863 if (slice.i != null) { 864 ret[0] = slice.i; 865 } else { 866 ret[0] = ZERO; 867 } 868 if (slice.j != null) { 869 ret[1] = slice.j; 870 } else { 871 ret[1] = slice.sequence.applySize().applyAdd(-1); 872 } 873 if (inPrestate) { 874 ret[0] = ret[0].applyPrestate(); 875 ret[1] = ret[1].applyPrestate(); 876 } 877 return ret; 878 } 879 880 /** The size of a contained sequence; form is like "size(sequence)" or "sequence.length". */ 881 public static @Interned class SizeOf extends VarInfoName { 882 // We are Serializable, so we specify a version to allow changes to 883 // method signatures without breaking serialization. If you add or 884 // remove fields, you should change this number to the current date. 885 static final long serialVersionUID = 20020130L; 886 887 public final VarInfoName sequence; 888 889 public SizeOf(VarInfoName sequence) { 890 assert sequence != null; 891 this.sequence = sequence; 892 } 893 894 @Override 895 protected String repr_impl(@GuardSatisfied @UnknownSignedness SizeOf this) { 896 return "SizeOf[" + sequence.repr() + "]"; 897 } 898 899 @Override 900 protected String name_impl(@GuardSatisfied SizeOf this) { 901 return "size(" + sequence.name() + ")"; 902 903 // I'm not sure how to get this right; seems to require info about 904 // the variable type. 905 // // The result could be either "sequence.length" or "sequence.size()", 906 // // depending on the type of "sequence". 907 // String seqname = sequence.name(); 908 // if (seqname.endsWith("[]") 909 // // This clause is too confusing for C output, where some 910 // // variables get "size(seq)" and some get seq.length. 911 // // && ! seqname.startsWith("::") 912 // ) { 913 // return sequence.term.name() + ".length"; 914 // } else { 915 // return seqname + ".size()"; 916 // } 917 } 918 919 /** Returns the hashcode that is the base of the array. */ 920 @Pure 921 public VarInfoName get_term() { 922 if (sequence instanceof Elements) { 923 return ((Elements) sequence).term; 924 } else if (sequence instanceof Prestate) { 925 VarInfoName term = ((Prestate) sequence).term; 926 return ((Elements) term).term; 927 } 928 throw new RuntimeException("unexpected term in sizeof " + this); 929 } 930 931 @Override 932 protected String esc_name_impl() { 933 return get_term().esc_name() + ".length"; 934 } 935 936 @Override 937 protected String simplify_name_impl(boolean prestate) { 938 return "(arrayLength " + get_term().simplify_name(prestate) + ")"; 939 } 940 941 @Override 942 protected String java_name_impl(VarInfo v) { 943 return java_family_impl(OutputFormat.JAVA, v); 944 } 945 946 @Override 947 protected String jml_name_impl(VarInfo v) { 948 return java_family_impl(OutputFormat.JML, v); 949 } 950 951 @Override 952 protected String dbc_name_impl(VarInfo v) { 953 return java_family_impl(OutputFormat.DBCJAVA, v); 954 } 955 956 protected String java_family_impl(OutputFormat format, VarInfo v) { 957 958 // See declaration of testCall for explanation of this flag. 959 if (testCall) { 960 return "no format when testCall."; 961 } 962 963 assert v != null; 964 assert v.isDerived(); 965 Derivation derived = v.derived; 966 assert derived instanceof SequenceLength; 967 VarInfo seqVarInfo = ((SequenceLength) derived).base; 968 String prefix = get_term().name_using(format, seqVarInfo); 969 return "daikon.Quant.size(" + prefix + ")"; 970 // if (seqVarInfo.type.pseudoDimensions() > seqVarInfo.type.dimensions()) { 971 // if (prefix.startsWith("daikon.Quant.collect")) { 972 // // Quant collect methods returns an array 973 // return prefix + ".length"; 974 // } else { 975 // // It's a Collection 976 // return prefix + ".size()"; 977 // } 978 // } else { 979 // // It's an array 980 // return prefix + ".length"; 981 // } 982 } 983 984 @Override 985 protected String identifier_name_impl() { 986 return "size_of" + sequence.identifier_name() + "___"; 987 } 988 989 @Override 990 public <T> T accept(Visitor<T> v) { 991 return v.visitSizeOf(this); 992 } 993 } 994 995 /** 996 * Returns a name for a unary function applied to this object. The result is like "sum(this)". 997 * 998 * @param function the function to apply 999 * @return a name for the function applied to this 1000 */ 1001 public VarInfoName applyFunction(@Interned VarInfoName this, String function) { 1002 return new FunctionOf(function, this).intern(); 1003 } 1004 1005 /** 1006 * Returns a name for a function applied to more than one argument. The result is like "sum(var1, 1007 * var2)". 1008 * 1009 * @param function the name of the function 1010 * @param vars the arguments to the function, of type VarInfoName 1011 * @return a name for a function applied to multiple arguments 1012 */ 1013 public static VarInfoName applyFunctionOfN(String function, List<VarInfoName> vars) { 1014 return new FunctionOfN(function, vars).intern(); 1015 } 1016 1017 /** 1018 * Returns a name for a function of more than one argument. The result is like "sum(var1, var2)". 1019 * 1020 * @param function the name of the function 1021 * @param vars the arguments to the function 1022 */ 1023 public static VarInfoName applyFunctionOfN(String function, @Interned VarInfoName[] vars) { 1024 // This causes an odd error with the Interned checker: 1025 // return applyFunctionOfN(function, Arrays.<@Interned VarInfoName>asList(vars)); 1026 return applyFunctionOfN(function, Arrays.asList(vars)); 1027 } 1028 1029 /** A function over a term, like "sum(argument)". */ 1030 public static @Interned class FunctionOf extends VarInfoName { 1031 // We are Serializable, so we specify a version to allow changes to 1032 // method signatures without breaking serialization. If you add or 1033 // remove fields, you should change this number to the current date. 1034 static final long serialVersionUID = 20020130L; 1035 1036 public final String function; 1037 public final VarInfoName argument; 1038 1039 public FunctionOf(String function, VarInfoName argument) { 1040 assert function != null; 1041 assert argument != null; 1042 this.function = function; 1043 this.argument = argument; 1044 } 1045 1046 @Override 1047 protected String repr_impl(@GuardSatisfied @UnknownSignedness FunctionOf this) { 1048 return "FunctionOf{" + function + "}[" + argument.repr() + "]"; 1049 } 1050 1051 @Override 1052 protected String name_impl(@GuardSatisfied FunctionOf this) { 1053 return function + "(" + argument.name() + ")"; 1054 } 1055 1056 @Override 1057 protected String esc_name_impl() { 1058 return "(warning: format_esc() needs to be implemented: " 1059 + function 1060 + " on " 1061 + argument.repr() 1062 + ")"; 1063 } 1064 1065 @Override 1066 protected String simplify_name_impl(boolean prestate) { 1067 return "(warning: format_simplify() needs to be implemented: " 1068 + function 1069 + " on " 1070 + argument.repr() 1071 + ")"; 1072 } 1073 1074 @Override 1075 protected String java_name_impl(VarInfo v) { 1076 return java_family_name_impl(OutputFormat.JAVA, v); 1077 } 1078 1079 @Override 1080 protected String jml_name_impl(VarInfo v) { 1081 return java_family_name_impl(OutputFormat.JML, v); 1082 } 1083 1084 @Override 1085 protected String dbc_name_impl(VarInfo v) { 1086 return java_family_name_impl(OutputFormat.DBCJAVA, v); 1087 } 1088 1089 protected String java_family_name_impl(OutputFormat format, VarInfo v) { 1090 1091 // See declaration of testCall for explanation of this flag. 1092 if (testCall) { 1093 return "no format when testCall."; 1094 } 1095 1096 assert v != null; 1097 assert v.isDerived(); 1098 Derivation derived = v.derived; 1099 assert derived instanceof UnaryDerivation; 1100 VarInfo argVarInfo = ((UnaryDerivation) derived).base; 1101 return "daikon.Quant." + function + "(" + argument.name_using(format, argVarInfo) + ")"; 1102 } 1103 1104 @Override 1105 protected String identifier_name_impl() { 1106 return function + "_of_" + argument.identifier_name() + "___"; 1107 } 1108 1109 @Override 1110 public <T> T accept(Visitor<T> v) { 1111 return v.visitFunctionOf(this); 1112 } 1113 } 1114 1115 /** A function of multiple parameters. */ 1116 public static @Interned class FunctionOfN extends VarInfoName { 1117 /** If you add or remove fields, change this number to the current date. */ 1118 static final long serialVersionUID = 20020130L; 1119 1120 /** The function being invoked. */ 1121 public final String function; 1122 1123 /** The parameters. */ 1124 @SuppressWarnings("serial") 1125 public final List<VarInfoName> args; 1126 1127 /** 1128 * Construct a new function of multiple arguments. 1129 * 1130 * @param function the name of the function 1131 * @param args the arguments to the function, of type VarInfoName 1132 */ 1133 public FunctionOfN(String function, List<VarInfoName> args) { 1134 assert function != null; 1135 assert args != null; 1136 this.args = args; 1137 this.function = function; 1138 } 1139 1140 /** 1141 * Returns a string representation of the elements of this. 1142 * 1143 * @return a string representation of the elements of this 1144 */ 1145 private List<String> elts_repr(@GuardSatisfied @UnknownSignedness FunctionOfN this) { 1146 List<String> elts = new ArrayList<>(args.size()); 1147 for (VarInfoName vin : args) { 1148 elts.add(vin.repr()); 1149 } 1150 return elts; 1151 } 1152 1153 /** 1154 * Return a comma-separated list of element names. 1155 * 1156 * @return comma-separated list of element names 1157 */ 1158 private String elts_repr_commas(@GuardSatisfied @UnknownSignedness FunctionOfN this) { 1159 return String.join(", ", elts_repr()); 1160 } 1161 1162 @Override 1163 protected String repr_impl(@GuardSatisfied @UnknownSignedness FunctionOfN this) { 1164 return "FunctionOfN{" + function + "}[" + elts_repr_commas() + "]"; 1165 } 1166 1167 @Override 1168 protected String name_impl(@GuardSatisfied FunctionOfN this) { 1169 return function + "(" + elts_repr_commas() + ")"; 1170 } 1171 1172 @Override 1173 protected String esc_name_impl() { 1174 return "(warning: format_esc() needs to be implemented: " 1175 + function 1176 + " on " 1177 + elts_repr_commas() 1178 + ")"; 1179 } 1180 1181 @Override 1182 protected String simplify_name_impl(boolean prestate) { 1183 return "(warning: format_simplify() needs to be implemented: " 1184 + function 1185 + " on " 1186 + elts_repr_commas() 1187 + ")"; 1188 } 1189 1190 @Override 1191 protected String java_name_impl(VarInfo v) { 1192 return java_family_name_impl(OutputFormat.JAVA, v); 1193 } 1194 1195 @Override 1196 protected String jml_name_impl(VarInfo v) { 1197 return java_family_name_impl(OutputFormat.JML, v); 1198 } 1199 1200 @Override 1201 protected String dbc_name_impl(VarInfo v) { 1202 return java_family_name_impl(OutputFormat.DBCJAVA, v); 1203 } 1204 1205 // Only works for two-argument functions. There are currently no 1206 // ternary (or greater) function applications in Daikon. 1207 protected String java_family_name_impl(OutputFormat format, VarInfo v) { 1208 1209 // See declaration of testCall for explanation of this flag. 1210 if (testCall) { 1211 return "no format when testCall."; 1212 } 1213 1214 assert v != null; 1215 assert v.isDerived(); 1216 Derivation derived = v.derived; 1217 assert derived instanceof BinaryDerivation; 1218 // || derived instanceof TernaryDerivation); 1219 assert args.size() == 2; 1220 VarInfo arg1VarInfo = ((BinaryDerivation) derived).base1; 1221 VarInfo arg2VarInfo = ((BinaryDerivation) derived).base2; 1222 return "daikon.Quant." 1223 + function 1224 + "(" 1225 + args.get(0).name_using(format, arg1VarInfo) 1226 + ", " 1227 + args.get(1).name_using(format, arg2VarInfo) 1228 + ")"; 1229 } 1230 1231 @Override 1232 protected String identifier_name_impl() { 1233 List<String> elts = new ArrayList<>(args.size()); 1234 for (VarInfoName vin : args) { 1235 elts.add(vin.identifier_name()); 1236 } 1237 return function + "_of_" + String.join("_comma_", elts) + "___"; 1238 } 1239 1240 /** Shortcut getter to avoid repeated type casting. */ 1241 public VarInfoName getArg(int n) { 1242 return args.get(n); 1243 } 1244 1245 @Override 1246 public <T> T accept(Visitor<T> v) { 1247 return v.visitFunctionOfN(this); 1248 } 1249 } 1250 1251 /** 1252 * Returns a name for the intersection of with another sequence, like "intersect(a[], b[])". 1253 * 1254 * @param seq2 the variable to intersect with 1255 * @return the name for the intersection of this and seq2 1256 */ 1257 public VarInfoName applyIntersection(@Interned VarInfoName this, VarInfoName seq2) { 1258 assert seq2 != null; 1259 return new Intersection(this, seq2).intern(); 1260 } 1261 1262 /** 1263 * Intersection of two sequences. Extends FunctionOfN, and the only change is that it does special 1264 * formatting for IOA. 1265 */ 1266 public static @Interned class Intersection extends FunctionOfN { 1267 // We are Serializable, so we specify a version to allow changes to 1268 // method signatures without breaking serialization. If you add or 1269 // remove fields, you should change this number to the current date. 1270 static final long serialVersionUID = 20020130L; 1271 1272 public Intersection(VarInfoName seq1, VarInfoName seq2) { 1273 super("intersection", Arrays.asList(seq1, seq2)); 1274 } 1275 } 1276 1277 /** 1278 * Returns a name for the union of this with another sequence, like "union(a[], b[])". 1279 * 1280 * @param seq2 the variable to union with 1281 * @return the name for the intersection of this and seq2 1282 */ 1283 public VarInfoName applyUnion(@Interned VarInfoName this, VarInfoName seq2) { 1284 assert seq2 != null; 1285 return new Union(this, seq2).intern(); 1286 } 1287 1288 /** 1289 * Union of two sequences. Extends FunctionOfN, and the only change is that it does special 1290 * formatting for IOA. 1291 */ 1292 public static @Interned class Union extends FunctionOfN { 1293 // We are Serializable, so we specify a version to allow changes to 1294 // method signatures without breaking serialization. If you add or 1295 // remove fields, you should change this number to the current date. 1296 static final long serialVersionUID = 20020130L; 1297 1298 public Union(VarInfoName seq1, VarInfoName seq2) { 1299 super("intersection", Arrays.asList(seq1, seq2)); 1300 } 1301 } 1302 1303 /** 1304 * Returns a 'getter' operation for some field of this name, like a.foo if this is a. 1305 * 1306 * @param field the field 1307 * @return the name for the given field of this 1308 */ 1309 public VarInfoName applyField(@Interned VarInfoName this, String field) { 1310 return new Field(this, field).intern(); 1311 } 1312 1313 /** A 'getter' operation for some field, like a.foo. */ 1314 public static @Interned class Field extends VarInfoName { 1315 // We are Serializable, so we specify a version to allow changes to 1316 // method signatures without breaking serialization. If you add or 1317 // remove fields, you should change this number to the current date. 1318 static final long serialVersionUID = 20020130L; 1319 1320 public final VarInfoName term; 1321 public final String field; 1322 1323 public Field(VarInfoName term, String field) { 1324 assert term != null; 1325 assert field != null; 1326 this.term = term; 1327 this.field = field; 1328 } 1329 1330 @Override 1331 protected String repr_impl(@GuardSatisfied @UnknownSignedness Field this) { 1332 return "Field{" + field + "}[" + term.repr() + "]"; 1333 } 1334 1335 @Override 1336 protected String name_impl(@GuardSatisfied Field this) { 1337 return term.name() + "." + field; 1338 } 1339 1340 @Override 1341 protected String esc_name_impl() { 1342 return term.esc_name() + "." + field; 1343 } 1344 1345 @Override 1346 protected String simplify_name_impl(boolean prestate) { 1347 return "(select " 1348 + Simple.simplify_name_impl(field, false) 1349 + " " 1350 + term.simplify_name(prestate) 1351 + ")"; 1352 } 1353 1354 @Override 1355 protected String java_name_impl(VarInfo v) { 1356 return java_family_name(OutputFormat.JAVA, v); 1357 } 1358 1359 @Override 1360 protected String jml_name_impl(VarInfo v) { 1361 return java_family_name(OutputFormat.JML, v); 1362 } 1363 1364 @Override 1365 protected String dbc_name_impl(VarInfo v) { 1366 return java_family_name(OutputFormat.DBCJAVA, v); 1367 } 1368 1369 // Special case: the fake "toString" field in Daikon is output 1370 // with parens, so that it's legal Java. 1371 protected String java_field(String f) { 1372 if (f.equals("toString")) { 1373 return "toString()"; 1374 } else { 1375 return f; 1376 } 1377 } 1378 1379 // For JAVA, JML and DBC formats. 1380 protected String java_family_name(OutputFormat format, VarInfo v) { 1381 1382 // See declaration of testCall for explanation of this flag. 1383 if (testCall) { 1384 return "no format when testCall."; 1385 } 1386 1387 if (term.name().indexOf("..") != -1) { 1388 // We cannot translate arr[i..].x because this translates into 1389 // 1390 // "daikon.Quant.collect(daikon.Quant.slice(arr,i,arr.length),"x")" 1391 // 1392 // but slice() returns an array of Objects, so an error will 1393 // occur when method collect() tries to query for field "x". 1394 return "(warning: " 1395 + format 1396 + " format cannot express a field applied to a slice:" 1397 + " [repr=" 1398 + repr() 1399 + "])"; 1400 } 1401 1402 boolean hasBrackets = (term.name().indexOf("[]") != -1); 1403 1404 if (format == OutputFormat.JAVA) { 1405 assert !hasBrackets || v.type.dimensions() > 0 1406 : "hasBrackets:" + hasBrackets + ", dimensions:" + v.type.dimensions() + ", v:" + v; 1407 } 1408 1409 if (!hasBrackets && format != OutputFormat.JAVA) { 1410 // Case 1: Not an array collection 1411 String term_name = null; 1412 if (format == OutputFormat.JML) { 1413 term_name = term.jml_name(v); 1414 } else { 1415 term_name = term.dbc_name(v); 1416 } 1417 return term_name + "." + java_field(field); 1418 } 1419 1420 // Case 2: An array collection 1421 1422 // How to translate foo[].f, which is the array obtained from 1423 // collecting o.f for every element o in the array foo? Just as 1424 // we did for slices, we'll translate this into a call of an 1425 // external function to do the job: 1426 1427 // x.y.foo[].bar.f 1428 // ---translates-into---> 1429 // daikon.Quant.collect_TYPE_(x, "y.foo[].bar.f") 1430 1431 // The method Quant.collect takes care of the "y.foo[].bar.f" 1432 // mess for object x. 1433 1434 if (field.equals("toString")) { 1435 return "(warning: " 1436 + format 1437 + " format cannot express a slice with String objects:" 1438 + " obtained by toString(): [repr=" 1439 + repr() 1440 + "])"; 1441 } 1442 1443 String term_name_no_brackets = term.name().replaceAll("\\[\\]", "") + "." + field; 1444 1445 @SuppressWarnings("keyfor") // PACKAGE_NAME is always a key 1446 String packageName = v.aux.getValue(VarInfoAux.PACKAGE_NAME); 1447 if (packageName.equals(VarInfoAux.NO_PACKAGE_NAME)) { 1448 packageName = ""; 1449 } 1450 1451 String[] splits; 1452 boolean isStatic = false; 1453 String packageNamePrefix = null; 1454 // if (isStatic) { 1455 if (term_name_no_brackets.startsWith(packageName + ".")) { 1456 // throw new Error("packageName=" + packageName + ", term_name_no_brackets=" + 1457 // term_name_no_brackets); 1458 // } 1459 // Before splitting, remove the package name. 1460 packageNamePrefix = (packageName.equals("") ? "" : packageName + "."); 1461 isStatic = true; 1462 splits = term_name_no_brackets.substring(packageNamePrefix.length()).split("\\."); 1463 } else { 1464 packageNamePrefix = ""; 1465 isStatic = false; 1466 splits = term_name_no_brackets.split("\\."); 1467 } 1468 1469 String object = splits[0]; 1470 if (isStatic) { 1471 object += DaikonVariableInfo.class_suffix; 1472 } 1473 if (object.equals("return")) { 1474 if (format == OutputFormat.DBCJAVA) { 1475 object = "$return"; 1476 } else { 1477 object = "\\result"; 1478 } 1479 } 1480 1481 String fields = ""; 1482 for (int j = 1; j < splits.length; j++) { 1483 if (j != 1) { 1484 fields += "."; 1485 } 1486 fields += splits[j]; 1487 } 1488 1489 String collectType = (v.type.baseIsPrimitive() ? v.type.base() : "Object"); 1490 1491 if (format == OutputFormat.JAVA) { 1492 return 1493 // On one line to enable searches for "collect.*_field". 1494 "daikon.Quant.collect" 1495 + collectType 1496 + (!v.is_array() ? "_field" : "") 1497 + "(" 1498 + packageNamePrefix 1499 + object 1500 + ", " 1501 + "\"" 1502 + fields 1503 + "\"" 1504 + ")"; 1505 } else { 1506 return "daikon.Quant.collect" 1507 + collectType 1508 + "(" 1509 + packageNamePrefix 1510 + object 1511 + ", " 1512 + "\"" 1513 + fields 1514 + "\"" 1515 + ")"; 1516 } 1517 } 1518 1519 @Override 1520 protected String identifier_name_impl() { 1521 return term.identifier_name() + "_dot_" + field; 1522 } 1523 1524 @Override 1525 public <T> T accept(Visitor<T> v) { 1526 return v.visitField(this); 1527 } 1528 } 1529 1530 /** 1531 * Returns a name for the type of this object; form is like "this.getClass().getName()" or 1532 * "\typeof(this)". 1533 * 1534 * @return the name for the type of this object 1535 */ 1536 public VarInfoName applyTypeOf(@Interned VarInfoName this) { 1537 return new TypeOf(this).intern(); 1538 } 1539 1540 /** The type of the term, like "term.getClass().getName()" or "\typeof(term)". */ 1541 public static @Interned class TypeOf extends VarInfoName { 1542 // We are Serializable, so we specify a version to allow changes to 1543 // method signatures without breaking serialization. If you add or 1544 // remove fields, you should change this number to the current date. 1545 static final long serialVersionUID = 20020130L; 1546 1547 public final VarInfoName term; 1548 1549 public TypeOf(VarInfoName term) { 1550 assert term != null; 1551 this.term = term; 1552 } 1553 1554 @Override 1555 protected String repr_impl(@GuardSatisfied @UnknownSignedness TypeOf this) { 1556 return "TypeOf[" + term.repr() + "]"; 1557 } 1558 1559 @Override 1560 protected String name_impl(@GuardSatisfied TypeOf this) { 1561 return term.name() + DaikonVariableInfo.class_suffix; 1562 } 1563 1564 @Override 1565 protected String esc_name_impl() { 1566 return "\\typeof(" + term.esc_name() + ")"; 1567 } 1568 1569 @Override 1570 protected String simplify_name_impl(boolean prestate) { 1571 return "(typeof " + term.simplify_name(prestate) + ")"; 1572 } 1573 1574 @SideEffectFree 1575 protected String javaFamilyFormat(String varname, boolean isArray) { 1576 if (isArray) { 1577 return "daikon.Quant.typeArray(" + varname + ")"; 1578 } else { 1579 return varname + DaikonVariableInfo.class_suffix; 1580 } 1581 } 1582 1583 @Override 1584 protected String java_name_impl(VarInfo v) { 1585 if (testCall) { 1586 return "no format when testCall."; 1587 } 1588 return javaFamilyFormat(term.java_name(v), v.type.isArray()); 1589 } 1590 1591 @Override 1592 protected String jml_name_impl(VarInfo v) { 1593 if (testCall) { 1594 return "no format when testCall."; 1595 } 1596 return javaFamilyFormat(term.jml_name(v), v.type.isArray()); 1597 } 1598 1599 @Override 1600 protected String dbc_name_impl(VarInfo v) { 1601 if (testCall) { 1602 return "no format when testCall."; 1603 } 1604 return javaFamilyFormat(term.dbc_name(v), v.type.isArray()); 1605 } 1606 1607 @Override 1608 protected String identifier_name_impl() { 1609 return "type_of_" + term.identifier_name() + "___"; 1610 } 1611 1612 @Override 1613 public <T> T accept(Visitor<T> v) { 1614 return v.visitTypeOf(this); 1615 } 1616 } 1617 1618 /** 1619 * Returns a name for a the prestate value of this object; form is like "orig(this)" or 1620 * "\old(this)". 1621 */ 1622 public VarInfoName applyPrestate(@Interned VarInfoName this) { 1623 if (this instanceof Poststate) { 1624 return ((Poststate) this).term; 1625 } else if ((this instanceof Add) && ((Add) this).term instanceof Poststate) { 1626 Add a = (Add) this; 1627 Poststate p = (Poststate) a.term; 1628 return p.term.applyAdd(a.amount); 1629 } else { 1630 return new Prestate(this).intern(); 1631 } 1632 } 1633 1634 /** The prestate value of a term, like "orig(term)" or "\old(term)". */ 1635 public static @Interned class Prestate extends VarInfoName { 1636 // We are Serializable, so we specify a version to allow changes to 1637 // method signatures without breaking serialization. If you add or 1638 // remove fields, you should change this number to the current date. 1639 static final long serialVersionUID = 20020130L; 1640 1641 public final VarInfoName term; 1642 1643 public Prestate(VarInfoName term) { 1644 assert term != null; 1645 this.term = term; 1646 } 1647 1648 @Override 1649 protected String repr_impl(@GuardSatisfied @UnknownSignedness Prestate this) { 1650 return "Prestate[" + term.repr() + "]"; 1651 } 1652 1653 @Override 1654 protected String name_impl(@GuardSatisfied Prestate this) { 1655 return "orig(" + term.name() + ")"; 1656 } 1657 1658 @Override 1659 protected String esc_name_impl() { 1660 return "\\old(" + term.esc_name() + ")"; 1661 } 1662 1663 @Override 1664 protected String simplify_name_impl(boolean prestate) { 1665 return term.simplify_name(true); 1666 } 1667 1668 @Override 1669 protected String java_name_impl(VarInfo v) { 1670 if (PrintInvariants.dkconfig_replace_prestate) { 1671 return PrintInvariants.addPrestateExpression(term.java_name(v)); 1672 } 1673 return "\\old(" + term.java_name(v) + ")"; 1674 } 1675 1676 @Override 1677 protected String jml_name_impl(VarInfo v) { 1678 return "\\old(" + term.jml_name(v) + ")"; 1679 } 1680 1681 @Override 1682 protected String dbc_name_impl(VarInfo v) { 1683 1684 // See declaration of testCall for explanation of this flag. 1685 if (testCall) { 1686 return "no format when testCall."; 1687 } 1688 1689 String brackets = ""; 1690 assert v != null; 1691 String preType = v.type.base(); 1692 if ((term instanceof Slice) 1693 // Slices are obtained by calling daikon.Quant.slice(...) 1694 // which returns things of type java.lang.Object 1695 && v.type.dimensions() > 0 1696 && v.type.base().equals("java.lang.Object")) { 1697 preType = "java.lang.Object"; 1698 } 1699 for (int i = 0; i < v.type.dimensions(); i++) { 1700 brackets += "[]"; 1701 } 1702 return "$pre(" + preType + brackets + ", " + term.dbc_name(v) + ")"; 1703 } 1704 1705 @Override 1706 protected String identifier_name_impl() { 1707 return "orig_of_" + term.identifier_name() + "___"; 1708 } 1709 1710 @Override 1711 public <T> T accept(Visitor<T> v) { 1712 return v.visitPrestate(this); 1713 } 1714 } 1715 1716 // sansOrig() 1717 // int origpos = s.indexOf("orig("); 1718 // assert origpos != -1; 1719 // int rparenpos = s.lastIndexOf(")"); 1720 // return s.substring(0, origpos) 1721 // + s.substring(origpos+5, rparenpos) 1722 // + s.substring(rparenpos+1); 1723 1724 // int origpos = s.indexOf("\\old("); 1725 // assert origpos != -1; 1726 // int rparenpos = s.lastIndexOf(")"); 1727 // return s.substring(0, origpos) 1728 // + s.substring(origpos+5, rparenpos) 1729 // + s.substring(rparenpos+1); 1730 1731 /** 1732 * Returns a name for a the poststate value of this object; form is like "new(this)" or 1733 * "\new(this)". 1734 * 1735 * @return the name for the poststate value of this object 1736 */ 1737 public VarInfoName applyPoststate(@Interned VarInfoName this) { 1738 return new Poststate(this).intern(); 1739 } 1740 1741 /** 1742 * The poststate value of a term, like "new(term)". Only used within prestate, so like 1743 * "orig(this.myArray[new(index)]". 1744 */ 1745 public static @Interned class Poststate extends VarInfoName { 1746 // We are Serializable, so we specify a version to allow changes to 1747 // method signatures without breaking serialization. If you add or 1748 // remove fields, you should change this number to the current date. 1749 static final long serialVersionUID = 20020130L; 1750 1751 public final VarInfoName term; 1752 1753 public Poststate(VarInfoName term) { 1754 assert term != null; 1755 this.term = term; 1756 } 1757 1758 @Override 1759 protected String repr_impl(@GuardSatisfied @UnknownSignedness Poststate this) { 1760 return "Poststate[" + term.repr() + "]"; 1761 } 1762 1763 @Override 1764 protected String name_impl(@GuardSatisfied Poststate this) { 1765 return "post(" + term.name() + ")"; 1766 } 1767 1768 @Override 1769 protected String esc_name_impl() { 1770 return "\\new(" + term.esc_name() + ")"; 1771 } 1772 1773 @Override 1774 protected String simplify_name_impl(boolean prestate) { 1775 return term.simplify_name(false); 1776 } 1777 1778 @Override 1779 protected String java_name_impl(VarInfo v) { 1780 return "\\post(" + term.java_name(v) + ")"; 1781 } 1782 1783 @Override 1784 protected String jml_name_impl(VarInfo v) { 1785 return "\\new(" + term.jml_name(v) + ")"; 1786 // return "(warning: JML format cannot express a Poststate" 1787 // + " [repr=" + repr() + "])"; 1788 } 1789 1790 @Override 1791 protected String dbc_name_impl(VarInfo v) { 1792 return "(warning: DBC format cannot express a Poststate [repr=" + repr() + "])"; 1793 } 1794 1795 @Override 1796 protected String identifier_name_impl() { 1797 return "post_of_" + term.identifier_name() + "___"; 1798 } 1799 1800 @Override 1801 public <T> T accept(Visitor<T> v) { 1802 return v.visitPoststate(this); 1803 } 1804 } 1805 1806 /** Returns a name for the this term plus a constant, like "this-1" or "this+1". */ 1807 public VarInfoName applyAdd(@Interned VarInfoName this, int amount) { 1808 if (amount == 0) { 1809 return this; 1810 } else { 1811 return new Add(this, amount).intern(); 1812 } 1813 } 1814 1815 /** An integer amount more or less than some other value, like "x+2". */ 1816 public static @Interned class Add extends VarInfoName { 1817 // We are Serializable, so we specify a version to allow changes to 1818 // method signatures without breaking serialization. If you add or 1819 // remove fields, you should change this number to the current date. 1820 static final long serialVersionUID = 20020130L; 1821 1822 public final VarInfoName term; 1823 public final int amount; 1824 1825 public Add(VarInfoName term, int amount) { 1826 assert term != null; 1827 this.term = term; 1828 this.amount = amount; 1829 } 1830 1831 private String amount(@GuardSatisfied Add this) { 1832 return (amount < 0) ? String.valueOf(amount) : "+" + amount; 1833 } 1834 1835 @SuppressWarnings("signedness:method.invocation") 1836 @Override 1837 protected String repr_impl(@GuardSatisfied @UnknownSignedness Add this) { 1838 return "Add{" + amount() + "}[" + term.repr() + "]"; 1839 } 1840 1841 @Override 1842 protected String name_impl(@GuardSatisfied Add this) { 1843 return term.name() + amount(); 1844 } 1845 1846 @Override 1847 protected String esc_name_impl() { 1848 return term.esc_name() + amount(); 1849 } 1850 1851 @Override 1852 protected String simplify_name_impl(boolean prestate) { 1853 return (amount < 0) 1854 ? "(- " + term.simplify_name(prestate) + " " + -amount + ")" 1855 : "(+ " + term.simplify_name(prestate) + " " + amount + ")"; 1856 } 1857 1858 @Override 1859 protected String java_name_impl(VarInfo v) { 1860 return term.java_name(v) + amount(); 1861 } 1862 1863 @Override 1864 protected String jml_name_impl(VarInfo v) { 1865 return term.jml_name(v) + amount(); 1866 } 1867 1868 @Override 1869 protected String dbc_name_impl(VarInfo v) { 1870 return term.dbc_name(v) + amount(); 1871 } 1872 1873 @Override 1874 protected String identifier_name_impl() { 1875 if (amount >= 0) { 1876 return term.identifier_name() + "_plus" + amount; 1877 } else { 1878 return term.identifier_name() + "_minus" + -amount; 1879 } 1880 } 1881 1882 @Override 1883 public <T> T accept(Visitor<T> v) { 1884 return v.visitAdd(this); 1885 } 1886 1887 // override for cleanliness 1888 @Override 1889 public VarInfoName applyAdd(int _amount) { 1890 int amt = _amount + this.amount; 1891 return (amt == 0) ? term : term.applyAdd(amt); 1892 } 1893 } 1894 1895 /** Returns a name for the decrement of this term, like "this-1". */ 1896 public VarInfoName applyDecrement(@Interned VarInfoName this) { 1897 return applyAdd(-1); 1898 } 1899 1900 /** Returns a name for the increment of this term, like "this+1". */ 1901 public VarInfoName applyIncrement(@Interned VarInfoName this) { 1902 return applyAdd(+1); 1903 } 1904 1905 /** 1906 * Returns a name for the elements of a container (as opposed to the identity of the container) 1907 * like "this[]" or "(elements this)". 1908 * 1909 * @return the name for the elements of this container 1910 */ 1911 public VarInfoName applyElements(@Interned VarInfoName this) { 1912 return new Elements(this).intern(); 1913 } 1914 1915 /** The elements of a container, like "term[]". */ 1916 public static @Interned class Elements extends VarInfoName { 1917 // We are Serializable, so we specify a version to allow changes to 1918 // method signatures without breaking serialization. If you add or 1919 // remove fields, you should change this number to the current date. 1920 static final long serialVersionUID = 20020130L; 1921 1922 public final VarInfoName term; 1923 1924 public Elements(VarInfoName term) { 1925 assert term != null; 1926 this.term = term; 1927 } 1928 1929 @Override 1930 protected String repr_impl(@GuardSatisfied @UnknownSignedness Elements this) { 1931 return "Elements[" + term.repr() + "]"; 1932 } 1933 1934 @Override 1935 protected String name_impl(@GuardSatisfied Elements this) { 1936 return name_impl(""); 1937 } 1938 1939 protected String name_impl(@GuardSatisfied Elements this, String index) { 1940 return term.name() + "[" + index + "]"; 1941 } 1942 1943 @Override 1944 protected String esc_name_impl() { 1945 throw new UnsupportedOperationException( 1946 "ESC cannot format an unquantified sequence of elements [repr=" + repr() + "]"); 1947 } 1948 1949 protected String esc_name_impl(String index) { 1950 return term.esc_name() + "[" + index + "]"; 1951 } 1952 1953 @Override 1954 protected String simplify_name_impl(boolean prestate) { 1955 return "(select elems " + term.simplify_name(prestate) + ")"; 1956 } 1957 1958 @Override 1959 protected String java_name_impl(VarInfo v) { 1960 return term.java_name(v); 1961 } 1962 1963 protected String java_name_impl(String index, VarInfo v) { 1964 return java_family_impl(OutputFormat.JAVA, v, index); 1965 } 1966 1967 @Override 1968 protected String jml_name_impl(VarInfo v) { 1969 return term.jml_name(v); 1970 } 1971 1972 protected String jml_name_impl(String index, VarInfo v) { 1973 return java_family_impl(OutputFormat.JML, v, index); 1974 } 1975 1976 @Override 1977 protected String dbc_name_impl(VarInfo v) { 1978 return term.dbc_name(v); 1979 } 1980 1981 protected String dbc_name_impl(String index, VarInfo v) { 1982 return java_family_impl(OutputFormat.DBCJAVA, v, index); 1983 } 1984 1985 protected String java_family_impl(OutputFormat format, VarInfo v, String index) { 1986 1987 // If the collection goes through daikon.Quant.collect___, then 1988 // it will be returned as an array no matter what. 1989 String formatted = term.name_using(format, v); 1990 String collectType = (v.type.baseIsPrimitive() ? v.type.base() : "Object"); 1991 return "daikon.Quant.getElement_" + collectType + "(" + formatted + ", " + index + ")"; 1992 // // XXX temporary fix: sometimes long is passed as index. 1993 // // I can't find where the VarInfo for "index" is found. Wherever that is, 1994 // // we should check if its type is long, and do the casting only for that 1995 // // case. 1996 // if (formatted.startsWith("daikon.Quant.collect")) { 1997 // return formatted + "[(int)" + index + "]"; 1998 // } else { 1999 // if (v.type.pseudoDimensions() > v.type.dimensions()) { 2000 // // it's a collection 2001 // return formatted + ".get((int)" + index + ")"; 2002 // } else { 2003 // // it's an array 2004 // return formatted + "[(int)" + index + "]"; 2005 // } 2006 // } 2007 } 2008 2009 protected String identifier_name_impl(String index) { 2010 if (index.equals("")) { 2011 return term.identifier_name() + "_elems"; 2012 } else { 2013 return term.identifier_name() + "_in_" + index + "_dex_"; 2014 } 2015 } 2016 2017 @Override 2018 protected String identifier_name_impl() { 2019 return identifier_name_impl(""); 2020 } 2021 2022 @Override 2023 public <T> T accept(Visitor<T> v) { 2024 return v.visitElements(this); 2025 } 2026 2027 public VarInfoName getLowerBound() { 2028 return ZERO; 2029 } 2030 2031 public VarInfoName getUpperBound() { 2032 return applySize().applyDecrement(); 2033 } 2034 2035 public VarInfoName getSubscript(VarInfoName index) { 2036 return applySubscript(index); 2037 } 2038 } 2039 2040 /** 2041 * Caller is subscripting an orig(a[]) array. Take the requested index and make it useful in that 2042 * context. 2043 */ 2044 static VarInfoName indexToPrestate(VarInfoName index) { 2045 // 1 orig(a[]) . orig(index) -> orig(a[index]) 2046 // 2 orig(a[]) . index -> orig(a[post(index)]) 2047 if (index instanceof Prestate) { 2048 index = ((Prestate) index).term; // #1 2049 } else if (index instanceof Add) { 2050 Add add = (Add) index; 2051 if (add.term instanceof Prestate) { 2052 index = ((Prestate) add.term).term.applyAdd(add.amount); // #1 2053 } else { 2054 index = index.applyPoststate(); // #2 2055 } 2056 } else if (index.isLiteralConstant()) { 2057 // we don't want orig(a[post(0)]), so leave index alone 2058 } else { 2059 index = index.applyPoststate(); // #2 2060 } 2061 return index; 2062 } 2063 2064 /** Returns a name for an element selected from a sequence, like "this[i]". */ 2065 public VarInfoName applySubscript(@Interned VarInfoName this, VarInfoName index) { 2066 assert index != null; 2067 ElementsFinder finder = new ElementsFinder(this); 2068 Elements elems = finder.elems(); 2069 assert elems != null : "applySubscript should have elements to use in " + this; 2070 if (finder.inPre()) { 2071 index = indexToPrestate(index); 2072 } 2073 Replacer r = new Replacer(elems, new Subscript(elems, index).intern()); 2074 return r.replace(this).intern(); 2075 } 2076 2077 // Given a sequence and subscript index, convert the index to an 2078 // explicit form if necessary (e.g. a[-1] becomes a[a.length-1]). 2079 // Result is not interned, because it is only ever used for printing. 2080 static VarInfoName indexExplicit(Elements sequence, VarInfoName index) { 2081 if (!index.isLiteralConstant()) { 2082 return index; 2083 } 2084 2085 int i = Integer.parseInt(index.name()); 2086 if (i >= 0) { 2087 return index; 2088 } 2089 2090 return sequence.applySize().applyAdd(i); 2091 } 2092 2093 /** An element from a sequence, like "sequence[index]". */ 2094 public static @Interned class Subscript extends VarInfoName { 2095 // We are Serializable, so we specify a version to allow changes to 2096 // method signatures without breaking serialization. If you add or 2097 // remove fields, you should change this number to the current date. 2098 static final long serialVersionUID = 20020130L; 2099 2100 public final Elements sequence; 2101 public final VarInfoName index; 2102 2103 public Subscript(Elements sequence, VarInfoName index) { 2104 assert sequence != null; 2105 assert index != null; 2106 this.sequence = sequence; 2107 this.index = index; 2108 } 2109 2110 @Override 2111 protected String repr_impl(@GuardSatisfied @UnknownSignedness Subscript this) { 2112 return "Subscript{" + index.repr() + "}[" + sequence.repr() + "]"; 2113 } 2114 2115 @Override 2116 protected String name_impl(@GuardSatisfied Subscript this) { 2117 return sequence.name_impl(index.name()); 2118 } 2119 2120 @Override 2121 protected String esc_name_impl() { 2122 return sequence.esc_name_impl(indexExplicit(sequence, index).esc_name()); 2123 } 2124 2125 @Override 2126 protected String simplify_name_impl(boolean prestate) { 2127 return "(select " 2128 + sequence.simplify_name(prestate) 2129 + " " 2130 + indexExplicit(sequence, index).simplify_name(prestate) 2131 + ")"; 2132 } 2133 2134 @Override 2135 protected String java_name_impl(VarInfo v) { 2136 return java_family_impl(OutputFormat.JAVA, v); 2137 } 2138 2139 @Override 2140 protected String jml_name_impl(VarInfo v) { 2141 return java_family_impl(OutputFormat.JML, v); 2142 } 2143 2144 @Override 2145 protected String dbc_name_impl(VarInfo v) { 2146 return java_family_impl(OutputFormat.DBCJAVA, v); 2147 } 2148 2149 protected String java_family_impl(OutputFormat format, VarInfo v) { 2150 2151 // See declaration of testCall for explanation of this flag. 2152 if (testCall) { 2153 return "no format when testCall."; 2154 } 2155 2156 assert v != null; 2157 assert v.isDerived(); 2158 Derivation derived = v.derived; 2159 assert derived instanceof SequenceScalarSubscript 2160 || derived instanceof SequenceStringSubscript 2161 || derived instanceof SequenceFloatSubscript; 2162 VarInfo indexVarInfo = ((BinaryDerivation) derived).base2; 2163 VarInfo seqVarInfo = ((BinaryDerivation) derived).base1; 2164 if (format == OutputFormat.JAVA) { 2165 return sequence.java_name_impl(index.java_name_impl(indexVarInfo), seqVarInfo); 2166 } else if (format == OutputFormat.JML) { 2167 return sequence.jml_name_impl(index.jml_name_impl(indexVarInfo), seqVarInfo); 2168 } else { // format == OutputFormat.DBCJAVA 2169 return sequence.dbc_name_impl(index.dbc_name_impl(indexVarInfo), seqVarInfo); 2170 } 2171 } 2172 2173 @Override 2174 protected String identifier_name_impl() { 2175 return sequence.identifier_name_impl(index.identifier_name()); 2176 } 2177 2178 @Override 2179 public <T> T accept(Visitor<T> v) { 2180 return v.visitSubscript(this); 2181 } 2182 } 2183 2184 /** 2185 * Returns a name for a slice of element selected from a sequence, like "this[i..j]". If an 2186 * endpoint is null, it means "from the start" or "to the end". 2187 */ 2188 public VarInfoName applySlice( 2189 @Interned VarInfoName this, @Nullable VarInfoName i, @Nullable VarInfoName j) { 2190 // a[] -> a[index..] 2191 // orig(a[]) -> orig(a[post(index)..]) 2192 ElementsFinder finder = new ElementsFinder(this); 2193 Elements elems = finder.elems(); 2194 assert elems != null; 2195 if (finder.inPre()) { 2196 if (i != null) { 2197 i = indexToPrestate(i); 2198 } 2199 if (j != null) { 2200 j = indexToPrestate(j); 2201 } 2202 } 2203 Replacer r = new Replacer(finder.elems(), new Slice(elems, i, j).intern()); 2204 return r.replace(this).intern(); 2205 } 2206 2207 /** A slice of elements from a sequence, like "sequence[i..j]". */ 2208 public static @Interned class Slice extends VarInfoName { 2209 // We are Serializable, so we specify a version to allow changes to 2210 // method signatures without breaking serialization. If you add or 2211 // remove fields, you should change this number to the current date. 2212 static final long serialVersionUID = 20020130L; 2213 2214 public final Elements sequence; 2215 public final VarInfoName i, j; 2216 2217 public Slice(Elements sequence, VarInfoName i, VarInfoName j) { 2218 assert sequence != null; 2219 assert (i != null) || (j != null); 2220 this.sequence = sequence; 2221 this.i = i; 2222 this.j = j; 2223 } 2224 2225 @Override 2226 protected String repr_impl(@GuardSatisfied @UnknownSignedness Slice this) { 2227 return "Slice{" 2228 + ((i == null) ? "" : i.repr()) 2229 + "," 2230 + ((j == null) ? "" : j.repr()) 2231 + "}[" 2232 + sequence.repr() 2233 + "]"; 2234 } 2235 2236 @Override 2237 protected String name_impl(@GuardSatisfied Slice this) { 2238 return sequence.name_impl( 2239 "" + ((i == null) ? "0" : i.name()) + ".." + ((j == null) ? "" : j.name())); 2240 } 2241 2242 @Override 2243 protected String esc_name_impl() { 2244 // return the default implementation for now. 2245 // return name_impl(); 2246 throw new UnsupportedOperationException( 2247 "ESC cannot format an unquantified slice of elements"); 2248 } 2249 2250 @Override 2251 protected String simplify_name_impl(boolean prestate) { 2252 System.out.println(" seq: " + sequence + " " + i + " " + j); 2253 throw new UnsupportedOperationException( 2254 "Simplify cannot format an unquantified slice of elements"); 2255 } 2256 2257 @Override 2258 protected String java_name_impl(VarInfo v) { 2259 return slice_helper(OutputFormat.JAVA, v); 2260 } 2261 2262 @Override 2263 protected String jml_name_impl(VarInfo v) { 2264 return slice_helper(OutputFormat.JML, v); 2265 } 2266 2267 @Override 2268 protected String dbc_name_impl(VarInfo v) { 2269 return slice_helper(OutputFormat.DBCJAVA, v); 2270 } 2271 2272 // Helper for JML, Java and DBC formats 2273 protected String slice_helper(OutputFormat format, VarInfo v) { 2274 2275 // See declaration of testCall for explanation of this flag. 2276 if (testCall) { 2277 return "no format when testCall."; 2278 } 2279 2280 assert v != null; 2281 assert v.isDerived(); 2282 Derivation derived = v.derived; 2283 assert derived instanceof SequenceSubsequence 2284 || derived instanceof SequenceScalarArbitrarySubsequence 2285 || derived instanceof SequenceFloatArbitrarySubsequence 2286 || derived instanceof SequenceStringArbitrarySubsequence; 2287 if (derived instanceof SequenceSubsequence) { 2288 assert i == null || j == null; 2289 if (i == null) { // sequence[0..j] 2290 assert j != null; 2291 return "daikon.Quant.slice(" 2292 + sequence.name_using(format, ((SequenceSubsequence) derived).seqvar()) 2293 + ", 0, " 2294 + j.name_using(format, ((SequenceSubsequence) derived).sclvar()) 2295 + ")"; 2296 } else { 2297 VarInfo seqVarInfo = ((SequenceSubsequence) derived).seqvar(); 2298 String prefix = sequence.name_using(format, seqVarInfo); 2299 String lastIdxString = "daikon.Quant.size(" + prefix + ")"; 2300 // if (seqVarInfo.type.pseudoDimensions() > seqVarInfo.type.dimensions()) { 2301 // if (prefix.startsWith("daikon.Quant.collect")) { 2302 // // Quant collect methods returns an array 2303 // lastIdxString = prefix + ".length-1"; 2304 // } else { 2305 // // it's a collection 2306 // lastIdxString = prefix + ".size()-1"; 2307 // } 2308 // } else { 2309 // // it's an array 2310 // lastIdxString = prefix + ".length-1"; 2311 // } 2312 return "daikon.Quant.slice(" 2313 + sequence.name_using(format, ((SequenceSubsequence) derived).seqvar()) 2314 + ", " 2315 + i.name_using(format, ((SequenceSubsequence) derived).sclvar()) 2316 + ", " 2317 + lastIdxString 2318 + ")"; 2319 } 2320 } else { 2321 assert i != null && j != null; 2322 if (derived instanceof SequenceScalarArbitrarySubsequence) { 2323 SequenceScalarArbitrarySubsequence derived2 = 2324 (SequenceScalarArbitrarySubsequence) derived; 2325 return "daikon.Quant.slice(" 2326 + sequence.name_using(format, derived2.seqvar()) 2327 + ", " 2328 + i.name_using(format, derived2.startvar()) 2329 + ", " 2330 + j.name_using(format, derived2.endvar()) 2331 + ")"; 2332 } else if (derived instanceof SequenceFloatArbitrarySubsequence) { 2333 SequenceFloatArbitrarySubsequence derived2 = (SequenceFloatArbitrarySubsequence) derived; 2334 return "daikon.Quant.slice(" 2335 + sequence.name_using(format, derived2.seqvar()) 2336 + ", " 2337 + i.name_using(format, derived2.startvar()) 2338 + ", " 2339 + j.name_using(format, derived2.endvar()) 2340 + ")"; 2341 } else { 2342 SequenceStringArbitrarySubsequence derived2 = 2343 (SequenceStringArbitrarySubsequence) derived; 2344 return "daikon.Quant.slice(" 2345 + sequence.name_using(format, derived2.seqvar()) 2346 + ", " 2347 + i.name_using(format, derived2.startvar()) 2348 + ", " 2349 + j.name_using(format, derived2.endvar()) 2350 + ")"; 2351 } 2352 } 2353 } 2354 2355 @Override 2356 protected String identifier_name_impl() { 2357 String start = (i == null) ? "0" : i.identifier_name(); 2358 String end = (j == null) ? "" : j.identifier_name(); 2359 return sequence.identifier_name_impl(start + "_to_" + end); 2360 } 2361 2362 @Override 2363 public <T> T accept(Visitor<T> v) { 2364 return v.visitSlice(this); 2365 } 2366 2367 public VarInfoName getLowerBound() { 2368 return (i != null) ? i : ZERO; 2369 } 2370 2371 public VarInfoName getUpperBound() { 2372 return (j != null) ? j : sequence.getUpperBound(); 2373 } 2374 2375 public VarInfoName getSubscript(VarInfoName index) { 2376 return sequence.getSubscript(index); 2377 } 2378 } 2379 2380 /** Accept the actions of a visitor. */ 2381 public abstract <T> T accept(Visitor<T> v); 2382 2383 /** Visitor framework for processing of VarInfoNames. */ 2384 public static interface Visitor<T> { 2385 public T visitSimple(Simple o); 2386 2387 public T visitSizeOf(SizeOf o); 2388 2389 public T visitFunctionOf(FunctionOf o); 2390 2391 public T visitFunctionOfN(FunctionOfN o); 2392 2393 public T visitField(Field o); 2394 2395 public T visitTypeOf(TypeOf o); 2396 2397 public T visitPrestate(Prestate o); 2398 2399 public T visitPoststate(Poststate o); 2400 2401 public T visitAdd(Add o); 2402 2403 public T visitElements(Elements o); 2404 2405 public T visitSubscript(Subscript o); 2406 2407 public T visitSlice(Slice o); 2408 } 2409 2410 /** 2411 * Traverse the tree elements that have exactly one branch (so the traversal order doesn't 2412 * matter). Visitors need to implement methods for traversing elements (e.g. FunctionOfN) with 2413 * more than one branch. 2414 */ 2415 public abstract static class AbstractVisitor<T> implements Visitor<T> { 2416 @Override 2417 public T visitSimple(Simple o) { 2418 // nothing to do; leaf node 2419 return null; 2420 } 2421 2422 @Override 2423 public T visitSizeOf(SizeOf o) { 2424 return o.sequence.accept(this); 2425 } 2426 2427 @Override 2428 public T visitFunctionOf(FunctionOf o) { 2429 return o.argument.accept(this); 2430 } 2431 2432 /** By default, return effect on first argument, but traverse all, backwards. */ 2433 @Override 2434 public T visitFunctionOfN(FunctionOfN o) { 2435 T retval = null; 2436 for (ListIterator<VarInfoName> i = o.args.listIterator(o.args.size()); i.hasPrevious(); ) { 2437 VarInfoName vin = i.previous(); 2438 retval = vin.accept(this); 2439 } 2440 return retval; 2441 } 2442 2443 @Override 2444 public T visitField(Field o) { 2445 return o.term.accept(this); 2446 } 2447 2448 @Override 2449 public T visitTypeOf(TypeOf o) { 2450 return o.term.accept(this); 2451 } 2452 2453 @Override 2454 public T visitPrestate(Prestate o) { 2455 return o.term.accept(this); 2456 } 2457 2458 @Override 2459 public T visitPoststate(Poststate o) { 2460 return o.term.accept(this); 2461 } 2462 2463 @Override 2464 public T visitAdd(Add o) { 2465 return o.term.accept(this); 2466 } 2467 2468 @Override 2469 public T visitElements(Elements o) { 2470 return o.term.accept(this); 2471 } 2472 2473 // leave abstract; traversal order and return values matter 2474 @Override 2475 public abstract T visitSubscript(Subscript o); 2476 2477 // leave abstract; traversal order and return values matter 2478 @Override 2479 public abstract T visitSlice(Slice o); 2480 } 2481 2482 /** 2483 * Use to report whether a node is in a pre- or post-state context. Throws an assertion error if a 2484 * given goal isn't present. 2485 */ 2486 public static class NodeFinder extends AbstractVisitor<VarInfoName> { 2487 /** 2488 * Creates a new NodeFinder. 2489 * 2490 * @param root the root of the tree to search 2491 * @param goal the goal to find 2492 */ 2493 public NodeFinder(VarInfoName root, VarInfoName goal) { 2494 this.goal = goal; 2495 assert root.accept(this) != null; 2496 } 2497 2498 // state and accessors 2499 private final VarInfoName goal; 2500 private boolean pre; 2501 2502 public boolean inPre() { 2503 return pre; 2504 } 2505 2506 // visitor methods that get the job done 2507 @Override 2508 public VarInfoName visitSimple(Simple o) { 2509 return (o == goal) ? goal : null; 2510 } 2511 2512 @Override 2513 public VarInfoName visitSizeOf(SizeOf o) { 2514 return (o == goal) ? goal : super.visitSizeOf(o); 2515 } 2516 2517 @Override 2518 public VarInfoName visitFunctionOf(FunctionOf o) { 2519 return (o == goal) ? goal : super.visitFunctionOf(o); 2520 } 2521 2522 @Override 2523 public VarInfoName visitFunctionOfN(FunctionOfN o) { 2524 VarInfoName retval = null; 2525 for (VarInfoName vin : o.args) { 2526 retval = vin.accept(this); 2527 if (retval != null) { 2528 return retval; 2529 } 2530 } 2531 return retval; 2532 } 2533 2534 @Override 2535 public VarInfoName visitField(Field o) { 2536 return (o == goal) ? goal : super.visitField(o); 2537 } 2538 2539 @Override 2540 public VarInfoName visitTypeOf(TypeOf o) { 2541 return (o == goal) ? goal : super.visitTypeOf(o); 2542 } 2543 2544 @Override 2545 public VarInfoName visitPrestate(Prestate o) { 2546 pre = true; 2547 return super.visitPrestate(o); 2548 } 2549 2550 @Override 2551 public VarInfoName visitPoststate(Poststate o) { 2552 pre = false; 2553 return super.visitPoststate(o); 2554 } 2555 2556 @Override 2557 public VarInfoName visitAdd(Add o) { 2558 return (o == goal) ? goal : super.visitAdd(o); 2559 } 2560 2561 @Override 2562 public VarInfoName visitElements(Elements o) { 2563 return (o == goal) ? goal : super.visitElements(o); 2564 } 2565 2566 @Override 2567 public VarInfoName visitSubscript(Subscript o) { 2568 if (o == goal) { 2569 return goal; 2570 } 2571 if (o.sequence.accept(this) != null) { 2572 return goal; 2573 } 2574 if (o.index.accept(this) != null) { 2575 return goal; 2576 } 2577 return null; 2578 } 2579 2580 @Override 2581 public VarInfoName visitSlice(Slice o) { 2582 if (o == goal) { 2583 return goal; 2584 } 2585 if (o.sequence.accept(this) != null) { 2586 return goal; 2587 } 2588 if ((o.i != null) && (o.i.accept(this) != null)) { 2589 return goal; 2590 } 2591 if ((o.j != null) && (o.j.accept(this) != null)) { 2592 return goal; 2593 } 2594 return null; 2595 } 2596 } 2597 2598 /** 2599 * Finds if a given VarInfoName is contained in a set of nodes in the VarInfoName tree using == 2600 * comparison. Recurse through everything except fields, so in x.a, we don't look at a. 2601 */ 2602 public static class Finder extends AbstractVisitor<VarInfoName> { 2603 // state and accessors 2604 private final Set<VarInfoName> goals; 2605 2606 /** 2607 * Creates a new Finder. Uses equals() to find. 2608 * 2609 * @param argGoals the goals to find 2610 */ 2611 public Finder(Set<VarInfoName> argGoals) { 2612 goals = new HashSet<VarInfoName>(); 2613 for (VarInfoName name : argGoals) { 2614 this.goals.add(name.intern()); 2615 } 2616 } 2617 2618 /** Returns true iff some part of root is contained in this.goals. */ 2619 @EnsuresNonNullIf(result = true, expression = "getPart(#1") 2620 public boolean contains(VarInfoName root) { 2621 VarInfoName o = getPart(root); 2622 return (o != null); 2623 } 2624 2625 /** Returns the part of root that is contained in this.goals, or null if not found. */ 2626 public @Nullable VarInfoName getPart(VarInfoName root) { 2627 VarInfoName o = root.intern().accept(this); 2628 return o; 2629 } 2630 2631 // visitor methods that get the job done 2632 @Override 2633 public VarInfoName visitSimple(Simple o) { 2634 return goals.contains(o) ? o : null; 2635 } 2636 2637 @Override 2638 public VarInfoName visitSizeOf(SizeOf o) { 2639 return goals.contains(o) ? o : o.sequence.intern().accept(this); 2640 } 2641 2642 @Override 2643 public VarInfoName visitFunctionOf(FunctionOf o) { 2644 return goals.contains(o) ? o : super.visitFunctionOf(o); 2645 } 2646 2647 @Override 2648 public VarInfoName visitFunctionOfN(FunctionOfN o) { 2649 VarInfoName result = null; 2650 if (goals.contains(o)) { 2651 return o; 2652 } 2653 for (VarInfoName vin : o.args) { 2654 result = vin.accept(this); 2655 if (result != null) { 2656 return result; 2657 } 2658 } 2659 return result; 2660 } 2661 2662 @Override 2663 public VarInfoName visitField(Field o) { 2664 return goals.contains(o) ? o : super.visitField(o); 2665 } 2666 2667 @Override 2668 public VarInfoName visitTypeOf(TypeOf o) { 2669 return goals.contains(o) ? o : super.visitTypeOf(o); 2670 } 2671 2672 @Override 2673 public VarInfoName visitPrestate(Prestate o) { 2674 if (goals.contains(o)) { 2675 return o; 2676 } 2677 return super.visitPrestate(o); 2678 } 2679 2680 @Override 2681 public VarInfoName visitPoststate(Poststate o) { 2682 if (goals.contains(o)) { 2683 return o; 2684 } 2685 return super.visitPoststate(o); 2686 } 2687 2688 @Override 2689 public VarInfoName visitAdd(Add o) { 2690 return goals.contains(o) ? o : super.visitAdd(o); 2691 } 2692 2693 @Override 2694 public VarInfoName visitElements(Elements o) { 2695 return goals.contains(o) ? o : super.visitElements(o); 2696 } 2697 2698 @Override 2699 public VarInfoName visitSubscript(Subscript o) { 2700 if (goals.contains(o)) { 2701 return o; 2702 } 2703 VarInfoName temp = o.sequence.accept(this); 2704 if (temp != null) { 2705 return temp; 2706 } 2707 temp = o.index.accept(this); 2708 if (temp != null) { 2709 return temp; 2710 } 2711 return null; 2712 } 2713 2714 @Override 2715 public VarInfoName visitSlice(Slice o) { 2716 if (goals.contains(o)) { 2717 return o; 2718 } 2719 VarInfoName temp = o.sequence.accept(this); 2720 if (temp != null) { 2721 return temp; 2722 } 2723 if (o.i != null) { 2724 temp = o.i.accept(this); 2725 if (temp != null) { 2726 return temp; 2727 } 2728 } 2729 if (o.j != null) { 2730 temp = o.j.accept(this); 2731 if (temp != null) { 2732 return temp; 2733 } 2734 } 2735 return null; 2736 } 2737 } 2738 2739 // An abstract base class for visitors that compute some predicate 2740 // of a conjunctive nature (true only if true on all subparts), 2741 // returning Boolean.FALSE or Boolean.TRUE. 2742 public abstract static class BooleanAndVisitor extends AbstractVisitor<Boolean> { 2743 private boolean result; 2744 2745 protected BooleanAndVisitor(VarInfoName name) { 2746 result = (name.accept(this) != null); 2747 } 2748 2749 public boolean result() { 2750 return result; 2751 } 2752 2753 @Override 2754 public Boolean visitFunctionOfN(FunctionOfN o) { 2755 Boolean retval = null; 2756 for (ListIterator<VarInfoName> i = o.args.listIterator(o.args.size()); i.hasPrevious(); ) { 2757 VarInfoName vin = i.previous(); 2758 retval = vin.accept(this); 2759 if (retval != null) { 2760 return null; 2761 } 2762 } 2763 return retval; 2764 } 2765 2766 @Override 2767 public Boolean visitSubscript(Subscript o) { 2768 Boolean temp = o.sequence.accept(this); 2769 if (temp == null) { 2770 return temp; 2771 } 2772 temp = o.index.accept(this); 2773 return temp; 2774 } 2775 2776 @Override 2777 public Boolean visitSlice(Slice o) { 2778 Boolean temp = o.sequence.accept(this); 2779 if (temp == null) { 2780 return temp; 2781 } 2782 if (o.i != null) { 2783 temp = o.i.accept(this); 2784 if (temp == null) { 2785 return temp; 2786 } 2787 } 2788 if (o.j != null) { 2789 temp = o.j.accept(this); 2790 if (temp == null) { 2791 return temp; 2792 } 2793 } 2794 return temp; 2795 } 2796 } 2797 2798 public static class IsAllPrestateVisitor extends BooleanAndVisitor { 2799 2800 public IsAllPrestateVisitor(VarInfoName vin) { 2801 super(vin); 2802 } 2803 2804 @Override 2805 public Boolean visitSimple(Simple o) { 2806 // Any var not inside an orig() isn't prestate 2807 return null; 2808 } 2809 2810 @Override 2811 public Boolean visitPrestate(Prestate o) { 2812 // orig(...) is all prestate unless it contains post(...) 2813 return new IsAllNonPoststateVisitor(o).result() ? Boolean.TRUE : null; 2814 } 2815 } 2816 2817 public static class IsAllNonPoststateVisitor extends BooleanAndVisitor { 2818 public IsAllNonPoststateVisitor(VarInfoName vin) { 2819 super(vin); 2820 } 2821 2822 @Override 2823 public Boolean visitSimple(Simple o) { 2824 // Any var not inside a post() isn't poststate 2825 return Boolean.TRUE; 2826 } 2827 2828 @Override 2829 public Boolean visitPoststate(Poststate o) { 2830 // If we see a post(...), we aren't all poststate. 2831 return null; 2832 } 2833 } 2834 2835 /** 2836 * Use to traverse a tree, find the first (elements ...) node, and report whether it's in pre or 2837 * post-state. 2838 */ 2839 public static class ElementsFinder extends AbstractVisitor<Elements> { 2840 public ElementsFinder(VarInfoName name) { 2841 elems = name.accept(this); 2842 } 2843 2844 // state and accessors 2845 private boolean pre = false; 2846 private Elements elems = null; 2847 2848 public boolean inPre() { 2849 return pre; 2850 } 2851 2852 public Elements elems() { 2853 return elems; 2854 } 2855 2856 // visitor methods that get the job done 2857 @Override 2858 public Elements visitFunctionOfN(FunctionOfN o) { 2859 Elements retval = null; 2860 for (VarInfoName vin : o.args) { 2861 retval = vin.accept(this); 2862 if (retval != null) { 2863 return retval; 2864 } 2865 } 2866 return retval; 2867 } 2868 2869 @Override 2870 public Elements visitPrestate(Prestate o) { 2871 pre = true; 2872 return super.visitPrestate(o); 2873 } 2874 2875 @Override 2876 public Elements visitPoststate(Poststate o) { 2877 pre = false; 2878 return super.visitPoststate(o); 2879 } 2880 2881 @Override 2882 public Elements visitElements(Elements o) { 2883 return o; 2884 } 2885 2886 @Override 2887 public Elements visitSubscript(Subscript o) { 2888 // skip the subscripted sequence 2889 Elements tmp = o.sequence.term.accept(this); 2890 if (tmp == null) { 2891 tmp = o.index.accept(this); 2892 } 2893 return tmp; 2894 } 2895 2896 @Override 2897 public Elements visitSlice(Slice o) { 2898 // skip the sliced sequence 2899 Elements tmp = o.sequence.term.accept(this); 2900 if (tmp == null && o.i != null) { 2901 tmp = o.i.accept(this); 2902 } 2903 if (tmp == null && o.j != null) { 2904 tmp = o.j.accept(this); 2905 } 2906 return tmp; 2907 } 2908 } 2909 2910 /** 2911 * A Replacer is a Visitor that makes a copy of a tree, but replaces some node (and its children) 2912 * with another. The result is *not* interned; the client must do that if desired. 2913 */ 2914 public static class Replacer extends AbstractVisitor<VarInfoName> { 2915 private final VarInfoName old; 2916 private final VarInfoName _new; 2917 2918 public Replacer(VarInfoName old, VarInfoName _new) { 2919 this.old = old; 2920 this._new = _new; 2921 } 2922 2923 public VarInfoName replace(VarInfoName root) { 2924 return root.accept(this); 2925 } 2926 2927 @Override 2928 public VarInfoName visitSimple(Simple o) { 2929 return (o == old) ? _new : o; 2930 } 2931 2932 @Override 2933 public VarInfoName visitSizeOf(SizeOf o) { 2934 return (o == old) ? _new : super.visitSizeOf(o).applySize(); 2935 } 2936 2937 @Override 2938 public VarInfoName visitFunctionOf(FunctionOf o) { 2939 return (o == old) ? _new : super.visitFunctionOf(o).applyFunction(o.function); 2940 } 2941 2942 @Override 2943 public VarInfoName visitFunctionOfN(FunctionOfN o) { 2944 // If o is getting replaced, then just replace it 2945 // otherwise, create a new function and check if arguments get replaced 2946 if (o == old) { 2947 return _new; 2948 } 2949 ArrayList<VarInfoName> newArgs = new ArrayList<>(); 2950 for (VarInfoName vin : o.args) { 2951 VarInfoName retval = vin.accept(this); 2952 newArgs.add(retval); 2953 } 2954 return VarInfoName.applyFunctionOfN(o.function, newArgs); 2955 } 2956 2957 @Override 2958 public VarInfoName visitField(Field o) { 2959 return (o == old) ? _new : super.visitField(o).applyField(o.field); 2960 } 2961 2962 @Override 2963 public VarInfoName visitTypeOf(TypeOf o) { 2964 return (o == old) ? _new : super.visitTypeOf(o).applyTypeOf(); 2965 } 2966 2967 @Override 2968 public VarInfoName visitPrestate(Prestate o) { 2969 return (o == old) ? _new : super.visitPrestate(o).applyPrestate(); 2970 } 2971 2972 @Override 2973 public VarInfoName visitPoststate(Poststate o) { 2974 return (o == old) ? _new : super.visitPoststate(o).applyPoststate(); 2975 } 2976 2977 @Override 2978 public VarInfoName visitAdd(Add o) { 2979 return (o == old) ? _new : super.visitAdd(o).applyAdd(o.amount); 2980 } 2981 2982 @Override 2983 public VarInfoName visitElements(Elements o) { 2984 return (o == old) ? _new : super.visitElements(o).applyElements(); 2985 } 2986 2987 @Override 2988 public VarInfoName visitSubscript(Subscript o) { 2989 return (o == old) ? _new : o.sequence.accept(this).applySubscript(o.index.accept(this)); 2990 } 2991 2992 @Override 2993 public VarInfoName visitSlice(Slice o) { 2994 return (o == old) 2995 ? _new 2996 : o.sequence 2997 .accept(this) 2998 .applySlice( 2999 (o.i == null) ? null : o.i.accept(this), (o.j == null) ? null : o.j.accept(this)); 3000 } 3001 } 3002 3003 /** 3004 * Replace pre states by normal variables, and normal variables by post states. We should do this 3005 * for all variables except for variables derived from return. This piggybacks on replacer but the 3006 * actual replacement is done elsewhere. 3007 */ 3008 public static class PostPreConverter extends Replacer { 3009 3010 public PostPreConverter() { 3011 super(null, null); 3012 } 3013 3014 @Override 3015 public VarInfoName visitSimple(Simple o) { 3016 if (o.name.equals("return")) { 3017 return o; 3018 } 3019 return o.applyPoststate(); 3020 } 3021 3022 @Override 3023 public VarInfoName visitPrestate(Prestate o) { 3024 return o.term; 3025 } 3026 } 3027 3028 public static class NoReturnValue {} 3029 3030 /** 3031 * Use to collect all elements in a tree into an inorder-traversal list. Result includes the root 3032 * element. All methods return null; to obtain the result, call nodes(). 3033 */ 3034 public static class InorderFlattener extends AbstractVisitor<NoReturnValue> { 3035 public InorderFlattener(VarInfoName root) { 3036 root.accept(this); 3037 } 3038 3039 // state and accessors 3040 private final List<VarInfoName> result = new ArrayList<>(); 3041 3042 /** Method returning the actual results (the nodes in order). */ 3043 public List<VarInfoName> nodes() { 3044 return Collections.unmodifiableList(result); 3045 } 3046 3047 // visitor methods that get the job done 3048 @Override 3049 public NoReturnValue visitSimple(Simple o) { 3050 result.add(o); 3051 return super.visitSimple(o); 3052 } 3053 3054 @Override 3055 public NoReturnValue visitSizeOf(SizeOf o) { 3056 result.add(o); 3057 return super.visitSizeOf(o); 3058 } 3059 3060 @Override 3061 public NoReturnValue visitFunctionOf(FunctionOf o) { 3062 result.add(o); 3063 return super.visitFunctionOf(o); 3064 } 3065 3066 @Override 3067 public NoReturnValue visitFunctionOfN(FunctionOfN o) { 3068 result.add(o); 3069 for (VarInfoName vin : o.args) { 3070 vin.accept(this); 3071 } 3072 return null; 3073 } 3074 3075 @Override 3076 public NoReturnValue visitField(Field o) { 3077 result.add(o); 3078 return super.visitField(o); 3079 } 3080 3081 @Override 3082 public NoReturnValue visitTypeOf(TypeOf o) { 3083 result.add(o); 3084 return super.visitTypeOf(o); 3085 } 3086 3087 @Override 3088 public NoReturnValue visitPrestate(Prestate o) { 3089 result.add(o); 3090 return super.visitPrestate(o); 3091 } 3092 3093 @Override 3094 public NoReturnValue visitPoststate(Poststate o) { 3095 result.add(o); 3096 return super.visitPoststate(o); 3097 } 3098 3099 @Override 3100 public NoReturnValue visitAdd(Add o) { 3101 result.add(o); 3102 return super.visitAdd(o); 3103 } 3104 3105 @Override 3106 public NoReturnValue visitElements(Elements o) { 3107 result.add(o); 3108 return super.visitElements(o); 3109 } 3110 3111 @Override 3112 public NoReturnValue visitSubscript(Subscript o) { 3113 result.add(o); 3114 o.sequence.accept(this); 3115 o.index.accept(this); 3116 return null; 3117 } 3118 3119 @Override 3120 public NoReturnValue visitSlice(Slice o) { 3121 result.add(o); 3122 o.sequence.accept(this); 3123 if (o.i != null) o.i.accept(this); 3124 if (o.j != null) o.j.accept(this); 3125 return null; 3126 } 3127 } 3128 3129 // ============================================================ 3130 // Quantification for formatting in ESC or Simplify 3131 3132 public static class SimpleNamesVisitor extends AbstractVisitor<NoReturnValue> { 3133 public SimpleNamesVisitor(VarInfoName root) { 3134 assert root != null; 3135 simples = new HashSet<String>(); 3136 root.accept(this); 3137 } 3138 3139 /** 3140 * See {@link #simples()}. 3141 * 3142 * @see #simples() 3143 */ 3144 private Set<String> simples; 3145 3146 /** 3147 * Returns collection of simple identifiers used in this expression, as Strings. (Used, for 3148 * instance, to check for conflict with a quantifier variable name.) 3149 * 3150 * @return collection of simple identifiers used in this expression, as Strings 3151 */ 3152 public Set<String> simples() { 3153 return Collections.unmodifiableSet(simples); 3154 } 3155 3156 // visitor methods that get the job done 3157 @Override 3158 public NoReturnValue visitSimple(Simple o) { 3159 simples.add(o.name); 3160 return super.visitSimple(o); 3161 } 3162 3163 @Override 3164 public NoReturnValue visitElements(Elements o) { 3165 return super.visitElements(o); 3166 } 3167 3168 @Override 3169 public NoReturnValue visitFunctionOf(FunctionOf o) { 3170 simples.add(o.function); 3171 return super.visitFunctionOf(o); 3172 } 3173 3174 @Override 3175 public NoReturnValue visitFunctionOfN(FunctionOfN o) { 3176 simples.add(o.function); 3177 return super.visitFunctionOfN(o); 3178 } 3179 3180 @Override 3181 public NoReturnValue visitSubscript(Subscript o) { 3182 o.sequence.accept(this); 3183 return o.index.accept(this); 3184 } 3185 3186 @Override 3187 public NoReturnValue visitSlice(Slice o) { 3188 if (o.i != null) { 3189 o.i.accept(this); 3190 } 3191 if (o.j != null) { 3192 o.j.accept(this); 3193 } 3194 return o.sequence.accept(this); 3195 } 3196 } 3197 3198 /** 3199 * A quantifier visitor can be used to search a tree and return all unquantified sequences (e.g. 3200 * a[] or a[i..j]). 3201 */ 3202 public static class QuantifierVisitor extends AbstractVisitor<NoReturnValue> { 3203 public QuantifierVisitor(VarInfoName root) { 3204 assert root != null; 3205 unquant = new HashSet<VarInfoName>(); 3206 root.accept(this); 3207 } 3208 3209 // state and accessors 3210 /** 3211 * See {@link #unquants()}. 3212 * 3213 * @see #unquants() 3214 */ 3215 private Set<VarInfoName> /*actually <Elements || Slice>*/ unquant; 3216 3217 /** 3218 * Returns a collection of the nodes under the root that need quantification. Each node 3219 * represents an array; in particular, the values are either of type Elements or Slice. 3220 * 3221 * @return the nodes under the root that need quantification 3222 */ 3223 // Here are some inputs and the corresponding output sets: 3224 // terms[index].elts[num] ==> { } 3225 // terms[index].elts[] ==> { terms[index].elts[] } 3226 // terms[].elts[] ==> { terms[], terms[].elts[] } 3227 // ary[row][col] ==> { } 3228 // ary[row][] ==> { ary[row][] } 3229 // ary[][] ==> { ary[], ary[][] } 3230 public Set<VarInfoName> unquants() { 3231 if (QuantHelper.debug.isLoggable(Level.FINE)) { 3232 QuantHelper.debug.fine("unquants: " + unquant); 3233 } 3234 return Collections.unmodifiableSet(unquant); 3235 } 3236 3237 // visitor methods that get the job done 3238 @Override 3239 public NoReturnValue visitSimple(Simple o) { 3240 return super.visitSimple(o); 3241 } 3242 3243 @Override 3244 public NoReturnValue visitElements(Elements o) { 3245 unquant.add(o); 3246 return super.visitElements(o); 3247 } 3248 3249 @Override 3250 public NoReturnValue visitFunctionOf(FunctionOf o) { 3251 return null; 3252 // return o.args.get(0).accept(this); // Return value doesn't matter 3253 // We only use one of them because we don't want double quantifiers 3254 } 3255 3256 /** 3257 * We do *not* want to pull out array members of FunctionOfN because a FunctionOfN creates a 3258 * black-box array with respect to quantification. (Also, otherwise, there may be two or more 3259 * arrays that are returned, making the quantification engine think it's working with 2-d 3260 * arrays.) 3261 */ 3262 @Override 3263 public NoReturnValue visitFunctionOfN(FunctionOfN o) { 3264 return null; 3265 // return o.args.get(0).accept(this); // Return value doesn't matter 3266 // We only use one of them because we don't want double quantifiers 3267 } 3268 3269 @Override 3270 public NoReturnValue visitSizeOf(SizeOf o) { 3271 // don't visit the sequence; we aren't using the elements of it, 3272 // just the length, so we don't want to include it in the results 3273 return o.get_term().accept(this); 3274 } 3275 3276 @Override 3277 public NoReturnValue visitSubscript(Subscript o) { 3278 o.index.accept(this); 3279 // don't visit the sequence; it is fixed with an exact 3280 // subscript, so we don't want to include it in the results 3281 return o.sequence.term.accept(this); 3282 } 3283 3284 @Override 3285 public NoReturnValue visitSlice(Slice o) { 3286 unquant.add(o); 3287 if (o.i != null) { 3288 o.i.accept(this); 3289 } 3290 if (o.j != null) { 3291 o.j.accept(this); 3292 } 3293 // don't visit the sequence; we will replace the slice with the 3294 // subscript, so we want to leave the elements alone 3295 return o.sequence.term.accept(this); 3296 } 3297 } 3298 3299 // ============================================================ 3300 // Quantification for formatting in ESC or Simplify: QuantHelper 3301 3302 /** 3303 * Helper for writing parts of quantification expressions. Formatting methods in invariants call 3304 * the formatting methods in this class to get commonly-used parts, like how universal 3305 * quanitifiers look in the different formatting schemes. 3306 */ 3307 public static class QuantHelper { 3308 3309 /** Debug tracer. */ 3310 public static final Logger debug = Logger.getLogger("daikon.inv.Invariant.print.QuantHelper"); 3311 3312 /** 3313 * A FreeVar is very much like a Simple, except that it doesn't care if it's in prestate or 3314 * poststate for simplify formatting. 3315 */ 3316 public static class FreeVar extends Simple { 3317 // We are Serializable, so we specify a version to allow changes to 3318 // method signatures without breaking serialization. If you add or 3319 // remove fields, you should change this number to the current date. 3320 static final long serialVersionUID = 20020130L; 3321 3322 public FreeVar(String name) { 3323 super(name); 3324 } 3325 3326 @Override 3327 protected String repr_impl(@GuardSatisfied @UnknownSignedness FreeVar this) { 3328 return "Free[" + super.repr_impl() + "]"; 3329 } 3330 3331 @Override 3332 protected String jml_name_impl(VarInfo v) { 3333 return super.jml_name_impl(v); 3334 } 3335 3336 // protected String esc_name_impl() { 3337 // return super.esc_name_impl(); 3338 // } 3339 @Override 3340 protected String simplify_name_impl(boolean prestate) { 3341 return super.simplify_name_impl(false); 3342 } 3343 } 3344 3345 // <root, needy, index> -> <root', lower, upper> 3346 /** 3347 * Replaces a needy (unquantified term) with its subscripted equivalent, using the given index 3348 * variable. 3349 * 3350 * @param root the root of the expression to be modified. Substitution occurs only in the 3351 * subtree reachable from root. 3352 * @param needy the term to be subscripted (must be of type Elements or Slice) 3353 * @param index the variable to place in the subscript 3354 * @return a 3-element array consisting of the new root, the lower bound for the index 3355 * (inclusive), and the upper bound for the index (inclusive), in that order 3356 */ 3357 public static VarInfoName[] replace(VarInfoName root, VarInfoName needy, VarInfoName index) { 3358 assert root != null; 3359 assert needy != null; 3360 assert index != null; 3361 assert (needy instanceof Elements) || (needy instanceof Slice); 3362 3363 // Figure out what to replace needy with, and the appropriate 3364 // bounds to use 3365 VarInfoName replace_with; 3366 VarInfoName lower, upper; 3367 if (needy instanceof Elements) { 3368 Elements sequence = (Elements) needy; 3369 replace_with = sequence.getSubscript(index); 3370 lower = sequence.getLowerBound(); 3371 upper = sequence.getUpperBound(); 3372 } else if (needy instanceof Slice) { 3373 Slice slice = (Slice) needy; 3374 replace_with = slice.getSubscript(index); 3375 lower = slice.getLowerBound(); 3376 upper = slice.getUpperBound(); 3377 } else { 3378 // unreachable; placate javac 3379 throw new IllegalStateException(); 3380 } 3381 assert replace_with != null; 3382 3383 // If needy was in prestate, adjust bounds appropriately 3384 if (root.inPrestateContext(needy)) { 3385 if (!lower.isLiteralConstant()) { 3386 if (lower instanceof Poststate) { 3387 lower = ((Poststate) lower).term; 3388 } else { 3389 lower = lower.applyPrestate(); 3390 } 3391 } 3392 if (!upper.isLiteralConstant()) { 3393 if (upper instanceof Poststate) { 3394 upper = ((Poststate) upper).term; 3395 } else { 3396 upper = upper.applyPrestate(); 3397 } 3398 } 3399 } 3400 3401 // replace needy 3402 VarInfoName root_prime = new Replacer(needy, replace_with).replace(root).intern(); 3403 3404 assert root_prime != null; 3405 assert lower != null; 3406 assert upper != null; 3407 3408 return new VarInfoName[] {root_prime, lower, upper}; 3409 } 3410 3411 /** 3412 * Assuming that root is a sequence, return a VarInfoName representing the 3413 * (index_base+index_off)-th element of that sequence. index_base may be null, to represent 0. 3414 */ 3415 public static VarInfoName selectNth( 3416 VarInfoName root, @Nullable VarInfoName index_base, int index_off) { 3417 QuantifierVisitor qv = new QuantifierVisitor(root); 3418 List<VarInfoName> unquants = new ArrayList<>(qv.unquants()); 3419 if (unquants.size() == 0) { 3420 // Nothing to do? 3421 return null; 3422 } else if (unquants.size() == 1) { 3423 VarInfoName index_vin; 3424 if (index_base != null) { 3425 index_vin = index_base; 3426 if (index_off != 0) index_vin = index_vin.applyAdd(index_off); 3427 } else { 3428 index_vin = new Simple(Integer.toString(index_off)).intern(); 3429 } 3430 VarInfoName to_replace = unquants.get(0); 3431 @Interned VarInfoName[] replace_result = replace(root, to_replace, index_vin); 3432 return replace_result[0]; 3433 } else { 3434 throw new Error("Can't handle multi-dim array in VarInfoName.QuantHelper.select_nth()"); 3435 } 3436 } 3437 3438 /** 3439 * Assuming that root is a sequence, return a VarInfoName representing the 3440 * (index_base+index_off)-th element of that sequence. index_base may be null, to represent 0. 3441 */ 3442 public static VarInfoName selectNth( 3443 VarInfoName root, String index_base, boolean free, int index_off) { 3444 QuantifierVisitor qv = new QuantifierVisitor(root); 3445 List<VarInfoName> unquants = new ArrayList<>(qv.unquants()); 3446 if (unquants.size() == 0) { 3447 // Nothing to do? 3448 return null; 3449 } else if (unquants.size() == 1) { 3450 VarInfoName index_vin; 3451 if (index_base != null) { 3452 if (index_off != 0) index_base += "+" + index_off; 3453 if (free) { 3454 index_vin = new FreeVar(index_base); 3455 } else { 3456 index_vin = VarInfoName.parse(index_base); 3457 } 3458 // if (index_base.contains ("a")) 3459 // System.out.printf("selectNth: '%s' '%s'%n", index_base, 3460 // index_vin); 3461 } else { 3462 index_vin = new Simple(Integer.toString(index_off)); 3463 } 3464 VarInfoName to_replace = unquants.get(0); 3465 VarInfoName[] replace_result = replace(root, to_replace, index_vin); 3466 // if ((index_base != null) && index_base.contains ("a")) 3467 // System.out.printf("root = %s, to_replace = %s, index_vin = %s%n", 3468 // root, to_replace, index_vin); 3469 return replace_result[0]; 3470 } else { 3471 throw new Error("Can't handle multi-dim array in VarInfoName.QuantHelper.select_nth()"); 3472 } 3473 } 3474 3475 // Return a string distinct from any of the strings in "taken". 3476 private static String freshDistinctFrom(Set<String> taken) { 3477 char c = 'i'; 3478 String name; 3479 do { 3480 name = String.valueOf(c++); 3481 } while (taken.contains(name)); 3482 return name; 3483 } 3484 3485 /** Return a fresh variable name that doesn't appear in the given variable names. */ 3486 public static VarInfoName getFreeIndex(VarInfoName... vins) { 3487 Set<String> simples = new HashSet<>(); 3488 for (VarInfoName vin : vins) { 3489 simples.addAll(new SimpleNamesVisitor(vin).simples()); 3490 } 3491 return new FreeVar(freshDistinctFrom(simples)); 3492 } 3493 3494 /** Record type for return value of the quantify method below. */ 3495 public static class QuantifyReturn { 3496 public @Interned VarInfoName[] root_primes; 3497 public List<@Interned VarInfoName[]> 3498 bound_vars; // each element is VarInfoName[3] = <variable, lower, upper> 3499 } 3500 3501 // <root*> -> <root'*, <index, lower, upper>*> 3502 // (The lengths of root* and root'* are the same; not sure about <i,l,u>*.) 3503 /** 3504 * Given a list of roots, changes all Elements and Slice terms to Subscripts by inserting a new 3505 * free variable; also return bounds for the new variables. 3506 */ 3507 public static QuantifyReturn quantify(VarInfoName[] roots) { 3508 assert roots != null; 3509 3510 if (QuantHelper.debug.isLoggable(Level.FINE)) { 3511 QuantHelper.debug.fine("roots: " + Arrays.asList(roots)); 3512 } 3513 3514 // create empty result 3515 QuantifyReturn result = new QuantifyReturn(); 3516 result.root_primes = new VarInfoName[roots.length]; 3517 result.bound_vars = new ArrayList<VarInfoName[]>(); 3518 3519 // all of the simple identifiers used by these roots 3520 Set<String> simples = new HashSet<>(); 3521 3522 // build helper for each roots; collect identifiers 3523 QuantifierVisitor[] helper = new QuantifierVisitor[roots.length]; 3524 for (int i = 0; i < roots.length; i++) { 3525 if (QuantHelper.debug.isLoggable(Level.FINE)) { 3526 QuantHelper.debug.fine("Calling quanthelper on: " + i + " " + roots[i]); 3527 } 3528 3529 helper[i] = new QuantifierVisitor(roots[i]); 3530 simples.addAll(new SimpleNamesVisitor(roots[i]).simples()); 3531 } 3532 3533 // choose names for the indices that don't conflict, and then 3534 // replace the right stuff in the term 3535 char tmp = 'i'; 3536 for (int i = 0; i < roots.length; i++) { 3537 List<VarInfoName> uq = new ArrayList<>(helper[i].unquants()); 3538 if (uq.size() == 0) { 3539 // nothing needs quantification 3540 result.root_primes[i] = roots[i]; 3541 } else { 3542 if (QuantHelper.debug.isLoggable(Level.FINE)) { 3543 QuantHelper.debug.fine("root: " + roots[i]); 3544 QuantHelper.debug.fine("uq_elts: " + uq.toString()); 3545 } 3546 3547 // We assume that the input was one unquantified sequence 3548 // variable. If uq has more than one element, then the 3549 // sequence had more than one dimension. 3550 assert uq.size() == 1 : "We can only handle 1D arrays for now"; 3551 3552 VarInfoName uq_elt = uq.get(0); 3553 3554 String idx_name; 3555 do { 3556 idx_name = String.valueOf(tmp++); 3557 } while (simples.contains(idx_name)); 3558 assert tmp <= 'z' : "Ran out of letters in quantification"; 3559 VarInfoName idx = new FreeVar(idx_name).intern(); 3560 3561 if (QuantHelper.debug.isLoggable(Level.FINE)) { 3562 QuantHelper.debug.fine("idx: " + idx); 3563 } 3564 3565 // call replace and unpack results 3566 VarInfoName[] replace_result = replace(roots[i], uq_elt, idx); 3567 VarInfoName root_prime = replace_result[0]; 3568 VarInfoName lower = replace_result[1]; 3569 VarInfoName upper = replace_result[2]; 3570 3571 result.root_primes[i] = root_prime; 3572 result.bound_vars.add(new VarInfoName[] {idx, lower, upper}); 3573 } 3574 } 3575 3576 return result; 3577 } 3578 3579 // <root*> -> <string string* string> 3580 /** 3581 * Given a list of roots, return a String array where the first element is a ESC-style 3582 * quantification over newly-introduced bound variables, the last element is a closer, and the 3583 * other elements are esc-named strings for the provided roots (with sequences subscripted by 3584 * one of the new bound variables). 3585 */ 3586 public static String[] format_esc(VarInfoName[] roots) { 3587 return format_esc(roots, false); 3588 } 3589 3590 public static String[] format_esc(VarInfoName[] roots, boolean elementwise) { 3591 // The call to format_esc is now handled by the combined formatter format_java_style 3592 return format_java_style(roots, elementwise, true, OutputFormat.ESCJAVA); 3593 } 3594 3595 // <root*> -> <string string*> 3596 /** 3597 * Given a list of roots, return a String array where the first element is a JML-style 3598 * quantification over newly-introduced bound variables, the last element is a closer, and the 3599 * other elements are jml-named strings for the provided roots (with sequenced subscripted by 3600 * one of the new bound variables). 3601 */ 3602 // public static String[] format_jml(VarInfoName[] roots) { 3603 // return format_jml(roots, false); 3604 // } 3605 // public static String[] format_jml(VarInfoName[] roots, boolean elementwise) { 3606 // return format_jml(roots, elementwise, true); 3607 // } 3608 // public static String[] format_jml(VarInfoName[] roots, boolean elementwise, boolean forall) { 3609 // return format_java_style(roots, elementwise, forall, OutputFormat.JML); 3610 // } 3611 3612 /* CP: Quantification for DBC: We would like quantified expression 3613 * to always return a boolean value, and in the previous 3614 * implementation (commented out below), quantification was 3615 * expressed as a for-loop, which does not return boolean 3616 * values. An alternative solution would be to use Jtest's $forall 3617 * and $exists constrcuts, but testing showed that Jtest does not 3618 * allow these constructs in @post annotations (!). The current 3619 * implementation uses helper methods defined in a separate class 3620 * daikon.Quant (not currently included with Daikon's 3621 * distribution). These methods always return a boolean value and 3622 * look something like this: 3623 * 3624 * Quant.eltsEqual(this.theArray, null) 3625 * Quant.subsetOf(this.arr, new int[] { 1, 2, 3 }) 3626 * 3627 */ 3628 // /** 3629 // * vi is the Varinfo corresponding to the VarInfoName var. Uses 3630 // * the variable i to iterate. This could mean a conflict with the 3631 // * name of the argument var. 3632 // */ 3633 // public static String dbcForalli(VarInfoName.Elements var, VarInfo vi, 3634 // String condition) { 3635 // if (vi.type.isArray()) { 3636 // return 3637 // "(java.util.Arrays.asList(" + var.term.dbc_name(vi) 3638 // + ")).$forall(" + vi.type.base() + " i, " 3639 // + condition + ")"; 3640 // } 3641 // return var.term.dbc_name(vi) 3642 // + ".$forall(" + vi.type.base() + " i, " 3643 // + condition + ")"; 3644 // } 3645 3646 // /** 3647 // * vi is the Varinfo corresponding to the VarInfoName var. Uses 3648 // * the variable i to iterate. This could mean a conflict with the 3649 // * name of the argument var. 3650 // */ 3651 // public static String dbcExistsi(VarInfoName.Elements var, VarInfo vi, 3652 // String condition) { 3653 // if (vi.type.isArray()) { 3654 // return 3655 // "(java.util.Arrays.asList(" + var.term.dbc_name(vi) 3656 // + ")).$exists(" + vi.type.base() + " i, " 3657 // + condition + ")"; 3658 // } 3659 // return var.term.dbc_name(vi) 3660 // + ".$exists(" + vi.type.base() + " i, " 3661 // + condition + ")"; 3662 // } 3663 3664 // //@tx 3665 // public static String[] format_dbc(VarInfoName[] roots, VarInfo[] varinfos) { 3666 // return format_dbc(roots, true, varinfos); 3667 // } 3668 // public static String[] format_dbc(VarInfoName[] roots, boolean elementwise, 3669 // VarInfo[] varinfos) { 3670 // return format_dbc(roots, elementwise, true, varinfos); 3671 // } 3672 // public static String[] format_dbc(VarInfoName[] roots, boolean elementwise, 3673 // boolean forall, VarInfo[] varinfos) { 3674 // assert roots != null; 3675 3676 // QuantifyReturn qret = quantify(roots); 3677 3678 // // build the "\forall ..." predicate 3679 // String[] result = new String[roots.length + 2]; 3680 // StringBuilder int_list, conditions, closing; 3681 // StringBuilder tempResult; 3682 // { 3683 // tempResult = new StringBuilder(); 3684 // // "i, j, ..." 3685 // int_list = new StringBuilder(); 3686 // // "ai <= i && i <= bi && aj <= j && j <= bj && ..." 3687 // // if elementwise, also do "(i-ai) == (b-bi) && ..." 3688 // conditions = new StringBuilder(); 3689 // closing = new StringBuilder(); 3690 // for (int i = 0; i < qret.bound_vars.size(); i++) { 3691 // int_list.setLength(0); 3692 // conditions.setLength(0); 3693 // closing.setLength(0); 3694 3695 // VarInfoName[] boundv = qret.bound_vars.get(i); 3696 // VarInfoName idx = boundv[0], low = boundv[1], high = boundv[2]; 3697 // if (i != 0) { 3698 // //int_list.append(", "); 3699 // //conditions.append(" && "); 3700 // //closing.append(", "); 3701 // closing.append(idx.dbc_name(null)); 3702 // closing.append("++"); 3703 // } else { 3704 // closing.append(idx.dbc_name(null)); 3705 // closing.append("++"); 3706 // } 3707 // int_list.append(idx.dbc_name(null)); 3708 // int_list.append(" = "); //@TX 3709 // int_list.append(low.dbc_name(null)); 3710 3711 // conditions.append(idx.dbc_name(null)); 3712 // conditions.append(" <= "); 3713 // conditions.append(high.dbc_name(null)); 3714 3715 // if (elementwise && (i >= 1)) { 3716 // VarInfoName[] _boundv = qret.bound_vars.get(i - 1); 3717 // VarInfoName _idx = _boundv[0], _low = _boundv[1]; 3718 // conditions.append(" && "); 3719 // if (ZERO.equals(_low)) { 3720 // conditions.append(_idx); 3721 // } else { 3722 // conditions.append("("); 3723 // conditions.append(_idx.dbc_name(null)); 3724 // conditions.append("-("); 3725 // conditions.append(_low.dbc_name(null)); 3726 // conditions.append("))"); 3727 // } 3728 // conditions.append(" == "); 3729 // if (ZERO.equals(low)) { 3730 // conditions.append(idx.dbc_name(null)); 3731 // } else { 3732 // conditions.append("("); 3733 // conditions.append(idx.dbc_name(null)); 3734 // conditions.append("-("); 3735 // conditions.append(low.dbc_name(null)); 3736 // conditions.append("))"); 3737 // } 3738 // } 3739 // tempResult.append(" for (int " + int_list + " ; " + conditions + "; " + closing + 3740 // ") "); 3741 // } 3742 // } 3743 // //result[0] = "{ for (int " + int_list + " ; " + conditions + "; " 3744 // + closing + ") $assert ("; //@TX 3745 // result[0] = "{ " + tempResult + " $assert ("; //@TX 3746 // result[result.length - 1] = "); }"; 3747 3748 // // stringify the terms 3749 // for (int i = 0; i < roots.length; i++) { 3750 // result[i + 1] = qret.root_primes[i].dbc_name(null); 3751 // } 3752 3753 // return result; 3754 // } 3755 3756 ////////////////////////// 3757 3758 public static String[] simplifyNameAndBounds(VarInfoName name) { 3759 String[] results = new String[3]; 3760 boolean preState = false; 3761 if (name instanceof Prestate) { 3762 Prestate wrapped = (Prestate) name; 3763 name = wrapped.term; 3764 preState = true; 3765 } 3766 if (name instanceof Elements) { 3767 Elements sequence = (Elements) name; 3768 VarInfoName array = sequence.term; 3769 results[0] = array.simplify_name(preState); 3770 results[1] = sequence.getLowerBound().simplify_name(preState); 3771 results[2] = sequence.getUpperBound().simplify_name(preState); 3772 return results; 3773 } else if (name instanceof Slice) { 3774 Slice slice = (Slice) name; 3775 VarInfoName array = slice.sequence.term; 3776 results[0] = array.simplify_name(preState); 3777 results[1] = slice.getLowerBound().simplify_name(preState); 3778 results[2] = slice.getUpperBound().simplify_name(preState); 3779 return results; 3780 } else { 3781 // There are some other cases this scheme can't handle. 3782 // For instance, if every Book has an ISBN, a front-end 3783 // might distribute the access to that field over an array 3784 // of books, so that "books[].isbn" is an array of ISBNs, 3785 // though its name has type Field. 3786 return null; 3787 } 3788 } 3789 3790 // <root*> -> <string string*> 3791 /** 3792 * Given a list of roots, return a String array where the first element is a simplify-style 3793 * quantification over newly-introduced bound variables, the last element is a closer, and the 3794 * other elements are simplify-named strings for the provided roots (with sequences subscripted 3795 * by one of the new bound variables). 3796 * 3797 * <p>If elementwise is true, include the additional contraint that the indices (there must be 3798 * exactly two in this case) refer to corresponding positions. If adjacent is true, include the 3799 * additional constraint that the second index be one more than the first. If distinct is true, 3800 * include the constraint that the two indices are different. If includeIndex is true, return 3801 * additional strings, after the roots but before the closer, with the names of the index 3802 * variables. 3803 */ 3804 // XXX This argument list is starting to get out of hand. -smcc 3805 public static String[] format_simplify(VarInfoName[] roots) { 3806 return format_simplify(roots, false, false, false, false); 3807 } 3808 3809 public static String[] format_simplify(VarInfoName[] roots, boolean eltwise) { 3810 return format_simplify(roots, eltwise, false, false, false); 3811 } 3812 3813 public static String[] format_simplify(VarInfoName[] roots, boolean eltwise, boolean adjacent) { 3814 return format_simplify(roots, eltwise, adjacent, false, false); 3815 } 3816 3817 public static String[] format_simplify( 3818 VarInfoName[] roots, boolean eltwise, boolean adjacent, boolean distinct) { 3819 return format_simplify(roots, eltwise, adjacent, distinct, false); 3820 } 3821 3822 public static String[] format_simplify( 3823 VarInfoName[] roots, 3824 boolean elementwise, 3825 boolean adjacent, 3826 boolean distinct, 3827 boolean includeIndex) { 3828 assert roots != null; 3829 3830 if (adjacent || distinct) { 3831 assert roots.length == 2; 3832 } 3833 3834 QuantifyReturn qret = quantify(roots); 3835 3836 // build the forall predicate 3837 String[] result = new String[(includeIndex ? 2 : 1) * roots.length + 2]; 3838 StringBuilder int_list, conditions; 3839 { 3840 // "i j ..." 3841 int_list = new StringBuilder(); 3842 // "(AND (<= ai i) (<= i bi) (<= aj j) (<= j bj) ...)" 3843 // if elementwise, also insert "(EQ (- i ai) (- j aj)) ..." 3844 conditions = new StringBuilder(); 3845 for (int i = 0; i < qret.bound_vars.size(); i++) { 3846 VarInfoName[] boundv = qret.bound_vars.get(i); 3847 VarInfoName idx = boundv[0], low = boundv[1], high = boundv[2]; 3848 if (i != 0) { 3849 int_list.append(" "); 3850 conditions.append(" "); 3851 } 3852 int_list.append(idx.simplify_name()); 3853 conditions.append("(<= " + low.simplify_name() + " " + idx.simplify_name() + ")"); 3854 conditions.append(" (<= " + idx.simplify_name() + " " + high.simplify_name() + ")"); 3855 if (elementwise && (i >= 1)) { 3856 VarInfoName[] _boundv = qret.bound_vars.get(i - 1); 3857 VarInfoName _idx = _boundv[0], _low = _boundv[1]; 3858 if (_low.simplify_name().equals(low.simplify_name())) { 3859 conditions.append(" (EQ " + _idx.simplify_name() + " " + idx.simplify_name() + ")"); 3860 } else { 3861 conditions.append( 3862 " (EQ (- " + _idx.simplify_name() + " " + _low.simplify_name() + ")"); 3863 conditions.append(" (- " + idx.simplify_name() + " " + low.simplify_name() + "))"); 3864 } 3865 } 3866 if (i == 1 && (adjacent || distinct)) { 3867 VarInfoName[] _boundv = qret.bound_vars.get(i - 1); 3868 VarInfoName prev_idx = _boundv[0]; 3869 if (adjacent) { 3870 conditions.append( 3871 " (EQ (+ " + prev_idx.simplify_name() + " 1) " + idx.simplify_name() + ")"); 3872 } 3873 if (distinct) { 3874 conditions.append( 3875 " (NEQ " + prev_idx.simplify_name() + " " + idx.simplify_name() + ")"); 3876 } 3877 } 3878 } 3879 } 3880 result[0] = "(FORALL (" + int_list + ") (IMPLIES (AND " + conditions + ") "; 3881 3882 // stringify the terms 3883 for (int i = 0; i < qret.root_primes.length; i++) { 3884 result[i + 1] = qret.root_primes[i].simplify_name(); 3885 } 3886 3887 // stringify the indices, if requested 3888 // note that the index should be relative to the slice, not relative 3889 // to the original array (we used to get this wrong) 3890 if (includeIndex) { 3891 for (int i = 0; i < qret.root_primes.length; i++) { 3892 VarInfoName[] boundv = qret.bound_vars.get(i); 3893 VarInfoName idx_var = boundv[0]; 3894 String idx_var_name = idx_var.simplify_name(); 3895 String lower_bound = qret.bound_vars.get(i)[1].simplify_name(); 3896 String idx_expr = "(- " + idx_var_name + " " + lower_bound + ")"; 3897 result[i + qret.root_primes.length + 1] = idx_expr; 3898 } 3899 } 3900 3901 result[result.length - 1] = "))"; // close IMPLIES, FORALL 3902 3903 return result; 3904 } 3905 3906 // Important Note: The Java quantification style actually makes no 3907 // sense as is. The resultant quantifications are statements as 3908 // opposed to expressions, and thus no value can be derived from 3909 // them. This must be fixed before the java statements are of any 3910 // value. However, the ESC and JML quantifications are fine because 3911 // they actually produce expressions with values. 3912 3913 // <root*> -> <string string* string> 3914 /** 3915 * Given a list of roots, return a String array where the first element is a Java-style 3916 * quantification over newly-introduced bound variables, the last element is a closer, and the 3917 * other elements are java-named strings for the provided roots (with sequences subscripted by 3918 * one of the new bound variables). 3919 */ 3920 // public static String[] format_java(VarInfoName[] roots) { 3921 // return format_java(roots, false); 3922 // } 3923 // public static String[] format_java(VarInfoName[] roots, boolean elementwise) { 3924 // return format_java_style(roots, false, true, OutputFormat.JAVA); 3925 // } 3926 3927 // This set of functions quantifies in the same manner to the ESC quantification, except that 3928 // JML names are used instead of ESC names, and minor formatting changes are incorporated 3929 // public static String[] format_jml(QuantifyReturn qret) { 3930 // return format_java_style(qret, false, true, OutputFormat.JML); 3931 // } 3932 // public static String[] format_jml(QuantifyReturn qret, boolean elementwise) { 3933 // return format_java_style(qret, elementwise, true, OutputFormat.JML); 3934 // } 3935 // public static String[] format_jml(QuantifyReturn qret, boolean elementwise, boolean 3936 // forall) { 3937 // return format_java_style(qret, elementwise, forall, OutputFormat.JML); 3938 // } 3939 3940 // This set of functions assists in quantification for all of the java style 3941 // output formats, that is, Java, ESC, and JML. It does the actual work behind 3942 // those formatting functions. This function was meant to be called only through 3943 // the other public formatting functions. 3944 // 3945 // The OutputFormat must be one of those three previously mentioned. 3946 // Also, if the Java format is selected, forall must be true. 3947 3948 protected static String[] format_java_style(VarInfoName[] roots, OutputFormat format) { 3949 return format_java_style(roots, false, true, format); 3950 } 3951 3952 protected static String[] format_java_style( 3953 VarInfoName[] roots, boolean elementwise, OutputFormat format) { 3954 return format_java_style(roots, elementwise, true, format); 3955 } 3956 3957 protected static String[] format_java_style( 3958 VarInfoName[] roots, boolean elementwise, boolean forall, OutputFormat format) { 3959 assert roots != null; 3960 3961 QuantifyReturn qret = quantify(roots); 3962 3963 return format_java_style(qret, elementwise, forall, format); 3964 } 3965 3966 // This form allows the indicies and bounds to be modified before quantification 3967 protected static String[] format_java_style(QuantifyReturn qret, OutputFormat format) { 3968 return format_java_style(qret, false, true, format); 3969 } 3970 3971 protected static String[] format_java_style( 3972 QuantifyReturn qret, boolean elementwise, OutputFormat format) { 3973 return format_java_style(qret, elementwise, true, format); 3974 } 3975 3976 protected static String[] format_java_style( 3977 QuantifyReturn qret, boolean elementwise, boolean forall, OutputFormat format) { 3978 // build the "\forall ..." predicate 3979 String[] result = new String[qret.root_primes.length + 2]; 3980 StringBuilder int_list, conditions, closing; 3981 { 3982 // "i, j, ..." 3983 int_list = new StringBuilder(); 3984 // "ai <= i && i <= bi && aj <= j && j <= bj && ..." 3985 // if elementwise, also do "(i-ai) == (b-bi) && ..." 3986 conditions = new StringBuilder(); 3987 closing = new StringBuilder(); 3988 for (int i = 0; i < qret.bound_vars.size(); i++) { 3989 VarInfoName[] boundv = qret.bound_vars.get(i); 3990 VarInfoName idx = boundv[0], low = boundv[1], high = boundv[2]; 3991 if (i != 0) { 3992 int_list.append(", "); 3993 conditions.append(" && "); 3994 } 3995 closing.append(quant_increment(idx, i, format)); 3996 3997 int_list.append(quant_var_initial_state(idx, low, format)); 3998 conditions.append(quant_execution_condition(low, idx, high, format)); 3999 4000 if (elementwise && (i >= 1)) { 4001 VarInfoName[] _boundv = qret.bound_vars.get(i - 1); 4002 VarInfoName _idx = _boundv[0], _low = _boundv[1]; 4003 if (format == OutputFormat.JAVA) { 4004 conditions.append(" || "); 4005 } else { 4006 conditions.append(" && "); 4007 } 4008 4009 conditions.append(quant_element_conditions(_idx, _low, idx, low, format)); 4010 } 4011 } 4012 } 4013 4014 if (forall) { 4015 result[0] = quant_format_forall(format); 4016 } else { 4017 result[0] = quant_format_exists(format); 4018 } 4019 4020 result[0] += 4021 (int_list 4022 + quant_separator1(format) 4023 + conditions 4024 + quant_separator2(format) 4025 + closing 4026 + quant_step_terminator(format)); 4027 result[result.length - 1] = ")"; 4028 4029 // stringify the terms 4030 for (int i = 0; i < qret.root_primes.length; i++) { 4031 result[i + 1] = qret.root_primes[i].name_using(format, null); 4032 } 4033 4034 return result; 4035 } 4036 4037 // This set of functions are helper functions to the quantification function. 4038 4039 /** 4040 * This function creates a string that represents how to increment the variables involved in 4041 * quantification. Since the increment is not stated explicitly in the JML and ESC formats this 4042 * function merely returns an empty string for those formats. 4043 */ 4044 protected static String quant_increment(VarInfoName idx, int i, OutputFormat format) { 4045 if (format != OutputFormat.JAVA) { 4046 return ""; 4047 } else { 4048 if (i != 0) { 4049 return (", " + idx.esc_name() + "++"); 4050 } else { 4051 return (idx.esc_name() + "++"); 4052 } 4053 } 4054 } 4055 4056 /** 4057 * This function returns a string that represents the initial condition for the index variable. 4058 */ 4059 protected static String quant_var_initial_state( 4060 VarInfoName idx, VarInfoName low, OutputFormat format) { 4061 if (format == OutputFormat.JAVA) { 4062 return idx.esc_name() + " == " + low.esc_name(); 4063 } else { 4064 return idx.name_using(format, null); 4065 } 4066 } 4067 4068 /** 4069 * This function returns a string that represents the execution condition for the 4070 * quantification. 4071 */ 4072 protected static String quant_execution_condition( 4073 VarInfoName low, VarInfoName idx, VarInfoName high, OutputFormat format) { 4074 if (format == OutputFormat.JAVA) { 4075 return idx.esc_name() + " <= " + high.esc_name(); 4076 } else { 4077 return low.name_using(format, null) 4078 + " <= " 4079 + idx.name_using(format, null) 4080 + " && " 4081 + idx.name_using(format, null) 4082 + " <= " 4083 + high.name_using(format, null); 4084 } 4085 } 4086 4087 /** 4088 * This function returns a string representing the extra conditions necessary if the 4089 * quantification is element-wise. 4090 */ 4091 protected static String quant_element_conditions( 4092 VarInfoName _idx, VarInfoName _low, VarInfoName idx, VarInfoName low, OutputFormat format) { 4093 StringBuilder conditions = new StringBuilder(); 4094 4095 if (ZERO.equals(_low)) { 4096 conditions.append(_idx.name_using(format, null)); 4097 } else { 4098 conditions.append("("); 4099 conditions.append(_idx.name_using(format, null)); 4100 conditions.append("-("); 4101 conditions.append(_low.name_using(format, null)); 4102 conditions.append("))"); 4103 } 4104 conditions.append(" == "); 4105 if (ZERO.equals(low)) { 4106 conditions.append(idx.name_using(format, null)); 4107 } else { 4108 conditions.append("("); 4109 conditions.append(idx.name_using(format, null)); 4110 conditions.append("-("); 4111 conditions.append(low.name_using(format, null)); 4112 conditions.append("))"); 4113 } 4114 4115 return conditions.toString(); 4116 } 4117 4118 /** 4119 * This function returns a string representing how to format a forall statement in a given 4120 * output mode. 4121 */ 4122 protected static String quant_format_forall(OutputFormat format) { 4123 if (format == OutputFormat.JAVA) { 4124 return "(for (int "; 4125 } else { 4126 return "(\\forall int "; 4127 } 4128 } 4129 4130 /** 4131 * This function returns a string representing how to format an exists statement in a given 4132 * output mode. 4133 */ 4134 protected static String quant_format_exists(OutputFormat format) { 4135 return "(\\exists int "; 4136 } 4137 4138 /** 4139 * This function returns a string representing how to format the first seperation in the 4140 * quantification, that is, the one between the intial condition and the execution condition. 4141 */ 4142 protected static String quant_separator1(OutputFormat format) { 4143 if (format == OutputFormat.JML) { 4144 return "; "; 4145 } else { 4146 return "; ("; 4147 } 4148 } 4149 4150 /** 4151 * This function returns a string representing how to format the second seperation in the 4152 * quantification, that is, the one between the execution condition and the assertion. 4153 */ 4154 protected static String quant_separator2(OutputFormat format) { 4155 if (format == OutputFormat.ESCJAVA) { 4156 return ") ==> "; 4157 } else { 4158 return "; "; 4159 } 4160 } 4161 4162 /** 4163 * This function returns a string representing how to format the final seperation in the 4164 * quantification, that is, the one between the assertion and any closing symbols. 4165 */ 4166 protected static String quant_step_terminator(OutputFormat format) { 4167 if (format == OutputFormat.JAVA) { 4168 return ")"; 4169 } 4170 return ""; 4171 } 4172 } // QuantHelper 4173 4174 // Special JML capability, since JML cannot format a sequence of elements, 4175 // often what is wanted is the name of the reference (we have a[], we want 4176 // a. This function provides the appropriate name for these circumstances. 4177 public VarInfoName JMLElementCorrector() { 4178 if (this instanceof Elements) { 4179 return ((Elements) this).term; 4180 } else if (this instanceof Slice) { 4181 return ((Slice) this).sequence.term; 4182 } else if (this instanceof Prestate) { 4183 return ((Prestate) this).term.JMLElementCorrector().applyPrestate(); 4184 } else if (this instanceof Poststate) { 4185 return ((Poststate) this).term.JMLElementCorrector().applyPoststate(); 4186 } 4187 return this; 4188 } 4189 4190 // ============================================================ 4191 // Transformation framework 4192 4193 /** Specifies a function that performs a transformation on VarInfoNames. */ 4194 public interface Transformer { 4195 /** Perform a transformation on the argument. */ 4196 public VarInfoName transform(VarInfoName v); 4197 } 4198 4199 /** A pass-through transformer. */ 4200 public static final Transformer IDENTITY_TRANSFORMER = 4201 new Transformer() { 4202 @Override 4203 public VarInfoName transform(VarInfoName v) { 4204 return v; 4205 } 4206 }; 4207 4208 /** Compare VarInfoNames alphabetically. */ 4209 public static class LexicalComparator implements Comparator<VarInfoName> { 4210 @Pure 4211 @Override 4212 public int compare(VarInfoName name1, VarInfoName name2) { 4213 return name1.compareTo(name2); 4214 } 4215 } 4216}