* CIs: attempt to use csources_v1
* also updated the BSDs
* also updated azure pipelines
* std modules should not itself use the 'std/' import dir...
* compiler has to be careful with std/ for v1 booting
* Add some enhancements to `jsonutils.nim`
* Use `jsonutils.nim` hookable API to add a possibility to deserialize
JSON arrays directly to `HashSet` and `OrderedSet` types and
respectively to serialize those types to JSON arrays.
* Also add a possibility to deserialize JSON `null` objects to Nim
option objects and respectively to serialize Nim option object to JSON
object if some or to JSON `null` object if none.
* Move serialization/deserialization functionality for `Table` and
`OrderedTable` types from `jsonutils.nim` to `tables.nim` via the
hookable API.
* Add object `jsonutils.Joptions` and parameter from its type to
`jsonutils.fromJson` procedure to control whether to allow
deserializing JSON objects to Nim objects when the JSON has some
extra or missing keys.
* Add unit tests for the added functionalities to `tjsonutils.nim`.
* improve fromJsonFields
* Add changelog entry for the jsonutils enhancements
* Add TODO in `jsonutils.nim`
* Added an entry to "Future directions" section in `jsonutils.nim` as
suggestion for future support of serialization and de-serialization of
nested variant objects.
* Added currently disabled test case in `tjsonutils.nim` for testing
serialization and de-serialization of nested variant objects.
* Move JSON hooks to `jsonutils.nim`
Move `fromJsonHook` and `toJsonHook` procedures for different types to
`jsonutils.nim` module to avoid a dependency of collections modules to
the `json.nim` module.
The hooks are removed from the following modules:
* `tables.nim`
* `sets.nim`
* `options.nim`
* `strtabs.nim`
* Add some tests about `StringTableRef`
Add tests for `StringTableRef`'s `fromJsonHook` and `toJsonHook` to
`tjsonutils.nim`.
* Disable a warning in `jsonutils.nim`
Mark `fun` template in `jsonutils` module with `{.used.}` pragma in
order to disable `[XDeclaredButNotUsed]` hint. The template is actually
used by the `initCaseObject` macro in the same module.
Co-authored-by: Timothee Cour <timothee.cour2@gmail.com>
request. This can be conceived as an alternate, more capable resolution of
https://github.com/nim-lang/Nim/issues/12200
than
https://github.com/nim-lang/Nim/pull/12208
The code re-org idea here is to upgrade tablimpl.nim:`delImpl`/`delImplIdx`
to abstract client code conventions for cell emptiness & cell hashing via
three new template arguments - `makeEmpty`, `cellEmpty`, `cellHash` which
all take a single integer argument and clear a cell, test if clear or
produce the hash of the key stored at that index in `.data[]`.
Then we update the 3 call sites (`Table`, `CountTable`, `SharedTable`) of
`delImpl`/`delImplIdx` by defining define those arguments just before the
first invocation as non-exported templates.
Because `CountTable` does not save hash() outputs as `.hcode`, it needs a
new tableimpl.nim:`delImplNoHCode` which simply in-lines the hash search
when no `.hcode` field is available for "prefix compare" acceleration.
It is conceivable this new template could be used by future variants, such
as one optimized for integer keys where `hash()` and `==` are fast and
`.hcode` is both wasted space & time (though a small change to interfaces
there for a sentinel key meaning "empty" is needed for maximum efficiency).
We also eliminate the old O(n) `proc remove(CountTable...)` in favor of
simply invoking the new `delImpl*` templates and take care to correctly
handle the case where `val` is either zero for non-existent keys in `inc`
or evolves to zero over time in `[]=` or `inc`.
The only user-visible changes from the +-42 delta here are speed, iteration
order post deletes, and relaxing the `Positive` constraint on `val` in
`proc inc` again, as indicated in the `changelog.md` entry.
* remove a condition that table size must be passed as power of 2
* remove power-of-2 condition from sets and sharedtables
* remove power-of-2 condition from deques
* use 'correctSize' for both branches
* prettify changelog.md and fix typos
* add a changelog entry
* fix double-call of 'right-size'
* fix the same thing in sets.nim
* introduce a new internal proc `slotsNeeded`
Deprecate the public proc `rightSize`, which is not needed anymore.
Now it is an identity function, allowing the old code to work
correctly and without extra allocations.
The `smallest` and `largest` procs for `CountTable` returned a tuple
with named fields, but the same procs for `CountTableRef` returned an
anonymous tuple.
This commit makes those `CountTableRef` procs more consistent, and adds
a test.
Fixes: #14918
* Unwind just the "pseudorandom probing" (whole hash-code-keyed variable
stride double hashing) part of recent sets & tables changes (which has
still been causing bugs over a month later (e.g., two days ago
https://github.com/nim-lang/Nim/issues/13794) as well as still having
several "figure this out" implementation question comments in them (see
just diffs of this PR).
This topic has been discussed in many places:
https://github.com/nim-lang/Nim/issues/13393https://github.com/nim-lang/Nim/pull/13418https://github.com/nim-lang/Nim/pull/13440https://github.com/nim-lang/Nim/issues/13794
Alternative/non-mandatory stronger integer hashes (or vice-versa opt-in
identity hashes) are a better solution that is more general (no illusion
of one hard-coded sequence solving all problems) while retaining the
virtues of linear probing such as cache obliviousness and age-less tables
under delete-heavy workloads (still untested after a month of this change).
The only real solution for truly adversarial keys is a hash keyed off of
data unobservable to attackers. That all fits better with a few families
of user-pluggable/define-switchable hashes which can be provided in a
separate PR more about `hashes.nim`.
This PR carefully preserves the better (but still hard coded!) probing
of the `intsets` and other recent fixes like `move` annotations, hash
order invariant tests, `intsets.missingOrExcl` fixing, and the move of
`rightSize` into `hashcommon.nim`.
* Fix `data.len` -> `dataLen` problem.
* fix#13496 handle tombstones
* add test
* more tests
* fix#13504; add SharedTable tests
* fix #https://github.com/nim-lang/Nim/issues/13505 intsets.missingOrExcl silently gave wrong results sometimes
* add test for tintsets
https://github.com/nim-lang/Nim/pull/12600
and in
https://forum.nim-lang.org/t/5499
indicates that everyone is happy/happier with ``pop``.
This just renames the brand new ``take``s to ``pop`` and installs inline
aliases/wrappers to preserve ``Table.take`` and ``TableRef.take``.
Update apis.rst to try to maintain consistency of remove-and-return procs.
