lambdalifting.nim 36 KB

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