1 // Copyright (c) 2003, 2009 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 import gnu.text.SourceLocator; 10 11 public class FindCapturedVars extends ExpExpVisitor<Void> 12 { findCapturedVars(Expression exp, Compilation comp)13 public static void findCapturedVars (Expression exp, Compilation comp) 14 { 15 FindCapturedVars visitor = new FindCapturedVars(); 16 visitor.setContext(comp); 17 exp.visit(visitor, null); 18 } 19 20 int backJumpPossible = 0; 21 visitDeclarationType(Declaration decl)22 protected final void visitDeclarationType (Declaration decl) 23 { 24 // If decl.typeExp references a ClassExp then we might get a 25 // needless capture of the ClassExp's declarations. 26 // For now ignore the issue ... FIXME 27 } 28 visitApplyExp(ApplyExp exp, Void ignored)29 protected Expression visitApplyExp (ApplyExp exp, Void ignored) 30 { 31 int oldBackJumpPossible = backJumpPossible; 32 boolean skipFunc = false; 33 boolean skipArgs = false; 34 // If the func is bound to a module-level known function, and it 35 // doesn't need a closure yet (i.e. could be compiled to a static 36 // method), don't visit the function, since that might force it to 37 // unnecessarily get "captured" which might force the current 38 // function to require a closure. That would be wasteful if the 39 // alternative is to just call func using invokestatic. (It is 40 // possible that we later find out that func needs a static link, 41 // in which case the current function does as well; this is taken 42 // care of by calling setCallersNeedStaticLink in LambdaExp.) 43 // (This code may be less useful now that --module-static is the default.) 44 if (exp.func instanceof ReferenceExp 45 && getCompilation().currentCallConvention() <= Compilation.CALL_WITH_RETURN) 46 { 47 Declaration decl 48 = Declaration.followAliases(((ReferenceExp) exp.func).binding); 49 if (decl != null && decl.context instanceof ModuleExp 50 && ! decl.isPublic() 51 && ! decl.getFlag(Declaration.NONSTATIC_SPECIFIED)) 52 { 53 Expression value = decl.getValue(); 54 if (value instanceof LambdaExp) 55 { 56 LambdaExp lexp = (LambdaExp) value; 57 if (! lexp.getNeedsClosureEnv() 58 && ! lexp.getFlag(LambdaExp.HAS_NONTRIVIAL_PATTERN)) 59 skipFunc = true; 60 } 61 } 62 } 63 // Similar hack for constructor calls, but here we want to 64 // avoid visiting the type argument. 65 else if (exp.func instanceof QuoteExp && exp.getArgCount() > 0) 66 { 67 Object val = ((QuoteExp) exp.func).getValue(); 68 Expression arg0 = exp.getArg(0); 69 if (val instanceof PrimProcedure 70 && ((PrimProcedure) val).isConstructor() 71 && arg0 instanceof ReferenceExp) 72 { 73 Declaration decl 74 = Declaration.followAliases(((ReferenceExp) arg0).binding); 75 if (decl != null && decl.context == comp.getModule() 76 && ! decl.getFlag(Declaration.NONSTATIC_SPECIFIED)) 77 { 78 Expression value = decl.getValue(); 79 if (value instanceof ClassExp) 80 { 81 Expression[] args = exp.getArgs(); 82 LambdaExp lexp = (LambdaExp) value; 83 if (! lexp.getNeedsClosureEnv()) 84 { 85 decl.addCaller(exp); 86 for (int i = 1; i < args.length; i++) 87 args[i].visit(this, ignored); 88 skipFunc = skipArgs = true; 89 } 90 } 91 } 92 } 93 } 94 if (! skipFunc) 95 exp.func = exp.func.visit(this, ignored); 96 if (exitValue == null && ! skipArgs) { 97 int nargs = exp.args.length; 98 for (int i = 0; i < nargs; i++) { 99 Expression arg = visit(exp.args[i], null); 100 // It is possible that visiting args[i] may cause prefix 101 // arguments to be inserted (search for IS_CAPTURED) 102 // so we need to adjust for that. 103 int inserted = exp.args.length - nargs; 104 i += inserted; 105 exp.args[i] = arg; 106 nargs += inserted; 107 } 108 } 109 if (backJumpPossible > oldBackJumpPossible) 110 exp.setFlag(ApplyExp.MAY_CONTAIN_BACK_JUMP); 111 return exp; 112 } 113 visitDefaultArgs(LambdaExp exp, Void ignored)114 public void visitDefaultArgs (LambdaExp exp, Void ignored) 115 { 116 super.visitDefaultArgs(exp, ignored); 117 118 if (exp.getClass() != LambdaExp.class) 119 return; 120 121 // Check if any default expression "captured" a parameter. 122 // If so, evaluating a default expression cannot be done until the 123 // heapFrame is allocated in the main-method. But in most cases, a 124 // default expression will not contain a nested scope, hence no 125 // capture, hence we can generate efficient code to handle optional 126 // arguments. 127 for (Declaration param = exp.firstDecl(); 128 param != null; param = param.nextDecl()) 129 { 130 if (! param.isSimple()) 131 { 132 exp.setFlag(LambdaExp.DEFAULT_CAPTURES_ARG|LambdaExp.HAS_NONTRIVIAL_PATTERN); 133 break; 134 } 135 } 136 } 137 visitClassExp(ClassExp exp, Void ignored)138 protected Expression visitClassExp (ClassExp exp, Void ignored) 139 { 140 Expression ret = super.visitClassExp(exp, ignored); 141 if (! exp.explicitInit && ! exp.instanceType.isInterface()) 142 // Make sure <init> has been declared, in case we need to invoke it. 143 Compilation.getConstructor(exp.instanceType, exp); 144 else if (exp.getNeedsClosureEnv()) 145 { 146 for (LambdaExp child = exp.firstChild; child != null; 147 child = child.nextSibling) 148 { 149 if ("*init*".equals(child.getName())) 150 child.setNeedsStaticLink(true); 151 } 152 } 153 if (exp.isSimple() && exp.getNeedsClosureEnv() && exp.nameDecl != null 154 && exp.nameDecl.getType() == Compilation.typeClass) 155 exp.nameDecl.setType(Compilation.typeClassType); 156 return ret; 157 } 158 visitModuleExp(ModuleExp exp, Void ignored)159 protected Expression visitModuleExp (ModuleExp exp, Void ignored) 160 { 161 ModuleExp saveModule = currentModule; 162 Hashtable saveDecls = unknownDecls; 163 currentModule = exp; 164 unknownDecls = null; 165 try 166 { 167 return visitLambdaExp(exp, ignored); 168 } 169 finally 170 { 171 currentModule = saveModule; 172 unknownDecls = saveDecls; 173 } 174 } 175 maybeWarnNoDeclarationSeen(Object name, boolean function, Compilation comp, SourceLocator location)176 void maybeWarnNoDeclarationSeen(Object name, boolean function, 177 Compilation comp, SourceLocator location) 178 { 179 if (comp.resolve(name, function) == null) 180 maybeWarnNoDeclarationSeen(name, comp, location); 181 } 182 maybeWarnNoDeclarationSeen(Object name, Compilation comp, SourceLocator location)183 void maybeWarnNoDeclarationSeen (Object name, Compilation comp, SourceLocator location) 184 { 185 if (comp.warnUndefinedVariable()) 186 comp.error('w', "no declaration seen for "+name, location); 187 } 188 visitFluidLetExp(FluidLetExp exp, Void ignored)189 protected Expression visitFluidLetExp (FluidLetExp exp, Void ignored) 190 { 191 for (Declaration decl = exp.firstDecl(); decl != null; decl = decl.nextDecl()) 192 { 193 if (decl.base == null) 194 { 195 Object name = decl.getSymbol(); 196 Declaration bind = allocUnboundDecl(name, false); 197 if (! decl.getFlag(Declaration.IS_DYNAMIC)) 198 maybeWarnNoDeclarationSeen(name, comp, exp); 199 capture(bind, null); 200 decl.base = bind; 201 } 202 } 203 return super.visitLetExp(exp, ignored); 204 } 205 visitLetExp(LetExp exp, Void ignored)206 protected Expression visitLetExp (LetExp exp, Void ignored) 207 { 208 if (exp.body instanceof BeginExp) 209 { 210 // Optimize "letrec"-like forms. 211 // If init[i] is the magic QuoteExp.nullExp, and the real value 212 // is a LambdaExp or a QuoteExp, we're not going to get weird 213 // order-dependencies, and it is safe to transform it to a regular let. 214 // It's also necessary in the case of a LambdaExp if it shares 215 // a field with the declaration (see LambdaExp.allocFieldField), 216 // since assigning the nullExp can clobber the field after it has 217 // been initialized with a CompiledProc. 218 Expression[] exps = ((BeginExp) exp.body).exps; 219 int init_index = 0; 220 Declaration decl = exp.firstDecl(); 221 for (int begin_index = 0; 222 begin_index < exps.length && decl != null; 223 begin_index++) 224 { 225 Expression st = exps[begin_index]; 226 if (st instanceof SetExp) 227 { 228 SetExp set = (SetExp) st; 229 if (set.binding == decl 230 && decl.getInitValue() == QuoteExp.nullExp 231 && set.isDefining()) 232 { 233 Expression new_value = set.new_value; 234 if ((new_value instanceof QuoteExp 235 || new_value instanceof LambdaExp) 236 && decl.getValue() == new_value) 237 { 238 decl.setInitValue(new_value); 239 exps[begin_index] = QuoteExp.voidExp; 240 } 241 init_index++; 242 decl = decl.nextDecl(); 243 } 244 } 245 } 246 } 247 return super.visitLetExp(exp, ignored); 248 } 249 visitLambdaExp(LambdaExp exp, Void ignored)250 protected Expression visitLambdaExp (LambdaExp exp, Void ignored) 251 { 252 if (exp.getInlineOnly()) 253 backJumpPossible++; 254 return super.visitLambdaExp(exp, ignored); 255 } 256 visitCaseExp(CaseExp exp, Void ignored)257 protected Expression visitCaseExp(CaseExp exp, Void ignored) { 258 259 exp.key = visit(exp.key, ignored); 260 for (int i = 0; i < exp.clauses.length; i++) { 261 Expression e = exp.clauses[i].exp; 262 e = visit(e, ignored); 263 } 264 265 CaseExp.CaseClause ecl = exp.elseClause; 266 if (ecl != null) 267 ecl.exp = visit(ecl.exp, ignored); 268 269 return exp; 270 } 271 capture(Declaration decl, ReferenceExp rexp)272 public void capture(Declaration decl, ReferenceExp rexp) 273 { 274 if (! decl.getCanReadOrCall()) 275 return; 276 if (decl.getField() != null && decl.getField().getStaticFlag()) 277 return; 278 // This catches the "(module-instance)" dummy context variable 279 // created in Translator.rewrite. 280 if (comp.immediate && decl.hasConstantValue()) 281 return; 282 283 LambdaExp curLambda = getCurrentLambda (); 284 ScopeExp sc = decl.getContext(); 285 LambdaExp declLambda = sc.currentLambda (); 286 287 // If curLambda is inlined, the function that actually needs a closure 288 // is its caller. We get its caller using getCaller(). 289 // A complication is that we can have a chain of functions that 290 // recursively call each other, and are hence inlined in each other. 291 // Since a function is only inlined if it has a single call site, 292 // that means there is actually no way to actually enter the chain; 293 // i.e. none of the inlined functions can actually get called. 294 // However, we have to watch out for this possibility, or the loop 295 // here will run forever. For us to have a cycle, all of the functions 296 // must have the same parent. If the loop is executed more times 297 // than the number of child functions of the parent, then we know we 298 // have a cycle. 299 // The `chain' variable is used to catch infinite inline loops by 300 // iterating through the parents children. 301 LambdaExp oldParent = null; 302 LambdaExp chain = null; 303 while (curLambda != declLambda && curLambda.getInlineOnly()) 304 { 305 LambdaExp curParent = curLambda.outerLambda(); 306 if (curParent != oldParent) 307 { 308 // Reset the chain. 309 chain = curParent.firstChild; 310 oldParent = curParent; 311 } 312 if (chain == null || curLambda.inlineHome == null) 313 { 314 // Infinite loop of functions that are inlined in each other. 315 return; 316 } 317 curLambda = curLambda.getCaller(); 318 chain = chain.nextSibling; 319 } 320 if (comp.usingCPStyle()) 321 { 322 if (curLambda instanceof ModuleExp) 323 return; 324 } 325 else 326 if (curLambda == declLambda) 327 return; 328 329 // The logic here is similar to that of decl.ignorable(): 330 Expression value = decl.getValue(); 331 LambdaExp declValue; 332 if (value == null || ! (value instanceof LambdaExp)) 333 declValue = null; 334 else 335 { 336 declValue = (LambdaExp) value; 337 if (declValue.getInlineOnly()) 338 return; 339 if (declValue.isHandlingTailCalls()) 340 declValue = null; 341 else if (declValue == curLambda && ! decl.getCanRead()) 342 return; 343 } 344 345 if (decl.getFlag(Declaration.IS_UNKNOWN)) 346 { 347 // Don't create a closure for a static function/class. 348 for (LambdaExp parent = curLambda; ; parent = parent.outerLambda()) 349 { 350 if (parent == declLambda) 351 break; 352 if (parent.nameDecl != null 353 && parent.nameDecl.getFlag(Declaration.STATIC_SPECIFIED)) 354 { 355 decl.setFlag(Declaration.STATIC_SPECIFIED); 356 break; 357 } 358 } 359 } 360 if (decl.base != null) 361 { 362 decl.base.setCanRead(true); 363 capture(decl.base, null); 364 } 365 else if (decl.getCanReadOrCall() || declValue == null) 366 { 367 if (! decl.isStatic()) 368 { 369 LambdaExp heapLambda = curLambda; 370 371 // Perform the "lambda lifting" optimization, if possible: 372 // (define (f x) ... y ...) 373 // (f a) 374 // to: 375 // (define (f y$ x) ... y$ ...) 376 // (f y a) 377 // This can avoid the need for creating a closure. 378 if (rexp != null 379 && decl.nvalues == 1 && ! decl.hasUnknownValue() 380 && ! (decl.getValueRaw() instanceof LambdaExp) 381 // don't confuse call/cc inlining (over-conservative ) 382 && ! decl.getFlag(Declaration.DONT_COPY) 383 && ! curLambda.getInlineOnly() // FIXME - for simplicity 384 && ! curLambda.getCanRead() && curLambda.nameDecl != null 385 && ! curLambda.nameDecl.context.isClassGenerated() 386 && curLambda.min_args == curLambda.max_args) { 387 Declaration ndecl = null; 388 for (ndecl = curLambda.firstDecl(); ndecl != null; 389 ndecl = ndecl.nextDecl()) { 390 if (ndecl.getFlag(Declaration.IS_CAPTURED) 391 && ndecl.base == decl) 392 break; 393 } 394 if (ndecl == null) { 395 ndecl = new Declaration(decl.getSymbol()); 396 ndecl.base = decl; 397 ndecl.setFlag(Declaration.IS_CAPTURED); 398 ndecl.setCanRead(true); 399 curLambda.add(null, ndecl); 400 curLambda.min_args++; 401 curLambda.max_args++; 402 for (ApplyExp exp = curLambda.nameDecl.firstCall; 403 exp != null; exp = exp.nextCall) { 404 LambdaExp context = exp.context; 405 Expression[] args = exp.getArgs(); 406 Expression[] nargs = new Expression[args.length+1]; 407 boolean recursive = exp.context == curLambda; 408 ReferenceExp ref = 409 new ReferenceExp(recursive ? ndecl : decl); 410 nargs[0] = ref; 411 System.arraycopy(args, 0, nargs, 1, args.length); 412 exp.setArgs(nargs); 413 LambdaExp saveLambda = currentLambda; 414 currentLambda = context; 415 capture(decl, ref); 416 currentLambda = saveLambda; 417 } 418 } 419 rexp.setBinding(ndecl); 420 return; 421 } 422 423 if (decl.context instanceof ClassExp) { 424 if (heapLambda.getOuter() == decl.context) 425 return; 426 ScopeExp methodLambda = heapLambda; 427 while (methodLambda != null) { 428 ScopeExp outer = methodLambda.getOuter(); 429 if (outer == decl.context) { 430 Declaration thisDecl = methodLambda.firstDecl(); 431 if (thisDecl != null && thisDecl.isThisParameter()) { 432 capture(thisDecl, null); 433 return; 434 } 435 break; 436 } 437 methodLambda = outer; 438 } 439 } 440 if (decl.isLexical()) { 441 heapLambda.setImportsLexVars(); 442 } 443 LambdaExp parent = heapLambda.outerLambda(); 444 for (LambdaExp outer = parent; outer != declLambda && outer != null; ) 445 { 446 heapLambda = outer; 447 if (! decl.getCanReadOrCall() && declValue == outer) 448 break; 449 Declaration heapDecl = heapLambda.nameDecl; 450 if (heapDecl != null 451 && heapDecl.getFlag(Declaration.STATIC_SPECIFIED)) 452 { 453 comp.error('e', "static " + heapLambda.getName() 454 + " references non-static " + decl.getName()); 455 } 456 if (heapLambda instanceof ClassExp 457 && heapLambda.getName() != null 458 && ((ClassExp) heapLambda).isSimple()) 459 comp.error('w', heapLambda.nameDecl, 460 "simple class ", " requiring lexical link (because of reference to "+decl.getName()+") - use define-class instead"); 461 heapLambda.setNeedsStaticLink(); 462 outer = heapLambda.outerLambda(); 463 } 464 } 465 declLambda.capture(decl); 466 } 467 } 468 469 Hashtable unknownDecls = null; 470 ModuleExp currentModule = null; 471 allocUnboundDecl(Object name, boolean function)472 Declaration allocUnboundDecl(Object name, boolean function) 473 { 474 Declaration decl; 475 Object key = name; 476 if (function && name instanceof Symbol) 477 { 478 if (! getCompilation().getLanguage().hasSeparateFunctionNamespace()) 479 function = false; 480 else // FIXME maybe just use gnu.lists.Pair and remove KeyPair class? 481 key = new KeyPair((Symbol) name, EnvironmentKey.FUNCTION); 482 } 483 if (unknownDecls == null) 484 { 485 unknownDecls = new Hashtable(100); 486 decl = null; 487 } 488 else 489 decl = (Declaration) unknownDecls.get(key); 490 if (decl == null) 491 { 492 decl = currentModule.addDeclaration(name); 493 decl.setSimple(false); 494 decl.setPrivate(true); 495 if (function) 496 decl.setProcedureDecl(true); 497 if (currentModule.isStatic()) 498 decl.setFlag(Declaration.STATIC_SPECIFIED); 499 decl.setCanRead(true); 500 decl.setCanWrite(true); 501 decl.noteValueUnknown(); 502 // Setting IS_SINGLE_VALUE unconditionally is a kludge. 503 // It is OK for Scheme/Lisp, since a variable can't be 504 // bound to multiple value. It is OK for XQuery, since we 505 // XQuery doesn't allow unknown/dynamic variables. FIXME. 506 decl.setFlag(Declaration.IS_UNKNOWN|Declaration.IS_SINGLE_VALUE); 507 decl.setIndirectBinding(true); 508 unknownDecls.put(key, decl); 509 } 510 return decl; 511 } 512 visitReferenceExp(ReferenceExp exp, Void ignored)513 protected Expression visitReferenceExp (ReferenceExp exp, Void ignored) 514 { 515 Declaration decl = exp.getBinding(); 516 if (decl == null) 517 { 518 decl = allocUnboundDecl(exp.getSymbol(), 519 exp.isProcedureName()); 520 exp.setBinding(decl); 521 } 522 if (decl.getFlag(Declaration.IS_UNKNOWN)) 523 maybeWarnNoDeclarationSeen(exp.getSymbol(), exp.isProcedureName(), 524 comp, exp); 525 526 capture(exp.contextDecl(), decl, exp); 527 return exp; 528 } 529 capture(Declaration containing, Declaration decl, ReferenceExp exp)530 void capture(Declaration containing, Declaration decl, ReferenceExp exp) 531 { 532 Expression dvalue; 533 if (decl.isAlias() && (dvalue = decl.getValue()) instanceof ReferenceExp) 534 { 535 ReferenceExp rexp = (ReferenceExp) dvalue; 536 Declaration orig = rexp.binding; 537 if (orig != null 538 && (containing == null || ! orig.needsContext())) 539 { 540 capture(rexp.contextDecl(), orig, null); 541 return; 542 } 543 } 544 while (decl.isFluid() && decl.context instanceof FluidLetExp) 545 { 546 decl = decl.base; 547 } 548 if (containing != null && decl.needsContext()) 549 capture(containing, null); 550 else 551 capture(decl, exp); 552 } 553 visitThisExp(ThisExp exp, Void ignored)554 protected Expression visitThisExp (ThisExp exp, Void ignored) 555 { 556 if (exp.isForContext()) 557 { 558 // This is an extension used by define_syntax. 559 // FIXME - not really right, but works in simple cases. 560 ScopeExp context = exp.getContextScope(); 561 if (! (context instanceof ModuleExp 562 && ((ModuleExp) context).isStatic())) 563 getCurrentLambda().setImportsLexVars(); 564 return exp; 565 } 566 else 567 return visitReferenceExp(exp, ignored); 568 } 569 visitSetExp(SetExp exp, Void ignored)570 protected Expression visitSetExp (SetExp exp, Void ignored) 571 { 572 Declaration decl = exp.binding; 573 if (decl == null) 574 { 575 decl = allocUnboundDecl(exp.getSymbol(), exp.isFuncDef()); 576 exp.binding = decl; 577 } 578 if (decl.getFlag(Declaration.IS_UNKNOWN)) 579 maybeWarnNoDeclarationSeen(exp.getSymbol(), false, comp, exp); 580 if (! decl.ignorable()) 581 { 582 if (! exp.isDefining()) 583 decl = Declaration.followAliases(decl); 584 capture(exp.contextDecl(), decl, null); 585 } 586 return super.visitSetExp(exp, ignored); 587 } 588 589 } 590