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
 321             Set<HNode> reachToSet = hierarchyGraph.getSkeleteNodeSetReachTo(hNode);
 322             for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
 323               HNode reachToNode = (HNode) iterator2.next();
 324               aboveSet.add(scGraph.getCurrentHNode(reachToNode));
 325             }
 326
 327             SCNode = aboveSet.iterator().next();
 328           }
 329
 330           // update above set w.r.t the hierarchy graph with SC nodes
 331           // because the skeleton nodes in the original hierarchy graph may be merged to a new node
 332           Set<HNode> endSet = new HashSet<HNode>();
 333           for (Iterator iterator2 = aboveSet.iterator(); iterator2.hasNext();) {
 334             HNode aboveNode = (HNode) iterator2.next();
 335             endSet.add(hierarchyGraph.getCurrentHNode(aboveNode));
 336           }
 337
 338           trace = hierarchyGraph.computeDistance(hNode, endSet, combineSkeletonNodeSet);
 339
 340           System.out.println("   COUNT-RESULT::start=" + hNode + " end=" + endSet + " trace="
 341               + trace);
 342         }
 343
 344         // 3) convert the node m into a chain of nodes with the last node in the chain having m’s
 345         // outgoing edges.
 346         Set<HNode> outgoingSCNodeSet = scGraph.getOutgoingNodeSet(SCNode);
 347         System.out.println("   outgoing scnode set from " + SCNode + "=" + outgoingSCNodeSet);
 348
 349         // convert hnodes to location names
 350         String startLocName = locSummary.getLocationName(SCNode.getName());
 351         Set<String> outgoingLocNameSet = new HashSet<String>();
 352         for (Iterator iterator2 = outgoingSCNodeSet.iterator(); iterator2.hasNext();) {
 353           HNode outSCNode = (HNode) iterator2.next();
 354           String locName = locSummary.getLocationName(outSCNode.getName());
 355           if (!locName.equals(outSCNode.getName())) {
 356             System.out.println("                         outSCNode=" + outSCNode + " -> locName="
 357                 + locName);
 358           }
 359           outgoingLocNameSet.add(locName);
 360         }
 361
 362         if (outgoingLocNameSet.isEmpty()) {
 363           outgoingLocNameSet.add(lattice.getBottomItem());
 364         }
 365
 366         if (hNode.isCombinationNode()) {
 367           System.out.println("make sure that the first node corresponds to the COMB node="
 368               + startLocName);
 369           LineIdentifier lineId = new LineIdentifier(startLocName, outgoingLocNameSet);
 370           LinkedList<LocPair> list = getLineList(desc, lineId);
 371           // make sure that the first node corresponds to the COMB node
 372           if (list.size() <= 0) {
 373             list.add(new LocPair());
 374           }
 375           LocPair firstPair = list.get(0);
 376           firstPair.nonShared = startLocName;
 377         }
 378
 379         // 4) If hnode is not a shared location, check if there already exists a local variable
 380         // node that has distance d below m along this chain. If such a node
 381         // does not exist, insert it.
 382         String locName =
 383             getNewLocation(desc, startLocName, outgoingLocNameSet, trace, hNode.isSharedNode());
 384
 385         System.out.println("       ###hNode=" + hNode + "---->locName=" + locName);
 386         locSummary.addMapHNodeNameToLocationName(hNode.getName(), locName);
 387
 388       }
 389     }
 390
 391     insertLocalLocations(desc, lattice);
 392
 393     return lattice;
 394   }
 395
 396   private void insertLocalLocations(Descriptor desc, SSJavaLattice<String> lattice) {
 397
 398     Map<LineIdentifier, LinkedList<LocPair>> map = getLineListMap(desc);
 399     System.out.println("####MAP=" + map);
 400
 401     Set<LineIdentifier> lineIdSet = map.keySet();
 402     for (Iterator iterator = lineIdSet.iterator(); iterator.hasNext();) {
 403       LineIdentifier lineId = (LineIdentifier) iterator.next();
 404
 405       LinkedList<LocPair> list = map.get(lineId);
 406
 407       String higherLocName = lineId.startLoc;
 408       Set<String> endLocNameSet = lineId.lowerLocSet;
 409
 410       for (int i = 0; i < list.size(); i++) {
 411         LocPair pair = list.get(i);
 412
 413         if (pair.nonShared != null) {
 414
 415           if (!lattice.getKeySet().contains(pair.nonShared)) {
 416             lattice.insertNewLocationBetween(higherLocName, endLocNameSet, pair.nonShared);
 417           }
 418           higherLocName = pair.nonShared;
 419         }
 420
 421         if (pair.shared != null) {
 422           if (!lattice.getKeySet().contains(pair.shared)) {
 423             lattice.insertNewLocationBetween(higherLocName, endLocNameSet, pair.shared);
 424             lattice.addSharedLoc(pair.shared);
 425           }
 426           higherLocName = pair.shared;
 427         }
 428
 429       }
 430
 431     }
 432
 433   }
 434
 435   private void addLocalLocation(SSJavaLattice<String> lattice, String localLoc) {
 436     if (!mapLatticeToLocalLocSet.containsKey(lattice)) {
 437       mapLatticeToLocalLocSet.put(lattice, new HashSet<String>());
 438     }
 439     mapLatticeToLocalLocSet.get(lattice).add(localLoc);
 440   }
 441
 442   private boolean isLocalLocation(SSJavaLattice<String> lattice, String localLoc) {
 443     if (mapLatticeToLocalLocSet.containsKey(lattice)) {
 444       return mapLatticeToLocalLocSet.get(lattice).contains(localLoc);
 445     }
 446     return false;
 447   }
 448
 449   public Map<InterLocItem, String> getInterLocMap(Descriptor desc) {
 450     if (!mapDescToInterLocMap.containsKey(desc)) {
 451       mapDescToInterLocMap.put(desc, new HashMap<InterLocItem, String>());
 452     }
 453     return mapDescToInterLocMap.get(desc);
 454   }
 455
 456   public Map<LineIdentifier, LinkedList<LocPair>> getLineListMap(Descriptor desc) {
 457     if (!mapDescToLineListMap.containsKey(desc)) {
 458       mapDescToLineListMap.put(desc, new HashMap<LineIdentifier, LinkedList<LocPair>>());
 459     }
 460     return mapDescToLineListMap.get(desc);
 461   }
 462
 463   public LinkedList<LocPair> getLineList(Descriptor desc, LineIdentifier lineId) {
 464     Map<LineIdentifier, LinkedList<LocPair>> map = getLineListMap(desc);
 465     if (!map.containsKey(lineId)) {
 466       map.put(lineId, new LinkedList<LocPair>());
 467     }
 468     return map.get(lineId);
 469   }
 470
 471   private String generateNewLocName() {
 472     String newLocName = "ILOC" + (LocationInference.locSeed++);
 473     System.out.println("newLocName=" + newLocName);
 474     return newLocName;
 475   }
 476
 477   public String getNewLocation(Descriptor desc, String start, Set<String> endSet,
 478       Stack<String> trace, boolean isShared) {
 479
 480     System.out.println("   #GetNewLocation start=" + start + " endSet=" + endSet + " trace="
 481         + trace);
 482
 483     LineIdentifier lineId = new LineIdentifier(start, endSet);
 484     LinkedList<LocPair> list = getLineList(desc, lineId);
 485
 486     int locPairIdx = trace.size() - 1;
 487
 488     LocPair pair;
 489     if (list.size() > locPairIdx) {
 490       // there already exsits a list of nodes up to the current one
 491       pair = list.get(locPairIdx);
 492       // check if we need to add a new shared or non-shred node to the pair
 493       if (isShared) {
 494         if (pair.shared == null) {
 495           pair.shared = generateNewLocName();
 496         }
 497         return pair.shared;
 498       } else {
 499         if (pair.nonShared == null) {
 500           pair.nonShared = generateNewLocName();
 501         }
 502         return pair.nonShared;
 503       }
 504
 505     } else {
 506       // we need to set up a chain of intermediate nodes to the current one.
 507       return recur_getNewLocation(0, list, trace);
 508     }
 509
 510   }
 511
 512   private String recur_getNewLocation(int idx, LinkedList<LocPair> list, Stack<String> trace) {
 513
 514     String curType = trace.pop();
 515     boolean isCurShared = false;
 516     if (curType.equals("S")) {
 517       isCurShared = true;
 518     }
 519
 520     if (list.size() <= idx) {
 521       // need to insert a new pair for the idx
 522       list.add(new LocPair());
 523     }
 524
 525     // here, the list already has a pair for the idx
 526     LocPair pair = list.get(idx);
 527     if (isCurShared && pair.shared == null) {
 528       pair.shared = generateNewLocName();
 529     } else if (!isCurShared && pair.nonShared == null) {
 530       pair.nonShared = generateNewLocName();
 531     }
 532
 533     if (trace.isEmpty()) {
 534       if (isCurShared) {
 535         return pair.shared;
 536       } else {
 537         return pair.nonShared;
 538       }
 539     }
 540
 541     idx++;
 542     return recur_getNewLocation(idx, list, trace);
 543   }
 544
 545   private Set<String> getAboveElementSet(SSJavaLattice<String> lattice, String loc) {
 546
 547     Set<String> aboveSet = new HashSet<String>();
 548
 549     Map<String, Set<String>> latticeMap = lattice.getTable();
 550     Set<String> keySet = latticeMap.keySet();
 551     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 552       String key = (String) iterator.next();
 553       if (latticeMap.get(key).contains(loc)) {
 554         aboveSet.add(key);
 555       }
 556     }
 557
 558     return aboveSet;
 559   }
 560
 561   private boolean needToExpandCombinationNode(Descriptor desc, HNode cnode) {
 562
 563     System.out.println("needToExpandCombinationNode?=" + cnode);
 564
 565     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 566     // HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
 567     Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
 568     Set<HNode> combinationNodeSetInSimpleGraph =
 569         simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 570     System.out.println("---combinationNodeSetInSimpleGraph=" + combinationNodeSetInSimpleGraph);
 571     Set<HNode> inNodeSetToCNode = simpleGraph.getIncomingNodeSet(cnode);
 572     System.out.println("------inNodeSetToCNode=" + inNodeSetToCNode);
 573     for (Iterator iterator = combinationNodeSetInSimpleGraph.iterator(); iterator.hasNext();) {
 574       HNode nodeBelongToTheSameCombinationNode = (HNode) iterator.next();
 575       if (inNodeSetToCNode.contains(nodeBelongToTheSameCombinationNode)) {
 576         // the combination node 'cnode' is not the highest location among the same combination node
 577         return false;
 578       }
 579     }
 580
 581     return true;
 582   }
 583
 584   private void expandCombinationNode(Descriptor desc, SSJavaLattice<String> lattice,
 585       Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc, LocationSummary locSummary,
 586       HNode cnode) {
 587
 588     // expand the combination node 'outNode'
 589     // here we need to expand the corresponding combination location in the lattice
 590     HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, cnode);
 591
 592     System.out.println("expandCombinationNode=" + cnode + "  cnode in scgraph="
 593         + combinationNodeInSCGraph);
 594
 595     if (combinationNodeInSCGraph == null) {
 596       return;
 597     }
 598
 599     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 600     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 601
 602     Set<HNode> combineSkeletonNodeSet = simpleGraph.getCombineSetByCombinationNode(cnode);
 603
 604     // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
 605
 606     Set<HNode> combinationNodeSet =
 607         simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 608
 609     // System.out.println("combinationNodeSet=" + combinationNodeSet);
 610
 611     // TODO
 612     // Set<HNode> endNodeSetFromSimpleGraph =
 613     // simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(cnode, combinationNodeSet);
 614     // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 615     // Set<HNode> endCombNodeSet = new HashSet<HNode>();
 616     // for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 617     // HNode endNode = (HNode) iterator3.next();
 618     // endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 619     // }
 620
 621     Set<HNode> endCombNodeSet = scGraph.getOutgoingNodeSet(combinationNodeInSCGraph);
 622     visited.add(cnode);
 623
 624     // follows the straight line up to another skeleton/combination node
 625     if (endCombNodeSet.size() > 0) {
 626       // System.out.println("---endCombNodeSet=" + endCombNodeSet);
 627       endCombNodeSet =
 628           removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
 629
 630       recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 631           mapIntermediateLoc, 1, locSummary, cnode);
 632     } else {
 633       endCombNodeSet.add(LocationInference.BOTTOMHNODE);
 634       // System.out.println("---endCombNodeSet is zero");
 635       // System.out.println("---endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 636       // System.out.println("---incoming=" + simpleGraph.getIncomingNodeSet(cnode));
 637       recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 638           mapIntermediateLoc, 1, locSummary, cnode);
 639
 640     }
 641
 642   }
 643
 644   private Set<HNode> removeTransitivelyReachToNode(Descriptor desc, HNode startNode,
 645       Set<HNode> endNodeSet) {
 646
 647     // if an end node is not directly connected to the start node in the SC graph
 648     // replace it with a directly connected one which transitively reaches to it.
 649
 650     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 651
 652     Set<HNode> newEndNodeSet = new HashSet<HNode>();
 653     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 654       HNode endNode = (HNode) iterator.next();
 655       if (scGraph.isDirectlyConnectedTo(startNode, endNode)) {
 656         newEndNodeSet.add(endNode);
 657       } else {
 658         HNode newEndNode =
 659             getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode);
 660         // System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode);
 661         newEndNodeSet.add(newEndNode);
 662       }
 663     }
 664
 665     // System.out.println("removeTransitivelyReachToNode=" + endNodeSet + "  newSet=" +
 666     // newEndNodeSet);
 667
 668     return newEndNodeSet;
 669
 670   }
 671
 672   private HNode getDirectlyReachableSCNodeFromEndNode(HierarchyGraph scGraph, HNode startNode,
 673       Set<HNode> endNodeSet) {
 674
 675     // System.out.println("getDirectlyReachableSCNodeFromEndNode start=" + startNode +
 676     // " endNodeSet="
 677     // + endNodeSet);
 678     Set<HNode> newStartNodeSet = new HashSet<HNode>();
 679
 680     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 681       HNode endNode = (HNode) iterator.next();
 682       Set<HNode> connectedToEndNodeSet = scGraph.getIncomingNodeSet(endNode);
 683
 684       for (Iterator iterator2 = connectedToEndNodeSet.iterator(); iterator2.hasNext();) {
 685         HNode curNode = (HNode) iterator2.next();
 686         if (recurConnectedFromStartNode(scGraph, startNode, curNode, new HashSet<HNode>())) {
 687           newStartNodeSet.add(curNode);
 688         }
 689       }
 690     }
 691
 692     // System.out.println("newStartNodeSet=" + newStartNodeSet);
 693
 694     if (newStartNodeSet.size() == 0) {
 695       newStartNodeSet.add(startNode);
 696     }
 697
 698     return newStartNodeSet.iterator().next();
 699   }
 700
 701   private boolean recurConnectedFromStartNode(HierarchyGraph scGraph, HNode startNode,
 702       HNode curNode, Set<HNode> visited) {
 703     // return true if curNode is transitively connected from the startNode
 704
 705     boolean isConnected = false;
 706     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 707     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 708       HNode in = (HNode) iterator.next();
 709       if (in.equals(startNode)) {
 710         return true;
 711       } else {
 712         visited.add(in);
 713         isConnected |= recurConnectedFromStartNode(scGraph, startNode, in, visited);
 714       }
 715     }
 716
 717     return isConnected;
 718   }
 719
 720   private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 721       HNode startNode, HNode endNode) {
 722     // System.out.println("getDirectlyReachableNodeFromStartNodeReachToEndNode start=" + startNode
 723     // + " end=" + endNode);
 724     Set<HNode> connected = new HashSet<HNode>();
 725     recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected);
 726     if (connected.size() == 0) {
 727       connected.add(endNode);
 728     }
 729     // System.out.println("connected=" + connected);
 730
 731     return connected.iterator().next();
 732   }
 733
 734   private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 735       HNode startNode, HNode curNode, Set<HNode> connected) {
 736
 737     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 738     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 739       HNode inNode = (HNode) iterator.next();
 740       if (inNode.equals(startNode)) {
 741         connected.add(curNode);
 742       } else {
 743         recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected);
 744       }
 745     }
 746
 747   }
 748
 749   private void recurDFSNormalNode(Descriptor desc, SSJavaLattice<String> lattice, HNode startNode,
 750       Set<HNode> endNodeSet, Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc,
 751       int idx, LocationSummary locSummary, HNode curNode) {
 752
 753     TripleItem item = new TripleItem(startNode, endNodeSet, idx);
 754     if (!mapIntermediateLoc.containsKey(item)) {
 755       // need to create a new intermediate location in the lattice
 756       String newLocName = "ILOC" + (LocationInference.locSeed++);
 757       String above;
 758       if (idx == 1) {
 759         above = startNode.getName();
 760       } else {
 761         int prevIdx = idx - 1;
 762         TripleItem prevItem = new TripleItem(startNode, endNodeSet, prevIdx);
 763         above = mapIntermediateLoc.get(prevItem);
 764       }
 765
 766       Set<String> belowSet = new HashSet<String>();
 767       for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 768         HNode endNode = (HNode) iterator.next();
 769         String locName;
 770         if (locSummary.getMapHNodeNameToLocationName().containsKey(endNode.getName())) {
 771           locName = locSummary.getLocationName(endNode.getName());
 772         } else {
 773           locName = endNode.getName();
 774         }
 775         belowSet.add(locName);
 776       }
 777       lattice.insertNewLocationBetween(above, belowSet, newLocName);
 778
 779       mapIntermediateLoc.put(item, newLocName);
 780     }
 781
 782     String locName = mapIntermediateLoc.get(item);
 783     HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 784
 785     if (curNode.isSharedNode()) {
 786       // if the current node is shared location, add a shared location to the lattice later
 787       System.out.println("###SHARED ITEM=" + item);
 788       mapSharedNodeToTripleItem.put(curNode, item);
 789     } else {
 790       Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
 791       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 792         Descriptor d = (Descriptor) iterator.next();
 793         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 794       }
 795       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 796     }
 797
 798     System.out.println("-TripleItem normal=" + item);
 799     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
 800         + " locName=" + locName + "  isC=" + curNode.isCombinationNode());
 801
 802     Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
 803     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 804       HNode outNode = (HNode) iterator2.next();
 805
 806       Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
 807       System.out.println("outNode=" + outNode);
 808       System.out.println("---incomingHNodeSetToOutNode=" + incomingHNodeSetToOutNode);
 809
 810       if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
 811         Pair<HNode, HNode> pair = new Pair(startNode, outNode);
 812         if (visited.containsAll(simpleHierarchyGraph.getIncomingNodeSet(outNode))) {
 813           visited.add(outNode);
 814           int newidx = getCurrentHighestIndex(pair, idx + 1);
 815           // int newidx = getCurrentHighestIndex(outNode, idx + 1);
 816           recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 817               newidx, locSummary, outNode);
 818           // recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 819           // idx + 1, locSummary, outNode);
 820         } else {
 821           updateHighestIndex(pair, idx + 1);
 822           // updateHighestIndex(outNode, idx + 1);
 823           System.out.println("NOT RECUR");
 824         }
 825       } else if (!outNode.isSkeleton() && outNode.isCombinationNode() && !visited.contains(outNode)) {
 826         if (needToExpandCombinationNode(desc, outNode)) {
 827           System.out.println("NEED TO");
 828           expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 829         } else {
 830           System.out.println("NOT NEED TO");
 831         }
 832       }
 833
 834     }
 835
 836   }
 837
 838   private void recurDFS(Descriptor desc, SSJavaLattice<String> lattice,
 839       HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
 840       Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode curNode) {
 841
 842     TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx);
 843
 844     if (!mapIntermediateLoc.containsKey(item)) {
 845       // need to create a new intermediate location in the lattice
 846       String above;
 847       if (idx == 1) {
 848         String newLocName = combinationNodeInSCGraph.getName();
 849         mapIntermediateLoc.put(item, newLocName);
 850       } else {
 851         String newLocName = "ILOC" + (LocationInference.locSeed++);
 852         int prevIdx = idx - 1;
 853         TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
 854         above = mapIntermediateLoc.get(prevItem);
 855
 856         Set<String> belowSet = new HashSet<String>();
 857         for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 858           HNode endNode = (HNode) iterator.next();
 859           belowSet.add(endNode.getName());
 860         }
 861         lattice.insertNewLocationBetween(above, belowSet, newLocName);
 862         mapIntermediateLoc.put(item, newLocName);
 863       }
 864
 865     }
 866
 867     // TODO
 868     // Do we need to skip the combination node and assign a shared location to the next node?
 869     // if (idx == 1 && curNode.isSharedNode()) {
 870     // System.out.println("THE FIRST COMBINATION NODE EXPANSION IS SHARED!");
 871     // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited, mapIntermediateLoc,
 872     // idx + 1, locSummary, curNode);
 873     // return;
 874     // }
 875
 876     HierarchyGraph simpleHierarchyGraph = infer.getSimpleHierarchyGraph(desc);
 877     String locName = mapIntermediateLoc.get(item);
 878     if (curNode.isSharedNode()) {
 879       // if the current node is shared location, add a shared location to the lattice later
 880       System.out.println("###SHARED ITEM=" + item);
 881       mapSharedNodeToTripleItem.put(curNode, item);
 882     } else {
 883       Set<Descriptor> descSet = simpleHierarchyGraph.getDescSetOfNode(curNode);
 884       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 885         Descriptor d = (Descriptor) iterator.next();
 886         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 887       }
 888       locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 889     }
 890
 891     System.out.println("-TripleItem=" + item);
 892     System.out.println("-curNode=" + curNode.getName() + " S=" + curNode.isSharedNode()
 893         + " locName=" + locName);
 894
 895     Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSet(curNode);
 896     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 897       HNode outNode = (HNode) iterator2.next();
 898       System.out.println("---recurDFS outNode=" + outNode);
 899       System.out.println("---cur combinationNodeInSCGraph=" + combinationNodeInSCGraph);
 900       System.out.println("---outNode combinationNodeInSCGraph="
 901           + getCombinationNodeInSCGraph(desc, outNode));
 902
 903       if (!outNode.isSkeleton() && !visited.contains(outNode)) {
 904         if (outNode.isCombinationNode()) {
 905
 906           Set<HNode> combineSkeletonNodeSet =
 907               simpleHierarchyGraph.getCombineSetByCombinationNode(outNode);
 908           Set<HNode> incomingHNodeSetToOutNode = simpleHierarchyGraph.getIncomingNodeSet(outNode);
 909           // extract nodes belong to the same combine node
 910           Set<HNode> incomingCombinedHNodeSet = new HashSet<HNode>();
 911           for (Iterator iterator = incomingHNodeSetToOutNode.iterator(); iterator.hasNext();) {
 912             HNode inNode = (HNode) iterator.next();
 913             if (combineSkeletonNodeSet.contains(inNode)) {
 914               incomingCombinedHNodeSet.add(inNode);
 915             }
 916           }
 917           System.out.println("-----incomingCombinedHNodeSet=" + incomingCombinedHNodeSet);
 918
 919           // check whether the next combination node is different from the current node
 920           if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
 921             Pair<HNode, HNode> pair = new Pair(combinationNodeInSCGraph, outNode);
 922             if (visited.containsAll(incomingCombinedHNodeSet)) {
 923               visited.add(outNode);
 924               System.out.println("-------curIdx=" + (idx + 1));
 925
 926               int newIdx = getCurrentHighestIndex(pair, idx + 1);
 927               // int newIdx = getCurrentHighestIndex(outNode, idx + 1);
 928               System.out.println("-------newIdx=" + newIdx);
 929               recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
 930                   mapIntermediateLoc, newIdx, locSummary, outNode);
 931               // recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
 932               // mapIntermediateLoc, idx + 1, locSummary, outNode);
 933             } else {
 934               updateHighestIndex(pair, idx + 1);
 935               // updateHighestIndex(outNode, idx + 1);
 936               System.out.println("-----NOT RECUR!");
 937             }
 938           } else {
 939             if (needToExpandCombinationNode(desc, outNode)) {
 940               System.out.println("NEED TO");
 941               expandCombinationNode(desc, lattice, visited, mapIntermediateLoc, locSummary, outNode);
 942             } else {
 943               System.out.println("NOT NEED TO");
 944             }
 945
 946           }
 947         }
 948       }
 949       // }
 950
 951     }
 952
 953   }
 954
 955   private int getCurrentHighestIndex(Pair<HNode, HNode> pair, int curIdx) {
 956     int recordedIdx = getCurrentHighestIndex(pair);
 957     if (recordedIdx > curIdx) {
 958       return recordedIdx;
 959     } else {
 960       return curIdx;
 961     }
 962   }
 963
 964   private int getCurrentHighestIndex(HNode node, int curIdx) {
 965     int recordedIdx = getCurrentHighestIndex(node);
 966     if (recordedIdx > curIdx) {
 967       return recordedIdx;
 968     } else {
 969       return curIdx;
 970     }
 971   }
 972
 973   private int getCurrentHighestIndex(Pair<HNode, HNode> pair) {
 974     if (!mapItemToHighestIndex.containsKey(pair)) {
 975       mapItemToHighestIndex.put(pair, new Integer(-1));
 976     }
 977     return mapItemToHighestIndex.get(pair).intValue();
 978   }
 979
 980   private void updateHighestIndex(Pair<HNode, HNode> pair, int idx) {
 981     if (idx > getCurrentHighestIndex(pair)) {
 982       mapItemToHighestIndex.put(pair, new Integer(idx));
 983     }
 984   }
 985
 986   private int getCurrentHighestIndex(HNode node) {
 987     if (!mapHNodeToHighestIndex.containsKey(node)) {
 988       mapHNodeToHighestIndex.put(node, new Integer(-1));
 989     }
 990     return mapHNodeToHighestIndex.get(node).intValue();
 991   }
 992
 993   private void updateHighestIndex(HNode node, int idx) {
 994     if (idx > getCurrentHighestIndex(node)) {
 995       mapHNodeToHighestIndex.put(node, new Integer(idx));
 996     }
 997   }
 998
 999   private String generateElementName(BasisSet basisSet, HierarchyGraph inputGraph,
1000       Map<Set<Integer>, String> mapF2LocName, Set<Integer> F) {
1001
1002     if (mapF2LocName.containsKey(F)) {
1003       return mapF2LocName.get(F);
1004     }
1005
1006     HNode node = basisSet.getHNode(F);
1007     if (node != null) {
1008       mapF2LocName.put(F, node.getName());
1009       return node.getName();
1010     } else {
1011       if (inputGraph.BASISTOPELEMENT.equals(F)) {
1012         return SSJavaAnalysis.BOTTOM;
1013       } else {
1014         String str = "LOC" + (LocationInference.locSeed++);
1015         mapF2LocName.put(F, str);
1016         return str;
1017       }
1018     }
1019   }
1020
1021   private void resetCount(Map<Set<Integer>, Integer> mapFtoCount, Family family) {
1022     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
1023       Set<Integer> F = iter.next();
1024       mapFtoCount.put(F, 0);
1025     }
1026   }
1027
1028   private Map<Set<Integer>, Set<Set<Integer>>> coveringGraph(BasisSet basisSet, Family family) {
1029
1030     Map<Set<Integer>, Integer> mapFtoCount = new HashMap<Set<Integer>, Integer>();
1031     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = new HashMap<Set<Integer>, Set<Set<Integer>>>();
1032
1033     // initialize COUNT(F) to 0 for all elements of the family
1034     resetCount(mapFtoCount, family);
1035
1036     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
1037       Set<Integer> F = iter.next();
1038       Set<HNode> gammaF = family.getGamma(F);
1039
1040       Set<HNode> curHNodeSet = basisSet.getHNodeSet();
1041       curHNodeSet.removeAll(gammaF);
1042       Set<Set<Integer>> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet);
1043
1044       for (Iterator iterator = Bset.iterator(); iterator.hasNext();) {
1045         Set<Integer> B = (Set<Integer>) iterator.next();
1046
1047         Set<Integer> Fprime = new HashSet<Integer>();
1048         Fprime.addAll(F);
1049         Fprime.addAll(B);
1050
1051         // COUNT(F')++;
1052         mapFtoCount.put(Fprime, mapFtoCount.get(Fprime) + 1);
1053
1054         // if |gamma(F')|==COUNT(F') + |gamma(F)|
1055         int numGammaFprime = family.getGamma(Fprime).size();
1056         int countFprime = mapFtoCount.get(Fprime);
1057         int numGammaF = family.getGamma(F).size();
1058         if (numGammaFprime == (countFprime + numGammaF)) {
1059           // ImSucc(F)=IMSucc(F) union F'
1060           addImSucc(mapImSucc, F, Fprime);
1061         }
1062
1063       }
1064       resetCount(mapFtoCount, family);
1065     }
1066
1067     // System.out.println("mapImSucc=" + mapImSucc);
1068
1069     return mapImSucc;
1070   }
1071
1072   private Set<Set<Integer>> getImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F) {
1073     if (!mapImSucc.containsKey(F)) {
1074       mapImSucc.put(F, new HashSet<Set<Integer>>());
1075     }
1076     return mapImSucc.get(F);
1077   }
1078
1079   private void addImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F,
1080       Set<Integer> Fprime) {
1081
1082     if (!mapImSucc.containsKey(F)) {
1083       mapImSucc.put(F, new HashSet<Set<Integer>>());
1084     }
1085
1086     mapImSucc.get(F).add(Fprime);
1087
1088   }
1089
1090   private Family generateFamily(BasisSet basisSet) {
1091
1092     Family family = new Family();
1093
1094     for (Iterator<Set<Integer>> iterator = basisSet.basisIterator(); iterator.hasNext();) {
1095       Set<Integer> B = iterator.next();
1096
1097       Set<Pair<Set<Integer>, Set<HNode>>> tobeadded = new HashSet<Pair<Set<Integer>, Set<HNode>>>();
1098
1099       for (Iterator<Set<Integer>> iterator2 = family.FIterator(); iterator2.hasNext();) {
1100         Set<Integer> F = iterator2.next();
1101
1102         Set<Integer> Fprime = new HashSet<Integer>();
1103         Fprime.addAll(F);
1104         Fprime.addAll(B);
1105
1106         Set<HNode> gammaFPrimeSet = new HashSet<HNode>();
1107         gammaFPrimeSet.addAll(family.getGamma(F));
1108         gammaFPrimeSet.add(basisSet.getHNode(B));
1109
1110         if (!family.containsF(Fprime)) {
1111           Pair<Set<Integer>, Set<HNode>> pair =
1112               new Pair<Set<Integer>, Set<HNode>>(Fprime, gammaFPrimeSet);
1113           tobeadded.add(pair);
1114         } else {
1115           family.updateGammaF(Fprime, gammaFPrimeSet);
1116         }
1117       }
1118
1119       for (Iterator<Pair<Set<Integer>, Set<HNode>>> iterator2 = tobeadded.iterator(); iterator2
1120           .hasNext();) {
1121         Pair<Set<Integer>, Set<HNode>> pair = iterator2.next();
1122         family.addFElement(pair.getFirst());
1123         family.updateGammaF(pair.getFirst(), pair.getSecond());
1124       }
1125
1126     }
1127     return family;
1128   }
1129
1130   private void debug_print(HierarchyGraph inputGraph) {
1131     System.out.println("\nBuild Lattice:" + inputGraph.getName());
1132     System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex());
1133     System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
1134   }
1135
1136 }
1137
1138 class Identifier {
1139   public HNode node;
1140   public int idx;
1141
1142   public Identifier(HNode n, int i) {
1143     node = n;
1144     idx = i;
1145   }
1146
1147   public int hashCode() {
1148     return node.hashCode() + idx;
1149   }
1150
1151   public boolean equals(Object obj) {
1152
1153     if (obj instanceof Identifier) {
1154       Identifier in = (Identifier) obj;
1155       if (node.equals(in.node) && idx == in.idx) {
1156         return true;
1157       }
1158     }
1159
1160     return false;
1161   }
1162
1163 }
1164
1165 class LocPair {
1166   public String nonShared;
1167   public String shared;
1168
1169   public int hashCode() {
1170     int h = 0;
1171     if (nonShared != null) {
1172       h = nonShared.hashCode();
1173     }
1174     if (shared != null) {
1175       h = shared.hashCode();
1176     }
1177     return h;
1178   }
1179
1180   public boolean equals(Object obj) {
1181
1182     if (obj instanceof LocPair) {
1183       LocPair in = (LocPair) obj;
1184
1185       if ((nonShared == null && in.nonShared == null)
1186           || (nonShared != null && nonShared.equals(in.nonShared))) {
1187
1188         if ((shared == null && in.shared == null) || (shared != null && shared.equals(in.shared))) {
1189           return true;
1190         }
1191
1192       }
1193
1194     }
1195
1196     return false;
1197   }
1198
1199   public String toString() {
1200     String rtr = "<" + nonShared + "," + shared + ">";
1201     return rtr;
1202   }
1203 }
1204
1205 class LineIdentifier {
1206   public String startLoc;
1207   public Set<String> lowerLocSet;
1208
1209   public LineIdentifier(String s, Set<String> lSet) {
1210     startLoc = s;
1211     lowerLocSet = lSet;
1212   }
1213
1214   public int hashCode() {
1215     int h = 0;
1216     h = startLoc.hashCode();
1217     return h + lowerLocSet.hashCode();
1218   }
1219
1220   public boolean equals(Object obj) {
1221
1222     if (obj instanceof LineIdentifier) {
1223       LineIdentifier in = (LineIdentifier) obj;
1224       if (startLoc.equals(in.startLoc) && lowerLocSet.equals(in.lowerLocSet)) {
1225         return true;
1226       }
1227     }
1228
1229     return false;
1230   }
1231
1232   public String toString() {
1233     String rtr = startLoc + "->" + lowerLocSet;
1234     return rtr;
1235   }
1236
1237 }
1238
1239 class InterLocItem {
1240   public String startLoc;
1241   public Set<String> lowerLocSet;
1242   public int idx;
1243
1244   public InterLocItem(String h, Set<String> l, int i) {
1245     startLoc = h;
1246     lowerLocSet = l;
1247     idx = i;
1248   }
1249
1250   public int hashCode() {
1251
1252     int h = 0;
1253     if (startLoc != null) {
1254       h = startLoc.hashCode();
1255     }
1256
1257     return h + lowerLocSet.hashCode() + idx;
1258   }
1259
1260   public boolean equals(Object obj) {
1261
1262     if (obj instanceof InterLocItem) {
1263       InterLocItem in = (InterLocItem) obj;
1264       if ((startLoc == null || (startLoc != null && startLoc.equals(in.startLoc)))
1265           && lowerLocSet.equals(in.lowerLocSet) && idx == in.idx) {
1266         return true;
1267       }
1268     }
1269
1270     return false;
1271   }
1272
1273   public String toString() {
1274     String rtr = startLoc + "-" + idx + "->" + lowerLocSet;
1275     if (idx % 2 != 0) {
1276       rtr += " S";
1277     }
1278     return rtr;
1279   }
1280 }
1281
1282 class TripleItem {
1283   public HNode higherNode;
1284   public Set<HNode> lowerNodeSet;
1285   public int idx;
1286   public boolean isShared;
1287
1288   public TripleItem(HNode h, Set<HNode> l, int i) {
1289     higherNode = h;
1290     lowerNodeSet = l;
1291     idx = i;
1292     isShared = false;
1293   }
1294
1295   public void setShared(boolean in) {
1296     this.isShared = in;
1297   }
1298
1299   public boolean isShared() {
1300     return isShared;
1301   }
1302
1303   public int hashCode() {
1304
1305     int h = 0;
1306     if (higherNode != null) {
1307       h = higherNode.hashCode();
1308     }
1309
1310     if (isShared) {
1311       h++;
1312     }
1313
1314     return h + lowerNodeSet.hashCode() + idx;
1315   }
1316
1317   public boolean equals(Object obj) {
1318
1319     if (obj instanceof TripleItem) {
1320       TripleItem in = (TripleItem) obj;
1321       if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode)))
1322           && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx && isShared == in.isShared()) {
1323         return true;
1324       }
1325     }
1326
1327     return false;
1328   }
1329
1330   public String toString() {
1331     String rtr = higherNode + "-" + idx + "->" + lowerNodeSet;
1332     if (isShared) {
1333       rtr += " S";
1334     }
1335     return rtr;
1336   }
1337
1338 }