writing to a location counts as "side effect"; implements https://github.com/nim-lang/RFCs/issues/234 (#15030)

5 files changed, 283 insertions, 5 deletions

diff --git a/compiler/isolation_check.nim b/compiler/isolation_check.nim
index a77e8c97a..2b53bce92 100644
--- a/compiler/isolation_check.nim
+++ b/compiler/isolation_check.nim
@@ -64,7 +64,7 @@ proc canAlias(arg, ret: PType; marker: var IntSet): bool =
   else:
     result = false
 
-proc canAlias(arg, ret: PType): bool =
+proc canAlias*(arg, ret: PType): bool =
   var marker = initIntSet()
   result = canAlias(arg, ret, marker)
 
diff --git a/compiler/options.nim b/compiler/options.nim
index 8b73c07fc..5d9bc245b 100644
--- a/compiler/options.nim
+++ b/compiler/options.nim
@@ -163,6 +163,7 @@ type
       ## which itself requires `nimble install libffi`, see #10150
       ## Note: this feature can't be localized with {.push.}
     vmopsDanger,
+    strictFuncs
 
   LegacyFeature* = enum
     allowSemcheckedAstModification,
diff --git a/compiler/sempass2.nim b/compiler/sempass2.nim
index 49fa44ca2..c6d6d9241 100644
--- a/compiler/sempass2.nim
+++ b/compiler/sempass2.nim
@@ -10,7 +10,7 @@
 import
   intsets, ast, astalgo, msgs, renderer, magicsys, types, idents, trees,
   wordrecg, strutils, options, guards, lineinfos, semfold, semdata,
-  modulegraphs
+  modulegraphs, varpartitions
 
 when defined(useDfa):
   import dfa
@@ -36,9 +36,6 @@ For every sink parameter of type T T is marked.
 
 For every call f() the return type of f() is marked.
 
-
-
-
 ]#
 
 # ------------------------ exception and tag tracking -------------------------
@@ -73,6 +70,7 @@ type
     guards: TModel # nested guards
     locked: seq[PNode] # locked locations
     gcUnsafe, isRecursive, isTopLevel, hasSideEffect, inEnforcedGcSafe: bool
+    hasDangerousAssign: bool
     inEnforcedNoSideEffects: bool
     maxLockLevel, currLockLevel: TLockLevel
     currOptions: TOptions
@@ -885,6 +883,8 @@ proc track(tracked: PEffects, n: PNode) =
       createTypeBoundOps(tracked, n[0].typ, n.info)
     if n[0].kind != nkSym or not isLocalVar(tracked, n[0].sym):
       checkForSink(tracked.config, tracked.owner, n[1])
+      if not tracked.hasDangerousAssign and n[0].kind != nkSym:
+        tracked.hasDangerousAssign = true
   of nkVarSection, nkLetSection:
     for child in n:
       let last = lastSon(child)
@@ -1237,6 +1237,9 @@ proc trackProc*(c: PContext; s: PSym, body: PNode) =
     patchResult(t, ensuresSpec)
     effects[ensuresEffects] = ensuresSpec
 
+  if strictFuncs in c.features and not t.hasSideEffect and t.hasDangerousAssign:
+    t.hasSideEffect = mutatesNonVarParameters(s, body)
+
   if sfThread in s.flags and t.gcUnsafe:
     if optThreads in g.config.globalOptions and optThreadAnalysis in g.config.globalOptions:
       #localError(s.info, "'$1' is not GC-safe" % s.name.s)
diff --git a/compiler/varpartitions.nim b/compiler/varpartitions.nim
new file mode 100644
index 000000000..b89b7d1da
--- /dev/null
+++ b/compiler/varpartitions.nim
@@ -0,0 +1,243 @@
+#
+#
+#           The Nim Compiler
+#        (c) Copyright 2020 Andreas Rumpf
+#
+#    See the file "copying.txt", included in this
+#    distribution, for details about the copyright.
+#
+
+## Partition variables into different graphs. Used for
+## Nim's write tracking. The used algorithm is "union find"
+## with path compression.
+
+import ast, types
+from trees import getMagic
+from isolation_check import canAlias
+
+type
+  SubgraphFlag = enum
+    isMutated, # graph might be mutated
+    connectsConstParam, # graph is connected to a non-var parameter.
+
+  VarIndexKind = enum
+    isEmptyRoot,
+    dependsOn,
+    isRootOf
+
+  VarIndex = object
+    case kind: VarIndexKind
+    of isEmptyRoot: discard
+    of dependsOn: parent: int
+    of isRootOf: graphIndex: int
+
+  Partitions = object
+    symToId: seq[PSym]
+    s: seq[VarIndex]
+    graphs: seq[set[SubgraphFlag]]
+
+proc hasSideEffect(p: Partitions): bool =
+  for g in p.graphs:
+    if g == {isMutated, connectsConstParam}: return true
+  return false
+
+template isConstParam(a): bool = a.kind == skParam and a.typ.kind != tyVar
+
+proc registerVariable(p: var Partitions; n: PNode) =
+  if n.kind == nkSym:
+    p.symToId.add n.sym
+    if isConstParam(n.sym):
+      p.s.add VarIndex(kind: isRootOf, graphIndex: p.graphs.len)
+      p.graphs.add({connectsConstParam})
+    else:
+      p.s.add VarIndex(kind: isEmptyRoot)
+
+proc variableId(p: Partitions; x: PSym): int {.inline.} = system.find(p.symToId, x)
+
+proc root(v: var Partitions; start: int): int =
+  result = start
+  while v.s[result].kind == dependsOn:
+    result = v.s[result].parent
+  # path compression:
+  var it = start
+  while v.s[it].kind == dependsOn:
+    let next = v.s[it].parent
+    v.s[it] = VarIndex(kind: dependsOn, parent: result)
+    it = next
+
+proc potentialMutation(v: var Partitions; s: PSym) =
+  let id = variableId(v, s)
+  if id >= 0:
+    let r = root(v, id)
+    case v.s[r].kind
+    of isEmptyRoot:
+      v.s[r] = VarIndex(kind: isRootOf, graphIndex: v.graphs.len)
+      v.graphs.add({isMutated})
+    of isRootOf:
+      v.graphs[v.s[r].graphIndex].incl isMutated
+    else:
+      assert false, "cannot happen"
+  else:
+    discard "we are not interested in the mutation"
+
+proc connect(v: var Partitions; a, b: PSym) =
+  let aid = variableId(v, a)
+  if aid < 0:
+    return
+  let bid = variableId(v, b)
+  if bid < 0:
+    return
+
+  let ra = root(v, aid)
+  let rb = root(v, bid)
+  if ra != rb:
+    let paramFlags =
+      if isConstParam(a) or isConstParam(b):
+        {connectsConstParam}
+      else:
+        {}
+
+    # for now we always make 'rb' the slave and 'ra' the master:
+    let rbFlags =
+      if v.s[rb].kind == isRootOf:
+        v.graphs[v.s[rb].graphIndex]
+      else:
+        {}
+
+    v.s[rb] = VarIndex(kind: dependsOn, parent: ra)
+    case v.s[ra].kind
+    of isEmptyRoot:
+      v.s[ra] = VarIndex(kind: isRootOf, graphIndex: v.graphs.len)
+      v.graphs.add(paramFlags + rbFlags)
+    of isRootOf:
+      v.graphs[v.s[ra].graphIndex].incl paramFlags + rbFlags
+    else:
+      assert false, "cannot happen"
+
+proc allRoots(n: PNode; result: var seq[PSym]) =
+  case n.kind
+  of nkSym:
+    if n.sym.kind in {skParam, skVar, skTemp, skLet, skResult, skForVar}:
+      result.add(n.sym)
+  of nkHiddenDeref, nkDerefExpr, nkAddr, nkDotExpr, nkBracketExpr,
+      nkCheckedFieldExpr, nkHiddenAddr, nkObjUpConv, nkObjDownConv:
+    allRoots(n[0], result)
+  of nkExprEqExpr, nkExprColonExpr, nkHiddenStdConv, nkHiddenSubConv, nkConv,
+      nkStmtList, nkStmtListExpr, nkBlockStmt, nkBlockExpr, nkCast:
+    if n.len > 0:
+      allRoots(n.lastSon, result)
+  of nkCaseStmt, nkObjConstr:
+    for i in 1..<n.len:
+      allRoots(n[i].lastSon, result)
+  of nkIfStmt, nkIfExpr:
+    for i in 0..<n.len:
+      allRoots(n[i].lastSon, result)
+  of nkBracket, nkTupleConstr, nkPar:
+    for i in 0..<n.len:
+      allRoots(n[i], result)
+
+  of nkCallKinds:
+    if n.typ != nil and n.typ.kind in {tyVar, tyLent}:
+      if n.len > 1:
+        allRoots(n[1], result)
+    else:
+      let m = getMagic(n)
+      case m
+      of mNone:
+        # we do significantly better here by using the available escape
+        # information:
+        if n[0].typ.isNil: return
+        var typ = n[0].typ
+        if typ != nil:
+          typ = skipTypes(typ, abstractInst)
+          if typ.kind != tyProc: typ = nil
+          else: assert(typ.len == typ.n.len)
+
+        for i in 1 ..< n.len:
+          let it = n[i]
+          if typ != nil and i < typ.len:
+            assert(typ.n[i].kind == nkSym)
+            let paramType = typ.n[i].typ
+            if not paramType.isCompileTimeOnly and not typ.sons[0].isEmptyType and
+                canAlias(paramType, typ.sons[0]):
+              allRoots(it, result)
+          else:
+            allRoots(it, result)
+
+      of mSlice:
+        allRoots(n[1], result)
+      else:
+        discard "harmless operation"
+  else:
+    discard "nothing to do"
+
+proc deps(p: var Partitions; dest, src: PNode) =
+  var targets, sources: seq[PSym]
+  allRoots(dest, targets)
+  allRoots(src, sources)
+  for t in targets:
+    if dest.kind != nkSym:
+      potentialMutation(p, t)
+
+    proc wrap(t: PType): bool {.nimcall.} = t.kind in {tyRef, tyPtr}
+    if types.searchTypeFor(t.typ, wrap):
+      for s in sources:
+        connect(p, t, s)
+
+proc traverse(p: var Partitions; n: PNode) =
+  case n.kind
+  of nkLetSection, nkVarSection:
+    for child in n:
+      let last = lastSon(child)
+      traverse(p, last)
+      if child.kind == nkVarTuple and last.kind in {nkPar, nkTupleConstr}:
+        if child.len-2 != last.len: return
+        for i in 0..<child.len-2:
+          registerVariable(p, child[i])
+          deps(p, child[i], last[i])
+      else:
+        for i in 0..<child.len-2:
+          registerVariable(p, child[i])
+          deps(p, child[i], last)
+  of nkAsgn, nkFastAsgn:
+    traverse(p, n[0])
+    traverse(p, n[1])
+    deps(p, n[0], n[1])
+  of nkNone..nkNilLit, nkTypeSection, nkProcDef, nkConverterDef,
+      nkMethodDef, nkIteratorDef, nkMacroDef, nkTemplateDef, nkLambda, nkDo,
+      nkFuncDef, nkConstSection, nkConstDef, nkIncludeStmt, nkImportStmt,
+      nkExportStmt, nkPragma, nkCommentStmt, nkBreakState, nkTypeOfExpr:
+    discard "do not follow the construct"
+  of nkCallKinds:
+    for child in n: traverse(p, child)
+
+    if n[0].typ.isNil: return
+    var typ = skipTypes(n[0].typ, abstractInst)
+    if typ.kind != tyProc: return
+    assert(typ.len == typ.n.len)
+    for i in 1..<n.len:
+      let it = n[i]
+      if i < typ.len:
+        assert(typ.n[i].kind == nkSym)
+        let paramType = typ.n[i]
+        if paramType.typ.isCompileTimeOnly: continue
+        if paramType.typ.kind == tyVar:
+          var roots: seq[PSym]
+          allRoots(n, roots)
+          for r in roots: potentialMutation(p, r)
+
+  else:
+    for child in n: traverse(p, child)
+
+
+proc mutatesNonVarParameters*(s: PSym; n: PNode): bool =
+  var par = Partitions()
+  if s.kind != skMacro:
+    let params = s.typ.n
+    for i in 1..<params.len:
+      registerVariable(par, params[i])
+    if resultPos < s.ast.safeLen:
+      registerVariable(par, s.ast[resultPos])
+
+  traverse(par, n)
+  result = hasSideEffect(par)
diff --git a/tests/effects/tfuncs_cannot_mutate.nim b/tests/effects/tfuncs_cannot_mutate.nim
new file mode 100644
index 000000000..ec3ad43f7
--- /dev/null
+++ b/tests/effects/tfuncs_cannot_mutate.nim
@@ -0,0 +1,31 @@
+discard """
+  errormsg: "'mutate' can have side effects"
+  line: 25
+"""
+
+{.experimental: "strictFuncs".}
+
+type
+  Node = ref object
+    le, ri: Node
+    data: string
+
+func len(n: Node): int =
+  var it = n
+  while it != nil:
+    inc result
+    it = it.ri
+
+func doNotDistract(n: Node) =
+  var m = Node()
+  m.data = "abc"
+
+func select(a, b: Node): Node = b
+
+func mutate(n: Node) =
+  var it = n
+  let x = it
+  let y = x
+  let z = y
+
+  select(x, z).data = "tricky"