diff options
Diffstat (limited to 'compiler/nilcheck.nim')
| -rw-r--r-- | compiler/nilcheck.nim | 1387 |
1 files changed, 1387 insertions, 0 deletions
diff --git a/compiler/nilcheck.nim b/compiler/nilcheck.nim new file mode 100644 index 000000000..7e0efc34b --- /dev/null +++ b/compiler/nilcheck.nim @@ -0,0 +1,1387 @@ +# +# +# The Nim Compiler +# (c) Copyright 2017 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +import ast, renderer, msgs, options, lineinfos, idents, treetab +import std/[intsets, tables, sequtils, strutils, sets, strformat, hashes] + +when defined(nimPreviewSlimSystem): + import std/assertions + +# IMPORTANT: notes not up to date, i'll update this comment again +# +# notes: +# +# Env: int => nilability +# a = b +# nilability a <- nilability b +# deref a +# if Nil error is nil +# if MaybeNil error might be nil, hint add if isNil +# if Safe fine +# fun(arg: A) +# nilability arg <- for ref MaybeNil, for not nil or others Safe +# map is env? +# a or b +# each one forks a different env +# result = union(envL, envR) +# a and b +# b forks a's env +# if a: code +# result = union(previousEnv after not a, env after code) +# if a: b else: c +# result = union(env after b, env after c) +# result = b +# nilability result <- nilability b, if return type is not nil and result not safe, error +# return b +# as result = b +# try: a except: b finally: c +# in b and c env is union of all possible try first n lines, after union of a and b and c +# keep in mind canRaise and finally +# case a: of b: c +# similar to if +# call(arg) +# if it returns ref, assume it's MaybeNil: hint that one can add not nil to the return type +# call(var arg) # zahary comment +# if arg is ref, assume it's MaybeNil after call +# loop +# union of env for 0, 1, 2 iterations as Herb Sutter's paper +# why 2? +# return +# if something: stop (break return etc) +# is equivalent to if something: .. else: remain +# new(ref) +# ref becomes Safe +# objConstr(a: b) +# returns safe +# each check returns its nilability and map + +type + SeqOfDistinct[T, U] = distinct seq[U] + +# TODO use distinct base type instead of int? +func `[]`[T, U](a: SeqOfDistinct[T, U], index: T): U = + (seq[U])(a)[index.int] + +proc `[]=`[T, U](a: var SeqOfDistinct[T, U], index: T, value: U) = + ((seq[U])(a))[index.int] = value + +func `[]`[T, U](a: var SeqOfDistinct[T, U], index: T): var U = + (seq[U])(a)[index.int] + +func len[T, U](a: SeqOfDistinct[T, U]): T = + (seq[U])(a).len.T + +func low[T, U](a: SeqOfDistinct[T, U]): T = + (seq[U])(a).low.T + +func high[T, U](a: SeqOfDistinct[T, U]): T = + (seq[U])(a).high.T + +proc setLen[T, U](a: var SeqOfDistinct[T, U], length: T) = + ((seq[U])(a)).setLen(length.Natural) + + +proc newSeqOfDistinct[T, U](length: T = 0.T): SeqOfDistinct[T, U] = + (SeqOfDistinct[T, U])(newSeq[U](length.int)) + +func newSeqOfDistinct[T, U](length: int = 0): SeqOfDistinct[T, U] = + # newSeqOfDistinct(length.T) + # ? newSeqOfDistinct[T, U](length.T) + (SeqOfDistinct[T, U])(newSeq[U](length)) + +iterator items[T, U](a: SeqOfDistinct[T, U]): U = + for element in (seq[U])(a): + yield element + +iterator pairs[T, U](a: SeqOfDistinct[T, U]): (T, U) = + for i, element in (seq[U])(a): + yield (i.T, element) + +func `$`[T, U](a: SeqOfDistinct[T, U]): string = + $((seq[U])(a)) + +proc add*[T, U](a: var SeqOfDistinct[T, U], value: U) = + ((seq[U])(a)).add(value) + +type + ## a hashed representation of a node: should be equal for structurally equal nodes + Symbol = distinct int + + ## the index of an expression in the pre-indexed sequence of those + ExprIndex = distinct int16 + + ## the set index + SetIndex = distinct int + + ## transition kind: + ## what was the reason for changing the nilability of an expression + ## useful for error messages and showing why an expression is being detected as nil / maybe nil + TransitionKind = enum TArg, TAssign, TType, TNil, TVarArg, TResult, TSafe, TPotentialAlias, TDependant + + ## keep history for each transition + History = object + info: TLineInfo ## the location + nilability: Nilability ## the nilability + kind: TransitionKind ## what kind of transition was that + node: PNode ## the node of the expression + + ## the context for the checker: an instance for each procedure + NilCheckerContext = ref object + # abstractTime: AbstractTime + # partitions: Partitions + # symbolGraphs: Table[Symbol, ] + symbolIndices: Table[Symbol, ExprIndex] ## index for each symbol + expressions: SeqOfDistinct[ExprIndex, PNode] ## a sequence of pre-indexed expressions + dependants: SeqOfDistinct[ExprIndex, IntSet] ## expr indices for expressions which are compound and based on others + warningLocations: HashSet[TLineInfo] ## warning locations to check we don't warn twice for stuff like warnings in for loops + idgen: IdGenerator ## id generator + config: ConfigRef ## the config of the compiler + + ## a map that is containing the current nilability for usually a branch + ## and is pointing optionally to a parent map: they make a stack of maps + NilMap = ref object + expressions: SeqOfDistinct[ExprIndex, Nilability] ## the expressions with the same order as in NilCheckerContext + history: SeqOfDistinct[ExprIndex, seq[History]] ## history for each of them + # what about gc and refs? + setIndices: SeqOfDistinct[ExprIndex, SetIndex] ## set indices for each expression + sets: SeqOfDistinct[SetIndex, IntSet] ## disjoint sets with the aliased expressions + parent: NilMap ## the parent map + + ## Nilability : if a value is nilable. + ## we have maybe nil and nil, so we can differentiate between + ## cases where we know for sure a value is nil and not + ## otherwise we can have Safe, MaybeNil + ## Parent: is because we just use a sequence with the same length + ## instead of a table, and we need to check if something was initialized + ## at all: if Parent is set, then you need to check the parent nilability + ## if the parent is nil, then for now we return MaybeNil + ## unreachable is the result of add(Safe, Nil) and others + ## it is a result of no states left, so it's usually e.g. in unreachable else branches? + Nilability* = enum Parent, Safe, MaybeNil, Nil, Unreachable + + ## check + Check = object + nilability: Nilability + map: NilMap + elements: seq[(PNode, Nilability)] + + +# useful to have known resultId so we can set it in the beginning and on return +const resultId: Symbol = (-1).Symbol +const resultExprIndex: ExprIndex = 0.ExprIndex +const noSymbol = (-2).Symbol + +func `<`*(a: ExprIndex, b: ExprIndex): bool = + a.int16 < b.int16 + +func `<=`*(a: ExprIndex, b: ExprIndex): bool = + a.int16 <= b.int16 + +func `>`*(a: ExprIndex, b: ExprIndex): bool = + a.int16 > b.int16 + +func `>=`*(a: ExprIndex, b: ExprIndex): bool = + a.int16 >= b.int16 + +func `==`*(a: ExprIndex, b: ExprIndex): bool = + a.int16 == b.int16 + +func `$`*(a: ExprIndex): string = + $(a.int16) + +func `+`*(a: ExprIndex, b: ExprIndex): ExprIndex = + (a.int16 + b.int16).ExprIndex + +# TODO overflowing / < 0? +func `-`*(a: ExprIndex, b: ExprIndex): ExprIndex = + (a.int16 - b.int16).ExprIndex + +func `$`*(a: SetIndex): string = + $(a.int) + +func `==`*(a: SetIndex, b: SetIndex): bool = + a.int == b.int + +func `+`*(a: SetIndex, b: SetIndex): SetIndex = + (a.int + b.int).SetIndex + +# TODO over / under limit? +func `-`*(a: SetIndex, b: SetIndex): SetIndex = + (a.int - b.int).SetIndex + +proc check(n: PNode, ctx: NilCheckerContext, map: NilMap): Check +proc checkCondition(n: PNode, ctx: NilCheckerContext, map: NilMap, reverse: bool, base: bool): NilMap + +# the NilMap structure + +proc newNilMap(parent: NilMap = nil, count: int = -1): NilMap = + var expressionsCount = 0 + if count != -1: + expressionsCount = count + elif not parent.isNil: + expressionsCount = parent.expressions.len.int + result = NilMap( + expressions: newSeqOfDistinct[ExprIndex, Nilability](expressionsCount), + history: newSeqOfDistinct[ExprIndex, seq[History]](expressionsCount), + setIndices: newSeqOfDistinct[ExprIndex, SetIndex](expressionsCount), + parent: parent) + if parent.isNil: + for i, expr in result.expressions: + result.setIndices[i] = i.SetIndex + var newSet = initIntSet() + newSet.incl(i.int) + result.sets.add(newSet) + else: + for i, exprs in parent.sets: + result.sets.add(exprs) + for i, index in parent.setIndices: + result.setIndices[i] = index + # result.sets = parent.sets + # if not parent.isNil: + # # optimize []? + # result.expressions = parent.expressions + # result.history = parent.history + # result.sets = parent.sets + # result.base = if parent.isNil: result else: parent.base + +proc `[]`(map: NilMap, index: ExprIndex): Nilability = + if index < 0.ExprIndex or index >= map.expressions.len: + return MaybeNil + var now = map + while not now.isNil: + if now.expressions[index] != Parent: + return now.expressions[index] + now = now.parent + return MaybeNil + +proc history(map: NilMap, index: ExprIndex): seq[History] = + if index < map.expressions.len: + map.history[index] + else: + @[] + + +# helpers for debugging + +# import macros + +# echo-s only when nilDebugInfo is defined +# macro aecho*(a: varargs[untyped]): untyped = +# var e = nnkCall.newTree(ident"echo") +# for b in a: +# e.add(b) +# result = quote: +# when defined(nilDebugInfo): +# `e` + +# end of helpers for debugging + + +proc symbol(n: PNode): Symbol +func `$`(map: NilMap): string +proc reverseDirect(map: NilMap): NilMap +proc checkBranch(n: PNode, ctx: NilCheckerContext, map: NilMap): Check +proc hasUnstructuredControlFlowJump(n: PNode): bool + +proc symbol(n: PNode): Symbol = + ## returns a Symbol for each expression + ## the goal is to get an unique Symbol + ## but we have to ensure hashTree does it as we expect + case n.kind: + of nkIdent: + # TODO ensure no idents get passed to symbol + result = noSymbol + of nkSym: + if n.sym.kind == skResult: # credit to disruptek for showing me that + result = resultId + else: + result = n.sym.id.Symbol + of nkHiddenAddr, nkAddr: + result = symbol(n[0]) + else: + result = hashTree(n).Symbol + # echo "symbol ", n, " ", n.kind, " ", result.int + +func `$`(map: NilMap): string = + result = "" + var now = map + var stack: seq[NilMap] = @[] + while not now.isNil: + stack.add(now) + now = now.parent + result.add("### start\n") + for i in 0 .. stack.len - 1: + now = stack[i] + result.add(" ###\n") + for index, value in now.expressions: + result.add(&" {index} {value}\n") + result.add "### end\n" + +proc namedMapDebugInfo(ctx: NilCheckerContext, map: NilMap): string = + result = "" + var now = map + var stack: seq[NilMap] = @[] + while not now.isNil: + stack.add(now) + now = now.parent + result.add("### start\n") + for i in 0 .. stack.len - 1: + now = stack[i] + result.add(" ###\n") + for index, value in now.expressions: + let name = ctx.expressions[index] + result.add(&" {name} {index} {value}\n") + result.add("### end\n") + +proc namedSetsDebugInfo(ctx: NilCheckerContext, map: NilMap): string = + result = "### sets " + for index, setIndex in map.setIndices: + var aliasSet = map.sets[setIndex] + result.add("{") + let expressions = aliasSet.mapIt($ctx.expressions[it.ExprIndex]) + result.add(join(expressions, ", ")) + result.add("} ") + result.add("\n") + +proc namedMapAndSetsDebugInfo(ctx: NilCheckerContext, map: NilMap): string = + result = namedMapDebugInfo(ctx, map) & namedSetsDebugInfo(ctx, map) + + + +const noExprIndex = (-1).ExprIndex +const noSetIndex = (-1).SetIndex + +proc `==`(a: Symbol, b: Symbol): bool = + a.int == b.int + +func `$`(a: Symbol): string = + $(a.int) + +template isConstBracket(n: PNode): bool = + n.kind == nkBracketExpr and n[1].kind in nkLiterals + +proc index(ctx: NilCheckerContext, n: PNode): ExprIndex = + # echo "n ", n, " ", n.kind + let a = symbol(n) + if ctx.symbolIndices.hasKey(a): + return ctx.symbolIndices[a] + else: + #for a, e in ctx.expressions: + # echo a, " ", e + #echo n.kind + # internalError(ctx.config, n.info, "expected " & $a & " " & $n & " to have a index") + return noExprIndex + # + #ctx.symbolIndices[symbol(n)] + + +proc aliasSet(ctx: NilCheckerContext, map: NilMap, n: PNode): IntSet = + result = map.sets[map.setIndices[ctx.index(n)]] + +proc aliasSet(ctx: NilCheckerContext, map: NilMap, index: ExprIndex): IntSet = + result = map.sets[map.setIndices[index]] + + + +proc store(map: NilMap, ctx: NilCheckerContext, index: ExprIndex, value: Nilability, kind: TransitionKind, info: TLineInfo, node: PNode = nil) = + if index == noExprIndex: + return + map.expressions[index] = value + map.history[index].add(History(info: info, kind: kind, node: node, nilability: value)) + #echo node, " ", index, " ", value + #echo ctx.namedMapAndSetsDebugInfo(map) + #for a, b in map.sets: + # echo a, " ", b + # echo map + + var exprAliases = aliasSet(ctx, map, index) + for a in exprAliases: + if a.ExprIndex != index: + #echo "alias ", a, " ", index + map.expressions[a.ExprIndex] = value + if value == Safe: + map.history[a.ExprIndex] = @[] + else: + map.history[a.ExprIndex].add(History(info: info, kind: TPotentialAlias, node: node, nilability: value)) + +proc moveOut(ctx: NilCheckerContext, map: NilMap, target: PNode) = + #echo "move out ", target + var targetIndex = ctx.index(target) + var targetSetIndex = map.setIndices[targetIndex] + if targetSetIndex != noSetIndex: + var targetSet = map.sets[targetSetIndex] + if targetSet.len > 1: + var other: ExprIndex = default(ExprIndex) + + for element in targetSet: + if element.ExprIndex != targetIndex: + other = element.ExprIndex + break + # map.sets[element].excl(targetIndex) + map.sets[map.setIndices[other]].excl(targetIndex.int) + var newSet = initIntSet() + newSet.incl(targetIndex.int) + map.sets.add(newSet) + map.setIndices[targetIndex] = map.sets.len - 1.SetIndex + +proc moveOutDependants(ctx: NilCheckerContext, map: NilMap, node: PNode) = + let index = ctx.index(node) + for dependant in ctx.dependants[index]: + moveOut(ctx, map, ctx.expressions[dependant.ExprIndex]) + +proc storeDependants(ctx: NilCheckerContext, map: NilMap, node: PNode, value: Nilability) = + let index = ctx.index(node) + for dependant in ctx.dependants[index]: + map.store(ctx, dependant.ExprIndex, value, TDependant, node.info, node) + +proc move(ctx: NilCheckerContext, map: NilMap, target: PNode, assigned: PNode) = + #echo "move ", target, " ", assigned + var targetIndex = ctx.index(target) + var assignedIndex: ExprIndex + var targetSetIndex = map.setIndices[targetIndex] + var assignedSetIndex: SetIndex + if assigned.kind == nkSym: + assignedIndex = ctx.index(assigned) + assignedSetIndex = map.setIndices[assignedIndex] + else: + assignedIndex = noExprIndex + assignedSetIndex = noSetIndex + if assignedIndex == noExprIndex: + moveOut(ctx, map, target) + elif targetSetIndex != assignedSetIndex: + map.sets[targetSetIndex].excl(targetIndex.int) + map.sets[assignedSetIndex].incl(targetIndex.int) + map.setIndices[targetIndex] = assignedSetIndex + +# proc hasKey(map: NilMap, ): bool = +# var now = map +# result = false +# while not now.isNil: +# if now.locals.hasKey(graphIndex): +# return true +# now = now.previous + +iterator pairs(map: NilMap): (ExprIndex, Nilability) = + for index, value in map.expressions: + yield (index, map[index]) + +proc copyMap(map: NilMap): NilMap = + if map.isNil: + return nil + result = newNilMap(map.parent) # no need for copy? if we change only this + result.expressions = map.expressions + result.history = map.history + result.sets = map.sets + result.setIndices = map.setIndices + +using + n: PNode + conf: ConfigRef + ctx: NilCheckerContext + map: NilMap + +proc typeNilability(typ: PType): Nilability + +# maybe: if canRaise, return MaybeNil ? +# no, because the target might be safe already +# with or without an exception +proc checkCall(n, ctx, map): Check = + # checks each call + # special case for new(T) -> result is always Safe + # for the others it depends on the return type of the call + # check args and handle possible mutations + + var isNew = false + result = Check(map: map) + for i, child in n: + discard check(child, ctx, map) + + if i > 0: + # var args make a new map with MaybeNil for our node + # as it might have been mutated + # TODO similar for normal refs and fields: find dependent exprs: brackets + + if child.kind == nkHiddenAddr and not child.typ.isNil and child.typ.kind == tyVar and child.typ.elementType.kind == tyRef: + if not isNew: + result.map = newNilMap(map) + isNew = true + # result.map[$child] = MaybeNil + var arg = child + while arg.kind == nkHiddenAddr: + arg = arg[0] + let a = ctx.index(arg) + if a != noExprIndex: + moveOut(ctx, result.map, arg) + moveOutDependants(ctx, result.map, arg) + result.map.store(ctx, a, MaybeNil, TVarArg, n.info, arg) + storeDependants(ctx, result.map, arg, MaybeNil) + elif not child.typ.isNil and child.typ.kind == tyRef: + if child.kind in {nkSym, nkDotExpr} or isConstBracket(child): + let a = ctx.index(child) + if ctx.dependants[a].len > 0: + if not isNew: + result.map = newNilMap(map) + isNew = true + moveOutDependants(ctx, result.map, child) + storeDependants(ctx, result.map, child, MaybeNil) + + if n[0].kind == nkSym and n[0].sym.magic == mNew: + # new hidden deref? + var value = if n[1].kind == nkHiddenDeref: n[1][0] else: n[1] + let b = ctx.index(value) + result.map.store(ctx, b, Safe, TAssign, value.info, value) + result.nilability = Safe + else: + # echo "n ", n, " ", n.typ.isNil + if not n.typ.isNil: + result.nilability = typeNilability(n.typ) + else: + result.nilability = Safe + # echo result.map + +template event(b: History): string = + case b.kind: + of TArg: "param with nilable type" + of TNil: "it returns true for isNil" + of TAssign: "assigns a value which might be nil" + of TVarArg: "passes it as a var arg which might change to nil" + of TResult: "it is nil by default" + of TType: "it has ref type" + of TSafe: "it is safe here as it returns false for isNil" + of TPotentialAlias: "it might be changed directly or through an alias" + of TDependant: "it might be changed because its base might be changed" + +proc derefWarning(n, ctx, map; kind: Nilability) = + ## a warning for potentially unsafe dereference + if n.info in ctx.warningLocations: + return + ctx.warningLocations.incl(n.info) + var a: seq[History] = @[] + if n.kind == nkSym: + a = history(map, ctx.index(n)) + var res = "" + var issue = case kind: + of Nil: "it is nil" + of MaybeNil: "it might be nil" + of Unreachable: "it is unreachable" + else: "" + res.add("can't deref " & $n & ", " & issue) + if a.len > 0: + res.add("\n") + for b in a: + res.add(" " & event(b) & " on line " & $b.info.line & ":" & $b.info.col) + message(ctx.config, n.info, warnStrictNotNil, res) + +proc handleNilability(check: Check; n, ctx, map) = + ## handle the check: + ## register a warning(error?) for Nil/MaybeNil + case check.nilability: + of Nil: + derefWarning(n, ctx, map, Nil) + of MaybeNil: + derefWarning(n, ctx, map, MaybeNil) + of Unreachable: + derefWarning(n, ctx, map, Unreachable) + else: + when defined(nilDebugInfo): + message(ctx.config, n.info, hintUser, "can deref " & $n) + +proc checkDeref(n, ctx, map): Check = + ## check dereference: deref n should be ok only if n is Safe + result = check(n[0], ctx, map) + + handleNilability(result, n[0], ctx, map) + + +proc checkRefExpr(n, ctx; check: Check): Check = + ## check ref expressions: TODO not sure when this happens + result = check + if n.typ.kind != tyRef: + result.nilability = typeNilability(n.typ) + elif tfNotNil notin n.typ.flags: + # echo "ref key ", n, " ", n.kind + if n.kind in {nkSym, nkDotExpr} or isConstBracket(n): + let key = ctx.index(n) + result.nilability = result.map[key] + elif n.kind == nkBracketExpr: + # sometimes false positive + result.nilability = MaybeNil + else: + # sometimes maybe false positive + result.nilability = MaybeNil + +proc checkDotExpr(n, ctx, map): Check = + ## check dot expressions: make sure we can dereference the base + result = check(n[0], ctx, map) + result = checkRefExpr(n, ctx, result) + +proc checkBracketExpr(n, ctx, map): Check = + ## check bracket expressions: make sure we can dereference the base + result = check(n[0], ctx, map) + # if might be deref: [] == *(a + index) for cstring + handleNilability(result, n[0], ctx, map) + result = check(n[1], ctx, result.map) + result = checkRefExpr(n, ctx, result) + # echo n, " ", result.nilability + + +template union(l: Nilability, r: Nilability): Nilability = + ## unify two states + if l == r: + l + else: + MaybeNil + +template add(l: Nilability, r: Nilability): Nilability = + if l == r: # Safe Safe -> Safe etc + l + elif l == Parent: # Parent Safe -> Safe etc + r + elif r == Parent: # Safe Parent -> Safe etc + l + elif l == Unreachable or r == Unreachable: # Safe Unreachable -> Unreachable etc + Unreachable + elif l == MaybeNil: # Safe MaybeNil -> Safe etc + r + elif r == MaybeNil: # MaybeNil Nil -> Nil etc + l + else: # Safe Nil -> Unreachable etc + Unreachable + +proc findCommonParent(l: NilMap, r: NilMap): NilMap = + result = l.parent + while not result.isNil: + var rparent = r.parent + while not rparent.isNil: + if result == rparent: + return result + rparent = rparent.parent + result = result.parent + +proc union(ctx: NilCheckerContext, l: NilMap, r: NilMap): NilMap = + ## unify two maps from different branches + ## combine their locals + ## what if they are from different parts of the same tree + ## e.g. + ## a -> b -> c + ## -> b1 + ## common then? + ## + if l.isNil: + return r + elif r.isNil: + return l + + let common = findCommonParent(l, r) + result = newNilMap(common, ctx.expressions.len.int) + + for index, value in l: + let h = history(r, index) + let info = if h.len > 0: h[^1].info else: TLineInfo(line: 0) # assert h.len > 0 + # echo "history", name, value, r[name], h[^1].info.line + result.store(ctx, index, union(value, r[index]), TAssign, info) + +proc add(ctx: NilCheckerContext, l: NilMap, r: NilMap): NilMap = + #echo "add " + #echo namedMapDebugInfo(ctx, l) + #echo " : " + #echo namedMapDebugInfo(ctx, r) + if l.isNil: + return r + elif r.isNil: + return l + + let common = findCommonParent(l, r) + result = newNilMap(common, ctx.expressions.len.int) + + for index, value in l: + let h = history(r, index) + let info = if h.len > 0: h[^1].info else: TLineInfo(line: 0) + # TODO: refactor and also think: is TAssign a good one + result.store(ctx, index, add(value, r[index]), TAssign, info) + + #echo "result" + #echo namedMapDebugInfo(ctx, result) + #echo "" + #echo "" + + +proc checkAsgn(target: PNode, assigned: PNode; ctx, map): Check = + ## check assignment + ## update map based on `assigned` + if assigned.kind != nkEmpty: + result = check(assigned, ctx, map) + else: + result = Check(nilability: typeNilability(target.typ), map: map) + + # we need to visit and check those, but we don't use the result for now + # is it possible to somehow have another event happen here? + discard check(target, ctx, map) + + if result.map.isNil: + result.map = map + if target.kind in {nkSym, nkDotExpr} or isConstBracket(target): + let t = ctx.index(target) + move(ctx, map, target, assigned) + case assigned.kind: + of nkNilLit: + result.map.store(ctx, t, Nil, TAssign, target.info, target) + else: + result.map.store(ctx, t, result.nilability, TAssign, target.info, target) + moveOutDependants(ctx, map, target) + storeDependants(ctx, map, target, MaybeNil) + if assigned.kind in {nkObjConstr, nkTupleConstr}: + for (element, value) in result.elements: + var elementNode = nkDotExpr.newTree(nkHiddenDeref.newTree(target), element) + if symbol(elementNode) in ctx.symbolIndices: + var elementIndex = ctx.index(elementNode) + result.map.store(ctx, elementIndex, value, TAssign, target.info, elementNode) + + +proc checkReturn(n, ctx, map): Check = + ## check return + # return n same as result = n; return ? + result = check(n[0], ctx, map) + result.map.store(ctx, resultExprIndex, result.nilability, TAssign, n.info) + + +proc checkIf(n, ctx, map): Check = + ## check branches based on condition + result = default(Check) + var mapIf: NilMap = map + + # first visit the condition + + # the structure is not If(Elif(Elif, Else), Else) + # it is + # If(Elif, Elif, Else) + + var mapCondition = checkCondition(n.sons[0].sons[0], ctx, mapIf, false, true) + + # the state of the conditions: negating conditions before the current one + var layerHistory = newNilMap(mapIf) + # the state after branch effects + var afterLayer: NilMap = nil + # the result nilability for expressions + var nilability = Safe + + for branch in n.sons: + var branchConditionLayer = newNilMap(layerHistory) + var branchLayer: NilMap + var code: PNode + if branch.kind in {nkIfStmt, nkElifBranch}: + var mapCondition = checkCondition(branch[0], ctx, branchConditionLayer, false, true) + let reverseMapCondition = reverseDirect(mapCondition) + layerHistory = ctx.add(layerHistory, reverseMapCondition) + branchLayer = mapCondition + code = branch[1] + else: + branchLayer = layerHistory + code = branch + + let branchCheck = checkBranch(code, ctx, branchLayer) + # handles nil afterLayer -> returns branchCheck.map + afterLayer = ctx.union(afterLayer, branchCheck.map) + nilability = if n.kind == nkIfStmt: Safe else: union(nilability, branchCheck.nilability) + if n.sons.len > 1: + result.map = afterLayer + result.nilability = nilability + else: + if not hasUnstructuredControlFlowJump(n[0][1]): + # here it matters what happend inside, because + # we might continue in the parent branch after entering this one + # either we enter the branch, so we get mapIf and effect of branch -> afterLayer + # or we dont , so we get mapIf and (not condition) effect -> layerHistory + result.map = ctx.union(layerHistory, afterLayer) + result.nilability = Safe # no expr? + else: + # similar to else: because otherwise we are jumping out of + # the branch, so no union with the mapIf (we dont continue if the condition was true) + # here it also doesn't matter for the parent branch what happened in the branch, e.g. assigning to nil + # as if we continue there, we haven't entered the branch probably + # so we don't do an union with afterLayer + # layerHistory has the effect of mapIf and (not condition) + result.map = layerHistory + result.nilability = Safe + +proc checkFor(n, ctx, map): Check = + ## check for loops + ## try to repeat the unification of the code twice + ## to detect what can change after a several iterations + ## approach based on discussions with Zahary/Araq + ## similar approach used for other loops + var m = map.copyMap() + var map0 = map.copyMap() + #echo namedMapDebugInfo(ctx, map) + m = check(n.sons[2], ctx, map).map.copyMap() + if n[0].kind == nkSym: + m.store(ctx, ctx.index(n[0]), typeNilability(n[0].typ), TAssign, n[0].info) + # echo namedMapDebugInfo(ctx, map) + var check2 = check(n.sons[2], ctx, m) + var map2 = check2.map + + result = Check(map: ctx.union(map0, m)) + result.map = ctx.union(result.map, map2) + result.nilability = Safe + +# check: +# while code: +# code2 + +# if code: +# code2 +# if code: +# code2 + +# if code: +# code2 + +# check(code), check(code2 in code's map) + +proc checkWhile(n, ctx, map): Check = + ## check while loops + ## try to repeat the unification of the code twice + var m = checkCondition(n[0], ctx, map, false, false) + var map0 = map.copyMap() + m = check(n.sons[1], ctx, m).map + var map1 = m.copyMap() + var check2 = check(n.sons[1], ctx, m) + var map2 = check2.map + + result = Check(map: ctx.union(map0, map1)) + result.map = ctx.union(result.map, map2) + result.nilability = Safe + +proc checkInfix(n, ctx, map): Check = + ## check infix operators in condition + ## a and b : map is based on a; next b + ## a or b : map is an union of a and b's + ## a == b : use checkCondition + ## else: no change, just check args + result = default(Check) + if n[0].kind == nkSym: + var mapL: NilMap = nil + var mapR: NilMap = nil + if n[0].sym.magic notin {mAnd, mEqRef}: + mapL = checkCondition(n[1], ctx, map, false, false) + mapR = checkCondition(n[2], ctx, map, false, false) + case n[0].sym.magic: + of mOr: + result.map = ctx.union(mapL, mapR) + of mAnd: + result.map = checkCondition(n[1], ctx, map, false, false) + result.map = checkCondition(n[2], ctx, result.map, false, false) + of mEqRef: + if n[2].kind == nkIntLit: + if $n[2] == "true": + result.map = checkCondition(n[1], ctx, map, false, false) + elif $n[2] == "false": + result.map = checkCondition(n[1], ctx, map, true, false) + elif n[1].kind == nkIntLit: + if $n[1] == "true": + result.map = checkCondition(n[2], ctx, map, false, false) + elif $n[1] == "false": + result.map = checkCondition(n[2], ctx, map, true, false) + + if result.map.isNil: + result.map = map + else: + result.map = map + else: + result.map = map + result.nilability = Safe + +proc checkIsNil(n, ctx, map; isElse: bool = false): Check = + ## check isNil calls + ## update the map depending on if it is not isNil or isNil + result = Check(map: newNilMap(map)) + let value = n[1] + result.map.store(ctx, ctx.index(n[1]), if not isElse: Nil else: Safe, TArg, n.info, n) + +proc infix(ctx: NilCheckerContext, l: PNode, r: PNode, magic: TMagic): PNode = + var name = case magic: + of mEqRef: "==" + of mAnd: "and" + of mOr: "or" + else: "" + + var cache = newIdentCache() + var op = newSym(skVar, cache.getIdent(name), ctx.idgen, nil, r.info) + + op.magic = magic + result = nkInfix.newTree( + newSymNode(op, r.info), + l, + r) + result.typ = newType(tyBool, ctx.idgen, nil) + +proc prefixNot(ctx: NilCheckerContext, node: PNode): PNode = + var cache = newIdentCache() + var op = newSym(skVar, cache.getIdent("not"), ctx.idgen, nil, node.info) + + op.magic = mNot + result = nkPrefix.newTree( + newSymNode(op, node.info), + node) + result.typ = newType(tyBool, ctx.idgen, nil) + +proc infixEq(ctx: NilCheckerContext, l: PNode, r: PNode): PNode = + infix(ctx, l, r, mEqRef) + +proc infixOr(ctx: NilCheckerContext, l: PNode, r: PNode): PNode = + infix(ctx, l, r, mOr) + +proc checkCase(n, ctx, map): Check = + # case a: + # of b: c + # of b2: c2 + # is like + # if a == b: + # c + # elif a == b2: + # c2 + # also a == true is a , a == false is not a + let base = n[0] + result = Check(map: map.copyMap()) + result.nilability = Safe + var a: PNode = nil + for child in n: + case child.kind: + of nkOfBranch: + if child.len < 2: + # echo "case with of with < 2 ", n + continue # TODO why does this happen + let branchBase = child[0] # TODO a, b or a, b..c etc + let code = child[^1] + let test = infixEq(ctx, base, branchBase) + if a.isNil: + a = test + else: + a = infixOr(ctx, a, test) + let conditionMap = checkCondition(test, ctx, map.copyMap(), false, false) + let newCheck = checkBranch(code, ctx, conditionMap) + result.map = ctx.union(result.map, newCheck.map) + result.nilability = union(result.nilability, newCheck.nilability) + of nkElifBranch: + discard "TODO: maybe adapt to be similar to checkIf" + of nkElse: + let mapElse = checkCondition(prefixNot(ctx, a), ctx, map.copyMap(), false, false) + let newCheck = checkBranch(child[0], ctx, mapElse) + result.map = ctx.union(result.map, newCheck.map) + result.nilability = union(result.nilability, newCheck.nilability) + else: + discard + +# notes +# try: +# a +# b +# except: +# c +# finally: +# d +# +# if a doesnt raise, this is not an exit point: +# so find what raises and update the map with that +# (a, b); c; d +# if nothing raises, except shouldn't happen +# .. might be a false positive tho, if canRaise is not conservative? +# so don't visit it +# +# nested nodes can raise as well: I hope nim returns canRaise for +# their parents +# +# a lot of stuff can raise +proc checkTry(n, ctx, map): Check = + var newMap = map.copyMap() + var currentMap = map + # we don't analyze except if nothing canRaise in try + var canRaise = false + var hasFinally = false + # var tryNodes: seq[PNode] + # if n[0].kind == nkStmtList: + # tryNodes = toSeq(n[0]) + # else: + # tryNodes = @[n[0]] + # for i, child in tryNodes: + # let (childNilability, childMap) = check(child, conf, currentMap) + # echo childMap + # currentMap = childMap + # # TODO what about nested + # if child.canRaise: + # newMap = union(newMap, childMap) + # canRaise = true + # else: + # newMap = childMap + let tryCheck = check(n[0], ctx, currentMap) + newMap = ctx.union(currentMap, tryCheck.map) + canRaise = n[0].canRaise + + var afterTryMap = newMap + for a, branch in n: + if a > 0: + case branch.kind: + of nkFinally: + newMap = ctx.union(afterTryMap, newMap) + let childCheck = check(branch[0], ctx, newMap) + newMap = ctx.union(newMap, childCheck.map) + hasFinally = true + of nkExceptBranch: + if canRaise: + let childCheck = check(branch[^1], ctx, newMap) + newMap = ctx.union(newMap, childCheck.map) + else: + discard + if not hasFinally: + # we might have not hit the except branches + newMap = ctx.union(afterTryMap, newMap) + result = Check(nilability: Safe, map: newMap) + +proc hasUnstructuredControlFlowJump(n: PNode): bool = + ## if the node contains a direct stop + ## as a continue/break/raise/return: then it means + ## we should reverse some of the map in the code after the condition + ## similar to else + # echo "n ", n, " ", n.kind + case n.kind: + of nkStmtList: + for child in n: + if hasUnstructuredControlFlowJump(child): + return true + of nkReturnStmt, nkBreakStmt, nkContinueStmt, nkRaiseStmt: + return true + of nkIfStmt, nkIfExpr, nkElifExpr, nkElse: + return false + else: + discard + return false + +proc reverse(value: Nilability): Nilability = + case value: + of Nil: Safe + of MaybeNil: MaybeNil + of Safe: Nil + of Parent: Parent + of Unreachable: Unreachable + +proc reverse(kind: TransitionKind): TransitionKind = + case kind: + of TNil: TSafe + of TSafe: TNil + of TPotentialAlias: TPotentialAlias + else: + kind + # raise newException(ValueError, "expected TNil or TSafe") + +proc reverseDirect(map: NilMap): NilMap = + # we create a new layer + # reverse the values only in this layer: + # because conditions should've stored their changes there + # b: Safe (not b.isNil) + # b: Parent Parent + # b: Nil (b.isNil) + + # layer block + # [ Parent ] [ Parent ] + # if -> if state + # layer -> reverse + # older older0 new + # older new + # [ b Nil ] [ Parent ] + # elif + # [ b Nil, c Nil] [ Parent ] + # + + # if b.isNil: + # # [ b Safe] + # c = A() # Safe + # elif not b.isNil: + # # [ b Safe ] + [b Nil] MaybeNil Unreachable + # # Unreachable defer can't deref b, it is unreachable + # discard + # else: + # b + + +# if + + + + # if: we just pass the map with a new layer for its block + # elif: we just pass the original map but with a new layer is the reverse of the previous popped layer (?) + # elif: + # else: we just pass the original map but with a new layer which is initialized as the reverse of the + # top layer of else + # else: + # + # [ b MaybeNil ] [b Parent] [b Parent] [b Safe] [b Nil] [] + # Safe + # c == 1 + # b Parent + # c == 2 + # b Parent + # not b.isNil + # b Safe + # c == 3 + # b Nil + # (else) + # b Nil + + result = map.copyMap() + for index, value in result.expressions: + result.expressions[index] = reverse(value) + if result.history[index].len > 0: + result.history[index][^1].kind = reverse(result.history[index][^1].kind) + result.history[index][^1].nilability = result.expressions[index] + +proc checkCondition(n, ctx, map; reverse: bool, base: bool): NilMap = + ## check conditions : used for if, some infix operators + ## isNil(a) + ## it returns a new map: you need to reverse all the direct elements for else + + # echo "condition ", n, " ", n.kind + if n.kind == nkCall: + result = newNilMap(map) + for element in n: + if element.kind == nkHiddenDeref and n[0].kind == nkSym and n[0].sym.magic == mIsNil: + result = check(element[0], ctx, result).map + else: + result = check(element, ctx, result).map + + if n[0].kind == nkSym and n[0].sym.magic == mIsNil: + # isNil(arg) + var arg = n[1] + while arg.kind == nkHiddenDeref: + arg = arg[0] + if arg.kind in {nkSym, nkDotExpr} or isConstBracket(arg): + let a = ctx.index(arg) + result.store(ctx, a, if not reverse: Nil else: Safe, if not reverse: TNil else: TSafe, n.info, arg) + else: + discard + else: + discard + elif n.kind == nkPrefix and n[0].kind == nkSym and n[0].sym.magic == mNot: + result = checkCondition(n[1], ctx, map, not reverse, false) + elif n.kind == nkInfix: + result = newNilMap(map) + result = checkInfix(n, ctx, result).map + else: + result = check(n, ctx, map).map + result = newNilMap(map) + assert not result.isNil + assert not result.parent.isNil + +proc checkResult(n, ctx, map) = + let resultNilability = map[resultExprIndex] + case resultNilability: + of Nil: + message(ctx.config, n.info, warnStrictNotNil, "return value is nil") + of MaybeNil: + message(ctx.config, n.info, warnStrictNotNil, "return value might be nil") + of Unreachable: + message(ctx.config, n.info, warnStrictNotNil, "return value is unreachable") + of Safe, Parent: + discard + +proc checkBranch(n: PNode, ctx: NilCheckerContext, map: NilMap): Check = + result = check(n, ctx, map) + + +# Faith! + +proc check(n: PNode, ctx: NilCheckerContext, map: NilMap): Check = + assert not map.isNil + + # echo "check n ", n, " ", n.kind + # echo "map ", namedMapDebugInfo(ctx, map) + case n.kind: + of nkSym: + result = Check(nilability: map[ctx.index(n)], map: map) + of nkCallKinds: + if n.sons[0].kind == nkSym: + let callSym = n.sons[0].sym + case callSym.magic: + of mAnd, mOr: + result = checkInfix(n, ctx, map) + of mIsNil: + result = checkIsNil(n, ctx, map) + else: + result = checkCall(n, ctx, map) + else: + result = checkCall(n, ctx, map) + of nkHiddenStdConv, nkHiddenSubConv, nkConv, nkExprColonExpr, nkExprEqExpr, + nkCast: + result = check(n.sons[1], ctx, map) + of nkStmtList, nkStmtListExpr, nkChckRangeF, nkChckRange64, nkChckRange, + nkBracket, nkCurly, nkPar, nkTupleConstr, nkClosure, nkObjConstr, nkElse: + result = Check(map: map) + if n.kind in {nkObjConstr, nkTupleConstr}: + # TODO deeper nested elements? + # A(field: B()) # + # field: Safe -> + var elements: seq[(PNode, Nilability)] = @[] + for i, child in n: + result = check(child, ctx, result.map) + if i > 0: + if child.kind == nkExprColonExpr: + elements.add((child[0], result.nilability)) + result.elements = elements + result.nilability = Safe + else: + for child in n: + result = check(child, ctx, result.map) + + of nkDotExpr: + result = checkDotExpr(n, ctx, map) + of nkDerefExpr, nkHiddenDeref: + result = checkDeref(n, ctx, map) + of nkAddr, nkHiddenAddr: + result = check(n.sons[0], ctx, map) + of nkIfStmt, nkIfExpr: + result = checkIf(n, ctx, map) + of nkAsgn, nkFastAsgn, nkSinkAsgn: + result = checkAsgn(n[0], n[1], ctx, map) + of nkVarSection, nkLetSection: + result = Check(map: map) + for child in n: + result = checkAsgn(child[0].skipPragmaExpr, child[2], ctx, result.map) + of nkForStmt: + result = checkFor(n, ctx, map) + of nkCaseStmt: + result = checkCase(n, ctx, map) + of nkReturnStmt: + result = checkReturn(n, ctx, map) + of nkBracketExpr: + result = checkBracketExpr(n, ctx, map) + of nkTryStmt: + result = checkTry(n, ctx, map) + of nkWhileStmt: + result = checkWhile(n, ctx, map) + of nkNone..pred(nkSym), succ(nkSym)..nkNilLit, nkTypeSection, nkProcDef, nkConverterDef, + nkMethodDef, nkIteratorDef, nkMacroDef, nkTemplateDef, nkLambda, nkDo, + nkFuncDef, nkConstSection, nkConstDef, nkIncludeStmt, nkImportStmt, + nkExportStmt, nkPragma, nkCommentStmt, nkBreakState, + nkTypeOfExpr, nkMixinStmt, nkBindStmt: + + discard "don't follow this : same as varpartitions" + result = Check(nilability: Nil, map: map) + else: + + var elementMap = map.copyMap() + var elementCheck = Check(map: elementMap) + for element in n: + elementCheck = check(element, ctx, elementCheck.map) + + result = Check(nilability: Nil, map: elementCheck.map) + + + + +proc typeNilability(typ: PType): Nilability = + assert not typ.isNil + # echo "typeNilability ", $typ.flags, " ", $typ.kind + result = if tfNotNil in typ.flags: + Safe + elif typ.kind in {tyRef, tyCstring, tyPtr, tyPointer}: + # + # tyVar ? tyVarargs ? tySink ? tyLent ? + # TODO spec? tests? + MaybeNil + else: + Safe + # echo " result ", result + +proc preVisitNode(ctx: NilCheckerContext, node: PNode, conf: ConfigRef) = + # echo "visit node ", node + if node.kind in {nkSym, nkDotExpr} or isConstBracket(node): + let nodeSymbol = symbol(node) + if not ctx.symbolIndices.hasKey(nodeSymbol): + ctx.symbolIndices[nodeSymbol] = ctx.expressions.len + ctx.expressions.add(node) + if node.kind in {nkDotExpr, nkBracketExpr}: + if node.kind == nkDotExpr and (not node.typ.isNil and node.typ.kind == tyRef and tfNotNil notin node.typ.flags) or + node.kind == nkBracketExpr: + let index = ctx.symbolIndices[nodeSymbol] + var baseIndex = noExprIndex + # deref usually? + # ok, we hit another case + var base = if node[0].kind notin {nkSym, nkIdent}: node[0][0] else: node[0] + if base.kind != nkIdent: + let baseSymbol = symbol(base) + if not ctx.symbolIndices.hasKey(baseSymbol): + baseIndex = ctx.expressions.len # next visit should add it + else: + baseIndex = ctx.symbolIndices[baseSymbol] + if ctx.dependants.len <= baseIndex: + ctx.dependants.setLen(baseIndex + 1.ExprIndex) + ctx.dependants[baseIndex].incl(index.int) + case node.kind: + of nkSym, nkEmpty, nkNilLit, nkType, nkIdent, nkCharLit .. nkUInt64Lit, nkFloatLit .. nkFloat64Lit, nkStrLit .. nkTripleStrLit: + discard + of nkDotExpr: + # visit only the base + ctx.preVisitNode(node[0], conf) + else: + for element in node: + ctx.preVisitNode(element, conf) + +proc preVisit(ctx: NilCheckerContext, s: PSym, body: PNode, conf: ConfigRef) = + ctx.symbolIndices = {resultId: resultExprIndex}.toTable() + var cache = newIdentCache() + ctx.expressions = SeqOfDistinct[ExprIndex, PNode](@[newIdentNode(cache.getIdent("result"), s.ast.info)]) + var emptySet: IntSet = initIntSet() # set[ExprIndex] + ctx.dependants = SeqOfDistinct[ExprIndex, IntSet](@[emptySet]) + for i, arg in s.typ.n.sons: + if i > 0: + if arg.kind != nkSym: + continue + let argSymbol = symbol(arg) + if not ctx.symbolIndices.hasKey(argSymbol): + ctx.symbolIndices[argSymbol] = ctx.expressions.len + ctx.expressions.add(arg) + ctx.preVisitNode(body, conf) + if ctx.dependants.len < ctx.expressions.len: + ctx.dependants.setLen(ctx.expressions.len) + # echo ctx.symbolIndices + # echo ctx.expressions + # echo ctx.dependants + +proc checkNil*(s: PSym; body: PNode; conf: ConfigRef, idgen: IdGenerator) = + let line = s.ast.info.line + let fileIndex = s.ast.info.fileIndex.int + var filename = conf.m.fileInfos[fileIndex].fullPath.string + + var context = NilCheckerContext(config: conf, idgen: idgen) + context.preVisit(s, body, conf) + var map = newNilMap(nil, context.symbolIndices.len) + + for i, child in s.typ.n.sons: + if i > 0: + if child.kind != nkSym: + continue + map.store(context, context.index(child), typeNilability(child.typ), TArg, child.info, child) + + map.store(context, resultExprIndex, if not s.typ.returnType.isNil and s.typ.returnType.kind == tyRef: Nil else: Safe, TResult, s.ast.info) + + # echo "checking ", s.name.s, " ", filename + + let res = check(body, context, map) + var canCheck = resultExprIndex in res.map.history.low .. res.map.history.high + if res.nilability == Safe and canCheck and res.map.history[resultExprIndex].len <= 1: + res.map.store(context, resultExprIndex, Safe, TAssign, s.ast.info) + else: + if res.nilability == Safe: + res.map.store(context, resultExprIndex, Safe, TAssign, s.ast.info) + + # TODO check for nilability result + # (ANotNil, BNotNil) : + # do we check on asgn nilability at all? + + if not s.typ.returnType.isNil and s.typ.returnType.kind == tyRef and tfNotNil in s.typ.returnType.flags: + checkResult(s.ast, context, res.map) |