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