Repair/RepairCompiler/MCC/IR/GraphNode.java

   1 package MCC.IR;
   2
   3 import java.util.*;
   4 import java.io.*;
   5 import MCC.Compiler;
   6
   7 public class GraphNode {
   8
   9     /* NodeStatus enumeration pattern ***********/
  10
  11     public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED");
  12     public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING");
  13     public static final NodeStatus FINISHED = new NodeStatus("FINISHED");
  14
  15     public static class NodeStatus {
  16         private static String name;
  17         private NodeStatus(String name) { this.name = name; }
  18         public String toString() { return name; }
  19     }
  20
  21     /* Edge *****************/
  22
  23     public static class Edge {
  24
  25         private String label;
  26         private GraphNode target;
  27         private GraphNode source;
  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 void setSource(GraphNode s) {
  40             this.source=s;
  41         }
  42
  43         public GraphNode getSource() {
  44             return source;
  45         }
  46
  47         public GraphNode getTarget() {
  48             return target;
  49         }
  50
  51         public void setDotNodeParameters(String param) {
  52             if (param == null) {
  53                 throw new NullPointerException();
  54             }
  55             if (param.length() > 0) {
  56                 dotnodeparams = "," + param;
  57             } else {
  58                 dotnodeparams = new String();
  59             }
  60         }
  61
  62     }
  63
  64     int discoverytime = -1;
  65     int finishingtime = -1; /* used for searches */
  66
  67     Vector edges = new Vector();
  68     Vector inedges = new Vector();
  69     String nodelabel;
  70     String textlabel;
  71     NodeStatus status = UNVISITED;
  72     String dotnodeparams = new String();
  73     Object owner = null;
  74     boolean merge=false;
  75     String nodeoption="";
  76
  77     public void setOption(String option) {
  78         this.nodeoption=option;
  79     }
  80
  81     public void setMerge() {
  82         merge=true;
  83     }
  84
  85     public GraphNode(String label) {
  86         this.nodelabel = label;
  87         this.textlabel = label;
  88     }
  89
  90     public GraphNode(String label, Object owner) {
  91         this.nodelabel = label;
  92         this.textlabel = label;
  93         this.owner = owner;
  94     }
  95
  96     public GraphNode(String label, String textlabel, Object owner) {
  97         this.nodelabel = label;
  98         this.textlabel = textlabel;
  99         this.owner = owner;
 100     }
 101
 102     public Object getOwner() {
 103         return owner;
 104     }
 105
 106     public static void computeclosure(Collection nodes, Collection removed) {
 107         Stack tovisit=new Stack();
 108         tovisit.addAll(nodes);
 109         while(!tovisit.isEmpty()) {
 110             GraphNode gn=(GraphNode)tovisit.pop();
 111             for(Iterator it=gn.edges();it.hasNext();) {
 112                 Edge edge=(Edge)it.next();
 113                 GraphNode target=edge.getTarget();
 114                 if (!nodes.contains(target)) {
 115                     if ((removed==null)||
 116                         (!removed.contains(target))) {
 117                         nodes.add(target);
 118                         tovisit.push(target);
 119                     }
 120                 }
 121             }
 122         }
 123     }
 124
 125     public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
 126         Stack tovisit=new Stack();
 127         Stack newvisit=new Stack();
 128         tovisit.addAll(nodes);
 129         for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
 130             while(!tovisit.isEmpty()) {
 131                 GraphNode gn=(GraphNode)tovisit.pop();
 132                 for(Iterator it=gn.edges();it.hasNext();) {
 133                     Edge edge=(Edge)it.next();
 134                     GraphNode target=edge.getTarget();
 135                     if (!nodes.contains(target)) {
 136                         if ((removed==null)||
 137                             (!removed.contains(target))) {
 138                             nodes.add(target);
 139                             newvisit.push(target);
 140                         }
 141                     }
 142                 }
 143             }
 144             tovisit=newvisit;
 145             newvisit=new Stack();
 146         }
 147     }
 148
 149     public void setDotNodeParameters(String param) {
 150         if (param == null) {
 151             throw new NullPointerException();
 152         }
 153         if (param.length() > 0) {
 154             dotnodeparams = "," + param;
 155         } else {
 156             dotnodeparams = new String();
 157         }
 158     }
 159
 160     public void setStatus(NodeStatus status) {
 161         if (status == null) {
 162             throw new NullPointerException();
 163         }
 164         this.status = status;
 165     }
 166
 167     public String getLabel() {
 168         return nodelabel;
 169     }
 170
 171     public String getTextLabel() {
 172         return textlabel;
 173     }
 174
 175     public NodeStatus getStatus() {
 176         return this.status;
 177     }
 178
 179     public Iterator edges() {
 180         return edges.iterator();
 181     }
 182
 183     public Iterator inedges() {
 184         return inedges.iterator();
 185     }
 186
 187     public void addEdge(Edge newedge) {
 188         newedge.setSource(this);
 189         edges.addElement(newedge);
 190         GraphNode tonode=newedge.getTarget();
 191         tonode.inedges.addElement(newedge);
 192     }
 193
 194     void reset() {
 195             discoverytime = -1;
 196             finishingtime = -1;
 197             status = UNVISITED;
 198     }
 199
 200     void resetscc() {
 201         status = UNVISITED;
 202     }
 203
 204     void discover(int time) {
 205         discoverytime = time;
 206         status = PROCESSING;
 207     }
 208
 209     void finish(int time) {
 210         assert status == PROCESSING;
 211         finishingtime = time;
 212         status = FINISHED;
 213     }
 214
 215     /** Returns finishing time for dfs */
 216
 217     public int getFinishingTime() {
 218         return finishingtime;
 219     }
 220
 221
 222     public static class DOTVisitor {
 223
 224         java.io.PrintWriter output;
 225         int tokennumber;
 226         int color;
 227
 228         private DOTVisitor(java.io.OutputStream output) {
 229             tokennumber = 0;
 230             color = 0;
 231             this.output = new java.io.PrintWriter(output, true);
 232         }
 233
 234         private String getNewID(String name) {
 235             tokennumber = tokennumber + 1;
 236             return new String (name+tokennumber);
 237         }
 238
 239         Collection nodes;
 240         Collection special;
 241
 242         public static void visit(java.io.OutputStream output, Collection nodes) {
 243             visit(output,nodes,null);
 244         }
 245
 246         public static void visit(java.io.OutputStream output, Collection nodes, Collection special) {
 247             DOTVisitor visitor = new DOTVisitor(output);
 248             visitor.special=special;
 249             visitor.nodes = nodes;
 250             visitor.make();
 251         }
 252
 253         private void make() {
 254             output.println("digraph dotvisitor {");
 255             output.println("\trotate=90;");
 256             /*            output.println("\tpage=\"8.5,11\";");
 257                           output.println("\tnslimit=1000.0;");
 258                           output.println("\tnslimit1=1000.0;");
 259                           output.println("\tmclimit=1000.0;");
 260                           output.println("\tremincross=true;");*/
 261             output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
 262             output.println("\tedge [fontsize=6];");
 263             traverse();
 264             output.println("}\n");
 265         }
 266
 267         private void traverse() {
 268             Set cycleset=GraphNode.findcycles(nodes);
 269
 270             Iterator i = nodes.iterator();
 271             while (i.hasNext()) {
 272                 GraphNode gn = (GraphNode) i.next();
 273                 Iterator edges = gn.edges();
 274                 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
 275                 String option=gn.nodeoption;
 276                 if (special!=null&&special.contains(gn))
 277                     option+=",shape=box";
 278                 if (!gn.merge)
 279                     output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
 280
 281                 if (!gn.merge)
 282                 while (edges.hasNext()) {
 283                     Edge edge = (Edge) edges.next();
 284                     GraphNode node = edge.getTarget();
 285                     if (nodes.contains(node)) {
 286                         for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
 287                             GraphNode node2=(GraphNode)nodeit.next();
 288                             String edgelabel = Compiler.DEBUGGRAPH ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
 289                             output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
 290                         }
 291                     }
 292                 }
 293             }
 294         }
 295
 296         Set nonmerge(GraphNode gn) {
 297             HashSet newset=new HashSet();
 298             HashSet toprocess=new HashSet();
 299             toprocess.add(gn);
 300             while(!toprocess.isEmpty()) {
 301                 GraphNode gn2=(GraphNode)toprocess.iterator().next();
 302                 toprocess.remove(gn2);
 303                 if (!gn2.merge)
 304                     newset.add(gn2);
 305                 else {
 306                     Iterator edges = gn2.edges();
 307                     while (edges.hasNext()) {
 308                         Edge edge = (Edge) edges.next();
 309                         GraphNode node = edge.getTarget();
 310                         if (!newset.contains(node)&&nodes.contains(node))
 311                             toprocess.add(node);
 312                     }
 313                 }
 314             }
 315             return newset;
 316         }
 317
 318     }
 319
 320     /** This function returns the set of nodes involved in cycles.
 321      *  It only considers cycles containing nodes in the set 'nodes'.
 322     */
 323     public static Set findcycles(Collection nodes) {
 324         HashSet cycleset=new HashSet();
 325         SCC scc=DFS.computeSCC(nodes);
 326         if (!scc.hasCycles())
 327             return cycleset;
 328         for(int i=0;i<scc.numSCC();i++) {
 329             if (scc.hasCycle(i))
 330                 cycleset.addAll(scc.getSCC(i));
 331         }
 332         return cycleset;
 333     }
 334
 335     public static class SCC {
 336         boolean acyclic;
 337         HashMap map,revmap;
 338         int numscc;
 339         public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
 340             this.acyclic=acyclic;
 341             this.map=map;
 342             this.revmap=revmap;
 343             this.numscc=numscc;
 344         }
 345
 346         /** Returns whether the graph has any cycles */
 347         public boolean hasCycles() {
 348             return !acyclic;
 349         }
 350
 351         /** Returns the number of Strongly Connected Components */
 352         public int numSCC() {
 353             return numscc;
 354         }
 355
 356         /** Returns the strongly connected component number for the GraphNode gn*/
 357         public int getComponent(GraphNode gn) {
 358             return ((Integer)revmap.get(gn)).intValue();
 359         }
 360
 361         /** Returns the set of nodes in the strongly connected component i*/
 362         public Set getSCC(int i) {
 363             Integer scc=new Integer(i);
 364             return (Set)map.get(scc);
 365         }
 366
 367         /** Returns whether the strongly connected component i contains a cycle */
 368         boolean hasCycle(int i) {
 369             Integer scc=new Integer(i);
 370             Set s=(Set)map.get(scc);
 371             if (s.size()>1)
 372                 return true;
 373             Object [] array=s.toArray();
 374             GraphNode gn=(GraphNode)array[0];
 375             for(Iterator it=gn.edges();it.hasNext();) {
 376                 Edge e=(Edge)it.next();
 377                 if (e.getTarget()==gn)
 378                     return true; /* Self Cycle */
 379             }
 380             return false;
 381         }
 382     }
 383
 384     /**
 385      * DFS encapsulates the depth first search algorithm
 386      */
 387     public static class DFS {
 388
 389         int time = 0;
 390         int sccindex = 0;
 391         Collection nodes;
 392         Vector finishingorder=null;
 393         HashMap sccmap;
 394         HashMap sccmaprev;
 395
 396         private DFS(Collection nodes) {
 397             this.nodes = nodes;
 398         }
 399         /** Calculates the strong connected components for the graph composed
 400          *  of the set of nodes 'nodes'*/
 401         public static SCC computeSCC(Collection nodes) {
 402             if (nodes==null) {
 403                 throw new NullPointerException();
 404             }
 405             DFS dfs=new DFS(nodes);
 406             dfs.sccmap=new HashMap();
 407             dfs.sccmaprev=new HashMap();
 408             dfs.finishingorder=new Vector();
 409             boolean acyclic=dfs.go();
 410             for (Iterator it = nodes.iterator();it.hasNext();) {
 411                 GraphNode gn = (GraphNode) it.next();
 412                 gn.resetscc();
 413             }
 414             for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
 415                 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
 416                 if (gn.getStatus() == UNVISITED) {
 417                     dfs.dfsprev(gn);
 418                     dfs.sccindex++; /* Increment scc index */
 419                 }
 420             }
 421             return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
 422         }
 423
 424         void dfsprev(GraphNode gn) {
 425             if (gn.getStatus()==FINISHED||!nodes.contains(gn))
 426                 return;
 427             gn.setStatus(FINISHED);
 428             Integer i=new Integer(sccindex);
 429             if (!sccmap.containsKey(i))
 430                 sccmap.put(i,new HashSet());
 431             ((Set)sccmap.get(i)).add(gn);
 432             sccmaprev.put(gn,i);
 433             for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
 434                 Edge e=(Edge)edgeit.next();
 435                 GraphNode gn2=e.getSource();
 436                 dfsprev(gn2);
 437             }
 438         }
 439
 440         public static boolean depthFirstSearch(Collection nodes) {
 441             if (nodes == null) {
 442                 throw new NullPointerException();
 443             }
 444
 445             DFS dfs = new DFS(nodes);
 446             return dfs.go();
 447         }
 448
 449         private boolean go() {
 450             Iterator i;
 451             time = 0;
 452             boolean acyclic=true;
 453             i = nodes.iterator();
 454             while (i.hasNext()) {
 455                 GraphNode gn = (GraphNode) i.next();
 456                 gn.reset();
 457             }
 458
 459             i = nodes.iterator();
 460             while (i.hasNext()) {
 461                 GraphNode gn = (GraphNode) i.next();
 462                 assert gn.getStatus() != PROCESSING;
 463                 if (gn.getStatus() == UNVISITED) {
 464                     if (!dfs(gn))
 465                         acyclic=false;
 466                 }
 467             }
 468             return acyclic;
 469         }
 470
 471         private boolean dfs(GraphNode gn) {
 472             boolean acyclic=true;
 473             gn.discover(time++);
 474             Iterator edges = gn.edges();
 475
 476             while (edges.hasNext()) {
 477                 Edge edge = (Edge) edges.next();
 478                 GraphNode node = edge.getTarget();
 479                 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
 480                     continue;
 481                 if (node.getStatus() == UNVISITED) {
 482                     if (!dfs(node))
 483                         acyclic=false;
 484                 } else if (node.getStatus()==PROCESSING) {
 485                     acyclic=false;
 486                 }
 487             }
 488             if (finishingorder!=null)
 489                 finishingorder.add(gn);
 490             gn.finish(time++);
 491             return acyclic;
 492         }
 493
 494     } /* end DFS */
 495
 496 }