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