Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java

   1 package Analysis.TaskStateAnalysis;
   2 import java.util.*;
   3 import IR.*;
   4 import IR.Tree.*;
   5 import IR.Flat.*;
   6 import java.io.*;
   7 import java.io.File;
   8 import java.io.FileWriter;
   9 import java.io.FileOutputStream;
  10 import Util.Edge;
  11
  12 public class SafetyAnalysis {
  13     private Hashtable executiongraph;
  14     private Hashtable<ClassDescriptor, Hashtable<FlagState, HashSet>> safeexecution; //to use to build code
  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     private TaskAnalysis taskanalysis;
  21     private Hashtable<ClassDescriptor, Hashtable> optionaltaskdescriptors;
  22
  23     private ClassDescriptor processedclass;
  24
  25
  26     public Hashtable<ClassDescriptor, Hashtable<FlagState, HashSet>> getResult(){
  27         return safeexecution;
  28     }
  29
  30     public Hashtable<ClassDescriptor, Hashtable> getOptionalTaskDescriptors(){
  31         return optionaltaskdescriptors;
  32     }
  33
  34     /*Structure that stores a possible optional
  35       task which would be safe to execute and
  36       the possible flagstates the object could
  37       be in before executing the task during an
  38       execution without failure*/
  39
  40     /*Constructor*/
  41     public SafetyAnalysis(Hashtable executiongraph, State state, TaskAnalysis taskanalysis){
  42         this.executiongraph = executiongraph;
  43         this.safeexecution = new Hashtable();
  44         this.reducedgraph = new Hashtable();
  45         this.state = state;
  46         this.taskanalysis = taskanalysis;
  47         this.optionaltaskdescriptors = new Hashtable();
  48     }
  49
  50     /*finds the the source node in the execution graph*/
  51     private EGTaskNode findSourceNode(Vector nodes){
  52         for(Iterator it = nodes.iterator(); it.hasNext();){
  53             EGTaskNode tn = (EGTaskNode)it.next();
  54             if(tn.isSource()){
  55                 return tn;
  56             }
  57         }
  58         return null;
  59     }
  60
  61     /*returns the nodes corresponding to the tasks
  62       that can fire with the object in flagstate
  63       previousflagstate*/
  64     private Vector findEGTaskNode(String previousflagstate, Vector nodes){
  65         Vector tns = new Vector();
  66         for(Iterator it = nodes.iterator(); it.hasNext();){
  67             EGTaskNode tn = (EGTaskNode)it.next();
  68             if(tn.getFSName().compareTo(previousflagstate)==0)
  69                 tns.add(tn);
  70         }
  71         if(tns.size() == 0)
  72             return null;
  73         else if (tns.size() > 1){
  74             for(Iterator it = tns.iterator(); it.hasNext();){
  75                 EGTaskNode tn = (EGTaskNode)it.next();
  76                 tn.setAND();
  77             }
  78         }
  79         return tns;
  80     }
  81
  82     /*returns the executiongraph corresponding to the classname*/
  83     private Vector getConcernedClass(ClassDescriptor cd){
  84         if (executiongraph.containsKey(cd))
  85             return (Vector) executiongraph.get(cd);
  86         else
  87             return null;
  88     }
  89
  90     /*Actual method used by the compiler.
  91       It computes the analysis for every
  92       possible flagstates of every classes*/
  93     public void buildPath() throws java.io.IOException {
  94         /*Explore the taskanalysis structure*/
  95         System.out.println("------- ANALYSING OPTIONAL TASKS -------");
  96         Enumeration e=taskanalysis.flagstates.keys();
  97
  98         while (e.hasMoreElements()) {
  99             System.out.println("\nAnalysing class :");
 100             processedclass=(ClassDescriptor)e.nextElement();
 101             classname = processedclass.getSymbol();
 102             Hashtable newhashtable = new Hashtable();
 103             optionaltaskdescriptors.put(processedclass, newhashtable);
 104             Hashtable cdhashtable = new Hashtable();
 105
 106             System.out.println("\t"+classname+ "\n");
 107             //get the graph result of executiongraph class
 108             Vector nodes = getConcernedClass(processedclass);
 109
 110             if(nodes==null) {
 111                 System.out.println("Impossible to find "+classname+". Unexpected.");
 112                 continue;
 113             } else if (nodes.size()==0) {
 114                 System.out.println("Nothing to do");
 115                 continue;
 116             }
 117
 118             //mark the graph
 119             EGTaskNode sourcenode = findSourceNode(nodes);
 120
 121             //skip classes that don't have source nodes
 122             if (sourcenode==null)
 123                 continue;
 124
 125             doGraphMarking(sourcenode);
 126             createDOTFile( classname );
 127             reducedgraph.clear();
 128
 129             Collection fses = ((Hashtable)taskanalysis.flagstates.get(processedclass)).values();
 130             Iterator itfses = fses.iterator();
 131             while (itfses.hasNext()) {
 132                 FlagState fs = (FlagState)itfses.next();
 133                 Hashtable fsresult = new Hashtable();
 134                 //get the tasknodes possible to execute with the flagstate before failure
 135                 HashSet tempnodes = new HashSet();
 136                 Vector tns = new Vector();
 137                 System.out.println("Analysing "+fs.getTextLabel());
 138                 tns = findEGTaskNode(fs.getTextLabel(), nodes);
 139                 if(tns==null) {
 140                     System.out.println("\tNo task corresponding, terminal FS");
 141                     continue;
 142                 }
 143                 System.out.println("\tProcessing...");
 144
 145                 //compute the result for all the nodes contained in tns.
 146                 //return the intersection of tns that are the same task and union for others.
 147
 148                 HashSet availabletasks = new HashSet();
 149                 availabletasks = computeTns(tns);
 150
 151                 //removeDoubles(availabletasks);
 152
 153                 for(Iterator it = availabletasks.iterator(); it.hasNext();){
 154                     OptionalTaskDescriptor otd = (OptionalTaskDescriptor)it.next();
 155                     resultingFS(otd, classname);
 156                 }
 157
 158                 cdhashtable.put(fs, availabletasks);
 159             }
 160
 161             safeexecution.put(processedclass, cdhashtable);
 162
 163         }
 164         putinoptionaltaskdescriptors();
 165         printTEST();
 166     }
 167
 168     private void putinoptionaltaskdescriptors(){
 169         Enumeration e = safeexecution.keys();
 170         while (e.hasMoreElements()) {
 171             ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
 172             optionaltaskdescriptors.get(cdtemp).clear();
 173             Hashtable hashtbtemp = safeexecution.get(cdtemp);
 174             Enumeration fses = hashtbtemp.keys();
 175             while(fses.hasMoreElements()){
 176                 FlagState fs = (FlagState)fses.nextElement();
 177                 HashSet availabletasks = (HashSet)hashtbtemp.get(fs);
 178                 for(Iterator otd_it = availabletasks.iterator(); otd_it.hasNext();){
 179                     OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
 180                     optionaltaskdescriptors.get(cdtemp).put(otd, otd);
 181                 }
 182             }
 183         }
 184     }
 185
 186     private void printTEST(){
 187         Enumeration e = safeexecution.keys();
 188         while (e.hasMoreElements()) {
 189             ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
 190             System.out.println("\nTesting class : "+cdtemp.getSymbol()+"\n");
 191             Hashtable hashtbtemp = safeexecution.get(cdtemp);
 192             Enumeration fses = hashtbtemp.keys();
 193             while(fses.hasMoreElements()){
 194                 FlagState fs = (FlagState)fses.nextElement();
 195                 System.out.println("\t"+fs.getTextLabel()+"\n\tSafe tasks to execute :\n");
 196                 HashSet availabletasks = (HashSet)hashtbtemp.get(fs);
 197                 for(Iterator otd_it = availabletasks.iterator(); otd_it.hasNext();){
 198                     OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
 199                     System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n");
 200                     System.out.println("\t\tDepth : "+otd.depth);
 201                     System.out.println("\t\twith flags :");
 202                     for(Iterator myfses = otd.flagstates.iterator(); myfses.hasNext();){
 203                         System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel());
 204                     }
 205                     System.out.println("\t\tand exitflags :");
 206                     for(Iterator fseshash = otd.exitfses.iterator(); fseshash.hasNext();){
 207                         HashSet temphs = (HashSet)fseshash.next();
 208                         System.out.println("");
 209                         for(Iterator exfses = temphs.iterator(); exfses.hasNext();){
 210                             System.out.println("\t\t\t"+((FlagState)exfses.next()).getTextLabel());
 211                         }
 212                     }
 213                     Predicate predicate = otd.predicate;
 214                     System.out.println("\t\tPredicate constains :");
 215                     Collection c = predicate.vardescriptors.values();
 216                     for(Iterator varit = c.iterator(); varit.hasNext();){
 217                         VarDescriptor vard = (VarDescriptor)varit.next();
 218                         System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol());
 219                     }
 220                     System.out.println("\t\t------------");
 221                 }
 222             }
 223
 224             System.out.println("\n\n\n\tOptionaltaskdescriptors contains : ");
 225             Collection c_otd = optionaltaskdescriptors.get(cdtemp).values();
 226             for(Iterator otd_it = c_otd.iterator(); otd_it.hasNext();){
 227                 OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
 228                 System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n");
 229                 System.out.println("\t\tDepth : "+otd.depth);
 230                 System.out.println("\t\twith flags :");
 231                 for(Iterator myfses = otd.flagstates.iterator(); myfses.hasNext();){
 232                     System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel());
 233                 }
 234                 System.out.println("\t\tand exitflags :");
 235                     for(Iterator fseshash = otd.exitfses.iterator(); fseshash.hasNext();){
 236                         HashSet temphs = (HashSet)fseshash.next();
 237                         System.out.println("");
 238                         for(Iterator exfses = temphs.iterator(); exfses.hasNext();){
 239                             System.out.println("\t\t\t"+((FlagState)exfses.next()).getTextLabel());
 240                         }
 241                     }
 242                     Predicate predicate = otd.predicate;
 243                     System.out.println("\t\tPredicate contains :");
 244                     Collection c = predicate.vardescriptors.values();
 245                     for(Iterator varit = c.iterator(); varit.hasNext();){
 246                         VarDescriptor vard = (VarDescriptor)varit.next();
 247                         System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol());
 248                         HashSet temphash = predicate.flags.get(vard.getName());
 249                         if(temphash == null) System.out.println("null hashset");
 250                         else System.out.println("\t\t\t"+temphash.size()+" flag(s)");
 251
 252                     }
 253                     System.out.println("\t\t------------");
 254             }
 255         }
 256
 257
 258     }
 259
 260     /*Marks the executiongraph :
 261       -optionals
 262       -multiple
 263       -AND and OR nodes
 264     */
 265     private void doGraphMarking(EGTaskNode extremity) throws java.io.IOException{
 266         //detects if there is a loop or no more nodes to explore
 267         if (extremity.isMarked() || !((Iterator)extremity.edges()).hasNext()){
 268             if (!((Iterator)extremity.edges()).hasNext()) extremity.mark();
 269             reducedgraph.put(extremity.getuid(), extremity);
 270         } else {
 271             //do the marking
 272             process(extremity);
 273             reducedgraph.put(extremity.getuid(), extremity);
 274             extremity.mark();
 275             //calls doGraphMarking recursively with the next nodes as
 276             //params
 277             for( Iterator it = extremity.edges(); it.hasNext(); ){
 278                 EGEdge edge = (EGEdge)it.next();
 279                 doGraphMarking((EGTaskNode)edge.getTarget());
 280             }
 281         }
 282     }
 283
 284     private void process(EGTaskNode tn){
 285         testIfOptional(tn);
 286         testIfAND(tn);
 287         testIfNextIsSelfLoop(tn);
 288         testIfRuntime(tn);
 289         testIfMultiple(tn);
 290     }
 291
 292     private void testIfOptional(EGTaskNode tn){
 293         for(Iterator edges = tn.edges(); edges.hasNext();){
 294             EGEdge edge = (EGEdge)edges.next();
 295             EGTaskNode nexttn = (EGTaskNode)edge.getTarget();
 296             if (nexttn.getTD()!=null)
 297                 if(nexttn.getTD().isOptional(classname))
 298                     nexttn.setOptional();
 299         }
 300     }
 301
 302     private void testIfMultiple(EGTaskNode tn){
 303         for(Iterator edges = tn.edges(); edges.hasNext();){
 304             EGEdge edge = (EGEdge)edges.next();
 305             EGTaskNode nexttn = (EGTaskNode)edge.getTarget();
 306             if (nexttn.getTD() == null ) return;//to be fixed
 307             if( nexttn.getTD().numParameters() > 1 ){
 308                 nexttn.setMultipleParams();
 309             }
 310         }
 311     }
 312
 313     //maybe a little bug to fix
 314     private void testIfRuntime(EGTaskNode tn){
 315         for(Iterator edges = tn.edges(); edges.hasNext();){
 316             EGEdge edge = (EGEdge)edges.next();
 317             EGTaskNode nexttn = (EGTaskNode)edge.getTarget();
 318             if( ((String)nexttn.getName()).compareTo("Runtime") == 0 )
 319                 nexttn.setAND();
 320         }
 321     }
 322
 323     /*That correspond to the case where it is
 324       not possible for us to choose a path of
 325       execution. The optional task has to be
 326       present in all the possible executions
 327       at this point. So we mark the node as an
 328       AND node.*/
 329     private void testIfAND(EGTaskNode tn){
 330         Vector vtemp = new Vector();
 331         Vector tomark = new Vector();
 332         for(Iterator edges = tn.edges(); edges.hasNext();){
 333             EGEdge edge = (EGEdge)edges.next();
 334             EGTaskNode nexttn = (EGTaskNode)edge.getTarget();
 335             int contains = 0;
 336             for (Iterator it = vtemp.iterator(); it.hasNext();){
 337                 EGTaskNode nexttn2 = (EGTaskNode)it.next();
 338                 if (nexttn.getName()==nexttn2.getName()){
 339                     contains = 1;
 340                     tomark.add(nexttn);
 341                     tomark.add(nexttn2);
 342                 }
 343             }
 344             if (contains == 0) vtemp.add(nexttn);
 345         }
 346
 347         for(Iterator it2 = tomark.iterator(); it2.hasNext();)
 348         ((EGTaskNode)it2.next()).setAND();
 349     }
 350
 351     //maybe little bug to fix
 352     private void testIfNextIsSelfLoop(EGTaskNode tn){
 353         for(Iterator edges = tn.edges(); edges.hasNext();){
 354             EGEdge edge = (EGEdge)edges.next();
 355             EGTaskNode nexttn = (EGTaskNode)edge.getTarget();
 356             if(nexttn.isSelfLoop()) nexttn.setAND();
 357         }
 358     }
 359
 360
 361     /*recursive method that returns a set of OptionalTaskDescriptors
 362       The computation basically consist in returning the
 363       intersection or union of sets depending on the nature
 364       of the node : OR -> UNION
 365                     AND -> INTERSECTION
 366       The method also looks for tag changes.
 367     */
 368     private HashSet determineIfIsSafe(EGTaskNode tn, int depth, HashSet visited, Predicate predicate){
 369         Predicate temppredicate = new Predicate();
 370         if(tn == null) return null;
 371         if(!tagChange(tn)){
 372             if(tn.isOptional()){
 373                 HashSet temp = new HashSet();
 374                 if( tn.isMultipleParams() ){
 375                     if( goodMultiple(tn) ){
 376                         temppredicate = combinePredicates(predicate, returnPredicate(tn));
 377                         System.out.println("Good multiple, Optional "+tn.getName());
 378                     }
 379                     else return temp;
 380                 }
 381                 else temppredicate = combinePredicates(temppredicate, predicate);
 382                 //if the tn is optional and there is no more nodes/presence of a loop
 383                 //create the OptionalTaskDescriptor and return it as a singleton.
 384                 if( !((Iterator)tn.edges()).hasNext() || tn.isSelfLoop()){
 385                     HashSet fstemp = new HashSet();
 386                     fstemp.add(tn.getFS());
 387                     OptionalTaskDescriptor otd = new OptionalTaskDescriptor(tn.getTD(), fstemp, depth, temppredicate);
 388                     if(optionaltaskdescriptors.get(processedclass).get(otd)!=null){
 389                         otd = (OptionalTaskDescriptor)((Hashtable)optionaltaskdescriptors.get(processedclass)).get(otd);
 390                     }
 391                     else optionaltaskdescriptors.get(processedclass).put(otd, otd);
 392                     temp.add(otd);
 393                     return temp;
 394                 }
 395                 else if(visited.contains(tn)){
 396                     return temp;
 397                 }
 398                 //else compute the edges, create the OptionalTaskDescriptor and add it to the set.
 399                 else{
 400                     int newdepth = depth + 1;
 401                     visited.add(tn);
 402                     HashSet newhashset = new HashSet(visited);
 403                     HashSet fstemp = new HashSet();
 404                     fstemp.add(tn.getFS());
 405                     OptionalTaskDescriptor otd = new OptionalTaskDescriptor(tn.getTD(), fstemp, depth, temppredicate);
 406                     if(optionaltaskdescriptors.get(processedclass).get(otd)!=null){
 407                         otd = (OptionalTaskDescriptor)((Hashtable)optionaltaskdescriptors.get(processedclass)).get(otd);
 408                     }
 409                     else optionaltaskdescriptors.get(processedclass).put(otd, otd);
 410                     temp = computeEdges(tn, newdepth, newhashset, temppredicate);
 411                     temp.add(otd);
 412                     return temp;
 413                 }
 414             }
 415             else{
 416                 HashSet temp = new HashSet();
 417                 if( tn.isMultipleParams() ){
 418                     if( goodMultiple(tn) ){
 419                         temppredicate = combinePredicates(predicate, returnPredicate(tn));
 420                         System.out.println("Good multiple, not Optional "+tn.getName());
 421                     }
 422                     else{
 423                         System.out.println("Bad multiple, not Optional "+tn.getName());
 424                         return temp;
 425                     }
 426                 }
 427                 else temppredicate = combinePredicates(temppredicate, predicate);
 428                 //if not optional but terminal just return an empty set.
 429                 if( !((Iterator)tn.edges()).hasNext() ||  visited.contains(tn) || tn.isSelfLoop()){
 430                     return temp;
 431                 }
 432                 //if not terminal return the computation of the edges.
 433                 else{
 434                     int newdepth = depth + 1;
 435                     visited.add(tn);
 436                     HashSet newhashset = new HashSet(visited);
 437                     return computeEdges(tn, newdepth, newhashset, temppredicate);
 438                 }
 439             }
 440         }
 441         //if there has been a tag change return an empty set.
 442         else{
 443             HashSet temp = new HashSet();
 444             return temp;
 445         }
 446     }
 447
 448     private boolean goodMultiple(EGTaskNode tn){
 449         TaskDescriptor td = tn.getTD();
 450         HashSet classes = new HashSet();
 451         for(int i = 0 ; i<td.numParameters(); i++){
 452             ClassDescriptor cd = td.getParamType(i).getClassDesc();
 453             if(cd.getSymbol().compareTo(classname)!=0)
 454                 classes.add(cd);
 455         }
 456
 457
 458             Stack stack = new Stack();
 459             FlatMethod fm = state.getMethodFlat(td);
 460             FlatNode fn = (FlatNode)fm;
 461
 462             Stack nodestack=new Stack();
 463             HashSet discovered=new HashSet();
 464             nodestack.push(fm);
 465             discovered.add(fm);
 466
 467             //Iterating through the nodes
 468             while(!nodestack.isEmpty()) {
 469                 FlatNode fn1 = (FlatNode) nodestack.pop();
 470                 if (fn1.kind()==FKind.FlatFlagActionNode) {
 471                     FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
 472                     if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
 473                         for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
 474                             TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 475                             TempDescriptor tempd = tfp.getTemp();
 476                             if (classes.contains((ClassDescriptor)((TypeDescriptor)tempd.getType()).getClassDesc()))
 477                                 return false;//return false if a taskexit modifies one of the other parameters
 478                         }
 479                         continue; // avoid queueing the return node if reachable
 480                     }
 481                 }
 482                 /* Queue other nodes past this one */
 483                 for(int i=0;i<fn1.numNext();i++) {
 484                     FlatNode fnext=fn1.getNext(i);
 485                     if (!discovered.contains(fnext)) {
 486                         discovered.add(fnext);
 487                         nodestack.push(fnext);
 488                     }
 489                 }
 490             }
 491             return true;
 492
 493     }
 494
 495     private Predicate returnPredicate(EGTaskNode tn){
 496         Predicate result = new Predicate();
 497         TaskDescriptor td = tn.getTD();
 498         for(int i=0; i<td.numParameters(); i++){
 499             TypeDescriptor typed = td.getParamType(i);
 500             if(((ClassDescriptor)typed.getClassDesc()).getSymbol().compareTo(classname)!=0){
 501                 VarDescriptor vd = td.getParameter(i);
 502                 result.vardescriptors.put(vd.getName(), vd);
 503                 HashSet flaglist = new HashSet();
 504                 flaglist.add((FlagExpressionNode)td.getFlag(vd));
 505                 result.flags.put( vd.getName(), flaglist);
 506                 if((TagExpressionList)td.getTag(vd) != null)
 507                     result.tags.put( vd.getName(), (TagExpressionList)td.getTag(vd));
 508             }
 509         }
 510         return result;
 511     }
 512
 513     /*check if there has been a tag Change*/
 514     private boolean tagChange(EGTaskNode tn){
 515         if(tn.getTD() == null) return false;//to be fixed
 516         FlatMethod fm = state.getMethodFlat(tn.getTD());
 517         FlatNode fn = (FlatNode)fm;
 518
 519         Stack nodestack=new Stack();
 520         HashSet discovered=new HashSet();
 521         nodestack.push(fm);
 522         discovered.add(fm);
 523
 524         //Iterating through the nodes
 525         while(!nodestack.isEmpty()) {
 526             FlatNode fn1 = (FlatNode) nodestack.pop();
 527             if (fn1.kind()==FKind.FlatFlagActionNode) {
 528                 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
 529                 if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
 530                     Iterator it_ttp=ffan.getTempTagPairs();
 531                     if(it_ttp.hasNext()){
 532                         System.out.println("Tag change detected in Task "+tn.getName());
 533                         return true;
 534                     }
 535                     else continue; // avoid queueing the return node if reachable
 536                 }
 537             }
 538
 539             /* Queue other nodes past this one */
 540             for(int i=0;i<fn1.numNext();i++) {
 541                 FlatNode fnext=fn1.getNext(i);
 542                 if (!discovered.contains(fnext)) {
 543                     discovered.add(fnext);
 544                     nodestack.push(fnext);
 545                 }
 546             }
 547         }
 548         return false;
 549     }
 550
 551
 552     private HashSet computeEdges(EGTaskNode tn, int depth, HashSet visited, Predicate predicate){
 553         Hashtable andlist = new Hashtable();
 554         Vector orlist = new Vector();
 555         for(Iterator edges = tn.edges(); edges.hasNext();){
 556             EGTaskNode tntemp = (EGTaskNode)((EGEdge)edges.next()).getTarget();
 557             if(tntemp.type() == OR) orlist.add(tntemp);
 558             else if(tntemp.type() == AND){
 559                 if(andlist.containsKey(tntemp.getName())){
 560                     ((Vector)andlist.get(tntemp.getName())).add(tntemp);}
 561                 else{
 562                     Vector vector = new Vector();
 563                     vector.add(tntemp);
 564                     andlist.put(tntemp.getName(), vector);
 565                 }
 566             }
 567         }
 568
 569         return (createUnion(computeOrVector(orlist, depth, visited, predicate), computeAndList(andlist, depth, visited, predicate)));
 570     }
 571
 572     private HashSet computeTns(Vector tns){
 573         Hashtable andlist = new Hashtable();
 574         Vector orlist = new Vector();
 575         for(Iterator nodes = tns.iterator(); nodes.hasNext();){
 576             EGTaskNode tntemp = (EGTaskNode)nodes.next();
 577             if(tntemp.type() == OR) orlist.add(tntemp);
 578             else if(tntemp.type() == AND){
 579                 if(andlist.containsKey(tntemp.getName())){
 580                     ((Vector)andlist.get(tntemp.getName())).add(tntemp);}
 581                 else{
 582                     Vector vector = new Vector();
 583                     vector.add(tntemp);
 584                     andlist.put(tntemp.getName(), vector);
 585                 }
 586             }
 587         }
 588
 589         return (createUnion(computeOrVector(orlist, 0), computeAndList(andlist, 0)));
 590
 591     }
 592
 593     private  HashSet computeOrVector( Vector orlist, int depth, HashSet visited, Predicate predicate){
 594         if(orlist.isEmpty()){
 595             HashSet temp = new HashSet();
 596             return temp;
 597         }
 598         else{
 599             HashSet temp = new HashSet();
 600             for(Iterator tns = orlist.iterator(); tns.hasNext();){
 601                 EGTaskNode tn = (EGTaskNode)tns.next();
 602                 temp = createUnion(determineIfIsSafe(tn, depth, visited, predicate), temp);
 603             }
 604             return temp;
 605         }
 606
 607     }
 608
 609     private  HashSet computeOrVector( Vector orlist, int depth){
 610         if(orlist.isEmpty()){
 611             HashSet temp = new HashSet();
 612             return temp;
 613         }
 614         else{
 615             HashSet temp = new HashSet();
 616             for(Iterator tns = orlist.iterator(); tns.hasNext();){
 617                 EGTaskNode tn = (EGTaskNode)tns.next();
 618                 HashSet visited = new HashSet();
 619                 Predicate predicate = new Predicate();
 620                 temp = createUnion(determineIfIsSafe(tn, depth, visited, predicate), temp);
 621             }
 622             return temp;
 623         }
 624
 625     }
 626
 627     private  HashSet computeAndList(Hashtable andlist, int depth, HashSet visited, Predicate predicate){
 628         if( andlist.isEmpty()){
 629             HashSet temp = new HashSet();
 630             return temp;
 631         }
 632         else{
 633             HashSet temp = new HashSet();
 634             Collection c = andlist.values();
 635             for(Iterator vectors = c.iterator(); vectors.hasNext();){
 636                 Vector vector = (Vector)vectors.next();
 637                 temp = createUnion(computeAndVector(vector, depth, visited, predicate), temp);
 638             }
 639             return temp;
 640         }
 641
 642     }
 643
 644     private  HashSet computeAndList(Hashtable andlist, int depth){
 645         if( andlist.isEmpty()){
 646             HashSet temp = new HashSet();
 647             return temp;
 648         }
 649         else{
 650             HashSet temp = new HashSet();
 651             Collection c = andlist.values();
 652             for(Iterator vectors = c.iterator(); vectors.hasNext();){
 653                 Vector vector = (Vector)vectors.next();
 654                 temp = createUnion(computeAndVector(vector, depth), temp);
 655             }
 656             return temp;
 657         }
 658
 659     }
 660
 661     private  HashSet computeAndVector(Vector vector, int depth, HashSet visited, Predicate predicate){
 662         HashSet temp = new HashSet();
 663         boolean init = true;
 664         for(Iterator tns = vector.iterator(); tns.hasNext();){
 665             EGTaskNode tn = (EGTaskNode)tns.next();
 666             if (init){
 667                 init = false;
 668                 temp = determineIfIsSafe(tn, depth, visited, predicate);
 669             }
 670             else{
 671                 temp = createIntersection(determineIfIsSafe(tn, depth, visited, predicate), temp);
 672             }
 673         }
 674         return temp;
 675     }
 676
 677     private  HashSet computeAndVector(Vector vector, int depth){
 678         HashSet temp = new HashSet();
 679         boolean init = true;
 680         for(Iterator tns = vector.iterator(); tns.hasNext();){
 681             EGTaskNode tn = (EGTaskNode)tns.next();
 682             if (init){
 683                 init = false;
 684                 HashSet visited = new HashSet();
 685                 Predicate predicate = new Predicate();
 686                 temp = determineIfIsSafe(tn, depth, visited, predicate);
 687             }
 688             else{
 689                 HashSet visited = new HashSet();
 690                 Predicate predicate = new Predicate();
 691                 temp = createIntersection(determineIfIsSafe(tn, depth, visited, predicate), temp);
 692             }
 693         }
 694         return temp;
 695     }
 696
 697     private HashSet createUnion( HashSet A, HashSet B){
 698         A.addAll(B);
 699
 700         return A;
 701     }
 702
 703
 704     private HashSet createIntersection( HashSet A, HashSet B){
 705         HashSet result = new HashSet();
 706         for(Iterator b_it = B.iterator(); b_it.hasNext();){
 707             OptionalTaskDescriptor otd_b = (OptionalTaskDescriptor)b_it.next();
 708             for(Iterator a_it = A.iterator(); a_it.hasNext();){
 709                 OptionalTaskDescriptor otd_a = (OptionalTaskDescriptor)a_it.next();
 710                 if(((String)otd_a.td.getSymbol()).compareTo((String)otd_b.td.getSymbol())==0){
 711                     HashSet newfs = new HashSet();
 712                     newfs.addAll(otd_a.flagstates);
 713                     newfs.addAll(otd_b.flagstates);
 714                     int newdepth = (otd_a.depth < otd_b.depth) ? otd_a.depth : otd_b.depth;
 715                     OptionalTaskDescriptor newotd = new OptionalTaskDescriptor(otd_b.td, newfs, newdepth, combinePredicates(otd_a.predicate, otd_b.predicate));
 716                     if(optionaltaskdescriptors.get(processedclass).get(newotd)!=null){
 717                         newotd = (OptionalTaskDescriptor)((Hashtable)optionaltaskdescriptors.get(processedclass)).get(newotd);
 718                     }
 719                     else optionaltaskdescriptors.get(processedclass).put(newotd, newotd);
 720                     result.add(newotd);
 721                 }
 722             }
 723         }
 724
 725         return result;
 726     }
 727
 728     private Predicate combinePredicates(Predicate A, Predicate B){
 729         Predicate result = new Predicate();
 730         result.vardescriptors.putAll(A.vardescriptors);
 731         result.flags.putAll(A.flags);
 732         result.tags.putAll(A.tags);
 733         Collection c = B.vardescriptors.values();
 734         for(Iterator  varit = c.iterator(); varit.hasNext();){//maybe change that
 735             VarDescriptor vd = (VarDescriptor)varit.next();
 736             if(result.vardescriptors.containsKey(vd.getName())) System.out.println("Already in ");
 737             else {
 738                 result.vardescriptors.put(vd.getName(), vd);
 739             }
 740         }
 741         Collection vardesc = result.vardescriptors.values();
 742         for(Iterator varit = vardesc.iterator(); varit.hasNext();){
 743             VarDescriptor vd = (VarDescriptor)varit.next();
 744             HashSet bflags = B.flags.get(vd.getName());
 745             if( bflags == null ){
 746                 continue;
 747             }
 748             else{
 749                 if (result.flags.containsKey(vd.getName())) ((HashSet)result.flags.get(vd.getName())).addAll(bflags);
 750                 else result.flags.put(vd.getName(), bflags);
 751             }
 752             TagExpressionList btags = B.tags.get(vd.getName());
 753             if( btags != null ){
 754                 if (result.tags.containsKey(vd.getName())) System.out.println("Tag found but there should be nothing to do because same tag");
 755                 else result.tags.put(vd.getName(), btags);
 756             }
 757         }
 758         return result;
 759     }
 760
 761     /////////DEBUG
 762     /*Thoose two tasks create the dot file named markedgraph.dot */
 763
 764     private void createDOTFile(String classname) throws java.io.IOException {
 765         Collection v = reducedgraph.values();
 766         java.io.PrintWriter output;
 767         File dotfile_flagstates= new File("markedgraph_"+classname+".dot");
 768         FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
 769         output = new java.io.PrintWriter(dotstream, true);
 770         output.println("digraph dotvisitor {");
 771         output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
 772         output.println("\tedge [fontsize=6];");
 773         traverse(output, v);
 774         output.println("}\n");
 775     }
 776
 777     private void traverse(java.io.PrintWriter output, Collection v) {
 778         EGTaskNode tn;
 779
 780         for(Iterator it1 = v.iterator(); it1.hasNext();){
 781             tn = (EGTaskNode)it1.next();
 782             output.println("\t"+tn.getLabel()+" [label=\""+tn.getTextLabel()+"\"");
 783             if (tn.isOptional()){
 784                 if (tn.isMultipleParams()) output.println(", shape = tripleoctagon");
 785                 else output.println(", shape=doubleoctagon");
 786             }
 787             else if (tn.isMultipleParams()) output.println(", shape=octagon");
 788             if (tn.type()==AND) output.println(", color=blue");
 789             output.println("];");
 790
 791             for(Iterator it2 = tn.edges();it2.hasNext();){
 792                 EGTaskNode tn2 = (EGTaskNode)((Edge)it2.next()).getTarget();
 793                 output.println("\t"+tn.getLabel()+" -> "+tn2.getLabel()+";");
 794             }
 795         }
 796     }
 797
 798     ////////////////////
 799     /* returns a set of the possible sets of flagstates
 800        resulting from the execution of the optional task.
 801        To do it with have to look for TaskExit FlatNodes
 802        in the IR.
 803     */
 804     private void resultingFS(OptionalTaskDescriptor otd, String classname){
 805         Stack stack = new Stack();
 806         HashSet result = new HashSet();
 807         FlatMethod fm = state.getMethodFlat((TaskDescriptor)otd.td);
 808         FlatNode fn = (FlatNode)fm;
 809
 810         Stack nodestack=new Stack();
 811         HashSet discovered=new HashSet();
 812         nodestack.push(fm);
 813         discovered.add(fm);
 814
 815         //Iterating through the nodes
 816         while(!nodestack.isEmpty()) {
 817             FlatNode fn1 = (FlatNode) nodestack.pop();
 818             if (fn1.kind()==FKind.FlatFlagActionNode) {
 819                 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
 820                 if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
 821                     HashSet tempset = new HashSet();
 822                     for(Iterator it_fs = otd.flagstates.iterator(); it_fs.hasNext();){
 823                         FlagState fstemp = (FlagState)it_fs.next();
 824                         for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
 825                             TempFlagPair tfp=(TempFlagPair)it_tfp.next();
 826                             TempDescriptor td = tfp.getTemp();
 827                             if (((String)((ClassDescriptor)((TypeDescriptor)td.getType()).getClassDesc()).getSymbol()).compareTo(classname)==0){
 828                                 fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
 829                             }
 830                         }
 831                         tempset.add(fstemp);
 832                     }
 833                     result.add(tempset);
 834                     continue; // avoid queueing the return node if reachable
 835                 }
 836             }else if (fn1.kind()==FKind.FlatReturnNode) {
 837                 result.add(otd.flagstates);
 838             }
 839
 840             /* Queue other nodes past this one */
 841             for(int i=0;i<fn1.numNext();i++) {
 842                 FlatNode fnext=fn1.getNext(i);
 843                 if (!discovered.contains(fnext)) {
 844                     discovered.add(fnext);
 845                     nodestack.push(fnext);
 846                 }
 847             }
 848         }
 849         otd.exitfses=result;
 850     }
 851 }
 852
 853