#
#
# 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 '*'
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])
#[
Keep in mind that C optimizers are bad at detecting the connection
between ``s.p != nil`` and ``s.len != 0`` and that these are intermingled
with user-level code that accesses ``s.len`` only, never ``s.p`` directly.
This means the check for whether ``s.p`` needs to be freed should
be ``s.len == 0`` even though that feels slightly more awkward.
]#
when not defined(nimV2):
proc `=destroy`[T](s: var seq[T]) =
var x = cast[ptr NimSeqV2[T]](addr s)
var p = x.p
if p != nil:
mixin `=destroy`
when not supportsCopyMem(T):
for i in 0..<x.len: `=destroy`(p.data[i])
if p.allocator != nil:
p.allocator.dealloc(p.allocator, p, payloadSize(p.cap))
x.p = nil
x.len = 0
proc `=`[T](x: var seq[T]; y: seq[T]) =
mixin `=destroy`
var a = cast[ptr NimSeqV2[T]](addr x)
var b = cast[ptr NimSeqV2[T]](unsafeAddr y)
if a.p == b.p: return
`=destroy`(x)
a.len = b.len
if b.p != nil:
a.p = cast[type(a.p)](alloc(payloadSize(a.len)))
when supportsCopyMem(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.p.data[i] = b.p.data[i]
proc `=sink`[T](x: var seq[T]; y: seq[T]) =
mixin `=destroy`
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`(x)
a.len = b.len
a.p = b.p
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) =
mixin `=destroy`
sysAssert newLen <= x.len, "invalid newLen parameter for 'shrink'"
when not supportsCopyMem(T):
for i in countdown(x.len - 1, newLen - 1):
`=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:
grow(s, newLen, default(T))
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:
for i in 0..<result.len:
result.data[i] = elems[i]