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