fixes merge conflicts

1 files changed, 138 insertions, 108 deletions

diff --git a/lib/core/seqs.nim b/lib/core/seqs.nim
index c32cf3690..4dcf6cbbb 100644
--- a/lib/core/seqs.nim
+++ b/lib/core/seqs.nim
@@ -7,133 +7,163 @@
 #    distribution, for details about the copyright.
 #
 
-import allocators, typetraits
+
+import typetraits
+# strs already imported allocators for us.
 
 ## Default seq implementation used by Nim's core.
 type
-  seq*[T] = object
-    len, cap: int
-    data: ptr UncheckedArray[T]
+  NimSeqPayload {.core.}[T] = object
+    cap: int
+    region: Allocator
+    data: UncheckedArray[T]
+
+  NimSeqV2*[T] = object
+    len: int
+    p: ptr NimSeqPayload[T]
+
+const nimSeqVersion {.core.} = 2
 
-template frees(s) = dealloc(s.data, s.cap * sizeof(T))
+template payloadSize(cap): int = cap * sizeof(T) + sizeof(int) + sizeof(Allocator)
 
 # XXX make code memory safe for overflows in '*'
-proc nimSeqLiteral[T](x: openArray[T]): seq[T] {.core.} =
-  seq[T](len: x.len, cap: x.len, data: x)
 
-when defined(nimHasTrace):
-  proc `=trace`[T](s: seq[T]; a: Allocator) =
-    for i in 0 ..< s.len: `=trace`(s.data[i], a)
+when false:
+  # this is currently not part of Nim's type bound operators and so it's
+  # built into the tracing proc generation just like before.
+  proc `=trace`[T](s: NimSeqV2[T]) =
+    for i in 0 ..< s.len: `=trace`(s.data[i])
 
-proc `=destroy`[T](x: var seq[T]) =
-  if x.data != nil:
+proc `=destroy`[T](s: var seq[T]) =
+  var x = cast[ptr NimSeqV2[T]](addr s)
+  var p = x.p
+  if p != nil:
     when not supportsCopyMem(T):
-      for i in 0..<x.len: `=destroy`(x[i])
-    frees(x)
-    x.data = nil
+      for i in 0..<x.len: `=destroy`(p.data[i])
+    p.region.dealloc(p.region, p, payloadSize(p.cap))
+    x.p = nil
     x.len = 0
-    x.cap = 0
 
-proc `=`[T](a: var seq[T]; b: seq[T]) =
-  if a.data == b.data: return
-  if a.data != nil:
-    frees(a)
-    a.data = nil
+proc `=`[T](x: var seq[T]; y: seq[T]) =
+  var a = cast[ptr NimSeqV2[T]](addr x)
+  var b = cast[ptr NimSeqV2[T]](unsafeAddr y)
+
+  if a.p == b.p: return
+  `=destroy`(a)
   a.len = b.len
-  a.cap = b.cap
-  if b.data != nil:
-    a.data = cast[type(a.data)](alloc(a.cap * sizeof(T)))
+  if b.p != nil:
+    a.p = cast[type(a.p)](alloc(payloadSize(a.len)))
     when supportsCopyMem(T):
-      copyMem(a.data, b.data, a.cap * sizeof(T))
+      if a.len > 0:
+        copyMem(unsafeAddr a.p.data[0], unsafeAddr b.p.data[0], a.len * sizeof(T))
     else:
       for i in 0..<a.len:
-        a.data[i] = b.data[i]
+        a.p.data[i] = b.p.data[i]
 
-proc `=sink`[T](a: var seq[T]; b: seq[T]) =
-  if a.data != nil and a.data != b.data:
-    frees(a)
+proc `=sink`[T](x: var seq[T]; y: seq[T]) =
+  var a = cast[ptr NimSeqV2[T]](addr x)
+  var b = cast[ptr NimSeqV2[T]](unsafeAddr y)
+  if a.p != nil and a.p != b.p:
+    `=destroy`(a)
   a.len = b.len
-  a.cap = b.cap
-  a.data = b.data
-
-proc resize[T](s: var seq[T]) =
-  let old = s.cap
-  if old == 0: s.cap = 8
-  else: s.cap = (s.cap * 3) shr 1
-  s.data = cast[type(s.data)](realloc(s.data, old * sizeof(T), s.cap * sizeof(T)))
-
-proc reserveSlot[T](x: var seq[T]): ptr T =
-  if x.len >= x.cap: resize(x)
-  result = addr(x.data[x.len])
-  inc x.len
-
-template add*[T](x: var seq[T]; y: T) =
-  reserveSlot(x)[] = y
-
-proc shrink*[T](x: var seq[T]; newLen: int) =
-  assert newLen <= x.len
-  assert newLen >= 0
+  a.p = b.p
+
+when false:
+  proc incrSeqV3(s: PGenericSeq, typ: PNimType): PGenericSeq {.compilerProc.}
+  proc setLengthSeqV2(s: PGenericSeq, typ: PNimType, newLen: int): PGenericSeq {.
+      compilerRtl.}
+  proc newSeq(typ: PNimType, len: int): pointer {.compilerRtl.}
+
+
+type
+  PayloadBase = object
+    cap: int
+    region: Allocator
+
+proc newSeqPayload(cap, elemSize: int): pointer {.compilerRtl.} =
+  # 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 region = getLocalAllocator()
+    var p = cast[ptr PayloadBase](region.alloc(region, cap * elemSize + sizeof(int) + sizeof(Allocator)))
+    p.region = region
+    p.cap = cap
+    result = p
+  else:
+    result = nil
+
+proc prepareSeqAdd(len: int; p: pointer; addlen, elemSize: int): pointer {.compilerRtl.} =
+  if len+addlen <= len:
+    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 region = if p.region == nil: getLocalAllocator() else: p.region
+    let cap = max(resize(p.cap), len+addlen)
+    var q = cast[ptr PayloadBase](region.realloc(region, p,
+      sizeof(int) + sizeof(Allocator) + elemSize * p.cap,
+      sizeof(int) + sizeof(Allocator) + elemSize * cap))
+    q.region = region
+    q.cap = cap
+    result = q
+
+proc shrink*[T](x: var seq[T]; newLen: Natural) =
+  sysAssert newLen <= x.len, "invalid newLen parameter for 'shrink'"
   when not supportsCopyMem(T):
     for i in countdown(x.len - 1, newLen - 1):
-      `=destroy`(x.data[i])
-  x.len = newLen
-
-proc grow*[T](x: var seq[T]; newLen: int; value: T) =
-  if newLen <= x.len: return
-  assert newLen >= 0
-  if x.cap == 0: x.cap = newLen
-  else: x.cap = max(newLen, (x.cap * 3) shr 1)
-  x.data = cast[type(x.data)](realloc(x.data, x.cap * sizeof(T)))
-  for i in x.len..<newLen:
+      `=destroy`(x[i])
+
+  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)
+
+  xu.p = prepareSeqAdd(oldLen, xu.p, newLen - oldLen, sizeof(T))
+  xu.len = newLen
+  for i in oldLen .. newLen-1:
     x.data[i] = value
-  x.len = newLen
-
-template default[T](t: typedesc[T]): T =
-  var v: T
-  v
-
-proc setLen*[T](x: var seq[T]; newLen: int) {.deprecated.} =
-  if newlen < x.len: shrink(x, newLen)
-  else: grow(x, newLen, default(T))
-
-template `[]`*[T](x: seq[T]; i: Natural): T =
-  assert i < x.len
-  x.data[i]
-
-template `[]=`*[T](x: seq[T]; i: Natural; y: T) =
-  assert i < x.len
-  x.data[i] = y
-
-proc `@`*[T](elems: openArray[T]): seq[T] =
-  result.cap = elems.len
-  result.len = elems.len
-  result.data = cast[type(result.data)](alloc(result.cap * sizeof(T)))
-  when supportsCopyMem(T):
-    copyMem(result.data, unsafeAddr(elems[0]), result.cap * sizeof(T))
+
+proc setLen[T](s: var seq[T], newlen: Natural) =
+  if newlen < s.len:
+    shrink(s, newLen)
   else:
-    for i in 0..<result.len:
-      result.data[i] = elems[i]
-
-proc len*[T](x: seq[T]): int {.inline.} = x.len
-
-proc `$`*[T](x: seq[T]): string =
-  result = "@["
-  var firstElement = true
-  for i in 0..<x.len:
-    let 
-      value = x.data[i]
-    if firstElement:
-      firstElement = false
-    else:
-      result.add(", ")
-
-    when compiles(value.isNil):
-      # this branch should not be necessary
-      if value.isNil:
-        result.add "nil"
-      else:
-        result.addQuoted(value)
+    var v: T # get the default value of 'v'
+    grow(s, newLen, v)
+
+when false:
+  proc resize[T](s: var NimSeqV2[T]) =
+    let old = s.cap
+    if old == 0: s.cap = 8
+    else: s.cap = (s.cap * 3) shr 1
+    s.data = cast[type(s.data)](realloc(s.data, old * sizeof(T), s.cap * sizeof(T)))
+
+  proc reserveSlot[T](x: var NimSeqV2[T]): ptr T =
+    if x.len >= x.cap: resize(x)
+    result = addr(x.data[x.len])
+    inc x.len
+
+  template add*[T](x: var NimSeqV2[T]; y: T) =
+    reserveSlot(x)[] = y
+
+  template `[]`*[T](x: NimSeqV2[T]; i: Natural): T =
+    assert i < x.len
+    x.data[i]
+
+  template `[]=`*[T](x: NimSeqV2[T]; i: Natural; y: T) =
+    assert i < x.len
+    x.data[i] = y
+
+  proc `@`*[T](elems: openArray[T]): NimSeqV2[T] =
+    result.cap = elems.len
+    result.len = elems.len
+    result.data = cast[type(result.data)](alloc(result.cap * sizeof(T)))
+    when supportsCopyMem(T):
+      copyMem(result.data, unsafeAddr(elems[0]), result.cap * sizeof(T))
     else:
-      result.addQuoted(value)
-
-  result.add("]")
+      for i in 0..<result.len:
+        result.data[i] = elems[i]