From e597db83b75e57535321e7407ede9835c298584d Mon Sep 17 00:00:00 2001 From: Jjp137 Date: Tue, 23 Apr 2019 00:37:21 -0700 Subject: tables: fix link (#11090) [ci skip] --- lib/pure/collections/tables.nim | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/pure/collections') diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index c6d5cc9e2..2da2baa48 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -19,7 +19,7 @@ ## For consistency with every other data type in Nim these have **value** ## semantics, this means that ``=`` performs a copy of the hash table. ## -## For `ref semantics`_ +## For `ref semantics`_ ## use their ``Ref`` variants: `TableRef<#TableRef>`_, ## `OrderedTableRef<#OrderedTableRef>`_, and `CountTableRef<#CountTableRef>`_. ## -- cgit 1.4.1-2-gfad0 From 3647c03cadfce2ccaec136590a8acd8a736d0bb0 Mon Sep 17 00:00:00 2001 From: cooldome Date: Sat, 27 Apr 2019 12:41:08 +0100 Subject: reimplement_pr_10974 (#11130) --- changelog.md | 3 +++ lib/pure/collections/sequtils.nim | 16 ++++++++++++++++ 2 files changed, 19 insertions(+) (limited to 'lib/pure/collections') diff --git a/changelog.md b/changelog.md index 7bebfc0e5..accea7d81 100644 --- a/changelog.md +++ b/changelog.md @@ -158,6 +158,9 @@ proc enumToString*(enums: openArray[enum]): string = - Added `system.default`. +- Added `sequtils.items` for closure iterators, allows closure iterators + to be used by the the mapIt, filterIt, allIt, anyIt, etc. + ### Library changes diff --git a/lib/pure/collections/sequtils.nim b/lib/pure/collections/sequtils.nim index 253340379..e39c1fb80 100644 --- a/lib/pure/collections/sequtils.nim +++ b/lib/pure/collections/sequtils.nim @@ -949,6 +949,14 @@ macro mapLiterals*(constructor, op: untyped; ## works for nested tuples of arrays of sets etc. result = mapLitsImpl(constructor, op, nested.boolVal) +iterator items*[T](xs: iterator: T): T = + ## iterates over each element yielded by a closure iterator. This may + ## not seem particularly useful on its own, but this allows closure + ## iterators to be used by the the mapIt, filterIt, allIt, anyIt, etc. + ## templates. + for x in xs(): + yield x + when isMainModule: import strutils from algorithm import sorted @@ -1382,5 +1390,13 @@ when isMainModule: doAssert outp == @[@["a", "b"], @["c", "d"]] + block: + proc iter(len: int): auto = + result = iterator(): int = + for i in 0.. Date: Mon, 29 Apr 2019 08:13:53 +0200 Subject: Initialized collections (#11094) * tables: initialized by default * sets: initialized by default * DRY: extract shared functionality * add a changelog entry * fix errors * don't test include files * make it work for sharedtables * fix discovered bugs * add exhaustive tests --- changelog.md | 10 + lib/pure/collections/hashcommon.nim | 68 +++++ lib/pure/collections/setimpl.nim | 153 +++++++++++ lib/pure/collections/sets.nim | 473 ++++++++++++---------------------- lib/pure/collections/sharedtables.nim | 10 +- lib/pure/collections/tableimpl.nim | 111 ++++---- lib/pure/collections/tables.nim | 259 +++++++++++++++---- testament/tester.nim | 2 + 8 files changed, 662 insertions(+), 424 deletions(-) create mode 100644 lib/pure/collections/hashcommon.nim create mode 100644 lib/pure/collections/setimpl.nim (limited to 'lib/pure/collections') diff --git a/changelog.md b/changelog.md index accea7d81..adc35a079 100644 --- a/changelog.md +++ b/changelog.md @@ -97,6 +97,7 @@ - Custom types that should be supported by `strformat` (&) now need an explicit overload of `formatValue`. + #### Breaking changes in the compiler - The compiler now implements the "generic symbol prepass" for `when` statements @@ -113,6 +114,7 @@ proc enumToString*(enums: openArray[enum]): string = ``` - ``discard x`` is now illegal when `x` is a function symbol. + - Implicit imports via ``--import: module`` in a config file are now restricted to the main package. @@ -188,6 +190,7 @@ proc enumToString*(enums: openArray[enum]): string = differently. - `securehash` is moved to `lib/deprecated` + - The switch ``-d:useWinAnsi`` is not supported anymore. @@ -211,14 +214,19 @@ proc enumToString*(enums: openArray[enum]): string = it's more recognizable and allows tools like github to recognize it as Nim, see [#9647](https://github.com/nim-lang/Nim/issues/9647). The previous extension will continue to work. + - Pragma syntax is now consistent. Previous syntax where type pragmas did not follow the type name is now deprecated. Also pragma before generic parameter list is deprecated to be consistent with how pragmas are used with a proc. See [#8514](https://github.com/nim-lang/Nim/issues/8514) and [#1872](https://github.com/nim-lang/Nim/issues/1872) for further details. +- Hash sets and tables are initialized by default. The explicit `initHashSet`, + `initTable`, etc. are not needed anymore. + ### Tool changes + - `jsondoc` now include a `moduleDescription` field with the module description. `jsondoc0` shows comments as it's own objects as shown in the documentation. @@ -227,6 +235,7 @@ proc enumToString*(enums: openArray[enum]): string = ### Compiler changes + - The deprecated `fmod` proc is now unavailable on the VM'. - A new `--outdir` option was added. - The compiled JavaScript file for the project produced by executing `nim js` @@ -235,4 +244,5 @@ proc enumToString*(enums: openArray[enum]): string = The compiler also provides a new more flexible API for handling the hot code reloading events in the code. + ### Bugfixes diff --git a/lib/pure/collections/hashcommon.nim b/lib/pure/collections/hashcommon.nim new file mode 100644 index 000000000..bbc6d401d --- /dev/null +++ b/lib/pure/collections/hashcommon.nim @@ -0,0 +1,68 @@ +# +# +# Nim's Runtime Library +# (c) Copyright 2019 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +# An ``include`` file which contains common code for +# hash sets and tables. + +const + growthFactor = 2 + +when not defined(nimHasDefault): + template default[T](t: typedesc[T]): T = + var v: T + v + +# hcode for real keys cannot be zero. hcode==0 signifies an empty slot. These +# two procs retain clarity of that encoding without the space cost of an enum. +proc isEmpty(hcode: Hash): bool {.inline.} = + result = hcode == 0 + +proc isFilled(hcode: Hash): bool {.inline.} = + result = hcode != 0 + +proc nextTry(h, maxHash: Hash): Hash {.inline.} = + result = (h + 1) and maxHash + +proc mustRehash(length, counter: int): bool {.inline.} = + assert(length > counter) + result = (length * 2 < counter * 3) or (length - counter < 4) + +template rawGetKnownHCImpl() {.dirty.} = + if t.dataLen == 0: + return -1 + var h: Hash = hc and maxHash(t) # start with real hash value + while isFilled(t.data[h].hcode): + # Compare hc THEN key with boolean short circuit. This makes the common case + # zero ==key's for missing (e.g.inserts) and exactly one ==key for present. + # It does slow down succeeding lookups by one extra Hash cmp&and..usually + # just a few clock cycles, generally worth it for any non-integer-like A. + if t.data[h].hcode == hc and t.data[h].key == key: + return h + h = nextTry(h, maxHash(t)) + result = -1 - h # < 0 => MISSING; insert idx = -1 - result + +proc rawGetKnownHC[X, A](t: X, key: A, hc: Hash): int {.inline.} = + rawGetKnownHCImpl() + +template genHashImpl(key, hc: typed) = + hc = hash(key) + if hc == 0: # This almost never taken branch should be very predictable. + hc = 314159265 # Value doesn't matter; Any non-zero favorite is fine. + +template genHash(key: typed): Hash = + var res: Hash + genHashImpl(key, res) + res + +template rawGetImpl() {.dirty.} = + genHashImpl(key, hc) + rawGetKnownHCImpl() + +proc rawGet[X, A](t: X, key: A, hc: var Hash): int {.inline.} = + rawGetImpl() diff --git a/lib/pure/collections/setimpl.nim b/lib/pure/collections/setimpl.nim new file mode 100644 index 000000000..eb131b540 --- /dev/null +++ b/lib/pure/collections/setimpl.nim @@ -0,0 +1,153 @@ +# +# +# Nim's Runtime Library +# (c) Copyright 2019 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +# An ``include`` file for the different hash set implementations. + + +template maxHash(t): untyped = high(t.data) +template dataLen(t): untyped = len(t.data) + +include hashcommon + +template initImpl(s: typed, size: int) = + assert isPowerOfTwo(size) + when s is OrderedSet: + s.first = -1 + s.last = -1 + s.counter = 0 + newSeq(s.data, size) + +template rawInsertImpl() {.dirty.} = + if data.len == 0: + initImpl(s, defaultInitialSize) + data[h].key = key + data[h].hcode = hc + +proc rawInsert[A](s: var HashSet[A], data: var KeyValuePairSeq[A], key: A, + hc: Hash, h: Hash) = + rawInsertImpl() + +proc enlarge[A](s: var HashSet[A]) = + var n: KeyValuePairSeq[A] + newSeq(n, len(s.data) * growthFactor) + swap(s.data, n) # n is now old seq + for i in countup(0, high(n)): + if isFilled(n[i].hcode): + var j = -1 - rawGetKnownHC(s, n[i].key, n[i].hcode) + rawInsert(s, s.data, n[i].key, n[i].hcode, j) + +template inclImpl() {.dirty.} = + if s.data.len == 0: + initImpl(s, defaultInitialSize) + var hc: Hash + var index = rawGet(s, key, hc) + if index < 0: + if mustRehash(len(s.data), s.counter): + enlarge(s) + index = rawGetKnownHC(s, key, hc) + rawInsert(s, s.data, key, hc, -1 - index) + inc(s.counter) + +template containsOrInclImpl() {.dirty.} = + if s.data.len == 0: + initImpl(s, defaultInitialSize) + var hc: Hash + var index = rawGet(s, key, hc) + if index >= 0: + result = true + else: + if mustRehash(len(s.data), s.counter): + enlarge(s) + index = rawGetKnownHC(s, key, hc) + rawInsert(s, s.data, key, hc, -1 - index) + inc(s.counter) + +template doWhile(a, b) = + while true: + b + if not a: break + +proc exclImpl[A](s: var HashSet[A], key: A) : bool {. inline .} = + var hc: Hash + var i = rawGet(s, key, hc) + var msk = high(s.data) + result = true + + if i >= 0: + result = false + dec(s.counter) + while true: # KnuthV3 Algo6.4R adapted for i=i+1 instead of i=i-1 + var j = i # The correctness of this depends on (h+1) in nextTry, + var r = j # though may be adaptable to other simple sequences. + s.data[i].hcode = 0 # mark current EMPTY + s.data[i].key = default(type(s.data[i].key)) + doWhile((i >= r and r > j) or (r > j and j > i) or (j > i and i >= r)): + i = (i + 1) and msk # increment mod table size + if isEmpty(s.data[i].hcode): # end of collision cluster; So all done + return + r = s.data[i].hcode and msk # "home" location of key@i + shallowCopy(s.data[j], s.data[i]) # data[i] will be marked EMPTY next loop + +template dollarImpl() {.dirty.} = + result = "{" + for key in items(s): + if result.len > 1: result.add(", ") + result.addQuoted(key) + result.add("}") + + + +# --------------------------- OrderedSet ------------------------------ + +proc rawGet[A](t: OrderedSet[A], key: A, hc: var Hash): int {.inline.} = + rawGetImpl() + +proc rawInsert[A](s: var OrderedSet[A], data: var OrderedKeyValuePairSeq[A], + key: A, hc: Hash, h: Hash) = + rawInsertImpl() + data[h].next = -1 + if s.first < 0: s.first = h + if s.last >= 0: data[s.last].next = h + s.last = h + +proc enlarge[A](s: var OrderedSet[A]) = + var n: OrderedKeyValuePairSeq[A] + newSeq(n, len(s.data) * growthFactor) + var h = s.first + s.first = -1 + s.last = -1 + swap(s.data, n) + while h >= 0: + var nxt = n[h].next + if isFilled(n[h].hcode): + var j = -1 - rawGetKnownHC(s, n[h].key, n[h].hcode) + rawInsert(s, s.data, n[h].key, n[h].hcode, j) + h = nxt + +proc exclImpl[A](s: var OrderedSet[A], key: A) : bool {.inline.} = + if len(s.data) == 0: + return true + var n: OrderedKeyValuePairSeq[A] + newSeq(n, len(s.data)) + var h = s.first + s.first = -1 + s.last = -1 + swap(s.data, n) + let hc = genHash(key) + result = true + while h >= 0: + var nxt = n[h].next + if isFilled(n[h].hcode): + if n[h].hcode == hc and n[h].key == key: + dec s.counter + result = false + else: + var j = -1 - rawGetKnownHC(s, n[h].key, n[h].hcode) + rawInsert(s, s.data, n[h].key, n[h].hcode, j) + h = nxt diff --git a/lib/pure/collections/sets.nim b/lib/pure/collections/sets.nim index 29bf31f96..86a72533e 100644 --- a/lib/pure/collections/sets.nim +++ b/lib/pure/collections/sets.nim @@ -26,7 +26,7 @@ ## `symmetric difference <#symmetricDifference,HashSet[A],HashSet[A]>`_ ## ## .. code-block:: -## echo toHashSet([9, 5, 1]) # {9, 1, 5} +## echo toHashSet([9, 5, 1]) # {9, 1, 5} ## echo toOrderedSet([9, 5, 1]) # {9, 5, 1} ## ## let @@ -69,148 +69,32 @@ type data: KeyValuePairSeq[A] counter: int +type + OrderedKeyValuePair[A] = tuple[ + hcode: Hash, next: int, key: A] + OrderedKeyValuePairSeq[A] = seq[OrderedKeyValuePair[A]] + OrderedSet* {.myShallow.} [A] = object ## \ + ## A generic hash set that remembers insertion order. + ## + ## Use `init proc <#init,OrderedSet[A],int>`_ or `initOrderedSet proc + ## <#initOrderedSet,int>`_ before calling other procs on it. + data: OrderedKeyValuePairSeq[A] + counter, first, last: int -# ---------------------- helpers ----------------------------------- - -const growthFactor = 2 - -when not defined(nimHasDefault): - template default[T](t: typedesc[T]): T = - ## Used by clear methods to get a default value. - var v: T - v - -# hcode for real keys cannot be zero. hcode==0 signifies an empty slot. These -# two procs retain clarity of that encoding without the space cost of an enum. -proc isEmpty(hcode: Hash): bool {.inline.} = - result = hcode == 0 - -proc isFilled(hcode: Hash): bool {.inline.} = - result = hcode != 0 - -proc nextTry(h, maxHash: Hash): Hash {.inline.} = - result = (h + 1) and maxHash - -template rawGetKnownHCImpl() {.dirty.} = - var h: Hash = hc and high(s.data) # start with real hash value - while isFilled(s.data[h].hcode): - # Compare hc THEN key with boolean short circuit. This makes the common case - # zero ==key's for missing (e.g.inserts) and exactly one ==key for present. - # It does slow down succeeding lookups by one extra Hash cmp&and..usually - # just a few clock cycles, generally worth it for any non-integer-like A. - if s.data[h].hcode == hc and s.data[h].key == key: # compare hc THEN key - return h - h = nextTry(h, high(s.data)) - result = -1 - h # < 0 => MISSING; insert idx = -1 - result - -template genHash(key: typed): Hash = - var hc = hash(key) - if hc == 0: # This almost never taken branch should be very predictable. - hc = 314159265 # Value doesn't matter; Any non-zero favorite is fine. - hc - -template rawGetImpl() {.dirty.} = - hc = genHash(key) - rawGetKnownHCImpl() - -template rawInsertImpl() {.dirty.} = - data[h].key = key - data[h].hcode = hc - -proc rawGetKnownHC[A](s: HashSet[A], key: A, hc: Hash): int {.inline.} = - rawGetKnownHCImpl() - -proc rawGet[A](s: HashSet[A], key: A, hc: var Hash): int {.inline.} = - rawGetImpl() - -proc rawInsert[A](s: var HashSet[A], data: var KeyValuePairSeq[A], key: A, - hc: Hash, h: Hash) = - rawInsertImpl() - -proc enlarge[A](s: var HashSet[A]) = - var n: KeyValuePairSeq[A] - newSeq(n, len(s.data) * growthFactor) - swap(s.data, n) # n is now old seq - for i in countup(0, high(n)): - if isFilled(n[i].hcode): - var j = -1 - rawGetKnownHC(s, n[i].key, n[i].hcode) - rawInsert(s, s.data, n[i].key, n[i].hcode, j) - -template inclImpl() {.dirty.} = - var hc: Hash - var index = rawGet(s, key, hc) - if index < 0: - if mustRehash(len(s.data), s.counter): - enlarge(s) - index = rawGetKnownHC(s, key, hc) - rawInsert(s, s.data, key, hc, -1 - index) - inc(s.counter) - -template containsOrInclImpl() {.dirty.} = - var hc: Hash - var index = rawGet(s, key, hc) - if index >= 0: - result = true - else: - if mustRehash(len(s.data), s.counter): - enlarge(s) - index = rawGetKnownHC(s, key, hc) - rawInsert(s, s.data, key, hc, -1 - index) - inc(s.counter) - -template doWhile(a, b) = - while true: - b - if not a: break - -proc exclImpl[A](s: var HashSet[A], key: A) : bool {. inline .} = - assert s.isValid, "The set needs to be initialized." - var hc: Hash - var i = rawGet(s, key, hc) - var msk = high(s.data) - result = true +const + defaultInitialSize* = 64 - if i >= 0: - result = false - dec(s.counter) - while true: # KnuthV3 Algo6.4R adapted for i=i+1 instead of i=i-1 - var j = i # The correctness of this depends on (h+1) in nextTry, - var r = j # though may be adaptable to other simple sequences. - s.data[i].hcode = 0 # mark current EMPTY - s.data[i].key = default(type(s.data[i].key)) - doWhile((i >= r and r > j) or (r > j and j > i) or (j > i and i >= r)): - i = (i + 1) and msk # increment mod table size - if isEmpty(s.data[i].hcode): # end of collision cluster; So all done - return - r = s.data[i].hcode and msk # "home" location of key@i - shallowCopy(s.data[j], s.data[i]) # data[i] will be marked EMPTY next loop - -proc mustRehash(length, counter: int): bool {.inline.} = - assert(length > counter) - result = (length * 2 < counter * 3) or (length - counter < 4) - -template dollarImpl() {.dirty.} = - result = "{" - for key in items(s): - if result.len > 1: result.add(", ") - result.addQuoted(key) - result.add("}") +include setimpl proc rightSize*(count: Natural): int {.inline.} - - - - - - # --------------------------------------------------------------------- # ------------------------------ HashSet ------------------------------ # --------------------------------------------------------------------- -proc init*[A](s: var HashSet[A], initialSize=64) = +proc init*[A](s: var HashSet[A], initialSize = defaultInitialSize) = ## Initializes a hash set. ## ## The `initialSize` parameter needs to be a power of two (default: 64). @@ -218,9 +102,8 @@ proc init*[A](s: var HashSet[A], initialSize=64) = ## `math.nextPowerOfTwo proc `_ or `rightSize proc ## <#rightSize,Natural>`_ from this module. ## - ## All set variables must be initialized before - ## use with other procs from this module, with the exception of `isValid proc - ## <#isValid,HashSet[A]>`_ and `len() <#len,HashSet[A]>`_. + ## Starting from Nim v0.20, sets are initialized by default and it is + ## not necessary to call this function explicitly. ## ## You can call this proc on a previously initialized hash set, which will ## discard all its values. This might be more convenient than iterating over @@ -235,42 +118,26 @@ proc init*[A](s: var HashSet[A], initialSize=64) = init(a) assert a.isValid - assert isPowerOfTwo(initialSize) - s.counter = 0 - newSeq(s.data, initialSize) + initImpl(s, initialSize) -proc initHashSet*[A](initialSize=64): HashSet[A] = +proc initHashSet*[A](initialSize = defaultInitialSize): HashSet[A] = ## Wrapper around `init proc <#init,HashSet[A],int>`_ for initialization of ## hash sets. ## ## Returns an empty hash set you can assign directly in ``var`` blocks in a ## single line. ## + ## Starting from Nim v0.20, sets are initialized by default and it is + ## not necessary to call this function explicitly. + ## ## See also: ## * `toHashSet proc <#toHashSet,openArray[A]>`_ runnableExamples: var a = initHashSet[int]() - assert a.isValid a.incl(3) assert len(a) == 1 - result.init(initialSize) -proc isValid*[A](s: HashSet[A]): bool = - ## Returns `true` if the set has been initialized (with `initHashSet proc - ## <#initHashSet,int>`_ or `init proc <#init,HashSet[A],int>`_). - ## - ## Most operations over an uninitialized set will crash at runtime and - ## `assert `_ in debug builds. You can use this proc in - ## your own procs to verify that sets passed to your procs are correctly - ## initialized. - ## - ## **Examples:** - ## - ## .. code-block :: - ## proc savePreferences(options: HashSet[string]) = - ## assert options.isValid, "Pass an initialized set!" - ## # Do stuff here, may crash in release builds! - result = s.data.len > 0 + result.init(initialSize) proc `[]`*[A](s: var HashSet[A], key: A): var A = ## Returns the element that is actually stored in `s` which has the same @@ -278,7 +145,6 @@ proc `[]`*[A](s: var HashSet[A], key: A): var A = ## ## This is useful when one overloaded `hash` and `==` but still needs ## reference semantics for sharing. - assert s.isValid, "The set needs to be initialized." var hc: Hash var index = rawGet(s, key, hc) if index >= 0: result = s.data[index].key @@ -305,7 +171,6 @@ proc contains*[A](s: HashSet[A], key: A): bool = assert values.contains(2) assert 2 in values - assert s.isValid, "The set needs to be initialized." var hc: Hash var index = rawGet(s, key, hc) result = index >= 0 @@ -325,7 +190,6 @@ proc incl*[A](s: var HashSet[A], key: A) = values.incl(2) assert values.len == 1 - assert s.isValid, "The set needs to be initialized." inclImpl() proc incl*[A](s: var HashSet[A], other: HashSet[A]) = @@ -344,8 +208,6 @@ proc incl*[A](s: var HashSet[A], other: HashSet[A]) = values.incl(others) assert values.len == 5 - assert s.isValid, "The set `s` needs to be initialized." - assert other.isValid, "The set `other` needs to be initialized." for item in other: incl(s, item) proc toHashSet*[A](keys: openArray[A]): HashSet[A] = @@ -368,14 +230,6 @@ proc toHashSet*[A](keys: openArray[A]): HashSet[A] = result = initHashSet[A](rightSize(keys.len)) for key in items(keys): result.incl(key) -proc initSet*[A](initialSize=64): HashSet[A] {.deprecated: - "Deprecated since v0.20, use `initHashSet`"} = initHashSet[A](initialSize) - ## Deprecated since v0.20, use `initHashSet`. - -proc toSet*[A](keys: openArray[A]): HashSet[A] {.deprecated: - "Deprecated since v0.20, use `toHashSet`"} = toHashSet[A](keys) - ## Deprecated since v0.20, use `toHashSet`. - iterator items*[A](s: HashSet[A]): A = ## Iterates over elements of the set `s`. ## @@ -395,8 +249,7 @@ iterator items*[A](s: HashSet[A]): A = ## assert a.len == 2 ## echo b ## # --> {(a: 1, b: 3), (a: 0, b: 4)} - assert s.isValid, "The set needs to be initialized." - for h in 0..high(s.data): + for h in 0 .. high(s.data): if isFilled(s.data[h].hcode): yield s.data[h].key proc containsOrIncl*[A](s: var HashSet[A], key: A): bool = @@ -417,7 +270,6 @@ proc containsOrIncl*[A](s: var HashSet[A], key: A): bool = assert values.containsOrIncl(2) == true assert values.containsOrIncl(3) == false - assert s.isValid, "The set needs to be initialized." containsOrInclImpl() proc excl*[A](s: var HashSet[A], key: A) = @@ -434,6 +286,7 @@ proc excl*[A](s: var HashSet[A], key: A) = s.excl(2) s.excl(2) assert s.len == 3 + discard exclImpl(s, key) proc excl*[A](s: var HashSet[A], other: HashSet[A]) = @@ -453,8 +306,6 @@ proc excl*[A](s: var HashSet[A], other: HashSet[A]) = assert len(numbers) == 3 ## numbers == {1, 3, 5} - assert s.isValid, "The set `s` needs to be initialized." - assert other.isValid, "The set `other` needs to be initialized." for item in other: discard exclImpl(s, item) proc missingOrExcl*[A](s: var HashSet[A], key: A): bool = @@ -474,6 +325,7 @@ proc missingOrExcl*[A](s: var HashSet[A], key: A): bool = assert s.missingOrExcl(4) == true assert s.missingOrExcl(6) == false assert s.missingOrExcl(6) == true + exclImpl(s, key) proc pop*[A](s: var HashSet[A]): A = @@ -489,7 +341,7 @@ proc pop*[A](s: var HashSet[A]): A = assert s.pop == 2 doAssertRaises(KeyError, echo s.pop) - for h in 0..high(s.data): + for h in 0 .. high(s.data): if isFilled(s.data[h].hcode): result = s.data[h].key excl(s, result) @@ -510,7 +362,7 @@ proc clear*[A](s: var HashSet[A]) = assert len(s) == 0 s.counter = 0 - for i in 0.. {2, 4, 5} ## echo toHashSet(["no", "esc'aping", "is \" provided"]) ## # --> {no, esc'aping, is " provided} - assert s.isValid, "The set needs to be initialized." dollarImpl() proc rightSize*(count: Natural): int {.inline.} = @@ -760,8 +603,28 @@ proc rightSize*(count: Natural): int {.inline.} = result = nextPowerOfTwo(count * 3 div 2 + 4) +proc initSet*[A](initialSize = defaultInitialSize): HashSet[A] {.deprecated: + "Deprecated since v0.20, use `initHashSet`"} = initHashSet[A](initialSize) + ## Deprecated since v0.20, use `initHashSet <#initHashSet,int>`_. +proc toSet*[A](keys: openArray[A]): HashSet[A] {.deprecated: + "Deprecated since v0.20, use `toHashSet`"} = toHashSet[A](keys) + ## Deprecated since v0.20, use `toHashSet <#toHashSet,openArray[A]>`_. +proc isValid*[A](s: HashSet[A]): bool {.deprecated: + "Deprecated since v0.20; sets are initialized by default"} = + ## **Deprecated since v0.20; sets are initialized by default** + ## + ## Returns `true` if the set has been initialized (with `initHashSet proc + ## <#initHashSet,int>`_ or `init proc <#init,HashSet[A],int>`_). + ## + ## **Examples:** + ## + ## .. code-block :: + ## proc savePreferences(options: HashSet[string]) = + ## assert options.isValid, "Pass an initialized set!" + ## # Do stuff here, may crash in release builds! + result = s.data.len > 0 @@ -769,89 +632,19 @@ proc rightSize*(count: Natural): int {.inline.} = # --------------------------- OrderedSet ------------------------------ # --------------------------------------------------------------------- -type - OrderedKeyValuePair[A] = tuple[ - hcode: Hash, next: int, key: A] - OrderedKeyValuePairSeq[A] = seq[OrderedKeyValuePair[A]] - OrderedSet* {.myShallow.} [A] = object ## \ - ## A generic hash set that remembers insertion order. - ## - ## Use `init proc <#init,OrderedSet[A],int>`_ or `initOrderedSet proc - ## <#initOrderedSet,int>`_ before calling other procs on it. - data: OrderedKeyValuePairSeq[A] - counter, first, last: int - - -# ---------------------- helpers ----------------------------------- - template forAllOrderedPairs(yieldStmt: untyped) {.dirty.} = - var h = s.first - var idx = 0 - while h >= 0: - var nxt = s.data[h].next - if isFilled(s.data[h].hcode): - yieldStmt - inc(idx) - h = nxt - -proc rawGetKnownHC[A](s: OrderedSet[A], key: A, hc: Hash): int {.inline.} = - rawGetKnownHCImpl() - -proc rawGet[A](s: OrderedSet[A], key: A, hc: var Hash): int {.inline.} = - rawGetImpl() - -proc rawInsert[A](s: var OrderedSet[A], data: var OrderedKeyValuePairSeq[A], - key: A, hc: Hash, h: Hash) = - rawInsertImpl() - data[h].next = -1 - if s.first < 0: s.first = h - if s.last >= 0: data[s.last].next = h - s.last = h - -proc enlarge[A](s: var OrderedSet[A]) = - var n: OrderedKeyValuePairSeq[A] - newSeq(n, len(s.data) * growthFactor) - var h = s.first - s.first = -1 - s.last = -1 - swap(s.data, n) - while h >= 0: - var nxt = n[h].next - if isFilled(n[h].hcode): - var j = -1 - rawGetKnownHC(s, n[h].key, n[h].hcode) - rawInsert(s, s.data, n[h].key, n[h].hcode, j) - h = nxt - -proc isValid*[A](s: OrderedSet[A]): bool - -proc exclImpl[A](s: var OrderedSet[A], key: A) : bool {. inline .} = - assert s.isValid, "The set needs to be initialized." - var n: OrderedKeyValuePairSeq[A] - newSeq(n, len(s.data)) - var h = s.first - s.first = -1 - s.last = -1 - swap(s.data, n) - let hc = genHash(key) - result = true - while h >= 0: - var nxt = n[h].next - if isFilled(n[h].hcode): - if n[h].hcode == hc and n[h].key == key: - dec s.counter - result = false - else: - var j = -1 - rawGetKnownHC(s, n[h].key, n[h].hcode) - rawInsert(s, s.data, n[h].key, n[h].hcode, j) - h = nxt - - - -# ----------------------------------------------------------------------- - - - -proc init*[A](s: var OrderedSet[A], initialSize=64) = + if s.data.len > 0: + var h = s.first + var idx = 0 + while h >= 0: + var nxt = s.data[h].next + if isFilled(s.data[h].hcode): + yieldStmt + inc(idx) + h = nxt + + +proc init*[A](s: var OrderedSet[A], initialSize = defaultInitialSize) = ## Initializes an ordered hash set. ## ## The `initialSize` parameter needs to be a power of two (default: 64). @@ -859,9 +652,8 @@ proc init*[A](s: var OrderedSet[A], initialSize=64) = ## `math.nextPowerOfTwo proc `_ or `rightSize proc ## <#rightSize,Natural>`_ from this module. ## - ## All set variables must be initialized before - ## use with other procs from this module, with the exception of `isValid proc - ## <#isValid,HashSet[A]>`_ and `len() <#len,HashSet[A]>`_. + ## Starting from Nim v0.20, sets are initialized by default and it is + ## not necessary to call this function explicitly. ## ## You can call this proc on a previously initialized hash set, which will ## discard all its values. This might be more convenient than iterating over @@ -876,26 +668,25 @@ proc init*[A](s: var OrderedSet[A], initialSize=64) = init(a) assert a.isValid - assert isPowerOfTwo(initialSize) - s.counter = 0 - s.first = -1 - s.last = -1 - newSeq(s.data, initialSize) + initImpl(s, initialSize) -proc initOrderedSet*[A](initialSize=64): OrderedSet[A] = +proc initOrderedSet*[A](initialSize = defaultInitialSize): OrderedSet[A] = ## Wrapper around `init proc <#init,OrderedSet[A],int>`_ for initialization of ## ordered hash sets. ## ## Returns an empty ordered hash set you can assign directly in ``var`` blocks ## in a single line. ## + ## Starting from Nim v0.20, sets are initialized by default and it is + ## not necessary to call this function explicitly. + ## ## See also: ## * `toOrderedSet proc <#toOrderedSet,openArray[A]>`_ runnableExamples: var a = initOrderedSet[int]() - assert a.isValid a.incl(3) assert len(a) == 1 + result.init(initialSize) proc toOrderedSet*[A](keys: openArray[A]): OrderedSet[A] = @@ -918,23 +709,6 @@ proc toOrderedSet*[A](keys: openArray[A]): OrderedSet[A] = result = initOrderedSet[A](rightSize(keys.len)) for key in items(keys): result.incl(key) -proc isValid*[A](s: OrderedSet[A]): bool = - ## Returns `true` if the set has been initialized (with `initHashSet proc - ## <#initOrderedSet,int>`_ or `init proc <#init,OrderedSet[A],int>`_). - ## - ## Most operations over an uninitialized set will crash at runtime and - ## `assert `_ in debug builds. You can use this proc in - ## your own procs to verify that sets passed to your procs are correctly - ## initialized. - ## - ## **Examples:** - ## - ## .. code-block :: - ## proc savePreferences(options: OrderedSet[string]) = - ## assert options.isValid, "Pass an initialized set!" - ## # Do stuff here, may crash in release builds! - result = s.data.len > 0 - proc contains*[A](s: OrderedSet[A], key: A): bool = ## Returns true if `key` is in `s`. ## @@ -952,7 +726,6 @@ proc contains*[A](s: OrderedSet[A], key: A): bool = assert values.contains(2) assert 2 in values - assert s.isValid, "The set needs to be initialized." var hc: Hash var index = rawGet(s, key, hc) result = index >= 0 @@ -972,7 +745,6 @@ proc incl*[A](s: var OrderedSet[A], key: A) = values.incl(2) assert values.len == 1 - assert s.isValid, "The set needs to be initialized." inclImpl() proc incl*[A](s: var HashSet[A], other: OrderedSet[A]) = @@ -988,8 +760,7 @@ proc incl*[A](s: var HashSet[A], other: OrderedSet[A]) = others = toOrderedSet([3, 4, 5]) values.incl(others) assert values.len == 5 - assert s.isValid, "The set `s` needs to be initialized." - assert other.isValid, "The set `other` needs to be initialized." + for item in items(other): incl(s, item) proc containsOrIncl*[A](s: var OrderedSet[A], key: A): bool = @@ -1009,7 +780,6 @@ proc containsOrIncl*[A](s: var OrderedSet[A], key: A): bool = assert values.containsOrIncl(2) == true assert values.containsOrIncl(3) == false - assert s.isValid, "The set needs to be initialized." containsOrInclImpl() proc excl*[A](s: var OrderedSet[A], key: A) = @@ -1025,6 +795,7 @@ proc excl*[A](s: var OrderedSet[A], key: A) = s.excl(2) s.excl(2) assert s.len == 3 + discard exclImpl(s, key) proc missingOrExcl*[A](s: var OrderedSet[A], key: A): bool = @@ -1044,6 +815,7 @@ proc missingOrExcl*[A](s: var OrderedSet[A], key: A): bool = assert s.missingOrExcl(4) == true assert s.missingOrExcl(6) == false assert s.missingOrExcl(6) == true + exclImpl(s, key) proc clear*[A](s: var OrderedSet[A]) = @@ -1059,7 +831,7 @@ proc clear*[A](s: var OrderedSet[A]) = s.counter = 0 s.first = -1 s.last = -1 - for i in 0.. {2, 4, 5} ## echo toOrderedSet(["no", "esc'aping", "is \" provided"]) ## # --> {no, esc'aping, is " provided} - assert s.isValid, "The set needs to be initialized." dollarImpl() @@ -1152,11 +923,9 @@ iterator items*[A](s: OrderedSet[A]): A = ## # --> Got 5 ## # --> Got 8 ## # --> Got 4 - assert s.isValid, "The set needs to be initialized." forAllOrderedPairs: yield s.data[h].key - iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] = ## Iterates through (position, value) tuples of OrderedSet `s`. runnableExamples: @@ -1166,12 +935,27 @@ iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] = p.add(x) assert p == @[(0, 'a'), (1, 'b'), (2, 'r'), (3, 'c'), (4, 'd')] - assert s.isValid, "The set needs to be initialized" forAllOrderedPairs: yield (idx, s.data[h].key) +proc isValid*[A](s: OrderedSet[A]): bool {.deprecated: + "Deprecated since v0.20; sets are initialized by default"} = + ## **Deprecated since v0.20; sets are initialized by default** + ## + ## Returns `true` if the set has been initialized (with `initHashSet proc + ## <#initOrderedSet,int>`_ or `init proc <#init,OrderedSet[A],int>`_). + ## + ## **Examples:** + ## + ## .. code-block :: + ## proc savePreferences(options: OrderedSet[string]) = + ## assert options.isValid, "Pass an initialized set!" + ## # Do stuff here, may crash in release builds! + result = s.data.len > 0 + + # ----------------------------------------------------------------------- @@ -1179,7 +963,7 @@ iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] = when isMainModule and not defined(release): proc testModule() = ## Internal micro test to validate docstrings and such. - block isValidTest: + block isValidTest: # isValid is deprecated var options: HashSet[string] proc savePreferences(options: HashSet[string]) = assert options.isValid, "Pass an initialized set!" @@ -1280,7 +1064,7 @@ when isMainModule and not defined(release): var b = a.map(proc (x: int): string = $x) assert b == toHashSet(["1", "2", "3"]) - block isValidTest: + block isValidTest: # isValid is deprecated var cards: OrderedSet[string] proc saveTarotCards(cards: OrderedSet[string]) = assert cards.isValid, "Pass an initialized set!" @@ -1393,6 +1177,69 @@ when isMainModule and not defined(release): bb.incl(y) assert aa == bb + block setsWithoutInit: + var + a: HashSet[int] + b: HashSet[int] + c: HashSet[int] + d: HashSet[int] + e: HashSet[int] + + doAssert a.containsOrIncl(3) == false + doAssert a.contains(3) + doAssert a.len == 1 + doAssert a.containsOrIncl(3) + a.incl(3) + doAssert a.len == 1 + a.incl(6) + doAssert a.len == 2 + + b.incl(5) + doAssert b.len == 1 + b.excl(5) + b.excl(c) + doAssert b.missingOrExcl(5) + doAssert b.disjoint(c) + + d = b + c + doAssert d.len == 0 + d = b * c + doAssert d.len == 0 + d = b - c + doAssert d.len == 0 + d = b -+- c + doAssert d.len == 0 + + doAssert (d < e) == false + doAssert d <= e + doAssert d == e + + block setsWithoutInit: + var + a: OrderedSet[int] + b: OrderedSet[int] + c: OrderedSet[int] + d: HashSet[int] + + + doAssert a.containsOrIncl(3) == false + doAssert a.contains(3) + doAssert a.len == 1 + doAssert a.containsOrIncl(3) + a.incl(3) + doAssert a.len == 1 + a.incl(6) + doAssert a.len == 2 + + b.incl(5) + doAssert b.len == 1 + doAssert b.missingOrExcl(5) == false + doAssert b.missingOrExcl(5) + + doAssert c.missingOrExcl(9) + d.incl(c) + doAssert d.len == 0 + when not defined(testing): echo "Micro tests run successfully." diff --git a/lib/pure/collections/sharedtables.nim b/lib/pure/collections/sharedtables.nim index 0292a27a2..6ebb00e57 100644 --- a/lib/pure/collections/sharedtables.nim +++ b/lib/pure/collections/sharedtables.nim @@ -29,6 +29,14 @@ template maxHash(t): untyped = t.dataLen-1 include tableimpl +template st_maybeRehashPutImpl(enlarge) {.dirty.} = + if mustRehash(t.dataLen, t.counter): + enlarge(t) + index = rawGetKnownHC(t, key, hc) + index = -1 - index # important to transform for mgetOrPutImpl + rawInsert(t, t.data, key, val, hc, index) + inc(t.counter) + proc enlarge[A, B](t: var SharedTable[A, B]) = let oldSize = t.dataLen let size = oldSize * growthFactor @@ -176,7 +184,7 @@ proc withKey*[A, B](t: var SharedTable[A, B], key: A, var val: B mapper(key, val, pairExists) if pairExists: - maybeRehashPutImpl(enlarge) + st_maybeRehashPutImpl(enlarge) proc `[]=`*[A, B](t: var SharedTable[A, B], key: A, val: B) = ## puts a (key, value)-pair into `t`. diff --git a/lib/pure/collections/tableimpl.nim b/lib/pure/collections/tableimpl.nim index 3e34b1488..4f9610db3 100644 --- a/lib/pure/collections/tableimpl.nim +++ b/lib/pure/collections/tableimpl.nim @@ -9,49 +9,7 @@ # An ``include`` file for the different table implementations. -# hcode for real keys cannot be zero. hcode==0 signifies an empty slot. These -# two procs retain clarity of that encoding without the space cost of an enum. -proc isEmpty(hcode: Hash): bool {.inline.} = - result = hcode == 0 - -proc isFilled(hcode: Hash): bool {.inline.} = - result = hcode != 0 - -const - growthFactor = 2 - -proc mustRehash(length, counter: int): bool {.inline.} = - assert(length > counter) - result = (length * 2 < counter * 3) or (length - counter < 4) - -proc nextTry(h, maxHash: Hash): Hash {.inline.} = - result = (h + 1) and maxHash - -template rawGetKnownHCImpl() {.dirty.} = - var h: Hash = hc and maxHash(t) # start with real hash value - while isFilled(t.data[h].hcode): - # Compare hc THEN key with boolean short circuit. This makes the common case - # zero ==key's for missing (e.g.inserts) and exactly one ==key for present. - # It does slow down succeeding lookups by one extra Hash cmp&and..usually - # just a few clock cycles, generally worth it for any non-integer-like A. - if t.data[h].hcode == hc and t.data[h].key == key: - return h - h = nextTry(h, maxHash(t)) - result = -1 - h # < 0 => MISSING; insert idx = -1 - result - -template genHashImpl(key, hc: typed) = - hc = hash(key) - if hc == 0: # This almost never taken branch should be very predictable. - hc = 314159265 # Value doesn't matter; Any non-zero favorite is fine. - -template genHash(key: typed): Hash = - var res: Hash - genHashImpl(key, res) - res - -template rawGetImpl() {.dirty.} = - genHashImpl(key, hc) - rawGetKnownHCImpl() +include hashcommon template rawGetDeepImpl() {.dirty.} = # Search algo for unconditional add genHashImpl(key, hc) @@ -65,20 +23,16 @@ template rawInsertImpl() {.dirty.} = data[h].val = val data[h].hcode = hc -proc rawGetKnownHC[X, A](t: X, key: A, hc: Hash): int {.inline.} = - rawGetKnownHCImpl() - proc rawGetDeep[X, A](t: X, key: A, hc: var Hash): int {.inline.} = rawGetDeepImpl() -proc rawGet[X, A](t: X, key: A, hc: var Hash): int {.inline.} = - rawGetImpl() - proc rawInsert[X, A, B](t: var X, data: var KeyValuePairSeq[A, B], key: A, val: B, hc: Hash, h: Hash) = rawInsertImpl() template addImpl(enlarge) {.dirty.} = + if t.dataLen == 0: + initImpl(t, defaultInitialSize) if mustRehash(t.dataLen, t.counter): enlarge(t) var hc: Hash var j = rawGetDeep(t, key, hc) @@ -86,6 +40,8 @@ template addImpl(enlarge) {.dirty.} = inc(t.counter) template maybeRehashPutImpl(enlarge) {.dirty.} = + if t.dataLen == 0: + initImpl(t, defaultInitialSize) if mustRehash(t.dataLen, t.counter): enlarge(t) index = rawGetKnownHC(t, key, hc) @@ -94,12 +50,16 @@ template maybeRehashPutImpl(enlarge) {.dirty.} = inc(t.counter) template putImpl(enlarge) {.dirty.} = + if t.dataLen == 0: + initImpl(t, defaultInitialSize) var hc: Hash var index = rawGet(t, key, hc) if index >= 0: t.data[index].val = val else: maybeRehashPutImpl(enlarge) template mgetOrPutImpl(enlarge) {.dirty.} = + if t.dataLen == 0: + initImpl(t, defaultInitialSize) var hc: Hash var index = rawGet(t, key, hc) if index < 0: @@ -109,6 +69,8 @@ template mgetOrPutImpl(enlarge) {.dirty.} = result = t.data[index].val template hasKeyOrPutImpl(enlarge) {.dirty.} = + if t.dataLen == 0: + initImpl(t, defaultInitialSize) var hc: Hash var index = rawGet(t, key, hc) if index < 0: @@ -116,11 +78,6 @@ template hasKeyOrPutImpl(enlarge) {.dirty.} = maybeRehashPutImpl(enlarge) else: result = true -when not defined(nimHasDefault): - template default[T](t: typedesc[T]): T = - var v: T - v - template delImplIdx(t, i) = let msk = maxHash(t) if i >= 0: @@ -150,9 +107,53 @@ template delImpl() {.dirty.} = delImplIdx(t, i) template clearImpl() {.dirty.} = - for i in 0 ..< t.data.len: + for i in 0 ..< t.dataLen: when compiles(t.data[i].hcode): # CountTable records don't contain a hcode t.data[i].hcode = 0 t.data[i].key = default(type(t.data[i].key)) t.data[i].val = default(type(t.data[i].val)) t.counter = 0 + +template initImpl(result: typed, size: int) = + assert isPowerOfTwo(size) + result.counter = 0 + newSeq(result.data, size) + +template insertImpl() = # for CountTable + if t.dataLen == 0: initImpl(t, defaultInitialSize) + if mustRehash(len(t.data), t.counter): enlarge(t) + ctRawInsert(t, t.data, key, val) + inc(t.counter) + +template getOrDefaultImpl(t, key): untyped = + mixin rawGet + var hc: Hash + var index = rawGet(t, key, hc) + if index >= 0: result = t.data[index].val + +template getOrDefaultImpl(t, key, default: untyped): untyped = + mixin rawGet + var hc: Hash + var index = rawGet(t, key, hc) + result = if index >= 0: t.data[index].val else: default + +template dollarImpl(): untyped {.dirty.} = + if t.len == 0: + result = "{:}" + else: + result = "{" + for key, val in pairs(t): + if result.len > 1: result.add(", ") + result.addQuoted(key) + result.add(": ") + result.addQuoted(val) + result.add("}") + +template equalsImpl(s, t: typed): typed = + if s.counter == t.counter: + # different insertion orders mean different 'data' seqs, so we have + # to use the slow route here: + for key, val in s: + if not t.hasKey(key): return false + if t.getOrDefault(key) != val: return false + return true diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index 2da2baa48..7acd71f38 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -237,9 +237,13 @@ type ## For creating a new empty TableRef, use `newTable proc ## <#newTable,int>`_. +const + defaultInitialSize* = 64 # ------------------------------ helpers --------------------------------- +# Do NOT move these to tableimpl.nim, because sharedtables uses that +# file and has its own implementation. template maxHash(t): untyped = high(t.data) template dataLen(t): untyped = len(t.data) @@ -260,30 +264,6 @@ template get(t, key): untyped = else: raise newException(KeyError, "key not found") -template getOrDefaultImpl(t, key): untyped = - mixin rawGet - var hc: Hash - var index = rawGet(t, key, hc) - if index >= 0: result = t.data[index].val - -template getOrDefaultImpl(t, key, default: untyped): untyped = - mixin rawGet - var hc: Hash - var index = rawGet(t, key, hc) - result = if index >= 0: t.data[index].val else: default - -template dollarImpl(): untyped {.dirty.} = - if t.len == 0: - result = "{:}" - else: - result = "{" - for key, val in pairs(t): - if result.len > 1: result.add(", ") - result.addQuoted(key) - result.add(": ") - result.addQuoted(val) - result.add("}") - proc enlarge[A, B](t: var Table[A, B]) = var n: KeyValuePairSeq[A, B] newSeq(n, len(t.data) * growthFactor) @@ -296,14 +276,6 @@ proc enlarge[A, B](t: var Table[A, B]) = j = nextTry(j, maxHash(t)) rawInsert(t, t.data, n[i].key, n[i].val, eh, j) -template equalsImpl(s, t: typed): typed = - if s.counter == t.counter: - # different insertion orders mean different 'data' seqs, so we have - # to use the slow route here: - for key, val in s: - if not t.hasKey(key): return false - if t.getOrDefault(key) != val: return false - return true @@ -311,7 +283,7 @@ template equalsImpl(s, t: typed): typed = # ------------------------------ Table ------------------------------ # ------------------------------------------------------------------- -proc initTable*[A, B](initialSize=64): Table[A, B] = +proc initTable*[A, B](initialsize = defaultInitialSize): Table[A, B] = ## Creates a new hash table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -320,6 +292,9 @@ proc initTable*[A, B](initialSize=64): Table[A, B] = ## `math module`_ or the `rightSize proc<#rightSize,Natural>`_ ## from this module. ## + ## Starting from Nim v0.20, tables are initialized by default and it is + ## not necessary to call this function explicitly. + ## ## See also: ## * `toTable proc<#toTable,openArray[]>`_ ## * `newTable proc<#newTable,int>`_ for creating a `TableRef` @@ -327,9 +302,7 @@ proc initTable*[A, B](initialSize=64): Table[A, B] = let a = initTable[int, string]() b = initTable[char, seq[int]]() - assert isPowerOfTwo(initialSize) - result.counter = 0 - newSeq(result.data, initialSize) + initImpl(result, initialSize) proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = ## Creates a new hash table that contains the given ``pairs``. @@ -343,6 +316,7 @@ proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = let a = [('a', 5), ('b', 9)] let b = toTable(a) assert b == {'a': 5, 'b': 9}.toTable + result = initTable[A, B](rightSize(pairs.len)) for key, val in items(pairs): result[key] = val @@ -398,6 +372,7 @@ proc `[]=`*[A, B](t: var Table[A, B], key: A, val: B) = a['x'] = 7 a['y'] = 33 doAssert a == {'x': 7, 'y': 33}.toTable + putImpl(enlarge) proc hasKey*[A, B](t: Table[A, B], key: A): bool = @@ -414,6 +389,7 @@ proc hasKey*[A, B](t: Table[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.toTable doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false + var hc: Hash result = rawGet(t, key, hc) >= 0 @@ -424,6 +400,7 @@ proc contains*[A, B](t: Table[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.toTable doAssert 'b' in a == true doAssert a.contains('z') == false + return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var Table[A, B], key: A, val: B): bool = @@ -443,6 +420,7 @@ proc hasKeyOrPut*[A, B](t: var Table[A, B], key: A, val: B): bool = if a.hasKeyOrPut('z', 50): a['z'] = 99 doAssert a == {'a': 99, 'b': 9, 'z': 50}.toTable + hasKeyOrPutImpl(enlarge) proc getOrDefault*[A, B](t: Table[A, B], key: A): B = @@ -461,6 +439,7 @@ proc getOrDefault*[A, B](t: Table[A, B], key: A): B = let a = {'a': 5, 'b': 9}.toTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 + getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: Table[A, B], key: A, default: B): B = @@ -478,6 +457,7 @@ proc getOrDefault*[A, B](t: Table[A, B], key: A, default: B): B = let a = {'a': 5, 'b': 9}.toTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 + getOrDefaultImpl(t, key, default) proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = @@ -497,6 +477,7 @@ proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = doAssert a.mgetOrPut('a', 99) == 5 doAssert a.mgetOrPut('z', 99) == 99 doAssert a == {'a': 5, 'b': 9, 'z': 99}.toTable + mgetOrPutImpl(enlarge) proc len*[A, B](t: Table[A, B]): int = @@ -504,6 +485,7 @@ proc len*[A, B](t: Table[A, B]): int = runnableExamples: let a = {'a': 5, 'b': 9}.toTable doAssert len(a) == 2 + result = t.counter proc add*[A, B](t: var Table[A, B], key: A, val: B) = @@ -527,6 +509,7 @@ proc del*[A, B](t: var Table[A, B], key: A) = doAssert a == {'b': 9, 'c': 13}.toTable a.del('z') doAssert a == {'b': 9, 'c': 13}.toTable + delImpl() proc take*[A, B](t: var Table[A, B], key: A, val: var B): bool = @@ -568,6 +551,7 @@ proc clear*[A, B](t: var Table[A, B]) = doAssert len(a) == 3 clear(a) doAssert len(a) == 0 + clearImpl() proc `$`*[A, B](t: Table[A, B]): string = @@ -583,6 +567,7 @@ proc `==`*[A, B](s, t: Table[A, B]): bool = a = {'a': 5, 'b': 9, 'c': 13}.toTable b = {'b': 9, 'c': 13, 'a': 5}.toTable doAssert a == b + equalsImpl(s, t) proc rightSize*(count: Natural): int {.inline.} = @@ -692,6 +677,7 @@ iterator mpairs*[A, B](t: var Table[A, B]): (A, var B) = for k, v in a.mpairs: v.add(v[0] + 10) doAssert a == {'e': @[2, 4, 6, 8, 12], 'o': @[1, 5, 7, 9, 11]}.toTable + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) @@ -709,6 +695,7 @@ iterator keys*[A, B](t: Table[A, B]): A = for k in a.keys: a[k].add(99) doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.toTable + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].key @@ -726,6 +713,7 @@ iterator values*[A, B](t: Table[A, B]): B = }.toTable for v in a.values: doAssert v.len == 4 + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val @@ -744,6 +732,7 @@ iterator mvalues*[A, B](t: var Table[A, B]): var B = for v in a.mvalues: v.add(99) doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.toTable + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val @@ -779,7 +768,7 @@ iterator allValues*[A, B](t: Table[A, B]; key: A): B = # ------------------------------------------------------------------- -proc newTable*[A, B](initialSize=64): TableRef[A, B] = +proc newTable*[A, B](initialsize = defaultInitialSize): TableRef[A, B] = ## Creates a new ref hash table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -796,6 +785,7 @@ proc newTable*[A, B](initialSize=64): TableRef[A, B] = let a = newTable[int, string]() b = newTable[char, seq[int]]() + new(result) result[] = initTable[A, B](initialSize) @@ -811,6 +801,7 @@ proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] = let a = [('a', 5), ('b', 9)] let b = newTable(a) assert b == {'a': 5, 'b': 9}.newTable + new(result) result[] = toTable[A, B](pairs) @@ -842,6 +833,7 @@ proc `[]`*[A, B](t: TableRef[A, B], key: A): var B = doAssert a['a'] == 5 doAssertRaises(KeyError): echo a['z'] + result = t[][key] proc `[]=`*[A, B](t: TableRef[A, B], key: A, val: B) = @@ -857,6 +849,7 @@ proc `[]=`*[A, B](t: TableRef[A, B], key: A, val: B) = a['x'] = 7 a['y'] = 33 doAssert a == {'x': 7, 'y': 33}.newTable + t[][key] = val proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = @@ -874,6 +867,7 @@ proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.newTable doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false + result = t[].hasKey(key) proc contains*[A, B](t: TableRef[A, B], key: A): bool = @@ -883,6 +877,7 @@ proc contains*[A, B](t: TableRef[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.newTable doAssert 'b' in a == true doAssert a.contains('z') == false + return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var TableRef[A, B], key: A, val: B): bool = @@ -902,6 +897,7 @@ proc hasKeyOrPut*[A, B](t: var TableRef[A, B], key: A, val: B): bool = if a.hasKeyOrPut('z', 50): a['z'] = 99 doAssert a == {'a': 99, 'b': 9, 'z': 50}.newTable + t[].hasKeyOrPut(key, val) proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B = @@ -920,6 +916,7 @@ proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B = let a = {'a': 5, 'b': 9}.newTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 + getOrDefault(t[], key) proc getOrDefault*[A, B](t: TableRef[A, B], key: A, default: B): B = @@ -937,6 +934,7 @@ proc getOrDefault*[A, B](t: TableRef[A, B], key: A, default: B): B = let a = {'a': 5, 'b': 9}.newTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 + getOrDefault(t[], key, default) proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B = @@ -956,6 +954,7 @@ proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B = doAssert a.mgetOrPut('a', 99) == 5 doAssert a.mgetOrPut('z', 99) == 99 doAssert a == {'a': 5, 'b': 9, 'z': 99}.newTable + t[].mgetOrPut(key, val) proc len*[A, B](t: TableRef[A, B]): int = @@ -963,6 +962,7 @@ proc len*[A, B](t: TableRef[A, B]): int = runnableExamples: let a = {'a': 5, 'b': 9}.newTable doAssert len(a) == 2 + result = t.counter proc add*[A, B](t: TableRef[A, B], key: A, val: B) = @@ -988,6 +988,7 @@ proc del*[A, B](t: TableRef[A, B], key: A) = doAssert a == {'b': 9, 'c': 13}.newTable a.del('z') doAssert a == {'b': 9, 'c': 13}.newTable + t[].del(key) proc take*[A, B](t: TableRef[A, B], key: A, val: var B): bool = @@ -1012,6 +1013,7 @@ proc take*[A, B](t: TableRef[A, B], key: A, val: var B): bool = doAssert a.take('z', i) == false doAssert a == {'a': 5, 'c': 13}.newTable doAssert i == 0 + result = t[].take(key, val) proc clear*[A, B](t: TableRef[A, B]) = @@ -1025,6 +1027,7 @@ proc clear*[A, B](t: TableRef[A, B]) = doAssert len(a) == 3 clear(a) doAssert len(a) == 0 + clearImpl() proc `$`*[A, B](t: TableRef[A, B]): string = @@ -1041,6 +1044,7 @@ proc `==`*[A, B](s, t: TableRef[A, B]): bool = a = {'a': 5, 'b': 9, 'c': 13}.newTable b = {'b': 9, 'c': 13, 'a': 5}.newTable doAssert a == b + if isNil(s): result = isNil(t) elif isNil(t): result = false else: equalsImpl(s[], t[]) @@ -1089,6 +1093,7 @@ iterator mpairs*[A, B](t: TableRef[A, B]): (A, var B) = for k, v in a.mpairs: v.add(v[0] + 10) doAssert a == {'e': @[2, 4, 6, 8, 12], 'o': @[1, 5, 7, 9, 11]}.newTable + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) @@ -1106,6 +1111,7 @@ iterator keys*[A, B](t: TableRef[A, B]): A = for k in a.keys: a[k].add(99) doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.newTable + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].key @@ -1123,6 +1129,7 @@ iterator values*[A, B](t: TableRef[A, B]): B = }.newTable for v in a.values: doAssert v.len == 4 + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val @@ -1140,6 +1147,7 @@ iterator mvalues*[A, B](t: TableRef[A, B]): var B = for v in a.mvalues: v.add(99) doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.newTable + for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val @@ -1218,7 +1226,7 @@ template forAllOrderedPairs(yieldStmt: untyped): typed {.dirty.} = # ---------------------------------------------------------------------- -proc initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] = +proc initOrderedTable*[A, B](initialsize = defaultInitialSize): OrderedTable[A, B] = ## Creates a new ordered hash table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -1227,6 +1235,9 @@ proc initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] = ## `math module`_ or the `rightSize proc<#rightSize,Natural>`_ ## from this module. ## + ## Starting from Nim v0.20, tables are initialized by default and it is + ## not necessary to call this function explicitly. + ## ## See also: ## * `toOrderedTable proc<#toOrderedTable,openArray[]>`_ ## * `newOrderedTable proc<#newOrderedTable,int>`_ for creating an @@ -1235,11 +1246,9 @@ proc initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] = let a = initOrderedTable[int, string]() b = initOrderedTable[char, seq[int]]() - assert isPowerOfTwo(initialSize) - result.counter = 0 + initImpl(result, initialSize) result.first = -1 result.last = -1 - newSeq(result.data, initialSize) proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = ## Creates a new ordered hash table that contains the given ``pairs``. @@ -1254,6 +1263,7 @@ proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = let a = [('a', 5), ('b', 9)] let b = toOrderedTable(a) assert b == {'a': 5, 'b': 9}.toOrderedTable + result = initOrderedTable[A, B](rightSize(pairs.len)) for key, val in items(pairs): result[key] = val @@ -1278,6 +1288,7 @@ proc `[]`*[A, B](t: OrderedTable[A, B], key: A): B = doAssert a['a'] == 5 doAssertRaises(KeyError): echo a['z'] + get(t, key) proc `[]`*[A, B](t: var OrderedTable[A, B], key: A): var B= @@ -1309,6 +1320,7 @@ proc `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: B) = a['x'] = 7 a['y'] = 33 doAssert a == {'x': 7, 'y': 33}.toOrderedTable + putImpl(enlarge) proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = @@ -1326,6 +1338,7 @@ proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false + var hc: Hash result = rawGet(t, key, hc) >= 0 @@ -1336,6 +1349,7 @@ proc contains*[A, B](t: OrderedTable[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.toOrderedTable doAssert 'b' in a == true doAssert a.contains('z') == false + return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): bool = @@ -1355,6 +1369,7 @@ proc hasKeyOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): bool = if a.hasKeyOrPut('z', 50): a['z'] = 99 doAssert a == {'a': 99, 'b': 9, 'z': 50}.toOrderedTable + hasKeyOrPutImpl(enlarge) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A): B = @@ -1373,6 +1388,7 @@ proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A): B = let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 + getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A, default: B): B = @@ -1390,6 +1406,7 @@ proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A, default: B): B = let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 + getOrDefaultImpl(t, key, default) proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = @@ -1409,6 +1426,7 @@ proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = doAssert a.mgetOrPut('a', 99) == 5 doAssert a.mgetOrPut('z', 99) == 99 doAssert a == {'a': 5, 'b': 9, 'z': 99}.toOrderedTable + mgetOrPutImpl(enlarge) proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = @@ -1416,6 +1434,7 @@ proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = runnableExamples: let a = {'a': 5, 'b': 9}.toOrderedTable doAssert len(a) == 2 + result = t.counter proc add*[A, B](t: var OrderedTable[A, B], key: A, val: B) = @@ -1440,6 +1459,7 @@ proc del*[A, B](t: var OrderedTable[A, B], key: A) = doAssert a == {'b': 9, 'c': 13}.toOrderedTable a.del('z') doAssert a == {'b': 9, 'c': 13}.toOrderedTable + var n: OrderedKeyValuePairSeq[A, B] newSeq(n, len(t.data)) var h = t.first @@ -1467,6 +1487,7 @@ proc clear*[A, B](t: var OrderedTable[A, B]) = doAssert len(a) == 3 clear(a) doAssert len(a) == 0 + clearImpl() t.first = -1 t.last = -1 @@ -1602,6 +1623,7 @@ iterator mpairs*[A, B](t: var OrderedTable[A, B]): (A, var B) = for k, v in a.mpairs: v.add(v[0] + 10) doAssert a == {'o': @[1, 5, 7, 9, 11], 'e': @[2, 4, 6, 8, 12]}.toOrderedTable + forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) @@ -1619,6 +1641,7 @@ iterator keys*[A, B](t: OrderedTable[A, B]): A = for k in a.keys: a[k].add(99) doAssert a == {'o': @[1, 5, 7, 9, 99], 'e': @[2, 4, 6, 8, 99]}.toOrderedTable + forAllOrderedPairs: yield t.data[h].key @@ -1636,6 +1659,7 @@ iterator values*[A, B](t: OrderedTable[A, B]): B = }.toOrderedTable for v in a.values: doAssert v.len == 4 + forAllOrderedPairs: yield t.data[h].val @@ -1666,7 +1690,7 @@ iterator mvalues*[A, B](t: var OrderedTable[A, B]): var B = # --------------------------- OrderedTableRef ------------------------------- # --------------------------------------------------------------------------- -proc newOrderedTable*[A, B](initialSize=64): OrderedTableRef[A, B] = +proc newOrderedTable*[A, B](initialsize = defaultInitialSize): OrderedTableRef[A, B] = ## Creates a new ordered ref hash table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -1700,6 +1724,7 @@ proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B] = let a = [('a', 5), ('b', 9)] let b = newOrderedTable(a) assert b == {'a': 5, 'b': 9}.newOrderedTable + result = newOrderedTable[A, B](rightSize(pairs.len)) for key, val in items(pairs): result.add(key, val) @@ -1740,6 +1765,7 @@ proc `[]=`*[A, B](t: OrderedTableRef[A, B], key: A, val: B) = a['x'] = 7 a['y'] = 33 doAssert a == {'x': 7, 'y': 33}.newOrderedTable + t[][key] = val proc hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = @@ -1757,6 +1783,7 @@ proc hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.newOrderedTable doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false + result = t[].hasKey(key) proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = @@ -1766,6 +1793,7 @@ proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = let a = {'a': 5, 'b': 9}.newOrderedTable doAssert 'b' in a == true doAssert a.contains('z') == false + return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var OrderedTableRef[A, B], key: A, val: B): bool = @@ -1785,6 +1813,7 @@ proc hasKeyOrPut*[A, B](t: var OrderedTableRef[A, B], key: A, val: B): bool = if a.hasKeyOrPut('z', 50): a['z'] = 99 doAssert a == {'a': 99, 'b': 9, 'z': 50}.newOrderedTable + result = t[].hasKeyOrPut(key, val) proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A): B = @@ -1803,6 +1832,7 @@ proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A): B = let a = {'a': 5, 'b': 9}.newOrderedTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 + getOrDefault(t[], key) proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A, default: B): B = @@ -1820,6 +1850,7 @@ proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A, default: B): B = let a = {'a': 5, 'b': 9}.newOrderedTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 + getOrDefault(t[], key, default) proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B = @@ -1839,6 +1870,7 @@ proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B = doAssert a.mgetOrPut('a', 99) == 5 doAssert a.mgetOrPut('z', 99) == 99 doAssert a == {'a': 5, 'b': 9, 'z': 99}.newOrderedTable + result = t[].mgetOrPut(key, val) proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = @@ -1846,6 +1878,7 @@ proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = runnableExamples: let a = {'a': 5, 'b': 9}.newOrderedTable doAssert len(a) == 2 + result = t.counter proc add*[A, B](t: OrderedTableRef[A, B], key: A, val: B) = @@ -1868,6 +1901,7 @@ proc del*[A, B](t: var OrderedTableRef[A, B], key: A) = doAssert a == {'b': 9, 'c': 13}.newOrderedTable a.del('z') doAssert a == {'b': 9, 'c': 13}.newOrderedTable + t[].del(key) proc clear*[A, B](t: var OrderedTableRef[A, B]) = @@ -1880,6 +1914,7 @@ proc clear*[A, B](t: var OrderedTableRef[A, B]) = doAssert len(a) == 3 clear(a) doAssert len(a) == 0 + clear(t[]) proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x,y: (A, B)): int, order = SortOrder.Ascending) = @@ -1899,6 +1934,7 @@ proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x,y: (A, B)): int, order = doAssert a == {'a': 10, 'b': 20, 'c': 0}.newOrderedTable a.sort(system.cmp, order=SortOrder.Descending) doAssert a == {'c': 0, 'b': 20, 'a': 10}.newOrderedTable + t[].sort(cmp, order=order) proc `$`*[A, B](t: OrderedTableRef[A, B]): string = @@ -1915,6 +1951,7 @@ proc `==`*[A, B](s, t: OrderedTableRef[A, B]): bool = a = {'a': 5, 'b': 9, 'c': 13}.newOrderedTable b = {'b': 9, 'c': 13, 'a': 5}.newOrderedTable doAssert a != b + if isNil(s): result = isNil(t) elif isNil(t): result = false else: result = s[] == t[] @@ -1964,6 +2001,7 @@ iterator mpairs*[A, B](t: OrderedTableRef[A, B]): (A, var B) = for k, v in a.mpairs: v.add(v[0] + 10) doAssert a == {'o': @[1, 5, 7, 9, 11], 'e': @[2, 4, 6, 8, 12]}.newOrderedTable + forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) @@ -1981,6 +2019,7 @@ iterator keys*[A, B](t: OrderedTableRef[A, B]): A = for k in a.keys: a[k].add(99) doAssert a == {'o': @[1, 5, 7, 9, 99], 'e': @[2, 4, 6, 8, 99]}.newOrderedTable + forAllOrderedPairs: yield t.data[h].key @@ -1998,6 +2037,7 @@ iterator values*[A, B](t: OrderedTableRef[A, B]): B = }.newOrderedTable for v in a.values: doAssert v.len == 4 + forAllOrderedPairs: yield t.data[h].val @@ -2016,6 +2056,7 @@ iterator mvalues*[A, B](t: OrderedTableRef[A, B]): var B = for v in a.mvalues: v.add(99) doAssert a == {'o': @[1, 5, 7, 9, 99], 'e': @[2, 4, 6, 8, 99]}.newOrderedTable + forAllOrderedPairs: yield t.data[h].val @@ -2046,7 +2087,7 @@ type # ------------------------------ helpers --------------------------------- -proc rawInsert[A](t: CountTable[A], data: var seq[tuple[key: A, val: int]], +proc ctRawInsert[A](t: CountTable[A], data: var seq[tuple[key: A, val: int]], key: A, val: int) = var h: Hash = hash(key) and high(data) while data[h].val != 0: h = nextTry(h, high(data)) @@ -2057,10 +2098,12 @@ proc enlarge[A](t: var CountTable[A]) = var n: seq[tuple[key: A, val: int]] newSeq(n, len(t.data) * growthFactor) for i in countup(0, high(t.data)): - if t.data[i].val != 0: rawInsert(t, n, t.data[i].key, t.data[i].val) + if t.data[i].val != 0: ctRawInsert(t, n, t.data[i].key, t.data[i].val) swap(t.data, n) proc rawGet[A](t: CountTable[A], key: A): int = + if t.data.len == 0: + return -1 var h: Hash = hash(key) and high(t.data) # start with real hash value while t.data[h].val != 0: if t.data[h].key == key: return h @@ -2075,7 +2118,7 @@ proc inc*[A](t: var CountTable[A], key: A, val = 1) # ---------------------------------------------------------------------- -proc initCountTable*[A](initialSize=64): CountTable[A] = +proc initCountTable*[A](initialsize = defaultInitialSize): CountTable[A] = ## Creates a new count table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -2084,13 +2127,14 @@ proc initCountTable*[A](initialSize=64): CountTable[A] = ## `math module`_ or the `rightSize proc<#rightSize,Natural>`_ ## from this module. ## + ## Starting from Nim v0.20, tables are initialized by default and it is + ## not necessary to call this function explicitly. + ## ## See also: ## * `toCountTable proc<#toCountTable,openArray[A]>`_ ## * `newCountTable proc<#newCountTable,int>`_ for creating a ## `CountTableRef` - assert isPowerOfTwo(initialSize) - result.counter = 0 - newSeq(result.data, initialSize) + initImpl(result, initialSize) proc toCountTable*[A](keys: openArray[A]): CountTable[A] = ## Creates a new count table with every member of a container ``keys`` @@ -2130,9 +2174,7 @@ proc `[]=`*[A](t: var CountTable[A], key: A, val: int) = if h >= 0: t.data[h].val = val else: - if mustRehash(len(t.data), t.counter): enlarge(t) - rawInsert(t, t.data, key, val) - inc(t.counter) + insertImpl() proc inc*[A](t: var CountTable[A], key: A, val = 1) = ## Increments ``t[key]`` by ``val`` (default: 1). @@ -2141,14 +2183,13 @@ proc inc*[A](t: var CountTable[A], key: A, val = 1) = a.inc('a') a.inc('b', 10) doAssert a == toCountTable("aaabbbbbbbbbbb") + var index = rawGet(t, key) if index >= 0: inc(t.data[index].val, val) if t.data[index].val == 0: dec(t.counter) else: - if mustRehash(len(t.data), t.counter): enlarge(t) - rawInsert(t, t.data, key, val) - inc(t.counter) + insertImpl() proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = ## Returns the ``(key, value)`` pair with the smallest ``val``. Efficiency: O(n) @@ -2229,6 +2270,7 @@ proc sort*[A](t: var CountTable[A], order = SortOrder.Descending) = doAssert toSeq(a.values) == @[5, 2, 2, 1, 1] a.sort(SortOrder.Ascending) doAssert toSeq(a.values) == @[1, 1, 2, 2, 5] + t.data.sort(cmp=ctCmp, order=order) proc merge*[A](s: var CountTable[A], t: CountTable[A]) = @@ -2238,6 +2280,7 @@ proc merge*[A](s: var CountTable[A], t: CountTable[A]) = let b = toCountTable("bcc") a.merge(b) doAssert a == toCountTable("aaabbbccc") + for key, value in t: s.inc(key, value) @@ -2248,6 +2291,7 @@ proc merge*[A](s, t: CountTable[A]): CountTable[A] = a = toCountTable("aaabbc") b = toCountTable("bcc") doAssert merge(a, b) == toCountTable("aaabbbccc") + result = initCountTable[A](nextPowerOfTwo(max(s.len, t.len))) for table in @[s, t]: for key, value in table: @@ -2306,6 +2350,7 @@ iterator mpairs*[A](t: var CountTable[A]): (A, var int) = for k, v in mpairs(a): v = 2 doAssert a == toCountTable("aabbccddrr") + for h in 0..high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) @@ -2320,6 +2365,7 @@ iterator keys*[A](t: CountTable[A]): A = for k in keys(a): a[k] = 2 doAssert a == toCountTable("aabbccddrr") + for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].key @@ -2334,6 +2380,7 @@ iterator values*[A](t: CountTable[A]): int = let a = toCountTable("abracadabra") for v in values(a): assert v < 10 + for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val @@ -2349,6 +2396,7 @@ iterator mvalues*[A](t: var CountTable[A]): var int = for v in mvalues(a): v = 2 doAssert a == toCountTable("aabbccddrr") + for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val @@ -2364,7 +2412,7 @@ iterator mvalues*[A](t: var CountTable[A]): var int = proc inc*[A](t: CountTableRef[A], key: A, val = 1) -proc newCountTable*[A](initialSize=64): CountTableRef[A] = +proc newCountTable*[A](initialsize = defaultInitialSize): CountTableRef[A] = ## Creates a new ref count table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -2493,6 +2541,7 @@ proc merge*[A](s, t: CountTableRef[A]) = b = newCountTable("bcc") a.merge(b) doAssert a == newCountTable("aaabbbccc") + s[].merge(t[]) proc `$`*[A](t: CountTableRef[A]): string = @@ -2551,6 +2600,7 @@ iterator mpairs*[A](t: CountTableRef[A]): (A, var int) = for k, v in mpairs(a): v = 2 doAssert a == newCountTable("aabbccddrr") + for h in 0..high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) @@ -2565,6 +2615,7 @@ iterator keys*[A](t: CountTableRef[A]): A = for k in keys(a): a[k] = 2 doAssert a == newCountTable("aabbccddrr") + for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].key @@ -2579,6 +2630,7 @@ iterator values*[A](t: CountTableRef[A]): int = let a = newCountTable("abracadabra") for v in values(a): assert v < 10 + for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val @@ -2593,6 +2645,7 @@ iterator mvalues*[A](t: CountTableRef[A]): var int = for v in mvalues(a): v = 2 doAssert a == newCountTable("aabbccddrr") + for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val @@ -2813,3 +2866,99 @@ when isMainModule: doAssert "test1" == orf.getOrDefault("test1", "test1") orf["test2"] = "test2" doAssert "test2" == orf.getOrDefault("test2", "test1") + + block tableWithoutInit: + var + a: Table[string, int] + b: Table[string, int] + c: Table[string, int] + d: Table[string, int] + e: Table[string, int] + + a["a"] = 7 + doAssert a.hasKey("a") + doAssert a.len == 1 + doAssert a["a"] == 7 + a["a"] = 9 + doAssert a.len == 1 + doAssert a["a"] == 9 + + doAssert b.hasKeyOrPut("b", 5) == false + doAssert b.hasKey("b") + doAssert b.hasKeyOrPut("b", 8) + doAssert b["b"] == 5 + + doAssert c.getOrDefault("a") == 0 + doAssert c.getOrDefault("a", 3) == 3 + c["a"] = 6 + doAssert c.getOrDefault("a", 3) == 6 + + doAssert d.mgetOrPut("a", 3) == 3 + doAssert d.mgetOrPut("a", 6) == 3 + + var x = 99 + doAssert e.take("a", x) == false + doAssert x == 99 + e["a"] = 77 + doAssert e.take("a", x) + doAssert x == 77 + + block orderedTableWithoutInit: + var + a: OrderedTable[string, int] + b: OrderedTable[string, int] + c: OrderedTable[string, int] + d: OrderedTable[string, int] + + a["a"] = 7 + doAssert a.hasKey("a") + doAssert a.len == 1 + doAssert a["a"] == 7 + a["a"] = 9 + doAssert a.len == 1 + doAssert a["a"] == 9 + + doAssert b.hasKeyOrPut("b", 5) == false + doAssert b.hasKey("b") + doAssert b.hasKeyOrPut("b", 8) + doAssert b["b"] == 5 + + doAssert c.getOrDefault("a") == 0 + doAssert c.getOrDefault("a", 3) == 3 + c["a"] = 6 + doAssert c.getOrDefault("a", 3) == 6 + + doAssert d.mgetOrPut("a", 3) == 3 + doAssert d.mgetOrPut("a", 6) == 3 + + block countTableWithoutInit: + var + a: CountTable[string] + b: CountTable[string] + c: CountTable[string] + d: CountTable[string] + e: CountTable[string] + + a["a"] = 7 + doAssert a.hasKey("a") + doAssert a.len == 1 + doAssert a["a"] == 7 + a["a"] = 9 + doAssert a.len == 1 + doAssert a["a"] == 9 + + doAssert b["b"] == 0 + b.inc("b") + doAssert b["b"] == 1 + + doAssert c.getOrDefault("a") == 0 + doAssert c.getOrDefault("a", 3) == 3 + c["a"] = 6 + doAssert c.getOrDefault("a", 3) == 6 + + e["f"] = 3 + merge(d, e) + doAssert d.hasKey("f") + d.inc("f") + merge(d, e) + doAssert d["f"] == 7 diff --git a/testament/tester.nim b/testament/tester.nim index fb8ba1838..d55eb7bd2 100644 --- a/testament/tester.nim +++ b/testament/tester.nim @@ -515,6 +515,8 @@ const disabledFilesDefault = @[ "LockFreeHash.nim", "sharedstrings.nim", "tableimpl.nim", + "setimpl.nim", + "hashcommon.nim", # Error: undeclared identifier: 'hasThreadSupport' "ioselectors_epoll.nim", -- cgit 1.4.1-2-gfad0 From e1515b53d1992aa8443a3317759cf5bab7fa9139 Mon Sep 17 00:00:00 2001 From: Andreas Rumpf Date: Thu, 2 May 2019 08:07:09 +0200 Subject: introduce temporary for 'owned' to get this compile with 0.19 (#11145) * introduce temporary for 'owned' to get this compile with 0.19 * make newTable[string, owned Node]() compile (but it crashes) * make sink/owned parameters consistent * make actiontable test compile again * VM: support sytem.move; makes tests green --- compiler/injectdestructors.nim | 14 ++++++++------ compiler/sempass2.nim | 2 +- compiler/trees.nim | 2 +- compiler/vmgen.nim | 41 ++++++++++++++++++++++++++--------------- lib/pure/collections/lists.nim | 18 +++++++++++------- lib/pure/collections/tables.nim | 16 ++++++++-------- lib/pure/parsecfg.nim | 10 +++++----- lib/pure/unittest.nim | 6 +++--- lib/system.nim | 6 ++++++ 9 files changed, 69 insertions(+), 46 deletions(-) (limited to 'lib/pure/collections') diff --git a/compiler/injectdestructors.nim b/compiler/injectdestructors.nim index 90ea0356b..0e414c975 100644 --- a/compiler/injectdestructors.nim +++ b/compiler/injectdestructors.nim @@ -426,11 +426,13 @@ proc sinkParamIsLastReadCheck(c: var Con, s: PNode) = proc isSinkTypeForParam(t: PType): bool = # a parameter like 'seq[owned T]' must not be used only once, but its # elements must, so we detect this case here: - if isSinkType(t): - if t.skipTypes({tyGenericInst, tyAlias}).kind in {tyArray, tyVarargs, tyOpenArray, tySequence}: - result = false - else: - result = true + result = t.skipTypes({tyGenericInst, tyAlias}).kind in {tySink, tyOwned} + when false: + if isSinkType(t): + if t.skipTypes({tyGenericInst, tyAlias}).kind in {tyArray, tyVarargs, tyOpenArray, tySequence}: + result = false + else: + result = true proc passCopyToSink(n: PNode; c: var Con): PNode = result = newNodeIT(nkStmtListExpr, n.info, n.typ) @@ -817,7 +819,7 @@ proc injectDestructorCalls*(g: ModuleGraph; owner: PSym; n: PNode): PNode = let params = owner.typ.n for i in 1 ..< params.len: let param = params[i].sym - if isSinkParam(param) and hasDestructor(param.typ.skipTypes({tySink})): + if isSinkTypeForParam(param.typ) and hasDestructor(param.typ.skipTypes({tySink})): c.addDestroy genDestroy(c, param.typ.skipTypes({tyGenericInst, tyAlias, tySink}), params[i]) #if optNimV2 in c.graph.config.globalOptions: diff --git a/compiler/sempass2.nim b/compiler/sempass2.nim index 7fd2bd5b6..c835ce8e3 100644 --- a/compiler/sempass2.nim +++ b/compiler/sempass2.nim @@ -527,7 +527,7 @@ proc isNoEffectList(n: PNode): bool {.inline.} = n.len == 0 or (n[tagEffects] == nil and n[exceptionEffects] == nil) proc isTrival(caller: PNode): bool {.inline.} = - result = caller.kind == nkSym and caller.sym.magic in {mEqProc, mIsNil} + result = caller.kind == nkSym and caller.sym.magic in {mEqProc, mIsNil, mMove, mWasMoved} proc trackOperand(tracked: PEffects, n: PNode, paramType: PType; caller: PNode) = let a = skipConvAndClosure(n) diff --git a/compiler/trees.nim b/compiler/trees.nim index 55a3c619e..a06e6152c 100644 --- a/compiler/trees.nim +++ b/compiler/trees.nim @@ -101,7 +101,7 @@ proc isDeepConstExpr*(n: PNode): bool = if not isDeepConstExpr(n.sons[i]): return false if n.typ.isNil: result = true else: - let t = n.typ.skipTypes({tyGenericInst, tyDistinct, tyAlias, tySink}) + let t = n.typ.skipTypes({tyGenericInst, tyDistinct, tyAlias, tySink, tyOwned}) if t.kind in {tyRef, tyPtr}: return false if t.kind != tyObject or not isCaseObj(t.n): result = true diff --git a/compiler/vmgen.nim b/compiler/vmgen.nim index 3a46af08a..9c6f8a970 100644 --- a/compiler/vmgen.nim +++ b/compiler/vmgen.nim @@ -931,6 +931,21 @@ proc ldNullOpcode(t: PType): TOpcode = assert t != nil if fitsRegister(t): opcLdNullReg else: opcLdNull +proc whichAsgnOpc(n: PNode): TOpcode = + case n.typ.skipTypes(abstractRange+{tyOwned}-{tyTypeDesc}).kind + of tyBool, tyChar, tyEnum, tyOrdinal, tyInt..tyInt64, tyUInt..tyUInt64: + opcAsgnInt + of tyString, tyCString: + opcAsgnStr + of tyFloat..tyFloat128: + opcAsgnFloat + of tyRef, tyNil, tyVar, tyLent, tyPtr: + opcAsgnRef + else: + opcAsgnComplex + +proc whichAsgnOpc(n: PNode; opc: TOpcode): TOpcode = opc + proc genMagic(c: PCtx; n: PNode; dest: var TDest; m: TMagic) = case m of mAnd: c.genAndOr(n, opcFJmp, dest) @@ -1330,6 +1345,17 @@ proc genMagic(c: PCtx; n: PNode; dest: var TDest; m: TMagic) = of mRunnableExamples: discard "just ignore any call to runnableExamples" of mDestroy: discard "ignore calls to the default destructor" + of mMove: + let arg = n[1] + let a = c.genx(arg) + assert dest >= 0 + if dest < 0: dest = c.getTemp(arg.typ) + gABC(c, arg, whichAsgnOpc(arg), dest, a, 1) + # XXX use ldNullOpcode() here? + c.gABx(n, opcLdNull, a, c.genType(arg.typ)) + c.gABx(n, opcNodeToReg, a, a) + c.genAsgnPatch(arg, a) + c.freeTemp(a) else: # mGCref, mGCunref, globalError(c.config, n.info, "cannot generate code for: " & $m) @@ -1423,21 +1449,6 @@ proc genDeref(c: PCtx, n: PNode, dest: var TDest, flags: TGenFlags) = if {gfNodeAddr, gfNode} * flags == {} and fitsRegister(n.typ): c.gABC(n, opcNodeToReg, dest, dest) -proc whichAsgnOpc(n: PNode): TOpcode = - case n.typ.skipTypes(abstractRange+{tyOwned}-{tyTypeDesc}).kind - of tyBool, tyChar, tyEnum, tyOrdinal, tyInt..tyInt64, tyUInt..tyUInt64: - opcAsgnInt - of tyString, tyCString: - opcAsgnStr - of tyFloat..tyFloat128: - opcAsgnFloat - of tyRef, tyNil, tyVar, tyLent, tyPtr: - opcAsgnRef - else: - opcAsgnComplex - -proc whichAsgnOpc(n: PNode; opc: TOpcode): TOpcode = opc - proc genAsgn(c: PCtx; dest: TDest; ri: PNode; requiresCopy: bool) = let tmp = c.genx(ri) assert dest >= 0 diff --git a/lib/pure/collections/lists.nim b/lib/pure/collections/lists.nim index 1fd32c9fa..2278be218 100644 --- a/lib/pure/collections/lists.nim +++ b/lib/pure/collections/lists.nim @@ -80,14 +80,15 @@ type DoublyLinkedNodeObj*[T] = object ## A node a doubly linked list consists of. ## ## It consists of a `value` field, and pointers to `next` and `prev`. - next*, prev*: ref DoublyLinkedNodeObj[T] + next*: (ref DoublyLinkedNodeObj[T]) + prev*: ref DoublyLinkedNodeObj[T] value*: T DoublyLinkedNode*[T] = ref DoublyLinkedNodeObj[T] SinglyLinkedNodeObj*[T] = object ## A node a singly linked list consists of. ## ## It consists of a `value` field, and a pointer to `next`. - next*: ref SinglyLinkedNodeObj[T] + next*: (ref SinglyLinkedNodeObj[T]) value*: T SinglyLinkedNode*[T] = ref SinglyLinkedNodeObj[T] @@ -95,19 +96,22 @@ type ## ## Use `initSinglyLinkedList proc <#initSinglyLinkedList>`_ to create ## a new empty list. - head*, tail*: SinglyLinkedNode[T] + head*: (SinglyLinkedNode[T]) + tail*: SinglyLinkedNode[T] DoublyLinkedList*[T] = object ## A doubly linked list. ## ## Use `initDoublyLinkedList proc <#initDoublyLinkedList>`_ to create ## a new empty list. - head*, tail*: DoublyLinkedNode[T] + head*: (DoublyLinkedNode[T]) + tail*: DoublyLinkedNode[T] SinglyLinkedRing*[T] = object ## A singly linked ring. ## ## Use `initSinglyLinkedRing proc <#initSinglyLinkedRing>`_ to create ## a new empty ring. - head*, tail*: SinglyLinkedNode[T] + head*: (SinglyLinkedNode[T]) + tail*: SinglyLinkedNode[T] DoublyLinkedRing*[T] = object ## A doubly linked ring. ## @@ -147,7 +151,7 @@ proc initDoublyLinkedRing*[T](): DoublyLinkedRing[T] = var a = initDoublyLinkedRing[int]() discard -proc newDoublyLinkedNode*[T](value: T): DoublyLinkedNode[T] = +proc newDoublyLinkedNode*[T](value: T): (DoublyLinkedNode[T]) = ## Creates a new doubly linked node with the given `value`. runnableExamples: var n = newDoublyLinkedNode[int](5) @@ -156,7 +160,7 @@ proc newDoublyLinkedNode*[T](value: T): DoublyLinkedNode[T] = new(result) result.value = value -proc newSinglyLinkedNode*[T](value: T): SinglyLinkedNode[T] = +proc newSinglyLinkedNode*[T](value: T): (SinglyLinkedNode[T]) = ## Creates a new singly linked node with the given `value`. runnableExamples: var n = newSinglyLinkedNode[int](5) diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index 7acd71f38..98ece4779 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -274,7 +274,7 @@ proc enlarge[A, B](t: var Table[A, B]) = var j: Hash = eh and maxHash(t) while isFilled(t.data[j].hcode): j = nextTry(j, maxHash(t)) - rawInsert(t, t.data, n[i].key, n[i].val, eh, j) + rawInsert(t, t.data, move n[i].key, move n[i].val, eh, j) @@ -768,7 +768,7 @@ iterator allValues*[A, B](t: Table[A, B]; key: A): B = # ------------------------------------------------------------------- -proc newTable*[A, B](initialsize = defaultInitialSize): TableRef[A, B] = +proc newTable*[A, B](initialsize = defaultInitialSize): TableRef[A, B] = ## Creates a new ref hash table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -789,7 +789,7 @@ proc newTable*[A, B](initialsize = defaultInitialSize): TableRef[A, B] = new(result) result[] = initTable[A, B](initialSize) -proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] = +proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] = ## Creates a new ref hash table that contains the given ``pairs``. ## ## ``pairs`` is a container consisting of ``(key, value)`` tuples. @@ -805,7 +805,7 @@ proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] = new(result) result[] = toTable[A, B](pairs) -proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): TableRef[C, B] = +proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): TableRef[C, B] = ## Index the collection with the proc provided. # TODO: As soon as supported, change collection: A to collection: A[B] result = newTable[C, B]() @@ -1690,7 +1690,7 @@ iterator mvalues*[A, B](t: var OrderedTable[A, B]): var B = # --------------------------- OrderedTableRef ------------------------------- # --------------------------------------------------------------------------- -proc newOrderedTable*[A, B](initialsize = defaultInitialSize): OrderedTableRef[A, B] = +proc newOrderedTable*[A, B](initialsize = defaultInitialSize): OrderedTableRef[A, B] = ## Creates a new ordered ref hash table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -1711,7 +1711,7 @@ proc newOrderedTable*[A, B](initialsize = defaultInitialSize): OrderedTableRef[A new(result) result[] = initOrderedTable[A, B](initialSize) -proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B] = +proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B] = ## Creates a new ordered ref hash table that contains the given ``pairs``. ## ## ``pairs`` is a container consisting of ``(key, value)`` tuples. @@ -2412,7 +2412,7 @@ iterator mvalues*[A](t: var CountTable[A]): var int = proc inc*[A](t: CountTableRef[A], key: A, val = 1) -proc newCountTable*[A](initialsize = defaultInitialSize): CountTableRef[A] = +proc newCountTable*[A](initialsize = defaultInitialSize): CountTableRef[A] = ## Creates a new ref count table that is empty. ## ## ``initialSize`` must be a power of two (default: 64). @@ -2429,7 +2429,7 @@ proc newCountTable*[A](initialsize = defaultInitialSize): CountTableRef[A] = new(result) result[] = initCountTable[A](initialSize) -proc newCountTable*[A](keys: openArray[A]): CountTableRef[A] = +proc newCountTable*[A](keys: openArray[A]): CountTableRef[A] = ## Creates a new ref count table with every member of a container ``keys`` ## having a count of how many times it occurs in that container. result = newCountTable[A](rightSize(keys.len)) diff --git a/lib/pure/parsecfg.nim b/lib/pure/parsecfg.nim index b6fd820ff..d85359953 100644 --- a/lib/pure/parsecfg.nim +++ b/lib/pure/parsecfg.nim @@ -441,17 +441,17 @@ proc next*(c: var CfgParser): CfgEvent {.rtl, extern: "npc$1".} = # ---------------- Configuration file related operations ---------------- type - Config* = OrderedTableRef[string, OrderedTableRef[string, string]] + Config* = OrderedTableRef[string, OrderedTableRef[string, string]] proc newConfig*(): Config = ## Create a new configuration table. ## Useful when wanting to create a configuration file. - result = newOrderedTable[string, OrderedTableRef[string, string]]() + result = newOrderedTable[string, OrderedTableRef[string, string]]() -proc loadConfig*(stream: Stream, filename: string = "[stream]"): Config = +proc loadConfig*(stream: Stream, filename: string = "[stream]"): Config = ## Load the specified configuration from stream into a new Config instance. ## `filename` parameter is only used for nicer error messages. - var dict = newOrderedTable[string, OrderedTableRef[string, string]]() + var dict = newOrderedTable[string, OrderedTableRef[string, string]]() var curSection = "" ## Current section, ## the default value of the current section is "", ## which means that the current section is a common @@ -481,7 +481,7 @@ proc loadConfig*(stream: Stream, filename: string = "[stream]"): Config = close(p) result = dict -proc loadConfig*(filename: string): Config = +proc loadConfig*(filename: string): Config = ## Load the specified configuration file into a new Config instance. let file = open(filename, fmRead) let fileStream = newFileStream(file) diff --git a/lib/pure/unittest.nim b/lib/pure/unittest.nim index 446ead86c..60b20c5b8 100644 --- a/lib/pure/unittest.nim +++ b/lib/pure/unittest.nim @@ -177,13 +177,13 @@ proc addOutputFormatter*(formatter: OutputFormatter) = formatters.add(formatter) proc newConsoleOutputFormatter*(outputLevel: OutputLevel = PRINT_ALL, - colorOutput = true): ConsoleOutputFormatter = + colorOutput = true): ConsoleOutputFormatter = ConsoleOutputFormatter( outputLevel: outputLevel, colorOutput: colorOutput ) -proc defaultConsoleFormatter*(): ConsoleOutputFormatter = +proc defaultConsoleFormatter*(): ConsoleOutputFormatter = when declared(stdout): # Reading settings # On a terminal this branch is executed @@ -263,7 +263,7 @@ proc xmlEscape(s: string): string = else: result.add(c) -proc newJUnitOutputFormatter*(stream: Stream): JUnitOutputFormatter = +proc newJUnitOutputFormatter*(stream: Stream): JUnitOutputFormatter = ## Creates a formatter that writes report to the specified stream in ## JUnit format. ## The ``stream`` is NOT closed automatically when the test are finished, diff --git a/lib/system.nim b/lib/system.nim index 23868db0f..bf2e156b4 100644 --- a/lib/system.nim +++ b/lib/system.nim @@ -1641,6 +1641,9 @@ when defined(nimV2) and not defined(nimscript): proc unown*[T](x: T): T {.magic: "Unown", noSideEffect.} ## Use the expression ``x`` ignoring its ownership attribute. + # This is only required to make 0.20 compile with the 0.19 line. + template ``*(t: untyped): untyped = owned(t) + else: template owned*(t: typeDesc): typedesc = t template unown*(x: typed): typed = x @@ -1662,6 +1665,9 @@ else: new(r) return r + # This is only required to make 0.20 compile with the 0.19 line. + template ``*(t: untyped): untyped = t + template disarm*(x: typed) = ## Useful for ``disarming`` dangling pointers explicitly for the ## --newruntime. Regardless of whether --newruntime is used or not -- cgit 1.4.1-2-gfad0