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     mapSharedNodeToTripleItem.clear();
 170
 171     HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 172     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 173     LocationSummary locSummary = infer.getLocationSummary(desc);
 174     SSJavaLattice<String> lattice = skeletonLattice.clone();
 175     Set<HNode> visited = new HashSet<HNode>();
 176     Set<HNode> scNodeSet = scGraph.getNodeSet();
 177
 178     Map<TripleItem, String> mapIntermediateLoc = new HashMap<TripleItem, String>();
 179
 180     for (Iterator iterator = scNodeSet.iterator(); iterator.hasNext();) {
 181       HNode scNode = (HNode) iterator.next();
 182       Set<HNode> outHierarchyNodeSet = hierarchyGraph.getOutgoingNodeSet(scNode);
 183       for (Iterator iterator2 = outHierarchyNodeSet.iterator(); iterator2.hasNext();) {
 184         HNode outHierarchyNode = (HNode) iterator2.next();
 185
 186         if (!visited.contains(outHierarchyNode)) {
 187
 188           if (!outHierarchyNode.isCombinationNode() && !outHierarchyNode.isSkeleton()) {
 189             visited.add(outHierarchyNode);
 190             Set<HNode> outSCNodeSet = scGraph.getOutgoingNodeSet(scNode);
 191
 192             if (outSCNodeSet.size() > 0) {
 193               // follows the straight line up to another skeleton/combination node
 194               outSCNodeSet = removeTransitivelyReachToNode(desc, scNode, outSCNodeSet);
 195             } else if (outSCNodeSet.size() == 0) {
 196               // the outNode is (directly/transitively) connected to the bottom node
 197               // therefore, we just add a dummy bottom HNode to the endCombNodeSet.
 198               outSCNodeSet.add(LocationInference.BOTTOMHNODE);
 199             }
 200
 201             recurDFVisitNormalNode(scNode, outSCNodeSet, outHierarchyNode, 1, desc, lattice,
 202                 visited, locSummary, mapIntermediateLoc);
 203           } else if (outHierarchyNode.isCombinationNode()) {
 204             visited.add(outHierarchyNode);
 205             expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary,
 206                 outHierarchyNode);
 207           }
 208
 209         }
 210
 211       }
 212
 213     }
 214
 215     // add shared locations
 216     Set<HNode> sharedNodeSet = mapSharedNodeToTripleItem.keySet();
 217     for (Iterator iterator = sharedNodeSet.iterator(); iterator.hasNext();) {
 218       HNode sharedNode = (HNode) iterator.next();
 219       TripleItem item = mapSharedNodeToTripleItem.get(sharedNode);
 220       String nonSharedLocName = mapIntermediateLoc.get(item);
 221       // System.out.println("sharedNode=" + sharedNode + "    locName=" + nonSharedLocName);
 222
 223       String newLocName;
 224       if (locSummary.getHNodeNameSetByLatticeLoationName(nonSharedLocName) != null
 225           && !lattice.isSharedLoc(nonSharedLocName)) {
 226         // need to generate a new shared location in the lattice, which is one level lower than the
 227         // 'locName' location
 228         newLocName = "ILOC" + (LocationInference.locSeed++);
 229
 230         // Set<String> aboveElementSet = getAboveElementSet(lattice, locName);
 231         Set<String> belowElementSet = new HashSet<String>();
 232         belowElementSet.addAll(lattice.get(nonSharedLocName));
 233
 234         // System.out.println("nonSharedLocName=" + nonSharedLocName + "   belowElementSet="
 235         // + belowElementSet + "  newLocName=" + newLocName);
 236
 237         lattice.insertNewLocationBetween(nonSharedLocName, belowElementSet, newLocName);
 238       } else {
 239         newLocName = nonSharedLocName;
 240       }
 241
 242       lattice.addSharedLoc(newLocName);
 243       HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
 244       Set<Descriptor> descSet = graph.getDescSetOfNode(sharedNode);
 245       for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
 246         Descriptor d = (Descriptor) iterator2.next();
 247         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), newLocName);
 248       }
 249       locSummary.addMapHNodeNameToLocationName(sharedNode.getName(), newLocName);
 250
 251     }
 252
 253     return lattice;
 254   }
 255
 256   private void recurDFVisitNormalNode(HNode scStartNode, Set<HNode> scEndNodeSet,
 257       HNode curHierarchyNode, int idx, Descriptor desc, SSJavaLattice<String> lattice,
 258       Set<HNode> visited, LocationSummary locSummary, Map<TripleItem, String> mapIntermediateLoc) {
 259
 260     TripleItem item = new TripleItem(scStartNode, scEndNodeSet, idx);
 261     // System.out.println("item=" + item);
 262     if (!mapIntermediateLoc.containsKey(item)) {
 263       // need to create a new intermediate location in the lattice
 264       String newLocName = "ILOC" + (LocationInference.locSeed++);
 265       String above;
 266       if (idx == 1) {
 267         above = scStartNode.getName();
 268       } else {
 269         int prevIdx = idx - 1;
 270         TripleItem prevItem = new TripleItem(scStartNode, scEndNodeSet, prevIdx);
 271         above = mapIntermediateLoc.get(prevItem);
 272       }
 273
 274       Set<String> belowSet = new HashSet<String>();
 275       for (Iterator iterator = scEndNodeSet.iterator(); iterator.hasNext();) {
 276         HNode endNode = (HNode) iterator.next();
 277         String locName;
 278         if (locSummary.getMapHNodeNameToLocationName().containsKey(endNode.getName())) {
 279           locName = locSummary.getLocationName(endNode.getName());
 280         } else {
 281           locName = endNode.getName();
 282         }
 283         belowSet.add(locName);
 284       }
 285       lattice.insertNewLocationBetween(above, belowSet, newLocName);
 286
 287       mapIntermediateLoc.put(item, newLocName);
 288     }
 289
 290     String curLocName = mapIntermediateLoc.get(item);
 291     HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 292
 293     if (curHierarchyNode.isSharedNode()) {
 294       // if the current node is shared location, add a shared location to the lattice later
 295       mapSharedNodeToTripleItem.put(curHierarchyNode, item);
 296     } else {
 297       Set<Descriptor> descSet = hierarchyGraph.getDescSetOfNode(curHierarchyNode);
 298       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 299         Descriptor d = (Descriptor) iterator.next();
 300         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), curLocName);
 301       }
 302       locSummary.addMapHNodeNameToLocationName(curHierarchyNode.getName(), curLocName);
 303     }
 304
 305     System.out.println("-TripleItem normal=" + item);
 306     System.out.println("-curNode=" + curHierarchyNode.getName() + " S="
 307         + curHierarchyNode.isSharedNode() + " locName=" + curLocName + "  isC="
 308         + curHierarchyNode.isCombinationNode());
 309
 310     Set<HNode> outSet = hierarchyGraph.getOutgoingNodeSet(curHierarchyNode);
 311     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 312       HNode outHierarchyNodeFromCurNode = (HNode) iterator2.next();
 313
 314       // Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
 315       System.out.println("outHierarchyNodeFromCurNode=" + outHierarchyNodeFromCurNode);
 316       // System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode);
 317
 318       if (outHierarchyNodeFromCurNode.isSkeleton()
 319           || outHierarchyNodeFromCurNode.isCombinationNode()) {
 320         String lowerLocName = locSummary.getLocationName(outHierarchyNodeFromCurNode.getName());
 321         lattice.addRelationHigherToLower(curLocName, lowerLocName);
 322       } else {
 323         if (visited.containsAll(hierarchyGraph.getIncomingNodeSet(outHierarchyNodeFromCurNode))) {
 324           visited.add(outHierarchyNodeFromCurNode);
 325           int newidx = getCurrentHighestIndex(outHierarchyNodeFromCurNode, idx + 1);
 326           recurDFVisitNormalNode(scStartNode, scEndNodeSet, outHierarchyNodeFromCurNode, newidx,
 327               desc, lattice, visited, locSummary, mapIntermediateLoc);
 328         } else {
 329           System.out.println("NOT RECUR");
 330           updateHighestIndex(outHierarchyNodeFromCurNode, idx + 1);
 331         }
 332       }
 333
 334       // if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
 335       // if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) {
 336       // visited.add(outNode);
 337       // int newidx = getCurrentHighestIndex(outNode, idx + 1);
 338       // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 339       // newidx, locSummary, outNode);
 340       // // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 341       // // idx + 1, locSummary, outNode);
 342       // } else {
 343       // updateHighestIndex(outNode, idx + 1);
 344       // System.out.println("NOT RECUR");
 345       // }
 346       // } else if (!outNode.isSkeleton() && outNode.isCombinationNode() &&
 347       // !visited.contains(outNode)) {
 348       // if (needToExpandCombinationNode(desc, outNode)) {
 349       // System.out.println("NEED TO");
 350       // expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 351       // } else {
 352       // System.out.println("NOT NEED TO");
 353       // }
 354       // }
 355
 356     }
 357
 358   }
 359
 360   private void recurDFVisitCombinationNode(HNode scCombNode, Set<HNode> scEndNodeSet,
 361       HNode curHierarchyCombNode, int idx, Descriptor desc, SSJavaLattice<String> lattice,
 362       Set<HNode> visited, LocationSummary locSummary, Map<TripleItem, String> mapIntermediateLoc) {
 363
 364     // Descriptor desc, SSJavaLattice<String> lattice,
 365     // HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
 366     // Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode
 367     // curNode) {
 368
 369     TripleItem item = new TripleItem(scCombNode, scEndNodeSet, idx);
 370
 371     if (!mapIntermediateLoc.containsKey(item)) {
 372       // need to create a new intermediate location in the lattice
 373       String above;
 374       if (idx == 1) {
 375         String newLocName = scCombNode.getName();
 376         mapIntermediateLoc.put(item, newLocName);
 377       } else {
 378         String newLocName = "ILOC" + (LocationInference.locSeed++);
 379         int prevIdx = idx - 1;
 380         TripleItem prevItem = new TripleItem(scCombNode, scEndNodeSet, prevIdx);
 381         above = mapIntermediateLoc.get(prevItem);
 382
 383         Set<String> belowSet = new HashSet<String>();
 384         for (Iterator iterator = scEndNodeSet.iterator(); iterator.hasNext();) {
 385           HNode endNode = (HNode) iterator.next();
 386           belowSet.add(endNode.getName());
 387         }
 388         lattice.insertNewLocationBetween(above, belowSet, newLocName);
 389         mapIntermediateLoc.put(item, newLocName);
 390       }
 391
 392     }
 393
 394     HierarchyGraph hierarchyNode = infer.getSimpleHierarchyGraph(desc);
 395     String locName = mapIntermediateLoc.get(item);
 396     if (curHierarchyCombNode.isSharedNode()) {
 397       // if the current node is shared location, add a shared location to the lattice later
 398       mapSharedNodeToTripleItem.put(curHierarchyCombNode, item);
 399     } else {
 400       Set<Descriptor> descSet = hierarchyNode.getDescSetOfNode(curHierarchyCombNode);
 401       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 402         Descriptor d = (Descriptor) iterator.next();
 403         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 404       }
 405       locSummary.addMapHNodeNameToLocationName(curHierarchyCombNode.getName(), locName);
 406     }
 407
 408     System.out.println("-TripleItem=" + item);
 409     System.out.println("-curNode=" + curHierarchyCombNode.getName() + " S="
 410         + curHierarchyCombNode.isSharedNode() + " locName=" + locName);
 411
 412     Set<HNode> outSet = hierarchyNode.getOutgoingNodeSet(curHierarchyCombNode);
 413     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 414       HNode outHierarchyNode = (HNode) iterator2.next();
 415
 416       System.out.println("---recurDFS outNode=" + outHierarchyNode);
 417       System.out.println("---outNode combinationNodeInSCGraph="
 418           + getCombinationNodeInSCGraph(desc, outHierarchyNode));
 419
 420       if (outHierarchyNode.isCombinationNode()) {
 421         HNode outCombinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, outHierarchyNode);
 422         if (outCombinationNodeInSCGraph.equals(scCombNode)) {
 423
 424           Set<HNode> combineSkeletonNodeSet =
 425               hierarchyNode.getCombineSetByCombinationNode(outHierarchyNode);
 426           Set<HNode> incomingHNodeSetToOutNode = hierarchyNode.getIncomingNodeSet(outHierarchyNode);
 427           // extract nodes belong to the same combine node
 428           Set<HNode> incomingCombinedHNodeSet = new HashSet<HNode>();
 429           for (Iterator iterator = incomingHNodeSetToOutNode.iterator(); iterator.hasNext();) {
 430             HNode inNode = (HNode) iterator.next();
 431             if (combineSkeletonNodeSet.contains(inNode)) {
 432               incomingCombinedHNodeSet.add(inNode);
 433             }
 434           }
 435           System.out.println("incomingCombinedHNodeSet=" + incomingCombinedHNodeSet);
 436           if (visited.containsAll(incomingCombinedHNodeSet)) {
 437             visited.add(outHierarchyNode);
 438             System.out.println("-------curIdx=" + (idx + 1));
 439             int newIdx = getCurrentHighestIndex(outHierarchyNode, idx + 1);
 440             System.out.println("-------newIdx=" + newIdx);
 441             recurDFVisitCombinationNode(scCombNode, scEndNodeSet, outHierarchyNode, newIdx, desc,
 442                 lattice, visited, locSummary, mapIntermediateLoc);
 443           } else {
 444             updateHighestIndex(outHierarchyNode, idx + 1);
 445             System.out.println("-----NOT RECUR!");
 446           }
 447
 448         }
 449       }
 450
 451     }
 452
 453   }
 454
 455   private void expandCombinationNode(Descriptor desc, SSJavaLattice<String> lattice,
 456       Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc, LocationSummary locSummary,
 457       HNode cnode) {
 458
 459     // expand the combination node 'outNode'
 460     // here we need to expand the corresponding combination location in the lattice
 461     HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
 462     Set<HNode> endNodeSet =
 463         infer.getSkeletonCombinationHierarchyGraph(desc).getOutgoingNodeSet(
 464             combinationNodeInSCGraph);
 465
 466     System.out.println("expandCombinationNode=" + cnode + "  cnode in scgraph="
 467         + combinationNodeInSCGraph);
 468     System.out.println("endnodeset=" + endNodeSet);
 469
 470     if (combinationNodeInSCGraph == null) {
 471       return;
 472     }
 473
 474     // HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 475     //
 476     // Set<HNode> combineSkeletonNodeSet = hierarchyGraph.getCombineSetByCombinationNode(cnode);
 477     //
 478     // // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
 479     //
 480     // Set<HNode> combinationNodeSet =
 481     // hierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 482     //
 483     // // System.out.println("combinationNodeSet=" + combinationNodeSet);
 484     //
 485     // Set<HNode> endNodeSetFromSimpleGraph =
 486     // hierarchyGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet);
 487     // // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 488     // Set<HNode> endCombNodeSet = new HashSet<HNode>();
 489     // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 490     // HNode endNode = (HNode) iterator3.next();
 491     // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 492     // }
 493
 494     visited.add(cnode);
 495
 496     // follows the straight line up to another skeleton/combination node
 497     if (endNodeSet.size() > 0) {
 498       // System.out.println("---endCombNodeSet=" + endCombNodeSet);
 499       endNodeSet = removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endNodeSet);
 500
 501       recurDFVisitCombinationNode(combinationNodeInSCGraph, endNodeSet, cnode, 1, desc, lattice,
 502           visited, locSummary, mapIntermediateLoc);
 503
 504     } else {
 505       endNodeSet.add(LocationInference.BOTTOMHNODE);
 506       // System.out.println("---endCombNodeSet is zero");
 507       // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 508       // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode));
 509       recurDFVisitCombinationNode(combinationNodeInSCGraph, endNodeSet, cnode, 1, desc, lattice,
 510           visited, locSummary, mapIntermediateLoc);
 511     }
 512
 513   }
 514
 515   public SSJavaLattice<String> insertIntermediateNodesToStraightLine2(Descriptor desc,
 516       SSJavaLattice<String> skeletonLattice) {
 517
 518     // perform DFS that starts from each skeleton/combination node and ends by another
 519     // skeleton/combination node
 520
 521     mapSharedNodeToTripleItem.clear();
 522
 523     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 524     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 525     LocationSummary locSummary = infer.getLocationSummary(desc);
 526
 527     SSJavaLattice<String> lattice = skeletonLattice.clone();
 528
 529     Set<HNode> visited = new HashSet<HNode>();
 530
 531     Set<HNode> nodeSet = simpleGraph.getNodeSet();
 532
 533     Map<TripleItem, String> mapIntermediateLoc = new HashMap<TripleItem, String>();
 534
 535     // System.out.println("*insert=" + desc);
 536     // System.out.println("***nodeSet=" + nodeSet);
 537     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 538       HNode node = (HNode) iterator.next();
 539       System.out.println("node=" + node);
 540
 541       if (node.isSkeleton() && (!visited.contains(node))) {
 542         visited.add(node);
 543
 544         Set<HNode> outSet = simpleGraph.getOutgoingNodeSet(node);
 545         for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 546           HNode outNode = (HNode) iterator2.next();
 547
 548           if (!outNode.isSkeleton()) {
 549             if (outNode.isCombinationNode()) {
 550               if (visited.containsAll(simpleGraph.getIncomingNodeSet(outNode))) {
 551                 // if (needToExpandCombinationNode(desc, outNode)) {
 552                 expandCombinationNode3(desc, lattice, visited, mapIntermediateLoc, locSummary,
 553                     outNode);
 554                 // }
 555               }
 556             } else {
 557               // we have a node that is neither combination or skeleton node
 558               // System.out.println("%%%skeleton node=" + node + "  outNode=" + outNode);
 559               HNode startNode = scGraph.getCurrentHNode(node);
 560
 561               // if (node.getDescriptor() != null) {
 562               // // node is a skeleton node and it might be merged into another node in the SC
 563               // graph.
 564               // startNode = scGraph.getHNode(node.getDescriptor());
 565               // } else {
 566               // // this node has already been merged before the SC graph.
 567               // startNode = node;
 568               // }
 569
 570               Set<HNode> endNodeSetFromSimpleGraph =
 571                   simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null);
 572
 573               // System.out.println("endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph
 574               // + "   from=" + outNode);
 575               Set<HNode> endCombNodeSet = new HashSet<HNode>();
 576               for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 577                 HNode endNode = (HNode) iterator3.next();
 578                 endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 579               }
 580               // System.out.println("endCombNodeSet=" + endCombNodeSet);
 581               visited.add(outNode);
 582               if (endCombNodeSet.size() > 0) {
 583                 // follows the straight line up to another skeleton/combination node
 584                 endCombNodeSet = removeTransitivelyReachToNode(desc, startNode, endCombNodeSet);
 585               } else if (endCombNodeSet.size() == 0) {
 586                 // the outNode is (directly/transitively) connected to the bottom node
 587                 // therefore, we just add a dummy bottom HNode to the endCombNodeSet.
 588                 endCombNodeSet.add(LocationInference.BOTTOMHNODE);
 589               }
 590
 591               recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
 592                   mapIntermediateLoc, 1, locSummary, outNode);
 593             }
 594
 595           }
 596
 597         }
 598       } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode()
 599           && !visited.contains(node)) {
 600
 601         System.out.println("n=" + node);
 602
 603         // an intermediate node 'node' may be located between "TOP" location and a skeleton node
 604         if (simpleGraph.getIncomingNodeSet(node).size() == 0) {
 605
 606           // this node will be directly connected to the TOP location
 607           // start adding the following nodes from this node
 608
 609           Set<HNode> endNodeSetFromSimpleGraph =
 610               simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(node, null);
 611
 612           Set<HNode> endCombNodeSet = new HashSet<HNode>();
 613           for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 614             HNode endNode = (HNode) iterator3.next();
 615             endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 616           }
 617
 618           System.out.println("endCombNodeSet=" + endCombNodeSet);
 619           HNode startNode = LocationInference.TOPHNODE;
 620           visited.add(startNode);
 621           if (endCombNodeSet.size() > 0) {
 622             // follows the straight line up to another skeleton/combination node
 623             // endCombNodeSet = removeTransitivelyReachToNode(desc, node, endCombNodeSet);
 624             recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
 625                 mapIntermediateLoc, 1, locSummary, node);
 626           }
 627
 628         }
 629
 630       }
 631     }
 632
 633     // add shared locations
 634     Set<HNode> sharedNodeSet = mapSharedNodeToTripleItem.keySet();
 635     for (Iterator iterator = sharedNodeSet.iterator(); iterator.hasNext();) {
 636       HNode sharedNode = (HNode) iterator.next();
 637       TripleItem item = mapSharedNodeToTripleItem.get(sharedNode);
 638       String nonSharedLocName = mapIntermediateLoc.get(item);
 639       // System.out.println("sharedNode=" + sharedNode + "    locName=" + nonSharedLocName);
 640
 641       String newLocName;
 642       if (locSummary.getHNodeNameSetByLatticeLoationName(nonSharedLocName) != null
 643           && !lattice.isSharedLoc(nonSharedLocName)) {
 644         // need to generate a new shared location in the lattice, which is one level lower than the
 645         // 'locName' location
 646         newLocName = "ILOC" + (LocationInference.locSeed++);
 647
 648         // Set<String> aboveElementSet = getAboveElementSet(lattice, locName);
 649         Set<String> belowElementSet = new HashSet<String>();
 650         belowElementSet.addAll(lattice.get(nonSharedLocName));
 651
 652         // System.out.println("nonSharedLocName=" + nonSharedLocName + "   belowElementSet="
 653         // + belowElementSet + "  newLocName=" + newLocName);
 654
 655         lattice.insertNewLocationBetween(nonSharedLocName, belowElementSet, newLocName);
 656       } else {
 657         newLocName = nonSharedLocName;
 658       }
 659
 660       lattice.addSharedLoc(newLocName);
 661       HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
 662       Set<Descriptor> descSet = graph.getDescSetOfNode(sharedNode);
 663       for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
 664         Descriptor d = (Descriptor) iterator2.next();
 665         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), newLocName);
 666       }
 667       locSummary.addMapHNodeNameToLocationName(sharedNode.getName(), newLocName);
 668
 669     }
 670
 671     return lattice;
 672
 673   }
 674
 675   private Set<String> getAboveElementSet(SSJavaLattice<String> lattice, String loc) {
 676
 677     Set<String> aboveSet = new HashSet<String>();
 678
 679     Map<String, Set<String>> latticeMap = lattice.getTable();
 680     Set<String> keySet = latticeMap.keySet();
 681     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 682       String key = (String) iterator.next();
 683       if (latticeMap.get(key).contains(loc)) {
 684         aboveSet.add(key);
 685       }
 686     }
 687
 688     return aboveSet;
 689   }
 690
 691   private boolean needToExpandCombinationNode(Descriptor desc, HNode cnode) {
 692
 693     System.out.println("needToExpandCombinationNode?=" + cnode);
 694
 695     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 696     // HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
 697     Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
 698     Set<HNode> combinationNodeSetInSimpleGraph =
 699         simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 700     System.out.println("---combinationNodeSetInSimpleGraph=" + combinationNodeSetInSimpleGraph);
 701     Set<HNode> inNodeSetToCNode = simpleGraph.getIncomingNodeSet(cnode);
 702     System.out.println("------inNodeSetToCNode=" + inNodeSetToCNode);
 703     for (Iterator iterator = combinationNodeSetInSimpleGraph.iterator(); iterator.hasNext();) {
 704       HNode nodeBelongToTheSameCombinationNode = (HNode) iterator.next();
 705       if (inNodeSetToCNode.contains(nodeBelongToTheSameCombinationNode)) {
 706         // the combination node 'cnode' is not the highest location among the same combination node
 707         return false;
 708       }
 709     }
 710
 711     return true;
 712   }
 713
 714   private Set<HNode> removeTransitivelyReachToNode(Descriptor desc, HNode startNode,
 715       Set<HNode> endNodeSet) {
 716
 717     // if an end node is not directly connected to the start node in the SC graph
 718     // replace it with a directly connected one which transitively reaches to it.
 719
 720     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 721
 722     Set<HNode> newEndNodeSet = new HashSet<HNode>();
 723     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 724       HNode endNode = (HNode) iterator.next();
 725       if (scGraph.isDirectlyConnectedTo(startNode, endNode)) {
 726         newEndNodeSet.add(endNode);
 727       } else {
 728         HNode newEndNode =
 729             getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode);
 730         // System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode);
 731         newEndNodeSet.add(newEndNode);
 732       }
 733     }
 734
 735     // System.out.println("removeTransitivelyReachToNode=" + endNodeSet + "  newSet=" +
 736     // newEndNodeSet);
 737
 738     return newEndNodeSet;
 739
 740   }
 741
 742   private HNode getDirectlyReachableSCNodeFromEndNode(HierarchyGraph scGraph, HNode startNode,
 743       Set<HNode> endNodeSet) {
 744
 745     // System.out.println("getDirectlyReachableSCNodeFromEndNode start=" + startNode +
 746     // " endNodeSet="
 747     // + endNodeSet);
 748     Set<HNode> newStartNodeSet = new HashSet<HNode>();
 749
 750     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 751       HNode endNode = (HNode) iterator.next();
 752       Set<HNode> connectedToEndNodeSet = scGraph.getIncomingNodeSet(endNode);
 753
 754       for (Iterator iterator2 = connectedToEndNodeSet.iterator(); iterator2.hasNext();) {
 755         HNode curNode = (HNode) iterator2.next();
 756         if (recurConnectedFromStartNode(scGraph, startNode, curNode, new HashSet<HNode>())) {
 757           newStartNodeSet.add(curNode);
 758         }
 759       }
 760     }
 761
 762     // System.out.println("newStartNodeSet=" + newStartNodeSet);
 763
 764     if (newStartNodeSet.size() == 0) {
 765       newStartNodeSet.add(startNode);
 766     }
 767
 768     return newStartNodeSet.iterator().next();
 769   }
 770
 771   private boolean recurConnectedFromStartNode(HierarchyGraph scGraph, HNode startNode,
 772       HNode curNode, Set<HNode> visited) {
 773     // return true if curNode is transitively connected from the startNode
 774
 775     boolean isConnected = false;
 776     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 777     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 778       HNode in = (HNode) iterator.next();
 779       if (in.equals(startNode)) {
 780         return true;
 781       } else {
 782         visited.add(in);
 783         isConnected |= recurConnectedFromStartNode(scGraph, startNode, in, visited);
 784       }
 785     }
 786
 787     return isConnected;
 788   }
 789
 790   private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 791       HNode startNode, HNode endNode) {
 792     // System.out.println("getDirectlyReachableNodeFromStartNodeReachToEndNode start=" + startNode
 793     // + " end=" + endNode);
 794     Set<HNode> connected = new HashSet<HNode>();
 795     recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected);
 796     if (connected.size() == 0) {
 797       connected.add(endNode);
 798     }
 799     // System.out.println("connected=" + connected);
 800
 801     return connected.iterator().next();
 802   }
 803
 804   private void expandCombinationNode3(Descriptor desc, SSJavaLattice<String> lattice,
 805       Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc, LocationSummary locSummary,
 806       HNode cnode) {
 807
 808     // expand the combination node 'outNode'
 809     // here we need to expand the corresponding combination location in the lattice
 810     HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
 811
 812     System.out.println("expandCombinationNode=" + cnode + "  cnode in scgraph="
 813         + combinationNodeInSCGraph);
 814
 815     if (combinationNodeInSCGraph == null) {
 816       return;
 817     }
 818
 819     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 820
 821     Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
 822
 823     // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
 824
 825     Set<HNode> combinationNodeSet =
 826         simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 827
 828     // System.out.println("combinationNodeSet=" + combinationNodeSet);
 829
 830     Set<HNode> endNodeSetFromSimpleGraph =
 831         simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet);
 832     // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 833     Set<HNode> endCombNodeSet = new HashSet<HNode>();
 834     for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 835       HNode endNode = (HNode) iterator3.next();
 836       endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 837     }
 838     visited.add(cnode);
 839
 840     // follows the straight line up to another skeleton/combination node
 841     if (endCombNodeSet.size() > 0) {
 842       // System.out.println("---endCombNodeSet=" + endCombNodeSet);
 843       endCombNodeSet =
 844           removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
 845
 846       recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 847           mapIntermediateLoc, 1, locSummary, cnode);
 848     } else {
 849       endCombNodeSet.add(LocationInference.BOTTOMHNODE);
 850       // System.out.println("---endCombNodeSet is zero");
 851       // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 852       // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode));
 853       recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 854           mapIntermediateLoc, 1, locSummary, cnode);
 855
 856     }
 857
 858   }
 859
 860   private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 861       HNode startNode, HNode curNode, Set<HNode> connected) {
 862
 863     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 864     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 865       HNode inNode = (HNode) iterator.next();
 866       if (inNode.equals(startNode)) {
 867         connected.add(curNode);
 868       } else {
 869         recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected);
 870       }
 871     }
 872
 873   }
 874
 875   private void recurDFSNormalNode(Descriptor desc, SSJavaLattice<String> lattice, HNode startNode,
 876       Set<HNode> endNodeSet, Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc,
 877       int idx, LocationSummary locSummary, HNode curNode) {
 878
 879     TripleItem item = new TripleItem(startNode, endNodeSet, idx);
 880     // System.out.println("item=" + item);
 881     if (!mapIntermediateLoc.containsKey(item)) {
 882       // need to create a new intermediate location in the lattice
 883       String newLocName = "ILOC" + (LocationInference.locSeed++);
 884       String above;
 885       if (idx == 1) {
 886         above = startNode.getName();
 887       } else {
 888         int prevIdx = idx - 1;
 889         TripleItem prevItem = new TripleItem(startNode, endNodeSet, prevIdx);
 890         above = mapIntermediateLoc.get(prevItem);
 891       }
 892
 893       Set<String> belowSet = new HashSet<String>();
 894       for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 895         HNode endNode = (HNode) iterator.next();
 896         String locName;
 897         if (locSummary.getMapHNodeNameToLocationName().containsKey(endNode.getName())) {
 898           locName = locSummary.getLocationName(endNode.getName());
 899         } else {
 900           locName = endNode.getName();
 901         }
 902         belowSet.add(locName);
 903       }
 904       lattice.insertNewLocationBetween(above, belowSet, newLocName);
 905
 906       mapIntermediateLoc.put(item, newLocName);
 907     }
 908
 909     String locName = mapIntermediateLoc.get(item);
 910     HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 911
 912     if (curNode.isSharedNode()) {
 913       // if the current node is shared location, add a shared location to the lattice later
 914       mapSharedNodeToTripleItem.put(curNode, item);
 915     } else {
 916       Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
 917       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 918         Descriptor d = (Descriptor) iterator.next();
 919         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 920       }
 921       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 922     }
 923
 924     System.out.println("-TripleItem normal=" + item);
 925     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
 926         + " locName=" + locName + "  isC=" + curNode.isCombinationNode());
 927
 928     Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
 929     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 930       HNode outNode = (HNode) iterator2.next();
 931
 932       Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
 933       System.out.println("outNode=" + outNode);
 934       System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode);
 935
 936       if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
 937         if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) {
 938           visited.add(outNode);
 939           int newidx = getCurrentHighestIndex(outNode, idx + 1);
 940           recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 941               newidx, locSummary, outNode);
 942           // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 943           // idx + 1, locSummary, outNode);
 944         } else {
 945           updateHighestIndex(outNode, idx + 1);
 946           System.out.println("NOT RECUR");
 947         }
 948       } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) {
 949         if (needToExpandCombinationNode(desc, outNode)) {
 950           System.out.println("NEED TO");
 951           expandCombinationNode3(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 952         } else {
 953           System.out.println("NOT NEED TO");
 954         }
 955       }
 956
 957     }
 958
 959   }
 960
 961   private void recurDFS(Descriptor desc, SSJavaLattice<String> lattice,
 962       HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
 963       Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode curNode) {
 964
 965     TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx);
 966
 967     if (!mapIntermediateLoc.containsKey(item)) {
 968       // need to create a new intermediate location in the lattice
 969       String above;
 970       if (idx == 1) {
 971         String newLocName = combinationNodeInSCGraph.getName();
 972         mapIntermediateLoc.put(item, newLocName);
 973       } else {
 974         String newLocName = "ILOC" + (LocationInference.locSeed++);
 975         int prevIdx = idx - 1;
 976         TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
 977         above = mapIntermediateLoc.get(prevItem);
 978
 979         Set<String> belowSet = new HashSet<String>();
 980         for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 981           HNode endNode = (HNode) iterator.next();
 982           belowSet.add(endNode.getName());
 983         }
 984         lattice.insertNewLocationBetween(above, belowSet, newLocName);
 985         mapIntermediateLoc.put(item, newLocName);
 986       }
 987
 988     }
 989
 990     // TODO
 991     // Do we need to skip the combination node and assign a shared location to the next node?
 992     // if (idx == 1 && curNode.isSharedNode()) {
 993     // System.out.println("THE FIRST COMBINATION NODE EXPANSION IS SHARED!");
 994     // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, mapIntermediateLoc,
 995     // idx + 1, locSummary, curNode);
 996     // return;
 997     // }
 998
 999     HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
1000     String locName = mapIntermediateLoc.get(item);
1001     if (curNode.isSharedNode()) {
1002       // if the current node is shared location, add a shared location to the lattice later
1003       mapSharedNodeToTripleItem.put(curNode, item);
1004     } else {
1005       Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
1006       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
1007         Descriptor d = (Descriptor) iterator.next();
1008         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
1009       }
1010       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
1011     }
1012
1013     System.out.println("-TripleItem=" + item);
1014     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
1015         + " locName=" + locName);
1016
1017     Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
1018     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
1019       HNode outNode = (HNode) iterator2.next();
1020       System.out.println("---recurDFS outNode=" + outNode);
1021       System.out.println("---cur combinationNodeInSCGraph=" + combinationNodeInSCGraph);
1022       System.out.println("---outNode combinationNodeInSCGraph="
1023           + getCombinationNodeInSCGraph(desc, outNode));
1024
1025       if (!outNode.isSkeleton() && !visited.contains(outNode)) {
1026         if (outNode.isCombinationNode()) {
1027
1028           Set<HNode> combineSkeletonNodeSet =
1029               simpleHierarchyGraph.getCombineSetByCombinationNode(outNode);
1030           Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
1031           // extract nodes belong to the same combine node
1032           Set<HNode> incomingCombinedHNodeSet = new HashSet<HNode>();
1033           for (Iterator iterator = incomingHNodeSetToOutNode.iterator(); iterator.hasNext();) {
1034             HNode inNode = (HNode) iterator.next();
1035             if (combineSkeletonNodeSet.contains(inNode)) {
1036               incomingCombinedHNodeSet.add(inNode);
1037             }
1038           }
1039           System.out.println("-----incomingCombinedHNodeSet=" + incomingCombinedHNodeSet);
1040
1041           // check whether the next combination node is different from the current node
1042           if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
1043             if (visited.containsAll(incomingCombinedHNodeSet)) {
1044               visited.add(outNode);
1045               System.out.println("-------curIdx=" + (idx + 1));
1046               int newIdx = getCurrentHighestIndex(outNode, idx + 1);
1047               System.out.println("-------newIdx=" + newIdx);
1048               recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
1049                   mapIntermediateLoc, newIdx, locSummary, outNode);
1050               // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
1051               // mapIntermediateLoc, idx + 1, locSummary, outNode);
1052             } else {
1053               updateHighestIndex(outNode, idx + 1);
1054               System.out.println("-----NOT RECUR!");
1055             }
1056           } else {
1057             if (needToExpandCombinationNode(desc, outNode)) {
1058               System.out.println("NEED TO");
1059               expandCombinationNode3(desc, lattice, visited, mapIntermediateLoc, locSummary,
1060                   outNode);
1061             } else {
1062               System.out.println("NOT NEED TO");
1063             }
1064
1065           }
1066         }
1067       }
1068       // }
1069
1070     }
1071
1072   }
1073
1074   private int getCurrentHighestIndex(HNode node, int curIdx) {
1075     int recordedIdx = getCurrentHighestIndex(node);
1076     if (recordedIdx > curIdx) {
1077       return recordedIdx;
1078     } else {
1079       return curIdx;
1080     }
1081   }
1082
1083   private int getCurrentHighestIndex(HNode node) {
1084     if (!mapHNodeToHighestIndex.containsKey(node)) {
1085       mapHNodeToHighestIndex.put(node, new Integer(-1));
1086     }
1087     return mapHNodeToHighestIndex.get(node).intValue();
1088   }
1089
1090   private void updateHighestIndex(HNode node, int idx) {
1091     if (idx > getCurrentHighestIndex(node)) {
1092       mapHNodeToHighestIndex.put(node, new Integer(idx));
1093     }
1094   }
1095
1096   private String generateElementName(BasisSet basisSet, HierarchyGraph inputGraph,
1097       Map<Set<Integer>, String> mapF2LocName, Set<Integer> F) {
1098
1099     if (mapF2LocName.containsKey(F)) {
1100       return mapF2LocName.get(F);
1101     }
1102
1103     HNode node = basisSet.getHNode(F);
1104     if (node != null) {
1105       mapF2LocName.put(F, node.getName());
1106       return node.getName();
1107     } else {
1108       if (inputGraph.BASISTOPELEMENT.equals(F)) {
1109         return SSJavaAnalysis.BOTTOM;
1110       } else {
1111         String str = "LOC" + (LocationInference.locSeed++);
1112         mapF2LocName.put(F, str);
1113         return str;
1114       }
1115     }
1116   }
1117
1118   private void resetCount(Map<Set<Integer>, Integer> mapFtoCount, Family family) {
1119     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
1120       Set<Integer> F = iter.next();
1121       mapFtoCount.put(F, 0);
1122     }
1123   }
1124
1125   private Map<Set<Integer>, Set<Set<Integer>>> coveringGraph(BasisSet basisSet, Family family) {
1126
1127     Map<Set<Integer>, Integer> mapFtoCount = new HashMap<Set<Integer>, Integer>();
1128     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = new HashMap<Set<Integer>, Set<Set<Integer>>>();
1129
1130     // initialize COUNT(F) to 0 for all elements of the family
1131     resetCount(mapFtoCount, family);
1132
1133     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
1134       Set<Integer> F = iter.next();
1135       Set<HNode> gammaF = family.getGamma(F);
1136
1137       Set<HNode> curHNodeSet = basisSet.getHNodeSet();
1138       curHNodeSet.removeAll(gammaF);
1139       Set<Set<Integer>> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet);
1140
1141       for (Iterator iterator = Bset.iterator(); iterator.hasNext();) {
1142         Set<Integer> B = (Set<Integer>) iterator.next();
1143
1144         Set<Integer> Fprime = new HashSet<Integer>();
1145         Fprime.addAll(F);
1146         Fprime.addAll(B);
1147
1148         // COUNT(F')++;
1149         mapFtoCount.put(Fprime, mapFtoCount.get(Fprime) + 1);
1150
1151         // if |gamma(F')|==COUNT(F') + |gamma(F)|
1152         int numGammaFprime = family.getGamma(Fprime).size();
1153         int countFprime = mapFtoCount.get(Fprime);
1154         int numGammaF = family.getGamma(F).size();
1155         if (numGammaFprime == (countFprime + numGammaF)) {
1156           // ImSucc(F)=IMSucc(F) union F'
1157           addImSucc(mapImSucc, F, Fprime);
1158         }
1159
1160       }
1161       resetCount(mapFtoCount, family);
1162     }
1163
1164     // System.out.println("mapImSucc=" + mapImSucc);
1165
1166     return mapImSucc;
1167   }
1168
1169   private Set<Set<Integer>> getImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F) {
1170     if (!mapImSucc.containsKey(F)) {
1171       mapImSucc.put(F, new HashSet<Set<Integer>>());
1172     }
1173     return mapImSucc.get(F);
1174   }
1175
1176   private void addImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F,
1177       Set<Integer> Fprime) {
1178
1179     if (!mapImSucc.containsKey(F)) {
1180       mapImSucc.put(F, new HashSet<Set<Integer>>());
1181     }
1182
1183     mapImSucc.get(F).add(Fprime);
1184
1185   }
1186
1187   private Family generateFamily(BasisSet basisSet) {
1188
1189     Family family = new Family();
1190
1191     for (Iterator<Set<Integer>> iterator = basisSet.basisIterator(); iterator.hasNext();) {
1192       Set<Integer> B = iterator.next();
1193
1194       Set<Pair<Set<Integer>, Set<HNode>>> tobeadded = new HashSet<Pair<Set<Integer>, Set<HNode>>>();
1195
1196       for (Iterator<Set<Integer>> iterator2 = family.FIterator(); iterator2.hasNext();) {
1197         Set<Integer> F = iterator2.next();
1198
1199         Set<Integer> Fprime = new HashSet<Integer>();
1200         Fprime.addAll(F);
1201         Fprime.addAll(B);
1202
1203         Set<HNode> gammaFPrimeSet = new HashSet<HNode>();
1204         gammaFPrimeSet.addAll(family.getGamma(F));
1205         gammaFPrimeSet.add(basisSet.getHNode(B));
1206
1207         if (!family.containsF(Fprime)) {
1208           Pair<Set<Integer>, Set<HNode>> pair =
1209               new Pair<Set<Integer>, Set<HNode>>(Fprime, gammaFPrimeSet);
1210           tobeadded.add(pair);
1211         } else {
1212           family.updateGammaF(Fprime, gammaFPrimeSet);
1213         }
1214       }
1215
1216       for (Iterator<Pair<Set<Integer>, Set<HNode>>> iterator2 = tobeadded.iterator(); iterator2
1217           .hasNext();) {
1218         Pair<Set<Integer>, Set<HNode>> pair = iterator2.next();
1219         family.addFElement(pair.getFirst());
1220         family.updateGammaF(pair.getFirst(), pair.getSecond());
1221       }
1222
1223     }
1224     return family;
1225   }
1226
1227   private void debug_print(HierarchyGraph inputGraph) {
1228     System.out.println("\nBuild Lattice:" + inputGraph.getName());
1229     // System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex());
1230     // System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
1231   }
1232
1233 }
1234
1235 class Identifier {
1236   public HNode node;
1237   public int idx;
1238
1239   public Identifier(HNode n, int i) {
1240     node = n;
1241     idx = i;
1242   }
1243
1244   public int hashCode() {
1245     return node.hashCode() + idx;
1246   }
1247
1248   public boolean equals(Object obj) {
1249
1250     if (obj instanceof Identifier) {
1251       Identifier in = (Identifier) obj;
1252       if (node.equals(in.node) && idx == in.idx) {
1253         return true;
1254       }
1255     }
1256
1257     return false;
1258   }
1259
1260 }
1261
1262 class TripleItem {
1263   public HNode higherNode;
1264   public Set<HNode> lowerNodeSet;
1265   public int idx;
1266   public boolean isShared;
1267
1268   public TripleItem(HNode h, Set<HNode> l, int i) {
1269     higherNode = h;
1270     lowerNodeSet = l;
1271     idx = i;
1272     isShared = false;
1273   }
1274
1275   public void setShared(boolean in) {
1276     this.isShared = in;
1277   }
1278
1279   public boolean isShared() {
1280     return isShared;
1281   }
1282
1283   public int hashCode() {
1284
1285     int h = 0;
1286     if (higherNode != null) {
1287       h = higherNode.hashCode();
1288     }
1289
1290     if (isShared) {
1291       h++;
1292     }
1293
1294     return h + lowerNodeSet.hashCode() + idx;
1295   }
1296
1297   public boolean equals(Object obj) {
1298
1299     if (obj instanceof TripleItem) {
1300       TripleItem in = (TripleItem) obj;
1301       if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode)))
1302           && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx && isShared == in.isShared()) {
1303         return true;
1304       }
1305     }
1306
1307     return false;
1308   }
1309
1310   public String toString() {
1311     String rtr = higherNode + "-" + idx + "->" + lowerNodeSet;
1312     if (isShared) {
1313       rtr += " S";
1314     }
1315     return rtr;
1316   }
1317 }