ARC: cycle detector (#12823)

* first implementation of the =trace and =dispose hooks for the cycle collector
* a cycle collector for ARC: progress
* manual: the .acyclic pragma is a thing once again
* gcbench: adaptations for --gc:arc
* enable valgrind tests for the strutils tests
* testament: better valgrind support
* ARC refactoring: growable jumpstacks
* ARC cycle detector: non-recursive algorithm
* moved and renamed core/ files back to system/
* refactoring: --gc:arc vs --gc:orc since 'orc' is even more experimental and we want to ship --gc:arc soonish

16 files changed, 299 insertions, 16 deletions

diff --git a/tests/destructor/tarc2.nim b/tests/destructor/tarc2.nim
index 56dbfe929..bd6343b2f 100644
--- a/tests/destructor/tarc2.nim
+++ b/tests/destructor/tarc2.nim
@@ -1,6 +1,6 @@
 discard """
-  output: '''leak: true'''
-  cmd: '''nim c --gc:arc $file'''
+  output: '''leak: false'''
+  cmd: '''nim c --gc:orc $file'''
 """
 
 type
@@ -19,11 +19,8 @@ proc addX(x: T; child: T) =
 proc main(rootName: string) =
   var root = create()
   root.data = rootName
-  # this implies we do the refcounting wrong. We should leak memory here
-  # and not create a destruction cycle:
   root.addX root
 
 let mem = getOccupiedMem()
 main("yeah")
-# since we created a retain cycle, we MUST leak memory here:
 echo "leak: ", getOccupiedMem() - mem > 0
diff --git a/tests/destructor/tarctypesections.nim b/tests/destructor/tarctypesections.nim
new file mode 100644
index 000000000..da81f1884
--- /dev/null
+++ b/tests/destructor/tarctypesections.nim
@@ -0,0 +1,70 @@
+discard """
+  output: "MEM 0"
+  cmd: "nim c --gc:arc $file"
+"""
+
+type
+  RefNode = ref object
+    le, ri: RefNode
+    name: char
+
+proc edge0(a, b: RefNode) =
+  if a.le == nil: a.le = b
+  else: a.ri = b
+
+proc createNode0(name: char): RefNode =
+  new result
+  result.name = name
+
+proc main0 =
+  let r = createNode0('R')
+  let c = createNode0('C')
+  c.edge0 r
+
+
+type
+  NodeDesc = object
+    le, ri: Node
+    name: char
+  Node = ref NodeDesc
+
+proc edge(a, b: Node) =
+  if a.le == nil: a.le = b
+  else: a.ri = b
+
+proc createNode(name: char): Node =
+  new result
+  result.name = name
+
+proc main =
+  let r = createNode('R')
+  let c = createNode('C')
+  c.edge r
+
+
+type
+  NodeB = ref NodeBo
+  NodeBo = object
+    le, ri: NodeB
+    name: char
+
+proc edge(a, b: NodeB) =
+  if a.le == nil: a.le = b
+  else: a.ri = b
+
+proc createNodeB(name: char): NodeB =
+  new result
+  result.name = name
+
+
+proc mainB =
+  let r = createNodeB('R')
+  let c = createNodeB('C')
+  c.edge r
+
+
+let memB = getOccupiedMem()
+main0()
+main()
+mainB()
+echo "MEM ", getOccupiedMem() - memB
diff --git a/tests/destructor/tasync_prototype_cyclic.nim b/tests/destructor/tasync_prototype_cyclic.nim
new file mode 100644
index 000000000..136e0b676
--- /dev/null
+++ b/tests/destructor/tasync_prototype_cyclic.nim
@@ -0,0 +1,54 @@
+discard """
+  output: '''asdas
+processClient end
+false
+MEMORY 0
+'''
+  cmd: '''nim c --gc:orc $file'''
+"""
+
+type
+  PAsyncHttpServer = ref object
+    value: string
+  PFutureBase = ref object
+    callback: proc () {.closure.}
+    value: string
+    failed: bool
+
+proc accept(server: PAsyncHttpServer): PFutureBase =
+  new(result)
+  result.callback = proc () =
+    discard
+  server.value = "hahaha"
+
+proc processClient(): PFutureBase =
+  new(result)
+
+proc serve(server: PAsyncHttpServer): PFutureBase =
+  iterator serveIter(): PFutureBase {.closure.} =
+    echo server.value
+    while true:
+      var acceptAddrFut = server.accept()
+      yield acceptAddrFut
+      var fut = acceptAddrFut.value
+
+      var f = processClient()
+      when true:
+        f.callback =
+          proc () =
+            echo("processClient end")
+            echo(f.failed)
+      yield f
+  var x = serveIter
+  for i in 0 .. 1:
+    result = x()
+    if result.callback != nil:
+      result.callback()
+
+let mem = getOccupiedMem()
+
+proc main =
+  discard serve(PAsyncHttpServer(value: "asdas"))
+
+main()
+echo "MEMORY ", getOccupiedMem() - mem
diff --git a/tests/destructor/tbintree2.nim b/tests/destructor/tbintree2.nim
index 15a3c41ec..5f88ffff5 100644
--- a/tests/destructor/tbintree2.nim
+++ b/tests/destructor/tbintree2.nim
@@ -4,7 +4,7 @@ discard """
 3 3  alloc/dealloc pairs: 0'''
 """
 
-import core / allocators
+import system / allocators
 import system / ansi_c
 
 import random
diff --git a/tests/destructor/tcycle1.nim b/tests/destructor/tcycle1.nim
new file mode 100644
index 000000000..c30977433
--- /dev/null
+++ b/tests/destructor/tcycle1.nim
@@ -0,0 +1,53 @@
+discard """
+  output: "MEM 0"
+  cmd: "nim c --gc:orc $file"
+"""
+
+type
+  Node = ref object of RootObj
+    le, ri: Node
+    name: char
+
+proc edge(a, b: Node) =
+  if a.le == nil: a.le = b
+  else: a.ri = b
+
+proc createNode(name: char): Node =
+  new result
+  result.name = name
+
+#[
+
++---------+      +------+
+|         |      |      |
+|  A      +----->+      <------+-------------+
++--+------+      |      |      |             |
+   |             |      |      |     C       |
+   |             |  R   |      |             |
++--v------+      |      |      +-------------+
+|         |      |      |        ^
+|   B     <------+      |        |
+|         |      |      +--------+
++---------+      |      |
+                 +------+
+
+]#
+
+proc main =
+  let a = createNode('A')
+  let b = createNode('B')
+  let r = createNode('R')
+  let c = createNode('C')
+
+  a.edge b
+  a.edge r
+
+  r.edge b
+  r.edge c
+
+  c.edge r
+
+
+let mem = getOccupiedMem()
+main()
+echo "MEM ", getOccupiedMem() - mem
diff --git a/tests/destructor/tcycle2.nim b/tests/destructor/tcycle2.nim
new file mode 100644
index 000000000..c4b297559
--- /dev/null
+++ b/tests/destructor/tcycle2.nim
@@ -0,0 +1,18 @@
+discard """
+  output: "MEM 0"
+  cmd: "nim c --gc:orc $file"
+"""
+
+type
+  Node = ref object
+    kids: seq[Node]
+    data: string
+
+proc main(x: int) =
+  var n = Node(kids: @[], data: "3" & $x)
+  let m = n
+  n.kids.add m
+
+let mem = getOccupiedMem()
+main(90)
+echo "MEM ", getOccupiedMem() - mem
diff --git a/tests/destructor/tcycle3.nim b/tests/destructor/tcycle3.nim
new file mode 100644
index 000000000..a938ded01
--- /dev/null
+++ b/tests/destructor/tcycle3.nim
@@ -0,0 +1,64 @@
+discard """
+  output: '''BEGIN
+END
+END 2
+0'''
+  cmd: '''nim c --gc:orc $file'''
+"""
+
+# extracted from thavlak.nim
+
+type
+  BasicBlock = ref object
+    inEdges: seq[BasicBlock]
+    outEdges: seq[BasicBlock]
+    name: int
+
+proc newBasicBlock(name: int): BasicBlock =
+  result = BasicBlock(
+    inEdges: newSeq[BasicBlock](),
+    outEdges: newSeq[BasicBlock](),
+    name: name
+  )
+
+type
+  Cfg = object
+    basicBlockMap: seq[BasicBlock]
+    startNode: BasicBlock
+
+proc newCfg(): Cfg =
+  result = Cfg(
+    basicBlockMap: newSeq[BasicBlock](),
+    startNode: nil)
+
+proc createNode(cfg: var Cfg, name: int): BasicBlock =
+  if name < cfg.basicBlockMap.len:
+    result = cfg.basicBlockMap[name]
+  else:
+    result = newBasicBlock(name)
+    cfg.basicBlockMap.setLen name+1
+    cfg.basicBlockMap[name] = result
+
+proc newBasicBlockEdge(cfg: var Cfg, fromName, toName: int) =
+  echo "BEGIN"
+  let fr = cfg.createNode(fromName)
+  let to = cfg.createNode(toName)
+
+  fr.outEdges.add(to)
+  to.inEdges.add(fr)
+
+proc run(cfg: var Cfg) =
+  cfg.startNode = cfg.createNode(0) # RC = 2
+  newBasicBlockEdge(cfg, 0, 1) #
+  echo "END"
+
+  discard cfg.createNode(1)
+
+proc main =
+  var c = newCfg()
+  c.run
+  echo "END 2"
+
+let mem = getOccupiedMem()
+main()
+echo getOccupiedMem() - mem
diff --git a/tests/destructor/tgcdestructors.nim b/tests/destructor/tgcdestructors.nim
index 7eb865915..4a66b4f77 100644
--- a/tests/destructor/tgcdestructors.nim
+++ b/tests/destructor/tgcdestructors.nim
@@ -13,7 +13,7 @@ true
 41 41'''
 """
 
-import allocators
+import system / allocators
 include system / ansi_c
 
 proc main =
diff --git a/tests/destructor/tnewruntime_misc.nim b/tests/destructor/tnewruntime_misc.nim
index 025383565..612d1a116 100644
--- a/tests/destructor/tnewruntime_misc.nim
+++ b/tests/destructor/tnewruntime_misc.nim
@@ -11,7 +11,7 @@ test
 '''
 """
 
-import core / allocators
+import system / allocators
 import system / ansi_c
 
 import tables
@@ -132,5 +132,5 @@ proc xx(xml: string): MyObject =
   result.x  = xml
   defer: echo stream
 
- 
+
 discard xx("test")
diff --git a/tests/destructor/tnewruntime_strutils.nim b/tests/destructor/tnewruntime_strutils.nim
index 54ce4acea..3e4ee27be 100644
--- a/tests/destructor/tnewruntime_strutils.nim
+++ b/tests/destructor/tnewruntime_strutils.nim
@@ -1,11 +1,12 @@
 discard """
-  cmd: '''nim c --newruntime $file'''
+  valgrind: true
+  cmd: '''nim c --newruntime -d:useMalloc $file'''
   output: '''422 422'''
 """
 
 import strutils, os, std / wordwrap
 
-import core / allocators
+import system / allocators
 import system / ansi_c
 
 # bug #11004
diff --git a/tests/destructor/tselect.nim b/tests/destructor/tselect.nim
new file mode 100644
index 000000000..9262b47d4
--- /dev/null
+++ b/tests/destructor/tselect.nim
@@ -0,0 +1,26 @@
+discard """
+   output: '''abcsuffix
+xyzsuffix'''
+  cmd: '''nim c --gc:arc $file'''
+"""
+
+proc select(cond: bool; a, b: sink string): string =
+  if cond:
+    result = a # moves a into result
+  else:
+    result = b # moves b into result
+
+proc test(param: string; cond: bool) =
+  var x = "abc" & param
+  var y = "xyz" & param
+
+  # possible self-assignment:
+  x = select(cond, x, y)
+
+  echo x
+  # 'select' must communicate what parameter has been
+  # consumed. We cannot simply generate:
+  # (select(...); wasMoved(x); wasMoved(y))
+
+test("suffix", true)
+test("suffix", false)
diff --git a/tests/destructor/tsimpleclosure.nim b/tests/destructor/tsimpleclosure.nim
index 583cc7d88..088f4a95c 100644
--- a/tests/destructor/tsimpleclosure.nim
+++ b/tests/destructor/tsimpleclosure.nim
@@ -8,7 +8,7 @@ hello
 2 2  alloc/dealloc pairs: 0'''
 """
 
-import core / allocators
+import system / allocators
 import system / ansi_c
 
 proc main(): owned(proc()) =
diff --git a/tests/destructor/tuse_ownedref_after_move.nim b/tests/destructor/tuse_ownedref_after_move.nim
index 2108fa01c..31f580db3 100644
--- a/tests/destructor/tuse_ownedref_after_move.nim
+++ b/tests/destructor/tuse_ownedref_after_move.nim
@@ -4,7 +4,7 @@ discard """
   line: 49
 """
 
-import core / allocators
+import system / allocators
 import system / ansi_c
 
 type
diff --git a/tests/destructor/tv2_raise.nim b/tests/destructor/tv2_raise.nim
index dcc3b1b38..409cdead8 100644
--- a/tests/destructor/tv2_raise.nim
+++ b/tests/destructor/tv2_raise.nim
@@ -6,7 +6,7 @@ discard """
 
 import strutils, math
 import system / ansi_c
-import core / allocators
+import system / allocators
 
 proc mainA =
   try:
diff --git a/tests/destructor/twidgets.nim b/tests/destructor/twidgets.nim
index 1d75a803d..9537748e3 100644
--- a/tests/destructor/twidgets.nim
+++ b/tests/destructor/twidgets.nim
@@ -5,7 +5,7 @@ clicked!
 1 1  alloc/dealloc pairs: 0'''
 """
 
-import core / allocators
+import system / allocators
 import system / ansi_c
 
 type
diff --git a/tests/destructor/twidgets_unown.nim b/tests/destructor/twidgets_unown.nim
index 39d3c46df..d594ad54c 100644
--- a/tests/destructor/twidgets_unown.nim
+++ b/tests/destructor/twidgets_unown.nim
@@ -5,7 +5,7 @@ clicked!
 6 6  alloc/dealloc pairs: 0'''
 """
 
-import core / allocators
+import system / allocators
 import system / ansi_c
 
 type