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 void setDotNodeParameters(String param) {
  87         if (param == null) {
  88             throw new NullPointerException();
  89         }
  90         if (param.length() > 0) {
  91             dotnodeparams = "," + param;
  92         } else {
  93             dotnodeparams = new String();
  94         }
  95     }
  96
  97     public void setStatus(NodeStatus status) {
  98         if (status == null) {
  99             throw new NullPointerException();
 100         }
 101         this.status = status;
 102     }
 103
 104     public String getLabel() {
 105         return nodelabel;
 106     }
 107
 108     public String getTextLabel() {
 109         return textlabel;
 110     }
 111
 112     public NodeStatus getStatus() {
 113         return this.status;
 114     }
 115
 116     public Iterator edges() {
 117         return edges.iterator();
 118     }
 119
 120     public void addEdge(Edge newedge) {
 121         edges.addElement(newedge);
 122     }
 123
 124     public void reset() {
 125         discoverytime = -1;
 126         finishingtime = -1;
 127         status = UNVISITED;
 128     }
 129
 130     public void discover(int time) {
 131         discoverytime = time++;
 132         status = PROCESSING;
 133     }
 134
 135     public void finish(int time) {
 136         assert status == PROCESSING;
 137         finishingtime = time++;
 138         status = FINISHED;
 139     }
 140
 141     public int getFinishingTime() {
 142         return finishingtime;
 143     }
 144
 145     public static class DOTVisitor {
 146
 147         java.io.PrintWriter output;
 148         int tokennumber;
 149         int color;
 150
 151         private DOTVisitor(java.io.OutputStream output) {
 152             tokennumber = 0;
 153             color = 0;
 154             this.output = new java.io.PrintWriter(output, true);
 155         }
 156
 157         private String getNewID(String name) {
 158             tokennumber = tokennumber + 1;
 159             return new String (name+tokennumber);
 160         }
 161
 162         Collection nodes;
 163
 164         public static void visit(java.io.OutputStream output, Collection nodes) {
 165             DOTVisitor visitor = new DOTVisitor(output);
 166             visitor.nodes = nodes;
 167             visitor.make();
 168
 169         }
 170
 171         private void make() {
 172             output.println("digraph dotvisitor {");
 173             output.println("\trotate=90;");
 174             output.println("\tpage=\"8.5,11\";");
 175             output.println("\tnslimit=1000.0;");
 176             output.println("\tnslimit1=1000.0;");
 177             output.println("\tmclimit=1000.0;");
 178             output.println("\tremincross=true;");
 179             output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
 180             output.println("\tedge [fontsize=6];");
 181
 182             traverse();
 183
 184             output.println("}\n");
 185         }
 186
 187         private void traverse() {
 188             Iterator i = nodes.iterator();
 189             while (i.hasNext()) {
 190                 GraphNode gn = (GraphNode) i.next();
 191                 Iterator edges = gn.edges();
 192                 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
 193                 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + "];");
 194
 195                 while (edges.hasNext()) {
 196                     Edge edge = (Edge) edges.next();
 197                     GraphNode node = edge.getTarget();
 198                     String edgelabel = useEdgeLabels ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
 199                     output.println("\t" + gn.getLabel() + " -> " + node.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
 200                 }
 201             }
 202         }
 203     }
 204
 205     /**
 206      * DFS encapsulates the depth first search algorithm
 207      */
 208     public static class DFS {
 209
 210         int time = 0;
 211         Collection nodes;
 212
 213         private DFS(Collection nodes) {
 214             this.nodes = nodes;
 215         }
 216
 217         public static void depthFirstSearch(Collection nodes) {
 218             if (nodes == null) {
 219                 throw new NullPointerException();
 220             }
 221
 222             DFS dfs = new DFS(nodes);
 223             dfs.go();
 224         }
 225
 226         private void go() {
 227             Iterator i;
 228             time = 0;
 229
 230             i = nodes.iterator();
 231             while (i.hasNext()) {
 232                 GraphNode gn = (GraphNode) i.next();
 233                 gn.reset();
 234             }
 235
 236             i = nodes.iterator();
 237             while (i.hasNext()) {
 238                 GraphNode gn = (GraphNode) i.next();
 239                 assert gn.getStatus() != PROCESSING;
 240                 if (gn.getStatus() == UNVISITED) {
 241                     dfs(gn);
 242                 }
 243             }
 244         }
 245
 246         private void dfs(GraphNode gn) {
 247             gn.discover(time++);
 248             Iterator edges = gn.edges();
 249
 250             while (edges.hasNext()) {
 251                 Edge edge = (Edge) edges.next();
 252                 GraphNode node = edge.getTarget();
 253                 if (node.getStatus() == UNVISITED) {
 254                     dfs(node);
 255                 }
 256             }
 257
 258             gn.finish(time++);
 259         }
 260
 261     } /* end DFS */
 262
 263 }