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