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