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