# # # 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, intsets, tables, msgs, options, lineinfos, strformat, idents, treetab, hashes import sequtils, strutils, sets # 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 = 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 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.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[0].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 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 # 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.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.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 if n[0].kind == nkSym: var mapL: NilMap var mapR: NilMap 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.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), nextSymId ctx.idgen, nil, r.info) op.magic = magic result = nkInfix.newTree( newSymNode(op, r.info), l, r) result.typ = newType(tyBool, nextTypeId ctx.idgen, nil) proc prefixNot(ctx: NilCheckerContext, node: PNode): PNode = var cache = newIdentCache() var op = newSym(skVar, cache.getIdent("not"), nextSymId ctx.idgen, nil, node.info) op.magic = mNot result = nkPrefix.newTree( newSymNode(op, node.info), node) result.typ = newType(tyBool, nextTypeId 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.map = map.copyMap() result.nilability = Safe var a: PNode 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.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: result = checkAsgn(n[0], n[1], ctx, map) of nkVarSection: result.map = map for child in n: result = checkAsgn(child[0], 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 elementCheck.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 # 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[0].isNil and s.typ[0].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[0].isNil and s.typ[0].kind == tyRef and tfNotNil in s.typ[0].flags: checkResult(s.ast, context, res.map)