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