1 package Analysis.TaskStateAnalysis;
8 import java.io.FileWriter;
9 import java.io.FileOutputStream;
12 public class SafetyAnalysis {
13 private Hashtable executiongraph;
14 private Hashtable<ClassDescriptor, Hashtable<FlagState, Set<OptionalTaskDescriptor>>> safeexecution; //to use to build code
16 private TaskAnalysis taskanalysis;
17 private Hashtable<ClassDescriptor, Hashtable<OptionalTaskDescriptor, OptionalTaskDescriptor>> optionaltaskdescriptors;
18 private Hashtable<FlagState, Hashtable<TaskIndex, Set<OptionalTaskDescriptor>>> fstotimap;
20 private ClassDescriptor processedclass;
22 public Hashtable<ClassDescriptor, Hashtable<FlagState, Set<OptionalTaskDescriptor>>> getResult() {
26 public Hashtable<ClassDescriptor, Hashtable<OptionalTaskDescriptor, OptionalTaskDescriptor>> getOptionalTaskDescriptors() {
27 return optionaltaskdescriptors;
30 /* Structure that stores a possible optional task which would be
31 safe to execute and the possible flagstates the object could be
32 in before executing the task during an execution without
36 public SafetyAnalysis(Hashtable executiongraph, State state, TaskAnalysis taskanalysis) {
37 this.executiongraph = executiongraph;
38 this.safeexecution = new Hashtable();
40 this.taskanalysis = taskanalysis;
41 this.optionaltaskdescriptors = new Hashtable();
42 this.fstotimap=new Hashtable<FlagState, Hashtable<TaskIndex, Set<OptionalTaskDescriptor>>>();
45 /* Builds map of fs -> EGTasknodes that can fire on fs for class cd */
47 private Hashtable<FlagState, Set<EGTaskNode>> buildMap(ClassDescriptor cd) {
48 Hashtable<FlagState, Set<EGTaskNode>> table=new Hashtable<FlagState, Set<EGTaskNode>>();
49 for(Iterator it=((Set)executiongraph.get(cd)).iterator(); it.hasNext(); ) {
50 EGTaskNode node=(EGTaskNode)it.next();
51 if (node.getFS()!=null) {
52 if (!table.containsKey(node.getFS()))
53 table.put(node.getFS(), new HashSet<EGTaskNode>());
54 table.get(node.getFS()).add(node);
61 public Set<OptionalTaskDescriptor> getOptions(FlagState fs, TaskDescriptor td, int index) {
62 return fstotimap.get(fs).get(new TaskIndex(td, index));
65 public Set<OptionalTaskDescriptor> getOptions(FlagState fs, TaskIndex ti) {
66 return fstotimap.get(fs).get(ti);
69 public Set<TaskIndex> getTaskIndex(FlagState fs) {
70 return fstotimap.get(fs).keySet();
74 /* Builds map of fs -> set of fs that depend on this fs */
76 private Hashtable<FlagState, Set<FlagState>> buildUseMap(ClassDescriptor cd) {
77 Hashtable<FlagState, Set<FlagState>> table=new Hashtable<FlagState, Set<FlagState>>();
78 for(Iterator it=((Set)executiongraph.get(cd)).iterator(); it.hasNext(); ) {
79 EGTaskNode node=(EGTaskNode)it.next();
80 if (node.getFS()!=null) {
81 if (!table.containsKey(node.getPostFS()))
82 table.put(node.getPostFS(), new HashSet<FlagState>());
83 table.get(node.getPostFS()).add(node.getFS());
89 public void doAnalysis() {
90 Enumeration classit=taskanalysis.flagstates.keys();
92 while (classit.hasMoreElements()) {
93 ClassDescriptor cd=(ClassDescriptor)classit.nextElement();
94 if (!executiongraph.containsKey(cd))
96 Hashtable<FlagState, Set<OptionalTaskDescriptor>> fstootd=new Hashtable<FlagState, Set<OptionalTaskDescriptor>>();
97 safeexecution.put(cd, fstootd);
99 optionaltaskdescriptors.put(cd, new Hashtable<OptionalTaskDescriptor, OptionalTaskDescriptor>());
101 Hashtable<FlagState, Set<EGTaskNode>> fstoegmap=buildMap(cd);
102 Hashtable<FlagState, Set<FlagState>> fsusemap=buildUseMap(cd);
104 HashSet<FlagState> tovisit=new HashSet<FlagState>();
105 tovisit.addAll(taskanalysis.getFlagStates(cd));
107 while(!tovisit.isEmpty()) {
108 FlagState fs=tovisit.iterator().next();
110 if (!fstoegmap.containsKey(fs))
111 continue; //This FS has no task that can trigger on it
112 Set<EGTaskNode> nodeset=fstoegmap.get(fs);
113 analyzeFS(fs, nodeset, fstootd, fsusemap, tovisit);
119 public void analyzeFS(FlagState fs, Set<EGTaskNode> egset, Hashtable<FlagState, Set<OptionalTaskDescriptor>> fstootd, Hashtable<FlagState, Set<FlagState>> fsusemap, HashSet<FlagState> tovisit) {
120 Hashtable<TaskIndex, Set<OptionalTaskDescriptor>> timap=new Hashtable<TaskIndex, Set<OptionalTaskDescriptor>>();
121 Set<TaskIndex> tiselfloops=new HashSet<TaskIndex>();
123 for(Iterator<EGTaskNode> egit=egset.iterator(); egit.hasNext(); ) {
124 EGTaskNode egnode=egit.next();
125 Set<OptionalTaskDescriptor> setotd;
126 if (egnode.isOptional()) {
127 setotd=new HashSet<OptionalTaskDescriptor>();
128 HashSet<FlagState> enterfsset=new HashSet<FlagState>();
130 ClassDescriptor cd=fs.getClassDescriptor();
131 OptionalTaskDescriptor newotd=new OptionalTaskDescriptor(egnode.getTD(), egnode.getIndex(), enterfsset, new Predicate());
132 if(optionaltaskdescriptors.get(cd).containsKey(newotd)) {
133 newotd = optionaltaskdescriptors.get(cd).get(newotd);
137 optionaltaskdescriptors.get(cd).put(newotd, newotd);
140 } else if (tagChange(egnode)) {
141 //Conservatively handle tag changes
142 setotd=new HashSet<OptionalTaskDescriptor>();
143 } else if(egnode.isMultipleParams()) {
144 if( goodMultiple(egnode)) {
145 Predicate p=returnPredicate(egnode);
146 Set<OptionalTaskDescriptor> oldsetotd;
147 if (fstootd.containsKey(egnode.getPostFS()))
148 oldsetotd=fstootd.get(egnode.getPostFS());
150 oldsetotd=new HashSet<OptionalTaskDescriptor>();
151 setotd=new HashSet<OptionalTaskDescriptor>();
152 for(Iterator<OptionalTaskDescriptor> otdit=oldsetotd.iterator(); otdit.hasNext(); ) {
153 OptionalTaskDescriptor oldotd=otdit.next();
154 Predicate newp=combinePredicates(oldotd.predicate, p);
155 OptionalTaskDescriptor newotd=new OptionalTaskDescriptor(oldotd.td, oldotd.getIndex(), oldotd.enterflagstates, newp);
156 ClassDescriptor cd=fs.getClassDescriptor();
157 if(optionaltaskdescriptors.get(cd).containsKey(newotd)) {
158 newotd = optionaltaskdescriptors.get(cd).get(newotd);
162 optionaltaskdescriptors.get(cd).put(newotd, newotd);
167 //Can't propagate anything
168 setotd=new HashSet<OptionalTaskDescriptor>();
171 if (fstootd.containsKey(egnode.getPostFS()))
172 setotd=fstootd.get(egnode.getPostFS());
174 setotd=new HashSet<OptionalTaskDescriptor>();
176 TaskIndex ti=egnode.isRuntime()?new TaskIndex():new TaskIndex(egnode.getTD(), egnode.getIndex());
178 //runtime edges don't do anything...don't have to take
179 //them, can't predict when we can.
180 if (state.selfloops.contains(egnode.getTD().getSymbol())) {
181 System.out.println("Self loop for: "+egnode.getTD()+" "+egnode.getIndex());
182 if (timap.containsKey(ti)) {
183 if (egnode.getPostFS()!=fs) {
184 if (tiselfloops.contains(ti)) {
186 timap.put(ti, setotd);
187 tiselfloops.remove(ti);
190 timap.put(ti, createIntersection(timap.get(ti), setotd, fs.getClassDescriptor()));
195 timap.put(ti, setotd);
196 if (egnode.getPostFS()==fs) {
200 } else if (timap.containsKey(ti)) {
202 timap.put(ti, createIntersection(timap.get(ti), setotd, fs.getClassDescriptor()));
204 timap.put(ti, setotd);
209 //Combine all options
210 HashSet<OptionalTaskDescriptor> set=new HashSet<OptionalTaskDescriptor>();
211 for(Iterator<Set<OptionalTaskDescriptor>> it=timap.values().iterator(); it.hasNext(); ) {
212 Set<OptionalTaskDescriptor> otdset=it.next();
216 if (!fstootd.containsKey(fs)||
217 !fstootd.get(fs).equals(set)) {
218 fstootd.put(fs, set);
219 //Requeue all flagstates that may use our updated results
220 if (fsusemap.containsKey(fs)) {
221 tovisit.addAll(fsusemap.get(fs));
224 fstotimap.put(fs, timap);
227 private HashSet createIntersection(Set A, Set B, ClassDescriptor cd) {
228 HashSet result = new HashSet();
229 for(Iterator b_it = B.iterator(); b_it.hasNext(); ) {
230 OptionalTaskDescriptor otd_b = (OptionalTaskDescriptor)b_it.next();
231 for(Iterator a_it = A.iterator(); a_it.hasNext(); ) {
232 OptionalTaskDescriptor otd_a = (OptionalTaskDescriptor)a_it.next();
233 if(otd_a.td==otd_b.td&&
234 otd_a.getIndex()==otd_b.getIndex()) {
235 HashSet newfs = new HashSet();
236 newfs.addAll(otd_a.enterflagstates);
237 newfs.addAll(otd_b.enterflagstates);
238 OptionalTaskDescriptor newotd = new OptionalTaskDescriptor(otd_b.td, otd_b.getIndex(), newfs, combinePredicates(otd_a.predicate, otd_b.predicate));
239 if(optionaltaskdescriptors.get(cd).get(newotd)!=null) {
240 newotd = optionaltaskdescriptors.get(cd).get(newotd);
244 optionaltaskdescriptors.get(cd).put(newotd, newotd);
253 // This method returns true if the only parameter whose flag is
254 // modified is the tracked one
256 private boolean goodMultiple(EGTaskNode tn) {
257 TaskDescriptor td = tn.getTD();
258 FlatMethod fm = state.getMethodFlat(td);
259 TempDescriptor tmp=fm.getParameter(tn.getIndex());
261 Set<FlatNode> nodeset=fm.getNodeSet();
263 for(Iterator<FlatNode> nodeit=nodeset.iterator(); nodeit.hasNext(); ) {
264 FlatNode fn=nodeit.next();
265 if (fn.kind()==FKind.FlatFlagActionNode) {
266 FlatFlagActionNode ffan=(FlatFlagActionNode)fn;
267 if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
268 for(Iterator it_tfp=ffan.getTempFlagPairs(); it_tfp.hasNext(); ) {
269 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
270 TempDescriptor tempd = tfp.getTemp();
272 return false; //return false if a taskexit modifies one of the other parameters
280 private Predicate returnPredicate(EGTaskNode tn) {
281 Predicate result = new Predicate();
282 TaskDescriptor td = tn.getTD();
283 for(int i=0; i<td.numParameters(); i++) {
284 if(i!=tn.getIndex()) {
285 VarDescriptor vd = td.getParameter(i);
286 result.vardescriptors.add(vd);
287 HashSet<FlagExpressionNode> flaglist = new HashSet<FlagExpressionNode>();
288 flaglist.add(td.getFlag(vd));
289 result.flags.put(vd, flaglist);
290 if (td.getTag(vd)!=null)
291 result.tags.put(vd, td.getTag(vd));
297 private Predicate combinePredicates(Predicate A, Predicate B) {
298 Predicate result = new Predicate();
299 result.vardescriptors.addAll(A.vardescriptors);
300 result.flags.putAll(A.flags);
301 result.tags.putAll(A.tags);
302 Collection c = B.vardescriptors;
303 for(Iterator varit = c.iterator(); varit.hasNext(); ) { //maybe change that
304 VarDescriptor vd = (VarDescriptor)varit.next();
305 if(result.vardescriptors.contains(vd))
306 System.out.println("Already in ");
308 result.vardescriptors.add(vd);
311 Collection vardesc = result.vardescriptors;
312 for(Iterator varit = vardesc.iterator(); varit.hasNext(); ) {
313 VarDescriptor vd = (VarDescriptor)varit.next();
314 HashSet bflags = B.flags.get(vd);
315 if( bflags == null ) {
318 if (result.flags.containsKey(vd))
319 ((HashSet)result.flags.get(vd)).addAll(bflags);
321 result.flags.put(vd, bflags);
323 TagExpressionList btags = B.tags.get(vd);
324 if( btags != null ) {
325 if (result.tags.containsKey(vd))
326 System.out.println("Tag found but there should be nothing to do because same tag");
328 result.tags.put(vd, btags);
335 /* returns a set of the possible sets of flagstates
336 resulting from the execution of the optional task.
337 To do it with have to look for TaskExit FlatNodes
340 private void resultingFS(OptionalTaskDescriptor otd) {
341 Stack stack = new Stack();
342 HashSet result = new HashSet();
343 FlatMethod fm = state.getMethodFlat((TaskDescriptor)otd.td);
344 FlatNode fn = (FlatNode)fm;
346 Stack nodestack=new Stack();
347 HashSet discovered=new HashSet();
350 TempDescriptor temp=fm.getParameter(otd.getIndex());
352 //Iterating through the nodes
353 while(!nodestack.isEmpty()) {
354 FlatNode fn1 = (FlatNode) nodestack.pop();
355 if (fn1.kind()==FKind.FlatFlagActionNode) {
356 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
357 if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
358 HashSet tempset = new HashSet();
359 for(Iterator it_fs = otd.enterflagstates.iterator(); it_fs.hasNext(); ) {
360 FlagState fstemp = (FlagState)it_fs.next();
361 Vector<FlagState> processed=new Vector<FlagState>();
363 for(Iterator it_tfp=ffan.getTempFlagPairs(); it_tfp.hasNext(); ) {
364 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
365 if (tfp.getTemp()==temp)
366 fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
369 processed.add(fstemp);
370 //Process clears first
372 for(Iterator it_ttp=ffan.getTempTagPairs(); it_ttp.hasNext(); ) {
373 TempTagPair ttp=(TempTagPair)it_ttp.next();
375 if (temp==ttp.getTemp()) {
376 Vector<FlagState> oldprocess=processed;
377 processed=new Vector<FlagState>();
379 for (Enumeration en=oldprocess.elements(); en.hasMoreElements(); ) {
380 FlagState fsworking=(FlagState)en.nextElement();
381 if (!ffan.getTagChange(ttp)) {
382 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
383 } else processed.add(fsworking);
388 for(Iterator it_ttp=ffan.getTempTagPairs(); it_ttp.hasNext(); ) {
389 TempTagPair ttp=(TempTagPair)it_ttp.next();
391 if (temp==ttp.getTemp()) {
392 Vector<FlagState> oldprocess=processed;
393 processed=new Vector<FlagState>();
395 for (Enumeration en=oldprocess.elements(); en.hasMoreElements(); ) {
396 FlagState fsworking=(FlagState)en.nextElement();
397 if (ffan.getTagChange(ttp)) {
398 processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
399 } else processed.add(fsworking);
404 tempset.addAll(processed);
407 continue; // avoid queueing the return node if reachable
409 } else if (fn1.kind()==FKind.FlatReturnNode) {
410 result.add(otd.enterflagstates);
413 /* Queue other nodes past this one */
414 for(int i=0; i<fn1.numNext(); i++) {
415 FlatNode fnext=fn1.getNext(i);
416 if (!discovered.contains(fnext)) {
417 discovered.add(fnext);
418 nodestack.push(fnext);
425 private void printTEST() {
426 Enumeration e = safeexecution.keys();
427 while (e.hasMoreElements()) {
428 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
429 System.out.println("\nTesting class : "+cdtemp.getSymbol()+"\n");
430 Hashtable hashtbtemp = safeexecution.get(cdtemp);
431 Enumeration fses = hashtbtemp.keys();
432 while(fses.hasMoreElements()) {
433 FlagState fs = (FlagState)fses.nextElement();
434 System.out.println("\t"+fs.getTextLabel()+"\n\tSafe tasks to execute :\n");
435 HashSet availabletasks = (HashSet)hashtbtemp.get(fs);
436 for(Iterator otd_it = availabletasks.iterator(); otd_it.hasNext(); ) {
437 OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
438 System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n");
439 System.out.println("\t\twith flags :");
440 for(Iterator myfses = otd.enterflagstates.iterator(); myfses.hasNext(); ) {
441 System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel());
443 System.out.println("\t\tand exitflags :");
444 for(Iterator fseshash = otd.exitfses.iterator(); fseshash.hasNext(); ) {
445 HashSet temphs = (HashSet)fseshash.next();
446 System.out.println("");
447 for(Iterator exfses = temphs.iterator(); exfses.hasNext(); ) {
448 System.out.println("\t\t\t"+((FlagState)exfses.next()).getTextLabel());
451 Predicate predicate = otd.predicate;
452 System.out.println("\t\tPredicate constraints :");
453 Collection c = predicate.vardescriptors;
454 for(Iterator varit = c.iterator(); varit.hasNext(); ) {
455 VarDescriptor vard = (VarDescriptor)varit.next();
456 System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol());
458 System.out.println("\t\t------------");
462 System.out.println("\n\n\n\tOptionaltaskdescriptors contains : ");
463 Collection c_otd = optionaltaskdescriptors.get(cdtemp).values();
464 for(Iterator otd_it = c_otd.iterator(); otd_it.hasNext(); ) {
465 OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
466 System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n");
467 System.out.println("\t\twith flags :");
468 for(Iterator myfses = otd.enterflagstates.iterator(); myfses.hasNext(); ) {
469 System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel());
471 System.out.println("\t\tand exitflags :");
472 for(Iterator fseshash = otd.exitfses.iterator(); fseshash.hasNext(); ) {
473 HashSet temphs = (HashSet)fseshash.next();
474 System.out.println("");
475 for(Iterator exfses = temphs.iterator(); exfses.hasNext(); ) {
476 System.out.println("\t\t\t"+((FlagState)exfses.next()).getTextLabel());
479 Predicate predicate = otd.predicate;
480 System.out.println("\t\tPredicate contains :");
481 Collection c = predicate.vardescriptors;
482 for(Iterator varit = c.iterator(); varit.hasNext(); ) {
483 VarDescriptor vard = (VarDescriptor)varit.next();
484 System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol());
485 HashSet temphash = predicate.flags.get(vard.getName());
486 if(temphash == null) System.out.println("null hashset");
487 else System.out.println("\t\t\t"+temphash.size()+" flag(s)");
490 System.out.println("\t\t------------");
495 /*check if there has been a tag Change*/
496 private boolean tagChange(EGTaskNode tn) {
497 if(tn.getTD() == null) return false; //to be fixed
498 FlatMethod fm = state.getMethodFlat(tn.getTD());
499 FlatNode fn = (FlatNode)fm;
501 Stack nodestack=new Stack();
502 HashSet discovered=new HashSet();
506 //Iterating through the nodes
507 while(!nodestack.isEmpty()) {
508 FlatNode fn1 = (FlatNode) nodestack.pop();
509 if (fn1.kind()==FKind.FlatFlagActionNode) {
510 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
511 if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
512 Iterator it_ttp=ffan.getTempTagPairs();
513 if(it_ttp.hasNext()) {
514 System.out.println("Tag change detected in Task "+tn.getName());
516 } else continue; // avoid queueing the return node if reachable
520 /* Queue other nodes past this one */
521 for(int i=0; i<fn1.numNext(); i++) {
522 FlatNode fnext=fn1.getNext(i);
523 if (!discovered.contains(fnext)) {
524 discovered.add(fnext);
525 nodestack.push(fnext);
533 /*Thoose two tasks create the dot file named markedgraph.dot */
535 private void createDOTFile(String classname, Collection v) throws java.io.IOException {
536 java.io.PrintWriter output;
537 File dotfile_flagstates= new File("markedgraph_"+classname+".dot");
538 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,false);
539 output = new java.io.PrintWriter(dotstream, true);
540 output.println("digraph dotvisitor {");
541 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
542 output.println("\tedge [fontsize=6];");
544 output.println("}\n");
547 private void traverse(java.io.PrintWriter output, Collection v) {
550 for(Iterator it1 = v.iterator(); it1.hasNext(); ) {
551 tn = (EGTaskNode)it1.next();
552 output.println("\t"+tn.getLabel()+" [label=\""+tn.getTextLabel()+"\"");
553 if (tn.isOptional()) {
554 if (tn.isMultipleParams())
555 output.println(", shape = tripleoctagon");
557 output.println(", shape=doubleoctagon");
558 } else if (tn.isMultipleParams())
559 output.println(", shape=octagon");
560 output.println("];");
562 for(Iterator it2 = tn.edges(); it2.hasNext(); ) {
563 EGTaskNode tn2 = (EGTaskNode)((Edge)it2.next()).getTarget();
564 output.println("\t"+tn.getLabel()+" -> "+tn2.getLabel()+";");