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