diff options
Diffstat (limited to 'compiler/lambdalifting.nim')
| -rw-r--r-- | compiler/lambdalifting.nim | 834 |
1 files changed, 511 insertions, 323 deletions
diff --git a/compiler/lambdalifting.nim b/compiler/lambdalifting.nim index c5b9d0f00..6c650eee3 100644 --- a/compiler/lambdalifting.nim +++ b/compiler/lambdalifting.nim @@ -103,43 +103,51 @@ discard """ """ +# Important things to keep in mind: +# * Don't base the analysis on nkProcDef et al. This doesn't work for +# instantiated (formerly generic) procs. The analysis has to look at nkSym. +# This also means we need to prevent the same proc is processed multiple +# times via the 'processed' set. +# * Keep in mind that the owner of some temporaries used to be unreliable. +# * For closure iterators we merge the "real" potential closure with the +# local storage requirements for efficiency. This means closure iterators +# have slightly different semantics from ordinary closures. + + const upName* = ":up" # field name for the 'up' reference - paramName* = ":env" + paramName* = ":envP" envName* = ":env" type - PInnerContext = ref TInnerContext POuterContext = ref TOuterContext + TIter = object + fn, closureParam, state, resultSym: PSym # most are only valid if + # fn.kind == skClosureIterator + obj: PType + PEnv = ref TEnv - TDep = tuple[e: PEnv, field: PSym] TEnv {.final.} = object of TObject - attachedNode: PNode - createdVar: PSym # if != nil it is a used environment + attachedNode, replacementNode: PNode + createdVar: PNode # if != nil it is a used environment; for closure + # iterators this can be 'envParam.env' createdVarComesFromIter: bool capturedVars: seq[PSym] # captured variables in this environment - deps: seq[TDep] # dependencies - up: PEnv + up, next: PEnv # outer scope and next to keep all in a list + upField: PSym # if != nil the dependency to the outer scope is used obj: PType - - TInnerContext = object - fn: PSym - closureParam: PSym - localsToAccess: TIdNodeTable + fn: PSym # function that belongs to this scope; + # if up.fn != fn then we cross function boundaries. + # This is an important case to consider. + vars: TIntSet # variables belonging to this environment TOuterContext = object fn: PSym # may also be a module! - currentEnv: PEnv - isIter: bool # first class iterator? + head: PEnv capturedVars, processed: TIntSet - localsToEnv: TIdTable # PSym->PEnv mapping localsToAccess: TIdNodeTable lambdasToEnv: TIdTable # PSym->PEnv mapping - up: POuterContext - - closureParam, state, resultSym: PSym # only if isIter - obj: PType # only if isIter proc getStateType(iter: PSym): PType = var n = newNodeI(nkRange, iter.info) @@ -147,12 +155,20 @@ proc getStateType(iter: PSym): PType = addSon(n, newIntNode(nkIntLit, 0)) result = newType(tyRange, iter) result.n = n - rawAddSon(result, getSysType(tyInt)) + var intType = nilOrSysInt() + if intType.isNil: intType = newType(tyInt, iter) + rawAddSon(result, intType) proc createStateField(iter: PSym): PSym = result = newSym(skField, getIdent(":state"), iter, iter.info) result.typ = getStateType(iter) +proc createEnvObj(owner: PSym): PType = + # YYY meh, just add the state field for every closure for now, it's too + # hard to figure out if it comes from a closure iterator: + result = createObj(owner, owner.info) + rawAddField(result, createStateField(owner)) + proc newIterResult(iter: PSym): PSym = if resultPos < iter.ast.len: result = iter.ast.sons[resultPos].sym @@ -164,6 +180,7 @@ proc newIterResult(iter: PSym): PSym = iter.ast.add newSymNode(result) proc addHiddenParam(routine: PSym, param: PSym) = + assert param.kind == skParam var params = routine.ast.sons[paramsPos] # -1 is correct here as param.position is 0 based but we have at position 0 # some nkEffect node: @@ -175,7 +192,7 @@ proc addHiddenParam(routine: PSym, param: PSym) = proc getHiddenParam(routine: PSym): PSym = let params = routine.ast.sons[paramsPos] let hidden = lastSon(params) - assert hidden.kind == nkSym + internalAssert hidden.kind == nkSym and hidden.sym.kind == skParam result = hidden.sym proc getEnvParam(routine: PSym): PSym = @@ -184,161 +201,191 @@ proc getEnvParam(routine: PSym): PSym = if hidden.kind == nkSym and hidden.sym.name.s == paramName: result = hidden.sym -proc initIterContext(c: POuterContext, iter: PSym) = - c.fn = iter - c.capturedVars = initIntSet() - - var cp = getEnvParam(iter) - if cp == nil: - c.obj = createObj(iter, iter.info) - - cp = newSym(skParam, getIdent(paramName), iter, iter.info) - incl(cp.flags, sfFromGeneric) - cp.typ = newType(tyRef, iter) - rawAddSon(cp.typ, c.obj) - addHiddenParam(iter, cp) - - c.state = createStateField(iter) - addField(c.obj, c.state) - else: - c.obj = cp.typ.sons[0] - assert c.obj.kind == tyObject - if c.obj.n.len > 0: - c.state = c.obj.n[0].sym +proc initIter(iter: PSym): TIter = + result.fn = iter + if iter.kind == skClosureIterator: + var cp = getEnvParam(iter) + if cp == nil: + result.obj = createEnvObj(iter) + + cp = newSym(skParam, getIdent(paramName), iter, iter.info) + incl(cp.flags, sfFromGeneric) + cp.typ = newType(tyRef, iter) + rawAddSon(cp.typ, result.obj) + addHiddenParam(iter, cp) else: - c.state = createStateField(iter) - addField(c.obj, c.state) - - c.closureParam = cp - if iter.typ.sons[0] != nil: - c.resultSym = newIterResult(iter) - #iter.ast.add(newSymNode(c.resultSym)) - -proc newOuterContext(fn: PSym, up: POuterContext = nil): POuterContext = + result.obj = cp.typ.sons[0] + assert result.obj.kind == tyObject + internalAssert result.obj.n.len > 0 + result.state = result.obj.n[0].sym + result.closureParam = cp + if iter.typ.sons[0] != nil: + result.resultSym = newIterResult(iter) + #iter.ast.add(newSymNode(c.resultSym)) + +proc newOuterContext(fn: PSym): POuterContext = new(result) result.fn = fn result.capturedVars = initIntSet() result.processed = initIntSet() initIdNodeTable(result.localsToAccess) - initIdTable(result.localsToEnv) initIdTable(result.lambdasToEnv) - result.isIter = fn.kind == skClosureIterator - if result.isIter: initIterContext(result, fn) -proc newInnerContext(fn: PSym): PInnerContext = +proc newEnv(o: POuterContext; up: PEnv, n: PNode; owner: PSym): PEnv = new(result) - result.fn = fn - initIdNodeTable(result.localsToAccess) - -proc newEnv(outerProc: PSym, up: PEnv, n: PNode): PEnv = - new(result) - result.deps = @[] result.capturedVars = @[] - result.obj = createObj(outerProc, outerProc.info) result.up = up result.attachedNode = n + result.fn = owner + result.vars = initIntSet() + result.next = o.head + o.head = result + if owner.kind != skModule and (up == nil or up.fn != owner): + let param = getEnvParam(owner) + if param != nil: + result.obj = param.typ.sons[0] + assert result.obj.kind == tyObject + if result.obj.isNil: + result.obj = createEnvObj(owner) proc addCapturedVar(e: PEnv, v: PSym) = for x in e.capturedVars: if x == v: return - # XXX meh, just add the state field for every closure for now, it's too - # hard to figure out if it comes from a closure iterator: - if e.obj.n.len == 0: addField(e.obj, createStateField(v.owner)) e.capturedVars.add(v) addField(e.obj, v) - -proc addDep(e, d: PEnv, owner: PSym): PSym = - for x, field in items(e.deps): - if x == d: return field - var pos = sonsLen(e.obj.n) - result = newSym(skField, getIdent(upName & $pos), owner, owner.info) - result.typ = newType(tyRef, owner) - result.position = pos - assert d.obj != nil - rawAddSon(result.typ, d.obj) - addField(e.obj, result) - e.deps.add((d, result)) -proc newCall(a, b: PSym): PNode = +proc newCall(a: PSym, b: PNode): PNode = result = newNodeI(nkCall, a.info) result.add newSymNode(a) - result.add newSymNode(b) - -proc isInnerProc(s, outerProc: PSym): bool {.inline.} = - result = s.kind in {skProc, skMethod, skConverter, skClosureIterator} and - s.skipGenericOwner == outerProc + result.add b + +proc isInnerProc(s, outerProc: PSym): bool = + if s.kind in {skProc, skMethod, skConverter, skClosureIterator}: + var owner = s.skipGenericOwner + while true: + if owner.isNil: return false + if owner == outerProc: return true + owner = owner.owner #s.typ.callConv == ccClosure -proc addClosureParam(i: PInnerContext, e: PEnv) = - var cp = getEnvParam(i.fn) +proc addClosureParam(fn: PSym; e: PEnv) = + var cp = getEnvParam(fn) if cp == nil: - cp = newSym(skParam, getIdent(paramName), i.fn, i.fn.info) + cp = newSym(skParam, getIdent(paramName), fn, fn.info) incl(cp.flags, sfFromGeneric) - cp.typ = newType(tyRef, i.fn) + cp.typ = newType(tyRef, fn) rawAddSon(cp.typ, e.obj) - addHiddenParam(i.fn, cp) - else: - e.obj = cp.typ.sons[0] - assert e.obj.kind == tyObject - i.closureParam = cp - #echo "closure param added for ", i.fn.name.s, " ", i.fn.id - -proc dummyClosureParam(o: POuterContext, i: PInnerContext) = - var e = o.currentEnv - if idTableGet(o.lambdasToEnv, i.fn) == nil: - idTablePut(o.lambdasToEnv, i.fn, e) - if i.closureParam == nil: addClosureParam(i, e) + addHiddenParam(fn, cp) + #else: + #cp.typ.sons[0] = e.obj + #assert e.obj.kind == tyObject proc illegalCapture(s: PSym): bool {.inline.} = result = skipTypes(s.typ, abstractInst).kind in {tyVar, tyOpenArray, tyVarargs} or s.kind == skResult -proc captureVar(o: POuterContext, i: PInnerContext, local: PSym, - info: TLineInfo) = - # for inlined variables the owner is still wrong, so it can happen that it's - # not a captured variable at all ... *sigh* - var it = PEnv(idTableGet(o.localsToEnv, local)) - if it == nil: return - - if illegalCapture(local) or o.fn.id != local.owner.id or - i.fn.typ.callConv notin {ccClosure, ccDefault}: - # Currently captures are restricted to a single level of nesting: - localError(info, errIllegalCaptureX, local.name.s) - i.fn.typ.callConv = ccClosure - #echo "captureVar ", i.fn.name.s, i.fn.id, " ", local.name.s, local.id - - incl(i.fn.typ.flags, tfCapturesEnv) - - # we need to remember which inner most closure belongs to this lambda: - var e = o.currentEnv - if idTableGet(o.lambdasToEnv, i.fn) == nil: - idTablePut(o.lambdasToEnv, i.fn, e) - - # variable already captured: - if idNodeTableGet(i.localsToAccess, local) != nil: return - if i.closureParam == nil: addClosureParam(i, e) - - # check which environment `local` belongs to: - var access = newSymNode(i.closureParam) - addCapturedVar(it, local) - if it == e: - # common case: local directly in current environment: - discard - else: - # it's in some upper environment: - access = indirectAccess(access, addDep(e, it, i.fn), info) - access = indirectAccess(access, local, info) - if o.isIter: - if not containsOrIncl(o.capturedVars, local.id): addField(o.obj, local) - else: - incl(o.capturedVars, local.id) - idNodeTablePut(i.localsToAccess, local, access) - proc interestingVar(s: PSym): bool {.inline.} = result = s.kind in {skVar, skLet, skTemp, skForVar, skParam, skResult} and sfGlobal notin s.flags +proc nestedAccess(top: PEnv; local: PSym): PNode = + # Parts after the transformation are in []: + # + # proc main = + # var [:env.]foo = 23 + # proc outer(:paramO) = + # [var :envO; createClosure(:envO); :envO.up = paramO] + # proc inner(:paramI) = + # echo [:paramI.up.]foo + # inner([:envO]) + # outer([:env]) + if not interestingVar(local) or top.fn == local.owner: + return nil + # check it's in fact a captured variable: + var it = top + while it != nil: + if it.vars.contains(local.id): break + it = it.up + if it == nil: return nil + let envParam = top.fn.getEnvParam + internalAssert(not envParam.isNil) + var access = newSymNode(envParam) + it = top.up + while it != nil: + if it.vars.contains(local.id): + access = indirectAccess(access, local, local.info) + return access + internalAssert it.upField != nil + access = indirectAccess(access, it.upField, local.info) + it = it.up + when false: + # Type based expression construction works too, but turned out to hide + # other bugs: + while true: + let obj = access.typ.sons[0] + let field = getFieldFromObj(obj, local) + if field != nil: + return rawIndirectAccess(access, field, local.info) + let upField = lookupInRecord(obj.n, getIdent(upName)) + if upField == nil: break + access = rawIndirectAccess(access, upField, local.info) + return nil + +proc createUpField(obj, fieldType: PType): PSym = + let pos = obj.n.len + result = newSym(skField, getIdent(upName), obj.owner, obj.owner.info) + result.typ = newType(tyRef, obj.owner) + result.position = pos + rawAddSon(result.typ, fieldType) + #rawAddField(obj, result) + addField(obj, result) + +proc captureVar(o: POuterContext; top: PEnv; local: PSym; + info: TLineInfo): bool = + # first check if we should be concerned at all: + var it = top + while it != nil: + if it.vars.contains(local.id): break + it = it.up + if it == nil: return false + # yes, so mark every 'up' pointer as taken: + if illegalCapture(local) or top.fn.typ.callConv notin {ccClosure, ccDefault}: + localError(info, errIllegalCaptureX, local.name.s) + it = top + while it != nil: + if it.vars.contains(local.id): break + # keep in mind that the first element of the chain belong to top.fn itself + # and these don't need any upFields + if it.upField == nil and it.up != nil and it.fn != top.fn: + it.upField = createUpField(it.obj, it.up.obj) + + if it.fn != local.owner: + it.fn.typ.callConv = ccClosure + incl(it.fn.typ.flags, tfCapturesEnv) + + var u = it.up + while u != nil and u.fn == it.fn: u = u.up + addClosureParam(it.fn, u) + + if idTableGet(o.lambdasToEnv, it.fn) == nil: + if u != nil: idTablePut(o.lambdasToEnv, it.fn, u) + + it = it.up + # don't do this: 'top' might not require a closure: + #if idTableGet(o.lambdasToEnv, it.fn) == nil: + # idTablePut(o.lambdasToEnv, it.fn, top) + + # mark as captured: + #if top.iter != nil: + # if not containsOrIncl(o.capturedVars, local.id): + # #addField(top.iter.obj, local) + # addCapturedVar(it, local) + #else: + incl(o.capturedVars, local.id) + addCapturedVar(it, local) + result = true + proc semCaptureSym*(s, owner: PSym) = if interestingVar(s) and owner.id != s.owner.id and s.kind != skResult: if owner.typ != nil and not isGenericRoutine(owner): @@ -350,28 +397,20 @@ proc semCaptureSym*(s, owner: PSym) = # since the analysis is not entirely correct, we don't set 'tfCapturesEnv' # here -proc gatherVars(o: POuterContext, i: PInnerContext, n: PNode) = - # gather used vars for closure generation - if n == nil: return +proc gatherVars(o: POuterContext; e: PEnv; n: PNode): int = + # gather used vars for closure generation; returns number of captured vars + if n == nil: return 0 case n.kind of nkSym: var s = n.sym - if interestingVar(s) and i.fn.id != s.owner.id: - captureVar(o, i, s, n.info) - elif s.kind in {skProc, skMethod, skConverter} and - s.skipGenericOwner == o.fn and - tfCapturesEnv in s.typ.flags and s != i.fn: - # call to some other inner proc; we need to track the dependencies for - # this: - let env = PEnv(idTableGet(o.lambdasToEnv, i.fn)) - if env == nil: internalError(n.info, "no environment computed") - if o.currentEnv != env: - discard addDep(o.currentEnv, env, i.fn) - internalError(n.info, "too complex environment handling required") - of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit, nkClosure: discard + if interestingVar(s) and e.fn != s.owner: + if captureVar(o, e, s, n.info): result = 1 + of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit, nkClosure, nkProcDef, + nkMethodDef, nkConverterDef, nkMacroDef, nkTemplateDef, nkTypeSection: + discard else: - for k in countup(0, sonsLen(n) - 1): - gatherVars(o, i, n.sons[k]) + for k in countup(0, sonsLen(n) - 1): + result += gatherVars(o, e, n.sons[k]) proc generateThunk(prc: PNode, dest: PType): PNode = ## Converts 'prc' into '(thunk, nil)' so that it's compatible with @@ -395,84 +434,143 @@ proc transformOuterConv(n: PNode): PNode = if dest.callConv == ccClosure and source.callConv == ccDefault: result = generateThunk(n.sons[1], dest) -proc makeClosure(prc, env: PSym, info: TLineInfo): PNode = +proc makeClosure(prc: PSym; env: PNode; info: TLineInfo): PNode = result = newNodeIT(nkClosure, info, prc.typ) result.add(newSymNode(prc)) if env == nil: result.add(newNodeIT(nkNilLit, info, getSysType(tyNil))) else: - result.add(newSymNode(env)) + result.add(env) + +proc newClosureCreationVar(e: PEnv): PNode = + var v = newSym(skVar, getIdent(envName), e.fn, e.attachedNode.info) + incl(v.flags, sfShadowed) + v.typ = newType(tyRef, e.fn) + v.typ.rawAddSon(e.obj) + if e.fn.kind == skClosureIterator: + let it = initIter(e.fn) + addUniqueField(it.obj, v) + result = indirectAccess(newSymNode(it.closureParam), v, v.info) + else: + result = newSymNode(v) + +proc getClosureVar(e: PEnv): PNode = + if e.createdVar == nil: + result = newClosureCreationVar(e) + e.createdVar = result + else: + result = e.createdVar + +proc findEnv(o: POuterContext; s: PSym): PEnv = + var env = o.head + while env != nil: + if env.fn == s: break + env = env.next + internalAssert env != nil and env.up != nil + result = env.up + while result.fn == s: result = result.up -proc transformInnerProc(o: POuterContext, i: PInnerContext, n: PNode): PNode = +proc transformInnerProc(o: POuterContext; e: PEnv, n: PNode): PNode = case n.kind of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: discard of nkSym: let s = n.sym - if s == i.fn: + if s == e.fn: # recursive calls go through (lambda, hiddenParam): - assert i.closureParam != nil, i.fn.name.s - result = makeClosure(s, i.closureParam, n.info) + result = makeClosure(s, getEnvParam(s).newSymNode, n.info) elif isInnerProc(s, o.fn) and s.typ.callConv == ccClosure: - # ugh: call to some other inner proc; - assert i.closureParam != nil - # XXX this is not correct in general! may also be some 'closure.upval' - result = makeClosure(s, i.closureParam, n.info) + # ugh: call to some other inner proc; + result = makeClosure(s, findEnv(o, s).getClosureVar, n.info) else: # captured symbol? - result = idNodeTableGet(i.localsToAccess, n.sym) - of nkLambdaKinds, nkIteratorDef: - if n.typ != nil: - result = transformInnerProc(o, i, n.sons[namePos]) + result = nestedAccess(e, n.sym) + #result = idNodeTableGet(i.localsToAccess, n.sym) + #of nkLambdaKinds, nkIteratorDef: + # if n.typ != nil: + # result = transformInnerProc(o, e, n.sons[namePos]) + #of nkClosure: + # let x = transformInnerProc(o, e, n.sons[0]) + # if x != nil: n.sons[0] = x of nkProcDef, nkMethodDef, nkConverterDef, nkMacroDef, nkTemplateDef, - nkClosure: + nkLambdaKinds, nkIteratorDef, nkClosure: # don't recurse here: discard else: for j in countup(0, sonsLen(n) - 1): - let x = transformInnerProc(o, i, n.sons[j]) + let x = transformInnerProc(o, e, n.sons[j]) if x != nil: n.sons[j] = x proc closureCreationPoint(n: PNode): PNode = - result = newNodeI(nkStmtList, n.info) - result.add(emptyNode) - result.add(n) - -proc searchForInnerProcs(o: POuterContext, n: PNode) = + if n.kind == nkStmtList and n.len >= 1 and n[0].kind == nkEmpty: + # we already have a free slot + result = n + else: + result = newNodeI(nkStmtList, n.info) + result.add(emptyNode) + result.add(n) + #result.flags.incl nfLL + +proc addParamsToEnv(fn: PSym; env: PEnv) = + let params = fn.typ.n + for i in 1.. <params.len: + if params.sons[i].kind != nkSym: + internalError(params.info, "liftLambdas: strange params") + let param = params.sons[i].sym + env.vars.incl(param.id) + # put the 'result' into the environment so it can be captured: + let ast = fn.ast + if resultPos < sonsLen(ast) and ast.sons[resultPos].kind == nkSym: + env.vars.incl(ast.sons[resultPos].sym.id) + +proc searchForInnerProcs(o: POuterContext, n: PNode, env: PEnv) = if n == nil: return case n.kind - of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: + of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: discard of nkSym: - if isInnerProc(n.sym, o.fn) and not containsOrIncl(o.processed, n.sym.id): - var inner = newInnerContext(n.sym) - let body = n.sym.getBody - gatherVars(o, inner, body) + let fn = n.sym + if isInnerProc(fn, o.fn) and not containsOrIncl(o.processed, fn.id): + let body = fn.getBody + + # handle deeply nested captures: + let ex = closureCreationPoint(body) + let envB = newEnv(o, env, ex, fn) + addParamsToEnv(fn, envB) + searchForInnerProcs(o, body, envB) + fn.ast.sons[bodyPos] = ex + + let capturedCounter = gatherVars(o, envB, body) # dummy closure param needed? - if inner.closureParam == nil and n.sym.typ.callConv == ccClosure: + if capturedCounter == 0 and fn.typ.callConv == ccClosure: #assert tfCapturesEnv notin n.sym.typ.flags - dummyClosureParam(o, inner) - # only transform if it really needs a closure: - if inner.closureParam != nil: - let ti = transformInnerProc(o, inner, body) - if ti != nil: n.sym.ast.sons[bodyPos] = ti + if idTableGet(o.lambdasToEnv, fn) == nil: + idTablePut(o.lambdasToEnv, fn, env) + addClosureParam(fn, env) + + elif fn.getEnvParam != nil: + # only transform if it really needs a closure: + let ti = transformInnerProc(o, envB, body) + if ti != nil: fn.ast.sons[bodyPos] = ti of nkLambdaKinds, nkIteratorDef: if n.typ != nil: - searchForInnerProcs(o, n.sons[namePos]) + searchForInnerProcs(o, n.sons[namePos], env) of nkWhileStmt, nkForStmt, nkParForStmt, nkBlockStmt: # some nodes open a new scope, so they are candidates for the insertion # of closure creation; however for simplicity we merge closures between # branches, in fact, only loop bodies are of interest here as only they # yield observable changes in semantics. For Zahary we also - # include ``nkBlock``. - var body = n.len-1 - for i in countup(0, body - 1): searchForInnerProcs(o, n.sons[i]) - # special handling for the loop body: - let oldEnv = o.currentEnv - let ex = closureCreationPoint(n.sons[body]) - o.currentEnv = newEnv(o.fn, oldEnv, ex) - searchForInnerProcs(o, n.sons[body]) - n.sons[body] = ex - o.currentEnv = oldEnv + # include ``nkBlock``. We don't do this for closure iterators because + # 'yield' can produce wrong code otherwise (XXX show example): + if env.fn.kind != skClosureIterator: + var body = n.len-1 + for i in countup(0, body - 1): searchForInnerProcs(o, n.sons[i], env) + # special handling for the loop body: + let ex = closureCreationPoint(n.sons[body]) + searchForInnerProcs(o, n.sons[body], newEnv(o, env, ex, env.fn)) + n.sons[body] = ex + else: + for i in countup(0, sonsLen(n) - 1): + searchForInnerProcs(o, n.sons[i], env) of nkVarSection, nkLetSection: # we need to compute a mapping var->declaredBlock. Note: The definition # counts, not the block where it is captured! @@ -481,26 +579,29 @@ proc searchForInnerProcs(o: POuterContext, n: PNode) = if it.kind == nkCommentStmt: discard elif it.kind == nkIdentDefs: var L = sonsLen(it) - if it.sons[0].kind != nkSym: internalError(it.info, "transformOuter") - #echo "set: ", it.sons[0].sym.name.s, " ", o.currentBlock == nil - idTablePut(o.localsToEnv, it.sons[0].sym, o.currentEnv) - searchForInnerProcs(o, it.sons[L-1]) + if it.sons[0].kind == nkSym: + # this can be false for recursive invokations that already + # transformed it into 'env.varName': + env.vars.incl(it.sons[0].sym.id) + searchForInnerProcs(o, it.sons[L-1], env) elif it.kind == nkVarTuple: var L = sonsLen(it) for j in countup(0, L-3): #echo "set: ", it.sons[j].sym.name.s, " ", o.currentBlock == nil - idTablePut(o.localsToEnv, it.sons[j].sym, o.currentEnv) - searchForInnerProcs(o, it.sons[L-1]) + if it.sons[j].kind == nkSym: + env.vars.incl(it.sons[j].sym.id) + searchForInnerProcs(o, it.sons[L-1], env) else: - internalError(it.info, "transformOuter") + internalError(it.info, "searchForInnerProcs") + of nkClosure: + searchForInnerProcs(o, n.sons[0], env) of nkProcDef, nkMethodDef, nkConverterDef, nkMacroDef, nkTemplateDef, - nkClosure, nkTypeSection: + nkTypeSection: # don't recurse here: - # XXX recurse here and setup 'up' pointers discard else: for i in countup(0, sonsLen(n) - 1): - searchForInnerProcs(o, n.sons[i]) + searchForInnerProcs(o, n.sons[i], env) proc newAsgnStmt(le, ri: PNode, info: TLineInfo): PNode = # Bugfix: unfortunately we cannot use 'nkFastAsgn' here as that would @@ -512,24 +613,12 @@ proc newAsgnStmt(le, ri: PNode, info: TLineInfo): PNode = result.sons[0] = le result.sons[1] = ri -proc newClosureCreationVar(o: POuterContext; e: PEnv): PSym = - result = newSym(skVar, getIdent(envName), o.fn, e.attachedNode.info) - incl(result.flags, sfShadowed) - result.typ = newType(tyRef, o.fn) - result.typ.rawAddSon(e.obj) - -proc getClosureVar(o: POuterContext; e: PEnv): PSym = - if e.createdVar == nil: - result = newClosureCreationVar(o, e) - e.createdVar = result - else: - result = e.createdVar - -proc rawClosureCreation(o: POuterContext, scope: PEnv; env: PSym): PNode = +proc rawClosureCreation(o: POuterContext, scope: PEnv; env: PNode): PNode = result = newNodeI(nkStmtList, env.info) - var v = newNodeI(nkVarSection, env.info) - addVar(v, newSymNode(env)) - result.add(v) + if env.kind == nkSym: + var v = newNodeI(nkVarSection, env.info) + addVar(v, env) + result.add(v) # add 'new' statement: result.add(newCall(getSysSym"internalNew", env)) @@ -548,21 +637,25 @@ proc rawClosureCreation(o: POuterContext, scope: PEnv; env: PSym): PNode = idNodeTablePut(o.localsToAccess, local, fieldAccess) else: result.add(newAsgnStmt(fieldAccess, existing, env.info)) - # add support for 'up' references: - for e, field in items(scope.deps): - # add ``env.up = env2`` - result.add(newAsgnStmt(indirectAccess(env, field, env.info), - newSymNode(getClosureVar(o, e)), env.info)) - + if scope.upField != nil: + # "up" chain has been used: + if scope.up.fn != scope.fn: + # crosses function boundary: + result.add(newAsgnStmt(indirectAccess(env, scope.upField, env.info), + newSymNode(getEnvParam(scope.fn)), env.info)) + else: + result.add(newAsgnStmt(indirectAccess(env, scope.upField, env.info), + getClosureVar(scope.up), env.info)) + proc generateClosureCreation(o: POuterContext, scope: PEnv): PNode = - var env = getClosureVar(o, scope) + var env = getClosureVar(scope) result = rawClosureCreation(o, scope, env) proc generateIterClosureCreation(o: POuterContext; env: PEnv; - scope: PNode): PSym = + scope: PNode): PNode = if env.createdVarComesFromIter or env.createdVar.isNil: # we have to create a new closure: - result = newClosureCreationVar(o, env) + result = newClosureCreationVar(env) let cc = rawClosureCreation(o, env, result) var insertPoint = scope.sons[0] if insertPoint.kind == nkEmpty: scope.sons[0] = cc @@ -577,21 +670,25 @@ proc generateIterClosureCreation(o: POuterContext; env: PEnv; proc interestingIterVar(s: PSym): bool {.inline.} = result = s.kind in {skVar, skLet, skTemp, skForVar} and sfGlobal notin s.flags -proc transformOuterProc(o: POuterContext, n: PNode): PNode +proc transformOuterProc(o: POuterContext, n: PNode, it: TIter): PNode -proc transformYield(c: POuterContext, n: PNode): PNode = - inc c.state.typ.n.sons[1].intVal - let stateNo = c.state.typ.n.sons[1].intVal +proc transformYield(c: POuterContext, n: PNode, it: TIter): PNode = + assert it.state != nil + assert it.state.typ != nil + assert it.state.typ.n != nil + inc it.state.typ.n.sons[1].intVal + let stateNo = it.state.typ.n.sons[1].intVal var stateAsgnStmt = newNodeI(nkAsgn, n.info) - stateAsgnStmt.add(indirectAccess(newSymNode(c.closureParam),c.state,n.info)) + stateAsgnStmt.add(rawIndirectAccess(newSymNode(it.closureParam), + it.state, n.info)) stateAsgnStmt.add(newIntTypeNode(nkIntLit, stateNo, getSysType(tyInt))) var retStmt = newNodeI(nkReturnStmt, n.info) if n.sons[0].kind != nkEmpty: var a = newNodeI(nkAsgn, n.sons[0].info) - var retVal = transformOuterProc(c, n.sons[0]) - addSon(a, newSymNode(c.resultSym)) + var retVal = transformOuterProc(c, n.sons[0], it) + addSon(a, newSymNode(it.resultSym)) addSon(a, if retVal.isNil: n.sons[0] else: retVal) retStmt.add(a) else: @@ -605,17 +702,18 @@ proc transformYield(c: POuterContext, n: PNode): PNode = result.add(retStmt) result.add(stateLabelStmt) -proc transformReturn(c: POuterContext, n: PNode): PNode = +proc transformReturn(c: POuterContext, n: PNode, it: TIter): PNode = result = newNodeI(nkStmtList, n.info) var stateAsgnStmt = newNodeI(nkAsgn, n.info) - stateAsgnStmt.add(indirectAccess(newSymNode(c.closureParam),c.state,n.info)) + stateAsgnStmt.add(rawIndirectAccess(newSymNode(it.closureParam), it.state, + n.info)) stateAsgnStmt.add(newIntTypeNode(nkIntLit, -1, getSysType(tyInt))) result.add(stateAsgnStmt) result.add(n) -proc outerProcSons(o: POuterContext, n: PNode) = +proc outerProcSons(o: POuterContext, n: PNode, it: TIter) = for i in countup(0, sonsLen(n) - 1): - let x = transformOuterProc(o, n.sons[i]) + let x = transformOuterProc(o, n.sons[i], it) if x != nil: n.sons[i] = x proc liftIterSym*(n: PNode): PNode = @@ -631,27 +729,137 @@ proc liftIterSym*(n: PNode): PNode = addVar(v, newSymNode(env)) result.add(v) # add 'new' statement: - result.add(newCall(getSysSym"internalNew", env)) - result.add makeClosure(iter, env, n.info) + let envAsNode = env.newSymNode + result.add newCall(getSysSym"internalNew", envAsNode) + result.add makeClosure(iter, envAsNode, n.info) + +when false: + proc transformRemainingLocals(n: PNode; it: TIter): PNode = + assert it.fn.kind == skClosureIterator + result = n + case n.kind + of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: discard + of nkSym: + let local = n.sym + if interestingIterVar(local) and it.fn == local.owner: + addUniqueField(it.obj, local) + result = indirectAccess(newSymNode(it.closureParam), local, n.info) + else: + result = newNodeI(n.kind, n.info, n.len) + for i in 0.. <n.safeLen: + result.sons[i] = transformRemainingLocals(n.sons[i], it) + +template envActive(env): expr = + (env.capturedVars.len > 0 or env.upField != nil) + +# We have to split up environment creation in 2 steps: +# 1. Generate it and store it in env.replacementNode +# 2. Insert replacementNode into its forseen slot. +# This split is necessary so that assignments belonging to closure +# creation like 'env.param = param' are not transformed +# into 'env.param = env.param'. +proc createEnvironments(o: POuterContext) = + var env = o.head + while env != nil: + if envActive(env): + var scope = env.attachedNode + assert scope.kind == nkStmtList + if scope.sons[0].kind == nkEmpty: + # prepare for closure construction: + env.replacementNode = generateClosureCreation(o, env) + env = env.next + +proc finishEnvironments(o: POuterContext) = + var env = o.head + while env != nil: + if env.replacementNode != nil: + var scope = env.attachedNode + assert scope.kind == nkStmtList + if scope.sons[0].kind == nkEmpty: + # change the empty node to contain the closure construction: + scope.sons[0] = env.replacementNode + when false: + if env.fn.kind == skClosureIterator: + scope.sons[0] = transformRemainingLocals(env.replacementNode, + initIter(env.fn)) + else: + scope.sons[0] = env.replacementNode + env = env.next + +proc transformOuterProcBody(o: POuterContext, n: PNode; it: TIter): PNode = + if nfLL in n.flags: + result = nil + elif it.fn.kind == skClosureIterator: + # unfortunately control flow is still convoluted and we can end up + # multiple times here for the very same iterator. We shield against this + # with some rather primitive check for now: + if n.kind == nkStmtList and n.len > 0: + if n.sons[0].kind == nkGotoState: return nil + if n.len > 1 and n[1].kind == nkStmtList and n[1].len > 0 and + n[1][0].kind == nkGotoState: + return nil + result = newNodeI(nkStmtList, it.fn.info) + var gs = newNodeI(nkGotoState, it.fn.info) + assert it.closureParam != nil + assert it.state != nil + gs.add(rawIndirectAccess(newSymNode(it.closureParam), it.state, it.fn.info)) + result.add(gs) + var state0 = newNodeI(nkState, it.fn.info) + state0.add(newIntNode(nkIntLit, 0)) + result.add(state0) + + let newBody = transformOuterProc(o, n, it) + if newBody != nil: + result.add(newBody) + else: + result.add(n) + + var stateAsgnStmt = newNodeI(nkAsgn, it.fn.info) + stateAsgnStmt.add(rawIndirectAccess(newSymNode(it.closureParam), + it.state, it.fn.info)) + stateAsgnStmt.add(newIntTypeNode(nkIntLit, -1, getSysType(tyInt))) + result.add(stateAsgnStmt) + result.flags.incl nfLL + else: + result = transformOuterProc(o, n, it) + if result != nil: result.flags.incl nfLL -proc transformOuterProc(o: POuterContext, n: PNode): PNode = - if n == nil: return nil +proc transformOuterProc(o: POuterContext, n: PNode; it: TIter): PNode = + if n == nil or nfLL in n.flags: return nil case n.kind of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: discard of nkSym: var local = n.sym - if o.isIter and interestingIterVar(local) and o.fn.id == local.owner.id: - if not containsOrIncl(o.capturedVars, local.id): addField(o.obj, local) - return indirectAccess(newSymNode(o.closureParam), local, n.info) + if isInnerProc(local, o.fn) and o.processed.contains(local.id): + o.processed.excl(local.id) + let body = local.getBody + let newBody = transformOuterProcBody(o, body, initIter(local)) + if newBody != nil: + local.ast.sons[bodyPos] = newBody + + if it.fn.kind == skClosureIterator and interestingIterVar(local) and + it.fn == local.owner: + # every local goes through the closure: + #if not containsOrIncl(o.capturedVars, local.id): + # addField(it.obj, local) + if contains(o.capturedVars, local.id): + # change 'local' to 'closure.local', unless it's a 'byCopy' variable: + # if sfByCopy notin local.flags: + result = idNodeTableGet(o.localsToAccess, local) + assert result != nil, "cannot find: " & local.name.s + return result + else: + addUniqueField(it.obj, local) + return indirectAccess(newSymNode(it.closureParam), local, n.info) var closure = PEnv(idTableGet(o.lambdasToEnv, local)) - if local.kind == skClosureIterator: # consider: [i1, i2, i1] Since we merged the iterator's closure # with the captured owning variables, we need to generate the # closure generation code again: - if local == o.fn: message(n.info, errRecursiveDependencyX, local.name.s) + if local == o.fn or local == it.fn: + message(n.info, errRecursiveDependencyX, local.name.s) # XXX why doesn't this work? if closure.isNil: return liftIterSym(n) @@ -662,7 +870,6 @@ proc transformOuterProc(o: POuterContext, n: PNode): PNode = if closure != nil: # we need to replace the lambda with '(lambda, env)': - let a = closure.createdVar if a != nil: return makeClosure(local, a, n.info) @@ -678,14 +885,6 @@ proc transformOuterProc(o: POuterContext, n: PNode): PNode = return makeClosure(local, x, n.info) if not contains(o.capturedVars, local.id): return - var env = PEnv(idTableGet(o.localsToEnv, local)) - if env == nil: return - var scope = env.attachedNode - assert scope.kind == nkStmtList - if scope.sons[0].kind == nkEmpty: - # change the empty node to contain the closure construction: - scope.sons[0] = generateClosureCreation(o, env) - # change 'local' to 'closure.local', unless it's a 'byCopy' variable: # if sfByCopy notin local.flags: result = idNodeTableGet(o.localsToAccess, local) @@ -694,73 +893,64 @@ proc transformOuterProc(o: POuterContext, n: PNode): PNode = # to access the local as a local. of nkLambdaKinds, nkIteratorDef: if n.typ != nil: - result = transformOuterProc(o, n.sons[namePos]) - of nkProcDef, nkMethodDef, nkConverterDef, nkMacroDef, nkTemplateDef, - nkClosure: + result = transformOuterProc(o, n.sons[namePos], it) + of nkProcDef, nkMethodDef, nkConverterDef, nkMacroDef, nkTemplateDef: # don't recurse here: discard + of nkClosure: + if n.sons[0].kind == nkSym: + var local = n.sons[0].sym + if isInnerProc(local, o.fn) and o.processed.contains(local.id): + o.processed.excl(local.id) + let body = local.getBody + let newBody = transformOuterProcBody(o, body, initIter(local)) + if newBody != nil: + local.ast.sons[bodyPos] = newBody + when false: + if n.sons[1].kind == nkSym: + var local = n.sons[1].sym + if it.fn.kind == skClosureIterator and interestingIterVar(local) and + it.fn == local.owner: + # every local goes through the closure: + addUniqueField(it.obj, local) + n.sons[1] = indirectAccess(newSymNode(it.closureParam), local, n.info) of nkHiddenStdConv, nkHiddenSubConv, nkConv: - let x = transformOuterProc(o, n.sons[1]) + let x = transformOuterProc(o, n.sons[1], it) if x != nil: n.sons[1] = x result = transformOuterConv(n) of nkYieldStmt: - if o.isIter: result = transformYield(o, n) - else: outerProcSons(o, n) + if it.fn.kind == skClosureIterator: result = transformYield(o, n, it) + else: outerProcSons(o, n, it) of nkReturnStmt: - if o.isIter: result = transformReturn(o, n) - else: outerProcSons(o, n) - else: - outerProcSons(o, n) - -proc liftIterator(c: POuterContext, body: PNode): PNode = - let iter = c.fn - result = newNodeI(nkStmtList, iter.info) - var gs = newNodeI(nkGotoState, iter.info) - gs.add(indirectAccess(newSymNode(c.closureParam), c.state, iter.info)) - result.add(gs) - var state0 = newNodeI(nkState, iter.info) - state0.add(newIntNode(nkIntLit, 0)) - result.add(state0) - - let newBody = transformOuterProc(c, body) - if newBody != nil: - result.add(newBody) + if it.fn.kind == skClosureIterator: result = transformReturn(o, n, it) + else: outerProcSons(o, n, it) else: - result.add(body) - - var stateAsgnStmt = newNodeI(nkAsgn, iter.info) - stateAsgnStmt.add(indirectAccess(newSymNode(c.closureParam), - c.state,iter.info)) - stateAsgnStmt.add(newIntTypeNode(nkIntLit, -1, getSysType(tyInt))) - result.add(stateAsgnStmt) + outerProcSons(o, n, it) proc liftLambdas*(fn: PSym, body: PNode): PNode = # XXX gCmd == cmdCompileToJS does not suffice! The compiletime stuff needs # the transformation even when compiling to JS ... - if body.kind == nkEmpty or gCmd == cmdCompileToJS: + if body.kind == nkEmpty or gCmd == cmdCompileToJS or + fn.skipGenericOwner.kind != skModule: # ignore forward declaration: result = body else: + #if fn.name.s == "cbOuter": + # echo rendertree(fn.ast, {renderIds}) var o = newOuterContext(fn) let ex = closureCreationPoint(body) - o.currentEnv = newEnv(fn, nil, ex) - # put all params into the environment so they can be captured: - let params = fn.typ.n - for i in 1.. <params.len: - if params.sons[i].kind != nkSym: - internalError(params.info, "liftLambdas: strange params") - let param = params.sons[i].sym - idTablePut(o.localsToEnv, param, o.currentEnv) - # put the 'result' into the environment so it can be captured: - let ast = fn.ast - if resultPos < sonsLen(ast) and ast.sons[resultPos].kind == nkSym: - idTablePut(o.localsToEnv, ast.sons[resultPos].sym, o.currentEnv) - searchForInnerProcs(o, body) - if o.isIter: - result = liftIterator(o, ex) + let env = newEnv(o, nil, ex, fn) + addParamsToEnv(fn, env) + searchForInnerProcs(o, body, env) + createEnvironments(o) + if fn.kind == skClosureIterator: + result = transformOuterProcBody(o, body, initIter(fn)) else: - discard transformOuterProc(o, body) + discard transformOuterProcBody(o, body, initIter(fn)) result = ex + finishEnvironments(o) + #if fn.name.s == "cbOuter": + # echo rendertree(result, {renderIds}) proc liftLambdasForTopLevel*(module: PSym, body: PNode): PNode = if body.kind == nkEmpty or gCmd == cmdCompileToJS: @@ -768,9 +958,11 @@ proc liftLambdasForTopLevel*(module: PSym, body: PNode): PNode = else: var o = newOuterContext(module) let ex = closureCreationPoint(body) - o.currentEnv = newEnv(module, nil, ex) - searchForInnerProcs(o, body) - discard transformOuterProc(o, body) + let env = newEnv(o, nil, ex, module) + searchForInnerProcs(o, body, env) + createEnvironments(o) + discard transformOuterProc(o, body, initIter(module)) + finishEnvironments(o) result = ex # ------------------- iterator transformation -------------------------------- @@ -821,7 +1013,7 @@ proc liftForLoop*(body: PNode): PNode = addVar(v, newSymNode(env)) result.add(v) # add 'new' statement: - result.add(newCall(getSysSym"internalNew", env)) + result.add(newCall(getSysSym"internalNew", env.newSymNode)) var loopBody = newNodeI(nkStmtList, body.info, 3) var whileLoop = newNodeI(nkWhileStmt, body.info, 2) @@ -840,16 +1032,12 @@ proc liftForLoop*(body: PNode): PNode = addSon(vpart, ast.emptyNode) # no explicit type if not env.isNil: - call.sons[0] = makeClosure(call.sons[0].sym, env, body.info) + call.sons[0] = makeClosure(call.sons[0].sym, env.newSymNode, body.info) addSon(vpart, call) addSon(v2, vpart) loopBody.sons[0] = v2 var bs = newNodeI(nkBreakState, body.info) - #if not env.isNil: - # bs.addSon(indirectAccess(env, - # newSym(skField, getIdent":state", env, env.info), body.info)) - #else: bs.addSon(call.sons[0]) loopBody.sons[1] = bs loopBody.sons[2] = body[L-1] |