logo
class

compiler::ResolveExpr

sys::Obj
  compiler::CompilerSupport
    compiler::CompilerStep
      compiler::ResolveExpr
   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.verbose("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, nullnull)
 476      expr.scratchB = curMethod.addLocalVar(expr.ctype, nullnull)
 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  }