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