`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`).
Resolves the FIXME added in #836: when removing an entry through
`updateValue(forKey:with:)` triggers shrinking, there is no need to
restore the hash table's invariants first, since resizing rehashes every
item anyway.
Factor the part of `RigidDictionary._punchHole(at:)` that doesn't touch
the value slot into `_punchHole(withMovedValueAt:)`, and use it on the
shrink path of `UniqueDictionary._removeEntry(withMovedValueAt:)`, which
now mirrors `_removeValue(at:)`.
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.