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;
43 // for the lattice generation
44 Map<HNode, Integer> mapHNodeToUniqueIndex;
45 Map<HNode, Set<Integer>> mapHNodeToBasis;
46 Set<Integer> BASISTOPELEMENT;
48 public HierarchyGraph() {
49 mapHNodeToIncomingSet = new HashMap<HNode, Set<HNode>>();
50 mapHNodeToOutgoingSet = new HashMap<HNode, Set<HNode>>();
51 mapHNodeToDescSet = new HashMap<HNode, Set<Descriptor>>();
52 mapDescToHNode = new HashMap<Descriptor, HNode>();
53 mapSkeletonNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
54 mapCombinationNodeToCombineNodeSet = new HashMap<HNode, Set<HNode>>();
55 mapCombineNodeSetToOutgoingNodeSet = new HashMap<Set<HNode>, Set<HNode>>();
56 mapCombineNodeSetToCombinationNode = new HashMap<Set<HNode>, HNode>();
57 nodeSet = new HashSet<HNode>();
59 mapHNodeToUniqueIndex = new HashMap<HNode, Integer>();
60 mapHNodeToBasis = new HashMap<HNode, Set<Integer>>();
62 mapMergeNodetoMergingSet = new HashMap<HNode, Set<HNode>>();
64 mapHNodeToCurrentHNode = new HashMap<HNode, HNode>();
66 mapHNodeNameToCurrentHNode = new HashMap<String, HNode>();
68 mapNormalNodeToSCNodeReachToSet = new HashMap<HNode, Set<HNode>>();
71 public Descriptor getDesc() {
75 public void setDesc(Descriptor desc) {
79 public String getName() {
83 public void setName(String name) {
87 public HierarchyGraph(Descriptor d) {
93 public Map<HNode, Set<Descriptor>> getMapHNodeToDescSet() {
94 return mapHNodeToDescSet;
97 public void setMapHNodeToDescSet(Map<HNode, Set<Descriptor>> map) {
98 mapHNodeToDescSet.putAll(map);
101 public Map<HNode, HNode> getMapHNodeToCurrentHNode() {
102 return mapHNodeToCurrentHNode;
105 public Map<String, HNode> getMapHNodeNameToCurrentHNode() {
106 return mapHNodeNameToCurrentHNode;
109 public void setMapHNodeToCurrentHNode(Map<HNode, HNode> mapHNodeToCurrentHNode) {
110 this.mapHNodeToCurrentHNode = mapHNodeToCurrentHNode;
113 public void setMapHNodeNameToCurrentHNode(Map<String, HNode> mapHNodeNameToCurrentHNode) {
114 this.mapHNodeNameToCurrentHNode = mapHNodeNameToCurrentHNode;
117 public Map<Descriptor, HNode> getMapDescToHNode() {
118 return mapDescToHNode;
121 public void setMapDescToHNode(Map<Descriptor, HNode> map) {
122 mapDescToHNode.putAll(map);
125 public Set<HNode> getNodeSet() {
129 public void addEdge(HNode srcHNode, HNode dstHNode) {
131 if (!nodeSet.contains(srcHNode)) {
132 nodeSet.add(srcHNode);
135 if (!nodeSet.contains(dstHNode)) {
136 nodeSet.add(dstHNode);
139 Set<HNode> possibleCycleSet = getPossibleCycleNodes(srcHNode, dstHNode);
141 if (possibleCycleSet.size() > 0) {
143 if (possibleCycleSet.size() == 1) {
144 System.out.println("possibleCycleSet=" + possibleCycleSet + " from src=" + srcHNode
145 + " dstHNode=" + dstHNode);
146 if (dstHNode.isSharedNode()) {
147 // it has already been assigned shared node.
149 dstHNode.setSharedNode(true);
150 System.out.println("$$$setShared=" + dstHNode);
155 System.out.println("--- CYCLIC VALUE FLOW: " + srcHNode + " -> " + dstHNode);
156 HNode newMergeNode = mergeNodes(possibleCycleSet, false);
157 newMergeNode.setSharedNode(true);
160 getIncomingNodeSet(dstHNode).add(srcHNode);
161 getOutgoingNodeSet(srcHNode).add(dstHNode);
162 // System.out.println("add an edge " + srcHNode + " -> " + dstHNode);
167 public void addNode(HNode node) {
171 public void addEdge(Descriptor src, Descriptor dst) {
173 if (src.equals(LocationInference.LITERALDESC)) {
174 // in this case, we do not need to add a source hnode
175 // just add a destination hnode
178 HNode srcHNode = getHNode(src);
179 HNode dstHNode = getHNode(dst);
180 addEdge(srcHNode, dstHNode);
185 public void setParamHNode(Descriptor d) {
186 getHNode(d).setSkeleton(true);
189 public HNode getHNode(Descriptor d) {
190 if (!mapDescToHNode.containsKey(d)) {
191 HNode newNode = new HNode(d);
193 if (d instanceof FieldDescriptor) {
194 newNode.setSkeleton(true);
197 if (d.equals(LocationInference.TOPDESC)) {
198 newNode.setSkeleton(true);
201 String symbol = d.getSymbol();
202 if (symbol.startsWith(LocationInference.PCLOC) || symbol.startsWith(LocationInference.RLOC)) {
203 newNode.setSkeleton(true);
206 mappingDescriptorToHNode(d, newNode);
207 nodeSet.add(newNode);
209 return mapDescToHNode.get(d);
212 public HNode getHNode(String name) {
213 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
214 HNode node = (HNode) iterator.next();
215 if (node.getName().equals(name)) {
222 private void mappingDescriptorToHNode(Descriptor desc, HNode node) {
223 mapDescToHNode.put(desc, node);
224 if (!mapHNodeToDescSet.containsKey(node)) {
225 mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
227 mapHNodeToDescSet.get(node).add(desc);
230 public HierarchyGraph generateSkeletonGraph() {
232 // compose a skeleton graph that only consists of fields or parameters
233 HierarchyGraph skeletonGraph = new HierarchyGraph(desc);
234 skeletonGraph.setName(desc + "_SKELETON");
236 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
237 HNode src = (HNode) iterator.next();
238 if (src.isSkeleton()) {
239 Set<HNode> reachSet = getDirectlyReachSkeletonSet(src);
240 if (reachSet.size() > 0) {
241 for (Iterator iterator2 = reachSet.iterator(); iterator2.hasNext();) {
242 HNode dst = (HNode) iterator2.next();
243 skeletonGraph.addEdge(src, dst);
246 skeletonGraph.addNode(src);
251 skeletonGraph.setMapDescToHNode(getMapDescToHNode());
252 skeletonGraph.setMapHNodeToDescSet(getMapHNodeToDescSet());
253 skeletonGraph.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
254 skeletonGraph.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
255 skeletonGraph.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
257 return skeletonGraph;
261 private Set<HNode> getDirectlyReachSkeletonSet(HNode node) {
263 Set<HNode> visited = new HashSet<HNode>();
264 Set<HNode> connected = new HashSet<HNode>();
265 recurReachSkeletonSet(node, connected, visited);
270 public void removeRedundantEdges() {
272 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
273 HNode src = (HNode) iterator.next();
274 Set<HNode> connectedSet = getOutgoingNodeSet(src);
275 Set<HNode> toberemovedSet = new HashSet<HNode>();
276 for (Iterator iterator2 = connectedSet.iterator(); iterator2.hasNext();) {
277 HNode dst = (HNode) iterator2.next();
278 Set<HNode> otherNeighborSet = new HashSet<HNode>();
279 otherNeighborSet.addAll(connectedSet);
280 otherNeighborSet.remove(dst);
281 for (Iterator iterator3 = otherNeighborSet.iterator(); iterator3.hasNext();) {
282 HNode neighbor = (HNode) iterator3.next();
283 if (reachTo(neighbor, dst, new HashSet<HNode>())) {
284 toberemovedSet.add(dst);
288 if (toberemovedSet.size() > 0) {
289 connectedSet.removeAll(toberemovedSet);
291 for (Iterator iterator2 = toberemovedSet.iterator(); iterator2.hasNext();) {
292 HNode node = (HNode) iterator2.next();
293 getIncomingNodeSet(node).remove(src);
301 public void simplifyHierarchyGraph(LocationInference infer) {
302 removeRedundantEdges();
303 combineRedundantNodes(false, infer);
306 public void combineRedundantNodes(boolean onlyCombinationNodes, LocationInference infer) {
307 // Combine field/parameter nodes who have the same set of incoming/outgoing edges.
308 boolean isUpdated = false;
310 isUpdated = combineTwoRedundatnNodes(onlyCombinationNodes, infer);
314 public Set<HNode> getIncomingNodeSet(HNode node) {
315 if (!mapHNodeToIncomingSet.containsKey(node)) {
316 mapHNodeToIncomingSet.put(node, new HashSet<HNode>());
318 return mapHNodeToIncomingSet.get(node);
321 public Set<HNode> getOutgoingNodeSet(HNode node) {
322 if (!mapHNodeToOutgoingSet.containsKey(node)) {
323 mapHNodeToOutgoingSet.put(node, new HashSet<HNode>());
325 return mapHNodeToOutgoingSet.get(node);
328 private boolean combineTwoRedundatnNodes(boolean onlyCombinationNodes, LocationInference infer) {
329 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
330 HNode node1 = (HNode) iterator.next();
332 if ((onlyCombinationNodes && (!node1.isCombinationNode()))
333 || (!onlyCombinationNodes && (!node1.isSkeleton()))) {
337 Set<HNode> incomingNodeSet1 = getIncomingNodeSet(node1);
338 Set<HNode> outgoingNodeSet1 = getOutgoingNodeSet(node1);
340 for (Iterator iterator2 = nodeSet.iterator(); iterator2.hasNext();) {
341 HNode node2 = (HNode) iterator2.next();
343 if ((onlyCombinationNodes && (!node2.isCombinationNode()))
344 || (!onlyCombinationNodes && (!node2.isSkeleton()))) {
348 if (!isEligibleForMerging(node1, node2)) {
352 if (!node1.equals(node2)) {
354 Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
355 Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
357 if (incomingNodeSet1.equals(incomingNodeSet2)
358 && outgoingNodeSet1.equals(outgoingNodeSet2)) {
359 // need to merge node1 and node2
362 // merge two nodes only if every hierarchy graph in the inheritance hierarchy
363 // that includes both nodes allows the merging of them...
364 Set<HNode> mergeSet = new HashSet<HNode>();
367 infer.isValidMergeInheritanceCheck(desc, mergeSet);
371 mergeNodes(mergeSet, onlyCombinationNodes);
382 private boolean isEligibleForMerging(HNode node1, HNode node2) {
384 if (node1.isSharedNode() || node2.isSharedNode()) {
386 // if either of nodes is a shared node,
387 // all descriptors of node1 & node2 should have a primitive type
389 Set<Descriptor> descSet = new HashSet<Descriptor>();
390 descSet.addAll(getDescSetOfNode(node1));
391 descSet.addAll(getDescSetOfNode(node2));
393 for (Iterator iterator = descSet.iterator(); iterator.hasNext();) {
394 Descriptor desc = (Descriptor) iterator.next();
395 if (!LocationInference.isPrimitive(desc)) {
404 private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
405 getIncomingNodeSet(dstHNode).add(srcHNode);
406 getOutgoingNodeSet(srcHNode).add(dstHNode);
407 // System.out.println("addEdgeWithNoCycleCheck src=" + srcHNode + " -> " + dstHNode);
410 private HNode mergeNodes(Set<HNode> set, boolean onlyCombinationNodes) {
412 Set<HNode> incomingNodeSet = new HashSet<HNode>();
413 Set<HNode> outgoingNodeSet = new HashSet<HNode>();
415 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
416 HNode node = (HNode) iterator.next();
417 incomingNodeSet.addAll(getIncomingNodeSet(node));
418 outgoingNodeSet.addAll(getOutgoingNodeSet(node));
422 boolean isMergeNode = false;
423 if (onlyCombinationNodes) {
424 nodeName = "Comb" + (LocationInference.locSeed++);
426 nodeName = "Node" + (LocationInference.locSeed++);
429 HNode newMergeNode = new HNode(nodeName);
430 newMergeNode.setMergeNode(isMergeNode);
432 nodeSet.add(newMergeNode);
433 nodeSet.removeAll(set);
435 // if the input set contains a skeleton node, need to set a new merge node as skeleton also
436 boolean hasSkeleton = false;
437 boolean hasShared = false;
438 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
439 HNode inNode = (HNode) iterator.next();
440 if (inNode.isSkeleton()) {
443 if (inNode.isSharedNode()) {
447 // System.out.println("-----Set merging node=" + newMergeNode + " as a skeleton=" + set
448 // + " hasSkeleton=" + hasSkeleton + " CUR DESC=" + desc);
449 newMergeNode.setSkeleton(hasSkeleton);
450 newMergeNode.setSharedNode(hasShared);
452 System.out.println("-----MERGING NODE=" + set + " new node=" + newMergeNode);
454 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
455 HNode node = (HNode) iterator.next();
456 Set<Descriptor> descSetOfNode = getDescSetOfNode(node);
457 for (Iterator iterator2 = descSetOfNode.iterator(); iterator2.hasNext();) {
458 Descriptor desc = (Descriptor) iterator2.next();
459 mappingDescriptorToHNode(desc, newMergeNode);
463 for (Iterator iterator = incomingNodeSet.iterator(); iterator.hasNext();) {
464 HNode inNode = (HNode) iterator.next();
465 Set<HNode> outSet = getOutgoingNodeSet(inNode);
466 outSet.removeAll(set);
467 if (!set.contains(inNode)) {
468 addEdgeWithNoCycleCheck(inNode, newMergeNode);
472 for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
473 HNode outNode = (HNode) iterator.next();
474 Set<HNode> inSet = getIncomingNodeSet(outNode);
475 inSet.removeAll(set);
476 if (!set.contains(outNode)) {
477 addEdgeWithNoCycleCheck(newMergeNode, outNode);
481 Set<HNode> mergedSkeletonNode = new HashSet<HNode>();
482 for (Iterator<HNode> iter = set.iterator(); iter.hasNext();) {
483 HNode merged = iter.next();
484 if (merged.isSkeleton()) {
485 mergedSkeletonNode.add(merged);
489 // mapMergeNodetoMergingSet.put(newMergeNode, mergedSkeletonNode);
490 // for (Iterator iterator = set.iterator(); iterator.hasNext();) {
491 mapMergeNodetoMergingSet.put(newMergeNode, set);
492 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
493 HNode mergedNode = (HNode) iterator.next();
494 addMapHNodeToCurrentHNode(mergedNode, newMergeNode);
497 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
498 HNode hNode = (HNode) iterator.next();
499 System.out.println("old=" + hNode + "----->newNode=" + getCurrentHNode(hNode));
502 System.out.println();
507 private void addMapHNodeToCurrentHNode(HNode curNode, HNode newNode) {
509 if (curNode.isMergeNode()) {
510 Set<HNode> mergingSet = getMergingSet(curNode);
511 mergingSet.add(curNode);
512 System.out.println("-------addMapHNodeToCurrentHNode curNode=" + curNode + " meringSet="
513 + mergingSet + " newNode=" + newNode);
514 for (Iterator iterator = mergingSet.iterator(); iterator.hasNext();) {
515 HNode mergingNode = (HNode) iterator.next();
516 mapHNodeToCurrentHNode.put(mergingNode, newNode);
517 mapHNodeNameToCurrentHNode.put(mergingNode.getName(), newNode);
520 mapHNodeToCurrentHNode.put(curNode, newNode);
521 mapHNodeNameToCurrentHNode.put(curNode.getName(), newNode);
526 public HNode getCurrentHNode(HNode node) {
527 if (!mapHNodeToCurrentHNode.containsKey(node)) {
528 mapHNodeToCurrentHNode.put(node, node);
530 return mapHNodeToCurrentHNode.get(node);
533 public HNode getCurrentHNode(String nodeName) {
534 return mapHNodeNameToCurrentHNode.get(nodeName);
537 private Set<HNode> getMergingSet(HNode mergeNode) {
538 Set<HNode> mergingSet = new HashSet<HNode>();
539 Set<HNode> mergedNode = mapMergeNodetoMergingSet.get(mergeNode);
540 for (Iterator iterator = mergedNode.iterator(); iterator.hasNext();) {
541 HNode node = (HNode) iterator.next();
542 if (node.isMergeNode()) {
543 mergingSet.add(node);
544 mergingSet.addAll(getMergingSet(node));
546 mergingSet.add(node);
552 public Set<Descriptor> getDescSetOfNode(HNode node) {
553 if (!mapHNodeToDescSet.containsKey(node)) {
554 mapHNodeToDescSet.put(node, new HashSet<Descriptor>());
556 return mapHNodeToDescSet.get(node);
559 private boolean reachTo(HNode src, HNode dst, Set<HNode> visited) {
560 Set<HNode> connectedSet = getOutgoingNodeSet(src);
561 for (Iterator<HNode> iterator = connectedSet.iterator(); iterator.hasNext();) {
562 HNode n = iterator.next();
566 if (!visited.contains(n)) {
568 if (reachTo(n, dst, visited)) {
576 private void recurReachSkeletonSet(HNode node, Set<HNode> connected, Set<HNode> visited) {
578 Set<HNode> outSet = getOutgoingNodeSet(node);
579 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
580 HNode outNode = (HNode) iterator.next();
582 if (outNode.isSkeleton()) {
583 connected.add(outNode);
584 } else if (!visited.contains(outNode)) {
585 visited.add(outNode);
586 recurReachSkeletonSet(outNode, connected, visited);
592 public Set<HNode> getReachableSCNodeSet(HNode startNode) {
593 // returns the set of hnodes which is reachable from the startNode and is either SC node or a
594 // node which is directly connected to the SC nodes
595 Set<HNode> reachable = new HashSet<HNode>();
596 Set<HNode> visited = new HashSet<HNode>();
597 visited.add(startNode);
598 recurReachableNodeSet(startNode, visited, reachable);
602 public Set<HNode> getSCNodeReachToSet(HNode node) {
603 if (!mapNormalNodeToSCNodeReachToSet.containsKey(node)) {
604 mapNormalNodeToSCNodeReachToSet.put(node, new HashSet<HNode>());
606 return mapNormalNodeToSCNodeReachToSet.get(node);
609 private void recurReachableNodeSet(HNode node, Set<HNode> visited, Set<HNode> reachable) {
611 Set<HNode> outSet = getOutgoingNodeSet(node);
612 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
613 HNode out = (HNode) iterator.next();
615 if (!visited.contains(out)) {
617 Set<HNode> reachableFromSCNodeSet = reachableFromSCNode(out);
618 mapNormalNodeToSCNodeReachToSet.put(out, reachableFromSCNodeSet);
619 if (out.isSkeleton() || out.isCombinationNode() || reachableFromSCNodeSet.size() > 0) {
623 recurReachableNodeSet(out, visited, reachable);
632 private Set<HNode> reachableFromSCNode(HNode node) {
633 Set<HNode> visited = new HashSet<HNode>();
635 Set<HNode> reachable = new HashSet<HNode>();
636 recurReachableFromSCNode(node, reachable, visited);
640 private void recurReachableFromSCNode(HNode node, Set<HNode> reachable, Set<HNode> visited) {
641 Set<HNode> inNodeSet = getIncomingNodeSet(node);
642 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
643 HNode inNode = (HNode) iterator.next();
644 if (inNode.isSkeleton() || inNode.isCombinationNode()) {
646 reachable.add(inNode);
647 } else if (!visited.contains(inNode)) {
649 recurReachableFromSCNode(inNode, reachable, visited);
654 public Set<HNode> getDirectlyReachableSkeletonCombinationNodeFrom(HNode node,
655 Set<HNode> combinationNodeSet) {
656 Set<HNode> reachable = new HashSet<HNode>();
657 Set<HNode> visited = new HashSet<HNode>();
659 recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited, reachable, combinationNodeSet);
663 public void recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited,
664 Set<HNode> reachable, Set<HNode> combinationNodeSet) {
666 Set<HNode> outSet = getOutgoingNodeSet(node);
667 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
668 HNode out = (HNode) iterator.next();
670 if (!visited.contains(out)) {
672 if (out.isSkeleton()) {
674 } else if (out.isCombinationNode()) {
675 if (combinationNodeSet == null) {
677 } else if (!combinationNodeSet.contains(out)) {
680 recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
684 recurDirectlyReachableSkeletonCombinationNodeFrom(out, visited, reachable,
694 public HNode getDirectlyReachableSkeletonCombinationNodeFrom(HNode node) {
695 Set<HNode> visited = new HashSet<HNode>();
696 return recurDirectlyReachableSkeletonCombinationNodeFrom(node, visited);
699 public HNode recurDirectlyReachableSkeletonCombinationNodeFrom(HNode node, Set<HNode> visited) {
701 Set<HNode> outSet = getOutgoingNodeSet(node);
702 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
703 HNode out = (HNode) iterator.next();
704 // if (!visited.contains(out)) {
705 if (out.isCombinationNode() || out.isSkeleton()) {
709 return getDirectlyReachableSkeletonCombinationNodeFrom(out);
717 public Set<HNode> getPossibleCycleNodes(HNode src, HNode dst) {
718 // if an edge from src to dst introduces a new cycle flow,
719 // the method returns the set of elements consisting of the cycle
720 Set<HNode> cycleNodeSet = new HashSet<HNode>();
721 // if the dst node reaches to the src node, the new relation
722 // introduces a cycle to the lattice
723 if (dst.equals(src)) {
724 cycleNodeSet.add(dst);
725 cycleNodeSet.add(src);
726 } else if (reachTo(dst, src)) {
727 cycleNodeSet.add(dst);
728 cycleNodeSet.add(src);
729 getInBetweenElements(dst, src, cycleNodeSet);
734 private void getInBetweenElements(HNode start, HNode end, Set<HNode> nodeSet) {
735 Set<HNode> connectedSet = getOutgoingNodeSet(start);
736 for (Iterator iterator = connectedSet.iterator(); iterator.hasNext();) {
737 HNode cur = (HNode) iterator.next();
738 if ((!start.equals(cur)) && (!cur.equals(end)) && reachTo(cur, end)) {
740 getInBetweenElements(cur, end, nodeSet);
745 public boolean reachTo(HNode node1, HNode node2) {
746 return reachTo(node1, node2, new HashSet<HNode>());
749 public Set<HNode> getCombineSetByCombinationNode(HNode node) {
750 if (!mapCombinationNodeToCombineNodeSet.containsKey(node)) {
751 mapCombinationNodeToCombineNodeSet.put(node, new HashSet<HNode>());
753 return mapCombinationNodeToCombineNodeSet.get(node);
756 public HNode getCombinationNode(Set<HNode> combineSet) {
757 if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
758 String name = "COMB" + (LocationInference.locSeed++);
759 HNode node = new HNode(name);
760 node.setCombinationNode(true);
762 mapCombineNodeSetToCombinationNode.put(combineSet, node);
763 mapCombinationNodeToCombineNodeSet.put(node, combineSet);
766 return mapCombineNodeSetToCombinationNode.get(combineSet);
769 public Map<Set<HNode>, HNode> getMapCombineNodeSetToCombinationNode() {
770 return mapCombineNodeSetToCombinationNode;
773 public Set<Set<HNode>> getCombineNodeSet() {
774 return mapCombineNodeSetToOutgoingNodeSet.keySet();
777 public void insertCombinationNodesToGraph(HierarchyGraph simpleHierarchyGraph) {
778 // add a new combination node where parameter/field flows are actually combined.
780 simpleHierarchyGraph.identifyCombinationNodes();
782 Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
783 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
784 Set<HNode> combineSet = (Set<HNode>) iterator.next();
785 // System.out.println("--combineSet=" + combineSet);
786 HNode combinationNode = getCombinationNode(combineSet);
787 System.out.println("--combinationNode=" + combinationNode + " combineSet=" + combineSet);
789 System.out.println("--hierarchynodes="
790 + simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet));
791 // add an edge from a skeleton node to a combination node
792 for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
793 HNode inSkeletonNode = (HNode) iterator2.next();
794 // System.out.println("--inSkeletonNode=" + inSkeletonNode + " desc="
795 // + inSkeletonNode.getDescriptor());
797 if (inSkeletonNode.getDescriptor() == null) {
798 // the node is merging one...
799 srcNode = inSkeletonNode;
801 srcNode = getHNode(inSkeletonNode.getDescriptor());
803 // System.out.println("--srcNode=" + srcNode);
804 addEdgeWithNoCycleCheck(srcNode, combinationNode);
807 // add an edge from the combination node to outgoing nodes
808 Set<HNode> outSet = simpleHierarchyGraph.getOutgoingNodeSetByCombineSet(combineSet);
809 for (Iterator iterator2 = outSet.iterator(); iterator2.hasNext();) {
810 HNode curNode = (HNode) iterator2.next();
811 if (curNode.isCombinationNode()) {
812 Set<HNode> combineNode = simpleHierarchyGraph.getCombineSetByCombinationNode(curNode);
813 HNode outNode = getCombinationNode(combineNode);
814 addEdgeWithNoCycleCheck(combinationNode, outNode);
815 } else if (curNode.isSkeleton()) {
816 // HNode dstNode2 = getHNode(curNode.getDescriptor());
817 HNode dstNode = getCurrentHNode(curNode);
818 // System.out.println("-----curNode=" + curNode + "------->" + dstNode + " dstNode2="
820 addEdgeWithNoCycleCheck(combinationNode, dstNode);
824 System.out.println("--");
830 private void addCombinationNode(HNode curNode, Set<HNode> reachToSet, Set<HNode> reachableSet) {
831 if (!mapSkeletonNodeSetToCombinationNode.containsKey(reachToSet)) {
832 // need to create a new combination node
833 String nodeName = "Comb" + (LocationInference.locSeed++);
834 HNode newCombinationNode = new HNode(nodeName);
835 newCombinationNode.setCombinationNode(true);
837 nodeSet.add(newCombinationNode);
838 mapSkeletonNodeSetToCombinationNode.put(reachToSet, newCombinationNode);
840 for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
841 HNode reachToNode = (HNode) iterator.next();
842 addEdge(reachToNode, newCombinationNode);
847 HNode combinationNode = mapSkeletonNodeSetToCombinationNode.get(reachToSet);
848 for (Iterator iterator = reachableSet.iterator(); iterator.hasNext();) {
849 HNode reachableNode = (HNode) iterator.next();
850 addEdge(combinationNode, reachableNode);
855 private Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
857 Set<HNode> reachToSet = new HashSet<HNode>();
858 Set<HNode> visited = new HashSet<HNode>();
859 // visited.add(node);
860 recurSkeletonReachTo(node, reachToSet, visited);
863 // if a node reaches to one of elements in the reachToSet, we do not need to keep it
864 // because the node is not directly connected to the combination node
865 // removeRedundantReachToNodes(reachToSet);
870 private void removeRedundantReachToNodes(Set<HNode> reachToSet) {
872 Set<HNode> toberemoved = new HashSet<HNode>();
873 for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
874 HNode cur = (HNode) iterator.next();
876 for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
877 HNode dst = (HNode) iterator2.next();
878 if (!cur.equals(dst) && reachTo(cur, dst)) {
880 toberemoved.add(cur);
884 reachToSet.removeAll(toberemoved);
887 private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
889 Set<HNode> inSet = getIncomingNodeSet(node);
890 for (Iterator iterator = inSet.iterator(); iterator.hasNext();) {
891 HNode inNode = (HNode) iterator.next();
893 if (inNode.isSkeleton()) {
895 reachToSet.add(inNode);
896 } else if (!visited.contains(inNode)) {
898 recurSkeletonReachTo(inNode, reachToSet, visited);
904 public Map<HNode, Set<HNode>> getMapHNodeToOutgoingSet() {
905 return mapHNodeToOutgoingSet;
908 public Map<HNode, Set<HNode>> getMapHNodeToIncomingSet() {
909 return mapHNodeToIncomingSet;
912 public void setMapHNodeToOutgoingSet(Map<HNode, Set<HNode>> in) {
913 mapHNodeToOutgoingSet.clear();
914 Set<HNode> keySet = in.keySet();
915 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
916 HNode key = (HNode) iterator.next();
917 Set<HNode> inSet = in.get(key);
918 Set<HNode> newSet = new HashSet<HNode>();
919 newSet.addAll(inSet);
920 mapHNodeToOutgoingSet.put(key, newSet);
924 public void setMapHNodeToIncomingSet(Map<HNode, Set<HNode>> in) {
925 mapHNodeToIncomingSet.clear();
926 Set<HNode> keySet = in.keySet();
927 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
928 HNode key = (HNode) iterator.next();
929 Set<HNode> inSet = in.get(key);
930 Set<HNode> newSet = new HashSet<HNode>();
931 newSet.addAll(inSet);
932 mapHNodeToIncomingSet.put(key, newSet);
936 public void setNodeSet(Set<HNode> inSet) {
938 nodeSet.addAll(inSet);
941 public HierarchyGraph clone() {
942 HierarchyGraph clone = new HierarchyGraph();
943 clone.setDesc(getDesc());
944 clone.setName(getName());
945 clone.setNodeSet(getNodeSet());
946 clone.setMapHNodeToIncomingSet(getMapHNodeToIncomingSet());
947 clone.setMapHNodeToOutgoingSet(getMapHNodeToOutgoingSet());
948 clone.setMapDescToHNode(getMapDescToHNode());
949 clone.setMapHNodeToDescSet(getMapHNodeToDescSet());
950 clone.setMapHNodetoMergeSet(getMapHNodetoMergeSet());
951 clone.setMapHNodeToCurrentHNode(getMapHNodeToCurrentHNode());
952 clone.setMapHNodeNameToCurrentHNode(getMapHNodeNameToCurrentHNode());
957 public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
958 return mapMergeNodetoMergingSet;
961 public void setMapHNodetoMergeSet(Map<HNode, Set<HNode>> mapHNodetoMergeSet) {
962 this.mapMergeNodetoMergingSet = mapHNodetoMergeSet;
965 public Set<HNode> getOutgoingNodeSetByCombineSet(Set<HNode> combineSet) {
967 if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
968 mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
970 return mapCombineNodeSetToOutgoingNodeSet.get(combineSet);
973 public void identifyCombinationNodes() {
975 // 1) set combination node flag if a node combines more than one skeleton node.
976 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
977 HNode node = (HNode) iterator.next();
978 if (!node.isSkeleton()) {
979 Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
980 // Set<HNode> tempSet = removeTransitivelyReachToSet(reachToSet);
981 // reachToSet = removeTransitivelyReachToSet(reachToSet);
982 Set<HNode> tempSet = reachToSet;
983 System.out.println("$node=" + node + " reachToNodeSet=" + reachToSet + " tempSet="
985 if (reachToSet.size() > 1) {
986 // if (countSkeletonNodes(reachToSet) > 1) {
987 System.out.println("-node=" + node + " reachToSet=" + reachToSet);
988 System.out.println("-set combinationnode=" + node);
989 node.setCombinationNode(true);
990 mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
995 // 2) compute the outgoing set that needs to be directly connected from the combination node
996 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
997 HNode node = (HNode) iterator.next();
998 if (node.isCombinationNode()) {
999 Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1000 Set<HNode> outSet = getDirectlyReachableNodeSetFromCombinationNode(node);
1001 addMapCombineSetToOutgoingSet(combineSet, outSet);
1007 private Set<HNode> removeTransitivelyReachToSet(Set<HNode> reachToSet) {
1009 Set<HNode> toberemoved = new HashSet<HNode>();
1010 Set<HNode> visited = new HashSet<HNode>();
1011 for (Iterator iterator = reachToSet.iterator(); iterator.hasNext();) {
1012 HNode node = (HNode) iterator.next();
1014 recurIsReachingTo(node, reachToSet, toberemoved, visited);
1017 Set<HNode> rSet = new HashSet<HNode>();
1018 rSet.addAll(reachToSet);
1019 rSet.removeAll(toberemoved);
1023 private void recurIsReachingTo(HNode curNode, Set<HNode> reachToSet, Set<HNode> toberemoved,
1024 Set<HNode> visited) {
1025 Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
1027 for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
1028 HNode inNode = (HNode) iterator.next();
1029 if (reachToSet.contains(inNode)) {
1030 toberemoved.add(inNode);
1031 } else if (!visited.contains(inNode)) {
1032 visited.add(inNode);
1033 recurIsReachingTo(inNode, reachToSet, toberemoved, visited);
1039 public Map<HNode, Set<HNode>> getMapCombinationNodeToCombineNodeSet() {
1040 return mapCombinationNodeToCombineNodeSet;
1043 public int countSkeletonNodes(Set<HNode> set) {
1046 for (Iterator iterator = set.iterator(); iterator.hasNext();) {
1047 HNode node = (HNode) iterator.next();
1048 Set<Descriptor> descSet = getDescSetOfNode(node);
1049 count += descSet.size();
1055 private void addMapCombineSetToOutgoingSet(Set<HNode> combineSet, Set<HNode> outSet) {
1056 if (!mapCombineNodeSetToOutgoingNodeSet.containsKey(combineSet)) {
1057 mapCombineNodeSetToOutgoingNodeSet.put(combineSet, new HashSet<HNode>());
1059 mapCombineNodeSetToOutgoingNodeSet.get(combineSet).addAll(outSet);
1062 private Set<HNode> getDirectlyReachableNodeSetFromCombinationNode(HNode node) {
1063 // the method returns the set of nodes that are reachable from the current node
1064 // and do not combine the same set of skeleton nodes...
1066 Set<HNode> visited = new HashSet<HNode>();
1067 Set<HNode> reachableSet = new HashSet<HNode>();
1068 Set<HNode> combineSet = mapCombinationNodeToCombineNodeSet.get(node);
1070 recurDirectlyReachableNodeSetFromCombinationNode(node, combineSet, reachableSet, visited);
1072 return reachableSet;
1075 private void recurDirectlyReachableNodeSetFromCombinationNode(HNode node, Set<HNode> combineSet,
1076 Set<HNode> reachableSet, Set<HNode> visited) {
1078 Set<HNode> outSet = getOutgoingNodeSet(node);
1079 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1080 HNode outNode = (HNode) iterator.next();
1082 if (outNode.isCombinationNode()) {
1083 Set<HNode> combineSetOfOutNode = mapCombinationNodeToCombineNodeSet.get(outNode);
1084 if (combineSetOfOutNode.equals(combineSet)) {
1085 recurDirectlyReachableNodeSetFromCombinationNode(outNode, combineSet, reachableSet,
1088 reachableSet.add(outNode);
1090 } else if (outNode.isSkeleton()) {
1091 reachableSet.add(outNode);
1098 private Set<HNode> getReachableNodeSetFrom(HNode node) {
1100 Set<HNode> reachableSet = new HashSet<HNode>();
1101 Set<HNode> visited = new HashSet<HNode>();
1103 recurReachableNodeSetFrom(node, reachableSet, visited);
1105 return reachableSet;
1108 private void recurReachableNodeSetFrom(HNode node, Set<HNode> reachableSet, Set<HNode> visited) {
1110 Set<HNode> outgoingNodeSet = getOutgoingNodeSet(node);
1111 for (Iterator iterator = outgoingNodeSet.iterator(); iterator.hasNext();) {
1112 HNode outNode = (HNode) iterator.next();
1113 reachableSet.add(outNode);
1114 if (!visited.contains(outNode)) {
1115 visited.add(outNode);
1116 recurReachableNodeSetFrom(outNode, reachableSet, visited);
1122 public void assignUniqueIndexToNode() {
1124 // System.out.println("nodeSet=" + nodeSet);
1125 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1126 HNode node = (HNode) iterator.next();
1127 mapHNodeToUniqueIndex.put(node, idx);
1131 BASISTOPELEMENT = new HashSet<Integer>();
1132 for (int i = 1; i < idx + 1; i++) {
1133 BASISTOPELEMENT.add(i);
1137 public BasisSet computeBasisSet(Set<HNode> notGenerateSet) {
1139 // assign a unique index to a node
1140 assignUniqueIndexToNode();
1142 // compute basis for each node
1143 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1144 HNode node = (HNode) iterator.next();
1146 if (notGenerateSet.contains(node)) {
1147 System.out.println("%%%SKIP =" + node);
1150 Set<Integer> basis = new HashSet<Integer>();
1151 basis.addAll(BASISTOPELEMENT);
1153 Set<HNode> reachableNodeSet = getReachableNodeSetFrom(node);
1154 // System.out.println("node=" + node + " reachableNodeSet=" + reachableNodeSet);
1155 // System.out.println("mapHNodeToUniqueIndex.get(node)=" + mapHNodeToUniqueIndex.get(node));
1156 // if a node is reachable from the current node
1157 // need to remove the index of the reachable node from the basis
1159 basis.remove(getHNodeIndex(node));
1160 for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) {
1161 HNode reachableNode = (HNode) iterator2.next();
1162 // System.out.println("reachableNode=" + reachableNode);
1163 // System.out.println("getHNodeIndex(reachableNode))="
1164 // + mapHNodeToUniqueIndex.get(reachableNode));
1165 int idx = getHNodeIndex(reachableNode);
1169 mapHNodeToBasis.put(node, basis);
1172 // construct the basis set
1174 BasisSet basisSet = new BasisSet();
1176 Set<HNode> keySet = mapHNodeToBasis.keySet();
1177 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1178 HNode node = (HNode) iterator.next();
1179 Set<Integer> basis = mapHNodeToBasis.get(node);
1180 basisSet.addElement(basis, node);
1187 public int getHNodeIndex(HNode node) {
1188 return mapHNodeToUniqueIndex.get(node).intValue();
1191 public Map<HNode, Integer> getMapHNodeToUniqueIndex() {
1192 return mapHNodeToUniqueIndex;
1195 public Map<HNode, Set<Integer>> getMapHNodeToBasis() {
1196 return mapHNodeToBasis;
1199 public Set<HNode> getCombinationNodeSetByCombineNodeSet(Set<HNode> combineSkeletonNodeSet) {
1201 Set<HNode> combinationNodeSet = new HashSet<HNode>();
1202 Set<HNode> keySet = mapCombinationNodeToCombineNodeSet.keySet();
1203 for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1204 HNode key = (HNode) iterator.next();
1206 if (mapCombinationNodeToCombineNodeSet.get(key).equals(combineSkeletonNodeSet)) {
1207 combinationNodeSet.add(key);
1211 return combinationNodeSet;
1214 public void writeGraph() {
1218 public void writeGraph(boolean isSimple) {
1220 String graphName = "hierarchy" + name;
1221 graphName = graphName.replaceAll("[\\W]", "");
1224 graphName += "_PAPER";
1227 // System.out.println("***graphName=" + graphName + " node siz=" + nodeSet.size());
1230 BufferedWriter bw = new BufferedWriter(new FileWriter(graphName + ".dot"));
1232 bw.write("digraph " + graphName + " {\n");
1234 Iterator<HNode> iter = nodeSet.iterator();
1236 Set<HNode> addedNodeSet = new HashSet<HNode>();
1238 while (iter.hasNext()) {
1239 HNode u = iter.next();
1241 Set<HNode> outSet = getOutgoingNodeSet(u);
1243 if (outSet.size() == 0) {
1244 if (!addedNodeSet.contains(u)) {
1248 drawNodeName(bw, u);
1250 addedNodeSet.add(u);
1253 for (Iterator iterator = outSet.iterator(); iterator.hasNext();) {
1254 HNode v = (HNode) iterator.next();
1255 if (!addedNodeSet.contains(u)) {
1259 drawNodeName(bw, u);
1261 addedNodeSet.add(u);
1263 if (!addedNodeSet.contains(v)) {
1267 drawNodeName(bw, v);
1269 addedNodeSet.add(v);
1271 bw.write("" + u.getName() + " -> " + v.getName() + ";\n");
1280 } catch (IOException e) {
1281 e.printStackTrace();
1285 public boolean contains(HNode node) {
1286 return nodeSet.contains(node);
1289 public boolean isDirectlyConnectedTo(HNode src, HNode dst) {
1290 return getOutgoingNodeSet(src).contains(dst);
1293 private String convertMergeSetToString(Set<HNode> mergeSet) {
1295 for (Iterator iterator = mergeSet.iterator(); iterator.hasNext();) {
1296 HNode merged = (HNode) iterator.next();
1297 if (merged.isMergeNode()) {
1298 str += " " + convertMergeSetToString(mapMergeNodetoMergingSet.get(merged));
1300 str += " " + merged.getName();
1306 private void drawNodeName(BufferedWriter bw, HNode node) throws IOException {
1307 String nodeName = node.getNamePropertyString();
1308 bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1311 private void drawNode(BufferedWriter bw, HNode node) throws IOException {
1313 if (node.isMergeNode()) {
1314 nodeName = node.getNamePropertyString();
1315 Set<HNode> mergeSet = mapMergeNodetoMergingSet.get(node);
1316 System.out.println("node=" + node + " mergeSet=" + mergeSet);
1317 nodeName += ":" + convertMergeSetToString(mergeSet);
1319 nodeName = node.getNamePropertyString();
1321 bw.write(node.getName() + " [label=\"" + nodeName + "\"]" + ";\n");
1324 public int countHopFromTopLocation(HNode node) {
1326 Set<HNode> inNodeSet = getIncomingNodeSet(node);
1328 if (inNodeSet.size() > 0) {
1329 count = recurCountHopFromTopLocation(inNodeSet, 1);
1335 private int recurCountHopFromTopLocation(Set<HNode> nodeSet, int curCount) {
1338 for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
1339 HNode node = (HNode) iterator.next();
1340 Set<HNode> inNodeSet = getIncomingNodeSet(node);
1341 if (inNodeSet.size() > 0) {
1342 int recurCount = recurCountHopFromTopLocation(inNodeSet, curCount + 1);
1343 if (max < recurCount) {