summary refs log tree commit diff stats
path: root/compiler/lambdalifting.nim
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/lambdalifting.nim')
-rw-r--r--compiler/lambdalifting.nim1026
1 files changed, 1026 insertions, 0 deletions
diff --git a/compiler/lambdalifting.nim b/compiler/lambdalifting.nim
new file mode 100644
index 000000000..54cdfc5bc
--- /dev/null
+++ b/compiler/lambdalifting.nim
@@ -0,0 +1,1026 @@
+#
+#
+#           The Nim Compiler
+#        (c) Copyright 2015 Andreas Rumpf
+#
+#    See the file "copying.txt", included in this
+#    distribution, for details about the copyright.
+#
+
+# This file implements lambda lifting for the transformator.
+
+import
+  options, ast, astalgo, msgs,
+  idents, renderer, types, magicsys, lowerings, modulegraphs, lineinfos,
+  transf, liftdestructors, typeallowed
+
+import std/[strutils, tables, intsets]
+
+when defined(nimPreviewSlimSystem):
+  import std/assertions
+
+discard """
+  The basic approach is that captured vars need to be put on the heap and
+  that the calling chain needs to be explicitly modelled. Things to consider:
+
+  proc a =
+    var v = 0
+    proc b =
+      var w = 2
+
+      for x in 0..3:
+        proc c = capture v, w, x
+        c()
+    b()
+
+    for x in 0..4:
+      proc d = capture x
+      d()
+
+  Needs to be translated into:
+
+  proc a =
+    var cl: *
+    new cl
+    cl.v = 0
+
+    proc b(cl) =
+      var bcl: *
+      new bcl
+      bcl.w = 2
+      bcl.up = cl
+
+      for x in 0..3:
+        var bcl2: *
+        new bcl2
+        bcl2.up = bcl
+        bcl2.up2 = cl
+        bcl2.x = x
+
+        proc c(cl) = capture cl.up2.v, cl.up.w, cl.x
+        c(bcl2)
+
+      c(bcl)
+
+    b(cl)
+
+    for x in 0..4:
+      var acl2: *
+      new acl2
+      acl2.x = x
+      proc d(cl) = capture cl.x
+      d(acl2)
+
+  Closures as interfaces:
+
+  proc outer: T =
+    var captureMe: TObject # value type required for efficiency
+    proc getter(): int = result = captureMe.x
+    proc setter(x: int) = captureMe.x = x
+
+    result = (getter, setter)
+
+  Is translated to:
+
+  proc outer: T =
+    var cl: *
+    new cl
+
+    proc getter(cl): int = result = cl.captureMe.x
+    proc setter(cl: *, x: int) = cl.captureMe.x = x
+
+    result = ((cl, getter), (cl, setter))
+
+
+  For 'byref' capture, the outer proc needs to access the captured var through
+  the indirection too. For 'bycopy' capture, the outer proc accesses the var
+  not through the indirection.
+
+  Possible optimizations:
+
+  1) If the closure contains a single 'ref' and this
+  reference is not re-assigned (check ``sfAddrTaken`` flag) make this the
+  closure. This is an important optimization if closures are used as
+  interfaces.
+  2) If the closure does not escape, put it onto the stack, not on the heap.
+  3) Dataflow analysis would help to eliminate the 'up' indirections.
+  4) If the captured var is not actually used in the outer proc (common?),
+  put it into an inner proc.
+
+"""
+
+# Important things to keep in mind:
+# * Don't base the analysis on nkProcDef et al. This doesn't work for
+#   instantiated (formerly generic) procs. The analysis has to look at nkSym.
+#   This also means we need to prevent the same proc is processed multiple
+#   times via the 'processed' set.
+# * Keep in mind that the owner of some temporaries used to be unreliable.
+# * For closure iterators we merge the "real" potential closure with the
+#   local storage requirements for efficiency. This means closure iterators
+#   have slightly different semantics from ordinary closures.
+
+# ---------------- essential helpers -------------------------------------
+
+const
+  upName* = ":up" # field name for the 'up' reference
+  paramName* = ":envP"
+  envName* = ":env"
+
+proc newCall(a: PSym, b: PNode): PNode =
+  result = newNodeI(nkCall, a.info)
+  result.add newSymNode(a)
+  result.add b
+
+proc createClosureIterStateType*(g: ModuleGraph; iter: PSym; idgen: IdGenerator): PType =
+  var n = newNodeI(nkRange, iter.info)
+  n.add newIntNode(nkIntLit, -1)
+  n.add newIntNode(nkIntLit, 0)
+  result = newType(tyRange, idgen, iter)
+  result.n = n
+  var intType = nilOrSysInt(g)
+  if intType.isNil: intType = newType(tyInt, idgen, iter)
+  rawAddSon(result, intType)
+
+proc createStateField(g: ModuleGraph; iter: PSym; idgen: IdGenerator): PSym =
+  result = newSym(skField, getIdent(g.cache, ":state"), idgen, iter, iter.info)
+  result.typ = createClosureIterStateType(g, iter, idgen)
+
+template isIterator*(owner: PSym): bool =
+  owner.kind == skIterator and owner.typ.callConv == ccClosure
+
+proc createEnvObj(g: ModuleGraph; idgen: IdGenerator; owner: PSym; info: TLineInfo): PType =
+  result = createObj(g, idgen, owner, info, final=false)
+  if owner.isIterator or not isDefined(g.config, "nimOptIters"):
+    rawAddField(result, createStateField(g, owner, idgen))
+
+proc getClosureIterResult*(g: ModuleGraph; iter: PSym; idgen: IdGenerator): PSym =
+  if resultPos < iter.ast.len:
+    result = iter.ast[resultPos].sym
+  else:
+    # XXX a bit hacky:
+    result = newSym(skResult, getIdent(g.cache, ":result"), idgen, iter, iter.info, {})
+    result.typ = iter.typ.returnType
+    incl(result.flags, sfUsed)
+    iter.ast.add newSymNode(result)
+
+proc addHiddenParam(routine: PSym, param: PSym) =
+  assert param.kind == skParam
+  var params = routine.ast[paramsPos]
+  # -1 is correct here as param.position is 0 based but we have at position 0
+  # some nkEffect node:
+  param.position = routine.typ.n.len-1
+  params.add newSymNode(param)
+  #incl(routine.typ.flags, tfCapturesEnv)
+  assert sfFromGeneric in param.flags
+  #echo "produced environment: ", param.id, " for ", routine.id
+
+proc getEnvParam*(routine: PSym): PSym =
+  let params = routine.ast[paramsPos]
+  let hidden = lastSon(params)
+  if hidden.kind == nkSym and hidden.sym.kind == skParam and hidden.sym.name.s == paramName:
+    result = hidden.sym
+    assert sfFromGeneric in result.flags
+  else:
+    result = nil
+
+proc getHiddenParam(g: ModuleGraph; routine: PSym): PSym =
+  result = getEnvParam(routine)
+  if result.isNil:
+    # writeStackTrace()
+    localError(g.config, routine.info, "internal error: could not find env param for " & routine.name.s)
+    result = routine
+
+proc interestingVar(s: PSym): bool {.inline.} =
+  result = s.kind in {skVar, skLet, skTemp, skForVar, skParam, skResult} and
+    sfGlobal notin s.flags and
+    s.typ.kind notin {tyStatic, tyTypeDesc}
+
+proc illegalCapture(s: PSym): bool {.inline.} =
+  result = classifyViewType(s.typ) != noView or s.kind == skResult
+
+proc isInnerProc(s: PSym): bool =
+  if s.kind in {skProc, skFunc, skMethod, skConverter, skIterator} and s.magic == mNone:
+    result = s.skipGenericOwner.kind in routineKinds
+  else:
+    result = false
+
+proc newAsgnStmt(le, ri: PNode, info: TLineInfo): PNode =
+  # Bugfix: unfortunately we cannot use 'nkFastAsgn' here as that would
+  # mean to be able to capture string literals which have no GC header.
+  # However this can only happen if the capture happens through a parameter,
+  # which is however the only case when we generate an assignment in the first
+  # place.
+  result = newNodeI(nkAsgn, info, 2)
+  result[0] = le
+  result[1] = ri
+
+proc makeClosure*(g: ModuleGraph; idgen: IdGenerator; prc: PSym; env: PNode; info: TLineInfo): PNode =
+  result = newNodeIT(nkClosure, info, prc.typ)
+  result.add(newSymNode(prc))
+  if env == nil:
+    result.add(newNodeIT(nkNilLit, info, getSysType(g, info, tyNil)))
+  else:
+    if env.skipConv.kind == nkClosure:
+      localError(g.config, info, "internal error: taking closure of closure")
+    result.add(env)
+  #if isClosureIterator(result.typ):
+  createTypeBoundOps(g, nil, result.typ, info, idgen)
+  if tfHasAsgn in result.typ.flags or optSeqDestructors in g.config.globalOptions:
+    prc.flags.incl sfInjectDestructors
+
+proc interestingIterVar(s: PSym): bool {.inline.} =
+  # unused with -d:nimOptIters
+  # XXX optimization: Only lift the variable if it lives across
+  # yield/return boundaries! This can potentially speed up
+  # closure iterators quite a bit.
+  result = s.kind in {skResult, skVar, skLet, skTemp, skForVar} and sfGlobal notin s.flags
+
+template liftingHarmful(conf: ConfigRef; owner: PSym): bool =
+  ## lambda lifting can be harmful for JS-like code generators.
+  let isCompileTime = sfCompileTime in owner.flags or owner.kind == skMacro
+  jsNoLambdaLifting in conf.legacyFeatures and conf.backend == backendJs and not isCompileTime
+
+proc createTypeBoundOpsLL(g: ModuleGraph; refType: PType; info: TLineInfo; idgen: IdGenerator; owner: PSym) =
+  if owner.kind != skMacro:
+    createTypeBoundOps(g, nil, refType.elementType, info, idgen)
+    createTypeBoundOps(g, nil, refType, info, idgen)
+    if tfHasAsgn in refType.flags or optSeqDestructors in g.config.globalOptions:
+      owner.flags.incl sfInjectDestructors
+
+proc genCreateEnv(env: PNode): PNode =
+  var c = newNodeIT(nkObjConstr, env.info, env.typ)
+  c.add newNodeIT(nkType, env.info, env.typ)
+  let e = copyTree(env)
+  e.flags.incl nfFirstWrite
+  result = newAsgnStmt(e, c)
+
+proc liftIterSym*(g: ModuleGraph; n: PNode; idgen: IdGenerator; owner: PSym): PNode =
+  # transforms  (iter)  to  (let env = newClosure[iter](); (iter, env))
+  if liftingHarmful(g.config, owner): return n
+  let iter = n.sym
+  assert iter.isIterator
+
+  result = newNodeIT(nkStmtListExpr, n.info, iter.typ)
+  let hp = getHiddenParam(g, iter)
+  var env: PNode
+  if owner.isIterator:
+    let it = getHiddenParam(g, owner)
+    addUniqueField(it.typ.skipTypes({tyOwned})[0], hp, g.cache, idgen)
+    env = indirectAccess(newSymNode(it), hp, hp.info)
+  else:
+    let e = newSym(skLet, iter.name, idgen, owner, n.info)
+    e.typ = hp.typ
+    e.flags = hp.flags
+    env = newSymNode(e)
+    var v = newNodeI(nkVarSection, n.info)
+    addVar(v, env)
+    result.add(v)
+  # add 'new' statement:
+  #result.add newCall(getSysSym(g, n.info, "internalNew"), env)
+  result.add genCreateEnv(env)
+  createTypeBoundOpsLL(g, env.typ, n.info, idgen, owner)
+  result.add makeClosure(g, idgen, iter, env, n.info)
+
+proc freshVarForClosureIter*(g: ModuleGraph; s: PSym; idgen: IdGenerator; owner: PSym): PNode =
+  # unused with -d:nimOptIters
+  let envParam = getHiddenParam(g, owner)
+  let obj = envParam.typ.skipTypes({tyOwned, tyRef, tyPtr})
+  let field = addField(obj, s, g.cache, idgen)
+
+  var access = newSymNode(envParam)
+  assert obj.kind == tyObject
+  result = rawIndirectAccess(access, field, s.info)
+
+# ------------------ new stuff -------------------------------------------
+
+proc markAsClosure(g: ModuleGraph; owner: PSym; n: PNode) =
+  let s = n.sym
+  let isEnv = s.name.id == getIdent(g.cache, ":env").id
+  if illegalCapture(s):
+    localError(g.config, n.info,
+      ("'$1' is of type <$2> which cannot be captured as it would violate memory" &
+       " safety, declared here: $3; using '-d:nimNoLentIterators' helps in some cases." &
+       " Consider using a <ref T> which can be captured.") %
+      [s.name.s, typeToString(s.typ.skipTypes({tyVar})), g.config$s.info])
+  elif not (owner.typ.isClosure or owner.isNimcall and not owner.isExplicitCallConv or isEnv):
+    localError(g.config, n.info, "illegal capture '$1' because '$2' has the calling convention: <$3>" %
+      [s.name.s, owner.name.s, $owner.typ.callConv])
+  incl(owner.typ.flags, tfCapturesEnv)
+  if not isEnv:
+    owner.typ.callConv = ccClosure
+
+type
+  DetectionPass = object
+    processed, capturedVars: IntSet
+    ownerToType: Table[int, PType]
+    somethingToDo: bool
+    inTypeOf: bool
+    graph: ModuleGraph
+    idgen: IdGenerator
+
+proc initDetectionPass(g: ModuleGraph; fn: PSym; idgen: IdGenerator): DetectionPass =
+  result = DetectionPass(processed: toIntSet([fn.id]),
+    capturedVars: initIntSet(), ownerToType: initTable[int, PType](),
+    graph: g, idgen: idgen
+  )
+
+discard """
+proc outer =
+  var a, b: int
+  proc innerA = use(a)
+  proc innerB = use(b); innerA()
+# --> innerA and innerB need to *share* the closure type!
+This is why need to store the 'ownerToType' table and use it
+during .closure'fication.
+"""
+
+proc getEnvTypeForOwner(c: var DetectionPass; owner: PSym;
+                        info: TLineInfo): PType =
+  result = c.ownerToType.getOrDefault(owner.id)
+  if result.isNil:
+    let env = getEnvParam(owner)
+    if env.isNil or not owner.isIterator or not isDefined(c.graph.config, "nimOptIters"):
+      result = newType(tyRef, c.idgen, owner)
+      let obj = createEnvObj(c.graph, c.idgen, owner, info)
+      rawAddSon(result, obj)
+    else:
+      result = env.typ
+    c.ownerToType[owner.id] = result
+
+proc asOwnedRef(c: var DetectionPass; t: PType): PType =
+  if optOwnedRefs in c.graph.config.globalOptions:
+    assert t.kind == tyRef
+    result = newType(tyOwned, c.idgen, t.owner)
+    result.flags.incl tfHasOwned
+    result.rawAddSon t
+  else:
+    result = t
+
+proc getEnvTypeForOwnerUp(c: var DetectionPass; owner: PSym;
+                          info: TLineInfo): PType =
+  var r = c.getEnvTypeForOwner(owner, info)
+  result = newType(tyPtr, c.idgen, owner)
+  rawAddSon(result, r.skipTypes({tyOwned, tyRef, tyPtr}))
+
+proc createUpField(c: var DetectionPass; dest, dep: PSym; info: TLineInfo) =
+  let refObj = c.getEnvTypeForOwner(dest, info) # getHiddenParam(dest).typ
+  let obj = refObj.skipTypes({tyOwned, tyRef, tyPtr})
+  # The assumption here is that gcDestructors means we cannot deal
+  # with cycles properly, so it's better to produce a weak ref (=ptr) here.
+  # This seems to be generally correct but since it's a bit risky it's disabled
+  # for now.
+  # XXX This is wrong for the 'hamming' test, so remove this logic again.
+  let fieldType = if isDefined(c.graph.config, "nimCycleBreaker"):
+                    c.getEnvTypeForOwnerUp(dep, info) #getHiddenParam(dep).typ
+                  else:
+                    c.getEnvTypeForOwner(dep, info)
+  if refObj == fieldType:
+    localError(c.graph.config, dep.info, "internal error: invalid up reference computed")
+
+  let upIdent = getIdent(c.graph.cache, upName)
+  let upField = lookupInRecord(obj.n, upIdent)
+  if upField != nil:
+    if upField.typ.skipTypes({tyOwned, tyRef, tyPtr}) != fieldType.skipTypes({tyOwned, tyRef, tyPtr}):
+      localError(c.graph.config, dep.info, "internal error: up references do not agree")
+
+    when false:
+      if c.graph.config.selectedGC == gcDestructors and sfCursor notin upField.flags:
+        localError(c.graph.config, dep.info, "internal error: up reference is not a .cursor")
+  else:
+    let result = newSym(skField, upIdent, c.idgen, obj.owner, obj.owner.info)
+    result.typ = fieldType
+    when false:
+      if c.graph.config.selectedGC == gcDestructors:
+        result.flags.incl sfCursor
+    rawAddField(obj, result)
+
+discard """
+There are a couple of possibilities of how to implement closure
+iterators that capture outer variables in a traditional sense
+(aka closure closure iterators).
+
+1. Transform iter() to  iter(state, capturedEnv). So use 2 hidden
+   parameters.
+2. Add the captured vars directly to 'state'.
+3. Make capturedEnv an up-reference of 'state'.
+
+We do (3) here because (2) is obviously wrong and (1) is wrong too.
+Consider:
+
+  proc outer =
+    var xx = 9
+
+    iterator foo() =
+      var someState = 3
+
+      proc bar = echo someState
+      proc baz = someState = 0
+      baz()
+      bar()
+
+"""
+
+proc isTypeOf(n: PNode): bool =
+  n.kind == nkSym and n.sym.magic in {mTypeOf, mType}
+
+proc addClosureParam(c: var DetectionPass; fn: PSym; info: TLineInfo) =
+  var cp = getEnvParam(fn)
+  let owner = if fn.kind == skIterator: fn else: fn.skipGenericOwner
+  let t = c.getEnvTypeForOwner(owner, info)
+  if cp == nil:
+    cp = newSym(skParam, getIdent(c.graph.cache, paramName), c.idgen, fn, fn.info)
+    incl(cp.flags, sfFromGeneric)
+    cp.typ = t
+    addHiddenParam(fn, cp)
+  elif cp.typ != t and fn.kind != skIterator:
+    localError(c.graph.config, fn.info, "internal error: inconsistent environment type")
+  #echo "adding closure to ", fn.name.s
+
+proc detectCapturedVars(n: PNode; owner: PSym; c: var DetectionPass) =
+  case n.kind
+  of nkSym:
+    let s = n.sym
+    if s.kind in {skProc, skFunc, skMethod, skConverter, skIterator} and
+        s.typ != nil and s.typ.callConv == ccClosure:
+      # this handles the case that the inner proc was declared as
+      # .closure but does not actually capture anything:
+      addClosureParam(c, s, n.info)
+      c.somethingToDo = true
+
+    let innerProc = isInnerProc(s)
+    if innerProc:
+      if s.isIterator: c.somethingToDo = true
+      if not c.processed.containsOrIncl(s.id):
+        let body = transformBody(c.graph, c.idgen, s, {useCache})
+        detectCapturedVars(body, s, c)
+    let ow = s.skipGenericOwner
+    let innerClosure = innerProc and s.typ.callConv == ccClosure and not s.isIterator
+    let interested = interestingVar(s)
+    if ow == owner:
+      if owner.isIterator:
+        c.somethingToDo = true
+        addClosureParam(c, owner, n.info)
+        if not isDefined(c.graph.config, "nimOptIters") and interestingIterVar(s):
+          if not c.capturedVars.contains(s.id):
+            if not c.inTypeOf: c.capturedVars.incl(s.id)
+            let obj = getHiddenParam(c.graph, owner).typ.skipTypes({tyOwned, tyRef, tyPtr})
+            #let obj = c.getEnvTypeForOwner(s.owner).skipTypes({tyOwned, tyRef, tyPtr})
+
+            if s.name.id == getIdent(c.graph.cache, ":state").id:
+              obj.n[0].sym.flags.incl sfNoInit
+              obj.n[0].sym.itemId = ItemId(module: s.itemId.module, item: -s.itemId.item)
+            else:
+              discard addField(obj, s, c.graph.cache, c.idgen)
+    # direct or indirect dependency:
+    elif innerClosure or interested:
+      discard """
+        proc outer() =
+          var x: int
+          proc inner() =
+            proc innerInner() =
+              echo x
+            innerInner()
+          inner()
+        # inner() takes a closure too!
+      """
+      # mark 'owner' as taking a closure:
+      c.somethingToDo = true
+      markAsClosure(c.graph, owner, n)
+      addClosureParam(c, owner, n.info)
+      #echo "capturing ", n.info
+      # variable 's' is actually captured:
+      if interestingVar(s):
+        if not c.capturedVars.contains(s.id):
+          if not c.inTypeOf: c.capturedVars.incl(s.id)
+          let obj = c.getEnvTypeForOwner(ow, n.info).skipTypes({tyOwned, tyRef, tyPtr})
+          #getHiddenParam(owner).typ.skipTypes({tyOwned, tyRef, tyPtr})
+          discard addField(obj, s, c.graph.cache, c.idgen)
+      # create required upFields:
+      var w = owner.skipGenericOwner
+      if isInnerProc(w) or owner.isIterator:
+        if owner.isIterator: w = owner
+        let last = if ow.isIterator: ow.skipGenericOwner else: ow
+        while w != nil and w.kind != skModule and last != w:
+          discard """
+          proc outer =
+            var a, b: int
+            proc outerB =
+              proc innerA = use(a)
+              proc innerB = use(b); innerA()
+          # --> make outerB of calling convention .closure and
+          # give it the same env type that outer's env var gets:
+          """
+          let up = w.skipGenericOwner
+          #echo "up for ", w.name.s, " up ", up.name.s
+          markAsClosure(c.graph, w, n)
+          addClosureParam(c, w, n.info) # , ow
+          createUpField(c, w, up, n.info)
+          w = up
+  of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit,
+     nkTemplateDef, nkTypeSection, nkProcDef, nkMethodDef,
+     nkConverterDef, nkMacroDef, nkFuncDef, nkCommentStmt,
+     nkTypeOfExpr, nkMixinStmt, nkBindStmt:
+    discard
+  of nkLambdaKinds, nkIteratorDef:
+    if n.typ != nil:
+      detectCapturedVars(n[namePos], owner, c)
+  of nkReturnStmt:
+    detectCapturedVars(n[0], owner, c)
+  of nkIdentDefs:
+    detectCapturedVars(n[^1], owner, c)
+  else:
+    if n.isCallExpr and n[0].isTypeOf:
+      c.inTypeOf = true
+    for i in 0..<n.len:
+      detectCapturedVars(n[i], owner, c)
+    c.inTypeOf = false
+
+type
+  LiftingPass = object
+    processed: IntSet
+    envVars: Table[int, PNode]
+    inContainer: int
+    unownedEnvVars: Table[int, PNode] # only required for --newruntime
+
+proc initLiftingPass(fn: PSym): LiftingPass =
+  result = LiftingPass(processed: toIntSet([fn.id]),
+                envVars: initTable[int, PNode]())
+
+proc accessViaEnvParam(g: ModuleGraph; n: PNode; owner: PSym): PNode =
+  let s = n.sym
+  # Type based expression construction for simplicity:
+  let envParam = getHiddenParam(g, owner)
+  if not envParam.isNil:
+    var access = newSymNode(envParam)
+    var obj = access.typ.elementType
+    while true:
+      assert obj.kind == tyObject
+      let field = getFieldFromObj(obj, s)
+      if field != nil:
+        return rawIndirectAccess(access, field, n.info)
+      let upField = lookupInRecord(obj.n, getIdent(g.cache, upName))
+      if upField == nil: break
+      access = rawIndirectAccess(access, upField, n.info)
+      obj = access.typ.baseClass
+  localError(g.config, n.info, "internal error: environment misses: " & s.name.s)
+  result = n
+
+proc newEnvVar(cache: IdentCache; owner: PSym; typ: PType; info: TLineInfo; idgen: IdGenerator): PNode =
+  var v = newSym(skVar, getIdent(cache, envName), idgen, owner, info)
+  v.flags = {sfShadowed, sfGeneratedOp}
+  v.typ = typ
+  result = newSymNode(v)
+  when false:
+    if owner.kind == skIterator and owner.typ.callConv == ccClosure:
+      let it = getHiddenParam(owner)
+      addUniqueField(it.typ.elementType, v)
+      result = indirectAccess(newSymNode(it), v, v.info)
+    else:
+      result = newSymNode(v)
+
+proc setupEnvVar(owner: PSym; d: var DetectionPass;
+                 c: var LiftingPass; info: TLineInfo): PNode =
+  if owner.isIterator:
+    return getHiddenParam(d.graph, owner).newSymNode
+  result = c.envVars.getOrDefault(owner.id)
+  if result.isNil:
+    let envVarType = d.ownerToType.getOrDefault(owner.id)
+    if envVarType.isNil:
+      localError d.graph.config, owner.info, "internal error: could not determine closure type"
+    result = newEnvVar(d.graph.cache, owner, asOwnedRef(d, envVarType), info, d.idgen)
+    c.envVars[owner.id] = result
+    if optOwnedRefs in d.graph.config.globalOptions:
+      var v = newSym(skVar, getIdent(d.graph.cache, envName & "Alt"), d.idgen, owner, info)
+      v.flags = {sfShadowed, sfGeneratedOp}
+      v.typ = envVarType
+      c.unownedEnvVars[owner.id] = newSymNode(v)
+
+proc getUpViaParam(g: ModuleGraph; owner: PSym): PNode =
+  let p = getHiddenParam(g, owner)
+  result = p.newSymNode
+  if owner.isIterator:
+    let upField = lookupInRecord(p.typ.skipTypes({tyOwned, tyRef, tyPtr}).n, getIdent(g.cache, upName))
+    if upField == nil:
+      localError(g.config, owner.info, "could not find up reference for closure iter")
+    else:
+      result = rawIndirectAccess(result, upField, p.info)
+
+proc rawClosureCreation(owner: PSym;
+                        d: var DetectionPass; c: var LiftingPass;
+                        info: TLineInfo): PNode =
+  result = newNodeI(nkStmtList, owner.info)
+
+  var env: PNode
+  if owner.isIterator:
+    env = getHiddenParam(d.graph, owner).newSymNode
+  else:
+    env = setupEnvVar(owner, d, c, info)
+    if env.kind == nkSym:
+      var v = newNodeI(nkVarSection, env.info)
+      addVar(v, env)
+      result.add(v)
+      if optOwnedRefs in d.graph.config.globalOptions:
+        let unowned = c.unownedEnvVars[owner.id]
+        assert unowned != nil
+        addVar(v, unowned)
+
+    # add 'new' statement:
+    result.add genCreateEnv(env)
+    if optOwnedRefs in d.graph.config.globalOptions:
+      let unowned = c.unownedEnvVars[owner.id]
+      assert unowned != nil
+      let env2 = copyTree(env)
+      env2.typ = unowned.typ
+      result.add newAsgnStmt(unowned, env2, env.info)
+      createTypeBoundOpsLL(d.graph, unowned.typ, env.info, d.idgen, owner)
+
+    # add assignment statements for captured parameters:
+    for i in 1..<owner.typ.n.len:
+      let local = owner.typ.n[i].sym
+      if local.id in d.capturedVars:
+        let fieldAccess = indirectAccess(env, local, env.info)
+        # add ``env.param = param``
+        result.add(newAsgnStmt(fieldAccess, newSymNode(local), env.info))
+        if owner.kind != skMacro:
+          createTypeBoundOps(d.graph, nil, fieldAccess.typ, env.info, d.idgen)
+        if tfHasAsgn in fieldAccess.typ.flags or optSeqDestructors in d.graph.config.globalOptions:
+          owner.flags.incl sfInjectDestructors
+
+  let upField = lookupInRecord(env.typ.skipTypes({tyOwned, tyRef, tyPtr}).n, getIdent(d.graph.cache, upName))
+  if upField != nil:
+    let up = getUpViaParam(d.graph, owner)
+    if up != nil and upField.typ.skipTypes({tyOwned, tyRef, tyPtr}) == up.typ.skipTypes({tyOwned, tyRef, tyPtr}):
+      result.add(newAsgnStmt(rawIndirectAccess(env, upField, env.info),
+                 up, env.info))
+    #elif oldenv != nil and oldenv.typ == upField.typ:
+    #  result.add(newAsgnStmt(rawIndirectAccess(env, upField, env.info),
+    #             oldenv, env.info))
+    else:
+      localError(d.graph.config, env.info, "internal error: cannot create up reference")
+  # we are not in the sem'check phase anymore! so pass 'nil' for the PContext
+  # and hope for the best:
+  createTypeBoundOpsLL(d.graph, env.typ, owner.info, d.idgen, owner)
+
+proc finishClosureCreation(owner: PSym; d: var DetectionPass; c: LiftingPass;
+                           info: TLineInfo; res: PNode) =
+  if optOwnedRefs in d.graph.config.globalOptions:
+    let unowned = c.unownedEnvVars[owner.id]
+    assert unowned != nil
+    let nilLit = newNodeIT(nkNilLit, info, unowned.typ)
+    res.add newAsgnStmt(unowned, nilLit, info)
+    createTypeBoundOpsLL(d.graph, unowned.typ, info, d.idgen, owner)
+
+proc closureCreationForIter(iter: PNode;
+                            d: var DetectionPass; c: var LiftingPass): PNode =
+  result = newNodeIT(nkStmtListExpr, iter.info, iter.sym.typ)
+  let owner = iter.sym.skipGenericOwner
+  var v = newSym(skVar, getIdent(d.graph.cache, envName), d.idgen, owner, iter.info)
+  incl(v.flags, sfShadowed)
+  v.typ = asOwnedRef(d, getHiddenParam(d.graph, iter.sym).typ)
+  var vnode: PNode
+  if owner.isIterator:
+    let it = getHiddenParam(d.graph, owner)
+    addUniqueField(it.typ.skipTypes({tyOwned, tyRef, tyPtr}), v, d.graph.cache, d.idgen)
+    vnode = indirectAccess(newSymNode(it), v, v.info)
+  else:
+    vnode = v.newSymNode
+    var vs = newNodeI(nkVarSection, iter.info)
+    addVar(vs, vnode)
+    result.add(vs)
+  result.add genCreateEnv(vnode)
+  createTypeBoundOpsLL(d.graph, vnode.typ, iter.info, d.idgen, owner)
+
+  let upField = lookupInRecord(v.typ.skipTypes({tyOwned, tyRef, tyPtr}).n, getIdent(d.graph.cache, upName))
+  if upField != nil:
+    let u = setupEnvVar(owner, d, c, iter.info)
+    if u.typ.skipTypes({tyOwned, tyRef, tyPtr}) == upField.typ.skipTypes({tyOwned, tyRef, tyPtr}):
+      result.add(newAsgnStmt(rawIndirectAccess(vnode, upField, iter.info),
+                 u, iter.info))
+    else:
+      localError(d.graph.config, iter.info, "internal error: cannot create up reference for iter")
+  result.add makeClosure(d.graph, d.idgen, iter.sym, vnode, iter.info)
+
+proc accessViaEnvVar(n: PNode; owner: PSym; d: var DetectionPass;
+                     c: var LiftingPass): PNode =
+  var access = setupEnvVar(owner, d, c, n.info)
+  if optOwnedRefs in d.graph.config.globalOptions:
+    access = c.unownedEnvVars[owner.id]
+  let obj = access.typ.skipTypes({tyOwned, tyRef, tyPtr})
+  let field = getFieldFromObj(obj, n.sym)
+  if field != nil:
+    result = rawIndirectAccess(access, field, n.info)
+  else:
+    localError(d.graph.config, n.info, "internal error: not part of closure object type")
+    result = n
+
+proc getStateField*(g: ModuleGraph; owner: PSym): PSym =
+  getHiddenParam(g, owner).typ.skipTypes({tyOwned, tyRef, tyPtr}).n[0].sym
+
+proc liftCapturedVars(n: PNode; owner: PSym; d: var DetectionPass;
+                      c: var LiftingPass): PNode
+
+proc symToClosure(n: PNode; owner: PSym; d: var DetectionPass;
+                  c: var LiftingPass): PNode =
+  let s = n.sym
+  if s == owner:
+    # recursive calls go through (lambda, hiddenParam):
+    let available = getHiddenParam(d.graph, owner)
+    result = makeClosure(d.graph, d.idgen, s, available.newSymNode, n.info)
+  elif s.isIterator:
+    result = closureCreationForIter(n, d, c)
+  elif s.skipGenericOwner == owner:
+    # direct dependency, so use the outer's env variable:
+    result = makeClosure(d.graph, d.idgen, s, setupEnvVar(owner, d, c, n.info), n.info)
+  else:
+    result = nil
+    let available = getHiddenParam(d.graph, owner)
+    let wanted = getHiddenParam(d.graph, s).typ
+    # ugh: call through some other inner proc;
+    var access = newSymNode(available)
+    while true:
+      if access.typ == wanted:
+        return makeClosure(d.graph, d.idgen, s, access, n.info)
+      let obj = access.typ.skipTypes({tyOwned, tyRef, tyPtr})
+      let upField = lookupInRecord(obj.n, getIdent(d.graph.cache, upName))
+      if upField == nil:
+        localError(d.graph.config, n.info, "internal error: no environment found")
+        return n
+      access = rawIndirectAccess(access, upField, n.info)
+
+proc liftCapturedVars(n: PNode; owner: PSym; d: var DetectionPass;
+                      c: var LiftingPass): PNode =
+  result = n
+  case n.kind
+  of nkSym:
+    let s = n.sym
+    if isInnerProc(s):
+      if not c.processed.containsOrIncl(s.id):
+        #if s.name.s == "temp":
+        #  echo renderTree(s.getBody, {renderIds})
+        let oldInContainer = c.inContainer
+        c.inContainer = 0
+        var body = transformBody(d.graph, d.idgen, s, {})
+        body = liftCapturedVars(body, s, d, c)
+        if c.envVars.getOrDefault(s.id).isNil:
+          s.transformedBody = body
+        else:
+          s.transformedBody = newTree(nkStmtList, rawClosureCreation(s, d, c, n.info), body)
+          finishClosureCreation(s, d, c, n.info, s.transformedBody)
+        c.inContainer = oldInContainer
+
+      if s.typ.callConv == ccClosure:
+        result = symToClosure(n, owner, d, c)
+
+    elif s.id in d.capturedVars:
+      if s.owner != owner:
+        result = accessViaEnvParam(d.graph, n, owner)
+      elif owner.isIterator and not isDefined(d.graph.config, "nimOptIters") and interestingIterVar(s):
+        result = accessViaEnvParam(d.graph, n, owner)
+      else:
+        result = accessViaEnvVar(n, owner, d, c)
+  of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit, nkComesFrom,
+     nkTemplateDef, nkTypeSection, nkProcDef, nkMethodDef, nkConverterDef,
+     nkMacroDef, nkFuncDef, nkMixinStmt, nkBindStmt:
+    discard
+  of nkClosure:
+    if n[1].kind == nkNilLit:
+      n[0] = liftCapturedVars(n[0], owner, d, c)
+      let x = n[0].skipConv
+      if x.kind == nkClosure:
+        #localError(n.info, "internal error: closure to closure created")
+        # now we know better, so patch it:
+        n[0] = x[0]
+        n[1] = x[1]
+  of nkLambdaKinds, nkIteratorDef:
+    if n.typ != nil and n[namePos].kind == nkSym:
+      let oldInContainer = c.inContainer
+      c.inContainer = 0
+      let m = newSymNode(n[namePos].sym)
+      m.typ = n.typ
+      result = liftCapturedVars(m, owner, d, c)
+      c.inContainer = oldInContainer
+  of nkHiddenStdConv:
+    if n.len == 2:
+      n[1] = liftCapturedVars(n[1], owner, d, c)
+      if n[1].kind == nkClosure: result = n[1]
+  of nkReturnStmt:
+    if n[0].kind in {nkAsgn, nkFastAsgn, nkSinkAsgn}:
+      # we have a `result = result` expression produced by the closure
+      # transform, let's not touch the LHS in order to make the lifting pass
+      # correct when `result` is lifted
+      n[0][1] = liftCapturedVars(n[0][1], owner, d, c)
+    else:
+      n[0] = liftCapturedVars(n[0], owner, d, c)
+  of nkTypeOfExpr:
+    result = n
+  else:
+    if n.isCallExpr and n[0].isTypeOf:
+      return
+    if owner.isIterator:
+      if nfLL in n.flags:
+        # special case 'when nimVm' due to bug #3636:
+        n[1] = liftCapturedVars(n[1], owner, d, c)
+        return
+
+    let inContainer = n.kind in {nkObjConstr, nkBracket}
+    if inContainer: inc c.inContainer
+    for i in 0..<n.len:
+      n[i] = liftCapturedVars(n[i], owner, d, c)
+    if inContainer: dec c.inContainer
+
+# ------------------ old stuff -------------------------------------------
+
+proc semCaptureSym*(s, owner: PSym) =
+  discard """
+    proc outer() =
+      var x: int
+      proc inner() =
+        proc innerInner() =
+          echo x
+        innerInner()
+      inner()
+    # inner() takes a closure too!
+  """
+  proc propagateClosure(start, last: PSym) =
+    var o = start
+    while o != nil and o.kind != skModule:
+      if o == last: break
+      o.typ.callConv = ccClosure
+      o = o.skipGenericOwner
+
+  if interestingVar(s) and s.kind != skResult:
+    if owner.typ != nil and not isGenericRoutine(owner):
+      # XXX: is this really safe?
+      # if we capture a var from another generic routine,
+      # it won't be consider captured.
+      var o = owner.skipGenericOwner
+      while o != nil and o.kind != skModule:
+        if s.owner == o:
+          if owner.typ.callConv == ccClosure or owner.kind == skIterator or
+             owner.typ.callConv == ccNimCall and tfExplicitCallConv notin owner.typ.flags:
+            owner.typ.callConv = ccClosure
+            propagateClosure(owner.skipGenericOwner, s.owner)
+          else:
+            discard "do not produce an error here, but later"
+          #echo "computing .closure for ", owner.name.s, " because of ", s.name.s
+        o = o.skipGenericOwner
+    # since the analysis is not entirely correct, we don't set 'tfCapturesEnv'
+    # here
+
+proc liftIterToProc*(g: ModuleGraph; fn: PSym; body: PNode; ptrType: PType;
+                     idgen: IdGenerator): PNode =
+  var d = initDetectionPass(g, fn, idgen)
+  var c = initLiftingPass(fn)
+  # pretend 'fn' is a closure iterator for the analysis:
+  let oldKind = fn.kind
+  let oldCC = fn.typ.callConv
+  fn.transitionRoutineSymKind(skIterator)
+  fn.typ.callConv = ccClosure
+  d.ownerToType[fn.id] = ptrType
+  detectCapturedVars(body, fn, d)
+  result = liftCapturedVars(body, fn, d, c)
+  fn.transitionRoutineSymKind(oldKind)
+  fn.typ.callConv = oldCC
+
+proc liftLambdas*(g: ModuleGraph; fn: PSym, body: PNode; tooEarly: var bool;
+                  idgen: IdGenerator; flags: TransformFlags): PNode =
+  let isCompileTime = sfCompileTime in fn.flags or fn.kind == skMacro
+
+  if body.kind == nkEmpty or (jsNoLambdaLifting in g.config.legacyFeatures and
+      g.config.backend == backendJs and not isCompileTime) or
+      (fn.skipGenericOwner.kind != skModule and force notin flags):
+
+    # ignore forward declaration:
+    result = body
+    tooEarly = true
+    if fn.isIterator and isDefined(g.config, "nimOptIters"):
+      var d = initDetectionPass(g, fn, idgen)
+      addClosureParam(d, fn, body.info)
+  else:
+    var d = initDetectionPass(g, fn, idgen)
+    detectCapturedVars(body, fn, d)
+    if not d.somethingToDo and fn.isIterator:
+      addClosureParam(d, fn, body.info)
+      d.somethingToDo = true
+    if d.somethingToDo:
+      var c = initLiftingPass(fn)
+      result = liftCapturedVars(body, fn, d, c)
+      # echo renderTree(result, {renderIds})
+      if c.envVars.getOrDefault(fn.id) != nil:
+        result = newTree(nkStmtList, rawClosureCreation(fn, d, c, body.info), result)
+        finishClosureCreation(fn, d, c, body.info, result)
+    else:
+      result = body
+    #if fn.name.s == "get2":
+    #  echo "had something to do ", d.somethingToDo
+    #  echo renderTree(result, {renderIds})
+
+proc liftLambdasForTopLevel*(module: PSym, body: PNode): PNode =
+  # XXX implement it properly
+  result = body
+
+# ------------------- iterator transformation --------------------------------
+
+proc liftForLoop*(g: ModuleGraph; body: PNode; idgen: IdGenerator; owner: PSym): PNode =
+  # problem ahead: the iterator could be invoked indirectly, but then
+  # we don't know what environment to create here:
+  #
+  # iterator count(): int =
+  #   yield 0
+  #
+  # iterator count2(): int =
+  #   var x = 3
+  #   yield x
+  #   inc x
+  #   yield x
+  #
+  # proc invoke(iter: iterator(): int) =
+  #   for x in iter(): echo x
+  #
+  # --> When to create the closure? --> for the (count) occurrence!
+  discard """
+      for i in foo(): ...
+
+    Is transformed to:
+
+      cl = createClosure()
+      while true:
+        let i = foo(cl)
+        if (nkBreakState(cl.state)):
+          break
+        ...
+    """
+  if liftingHarmful(g.config, owner): return body
+  if not (body.kind == nkForStmt and body[^2].kind in nkCallKinds):
+    localError(g.config, body.info, "ignored invalid for loop")
+    return body
+  var call = body[^2]
+
+  result = newNodeI(nkStmtList, body.info)
+
+  # static binding?
+  var env: PSym = nil
+  let op = call[0]
+  if op.kind == nkSym and op.sym.isIterator:
+    # createClosure()
+    let iter = op.sym
+
+    let hp = getHiddenParam(g, iter)
+    env = newSym(skLet, iter.name, idgen, owner, body.info)
+    env.typ = hp.typ
+    env.flags = hp.flags
+
+    var v = newNodeI(nkVarSection, body.info)
+    addVar(v, newSymNode(env))
+    result.add(v)
+    # add 'new' statement:
+    result.add genCreateEnv(env.newSymNode)
+    createTypeBoundOpsLL(g, env.typ, body.info, idgen, owner)
+
+  elif op.kind == nkStmtListExpr:
+    let closure = op.lastSon
+    if closure.kind == nkClosure:
+      call[0] = closure
+      for i in 0..<op.len-1:
+        result.add op[i]
+
+  var loopBody = newNodeI(nkStmtList, body.info, 3)
+  var whileLoop = newNodeI(nkWhileStmt, body.info, 2)
+  whileLoop[0] = newIntTypeNode(1, getSysType(g, body.info, tyBool))
+  whileLoop[1] = loopBody
+  result.add whileLoop
+
+  # setup loopBody:
+  # gather vars in a tuple:
+  var v2 = newNodeI(nkLetSection, body.info)
+  var vpart = newNodeI(if body.len == 3: nkIdentDefs else: nkVarTuple, body.info)
+  if body.len == 3 and body[0].kind == nkVarTuple:
+    vpart = body[0] # fixes for (i,j) in walk() # bug #15924
+  else:
+    for i in 0..<body.len-2:
+      if body[i].kind == nkSym:
+        body[i].sym.transitionToLet()
+      vpart.add body[i]
+
+    vpart.add newNodeI(nkEmpty, body.info) # no explicit type
+  if not env.isNil:
+    call[0] = makeClosure(g, idgen, call[0].sym, env.newSymNode, body.info)
+  vpart.add call
+  v2.add vpart
+
+  loopBody[0] = v2
+  var bs = newNodeI(nkBreakState, body.info)
+  bs.add call[0]
+
+  let ibs = newNodeI(nkIfStmt, body.info)
+  let elifBranch = newNodeI(nkElifBranch, body.info)
+  elifBranch.add(bs)
+
+  let br = newNodeI(nkBreakStmt, body.info)
+  br.add(g.emptyNode)
+
+  elifBranch.add(br)
+  ibs.add(elifBranch)
+
+  loopBody[1] = ibs
+  loopBody[2] = body[^1]