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