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