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