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