Robust/src/Analysis/SSJava/HierarchyGraph.java

   1 package Analysis.SSJava;
   2
   3 import java.io.BufferedWriter;
   4 import java.io.FileWriter;
   5 import java.io.IOException;
   6 import java.util.HashMap;
   7 import java.util.HashSet;
   8 import java.util.Iterator;
   9 import java.util.Map;
  10 import java.util.Set;
  11
  12 import IR.Descriptor;
  13 import IR.FieldDescriptor;
  14
  15 public class HierarchyGraph {
  16
  17   Descriptor desc;
  18
  19   String name;
  20
  21   // graph structure
  22   Map<HNode, Set<HNode>> mapHNodeToIncomingSet;
  23   Map<HNode, Set<HNode>> mapHNodeToOutgoingSet;
  24
  25   Map<Descriptor, HNode> mapDescToHNode;
  26   Map<HNode, Set<Descriptor>> mapHNodeToDescSet;
  27   Map<HNode, HNode> mapHNodeToCurrentHNode; // tracking which node corresponds to the initial node
  28   Map<HNode, Set<HNode>> mapMergeNodetoMergingSet;
  29
  30   // data structures for a combination node
  31   Map<Set<HNode>, HNode> mapSkeletonNodeSetToCombinationNode;
  32   Map<HNode, Set<HNode>> mapCombinationNodeToCombineNodeSet;
  33   Map<Set<HNode>, HNode> mapCombineNodeSetToCombinationNode;
  34   Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToOutgoingNodeSet;
  35
  36   Map<HNode, String> mapHNodeToLocationName;
  37
  38   Set<HNode> nodeSet;
  39
  40   public static int seed = 0;
  41
  42   // for the lattice generation
  43   Map<HNode, Integer> mapHNodeToUniqueIndex;
  44   Map<HNode, Set<Integer>> mapHNodeToBasis;
  45   Set<Integer> BASISTOPELEMENT;
  46
  47   public HierarchyGraph() {
  48     mapHNodeToIncomingSet = new HashMap<HNode, Set<HNode>>();
  49     mapHNodeToOutgoingSet = new HashMap<HNode, Set<HNode>>();
  50     mapHNodeToDescSet = new HashMap<HNode, Set<Descriptor>>();
  51     mapDescToHNode = new HashMap<Descriptor, HNode>();
  52     mapSkeletonNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
  53     mapCombinationNodeToCombineNodeSet = new HashMap<HNode, Set<HNode>>();
  54     mapCombineNodeSetToOutgoingNodeSet = new HashMap<Set<HNode>, Set<HNode>>();
  55     mapCombineNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
  56     nodeSet = new HashSet<HNode>();
  57
  58     mapHNodeToUniqueIndex = new HashMap<HNode, Integer>();
  59     mapHNodeToBasis = new HashMap<HNode, Set<Integer>>();
  60
  61     mapHNodeToLocationName = new HashMap<HNode, String>();
  62     mapMergeNodetoMergingSet = new HashMap<HNode, Set<HNode>>();
  63
  64     mapHNodeToCurrentHNode = new HashMap<HNode, HNode>();
  65
  66   }
  67
  68   public Descriptor getDesc() {
  69     return desc;
  70   }
  71
  72   public void setDesc(Descriptor desc) {
  73     this.desc = desc;
  74   }
  75
  76   public void addMapHNodeToLocationName(HNode node, String locName) {
  77     mapHNodeToLocationName.put(node, locName);
  78   }
  79
  80   public String getLocationName(HNode node) {
  81     return mapHNodeToLocationName.get(node);
  82   }
  83
  84   public String getName() {
  85     return name;
  86   }
  87
  88   public void setName(String name) {
  89     this.name = name;
  90   }
  91
  92   public HierarchyGraph(Descriptor d) {
  93     this();
  94     desc = d;
  95     name = d.toString();
  96   }
  97
  98   public Map<HNode, Set<Descriptor>> getMapHNodeToDescSet() {
  99     return mapHNodeToDescSet;
 100   }
 101
 102   public void setMapHNodeToDescSet(Map<HNode, Set<Descriptor>> map) {
 103     mapHNodeToDescSet.putAll(map);
 104   }
 105
 106   public Map<HNode, HNode> getMapHNodeToCurrentHNode() {
 107     return mapHNodeToCurrentHNode;
 108   }
 109
 110   public void setMapHNodeToCurrentHNode(Map<HNode, HNode> mapHNodeToCurrentHNode) {
 111     this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode;
 112   }
 113
 114   public Map<Descriptor, HNode> getMapDescToHNode() {
 115     return mapDescToHNode;
 116   }
 117
 118   public void setMapDescToHNode(Map<Descriptor, HNode> map) {
 119     mapDescToHNode.putAll(map);
 120   }
 121
 122   public Set<HNode> getNodeSet() {
 123     return nodeSet;
 124   }
 125
 126   public void addEdge(HNode srcHNode, HNode dstHNode) {
 127
 128     if (!nodeSet.contains(srcHNode)) {
 129       nodeSet.add(srcHNode);
 130     }
 131
 132     if (!nodeSet.contains(dstHNode)) {
 133       nodeSet.add(dstHNode);
 134     }
 135
 136     Set<HNode> possibleCycleSet = getPossibleCycleNodes(srcHNode, dstHNode);
 137
 138     if (possibleCycleSet.size() > 0) {
 139
 140       if (possibleCycleSet.size() == 1) {
 141         if (dstHNode.isSharedNode()) {
 142           // it has already been assigned shared node.
 143         } else {
 144           dstHNode.setSharedNode(true);
 145         }
 146         return;
 147       }
 148
 149       HNode newMergeNode = mergeNodes(possibleCycleSet, false);
 150       newMergeNode.setSharedNode(true);
 151       System.out.println("### INTRODUCE A NEW MERGE NODE: " + newMergeNode);
 152       System.out.println("### CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
 153     } else {
 154       getIncomingNodeSet(dstHNode).add(srcHNode);
 155       getOutgoingNodeSet(srcHNode).add(dstHNode);
 156       System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
 157     }
 158
 159   }
 160
 161   public void addNode(HNode node) {
 162     nodeSet.add(node);
 163   }
 164
 165   public void addEdge(Descriptor src, Descriptor dst) {
 166     HNode srcHNode = getHNode(src);
 167     HNode dstHNode = getHNode(dst);
 168
 169     addEdge(srcHNode, dstHNode);
 170
 171   }
 172
 173   public void setParamHNode(Descriptor d) {
 174     getHNode(d).setSkeleton(true);
 175   }
 176
 177   public HNode getHNode(Descriptor d) {
 178     if (!mapDescToHNode.containsKey(d)) {
 179       HNode newNode = new HNode(d);
 180       if (d instanceof FieldDescriptor) {
 181         newNode.setSkeleton(true);
 182       }
 183       mappingDescriptorToHNode(d, newNode);
 184       nodeSet.add(newNode);
 185     }
 186     return mapDescToHNode.get(d);
 187   }
 188
 189   public HNode getHNode(String name) {
 190     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 191       HNode node = (HNode) iterator.next();
 192       if (node.getName().equals(name)) {
 193         return node;
 194       }
 195     }
 196     return null;
 197   }
 198
 199   private void mappingDescriptorToHNode(Descriptor desc, HNode node) {
 200     mapDescToHNode.put(desc, node);
 201     if (!mapHNodeToDescSet.containsKey(node)) {
 202       mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
 203     }
 204     mapHNodeToDescSet.get(node).add(desc);
 205   }
 206
 207   public HierarchyGraph generateSkeletonGraph() {
 208
 209     // compose a skeleton graph that only consists of fields or parameters
 210     HierarchyGraph skeletonGraph = new HierarchyGraph(desc);
 211     skeletonGraph.setName(desc + "_SKELETON");
 212
 213     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 214       HNode src = (HNode) iterator.next();
 215       if (src.isSkeleton()) {
 216         Set<HNode> reachSet = getDirectlyReachSkeletonSet(src);
 217         if (reachSet.size() > 0) {
 218           for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
 219             HNode dst = (HNode) iterator2.next();
 220             skeletonGraph.addEdge(src, dst);
 221           }
 222         } else {
 223           skeletonGraph.addNode(src);
 224         }
 225       }
 226     }
 227
 228     skeletonGraph.setMapDescToHNode(getMapDescToHNode());
 229     skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet());
 230     skeletonGraph.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
 231     skeletonGraph.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
 232
 233     return skeletonGraph;
 234
 235   }
 236
 237   private Set<HNode> getDirectlyReachSkeletonSet(HNode node) {
 238
 239     Set<HNode> visited = new HashSet<HNode>();
 240     Set<HNode> connected = new HashSet<HNode>();
 241     recurReachSkeletonSet(node, connected, visited);
 242
 243     return connected;
 244   }
 245
 246   public void removeRedundantEdges() {
 247
 248     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 249       HNode src = (HNode) iterator.next();
 250       Set<HNode> connectedSet = getOutgoingNodeSet(src);
 251       Set<HNode> toberemovedSet = new HashSet<HNode>();
 252       for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
 253         HNode dst = (HNode) iterator2.next();
 254         Set<HNode> otherNeighborSet = new HashSet<HNode>();
 255         otherNeighborSet.addAll(connectedSet);
 256         otherNeighborSet.remove(dst);
 257         for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
 258           HNode neighbor = (HNode) iterator3.next();
 259           if (reachTo(neighbor, dst, new HashSet<HNode>())) {
 260             toberemovedSet.add(dst);
 261           }
 262         }
 263       }
 264       if (toberemovedSet.size() > 0) {
 265         connectedSet.removeAll(toberemovedSet);
 266
 267         for (Iterator iterator2 = toberemovedSet.iterator(); iterator2.hasNext();) {
 268           HNode node = (HNode) iterator2.next();
 269           getIncomingNodeSet(node).remove(src);
 270         }
 271
 272       }
 273     }
 274
 275   }
 276
 277   public void simplifyHierarchyGraph() {
 278     removeRedundantEdges();
 279     combineRedundantNodes(false);
 280   }
 281
 282   public void simplifySkeletonCombinationHierarchyGraph() {
 283     removeRedundantEdges();
 284     combineRedundantNodes(true);
 285   }
 286
 287   public void combineRedundantNodes(boolean onlyCombinationNodes) {
 288     // Combine field/parameter nodes who have the same set of incoming/outgoing edges.
 289     boolean isUpdated = false;
 290     do {
 291       isUpdated = combineTwoRedundatnNodes(onlyCombinationNodes);
 292     } while (isUpdated);
 293   }
 294
 295   public Set<HNode> getIncomingNodeSet(HNode node) {
 296     if (!mapHNodeToIncomingSet.containsKey(node)) {
 297       mapHNodeToIncomingSet.put(node, new HashSet<HNode>());
 298     }
 299     return mapHNodeToIncomingSet.get(node);
 300   }
 301
 302   public Set<HNode> getOutgoingNodeSet(HNode node) {
 303     if (!mapHNodeToOutgoingSet.containsKey(node)) {
 304       mapHNodeToOutgoingSet.put(node, new HashSet<HNode>());
 305     }
 306     return mapHNodeToOutgoingSet.get(node);
 307   }
 308
 309   private boolean combineTwoRedundatnNodes(boolean onlyCombinationNodes) {
 310     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 311       HNode node1 = (HNode) iterator.next();
 312
 313       if ((onlyCombinationNodes && (!node1.isCombinationNode()))
 314           || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
 315         continue;
 316       }
 317
 318       Set<HNode> incomingNodeSet1 = getIncomingNodeSet(node1);
 319       Set<HNode> outgoingNodeSet1 = getOutgoingNodeSet(node1);
 320
 321       for (Iterator iterator2 = nodeSet.iterator(); iterator2.hasNext();) {
 322         HNode node2 = (HNode) iterator2.next();
 323
 324         if ((onlyCombinationNodes && (!node2.isCombinationNode()))
 325             || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
 326           continue;
 327         }
 328
 329         if (!node1.equals(node2)) {
 330
 331           Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
 332           Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
 333
 334           if (incomingNodeSet1.equals(incomingNodeSet2)
 335               && outgoingNodeSet1.equals(outgoingNodeSet2)) {
 336             // need to merge node1 and node2
 337
 338             Set<HNode> mergeSet = new HashSet<HNode>();
 339             mergeSet.add(node1);
 340             mergeSet.add(node2);
 341             mergeNodes(mergeSet, onlyCombinationNodes);
 342             return true;
 343           }
 344
 345         }
 346       }
 347
 348     }
 349     return false;
 350   }
 351
 352   private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
 353     getIncomingNodeSet(dstHNode).add(srcHNode);
 354     getOutgoingNodeSet(srcHNode).add(dstHNode);
 355     System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
 356   }
 357
 358   private HNode mergeNodes(Set<HNode> set, boolean onlyCombinationNodes) {
 359
 360     Set<HNode> incomingNodeSet = new HashSet<HNode>();
 361     Set<HNode> outgoingNodeSet = new HashSet<HNode>();
 362
 363     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 364       HNode node = (HNode) iterator.next();
 365       incomingNodeSet.addAll(getIncomingNodeSet(node));
 366       outgoingNodeSet.addAll(getOutgoingNodeSet(node));
 367     }
 368
 369     String nodeName;
 370     boolean isMergeNode = false;
 371     if (onlyCombinationNodes) {
 372       nodeName = "Comb" + (seed++);
 373     } else {
 374       nodeName = "Node" + (seed++);
 375       isMergeNode = true;
 376     }
 377     HNode newMergeNode = new HNode(nodeName);
 378     newMergeNode.setMergeNode(isMergeNode);
 379
 380     nodeSet.add(newMergeNode);
 381     nodeSet.removeAll(set);
 382
 383     // if the input set contains a skeleton node, need to set a new merge node as skeleton also
 384     boolean hasSkeleton = false;
 385     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 386       HNode inNode = (HNode) iterator.next();
 387       if (inNode.isSkeleton()) {
 388         hasSkeleton = true;
 389         break;
 390       }
 391     }
 392     System.out.println("--Set merging node=" + newMergeNode + " as a skeleton=" + set
 393         + " hasSkeleton=" + hasSkeleton);
 394     newMergeNode.setSkeleton(hasSkeleton);
 395
 396     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 397       HNode node = (HNode) iterator.next();
 398       Set<Descriptor> descSetOfNode = getDescSetOfNode(node);
 399       for (Iterator iterator2 = descSetOfNode.iterator(); iterator2.hasNext();) {
 400         Descriptor desc = (Descriptor) iterator2.next();
 401         mappingDescriptorToHNode(desc, newMergeNode);
 402       }
 403     }
 404
 405     for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
 406       HNode inNode = (HNode) iterator.next();
 407       Set<HNode> outSet = getOutgoingNodeSet(inNode);
 408       outSet.removeAll(set);
 409       if (!set.contains(inNode)) {
 410         addEdgeWithNoCycleCheck(inNode, newMergeNode);
 411       }
 412     }
 413
 414     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
 415       HNode outNode = (HNode) iterator.next();
 416       Set<HNode> inSet = getIncomingNodeSet(outNode);
 417       inSet.removeAll(set);
 418       if (!set.contains(outNode)) {
 419         addEdgeWithNoCycleCheck(newMergeNode, outNode);
 420       }
 421     }
 422
 423     Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
 424     for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
 425       HNode merged = iter.next();
 426       if (merged.isSkeleton()) {
 427         mergedSkeletonNode.add(merged);
 428       }
 429     }
 430     mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
 431     for (Iterator iterator = mergedSkeletonNode.iterator(); iterator.hasNext();) {
 432       HNode mergedNode = (HNode) iterator.next();
 433       addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
 434     }
 435
 436     System.out.println("###MERGING NODE=" + set + " new node=" + newMergeNode);
 437     return newMergeNode;
 438   }
 439
 440   private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
 441     if (curNode.isMergeNode()) {
 442       Set<HNode> mergingSet = getMergingSet(curNode);
 443       for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
 444         HNode mergingNode = (HNode) iterator.next();
 445         mapHNodeToCurrentHNode.put(mergingNode, newNode);
 446       }
 447     } else {
 448       mapHNodeToCurrentHNode.put(curNode, newNode);
 449     }
 450   }
 451
 452   public HNode getCurrentHNode(HNode node) {
 453     if (!mapHNodeToCurrentHNode.containsKey(node)) {
 454       mapHNodeToCurrentHNode.put(node, node);
 455     }
 456     return mapHNodeToCurrentHNode.get(node);
 457   }
 458
 459   private Set<HNode> getMergingSet(HNode mergeNode) {
 460     Set<HNode> mergingSet = new HashSet<HNode>();
 461     Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
 462     for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
 463       HNode node = (HNode) iterator.next();
 464       if (node.isMergeNode()) {
 465         mergingSet.addAll(getMergingSet(node));
 466       } else {
 467         mergingSet.add(node);
 468       }
 469     }
 470     return mergingSet;
 471   }
 472
 473   private Set<Descriptor> getDescSetOfNode(HNode node) {
 474     if (!mapHNodeToDescSet.containsKey(node)) {
 475       mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
 476     }
 477     return mapHNodeToDescSet.get(node);
 478   }
 479
 480   private boolean reachTo(HNode src, HNode dst, Set<HNode> visited) {
 481     Set<HNode> connectedSet = getOutgoingNodeSet(src);
 482     for (Iterator<HNode> iterator = connectedSet.iterator(); iterator.hasNext();) {
 483       HNode n = iterator.next();
 484       if (n.equals(dst)) {
 485         return true;
 486       }
 487       if (!visited.contains(n)) {
 488         visited.add(n);
 489         if (reachTo(n, dst, visited)) {
 490           return true;
 491         }
 492       }
 493     }
 494     return false;
 495   }
 496
 497   private void recurReachSkeletonSet(HNode node, Set<HNode> connected, Set<HNode> visited) {
 498
 499     Set<HNode> outSet = getOutgoingNodeSet(node);
 500     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 501       HNode outNode = (HNode) iterator.next();
 502
 503       if (outNode.isSkeleton()) {
 504         connected.add(outNode);
 505       } else if (!visited.contains(outNode)) {
 506         visited.add(outNode);
 507         recurReachSkeletonSet(outNode, connected, visited);
 508       }
 509     }
 510
 511   }
 512
 513   public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
 514       Set<HNode> combinationNodeSet) {
 515     Set<HNode> reachable = new HashSet<HNode>();
 516     Set<HNode> visited = new HashSet<HNode>();
 517     visited.add(node);
 518     recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
 519     return reachable;
 520   }
 521
 522   public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
 523       Set<HNode> reachable, Set<HNode> combinationNodeSet) {
 524
 525     Set<HNode> outSet = getOutgoingNodeSet(node);
 526     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 527       HNode out = (HNode) iterator.next();
 528
 529       if (!visited.contains(out)) {
 530         visited.add(out);
 531         if (out.isSkeleton()) {
 532           reachable.add(out);
 533         } else if (out.isCombinationNode()) {
 534           if (combinationNodeSet == null) {
 535             reachable.add(out);
 536           } else if (!combinationNodeSet.contains(out)) {
 537             reachable.add(out);
 538           } else {
 539             recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
 540                 combinationNodeSet);
 541           }
 542         } else {
 543           recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
 544               combinationNodeSet);
 545         }
 546
 547       }
 548
 549     }
 550
 551   }
 552
 553   public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
 554     Set<HNode> visited = new HashSet<HNode>();
 555     return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
 556   }
 557
 558   public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
 559
 560     Set<HNode> outSet = getOutgoingNodeSet(node);
 561     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 562       HNode out = (HNode) iterator.next();
 563       // if (!visited.contains(out)) {
 564       if (out.isCombinationNode() || out.isSkeleton()) {
 565         return out;
 566       } else {
 567         // visited.add(out);
 568         return getDirectlyReachableSkeletonCombinationNodeFrom(out);
 569       }
 570     }
 571     // }
 572
 573     return null;
 574   }
 575
 576   public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
 577     // if an edge from src to dst introduces a new cycle flow,
 578     // the method returns the set of elements consisting of the cycle
 579     Set<HNode> cycleNodeSet = new HashSet<HNode>();
 580     // if the dst node reaches to the src node, the new relation
 581     // introduces a cycle to the lattice
 582     if (dst.equals(src)) {
 583       cycleNodeSet.add(dst);
 584       cycleNodeSet.add(src);
 585     } else if (reachTo(dst, src)) {
 586       cycleNodeSet.add(dst);
 587       cycleNodeSet.add(src);
 588       getInBetweenElements(dst, src, cycleNodeSet);
 589     }
 590     return cycleNodeSet;
 591   }
 592
 593   private void getInBetweenElements(HNode start, HNode end, Set<HNode> nodeSet) {
 594     Set<HNode> connectedSet = getOutgoingNodeSet(start);
 595     for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
 596       HNode cur = (HNode) iterator.next();
 597       if ((!start.equals(cur)) && (!cur.equals(end)) && reachTo(cur, end)) {
 598         nodeSet.add(cur);
 599         getInBetweenElements(cur, end, nodeSet);
 600       }
 601     }
 602   }
 603
 604   public boolean reachTo(HNode node1, HNode node2) {
 605     return reachTo(node1, node2, new HashSet<HNode>());
 606   }
 607
 608   public Set<HNode> getCombineSetByCombinationNode(HNode node) {
 609     if (!mapCombinationNodeToCombineNodeSet.containsKey(node)) {
 610       mapCombinationNodeToCombineNodeSet.put(node, new HashSet<HNode>());
 611     }
 612     return mapCombinationNodeToCombineNodeSet.get(node);
 613   }
 614
 615   public HNode getCombinationNode(Set<HNode> combineSet) {
 616     if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
 617       String name = "COMB" + (seed++);
 618       HNode node = new HNode(name);
 619       node.setCombinationNode(true);
 620       nodeSet.add(node);
 621       mapCombineNodeSetToCombinationNode.put(combineSet, node);
 622       mapCombinationNodeToCombineNodeSet.put(node, combineSet);
 623     }
 624
 625     return mapCombineNodeSetToCombinationNode.get(combineSet);
 626   }
 627
 628   public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
 629     return mapCombineNodeSetToCombinationNode;
 630   }
 631
 632   public Set<Set<HNode>> getCombineNodeSet() {
 633     return mapCombineNodeSetToOutgoingNodeSet.keySet();
 634   }
 635
 636   public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
 637     // add a new combination node where parameter/field flows are actually combined.
 638
 639     simpleHierarchyGraph.identifyCombinationNodes();
 640
 641     Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
 642     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 643       Set<HNode> combineSet = (Set<HNode>) iterator.next();
 644       System.out.println("--combineSet=" + combineSet);
 645       HNode combinationNode = getCombinationNode(combineSet);
 646       System.out.println("--combinationNode=" + combinationNode);
 647       // add an edge from a skeleton node to a combination node
 648       for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
 649         HNode inSkeletonNode = (HNode) iterator2.next();
 650         // System.out.println("--inSkeletonNode=" + inSkeletonNode + "  desc="
 651         // + inSkeletonNode.getDescriptor());
 652         HNode srcNode;
 653         if (inSkeletonNode.getDescriptor() == null) {
 654           // the node is merging one...
 655           srcNode = inSkeletonNode;
 656         } else {
 657           srcNode = getHNode(inSkeletonNode.getDescriptor());
 658         }
 659         // System.out.println("--srcNode=" + srcNode);
 660         addEdgeWithNoCycleCheck(srcNode, combinationNode);
 661       }
 662
 663       // add an edge from the combination node to outgoing nodes
 664       Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
 665       for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 666         HNode curNode = (HNode) iterator2.next();
 667         if (curNode.isCombinationNode()) {
 668           Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
 669           HNode outNode = getCombinationNode(combineNode);
 670           addEdgeWithNoCycleCheck(combinationNode, outNode);
 671         } else if (curNode.isSkeleton()) {
 672           // HNode dstNode = getHNode(curNode.getDescriptor());
 673           HNode dstNode = getCurrentHNode(curNode);
 674           addEdgeWithNoCycleCheck(combinationNode, dstNode);
 675         }
 676       }
 677
 678       System.out.println("--");
 679
 680     }
 681
 682   }
 683
 684   private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
 685     if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
 686       // need to create a new combination node
 687       String nodeName = "Comb" + (seed++);
 688       HNode newCombinationNode = new HNode(nodeName);
 689       newCombinationNode.setCombinationNode(true);
 690
 691       nodeSet.add(newCombinationNode);
 692       mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
 693
 694       for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 695         HNode reachToNode = (HNode) iterator.next();
 696         addEdge(reachToNode, newCombinationNode);
 697       }
 698
 699     }
 700
 701     HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
 702     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
 703       HNode reachableNode = (HNode) iterator.next();
 704       addEdge(combinationNode, reachableNode);
 705     }
 706
 707   }
 708
 709   private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
 710
 711     Set<HNode> reachToSet = new HashSet<HNode>();
 712     Set<HNode> visited = new HashSet<HNode>();
 713     recurSkeletonReachTo(node, reachToSet, visited);
 714
 715     // if a node reaches to one of elements in the reachToSet, we do not need to keep it
 716     // because the node is not directly connected to the combination node
 717
 718     removeRedundantReachToNodes(reachToSet);
 719
 720     return reachToSet;
 721   }
 722
 723   private void removeRedundantReachToNodes(Set<HNode> reachToSet) {
 724
 725     Set<HNode> toberemoved = new HashSet<HNode>();
 726     for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 727       HNode cur = (HNode) iterator.next();
 728
 729       for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
 730         HNode dst = (HNode) iterator2.next();
 731         if (!cur.equals(dst) && reachTo(cur, dst)) {
 732           // it is redundant
 733           toberemoved.add(cur);
 734         }
 735       }
 736     }
 737     reachToSet.removeAll(toberemoved);
 738   }
 739
 740   private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
 741
 742     Set<HNode> inSet = getIncomingNodeSet(node);
 743     for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
 744       HNode inNode = (HNode) iterator.next();
 745
 746       if (inNode.isSkeleton()) {
 747         reachToSet.add(inNode);
 748       } else if (!visited.contains(inNode)) {
 749         visited.add(inNode);
 750         recurSkeletonReachTo(inNode, reachToSet, visited);
 751       }
 752     }
 753
 754   }
 755
 756   public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
 757     return mapHNodeToOutgoingSet;
 758   }
 759
 760   public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
 761     return mapHNodeToIncomingSet;
 762   }
 763
 764   public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
 765     mapHNodeToOutgoingSet.clear();
 766     Set<HNode> keySet = in.keySet();
 767     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 768       HNode key = (HNode) iterator.next();
 769       Set<HNode> inSet = in.get(key);
 770       Set<HNode> newSet = new HashSet<HNode>();
 771       newSet.addAll(inSet);
 772       mapHNodeToOutgoingSet.put(key, newSet);
 773     }
 774   }
 775
 776   public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
 777     mapHNodeToIncomingSet.clear();
 778     Set<HNode> keySet = in.keySet();
 779     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 780       HNode key = (HNode) iterator.next();
 781       Set<HNode> inSet = in.get(key);
 782       Set<HNode> newSet = new HashSet<HNode>();
 783       newSet.addAll(inSet);
 784       mapHNodeToIncomingSet.put(key, newSet);
 785     }
 786   }
 787
 788   public void setNodeSet(Set<HNode> inSet) {
 789     nodeSet.clear();
 790     nodeSet.addAll(inSet);
 791   }
 792
 793   public HierarchyGraph clone() {
 794     HierarchyGraph clone = new HierarchyGraph();
 795     clone.setDesc(getDesc());
 796     clone.setName(getName());
 797     clone.setNodeSet(getNodeSet());
 798     clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
 799     clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
 800     clone.setMapDescToHNode(getMapDescToHNode());
 801     clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
 802     clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
 803     clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
 804     return clone;
 805   }
 806
 807   public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
 808     return mapMergeNodetoMergingSet;
 809   }
 810
 811   public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
 812     this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
 813   }
 814
 815   public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
 816
 817     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
 818       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
 819     }
 820     return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
 821   }
 822
 823   public void identifyCombinationNodes() {
 824
 825     // 1) set combination node flag if a node combines more than one skeleton node.
 826     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 827       HNode node = (HNode) iterator.next();
 828       if (!node.isSkeleton()) {
 829         Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
 830         if (reachToSet.size() > 1) {
 831           // if (countSkeletonNodes(reachToSet) > 1) {
 832           System.out.println("-node=" + node + "  reachToSet=" + reachToSet);
 833           System.out.println("-set combinationnode=" + node);
 834           node.setCombinationNode(true);
 835           mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
 836         }
 837       }
 838     }
 839
 840     // 2) compute the outgoing set that needs to be directly connected from the combination node
 841     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 842       HNode node = (HNode) iterator.next();
 843       if (node.isCombinationNode()) {
 844         Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
 845         Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
 846         addMapCombineSetToOutgoingSet(combineSet, outSet);
 847       }
 848     }
 849
 850   }
 851
 852   public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
 853     return mapCombinationNodeToCombineNodeSet;
 854   }
 855
 856   public int countSkeletonNodes(Set<HNode> set) {
 857     int count = 0;
 858
 859     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 860       HNode node = (HNode) iterator.next();
 861       Set<Descriptor> descSet = getDescSetOfNode(node);
 862       count += descSet.size();
 863     }
 864
 865     return count;
 866   }
 867
 868   private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
 869     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
 870       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
 871     }
 872     mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
 873   }
 874
 875   private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
 876     // the method returns the set of nodes that are reachable from the current node
 877     // and do not combine the same set of skeleton nodes...
 878
 879     Set<HNode> visited = new HashSet<HNode>();
 880     Set<HNode> reachableSet = new HashSet<HNode>();
 881     Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
 882
 883     recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
 884
 885     return reachableSet;
 886   }
 887
 888   private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
 889       Set<HNode> reachableSet, Set<HNode> visited) {
 890
 891     Set<HNode> outSet = getOutgoingNodeSet(node);
 892     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 893       HNode outNode = (HNode) iterator.next();
 894
 895       if (outNode.isCombinationNode()) {
 896         Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
 897         if (combineSetOfOutNode.equals(combineSet)) {
 898           recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
 899               visited);
 900         } else {
 901           reachableSet.add(outNode);
 902         }
 903       } else if (outNode.isSkeleton()) {
 904         reachableSet.add(outNode);
 905       }
 906
 907     }
 908
 909   }
 910
 911   private Set<HNode> getReachableNodeSetFrom(HNode node) {
 912
 913     Set<HNode> reachableSet = new HashSet<HNode>();
 914     Set<HNode> visited = new HashSet<HNode>();
 915
 916     recurReachableNodeSetFrom(node, reachableSet, visited);
 917
 918     return reachableSet;
 919   }
 920
 921   private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
 922
 923     Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
 924     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
 925       HNode outNode = (HNode) iterator.next();
 926       reachableSet.add(outNode);
 927       if (!visited.contains(outNode)) {
 928         visited.add(outNode);
 929         recurReachableNodeSetFrom(outNode, reachableSet, visited);
 930       }
 931     }
 932
 933   }
 934
 935   public void assignUniqueIndexToNode() {
 936     int idx = 1;
 937     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 938       HNode node = (HNode) iterator.next();
 939       mapHNodeToUniqueIndex.put(node, idx);
 940       idx++;
 941     }
 942
 943     BASISTOPELEMENT = new HashSet<Integer>();
 944     for (int i = 1; i < idx + 1; i++) {
 945       BASISTOPELEMENT.add(i);
 946     }
 947   }
 948
 949   public BasisSet computeBasisSet() {
 950
 951     // assign a unique index to a node
 952     assignUniqueIndexToNode();
 953
 954     // compute basis for each node
 955     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 956       HNode node = (HNode) iterator.next();
 957
 958       Set<Integer> basis = new HashSet<Integer>();
 959       basis.addAll(BASISTOPELEMENT);
 960
 961       Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
 962       System.out.println("node=" + node + "    reachableNodeSet=" + reachableNodeSet);
 963
 964       // if a node is reachable from the current node
 965       // need to remove the index of the reachable node from the basis
 966
 967       basis.remove(getHNodeIndex(node));
 968       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
 969         HNode reachableNode = (HNode) iterator2.next();
 970         System.out.println("reachableNode=" + reachableNode);
 971         int idx = getHNodeIndex(reachableNode);
 972         basis.remove(idx);
 973       }
 974
 975       mapHNodeToBasis.put(node, basis);
 976     }
 977
 978     // construct the basis set
 979
 980     BasisSet basisSet = new BasisSet();
 981
 982     Set<HNode> keySet = mapHNodeToBasis.keySet();
 983     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 984       HNode node = (HNode) iterator.next();
 985       Set<Integer> basis = mapHNodeToBasis.get(node);
 986       basisSet.addElement(basis, node);
 987     }
 988
 989     return basisSet;
 990
 991   }
 992
 993   public int getHNodeIndex(HNode node) {
 994     return mapHNodeToUniqueIndex.get(node).intValue();
 995   }
 996
 997   public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
 998     return mapHNodeToUniqueIndex;
 999   }
1000
1001   public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1002     return mapHNodeToBasis;
1003   }
1004
1005   public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1006
1007     Set<HNode> combinationNodeSet = new HashSet<HNode>();
1008     Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1009     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1010       HNode key = (HNode) iterator.next();
1011
1012       if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1013         combinationNodeSet.add(key);
1014       }
1015     }
1016
1017     return combinationNodeSet;
1018   }
1019
1020   public void writeGraph() {
1021
1022     String graphName = "hierarchy" + name;
1023     graphName = graphName.replaceAll("[\\W]", "");
1024
1025     try {
1026       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1027
1028       bw.write("digraph " + graphName + " {\n");
1029
1030       Iterator<HNode> iter = nodeSet.iterator();
1031
1032       Set<HNode> addedNodeSet = new HashSet<HNode>();
1033
1034       while (iter.hasNext()) {
1035         HNode u = iter.next();
1036
1037         Set<HNode> outSet = getOutgoingNodeSet(u);
1038
1039         if (outSet.size() == 0) {
1040           if (!addedNodeSet.contains(u)) {
1041             drawNode(bw, u);
1042             addedNodeSet.add(u);
1043           }
1044         } else {
1045           for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1046             HNode v = (HNode) iterator.next();
1047             if (!addedNodeSet.contains(u)) {
1048               drawNode(bw, u);
1049               addedNodeSet.add(u);
1050             }
1051             if (!addedNodeSet.contains(v)) {
1052               drawNode(bw, v);
1053               addedNodeSet.add(v);
1054             }
1055             bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1056           }
1057         }
1058
1059       }
1060
1061       bw.write("}\n");
1062       bw.close();
1063
1064     } catch (IOException e) {
1065       e.printStackTrace();
1066     }
1067   }
1068
1069   public boolean contains(HNode node) {
1070     return nodeSet.contains(node);
1071   }
1072
1073   public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1074     return getOutgoingNodeSet(src).contains(dst);
1075   }
1076
1077   private String convertMergeSetToString(Set<HNode> mergeSet) {
1078     String str = "";
1079     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1080       HNode merged = (HNode) iterator.next();
1081       if (merged.isMergeNode()) {
1082         str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1083       } else {
1084         str += " " + merged.getName();
1085       }
1086     }
1087     return str;
1088   }
1089
1090   private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1091     String nodeName;
1092     if (node.isMergeNode()) {
1093       nodeName = node.getNamePropertyString();
1094       Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1095       nodeName += ":" + convertMergeSetToString(mergeSet);
1096     } else {
1097       nodeName = node.getNamePropertyString();
1098     }
1099     bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1100   }
1101 }