001package daikon; 002 003import static daikon.FileIO.ParentRelation; 004 005import daikon.inv.Equality; 006import daikon.inv.Invariant; 007import daikon.split.PptSplitter; 008import java.io.Serializable; 009import java.util.ArrayList; 010import java.util.Arrays; 011import java.util.Iterator; 012import java.util.LinkedHashMap; 013import java.util.List; 014import java.util.Map; 015import java.util.Set; 016import java.util.StringJoiner; 017import java.util.logging.Level; 018import java.util.logging.Logger; 019import org.checkerframework.checker.initialization.qual.UnderInitialization; 020import org.checkerframework.checker.lock.qual.GuardSatisfied; 021import org.checkerframework.checker.nullness.qual.Nullable; 022import org.checkerframework.dataflow.qual.Pure; 023import org.checkerframework.dataflow.qual.SideEffectFree; 024 025/** 026 * Class that builds and describes relations in the ppt hierarchy. Building the relationship is 027 * specific to each type of parent/child relationship (eg, method to object, exit to combined exit, 028 * etc). The use of the relationship is general. 029 * 030 * <p>The basic function of the class is to translate from a variable in the parent to the 031 * equivalent variable in the child and vice-versa. For example, in the ENTER → EXIT 032 * relationship, the parent is the ENTER ppt and the child is the EXIT ppt. Each variable in the 033 * ENTER ppt is connected to the corresponding orig variable in the EXIT ppt. 034 */ 035public class PptRelation implements Serializable { 036 037 static final long serialVersionUID = 20030819L; 038 039 /** 040 * The different ppt/variable hierarchy relationships. Parent and User relations are specified in 041 * the declaration record of the ppt. ENTER_EXIT, EXIT_EXITNN, and PPT_COND are automatically 042 * constructed. MERGE_CHILD is not used by Daikon. 043 */ 044 public enum PptRelationType { 045 /** Acyclic relationship to a parent, eg, method to its object. */ 046 PARENT, 047 /** Possibly cyclic relationship, eg. nested object instances */ 048 USER, 049 /** Entrance of method to exit of method. */ 050 ENTER_EXIT, 051 /** Combined exit to numbered exit of a method. */ 052 EXIT_EXITNN, 053 /** Relation between the same ppt in two different PptMaps. */ 054 MERGE_CHILD, 055 /** Relation from a program point to its conditional ppts. */ 056 PPT_PPTCOND 057 }; 058 059 private static final Logger debug = Logger.getLogger("daikon.PptRelation"); 060 061 /** Description of type of parent-child relationship (debug output only). */ 062 PptRelationType relationship; 063 064 /** Parent of relation. */ 065 public PptTopLevel parent; 066 067 /** Child of relation. */ 068 public PptTopLevel child; 069 070 /** Map from parent vars to matching child vars. */ 071 @SuppressWarnings("serial") 072 public Map<VarInfo, VarInfo> parent_to_child_map; 073 074 /** Map from child vars to matching parent vars. */ 075 @SuppressWarnings("serial") 076 public Map<VarInfo, VarInfo> child_to_parent_map; 077 078 /** Boolean. Controls whether the object-user relation is created in the variable hierarchy. */ 079 public static boolean dkconfig_enable_object_user = false; 080 081 /** 082 * Create a relation between the specified parent and child. The actual variable relations are 083 * filled in by the caller. Note that this creates the connection between this relation and the 084 * parent/child. As a side effect, the constructed PptRelation is stored in both the parent and 085 * the child. 086 */ 087 private PptRelation(PptTopLevel parent, PptTopLevel child, PptRelationType rel_type) { 088 089 this.parent = parent; 090 this.child = child; 091 parent_to_child_map = new LinkedHashMap<>(); 092 child_to_parent_map = new LinkedHashMap<>(); 093 // rel_type is one of the above relationship types because this is a 094 // private constructor, called only within this file. 095 relationship = rel_type; 096 connect(); 097 } 098 099 /** Adds this relation to its child's parent list and its parent's children list. */ 100 @SuppressWarnings({ 101 "nullness:argument" // won't be used until initialization is finished 102 }) 103 private void connect(@UnderInitialization(PptRelation.class) PptRelation this) { 104 assert !child.parents.contains(this); 105 assert !parent.children.contains(this); 106 child.parents.add(this); 107 parent.children.add(this); 108 } 109 110 /** Returns the number of parent to child variable relations. */ 111 @Pure 112 public int size() { 113 return parent_to_child_map.size(); 114 } 115 116 @SideEffectFree 117 @Override 118 public String toString(@GuardSatisfied PptRelation this) { 119 return (parent.ppt_name + "->" + child.ppt_name + "(" + relationship + ")"); 120 } 121 122 /** Return a string containing all of the parent→child var relations. */ 123 public String parent_to_child_var_string() { 124 125 StringJoiner var_str = new StringJoiner(", "); 126 for (Map.Entry<VarInfo, VarInfo> entry : parent_to_child_map.entrySet()) { 127 var_str.add(entry.getKey().name() + "->" + entry.getValue().name()); 128 } 129 130 return var_str.toString(); 131 } 132 133 /** 134 * Relates all of the variables with the same name in parent and child. Returns true if each 135 * non-static parent variable was related to a child variable. 136 */ 137 public boolean relate_same_name() { 138 139 boolean relate_all = true; 140 for (VarInfo vp : parent.var_infos) { 141 boolean relate_var = relate(vp, vp.name()); 142 if (!relate_var && !vp.isStaticConstant()) { 143 // System.out.printf("no relation for '%s' from %s-%s with vars %s%n", 144 // vp.name(), parent.name(), child.name(), 145 // child.varNames()); 146 relate_all = false; 147 } 148 } 149 150 return relate_all; 151 } 152 153 /** Prints a ppt hierarchy of all of the ppts of this child and below. */ 154 public void debug_print_tree(Logger l, int indent) { 155 156 // Print the child tree including vars and class name 157 child.debug_print_tree(l, indent, this); 158 } 159 160 /** 161 * Returns whether or not this relation is a primary relation. This used to simplify debug prints 162 * of the PPt tree (so that extra relations don't result in duplicative information). 163 * 164 * <p>Somewhat arbitrarily, Object→User and Enter→Exit are not considered primary while 165 * all others are. The remaining relations (class→object, object→method,and 166 * exit→exitNN) form a simple tree without duplication. 167 */ 168 @Pure 169 public boolean is_primary() { 170 return (relationship != PptRelationType.USER) && (relationship != PptRelationType.ENTER_EXIT); 171 } 172 173 /** Returns a string describing the parent-child relationship. */ 174 public PptRelationType getRelationType() { 175 return relationship; 176 } 177 178 /** 179 * Returns the parent variable that corresponds to childVar. Returns null if there is no 180 * corresponding variable. 181 */ 182 public @Nullable VarInfo parentVar(VarInfo childVar) { 183 return child_to_parent_map.get(childVar); 184 } 185 186 /** 187 * Like parentVar(VarInfo), but if no parent is found, tries every variable in the equality set 188 * and returns null only if none of them has a parent. 189 */ 190 public @Nullable VarInfo parentVarAnyInEquality(VarInfo childVar) { 191 VarInfo result = parentVar(childVar); 192 if (result != null) { 193 return result; 194 } 195 if (childVar.equalitySet == null) { 196 return null; 197 } 198 for (VarInfo v : childVar.equalitySet.getVars()) { 199 result = parentVar(v); 200 if (result != null) { 201 return result; 202 } 203 } 204 return null; 205 } 206 207 /** 208 * Returns the child variable that corresponds to parentVar. Returns null if there is no 209 * corresponding variable. 210 */ 211 public @Nullable VarInfo childVar(VarInfo parentVar) { 212 return parent_to_child_map.get(parentVar); 213 } 214 215 /** Returns whether or not this relation's child has children of its own. */ 216 public boolean hasChildren() { 217 return (child.children.size() > 0); 218 } 219 220 /** 221 * Returns a map of VarInfo.Pair with an entry for each pair of equal variables in all of the 222 * equality sets of the child. The variables are the corresponding parent variables and not the 223 * child variables themselves. The map is from the pair to itself, which allows the pair to be 224 * looked up (which is not possible with a set). 225 */ 226 public Map<VarInfo.Pair, VarInfo.Pair> get_child_equalities_as_parent() { 227 228 debug.fine( 229 "get_child_equalities for " 230 + child.name() 231 + " for parent " 232 + parent.name() 233 + " " 234 + relationship); 235 Map<VarInfo.Pair, VarInfo.Pair> emap = new LinkedHashMap<>(); 236 237 if (child.equality_view == null) { 238 throw new Error( 239 "child.equality_view == null for child ppt: " 240 + child.name() 241 + " samples = " 242 + child.num_samples()); 243 } 244 if (child.equality_view.invs == null) { 245 throw new Error( 246 "child.equality_view.invs == null for child ppt: " 247 + child.name() 248 + " samples = " 249 + child.num_samples() 250 + "children = " 251 + child.children); 252 } 253 254 // Loop through each equality set in the child 255 for (Invariant inv : child.equality_view.invs) { 256 Equality e = (Equality) inv; 257 debug.fine("-- processing equality set " + e); 258 Set<VarInfo> eqset = e.getVars(); 259 VarInfo[] varr = eqset.toArray(new VarInfo[0]); 260 261 // Build each combination of variables in the equality set and produce 262 // a pair for each. Skip any variables that do not have corresponding 263 // variables in the parent. 264 for (int j = 0; j < varr.length; j++) { 265 VarInfo v1 = parentVar(varr[j]); 266 if (v1 == null) { 267 debug.fine("-- -- " + varr[j].name() + " not in parent (skip)"); 268 continue; 269 } 270 for (int k = j + 1; k < varr.length; k++) { 271 VarInfo v2 = parentVar(varr[k]); 272 if (v2 == null) { 273 debug.fine("-- -- " + varr[k].name() + " not in parent (skip)"); 274 continue; 275 } 276 VarInfo.Pair parent_pair = new VarInfo.Pair(v1, v2, e.numSamples()); 277 emap.put(parent_pair, parent_pair); 278 if (debug.isLoggable(Level.FINE)) { 279 debug.fine( 280 "-- -- " 281 + varr[j].name() 282 + ", " 283 + varr[k].name() 284 + " in child yield " 285 + parent_pair 286 + " in parent"); 287 } 288 } 289 } 290 } 291 return emap; 292 } 293 294 /** 295 * Relates parent_var to a variable in child that matches name. 296 * 297 * @param parent_var the parent variable being matched 298 * @param viname the name to look for in child variables 299 * @return true if there was a matching variable, false otherwise 300 */ 301 private boolean relate(VarInfo parent_var, String viname) { 302 303 for (VarInfo vc : child.var_infos) { 304 if (viname.equals(vc.name())) { 305 child_to_parent_map.put(vc, parent_var); 306 parent_to_child_map.put(parent_var, vc); 307 return true; 308 } 309 } 310 return false; 311 } 312 313 /** 314 * Returns a relation in the ppt hierarchy from an object (parent) to a method (child) on that 315 * object. 316 */ 317 public static PptRelation newObjectMethodRel(PptTopLevel parent, PptTopLevel child) { 318 319 assert (parent != null) && (child != null); 320 321 PptRelation rel = new PptRelation(parent, child, PptRelationType.PARENT); 322 323 debug.fine(parent.name() + " parent vars = " + Arrays.toString(parent.var_infos)); 324 debug.fine(child.name() + " child vars = " + Arrays.toString(child.var_infos)); 325 326 // Connect each 'this' variable between parent and child. 327 // Note that these should be the only variables whose names match and 328 // that each parent variable should match one in the child. 329 boolean relate_all = rel.relate_same_name(); 330 assert relate_all; 331 return rel; 332 } 333 334 /** 335 * Returns a relation in the ppt hierarchy from a class (parent) to an object (child) containing 336 * static members of that class. 337 */ 338 public static PptRelation newClassObjectRel(PptTopLevel parent, PptTopLevel child) { 339 340 assert (parent != null) && (child != null); 341 342 PptRelation rel = new PptRelation(parent, child, PptRelationType.PARENT); 343 344 // Connect each static variable between parent and child 345 // Note that these should be the only variables whose names match 346 rel.relate_same_name(); 347 return rel; 348 } 349 350 /** 351 * Creates a USER or PARENT relation from child to parent. The variable relationships are 352 * specified in the declaration record and stored in the VarInfo for each variable. 353 * RuntimeException will be thrown if any of the parent variables cannot be found. 354 */ 355 public static PptRelation newParentRelation( 356 ParentRelation pr, PptTopLevel parent, PptTopLevel child) { 357 358 assert pr != null && parent != null && child != null; 359 // System.out.printf("Parent Relation %s[%d] to %s%n", pr.parent_ppt_name, 360 // pr.id, child.name()); 361 362 PptRelation rel = new PptRelation(parent, child, pr.rel_type); 363 for (VarInfo vc : child.var_infos) { 364 for (VarParent pi : vc.parents) { 365 // System.out.printf("--child variable %s, ppt %s[%d], parent_var %s%n", 366 // vc.name(), pi.parent_ppt, pi.parent_relation_id, 367 // pi.parent_variable); 368 if (pi.parent_relation_id != pr.id) { 369 continue; 370 } 371 372 // Get the name of the parent variable. Its the same as this one if 373 // not specified. For now, remove the array placeholder (..) since 374 // VarInfoName doesn't support it. 375 String parent_name = pi.parent_variable; 376 if (parent_name == null) { 377 parent_name = vc.name(); 378 } 379 // parent_name = parent_name.replace ("[..]", "[]"); 380 381 // System.out.printf("---parent name %s%n", parent_name); 382 VarInfo vp = parent.find_var_by_name(parent_name); 383 if (vp == null) { 384 throw new RuntimeException( 385 String.format( 386 "Can't find parent variable '%s' in ppt '%s', " 387 + "with vars %s specified by var '%s' in ppt '%s'", 388 parent_name, pi.parent_ppt, parent.var_names(), vc.name(), child.name())); 389 } 390 rel.child_to_parent_map.put(vc, vp); 391 rel.parent_to_child_map.put(vp, vc); 392 } 393 } 394 return rel; 395 } 396 397 /** 398 * Returns a relation in the ppt hierarchy from an object (parent) to a user (child) of that 399 * objects (eg, from the object B to the method A.foo (B arg)). 400 * 401 * @param parent ppt of the object definition 402 * @param child ppt of a user of parent's object 403 * @param arg variable of type object found in child 404 */ 405 public static PptRelation newObjectUserRel(PptTopLevel parent, PptTopLevel child, VarInfo arg) { 406 407 assert (parent != null) && (child != null); 408 409 PptRelation rel = new PptRelation(parent, child, PptRelationType.USER); 410 411 // Connect each each field in arg between parent and child. Do this 412 // by substituting args name for this in the parent and then looking 413 // for a name match in the child 414 for (VarInfo vp : parent.var_infos) { 415 rel.relate(vp, vp.replace_this(arg)); 416 } 417 return rel; 418 } 419 420 /** 421 * Returns a relation in the ppt hierarchy from enter points to exit points over orig variables. 422 */ 423 public static PptRelation newEnterExitRel(PptTopLevel parent, PptTopLevel child) { 424 425 assert (parent != null) && (child != null); 426 427 PptRelation rel = new PptRelation(parent, child, PptRelationType.ENTER_EXIT); 428 429 // Look for orig versions of each non-derived parent variable in the child 430 // Note that static constants don't have orig versions (since they are 431 // known to be the same), so we connect to the post version instead. 432 for (VarInfo vp : parent.var_infos) { 433 if (vp.derived != null) { 434 continue; 435 } 436 if (vp.isStaticConstant()) { 437 @SuppressWarnings("UnusedVariable") // see comment below 438 boolean found = rel.relate(vp, vp.name()); 439 // Static constants are not always placed at each level in hierarchy 440 // (due to mutually recursive constants that contain one another as 441 // fields). 442 // assert found; 443 } else { 444 // VarInfoName orig_name = vp.name.applyPrestate().intern(); 445 boolean found = rel.relate(vp, vp.prestate_name()); 446 assert found 447 : String.format( 448 "vp %s orig_name %s parent %s child %s with vars %s", 449 vp, vp.prestate_name(), parent.name(), child.name(), child.var_names()); 450 } 451 } 452 453 // Look for orig versions of derived variables in the child. This is 454 // done by finding the base of each derived variable and looking for 455 // a child variable with the same bases and the same equation. This 456 // is necessary because derivations are done AFTER orig variables so 457 // applying the prestate name (as done above) won't work (the resulting 458 // variable is really the same but the name is constructed differently). 459 460 // Loop through each derived parent (ENTER) variable 461 for (VarInfo vp : parent.var_infos) { 462 if (vp.derived == null) { 463 continue; 464 } 465 466 // Get a child version of each of the bases of the derivation 467 VarInfo[] vp_bases = vp.derived.getBases(); 468 // TODO: Is this "@Nullable" annotation correct? (That is, can the 469 // element value actually be null?) 470 @Nullable VarInfo[] child_vp_bases = new VarInfo[vp_bases.length]; 471 for (int j = 0; j < vp_bases.length; j++) { 472 child_vp_bases[j] = rel.childVar(vp_bases[j]); 473 } 474 475 // Loop through the child (exit) looking for a matching derived variable 476 for (VarInfo vc : child.var_infos) { 477 if (vc.derived == null) { 478 continue; 479 } 480 if (vc.derived.isSameFormula(vp.derived)) { 481 assert vc.derived != null; 482 VarInfo[] vc_bases = vc.derived.getBases(); 483 if (Arrays.equals(child_vp_bases, vc_bases)) { 484 rel.child_to_parent_map.put(vc, vp); 485 rel.parent_to_child_map.put(vp, vc); 486 break; 487 } 488 } 489 } 490 } 491 492 // Make sure every non-static ENTER variable was found in the EXIT point 493 boolean all_found = true; 494 for (VarInfo vp : parent.var_infos) { 495 if (vp.isStaticConstant()) { 496 continue; 497 } 498 if (!rel.parent_to_child_map.containsKey(vp)) { 499 if (all_found) { 500 System.out.printf( 501 "missing variables in newEnterExitRel:%n" 502 + " parent = %s%n" 503 + " child = %s%n" 504 + " parent.var_infos = %s%n" 505 + "parent varinfos missing from parent_to_child_map:%n", 506 parent.name(), child.name(), parent.var_infos); 507 all_found = false; 508 } 509 System.out.printf(" %s%n", vp.name()); 510 } 511 } 512 if (!all_found) { 513 System.out.printf("rel.parent_to_child_map:%n"); 514 for (Map.Entry<VarInfo, VarInfo> entry : rel.parent_to_child_map.entrySet()) { 515 System.out.printf(" %s => %s%n", entry.getKey(), entry.getValue()); 516 } 517 System.out.printf("child.var_infos:%n"); 518 for (VarInfo vc : child.var_infos) { 519 System.out.println(" " + vc.name()); 520 } 521 System.out.printf( 522 "End of diagnostics for newEnterExitRel(%s, %s)%n", parent.name(), child.name()); 523 // throw new Error("Missing orig variable in EXIT"); 524 } 525 return rel; 526 } 527 528 /** 529 * Returns a relation in the ppt hierarchy from combined exit points (parent) to an individual 530 * exit point (child). Individual exit points are often referred to as exitNN where NN is the line 531 * number of the exit point). 532 */ 533 public static PptRelation newCombinedExitExitNNRel(PptTopLevel parent, PptTopLevel child) { 534 535 assert (parent != null) && (child != null); 536 537 PptRelation rel = new PptRelation(parent, child, PptRelationType.EXIT_EXITNN); 538 539 // Create the parent-child variable map. This one is easy as the 540 // variables should match exactly 541 assert parent.var_infos.length == child.var_infos.length; 542 for (int i = 0; i < parent.var_infos.length; i++) { 543 VarInfo vc = child.var_infos[i]; 544 VarInfo vp = parent.var_infos[i]; 545 assert vc.name().equals(vp.name()); 546 rel.child_to_parent_map.put(vc, vp); 547 rel.parent_to_child_map.put(vp, vc); 548 } 549 return rel; 550 } 551 552 /** Returns a relation in the ppt hierarchy from a ppt to a PptConditional for that point. */ 553 public static PptRelation newPptPptConditional(PptTopLevel parent, PptTopLevel child) { 554 555 assert (parent != null) && (child != null); 556 557 PptRelation rel = new PptRelation(parent, child, PptRelationType.PPT_PPTCOND); 558 559 // Create the parent-child variable map. This one is easy as the 560 // variables should match exactly 561 assert parent.var_infos.length == child.var_infos.length; 562 for (int i = 0; i < parent.var_infos.length; i++) { 563 VarInfo vc = child.var_infos[i]; 564 VarInfo vp = parent.var_infos[i]; 565 assert vc.name().equals(vp.name()); 566 rel.child_to_parent_map.put(vc, vp); 567 rel.parent_to_child_map.put(vp, vc); 568 } 569 return rel; 570 } 571 572 /** 573 * Returns a an artificial relation in the Program point hierarchy between the same ppt in two 574 * different PptMaps. Used to merge invariants between different data sets. The parent and the 575 * child should have exactly the same variables. 576 */ 577 public static PptRelation newMergeChildRel(PptTopLevel parent, PptTopLevel child) { 578 579 assert (parent != null) && (child != null); 580 581 PptRelation rel = new PptRelation(parent, child, PptRelationType.MERGE_CHILD); 582 583 // assert that parent vars match child vars 584 if (parent.var_infos.length != child.var_infos.length) { 585 System.out.println("newMergeChildRel: in ppt " + parent.name() + " vars don't match"); 586 System.out.println("parent vars= " + Arrays.toString(parent.var_infos)); 587 System.out.println("child vars= " + Arrays.toString(child.var_infos)); 588 assert parent.var_infos.length == child.var_infos.length; 589 } 590 591 // Create the parent-child variable map. This one is easy as the 592 // variables should match exactly 593 for (int i = 0; i < parent.var_infos.length; i++) { 594 VarInfo vc = child.var_infos[i]; 595 VarInfo vp = parent.var_infos[i]; 596 if (!vc.name().equals(vp.name())) { 597 System.out.println( 598 "newMergeChildRel: in ppt " + parent.name() + " var " + vc.name() + " doesn't match"); 599 System.out.println("par vars = " + Arrays.toString(parent.var_infos)); 600 System.out.println("child vars= " + Arrays.toString(child.var_infos)); 601 assert vc.name().equals(vp.name()); 602 } 603 rel.child_to_parent_map.put(vc, vp); 604 rel.parent_to_child_map.put(vp, vc); 605 } 606 return rel; 607 } 608 609 /** 610 * Copies the relation from its current ppts to the specified ppts. The new ppts must have the 611 * same variables in the same order as do the original ones. 612 */ 613 public PptRelation copy(PptTopLevel new_parent, PptTopLevel new_child) { 614 615 PptRelation rel = new PptRelation(new_parent, new_child, relationship); 616 for (VarInfo vc : child_to_parent_map.keySet()) { 617 VarInfo vp = child_to_parent_map.get(vc); 618 VarInfo new_vc = new_child.var_infos[vc.varinfo_index]; 619 VarInfo new_vp = new_parent.var_infos[vp.varinfo_index]; 620 assert new_vc.name().equals(vc.name()); 621 assert new_vp.name().equals(vp.name()); 622 rel.child_to_parent_map.put(new_vc, new_vp); 623 rel.parent_to_child_map.put(new_vp, new_vc); 624 } 625 return rel; 626 } 627 628 // used by init_hierarchy below 629 private static class SplitChild { 630 public PptRelation rel; 631 public PptSplitter ppt_split; 632 633 public SplitChild(PptRelation rel, PptSplitter ppt_split) { 634 this.rel = rel; 635 this.ppt_split = ppt_split; 636 } 637 } 638 639 /** 640 * Initialize the hierarchical relationship between ppts. Specifically process each ppt, find its 641 * parent(s) in the partial order, and fill this point into the children field in the parent. Note 642 * that children contains only the immediate descendants of the ppt. 643 * 644 * <p>This version should be used with the old version of declaration records. Use 645 * init_hierarchy_new() with new declaration records. 646 */ 647 public static void init_hierarchy(PptMap all_ppts) { 648 649 for (PptTopLevel ppt : all_ppts.pptIterable()) { 650 PptName pname = ppt.ppt_name; 651 PptRelation rel = null; 652 Daikon.debugProgress.fine("Processing ppt " + pname); 653 debug.fine("Processing ppt " + pname); 654 655 // If this is an object ppt, parent is the class point 656 if (pname.isObjectInstanceSynthetic()) { 657 PptTopLevel parent = all_ppts.get(pname.makeClassStatic()); 658 if (parent != null) { 659 rel = newClassObjectRel(parent, ppt); 660 } 661 662 // Else if it's a method and not a constructor, parent is 663 // object or class static methods will relate to the class, 664 // while non-static methods will relate to the object. 665 // Whether or not a method is static is not in the decls file. 666 // We infer this by looking to see if the variables match with 667 // the object ppt or the class ppt. 668 } else if ((pname.isEnterPoint() && !pname.isConstructor()) || pname.isCombinedExitPoint()) { 669 670 PptTopLevel parent = all_ppts.get(pname.makeObject()); 671 672 if (parent != null) { 673 if (ppt.find_var_by_name(parent.var_infos[0].name()) != null) { 674 rel = newObjectMethodRel(parent, ppt); 675 } else { 676 parent = all_ppts.get(parent.ppt_name.makeClassStatic()); 677 if (parent != null) { 678 rel = newObjectMethodRel(parent, ppt); 679 } 680 } 681 } 682 683 // Else if an exitNN point, parent is combined exit point 684 } else if (pname.isExitPoint()) { 685 PptTopLevel parent = all_ppts.get(pname.makeExit()); 686 // System.out.printf("Parent of %s is %s%n", pname.name(), 687 // parent.name()); 688 if (parent != null) { 689 rel = newCombinedExitExitNNRel(parent, ppt); 690 } 691 } 692 693 // If a relation was created, connect it into its ppts 694 if (rel != null) { 695 debug.fine( 696 "-- ppt parent is " 697 + rel.parent.name() 698 + " with connections [" 699 + rel.parent_to_child_var_string() 700 + "]"); 701 } else { 702 debug.fine(" -- no ppt parent"); 703 } 704 705 // Connect combined exit points to enter points over orig variables 706 if (pname.isCombinedExitPoint()) { 707 PptTopLevel enter = all_ppts.get(pname.makeEnter()); 708 if (enter != null) { 709 rel = PptRelation.newEnterExitRel(enter, ppt); 710 debug.fine( 711 " -- exit to enter " 712 + enter.name 713 + " with connections [" 714 + rel.parent_to_child_var_string() 715 + "]"); 716 } else { 717 debug.fine("-- No matching enter for exit"); 718 } 719 } 720 721 // For all points, look for vars of a declared type for which we have 722 // a corresponding OBJECT ppt. Essentially these are all of the 723 // users of the object. Don't match if the variable already has 724 // a parent (since the parent will provide the link back to the 725 // object) For each variable of this type that we find, setup a 726 // parent-child relationship with its corresponding OBJECT 727 // variables. 728 // 729 // For example, consider class A with fields x and y and method 730 // B.foo (A arg1, A arg2). We will setup two relations to this 731 // ppt -- one from A to b.foo.arg1 and one from A to b.foo.arg2. 732 // in each we will equate A.x with arg.x and A.y with arg.y. 733 // 734 // We skip variables named exactly 'this' so that we don't setup a 735 // recursive relationship from the object to itself. 736 737 // DaikonSimple can not see these relations, so don't create them 738 // if we'll be comparing to DaikonSimple. 739 if (dkconfig_enable_object_user) { 740 741 debug.fine("-- Looking for variables with an OBJECT ppt"); 742 for (VarInfo vc : ppt.var_infos) { 743 String dstr = "-- -- var '" + vc.name() + "' - "; 744 if (ppt.has_parent(vc)) { 745 debug.fine(dstr + " Skipping, already has a parent"); 746 continue; 747 } 748 if (vc.isThis()) { 749 debug.fine(dstr + " skipping, name is 'this'"); 750 continue; 751 } 752 PptTopLevel object_ppt = vc.find_object_ppt(all_ppts); 753 if (object_ppt != null) { 754 if (object_ppt == ppt) { 755 debug.fine(dstr + " skipping, OBJECT (" + object_ppt + ") is the same as this"); 756 continue; 757 } 758 rel = PptRelation.newObjectUserRel(object_ppt, ppt, vc); 759 debug.fine( 760 dstr 761 + " Connected to Object ppt " 762 + object_ppt.name() 763 + " with connections [" 764 + rel.parent_to_child_var_string() 765 + "]"); 766 } else { 767 debug.fine(dstr + " No object ppt"); 768 } 769 } 770 } 771 // Connect any conditional ppt variables. Only connect to the 772 // first splitter, since each splitter should yield the same 773 // results at the parent (since each splitter sees the same 774 // points) This should only happen at the leaves (numbered 775 // exit points) since all other points should be built from 776 // their other children. But since we need the relation 777 // from the child's point of view when printing, we create 778 // under all cases and then remove it from non-leaves children 779 // list. This doesn't seem like the best solution. 780 if (ppt.has_splitters()) { 781 assert ppt.splitters != null; // guaranteed by call to has_splitters 782 PptSplitter ppt_split = ppt.splitters.get(0); 783 for (int ii = 0; ii < ppt_split.ppts.length; ii++) { 784 rel = newPptPptConditional(ppt, ppt_split.ppts[ii]); 785 debug.fine( 786 " -- Connected down to ppt conditional " 787 + ppt_split.ppts[ii].name() 788 + " with connections [" 789 + rel.parent_to_child_var_string() 790 + "]"); 791 if (!ppt.ppt_name.isNumberedExitPoint()) { 792 ppt.children.remove(rel); 793 } 794 } 795 } 796 } 797 798 // Create relations between conditional ppts and their children. 799 // The relationship between conditional ppts matches exactly 800 // the relationship between each their parents. For example, 801 // presume ppt A has a child ppt B. A has two conditional 802 // ppts (AC1, AC2) and B has two conditional ppts (BC1, BC2) 803 // Then AC1 is the parent of BC1 and AC2 is the parent of BC2 804 805 // Loop over each ppt and process each non-leaf with splitters 806 for (PptTopLevel ppt : all_ppts.pptIterable()) { 807 if (ppt.ppt_name.isNumberedExitPoint()) { 808 continue; 809 } 810 if (!ppt.has_splitters()) { 811 continue; 812 } 813 814 // System.out.printf("processing splitter '%s' [%s] %b%n", ppt.name(), 815 // ppt.ppt_name.getPoint(), 816 // ppt.ppt_name.isNumberedExitPoint()); 817 818 // Loop over each splitter 819 // splitter_loop: 820 for (Iterator<PptSplitter> ii = ppt.splitters.iterator(); ii.hasNext(); ) { 821 PptSplitter ppt_split = ii.next(); 822 823 // list of children that match this splitter 824 List<SplitChild> split_children = new ArrayList<>(); 825 826 // Create a list of children for this splitter 827 child_loop: 828 for (PptRelation rel : ppt.children) { 829 if (!rel.child.has_splitters()) { 830 break; 831 } 832 for (PptSplitter csplit : rel.child.splitters) { 833 if (ppt_split.splitter == csplit.splitter) { 834 split_children.add(new SplitChild(rel, csplit)); 835 continue child_loop; 836 } 837 } 838 break; 839 } 840 841 // If we didn't find a matching splitter at each child, can't merge 842 // this point. Just remove it from the list of splitters 843 if (split_children.size() != ppt.children.size()) { 844 ii.remove(); 845 continue; 846 } 847 848 // Build the PptRelations for each child. The PptRelation from 849 // the conditional point is of the same type as the original 850 // relation from parent to child 851 for (SplitChild sc : split_children) { 852 ppt_split.add_relation(sc.rel, sc.ppt_split); 853 } 854 } 855 } 856 857 // Debug print the hierarchy in a more readable manner 858 if (debug.isLoggable(Level.FINE)) { 859 debug.fine("PPT Hierarchy"); 860 for (PptTopLevel ppt : all_ppts.pptIterable()) { 861 if (ppt.parents.size() == 0) { 862 ppt.debug_print_tree(debug, 0, null); 863 } 864 } 865 } 866 867 // Debug print the equality sets for each ppt 868 if (debug.isLoggable(Level.FINE)) { 869 for (PptTopLevel ppt : all_ppts.pptIterable()) { 870 debug.fine(ppt.name() + " equality sets: " + ppt.equality_sets_txt()); 871 } 872 } 873 } 874 875 /** 876 * Initialize the hierarchical relationship between ppts. Specifically process each ppt, find its 877 * parent(s) in the partial order, and fill this point into the children field in the parent. Note 878 * that children contains only the immediate descendants of the ppt. 879 */ 880 public static void init_hierarchy_new(PptMap all_ppts) { 881 882 for (PptTopLevel ppt : all_ppts.pptIterable()) { 883 PptName pname = ppt.ppt_name; 884 // rels is solely for debugging; each relation is stored in the 885 // parent and child ppts 886 List<PptRelation> rels = new ArrayList<>(); 887 Daikon.debugProgress.finer("Processing ppt " + pname); 888 debug.fine("Processing ppt " + pname); 889 890 assert ppt.parent_relations != null : "missing parent_relations in ppt " + ppt.name(); 891 892 // Process the front-end specified relations 893 for (ParentRelation pr : ppt.parent_relations) { 894 // Skip all relations in subexits. These relations will be handled 895 // in the combined exit point. 896 if (ppt.is_subexit()) { 897 continue; 898 } 899 900 PptTopLevel parent = all_ppts.get(pr.parent_ppt_name); 901 if (parent == null) { 902 throw new RuntimeException( 903 "parent ppt " + pr.parent_ppt_name + " not found for ppt " + ppt.name()); 904 } 905 if ((pr.rel_type == PptRelationType.USER) && !dkconfig_enable_object_user) { 906 continue; 907 } 908 // System.out.printf("processing hierarchy rel from '%s' to '%s'%n", 909 // ppt.name(), pr.parent_ppt_name); 910 rels.add(newParentRelation(pr, parent, ppt)); 911 } 912 913 // if an exitNN point, parent is combined exit point 914 if (ppt.is_subexit()) { 915 PptTopLevel parent = all_ppts.get(pname.makeExit()); 916 if (parent != null) { 917 rels.add(newCombinedExitExitNNRel(parent, ppt)); 918 } 919 920 // Connect combined exit points to enter points over orig variables 921 } else if (ppt.is_combined_exit()) { 922 PptTopLevel enter = all_ppts.get(pname.makeEnter()); 923 if (enter != null) { 924 rels.add(PptRelation.newEnterExitRel(enter, ppt)); 925 } 926 } 927 928 // Connect any conditional ppt variables. Only connect to the 929 // first splitter, since each splitter should yield the same 930 // results at the parent (since each splitter sees the same 931 // points) This should only happen at the leaves (numbered 932 // exit points) since all other points should be built from 933 // their other children. But since we need the relation 934 // from the child's point of view when printing, we create 935 // under all cases and then remove it from non-leaves children 936 // list. This doesn't seem like the best solution. 937 if (ppt.has_splitters()) { 938 assert ppt.splitters != null; // guaranteed by call to has_splitters 939 PptSplitter ppt_split = ppt.splitters.get(0); 940 for (int ii = 0; ii < ppt_split.ppts.length; ii++) { 941 PptRelation rel = newPptPptConditional(ppt, ppt_split.ppts[ii]); 942 rels.add(rel); 943 if (!ppt.is_subexit()) { 944 ppt.children.remove(rel); 945 } 946 } 947 } 948 // Debug print the created relations 949 for (PptRelation rel : rels) { 950 debug.fine( 951 "-- ppt parent is " 952 + rel.parent.name() 953 + " with connections [" 954 + rel.parent_to_child_var_string() 955 + "]"); 956 } 957 } 958 959 // Create relations between conditional ppts and their children. 960 // The relationship between conditional ppts matches exactly 961 // the relationship between each their parents. For example, 962 // presume ppt A has a child ppt B. A has two conditional 963 // ppts (AC1, AC2) and B has two conditional ppts (BC1, BC2) 964 // Then AC1 is the parent of BC1 and AC2 is the parent of BC2 965 966 // Loop over each ppt and process each non-leaf with splitters 967 for (PptTopLevel ppt : all_ppts.pptIterable()) { 968 if (ppt.is_subexit()) { 969 continue; 970 } 971 if (!ppt.has_splitters()) { 972 continue; 973 } 974 975 // System.out.printf("processing splitter %s%n", ppt.name()); 976 977 // Loop over each splitter 978 // splitter_loop: 979 for (Iterator<PptSplitter> ii = ppt.splitters.iterator(); ii.hasNext(); ) { 980 PptSplitter ppt_split = ii.next(); 981 982 // list of children that match this splitter 983 List<SplitChild> split_children = new ArrayList<>(); 984 985 // Create a list of children for this splitter 986 child_loop: 987 for (PptRelation rel : ppt.children) { 988 if (!rel.child.has_splitters()) { 989 break; 990 } 991 for (PptSplitter csplit : rel.child.splitters) { 992 if (ppt_split.splitter == csplit.splitter) { 993 split_children.add(new SplitChild(rel, csplit)); 994 continue child_loop; 995 } 996 } 997 break; 998 } 999 1000 // If we didn't find a matching splitter at each child, can't merge 1001 // this point. Just remove it from the list of splitters 1002 if (split_children.size() != ppt.children.size()) { 1003 ii.remove(); 1004 continue; 1005 } 1006 1007 // Build the PptRelations for each child. The PptRelation from 1008 // the conditional point is of the same type as the original 1009 // relation from parent to child 1010 for (SplitChild sc : split_children) { 1011 ppt_split.add_relation(sc.rel, sc.ppt_split); 1012 } 1013 } 1014 } 1015 1016 // Loop over each ppt and create an equality view and invariants for 1017 // any ppt without children that doesn't already have them. This can 1018 // happen when there are ppts such as OBJECT or CLASS that don't end up 1019 // with any children (due to the program source or because of ppt filtering). 1020 for (PptTopLevel ppt : all_ppts.pptIterable()) { 1021 if ((ppt.children.size() == 0) && (ppt.equality_view == null)) { 1022 assert ppt.is_object() || ppt.is_class() || ppt.is_enter() : ppt; 1023 ppt.equality_view = new PptSliceEquality(ppt); 1024 ppt.equality_view.instantiate_invariants(); 1025 } 1026 } 1027 1028 // Debug print the hierarchy in a more readable manner 1029 if (debug.isLoggable(Level.FINE)) { 1030 debug.fine("PPT Hierarchy"); 1031 for (PptTopLevel ppt : all_ppts.pptIterable()) { 1032 if (ppt.parents.size() == 0) { 1033 ppt.debug_print_tree(debug, 0, null); 1034 } 1035 } 1036 } 1037 1038 // Debug print the equality sets for each ppt 1039 if (debug.isLoggable(Level.FINE)) { 1040 for (PptTopLevel ppt : all_ppts.pptIterable()) { 1041 debug.fine(ppt.name() + " equality sets: " + ppt.equality_sets_txt()); 1042 } 1043 } 1044 } 1045}