CFGBuilder


1   package polyglot.visit;
2   
3   import java.util.*;
4   
5   import polyglot.ast.*;
6   import polyglot.main.Report;
7   import polyglot.types.Type;
8   import polyglot.types.TypeSystem;
9   import polyglot.util.*;
10  
11  /**
12   * Class used to construct a CFG.
13   */
14  public class CFGBuilder implements Copy
15  {
16      /** The flowgraph under construction. */
17      protected FlowGraph graph;
18  
19      /** The type system. */
20      protected TypeSystem ts;
21  
22      /**
23       * The outer CFGBuilder.  We create a new inner CFGBuilder when entering a
24       * loop or try-block and when entering a finally block.
25       */
26      protected CFGBuilder outer;
27  
28      /**
29       * The innermost loop or try-block in lexical scope.  We maintain a stack
30       * of loops and try-blocks in order to add edges for break and continue
31       * statements and for exception throws.  When such a jump is encountered we
32       * traverse the stack, searching for the target of the jump.
33       */
34      protected Stmt innermostTarget;
35  
36      /**
37       * List of terms on the path to the innermost finally block.  If we are
38       * constructing a CFG for a finally block, this is the sequence of terms
39       * that caused entry into this and lexically enclosing finally blocks.
40       * We construct a unique subgraph for each such path. The list
41       * is empty if this CFGBuilder is not constructing the CFG for a finally
42       * block.
43       */
44      protected List path_to_finally;
45  
46      /** The data flow analysis for which we are constructing the graph. */
47      protected DataFlow df;
48  
49      /**
50       * True if we should skip the catch blocks for the innermost try when
51       * building edges for an exception throw.
52       */
53      protected boolean skipInnermostCatches;
54      
55      /**
56       * True if we should add edges for uncaught Errors to the exit node of the
57       * graph.  By default, we do not, but subclasses can change this behavior
58       * if needed.
59       */
60      protected boolean errorEdgesToExitNode;
61  
62      public CFGBuilder(TypeSystem ts, FlowGraph graph, DataFlow df) {
63          this.ts = ts;
64          this.graph = graph;
65          this.df = df;
66          this.path_to_finally = Collections.EMPTY_LIST;
67          this.outer = null;
68          this.innermostTarget = null;
69          this.skipInnermostCatches = false;
70          this.errorEdgesToExitNode = false;
71      }
72  
73      /** Get the type system. */
74      public TypeSystem typeSystem() {
75          return ts;
76      }
77  
78      /** Copy the CFGBuilder. */
79      public Object   copy() {
80          try {
81              return (CFGBuilder) super.clone();
82          }
83          catch (CloneNotSupportedException   e) {
84              throw new InternalCompilerError("Java clone() weirdness.");
85          }
86      }
87  
88      /**
89       * Construct a new CFGBuilder with the a new innermost loop or
90       * try-block <code>n</code>.
91       */
92      public CFGBuilder push(Stmt n) {
93          return push(n, false);
94      }
95  
96      /**
97       * Construct a new CFGBuilder with the a new innermost loop or
98       * try-block <code>n</code>, optionally skipping innermost catch blocks.
99       */
100     public CFGBuilder push(Stmt n, boolean skipInnermostCatches) {
101         CFGBuilder v = (CFGBuilder) copy();
102         v.outer = this;
103         v.innermostTarget = n;
104         v.skipInnermostCatches = skipInnermostCatches;
105         return v;
106     }
107 
108     /**
109      * Visit edges from a branch.  Simulate breaking/continuing out of
110      * the loop, visiting any finally blocks encountered.
111      */
112     public void visitBranchTarget(Branch b) {
113       Term last = b;
114       CFGBuilder last_visitor = this;
115 
116       for (CFGBuilder v = this; v != null; v = v.outer) {
117         Term c = v.innermostTarget;
118 
119         if (c instanceof Try) {
120           Try tr = (Try) c;
121           if (tr.finallyBlock() != null) {
122             last_visitor = tryFinally(v, last, last_visitor, tr.finallyBlock());
123             last = tr.finallyBlock();
124           }
125         }
126 
127         if (b.label() != null) {
128           if (c instanceof Labeled) {
129             Labeled l = (Labeled) c;
130             if (l.label().equals(b.label())) {
131               if (b.kind() == Branch.BREAK) {
132                 edge(last_visitor, last, l, FlowGraph.EDGE_KEY_OTHER);
133               }
134               else {
135                 Stmt s = l.statement();
136                 if (s instanceof Loop) {
137                   Loop loop = (Loop) s;
138                   edge(last_visitor, last, loop.continueTarget(), FlowGraph.EDGE_KEY_OTHER);
139                 }
140                 else {
141                   throw new CFGBuildError("Target of continue statement must " +
142                                           "be a loop.", l.position());
143                 }
144               }
145 
146               return;
147             }
148           }
149         }
150         else {
151           if (c instanceof Loop) {
152             Loop l = (Loop) c;
153             if (b.kind() == Branch.CONTINUE) {
154               edge(last_visitor, last, l.continueTarget(), FlowGraph.EDGE_KEY_OTHER);
155             }
156             else {
157               edge(last_visitor, last, l, FlowGraph.EDGE_KEY_OTHER);
158             }
159 
160             return;
161           }
162           else if (c instanceof Switch && b.kind() == Branch.BREAK) {
163             edge(last_visitor, last, c, FlowGraph.EDGE_KEY_OTHER);
164             return;
165           }
166         }
167       }
168 
169       throw new CFGBuildError("Target of branch statement not found.",
170                               b.position());
171     }
172 
173     /**
174      * Visit edges for a return statement.  Simulate the return, visiting any
175      * finally blocks encountered.
176      */
177     public void visitReturn(Return r) {
178       Term last = r;
179       CFGBuilder last_visitor = this;
180 
181       for (CFGBuilder v = this; v != null; v = v.outer) {
182         Term c = v.innermostTarget;
183 
184         if (c instanceof Try) {
185           Try tr = (Try) c;
186           if (tr.finallyBlock() != null) {
187             last_visitor = tryFinally(v, last, last_visitor, tr.finallyBlock());
188             last = tr.finallyBlock();
189           }
190         }
191       }
192 
193       // Add an edge to the exit node.
194       edge(last_visitor, last, graph.exitNode(), FlowGraph.EDGE_KEY_OTHER);
195     }
196 
197     static int counter = 0;
198 
199     /** Visit the AST, constructing the CFG. */
200     public void visitGraph() {
201         String   name = StringUtil.getShortNameComponent(df.getClass().getName());
202         name += counter++;
203 
204     if (Report.should_report(Report.cfg, 2)) {
205             String   rootName = "";
206             if (graph.root() instanceof CodeDecl) {
207                 CodeDecl cd = (CodeDecl)graph.root();
208                 rootName = cd.codeInstance().toString() + " in " + 
209                             cd.codeInstance().container().toString();
210             }
211 
212             Report.report(2, "digraph CFGBuild" + name + " {");
213             Report.report(2, "  label=\"CFGBuilder: " + name + "\\n" + rootName +
214                 "\"; fontsize=20; center=true; ratio=auto; size = \"8.5,11\";");
215         }
216 
217         // create peers for the entry and exit nodes.
218         graph.peer(graph.entryNode(), Collections.EMPTY_LIST, df);
219         graph.peer(graph.exitNode(), Collections.EMPTY_LIST, df);
220 
221         this.visitCFG(graph.root(), Collections.EMPTY_LIST);
222 
223     if (Report.should_report(Report.cfg, 2))
224         Report.report(2, "}");
225     }
226 
227     /** Utility function to visit all edges in a list. */
228     public void visitCFGList(List elements, Term after) {
229         Term prev = null;
230 
231         for (Iterator i = elements.iterator(); i.hasNext(); ) {
232             Term c = (Term) i.next();
233 
234             if (prev != null) {
235                 visitCFG(prev, c.entry());
236             }
237 
238             prev = c;
239         }
240 
241         if (prev != null) {
242             visitCFG(prev, after);
243         }
244     }
245 
246     /**
247      * Create an edge for a node <code>a</code> with a single successor
248      * <code>succ</code>.
249      * 
250      * The EdgeKey used for the edge from <code>a</code> to <code>succ</code>
251      * will be FlowGraph.EDGE_KEY_OTHER
252      */
253     public void visitCFG(Term a, Term succ) {
254         visitCFG(a, FlowGraph.EDGE_KEY_OTHER, succ);
255     }
256 
257     /**
258      * Create an edge for a node <code>a</code> with a single successor
259      * <code>succ</code>, and EdgeKey <code>edgeKey</code>
260      */
261     public void visitCFG(Term a, FlowGraph.EdgeKey edgeKey, Term succ) {
262         visitCFG(a, CollectionUtil.list(new EdgeKeyTermPair(edgeKey, succ)));
263     }
264 
265     /**
266      * Create edges from node <code>a</code> to successors <code>succ1</code> 
267      * and <code>succ2</code> with EdgeKeys <code>edgeKey1</code> and
268      * <code>edgeKey2</code> respecitvely.
269      */
270     public void visitCFG(Term a, FlowGraph.EdgeKey edgeKey1, Term succ1, 
271                                  FlowGraph.EdgeKey edgeKey2, Term succ2) {
272         visitCFG(a, CollectionUtil.list(new EdgeKeyTermPair(edgeKey1, succ1), 
273                                         new EdgeKeyTermPair(edgeKey2, succ2)));
274     }
275 
276     /**
277      * Create edges from node <code>a</code> to all successors <code>succ</code> 
278      * with the EdgeKey <code>edgeKey</code> for all edges created.
279      */
280     public void visitCFG(Term a, FlowGraph.EdgeKey edgeKey, List succ) {
281         List l = new ArrayList(2*succ.size());
282         for (Iterator iter = succ.iterator(); iter.hasNext(); ) {
283             l.add(new EdgeKeyTermPair(edgeKey, (Term)iter.next()));
284         }
285         visitCFG(a, l);
286     }
287 
288     protected static class EdgeKeyTermPair {
289         public EdgeKeyTermPair(FlowGraph.EdgeKey edgeKey, Term term) {
290             this.edgeKey = edgeKey;
291             this.term = term;
292         }
293         FlowGraph.EdgeKey edgeKey;
294         Term term;        
295 
296     public String   toString() {
297         return "{edgeKey=" + edgeKey + ",term=" + term + "}";
298     }
299     }
300     /**
301      * Create edges for a node <code>a</code> with successors
302      * <code>succs</code>.
303      * 
304      * @param a the source node for the edges.
305      * @param succs a list of <code>EdgeKeyTermPair</code>s
306      */
307     protected void visitCFG(Term a, List succs) {
308         if (Report.should_report(Report.cfg, 2))
309             Report.report(2, "// node " + a + " -> " + succs);
310 
311         succs = a.acceptCFG(this, succs);
312 
313         for (Iterator i = succs.iterator(); i.hasNext(); ) {
314             EdgeKeyTermPair pair = (EdgeKeyTermPair)i.next();
315             edge(a, pair.term, pair.edgeKey);
316         }
317 
318         visitThrow(a);
319     }
320 
321     public void visitThrow(Term a) {
322         for (Iterator i = a.del().throwTypes(ts).iterator(); i.hasNext(); ) {
323             Type type = (Type) i.next();
324             visitThrow(a, type);
325         }
326 
327         // Every statement can throw an error.
328         // This is probably too inefficient.
329         if ((a instanceof Stmt && ! (a instanceof CompoundStmt)) ||
330             (a instanceof Block && ((Block) a).statements().isEmpty())) {
331             
332             visitThrow(a, ts.Error());
333         }
334     }
335     
336     /**
337      * Create edges for an exception thrown from term <code>t</code>.
338      */
339     public void visitThrow(Term t, Type type) {
340         Term last = t;
341         CFGBuilder last_visitor = this;
342 
343         for (CFGBuilder v = this; v != null; v = v.outer) {
344             Term c = v.innermostTarget;
345 
346             if (c instanceof Try) {
347                 Try tr = (Try) c;
348 
349                 if (! v.skipInnermostCatches) {                    
350                     boolean definiteCatch = false;
351                     
352                     for (Iterator i = tr.catchBlocks().iterator(); i.hasNext(); ) {
353                         Catch cb = (Catch) i.next();
354 
355                         // definite catch
356                         if (type.isImplicitCastValid(cb.catchType())) {
357                             edge(last_visitor, last, cb.entry(), new FlowGraph.ExceptionEdgeKey(type));
358                             definiteCatch = true;
359                         }
360                         // possible catch
361                         else if (cb.catchType().isImplicitCastValid(type)) { 
362                             edge(last_visitor, last, cb.entry(), new FlowGraph.ExceptionEdgeKey(cb.catchType()));
363                         }
364                     }
365                     if (definiteCatch) {
366                         // the exception has definitely been caught.
367                         // we can stop recursing to outer try-catch blocks
368                         return; 
369                     }
370                 }
371 
372                 if (tr.finallyBlock() != null) {
373                     last_visitor = tryFinally(v, last, last_visitor, tr.finallyBlock());
374                     last = tr.finallyBlock();
375                 }
376             }
377         }
378 
379         // If not caught, insert a node from the thrower to exit.
380         if (errorEdgesToExitNode || !type.isSubtype(ts.Error())) {
381             edge(last_visitor, last, graph.exitNode(), new FlowGraph.ExceptionEdgeKey(type));
382         }
383     }
384 
385     /**
386      * Create edges for the finally block of a try-finally construct. 
387      * 
388      * @param v v.innermostTarget is the Try term that the finallyBlock is assoicated with. @@@XXX
389      * @param last the last term visited before the finally block is entered.
390      * @param last_visitor @@@XXX
391      * @param finallyBlock the finally block associated with a try finally block.
392      */
393     protected static CFGBuilder tryFinally(CFGBuilder v, Term last,
394                                  CFGBuilder last_visitor, Block finallyBlock) {
395         //###@@@ I think that we may be using the wrong visitor to perform the
396         // enterFinally on; should it maybe be last_visitor? we want to make 
397         // sure that the path_to_finally list grows correctly.
398         CFGBuilder v_ = v.outer.enterFinally(last);
399         
400         // @@@XXX
401         v_.edge(last_visitor, last, finallyBlock.entry(), FlowGraph.EDGE_KEY_OTHER);
402         
403         // visit the finally block.  
404         v_.visitCFG(finallyBlock, Collections.EMPTY_LIST);
405         return v_;
406     }
407 
408     /** 
409      * Enter a finally block. This method returns a new CFGBuilder
410      * with the path_to_finally field pointing to a list that has the
411      * Term <code>from</code> appended.
412      */
413     protected CFGBuilder enterFinally(Term from) {
414       CFGBuilder v = (CFGBuilder) this.copy();
415       v.path_to_finally = new ArrayList(path_to_finally.size()+1);
416       v.path_to_finally.addAll(path_to_finally);
417       v.path_to_finally.add(from);
418       return v;
419     }
420 
421     /**
422      * Add an edge to the CFG from <code>p</code> to <code>q</code>.
423      */
424     public void edge(Term p, Term q) {
425       edge(this, p, q, FlowGraph.EDGE_KEY_OTHER);
426     }
427 
428     /**
429      * Add an edge to the CFG from <code>p</code> to <code>q</code>.
430      */
431     public void edge(Term p, Term q, FlowGraph.EdgeKey edgeKey) {
432       edge(this, p, q, edgeKey);
433     }
434     
435     /**
436      * @param p_visitor The visitor used to create p ("this" is the visitor
437      *                  that created q) 
438      * @param p The predecessor node in the forward graph
439      * @param q The successor node in the forward graph
440      */
441     public void edge(CFGBuilder p_visitor, Term p, Term q, FlowGraph.EdgeKey edgeKey) {
442         if (Report.should_report(Report.cfg, 2))
443             Report.report(2, "//     edge " + p + " -> " + q);
444         
445         FlowGraph.Peer pp = graph.peer(p, p_visitor.path_to_finally, df);
446         FlowGraph.Peer pq = graph.peer(q, path_to_finally, df);
447         
448         if (Report.should_report(Report.cfg, 3)) {
449             // at level 3, use Peer.toString() as the label for the nodes
450             Report.report(2,
451                           pp.hashCode() + " [ label = \"" +
452                           StringUtil.escape(pp.toString()) + "\" ];");
453             Report.report(2,
454                           pq.hashCode() + " [ label = \"" +
455                           StringUtil.escape(pq.toString()) + "\" ];");
456         }
457         else if (Report.should_report(Report.cfg, 2)) {
458             // at level 2, use Node.toString() as the label for the nodes
459             // which is more readable than Peer.toString(), but not as unique.
460             Report.report(2,
461                           pp.hashCode() + " [ label = \"" +
462                           StringUtil.escape(pp.node.toString()) + "\" ];");
463             Report.report(2,
464                           pq.hashCode() + " [ label = \"" +
465                           StringUtil.escape(pq.node.toString()) + "\" ];");
466         }
467         
468         if (graph.forward()) {
469             if (Report.should_report(Report.cfg, 2)) {
470                 Report.report(2, pp.hashCode() + " -> " + pq.hashCode() + " [label=\"" + edgeKey + "\"];");
471             }
472             pp.succs.add(new FlowGraph.Edge(edgeKey, pq));
473             pq.preds.add(new FlowGraph.Edge(edgeKey, pp));
474         }
475         else {
476             if (Report.should_report(Report.cfg, 2)) {
477                 Report.report(2, pq.hashCode() + " -> " + pp.hashCode() + " [label=\"" + edgeKey + "\"];");
478             }
479             pq.succs.add(new FlowGraph.Edge(edgeKey, pp));
480             pp.preds.add(new FlowGraph.Edge(edgeKey, pq));
481         }
482     }
483 }
484
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags