X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=Repair%2FRepairCompiler%2FMCC%2FIR%2FGraphNode.java;h=80d34a9a5ac626a786e6c2fcc5a2212b1ed73834;hb=15be88521357bb3abffcd7273d7c9779daa53f1f;hp=da50a5abd882785cdcddcad1bfae2c8655598fe9;hpb=0ddd66cf596f161886dc67214f3fb2e19f6f7168;p=repair.git

diff --git a/Repair/RepairCompiler/MCC/IR/GraphNode.java b/Repair/RepairCompiler/MCC/IR/GraphNode.java
index da50a5a..80d34a9 100755
--- a/Repair/RepairCompiler/MCC/IR/GraphNode.java
+++ b/Repair/RepairCompiler/MCC/IR/GraphNode.java
@@ -2,13 +2,12 @@ package MCC.IR;
 
 import java.util.*;
 import java.io.*;
+import MCC.Compiler;
 
 public class GraphNode {
 
-    public static boolean useEdgeLabels;
-
     /* NodeStatus enumeration pattern ***********/
-    
+
     public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED");
     public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING");
     public static final NodeStatus FINISHED = new NodeStatus("FINISHED");
@@ -22,9 +21,10 @@ public class GraphNode {
     /* Edge *****************/
 
     public static class Edge {
-        
+
         private String label;
         private GraphNode target;
+	private GraphNode source;
         private String dotnodeparams = new String();
 
         public Edge(String label, GraphNode target) {
@@ -36,6 +36,14 @@ public class GraphNode {
             return label;
         }
 
+	public void setSource(GraphNode s) {
+	    this.source=s;
+	}
+
+	public GraphNode getSource() {
+	    return source;
+	}
+
         public GraphNode getTarget() {
             return target;
         }
@@ -55,12 +63,24 @@ public class GraphNode {
 
     int discoverytime = -1;
     int finishingtime = -1; /* used for searches */
-    Vector edges = new Vector();  
+
+    Vector edges = new Vector();
+    Vector inedges = new Vector();
     String nodelabel;
     String textlabel;
-    NodeStatus status = UNVISITED;    
+    NodeStatus status = UNVISITED;
     String dotnodeparams = new String();
     Object owner = null;
+    boolean merge=false;
+    String nodeoption="";
+
+    public void setOption(String option) {
+	this.nodeoption=","+option;
+    }
+
+    public void setMerge() {
+	merge=true;
+    }
 
     public GraphNode(String label) {
         this.nodelabel = label;
@@ -83,7 +103,7 @@ public class GraphNode {
         return owner;
     }
 
-    public static void computeclosure(Set nodes) {
+    public static void computeclosure(Collection nodes, Collection removed) {
 	Stack tovisit=new Stack();
 	tovisit.addAll(nodes);
 	while(!tovisit.isEmpty()) {
@@ -92,10 +112,37 @@ 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);
+		    }
+		}
+	    }
+	}
+    }
+
+    public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
+	Stack tovisit=new Stack();
+	Stack newvisit=new Stack();
+	tovisit.addAll(nodes);
+	for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
+	    while(!tovisit.isEmpty()) {
+		GraphNode gn=(GraphNode)tovisit.pop();
+		for(Iterator it=gn.edges();it.hasNext();) {
+		    Edge edge=(Edge)it.next();
+		    GraphNode target=edge.getTarget();
+		    if (!nodes.contains(target)) {
+			if ((removed==null)||
+			    (!removed.contains(target))) {
+			    nodes.add(target);
+			    newvisit.push(target);
+			}
+		    }
 		}
 	    }
+	    tovisit=newvisit;
+	    newvisit=new Stack();
 	}
     }
 
@@ -109,7 +156,7 @@ public class GraphNode {
             dotnodeparams = new String();
         }
     }
-    
+
     public void setStatus(NodeStatus status) {
         if (status == null) {
             throw new NullPointerException();
@@ -124,7 +171,7 @@ public class GraphNode {
     public String getTextLabel() {
         return textlabel;
     }
-    
+
     public NodeStatus getStatus() {
         return this.status;
     }
@@ -133,57 +180,76 @@ public class GraphNode {
         return edges.iterator();
     }
 
+    public Iterator inedges() {
+        return inedges.iterator();
+    }
+
     public void addEdge(Edge newedge) {
+	newedge.setSource(this);
         edges.addElement(newedge);
+	GraphNode tonode=newedge.getTarget();
+	tonode.inedges.addElement(newedge);
+    }
+
+    void reset() {
+	    discoverytime = -1;
+	    finishingtime = -1;
+	    status = UNVISITED;
     }
 
-    public void reset() {
-        discoverytime = -1;
-        finishingtime = -1;
-        status = UNVISITED;
+    void resetscc() {
+	status = UNVISITED;
     }
 
-    public void discover(int time) {
-        discoverytime = time++;
-        status = PROCESSING;
+    void discover(int time) {
+	discoverytime = time;
+	status = PROCESSING;
     }
 
-    public void finish(int time) {
+    void finish(int time) {
         assert status == PROCESSING;
-        finishingtime = time++;
+	finishingtime = time;
         status = FINISHED;
     }
 
+    /** Returns finishing time for dfs */
+
     public int getFinishingTime() {
-        return finishingtime;
+	return finishingtime;
     }
 
+
     public static class DOTVisitor {
-        
+
         java.io.PrintWriter output;
         int tokennumber;
         int color;
-      
+
         private DOTVisitor(java.io.OutputStream output) {
             tokennumber = 0;
             color = 0;
             this.output = new java.io.PrintWriter(output, true);
         }
-        
+
         private String getNewID(String name) {
             tokennumber = tokennumber + 1;
             return new String (name+tokennumber);
         }
 
         Collection nodes;
-        
+	Collection special;
+
         public static void visit(java.io.OutputStream output, Collection nodes) {
+	    visit(output,nodes,null);
+	}
+
+        public static void visit(java.io.OutputStream output, Collection nodes, Collection special) {
             DOTVisitor visitor = new DOTVisitor(output);
+	    visitor.special=special;
             visitor.nodes = nodes;
             visitor.make();
-
         }
-        
+
         private void make() {
             output.println("digraph dotvisitor {");
             output.println("\trotate=90;");
@@ -194,87 +260,236 @@ 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() {            
+
+        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=gn.nodeoption;
+		if (special!=null&&special.contains(gn))
+		    option+=",shape=box";
+		if (!gn.merge)
+                    output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
 
+		if (!gn.merge)
                 while (edges.hasNext()) {
                     Edge edge = (Edge) edges.next();
                     GraphNode node = edge.getTarget();
 		    if (nodes.contains(node)) {
-			String edgelabel = useEdgeLabels ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
-			output.println("\t" + gn.getLabel() + " -> " + node.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
+			for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
+			    GraphNode node2=(GraphNode)nodeit.next();
+			    String edgelabel = Compiler.DEBUGGRAPH ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
+			    output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
+			}
 		    }
                 }
             }
         }
+
+	Set nonmerge(GraphNode gn) {
+	    HashSet newset=new HashSet();
+	    HashSet toprocess=new HashSet();
+	    toprocess.add(gn);
+	    while(!toprocess.isEmpty()) {
+		GraphNode gn2=(GraphNode)toprocess.iterator().next();
+		toprocess.remove(gn2);
+		if (!gn2.merge)
+		    newset.add(gn2);
+		else {
+		    Iterator edges = gn2.edges();
+		    while (edges.hasNext()) {
+			Edge edge = (Edge) edges.next();
+			GraphNode node = edge.getTarget();
+			if (!newset.contains(node)&&nodes.contains(node))
+			    toprocess.add(node);
+		    }
+		}
+	    }
+	    return newset;
+	}
+
+    }
+
+    /** This function returns the set of nodes involved in cycles.
+     *	It only considers cycles containing nodes in the set 'nodes'.
+    */
+    public static Set findcycles(Collection nodes) {
+	HashSet cycleset=new HashSet();
+	SCC scc=DFS.computeSCC(nodes);
+	if (!scc.hasCycles())
+	    return cycleset;
+	for(int i=0;i<scc.numSCC();i++) {
+	    if (scc.hasCycle(i))
+		cycleset.addAll(scc.getSCC(i));
+	}
+	return cycleset;
+    }
+
+    public static class SCC {
+	boolean acyclic;
+	HashMap map,revmap;
+	int numscc;
+	public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
+	    this.acyclic=acyclic;
+	    this.map=map;
+	    this.revmap=revmap;
+	    this.numscc=numscc;
+	}
+
+	/** Returns whether the graph has any cycles */
+	public boolean hasCycles() {
+	    return !acyclic;
+	}
+
+	/** Returns the number of Strongly Connected Components */
+	public int numSCC() {
+	    return numscc;
+	}
+
+	/** Returns the strongly connected component number for the GraphNode gn*/
+	public int getComponent(GraphNode gn) {
+	    return ((Integer)revmap.get(gn)).intValue();
+	}
+
+	/** Returns the set of nodes in the strongly connected component i*/
+	public Set getSCC(int i) {
+	    Integer scc=new Integer(i);
+	    return (Set)map.get(scc);
+	}
+
+	/** Returns whether the strongly connected component i contains a cycle */
+	boolean hasCycle(int i) {
+	    Integer scc=new Integer(i);
+	    Set s=(Set)map.get(scc);
+	    if (s.size()>1)
+		return true;
+	    Object [] array=s.toArray();
+	    GraphNode gn=(GraphNode)array[0];
+	    for(Iterator it=gn.edges();it.hasNext();) {
+		Edge e=(Edge)it.next();
+		if (e.getTarget()==gn)
+		    return true; /* Self Cycle */
+	    }
+	    return false;
+	}
     }
-    
+
     /**
-     * DFS encapsulates the depth first search algorithm 
+     * DFS encapsulates the depth first search algorithm
      */
     public static class DFS {
 
         int time = 0;
+	int sccindex = 0;
         Collection nodes;
+	Vector finishingorder=null;
+	HashMap sccmap;
+	HashMap sccmaprev;
 
-        private DFS(Collection nodes) { 
+        private DFS(Collection nodes) {
             this.nodes = nodes;
         }
+	/** Calculates the strong connected components for the graph composed
+	 *  of the set of nodes 'nodes'*/
+	public static SCC computeSCC(Collection nodes) {
+	    if (nodes==null) {
+		throw new NullPointerException();
+	    }
+	    DFS dfs=new DFS(nodes);
+	    dfs.sccmap=new HashMap();
+	    dfs.sccmaprev=new HashMap();
+	    dfs.finishingorder=new Vector();
+	    boolean acyclic=dfs.go();
+            for (Iterator it = nodes.iterator();it.hasNext();) {
+                GraphNode gn = (GraphNode) it.next();
+                gn.resetscc();
+            }
+	    for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
+		GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
+		if (gn.getStatus() == UNVISITED) {
+		    dfs.dfsprev(gn);
+		    dfs.sccindex++; /* Increment scc index */
+		}
+	    }
+	    return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
+	}
 
-        public static void depthFirstSearch(Collection nodes) {
+	void dfsprev(GraphNode gn) {
+	    if (gn.getStatus()==FINISHED||!nodes.contains(gn))
+		return;
+	    gn.setStatus(FINISHED);
+	    Integer i=new Integer(sccindex);
+	    if (!sccmap.containsKey(i))
+		sccmap.put(i,new HashSet());
+	    ((Set)sccmap.get(i)).add(gn);
+	    sccmaprev.put(gn,i);
+	    for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
+		Edge e=(Edge)edgeit.next();
+		GraphNode gn2=e.getSource();
+		dfsprev(gn2);
+	    }
+	}
+
+        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();
-                gn.reset();            
-            }            
+                gn.reset();
+            }
 
             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) {
-            gn.discover(time++);            
+        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;
+		}
             }
-
+	    if (finishingorder!=null)
+		finishingorder.add(gn);
             gn.finish(time++);
-        }                        
+	    return acyclic;
+        }
 
     } /* end DFS */