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

4 files changed, 0 insertions, 518 deletions

diff --git a/lib/core/allocators.nim b/lib/core/allocators.nim
deleted file mode 100644
index 43aae0111..000000000
--- a/lib/core/allocators.nim
+++ /dev/null
@@ -1,80 +0,0 @@
-#
-#
-#            Nim's Runtime Library
-#        (c) Copyright 2017 Nim contributors
-#
-#    See the file "copying.txt", included in this
-#    distribution, for details about the copyright.
-#
-
-## Unstable API.
-
-type
-  AllocatorFlag* {.pure.} = enum  ## flags describing the properties of the allocator
-    ThreadLocal ## the allocator is thread local only.
-    ZerosMem    ## the allocator always zeros the memory on an allocation
-  Allocator* = ptr AllocatorObj
-  AllocatorObj* {.inheritable, compilerproc.} = object
-    alloc*: proc (a: Allocator; size: int; alignment: int = 8): pointer {.nimcall, raises: [], tags: [], gcsafe.}
-    dealloc*: proc (a: Allocator; p: pointer; size: int) {.nimcall, raises: [], tags: [], gcsafe.}
-    realloc*: proc (a: Allocator; p: pointer; oldSize, newSize: int): pointer {.nimcall, raises: [], tags: [], gcsafe.}
-    deallocAll*: proc (a: Allocator) {.nimcall, raises: [], tags: [], gcsafe.}
-    flags*: set[AllocatorFlag]
-    name*: cstring
-    allocCount: int
-    deallocCount: int
-
-var
-  localAllocator {.threadvar.}: Allocator
-  sharedAllocator: Allocator
-  allocatorStorage {.threadvar.}: AllocatorObj
-
-when defined(useMalloc) and not defined(nimscript):
-  import "system/ansi_c"
-
-import "system/memory"
-
-template `+!`(p: pointer, s: int): pointer =
-  cast[pointer](cast[int](p) +% s)
-
-proc getLocalAllocator*(): Allocator =
-  result = localAllocator
-  if result == nil:
-    result = addr allocatorStorage
-    result.alloc = proc (a: Allocator; size: int; alignment: int = 8): pointer {.nimcall, raises: [].} =
-      when defined(useMalloc) and not defined(nimscript):
-        result = c_malloc(cuint size)
-        # XXX do we need this?
-        nimZeroMem(result, size)
-      else:
-        result = system.alloc0(size)
-      inc a.allocCount
-    result.dealloc = proc (a: Allocator; p: pointer; size: int) {.nimcall, raises: [].} =
-      when defined(useMalloc) and not defined(nimscript):
-        c_free(p)
-      else:
-        system.dealloc(p)
-      inc a.deallocCount
-    result.realloc = proc (a: Allocator; p: pointer; oldSize, newSize: int): pointer {.nimcall, raises: [].} =
-      when defined(useMalloc) and not defined(nimscript):
-        result = c_realloc(p, cuint newSize)
-      else:
-        result = system.realloc(p, newSize)
-      nimZeroMem(result +! oldSize, newSize - oldSize)
-    result.deallocAll = nil
-    result.flags = {ThreadLocal, ZerosMem}
-    result.name = "nim_local"
-    localAllocator = result
-
-proc setLocalAllocator*(a: Allocator) =
-  localAllocator = a
-
-proc getSharedAllocator*(): Allocator =
-  result = sharedAllocator
-
-proc setSharedAllocator*(a: Allocator) =
-  sharedAllocator = a
-
-proc allocCounters*(): (int, int) =
-  let a = getLocalAllocator()
-  result = (a.allocCount, a.deallocCount)
diff --git a/lib/core/runtime_v2.nim b/lib/core/runtime_v2.nim
deleted file mode 100644
index d566a4c69..000000000
--- a/lib/core/runtime_v2.nim
+++ /dev/null
@@ -1,157 +0,0 @@
-#[
-In this new runtime we simplify the object layouts a bit: The runtime type
-information is only accessed for the objects that have it and it's always
-at offset 0 then. The ``ref`` object header is independent from the
-runtime type and only contains a reference count.
-
-Object subtyping is checked via the generated 'name'. This should have
-comparable overhead to the old pointer chasing approach but has the benefit
-that it works across DLL boundaries.
-
-The generated name is a concatenation of the object names in the hierarchy
-so that a subtype check becomes a substring check. For example::
-
-  type
-    ObjectA = object of RootObj
-    ObjectB = object of ObjectA
-
-ObjectA's ``name`` is "|ObjectA|RootObj|".
-ObjectB's ``name`` is "|ObjectB|ObjectA|RootObj|".
-
-Now to check for ``x of ObjectB`` we need to check
-for ``x.typ.name.hasSubstring("|ObjectB|")``. In the actual implementation,
-however, we could also use a
-hash of ``package & "." & module & "." & name`` to save space.
-
-]#
-
-type
-  RefHeader = object
-    rc: int # the object header is now a single RC field.
-            # we could remove it in non-debug builds for the 'owned ref'
-            # design but this seems unwise.
-
-template `+!`(p: pointer, s: int): pointer =
-  cast[pointer](cast[int](p) +% s)
-
-template `-!`(p: pointer, s: int): pointer =
-  cast[pointer](cast[int](p) -% s)
-
-template head(p: pointer): ptr RefHeader =
-  cast[ptr RefHeader](cast[int](p) -% sizeof(RefHeader))
-
-var allocs*: int
-
-proc nimNewObj(size: int): pointer {.compilerRtl.} =
-  let s = size + sizeof(RefHeader)
-  when defined(nimscript):
-    discard
-  elif defined(useMalloc):
-    var orig = c_malloc(cuint s)
-    nimZeroMem(orig, s)
-    result = orig +! sizeof(RefHeader)
-  else:
-    result = alloc0(s) +! sizeof(RefHeader)
-  when hasThreadSupport:
-    atomicInc allocs
-  else:
-    inc allocs
-
-proc nimDecWeakRef(p: pointer) {.compilerRtl, inl.} =
-  when hasThreadSupport:
-    atomicDec head(p).rc
-  else:
-    dec head(p).rc
-
-proc nimIncRef(p: pointer) {.compilerRtl, inl.} =
-  when hasThreadSupport:
-    atomicInc head(p).rc
-  else:
-    inc head(p).rc
-    #cprintf("[INCREF] %p\n", p)
-
-proc nimRawDispose(p: pointer) {.compilerRtl.} =
-  when not defined(nimscript):
-    when defined(nimOwnedEnabled):
-      when hasThreadSupport:
-        let hasDanglingRefs = atomicLoadN(addr head(p).rc, ATOMIC_RELAXED) != 0
-      else:
-        let hasDanglingRefs = head(p).rc != 0
-      if hasDanglingRefs:
-        cstderr.rawWrite "[FATAL] dangling references exist\n"
-        quit 1
-    when defined(useMalloc):
-      c_free(p -! sizeof(RefHeader))
-    else:
-      dealloc(p -! sizeof(RefHeader))
-    if allocs > 0:
-      when hasThreadSupport:
-        discard atomicDec(allocs)
-      else:
-        dec allocs
-    else:
-      cstderr.rawWrite "[FATAL] unpaired dealloc\n"
-      quit 1
-
-template dispose*[T](x: owned(ref T)) = nimRawDispose(cast[pointer](x))
-#proc dispose*(x: pointer) = nimRawDispose(x)
-
-proc nimDestroyAndDispose(p: pointer) {.compilerRtl.} =
-  let d = cast[ptr PNimType](p)[].destructor
-  if d != nil: cast[DestructorProc](d)(p)
-  when false:
-    cstderr.rawWrite cast[ptr PNimType](p)[].name
-    cstderr.rawWrite "\n"
-    if d == nil:
-      cstderr.rawWrite "bah, nil\n"
-    else:
-      cstderr.rawWrite "has destructor!\n"
-  nimRawDispose(p)
-
-proc nimDecRefIsLast(p: pointer): bool {.compilerRtl, inl.} =
-  if p != nil:
-    when hasThreadSupport:
-      if atomicLoadN(addr head(p).rc, ATOMIC_RELAXED) == 0:
-        result = true
-      else:
-        discard atomicDec(head(p).rc)
-    else:
-      if head(p).rc == 0:
-        result = true
-        #cprintf("[DESTROY] %p\n", p)
-      else:
-        dec head(p).rc
-        # According to Lins it's correct to do nothing else here.
-        #cprintf("[DeCREF] %p\n", p)
-
-proc GC_unref*[T](x: ref T) =
-  ## New runtime only supports this operation for 'ref T'.
-  if nimDecRefIsLast(cast[pointer](x)):
-    # XXX this does NOT work for virtual destructors!
-    `=destroy`(x[])
-    nimRawDispose(cast[pointer](x))
-
-proc GC_ref*[T](x: ref T) =
-  ## New runtime only supports this operation for 'ref T'.
-  if x != nil: nimIncRef(cast[pointer](x))
-
-template GC_fullCollect* =
-  ## Forces a full garbage collection pass. With ``--gc:arc`` a nop.
-  discard
-
-template setupForeignThreadGc* =
-  ## With ``--gc:arc`` a nop.
-  discard
-
-template tearDownForeignThreadGc* =
-  ## With ``--gc:arc`` a nop.
-  discard
-
-proc isObj(obj: PNimType, subclass: cstring): bool {.compilerRtl, inl.} =
-  proc strstr(s, sub: cstring): cstring {.header: "<string.h>", importc.}
-
-  result = strstr(obj.name, subclass) != nil
-
-proc chckObj(obj: PNimType, subclass: cstring) {.compilerRtl.} =
-  # checks if obj is of type subclass:
-  if not isObj(obj, subclass): sysFatal(ObjectConversionError, "invalid object conversion")
diff --git a/lib/core/seqs.nim b/lib/core/seqs.nim
deleted file mode 100644
index b7f9fb153..000000000
--- a/lib/core/seqs.nim
+++ /dev/null
@@ -1,129 +0,0 @@
-#
-#
-#            Nim's Runtime Library
-#        (c) Copyright 2017 Nim contributors
-#
-#    See the file "copying.txt", included in this
-#    distribution, for details about the copyright.
-#
-
-
-# import typetraits
-# strs already imported allocators for us.
-
-proc supportsCopyMem(t: typedesc): bool {.magic: "TypeTrait".}
-
-## Default seq implementation used by Nim's core.
-type
-  NimSeqPayload[T] = object
-    cap: int
-    allocator: Allocator
-    data: UncheckedArray[T]
-
-  NimSeqV2*[T] = object
-    len: int
-    p: ptr NimSeqPayload[T]
-
-const nimSeqVersion {.core.} = 2
-
-template payloadSize(cap): int = cap * sizeof(T) + sizeof(int) + sizeof(Allocator)
-
-# XXX make code memory safe for overflows in '*'
-
-type
-  PayloadBase = object
-    cap: int
-    allocator: Allocator
-
-proc newSeqPayload(cap, elemSize: int): pointer {.compilerRtl, raises: [].} =
-  # we have to use type erasure here as Nim does not support generic
-  # compilerProcs. Oh well, this will all be inlined anyway.
-  if cap > 0:
-    let allocator = getLocalAllocator()
-    var p = cast[ptr PayloadBase](allocator.alloc(allocator, cap * elemSize + sizeof(int) + sizeof(Allocator)))
-    p.allocator = allocator
-    p.cap = cap
-    result = p
-  else:
-    result = nil
-
-proc prepareSeqAdd(len: int; p: pointer; addlen, elemSize: int): pointer {.
-    compilerRtl, noSideEffect, raises: [].} =
-  {.noSideEffect.}:
-    template `+!`(p: pointer, s: int): pointer =
-      cast[pointer](cast[int](p) +% s)
-
-    const headerSize = sizeof(int) + sizeof(Allocator)
-    if addlen <= 0:
-      result = p
-    elif p == nil:
-      result = newSeqPayload(len+addlen, elemSize)
-    else:
-      # Note: this means we cannot support things that have internal pointers as
-      # they get reallocated here. This needs to be documented clearly.
-      var p = cast[ptr PayloadBase](p)
-      let cap = max(resize(p.cap), len+addlen)
-      if p.allocator == nil:
-        let allocator = getLocalAllocator()
-        var q = cast[ptr PayloadBase](allocator.alloc(allocator,
-          headerSize + elemSize * cap))
-        copyMem(q +! headerSize, p +! headerSize, len * elemSize)
-        q.allocator = allocator
-        q.cap = cap
-        result = q
-      else:
-        let allocator = p.allocator
-        var q = cast[ptr PayloadBase](allocator.realloc(allocator, p,
-          headerSize + elemSize * p.cap,
-          headerSize + elemSize * cap))
-        q.allocator = allocator
-        q.cap = cap
-        result = q
-
-proc shrink*[T](x: var seq[T]; newLen: Natural) =
-  when nimvm:
-    setLen(x, newLen)
-  else:
-    mixin `=destroy`
-    sysAssert newLen <= x.len, "invalid newLen parameter for 'shrink'"
-    when not supportsCopyMem(T):
-      for i in countdown(x.len - 1, newLen):
-        `=destroy`(x[i])
-    # XXX This is wrong for const seqs that were moved into 'x'!
-    cast[ptr NimSeqV2[T]](addr x).len = newLen
-
-proc grow*[T](x: var seq[T]; newLen: Natural; value: T) =
-  let oldLen = x.len
-  if newLen <= oldLen: return
-  var xu = cast[ptr NimSeqV2[T]](addr x)
-  if xu.p == nil or xu.p.cap < newLen:
-    xu.p = cast[typeof(xu.p)](prepareSeqAdd(oldLen, xu.p, newLen - oldLen, sizeof(T)))
-  xu.len = newLen
-  for i in oldLen .. newLen-1:
-    xu.p.data[i] = value
-
-proc add*[T](x: var seq[T]; value: sink T) {.magic: "AppendSeqElem", noSideEffect.} =
-  ## Generic proc for adding a data item `y` to a container `x`.
-  ##
-  ## For containers that have an order, `add` means *append*. New generic
-  ## 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)))
-  xu.len = oldLen+1
-  xu.p.data[oldLen] = value
-
-proc setLen[T](s: var seq[T], newlen: Natural) =
-  {.noSideEffect.}:
-    if newlen < s.len:
-      shrink(s, newlen)
-    else:
-      let oldLen = s.len
-      if newlen <= oldLen: return
-      var xu = cast[ptr NimSeqV2[T]](addr s)
-      if xu.p == nil or xu.p.cap < newlen:
-        xu.p = cast[typeof(xu.p)](prepareSeqAdd(oldLen, xu.p, newlen - oldLen, sizeof(T)))
-      xu.len = newlen
diff --git a/lib/core/strs.nim b/lib/core/strs.nim
deleted file mode 100644
index 3b7a46ff1..000000000
--- a/lib/core/strs.nim
+++ /dev/null
@@ -1,152 +0,0 @@
-#
-#
-#            Nim's Runtime Library
-#        (c) Copyright 2017 Nim contributors
-#
-#    See the file "copying.txt", included in this
-#    distribution, for details about the copyright.
-#
-
-## Default new string implementation used by Nim's core.
-
-import allocators
-
-type
-  NimStrPayload {.core.} = object
-    cap: int
-    allocator: Allocator
-    data: UncheckedArray[char]
-
-  NimStringV2 {.core.} = object
-    len: int
-    p: ptr NimStrPayload ## can be nil if len == 0.
-
-const nimStrVersion {.core.} = 2
-
-template isLiteral(s): bool = s.p == nil or s.p.allocator == nil
-
-template contentSize(cap): int = cap + 1 + sizeof(int) + sizeof(Allocator)
-
-template frees(s) =
-  if not isLiteral(s):
-    s.p.allocator.dealloc(s.p.allocator, s.p, contentSize(s.p.cap))
-
-proc resize(old: int): int {.inline.} =
-  if old <= 0: result = 4
-  elif old < 65536: result = old * 2
-  else: result = old * 3 div 2 # for large arrays * 3/2 is better
-
-proc prepareAdd(s: var NimStringV2; addlen: int) {.compilerRtl.} =
-  if isLiteral(s) and addlen > 0:
-    let oldP = s.p
-    # can't mutate a literal, so we need a fresh copy here:
-    let allocator = getLocalAllocator()
-    s.p = cast[ptr NimStrPayload](allocator.alloc(allocator, contentSize(s.len + addlen)))
-    s.p.allocator = allocator
-    s.p.cap = s.len + addlen
-    if s.len > 0:
-      # we are about to append, so there is no need to copy the \0 terminator:
-      copyMem(unsafeAddr s.p.data[0], unsafeAddr oldP.data[0], s.len)
-  elif s.len + addlen > s.p.cap:
-    let cap = max(s.len + addlen, resize(s.p.cap))
-    s.p = cast[ptr NimStrPayload](s.p.allocator.realloc(s.p.allocator, s.p,
-      oldSize = contentSize(s.p.cap),
-      newSize = contentSize(cap)))
-    s.p.cap = cap
-
-proc nimAddCharV1(s: var NimStringV2; c: char) {.compilerRtl.} =
-  prepareAdd(s, 1)
-  s.p.data[s.len] = c
-  s.p.data[s.len+1] = '\0'
-  inc s.len
-
-proc toNimStr(str: cstring, len: int): NimStringV2 {.compilerproc.} =
-  if len <= 0:
-    result = NimStringV2(len: 0, p: nil)
-  else:
-    let allocator = getLocalAllocator()
-    var p = cast[ptr NimStrPayload](allocator.alloc(allocator, contentSize(len)))
-    p.allocator = allocator
-    p.cap = len
-    if len > 0:
-      # we are about to append, so there is no need to copy the \0 terminator:
-      copyMem(unsafeAddr p.data[0], str, len)
-    result = NimStringV2(len: len, p: p)
-
-proc cstrToNimstr(str: cstring): NimStringV2 {.compilerRtl.} =
-  if str == nil: toNimStr(str, 0)
-  else: toNimStr(str, str.len)
-
-proc nimToCStringConv(s: NimStringV2): cstring {.compilerproc, nonReloadable, inline.} =
-  if s.len == 0: result = cstring""
-  else: result = cstring(unsafeAddr s.p.data)
-
-proc appendString(dest: var NimStringV2; src: NimStringV2) {.compilerproc, inline.} =
-  if src.len > 0:
-    # also copy the \0 terminator:
-    copyMem(unsafeAddr dest.p.data[dest.len], unsafeAddr src.p.data[0], src.len+1)
-    inc dest.len, src.len
-
-proc appendChar(dest: var NimStringV2; c: char) {.compilerproc, inline.} =
-  dest.p.data[dest.len] = c
-  dest.p.data[dest.len+1] = '\0'
-  inc dest.len
-
-proc rawNewString(space: int): NimStringV2 {.compilerproc.} =
-  # this is also 'system.newStringOfCap'.
-  if space <= 0:
-    result = NimStringV2(len: 0, p: nil)
-  else:
-    let allocator = getLocalAllocator()
-    var p = cast[ptr NimStrPayload](allocator.alloc(allocator, contentSize(space)))
-    p.allocator = allocator
-    p.cap = space
-    result = NimStringV2(len: 0, p: p)
-
-proc mnewString(len: int): NimStringV2 {.compilerproc.} =
-  if len <= 0:
-    result = NimStringV2(len: 0, p: nil)
-  else:
-    let allocator = getLocalAllocator()
-    var p = cast[ptr NimStrPayload](allocator.alloc(allocator, contentSize(len)))
-    p.allocator = allocator
-    p.cap = len
-    result = NimStringV2(len: len, p: p)
-
-proc setLengthStrV2(s: var NimStringV2, newLen: int) {.compilerRtl.} =
-  if newLen == 0:
-    frees(s)
-    s.p = nil
-  elif newLen > s.len or isLiteral(s):
-    prepareAdd(s, newLen - s.len)
-  s.len = newLen
-
-proc nimAsgnStrV2(a: var NimStringV2, b: NimStringV2) {.compilerRtl.} =
-  if a.p == b.p: return
-  if isLiteral(b):
-    # we can shallow copy literals:
-    frees(a)
-    a.len = b.len
-    a.p = b.p
-  else:
-    if isLiteral(a) or a.p.cap < b.len:
-      let allocator = if a.p != nil and a.p.allocator != nil: a.p.allocator else: getLocalAllocator()
-      # we have to allocate the 'cap' here, consider
-      # 'let y = newStringOfCap(); var x = y'
-      # on the other hand... These get turned into moves now.
-      frees(a)
-      a.p = cast[ptr NimStrPayload](allocator.alloc(allocator, contentSize(b.len)))
-      a.p.allocator = allocator
-      a.p.cap = b.len
-    a.len = b.len
-    copyMem(unsafeAddr a.p.data[0], unsafeAddr b.p.data[0], b.len+1)
-
-proc nimPrepareStrMutationV2(s: var NimStringV2) {.compilerRtl.} =
-  if s.p != nil and s.p.allocator == nil:
-    let oldP = s.p
-    # can't mutate a literal, so we need a fresh copy here:
-    let allocator = getLocalAllocator()
-    s.p = cast[ptr NimStrPayload](allocator.alloc(allocator, contentSize(s.len)))
-    s.p.allocator = allocator
-    s.p.cap = s.len
-    copyMem(unsafeAddr s.p.data[0], unsafeAddr oldP.data[0], s.len+1)