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     Hashtable<TaskDescriptor, TaskQueue> tasktable;
  17
  18
  19     /**
  20      * Class Constructor
  21      *
  22      */
  23     public TaskTagAnalysis(State state, TagAnalysis taganalysis) {
  24         this.state=state;
  25         this.typeutil=new TypeUtil(state);
  26         this.taganalysis=taganalysis;
  27         this.flaginfo=new FlagInfo(state);
  28         this.toprocess=new HashSet<TagState>();
  29         this.tasktable=new Hashtable<TaskDescriptor, TaskQueue>();
  30         for(Iterator taskit=state.getTaskSymbolTable().getDescriptorsIterator();taskit.hasNext();) {
  31             TaskDescriptor td=(TaskDescriptor)taskit.next();
  32             tasktable.put(td, new TaskQueue(td));
  33         }
  34     }
  35
  36     private void doAnalysis() {
  37         toprocess.add(createInitialState());
  38         while(!toprocess.isEmpty()) {
  39             TagState ts=toprocess.iterator().next();
  40             toprocess.remove(ts);
  41             //Loop through each task
  42             for(Iterator taskit=state.getTaskSymbolTable().getDescriptorsIterator();taskit.hasNext();) {
  43                 TaskDescriptor td=(TaskDescriptor)taskit.next();
  44                 TaskQueue tq=tasktable.get(td);
  45                 processTask(td, tq, ts);
  46             }
  47         }
  48     }
  49
  50     private void processTask(TaskDescriptor td, TaskQueue tq, TagState ts) {
  51         Set<FlagState> flagset=ts.getFS();
  52         for(Iterator<FlagState> fsit=flagset.iterator();fsit.hasNext();) {
  53             FlagState fs=fsit.next();
  54             FlagTagState fts=new FlagTagState(ts, fs);
  55             for(int i=0;i<td.numParameters();i++) {
  56                 if (canEnqueue(td, i, fs)) {
  57                     TaskQueueIterator tqi=tq.enqueue(i, fts);
  58                     while(tqi.hasNext()) {
  59                         processBinding(tqi);
  60                         tqi.next();
  61                     }
  62                 }
  63             }
  64         }
  65     }
  66
  67     private void processBinding(TaskQueueIterator tqi) {
  68         TaskBinding tb=new TaskBinding(tqi);
  69         while(tb.hasNext()) {
  70             doAnalysis(tb);
  71             tb.next();
  72         }
  73     }
  74
  75     private Hashtable<TempDescriptor, Wrapper> computeInitialState(Hashtable<FlatNode, Hashtable<TempDescriptor, Wrapper>> maintable, FlatNode fn) {
  76         Hashtable<TempDescriptor, Wrapper> table=new Hashtable<TempDescriptor, Wrapper>();
  77         Hashtable<TagWrapper,TagWrapper> tagtable=new Hashtable<TagWrapper, TagWrapper>();
  78         for(int i=0;i<fn.numPrev();i++) {
  79             FlatNode fnprev=fn.getPrev(i);
  80             Hashtable<TempDescriptor, Wrapper> prevtable=maintable.get(fn);
  81
  82             //Iterator through the Tags
  83             for(Iterator<TempDescriptor> tmpit=prevtable.keySet().iterator();tmpit.hasNext();) {
  84                 TempDescriptor tmp=tmpit.next();
  85                 Wrapper prevtag=prevtable.get(tmp);
  86                 if (prevtag instanceof ObjWrapper)
  87                     continue;
  88                 if (table.containsKey(tmp)) {
  89                     //merge tag states
  90                     TagWrapper currtag=(TagWrapper) table.get(tmp);
  91                     tagtable.put((TagWrapper)prevtag, currtag);
  92                     assert(currtag.initts.equals(((TagWrapper)prevtag).initts));
  93                     for(Iterator<TagState> tagit=((TagWrapper)prevtag).ts.iterator();tagit.hasNext();) {
  94                         TagState tag=tagit.next();
  95                         if (!currtag.ts.contains(tag)) {
  96                             currtag.ts.add(tag);
  97                         }
  98                     }
  99                 } else {
 100                     TagWrapper clonetag=prevtag.clone();
 101                     tagtable.put(prevtag, clonetag);
 102                     table.put(tmp, clonetag);
 103                 }
 104             }
 105
 106             //Iterator through the Objects
 107             for(Iterator<TempDescriptor> tmpit=prevtable.keySet().iterator();tmpit.hasNext();) {
 108                 TempDescriptor tmp=tmpit.next();
 109                 Wrapper obj=prevtable.get(tmp);
 110                 if (obj instanceof TagWrapper)
 111                     continue;
 112                 ObjWrapper prevobj=(ObjWrapper)obj;
 113                 if (table.containsKey(tmp)) {
 114                     //merge tag states
 115                     ObjWrapper newobj=new ObjWrapper(prevobj.fs);
 116                     table.put(tmp, newobj);
 117                 }
 118                 ObjWrapper currobj=(ObjWrapper) table.get(tmp);
 119                 for(int j=0;j<prevobj.tags.size();j++) {
 120                     TagWrapper t=tagtable.get(prevobj.tags.get(j));
 121                     if (!currobj.tags.contains(t))
 122                         currobj.tags.add(t);
 123                 }
 124             }
 125         }
 126         return table;
 127     }
 128
 129     private void processFlatFlag(FlatFlagActionNode fn, Hashtable<TempDescriptor, TagState> table) {
 130
 131     }
 132
 133     private void processFlatCall(FlatCall fc, Hashtable<TempDescriptor, TagState> table) {
 134         //Do nothing for now
 135     }
 136
 137     private void processFlatReturnNode(FlatReturnNode fr, Hashtable<TempDescriptor, TagState> table) {
 138
 139     }
 140
 141     private boolean equivalent(Hashtable<TempDescriptor, Wrapper> table1, Hashtable<TempDescriptor, Wrapper> table2) {
 142         Hashtable<Wrapper, Wrapper> emap=new Hashtable<Wrapper, Wrapper>;
 143         for(Iterator<TempDescriptor> tmpit=table1.keySet().iterator();tmpit.hasNext();) {
 144             TempDescriptor tmp=tmpit.next();
 145             if (table2.containsKey(tmp)) {
 146                 emap.put(table1.get(tmp), table2.get(tmp));
 147             } else return false;
 148         }
 149         for(Iterator<TempDescriptor> tmpit=table2.keySet().iterator();tmpit.hasNext();) {
 150             TempDescriptor tmp=tmpit.next();
 151             if (table1.containsKey(tmp)) {
 152                 emap.put(table1.get(tmp), table2.get(tmp));
 153             } else return false;
 154         }
 155
 156         for
 157
 158     }
 159
 160     private void doAnalysis(TaskBinding tb) {
 161         TaskDescriptor td=tb.tqi.tq.getTask();
 162         FlatMethod fm=state.getMethodFlat(td);
 163         Hashtable<FlatNode, Hashtable<TempDescriptor, Wrapper>> wtable=new Hashtable<FlatNode, Hashtable<TempDescriptor, Wrapper>>();
 164         wtable.put(fm, buildinittable(tb));
 165         HashSet<FlatNode> visited=new HashSet<FlatNode>();
 166         HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
 167         tovisit.add(fm.getNext(0));
 168         while(!tovisit.isEmpty()) {
 169             FlatNode fn=tovisit.iterator().next();
 170             tovisit.remove(fn);
 171             visited.add(fn);
 172             Hashtable<TempDescriptor, Wrapper> table=computeInitialState(wtable, fn);
 173             switch(fn.kind()) {
 174             case FKind.FlatFlagActionNode:
 175                 processFlatFlag((FlatFlagActionNode)fn, table);
 176                 break;
 177             case FKind.FlatCall:
 178                 processFlatCall((FlatCall)fn, table);
 179                 break;
 180             case FKind.FlatReturnNode:
 181                 processFlatReturnNode((FlatReturn)fn, table);
 182                 break;
 183             default:
 184             }
 185
 186             if (!equivalent(table, wtable.get(fn))) {
 187                 wtable.put(fn, table);
 188                 for(int i=0;i<fn.numNext();i++) {
 189                     tovisit.add(fn.getNext(i));
 190                 }
 191             } else {
 192                 for(int i=0;i<fn.numNext();i++) {
 193                     if (!visited.contains(fn.getNext(i)))
 194                         tovisit.add(fn.getNext(i));
 195                 }
 196             }
 197         }
 198
 199     }
 200
 201     private Hashtable<TempDescriptor, Wrapper> buildinittable(TaskBinding tb, FlatMethod fm) {
 202         Hashtable<TempDescriptor, Wrapper> table=new Hashtable<TempDescriptor, Wrapper>();
 203         Vector<TempDescriptor> tagtmps=tb.tqi.tq.tags;
 204         for(int i=0;i<tagtmps.size();i++) {
 205             TempDescriptor tmp=tagtmps.get(i);
 206             table.put(tmp, tb.getTag(tmp));
 207         }
 208         for(int i=0;i<fm.numParameters();i++) {
 209             TempDescriptor tmp=fm.getParameter(i);
 210             table.put(tmp, tb.getParameter(i));
 211         }
 212         return table;
 213     }
 214
 215     /*
 216       method summary:
 217       new flag states created
 218       new tag states created
 219       flag states bound to tag parameters
 220     */
 221
 222     public boolean canEnqueue(TaskDescriptor td, int paramnum, FlagState fs) {
 223         return typeutil.isSuperorType(td.getParamType(paramnum).getClassDesc(),fs.getClassDescriptor())&&
 224             isTaskTrigger_flag(td.getFlag(td.getParameter(paramnum)),fs)&&
 225             isTaskTrigger_tag(td.getTag(td.getParameter(paramnum)),fs);
 226     }
 227
 228     private static boolean isTaskTrigger_flag(FlagExpressionNode fen, FlagState fs) {
 229         if (fen==null)
 230             return true;
 231         else if (fen instanceof FlagNode)
 232             return fs.get(((FlagNode)fen).getFlag());
 233         else
 234             switch (((FlagOpNode)fen).getOp().getOp()) {
 235             case Operation.LOGIC_AND:
 236                 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 237             case Operation.LOGIC_OR:
 238                 return ((isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger_flag(((FlagOpNode)fen).getRight(),fs)));
 239             case Operation.LOGIC_NOT:
 240                 return !(isTaskTrigger_flag(((FlagOpNode)fen).getLeft(),fs));
 241             default:
 242                 return false;
 243             }
 244     }
 245
 246
 247     private static boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){
 248         if (tel!=null){
 249             for (int i=0;i<tel.numTags() ; i++){
 250                 switch (fs.getTagCount(tel.getType(i))){
 251                 case FlagState.ONETAG:
 252                 case FlagState.MULTITAGS:
 253                     break;
 254                 case FlagState.NOTAGS:
 255                     return false;
 256                 }
 257             }
 258         }
 259         return true;
 260     }
 261
 262     TagState createInitialState() {
 263         ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
 264         FlagDescriptor fd=(FlagDescriptor)startupobject.getFlagTable().get(FlagDescriptor.InitialFlag);
 265         FlagState fsstartup=(new FlagState(startupobject)).setFlag(fd,true);
 266         fsstartup.setAsSourceNode();
 267         fsstartup=canonical(fsstartup);
 268         TagState ts=new TagState();
 269         TagState[] tsarray=ts.addFS(fsstartup);
 270         return canonical(tsarray[0]);
 271     }
 272
 273     FlagState canonical(FlagState fs) {
 274         return fs;
 275     }
 276
 277     TagState canonical(TagState ts) {
 278         return ts;
 279     }
 280
 281
 282 }
 283