Committing pretty printer fix.
[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 static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
117         Stack tovisit=new Stack();
118         Stack newvisit=new Stack();
119         tovisit.addAll(nodes);
120         for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
121             while(!tovisit.isEmpty()) {
122                 GraphNode gn=(GraphNode)tovisit.pop();
123                 for(Iterator it=gn.edges();it.hasNext();) {
124                     Edge edge=(Edge)it.next();
125                     GraphNode target=edge.getTarget();
126                     if (!nodes.contains(target)) {
127                         if ((removed==null)||
128                             (!removed.contains(target))) {
129                             nodes.add(target);
130                             newvisit.push(target);
131                         }
132                     }
133                 }
134             }
135             tovisit=newvisit;
136             newvisit=new Stack();
137         }
138     }
139
140     public void setDotNodeParameters(String param) {
141         if (param == null) {
142             throw new NullPointerException();
143         }
144         if (param.length() > 0) {
145             dotnodeparams = "," + param;
146         } else {
147             dotnodeparams = new String();
148         }
149     }
150     
151     public void setStatus(NodeStatus status) {
152         if (status == null) {
153             throw new NullPointerException();
154         }
155         this.status = status;
156     }
157
158     public String getLabel() {
159         return nodelabel;
160     }
161
162     public String getTextLabel() {
163         return textlabel;
164     }
165     
166     public NodeStatus getStatus() {
167         return this.status;
168     }
169
170     public Iterator edges() {
171         return edges.iterator();
172     }
173
174     public Iterator inedges() {
175         return inedges.iterator();
176     }
177
178     public void addEdge(Edge newedge) {
179         newedge.setSource(this);
180         edges.addElement(newedge);
181         GraphNode tonode=newedge.getTarget();
182         tonode.inedges.addElement(newedge);
183     }
184
185     void reset() {
186             discoverytime = -1;
187             finishingtime = -1;
188             status = UNVISITED;
189     }
190
191     void resetscc() {
192         status = UNVISITED;
193     }
194
195     void discover(int time) {
196         discoverytime = time;
197         status = PROCESSING;
198     }
199
200     void finish(int time) {
201         assert status == PROCESSING;
202         finishingtime = time;
203         status = FINISHED;
204     }
205
206     /** Returns finishing time for dfs */
207
208     public int getFinishingTime() {
209         return finishingtime;
210     }
211
212
213     public static class DOTVisitor {
214         
215         java.io.PrintWriter output;
216         int tokennumber;
217         int color;
218       
219         private DOTVisitor(java.io.OutputStream output) {
220             tokennumber = 0;
221             color = 0;
222             this.output = new java.io.PrintWriter(output, true);
223         }
224         
225         private String getNewID(String name) {
226             tokennumber = tokennumber + 1;
227             return new String (name+tokennumber);
228         }
229
230         Collection nodes;
231         Collection special;
232         
233         public static void visit(java.io.OutputStream output, Collection nodes) {
234             visit(output,nodes,null);
235         }
236
237         public static void visit(java.io.OutputStream output, Collection nodes, Collection special) {
238             DOTVisitor visitor = new DOTVisitor(output);
239             visitor.special=special;
240             visitor.nodes = nodes;
241             visitor.make();
242         }
243         
244         private void make() {
245             output.println("digraph dotvisitor {");
246             output.println("\trotate=90;");
247             /*            output.println("\tpage=\"8.5,11\";");
248                           output.println("\tnslimit=1000.0;");
249                           output.println("\tnslimit1=1000.0;");
250                           output.println("\tmclimit=1000.0;");
251                           output.println("\tremincross=true;");*/
252             output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
253             output.println("\tedge [fontsize=6];");
254             traverse();
255             output.println("}\n");
256         }
257                 
258         private void traverse() {            
259             Set cycleset=GraphNode.findcycles(nodes);
260
261             Iterator i = nodes.iterator();
262             while (i.hasNext()) {
263                 GraphNode gn = (GraphNode) i.next();
264                 Iterator edges = gn.edges();
265                 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
266                 String option="";
267                 if (cycleset.contains(gn))
268                     option=",style=bold";
269                 if (special!=null&&special.contains(gn))
270                     option+=",shape=box";
271                 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
272
273                 while (edges.hasNext()) {
274                     Edge edge = (Edge) edges.next();
275                     GraphNode node = edge.getTarget();
276                     if (nodes.contains(node)) {
277                         String edgelabel = useEdgeLabels ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
278                         output.println("\t" + gn.getLabel() + " -> " + node.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
279                     }
280                 }
281             }
282         }
283     }
284
285     /** This function returns the set of nodes involved in cycles. 
286      *  It only considers cycles containing nodes in the set 'nodes'.
287     */
288     public static Set findcycles(Collection nodes) {
289         HashSet cycleset=new HashSet();
290         SCC scc=DFS.computeSCC(nodes);
291         if (!scc.hasCycles())
292             return cycleset;
293         for(int i=0;i<scc.numSCC();i++) {
294             if (scc.hasCycle(i))
295                 cycleset.addAll(scc.getSCC(i));
296         }
297         return cycleset;
298     }
299
300     public static class SCC {
301         boolean acyclic;
302         HashMap map,revmap;
303         int numscc;
304         public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
305             this.acyclic=acyclic;
306             this.map=map;
307             this.revmap=revmap;
308             this.numscc=numscc;
309         }
310
311         /** Returns whether the graph has any cycles */
312         public boolean hasCycles() {
313             return !acyclic;
314         }
315
316         /** Returns the number of Strongly Connected Components */
317         public int numSCC() {
318             return numscc;
319         }
320
321         /** Returns the strongly connected component number for the GraphNode gn*/
322         public int getComponent(GraphNode gn) {
323             return ((Integer)revmap.get(gn)).intValue();
324         }
325
326         /** Returns the set of nodes in the strongly connected component i*/
327         public Set getSCC(int i) {
328             Integer scc=new Integer(i);
329             return (Set)map.get(scc);
330         }
331
332         /** Returns whether the strongly connected component i contains a cycle */
333         boolean hasCycle(int i) {
334             Integer scc=new Integer(i);
335             Set s=(Set)map.get(scc);
336             if (s.size()>1)
337                 return true;
338             Object [] array=s.toArray();
339             GraphNode gn=(GraphNode)array[0];
340             for(Iterator it=gn.edges();it.hasNext();) {
341                 Edge e=(Edge)it.next();
342                 if (e.getTarget()==gn)
343                     return true; /* Self Cycle */
344             }
345             return false;
346         }
347     }
348
349     /**
350      * DFS encapsulates the depth first search algorithm 
351      */
352     public static class DFS {
353
354         int time = 0;
355         int sccindex = 0;
356         Collection nodes;
357         Vector finishingorder=null;
358         HashMap sccmap;
359         HashMap sccmaprev;
360
361         private DFS(Collection nodes) { 
362             this.nodes = nodes;
363         }
364         /** Calculates the strong connected components for the graph composed
365          *  of the set of nodes 'nodes'*/
366         public static SCC computeSCC(Collection nodes) {
367             if (nodes==null) {
368                 throw new NullPointerException();
369             }
370             DFS dfs=new DFS(nodes);
371             dfs.sccmap=new HashMap();
372             dfs.sccmaprev=new HashMap();
373             dfs.finishingorder=new Vector();
374             boolean acyclic=dfs.go();
375             for (Iterator it = nodes.iterator();it.hasNext();) {
376                 GraphNode gn = (GraphNode) it.next();
377                 gn.resetscc();
378             }
379             for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
380                 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
381                 if (gn.getStatus() == UNVISITED) {
382                     dfs.dfsprev(gn);
383                     dfs.sccindex++; /* Increment scc index */
384                 }
385             }
386             return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
387         }
388
389         void dfsprev(GraphNode gn) {
390             if (gn.getStatus()==FINISHED||!nodes.contains(gn))
391                 return;
392             gn.setStatus(FINISHED);
393             Integer i=new Integer(sccindex);
394             if (!sccmap.containsKey(i))
395                 sccmap.put(i,new HashSet());
396             ((Set)sccmap.get(i)).add(gn);
397             sccmaprev.put(gn,i);
398             for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
399                 Edge e=(Edge)edgeit.next();
400                 GraphNode gn2=e.getSource();
401                 dfsprev(gn2);
402             }
403         }
404
405         public static boolean depthFirstSearch(Collection nodes) {
406             if (nodes == null) {
407                 throw new NullPointerException();
408             }
409             
410             DFS dfs = new DFS(nodes);
411             return dfs.go();
412         }
413
414         private boolean go() {           
415             Iterator i;
416             time = 0;
417             boolean acyclic=true;
418             i = nodes.iterator();
419             while (i.hasNext()) {
420                 GraphNode gn = (GraphNode) i.next();
421                 gn.reset();            
422             }            
423
424             i = nodes.iterator();
425             while (i.hasNext()) {
426                 GraphNode gn = (GraphNode) i.next();
427                 assert gn.getStatus() != PROCESSING;                    
428                 if (gn.getStatus() == UNVISITED) {
429                     if (!dfs(gn))
430                         acyclic=false;
431                 } 
432             }
433             return acyclic;
434         }
435
436         private boolean dfs(GraphNode gn) {
437             boolean acyclic=true;
438             gn.discover(time++);
439             Iterator edges = gn.edges();
440
441             while (edges.hasNext()) {
442                 Edge edge = (Edge) edges.next();
443                 GraphNode node = edge.getTarget();
444                 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
445                     continue;
446                 if (node.getStatus() == UNVISITED) {
447                     if (!dfs(node))
448                         acyclic=false;
449                 } else if (node.getStatus()==PROCESSING) {
450                     acyclic=false;
451                 }
452             }
453             if (finishingorder!=null)
454                 finishingorder.add(gn);
455             gn.finish(time++);
456             return acyclic;
457         }
458
459     } /* end DFS */
460
461 }