From 17196a509db8e759543c50a3e09d3aaa250c37a3 Mon Sep 17 00:00:00 2001 From: wmontaz Date: Thu, 26 Jul 2007 23:49:13 +0000 Subject: [PATCH] files added. Code improved. Few corrections. build output code.(not finished yet) --- .../Analysis/TaskStateAnalysis/EGEdge.java | 36 +++++ .../TaskStateAnalysis/EGTaskNode.java | 29 ++++- .../TaskStateAnalysis/ExecutionGraph.java | 45 +------ .../TaskStateAnalysis/MyOptional.java | 45 +++++++ .../Analysis/TaskStateAnalysis/Predicate.java | 18 +++ .../TaskStateAnalysis/SafetyAnalysis.java | 123 ++++++++++-------- Robust/src/IR/Flat/BuildCode.java | 95 ++++++++++++-- Robust/src/IR/State.java | 21 +++ Robust/src/Main/Main.java | 17 ++- 9 files changed, 316 insertions(+), 113 deletions(-) create mode 100644 Robust/src/Analysis/TaskStateAnalysis/EGEdge.java create mode 100644 Robust/src/Analysis/TaskStateAnalysis/MyOptional.java create mode 100644 Robust/src/Analysis/TaskStateAnalysis/Predicate.java diff --git a/Robust/src/Analysis/TaskStateAnalysis/EGEdge.java b/Robust/src/Analysis/TaskStateAnalysis/EGEdge.java new file mode 100644 index 00000000..b4f7d004 --- /dev/null +++ b/Robust/src/Analysis/TaskStateAnalysis/EGEdge.java @@ -0,0 +1,36 @@ +package Analysis.TaskStateAnalysis; +import IR.*; +import Analysis.TaskStateAnalysis.*; +import IR.Tree.*; +import IR.Flat.*; +import java.util.*; +import Util.Edge; + + +public class EGEdge extends Edge{ + EGTaskNode target; + + + public EGEdge(EGTaskNode target){ + super(target); + this.target = target; + } + + public EGTaskNode getTarget(){ + return target; + } + + public int hashCode(){ + return target.hashCode(); + } + + public boolean equals(Object o) { + if (o instanceof EGEdge) { + EGEdge e=(EGEdge)o; + return e.target.equals(target); + } + return false; + } + + +} diff --git a/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java b/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java index 64b04014..59745582 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java +++ b/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java @@ -16,7 +16,7 @@ public class EGTaskNode extends TaskNode { private int type = 0; private FlagState fs; private TaskDescriptor td; - + protected HashSet edges = new HashSet(); public EGTaskNode(){ super("default"); this.fs = null; @@ -46,7 +46,34 @@ public class EGTaskNode extends TaskNode { this.fs = fs; this.td = td; } + + public int hashCode(){ + return getLabel().hashCode(); + } + + public boolean equals(Object o){ + if(o instanceof EGTaskNode){ + EGTaskNode tn=(EGTaskNode) o; + return (tn.getLabel().compareTo(this.getLabel())==0) ? true : false; + } + return false; + } + public HashSet getEdgeSet(){ + return edges; + } + + public void addEdge(EGEdge newedge) { + newedge.setSource(this); + edges.add(newedge); + EGTaskNode tonode=newedge.getTarget(); + tonode.inedges.addElement(newedge); + } + + public Iterator edges(){ + return edges.iterator(); + } + public TaskDescriptor getTD(){ return td; } diff --git a/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java b/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java index ad907054..493ac644 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java +++ b/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java @@ -104,8 +104,6 @@ public class ExecutionGraph { } } - //clean the graph to remove doubles due to reinjection of non totally processed fses in the fifo - graph = clean(graph); } } @@ -142,11 +140,11 @@ public class ExecutionGraph { //link to the parent. if (graph.containsKey(key2)){ target = (EGTaskNode)graph.get(key2); - TEdge newedge=new TEdge(target); + EGEdge newedge=new EGEdge(target); tn.addEdge(newedge); } else { - TEdge newedge=new TEdge(target); + EGEdge newedge=new EGEdge(target); tn.addEdge(newedge); } //put child in graph @@ -177,11 +175,11 @@ public class ExecutionGraph { } if (graph.containsKey(key2)){ target = (EGTaskNode)graph.get(key2); - TEdge newedge=new TEdge(target); + EGEdge newedge=new EGEdge(target); tn.addEdge(newedge); } else { - TEdge newedge=new TEdge(target); + EGEdge newedge=new EGEdge(target); tn.addEdge(newedge); } graph.put(key2, target); @@ -209,39 +207,6 @@ public class ExecutionGraph { } } - //removes the duplicated edges - private Hashtable clean(Hashtable ht){ - Hashtable cleaned = new Hashtable(); - Collection c = ht.values(); - for ( Iterator it = c.iterator(); it.hasNext();){ - EGTaskNode tn = (EGTaskNode)it.next(); - Vector v = tn.getEdgeVector(); - v = removeDouble(v); - tn.removeAllEdges(); - tn.addEdge(v); - cleaned.put(tn.getuid(), tn); - } - return cleaned; - } - - //removes all the edge doubles in vector v - private Vector removeDouble(Vector v){ - - Vector vcleaned = new Vector(); - for (Iterator it = v.iterator(); it.hasNext();){ - - TEdge edge = (TEdge)it.next(); - int contains = 0; - for (Iterator it2 = vcleaned.iterator(); it2.hasNext();){ - if (((EGTaskNode)edge.getTarget()).getuid()==((EGTaskNode)((TEdge)it2.next()).getTarget()).getuid()) contains = 1; - } - - if (contains == 0) vcleaned.add(edge); - } - - return vcleaned; - } - //test if a flagstate has been entirely processed private boolean isFinished(FlagState fs){ @@ -299,7 +264,7 @@ public class ExecutionGraph { for(Iterator it2 = tn.edges();it2.hasNext();){ - output.println("\t"+tn.getLabel()+" -> "+((EGTaskNode)((TEdge)it2.next()).getTarget()).getLabel()+";"); + output.println("\t"+tn.getLabel()+" -> "+((EGTaskNode)((EGEdge)it2.next()).getTarget()).getLabel()+";"); } } } diff --git a/Robust/src/Analysis/TaskStateAnalysis/MyOptional.java b/Robust/src/Analysis/TaskStateAnalysis/MyOptional.java new file mode 100644 index 00000000..1e7d5cb0 --- /dev/null +++ b/Robust/src/Analysis/TaskStateAnalysis/MyOptional.java @@ -0,0 +1,45 @@ +package Analysis.TaskStateAnalysis; +import java.util.*; +import IR.*; +import IR.Tree.*; +import IR.Flat.*; +import java.io.*; +import Util.Edge; + +public class MyOptional{ + public TaskDescriptor td; + public HashSet flagstates; + public int depth; + public HashSet exitfses; + public Predicate predicate; + + protected MyOptional(TaskDescriptor td, HashSet flagstates, int depth, Predicate predicate){ + this.td = td; + this.flagstates = flagstates; + this.depth = depth; + this.exitfses = new HashSet(); + this.predicate = predicate; + + } + + public boolean equals(Object o){ + if (o instanceof MyOptional) { + MyOptional myo = (MyOptional) o; + if (this.td.getSymbol().compareTo(myo.td.getSymbol())==0) + if(this.flagstates.equals(myo.flagstates)) + return true; + return false; + } + else return false; + + } + + public int hashCode() { + return td.hashCode()+flagstates.hashCode()+exitfses.hashCode(); + } + + public String tostring() { + return "Optional task "+td.getSymbol(); + } + +} diff --git a/Robust/src/Analysis/TaskStateAnalysis/Predicate.java b/Robust/src/Analysis/TaskStateAnalysis/Predicate.java new file mode 100644 index 00000000..ea39a952 --- /dev/null +++ b/Robust/src/Analysis/TaskStateAnalysis/Predicate.java @@ -0,0 +1,18 @@ +package Analysis.TaskStateAnalysis; +import java.util.*; +import IR.*; +import IR.Tree.*; +import IR.Flat.*; +import Util.Edge; + +public class Predicate{ + public HashSet vardescriptors; + public Hashtable> flags; + public Hashtable tags; //if there is a tag change, we stop the analysis + + public Predicate(){ + this.vardescriptors = new HashSet(); + this.flags = new Hashtable(); + this.tags = new Hashtable(); + } +} diff --git a/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java b/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java index ff918f53..5bfb7e04 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java +++ b/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java @@ -19,51 +19,25 @@ public class SafetyAnalysis { private String classname; private State state; private TaskAnalysis taskanalysis; - //private Hashtable visited; - //private static int analysisid=0; + private Hashtable myoptionals; + + private ClassDescriptor processedclass; + + + public Hashtable> getResult(){ + return safeexecution; + } + + public Hashtable getMyOptionals(){ + return myoptionals; + } /*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*/ - - public class MyOptional{ - public TaskDescriptor td; - public HashSet flagstates; - public int depth; - public HashSet exitfses; - public Predicate predicate; - - protected MyOptional(TaskDescriptor td, HashSet flagstates, int depth, Predicate predicate){ - this.td = td; - this.flagstates = flagstates; - this.depth = depth; - this.exitfses = new HashSet(); - this.predicate = predicate; - } - - public boolean equal(MyOptional myo){ - if (this.td.getSymbol().compareTo(myo.td.getSymbol())==0) - if(this.depth == myo.depth) - if(this.flagstates.equals(myo.flagstates)) - return true; - return false; - } - } - - public class Predicate{ - public HashSet vardescriptors; - public Hashtable> flags; - public Hashtable tags; //if there is a tag change, we stop the analysis - - public Predicate(){ - this.vardescriptors = new HashSet(); - this.flags = new Hashtable(); - this.tags = new Hashtable(); - } - } - + /*Constructor*/ public SafetyAnalysis(Hashtable executiongraph, State state, TaskAnalysis taskanalysis){ this.executiongraph = executiongraph; @@ -71,7 +45,7 @@ public class SafetyAnalysis { this.reducedgraph = new Hashtable(); this.state = state; this.taskanalysis = taskanalysis; - //this.visited = new Hashtable(); + this.myoptionals = new Hashtable(); } /*finds the the source node in the execution graph*/ @@ -127,8 +101,10 @@ public class SafetyAnalysis { while (e.hasMoreElements()) { System.out.println("\nAnalysing class :"); - ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement(); - classname = cdtemp.getSymbol(); + processedclass=(ClassDescriptor)e.nextElement(); + classname = processedclass.getSymbol(); + HashSet newhashset = new HashSet(); + myoptionals.put(processedclass, newhashset); Hashtable cdhashtable = new Hashtable(); System.out.println("\t"+classname+ "\n"); @@ -150,7 +126,7 @@ public class SafetyAnalysis { createDOTFile( classname ); reducedgraph.clear(); - Collection fses = ((Hashtable)taskanalysis.flagstates.get(cdtemp)).values(); + Collection fses = ((Hashtable)taskanalysis.flagstates.get(processedclass)).values(); Iterator itfses = fses.iterator(); while (itfses.hasNext()) { FlagState fs = (FlagState)itfses.next(); @@ -182,7 +158,7 @@ public class SafetyAnalysis { cdhashtable.put(fs, availabletasks); } - safeexecution.put(cdtemp, cdhashtable); + safeexecution.put(processedclass, cdhashtable); } @@ -228,7 +204,35 @@ public class SafetyAnalysis { System.out.println("\t\t------------"); } } + + System.out.println("\n\n\n\tMyoptionals contains : "); + for(Iterator myoit = myoptionals.get(cdtemp).iterator(); myoit.hasNext();){ + MyOptional mm = (MyOptional)myoit.next(); + System.out.println("\t\tTASK "+mm.td.getSymbol()+"\n"); + System.out.println("\t\tDepth : "+mm.depth); + System.out.println("\t\twith flags :"); + for(Iterator myfses = mm.flagstates.iterator(); myfses.hasNext();){ + System.out.println("\t\t\t"+((FlagState)myfses.next()).getTextLabel()); + } + System.out.println("\t\tand exitflags :"); + for(Iterator fseshash = mm.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 = mm.predicate; + System.out.println("\t\tPredicate constains :"); + for(Iterator varit = predicate.vardescriptors.iterator(); varit.hasNext();){ + VarDescriptor vard = (VarDescriptor)varit.next(); + System.out.println("\t\t\tClass "+vard.getType().getClassDesc().getSymbol()); + } + System.out.println("\t\t------------"); + } } + + } /*Marks the executiongraph : @@ -249,7 +253,7 @@ public class SafetyAnalysis { extremity.mark(); //calls doGraphMarking recursively with the next nodes as params for( Iterator it = extremity.edges(); it.hasNext(); ){ - TEdge edge = (TEdge)it.next(); + EGEdge edge = (EGEdge)it.next(); doGraphMarking((EGTaskNode)edge.getTarget()); } } @@ -265,7 +269,7 @@ public class SafetyAnalysis { private void testIfOptional(EGTaskNode tn){ for(Iterator edges = tn.edges(); edges.hasNext();){ - TEdge edge = (TEdge)edges.next(); + EGEdge edge = (EGEdge)edges.next(); EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); if (nexttn.getTD()!=null) if(nexttn.getTD().isOptional(classname)) @@ -275,8 +279,9 @@ public class SafetyAnalysis { private void testIfMultiple(EGTaskNode tn){ for(Iterator edges = tn.edges(); edges.hasNext();){ - TEdge edge = (TEdge)edges.next(); + EGEdge edge = (EGEdge)edges.next(); EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); + if (nexttn.getTD() == null ) return;//to be fixed if( nexttn.getTD().numParameters() > 1 ){ nexttn.setMultipleParams(); } @@ -286,7 +291,7 @@ public class SafetyAnalysis { //maybe a little bug to fix private void testIfRuntime(EGTaskNode tn){ for(Iterator edges = tn.edges(); edges.hasNext();){ - TEdge edge = (TEdge)edges.next(); + EGEdge edge = (EGEdge)edges.next(); EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); if( ((String)nexttn.getName()).compareTo("Runtime") == 0 ) nexttn.setAND(); @@ -303,7 +308,7 @@ public class SafetyAnalysis { Vector vtemp = new Vector(); Vector tomark = new Vector(); for(Iterator edges = tn.edges(); edges.hasNext();){ - TEdge edge = (TEdge)edges.next(); + EGEdge edge = (EGEdge)edges.next(); EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); int contains = 0; for (Iterator it = vtemp.iterator(); it.hasNext();){ @@ -324,7 +329,7 @@ public class SafetyAnalysis { //maybe little bug to fix private void testIfNextIsSelfLoop(EGTaskNode tn){ for(Iterator edges = tn.edges(); edges.hasNext();){ - TEdge edge = (TEdge)edges.next(); + EGEdge edge = (EGEdge)edges.next(); EGTaskNode nexttn = (EGTaskNode)edge.getTarget(); if(nexttn.isSelfLoop()) nexttn.setAND(); } @@ -357,7 +362,8 @@ public class SafetyAnalysis { if( !((Iterator)tn.edges()).hasNext() || tn.isSelfLoop()){ HashSet fstemp = new HashSet(); fstemp.add(tn.getFS()); - MyOptional mo = new MyOptional(tn.getTD(), fstemp, depth, temppredicate); + MyOptional mo = new MyOptional(tn.getTD(), fstemp, depth, temppredicate); + myoptionals.get(processedclass).add(mo); temp.add(mo); return temp; } @@ -372,6 +378,7 @@ public class SafetyAnalysis { HashSet fstemp = new HashSet(); fstemp.add(tn.getFS()); MyOptional mo = new MyOptional(tn.getTD(), fstemp, depth, temppredicate); + myoptionals.get(processedclass).add(mo); temp = computeEdges(tn, newdepth, newhashset, temppredicate); temp.add(mo); return temp; @@ -477,6 +484,7 @@ public class SafetyAnalysis { /*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; @@ -517,7 +525,7 @@ public class SafetyAnalysis { Hashtable andlist = new Hashtable(); Vector orlist = new Vector(); for(Iterator edges = tn.edges(); edges.hasNext();){ - EGTaskNode tntemp = (EGTaskNode)((TEdge)edges.next()).getTarget(); + EGTaskNode tntemp = (EGTaskNode)((EGEdge)edges.next()).getTarget(); if(tntemp.type() == OR) orlist.add(tntemp); else if(tntemp.type() == AND){ if(andlist.containsKey(tntemp.getName())){ @@ -664,7 +672,7 @@ public class SafetyAnalysis { return A; } - private void removeDoubles( HashSet A ){ + /*private void removeDoubles( HashSet A ){ //remove duplicated MyOptionals (might happend in few cases) Vector toremove = new Vector(); int i = 0; @@ -678,7 +686,7 @@ public class SafetyAnalysis { for(Iterator itA3 = itA2; itA3.hasNext();){ MyOptional myA2 = (MyOptional)itA3.next(); if(myA2.equal(myA)){ - myA.depth = (myA.depth < myA2.depth) ? myA.depth : myA2.depth; + //myA.depth = (myA.depth < myA2.depth) ? myA.depth : myA2.depth; toremove.add(myA2); System.out.println("removed!"); } @@ -686,7 +694,7 @@ public class SafetyAnalysis { } for( Iterator it = toremove.iterator(); it.hasNext();) A.remove(it.next()); - } + }*/ private HashSet createIntersection( HashSet A, HashSet B){ HashSet result = new HashSet(); @@ -713,7 +721,10 @@ public class SafetyAnalysis { for(Iterator varit = B.vardescriptors.iterator(); varit.hasNext();){ VarDescriptor vd = (VarDescriptor)varit.next(); if(result.vardescriptors.contains(vd))System.out.println("Already in "); - else result.vardescriptors.add(vd); + else { + System.out.println("Not already in..."); + result.vardescriptors.add(vd); + } } for(Iterator varit = result.vardescriptors.iterator(); varit.hasNext();){ VarDescriptor vd = (VarDescriptor)varit.next(); diff --git a/Robust/src/IR/Flat/BuildCode.java b/Robust/src/IR/Flat/BuildCode.java index a78754f0..05e360a1 100644 --- a/Robust/src/IR/Flat/BuildCode.java +++ b/Robust/src/IR/Flat/BuildCode.java @@ -7,6 +7,8 @@ import IR.*; import java.util.*; import java.io.*; import Util.Relation; +import Analysis.TaskStateAnalysis.FlagState; +import Analysis.TaskStateAnalysis.MyOptional; public class BuildCode { State state; @@ -26,7 +28,7 @@ public class BuildCode { private int maxtaskparams=0; ClassDescriptor[] cdarray; TypeDescriptor[] arraytable; - + public BuildCode(State st, Hashtable temptovar, TypeUtil typeutil) { state=st; this.temptovar=temptovar; @@ -324,6 +326,11 @@ public class BuildCode { if (state.TASK) outstructs.println("#define MAXTASKPARAMS "+maxtaskparams); + if (state.TASK&&state.OPTIONAL){ + generateOptionalArrays(outoptionalarrays, state.getAnalysisResult(), state.getMyOptionals()); + outoptionalarrays.close(); + } + /* Output structure definitions for repair tool */ if (state.structfile!=null) { @@ -334,11 +341,8 @@ public class BuildCode { outstructs.close(); outmethod.close(); + - if (state.TASK&&state.OPTIONAL) { - generateOptionalArrays(outoptionalarrays); - outoptionalarrays.close(); - } } private int maxcount=0; @@ -1596,9 +1600,9 @@ public class BuildCode { } } - void generateOptionalArrays(PrintWriter output) { + void generateOptionalArrays(PrintWriter output, Hashtable> safeexecution, Hashtable myoptionals) { - SymbolTable classes = state.getClassSymbolTable(); + /* SymbolTable classes = state.getClassSymbolTable(); for( Iterator it = classes.getAllDescriptorsIterator(); it.hasNext();){ ClassDescriptor cd = (ClassDescriptor)it.next(); output.println("Class "+cd.getSymbol()); @@ -1608,10 +1612,83 @@ public class BuildCode { int flagid=1<<((Integer)flags.get(fd)).intValue(); output.println("\tFlag associated with "+fd.getSymbol()+" : 0x"+Integer.toHexString(flagid)+" bx"+Integer.toBinaryString(flagid)); } - } + }*/ + + + int fscounter = 0; + int myocounter = 0; + int classescounter = 0; + Enumeration e = safeexecution.keys(); + while (e.hasMoreElements()) { + //get the class + ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement(); + for(Iterator myoit = ((HashSet)myoptionals.get(cdtemp)).iterator(); myoit.hasNext();){ + MyOptional myo = (MyOptional)myoit.next(); + output.println("struct myoptional myoptional_"+"/*ID to determine*/"+"_"+"cdtemp.getsafeSymbol()"+"={"); + //insert code to generate the myoptional + output.println("};"); + } + classescounter++; + Hashtable hashtbtemp = safeexecution.get(cdtemp); + Enumeration fses = hashtbtemp.keys(); + while(fses.hasMoreElements()){ + //get all the possible falgstates reachable by an object + FlagState fs = (FlagState)fses.nextElement(); + fscounter++; + //get the set of MyOptionnals + HashSet availabletasks = (HashSet)hashtbtemp.get(fs); + //iterate through the MyOptionals + for(Iterator mos = availabletasks.iterator(); mos.hasNext();){ + MyOptional mm = (MyOptional)mos.next(); + myocounter++; + } + output.println("struct myoptional * myoptionals_FS"+fscounter+"_"+cdtemp.getSafeSymbol()+"[] = {"); + for(int i=0; i