Robust/src/Analysis/TaskStateAnalysis/TaskTagAnalysis.java

   1 package Analysis.TaskStateAnalysis;
   2 import IR.*;
   3 import IR.Tree.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.File;
   7 import java.io.FileWriter;
   8 import java.io.FileOutputStream;
   9
  10 public class TaskTagAnalysis {
  11   State state;
  12   TagAnalysis taganalysis;
  13   TypeUtil typeutil;
  14   FlagInfo flaginfo;
  15   HashSet<TagState> toprocess;
  16   HashSet<TagState> discovered;
  17   Hashtable<TaskDescriptor, TaskQueue> tasktable;
  18   Hashtable<TagDescriptor, Set<TagState>> tsresults;
  19   Hashtable<ClassDescriptor, Set<TagState>> fsresults;
  20
  21
  22   /**
  23    * Class Constructor
  24    *
  25    */
  26   public TaskTagAnalysis(State state, TagAnalysis taganalysis, TypeUtil typeutil) {
  27     this.state=state;
  28     this.typeutil=typeutil;
  29     this.taganalysis=taganalysis;
  30     this.flaginfo=new FlagInfo(state);
  31     this.toprocess=new HashSet<TagState>();
  32     this.discovered=new HashSet<TagState>();
  33     this.tasktable=new Hashtable<TaskDescriptor, TaskQueue>();
  34     this.tsresults=new Hashtable<TagDescriptor, Set<TagState>>();
  35     this.fsresults=new Hashtable<ClassDescriptor, Set<TagState>>();
  36
  37
  38     for(Iterator taskit=state.getTaskSymbolTable().getDescriptorsIterator(); taskit.hasNext(); ) {
  39       TaskDescriptor td=(TaskDescriptor)taskit.next();
  40       tasktable.put(td, new TaskQueue(td));
  41     }
  42     doAnalysis();
  43     doOutput();
  44   }
  45
  46   private void doOutput() {
  47     try {
  48       for(Iterator<TagDescriptor> tagit=tsresults.keySet().iterator(); tagit.hasNext(); ) {
  49         TagDescriptor tag=tagit.next();
  50         Set<TagState> set=tsresults.get(tag);
  51         File dotfile_flagstates= new File("tag"+tag.getSymbol()+".dot");
  52         FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
  53         TagState.DOTVisitor.visit(dotstream,set);
  54       }
  55       for(Iterator<ClassDescriptor> cdit=fsresults.keySet().iterator(); cdit.hasNext(); ) {
  56         ClassDescriptor cd=cdit.next();
  57         Set<TagState> set=fsresults.get(cd);
  58         File dotfile_flagstates= new File("class"+cd.getSymbol()+".dot");
  59         FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
  60         TagState.DOTVisitor.visit(dotstream,set);
  61       }
  62     } catch (Exception e) {
  63       e.printStackTrace();
  64     }
  65   }
  66
  67   private void doAnalysis() {
  68     toprocess.add(createInitialState());
  69     while(!toprocess.isEmpty()) {
  70       TagState ts=toprocess.iterator().next();
  71       toprocess.remove(ts);
  72       //Loop through each task
  73       for(Iterator taskit=state.getTaskSymbolTable().getDescriptorsIterator(); taskit.hasNext(); ) {
  74         TaskDescriptor td=(TaskDescriptor)taskit.next();
  75         TaskQueue tq=tasktable.get(td);
  76         processTask(td, tq, ts);
  77       }
  78     }
  79   }
  80
  81   private void processTask(TaskDescriptor td, TaskQueue tq, TagState ts) {
  82     Set<FlagState> flagset=ts.getFS();
  83     for(Iterator<FlagState> fsit=flagset.iterator(); fsit.hasNext(); ) {
  84       FlagState fs=fsit.next();
  85       FlagTagState fts=new FlagTagState(ts, fs);
  86       for(int i=0; i<td.numParameters(); i++) {
  87         System.out.println("Trying to enqueue "+td);
  88         if (canEnqueue(td, i, fs)) {
  89           System.out.println("Enqueued");
  90           TaskQueueIterator tqi=tq.enqueue(i, fts);
  91           while(tqi.hasNext()) {
  92             System.out.println("binding");
  93             processBinding(tqi);
  94             tqi.next();
  95           }
  96         }
  97       }
  98     }
  99   }
 100
 101   private void processBinding(TaskQueueIterator tqi) {
 102     TaskBinding tb=new TaskBinding(tqi);
 103     while(tb.hasNext()) {
 104       doAnalysis(tb);
 105       tb.next();
 106     }
 107   }
 108
 109   private Hashtable<TempDescriptor, Wrapper> computeInitialState(Hashtable<FlatNode, Hashtable<TempDescriptor, Wrapper>> maintable, FlatNode fn) {
 110     Hashtable<TempDescriptor, Wrapper> table=new Hashtable<TempDescriptor, Wrapper>();
 111     Hashtable<TagWrapper,TagWrapper> tagtable=new Hashtable<TagWrapper, TagWrapper>();
 112     for(int i=0; i<fn.numPrev(); i++) {
 113       FlatNode fnprev=fn.getPrev(i);
 114       Hashtable<TempDescriptor, Wrapper> prevtable=maintable.get(fn);
 115
 116       //Iterator through the Tags
 117       for(Iterator<TempDescriptor> tmpit=prevtable.keySet().iterator(); tmpit.hasNext(); ) {
 118         TempDescriptor tmp=tmpit.next();
 119         Wrapper prevtag=prevtable.get(tmp);
 120         if (prevtag instanceof ObjWrapper)
 121           continue;
 122         if (table.containsKey(tmp)) {
 123           //merge tag states
 124           TagWrapper currtag=(TagWrapper) table.get(tmp);
 125           tagtable.put((TagWrapper)prevtag, currtag);
 126           assert(currtag.initts.equals(((TagWrapper)prevtag).initts));
 127           for(Iterator<TagState> tagit=((TagWrapper)prevtag).ts.iterator(); tagit.hasNext(); ) {
 128             TagState tag=tagit.next();
 129             if (!currtag.ts.contains(tag)) {
 130               currtag.ts.add(tag);
 131             }
 132           }
 133         } else {
 134           TagWrapper clonetag=((TagWrapper)prevtag).clone();
 135           tagtable.put((TagWrapper)prevtag, clonetag);
 136           table.put(tmp, clonetag);
 137         }
 138       }
 139
 140       //Iterator through the Objects
 141       for(Iterator<TempDescriptor> tmpit=prevtable.keySet().iterator(); tmpit.hasNext(); ) {
 142         TempDescriptor tmp=tmpit.next();
 143         Wrapper obj=prevtable.get(tmp);
 144         if (obj instanceof TagWrapper)
 145           continue;
 146         ObjWrapper prevobj=(ObjWrapper)obj;
 147         if (!table.containsKey(tmp)) {
 148           //merge tag states
 149           ObjWrapper newobj=new ObjWrapper();
 150           newobj.initfs=prevobj.initfs;
 151           table.put(tmp, newobj);
 152         }
 153         ObjWrapper currobj=(ObjWrapper) table.get(tmp);
 154         assert(currobj.initfs.equals(prevobj.initfs));
 155         for(Iterator<TagWrapper> tagit=prevobj.tags.iterator(); tagit.hasNext(); ) {
 156           TagWrapper tprev=tagit.next();
 157           TagWrapper t=tagtable.get(tprev);
 158           currobj.tags.add(t);
 159         }
 160         for(Iterator<FlagState> flagit=prevobj.fs.iterator(); flagit.hasNext(); ) {
 161           FlagState fs=flagit.next();
 162           currobj.fs.add(fs);
 163         }
 164       }
 165     }
 166     return table;
 167   }
 168
 169   private void processFlatFlag(FlatFlagActionNode fn, Hashtable<TempDescriptor, Wrapper> table, TaskDescriptor td) {
 170     if (fn.getTaskType()==FlatFlagActionNode.PRE) {
 171       throw new Error("Unsupported");
 172     } else if (fn.getTaskType()==FlatFlagActionNode.TASKEXIT) {
 173       evalTaskExitNode(fn, table);
 174     } else if (fn.getTaskType()==FlatFlagActionNode.NEWOBJECT) {
 175       evalNewNode(fn, table, td);
 176     }
 177   }
 178
 179   private void setFlag(ObjWrapper ow, FlagDescriptor fd, boolean value) {
 180     HashSet<FlagState> newstate=new HashSet<FlagState>();
 181     Hashtable<FlagState, FlagState> flagmap=new Hashtable<FlagState, FlagState>();
 182     for(Iterator<FlagState> flagit=ow.fs.iterator(); flagit.hasNext(); ) {
 183       FlagState fs=flagit.next();
 184       FlagState fsnew=canonical(fs.setFlag(fd, value));
 185       newstate.add(fsnew);
 186       flagmap.put(fs, fsnew);
 187     }
 188
 189     for(Iterator<TagWrapper> tagit=ow.tags.iterator(); tagit.hasNext(); ) {
 190       TagWrapper tw=tagit.next();
 191       HashSet<TagState> newstates=new HashSet<TagState>();
 192       for(Iterator<TagState> tgit=tw.ts.iterator(); tgit.hasNext(); ) {
 193         TagState ts=tgit.next();
 194         for(Iterator<FlagState> flagit=ts.getFS().iterator(); flagit.hasNext(); ) {
 195           FlagState fs=flagit.next();
 196           if (flagmap.containsKey(fs)) {
 197             if (flagmap.get(fs).equals(fs)) {
 198               newstates.add(ts);
 199             } else {
 200               TagState tsarray[]=ts.clearFS(fs);
 201               //Can do strong update here because these
 202               //must be parameter objects...therefore
 203               //all possible aliasing relationships are
 204               //explored
 205               for(int i=0; i<tsarray.length; i++) {
 206                 TagState ts2=canonical(tsarray[i]);
 207                 TagState tsarray2[]=ts2.addnewFS(flagmap.get(fs));
 208                 for(int j=0; j<tsarray2.length; j++)
 209                   newstates.add(canonical(tsarray2[j]));
 210               }
 211             }
 212           }
 213         }
 214       }
 215       tw.ts=newstates;
 216     }
 217   }
 218
 219   private void setTag(ObjWrapper ow, TagWrapper twnew, TagDescriptor tag, boolean value) {
 220     if (value) {
 221       if (ow.tags.contains(twnew)) {
 222         System.out.println("Tag already bound to object.");
 223         return;
 224       }
 225     } else {
 226       if (!ow.tags.contains(twnew)) {
 227         System.out.println("Tag not bound to object.");
 228         return;
 229       }
 230     }
 231     HashSet<FlagState> newfsstates=new HashSet<FlagState>();
 232     Hashtable<FlagState, FlagState[]> flagmap=new Hashtable<FlagState, FlagState[]>();
 233     //Change the flag states
 234     for(Iterator<FlagState> fsit=ow.fs.iterator(); fsit.hasNext(); ) {
 235       FlagState fs=fsit.next();
 236       FlagState[] fsnew=canonical(fs.setTag(tag, value));
 237       flagmap.put(fs, fsnew);
 238       newfsstates.addAll(Arrays.asList(fsnew));
 239     }
 240     for(Iterator<TagWrapper> tagit=ow.tags.iterator(); tagit.hasNext(); ) {
 241       TagWrapper tw=tagit.next();
 242       HashSet<TagState> newstates=new HashSet<TagState>();
 243       for(Iterator<TagState> tgit=tw.ts.iterator(); tgit.hasNext(); ) {
 244         TagState ts=tgit.next();
 245         for(Iterator<FlagState> flagit=ts.getFS().iterator(); flagit.hasNext(); ) {
 246           FlagState fs=flagit.next();
 247           if (flagmap.containsKey(fs)) {
 248             FlagState[] fmap=flagmap.get(fs);
 249             for(int i=0; i<fmap.length; i++) {
 250               FlagState fsnew=fmap[i];
 251               if (fsnew.equals(fs)) {
 252                 newstates.add(ts);
 253               } else {
 254                 TagState tsarray[]=ts.clearFS(fs);
 255                 //Can do strong update here because
 256                 //these must be parameter
 257                 //objects...therefore all possible
 258                 //aliasing relationships are explored
 259                 for(int j=0; j<tsarray.length; j++) {
 260                   TagState ts2=canonical(tsarray[j]);
 261                   TagState tsarray2[]=ts2.addnewFS(fsnew);
 262                   for(int k=0; k<tsarray2.length; k++)
 263                     newstates.add(canonical(tsarray2[k]));
 264                 }
 265               }
 266             }
 267           }
 268         }
 269       }
 270       tw.ts=newstates;
 271     }
 272
 273     {
 274       HashSet<TagState> newstates=new HashSet<TagState>();
 275       for(Iterator<TagState> tgit=twnew.ts.iterator(); tgit.hasNext(); ) {
 276         TagState ts=tgit.next();
 277         for(Iterator<FlagState> flagit=newfsstates.iterator(); flagit.hasNext(); ) {
 278           FlagState fsnew=flagit.next();
 279           //Can do strong update here because these must
 280           //be parameter objects...therefore all
 281           //possible aliasing relationships are explored
 282           TagState tsarray2[];
 283           if (value)
 284             tsarray2=ts.addnewFS(fsnew);
 285           else
 286             tsarray2=ts.clearFS(fsnew);
 287           for(int j=0; j<tsarray2.length; j++)
 288             newstates.add(canonical(tsarray2[j]));
 289         }
 290       }
 291       twnew.ts=newstates;
 292     }
 293
 294     if (value)
 295       ow.tags.add(twnew);
 296     else
 297       ow.tags.remove(twnew);
 298     ow.fs=newfsstates;
 299   }
 300
 301   private void evalTaskExitNode(FlatFlagActionNode fn, Hashtable<TempDescriptor, Wrapper> table) {
 302     //Process clears first
 303     for(Iterator<TempTagPair> it_ttp=fn.getTempTagPairs(); it_ttp.hasNext(); ) {
 304       TempTagPair ttp=it_ttp.next();
 305       TempDescriptor tmp=ttp.getTemp();
 306       TagDescriptor tag=ttp.getTag();
 307       TempDescriptor tagtmp=ttp.getTagTemp();
 308       TagWrapper tagw=(TagWrapper)table.get(tagtmp);
 309       boolean newtagstate=fn.getTagChange(ttp);
 310       ObjWrapper ow=(ObjWrapper)table.get(tmp);
 311       if (!newtagstate)
 312         setTag(ow, tagw, tag, newtagstate);
 313     }
 314
 315     //Do the flags next
 316     for(Iterator<TempFlagPair> it_tfp=fn.getTempFlagPairs(); it_tfp.hasNext(); ) {
 317       TempFlagPair tfp=it_tfp.next();
 318       TempDescriptor tmp=tfp.getTemp();
 319       FlagDescriptor fd=tfp.getFlag();
 320       boolean newflagstate=fn.getFlagChange(tfp);
 321       ObjWrapper ow=(ObjWrapper)table.get(tmp);
 322       setFlag(ow, fd, newflagstate);
 323     }
 324
 325     //Process sets last
 326     for(Iterator it_ttp=fn.getTempTagPairs(); it_ttp.hasNext(); ) {
 327       TempTagPair ttp=(TempTagPair)it_ttp.next();
 328       TempDescriptor tmp=ttp.getTemp();
 329       TagDescriptor tag=ttp.getTag();
 330       TempDescriptor tagtmp=ttp.getTagTemp();
 331       TagWrapper tagw=(TagWrapper)table.get(tagtmp);
 332       boolean newtagstate=fn.getTagChange(ttp);
 333       ObjWrapper ow=(ObjWrapper)table.get(tmp);
 334       if (newtagstate)
 335         setTag(ow, tagw, tag, newtagstate);
 336     }
 337   }
 338
 339   private void evalNewNode(FlatFlagActionNode fn, Hashtable<TempDescriptor, Wrapper> table, TaskDescriptor td) {
 340     TempDescriptor fntemp=null;
 341     {
 342       /* Compute type */
 343       Iterator it=fn.getTempFlagPairs();
 344       if (it.hasNext()) {
 345         TempFlagPair tfp=(TempFlagPair)it.next();
 346         fntemp=tfp.getTemp();
 347       } else {
 348         it=fn.getTempTagPairs();
 349         if (!it.hasNext())
 350           throw new Error();
 351         TempTagPair ttp=(TempTagPair)it.next();
 352         fntemp=ttp.getTemp();
 353       }
 354     }
 355     FlagState fs=canonical(new FlagState(fntemp.getType().getClassDesc()));
 356     ObjWrapper ow=new ObjWrapper();
 357     ow.fs.add(fs);
 358     table.put(fntemp, ow);
 359     //Do the flags first
 360     for(Iterator<TempFlagPair> it_tfp=fn.getTempFlagPairs(); it_tfp.hasNext(); ) {
 361       TempFlagPair tfp=it_tfp.next();
 362       TempDescriptor tmp=tfp.getTemp();
 363       FlagDescriptor fd=tfp.getFlag();
 364       boolean newflagstate=fn.getFlagChange(tfp);
 365       assert(ow==table.get(tmp));
 366       setFlag(ow, fd, newflagstate);
 367     }
 368     //Process sets next
 369     for(Iterator it_ttp=fn.getTempTagPairs(); it_ttp.hasNext(); ) {
 370       TempTagPair ttp=(TempTagPair)it_ttp.next();
 371       TempDescriptor tmp=ttp.getTemp();
 372       TagDescriptor tag=ttp.getTag();
 373       TempDescriptor tagtmp=ttp.getTagTemp();
 374       TagWrapper tagw=(TagWrapper)table.get(tagtmp);
 375       boolean newtagstate=fn.getTagChange(ttp);
 376       assert(ow==table.get(tmp));
 377       if (newtagstate)
 378         setTag(ow, tagw, tag, newtagstate);
 379       else
 380         throw new Error("Can't clear tag in newly allocated object");
 381     }
 382     for(Iterator<FlagState> fsit=ow.fs.iterator(); fsit.hasNext(); ) {
 383       FlagState fs2=fsit.next();
 384       fs2.addAllocatingTask(td);
 385       TagState ts2=new TagState(fs2.getClassDescriptor());
 386       ts2.addFS(fs2);
 387       ts2=canonical(ts2);
 388       ts2.addSource(td);
 389       addresult(fs2.getClassDescriptor(), ts2);
 390       if (!discovered.contains(ts2)) {
 391         discovered.add(ts2);
 392         toprocess.add(ts2);
 393       }
 394     }
 395   }
 396
 397   private void processFlatTag(FlatTagDeclaration fn, Hashtable<TempDescriptor, Wrapper> table, TaskDescriptor td) {
 398     TempDescriptor tmp=fn.getDst();
 399     if (table.containsKey(tmp)) {
 400       recordtagchange((TagWrapper)table.get(tmp), td);
 401     }
 402     TagDescriptor tag=fn.getType();
 403     TagState ts=canonical(new TagState(tag));
 404     TagWrapper tw=new TagWrapper(ts);
 405     tw.initts=null;
 406     table.put(tmp, tw);
 407   }
 408
 409   private void addresult(TagDescriptor td, TagState ts) {
 410     if (!tsresults.containsKey(td))
 411       tsresults.put(td, new HashSet<TagState>());
 412     tsresults.get(td).add(ts);
 413   }
 414
 415   private void addresult(ClassDescriptor cd, TagState ts) {
 416     if (!fsresults.containsKey(cd))
 417       fsresults.put(cd, new HashSet<TagState>());
 418     fsresults.get(cd).add(ts);
 419   }
 420
 421   public void recordtagchange(TagWrapper tw, TaskDescriptor td) {
 422     TagState init=tw.initts;
 423     for(Iterator<TagState> tsit=tw.ts.iterator(); tsit.hasNext(); ) {
 424       TagState ts=tsit.next();
 425       if (init==null) {
 426         ts.addSource(td);
 427       } else {
 428         TagEdge te=new TagEdge(ts, td);
 429         if (!init.containsEdge(te)) {
 430           init.addEdge(te);
 431         }
 432       }
 433       if (ts.getTag()!=null)
 434         addresult(ts.getTag(), ts);
 435       else
 436         addresult(ts.getClassDesc(), ts);
 437       if (!discovered.contains(ts)) {
 438         discovered.add(ts);
 439         toprocess.add(ts);
 440       }
 441     }
 442   }
 443
 444   private void recordobj(ObjWrapper ow, TaskDescriptor td) {
 445     for(Iterator<TagWrapper> twit=ow.tags.iterator(); twit.hasNext(); ) {
 446       TagWrapper tw=twit.next();
 447       recordtagchange(tw, td);
 448     }
 449   }
 450
 451   private void processFlatCall(FlatCall fc, Hashtable<TempDescriptor, Wrapper> table) {
 452     //Do nothing for now
 453   }
 454
 455   private void processFlatReturnNode(FlatReturnNode fr, Hashtable<TempDescriptor, Wrapper> table, TaskDescriptor td) {
 456     for(Iterator<TempDescriptor> tmpit=table.keySet().iterator(); tmpit.hasNext(); ) {
 457       TempDescriptor tmp=tmpit.next();
 458       Wrapper w=table.get(tmp);
 459       if (w instanceof TagWrapper) {
 460         TagWrapper tw=(TagWrapper)w;
 461         recordtagchange(tw, td);
 462       } else {
 463         ObjWrapper ow=(ObjWrapper)w;
 464         recordobj(ow, td);
 465       }
 466     }
 467   }
 468
 469   private boolean equivalent(Hashtable<TempDescriptor, Wrapper> table1, Hashtable<TempDescriptor, Wrapper> table2) {
 470     Hashtable<Wrapper, Wrapper> emap=new Hashtable<Wrapper, Wrapper>();
 471
 472     if (table1.keySet().size()!=table2.keySet().size())
 473       return false;
 474
 475     for(Iterator<TempDescriptor> tmpit=table1.keySet().iterator(); tmpit.hasNext(); ) {
 476       TempDescriptor tmp=tmpit.next();
 477       if (table2.containsKey(tmp)) {
 478         emap.put(table1.get(tmp), table2.get(tmp));
 479       } else return false;
 480     }
 481
 482     for(Iterator<TempDescriptor> tmpit=table1.keySet().iterator(); tmpit.hasNext(); ) {
 483       TempDescriptor tmp=tmpit.next();
 484       Wrapper w1=table1.get(tmp);
 485       Wrapper w2=table2.get(tmp);
 486       if (w1 instanceof TagWrapper) {
 487         TagWrapper t1=(TagWrapper)w1;
 488         TagWrapper t2=(TagWrapper)w2;
 489         if (!t1.ts.equals(t2.ts))
 490           return false;
 491
 492       } else {
 493         ObjWrapper t1=(ObjWrapper)w1;
 494         ObjWrapper t2=(ObjWrapper)w2;
 495         if (!t1.fs.equals(t2.fs))
 496           return false;
 497         if (t1.tags.size()!=t2.tags.size())
 498           return false;
 499         for(Iterator<TagWrapper> twit=t1.tags.iterator(); twit.hasNext(); ) {
 500           TagWrapper tw1=twit.next();
 501           if (!t2.tags.contains(emap.get(tw1)))
 502             return false;
 503         }
 504       }
 505     }
 506     return true;
 507   }
 508
 509   private void doAnalysis(TaskBinding tb) {
 510     TaskDescriptor td=tb.tqi.tq.getTask();
 511     FlatMethod fm=state.getMethodFlat(td);
 512     Hashtable<FlatNode, Hashtable<TempDescriptor, Wrapper>> wtable=new Hashtable<FlatNode, Hashtable<TempDescriptor, Wrapper>>();
 513     wtable.put(fm, buildinittable(tb, fm));
 514     HashSet<FlatNode> visited=new HashSet<FlatNode>();
 515     HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
 516     tovisit.add(fm.getNext(0));
 517     while(!tovisit.isEmpty()) {
 518       FlatNode fn=tovisit.iterator().next();
 519       tovisit.remove(fn);
 520       visited.add(fn);
 521       Hashtable<TempDescriptor, Wrapper> table=computeInitialState(wtable, fn);
 522       switch(fn.kind()) {
 523       case FKind.FlatFlagActionNode:
 524         processFlatFlag((FlatFlagActionNode)fn, table, td);
 525         break;
 526
 527       case FKind.FlatTagDeclaration:
 528         processFlatTag((FlatTagDeclaration)fn, table, td);
 529         break;
 530
 531       case FKind.FlatCall:
 532         processFlatCall((FlatCall)fn, table);
 533         break;
 534
 535       case FKind.FlatReturnNode:
 536         processFlatReturnNode((FlatReturnNode)fn, table, td);
 537         break;
 538
 539       default:
 540       }
 541
 542       if (!equivalent(table, wtable.get(fn))) {
 543         wtable.put(fn, table);
 544         for(int i=0; i<fn.numNext(); i++) {
 545           tovisit.add(fn.getNext(i));
 546         }
 547       } else {
 548         for(int i=0; i<fn.numNext(); i++) {
 549           if (!visited.contains(fn.getNext(i)))
 550             tovisit.add(fn.getNext(i));
 551         }
 552       }
 553     }
 554
 555   }
 556
 557   private Hashtable<TempDescriptor, Wrapper> buildinittable(TaskBinding tb, FlatMethod fm) {
 558     Hashtable<TempDescriptor, Wrapper> table=new Hashtable<TempDescriptor, Wrapper>();
 559     Vector<TempDescriptor> tagtmps=tb.tqi.tq.tags;
 560     for(int i=0; i<tagtmps.size(); i++) {
 561       TempDescriptor tmp=tagtmps.get(i);
 562       table.put(tmp, tb.getTag(tmp));
 563     }
 564     for(int i=0; i<fm.numParameters(); i++) {
 565       TempDescriptor tmp=fm.getParameter(i);
 566       table.put(tmp, tb.getParameter(i));
 567     }
 568     return table;
 569   }
 570
 571   /*
 572      method summary:
 573      new flag states created
 574      new tag states created
 575      flag states bound to tag parameters
 576    */
 577
 578   public boolean canEnqueue(TaskDescriptor td, int paramnum, FlagState fs) {
 579     return typeutil.isSuperorType(td.getParamType(paramnum).getClassDesc(),fs.getClassDescriptor())&&
 580            isTaskTrigger_flag(td.getFlag(td.getParameter(paramnum)),fs)&&
 581            isTaskTrigger_tag(td.getTag(td.getParameter(paramnum)),fs);
 582   }
 583
 584   private static boolean isTaskTrigger_flag(FlagExpressionNode fen, FlagState fs) {
 585     if (fen==null)
 586       return true;
 587     else if (fen instanceof FlagNode)
 588       return fs.get(((FlagNode)fen).getFlag());
 589     else
 590       switch (((FlagOpNode)fen).getOp().getOp()) {
 591       case Operation.LOGIC_AND:
 592         return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 593
 594       case Operation.LOGIC_OR:
 595         return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 596
 597       case Operation.LOGIC_NOT:
 598         return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
 599
 600       default:
 601         return false;
 602       }
 603   }
 604
 605
 606   private static boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs) {
 607     if (tel!=null) {
 608       for (int i=0; i<tel.numTags(); i++) {
 609         switch (fs.getTagCount(tel.getType(i))) {
 610         case FlagState.ONETAG:
 611         case FlagState.MULTITAGS:
 612           break;
 613
 614         case FlagState.NOTAGS:
 615           return false;
 616         }
 617       }
 618     }
 619     return true;
 620   }
 621
 622   TagState createInitialState() {
 623     ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
 624     FlagDescriptor fd=(FlagDescriptor)startupobject.getFlagTable().get(FlagDescriptor.InitialFlag);
 625     FlagState fsstartup=(new FlagState(startupobject)).setFlag(fd,true);
 626     fsstartup.setAsSourceNode();
 627     fsstartup=canonical(fsstartup);
 628     TagState ts=new TagState(startupobject);
 629     TagState[] tsarray=ts.addFS(fsstartup);
 630     return canonical(tsarray[0]);
 631   }
 632
 633   FlagState[] canonical(FlagState[] fs) {
 634     FlagState[] fsarray=new FlagState[fs.length];
 635     for(int i=0; i<fs.length; i++)
 636       fsarray[i]=canonical(fs[i]);
 637     return fsarray;
 638   }
 639
 640   FlagState canonical(FlagState fs) {
 641     return fs;
 642   }
 643
 644   TagState canonical(TagState ts) {
 645     return ts;
 646   }
 647
 648
 649 }
 650