Replaced findcycles method with something more efficient based on SCC computation.
[repair.git] / Repair / RepairCompiler / MCC / IR / GraphNode.java
1 package MCC.IR;
2
3 import java.util.*;
4 import java.io.*;
5
6 public class GraphNode {
7
8     public static boolean useEdgeLabels;
9
10     /* NodeStatus enumeration pattern ***********/
11     
12     public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED");
13     public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING");
14     public static final NodeStatus FINISHED = new NodeStatus("FINISHED");
15
16     public static class NodeStatus {
17         private static String name;
18         private NodeStatus(String name) { this.name = name; }
19         public String toString() { return name; }
20     }
21
22     /* Edge *****************/
23
24     public static class Edge {
25         
26         private String label;
27         private GraphNode target;
28         private GraphNode source;
29         private String dotnodeparams = new String();
30
31         public Edge(String label, GraphNode target) {
32             this.label = label;
33             this.target = target;
34         }
35
36         public String getLabel() {
37             return label;
38         }
39
40         public void setSource(GraphNode s) {
41             this.source=s;
42         }
43
44         public GraphNode getSource() {
45             return source;
46         }
47
48         public GraphNode getTarget() {
49             return target;
50         }
51
52         public void setDotNodeParameters(String param) {
53             if (param == null) {
54                 throw new NullPointerException();
55             }
56             if (param.length() > 0) {
57                 dotnodeparams = "," + param;
58             } else {
59                 dotnodeparams = new String();
60             }
61         }
62
63     }
64
65     int discoverytime = -1;
66     int finishingtime = -1; /* used for searches */
67
68     Vector edges = new Vector();  
69     Vector inedges = new Vector();
70     String nodelabel;
71     String textlabel;
72     NodeStatus status = UNVISITED;    
73     String dotnodeparams = new String();
74     Object owner = null;
75
76     public GraphNode(String label) {
77         this.nodelabel = label;
78         this.textlabel = label;
79     }
80
81     public GraphNode(String label, Object owner) {
82         this.nodelabel = label;
83         this.textlabel = label;
84         this.owner = owner;
85     }
86
87     public GraphNode(String label, String textlabel, Object owner) {
88         this.nodelabel = label;
89         this.textlabel = textlabel;
90         this.owner = owner;
91     }
92
93     public Object getOwner() {
94         return owner;
95     }
96
97     public static void computeclosure(Collection nodes, Collection removed) {
98         Stack tovisit=new Stack();
99         tovisit.addAll(nodes);
100         while(!tovisit.isEmpty()) {
101             GraphNode gn=(GraphNode)tovisit.pop();
102             for(Iterator it=gn.edges();it.hasNext();) {
103                 Edge edge=(Edge)it.next();
104                 GraphNode target=edge.getTarget();
105                 if (!nodes.contains(target)) {
106                     if ((removed==null)||
107                         (!removed.contains(target))) {
108                         nodes.add(target);
109                         tovisit.push(target);
110                     }
111                 }
112             }
113         }
114     }
115
116     public void setDotNodeParameters(String param) {
117         if (param == null) {
118             throw new NullPointerException();
119         }
120         if (param.length() > 0) {
121             dotnodeparams = "," + param;
122         } else {
123             dotnodeparams = new String();
124         }
125     }
126     
127     public void setStatus(NodeStatus status) {
128         if (status == null) {
129             throw new NullPointerException();
130         }
131         this.status = status;
132     }
133
134     public String getLabel() {
135         return nodelabel;
136     }
137
138     public String getTextLabel() {
139         return textlabel;
140     }
141     
142     public NodeStatus getStatus() {
143         return this.status;
144     }
145
146     public Iterator edges() {
147         return edges.iterator();
148     }
149
150     public Iterator inedges() {
151         return inedges.iterator();
152     }
153
154     public void addEdge(Edge newedge) {
155         newedge.setSource(this);
156         edges.addElement(newedge);
157         GraphNode tonode=newedge.getTarget();
158         tonode.inedges.addElement(newedge);
159     }
160
161     void reset() {
162             discoverytime = -1;
163             finishingtime = -1;
164             status = UNVISITED;
165     }
166
167     void resetscc() {
168         status = UNVISITED;
169     }
170
171     void discover(int time) {
172         discoverytime = time;
173         status = PROCESSING;
174     }
175
176     void finish(int time) {
177         assert status == PROCESSING;
178         finishingtime = time;
179         status = FINISHED;
180     }
181
182     /** Returns finishing time for dfs */
183
184     public int getFinishingTime() {
185         return finishingtime;
186     }
187
188
189     public static class DOTVisitor {
190         
191         java.io.PrintWriter output;
192         int tokennumber;
193         int color;
194       
195         private DOTVisitor(java.io.OutputStream output) {
196             tokennumber = 0;
197             color = 0;
198             this.output = new java.io.PrintWriter(output, true);
199         }
200         
201         private String getNewID(String name) {
202             tokennumber = tokennumber + 1;
203             return new String (name+tokennumber);
204         }
205
206         Collection nodes;
207         
208         public static void visit(java.io.OutputStream output, Collection nodes) {
209             DOTVisitor visitor = new DOTVisitor(output);
210             visitor.nodes = nodes;
211             visitor.make();
212
213         }
214         
215         private void make() {
216             output.println("digraph dotvisitor {");
217             output.println("\trotate=90;");
218             /*            output.println("\tpage=\"8.5,11\";");
219                           output.println("\tnslimit=1000.0;");
220                           output.println("\tnslimit1=1000.0;");
221                           output.println("\tmclimit=1000.0;");
222                           output.println("\tremincross=true;");*/
223             output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
224             output.println("\tedge [fontsize=6];");
225             traverse();
226             output.println("}\n");
227         }
228                 
229         private void traverse() {            
230             Set cycleset=GraphNode.findcycles(nodes);
231
232             Iterator i = nodes.iterator();
233             while (i.hasNext()) {
234                 GraphNode gn = (GraphNode) i.next();
235                 Iterator edges = gn.edges();
236                 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
237                 String option="";
238                 if (cycleset.contains(gn))
239                     option=",style=bold";
240                 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
241
242                 while (edges.hasNext()) {
243                     Edge edge = (Edge) edges.next();
244                     GraphNode node = edge.getTarget();
245                     if (nodes.contains(node)) {
246                         String edgelabel = useEdgeLabels ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
247                         output.println("\t" + gn.getLabel() + " -> " + node.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
248                     }
249                 }
250             }
251         }
252     }
253
254     /** This function returns the set of nodes involved in cycles. 
255      *  It only considers cycles containing nodes in the set 'nodes'.
256     */
257     public static Set findcycles(Collection nodes) {
258         HashSet cycleset=new HashSet();
259         SCC scc=DFS.computeSCC(nodes);
260         if (!scc.hasCycles())
261             return cycleset;
262         for(int i=0;i<scc.numSCC();i++) {
263             if (scc.hasCycle(i))
264                 cycleset.addAll(scc.getSCC(i));
265         }
266         return cycleset;
267     }
268
269     public static class SCC {
270         boolean acyclic;
271         HashMap map,revmap;
272         int numscc;
273         public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
274             this.acyclic=acyclic;
275             this.map=map;
276             this.revmap=revmap;
277             this.numscc=numscc;
278         }
279
280         /** Returns whether the graph has any cycles */
281         public boolean hasCycles() {
282             return !acyclic;
283         }
284
285         /** Returns the number of Strongly Connected Components */
286         public int numSCC() {
287             return numscc;
288         }
289
290         /** Returns the strongly connected component number for the GraphNode gn*/
291         public int getComponent(GraphNode gn) {
292             return ((Integer)revmap.get(gn)).intValue();
293         }
294
295         /** Returns the set of nodes in the strongly connected component i*/
296         public Set getSCC(int i) {
297             Integer scc=new Integer(i);
298             return (Set)map.get(scc);
299         }
300
301         /** Returns whether the strongly connected component i contains a cycle */
302         boolean hasCycle(int i) {
303             Integer scc=new Integer(i);
304             Set s=(Set)map.get(scc);
305             if (s.size()>1)
306                 return true;
307             Object [] array=s.toArray();
308             GraphNode gn=(GraphNode)array[0];
309             for(Iterator it=gn.edges();it.hasNext();) {
310                 Edge e=(Edge)it.next();
311                 if (e.getTarget()==gn)
312                     return true; /* Self Cycle */
313             }
314             return false;
315         }
316     }
317
318     /**
319      * DFS encapsulates the depth first search algorithm 
320      */
321     public static class DFS {
322
323         int time = 0;
324         int sccindex = 0;
325         Collection nodes;
326         Vector finishingorder=null;
327         HashMap sccmap;
328         HashMap sccmaprev;
329
330         private DFS(Collection nodes) { 
331             this.nodes = nodes;
332         }
333         /** Calculates the strong connected components for the graph composed
334          *  of the set of nodes 'nodes'*/
335         public static SCC computeSCC(Collection nodes) {
336             if (nodes==null) {
337                 throw new NullPointerException();
338             }
339             DFS dfs=new DFS(nodes);
340             dfs.sccmap=new HashMap();
341             dfs.sccmaprev=new HashMap();
342             dfs.finishingorder=new Vector();
343             boolean acyclic=dfs.go();
344             for (Iterator it = nodes.iterator();it.hasNext();) {
345                 GraphNode gn = (GraphNode) it.next();
346                 gn.resetscc();
347             }
348             for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
349                 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
350                 if (gn.getStatus() == UNVISITED) {
351                     dfs.dfsprev(gn);
352                     dfs.sccindex++; /* Increment scc index */
353                 }
354             }
355             return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
356         }
357
358         void dfsprev(GraphNode gn) {
359             if (gn.getStatus()==FINISHED||!nodes.contains(gn))
360                 return;
361             gn.setStatus(FINISHED);
362             Integer i=new Integer(sccindex);
363             if (!sccmap.containsKey(i))
364                 sccmap.put(i,new HashSet());
365             ((Set)sccmap.get(i)).add(gn);
366             sccmaprev.put(gn,i);
367             for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
368                 Edge e=(Edge)edgeit.next();
369                 GraphNode gn2=e.getSource();
370                 dfsprev(gn2);
371             }
372         }
373
374         public static boolean depthFirstSearch(Collection nodes) {
375             if (nodes == null) {
376                 throw new NullPointerException();
377             }
378             
379             DFS dfs = new DFS(nodes);
380             return dfs.go();
381         }
382
383         private boolean go() {           
384             Iterator i;
385             time = 0;
386             boolean acyclic=true;
387             i = nodes.iterator();
388             while (i.hasNext()) {
389                 GraphNode gn = (GraphNode) i.next();
390                 gn.reset();            
391             }            
392
393             i = nodes.iterator();
394             while (i.hasNext()) {
395                 GraphNode gn = (GraphNode) i.next();
396                 assert gn.getStatus() != PROCESSING;                    
397                 if (gn.getStatus() == UNVISITED) {
398                     if (!dfs(gn))
399                         acyclic=false;
400                 } 
401             }
402             return acyclic;
403         }
404
405         private boolean dfs(GraphNode gn) {
406             boolean acyclic=true;
407             gn.discover(time++);
408             Iterator edges = gn.edges();
409
410             while (edges.hasNext()) {
411                 Edge edge = (Edge) edges.next();
412                 GraphNode node = edge.getTarget();
413                 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
414                     continue;
415                 if (node.getStatus() == UNVISITED) {
416                     if (!dfs(node))
417                         acyclic=false;
418                 } else if (node.getStatus()==PROCESSING) {
419                     acyclic=false;
420                 }
421             }
422             if (finishingorder!=null)
423                 finishingorder.add(gn);
424             gn.finish(time++);
425             return acyclic;
426         }
427
428     } /* end DFS */
429
430 }