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