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