`maskingShiftLeft(by:)`, `maskingShiftRight(by:)` and
`resizingShiftLeft(by:)` handle a negative amount by negating it and
shifting the other way, so `Int.min` trapped with an arithmetic
overflow. All three have a defined result for it: an amount of at least
`count` clears or removes every value, which is what `Int.min + 1`
already did.
Clamp the magnitude of a negative amount to `Int.max` in these three.
`resizingShiftRight(by:)` is left alone: a negative amount inserts
values there, and no array can hold as many as `Int.min` asks for.
The masking shifts had no tests. Add tests for both of them over
word-crossing counts and amounts on either side of `count`, for their
doc examples, and for the extreme amounts.
Co-Authored-By: Claude Fable 5.2 <noreply@anthropic.com>
A rope may contain the same leaf node at multiple positions (e.g. after
appending a rope to itself, or inserting a BigString slice into its own
base). Rope.distance(from:to:in:) assumed that two indices with the same
cached leaf reference address the same position in the tree, and returned
a distance computed only from their leaf slots. Also compare the paths
above the leaf level before taking the fast path.
This made BigString's character/scalar/UTF-16 distances and
index(_:offsetBy:) return wrong results (including indices with a bogus
utf8Offset) after such operations.
RigidSet, UniqueSet, RigidDictionary and UniqueDictionary had no
Sendable conformance, while the arrays and deques conform when their
elements are Sendable. Add the same conditional conformances: unchecked
for the rigid containers, which keep their elements behind unsafe
pointers, and checked for the unique ones.
Check that next() and reduce(into:_:) over the mapped producer rethrow
the transform's error, stop calling it after it throws, pass on only
items mapped before the failure, in order, and leak nothing.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Check that reduce(_:_:) and reduce(into:_:) rethrow the closure's error,
stop calling it after it throws, and leak nothing.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Two keys with equal hashes whose hash also agrees with a third key on
every level except the last end up in a collision node that sits below
the last hash level. Removing one of the colliding keys (remove,
removeValue, subscript setter/_modify to nil, subtracting, filter,
symmetricDifference, ...) computed `hash[level]` for that node, which
trips the `assert(!level.isAtBottom)` in `_Hash.subscript` in debug
builds. Collision nodes don't use buckets, and parents replace the
bucket of an inlined child item with their own, so release builds were
not affected.
Skip the bucket lookup at the bottom level, the same way lookups in
`_findInCollision` already do.
UnorderedView is not a Sequence, so checkSetAlgebra cannot run on it,
and most of its operations were not called by any test. Check union,
intersection, symmetricDifference and subtracting, and their mutating
forms, with an UnorderedView and with a sequence that holds
duplicates, against results built from the documented element order.
Check the set predicates in their UnorderedView, Set and Sequence
overloads against Set, plus the initializers and the descriptions.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
`TrailingArray.init(header:initializingTrailingElementsWith:)` created
the value with just its header, then ran the initializer. If the
initializer threw, the half-built value was destroyed, so `deinit`
deinitialized all `trailingCount` elements, even though the output span
had already deinitialized the ones it had initialized and the rest were
never initialized. `withTemporaryValue(header:initializingTrailingElementsWith:body:)`
had the same problem through the `defer` in `_withTemporaryValue`. With
non-trivial elements (e.g. class references) both crashed.
Initialize the trailing elements before creating the `TrailingArray`,
and if the initializer throws, only deinitialize the header (and free the
heap storage) before rethrowing.
`BitSet[members:]` resolved range expressions against
`Int.min ..< Int.max`. A closed range ending at `Int.max`
(`bits[members: ...Int.max]`, `bits[members: 0 ... Int.max]`) needs the
index after `Int.max`, so it trapped with "Index out of bounds", while
`..<Int.max` and `0...` worked.
Resolve against a small internal collection of all `Int` values whose
`index(after:)` saturates at `Int.max`. `Int.max` can never be a bit set
member, so `lower ... Int.max` resolving to `lower ..< Int.max` doesn't
change which members are selected. `BitSet.Counted[members:]` forwards
to `BitSet`, so it's fixed too.
`memoizedValue(forKey:_:)` and `Ref.value` need SwiftStdlib 6.4, so the
fuzz tests failed to compile on macOS with the UnstableHashedContainers
trait (CI only enables that trait on Linux). Skip just that operation
on older platforms instead of marking the whole tests unavailable.
test_memoizedValue_returnsNewlyInsertedValue in RigidDictionaryTests and
UniqueDictionaryTests calls memoizedValue(forKey:_:), which needs
SwiftStdlib 6.4, but the tests had no availability attribute. With the
UnstableHashedContainers trait on macOS, BasicContainersTests failed to
build ("'memoizedValue(forKey:_:)' is only available in macOS 27.0 or
newer"). Add the same @available attribute test_memoizedValue_one uses.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Run random sequences of operations on SortedDictionary and SortedSet and
compare them against a standard Dictionary/Set model after each step:
count, contents in sorted order (forward and backward), offset-based
indexing, lookups for every key in the domain, and value semantics of
earlier copies.
SortedDictionary operations include subscript assignment, the
`_modify` accessor (`take()`, optional chaining, inout), updateValue,
removeValue, modifyValue(forKey:default:), the default subscript,
remove(at:), removeFirst/removeLast(_:), popFirst/popLast, filter,
mapValues, and rebuilding from a sequence.
SortedSet operations include insert/update/remove with members that are
equal but distinguishable (checking that insert keeps and update
replaces the stored member), remove(at:), removeFirst/removeLast(_:),
the form* set algebra operations, and the element range subscripts.
In debug builds, nodes hold at most 4-5 keys, so even small key domains
produce multi-level trees. Building with COLLECTIONS_INTERNAL_CHECKS
also validates the B-tree after every mutation; with that, these tests
catch the bugs fixed in 93745231 (remove(at:) not rebalancing) and
3a80514a (empty root after removal through `_modify`).
Run random sequences of operations on RigidSet, UniqueSet,
RigidDictionary and UniqueDictionary, and after each step compare them
against a standard Set/Dictionary model: count, contents (via index
iteration), positive and negative lookups, and `_checkInvariants()`.
The operations cover insert/update/remove, the closure form of
`updateValue(forKey:with:)`, `memoizedValue(forKey:_:)`, `reallocate`/
`reserveCapacity`, `removeAll` (with and without keeping capacity),
Rigid <-> Unique conversions via `init(consuming:)`, and `_consumeAll`.
Keys use a configurable number of distinct hash values, from no
collisions down to a single collision chain, and all elements are
lifetime-tracked to catch leaks and double destroys.
These tests found the bugs fixed in #835 and #836.
When the updater closure removes an existing entry (sets the value to
nil), `UniqueDictionary.updateValue(forKey:with:)` called
`_removeValue(at:)`. But the value had already been moved out of its
slot before calling the updater, and `_removeValue(at:)` moves it out
again and discards the result, destroying uninitialized memory. This
leads to crashes or memory corruption.
`RigidDictionary.updateValue(forKey:with:)` already handles this case
correctly, by deinitializing just the key and resolving the hole.
Add `UniqueDictionary._removeEntry(withMovedValueAt:)`, which does the
same and then shrinks storage under the same condition as
`_removeValue(at:)`, and use it for the removal path.
`RigidDictionary._insertNew` (and `RigidSet._insertNew`) returned the
bucket reported by the hash table's `insertNew_Small`/`insertNew_Large`.
That is where the *last displaced* item ends up, not the new item: small
tables swap the new item into the middle and move the old middle item to
the end, and hashed tables do Robin Hood swaps along the probe sequence.
Whenever a swap happened, the returned bucket held some other entry.
`memoizedValue(forKey:_:)` on `RigidDictionary` and `UniqueDictionary`
returns a reference to the value at that bucket, so inserting a new key
often returned the value of a different key.
Track the first bucket the swapper writes the new item into, and return
that (or the final bucket if nothing was swapped). The hash table's own
return value is still used to initialize the displaced item, and its
other user (rehashing in `migrateItems_Large`) is unchanged.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Also run the permutable container checker against an OutputSpan, over the
same layouts as RigidArray.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Also run the permutable container checker against an InputSpan, over the
same layouts as RigidArray. InputSpan.swapAt(_:_:) is the only span
implementation of swapAt in this package, and a no-op version of it
passes every other test.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Run the permutable container checker against UniqueDeque over the same
storage layouts as its mutable container test, including wrapped ones.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Run the permutable container checker against RigidDeque over the same
storage layouts as its mutable container test, including wrapped ones,
where swapped pairs can span both ends of the storage.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Run the permutable container checker against UniqueArray, over arrays of
up to ten items, full and with spare capacity.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Also run the permutable container checker against the mutable span of a
RigidArray, over the same layouts. MutableSpan is nonescapable, so this
also runs the checker on a nonescapable container.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Run the permutable container checker against RigidArray, over arrays of
up to ten items, full and with spare capacity.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Check swapAt(_:_:), the one requirement PermutableContainer adds to
Container, against an Array model. The checker swaps every pair of
indices, including an index with itself, and then repeats the same swaps
in reverse order, comparing the whole container after each swap. That
leaves the container holding the expected contents in their original
order. It first runs validateContainer.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
- withEveryDeque/withEveryFullDeque now visit capacity 0.
- checkEquatable reports transitivity violations instead of trapping
when pairs arrive out of order (non-transitive oracles, maxSamples).
- Minimal range-replaceable collections no longer trap in removeLast()
and popLast().
- LifetimeTracked's "Double deinit" precondition can now fire.
- withEvery, withEveryRange and withSomeArrayLayouts include the
failing value in their "Throwing trace".
- CustomCountedProducer drops its unused chunkSize parameter, and the
two loops that reran identical cases over it are removed.
Adds regression tests for the first three.
Fixes#810