alternative, much simpler algorithm for strict func checking (#21066)

* alternative, much simpler algorithm for strict func checking

* forgot to git add new compiler module

* new spec is incredibly simple to describe

* fixes bigints regression

* typos

* closes #16305; closes #17387; closes #20863

14 files changed, 187 insertions, 78 deletions

diff --git a/compiler/renderer.nim b/compiler/renderer.nim
index 61bd9cf62..15b712d0d 100644
--- a/compiler/renderer.nim
+++ b/compiler/renderer.nim
@@ -1260,8 +1260,12 @@ proc gsub(g: var TSrcGen, n: PNode, c: TContext, fromStmtList = false) =
     gsub(g, n, 0)
   of nkCheckedFieldExpr, nkHiddenAddr, nkHiddenDeref, nkStringToCString, nkCStringToString:
     if renderIds in g.flags:
-      putWithSpace(g, tkAddr, $n.kind)
+      put(g, tkAddr, $n.kind)
+      put(g, tkParLe, "(")
     gsub(g, n, 0)
+    if renderIds in g.flags:
+      put(g, tkParRi, ")")
+
   of nkLambda:
     putWithSpace(g, tkProc, "proc")
     gsub(g, n, paramsPos)
diff --git a/compiler/sempass2.nim b/compiler/sempass2.nim
index 6ba89c4bb..4520609e3 100644
--- a/compiler/sempass2.nim
+++ b/compiler/sempass2.nim
@@ -10,7 +10,8 @@
 import
   intsets, ast, astalgo, msgs, renderer, magicsys, types, idents, trees,
   wordrecg, strutils, options, guards, lineinfos, semfold, semdata,
-  modulegraphs, varpartitions, typeallowed, nilcheck, errorhandling, tables
+  modulegraphs, varpartitions, typeallowed, nilcheck, errorhandling, tables,
+  semstrictfuncs
 
 when defined(nimPreviewSlimSystem):
   import std/assertions
@@ -75,7 +76,7 @@ type
     guards: TModel # nested guards
     locked: seq[PNode] # locked locations
     gcUnsafe, isRecursive, isTopLevel, hasSideEffect, inEnforcedGcSafe: bool
-    hasDangerousAssign, isInnerProc: bool
+    isInnerProc: bool
     inEnforcedNoSideEffects: bool
     currOptions: TOptions
     config: ConfigRef
@@ -817,6 +818,9 @@ proc checkForSink(tracked: PEffects; n: PNode) =
   if tracked.inIfStmt == 0 and optSinkInference in tracked.config.options:
     checkForSink(tracked.config, tracked.c.idgen, tracked.owner, n)
 
+proc strictFuncsActive(tracked: PEffects): bool {.inline.} =
+  sfNoSideEffect in tracked.owner.flags and strictFuncs in tracked.c.features and not tracked.inEnforcedNoSideEffects
+
 proc trackCall(tracked: PEffects; n: PNode) =
   template gcsafeAndSideeffectCheck() =
     if notGcSafe(op) and not importedFromC(a):
@@ -921,12 +925,15 @@ proc trackCall(tracked: PEffects; n: PNode) =
         createTypeBoundOps(tracked, paramType[0], n.info)
         checkForSink(tracked, n[i])
       of tyVar:
-        tracked.hasDangerousAssign = true
         if isOutParam(paramType):
           # consider this case: p(out x, x); we want to remark that 'x' is not
           # initialized until after the call. Since we do this after we analysed the
           # call, this is fine.
           initVar(tracked, n[i].skipAddr, false)
+        if tracked.strictFuncsActive and isDangerousLocation(n[i].skipAddr, tracked.owner):
+          localError(tracked.config, n[i].info,
+            "cannot pass $1 to `var T` parameter within a strict func" % renderTree(n[i]))
+          tracked.hasSideEffect = true
       else: discard
 
 type
@@ -1079,8 +1086,10 @@ proc track(tracked: PEffects, n: PNode) =
       createTypeBoundOps(tracked, n[0].typ, n.info)
     if n[0].kind != nkSym or not isLocalSym(tracked, n[0].sym):
       checkForSink(tracked, n[1])
-      if not tracked.hasDangerousAssign and n[0].kind != nkSym:
-        tracked.hasDangerousAssign = true
+      if tracked.strictFuncsActive and isDangerousLocation(n[0], tracked.owner):
+        tracked.hasSideEffect = true
+        localError(tracked.config, n[0].info,
+            "cannot mutate location $1 within a strict func" % renderTree(n[0]))
   of nkVarSection, nkLetSection:
     for child in n:
       let last = lastSon(child)
@@ -1513,17 +1522,9 @@ proc trackProc*(c: PContext; s: PSym, body: PNode) =
     effects[ensuresEffects] = ensuresSpec
 
   var mutationInfo = MutationInfo()
-  var hasMutationSideEffect = false
-  if {strictFuncs, views} * c.features != {}:
-    var goals: set[Goal] = {}
-    if strictFuncs in c.features: goals.incl constParameters
-    if views in c.features: goals.incl borrowChecking
-    var partitions = computeGraphPartitions(s, body, g, goals)
-    if not t.hasSideEffect and t.hasDangerousAssign:
-      t.hasSideEffect = varpartitions.hasSideEffect(partitions, mutationInfo)
-      hasMutationSideEffect = t.hasSideEffect
-    if views in c.features:
-      checkBorrowedLocations(partitions, body, g.config)
+  if views in c.features:
+    var partitions = computeGraphPartitions(s, body, g, {borrowChecking})
+    checkBorrowedLocations(partitions, body, g.config)
 
   if sfThread in s.flags and t.gcUnsafe:
     if optThreads in g.config.globalOptions and optThreadAnalysis in g.config.globalOptions:
@@ -1536,9 +1537,7 @@ proc trackProc*(c: PContext; s: PSym, body: PNode) =
     when false:
       listGcUnsafety(s, onlyWarning=false, g.config)
     else:
-      if hasMutationSideEffect:
-        localError(g.config, s.info, "'$1' can have side effects$2" % [s.name.s, g.config $ mutationInfo])
-      elif c.compilesContextId == 0: # don't render extended diagnostic messages in `system.compiles` context
+      if c.compilesContextId == 0: # don't render extended diagnostic messages in `system.compiles` context
         var msg = ""
         listSideEffects(msg, s, g.config, t.c)
         message(g.config, s.info, errGenerated, msg)
diff --git a/compiler/semstrictfuncs.nim b/compiler/semstrictfuncs.nim
new file mode 100644
index 000000000..c54196283
--- /dev/null
+++ b/compiler/semstrictfuncs.nim
@@ -0,0 +1,55 @@
+#

+#

+#           The Nim Compiler

+#        (c) Copyright 2022 Andreas Rumpf

+#

+#    See the file "copying.txt", included in this

+#    distribution, for details about the copyright.

+#

+

+## New "strict funcs" checking. Much simpler and hopefully easier to teach than

+## the old but more advanced algorithm that can/could be found in `varpartitions.nim`.

+

+import ast, typeallowed, renderer

+from aliasanalysis import PathKinds0, PathKinds1

+from trees import getMagic

+

+proc isDangerousLocation*(n: PNode; owner: PSym): bool =

+  var n = n

+  var hasDeref = false

+  while true:

+    case n.kind

+    of nkDerefExpr, nkHiddenDeref:

+      if n[0].typ.kind != tyVar:

+        hasDeref = true

+      n = n[0]

+    of PathKinds0 - {nkDerefExpr, nkHiddenDeref}:

+      n = n[0]

+    of PathKinds1:

+      n = n[1]

+    of nkCallKinds:

+      if n.len > 1:

+        if (n.typ != nil and classifyViewType(n.typ) != noView) or getMagic(n) == mSlice:

+          # borrow from first parameter:

+          n = n[1]

+        else:

+          break

+      else:

+        break

+    else:

+      break

+  if n.kind == nkSym:

+    # dangerous if contains a pointer deref or if it doesn't belong to us:

+    result = hasDeref or n.sym.owner != owner

+    when false:

+      # store to something that belongs to a `var` parameter is fine:

+      let s = n.sym

+      if s.kind == skParam:

+        # dangerous unless a `var T` parameter:

+        result = s.typ.kind != tyVar

+      else:

+        # dangerous if contains a pointer deref or if it doesn't belong to us:

+        result = hasDeref or s.owner != owner

+  else:

+    # dangerous if it contains a pointer deref

+    result = hasDeref

diff --git a/doc/manual_experimental.md b/doc/manual_experimental.md
index a40dfedce..6f5906019 100644
--- a/doc/manual_experimental.md
+++ b/doc/manual_experimental.md
@@ -519,8 +519,7 @@ Since version 1.4, a stricter definition of "side effect" is available.
 In addition to the existing rule that a side effect is calling a function
 with side effects, the following rule is also enforced:
 
-Any mutation to an object does count as a side effect if that object is reachable
-via a parameter that is not declared as a `var` parameter.
+A store to the heap via a `ref` or `ptr` indirection is not allowed.
 
 For example:
 
@@ -540,15 +539,12 @@ For example:
       it = it.ri
 
   func mut(n: Node) =
-    let m = n # is the statement that connected the mutation to the parameter
-    m.data = "yeah" # the mutation is here
-    # Error: 'mut' can have side effects
-    # an object reachable from 'n' is potentially mutated
-  ```
-
+    var it = n
+    while it != nil:
+      it.data = "yeah" # forbidden mutation
+      it = it.ri
 
-The algorithm behind this analysis is described in
-the [view types algorithm][Algorithm].
+  ```
 
 
 View types
diff --git a/lib/pure/httpcore.nim b/lib/pure/httpcore.nim
index 7e995ac46..d639bef05 100644
--- a/lib/pure/httpcore.nim
+++ b/lib/pure/httpcore.nim
@@ -132,17 +132,13 @@ func toCaseInsensitive(headers: HttpHeaders, s: string): string {.inline.} =
 func newHttpHeaders*(titleCase=false): HttpHeaders =
   ## Returns a new `HttpHeaders` object. if `titleCase` is set to true,
   ## headers are passed to the server in title case (e.g. "Content-Length")
-  new result
-  result.table = newTable[string, seq[string]]()
-  result.isTitleCase = titleCase
+  result = HttpHeaders(table: newTable[string, seq[string]](), isTitleCase: titleCase)
 
 func newHttpHeaders*(keyValuePairs:
     openArray[tuple[key: string, val: string]], titleCase=false): HttpHeaders =
   ## Returns a new `HttpHeaders` object from an array. if `titleCase` is set to true,
   ## headers are passed to the server in title case (e.g. "Content-Length")
-  new result
-  result.table = newTable[string, seq[string]]()
-  result.isTitleCase = titleCase
+  result = HttpHeaders(table: newTable[string, seq[string]](), isTitleCase: titleCase)
 
   for pair in keyValuePairs:
     let key = result.toCaseInsensitive(pair.key)
diff --git a/lib/pure/pegs.nim b/lib/pure/pegs.nim
index 5827b7444..86ad9c0f6 100644
--- a/lib/pure/pegs.nim
+++ b/lib/pure/pegs.nim
@@ -168,8 +168,9 @@ func charSet*(s: set[char]): Peg {.rtl, extern: "npegs$1".} =
   ## constructs a PEG from a character set `s`
   assert '\0' notin s
   result = Peg(kind: pkCharChoice)
-  new(result.charChoice)
-  result.charChoice[] = s
+  {.cast(noSideEffect).}:
+    new(result.charChoice)
+    result.charChoice[] = s
 
 func len(a: Peg): int {.inline.} = return a.sons.len
 func add(d: var Peg, s: Peg) {.inline.} = add(d.sons, s)
@@ -1823,9 +1824,7 @@ type
     skip: Peg
 
 func pegError(p: PegParser, msg: string, line = -1, col = -1) =
-  var e: ref EInvalidPeg
-  new(e)
-  e.msg = errorStr(p, msg, line, col)
+  var e = (ref EInvalidPeg)(msg: errorStr(p, msg, line, col))
   raise e
 
 func getTok(p: var PegParser) =
@@ -1909,7 +1908,8 @@ func primary(p: var PegParser): Peg =
       getTok(p)
     elif not arrowIsNextTok(p):
       var nt = getNonTerminal(p, p.tok.literal)
-      incl(nt.flags, ntUsed)
+      {.cast(noSideEffect).}:
+        incl(nt.flags, ntUsed)
       result = nonterminal(nt).token(p)
       getTok(p)
     else:
@@ -2002,12 +2002,14 @@ func parseRule(p: var PegParser): NonTerminal =
     result = getNonTerminal(p, p.tok.literal)
     if ntDeclared in result.flags:
       pegError(p, "attempt to redefine: " & result.name)
-    result.line = getLine(p)
-    result.col = getColumn(p)
+    {.cast(noSideEffect).}:
+      result.line = getLine(p)
+      result.col = getColumn(p)
     getTok(p)
     eat(p, tkArrow)
-    result.rule = parseExpr(p)
-    incl(result.flags, ntDeclared) # NOW inlining may be attempted
+    {.cast(noSideEffect).}:
+      result.rule = parseExpr(p)
+      incl(result.flags, ntDeclared) # NOW inlining may be attempted
   else:
     pegError(p, "rule expected, but found: " & p.tok.literal)
 
diff --git a/lib/pure/strtabs.nim b/lib/pure/strtabs.nim
index c72e6f876..11d5015cb 100644
--- a/lib/pure/strtabs.nim
+++ b/lib/pure/strtabs.nim
@@ -261,10 +261,7 @@ proc newStringTable*(mode: StringTableMode): owned(StringTableRef) {.
   ## See also:
   ## * `newStringTable(keyValuePairs) proc
   ##   <#newStringTable,varargs[tuple[string,string]],StringTableMode>`_
-  new(result)
-  result.mode = mode
-  result.counter = 0
-  newSeq(result.data, startSize)
+  result = StringTableRef(mode: mode, counter: 0, data: newSeq[KeyValuePair](startSize))
 
 proc newStringTable*(keyValuePairs: varargs[string],
                      mode: StringTableMode): owned(StringTableRef) {.
diff --git a/lib/pure/strutils.nim b/lib/pure/strutils.nim
index 8b3d36f66..0367ea1e5 100644
--- a/lib/pure/strutils.nim
+++ b/lib/pure/strutils.nim
@@ -624,7 +624,7 @@ iterator splitLines*(s: string, keepEol = false): string =
   ##
   ## Every `character literal <manual.html#lexical-analysis-character-literals>`_
   ## newline combination (CR, LF, CR-LF) is supported. The result strings
-  ## contain no trailing end of line characters unless parameter `keepEol`
+  ## contain no trailing end of line characters unless the parameter `keepEol`
   ## is set to `true`.
   ##
   ## Example:
diff --git a/lib/system.nim b/lib/system.nim
index 8faf8f4ce..d0f78bfbd 100644
--- a/lib/system.nim
+++ b/lib/system.nim
@@ -2358,7 +2358,8 @@ when not defined(gcArc) and not defined(gcOrc):
     if s.len == 0: return
     when not defined(js) and not defined(nimscript) and not defined(nimSeqsV2):
       var s = cast[PGenericSeq](s)
-      s.reserved = s.reserved or seqShallowFlag
+      {.noSideEffect.}:
+        s.reserved = s.reserved or seqShallowFlag
 
   proc shallow*(s: var string) {.noSideEffect, inline.} =
     ## Marks a string `s` as `shallow`:idx:. Subsequent assignments will not
@@ -2371,7 +2372,8 @@ when not defined(gcArc) and not defined(gcOrc):
         s = cast[PGenericSeq](newString(0))
       # string literals cannot become 'shallow':
       if (s.reserved and strlitFlag) == 0:
-        s.reserved = s.reserved or seqShallowFlag
+        {.noSideEffect.}:
+          s.reserved = s.reserved or seqShallowFlag
 
 type
   NimNodeObj = object
diff --git a/lib/system/seqs_v2.nim b/lib/system/seqs_v2.nim
index 40fd50b48..50f23111c 100644
--- a/lib/system/seqs_v2.nim
+++ b/lib/system/seqs_v2.nim
@@ -103,16 +103,17 @@ proc add*[T](x: var seq[T]; value: sink T) {.magic: "AppendSeqElem", noSideEffec
   ## containers should also call their adding proc `add` for consistency.
   ## Generic code becomes much easier to write if the Nim naming scheme is
   ## respected.
-  let oldLen = x.len
-  var xu = cast[ptr NimSeqV2[T]](addr x)
-  if xu.p == nil or xu.p.cap < oldLen+1:
-    xu.p = cast[typeof(xu.p)](prepareSeqAdd(oldLen, xu.p, 1, sizeof(T), alignof(T)))
-  xu.len = oldLen+1
-  # .nodestroy means `xu.p.data[oldLen] = value` is compiled into a
-  # copyMem(). This is fine as know by construction that
-  # in `xu.p.data[oldLen]` there is nothing to destroy.
-  # We also save the `wasMoved + destroy` pair for the sink parameter.
-  xu.p.data[oldLen] = value
+  {.cast(noSideEffect).}:
+    let oldLen = x.len
+    var xu = cast[ptr NimSeqV2[T]](addr x)
+    if xu.p == nil or xu.p.cap < oldLen+1:
+      xu.p = cast[typeof(xu.p)](prepareSeqAdd(oldLen, xu.p, 1, sizeof(T), alignof(T)))
+    xu.len = oldLen+1
+    # .nodestroy means `xu.p.data[oldLen] = value` is compiled into a
+    # copyMem(). This is fine as know by construction that
+    # in `xu.p.data[oldLen]` there is nothing to destroy.
+    # We also save the `wasMoved + destroy` pair for the sink parameter.
+    xu.p.data[oldLen] = value
 
 proc setLen[T](s: var seq[T], newlen: Natural) =
   {.noSideEffect.}:
diff --git a/tests/effects/tfuncs_cannot_mutate.nim b/tests/effects/tfuncs_cannot_mutate.nim
index 8784cbbb1..9934d27a7 100644
--- a/tests/effects/tfuncs_cannot_mutate.nim
+++ b/tests/effects/tfuncs_cannot_mutate.nim
@@ -1,9 +1,6 @@
 discard """
-  errormsg: "'mutate' can have side effects"
-  nimout: '''an object reachable from 'n' is potentially mutated
-tfuncs_cannot_mutate.nim(39, 15) the mutation is here
-tfuncs_cannot_mutate.nim(37, 7) is the statement that connected the mutation to the parameter
-'''
+  errormsg: "cannot mutate location select(x, z).data within a strict func"
+  line: 35
 """
 
 {.experimental: "strictFuncs".}
@@ -25,8 +22,7 @@ func len(n: Node): int =
     it = it.ri
 
 func doNotDistract(n: Node) =
-  var m = Node()
-  m.data = "abc"
+  var m = Node(data: "abc")
 
 func select(a, b: Node): Node = b
 
diff --git a/tests/effects/tfuncs_cannot_mutate2.nim b/tests/effects/tfuncs_cannot_mutate2.nim
index d5082e57b..86f811017 100644
--- a/tests/effects/tfuncs_cannot_mutate2.nim
+++ b/tests/effects/tfuncs_cannot_mutate2.nim
@@ -1,9 +1,6 @@
 discard """
-  errormsg: "'copy' can have side effects"
-  nimout: '''an object reachable from 'y' is potentially mutated
-tfuncs_cannot_mutate2.nim(15, 7) the mutation is here
-tfuncs_cannot_mutate2.nim(13, 10) is the statement that connected the mutation to the parameter
-'''
+  errormsg: "cannot mutate location x[0].a within a strict func"
+  line: 12
 """
 
 {.experimental: "strictFuncs".}
diff --git a/tests/effects/tfuncs_cannot_mutate_simple.nim b/tests/effects/tfuncs_cannot_mutate_simple.nim
index a94a8d746..0ae4a0db9 100644
--- a/tests/effects/tfuncs_cannot_mutate_simple.nim
+++ b/tests/effects/tfuncs_cannot_mutate_simple.nim
@@ -1,7 +1,6 @@
 discard """
-  errormsg: "'edit' can have side effects"
-  nimout: '''an object reachable from 'x' is potentially mutated
-tfuncs_cannot_mutate_simple.nim(16, 4) the mutation is here'''
+  errormsg: '''cannot mutate location x.data within a strict func'''
+  line: 15
 """
 
 {.experimental: "strictFuncs".}
diff --git a/tests/effects/tstrictfuncs_misc.nim b/tests/effects/tstrictfuncs_misc.nim
new file mode 100644
index 000000000..59d850763
--- /dev/null
+++ b/tests/effects/tstrictfuncs_misc.nim
@@ -0,0 +1,65 @@
+discard """
+  action: compile
+"""
+
+{.experimental: "strictFuncs".}
+
+func sortedFake1[T](a: openArray[T]): seq[T] =
+  for i in 0 .. a.high: result.add a[i]
+func sortedFake2[T](a: openArray[T]): seq[T] =
+  result = newSeq[T](a.len)
+  for i in 0 .. a.high: result[i] = a[i]
+type Foo1 = object
+type Foo2 = ref object
+block:
+  let a1 = sortedFake1([Foo1()]) # ok
+  let a2 = sortedFake1([Foo2()]) # ok
+block:
+  let a1 = sortedFake2([Foo1()]) # ok
+  let a2 = sortedFake2([Foo2()]) # error: Error: 'sortedFake2' can have side effects
+
+
+import std/sequtils
+type Foob = ref object
+  x: int
+let a1 = zip(@[1,2], @[1,2]) # ok
+let a2 = zip(@[Foob(x: 1)], @[Foob(x: 2)]) # error in 1.6.0 RC2, but not 1.4.x
+
+
+# bug #20863
+type
+  Fooc = ref object
+
+func twice(foo: Fooc) =
+  var a = newSeq[Fooc](2)
+  a[0] = foo # No error.
+  a[1] = foo # Error: 'twice' can have side effects.
+
+let foo = Fooc()
+twice(foo)
+
+# bug #17387
+import json
+
+func parseColumn(columnNode: JsonNode) =
+  let columnName = columnNode["name"].str
+
+parseColumn(%*{"a": "b"})
+
+type
+  MyTable = object
+    data: seq[int]
+
+  JsonNode3 = ref object
+    fields: MyTable
+
+proc `[]`(t: var MyTable, key: string): var int =
+  result = t.data[0]
+
+proc `[]`(x: JsonNode3, key: string): int =
+  result = x.fields[key]
+
+func parseColumn(columnNode: JsonNode3) =
+  var columnName = columnNode["test"]
+
+parseColumn(JsonNode3())