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       mapSharedNodeToTripleItem.put(curNode, item);
 576     } else {
 577       Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
 578       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 579         Descriptor d = (Descriptor) iterator.next();
 580         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 581       }
 582       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 583     }
 584
 585     System.out.println("-TripleItem normal=" + item);
 586     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
 587         + " locName=" + locName + "  isC=" + curNode.isCombinationNode());
 588
 589     Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
 590     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 591       HNode outNode = (HNode) iterator2.next();
 592
 593       Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
 594       System.out.println("outNode=" + outNode);
 595       System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode);
 596
 597       if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
 598         Pair<HNode, HNode> pair = new Pair(startNode, outNode);
 599         if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) {
 600           visited.add(outNode);
 601           int newidx = getCurrentHighestIndex(pair, idx + 1);
 602           // int newidx = getCurrentHighestIndex(outNode, idx + 1);
 603           recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 604               newidx, locSummary, outNode);
 605           // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 606           // idx + 1, locSummary, outNode);
 607         } else {
 608           updateHighestIndex(pair, idx + 1);
 609           // updateHighestIndex(outNode, idx + 1);
 610           System.out.println("NOT RECUR");
 611         }
 612       } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) {
 613         if (needToExpandCombinationNode(desc, outNode)) {
 614           System.out.println("NEED TO");
 615           expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 616         } else {
 617           System.out.println("NOT NEED TO");
 618         }
 619       }
 620
 621     }
 622
 623   }
 624
 625   private void recurDFS(Descriptor desc, SSJavaLattice<String> lattice,
 626       HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
 627       Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode curNode) {
 628
 629     TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx);
 630
 631     if (!mapIntermediateLoc.containsKey(item)) {
 632       // need to create a new intermediate location in the lattice
 633       String above;
 634       if (idx == 1) {
 635         String newLocName = combinationNodeInSCGraph.getName();
 636         mapIntermediateLoc.put(item, newLocName);
 637       } else {
 638         String newLocName = "ILOC" + (LocationInference.locSeed++);
 639         int prevIdx = idx - 1;
 640         TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
 641         above = mapIntermediateLoc.get(prevItem);
 642
 643         Set<String> belowSet = new HashSet<String>();
 644         for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 645           HNode endNode = (HNode) iterator.next();
 646           belowSet.add(endNode.getName());
 647         }
 648         lattice.insertNewLocationBetween(above, belowSet, newLocName);
 649         mapIntermediateLoc.put(item, newLocName);
 650       }
 651
 652     }
 653
 654     // TODO
 655     // Do we need to skip the combination node and assign a shared location to the next node?
 656     // if (idx == 1 && curNode.isSharedNode()) {
 657     // System.out.println("THE FIRST COMBINATION NODE EXPANSION IS SHARED!");
 658     // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, mapIntermediateLoc,
 659     // idx + 1, locSummary, curNode);
 660     // return;
 661     // }
 662
 663     HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 664     String locName = mapIntermediateLoc.get(item);
 665     if (curNode.isSharedNode()) {
 666       // if the current node is shared location, add a shared location to the lattice later
 667       mapSharedNodeToTripleItem.put(curNode, item);
 668     } else {
 669       Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
 670       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 671         Descriptor d = (Descriptor) iterator.next();
 672         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 673       }
 674       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 675     }
 676
 677     System.out.println("-TripleItem=" + item);
 678     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
 679         + " locName=" + locName);
 680
 681     Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
 682     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 683       HNode outNode = (HNode) iterator2.next();
 684       System.out.println("---recurDFS outNode=" + outNode);
 685       System.out.println("---cur combinationNodeInSCGraph=" + combinationNodeInSCGraph);
 686       System.out.println("---outNode combinationNodeInSCGraph="
 687           + getCombinationNodeInSCGraph(desc, outNode));
 688
 689       if (!outNode.isSkeleton() && !visited.contains(outNode)) {
 690         if (outNode.isCombinationNode()) {
 691
 692           Set<HNode> combineSkeletonNodeSet =
 693               simpleHierarchyGraph.getCombineSetByCombinationNode(outNode);
 694           Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
 695           // extract nodes belong to the same combine node
 696           Set<HNode> incomingCombinedHNodeSet = new HashSet<HNode>();
 697           for (Iterator iterator = incomingHNodeSetToOutNode.iterator(); iterator.hasNext();) {
 698             HNode inNode = (HNode) iterator.next();
 699             if (combineSkeletonNodeSet.contains(inNode)) {
 700               incomingCombinedHNodeSet.add(inNode);
 701             }
 702           }
 703           System.out.println("-----incomingCombinedHNodeSet=" + incomingCombinedHNodeSet);
 704
 705           // check whether the next combination node is different from the current node
 706           if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
 707             Pair<HNode, HNode> pair = new Pair(combinationNodeInSCGraph, outNode);
 708             if (visited.containsAll(incomingCombinedHNodeSet)) {
 709               visited.add(outNode);
 710               System.out.println("-------curIdx=" + (idx + 1));
 711
 712               int newIdx = getCurrentHighestIndex(pair, idx + 1);
 713               // int newIdx = getCurrentHighestIndex(outNode, idx + 1);
 714               System.out.println("-------newIdx=" + newIdx);
 715               recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
 716                   mapIntermediateLoc, newIdx, locSummary, outNode);
 717               // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
 718               // mapIntermediateLoc, idx + 1, locSummary, outNode);
 719             } else {
 720               updateHighestIndex(pair, idx + 1);
 721               // updateHighestIndex(outNode, idx + 1);
 722               System.out.println("-----NOT RECUR!");
 723             }
 724           } else {
 725             if (needToExpandCombinationNode(desc, outNode)) {
 726               System.out.println("NEED TO");
 727               expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 728             } else {
 729               System.out.println("NOT NEED TO");
 730             }
 731
 732           }
 733         }
 734       }
 735       // }
 736
 737     }
 738
 739   }
 740
 741   private int getCurrentHighestIndex(Pair<HNode, HNode> pair, int curIdx) {
 742     int recordedIdx = getCurrentHighestIndex(pair);
 743     if (recordedIdx > curIdx) {
 744       return recordedIdx;
 745     } else {
 746       return curIdx;
 747     }
 748   }
 749
 750   private int getCurrentHighestIndex(HNode node, int curIdx) {
 751     int recordedIdx = getCurrentHighestIndex(node);
 752     if (recordedIdx > curIdx) {
 753       return recordedIdx;
 754     } else {
 755       return curIdx;
 756     }
 757   }
 758
 759   private int getCurrentHighestIndex(Pair<HNode, HNode> pair) {
 760     if (!mapItemToHighestIndex.containsKey(pair)) {
 761       mapItemToHighestIndex.put(pair, new Integer(-1));
 762     }
 763     return mapItemToHighestIndex.get(pair).intValue();
 764   }
 765
 766   private void updateHighestIndex(Pair<HNode, HNode> pair, int idx) {
 767     if (idx > getCurrentHighestIndex(pair)) {
 768       mapItemToHighestIndex.put(pair, new Integer(idx));
 769     }
 770   }
 771
 772   private int getCurrentHighestIndex(HNode node) {
 773     if (!mapHNodeToHighestIndex.containsKey(node)) {
 774       mapHNodeToHighestIndex.put(node, new Integer(-1));
 775     }
 776     return mapHNodeToHighestIndex.get(node).intValue();
 777   }
 778
 779   private void updateHighestIndex(HNode node, int idx) {
 780     if (idx > getCurrentHighestIndex(node)) {
 781       mapHNodeToHighestIndex.put(node, new Integer(idx));
 782     }
 783   }
 784
 785   private String generateElementName(BasisSet basisSet, HierarchyGraph inputGraph,
 786       Map<Set<Integer>, String> mapF2LocName, Set<Integer> F) {
 787
 788     if (mapF2LocName.containsKey(F)) {
 789       return mapF2LocName.get(F);
 790     }
 791
 792     HNode node = basisSet.getHNode(F);
 793     if (node != null) {
 794       mapF2LocName.put(F, node.getName());
 795       return node.getName();
 796     } else {
 797       if (inputGraph.BASISTOPELEMENT.equals(F)) {
 798         return SSJavaAnalysis.BOTTOM;
 799       } else {
 800         String str = "LOC" + (LocationInference.locSeed++);
 801         mapF2LocName.put(F, str);
 802         return str;
 803       }
 804     }
 805   }
 806
 807   private void resetCount(Map<Set<Integer>, Integer> mapFtoCount, Family family) {
 808     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
 809       Set<Integer> F = iter.next();
 810       mapFtoCount.put(F, 0);
 811     }
 812   }
 813
 814   private Map<Set<Integer>, Set<Set<Integer>>> coveringGraph(BasisSet basisSet, Family family) {
 815
 816     Map<Set<Integer>, Integer> mapFtoCount = new HashMap<Set<Integer>, Integer>();
 817     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = new HashMap<Set<Integer>, Set<Set<Integer>>>();
 818
 819     // initialize COUNT(F) to 0 for all elements of the family
 820     resetCount(mapFtoCount, family);
 821
 822     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
 823       Set<Integer> F = iter.next();
 824       Set<HNode> gammaF = family.getGamma(F);
 825
 826       Set<HNode> curHNodeSet = basisSet.getHNodeSet();
 827       curHNodeSet.removeAll(gammaF);
 828       Set<Set<Integer>> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet);
 829
 830       for (Iterator iterator = Bset.iterator(); iterator.hasNext();) {
 831         Set<Integer> B = (Set<Integer>) iterator.next();
 832
 833         Set<Integer> Fprime = new HashSet<Integer>();
 834         Fprime.addAll(F);
 835         Fprime.addAll(B);
 836
 837         // COUNT(F')++;
 838         mapFtoCount.put(Fprime, mapFtoCount.get(Fprime) + 1);
 839
 840         // if |gamma(F')|==COUNT(F') + |gamma(F)|
 841         int numGammaFprime = family.getGamma(Fprime).size();
 842         int countFprime = mapFtoCount.get(Fprime);
 843         int numGammaF = family.getGamma(F).size();
 844         if (numGammaFprime == (countFprime + numGammaF)) {
 845           // ImSucc(F)=IMSucc(F) union F'
 846           addImSucc(mapImSucc, F, Fprime);
 847         }
 848
 849       }
 850       resetCount(mapFtoCount, family);
 851     }
 852
 853     // System.out.println("mapImSucc=" + mapImSucc);
 854
 855     return mapImSucc;
 856   }
 857
 858   private Set<Set<Integer>> getImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F) {
 859     if (!mapImSucc.containsKey(F)) {
 860       mapImSucc.put(F, new HashSet<Set<Integer>>());
 861     }
 862     return mapImSucc.get(F);
 863   }
 864
 865   private void addImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F,
 866       Set<Integer> Fprime) {
 867
 868     if (!mapImSucc.containsKey(F)) {
 869       mapImSucc.put(F, new HashSet<Set<Integer>>());
 870     }
 871
 872     mapImSucc.get(F).add(Fprime);
 873
 874   }
 875
 876   private Family generateFamily(BasisSet basisSet) {
 877
 878     Family family = new Family();
 879
 880     for (Iterator<Set<Integer>> iterator = basisSet.basisIterator(); iterator.hasNext();) {
 881       Set<Integer> B = iterator.next();
 882
 883       Set<Pair<Set<Integer>, Set<HNode>>> tobeadded = new HashSet<Pair<Set<Integer>, Set<HNode>>>();
 884
 885       for (Iterator<Set<Integer>> iterator2 = family.FIterator(); iterator2.hasNext();) {
 886         Set<Integer> F = iterator2.next();
 887
 888         Set<Integer> Fprime = new HashSet<Integer>();
 889         Fprime.addAll(F);
 890         Fprime.addAll(B);
 891
 892         Set<HNode> gammaFPrimeSet = new HashSet<HNode>();
 893         gammaFPrimeSet.addAll(family.getGamma(F));
 894         gammaFPrimeSet.add(basisSet.getHNode(B));
 895
 896         if (!family.containsF(Fprime)) {
 897           Pair<Set<Integer>, Set<HNode>> pair =
 898               new Pair<Set<Integer>, Set<HNode>>(Fprime, gammaFPrimeSet);
 899           tobeadded.add(pair);
 900         } else {
 901           family.updateGammaF(Fprime, gammaFPrimeSet);
 902         }
 903       }
 904
 905       for (Iterator<Pair<Set<Integer>, Set<HNode>>> iterator2 = tobeadded.iterator(); iterator2
 906           .hasNext();) {
 907         Pair<Set<Integer>, Set<HNode>> pair = iterator2.next();
 908         family.addFElement(pair.getFirst());
 909         family.updateGammaF(pair.getFirst(), pair.getSecond());
 910       }
 911
 912     }
 913     return family;
 914   }
 915
 916   private void debug_print(HierarchyGraph inputGraph) {
 917     System.out.println("\nBuild Lattice:" + inputGraph.getName());
 918     // System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex());
 919     // System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
 920   }
 921
 922 }
 923
 924 class Identifier {
 925   public HNode node;
 926   public int idx;
 927
 928   public Identifier(HNode n, int i) {
 929     node = n;
 930     idx = i;
 931   }
 932
 933   public int hashCode() {
 934     return node.hashCode() + idx;
 935   }
 936
 937   public boolean equals(Object obj) {
 938
 939     if (obj instanceof Identifier) {
 940       Identifier in = (Identifier) obj;
 941       if (node.equals(in.node) && idx == in.idx) {
 942         return true;
 943       }
 944     }
 945
 946     return false;
 947   }
 948
 949 }
 950
 951 class TripleItem {
 952   public HNode higherNode;
 953   public Set<HNode> lowerNodeSet;
 954   public int idx;
 955   public boolean isShared;
 956
 957   public TripleItem(HNode h, Set<HNode> l, int i) {
 958     higherNode = h;
 959     lowerNodeSet = l;
 960     idx = i;
 961     isShared = false;
 962   }
 963
 964   public void setShared(boolean in) {
 965     this.isShared = in;
 966   }
 967
 968   public boolean isShared() {
 969     return isShared;
 970   }
 971
 972   public int hashCode() {
 973
 974     int h = 0;
 975     if (higherNode != null) {
 976       h = higherNode.hashCode();
 977     }
 978
 979     if (isShared) {
 980       h++;
 981     }
 982
 983     return h + lowerNodeSet.hashCode() + idx;
 984   }
 985
 986   public boolean equals(Object obj) {
 987
 988     if (obj instanceof TripleItem) {
 989       TripleItem in = (TripleItem) obj;
 990       if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode)))
 991           && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx && isShared == in.isShared()) {
 992         return true;
 993       }
 994     }
 995
 996     return false;
 997   }
 998
 999   public String toString() {
1000     String rtr = higherNode + "-" + idx + "->" + lowerNodeSet;
1001     if (isShared) {
1002       rtr += " S";
1003     }
1004     return rtr;
1005   }
1006 }