copying_gc.nim

type
  PtrTable = ptr object
    counter, max: int
    data: array[0xff_ffff, (pointer, pointer)]

template hashPtr(key: pointer): int = cast[int](key) shr 8
template allocPtrTable: untyped =
  cast[PtrTable](alloc0(sizeof(int)*2 + sizeof(pointer)*2*cap))

proc rehash(t: PtrTable): PtrTable =
  let cap = (t.max+1) * 2
  result = allocPtrTable()
  result.counter = t.counter
  result.max = cap-1
  for i in 0..t.max:
    let k = t.data[i][0]
    if k != nil:
      var h = hashPtr(k)
      while result.data[h and result.max][0] != nil: inc h
      result.data[h and result.max] = t.data[i]
  dealloc t

proc initPtrTable(): PtrTable =
  const cap = 32
  result = allocPtrTable()
  result.counter = 0
  result.max = cap-1

template deinit(t: PtrTable) = dealloc(t)

proc get(t: PtrTable; key: pointer): pointer =
  var h = hashPtr(key)
  while true:
    let k = t.data[h and t.max][0]
    if k == nil: break
    if k == key:
      return t.data[h and t.max][1]
    inc h

proc put(t: var PtrTable; key, val: pointer) =
  if (t.max+1) * 2 < t.counter * 3: t = rehash(t)
  var h = hashPtr(key)
  while t.data[h and t.max][0] != nil: inc h
  t.data[h and t.max] = (key, val)
  inc t.counter


type
  GcCellIter = proc (self: ptr GcCell; prevOffset: int): int {.nimcall.}
  GcCell {.inheritable.} = object
    iter: GcCellIter

type
  Node = object of GcCell
    left, right: ptr Node
    data: int

proc render(a: ptr Node) =
  stdout.write "("
  if a.left != nil: render(a.left)
  if a.left == nil and a.right == nil:
    stdout.write a.data
  if a.right != nil: render(a.right)
  stdout.write ")"

const
  HeapSize = 1024 * 1024

# But stuff can also be on the stack in arrays of tuples etc, so
# we push addresses of these stack slots to our shadow stack.
# Simpler code.
var
  stackRoots: array[50_000, ptr ptr GcCell]
  stackPtr: int

  fromSpace = system.alloc(HeapSize)
  toSpace = system.alloc(HeapSize)
  fs, ts: int

template `+!`(x: typed; y: int): untyped = cast[typeof(x)](cast[int](x) +% y)

proc allocForwarding(x: ptr GcCell): ptr GcCell =
  let size = x.iter(x, -1)
  assert size == 40
  assert ts + size < HeapSize
  result = cast[ptr GcCell](toSpace +! ts)
  inc ts, size
  copyMem(result, x, size) # copy includes the object header

proc pushRoot(root: ptr ptr GcCell) =
  stackRoots[stackPtr] = root
  inc stackPtr

iterator children(x: ptr GcCell): ptr ptr GcCell =
  var offset = 0
  while true:
    offset = x.iter(x, offset)
    if offset < 0: break
    yield cast[ptr ptr GcCell](cast[uint](x) + uint(offset))

var copyOps = 0

proc dcopy(tab: var PtrTable; x: ptr GcCell): ptr GcCell =
  if x == nil: return nil
  result = cast[ptr GcCell](tab.get(x))
  if result == nil:
    result = allocForwarding(x)
    inc copyOps
    tab.put(x, result)
    for child in children(result):
      # Note: this nil check cannot be moved into pushRoot!
      if child[] != nil:
        pushRoot(child)
        #child[] = dcopy(tab, child[])

proc collect() =
  var tab = initPtrTable()
  assert ts == 0
  # first trace the roots, ensure these are not popped off the stack:
  let rootsWatermark = stackPtr
  for i in 0 ..< rootsWatermark:
    let x = stackRoots[i]
    x[] = dcopy(tab, x[])
  while stackPtr > rootsWatermark:
    let x = stackRoots[stackPtr-1]
    dec stackPtr
    x[] = dcopy(tab, x[])
  swap(fromSpace, toSpace)
  fs = ts
  echo "FS is now ", fs
  ts = 0
  deinit tab


proc gcAlloc0(size: int; iter: GcCellIter): ptr GcCell =
  #if fs + size >= HeapSize:
  #  collect()
  assert fs + size < HeapSize
  result = cast[ptr GcCell](fromSpace +! fs)
  inc fs, size
  zeroMem(result, size)
  result.iter = iter

# --------------- user space ---------------------------------

proc describeNode(x: ptr GcCell; prevOffset: int): int =
  let x = cast[ptr Node](x)
  case prevOffset
  of -1:
    result = sizeof(Node)
  of 0:
    result = offsetof(x, left)
  of offsetof(x, left):
    result = offsetof(x, right)
  else:
    result = -1 # signal we're at the end

proc newNode(data: int): ptr Node =
  result = cast[ptr Node](gcAlloc0(sizeof(Node), describeNode))
  result.data = data
  result.left = nil
  result.right = nil

proc append(a, b: ptr Node; id: int): ptr Node =
  result = newNode(id)
  result.left = a
  result.right = b

proc test =
  var x = [1, 2, 3, 4, 5, 6]

  var root: ptr Node
  let oldStack = stackPtr
  pushRoot(cast[ptr ptr GcCell](addr root))

  for i in 0..5:
    root = append(newNode(i), root, 100+i)
  render(root)
  echo "phase 0"
  collect()

  render(root)
  echo "phase 1"
  collect()

  render(root)
  echo "phase 2"

  var rootB: ptr Node
  pushRoot(cast[ptr ptr GcCell](addr rootB))

  for i in 0..100:
    rootB = append(rootB, newNode(i), 100+i)
  render(root)
  echo "phase 3"
  collect()
  render(rootB)
  echo "phase 4 "

  stackPtr = oldStack

test()