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 GraphNode source;
  29         private String dotnodeparams = new String();
  30
  31         public Edge(String label, GraphNode target) {
  32             this.label = label;
  33             this.target = target;
  34         }
  35
  36         public String getLabel() {
  37             return label;
  38         }
  39
  40         public void setSource(GraphNode s) {
  41             this.source=s;
  42         }
  43
  44         public GraphNode getSource() {
  45             return source;
  46         }
  47
  48         public GraphNode getTarget() {
  49             return target;
  50         }
  51
  52         public void setDotNodeParameters(String param) {
  53             if (param == null) {
  54                 throw new NullPointerException();
  55             }
  56             if (param.length() > 0) {
  57                 dotnodeparams = "," + param;
  58             } else {
  59                 dotnodeparams = new String();
  60             }
  61         }
  62
  63     }
  64
  65     int discoverytime = -1;
  66     int finishingtime = -1; /* used for searches */
  67     int scc = -1;
  68
  69     Vector edges = new Vector();
  70     Vector inedges = new Vector();
  71     String nodelabel;
  72     String textlabel;
  73     NodeStatus status = UNVISITED;
  74     String dotnodeparams = new String();
  75     Object owner = null;
  76
  77     public GraphNode(String label) {
  78         this.nodelabel = label;
  79         this.textlabel = label;
  80     }
  81
  82     public GraphNode(String label, Object owner) {
  83         this.nodelabel = label;
  84         this.textlabel = label;
  85         this.owner = owner;
  86     }
  87
  88     public GraphNode(String label, String textlabel, Object owner) {
  89         this.nodelabel = label;
  90         this.textlabel = textlabel;
  91         this.owner = owner;
  92     }
  93
  94     public Object getOwner() {
  95         return owner;
  96     }
  97
  98     public static void computeclosure(Collection nodes, Collection removed) {
  99         Stack tovisit=new Stack();
 100         tovisit.addAll(nodes);
 101         while(!tovisit.isEmpty()) {
 102             GraphNode gn=(GraphNode)tovisit.pop();
 103             for(Iterator it=gn.edges();it.hasNext();) {
 104                 Edge edge=(Edge)it.next();
 105                 GraphNode target=edge.getTarget();
 106                 if (!nodes.contains(target)) {
 107                     if ((removed==null)||
 108                         (!removed.contains(target))) {
 109                         nodes.add(target);
 110                         tovisit.push(target);
 111                     }
 112                 }
 113             }
 114         }
 115     }
 116
 117     public void setDotNodeParameters(String param) {
 118         if (param == null) {
 119             throw new NullPointerException();
 120         }
 121         if (param.length() > 0) {
 122             dotnodeparams = "," + param;
 123         } else {
 124             dotnodeparams = new String();
 125         }
 126     }
 127
 128     public void setStatus(NodeStatus status) {
 129         if (status == null) {
 130             throw new NullPointerException();
 131         }
 132         this.status = status;
 133     }
 134
 135     public String getLabel() {
 136         return nodelabel;
 137     }
 138
 139     public String getTextLabel() {
 140         return textlabel;
 141     }
 142
 143     public NodeStatus getStatus() {
 144         return this.status;
 145     }
 146
 147     public Iterator edges() {
 148         return edges.iterator();
 149     }
 150
 151     public Iterator inedges() {
 152         return inedges.iterator();
 153     }
 154
 155     public void addEdge(Edge newedge) {
 156         newedge.setSource(this);
 157         edges.addElement(newedge);
 158         GraphNode tonode=newedge.getTarget();
 159         tonode.inedges.addElement(newedge);
 160     }
 161
 162     void reset() {
 163             discoverytime = -1;
 164             finishingtime = -1;
 165             status = UNVISITED;
 166     }
 167
 168     void resetscc() {
 169         status = UNVISITED;
 170         scc = -1;
 171     }
 172
 173     public int getSCC() {
 174         return scc;
 175     }
 176
 177     void setSCC(int s) {
 178         scc=s;
 179     }
 180
 181     void discover(int time) {
 182         discoverytime = time;
 183         status = PROCESSING;
 184     }
 185
 186     void finish(int time) {
 187         assert status == PROCESSING;
 188         finishingtime = time;
 189         status = FINISHED;
 190     }
 191
 192     /** Returns finishing time for dfs */
 193
 194     public int getFinishingTime() {
 195         return finishingtime;
 196     }
 197
 198
 199     public static class DOTVisitor {
 200
 201         java.io.PrintWriter output;
 202         int tokennumber;
 203         int color;
 204
 205         private DOTVisitor(java.io.OutputStream output) {
 206             tokennumber = 0;
 207             color = 0;
 208             this.output = new java.io.PrintWriter(output, true);
 209         }
 210
 211         private String getNewID(String name) {
 212             tokennumber = tokennumber + 1;
 213             return new String (name+tokennumber);
 214         }
 215
 216         Collection nodes;
 217
 218         public static void visit(java.io.OutputStream output, Collection nodes) {
 219             DOTVisitor visitor = new DOTVisitor(output);
 220             visitor.nodes = nodes;
 221             visitor.make();
 222
 223         }
 224
 225         private void make() {
 226             output.println("digraph dotvisitor {");
 227             output.println("\trotate=90;");
 228             /*            output.println("\tpage=\"8.5,11\";");
 229                           output.println("\tnslimit=1000.0;");
 230                           output.println("\tnslimit1=1000.0;");
 231                           output.println("\tmclimit=1000.0;");
 232                           output.println("\tremincross=true;");*/
 233             output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
 234             output.println("\tedge [fontsize=6];");
 235             traverse();
 236             output.println("}\n");
 237         }
 238
 239         private void traverse() {
 240             Set cycleset=GraphNode.findcycles(nodes);
 241
 242             Iterator i = nodes.iterator();
 243             while (i.hasNext()) {
 244                 GraphNode gn = (GraphNode) i.next();
 245                 Iterator edges = gn.edges();
 246                 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
 247                 String option="";
 248                 if (cycleset.contains(gn))
 249                     option=",style=bold";
 250                 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
 251
 252                 while (edges.hasNext()) {
 253                     Edge edge = (Edge) edges.next();
 254                     GraphNode node = edge.getTarget();
 255                     if (nodes.contains(node)) {
 256                         String edgelabel = useEdgeLabels ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
 257                         output.println("\t" + gn.getLabel() + " -> " + node.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
 258                     }
 259                 }
 260             }
 261         }
 262     }
 263
 264     /* XXXXXXXX  Should use SCC algorithm here - will change */
 265     public static Set findcycles(Collection nodes) {
 266         Stack st=new Stack();
 267         HashSet acyclic=new HashSet();
 268         HashSet cycles=new HashSet();
 269         for(Iterator it=nodes.iterator();it.hasNext();) {
 270             GraphNode node=(GraphNode)it.next();
 271             if (acyclic.contains(node))
 272                 continue;
 273             if (cycles.contains(node))
 274                 continue;
 275             findcycles(cycles, acyclic, st,node,nodes);
 276         }
 277         return cycles;
 278     }
 279
 280     private static boolean findcycles(Set cycles, Set acyclic, Stack visited, GraphNode gn, Collection nodes) {
 281         if (visited.contains(gn)) {/* Found cycle */
 282             cycles.addAll(visited.subList(visited.indexOf(gn),visited.size()));  /* Add this cycle */
 283             return true;
 284         }
 285         boolean acyclicflag=true;
 286         visited.push(gn);
 287         for(Iterator it=gn.edges();it.hasNext();) {
 288             Edge e=(Edge) it.next();
 289             GraphNode node = e.getTarget();
 290             if (!nodes.contains(node))
 291                 continue; /* Don't visit stuff outside set */
 292             if (acyclic.contains(node))
 293                 continue;
 294             if (findcycles(cycles,acyclic,visited,node,nodes)) {
 295                 /* Found cycle */
 296                 acyclicflag=false;
 297             }
 298         }
 299         visited.pop();
 300         if (acyclicflag) {
 301             acyclic.add(gn); /* no cycles through gn */
 302             return false;
 303         } else
 304             return true; /* found cycle */
 305     }
 306
 307     public static class SCC {
 308         boolean hascycles;
 309         HashMap map;
 310         int numscc;
 311         public SCC(boolean hascycles, HashMap map,int numscc) {
 312             this.hascycles=hascycles;
 313             this.map=map;
 314             this.numscc=numscc;
 315         }
 316
 317         public boolean hasCycles() {
 318             return hascycles;
 319         }
 320
 321         public int numSCC() {
 322             return numscc;
 323         }
 324
 325         public Set getSCC(int i) {
 326             Integer scc=new Integer(i);
 327             return (Set)map.get(scc);
 328         }
 329
 330         boolean hascycle(int i) {
 331             Integer scc=new Integer(i);
 332             Set s=(Set)map.get(scc);
 333             if (s.size()>1)
 334                 return true;
 335             Object [] array=s.toArray();
 336             GraphNode gn=(GraphNode)array[0];
 337             for(Iterator it=gn.edges();it.hasNext();) {
 338                 Edge e=(Edge)it.next();
 339                 if (e.getTarget()==gn)
 340                     return true; /* Self Cycle */
 341             }
 342             return false;
 343         }
 344     }
 345
 346     /**
 347      * DFS encapsulates the depth first search algorithm
 348      */
 349     public static class DFS {
 350
 351         int time = 0;
 352         int sccindex = 0;
 353         Collection nodes;
 354         Vector finishingorder=null;
 355         HashMap sccmap;
 356
 357         private DFS(Collection nodes) {
 358             this.nodes = nodes;
 359         }
 360
 361         public static SCC computeSCC(Collection nodes) {
 362             if (nodes==null) {
 363                 throw new NullPointerException();
 364             }
 365             DFS dfs=new DFS(nodes);
 366             dfs.sccmap=new HashMap();
 367             dfs.finishingorder=new Vector();
 368             boolean hascycles=dfs.go();
 369             for (Iterator it = nodes.iterator();it.hasNext();) {
 370                 GraphNode gn = (GraphNode) it.next();
 371                 gn.resetscc();
 372             }
 373             for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
 374                 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
 375                 if (gn.getStatus() == UNVISITED) {
 376                     dfs.dfsprev(gn);
 377                     dfs.sccindex++; /* Increment scc index */
 378                 }
 379             }
 380             return new SCC(hascycles,dfs.sccmap,dfs.sccindex);
 381         }
 382
 383         void dfsprev(GraphNode gn) {
 384             if (gn.getStatus()==FINISHED||!nodes.contains(gn))
 385                 return;
 386             gn.setStatus(FINISHED);
 387             gn.setSCC(sccindex);
 388             Integer i=new Integer(sccindex);
 389             if (!sccmap.containsKey(i))
 390                 sccmap.put(i,new HashSet());
 391             ((Set)sccmap.get(i)).add(gn);
 392             for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
 393                 Edge e=(Edge)edgeit.next();
 394                 GraphNode gn2=e.getSource();
 395                 dfsprev(gn2);
 396             }
 397         }
 398
 399         public static boolean depthFirstSearch(Collection nodes) {
 400             if (nodes == null) {
 401                 throw new NullPointerException();
 402             }
 403
 404             DFS dfs = new DFS(nodes);
 405             return dfs.go();
 406         }
 407
 408         private boolean go() {
 409             Iterator i;
 410             time = 0;
 411             boolean acyclic=true;
 412             i = nodes.iterator();
 413             while (i.hasNext()) {
 414                 GraphNode gn = (GraphNode) i.next();
 415                 gn.reset();
 416             }
 417
 418             i = nodes.iterator();
 419             while (i.hasNext()) {
 420                 GraphNode gn = (GraphNode) i.next();
 421                 assert gn.getStatus() != PROCESSING;
 422                 if (gn.getStatus() == UNVISITED) {
 423                     if (!dfs(gn))
 424                         acyclic=false;
 425                 }
 426             }
 427             return acyclic;
 428         }
 429
 430         private boolean dfs(GraphNode gn) {
 431             boolean acyclic=true;
 432             gn.discover(time++);
 433             Iterator edges = gn.edges();
 434
 435             while (edges.hasNext()) {
 436                 Edge edge = (Edge) edges.next();
 437                 GraphNode node = edge.getTarget();
 438                 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
 439                     continue;
 440                 if (node.getStatus() == UNVISITED) {
 441                     if (!dfs(node))
 442                         acyclic=false;
 443                 } else if (node.getStatus()==PROCESSING) {
 444                     acyclic=false;
 445                 }
 446             }
 447             if (finishingorder!=null)
 448                 finishingorder.add(gn);
 449             gn.finish(time++);
 450             return acyclic;
 451         }
 452
 453     } /* end DFS */
 454
 455 }