FindCapturedVars


1   // Copyright (c) 2003  Per M.A. Bothner.
2   // This is free software;  for terms and warranty disclaimer see ./COPYING.
3   
4   package gnu.expr;
5   import java.util.Hashtable  ;
6   import java.io.Externalizable  ;
7   import gnu.bytecode.Type;
8   import gnu.mapping.*;
9   
10  public class FindCapturedVars extends ExpWalker
11  {
12    public static void findCapturedVars (Expression exp, Compilation comp)
13    {
14      FindCapturedVars walker = new FindCapturedVars();
15      walker.setContext(comp);
16      exp.walk(walker);
17    }
18  
19    protected Expression walkApplyExp (ApplyExp exp)
20    {
21      boolean skipFunc = false;
22      // If the func is bound to a module-level known function, and it
23      // doesn't need a closure yet (i.e. could be compiled to a static
24      // method), don't walk the function, since that might force it to
25      // unnecessarily get "captured" which might force the current
26      // function to require a closure.  That would be wasteful if the
27      // alternative is to just call func using invokestatic.  (It is
28      // possible that we later find out that func needs a static link,
29      // in which case the current function does as well;  this is taken
30      // care of by calling setCallersNeedStaticLink in LambdaExp.)
31      if (exp.func instanceof ReferenceExp
32      && Compilation.defaultCallConvention <= Compilation.CALL_WITH_RETURN)
33        {
34      Declaration decl
35        = Declaration.followAliases(((ReferenceExp) exp.func).binding);
36      if (decl != null && decl.context instanceof ModuleExp
37              && ! decl.isPublic()
38              && ! decl.getFlag(Declaration.NONSTATIC_SPECIFIED))
39        {
40          Expression value = decl.getValue();
41          if (value instanceof LambdaExp)
42            {
43          LambdaExp lexp = (LambdaExp) value;
44          if (! lexp.getNeedsClosureEnv())
45            skipFunc = true;
46            }
47        }
48        }
49      if (! skipFunc)
50        exp.func = (Expression) exp.func.walk(this);
51      if (exitValue == null)
52        exp.args = walkExps(exp.args);
53      return exp;
54    }
55  
56    public void walkDefaultArgs (LambdaExp exp)
57    {
58      if (exp.defaultArgs == null)
59        return;
60  
61      super.walkDefaultArgs(exp);
62  
63      // Check if any default expression "captured" a parameters.
64      // If so, evaluating a default expression cannot be done until the
65      // heapFrame is allocated in the main-method.  But in most cases, a
66      // default expression will not contain a nested scope, hence no
67      // capture, hence we can generate efficient code to handle optional
68      // arguments.
69      for (Declaration param = exp.firstDecl();
70       param != null; param = param.nextDecl())
71        {
72      if (! param.isSimple())
73        {
74          exp.setFlag(true, LambdaExp.DEFAULT_CAPTURES_ARG);
75          break;
76        }
77        }
78    }
79  
80    protected Expression walkClassExp (ClassExp exp)
81    {
82      Expression ret = super.walkClassExp(exp);
83      // Make sure <init> has been declared, in case we need to invoke it.
84      // However, this is only safe to do if ! getNeedsClosureEnv().  FIXME.
85      if (! exp.explicitInit && ! exp.getNeedsClosureEnv())
86        Compilation.getConstructor(exp.instanceType, exp);
87      return ret;
88    }
89  
90    protected Expression walkModuleExp (ModuleExp exp)
91    {
92      ModuleExp saveModule = currentModule;
93      Hashtable   saveDecls = unknownDecls;
94      currentModule = exp;
95      unknownDecls = null;
96      try
97        {
98      return walkLambdaExp(exp);
99        }
100     finally
101       {
102     currentModule = saveModule;
103     unknownDecls = saveDecls;
104       }
105   }
106 
107   protected Expression walkFluidLetExp (FluidLetExp exp)
108   {
109     for (Declaration decl = exp.firstDecl(); decl != null; decl = decl.nextDecl())
110       {
111         if (decl.base == null)
112           {
113             Declaration bind = allocUnboundDecl(decl.getSymbol(), false);
114             capture(bind);
115             decl.base = bind;
116           }
117       }
118     return super.walkLetExp(exp);
119   }
120 
121   protected Expression walkLetExp (LetExp exp)
122   {
123     if (exp.body instanceof BeginExp)
124       {
125     // Optimize "letrec"-like forms.
126     // If init[i] is the magic QuoteExp.nullExp, and the real value
127     // is a LambdaExp or a QuoteExp, we're not going to get weird
128     // order-dependencies, and it is safe to transform it to a regular let.
129     // It's also necessary in the case of a LambdaExp if it shares
130     // a field with the declaration (see LambdaExp.allocFieldField),
131     // since assigning the nullExp can clobber the field after it has
132     // been initialized with a ModuleMethod.
133     Expression[] inits = exp.inits;
134     int len = inits.length;
135     Expression[] exps = ((BeginExp) exp.body).exps;
136     int init_index = 0;
137     Declaration decl = exp.firstDecl();
138     for (int begin_index = 0;
139          begin_index < exps.length && init_index < len;
140          begin_index++)
141       {
142         Expression st = exps[begin_index];
143         if (st instanceof SetExp)
144           {
145         SetExp set = (SetExp) st;
146         if (set.binding == decl
147             && inits[init_index] == QuoteExp.nullExp
148             && set.isDefining())
149           {
150             Expression new_value = set.new_value;
151             if ((new_value instanceof QuoteExp
152              || new_value instanceof LambdaExp)
153             && decl.getValue() == new_value)
154               {
155             inits[init_index] = new_value;
156             exps[begin_index] = QuoteExp.voidExp;
157               }
158             init_index++;
159             decl = decl.nextDecl();
160           }
161           }
162       }
163       }
164     return super.walkLetExp(exp);
165   }
166 
167   public void capture(Declaration decl)
168   {
169     if (! (decl.getCanRead() || decl.getCanCall()))
170       return;
171     if (decl.field != null && decl.field.getStaticFlag())
172       return;
173 
174     LambdaExp curLambda = getCurrentLambda ();
175     LambdaExp declLambda = decl.getContext().currentLambda ();
176 
177     // If curLambda is inlined, the function that actually needs a closure
178     // is its caller.  We get its caller using returnContinuation.context.
179     // A complication is that we can have a chain of functions that
180     // recursively call each other, and are hence inlined in each other.
181     // Since a function is only inlined if it has a single call site,
182     // that means there is actually no way to actually enter the chain;
183     // i.e. none of the inlined functions can actually get called.
184     // However, we have to watch out for this possibility, or the loop
185     // here will run forever.  For us to have a cycle, all of the functions
186     // must have the same parent.  If the loop is executed more times
187     // than the number of child functions of the parent, then we know we
188     // have a cycle.
189     // The `chain' variable is used to catch infinite inline loops by
190     // iterating through the parents children.
191     LambdaExp oldParent = null;
192     LambdaExp chain = null;
193     while (curLambda != declLambda && curLambda.getInlineOnly())
194       {
195         LambdaExp curParent = curLambda.outerLambda();
196         if (curParent != oldParent)
197           {
198             // Reset the chain.
199             chain = curParent.firstChild;
200             oldParent = curParent;
201           }
202         ApplyExp curReturn = curLambda.returnContinuation;
203         if (chain == null || curReturn == null)
204           {
205             // Infinite loop of functions that are inlined in each other.
206             curLambda.setCanCall(false);
207             return;
208         }
209         curLambda = curReturn.context;
210         chain = chain.nextSibling;
211       }
212     if (comp.usingCPStyle())
213       {
214     if (curLambda instanceof ModuleExp)
215       return;
216       }
217     else
218       if (curLambda == declLambda)
219     return;
220 
221     // The logic here is similar to that of decl.ignorable():
222     Expression value = decl.getValue();
223     LambdaExp declValue;
224     if (value == null || ! (value instanceof LambdaExp))
225       declValue = null;
226     else
227       {
228         declValue = (LambdaExp) value;
229         if (declValue.getInlineOnly())
230           return;
231         if (declValue.isHandlingTailCalls())
232           declValue = null;
233     else if (declValue == curLambda && ! decl.getCanRead())
234           return;
235       }
236 
237     if (decl.getFlag(Declaration.IS_UNKNOWN))
238       {
239     // Don't create a closure for a static function/class.
240     for (LambdaExp parent = curLambda; ; parent = parent.outerLambda())
241       {
242         if (parent == declLambda)
243           break;
244         if (parent.nameDecl != null
245         && parent.nameDecl.getFlag(Declaration.STATIC_SPECIFIED))
246           {
247         decl.setFlag(Declaration.STATIC_SPECIFIED);
248         break;
249           }
250       }
251       }
252     if (decl.base != null)
253       {
254     decl.base.setCanRead(true);
255     capture(decl.base);
256       }
257     else if (decl.getCanRead() || declValue == null)
258       {
259     if (! decl.isStatic())
260       {
261         LambdaExp heapLambda = curLambda;
262         heapLambda.setImportsLexVars();
263         LambdaExp parent = heapLambda.outerLambda();
264         for (LambdaExp outer = parent;  outer != declLambda && outer != null; )
265           {
266         heapLambda = outer;
267         if (! decl.getCanRead() && declValue == outer)
268           break;
269         Declaration heapDecl = heapLambda.nameDecl;
270         if (heapDecl != null
271             && heapDecl.getFlag(Declaration.STATIC_SPECIFIED))
272           {
273             comp.error('e', "static " + heapLambda.getName()
274                    + " references non-static " + decl.getName());
275           }
276         heapLambda.setNeedsStaticLink();
277         outer = heapLambda.outerLambda();
278           }
279       }
280 
281         declLambda.capture(decl);
282       }
283   }
284 
285   Hashtable   unknownDecls = null;
286   ModuleExp currentModule = null;
287 
288   Declaration allocUnboundDecl(Object   name, boolean function)
289   {
290     Declaration decl;
291     Object   key = name;
292     if (function && name instanceof Symbol)
293       {
294     if (! getCompilation().getLanguage().hasSeparateFunctionNamespace())
295       function = false;
296     else // FIXME maybe just use gnu.lists.Pair and remove KeyPair class?
297       key = new KeyPair((Symbol) name, EnvironmentKey.FUNCTION);
298       }
299     if (unknownDecls == null)
300       {
301     unknownDecls = new Hashtable  (100);
302     decl = null;
303       }
304     else
305       decl = (Declaration) unknownDecls.get(key);
306     if (decl == null)
307       {
308     decl = currentModule.addDeclaration(name);
309     decl.setSimple(false);
310     decl.setPrivate(true);
311     if (function)
312       decl.setProcedureDecl(true);
313     if (currentModule.isStatic())
314       decl.setFlag(Declaration.STATIC_SPECIFIED);
315     decl.setCanRead(true);
316     decl.setFlag(Declaration.IS_UNKNOWN);
317     decl.setIndirectBinding(true);
318     unknownDecls.put(key, decl);
319       }
320     return decl;
321   }
322 
323   protected Expression walkReferenceExp (ReferenceExp exp)
324   {
325     Declaration decl = exp.getBinding();
326     if (decl == null)
327       {
328     decl = allocUnboundDecl(exp.getSymbol(),
329                 exp.isProcedureName());
330     exp.setBinding(decl);
331       }
332     if (decl.getFlag(Declaration.IS_UNKNOWN))
333       {
334     Type type = getCompilation().getLanguage().getTypeFor(exp);
335     if (type instanceof Externalizable   && ! exp.getDontDereference())
336       return new QuoteExp(type);
337 
338     if (comp.getBooleanOption("warn-undefined-variable", false))
339       {
340         Object   resolved
341           = comp.resolve(exp.getSymbol(), exp.isProcedureName());
342         if (resolved == null)
343           comp.error('w', "no declaration seen for "+exp.getName(), exp);
344       }
345       }
346 
347     capture(exp.contextDecl(), decl);
348     return exp;
349   }
350 
351   void capture (Declaration containing, Declaration decl)
352   {
353     if (decl.isAlias() && decl.value instanceof ReferenceExp)
354       {
355     ReferenceExp rexp = (ReferenceExp) decl.value;
356     Declaration orig = rexp.binding;
357     if (orig != null
358         && (containing == null || ! orig.needsContext()))
359       {
360         capture(rexp.contextDecl(), orig);
361         return;
362       }
363       }
364     if (containing != null && decl.needsContext())
365       capture(containing);
366     else
367       capture(decl);
368   }
369 
370   protected Expression walkThisExp (ThisExp exp)
371   {
372     if (exp.isForContext())
373       {
374         // This is an extension used by define_syntax.
375         // FIXME - not really right, but works in simple cases.
376         getCurrentLambda ().setImportsLexVars();
377         return exp;
378       }
379     else
380       return walkReferenceExp (exp);
381   }
382 
383   protected Expression walkSetExp (SetExp exp)
384   {
385     Declaration decl = exp.binding;
386     if (decl == null)
387       {
388     decl = allocUnboundDecl(exp.getSymbol(), exp.isFuncDef());
389     exp.binding = decl;
390       }
391     if (! decl.ignorable())
392       {
393     if (! exp.isDefining())
394       decl = Declaration.followAliases(decl);
395     capture(exp.contextDecl(), decl);
396       }
397     return super.walkSetExp(exp);
398   }
399 
400 }
401
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags