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 }