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<TagDescriptor,Integer> tags=new Hashtable<TagDescriptor,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<TagDescriptor,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<TagDescriptor,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<TagDescriptor,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=(HashSet)flagstate.clone();
104 Hashtable<TagDescriptor,Integer> newtags=(Hashtable<TagDescriptor,Integer>)tags.clone();
106 if (newtags.containsKey(tag)){
107 switch (newtags.get(tag).intValue()){
109 newtags.put(tag,new Integer(MULTITAGS));
112 newtags.put(tag,new Integer(MULTITAGS));
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){
136 FlagState[] retstates;
138 if (tags.containsKey(tag)){
139 switch(tags.get(tag).intValue()){
141 HashSet newset=(HashSet)flagstate.clone();
142 Hashtable<TagDescriptor,Integer> newtags=(Hashtable<TagDescriptor,Integer>)tags.clone();
144 retstates=new FlagState[]{new FlagState(newset,cd,newtags)};
148 //when tagcount is more than 2, COUNT stays at MULTITAGS
149 retstates=new FlagState[2];
150 HashSet newset1=(HashSet)flagstate.clone();
151 Hashtable<TagDescriptor,Integer> newtags1=(Hashtable<TagDescriptor,Integer>)tags.clone();
152 retstates[1]=new FlagState(newset1,cd,newtags1);
153 //when tagcount is 2, COUNT changes to ONETAG
154 HashSet newset2=(HashSet)flagstate.clone();
155 Hashtable<TagDescriptor,Integer> newtags2=(Hashtable<TagDescriptor,Integer>)tags.clone();
156 newtags1.put(tag,new Integer(ONETAG));
157 retstates[1]=new FlagState(newset2,cd,newtags2);
163 throw new Error("Invalid Operation: Can not clear a tag that doesn't exist.");
169 /** Creates a string description of the flagstate
170 * e.g. a flagstate with five flags could look like 01001
171 * @param flags an array of flagdescriptors.
172 * @return string representation of the flagstate.
174 public String toString(FlagDescriptor[] flags)
176 StringBuffer sb = new StringBuffer(flagstate.size());
177 for(int i=0;i < flags.length; i++)
185 return new String(sb);
189 * @return returns the classdescriptor of the flagstate.
192 public ClassDescriptor getClassDescriptor(){
196 /** Sets the status of a specific flag in a flagstate after cloning it.
197 * @param fd FlagDescriptor of the flag whose status is being set.
198 * @param status boolean value
199 * @return the new flagstate with <CODE>fd</CODE> set to <CODE>status</CODE>.
202 public FlagState setFlag(FlagDescriptor fd, boolean status) {
203 HashSet newset=(HashSet) flagstate.clone();
204 Hashtable<TagDescriptor,Integer> newtags=(Hashtable<TagDescriptor,Integer>)tags.clone();
207 else if (newset.contains(fd)){
211 return new FlagState(newset, cd,newtags);
214 /** Tests for equality of two flagstate objects.
217 public boolean equals(Object o) {
218 if (o instanceof FlagState) {
219 FlagState fs=(FlagState)o;
222 return (fs.flagstate.equals(flagstate) & fs.tags.equals(tags));
227 public int hashCode() {
228 return cd.hashCode()^flagstate.hashCode()^tags.hashCode();
231 public static void computeclosure(Collection nodes, Collection removed) {
232 Stack tovisit=new Stack();
233 tovisit.addAll(nodes);
234 while(!tovisit.isEmpty()) {
235 FlagState gn=(FlagState)tovisit.pop();
236 for(Iterator it=gn.edges();it.hasNext();) {
237 Edge edge=(Edge)it.next();
238 FlagState target=edge.getTarget();
239 if (!nodes.contains(target)) {
240 if ((removed==null)||
241 (!removed.contains(target))) {
243 tovisit.push(target);
250 public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
251 Stack tovisit=new Stack();
252 Stack newvisit=new Stack();
253 tovisit.addAll(nodes);
254 for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
255 while(!tovisit.isEmpty()) {
256 FlagState gn=(FlagState)tovisit.pop();
257 for(Iterator it=gn.edges();it.hasNext();) {
258 Edge edge=(Edge)it.next();
259 FlagState target=edge.getTarget();
260 if (!nodes.contains(target)) {
261 if ((removed==null)||
262 (!removed.contains(target))) {
264 newvisit.push(target);
270 newvisit=new Stack();
274 public void setDotNodeParameters(String param) {
276 throw new NullPointerException();
278 if (param.length() > 0) {
279 dotnodeparams = "," + param;
281 dotnodeparams = new String();
285 public void setStatus(NodeStatus status) {
286 if (status == null) {
287 throw new NullPointerException();
289 this.status = status;
292 public String getLabel() {
296 public String getTextLabel() {
298 for(Iterator it=getFlags();it.hasNext();) {
299 FlagDescriptor fd=(FlagDescriptor) it.next();
303 label+=", "+fd.toString();
305 for (Enumeration en_tags=getTags();en_tags.hasMoreElements();){
306 TagDescriptor td=(TagDescriptor)en_tags.nextElement();
307 switch (tags.get(td).intValue()){
309 label+=", "+td.toString()+"(1)";
312 label+=", "+td.toString()+"(n)";
321 public Enumeration getTags(){
325 public NodeStatus getStatus() {
329 public Iterator edges() {
330 return edges.iterator();
333 public Iterator inedges() {
334 return inedges.iterator();
337 public void addEdge(Edge newedge) {
338 newedge.setSource(this);
339 edges.addElement(newedge);
340 FlagState tonode=newedge.getTarget();
341 tonode.inedges.addElement(newedge);
354 void discover(int time) {
355 discoverytime = time;
359 void finish(int time) {
360 assert status == PROCESSING;
361 finishingtime = time;
365 /** Returns finishing time for dfs */
367 public int getFinishingTime() {
368 return finishingtime;
372 public static class DOTVisitor {
374 java.io.PrintWriter output;
378 private DOTVisitor(java.io.OutputStream output) {
381 this.output = new java.io.PrintWriter(output, true);
384 private String getNewID(String name) {
385 tokennumber = tokennumber + 1;
386 return new String (name+tokennumber);
392 public static void visit(java.io.OutputStream output, Collection nodes) {
393 visit(output,nodes,null);
396 public static void visit(java.io.OutputStream output, Collection nodes, Collection special) {
397 DOTVisitor visitor = new DOTVisitor(output);
398 visitor.special=special;
399 visitor.nodes = nodes;
403 private void make() {
404 output.println("digraph dotvisitor {");
405 output.println("\trotate=90;");
406 /* output.println("\tpage=\"8.5,11\";");
407 output.println("\tnslimit=1000.0;");
408 output.println("\tnslimit1=1000.0;");
409 output.println("\tmclimit=1000.0;");
410 output.println("\tremincross=true;");*/
411 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
412 output.println("\tedge [fontsize=6];");
414 output.println("}\n");
417 private void traverse() {
418 Iterator i = nodes.iterator();
419 while (i.hasNext()) {
420 FlagState gn = (FlagState) i.next();
421 Iterator edges = gn.edges();
422 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
423 String option=gn.nodeoption;
424 if (special!=null&&special.contains(gn))
425 option+=",shape=box";
427 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
429 while (edges.hasNext()) {
430 Edge edge = (Edge) edges.next();
431 FlagState node = edge.getTarget();
432 if (nodes.contains(node)) {
433 for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
434 FlagState node2=(FlagState)nodeit.next();
435 String edgelabel = "label=\"" + edge.getLabel() + "\"";
436 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
444 Set nonmerge(FlagState gn) {
445 HashSet newset=new HashSet();
446 HashSet toprocess=new HashSet();
448 while(!toprocess.isEmpty()) {
449 FlagState gn2=(FlagState)toprocess.iterator().next();
450 toprocess.remove(gn2);
454 Iterator edges = gn2.edges();
455 while (edges.hasNext()) {
456 Edge edge = (Edge) edges.next();
457 FlagState node = edge.getTarget();
458 if (!newset.contains(node)&&nodes.contains(node))
468 /** This function returns the set of nodes involved in cycles.
469 * It only considers cycles containing nodes in the set 'nodes'.
471 public static Set findcycles(Collection nodes) {
472 HashSet cycleset=new HashSet();
473 SCC scc=DFS.computeSCC(nodes);
474 if (!scc.hasCycles())
476 for(int i=0;i<scc.numSCC();i++) {
478 cycleset.addAll(scc.getSCC(i));
483 public static class SCC {
487 public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
488 this.acyclic=acyclic;
494 /** Returns whether the graph has any cycles */
495 public boolean hasCycles() {
499 /** Returns the number of Strongly Connected Components */
500 public int numSCC() {
504 /** Returns the strongly connected component number for the FlagState gn*/
505 public int getComponent(FlagState gn) {
506 return ((Integer)revmap.get(gn)).intValue();
509 /** Returns the set of nodes in the strongly connected component i*/
510 public Set getSCC(int i) {
511 Integer scc=new Integer(i);
512 return (Set)map.get(scc);
515 /** Returns whether the strongly connected component i contains a cycle */
516 boolean hasCycle(int i) {
517 Integer scc=new Integer(i);
518 Set s=(Set)map.get(scc);
521 Object [] array=s.toArray();
522 FlagState gn=(FlagState)array[0];
523 for(Iterator it=gn.edges();it.hasNext();) {
524 Edge e=(Edge)it.next();
525 if (e.getTarget()==gn)
526 return true; /* Self Cycle */
533 * DFS encapsulates the depth first search algorithm
535 public static class DFS {
540 Vector finishingorder=null;
544 private DFS(Collection nodes) {
547 /** Calculates the strong connected components for the graph composed
548 * of the set of nodes 'nodes'*/
549 public static SCC computeSCC(Collection nodes) {
551 throw new NullPointerException();
553 DFS dfs=new DFS(nodes);
554 dfs.sccmap=new HashMap();
555 dfs.sccmaprev=new HashMap();
556 dfs.finishingorder=new Vector();
557 boolean acyclic=dfs.go();
558 for (Iterator it = nodes.iterator();it.hasNext();) {
559 FlagState gn = (FlagState) it.next();
562 for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
563 FlagState gn=(FlagState)dfs.finishingorder.get(i);
564 if (gn.getStatus() == UNVISITED) {
566 dfs.sccindex++; /* Increment scc index */
569 return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
572 void dfsprev(FlagState gn) {
573 if (gn.getStatus()==FINISHED||!nodes.contains(gn))
575 gn.setStatus(FINISHED);
576 Integer i=new Integer(sccindex);
577 if (!sccmap.containsKey(i))
578 sccmap.put(i,new HashSet());
579 ((Set)sccmap.get(i)).add(gn);
581 for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
582 Edge e=(Edge)edgeit.next();
583 FlagState gn2=e.getSource();
588 public static boolean depthFirstSearch(Collection nodes) {
590 throw new NullPointerException();
593 DFS dfs = new DFS(nodes);
597 private boolean go() {
600 boolean acyclic=true;
601 i = nodes.iterator();
602 while (i.hasNext()) {
603 FlagState gn = (FlagState) i.next();
607 i = nodes.iterator();
608 while (i.hasNext()) {
609 FlagState gn = (FlagState) i.next();
610 assert gn.getStatus() != PROCESSING;
611 if (gn.getStatus() == UNVISITED) {
619 private boolean dfs(FlagState gn) {
620 boolean acyclic=true;
622 Iterator edges = gn.edges();
624 while (edges.hasNext()) {
625 Edge edge = (Edge) edges.next();
626 FlagState node = edge.getTarget();
627 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
629 if (node.getStatus() == UNVISITED) {
632 } else if (node.getStatus()==PROCESSING) {
636 if (finishingorder!=null)
637 finishingorder.add(gn);