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.Descriptor;
  10 import IR.MethodDescriptor;
  11 import Util.Pair;
  12
  13 public class BuildLattice {
  14
  15   public static int seed = 0;
  16   private LocationInference infer;
  17
  18   private final HNode topNode;
  19   private final HNode bottomNode;
  20
  21   public BuildLattice(LocationInference infer) {
  22     this.infer = infer;
  23     topNode = new HNode(infer.ssjava.TOP);
  24     bottomNode = new HNode(infer.ssjava.BOTTOM);
  25   }
  26
  27   public SSJavaLattice<String> buildLattice(Descriptor desc) {
  28
  29     HierarchyGraph inputGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
  30     LocationSummary locSummary = infer.getLocationSummary(desc);
  31
  32     Set<HNode> nodeSetWithCompositeLocation = new HashSet<HNode>();
  33     if (desc instanceof MethodDescriptor) {
  34       FlowGraph flowGraph = infer.getFlowGraph((MethodDescriptor) desc);
  35
  36       for (Iterator iterator = inputGraph.getNodeSet().iterator(); iterator.hasNext();) {
  37         HNode hnode = (HNode) iterator.next();
  38         Descriptor hnodeDesc = hnode.getDescriptor();
  39         if (hnodeDesc != null) {
  40           NTuple<Descriptor> descTuple = new NTuple<Descriptor>();
  41           descTuple.add(hnodeDesc);
  42
  43           if (flowGraph.contains(descTuple)) {
  44             FlowNode flowNode = flowGraph.getFlowNode(descTuple);
  45             if (flowNode.getCompositeLocation() != null) {
  46               nodeSetWithCompositeLocation.add(hnode);
  47             }
  48           }
  49
  50         }
  51       }
  52
  53     }
  54
  55     BasisSet basisSet = inputGraph.computeBasisSet(nodeSetWithCompositeLocation);
  56     debug_print(inputGraph);
  57
  58     Family family = generateFamily(basisSet);
  59     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = coveringGraph(basisSet, family);
  60
  61     SSJavaLattice<String> lattice = buildLattice(basisSet, inputGraph, locSummary, mapImSucc);
  62     return lattice;
  63
  64   }
  65
  66   private SSJavaLattice<String> buildLattice(BasisSet basisSet, HierarchyGraph inputGraph,
  67       LocationSummary locSummary, Map<Set<Integer>, Set<Set<Integer>>> mapImSucc) {
  68
  69     SSJavaLattice<String> lattice =
  70         new SSJavaLattice<String>(SSJavaAnalysis.TOP, SSJavaAnalysis.BOTTOM);
  71
  72     Map<Set<Integer>, String> mapFToLocName = new HashMap<Set<Integer>, String>();
  73
  74     Set<Set<Integer>> keySet = mapImSucc.keySet();
  75     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
  76       Set<Integer> higher = (Set<Integer>) iterator.next();
  77
  78       String higherName = generateElementName(basisSet, inputGraph, mapFToLocName, higher);
  79
  80       HNode higherNode = inputGraph.getHNode(higherName);
  81       if (higherNode != null && higherNode.isSharedNode()) {
  82         lattice.addSharedLoc(higherName);
  83       }
  84       Set<Descriptor> descSet = inputGraph.getDescSetOfNode(higherNode);
  85       // System.out.println("higherName=" + higherName + "  higherNode=" + higherNode + "  descSet="
  86       // + descSet);
  87       for (Iterator iterator2 = descSet.iterator(); iterator2.hasNext();) {
  88         Descriptor d = (Descriptor) iterator2.next();
  89         locSummary.addMapHNodeNameToLocationName(d.getSymbol(), higherName);
  90       }
  91       // locSummary.addMapHNodeNameToLocationName(higherName, higherName);
  92
  93       Set<Set<Integer>> lowerSet = mapImSucc.get(higher);
  94       for (Iterator iterator2 = lowerSet.iterator(); iterator2.hasNext();) {
  95         Set<Integer> lower = (Set<Integer>) iterator2.next();
  96
  97         String lowerName = generateElementName(basisSet, inputGraph, mapFToLocName, lower);
  98         HNode lowerNode = inputGraph.getHNode(lowerName);
  99         if (lowerNode != null && lowerNode.isSharedNode()) {
 100           lattice.addSharedLoc(lowerName);
 101         }
 102
 103         Set<Descriptor> lowerDescSet = inputGraph.getDescSetOfNode(lowerNode);
 104         // System.out.println("lowerName=" + lowerName + "  lowerNode=" + lowerNode + "  descSet="
 105         // + lowerDescSet);
 106         for (Iterator iterator3 = lowerDescSet.iterator(); iterator3.hasNext();) {
 107           Descriptor d = (Descriptor) iterator3.next();
 108           locSummary.addMapHNodeNameToLocationName(d.getSymbol(), lowerName);
 109         }
 110         // locSummary.addMapHNodeNameToLocationName(lowerName, lowerName);
 111
 112         if (higher.size() == 0) {
 113           // empty case
 114           lattice.put(lowerName);
 115         } else {
 116           lattice.addRelationHigherToLower(higherName, lowerName);
 117         }
 118
 119       }
 120
 121     }
 122
 123     return lattice;
 124   }
 125
 126   public HNode getCombinationNodeInSCGraph(Descriptor desc, HNode nodeFromSimpleGraph) {
 127
 128     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 129
 130     if (nodeFromSimpleGraph.isSkeleton()) {
 131       return scGraph.getCurrentHNode(nodeFromSimpleGraph);
 132     }
 133
 134     Set<HNode> combineSkeletonNodeSet =
 135         infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(nodeFromSimpleGraph);
 136     HNode combinationNodeInSCGraph =
 137         infer.getSkeletonCombinationHierarchyGraph(desc).getMapCombineNodeSetToCombinationNode()
 138             .get(combineSkeletonNodeSet);
 139
 140     // Set<HNode> combineSkeletonNodeSet =
 141     // infer.getSimpleHierarchyGraph(desc).getCombineSetByCombinationNode(simpleGraphNode);
 142     // HNode combinationNodeInSCGraph =
 143     // infer.getSkeletonCombinationHierarchyGraph(desc).getCombinationNode(combineSkeletonNodeSet);
 144     return combinationNodeInSCGraph;
 145   }
 146
 147   public SSJavaLattice<String> insertIntermediateNodesToStraightLine(Descriptor desc,
 148       SSJavaLattice<String> skeletonLattice) {
 149
 150     // perform DFS that starts from each skeleton/combination node and ends by another
 151     // skeleton/combination node
 152
 153     HierarchyGraph simpleGraph = infer.getSimpleHierarchyGraph(desc);
 154     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 155     LocationSummary locSummary = infer.getLocationSummary(desc);
 156
 157     SSJavaLattice<String> lattice = skeletonLattice.clone();
 158
 159     Set<HNode> visited = new HashSet<HNode>();
 160
 161     Set<HNode> nodeSet = simpleGraph.getNodeSet();
 162
 163     Map<TripleItem, String> mapIntermediateLoc = new HashMap<TripleItem, String>();
 164
 165     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 166       HNode node = (HNode) iterator.next();
 167       // System.out.println("node=" + node);
 168       if (node.isSkeleton() && (!visited.contains(node))) {
 169         visited.add(node);
 170
 171         Set<HNode> outSet = simpleGraph.getOutgoingNodeSet(node);
 172         for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 173           HNode outNode = (HNode) iterator2.next();
 174
 175           if (!outNode.isSkeleton()) {
 176             if (outNode.isCombinationNode()) {
 177               // expand the combination node 'outNode'
 178               // here we need to expand the corresponding combination location in the lattice
 179               HNode combinationNodeInSCGraph = getCombinationNodeInSCGraph(desc, outNode);
 180
 181               Set<HNode> combineSkeletonNodeSet =
 182                   simpleGraph.getCombineSetByCombinationNode(outNode);
 183
 184               // System.out.println("combineSkeletonNodeSet=" + combineSkeletonNodeSet);
 185
 186               Set<HNode> combinationNodeSet =
 187                   simpleGraph.getCombinationNodeSetByCombineNodeSet(combineSkeletonNodeSet);
 188
 189               // System.out.println("combinationNodeSet=" + combinationNodeSet);
 190
 191               Set<HNode> endNodeSetFromSimpleGraph =
 192                   simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode,
 193                       combinationNodeSet);
 194               // System.out.println("-endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph);
 195               Set<HNode> endCombNodeSet = new HashSet<HNode>();
 196               for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 197                 HNode endNode = (HNode) iterator3.next();
 198                 endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 199               }
 200               visited.add(outNode);
 201
 202               // follows the straight line up to another skeleton/combination node
 203               if (endCombNodeSet.size() > 0) {
 204                 endCombNodeSet =
 205                     removeTransitivelyReachToNode(desc, combinationNodeInSCGraph, endCombNodeSet);
 206                 recurDFS(desc, lattice, combinationNodeInSCGraph, endCombNodeSet, visited,
 207                     mapIntermediateLoc, 1, locSummary, outNode);
 208               }
 209
 210             } else {
 211               // we have a node that is neither combination or skeleton node
 212               // System.out.println("%%%skeleton node=" + node + "  outNode=" + outNode);
 213               HNode startNode = scGraph.getCurrentHNode(node);
 214
 215               // if (node.getDescriptor() != null) {
 216               // // node is a skeleton node and it might be merged into another node in the SC
 217               // graph.
 218               // startNode = scGraph.getHNode(node.getDescriptor());
 219               // } else {
 220               // // this node has already been merged before the SC graph.
 221               // startNode = node;
 222               // }
 223
 224               Set<HNode> endNodeSetFromSimpleGraph =
 225                   simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(outNode, null);
 226
 227               // System.out.println("endNodeSetFromSimpleGraph=" + endNodeSetFromSimpleGraph
 228               // + "   from=" + outNode);
 229               Set<HNode> endCombNodeSet = new HashSet<HNode>();
 230               for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 231                 HNode endNode = (HNode) iterator3.next();
 232                 endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 233               }
 234               // System.out.println("endCombNodeSet=" + endCombNodeSet);
 235               visited.add(outNode);
 236               if (endCombNodeSet.size() > 0) {
 237                 // follows the straight line up to another skeleton/combination node
 238                 endCombNodeSet = removeTransitivelyReachToNode(desc, startNode, endCombNodeSet);
 239               } else if (endCombNodeSet.size() == 0) {
 240                 // the outNode is (directly/transitively) connected to the bottom node
 241                 // therefore, we just add a dummy bottom HNode to the endCombNodeSet.
 242                 endCombNodeSet.add(bottomNode);
 243               }
 244               recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
 245                   mapIntermediateLoc, 1, locSummary, outNode);
 246             }
 247
 248           }
 249
 250         }
 251       } else if (!node.isSkeleton() && !node.isCombinationNode() && !node.isMergeNode()
 252           && !visited.contains(node)) {
 253
 254         // an intermediate node 'node' may be located between "TOP" location and a skeleton node
 255         int sizeIncomingNode = simpleGraph.getIncomingNodeSet(node).size();
 256
 257         if (sizeIncomingNode == 0) {
 258           // this node will be directly connected to the TOP location
 259           // start adding the following nodes from this node
 260
 261           Set<HNode> endNodeSetFromSimpleGraph =
 262               simpleGraph.getDirectlyReachableSkeletonCombinationNodeFrom(node, null);
 263
 264           Set<HNode> endCombNodeSet = new HashSet<HNode>();
 265           for (Iterator iterator3 = endNodeSetFromSimpleGraph.iterator(); iterator3.hasNext();) {
 266             HNode endNode = (HNode) iterator3.next();
 267             endCombNodeSet.add(getCombinationNodeInSCGraph(desc, endNode));
 268           }
 269
 270           HNode startNode = topNode;
 271           visited.add(startNode);
 272           if (endCombNodeSet.size() > 0) {
 273             // follows the straight line up to another skeleton/combination node
 274             // endCombNodeSet = removeTransitivelyReachToNode(desc, node, endCombNodeSet);
 275             recurDFSNormalNode(desc, lattice, startNode, endCombNodeSet, visited,
 276                 mapIntermediateLoc, 1, locSummary, node);
 277           }
 278
 279         }
 280
 281       }
 282     }
 283
 284     return lattice;
 285
 286   }
 287
 288   private Set<HNode> removeTransitivelyReachToNode(Descriptor desc, HNode startNode,
 289       Set<HNode> endNodeSet) {
 290
 291     // if an end node is not directly connected to the start node in the SC graph
 292     // replace it with a directly connected one which transitively reaches to it.
 293
 294     HierarchyGraph scGraph = infer.getSkeletonCombinationHierarchyGraph(desc);
 295     Set<HNode> newEndNodeSet = new HashSet<HNode>();
 296
 297     for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 298       HNode endNode = (HNode) iterator.next();
 299       if (scGraph.isDirectlyConnectedTo(startNode, endNode)) {
 300         newEndNodeSet.add(endNode);
 301       } else {
 302         HNode newEndNode =
 303             getDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode);
 304         // System.out.println("#### old END NODE=" + endNode + " --->" + newEndNode);
 305         newEndNodeSet.add(newEndNode);
 306       }
 307     }
 308
 309     // System.out.println("removeTransitivelyReachToNode=" + endNodeSet + "  newSet=" +
 310     // newEndNodeSet);
 311
 312     return newEndNodeSet;
 313
 314   }
 315
 316   private HNode getDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 317       HNode startNode, HNode endNode) {
 318     Set<HNode> connected = new HashSet<HNode>();
 319     recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, endNode, connected);
 320     return connected.iterator().next();
 321   }
 322
 323   private void recurDirectlyReachableNodeFromStartNodeReachToEndNode(HierarchyGraph scGraph,
 324       HNode startNode, HNode curNode, Set<HNode> connected) {
 325
 326     Set<HNode> inNodeSet = scGraph.getIncomingNodeSet(curNode);
 327     for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
 328       HNode inNode = (HNode) iterator.next();
 329       if (inNode.equals(startNode)) {
 330         connected.add(curNode);
 331       } else {
 332         // System.out.println("inNode=" + inNode);
 333         recurDirectlyReachableNodeFromStartNodeReachToEndNode(scGraph, startNode, inNode, connected);
 334       }
 335     }
 336
 337   }
 338
 339   private void recurDFSNormalNode(Descriptor desc, SSJavaLattice<String> lattice, HNode startNode,
 340       Set<HNode> endNodeSet, Set<HNode> visited, Map<TripleItem, String> mapIntermediateLoc,
 341       int idx, LocationSummary locSummary, HNode curNode) {
 342
 343     TripleItem item = new TripleItem(startNode, endNodeSet, idx);
 344     // System.out.println("item=" + item);
 345     if (!mapIntermediateLoc.containsKey(item)) {
 346       // need to create a new intermediate location in the lattice
 347       String newLocName = "ILOC" + (seed++);
 348       String above;
 349       if (idx == 1) {
 350         above = startNode.getName();
 351       } else {
 352         int prevIdx = idx - 1;
 353         TripleItem prevItem = new TripleItem(startNode, endNodeSet, prevIdx);
 354         above = mapIntermediateLoc.get(prevItem);
 355       }
 356
 357       Set<String> belowSet = new HashSet<String>();
 358       for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 359         HNode endNode = (HNode) iterator.next();
 360         belowSet.add(endNode.getName());
 361       }
 362
 363       lattice.insertNewLocationBetween(above, belowSet, newLocName);
 364
 365       mapIntermediateLoc.put(item, newLocName);
 366     }
 367
 368     String locName = mapIntermediateLoc.get(item);
 369     HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
 370
 371     Set<Descriptor> descSet = graph.getDescSetOfNode(curNode);
 372     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 373       Descriptor d = (Descriptor) iterator.next();
 374       locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 375     }
 376     // locSummary.addMapHNodeNameToLocationName(curNode.getName(), locName);
 377
 378     Set<HNode> outSet = graph.getOutgoingNodeSet(curNode);
 379     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 380       HNode outNode = (HNode) iterator2.next();
 381       if (!outNode.isSkeleton() && !outNode.isCombinationNode() && !visited.contains(outNode)) {
 382         visited.add(outNode);
 383         recurDFSNormalNode(desc, lattice, startNode, endNodeSet, visited, mapIntermediateLoc,
 384             idx + 1, locSummary, outNode);
 385       }
 386     }
 387
 388   }
 389
 390   private void recurDFS(Descriptor desc, SSJavaLattice<String> lattice,
 391       HNode combinationNodeInSCGraph, Set<HNode> endNodeSet, Set<HNode> visited,
 392       Map<TripleItem, String> mapIntermediateLoc, int idx, LocationSummary locSummary, HNode curNode) {
 393
 394     TripleItem item = new TripleItem(combinationNodeInSCGraph, endNodeSet, idx);
 395
 396     if (!mapIntermediateLoc.containsKey(item)) {
 397       // need to create a new intermediate location in the lattice
 398       String above;
 399       if (idx == 1) {
 400         String newLocName = combinationNodeInSCGraph.getName();
 401         mapIntermediateLoc.put(item, newLocName);
 402       } else {
 403         String newLocName = "ILOC" + (seed++);
 404         int prevIdx = idx - 1;
 405         TripleItem prevItem = new TripleItem(combinationNodeInSCGraph, endNodeSet, prevIdx);
 406         above = mapIntermediateLoc.get(prevItem);
 407
 408         Set<String> belowSet = new HashSet<String>();
 409         for (Iterator iterator = endNodeSet.iterator(); iterator.hasNext();) {
 410           HNode endNode = (HNode) iterator.next();
 411           belowSet.add(endNode.getName());
 412         }
 413         lattice.insertNewLocationBetween(above, belowSet, newLocName);
 414         mapIntermediateLoc.put(item, newLocName);
 415
 416       }
 417
 418     }
 419
 420     HierarchyGraph graph = infer.getSimpleHierarchyGraph(desc);
 421     String locName = mapIntermediateLoc.get(item);
 422     Set<Descriptor> descSet = graph.getDescSetOfNode(curNode);
 423     for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 424       Descriptor d = (Descriptor) iterator.next();
 425       locSummary.addMapHNodeNameToLocationName(d.getSymbol(), locName);
 426     }
 427
 428     // System.out.println("-TripleItem=" + item);
 429     // System.out.println("-curNode=" + curNode.getName() + " locName=" + locName);
 430
 431     Set<HNode> outSet = graph.getOutgoingNodeSet(curNode);
 432     for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 433       HNode outNode = (HNode) iterator2.next();
 434       if (!outNode.isSkeleton() && !visited.contains(outNode)) {
 435         if (combinationNodeInSCGraph.equals(getCombinationNodeInSCGraph(desc, outNode))) {
 436           visited.add(outNode);
 437           recurDFS(desc, lattice, combinationNodeInSCGraph, endNodeSet, visited,
 438               mapIntermediateLoc, idx + 1, locSummary, outNode);
 439         }
 440       }
 441     }
 442
 443   }
 444
 445   private String generateElementName(BasisSet basisSet, HierarchyGraph inputGraph,
 446       Map<Set<Integer>, String> mapF2LocName, Set<Integer> F) {
 447
 448     if (mapF2LocName.containsKey(F)) {
 449       return mapF2LocName.get(F);
 450     }
 451
 452     HNode node = basisSet.getHNode(F);
 453     if (node != null) {
 454       mapF2LocName.put(F, node.getName());
 455       return node.getName();
 456     } else {
 457       if (inputGraph.BASISTOPELEMENT.equals(F)) {
 458         return SSJavaAnalysis.BOTTOM;
 459       } else {
 460         String str = "LOC" + (seed++);
 461         mapF2LocName.put(F, str);
 462         return str;
 463       }
 464     }
 465   }
 466
 467   private void resetCount(Map<Set<Integer>, Integer> mapFtoCount, Family family) {
 468     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
 469       Set<Integer> F = iter.next();
 470       mapFtoCount.put(F, 0);
 471     }
 472   }
 473
 474   private Map<Set<Integer>, Set<Set<Integer>>> coveringGraph(BasisSet basisSet, Family family) {
 475
 476     Map<Set<Integer>, Integer> mapFtoCount = new HashMap<Set<Integer>, Integer>();
 477     Map<Set<Integer>, Set<Set<Integer>>> mapImSucc = new HashMap<Set<Integer>, Set<Set<Integer>>>();
 478
 479     // initialize COUNT(F) to 0 for all elements of the family
 480     resetCount(mapFtoCount, family);
 481
 482     for (Iterator<Set<Integer>> iter = family.FIterator(); iter.hasNext();) {
 483       Set<Integer> F = iter.next();
 484       Set<HNode> gammaF = family.getGamma(F);
 485
 486       Set<HNode> curHNodeSet = basisSet.getHNodeSet();
 487       curHNodeSet.removeAll(gammaF);
 488       Set<Set<Integer>> Bset = basisSet.getBasisSetByHNodeSet(curHNodeSet);
 489
 490       for (Iterator iterator = Bset.iterator(); iterator.hasNext();) {
 491         Set<Integer> B = (Set<Integer>) iterator.next();
 492
 493         Set<Integer> Fprime = new HashSet<Integer>();
 494         Fprime.addAll(F);
 495         Fprime.addAll(B);
 496
 497         // COUNT(F')++;
 498         mapFtoCount.put(Fprime, mapFtoCount.get(Fprime) + 1);
 499
 500         // if |gamma(F')|==COUNT(F') + |gamma(F)|
 501         int numGammaFprime = family.getGamma(Fprime).size();
 502         int countFprime = mapFtoCount.get(Fprime);
 503         int numGammaF = family.getGamma(F).size();
 504         if (numGammaFprime == (countFprime + numGammaF)) {
 505           // ImSucc(F)=IMSucc(F) union F'
 506           addImSucc(mapImSucc, F, Fprime);
 507         }
 508
 509       }
 510       resetCount(mapFtoCount, family);
 511     }
 512
 513     // System.out.println("mapImSucc=" + mapImSucc);
 514
 515     return mapImSucc;
 516   }
 517
 518   private Set<Set<Integer>> getImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F) {
 519     if (!mapImSucc.containsKey(F)) {
 520       mapImSucc.put(F, new HashSet<Set<Integer>>());
 521     }
 522     return mapImSucc.get(F);
 523   }
 524
 525   private void addImSucc(Map<Set<Integer>, Set<Set<Integer>>> mapImSucc, Set<Integer> F,
 526       Set<Integer> Fprime) {
 527
 528     if (!mapImSucc.containsKey(F)) {
 529       mapImSucc.put(F, new HashSet<Set<Integer>>());
 530     }
 531
 532     mapImSucc.get(F).add(Fprime);
 533
 534   }
 535
 536   private Family generateFamily(BasisSet basisSet) {
 537
 538     Family family = new Family();
 539
 540     for (Iterator<Set<Integer>> iterator = basisSet.basisIterator(); iterator.hasNext();) {
 541       Set<Integer> B = iterator.next();
 542
 543       Set<Pair<Set<Integer>, Set<HNode>>> tobeadded = new HashSet<Pair<Set<Integer>, Set<HNode>>>();
 544
 545       for (Iterator<Set<Integer>> iterator2 = family.FIterator(); iterator2.hasNext();) {
 546         Set<Integer> F = iterator2.next();
 547
 548         Set<Integer> Fprime = new HashSet<Integer>();
 549         Fprime.addAll(F);
 550         Fprime.addAll(B);
 551
 552         Set<HNode> gammaFPrimeSet = new HashSet<HNode>();
 553         gammaFPrimeSet.addAll(family.getGamma(F));
 554         gammaFPrimeSet.add(basisSet.getHNode(B));
 555
 556         if (!family.containsF(Fprime)) {
 557           Pair<Set<Integer>, Set<HNode>> pair =
 558               new Pair<Set<Integer>, Set<HNode>>(Fprime, gammaFPrimeSet);
 559           tobeadded.add(pair);
 560         } else {
 561           family.updateGammaF(Fprime, gammaFPrimeSet);
 562         }
 563       }
 564
 565       for (Iterator<Pair<Set<Integer>, Set<HNode>>> iterator2 = tobeadded.iterator(); iterator2
 566           .hasNext();) {
 567         Pair<Set<Integer>, Set<HNode>> pair = iterator2.next();
 568         family.addFElement(pair.getFirst());
 569         family.updateGammaF(pair.getFirst(), pair.getSecond());
 570       }
 571
 572     }
 573     return family;
 574   }
 575
 576   private void debug_print(HierarchyGraph inputGraph) {
 577     System.out.println("\nBuild Lattice:" + inputGraph.getName());
 578     // System.out.println("Node2Index:\n" + inputGraph.getMapHNodeToUniqueIndex());
 579     // System.out.println("Node2Basis:\n" + inputGraph.getMapHNodeToBasis());
 580   }
 581
 582 }
 583
 584 class Identifier {
 585   public HNode node;
 586   public int idx;
 587
 588   public Identifier(HNode n, int i) {
 589     node = n;
 590     idx = i;
 591   }
 592
 593   public int hashCode() {
 594     return node.hashCode() + idx;
 595   }
 596
 597   public boolean equals(Object obj) {
 598
 599     if (obj instanceof Identifier) {
 600       Identifier in = (Identifier) obj;
 601       if (node.equals(in.node) && idx == in.idx) {
 602         return true;
 603       }
 604     }
 605
 606     return false;
 607   }
 608
 609 }
 610
 611 class TripleItem {
 612   public HNode higherNode;
 613   public Set<HNode> lowerNodeSet;
 614   public int idx;
 615
 616   public TripleItem(HNode h, Set<HNode> l, int i) {
 617     higherNode = h;
 618     lowerNodeSet = l;
 619     idx = i;
 620   }
 621
 622   public int hashCode() {
 623
 624     int h = 0;
 625     if (higherNode != null) {
 626       h = higherNode.hashCode();
 627     }
 628
 629     return h + lowerNodeSet.hashCode() + idx;
 630   }
 631
 632   public boolean equals(Object obj) {
 633
 634     if (obj instanceof TripleItem) {
 635       TripleItem in = (TripleItem) obj;
 636       if ((higherNode == null || (higherNode != null && higherNode.equals(in.higherNode)))
 637           && lowerNodeSet.equals(in.lowerNodeSet) && idx == in.idx) {
 638         return true;
 639       }
 640     }
 641
 642     return false;
 643   }
 644
 645   public String toString() {
 646     return higherNode + "-" + idx + "->" + lowerNodeSet;
 647   }
 648 }