diff options
Diffstat (limited to 'lib/system/sysstr.nim')
| -rw-r--r--[-rwxr-xr-x] | lib/system/sysstr.nim | 407 |
1 files changed, 237 insertions, 170 deletions
diff --git a/lib/system/sysstr.nim b/lib/system/sysstr.nim index d62a987ff..3621c4960 100755..100644 --- a/lib/system/sysstr.nim +++ b/lib/system/sysstr.nim @@ -1,6 +1,6 @@ # # -# Nimrod's Runtime Library +# Nim's Runtime Library # (c) Copyright 2012 Andreas Rumpf # # See the file "copying.txt", included in this @@ -15,111 +15,154 @@ # we don't use refcounts because that's a behaviour # the programmer may not want + +proc dataPointer(a: PGenericSeq, elemAlign: int): pointer = + cast[pointer](cast[int](a) +% align(GenericSeqSize, elemAlign)) + +proc dataPointer(a: PGenericSeq, elemAlign, elemSize, index: int): pointer = + cast[pointer](cast[int](a) +% align(GenericSeqSize, elemAlign) +% (index*%elemSize)) + 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 cmpStrings(a, b: NimString): int {.inline, compilerProc.} = - if a == b: return 0 - if a == nil: return -1 - if b == nil: return 1 - return c_strcmp(a.data, b.data) +when declared(allocAtomic): + template allocStr(size: untyped): untyped = + cast[NimString](allocAtomic(size)) -proc eqStrings(a, b: NimString): bool {.inline, compilerProc.} = - if a == b: return true - if a == nil or b == nil: return false - return a.len == b.len and - c_memcmp(a.data, b.data, a.len * sizeof(char)) == 0'i32 + template allocStrNoInit(size: untyped): untyped = + cast[NimString](boehmAllocAtomic(size)) +elif defined(gcRegions): + template allocStr(size: untyped): untyped = + cast[NimString](newStr(addr(strDesc), size, true)) + + template allocStrNoInit(size: untyped): untyped = + cast[NimString](newStr(addr(strDesc), size, false)) -when defined(allocAtomic): - template allocStr(size: expr): expr = - cast[NimString](allocAtomic(size)) else: - template allocStr(size: expr): expr = + template allocStr(size: untyped): untyped = cast[NimString](newObj(addr(strDesc), size)) -proc rawNewString(space: int): NimString {.compilerProc.} = - var s = space - if s < 8: s = 7 - result = allocStr(sizeof(TGenericSeq) + s + 1) + template allocStrNoInit(size: untyped): untyped = + cast[NimString](newObjNoInit(addr(strDesc), size)) + +proc rawNewStringNoInit(space: int): NimString = + let s = max(space, 7) + result = allocStrNoInit(sizeof(TGenericSeq) + s + 1) result.reserved = s + when defined(gogc): + result.elemSize = 1 + +proc rawNewString(space: int): NimString {.compilerproc.} = + result = rawNewStringNoInit(space) + result.len = 0 + result.data[0] = '\0' -proc mnewString(len: int): NimString {.compilerProc.} = - result = rawNewString(len) +proc mnewString(len: int): NimString {.compilerproc.} = + result = rawNewStringNoInit(len) result.len = len + zeroMem(addr result.data[0], len + 1) -proc copyStrLast(s: NimString, start, last: int): NimString {.compilerProc.} = - var start = max(start, 0) - var len = min(last, s.len-1) - start + 1 - if len > 0: - result = rawNewString(len) - result.len = len - c_memcpy(result.data, addr(s.data[start]), len * sizeof(Char)) - #result.data[len] = '\0' - else: - result = rawNewString(len) +proc copyStrLast(s: NimString, start, last: int): NimString {.compilerproc.} = + # This is not used by most recent versions of the compiler anymore, but + # required for bootstrapping purposes. + let start = max(start, 0) + if s == nil: return nil + let len = min(last, s.len-1) - start + 1 + result = rawNewStringNoInit(len) + result.len = len + copyMem(addr(result.data), addr(s.data[start]), len) + result.data[len] = '\0' -proc copyStr(s: NimString, start: int): NimString {.compilerProc.} = +proc copyStr(s: NimString, start: int): NimString {.compilerproc.} = + # This is not used by most recent versions of the compiler anymore, but + # required for bootstrapping purposes. + if s == nil: return nil result = copyStrLast(s, start, s.len-1) -proc toNimStr(str: CString, len: int): NimString {.compilerProc.} = - result = rawNewString(len) +proc nimToCStringConv(s: NimString): cstring {.compilerproc, nonReloadable, inline.} = + if s == nil or s.len == 0: result = cstring"" + else: result = cast[cstring](addr s.data) + +proc toNimStr(str: cstring, len: int): NimString {.compilerproc.} = + result = rawNewStringNoInit(len) result.len = len - c_memcpy(result.data, str, (len+1) * sizeof(Char)) - #result.data[len] = '\0' # readline relies on this! + copyMem(addr(result.data), str, len) + result.data[len] = '\0' -proc cstrToNimstr(str: CString): NimString {.compilerRtl.} = - result = toNimstr(str, c_strlen(str)) +proc cstrToNimstr(str: cstring): NimString {.compilerRtl.} = + if str == nil: NimString(nil) + else: toNimStr(str, str.len) proc copyString(src: NimString): NimString {.compilerRtl.} = if src != nil: if (src.reserved and seqShallowFlag) != 0: result = src else: - result = rawNewString(src.space) + result = rawNewStringNoInit(src.len) result.len = src.len - c_memcpy(result.data, src.data, (src.len + 1) * sizeof(Char)) + copyMem(addr(result.data), addr(src.data), src.len + 1) + sysAssert((seqShallowFlag and result.reserved) == 0, "copyString") + when defined(nimShallowStrings): + if (src.reserved and strlitFlag) != 0: + result.reserved = (result.reserved and not strlitFlag) or seqShallowFlag + +proc newOwnedString(src: NimString; n: int): NimString = + result = rawNewStringNoInit(n) + result.len = n + copyMem(addr(result.data), addr(src.data), n) + result.data[n] = '\0' proc copyStringRC1(src: NimString): NimString {.compilerRtl.} = if src != nil: - var s = src.space - if s < 8: s = 7 - when defined(newObjRC1): - result = cast[NimString](newObjRC1(addr(strDesc), sizeof(TGenericSeq) + - s+1)) + if (src.reserved and seqShallowFlag) != 0: + result = src + when declared(incRef): + incRef(usrToCell(result)) else: - result = allocStr(sizeof(TGenericSeq) + s + 1) - result.reserved = s + when declared(newObjRC1) and not defined(gcRegions): + var s = src.len + if s < 7: s = 7 + result = cast[NimString](newObjRC1(addr(strDesc), sizeof(TGenericSeq) + + s+1)) + result.reserved = s + when defined(gogc): + result.elemSize = 1 + else: + result = rawNewStringNoInit(src.len) + result.len = src.len + copyMem(addr(result.data), addr(src.data), src.len + 1) + sysAssert((seqShallowFlag and result.reserved) == 0, "copyStringRC1") + when defined(nimShallowStrings): + if (src.reserved and strlitFlag) != 0: + result.reserved = (result.reserved and not strlitFlag) or seqShallowFlag + +proc copyDeepString(src: NimString): NimString {.inline.} = + if src != nil: + result = rawNewStringNoInit(src.len) result.len = src.len - c_memcpy(result.data, src.data, src.len + 1) - -proc hashString(s: string): int {.compilerproc.} = - # the compiler needs exactly the same hash function! - # this used to be used for efficient generation of string case statements - var h = 0 - for i in 0..Len(s)-1: - h = h +% Ord(s[i]) - h = h +% h shl 10 - h = h xor (h shr 6) - h = h +% h shl 3 - h = h xor (h shr 11) - h = h +% h shl 15 - result = h + copyMem(addr(result.data), addr(src.data), src.len + 1) proc addChar(s: NimString, c: char): NimString = # is compilerproc! - result = s - if result.len >= result.space: - result.reserved = resize(result.space) - result = cast[NimString](growObj(result, - sizeof(TGenericSeq) + (result.reserved+1) * sizeof(char))) + if s == nil: + result = rawNewStringNoInit(1) + result.len = 0 + else: + result = s + if result.len >= result.space: + let r = resize(result.space) + result = rawNewStringNoInit(r) + result.len = s.len + copyMem(addr result.data[0], unsafeAddr(s.data[0]), s.len+1) + result.reserved = r result.data[result.len] = c result.data[result.len+1] = '\0' inc(result.len) # These routines should be used like following: -# <Nimrod code> +# <Nim code> # s &= "Hello " & name & ", how do you feel?" # # <generated C code> @@ -130,7 +173,7 @@ proc addChar(s: NimString, c: char): NimString = # appendString(s, strLit3); # } # -# <Nimrod code> +# <Nim code> # s = "Hello " & name & ", how do you feel?" # # <generated C code> @@ -143,26 +186,31 @@ proc addChar(s: NimString, c: char): NimString = # s = tmp0; # } # -# <Nimrod code> +# <Nim code> # s = "" # # <generated C code> # s = rawNewString(0); proc resizeString(dest: NimString, addlen: int): NimString {.compilerRtl.} = - if dest.len + addLen <= dest.space: + if dest == nil: + result = rawNewString(addlen) + elif dest.len + addlen <= dest.space: result = dest else: # slow path: - var sp = max(resize(dest.space), dest.len + addLen) - result = cast[NimString](growObj(dest, sizeof(TGenericSeq) + sp + 1)) + let sp = max(resize(dest.space), dest.len + addlen) + result = rawNewStringNoInit(sp) + result.len = dest.len + copyMem(addr result.data[0], unsafeAddr(dest.data[0]), dest.len+1) result.reserved = sp #result = rawNewString(sp) - #copyMem(result, dest, dest.len * sizeof(char) + sizeof(TGenericSeq)) + #copyMem(result, dest, dest.len + sizeof(TGenericSeq)) # DO NOT UPDATE LEN YET: dest.len = newLen proc appendString(dest, src: NimString) {.compilerproc, inline.} = - c_memcpy(addr(dest.data[dest.len]), src.data, src.len + 1) - inc(dest.len, src.len) + if src != nil: + copyMem(addr(dest.data[dest.len]), addr(src.data), src.len + 1) + inc(dest.len, src.len) proc appendChar(dest: NimString, c: char) {.compilerproc, inline.} = dest.data[dest.len] = c @@ -170,17 +218,27 @@ proc appendChar(dest: NimString, c: char) {.compilerproc, inline.} = inc(dest.len) proc setLengthStr(s: NimString, newLen: int): NimString {.compilerRtl.} = - var n = max(newLen, 0) - if n <= s.space: + let n = max(newLen, 0) + if s == nil: + if n == 0: + return s + else: + result = mnewString(n) + elif n <= s.space: result = s else: - result = resizeString(s, n) + let sp = max(resize(s.space), n) + result = rawNewStringNoInit(sp) + result.len = s.len + copyMem(addr result.data[0], unsafeAddr(s.data[0]), s.len) + zeroMem(addr result.data[s.len], n - s.len) + result.reserved = sp result.len = n result.data[n] = '\0' # ----------------- sequences ---------------------------------------------- -proc incrSeq(seq: PGenericSeq, elemSize: int): PGenericSeq {.compilerProc.} = +proc incrSeq(seq: PGenericSeq, elemSize, elemAlign: int): PGenericSeq {.compilerproc.} = # increments the length by one: # this is needed for supporting ``add``; # @@ -189,108 +247,117 @@ proc incrSeq(seq: PGenericSeq, elemSize: int): PGenericSeq {.compilerProc.} = # seq[seq->len-1] = x; result = seq if result.len >= result.space: - result.reserved = resize(result.space) - result = cast[PGenericSeq](growObj(result, elemSize * result.reserved + - GenericSeqSize)) + let r = resize(result.space) + result = cast[PGenericSeq](growObj(result, align(GenericSeqSize, elemAlign) + elemSize * r)) + result.reserved = r inc(result.len) -proc setLengthSeq(seq: PGenericSeq, elemSize, newLen: int): PGenericSeq {. - compilerRtl.} = +proc incrSeqV2(seq: PGenericSeq, elemSize, elemAlign: int): PGenericSeq {.compilerproc.} = + # incrSeq version 2 + result = seq + if result.len >= result.space: + let r = resize(result.space) + result = cast[PGenericSeq](growObj(result, align(GenericSeqSize, elemAlign) + elemSize * r)) + result.reserved = r + +proc incrSeqV3(s: PGenericSeq, typ: PNimType): PGenericSeq {.compilerproc.} = + if s == nil: + result = cast[PGenericSeq](newSeq(typ, 1)) + result.len = 0 + else: + result = s + if result.len >= result.space: + let r = resize(result.space) + result = cast[PGenericSeq](newSeq(typ, r)) + result.len = s.len + copyMem(dataPointer(result, typ.base.align), dataPointer(s, typ.base.align), s.len * typ.base.size) + # since we steal the content from 's', it's crucial to set s's len to 0. + s.len = 0 + +proc setLengthSeq(seq: PGenericSeq, elemSize, elemAlign, newLen: int): PGenericSeq {. + compilerRtl, inl.} = result = seq if result.space < newLen: - result.reserved = max(resize(result.space), newLen) - result = cast[PGenericSeq](growObj(result, elemSize * result.reserved + - GenericSeqSize)) + let r = max(resize(result.space), newLen) + result = cast[PGenericSeq](growObj(result, align(GenericSeqSize, elemAlign) + elemSize * r)) + result.reserved = r elif newLen < result.len: # we need to decref here, otherwise the GC leaks! - when not defined(boehmGC) and not defined(nogc) and - not defined(gcMarkAndSweep): - when compileOption("gc", "v2"): + when not defined(boehmGC) and not defined(nogc) and + not defined(gcMarkAndSweep) and not defined(gogc) and + not defined(gcRegions): + if ntfNoRefs notin extGetCellType(result).base.flags: for i in newLen..result.len-1: - let len0 = gch.tempStack.len - forAllChildrenAux(cast[pointer](cast[TAddress](result) +% - GenericSeqSize +% (i*%elemSize)), - extGetCellType(result).base, waPush) - let len1 = gch.tempStack.len - for i in len0 .. <len1: - doDecRef(gch.tempStack.d[i], LocalHeap, MaybeCyclic) - gch.tempStack.len = len0 - else: - for i in newLen..result.len-1: - forAllChildrenAux(cast[pointer](cast[TAddress](result) +% - GenericSeqSize +% (i*%elemSize)), + forAllChildrenAux(dataPointer(result, elemAlign, elemSize, i), extGetCellType(result).base, waZctDecRef) - + # XXX: zeroing out the memory can still result in crashes if a wiped-out - # cell is aliased by another pointer (ie proc paramter or a let variable). - # This is a tought problem, because even if we don't zeroMem here, in the - # presense of user defined destructors, the user will expect the cell to be - # "destroyed" thus creating the same problem. We can destoy the cell in the + # cell is aliased by another pointer (ie proc parameter or a let variable). + # This is a tough problem, because even if we don't zeroMem here, in the + # presence of user defined destructors, the user will expect the cell to be + # "destroyed" thus creating the same problem. We can destroy the cell in the # finalizer of the sequence, but this makes destruction non-deterministic. - zeroMem(cast[pointer](cast[TAddress](result) +% GenericSeqSize +% - (newLen*%elemSize)), (result.len-%newLen) *% elemSize) + zeroMem(dataPointer(result, elemAlign, elemSize, newLen), (result.len-%newLen) *% elemSize) result.len = newLen -# --------------- other string routines ---------------------------------- -proc nimIntToStr(x: int): string {.compilerRtl.} = - result = newString(sizeof(x)*4) - var i = 0 - var y = x - while True: - var d = y div 10 - result[i] = chr(abs(int(y - d*10)) + ord('0')) - inc(i) - y = d - if y == 0: break - if x < 0: - result[i] = '-' - inc(i) - setLen(result, i) - # mirror the string: - for j in 0..i div 2 - 1: - swap(result[j], result[i-j-1]) - -proc nimFloatToStr(x: float): string {.compilerproc.} = - var buf: array [0..59, char] - c_sprintf(buf, "%#.16e", x) - return $buf - -proc nimInt64ToStr(x: int64): string {.compilerRtl.} = - result = newString(sizeof(x)*4) - var i = 0 - var y = x - while True: - var d = y div 10 - result[i] = chr(abs(int(y - d*10)) + ord('0')) - inc(i) - y = d - if y == 0: break - if x < 0: - result[i] = '-' - inc(i) - setLen(result, i) - # mirror the string: - for j in 0..i div 2 - 1: - swap(result[j], result[i-j-1]) - -proc nimBoolToStr(x: bool): string {.compilerRtl.} = - return if x: "true" else: "false" - -proc nimCharToStr(x: char): string {.compilerRtl.} = - result = newString(1) - result[0] = x - -proc binaryStrSearch(x: openarray[string], y: string): int {.compilerproc.} = - var - a = 0 - b = len(x) - while a < b: - var mid = (a + b) div 2 - if x[mid] < y: - a = mid + 1 +proc setLengthSeqV2(s: PGenericSeq, typ: PNimType, newLen: int): PGenericSeq {. + compilerRtl.} = + sysAssert typ.kind == tySequence, "setLengthSeqV2: type is not a seq" + if s == nil: + if newLen == 0: + result = s else: - b = mid - if a < len(x) and x[a] == y: - result = a + result = cast[PGenericSeq](newSeq(typ, newLen)) else: - result = -1 + let elemSize = typ.base.size + let elemAlign = typ.base.align + if s.space < newLen: + let r = max(resize(s.space), newLen) + result = cast[PGenericSeq](newSeq(typ, r)) + copyMem(dataPointer(result, elemAlign), dataPointer(s, elemAlign), s.len * elemSize) + # since we steal the content from 's', it's crucial to set s's len to 0. + s.len = 0 + elif newLen < s.len: + result = s + # we need to decref here, otherwise the GC leaks! + when not defined(boehmGC) and not defined(nogc) and + not defined(gcMarkAndSweep) and not defined(gogc) and + not defined(gcRegions): + if ntfNoRefs notin typ.base.flags: + for i in newLen..result.len-1: + forAllChildrenAux(dataPointer(result, elemAlign, elemSize, i), + extGetCellType(result).base, waZctDecRef) + + # XXX: zeroing out the memory can still result in crashes if a wiped-out + # cell is aliased by another pointer (ie proc parameter or a let variable). + # This is a tough problem, because even if we don't zeroMem here, in the + # presence of user defined destructors, the user will expect the cell to be + # "destroyed" thus creating the same problem. We can destroy the cell in the + # finalizer of the sequence, but this makes destruction non-deterministic. + zeroMem(dataPointer(result, elemAlign, elemSize, newLen), (result.len-%newLen) *% elemSize) + else: + result = s + zeroMem(dataPointer(result, elemAlign, elemSize, result.len), (newLen-%result.len) *% elemSize) + result.len = newLen + +func capacity*(self: string): int {.inline.} = + ## Returns the current capacity of the string. + # See https://github.com/nim-lang/RFCs/issues/460 + runnableExamples: + var str = newStringOfCap(cap = 42) + str.add "Nim" + assert str.capacity == 42 + + let str = cast[NimString](self) + result = if str != nil: str.space else: 0 + +func capacity*[T](self: seq[T]): int {.inline.} = + ## Returns the current capacity of the seq. + # See https://github.com/nim-lang/RFCs/issues/460 + runnableExamples: + var lst = newSeqOfCap[string](cap = 42) + lst.add "Nim" + assert lst.capacity == 42 + + let sek = cast[PGenericSeq](self) + result = if sek != nil: sek.space else: 0 |