diff options
Diffstat (limited to 'compiler/semthreads.nim')
| -rw-r--r-- | compiler/semthreads.nim | 390 |
1 files changed, 0 insertions, 390 deletions
diff --git a/compiler/semthreads.nim b/compiler/semthreads.nim deleted file mode 100644 index d3426ca3e..000000000 --- a/compiler/semthreads.nim +++ /dev/null @@ -1,390 +0,0 @@ -# -# -# The Nimrod Compiler -# (c) Copyright 2013 Andreas Rumpf -# -# See the file "copying.txt", included in this -# distribution, for details about the copyright. -# - -## Semantic analysis that deals with threads: Possible race conditions should -## be reported some day. -## -## -## ======================== -## No heap sharing analysis -## ======================== -## -## The only crucial operation that can violate the heap invariants is the -## write access. The analysis needs to distinguish between 'unknown', 'mine', -## and 'theirs' memory and pointers. Assignments 'whatever <- unknown' are -## invalid, and so are 'theirs <- whatever' but not 'mine <- theirs'. Since -## strings and sequences are heap allocated they are affected too: -## -## .. code-block:: nimrod -## proc p() = -## global = "alloc this string" # ugh! -## -## Thus the analysis is concerned with any type that contains a GC'ed -## reference... -## If the type system would distinguish between 'ref' and '!ref' and threads -## could not have '!ref' as input parameters the analysis could simply need to -## reject any write access to a global variable which contains GC'ed data. -## Thanks to the write barrier of the GC, this is exactly what needs to be -## done! Every write access to a global that contains GC'ed data needs to -## be prevented! Unfortunately '!ref' is not implemented yet... -## -## The assignment target is essential for the algorithm: only -## write access to heap locations and global variables are critical and need -## to be checked. Access via 'var' parameters is no problem to analyse since -## we need the arguments' locations in the analysis. -## -## However, this is tricky: -## -## var x = globalVar # 'x' points to 'theirs' -## while true: -## globalVar = x # NOT OK: 'theirs <- theirs' invalid due to -## # write barrier! -## x = "new string" # ugh: 'x is toUnknown'! -## -## --> Solution: toUnknown is never allowed anywhere! -## -## -## Beware that the same proc might need to be -## analysed multiple times! Oh and watch out for recursion! Recursion is handled -## by a stack of symbols that we are processing, if we come back to the same -## symbol, we have to skip this check (assume no error in the recursive case). -## However this is wrong. We need to check for the particular combination -## of (procsym, threadOwner(arg1), threadOwner(arg2), ...)! - -import - ast, astalgo, strutils, hashes, options, msgs, idents, types, os, - renderer, tables, rodread - -type - TThreadOwner = enum - toUndefined, # not computed yet - toVoid, # no return type - toNil, # cycle in computation or nil: can be overwritten - toTheirs, # some other heap - toMine # mine heap - - TCall = object {.pure.} - callee: PSym # what if callee is an indirect call? - args: seq[TThreadOwner] - - PProcCtx = ref TProcCtx - TProcCtx = object {.pure.} - nxt: PProcCtx # can be stacked - mapping: tables.TTable[int, TThreadOwner] # int = symbol ID - owner: PSym # current owner - -var - computed = tables.initTable[TCall, TThreadOwner]() - -proc hash(c: TCall): THash = - result = hash(c.callee.id) - for a in items(c.args): result = result !& hash(ord(a)) - result = !$result - -proc `==`(a, b: TCall): bool = - if a.callee != b.callee: return - if a.args.len != b.args.len: return - for i in 0..a.args.len-1: - if a.args[i] != b.args[i]: return - result = true - -proc newProcCtx(owner: PSym): PProcCtx = - assert owner != nil - new(result) - result.mapping = tables.initTable[int, TThreadOwner]() - result.owner = owner - -proc analyse(c: PProcCtx, n: PNode): TThreadOwner - -proc analyseSym(c: PProcCtx, n: PNode): TThreadOwner = - var v = n.sym - result = c.mapping[v.id] - if result != toUndefined: return - case v.kind - of skVar, skForVar, skLet, skResult: - result = toNil - if sfGlobal in v.flags: - if sfThread in v.flags: - result = toMine - elif containsGarbageCollectedRef(v.typ): - result = toTheirs - of skTemp: result = toNil - of skConst: result = toMine - of skParam: - result = c.mapping[v.id] - if result == toUndefined: - internalError(n.info, "param not set: " & v.name.s) - else: - result = toNil - c.mapping[v.id] = result - -proc lvalueSym(n: PNode): PNode = - result = n - while result.kind in {nkDotExpr, nkCheckedFieldExpr, - nkBracketExpr, nkDerefExpr, nkHiddenDeref}: - result = result.sons[0] - -proc writeAccess(c: PProcCtx, n: PNode, owner: TThreadOwner) = - if owner notin {toNil, toMine, toTheirs}: - internalError(n.info, "writeAccess: " & $owner) - var a = lvalueSym(n) - if a.kind == nkSym: - var v = a.sym - var lastOwner = analyseSym(c, a) - case lastOwner - of toNil: - # fine, toNil can be overwritten - var newOwner: TThreadOwner - if sfGlobal in v.flags: - newOwner = owner - elif containsTyRef(v.typ): - # ``var local = gNode`` --> ok, but ``local`` is theirs! - newOwner = owner - else: - # ``var local = gString`` --> string copy: ``local`` is mine! - newOwner = toMine - # XXX BUG what if the tuple contains both ``tyRef`` and ``tyString``? - c.mapping[v.id] = newOwner - of toVoid, toUndefined: internalError(n.info, "writeAccess") - of toTheirs: message(n.info, warnWriteToForeignHeap) - of toMine: - if lastOwner != owner and owner != toNil: - message(n.info, warnDifferentHeaps) - else: - # we could not backtrack to a concrete symbol, but that's fine: - var lastOwner = analyse(c, n) - case lastOwner - of toNil: discard # fine, toNil can be overwritten - of toVoid, toUndefined: internalError(n.info, "writeAccess") - of toTheirs: message(n.info, warnWriteToForeignHeap) - of toMine: - if lastOwner != owner and owner != toNil: - message(n.info, warnDifferentHeaps) - -proc analyseAssign(c: PProcCtx, le, ri: PNode) = - var y = analyse(c, ri) # read access; ok - writeAccess(c, le, y) - -proc analyseAssign(c: PProcCtx, n: PNode) = - analyseAssign(c, n.sons[0], n.sons[1]) - -proc analyseCall(c: PProcCtx, n: PNode): TThreadOwner = - var prc = n[0].sym - var newCtx = newProcCtx(prc) - var call: TCall - call.callee = prc - newSeq(call.args, n.len-1) - for i in 1..n.len-1: - call.args[i-1] = analyse(c, n[i]) - if not computed.hasKey(call): - computed[call] = toUndefined # we are computing it - let prctyp = skipTypes(prc.typ, abstractInst).n - for i in 1.. prctyp.len-1: - var formal = prctyp.sons[i].sym - newCtx.mapping[formal.id] = call.args[i-1] - pushInfoContext(n.info) - result = analyse(newCtx, prc.getBody) - if prc.ast.sons[bodyPos].kind == nkEmpty and - {sfNoSideEffect, sfThread, sfImportc} * prc.flags == {}: - message(n.info, warnAnalysisLoophole, renderTree(n)) - if result == toUndefined: result = toNil - if prc.typ.sons[0] != nil: - if prc.ast.len > resultPos: - result = newCtx.mapping[prc.ast.sons[resultPos].sym.id] - # if the proc body does not set 'result', nor 'return's something - # explicitely, it returns a binary zero, so 'toNil' is correct: - if result == toUndefined: result = toNil - else: - result = toNil - else: - result = toVoid - computed[call] = result - popInfoContext() - else: - result = computed[call] - if result == toUndefined: - # ugh, cycle! We are already computing it but don't know the - # outcome yet... - if prc.typ.sons[0] == nil: result = toVoid - else: result = toNil - -proc analyseVarTuple(c: PProcCtx, n: PNode) = - if n.kind != nkVarTuple: internalError(n.info, "analyseVarTuple") - var L = n.len - for i in countup(0, L-3): analyseAssign(c, n.sons[i], n.sons[L-1]) - -proc analyseSingleVar(c: PProcCtx, a: PNode) = - if a.sons[2].kind != nkEmpty: analyseAssign(c, a.sons[0], a.sons[2]) - -proc analyseVarSection(c: PProcCtx, n: PNode): TThreadOwner = - 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); also valid for after - # closure transformation: - analyseSingleVar(c, a) - else: - analyseVarTuple(c, a) - result = toVoid - -proc analyseConstSection(c: PProcCtx, t: PNode): TThreadOwner = - for i in countup(0, sonsLen(t) - 1): - var it = t.sons[i] - if it.kind == nkCommentStmt: continue - if it.kind != nkConstDef: internalError(t.info, "analyseConstSection") - if sfFakeConst in it.sons[0].sym.flags: analyseSingleVar(c, it) - result = toVoid - -template aggregateOwner(result, ana: expr) = - var a = ana # eval once - if result != a: - if result == toNil: result = a - elif a != toNil: message(n.info, warnDifferentHeaps) - -proc analyseArgs(c: PProcCtx, n: PNode, start = 1) = - for i in start..n.len-1: discard analyse(c, n[i]) - -proc analyseOp(c: PProcCtx, n: PNode): TThreadOwner = - if n[0].kind != nkSym or n[0].sym.kind != skProc: - if {tfNoSideEffect, tfThread} * n[0].typ.flags == {}: - message(n.info, warnAnalysisLoophole, renderTree(n)) - result = toNil - else: - var prc = n[0].sym - case prc.magic - of mNone: - if sfSystemModule in prc.owner.flags: - # System module proc does no harm :-) - analyseArgs(c, n) - if prc.typ.sons[0] == nil: result = toVoid - else: result = toNil - else: - result = analyseCall(c, n) - of mNew, mNewFinalize, mNewSeq, mSetLengthStr, mSetLengthSeq, - mAppendSeqElem, mReset, mAppendStrCh, mAppendStrStr: - writeAccess(c, n[1], toMine) - result = toVoid - of mSwap: - var a = analyse(c, n[2]) - writeAccess(c, n[1], a) - writeAccess(c, n[2], a) - result = toVoid - of mIntToStr, mInt64ToStr, mFloatToStr, mBoolToStr, mCharToStr, - mCStrToStr, mStrToStr, mEnumToStr, - mConStrStr, mConArrArr, mConArrT, - mConTArr, mConTT, mSlice, - mRepr, mArrToSeq, mCopyStr, mCopyStrLast, - mNewString, mNewStringOfCap: - analyseArgs(c, n) - result = toMine - else: - # don't recurse, but check args: - analyseArgs(c, n) - if prc.typ.sons[0] == nil: result = toVoid - else: result = toNil - -proc analyse(c: PProcCtx, n: PNode): TThreadOwner = - case n.kind - of nkCall, nkInfix, nkPrefix, nkPostfix, nkCommand, - nkCallStrLit, nkHiddenCallConv: - result = analyseOp(c, n) - of nkAsgn, nkFastAsgn: - analyseAssign(c, n) - result = toVoid - of nkSym: result = analyseSym(c, n) - of nkEmpty, nkNone: result = toVoid - of nkNilLit, nkCharLit..nkFloat64Lit: result = toNil - of nkStrLit..nkTripleStrLit: result = toMine - of nkDotExpr, nkBracketExpr, nkDerefExpr, nkHiddenDeref: - # field access: - # pointer deref or array access: - result = analyse(c, n.sons[0]) - of nkBind: result = analyse(c, n.sons[0]) - of nkPar, nkCurly, nkBracket, nkRange: - # container construction: - result = toNil # nothing until later - for i in 0..n.len-1: aggregateOwner(result, analyse(c, n[i])) - of nkObjConstr: - if n.typ != nil and containsGarbageCollectedRef(n.typ): - result = toMine - else: - result = toNil # nothing until later - for i in 1..n.len-1: aggregateOwner(result, analyse(c, n[i])) - of nkAddr, nkHiddenAddr: - var a = lvalueSym(n) - if a.kind == nkSym: - result = analyseSym(c, a) - assert result in {toNil, toMine, toTheirs} - if result == toNil: - # assume toMine here for consistency: - c.mapping[a.sym.id] = toMine - result = toMine - else: - # should never really happen: - result = analyse(c, n.sons[0]) - of nkIfExpr: - result = toNil - for i in countup(0, sonsLen(n) - 1): - var it = n.sons[i] - if it.len == 2: - discard analyse(c, it.sons[0]) - aggregateOwner(result, analyse(c, it.sons[1])) - else: - aggregateOwner(result, analyse(c, it.sons[0])) - of nkStmtListExpr, nkBlockExpr: - var n = if n.kind == nkBlockExpr: n.sons[1] else: n - var L = sonsLen(n) - for i in countup(0, L-2): discard analyse(c, n.sons[i]) - if L > 0: result = analyse(c, n.sons[L-1]) - else: result = toVoid - of nkHiddenStdConv, nkHiddenSubConv, nkConv, nkCast: - result = analyse(c, n.sons[1]) - of nkStringToCString, nkCStringToString, nkChckRangeF, nkChckRange64, - nkChckRange, nkCheckedFieldExpr, nkObjDownConv, - nkObjUpConv: - result = analyse(c, n.sons[0]) - of nkRaiseStmt: - var a = analyse(c, n.sons[0]) - if a != toMine: message(n.info, warnDifferentHeaps) - result = toVoid - of nkVarSection, nkLetSection: result = analyseVarSection(c, n) - of nkConstSection: result = analyseConstSection(c, n) - of nkTypeSection, nkCommentStmt: result = toVoid - of nkIfStmt, nkWhileStmt, nkTryStmt, nkCaseStmt, nkStmtList, nkBlockStmt, - nkElifBranch, nkElse, nkExceptBranch, nkOfBranch, nkFinally: - for i in 0 .. <n.len: discard analyse(c, n[i]) - result = toVoid - of nkBreakStmt, nkContinueStmt: result = toVoid - of nkReturnStmt, nkDiscardStmt: - if n.sons[0].kind != nkEmpty: result = analyse(c, n.sons[0]) - else: result = toVoid - of nkLambdaKinds, nkClosure: - result = toMine - of nkAsmStmt, nkPragma, nkIteratorDef, nkProcDef, nkMethodDef, - nkConverterDef, nkMacroDef, nkTemplateDef, - nkGotoState, nkState, nkBreakState, nkType, nkIdent: - result = toVoid - of nkExprColonExpr: - result = analyse(c, n.sons[1]) - else: internalError(n.info, "analysis not implemented for: " & $n.kind) - -proc analyseThreadProc*(prc: PSym) = - var c = newProcCtx(prc) - var formals = skipTypes(prc.typ, abstractInst).n - for i in 1 .. formals.len-1: - var formal = formals.sons[i].sym - # the input is copied and belongs to the thread: - c.mapping[formal.id] = toMine - discard analyse(c, prc.getBody) - -proc needsGlobalAnalysis*: bool = - result = gGlobalOptions * {optThreads, optThreadAnalysis} == - {optThreads, optThreadAnalysis} - |