1 //
2 // Copyright (c) 2006, Brian Frank and Andy Frank
3 // Licensed under the Academic Free License version 3.0
4 //
5 // History:
6 // 2 Dec 05 Brian Frank Creation
7 //
8
9 **
10 ** Walk the AST to resolve:
11 ** - Manage local variable scope
12 ** - Resolve loop for breaks and continues
13 ** - Resolve LocalDefStmt.init into full assignment expression
14 ** - Resolve Expr.ctype
15 ** - Resolve UknownVarExpr -> LocalVarExpr, FieldExpr, or CallExpr
16 ** - Resolve CallExpr to their CMethod
17 **
18 class ResolveExpr : CompilerStep
19 {
20
21 //////////////////////////////////////////////////////////////////////////
22 // Constructor
23 //////////////////////////////////////////////////////////////////////////
24
25 new make(Compiler compiler)
26 : super(compiler)
27 {
28 }
29
30 //////////////////////////////////////////////////////////////////////////
31 // Run
32 //////////////////////////////////////////////////////////////////////////
33
34 override Void run()
35 {
36 log.debug("ResolveExpr")
37 walk(types, VisitDepth.expr)
38 bombIfErr
39 }
40
41 //////////////////////////////////////////////////////////////////////////
42 // Method
43 //////////////////////////////////////////////////////////////////////////
44
45 override Void enterMethodDef(MethodDef m)
46 {
47 super.enterMethodDef(m)
48 this.inClosure = (curType.isClosure && curType.closure.doCall === m)
49 initMethodVars
50 }
51
52 //////////////////////////////////////////////////////////////////////////
53 // Stmt
54 //////////////////////////////////////////////////////////////////////////
55
56 override Void enterStmt(Stmt stmt) { stmtStack.push(stmt) }
57
58 override Void visitStmt(Stmt stmt)
59 {
60 stmtStack.pop
61 switch (stmt.id)
62 {
63 case StmtId.expr: resolveExprStmt((ExprStmt)stmt)
64 case StmtId.forStmt: resolveFor((ForStmt)stmt)
65 case StmtId.breakStmt: resolveBreak((BreakStmt)stmt)
66 case StmtId.continueStmt: resolveContinue((ContinueStmt)stmt)
67 case StmtId.localDef: resolveLocalVarDef((LocalDefStmt)stmt)
68 }
69 }
70
71 private Void resolveExprStmt(ExprStmt stmt)
72 {
73 // stand alone expr statements, shouldn't be left on the stack
74 stmt.expr.leave = false
75 }
76
77 private Void resolveLocalVarDef(LocalDefStmt def)
78 {
79 // check for type inference
80 if (def.ctype == null)
81 def.ctype = def.init.ctype
82
83 // bind to scope as a method variable
84 bindToMethodVar(def)
85
86 // if init is null, then we default the variable to null (Fan
87 // doesn't do true definite assignment checking since most local
88 // variables use type inference anyhow)
89 if (def.init == null)
90 def.init = LiteralExpr.make(def.location, ExprId.nullLiteral, def.ctype, null)
91
92 // turn init into full assignment
93 def.init = BinaryExpr.makeAssign(LocalVarExpr.make(def.location, def.var), def.init)
94 }
95
96 private Void resolveFor(ForStmt stmt)
97 {
98 // don't leave update expression on the stack
99 if (stmt.update != null) stmt.update.leave = false
100 }
101
102 private Void resolveBreak(BreakStmt stmt)
103 {
104 // find which loop we're inside of (checked in CheckErrors)
105 stmt.loop = findLoop
106 }
107
108 private Void resolveContinue(ContinueStmt stmt)
109 {
110 // find which loop we're inside of (checked in CheckErrors)
111 stmt.loop = findLoop
112 }
113
114 //////////////////////////////////////////////////////////////////////////
115 // Expr
116 //////////////////////////////////////////////////////////////////////////
117
118 override Expr visitExpr(Expr expr)
119 {
120 // resolve the expression
121 expr = resolveExpr(expr)
122
123 // expr type must be resolved at this point
124 if (expr.ctype == null)
125 throw err("Expr type not resolved: ${expr.id}: ${expr}", expr.location)
126
127 return expr
128 }
129
130 private Expr resolveExpr(Expr expr)
131 {
132 switch (expr.id)
133 {
134 case ExprId.listLiteral: return resolveList((ListLiteralExpr)expr)
135 case ExprId.mapLiteral: return resolveMap((MapLiteralExpr)expr)
136 case ExprId.boolNot:
137 case ExprId.cmpNull:
138 case ExprId.cmpNotNull: expr.ctype = ns.boolType
139 case ExprId.assign: return resolveAssign((BinaryExpr)expr)
140 case ExprId.same:
141 case ExprId.notSame:
142 case ExprId.boolOr:
143 case ExprId.boolAnd:
144 case ExprId.isExpr: expr.ctype = ns.boolType
145 case ExprId.asExpr: expr.ctype = ((TypeCheckExpr)expr).check
146 case ExprId.call: return resolveCall((CallExpr)expr)
147 case ExprId.shortcut: return resolveShortcut((ShortcutExpr)expr)
148 case ExprId.thisExpr: return resolveThis((ThisExpr)expr)
149 case ExprId.superExpr: return resolveSuper((SuperExpr)expr)
150 case ExprId.unknownVar: return resolveVar((UnknownVarExpr)expr)
151 case ExprId.storage: return resolveStorage((UnknownVarExpr)expr)
152 case ExprId.cast: expr.ctype = ((TypeCheckExpr)expr).check
153 case ExprId.ternary: resolveTernary((TernaryExpr)expr)
154 case ExprId.withBlock: resolveWithBlock((WithBlockExpr)expr)
155 case ExprId.curry: return resolveCurry((CurryExpr)expr)
156 case ExprId.closure: resolveClosure((ClosureExpr)expr)
157 }
158
159 return expr
160 }
161
162 **
163 ** Resolve list literal
164 **
165 private Expr resolveList(ListLiteralExpr expr)
166 {
167 if (expr.explicitType != null)
168 {
169 expr.ctype = expr.explicitType
170 }
171 else
172 {
173 // infer from list item expressions
174 v := Expr.commonType(ns, expr.vals)
175 expr.ctype = v.toListOf
176 }
177 return expr
178 }
179
180 **
181 ** Resolve map literal
182 **
183 private Expr resolveMap(MapLiteralExpr expr)
184 {
185 if (expr.explicitType != null)
186 {
187 expr.ctype = expr.explicitType
188 }
189 else
190 {
191 // infer from key/val expressions
192 k := Expr.commonType(ns, expr.keys)
193 v := Expr.commonType(ns, expr.vals)
194 expr.ctype = MapType.make(k, v)
195 }
196 return expr
197 }
198
199 **
200 ** Resolve this keyword expression
201 **
202 private Expr resolveThis(ThisExpr expr)
203 {
204 if (inClosure)
205 {
206 loc := expr.location
207 closure := curType.closure
208
209 // if the closure is in a static method, report an error
210 if (closure.enclosingMethod.isStatic)
211 {
212 expr.ctype = ns.error
213 err("Cannot access 'this' within closure of static context", loc)
214 return expr
215 }
216
217 // otherwise replace this with $this field access
218 return FieldExpr.make(loc, ThisExpr.make(loc), closure.outerThisField)
219 }
220
221 expr.ctype = curType
222 return expr
223 }
224
225 **
226 ** Resolve super keyword expression
227 **
228 private Expr resolveSuper(SuperExpr expr)
229 {
230 if (inClosure)
231 {
232 // it would be nice to support super from within a closure,
233 // but the Java VM has the stupid restriction that invokespecial
234 // cannot be used outside of the class - we could potentially
235 // work around this using a wrapper method - but for now we will
236 // just disallow it
237 err("Invalid use of 'super' within closure", expr.location)
238 expr.ctype = ns.error
239 return expr
240 }
241
242 if (expr.explicitType != null)
243 expr.ctype = expr.explicitType
244 else
245 expr.ctype = curType.base
246
247 return expr
248 }
249
250 **
251 ** Resolve an assignment operation
252 **
253 private Expr resolveAssign(BinaryExpr expr)
254 {
255 // check for left hand side the [] shortcut, because []= is set
256 shortcut := expr.lhs as ShortcutExpr
257 if (shortcut != null && shortcut.op == ShortcutOp.get)
258 {
259 shortcut.op = ShortcutOp.set
260 shortcut.name = "set"
261 shortcut.args.add(expr.rhs)
262 shortcut.method = null
263 return resolveCall(shortcut)
264 }
265
266 // check for left hand side the -> shortcut, because a->x=b is trap.a("x", [b])
267 call := expr.lhs as CallExpr
268 if (call != null && call.isDynamic)
269 {
270 call.args.add(expr.rhs)
271 return resolveCall(call)
272 }
273
274 // assignment is typed by lhs
275 expr.ctype = expr.lhs.ctype
276
277 return expr
278 }
279
280 **
281 ** Resolve an UnknownVar to its replacement node.
282 **
283 private Expr resolveVar(UnknownVarExpr var)
284 {
285 // if there is no target, attempt to bind to local variable
286 if (var.target == null)
287 {
288 // attempt to a name in the current scope
289 binding := resolveLocal(var.name)
290 if (binding != null)
291 return LocalVarExpr.make(var.location, binding)
292 }
293
294 // at this point it can't be a local variable, so it must be
295 // a slot on either myself or the variable's target
296 return CallResolver.make(compiler, curType, curMethod, var).resolve
297 }
298
299 **
300 ** Resolve storage operator
301 **
302 private Expr resolveStorage(UnknownVarExpr var)
303 {
304 // resolve as normal unknown variable
305 resolved := resolveVar(var)
306 if (resolved.id !== ExprId.field)
307 {
308 if (resolved.ctype !== ns.error)
309 err("Invalid use of field storage operator '@'", var.location)
310 return resolved
311 }
312
313 f := resolved as FieldExpr
314 f.useAccessor = false
315 if (f.field is FieldDef) ((FieldDef)f.field).flags |= FConst.Storage
316 return f
317 }
318
319 **
320 ** Resolve "x ? y : z" ternary expression
321 **
322 private Expr resolveTernary(TernaryExpr expr)
323 {
324 if (expr.trueExpr.id === ExprId.nullLiteral)
325 expr.ctype = expr.falseExpr.ctype
326 else if (expr.falseExpr.id === ExprId.nullLiteral)
327 expr.ctype = expr.trueExpr.ctype
328 else
329 expr.ctype = CType.common(ns, [expr.trueExpr.ctype, expr.falseExpr.ctype])
330 return expr
331 }
332
333 **
334 ** Resolve with block
335 **
336 private Expr resolveWithBlock(WithBlockExpr expr)
337 {
338 // make sure we pop all sub-expressions
339 expr.subs.each |Expr sub| { sub.leave = false }
340 return expr
341 }
342
343 **
344 ** Resolve a call to it's Method and return type.
345 **
346 private Expr resolveCall(CallExpr call)
347 {
348 // dynamic calls are just syntactic sugar for Obj.trap
349 if (call.isDynamic)
350 {
351 call.method = ns.objTrap
352 call.ctype = ns.objType
353 return call
354 }
355
356 // if there is no target, attempt to bind to local variable
357 if (call.target == null)
358 {
359 // attempt to a name in the current scope
360 binding := resolveLocal(call.name)
361 if (binding != null)
362 return resolveCallOnLocalVar(call, LocalVarExpr.make(call.location, binding))
363 }
364
365 return CallResolver.make(compiler, curType, curMethod, call).resolve
366 }
367
368 **
369 ** Resolve the () operator on a local variable - if the local
370 ** is a Method, then () is syntactic sugar for Method.callx()
371 **
372 private Expr resolveCallOnLocalVar(CallExpr call, LocalVarExpr binding)
373 {
374 // if binding isn't a sys::Func then no can do
375 if (!binding.ctype.fits(ns.funcType))
376 {
377 if (binding.ctype != ns.error)
378 err("Cannot call local variable '$call.name' like a function", call.location)
379 call.ctype = ns.error
380 return call
381 }
382
383 // can only handle zero to eight arguments; I could wrap up the
384 // arguments into a List and use call(List) - but methods with
385 // that many arguments are just inane so tough luck
386 if (call.args.size > 8)
387 {
388 err("Tough luck - cannot use () operator with more than 8 arguments, use call(List)", call.location)
389 call.ctype = ns.error
390 return call
391 }
392
393 // invoking the () operator on a sys::Func is syntactic
394 // sugar for invoking one of the Func.callX methods
395 callx := binding.ctype.method("call${call.args.size}")
396 return CallExpr.makeWithMethod(call.location, binding, callx, call.args)
397 }
398
399 **
400 ** Resolve ShortcutExpr.
401 **
402 private Expr resolveShortcut(ShortcutExpr expr)
403 {
404 // if this is an indexed assigment such as x[y] += z
405 if (expr.isAssign && expr.target.id === ExprId.shortcut)
406 return resolveIndexedAssign(expr)
407
408 // if a binary operation
409 if (expr.args.size == 1)
410 {
411 // extract lhs and rhs
412 lhs := expr.target
413 rhs := expr.args.first
414
415 // if arg is Range, then get() is really slice()
416 if (expr.op === ShortcutOp.get && rhs.ctype.isRange)
417 {
418 expr.op = ShortcutOp.slice
419 expr.name = "slice"
420 }
421
422 // string concat is always optimized, and performs a bit
423 // different since a non-string can be used as the lhs
424 if (expr.isStrConcat)
425 {
426 expr.ctype = ns.strType
427 expr.method = ns.strPlus
428 return ConstantFolder.make(compiler).fold(expr)
429 }
430 }
431
432 // resolve the call, if optimized, then return it immediately
433 result := resolveCall(expr)
434 if (result !== expr) return result
435
436 // the comparision operations are special case that call a method
437 // that return an Int, but leave a Bool on the stack (we also handle
438 // specially in assembler)
439 switch (expr.opToken)
440 {
441 case Token.lt:
442 case Token.ltEq:
443 case Token.gt:
444 case Token.gtEq:
445 expr.ctype = ns.boolType
446 }
447
448 return expr
449 }
450
451 **
452 ** If we have an assignment against an indexed shortcut
453 ** such as x[y] += z, then process specially to return
454 ** a IndexedAssignExpr subclass of ShortcutExpr.
455 **
456 private Expr resolveIndexedAssign(ShortcutExpr orig)
457 {
458 // we better have a x[y] indexed get expression
459 if (orig.target.id != ExprId.shortcut && orig.target->op === ShortcutOp.get)
460 {
461 err("Expected indexed expression", orig.location)
462 return orig
463 }
464
465 // wrap the shorcut as an IndexedAssignExpr
466 expr := IndexedAssignExpr.makeFrom(orig)
467
468 // resolve it normally - if the orig is "x[y] += z" then we
469 // are resolving Int.plus here - the target is "x[y]" and should
470 // already be resolved
471 resolveCall(expr)
472
473 // we need two scratch variables to manipulate the stack cause
474 // .NET is lame when it comes to doing anything with the stack
475 expr.scratchA = curMethod.addLocalVar(expr.ctype, null, null)
476 expr.scratchB = curMethod.addLocalVar(expr.ctype, null, null)
477
478 // resolve the set method which matches
479 // the get method on the target
480 get := ((ShortcutExpr)expr.target).method
481 set := get.parent.method("set")
482 if (set == null || set.params.size != 2 || set.isStatic ||
483 set.params[0].paramType != get.params[0].paramType ||
484 set.params[1].paramType != get.returnType)
485 err("No matching 'set' method for '$get.qname'", orig.location)
486 expr.setMethod = set
487
488 // return the new IndexedAssignExpr
489 return expr
490 }
491
492 **
493 ** CurryExpr
494 **
495 private Expr resolveCurry(CurryExpr expr)
496 {
497 // if the operand isn't a CallExpr, then we have a problem
498 if (expr.operand.id !== ExprId.call)
499 {
500 err("Invalid operand '$expr.operand.id' for curry operator", expr.location)
501 expr.ctype = ns.error
502 return expr
503 }
504
505 // use CurryResolver for all the heavy lifting
506 return CurryResolver.make(compiler, curType, curryCount++, expr).resolve
507 }
508
509 **
510 ** ClosureExpr will just output it's substitute expression. But we take
511 ** this opportunity to capture the local variables in the closure's scope
512 ** and cache them on the ClosureExpr. We also do variable name checking.
513 **
514 private Void resolveClosure(ClosureExpr expr)
515 {
516 // save away current locals in scope
517 expr.enclosingLocals = localsInScope
518
519 // make sure none of the closure's parameters
520 // conflict with the locals in scope
521 expr.doCall.paramDefs.each |ParamDef p|
522 {
523 if (expr.enclosingLocals.containsKey(p.name))
524 err("Closure parameter '$p.name' is already defined in current block", p.location)
525 }
526 }
527
528 //////////////////////////////////////////////////////////////////////////
529 // Scope
530 //////////////////////////////////////////////////////////////////////////
531
532 **
533 ** Setup the MethodVars for the parameters.
534 **
535 private Void initMethodVars()
536 {
537 m := curMethod
538 reg := m.isStatic ? 0 : 1
539
540 m.paramDefs.each |ParamDef p|
541 {
542 var := MethodVar.makeForParam(reg++, p)
543 m.vars.add(var)
544 }
545 }
546
547 **
548 ** Bind the specified local variable definition to a
549 ** MethodVar (and register number).
550 **
551 private Void bindToMethodVar(LocalDefStmt def)
552 {
553 // make sure it doesn't exist in the current scope
554 if (resolveLocal(def.name) != null)
555 err("Variable '$def.name' is already defined in current block", def.location)
556
557 // create and add it
558 def.var = curMethod.addLocalVar(def.ctype, def.name, currentBlock)
559 }
560
561 **
562 ** Resolve a local variable using current scope based on
563 ** the block stack and possibly the scope of a closure.
564 **
565 private MethodVar resolveLocal(Str name)
566 {
567 // if not in method, then we can't have a local
568 if (curMethod == null) return null
569
570 // attempt to a name in the current scope
571 binding := curMethod.vars.find |MethodVar var->Bool|
572 {
573 return var.name == name && isBlockInScope(var.scope)
574 }
575 if (binding != null) return binding
576
577 // if a closure, check parent scope
578 if (inClosure)
579 {
580 closure := curType.closure
581 binding = closure.enclosingLocals[name]
582 if (binding != null)
583 {
584 // mark the local var as being used in a closure so that
585 // we know to generate a cvar field for it in ClosureVars
586 binding.usedInClosure = true
587
588 // mark this closure as using cvars
589 closure.usesCvars = true
590
591 // mark the enclosing method and recursively
592 // any outer closures as needing cvars
593 closure.enclosingMethod.needsCvars = true
594 for (p := closure.enclosingClosure; p != null; p = p.enclosingClosure)
595 p.doCall.needsCvars = true
596
597 return binding
598 }
599 }
600
601 // not found
602 return null
603 }
604
605 **
606 ** Get a list of all the local method variables that
607 ** are currently in scope.
608 **
609 private Str:MethodVar localsInScope()
610 {
611 Str:MethodVar acc
612 if (inClosure)
613 acc = curType.closure.enclosingLocals.dup
614 else
615 acc = Str:MethodVar[:]
616
617 curMethod.vars.each |MethodVar var|
618 {
619 if (isBlockInScope(var.scope))
620 acc[var.name] = var
621 }
622
623 return acc
624 }
625
626 **
627 ** Get the current block which defines our scope. We make
628 ** a special case for "for" loops which can declare variables.
629 **
630 private Block currentBlock()
631 {
632 if (stmtStack.peek is ForStmt)
633 return ((ForStmt)stmtStack.peek).block
634 else
635 return blockStack.peek
636 }
637
638 **
639 ** Check if the specified block is currently in scope. We make
640 ** a specialcase for "for" loops which can declare variables.
641 **
642 private Bool isBlockInScope(Block block)
643 {
644 // the null block within the whole method (ctorChains or defaultParams)
645 if (block == null) return true
646
647 // special case for "for" loops
648 if (stmtStack.peek is ForStmt)
649 {
650 if (((ForStmt)stmtStack.peek).block === block)
651 return true
652 }
653
654 // look in block stack which models scope chain
655 return blockStack.any |Block b->Bool| { return b === block }
656 }
657
658 //////////////////////////////////////////////////////////////////////////
659 // StmtStack
660 //////////////////////////////////////////////////////////////////////////
661
662 private Stmt findLoop()
663 {
664 for (i:=stmtStack.size-1; i>=0; --i)
665 {
666 stmt := stmtStack[i]
667 if (stmt.id === StmtId.whileStmt) return stmt
668 if (stmt.id === StmtId.forStmt) return stmt
669 }
670 return null
671 }
672
673 //////////////////////////////////////////////////////////////////////////
674 // BlockStack
675 //////////////////////////////////////////////////////////////////////////
676
677 override Void enterBlock(Block block) { blockStack.push(block) }
678 override Void exitBlock(Block block) { blockStack.pop }
679
680 //////////////////////////////////////////////////////////////////////////
681 // Fields
682 //////////////////////////////////////////////////////////////////////////
683
684 Stmt[] stmtStack := Stmt[,] // statement stack
685 Block[] blockStack := Block[,] // block stack used for scoping
686 Bool inClosure := false // are we inside a closure's block
687 Int curryCount := 0 // total number of curry exprs processed
688
689 }