1 package Analysis.TaskStateAnalysis;
5 import IR.ClassDescriptor;
6 import IR.TaskDescriptor;
8 import java.io.FileWriter;
9 import java.io.FileOutputStream;
12 public class ExecutionGraph {
14 private TaskAnalysis taskanalysis;
16 private Hashtable graph;
17 private Hashtable executiongraph;
18 private SymbolTable tasks;
20 public ExecutionGraph(State state, TaskAnalysis ta){
23 this.tasks = this.state. getTaskSymbolTable();
24 this.graph=new Hashtable();
25 this.executiongraph = new Hashtable();
28 public Hashtable getExecutionGraph(){
29 return executiongraph;
32 public void createExecutionGraph() throws java.io.IOException {
33 /*Explore the taskanalysis structure*/
35 Enumeration e=taskanalysis.flagstates.keys();
37 while (e.hasMoreElements()) {
38 System.out.println("\nInto class :");
39 ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
40 System.out.println("\t"+(cdtemp.getSymbol())+ "\n");
49 private void exploreGraph(ClassDescriptor cd) {
51 LinkedList fifo = new LinkedList();
52 Vector sourceNodeList = new Vector();
56 /* Search for starting nodes */
57 Collection nodes = ((Hashtable)taskanalysis.flagstates.get(cd)).values();
58 Iterator it = nodes.iterator();
59 while (it.hasNext()) {
60 FlagState fs = (FlagState)it.next();
61 if(fs.isSourceNode()){
62 sourceNodeList.addElement(fs);
66 /* Perform the Breadth first search algorithm and build ExecutionGraph */
67 FlagState fstemp, fstemp2;
68 Iterator sourceit = sourceNodeList.iterator();
69 while( sourceit.hasNext() ){
70 FlagState fs = (FlagState)sourceit.next();
75 while ( !fifo.isEmpty() ){
77 fstemp = (FlagState)fifo.getFirst();
80 System.out.println("IN FS : "+fstemp.getTextLabel());
82 Iterator edges = fstemp.edges();
85 //build corresponding nodes of the ExecutionGraph
88 //add the other non marked (prevent looping) fses to the fifo
89 while(edges.hasNext()){
91 FEdge edge = (FEdge)edges.next();
92 fstemp2 = (FlagState)edge.getTarget();
94 if ( !fstemp2.isMarked() ) {
96 fifo.addLast(fstemp2);
100 //if the flagstate is not entirely processed, back into fifo
101 if (!isFinished(fstemp)){
102 fifo.addLast(fstemp);
107 //clean the graph to remove doubles due to reinjection of non totally processed fses in the fifo
108 graph = clean(graph);
112 private void createNode(FlagState fs){
113 Enumeration allocatingtasks;
117 //the idea is to look at the inedges to find the "parents" nodes. Then create the "children" and link them to the "parents".
118 if (fs.isSourceNode()){
119 //in the case of sourcenode, "parents" are the allocating tasks
120 for (Iterator inedges = ((Vector)fs.getAllocatingTasks()).iterator(); inedges.hasNext();){
121 String tname = new String(((TaskDescriptor)inedges.next()).getSymbol());
122 //the hashkey for source EGTaskNodes is : nextfs+taskname.
123 String key1 = new String(fs.getTextLabel()+tname);
125 if (graph.containsKey(key1)){
126 tn = (EGTaskNode)graph.get(key1);
128 else{//if not existing, create it
129 tn = new EGTaskNode(tname,(TaskDescriptor)tasks.get(tname));
132 //create the children. the key is : nextfs+taskname+previousfs (that ensures that only one node can have that key).
133 for (Iterator edges = fs.edges(); edges.hasNext();){
134 edge = (FEdge)edges.next();
135 target=new EGTaskNode(edge.getLabel(), fs, (TaskDescriptor)tasks.get(edge.getLabel()));
136 String key2 = new String(((FlagState)edge.getTarget()).getTextLabel()+target.getName()+((FlagState)edge.getSource()).getTextLabel());
137 //mark if is self loop
138 if (((FlagState)edge.getTarget()).isMarked()){
139 target.doSelfLoopMarking();
141 //check if child already exists. if not, create it.
142 //link to the parent.
143 if (graph.containsKey(key2)){
144 target = (EGTaskNode)graph.get(key2);
145 TEdge newedge=new TEdge(target);
149 TEdge newedge=new TEdge(target);
153 graph.put(key2, target);
155 //put parent in graph
160 for (Iterator inedges = fs.inedges(); inedges.hasNext();){
161 //regular case, "parents" are the inedges.
162 FEdge in=(FEdge)inedges.next();
163 if (!in.isProcessed()){
164 //the key to search is : nextfs+taskname+previousfs.
165 String key1 = new String(fs.getTextLabel()+in.getLabel()+((FlagState)in.getSource()).getTextLabel());
166 tn = (EGTaskNode)graph.get(key1);
167 //if the TaskNode does not exist, that means that we are in the case of a loop.
168 //The fs will not be entirely processed, will be put back in the fifo until the TaskNode has finaly been created.
170 //same process than with the sourcenode.
171 for (Iterator edges = fs.edges(); edges.hasNext();){
172 edge = (FEdge)edges.next();
173 target=new EGTaskNode(edge.getLabel(), fs, (TaskDescriptor)tasks.get(edge.getLabel()));
174 String key2 = new String(((FlagState)edge.getTarget()).getTextLabel()+target.getName()+((FlagState)edge.getSource()).getTextLabel());
175 if (((String)((FlagState)edge.getTarget()).getTextLabel()).compareTo(fs.getTextLabel())==0){
176 target.doSelfLoopMarking();
178 if (graph.containsKey(key2)){
179 target = (EGTaskNode)graph.get(key2);
180 TEdge newedge=new TEdge(target);
184 TEdge newedge=new TEdge(target);
187 graph.put(key2, target);
196 //put the graph into executiongraph
197 private void adapt(ClassDescriptor cd) {
198 Vector tasknodes = new Vector();
199 tasknodes.addAll(graph.values());
200 executiongraph.put(cd,tasknodes);
202 //print the contain of graph
203 private void test() {
204 System.out.println("\nGraph contains :");
205 Collection c = graph.values();
206 for ( Iterator it = c.iterator(); it.hasNext();){
207 EGTaskNode tn = (EGTaskNode)it.next();
208 System.out.println(tn.getTextLabel()+" ID "+tn.getLabel()+" FS "+tn.getFSName());
212 //removes the duplicated edges
213 private Hashtable clean(Hashtable ht){
214 Hashtable cleaned = new Hashtable();
215 Collection c = ht.values();
216 for ( Iterator it = c.iterator(); it.hasNext();){
217 EGTaskNode tn = (EGTaskNode)it.next();
218 Vector v = tn.getEdgeVector();
222 cleaned.put(tn.getuid(), tn);
227 //removes all the edge doubles in vector v
228 private Vector removeDouble(Vector v){
230 Vector vcleaned = new Vector();
231 for (Iterator it = v.iterator(); it.hasNext();){
233 TEdge edge = (TEdge)it.next();
235 for (Iterator it2 = vcleaned.iterator(); it2.hasNext();){
236 if (((EGTaskNode)edge.getTarget()).getuid()==((EGTaskNode)((TEdge)it2.next()).getTarget()).getuid()) contains = 1;
239 if (contains == 0) vcleaned.add(edge);
245 //test if a flagstate has been entirely processed
246 private boolean isFinished(FlagState fs){
248 for (Iterator inedges = fs.inedges(); inedges.hasNext();){
250 FEdge in=(FEdge)inedges.next();
252 if (!in.isProcessed()){
253 String key1 = new String(fs.getTextLabel()+in.getLabel()+((FlagState)in.getSource()).getTextLabel());
255 if (graph.get(key1)==null){
256 //except for the case of self loop, if the pointed tn is not present, fs is not totally processed
257 if (((String)((FlagState)in.getSource()).getTextLabel()).compareTo(fs.getTextLabel())!=0){
269 //create dot files execution_classname_.dot
270 private void printDOTFile()throws java.io.IOException {
271 Enumeration e = executiongraph.keys();
272 while (e.hasMoreElements()){
273 createDOTFile((ClassDescriptor)e.nextElement());
277 private void createDOTFile(ClassDescriptor cd) throws java.io.IOException {
278 Vector v = (Vector)executiongraph.get(cd);
279 java.io.PrintWriter output;
280 File dotfile_flagstates= new File("execution"+cd.getSymbol()+".dot");
281 FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
282 output = new java.io.PrintWriter(dotstream, true);
283 output.println("digraph dotvisitor {");
284 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
285 output.println("\tedge [fontsize=6];");
287 output.println("}\n");
290 private void traverse(java.io.PrintWriter output, Vector v) {
293 for(Iterator it1 = v.iterator(); it1.hasNext();){
294 tn = (EGTaskNode)it1.next();
295 output.println("\t"+tn.getLabel()+" [label=\""+tn.getTextLabel()+"\"");
296 if (tn.isSelfLoop()) output.println(", shape=box");
297 if (tn.isMultipleParams()) output.println(", color=blue");
298 output.println("];");
301 for(Iterator it2 = tn.edges();it2.hasNext();){
302 output.println("\t"+tn.getLabel()+" -> "+((EGTaskNode)((TEdge)it2.next()).getTarget()).getLabel()+";");
306 //*********************