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(Collection nodes, Collection removed) {
  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                     if ((removed==null)||
  96                         (!removed.contains(target))) {
  97                         nodes.add(target);
  98                         tovisit.push(target);
  99                     }
 100                 }
 101             }
 102         }
 103     }
 104
 105     public void setDotNodeParameters(String param) {
 106         if (param == null) {
 107             throw new NullPointerException();
 108         }
 109         if (param.length() > 0) {
 110             dotnodeparams = "," + param;
 111         } else {
 112             dotnodeparams = new String();
 113         }
 114     }
 115
 116     public void setStatus(NodeStatus status) {
 117         if (status == null) {
 118             throw new NullPointerException();
 119         }
 120         this.status = status;
 121     }
 122
 123     public String getLabel() {
 124         return nodelabel;
 125     }
 126
 127     public String getTextLabel() {
 128         return textlabel;
 129     }
 130
 131     public NodeStatus getStatus() {
 132         return this.status;
 133     }
 134
 135     public Iterator edges() {
 136         return edges.iterator();
 137     }
 138
 139     public void addEdge(Edge newedge) {
 140         edges.addElement(newedge);
 141     }
 142
 143     public void reset() {
 144         discoverytime = -1;
 145         finishingtime = -1;
 146         status = UNVISITED;
 147     }
 148
 149     public void discover(int time) {
 150         discoverytime = time;
 151         status = PROCESSING;
 152     }
 153
 154     public void finish(int time) {
 155         assert status == PROCESSING;
 156         finishingtime = time;
 157         status = FINISHED;
 158     }
 159
 160     public int getFinishingTime() {
 161         return finishingtime;
 162     }
 163
 164
 165     public static class DOTVisitor {
 166
 167         java.io.PrintWriter output;
 168         int tokennumber;
 169         int color;
 170
 171         private DOTVisitor(java.io.OutputStream output) {
 172             tokennumber = 0;
 173             color = 0;
 174             this.output = new java.io.PrintWriter(output, true);
 175         }
 176
 177         private String getNewID(String name) {
 178             tokennumber = tokennumber + 1;
 179             return new String (name+tokennumber);
 180         }
 181
 182         Collection nodes;
 183
 184         public static void visit(java.io.OutputStream output, Collection nodes) {
 185             DOTVisitor visitor = new DOTVisitor(output);
 186             visitor.nodes = nodes;
 187             visitor.make();
 188
 189         }
 190
 191         private void make() {
 192             output.println("digraph dotvisitor {");
 193             output.println("\trotate=90;");
 194             /*            output.println("\tpage=\"8.5,11\";");
 195                           output.println("\tnslimit=1000.0;");
 196                           output.println("\tnslimit1=1000.0;");
 197                           output.println("\tmclimit=1000.0;");
 198                           output.println("\tremincross=true;");*/
 199             output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
 200             output.println("\tedge [fontsize=6];");
 201             traverse();
 202             output.println("}\n");
 203         }
 204
 205         private void traverse() {
 206             Set cycleset=GraphNode.findcycles(nodes);
 207
 208             Iterator i = nodes.iterator();
 209             while (i.hasNext()) {
 210                 GraphNode gn = (GraphNode) i.next();
 211                 Iterator edges = gn.edges();
 212                 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
 213                 String option="";
 214                 if (cycleset.contains(gn))
 215                     option=",style=bold";
 216                 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
 217
 218                 while (edges.hasNext()) {
 219                     Edge edge = (Edge) edges.next();
 220                     GraphNode node = edge.getTarget();
 221                     if (nodes.contains(node)) {
 222                         String edgelabel = useEdgeLabels ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
 223                         output.println("\t" + gn.getLabel() + " -> " + node.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
 224                     }
 225                 }
 226             }
 227         }
 228     }
 229
 230     /* XXXXXXXX  Should use SCC algorithm here - will change */
 231     public static Set findcycles(Collection nodes) {
 232         Stack st=new Stack();
 233         HashSet acyclic=new HashSet();
 234         HashSet cycles=new HashSet();
 235         for(Iterator it=nodes.iterator();it.hasNext();) {
 236             GraphNode node=(GraphNode)it.next();
 237             if (acyclic.contains(node))
 238                 continue;
 239             if (cycles.contains(node))
 240                 continue;
 241             findcycles(cycles, acyclic, st,node,nodes);
 242         }
 243         return cycles;
 244     }
 245
 246     private static boolean findcycles(Set cycles, Set acyclic, Stack visited, GraphNode gn, Collection nodes) {
 247         if (visited.contains(gn)) {/* Found cycle */
 248             cycles.addAll(visited.subList(visited.indexOf(gn),visited.size()));  /* Add this cycle */
 249             return true;
 250         }
 251         boolean acyclicflag=true;
 252         visited.push(gn);
 253         for(Iterator it=gn.edges();it.hasNext();) {
 254             Edge e=(Edge) it.next();
 255             GraphNode node = e.getTarget();
 256             if (!nodes.contains(node))
 257                 continue; /* Don't visit stuff outside set */
 258             if (acyclic.contains(node))
 259                 continue;
 260             if (findcycles(cycles,acyclic,visited,node,nodes)) {
 261                 /* Found cycle */
 262                 acyclicflag=false;
 263             }
 264         }
 265         visited.pop();
 266         if (acyclicflag) {
 267             acyclic.add(gn); /* no cycles through gn */
 268             return false;
 269         } else
 270             return true; /* found cycle */
 271     }
 272
 273     /**
 274      * DFS encapsulates the depth first search algorithm
 275      */
 276     public static class DFS {
 277
 278         int time = 0;
 279         Collection nodes;
 280
 281         private DFS(Collection nodes) {
 282             this.nodes = nodes;
 283         }
 284
 285         public static boolean depthFirstSearch(Collection nodes) {
 286             if (nodes == null) {
 287                 throw new NullPointerException();
 288             }
 289
 290             DFS dfs = new DFS(nodes);
 291             return dfs.go();
 292         }
 293
 294         private boolean go() {
 295             Iterator i;
 296             time = 0;
 297             boolean acyclic=true;
 298             i = nodes.iterator();
 299             while (i.hasNext()) {
 300                 GraphNode gn = (GraphNode) i.next();
 301                 gn.reset();
 302             }
 303
 304             i = nodes.iterator();
 305             while (i.hasNext()) {
 306                 GraphNode gn = (GraphNode) i.next();
 307                 assert gn.getStatus() != PROCESSING;
 308                 if (gn.getStatus() == UNVISITED) {
 309                     if (!dfs(gn))
 310                         acyclic=false;
 311                 }
 312             }
 313             return acyclic;
 314         }
 315
 316         private boolean dfs(GraphNode gn) {
 317             boolean acyclic=true;
 318             gn.discover(time++);
 319             Iterator edges = gn.edges();
 320
 321             while (edges.hasNext()) {
 322                 Edge edge = (Edge) edges.next();
 323                 GraphNode node = edge.getTarget();
 324                 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
 325                     continue;
 326                 if (node.getStatus() == UNVISITED) {
 327                     if (!dfs(node))
 328                         acyclic=false;
 329                 } else if (node.getStatus()==PROCESSING) {
 330                     acyclic=false;
 331                 }
 332             }
 333
 334             gn.finish(time++);
 335             return acyclic;
 336         }
 337
 338     } /* end DFS */
 339
 340 }