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;
19 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();
44 /* Builds map of fs -> EGTasknodes that can fire on fs for class cd */
46 private Hashtable<FlagState, Set<EGTaskNode>> buildMap(ClassDescriptor cd) {
47 Hashtable<FlagState, Set<EGTaskNode>> table=new Hashtable<FlagState, Set<EGTaskNode>>();
48 for(Iterator it=((Set)executiongraph.get(cd)).iterator();it.hasNext();) {
49 EGTaskNode node=(EGTaskNode)it.next();
50 if (node.getFS()!=null) {
51 if (!table.containsKey(node.getFS()))
52 table.put(node.getFS(), new HashSet<EGTaskNode>());
53 table.get(node.getFS()).add(node);
59 /* Builds map of fs -> set of fs that depend on this fs */
61 private Hashtable<FlagState, Set<FlagState>> buildUseMap(ClassDescriptor cd) {
62 Hashtable<FlagState, Set<FlagState>> table=new Hashtable<FlagState, Set<FlagState>>();
63 for(Iterator it=((Set)executiongraph.get(cd)).iterator();it.hasNext();) {
64 EGTaskNode node=(EGTaskNode)it.next();
65 if (node.getFS()!=null) {
66 if (!table.containsKey(node.getPostFS()))
67 table.put(node.getPostFS(), new HashSet<FlagState>());
68 table.get(node.getPostFS()).add(node.getFS());
74 public void doAnalysis() {
75 Enumeration classit=taskanalysis.flagstates.keys();
77 while (classit.hasMoreElements()) {
78 ClassDescriptor cd=(ClassDescriptor)classit.nextElement();
79 if (!executiongraph.containsKey(cd))
81 Hashtable<FlagState, Set<OptionalTaskDescriptor>> fstootd=new Hashtable<FlagState, Set<OptionalTaskDescriptor>>();
82 safeexecution.put(cd, fstootd);
84 optionaltaskdescriptors.put(cd, new Hashtable<OptionalTaskDescriptor, OptionalTaskDescriptor>());
86 Hashtable<FlagState, Set<EGTaskNode>> fstoegmap=buildMap(cd);
87 Hashtable<FlagState, Set<FlagState>> fsusemap=buildUseMap(cd);
89 HashSet<FlagState> tovisit=new HashSet<FlagState>();
90 tovisit.addAll(taskanalysis.getFlagStates(cd));
92 while(!tovisit.isEmpty()) {
93 FlagState fs=tovisit.iterator().next();
95 if (!fstoegmap.containsKey(fs))
96 continue;//This FS has no task that can trigger on it
97 Set<EGTaskNode> nodeset=fstoegmap.get(fs);
98 analyzeFS(fs, nodeset, fstootd, fsusemap, tovisit);
104 public void analyzeFS(FlagState fs, Set<EGTaskNode> egset, Hashtable<FlagState, Set<OptionalTaskDescriptor>> fstootd, Hashtable<FlagState, Set<FlagState>> fsusemap, HashSet<FlagState> tovisit) {
105 Hashtable<TaskIndex, Set<OptionalTaskDescriptor>> timap=new Hashtable<TaskIndex, Set<OptionalTaskDescriptor>>();
107 for(Iterator<EGTaskNode> egit=egset.iterator();egit.hasNext();) {
108 EGTaskNode egnode=egit.next();
109 Set<OptionalTaskDescriptor> setotd;
110 if (egnode.isOptional()) {
111 setotd=new HashSet<OptionalTaskDescriptor>();
112 HashSet<FlagState> enterfsset=new HashSet<FlagState>();
114 ClassDescriptor cd=fs.getClassDescriptor();
115 OptionalTaskDescriptor newotd=new OptionalTaskDescriptor(egnode.getTD(), egnode.getIndex(), enterfsset, new Predicate());
116 if(optionaltaskdescriptors.get(cd).containsKey(newotd)) {
117 newotd = optionaltaskdescriptors.get(cd).get(newotd);
121 optionaltaskdescriptors.get(cd).put(newotd, newotd);
124 } else if (tagChange(egnode)) {
125 //Conservatively handle tag changes
126 setotd=new HashSet<OptionalTaskDescriptor>();
127 } else if(egnode.isMultipleParams()) {
128 if( goodMultiple(egnode)){
129 Predicate p=returnPredicate(egnode);
130 Set<OptionalTaskDescriptor> oldsetotd;
131 if (fstootd.containsKey(egnode.getPostFS()))
132 oldsetotd=fstootd.get(egnode.getPostFS());
134 oldsetotd=new HashSet<OptionalTaskDescriptor>();
135 setotd=new HashSet<OptionalTaskDescriptor>();
136 for(Iterator<OptionalTaskDescriptor> otdit=oldsetotd.iterator();otdit.hasNext();) {
137 OptionalTaskDescriptor oldotd=otdit.next();
138 Predicate newp=combinePredicates(oldotd.predicate, p);
139 OptionalTaskDescriptor newotd=new OptionalTaskDescriptor(oldotd.td, oldotd.getIndex(), oldotd.enterflagstates, newp);
140 ClassDescriptor cd=fs.getClassDescriptor();
141 if(optionaltaskdescriptors.get(cd).containsKey(newotd)) {
142 newotd = optionaltaskdescriptors.get(cd).get(newotd);
146 optionaltaskdescriptors.get(cd).put(newotd, newotd);
151 //Can't propagate anything
152 setotd=new HashSet<OptionalTaskDescriptor>();
155 if (fstootd.containsKey(egnode.getPostFS()))
156 setotd=fstootd.get(egnode.getPostFS());
158 setotd=new HashSet<OptionalTaskDescriptor>();
161 TaskIndex ti=new TaskIndex(egnode.getTD(), egnode.getIndex());
162 if (timap.containsKey(ti)) {
164 timap.put(ti, createIntersection(timap.get(ti), setotd, fs.getClassDescriptor()));
166 timap.put(ti, setotd);
170 //Combine all options
171 HashSet<OptionalTaskDescriptor> set=new HashSet<OptionalTaskDescriptor>();
172 for(Iterator<Set<OptionalTaskDescriptor>> it=timap.values().iterator();it.hasNext();) {
173 Set<OptionalTaskDescriptor> otdset=it.next();
177 if (!fstootd.containsKey(fs)||
178 !fstootd.get(fs).equals(set)) {
179 fstootd.put(fs, set);
180 //Requeue all flagstates that may use our updated results
181 if (fsusemap.containsKey(fs)) {
182 tovisit.addAll(fsusemap.get(fs));
187 private HashSet createIntersection(Set A, Set B, ClassDescriptor cd){
188 HashSet result = new HashSet();
189 for(Iterator b_it = B.iterator(); b_it.hasNext();){
190 OptionalTaskDescriptor otd_b = (OptionalTaskDescriptor)b_it.next();
191 for(Iterator a_it = A.iterator(); a_it.hasNext();){
192 OptionalTaskDescriptor otd_a = (OptionalTaskDescriptor)a_it.next();
193 if(otd_a.td==otd_b.td&&
194 otd_a.getIndex()==otd_b.getIndex()) {
195 HashSet newfs = new HashSet();
196 newfs.addAll(otd_a.enterflagstates);
197 newfs.addAll(otd_b.enterflagstates);
198 OptionalTaskDescriptor newotd = new OptionalTaskDescriptor(otd_b.td, otd_b.getIndex(), newfs, combinePredicates(otd_a.predicate, otd_b.predicate));
199 if(optionaltaskdescriptors.get(cd).get(newotd)!=null){
200 newotd = optionaltaskdescriptors.get(cd).get(newotd);
204 optionaltaskdescriptors.get(cd).put(newotd, newotd);
213 // This method returns true if the only parameter whose flag is
214 // modified is the tracked one
216 private boolean goodMultiple(EGTaskNode tn){
217 TaskDescriptor td = tn.getTD();
218 FlatMethod fm = state.getMethodFlat(td);
219 TempDescriptor tmp=fm.getParameter(tn.getIndex());
221 Set<FlatNode> nodeset=fm.getNodeSet();
223 for(Iterator<FlatNode> nodeit=nodeset.iterator();nodeit.hasNext();) {
224 FlatNode fn=nodeit.next();
225 if (fn.kind()==FKind.FlatFlagActionNode) {
226 FlatFlagActionNode ffan=(FlatFlagActionNode)fn;
227 if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
228 for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
229 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
230 TempDescriptor tempd = tfp.getTemp();
232 return false; //return false if a taskexit modifies one of the other parameters
240 private Predicate returnPredicate(EGTaskNode tn){
241 Predicate result = new Predicate();
242 TaskDescriptor td = tn.getTD();
243 for(int i=0; i<td.numParameters(); i++) {
244 if(i!=tn.getIndex()) {
245 VarDescriptor vd = td.getParameter(i);
246 result.vardescriptors.add(vd);
247 HashSet<FlagExpressionNode> flaglist = new HashSet<FlagExpressionNode>();
248 flaglist.add(td.getFlag(vd));
249 result.flags.put(vd, flaglist);
250 if (td.getTag(vd)!=null)
251 result.tags.put(vd, td.getTag(vd));
257 private Predicate combinePredicates(Predicate A, Predicate B){
258 Predicate result = new Predicate();
259 result.vardescriptors.addAll(A.vardescriptors);
260 result.flags.putAll(A.flags);
261 result.tags.putAll(A.tags);
262 Collection c = B.vardescriptors;
263 for(Iterator varit = c.iterator(); varit.hasNext();){//maybe change that
264 VarDescriptor vd = (VarDescriptor)varit.next();
265 if(result.vardescriptors.contains(vd))
266 System.out.println("Already in ");
268 result.vardescriptors.add(vd);
271 Collection vardesc = result.vardescriptors;
272 for(Iterator varit = vardesc.iterator(); varit.hasNext();){
273 VarDescriptor vd = (VarDescriptor)varit.next();
274 HashSet bflags = B.flags.get(vd);
275 if( bflags == null ){
278 if (result.flags.containsKey(vd))
279 ((HashSet)result.flags.get(vd)).addAll(bflags);
281 result.flags.put(vd, bflags);
283 TagExpressionList btags = B.tags.get(vd);
285 if (result.tags.containsKey(vd))
286 System.out.println("Tag found but there should be nothing to do because same tag");
288 result.tags.put(vd, btags);
295 /* returns a set of the possible sets of flagstates
296 resulting from the execution of the optional task.
297 To do it with have to look for TaskExit FlatNodes
300 private void resultingFS(OptionalTaskDescriptor otd){
301 Stack stack = new Stack();
302 HashSet result = new HashSet();
303 FlatMethod fm = state.getMethodFlat((TaskDescriptor)otd.td);
304 FlatNode fn = (FlatNode)fm;
306 Stack nodestack=new Stack();
307 HashSet discovered=new HashSet();
310 TempDescriptor temp=fm.getParameter(otd.getIndex());
312 //Iterating through the nodes
313 while(!nodestack.isEmpty()) {
314 FlatNode fn1 = (FlatNode) nodestack.pop();
315 if (fn1.kind()==FKind.FlatFlagActionNode) {
316 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
317 if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
318 HashSet tempset = new HashSet();
319 for(Iterator it_fs = otd.enterflagstates.iterator(); it_fs.hasNext();){
320 FlagState fstemp = (FlagState)it_fs.next();
321 Vector<FlagState> processed=new Vector<FlagState>();
323 for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) {
324 TempFlagPair tfp=(TempFlagPair)it_tfp.next();
325 if (tfp.getTemp()==temp)
326 fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp));
329 processed.add(fstemp);
330 //Process clears first
332 for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
333 TempTagPair ttp=(TempTagPair)it_ttp.next();
335 if (temp==ttp.getTemp()) {
336 Vector<FlagState> oldprocess=processed;
337 processed=new Vector<FlagState>();
339 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
340 FlagState fsworking=(FlagState)en.nextElement();
341 if (!ffan.getTagChange(ttp)){
342 processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag())));
343 } else processed.add(fsworking);
348 for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) {
349 TempTagPair ttp=(TempTagPair)it_ttp.next();
351 if (temp==ttp.getTemp()) {
352 Vector<FlagState> oldprocess=processed;
353 processed=new Vector<FlagState>();
355 for (Enumeration en=oldprocess.elements();en.hasMoreElements();){
356 FlagState fsworking=(FlagState)en.nextElement();
357 if (ffan.getTagChange(ttp)){
358 processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag())));
359 } else processed.add(fsworking);
364 tempset.addAll(processed);
367 continue; // avoid queueing the return node if reachable
369 } else if (fn1.kind()==FKind.FlatReturnNode) {
370 result.add(otd.enterflagstates);
373 /* Queue other nodes past this one */
374 for(int i=0;i<fn1.numNext();i++) {
375 FlatNode fnext=fn1.getNext(i);
376 if (!discovered.contains(fnext)) {
377 discovered.add(fnext);
378 nodestack.push(fnext);
385 private void printTEST(){
386 Enumeration e = safeexecution.keys();
387 while (e.hasMoreElements()) {
388 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
389 System.out.println("\nTesting class : "+cdtemp.getSymbol()+"\n");
390 Hashtable hashtbtemp = safeexecution.get(cdtemp);
391 Enumeration fses = hashtbtemp.keys();
392 while(fses.hasMoreElements()){
393 FlagState fs = (FlagState)fses.nextElement();
394 System.out.println("\t"+fs.getTextLabel()+"\n\tSafe tasks to execute :\n");
395 HashSet availabletasks = (HashSet)hashtbtemp.get(fs);
396 for(Iterator otd_it = availabletasks.iterator(); otd_it.hasNext();){
397 OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
398 System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n");
399 System.out.println("\t\twith flags :");
400 for(Iterator myfses = otd.enterflagstates.iterator(); myfses.hasNext();){
401 System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel());
403 System.out.println("\t\tand exitflags :");
404 for(Iterator fseshash = otd.exitfses.iterator(); fseshash.hasNext();){
405 HashSet temphs = (HashSet)fseshash.next();
406 System.out.println("");
407 for(Iterator exfses = temphs.iterator(); exfses.hasNext();){
408 System.out.println("\t\t\t"+((FlagState)exfses.next()).getTextLabel());
411 Predicate predicate = otd.predicate;
412 System.out.println("\t\tPredicate constraints :");
413 Collection c = predicate.vardescriptors;
414 for(Iterator varit = c.iterator(); varit.hasNext();){
415 VarDescriptor vard = (VarDescriptor)varit.next();
416 System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol());
418 System.out.println("\t\t------------");
422 System.out.println("\n\n\n\tOptionaltaskdescriptors contains : ");
423 Collection c_otd = optionaltaskdescriptors.get(cdtemp).values();
424 for(Iterator otd_it = c_otd.iterator(); otd_it.hasNext();){
425 OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next();
426 System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n");
427 System.out.println("\t\twith flags :");
428 for(Iterator myfses = otd.enterflagstates.iterator(); myfses.hasNext();){
429 System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel());
431 System.out.println("\t\tand exitflags :");
432 for(Iterator fseshash = otd.exitfses.iterator(); fseshash.hasNext();){
433 HashSet temphs = (HashSet)fseshash.next();
434 System.out.println("");
435 for(Iterator exfses = temphs.iterator(); exfses.hasNext();){
436 System.out.println("\t\t\t"+((FlagState)exfses.next()).getTextLabel());
439 Predicate predicate = otd.predicate;
440 System.out.println("\t\tPredicate contains :");
441 Collection c = predicate.vardescriptors;
442 for(Iterator varit = c.iterator(); varit.hasNext();){
443 VarDescriptor vard = (VarDescriptor)varit.next();
444 System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol());
445 HashSet temphash = predicate.flags.get(vard.getName());
446 if(temphash == null) System.out.println("null hashset");
447 else System.out.println("\t\t\t"+temphash.size()+" flag(s)");
450 System.out.println("\t\t------------");
455 /*check if there has been a tag Change*/
456 private boolean tagChange(EGTaskNode tn){
457 if(tn.getTD() == null) return false;//to be fixed
458 FlatMethod fm = state.getMethodFlat(tn.getTD());
459 FlatNode fn = (FlatNode)fm;
461 Stack nodestack=new Stack();
462 HashSet discovered=new HashSet();
466 //Iterating through the nodes
467 while(!nodestack.isEmpty()) {
468 FlatNode fn1 = (FlatNode) nodestack.pop();
469 if (fn1.kind()==FKind.FlatFlagActionNode) {
470 FlatFlagActionNode ffan=(FlatFlagActionNode)fn1;
471 if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) {
472 Iterator it_ttp=ffan.getTempTagPairs();
473 if(it_ttp.hasNext()){
474 System.out.println("Tag change detected in Task "+tn.getName());
477 else continue; // avoid queueing the return node if reachable
481 /* Queue other nodes past this one */
482 for(int i=0;i<fn1.numNext();i++) {
483 FlatNode fnext=fn1.getNext(i);
484 if (!discovered.contains(fnext)) {
485 discovered.add(fnext);
486 nodestack.push(fnext);
494 /*Thoose two tasks create the dot file named markedgraph.dot */
496 private void createDOTFile(String classname, Collection v) throws java.io.IOException {
497 java.io.PrintWriter output;
498 File dotfile_flagstates= new File("markedgraph_"+classname+".dot");
499 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
500 output = new java.io.PrintWriter(dotstream, true);
501 output.println("digraph dotvisitor {");
502 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
503 output.println("\tedge [fontsize=6];");
505 output.println("}\n");
508 private void traverse(java.io.PrintWriter output, Collection v) {
511 for(Iterator it1 = v.iterator(); it1.hasNext();){
512 tn = (EGTaskNode)it1.next();
513 output.println("\t"+tn.getLabel()+" [label=\""+tn.getTextLabel()+"\"");
514 if (tn.isOptional()){
515 if (tn.isMultipleParams())
516 output.println(", shape = tripleoctagon");
518 output.println(", shape=doubleoctagon");
519 } else if (tn.isMultipleParams())
520 output.println(", shape=octagon");
521 output.println("];");
523 for(Iterator it2 = tn.edges();it2.hasNext();){
524 EGTaskNode tn2 = (EGTaskNode)((Edge)it2.next()).getTarget();
525 output.println("\t"+tn.getLabel()+" -> "+tn2.getLabel()+";");