1   // Copyright 2012- Bill Campbell, Swami Iyer and Bahar Akbal-Delibas
2   
3   package jminusminus;
4   
5   import java.util.ArrayList;
6   import java.util.HashMap;
7   import java.util.Map;
8   import java.util.Set;
9   
10  /**
11   * A Context encapsulates the environment in which an AST is analyzed. It represents a scope; the
12   * scope of a variable is captured by its context. It's the symbol table.
13   * <p>
14   * Because scopes are lexically nested in Java (and so in j--), the environment can be seen as a
15   * stack of contexts, each of which is a mapping from names to their definitions (IDefns). A
16   * Context keeps track of its (most closely) surrounding context, its surrounding class  context,
17   * and its surrounding compilation unit context, and as well as a map from names to definitions
18   * in the level of scope that the Context represents. Contexts are created for the compilation
19   * unit (a CompilationUnitContext), a class (a ClassContext), each method (a MethodContext), and
20   * each block (a LocalContext). If we were to add the for-statement to j--, we would necessarily
21   * create a (local) context.
22   * <p>
23   * From the outside, the structure looks like a tree strung over the AST. But from any location
24   * on the AST, that is from any point along a particular branch, it looks like a stack of context
25   * objects leading back to the root of the AST, that is, back to the JCompilationUnit object at
26   * the root.
27   * <p>
28   * Part of this structure is built during pre-analysis; pre-analysis reaches only into the type
29   * (for example a class) declaration for typing the members; pre-analysis does not reach into the
30   * method bodies. The rest of it is built during analysis.
31   */
32  class Context {
33      /**
34       * The surrounding context (scope).
35       */
36      protected Context surroundingContext;
37  
38      /**
39       * The surrounding class context.
40       */
41      protected ClassContext classContext;
42  
43      /**
44       * The compilation unit context (for the whole source program or file).
45       */
46      protected CompilationUnitContext compilationUnitContext;
47  
48      /**
49       * Map of (local variable, formal parameters, type) names to their definitions.
50       */
51      protected Map<String, IDefn> entries;
52  
53      /**
54       * Constructs a Context.
55       *
56       * @param surrounding            the surrounding context (scope).
57       * @param classContext           the surrounding class context.
58       * @param compilationUnitContext the compilation unit context (for the whole source program or
59       *                               file).
60       */
61      protected Context(Context surrounding, ClassContext classContext,
62                        CompilationUnitContext compilationUnitContext) {
63          this.surroundingContext = surrounding;
64          this.classContext = classContext;
65          this.compilationUnitContext = compilationUnitContext;
66          this.entries = new HashMap<String, IDefn>();
67      }
68  
69      /**
70       * Adds an entry to the symbol table, binding a name to its definition in the current context.
71       *
72       * @param line       the line number of the entry.
73       * @param name       the name being declared.
74       * @param definition and its definition.
75       */
76      public void addEntry(int line, String name, IDefn definition) {
77          if (entries.containsKey(name)) {
78              JAST.compilationUnit.reportSemanticError(line, "redefining name: " + name);
79          } else {
80              entries.put(name, definition);
81          }
82      }
83  
84      /**
85       * Returns the definition for a name in the current (or surrounding) context, or null.
86       *
87       * @param name the name whose definition we're looking for.
88       * @return the definition for a name in the current (or surrounding) context, or null.
89       */
90      public IDefn lookup(String name) {
91          IDefn iDefn = (IDefn) entries.get(name);
92          return iDefn != null ?
93                  iDefn : surroundingContext != null ? surroundingContext.lookup(name) : null;
94      }
95  
96      /**
97       * Returns the definition for a type name in the compilation unit context, or null.
98       *
99       * @param name the name of the type whose definition we're looking for.
100      * @return the definition for a type name in the compilation unit context, or null.
101      */
102     public Type lookupType(String name) {
103         TypeNameDefn defn = (TypeNameDefn) compilationUnitContext.lookup(name);
104         return defn == null ? null : defn.type();
105     }
106 
107     /**
108      * Adds the given type to the compilation unit context.
109      *
110      * @param line line number of type declaration.
111      * @param type the type we are declaring.
112      */
113     public void addType(int line, Type type) {
114         IDefn iDefn = new TypeNameDefn(type);
115         compilationUnitContext.addEntry(line, type.simpleName(), iDefn);
116         if (!type.toString().equals(type.simpleName())) {
117             compilationUnitContext.addEntry(line, type.toString(), iDefn);
118         }
119     }
120 
121     /**
122      * Returns the type that defines this context (used principally for checking accessibility).
123      *
124      * @return the type that defines this context.
125      */
126     public Type definingType() {
127         return ((JTypeDecl) classContext.definition()).thisType();
128     }
129 
130     /**
131      * Returns the surrounding context (scope) in the stack of contexts.
132      *
133      * @return the surrounding context.
134      */
135     public Context surroundingContext() {
136         return surroundingContext;
137     }
138 
139     /**
140      * Returns the surrounding class context.
141      *
142      * @return the surrounding class context.
143      */
144     public ClassContext classContext() {
145         return classContext;
146     }
147 
148     /**
149      * Returns the surrounding compilation unit context. This is where imported types and other
150      * types defined in the compilation unit are declared.
151      *
152      * @return the compilation unit context.
153      */
154     public CompilationUnitContext compilationUnitContext() {
155         return compilationUnitContext;
156     }
157 
158     /**
159      * Returns the closest surrounding method context, or null (if we are not within a method).
160      *
161      * @return the closest surrounding method context, or null.
162      */
163     public MethodContext methodContext() {
164         Context context = this;
165         while (context != null && !(context instanceof MethodContext)) {
166             context = context.surroundingContext();
167         }
168         return (MethodContext) context;
169     }
170 
171     /**
172      * Returns a set containing the names declared in this context.
173      *
174      * @return a set containing the names declared in this context.
175      */
176     public Set<String> names() {
177         return entries.keySet();
178     }
179 
180     /**
181      * Adds information pertaining to this context to the given JSON element.
182      *
183      * @param json JSON element.
184      */
185     public void toJSON(JSONElement json) {
186         // Nothing here.
187     }
188 }
189 
190 /**
191  * The compilation unit context is always the outermost context and is where imported types and
192  * locally defined types (classes) are declared.
193  */
194 class CompilationUnitContext extends Context {
195     /**
196      * Constructs a new compilation unit context.
197      */
198     public CompilationUnitContext() {
199         super(null, null, null);
200         compilationUnitContext = this;
201     }
202 
203     /**
204      * {@inheritDoc}
205      */
206     public void toJSON(JSONElement json) {
207         JSONElement e = new JSONElement();
208         json.addChild("CompilationUnitContext", e);
209         if (entries != null) {
210             ArrayList<String> value = new ArrayList<String>();
211             for (String name : names()) {
212                 value.add(String.format("\"%s\"", name));
213             }
214             e.addAttribute("entries", value);
215         }
216     }
217 }
218 
219 /**
220  * Represents the context (scope, environment, symbol table) for a type, for example a class, in
221  * j--. It also keeps track of its surrounding context(s) and the type whose context it represents.
222  */
223 class ClassContext extends Context {
224     /**
225      * AST node of the type that this class represents.
226      */
227     private JAST definition;
228 
229     /**
230      * Constructs a class context.
231      *
232      * @param definition  the AST node of the type that this class represents.
233      * @param surrounding the surrounding context(s).
234      */
235     public ClassContext(JAST definition, Context surrounding) {
236         super(surrounding, null, surrounding.compilationUnitContext());
237         classContext = this;
238         this.definition = definition;
239     }
240 
241     /**
242      * Returns the AST node of the type defined by this class.
243      *
244      * @return the AST of the type defined by this class.
245      */
246     public JAST definition() {
247         return definition;
248     }
249 
250     /**
251      * {@inheritDoc}
252      */
253     public void toJSON(JSONElement json) {
254         JSONElement e = new JSONElement();
255         json.addChild("ClassContext", e);
256     }
257 }
258 
259 /**
260  * A local context is a context (scope) in which local variables (including formal parameters)
261  * can be declared. Local variables are allocated at fixed offsets from the base of the current
262  * method's stack frame; this is done during analysis. The definitions for local variables record
263  * these offsets. The offsets are used in code generation.
264  */
265 class LocalContext extends Context {
266     /**
267      * Next offset for a local variable.
268      */
269     protected int offset;
270 
271     /**
272      * Constructs a local context. A local context is constructed for each block.
273      *
274      * @param surrounding the surrounding context.
275      */
276     public LocalContext(Context surrounding) {
277         super(surrounding, surrounding.classContext(), surrounding.compilationUnitContext());
278         offset = (surrounding instanceof LocalContext) ? ((LocalContext) surrounding).offset() : 0;
279     }
280 
281     /**
282      * Returns the "next" offset. Not to be used for allocating new offsets (the nextOffset()
283      * method is used for that).
284      *
285      * @return the next available offset.
286      */
287     public int offset() {
288         return offset;
289     }
290 
291     /**
292      * Allocates and returns a new offset (eg, for a parameter or local variable).
293      *
294      * @return the next allocated offset.
295      */
296     public int nextOffset() {
297         return offset++;
298     }
299 
300     /**
301      * {@inheritDoc}
302      */
303     public void toJSON(JSONElement json) {
304         JSONElement e = new JSONElement();
305         json.addChild("LocalContext", e);
306         if (entries != null) {
307             ArrayList<String> value = new ArrayList<String>();
308             for (String name : names()) {
309                 IDefn defn = entries.get(name);
310                 if (defn instanceof LocalVariableDefn) {
311                     int offset = ((LocalVariableDefn) defn).offset();
312                     value.add(String.format("[\"%s\", \"%s\"]", name, offset));
313                 }
314             }
315             e.addAttribute("entries", value);
316         }
317     }
318 }
319 
320 /**
321  * A method context is where formal parameters are declared. Also, it's where we start computing
322  * the offsets for local variables (formal parameters included), which are allocated in the
323  * current stack frame (for a method invocation).
324  */
325 class MethodContext extends LocalContext {
326     /**
327      * Is this method static?
328      */
329     private boolean isStatic;
330 
331     /**
332      * Return type of this method.
333      */
334     private Type methodReturnType;
335 
336     /**
337      * Does (non-void) method have at least one return?
338      */
339     private boolean hasReturnStatement;
340 
341     /**
342      * Constructs a method context.
343      *
344      * @param surrounding      the surrounding (class) context.
345      * @param isStatic         is this method static?
346      * @param methodReturnType return type of this method.
347      */
348     public MethodContext(Context surrounding, boolean isStatic, Type methodReturnType) {
349         super(surrounding);
350         super.offset = 0;
351         this.isStatic = isStatic;
352         this.methodReturnType = methodReturnType;
353         hasReturnStatement = false;
354     }
355 
356     /**
357      * Returns true if this is a static method, and false otherwise.
358      *
359      * @return true if this is a static method, and false otherwise.
360      */
361     public boolean isStatic() {
362         return isStatic;
363     }
364 
365     /**
366      * Records fact that (non-void) method has at least one return.
367      */
368     public void confirmMethodHasReturn() {
369         hasReturnStatement = true;
370     }
371 
372     /**
373      * Returns true if this (non-void) method has at least one return, and false otherwise.
374      *
375      * @return true if this (non-void) method has at least one return, and false otherwise.
376      */
377     public boolean methodHasReturn() {
378         return hasReturnStatement;
379     }
380 
381     /**
382      * Returns the return type of this method.
383      *
384      * @return the return type of this method.
385      */
386     public Type methodReturnType() {
387         return methodReturnType;
388     }
389 
390     /**
391      * {@inheritDoc}
392      */
393     public void toJSON(JSONElement json) {
394         JSONElement e = new JSONElement();
395         json.addChild("MethodContext", e);
396         if (entries != null) {
397             ArrayList<String> value = new ArrayList<String>();
398             for (String name : names()) {
399                 IDefn defn = entries.get(name);
400                 if (defn instanceof LocalVariableDefn) {
401                     int offset = ((LocalVariableDefn) defn).offset();
402                     value.add(String.format("[\"%s\", \"%s\"]", name, offset));
403                 }
404             }
405             e.addAttribute("entries", value);
406         }
407     }
408 }
409