Robust/src/Analysis/TaskStateAnalysis/ExecutionGraph.java

   1 package Analysis.TaskStateAnalysis;
   2 import java.util.*;
   3 import IR.State;
   4 import IR.SymbolTable;
   5 import IR.ClassDescriptor;
   6 import IR.TaskDescriptor;
   7 import java.io.File;
   8 import java.io.FileWriter;
   9 import java.io.FileOutputStream;
  10 import Util.Edge;
  11
  12 public class ExecutionGraph {
  13
  14     private TaskAnalysis taskanalysis;
  15     private State state;
  16     private Hashtable graph;
  17     private Hashtable executiongraph;
  18     private SymbolTable tasks;
  19
  20     public ExecutionGraph(State state, TaskAnalysis ta){
  21         this.taskanalysis=ta;
  22         this.state=state;
  23         this.tasks = this.state. getTaskSymbolTable();
  24         this.graph=new Hashtable();
  25         this.executiongraph = new Hashtable();
  26     }
  27
  28     public Hashtable getExecutionGraph(){
  29         return executiongraph;
  30     }
  31
  32     public void createExecutionGraph() throws java.io.IOException {
  33         /*Explore the taskanalysis structure*/
  34
  35         Enumeration e=taskanalysis.flagstates.keys();
  36
  37         while (e.hasMoreElements()) {
  38             System.out.println("\nInto class :");
  39             ClassDescriptor cdtemp=(ClassDescriptor)e.nextElement();
  40             System.out.println("\t"+(cdtemp.getSymbol())+ "\n");
  41             exploreGraph(cdtemp);
  42             test();
  43             adapt(cdtemp);
  44         }
  45         printDOTFile();
  46
  47     }
  48
  49     private void exploreGraph(ClassDescriptor cd) {
  50
  51         LinkedList fifo = new LinkedList();
  52         Vector sourceNodeList = new Vector();
  53         Enumeration e;
  54         graph.clear();
  55
  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);
  63             }
  64         }
  65
  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();
  71
  72             fs.doMarking();
  73             fifo.addLast(fs);
  74
  75             while ( !fifo.isEmpty() ){
  76
  77                 fstemp = (FlagState)fifo.getFirst();
  78                 fifo.removeFirst();
  79
  80                 System.out.println("IN FS : "+fstemp.getTextLabel());
  81
  82                 Iterator edges = fstemp.edges();
  83                 if (edges.hasNext()){
  84
  85                     //build corresponding nodes of the ExecutionGraph
  86                     createNode(fstemp);
  87
  88                     //add the other non marked (prevent looping) fses to the fifo
  89                     while(edges.hasNext()){
  90
  91                         FEdge edge = (FEdge)edges.next();
  92                         fstemp2 = (FlagState)edge.getTarget();
  93
  94                         if ( !fstemp2.isMarked() ) {
  95                             fstemp2.doMarking();
  96                             fifo.addLast(fstemp2);
  97                         }
  98                     }
  99
 100                     //if the flagstate is not entirely processed, back into fifo
 101                     if (!isFinished(fstemp)){
 102                         fifo.addLast(fstemp);
 103                     }
 104                 }
 105
 106             }
 107             //clean the graph to remove doubles due to reinjection of non totally processed fses in the fifo
 108             graph = clean(graph);
 109         }
 110     }
 111
 112     private void createNode(FlagState fs){
 113         Enumeration allocatingtasks;
 114         EGTaskNode tn;
 115         EGTaskNode target;
 116         FEdge edge;
 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);
 124                 //get the parent
 125                 if (graph.containsKey(key1)){
 126                     tn = (EGTaskNode)graph.get(key1);
 127                 }
 128                 else{//if not existing, create it
 129                     tn = new EGTaskNode(tname,(TaskDescriptor)tasks.get(tname));
 130                     tn.setSource();
 131                 }
 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();
 140                     }
 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);
 146                         tn.addEdge(newedge);
 147                     }
 148                     else {
 149                         TEdge newedge=new TEdge(target);
 150                         tn.addEdge(newedge);
 151                     }
 152                     //put child in graph
 153                     graph.put(key2, target);
 154                 }
 155                 //put parent in graph
 156                 graph.put(key1, tn);
 157             }
 158         }
 159
 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.
 169                 if (tn != null){
 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();
 177                         }
 178                         if (graph.containsKey(key2)){
 179                             target = (EGTaskNode)graph.get(key2);
 180                             TEdge newedge=new TEdge(target);
 181                             tn.addEdge(newedge);
 182                         }
 183                         else {
 184                             TEdge newedge=new TEdge(target);
 185                             tn.addEdge(newedge);
 186                         }
 187                         graph.put(key2, target);
 188                     }
 189                     graph.put(key1, tn);
 190                     in.setProcessed();
 191                 }
 192             }
 193         }
 194     }
 195
 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);
 201     }
 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());
 209         }
 210     }
 211
 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();
 219             v = removeDouble(v);
 220             tn.removeAllEdges();
 221             tn.addEdge(v);
 222             cleaned.put(tn.getuid(), tn);
 223         }
 224         return cleaned;
 225     }
 226
 227     //removes all the edge doubles in vector v
 228     private Vector removeDouble(Vector v){
 229
 230         Vector vcleaned = new Vector();
 231         for (Iterator it = v.iterator(); it.hasNext();){
 232
 233             TEdge edge = (TEdge)it.next();
 234             int contains = 0;
 235             for (Iterator it2 = vcleaned.iterator(); it2.hasNext();){
 236                 if (((EGTaskNode)edge.getTarget()).getuid()==((EGTaskNode)((TEdge)it2.next()).getTarget()).getuid()) contains = 1;
 237             }
 238
 239             if (contains == 0) vcleaned.add(edge);
 240         }
 241
 242         return vcleaned;
 243     }
 244
 245     //test if a flagstate has been entirely processed
 246     private boolean isFinished(FlagState fs){
 247
 248         for (Iterator inedges = fs.inedges(); inedges.hasNext();){
 249
 250             FEdge in=(FEdge)inedges.next();
 251
 252             if (!in.isProcessed()){
 253                 String key1 = new String(fs.getTextLabel()+in.getLabel()+((FlagState)in.getSource()).getTextLabel());
 254
 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){
 258                         return false;
 259                     }
 260                 }
 261
 262             }
 263         }
 264         return true;
 265     }
 266
 267
 268     //********DEBUG
 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());
 274         }
 275     }
 276
 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];");
 286         traverse(output, v);
 287         output.println("}\n");
 288     }
 289
 290     private void traverse(java.io.PrintWriter output, Vector v) {
 291         EGTaskNode tn;
 292
 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("];");
 299
 300
 301             for(Iterator it2 = tn.edges();it2.hasNext();){
 302                 output.println("\t"+tn.getLabel()+" -> "+((EGTaskNode)((TEdge)it2.next()).getTarget()).getLabel()+";");
 303             }
 304         }
 305     }
 306     //*********************
 307
 308 }
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321