Programming Languages Research Group: Git - IRC.git/blob

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