1 package Analysis.TaskStateAnalysis;
2 import Analysis.TaskStateAnalysis.*;
9 /** This class is used to hold the flag states that a class in the Bristlecone
10 * program can exist in, during runtime.
12 public class FlagState {
13 /* NodeStatus enumeration pattern ***********/
15 public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED");
16 public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING");
17 public static final NodeStatus FINISHED = new NodeStatus("FINISHED");
18 public static final int ONETAG=1;
19 public static final int NOTAGS=0;
20 public static final int MULTITAGS=-1;
25 public static class NodeStatus {
26 private static String name;
27 private NodeStatus(String name) { this.name = name; }
28 public String toString() { return name; }
32 int discoverytime = -1;
33 int finishingtime = -1; /* used for searches */
35 //Hashtable<String,Integer> tags=new Hashtable<String,Integer>();
36 Vector edges = new Vector();
37 Vector inedges = new Vector();
38 NodeStatus status = UNVISITED;
39 protected String dotnodeparams = new String();
43 private static int nodeid=0;
45 private final HashSet flagstate;
46 private final ClassDescriptor cd;
47 private final Hashtable<String,Integer> tags;
49 public void setOption(String option) {
50 this.nodeoption=","+option;
53 public void setMerge() {
57 * Creates a new flagstate with all flags set to false.
58 * @param cd ClassDescriptor
60 public FlagState(ClassDescriptor cd) {
61 this.flagstate=new HashSet();
63 this.tags=new Hashtable<String,Integer>();
64 this.uid=FlagState.nodeid++;
68 * Creates a new flagstate with flags set according to the HashSet.
69 * If the flag exists in the hashset, it's set to true else set to false.
70 * @param cd ClassDescriptor
71 * @param flagstate a <CODE>HashSet</CODE> containing FlagDescriptors
73 private FlagState(HashSet flagstate, ClassDescriptor cd,Hashtable<String,Integer> tags) {
74 this.flagstate=flagstate;
77 this.uid=FlagState.nodeid++;
82 * @param fd FlagDescriptor
83 * @return true if the flagstate contains fd else false.
85 public boolean get(FlagDescriptor fd) {
86 return flagstate.contains(fd);
90 public String toString() {
91 return cd.toString()+getTextLabel();
94 /** @return Iterator over the flags in the flagstate.
97 public Iterator getFlags() {
98 return flagstate.iterator();
101 public FlagState setTag(TagDescriptor tag){
103 HashSet newset=flagstate.clone();
104 Hashtable<String,Integer> newtags=tags.clone();
106 if (newtags.containsKey(tag)){
107 switch (newtags.get(tag).intValue()){
109 newtags.put(tag,new Integer(MULTITAG));
112 newtags.put(tag,new Integer(MULTITAG));
117 newtags.put(tag,new Integer(ONETAG));
120 return new FlagState(newset,cd,newtags);
123 public int getTagCount(String tagtype){
124 for (Enumeration en=getTags();en.hasMoreElements();){
125 TagDescriptor td=(TagDescriptor)en.nextElement();
126 if (tagtype.equals(td.getSymbol()))
127 return tags.get(td).intValue(); //returns either ONETAG or MULTITAG
135 public FlagState[] clearTag(TagDescriptor tag){
137 if (tags.containsKey(tag)){
138 switch(tags.get(tag).intValue()){
140 HashSet newset=flagstate.clone();
141 Hashtable<String,Integer> newtags=tags.clone();
143 return new FlagState(newset,cd,newtags);
146 //when tagcount is more than 2, COUNT stays at MULTITAG
147 FlagState[] retstates=new FlagState[2];
148 HashSet newset1=flagstate.clone();
149 Hashtable<String,Integer> newtags1=tags.clone();
150 retstates[1]=new FlagState(newset1,cd,newtags1);
151 //when tagcount is 2, COUNT changes to ONETAG
152 HashSet newset2=flagstate.clone();
153 Hashtable<String,Integer> newtags2=tags.clone();
154 newtags1.put(tag,new Integer(ONETAG));
155 retstates[1]=new FlagState(newset2,cd,newtags2);
160 throw new Error("Invalid Operation: Can not clear a tag that doesn't exist.");
165 /** Creates a string description of the flagstate
166 * e.g. a flagstate with five flags could look like 01001
167 * @param flags an array of flagdescriptors.
168 * @return string representation of the flagstate.
170 public String toString(FlagDescriptor[] flags)
172 StringBuffer sb = new StringBuffer(flagstate.size());
173 for(int i=0;i < flags.length; i++)
181 return new String(sb);
185 * @return returns the classdescriptor of the flagstate.
188 public ClassDescriptor getClassDescriptor(){
192 /** Sets the status of a specific flag in a flagstate after cloning it.
193 * @param fd FlagDescriptor of the flag whose status is being set.
194 * @param status boolean value
195 * @return the new flagstate with <CODE>fd</CODE> set to <CODE>status</CODE>.
198 public FlagState setFlag(FlagDescriptor fd, boolean status) {
199 HashSet newset=(HashSet) flagstate.clone();
202 else if (newset.contains(fd)){
205 return new FlagState(newset, cd);
208 /** Tests for equality of two flagstate objects.
211 public boolean equals(Object o) {
212 if (o instanceof FlagState) {
213 FlagState fs=(FlagState)o;
216 return (fs.flagstate.equals(flagstate) & fs.tags.equals(tags));
221 public int hashCode() {
222 return cd.hashCode()^flagstate.hashCode()^tags.hashCode();
225 public static void computeclosure(Collection nodes, Collection removed) {
226 Stack tovisit=new Stack();
227 tovisit.addAll(nodes);
228 while(!tovisit.isEmpty()) {
229 FlagState gn=(FlagState)tovisit.pop();
230 for(Iterator it=gn.edges();it.hasNext();) {
231 Edge edge=(Edge)it.next();
232 FlagState target=edge.getTarget();
233 if (!nodes.contains(target)) {
234 if ((removed==null)||
235 (!removed.contains(target))) {
237 tovisit.push(target);
244 public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
245 Stack tovisit=new Stack();
246 Stack newvisit=new Stack();
247 tovisit.addAll(nodes);
248 for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
249 while(!tovisit.isEmpty()) {
250 FlagState gn=(FlagState)tovisit.pop();
251 for(Iterator it=gn.edges();it.hasNext();) {
252 Edge edge=(Edge)it.next();
253 FlagState target=edge.getTarget();
254 if (!nodes.contains(target)) {
255 if ((removed==null)||
256 (!removed.contains(target))) {
258 newvisit.push(target);
264 newvisit=new Stack();
268 public void setDotNodeParameters(String param) {
270 throw new NullPointerException();
272 if (param.length() > 0) {
273 dotnodeparams = "," + param;
275 dotnodeparams = new String();
279 public void setStatus(NodeStatus status) {
280 if (status == null) {
281 throw new NullPointerException();
283 this.status = status;
286 public String getLabel() {
290 public String getTextLabel() {
292 for(Iterator it=getFlags();it.hasNext();) {
293 FlagDescriptor fd=(FlagDescriptor) it.next();
297 label+=", "+fd.toString();
299 for (Enumeration en_tags=getTags();en_tags.hasMoreElements();){
300 TagDescriptor td=(TagDescriptor)en_tags.nextElement();
301 switch (tags.get(td).intValue()){
303 label+=", "+td.toString()+"(1)";
306 label+=", "+td.toString()+"(n)";
315 public Enumeration getTags(){
319 public NodeStatus getStatus() {
323 public Iterator edges() {
324 return edges.iterator();
327 public Iterator inedges() {
328 return inedges.iterator();
331 public void addEdge(Edge newedge) {
332 newedge.setSource(this);
333 edges.addElement(newedge);
334 FlagState tonode=newedge.getTarget();
335 tonode.inedges.addElement(newedge);
348 void discover(int time) {
349 discoverytime = time;
353 void finish(int time) {
354 assert status == PROCESSING;
355 finishingtime = time;
359 /** Returns finishing time for dfs */
361 public int getFinishingTime() {
362 return finishingtime;
366 public static class DOTVisitor {
368 java.io.PrintWriter output;
372 private DOTVisitor(java.io.OutputStream output) {
375 this.output = new java.io.PrintWriter(output, true);
378 private String getNewID(String name) {
379 tokennumber = tokennumber + 1;
380 return new String (name+tokennumber);
386 public static void visit(java.io.OutputStream output, Collection nodes) {
387 visit(output,nodes,null);
390 public static void visit(java.io.OutputStream output, Collection nodes, Collection special) {
391 DOTVisitor visitor = new DOTVisitor(output);
392 visitor.special=special;
393 visitor.nodes = nodes;
397 private void make() {
398 output.println("digraph dotvisitor {");
399 output.println("\trotate=90;");
400 /* output.println("\tpage=\"8.5,11\";");
401 output.println("\tnslimit=1000.0;");
402 output.println("\tnslimit1=1000.0;");
403 output.println("\tmclimit=1000.0;");
404 output.println("\tremincross=true;");*/
405 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
406 output.println("\tedge [fontsize=6];");
408 output.println("}\n");
411 private void traverse() {
412 Iterator i = nodes.iterator();
413 while (i.hasNext()) {
414 FlagState gn = (FlagState) i.next();
415 Iterator edges = gn.edges();
416 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
417 String option=gn.nodeoption;
418 if (special!=null&&special.contains(gn))
419 option+=",shape=box";
421 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
423 while (edges.hasNext()) {
424 Edge edge = (Edge) edges.next();
425 FlagState node = edge.getTarget();
426 if (nodes.contains(node)) {
427 for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
428 FlagState node2=(FlagState)nodeit.next();
429 String edgelabel = "label=\"" + edge.getLabel() + "\"";
430 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
438 Set nonmerge(FlagState gn) {
439 HashSet newset=new HashSet();
440 HashSet toprocess=new HashSet();
442 while(!toprocess.isEmpty()) {
443 FlagState gn2=(FlagState)toprocess.iterator().next();
444 toprocess.remove(gn2);
448 Iterator edges = gn2.edges();
449 while (edges.hasNext()) {
450 Edge edge = (Edge) edges.next();
451 FlagState node = edge.getTarget();
452 if (!newset.contains(node)&&nodes.contains(node))
462 /** This function returns the set of nodes involved in cycles.
463 * It only considers cycles containing nodes in the set 'nodes'.
465 public static Set findcycles(Collection nodes) {
466 HashSet cycleset=new HashSet();
467 SCC scc=DFS.computeSCC(nodes);
468 if (!scc.hasCycles())
470 for(int i=0;i<scc.numSCC();i++) {
472 cycleset.addAll(scc.getSCC(i));
477 public static class SCC {
481 public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
482 this.acyclic=acyclic;
488 /** Returns whether the graph has any cycles */
489 public boolean hasCycles() {
493 /** Returns the number of Strongly Connected Components */
494 public int numSCC() {
498 /** Returns the strongly connected component number for the FlagState gn*/
499 public int getComponent(FlagState gn) {
500 return ((Integer)revmap.get(gn)).intValue();
503 /** Returns the set of nodes in the strongly connected component i*/
504 public Set getSCC(int i) {
505 Integer scc=new Integer(i);
506 return (Set)map.get(scc);
509 /** Returns whether the strongly connected component i contains a cycle */
510 boolean hasCycle(int i) {
511 Integer scc=new Integer(i);
512 Set s=(Set)map.get(scc);
515 Object [] array=s.toArray();
516 FlagState gn=(FlagState)array[0];
517 for(Iterator it=gn.edges();it.hasNext();) {
518 Edge e=(Edge)it.next();
519 if (e.getTarget()==gn)
520 return true; /* Self Cycle */
527 * DFS encapsulates the depth first search algorithm
529 public static class DFS {
534 Vector finishingorder=null;
538 private DFS(Collection nodes) {
541 /** Calculates the strong connected components for the graph composed
542 * of the set of nodes 'nodes'*/
543 public static SCC computeSCC(Collection nodes) {
545 throw new NullPointerException();
547 DFS dfs=new DFS(nodes);
548 dfs.sccmap=new HashMap();
549 dfs.sccmaprev=new HashMap();
550 dfs.finishingorder=new Vector();
551 boolean acyclic=dfs.go();
552 for (Iterator it = nodes.iterator();it.hasNext();) {
553 FlagState gn = (FlagState) it.next();
556 for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
557 FlagState gn=(FlagState)dfs.finishingorder.get(i);
558 if (gn.getStatus() == UNVISITED) {
560 dfs.sccindex++; /* Increment scc index */
563 return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
566 void dfsprev(FlagState gn) {
567 if (gn.getStatus()==FINISHED||!nodes.contains(gn))
569 gn.setStatus(FINISHED);
570 Integer i=new Integer(sccindex);
571 if (!sccmap.containsKey(i))
572 sccmap.put(i,new HashSet());
573 ((Set)sccmap.get(i)).add(gn);
575 for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
576 Edge e=(Edge)edgeit.next();
577 FlagState gn2=e.getSource();
582 public static boolean depthFirstSearch(Collection nodes) {
584 throw new NullPointerException();
587 DFS dfs = new DFS(nodes);
591 private boolean go() {
594 boolean acyclic=true;
595 i = nodes.iterator();
596 while (i.hasNext()) {
597 FlagState gn = (FlagState) i.next();
601 i = nodes.iterator();
602 while (i.hasNext()) {
603 FlagState gn = (FlagState) i.next();
604 assert gn.getStatus() != PROCESSING;
605 if (gn.getStatus() == UNVISITED) {
613 private boolean dfs(FlagState gn) {
614 boolean acyclic=true;
616 Iterator edges = gn.edges();
618 while (edges.hasNext()) {
619 Edge edge = (Edge) edges.next();
620 FlagState node = edge.getTarget();
621 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
623 if (node.getStatus() == UNVISITED) {
626 } else if (node.getStatus()==PROCESSING) {
630 if (finishingorder!=null)
631 finishingorder.add(gn);