import java.util.Iterator;
import java.util.Map;
import java.util.Set;
+import java.util.Stack;
import IR.Descriptor;
import IR.FieldDescriptor;
-import IR.VarDescriptor;
public class HierarchyGraph {
Descriptor desc;
+ boolean isSCgraph;
+
String name;
// graph structure
mapNormalNodeToSCNodeReachToSet = new HashMap<HNode, Set<HNode>>();
mapCombineNodeSetToFirstNodeOfChainSet = new HashMap<Set<HNode>, Set<HNode>>();
+
+ isSCgraph = false;
+ }
+
+ public void setSCGraph(boolean in) {
+ isSCgraph = in;
+ }
+
+ public boolean isSCGraph() {
+ return isSCgraph;
}
public Descriptor getDesc() {
continue;
}
+ // System.out.println("node1=" + node1 + " vs node2=" + node2);
if (!isEligibleForMerging(node1, node2)) {
continue;
}
Set<HNode> incomingNodeSet2 = getIncomingNodeSet(node2);
Set<HNode> outgoingNodeSet2 = getOutgoingNodeSet(node2);
+ // System.out.println(node1 + " " + node2 + " MERGING incoming?=" + incomingNodeSet1
+ // + " vs " + incomingNodeSet2);
+ // System.out.println(node1 + " " + node2 + " MERGING outgoing?=" + outgoingNodeSet1
+ // + " vs " + outgoingNodeSet2);
+
if (incomingNodeSet1.equals(incomingNodeSet2)
&& outgoingNodeSet1.equals(outgoingNodeSet2)) {
// need to merge node1 and node2
-
+ // System.out.println("MERGE!!!!!!!!!!!!!");
// ///////////////
// merge two nodes only if every hierarchy graph in the inheritance hierarchy
// that includes both nodes allows the merging of them...
}
return true;
}
- return false;
+ return true;
}
private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
}
public HNode getCombinationNode(Set<HNode> combineSet) {
+ assert isSCGraph();
if (!mapCombineNodeSetToCombinationNode.containsKey(combineSet)) {
String name = "COMB" + (LocationInference.locSeed++);
+ System.out.println("-NEW COMB NODE=" + name);
HNode node = new HNode(name);
node.setCombinationNode(true);
nodeSet.add(node);
Set<Set<HNode>> keySet = simpleHierarchyGraph.getCombineNodeSet();
for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
Set<HNode> combineSet = (Set<HNode>) iterator.next();
- System.out.println("--combineSet=" + combineSet);
HNode combinationNode = getCombinationNode(combineSet);
- System.out.println("--combinationNode=" + combinationNode + " combineSet=" + combineSet);
-
- // System.out.println("--hierarchynodes="
- // + simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet));
+ System.out.println("\n@INSERT COMBINATION NODE FOR combineSet=" + combineSet
+ + " --combinationNode=" + combinationNode);
+ System.out.println(" --hierarchynodes="
+ + simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet));
+
+ Set<HNode> simpleHNodeSet =
+ simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet);
+
+ // check whether a hnode in the simple hierarchy graph is the first node of the chain
+ // if all incoming combination nodes to the hnode have a different combination set from the
+ // hnode, it is the first node of the chain
+ for (Iterator iterator2 = simpleHNodeSet.iterator(); iterator2.hasNext();) {
+ HNode simpleHNode = (HNode) iterator2.next();
+ boolean isFirstNodeOfChain = true;
+ Set<HNode> incomingNodeSet = simpleHierarchyGraph.getIncomingNodeSet(simpleHNode);
+ for (Iterator iterator3 = incomingNodeSet.iterator(); iterator3.hasNext();) {
+ HNode inNode = (HNode) iterator3.next();
+ if (inNode.isCombinationNode()) {
+ Set<HNode> inNodeCombineSet =
+ simpleHierarchyGraph.getCombineSetByCombinationNode(inNode);
+ if (inNodeCombineSet.equals(combineSet)) {
+ isFirstNodeOfChain = false;
+ break;
+ }
+ }
+ }
+ simpleHNode.setDirectCombinationNode(isFirstNodeOfChain);
+ if (isFirstNodeOfChain) {
+ simpleHierarchyGraph.addFirstNodeOfChain(combineSet, simpleHNode);
+ System.out.println("IT IS THE FIRST NODE OF THE CHAIN:" + simpleHNode);
+ // System.out.println("--->INCOMING NODES=");
+ // Set<HNode> inNodeSet = simpleHierarchyGraph.getIncomingNodeSet(simpleHNode);
+ // for (Iterator iterator3 = inNodeSet.iterator(); iterator3.hasNext();) {
+ // HNode inNode = (HNode) iterator3.next();
+ // System.out.println(" inNode=" + inNode + " combineSet="
+ // + simpleHierarchyGraph.getCombineSetByCombinationNode(inNode) + " SKELETON TO SET="
+ // + simpleHierarchyGraph.getSkeleteNodeSetReachTo(inNode));
+ // }
+ }
+ }
// add an edge from a skeleton node to a combination node
for (Iterator iterator2 = combineSet.iterator(); iterator2.hasNext();) {
srcNode = getHNode(inSkeletonNode.getDescriptor());
}
// System.out.println("--srcNode=" + srcNode);
+ System.out.println(" ADD EDGE SRC=" + srcNode + " -> " + combinationNode);
addEdgeWithNoCycleCheck(srcNode, combinationNode);
}
}
+ public Set<HNode> getSkeleteNodeSetReachToNoTransitive(HNode node) {
+
+ Set<HNode> reachToSet = new HashSet<HNode>();
+ Set<HNode> visited = new HashSet<HNode>();
+ // visited.add(node);
+ recurSkeletonReachTo(node, reachToSet, visited);
+
+ // obsolete!
+ // if a node reaches to one of elements in the reachToSet, we do not need to keep it
+ // because the node is not directly connected to the combination node
+ // removeRedundantReachToNodes(reachToSet);
+
+ return removeTransitivelyReachToSet(reachToSet);
+ // return reachToSet;
+ }
+
public Set<HNode> getSkeleteNodeSetReachTo(HNode node) {
Set<HNode> reachToSet = new HashSet<HNode>();
// because the node is not directly connected to the combination node
// removeRedundantReachToNodes(reachToSet);
- return reachToSet;
+ // TODO
+ return removeTransitivelyReachToSet(reachToSet);
+ // return reachToSet;
}
private void recurSkeletonReachTo(HNode node, Set<HNode> reachToSet, Set<HNode> visited) {
return clone;
}
+ public void setMapCombineNodeSetToCombinationNode(Map<Set<HNode>, HNode> in) {
+ mapCombineNodeSetToCombinationNode = in;
+ }
+
public Map<HNode, Set<HNode>> getMapHNodetoMergeSet() {
return mapMergeNodetoMergingSet;
}
if (!node.isSkeleton()) {
Set<HNode> reachToSet = getSkeleteNodeSetReachTo(node);
// Set<HNode> tempSet = removeTransitivelyReachToSet(reachToSet);
+ // System.out.println("ALL REACH SET=" + reachToSet);
// reachToSet = removeTransitivelyReachToSet(reachToSet);
- Set<HNode> tempSet = reachToSet;
+
+ Set<HNode> curReachToSet = new HashSet<HNode>();
+ for (Iterator iterator2 = reachToSet.iterator(); iterator2.hasNext();) {
+ HNode reachSkeletonNode = (HNode) iterator2.next();
+ curReachToSet.add(getCurrentHNode(reachSkeletonNode));
+ }
+
+ // System.out.println("-curReachToSett=" + curReachToSet + " reachToSet=" + reachToSet);
+
+ reachToSet = curReachToSet;
// System.out.println("$node=" + node + " reachToNodeSet=" + reachToSet + " tempSet="
// + tempSet);
if (reachToSet.size() > 1) {
// if (countSkeletonNodes(reachToSet) > 1) {
- System.out.println("-node=" + node + " reachToSet=" + reachToSet);
+ System.out.println("\n-node=" + node + " reachToSet=" + reachToSet);
System.out.println("-set combinationnode=" + node);
node.setCombinationNode(true);
mapCombinationNodeToCombineNodeSet.put(node, reachToSet);
// check if this node is the first node of the chain
- boolean isFirstNodeOfChain = false;
- Set<HNode> inNodeSet = getIncomingNodeSet(node);
- for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
- HNode inNode = (HNode) iterator2.next();
- if (inNode.isSkeleton()) {
- isFirstNodeOfChain = true;
- } else if (inNode.isCombinationNode()) {
- Set<HNode> inNodeReachToSet = getSkeleteNodeSetReachTo(inNode);
- if (!reachToSet.equals(inNodeReachToSet)) {
- isFirstNodeOfChain = true;
- }
- }
- }
-
- if (isFirstNodeOfChain) {
- node.setDirectCombinationNode(true);
- addFirstNodeOfChain(reachToSet, node);
- // System.out.println("IT IS DIRECTLY CONNECTED WITH SC NODES:" + node);
- }
+ // boolean isFirstNodeOfChain = false;
+ // Set<HNode> inNodeSet = getIncomingNodeSet(node);
+ // for (Iterator iterator2 = inNodeSet.iterator(); iterator2.hasNext();) {
+ // HNode inNode = (HNode) iterator2.next();
+ // if (inNode.isSkeleton()) {
+ // isFirstNodeOfChain = true;
+ // } else if (inNode.isCombinationNode()) {
+ // Set<HNode> inNodeReachToSet = getSkeleteNodeSetReachTo(inNode);
+ // if (!reachToSet.equals(inNodeReachToSet)) {
+ // isFirstNodeOfChain = true;
+ // }
+ // }
+ // }
+ //
+ // if (isFirstNodeOfChain) {
+ // node.setDirectCombinationNode(true);
+ // addFirstNodeOfChain(reachToSet, node);
+ // }
}
}
return max;
}
+ public Stack<String> computeDistance2(HNode startNode, Set<HNode> endNodeSet,
+ HierarchyGraph scGraph, Set<HNode> combineSet) {
+ System.out
+ .println("#####computeDistanceance startNode=" + startNode + " endNode=" + endNodeSet);
+ Stack<String> trace = new Stack<String>();
+ return recur_computeDistance2(startNode, endNodeSet, scGraph, 0, combineSet, trace);
+ }
+
+ public Stack<String> computeDistance(HNode startNode, Set<HNode> endNodeSet,
+ HierarchyGraph scGraph, Set<HNode> combineSet) {
+ System.out
+ .println("#####computeDistanceance startNode=" + startNode + " endNode=" + endNodeSet);
+ Stack<String> trace = new Stack<String>();
+ return recur_computeDistance(startNode, endNodeSet, 0, combineSet, trace);
+ }
+
+ private Stack<String> recur_computeDistance(HNode curNode, Set<HNode> endNodeSet, int count,
+ Set<HNode> combineSet, Stack<String> trace) {
+
+ if (!curNode.isSkeleton()) {
+ if (curNode.isSharedNode()) {
+ trace.add("S");
+ } else {
+ trace.add("N");
+ }
+ }
+
+ if (endNodeSet.contains(curNode)) {
+ // it reaches to one of endNodeSet
+ return trace;
+ }
+
+ Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
+
+ int curMaxDistance = 0;
+ Stack<String> curMaxTrace = (Stack<String>) trace.clone();
+ ;
+ for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+ HNode inNode = (HNode) iterator.next();
+ // traverse more...
+
+ if (inNode.isCombinationNode() && combineSet != null) {
+ // check if inNode have the same combination set of the starting node
+ Set<HNode> inNodeCombineSet = getCombineSetByCombinationNode(inNode);
+ if (!inNodeCombineSet.equals(combineSet)) {
+ continue;
+ }
+ }
+
+ // System.out.println(" traverse more to" + inNode + " before-trace=" + trace);
+ Stack<String> newTrace = (Stack<String>) trace.clone();
+ Stack<String> curTrace =
+ recur_computeDistance(inNode, endNodeSet, count, combineSet, newTrace);
+ // System.out.println("curTracerTrace=" + curTrace);
+
+ if (curTrace != null && curTrace.size() > curMaxDistance) {
+ curMaxTrace = curTrace;
+ curMaxDistance = curTrace.size();
+ }
+ }
+ return curMaxTrace;
+
+ }
+
+ private Stack<String> recur_computeDistance2(HNode curNode, Set<HNode> endNodeSet,
+ HierarchyGraph scGraph, int count, Set<HNode> combineSet, Stack<String> trace) {
+
+ if (!curNode.isSkeleton()) {
+ if (curNode.isSharedNode()) {
+ trace.add("S");
+ } else {
+ trace.add("N");
+ }
+ }
+
+ System.out.println(" curNode=" + curNode + " curTrace=" + trace);
+ // System.out.println(" curNode=" + curNode + " curSCNode="
+ // + scGraph.getCurrentHNode(curNode) + " contains="
+ // + endNodeSet.contains(scGraph.getCurrentHNode(curNode)));
+ if (endNodeSet.contains(scGraph.getCurrentHNode(curNode))) {
+ // it reaches to one of endNodeSet
+ return trace;
+ }
+
+ Set<HNode> inNodeSet = getIncomingNodeSet(curNode);
+
+ int curMaxDistance = 0;
+ Stack<String> curMaxTrace = (Stack<String>) trace.clone();
+ ;
+ for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+ HNode inNode = (HNode) iterator.next();
+ // traverse more...
+
+ if (inNode.isCombinationNode() && combineSet != null) {
+ // check if inNode have the same combination set of the starting node
+ Set<HNode> inNodeCombineSet = getCombineSetByCombinationNode(inNode);
+ if (!inNodeCombineSet.equals(combineSet)) {
+ continue;
+ }
+ }
+
+ // Stack<String> newTrace = (Stack<String>) trace.clone();
+ // Stack<String> curTrace =
+ // recur_computeDistance(inNode, endNodeSet, scGraph, count, combineSet, newTrace);
+ // if (curTrace != null) {
+ // return curTrace;
+ // }
+
+ Set<HNode> inReachToNodeSet = getSkeleteNodeSetReachToNoTransitive(inNode);
+ Set<HNode> inCurReachToNodeSet = new HashSet<HNode>();
+ for (Iterator iterator2 = inReachToNodeSet.iterator(); iterator2.hasNext();) {
+ HNode aboveNode = (HNode) iterator2.next();
+ inCurReachToNodeSet.add(getCurrentHNode(aboveNode));
+ }
+
+ if (combineSet != null || inCurReachToNodeSet.equals(endNodeSet)) {
+ System.out
+ .println(" traverse to incomingNode=" + inNode + " before-trace=" + trace);
+
+ Stack<String> newTrace = (Stack<String>) trace.clone();
+ Stack<String> curTrace =
+ recur_computeDistance2(inNode, endNodeSet, scGraph, count, combineSet, newTrace);
+
+ if (curTrace != null && curTrace.size() > curMaxDistance) {
+ curMaxTrace = curTrace;
+ curMaxDistance = curTrace.size();
+ }
+ } else {
+ System.out.println("NOT TRAVERSE a new inNode=" + inNode + " inReachToNodeSet="
+ + inCurReachToNodeSet);
+ }
+
+ }
+ return curMaxTrace;
+ }
+
public int countNonSharedNode(HNode startNode, Set<HNode> endNodeSet) {
System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
return recur_countNonSharedNode(startNode, endNodeSet, 0);
Set<HNode> inNodeSet = getIncomingNodeSet(startNode);
+ for (Iterator iterator = inNodeSet.iterator(); iterator.hasNext();) {
+ HNode inNode = (HNode) iterator.next();
+ if (endNodeSet.contains(inNode)) {
+ count++;
+ return count;
+ } else {
+ if (!inNode.isSharedNode()) {
+ count++;
+ }
+ return recur_countNonSharedNode2(inNode, endNodeSet, count);
+ }
+ }
+
+ return 0;
+ }
+
+ public int countNonSharedNode2(HNode startNode, Set<HNode> endNodeSet) {
+ System.out.println("countNonSharedNode startNode=" + startNode + " endNode=" + endNodeSet);
+ return recur_countNonSharedNode2(startNode, endNodeSet, 0);
+ }
+
+ private int recur_countNonSharedNode2(HNode startNode, Set<HNode> endNodeSet, int count) {
+
+ Set<HNode> inNodeSet = getIncomingNodeSet(startNode);
+
if (inNodeSet.size() == 0) {
// it is directly connected to the TOP node
}
if (!inNode.isSharedNode()) {
count++;
}
- return recur_countNonSharedNode(inNode, endNodeSet, count);
+ return recur_countNonSharedNode2(inNode, endNodeSet, count);
}
}
// HNode inNode = inNodeSet.iterator().next();
return -1;
}
+
+ public void removeIsolatedNodes() {
+ Set<HNode> toberemoved = new HashSet<HNode>();
+ for (Iterator iterator = nodeSet.iterator(); iterator.hasNext();) {
+ HNode node = (HNode) iterator.next();
+ if (getIncomingNodeSet(node).isEmpty() && getOutgoingNodeSet(node).isEmpty()) {
+ toberemoved.add(node);
+ }
+ }
+ nodeSet.removeAll(toberemoved);
+ }
}
projects / IRC.git / blobdiff