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