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