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