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.LinkedList;
   7 import java.util.Map;
   8 import java.util.Set;
   9 import java.util.Stack;
  10
  11 import IR.ClassDescriptor;
  12 import IR.Descriptor;
  13 import IR.MethodDescriptor;
  14 import IR.NameDescriptor;
  15 import Util.Pair;
  16
  17 public class BuildLattice {
  18
  19   private LocationInference infer;
  20   private Map<HNode, TripleItem> mapSharedNodeToTripleItem;
  21   private Map<HNode, Integer> mapHNodeToHighestIndex;
  22
  23   private Map<Descriptor, Map<TripleItem, String>> mapDescToIntermediateLocMap;
  24
  25   private Map<Descriptor, Map<InterLocItem, String>> mapDescToInterLocMap;
  26
  27   private Map<Pair<HNode, HNode>, Integer> mapItemToHighestIndex;
  28
  29   private Map<SSJavaLattice<String>, Set<String>> mapLatticeToLocalLocSet;
  30
  31   private Map<Descriptor, Map<LineIdentifier, LinkedList<LocPair>>> mapDescToLineListMap;
  32
  33   public BuildLattice() {
  34     this(null);
  35   }
  36
  37   public BuildLattice(LocationInference infer) {
  38     this.infer = infer;
  39     this.mapSharedNodeToTripleItem = new HashMap<HNode, TripleItem>();
  40     this.mapHNodeToHighestIndex = new HashMap<HNode, Integer>();
  41     this.mapItemToHighestIndex = new HashMap<Pair<HNode, HNode>, Integer>();
  42     this.mapDescToIntermediateLocMap = new HashMap<Descriptor, Map<TripleItem, String>>();
  43     this.mapLatticeToLocalLocSet = new HashMap<SSJavaLattice<String>, Set<String>>();
  44     this.mapDescToInterLocMap = new HashMap<Descriptor, Map<InterLocItem, String>>();
  45     this.mapDescToLineListMap = new HashMap<Descriptor, Map<LineIdentifier, LinkedList<LocPair>>>();
  46   }
  47
  48   public SSJavaLattice<String> buildLattice(Descriptor desc) {
  49
  50     HierarchyGraph inputGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
  51     LocationSummary locSummary = infer.getLocationSummary(desc);
  52
  53     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
  54     HierarchyGraph naiveGraph = simpleGraph.clone();
  55
  56     // I don't think we need to keep the below if statement anymore
  57     // because hierarchy graph does not have any composite location
  58     Set<HNode> nodeSetWithCompositeLocation = new HashSet<HNode>();
  59     if (desc instanceof MethodDescriptor) {
  60       FlowGraph flowGraph = infer.getFlowGraph((MethodDescriptor) desc);
  61
  62       for (Iterator iterator = inputGraph.getNodeSet().iterator(); iterator.hasNext();) {
  63         HNode hnode = (HNode) iterator.next();
  64         Descriptor hnodeDesc = hnode.getDescriptor();
  65         if (hnodeDesc != null) {
  66           NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
  67           descTuple.add(hnodeDesc);
  68
  69           if (flowGraph.contains(descTuple)) {
  70             FlowNode flowNode = flowGraph.getFlowNode(descTuple);
  71             if (flowNode.getCompositeLocation() != null) {
  72               nodeSetWithCompositeLocation.add(hnode);
  73             }
  74           }
  75
  76         }
  77       }
  78
  79     }
  80
  81     // /////////////////////////////////////////////////////////////////////////////////////
  82     // lattice generation for the native approach
  83
  84     if (infer.state.SSJAVA_INFER_NAIVE_WRITEDOTS) {
  85       BasisSet naiveBasisSet = naiveGraph.computeBasisSet(nodeSetWithCompositeLocation);
  86
  87       Family naiveFamily = generateFamily(naiveBasisSet);
  88       Map<Set<Integer>, Set<Set<Integer>>> naive_mapImSucc =
  89           coveringGraph(naiveBasisSet, naiveFamily);
  90
  91       SSJavaLattice<String> naive_lattice =
  92           buildLattice(desc, naiveBasisSet, naiveGraph, null, naive_mapImSucc);
  93       int numLocs = naive_lattice.getKeySet().size() ;
  94       LocationInference.numLocationsNaive += numLocs;
  95       infer.mapNumLocsMapNaive.put(desc, new Integer(numLocs));
  96
  97       int numPaths = naive_lattice.countPaths();
  98       infer.mapNumPathsMapNaive.put(desc, new Integer(numPaths));
  99
 100       System.out.println(desc + " numPaths=" + numPaths + " numLocs="
 101           + naive_lattice.getKeySet().size());
 102
 103       infer.addNaiveLattice(desc, naive_lattice);
 104
 105       // write a dot file before everything is done
 106       if (desc instanceof ClassDescriptor) {
 107         infer.writeInferredLatticeDotFile((ClassDescriptor) desc, null, naive_lattice, "_naive");
 108       } else {
 109         MethodDescriptor md = (MethodDescriptor) desc;
 110         infer.writeInferredLatticeDotFile(md.getClassDesc(), md, naive_lattice, "_naive");
 111       }
 112
 113     }
 114
 115     // /////////////////////////////////////////////////////////////////////////////////////
 116
 117     // lattice generation for the proposed approach
 118     BasisSet basisSet = inputGraph.computeBasisSet(nodeSetWithCompositeLocation);
 119     // debug_print(inputGraph);
 120
 121     Family family = generateFamily(basisSet);
 122     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = coveringGraph(basisSet, family);
 123
 124     SSJavaLattice<String> lattice = buildLattice(desc, basisSet, inputGraph, locSummary, mapImSucc);
 125     return lattice;
 126
 127   }
 128
 129   public void setIntermediateLocMap(Descriptor desc, Map<TripleItem, String> map) {
 130     mapDescToIntermediateLocMap.put(desc, map);
 131   }
 132
 133   public Map<TripleItem, String> getIntermediateLocMap(Descriptor desc) {
 134     if (!mapDescToIntermediateLocMap.containsKey(desc)) {
 135       mapDescToIntermediateLocMap.put(desc, new HashMap<TripleItem, String>());
 136     }
 137     return mapDescToIntermediateLocMap.get(desc);
 138   }
 139
 140   private Descriptor getParent(Descriptor desc) {
 141     if (desc instanceof MethodDescriptor) {
 142       MethodDescriptor md = (MethodDescriptor) desc;
 143       ClassDescriptor cd = md.getClassDesc();
 144       return infer.getParentMethodDesc(cd, md);
 145     } else {
 146       return ((ClassDescriptor) desc).getSuperDesc();
 147     }
 148   }
 149
 150   private SSJavaLattice<String> buildLattice(BasisSet basisSet, HierarchyGraph inputGraph,
 151       Map<Set<Integer>, Set<Set<Integer>>> mapImSucc) {
 152
 153     System.out.println("\nBuild Complete Lattice:" + inputGraph.getName());
 154
 155     SSJavaLattice<String> completeLattice =
 156         new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
 157
 158     Map<Set<Integer>, String> mapFToLocName = new HashMap<Set<Integer>, String>();
 159
 160     Set<Set<Integer>> keySet = mapImSucc.keySet();
 161     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 162       Set<Integer> higher = (Set<Integer>) iterator.next();
 163
 164       String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher);
 165
 166       HNode higherNode = inputGraph.getHNode(higherName);
 167
 168       if (higherNode == null) {
 169         NameDescriptor d = new NameDescriptor(higherName);
 170         higherNode = inputGraph.getHNode(d);
 171         higherNode.setSkeleton(true);
 172       }
 173
 174       if (higherNode != null && higherNode.isSharedNode()) {
 175         completeLattice.addSharedLoc(higherName);
 176       }
 177       Set<Descriptor> descSet = inputGraph.getDescSetOfNode(higherNode);
 178       // System.out.println("higherName=" + higherName + "  higherNode=" + higherNode + "  descSet="
 179       // + descSet);
 180
 181       // locSummary.addMapHNodeNameToLocationName(higherName, higherName);
 182
 183       Set<Set<Integer>> lowerSet = mapImSucc.get(higher);
 184       for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
 185         Set<Integer> lower = (Set<Integer>) iterator2.next();
 186
 187         String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower);
 188         HNode lowerNode = inputGraph.getHNode(lowerName);
 189
 190         if (lowerNode == null && !lowerName.equals(SSJavaAnalysis.BOTTOM)) {
 191           NameDescriptor d = new NameDescriptor(lowerName);
 192           lowerNode = inputGraph.getHNode(d);
 193           lowerNode.setSkeleton(true);
 194         }
 195
 196         if (lowerNode != null && !inputGraph.isDirectlyConnectedTo(higherNode, lowerNode)) {
 197           inputGraph.addEdge(higherNode, lowerNode);
 198         }
 199
 200         if (lowerNode != null && lowerNode.isSharedNode()) {
 201           completeLattice.addSharedLoc(lowerName);
 202         }
 203
 204         Set<Descriptor> lowerDescSet = inputGraph.getDescSetOfNode(lowerNode);
 205         // System.out.println("lowerName=" + lowerName + "  lowerNode=" + lowerNode + "  descSet="
 206         // + lowerDescSet);
 207         // locSummary.addMapHNodeNameToLocationName(lowerName, lowerName);
 208
 209         if (higher.size() == 0) {
 210           // empty case
 211           completeLattice.put(lowerName);
 212         } else {
 213           completeLattice.addRelationHigherToLower(higherName, lowerName);
 214         }
 215
 216       }
 217
 218     }
 219
 220     return completeLattice;
 221   }
 222
 223   private SSJavaLattice<String> buildLattice(Descriptor desc, BasisSet basisSet,
 224       HierarchyGraph inputGraph, LocationSummary locSummary,
 225       Map<Set<Integer>, Set<Set<Integer>>> mapImSucc) {
 226
 227     System.out.println("\nBuild Lattice:" + inputGraph.getName());
 228
 229     SSJavaLattice<String> lattice =
 230         new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
 231
 232     Map<Set<Integer>, String> mapFToLocName = new HashMap<Set<Integer>, String>();
 233
 234     Set<Set<Integer>> keySet = mapImSucc.keySet();
 235     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 236       Set<Integer> higher = (Set<Integer>) iterator.next();
 237
 238       String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher);
 239
 240       HNode higherNode = inputGraph.getHNode(higherName);
 241
 242       if (higherNode == null) {
 243         NameDescriptor d = new NameDescriptor(higherName);
 244         higherNode = inputGraph.getHNode(d);
 245         higherNode.setSkeleton(true);
 246       }
 247
 248       if (higherNode != null && higherNode.isSharedNode()) {
 249         lattice.addSharedLoc(higherName);
 250       }
 251       Set<Descriptor> descSet = inputGraph.getDescSetOfNode(higherNode);
 252       // System.out.println("higherName=" + higherName + "  higherNode=" + higherNode + "  descSet="
 253       // + descSet);
 254
 255       if (locSummary != null) {
 256         for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
 257           Descriptor d = (Descriptor) iterator2.next();
 258           locSummary.addMapHNodeNameToLocationName(d.getSymbol(), higherName);
 259         }
 260       }
 261
 262       // locSummary.addMapHNodeNameToLocationName(higherName, higherName);
 263
 264       Set<Set<Integer>> lowerSet = mapImSucc.get(higher);
 265       for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
 266         Set<Integer> lower = (Set<Integer>) iterator2.next();
 267
 268         String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower);
 269         HNode lowerNode = inputGraph.getHNode(lowerName);
 270
 271         if (lowerNode == null && !lowerName.equals(SSJavaAnalysis.BOTTOM)) {
 272           NameDescriptor d = new NameDescriptor(lowerName);
 273           lowerNode = inputGraph.getHNode(d);
 274           lowerNode.setSkeleton(true);
 275         }
 276
 277         if (lowerNode != null && !inputGraph.isDirectlyConnectedTo(higherNode, lowerNode)) {
 278           inputGraph.addEdge(higherNode, lowerNode);
 279         }
 280
 281         if (lowerNode != null && lowerNode.isSharedNode()) {
 282           lattice.addSharedLoc(lowerName);
 283         }
 284
 285         Set<Descriptor> lowerDescSet = inputGraph.getDescSetOfNode(lowerNode);
 286         // System.out.println("lowerName=" + lowerName + "  lowerNode=" + lowerNode + "  descSet="
 287         // + lowerDescSet);
 288         if (locSummary != null) {
 289           for (Iterator iterator3 = lowerDescSet.iterator(); iterator3.hasNext();) {
 290             Descriptor d = (Descriptor) iterator3.next();
 291             locSummary.addMapHNodeNameToLocationName(d.getSymbol(), lowerName);
 292           }
 293         }
 294         // locSummary.addMapHNodeNameToLocationName(lowerName, lowerName);
 295
 296         if (higher.size() == 0) {
 297           // empty case
 298           lattice.put(lowerName);
 299         } else {
 300           lattice.addRelationHigherToLower(higherName, lowerName);
 301         }
 302
 303       }
 304
 305     }
 306
 307     inputGraph.removeRedundantEdges();
 308     return lattice;
 309   }
 310
 311   public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode nodeFromSimpleGraph) {
 312
 313     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 314
 315     if (nodeFromSimpleGraph.isSkeleton()) {
 316       return scGraph.getCurrentHNode(nodeFromSimpleGraph);
 317     }
 318
 319     Set<HNode> combineSkeletonNodeSet =
 320         infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(nodeFromSimpleGraph);
 321     HNode combinationNodeInSCGraph =
 322         infer.getSkeletonCombinationHierarchyGraph(desc).getMapCombineNodeSetToCombinationNode()
 323             .get(combineSkeletonNodeSet);
 324
 325     // Set<HNode> combineSkeletonNodeSet =
 326     // infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode);
 327     // HNode combinationNodeInSCGraph =
 328     // infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet);
 329     return combinationNodeInSCGraph;
 330   }
 331
 332   public SSJavaLattice<String> insertIntermediateNodesToStraightLine(Descriptor desc,
 333       SSJavaLattice<String> skeletonLattice) {
 334
 335     SSJavaLattice<String> lattice = skeletonLattice.clone();
 336     LocationSummary locSummary = infer.getLocationSummary(desc);
 337
 338     Descriptor parentDesc = getParent(desc);
 339     if (parentDesc != null) {
 340       SSJavaLattice<String> parentLattice = infer.getLattice(parentDesc);
 341
 342       Map<String, Set<String>> parentMap = parentLattice.getTable();
 343       Set<String> parentKeySet = parentMap.keySet();
 344       for (Iterator iterator = parentKeySet.iterator(); iterator.hasNext();) {
 345         String parentKey = (String) iterator.next();
 346         Set<String> parentValueSet = parentMap.get(parentKey);
 347         for (Iterator iterator2 = parentValueSet.iterator(); iterator2.hasNext();) {
 348           String value = (String) iterator2.next();
 349           lattice.put(parentKey, value);
 350         }
 351       }
 352
 353       Set<String> parentSharedLocSet = parentLattice.getSharedLocSet();
 354       for (Iterator iterator = parentSharedLocSet.iterator(); iterator.hasNext();) {
 355         String parentSharedLoc = (String) iterator.next();
 356         lattice.addSharedLoc(parentSharedLoc);
 357       }
 358     }
 359
 360     HierarchyGraph hierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 361     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 362
 363     Set<HNode> hierarchyGraphNodeSet = hierarchyGraph.getNodeSet();
 364     for (Iterator iterator = hierarchyGraphNodeSet.iterator(); iterator.hasNext();) {
 365       HNode hNode = (HNode) iterator.next();
 366       if (!hNode.isSkeleton()) {
 367         // here we need to insert an intermediate node for the hNode
 368         System.out.println("\n#local node=" + hNode);
 369
 370         // 1) find the lowest node m in the lattice that is above hnode in the lattice
 371         // 2) count the number of non-shared nodes d between the hnode and the node m
 372         // int numNonSharedNodes;
 373         int dist = 0;
 374
 375         HNode SCNode;
 376         Set<HNode> combineSkeletonNodeSet = null;
 377         Stack<String> trace = new Stack<String>();
 378         if (hNode.isDirectCombinationNode()) {
 379           // this node itself is the lowest node m. it is the first node of the chain
 380           Set<HNode> combineSet = hierarchyGraph.getCombineSetByCombinationNode(hNode);
 381
 382           System.out.println("     # direct combine node::combineSkeletonNodeSet=" + combineSet);
 383
 384           SCNode = scGraph.getCombinationNode(combineSet);
 385           // numNonSharedNodes = -1;
 386           dist = 0;
 387           if (hNode.isSharedNode()) {
 388             trace.add("S");
 389           } else {
 390             trace.add("N");
 391           }
 392         } else {
 393
 394           Set<HNode> aboveSet = new HashSet<HNode>();
 395           if (hNode.isCombinationNode()) {
 396             // the current node is a combination node
 397             combineSkeletonNodeSet = hierarchyGraph.getCombineSetByCombinationNode(hNode);
 398             System.out.println("     combineSkeletonNodeSet=" + combineSkeletonNodeSet
 399                 + " combinationNode=" + scGraph.getCombinationNode(combineSkeletonNodeSet));
 400
 401             scGraph.getCombinationNode(combineSkeletonNodeSet);
 402
 403             System.out.println("        firstnodeOfSimpleGraph="
 404                 + hierarchyGraph.getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet));
 405             aboveSet.addAll(hierarchyGraph
 406                 .getFirstNodeOfCombinationNodeChainSet(combineSkeletonNodeSet));
 407
 408             SCNode = scGraph.getCombinationNode(combineSkeletonNodeSet);
 409
 410           } else {
 411             // the current node is not a combination node
 412             // there is only one parent node which should be skeleton node.
 413
 414             // System.out.println("   hierarchyGraph.getSkeleteNodeSetReachTo(" + hNode + ")="
 415             // + hierarchyGraph.getSkeleteNodeSetReachTo(hNode));
 416
 417
 418             //TODO attempt to use  non-transitive reachToSet
 419 //            Set<HNode> reachToSet = hierarchyGraph.getSkeleteNodeSetReachToNoTransitive(hNode);
 420             Set<HNode> reachToSet = hierarchyGraph.getSkeleteNodeSetReachTo(hNode);
 421 //            System.out.println("reachToSet=" + reachToSet);
 422             for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
 423               HNode reachToNode = (HNode) iterator2.next();
 424               aboveSet.add(scGraph.getCurrentHNode(reachToNode));
 425             }
 426
 427             SCNode = aboveSet.iterator().next();
 428           }
 429
 430           // update above set w.r.t the hierarchy graph with SC nodes
 431           // because the skeleton nodes in the original hierarchy graph may be merged to a new node
 432           Set<HNode> endSet = new HashSet<HNode>();
 433           for (Iterator iterator2 = aboveSet.iterator(); iterator2.hasNext();) {
 434             HNode aboveNode = (HNode) iterator2.next();
 435             endSet.add(hierarchyGraph.getCurrentHNode(aboveNode));
 436           }
 437
 438           trace = hierarchyGraph.computeDistance(hNode, endSet, scGraph, combineSkeletonNodeSet);
 439
 440           System.out.println("   COUNT-RESULT::start=" + hNode + " end=" + endSet + " trace="
 441               + trace);
 442         }
 443
 444         // 3) convert the node m into a chain of nodes with the last node in the chain having m's
 445         // outgoing edges.
 446         Set<HNode> outgoingSCNodeSet = scGraph.getOutgoingNodeSet(SCNode);
 447         System.out.println("   outgoing scnode set from " + SCNode + "=" + outgoingSCNodeSet);
 448
 449         // convert hnodes to location names
 450         String startLocName = locSummary.getLocationName(SCNode.getName());
 451         Set<String> outgoingLocNameSet = new HashSet<String>();
 452         for (Iterator iterator2 = outgoingSCNodeSet.iterator(); iterator2.hasNext();) {
 453           HNode outSCNode = (HNode) iterator2.next();
 454           String locName = locSummary.getLocationName(outSCNode.getName());
 455           if (!locName.equals(outSCNode.getName())) {
 456             System.out.println("                         outSCNode=" + outSCNode + " -> locName="
 457                 + locName);
 458           }
 459           outgoingLocNameSet.add(locName);
 460         }
 461
 462         if (outgoingLocNameSet.isEmpty()) {
 463           outgoingLocNameSet.add(lattice.getBottomItem());
 464         }
 465
 466         if (hNode.isCombinationNode()) {
 467           System.out.println("make sure that the first node corresponds to the COMB node="
 468               + startLocName);
 469           LineIdentifier lineId = new LineIdentifier(startLocName, outgoingLocNameSet);
 470           LinkedList<LocPair> list = getLineList(desc, lineId);
 471           // make sure that the first node corresponds to the COMB node
 472           if (list.size() <= 0) {
 473             list.add(new LocPair());
 474           }
 475           LocPair firstPair = list.get(0);
 476           firstPair.nonShared = startLocName;
 477         }
 478
 479         // 4) If hnode is not a shared location, check if there already exists a local variable
 480         // node that has distance d below m along this chain. If such a node
 481         // does not exist, insert it.
 482         String locName =
 483             getNewLocation(desc, startLocName, outgoingLocNameSet, trace, hNode.isSharedNode());
 484
 485         System.out.println("       ###hNode=" + hNode + "---->locName=" + locName);
 486         locSummary.addMapHNodeNameToLocationName(hNode.getName(), locName);
 487
 488       }
 489     }
 490
 491     insertLocalLocations(desc, lattice);
 492
 493     return lattice;
 494   }
 495
 496   private void insertLocalLocations(Descriptor desc, SSJavaLattice<String> lattice) {
 497
 498     Map<LineIdentifier, LinkedList<LocPair>> map = getLineListMap(desc);
 499     System.out.println("####MAP=" + map);
 500
 501     Set<LineIdentifier> lineIdSet = map.keySet();
 502     for (Iterator iterator = lineIdSet.iterator(); iterator.hasNext();) {
 503       LineIdentifier lineId = (LineIdentifier) iterator.next();
 504
 505       LinkedList<LocPair> list = map.get(lineId);
 506
 507       String higherLocName = lineId.startLoc;
 508       Set<String> endLocNameSet = lineId.lowerLocSet;
 509
 510       for (int i = 0; i < list.size(); i++) {
 511         LocPair pair = list.get(i);
 512
 513         if (pair.nonShared != null) {
 514
 515           if (!lattice.getKeySet().contains(pair.nonShared)) {
 516             lattice.insertNewLocationBetween(higherLocName, endLocNameSet, pair.nonShared);
 517           }
 518           higherLocName = pair.nonShared;
 519         }
 520
 521         if (pair.shared != null) {
 522           if (!lattice.getKeySet().contains(pair.shared)) {
 523             lattice.insertNewLocationBetween(higherLocName, endLocNameSet, pair.shared);
 524             lattice.addSharedLoc(pair.shared);
 525           }
 526           higherLocName = pair.shared;
 527         }
 528
 529       }
 530
 531     }
 532
 533   }
 534
 535   private void addLocalLocation(SSJavaLattice<String> lattice, String localLoc) {
 536     if (!mapLatticeToLocalLocSet.containsKey(lattice)) {
 537       mapLatticeToLocalLocSet.put(lattice, new HashSet<String>());
 538     }
 539     mapLatticeToLocalLocSet.get(lattice).add(localLoc);
 540   }
 541
 542   private boolean isLocalLocation(SSJavaLattice<String> lattice, String localLoc) {
 543     if (mapLatticeToLocalLocSet.containsKey(lattice)) {
 544       return mapLatticeToLocalLocSet.get(lattice).contains(localLoc);
 545     }
 546     return false;
 547   }
 548
 549   public Map<InterLocItem, String> getInterLocMap(Descriptor desc) {
 550     if (!mapDescToInterLocMap.containsKey(desc)) {
 551       mapDescToInterLocMap.put(desc, new HashMap<InterLocItem, String>());
 552     }
 553     return mapDescToInterLocMap.get(desc);
 554   }
 555
 556   public Map<LineIdentifier, LinkedList<LocPair>> getLineListMap(Descriptor desc) {
 557     if (!mapDescToLineListMap.containsKey(desc)) {
 558       mapDescToLineListMap.put(desc, new HashMap<LineIdentifier, LinkedList<LocPair>>());
 559     }
 560     return mapDescToLineListMap.get(desc);
 561   }
 562
 563   public LinkedList<LocPair> getLineList(Descriptor desc, LineIdentifier lineId) {
 564     Map<LineIdentifier, LinkedList<LocPair>> map = getLineListMap(desc);
 565     if (!map.containsKey(lineId)) {
 566       map.put(lineId, new LinkedList<LocPair>());
 567     }
 568     return map.get(lineId);
 569   }
 570
 571   private String generateNewLocName() {
 572     String newLocName = "ILOC" + (LocationInference.locSeed++);
 573     System.out.println("newLocName=" + newLocName);
 574     return newLocName;
 575   }
 576
 577   public String getNewLocation(Descriptor desc, String start, Set<String> endSet,
 578       Stack<String> trace, boolean isShared) {
 579
 580     System.out.println("   #GetNewLocation start=" + start + " endSet=" + endSet + " trace="
 581         + trace);
 582
 583     LineIdentifier lineId = new LineIdentifier(start, endSet);
 584     LinkedList<LocPair> list = getLineList(desc, lineId);
 585
 586     int locPairIdx = trace.size() - 1;
 587
 588     LocPair pair;
 589     if (list.size() > locPairIdx) {
 590       // there already exsits a list of nodes up to the current one
 591       pair = list.get(locPairIdx);
 592       // check if we need to add a new shared or non-shred node to the pair
 593       if (isShared) {
 594         if (pair.shared == null) {
 595           pair.shared = generateNewLocName();
 596         }
 597         return pair.shared;
 598       } else {
 599         if (pair.nonShared == null) {
 600           pair.nonShared = generateNewLocName();
 601         }
 602         return pair.nonShared;
 603       }
 604
 605     } else {
 606       // we need to set up a chain of intermediate nodes to the current one.
 607       return recur_getNewLocation(0, list, trace);
 608     }
 609
 610   }
 611
 612   private String recur_getNewLocation(int idx, LinkedList<LocPair> list, Stack<String> trace) {
 613
 614     String curType = trace.pop();
 615     boolean isCurShared = false;
 616     if (curType.equals("S")) {
 617       isCurShared = true;
 618     }
 619
 620     if (list.size() <= idx) {
 621       // need to insert a new pair for the idx
 622       list.add(new LocPair());
 623     }
 624
 625     // here, the list already has a pair for the idx
 626     LocPair pair = list.get(idx);
 627     if (isCurShared && pair.shared == null) {
 628       pair.shared = generateNewLocName();
 629     } else if (!isCurShared && pair.nonShared == null) {
 630       pair.nonShared = generateNewLocName();
 631     }
 632
 633     if (trace.isEmpty()) {
 634       if (isCurShared) {
 635         return pair.shared;
 636       } else {
 637         return pair.nonShared;
 638       }
 639     }
 640
 641     idx++;
 642     return recur_getNewLocation(idx, list, trace);
 643   }
 644
 645   private Set<String> getAboveElementSet(SSJavaLattice<String> lattice, String loc) {
 646
 647     Set<String> aboveSet = new HashSet<String>();
 648
 649     Map<String, Set<String>> latticeMap = lattice.getTable();
 650     Set<String> keySet = latticeMap.keySet();
 651     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 652       String key = (String) iterator.next();
 653       if (latticeMap.get(key).contains(loc)) {
 654         aboveSet.add(key);
 655       }
 656     }
 657
 658     return aboveSet;
 659   }
 660
 661   private boolean needToExpandCombinationNode(Descriptor desc, HNode cnode) {
 662
 663     System.out.println("needToExpandCombinationNode?=" + cnode);
 664
 665     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 666     // HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
 667     Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
 668     Set<HNode> combinationNodeSetInSimpleGraph =
 669         simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 670     System.out.println("---combinationNodeSetInSimpleGraph=" + combinationNodeSetInSimpleGraph);
 671     Set<HNode> inNodeSetToCNode = simpleGraph.getIncomingNodeSet(cnode);
 672     System.out.println("------inNodeSetToCNode=" + inNodeSetToCNode);
 673     for (Iterator iterator = combinationNodeSetInSimpleGraph.iterator(); iterator.hasNext();) {
 674       HNode nodeBelongToTheSameCombinationNode = (HNode) iterator.next();
 675       if (inNodeSetToCNode.contains(nodeBelongToTheSameCombinationNode)) {
 676         // the combination node 'cnode' is not the highest location among the same combination node
 677         return false;
 678       }
 679     }
 680
 681     return true;
 682   }
 683
 684   private void expandCombinationNode(Descriptor desc, SSJavaLattice<String> lattice,
 685       Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc, LocationSummary locSummary,
 686       HNode cnode) {
 687
 688     // expand the combination node 'outNode'
 689     // here we need to expand the corresponding combination location in the lattice
 690     HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
 691
 692     System.out.println("expandCombinationNode=" + cnode + "  cnode in scgraph="
 693         + combinationNodeInSCGraph);
 694
 695     if (combinationNodeInSCGraph == null) {
 696       return;
 697     }
 698
 699     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 700     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 701
 702     Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
 703
 704     // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
 705
 706     Set<HNode> combinationNodeSet =
 707         simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 708
 709     // System.out.println("combinationNodeSet=" + combinationNodeSet);
 710
 711     // TODO
 712     // Set<HNode> endNodeSetFromSimpleGraph =
 713     // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet);
 714     // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 715     // Set<HNode> endCombNodeSet = new HashSet<HNode>();
 716     // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 717     // HNode endNode = (HNode) iterator3.next();
 718     // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 719     // }
 720
 721     Set<HNode> endCombNodeSet = scGraph.getOutgoingNodeSet(combinationNodeInSCGraph);
 722     visited.add(cnode);
 723
 724     // follows the straight line up to another skeleton/combination node
 725     if (endCombNodeSet.size() > 0) {
 726       // System.out.println("---endCombNodeSet=" + endCombNodeSet);
 727       endCombNodeSet =
 728           removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
 729
 730       recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 731           mapIntermediateLoc, 1, locSummary, cnode);
 732     } else {
 733       endCombNodeSet.add(LocationInference.BOTTOMHNODE);
 734       // System.out.println("---endCombNodeSet is zero");
 735       // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 736       // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode));
 737       recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 738           mapIntermediateLoc, 1, locSummary, cnode);
 739
 740     }
 741
 742   }
 743
 744   private Set<HNode> removeTransitivelyReachToNode(Descriptor desc, HNode startNode,
 745       Set<HNode> endNodeSet) {
 746
 747     // if an end node is not directly connected to the start node in the SC graph
 748     // replace it with a directly connected one which transitively reaches to it.
 749
 750     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 751
 752     Set<HNode> newEndNodeSet = new HashSet<HNode>();
 753     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 754       HNode endNode = (HNode) iterator.next();
 755       if (scGraph.isDirectlyConnectedTo(startNode, endNode)) {
 756         newEndNodeSet.add(endNode);
 757       } else {
 758         HNode newEndNode =
 759             getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode);
 760         // System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode);
 761         newEndNodeSet.add(newEndNode);
 762       }
 763     }
 764
 765     // System.out.println("removeTransitivelyReachToNode=" + endNodeSet + "  newSet=" +
 766     // newEndNodeSet);
 767
 768     return newEndNodeSet;
 769
 770   }
 771
 772   private HNode getDirectlyReachableSCNodeFromEndNode(HierarchyGraph scGraph, HNode startNode,
 773       Set<HNode> endNodeSet) {
 774
 775     // System.out.println("getDirectlyReachableSCNodeFromEndNode start=" + startNode +
 776     // " endNodeSet="
 777     // + endNodeSet);
 778     Set<HNode> newStartNodeSet = new HashSet<HNode>();
 779
 780     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 781       HNode endNode = (HNode) iterator.next();
 782       Set<HNode> connectedToEndNodeSet = scGraph.getIncomingNodeSet(endNode);
 783
 784       for (Iterator iterator2 = connectedToEndNodeSet.iterator(); iterator2.hasNext();) {
 785         HNode curNode = (HNode) iterator2.next();
 786         if (recurConnectedFromStartNode(scGraph, startNode, curNode, new HashSet<HNode>())) {
 787           newStartNodeSet.add(curNode);
 788         }
 789       }
 790     }
 791
 792     // System.out.println("newStartNodeSet=" + newStartNodeSet);
 793
 794     if (newStartNodeSet.size() == 0) {
 795       newStartNodeSet.add(startNode);
 796     }
 797
 798     return newStartNodeSet.iterator().next();
 799   }
 800
 801   private boolean recurConnectedFromStartNode(HierarchyGraph scGraph, HNode startNode,
 802       HNode curNode, Set<HNode> visited) {
 803     // return true if curNode is transitively connected from the startNode
 804
 805     boolean isConnected = false;
 806     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 807     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 808       HNode in = (HNode) iterator.next();
 809       if (in.equals(startNode)) {
 810         return true;
 811       } else {
 812         visited.add(in);
 813         isConnected |= recurConnectedFromStartNode(scGraph, startNode, in, visited);
 814       }
 815     }
 816
 817     return isConnected;
 818   }
 819
 820   private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 821       HNode startNode, HNode endNode) {
 822     // System.out.println("getDirectlyReachableNodeFromStartNodeReachToEndNode start=" + startNode
 823     // + " end=" + endNode);
 824     Set<HNode> connected = new HashSet<HNode>();
 825     recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected);
 826     if (connected.size() == 0) {
 827       connected.add(endNode);
 828     }
 829     // System.out.println("connected=" + connected);
 830
 831     return connected.iterator().next();
 832   }
 833
 834   private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 835       HNode startNode, HNode curNode, Set<HNode> connected) {
 836
 837     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 838     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 839       HNode inNode = (HNode) iterator.next();
 840       if (inNode.equals(startNode)) {
 841         connected.add(curNode);
 842       } else {
 843         recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected);
 844       }
 845     }
 846
 847   }
 848
 849   private void recurDFSNormalNode(Descriptor desc, SSJavaLattice<String> lattice, HNode startNode,
 850       Set<HNode> endNodeSet, Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc,
 851       int idx, LocationSummary locSummary, HNode curNode) {
 852
 853     TripleItem item = new TripleItem(startNode, endNodeSet, idx);
 854     if (!mapIntermediateLoc.containsKey(item)) {
 855       // need to create a new intermediate location in the lattice
 856       String newLocName = "ILOC" + (LocationInference.locSeed++);
 857       String above;
 858       if (idx == 1) {
 859         above = startNode.getName();
 860       } else {
 861         int prevIdx = idx - 1;
 862         TripleItem prevItem = new TripleItem(startNode, endNodeSet, prevIdx);
 863         above = mapIntermediateLoc.get(prevItem);
 864       }
 865
 866       Set<String> belowSet = new HashSet<String>();
 867       for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 868         HNode endNode = (HNode) iterator.next();
 869         String locName;
 870         if (locSummary.getMapHNodeNameToLocationName().containsKey(endNode.getName())) {
 871           locName = locSummary.getLocationName(endNode.getName());
 872         } else {
 873           locName = endNode.getName();
 874         }
 875         belowSet.add(locName);
 876       }
 877       lattice.insertNewLocationBetween(above, belowSet, newLocName);
 878
 879       mapIntermediateLoc.put(item, newLocName);
 880     }
 881
 882     String locName = mapIntermediateLoc.get(item);
 883     HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 884
 885     if (curNode.isSharedNode()) {
 886       // if the current node is shared location, add a shared location to the lattice later
 887       System.out.println("###SHARED ITEM=" + item);
 888       mapSharedNodeToTripleItem.put(curNode, item);
 889     } else {
 890       Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
 891       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 892         Descriptor d = (Descriptor) iterator.next();
 893         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 894       }
 895       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 896     }
 897
 898     System.out.println("-TripleItem normal=" + item);
 899     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
 900         + " locName=" + locName + "  isC=" + curNode.isCombinationNode());
 901
 902     Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
 903     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 904       HNode outNode = (HNode) iterator2.next();
 905
 906       Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
 907       System.out.println("outNode=" + outNode);
 908       System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode);
 909
 910       if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
 911         Pair<HNode, HNode> pair = new Pair(startNode, outNode);
 912         if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) {
 913           visited.add(outNode);
 914           int newidx = getCurrentHighestIndex(pair, idx + 1);
 915           // int newidx = getCurrentHighestIndex(outNode, idx + 1);
 916           recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 917               newidx, locSummary, outNode);
 918           // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 919           // idx + 1, locSummary, outNode);
 920         } else {
 921           updateHighestIndex(pair, idx + 1);
 922           // updateHighestIndex(outNode, idx + 1);
 923           System.out.println("NOT RECUR");
 924         }
 925       } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) {
 926         if (needToExpandCombinationNode(desc, outNode)) {
 927           System.out.println("NEED TO");
 928           expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 929         } else {
 930           System.out.println("NOT NEED TO");
 931         }
 932       }
 933
 934     }
 935
 936   }
 937
 938   private void recurDFS(Descriptor desc, SSJavaLattice<String> lattice,
 939       HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
 940       Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode curNode) {
 941
 942     TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx);
 943
 944     if (!mapIntermediateLoc.containsKey(item)) {
 945       // need to create a new intermediate location in the lattice
 946       String above;
 947       if (idx == 1) {
 948         String newLocName = combinationNodeInSCGraph.getName();
 949         mapIntermediateLoc.put(item, newLocName);
 950       } else {
 951         String newLocName = "ILOC" + (LocationInference.locSeed++);
 952         int prevIdx = idx - 1;
 953         TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
 954         above = mapIntermediateLoc.get(prevItem);
 955
 956         Set<String> belowSet = new HashSet<String>();
 957         for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 958           HNode endNode = (HNode) iterator.next();
 959           belowSet.add(endNode.getName());
 960         }
 961         lattice.insertNewLocationBetween(above, belowSet, newLocName);
 962         mapIntermediateLoc.put(item, newLocName);
 963       }
 964
 965     }
 966
 967     // TODO
 968     // Do we need to skip the combination node and assign a shared location to the next node?
 969     // if (idx == 1 && curNode.isSharedNode()) {
 970     // System.out.println("THE FIRST COMBINATION NODE EXPANSION IS SHARED!");
 971     // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, mapIntermediateLoc,
 972     // idx + 1, locSummary, curNode);
 973     // return;
 974     // }
 975
 976     HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 977     String locName = mapIntermediateLoc.get(item);
 978     if (curNode.isSharedNode()) {
 979       // if the current node is shared location, add a shared location to the lattice later
 980       System.out.println("###SHARED ITEM=" + item);
 981       mapSharedNodeToTripleItem.put(curNode, item);
 982     } else {
 983       Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
 984       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 985         Descriptor d = (Descriptor) iterator.next();
 986         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 987       }
 988       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 989     }
 990
 991     System.out.println("-TripleItem=" + item);
 992     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
 993         + " locName=" + locName);
 994
 995     Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
 996     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 997       HNode outNode = (HNode) iterator2.next();
 998       System.out.println("---recurDFS outNode=" + outNode);
 999       System.out.println("---cur combinationNodeInSCGraph=" + combinationNodeInSCGraph);
1000       System.out.println("---outNode combinationNodeInSCGraph="
1001           + getCombinationNodeInSCGraph(desc, outNode));
1002
1003       if (!outNode.isSkeleton() && !visited.contains(outNode)) {
1004         if (outNode.isCombinationNode()) {
1005
1006           Set<HNode> combineSkeletonNodeSet =
1007               simpleHierarchyGraph.getCombineSetByCombinationNode(outNode);
1008           Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
1009           // extract nodes belong to the same combine node
1010           Set<HNode> incomingCombinedHNodeSet = new HashSet<HNode>();
1011           for (Iterator iterator = incomingHNodeSetToOutNode.iterator(); iterator.hasNext();) {
1012             HNode inNode = (HNode) iterator.next();
1013             if (combineSkeletonNodeSet.contains(inNode)) {
1014               incomingCombinedHNodeSet.add(inNode);
1015             }
1016           }
1017           System.out.println("-----incomingCombinedHNodeSet=" + incomingCombinedHNodeSet);
1018
1019           // check whether the next combination node is different from the current node
1020           if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
1021             Pair<HNode, HNode> pair = new Pair(combinationNodeInSCGraph, outNode);
1022             if (visited.containsAll(incomingCombinedHNodeSet)) {
1023               visited.add(outNode);
1024               System.out.println("-------curIdx=" + (idx + 1));
1025
1026               int newIdx = getCurrentHighestIndex(pair, idx + 1);
1027               // int newIdx = getCurrentHighestIndex(outNode, idx + 1);
1028               System.out.println("-------newIdx=" + newIdx);
1029               recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
1030                   mapIntermediateLoc, newIdx, locSummary, outNode);
1031               // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
1032               // mapIntermediateLoc, idx + 1, locSummary, outNode);
1033             } else {
1034               updateHighestIndex(pair, idx + 1);
1035               // updateHighestIndex(outNode, idx + 1);
1036               System.out.println("-----NOT RECUR!");
1037             }
1038           } else {
1039             if (needToExpandCombinationNode(desc, outNode)) {
1040               System.out.println("NEED TO");
1041               expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
1042             } else {
1043               System.out.println("NOT NEED TO");
1044             }
1045
1046           }
1047         }
1048       }
1049       // }
1050
1051     }
1052
1053   }
1054
1055   private int getCurrentHighestIndex(Pair<HNode, HNode> pair, int curIdx) {
1056     int recordedIdx = getCurrentHighestIndex(pair);
1057     if (recordedIdx > curIdx) {
1058       return recordedIdx;
1059     } else {
1060       return curIdx;
1061     }
1062   }
1063
1064   private int getCurrentHighestIndex(HNode node, int curIdx) {
1065     int recordedIdx = getCurrentHighestIndex(node);
1066     if (recordedIdx > curIdx) {
1067       return recordedIdx;
1068     } else {
1069       return curIdx;
1070     }
1071   }
1072
1073   private int getCurrentHighestIndex(Pair<HNode, HNode> pair) {
1074     if (!mapItemToHighestIndex.containsKey(pair)) {
1075       mapItemToHighestIndex.put(pair, new Integer(-1));
1076     }
1077     return mapItemToHighestIndex.get(pair).intValue();
1078   }
1079
1080   private void updateHighestIndex(Pair<HNode, HNode> pair, int idx) {
1081     if (idx > getCurrentHighestIndex(pair)) {
1082       mapItemToHighestIndex.put(pair, new Integer(idx));
1083     }
1084   }
1085
1086   private int getCurrentHighestIndex(HNode node) {
1087     if (!mapHNodeToHighestIndex.containsKey(node)) {
1088       mapHNodeToHighestIndex.put(node, new Integer(-1));
1089     }
1090     return mapHNodeToHighestIndex.get(node).intValue();
1091   }
1092
1093   private void updateHighestIndex(HNode node, int idx) {
1094     if (idx > getCurrentHighestIndex(node)) {
1095       mapHNodeToHighestIndex.put(node, new Integer(idx));
1096     }
1097   }
1098
1099   private String generateElementName(BasisSet basisSet, HierarchyGraph inputGraph,
1100       Map<Set<Integer>, String> mapF2LocName, Set<Integer> F) {
1101
1102     if (mapF2LocName.containsKey(F)) {
1103       return mapF2LocName.get(F);
1104     }
1105
1106     HNode node = basisSet.getHNode(F);
1107     if (node != null) {
1108       mapF2LocName.put(F, node.getName());
1109       return node.getName();
1110     } else {
1111       if (inputGraph.BASISTOPELEMENT.equals(F)) {
1112         return SSJavaAnalysis.BOTTOM;
1113       } else {
1114         String str = "LOC" + (LocationInference.locSeed++);
1115         mapF2LocName.put(F, str);
1116         return str;
1117       }
1118     }
1119   }
1120
1121   private void resetCount(Map<Set<Integer>, Integer> mapFtoCount, Family family) {
1122     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
1123       Set<Integer> F = iter.next();
1124       mapFtoCount.put(F, 0);
1125     }
1126   }
1127
1128   private Map<Set<Integer>, Set<Set<Integer>>> coveringGraph(BasisSet basisSet, Family family) {
1129
1130     Map<Set<Integer>, Integer> mapFtoCount = new HashMap<Set<Integer>, Integer>();
1131     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = new HashMap<Set<Integer>, Set<Set<Integer>>>();
1132
1133     // initialize COUNT(F) to 0 for all elements of the family
1134     resetCount(mapFtoCount, family);
1135
1136     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
1137       Set<Integer> F = iter.next();
1138       Set<HNode> gammaF = family.getGamma(F);
1139
1140       Set<HNode> curHNodeSet = basisSet.getHNodeSet();
1141       curHNodeSet.removeAll(gammaF);
1142       Set<Set<Integer>> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet);
1143
1144       for (Iterator iterator = Bset.iterator(); iterator.hasNext();) {
1145         Set<Integer> B = (Set<Integer>) iterator.next();
1146
1147         Set<Integer> Fprime = new HashSet<Integer>();
1148         Fprime.addAll(F);
1149         Fprime.addAll(B);
1150
1151         // COUNT(F')++;
1152         mapFtoCount.put(Fprime, mapFtoCount.get(Fprime) + 1);
1153
1154         // if |gamma(F')|==COUNT(F') + |gamma(F)|
1155         int numGammaFprime = family.getGamma(Fprime).size();
1156         int countFprime = mapFtoCount.get(Fprime);
1157         int numGammaF = family.getGamma(F).size();
1158         if (numGammaFprime == (countFprime + numGammaF)) {
1159           // ImSucc(F)=IMSucc(F) union F'
1160           addImSucc(mapImSucc, F, Fprime);
1161         }
1162
1163       }
1164       resetCount(mapFtoCount, family);
1165     }
1166
1167     // System.out.println("mapImSucc=" + mapImSucc);
1168
1169     return mapImSucc;
1170   }
1171
1172   private Set<Set<Integer>> getImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F) {
1173     if (!mapImSucc.containsKey(F)) {
1174       mapImSucc.put(F, new HashSet<Set<Integer>>());
1175     }
1176     return mapImSucc.get(F);
1177   }
1178
1179   private void addImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F,
1180       Set<Integer> Fprime) {
1181
1182     if (!mapImSucc.containsKey(F)) {
1183       mapImSucc.put(F, new HashSet<Set<Integer>>());
1184     }
1185
1186     mapImSucc.get(F).add(Fprime);
1187
1188   }
1189
1190   private Family generateFamily(BasisSet basisSet) {
1191
1192     Family family = new Family();
1193
1194     for (Iterator<Set<Integer>> iterator = basisSet.basisIterator(); iterator.hasNext();) {
1195       Set<Integer> B = iterator.next();
1196
1197       Set<Pair<Set<Integer>, Set<HNode>>> tobeadded = new HashSet<Pair<Set<Integer>, Set<HNode>>>();
1198
1199       for (Iterator<Set<Integer>> iterator2 = family.FIterator(); iterator2.hasNext();) {
1200         Set<Integer> F = iterator2.next();
1201
1202         Set<Integer> Fprime = new HashSet<Integer>();
1203         Fprime.addAll(F);
1204         Fprime.addAll(B);
1205
1206         Set<HNode> gammaFPrimeSet = new HashSet<HNode>();
1207         gammaFPrimeSet.addAll(family.getGamma(F));
1208         gammaFPrimeSet.add(basisSet.getHNode(B));
1209
1210         if (!family.containsF(Fprime)) {
1211           Pair<Set<Integer>, Set<HNode>> pair =
1212               new Pair<Set<Integer>, Set<HNode>>(Fprime, gammaFPrimeSet);
1213           tobeadded.add(pair);
1214         } else {
1215           family.updateGammaF(Fprime, gammaFPrimeSet);
1216         }
1217       }
1218
1219       for (Iterator<Pair<Set<Integer>, Set<HNode>>> iterator2 = tobeadded.iterator(); iterator2
1220           .hasNext();) {
1221         Pair<Set<Integer>, Set<HNode>> pair = iterator2.next();
1222         family.addFElement(pair.getFirst());
1223         family.updateGammaF(pair.getFirst(), pair.getSecond());
1224       }
1225
1226     }
1227     return family;
1228   }
1229
1230   private void debug_print(HierarchyGraph inputGraph) {
1231     System.out.println("\nBuild Lattice:" + inputGraph.getName());
1232     System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex());
1233     System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
1234   }
1235
1236   public SSJavaLattice<String> buildLattice(HierarchyGraph hierarchyGraph) {
1237     BasisSet basisSet = hierarchyGraph.computeBasisSet(new HashSet<HNode>());
1238
1239     Family family = generateFamily(basisSet);
1240     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = coveringGraph(basisSet, family);
1241
1242     SSJavaLattice<String> completeLattice = buildLattice(basisSet, hierarchyGraph, mapImSucc);
1243     return completeLattice;
1244   }
1245
1246 }
1247
1248 class Identifier {
1249   public HNode node;
1250   public int idx;
1251
1252   public Identifier(HNode n, int i) {
1253     node = n;
1254     idx = i;
1255   }
1256
1257   public int hashCode() {
1258     return node.hashCode() + idx;
1259   }
1260
1261   public boolean equals(Object obj) {
1262
1263     if (obj instanceof Identifier) {
1264       Identifier in = (Identifier) obj;
1265       if (node.equals(in.node) && idx == in.idx) {
1266         return true;
1267       }
1268     }
1269
1270     return false;
1271   }
1272
1273 }
1274
1275 class LocPair {
1276   public String nonShared;
1277   public String shared;
1278
1279   public int hashCode() {
1280     int h = 0;
1281     if (nonShared != null) {
1282       h = nonShared.hashCode();
1283     }
1284     if (shared != null) {
1285       h = shared.hashCode();
1286     }
1287     return h;
1288   }
1289
1290   public boolean equals(Object obj) {
1291
1292     if (obj instanceof LocPair) {
1293       LocPair in = (LocPair) obj;
1294
1295       if ((nonShared == null && in.nonShared == null)
1296           || (nonShared != null && nonShared.equals(in.nonShared))) {
1297
1298         if ((shared == null && in.shared == null) || (shared != null && shared.equals(in.shared))) {
1299           return true;
1300         }
1301
1302       }
1303
1304     }
1305
1306     return false;
1307   }
1308
1309   public String toString() {
1310     String rtr = "<" + nonShared + "," + shared + ">";
1311     return rtr;
1312   }
1313 }
1314
1315 class LineIdentifier {
1316   public String startLoc;
1317   public Set<String> lowerLocSet;
1318
1319   public LineIdentifier(String s, Set<String> lSet) {
1320     startLoc = s;
1321     lowerLocSet = lSet;
1322   }
1323
1324   public int hashCode() {
1325     int h = 0;
1326     h = startLoc.hashCode();
1327     return h + lowerLocSet.hashCode();
1328   }
1329
1330   public boolean equals(Object obj) {
1331
1332     if (obj instanceof LineIdentifier) {
1333       LineIdentifier in = (LineIdentifier) obj;
1334       if (startLoc.equals(in.startLoc) && lowerLocSet.equals(in.lowerLocSet)) {
1335         return true;
1336       }
1337     }
1338
1339     return false;
1340   }
1341
1342   public String toString() {
1343     String rtr = startLoc + "->" + lowerLocSet;
1344     return rtr;
1345   }
1346
1347 }
1348
1349 class InterLocItem {
1350   public String startLoc;
1351   public Set<String> lowerLocSet;
1352   public int idx;
1353
1354   public InterLocItem(String h, Set<String> l, int i) {
1355     startLoc = h;
1356     lowerLocSet = l;
1357     idx = i;
1358   }
1359
1360   public int hashCode() {
1361
1362     int h = 0;
1363     if (startLoc != null) {
1364       h = startLoc.hashCode();
1365     }
1366
1367     return h + lowerLocSet.hashCode() + idx;
1368   }
1369
1370   public boolean equals(Object obj) {
1371
1372     if (obj instanceof InterLocItem) {
1373       InterLocItem in = (InterLocItem) obj;
1374       if ((startLoc == null || (startLoc != null && startLoc.equals(in.startLoc)))
1375           && lowerLocSet.equals(in.lowerLocSet) && idx == in.idx) {
1376         return true;
1377       }
1378     }
1379
1380     return false;
1381   }
1382
1383   public String toString() {
1384     String rtr = startLoc + "-" + idx + "->" + lowerLocSet;
1385     if (idx % 2 != 0) {
1386       rtr += " S";
1387     }
1388     return rtr;
1389   }
1390 }
1391
1392 class TripleItem {
1393   public HNode higherNode;
1394   public Set<HNode> lowerNodeSet;
1395   public int idx;
1396   public boolean isShared;
1397
1398   public TripleItem(HNode h, Set<HNode> l, int i) {
1399     higherNode = h;
1400     lowerNodeSet = l;
1401     idx = i;
1402     isShared = false;
1403   }
1404
1405   public void setShared(boolean in) {
1406     this.isShared = in;
1407   }
1408
1409   public boolean isShared() {
1410     return isShared;
1411   }
1412
1413   public int hashCode() {
1414
1415     int h = 0;
1416     if (higherNode != null) {
1417       h = higherNode.hashCode();
1418     }
1419
1420     if (isShared) {
1421       h++;
1422     }
1423
1424     return h + lowerNodeSet.hashCode() + idx;
1425   }
1426
1427   public boolean equals(Object obj) {
1428
1429     if (obj instanceof TripleItem) {
1430       TripleItem in = (TripleItem) obj;
1431       if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode)))
1432           && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx && isShared == in.isShared()) {
1433         return true;
1434       }
1435     }
1436
1437     return false;
1438   }
1439
1440   public String toString() {
1441     String rtr = higherNode + "-" + idx + "->" + lowerNodeSet;
1442     if (isShared) {
1443       rtr += " S";
1444     }
1445     return rtr;
1446   }
1447
1448 }