1 package Analysis.SSJava;
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;
13 import IR.FieldDescriptor;
14 import IR.VarDescriptor;
16 public class HierarchyGraph {
23 Map<HNode, Set<HNode>> mapHNodeToIncomingSet;
24 Map<HNode, Set<HNode>> mapHNodeToOutgoingSet;
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
31 Map<HNode, Set<HNode>> mapMergeNodetoMergingSet;
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;
39 Map<HNode, Set<HNode>> mapNormalNodeToSCNodeReachToSet;
41 Map<Set<HNode>, Set<HNode>> mapCombineNodeSetToFirstNodeOfChainSet;
45 // for the lattice generation
46 Map<HNode, Integer> mapHNodeToUniqueIndex;
47 Map<HNode, Set<Integer>> mapHNodeToBasis;
48 Set<Integer> BASISTOPELEMENT;
50 public HierarchyGraph() {
51 mapHNodeToIncomingSet = new HashMap<HNode, Set<HNode>>();
52 mapHNodeToOutgoingSet = new HashMap<HNode, Set<HNode>>();
53 mapHNodeToDescSet = new HashMap<HNode, Set<Descriptor>>();
54 mapDescToHNode = new HashMap<Descriptor, HNode>();
55 mapSkeletonNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
56 mapCombinationNodeToCombineNodeSet = new HashMap<HNode, Set<HNode>>();
57 mapCombineNodeSetToOutgoingNodeSet = new HashMap<Set<HNode>, Set<HNode>>();
58 mapCombineNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
59 nodeSet = new HashSet<HNode>();
61 mapHNodeToUniqueIndex = new HashMap<HNode, Integer>();
62 mapHNodeToBasis = new HashMap<HNode, Set<Integer>>();
64 mapMergeNodetoMergingSet = new HashMap<HNode, Set<HNode>>();
66 mapHNodeToCurrentHNode = new HashMap<HNode, HNode>();
68 mapHNodeNameToCurrentHNode = new HashMap<String, HNode>();
70 mapNormalNodeToSCNodeReachToSet = new HashMap<HNode, Set<HNode>>();
72 mapCombineNodeSetToFirstNodeOfChainSet = new HashMap<Set<HNode>, Set<HNode>>();
75 public Descriptor getDesc() {
79 public void setDesc(Descriptor desc) {
83 public String getName() {
87 public void setName(String name) {
91 public HierarchyGraph(Descriptor d) {
97 public Map<HNode, Set<Descriptor>> getMapHNodeToDescSet() {
98 return mapHNodeToDescSet;
101 public void setMapHNodeToDescSet(Map<HNode, Set<Descriptor>> map) {
102 mapHNodeToDescSet.putAll(map);
105 public Map<HNode, HNode> getMapHNodeToCurrentHNode() {
106 return mapHNodeToCurrentHNode;
109 public Map<String, HNode> getMapHNodeNameToCurrentHNode() {
110 return mapHNodeNameToCurrentHNode;
113 public void setMapHNodeToCurrentHNode(Map<HNode, HNode> mapHNodeToCurrentHNode) {
114 this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode;
117 public void setMapHNodeNameToCurrentHNode(Map<String, HNode> mapHNodeNameToCurrentHNode) {
118 this.mapHNodeNameToCurrentHNode = mapHNodeNameToCurrentHNode;
121 public Map<Descriptor, HNode> getMapDescToHNode() {
122 return mapDescToHNode;
125 public void setMapDescToHNode(Map<Descriptor, HNode> map) {
126 mapDescToHNode.putAll(map);
129 public Set<HNode> getNodeSet() {
133 public void addEdge(HNode srcHNode, HNode dstHNode) {
135 if (!nodeSet.contains(srcHNode)) {
136 nodeSet.add(srcHNode);
139 if (!nodeSet.contains(dstHNode)) {
140 nodeSet.add(dstHNode);
143 Set<HNode> possibleCycleSet = getPossibleCycleNodes(srcHNode, dstHNode);
145 if (possibleCycleSet.size() > 0) {
147 if (possibleCycleSet.size() == 1) {
148 // System.out.println("possibleCycleSet=" + possibleCycleSet + " from src=" + srcHNode
149 // + " dstHNode=" + dstHNode);
150 if (dstHNode.isSharedNode()) {
151 // it has already been assigned shared node.
153 dstHNode.setSharedNode(true);
154 // System.out.println("$$$setShared=" + dstHNode);
159 // System.out.println("--- CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
160 HNode newMergeNode = mergeNodes(possibleCycleSet);
161 newMergeNode.setSharedNode(true);
164 getIncomingNodeSet(dstHNode).add(srcHNode);
165 getOutgoingNodeSet(srcHNode).add(dstHNode);
166 // System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
171 public void addNode(HNode node) {
175 public void addEdge(Descriptor src, Descriptor dst) {
177 if (src.equals(LocationInference.LITERALDESC)) {
178 // in this case, we do not need to add a source hnode
179 // just add a destination hnode
182 HNode srcHNode = getHNode(src);
183 HNode dstHNode = getHNode(dst);
184 addEdge(srcHNode, dstHNode);
189 public void setParamHNode(Descriptor d) {
190 getHNode(d).setSkeleton(true);
193 public HNode getHNode(Descriptor d) {
194 if (!mapDescToHNode.containsKey(d)) {
195 HNode newNode = new HNode(d);
197 if (d instanceof FieldDescriptor) {
198 newNode.setSkeleton(true);
201 if (d.equals(LocationInference.TOPDESC)) {
202 newNode.setSkeleton(true);
205 String symbol = d.getSymbol();
206 if (symbol.startsWith(LocationInference.PCLOC) || symbol.startsWith(LocationInference.RLOC)) {
207 newNode.setSkeleton(true);
210 mappingDescriptorToHNode(d, newNode);
211 nodeSet.add(newNode);
213 return mapDescToHNode.get(d);
216 public HNode getHNode(String name) {
217 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
218 HNode node = (HNode) iterator.next();
219 if (node.getName().equals(name)) {
226 private void mappingDescriptorToHNode(Descriptor desc, HNode node) {
227 mapDescToHNode.put(desc, node);
228 if (!mapHNodeToDescSet.containsKey(node)) {
229 mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
231 mapHNodeToDescSet.get(node).add(desc);
234 public HierarchyGraph generateSkeletonGraph() {
236 // compose a skeleton graph that only consists of fields or parameters
237 HierarchyGraph skeletonGraph = new HierarchyGraph(desc);
238 skeletonGraph.setName(desc + "_SKELETON");
240 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
241 HNode src = (HNode) iterator.next();
242 if (src.isSkeleton()) {
243 Set<HNode> reachSet = getDirectlyReachSkeletonSet(src);
244 if (reachSet.size() > 0) {
245 for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
246 HNode dst = (HNode) iterator2.next();
247 skeletonGraph.addEdge(src, dst);
250 skeletonGraph.addNode(src);
255 skeletonGraph.setMapDescToHNode(getMapDescToHNode());
256 skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet());
257 skeletonGraph.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
258 skeletonGraph.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
259 skeletonGraph.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
261 return skeletonGraph;
265 private Set<HNode> getDirectlyReachSkeletonSet(HNode node) {
267 Set<HNode> visited = new HashSet<HNode>();
268 Set<HNode> connected = new HashSet<HNode>();
269 recurReachSkeletonSet(node, connected, visited);
274 public void removeRedundantEdges() {
276 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
277 HNode src = (HNode) iterator.next();
278 Set<HNode> connectedSet = getOutgoingNodeSet(src);
279 Set<HNode> toberemovedSet = new HashSet<HNode>();
280 for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
281 HNode dst = (HNode) iterator2.next();
282 Set<HNode> otherNeighborSet = new HashSet<HNode>();
283 otherNeighborSet.addAll(connectedSet);
284 otherNeighborSet.remove(dst);
285 for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
286 HNode neighbor = (HNode) iterator3.next();
287 if (reachTo(neighbor, dst, new HashSet<HNode>())) {
288 toberemovedSet.add(dst);
292 if (toberemovedSet.size() > 0) {
293 connectedSet.removeAll(toberemovedSet);
295 for (Iterator iterator2 = toberemovedSet.iterator(); iterator2.hasNext();) {
296 HNode node = (HNode) iterator2.next();
297 getIncomingNodeSet(node).remove(src);
305 public void simplifyHierarchyGraph(LocationInference infer) {
306 removeRedundantEdges();
307 combineRedundantNodes(infer);
310 public void combineRedundantNodes(LocationInference infer) {
311 // Combine field/parameter nodes who have the same set of incoming/outgoing edges.
312 boolean isUpdated = false;
314 isUpdated = combineTwoRedundatnNodes(infer);
318 public Set<HNode> getIncomingNodeSet(HNode node) {
319 if (!mapHNodeToIncomingSet.containsKey(node)) {
320 mapHNodeToIncomingSet.put(node, new HashSet<HNode>());
322 return mapHNodeToIncomingSet.get(node);
325 public Set<HNode> getOutgoingNodeSet(HNode node) {
326 if (!mapHNodeToOutgoingSet.containsKey(node)) {
327 mapHNodeToOutgoingSet.put(node, new HashSet<HNode>());
329 return mapHNodeToOutgoingSet.get(node);
332 private boolean combineTwoRedundatnNodes(LocationInference infer) {
333 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
334 HNode node1 = (HNode) iterator.next();
336 // if ((onlyCombinationNodes && (!node1.isCombinationNode()))
337 // || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
341 if (!node1.isSkeleton()) {
345 Set<HNode> incomingNodeSet1 = getIncomingNodeSet(node1);
346 Set<HNode> outgoingNodeSet1 = getOutgoingNodeSet(node1);
348 for (Iterator iterator2 = nodeSet.iterator(); iterator2.hasNext();) {
349 HNode node2 = (HNode) iterator2.next();
351 // if ((onlyCombinationNodes && (!node2.isCombinationNode()))
352 // || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
356 if (!node2.isSkeleton()) {
360 if (!isEligibleForMerging(node1, node2)) {
364 if (!node1.equals(node2)) {
366 Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
367 Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
369 if (incomingNodeSet1.equals(incomingNodeSet2)
370 && outgoingNodeSet1.equals(outgoingNodeSet2)) {
371 // need to merge node1 and node2
374 // merge two nodes only if every hierarchy graph in the inheritance hierarchy
375 // that includes both nodes allows the merging of them...
376 Set<HNode> mergeSet = new HashSet<HNode>();
379 infer.isValidMergeInheritanceCheck(desc, mergeSet);
383 mergeNodes(mergeSet);
394 private boolean isEligibleForMerging(HNode node1, HNode node2) {
396 if (node1.isSharedNode() || node2.isSharedNode()) {
398 // if either of nodes is a shared node,
399 // all descriptors of node1 & node2 should have a primitive type
401 Set<Descriptor> descSet = new HashSet<Descriptor>();
402 descSet.addAll(getDescSetOfNode(node1));
403 descSet.addAll(getDescSetOfNode(node2));
405 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
406 Descriptor desc = (Descriptor) iterator.next();
407 if (!LocationInference.isPrimitive(desc)) {
416 private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
417 getIncomingNodeSet(dstHNode).add(srcHNode);
418 getOutgoingNodeSet(srcHNode).add(dstHNode);
419 // System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
422 private HNode mergeNodes(Set<HNode> set) {
424 Set<HNode> incomingNodeSet = new HashSet<HNode>();
425 Set<HNode> outgoingNodeSet = new HashSet<HNode>();
427 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
428 HNode node = (HNode) iterator.next();
429 incomingNodeSet.addAll(getIncomingNodeSet(node));
430 outgoingNodeSet.addAll(getOutgoingNodeSet(node));
434 boolean isMergeNode = false;
435 nodeName = "MNode" + (LocationInference.locSeed++);
438 HNode newMergeNode = new HNode(nodeName);
439 newMergeNode.setMergeNode(isMergeNode);
441 nodeSet.add(newMergeNode);
442 nodeSet.removeAll(set);
444 // if the input set contains a skeleton node, need to set a new merge node as skeleton also
445 boolean hasSkeleton = false;
446 boolean hasShared = false;
447 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
448 HNode inNode = (HNode) iterator.next();
449 if (inNode.isSkeleton()) {
452 if (inNode.isSharedNode()) {
456 // System.out.println("-----Set merging node=" + newMergeNode + " as a skeleton=" + set
457 // + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
458 newMergeNode.setSkeleton(hasSkeleton);
459 newMergeNode.setSharedNode(hasShared);
461 // System.out.println("-----MERGING NODE=" + set + " new node=" + newMergeNode);
463 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
464 HNode node = (HNode) iterator.next();
465 Set<Descriptor> descSetOfNode = getDescSetOfNode(node);
466 for (Iterator iterator2 = descSetOfNode.iterator(); iterator2.hasNext();) {
467 Descriptor desc = (Descriptor) iterator2.next();
468 mappingDescriptorToHNode(desc, newMergeNode);
472 for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
473 HNode inNode = (HNode) iterator.next();
474 Set<HNode> outSet = getOutgoingNodeSet(inNode);
475 outSet.removeAll(set);
476 if (!set.contains(inNode)) {
477 addEdgeWithNoCycleCheck(inNode, newMergeNode);
481 for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
482 HNode outNode = (HNode) iterator.next();
483 Set<HNode> inSet = getIncomingNodeSet(outNode);
484 inSet.removeAll(set);
485 if (!set.contains(outNode)) {
486 addEdgeWithNoCycleCheck(newMergeNode, outNode);
490 Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
491 for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
492 HNode merged = iter.next();
493 if (merged.isSkeleton()) {
494 mergedSkeletonNode.add(merged);
498 // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
499 // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
500 mapMergeNodetoMergingSet.put(newMergeNode, set);
501 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
502 HNode mergedNode = (HNode) iterator.next();
503 addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
506 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
507 HNode hNode = (HNode) iterator.next();
508 // System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
511 // System.out.println();
516 private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
518 if (curNode.isMergeNode()) {
519 Set<HNode> mergingSet = getMergingSet(curNode);
520 mergingSet.add(curNode);
521 // System.out.println("-------addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
522 // + mergingSet + " newNode=" + newNode);
523 for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
524 HNode mergingNode = (HNode) iterator.next();
525 mapHNodeToCurrentHNode.put(mergingNode, newNode);
526 mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
529 mapHNodeToCurrentHNode.put(curNode, newNode);
530 mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
535 public HNode getCurrentHNode(HNode node) {
536 if (!mapHNodeToCurrentHNode.containsKey(node)) {
537 mapHNodeToCurrentHNode.put(node, node);
539 return mapHNodeToCurrentHNode.get(node);
542 public HNode getCurrentHNode(String nodeName) {
543 return mapHNodeNameToCurrentHNode.get(nodeName);
546 private Set<HNode> getMergingSet(HNode mergeNode) {
547 Set<HNode> mergingSet = new HashSet<HNode>();
548 Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
549 for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
550 HNode node = (HNode) iterator.next();
551 if (node.isMergeNode()) {
552 mergingSet.add(node);
553 mergingSet.addAll(getMergingSet(node));
555 mergingSet.add(node);
561 public Set<Descriptor> getDescSetOfNode(HNode node) {
562 if (!mapHNodeToDescSet.containsKey(node)) {
563 mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
565 return mapHNodeToDescSet.get(node);
568 private boolean reachTo(HNode src, HNode dst, Set<HNode> visited) {
569 Set<HNode> connectedSet = getOutgoingNodeSet(src);
570 for (Iterator<HNode> iterator = connectedSet.iterator(); iterator.hasNext();) {
571 HNode n = iterator.next();
575 if (!visited.contains(n)) {
577 if (reachTo(n, dst, visited)) {
585 private void recurReachSkeletonSet(HNode node, Set<HNode> connected, Set<HNode> visited) {
587 Set<HNode> outSet = getOutgoingNodeSet(node);
588 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
589 HNode outNode = (HNode) iterator.next();
591 if (outNode.isSkeleton()) {
592 connected.add(outNode);
593 } else if (!visited.contains(outNode)) {
594 visited.add(outNode);
595 recurReachSkeletonSet(outNode, connected, visited);
601 public Set<HNode> getReachableSCNodeSet(HNode startNode) {
602 // returns the set of hnodes which is reachable from the startNode and is either SC node or a
603 // node which is directly connected to the SC nodes
604 Set<HNode> reachable = new HashSet<HNode>();
605 Set<HNode> visited = new HashSet<HNode>();
606 visited.add(startNode);
607 recurReachableNodeSet(startNode, visited, reachable);
611 public Set<HNode> getSCNodeReachToSet(HNode node) {
612 if (!mapNormalNodeToSCNodeReachToSet.containsKey(node)) {
613 mapNormalNodeToSCNodeReachToSet.put(node, new HashSet<HNode>());
615 return mapNormalNodeToSCNodeReachToSet.get(node);
618 private void recurReachableNodeSet(HNode node, Set<HNode> visited, Set<HNode> reachable) {
620 Set<HNode> outSet = getOutgoingNodeSet(node);
621 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
622 HNode out = (HNode) iterator.next();
624 if (!visited.contains(out)) {
626 Set<HNode> reachableFromSCNodeSet = reachableFromSCNode(out);
627 mapNormalNodeToSCNodeReachToSet.put(out, reachableFromSCNodeSet);
628 if (out.isSkeleton() || out.isCombinationNode() || reachableFromSCNodeSet.size() > 0) {
632 recurReachableNodeSet(out, visited, reachable);
641 private Set<HNode> reachableFromSCNode(HNode node) {
642 Set<HNode> visited = new HashSet<HNode>();
644 Set<HNode> reachable = new HashSet<HNode>();
645 recurReachableFromSCNode(node, reachable, visited);
649 private void recurReachableFromSCNode(HNode node, Set<HNode> reachable, Set<HNode> visited) {
650 Set<HNode> inNodeSet = getIncomingNodeSet(node);
651 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
652 HNode inNode = (HNode) iterator.next();
653 if (inNode.isSkeleton() || inNode.isCombinationNode()) {
655 reachable.add(inNode);
656 } else if (!visited.contains(inNode)) {
658 recurReachableFromSCNode(inNode, reachable, visited);
663 public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
664 Set<HNode> combinationNodeSet) {
665 Set<HNode> reachable = new HashSet<HNode>();
666 Set<HNode> visited = new HashSet<HNode>();
668 recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
672 public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
673 Set<HNode> reachable, Set<HNode> combinationNodeSet) {
675 Set<HNode> outSet = getOutgoingNodeSet(node);
676 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
677 HNode out = (HNode) iterator.next();
679 if (!visited.contains(out)) {
681 if (out.isSkeleton()) {
683 } else if (out.isCombinationNode()) {
684 if (combinationNodeSet == null) {
686 } else if (!combinationNodeSet.contains(out)) {
689 recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
693 recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
703 public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
704 Set<HNode> visited = new HashSet<HNode>();
705 return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
708 public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
710 Set<HNode> outSet = getOutgoingNodeSet(node);
711 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
712 HNode out = (HNode) iterator.next();
713 // if (!visited.contains(out)) {
714 if (out.isCombinationNode() || out.isSkeleton()) {
718 return getDirectlyReachableSkeletonCombinationNodeFrom(out);
726 public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
727 // if an edge from src to dst introduces a new cycle flow,
728 // the method returns the set of elements consisting of the cycle
729 Set<HNode> cycleNodeSet = new HashSet<HNode>();
730 // if the dst node reaches to the src node, the new relation
731 // introduces a cycle to the lattice
732 if (dst.equals(src)) {
733 cycleNodeSet.add(dst);
734 cycleNodeSet.add(src);
735 } else if (reachTo(dst, src)) {
736 cycleNodeSet.add(dst);
737 cycleNodeSet.add(src);
738 getInBetweenElements(dst, src, cycleNodeSet);
743 private void getInBetweenElements(HNode start, HNode end, Set<HNode> nodeSet) {
744 Set<HNode> connectedSet = getOutgoingNodeSet(start);
745 for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
746 HNode cur = (HNode) iterator.next();
747 if ((!start.equals(cur)) && (!cur.equals(end)) && reachTo(cur, end)) {
749 getInBetweenElements(cur, end, nodeSet);
754 public boolean reachTo(HNode node1, HNode node2) {
755 return reachTo(node1, node2, new HashSet<HNode>());
758 public Set<HNode> getCombineSetByCombinationNode(HNode node) {
759 if (!mapCombinationNodeToCombineNodeSet.containsKey(node)) {
760 mapCombinationNodeToCombineNodeSet.put(node, new HashSet<HNode>());
762 return mapCombinationNodeToCombineNodeSet.get(node);
765 public HNode getCombinationNode(Set<HNode> combineSet) {
766 if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
767 String name = "COMB" + (LocationInference.locSeed++);
768 HNode node = new HNode(name);
769 node.setCombinationNode(true);
771 mapCombineNodeSetToCombinationNode.put(combineSet, node);
772 mapCombinationNodeToCombineNodeSet.put(node, combineSet);
775 return mapCombineNodeSetToCombinationNode.get(combineSet);
778 public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
779 return mapCombineNodeSetToCombinationNode;
782 public Set<Set<HNode>> getCombineNodeSet() {
783 return mapCombineNodeSetToOutgoingNodeSet.keySet();
786 public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
787 // add a new combination node where parameter/field flows are actually combined.
789 simpleHierarchyGraph.identifyCombinationNodes();
791 Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
792 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
793 Set<HNode> combineSet = (Set<HNode>) iterator.next();
794 System.out.println("--combineSet=" + combineSet);
795 HNode combinationNode = getCombinationNode(combineSet);
796 System.out.println("--combinationNode=" + combinationNode + " combineSet=" + combineSet);
798 // System.out.println("--hierarchynodes="
799 // + simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet));
801 // add an edge from a skeleton node to a combination node
802 for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
803 HNode inSkeletonNode = (HNode) iterator2.next();
804 // System.out.println("--inSkeletonNode=" + inSkeletonNode + " desc="
805 // + inSkeletonNode.getDescriptor());
807 if (inSkeletonNode.getDescriptor() == null) {
808 // the node is merging one...
809 srcNode = inSkeletonNode;
811 srcNode = getHNode(inSkeletonNode.getDescriptor());
813 // System.out.println("--srcNode=" + srcNode);
814 addEdgeWithNoCycleCheck(srcNode, combinationNode);
817 // add an edge from the combination node to outgoing nodes
818 Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
819 for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
820 HNode curNode = (HNode) iterator2.next();
821 if (curNode.isCombinationNode()) {
822 Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
823 HNode outNode = getCombinationNode(combineNode);
824 addEdgeWithNoCycleCheck(combinationNode, outNode);
825 } else if (curNode.isSkeleton()) {
826 // HNode dstNode2 = getHNode(curNode.getDescriptor());
827 HNode dstNode = getCurrentHNode(curNode);
828 // System.out.println("-----curNode=" + curNode + "------->" + dstNode + " dstNode2="
830 addEdgeWithNoCycleCheck(combinationNode, dstNode);
834 // System.out.println("--");
840 public Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
842 Set<HNode> reachToSet = new HashSet<HNode>();
843 Set<HNode> visited = new HashSet<HNode>();
844 // visited.add(node);
845 recurSkeletonReachTo(node, reachToSet, visited);
848 // if a node reaches to one of elements in the reachToSet, we do not need to keep it
849 // because the node is not directly connected to the combination node
850 // removeRedundantReachToNodes(reachToSet);
855 private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
857 Set<HNode> inSet = getIncomingNodeSet(node);
858 for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
859 HNode inNode = (HNode) iterator.next();
861 if (inNode.isSkeleton()) {
863 reachToSet.add(inNode);
864 } else if (!visited.contains(inNode)) {
866 recurSkeletonReachTo(inNode, reachToSet, visited);
872 public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
873 return mapHNodeToOutgoingSet;
876 public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
877 return mapHNodeToIncomingSet;
880 public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
881 mapHNodeToOutgoingSet.clear();
882 Set<HNode> keySet = in.keySet();
883 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
884 HNode key = (HNode) iterator.next();
885 Set<HNode> inSet = in.get(key);
886 Set<HNode> newSet = new HashSet<HNode>();
887 newSet.addAll(inSet);
888 mapHNodeToOutgoingSet.put(key, newSet);
892 public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
893 mapHNodeToIncomingSet.clear();
894 Set<HNode> keySet = in.keySet();
895 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
896 HNode key = (HNode) iterator.next();
897 Set<HNode> inSet = in.get(key);
898 Set<HNode> newSet = new HashSet<HNode>();
899 newSet.addAll(inSet);
900 mapHNodeToIncomingSet.put(key, newSet);
904 public void setNodeSet(Set<HNode> inSet) {
906 nodeSet.addAll(inSet);
909 public HierarchyGraph clone() {
910 HierarchyGraph clone = new HierarchyGraph();
911 clone.setDesc(getDesc());
912 clone.setName(getName());
913 clone.setNodeSet(getNodeSet());
914 clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
915 clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
916 clone.setMapDescToHNode(getMapDescToHNode());
917 clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
918 clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
919 clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
920 clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
925 public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
926 return mapMergeNodetoMergingSet;
929 public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
930 this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
933 public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
935 if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
936 mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
938 return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
941 public void identifyCombinationNodes() {
943 // 1) set combination node flag if a node combines more than one skeleton node.
944 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
945 HNode node = (HNode) iterator.next();
946 if (!node.isSkeleton()) {
947 Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
948 // Set<HNode> tempSet = removeTransitivelyReachToSet(reachToSet);
949 // reachToSet = removeTransitivelyReachToSet(reachToSet);
950 Set<HNode> tempSet = reachToSet;
951 // System.out.println("$node=" + node + " reachToNodeSet=" + reachToSet + " tempSet="
953 if (reachToSet.size() > 1) {
954 // if (countSkeletonNodes(reachToSet) > 1) {
955 System.out.println("-node=" + node + " reachToSet=" + reachToSet);
956 System.out.println("-set combinationnode=" + node);
957 node.setCombinationNode(true);
958 mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
960 // check if this node is the first node of the chain
961 boolean isFirstNodeOfChain = false;
962 Set<HNode> inNodeSet = getIncomingNodeSet(node);
963 for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
964 HNode inNode = (HNode) iterator2.next();
965 if (inNode.isSkeleton()) {
966 isFirstNodeOfChain = true;
967 } else if (inNode.isCombinationNode()) {
968 Set<HNode> inNodeReachToSet = getSkeleteNodeSetReachTo(inNode);
969 if (!reachToSet.equals(inNodeReachToSet)) {
970 isFirstNodeOfChain = true;
975 if (isFirstNodeOfChain) {
976 node.setDirectCombinationNode(true);
977 addFirstNodeOfChain(reachToSet, node);
978 // System.out.println("IT IS DIRECTLY CONNECTED WITH SC NODES:" + node);
985 // 2) compute the outgoing set that needs to be directly connected from the combination node
986 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
987 HNode node = (HNode) iterator.next();
988 if (node.isCombinationNode()) {
989 Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
990 Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
991 addMapCombineSetToOutgoingSet(combineSet, outSet);
997 public void addFirstNodeOfChain(Set<HNode> combineSet, HNode firstNode) {
999 if (!mapCombineNodeSetToFirstNodeOfChainSet.containsKey(combineSet)) {
1000 mapCombineNodeSetToFirstNodeOfChainSet.put(combineSet, new HashSet<HNode>());
1003 mapCombineNodeSetToFirstNodeOfChainSet.get(combineSet).add(firstNode);
1007 public Set<HNode> getFirstNodeOfCombinationNodeChainSet(Set<HNode> combineNodeSet) {
1008 return mapCombineNodeSetToFirstNodeOfChainSet.get(combineNodeSet);
1011 private Set<HNode> removeTransitivelyReachToSet(Set<HNode> reachToSet) {
1013 Set<HNode> toberemoved = new HashSet<HNode>();
1014 Set<HNode> visited = new HashSet<HNode>();
1015 for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
1016 HNode node = (HNode) iterator.next();
1018 recurIsReachingTo(node, reachToSet, toberemoved, visited);
1021 Set<HNode> rSet = new HashSet<HNode>();
1022 rSet.addAll(reachToSet);
1023 rSet.removeAll(toberemoved);
1027 private void recurIsReachingTo(HNode curNode, Set<HNode> reachToSet, Set<HNode> toberemoved,
1028 Set<HNode> visited) {
1029 Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1031 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1032 HNode inNode = (HNode) iterator.next();
1033 if (reachToSet.contains(inNode)) {
1034 toberemoved.add(inNode);
1035 } else if (!visited.contains(inNode)) {
1036 visited.add(inNode);
1037 recurIsReachingTo(inNode, reachToSet, toberemoved, visited);
1043 public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
1044 return mapCombinationNodeToCombineNodeSet;
1047 public int countSkeletonNodes(Set<HNode> set) {
1050 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
1051 HNode node = (HNode) iterator.next();
1052 Set<Descriptor> descSet = getDescSetOfNode(node);
1053 count += descSet.size();
1059 private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
1060 if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
1061 mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
1063 mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
1066 private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
1067 // the method returns the set of nodes that are reachable from the current node
1068 // and do not combine the same set of skeleton nodes...
1070 Set<HNode> visited = new HashSet<HNode>();
1071 Set<HNode> reachableSet = new HashSet<HNode>();
1072 Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1074 recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
1076 return reachableSet;
1079 private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
1080 Set<HNode> reachableSet, Set<HNode> visited) {
1082 Set<HNode> outSet = getOutgoingNodeSet(node);
1083 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1084 HNode outNode = (HNode) iterator.next();
1086 if (outNode.isCombinationNode()) {
1087 Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
1088 if (combineSetOfOutNode.equals(combineSet)) {
1089 recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
1092 reachableSet.add(outNode);
1094 } else if (outNode.isSkeleton()) {
1095 reachableSet.add(outNode);
1102 private Set<HNode> getReachableNodeSetFrom(HNode node) {
1104 Set<HNode> reachableSet = new HashSet<HNode>();
1105 Set<HNode> visited = new HashSet<HNode>();
1107 recurReachableNodeSetFrom(node, reachableSet, visited);
1109 return reachableSet;
1112 private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
1114 Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
1115 for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
1116 HNode outNode = (HNode) iterator.next();
1117 reachableSet.add(outNode);
1118 if (!visited.contains(outNode)) {
1119 visited.add(outNode);
1120 recurReachableNodeSetFrom(outNode, reachableSet, visited);
1126 public void assignUniqueIndexToNode() {
1128 // System.out.println("nodeSet=" + nodeSet);
1129 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1130 HNode node = (HNode) iterator.next();
1131 mapHNodeToUniqueIndex.put(node, idx);
1135 BASISTOPELEMENT = new HashSet<Integer>();
1136 for (int i = 1; i < idx + 1; i++) {
1137 BASISTOPELEMENT.add(i);
1141 public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
1143 // assign a unique index to a node
1144 assignUniqueIndexToNode();
1146 // compute basis for each node
1147 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1148 HNode node = (HNode) iterator.next();
1150 if (notGenerateSet.contains(node)) {
1151 System.out.println("%%%SKIP =" + node);
1154 Set<Integer> basis = new HashSet<Integer>();
1155 basis.addAll(BASISTOPELEMENT);
1157 Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
1158 // System.out.println("node=" + node + " reachableNodeSet=" + reachableNodeSet);
1159 // System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
1160 // if a node is reachable from the current node
1161 // need to remove the index of the reachable node from the basis
1163 basis.remove(getHNodeIndex(node));
1164 for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1165 HNode reachableNode = (HNode) iterator2.next();
1166 // System.out.println("reachableNode=" + reachableNode);
1167 // System.out.println("getHNodeIndex(reachableNode))="
1168 // + mapHNodeToUniqueIndex.get(reachableNode));
1169 int idx = getHNodeIndex(reachableNode);
1173 mapHNodeToBasis.put(node, basis);
1176 // construct the basis set
1178 BasisSet basisSet = new BasisSet();
1180 Set<HNode> keySet = mapHNodeToBasis.keySet();
1181 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1182 HNode node = (HNode) iterator.next();
1183 Set<Integer> basis = mapHNodeToBasis.get(node);
1184 basisSet.addElement(basis, node);
1191 public int getHNodeIndex(HNode node) {
1192 return mapHNodeToUniqueIndex.get(node).intValue();
1195 public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
1196 return mapHNodeToUniqueIndex;
1199 public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1200 return mapHNodeToBasis;
1203 public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1205 Set<HNode> combinationNodeSet = new HashSet<HNode>();
1206 Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1207 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1208 HNode key = (HNode) iterator.next();
1210 if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1211 combinationNodeSet.add(key);
1215 return combinationNodeSet;
1218 public void writeGraph() {
1222 public void writeGraph(boolean isSimple) {
1224 String graphName = "hierarchy" + name;
1225 graphName = graphName.replaceAll("[\\W]", "");
1228 graphName += "_PAPER";
1231 // System.out.println("***graphName=" + graphName + " node siz=" + nodeSet.size());
1234 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1236 bw.write("digraph " + graphName + " {\n");
1238 Iterator<HNode> iter = nodeSet.iterator();
1240 Set<HNode> addedNodeSet = new HashSet<HNode>();
1242 while (iter.hasNext()) {
1243 HNode u = iter.next();
1245 Set<HNode> outSet = getOutgoingNodeSet(u);
1247 if (outSet.size() == 0) {
1248 if (!addedNodeSet.contains(u)) {
1252 drawNodeName(bw, u);
1254 addedNodeSet.add(u);
1257 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1258 HNode v = (HNode) iterator.next();
1259 if (!addedNodeSet.contains(u)) {
1263 drawNodeName(bw, u);
1265 addedNodeSet.add(u);
1267 if (!addedNodeSet.contains(v)) {
1271 drawNodeName(bw, v);
1273 addedNodeSet.add(v);
1275 bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1284 } catch (IOException e) {
1285 e.printStackTrace();
1289 public boolean contains(HNode node) {
1290 return nodeSet.contains(node);
1293 public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1294 return getOutgoingNodeSet(src).contains(dst);
1297 private String convertMergeSetToString(Set<HNode> mergeSet) {
1299 for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1300 HNode merged = (HNode) iterator.next();
1301 if (merged.isMergeNode()) {
1302 str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1304 str += " " + merged.getName();
1310 private void drawNodeName(BufferedWriter bw, HNode node) throws IOException {
1311 String nodeName = node.getNamePropertyString();
1312 bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1315 private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1317 if (node.isMergeNode()) {
1318 nodeName = node.getNamePropertyString();
1319 Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1320 // System.out.println("node=" + node + " mergeSet=" + mergeSet);
1321 nodeName += ":" + convertMergeSetToString(mergeSet);
1323 nodeName = node.getNamePropertyString();
1325 bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1328 public int countHopFromTopLocation(HNode node) {
1330 Set<HNode> inNodeSet = getIncomingNodeSet(node);
1332 if (inNodeSet.size() > 0) {
1333 count = recurCountHopFromTopLocation(inNodeSet, 1);
1339 private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
1342 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1343 HNode node = (HNode) iterator.next();
1344 Set<HNode> inNodeSet = getIncomingNodeSet(node);
1345 if (inNodeSet.size() > 0) {
1346 int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
1347 if (max < recurCount) {
1355 public int countNonSharedNode(HNode startNode, Set<HNode> endNodeSet) {
1356 System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
1357 return recur_countNonSharedNode(startNode, endNodeSet, 0);
1360 private int recur_countNonSharedNode(HNode startNode, Set<HNode> endNodeSet, int count) {
1362 Set<HNode> inNodeSet = getIncomingNodeSet(startNode);
1364 if (inNodeSet.size() == 0) {
1365 // it is directly connected to the TOP node
1368 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1369 HNode inNode = (HNode) iterator.next();
1370 if (endNodeSet.contains(inNode)) {
1373 if (!inNode.isSharedNode()) {
1376 return recur_countNonSharedNode(inNode, endNodeSet, count);
1380 // System.out.println("startNode=" + startNode + " inNodeSet=" + inNodeSet);
1381 // HNode inNode = inNodeSet.iterator().next();