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