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.Descriptor;
  10 import IR.MethodDescriptor;
  11 import Util.Pair;
  12
  13 public class BuildLattice {
  14
  15   private LocationInference infer;
  16   private Map<HNode, TripleItem> mapSharedNodeToTripleItem;
  17
  18   public BuildLattice(LocationInference infer) {
  19     this.infer = infer;
  20     this.mapSharedNodeToTripleItem = new HashMap<HNode, TripleItem>();
  21   }
  22
  23   public SSJavaLattice<String> buildLattice(Descriptor desc) {
  24
  25     HierarchyGraph inputGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
  26     LocationSummary locSummary = infer.getLocationSummary(desc);
  27
  28     Set<HNode> nodeSetWithCompositeLocation = new HashSet<HNode>();
  29     if (desc instanceof MethodDescriptor) {
  30       FlowGraph flowGraph = infer.getFlowGraph((MethodDescriptor) desc);
  31
  32       for (Iterator iterator = inputGraph.getNodeSet().iterator(); iterator.hasNext();) {
  33         HNode hnode = (HNode) iterator.next();
  34         Descriptor hnodeDesc = hnode.getDescriptor();
  35         if (hnodeDesc != null) {
  36           NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
  37           descTuple.add(hnodeDesc);
  38
  39           if (flowGraph.contains(descTuple)) {
  40             FlowNode flowNode = flowGraph.getFlowNode(descTuple);
  41             if (flowNode.getCompositeLocation() != null) {
  42               nodeSetWithCompositeLocation.add(hnode);
  43             }
  44           }
  45
  46         }
  47       }
  48
  49     }
  50
  51     BasisSet basisSet = inputGraph.computeBasisSet(nodeSetWithCompositeLocation);
  52     debug_print(inputGraph);
  53
  54     Family family = generateFamily(basisSet);
  55     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = coveringGraph(basisSet, family);
  56
  57     SSJavaLattice<String> lattice = buildLattice(basisSet, inputGraph, locSummary, mapImSucc);
  58     return lattice;
  59
  60   }
  61
  62   private SSJavaLattice<String> buildLattice(BasisSet basisSet, HierarchyGraph inputGraph,
  63       LocationSummary locSummary, Map<Set<Integer>, Set<Set<Integer>>> mapImSucc) {
  64
  65     SSJavaLattice<String> lattice =
  66         new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
  67
  68     Map<Set<Integer>, String> mapFToLocName = new HashMap<Set<Integer>, String>();
  69
  70     Set<Set<Integer>> keySet = mapImSucc.keySet();
  71     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
  72       Set<Integer> higher = (Set<Integer>) iterator.next();
  73
  74       String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher);
  75
  76       HNode higherNode = inputGraph.getHNode(higherName);
  77       if (higherNode != null && higherNode.isSharedNode()) {
  78         lattice.addSharedLoc(higherName);
  79       }
  80       Set<Descriptor> descSet = inputGraph.getDescSetOfNode(higherNode);
  81       // System.out.println("higherName=" + higherName + "  higherNode=" + higherNode + "  descSet="
  82       // + descSet);
  83       for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
  84         Descriptor d = (Descriptor) iterator2.next();
  85         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), higherName);
  86       }
  87       // locSummary.addMapHNodeNameToLocationName(higherName, higherName);
  88
  89       Set<Set<Integer>> lowerSet = mapImSucc.get(higher);
  90       for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
  91         Set<Integer> lower = (Set<Integer>) iterator2.next();
  92
  93         String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower);
  94         HNode lowerNode = inputGraph.getHNode(lowerName);
  95         if (lowerNode != null && lowerNode.isSharedNode()) {
  96           lattice.addSharedLoc(lowerName);
  97         }
  98
  99         Set<Descriptor> lowerDescSet = inputGraph.getDescSetOfNode(lowerNode);
 100         // System.out.println("lowerName=" + lowerName + "  lowerNode=" + lowerNode + "  descSet="
 101         // + lowerDescSet);
 102         for (Iterator iterator3 = lowerDescSet.iterator(); iterator3.hasNext();) {
 103           Descriptor d = (Descriptor) iterator3.next();
 104           locSummary.addMapHNodeNameToLocationName(d.getSymbol(), lowerName);
 105         }
 106         // locSummary.addMapHNodeNameToLocationName(lowerName, lowerName);
 107
 108         if (higher.size() == 0) {
 109           // empty case
 110           lattice.put(lowerName);
 111         } else {
 112           lattice.addRelationHigherToLower(higherName, lowerName);
 113         }
 114
 115       }
 116
 117     }
 118
 119     return lattice;
 120   }
 121
 122   public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode nodeFromSimpleGraph) {
 123
 124     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 125
 126     if (nodeFromSimpleGraph.isSkeleton()) {
 127       return scGraph.getCurrentHNode(nodeFromSimpleGraph);
 128     }
 129
 130     Set<HNode> combineSkeletonNodeSet =
 131         infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(nodeFromSimpleGraph);
 132     HNode combinationNodeInSCGraph =
 133         infer.getSkeletonCombinationHierarchyGraph(desc).getMapCombineNodeSetToCombinationNode()
 134             .get(combineSkeletonNodeSet);
 135
 136     // Set<HNode> combineSkeletonNodeSet =
 137     // infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode);
 138     // HNode combinationNodeInSCGraph =
 139     // infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet);
 140     return combinationNodeInSCGraph;
 141   }
 142
 143   public SSJavaLattice<String> insertIntermediateNodesToStraightLine(Descriptor desc,
 144       SSJavaLattice<String> skeletonLattice) {
 145
 146     // perform DFS that starts from each skeleton/combination node and ends by another
 147     // skeleton/combination node
 148
 149     mapSharedNodeToTripleItem.clear();
 150
 151     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 152     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 153     LocationSummary locSummary = infer.getLocationSummary(desc);
 154
 155     SSJavaLattice<String> lattice = skeletonLattice.clone();
 156
 157     Set<HNode> visited = new HashSet<HNode>();
 158
 159     Set<HNode> nodeSet = simpleGraph.getNodeSet();
 160
 161     Map<TripleItem, String> mapIntermediateLoc = new HashMap<TripleItem, String>();
 162
 163     System.out.println("*insert=" + desc);
 164     System.out.println("***nodeSet=" + nodeSet);
 165     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 166       HNode node = (HNode) iterator.next();
 167       System.out.println("node=" + node);
 168
 169       if (node.isSkeleton() && (!visited.contains(node))) {
 170         visited.add(node);
 171
 172         Set<HNode> outSet = simpleGraph.getOutgoingNodeSet(node);
 173         for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 174           HNode outNode = (HNode) iterator2.next();
 175
 176           if (!outNode.isSkeleton()) {
 177             if (outNode.isCombinationNode()) {
 178               expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 179             } else {
 180               // we have a node that is neither combination or skeleton node
 181               // System.out.println("%%%skeleton node=" + node + "  outNode=" + outNode);
 182               HNode startNode = scGraph.getCurrentHNode(node);
 183
 184               // if (node.getDescriptor() != null) {
 185               // // node is a skeleton node and it might be merged into another node in the SC
 186               // graph.
 187               // startNode = scGraph.getHNode(node.getDescriptor());
 188               // } else {
 189               // // this node has already been merged before the SC graph.
 190               // startNode = node;
 191               // }
 192
 193               Set<HNode> endNodeSetFromSimpleGraph =
 194                   simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null);
 195
 196               // System.out.println("endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph
 197               // + "   from=" + outNode);
 198               Set<HNode> endCombNodeSet = new HashSet<HNode>();
 199               for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 200                 HNode endNode = (HNode) iterator3.next();
 201                 endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 202               }
 203               // System.out.println("endCombNodeSet=" + endCombNodeSet);
 204               visited.add(outNode);
 205               if (endCombNodeSet.size() > 0) {
 206                 // follows the straight line up to another skeleton/combination node
 207                 endCombNodeSet = removeTransitivelyReachToNode(desc, startNode, endCombNodeSet);
 208               } else if (endCombNodeSet.size() == 0) {
 209                 // the outNode is (directly/transitively) connected to the bottom node
 210                 // therefore, we just add a dummy bottom HNode to the endCombNodeSet.
 211                 endCombNodeSet.add(LocationInference.BOTTOMHNODE);
 212               }
 213
 214               recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
 215                   mapIntermediateLoc, 1, locSummary, outNode);
 216             }
 217
 218           }
 219
 220         }
 221       } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode()
 222           && !visited.contains(node)) {
 223
 224         System.out.println("n=" + node);
 225
 226         // an intermediate node 'node' may be located between "TOP" location and a skeleton node
 227         if (simpleGraph.getIncomingNodeSet(node).size() == 0) {
 228
 229           // this node will be directly connected to the TOP location
 230           // start adding the following nodes from this node
 231
 232           Set<HNode> endNodeSetFromSimpleGraph =
 233               simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(node, null);
 234
 235           Set<HNode> endCombNodeSet = new HashSet<HNode>();
 236           for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 237             HNode endNode = (HNode) iterator3.next();
 238             endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 239           }
 240
 241           System.out.println("endCombNodeSet=" + endCombNodeSet);
 242           HNode startNode = LocationInference.TOPHNODE;
 243           visited.add(startNode);
 244           if (endCombNodeSet.size() > 0) {
 245             // follows the straight line up to another skeleton/combination node
 246             // endCombNodeSet = removeTransitivelyReachToNode(desc, node, endCombNodeSet);
 247             recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
 248                 mapIntermediateLoc, 1, locSummary, node);
 249           }
 250
 251         }
 252
 253       }
 254     }
 255
 256     // add shared locations
 257     Set<HNode> sharedNodeSet = mapSharedNodeToTripleItem.keySet();
 258     for (Iterator iterator = sharedNodeSet.iterator(); iterator.hasNext();) {
 259       HNode sharedNode = (HNode) iterator.next();
 260       TripleItem item = mapSharedNodeToTripleItem.get(sharedNode);
 261       String nonSharedLocName = mapIntermediateLoc.get(item);
 262       System.out.println("sharedNode=" + sharedNode + "    locName=" + nonSharedLocName);
 263
 264       String newLocName;
 265       if (locSummary.getHNodeNameSetByLatticeLoationName(nonSharedLocName) != null
 266           && !lattice.isSharedLoc(nonSharedLocName)) {
 267         // need to generate a new shared location in the lattice, which is one level lower than the
 268         // 'locName' location
 269         newLocName = "ILOC" + (LocationInference.locSeed++);
 270
 271         // Set<String> aboveElementSet = getAboveElementSet(lattice, locName);
 272         Set<String> belowElementSet = new HashSet<String>();
 273         belowElementSet.addAll(lattice.get(nonSharedLocName));
 274
 275         System.out.println("nonSharedLocName=" + nonSharedLocName + "   belowElementSet="
 276             + belowElementSet + "  newLocName=" + newLocName);
 277
 278         lattice.insertNewLocationBetween(nonSharedLocName, belowElementSet, newLocName);
 279       } else {
 280         newLocName = nonSharedLocName;
 281       }
 282
 283       lattice.addSharedLoc(newLocName);
 284       HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
 285       Set<Descriptor> descSet = graph.getDescSetOfNode(sharedNode);
 286       for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
 287         Descriptor d = (Descriptor) iterator2.next();
 288         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), newLocName);
 289       }
 290       locSummary.addMapHNodeNameToLocationName(sharedNode.getName(), newLocName);
 291
 292     }
 293
 294     return lattice;
 295
 296   }
 297
 298   private Set<String> getAboveElementSet(SSJavaLattice<String> lattice, String loc) {
 299
 300     Set<String> aboveSet = new HashSet<String>();
 301
 302     Map<String, Set<String>> latticeMap = lattice.getTable();
 303     Set<String> keySet = latticeMap.keySet();
 304     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 305       String key = (String) iterator.next();
 306       if (latticeMap.get(key).contains(loc)) {
 307         aboveSet.add(key);
 308       }
 309     }
 310
 311     return aboveSet;
 312   }
 313
 314   private void expandCombinationNode(Descriptor desc, SSJavaLattice<String> lattice,
 315       Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc, LocationSummary locSummary,
 316       HNode cnode) {
 317
 318     System.out.println("expandCombinationNode=" + cnode);
 319     // expand the combination node 'outNode'
 320     // here we need to expand the corresponding combination location in the lattice
 321     HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
 322
 323     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 324
 325     Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
 326
 327     // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
 328
 329     Set<HNode> combinationNodeSet =
 330         simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 331
 332     // System.out.println("combinationNodeSet=" + combinationNodeSet);
 333
 334     Set<HNode> endNodeSetFromSimpleGraph =
 335         simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet);
 336     // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 337     Set<HNode> endCombNodeSet = new HashSet<HNode>();
 338     for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 339       HNode endNode = (HNode) iterator3.next();
 340       endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 341     }
 342     visited.add(cnode);
 343
 344     // follows the straight line up to another skeleton/combination node
 345     if (endCombNodeSet.size() > 0) {
 346       System.out.println("---endCombNodeSet=" + endCombNodeSet);
 347       endCombNodeSet =
 348           removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
 349
 350       recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 351           mapIntermediateLoc, 1, locSummary, cnode);
 352     } else {
 353       endCombNodeSet.add(LocationInference.BOTTOMHNODE);
 354       // System.out.println("---endCombNodeSet is zero");
 355       // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 356       // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode));
 357       recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 358           mapIntermediateLoc, 1, locSummary, cnode);
 359
 360     }
 361
 362   }
 363
 364   private Set<HNode> removeTransitivelyReachToNode(Descriptor desc, HNode startNode,
 365       Set<HNode> endNodeSet) {
 366
 367     // if an end node is not directly connected to the start node in the SC graph
 368     // replace it with a directly connected one which transitively reaches to it.
 369
 370     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 371
 372     Set<HNode> newEndNodeSet = new HashSet<HNode>();
 373     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 374       HNode endNode = (HNode) iterator.next();
 375       if (scGraph.isDirectlyConnectedTo(startNode, endNode)) {
 376         newEndNodeSet.add(endNode);
 377       } else {
 378         HNode newEndNode =
 379             getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode);
 380         // System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode);
 381         newEndNodeSet.add(newEndNode);
 382       }
 383     }
 384
 385     // System.out.println("removeTransitivelyReachToNode=" + endNodeSet + "  newSet=" +
 386     // newEndNodeSet);
 387
 388     return newEndNodeSet;
 389
 390   }
 391
 392   private HNode getDirectlyReachableSCNodeFromEndNode(HierarchyGraph scGraph, HNode startNode,
 393       Set<HNode> endNodeSet) {
 394
 395     System.out.println("getDirectlyReachableSCNodeFromEndNode start=" + startNode + " endNodeSet="
 396         + endNodeSet);
 397     Set<HNode> newStartNodeSet = new HashSet<HNode>();
 398
 399     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 400       HNode endNode = (HNode) iterator.next();
 401       Set<HNode> connectedToEndNodeSet = scGraph.getIncomingNodeSet(endNode);
 402
 403       for (Iterator iterator2 = connectedToEndNodeSet.iterator(); iterator2.hasNext();) {
 404         HNode curNode = (HNode) iterator2.next();
 405         if (recurConnectedFromStartNode(scGraph, startNode, curNode, new HashSet<HNode>())) {
 406           newStartNodeSet.add(curNode);
 407         }
 408       }
 409     }
 410
 411     System.out.println("newStartNodeSet=" + newStartNodeSet);
 412
 413     if (newStartNodeSet.size() == 0) {
 414       newStartNodeSet.add(startNode);
 415     }
 416
 417     return newStartNodeSet.iterator().next();
 418   }
 419
 420   private boolean recurConnectedFromStartNode(HierarchyGraph scGraph, HNode startNode,
 421       HNode curNode, Set<HNode> visited) {
 422     // return true if curNode is transitively connected from the startNode
 423
 424     boolean isConnected = false;
 425     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 426     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 427       HNode in = (HNode) iterator.next();
 428       if (in.equals(startNode)) {
 429         return true;
 430       } else {
 431         visited.add(in);
 432         isConnected |= recurConnectedFromStartNode(scGraph, startNode, in, visited);
 433       }
 434     }
 435
 436     return isConnected;
 437   }
 438
 439   private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 440       HNode startNode, HNode endNode) {
 441     System.out.println("getDirectlyReachableNodeFromStartNodeReachToEndNode start=" + startNode
 442         + " end=" + endNode);
 443     Set<HNode> connected = new HashSet<HNode>();
 444     recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected);
 445     if (connected.size() == 0) {
 446       connected.add(endNode);
 447     }
 448     System.out.println("connected=" + connected);
 449
 450     return connected.iterator().next();
 451   }
 452
 453   private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 454       HNode startNode, HNode curNode, Set<HNode> connected) {
 455
 456     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 457     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 458       HNode inNode = (HNode) iterator.next();
 459       if (inNode.equals(startNode)) {
 460         connected.add(curNode);
 461       } else {
 462         recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected);
 463       }
 464     }
 465
 466   }
 467
 468   private void recurDFSNormalNode(Descriptor desc, SSJavaLattice<String> lattice, HNode startNode,
 469       Set<HNode> endNodeSet, Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc,
 470       int idx, LocationSummary locSummary, HNode curNode) {
 471
 472     TripleItem item = new TripleItem(startNode, endNodeSet, idx);
 473     // System.out.println("item=" + item);
 474     if (!mapIntermediateLoc.containsKey(item)) {
 475       // need to create a new intermediate location in the lattice
 476       String newLocName = "ILOC" + (LocationInference.locSeed++);
 477       String above;
 478       if (idx == 1) {
 479         above = startNode.getName();
 480       } else {
 481         int prevIdx = idx - 1;
 482         TripleItem prevItem = new TripleItem(startNode, endNodeSet, prevIdx);
 483         above = mapIntermediateLoc.get(prevItem);
 484       }
 485
 486       Set<String> belowSet = new HashSet<String>();
 487       for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 488         HNode endNode = (HNode) iterator.next();
 489         String locName;
 490         if (locSummary.getMapHNodeNameToLocationName().containsKey(endNode.getName())) {
 491           locName = locSummary.getLocationName(endNode.getName());
 492         } else {
 493           locName = endNode.getName();
 494         }
 495         belowSet.add(locName);
 496       }
 497       lattice.insertNewLocationBetween(above, belowSet, newLocName);
 498
 499       mapIntermediateLoc.put(item, newLocName);
 500     }
 501
 502     String locName = mapIntermediateLoc.get(item);
 503     HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
 504
 505     if (curNode.isSharedNode()) {
 506       // if the current node is shared location, add a shared location to the lattice later
 507       mapSharedNodeToTripleItem.put(curNode, item);
 508     } else {
 509       Set<Descriptor> descSet = graph.getDescSetOfNode(curNode);
 510       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 511         Descriptor d = (Descriptor) iterator.next();
 512         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 513       }
 514       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 515     }
 516
 517     System.out.println("-TripleItem=" + item);
 518     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
 519         + " locName=" + locName);
 520
 521     Set<HNode> outSet = graph.getOutgoingNodeSet(curNode);
 522     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 523       HNode outNode = (HNode) iterator2.next();
 524       if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
 525         visited.add(outNode);
 526         recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 527             idx + 1, locSummary, outNode);
 528       } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) {
 529         expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 530       }
 531     }
 532
 533   }
 534
 535   private void recurDFS(Descriptor desc, SSJavaLattice<String> lattice,
 536       HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
 537       Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode curNode) {
 538
 539     TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx);
 540
 541     if (!mapIntermediateLoc.containsKey(item)) {
 542       // need to create a new intermediate location in the lattice
 543       String above;
 544       if (idx == 1) {
 545         String newLocName = combinationNodeInSCGraph.getName();
 546         mapIntermediateLoc.put(item, newLocName);
 547       } else {
 548         String newLocName = "ILOC" + (LocationInference.locSeed++);
 549         int prevIdx = idx - 1;
 550         TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
 551         above = mapIntermediateLoc.get(prevItem);
 552
 553         Set<String> belowSet = new HashSet<String>();
 554         for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 555           HNode endNode = (HNode) iterator.next();
 556           belowSet.add(endNode.getName());
 557         }
 558         lattice.insertNewLocationBetween(above, belowSet, newLocName);
 559         mapIntermediateLoc.put(item, newLocName);
 560       }
 561
 562     }
 563
 564     // TODO
 565     // Do we need to skip the combination node and assign a shared location to the next node?
 566     // if (idx == 1 && curNode.isSharedNode()) {
 567     // System.out.println("THE FIRST COMBINATION NODE EXPANSION IS SHARED!");
 568     // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, mapIntermediateLoc,
 569     // idx + 1, locSummary, curNode);
 570     // return;
 571     // }
 572
 573     HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
 574     String locName = mapIntermediateLoc.get(item);
 575     if (curNode.isSharedNode()) {
 576       // if the current node is shared location, add a shared location to the lattice later
 577       mapSharedNodeToTripleItem.put(curNode, item);
 578     } else {
 579       Set<Descriptor> descSet = graph.getDescSetOfNode(curNode);
 580       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 581         Descriptor d = (Descriptor) iterator.next();
 582         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 583       }
 584       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 585     }
 586
 587     System.out.println("-TripleItem=" + item);
 588     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
 589         + " locName=" + locName);
 590
 591     Set<HNode> outSet = graph.getOutgoingNodeSet(curNode);
 592     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 593       HNode outNode = (HNode) iterator2.next();
 594       // System.out.println("recurDFS outNode=" + outNode);
 595       // System.out.println("---cur combinationNodeInSCGraph=" + combinationNodeInSCGraph);
 596       // System.out.println("---outNode combinationNodeInSCGraph="
 597       // + getCombinationNodeInSCGraph(desc, outNode));
 598       if (!outNode.isSkeleton() && !visited.contains(outNode)) {
 599         if (outNode.isCombinationNode()) {
 600           // check whether the next combination node is different from the current node
 601           if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
 602             visited.add(outNode);
 603             recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
 604                 mapIntermediateLoc, idx + 1, locSummary, outNode);
 605           } else {
 606             expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 607           }
 608         }
 609
 610       }
 611     }
 612
 613   }
 614
 615   private String generateElementName(BasisSet basisSet, HierarchyGraph inputGraph,
 616       Map<Set<Integer>, String> mapF2LocName, Set<Integer> F) {
 617
 618     if (mapF2LocName.containsKey(F)) {
 619       return mapF2LocName.get(F);
 620     }
 621
 622     HNode node = basisSet.getHNode(F);
 623     if (node != null) {
 624       mapF2LocName.put(F, node.getName());
 625       return node.getName();
 626     } else {
 627       if (inputGraph.BASISTOPELEMENT.equals(F)) {
 628         return SSJavaAnalysis.BOTTOM;
 629       } else {
 630         String str = "LOC" + (LocationInference.locSeed++);
 631         mapF2LocName.put(F, str);
 632         return str;
 633       }
 634     }
 635   }
 636
 637   private void resetCount(Map<Set<Integer>, Integer> mapFtoCount, Family family) {
 638     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
 639       Set<Integer> F = iter.next();
 640       mapFtoCount.put(F, 0);
 641     }
 642   }
 643
 644   private Map<Set<Integer>, Set<Set<Integer>>> coveringGraph(BasisSet basisSet, Family family) {
 645
 646     Map<Set<Integer>, Integer> mapFtoCount = new HashMap<Set<Integer>, Integer>();
 647     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = new HashMap<Set<Integer>, Set<Set<Integer>>>();
 648
 649     // initialize COUNT(F) to 0 for all elements of the family
 650     resetCount(mapFtoCount, family);
 651
 652     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
 653       Set<Integer> F = iter.next();
 654       Set<HNode> gammaF = family.getGamma(F);
 655
 656       Set<HNode> curHNodeSet = basisSet.getHNodeSet();
 657       curHNodeSet.removeAll(gammaF);
 658       Set<Set<Integer>> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet);
 659
 660       for (Iterator iterator = Bset.iterator(); iterator.hasNext();) {
 661         Set<Integer> B = (Set<Integer>) iterator.next();
 662
 663         Set<Integer> Fprime = new HashSet<Integer>();
 664         Fprime.addAll(F);
 665         Fprime.addAll(B);
 666
 667         // COUNT(F')++;
 668         mapFtoCount.put(Fprime, mapFtoCount.get(Fprime) + 1);
 669
 670         // if |gamma(F')|==COUNT(F') + |gamma(F)|
 671         int numGammaFprime = family.getGamma(Fprime).size();
 672         int countFprime = mapFtoCount.get(Fprime);
 673         int numGammaF = family.getGamma(F).size();
 674         if (numGammaFprime == (countFprime + numGammaF)) {
 675           // ImSucc(F)=IMSucc(F) union F'
 676           addImSucc(mapImSucc, F, Fprime);
 677         }
 678
 679       }
 680       resetCount(mapFtoCount, family);
 681     }
 682
 683     // System.out.println("mapImSucc=" + mapImSucc);
 684
 685     return mapImSucc;
 686   }
 687
 688   private Set<Set<Integer>> getImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F) {
 689     if (!mapImSucc.containsKey(F)) {
 690       mapImSucc.put(F, new HashSet<Set<Integer>>());
 691     }
 692     return mapImSucc.get(F);
 693   }
 694
 695   private void addImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F,
 696       Set<Integer> Fprime) {
 697
 698     if (!mapImSucc.containsKey(F)) {
 699       mapImSucc.put(F, new HashSet<Set<Integer>>());
 700     }
 701
 702     mapImSucc.get(F).add(Fprime);
 703
 704   }
 705
 706   private Family generateFamily(BasisSet basisSet) {
 707
 708     Family family = new Family();
 709
 710     for (Iterator<Set<Integer>> iterator = basisSet.basisIterator(); iterator.hasNext();) {
 711       Set<Integer> B = iterator.next();
 712
 713       Set<Pair<Set<Integer>, Set<HNode>>> tobeadded = new HashSet<Pair<Set<Integer>, Set<HNode>>>();
 714
 715       for (Iterator<Set<Integer>> iterator2 = family.FIterator(); iterator2.hasNext();) {
 716         Set<Integer> F = iterator2.next();
 717
 718         Set<Integer> Fprime = new HashSet<Integer>();
 719         Fprime.addAll(F);
 720         Fprime.addAll(B);
 721
 722         Set<HNode> gammaFPrimeSet = new HashSet<HNode>();
 723         gammaFPrimeSet.addAll(family.getGamma(F));
 724         gammaFPrimeSet.add(basisSet.getHNode(B));
 725
 726         if (!family.containsF(Fprime)) {
 727           Pair<Set<Integer>, Set<HNode>> pair =
 728               new Pair<Set<Integer>, Set<HNode>>(Fprime, gammaFPrimeSet);
 729           tobeadded.add(pair);
 730         } else {
 731           family.updateGammaF(Fprime, gammaFPrimeSet);
 732         }
 733       }
 734
 735       for (Iterator<Pair<Set<Integer>, Set<HNode>>> iterator2 = tobeadded.iterator(); iterator2
 736           .hasNext();) {
 737         Pair<Set<Integer>, Set<HNode>> pair = iterator2.next();
 738         family.addFElement(pair.getFirst());
 739         family.updateGammaF(pair.getFirst(), pair.getSecond());
 740       }
 741
 742     }
 743     return family;
 744   }
 745
 746   private void debug_print(HierarchyGraph inputGraph) {
 747     System.out.println("\nBuild Lattice:" + inputGraph.getName());
 748     // System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex());
 749     // System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
 750   }
 751
 752 }
 753
 754 class Identifier {
 755   public HNode node;
 756   public int idx;
 757
 758   public Identifier(HNode n, int i) {
 759     node = n;
 760     idx = i;
 761   }
 762
 763   public int hashCode() {
 764     return node.hashCode() + idx;
 765   }
 766
 767   public boolean equals(Object obj) {
 768
 769     if (obj instanceof Identifier) {
 770       Identifier in = (Identifier) obj;
 771       if (node.equals(in.node) && idx == in.idx) {
 772         return true;
 773       }
 774     }
 775
 776     return false;
 777   }
 778
 779 }
 780
 781 class TripleItem {
 782   public HNode higherNode;
 783   public Set<HNode> lowerNodeSet;
 784   public int idx;
 785   public boolean isShared;
 786
 787   public TripleItem(HNode h, Set<HNode> l, int i) {
 788     higherNode = h;
 789     lowerNodeSet = l;
 790     idx = i;
 791     isShared = false;
 792   }
 793
 794   public void setShared(boolean in) {
 795     this.isShared = in;
 796   }
 797
 798   public boolean isShared() {
 799     return isShared;
 800   }
 801
 802   public int hashCode() {
 803
 804     int h = 0;
 805     if (higherNode != null) {
 806       h = higherNode.hashCode();
 807     }
 808
 809     if (isShared) {
 810       h++;
 811     }
 812
 813     return h + lowerNodeSet.hashCode() + idx;
 814   }
 815
 816   public boolean equals(Object obj) {
 817
 818     if (obj instanceof TripleItem) {
 819       TripleItem in = (TripleItem) obj;
 820       if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode)))
 821           && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx && isShared == in.isShared()) {
 822         return true;
 823       }
 824     }
 825
 826     return false;
 827   }
 828
 829   public String toString() {
 830     String rtr = higherNode + "-" + idx + "->" + lowerNodeSet;
 831     if (isShared) {
 832       rtr += " S";
 833     }
 834     return rtr;
 835   }
 836 }