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