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 /** This class is used to hold the flag states that a class in the Bristlecone
  10  *  program can exist in, during runtime.
  11  */
  12 public class FlagState {
  13     /* NodeStatus enumeration pattern ***********/
  14
  15     public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED");
  16     public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING");
  17     public static final NodeStatus FINISHED = new NodeStatus("FINISHED");
  18     public static final int ONETAG=1;
  19     public static final int NOTAGS=0;
  20     public static final int MULTITAGS=-1;
  21
  22
  23
  24
  25     public static class NodeStatus {
  26         private static String name;
  27         private NodeStatus(String name) { this.name = name; }
  28         public String toString() { return name; }
  29     }
  30
  31
  32     int discoverytime = -1;
  33     int finishingtime = -1; /* used for searches */
  34
  35     //Hashtable<String,Integer> tags=new Hashtable<String,Integer>();
  36     Vector edges = new Vector();
  37     Vector inedges = new Vector();
  38     NodeStatus status = UNVISITED;
  39     protected String dotnodeparams = new String();
  40     boolean merge=false;
  41     String nodeoption="";
  42     private int uid;
  43     private static int nodeid=0;
  44
  45     private final HashSet flagstate;
  46     private final ClassDescriptor cd;
  47     private final Hashtable<String,Integer> tags;
  48
  49     public void setOption(String option) {
  50         this.nodeoption=","+option;
  51     }
  52
  53     public void setMerge() {
  54         merge=true;
  55     }
  56     /** Class constructor
  57      *  Creates a new flagstate with all flags set to false.
  58      *  @param cd ClassDescriptor
  59      */
  60     public FlagState(ClassDescriptor cd) {
  61         this.flagstate=new HashSet();
  62         this.cd=cd;
  63         this.tags=new Hashtable<String,Integer>();
  64         this.uid=FlagState.nodeid++;
  65     }
  66
  67     /** Class constructor
  68      *  Creates a new flagstate with flags set according to the HashSet.
  69      *  If the flag exists in the hashset, it's set to true else set to false.
  70      *  @param cd ClassDescriptor
  71      *  @param flagstate a <CODE>HashSet</CODE> containing FlagDescriptors
  72      */
  73     private FlagState(HashSet flagstate, ClassDescriptor cd,Hashtable<String,Integer> tags) {
  74         this.flagstate=flagstate;
  75         this.cd=cd;
  76         this.tags=tags;
  77         this.uid=FlagState.nodeid++;
  78
  79     }
  80
  81     /** Accessor method
  82       *  @param fd FlagDescriptor
  83       *  @return true if the flagstate contains fd else false.
  84       */
  85     public boolean get(FlagDescriptor fd) {
  86         return flagstate.contains(fd);
  87     }
  88
  89
  90     public String toString() {
  91         return cd.toString()+getTextLabel();
  92     }
  93
  94     /** @return Iterator over the flags in the flagstate.
  95      */
  96
  97     public Iterator getFlags() {
  98         return flagstate.iterator();
  99     }
 100
 101     public FlagState setTag(TagDescriptor tag){
 102
 103             HashSet newset=flagstate.clone();
 104             Hashtable<String,Integer> newtags=tags.clone();
 105
 106             if (newtags.containsKey(tag)){
 107                    switch (newtags.get(tag).intValue()){
 108                            case ONETAG:
 109                                         newtags.put(tag,new Integer(MULTITAG));
 110                                         break;
 111                            case MULTITAG:
 112                                         newtags.put(tag,new Integer(MULTITAG));
 113                                         break;
 114                         }
 115                 }
 116                 else{
 117                         newtags.put(tag,new Integer(ONETAG));
 118                 }
 119
 120                 return new FlagState(newset,cd,newtags);
 121
 122     }
 123     public int getTagCount(String tagtype){
 124                 for (Enumeration en=getTags();en.hasMoreElements();){
 125                         TagDescriptor td=(TagDescriptor)en.nextElement();
 126                         if (tagtype.equals(td.getSymbol()))
 127                                 return tags.get(td).intValue();   //returns either ONETAG or MULTITAG
 128                 }
 129                 return NOTAG;
 130
 131     }
 132
 133
 134
 135     public FlagState[] clearTag(TagDescriptor tag){
 136
 137             if (tags.containsKey(tag)){
 138             switch(tags.get(tag).intValue()){
 139                     case ONETAG:
 140                         HashSet newset=flagstate.clone();
 141                         Hashtable<String,Integer> newtags=tags.clone();
 142                         newtags.remove(tag);
 143                         return new FlagState(newset,cd,newtags);
 144                         break;
 145                     case MULTITAG:
 146                         //when tagcount is more than 2, COUNT stays at MULTITAG
 147                         FlagState[] retstates=new FlagState[2];
 148                         HashSet newset1=flagstate.clone();
 149                         Hashtable<String,Integer> newtags1=tags.clone();
 150                         retstates[1]=new FlagState(newset1,cd,newtags1);
 151                         //when tagcount is 2, COUNT changes to ONETAG
 152                         HashSet newset2=flagstate.clone();
 153                         Hashtable<String,Integer> newtags2=tags.clone();
 154                         newtags1.put(tag,new Integer(ONETAG));
 155                         retstates[1]=new FlagState(newset2,cd,newtags2);
 156                         return retstates;
 157                         break;
 158         }
 159                 }else{
 160                         throw new Error("Invalid Operation: Can not clear a tag that doesn't exist.");
 161                 }
 162
 163     }
 164
 165     /** Creates a string description of the flagstate
 166      *  e.g.  a flagstate with five flags could look like 01001
 167      *  @param flags an array of flagdescriptors.
 168      *  @return string representation of the flagstate.
 169      */
 170         public String toString(FlagDescriptor[] flags)
 171         {
 172                 StringBuffer sb = new StringBuffer(flagstate.size());
 173                 for(int i=0;i < flags.length; i++)
 174                 {
 175                         if (get(flags[i]))
 176                                 sb.append(1);
 177                         else
 178                                 sb.append(0);
 179                 }
 180
 181                 return new String(sb);
 182         }
 183
 184         /** Accessor method
 185          *  @return returns the classdescriptor of the flagstate.
 186          */
 187
 188         public ClassDescriptor getClassDescriptor(){
 189         return cd;
 190         }
 191
 192         /** Sets the status of a specific flag in a flagstate after cloning it.
 193          *  @param      fd FlagDescriptor of the flag whose status is being set.
 194          *  @param  status boolean value
 195          *  @return the new flagstate with <CODE>fd</CODE> set to <CODE>status</CODE>.
 196          */
 197
 198     public FlagState setFlag(FlagDescriptor fd, boolean status) {
 199         HashSet newset=(HashSet) flagstate.clone();
 200         if (status)
 201             newset.add(fd);
 202         else if (newset.contains(fd)){
 203             newset.remove(fd);
 204         }
 205         return new FlagState(newset, cd);
 206     }
 207
 208     /** Tests for equality of two flagstate objects.
 209     */
 210
 211     public boolean equals(Object o) {
 212         if (o instanceof FlagState) {
 213             FlagState fs=(FlagState)o;
 214             if (fs.cd!=cd)
 215                 return false;
 216             return (fs.flagstate.equals(flagstate) & fs.tags.equals(tags));
 217         }
 218         return false;
 219     }
 220
 221     public int hashCode() {
 222         return cd.hashCode()^flagstate.hashCode()^tags.hashCode();
 223     }
 224
 225     public static void computeclosure(Collection nodes, Collection removed) {
 226         Stack tovisit=new Stack();
 227         tovisit.addAll(nodes);
 228         while(!tovisit.isEmpty()) {
 229             FlagState gn=(FlagState)tovisit.pop();
 230             for(Iterator it=gn.edges();it.hasNext();) {
 231                 Edge edge=(Edge)it.next();
 232                 FlagState target=edge.getTarget();
 233                 if (!nodes.contains(target)) {
 234                     if ((removed==null)||
 235                         (!removed.contains(target))) {
 236                         nodes.add(target);
 237                         tovisit.push(target);
 238                     }
 239                 }
 240             }
 241         }
 242     }
 243
 244     public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
 245         Stack tovisit=new Stack();
 246         Stack newvisit=new Stack();
 247         tovisit.addAll(nodes);
 248         for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
 249             while(!tovisit.isEmpty()) {
 250                 FlagState gn=(FlagState)tovisit.pop();
 251                 for(Iterator it=gn.edges();it.hasNext();) {
 252                     Edge edge=(Edge)it.next();
 253                     FlagState target=edge.getTarget();
 254                     if (!nodes.contains(target)) {
 255                         if ((removed==null)||
 256                             (!removed.contains(target))) {
 257                             nodes.add(target);
 258                             newvisit.push(target);
 259                         }
 260                     }
 261                 }
 262             }
 263             tovisit=newvisit;
 264             newvisit=new Stack();
 265         }
 266     }
 267
 268     public void setDotNodeParameters(String param) {
 269         if (param == null) {
 270             throw new NullPointerException();
 271         }
 272         if (param.length() > 0) {
 273             dotnodeparams = "," + param;
 274         } else {
 275             dotnodeparams = new String();
 276         }
 277     }
 278
 279     public void setStatus(NodeStatus status) {
 280         if (status == null) {
 281             throw new NullPointerException();
 282         }
 283         this.status = status;
 284     }
 285
 286     public String getLabel() {
 287         return "N"+uid;
 288     }
 289
 290     public String getTextLabel() {
 291         String label=null;
 292         for(Iterator it=getFlags();it.hasNext();) {
 293             FlagDescriptor fd=(FlagDescriptor) it.next();
 294             if (label==null)
 295                 label=fd.toString();
 296             else
 297                 label+=", "+fd.toString();
 298         }
 299         for (Enumeration en_tags=getTags();en_tags.hasMoreElements();){
 300                 TagDescriptor td=(TagDescriptor)en_tags.nextElement();
 301                 switch (tags.get(td).intValue()){
 302                         case ONETAG:
 303                                 label+=", "+td.toString()+"(1)";
 304                                 break;
 305                         case MULTITAG:
 306                                 label+=", "+td.toString()+"(n)";
 307                                 break;
 308                         default:
 309                                 break;
 310                 }
 311         }
 312         return label;
 313     }
 314
 315     public Enumeration getTags(){
 316             return tags.keys();
 317         }
 318
 319     public NodeStatus getStatus() {
 320         return this.status;
 321     }
 322
 323     public Iterator edges() {
 324         return edges.iterator();
 325     }
 326
 327     public Iterator inedges() {
 328         return inedges.iterator();
 329     }
 330
 331     public void addEdge(Edge newedge) {
 332         newedge.setSource(this);
 333         edges.addElement(newedge);
 334         FlagState tonode=newedge.getTarget();
 335         tonode.inedges.addElement(newedge);
 336     }
 337
 338     void reset() {
 339             discoverytime = -1;
 340             finishingtime = -1;
 341             status = UNVISITED;
 342     }
 343
 344     void resetscc() {
 345         status = UNVISITED;
 346     }
 347
 348     void discover(int time) {
 349         discoverytime = time;
 350         status = PROCESSING;
 351     }
 352
 353     void finish(int time) {
 354         assert status == PROCESSING;
 355         finishingtime = time;
 356         status = FINISHED;
 357     }
 358
 359     /** Returns finishing time for dfs */
 360
 361     public int getFinishingTime() {
 362         return finishingtime;
 363     }
 364
 365
 366     public static class DOTVisitor {
 367
 368         java.io.PrintWriter output;
 369         int tokennumber;
 370         int color;
 371
 372         private DOTVisitor(java.io.OutputStream output) {
 373             tokennumber = 0;
 374             color = 0;
 375             this.output = new java.io.PrintWriter(output, true);
 376         }
 377
 378         private String getNewID(String name) {
 379             tokennumber = tokennumber + 1;
 380             return new String (name+tokennumber);
 381         }
 382
 383         Collection nodes;
 384         Collection special;
 385
 386         public static void visit(java.io.OutputStream output, Collection nodes) {
 387             visit(output,nodes,null);
 388         }
 389
 390         public static void visit(java.io.OutputStream output, Collection nodes, Collection special) {
 391             DOTVisitor visitor = new DOTVisitor(output);
 392             visitor.special=special;
 393             visitor.nodes = nodes;
 394             visitor.make();
 395         }
 396
 397         private void make() {
 398             output.println("digraph dotvisitor {");
 399             output.println("\trotate=90;");
 400             /*            output.println("\tpage=\"8.5,11\";");
 401                           output.println("\tnslimit=1000.0;");
 402                           output.println("\tnslimit1=1000.0;");
 403                           output.println("\tmclimit=1000.0;");
 404                           output.println("\tremincross=true;");*/
 405             output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
 406             output.println("\tedge [fontsize=6];");
 407             traverse();
 408             output.println("}\n");
 409         }
 410
 411        private void traverse() {
 412             Iterator i = nodes.iterator();
 413             while (i.hasNext()) {
 414                 FlagState gn = (FlagState) i.next();
 415                 Iterator edges = gn.edges();
 416                 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
 417                                 String option=gn.nodeoption;
 418                                 if (special!=null&&special.contains(gn))
 419                                 option+=",shape=box";
 420                                 if (!gn.merge)
 421                     output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
 422                                 if (!gn.merge)
 423                         while (edges.hasNext()) {
 424                         Edge edge = (Edge) edges.next();
 425                             FlagState node = edge.getTarget();
 426                                         if (nodes.contains(node)) {
 427                                                         for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
 428                                                         FlagState node2=(FlagState)nodeit.next();
 429                                                         String edgelabel = "label=\"" + edge.getLabel() + "\"";
 430                                                                 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
 431                                                         }
 432                                         }
 433                         }
 434             }
 435         }
 436
 437
 438         Set nonmerge(FlagState gn) {
 439             HashSet newset=new HashSet();
 440             HashSet toprocess=new HashSet();
 441             toprocess.add(gn);
 442             while(!toprocess.isEmpty()) {
 443                 FlagState gn2=(FlagState)toprocess.iterator().next();
 444                 toprocess.remove(gn2);
 445                 if (!gn2.merge)
 446                     newset.add(gn2);
 447                 else {
 448                     Iterator edges = gn2.edges();
 449                     while (edges.hasNext()) {
 450                         Edge edge = (Edge) edges.next();
 451                         FlagState node = edge.getTarget();
 452                         if (!newset.contains(node)&&nodes.contains(node))
 453                             toprocess.add(node);
 454                     }
 455                 }
 456             }
 457             return newset;
 458         }
 459
 460     }
 461
 462     /** This function returns the set of nodes involved in cycles.
 463      *  It only considers cycles containing nodes in the set 'nodes'.
 464     */
 465     public static Set findcycles(Collection nodes) {
 466         HashSet cycleset=new HashSet();
 467         SCC scc=DFS.computeSCC(nodes);
 468         if (!scc.hasCycles())
 469             return cycleset;
 470         for(int i=0;i<scc.numSCC();i++) {
 471             if (scc.hasCycle(i))
 472                 cycleset.addAll(scc.getSCC(i));
 473         }
 474         return cycleset;
 475     }
 476
 477     public static class SCC {
 478         boolean acyclic;
 479         HashMap map,revmap;
 480         int numscc;
 481         public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
 482             this.acyclic=acyclic;
 483             this.map=map;
 484             this.revmap=revmap;
 485             this.numscc=numscc;
 486         }
 487
 488         /** Returns whether the graph has any cycles */
 489         public boolean hasCycles() {
 490             return !acyclic;
 491         }
 492
 493         /** Returns the number of Strongly Connected Components */
 494         public int numSCC() {
 495             return numscc;
 496         }
 497
 498         /** Returns the strongly connected component number for the FlagState gn*/
 499         public int getComponent(FlagState gn) {
 500             return ((Integer)revmap.get(gn)).intValue();
 501         }
 502
 503         /** Returns the set of nodes in the strongly connected component i*/
 504         public Set getSCC(int i) {
 505             Integer scc=new Integer(i);
 506             return (Set)map.get(scc);
 507         }
 508
 509         /** Returns whether the strongly connected component i contains a cycle */
 510         boolean hasCycle(int i) {
 511             Integer scc=new Integer(i);
 512             Set s=(Set)map.get(scc);
 513             if (s.size()>1)
 514                 return true;
 515             Object [] array=s.toArray();
 516             FlagState gn=(FlagState)array[0];
 517             for(Iterator it=gn.edges();it.hasNext();) {
 518                 Edge e=(Edge)it.next();
 519                 if (e.getTarget()==gn)
 520                     return true; /* Self Cycle */
 521             }
 522             return false;
 523         }
 524     }
 525
 526     /**
 527      * DFS encapsulates the depth first search algorithm
 528      */
 529     public static class DFS {
 530
 531         int time = 0;
 532         int sccindex = 0;
 533         Collection nodes;
 534         Vector finishingorder=null;
 535         HashMap sccmap;
 536         HashMap sccmaprev;
 537
 538         private DFS(Collection nodes) {
 539             this.nodes = nodes;
 540         }
 541         /** Calculates the strong connected components for the graph composed
 542          *  of the set of nodes 'nodes'*/
 543         public static SCC computeSCC(Collection nodes) {
 544             if (nodes==null) {
 545                 throw new NullPointerException();
 546             }
 547             DFS dfs=new DFS(nodes);
 548             dfs.sccmap=new HashMap();
 549             dfs.sccmaprev=new HashMap();
 550             dfs.finishingorder=new Vector();
 551             boolean acyclic=dfs.go();
 552             for (Iterator it = nodes.iterator();it.hasNext();) {
 553                 FlagState gn = (FlagState) it.next();
 554                 gn.resetscc();
 555             }
 556             for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
 557                 FlagState gn=(FlagState)dfs.finishingorder.get(i);
 558                 if (gn.getStatus() == UNVISITED) {
 559                     dfs.dfsprev(gn);
 560                     dfs.sccindex++; /* Increment scc index */
 561                 }
 562             }
 563             return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
 564         }
 565
 566         void dfsprev(FlagState gn) {
 567             if (gn.getStatus()==FINISHED||!nodes.contains(gn))
 568                 return;
 569             gn.setStatus(FINISHED);
 570             Integer i=new Integer(sccindex);
 571             if (!sccmap.containsKey(i))
 572                 sccmap.put(i,new HashSet());
 573             ((Set)sccmap.get(i)).add(gn);
 574             sccmaprev.put(gn,i);
 575             for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
 576                 Edge e=(Edge)edgeit.next();
 577                 FlagState gn2=e.getSource();
 578                 dfsprev(gn2);
 579             }
 580         }
 581
 582         public static boolean depthFirstSearch(Collection nodes) {
 583             if (nodes == null) {
 584                 throw new NullPointerException();
 585             }
 586
 587             DFS dfs = new DFS(nodes);
 588             return dfs.go();
 589         }
 590
 591         private boolean go() {
 592             Iterator i;
 593             time = 0;
 594             boolean acyclic=true;
 595             i = nodes.iterator();
 596             while (i.hasNext()) {
 597                 FlagState gn = (FlagState) i.next();
 598                 gn.reset();
 599             }
 600
 601             i = nodes.iterator();
 602             while (i.hasNext()) {
 603                 FlagState gn = (FlagState) i.next();
 604                 assert gn.getStatus() != PROCESSING;
 605                 if (gn.getStatus() == UNVISITED) {
 606                     if (!dfs(gn))
 607                         acyclic=false;
 608                 }
 609             }
 610             return acyclic;
 611         }
 612
 613         private boolean dfs(FlagState gn) {
 614             boolean acyclic=true;
 615             gn.discover(time++);
 616             Iterator edges = gn.edges();
 617
 618             while (edges.hasNext()) {
 619                 Edge edge = (Edge) edges.next();
 620                 FlagState node = edge.getTarget();
 621                 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
 622                     continue;
 623                 if (node.getStatus() == UNVISITED) {
 624                     if (!dfs(node))
 625                         acyclic=false;
 626                 } else if (node.getStatus()==PROCESSING) {
 627                     acyclic=false;
 628                 }
 629             }
 630             if (finishingorder!=null)
 631                 finishingorder.add(gn);
 632             gn.finish(time++);
 633             return acyclic;
 634         }
 635     } /* end DFS */
 636 }