Repair/RepairCompiler/MCC/IR/GraphNode.java

   1 package MCC.IR;
   2
   3 import java.util.*;
   4 import java.io.*;
   5
   6 public class GraphNode {
   7
   8     public static boolean useEdgeLabels;
   9
  10     /* NodeStatus enumeration pattern ***********/
  11
  12     public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED");
  13     public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING");
  14     public static final NodeStatus FINISHED = new NodeStatus("FINISHED");
  15
  16     public static class NodeStatus {
  17         private static String name;
  18         private NodeStatus(String name) { this.name = name; }
  19         public String toString() { return name; }
  20     }
  21
  22     /* Edge *****************/
  23
  24     public static class Edge {
  25
  26         private String label;
  27         private GraphNode target;
  28         private String dotnodeparams = new String();
  29
  30         public Edge(String label, GraphNode target) {
  31             this.label = label;
  32             this.target = target;
  33         }
  34
  35         public String getLabel() {
  36             return label;
  37         }
  38
  39         public GraphNode getTarget() {
  40             return target;
  41         }
  42
  43         public void setDotNodeParameters(String param) {
  44             if (param == null) {
  45                 throw new NullPointerException();
  46             }
  47             if (param.length() > 0) {
  48                 dotnodeparams = "," + param;
  49             } else {
  50                 dotnodeparams = new String();
  51             }
  52         }
  53
  54     }
  55
  56     int discoverytime = -1;
  57     int finishingtime = -1; /* used for searches */
  58     Vector edges = new Vector();
  59     String nodelabel;
  60     String textlabel;
  61     NodeStatus status = UNVISITED;
  62     String dotnodeparams = new String();
  63     Object owner = null;
  64
  65     public GraphNode(String label) {
  66         this.nodelabel = label;
  67         this.textlabel = label;
  68     }
  69
  70     public GraphNode(String label, Object owner) {
  71         this.nodelabel = label;
  72         this.textlabel = label;
  73         this.owner = owner;
  74     }
  75
  76     public GraphNode(String label, String textlabel, Object owner) {
  77         this.nodelabel = label;
  78         this.textlabel = textlabel;
  79         this.owner = owner;
  80     }
  81
  82     public Object getOwner() {
  83         return owner;
  84     }
  85
  86     public static void computeclosure(Set nodes) {
  87         Stack tovisit=new Stack();
  88         tovisit.addAll(nodes);
  89         while(!tovisit.isEmpty()) {
  90             GraphNode gn=(GraphNode)tovisit.pop();
  91             for(Iterator it=gn.edges();it.hasNext();) {
  92                 Edge edge=(Edge)it.next();
  93                 GraphNode target=edge.getTarget();
  94                 if (!nodes.contains(target)) {
  95                     nodes.add(target);
  96                     tovisit.push(target);
  97                 }
  98             }
  99         }
 100     }
 101
 102     public void setDotNodeParameters(String param) {
 103         if (param == null) {
 104             throw new NullPointerException();
 105         }
 106         if (param.length() > 0) {
 107             dotnodeparams = "," + param;
 108         } else {
 109             dotnodeparams = new String();
 110         }
 111     }
 112
 113     public void setStatus(NodeStatus status) {
 114         if (status == null) {
 115             throw new NullPointerException();
 116         }
 117         this.status = status;
 118     }
 119
 120     public String getLabel() {
 121         return nodelabel;
 122     }
 123
 124     public String getTextLabel() {
 125         return textlabel;
 126     }
 127
 128     public NodeStatus getStatus() {
 129         return this.status;
 130     }
 131
 132     public Iterator edges() {
 133         return edges.iterator();
 134     }
 135
 136     public void addEdge(Edge newedge) {
 137         edges.addElement(newedge);
 138     }
 139
 140     public void reset() {
 141         discoverytime = -1;
 142         finishingtime = -1;
 143         status = UNVISITED;
 144     }
 145
 146     public void discover(int time) {
 147         discoverytime = time;
 148         status = PROCESSING;
 149     }
 150
 151     public void finish(int time) {
 152         assert status == PROCESSING;
 153         finishingtime = time;
 154         status = FINISHED;
 155     }
 156
 157     public int getFinishingTime() {
 158         return finishingtime;
 159     }
 160
 161
 162     public static class DOTVisitor {
 163
 164         java.io.PrintWriter output;
 165         int tokennumber;
 166         int color;
 167
 168         private DOTVisitor(java.io.OutputStream output) {
 169             tokennumber = 0;
 170             color = 0;
 171             this.output = new java.io.PrintWriter(output, true);
 172         }
 173
 174         private String getNewID(String name) {
 175             tokennumber = tokennumber + 1;
 176             return new String (name+tokennumber);
 177         }
 178
 179         Collection nodes;
 180
 181         public static void visit(java.io.OutputStream output, Collection nodes) {
 182             DOTVisitor visitor = new DOTVisitor(output);
 183             visitor.nodes = nodes;
 184             visitor.make();
 185
 186         }
 187
 188         private void make() {
 189             output.println("digraph dotvisitor {");
 190             output.println("\trotate=90;");
 191             /*            output.println("\tpage=\"8.5,11\";");
 192                           output.println("\tnslimit=1000.0;");
 193                           output.println("\tnslimit1=1000.0;");
 194                           output.println("\tmclimit=1000.0;");
 195                           output.println("\tremincross=true;");*/
 196             output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
 197             output.println("\tedge [fontsize=6];");
 198             traverse();
 199             output.println("}\n");
 200         }
 201
 202         private void traverse() {
 203             Set cycleset=GraphNode.findcycles(nodes);
 204
 205             Iterator i = nodes.iterator();
 206             while (i.hasNext()) {
 207                 GraphNode gn = (GraphNode) i.next();
 208                 Iterator edges = gn.edges();
 209                 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
 210                 String option="";
 211                 if (cycleset.contains(gn))
 212                     option=",style=bold";
 213                 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
 214
 215                 while (edges.hasNext()) {
 216                     Edge edge = (Edge) edges.next();
 217                     GraphNode node = edge.getTarget();
 218                     if (nodes.contains(node)) {
 219                         String edgelabel = useEdgeLabels ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
 220                         output.println("\t" + gn.getLabel() + " -> " + node.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
 221                     }
 222                 }
 223             }
 224         }
 225     }
 226
 227     /* XXXXXXXX  Should use SCC algorithm here - will change */
 228     public static Set findcycles(Collection nodes) {
 229         Stack st=new Stack();
 230         HashSet acyclic=new HashSet();
 231         HashSet cycles=new HashSet();
 232         for(Iterator it=nodes.iterator();it.hasNext();) {
 233             GraphNode node=(GraphNode)it.next();
 234             if (acyclic.contains(node))
 235                 continue;
 236             if (cycles.contains(node))
 237                 continue;
 238             findcycles(cycles, acyclic, st,node,nodes);
 239         }
 240         return cycles;
 241     }
 242
 243     private static boolean findcycles(Set cycles, Set acyclic, Stack visited, GraphNode gn, Collection nodes) {
 244         if (visited.contains(gn)) {/* Found cycle */
 245             cycles.addAll(visited.subList(visited.indexOf(gn),visited.size()));  /* Add this cycle */
 246             return true;
 247         }
 248         boolean acyclicflag=true;
 249         visited.push(gn);
 250         for(Iterator it=gn.edges();it.hasNext();) {
 251             Edge e=(Edge) it.next();
 252             GraphNode node = e.getTarget();
 253             if (!nodes.contains(node))
 254                 continue; /* Don't visit stuff outside set */
 255             if (acyclic.contains(node))
 256                 continue;
 257             if (findcycles(cycles,acyclic,visited,node,nodes)) {
 258                 /* Found cycle */
 259                 acyclicflag=false;
 260             }
 261         }
 262         visited.pop();
 263         if (acyclicflag) {
 264             acyclic.add(gn); /* no cycles through gn */
 265             return false;
 266         } else
 267             return true; /* found cycle */
 268     }
 269
 270     /**
 271      * DFS encapsulates the depth first search algorithm
 272      */
 273     public static class DFS {
 274
 275         int time = 0;
 276         Collection nodes;
 277
 278         private DFS(Collection nodes) {
 279             this.nodes = nodes;
 280         }
 281
 282         public static boolean depthFirstSearch(Collection nodes) {
 283             if (nodes == null) {
 284                 throw new NullPointerException();
 285             }
 286
 287             DFS dfs = new DFS(nodes);
 288             return dfs.go();
 289         }
 290
 291         private boolean go() {
 292             Iterator i;
 293             time = 0;
 294             boolean acyclic=true;
 295             i = nodes.iterator();
 296             while (i.hasNext()) {
 297                 GraphNode gn = (GraphNode) i.next();
 298                 gn.reset();
 299             }
 300
 301             i = nodes.iterator();
 302             while (i.hasNext()) {
 303                 GraphNode gn = (GraphNode) i.next();
 304                 assert gn.getStatus() != PROCESSING;
 305                 if (gn.getStatus() == UNVISITED) {
 306                     if (!dfs(gn))
 307                         acyclic=false;
 308                 }
 309             }
 310             return acyclic;
 311         }
 312
 313         private boolean dfs(GraphNode gn) {
 314             boolean acyclic=true;
 315             gn.discover(time++);
 316             Iterator edges = gn.edges();
 317
 318             while (edges.hasNext()) {
 319                 Edge edge = (Edge) edges.next();
 320                 GraphNode node = edge.getTarget();
 321                 if (node.getStatus() == UNVISITED) {
 322                     if (!dfs(node))
 323                         acyclic=false;
 324                 } else if (node.getStatus()==PROCESSING) {
 325                     acyclic=false;
 326                 }
 327             }
 328
 329             gn.finish(time++);
 330             return acyclic;
 331         }
 332
 333     } /* end DFS */
 334
 335 }