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