1#
2#
3#           The Nim Compiler
4#        (c) Copyright 2015 Andreas Rumpf
5#
6#    See the file "copying.txt", included in this
7#    distribution, for details about the copyright.
8#
9
10# This file implements lambda lifting for the transformator.
11
12import
13  intsets, strutils, options, ast, astalgo, msgs,
14  idents, renderer, types, magicsys, lowerings, tables, modulegraphs, lineinfos,
15  transf, liftdestructors, typeallowed
16
17discard """
18  The basic approach is that captured vars need to be put on the heap and
19  that the calling chain needs to be explicitly modelled. Things to consider:
20
21  proc a =
22    var v = 0
23    proc b =
24      var w = 2
25
26      for x in 0..3:
27        proc c = capture v, w, x
28        c()
29    b()
30
31    for x in 0..4:
32      proc d = capture x
33      d()
34
35  Needs to be translated into:
36
37  proc a =
38    var cl: *
39    new cl
40    cl.v = 0
41
42    proc b(cl) =
43      var bcl: *
44      new bcl
45      bcl.w = 2
46      bcl.up = cl
47
48      for x in 0..3:
49        var bcl2: *
50        new bcl2
51        bcl2.up = bcl
52        bcl2.up2 = cl
53        bcl2.x = x
54
55        proc c(cl) = capture cl.up2.v, cl.up.w, cl.x
56        c(bcl2)
57
58      c(bcl)
59
60    b(cl)
61
62    for x in 0..4:
63      var acl2: *
64      new acl2
65      acl2.x = x
66      proc d(cl) = capture cl.x
67      d(acl2)
68
69  Closures as interfaces:
70
71  proc outer: T =
72    var captureMe: TObject # value type required for efficiency
73    proc getter(): int = result = captureMe.x
74    proc setter(x: int) = captureMe.x = x
75
76    result = (getter, setter)
77
78  Is translated to:
79
80  proc outer: T =
81    var cl: *
82    new cl
83
84    proc getter(cl): int = result = cl.captureMe.x
85    proc setter(cl: *, x: int) = cl.captureMe.x = x
86
87    result = ((cl, getter), (cl, setter))
88
89
90  For 'byref' capture, the outer proc needs to access the captured var through
91  the indirection too. For 'bycopy' capture, the outer proc accesses the var
92  not through the indirection.
93
94  Possible optimizations:
95
96  1) If the closure contains a single 'ref' and this
97  reference is not re-assigned (check ``sfAddrTaken`` flag) make this the
98  closure. This is an important optimization if closures are used as
99  interfaces.
100  2) If the closure does not escape, put it onto the stack, not on the heap.
101  3) Dataflow analysis would help to eliminate the 'up' indirections.
102  4) If the captured var is not actually used in the outer proc (common?),
103  put it into an inner proc.
104
105"""
106
107# Important things to keep in mind:
108# * Don't base the analysis on nkProcDef et al. This doesn't work for
109#   instantiated (formerly generic) procs. The analysis has to look at nkSym.
110#   This also means we need to prevent the same proc is processed multiple
111#   times via the 'processed' set.
112# * Keep in mind that the owner of some temporaries used to be unreliable.
113# * For closure iterators we merge the "real" potential closure with the
114#   local storage requirements for efficiency. This means closure iterators
115#   have slightly different semantics from ordinary closures.
116
117# ---------------- essential helpers -------------------------------------
118
119const
120  upName* = ":up" # field name for the 'up' reference
121  paramName* = ":envP"
122  envName* = ":env"
123
124proc newCall(a: PSym, b: PNode): PNode =
125  result = newNodeI(nkCall, a.info)
126  result.add newSymNode(a)
127  result.add b
128
129proc createClosureIterStateType*(g: ModuleGraph; iter: PSym; idgen: IdGenerator): PType =
130  var n = newNodeI(nkRange, iter.info)
131  n.add newIntNode(nkIntLit, -1)
132  n.add newIntNode(nkIntLit, 0)
133  result = newType(tyRange, nextTypeId(idgen), iter)
134  result.n = n
135  var intType = nilOrSysInt(g)
136  if intType.isNil: intType = newType(tyInt, nextTypeId(idgen), iter)
137  rawAddSon(result, intType)
138
139proc createStateField(g: ModuleGraph; iter: PSym; idgen: IdGenerator): PSym =
140  result = newSym(skField, getIdent(g.cache, ":state"), nextSymId(idgen), iter, iter.info)
141  result.typ = createClosureIterStateType(g, iter, idgen)
142
143proc createEnvObj(g: ModuleGraph; idgen: IdGenerator; owner: PSym; info: TLineInfo): PType =
144  # YYY meh, just add the state field for every closure for now, it's too
145  # hard to figure out if it comes from a closure iterator:
146  result = createObj(g, idgen, owner, info, final=false)
147  rawAddField(result, createStateField(g, owner, idgen))
148
149proc getClosureIterResult*(g: ModuleGraph; iter: PSym; idgen: IdGenerator): PSym =
150  if resultPos < iter.ast.len:
151    result = iter.ast[resultPos].sym
152  else:
153    # XXX a bit hacky:
154    result = newSym(skResult, getIdent(g.cache, ":result"), nextSymId(idgen), iter, iter.info, {})
155    result.typ = iter.typ[0]
156    incl(result.flags, sfUsed)
157    iter.ast.add newSymNode(result)
158
159proc addHiddenParam(routine: PSym, param: PSym) =
160  assert param.kind == skParam
161  var params = routine.ast[paramsPos]
162  # -1 is correct here as param.position is 0 based but we have at position 0
163  # some nkEffect node:
164  param.position = routine.typ.n.len-1
165  params.add newSymNode(param)
166  #incl(routine.typ.flags, tfCapturesEnv)
167  assert sfFromGeneric in param.flags
168  #echo "produced environment: ", param.id, " for ", routine.id
169
170proc getHiddenParam(g: ModuleGraph; routine: PSym): PSym =
171  let params = routine.ast[paramsPos]
172  let hidden = lastSon(params)
173  if hidden.kind == nkSym and hidden.sym.kind == skParam and hidden.sym.name.s == paramName:
174    result = hidden.sym
175    assert sfFromGeneric in result.flags
176  else:
177    # writeStackTrace()
178    localError(g.config, routine.info, "internal error: could not find env param for " & routine.name.s)
179    result = routine
180
181proc getEnvParam*(routine: PSym): PSym =
182  let params = routine.ast[paramsPos]
183  let hidden = lastSon(params)
184  if hidden.kind == nkSym and hidden.sym.name.s == paramName:
185    result = hidden.sym
186    assert sfFromGeneric in result.flags
187
188proc interestingVar(s: PSym): bool {.inline.} =
189  result = s.kind in {skVar, skLet, skTemp, skForVar, skParam, skResult} and
190    sfGlobal notin s.flags and
191    s.typ.kind notin {tyStatic, tyTypeDesc}
192
193proc illegalCapture(s: PSym): bool {.inline.} =
194  result = classifyViewType(s.typ) != noView or s.kind == skResult
195
196proc isInnerProc(s: PSym): bool =
197  if s.kind in {skProc, skFunc, skMethod, skConverter, skIterator} and s.magic == mNone:
198    result = s.skipGenericOwner.kind in routineKinds
199
200proc newAsgnStmt(le, ri: PNode, info: TLineInfo): PNode =
201  # Bugfix: unfortunately we cannot use 'nkFastAsgn' here as that would
202  # mean to be able to capture string literals which have no GC header.
203  # However this can only happen if the capture happens through a parameter,
204  # which is however the only case when we generate an assignment in the first
205  # place.
206  result = newNodeI(nkAsgn, info, 2)
207  result[0] = le
208  result[1] = ri
209
210proc makeClosure*(g: ModuleGraph; idgen: IdGenerator; prc: PSym; env: PNode; info: TLineInfo): PNode =
211  result = newNodeIT(nkClosure, info, prc.typ)
212  result.add(newSymNode(prc))
213  if env == nil:
214    result.add(newNodeIT(nkNilLit, info, getSysType(g, info, tyNil)))
215  else:
216    if env.skipConv.kind == nkClosure:
217      localError(g.config, info, "internal error: taking closure of closure")
218    result.add(env)
219  #if isClosureIterator(result.typ):
220  createTypeBoundOps(g, nil, result.typ, info, idgen)
221  if tfHasAsgn in result.typ.flags or optSeqDestructors in g.config.globalOptions:
222    prc.flags.incl sfInjectDestructors
223
224proc interestingIterVar(s: PSym): bool {.inline.} =
225  # XXX optimization: Only lift the variable if it lives across
226  # yield/return boundaries! This can potentially speed up
227  # closure iterators quite a bit.
228  result = s.kind in {skResult, skVar, skLet, skTemp, skForVar} and sfGlobal notin s.flags
229
230template isIterator*(owner: PSym): bool =
231  owner.kind == skIterator and owner.typ.callConv == ccClosure
232
233proc liftingHarmful(conf: ConfigRef; owner: PSym): bool {.inline.} =
234  ## lambda lifting can be harmful for JS-like code generators.
235  let isCompileTime = sfCompileTime in owner.flags or owner.kind == skMacro
236  result = conf.backend == backendJs and not isCompileTime
237
238proc createTypeBoundOpsLL(g: ModuleGraph; refType: PType; info: TLineInfo; idgen: IdGenerator; owner: PSym) =
239  if owner.kind != skMacro:
240    createTypeBoundOps(g, nil, refType.lastSon, info, idgen)
241    createTypeBoundOps(g, nil, refType, info, idgen)
242    if tfHasAsgn in refType.flags or optSeqDestructors in g.config.globalOptions:
243      owner.flags.incl sfInjectDestructors
244
245proc liftIterSym*(g: ModuleGraph; n: PNode; idgen: IdGenerator; owner: PSym): PNode =
246  # transforms  (iter)  to  (let env = newClosure[iter](); (iter, env))
247  if liftingHarmful(g.config, owner): return n
248  let iter = n.sym
249  assert iter.isIterator
250
251  result = newNodeIT(nkStmtListExpr, n.info, n.typ)
252
253  let hp = getHiddenParam(g, iter)
254  var env: PNode
255  if owner.isIterator:
256    let it = getHiddenParam(g, owner)
257    addUniqueField(it.typ.skipTypes({tyOwned})[0], hp, g.cache, idgen)
258    env = indirectAccess(newSymNode(it), hp, hp.info)
259  else:
260    let e = newSym(skLet, iter.name, nextSymId(idgen), owner, n.info)
261    e.typ = hp.typ
262    e.flags = hp.flags
263    env = newSymNode(e)
264    var v = newNodeI(nkVarSection, n.info)
265    addVar(v, env)
266    result.add(v)
267  # add 'new' statement:
268  result.add newCall(getSysSym(g, n.info, "internalNew"), env)
269  createTypeBoundOpsLL(g, env.typ, n.info, idgen, owner)
270  result.add makeClosure(g, idgen, iter, env, n.info)
271
272proc freshVarForClosureIter*(g: ModuleGraph; s: PSym; idgen: IdGenerator; owner: PSym): PNode =
273  let envParam = getHiddenParam(g, owner)
274  let obj = envParam.typ.skipTypes({tyOwned, tyRef, tyPtr})
275  addField(obj, s, g.cache, idgen)
276
277  var access = newSymNode(envParam)
278  assert obj.kind == tyObject
279  let field = getFieldFromObj(obj, s)
280  if field != nil:
281    result = rawIndirectAccess(access, field, s.info)
282  else:
283    localError(g.config, s.info, "internal error: cannot generate fresh variable")
284    result = access
285
286# ------------------ new stuff -------------------------------------------
287
288proc markAsClosure(g: ModuleGraph; owner: PSym; n: PNode) =
289  let s = n.sym
290  if illegalCapture(s):
291    localError(g.config, n.info,
292      ("'$1' is of type <$2> which cannot be captured as it would violate memory" &
293       " safety, declared here: $3; using '-d:nimNoLentIterators' helps in some cases") %
294      [s.name.s, typeToString(s.typ), g.config$s.info])
295  elif not (owner.typ.callConv == ccClosure or owner.typ.callConv == ccNimCall and tfExplicitCallConv notin owner.typ.flags):
296    localError(g.config, n.info, "illegal capture '$1' because '$2' has the calling convention: <$3>" %
297      [s.name.s, owner.name.s, $owner.typ.callConv])
298  incl(owner.typ.flags, tfCapturesEnv)
299  owner.typ.callConv = ccClosure
300
301type
302  DetectionPass = object
303    processed, capturedVars: IntSet
304    ownerToType: Table[int, PType]
305    somethingToDo: bool
306    graph: ModuleGraph
307    idgen: IdGenerator
308
309proc initDetectionPass(g: ModuleGraph; fn: PSym; idgen: IdGenerator): DetectionPass =
310  result.processed = initIntSet()
311  result.capturedVars = initIntSet()
312  result.ownerToType = initTable[int, PType]()
313  result.processed.incl(fn.id)
314  result.graph = g
315  result.idgen = idgen
316
317discard """
318proc outer =
319  var a, b: int
320  proc innerA = use(a)
321  proc innerB = use(b); innerA()
322# --> innerA and innerB need to *share* the closure type!
323This is why need to store the 'ownerToType' table and use it
324during .closure'fication.
325"""
326
327proc getEnvTypeForOwner(c: var DetectionPass; owner: PSym;
328                        info: TLineInfo): PType =
329  result = c.ownerToType.getOrDefault(owner.id)
330  if result.isNil:
331    result = newType(tyRef, nextTypeId(c.idgen), owner)
332    let obj = createEnvObj(c.graph, c.idgen, owner, info)
333    rawAddSon(result, obj)
334    c.ownerToType[owner.id] = result
335
336proc asOwnedRef(c: var DetectionPass; t: PType): PType =
337  if optOwnedRefs in c.graph.config.globalOptions:
338    assert t.kind == tyRef
339    result = newType(tyOwned, nextTypeId(c.idgen), t.owner)
340    result.flags.incl tfHasOwned
341    result.rawAddSon t
342  else:
343    result = t
344
345proc getEnvTypeForOwnerUp(c: var DetectionPass; owner: PSym;
346                          info: TLineInfo): PType =
347  var r = c.getEnvTypeForOwner(owner, info)
348  result = newType(tyPtr, nextTypeId(c.idgen), owner)
349  rawAddSon(result, r.skipTypes({tyOwned, tyRef, tyPtr}))
350
351proc createUpField(c: var DetectionPass; dest, dep: PSym; info: TLineInfo) =
352  let refObj = c.getEnvTypeForOwner(dest, info) # getHiddenParam(dest).typ
353  let obj = refObj.skipTypes({tyOwned, tyRef, tyPtr})
354  # The assumption here is that gcDestructors means we cannot deal
355  # with cycles properly, so it's better to produce a weak ref (=ptr) here.
356  # This seems to be generally correct but since it's a bit risky it's disabled
357  # for now.
358  # XXX This is wrong for the 'hamming' test, so remove this logic again.
359  let fieldType = if isDefined(c.graph.config, "nimCycleBreaker"):
360                    c.getEnvTypeForOwnerUp(dep, info) #getHiddenParam(dep).typ
361                  else:
362                    c.getEnvTypeForOwner(dep, info)
363  if refObj == fieldType:
364    localError(c.graph.config, dep.info, "internal error: invalid up reference computed")
365
366  let upIdent = getIdent(c.graph.cache, upName)
367  let upField = lookupInRecord(obj.n, upIdent)
368  if upField != nil:
369    if upField.typ.skipTypes({tyOwned, tyRef, tyPtr}) != fieldType.skipTypes({tyOwned, tyRef, tyPtr}):
370      localError(c.graph.config, dep.info, "internal error: up references do not agree")
371
372    when false:
373      if c.graph.config.selectedGC == gcDestructors and sfCursor notin upField.flags:
374        localError(c.graph.config, dep.info, "internal error: up reference is not a .cursor")
375  else:
376    let result = newSym(skField, upIdent, nextSymId(c.idgen), obj.owner, obj.owner.info)
377    result.typ = fieldType
378    when false:
379      if c.graph.config.selectedGC == gcDestructors:
380        result.flags.incl sfCursor
381    rawAddField(obj, result)
382
383discard """
384There are a couple of possibilities of how to implement closure
385iterators that capture outer variables in a traditional sense
386(aka closure closure iterators).
387
3881. Transform iter() to  iter(state, capturedEnv). So use 2 hidden
389   parameters.
3902. Add the captured vars directly to 'state'.
3913. Make capturedEnv an up-reference of 'state'.
392
393We do (3) here because (2) is obviously wrong and (1) is wrong too.
394Consider:
395
396  proc outer =
397    var xx = 9
398
399    iterator foo() =
400      var someState = 3
401
402      proc bar = echo someState
403      proc baz = someState = 0
404      baz()
405      bar()
406
407"""
408
409proc addClosureParam(c: var DetectionPass; fn: PSym; info: TLineInfo) =
410  var cp = getEnvParam(fn)
411  let owner = if fn.kind == skIterator: fn else: fn.skipGenericOwner
412  let t = c.getEnvTypeForOwner(owner, info)
413  if cp == nil:
414    cp = newSym(skParam, getIdent(c.graph.cache, paramName), nextSymId(c.idgen), fn, fn.info)
415    incl(cp.flags, sfFromGeneric)
416    cp.typ = t
417    addHiddenParam(fn, cp)
418  elif cp.typ != t and fn.kind != skIterator:
419    localError(c.graph.config, fn.info, "internal error: inconsistent environment type")
420  #echo "adding closure to ", fn.name.s
421
422proc detectCapturedVars(n: PNode; owner: PSym; c: var DetectionPass) =
423  case n.kind
424  of nkSym:
425    let s = n.sym
426    if s.kind in {skProc, skFunc, skMethod, skConverter, skIterator} and
427        s.typ != nil and s.typ.callConv == ccClosure:
428      # this handles the case that the inner proc was declared as
429      # .closure but does not actually capture anything:
430      addClosureParam(c, s, n.info)
431      c.somethingToDo = true
432
433    let innerProc = isInnerProc(s)
434    if innerProc:
435      if s.isIterator: c.somethingToDo = true
436      if not c.processed.containsOrIncl(s.id):
437        let body = transformBody(c.graph, c.idgen, s, cache = true)
438        detectCapturedVars(body, s, c)
439    let ow = s.skipGenericOwner
440    if ow == owner:
441      if owner.isIterator:
442        c.somethingToDo = true
443        addClosureParam(c, owner, n.info)
444        if interestingIterVar(s):
445          if not c.capturedVars.containsOrIncl(s.id):
446            let obj = getHiddenParam(c.graph, owner).typ.skipTypes({tyOwned, tyRef, tyPtr})
447            #let obj = c.getEnvTypeForOwner(s.owner).skipTypes({tyOwned, tyRef, tyPtr})
448
449            if s.name.id == getIdent(c.graph.cache, ":state").id:
450              obj.n[0].sym.itemId = ItemId(module: s.itemId.module, item: -s.itemId.item)
451            else:
452              addField(obj, s, c.graph.cache, c.idgen)
453    # direct or indirect dependency:
454    elif (innerProc and s.typ.callConv == ccClosure) or interestingVar(s):
455      discard """
456        proc outer() =
457          var x: int
458          proc inner() =
459            proc innerInner() =
460              echo x
461            innerInner()
462          inner()
463        # inner() takes a closure too!
464      """
465      # mark 'owner' as taking a closure:
466      c.somethingToDo = true
467      markAsClosure(c.graph, owner, n)
468      addClosureParam(c, owner, n.info)
469      #echo "capturing ", n.info
470      # variable 's' is actually captured:
471      if interestingVar(s) and not c.capturedVars.containsOrIncl(s.id):
472        let obj = c.getEnvTypeForOwner(ow, n.info).skipTypes({tyOwned, tyRef, tyPtr})
473        #getHiddenParam(owner).typ.skipTypes({tyOwned, tyRef, tyPtr})
474        addField(obj, s, c.graph.cache, c.idgen)
475      # create required upFields:
476      var w = owner.skipGenericOwner
477      if isInnerProc(w) or owner.isIterator:
478        if owner.isIterator: w = owner
479        let last = if ow.isIterator: ow.skipGenericOwner else: ow
480        while w != nil and w.kind != skModule and last != w:
481          discard """
482          proc outer =
483            var a, b: int
484            proc outerB =
485              proc innerA = use(a)
486              proc innerB = use(b); innerA()
487          # --> make outerB of calling convention .closure and
488          # give it the same env type that outer's env var gets:
489          """
490          let up = w.skipGenericOwner
491          #echo "up for ", w.name.s, " up ", up.name.s
492          markAsClosure(c.graph, w, n)
493          addClosureParam(c, w, n.info) # , ow
494          createUpField(c, w, up, n.info)
495          w = up
496  of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit,
497     nkTemplateDef, nkTypeSection, nkProcDef, nkMethodDef,
498     nkConverterDef, nkMacroDef, nkFuncDef, nkCommentStmt,
499     nkTypeOfExpr, nkMixinStmt, nkBindStmt:
500    discard
501  of nkLambdaKinds, nkIteratorDef:
502    if n.typ != nil:
503      detectCapturedVars(n[namePos], owner, c)
504  of nkReturnStmt:
505    detectCapturedVars(n[0], owner, c)
506  else:
507    for i in 0..<n.len:
508      detectCapturedVars(n[i], owner, c)
509
510type
511  LiftingPass = object
512    processed: IntSet
513    envVars: Table[int, PNode]
514    inContainer: int
515    unownedEnvVars: Table[int, PNode] # only required for --newruntime
516
517proc initLiftingPass(fn: PSym): LiftingPass =
518  result.processed = initIntSet()
519  result.processed.incl(fn.id)
520  result.envVars = initTable[int, PNode]()
521
522proc accessViaEnvParam(g: ModuleGraph; n: PNode; owner: PSym): PNode =
523  let s = n.sym
524  # Type based expression construction for simplicity:
525  let envParam = getHiddenParam(g, owner)
526  if not envParam.isNil:
527    var access = newSymNode(envParam)
528    while true:
529      let obj = access.typ[0]
530      assert obj.kind == tyObject
531      let field = getFieldFromObj(obj, s)
532      if field != nil:
533        return rawIndirectAccess(access, field, n.info)
534      let upField = lookupInRecord(obj.n, getIdent(g.cache, upName))
535      if upField == nil: break
536      access = rawIndirectAccess(access, upField, n.info)
537  localError(g.config, n.info, "internal error: environment misses: " & s.name.s)
538  result = n
539
540proc newEnvVar(cache: IdentCache; owner: PSym; typ: PType; info: TLineInfo; idgen: IdGenerator): PNode =
541  var v = newSym(skVar, getIdent(cache, envName), nextSymId(idgen), owner, info)
542  v.flags = {sfShadowed, sfGeneratedOp}
543  v.typ = typ
544  result = newSymNode(v)
545  when false:
546    if owner.kind == skIterator and owner.typ.callConv == ccClosure:
547      let it = getHiddenParam(owner)
548      addUniqueField(it.typ[0], v)
549      result = indirectAccess(newSymNode(it), v, v.info)
550    else:
551      result = newSymNode(v)
552
553proc setupEnvVar(owner: PSym; d: var DetectionPass;
554                 c: var LiftingPass; info: TLineInfo): PNode =
555  if owner.isIterator:
556    return getHiddenParam(d.graph, owner).newSymNode
557  result = c.envVars.getOrDefault(owner.id)
558  if result.isNil:
559    let envVarType = d.ownerToType.getOrDefault(owner.id)
560    if envVarType.isNil:
561      localError d.graph.config, owner.info, "internal error: could not determine closure type"
562    result = newEnvVar(d.graph.cache, owner, asOwnedRef(d, envVarType), info, d.idgen)
563    c.envVars[owner.id] = result
564    if optOwnedRefs in d.graph.config.globalOptions:
565      var v = newSym(skVar, getIdent(d.graph.cache, envName & "Alt"), nextSymId d.idgen, owner, info)
566      v.flags = {sfShadowed, sfGeneratedOp}
567      v.typ = envVarType
568      c.unownedEnvVars[owner.id] = newSymNode(v)
569
570proc getUpViaParam(g: ModuleGraph; owner: PSym): PNode =
571  let p = getHiddenParam(g, owner)
572  result = p.newSymNode
573  if owner.isIterator:
574    let upField = lookupInRecord(p.typ.skipTypes({tyOwned, tyRef, tyPtr}).n, getIdent(g.cache, upName))
575    if upField == nil:
576      localError(g.config, owner.info, "could not find up reference for closure iter")
577    else:
578      result = rawIndirectAccess(result, upField, p.info)
579
580proc rawClosureCreation(owner: PSym;
581                        d: var DetectionPass; c: var LiftingPass;
582                        info: TLineInfo): PNode =
583  result = newNodeI(nkStmtList, owner.info)
584
585  var env: PNode
586  if owner.isIterator:
587    env = getHiddenParam(d.graph, owner).newSymNode
588  else:
589    env = setupEnvVar(owner, d, c, info)
590    if env.kind == nkSym:
591      var v = newNodeI(nkVarSection, env.info)
592      addVar(v, env)
593      result.add(v)
594      if optOwnedRefs in d.graph.config.globalOptions:
595        let unowned = c.unownedEnvVars[owner.id]
596        assert unowned != nil
597        addVar(v, unowned)
598
599    # add 'new' statement:
600    result.add(newCall(getSysSym(d.graph, env.info, "internalNew"), env))
601    if optOwnedRefs in d.graph.config.globalOptions:
602      let unowned = c.unownedEnvVars[owner.id]
603      assert unowned != nil
604      let env2 = copyTree(env)
605      env2.typ = unowned.typ
606      result.add newAsgnStmt(unowned, env2, env.info)
607      createTypeBoundOpsLL(d.graph, unowned.typ, env.info, d.idgen, owner)
608
609    # add assignment statements for captured parameters:
610    for i in 1..<owner.typ.n.len:
611      let local = owner.typ.n[i].sym
612      if local.id in d.capturedVars:
613        let fieldAccess = indirectAccess(env, local, env.info)
614        # add ``env.param = param``
615        result.add(newAsgnStmt(fieldAccess, newSymNode(local), env.info))
616        if owner.kind != skMacro:
617          createTypeBoundOps(d.graph, nil, fieldAccess.typ, env.info, d.idgen)
618        if tfHasAsgn in fieldAccess.typ.flags or optSeqDestructors in d.graph.config.globalOptions:
619          owner.flags.incl sfInjectDestructors
620
621  let upField = lookupInRecord(env.typ.skipTypes({tyOwned, tyRef, tyPtr}).n, getIdent(d.graph.cache, upName))
622  if upField != nil:
623    let up = getUpViaParam(d.graph, owner)
624    if up != nil and upField.typ.skipTypes({tyOwned, tyRef, tyPtr}) == up.typ.skipTypes({tyOwned, tyRef, tyPtr}):
625      result.add(newAsgnStmt(rawIndirectAccess(env, upField, env.info),
626                 up, env.info))
627    #elif oldenv != nil and oldenv.typ == upField.typ:
628    #  result.add(newAsgnStmt(rawIndirectAccess(env, upField, env.info),
629    #             oldenv, env.info))
630    else:
631      localError(d.graph.config, env.info, "internal error: cannot create up reference")
632  # we are not in the sem'check phase anymore! so pass 'nil' for the PContext
633  # and hope for the best:
634  createTypeBoundOpsLL(d.graph, env.typ, owner.info, d.idgen, owner)
635
636proc finishClosureCreation(owner: PSym; d: var DetectionPass; c: LiftingPass;
637                           info: TLineInfo; res: PNode) =
638  if optOwnedRefs in d.graph.config.globalOptions:
639    let unowned = c.unownedEnvVars[owner.id]
640    assert unowned != nil
641    let nilLit = newNodeIT(nkNilLit, info, unowned.typ)
642    res.add newAsgnStmt(unowned, nilLit, info)
643    createTypeBoundOpsLL(d.graph, unowned.typ, info, d.idgen, owner)
644
645proc closureCreationForIter(iter: PNode;
646                            d: var DetectionPass; c: var LiftingPass): PNode =
647  result = newNodeIT(nkStmtListExpr, iter.info, iter.sym.typ)
648  let owner = iter.sym.skipGenericOwner
649  var v = newSym(skVar, getIdent(d.graph.cache, envName), nextSymId(d.idgen), owner, iter.info)
650  incl(v.flags, sfShadowed)
651  v.typ = asOwnedRef(d, getHiddenParam(d.graph, iter.sym).typ)
652  var vnode: PNode
653  if owner.isIterator:
654    let it = getHiddenParam(d.graph, owner)
655    addUniqueField(it.typ.skipTypes({tyOwned, tyRef, tyPtr}), v, d.graph.cache, d.idgen)
656    vnode = indirectAccess(newSymNode(it), v, v.info)
657  else:
658    vnode = v.newSymNode
659    var vs = newNodeI(nkVarSection, iter.info)
660    addVar(vs, vnode)
661    result.add(vs)
662  result.add(newCall(getSysSym(d.graph, iter.info, "internalNew"), vnode))
663  createTypeBoundOpsLL(d.graph, vnode.typ, iter.info, d.idgen, owner)
664
665  let upField = lookupInRecord(v.typ.skipTypes({tyOwned, tyRef, tyPtr}).n, getIdent(d.graph.cache, upName))
666  if upField != nil:
667    let u = setupEnvVar(owner, d, c, iter.info)
668    if u.typ.skipTypes({tyOwned, tyRef, tyPtr}) == upField.typ.skipTypes({tyOwned, tyRef, tyPtr}):
669      result.add(newAsgnStmt(rawIndirectAccess(vnode, upField, iter.info),
670                 u, iter.info))
671    else:
672      localError(d.graph.config, iter.info, "internal error: cannot create up reference for iter")
673  result.add makeClosure(d.graph, d.idgen, iter.sym, vnode, iter.info)
674
675proc accessViaEnvVar(n: PNode; owner: PSym; d: var DetectionPass;
676                     c: var LiftingPass): PNode =
677  var access = setupEnvVar(owner, d, c, n.info)
678  if optOwnedRefs in d.graph.config.globalOptions:
679    access = c.unownedEnvVars[owner.id]
680  let obj = access.typ.skipTypes({tyOwned, tyRef, tyPtr})
681  let field = getFieldFromObj(obj, n.sym)
682  if field != nil:
683    result = rawIndirectAccess(access, field, n.info)
684  else:
685    localError(d.graph.config, n.info, "internal error: not part of closure object type")
686    result = n
687
688proc getStateField*(g: ModuleGraph; owner: PSym): PSym =
689  getHiddenParam(g, owner).typ.skipTypes({tyOwned, tyRef, tyPtr}).n[0].sym
690
691proc liftCapturedVars(n: PNode; owner: PSym; d: var DetectionPass;
692                      c: var LiftingPass): PNode
693
694proc symToClosure(n: PNode; owner: PSym; d: var DetectionPass;
695                  c: var LiftingPass): PNode =
696  let s = n.sym
697  if s == owner:
698    # recursive calls go through (lambda, hiddenParam):
699    let available = getHiddenParam(d.graph, owner)
700    result = makeClosure(d.graph, d.idgen, s, available.newSymNode, n.info)
701  elif s.isIterator:
702    result = closureCreationForIter(n, d, c)
703  elif s.skipGenericOwner == owner:
704    # direct dependency, so use the outer's env variable:
705    result = makeClosure(d.graph, d.idgen, s, setupEnvVar(owner, d, c, n.info), n.info)
706  else:
707    let available = getHiddenParam(d.graph, owner)
708    let wanted = getHiddenParam(d.graph, s).typ
709    # ugh: call through some other inner proc;
710    var access = newSymNode(available)
711    while true:
712      if access.typ == wanted:
713        return makeClosure(d.graph, d.idgen, s, access, n.info)
714      let obj = access.typ.skipTypes({tyOwned, tyRef, tyPtr})
715      let upField = lookupInRecord(obj.n, getIdent(d.graph.cache, upName))
716      if upField == nil:
717        localError(d.graph.config, n.info, "internal error: no environment found")
718        return n
719      access = rawIndirectAccess(access, upField, n.info)
720
721proc liftCapturedVars(n: PNode; owner: PSym; d: var DetectionPass;
722                      c: var LiftingPass): PNode =
723  result = n
724  case n.kind
725  of nkSym:
726    let s = n.sym
727    if isInnerProc(s):
728      if not c.processed.containsOrIncl(s.id):
729        #if s.name.s == "temp":
730        #  echo renderTree(s.getBody, {renderIds})
731        let oldInContainer = c.inContainer
732        c.inContainer = 0
733        var body = transformBody(d.graph, d.idgen, s, cache = false)
734        body = liftCapturedVars(body, s, d, c)
735        if c.envVars.getOrDefault(s.id).isNil:
736          s.transformedBody = body
737        else:
738          s.transformedBody = newTree(nkStmtList, rawClosureCreation(s, d, c, n.info), body)
739          finishClosureCreation(s, d, c, n.info, s.transformedBody)
740        c.inContainer = oldInContainer
741
742      if s.typ.callConv == ccClosure:
743        result = symToClosure(n, owner, d, c)
744
745    elif s.id in d.capturedVars:
746      if s.owner != owner:
747        result = accessViaEnvParam(d.graph, n, owner)
748      elif owner.isIterator and interestingIterVar(s):
749        result = accessViaEnvParam(d.graph, n, owner)
750      else:
751        result = accessViaEnvVar(n, owner, d, c)
752  of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit, nkComesFrom,
753     nkTemplateDef, nkTypeSection, nkProcDef, nkMethodDef, nkConverterDef,
754     nkMacroDef, nkFuncDef, nkMixinStmt, nkBindStmt:
755    discard
756  of nkClosure:
757    if n[1].kind == nkNilLit:
758      n[0] = liftCapturedVars(n[0], owner, d, c)
759      let x = n[0].skipConv
760      if x.kind == nkClosure:
761        #localError(n.info, "internal error: closure to closure created")
762        # now we know better, so patch it:
763        n[0] = x[0]
764        n[1] = x[1]
765  of nkLambdaKinds, nkIteratorDef:
766    if n.typ != nil and n[namePos].kind == nkSym:
767      let oldInContainer = c.inContainer
768      c.inContainer = 0
769      let m = newSymNode(n[namePos].sym)
770      m.typ = n.typ
771      result = liftCapturedVars(m, owner, d, c)
772      c.inContainer = oldInContainer
773  of nkHiddenStdConv:
774    if n.len == 2:
775      n[1] = liftCapturedVars(n[1], owner, d, c)
776      if n[1].kind == nkClosure: result = n[1]
777  of nkReturnStmt:
778    if n[0].kind in {nkAsgn, nkFastAsgn}:
779      # we have a `result = result` expression produced by the closure
780      # transform, let's not touch the LHS in order to make the lifting pass
781      # correct when `result` is lifted
782      n[0][1] = liftCapturedVars(n[0][1], owner, d, c)
783    else:
784      n[0] = liftCapturedVars(n[0], owner, d, c)
785  of nkTypeOfExpr:
786    result = n
787  else:
788    if owner.isIterator:
789      if nfLL in n.flags:
790        # special case 'when nimVm' due to bug #3636:
791        n[1] = liftCapturedVars(n[1], owner, d, c)
792        return
793
794    let inContainer = n.kind in {nkObjConstr, nkBracket}
795    if inContainer: inc c.inContainer
796    for i in 0..<n.len:
797      n[i] = liftCapturedVars(n[i], owner, d, c)
798    if inContainer: dec c.inContainer
799
800# ------------------ old stuff -------------------------------------------
801
802proc semCaptureSym*(s, owner: PSym) =
803  discard """
804    proc outer() =
805      var x: int
806      proc inner() =
807        proc innerInner() =
808          echo x
809        innerInner()
810      inner()
811    # inner() takes a closure too!
812  """
813  proc propagateClosure(start, last: PSym) =
814    var o = start
815    while o != nil and o.kind != skModule:
816      if o == last: break
817      o.typ.callConv = ccClosure
818      o = o.skipGenericOwner
819
820  if interestingVar(s) and s.kind != skResult:
821    if owner.typ != nil and not isGenericRoutine(owner):
822      # XXX: is this really safe?
823      # if we capture a var from another generic routine,
824      # it won't be consider captured.
825      var o = owner.skipGenericOwner
826      while o != nil and o.kind != skModule:
827        if s.owner == o:
828          if owner.typ.callConv == ccClosure or owner.kind == skIterator or
829             owner.typ.callConv == ccNimCall and tfExplicitCallConv notin owner.typ.flags:
830            owner.typ.callConv = ccClosure
831            propagateClosure(owner.skipGenericOwner, s.owner)
832          else:
833            discard "do not produce an error here, but later"
834          #echo "computing .closure for ", owner.name.s, " because of ", s.name.s
835        o = o.skipGenericOwner
836    # since the analysis is not entirely correct, we don't set 'tfCapturesEnv'
837    # here
838
839proc liftIterToProc*(g: ModuleGraph; fn: PSym; body: PNode; ptrType: PType;
840                     idgen: IdGenerator): PNode =
841  var d = initDetectionPass(g, fn, idgen)
842  var c = initLiftingPass(fn)
843  # pretend 'fn' is a closure iterator for the analysis:
844  let oldKind = fn.kind
845  let oldCC = fn.typ.callConv
846  fn.transitionRoutineSymKind(skIterator)
847  fn.typ.callConv = ccClosure
848  d.ownerToType[fn.id] = ptrType
849  detectCapturedVars(body, fn, d)
850  result = liftCapturedVars(body, fn, d, c)
851  fn.transitionRoutineSymKind(oldKind)
852  fn.typ.callConv = oldCC
853
854proc liftLambdas*(g: ModuleGraph; fn: PSym, body: PNode; tooEarly: var bool;
855                  idgen: IdGenerator): PNode =
856  # XXX backend == backendJs does not suffice! The compiletime stuff needs
857  # the transformation even when compiling to JS ...
858
859  # However we can do lifting for the stuff which is *only* compiletime.
860  let isCompileTime = sfCompileTime in fn.flags or fn.kind == skMacro
861
862  if body.kind == nkEmpty or (
863      g.config.backend == backendJs and not isCompileTime) or
864      fn.skipGenericOwner.kind != skModule:
865
866    # ignore forward declaration:
867    result = body
868    tooEarly = true
869  else:
870    var d = initDetectionPass(g, fn, idgen)
871    detectCapturedVars(body, fn, d)
872    if not d.somethingToDo and fn.isIterator:
873      addClosureParam(d, fn, body.info)
874      d.somethingToDo = true
875    if d.somethingToDo:
876      var c = initLiftingPass(fn)
877      result = liftCapturedVars(body, fn, d, c)
878      # echo renderTree(result, {renderIds})
879      if c.envVars.getOrDefault(fn.id) != nil:
880        result = newTree(nkStmtList, rawClosureCreation(fn, d, c, body.info), result)
881        finishClosureCreation(fn, d, c, body.info, result)
882    else:
883      result = body
884    #if fn.name.s == "get2":
885    #  echo "had something to do ", d.somethingToDo
886    #  echo renderTree(result, {renderIds})
887
888proc liftLambdasForTopLevel*(module: PSym, body: PNode): PNode =
889  # XXX implement it properly
890  result = body
891
892# ------------------- iterator transformation --------------------------------
893
894proc liftForLoop*(g: ModuleGraph; body: PNode; idgen: IdGenerator; owner: PSym): PNode =
895  # problem ahead: the iterator could be invoked indirectly, but then
896  # we don't know what environment to create here:
897  #
898  # iterator count(): int =
899  #   yield 0
900  #
901  # iterator count2(): int =
902  #   var x = 3
903  #   yield x
904  #   inc x
905  #   yield x
906  #
907  # proc invoke(iter: iterator(): int) =
908  #   for x in iter(): echo x
909  #
910  # --> When to create the closure? --> for the (count) occurrence!
911  discard """
912      for i in foo(): ...
913
914    Is transformed to:
915
916      cl = createClosure()
917      while true:
918        let i = foo(cl)
919        if (nkBreakState(cl.state)):
920          break
921        ...
922    """
923  if liftingHarmful(g.config, owner): return body
924  if not (body.kind == nkForStmt and body[^2].kind in nkCallKinds):
925    localError(g.config, body.info, "ignored invalid for loop")
926    return body
927  var call = body[^2]
928
929  result = newNodeI(nkStmtList, body.info)
930
931  # static binding?
932  var env: PSym
933  let op = call[0]
934  if op.kind == nkSym and op.sym.isIterator:
935    # createClosure()
936    let iter = op.sym
937
938    let hp = getHiddenParam(g, iter)
939    env = newSym(skLet, iter.name, nextSymId(idgen), owner, body.info)
940    env.typ = hp.typ
941    env.flags = hp.flags
942
943    var v = newNodeI(nkVarSection, body.info)
944    addVar(v, newSymNode(env))
945    result.add(v)
946    # add 'new' statement:
947    result.add(newCall(getSysSym(g, env.info, "internalNew"), env.newSymNode))
948    createTypeBoundOpsLL(g, env.typ, body.info, idgen, owner)
949
950  elif op.kind == nkStmtListExpr:
951    let closure = op.lastSon
952    if closure.kind == nkClosure:
953      call[0] = closure
954      for i in 0..<op.len-1:
955        result.add op[i]
956
957  var loopBody = newNodeI(nkStmtList, body.info, 3)
958  var whileLoop = newNodeI(nkWhileStmt, body.info, 2)
959  whileLoop[0] = newIntTypeNode(1, getSysType(g, body.info, tyBool))
960  whileLoop[1] = loopBody
961  result.add whileLoop
962
963  # setup loopBody:
964  # gather vars in a tuple:
965  var v2 = newNodeI(nkLetSection, body.info)
966  var vpart = newNodeI(if body.len == 3: nkIdentDefs else: nkVarTuple, body.info)
967  for i in 0..<body.len-2:
968    if body[i].kind == nkSym:
969      body[i].sym.transitionToLet()
970    vpart.add body[i]
971
972  vpart.add newNodeI(nkEmpty, body.info) # no explicit type
973  if not env.isNil:
974    call[0] = makeClosure(g, idgen, call[0].sym, env.newSymNode, body.info)
975  vpart.add call
976  v2.add vpart
977
978  loopBody[0] = v2
979  var bs = newNodeI(nkBreakState, body.info)
980  bs.add call[0]
981
982  let ibs = newNodeI(nkIfStmt, body.info)
983  let elifBranch = newNodeI(nkElifBranch, body.info)
984  elifBranch.add(bs)
985
986  let br = newNodeI(nkBreakStmt, body.info)
987  br.add(g.emptyNode)
988
989  elifBranch.add(br)
990  ibs.add(elifBranch)
991
992  loopBody[1] = ibs
993  loopBody[2] = body[^1]
994