Programming Languages Research Group: Git - IRC.git/blob

   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         System.out.println("------- BUILDING THE EXECUTION GRAPH -------");
  35         Enumeration e=taskanalysis.flagstates.keys();
  36
  37         while (e.hasMoreElements()) {
  38             System.out.println("\nBuilding 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         }
 108     }
 109
 110     private void createNode(FlagState fs){
 111         Enumeration allocatingtasks;
 112         EGTaskNode tn;
 113         EGTaskNode target;
 114         FEdge edge;
 115         //the idea is to look at the inedges to find the "parents" nodes. Then create the "children" and link them to the "parents".
 116         if (fs.isSourceNode()){
 117             //in the case of sourcenode, "parents" are the allocating tasks
 118             for (Iterator inedges = ((Vector)fs.getAllocatingTasks()).iterator(); inedges.hasNext();){
 119                 String tname = new String(((TaskDescriptor)inedges.next()).getSymbol());
 120                 //the hashkey for source EGTaskNodes is : nextfs+taskname.
 121                 String key1 = new String(fs.getTextLabel()+tname);
 122                 //get the parent
 123                 if (graph.containsKey(key1)){
 124                     tn = (EGTaskNode)graph.get(key1);
 125                 }
 126                 else{//if not existing, create it
 127                     tn = new EGTaskNode(tname,(TaskDescriptor)tasks.get(tname));
 128                     tn.setSource();
 129                 }
 130                 //create the children. the key is : nextfs+taskname+previousfs (that ensures that only one node can have that key).
 131                 for (Iterator edges = fs.edges(); edges.hasNext();){
 132                     edge = (FEdge)edges.next();
 133                     target=new EGTaskNode(edge.getLabel(), fs, (TaskDescriptor)tasks.get(edge.getLabel()));
 134                     String key2 = new String(((FlagState)edge.getTarget()).getTextLabel()+target.getName()+((FlagState)edge.getSource()).getTextLabel());
 135                     //mark if is self loop
 136                     if (((FlagState)edge.getTarget()).isMarked()){
 137                         target.doSelfLoopMarking();
 138                     }
 139                     //check if child already exists. if not, create it.
 140                     //link to the parent.
 141                     if (graph.containsKey(key2)){
 142                         target = (EGTaskNode)graph.get(key2);
 143                         EGEdge newedge=new EGEdge(target);
 144                         tn.addEdge(newedge);
 145                     }
 146                     else {
 147                         EGEdge newedge=new EGEdge(target);
 148                         tn.addEdge(newedge);
 149                     }
 150                     //put child in graph
 151                     graph.put(key2, target);
 152                 }
 153                 //put parent in graph
 154                 graph.put(key1, tn);
 155             }
 156         }
 157
 158         for (Iterator inedges = fs.inedges(); inedges.hasNext();){
 159             //regular case, "parents" are the inedges.
 160             FEdge in=(FEdge)inedges.next();
 161             if (!in.isProcessed()){
 162                 //the key to search is : nextfs+taskname+previousfs.
 163                 String key1 = new String(fs.getTextLabel()+in.getLabel()+((FlagState)in.getSource()).getTextLabel());
 164                 tn = (EGTaskNode)graph.get(key1);
 165                 //if the TaskNode does not exist, that means that we are in the case of a loop.
 166                 //The fs will not be entirely processed, will be put back in the fifo until the TaskNode has finaly been created.
 167                 if (tn != null){
 168                     //same process than with the sourcenode.
 169                     for (Iterator edges = fs.edges(); edges.hasNext();){
 170                         edge = (FEdge)edges.next();
 171                         target=new EGTaskNode(edge.getLabel(), fs, (TaskDescriptor)tasks.get(edge.getLabel()));
 172                         String key2 = new String(((FlagState)edge.getTarget()).getTextLabel()+target.getName()+((FlagState)edge.getSource()).getTextLabel());
 173                         if (((String)((FlagState)edge.getTarget()).getTextLabel()).compareTo(fs.getTextLabel())==0){
 174                             target.doSelfLoopMarking();
 175                         }
 176                         if (graph.containsKey(key2)){
 177                             target = (EGTaskNode)graph.get(key2);
 178                             EGEdge newedge=new EGEdge(target);
 179                             tn.addEdge(newedge);
 180                         }
 181                         else {
 182                             EGEdge newedge=new EGEdge(target);
 183                             tn.addEdge(newedge);
 184                         }
 185                         graph.put(key2, target);
 186                     }
 187                     graph.put(key1, tn);
 188                     in.setProcessed();
 189                 }
 190             }
 191         }
 192     }
 193
 194     //put the graph into executiongraph
 195     private void adapt(ClassDescriptor cd) {
 196         Vector tasknodes = new Vector();
 197         tasknodes.addAll(graph.values());
 198         executiongraph.put(cd,tasknodes);
 199     }
 200     //print the contain of graph
 201     private void test() {
 202         System.out.println("\nGraph contains :");
 203         Collection c = graph.values();
 204         for ( Iterator it = c.iterator(); it.hasNext();){
 205             EGTaskNode tn = (EGTaskNode)it.next();
 206             System.out.println(tn.getTextLabel()+" ID "+tn.getLabel()+" FS "+tn.getFSName());
 207         }
 208     }
 209
 210     //test if a flagstate has been entirely processed
 211     private boolean isFinished(FlagState fs){
 212
 213         for (Iterator inedges = fs.inedges(); inedges.hasNext();){
 214
 215             FEdge in=(FEdge)inedges.next();
 216
 217             if (!in.isProcessed()){
 218                 String key1 = new String(fs.getTextLabel()+in.getLabel()+((FlagState)in.getSource()).getTextLabel());
 219
 220                 if (graph.get(key1)==null){
 221                     //except for the case of self loop, if the pointed tn is not present, fs is not totally processed
 222                     if (((String)((FlagState)in.getSource()).getTextLabel()).compareTo(fs.getTextLabel())!=0){
 223                         return false;
 224                     }
 225                 }
 226
 227             }
 228         }
 229         return true;
 230     }
 231
 232
 233     //********DEBUG
 234     //create dot files execution_classname_.dot
 235     private void printDOTFile()throws java.io.IOException {
 236         Enumeration e = executiongraph.keys();
 237         while (e.hasMoreElements()){
 238             createDOTFile((ClassDescriptor)e.nextElement());
 239         }
 240     }
 241
 242     private void createDOTFile(ClassDescriptor cd) throws java.io.IOException {
 243         Vector v = (Vector)executiongraph.get(cd);
 244         java.io.PrintWriter output;
 245         File dotfile_flagstates= new File("execution"+cd.getSymbol()+".dot");
 246         FileOutputStream dotstream=new FileOutputStream(dotfile_flagstates,true);
 247         output = new java.io.PrintWriter(dotstream, true);
 248         output.println("digraph dotvisitor {");
 249         output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
 250         output.println("\tedge [fontsize=6];");
 251         traverse(output, v);
 252         output.println("}\n");
 253     }
 254
 255     private void traverse(java.io.PrintWriter output, Vector v) {
 256         EGTaskNode tn;
 257
 258         for(Iterator it1 = v.iterator(); it1.hasNext();){
 259             tn = (EGTaskNode)it1.next();
 260             output.println("\t"+tn.getLabel()+" [label=\""+tn.getTextLabel()+"\"");
 261             if (tn.isSelfLoop()) output.println(", shape=box");
 262             if (tn.isMultipleParams()) output.println(", color=blue");
 263             output.println("];");
 264
 265
 266             for(Iterator it2 = tn.edges();it2.hasNext();){
 267                 output.println("\t"+tn.getLabel()+" -> "+((EGTaskNode)((EGEdge)it2.next()).getTarget()).getLabel()+";");
 268             }
 269         }
 270     }
 271     //*********************
 272
 273 }
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286