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