Robust/src/Analysis/SSJava/BuildLattice.java

   1 package Analysis.SSJava;
   2
   3 import java.util.HashMap;
   4 import java.util.HashSet;
   5 import java.util.Iterator;
   6 import java.util.Map;
   7 import java.util.Set;
   8
   9 import IR.ClassDescriptor;
  10 import IR.Descriptor;
  11 import IR.MethodDescriptor;
  12 import IR.NameDescriptor;
  13 import Util.Pair;
  14
  15 public class BuildLattice {
  16
  17   private LocationInference infer;
  18   private Map<HNode, TripleItem> mapSharedNodeToTripleItem;
  19   private Map<HNode, Integer> mapHNodeToHighestIndex;
  20
  21   private Map<Descriptor, Map<TripleItem, String>> mapDescToIntermediateLocMap;
  22
  23   private Map<Pair<HNode, HNode>, Integer> mapItemToHighestIndex;
  24
  25   private Map<SSJavaLattice<String>, Set<String>> mapLatticeToLocalLocSet;
  26
  27   public BuildLattice(LocationInference infer) {
  28     this.infer = infer;
  29     this.mapSharedNodeToTripleItem = new HashMap<HNode, TripleItem>();
  30     this.mapHNodeToHighestIndex = new HashMap<HNode, Integer>();
  31     this.mapItemToHighestIndex = new HashMap<Pair<HNode, HNode>, Integer>();
  32     this.mapDescToIntermediateLocMap = new HashMap<Descriptor, Map<TripleItem, String>>();
  33     this.mapLatticeToLocalLocSet = new HashMap<SSJavaLattice<String>, Set<String>>();
  34   }
  35
  36   public SSJavaLattice<String> buildLattice(Descriptor desc) {
  37
  38     HierarchyGraph inputGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
  39     LocationSummary locSummary = infer.getLocationSummary(desc);
  40
  41     HierarchyGraph naiveGraph = infer.getSimpleHierarchyGraph(desc);
  42
  43     // I don't think we need to keep the below if statement anymore
  44     // because hierarchy graph does not have any composite location
  45     Set<HNode> nodeSetWithCompositeLocation = new HashSet<HNode>();
  46     if (desc instanceof MethodDescriptor) {
  47       FlowGraph flowGraph = infer.getFlowGraph((MethodDescriptor) desc);
  48
  49       for (Iterator iterator = inputGraph.getNodeSet().iterator(); iterator.hasNext();) {
  50         HNode hnode = (HNode) iterator.next();
  51         Descriptor hnodeDesc = hnode.getDescriptor();
  52         if (hnodeDesc != null) {
  53           NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
  54           descTuple.add(hnodeDesc);
  55
  56           if (flowGraph.contains(descTuple)) {
  57             FlowNode flowNode = flowGraph.getFlowNode(descTuple);
  58             if (flowNode.getCompositeLocation() != null) {
  59               nodeSetWithCompositeLocation.add(hnode);
  60             }
  61           }
  62
  63         }
  64       }
  65
  66     }
  67
  68     // /////////////////////////////////////////////////////////////////////////////////////
  69     // lattice generation for the native approach
  70
  71     if (infer.state.SSJAVA_INFER_NAIVE_WRITEDOTS) {
  72       BasisSet naiveBasisSet = naiveGraph.computeBasisSet(nodeSetWithCompositeLocation);
  73
  74       Family naiveFamily = generateFamily(naiveBasisSet);
  75       Map<Set<Integer>, Set<Set<Integer>>> naive_mapImSucc =
  76           coveringGraph(naiveBasisSet, naiveFamily);
  77
  78       SSJavaLattice<String> naive_lattice =
  79           buildLattice(desc, naiveBasisSet, naiveGraph, null, naive_mapImSucc);
  80       LocationInference.numLocationsNaive += naive_lattice.getKeySet().size();
  81       infer.addNaiveLattice(desc, naive_lattice);
  82     }
  83
  84     // /////////////////////////////////////////////////////////////////////////////////////
  85
  86     // lattice generation for the proposed approach
  87     BasisSet basisSet = inputGraph.computeBasisSet(nodeSetWithCompositeLocation);
  88     // debug_print(inputGraph);
  89
  90     Family family = generateFamily(basisSet);
  91     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = coveringGraph(basisSet, family);
  92
  93     SSJavaLattice<String> lattice = buildLattice(desc, basisSet, inputGraph, locSummary, mapImSucc);
  94     return lattice;
  95
  96   }
  97
  98   public void setIntermediateLocMap(Descriptor desc, Map<TripleItem, String> map) {
  99     mapDescToIntermediateLocMap.put(desc, map);
 100   }
 101
 102   public Map<TripleItem, String> getIntermediateLocMap(Descriptor desc) {
 103     if (!mapDescToIntermediateLocMap.containsKey(desc)) {
 104       mapDescToIntermediateLocMap.put(desc, new HashMap<TripleItem, String>());
 105     }
 106     return mapDescToIntermediateLocMap.get(desc);
 107   }
 108
 109   private Descriptor getParent(Descriptor desc) {
 110     if (desc instanceof MethodDescriptor) {
 111       MethodDescriptor md = (MethodDescriptor) desc;
 112       ClassDescriptor cd = md.getClassDesc();
 113       return infer.getParentMethodDesc(cd, md);
 114     } else {
 115       return ((ClassDescriptor) desc).getSuperDesc();
 116     }
 117   }
 118
 119   private SSJavaLattice<String> buildLattice(Descriptor desc, BasisSet basisSet,
 120       HierarchyGraph inputGraph, LocationSummary locSummary,
 121       Map<Set<Integer>, Set<Set<Integer>>> mapImSucc) {
 122
 123     System.out.println("\nBuild Lattice:" + inputGraph.getName());
 124
 125     SSJavaLattice<String> lattice =
 126         new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
 127
 128     Map<Set<Integer>, String> mapFToLocName = new HashMap<Set<Integer>, String>();
 129
 130     Set<Set<Integer>> keySet = mapImSucc.keySet();
 131     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 132       Set<Integer> higher = (Set<Integer>) iterator.next();
 133
 134       String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher);
 135
 136       HNode higherNode = inputGraph.getHNode(higherName);
 137
 138       if (higherNode == null) {
 139         NameDescriptor d = new NameDescriptor(higherName);
 140         higherNode = inputGraph.getHNode(d);
 141         higherNode.setSkeleton(true);
 142       }
 143
 144       if (higherNode != null && higherNode.isSharedNode()) {
 145         lattice.addSharedLoc(higherName);
 146       }
 147       Set<Descriptor> descSet = inputGraph.getDescSetOfNode(higherNode);
 148       // System.out.println("higherName=" + higherName + "  higherNode=" + higherNode + "  descSet="
 149       // + descSet);
 150
 151       if (locSummary != null) {
 152         for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
 153           Descriptor d = (Descriptor) iterator2.next();
 154           locSummary.addMapHNodeNameToLocationName(d.getSymbol(), higherName);
 155         }
 156       }
 157
 158       // locSummary.addMapHNodeNameToLocationName(higherName, higherName);
 159
 160       Set<Set<Integer>> lowerSet = mapImSucc.get(higher);
 161       for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
 162         Set<Integer> lower = (Set<Integer>) iterator2.next();
 163
 164         String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower);
 165         HNode lowerNode = inputGraph.getHNode(lowerName);
 166
 167         if (lowerNode == null && !lowerName.equals(SSJavaAnalysis.BOTTOM)) {
 168           NameDescriptor d = new NameDescriptor(lowerName);
 169           lowerNode = inputGraph.getHNode(d);
 170           lowerNode.setSkeleton(true);
 171         }
 172
 173         if (lowerNode != null && !inputGraph.isDirectlyConnectedTo(higherNode, lowerNode)) {
 174           inputGraph.addEdge(higherNode, lowerNode);
 175         }
 176
 177         if (lowerNode != null && lowerNode.isSharedNode()) {
 178           lattice.addSharedLoc(lowerName);
 179         }
 180
 181         Set<Descriptor> lowerDescSet = inputGraph.getDescSetOfNode(lowerNode);
 182         // System.out.println("lowerName=" + lowerName + "  lowerNode=" + lowerNode + "  descSet="
 183         // + lowerDescSet);
 184         if (locSummary != null) {
 185           for (Iterator iterator3 = lowerDescSet.iterator(); iterator3.hasNext();) {
 186             Descriptor d = (Descriptor) iterator3.next();
 187             locSummary.addMapHNodeNameToLocationName(d.getSymbol(), lowerName);
 188           }
 189         }
 190         // locSummary.addMapHNodeNameToLocationName(lowerName, lowerName);
 191
 192         if (higher.size() == 0) {
 193           // empty case
 194           lattice.put(lowerName);
 195         } else {
 196           lattice.addRelationHigherToLower(higherName, lowerName);
 197         }
 198
 199       }
 200
 201     }
 202
 203     inputGraph.removeRedundantEdges();
 204     return lattice;
 205   }
 206
 207   public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode nodeFromSimpleGraph) {
 208
 209     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 210
 211     if (nodeFromSimpleGraph.isSkeleton()) {
 212       return scGraph.getCurrentHNode(nodeFromSimpleGraph);
 213     }
 214
 215     Set<HNode> combineSkeletonNodeSet =
 216         infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(nodeFromSimpleGraph);
 217     HNode combinationNodeInSCGraph =
 218         infer.getSkeletonCombinationHierarchyGraph(desc).getMapCombineNodeSetToCombinationNode()
 219             .get(combineSkeletonNodeSet);
 220
 221     // Set<HNode> combineSkeletonNodeSet =
 222     // infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode);
 223     // HNode combinationNodeInSCGraph =
 224     // infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet);
 225     return combinationNodeInSCGraph;
 226   }
 227
 228   public SSJavaLattice<String> insertIntermediateNodesToStraightLine(Descriptor desc,
 229       SSJavaLattice<String> skeletonLattice) {
 230
 231     SSJavaLattice<String> lattice = skeletonLattice.clone();
 232     LocationSummary locSummary = infer.getLocationSummary(desc);
 233
 234     Descriptor parentDesc = getParent(desc);
 235     if (parentDesc != null) {
 236       SSJavaLattice<String> parentLattice = infer.getLattice(parentDesc);
 237
 238       Map<String, Set<String>> parentMap = parentLattice.getTable();
 239       Set<String> parentKeySet = parentMap.keySet();
 240       for (Iterator iterator = parentKeySet.iterator(); iterator.hasNext();) {
 241         String parentKey = (String) iterator.next();
 242         Set<String> parentValueSet = parentMap.get(parentKey);
 243         for (Iterator iterator2 = parentValueSet.iterator(); iterator2.hasNext();) {
 244           String value = (String) iterator2.next();
 245           lattice.put(parentKey, value);
 246         }
 247       }
 248
 249       Set<String> parentSharedLocSet = parentLattice.getSharedLocSet();
 250       for (Iterator iterator = parentSharedLocSet.iterator(); iterator.hasNext();) {
 251         String parentSharedLoc = (String) iterator.next();
 252         lattice.addSharedLoc(parentSharedLoc);
 253       }
 254     }
 255
 256     HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 257     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 258
 259     Set<HNode> hierarchyGraphNodeSet = hierarchyGraph.getNodeSet();
 260     for (Iterator iterator = hierarchyGraphNodeSet.iterator(); iterator.hasNext();) {
 261       HNode hNode = (HNode) iterator.next();
 262       if (!hNode.isSkeleton()) {
 263         // here we need to insert an intermediate node for the hNode
 264         System.out.println("\n#local node=" + hNode);
 265
 266         // 1) find the lowest node m in the lattice that is above hnode in the lattice
 267         // 2) count the number of non-shared nodes d between the hnode and the node m
 268         // int numNonSharedNodes;
 269         int dist;
 270
 271         HNode SCNode;
 272         if (hNode.isDirectCombinationNode()) {
 273           // this node itself is the lowest node m. it is the first node of the chain
 274           Set<HNode> combineSet = hierarchyGraph.getCombineSetByCombinationNode(hNode);
 275
 276           System.out.println("     # direct combine node::combineSkeletonNodeSet=" + combineSet);
 277
 278           SCNode = scGraph.getCombinationNode(combineSet);
 279           // numNonSharedNodes = -1;
 280           dist = 0;
 281         } else {
 282
 283           Set<HNode> aboveSet = new HashSet<HNode>();
 284           if (hNode.isCombinationNode()) {
 285             // the current node is a combination node
 286             Set<HNode> combineSkeletonNodeSet =
 287                 hierarchyGraph.getCombineSetByCombinationNode(hNode);
 288             System.out.println("     combineSkeletonNodeSet=" + combineSkeletonNodeSet
 289                 + " combinationNode=" + scGraph.getCombinationNode(combineSkeletonNodeSet));
 290
 291             scGraph.getCombinationNode(combineSkeletonNodeSet);
 292
 293             System.out.println("        firstnodeOfSimpleGraph="
 294                 + hierarchyGraph.getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet));
 295             aboveSet.addAll(hierarchyGraph
 296                 .getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet));
 297
 298             SCNode = scGraph.getCombinationNode(combineSkeletonNodeSet);
 299
 300           } else {
 301             // the current node is not a combination node
 302             // there is only one parent node which should be skeleton node.
 303
 304             System.out.println("   hierarchyGraph.getSkeleteNodeSetReachTo(" + hNode + ")="
 305                 + hierarchyGraph.getSkeleteNodeSetReachTo(hNode));
 306             aboveSet.addAll(hierarchyGraph.getSkeleteNodeSetReachTo(hNode));
 307             System.out.println("   aboveset of " + hNode + "=" + aboveSet);
 308             // assert aboveSet.size() == 1;
 309             SCNode = aboveSet.iterator().next();
 310           }
 311
 312           // update above set w.r.t the hierarchy graph with SC nodes
 313           // because the skeleton nodes in the origianl hierarchy graph may merged to a new node
 314           Set<HNode> endSet = new HashSet<HNode>();
 315           for (Iterator iterator2 = aboveSet.iterator(); iterator2.hasNext();) {
 316             HNode aboveNode = (HNode) iterator2.next();
 317             endSet.add(scGraph.getCurrentHNode(aboveNode));
 318           }
 319           dist = hierarchyGraph.computeDistance(hNode, endSet);
 320           System.out.println("##### " + hNode + "::dist=" + dist);
 321
 322           // numNonSharedNodes = hierarchyGraph.countNonSharedNode(hNode, endSet);
 323
 324           System.out.println("   COUNT-RESULT::node=" + hNode + " above=" + endSet + " distance="
 325               + dist + "   SCNode=" + SCNode);
 326         }
 327
 328         // 3) convert the node m into a chain of nodes with the last node in the chain having m’s
 329         // outgoing edges.
 330         Set<HNode> outgoingSCNodeSet = scGraph.getOutgoingNodeSet(SCNode);
 331         System.out.println("   outgoing scnode set from " + SCNode + "=" + outgoingSCNodeSet);
 332
 333         // convert hnodes to location names
 334         String startLocName = locSummary.getLocationName(SCNode.getName());
 335         Set<String> outgoingLocNameSet = new HashSet<String>();
 336         for (Iterator iterator2 = outgoingSCNodeSet.iterator(); iterator2.hasNext();) {
 337           HNode outSCNode = (HNode) iterator2.next();
 338           String locName = locSummary.getLocationName(outSCNode.getName());
 339           if (!locName.equals(outSCNode.getName())) {
 340             System.out.println("                         outSCNode=" + outSCNode + " -> locName="
 341                 + locName);
 342           }
 343           outgoingLocNameSet.add(locName);
 344         }
 345
 346         if (outgoingLocNameSet.isEmpty()) {
 347           outgoingLocNameSet.add(lattice.getBottomItem());
 348         }
 349
 350         // 4) If hnode is not a shared location, check if there already exists a local variable
 351         // node that has distance d below m along this chain. If such a node
 352         // does not exist, insert it.
 353         String locName =
 354             getNewLocation(lattice, startLocName, outgoingLocNameSet, dist, hNode.isSharedNode());
 355         System.out.println("       ###hNode=" + hNode + "---->locName=" + locName);
 356         locSummary.addMapHNodeNameToLocationName(hNode.getName(), locName);
 357
 358       }
 359     }
 360
 361     return lattice;
 362   }
 363
 364   private void addLocalLocation(SSJavaLattice<String> lattice, String localLoc) {
 365     if (!mapLatticeToLocalLocSet.containsKey(lattice)) {
 366       mapLatticeToLocalLocSet.put(lattice, new HashSet<String>());
 367     }
 368     mapLatticeToLocalLocSet.get(lattice).add(localLoc);
 369   }
 370
 371   private boolean isLocalLocation(SSJavaLattice<String> lattice, String localLoc) {
 372     if (mapLatticeToLocalLocSet.containsKey(lattice)) {
 373       return mapLatticeToLocalLocSet.get(lattice).contains(localLoc);
 374     }
 375     return false;
 376   }
 377
 378   public String getNewLocation(SSJavaLattice<String> lattice, String start, Set<String> endSet,
 379       int dist, boolean isShared) {
 380     System.out.println("       #GETNEWLOCATION:: start=" + start + "  endSet=" + endSet + " dist="
 381         + dist + " isShared=" + isShared);
 382     // if (dist == -1) {
 383     // if (isShared) {
 384     // // if the node is a shared one, check if the next node is shared
 385     // // if not, need to insert a new shared node
 386     // return recur_getNewLocation(lattice, start, endSet, dist + 1, isShared);
 387     // } else {
 388     // return start;
 389     // }
 390     //
 391     // }
 392     return recur_getNewLocation(lattice, start, start, endSet, dist, isShared);
 393   }
 394
 395   private String recur_getNewLocation(SSJavaLattice<String> lattice, String start, String cur,
 396       Set<String> endSet, int dist, boolean isShared) {
 397
 398     System.out.println("          recur_getNewLocation cur=" + cur + " dist=" + dist);
 399
 400     if (dist == 0) {
 401       if (isShared) {
 402         // first check if there already exists a non-shared node at distance d
 403         if (!isLocalLocation(lattice, cur) && !start.equals(cur)) {
 404           // if not, need to insert a new local location at this point
 405           System.out.println("if not, need to insert a new local location at this point");
 406           String newLocName = "ILOC" + (LocationInference.locSeed++);
 407           Set<String> lowerSet = new HashSet<String>();
 408           lowerSet.addAll(lattice.get(cur));
 409           lattice.insertNewLocationBetween(cur, lowerSet, newLocName);
 410           addLocalLocation(lattice, newLocName);
 411
 412           // assign the new local location to cur
 413           cur = newLocName;
 414         }
 415
 416         Set<String> connectedSet = lattice.get(cur);
 417         if (connectedSet == null) {
 418           connectedSet = new HashSet<String>();
 419         }
 420         System.out.println("cur=" + cur + "  connectedSet=" + connectedSet);
 421
 422         // check if there already exists a shared node that has distance d + 1 on the chain
 423         boolean needToInsertSharedNode = false;
 424         if (connectedSet.equals(endSet)) {
 425           needToInsertSharedNode = true;
 426         } else {
 427           // in this case, the current node is in the middle of the chain
 428           assert connectedSet.size() == 1;
 429           String below = connectedSet.iterator().next();
 430           if (lattice.isSharedLoc(below)) {
 431             return below;
 432           } else {
 433             needToInsertSharedNode = true;
 434           }
 435         }
 436
 437         if (needToInsertSharedNode) {
 438           // no shared local location at d+1, need to insert it!
 439           String newSharedLocName = "ILOC" + (LocationInference.locSeed++);
 440           Set<String> lowerSet = new HashSet<String>();
 441           lowerSet.addAll(connectedSet);
 442           lattice.insertNewLocationBetween(cur, lowerSet, newSharedLocName);
 443           lattice.addSharedLoc(newSharedLocName);
 444           addLocalLocation(lattice, newSharedLocName);
 445           System.out.println("          INSERT NEW SHARED LOC=" + newSharedLocName);
 446           cur = newSharedLocName;
 447         }
 448
 449         return cur;
 450
 451       } else {
 452
 453         return cur;
 454         // if the node is not shared, check if a node at distance d is a local or combination node
 455         // Set<String> connectedSet = lattice.get(cur);
 456         // if (connectedSet == null) {
 457         // connectedSet = new HashSet<String>();
 458         // }
 459         // System.out
 460         // .println("if the node is not shared, check if a node at distance d is a local or combination node connectedSet="
 461         // + connectedSet);
 462         // // if (!start.equals(cur) && (cur.equals(lattice.getTopItem()) ||
 463         // connectedSet.equals(endSet))) {
 464         // // if not, need to insert a new local location at this point
 465         // System.out.println("NEED TO INSERT A NEW LOCAL LOC connectedSet=" + connectedSet);
 466         // String newLocName = "ILOC" + (LocationInference.locSeed++);
 467         // Set<String> lowerSet = new HashSet<String>();
 468         // lowerSet.addAll(connectedSet);
 469         // lattice.insertNewLocationBetween(cur, lowerSet, newLocName);
 470         // addLocalLocation(lattice, newLocName);
 471         // return newLocName;
 472         // } else {
 473         // return cur;
 474         // }
 475       }
 476     }
 477
 478     Set<String> connectedSet = lattice.get(cur);
 479     if (connectedSet == null) {
 480       connectedSet = new HashSet<String>();
 481     }
 482
 483     System.out.println("cur=" + cur + " connected set=" + connectedSet);
 484     if (cur.equals(lattice.getTopItem()) || connectedSet.equals(endSet)) {
 485       // if not, need to insert a new local location at this point
 486       System.out.println("NEED TO INSERT A NEW LOCAL LOC FOR NEXT connectedSet=" + connectedSet);
 487       String newLocName = "ILOC" + (LocationInference.locSeed++);
 488       Set<String> lowerSet = new HashSet<String>();
 489       lowerSet.addAll(connectedSet);
 490       lattice.insertNewLocationBetween(cur, lowerSet, newLocName);
 491       addLocalLocation(lattice, newLocName);
 492       cur = newLocName;
 493     } else {
 494       // in this case, the current node is in the middle of the chain
 495       assert connectedSet.size() == 1;
 496       cur = connectedSet.iterator().next();
 497     }
 498
 499     if (!lattice.isSharedLoc(cur)) {
 500       dist--;
 501     }
 502     return recur_getNewLocation(lattice, start, cur, endSet, dist, isShared);
 503
 504   }
 505
 506   public String getNewLocation2(SSJavaLattice<String> lattice, String start, Set<String> endSet,
 507       int dist, boolean isShared) {
 508     System.out.println("       #GETNEWLOCATION:: start=" + start + "  endSet=" + endSet + " dist="
 509         + dist + " isShared=" + isShared);
 510     if (dist == -1) {
 511       if (isShared) {
 512         // if the node is a shared one, check if the next node is shared
 513         // if not, need to insert a new shared node
 514         return recur_getNewLocation2(lattice, start, endSet, dist + 1, isShared);
 515       } else {
 516         return start;
 517       }
 518
 519     }
 520     return recur_getNewLocation2(lattice, start, endSet, dist, isShared);
 521   }
 522
 523   private String recur_getNewLocation2(SSJavaLattice<String> lattice, String cur,
 524       Set<String> endSet, int dist, boolean isShared) {
 525     Set<String> connectedSet = lattice.get(cur);
 526     if (connectedSet == null) {
 527       connectedSet = new HashSet<String>();
 528     }
 529
 530     System.out.println("          recur_getNewLocation::cur=" + cur + " dist=" + dist
 531         + " connectedSet=" + connectedSet + " endSet=" + endSet);
 532
 533     if (dist == 0 && isShared) {
 534       // if the node is shared,
 535       // check if there already exists a shared node that has distance d + 1 on the chain
 536       if ((cur.equals(lattice.getTopItem()) && connectedSet.containsAll(endSet))
 537           || connectedSet.equals(endSet)) {
 538         // need to insert a new shared location
 539         // it is done after this if statement
 540       } else {
 541         assert connectedSet.size() == 1;
 542         String below = connectedSet.iterator().next();
 543         if (lattice.isSharedLoc(below)) {
 544           return below;
 545         }
 546       }
 547
 548       // need to insert a new shared location
 549       Set<String> newChildSet = new HashSet<String>();
 550       newChildSet.addAll(connectedSet);
 551
 552       String newLocName = "ILOC" + (LocationInference.locSeed++);
 553       for (Iterator iterator = newChildSet.iterator(); iterator.hasNext();) {
 554         String outNode = (String) iterator.next();
 555         lattice.put(newLocName, outNode);
 556       }
 557       lattice.get(cur).clear();
 558       lattice.put(cur, newLocName);
 559
 560       System.out.println("          INSERT NEW SHARED NODE=" + newLocName + " above=" + cur
 561           + " below=" + lattice.get(newLocName));
 562
 563       lattice.addSharedLoc(newLocName);
 564
 565       return newLocName;
 566
 567     }
 568
 569     String next;
 570
 571     if (cur.equals(lattice.getTopItem()) || connectedSet.equals(endSet) /* || endSet.isEmpty() */) {
 572
 573       // if ( (cur.equals(lattice.getTopItem()) && connectedSet.containsAll(endSet))
 574       // || connectedSet.equals(endSet)) {
 575
 576       // need to insert a new location
 577       String newLocName = "ILOC" + (LocationInference.locSeed++);
 578       connectedSet.clear();
 579       lattice.put(cur, newLocName);
 580
 581       System.out.println("#INSERT NEW RELATION cur=" + cur + " newLocName=" + newLocName + "::"
 582           + lattice.get(cur));
 583
 584       for (Iterator iterator = endSet.iterator(); iterator.hasNext();) {
 585         String endNode = (String) iterator.next();
 586         lattice.put(newLocName, endNode);
 587       }
 588
 589       next = newLocName;
 590       System.out.println("       INSERT NEW NODE=" + newLocName + " above=" + cur + " below="
 591           + endSet);
 592     } else {
 593       assert connectedSet.size() == 1;
 594       next = connectedSet.iterator().next();
 595       if (lattice.isSharedLoc(next)) {
 596         return recur_getNewLocation2(lattice, next, endSet, dist, isShared);
 597       }
 598     }
 599     System.out.println("              next=" + next);
 600
 601     if (dist == 0) {
 602       return next;
 603     } else {
 604       if (!lattice.isSharedLoc(next)) {
 605         dist--;
 606       }
 607       return recur_getNewLocation2(lattice, next, endSet, dist, isShared);
 608     }
 609
 610   }
 611
 612   public SSJavaLattice<String> insertIntermediateNodesToStraightLine2(Descriptor desc,
 613       SSJavaLattice<String> skeletonLattice) {
 614     // copy nodes/edges from the parent method/class if possible
 615     SSJavaLattice<String> lattice = skeletonLattice.clone();
 616
 617     Descriptor parentDesc = getParent(desc);
 618     if (parentDesc != null) {
 619       SSJavaLattice<String> parentLattice = infer.getLattice(parentDesc);
 620
 621       Map<String, Set<String>> parentMap = parentLattice.getTable();
 622       Set<String> parentKeySet = parentMap.keySet();
 623       for (Iterator iterator = parentKeySet.iterator(); iterator.hasNext();) {
 624         String parentKey = (String) iterator.next();
 625         Set<String> parentValueSet = parentMap.get(parentKey);
 626         for (Iterator iterator2 = parentValueSet.iterator(); iterator2.hasNext();) {
 627           String value = (String) iterator2.next();
 628           lattice.put(parentKey, value);
 629         }
 630       }
 631
 632       Set<String> parentSharedLocSet = parentLattice.getSharedLocSet();
 633       for (Iterator iterator = parentSharedLocSet.iterator(); iterator.hasNext();) {
 634         String parentSharedLoc = (String) iterator.next();
 635         lattice.addSharedLoc(parentSharedLoc);
 636       }
 637     }
 638
 639     // ////
 640
 641     // perform DFS that starts from each skeleton/combination node and ends by another
 642     // skeleton/combination node
 643
 644     mapSharedNodeToTripleItem.clear();
 645
 646     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 647     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 648     LocationSummary locSummary = infer.getLocationSummary(desc);
 649
 650     Set<HNode> visited = new HashSet<HNode>();
 651
 652     Set<HNode> nodeSet = simpleGraph.getNodeSet();
 653
 654     Map<TripleItem, String> mapIntermediateLoc = getIntermediateLocMap(desc);
 655     // Map<TripleItem, String> mapIntermediateLoc = new HashMap<TripleItem, String>();
 656
 657     // System.out.println("*insert=" + desc);
 658     // System.out.println("***nodeSet=" + nodeSet);
 659     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 660       HNode node = (HNode) iterator.next();
 661       System.out.println("node=" + node);
 662
 663       if (node.isSkeleton() && (!visited.contains(node))) {
 664         visited.add(node);
 665
 666         Set<HNode> outSet = simpleGraph.getOutgoingNodeSet(node);
 667         for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 668           HNode outNode = (HNode) iterator2.next();
 669
 670           if (!outNode.isSkeleton()) {
 671             if (outNode.isCombinationNode()) {
 672               if (visited.containsAll(simpleGraph.getIncomingNodeSet(outNode))) {
 673                 // if (needToExpandCombinationNode(desc, outNode)) {
 674                 expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary,
 675                     outNode);
 676                 // }
 677               }
 678             } else {
 679               // we have a node that is neither combination or skeleton node
 680               // System.out.println("%%%skeleton node=" + node + "  outNode=" + outNode);
 681               HNode startNode = scGraph.getCurrentHNode(node);
 682
 683               // if (node.getDescriptor() != null) {
 684               // // node is a skeleton node and it might be merged into another node in the SC
 685               // graph.
 686               // startNode = scGraph.getHNode(node.getDescriptor());
 687               // } else {
 688               // // this node has already been merged before the SC graph.
 689               // startNode = node;
 690               // }
 691
 692               // TODO
 693               // Set<HNode> endNodeSetFromSimpleGraph =
 694               // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null);
 695               // Set<HNode> endCombNodeSet = new HashSet<HNode>();
 696               // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator();
 697               // iterator3.hasNext();) {
 698               // HNode endNode = (HNode) iterator3.next();
 699               // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 700               // }
 701
 702               Set<HNode> endCombNodeSet = scGraph.getOutgoingNodeSet(startNode);
 703
 704               // System.out.println("endCombNodeSet=" + endCombNodeSet);
 705               visited.add(outNode);
 706               if (endCombNodeSet.size() > 0) {
 707                 // follows the straight line up to another skeleton/combination node
 708                 endCombNodeSet = removeTransitivelyReachToNode(desc, startNode, endCombNodeSet);
 709               } else if (endCombNodeSet.size() == 0) {
 710                 // the outNode is (directly/transitively) connected to the bottom node
 711                 // therefore, we just add a dummy bottom HNode to the endCombNodeSet.
 712                 endCombNodeSet.add(LocationInference.BOTTOMHNODE);
 713               }
 714
 715               recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
 716                   mapIntermediateLoc, 1, locSummary, outNode);
 717             }
 718
 719           }
 720
 721         }
 722       } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode()
 723           && !visited.contains(node)) {
 724
 725         System.out.println("n=" + node);
 726
 727         // an intermediate node 'node' may be located between "TOP" location and a skeleton node
 728         if (simpleGraph.getIncomingNodeSet(node).size() == 0) {
 729
 730           // this node will be directly connected to the TOP location
 731           // start adding the following nodes from this node
 732
 733           Set<HNode> endNodeSetFromSimpleGraph =
 734               simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(node, null);
 735
 736           Set<HNode> endCombNodeSet = new HashSet<HNode>();
 737           for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 738             HNode endNode = (HNode) iterator3.next();
 739             endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 740           }
 741
 742           System.out.println("endCombNodeSet=" + endCombNodeSet);
 743           HNode startNode = LocationInference.TOPHNODE;
 744           visited.add(startNode);
 745           if (endCombNodeSet.size() > 0) {
 746             // follows the straight line up to another skeleton/combination node
 747             // endCombNodeSet = removeTransitivelyReachToNode(desc, node, endCombNodeSet);
 748             recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
 749                 mapIntermediateLoc, 1, locSummary, node);
 750           }
 751
 752         }
 753
 754       }
 755     }
 756
 757     // add shared locations
 758     Set<HNode> sharedNodeSet = mapSharedNodeToTripleItem.keySet();
 759     for (Iterator iterator = sharedNodeSet.iterator(); iterator.hasNext();) {
 760       HNode sharedNode = (HNode) iterator.next();
 761       TripleItem item = mapSharedNodeToTripleItem.get(sharedNode);
 762       String nonSharedLocName = mapIntermediateLoc.get(item);
 763
 764       System.out.println("sharedNode=" + sharedNode + "    locName=" + nonSharedLocName);
 765
 766       String newLocName;
 767       if (locSummary.getHNodeNameSetByLatticeLoationName(nonSharedLocName) != null
 768           && !lattice.isSharedLoc(nonSharedLocName)) {
 769         // need to generate a new shared location in the lattice, which is one level lower than the
 770         // 'locName' location
 771         newLocName = "ILOC" + (LocationInference.locSeed++);
 772
 773         // Set<String> aboveElementSet = getAboveElementSet(lattice, locName);
 774         Set<String> belowElementSet = new HashSet<String>();
 775         belowElementSet.addAll(lattice.get(nonSharedLocName));
 776
 777         System.out.println("nonSharedLocName=" + nonSharedLocName + "   belowElementSet="
 778             + belowElementSet + "  newLocName=" + newLocName);
 779
 780         lattice.insertNewLocationBetween(nonSharedLocName, belowElementSet, newLocName);
 781       } else {
 782         newLocName = nonSharedLocName;
 783       }
 784
 785       lattice.addSharedLoc(newLocName);
 786       HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
 787       Set<Descriptor> descSet = graph.getDescSetOfNode(sharedNode);
 788       for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
 789         Descriptor d = (Descriptor) iterator2.next();
 790         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), newLocName);
 791       }
 792       locSummary.addMapHNodeNameToLocationName(sharedNode.getName(), newLocName);
 793
 794     }
 795
 796     return lattice;
 797
 798   }
 799
 800   private Set<String> getAboveElementSet(SSJavaLattice<String> lattice, String loc) {
 801
 802     Set<String> aboveSet = new HashSet<String>();
 803
 804     Map<String, Set<String>> latticeMap = lattice.getTable();
 805     Set<String> keySet = latticeMap.keySet();
 806     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 807       String key = (String) iterator.next();
 808       if (latticeMap.get(key).contains(loc)) {
 809         aboveSet.add(key);
 810       }
 811     }
 812
 813     return aboveSet;
 814   }
 815
 816   private boolean needToExpandCombinationNode(Descriptor desc, HNode cnode) {
 817
 818     System.out.println("needToExpandCombinationNode?=" + cnode);
 819
 820     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 821     // HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
 822     Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
 823     Set<HNode> combinationNodeSetInSimpleGraph =
 824         simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 825     System.out.println("---combinationNodeSetInSimpleGraph=" + combinationNodeSetInSimpleGraph);
 826     Set<HNode> inNodeSetToCNode = simpleGraph.getIncomingNodeSet(cnode);
 827     System.out.println("------inNodeSetToCNode=" + inNodeSetToCNode);
 828     for (Iterator iterator = combinationNodeSetInSimpleGraph.iterator(); iterator.hasNext();) {
 829       HNode nodeBelongToTheSameCombinationNode = (HNode) iterator.next();
 830       if (inNodeSetToCNode.contains(nodeBelongToTheSameCombinationNode)) {
 831         // the combination node 'cnode' is not the highest location among the same combination node
 832         return false;
 833       }
 834     }
 835
 836     return true;
 837   }
 838
 839   private void expandCombinationNode(Descriptor desc, SSJavaLattice<String> lattice,
 840       Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc, LocationSummary locSummary,
 841       HNode cnode) {
 842
 843     // expand the combination node 'outNode'
 844     // here we need to expand the corresponding combination location in the lattice
 845     HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
 846
 847     System.out.println("expandCombinationNode=" + cnode + "  cnode in scgraph="
 848         + combinationNodeInSCGraph);
 849
 850     if (combinationNodeInSCGraph == null) {
 851       return;
 852     }
 853
 854     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 855     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 856
 857     Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
 858
 859     // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
 860
 861     Set<HNode> combinationNodeSet =
 862         simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 863
 864     // System.out.println("combinationNodeSet=" + combinationNodeSet);
 865
 866     // TODO
 867     // Set<HNode> endNodeSetFromSimpleGraph =
 868     // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet);
 869     // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 870     // Set<HNode> endCombNodeSet = new HashSet<HNode>();
 871     // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 872     // HNode endNode = (HNode) iterator3.next();
 873     // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 874     // }
 875
 876     Set<HNode> endCombNodeSet = scGraph.getOutgoingNodeSet(combinationNodeInSCGraph);
 877     visited.add(cnode);
 878
 879     // follows the straight line up to another skeleton/combination node
 880     if (endCombNodeSet.size() > 0) {
 881       // System.out.println("---endCombNodeSet=" + endCombNodeSet);
 882       endCombNodeSet =
 883           removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
 884
 885       recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 886           mapIntermediateLoc, 1, locSummary, cnode);
 887     } else {
 888       endCombNodeSet.add(LocationInference.BOTTOMHNODE);
 889       // System.out.println("---endCombNodeSet is zero");
 890       // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 891       // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode));
 892       recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 893           mapIntermediateLoc, 1, locSummary, cnode);
 894
 895     }
 896
 897   }
 898
 899   private Set<HNode> removeTransitivelyReachToNode(Descriptor desc, HNode startNode,
 900       Set<HNode> endNodeSet) {
 901
 902     // if an end node is not directly connected to the start node in the SC graph
 903     // replace it with a directly connected one which transitively reaches to it.
 904
 905     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 906
 907     Set<HNode> newEndNodeSet = new HashSet<HNode>();
 908     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 909       HNode endNode = (HNode) iterator.next();
 910       if (scGraph.isDirectlyConnectedTo(startNode, endNode)) {
 911         newEndNodeSet.add(endNode);
 912       } else {
 913         HNode newEndNode =
 914             getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode);
 915         // System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode);
 916         newEndNodeSet.add(newEndNode);
 917       }
 918     }
 919
 920     // System.out.println("removeTransitivelyReachToNode=" + endNodeSet + "  newSet=" +
 921     // newEndNodeSet);
 922
 923     return newEndNodeSet;
 924
 925   }
 926
 927   private HNode getDirectlyReachableSCNodeFromEndNode(HierarchyGraph scGraph, HNode startNode,
 928       Set<HNode> endNodeSet) {
 929
 930     // System.out.println("getDirectlyReachableSCNodeFromEndNode start=" + startNode +
 931     // " endNodeSet="
 932     // + endNodeSet);
 933     Set<HNode> newStartNodeSet = new HashSet<HNode>();
 934
 935     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 936       HNode endNode = (HNode) iterator.next();
 937       Set<HNode> connectedToEndNodeSet = scGraph.getIncomingNodeSet(endNode);
 938
 939       for (Iterator iterator2 = connectedToEndNodeSet.iterator(); iterator2.hasNext();) {
 940         HNode curNode = (HNode) iterator2.next();
 941         if (recurConnectedFromStartNode(scGraph, startNode, curNode, new HashSet<HNode>())) {
 942           newStartNodeSet.add(curNode);
 943         }
 944       }
 945     }
 946
 947     // System.out.println("newStartNodeSet=" + newStartNodeSet);
 948
 949     if (newStartNodeSet.size() == 0) {
 950       newStartNodeSet.add(startNode);
 951     }
 952
 953     return newStartNodeSet.iterator().next();
 954   }
 955
 956   private boolean recurConnectedFromStartNode(HierarchyGraph scGraph, HNode startNode,
 957       HNode curNode, Set<HNode> visited) {
 958     // return true if curNode is transitively connected from the startNode
 959
 960     boolean isConnected = false;
 961     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 962     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 963       HNode in = (HNode) iterator.next();
 964       if (in.equals(startNode)) {
 965         return true;
 966       } else {
 967         visited.add(in);
 968         isConnected |= recurConnectedFromStartNode(scGraph, startNode, in, visited);
 969       }
 970     }
 971
 972     return isConnected;
 973   }
 974
 975   private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 976       HNode startNode, HNode endNode) {
 977     // System.out.println("getDirectlyReachableNodeFromStartNodeReachToEndNode start=" + startNode
 978     // + " end=" + endNode);
 979     Set<HNode> connected = new HashSet<HNode>();
 980     recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected);
 981     if (connected.size() == 0) {
 982       connected.add(endNode);
 983     }
 984     // System.out.println("connected=" + connected);
 985
 986     return connected.iterator().next();
 987   }
 988
 989   private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 990       HNode startNode, HNode curNode, Set<HNode> connected) {
 991
 992     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 993     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 994       HNode inNode = (HNode) iterator.next();
 995       if (inNode.equals(startNode)) {
 996         connected.add(curNode);
 997       } else {
 998         recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected);
 999       }
1000     }
1001
1002   }
1003
1004   private void recurDFSNormalNode(Descriptor desc, SSJavaLattice<String> lattice, HNode startNode,
1005       Set<HNode> endNodeSet, Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc,
1006       int idx, LocationSummary locSummary, HNode curNode) {
1007
1008     TripleItem item = new TripleItem(startNode, endNodeSet, idx);
1009     if (!mapIntermediateLoc.containsKey(item)) {
1010       // need to create a new intermediate location in the lattice
1011       String newLocName = "ILOC" + (LocationInference.locSeed++);
1012       String above;
1013       if (idx == 1) {
1014         above = startNode.getName();
1015       } else {
1016         int prevIdx = idx - 1;
1017         TripleItem prevItem = new TripleItem(startNode, endNodeSet, prevIdx);
1018         above = mapIntermediateLoc.get(prevItem);
1019       }
1020
1021       Set<String> belowSet = new HashSet<String>();
1022       for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
1023         HNode endNode = (HNode) iterator.next();
1024         String locName;
1025         if (locSummary.getMapHNodeNameToLocationName().containsKey(endNode.getName())) {
1026           locName = locSummary.getLocationName(endNode.getName());
1027         } else {
1028           locName = endNode.getName();
1029         }
1030         belowSet.add(locName);
1031       }
1032       lattice.insertNewLocationBetween(above, belowSet, newLocName);
1033
1034       mapIntermediateLoc.put(item, newLocName);
1035     }
1036
1037     String locName = mapIntermediateLoc.get(item);
1038     HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
1039
1040     if (curNode.isSharedNode()) {
1041       // if the current node is shared location, add a shared location to the lattice later
1042       System.out.println("###SHARED ITEM=" + item);
1043       mapSharedNodeToTripleItem.put(curNode, item);
1044     } else {
1045       Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
1046       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
1047         Descriptor d = (Descriptor) iterator.next();
1048         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
1049       }
1050       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
1051     }
1052
1053     System.out.println("-TripleItem normal=" + item);
1054     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
1055         + " locName=" + locName + "  isC=" + curNode.isCombinationNode());
1056
1057     Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
1058     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
1059       HNode outNode = (HNode) iterator2.next();
1060
1061       Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
1062       System.out.println("outNode=" + outNode);
1063       System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode);
1064
1065       if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
1066         Pair<HNode, HNode> pair = new Pair(startNode, outNode);
1067         if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) {
1068           visited.add(outNode);
1069           int newidx = getCurrentHighestIndex(pair, idx + 1);
1070           // int newidx = getCurrentHighestIndex(outNode, idx + 1);
1071           recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
1072               newidx, locSummary, outNode);
1073           // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
1074           // idx + 1, locSummary, outNode);
1075         } else {
1076           updateHighestIndex(pair, idx + 1);
1077           // updateHighestIndex(outNode, idx + 1);
1078           System.out.println("NOT RECUR");
1079         }
1080       } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) {
1081         if (needToExpandCombinationNode(desc, outNode)) {
1082           System.out.println("NEED TO");
1083           expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
1084         } else {
1085           System.out.println("NOT NEED TO");
1086         }
1087       }
1088
1089     }
1090
1091   }
1092
1093   private void recurDFS(Descriptor desc, SSJavaLattice<String> lattice,
1094       HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
1095       Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode curNode) {
1096
1097     TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx);
1098
1099     if (!mapIntermediateLoc.containsKey(item)) {
1100       // need to create a new intermediate location in the lattice
1101       String above;
1102       if (idx == 1) {
1103         String newLocName = combinationNodeInSCGraph.getName();
1104         mapIntermediateLoc.put(item, newLocName);
1105       } else {
1106         String newLocName = "ILOC" + (LocationInference.locSeed++);
1107         int prevIdx = idx - 1;
1108         TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
1109         above = mapIntermediateLoc.get(prevItem);
1110
1111         Set<String> belowSet = new HashSet<String>();
1112         for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
1113           HNode endNode = (HNode) iterator.next();
1114           belowSet.add(endNode.getName());
1115         }
1116         lattice.insertNewLocationBetween(above, belowSet, newLocName);
1117         mapIntermediateLoc.put(item, newLocName);
1118       }
1119
1120     }
1121
1122     // TODO
1123     // Do we need to skip the combination node and assign a shared location to the next node?
1124     // if (idx == 1 && curNode.isSharedNode()) {
1125     // System.out.println("THE FIRST COMBINATION NODE EXPANSION IS SHARED!");
1126     // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, mapIntermediateLoc,
1127     // idx + 1, locSummary, curNode);
1128     // return;
1129     // }
1130
1131     HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
1132     String locName = mapIntermediateLoc.get(item);
1133     if (curNode.isSharedNode()) {
1134       // if the current node is shared location, add a shared location to the lattice later
1135       System.out.println("###SHARED ITEM=" + item);
1136       mapSharedNodeToTripleItem.put(curNode, item);
1137     } else {
1138       Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
1139       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
1140         Descriptor d = (Descriptor) iterator.next();
1141         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
1142       }
1143       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
1144     }
1145
1146     System.out.println("-TripleItem=" + item);
1147     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
1148         + " locName=" + locName);
1149
1150     Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
1151     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
1152       HNode outNode = (HNode) iterator2.next();
1153       System.out.println("---recurDFS outNode=" + outNode);
1154       System.out.println("---cur combinationNodeInSCGraph=" + combinationNodeInSCGraph);
1155       System.out.println("---outNode combinationNodeInSCGraph="
1156           + getCombinationNodeInSCGraph(desc, outNode));
1157
1158       if (!outNode.isSkeleton() && !visited.contains(outNode)) {
1159         if (outNode.isCombinationNode()) {
1160
1161           Set<HNode> combineSkeletonNodeSet =
1162               simpleHierarchyGraph.getCombineSetByCombinationNode(outNode);
1163           Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
1164           // extract nodes belong to the same combine node
1165           Set<HNode> incomingCombinedHNodeSet = new HashSet<HNode>();
1166           for (Iterator iterator = incomingHNodeSetToOutNode.iterator(); iterator.hasNext();) {
1167             HNode inNode = (HNode) iterator.next();
1168             if (combineSkeletonNodeSet.contains(inNode)) {
1169               incomingCombinedHNodeSet.add(inNode);
1170             }
1171           }
1172           System.out.println("-----incomingCombinedHNodeSet=" + incomingCombinedHNodeSet);
1173
1174           // check whether the next combination node is different from the current node
1175           if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
1176             Pair<HNode, HNode> pair = new Pair(combinationNodeInSCGraph, outNode);
1177             if (visited.containsAll(incomingCombinedHNodeSet)) {
1178               visited.add(outNode);
1179               System.out.println("-------curIdx=" + (idx + 1));
1180
1181               int newIdx = getCurrentHighestIndex(pair, idx + 1);
1182               // int newIdx = getCurrentHighestIndex(outNode, idx + 1);
1183               System.out.println("-------newIdx=" + newIdx);
1184               recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
1185                   mapIntermediateLoc, newIdx, locSummary, outNode);
1186               // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
1187               // mapIntermediateLoc, idx + 1, locSummary, outNode);
1188             } else {
1189               updateHighestIndex(pair, idx + 1);
1190               // updateHighestIndex(outNode, idx + 1);
1191               System.out.println("-----NOT RECUR!");
1192             }
1193           } else {
1194             if (needToExpandCombinationNode(desc, outNode)) {
1195               System.out.println("NEED TO");
1196               expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
1197             } else {
1198               System.out.println("NOT NEED TO");
1199             }
1200
1201           }
1202         }
1203       }
1204       // }
1205
1206     }
1207
1208   }
1209
1210   private int getCurrentHighestIndex(Pair<HNode, HNode> pair, int curIdx) {
1211     int recordedIdx = getCurrentHighestIndex(pair);
1212     if (recordedIdx > curIdx) {
1213       return recordedIdx;
1214     } else {
1215       return curIdx;
1216     }
1217   }
1218
1219   private int getCurrentHighestIndex(HNode node, int curIdx) {
1220     int recordedIdx = getCurrentHighestIndex(node);
1221     if (recordedIdx > curIdx) {
1222       return recordedIdx;
1223     } else {
1224       return curIdx;
1225     }
1226   }
1227
1228   private int getCurrentHighestIndex(Pair<HNode, HNode> pair) {
1229     if (!mapItemToHighestIndex.containsKey(pair)) {
1230       mapItemToHighestIndex.put(pair, new Integer(-1));
1231     }
1232     return mapItemToHighestIndex.get(pair).intValue();
1233   }
1234
1235   private void updateHighestIndex(Pair<HNode, HNode> pair, int idx) {
1236     if (idx > getCurrentHighestIndex(pair)) {
1237       mapItemToHighestIndex.put(pair, new Integer(idx));
1238     }
1239   }
1240
1241   private int getCurrentHighestIndex(HNode node) {
1242     if (!mapHNodeToHighestIndex.containsKey(node)) {
1243       mapHNodeToHighestIndex.put(node, new Integer(-1));
1244     }
1245     return mapHNodeToHighestIndex.get(node).intValue();
1246   }
1247
1248   private void updateHighestIndex(HNode node, int idx) {
1249     if (idx > getCurrentHighestIndex(node)) {
1250       mapHNodeToHighestIndex.put(node, new Integer(idx));
1251     }
1252   }
1253
1254   private String generateElementName(BasisSet basisSet, HierarchyGraph inputGraph,
1255       Map<Set<Integer>, String> mapF2LocName, Set<Integer> F) {
1256
1257     if (mapF2LocName.containsKey(F)) {
1258       return mapF2LocName.get(F);
1259     }
1260
1261     HNode node = basisSet.getHNode(F);
1262     if (node != null) {
1263       mapF2LocName.put(F, node.getName());
1264       return node.getName();
1265     } else {
1266       if (inputGraph.BASISTOPELEMENT.equals(F)) {
1267         return SSJavaAnalysis.BOTTOM;
1268       } else {
1269         String str = "LOC" + (LocationInference.locSeed++);
1270         mapF2LocName.put(F, str);
1271         return str;
1272       }
1273     }
1274   }
1275
1276   private void resetCount(Map<Set<Integer>, Integer> mapFtoCount, Family family) {
1277     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
1278       Set<Integer> F = iter.next();
1279       mapFtoCount.put(F, 0);
1280     }
1281   }
1282
1283   private Map<Set<Integer>, Set<Set<Integer>>> coveringGraph(BasisSet basisSet, Family family) {
1284
1285     Map<Set<Integer>, Integer> mapFtoCount = new HashMap<Set<Integer>, Integer>();
1286     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = new HashMap<Set<Integer>, Set<Set<Integer>>>();
1287
1288     // initialize COUNT(F) to 0 for all elements of the family
1289     resetCount(mapFtoCount, family);
1290
1291     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
1292       Set<Integer> F = iter.next();
1293       Set<HNode> gammaF = family.getGamma(F);
1294
1295       Set<HNode> curHNodeSet = basisSet.getHNodeSet();
1296       curHNodeSet.removeAll(gammaF);
1297       Set<Set<Integer>> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet);
1298
1299       for (Iterator iterator = Bset.iterator(); iterator.hasNext();) {
1300         Set<Integer> B = (Set<Integer>) iterator.next();
1301
1302         Set<Integer> Fprime = new HashSet<Integer>();
1303         Fprime.addAll(F);
1304         Fprime.addAll(B);
1305
1306         // COUNT(F')++;
1307         mapFtoCount.put(Fprime, mapFtoCount.get(Fprime) + 1);
1308
1309         // if |gamma(F')|==COUNT(F') + |gamma(F)|
1310         int numGammaFprime = family.getGamma(Fprime).size();
1311         int countFprime = mapFtoCount.get(Fprime);
1312         int numGammaF = family.getGamma(F).size();
1313         if (numGammaFprime == (countFprime + numGammaF)) {
1314           // ImSucc(F)=IMSucc(F) union F'
1315           addImSucc(mapImSucc, F, Fprime);
1316         }
1317
1318       }
1319       resetCount(mapFtoCount, family);
1320     }
1321
1322     // System.out.println("mapImSucc=" + mapImSucc);
1323
1324     return mapImSucc;
1325   }
1326
1327   private Set<Set<Integer>> getImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F) {
1328     if (!mapImSucc.containsKey(F)) {
1329       mapImSucc.put(F, new HashSet<Set<Integer>>());
1330     }
1331     return mapImSucc.get(F);
1332   }
1333
1334   private void addImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F,
1335       Set<Integer> Fprime) {
1336
1337     if (!mapImSucc.containsKey(F)) {
1338       mapImSucc.put(F, new HashSet<Set<Integer>>());
1339     }
1340
1341     mapImSucc.get(F).add(Fprime);
1342
1343   }
1344
1345   private Family generateFamily(BasisSet basisSet) {
1346
1347     Family family = new Family();
1348
1349     for (Iterator<Set<Integer>> iterator = basisSet.basisIterator(); iterator.hasNext();) {
1350       Set<Integer> B = iterator.next();
1351
1352       Set<Pair<Set<Integer>, Set<HNode>>> tobeadded = new HashSet<Pair<Set<Integer>, Set<HNode>>>();
1353
1354       for (Iterator<Set<Integer>> iterator2 = family.FIterator(); iterator2.hasNext();) {
1355         Set<Integer> F = iterator2.next();
1356
1357         Set<Integer> Fprime = new HashSet<Integer>();
1358         Fprime.addAll(F);
1359         Fprime.addAll(B);
1360
1361         Set<HNode> gammaFPrimeSet = new HashSet<HNode>();
1362         gammaFPrimeSet.addAll(family.getGamma(F));
1363         gammaFPrimeSet.add(basisSet.getHNode(B));
1364
1365         if (!family.containsF(Fprime)) {
1366           Pair<Set<Integer>, Set<HNode>> pair =
1367               new Pair<Set<Integer>, Set<HNode>>(Fprime, gammaFPrimeSet);
1368           tobeadded.add(pair);
1369         } else {
1370           family.updateGammaF(Fprime, gammaFPrimeSet);
1371         }
1372       }
1373
1374       for (Iterator<Pair<Set<Integer>, Set<HNode>>> iterator2 = tobeadded.iterator(); iterator2
1375           .hasNext();) {
1376         Pair<Set<Integer>, Set<HNode>> pair = iterator2.next();
1377         family.addFElement(pair.getFirst());
1378         family.updateGammaF(pair.getFirst(), pair.getSecond());
1379       }
1380
1381     }
1382     return family;
1383   }
1384
1385   private void debug_print(HierarchyGraph inputGraph) {
1386     System.out.println("\nBuild Lattice:" + inputGraph.getName());
1387     System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex());
1388     System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
1389   }
1390
1391 }
1392
1393 class Identifier {
1394   public HNode node;
1395   public int idx;
1396
1397   public Identifier(HNode n, int i) {
1398     node = n;
1399     idx = i;
1400   }
1401
1402   public int hashCode() {
1403     return node.hashCode() + idx;
1404   }
1405
1406   public boolean equals(Object obj) {
1407
1408     if (obj instanceof Identifier) {
1409       Identifier in = (Identifier) obj;
1410       if (node.equals(in.node) && idx == in.idx) {
1411         return true;
1412       }
1413     }
1414
1415     return false;
1416   }
1417
1418 }
1419
1420 class TripleItem {
1421   public HNode higherNode;
1422   public Set<HNode> lowerNodeSet;
1423   public int idx;
1424   public boolean isShared;
1425
1426   public TripleItem(HNode h, Set<HNode> l, int i) {
1427     higherNode = h;
1428     lowerNodeSet = l;
1429     idx = i;
1430     isShared = false;
1431   }
1432
1433   public void setShared(boolean in) {
1434     this.isShared = in;
1435   }
1436
1437   public boolean isShared() {
1438     return isShared;
1439   }
1440
1441   public int hashCode() {
1442
1443     int h = 0;
1444     if (higherNode != null) {
1445       h = higherNode.hashCode();
1446     }
1447
1448     if (isShared) {
1449       h++;
1450     }
1451
1452     return h + lowerNodeSet.hashCode() + idx;
1453   }
1454
1455   public boolean equals(Object obj) {
1456
1457     if (obj instanceof TripleItem) {
1458       TripleItem in = (TripleItem) obj;
1459       if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode)))
1460           && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx && isShared == in.isShared()) {
1461         return true;
1462       }
1463     }
1464
1465     return false;
1466   }
1467
1468   public String toString() {
1469     String rtr = higherNode + "-" + idx + "->" + lowerNodeSet;
1470     if (isShared) {
1471       rtr += " S";
1472     }
1473     return rtr;
1474   }
1475 }