Nim/compiler/nilcheck.nim

#
#
#           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

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 =
  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, nkFastAsgn, nkSinkAsgn:
    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)