diff options
-rwxr-xr-x | compiler/ast.nim | 20 | ||||
-rw-r--r-- | compiler/ccgcalls.nim | 71 | ||||
-rwxr-xr-x | compiler/ccgexprs.nim | 30 | ||||
-rwxr-xr-x | compiler/ccgstmts.nim | 19 | ||||
-rwxr-xr-x | compiler/ccgtypes.nim | 32 | ||||
-rwxr-xr-x | compiler/cgen.nim | 33 | ||||
-rw-r--r-- | compiler/lambdalifting.nim | 232 | ||||
-rwxr-xr-x | compiler/msgs.nim | 3 | ||||
-rwxr-xr-x | compiler/renderer.nim | 4 | ||||
-rwxr-xr-x | compiler/semexprs.nim | 14 | ||||
-rwxr-xr-x | compiler/semstmts.nim | 5 | ||||
-rwxr-xr-x | compiler/semthreads.nim | 2 | ||||
-rwxr-xr-x | compiler/sigmatch.nim | 10 | ||||
-rwxr-xr-x | compiler/transf.nim | 98 | ||||
-rwxr-xr-x | compiler/trees.nim | 2 | ||||
-rwxr-xr-x | compiler/types.nim | 11 | ||||
-rwxr-xr-x | doc/gramcurl.txt | 179 | ||||
-rwxr-xr-x | doc/intern.txt | 129 | ||||
-rwxr-xr-x | doc/manual.txt | 37 | ||||
-rwxr-xr-x | lib/pure/algorithm.nim | 18 | ||||
-rwxr-xr-x | lib/system.nim | 3 | ||||
-rwxr-xr-x | todo.txt | 24 | ||||
-rwxr-xr-x | web/download.txt | 7 | ||||
-rwxr-xr-x | web/news.txt | 5 |
24 files changed, 630 insertions, 358 deletions
diff --git a/compiler/ast.nim b/compiler/ast.nim index 76260b586..65d7bccf1 100755 --- a/compiler/ast.nim +++ b/compiler/ast.nim @@ -189,7 +189,8 @@ type nkProcTy, # proc type nkEnumTy, # enum body nkEnumFieldDef, # `ident = expr` in an enumeration - nkReturnToken # token used for interpretation + nkReturnToken, # token used for interpretation + nkClosure # (prc, env)-pair (internally used for code gen) TNodeKinds* = set[TNodeKind] type @@ -220,7 +221,7 @@ type sfDiscriminant, # field is a discriminant in a record/object sfDeprecated, # symbol is deprecated sfError, # usage of symbol should trigger a compile-time error - sfInClosure, # variable is accessed by a closure + sfInnerProc, # proc is an inner proc sfThread, # proc will run as a thread # variable is a thread variable sfCompileTime, # proc can be evaluated at compile time @@ -976,6 +977,14 @@ proc hasSonWith(n: PNode, kind: TNodeKind): bool = return true result = false +proc containsNode*(n: PNode, kinds: TNodeKinds): bool = + if n == nil: return + case n.kind + of nkEmpty..nkNilLit: result = n.kind in kinds + else: + for i in countup(0, sonsLen(n) - 1): + if n.kind in kinds or containsNode(n.sons[i], kinds): return true + proc hasSubnodeWith(n: PNode, kind: TNodeKind): bool = case n.kind of nkEmpty..nkNilLit: result = n.kind == kind @@ -1030,3 +1039,10 @@ proc isGenericRoutine*(s: PSym): bool = result = s.ast != nil and s.ast[genericParamsPos].kind != nkEmpty else: nil +proc isRoutine*(s: PSym): bool {.inline.} = + result = s.kind in {skProc, skTemplate, skMacro, skIterator, skMethod, + skConverter} + +iterator items*(n: PNode): PNode = + for i in 0.. <n.len: yield n.sons[i] + diff --git a/compiler/ccgcalls.nim b/compiler/ccgcalls.nim index b468c4dee..d6e2d67b7 100644 --- a/compiler/ccgcalls.nim +++ b/compiler/ccgcalls.nim @@ -48,7 +48,7 @@ proc fixupCall(p: BProc, le, ri: PNode, d: var TLoc, pl: PRope) = if d.k == locNone: getTemp(p, typ.sons[0], d) assert(d.t != nil) # generate an assignment to d: var list: TLoc - initLoc(list, locCall, nil, OnUnknown) + initLoc(list, locCall, d.t, OnUnknown) list.r = pl genAssignment(p, d, list, {}) # no need for deep copying else: @@ -137,6 +137,67 @@ proc genPrefixCall(p: BProc, le, ri: PNode, d: var TLoc) = if i < length - 1: app(pl, ", ") fixupCall(p, le, ri, d, pl) +proc genClosureCall(p: BProc, le, ri: PNode, d: var TLoc) = + + proc getRawProcType(p: BProc, t: PType): PRope = + var d = copyType(t, t.owner, false) + d.callConv = ccDefault + result = getTypeDesc(p.module, d) + + proc addComma(r: PRope): PRope = + result = if r == nil: r else: con(r, ", ") + + const CallPattern = "$1.ClEnv? $1.ClPrc($3$1.ClEnv) : (($4)($1.ClPrc))($2)" + var op: TLoc + initLocExpr(p, ri.sons[0], op) + var pl: PRope + var typ = ri.sons[0].typ + assert(typ.kind == tyProc) + var length = sonsLen(ri) + for i in countup(1, length - 1): + assert(sonsLen(typ) == sonsLen(typ.n)) + if i < sonsLen(typ): + assert(typ.n.sons[i].kind == nkSym) + app(pl, genArg(p, ri.sons[i], typ.n.sons[i].sym)) + else: + app(pl, genArgNoParam(p, ri.sons[i])) + if i < length - 1: app(pl, ", ") + + template genCallPattern = + appf(p.s[cpsStmts], CallPattern, op.r, pl, pl.addComma, rawProc) + + let rawProc = getRawProcType(p, typ) + if typ.sons[0] != nil: + if isInvalidReturnType(typ.sons[0]): + if sonsLen(ri) > 1: app(pl, ", ") + # beware of 'result = p(result)'. We may need to allocate a temporary: + if d.k in {locTemp, locNone} or not leftAppearsOnRightSide(le, ri): + # Great, we can use 'd': + if d.k == locNone: getTemp(p, typ.sons[0], d) + elif d.k notin {locExpr, locTemp} and not hasNoInit(ri): + # reset before pass as 'result' var: + resetLoc(p, d) + app(pl, addrLoc(d)) + genCallPattern() + appf(p.s[cpsStmts], ";$n") + else: + var tmp: TLoc + getTemp(p, typ.sons[0], tmp) + app(pl, addrLoc(tmp)) + genCallPattern() + appf(p.s[cpsStmts], ";$n") + genAssignment(p, d, tmp, {}) # no need for deep copying + else: + if d.k == locNone: getTemp(p, typ.sons[0], d) + assert(d.t != nil) # generate an assignment to d: + var list: TLoc + initLoc(list, locCall, d.t, OnUnknown) + list.r = ropef(CallPattern, op.r, pl, pl.addComma, rawProc) + genAssignment(p, d, list, {}) # no need for deep copying + else: + genCallPattern() + appf(p.s[cpsStmts], ";$n") + proc genInfixCall(p: BProc, le, ri: PNode, d: var TLoc) = var op, a: TLoc initLocExpr(p, ri.sons[0], op) @@ -224,7 +285,9 @@ proc genNamedParamCall(p: BProc, ri: PNode, d: var TLoc) = appf(p.s[cpsStmts], ";$n") proc genCall(p: BProc, e: PNode, d: var TLoc) = - if e.sons[0].kind == nkSym and sfInfixCall in e.sons[0].sym.flags and + if e.sons[0].typ.callConv == ccClosure: + genClosureCall(p, nil, e, d) + elif e.sons[0].kind == nkSym and sfInfixCall in e.sons[0].sym.flags and e.len >= 2: genInfixCall(p, nil, e, d) elif e.sons[0].kind == nkSym and sfNamedParamCall in e.sons[0].sym.flags: @@ -235,7 +298,9 @@ proc genCall(p: BProc, e: PNode, d: var TLoc) = if d.s == onStack and containsGarbageCollectedRef(d.t): keepAlive(p, d) proc genAsgnCall(p: BProc, le, ri: PNode, d: var TLoc) = - if ri.sons[0].kind == nkSym and sfInfixCall in ri.sons[0].sym.flags and + if ri.sons[0].typ.callConv == ccClosure: + genClosureCall(p, le, ri, d) + elif ri.sons[0].kind == nkSym and sfInfixCall in ri.sons[0].sym.flags and ri.len >= 2: genInfixCall(p, le, ri, d) elif ri.sons[0].kind == nkSym and sfNamedParamCall in ri.sons[0].sym.flags: diff --git a/compiler/ccgexprs.nim b/compiler/ccgexprs.nim index ef412d753..6a8156220 100755 --- a/compiler/ccgexprs.nim +++ b/compiler/ccgexprs.nim @@ -244,7 +244,7 @@ proc genAssignment(p: BProc, dest, src: TLoc, flags: TAssignmentFlags) = appcg(p, cpsStmts, "#unsureAsgnRef((void**) $1, #copyString($2));$n", [addrLoc(dest), rdLoc(src)]) if needToKeepAlive in flags: keepAlive(p, dest) - of tyTuple, tyObject: + of tyTuple, tyObject, tyProc: # XXX: check for subtyping? if needsComplexAssignment(dest.t): genGenericAsgn(p, dest, src, flags) @@ -274,7 +274,7 @@ proc genAssignment(p: BProc, dest, src: TLoc, flags: TAssignmentFlags) = [rdLoc(dest), rdLoc(src), toRope(getSize(dest.t))]) else: appcg(p, cpsStmts, "$1 = $2;$n", [rdLoc(dest), rdLoc(src)]) - of tyPtr, tyPointer, tyChar, tyBool, tyProc, tyEnum, tyCString, + of tyPtr, tyPointer, tyChar, tyBool, tyEnum, tyCString, tyInt..tyFloat128, tyRange: appcg(p, cpsStmts, "$1 = $2;$n", [rdLoc(dest), rdLoc(src)]) else: InternalError("genAssignment(" & $ty.kind & ')') @@ -1308,7 +1308,6 @@ proc convStrToCStr(p: BProc, n: PNode, d: var TLoc) = [rdLoc(a)])) proc convCStrToStr(p: BProc, n: PNode, d: var TLoc) = - # XXX we don't generate keep alive info here var a: TLoc initLocExpr(p, n.sons[0], a) putIntoDest(p, d, skipTypes(n.typ, abstractVar), @@ -1515,6 +1514,28 @@ proc genTupleConstr(p: BProc, n: PNode, d: var TLoc) = [rdLoc(d), mangleRecFieldName(t.n.sons[i].sym, t)]) expr(p, it, rec) +proc IsConstClosure(n: PNode): bool {.inline.} = + result = n.sons[0].kind == nkSym and isRoutine(n.sons[0].sym) and + n.sons[1].kind == nkNilLit + +proc genClosure(p: BProc, n: PNode, d: var TLoc) = + assert n.kind == nkClosure + + if IsConstClosure(n): + inc(p.labels) + var tmp = con("LOC", toRope(p.labels)) + appf(p.module.s[cfsData], "NIM_CONST $1 $2 = $3;$n", + [getTypeDesc(p.module, n.typ), tmp, genConstExpr(p, n)]) + putIntoDest(p, d, n.typ, tmp) + else: + var tmp, a, b: TLoc + initLocExpr(p, n.sons[0], a) + initLocExpr(p, n.sons[1], b) + getTemp(p, n.typ, tmp) + appcg(p, cpsStmts, "$1.ClPrc = $2; $1.ClEnv = $3;$n", + tmp.rdLoc, a.rdLoc, b.rdLoc) + putLocIntoDest(p, d, tmp) + proc genArrayConstr(p: BProc, n: PNode, d: var TLoc) = var arr: TLoc if not handleConstExpr(p, n, d): @@ -1705,6 +1726,7 @@ proc expr(p: BProc, e: PNode, d: var TLoc) = if sym.loc.r == nil or sym.loc.t == nil: InternalError(e.info, "expr: proc not init " & sym.name.s) putLocIntoDest(p, d, sym.loc) + of nkClosure: genClosure(p, e, d) of nkMetaNode: expr(p, e.sons[0], d) else: InternalError(e.info, "expr(" & $e.kind & "); unknown node kind") @@ -1751,7 +1773,7 @@ proc genConstExpr(p: BProc, n: PNode): PRope = var cs: TBitSet toBitSet(n, cs) result = genRawSetData(cs, int(getSize(n.typ))) - of nkBracket, nkPar: + of nkBracket, nkPar, nkClosure: var t = skipTypes(n.typ, abstractInst) if t.kind == tySequence: result = genConstSeq(p, n, t) diff --git a/compiler/ccgstmts.nim b/compiler/ccgstmts.nim index ad1b5646f..8e7b05c0f 100755 --- a/compiler/ccgstmts.nim +++ b/compiler/ccgstmts.nim @@ -57,13 +57,24 @@ proc genSingleVar(p: BProc, a: PNode) = genLineDir(p, a) loadInto(p, a.sons[0], a.sons[2], v.loc) +proc genClosureVar(p: BProc, a: PNode) = + var immediateAsgn = a.sons[2].kind != nkEmpty + if immediateAsgn: + var v: TLoc + initLocExpr(p, a.sons[0], v) + genLineDir(p, a) + loadInto(p, a.sons[0], a.sons[2], v) + proc genVarStmt(p: BProc, n: PNode) = for i in countup(0, sonsLen(n) - 1): var a = n.sons[i] if a.kind == nkCommentStmt: continue - if a.kind == nkIdentDefs: - assert(a.sons[0].kind == nkSym) - genSingleVar(p, a) + if a.kind == nkIdentDefs: + # can be a lifted var nowadays ... + if a.sons[0].kind == nkSym: + genSingleVar(p, a) + else: + genClosureVar(p, a) else: genVarTuple(p, a) @@ -704,7 +715,7 @@ proc genStmts(p: BProc, t: PNode) = of nkReturnStmt: genReturnStmt(p, t) of nkBreakStmt: genBreakStmt(p, t) of nkCall, nkHiddenCallConv, nkInfix, nkPrefix, nkPostfix, nkCommand, - nkCallStrLit: + nkCallStrLit, nkClosure: genLineDir(p, t) initLocExpr(p, t, a) of nkAsgn: genAsgn(p, t, fastAsgn=false) diff --git a/compiler/ccgtypes.nim b/compiler/ccgtypes.nim index a2faf3cbf..c7002954a 100755 --- a/compiler/ccgtypes.nim +++ b/compiler/ccgtypes.nim @@ -94,7 +94,7 @@ proc mapType(typ: PType): TCTypeKind = else: result = ctPtr of tyPointer: result = ctPtr of tySequence: result = ctNimSeq - of tyProc: result = ctProc + of tyProc: result = if typ.callConv != ccClosure: ctProc else: ctStruct of tyString: result = ctNimStr of tyCString: result = ctCString of tyInt..tyFloat128: @@ -215,7 +215,7 @@ proc genProcParams(m: BModule, t: PType, rettype, params: var PRope, appff(params, " Result", " @Result", []) if t.callConv == ccClosure: if params != nil: app(params, ", ") - app(params, "void* ClPart") + app(params, "void* ClEnv") if tfVarargs in t.flags: if params != nil: app(params, ", ") app(params, "...") @@ -331,7 +331,7 @@ proc genRecordFieldsAux(m: BModule, n: PNode, appf(result, "} $1;$n", [uname]) of nkSym: field = n.sym - assert(field.ast == nil) + #assert(field.ast == nil) sname = mangleRecFieldName(field, rectype) if accessExpr != nil: ae = ropef("$1.$2", [accessExpr, sname]) else: ae = sname @@ -436,9 +436,10 @@ proc getTypeDescAux(m: BModule, typ: PType, check: var TIntSet): PRope = if t.callConv != ccClosure: # procedure vars may need a closure! appf(m.s[cfsTypes], "typedef $1_PTR($2, $3) $4;$n", [toRope(CallingConvToStr[t.callConv]), rettype, result, desc]) - else: - appf(m.s[cfsTypes], "typedef struct $1 {$n" & - "N_CDECL_PTR($2, PrcPart) $3;$n" & "void* ClPart;$n};$n", + else: + appf(m.s[cfsTypes], "typedef struct {$n" & + "N_CDECL_PTR($2, ClPrc) $3;$n" & + "void* ClEnv;$n} $1;$n", [result, rettype, desc]) of tySequence: # we cannot use getTypeForward here because then t would be associated @@ -673,7 +674,8 @@ proc genTupleInfo(m: BModule, typ: PType, name: PRope) = var tmp2 = getNimNode(m) appf(m.s[cfsTypeInit3], "$1[$2] = &$3;$n", [tmp, toRope(i), tmp2]) appf(m.s[cfsTypeInit3], "$1.kind = 1;$n" & - "$1.offset = offsetof($2, Field$3);$n" & "$1.typ = $4;$n" & + "$1.offset = offsetof($2, Field$3);$n" & + "$1.typ = $4;$n" & "$1.name = \"Field$3\";$n", [tmp2, getTypeDesc(m, typ), toRope(i), genTypeInfo(m, a)]) appf(m.s[cfsTypeInit3], "$1.len = $2; $1.kind = 2; $1.sons = &$3[0];$n", @@ -736,6 +738,14 @@ proc genSetInfo(m: BModule, typ: PType, name: PRope) = proc genArrayInfo(m: BModule, typ: PType, name: PRope) = genTypeInfoAuxBase(m, typ, name, genTypeInfo(m, typ.sons[1])) +proc fakeClosureType(owner: PSym): PType = + # we generate the same RTTI as for a tuple[pointer, ref tuple[]] + result = newType(tyTuple, owner) + result.addSon(newType(tyPointer, owner)) + var r = newType(tyRef, owner) + r.addSon(newType(tyTuple, owner)) + result.addSon(r) + proc genTypeInfo(m: BModule, typ: PType): PRope = var t = getUniqueType(typ) # gNimDat contains all the type information nowadays: @@ -750,9 +760,13 @@ proc genTypeInfo(m: BModule, typ: PType): PRope = if dataGenerated: return case t.kind of tyEmpty: result = toRope"0" - of tyPointer, tyProc, tyBool, tyChar, tyCString, tyString, tyInt..tyFloat128, - tyVar: + of tyPointer, tyBool, tyChar, tyCString, tyString, tyInt..tyFloat128, tyVar: genTypeInfoAuxBase(gNimDat, t, result, toRope"0") + of tyProc: + if t.callConv != ccClosure: + genTypeInfoAuxBase(gNimDat, t, result, toRope"0") + else: + genTupleInfo(gNimDat, fakeClosureType(t.owner), result) of tyRef, tyPtr, tySequence, tyRange: genTypeInfoAux(gNimDat, t, result) of tyArrayConstr, tyArray: genArrayInfo(gNimDat, t, result) of tySet: genSetInfo(gNimDat, t, result) diff --git a/compiler/cgen.nim b/compiler/cgen.nim index d60f11639..9784b21bb 100755 --- a/compiler/cgen.nim +++ b/compiler/cgen.nim @@ -75,8 +75,10 @@ proc fillLoc(a: var TLoc, k: TLocKind, typ: PType, r: PRope, s: TStorageLoc) = if a.r == nil: a.r = r proc isSimpleConst(typ: PType): bool = - result = skipTypes(typ, abstractVar).kind notin - {tyTuple, tyObject, tyArray, tyArrayConstr, tySet, tySequence} + let t = skipTypes(typ, abstractVar) + result = t.kind notin + {tyTuple, tyObject, tyArray, tyArrayConstr, tySet, tySequence} and not + (t.kind == tyProc and t.callConv == ccClosure) proc useHeader(m: BModule, sym: PSym) = if lfHeader in sym.loc.Flags: @@ -187,7 +189,7 @@ proc rdLoc(a: TLoc): PRope = proc addrLoc(a: TLoc): PRope = result = a.r - if lfIndirect notin a.flags and mapType(a.t) != ctArray: + if lfIndirect notin a.flags and mapType(a.t) != ctArray: result = con("&", result) proc rdCharLoc(a: TLoc): PRope = @@ -196,7 +198,7 @@ proc rdCharLoc(a: TLoc): PRope = if skipTypes(a.t, abstractRange).kind == tyChar: result = ropef("((NU8)($1))", [result]) -proc genObjectInit(p: BProc, section: TCProcSection, t: PType, a: TLoc, +proc genObjectInit(p: BProc, section: TCProcSection, t: PType, a: TLoc, takeAddr: bool) = case analyseObjectWithTypeField(t) of frNone: @@ -223,11 +225,12 @@ type proc genRefAssign(p: BProc, dest, src: TLoc, flags: TAssignmentFlags) -const - complexValueType = {tyArray, tyArrayConstr, tySet, tyTuple, tyObject} +proc isComplexValueType(t: PType): bool {.inline.} = + result = t.kind in {tyArray, tyArrayConstr, tySet, tyTuple, tyObject} or + (t.kind == tyProc and t.callConv == ccClosure) proc zeroVar(p: BProc, loc: TLoc, containsGCref: bool) = - if skipTypes(loc.t, abstractVarRange).Kind notin ComplexValueType: + if not isComplexValueType(skipTypes(loc.t, abstractVarRange)): if containsGcref and p.WithInLoop > 0: appf(p.s[cpsInit], "$1 = 0;$n", [rdLoc(loc)]) var nilLoc: TLoc @@ -249,8 +252,8 @@ proc zeroVar(p: BProc, loc: TLoc, containsGCref: bool) = [addrLoc(loc), rdLoc(loc)]) genObjectInit(p, cpsStmts, loc.t, loc, true) -proc zeroTemp(p: BProc, loc: TLoc) = - if skipTypes(loc.t, abstractVarRange).Kind notin complexValueType: +proc zeroTemp(p: BProc, loc: TLoc) = + if not isComplexValueType(skipTypes(loc.t, abstractVarRange)): appf(p.s[cpsStmts], "$1 = 0;$n", [rdLoc(loc)]) when false: var nilLoc: TLoc @@ -313,7 +316,7 @@ proc keepAlive(p: BProc, toKeepAlive: TLoc) = result.s = OnStack result.flags = {} - if skipTypes(toKeepAlive.t, abstractVarRange).Kind notin complexValueType: + if not isComplexValueType(skipTypes(toKeepAlive.t, abstractVarRange)): appf(p.s[cpsStmts], "$1 = $2;$n", [rdLoc(result), rdLoc(toKeepAlive)]) else: appcg(p, cpsStmts, @@ -571,6 +574,15 @@ proc initFrame(p: BProc, procname, filename: PRope): PRope = proc deinitFrame(p: BProc): PRope = result = ropecg(p.module, "#popFrame();$n") +proc closureSetup(p: BProc, prc: PSym) = + if prc.typ.callConv != ccClosure: return + # prc.ast[paramsPos].last contains the type we're after: + var env = lastSon(prc.ast[paramsPos]).sym + assignLocalVar(p, env) + # generate cast assignment: + appcg(p, cpsStmts, "$1 = ($2) ClEnv;$n", rdLoc(env.loc), + getTypeDesc(p.module, env.typ)) + proc genProcAux(m: BModule, prc: PSym) = var p = newProc(prc, m) var header = genProcHeader(m, prc) @@ -594,6 +606,7 @@ proc genProcAux(m: BModule, prc: PSym) = for i in countup(1, sonsLen(prc.typ.n) - 1): var param = prc.typ.n.sons[i].sym assignParam(p, param) + closureSetup(p, prc) genStmts(p, prc.getBody) # modifies p.locals, p.init, etc. var generatedProc: PRope if sfPure in prc.flags: diff --git a/compiler/lambdalifting.nim b/compiler/lambdalifting.nim new file mode 100644 index 000000000..4a2a8997c --- /dev/null +++ b/compiler/lambdalifting.nim @@ -0,0 +1,232 @@ +# +# +# The Nimrod Compiler +# (c) Copyright 2012 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +# This include file implements lambda lifting for the transformator. + +const + procDefs = {nkLambda, nkProcDef, nkMethodDef, nkIteratorDef, nkMacroDef, + nkConverterDef} + +proc indirectAccess(a, b: PSym, info: TLineInfo): PNode = + # returns a[].b as a node + let x = newSymNode(a) + var deref = newNodeI(nkHiddenDeref, info) + deref.typ = x.typ.sons[0] + + let field = getSymFromList(deref.typ.n, b.name) + addSon(deref, x) + result = newNodeI(nkDotExpr, info) + addSon(result, deref) + addSon(result, newSymNode(field)) + result.typ = field.typ + +type + TCapture = seq[PSym] + +proc Capture(cap: var TCapture, s: PSym) = + for x in cap: + if x.name.id == s.name.id: return + cap.add(s) + +proc captureToTuple(cap: TCapture, owner: PSym): PType = + result = newType(tyTuple, owner) + result.n = newNodeI(nkRecList, owner.info) + for s in cap: + var field = newSym(skField, s.name, s.owner) + + let typ = s.typ + field.typ = typ + field.position = sonsLen(result) + + addSon(result.n, newSymNode(field)) + addSon(result, typ) + +proc gatherVars(c: PTransf, n: PNode, outerProc: PSym, cap: var TCapture) = + # gather used vars for closure generation into 'cap' + case n.kind + of nkSym: + var s = n.sym + var found = false + case s.kind + of skVar, skLet: found = sfGlobal notin s.flags + of skTemp, skForVar, skParam, skResult: found = true + else: nil + if found and outerProc.id == s.owner.id: + #echo "captured: ", s.name.s + Capture(cap, s) + of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: nil + else: + for i in countup(0, sonsLen(n) - 1): + gatherVars(c, n.sons[i], outerProc, cap) + +proc replaceVars(c: PTransf, n: PNode, outerProc, env: PSym) = + for i in countup(0, safeLen(n) - 1): + let a = n.sons[i] + if a.kind == nkSym: + let s = a.sym + var found = false + case s.kind + of skVar, skLet: found = sfGlobal notin s.flags + of skTemp, skForVar, skParam, skResult: found = true + else: nil + if found and outerProc.id == s.owner.id: + # access through the closure param: + n.sons[i] = indirectAccess(env, s, n.info) + else: + replaceVars(c, a, outerProc, env) + +proc addFormalParam(routine: PType, param: PSym) = + addSon(routine, param.typ) + addSon(routine.n, newSymNode(param)) + +proc addFormalParam(routine: PSym, param: PSym) = + #addFormalParam(routine.typ, param) + addSon(routine.ast.sons[paramsPos], newSymNode(param)) + +proc isInnerProc(s, outerProc: PSym): bool {.inline.} = + result = s.kind in {skProc, skMacro, skIterator, skMethod, skConverter} and + s.owner.id == outerProc.id and not isGenericRoutine(s) and + s.typ.callConv == ccClosure + +proc searchForInnerProcs(c: PTransf, n: PNode, outerProc: PSym, + cap: var TCapture) = + case n.kind + of nkSym: + let s = n.sym + if isInnerProc(s, outerProc): + gatherVars(c, s.getBody, outerProc, cap) + of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: nil + else: + for i in 0.. <len(n): + searchForInnerProcs(c, n.sons[i], outerProc, cap) + +proc makeClosure(c: PTransf, prc, env: PSym, info: TLineInfo): PNode = + result = newNodeIT(nkClosure, info, prc.typ) + result.add(newSymNode(prc)) + result.add(newSymNode(env)) + +proc transformInnerProcs(c: PTransf, n: PNode, outerProc, env: PSym) = + case n.kind + of nkSym: + let innerProc = n.sym + if isInnerProc(innerProc, outerProc): + # inner proc could capture outer vars: + var param = newTemp(c, env.typ, n.info) + param.kind = skParam + addFormalParam(innerProc, param) + # 'anon' should be replaced by '(anon, env)': + IdNodeTablePut(c.transCon.mapping, innerProc, + makeClosure(c, innerProc, env, n.info)) + # access all non-local vars through the 'env' param: + var body = innerProc.getBody + # XXX does not work with recursion! + replaceVars(c, body, outerProc, param) + innerProc.ast.sons[bodyPos] = body + of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: nil + else: + for i in 0.. <len(n): + transformInnerProcs(c, n.sons[i], outerProc, env) + +proc newCall(a, b: PSym): PNode = + result = newNodeI(nkCall, a.info) + result.add newSymNode(a) + result.add newSymNode(b) + +proc createEnvStmt(c: PTransf, varList: TCapture, env: PSym): PTransNode = + # 'varlist' can contain parameters or variables. We don't eliminate yet + # local vars that end up in an environment. This could even be a for loop + # var! + result = newTransNode(nkStmtList, env.info, 0) + var v = newNodeI(nkVarSection, env.info) + addVar(v, newSymNode(env)) + result.add(v.ptransNode) + # add 'new' statement: + result.add(newCall(getSysSym"internalNew", env).ptransnode) + + # add assignment statements: + for v in varList: + let fieldAccess = indirectAccess(env, v, env.info) + if v.kind == skParam: + # add ``env.param = param`` + result.add(newAsgnStmt(c, fieldAccess, newSymNode(v).ptransNode)) + IdNodeTablePut(c.transCon.mapping, v, fieldAccess) + +proc transformProcFin(c: PTransf, n: PNode, s: PSym): PTransNode = + # to be safe: XXX this a mystery how it could ever happen that: s.ast != n. + s.ast.sons[bodyPos] = n.sons[bodyPos] + if n.kind == nkMethodDef: methodDef(s, false) + + # should 's' be replaced by a tuple ('s', env)? + var tc = c.transCon + var repl: PNode = nil + while tc != nil: + repl = IdNodeTableGet(tc.mapping, s) + if repl != nil: break + tc = tc.next + if repl != nil: + result = PTransNode(repl) + else: + result = PTransNode(n) + +proc transformProc(c: PTransf, n: PNode): PTransNode = + # don't process generics: + if n.sons[genericParamsPos].kind != nkEmpty: + return PTransNode(n) + + var s = n.sons[namePos].sym + var body = s.getBody + if body.kind == nkEmpty: + return PTransNode(n) + + if not containsNode(body, procDefs): + # fast path: no inner procs, so no closure needed: + n.sons[bodyPos] = PNode(transform(c, body)) + return transformProcFin(c, n, s) + + # create environment: + var cap: TCapture = @[] + searchForInnerProcs(c, body, s, cap) + + if cap.len == 0: + # fast path: no captured variables, so no closure needed: + n.sons[bodyPos] = PNode(transform(c, body)) + return transformProcFin(c, n, s) + + var envType = newType(tyRef, s) + addSon(envType, captureToTuple(cap, s)) + + # Currently we always do a heap allocation. A simple escape analysis + # could turn the closure into a stack allocation. Later versions might + # implement that. This would require backend changes too though. + var envSym = newTemp(c, envType, s.info) + + var newBody = createEnvStmt(c, cap, envSym) + # modify any local proc to gain a new parameter; this also creates the + # mapping entries that turn (localProc) into (localProc, env): + transformInnerProcs(c, body, s, envSym) + + # now we can transform 'body' as all rewriting entries have been created. + # Careful this transforms the inner procs too! + newBody.add(transform(c, body)) + n.sons[bodyPos] = newBody.pnode + result = transformProcFin(c, n, s) + +proc generateThunk(c: PTransf, prc: PNode, dest: PType): PNode = + ## Converts 'prc' into '(thunk, nil)' so that it's compatible with + ## a closure. + + # XXX we hack around here by generating a 'cast' instead of a proper thunk. + result = newNodeIT(nkClosure, prc.info, dest) + var conv = newNodeIT(nkHiddenStdConv, prc.info, dest) + conv.add(emptyNode) + conv.add(prc) + result.add(conv) + result.add(newNodeIT(nkNilLit, prc.info, getSysType(tyNil))) + + diff --git a/compiler/msgs.nim b/compiler/msgs.nim index e1deb6e35..43ab7a192 100755 --- a/compiler/msgs.nim +++ b/compiler/msgs.nim @@ -93,7 +93,7 @@ type errAssertionFailed, errCannotGenerateCodeForX, errXRequiresOneArgument, errUnhandledExceptionX, errCyclicTree, errXisNoMacroOrTemplate, errXhasSideEffects, errIteratorExpected, errLetNeedsInit, - errThreadvarCannotInit, errWrongSymbolX, + errThreadvarCannotInit, errWrongSymbolX, errIllegalCaptureX, errUser, warnCannotOpenFile, warnOctalEscape, warnXIsNeverRead, warnXmightNotBeenInit, @@ -325,6 +325,7 @@ const errLetNeedsInit: "'let' symbol requires an initialization", errThreadvarCannotInit: "a thread var cannot be initialized explicitly", errWrongSymbolX: "usage of \'$1\' is a user-defined error", + errIllegalCaptureX: "illegal capture '$1'", errUser: "$1", warnCannotOpenFile: "cannot open \'$1\' [CannotOpenFile]", warnOctalEscape: "octal escape sequences do not exist; leading zero is ignored [OctalEscape]", diff --git a/compiler/renderer.nim b/compiler/renderer.nim index 6fb5da2a9..dd62363e1 100755 --- a/compiler/renderer.nim +++ b/compiler/renderer.nim @@ -339,7 +339,7 @@ proc lsub(n: PNode): int = of nkHiddenAddr, nkHiddenDeref: result = lsub(n.sons[0]) of nkCommand: result = lsub(n.sons[0]) + lcomma(n, 1) + 1 of nkExprEqExpr, nkAsgn, nkFastAsgn: result = lsons(n) + 3 - of nkPar, nkCurly, nkBracket: result = lcomma(n) + 2 + of nkPar, nkCurly, nkBracket, nkClosure: result = lcomma(n) + 2 of nkTableConstr: result = if n.len > 0: lcomma(n) + 2 else: len("{:}") of nkSymChoice: result = lsons(n) + len("()") + sonsLen(n) - 1 @@ -759,7 +759,7 @@ proc gsub(g: var TSrcGen, n: PNode, c: TContext) = if i > 0: put(g, tkOpr, "|") gsub(g, n.sons[i], c) put(g, tkParRi, ")") - of nkPar: + of nkPar, nkClosure: put(g, tkParLe, "(") gcomma(g, n, c) put(g, tkParRi, ")") diff --git a/compiler/semexprs.nim b/compiler/semexprs.nim index 32244af85..24161e85e 100755 --- a/compiler/semexprs.nim +++ b/compiler/semexprs.nim @@ -50,6 +50,10 @@ proc inlineConst(n: PNode, s: PSym): PNode {.inline.} = result.typ = s.typ result.info = n.info +proc illegalCapture(s: PSym): bool {.inline.} = + result = skipTypes(s.typ, abstractInst).kind in {tyVar, tyOpenArray} or + s.kind == skResult + proc semSym(c: PContext, n: PNode, s: PSym, flags: TExprFlags): PNode = case s.kind of skProc, skMethod, skIterator, skConverter: @@ -83,10 +87,16 @@ proc semSym(c: PContext, n: PNode, s: PSym, flags: TExprFlags): PNode = result = newSymNode(s, n.info) of skMacro: result = semMacroExpr(c, n, s) of skTemplate: result = semTemplateExpr(c, n, s) - of skVar, skLet, skResult: + of skVar, skLet, skResult, skParam: markUsed(n, s) # if a proc accesses a global variable, it is not side effect free: - if sfGlobal in s.flags: incl(c.p.owner.flags, sfSideEffect) + if sfGlobal in s.flags: + incl(c.p.owner.flags, sfSideEffect) + elif s.owner != c.p.owner and s.owner.kind != skModule: + c.p.owner.typ.callConv = ccClosure + if illegalCapture(s) or c.p.next.owner != s.owner: + # Currently captures are restricted to a single level of nesting: + GlobalError(n.info, errIllegalCaptureX, s.name.s) result = newSymNode(s, n.info) of skGenericParam: if s.ast == nil: InternalError(n.info, "no default for") diff --git a/compiler/semstmts.nim b/compiler/semstmts.nim index ab8081031..424950056 100755 --- a/compiler/semstmts.nim +++ b/compiler/semstmts.nim @@ -644,8 +644,6 @@ proc semLambda(c: PContext, n: PNode): PNode = else: s.typ = newTypeS(tyProc, c) addSon(s.typ, nil) - # no! do a proper analysis to determine calling convention - when false: s.typ.callConv = ccClosure if n.sons[pragmasPos].kind != nkEmpty: pragma(c, s, n.sons[pragmasPos], lambdaPragmas) s.options = gOptions @@ -697,9 +695,6 @@ proc semProcAux(c: PContext, n: PNode, kind: TSymKind, # open for parameters if proto == nil: s.typ.callConv = lastOptionEntry(c).defaultCC - when false: - # do a proper analysis here: - if c.p.owner.kind != skModule: s.typ.callConv = ccClosure # add it here, so that recursive procs are possible: # -2 because we have a scope open for parameters if kind in OverloadableSyms: diff --git a/compiler/semthreads.nim b/compiler/semthreads.nim index 59ff4e652..f542e04d6 100755 --- a/compiler/semthreads.nim +++ b/compiler/semthreads.nim @@ -360,7 +360,7 @@ proc analyse(c: PProcCtx, n: PNode): TThreadOwner = if n.sons[0].kind != nkEmpty: result = analyse(c, n.sons[0]) else: result = toVoid of nkAsmStmt, nkPragma, nkIteratorDef, nkProcDef, nkMethodDef, - nkConverterDef, nkMacroDef, nkTemplateDef: + nkConverterDef, nkMacroDef, nkTemplateDef, nkLambda: result = toVoid of nkExprColonExpr: result = analyse(c, n.sons[1]) diff --git a/compiler/sigmatch.nim b/compiler/sigmatch.nim index 04278ba87..c21dc3c6e 100755 --- a/compiler/sigmatch.nim +++ b/compiler/sigmatch.nim @@ -212,8 +212,8 @@ proc procTypeRel(mapping: var TIdTable, f, a: PType): TTypeRelation = case a.kind of tyNil: result = isSubtype - of tyProc: - if sonsLen(f) != sonsLen(a) or f.callconv != a.callconv: return + of tyProc: + if sonsLen(f) != sonsLen(a): return # Note: We have to do unification for the parameters before the # return type! result = isEqual # start with maximum; also correct for no @@ -240,6 +240,12 @@ proc procTypeRel(mapping: var TIdTable, f, a: PType): TTypeRelation = elif tfThread in f.flags and a.flags * {tfThread, tfNoSideEffect} == {}: # noSideEffect implies ``tfThread``! XXX really? result = isNone + elif f.callconv != a.callconv: + # valid to pass a 'nimcall' thingie to 'closure': + if f.callconv == ccClosure and a.callconv == ccDefault: + result = isConvertible + else: + result = isNone else: nil proc typeRel(mapping: var TIdTable, f, a: PType): TTypeRelation = diff --git a/compiler/transf.nim b/compiler/transf.nim index 12117f62a..be8f7aeb5 100755 --- a/compiler/transf.nim +++ b/compiler/transf.nim @@ -15,6 +15,7 @@ # * performes contant folding # * converts "continue" to "break" # * introduces method dispatchers +# * performs lambda lifting for closure support import intsets, strutils, lists, options, ast, astalgo, trees, treetab, msgs, os, @@ -45,7 +46,8 @@ type transCon: PTransCon # top of a TransCon stack inlining: int # > 0 if we are in inlining context (copy vars) blocksyms: seq[PSym] - + procToEnv: TIdTable # mapping from a proc to its generated explicit + # 'env' var (for closure generation) PTransf = ref TTransfContext proc newTransNode(a: PNode): PTransNode {.inline.} = @@ -354,6 +356,8 @@ proc transformAddrDeref(c: PTransf, n: PNode, a, b: TNodeKind): PTransNode = if n.sons[0].kind == a or n.sons[0].kind == b: # addr ( deref ( x )) --> x result = PTransNode(n.sons[0].sons[0]) + +include lambdalifting proc transformConv(c: PTransf, n: PNode): PTransNode = # numeric types need range checks: @@ -427,6 +431,11 @@ proc transformConv(c: PTransf, n: PNode): PTransNode = result[0] = transform(c, n.sons[1]) else: result = transform(c, n.sons[1]) + of tyProc: + if dest.callConv == ccClosure and source.callConv == ccDefault: + result = generateThunk(c, n.sons[1], dest).ptransnode + else: + result = transformSons(c, n) of tyGenericParam, tyOrdinal: result = transform(c, n.sons[1]) # happens sometimes for generated assignments, etc. @@ -502,77 +511,12 @@ proc transformFor(c: PTransf, n: PNode): PTransNode = popTransCon(c) #echo "transformed: ", renderTree(n) - proc getMagicOp(call: PNode): TMagic = if call.sons[0].kind == nkSym and call.sons[0].sym.kind in {skProc, skMethod, skConverter}: result = call.sons[0].sym.magic else: result = mNone - -proc gatherVars(c: PTransf, n: PNode, marked: var TIntSet, owner: PSym, - container: PNode) = - # gather used vars for closure generation - case n.kind - of nkSym: - var s = n.sym - var found = false - case s.kind - of skVar, skLet: found = sfGlobal notin s.flags - of skTemp, skForVar, skParam, skResult: found = true - else: nil - if found and owner.id != s.owner.id and not ContainsOrIncl(marked, s.id): - incl(s.flags, sfInClosure) - addSon(container, copyNode(n)) # DON'T make a copy of the symbol! - of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: - nil - else: - for i in countup(0, sonsLen(n) - 1): - gatherVars(c, n.sons[i], marked, owner, container) - -proc addFormalParam(routine: PSym, param: PSym) = - addSon(routine.typ, param.typ) - addSon(routine.ast.sons[paramsPos], newSymNode(param)) - -proc indirectAccess(a, b: PSym): PNode = - # returns a[].b as a node - var x = newSymNode(a) - var y = newSymNode(b) - var deref = newNodeI(nkHiddenDeref, x.info) - deref.typ = x.typ.sons[0] - addSon(deref, x) - result = newNodeI(nkDotExpr, x.info) - addSon(result, deref) - addSon(result, y) - result.typ = y.typ - -proc transformLambda(c: PTransf, n: PNode): PNode = - var marked = initIntSet() - result = n - if n.sons[namePos].kind != nkSym: InternalError(n.info, "transformLambda") - var s = n.sons[namePos].sym - var closure = newNodeI(nkRecList, n.info) - var body = s.getBody - gatherVars(c, body, marked, s, closure) - # add closure type to the param list (even if closure is empty!): - var cl = newType(tyObject, s) - cl.n = closure - addSon(cl, nil) # no super class - var p = newType(tyRef, s) - addSon(p, cl) - var param = newSym(skParam, getIdent(genPrefix & "Cl"), s) - param.typ = p - addFormalParam(s, param) - # all variables that are accessed should be accessed by the new closure - # parameter: - if sonsLen(closure) > 0: - var newC = newTransCon(c.transCon.owner) - for i in countup(0, sonsLen(closure) - 1): - IdNodeTablePut(newC.mapping, closure.sons[i].sym, - indirectAccess(param, closure.sons[i].sym)) - pushTransCon(c, newC) - n.sons[bodyPos] = transform(c, body).pnode - popTransCon(c) proc transformCase(c: PTransf, n: PNode): PTransNode = # removes `elif` branches of a case stmt @@ -670,23 +614,10 @@ proc transform(c: PTransf, n: PNode): PTransNode = of nkEmpty..pred(nkSym), succ(nkSym)..nkNilLit: # nothing to be done for leaves: result = PTransNode(n) - of nkBracketExpr: - result = transformArrayAccess(c, n) - of nkLambda: - var s = n.sons[namePos].sym - n.sons[bodyPos] = PNode(transform(c, s.getBody)) - result = PTransNode(n) - when false: result = transformLambda(c, n) - of nkForStmt: - result = transformFor(c, n) - of nkCaseStmt: - result = transformCase(c, n) - of nkProcDef, nkMethodDef, nkIteratorDef, nkMacroDef, nkConverterDef: - if n.sons[genericParamsPos].kind == nkEmpty: - var s = n.sons[namePos].sym - n.sons[bodyPos] = PNode(transform(c, s.getBody)) - if n.kind == nkMethodDef: methodDef(s, false) - result = PTransNode(n) + of nkBracketExpr: result = transformArrayAccess(c, n) + of procDefs: result = transformProc(c, n) + of nkForStmt: result = transformFor(c, n) + of nkCaseStmt: result = transformCase(c, n) of nkContinueStmt: result = PTransNode(newNode(nkBreakStmt)) var labl = c.blockSyms[c.blockSyms.high] @@ -748,6 +679,7 @@ proc openTransf(module: PSym, filename: string): PPassContext = new(n) n.blocksyms = @[] n.module = module + initIdTable(n.procToEnv) result = n proc openTransfCached(module: PSym, filename: string, diff --git a/compiler/trees.nim b/compiler/trees.nim index f393bfc66..57acfba8a 100755 --- a/compiler/trees.nim +++ b/compiler/trees.nim @@ -115,7 +115,7 @@ proc isDeepConstExpr*(n: PNode): bool = result = true of nkExprEqExpr, nkExprColonExpr, nkHiddenStdConv, nkHiddenSubConv: result = isDeepConstExpr(n.sons[1]) - of nkCurly, nkBracket, nkPar: + of nkCurly, nkBracket, nkPar, nkClosure: for i in 0 .. <n.len: if not isDeepConstExpr(n.sons[i]): return false result = true diff --git a/compiler/types.nim b/compiler/types.nim index 42acae831..d2359faae 100755 --- a/compiler/types.nim +++ b/compiler/types.nim @@ -276,16 +276,17 @@ proc analyseObjectWithTypeField(t: PType): TTypeFieldResult = var marker = InitIntSet() result = analyseObjectWithTypeFieldAux(t, marker) -proc isGBCRef(t: PType): bool = - result = t.kind in GcTypeKinds +proc isGCRef(t: PType): bool = + result = t.kind in GcTypeKinds or + (t.kind == tyProc and t.callConv == ccClosure) proc containsGarbageCollectedRef(typ: PType): bool = # returns true if typ contains a reference, sequence or string (all the # things that are garbage-collected) - result = searchTypeFor(typ, isGBCRef) + result = searchTypeFor(typ, isGCRef) proc isTyRef(t: PType): bool = - result = t.kind == tyRef + result = t.kind == tyRef or (t.kind == tyProc and t.callConv == ccClosure) proc containsTyRef*(typ: PType): bool = # returns true if typ contains a 'ref' @@ -332,6 +333,8 @@ proc canFormAcycleAux(marker: var TIntSet, typ: PType, startId: int): bool = nil proc canFormAcycle(typ: PType): bool = + # XXX as I expect cycles introduced by closures are very rare, we pretend + # they can't happen here. var marker = InitIntSet() result = canFormAcycleAux(marker, typ, typ.id) diff --git a/doc/gramcurl.txt b/doc/gramcurl.txt deleted file mode 100755 index 3ac9294c8..000000000 --- a/doc/gramcurl.txt +++ /dev/null @@ -1,179 +0,0 @@ -module ::= stmt* - -comma ::= ',' [COMMENT] [IND] -operator ::= OP0 | OR | XOR | AND | OP3 | OP4 | OP5 | OP6 | OP7 - | 'is' | 'isnot' | 'in' | 'notin' - | 'div' | 'mod' | 'shl' | 'shr' | 'not' - -prefixOperator ::= OP0 | OP3 | OP4 | OP5 | OP6 | OP7 | 'not' - -optInd ::= [COMMENT] [IND] - - -lowestExpr ::= orExpr (OP0 optInd orExpr)* -orExpr ::= andExpr (OR | 'xor' optInd andExpr)* -andExpr ::= cmpExpr ('and' optInd cmpExpr)* -cmpExpr ::= ampExpr (OP3 | 'is' | 'isnot' | 'in' | 'notin' optInd ampExpr)* -ampExpr ::= plusExpr (OP4 optInd plusExpr)* -plusExpr ::= mulExpr (OP5 optInd mulExpr)* -mulExpr ::= dollarExpr (OP6 | 'div' | 'mod' | 'shl' | 'shr' optInd dollarExpr)* -dollarExpr ::= primary (OP7 optInd primary)* - -indexExpr ::= '..' [expr] | expr ['=' expr | '..' expr] - -castExpr ::= 'cast' '[' optInd typeDesc [SAD] ']' '(' optInd expr [SAD] ')' -addrExpr ::= 'addr' '(' optInd expr ')' -symbol ::= '`' (KEYWORD | IDENT | operator | '(' ')' - | '[' ']' | '=' | literal)+ '`' - | IDENT - -primaryPrefix ::= (prefixOperator | 'bind') optInd -primarySuffix ::= '.' optInd symbol - | '(' optInd namedExprList [SAD] ')' - | '[' optInd [indexExpr (comma indexExpr)* [comma]] [SAD] ']' - | '^' - | pragma - -primary ::= primaryPrefix* (symbol | constructor | castExpr | addrExpr) - primarySuffix* - -literal ::= INT_LIT | INT8_LIT | INT16_LIT | INT32_LIT | INT64_LIT - | FLOAT_LIT | FLOAT32_LIT | FLOAT64_LIT - | STR_LIT | RSTR_LIT | TRIPLESTR_LIT - | CHAR_LIT - | NIL - -constructor ::= literal - | '[' optInd colonExprList [SAD] ']' - | '{' optInd sliceExprList [SAD] '}' - | '(' optInd colonExprList [SAD] ')' - -colonExpr ::= expr [':' expr] -colonExprList ::= [colonExpr (comma colonExpr)* [comma]] - -namedExpr ::= expr ['=' expr] -namedExprList ::= [namedExpr (comma namedExpr)* [comma]] - -sliceExpr ::= expr ['..' expr] -sliceExprList ::= [sliceExpr (comma sliceExpr)* [comma]] - -exprOrType ::= lowestExpr - | 'if' '(' expr ')' expr ('elif' '(' expr ')' expr)* 'else' expr - | 'var' exprOrType - | 'ref' exprOrType - | 'ptr' exprOrType - | 'type' exprOrType - | 'tuple' tupleDesc - -expr ::= exprOrType - | 'proc' paramList [pragma] ['=' stmt] - -qualifiedIdent ::= symbol ['.' symbol] - -typeDesc ::= exprOrType - | 'proc' paramList [pragma] - -macroStmt ::= '{' [stmt] '}' ('of' [sliceExprList] stmt - |'elif' '(' expr ')' stmt - |'except' '(' exceptList ')' stmt )* - ['else' stmt] - -simpleStmt ::= returnStmt - | yieldStmt - | discardStmt - | raiseStmt - | breakStmt - | continueStmt - | pragma - | importStmt - | fromStmt - | includeStmt - | exprStmt -complexStmt ::= ifStmt | whileStmt | caseStmt | tryStmt | forStmt - | blockStmt | asmStmt - | procDecl | iteratorDecl | macroDecl | templateDecl | methodDecl - | constSection | typeSection | whenStmt | varSection - -stmt ::= simpleStmt - | indPush (complexStmt | simpleStmt) (';' (complexStmt | simpleStmt))* - DED indPop - -exprStmt ::= lowestExpr ['=' expr | [expr (comma expr)*] [macroStmt]] -returnStmt ::= 'return' [expr] -yieldStmt ::= 'yield' expr -discardStmt ::= 'discard' expr -raiseStmt ::= 'raise' [expr] -breakStmt ::= 'break' [symbol] -continueStmt ::= 'continue' -ifStmt ::= 'if' '(' expr ')' stmt ('elif' '(' expr ')' stmt)* ['else' stmt] -whenStmt ::= 'when' '(' expr ')' stmt ('elif' '(' expr ')' stmt)* ['else' stmt] -caseStmt ::= 'case' '(' expr ')' ('of' sliceExprList ':' stmt)* - ('elif' '(' expr ')' stmt)* - ['else' stmt] -whileStmt ::= 'while' '(' expr ')' stmt -forStmt ::= 'for' '(' symbol (comma symbol)* 'in' expr ['..' expr] ')' stmt -exceptList ::= [qualifiedIdent (comma qualifiedIdent)*] - -tryStmt ::= 'try' stmt - ('except' '(' exceptList ')' stmt)* - ['finally' stmt] -asmStmt ::= 'asm' [pragma] (STR_LIT | RSTR_LIT | TRIPLESTR_LIT) -blockStmt ::= 'block' [symbol] stmt -filename ::= symbol | STR_LIT | RSTR_LIT | TRIPLESTR_LIT -importStmt ::= 'import' filename (comma filename)* -includeStmt ::= 'include' filename (comma filename)* -fromStmt ::= 'from' filename 'import' symbol (comma symbol)* - -pragma ::= '{.' optInd (colonExpr [comma])* [SAD] ('.}' | '}') - -param ::= symbol (comma symbol)* (':' typeDesc ['=' expr] | '=' expr) -paramList ::= ['(' [param (comma param)*] [SAD] ')'] [':' typeDesc] - -genericParam ::= symbol [':' typeDesc] ['=' expr] -genericParams ::= '[' genericParam (comma genericParam)* [SAD] ']' - - -routineDecl := symbol ['*'] [genericParams] paramList [pragma] ['=' stmt] -procDecl ::= 'proc' routineDecl -macroDecl ::= 'macro' routineDecl -iteratorDecl ::= 'iterator' routineDecl -templateDecl ::= 'template' routineDecl -methodDecl ::= 'method' routineDecl - -colonAndEquals ::= [':' typeDesc] '=' expr - -constDecl ::= symbol ['*'] [pragma] colonAndEquals ';' [COMMENT] -constSection ::= 'const' [COMMENT] (constDecl | '{' constDecl+ '}') - -typeDef ::= typeDesc | objectDef | enumDef | 'distinct' typeDesc - -objectField ::= symbol ['*'] [pragma] -objectIdentPart ::= objectField (comma objectField)* ':' typeDesc - [COMMENT|IND COMMENT] - -objectWhen ::= 'when' expr ':' [COMMENT] objectPart - ('elif' expr ':' [COMMENT] objectPart)* - ['else' ':' [COMMENT] objectPart] -objectCase ::= 'case' expr ':' typeDesc [COMMENT] - ('of' sliceExprList ':' [COMMENT] objectPart)* - ['else' ':' [COMMENT] objectPart] - -objectPart ::= objectWhen | objectCase | objectIdentPart | 'nil' - | indPush objectPart (SAD objectPart)* DED indPop -tupleDesc ::= '[' optInd [param (comma param)*] [SAD] ']' - -objectDef ::= 'object' [pragma] ['of' typeDesc] objectPart -enumField ::= symbol ['=' expr] -enumDef ::= 'enum' ['of' typeDesc] (enumField [comma] [COMMENT | IND COMMENT])+ - -typeDecl ::= COMMENT - | symbol ['*'] [genericParams] ['=' typeDef] [COMMENT | IND COMMENT] - -typeSection ::= 'type' indPush typeDecl (SAD typeDecl)* DED indPop - -colonOrEquals ::= ':' typeDesc ['=' expr] | '=' expr -varField ::= symbol ['*'] [pragma] -varPart ::= symbol (comma symbol)* colonOrEquals [COMMENT | IND COMMENT] -varSection ::= 'var' (varPart - | indPush (COMMENT|varPart) - (SAD (COMMENT|varPart))* DED indPop) diff --git a/doc/intern.txt b/doc/intern.txt index 86afbb7ba..748b648fb 100755 --- a/doc/intern.txt +++ b/doc/intern.txt @@ -218,7 +218,7 @@ Backend issues However the biggest problem is that dead code elimination breaks modularity! To see why, consider this scenario: The module ``G`` (for example the huge -Gtk2 module...) is compiled with dead code elimination turned on. So no +Gtk2 module...) is compiled with dead code elimination turned on. So none of ``G``'s procs is generated at all. Then module ``B`` is compiled that requires ``G.P1``. Ok, no problem, @@ -366,11 +366,39 @@ comparisons). Code generation for closures ============================ +Code generation for closures is implemented by `lambda lifting`:idx:. + +Design +------ + +A ``closure`` proc var can call ordinary procs of the default Nimrod calling +convention. But not the other way round! A closure is implemented as a +``tuple[prc, env]``. ``env`` can be nil implying a call without a closure. +This means that a call through a closure generates an ``if`` but the +interoperability is worth the cost of the ``if``. Thunk generation would be +possible too, but it's slightly more effort to implement. + +Tests with GCC on Amd64 showed that it's really beneficical if the +'environment' pointer is passed as the last argument, not as the first argument. + +Proper thunk generation is harder because the proc that is to wrap +could stem from a complex expression: + +.. code-block:: nimrod + receivesClosure(returnsDefaultCC[i]) + +A thunk would need to call 'returnsDefaultCC[i]' somehow and that would require +an *additional* closure generation... Ok, not really, but it requires to pass +the function to call. So we'd end up with 2 indirect calls instead of one. +Another much more severe problem which this solution is that it's not GC-safe +to pass a proc pointer around via a generic ``ref`` type. + + Example code: .. code-block:: nimrod proc add(x: int): proc (y: int): int {.closure.} = - return lambda (y: int): int = + return proc (y: int): int = return x + y var add2 = add(2) @@ -380,21 +408,21 @@ This should produce roughly this code: .. code-block:: nimrod type - PClosure = ref object - fn: proc (x: int, c: PClosure): int + PEnv = ref object x: int # data - proc wasLambda(y: int, c: PClosure): int = + proc anon(y: int, c: PClosure): int = return y + c.x - proc add(x: int): PClosure = - var c: PClosure - new(c) - c.x = x - c.fn = wasLambda + proc add(x: int): tuple[prc, data] = + var env: PEnv + new env + env.x = x + result = (anon, env) var add2 = add(2) - echo add2.fn(5, add2) + let tmp = if add2.data == nil: add2.prc(5) else: add2.prc(5, add2.data) + echo tmp Beware of nesting: @@ -412,36 +440,46 @@ This should produce roughly this code: .. code-block:: nimrod type - PClosure1 = ref object - fn: proc (x: int, c: PClosure1): int + PEnvX = ref object x: int # data - PClosure2 = ref object - fn: proc (x: int, c: PClosure2): int + PEnvY = ref object y: int - c1: PClosure1 + ex: PEnvX + proc lambdaZ(z: int, ey: PEnvY): int = + return ey.ex.x + ey.y + z - proc innerLambda(z: int, c2: PClosure2): int = - return c2.c1.x + c2.y + z - - proc outerLambda1(y: int, c1: PClosure1): PClosure2 = - new(result) - result.c1 = c1 - result.y = y - result.fn = innerLambda + proc lambdaY(y: int, ex: PEnvX): tuple[prc, data: PEnvY] = + var ey: PEnvY + new ey + ey.y = y + ey.ex = ex + result = (lambdaZ, ey) - proc add(x: int): PClosure1 = - new(result) - result.x = x - result.fn = outerLambda + proc add(x: int): tuple[prc, data: PEnvX] = + var ex: PEnvX + ex.x = x + result = (labmdaY, ex) var tmp = add(2) - var tmp2 = tmp.fn(4, tmp) - var add24 = tmp2.fn(4, tmp2) + var tmp2 = tmp.fn(4, tmp.data) + var add24 = tmp2.fn(4, tmp2.data) echo add24(5) +We could get rid of nesting environments by always inlining inner anon procs. +More useful is escape analysis and stack allocation of the environment, +however. + + +Alternative +----------- + +Process the closure of all inner procs in one pass and accumulate the +environments. This is however not always possible. + + Accumulator ----------- @@ -451,3 +489,34 @@ Accumulator return lambda: int = inc i return i + + proc p = + var delta = 7 + proc accumulator(start: int): proc(): int = + var x = start-1 + result = proc (): int = + x = x + delta + inc delta + return x + + var a = accumulator(3) + var b = accumulator(4) + echo a() + b() + + +Internals +--------- + +Lambda lifting is implemented as part of the ``transf`` pass. The ``transf`` +pass generates code to setup the environment and to pass it around. However, +this pass does not change the types! So we have some kind of mismatch here; on +the one hand the proc expression becomes an explicit tuple, on the other hand +the tyProc(ccClosure) type is not changed. For C code generation it's also +important the hidden formal param is ``void*`` and not something more +specialized. However the more specialized env type needs to passed to the +backend somehow. We deal with this by modifying ``s.ast[paramPos]`` to contain +the formal hidden parameter, but not ``s.typ``! + + + + diff --git a/doc/manual.txt b/doc/manual.txt index abdcc05d5..231aaf2ce 100755 --- a/doc/manual.txt +++ b/doc/manual.txt @@ -1037,7 +1037,7 @@ A `procedural type`:idx: is internally a pointer to a procedure. ``nil`` is an allowed value for variables of a procedural type. Nimrod uses procedural types to achieve `functional`:idx: programming techniques. -Example: +Examples: .. code-block:: nimrod @@ -1051,12 +1051,30 @@ Example: forEach(printItem) # this will NOT work because calling conventions differ + +.. code-block:: nimrod + + type + TOnMouseMove = proc (x, y: int) {.closure.} + + proc onMouseMove(mouseX, mouseY: int) = + # has default calling convention + echo "x: ", mouseX, " y: ", mouseY + + proc setOnMouseMove(mouseMoveEvent: TOnMouseMove) = nil + + # ok, 'onMouseMove' has the default calling convention, which is compatible + # to 'closure': + setOnMouseMove(onMouseMove) + + A subtle issue with procedural types is that the calling convention of the procedure influences the type compatibility: procedural types are only -compatible if they have the same calling convention. +compatible if they have the same calling convention. As a special extension, +a procedure of the calling convention ``nimcall`` can be passed to a parameter +that expects a proc of the calling convention ``closure``. -Nimrod supports these `calling conventions`:idx:, which are all incompatible to -each other: +Nimrod supports these `calling conventions`:idx:\: `stdcall`:idx: This the stdcall convention as specified by Microsoft. The generated C @@ -1089,8 +1107,10 @@ each other: same as ``fastcall``, but only for C compilers that support ``fastcall``. `closure`:idx: - indicates that the procedure expects a context, a closure that needs - to be passed to the procedure. + indicates that the procedure has a hidden implicit parameter + (an *environment*). Proc vars that have the calling convention ``closure`` + take up two machine words: One for the proc pointer and another one for + the pointer to implicitely passed environment. `syscall`:idx: The syscall convention is the same as ``__syscall`` in C. It is used for @@ -1114,6 +1134,11 @@ of the following conditions hold: The rules' purpose is to prevent the case that extending a non-``procvar`` procedure with default parameters breaks client code. +The default calling convention is ``nimcall``, unless it is an inner proc ( +a proc inside of a proc). For an inner proc an analysis is performed wether it +accesses its environment. If it does so, it has the calling convention +``closure``, otherwise it has the calling convention ``nimcall``. + Distinct type ~~~~~~~~~~~~~ diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim index 1e9a0bb4b..045b78250 100755 --- a/lib/pure/algorithm.nim +++ b/lib/pure/algorithm.nim @@ -34,6 +34,24 @@ proc reverse*[T](a: var openArray[T]) = ## reverses the array `a`. reverse(a, 0, a.high) +proc binarySearch*[T](a: openarray[T], key: T): int = + ## binary search for `key` in `a`. Returns -1 if not found. + var b = len(a) + while result < b: + var mid = (result + b) div 2 + if a[mid] < key: result = mid + 1 + else: b = mid + if result >= len(x) or a[result] != key: result = -1 + +proc smartBinarySearch*[T](a: openArray[T], key: T): int = + ## ``a.len`` must be a power of 2 for this to work. + var step = a.len div 2 + while step > 0: + if a[result or step] <= key: + result = result or step + step = step shr 1 + if a[result] != key: result = -1 + const onlySafeCode = false diff --git a/lib/system.nim b/lib/system.nim index 1e3509174..55abcaea6 100755 --- a/lib/system.nim +++ b/lib/system.nim @@ -83,6 +83,9 @@ proc new*[T](a: var ref T) {.magic: "New", noSideEffect.} ## creates a new object of type ``T`` and returns a safe (traced) ## reference to it in ``a``. +proc internalNew*[T](a: var ref T) {.magic: "New", noSideEffect.} + ## leaked implementation detail. Do not use. + proc new*[T](a: var ref T, finalizer: proc (x: ref T)) {. magic: "NewFinalize", noSideEffect.} ## creates a new object of type ``T`` and returns a safe (traced) diff --git a/todo.txt b/todo.txt index c666f7903..b43357007 100755 --- a/todo.txt +++ b/todo.txt @@ -1,8 +1,16 @@ version 0.8.14 ============== -- bug: tsortdev does not run with native GC? +- implement closures + - test evals.nim with closures + - deactivate lambda lifting for JS backend + - Test that iterators within closures work etc; test generics; + test recursion + - test constant closures + - 'closureEnv' magic for easy interfacing with C + - object {.pure, final.} does not work again! +- bug: tsortdev does not run with native GC? - ``=`` should be overloadable; requires specialization for ``=``? version 0.9.0 @@ -18,7 +26,7 @@ version 0.9.0 use tyInt+node for that - implement the high level optimizer - change overloading resolution -- implement closures; implement proper coroutines +- implement proper coroutines - implement ``partial`` pragma for partial evaluation - we need to support iteration of 2 different data structures in parallel - make exceptions compatible with C++ exceptions @@ -44,8 +52,7 @@ Bugs result = forward(x) - bug: stress testing basic method example (eval example) - without ``-d:release`` leaks memory; good way to figure out how a - fixed amount of stack can hold an arbitrary number of GC roots! + without ``-d:release`` leaks memory? - bug: temp2.nim triggers weird compiler and except.nim bug - bug: negative array indexes fail to index check @@ -56,6 +63,11 @@ version 0.9.XX - implicit ref/ptr->var conversion; the compiler may store an object implicitly on the heap for write barrier efficiency; better: proc specialization in the code gen +- shared memory heap: ``shared ref`` etc. The only hard part in the GC is to + "stop the world". However, it may be worthwhile to generate explicit + (or implicit) syncGC() calls in loops. Automatic loop injection seems + troublesome, but maybe we can come up with a simple heuristic. (All procs + that `new` shared memory are syncGC() candidates...) - EcmaScript needs a new and better code gen: simply adapt the C code gen to it - tlastmod returns wrong results on BSD (Linux, MacOS X: works) - nested tuple unpacking; tuple unpacking in non-var-context @@ -125,6 +137,8 @@ Low priority - warning for implicit openArray -> varargs conversion - implement explicit varargs; **but** ``len(varargs)`` problem remains! --> solve by implicit conversion from varargs to openarray +- implement closures that support nesting > 1 + Version 2 ========= @@ -160,6 +174,4 @@ Version 2 a full blown statement; a ``try`` expression might be a good idea to make error handling more light-weight people also want ``inc a; inc b`` - --> solved by providing an expr version of most control structures? - diff --git a/web/download.txt b/web/download.txt index bd231dd54..47c2501e9 100755 --- a/web/download.txt +++ b/web/download.txt @@ -3,15 +3,16 @@ Here you can download the latest version of the Nimrod Compiler. Please choose your platform: -* source-based installation: `<download/nimrod_0.8.12.zip>`_ -* installer for Windows XP/Vista (i386): `<download/nimrod_0.8.12.exe>`_ +* source-based installation: `<download/nimrod_0.8.14.zip>`_ +* installer for Windows XP/Vista (i386): `<download/nimrod_0.8.14.exe>`_ (includes GCC and everything else you need) The source-based installation has been tested on these systems: -* Linux: i386, AMD64 +* Linux: i386, AMD64, PowerPC * Mac OS X: i386 Other UNIX-based operating systems may work. An older version was tested on FreeBSD (i386). .. include:: ../install.txt + diff --git a/web/news.txt b/web/news.txt index db4658722..35b10019e 100755 --- a/web/news.txt +++ b/web/news.txt @@ -2,7 +2,7 @@ News ==== -2012-XX-XX Version 0.8.14 released +2012-02-XX Version 0.8.14 released ================================== Version 0.8.14 has been released! Get it `here <download.html>`_. @@ -19,6 +19,7 @@ Bugfixes - Some more bugfixes for macros and compile-time evaluation. - The GC now takes into account interior pointers on the stack which may be introduced by aggressive C optimizers. +- Nimrod's native allocator/GC now works on PowerPC. - Lots of other bugfixes: Too many to list them all. @@ -124,6 +125,8 @@ Compiler Additions for ``on|off`` switches in pragmas. In order to not break existing code, ``on`` and ``off`` are now aliases for ``true`` and ``false`` and declared in the system module. +- The compiler finally supports **closures**. This is a preliminary + implementation, which does not yet support nestings deeper than 1 level. Library Additions |