2225 Commits
Author SHA1 Message Date
Doug Gregor 3b10d15a65 Merge pull request #848 from sandeepvijayarao09/fix-trailing-array-throwing-init
[TrailingElements] Don't deinitialize elements when the initializer throws
2026-11-21 14:50:19 -08:00
Karoy Lorentey a807eb67ee Merge pull request #851 from Joseph-Cursio/producer-throwing-closure-tests
Test Producer.reduce and map with a throwing closure
2026-11-19 14:16:09 -08:00
Karoy Lorentey 50cce1e818 Merge pull request #852 from Joseph-Cursio/unorderedview-tests
Test OrderedSet.UnorderedView's SetAlgebra operations
2026-11-19 11:29:33 -08:00
Karoy Lorentey 8594f76181 Merge pull request #872 from lorentey/hashed-container-benchmarks
[Benchmark] Add basic lookup benchmarks for hashed containers
2026-11-19 11:13:06 -08:00
Karoy Lorentey f9fe9f44f7 [Benchmarks] Add basic lookup benchmarks for hashed containers 2026-11-18 16:29:40 -08:00
Karoy Lorentey 29fd239474 [Benchmarks] Unconditionally enable unstable traits in swift-collections
Evidently some versions of Xcode have trouble dealing with conditionally forwarded traits.
2026-11-18 16:28:47 -08:00
Karoy Lorentey dc97b85ef2 Merge pull request #857 from apple/bump-github-workflows-0.0.18
Bump `swiftlang/github-workflows` to 0.0.18
2026-11-18 16:16:26 -08:00
Karoy Lorentey 43803b742a Merge pull request #870 from yuvrajtiwary-bitmesraece/bitarray-shift-int-min
[BitCollections] Don't trap in BitArray shifts when the amount is Int.min
2026-11-18 12:08:01 -08:00
Karoy Lorentey 68388f097f Merge pull request #858 from sandeepvijayarao09/fix-rope-distance-shared-leaves
[Rope] Don't take the same-leaf fast path in distance(from:to:in:) for shared leaves
2026-11-18 12:07:44 -08:00
Yuvraj TiwaryandClaude Fable 5.2 09d8daf0b5 [BitCollections] Don't trap in BitArray shifts when the amount is Int.min
`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>
2026-11-18 12:00:05 +05:30
Karoy Lorentey 8c409d4e06 [RigidDictionary] Deallocate values buffer on deinit (#869)
Oops, empty RigidDictionary instances leaked their values buffers on deinit.
2026-11-17 20:51:22 -08:00
Karoy Lorentey a06a54fe39 [RigidDictionary] Deallocate values buffer on deinit
Oops, empty RigidDictionary instances leaked their values buffers on deinit.
2026-11-17 14:59:40 -08:00
Sandeep Vijayarao 503047e77a [Rope] Don't take the same-leaf fast path in distance(from:to:in:) for shared leaves
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.
2026-11-16 18:50:37 -08:00
Sandeep Vijayarao 0165c6e71c Use LifetimeTracked in the trailing elements tests 2026-11-16 18:10:52 -08:00
Rick Newton-Rogers 66a16e5b01 Bump swiftlang/github-workflows to 0.0.18
The new workflows use macOS Golden Gate rather than macOS Tahoe by default.
2026-11-16 19:13:20 -05:00
SandeepVijayarao 86da5fc128 Merge pull request #846 from sandeepvijayarao09/fix-bitset-bitpattern-negative
[BitCollections] Don't keep sign extension bits in BitSet(bitPattern:)
2026-11-16 14:27:24 -08:00
Karoy Lorentey e110089b7c Merge pull request #856 from lorentey/small-fixes
An assortment of minor fixes
2026-11-16 14:07:33 -08:00
Karoy Lorentey 24bb9e4610 Merge pull request #855 from unaltolga/fix-hashed-containers-sendable
[BasicContainers] Make the hashed containers Sendable
2026-11-16 14:07:16 -08:00
Karoy Lorentey af94796d89 Merge pull request #850 from 0z5a/fix/hash-tree-bottom-collision-removal
[HashTreeCollections] Don't read hash buckets below the last hash level
2026-11-16 14:06:43 -08:00
Karoy Lorentey e4bf8eeccb Merge pull request #847 from sandeepvijayarao09/fix-bitset-members-int-max
[BitCollections] Don't trap on BitSet[members:] closed ranges ending at Int.max
2026-11-16 14:06:27 -08:00
Karoy Lorentey ddf1a48382 [test] Fix strict memory safety warnings 2026-11-16 11:37:39 -08:00
Karoy Lorentey 10e81940b1 HashTreeCollection._HashNode: Use immortal empty singleton 2026-11-16 11:36:29 -08:00
Karoy Lorentey 8f033f1450 MutableContainer.updateElements: Keep consistent with MutableSpan proposal 2026-11-16 11:35:33 -08:00
Tolga Unal c211bc56af [BasicContainers] Make the hashed containers Sendable
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.
2026-11-16 11:38:37 -05:00
Joseph CursioandClaude Opus 5.5 0b3faf58d9 Test Producer.map with a throwing transform
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>
2026-11-13 07:52:21 -06:00
Joseph CursioandClaude Opus 5.5 598f867179 Test Producer.reduce with a throwing closure over noncopyable items
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>
2026-11-13 07:50:42 -06:00
0z5a 0183be558f [HashTreeCollections] Don't read hash buckets below the last hash level
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.
2026-11-13 08:53:29 +01:00
Joseph CursioandClaude Opus 5.5 7095a4804f Test OrderedSet.UnorderedView's SetAlgebra operations
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>
2026-11-12 12:40:30 -06:00
Sandeep Vijayarao a46a543feb [TrailingElements] Don't deinitialize elements when the initializer throws
`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.
2026-11-11 00:24:31 -08:00
Sandeep Vijayarao 1f4913eb96 [BitCollections] Don't trap on BitSet[members:] closed ranges ending at Int.max
`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.
2026-11-11 00:19:39 -08:00
Karoy Lorentey 88754449ab Merge pull request #845 from aashish254/codex/812-container-iterator-boundary
Fix ContainerIterator skip bounds
1.7.6
2026-11-10 11:16:20 -08:00
Karoy Lorentey 78be6a1820 Merge pull request #844 from SwastikTripathi/undeprecate-withkeys
[BasicContainers] Un-deprecate withKeys while keys is miscompiled
2026-11-10 11:15:53 -08:00
Karoy Lorentey 827fef0660 Merge pull request #817 from Joseph-Cursio/drainable-container-check
Add checkDrainableContainer and fix RigidArray's consumeLast recursion
2026-11-10 11:01:51 -08:00
Karoy Lorentey 612865a2d0 Merge pull request #823 from Joseph-Cursio/fix-816-permutable-noncopyable
Add checkPermutableContainer
2026-11-10 11:01:28 -08:00
Karoy Lorentey d01e52d04d Merge pull request #843 from lorentey/immortalize-deque-empty-singleton
Deque: Make the empty singleton immortal
2026-11-09 14:07:29 -08:00
Aashish fc11462e69 Fix ContainerIterator skip bounds 2026-11-09 21:42:36 +05:45
Swastik TripathiandClaude Opus 5.5 b0d9a5ebbb [BasicContainers] Un-deprecate withKeys while keys is miscompiled
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-11-07 09:12:34 +05:30
Karoy Lorentey 8d0a2dfceb Deque: Make the empty singleton immortal 2026-11-06 16:06:08 -08:00
Karoy Lorentey 9e74a3f71f Merge pull request #839 from sandeepvijayarao09/sorted-collections-fuzz-tests
[SortedCollections] Add differential fuzz tests for SortedDictionary and SortedSet
2026-11-06 14:33:31 -08:00
Karoy Lorentey de714531cf Merge pull request #837 from sandeepvijayarao09/hashed-containers-fuzz-tests-v2
[BasicContainers] Add differential fuzz tests for the hashed containers
2026-11-06 14:33:11 -08:00
Karoy Lorentey 54a1457375 Merge pull request #838 from sandeepvijayarao09/unique-dictionary-shrink-punch-hole
[BasicContainers] Don't resolve the hole before shrinking in UniqueDictionary
2026-11-06 14:02:58 -08:00
Karoy Lorentey af4e8c9a0e Merge pull request #840 from SwastikTripathi/fix/memoized-value-test-availability
[BasicContainers] Mark the new memoizedValue tests as SwiftStdlib 6.4
2026-11-06 13:54:26 -08:00
Karoy Lorentey 9172930c07 Merge pull request #842 from charles-zablit/cz/cmake/cmake-3.29
[CMake] Require CMake 3.29 and drop the CMP0157 checks
2026-11-06 12:43:26 -08:00
Charles Zablit 87134207c5 [CMake] Require CMake 3.29 and drop the CMP0157 checks 2026-11-06 12:05:41 +00:00
Sandeep Vijayarao ebc8757bd3 Guard the memoizedValue fuzz steps with #available
`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.
2026-11-06 03:35:03 -08:00
Swastik TripathiandClaude Opus 5.5 d3f3684195 [BasicContainers] Mark the new memoizedValue tests as SwiftStdlib 6.4
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>
2026-11-06 13:40:07 +05:30
Sandeep Vijayarao 1aa0323dd7 [SortedCollections] Add differential fuzz tests for SortedDictionary and SortedSet
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`).
2026-11-05 19:05:49 -08:00
Sandeep Vijayarao 9a699a1952 [BasicContainers] Don't resolve the hole before shrinking in UniqueDictionary
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:)`.
2026-11-05 18:54:31 -08:00
Sandeep Vijayarao b2f5535d27 [BasicContainers] Add differential fuzz tests for the hashed containers
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.
2026-11-05 18:51:15 -08:00
Karoy Lorentey 9b328ecb94 Merge pull request #836 from sandeepvijayarao09/fix-unique-dictionary-closure-removal
[BasicContainers] Fix double destroy in UniqueDictionary.updateValue(forKey:with:)
2026-11-05 18:50:36 -08:00