Checking in code to perform safety checks on repair dependency graph.

[repair.git] / Repair / RepairCompiler / MCC / IR / GraphNode.java

diff --git a/Repair/RepairCompiler/MCC/IR/GraphNode.java b/Repair/RepairCompiler/MCC/IR/GraphNode.java
index da50a5abd882785cdcddcad1bfae2c8655598fe9..eab969124c546d50472d840635950ed79de42dc9 100755 (executable)
--- a/Repair/RepairCompiler/MCC/IR/GraphNode.java
+++ b/Repair/RepairCompiler/MCC/IR/GraphNode.java
@@ -83,7 +83,7 @@ public class GraphNode {
         return owner;
     }
 
-    public static void computeclosure(Set nodes) {
+    public static void computeclosure(Set nodes, Set removed) {
        Stack tovisit=new Stack();
        tovisit.addAll(nodes);
        while(!tovisit.isEmpty()) {
@@ -92,8 +92,11 @@ public class GraphNode {
                Edge edge=(Edge)it.next();
                GraphNode target=edge.getTarget();
                if (!nodes.contains(target)) {
-                   nodes.add(target);
-                   tovisit.push(target);
+                   if ((removed!=null)&&
+                       (!removed.contains(target))) {
+                       nodes.add(target);
+                       tovisit.push(target);
+                   }
                }
            }
        }
@@ -144,13 +147,13 @@ public class GraphNode {
     }
 
     public void discover(int time) {
-        discoverytime = time++;
+        discoverytime = time;
         status = PROCESSING;
     }
 
     public void finish(int time) {
         assert status == PROCESSING;
-        finishingtime = time++;
+        finishingtime = time;
         status = FINISHED;
     }
 
@@ -158,6 +161,7 @@ public class GraphNode {
         return finishingtime;
     }
 
+
     public static class DOTVisitor {
         
         java.io.PrintWriter output;
@@ -194,19 +198,22 @@ public class GraphNode {
                          output.println("\tremincross=true;");*/
             output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
             output.println("\tedge [fontsize=6];");
-
             traverse();
-
             output.println("}\n");
         }
                 
         private void traverse() {            
+           Set cycleset=GraphNode.findcycles(nodes);
+
             Iterator i = nodes.iterator();
             while (i.hasNext()) {
                 GraphNode gn = (GraphNode) i.next();
                 Iterator edges = gn.edges();
                 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
-                output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + "];");
+               String option="";
+               if (cycleset.contains(gn))
+                   option=",style=bold";
+                output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
 
                 while (edges.hasNext()) {
                     Edge edge = (Edge) edges.next();
@@ -219,6 +226,49 @@ public class GraphNode {
             }
         }
     }
+
+    /* XXXXXXXX  Should use SCC algorithm here - will change */
+    public static Set findcycles(Collection nodes) {
+       Stack st=new Stack();
+       HashSet acyclic=new HashSet();
+       HashSet cycles=new HashSet();
+       for(Iterator it=nodes.iterator();it.hasNext();) {
+           GraphNode node=(GraphNode)it.next();
+           if (acyclic.contains(node))
+               continue;
+           if (cycles.contains(node))
+               continue;
+           findcycles(cycles, acyclic, st,node,nodes);
+       }
+       return cycles;
+    }
+
+    private static boolean findcycles(Set cycles, Set acyclic, Stack visited, GraphNode gn, Collection nodes) {
+       if (visited.contains(gn)) {/* Found cycle */
+           cycles.addAll(visited.subList(visited.indexOf(gn),visited.size()));  /* Add this cycle */
+           return true;
+       }
+       boolean acyclicflag=true;
+       visited.push(gn);
+       for(Iterator it=gn.edges();it.hasNext();) {
+           Edge e=(Edge) it.next();
+           GraphNode node = e.getTarget();
+           if (!nodes.contains(node))
+               continue; /* Don't visit stuff outside set */
+           if (acyclic.contains(node))
+               continue;
+           if (findcycles(cycles,acyclic,visited,node,nodes)) {
+               /* Found cycle */
+               acyclicflag=false;
+           }
+       }
+       visited.pop();
+       if (acyclicflag) {
+           acyclic.add(gn); /* no cycles through gn */
+           return false;
+       } else
+           return true; /* found cycle */
+    }
     
     /**
      * DFS encapsulates the depth first search algorithm 
@@ -232,19 +282,19 @@ public class GraphNode {
             this.nodes = nodes;
         }
 
-        public static void depthFirstSearch(Collection nodes) {
+        public static boolean depthFirstSearch(Collection nodes) {
             if (nodes == null) {
                 throw new NullPointerException();
             }
             
             DFS dfs = new DFS(nodes);
-            dfs.go();
+            return dfs.go();
         }
 
-        private void go() {           
+        private boolean go() {           
             Iterator i;
             time = 0;
-            
+            boolean acyclic=true;
             i = nodes.iterator();
             while (i.hasNext()) {
                 GraphNode gn = (GraphNode) i.next();
@@ -254,27 +304,36 @@ public class GraphNode {
             i = nodes.iterator();
             while (i.hasNext()) {
                 GraphNode gn = (GraphNode) i.next();
-                assert gn.getStatus() != PROCESSING;                    
+               assert gn.getStatus() != PROCESSING;                    
                 if (gn.getStatus() == UNVISITED) {
-                    dfs(gn);
+                    if (!dfs(gn))
+                       acyclic=false;
                 } 
             }
+           return acyclic;
         }
 
-        private void dfs(GraphNode gn) {
+        private boolean dfs(GraphNode gn) {
+           boolean acyclic=true;
             gn.discover(time++);            
             Iterator edges = gn.edges();
 
             while (edges.hasNext()) {
                 Edge edge = (Edge) edges.next();
                 GraphNode node = edge.getTarget();
+               if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
+                   continue;
                 if (node.getStatus() == UNVISITED) {
-                    dfs(node);
-                }
+                    if (!dfs(node))
+                       acyclic=false;
+                } else if (node.getStatus()==PROCESSING) {
+                   acyclic=false;
+               }
             }
 
             gn.finish(time++);
-        }                        
+           return acyclic;
+        }
 
     } /* end DFS */