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