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