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