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