142 Commits
Author SHA1 Message Date
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
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
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 5bb5daddbb Merge pull request #807 from SwastikTripathi/docs-examples
Fix doc comment examples in OrderedDictionary, BitArray and SortedDictionary
2026-11-03 14:22:34 -08:00
HuzaifaChaudary ed61a95cc8 [BitCollections] sign extend BitArray conversions to integers wider than a word
converting a negative bit array to `Int128` lost the sign above the first
64 bits , so `Int128(truncatingIfNeeded: "1" as BitArray)` gave
18446744073709551615 , not -1 , `Int128(exactly:)` gave nil , and
`Int128(_:)` trapped . a negative value now starts out as all ones , so the
words shifted in keep the sign .

the trap message also named `BitArray` as the type it could not convert
to , it names the integer type now .
2026-10-30 20:22:20 +05:00
Swastik TripathiandClaude Opus 5.5 8da3cafe2e Fix doc comment examples in OrderedDictionary, BitArray and SortedDictionary
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-10-30 09:04:13 +05:30
Karoy Lorentey 885d9a7a7e Merge pull request #798 from aashish254/fix-bitarray-resizing-shift
[BitCollections] Fix BitArray.resizingShiftRight leaving stale bits
2026-10-22 18:09:51 -07:00
Aashish fc31ca4a29 [BitCollections] Fix BitSet intersection doc examples for Range inputs
The examples for `intersection(_ other: Range<Int>)` and
`formIntersection(_ other: Range<Int>)` (on both `BitSet` and
`BitSet.Counted`) showed the result of the corresponding `subtract`
example instead: intersecting `[1, 2, 3, 4]` with `-10 ..< 3` yields
`[1, 2]`, not `[3, 4]`.
2026-10-22 16:34:53 +05:45
Aashish 297ffa296b [BitCollections] Fix BitArray.resizingShiftRight leaving stale bits
_resizingShiftRight(by:) copied the surviving suffix down to index 0 and
then removed `count &- amount` trailing bits instead of `amount`, so it
truncated the result to `amount` stale bits rather than keeping
`count - amount` valid ones. resizingShiftLeft(by: -n) was affected via
the same path, and the API had no test coverage at all.

Also fix the doc examples, which demonstrated the resizing shifts with
the masking shift function names (and, in one case, a result whose bit
count contradicted the documented growth by `amount`).

Add regression tests asserting parity with the documented semantics
(dropFirst / prepending false values) across word-boundary counts,
negative amounts, boundary `amount` values, and the doc examples
verbatim.
2026-10-22 15:27:56 +05:45
Karoy Lorentey 24339ad6a3 CMake: Remove obsolete references to source variables 2026-10-12 12:24:03 -07:00
kwy404 ea599358e6 [BitCollections] Fix BitSet.Counted.isEqualSet(to:) rejecting sequences with duplicates
The generic `isEqualSet(to: some Sequence<Int>)` overload returned false
whenever `other.underestimatedCount` exceeded `count`. A sequence with
duplicate items can be longer than the set it equals, so
`([1, 2, 3, 4] as BitSet.Counted).isEqualSet(to: [4, 1, 1, 2, 3, 3, 4] as [Int])`
returned false, contradicting the documented behavior.

Forward straight to `BitSet.isEqualSet(to:)`, which already handles
duplicates and keeps the count shortcut for unique collections.
2026-10-02 17:54:38 -03:00
Karoy Lorentey d07dc32dfa Sources: Add unsafe keywords where needed 2026-10-01 11:14:29 -07:00
Karoy Lorentey 0ec72a9532 Stop using @_spi attribute and @testable import 2026-09-29 18:32:55 -07:00
Nikhil Gupta 84e65e8b5a [BitCollections] Fix BitSet.Counted.update(with:) not maintaining the cached count
BitSet.Counted caches its size in `_count` so that `count` is O(1).
Every mutating operation is responsible for keeping that cache in sync
with the underlying bit set.

`update(with:)` forwarded straight to `BitSet.update(with:)` without
adjusting `_count`. That method inserts the member when it isn't already
present (it is defined as `insert(newMember).inserted ? nil : newMember`),
so inserting a new member this way left the cached count one too low.

The stale count is observable in a few ways:

- `count` under-reports the number of members.
- `isEmpty` is `_count == 0`, so a set that still contains members can
  report itself as empty.
- The `Collection` conformance promises `count` elements but iteration
  yields more, which breaks the standard library. `Array(set)` traps with
  "Fatal error: invalid Collection: more than 'count' elements in
  collection".

In builds with COLLECTIONS_INTERNAL_CHECKS this also violates
`_checkInvariants()`, which asserts `_count == _bits.count`.

Mirror what `insert(_:)` already does and bump `_count` when a new member
was inserted. `update(with:)` returns nil exactly in that case.

`BitSet` has had a `test_update` for this all along; `BitSet.Counted` did
not, which is how this went unnoticed. Add the matching test, following
the same combinatorial style and using `Set<Int>` as the oracle.
2026-09-25 13:02:10 +05:30
hxperl 80216ab026 Unbacktick parameter names so DocC binds the parameter docs
Six `- Parameter` entries in `Deque` and `BitSet` write the parameter
name inside backticks (``- Parameter `i`:``). DocC binds parameter
documentation by bare identifier, so these never attach: no Parameters
section is rendered at all, and the entry instead falls into the
Discussion as a literal "Parameter `i`: ..." bullet, which also swallows
the `- Complexity:` callout that follows it.

Dropping the backticks around the name restores the Parameters section on
all six pages. Backticks inside the description text are left alone.
2026-09-11 14:07:13 +09:00
Dylan Pulver 85342a6a49 [BitSet] isEqualSet(to: Range<Int>) is wrong for an empty range
`_toUInt()` returns nil whenever a bound is negative, and the guard maps that
straight to `false`. That is right for a nonempty range -- a bit set can never
hold a negative value -- but an empty range equals the empty set regardless of
where its bounds sit, so `BitSet().isEqualSet(to: -5 ..< -5)` answered false.

Five of the six `Range<Int>` predicates already handle this: isSubset and
isDisjoint clamp, isStrictSubset composes those two, and isSuperset and
isStrictSuperset test `other.isEmpty` before converting. isEqualSet was the
one that did not, which let a bit set be both a subset and a superset of a
range while reporting that it was not equal to it.
2026-09-03 02:59:42 +03:00
Karoy Lorentey e611f62e67 Disable _UniqueCollection fast paths in embedded Swift
As of 2026-09-01, conformance checks are now diagnosed as errors:

```
 70 |     // Fast paths for when we know elements are all unique
 71 |     if elements is _UniqueCollection {
    |                 `- error: cannot perform a dynamic cast to a type involving protocol '_UniqueCollection' in Embedded Swift
```
2026-09-01 10:31:54 -07:00
Anton Karpov c2b2092f94 Name the documented arguments the way the declarations name them
Twenty-five doc comments in the shipping modules name an argument that the
declaration below them does not have, so DocC has nothing to bind the
description to and drops it. Nothing warns about this.

Most of them are renames that the comment did not follow, and the file itself
usually holds the proof: RigidDeque.prepend says - maxCount while its own
Complexity line already says newItemCount, and append(copying:) has three
overloads where the oldest still takes newElements and the two newer ones take
items with the older one's wording.

Three entries name an argument that no longer exists at all and are removed
rather than renamed.
2026-08-13 16:29:06 +03:00
Karoy Lorentey 8380ca41da Merge pull request #682 from lorentey/container-updates
[ContainersPreview] Update Container protocols
2026-07-22 13:08:25 -07:00
Karoy Lorentey 90f26545ce Merge pull request #673 from wjdtjq6/fix/doc-comment-typos
Fix typos in doc comments and a DocC article
2026-07-07 15:09:13 -07:00
Karoy Lorentey bb0dc189ef maximumCount → maxCount
While we’re here, adjust `RigidSet.insert(maximumCount:initializingWith:)` and similar APIs to be consistent with RangeReplaceableContainer’s methods.
2026-07-07 14:21:53 -07:00
wjdtjq6 62a08e503e docs: fix typos in doc comments and DocC article 2026-07-02 21:17:11 +09:00
wjdtjq6 646274ed7c docs: fix superset set algebra comments 2026-06-23 13:21:36 +09:00
Karoy Lorentey e31c04143e Update CMake & Xcode build configurations 2026-06-05 18:45:56 -07:00
Karoy Lorentey 1447248b49 [BitCollections] BitArray.insert(repeating:count:at:): Fix bogus precondition 2026-05-01 14:34:51 -07:00
Karoy Lorentey cef6301d19 [BitCollections] BitSet.isSubset(of: Range<Int>): also look at elements above the range's upper word 2026-05-01 14:33:28 -07:00
Karoy Lorentey 084be39d7e [BitSet] Add makeIterator(from:)
This enables faster iteration over subranges of a BitSet than the `Slice` type’s default indexing iterator. (Depending on the fill factor, the speedup can be as high as 4x — not insignificant.)
2026-04-21 16:28:14 -07:00
Karoy Lorentey 80878519f2 [doc] Fix most issues reported by docc
DocC keeps changing its link syntax. The latest iteration appears to have trouble dealing with `Self`-taking or `Self`-returning methods, so change our API to replace `Self` with a direct mention of the concrete type. ¯\\\_(ツ)\_/¯

That said, the new compiler also found a large number of mismatching parameter names, and that was really helpful.
2026-03-09 14:14:51 -07:00
Karoy Lorentey 1c69635852 Add SPDX-License-Identifier tags 2026-03-05 19:39:24 -08:00
Karoy Lorentey d9b09ecde8 Update copyright dates 2026-03-05 19:39:20 -08:00
Karoy Lorentey 01661b6694 Merge pull request #541 from apple/doc-basic-span-index-mutation
Include notes about index mutation in `span(after/before:)` (+ other doc fixes)
2026-03-02 16:56:35 -08:00
Nate Cook 54ca53612f Include notes about index mutation in span(after/before:)
The indexes passed to span(after:) and friends on UniqueArray
and RigidArray are modified before return. This adds notes
about the updated values to the method documentation, along
with a few other minor formatting changes (dropping smart
quotes, single-sentence abstracts).
2026-03-02 16:38:48 -08:00
Karoy Lorentey 624bf2ce6a Merge pull request #538 from benrimmington/bitset-update
[BitSet] Amend return value of `update(with:)` method
2026-03-02 16:15:31 -08:00
Karoy Lorentey bf9a7033a0 [BasicContainers] Add early drafts for RigidSet/RigidDictionary 2026-02-16 17:15:59 -08:00
Karoy Lorentey 9503f8fe57 Improve consistency of precondition failure messages
More uniform message strings should feel better, and they should ever so slightly reduce code size.
2026-02-04 10:27:17 -08:00
Karoy Lorentey eac10abae2 Stop using @_exported import
- Stop using unstable import attributes with undefined/flaky semantics in package contexts.
- Freeze the contents of the Collections module. Do not make the new RigidDeque/UniqueDeque types from there, at least not yet. Replace reexported types with typealiases, and reexported protocol extensions with redefinitions forwarding to a common implementation in the original module.
2026-01-30 12:07:28 -08:00
Karoy Lorentey 8687ef52ea [BitCollections] Add missing imports for InternalCollectionsUtilities
Recent development compiler versions have started emitting errors for previously undiagnosed cases where a conformance in another module is referenced by a source file that does not itself explicitly import that module. Add the missing imports.
2025-12-11 14:49:27 -08:00
Ben Rimmington e2e2d00881 [BitSet] Amend return value of update(with:) method 2025-10-14 09:26:56 +01:00
Karoy Lorentey bb8d566833 Adopt package access modifier and get rid of gybbing 2025-09-29 11:56:14 -07:00
Karoy Lorentey e5577bb12b Update DocC documentation 2025-09-27 16:05:12 -07:00
faimin f6256df262 Add the missing macro condition when import InternalCollectionsUtilities 2025-07-30 14:44:22 +08:00
Tony Parker c883a1729a Add support for embedded Swift mode
Remove calls to `debugPrint` (which does not exist), and ifdef out support for `Codable` and `Reflection`.
2025-07-17 16:36:56 -07:00
Karoy Lorentey 6819c6d149 Enable MemberImportVisibility and fix issues uncovered 2025-05-20 18:11:44 -07:00
LamTrinh.Dev 7f49fa5164 Add more file in Sources/BitCollections/CMakeLists.txt 2024-09-04 18:18:09 +07:00
Jeremy Schonfeld 3e120b48bb [CMake] Reduce path lengths in single-module build (#392)
* Eliminate relative paths from the cmake single-module build

* Attempt to reduce length of paths in single module build
2024-06-26 08:39:11 -07:00
Jeremy Schonfeld ee97538f5b Add Single Module Build Mode to CMake for Foundation (#385)
* Add new single-module and foundation-toolchain-module modes to CMake build

* Fix allowable client flag syntax
2024-06-03 16:15:50 -07:00
Karoy Lorentey 35d5746117 Rename _CollectionsUtilities to InternalCollectionsUtilities
We are forced to do this due to an Xcode issue (#364) with underscored module names.

This module remains unstable, despite the removal of the underscore. Directly importing it from outside the package remains unsupported. This module and/or its entire contents may go away or change in incompatible ways in any future swift-collections release.
2024-05-29 14:00:13 -07:00
Karoy Lorentey d45ccb0028 [BitSet] Fix missing import 2024-01-31 19:34:37 -08:00
Karoy Lorentey a0da2df799 [BitArray] Update LosslessStringConvertible initializer to accept new description format 2024-01-31 19:34:36 -08:00
Karoy Lorentey ae641c3d5d [BitArray] Fix description implementation; update tests 2024-01-31 19:34:36 -08:00