Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.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.File;
   8 import java.io.FileOutputStream;
   9
  10 public class TaskAnalysis {
  11     State state;
  12     Hashtable flagstates;
  13     Hashtable flags;
  14     Hashtable extern_flags;
  15     Queue<FlagState> q_main;
  16     Hashtable map;
  17     TempDescriptor temp;
  18     TypeUtil typeutil;
  19
  20     /**
  21      * Class Constructor
  22      *
  23      * @param state a flattened State object
  24      * @see State
  25      * @param map Hashtable containing the temp to var mapping
  26      */
  27     public TaskAnalysis(State state,Hashtable map)
  28     {
  29         this.state=state;
  30         this.map=map;
  31         this.typeutil=new TypeUtil(state);
  32     }
  33
  34     /** This function builds a table of flags for each class **/
  35
  36     private void getFlagsfromClasses() {
  37         flags=new Hashtable();
  38         extern_flags = new Hashtable();
  39
  40         for(Iterator it_classes=state.getClassSymbolTable().getDescriptorsIterator();it_classes.hasNext();) {
  41
  42             ClassDescriptor cd = (ClassDescriptor)it_classes.next();
  43             System.out.println(cd.getSymbol());
  44             Vector vFlags=new Vector();
  45             FlagDescriptor flag[];
  46             int ctr=0;
  47
  48
  49             /* Adding the flags of the super class */
  50             if (cd.getSuper()!=null) {
  51                 ClassDescriptor superdesc=cd.getSuperDesc();
  52
  53                 for(Iterator it_cflags=superdesc.getFlags();it_cflags.hasNext();) {
  54                     FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
  55                     System.out.println(fd.toString());
  56                     vFlags.add(fd);
  57                 }
  58             }
  59
  60             for(Iterator it_cflags=cd.getFlags();it_cflags.hasNext();) {
  61                 FlagDescriptor fd = (FlagDescriptor)it_cflags.next();
  62                 System.out.println(fd.toString());
  63                 vFlags.add(fd);
  64             }
  65
  66             if (vFlags.size()!=0) {
  67                 flag=new FlagDescriptor[vFlags.size()];
  68
  69                 for(int i=0;i < vFlags.size() ; i++) {
  70                     if (((FlagDescriptor)vFlags.get(i)).getExternal()) {
  71                         flag[ctr]=(FlagDescriptor)vFlags.get(i);
  72                         vFlags.remove(flag[ctr]);
  73                         ctr++;
  74                     }
  75                 }
  76                 for(int i=0;i < vFlags.size() ; i++) {
  77                     flag[i+ctr]=(FlagDescriptor)vFlags.get(i);
  78                 }
  79                 extern_flags.put(cd,new Integer(ctr));
  80                 flags.put(cd,flag);
  81
  82             }
  83         }
  84     }
  85
  86     public void taskAnalysis() throws java.io.IOException {
  87         flagstates=new Hashtable();
  88         Hashtable<FlagState,FlagState> sourcenodes;
  89
  90         getFlagsfromClasses();
  91
  92         int externs;
  93         q_main=new LinkedList<FlagState>();
  94
  95         for(Iterator it_classes=(Iterator)flags.keys();it_classes.hasNext();) {
  96             ClassDescriptor cd=(ClassDescriptor)it_classes.next();
  97             externs=((Integer)extern_flags.get(cd)).intValue();
  98             FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
  99
 100             //Debug block
 101             System.out.println("Inside taskAnalysis;\n Class:"+ cd.getSymbol());
 102             System.out.println("No of externs " + externs);
 103             System.out.println("No of flags: "+fd.length);
 104             //Debug block
 105
 106            flagstates.put(cd,new Hashtable<FlagState,FlagState>());
 107         }
 108
 109
 110         ClassDescriptor startupobject=typeutil.getClass(TypeUtil.StartupClass);
 111
 112         sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(startupobject);
 113
 114         FlagState fsstartup=new FlagState(startupobject);
 115         FlagDescriptor[] fd=(FlagDescriptor[])flags.get(startupobject);
 116
 117         fsstartup=fsstartup.setFlag(fd[0],true);
 118
 119         sourcenodes.put(fsstartup,fsstartup);
 120
 121         Queue<FlagState> q_temp=analyseTasks(fsstartup);
 122
 123         if ( q_temp != null) {
 124                 q_main.addAll(q_temp);
 125         }
 126
 127         while (q_main.size() > 0) {
 128             // ****debug block********
 129
 130             System.out.println("/***********contents of main q before pop**********/");
 131             for (Iterator it_qm=q_main.iterator();it_qm.hasNext();)
 132                 {
 133
 134                     FlagState fs_qm=(FlagState)it_qm.next();
 135
 136                     System.out.println("FS : "+fs_qm.getClassDescriptor().toString()+" : "+fs_qm.toString((FlagDescriptor [])flags.get(fs_qm.getClassDescriptor())));
 137                 }
 138             System.out.println("/*********************************/");
 139             // ****debug block********
 140             FlagState trigger=q_main.poll();
 141
 142
 143             q_temp=createPossibleRuntimeStates(trigger);
 144
 145             if ( q_temp != null){
 146                     q_main.addAll(q_temp);
 147
 148                 // ****debug block********
 149
 150             System.out.println("/***********contents of main q**********/");
 151             for (Iterator it_qm=q_main.iterator();it_qm.hasNext();)
 152                 {
 153
 154                     FlagState fs_qm=(FlagState)it_qm.next();
 155
 156                     System.out.println("FS : "+fs_qm.getClassDescriptor().toString()+" : "+fs_qm.toString((FlagDescriptor [])flags.get(fs_qm.getClassDescriptor())));
 157                 }
 158             System.out.println("/*********************************/");
 159             // ****debug block********
 160
 161             q_temp=analyseTasks(trigger);
 162
 163             if ( q_temp != null)
 164                         q_main.addAll(q_temp);
 165
 166                 // ****debug block********
 167
 168             System.out.println("/***********contents of main q after analyse tasks**********/");
 169             for (Iterator it_qm=q_main.iterator();it_qm.hasNext();)
 170                 {
 171
 172                     FlagState fs_qm=(FlagState)it_qm.next();
 173
 174                     System.out.println("FS : "+fs_qm.getClassDescriptor().toString()+" : "+fs_qm.toString((FlagDescriptor [])flags.get(fs_qm.getClassDescriptor())));
 175                 }
 176             System.out.println("/*********************************/");
 177             // ****debug block********
 178
 179         }
 180         }
 181
 182         //Creating DOT files
 183         Enumeration e=flagstates.keys();
 184
 185         while (e.hasMoreElements()) {
 186             System.out.println("creating dot file");
 187             ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
 188             System.out.println((cdtemp.getSymbol()));
 189             createDOTfile(cdtemp);
 190         }
 191
 192
 193         }
 194
 195
 196     public Queue<FlagState> analyseTasks(FlagState fs) throws java.io.IOException {
 197
 198
 199         Hashtable<FlagState,FlagState> sourcenodes;
 200         Queue<FlagState> q_retval;
 201
 202
 203
 204         ClassDescriptor cd=fs.getClassDescriptor();
 205
 206         sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 207
 208         int externs=((Integer)extern_flags.get(cd)).intValue();
 209         FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
 210
 211         q_retval=new LinkedList<FlagState>();
 212         //***Debug Block***
 213
 214         //while (q.size() != 0) {
 215             System.out.println("inside while loop in analysetasks \n");
 216
 217             //***Debug Block***
 218             //FlagDescriptor[] ftemp=(FlagDescriptor[])flags.get(cd);
 219             //System.out.println("Processing state: "+cd.getSymbol()+" " + fsworking.toString(ftemp));
 220             //***Debug Block***
 221
 222
 223             for(Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();it_tasks.hasNext();) {
 224                 TaskDescriptor td = (TaskDescriptor)it_tasks.next();
 225                 boolean taskistriggered=false;
 226                 int trigger_ctr=0;
 227                 String taskname=getTaskName(td);
 228
 229
 230
 231                 //***Debug Block***
 232
 233                 System.out.println("Method: AnalyseTasks");
 234                 System.out.println(taskname);
 235                 System.out.println();
 236
 237                 //***Debug Block***
 238
 239
 240
 241                 for(int i=0; i < td.numParameters(); i++) {
 242                     FlagExpressionNode fen=td.getFlag(td.getParameter(i));
 243                     //if ( (td.getParamType(i).equals(cd))&&(isTaskTrigger(fen,fs))){
 244                         if ((isParamOfSameClass(td.getParamType(i),cd)) && (isTaskTrigger(fen,fs))){
 245                                 taskistriggered = true;
 246                                 System.out.println(td.getParamType(i).toString()+"   "+cd.toString());
 247                                 temp=(TempDescriptor)map.get(td.getParameter(i));
 248                                 trigger_ctr++;
 249                         }
 250                 }
 251
 252                 if (trigger_ctr>1)
 253                         throw new Error("Illegal Operation: A single flagstate cannot satisfy more than one parameter of a task.");
 254
 255                 if (taskistriggered) {
 256                     //***Debug Block***
 257                     //
 258                     System.out.println("inside taskistriggered");
 259
 260                     //***Debug Block***
 261
 262                     taskistriggered=false;
 263                     if (!wasFlagStateProcessed(sourcenodes,fs)){
 264                                 sourcenodes.put(fs,fs);
 265                         }
 266                         else{
 267                                 fs=sourcenodes.get(fs);
 268                         }
 269
 270                         //Iterating through the nodes
 271                     FlatMethod fm = state.getMethodFlat(td);
 272                     FlatNode fn=fm.methodEntryNode();
 273
 274                     HashSet tovisit= new HashSet();
 275                     HashSet visited= new HashSet();
 276
 277                     tovisit.add(fn);
 278                     while(!tovisit.isEmpty()) {
 279                         FlatNode fn1 = (FlatNode)tovisit.iterator().next();
 280                         tovisit.remove(fn1);
 281                         visited.add(fn1);
 282                         for(int i = 0; i < fn1.numNext(); i++) {
 283                             FlatNode nn=fn1.getNext(i);
 284                             if (nn.kind()==FKind.FlatFlagActionNode) {
 285                                 //***Debug Block***
 286                                 if (((FlatFlagActionNode)nn).getTaskType() == FlatFlagActionNode.PRE) {
 287                                     throw new Error("PRE FlagActions not supported");
 288
 289                                 } else if (((FlatFlagActionNode)nn).getTaskType() == FlatFlagActionNode.NEWOBJECT) {
 290                                     //***Debug Block***
 291                                     System.out.println("NEWObject");
 292                                     //***Debug Block***
 293
 294                                     q_retval.offer(evalNewObjNode(nn));
 295                                 }
 296                                 if (((FlatFlagActionNode)nn).getTaskType() == FlatFlagActionNode.TASKEXIT) {
 297                                     //***Debug Block***
 298                                         System.out.println("TaskExit");
 299                                     //***Debug Block***
 300                                     FlagState fs_taskexit=evalTaskExitNode(nn,cd,fs);
 301
 302                                     Edge newedge=new Edge(fs_taskexit,taskname);
 303                                     if (!edgeexists(fs,newedge)) {
 304                                                 fs.addEdge(newedge);
 305                                     }
 306                                     if ((!wasFlagStateProcessed(sourcenodes,fs_taskexit)) && (!existsInQMain(fs_taskexit)) && (!existsInQ(q_retval,fs_taskexit))){
 307                                         q_retval.offer(fs_taskexit);
 308                                     }
 309                                 }
 310                             }
 311
 312                             if (!visited.contains(nn) && !tovisit.contains(nn)) {
 313                                 tovisit.add(nn);
 314                             }
 315                         }
 316
 317                         }
 318             }
 319         }
 320         if (q_retval.size()==0)
 321             return null;
 322         else
 323             return q_retval;
 324     }
 325
 326     private boolean isTaskTrigger(FlagExpressionNode fen,FlagState fs) {
 327         if (fen instanceof FlagNode)
 328             return fs.get(((FlagNode)fen).getFlag());
 329         else
 330             switch (((FlagOpNode)fen).getOp().getOp()) {
 331             case Operation.LOGIC_AND:
 332                 return ((isTaskTrigger(((FlagOpNode)fen).getLeft(),fs)) && (isTaskTrigger(((FlagOpNode)fen).getRight(),fs)));
 333             case Operation.LOGIC_OR:
 334                 return ((isTaskTrigger(((FlagOpNode)fen).getLeft(),fs)) || (isTaskTrigger(((FlagOpNode)fen).getRight(),fs)));
 335             case Operation.LOGIC_NOT:
 336                 return !(isTaskTrigger(((FlagOpNode)fen).getLeft(),fs));
 337             default:
 338                 return false;
 339             }
 340     }
 341
 342     private boolean isParamOfSameClass(TypeDescriptor typedesc, ClassDescriptor classdesc){
 343            /* Set subclasses=typeutil.getSubClasses(classdesc);
 344             if (subclasses!=null){
 345                         if (subclasses.contains(typedesc.getClassDesc()) || typedesc.getClassDesc().equals(classdesc))
 346                                 return true;
 347                         else
 348                                 return false;
 349                 }
 350                 else{
 351                         if (typedesc.getClassDesc().equals(classdesc))
 352                                 return true;
 353                         else
 354                                 return false;
 355                 }*/
 356
 357                  return typeutil.isSuperorType(classdesc,typedesc.getClassDesc());
 358
 359
 360         }
 361
 362
 363     private FlagState evalNewObjNode(FlatNode nn){
 364             TempDescriptor[] tdArray = ((FlatFlagActionNode)nn).readsTemps();
 365
 366                 //Under the safe assumption that all the temps in FFAN.NewObject node are of the same type(class)
 367                 ClassDescriptor cd_new=tdArray[0].getType().getClassDesc();
 368
 369                 FlagState fstemp=new FlagState(cd_new);
 370
 371                 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
 372                         TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 373                         if (! (tfp.getFlag()==null))// condition checks if the new object was created without any flag setting
 374                         {
 375                                 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
 376                         }
 377                         else
 378                                 break;
 379                 }
 380                 return fstemp;
 381         }
 382
 383         private FlagState evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs){
 384                 FlagState fstemp=fs;
 385
 386                 for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) {
 387                         TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 388                         if (temp.toString().equals(tfp.getTemp().toString()))
 389                                 fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp));
 390                 }
 391                 return fstemp;
 392         }
 393
 394
 395     private boolean wasFlagStateProcessed(Hashtable sourcenodes,FlagState fs) {
 396                 if (sourcenodes.containsKey(fs))
 397                         return true;
 398                 else
 399                         return false;
 400     }
 401
 402    /* private boolean existsInQueue(TriggerState ts) {
 403         throw new Error("Use hashcode/contains of set method to find...no linear search allowed");
 404     }*/
 405
 406     private boolean existsInQMain(FlagState fs) {
 407                 if (q_main.contains(fs))
 408                         return true;
 409                 else
 410                         return false;
 411     }
 412
 413     private boolean existsInQ(Queue q,FlagState fs) {
 414                 if (q.contains(fs))
 415                         return true;
 416                 else
 417                         return false;
 418     }
 419
 420
 421    /* public void printAdjList(ClassDescriptor cd) {
 422         Enumeration e=((Hashtable)Adj_List.get(cd)).keys();
 423         while(e.hasMoreElements()) {
 424             FlagState fsv = (FlagState)(e.nextElement());
 425             System.out.println(fsv.toString((FlagDescriptor [])flags.get(cd)));
 426         }
 427     }*/
 428
 429    public void createDOTfile(ClassDescriptor cd) throws java.io.IOException {
 430
 431         File dotfile= new File("graph"+cd.getSymbol()+".dot");
 432
 433         FileOutputStream dotstream=new FileOutputStream(dotfile,true);
 434
 435         FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values());
 436
 437         }
 438
 439
 440     private String getTaskName(TaskDescriptor td) {
 441         StringTokenizer st = new StringTokenizer(td.toString(),"(");
 442         return st.nextToken();
 443     }
 444
 445    /* private boolean edgeexists(Hashtable Adj_List_local,FlagState v1, FlagState v2,String label) {
 446         Vector edges=(Vector)Adj_List_local.get(v1);
 447
 448         if (edges != null) {
 449             for(int i=0;i < edges.size();i++) {
 450                 FlagState fs=((Edge)edges.get(i)).getTarget();
 451                 if (fs.equals(v2) && (label.compareTo(((Edge)edges.get(i)).getLabel())==0))
 452                     return true;
 453             }
 454         }
 455         return false;
 456     }*/
 457
 458     private boolean edgeexists(FlagState fs, Edge newedge){
 459                 for(Iterator it_edges=fs.edges();it_edges.hasNext();){
 460                                 Edge e=(Edge)it_edges.next();
 461                                 if (newedge.equals(e))
 462                                         return true;
 463                 }
 464                 return false;
 465         }
 466
 467     private Queue createPossibleRuntimeStates(FlagState fs) throws java.io.IOException {
 468
 469                 int noOfIterations, externs;
 470                 Hashtable<FlagState,FlagState> sourcenodes;
 471
 472
 473                 System.out.println("Inside CreatePossible runtime states");
 474
 475                 ClassDescriptor cd = fs.getClassDescriptor();
 476
 477                 sourcenodes=(Hashtable<FlagState,FlagState>)flagstates.get(cd);
 478                 FlagDescriptor[] fd=(FlagDescriptor[])flags.get(cd);
 479                 externs=((Integer)extern_flags.get(cd)).intValue();
 480                 //System.out.println("No of externs:"+externs);
 481
 482
 483                 Queue<FlagState>  q_ret=new LinkedList<FlagState>();
 484
 485
 486             noOfIterations=(1<<externs) - 1;
 487            // System.out.println("No of iterations: "+noOfIterations);
 488             boolean BoolValTable[]=new boolean[externs];
 489
 490             for(int i=0; i < externs ; i++) {
 491                 System.out.println(fd[i].getSymbol());
 492                 BoolValTable[i]=fs.get(fd[i]);
 493             }
 494
 495            /* if (! wasFlagStateProcessed(Adj_List_temp,fs)) {
 496                         Adj_List_temp.put(fs,new Vector());
 497             }
 498             */
 499             if (externs > 0){
 500                 sourcenodes.put(fs,fs);
 501
 502                         for(int k=0; k<noOfIterations; k++) {
 503                                 for(int j=0; j < externs ;j++) {
 504                                     if ((k% (1<<j)) == 0)
 505                                                 BoolValTable[j]=(!BoolValTable[j]);
 506                                 }
 507
 508                                 FlagState fstemp=fs;
 509
 510                                 for(int i=0; i < externs;i++) {
 511                                     fstemp=fstemp.setFlag(fd[i],BoolValTable[i]);
 512                                 }
 513                                 fs.addEdge(new Edge(fstemp,"Runtime"));
 514
 515                                 if (!existsInQMain(fstemp) && ! wasFlagStateProcessed(sourcenodes,fstemp)){
 516                                         q_ret.add(fstemp);
 517                                 }
 518
 519                         }
 520                 }
 521                 return q_ret;
 522         }
 523
 524
 525
 526
 527     private void processTasksWithPost(ClassDescriptor cd, Hashtable pre) {
 528     }
 529
 530     private ClassDescriptor processFlatNew(FlatNode fn) {
 531         if (! (fn.getNext(0).kind() == 13)) {
 532             return (((FlatNew)fn).getType().getClassDesc());
 533         }
 534         return null;
 535     }
 536
 537 }