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