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>>();
122 for(Iterator<EGTaskNode> egit=egset.iterator();egit.hasNext();) {
123 EGTaskNode egnode=egit.next();
124 Set<OptionalTaskDescriptor> setotd;
125 if (egnode.isOptional()) {
126 setotd=new HashSet<OptionalTaskDescriptor>();
127 HashSet<FlagState> enterfsset=new HashSet<FlagState>();
129 ClassDescriptor cd=fs.getClassDescriptor();
130 OptionalTaskDescriptor newotd=new OptionalTaskDescriptor(egnode.getTD(), egnode.getIndex(), enterfsset, new Predicate());
131 if(optionaltaskdescriptors.get(cd).containsKey(newotd)) {
132 newotd = optionaltaskdescriptors.get(cd).get(newotd);
136 optionaltaskdescriptors.get(cd).put(newotd, newotd);
139 } else if (tagChange(egnode)) {
140 //Conservatively handle tag changes
141 setotd=new HashSet<OptionalTaskDescriptor>();
142 } else if(egnode.isMultipleParams()) {
143 if( goodMultiple(egnode)){
144 Predicate p=returnPredicate(egnode);
145 Set<OptionalTaskDescriptor> oldsetotd;
146 if (fstootd.containsKey(egnode.getPostFS()))
147 oldsetotd=fstootd.get(egnode.getPostFS());
149 oldsetotd=new HashSet<OptionalTaskDescriptor>();
150 setotd=new HashSet<OptionalTaskDescriptor>();
151 for(Iterator<OptionalTaskDescriptor> otdit=oldsetotd.iterator();otdit.hasNext();) {
152 OptionalTaskDescriptor oldotd=otdit.next();
153 Predicate newp=combinePredicates(oldotd.predicate, p);
154 OptionalTaskDescriptor newotd=new OptionalTaskDescriptor(oldotd.td, oldotd.getIndex(), oldotd.enterflagstates, newp);
155 ClassDescriptor cd=fs.getClassDescriptor();
156 if(optionaltaskdescriptors.get(cd).containsKey(newotd)) {
157 newotd = optionaltaskdescriptors.get(cd).get(newotd);
161 optionaltaskdescriptors.get(cd).put(newotd, newotd);
166 //Can't propagate anything
167 setotd=new HashSet<OptionalTaskDescriptor>();
170 if (fstootd.containsKey(egnode.getPostFS()))
171 setotd=fstootd.get(egnode.getPostFS());
173 setotd=new HashSet<OptionalTaskDescriptor>();
175 TaskIndex ti=egnode.isRuntime()?new TaskIndex():new TaskIndex(egnode.getTD(), egnode.getIndex());
177 //runtime edges don't do anything...don't have to take them, can't predict when we can.
178 if (timap.containsKey(ti)) {
180 timap.put(ti, createIntersection(timap.get(ti), setotd, fs.getClassDescriptor()));
182 timap.put(ti, setotd);
187 //Combine all options
188 HashSet<OptionalTaskDescriptor> set=new HashSet<OptionalTaskDescriptor>();
189 for(Iterator<Set<OptionalTaskDescriptor>> it=timap.values().iterator();it.hasNext();) {
190 Set<OptionalTaskDescriptor> otdset=it.next();
194 if (!fstootd.containsKey(fs)||
195 !fstootd.get(fs).equals(set)) {
196 fstootd.put(fs, set);
197 //Requeue all flagstates that may use our updated results
198 if (fsusemap.containsKey(fs)) {
199 tovisit.addAll(fsusemap.get(fs));
202 fstotimap.put(fs, timap);
205 private HashSet createIntersection(Set A, Set B, ClassDescriptor cd){
206 HashSet result = new HashSet();
207 for(Iterator b_it = B.iterator(); b_it.hasNext();){
208 OptionalTaskDescriptor otd_b = (OptionalTaskDescriptor)b_it.next();
209 for(Iterator a_it = A.iterator(); a_it.hasNext();){
210 OptionalTaskDescriptor otd_a = (OptionalTaskDescriptor)a_it.next();
211 if(otd_a.td==otd_b.td&&
212 otd_a.getIndex()==otd_b.getIndex()) {
213 HashSet newfs = new HashSet();
214 newfs.addAll(otd_a.enterflagstates);
215 newfs.addAll(otd_b.enterflagstates);
216 OptionalTaskDescriptor newotd = new OptionalTaskDescriptor(otd_b.td, otd_b.getIndex(), newfs, combinePredicates(otd_a.predicate, otd_b.predicate));
217 if(optionaltaskdescriptors.get(cd).get(newotd)!=null){
218 newotd = optionaltaskdescriptors.get(cd).get(newotd);
222 optionaltaskdescriptors.get(cd).put(newotd, newotd);
231 // This method returns true if the only parameter whose flag is
232 // modified is the tracked one
234 private boolean goodMultiple(EGTaskNode tn){
235 TaskDescriptor td = tn.getTD();
236 FlatMethod fm = state.getMethodFlat(td);
237 TempDescriptor tmp=fm.getParameter(tn.getIndex());
239 Set<FlatNode> nodeset=fm.getNodeSet();
241 for(Iterator<FlatNode> nodeit=nodeset.iterator();nodeit.hasNext();) {
242 FlatNode fn=nodeit.next();
243 if (fn.kind()==FKind.FlatFlagActionNode) {
244 FlatFlagActionNode ffan=(FlatFlagActionNode)fn;
245 if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
246 for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
247 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
248 TempDescriptor tempd = tfp.getTemp();
250 return false; //return false if a taskexit modifies one of the other parameters
258 private Predicate returnPredicate(EGTaskNode tn){
259 Predicate result = new Predicate();
260 TaskDescriptor td = tn.getTD();
261 for(int i=0; i<td.numParameters(); i++) {
262 if(i!=tn.getIndex()) {
263 VarDescriptor vd = td.getParameter(i);
264 result.vardescriptors.add(vd);
265 HashSet<FlagExpressionNode> flaglist = new HashSet<FlagExpressionNode>();
266 flaglist.add(td.getFlag(vd));
267 result.flags.put(vd, flaglist);
268 if (td.getTag(vd)!=null)
269 result.tags.put(vd, td.getTag(vd));
275 private Predicate combinePredicates(Predicate A, Predicate B){
276 Predicate result = new Predicate();
277 result.vardescriptors.addAll(A.vardescriptors);
278 result.flags.putAll(A.flags);
279 result.tags.putAll(A.tags);
280 Collection c = B.vardescriptors;
281 for(Iterator varit = c.iterator(); varit.hasNext();){//maybe change that
282 VarDescriptor vd = (VarDescriptor)varit.next();
283 if(result.vardescriptors.contains(vd))
284 System.out.println("Already in ");
286 result.vardescriptors.add(vd);
289 Collection vardesc = result.vardescriptors;
290 for(Iterator varit = vardesc.iterator(); varit.hasNext();){
291 VarDescriptor vd = (VarDescriptor)varit.next();
292 HashSet bflags = B.flags.get(vd);
293 if( bflags == null ){
296 if (result.flags.containsKey(vd))
297 ((HashSet)result.flags.get(vd)).addAll(bflags);
299 result.flags.put(vd, bflags);
301 TagExpressionList btags = B.tags.get(vd);
303 if (result.tags.containsKey(vd))
304 System.out.println("Tag found but there should be nothing to do because same tag");
306 result.tags.put(vd, btags);
313 /* returns a set of the possible sets of flagstates
314 resulting from the execution of the optional task.
315 To do it with have to look for TaskExit FlatNodes
318 private void resultingFS(OptionalTaskDescriptor otd){
319 Stack stack = new Stack();
320 HashSet result = new HashSet();
321 FlatMethod fm = state.getMethodFlat((TaskDescriptor)otd.td);
322 FlatNode fn = (FlatNode)fm;
324 Stack nodestack=new Stack();
325 HashSet discovered=new HashSet();
328 TempDescriptor temp=fm.getParameter(otd.getIndex());
330 //Iterating through the nodes
331 while(!nodestack.isEmpty()) {
332 FlatNode fn1 = (FlatNode) nodestack.pop();
333 if (fn1.kind()==FKind.FlatFlagActionNode) {
334 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
335 if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
336 HashSet tempset = new HashSet();
337 for(Iterator it_fs = otd.enterflagstates.iterator(); it_fs.hasNext();){
338 FlagState fstemp = (FlagState)it_fs.next();
339 Vector<FlagState> processed=new Vector<FlagState>();
341 for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
342 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
343 if (tfp.getTemp()==temp)
344 fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
347 processed.add(fstemp);
348 //Process clears first
350 for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
351 TempTagPair ttp=(TempTagPair)it_ttp.next();
353 if (temp==ttp.getTemp()) {
354 Vector<FlagState> oldprocess=processed;
355 processed=new Vector<FlagState>();
357 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
358 FlagState fsworking=(FlagState)en.nextElement();
359 if (!ffan.getTagChange(ttp)){
360 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
361 } else processed.add(fsworking);
366 for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
367 TempTagPair ttp=(TempTagPair)it_ttp.next();
369 if (temp==ttp.getTemp()) {
370 Vector<FlagState> oldprocess=processed;
371 processed=new Vector<FlagState>();
373 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
374 FlagState fsworking=(FlagState)en.nextElement();
375 if (ffan.getTagChange(ttp)){
376 processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
377 } else processed.add(fsworking);
382 tempset.addAll(processed);
385 continue; // avoid queueing the return node if reachable
387 } else if (fn1.kind()==FKind.FlatReturnNode) {
388 result.add(otd.enterflagstates);
391 /* Queue other nodes past this one */
392 for(int i=0;i<fn1.numNext();i++) {
393 FlatNode fnext=fn1.getNext(i);
394 if (!discovered.contains(fnext)) {
395 discovered.add(fnext);
396 nodestack.push(fnext);
403 private void printTEST(){
404 Enumeration e = safeexecution.keys();
405 while (e.hasMoreElements()) {
406 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
407 System.out.println("\nTesting class : "+cdtemp.getSymbol()+"\n");
408 Hashtable hashtbtemp = safeexecution.get(cdtemp);
409 Enumeration fses = hashtbtemp.keys();
410 while(fses.hasMoreElements()){
411 FlagState fs = (FlagState)fses.nextElement();
412 System.out.println("\t"+fs.getTextLabel()+"\n\tSafe tasks to execute :\n");
413 HashSet availabletasks = (HashSet)hashtbtemp.get(fs);
414 for(Iterator otd_it = availabletasks.iterator(); otd_it.hasNext();){
415 OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
416 System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n");
417 System.out.println("\t\twith flags :");
418 for(Iterator myfses = otd.enterflagstates.iterator(); myfses.hasNext();){
419 System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel());
421 System.out.println("\t\tand exitflags :");
422 for(Iterator fseshash = otd.exitfses.iterator(); fseshash.hasNext();){
423 HashSet temphs = (HashSet)fseshash.next();
424 System.out.println("");
425 for(Iterator exfses = temphs.iterator(); exfses.hasNext();){
426 System.out.println("\t\t\t"+((FlagState)exfses.next()).getTextLabel());
429 Predicate predicate = otd.predicate;
430 System.out.println("\t\tPredicate constraints :");
431 Collection c = predicate.vardescriptors;
432 for(Iterator varit = c.iterator(); varit.hasNext();){
433 VarDescriptor vard = (VarDescriptor)varit.next();
434 System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol());
436 System.out.println("\t\t------------");
440 System.out.println("\n\n\n\tOptionaltaskdescriptors contains : ");
441 Collection c_otd = optionaltaskdescriptors.get(cdtemp).values();
442 for(Iterator otd_it = c_otd.iterator(); otd_it.hasNext();){
443 OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
444 System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n");
445 System.out.println("\t\twith flags :");
446 for(Iterator myfses = otd.enterflagstates.iterator(); myfses.hasNext();){
447 System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel());
449 System.out.println("\t\tand exitflags :");
450 for(Iterator fseshash = otd.exitfses.iterator(); fseshash.hasNext();){
451 HashSet temphs = (HashSet)fseshash.next();
452 System.out.println("");
453 for(Iterator exfses = temphs.iterator(); exfses.hasNext();){
454 System.out.println("\t\t\t"+((FlagState)exfses.next()).getTextLabel());
457 Predicate predicate = otd.predicate;
458 System.out.println("\t\tPredicate contains :");
459 Collection c = predicate.vardescriptors;
460 for(Iterator varit = c.iterator(); varit.hasNext();){
461 VarDescriptor vard = (VarDescriptor)varit.next();
462 System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol());
463 HashSet temphash = predicate.flags.get(vard.getName());
464 if(temphash == null) System.out.println("null hashset");
465 else System.out.println("\t\t\t"+temphash.size()+" flag(s)");
468 System.out.println("\t\t------------");
473 /*check if there has been a tag Change*/
474 private boolean tagChange(EGTaskNode tn){
475 if(tn.getTD() == null) return false;//to be fixed
476 FlatMethod fm = state.getMethodFlat(tn.getTD());
477 FlatNode fn = (FlatNode)fm;
479 Stack nodestack=new Stack();
480 HashSet discovered=new HashSet();
484 //Iterating through the nodes
485 while(!nodestack.isEmpty()) {
486 FlatNode fn1 = (FlatNode) nodestack.pop();
487 if (fn1.kind()==FKind.FlatFlagActionNode) {
488 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
489 if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
490 Iterator it_ttp=ffan.getTempTagPairs();
491 if(it_ttp.hasNext()){
492 System.out.println("Tag change detected in Task "+tn.getName());
495 else continue; // avoid queueing the return node if reachable
499 /* Queue other nodes past this one */
500 for(int i=0;i<fn1.numNext();i++) {
501 FlatNode fnext=fn1.getNext(i);
502 if (!discovered.contains(fnext)) {
503 discovered.add(fnext);
504 nodestack.push(fnext);
512 /*Thoose two tasks create the dot file named markedgraph.dot */
514 private void createDOTFile(String classname, Collection v) throws java.io.IOException {
515 java.io.PrintWriter output;
516 File dotfile_flagstates= new File("markedgraph_"+classname+".dot");
517 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
518 output = new java.io.PrintWriter(dotstream, true);
519 output.println("digraph dotvisitor {");
520 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
521 output.println("\tedge [fontsize=6];");
523 output.println("}\n");
526 private void traverse(java.io.PrintWriter output, Collection v) {
529 for(Iterator it1 = v.iterator(); it1.hasNext();){
530 tn = (EGTaskNode)it1.next();
531 output.println("\t"+tn.getLabel()+" [label=\""+tn.getTextLabel()+"\"");
532 if (tn.isOptional()){
533 if (tn.isMultipleParams())
534 output.println(", shape = tripleoctagon");
536 output.println(", shape=doubleoctagon");
537 } else if (tn.isMultipleParams())
538 output.println(", shape=octagon");
539 output.println("];");
541 for(Iterator it2 = tn.edges();it2.hasNext();){
542 EGTaskNode tn2 = (EGTaskNode)((Edge)it2.next()).getTarget();
543 output.println("\t"+tn.getLabel()+" -> "+tn2.getLabel()+";");