Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java

   1 package Analysis.TaskStateAnalysis;
   2 import java.util.*;
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.io.*;
   6 import java.io.File;
   7 import java.io.FileWriter;
   8 import java.io.FileOutputStream;
   9 import Util.Edge;
  10
  11 public class SafetyAnalysis {
  12
  13     private Hashtable executiongraph;
  14     private TreeMap safeexecution;
  15     private static final int OR = 0;
  16     private static final int AND = 1;
  17     private Hashtable reducedgraph;
  18     private String classname;
  19     private State state;
  20
  21
  22     /*Structure that stores a possible optional
  23       task which would be safe to execute and
  24       the possible flagstates the object could
  25       be in before executing the task during an
  26       execution without failure*/
  27
  28     public class  MyOptional{
  29         public TaskDescriptor td;
  30         public HashSet flagstates;
  31
  32         protected MyOptional(TaskDescriptor td, HashSet flagstates){
  33             this.td = td;
  34             this.flagstates = flagstates;
  35         }
  36
  37         public boolean equal(MyOptional myo){
  38             if (this.td.getSymbol().compareTo(myo.td.getSymbol())==0)
  39                 if(this.flagstates.equals(myo.flagstates))
  40                     return true;
  41             return false;
  42         }
  43     }
  44
  45     /*Constructor*/
  46     public SafetyAnalysis(Hashtable executiongraph, State state){
  47         this.executiongraph = executiongraph;
  48         this.safeexecution = new TreeMap();
  49         this.reducedgraph = new Hashtable();
  50         this.state = state;
  51     }
  52
  53
  54     public void unMarkProcessed(Vector nodes){
  55         for(Iterator it = nodes.iterator(); it.hasNext();){
  56             EGTaskNode tn = (EGTaskNode)it.next();
  57             tn.unMark();
  58         }
  59     }
  60
  61     /*returns a hashset of tags used during the analysis */
  62     private HashSet createNodeTags(EGTaskNode tn){
  63         HashSet nodetags = new HashSet();
  64         String flagstate = tn.getFSName();
  65         String word = new String();
  66         StringTokenizer st = new StringTokenizer(flagstate);
  67         while (st.hasMoreTokens()){
  68             word = st.nextToken();
  69             if (word.compareTo("Tag")==0)
  70                 nodetags.add(st.nextToken());
  71         }
  72         for(Iterator it = nodetags.iterator(); it.hasNext();){
  73             System.out.println("nodetag :"+it.next());
  74         }
  75         return nodetags;
  76     }
  77
  78     /*finds the the source node in the execution graph*/
  79     private EGTaskNode findSourceNode(Vector nodes){
  80         for(Iterator it = nodes.iterator(); it.hasNext();){
  81             EGTaskNode tn = (EGTaskNode)it.next();
  82             if(tn.isSource()){
  83                 System.out.println("Found Source Node !!");
  84                 return tn;
  85             }
  86         }
  87         return null;
  88     }
  89
  90     /*returns the nodes corresponding to the tasks
  91       that can fire with the object in flagstate
  92       previousflagstate*/
  93     private Vector findEGTaskNode(String previousflagstate, Vector nodes){
  94         Vector tns = new Vector();
  95         for(Iterator it = nodes.iterator(); it.hasNext();){
  96             EGTaskNode tn = (EGTaskNode)it.next();
  97             if(tn.getFSName().compareTo(previousflagstate)==0)
  98                 tns.add(tn);
  99         }
 100         if(tns.size() == 0)
 101             return null;
 102         else if (tns.size() > 1){
 103             for(Iterator it = tns.iterator(); it.hasNext();){
 104                 EGTaskNode tn = (EGTaskNode)it.next();
 105                 tn.setAND();
 106             }
 107         }
 108         return tns;
 109     }
 110
 111     /*returns the executiongraph corresponding to the classname*/
 112     private Vector getConcernedClass( String classname ){
 113         Enumeration e = executiongraph.keys();
 114         while( e.hasMoreElements() ){
 115             ClassDescriptor cd = (ClassDescriptor)e.nextElement();
 116             if (classname.compareTo(cd.getSymbol())==0)
 117                 return (Vector)executiongraph.get(cd);
 118         }
 119         return null;
 120     }
 121
 122     /*Method used for debugging*/
 123     public void buildPath() throws java.io.IOException {
 124
 125         byte[] b = new byte[100] ;
 126         HashSet safetasks = new HashSet();
 127         System.out.println("Enter the Class of the object concerned :");
 128         int k = System.in.read(b);
 129         classname = new String(b,0,k-1);
 130         System.out.println("Enter the flagstate :");
 131         k = System.in.read(b);
 132         String previousflagstate = new String(b,0,k-1);
 133
 134         //get the graph result of executiongraph class
 135         Vector nodes = new Vector();
 136         nodes = getConcernedClass( classname );
 137         if(nodes==null) {
 138             System.out.println("Impossible to find "+classname+". Maybe not declared in the source code.");
 139             return;
 140         }
 141
 142         //mark the graph
 143         EGTaskNode sourcenode = findSourceNode(nodes);
 144         doGraphMarking(sourcenode);
 145         createDOTFile();
 146         //get the tasknodes possible to execute with the flagstate before failure
 147         HashSet tempnodes = new HashSet();
 148         Vector tns = new Vector();
 149         tns = findEGTaskNode(previousflagstate, nodes);
 150         if(tns==null) {
 151             System.out.println("No task corresponding");
 152             return;
 153         }
 154
 155         //compute the result for all the nodes contained in tns.
 156         //return the intersection. (because it is not possible to choose)
 157         int counter = 0;
 158         HashSet availabletasks = new HashSet();
 159         for(Iterator it = tns.iterator(); it.hasNext();){
 160             counter++;
 161             unMarkProcessed(nodes);
 162             EGTaskNode tn = (EGTaskNode)it.next();
 163             HashSet nodetags = createNodeTags(tn);
 164             availabletasks = createUnion(determineIfIsSafe(tn, nodetags), availabletasks);
 165                 //DEBUG
 166                 System.out.println("-----------------------------");
 167                 for(Iterator it2 = availabletasks.iterator(); it2.hasNext();){
 168                 MyOptional mm = (MyOptional)it2.next();
 169                 System.out.println("\t"+mm.td.getSymbol());
 170                 System.out.println("with flags :");
 171                 for(Iterator it3 = mm.flagstates.iterator(); it3.hasNext();){
 172                 System.out.println("\t"+((FlagState)it3.next()).getTextLabel());
 173                 }
 174                 resultingFS(mm, classname);
 175                 System.out.println("-----------------------------");
 176                 }
 177             if(counter == 1) safetasks = availabletasks;
 178             else safetasks = createIntersection(availabletasks, safetasks);
 179         }
 180         //DEBUG
 181           System.out.println("----------FINAL--------------");
 182           for(Iterator it2 = safetasks.iterator(); it2.hasNext();){
 183           MyOptional mm = (MyOptional)it2.next();
 184           System.out.println("\t"+mm.td.getSymbol());
 185           System.out.println("with flags :");
 186           for(Iterator it3 = mm.flagstates.iterator(); it3.hasNext();){
 187           System.out.println("\t"+((FlagState)it3.next()).getTextLabel());
 188           }
 189           resultingFS(mm, classname);
 190           System.out.println("-----");
 191           }
 192           System.out.println("----------FINAL--------------");
 193     }
 194
 195     /*Actual method used by the compiler.
 196       It computes the analysis for every
 197       possible flagstates of every classes*/
 198     public void buildPath(Vector flagstates, ClassDescriptor cd) throws java.io.IOException {
 199     }
 200
 201
 202     /*Marks the executiongraph :
 203           -optionals
 204           -multiple
 205           -AND and OR nodes
 206     */
 207     private void doGraphMarking(EGTaskNode extremity) throws java.io.IOException{
 208         //detects if there is a loop or no more nodes to explore
 209         if (extremity.isMarked() || !((Iterator)extremity.edges()).hasNext()){
 210             if (!((Iterator)extremity.edges()).hasNext()) extremity.mark();
 211             reducedgraph.put(extremity.getuid(), extremity);
 212         }
 213         else {
 214             //do the marking
 215             process(extremity);
 216             reducedgraph.put(extremity.getuid(), extremity);
 217             extremity.mark();
 218             //calls doGraphMarking recursively with the next nodes as params
 219             for( Iterator it = extremity.edges(); it.hasNext(); ){
 220                 TEdge edge = (TEdge)it.next();
 221                 doGraphMarking((EGTaskNode)edge.getTarget());
 222             }
 223         }
 224     }
 225
 226     private void process(EGTaskNode tn){
 227         testIfOptional(tn);
 228         testIfSameTask(tn);
 229         testIfNextIsSelfLoop(tn);
 230         testIfRuntime(tn);
 231         testIfMultiple(tn);
 232     }
 233
 234     private void testIfOptional(EGTaskNode tn){
 235         for(Iterator edges = tn.edges(); edges.hasNext();){
 236             TEdge edge = (TEdge)edges.next();
 237             EGTaskNode nexttn = (EGTaskNode)edge.getTarget();
 238             if (nexttn.getTD()!=null)
 239                 if(nexttn.getTD().isOptional(classname))
 240                     nexttn.setOptional();
 241         }
 242     }
 243
 244     private void testIfMultiple(EGTaskNode tn){
 245         for(Iterator edges = tn.edges(); edges.hasNext();){
 246             TEdge edge = (TEdge)edges.next();
 247             EGTaskNode nexttn = (EGTaskNode)edge.getTarget();
 248             if( nexttn.getTD().numParameters() > 1 ){
 249                 nexttn.setMultipleParams();
 250             }
 251         }
 252     }
 253
 254     //maybe a little bug to fix
 255     private void testIfRuntime(EGTaskNode tn){
 256         for(Iterator edges = tn.edges(); edges.hasNext();){
 257             TEdge edge = (TEdge)edges.next();
 258             EGTaskNode nexttn = (EGTaskNode)edge.getTarget();
 259             if( ((String)nexttn.getName()).compareTo("Runtime") == 0 )
 260                 nexttn.setAND();
 261         }
 262     }
 263
 264     /*That correspond to the case where it is
 265       not possible for us to choose a path of
 266       execution. The optional task has to be
 267       present in all the possible executions
 268       at this point. So we mark the node as an
 269       AND node.*/
 270     private void testIfSameTask(EGTaskNode tn){
 271         Vector vtemp = new Vector();
 272         Vector tomark = new Vector();
 273         for(Iterator edges = tn.edges(); edges.hasNext();){
 274             TEdge edge = (TEdge)edges.next();
 275             EGTaskNode nexttn = (EGTaskNode)edge.getTarget();
 276             int contains = 0;
 277             for (Iterator it = vtemp.iterator(); it.hasNext();){
 278                 EGTaskNode nexttn2 = (EGTaskNode)it.next();
 279                 if (nexttn.getName()==nexttn2.getName()){
 280                     contains = 1;
 281                     tomark.add(nexttn);
 282                     tomark.add(nexttn2);
 283                 }
 284             }
 285             if (contains == 0) vtemp.add(nexttn);
 286         }
 287
 288         for(Iterator it2 = tomark.iterator(); it2.hasNext();)
 289             ((EGTaskNode)it2.next()).setAND();
 290     }
 291
 292     //maybe little bug to fix
 293     private void testIfNextIsSelfLoop(EGTaskNode tn){
 294         for(Iterator edges = tn.edges(); edges.hasNext();){
 295             TEdge edge = (TEdge)edges.next();
 296             EGTaskNode nexttn = (EGTaskNode)edge.getTarget();
 297             if(nexttn.isSelfLoop()) nexttn.setAND();
 298         }
 299     }
 300
 301
 302     /*recursive method that returns a set of MyOptionals
 303       The computation basically consist in returning the
 304       intersection or union of sets depending on the nature
 305       of the node : OR -> UNION
 306                     AND -> INTERSECTION
 307       The method also looks for tag changes.
 308     */
 309     private HashSet determineIfIsSafe(EGTaskNode tn, HashSet nodetags){
 310         if(tn == null) return null;
 311         if(!tagChange(tn, nodetags)){
 312             if(tn.isOptional()){
 313                 HashSet temp = new HashSet();
 314                 //if the tn is optional and there is no more nodes/presence of a loop
 315                 //create the MyOptional and return it as a singleton.
 316                 if( !((Iterator)tn.edges()).hasNext() || tn.isMarked() || tn.isSelfLoop()){
 317                     HashSet fstemp = new HashSet();
 318                     fstemp.add(tn.getFS());
 319                     MyOptional mo = new MyOptional(tn.getTD(), fstemp);
 320                     temp.add(mo);
 321                     return temp;
 322                 }
 323                 //else compute the edges, create the MyOptional and add it to the set.
 324                 else{
 325                     tn.mark();
 326                     temp = computeEdges(tn, nodetags);
 327                     HashSet fstemp = new HashSet();
 328                     fstemp.add(tn.getFS());
 329                     MyOptional mo = new MyOptional(tn.getTD(), fstemp);
 330                     temp.add(mo);
 331                     return temp;
 332                 }
 333             }
 334             else{
 335                 //if not optional but terminal just return an empty set.
 336                 if( !((Iterator)tn.edges()).hasNext() || tn.isMarked() || tn.isSelfLoop()){
 337                     HashSet temp = new HashSet();
 338                     return temp;
 339                 }
 340                 //if not terminal return the computation of the edges.
 341                 else{
 342                     tn.mark();
 343                     return computeEdges(tn, nodetags);
 344                 }
 345             }
 346         }
 347         //if there has been a tag change return an empty set.
 348         else{
 349             HashSet temp = new HashSet();
 350             return temp;
 351         }
 352     }
 353
 354     /*check if there has been a tag Change*/
 355     private boolean tagChange(EGTaskNode tn, HashSet nodetags){
 356         HashSet tags = new HashSet();
 357         String flagstate = tn.getFSName();
 358         String word = new String();
 359         StringTokenizer st = new StringTokenizer(flagstate);
 360         while (st.hasMoreTokens()){
 361             word = st.nextToken();
 362             if (word.compareTo("Tag")==0)
 363                 tags.add(st.nextToken());
 364         }
 365         //compare the tag needed now to the tag of the initial node
 366         for(Iterator it = tags.iterator(); it.hasNext();){
 367             String tag = (String)it.next();
 368             if( !nodetags.contains(tag)){
 369                 System.out.println("Tag Change :"+tag);
 370                 return true;
 371             }
 372         }
 373
 374         return false;
 375     }
 376
 377
 378     private HashSet computeEdges(EGTaskNode tn, HashSet nodetags){
 379         Hashtable andlist = new Hashtable();
 380         Vector orlist = new Vector();
 381         for(Iterator edges = tn.edges(); edges.hasNext();){
 382             EGTaskNode tntemp = (EGTaskNode)((TEdge)edges.next()).getTarget();
 383             if(tntemp.type() == OR) orlist.add(tntemp);
 384             else if(tntemp.type() == AND){
 385                 if(andlist.containsKey(tntemp.getName())){
 386                     ((Vector)andlist.get(tntemp.getName())).add(tntemp);}
 387                 else{
 388                     Vector vector = new Vector();
 389                     vector.add(tntemp);
 390                     andlist.put(tntemp.getName(), vector);
 391                 }
 392             }
 393         }
 394
 395         return (createUnion(computeOrVector(orlist, nodetags), computeAndList(andlist, nodetags)));
 396     }
 397
 398     private  HashSet computeOrVector( Vector orlist, HashSet nodetags){
 399         if(orlist.isEmpty()){
 400             HashSet temp = new HashSet();
 401             return temp;
 402         }
 403         else{
 404             HashSet temp = new HashSet();
 405             for(Iterator tns = orlist.iterator(); tns.hasNext();){
 406                 EGTaskNode tn = (EGTaskNode)tns.next();
 407                 temp = createUnion(determineIfIsSafe(tn, nodetags), temp);
 408             }
 409             return temp;
 410         }
 411
 412     }
 413
 414     private  HashSet computeAndList(Hashtable andlist, HashSet nodetags){
 415         if( andlist.isEmpty()){
 416             HashSet temp = new HashSet();
 417             return temp;
 418         }
 419         else{
 420             HashSet temp = new HashSet();
 421             Collection c = andlist.values();
 422             for(Iterator vectors = c.iterator(); vectors.hasNext();){
 423                 Vector vector = (Vector)vectors.next();
 424                 temp = createUnion(computeAndVector(vector, nodetags), temp);
 425             }
 426             return temp;
 427         }
 428
 429     }
 430
 431     private  HashSet computeAndVector(Vector vector, HashSet nodetags){
 432         HashSet temp = new HashSet();
 433         boolean init = true;
 434         for(Iterator tns = vector.iterator(); tns.hasNext();){
 435             EGTaskNode tn = (EGTaskNode)tns.next();
 436             if (init){
 437                 init = false;
 438                 temp = determineIfIsSafe(tn, nodetags);
 439             }
 440             else{
 441                 temp = createIntersection(determineIfIsSafe(tn, nodetags), temp);
 442             }
 443         }
 444         return temp;
 445     }
 446
 447     private HashSet createUnion( HashSet A, HashSet B){
 448         A.addAll(B);
 449
 450         //remove duplicated MyOptionals (might happend)
 451         Vector toremove = new Vector();
 452         System.out.println("A contains "+A.size()+" elements");
 453         int i = 0;
 454         for(Iterator itA = A.iterator(); itA.hasNext();){
 455             MyOptional myA = (MyOptional)itA.next();
 456             i++;
 457             System.out.println("myA = "+myA.td.getSymbol());
 458             Iterator itA2 = A.iterator();
 459             for(int j = 0; j<i; j++){
 460                 itA2.next();
 461             }
 462             for(Iterator itA3 = itA2; itA3.hasNext();){
 463                 MyOptional myA2 = (MyOptional)itA3.next();
 464                 System.out.println("myA2 = "+myA2.td.getSymbol());
 465                 if(myA2.equal(myA)){
 466                     toremove.add(myA2);
 467                     System.out.println("removed!");
 468                 }
 469             }
 470         }
 471         for( Iterator it = toremove.iterator(); it.hasNext();)
 472             A.remove(it.next());
 473
 474         return A;
 475     }
 476
 477     private HashSet createIntersection( HashSet A, HashSet B){
 478         HashSet result = new HashSet();
 479         for(Iterator itB = B.iterator(); itB.hasNext();){
 480             MyOptional myB = (MyOptional)itB.next();
 481             for(Iterator itA = A.iterator(); itA.hasNext();){
 482                 MyOptional myA = (MyOptional)itA.next();
 483                 if(((String)myA.td.getSymbol()).compareTo((String)myB.td.getSymbol())==0){
 484                         HashSet newfs = new HashSet();
 485                         newfs.addAll(myA.flagstates);
 486                         newfs.addAll(myB.flagstates);
 487                         MyOptional newmy = new MyOptional(myB.td, newfs);
 488                         result.add(newmy);
 489                 }
 490             }
 491         }
 492         return result;
 493     }
 494
 495     /////////DEBUG
 496     /*Thoose two tasks create the dot file named markedgraph.dot */
 497
 498     private void createDOTFile() throws java.io.IOException {
 499         Collection v = reducedgraph.values();
 500         java.io.PrintWriter output;
 501         File dotfile_flagstates= new File("markedgraph.dot");
 502         FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
 503         output = new java.io.PrintWriter(dotstream, true);
 504         output.println("digraph dotvisitor {");
 505         output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
 506         output.println("\tedge [fontsize=6];");
 507         traverse(output, v);
 508         output.println("}\n");
 509     }
 510
 511     private void traverse(java.io.PrintWriter output, Collection v) {
 512         EGTaskNode tn;
 513
 514         for(Iterator it1 = v.iterator(); it1.hasNext();){
 515             tn = (EGTaskNode)it1.next();
 516             output.println("\t"+tn.getLabel()+" [label=\""+tn.getTextLabel()+"\"");
 517             if (tn.isOptional()){
 518                 if (tn.isMultipleParams()) output.println(", shape = tripleoctagon");
 519                 else output.println(", shape=doubleoctagon");
 520             }
 521             else if (tn.isMultipleParams()) output.println(", shape=octagon");
 522             if (tn.type()==AND) output.println(", color=blue");
 523             output.println("];");
 524
 525             for(Iterator it2 = tn.edges();it2.hasNext();){
 526                 EGTaskNode tn2 = (EGTaskNode)((Edge)it2.next()).getTarget();
 527                 output.println("\t"+tn.getLabel()+" -> "+tn2.getLabel()+";");
 528             }
 529         }
 530     }
 531
 532     ////////////////////
 533     /* returns a set of the possible sets of flagstates
 534        resulting from the execution of the optional task.
 535        To do it with have to look for TaskExit FlatNodes
 536        in the IR.
 537     */
 538     private HashSet resultingFS(MyOptional mo, ClassDescriptor cd){
 539         return resultingFS(mo, cd.getSymbol());
 540     }
 541
 542     private HashSet resultingFS(MyOptional mo, String classname){
 543         Stack stack = new Stack();
 544         HashSet result = new HashSet();
 545         FlatMethod fm = state.getMethodFlat((TaskDescriptor)mo.td);
 546         FlatNode fn = (FlatNode)fm;
 547
 548         Stack nodestack=new Stack();
 549         HashSet discovered=new HashSet();
 550         nodestack.push(fm);
 551         discovered.add(fm);
 552
 553         //Iterating through the nodes
 554         while(!nodestack.isEmpty()) {
 555             FlatNode fn1 = (FlatNode) nodestack.pop();
 556             if (fn1.kind()==FKind.FlatFlagActionNode) {
 557                 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
 558                 if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
 559                     //***
 560                     System.out.println("TASKEXIT");
 561                     //***
 562                     HashSet tempset = new HashSet();
 563                     for(Iterator it_fs = mo.flagstates.iterator(); it_fs.hasNext();){
 564                         FlagState fstemp = (FlagState)it_fs.next();
 565                         for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
 566                             TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 567                             TempDescriptor td = tfp.getTemp();
 568                             if (((String)((ClassDescriptor)((TypeDescriptor)td.getType()).getClassDesc()).getSymbol()).compareTo(classname)==0){
 569                                 fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
 570                             }
 571                         }
 572                         System.out.println("new flag : "+fstemp.getTextLabel());
 573                         tempset.add(fstemp);
 574                     }
 575                     result.add(tempset);
 576                     continue; // avoid queueing the return node if reachable
 577                 }
 578             }else if (fn1.kind()==FKind.FlatReturnNode) {
 579                 //***
 580                 System.out.println("RETURN NODE REACHABLE WITHOUT TASKEXITS");
 581                 //***
 582                 result.add(mo.flagstates);
 583             }
 584
 585             /* Queue other nodes past this one */
 586             for(int i=0;i<fn1.numNext();i++) {
 587                 FlatNode fnext=fn1.getNext(i);
 588                 if (!discovered.contains(fnext)) {
 589                     discovered.add(fnext);
 590                     nodestack.push(fnext);
 591                 }
 592             }
 593         }
 594         return result;
 595     }
 596
 597 }
 598
 599