small diff
[IRC.git] / 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 }