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<String, HNode> mapHNodeNameToCurrentHNode; // tracking which node corresponds to the initial
  30                                                  // node
  31   Map<HNode, Set<HNode>> mapMergeNodetoMergingSet;
  32
  33   // data structures for a combination node
  34   Map<Set<HNode>, HNode> mapSkeletonNodeSetToCombinationNode;
  35   Map<HNode, Set<HNode>> mapCombinationNodeToCombineNodeSet;
  36   Map<Set<HNode>, HNode> mapCombineNodeSetToCombinationNode;
  37   Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToOutgoingNodeSet;
  38
  39   Set<HNode> nodeSet;
  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     mapHNodeNameToCurrentHNode = new HashMap<String, 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 String getName() {
  77     return name;
  78   }
  79
  80   public void setName(String name) {
  81     this.name = name;
  82   }
  83
  84   public HierarchyGraph(Descriptor d) {
  85     this();
  86     desc = d;
  87     name = d.toString();
  88   }
  89
  90   public Map<HNode, Set<Descriptor>> getMapHNodeToDescSet() {
  91     return mapHNodeToDescSet;
  92   }
  93
  94   public void setMapHNodeToDescSet(Map<HNode, Set<Descriptor>> map) {
  95     mapHNodeToDescSet.putAll(map);
  96   }
  97
  98   public Map<HNode, HNode> getMapHNodeToCurrentHNode() {
  99     return mapHNodeToCurrentHNode;
 100   }
 101
 102   public Map<String, HNode> getMapHNodeNameToCurrentHNode() {
 103     return mapHNodeNameToCurrentHNode;
 104   }
 105
 106   public void setMapHNodeToCurrentHNode(Map<HNode, HNode> mapHNodeToCurrentHNode) {
 107     this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode;
 108   }
 109
 110   public void setMapHNodeNameToCurrentHNode(Map<String, HNode> mapHNodeNameToCurrentHNode) {
 111     this.mapHNodeNameToCurrentHNode = mapHNodeNameToCurrentHNode;
 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 + "\n");
 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 (!isEligibleForMerging(node1, node2)) {
 330           continue;
 331         }
 332
 333         if (!node1.equals(node2)) {
 334
 335           Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
 336           Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
 337
 338           if (incomingNodeSet1.equals(incomingNodeSet2)
 339               && outgoingNodeSet1.equals(outgoingNodeSet2)) {
 340             // need to merge node1 and node2
 341
 342             Set<HNode> mergeSet = new HashSet<HNode>();
 343             mergeSet.add(node1);
 344             mergeSet.add(node2);
 345             mergeNodes(mergeSet, onlyCombinationNodes);
 346             return true;
 347           }
 348
 349         }
 350       }
 351
 352     }
 353     return false;
 354   }
 355
 356   private boolean isEligibleForMerging(HNode node1, HNode node2) {
 357
 358     if (node1.isSharedNode() || node2.isSharedNode()) {
 359
 360       // if either of nodes is a shared node,
 361       // all descriptors of node1 & node2 should have a primitive type
 362
 363       Set<Descriptor> descSet = new HashSet<Descriptor>();
 364       descSet.addAll(getDescSetOfNode(node1));
 365       descSet.addAll(getDescSetOfNode(node2));
 366
 367       for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
 368         Descriptor desc = (Descriptor) iterator.next();
 369         if (!LocationInference.isPrimitive(desc)) {
 370           return false;
 371         }
 372       }
 373       return true;
 374     }
 375     return false;
 376   }
 377
 378   private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
 379     getIncomingNodeSet(dstHNode).add(srcHNode);
 380     getOutgoingNodeSet(srcHNode).add(dstHNode);
 381     System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
 382   }
 383
 384   private HNode mergeNodes(Set<HNode> set, boolean onlyCombinationNodes) {
 385
 386     Set<HNode> incomingNodeSet = new HashSet<HNode>();
 387     Set<HNode> outgoingNodeSet = new HashSet<HNode>();
 388
 389     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 390       HNode node = (HNode) iterator.next();
 391       incomingNodeSet.addAll(getIncomingNodeSet(node));
 392       outgoingNodeSet.addAll(getOutgoingNodeSet(node));
 393     }
 394
 395     String nodeName;
 396     boolean isMergeNode = false;
 397     if (onlyCombinationNodes) {
 398       nodeName = "Comb" + (LocationInference.locSeed++);
 399     } else {
 400       nodeName = "Node" + (LocationInference.locSeed++);
 401       isMergeNode = true;
 402     }
 403     HNode newMergeNode = new HNode(nodeName);
 404     newMergeNode.setMergeNode(isMergeNode);
 405
 406     nodeSet.add(newMergeNode);
 407     nodeSet.removeAll(set);
 408
 409     // if the input set contains a skeleton node, need to set a new merge node as skeleton also
 410     boolean hasSkeleton = false;
 411     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 412       HNode inNode = (HNode) iterator.next();
 413       if (inNode.isSkeleton()) {
 414         hasSkeleton = true;
 415         break;
 416       }
 417     }
 418     System.out.println("--Set merging node=" + newMergeNode + " as a skeleton=" + set
 419         + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
 420     newMergeNode.setSkeleton(hasSkeleton);
 421
 422     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 423       HNode node = (HNode) iterator.next();
 424       Set<Descriptor> descSetOfNode = getDescSetOfNode(node);
 425       for (Iterator iterator2 = descSetOfNode.iterator(); iterator2.hasNext();) {
 426         Descriptor desc = (Descriptor) iterator2.next();
 427         mappingDescriptorToHNode(desc, newMergeNode);
 428       }
 429     }
 430
 431     for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
 432       HNode inNode = (HNode) iterator.next();
 433       Set<HNode> outSet = getOutgoingNodeSet(inNode);
 434       outSet.removeAll(set);
 435       if (!set.contains(inNode)) {
 436         addEdgeWithNoCycleCheck(inNode, newMergeNode);
 437       }
 438     }
 439
 440     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
 441       HNode outNode = (HNode) iterator.next();
 442       Set<HNode> inSet = getIncomingNodeSet(outNode);
 443       inSet.removeAll(set);
 444       if (!set.contains(outNode)) {
 445         addEdgeWithNoCycleCheck(newMergeNode, outNode);
 446       }
 447     }
 448
 449     Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
 450     for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
 451       HNode merged = iter.next();
 452       if (merged.isSkeleton()) {
 453         mergedSkeletonNode.add(merged);
 454       }
 455     }
 456
 457     // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
 458     // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 459     mapMergeNodetoMergingSet.put(newMergeNode, set);
 460     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 461       HNode mergedNode = (HNode) iterator.next();
 462       addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
 463     }
 464     System.out.println("###mergedSkeletonNode=" + mergedSkeletonNode);
 465     System.out.println("###MERGING NODE=" + set + " new node=" + newMergeNode);
 466
 467     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 468       HNode hNode = (HNode) iterator.next();
 469       System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
 470     }
 471
 472     return newMergeNode;
 473   }
 474
 475   private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
 476     if (curNode.isMergeNode()) {
 477       Set<HNode> mergingSet = getMergingSet(curNode);
 478       mergingSet.add(curNode);
 479       System.out.println("addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
 480           + mergingSet);
 481       for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
 482         HNode mergingNode = (HNode) iterator.next();
 483         mapHNodeToCurrentHNode.put(mergingNode, newNode);
 484         mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
 485       }
 486     } else {
 487       mapHNodeToCurrentHNode.put(curNode, newNode);
 488       mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
 489     }
 490   }
 491
 492   public HNode getCurrentHNode(HNode node) {
 493     if (!mapHNodeToCurrentHNode.containsKey(node)) {
 494       mapHNodeToCurrentHNode.put(node, node);
 495     }
 496     return mapHNodeToCurrentHNode.get(node);
 497   }
 498
 499   public HNode getCurrentHNode(String nodeName) {
 500     return mapHNodeNameToCurrentHNode.get(nodeName);
 501   }
 502
 503   private Set<HNode> getMergingSet(HNode mergeNode) {
 504     Set<HNode> mergingSet = new HashSet<HNode>();
 505     Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
 506     for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
 507       HNode node = (HNode) iterator.next();
 508       if (node.isMergeNode()) {
 509         mergingSet.add(node);
 510         mergingSet.addAll(getMergingSet(node));
 511       } else {
 512         mergingSet.add(node);
 513       }
 514     }
 515     return mergingSet;
 516   }
 517
 518   public Set<Descriptor> getDescSetOfNode(HNode node) {
 519     if (!mapHNodeToDescSet.containsKey(node)) {
 520       mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
 521     }
 522     return mapHNodeToDescSet.get(node);
 523   }
 524
 525   private boolean reachTo(HNode src, HNode dst, Set<HNode> visited) {
 526     Set<HNode> connectedSet = getOutgoingNodeSet(src);
 527     for (Iterator<HNode> iterator = connectedSet.iterator(); iterator.hasNext();) {
 528       HNode n = iterator.next();
 529       if (n.equals(dst)) {
 530         return true;
 531       }
 532       if (!visited.contains(n)) {
 533         visited.add(n);
 534         if (reachTo(n, dst, visited)) {
 535           return true;
 536         }
 537       }
 538     }
 539     return false;
 540   }
 541
 542   private void recurReachSkeletonSet(HNode node, Set<HNode> connected, Set<HNode> visited) {
 543
 544     Set<HNode> outSet = getOutgoingNodeSet(node);
 545     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 546       HNode outNode = (HNode) iterator.next();
 547
 548       if (outNode.isSkeleton()) {
 549         connected.add(outNode);
 550       } else if (!visited.contains(outNode)) {
 551         visited.add(outNode);
 552         recurReachSkeletonSet(outNode, connected, visited);
 553       }
 554     }
 555
 556   }
 557
 558   public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
 559       Set<HNode> combinationNodeSet) {
 560     Set<HNode> reachable = new HashSet<HNode>();
 561     Set<HNode> visited = new HashSet<HNode>();
 562     visited.add(node);
 563     recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
 564     return reachable;
 565   }
 566
 567   public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
 568       Set<HNode> reachable, Set<HNode> combinationNodeSet) {
 569
 570     Set<HNode> outSet = getOutgoingNodeSet(node);
 571     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 572       HNode out = (HNode) iterator.next();
 573
 574       if (!visited.contains(out)) {
 575         visited.add(out);
 576         if (out.isSkeleton()) {
 577           reachable.add(out);
 578         } else if (out.isCombinationNode()) {
 579           if (combinationNodeSet == null) {
 580             reachable.add(out);
 581           } else if (!combinationNodeSet.contains(out)) {
 582             reachable.add(out);
 583           } else {
 584             recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
 585                 combinationNodeSet);
 586           }
 587         } else {
 588           recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
 589               combinationNodeSet);
 590         }
 591
 592       }
 593
 594     }
 595
 596   }
 597
 598   public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
 599     Set<HNode> visited = new HashSet<HNode>();
 600     return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
 601   }
 602
 603   public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
 604
 605     Set<HNode> outSet = getOutgoingNodeSet(node);
 606     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 607       HNode out = (HNode) iterator.next();
 608       // if (!visited.contains(out)) {
 609       if (out.isCombinationNode() || out.isSkeleton()) {
 610         return out;
 611       } else {
 612         // visited.add(out);
 613         return getDirectlyReachableSkeletonCombinationNodeFrom(out);
 614       }
 615     }
 616     // }
 617
 618     return null;
 619   }
 620
 621   public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
 622     // if an edge from src to dst introduces a new cycle flow,
 623     // the method returns the set of elements consisting of the cycle
 624     Set<HNode> cycleNodeSet = new HashSet<HNode>();
 625     // if the dst node reaches to the src node, the new relation
 626     // introduces a cycle to the lattice
 627     if (dst.equals(src)) {
 628       cycleNodeSet.add(dst);
 629       cycleNodeSet.add(src);
 630     } else if (reachTo(dst, src)) {
 631       cycleNodeSet.add(dst);
 632       cycleNodeSet.add(src);
 633       getInBetweenElements(dst, src, cycleNodeSet);
 634     }
 635     return cycleNodeSet;
 636   }
 637
 638   private void getInBetweenElements(HNode start, HNode end, Set<HNode> nodeSet) {
 639     Set<HNode> connectedSet = getOutgoingNodeSet(start);
 640     for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
 641       HNode cur = (HNode) iterator.next();
 642       if ((!start.equals(cur)) && (!cur.equals(end)) && reachTo(cur, end)) {
 643         nodeSet.add(cur);
 644         getInBetweenElements(cur, end, nodeSet);
 645       }
 646     }
 647   }
 648
 649   public boolean reachTo(HNode node1, HNode node2) {
 650     return reachTo(node1, node2, new HashSet<HNode>());
 651   }
 652
 653   public Set<HNode> getCombineSetByCombinationNode(HNode node) {
 654     if (!mapCombinationNodeToCombineNodeSet.containsKey(node)) {
 655       mapCombinationNodeToCombineNodeSet.put(node, new HashSet<HNode>());
 656     }
 657     return mapCombinationNodeToCombineNodeSet.get(node);
 658   }
 659
 660   public HNode getCombinationNode(Set<HNode> combineSet) {
 661     if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
 662       String name = "COMB" + (LocationInference.locSeed++);
 663       HNode node = new HNode(name);
 664       node.setCombinationNode(true);
 665       nodeSet.add(node);
 666       mapCombineNodeSetToCombinationNode.put(combineSet, node);
 667       mapCombinationNodeToCombineNodeSet.put(node, combineSet);
 668     }
 669
 670     return mapCombineNodeSetToCombinationNode.get(combineSet);
 671   }
 672
 673   public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
 674     return mapCombineNodeSetToCombinationNode;
 675   }
 676
 677   public Set<Set<HNode>> getCombineNodeSet() {
 678     return mapCombineNodeSetToOutgoingNodeSet.keySet();
 679   }
 680
 681   public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
 682     // add a new combination node where parameter/field flows are actually combined.
 683
 684     simpleHierarchyGraph.identifyCombinationNodes();
 685
 686     Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
 687     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 688       Set<HNode> combineSet = (Set<HNode>) iterator.next();
 689       System.out.println("--combineSet=" + combineSet);
 690       HNode combinationNode = getCombinationNode(combineSet);
 691       System.out.println("--combinationNode=" + combinationNode);
 692       // add an edge from a skeleton node to a combination node
 693       for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
 694         HNode inSkeletonNode = (HNode) iterator2.next();
 695         // System.out.println("--inSkeletonNode=" + inSkeletonNode + "  desc="
 696         // + inSkeletonNode.getDescriptor());
 697         HNode srcNode;
 698         if (inSkeletonNode.getDescriptor() == null) {
 699           // the node is merging one...
 700           srcNode = inSkeletonNode;
 701         } else {
 702           srcNode = getHNode(inSkeletonNode.getDescriptor());
 703         }
 704         // System.out.println("--srcNode=" + srcNode);
 705         addEdgeWithNoCycleCheck(srcNode, combinationNode);
 706       }
 707
 708       // add an edge from the combination node to outgoing nodes
 709       Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
 710       for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
 711         HNode curNode = (HNode) iterator2.next();
 712         if (curNode.isCombinationNode()) {
 713           Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
 714           HNode outNode = getCombinationNode(combineNode);
 715           addEdgeWithNoCycleCheck(combinationNode, outNode);
 716         } else if (curNode.isSkeleton()) {
 717           // HNode dstNode2 = getHNode(curNode.getDescriptor());
 718           HNode dstNode = getCurrentHNode(curNode);
 719           // System.out.println("-----curNode=" + curNode + "------->" + dstNode + "    dstNode2="
 720           // + dstNode2);
 721           addEdgeWithNoCycleCheck(combinationNode, dstNode);
 722         }
 723       }
 724
 725       System.out.println("--");
 726
 727     }
 728
 729   }
 730
 731   private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
 732     if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
 733       // need to create a new combination node
 734       String nodeName = "Comb" + (LocationInference.locSeed++);
 735       HNode newCombinationNode = new HNode(nodeName);
 736       newCombinationNode.setCombinationNode(true);
 737
 738       nodeSet.add(newCombinationNode);
 739       mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
 740
 741       for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 742         HNode reachToNode = (HNode) iterator.next();
 743         addEdge(reachToNode, newCombinationNode);
 744       }
 745
 746     }
 747
 748     HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
 749     for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
 750       HNode reachableNode = (HNode) iterator.next();
 751       addEdge(combinationNode, reachableNode);
 752     }
 753
 754   }
 755
 756   private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
 757
 758     Set<HNode> reachToSet = new HashSet<HNode>();
 759     Set<HNode> visited = new HashSet<HNode>();
 760     recurSkeletonReachTo(node, reachToSet, visited);
 761
 762     // if a node reaches to one of elements in the reachToSet, we do not need to keep it
 763     // because the node is not directly connected to the combination node
 764
 765     removeRedundantReachToNodes(reachToSet);
 766
 767     return reachToSet;
 768   }
 769
 770   private void removeRedundantReachToNodes(Set<HNode> reachToSet) {
 771
 772     Set<HNode> toberemoved = new HashSet<HNode>();
 773     for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
 774       HNode cur = (HNode) iterator.next();
 775
 776       for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
 777         HNode dst = (HNode) iterator2.next();
 778         if (!cur.equals(dst) && reachTo(cur, dst)) {
 779           // it is redundant
 780           toberemoved.add(cur);
 781         }
 782       }
 783     }
 784     reachToSet.removeAll(toberemoved);
 785   }
 786
 787   private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
 788
 789     Set<HNode> inSet = getIncomingNodeSet(node);
 790     for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
 791       HNode inNode = (HNode) iterator.next();
 792
 793       if (inNode.isSkeleton()) {
 794         reachToSet.add(inNode);
 795       } else if (!visited.contains(inNode)) {
 796         visited.add(inNode);
 797         recurSkeletonReachTo(inNode, reachToSet, visited);
 798       }
 799     }
 800
 801   }
 802
 803   public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
 804     return mapHNodeToOutgoingSet;
 805   }
 806
 807   public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
 808     return mapHNodeToIncomingSet;
 809   }
 810
 811   public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
 812     mapHNodeToOutgoingSet.clear();
 813     Set<HNode> keySet = in.keySet();
 814     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 815       HNode key = (HNode) iterator.next();
 816       Set<HNode> inSet = in.get(key);
 817       Set<HNode> newSet = new HashSet<HNode>();
 818       newSet.addAll(inSet);
 819       mapHNodeToOutgoingSet.put(key, newSet);
 820     }
 821   }
 822
 823   public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
 824     mapHNodeToIncomingSet.clear();
 825     Set<HNode> keySet = in.keySet();
 826     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 827       HNode key = (HNode) iterator.next();
 828       Set<HNode> inSet = in.get(key);
 829       Set<HNode> newSet = new HashSet<HNode>();
 830       newSet.addAll(inSet);
 831       mapHNodeToIncomingSet.put(key, newSet);
 832     }
 833   }
 834
 835   public void setNodeSet(Set<HNode> inSet) {
 836     nodeSet.clear();
 837     nodeSet.addAll(inSet);
 838   }
 839
 840   public HierarchyGraph clone() {
 841     HierarchyGraph clone = new HierarchyGraph();
 842     clone.setDesc(getDesc());
 843     clone.setName(getName());
 844     clone.setNodeSet(getNodeSet());
 845     clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
 846     clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
 847     clone.setMapDescToHNode(getMapDescToHNode());
 848     clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
 849     clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
 850     clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
 851     clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
 852
 853     return clone;
 854   }
 855
 856   public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
 857     return mapMergeNodetoMergingSet;
 858   }
 859
 860   public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
 861     this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
 862   }
 863
 864   public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
 865
 866     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
 867       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
 868     }
 869     return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
 870   }
 871
 872   public void identifyCombinationNodes() {
 873
 874     // 1) set combination node flag if a node combines more than one skeleton node.
 875     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 876       HNode node = (HNode) iterator.next();
 877       if (!node.isSkeleton()) {
 878         Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
 879         if (reachToSet.size() > 1) {
 880           // if (countSkeletonNodes(reachToSet) > 1) {
 881           System.out.println("-node=" + node + "  reachToSet=" + reachToSet);
 882           System.out.println("-set combinationnode=" + node);
 883           node.setCombinationNode(true);
 884           mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
 885         }
 886       }
 887     }
 888
 889     // 2) compute the outgoing set that needs to be directly connected from the combination node
 890     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 891       HNode node = (HNode) iterator.next();
 892       if (node.isCombinationNode()) {
 893         Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
 894         Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
 895         addMapCombineSetToOutgoingSet(combineSet, outSet);
 896       }
 897     }
 898
 899   }
 900
 901   public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
 902     return mapCombinationNodeToCombineNodeSet;
 903   }
 904
 905   public int countSkeletonNodes(Set<HNode> set) {
 906     int count = 0;
 907
 908     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 909       HNode node = (HNode) iterator.next();
 910       Set<Descriptor> descSet = getDescSetOfNode(node);
 911       count += descSet.size();
 912     }
 913
 914     return count;
 915   }
 916
 917   private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
 918     if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
 919       mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
 920     }
 921     mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
 922   }
 923
 924   private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
 925     // the method returns the set of nodes that are reachable from the current node
 926     // and do not combine the same set of skeleton nodes...
 927
 928     Set<HNode> visited = new HashSet<HNode>();
 929     Set<HNode> reachableSet = new HashSet<HNode>();
 930     Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
 931
 932     recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
 933
 934     return reachableSet;
 935   }
 936
 937   private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
 938       Set<HNode> reachableSet, Set<HNode> visited) {
 939
 940     Set<HNode> outSet = getOutgoingNodeSet(node);
 941     for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
 942       HNode outNode = (HNode) iterator.next();
 943
 944       if (outNode.isCombinationNode()) {
 945         Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
 946         if (combineSetOfOutNode.equals(combineSet)) {
 947           recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
 948               visited);
 949         } else {
 950           reachableSet.add(outNode);
 951         }
 952       } else if (outNode.isSkeleton()) {
 953         reachableSet.add(outNode);
 954       }
 955
 956     }
 957
 958   }
 959
 960   private Set<HNode> getReachableNodeSetFrom(HNode node) {
 961
 962     Set<HNode> reachableSet = new HashSet<HNode>();
 963     Set<HNode> visited = new HashSet<HNode>();
 964
 965     recurReachableNodeSetFrom(node, reachableSet, visited);
 966
 967     return reachableSet;
 968   }
 969
 970   private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
 971
 972     Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
 973     for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
 974       HNode outNode = (HNode) iterator.next();
 975       reachableSet.add(outNode);
 976       if (!visited.contains(outNode)) {
 977         visited.add(outNode);
 978         recurReachableNodeSetFrom(outNode, reachableSet, visited);
 979       }
 980     }
 981
 982   }
 983
 984   public void assignUniqueIndexToNode() {
 985     int idx = 1;
 986     System.out.println("nodeSet=" + nodeSet);
 987     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
 988       HNode node = (HNode) iterator.next();
 989       mapHNodeToUniqueIndex.put(node, idx);
 990       idx++;
 991     }
 992
 993     BASISTOPELEMENT = new HashSet<Integer>();
 994     for (int i = 1; i < idx + 1; i++) {
 995       BASISTOPELEMENT.add(i);
 996     }
 997   }
 998
 999   public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
1000
1001     // assign a unique index to a node
1002     assignUniqueIndexToNode();
1003
1004     // compute basis for each node
1005     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1006       HNode node = (HNode) iterator.next();
1007
1008       if (notGenerateSet.contains(node)) {
1009         System.out.println("%%%SKIP =" + node);
1010         continue;
1011       }
1012       Set<Integer> basis = new HashSet<Integer>();
1013       basis.addAll(BASISTOPELEMENT);
1014
1015       Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
1016       System.out.println("node=" + node + "    reachableNodeSet=" + reachableNodeSet);
1017       System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
1018       // if a node is reachable from the current node
1019       // need to remove the index of the reachable node from the basis
1020
1021       basis.remove(getHNodeIndex(node));
1022       for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1023         HNode reachableNode = (HNode) iterator2.next();
1024         System.out.println("reachableNode=" + reachableNode);
1025         System.out.println("getHNodeIndex(reachableNode))="
1026             + mapHNodeToUniqueIndex.get(reachableNode));
1027         int idx = getHNodeIndex(reachableNode);
1028         basis.remove(idx);
1029       }
1030
1031       mapHNodeToBasis.put(node, basis);
1032     }
1033
1034     // construct the basis set
1035
1036     BasisSet basisSet = new BasisSet();
1037
1038     Set<HNode> keySet = mapHNodeToBasis.keySet();
1039     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1040       HNode node = (HNode) iterator.next();
1041       Set<Integer> basis = mapHNodeToBasis.get(node);
1042       basisSet.addElement(basis, node);
1043     }
1044
1045     return basisSet;
1046
1047   }
1048
1049   public int getHNodeIndex(HNode node) {
1050     return mapHNodeToUniqueIndex.get(node).intValue();
1051   }
1052
1053   public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
1054     return mapHNodeToUniqueIndex;
1055   }
1056
1057   public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1058     return mapHNodeToBasis;
1059   }
1060
1061   public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1062
1063     Set<HNode> combinationNodeSet = new HashSet<HNode>();
1064     Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1065     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1066       HNode key = (HNode) iterator.next();
1067
1068       if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1069         combinationNodeSet.add(key);
1070       }
1071     }
1072
1073     return combinationNodeSet;
1074   }
1075
1076   public void writeGraph() {
1077
1078     String graphName = "hierarchy" + name;
1079     graphName = graphName.replaceAll("[\\W]", "");
1080
1081     try {
1082       BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1083
1084       bw.write("digraph " + graphName + " {\n");
1085
1086       Iterator<HNode> iter = nodeSet.iterator();
1087
1088       Set<HNode> addedNodeSet = new HashSet<HNode>();
1089
1090       while (iter.hasNext()) {
1091         HNode u = iter.next();
1092
1093         Set<HNode> outSet = getOutgoingNodeSet(u);
1094
1095         if (outSet.size() == 0) {
1096           if (!addedNodeSet.contains(u)) {
1097             drawNode(bw, u);
1098             addedNodeSet.add(u);
1099           }
1100         } else {
1101           for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1102             HNode v = (HNode) iterator.next();
1103             if (!addedNodeSet.contains(u)) {
1104               drawNode(bw, u);
1105               addedNodeSet.add(u);
1106             }
1107             if (!addedNodeSet.contains(v)) {
1108               drawNode(bw, v);
1109               addedNodeSet.add(v);
1110             }
1111             bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1112           }
1113         }
1114
1115       }
1116
1117       bw.write("}\n");
1118       bw.close();
1119
1120     } catch (IOException e) {
1121       e.printStackTrace();
1122     }
1123   }
1124
1125   public boolean contains(HNode node) {
1126     return nodeSet.contains(node);
1127   }
1128
1129   public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1130     return getOutgoingNodeSet(src).contains(dst);
1131   }
1132
1133   private String convertMergeSetToString(Set<HNode> mergeSet) {
1134     String str = "";
1135     for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1136       HNode merged = (HNode) iterator.next();
1137       if (merged.isMergeNode()) {
1138         str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1139       } else {
1140         str += " " + merged.getName();
1141       }
1142     }
1143     return str;
1144   }
1145
1146   private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1147     String nodeName;
1148     if (node.isMergeNode()) {
1149       nodeName = node.getNamePropertyString();
1150       Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1151       nodeName += ":" + convertMergeSetToString(mergeSet);
1152     } else {
1153       nodeName = node.getNamePropertyString();
1154     }
1155     bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1156   }
1157
1158   public int countHopFromTopLocation(HNode node) {
1159
1160     Set<HNode> inNodeSet = getIncomingNodeSet(node);
1161     int count = 0;
1162     if (inNodeSet.size() > 0) {
1163       count = recurCountHopFromTopLocation(inNodeSet, 1);
1164     }
1165
1166     return count;
1167   }
1168
1169   private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
1170
1171     int max = curCount;
1172     for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1173       HNode node = (HNode) iterator.next();
1174       Set<HNode> inNodeSet = getIncomingNodeSet(node);
1175       if (inNodeSet.size() > 0) {
1176         int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
1177         if (max < recurCount) {
1178           max = recurCount;
1179         }
1180       }
1181     }
1182     return max;
1183   }
1184
1185 }