cycle collector (#14071)

* figured out the wrong cycle trace proc problem
* cycle collector/break refactorings and minor improvements

3 files changed, 74 insertions, 106 deletions

diff --git a/lib/system/cellseqs_v2.nim b/lib/system/cellseqs_v2.nim
new file mode 100644
index 000000000..c71ba9726
--- /dev/null
+++ b/lib/system/cellseqs_v2.nim
@@ -0,0 +1,55 @@
+#
+#
+#            Nim's Runtime Library
+#        (c) Copyright 2019 Andreas Rumpf
+#
+#    See the file "copying.txt", included in this
+#    distribution, for details about the copyright.
+#
+
+# Cell seqs for cyclebreaker and cyclicrefs_v2.
+
+type
+  CellTuple = (ptr pointer, PNimType)
+  CellArray = ptr UncheckedArray[CellTuple]
+  CellSeq = object
+    len, cap: int
+    d: CellArray
+
+proc add(s: var CellSeq, c: ptr pointer; t: PNimType) {.inline.} =
+  if s.len >= s.cap:
+    s.cap = s.cap * 3 div 2
+    when defined(useMalloc):
+      var d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple))))
+    else:
+      var d = cast[CellArray](alloc(s.cap * sizeof(CellTuple)))
+    copyMem(d, s.d, s.len * sizeof(CellTuple))
+    when defined(useMalloc):
+      c_free(s.d)
+    else:
+      dealloc(s.d)
+    s.d = d
+    # XXX: realloc?
+  s.d[s.len] = (c, t)
+  inc(s.len)
+
+proc init(s: var CellSeq, cap: int = 1024) =
+  s.len = 0
+  s.cap = cap
+  when defined(useMalloc):
+    s.d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple))))
+  else:
+    s.d = cast[CellArray](alloc(s.cap * sizeof(CellTuple)))
+
+proc deinit(s: var CellSeq) =
+  when defined(useMalloc):
+    c_free(s.d)
+  else:
+    dealloc(s.d)
+  s.d = nil
+  s.len = 0
+  s.cap = 0
+
+proc pop(s: var CellSeq): (ptr pointer, PNimType) =
+  result = s.d[s.len-1]
+  dec s.len
diff --git a/lib/system/cyclebreaker.nim b/lib/system/cyclebreaker.nim
index e036acb53..1f320b30e 100644
--- a/lib/system/cyclebreaker.nim
+++ b/lib/system/cyclebreaker.nim
@@ -52,6 +52,8 @@ That seems acceptable, no leak is produced. This implies that the standard
 depth-first traversal suffices.
 
 ]#
+include cellseqs_v2
+
 const
   colGreen = 0b000
   colYellow = 0b001
@@ -72,57 +74,9 @@ proc nimIncRefCyclic(p: pointer) {.compilerRtl, inl.} =
   inc h.rc, rcIncrement
 
 type
-  CellTuple = (ptr pointer, PNimType)
-  CellArray = ptr UncheckedArray[CellTuple]
-  CellSeq = object
-    len, cap: int
-    d: CellArray
-
   GcEnv = object
     traceStack: CellSeq
 
-# ------------------- cell seq handling --------------------------------------
-
-proc add(s: var CellSeq, c: ptr pointer; t: PNimType) {.inline.} =
-  if s.len >= s.cap:
-    s.cap = s.cap * 3 div 2
-    when defined(useMalloc):
-      var d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple))))
-    else:
-      var d = cast[CellArray](alloc(s.cap * sizeof(CellTuple)))
-    copyMem(d, s.d, s.len * sizeof(CellTuple))
-    when defined(useMalloc):
-      c_free(s.d)
-    else:
-      dealloc(s.d)
-    s.d = d
-    # XXX: realloc?
-  s.d[s.len] = (c, t)
-  inc(s.len)
-
-proc init(s: var CellSeq, cap: int = 1024) =
-  s.len = 0
-  s.cap = cap
-  when defined(useMalloc):
-    s.d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple))))
-  else:
-    s.d = cast[CellArray](alloc(s.cap * sizeof(CellTuple)))
-
-proc deinit(s: var CellSeq) =
-  when defined(useMalloc):
-    c_free(s.d)
-  else:
-    dealloc(s.d)
-  s.d = nil
-  s.len = 0
-  s.cap = 0
-
-proc pop(s: var CellSeq): (ptr pointer, PNimType) =
-  result = s.d[s.len-1]
-  dec s.len
-
-# ----------------------------------------------------------------------------
-
 proc trace(p: pointer; desc: PNimType; j: var GcEnv) {.inline.} =
   when false:
     cprintf("[Trace] desc: %p %p\n", desc, p)
diff --git a/lib/system/cyclicrefs_v2.nim b/lib/system/cyclicrefs_v2.nim
index 0dd669925..819cb2bd0 100644
--- a/lib/system/cyclicrefs_v2.nim
+++ b/lib/system/cyclicrefs_v2.nim
@@ -14,6 +14,8 @@
 # "Cyclic reference counting" by Rafael Dueire Lins
 # R.D. Lins / Information Processing Letters 109 (2008) 71–78
 
+include cellseqs_v2
+
 const
   colGreen = 0b000
   colYellow = 0b001
@@ -45,58 +47,10 @@ proc markCyclic*[T](x: ref T) {.inline.} =
   h.setColor colYellow
 
 type
-  CellTuple = (Cell, PNimType)
-  CellArray = ptr UncheckedArray[CellTuple]
-  CellSeq = object
-    len, cap: int
-    d: CellArray
-
   GcEnv = object
     traceStack: CellSeq
     jumpStack: CellSeq
 
-# ------------------- cell seq handling --------------------------------------
-
-proc add(s: var CellSeq, c: Cell; t: PNimType) {.inline.} =
-  if s.len >= s.cap:
-    s.cap = s.cap * 3 div 2
-    when defined(useMalloc):
-      var d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple))))
-    else:
-      var d = cast[CellArray](alloc(s.cap * sizeof(CellTuple)))
-    copyMem(d, s.d, s.len * sizeof(CellTuple))
-    when defined(useMalloc):
-      c_free(s.d)
-    else:
-      dealloc(s.d)
-    s.d = d
-    # XXX: realloc?
-  s.d[s.len] = (c, t)
-  inc(s.len)
-
-proc init(s: var CellSeq, cap: int = 1024) =
-  s.len = 0
-  s.cap = cap
-  when defined(useMalloc):
-    s.d = cast[CellArray](c_malloc(uint(s.cap * sizeof(CellTuple))))
-  else:
-    s.d = cast[CellArray](alloc(s.cap * sizeof(CellTuple)))
-
-proc deinit(s: var CellSeq) =
-  when defined(useMalloc):
-    c_free(s.d)
-  else:
-    dealloc(s.d)
-  s.d = nil
-  s.len = 0
-  s.cap = 0
-
-proc pop(s: var CellSeq): (Cell, PNimType) =
-  result = s.d[s.len-1]
-  dec s.len
-
-# ----------------------------------------------------------------------------
-
 proc trace(s: Cell; desc: PNimType; j: var GcEnv) {.inline.} =
   if desc.traceImpl != nil:
     var p = s +! sizeof(RefHeader)
@@ -116,7 +70,10 @@ proc collect(s: Cell; desc: PNimType; j: var GcEnv) =
     s.setColor colGreen
     trace(s, desc, j)
     while j.traceStack.len > 0:
-      let (t, desc) = j.traceStack.pop()
+      let (p, desc) = j.traceStack.pop()
+      let t = head(p[])
+      #Remove(<S, T>):
+      p[] = nil
       if t.color == colRed:
         t.setColor colGreen
         trace(t, desc, j)
@@ -129,7 +86,8 @@ proc markRed(s: Cell; desc: PNimType; j: var GcEnv) =
     s.setColor colRed
     trace(s, desc, j)
     while j.traceStack.len > 0:
-      let (t, desc) = j.traceStack.pop()
+      let (p, desc) = j.traceStack.pop()
+      let t = head(p[])
       when traceCollector:
         cprintf("[Cycle dec] %p %ld color %ld in jumpstack %ld\n", t, t.rc shr rcShift, t.color, t.rc and jumpStackFlag)
       dec t.rc, rcIncrement
@@ -137,7 +95,7 @@ proc markRed(s: Cell; desc: PNimType; j: var GcEnv) =
         t.rc = t.rc or jumpStackFlag
         when traceCollector:
           cprintf("[Now in jumpstack] %p %ld color %ld in jumpstack %ld\n", t, t.rc shr rcShift, t.color, t.rc and jumpStackFlag)
-        j.jumpStack.add(t, desc)
+        j.jumpStack.add(p, desc)
       if t.color != colRed:
         t.setColor colRed
         trace(t, desc, j)
@@ -146,7 +104,8 @@ proc scanGreen(s: Cell; desc: PNimType; j: var GcEnv) =
   s.setColor colGreen
   trace(s, desc, j)
   while j.traceStack.len > 0:
-    let (t, desc) = j.traceStack.pop()
+    let (p, desc) = j.traceStack.pop()
+    let t = head(p[])
     if t.color != colGreen:
       t.setColor colGreen
       trace(t, desc, j)
@@ -158,15 +117,13 @@ proc nimTraceRef(q: pointer; desc: PNimType; env: pointer) {.compilerRtl.} =
   let p = cast[ptr pointer](q)
   if p[] != nil:
     var j = cast[ptr GcEnv](env)
-    var t = head(p[])
-    j.traceStack.add(t, desc)
+    j.traceStack.add(p, desc)
 
 proc nimTraceRefDyn(q: pointer; env: pointer) {.compilerRtl.} =
   let p = cast[ptr pointer](q)
   if p[] != nil:
     var j = cast[ptr GcEnv](env)
-    var t = head(p[])
-    j.traceStack.add(t, cast[ptr PNimType](p[])[])
+    j.traceStack.add(p, cast[ptr PNimType](p[])[])
 
 proc scan(s: Cell; desc: PNimType; j: var GcEnv) =
   when traceCollector:
@@ -181,7 +138,8 @@ proc scan(s: Cell; desc: PNimType; j: var GcEnv) =
     # that are still alive; we also need to mark what they
     # refer to as alive:
     while j.jumpStack.len > 0:
-      let (t, desc) = j.jumpStack.pop
+      let (p, desc) = j.jumpStack.pop
+      let t = head(p[])
       # not in jump stack anymore!
       t.rc = t.rc and not jumpStackFlag
       if t.color == colRed and (t.rc and not rcMask) >= 0:
@@ -202,7 +160,8 @@ proc traceCycle(s: Cell; desc: PNimType) {.noinline.} =
   markRed(s, desc, j)
   scan(s, desc, j)
   while j.jumpStack.len > 0:
-    let (t, desc) = j.jumpStack.pop
+    let (p, desc) = j.jumpStack.pop
+    let t = head(p[])
     # not in jump stack anymore!
     t.rc = t.rc and not jumpStackFlag
   deinit j.jumpStack