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