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