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 module implements the transformator. It transforms the syntax tree
11# to ease the work of the code generators. Does some transformations:
12#
13# * inlines iterators
14# * inlines constants
15# * performs constant folding
16# * converts "continue" to "break"; disambiguates "break"
17# * introduces method dispatchers
18# * performs lambda lifting for closure support
19# * transforms 'defer' into a 'try finally' statement
20
21import
22  options, ast, astalgo, trees, msgs,
23  idents, renderer, types, semfold, magicsys, cgmeth,
24  lowerings, liftlocals,
25  modulegraphs, lineinfos
26
27proc transformBody*(g: ModuleGraph; idgen: IdGenerator, prc: PSym, cache: bool): PNode
28
29import closureiters, lambdalifting
30
31type
32  PTransCon = ref object # part of TContext; stackable
33    mapping: TIdNodeTable     # mapping from symbols to nodes
34    owner: PSym               # current owner
35    forStmt: PNode            # current for stmt
36    forLoopBody: PNode   # transformed for loop body
37    yieldStmts: int           # we count the number of yield statements,
38                              # because we need to introduce new variables
39                              # if we encounter the 2nd yield statement
40    next: PTransCon           # for stacking
41
42  PTransf = ref object
43    module: PSym
44    transCon: PTransCon      # top of a TransCon stack
45    inlining: int            # > 0 if we are in inlining context (copy vars)
46    nestedProcs: int         # > 0 if we are in a nested proc
47    contSyms, breakSyms: seq[PSym]  # to transform 'continue' and 'break'
48    deferDetected, tooEarly: bool
49    graph: ModuleGraph
50    idgen: IdGenerator
51
52proc newTransNode(a: PNode): PNode {.inline.} =
53  result = shallowCopy(a)
54
55proc newTransNode(kind: TNodeKind, info: TLineInfo,
56                  sons: int): PNode {.inline.} =
57  var x = newNodeI(kind, info)
58  newSeq(x.sons, sons)
59  result = x
60
61proc newTransNode(kind: TNodeKind, n: PNode,
62                  sons: int): PNode {.inline.} =
63  var x = newNodeIT(kind, n.info, n.typ)
64  newSeq(x.sons, sons)
65  x.typ = n.typ
66#  x.flags = n.flags
67  result = x
68
69proc newTransCon(owner: PSym): PTransCon =
70  assert owner != nil
71  new(result)
72  initIdNodeTable(result.mapping)
73  result.owner = owner
74
75proc pushTransCon(c: PTransf, t: PTransCon) =
76  t.next = c.transCon
77  c.transCon = t
78
79proc popTransCon(c: PTransf) =
80  if (c.transCon == nil): internalError(c.graph.config, "popTransCon")
81  c.transCon = c.transCon.next
82
83proc getCurrOwner(c: PTransf): PSym =
84  if c.transCon != nil: result = c.transCon.owner
85  else: result = c.module
86
87proc newTemp(c: PTransf, typ: PType, info: TLineInfo): PNode =
88  let r = newSym(skTemp, getIdent(c.graph.cache, genPrefix), nextSymId(c.idgen), getCurrOwner(c), info)
89  r.typ = typ #skipTypes(typ, {tyGenericInst, tyAlias, tySink})
90  incl(r.flags, sfFromGeneric)
91  let owner = getCurrOwner(c)
92  if owner.isIterator and not c.tooEarly:
93    result = freshVarForClosureIter(c.graph, r, c.idgen, owner)
94  else:
95    result = newSymNode(r)
96
97proc transform(c: PTransf, n: PNode): PNode
98
99proc transformSons(c: PTransf, n: PNode): PNode =
100  result = newTransNode(n)
101  for i in 0..<n.len:
102    result[i] = transform(c, n[i])
103
104proc newAsgnStmt(c: PTransf, kind: TNodeKind, le: PNode, ri: PNode): PNode =
105  result = newTransNode(kind, ri.info, 2)
106  result[0] = le
107  result[1] = ri
108
109proc transformSymAux(c: PTransf, n: PNode): PNode =
110  let s = n.sym
111  if s.typ != nil and s.typ.callConv == ccClosure:
112    if s.kind in routineKinds:
113      discard transformBody(c.graph, c.idgen, s, true)
114    if s.kind == skIterator:
115      if c.tooEarly: return n
116      else: return liftIterSym(c.graph, n, c.idgen, getCurrOwner(c))
117    elif s.kind in {skProc, skFunc, skConverter, skMethod} and not c.tooEarly:
118      # top level .closure procs are still somewhat supported for 'Nake':
119      return makeClosure(c.graph, c.idgen, s, nil, n.info)
120  #elif n.sym.kind in {skVar, skLet} and n.sym.typ.callConv == ccClosure:
121  #  echo n.info, " come heer for ", c.tooEarly
122  #  if not c.tooEarly:
123  var b: PNode
124  var tc = c.transCon
125  if sfBorrow in s.flags and s.kind in routineKinds:
126    # simply exchange the symbol:
127    b = getBody(c.graph, s)
128    if b.kind != nkSym: internalError(c.graph.config, n.info, "wrong AST for borrowed symbol")
129    b = newSymNode(b.sym, n.info)
130  elif c.inlining > 0:
131    # see bug #13596: we use ref-based equality in the DFA for destruction
132    # injections so we need to ensure unique nodes after iterator inlining
133    # which can lead to duplicated for loop bodies! Consider:
134    #[
135      while remaining > 0:
136        if ending == nil:
137          yield ms
138          break
139        ...
140        yield ms
141    ]#
142    b = newSymNode(n.sym, n.info)
143  else:
144    b = n
145  while tc != nil:
146    result = idNodeTableGet(tc.mapping, b.sym)
147    if result != nil:
148      # this slightly convoluted way ensures the line info stays correct:
149      if result.kind == nkSym:
150        result = copyNode(result)
151        result.info = n.info
152      return
153    tc = tc.next
154  result = b
155
156proc transformSym(c: PTransf, n: PNode): PNode =
157  result = transformSymAux(c, n)
158
159proc freshVar(c: PTransf; v: PSym): PNode =
160  let owner = getCurrOwner(c)
161  if owner.isIterator and not c.tooEarly:
162    result = freshVarForClosureIter(c.graph, v, c.idgen, owner)
163  else:
164    var newVar = copySym(v, nextSymId(c.idgen))
165    incl(newVar.flags, sfFromGeneric)
166    newVar.owner = owner
167    result = newSymNode(newVar)
168
169proc transformVarSection(c: PTransf, v: PNode): PNode =
170  result = newTransNode(v)
171  for i in 0..<v.len:
172    var it = v[i]
173    if it.kind == nkCommentStmt:
174      result[i] = it
175    elif it.kind == nkIdentDefs:
176      if it[0].kind == nkSym:
177        internalAssert(c.graph.config, it.len == 3)
178        let x = freshVar(c, it[0].sym)
179        idNodeTablePut(c.transCon.mapping, it[0].sym, x)
180        var defs = newTransNode(nkIdentDefs, it.info, 3)
181        if importantComments(c.graph.config):
182          # keep documentation information:
183          defs.comment = it.comment
184        defs[0] = x
185        defs[1] = it[1]
186        defs[2] = transform(c, it[2])
187        if x.kind == nkSym: x.sym.ast = defs[2]
188        result[i] = defs
189      else:
190        # has been transformed into 'param.x' for closure iterators, so just
191        # transform it:
192        result[i] = transform(c, it)
193    else:
194      if it.kind != nkVarTuple:
195        internalError(c.graph.config, it.info, "transformVarSection: not nkVarTuple")
196      var defs = newTransNode(it.kind, it.info, it.len)
197      for j in 0..<it.len-2:
198        if it[j].kind == nkSym:
199          let x = freshVar(c, it[j].sym)
200          idNodeTablePut(c.transCon.mapping, it[j].sym, x)
201          defs[j] = x
202        else:
203          defs[j] = transform(c, it[j])
204      assert(it[^2].kind == nkEmpty)
205      defs[^2] = newNodeI(nkEmpty, it.info)
206      defs[^1] = transform(c, it[^1])
207      result[i] = defs
208
209proc transformConstSection(c: PTransf, v: PNode): PNode =
210  result = v
211  when false:
212    result = newTransNode(v)
213    for i in 0..<v.len:
214      var it = v[i]
215      if it.kind == nkCommentStmt:
216        result[i] = it
217      else:
218        if it.kind != nkConstDef: internalError(c.graph.config, it.info, "transformConstSection")
219        if it[0].kind != nkSym:
220          debug it[0]
221          internalError(c.graph.config, it.info, "transformConstSection")
222
223        result[i] = it
224
225proc hasContinue(n: PNode): bool =
226  case n.kind
227  of nkEmpty..nkNilLit, nkForStmt, nkParForStmt, nkWhileStmt: discard
228  of nkContinueStmt: result = true
229  else:
230    for i in 0..<n.len:
231      if hasContinue(n[i]): return true
232
233proc newLabel(c: PTransf, n: PNode): PSym =
234  result = newSym(skLabel, nil, nextSymId(c.idgen), getCurrOwner(c), n.info)
235  result.name = getIdent(c.graph.cache, genPrefix)
236
237proc transformBlock(c: PTransf, n: PNode): PNode =
238  var labl: PSym
239  if c.inlining > 0:
240    labl = newLabel(c, n[0])
241    idNodeTablePut(c.transCon.mapping, n[0].sym, newSymNode(labl))
242  else:
243    labl =
244      if n[0].kind != nkEmpty:
245        n[0].sym  # already named block? -> Push symbol on the stack
246      else:
247        newLabel(c, n)
248  c.breakSyms.add(labl)
249  result = transformSons(c, n)
250  discard c.breakSyms.pop
251  result[0] = newSymNode(labl)
252
253proc transformLoopBody(c: PTransf, n: PNode): PNode =
254  # What if it contains "continue" and "break"? "break" needs
255  # an explicit label too, but not the same!
256
257  # We fix this here by making every 'break' belong to its enclosing loop
258  # and changing all breaks that belong to a 'block' by annotating it with
259  # a label (if it hasn't one already).
260  if hasContinue(n):
261    let labl = newLabel(c, n)
262    c.contSyms.add(labl)
263
264    result = newTransNode(nkBlockStmt, n.info, 2)
265    result[0] = newSymNode(labl)
266    result[1] = transform(c, n)
267    discard c.contSyms.pop()
268  else:
269    result = transform(c, n)
270
271proc transformWhile(c: PTransf; n: PNode): PNode =
272  if c.inlining > 0:
273    result = transformSons(c, n)
274  else:
275    let labl = newLabel(c, n)
276    c.breakSyms.add(labl)
277    result = newTransNode(nkBlockStmt, n.info, 2)
278    result[0] = newSymNode(labl)
279
280    var body = newTransNode(n)
281    for i in 0..<n.len-1:
282      body[i] = transform(c, n[i])
283    body[^1] = transformLoopBody(c, n[^1])
284    result[1] = body
285    discard c.breakSyms.pop
286
287proc transformBreak(c: PTransf, n: PNode): PNode =
288  result = transformSons(c, n)
289  if n[0].kind == nkEmpty and c.breakSyms.len > 0:
290    let labl = c.breakSyms[c.breakSyms.high]
291    result[0] = newSymNode(labl)
292
293proc introduceNewLocalVars(c: PTransf, n: PNode): PNode =
294  case n.kind
295  of nkSym:
296    result = transformSym(c, n)
297  of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit:
298    # nothing to be done for leaves:
299    result = n
300  of nkVarSection, nkLetSection:
301    result = transformVarSection(c, n)
302  of nkClosure:
303    # it can happen that for-loop-inlining produced a fresh
304    # set of variables, including some computed environment
305    # (bug #2604). We need to patch this environment here too:
306    let a = n[1]
307    if a.kind == nkSym:
308      n[1] = transformSymAux(c, a)
309    return n
310  else:
311    result = newTransNode(n)
312    for i in 0..<n.len:
313      result[i] = introduceNewLocalVars(c, n[i])
314
315proc transformAsgn(c: PTransf, n: PNode): PNode =
316  let rhs = n[1]
317
318  if rhs.kind != nkTupleConstr:
319    return transformSons(c, n)
320
321  # Unpack the tuple assignment into N temporary variables and then pack them
322  # into a tuple: this allows us to get the correct results even when the rhs
323  # depends on the value of the lhs
324  let letSection = newTransNode(nkLetSection, n.info, rhs.len)
325  let newTupleConstr = newTransNode(nkTupleConstr, n.info, rhs.len)
326  for i, field in rhs:
327    let val = if field.kind == nkExprColonExpr: field[1] else: field
328    let def = newTransNode(nkIdentDefs, field.info, 3)
329    def[0] = newTemp(c, val.typ, field.info)
330    def[1] = newNodeI(nkEmpty, field.info)
331    def[2] = transform(c, val)
332    letSection[i] = def
333    # NOTE: We assume the constructor fields are in the correct order for the
334    # given tuple type
335    newTupleConstr[i] = def[0]
336
337  newTupleConstr.typ = rhs.typ
338
339  let asgnNode = newTransNode(nkAsgn, n.info, 2)
340  asgnNode[0] = transform(c, n[0])
341  asgnNode[1] = newTupleConstr
342
343  result = newTransNode(nkStmtList, n.info, 2)
344  result[0] = letSection
345  result[1] = asgnNode
346
347proc transformYield(c: PTransf, n: PNode): PNode =
348  proc asgnTo(lhs: PNode, rhs: PNode): PNode =
349    # Choose the right assignment instruction according to the given ``lhs``
350    # node since it may not be a nkSym (a stack-allocated skForVar) but a
351    # nkDotExpr (a heap-allocated slot into the envP block)
352    case lhs.kind
353    of nkSym:
354      internalAssert c.graph.config, lhs.sym.kind == skForVar
355      result = newAsgnStmt(c, nkFastAsgn, lhs, rhs)
356    of nkDotExpr:
357      result = newAsgnStmt(c, nkAsgn, lhs, rhs)
358    else:
359      internalAssert c.graph.config, false
360  result = newTransNode(nkStmtList, n.info, 0)
361  var e = n[0]
362  # c.transCon.forStmt.len == 3 means that there is one for loop variable
363  # and thus no tuple unpacking:
364  if e.typ.isNil: return result # can happen in nimsuggest for unknown reasons
365  if c.transCon.forStmt.len != 3:
366    e = skipConv(e)
367    if e.kind == nkTupleConstr:
368      for i in 0..<e.len:
369        var v = e[i]
370        if v.kind == nkExprColonExpr: v = v[1]
371        if c.transCon.forStmt[i].kind == nkVarTuple:
372          for j in 0..<c.transCon.forStmt[i].len-1:
373            let lhs = c.transCon.forStmt[i][j]
374            let rhs = transform(c, newTupleAccess(c.graph, v, j))
375            result.add(asgnTo(lhs, rhs))
376        else:
377          let lhs = c.transCon.forStmt[i]
378          let rhs = transform(c, v)
379          result.add(asgnTo(lhs, rhs))
380    elif e.kind notin {nkAddr, nkHiddenAddr}: # no need to generate temp for address operation
381      # TODO do not use temp for nodes which cannot have side-effects
382      var tmp = newTemp(c, e.typ, e.info)
383      let v = newNodeI(nkVarSection, e.info)
384      v.addVar(tmp, e)
385
386      result.add transform(c, v)
387
388      for i in 0..<c.transCon.forStmt.len - 2:
389        let lhs = c.transCon.forStmt[i]
390        let rhs = transform(c, newTupleAccess(c.graph, tmp, i))
391        result.add(asgnTo(lhs, rhs))
392    else:
393      for i in 0..<c.transCon.forStmt.len - 2:
394        let lhs = c.transCon.forStmt[i]
395        let rhs = transform(c, newTupleAccess(c.graph, e, i))
396        result.add(asgnTo(lhs, rhs))
397  else:
398    if c.transCon.forStmt[0].kind == nkVarTuple:
399      var notLiteralTuple = false # we don't generate temp for tuples with const value: (1, 2, 3)
400      let ev = e.skipConv
401      if ev.kind == nkTupleConstr:
402        for i in ev:
403          if not isConstExpr(i):
404            notLiteralTuple = true
405            break
406      else:
407        notLiteralTuple = true
408
409      if e.kind notin {nkAddr, nkHiddenAddr} and notLiteralTuple:
410        # TODO do not use temp for nodes which cannot have side-effects
411        var tmp = newTemp(c, e.typ, e.info)
412        let v = newNodeI(nkVarSection, e.info)
413        v.addVar(tmp, e)
414
415        result.add transform(c, v)
416        for i in 0..<c.transCon.forStmt[0].len-1:
417          let lhs = c.transCon.forStmt[0][i]
418          let rhs = transform(c, newTupleAccess(c.graph, tmp, i))
419          result.add(asgnTo(lhs, rhs))
420      else:
421        for i in 0..<c.transCon.forStmt[0].len-1:
422          let lhs = c.transCon.forStmt[0][i]
423          let rhs = transform(c, newTupleAccess(c.graph, e, i))
424          result.add(asgnTo(lhs, rhs))
425    else:
426      let lhs = c.transCon.forStmt[0]
427      let rhs = transform(c, e)
428      result.add(asgnTo(lhs, rhs))
429
430  inc(c.transCon.yieldStmts)
431  if c.transCon.yieldStmts <= 1:
432    # common case
433    result.add(c.transCon.forLoopBody)
434  else:
435    # we need to introduce new local variables:
436    result.add(introduceNewLocalVars(c, c.transCon.forLoopBody))
437
438  for idx in 0 ..< result.len:
439    var changeNode = result[idx]
440    changeNode.info = c.transCon.forStmt.info
441    for i, child in changeNode:
442      child.info = changeNode.info
443
444proc transformAddrDeref(c: PTransf, n: PNode, a, b: TNodeKind): PNode =
445  result = transformSons(c, n)
446  if c.graph.config.backend == backendCpp or sfCompileToCpp in c.module.flags: return
447  var n = result
448  case n[0].kind
449  of nkObjUpConv, nkObjDownConv, nkChckRange, nkChckRangeF, nkChckRange64:
450    var m = n[0][0]
451    if m.kind == a or m.kind == b:
452      # addr ( nkConv ( deref ( x ) ) ) --> nkConv(x)
453      n[0][0] = m[0]
454      result = n[0]
455      if n.typ.skipTypes(abstractVar).kind != tyOpenArray:
456        result.typ = n.typ
457      elif n.typ.skipTypes(abstractInst).kind in {tyVar}:
458        result.typ = toVar(result.typ, n.typ.skipTypes(abstractInst).kind, c.idgen)
459  of nkHiddenStdConv, nkHiddenSubConv, nkConv:
460    var m = n[0][1]
461    if m.kind == a or m.kind == b:
462      # addr ( nkConv ( deref ( x ) ) ) --> nkConv(x)
463      n[0][1] = m[0]
464      result = n[0]
465      if n.typ.skipTypes(abstractVar).kind != tyOpenArray:
466        result.typ = n.typ
467      elif n.typ.skipTypes(abstractInst).kind in {tyVar}:
468        result.typ = toVar(result.typ, n.typ.skipTypes(abstractInst).kind, c.idgen)
469  else:
470    if n[0].kind == a or n[0].kind == b:
471      # addr ( deref ( x )) --> x
472      result = n[0][0]
473      if n.typ.skipTypes(abstractVar).kind != tyOpenArray:
474        result.typ = n.typ
475
476proc generateThunk(c: PTransf; prc: PNode, dest: PType): PNode =
477  ## Converts 'prc' into '(thunk, nil)' so that it's compatible with
478  ## a closure.
479
480  # we cannot generate a proper thunk here for GC-safety reasons
481  # (see internal documentation):
482  if c.graph.config.backend == backendJs: return prc
483  result = newNodeIT(nkClosure, prc.info, dest)
484  var conv = newNodeIT(nkHiddenSubConv, prc.info, dest)
485  conv.add(newNodeI(nkEmpty, prc.info))
486  conv.add(prc)
487  if prc.kind == nkClosure:
488    internalError(c.graph.config, prc.info, "closure to closure created")
489  result.add(conv)
490  result.add(newNodeIT(nkNilLit, prc.info, getSysType(c.graph, prc.info, tyNil)))
491
492proc transformConv(c: PTransf, n: PNode): PNode =
493  # numeric types need range checks:
494  var dest = skipTypes(n.typ, abstractVarRange)
495  var source = skipTypes(n[1].typ, abstractVarRange)
496  case dest.kind
497  of tyInt..tyInt64, tyEnum, tyChar, tyUInt8..tyUInt32:
498    # we don't include uint and uint64 here as these are no ordinal types ;-)
499    if not isOrdinalType(source):
500      # float -> int conversions. ugh.
501      result = transformSons(c, n)
502    elif firstOrd(c.graph.config, n.typ) <= firstOrd(c.graph.config, n[1].typ) and
503        lastOrd(c.graph.config, n[1].typ) <= lastOrd(c.graph.config, n.typ):
504      # BUGFIX: simply leave n as it is; we need a nkConv node,
505      # but no range check:
506      result = transformSons(c, n)
507    else:
508      # generate a range check:
509      if dest.kind == tyInt64 or source.kind == tyInt64:
510        result = newTransNode(nkChckRange64, n, 3)
511      else:
512        result = newTransNode(nkChckRange, n, 3)
513      dest = skipTypes(n.typ, abstractVar)
514      result[0] = transform(c, n[1])
515      result[1] = newIntTypeNode(firstOrd(c.graph.config, dest), dest)
516      result[2] = newIntTypeNode(lastOrd(c.graph.config, dest), dest)
517  of tyFloat..tyFloat128:
518    # XXX int64 -> float conversion?
519    if skipTypes(n.typ, abstractVar).kind == tyRange:
520      result = newTransNode(nkChckRangeF, n, 3)
521      dest = skipTypes(n.typ, abstractVar)
522      result[0] = transform(c, n[1])
523      result[1] = copyTree(dest.n[0])
524      result[2] = copyTree(dest.n[1])
525    else:
526      result = transformSons(c, n)
527  of tyOpenArray, tyVarargs:
528    result = transform(c, n[1])
529    #result = transformSons(c, n)
530    result.typ = takeType(n.typ, n[1].typ, c.graph, c.idgen)
531    #echo n.info, " came here and produced ", typeToString(result.typ),
532    #   " from ", typeToString(n.typ), " and ", typeToString(n[1].typ)
533  of tyCstring:
534    if source.kind == tyString:
535      result = newTransNode(nkStringToCString, n, 1)
536      result[0] = transform(c, n[1])
537    else:
538      result = transformSons(c, n)
539  of tyString:
540    if source.kind == tyCstring:
541      result = newTransNode(nkCStringToString, n, 1)
542      result[0] = transform(c, n[1])
543    else:
544      result = transformSons(c, n)
545  of tyRef, tyPtr:
546    dest = skipTypes(dest, abstractPtrs)
547    source = skipTypes(source, abstractPtrs)
548    if source.kind == tyObject:
549      var diff = inheritanceDiff(dest, source)
550      if diff < 0:
551        result = newTransNode(nkObjUpConv, n, 1)
552        result[0] = transform(c, n[1])
553      elif diff > 0 and diff != high(int):
554        result = newTransNode(nkObjDownConv, n, 1)
555        result[0] = transform(c, n[1])
556      else:
557        result = transform(c, n[1])
558        result.typ = n.typ
559    else:
560      result = transformSons(c, n)
561  of tyObject:
562    var diff = inheritanceDiff(dest, source)
563    if diff < 0:
564      result = newTransNode(nkObjUpConv, n, 1)
565      result[0] = transform(c, n[1])
566    elif diff > 0 and diff != high(int):
567      result = newTransNode(nkObjDownConv, n, 1)
568      result[0] = transform(c, n[1])
569    else:
570      result = transform(c, n[1])
571      result.typ = n.typ
572  of tyGenericParam, tyOrdinal:
573    result = transform(c, n[1])
574    # happens sometimes for generated assignments, etc.
575  of tyProc:
576    result = transformSons(c, n)
577    if dest.callConv == ccClosure and source.callConv == ccNimCall:
578      result = generateThunk(c, result[1], dest)
579  else:
580    result = transformSons(c, n)
581
582type
583  TPutArgInto = enum
584    paDirectMapping, paFastAsgn, paFastAsgnTakeTypeFromArg
585    paVarAsgn, paComplexOpenarray
586
587proc putArgInto(arg: PNode, formal: PType): TPutArgInto =
588  # This analyses how to treat the mapping "formal <-> arg" in an
589  # inline context.
590  if formal.kind == tyTypeDesc: return paDirectMapping
591  if skipTypes(formal, abstractInst).kind in {tyOpenArray, tyVarargs}:
592    case arg.kind
593    of nkStmtListExpr:
594      return paComplexOpenarray
595    of nkBracket:
596      return paFastAsgnTakeTypeFromArg
597    else:
598      # XXX incorrect, causes #13417 when `arg` has side effects.
599      return paDirectMapping
600  case arg.kind
601  of nkEmpty..nkNilLit:
602    result = paDirectMapping
603  of nkDotExpr, nkDerefExpr, nkHiddenDeref, nkAddr, nkHiddenAddr:
604    result = putArgInto(arg[0], formal)
605  of nkCurly, nkBracket:
606    for i in 0..<arg.len:
607      if putArgInto(arg[i], formal) != paDirectMapping:
608        return paFastAsgn
609    result = paDirectMapping
610  of nkPar, nkTupleConstr, nkObjConstr:
611    for i in 0..<arg.len:
612      let a = if arg[i].kind == nkExprColonExpr: arg[i][1]
613              else: arg[0]
614      if putArgInto(a, formal) != paDirectMapping:
615        return paFastAsgn
616    result = paDirectMapping
617  else:
618    if skipTypes(formal, abstractInst).kind in {tyVar, tyLent}: result = paVarAsgn
619    else: result = paFastAsgn
620
621proc findWrongOwners(c: PTransf, n: PNode) =
622  if n.kind == nkVarSection:
623    let x = n[0][0]
624    if x.kind == nkSym and x.sym.owner != getCurrOwner(c):
625      internalError(c.graph.config, x.info, "bah " & x.sym.name.s & " " &
626        x.sym.owner.name.s & " " & getCurrOwner(c).name.s)
627  else:
628    for i in 0..<n.safeLen: findWrongOwners(c, n[i])
629
630proc isSimpleIteratorVar(c: PTransf; iter: PSym): bool =
631  proc rec(n: PNode; owner: PSym; dangerousYields: var int) =
632    case n.kind
633    of nkEmpty..nkNilLit: discard
634    of nkYieldStmt:
635      if n[0].kind == nkSym and n[0].sym.owner == owner:
636        discard "good: yield a single variable that we own"
637      else:
638        inc dangerousYields
639    else:
640      for c in n: rec(c, owner, dangerousYields)
641
642  var dangerousYields = 0
643  rec(getBody(c.graph, iter), iter, dangerousYields)
644  result = dangerousYields == 0
645
646template destructor(t: PType): PSym = getAttachedOp(c.graph, t, attachedDestructor)
647
648proc transformFor(c: PTransf, n: PNode): PNode =
649  # generate access statements for the parameters (unless they are constant)
650  # put mapping from formal parameters to actual parameters
651  if n.kind != nkForStmt: internalError(c.graph.config, n.info, "transformFor")
652
653  var call = n[^2]
654
655  let labl = newLabel(c, n)
656  result = newTransNode(nkBlockStmt, n.info, 2)
657  result[0] = newSymNode(labl)
658  if call.typ.isNil:
659    # see bug #3051
660    result[1] = newNode(nkEmpty)
661    return result
662  c.breakSyms.add(labl)
663  if call.kind notin nkCallKinds or call[0].kind != nkSym or
664      call[0].typ.skipTypes(abstractInst).callConv == ccClosure:
665    result[1] = n
666    result[1][^1] = transformLoopBody(c, n[^1])
667    result[1][^2] = transform(c, n[^2])
668    result[1] = lambdalifting.liftForLoop(c.graph, result[1], c.idgen, getCurrOwner(c))
669    discard c.breakSyms.pop
670    return result
671
672  #echo "transforming: ", renderTree(n)
673  var stmtList = newTransNode(nkStmtList, n.info, 0)
674  result[1] = stmtList
675
676  var loopBody = transformLoopBody(c, n[^1])
677
678  discard c.breakSyms.pop
679
680  let iter = call[0].sym
681
682  var v = newNodeI(nkVarSection, n.info)
683  for i in 0..<n.len - 2:
684    if n[i].kind == nkVarTuple:
685      for j in 0..<n[i].len-1:
686        addVar(v, copyTree(n[i][j])) # declare new vars
687    else:
688      if n[i].kind == nkSym and isSimpleIteratorVar(c, iter):
689        incl n[i].sym.flags, sfCursor
690      addVar(v, copyTree(n[i])) # declare new vars
691  stmtList.add(v)
692
693
694  # Bugfix: inlined locals belong to the invoking routine, not to the invoked
695  # iterator!
696  var newC = newTransCon(getCurrOwner(c))
697  newC.forStmt = n
698  newC.forLoopBody = loopBody
699  # this can fail for 'nimsuggest' and 'check':
700  if iter.kind != skIterator: return result
701  # generate access statements for the parameters (unless they are constant)
702  pushTransCon(c, newC)
703  for i in 1..<call.len:
704    var arg = transform(c, call[i])
705    let ff = skipTypes(iter.typ, abstractInst)
706    # can happen for 'nim check':
707    if i >= ff.n.len: return result
708    var formal = ff.n[i].sym
709    let pa = putArgInto(arg, formal.typ)
710    case pa
711    of paDirectMapping:
712      idNodeTablePut(newC.mapping, formal, arg)
713    of paFastAsgn, paFastAsgnTakeTypeFromArg:
714      var t = formal.typ
715      if pa == paFastAsgnTakeTypeFromArg:
716        t = arg.typ
717      elif formal.ast != nil and formal.ast.typ.destructor != nil and t.destructor == nil:
718        t = formal.ast.typ # better use the type that actually has a destructor.
719      elif t.destructor == nil and arg.typ.destructor != nil:
720        t = arg.typ
721      # generate a temporary and produce an assignment statement:
722      var temp = newTemp(c, t, formal.info)
723      addVar(v, temp)
724      stmtList.add(newAsgnStmt(c, nkFastAsgn, temp, arg))
725      idNodeTablePut(newC.mapping, formal, temp)
726    of paVarAsgn:
727      assert(skipTypes(formal.typ, abstractInst).kind in {tyVar})
728      idNodeTablePut(newC.mapping, formal, arg)
729      # XXX BUG still not correct if the arg has a side effect!
730    of paComplexOpenarray:
731      # arrays will deep copy here (pretty bad).
732      var temp = newTemp(c, arg.typ, formal.info)
733      addVar(v, temp)
734      stmtList.add(newAsgnStmt(c, nkFastAsgn, temp, arg))
735      idNodeTablePut(newC.mapping, formal, temp)
736
737  let body = transformBody(c.graph, c.idgen, iter, true)
738  pushInfoContext(c.graph.config, n.info)
739  inc(c.inlining)
740  stmtList.add(transform(c, body))
741  #findWrongOwners(c, stmtList.PNode)
742  dec(c.inlining)
743  popInfoContext(c.graph.config)
744  popTransCon(c)
745  # echo "transformed: ", stmtList.renderTree
746
747proc transformCase(c: PTransf, n: PNode): PNode =
748  # removes `elif` branches of a case stmt
749  # adds ``else: nil`` if needed for the code generator
750  result = newTransNode(nkCaseStmt, n, 0)
751  var ifs: PNode = nil
752  for it in n:
753    var e = transform(c, it)
754    case it.kind
755    of nkElifBranch:
756      if ifs == nil:
757        # Generate the right node depending on whether `n` is used as a stmt or
758        # as an expr
759        let kind = if n.typ != nil: nkIfExpr else: nkIfStmt
760        ifs = newTransNode(kind, it.info, 0)
761        ifs.typ = n.typ
762      ifs.add(e)
763    of nkElse:
764      if ifs == nil: result.add(e)
765      else: ifs.add(e)
766    else:
767      result.add(e)
768  if ifs != nil:
769    var elseBranch = newTransNode(nkElse, n.info, 1)
770    elseBranch[0] = ifs
771    result.add(elseBranch)
772  elif result.lastSon.kind != nkElse and not (
773      skipTypes(n[0].typ, abstractVarRange).kind in
774        {tyInt..tyInt64, tyChar, tyEnum, tyUInt..tyUInt64}):
775    # fix a stupid code gen bug by normalizing:
776    var elseBranch = newTransNode(nkElse, n.info, 1)
777    elseBranch[0] = newTransNode(nkNilLit, n.info, 0)
778    result.add(elseBranch)
779
780proc transformArrayAccess(c: PTransf, n: PNode): PNode =
781  # XXX this is really bad; transf should use a proper AST visitor
782  if n[0].kind == nkSym and n[0].sym.kind == skType:
783    result = n
784  else:
785    result = newTransNode(n)
786    for i in 0..<n.len:
787      result[i] = transform(c, skipConv(n[i]))
788
789proc getMergeOp(n: PNode): PSym =
790  case n.kind
791  of nkCall, nkHiddenCallConv, nkCommand, nkInfix, nkPrefix, nkPostfix,
792     nkCallStrLit:
793    if n[0].kind == nkSym and n[0].sym.magic == mConStrStr:
794      result = n[0].sym
795  else: discard
796
797proc flattenTreeAux(d, a: PNode, op: PSym) =
798  let op2 = getMergeOp(a)
799  if op2 != nil and
800      (op2.id == op.id or op.magic != mNone and op2.magic == op.magic):
801    for i in 1..<a.len: flattenTreeAux(d, a[i], op)
802  else:
803    d.add copyTree(a)
804
805proc flattenTree(root: PNode): PNode =
806  let op = getMergeOp(root)
807  if op != nil:
808    result = copyNode(root)
809    result.add copyTree(root[0])
810    flattenTreeAux(result, root, op)
811  else:
812    result = root
813
814proc transformCall(c: PTransf, n: PNode): PNode =
815  var n = flattenTree(n)
816  let op = getMergeOp(n)
817  let magic = getMagic(n)
818  if op != nil and op.magic != mNone and n.len >= 3:
819    result = newTransNode(nkCall, n, 0)
820    result.add(transform(c, n[0]))
821    var j = 1
822    while j < n.len:
823      var a = transform(c, n[j])
824      inc(j)
825      if isConstExpr(a):
826        while (j < n.len):
827          let b = transform(c, n[j])
828          if not isConstExpr(b): break
829          a = evalOp(op.magic, n, a, b, nil, c.idgen, c.graph)
830          inc(j)
831      result.add(a)
832    if result.len == 2: result = result[1]
833  elif magic == mAddr:
834    result = newTransNode(nkAddr, n, 1)
835    result[0] = n[1]
836    result = transformAddrDeref(c, result, nkDerefExpr, nkHiddenDeref)
837  elif magic in {mNBindSym, mTypeOf, mRunnableExamples}:
838    # for bindSym(myconst) we MUST NOT perform constant folding:
839    result = n
840  elif magic == mProcCall:
841    # but do not change to its dispatcher:
842    result = transformSons(c, n[1])
843  elif magic == mStrToStr:
844    result = transform(c, n[1])
845  else:
846    let s = transformSons(c, n)
847    # bugfix: check after 'transformSons' if it's still a method call:
848    # use the dispatcher for the call:
849    if s[0].kind == nkSym and s[0].sym.kind == skMethod:
850      when false:
851        let t = lastSon(s[0].sym.ast)
852        if t.kind != nkSym or sfDispatcher notin t.sym.flags:
853          methodDef(s[0].sym, false)
854      result = methodCall(s, c.graph.config)
855    else:
856      result = s
857
858proc transformExceptBranch(c: PTransf, n: PNode): PNode =
859  if n[0].isInfixAs() and not isImportedException(n[0][1].typ, c.graph.config):
860    let excTypeNode = n[0][1]
861    let actions = newTransNode(nkStmtListExpr, n[1], 2)
862    # Generating `let exc = (excType)(getCurrentException())`
863    # -> getCurrentException()
864    let excCall = callCodegenProc(c.graph, "getCurrentException")
865    # -> (excType)
866    let convNode = newTransNode(nkHiddenSubConv, n[1].info, 2)
867    convNode[0] = newNodeI(nkEmpty, n.info)
868    convNode[1] = excCall
869    convNode.typ = excTypeNode.typ.toRef(c.idgen)
870    # -> let exc = ...
871    let identDefs = newTransNode(nkIdentDefs, n[1].info, 3)
872    identDefs[0] = n[0][2]
873    identDefs[1] = newNodeI(nkEmpty, n.info)
874    identDefs[2] = convNode
875
876    let letSection = newTransNode(nkLetSection, n[1].info, 1)
877    letSection[0] = identDefs
878    # Place the let statement and body of the 'except' branch into new stmtList.
879    actions[0] = letSection
880    actions[1] = transform(c, n[1])
881    # Overwrite 'except' branch body with our stmtList.
882    result = newTransNode(nkExceptBranch, n[1].info, 2)
883    # Replace the `Exception as foobar` with just `Exception`.
884    result[0] = transform(c, n[0][1])
885    result[1] = actions
886  else:
887    result = transformSons(c, n)
888
889proc commonOptimizations*(g: ModuleGraph; idgen: IdGenerator; c: PSym, n: PNode): PNode =
890  result = n
891  for i in 0..<n.safeLen:
892    result[i] = commonOptimizations(g, idgen, c, n[i])
893  var op = getMergeOp(n)
894  if (op != nil) and (op.magic != mNone) and (n.len >= 3):
895    result = newNodeIT(nkCall, n.info, n.typ)
896    result.add(n[0])
897    var args = newNode(nkArgList)
898    flattenTreeAux(args, n, op)
899    var j = 0
900    while j < args.len:
901      var a = args[j]
902      inc(j)
903      if isConstExpr(a):
904        while j < args.len:
905          let b = args[j]
906          if not isConstExpr(b): break
907          a = evalOp(op.magic, result, a, b, nil, idgen, g)
908          inc(j)
909      result.add(a)
910    if result.len == 2: result = result[1]
911  else:
912    var cnst = getConstExpr(c, n, idgen, g)
913    # we inline constants if they are not complex constants:
914    if cnst != nil and not dontInlineConstant(n, cnst):
915      result = cnst
916    else:
917      result = n
918
919proc transform(c: PTransf, n: PNode): PNode =
920  when false:
921    var oldDeferAnchor: PNode
922    if n.kind in {nkElifBranch, nkOfBranch, nkExceptBranch, nkElifExpr,
923                  nkElseExpr, nkElse, nkForStmt, nkWhileStmt, nkFinally,
924                  nkBlockStmt, nkBlockExpr}:
925      oldDeferAnchor = c.deferAnchor
926      c.deferAnchor = n
927  case n.kind
928  of nkSym:
929    result = transformSym(c, n)
930  of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit, nkComesFrom:
931    # nothing to be done for leaves:
932    result = n
933  of nkBracketExpr: result = transformArrayAccess(c, n)
934  of procDefs:
935    var s = n[namePos].sym
936    if n.typ != nil and s.typ.callConv == ccClosure:
937      result = transformSym(c, n[namePos])
938      # use the same node as before if still a symbol:
939      if result.kind == nkSym: result = n
940    else:
941      result = n
942  of nkMacroDef:
943    # XXX no proper closure support yet:
944    when false:
945      if n[genericParamsPos].kind == nkEmpty:
946        var s = n[namePos].sym
947        n[bodyPos] = transform(c, s.getBody)
948        if n.kind == nkMethodDef: methodDef(s, false)
949    result = n
950  of nkForStmt:
951    result = transformFor(c, n)
952  of nkParForStmt:
953    result = transformSons(c, n)
954  of nkCaseStmt:
955    result = transformCase(c, n)
956  of nkWhileStmt: result = transformWhile(c, n)
957  of nkBlockStmt, nkBlockExpr:
958    result = transformBlock(c, n)
959  of nkDefer:
960    c.deferDetected = true
961    result = transformSons(c, n)
962    when false:
963      let deferPart = newNodeI(nkFinally, n.info)
964      deferPart.add n[0]
965      let tryStmt = newNodeI(nkTryStmt, n.info)
966      if c.deferAnchor.isNil:
967        tryStmt.add c.root
968        c.root = tryStmt
969        result = tryStmt
970      else:
971        # modify the corresponding *action*, don't rely on nkStmtList:
972        tryStmt.add c.deferAnchor[^1]
973        c.deferAnchor[^1] = tryStmt
974        result = newTransNode(nkCommentStmt, n.info, 0)
975      tryStmt.add deferPart
976      # disable the original 'defer' statement:
977      n.kind = nkEmpty
978  of nkContinueStmt:
979    result = newNodeI(nkBreakStmt, n.info)
980    var labl = c.contSyms[c.contSyms.high]
981    result.add(newSymNode(labl))
982  of nkBreakStmt: result = transformBreak(c, n)
983  of nkCallKinds:
984    result = transformCall(c, n)
985  of nkAddr, nkHiddenAddr:
986    result = transformAddrDeref(c, n, nkDerefExpr, nkHiddenDeref)
987  of nkDerefExpr, nkHiddenDeref:
988    result = transformAddrDeref(c, n, nkAddr, nkHiddenAddr)
989  of nkHiddenStdConv, nkHiddenSubConv, nkConv:
990    result = transformConv(c, n)
991  of nkDiscardStmt:
992    result = n
993    if n[0].kind != nkEmpty:
994      result = transformSons(c, n)
995      if isConstExpr(result[0]):
996        # ensure that e.g. discard "some comment" gets optimized away
997        # completely:
998        result = newNode(nkCommentStmt)
999  of nkCommentStmt, nkTemplateDef, nkImportStmt, nkStaticStmt,
1000      nkExportStmt, nkExportExceptStmt:
1001    return n
1002  of nkConstSection:
1003    # do not replace ``const c = 3`` with ``const 3 = 3``
1004    return transformConstSection(c, n)
1005  of nkTypeSection, nkTypeOfExpr, nkMixinStmt, nkBindStmt:
1006    # no need to transform type sections:
1007    return n
1008  of nkVarSection, nkLetSection:
1009    if c.inlining > 0:
1010      # we need to copy the variables for multiple yield statements:
1011      result = transformVarSection(c, n)
1012    else:
1013      result = transformSons(c, n)
1014  of nkYieldStmt:
1015    if c.inlining > 0:
1016      result = transformYield(c, n)
1017    else:
1018      result = transformSons(c, n)
1019  of nkAsgn:
1020    result = transformAsgn(c, n)
1021  of nkIdentDefs, nkConstDef:
1022    result = newTransNode(n)
1023    result[0] = transform(c, n[0])
1024    # Skip the second son since it only contains an unsemanticized copy of the
1025    # variable type used by docgen
1026    let last = n.len-1
1027    for i in 1..<last: result[i] = n[i]
1028    result[last] = transform(c, n[last])
1029    # XXX comment handling really sucks:
1030    if importantComments(c.graph.config):
1031      result.comment = n.comment
1032  of nkClosure:
1033    # it can happen that for-loop-inlining produced a fresh
1034    # set of variables, including some computed environment
1035    # (bug #2604). We need to patch this environment here too:
1036    let a = n[1]
1037    if a.kind == nkSym:
1038      result = copyTree(n)
1039      result[1] = transformSymAux(c, a)
1040    else:
1041      result = n
1042  of nkExceptBranch:
1043    result = transformExceptBranch(c, n)
1044  of nkCheckedFieldExpr:
1045    result = transformSons(c, n)
1046    if result[0].kind != nkDotExpr:
1047      # simplfied beyond a dot expression --> simplify further.
1048      result = result[0]
1049  else:
1050    result = transformSons(c, n)
1051  when false:
1052    if oldDeferAnchor != nil: c.deferAnchor = oldDeferAnchor
1053
1054  # Constants can be inlined here, but only if they cannot result in a cast
1055  # in the back-end (e.g. var p: pointer = someProc)
1056  let exprIsPointerCast = n.kind in {nkCast, nkConv, nkHiddenStdConv} and
1057                          n.typ != nil and
1058                          n.typ.kind == tyPointer
1059  if not exprIsPointerCast:
1060    var cnst = getConstExpr(c.module, result, c.idgen, c.graph)
1061    # we inline constants if they are not complex constants:
1062    if cnst != nil and not dontInlineConstant(n, cnst):
1063      result = cnst # do not miss an optimization
1064
1065proc processTransf(c: PTransf, n: PNode, owner: PSym): PNode =
1066  # Note: For interactive mode we cannot call 'passes.skipCodegen' and skip
1067  # this step! We have to rely that the semantic pass transforms too errornous
1068  # nodes into an empty node.
1069  if nfTransf in n.flags: return n
1070  pushTransCon(c, newTransCon(owner))
1071  result = transform(c, n)
1072  popTransCon(c)
1073  incl(result.flags, nfTransf)
1074
1075proc openTransf(g: ModuleGraph; module: PSym, filename: string; idgen: IdGenerator): PTransf =
1076  new(result)
1077  result.contSyms = @[]
1078  result.breakSyms = @[]
1079  result.module = module
1080  result.graph = g
1081  result.idgen = idgen
1082
1083proc flattenStmts(n: PNode) =
1084  var goOn = true
1085  while goOn:
1086    goOn = false
1087    var i = 0
1088    while i < n.len:
1089      let it = n[i]
1090      if it.kind in {nkStmtList, nkStmtListExpr}:
1091        n.sons[i..i] = it.sons[0..<it.len]
1092        goOn = true
1093      inc i
1094
1095proc liftDeferAux(n: PNode) =
1096  if n.kind in {nkStmtList, nkStmtListExpr}:
1097    flattenStmts(n)
1098    var goOn = true
1099    while goOn:
1100      goOn = false
1101      let last = n.len-1
1102      for i in 0..last:
1103        if n[i].kind == nkDefer:
1104          let deferPart = newNodeI(nkFinally, n[i].info)
1105          deferPart.add n[i][0]
1106          var tryStmt = newNodeIT(nkTryStmt, n[i].info, n.typ)
1107          var body = newNodeIT(n.kind, n[i].info, n.typ)
1108          if i < last:
1109            body.sons = n.sons[(i+1)..last]
1110          tryStmt.add body
1111          tryStmt.add deferPart
1112          n[i] = tryStmt
1113          n.sons.setLen(i+1)
1114          n.typ = tryStmt.typ
1115          goOn = true
1116          break
1117  for i in 0..n.safeLen-1:
1118    liftDeferAux(n[i])
1119
1120template liftDefer(c, root) =
1121  if c.deferDetected:
1122    liftDeferAux(root)
1123
1124proc transformBody*(g: ModuleGraph; idgen: IdGenerator; prc: PSym; cache: bool): PNode =
1125  assert prc.kind in routineKinds
1126
1127  if prc.transformedBody != nil:
1128    result = prc.transformedBody
1129  elif nfTransf in getBody(g, prc).flags or prc.kind in {skTemplate}:
1130    result = getBody(g, prc)
1131  else:
1132    prc.transformedBody = newNode(nkEmpty) # protects from recursion
1133    var c = openTransf(g, prc.getModule, "", idgen)
1134    result = liftLambdas(g, prc, getBody(g, prc), c.tooEarly, c.idgen)
1135    result = processTransf(c, result, prc)
1136    liftDefer(c, result)
1137    result = liftLocalsIfRequested(prc, result, g.cache, g.config, c.idgen)
1138
1139    if prc.isIterator:
1140      result = g.transformClosureIterator(c.idgen, prc, result)
1141
1142    incl(result.flags, nfTransf)
1143
1144    if cache or prc.typ.callConv == ccInline:
1145      # genProc for inline procs will be called multiple times from different modules,
1146      # it is important to transform exactly once to get sym ids and locations right
1147      prc.transformedBody = result
1148    else:
1149      prc.transformedBody = nil
1150    # XXX Rodfile support for transformedBody!
1151
1152  #if prc.name.s == "main":
1153  #  echo "transformed into ", renderTree(result, {renderIds})
1154
1155proc transformStmt*(g: ModuleGraph; idgen: IdGenerator; module: PSym, n: PNode): PNode =
1156  if nfTransf in n.flags:
1157    result = n
1158  else:
1159    var c = openTransf(g, module, "", idgen)
1160    result = processTransf(c, n, module)
1161    liftDefer(c, result)
1162    #result = liftLambdasForTopLevel(module, result)
1163    incl(result.flags, nfTransf)
1164
1165proc transformExpr*(g: ModuleGraph; idgen: IdGenerator; module: PSym, n: PNode): PNode =
1166  if nfTransf in n.flags:
1167    result = n
1168  else:
1169    var c = openTransf(g, module, "", idgen)
1170    result = processTransf(c, n, module)
1171    liftDefer(c, result)
1172    # expressions are not to be injected with destructor calls as that
1173    # the list of top level statements needs to be collected before.
1174    incl(result.flags, nfTransf)
1175