From c7c4035c3310d3306b101f9869e0c3f52638945e Mon Sep 17 00:00:00 2001 From: wmontaz Date: Tue, 17 Jul 2007 21:02:55 +0000 Subject: [PATCH] Changes for William's Analysis --- .../TaskStateAnalysis/EGTaskNode.java | 142 ++++ .../TaskStateAnalysis/ExecutionGraph.java | 336 +++++++++ .../Analysis/TaskStateAnalysis/FlagState.java | 20 +- .../TaskStateAnalysis/SafetyAnalysis.java | 644 ++++++++++++++++++ .../src/Analysis/TaskStateAnalysis/TEdge.java | 4 - .../TaskStateAnalysis/TaskAnalysis.java | 82 +-- .../Analysis/TaskStateAnalysis/TaskNode.java | 13 +- Robust/src/IR/State.java | 3 + Robust/src/IR/TaskDescriptor.java | 12 +- Robust/src/IR/Tree/BuildIR.java | 49 +- Robust/src/Lex/Keyword.java | 1 + Robust/src/Lex/Lexer.java | 4 +- Robust/src/Main/Main.java | 14 +- Robust/src/Parse/java14.cup | 7 + Robust/src/Util/Edge.java | 11 + Robust/src/Util/GraphNode.java | 38 +- 16 files changed, 1306 insertions(+), 74 deletions(-) create mode 100644 Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java create mode 100644 Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java create mode 100644 Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java diff --git a/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java b/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java new file mode 100644 index 00000000..64b04014 --- /dev/null +++ b/Robust/src/Analysis/TaskStateAnalysis/EGTaskNode.java @@ -0,0 +1,142 @@ +package Analysis.TaskStateAnalysis; +import Analysis.TaskStateAnalysis.*; +import IR.*; +import IR.Tree.*; +import IR.Flat.*; +import java.util.*; +import Util.GraphNode; + +public class EGTaskNode extends TaskNode { + private boolean source=false; + private int loopmarker=0; + private boolean multipleparams=false; + private boolean optional = false; + private boolean marked=false; + private boolean tomention=true; + private int type = 0; + private FlagState fs; + private TaskDescriptor td; + + public EGTaskNode(){ + super("default"); + this.fs = null; + this.td = null; + } + + public EGTaskNode(String name){ + super(name); + this.fs = null; + this.td = null; + } + + public EGTaskNode(String name, FlagState fs){ + super(name); + this.fs = fs; + this.td = null; + } + + public EGTaskNode(String name, TaskDescriptor td){ + super(name); + this.fs = null; + this.td = td; + } + + public EGTaskNode(String name, FlagState fs, TaskDescriptor td){ + super(name); + this.fs = fs; + this.td = td; + } + + public TaskDescriptor getTD(){ + return td; + } + + public void setSource(){ + source = true; + } + + public boolean isSource(){ + return source; + } + + public int getuid(){ + return uid; + } + + public void doSelfLoopMarking(){ + loopmarker=1; + } + + public void doLoopMarking(){ + loopmarker=2; + } + + public boolean isSelfLoop(){ + if (loopmarker==1) return true; + else return false; + } + + public boolean isLoop(){ + if (loopmarker==2) return true; + else return false; + } + + public void setMultipleParams(){ + multipleparams=true; + } + + public boolean isMultipleParams(){ + return multipleparams; + } + + public void setOptional(){ + optional = true; + } + + public boolean isOptional(){ + return optional; + } + + public void mark(){ + marked = true; + } + + public void unMark(){ + marked = false; + } + + public boolean isMarked(){ + return marked; + } + + public String getFSName(){ + if(fs == null) return "no flag"; + else return fs.getTextLabel(); + } + + public FlagState getFS(){ + return fs; + } + + public void dontMention(){ + tomention = false; + } + + public boolean toMention(){ + return tomention; + } + + public void setAND(){ + type = 1; + } + + public void setOR(){ + type = 0; + } + + public int type(){ + return type; + } + + +} diff --git a/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java b/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java new file mode 100644 index 00000000..d6fdb81b --- /dev/null +++ b/Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java @@ -0,0 +1,336 @@ +package Analysis.TaskStateAnalysis; +import java.util.*; +import IR.State; +import IR.SymbolTable; +import IR.ClassDescriptor; +import IR.TaskDescriptor; +import java.io.File; +import java.io.FileWriter; +import java.io.FileOutputStream; +import Util.Edge; + +public class ExecutionGraph { + + private TaskAnalysis taskanalysis; + private State state; + private TreeMap graphs; + private Hashtable executiongraph; + private SymbolTable tasks; + + public ExecutionGraph(State state, TaskAnalysis ta){ + this.taskanalysis=ta; + this.state=state; + this.tasks = this.state. getTaskSymbolTable(); + this.graphs=new TreeMap(); + this.executiongraph = new Hashtable(); + } + + public Hashtable getExecutionGraph(){ + return executiongraph; + } + + public void createExecutionGraph() throws java.io.IOException { + /** Explore the analysis structure "OPTIONAL ARGS" PROJECT**/ + + Enumeration e=taskanalysis.flagstates.keys(); + + while (e.hasMoreElements()) { + System.out.println("\nInto class :"); + ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement(); + System.out.println("\t"+(cdtemp.getSymbol())+ "\n"); + exploreGraph(cdtemp); + test(); + adapt(cdtemp); + } + printDOTFile(); + + } + + private void exploreGraph(ClassDescriptor cd) { + + LinkedList fifo = new LinkedList(); + Vector sourceNodeList = new Vector(); + Enumeration e; + graphs.clear(); + int l=0; + + /* Search for starting nodes */ + Collection nodes = ((Hashtable)taskanalysis.flagstates.get(cd)).values(); + Iterator it = nodes.iterator(); + while (it.hasNext()) { + FlagState fs = (FlagState)it.next(); + if(fs.isSourceNode()){ + sourceNodeList.addElement(fs); + } + } + + /* Perform the Breadth first search algorithm and build ExecutionGraph */ + FlagState fstemp, fstemp2; + + Iterator sourceit = sourceNodeList.iterator(); + while( sourceit.hasNext() ){ + createLevel(l); + FlagState fs = (FlagState)sourceit.next(); + + fs.doMarking(); + fifo.addLast(fs); + + + int i=0; + while ( !fifo.isEmpty() ){ + + fstemp = (FlagState)fifo.getFirst(); + fifo.removeFirst(); + + System.out.println("IN FS : "+fstemp.getTextLabel()); + + Iterator edges = fstemp.edges(); + if (edges.hasNext()){ + + createNode(fstemp, l); + + while(edges.hasNext()){ + + FEdge edge = (FEdge)edges.next(); + fstemp2 = (FlagState)edge.getTarget(); + + if ( !fstemp2.isMarked() ) { + fstemp2.doMarking(); + fifo.addLast(fstemp2); + } + } + + + if (!isFinished(fstemp, l)){ + fifo.addLast(fstemp); + } + } + + } + + Hashtable temphash = new Hashtable(); + temphash = clean((Hashtable)graphs.get(l)); + graphs.put(l, temphash); + l++; + } + } + + private void createLevel(int level){ + if (!graphs.containsKey(level)){ + Hashtable ht = new Hashtable(); + graphs.put(level, ht); + } + } + + private void createNode(FlagState fs, int level){ + Enumeration allocatingtasks; + EGTaskNode tn; + EGTaskNode target; + FEdge edge; + + if (fs.isSourceNode()){ + + for (Iterator inedges = ((Vector)fs.getAllocatingTasks()).iterator(); inedges.hasNext();){ + String tname = new String(((TaskDescriptor)inedges.next()).getSymbol()); + String key1 = new String(fs.getTextLabel()+tname); + if (((Hashtable)graphs.get(level)).containsKey(key1)){ + tn = (EGTaskNode)((Hashtable)graphs.get(level)).get(key1); + } + else{ + tn = new EGTaskNode(tname,(TaskDescriptor)tasks.get(tname)); + tn.setSource(); + } + for (Iterator edges = fs.edges(); edges.hasNext();){ + edge = (FEdge)edges.next(); + // if(!edge.isProcessed()){ + target=new EGTaskNode(edge.getLabel(), fs, (TaskDescriptor)tasks.get(edge.getLabel())); + String key2 = new String(((FlagState)edge.getTarget()).getTextLabel()+target.getName()+((FlagState)edge.getSource()).getTextLabel()); + if (((FlagState)edge.getTarget()).isMarked()){ + target.doSelfLoopMarking(); + } + if (((Hashtable)graphs.get(level)).containsKey(key2)){ + target = (EGTaskNode)((Hashtable)graphs.get(level)).get(key2); + TEdge newedge=new TEdge(target); + tn.addEdge(newedge); + } + else { + TEdge newedge=new TEdge(target); + tn.addEdge(newedge); + } + ((Hashtable)graphs.get(level)).put(key2, target); + // } + } + ((Hashtable)graphs.get(level)).put(key1, tn); + } + } + + for (Iterator inedges = fs.inedges(); inedges.hasNext();){ + + FEdge in=(FEdge)inedges.next(); + String key1 = new String(fs.getTextLabel()+in.getLabel()+((FlagState)in.getSource()).getTextLabel()); + if (!in.isProcessed()){ + tn = (EGTaskNode)((Hashtable)graphs.get(level)).get(key1); + if (tn != null){ + for (Iterator edges = fs.edges(); edges.hasNext();){ + edge = (FEdge)edges.next(); + target=new EGTaskNode(edge.getLabel(), fs, (TaskDescriptor)tasks.get(edge.getLabel())); + String key2 = new String(((FlagState)edge.getTarget()).getTextLabel()+target.getName()+((FlagState)edge.getSource()).getTextLabel()); + if (((String)((FlagState)edge.getTarget()).getTextLabel()).compareTo(fs.getTextLabel())==0){ + target.doSelfLoopMarking(); + } + if (((Hashtable)graphs.get(level)).containsKey(key2)){ + target = (EGTaskNode)((Hashtable)graphs.get(level)).get(key2); + TEdge newedge=new TEdge(target); + tn.addEdge(newedge); + } + else { + TEdge newedge=new TEdge(target); + tn.addEdge(newedge); + } + ((Hashtable)graphs.get(level)).put(key2, target); + } + ((Hashtable)graphs.get(level)).put(key1, tn); + in.setProcessed(); + } + } + } + + } + + private void adapt(ClassDescriptor cd) { + Vector tasknodes = new Vector(); + + Collection c1 = graphs.values(); + for (Iterator it1 = c1.iterator(); it1.hasNext();){ + Collection tempc=((Hashtable)it1.next()).values(); + for(Iterator it2 = tempc.iterator(); it2.hasNext();){ + EGTaskNode tn = (EGTaskNode)it2.next(); + if(tn.getName().compareTo("Runtime")!=0){ + TaskDescriptor td = tn.getTD(); + System.out.println("Trying to get : " + tn.getName()); + if(td.numParameters()>1) tn.setMultipleParams(); + } + } + tasknodes.addAll(tempc); + } + executiongraph.put(cd,tasknodes); + } + + private void test() { + int i = 0; + Collection c1 = graphs.values(); + for (Iterator it1 = c1.iterator(); it1.hasNext();){ + Hashtable ht = ((Hashtable)it1.next()); + System.out.println("\nLevel " + i++ + " contains :"); + Collection c2 = ht.values(); + for ( Iterator it2 = c2.iterator(); it2.hasNext();){ + EGTaskNode tn = (EGTaskNode)it2.next(); + System.out.println(tn.getTextLabel()+" ID "+tn.getLabel()+" FS "+tn.getFSName()); + } + } + } + + private void printDOTFile()throws java.io.IOException { + Enumeration e = executiongraph.keys(); + while (e.hasMoreElements()){ + createDOTFile((ClassDescriptor)e.nextElement()); + } + } + + private void createDOTFile(ClassDescriptor cd) throws java.io.IOException { + Vector v = (Vector)executiongraph.get(cd); + java.io.PrintWriter output; + File dotfile_flagstates= new File("execution"+cd.getSymbol()+".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, Vector v) { + EGTaskNode tn; + + for(Iterator it1 = v.iterator(); it1.hasNext();){ + tn = (EGTaskNode)it1.next(); + output.println("\t"+tn.getLabel()+" [label=\""+tn.getTextLabel()+"\""); + if (tn.isSelfLoop()) output.println(", shape=box"); + if (tn.isMultipleParams()) output.println(", color=blue"); + output.println("];"); + + + for(Iterator it2 = tn.edges();it2.hasNext();){ + output.println("\t"+tn.getLabel()+" -> "+((EGTaskNode)((TEdge)it2.next()).getTarget()).getLabel()+";"); + } + } + } + + 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; + } + + 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; + } + + private boolean isFinished(FlagState fs, int level){ + + boolean result = true; + for (Iterator inedges = fs.inedges(); inedges.hasNext();){ + + FEdge in=(FEdge)inedges.next(); + + if (!in.isProcessed()){ + String key1 = new String(fs.getTextLabel()+in.getLabel()+((FlagState)in.getSource()).getTextLabel()); + + if (((Hashtable)graphs.get(level)).get(key1)==null){ + if (((String)((FlagState)in.getSource()).getTextLabel()).compareTo(fs.getTextLabel())!=0){ + result = false; + } + } + + } + } + return result; + } + + +} + + + + + + + + + + + + + diff --git a/Robust/src/Analysis/TaskStateAnalysis/FlagState.java b/Robust/src/Analysis/TaskStateAnalysis/FlagState.java index 7a83da44..6e122435 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/FlagState.java +++ b/Robust/src/Analysis/TaskStateAnalysis/FlagState.java @@ -23,6 +23,8 @@ public class FlagState extends GraphNode { private final Hashtable tags; private boolean issourcenode; private Vector tasks; + + private boolean marked=false; /** Class constructor @@ -51,7 +53,23 @@ public class FlagState extends GraphNode { this.issourcenode=false; } - + + public int getuid() { + return uid; + } + + public boolean isMarked() { + return marked; + } + + public void doUnmarking() { + marked = false; + } + + public void doMarking() { + marked = true; + } + /** Accessor method * @param fd FlagDescriptor * @return true if the flagstate contains fd else false. diff --git a/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java b/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java new file mode 100644 index 00000000..ccee31dc --- /dev/null +++ b/Robust/src/Analysis/TaskStateAnalysis/SafetyAnalysis.java @@ -0,0 +1,644 @@ +package Analysis.TaskStateAnalysis; +import java.util.*; +import IR.*; +import IR.Flat.*; +import java.io.*; +import java.io.File; +import java.io.FileWriter; +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 State state; + + public class MyOptional{ + public TaskDescriptor td; + public HashSet flagstates; + + protected MyOptional(TaskDescriptor td, HashSet flagstates){ + this.td = td; + this.flagstates = flagstates; + } + + public boolean equal(MyOptional myo){ + if (this.td.getSymbol().compareTo(myo.td.getSymbol())==0) + if(this.flagstates.equals(myo.flagstates)) + return true; + return false; + } + } + + public SafetyAnalysis(Hashtable executiongraph, State state){ + this.executiongraph = executiongraph; + this.safeexecution = new TreeMap(); + this.reducedgraph = new Hashtable(); + this.state = state; + } + + public void unMark(Vector nodes){ + for(Iterator it = nodes.iterator(); it.hasNext();){ + EGTaskNode tn = (EGTaskNode)it.next(); + tn.unMark(); + } + } + + 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); + } + } + + 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); + } + ////// + } + + 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); + + + } + + 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; + } + + 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; + + } + + + 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(); + } + } + } + + 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(); + } + } + + 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); + } + + 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(); + + if (classname.compareTo(cd.getSymbol())==0) + return (Vector)executiongraph.get(cd); + } + return null; + } + + 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; + } + else{ + tn.mark(); + return computeEdges(tn, nodetags); + } + } + } + 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); + } + } + } + + 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; + } + 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); + } + return temp; + } + + } + + 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()); + } + } + } + } + // 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; + } + + 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 "+tn2.getLabel()+";"); + } + } + } + + //////////////////// + + private HashSet resultingFS(MyOptional mo, ClassDescriptor cd){ + return resultingFS(mo, cd.getSymbol()); + } + + private HashSet resultingFS(MyOptional mo, String classname){ + Stack stack = new Stack(); + HashSet result = new HashSet(); + FlatMethod fm = state.getMethodFlat((TaskDescriptor)mo.td); + 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) { + //*** + System.out.println("TASKEXIT"); + //*** + HashSet tempset = new HashSet(); + for(Iterator it_fs = mo.flagstates.iterator(); it_fs.hasNext();){ + FlagState fstemp = (FlagState)it_fs.next(); + 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){ + fstemp=fstemp.setFlag(tfp.getFlag(),ffan.getFlagChange(tfp)); + } + } + System.out.println("new flag : "+fstemp.getTextLabel()); + tempset.add(fstemp); + } + 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); + } + + /* Queue other nodes past this one */ + for(int i=0;i evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){ - FlagState fstemp=fs; - //FlagState[] fstemparray=new FlagState[3]; - Vector inprocess=new Vector(); - Vector processed=new Vector(); - - for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) { - TempFlagPair tfp=(TempFlagPair)it_tfp.next(); - if (temp==tfp.getTemp()) - fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp)); - } - - inprocess.add(fstemp); - processed.add(fstemp); - - for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) { - TempTagPair ttp=(TempTagPair)it_ttp.next(); - - if (temp==ttp.getTemp()){ - processed=new Vector(); - for (Enumeration en=inprocess.elements();en.hasMoreElements();){ - FlagState fsworking=(FlagState)en.nextElement(); - if (((FlatFlagActionNode)nn).getTagChange(ttp)){ - fsworking=fsworking.setTag(ttp.getTag()); - processed.add(fsworking); - } - else - { - processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag()))); - } - } - inprocess=processed; - } - } - return processed; + private Vector evalTaskExitNode(FlatNode nn,ClassDescriptor cd,FlagState fs, TempDescriptor temp){ + FlagState fstemp=fs; + //FlagState[] fstemparray=new FlagState[3]; + Vector inprocess=new Vector(); + Vector processed=new Vector(); + + for(Iterator it_tfp=((FlatFlagActionNode)nn).getTempFlagPairs();it_tfp.hasNext();) { + TempFlagPair tfp=(TempFlagPair)it_tfp.next(); + if (temp==tfp.getTemp()) + fstemp=fstemp.setFlag(tfp.getFlag(),((FlatFlagActionNode)nn).getFlagChange(tfp)); + } + + inprocess.add(fstemp); + processed.add(fstemp); -} + for(Iterator it_ttp=((FlatFlagActionNode)nn).getTempTagPairs();it_ttp.hasNext();) { + TempTagPair ttp=(TempTagPair)it_ttp.next(); + if (temp==ttp.getTemp()){ + processed=new Vector(); + for (Enumeration en=inprocess.elements();en.hasMoreElements();){ + FlagState fsworking=(FlagState)en.nextElement(); + if (((FlatFlagActionNode)nn).getTagChange(ttp)){ + fsworking=fsworking.setTag(ttp.getTag()); + processed.add(fsworking); + } + else + { + processed.addAll(Arrays.asList(fsworking.clearTag(ttp.getTag()))); + } + } + inprocess=processed; + } + } + return processed; + + } + private FlagState canonicalizeFlagState(Hashtable sourcenodes, FlagState fs){ if (sourcenodes.containsKey(fs)) @@ -433,7 +438,7 @@ private FlagState evalNewObjNode(FlatNode nn){ FlagState.DOTVisitor.visit(dotstream,((Hashtable)flagstates.get(cd)).values()); } - + /** Returns the flag states for the class descriptor. */ public Set getFlagStates(ClassDescriptor cd) { if (flagstates.containsKey(cd)) @@ -483,6 +488,7 @@ private FlagState evalNewObjNode(FlatNode nn){ return (Vector)cdtorootnodes.get(cd); } - + + } diff --git a/Robust/src/Analysis/TaskStateAnalysis/TaskNode.java b/Robust/src/Analysis/TaskStateAnalysis/TaskNode.java index 64c14a01..7ee1c36f 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/TaskNode.java +++ b/Robust/src/Analysis/TaskStateAnalysis/TaskNode.java @@ -10,9 +10,10 @@ import Util.GraphNode; public class TaskNode extends GraphNode { private final String name; - private int uid; + protected int uid; private static int nodeid=0; - + // private int loopmarker=0; + //private boolean multipleparams=false; /**Class Constructor * Creates a new TaskNode using the TaskDescriptor. * @param tasknode TaskDescriptor @@ -36,6 +37,11 @@ public class TaskNode extends GraphNode { public String getName(){ return name; } + + // public int getuid(){ + //return uid; + //} + /**toString method. * @return string representation of the tasknode (e.g "Task foo") @@ -56,14 +62,13 @@ public class TaskNode extends GraphNode { } return false; } - + public boolean edgeExists(TEdge newedge){ if(edges.isEmpty()) return false; else return edges.contains(newedge); } - } diff --git a/Robust/src/IR/State.java b/Robust/src/IR/State.java index eadd05f2..8d399600 100644 --- a/Robust/src/IR/State.java +++ b/Robust/src/IR/State.java @@ -25,6 +25,9 @@ public class State { public boolean WEBINTERFACE; public boolean TASK; public boolean TASKSTATE=false; + + public boolean OPTIONAL=false; + public boolean THREAD=false; public boolean INSTRUCTIONFAILURE=false; public String structfile; diff --git a/Robust/src/IR/TaskDescriptor.java b/Robust/src/IR/TaskDescriptor.java index 1fa23b89..6640963b 100644 --- a/Robust/src/IR/TaskDescriptor.java +++ b/Robust/src/IR/TaskDescriptor.java @@ -4,6 +4,7 @@ import IR.Tree.TagExpressionList; import IR.Tree.FlagEffects; import java.util.Vector; import java.util.Hashtable; +import java.util.Iterator; import IR.Tree.Modifiers; /** @@ -18,6 +19,7 @@ public class TaskDescriptor extends Descriptor { protected Vector vfe; protected String identifier; protected Vector params; + protected Vector optionals; protected SymbolTable paramtable; public TaskDescriptor(String identifier) { @@ -27,6 +29,7 @@ public class TaskDescriptor extends Descriptor { flagstable=new Hashtable(); tagstable=new Hashtable(); //BUGFIX - added initialization here params=new Vector(); + optionals = new Vector(); paramtable=new SymbolTable(); } @@ -42,11 +45,12 @@ public class TaskDescriptor extends Descriptor { return paramtable; } - public void addParameter(TypeDescriptor type, String paramname, FlagExpressionNode fen, TagExpressionList tel) { + public void addParameter(TypeDescriptor type, String paramname, FlagExpressionNode fen, TagExpressionList tel, boolean isoptional) { if (paramname.equals("this")) throw new Error("Can't have parameter named this"); VarDescriptor vd=new VarDescriptor(type, paramname); params.add(vd); + if (isoptional) optionals.add(vd); if (fen!=null) flagstable.put(vd, fen); if (tel!=null) {//BUGFIX - added null check here...test with any bristlecone program @@ -66,6 +70,12 @@ public class TaskDescriptor extends Descriptor { paramtable.add(vd); } + public boolean isOptional(String classname){ + for (Iterator it = optionals.iterator(); it.hasNext();) + if( ((VarDescriptor)it.next()).getType().getSymbol().compareTo(classname)==0) return true; + return false; + } + public int numParameters() { return params.size(); } diff --git a/Robust/src/IR/Tree/BuildIR.java b/Robust/src/IR/Tree/BuildIR.java index 4f8a0aa6..6fa0cd6e 100644 --- a/Robust/src/IR/Tree/BuildIR.java +++ b/Robust/src/IR/Tree/BuildIR.java @@ -167,30 +167,41 @@ public class BuildIR { } public void parseParameterList(TaskDescriptor td, ParseNode pn) { + + boolean optional; ParseNode paramlist=pn.getChild("task_parameter_list"); if (paramlist==null) return; - ParseNodeVector pnv=paramlist.getChildren(); - for(int i=0;i