1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
#
#
# 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 allocateds for us.
proc supportsCopyMem(t: typedesc): bool {.magic: "TypeTrait".}
## Default seq implementation used by Nim's core.
type
NimSeqPayloadBase = object
cap: int
NimSeqPayload[T] = object
cap: int
data: UncheckedArray[T]
NimSeqV2*[T] = object # \
# if you change this implementation, also change seqs_v2_reimpl.nim!
len: int
p: ptr NimSeqPayload[T]
const nimSeqVersion {.core.} = 2
# XXX make code memory safe for overflows in '*'
proc newSeqPayload(cap, elemSize, elemAlign: 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:
when compileOption("threads"):
var p = cast[ptr NimSeqPayloadBase](allocShared0(align(sizeof(NimSeqPayloadBase), elemAlign) + cap * elemSize))
else:
var p = cast[ptr NimSeqPayloadBase](alloc0(align(sizeof(NimSeqPayloadBase), elemAlign) + cap * elemSize))
p.cap = cap
result = p
else:
result = nil
template `+!`(p: pointer, s: int): pointer =
cast[pointer](cast[int](p) +% s)
template `-!`(p: pointer, s: int): pointer =
cast[pointer](cast[int](p) -% s)
proc prepareSeqAdd(len: int; p: pointer; addlen, elemSize, elemAlign: int): pointer {.
noSideEffect, raises: [], compilerRtl.} =
{.noSideEffect.}:
let headerSize = align(sizeof(NimSeqPayloadBase), elemAlign)
if addlen <= 0:
result = p
elif p == nil:
result = newSeqPayload(len+addlen, elemSize, elemAlign)
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 NimSeqPayloadBase](p)
let oldCap = p.cap and not strlitFlag
let newCap = max(resize(oldCap), len+addlen)
if (p.cap and strlitFlag) == strlitFlag:
when compileOption("threads"):
var q = cast[ptr NimSeqPayloadBase](allocShared0(headerSize + elemSize * newCap))
else:
var q = cast[ptr NimSeqPayloadBase](alloc0(headerSize + elemSize * newCap))
copyMem(q +! headerSize, p +! headerSize, len * elemSize)
q.cap = newCap
result = q
else:
let oldSize = headerSize + elemSize * oldCap
let newSize = headerSize + elemSize * newCap
when compileOption("threads"):
var q = cast[ptr NimSeqPayloadBase](reallocShared0(p, oldSize, newSize))
else:
var q = cast[ptr NimSeqPayloadBase](realloc0(p, oldSize, newSize))
q.cap = newCap
result = q
proc shrink*[T](x: var seq[T]; newLen: Natural) =
when nimvm:
setLen(x, newLen)
else:
#sysAssert newLen <= x.len, "invalid newLen parameter for 'shrink'"
when not supportsCopyMem(T):
for i in countdown(x.len - 1, newLen):
reset 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
#sysAssert newLen >= x.len, "invalid newLen parameter for 'grow'"
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), alignof(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, nodestroy.} =
## 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), alignof(T)))
xu.len = oldLen+1
# .nodestroy means `xu.p.data[oldLen] = value` is compiled into a
# copyMem(). This is fine as know by construction that
# in `xu.p.data[oldLen]` there is nothing to destroy.
# We also save the `wasMoved + destroy` pair for the sink parameter.
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), alignof(T)))
xu.len = newlen
|