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