From e9da255c320555b361ced41c41add845b020afe0 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Tue, 17 Apr 2007 21:48:57 +0000 Subject: [PATCH] clean up interfaces --- .../src/Analysis/TaskStateAnalysis/Edge.java | 55 +- .../Analysis/TaskStateAnalysis/FlagState.java | 500 +++++++++++++++--- .../TaskStateAnalysis/TriggerState.java | 42 -- 3 files changed, 478 insertions(+), 119 deletions(-) delete mode 100644 Robust/src/Analysis/TaskStateAnalysis/TriggerState.java diff --git a/Robust/src/Analysis/TaskStateAnalysis/Edge.java b/Robust/src/Analysis/TaskStateAnalysis/Edge.java index e9d03e9d..2cb1bdb5 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/Edge.java +++ b/Robust/src/Analysis/TaskStateAnalysis/Edge.java @@ -5,26 +5,45 @@ import IR.Tree.*; import IR.Flat.*; import java.util.*; -public class Edge -{ - FlagState fs; - String name; - public Edge(FlagState fs, String name) - { - this.fs=fs; - this.name=name; - } +/* Edge *****************/ - public FlagState getState() - { - return fs; - } +public static class Edge { - public String getName() - { - return name; + private String label; + private FlagState target; + private FlagState source; + private String dotnodeparams = new String(); + + public Edge(FlagState target, String label) { + this.label = label; + this.target = target; + } + + public String getLabel() { + return label; + } + + public void setSource(FlagState s) { + this.source=s; + } + + public FlagState getSource() { + return source; + } + + public FlagState getTarget() { + return target; + } + + public void setDotNodeParameters(String param) { + if (param == null) { + throw new NullPointerException(); } - + if (param.length() > 0) { + dotnodeparams = "," + param; + } else { + dotnodeparams = new String(); + } + } } - diff --git a/Robust/src/Analysis/TaskStateAnalysis/FlagState.java b/Robust/src/Analysis/TaskStateAnalysis/FlagState.java index 007ab7e7..3de49a19 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/FlagState.java +++ b/Robust/src/Analysis/TaskStateAnalysis/FlagState.java @@ -4,96 +4,478 @@ import IR.*; import IR.Tree.*; import IR.Flat.*; import java.util.*; +import java.io.*; public class FlagState { - Hashtable flagstate; - ClassDescriptor cd; + /* NodeStatus enumeration pattern ***********/ - public FlagState(FlagDescriptor[] flags, ClassDescriptor cd) { - flagstate=new Hashtable(flags.length); - this.cd=cd; - for (int i=0; i < flags.length; i++) { - flagstate.put(flags[i],new Boolean(false)); - } + public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED"); + public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING"); + public static final NodeStatus FINISHED = new NodeStatus("FINISHED"); + + public static class NodeStatus { + private static String name; + private NodeStatus(String name) { this.name = name; } + public String toString() { return name; } } - - public FlagState(Hashtable flagstate, ClassDescriptor cd) { - this.flagstate = new Hashtable(flagstate); - this.cd=cd; + + + int discoverytime = -1; + int finishingtime = -1; /* used for searches */ + + Vector edges = new Vector(); + Vector inedges = new Vector(); + NodeStatus status = UNVISITED; + String dotnodeparams = new String(); + boolean merge=false; + String nodeoption=""; + + private final HashSet flagstate; + private final ClassDescriptor cd; + + public void setOption(String option) { + this.nodeoption=","+option; } - public Hashtable getStateTable() { - return flagstate; + public void setMerge() { + merge=true; } - public void put(FlagDescriptor fd, Boolean status) { - flagstate.put(fd,status); + public FlagState(HashSet flagstate, ClassDescriptor cd) { + this.flagstate=flagstate; + this.cd=cd; } public boolean get(FlagDescriptor fd) { - if (! flagstate.containsKey(fd)) - return false; + return flagstate.contains(fd); + } + + public String toString() { + return cd.toString()+getTextLabel(); + } + + public Iterator getFlags() { + return flagstate.iterator(); + } + + public FlagState setFlag(FlagDescriptor fd, boolean status) { + HashSet newset=(HashSet) flagstate.clone(); + if (status) + newset.add(fd); else - return ((Boolean)(flagstate.get(fd))).booleanValue(); + newset.remove(fd); + return new FlagState(newset, cd); } - public String toString() { - StringBuffer sb = new StringBuffer(flagstate.size()); - Enumeration e = flagstate.keys(); - - while (e.hasMoreElements()) { - if (((Boolean)(flagstate.get((FlagDescriptor)e.nextElement()))).booleanValue()) - sb.append(1); + public boolean equals(Object o) { + if (o instanceof FlagState) { + FlagState fs=(FlagState)o; + if (fs.cd!=cd) + return false; + return fs.flagstate.equals(flagstate); + } + return false; + } + + public int hashCode() { + return cd.hashCode()^flagstate.hashCode(); + } + + public static void computeclosure(Collection nodes, Collection removed) { + Stack tovisit=new Stack(); + tovisit.addAll(nodes); + while(!tovisit.isEmpty()) { + FlagState gn=(FlagState)tovisit.pop(); + for(Iterator it=gn.edges();it.hasNext();) { + Edge edge=(Edge)it.next(); + FlagState target=edge.getTarget(); + if (!nodes.contains(target)) { + if ((removed==null)|| + (!removed.contains(target))) { + nodes.add(target); + tovisit.push(target); + } + } + } + } + } + + public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) { + Stack tovisit=new Stack(); + Stack newvisit=new Stack(); + tovisit.addAll(nodes); + for(int i=0;i 0) { + dotnodeparams = "," + param; + } else { + dotnodeparams = new String(); + } + } + + public void setStatus(NodeStatus status) { + if (status == null) { + throw new NullPointerException(); + } + this.status = status; + } + + public String getLabel() { + return getTextLabel(); + } + + public String getTextLabel() { + String label=null; + for(Iterator it=getFlags();it.hasNext();) { + FlagState fs=(FlagState) it.next(); + if (label==null) + label=fs.toString(); else - sb.append(0); + label+=", "+fs.toString(); } - return new String(sb); + return label; + } + + public NodeStatus getStatus() { + return this.status; + } + + public Iterator edges() { + return edges.iterator(); } - public String toString(FlagDescriptor[] flags) { - StringBuffer sb = new StringBuffer(flagstate.size()); - Enumeration e; + public Iterator inedges() { + return inedges.iterator(); + } + + public void addEdge(Edge newedge) { + newedge.setSource(this); + edges.addElement(newedge); + FlagState tonode=newedge.getTarget(); + tonode.inedges.addElement(newedge); + } - for(int i=0;i < flags.length; i++) { - e = flagstate.keys(); + void reset() { + discoverytime = -1; + finishingtime = -1; + status = UNVISITED; + } + + void resetscc() { + status = UNVISITED; + } - while (e.hasMoreElements()) { - FlagDescriptor fdtemp=(FlagDescriptor)e.nextElement(); - if( flags[i] == fdtemp) { - if (((Boolean)(flagstate.get(fdtemp))).booleanValue()) - sb.append(1); - else - sb.append(0); + void discover(int time) { + discoverytime = time; + status = PROCESSING; + } + + void finish(int time) { + assert status == PROCESSING; + finishingtime = time; + status = FINISHED; + } + + /** Returns finishing time for dfs */ + + public int getFinishingTime() { + return finishingtime; + } + + + public static class DOTVisitor { + + java.io.PrintWriter output; + int tokennumber; + int color; + + private DOTVisitor(java.io.OutputStream output) { + tokennumber = 0; + color = 0; + this.output = new java.io.PrintWriter(output, true); + } + + private String getNewID(String name) { + tokennumber = tokennumber + 1; + return new String (name+tokennumber); + } + + Collection nodes; + Collection special; + + public static void visit(java.io.OutputStream output, Collection nodes) { + visit(output,nodes,null); + } + + public static void visit(java.io.OutputStream output, Collection nodes, Collection special) { + DOTVisitor visitor = new DOTVisitor(output); + visitor.special=special; + visitor.nodes = nodes; + visitor.make(); + } + + private void make() { + output.println("digraph dotvisitor {"); + output.println("\trotate=90;"); + /* output.println("\tpage=\"8.5,11\";"); + output.println("\tnslimit=1000.0;"); + output.println("\tnslimit1=1000.0;"); + output.println("\tmclimit=1000.0;"); + output.println("\tremincross=true;");*/ + output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];"); + output.println("\tedge [fontsize=6];"); + traverse(); + output.println("}\n"); + } + + private void traverse() { + Set cycleset=FlagState.findcycles(nodes); + + Iterator i = nodes.iterator(); + while (i.hasNext()) { + FlagState gn = (FlagState) i.next(); + Iterator edges = gn.edges(); + String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];"; + String option=gn.nodeoption; + if (special!=null&&special.contains(gn)) + option+=",shape=box"; + if (!gn.merge) + output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];"); + + if (!gn.merge) + while (edges.hasNext()) { + Edge edge = (Edge) edges.next(); + FlagState node = edge.getTarget(); + if (nodes.contains(node)) { + for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) { + FlagState node2=(FlagState)nodeit.next(); + String edgelabel = Compiler.DEBUGGRAPH ? "label=\"" + edge.getLabel() + "\"" : "label=\"\""; + output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];"); + } + } + } + } + } + + Set nonmerge(FlagState gn) { + HashSet newset=new HashSet(); + HashSet toprocess=new HashSet(); + toprocess.add(gn); + while(!toprocess.isEmpty()) { + FlagState gn2=(FlagState)toprocess.iterator().next(); + toprocess.remove(gn2); + if (!gn2.merge) + newset.add(gn2); + else { + Iterator edges = gn2.edges(); + while (edges.hasNext()) { + Edge edge = (Edge) edges.next(); + FlagState node = edge.getTarget(); + if (!newset.contains(node)&&nodes.contains(node)) + toprocess.add(node); + } } } + return newset; } - return new String(sb); + } - public Enumeration getFlags() { - return flagstate.keys(); + /** This function returns the set of nodes involved in cycles. + * It only considers cycles containing nodes in the set 'nodes'. + */ + public static Set findcycles(Collection nodes) { + HashSet cycleset=new HashSet(); + SCC scc=DFS.computeSCC(nodes); + if (!scc.hasCycles()) + return cycleset; + for(int i=0;i1) + return true; + Object [] array=s.toArray(); + FlagState gn=(FlagState)array[0]; + for(Iterator it=gn.edges();it.hasNext();) { + Edge e=(Edge)it.next(); + if (e.getTarget()==gn) + return true; /* Self Cycle */ } - return true; + return false; } - return false; } - public int hashCode() { - return cd.hashCode()^flagstate.hashCode(); - } + /** + * DFS encapsulates the depth first search algorithm + */ + public static class DFS { + + int time = 0; + int sccindex = 0; + Collection nodes; + Vector finishingorder=null; + HashMap sccmap; + HashMap sccmaprev; + + private DFS(Collection nodes) { + this.nodes = nodes; + } + /** Calculates the strong connected components for the graph composed + * of the set of nodes 'nodes'*/ + public static SCC computeSCC(Collection nodes) { + if (nodes==null) { + throw new NullPointerException(); + } + DFS dfs=new DFS(nodes); + dfs.sccmap=new HashMap(); + dfs.sccmaprev=new HashMap(); + dfs.finishingorder=new Vector(); + boolean acyclic=dfs.go(); + for (Iterator it = nodes.iterator();it.hasNext();) { + FlagState gn = (FlagState) it.next(); + gn.resetscc(); + } + for(int i=dfs.finishingorder.size()-1;i>=0;i--) { + FlagState gn=(FlagState)dfs.finishingorder.get(i); + if (gn.getStatus() == UNVISITED) { + dfs.dfsprev(gn); + dfs.sccindex++; /* Increment scc index */ + } + } + return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex); + } + + void dfsprev(FlagState gn) { + if (gn.getStatus()==FINISHED||!nodes.contains(gn)) + return; + gn.setStatus(FINISHED); + Integer i=new Integer(sccindex); + if (!sccmap.containsKey(i)) + sccmap.put(i,new HashSet()); + ((Set)sccmap.get(i)).add(gn); + sccmaprev.put(gn,i); + for(Iterator edgeit=gn.inedges();edgeit.hasNext();) { + Edge e=(Edge)edgeit.next(); + FlagState gn2=e.getSource(); + dfsprev(gn2); + } + } + + public static boolean depthFirstSearch(Collection nodes) { + if (nodes == null) { + throw new NullPointerException(); + } + + DFS dfs = new DFS(nodes); + return dfs.go(); + } + + private boolean go() { + Iterator i; + time = 0; + boolean acyclic=true; + i = nodes.iterator(); + while (i.hasNext()) { + FlagState gn = (FlagState) i.next(); + gn.reset(); + } + + i = nodes.iterator(); + while (i.hasNext()) { + FlagState gn = (FlagState) i.next(); + assert gn.getStatus() != PROCESSING; + if (gn.getStatus() == UNVISITED) { + if (!dfs(gn)) + acyclic=false; + } + } + return acyclic; + } + + private boolean dfs(FlagState gn) { + boolean acyclic=true; + gn.discover(time++); + Iterator edges = gn.edges(); + + while (edges.hasNext()) { + Edge edge = (Edge) edges.next(); + FlagState node = edge.getTarget(); + if (!nodes.contains(node)) /* Skip nodes which aren't in the set */ + continue; + if (node.getStatus() == UNVISITED) { + if (!dfs(node)) + acyclic=false; + } else if (node.getStatus()==PROCESSING) { + acyclic=false; + } + } + if (finishingorder!=null) + finishingorder.add(gn); + gn.finish(time++); + return acyclic; + } + } /* end DFS */ } diff --git a/Robust/src/Analysis/TaskStateAnalysis/TriggerState.java b/Robust/src/Analysis/TaskStateAnalysis/TriggerState.java deleted file mode 100644 index 9210dbfe..00000000 --- a/Robust/src/Analysis/TaskStateAnalysis/TriggerState.java +++ /dev/null @@ -1,42 +0,0 @@ -package Analysis.TaskStateAnalysis; -import Analysis.TaskStateAnalysis.*; -import IR.*; -import IR.Tree.*; -import IR.Flat.*; -import java.util.*; - -public class TriggerState -{ - ClassDescriptor cd; - FlagState fs; - - public TriggerState(ClassDescriptor cd, FlagState fs) { - throw new Error("Just use FlagState...roll classdescriptor into it"); - this.cd = cd; - this.fs = fs; - } - - public ClassDescriptor getClassDescriptor() - { - return cd; - } - - public FlagState getState() - { - return fs; - } - - public boolean equals(TriggerState ts) - { - if ((this.getClassDescriptor().getNum()==ts.getClassDescriptor().getNum()) && (this.getState().isEqual(ts.getState()))) - { - return true; - } - else - { - return false; - } - } - -} - -- 2.34.1