ReachChecker


1   package polyglot.visit;
2   
3   import java.util.*;
4   
5   import polyglot.ast.*;
6   import polyglot.frontend.Job;
7   import polyglot.main.Report;
8   import polyglot.types.SemanticException;
9   import polyglot.types.TypeSystem;
10  import polyglot.util.InternalCompilerError;
11  
12  /**
13   * Visitor which checks that all statements must be reachable
14   */
15  public class ReachChecker extends DataFlow
16  {
17      public ReachChecker(Job job, TypeSystem ts, NodeFactory nf) {
18      super(job, ts, nf, 
19                true /* forward analysis */, 
20                true /* perform dataflow on entry to CodeDecls */);
21      }
22  
23      protected static class DataFlowItem extends Item {
24          final boolean reachable;
25          final boolean normalReachable;
26  
27          protected DataFlowItem(boolean reachable, boolean normalReachable) {
28              this.reachable = reachable;
29              this.normalReachable = normalReachable;
30          }
31          
32          // terms that are reachable through normal control flow
33          public static final DataFlowItem REACHABLE = new DataFlowItem(true, true);
34          
35          // terms that are reachable only through exception control flow, but
36          // not by normal control flow. 
37          public static final DataFlowItem REACHABLE_EX_ONLY = new DataFlowItem(true, false);
38  
39          // terms that are not reachable 
40          public static final DataFlowItem NOT_REACHABLE = new DataFlowItem(false, false);
41  
42          public String   toString() {
43              return (reachable?"":"not ") + "reachable" +
44                     (normalReachable?"":" by exceptions only");
45          }
46          
47          public boolean equals(Object   o) {
48              if (o instanceof DataFlowItem) {
49                  return this.reachable == ((DataFlowItem)o).reachable &&
50                         this.normalReachable == ((DataFlowItem)o).normalReachable;
51              }
52              return false;
53          }
54          public int hashCode() {
55              return (reachable ? 5423 : 5753) + (normalReachable ? 31 : -2);
56          }
57      }
58  
59      public Item createInitialItem(FlowGraph graph, Term node) {
60          if (node == graph.entryNode()) {
61              return DataFlowItem.REACHABLE;
62          }
63          else {
64              return DataFlowItem.NOT_REACHABLE;
65          }
66      }
67      public Map flow(Item in, FlowGraph graph, Term n, Set succEdgeKeys) {
68          if (in == DataFlowItem.NOT_REACHABLE) {
69              return itemToMap(in, succEdgeKeys);
70          }
71          
72          // in is either REACHABLE or REACHABLE_EX_ONLY.
73          // return a map where all exception edges are REACHABLE_EX_ONLY,
74          // and all non-exception edges are REACHABLE.
75          Map m = itemToMap(DataFlowItem.REACHABLE_EX_ONLY, succEdgeKeys);
76  
77          if (succEdgeKeys.contains(FlowGraph.EDGE_KEY_OTHER)) {
78              m.put(FlowGraph.EDGE_KEY_OTHER, DataFlowItem.REACHABLE);
79          }
80          if (succEdgeKeys.contains(FlowGraph.EDGE_KEY_TRUE)) {
81              m.put(FlowGraph.EDGE_KEY_TRUE, DataFlowItem.REACHABLE);
82          }
83          if (succEdgeKeys.contains(FlowGraph.EDGE_KEY_FALSE)) {
84              m.put(FlowGraph.EDGE_KEY_FALSE, DataFlowItem.REACHABLE);
85          }
86          
87          return m;
88      }
89  
90      public Item confluence(List inItems, Term node, FlowGraph graph) {
91          throw new InternalCompilerError("Should never be called.");
92      }
93  
94      public Item confluence(List inItems, List itemKeys, Term node, FlowGraph graph) {
95          // if any predecessor is reachable, so is this one, and if any
96          // predecessor is normal reachable, and the edge key is not an 
97          // exception edge key, then so is this one.
98          
99          
100         List l = this.filterItemsNonException(inItems, itemKeys);
101         for (Iterator i = l.iterator(); i.hasNext(); ) {
102             if (i.next() == DataFlowItem.REACHABLE) {
103                 // this term is reachable via a non-exception edge
104                 return DataFlowItem.REACHABLE;
105             }
106         }
107 
108         // If we fall through to here, then there were
109         // no non-exception edges that were normally reachable.        
110         // We now need to determine if this node is
111         // reachable via an exception edge key, or if 
112         // it is not reachable at all.
113         for (Iterator i = inItems.iterator(); i.hasNext(); ) {
114             if (((DataFlowItem)i.next()).reachable) {
115                 // this term is reachable, but only through an
116                 // exception edge.
117                 return DataFlowItem.REACHABLE_EX_ONLY;
118             }
119         }
120 
121         return DataFlowItem.NOT_REACHABLE;
122     }
123 
124     public Node leaveCall(Node n) throws SemanticException {
125         // check for reachability.
126         if (n instanceof Term) {
127            n = checkReachability((Term)n);
128         }
129          
130         return super.leaveCall(n);
131     }
132 
133     protected Node checkReachability(Term n) throws SemanticException {
134         FlowGraph g = currentFlowGraph();
135         if (g != null) {   
136             Collection peers = g.peers(n);
137             if (peers != null && !peers.isEmpty()) {
138                 boolean isInitializer = (n instanceof Initializer);
139                 
140                 for (Iterator iter = peers.iterator(); iter.hasNext(); ) {
141                     FlowGraph.Peer p = (FlowGraph.Peer) iter.next();
142         
143                     // the peer is reachable if at least one of its out items
144                     // is reachable. This would cover all cases, except that some
145                     // peers may have no successors (e.g. peers that throw an
146                     // an exception that is not caught by the method). So we need 
147                     // to also check the inItem.
148                     if (p.inItem() != null) {
149                         DataFlowItem dfi = (DataFlowItem)p.inItem();
150                         // there will only be one peer for an initializer,
151                         // as it cannot occur in a finally block.
152                         if (isInitializer && !dfi.normalReachable) {
153                             throw new SemanticException("Initializers must be able to complete normally.",
154                                                         n.position());
155                         }
156 
157                         if (dfi.reachable) {
158                             return n.reachable(true);
159                         }
160                     }
161                     
162                     if (p.outItems != null) {
163                         for (Iterator k = p.outItems.values().iterator(); k.hasNext(); ) {
164                             DataFlowItem item = (DataFlowItem) k.next();
165                         
166                             if (item != null && item.reachable) {
167                                 // n is reachable.
168                                 return n.reachable(true);
169                             }                    
170                         }
171                     }
172                 }
173                 
174                 // if we fall through to here, then no peer for n was reachable.
175                 n = n.reachable(false);
176                 
177                 // Compound statements are allowed to be unreachable
178                 // (e.g., "{ // return; }" or "while (true) S").  If a compound
179                 // statement is truly unreachable, one of its sub-statements will
180                 // be also and we will report an error there.
181     
182                 if ((n instanceof Block && ((Block) n).statements().isEmpty()) ||
183                     (n instanceof Stmt && ! (n instanceof CompoundStmt))) {
184                     throw new SemanticException("Unreachable statement.",
185                                                 n.position());
186                 }
187             }
188         }        
189         return n;
190     }
191     
192     public void post(FlowGraph graph, Term root) throws SemanticException {
193         // There is no need to do any checking in this method, as this will
194         // be handled by leaveCall and checkReachability.
195         if (Report.should_report(Report.cfg, 2)) {
196             dumpFlowGraph(graph, root);
197         }
198     } 
199 
200     public void check(FlowGraph graph, Term n, Item inItem, Map outItems) throws SemanticException {
201         throw new InternalCompilerError("ReachChecker.check should " +
202                 "never be called.");
203     }
204     
205 }
206
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags