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