FlowGraph


1   package polyglot.visit;
2   
3   import polyglot.ast.*;
4   import polyglot.types.*;
5   import polyglot.util.*;
6   import java.util.*;
7   
8   public class FlowGraph {
9     /**
10     * Maps from AST nodes to path maps and hence to <code>Peer</code>s
11     * that represent occurrences of the
12     * AST node in the flow graph.  In particular, <code>peerMap</code>
13     * maps <code>IdentityKey(Node)</code>s to path maps.  A path map is a
14     * map from paths (<code>ListKey(List of Terms)</code>) to
15     * <code>Peer</code>s.  In particular, if <code>n</code> is an AST
16     * node in a finally block, then there will be a <code>Peer</code> of
17     * <code>n</code> for each possible path to the finally block, and the
18     * path map records which <code>Peer</code> corresponds to which path.
19     * If <code>n</code> does not occur in a finally block, then the path
20     * map should have only a single entry, from an empty list to the
21     * unique <code>Peer</code> for <code>n</code>.
22     *
23     * <p>
24     * <b>WARNING</b>: the AST must be a tree, not a DAG.  Otherwise the
25     * same peer may be used for a node that appears at multiple points in
26     * the AST.  These points may have different data flows.
27     * </p>
28     */  
29    protected Map peerMap;
30    
31    /**
32     * The root of the AST that this is a flow graph for.
33     */
34    protected Term root;
35    
36    /**
37     * Is the flow in this flow graph forward or backward?
38     */
39    protected boolean forward;
40  
41    FlowGraph(Term root, boolean forward) {
42      this.root = root;
43      this.forward = forward;
44      this.peerMap = new HashMap();
45    }
46  
47    public Term startNode() { return forward ? root.entry() : root; }
48    public Term finishNode() { return forward ? root : root.entry(); }
49    public Term entryNode() { return root.entry(); }
50    public Term exitNode() { return root; }
51    public Term root() { return root; }
52    public boolean forward() { return forward; }
53  
54    public Collection pathMaps() {
55      return peerMap.values();
56    }
57  
58    public Map pathMap(Node n) {
59      return (Map) peerMap.get(new IdentityKey(n));
60    }
61  
62    /**
63     * Return a collection of all <code>Peer</code>s in this flow graph.
64     */
65    public Collection peers() {
66      Collection c = new ArrayList();
67      for (Iterator i = peerMap.values().iterator(); i.hasNext(); ) {
68        Map m = (Map) i.next();
69        for (Iterator j = m.values().iterator(); j.hasNext(); ) {
70          c.add(j.next());
71        }
72      }
73      return c;
74    }
75  
76    /**
77     * Retrieve the <code>Peer</code> for the <code>Term n</code>, where 
78     * <code>n</code> does not appear in a finally block. If no such Peer 
79     * exists, then one will be created.
80     * 
81     * @param df unused; for legacy purposes only?
82     */
83    public Peer peer(Term n, DataFlow df) {
84      return peer(n, Collections.EMPTY_LIST, df);
85    }
86  
87    /**
88     * Return a collection of all of the <code>Peer</code>s for the given 
89     * <code>Term n</code>. 
90     */
91    public Collection peers(Term n) {
92      IdentityKey k = new IdentityKey(n);
93      Map pathMap = (Map) peerMap.get(k);
94      if (pathMap == null) {
95          return Collections.EMPTY_LIST;
96      }
97      return pathMap.values();
98    }
99  
100   /**
101    * Retrieve the <code>Peer</code> for the <code>Term n</code> that is 
102    * associated with the given path to the finally block. (A term that occurs
103    * in a finally block has one Peer for each possible path to that finally
104    * block.) If no such Peer exists, then one will be created.
105    * 
106    * @param df unused; for legacy purposes only?
107    */
108   public Peer peer(Term n, List path_to_finally, DataFlow df) {
109     IdentityKey k = new IdentityKey(n);
110     Map pathMap = (Map) peerMap.get(k);
111     if (pathMap == null) {
112       pathMap = new HashMap();
113       peerMap.put(k, pathMap);
114     }
115 
116     ListKey lk = new ListKey(path_to_finally);
117     Peer p = (Peer) pathMap.get(lk);
118     if (p == null) {
119       p = new Peer(n, path_to_finally);
120       pathMap.put(lk, p);
121     }
122     return p;
123   }
124 
125   /**
126    * This class provides an identifying label for edges in the flow graph.
127    * Thus, the condition of an if statement will have at least two edges
128    * leaving it (in a forward flow graph): one will have the EdgeKey
129    * FlowGraph.EDGE_KEY_TRUE, and is the flow that is taken when the condition
130    * evaluates to true, and one will have the EdgeKey FlowGraph.EDGE_KEY_FALSE,
131    * and is the flow that is taken when the condition evaluates to false. 
132    * 
133    * The differentiation of the flow graph edges allows for a finer grain
134    * data flow analysis, as the dataflow equations can incorporate the 
135    * knowledge that a condition is true or false on certain flow paths.
136    */
137   public static class EdgeKey {
138       protected Object   o;
139       protected EdgeKey(Object   o) {
140           this.o = o;
141       }
142       public int hashCode() {
143           return o.hashCode();
144       }
145       public boolean equals(Object   other) {
146           return (other instanceof EdgeKey) && 
147                   (((EdgeKey)other).o.equals(this.o));
148       }
149       public String   toString() {
150           return o.toString();
151       }
152   }
153   
154   /**
155    * This class extends EdgeKey and is the key for edges that are
156    * taken when an exception of type t is thrown. Thus, the flow from
157    * line 2 in the example below to the catch block (line 4) would have an
158    * ExceptionEdgeKey constructed with the Type representing 
159    * NullPointerExceptions.
160    * 
161    * <pre>
162    * ...
163    * try {                                      // line 1
164    *   o.foo();                                 // line 2
165    * }                                          // line 3
166    * catch (NullPointerException e) {           // line 4
167    *   ...
168    * }
169    * ...
170    * </pre>
171    */
172   public static class ExceptionEdgeKey extends EdgeKey {
173       public ExceptionEdgeKey(Type t) {
174           super(t);
175       }
176 
177       public Type type() {
178           return (Type) o;
179       }
180 
181       public String   toString() {
182           return (type().isClass() ? type().toClass().name() : type().toString() );
183       }
184   }
185   
186   /**
187    * This EdgeKey is the EdgeKey for edges where the expression evaluates
188    * to true.
189    */
190   public static final EdgeKey EDGE_KEY_TRUE = new EdgeKey("true");
191   
192   /**
193    * This EdgeKey is the EdgeKey for edges where the expression evaluates
194    * to false.
195    */
196   public static final EdgeKey EDGE_KEY_FALSE = new EdgeKey("false");
197 
198   /**
199    * This EdgeKey is the EdgeKey for edges where the flow is not suitable 
200    * for EDGE_KEY_TRUE, EDGE_KEY_FALSE or an 
201    * ExceptionEdgeKey, such as the edges from a switch
202    * statement to its cases and
203    * the flow from a sink node in the control flow graph.
204    */
205   public static final EdgeKey EDGE_KEY_OTHER = new EdgeKey("");
206 
207   /**
208    * This class represents an edge in the flow graph. The target of the edge
209    * is either the head or the tail of the edge, depending on how the Edge is 
210    * used. Thus, the target field in Edges in the collection Peer.preds is the
211    * source Peer, while the target field in Edges in the collection Peer.succs 
212    * is the destination Peer of edges.
213    * 
214    * Each Edge has an EdgeKey, which identifies when flow uses that edge in 
215    * the flow graph. See EdgeKey for more information.
216    */
217   public static class Edge {
218       protected Edge(EdgeKey key, Peer target) {
219           this.key = key;
220           this.target = target;
221       }
222       public EdgeKey getKey() {
223           return key;
224       }
225       public Peer getTarget() {
226           return target;
227       }
228       protected EdgeKey key;
229       protected Peer target;
230       public String   toString() {
231           return "(" + key + ")" + target;
232       }
233       
234   }
235   
236   /**
237    * A <code>Peer</code> is an occurance of an AST node in a flow graph. 
238    * For most AST nodes, there will be only one Peer for each AST node. 
239    * However, if the AST node occurs in a finally block, then there will be
240    * multiple <code>Peer</code>s for that AST node, one for each possible
241    * path to the finally block. This is becuase flow graphs for finally blocks 
242    * are copied, one copy for each possible path to the finally block.
243    */
244   public static class Peer {
245     protected DataFlow.Item inItem;  // Input Item for dataflow analysis
246     protected Map outItems; // Output Items for dataflow analysis, a map from EdgeKeys to DataFlowlItems
247     protected Term node; // The AST node that this peer is an occurance of.
248     protected List succs; // List of successor Edges 
249     protected List preds; // List of predecessor Edges 
250     protected List path_to_finally; // the path to the finally block that 
251                                     // uniquely distinguishes this Peer
252                                     // from the other Peers for the AST node.
253 
254     /**
255      * Set of all the different EdgeKeys that occur in the Edges in the 
256      * succs. This Set is lazily constructed, as needed, by the 
257      * method succEdgeKeys()
258      */     
259     private Set succEdgeKeys;
260 
261     public Peer(Term node, List path_to_finally) {
262       this.node = node;
263       this.path_to_finally = path_to_finally;
264       this.inItem = null;
265       this.outItems = null;
266       this.succs = new ArrayList();
267       this.preds = new ArrayList();
268       this.succEdgeKeys = null;
269     }
270 
271     /** The successor Edges. */
272     public List succs() { return succs; }
273 
274     /** The predecessor Edges. */
275     public List preds() { return preds; }
276 
277     /** The node for which this is a peer. */
278     public Term node()  { return node; }
279 
280     /**
281      * The input data flow item.  Should only be called
282      * after data flow analysis is performed.
283      */
284     public DataFlow.Item inItem() { return inItem; }
285 
286     /**
287      * The output item for a particular EdgeKey.  Should only be called
288      * after data flow analysis is performed.
289      */
290     public DataFlow.Item outItem(EdgeKey key) {
291       return (DataFlow.Item) outItems.get(key);
292     }
293 
294     public String   toString() {
295       return node + "[" + hashCode() + ": " + path_to_finally + "]";
296     }
297 
298     public Set succEdgeKeys() {
299         if (this.succEdgeKeys == null) {
300             // the successor edge keys have not yet been calculated. do it
301             // now.
302             this.succEdgeKeys = new HashSet();
303             for (Iterator iter = this.succs.iterator(); iter.hasNext(); ) {
304                 Edge e = (Edge)iter.next();
305                 this.succEdgeKeys.add(e.getKey());
306             }
307             if (this.succEdgeKeys.isEmpty()) {
308                 // There are no successors for this node. Add in the OTHER
309                 // edge key, so that there is something to map the output
310                 // item from...
311                 this.succEdgeKeys.add(FlowGraph.EDGE_KEY_OTHER);
312             }
313         }
314         return this.succEdgeKeys;
315     }
316   }
317 
318   /**
319    * Class to be used for inserting Lists in hashtables using collection
320    * equality (as defined in {@link polyglot.util.CollectionUtil CollectionUtil}).
321    */
322   protected static class ListKey {
323     protected List list;
324 
325     ListKey(List list) {
326       this.list = list;
327     }
328 
329     public int hashCode() {
330       return list.hashCode();
331     }
332 
333     public boolean equals(Object   other) {
334       if (other instanceof ListKey) {
335           ListKey k = (ListKey) other;
336           return CollectionUtil.equals(list, k.list);
337       }
338 
339       return false;
340     }
341   }
342   
343   public String   toString() {
344     
345     StringBuffer   sb = new StringBuffer  ();
346     Set todo = new HashSet(this.peers());
347     LinkedList queue = new LinkedList(this.peers(this.startNode()));
348     
349     while (!queue.isEmpty()) {
350         Peer p = (Peer)queue.removeFirst();
351         todo.remove(p);
352 //        sb.append(StringUtil.getShortNameComponent(p.node.getClass().getName()) + " ["+p.node+"]" + "\n");
353         sb.append(p.node+" (" + p.node.position()+ ")\n");
354         for (Iterator i = p.succs.iterator(); i.hasNext(); ) {
355             Edge e = (Edge)i.next();
356             Peer q = e.getTarget();
357             sb.append("    -> " + q.node+" (" + q.node.position()+ ")\n");
358             //sb.append("  " + StringUtil.getShortNameComponent(q.node.getClass().getName()) + " ["+q.node+"]" + "\n");
359             if (todo.contains(q) && !queue.contains(q)) {
360                 queue.addLast(q);
361             }
362         }
363         
364         if (queue.isEmpty() && !todo.isEmpty()) {
365             sb.append("\n\n***UNREACHABLE***\n");
366             queue.addAll(todo);
367             todo = Collections.EMPTY_SET;
368         }
369     }
370     
371     return sb.toString();
372   }
373 }
374
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags