001: // Copyright (c) 2003 Per M.A. Bothner.
002: // This is free software; for terms and warranty disclaimer see ./COPYING.
003:
004: package gnu.expr;
005:
006: import java.util.Hashtable;
007: import java.io.Externalizable;
008: import gnu.bytecode.Type;
009: import gnu.mapping.*;
010:
011: public class FindCapturedVars extends ExpWalker {
012: public static void findCapturedVars(Expression exp, Compilation comp) {
013: FindCapturedVars walker = new FindCapturedVars();
014: walker.setContext(comp);
015: exp.walk(walker);
016: }
017:
018: protected Expression walkApplyExp(ApplyExp exp) {
019: boolean skipFunc = false;
020: // If the func is bound to a module-level known function, and it
021: // doesn't need a closure yet (i.e. could be compiled to a static
022: // method), don't walk the function, since that might force it to
023: // unnecessarily get "captured" which might force the current
024: // function to require a closure. That would be wasteful if the
025: // alternative is to just call func using invokestatic. (It is
026: // possible that we later find out that func needs a static link,
027: // in which case the current function does as well; this is taken
028: // care of by calling setCallersNeedStaticLink in LambdaExp.)
029: if (exp.func instanceof ReferenceExp
030: && Compilation.defaultCallConvention <= Compilation.CALL_WITH_RETURN) {
031: Declaration decl = Declaration
032: .followAliases(((ReferenceExp) exp.func).binding);
033: if (decl != null && decl.context instanceof ModuleExp
034: && !decl.isPublic()
035: && !decl.getFlag(Declaration.NONSTATIC_SPECIFIED)) {
036: Expression value = decl.getValue();
037: if (value instanceof LambdaExp) {
038: LambdaExp lexp = (LambdaExp) value;
039: if (!lexp.getNeedsClosureEnv())
040: skipFunc = true;
041: }
042: }
043: }
044: if (!skipFunc)
045: exp.func = (Expression) exp.func.walk(this );
046: if (exitValue == null)
047: exp.args = walkExps(exp.args);
048: return exp;
049: }
050:
051: public void walkDefaultArgs(LambdaExp exp) {
052: if (exp.defaultArgs == null)
053: return;
054:
055: super .walkDefaultArgs(exp);
056:
057: // Check if any default expression "captured" a parameters.
058: // If so, evaluating a default expression cannot be done until the
059: // heapFrame is allocated in the main-method. But in most cases, a
060: // default expression will not contain a nested scope, hence no
061: // capture, hence we can generate efficient code to handle optional
062: // arguments.
063: for (Declaration param = exp.firstDecl(); param != null; param = param
064: .nextDecl()) {
065: if (!param.isSimple()) {
066: exp.setFlag(true, LambdaExp.DEFAULT_CAPTURES_ARG);
067: break;
068: }
069: }
070: }
071:
072: protected Expression walkClassExp(ClassExp exp) {
073: Expression ret = super .walkClassExp(exp);
074: // Make sure <init> has been declared, in case we need to invoke it.
075: // However, this is only safe to do if ! getNeedsClosureEnv(). FIXME.
076: if (!exp.explicitInit && !exp.getNeedsClosureEnv())
077: Compilation.getConstructor(exp.instanceType, exp);
078: return ret;
079: }
080:
081: protected Expression walkModuleExp(ModuleExp exp) {
082: ModuleExp saveModule = currentModule;
083: Hashtable saveDecls = unknownDecls;
084: currentModule = exp;
085: unknownDecls = null;
086: try {
087: return walkLambdaExp(exp);
088: } finally {
089: currentModule = saveModule;
090: unknownDecls = saveDecls;
091: }
092: }
093:
094: protected Expression walkFluidLetExp(FluidLetExp exp) {
095: for (Declaration decl = exp.firstDecl(); decl != null; decl = decl
096: .nextDecl()) {
097: if (decl.base == null) {
098: Declaration bind = allocUnboundDecl(decl.getSymbol(),
099: false);
100: capture(bind);
101: decl.base = bind;
102: }
103: }
104: return super .walkLetExp(exp);
105: }
106:
107: protected Expression walkLetExp(LetExp exp) {
108: if (exp.body instanceof BeginExp) {
109: // Optimize "letrec"-like forms.
110: // If init[i] is the magic QuoteExp.nullExp, and the real value
111: // is a LambdaExp or a QuoteExp, we're not going to get weird
112: // order-dependencies, and it is safe to transform it to a regular let.
113: // It's also necessary in the case of a LambdaExp if it shares
114: // a field with the declaration (see LambdaExp.allocFieldField),
115: // since assigning the nullExp can clobber the field after it has
116: // been initialized with a ModuleMethod.
117: Expression[] inits = exp.inits;
118: int len = inits.length;
119: Expression[] exps = ((BeginExp) exp.body).exps;
120: int init_index = 0;
121: Declaration decl = exp.firstDecl();
122: for (int begin_index = 0; begin_index < exps.length
123: && init_index < len; begin_index++) {
124: Expression st = exps[begin_index];
125: if (st instanceof SetExp) {
126: SetExp set = (SetExp) st;
127: if (set.binding == decl
128: && inits[init_index] == QuoteExp.nullExp
129: && set.isDefining()) {
130: Expression new_value = set.new_value;
131: if ((new_value instanceof QuoteExp || new_value instanceof LambdaExp)
132: && decl.getValue() == new_value) {
133: inits[init_index] = new_value;
134: exps[begin_index] = QuoteExp.voidExp;
135: }
136: init_index++;
137: decl = decl.nextDecl();
138: }
139: }
140: }
141: }
142: return super .walkLetExp(exp);
143: }
144:
145: public void capture(Declaration decl) {
146: if (!(decl.getCanRead() || decl.getCanCall()))
147: return;
148: if (decl.field != null && decl.field.getStaticFlag())
149: return;
150:
151: LambdaExp curLambda = getCurrentLambda();
152: LambdaExp declLambda = decl.getContext().currentLambda();
153:
154: // If curLambda is inlined, the function that actually needs a closure
155: // is its caller. We get its caller using returnContinuation.context.
156: // A complication is that we can have a chain of functions that
157: // recursively call each other, and are hence inlined in each other.
158: // Since a function is only inlined if it has a single call site,
159: // that means there is actually no way to actually enter the chain;
160: // i.e. none of the inlined functions can actually get called.
161: // However, we have to watch out for this possibility, or the loop
162: // here will run forever. For us to have a cycle, all of the functions
163: // must have the same parent. If the loop is executed more times
164: // than the number of child functions of the parent, then we know we
165: // have a cycle.
166: // The `chain' variable is used to catch infinite inline loops by
167: // iterating through the parents children.
168: LambdaExp oldParent = null;
169: LambdaExp chain = null;
170: while (curLambda != declLambda && curLambda.getInlineOnly()) {
171: LambdaExp curParent = curLambda.outerLambda();
172: if (curParent != oldParent) {
173: // Reset the chain.
174: chain = curParent.firstChild;
175: oldParent = curParent;
176: }
177: ApplyExp curReturn = curLambda.returnContinuation;
178: if (chain == null || curReturn == null) {
179: // Infinite loop of functions that are inlined in each other.
180: curLambda.setCanCall(false);
181: return;
182: }
183: curLambda = curReturn.context;
184: chain = chain.nextSibling;
185: }
186: if (comp.usingCPStyle()) {
187: if (curLambda instanceof ModuleExp)
188: return;
189: } else if (curLambda == declLambda)
190: return;
191:
192: // The logic here is similar to that of decl.ignorable():
193: Expression value = decl.getValue();
194: LambdaExp declValue;
195: if (value == null || !(value instanceof LambdaExp))
196: declValue = null;
197: else {
198: declValue = (LambdaExp) value;
199: if (declValue.getInlineOnly())
200: return;
201: if (declValue.isHandlingTailCalls())
202: declValue = null;
203: else if (declValue == curLambda && !decl.getCanRead())
204: return;
205: }
206:
207: if (decl.getFlag(Declaration.IS_UNKNOWN)) {
208: // Don't create a closure for a static function/class.
209: for (LambdaExp parent = curLambda;; parent = parent
210: .outerLambda()) {
211: if (parent == declLambda)
212: break;
213: if (parent.nameDecl != null
214: && parent.nameDecl
215: .getFlag(Declaration.STATIC_SPECIFIED)) {
216: decl.setFlag(Declaration.STATIC_SPECIFIED);
217: break;
218: }
219: }
220: }
221: if (decl.base != null) {
222: decl.base.setCanRead(true);
223: capture(decl.base);
224: } else if (decl.getCanRead() || declValue == null) {
225: if (!decl.isStatic()) {
226: LambdaExp heapLambda = curLambda;
227: heapLambda.setImportsLexVars();
228: LambdaExp parent = heapLambda.outerLambda();
229: for (LambdaExp outer = parent; outer != declLambda
230: && outer != null;) {
231: heapLambda = outer;
232: if (!decl.getCanRead() && declValue == outer)
233: break;
234: Declaration heapDecl = heapLambda.nameDecl;
235: if (heapDecl != null
236: && heapDecl
237: .getFlag(Declaration.STATIC_SPECIFIED)) {
238: comp.error('e', "static "
239: + heapLambda.getName()
240: + " references non-static "
241: + decl.getName());
242: }
243: heapLambda.setNeedsStaticLink();
244: outer = heapLambda.outerLambda();
245: }
246: }
247:
248: declLambda.capture(decl);
249: }
250: }
251:
252: Hashtable unknownDecls = null;
253: ModuleExp currentModule = null;
254:
255: Declaration allocUnboundDecl(Object name, boolean function) {
256: Declaration decl;
257: Object key = name;
258: if (function && name instanceof Symbol) {
259: if (!getCompilation().getLanguage()
260: .hasSeparateFunctionNamespace())
261: function = false;
262: else
263: // FIXME maybe just use gnu.lists.Pair and remove KeyPair class?
264: key = new KeyPair((Symbol) name,
265: EnvironmentKey.FUNCTION);
266: }
267: if (unknownDecls == null) {
268: unknownDecls = new Hashtable(100);
269: decl = null;
270: } else
271: decl = (Declaration) unknownDecls.get(key);
272: if (decl == null) {
273: decl = currentModule.addDeclaration(name);
274: decl.setSimple(false);
275: decl.setPrivate(true);
276: if (function)
277: decl.setProcedureDecl(true);
278: if (currentModule.isStatic())
279: decl.setFlag(Declaration.STATIC_SPECIFIED);
280: decl.setCanRead(true);
281: decl.setFlag(Declaration.IS_UNKNOWN);
282: decl.setIndirectBinding(true);
283: unknownDecls.put(key, decl);
284: }
285: return decl;
286: }
287:
288: protected Expression walkReferenceExp(ReferenceExp exp) {
289: Declaration decl = exp.getBinding();
290: if (decl == null) {
291: decl = allocUnboundDecl(exp.getSymbol(), exp
292: .isProcedureName());
293: exp.setBinding(decl);
294: }
295: if (decl.getFlag(Declaration.IS_UNKNOWN)) {
296: Type type = getCompilation().getLanguage().getTypeFor(exp);
297: if (type instanceof Externalizable
298: && !exp.getDontDereference())
299: return new QuoteExp(type);
300:
301: if (comp.getBooleanOption("warn-undefined-variable", false)) {
302: Object resolved = comp.resolve(exp.getSymbol(), exp
303: .isProcedureName());
304: if (resolved == null)
305: comp.error('w', "no declaration seen for "
306: + exp.getName(), exp);
307: }
308: }
309:
310: capture(exp.contextDecl(), decl);
311: return exp;
312: }
313:
314: void capture(Declaration containing, Declaration decl) {
315: if (decl.isAlias() && decl.value instanceof ReferenceExp) {
316: ReferenceExp rexp = (ReferenceExp) decl.value;
317: Declaration orig = rexp.binding;
318: if (orig != null
319: && (containing == null || !orig.needsContext())) {
320: capture(rexp.contextDecl(), orig);
321: return;
322: }
323: }
324: if (containing != null && decl.needsContext())
325: capture(containing);
326: else
327: capture(decl);
328: }
329:
330: protected Expression walkThisExp(ThisExp exp) {
331: if (exp.isForContext()) {
332: // This is an extension used by define_syntax.
333: // FIXME - not really right, but works in simple cases.
334: getCurrentLambda().setImportsLexVars();
335: return exp;
336: } else
337: return walkReferenceExp(exp);
338: }
339:
340: protected Expression walkSetExp(SetExp exp) {
341: Declaration decl = exp.binding;
342: if (decl == null) {
343: decl = allocUnboundDecl(exp.getSymbol(), exp.isFuncDef());
344: exp.binding = decl;
345: }
346: if (!decl.ignorable()) {
347: if (!exp.isDefining())
348: decl = Declaration.followAliases(decl);
349: capture(exp.contextDecl(), decl);
350: }
351: return super.walkSetExp(exp);
352: }
353:
354: }
|