changes.
[IRC.git] / Robust / src / Analysis / SSJava / HierarchyGraph.java
index 4e7c4b57a6a52e3e6e8c7680d70095be7b49a240..d7900939e6d4d6e4f221838c2113f8177527ce35 100644 (file)
@@ -8,10 +8,10 @@ import java.util.HashSet;
 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 {
 
@@ -369,6 +369,7 @@ public class HierarchyGraph {
           continue;
         }
 
+        // System.out.println("node1=" + node1 + " vs node2=" + node2);
         if (!isEligibleForMerging(node1, node2)) {
           continue;
         }
@@ -378,10 +379,15 @@ public class HierarchyGraph {
           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...
@@ -422,7 +428,7 @@ public class HierarchyGraph {
       }
       return true;
     }
-    return false;
+    return true;
   }
 
   private void addEdgeWithNoCycleCheck(HNode srcHNode, HNode dstHNode) {
@@ -805,11 +811,10 @@ public class HierarchyGraph {
     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="
+      System.out.println("\n@INSERT COMBINATION NODE FOR combineSet=" + combineSet
+          + "  --combinationNode=" + combinationNode);
+      System.out.println("      --hierarchynodes="
           + simpleHierarchyGraph.getCombinationNodeSetByCombineNodeSet(combineSet));
 
       Set<HNode> simpleHNodeSet =
@@ -837,6 +842,14 @@ public class HierarchyGraph {
         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));
+          // }
         }
       }
 
@@ -853,6 +866,7 @@ public class HierarchyGraph {
           srcNode = getHNode(inSkeletonNode.getDescriptor());
         }
         // System.out.println("--srcNode=" + srcNode);
+        System.out.println("     ADD EDGE SRC=" + srcNode + " -> " + combinationNode);
         addEdgeWithNoCycleCheck(srcNode, combinationNode);
       }
 
@@ -879,6 +893,22 @@ public class HierarchyGraph {
 
   }
 
+  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>();
@@ -891,7 +921,9 @@ public class HierarchyGraph {
     // 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) {
@@ -992,8 +1024,18 @@ public class HierarchyGraph {
       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) {
@@ -1397,6 +1439,142 @@ public class HierarchyGraph {
     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);
@@ -1406,6 +1584,31 @@ public class HierarchyGraph {
 
     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
     }
@@ -1418,7 +1621,7 @@ public class HierarchyGraph {
         if (!inNode.isSharedNode()) {
           count++;
         }
-        return recur_countNonSharedNode(inNode, endNodeSet, count);
+        return recur_countNonSharedNode2(inNode, endNodeSet, count);
       }
     }
 
@@ -1426,4 +1629,15 @@ public class HierarchyGraph {
     // 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);
+  }
 }