Nim - This repository contains the Nim compiler, Nim's stdlib, tools, and documentation. (mirror)

diff options

Diffstat (limited to 'tests/namedparams')

0 files changed, 0 insertions, 0 deletions

# # # The Nim Compiler # (c) Copyright 2020 Andreas Rumpf # # See the file "copying.txt", included in this # distribution, for details about the copyright. # ## Partition variables into different graphs. Used for ## Nim's write tracking, borrow checking and also for the ## cursor inference. ## The algorithm is a reinvention / variation of Steensgaard's ## algorithm. ## The used data structure is "union find" with path compression. ## We perform two passes over the AST: ## - Pass one (``computeLiveRanges``): collect livetimes of local ## variables and whether they are potentially re-assigned. ## - Pass two (``traverse``): combine local variables to abstract "graphs". ## Strict func checking: Ensure that graphs that are connected to ## const parameters are not mutated. ## Cursor inference: Ensure that potential cursors are not ## borrowed from locations that are connected to a graph ## that is mutated during the liveness of the cursor. ## (We track all possible mutations of a graph.) ## ## See https://nim-lang.github.io/Nim/manual_experimental.html#view-types-algorithm ## for a high-level description of how borrow checking works. import ast, types, lineinfos, options, msgs, renderer, typeallowed, modulegraphs from trees import getMagic, isNoSideEffectPragma, stupidStmtListExpr from isolation_check import canAlias when defined(nimPreviewSlimSystem): import std/assertions type AbstractTime = distinct int const MaxTime = AbstractTime high(int) MinTime = AbstractTime(-1) proc `<=`(a, b: AbstractTime): bool {.borrow.} proc `<`(a, b: AbstractTime): bool {.borrow.} proc inc(x: var AbstractTime; diff = 1) {.borrow.} proc dec(x: var AbstractTime; diff = 1) {.borrow.} proc `$`(x: AbstractTime): string {.borrow.} type SubgraphFlag = enum isMutated, # graph might be mutated isMutatedDirectly, # graph is mutated directly by a non-var parameter. isMutatedByVarParam, # graph is mutated by a var parameter. connectsConstParam # graph is connected to a non-var parameter. VarFlag = enum ownsData, preventCursor, isReassigned, isConditionallyReassigned, viewDoesMutate, viewBorrowsFromConst VarIndexKind = enum isEmptyRoot, dependsOn, isRootOf Connection = object case kind: VarIndexKind of isEmptyRoot: discard of dependsOn: parent: int of isRootOf: graphIndex: int VarIndex = object con: Connection flags: set[VarFlag] sym: PSym reassignedTo: int aliveStart, aliveEnd: AbstractTime # the range for which the variable is alive. borrowsFrom: seq[int] # indexes into Partitions.s MutationInfo* = object param: PSym mutatedHere, connectedVia: TLineInfo flags: set[SubgraphFlag] maxMutation, minConnection: AbstractTime mutations: seq[AbstractTime] Goal* = enum constParameters, borrowChecking, cursorInference Partitions* = object abstractTime: AbstractTime defers: seq[PNode] processDefer: bool s: seq[VarIndex] graphs: seq[MutationInfo] goals: set[Goal] unanalysableMutation: bool inAsgnSource, inConstructor, inNoSideEffectSection: int inConditional, inLoop: int owner: PSym g: ModuleGraph proc mutationAfterConnection(g: MutationInfo): bool {.inline.} = #echo g.maxMutation.int, " ", g.minConnection.int, " ", g.param g.maxMutation > g.minConnection proc `$`*(config: ConfigRef; g: MutationInfo): string = result = "" if g.flags * {isMutated, connectsConstParam} == {isMutated, connectsConstParam}: result.add "\nan object reachable from '" result.add g.param.name.s result.add "' is potentially mutated" if g.mutatedHere != unknownLineInfo: result.add "\n" result.add config $ g.mutatedHere result.add " the mutation is here" if g.connectedVia != unknownLineInfo: result.add "\n" result.add config $ g.connectedVia result.add " is the statement that connected the mutation to the parameter" proc hasSideEffect*(c: var Partitions; info: var MutationInfo): bool = for g in mitems c.graphs: if g.flags * {isMutated, connectsConstParam} == {isMutated, connectsConstParam} and (mutationAfterConnection(g) or isMutatedDirectly in g.flags): info = g return true return false template isConstParam(a): bool = a.kind == skParam and a.typ.kind notin {tyVar, tySink} proc variableId(c: Partitions; x: PSym): int = for i in 0 ..< c.s.len: if c.s[i].sym == x: return i return -1 proc registerResult(c: var Partitions; n: PNode) = if n.kind == nkSym: c.s.add VarIndex(con: Connection(kind: isEmptyRoot), sym: n.sym, reassignedTo: 0, aliveStart: MaxTime, aliveEnd: c.abstractTime) proc registerParam(c: var Partitions; n: PNode) = assert n.kind == nkSym if isConstParam(n.sym): c.s.add VarIndex(con: Connection(kind: isRootOf, graphIndex: c.graphs.len), sym: n.sym, reassignedTo: 0, aliveStart: c.abstractTime, aliveEnd: c.abstractTime) c.graphs.add MutationInfo(param: n.sym, mutatedHere: unknownLineInfo, connectedVia: unknownLineInfo, flags: {connectsConstParam}, maxMutation: MinTime, minConnection: MaxTime, mutations: @[]) else: c.s.add VarIndex(con: Connection(kind: isEmptyRoot), sym: n.sym, reassignedTo: 0, aliveStart: c.abstractTime, aliveEnd: c.abstractTime) proc registerVariable(c: var Partitions; n: PNode) = if n.kind == nkSym and variableId(c, n.sym) < 0: c.s.add VarIndex(con: Connection(kind: isEmptyRoot), sym: n.sym, reassignedTo: 0, aliveStart: c.abstractTime, aliveEnd: c.abstractTime) proc root(v: var Partitions; start: int): int = result = start var depth = 0 while v.s[result].con.kind == dependsOn: result = v.s[result].con.parent inc depth if depth > 0: # path compression: var it = start while v.s[it].con.kind == dependsOn: let next = v.s[it].con.parent v.s[it].con = Connection(kind: dependsOn, parent: result) it = next proc potentialMutation(v: var Partitions; s: PSym; level: int; info: TLineInfo) = let id = variableId(v, s) if id >= 0: let r = root(v, id) let flags = if s.kind == skParam: if isConstParam(s): {isMutated, isMutatedDirectly} elif s.typ.kind == tyVar and level <= 1: # varParam[i] = v is different from varParam[i][] = v {isMutatedByVarParam} else: {isMutated} else: {isMutated} case v.s[r].con.kind of isEmptyRoot: v.s[r].con = Connection(kind: isRootOf, graphIndex: v.graphs.len) v.graphs.add MutationInfo(param: if isConstParam(s): s else: nil, mutatedHere: info, connectedVia: unknownLineInfo, flags: flags, maxMutation: v.abstractTime, minConnection: MaxTime, mutations: @[v.abstractTime]) of isRootOf: let g = addr v.graphs[v.s[r].con.graphIndex] if g.param == nil and isConstParam(s): g.param = s if v.abstractTime > g.maxMutation: g.mutatedHere = info g.maxMutation = v.abstractTime g.flags.incl flags g.mutations.add v.abstractTime else: assert false, "cannot happen" else: v.unanalysableMutation = true proc connect(v: var Partitions; a, b: PSym; info: TLineInfo) = let aid = variableId(v, a) if aid < 0: return let bid = variableId(v, b) if bid < 0: return let ra = root(v, aid) let rb = root(v, bid) if ra != rb: var param = PSym(nil) if isConstParam(a): param = a elif isConstParam(b): param = b let paramFlags = if param != nil: {connectsConstParam} else: {} # for now we always make 'rb' the slave and 'ra' the master: var rbFlags: set[SubgraphFlag] = {} var mutatedHere = unknownLineInfo var mut = AbstractTime 0 var con = v.abstractTime var gb: ptr MutationInfo = nil if v.s[rb].con.kind == isRootOf: gb = addr v.graphs[v.s[rb].con.graphIndex] if param == nil: param = gb.param mutatedHere = gb.mutatedHere rbFlags = gb.flags mut = gb.maxMutation con = min(con, gb.minConnection) v.s[rb].con = Connection(kind: dependsOn, parent: ra) case v.s[ra].con.kind of isEmptyRoot: v.s[ra].con = Connection(kind: isRootOf, graphIndex: v.graphs.len) v.graphs.add MutationInfo(param: param, mutatedHere: mutatedHere, connectedVia: info, flags: paramFlags + rbFlags, maxMutation: mut, minConnection: con, mutations: if gb != nil: gb.mutations else: @[]) of isRootOf: var g = addr v.graphs[v.s[ra].con.graphIndex] if g.param == nil: g.param = param if g.mutatedHere == unknownLineInfo: g.mutatedHere = mutatedHere g.minConnection = min(g.minConnection, con) g.connectedVia = info g.flags.incl paramFlags + rbFlags if gb != nil: g.mutations.add gb.mutations else: assert false, "cannot happen" proc borrowFromConstExpr(n: PNode): bool = case n.kind of nkCharLit..nkNilLit: result = true of nkExprEqExpr, nkExprColonExpr, nkHiddenStdConv, nkHiddenSubConv, nkCast, nkObjUpConv, nkObjDownConv: result = borrowFromConstExpr(n.lastSon) of nkCurly, nkBracket, nkPar, nkTupleConstr, nkObjConstr, nkClosure, nkRange: result = true for i in ord(n.kind == nkObjConstr)..<n.len: if not borrowFromConstExpr(n[i]): return false of nkCallKinds: if getMagic(n) == mArrToSeq: result = true for i in 1..<n.len: if not borrowFromConstExpr(n[i]): return false else: discard proc pathExpr(node: PNode; owner: PSym): PNode = #[ From the spec: - ``source`` itself is a path expression. - Container access like ``e[i]`` is a path expression. - Tuple access ``e[0]`` is a path expression. - Object field access ``e.field`` is a path expression. - ``system.toOpenArray(e, ...)`` is a path expression. - Pointer dereference ``e[]`` is a path expression. - An address ``addr e``, ``unsafeAddr e`` is a path expression. - A type conversion ``T(e)`` is a path expression. - A cast expression ``cast[T](e)`` is a path expression. - ``f(e, ...)`` is a path expression if ``f``'s return type is a view type. Because the view can only have been borrowed from ``e``, we then know that owner of ``f(e, ...)`` is ``e``. Returns the owner of the path expression. Returns ``nil`` if it is not a valid path expression. ]# var n = node result = nil while true: case n.kind of nkSym: case n.sym.kind of skParam, skTemp, skResult, skForVar: if n.sym.owner == owner: result = n of skVar: if n.sym.owner == owner or sfThread in n.sym.flags: result = n of skLet, skConst: if n.sym.owner == owner or {sfThread, sfGlobal} * n.sym.flags != {}: result = n else: discard break of nkDotExpr, nkDerefExpr, nkBracketExpr, nkHiddenDeref, nkCheckedFieldExpr, nkAddr, nkHiddenAddr: n = n[0] of nkHiddenStdConv, nkHiddenSubConv, nkConv, nkCast, nkObjUpConv, nkObjDownConv: n = n.lastSon of nkStmtList, nkStmtListExpr: if n.len > 0 and stupidStmtListExpr(n): n = n.lastSon else: break of nkCallKinds: if n.len > 1: if (n.typ != nil and classifyViewType(n.typ) != noView) or getMagic(n) == mSlice: n = n[1] else: break else: break else: break # borrowFromConstExpr(n) is correct here because we need 'node' # stripped off the path suffixes: if result == nil and borrowFromConstExpr(n): result = n const RootEscapes = 1000 # in 'p(r)' we don't know what p does to our poor root. # so we assume a high level of indirections proc allRoots(n: PNode; result: var seq[(PSym, int)]; level: int) = case n.kind of nkSym: if n.sym.kind in {skParam, skVar, skTemp, skLet, skResult, skForVar}: result.add((n.sym, level)) of nkDerefExpr, nkHiddenDeref: allRoots(n[0], result, level+1) of nkBracketExpr, nkDotExpr, nkCheckedFieldExpr, nkAddr, nkHiddenAddr: allRoots(n[0], result, level) of nkExprEqExpr, nkExprColonExpr, nkHiddenStdConv, nkHiddenSubConv, nkConv, nkStmtList, nkStmtListExpr, nkBlockStmt, nkBlockExpr, nkCast, nkObjUpConv, nkObjDownConv: if n.len > 0: allRoots(n.lastSon, result, level) of nkCaseStmt, nkObjConstr: for i in 1..<n.len: allRoots(n[i].lastSon, result, level) of nkIfStmt, nkIfExpr: for i in 0..<n.len: allRoots(n[i].lastSon, result, level) of nkBracket, nkTupleConstr, nkPar: for i in 0..<n.len: allRoots(n[i], result, level-1) of nkCallKinds: if n.typ != nil and n.typ.kind in {tyVar, tyLent}: if n.len > 1: # XXX We really need the unwritten RFC here and distinguish between # proc `[]`(x: var Container): var T # resizes the container # and # proc `[]`(x: Container): var T # only allows for slot mutation allRoots(n[1], result, RootEscapes) else: let m = getMagic(n) case m of mNone: if n[0].typ.isNil: return var typ = n[0].typ if typ != nil: typ = skipTypes(typ, abstractInst) if typ.kind != tyProc: typ = nil else: assert(typ.len == typ.n.len) for i in 1 ..< n.len: let it = n[i] if typ != nil and i < typ.len: assert(typ.n[i].kind == nkSym) let paramType = typ.n[i].typ if not paramType.isCompileTimeOnly and not typ.sons[0].isEmptyType and canAlias(paramType, typ.sons[0]): allRoots(it, result, RootEscapes) else: allRoots(it, result, RootEscapes) of mSlice: allRoots(n[1], result, level+1) else: discard "harmless operation" else: discard "nothing to do" proc destMightOwn(c: var Partitions; dest: var VarIndex; n: PNode) = ## Analyse if 'n' is an expression that owns the data, if so mark 'dest' ## with 'ownsData'. case n.kind of nkEmpty, nkCharLit..nkNilLit: # primitive literals including the empty are harmless: discard of nkExprEqExpr, nkExprColonExpr, nkHiddenStdConv, nkHiddenSubConv, nkCast, nkConv: destMightOwn(c, dest, n[1]) of nkIfStmt, nkIfExpr: for i in 0..<n.len: destMightOwn(c, dest, n[i].lastSon) of nkCaseStmt: for i in 1..<n.len: destMightOwn(c, dest, n[i].lastSon) of nkStmtList, nkStmtListExpr: if n.len > 0: destMightOwn(c, dest, n[^1]) of nkClosure: for i in 1..<n.len: destMightOwn(c, dest, n[i]) # you must destroy a closure: dest.flags.incl ownsData of nkObjConstr: for i in 1..<n.len: destMightOwn(c, dest, n[i]) if hasDestructor(n.typ): # you must destroy a ref object: dest.flags.incl ownsData of nkCurly, nkBracket, nkPar, nkTupleConstr: inc c.inConstructor for son in n: destMightOwn(c, dest, son) dec c.inConstructor if n.typ.skipTypes(abstractInst).kind == tySequence: # you must destroy a sequence: dest.flags.incl ownsData of nkSym: if n.sym.kind in {skVar, skResult, skTemp, skLet, skForVar, skParam}: if n.sym.flags * {sfThread, sfGlobal} != {}: # aliasing a global is inherently dangerous: dest.flags.incl ownsData else: # otherwise it's just a dependency, nothing to worry about: connect(c, dest.sym, n.sym, n.info) # but a construct like ``[symbol]`` is dangerous: if c.inConstructor > 0: dest.flags.incl ownsData of nkDotExpr, nkBracketExpr, nkHiddenDeref, nkDerefExpr, nkObjUpConv, nkObjDownConv, nkCheckedFieldExpr, nkAddr, nkHiddenAddr: destMightOwn(c, dest, n[0]) of nkCallKinds: if n.typ != nil: if hasDestructor(n.typ): # calls do construct, what we construct must be destroyed, # so dest cannot be a cursor: dest.flags.incl ownsData elif n.typ.kind in {tyLent, tyVar} and n.len > 1: # we know the result is derived from the first argument: var roots: seq[(PSym, int)] allRoots(n[1], roots, RootEscapes) for r in roots: connect(c, dest.sym, r[0], n[1].info) else: let magic = if n[0].kind == nkSym: n[0].sym.magic else: mNone # this list is subtle, we try to answer the question if after 'dest = f(src)' # there is a connection betwen 'src' and 'dest' so that mutations to 'src' # also reflect 'dest': if magic in {mNone, mMove, mSlice, mAppendStrCh, mAppendStrStr, mAppendSeqElem, mArrToSeq, mOpenArrayToSeq}: for i in 1..<n.len: # we always have to assume a 'select(...)' like mechanism. # But at least we do filter out simple POD types from the # list of dependencies via the 'hasDestructor' check for # the root's symbol. if hasDestructor(n[i].typ.skipTypes({tyVar, tySink, tyLent, tyGenericInst, tyAlias})): destMightOwn(c, dest, n[i]) else: # something we cannot handle: dest.flags.incl preventCursor proc noCursor(c: var Partitions, s: PSym) = let vid = variableId(c, s) if vid >= 0: c.s[vid].flags.incl preventCursor proc pretendOwnsData(c: var Partitions, s: PSym) = let vid = variableId(c, s) if vid >= 0: c.s[vid].flags.incl ownsData const explainCursors = false proc isConstSym(s: PSym): bool = result = s.kind in {skConst, skLet} or isConstParam(s) proc toString(n: PNode): string = if n.kind == nkEmpty: result = "<empty>" else: result = $n proc borrowFrom(c: var Partitions; dest: PSym; src: PNode) = const url = "see https://nim-lang.github.io/Nim/manual_experimental.html#view-types-algorithm-path-expressions for details" let s = pathExpr(src, c.owner) if s == nil: localError(c.g.config, src.info, "cannot borrow from " & src.toString & ", it is not a path expression; " & url) elif s.kind == nkSym: if dest.kind == skResult: if s.sym.kind != skParam or s.sym.position != 0: localError(c.g.config, src.info, "'result' must borrow from the first parameter") let vid = variableId(c, dest) if vid >= 0: var sourceIdx = variableId(c, s.sym) if sourceIdx < 0: sourceIdx = c.s.len c.s.add VarIndex(con: Connection(kind: isEmptyRoot), sym: s.sym, reassignedTo: 0, aliveStart: MinTime, aliveEnd: MaxTime) c.s[vid].borrowsFrom.add sourceIdx if isConstSym(s.sym): c.s[vid].flags.incl viewBorrowsFromConst else: let vid = variableId(c, dest) if vid >= 0: c.s[vid].flags.incl viewBorrowsFromConst #discard "a valid borrow location that is a deeply constant expression so we have nothing to track" proc borrowingCall(c: var Partitions; destType: PType; n: PNode; i: int) = let v = pathExpr(n[i], c.owner) if v != nil and v.kind == nkSym: when false: let isView = directViewType(destType) == immutableView if n[0].kind == nkSym and n[0].sym.name.s == "[]=": localError(c.g.config, n[i].info, "attempt to mutate an immutable view") for j in i+1..<n.len: if getMagic(n[j]) == mSlice: borrowFrom(c, v.sym, n[j]) else: localError(c.g.config, n[i].info, "cannot determine the target of the borrow") proc borrowingAsgn(c: var Partitions; dest, src: PNode) = proc mutableParameter(n: PNode): bool {.inline.} = result = n.kind == nkSym and n.sym.kind == skParam and n.sym.typ.kind == tyVar if dest.kind == nkSym: if directViewType(dest.typ) != noView: borrowFrom(c, dest.sym, src) else: let viewOrigin = pathExpr(dest, c.owner) if viewOrigin != nil and viewOrigin.kind == nkSym: let viewSym = viewOrigin.sym let directView = directViewType(dest[0].typ) # check something like result[first] = toOpenArray(s, first, last-1) # so we don't need to iterate the original type let originSymbolView = directViewType(viewSym.typ) # find the original symbol which preserves the view type # var foo: var Object = a # foo.id = 777 # the type of foo is no view, so we need # to check the original symbol let viewSets = {directView, originSymbolView} if viewSets * {mutableView, immutableView} != {}: # we do not borrow, but we use the view to mutate the borrowed # location: let vid = variableId(c, viewSym) if vid >= 0: c.s[vid].flags.incl viewDoesMutate #[of immutableView: if dest.kind == nkBracketExpr and dest[0].kind == nkHiddenDeref and mutableParameter(dest[0][0]): discard "remains a mutable location anyhow" else: localError(c.g.config, dest.info, "attempt to mutate a borrowed location from an immutable view") ]# else: discard "nothing to do" proc containsPointer(t: PType): bool = proc wrap(t: PType): bool {.nimcall.} = t.kind in {tyRef, tyPtr} result = types.searchTypeFor(t, wrap) proc deps(c: var Partitions; dest, src: PNode) = if borrowChecking in c.goals: borrowingAsgn(c, dest, src) var targets, sources: seq[(PSym, int)] allRoots(dest, targets, 0) allRoots(src, sources, 0) let destIsComplex = containsPointer(dest.typ) for t in targets: if dest.kind != nkSym and c.inNoSideEffectSection == 0: potentialMutation(c, t[0], t[1], dest.info) if destIsComplex: for s in sources: connect(c, t[0], s[0], dest.info) if cursorInference in c.goals and src.kind != nkEmpty: let d = pathExpr(dest, c.owner) if d != nil and d.kind == nkSym: let vid = variableId(c, d.sym) if vid >= 0: destMightOwn(c, c.s[vid], src) for source in sources: let s = source[0] if s == d.sym: discard "assignments like: it = it.next are fine" elif {sfGlobal, sfThread} * s.flags != {} or hasDisabledAsgn(c.g, s.typ): # do not borrow from a global variable or from something with a # disabled assignment operator. c.s[vid].flags.incl preventCursor when explainCursors: echo "A not a cursor: ", d.sym, " ", s else: let srcid = variableId(c, s) if srcid >= 0: if s.kind notin {skResult, skParam} and ( c.s[srcid].aliveEnd < c.s[vid].aliveEnd): # you cannot borrow from a local that lives shorter than 'vid': when explainCursors: echo "B not a cursor ", d.sym, " ", c.s[srcid].aliveEnd, " ", c.s[vid].aliveEnd c.s[vid].flags.incl preventCursor elif {isReassigned, preventCursor} * c.s[srcid].flags != {}: # you cannot borrow from something that is re-assigned: when explainCursors: echo "C not a cursor ", d.sym, " ", c.s[srcid].flags, " reassignedTo ", c.s[srcid].reassignedTo c.s[vid].flags.incl preventCursor elif c.s[srcid].reassignedTo != 0 and c.s[srcid].reassignedTo != d.sym.id: when explainCursors: echo "D not a cursor ", d.sym, " reassignedTo ", c.s[srcid].reassignedTo c.s[vid].flags.incl preventCursor proc potentialMutationViaArg(c: var Partitions; n: PNode; callee: PType) = if constParameters in c.goals and tfNoSideEffect in callee.flags: discard "we know there are no hidden mutations through an immutable parameter" elif c.inNoSideEffectSection == 0 and containsPointer(n.typ): var roots: seq[(PSym, int)] allRoots(n, roots, RootEscapes) for r in roots: potentialMutation(c, r[0], r[1], n.info) proc traverse(c: var Partitions; n: PNode) = inc c.abstractTime case n.kind of nkLetSection, nkVarSection: for child in n: let last = lastSon(child) traverse(c, last) if child.kind == nkVarTuple and last.kind in {nkPar, nkTupleConstr}: if child.len-2 != last.len: return for i in 0..<child.len-2: #registerVariable(c, child[i]) deps(c, child[i], last[i]) else: for i in 0..<child.len-2: #registerVariable(c, child[i]) deps(c, child[i], last) of nkAsgn, nkFastAsgn, nkSinkAsgn: traverse(c, n[0]) inc c.inAsgnSource traverse(c, n[1]) dec c.inAsgnSource deps(c, n[0], n[1]) of nkSym: dec c.abstractTime of nodesToIgnoreSet: dec c.abstractTime discard "do not follow the construct" of nkCallKinds: for child in n: traverse(c, child) let parameters = n[0].typ let L = if parameters != nil: parameters.len else: 0 let m = getMagic(n) for i in 1..<n.len: let it = n[i] if i < L: let paramType = parameters[i].skipTypes({tyGenericInst, tyAlias}) if not paramType.isCompileTimeOnly and paramType.kind in {tyVar, tySink, tyOwned}: var roots: seq[(PSym, int)] allRoots(it, roots, RootEscapes) if paramType.kind == tyVar: if c.inNoSideEffectSection == 0: for r in roots: potentialMutation(c, r[0], r[1], it.info) for r in roots: noCursor(c, r[0]) if borrowChecking in c.goals: # a call like 'result.add toOpenArray()' can also be a borrow # operation. We know 'paramType' is a tyVar and we really care if # 'paramType[0]' is still a view type, this is not a typo! if directViewType(paramType[0]) == noView and classifyViewType(paramType[0]) != noView: borrowingCall(c, paramType[0], n, i) elif m == mNone: potentialMutationViaArg(c, n[i], parameters) of nkAddr, nkHiddenAddr: traverse(c, n[0]) when false: # XXX investigate if this is required, it doesn't look # like it is! var roots: seq[(PSym, int)] allRoots(n[0], roots, RootEscapes) for r in roots: potentialMutation(c, r[0], r[1], it.info) of nkTupleConstr, nkBracket: for child in n: traverse(c, child) if c.inAsgnSource > 0: for i in 0..<n.len: if n[i].kind == nkSym: # we assume constructions with cursors are better without # the cursors because it's likely we can move then, see # test arc/topt_no_cursor.nim pretendOwnsData(c, n[i].sym) of nkObjConstr: for child in n: traverse(c, child) if c.inAsgnSource > 0: for i in 1..<n.len: let it = n[i].skipColon if it.kind == nkSym: # we assume constructions with cursors are better without # the cursors because it's likely we can move then, see # test arc/topt_no_cursor.nim pretendOwnsData(c, it.sym) of nkPragmaBlock: let pragmaList = n[0] var enforceNoSideEffects = 0 for i in 0..<pragmaList.len: if isNoSideEffectPragma(pragmaList[i]): enforceNoSideEffects = 1 break inc c.inNoSideEffectSection, enforceNoSideEffects traverse(c, n.lastSon) dec c.inNoSideEffectSection, enforceNoSideEffects of nkWhileStmt, nkForStmt, nkParForStmt: for child in n: traverse(c, child) # analyse loops twice so that 'abstractTime' suffices to detect cases # like: # while cond: # mutate(graph) # connect(graph, cursorVar) for child in n: traverse(c, child) if n.kind == nkWhileStmt: traverse(c, n[0]) # variables in while condition has longer alive time than local variables # in the while loop body of nkDefer: if c.processDefer: for child in n: traverse(c, child) else: for child in n: traverse(c, child) proc markAsReassigned(c: var Partitions; vid: int) {.inline.} = c.s[vid].flags.incl isReassigned if c.inConditional > 0 and c.inLoop > 0: # bug #17033: live ranges with loops and conditionals are too # complex for our current analysis, so we prevent the cursorfication. c.s[vid].flags.incl isConditionallyReassigned proc computeLiveRanges(c: var Partitions; n: PNode) = # first pass: Compute live ranges for locals. # **Watch out!** We must traverse the tree like 'traverse' does # so that the 'c.abstractTime' is consistent. inc c.abstractTime case n.kind of nkLetSection, nkVarSection: for child in n: let last = lastSon(child) computeLiveRanges(c, last) if child.kind == nkVarTuple and last.kind in {nkPar, nkTupleConstr}: if child.len-2 != last.len: return for i in 0..<child.len-2: registerVariable(c, child[i]) #deps(c, child[i], last[i]) else: for i in 0..<child.len-2: registerVariable(c, child[i]) #deps(c, child[i], last) of nkAsgn, nkFastAsgn, nkSinkAsgn: computeLiveRanges(c, n[0]) computeLiveRanges(c, n[1]) if n[0].kind == nkSym: let vid = variableId(c, n[0].sym) if vid >= 0: if n[1].kind == nkSym and (c.s[vid].reassignedTo == 0 or c.s[vid].reassignedTo == n[1].sym.id): c.s[vid].reassignedTo = n[1].sym.id if c.inConditional > 0 and c.inLoop > 0: # bug #22200: live ranges with loops and conditionals are too # complex for our current analysis, so we prevent the cursorfication. c.s[vid].flags.incl isConditionallyReassigned else: markAsReassigned(c, vid) of nkSym: dec c.abstractTime if n.sym.kind in {skVar, skResult, skTemp, skLet, skForVar, skParam}: let id = variableId(c, n.sym) if id >= 0: c.s[id].aliveEnd = max(c.s[id].aliveEnd, c.abstractTime) if n.sym.kind == skResult: c.s[id].aliveStart = min(c.s[id].aliveStart, c.abstractTime) of nodesToIgnoreSet: dec c.abstractTime discard "do not follow the construct" of nkCallKinds: for child in n: computeLiveRanges(c, child) let parameters = n[0].typ let L = if parameters != nil: parameters.len else: 0 for i in 1..<n.len: let it = n[i] if it.kind == nkSym and i < L: let paramType = parameters[i].skipTypes({tyGenericInst, tyAlias}) if not paramType.isCompileTimeOnly and paramType.kind == tyVar: let vid = variableId(c, it.sym) if vid >= 0: markAsReassigned(c, vid) of nkAddr, nkHiddenAddr: computeLiveRanges(c, n[0]) if n[0].kind == nkSym: let vid = variableId(c, n[0].sym) if vid >= 0: c.s[vid].flags.incl preventCursor of nkPragmaBlock: computeLiveRanges(c, n.lastSon) of nkWhileStmt, nkForStmt, nkParForStmt: for child in n: computeLiveRanges(c, child) # analyse loops twice so that 'abstractTime' suffices to detect cases # like: # while cond: # mutate(graph) # connect(graph, cursorVar) inc c.inLoop for child in n: computeLiveRanges(c, child) dec c.inLoop if n.kind == nkWhileStmt: computeLiveRanges(c, n[0]) # variables in while condition has longer alive time than local variables # in the while loop body of nkElifBranch, nkElifExpr, nkElse, nkOfBranch: inc c.inConditional for child in n: computeLiveRanges(c, child) dec c.inConditional of nkDefer: if c.processDefer: for child in n: computeLiveRanges(c, child) else: c.defers.add n else: for child in n: computeLiveRanges(c, child) proc computeGraphPartitions*(s: PSym; n: PNode; g: ModuleGraph; goals: set[Goal]): Partitions = result = Partitions(owner: s, g: g, goals: goals) if s.kind notin {skModule, skMacro}: let params = s.typ.n for i in 1..<params.len: registerParam(result, params[i]) if resultPos < s.ast.safeLen: registerResult(result, s.ast[resultPos]) computeLiveRanges(result, n) result.processDefer = true for i in countdown(len(result.defers)-1, 0): computeLiveRanges(result, result.defers[i]) result.processDefer = false # restart the timer for the second pass: result.abstractTime = AbstractTime 0 traverse(result, n) result.processDefer = true for i in countdown(len(result.defers)-1, 0): traverse(result, result.defers[i]) result.processDefer = false proc dangerousMutation(g: MutationInfo; v: VarIndex): bool = #echo "range ", v.aliveStart, " .. ", v.aliveEnd, " ", v.sym if {isMutated, isMutatedByVarParam} * g.flags != {}: for m in g.mutations: #echo "mutation ", m if m in v.aliveStart..v.aliveEnd: return true return false proc cannotBorrow(config: ConfigRef; s: PSym; g: MutationInfo) = var m = "cannot borrow " & s.name.s & "; what it borrows from is potentially mutated" if g.mutatedHere != unknownLineInfo: m.add "\n" m.add config $ g.mutatedHere m.add " the mutation is here" if g.connectedVia != unknownLineInfo: m.add "\n" m.add config $ g.connectedVia m.add " is the statement that connected the mutation to the parameter" localError(config, s.info, m) proc checkBorrowedLocations*(par: var Partitions; body: PNode; config: ConfigRef) = for i in 0 ..< par.s.len: let v = par.s[i].sym if v.kind != skParam and classifyViewType(v.typ) != noView: let rid = root(par, i) if rid >= 0: var constViolation = false for b in par.s[rid].borrowsFrom: let sid = root(par, b) if sid >= 0: if par.s[sid].con.kind == isRootOf and dangerousMutation(par.graphs[par.s[sid].con.graphIndex], par.s[i]): cannotBorrow(config, v, par.graphs[par.s[sid].con.graphIndex]) if par.s[sid].sym.kind != skParam and par.s[sid].aliveEnd < par.s[rid].aliveEnd: localError(config, v.info, "'" & v.name.s & "' borrows from location '" & par.s[sid].sym.name.s & "' which does not live long enough") if viewDoesMutate in par.s[rid].flags and isConstSym(par.s[sid].sym): localError(config, v.info, "'" & v.name.s & "' borrows from the immutable location '" & par.s[sid].sym.name.s & "' and attempts to mutate it") constViolation = true if {viewDoesMutate, viewBorrowsFromConst} * par.s[rid].flags == {viewDoesMutate, viewBorrowsFromConst} and not constViolation: # we do not track the constant expressions we allow to borrow from so # we can only produce a more generic error message: localError(config, v.info, "'" & v.name.s & "' borrows from an immutable location and attempts to mutate it") #if par.s[rid].con.kind == isRootOf and dangerousMutation(par.graphs[par.s[rid].con.graphIndex], par.s[i]): # cannotBorrow(config, s, par.graphs[par.s[rid].con.graphIndex]) proc computeCursors*(s: PSym; n: PNode; g: ModuleGraph) = var par = computeGraphPartitions(s, n, g, {cursorInference}) for i in 0 ..< par.s.len: let v = addr(par.s[i]) if v.flags * {ownsData, preventCursor, isConditionallyReassigned} == {} and v.sym.kind notin {skParam, skResult} and v.sym.flags * {sfThread, sfGlobal} == {} and hasDestructor(v.sym.typ) and v.sym.typ.skipTypes({tyGenericInst, tyAlias}).kind != tyOwned: let rid = root(par, i) if par.s[rid].con.kind == isRootOf and dangerousMutation(par.graphs[par.s[rid].con.graphIndex], par.s[i]): discard "cannot cursor into a graph that is mutated" else: v.sym.flags.incl sfCursor when false: echo "this is now a cursor ", v.sym, " ", par.s[rid].flags, " ", g.config $ v.sym.info


context:
space:
mode: