X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FTaskStateAnalysis%2FSafetyAnalysis.java;h=939613773cf40408298017cbfbd77720e28c5812;hb=26239411e098e42b009ced05f6a8c4f6c5bc98bb;hp=ccee31dc1c7357355eb7639008e7af913a687234;hpb=c7c4035c3310d3306b101f9869e0c3f52638945e;p=IRC.git diff --git a/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java b/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java index ccee31dc..93961377 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java +++ b/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java @@ -1,6 +1,7 @@ package Analysis.TaskStateAnalysis; import java.util.*; import IR.*; +import IR.Tree.*; import IR.Flat.*; import java.io.*; import java.io.File; @@ -9,591 +10,344 @@ import java.io.FileOutputStream; import Util.Edge; public class SafetyAnalysis { - private Hashtable executiongraph; - private TreeMap safeexecution; - private static final int OR = 0; - private static final int AND = 1; - private static final int UNIONFS = 1; - private static final int NOUNION = 0; - private Hashtable reducedgraph; - private String classname; + private Hashtable>> safeexecution; //to use to build code private State state; - - public class MyOptional{ - public TaskDescriptor td; - public HashSet flagstates; - - protected MyOptional(TaskDescriptor td, HashSet flagstates){ - this.td = td; - this.flagstates = flagstates; - } + private TaskAnalysis taskanalysis; + private Hashtable> optionaltaskdescriptors; + private Hashtable>> fstotimap; - public boolean equal(MyOptional myo){ - if (this.td.getSymbol().compareTo(myo.td.getSymbol())==0) - if(this.flagstates.equals(myo.flagstates)) - return true; - return false; - } + private ClassDescriptor processedclass; + + public Hashtable>> getResult() { + return safeexecution; } - - public SafetyAnalysis(Hashtable executiongraph, State state){ + + public Hashtable> getOptionalTaskDescriptors() { + return optionaltaskdescriptors; + } + + /* Structure that stores a possible optional task which would be + safe to execute and the possible flagstates the object could be + in before executing the task during an execution without + failure*/ + + /*Constructor*/ + public SafetyAnalysis(Hashtable executiongraph, State state, TaskAnalysis taskanalysis) { this.executiongraph = executiongraph; - this.safeexecution = new TreeMap(); - this.reducedgraph = new Hashtable(); + this.safeexecution = new Hashtable(); this.state = state; + this.taskanalysis = taskanalysis; + this.optionaltaskdescriptors = new Hashtable(); + this.fstotimap=new Hashtable>>(); } - public void unMark(Vector nodes){ - for(Iterator it = nodes.iterator(); it.hasNext();){ - EGTaskNode tn = (EGTaskNode)it.next(); - tn.unMark(); - } - } + /* Builds map of fs -> EGTasknodes that can fire on fs for class cd */ - public void buildPath() throws java.io.IOException { - - byte[] b = new byte[100] ; - Vector flagstates = new Vector(); - HashSet safetasks = new HashSet(); - System.out.println("Enter the Class of the object concerned :"); - int k = System.in.read(b); - classname = new String(b,0,k-1); - //classname =new String("Test"); - for (int i = 0 ; i<2 ; i++){ - System.out.println("Enter the possible flagstates :"); - k = System.in.read(b); - String previousflagstate = new String(b,0,k-1); - flagstates.add(previousflagstate); - } - - Vector nodes = new Vector(); - nodes = getConcernedClass( classname ); - if(nodes==null) { - System.out.println("Impossible to find "+classname+". Maybe not declared in the source code."); - return; - } - - HashSet tempnodes = new HashSet(); - for(Iterator it = flagstates.iterator(); it.hasNext();){ - Vector tns = new Vector(); - String flagstate = (String)it.next(); - tns = findEGTaskNode(flagstate, nodes); - if(tns==null) { - System.out.println("No task corresponding"); - return; - } - else{ - tempnodes.add(tns); + private Hashtable> buildMap(ClassDescriptor cd) { + Hashtable> table=new Hashtable>(); + for(Iterator it=((Set)executiongraph.get(cd)).iterator();it.hasNext();) { + EGTaskNode node=(EGTaskNode)it.next(); + if (node.getFS()!=null) { + if (!table.containsKey(node.getFS())) + table.put(node.getFS(), new HashSet()); + table.get(node.getFS()).add(node); } } - - EGTaskNode sourcenode = findSourceNode(nodes); - buildSafeExecutions(sourcenode); - - createDOTFile(); - - int counter = 0; - for(Iterator nodesit = tempnodes.iterator(); nodesit.hasNext();){ - Vector tns = (Vector)nodesit.next(); - HashSet availabletasks = new HashSet(); - for(Iterator it = tns.iterator(); it.hasNext();){ - counter++; - unMark(nodes); - EGTaskNode tn = (EGTaskNode)it.next(); - HashSet nodetags = createNodeTags(tn); - availabletasks = createUnion(determineIfIsSafe(tn, nodetags), availabletasks); - //DEBUG - System.out.println("-----------------------------"); - for(Iterator it2 = availabletasks.iterator(); it2.hasNext();){ - MyOptional mm = (MyOptional)it2.next(); - System.out.println("\t"+mm.td.getSymbol()); - System.out.println("with flags :"); - for(Iterator it3 = mm.flagstates.iterator(); it3.hasNext();){ - System.out.println("\t"+((FlagState)it3.next()).getTextLabel()); - } - System.out.println("-----------------------------"); - } - // - if(counter == 1) safetasks = availabletasks; - else safetasks = createIntersection(availabletasks, safetasks, NOUNION); - } - } - - /////DEBUG - System.out.println("\n\n\n\nSAFE TASKS : "); - for(Iterator it2 = safetasks.iterator(); it2.hasNext();){ - MyOptional mm = (MyOptional)it2.next(); - System.out.println("\t"+mm.td.getSymbol()); - System.out.println("with flags :"); - for(Iterator it3 = mm.flagstates.iterator(); it3.hasNext();){ - System.out.println("\t"+((FlagState)it3.next()).getTextLabel()); - } - resultingFS(mm, classname); - } - ////// + return table; } - - public HashSet buildPath(Vector flagstates, ClassDescriptor cd) throws java.io.IOException { - HashSet safetasks = new HashSet(); - Vector nodes = new Vector(); - classname = cd.getSymbol(); - nodes = getConcernedClass( classname ); - if(nodes==null) { - System.out.println("Impossible to find "+classname+". Maybe not declared in the source code."); - return null; - } - - HashSet tempnodes = new HashSet(); - for(Iterator it = flagstates.iterator(); it.hasNext();){ - Vector tns = new Vector(); - String flagstate = (String)it.next(); - tns = findEGTaskNode(flagstate, nodes); - if(tns==null) { - System.out.println("No task corresponding"); - return null; - } - else{ - tempnodes.add(tns); - } - } - - EGTaskNode sourcenode = findSourceNode(nodes); - buildSafeExecutions(sourcenode); - - createDOTFile(); - - int counter = 0; - for(Iterator nodesit = tempnodes.iterator(); nodesit.hasNext();){ - Vector tns = (Vector)nodesit.next(); - HashSet availabletasks = new HashSet(); - for(Iterator it = tns.iterator(); it.hasNext();){ - counter++; - unMark(nodes); - EGTaskNode tn = (EGTaskNode)it.next(); - HashSet nodetags = createNodeTags(tn); - availabletasks = createUnion(determineIfIsSafe(tn, nodetags), availabletasks); - if(counter == 1) safetasks = availabletasks; - else safetasks = createIntersection(availabletasks, safetasks, NOUNION); - } - } - - return safetasks; - - } - - private void buildSafeExecutions(EGTaskNode extremity) throws java.io.IOException{ - - if (extremity.isMarked() || !((Iterator)extremity.edges()).hasNext()){ - if (!((Iterator)extremity.edges()).hasNext()) extremity.mark(); - reducedgraph.put(extremity.getuid(), extremity); - } - else { - process(extremity); - reducedgraph.put(extremity.getuid(), extremity); - extremity.mark(); - for( Iterator it = extremity.edges(); it.hasNext(); ){ - TEdge edge = (TEdge)it.next(); - buildSafeExecutions((EGTaskNode)edge.getTarget()); - } - } - } - - private void process(EGTaskNode tn){ - testIfOptional(tn); - testIfSameTask(tn); - testIfNextIsSelfLoop(tn); - //testIfLoop(tn); - testIfRuntime(tn); - testIfMultiple(tn); - + + public Set getOptions(FlagState fs, TaskDescriptor td, int index) { + return fstotimap.get(fs).get(new TaskIndex(td, index)); } - - private HashSet createNodeTags(EGTaskNode tn){ - HashSet nodetags = new HashSet(); - String flagstate = tn.getFSName(); - String word = new String(); - StringTokenizer st = new StringTokenizer(flagstate); - while (st.hasMoreTokens()){ - word = st.nextToken(); - if (word.compareTo("Tag")==0) - nodetags.add(st.nextToken()); - } - for(Iterator it = nodetags.iterator(); it.hasNext();){ - System.out.println("nodetag :"+it.next()); - } - return nodetags; + + public Set getOptions(FlagState fs, TaskIndex ti) { + return fstotimap.get(fs).get(ti); } - - private boolean tagChange(EGTaskNode tn, HashSet nodetags){ - - HashSet tags = new HashSet(); - String flagstate = tn.getFSName(); - String word = new String(); - StringTokenizer st = new StringTokenizer(flagstate); - while (st.hasMoreTokens()){ - word = st.nextToken(); - if (word.compareTo("Tag")==0) - tags.add(st.nextToken()); - } - for(Iterator it = tags.iterator(); it.hasNext();){ - String tag = (String)it.next(); - if( !nodetags.contains(tag)){ - System.out.println("Tag Change :"+tag); - return true; - } - } - - return false; - + + public Set getTaskIndex(FlagState fs) { + return fstotimap.get(fs).keySet(); } - private void testIfOptional(EGTaskNode tn){ - for(Iterator edges = tn.edges(); edges.hasNext();){ - TEdge edge = (TEdge)edges.next(); - EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); - if (nexttn.getTD()!=null) - if(nexttn.getTD().isOptional(classname)) - nexttn.setOptional(); - } - } - - private void testIfMultiple(EGTaskNode tn){ - for(Iterator edges = tn.edges(); edges.hasNext();){ - TEdge edge = (TEdge)edges.next(); - EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); - if( nexttn.getTD().numParameters() > 1 ){ - System.out.println("Multiple found"); - nexttn.setMultipleParams(); + /* Builds map of fs -> set of fs that depend on this fs */ + + private Hashtable> buildUseMap(ClassDescriptor cd) { + Hashtable> table=new Hashtable>(); + for(Iterator it=((Set)executiongraph.get(cd)).iterator();it.hasNext();) { + EGTaskNode node=(EGTaskNode)it.next(); + if (node.getFS()!=null) { + if (!table.containsKey(node.getPostFS())) + table.put(node.getPostFS(), new HashSet()); + table.get(node.getPostFS()).add(node.getFS()); } - } - } - - private void testIfRuntime(EGTaskNode tn){ - for(Iterator edges = tn.edges(); edges.hasNext();){ - TEdge edge = (TEdge)edges.next(); - EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); - if( ((String)nexttn.getName()).compareTo("Runtime") == 0 ) - nexttn.setAND(); } + return table; } - - private void testIfSameTask(EGTaskNode tn){ - Vector vtemp = new Vector(); - Vector tomark = new Vector(); - for(Iterator edges = tn.edges(); edges.hasNext();){ - TEdge edge = (TEdge)edges.next(); - EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); - int contains = 0; - for (Iterator it = vtemp.iterator(); it.hasNext();){ - EGTaskNode nexttn2 = (EGTaskNode)it.next(); - if (nexttn.getName()==nexttn2.getName()){ - contains = 1; - tomark.add(nexttn); - tomark.add(nexttn2); - } - } - if (contains == 0) vtemp.add(nexttn); - } + + public void doAnalysis() { + Enumeration classit=taskanalysis.flagstates.keys(); - for(Iterator it2 = tomark.iterator(); it2.hasNext();) - ((EGTaskNode)it2.next()).setAND(); - } - - private void testIfNextIsSelfLoop(EGTaskNode tn){ - for(Iterator edges = tn.edges(); edges.hasNext();){ - TEdge edge = (TEdge)edges.next(); - EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); - if(nexttn.isSelfLoop()) nexttn.setAND(); - } - } - - /*private void testIfLoop(EGTaskNode tn){ - for(Iterator edges = tn.edges(); edges.hasNext();){ - TEdge edge = (TEdge)edges.next(); - if (((EGTaskNode)edge.getTarget()).isMarked()){ - ((EGTaskNode)edge.getTarget()).doLoopMarking(); - } - } - }*/ - - private EGTaskNode findSourceNode(Vector nodes){ - for(Iterator it = nodes.iterator(); it.hasNext();){ - EGTaskNode tn = (EGTaskNode)it.next(); - if(tn.isSource()){ - System.out.println("Found Source Node !!"); - return tn; - } - } - return null; - } - - private Vector findEGTaskNode(String previousflagstate, Vector nodes){ - Vector tns = new Vector(); - for(Iterator it = nodes.iterator(); it.hasNext();){ - EGTaskNode tn = (EGTaskNode)it.next(); - if(tn.getFSName().compareTo(previousflagstate)==0) - tns.add(tn); - } - if(tns.size() == 0) - return null; - else if (tns.size() > 1){ - for(Iterator it = tns.iterator(); it.hasNext();){ - EGTaskNode tn = (EGTaskNode)it.next(); - tn.setAND(); - } - } - return tns; - } - - private Vector getConcernedClass( String classname ){ - Enumeration e = executiongraph.keys(); - while( e.hasMoreElements() ){ - ClassDescriptor cd = (ClassDescriptor)e.nextElement(); + while (classit.hasMoreElements()) { + ClassDescriptor cd=(ClassDescriptor)classit.nextElement(); + if (!executiongraph.containsKey(cd)) + continue; + Hashtable> fstootd=new Hashtable>(); + safeexecution.put(cd, fstootd); + + optionaltaskdescriptors.put(cd, new Hashtable()); + + Hashtable> fstoegmap=buildMap(cd); + Hashtable> fsusemap=buildUseMap(cd); - if (classname.compareTo(cd.getSymbol())==0) - return (Vector)executiongraph.get(cd); + HashSet tovisit=new HashSet(); + tovisit.addAll(taskanalysis.getFlagStates(cd)); + + while(!tovisit.isEmpty()) { + FlagState fs=tovisit.iterator().next(); + tovisit.remove(fs); + if (!fstoegmap.containsKey(fs)) + continue;//This FS has no task that can trigger on it + Set nodeset=fstoegmap.get(fs); + analyzeFS(fs, nodeset, fstootd, fsusemap, tovisit); + } } - return null; + printTEST(); } - - private HashSet determineIfIsSafe(EGTaskNode tn, HashSet nodetags){ - if(tn == null) return null; - if(!tagChange(tn, nodetags)){ - if(tn.isOptional()){ - HashSet temp = new HashSet(); - if( !((Iterator)tn.edges()).hasNext() || tn.isMarked() || tn.isSelfLoop()){ - HashSet fstemp = new HashSet(); - fstemp.add(tn.getFS()); - MyOptional mo = new MyOptional(tn.getTD(), fstemp); - temp.add(mo); - return temp; - } - else{ - tn.mark(); - temp = computeEdges(tn, nodetags); - HashSet fstemp = new HashSet(); - fstemp.add(tn.getFS()); - MyOptional mo = new MyOptional(tn.getTD(), fstemp); - temp.add(mo); - return temp; - } - } - else{ - if( !((Iterator)tn.edges()).hasNext() || tn.isMarked() || tn.isSelfLoop()){ - HashSet temp = new HashSet(); - return temp; + + public void analyzeFS(FlagState fs, Set egset, Hashtable> fstootd, Hashtable> fsusemap, HashSet tovisit) { + Hashtable> timap=new Hashtable>(); + Set tiselfloops=new HashSet(); + + for(Iterator egit=egset.iterator();egit.hasNext();) { + EGTaskNode egnode=egit.next(); + Set setotd; + if (egnode.isOptional()) { + setotd=new HashSet(); + HashSet enterfsset=new HashSet(); + enterfsset.add(fs); + ClassDescriptor cd=fs.getClassDescriptor(); + OptionalTaskDescriptor newotd=new OptionalTaskDescriptor(egnode.getTD(), egnode.getIndex(), enterfsset, new Predicate()); + if(optionaltaskdescriptors.get(cd).containsKey(newotd)) { + newotd = optionaltaskdescriptors.get(cd).get(newotd); + } else { + newotd.setuid(); + resultingFS(newotd); + optionaltaskdescriptors.get(cd).put(newotd, newotd); } - else{ - tn.mark(); - return computeEdges(tn, nodetags); + setotd.add(newotd); + } else if (tagChange(egnode)) { + //Conservatively handle tag changes + setotd=new HashSet(); + } else if(egnode.isMultipleParams()) { + if( goodMultiple(egnode)){ + Predicate p=returnPredicate(egnode); + Set oldsetotd; + if (fstootd.containsKey(egnode.getPostFS())) + oldsetotd=fstootd.get(egnode.getPostFS()); + else + oldsetotd=new HashSet(); + setotd=new HashSet(); + for(Iterator otdit=oldsetotd.iterator();otdit.hasNext();) { + OptionalTaskDescriptor oldotd=otdit.next(); + Predicate newp=combinePredicates(oldotd.predicate, p); + OptionalTaskDescriptor newotd=new OptionalTaskDescriptor(oldotd.td, oldotd.getIndex(), oldotd.enterflagstates, newp); + ClassDescriptor cd=fs.getClassDescriptor(); + if(optionaltaskdescriptors.get(cd).containsKey(newotd)) { + newotd = optionaltaskdescriptors.get(cd).get(newotd); + } else { + newotd.setuid(); + resultingFS(newotd); + optionaltaskdescriptors.get(cd).put(newotd, newotd); + } + setotd.add(newotd); + } + } else { + //Can't propagate anything + setotd=new HashSet(); } + } else { + if (fstootd.containsKey(egnode.getPostFS())) + setotd=fstootd.get(egnode.getPostFS()); + else + setotd=new HashSet(); } - } - else{ - HashSet temp = new HashSet(); - return temp; - } - } - - private HashSet computeEdges(EGTaskNode tn, HashSet nodetags){ - Hashtable andlist = new Hashtable(); - Vector orlist = new Vector(); - for(Iterator edges = tn.edges(); edges.hasNext();){ - EGTaskNode tntemp = (EGTaskNode)((TEdge)edges.next()).getTarget(); - if(tntemp.type() == OR) orlist.add(tntemp); - else if(tntemp.type() == AND){ - if(andlist.containsKey(tntemp.getName())){ - ((Vector)andlist.get(tntemp.getName())).add(tntemp);} - else{ - Vector vector = new Vector(); - vector.add(tntemp); - andlist.put(tntemp.getName(), vector); + TaskIndex ti=egnode.isRuntime()?new TaskIndex():new TaskIndex(egnode.getTD(), egnode.getIndex()); + if (!ti.runtime) { + //runtime edges don't do anything...don't have to take + //them, can't predict when we can. + if (state.selfloops.contains(egnode.getTD().getSymbol())) { + System.out.println("Self loop for: "+egnode.getTD()+" "+egnode.getIndex()); + if (timap.containsKey(ti)) { + if (egnode.getPostFS()!=fs) { + if (tiselfloops.contains(ti)) { + //dump old self loop + timap.put(ti, setotd); + tiselfloops.remove(ti); + } else { + //standard and case + timap.put(ti, createIntersection(timap.get(ti), setotd, fs.getClassDescriptor())); + } + } + } else { + //mark as self loop + timap.put(ti, setotd); + if (egnode.getPostFS()==fs) { + tiselfloops.add(ti); + } + } + } else if (timap.containsKey(ti)) { + //AND case + timap.put(ti, createIntersection(timap.get(ti), setotd, fs.getClassDescriptor())); + } else { + timap.put(ti, setotd); } } } - - return (createUnion(computeOrVector(orlist, nodetags), computeAndList(andlist, nodetags))); - } - private HashSet computeOrVector( Vector orlist, HashSet nodetags){ - if(orlist.isEmpty()){ - HashSet temp = new HashSet(); - return temp; - } - else{ - HashSet temp = new HashSet(); - for(Iterator tns = orlist.iterator(); tns.hasNext();){ - EGTaskNode tn = (EGTaskNode)tns.next(); - temp = createUnion(determineIfIsSafe(tn, nodetags), temp); - } - return temp; - } - - } - - private HashSet computeAndList(Hashtable andlist, HashSet nodetags){ - if( andlist.isEmpty()){ - HashSet temp = new HashSet(); - return temp; + //Combine all options + HashSet set=new HashSet(); + for(Iterator> it=timap.values().iterator();it.hasNext();) { + Set otdset=it.next(); + set.addAll(otdset); } - else{ - HashSet temp = new HashSet(); - Collection c = andlist.values(); - for(Iterator vectors = c.iterator(); vectors.hasNext();){ - Vector vector = (Vector)vectors.next(); - temp = createUnion(computeAndVector(vector, nodetags), temp); + + if (!fstootd.containsKey(fs)|| + !fstootd.get(fs).equals(set)) { + fstootd.put(fs, set); + //Requeue all flagstates that may use our updated results + if (fsusemap.containsKey(fs)) { + tovisit.addAll(fsusemap.get(fs)); } - return temp; } - + fstotimap.put(fs, timap); } - - private HashSet computeAndVector(Vector vector, HashSet nodetags){ - HashSet temp = new HashSet(); - boolean init = true; - for(Iterator tns = vector.iterator(); tns.hasNext();){ - EGTaskNode tn = (EGTaskNode)tns.next(); - if (init){ - init = false; - temp = determineIfIsSafe(tn, nodetags); - //DEBUG - System.out.println("first and vector : "); - for(Iterator it = temp.iterator(); it.hasNext();){ - MyOptional mm = (MyOptional)it.next(); - System.out.println(mm.td.getSymbol()); - System.out.println("with flag :"); - for(Iterator it3 = mm.flagstates.iterator(); it3.hasNext();){ - System.out.println(((FlagState)it3.next()).getTextLabel()); - } - } - } - else{ - temp = createIntersection(determineIfIsSafe(tn, nodetags), temp, UNIONFS); - //DEBUG - System.out.println("another and vector : "); - for(Iterator it = temp.iterator(); it.hasNext();){ - MyOptional mm = (MyOptional)it.next(); - System.out.println(mm.td.getSymbol()); - System.out.println("with flag :"); - for(Iterator it3 = mm.flagstates.iterator(); it3.hasNext();){ - System.out.println(((FlagState)it3.next()).getTextLabel()); - } + + private HashSet createIntersection(Set A, Set B, ClassDescriptor cd){ + HashSet result = new HashSet(); + for(Iterator b_it = B.iterator(); b_it.hasNext();){ + OptionalTaskDescriptor otd_b = (OptionalTaskDescriptor)b_it.next(); + for(Iterator a_it = A.iterator(); a_it.hasNext();){ + OptionalTaskDescriptor otd_a = (OptionalTaskDescriptor)a_it.next(); + if(otd_a.td==otd_b.td&& + otd_a.getIndex()==otd_b.getIndex()) { + HashSet newfs = new HashSet(); + newfs.addAll(otd_a.enterflagstates); + newfs.addAll(otd_b.enterflagstates); + OptionalTaskDescriptor newotd = new OptionalTaskDescriptor(otd_b.td, otd_b.getIndex(), newfs, combinePredicates(otd_a.predicate, otd_b.predicate)); + if(optionaltaskdescriptors.get(cd).get(newotd)!=null){ + newotd = optionaltaskdescriptors.get(cd).get(newotd); + } else { + newotd.setuid(); + resultingFS(newotd); + optionaltaskdescriptors.get(cd).put(newotd, newotd); + } + result.add(newotd); } } } - // DEBUG - System.out.println("Computation of and vector : "); - for(Iterator it = temp.iterator(); it.hasNext();){ - System.out.println("\t"+(String)((MyOptional)it.next()).td.getSymbol()); - } - - return temp; - } + return result; + } - private HashSet createUnion( HashSet A, HashSet B){ - A.addAll(B); - //remove duplicates (might happend) - System.out.println("A contains "+A.size()+" elements"); - int i = 0; - for(Iterator itA = A.iterator(); itA.hasNext();){ - MyOptional myA = (MyOptional)itA.next(); - i++; - System.out.println("myA = "+myA.td.getSymbol()); - Iterator itA2 = A.iterator(); - for(int j = 0; j nodeset=fm.getNodeSet(); + + for(Iterator nodeit=nodeset.iterator();nodeit.hasNext();) { + FlatNode fn=nodeit.next(); + if (fn.kind()==FKind.FlatFlagActionNode) { + FlatFlagActionNode ffan=(FlatFlagActionNode)fn; + if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) { + for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) { + TempFlagPair tfp=(TempFlagPair)it_tfp.next(); + TempDescriptor tempd = tfp.getTemp(); + if(tempd!=tmp) + return false; //return false if a taskexit modifies one of the other parameters + } } } } - return A; + return true; } - - private HashSet createIntersection( HashSet A, HashSet B, int option){ - HashSet result = new HashSet(); - for(Iterator itB = B.iterator(); itB.hasNext();){ - MyOptional myB = (MyOptional)itB.next(); - for(Iterator itA = A.iterator(); itA.hasNext();){ - MyOptional myA = (MyOptional)itA.next(); - if(((String)myA.td.getSymbol()).compareTo((String)myB.td.getSymbol())==0){ - if(option==UNIONFS){ - HashSet newfs = new HashSet(); - newfs.addAll(myA.flagstates); - newfs.addAll(myB.flagstates); - MyOptional newmy = new MyOptional(myB.td, newfs); - result.add(newmy); - } - else{//to do : don't duplicate tasks with same fses - result.add(myA); - result.add(myB); - } - } + + private Predicate returnPredicate(EGTaskNode tn){ + Predicate result = new Predicate(); + TaskDescriptor td = tn.getTD(); + for(int i=0; i flaglist = new HashSet(); + flaglist.add(td.getFlag(vd)); + result.flags.put(vd, flaglist); + if (td.getTag(vd)!=null) + result.tags.put(vd, td.getTag(vd)); } } return result; } - /////////DEBUG - - private void createDOTFile() throws java.io.IOException { - Collection v = reducedgraph.values(); - java.io.PrintWriter output; - File dotfile_flagstates= new File("reducedtree.dot"); - FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true); - output = new java.io.PrintWriter(dotstream, true); - output.println("digraph dotvisitor {"); - output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];"); - output.println("\tedge [fontsize=6];"); - traverse(output, v); - output.println("}\n"); - } - - private void traverse(java.io.PrintWriter output, Collection v) { - EGTaskNode tn; - - for(Iterator it1 = v.iterator(); it1.hasNext();){ - tn = (EGTaskNode)it1.next(); - output.println("\t"+tn.getLabel()+" [label=\""+tn.getTextLabel()+"\""); - if (tn.isOptional()){ - if (tn.isMultipleParams()) output.println(", shape = tripleoctagon"); - else output.println(", shape=doubleoctagon"); + private Predicate combinePredicates(Predicate A, Predicate B){ + Predicate result = new Predicate(); + result.vardescriptors.addAll(A.vardescriptors); + result.flags.putAll(A.flags); + result.tags.putAll(A.tags); + Collection c = B.vardescriptors; + for(Iterator varit = c.iterator(); varit.hasNext();){//maybe change that + VarDescriptor vd = (VarDescriptor)varit.next(); + if(result.vardescriptors.contains(vd)) + System.out.println("Already in "); + else { + result.vardescriptors.add(vd); } - else if (tn.isMultipleParams()) output.println(", shape=octagon"); - if (tn.type()==AND) output.println(", color=blue"); - output.println("];"); - - for(Iterator it2 = tn.edges();it2.hasNext();){ - EGTaskNode tn2 = (EGTaskNode)((Edge)it2.next()).getTarget(); - output.println("\t"+tn.getLabel()+" -> "+tn2.getLabel()+";"); + } + Collection vardesc = result.vardescriptors; + for(Iterator varit = vardesc.iterator(); varit.hasNext();){ + VarDescriptor vd = (VarDescriptor)varit.next(); + HashSet bflags = B.flags.get(vd); + if( bflags == null ){ + continue; + } else { + if (result.flags.containsKey(vd)) + ((HashSet)result.flags.get(vd)).addAll(bflags); + else + result.flags.put(vd, bflags); + } + TagExpressionList btags = B.tags.get(vd); + if( btags != null ){ + if (result.tags.containsKey(vd)) + System.out.println("Tag found but there should be nothing to do because same tag"); + else + result.tags.put(vd, btags); } } + return result; } - + //////////////////// - - private HashSet resultingFS(MyOptional mo, ClassDescriptor cd){ - return resultingFS(mo, cd.getSymbol()); - } - - private HashSet resultingFS(MyOptional mo, String classname){ + /* returns a set of the possible sets of flagstates + resulting from the execution of the optional task. + To do it with have to look for TaskExit FlatNodes + in the IR. + */ + private void resultingFS(OptionalTaskDescriptor otd){ Stack stack = new Stack(); HashSet result = new HashSet(); - FlatMethod fm = state.getMethodFlat((TaskDescriptor)mo.td); + FlatMethod fm = state.getMethodFlat((TaskDescriptor)otd.td); FlatNode fn = (FlatNode)fm; Stack nodestack=new Stack(); HashSet discovered=new HashSet(); nodestack.push(fm); discovered.add(fm); + TempDescriptor temp=fm.getParameter(otd.getIndex()); //Iterating through the nodes while(!nodestack.isEmpty()) { @@ -601,28 +355,59 @@ public class SafetyAnalysis { if (fn1.kind()==FKind.FlatFlagActionNode) { FlatFlagActionNode ffan=(FlatFlagActionNode)fn1; if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) { - //*** - System.out.println("TASKEXIT"); - //*** HashSet tempset = new HashSet(); - for(Iterator it_fs = mo.flagstates.iterator(); it_fs.hasNext();){ + for(Iterator it_fs = otd.enterflagstates.iterator(); it_fs.hasNext();){ FlagState fstemp = (FlagState)it_fs.next(); + Vector processed=new Vector(); + for(Iterator it_tfp=ffan.getTempFlagPairs();it_tfp.hasNext();) { TempFlagPair tfp=(TempFlagPair)it_tfp.next(); - TempDescriptor td = tfp.getTemp(); - if (((String)((ClassDescriptor)((TypeDescriptor)td.getType()).getClassDesc()).getSymbol()).compareTo(classname)==0){ + if (tfp.getTemp()==temp) fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp)); + } + + processed.add(fstemp); + //Process clears first + + for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) { + TempTagPair ttp=(TempTagPair)it_ttp.next(); + + if (temp==ttp.getTemp()) { + Vector oldprocess=processed; + processed=new Vector(); + + for (Enumeration en=oldprocess.elements();en.hasMoreElements();){ + FlagState fsworking=(FlagState)en.nextElement(); + if (!ffan.getTagChange(ttp)){ + processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag()))); + } else processed.add(fsworking); + } + } + } + //Process sets next + for(Iterator it_ttp=ffan.getTempTagPairs();it_ttp.hasNext();) { + TempTagPair ttp=(TempTagPair)it_ttp.next(); + + if (temp==ttp.getTemp()) { + Vector oldprocess=processed; + processed=new Vector(); + + for (Enumeration en=oldprocess.elements();en.hasMoreElements();){ + FlagState fsworking=(FlagState)en.nextElement(); + if (ffan.getTagChange(ttp)){ + processed.addAll(Arrays.asList(fsworking.setTag(ttp.getTag()))); + } else processed.add(fsworking); + } } } - System.out.println("new flag : "+fstemp.getTextLabel()); - tempset.add(fstemp); + //Add to exit states + tempset.addAll(processed); } result.add(tempset); continue; // avoid queueing the return node if reachable } - }else if (fn1.kind()==FKind.FlatReturnNode) { - System.out.println("RETURN NODE REACHABLE WITHOUT TASKEXITS"); - result.add(mo.flagstates); + } else if (fn1.kind()==FKind.FlatReturnNode) { + result.add(otd.enterflagstates); } /* Queue other nodes past this one */ @@ -634,11 +419,151 @@ public class SafetyAnalysis { } } } - return result; + otd.exitfses=result; + } + + private void printTEST(){ + Enumeration e = safeexecution.keys(); + while (e.hasMoreElements()) { + ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement(); + System.out.println("\nTesting class : "+cdtemp.getSymbol()+"\n"); + Hashtable hashtbtemp = safeexecution.get(cdtemp); + Enumeration fses = hashtbtemp.keys(); + while(fses.hasMoreElements()){ + FlagState fs = (FlagState)fses.nextElement(); + System.out.println("\t"+fs.getTextLabel()+"\n\tSafe tasks to execute :\n"); + HashSet availabletasks = (HashSet)hashtbtemp.get(fs); + for(Iterator otd_it = availabletasks.iterator(); otd_it.hasNext();){ + OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next(); + System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n"); + System.out.println("\t\twith flags :"); + for(Iterator myfses = otd.enterflagstates.iterator(); myfses.hasNext();){ + System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel()); + } + System.out.println("\t\tand exitflags :"); + for(Iterator fseshash = otd.exitfses.iterator(); fseshash.hasNext();){ + HashSet temphs = (HashSet)fseshash.next(); + System.out.println(""); + for(Iterator exfses = temphs.iterator(); exfses.hasNext();){ + System.out.println("\t\t\t"+((FlagState)exfses.next()).getTextLabel()); + } + } + Predicate predicate = otd.predicate; + System.out.println("\t\tPredicate constraints :"); + Collection c = predicate.vardescriptors; + for(Iterator varit = c.iterator(); varit.hasNext();){ + VarDescriptor vard = (VarDescriptor)varit.next(); + System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol()); + } + System.out.println("\t\t------------"); + } + } + + System.out.println("\n\n\n\tOptionaltaskdescriptors contains : "); + Collection c_otd = optionaltaskdescriptors.get(cdtemp).values(); + for(Iterator otd_it = c_otd.iterator(); otd_it.hasNext();){ + OptionalTaskDescriptor otd = (OptionalTaskDescriptor)otd_it.next(); + System.out.println("\t\tTASK "+otd.td.getSymbol()+" UID : "+otd.getuid()+"\n"); + System.out.println("\t\twith flags :"); + for(Iterator myfses = otd.enterflagstates.iterator(); myfses.hasNext();){ + System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel()); + } + System.out.println("\t\tand exitflags :"); + for(Iterator fseshash = otd.exitfses.iterator(); fseshash.hasNext();){ + HashSet temphs = (HashSet)fseshash.next(); + System.out.println(""); + for(Iterator exfses = temphs.iterator(); exfses.hasNext();){ + System.out.println("\t\t\t"+((FlagState)exfses.next()).getTextLabel()); + } + } + Predicate predicate = otd.predicate; + System.out.println("\t\tPredicate contains :"); + Collection c = predicate.vardescriptors; + for(Iterator varit = c.iterator(); varit.hasNext();){ + VarDescriptor vard = (VarDescriptor)varit.next(); + System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol()); + HashSet temphash = predicate.flags.get(vard.getName()); + if(temphash == null) System.out.println("null hashset"); + else System.out.println("\t\t\t"+temphash.size()+" flag(s)"); + + } + System.out.println("\t\t------------"); + } + } } + /*check if there has been a tag Change*/ + private boolean tagChange(EGTaskNode tn){ + if(tn.getTD() == null) return false;//to be fixed + FlatMethod fm = state.getMethodFlat(tn.getTD()); + FlatNode fn = (FlatNode)fm; + + Stack nodestack=new Stack(); + HashSet discovered=new HashSet(); + nodestack.push(fm); + discovered.add(fm); + + //Iterating through the nodes + while(!nodestack.isEmpty()) { + FlatNode fn1 = (FlatNode) nodestack.pop(); + if (fn1.kind()==FKind.FlatFlagActionNode) { + FlatFlagActionNode ffan=(FlatFlagActionNode)fn1; + if (ffan.getTaskType() == FlatFlagActionNode.TASKEXIT) { + Iterator it_ttp=ffan.getTempTagPairs(); + if(it_ttp.hasNext()){ + System.out.println("Tag change detected in Task "+tn.getName()); + return true; + } + else continue; // avoid queueing the return node if reachable + } + } + + /* Queue other nodes past this one */ + for(int i=0;i "+tn2.getLabel()+";"); + } + } + } } - -