199 Commits
Author SHA1 Message Date
Karoy Lorentey 8f033f1450 MutableContainer.updateElements: Keep consistent with MutableSpan proposal 2026-11-16 11:35:33 -08:00
Karoy Lorentey 88754449ab Merge pull request #845 from aashish254/codex/812-container-iterator-boundary
Fix ContainerIterator skip bounds
2026-11-10 11:16:20 -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
Aashish fc11462e69 Fix ContainerIterator skip bounds 2026-11-09 21:42:36 +05:45
Karoy Lorentey daeac4ebb8 Stop catering to toolchains older than Swift 6.2 2026-11-05 17:40:50 -08:00
Karoy Lorentey 7b578e5bfb Review and fix filter implementations
- Define a separate `filter` result on Iterable vs BorrowingIteratorProtocol
- Fix handling of delimited iterators in Container.filter
- Add fixmes for throwing
- Inlinability and other small fixes
2026-11-04 18:28:38 -08:00
Joseph CursioandClaude Opus 5.5 c1ff9b9063 Build RigidArray's consumeLast drain without recursing
RigidArray's _customConsumeLast(_:) hook called consumeLast(_:), but
RigidArray has no one-argument consumeLast of its own, so the call went
to DrainableContainer.consumeLast(_:), which starts by calling the
hook. Every call to consumeLast(_:) on a RigidArray, directly or
through generic code, recursed until the stack overflowed.

Have the hook check the count and return consumeSubrange(_:) over the
last n items directly, the way consumeLast(_:consumingWith:) does.

Fixes #814.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
2026-11-03 19:16:00 -06:00
Karoy Lorentey b14ab924a5 Fix PermutableContainer algorithms 2026-11-03 16:04:44 -08:00
e7d8cd2203 [ContainersPreview] Fix append(copying:) recursion and wrapped insert(copying:at:) (#819)
* [ContainersPreview] Fix append(copying:) recursion and wrapped insert(copying:at:)

The RangeReplaceableContainer extension's append(copying:) passed a
contiguous source's buffer back to itself and never returned.
_insertCollection copied the whole buffer on every initializer call, which
trapped when a deque's gap wrapped around the end of its storage. Copy only
what fits on each call, as replaceSubrange(_:copying:) already does.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

* Delete Tests/DequeTests/RangeReplaceableContainerCopyingTests.swift

Let's drop the tests for now; we'll need a less involved way to exercise such algorithms.

---------

Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>
Co-authored-by: Karoy Lorentey <klorentey@apple.com>
2026-11-03 14:57:43 -08:00
Karoy Lorentey e6196f9c7a Merge pull request #797 from aashish254/cmake-add-rigidset-extras
[ContainersPreview] Add missing RigidSet+Extras.swift to CMake source list
2026-10-22 16:00:28 -07:00
SwastikTripathi 0b51424337 Merge pull request #794 from SwastikTripathi/fix/borrowing-map-skip-infinite-loop
[BorrowingMapProducer] Fix skip(by:) hanging at end of iterator
2026-10-22 11:02:24 -07:00
Aashish b84aa036f3 ContainersPreview: Add missing RigidSet+Extras.swift to CMake source list 2026-10-22 14:49:35 +05:45
Karoy Lorentey bbdd37ada7 Fix a variety of issues in the nextSpan/previousSpan method family 2026-10-21 19:56:55 -07:00
Karoy Lorentey 1e51781091 UniqueSet.init(minimumCapacity:from:): Make sure we allocate storage for at least minimumCapacity items 2026-10-21 17:29:42 -07:00
Karoy Lorentey abddfb7ced Producer.map: Saturate generate(into:) target 2026-10-21 17:29:03 -07:00
Karoy Lorentey fcca0e3e2b Producer.filter: Saturate generate(into:) target, and fix underestimatedCount 2026-10-21 17:28:42 -07:00
Karoy Lorentey c314bdad78 Producer.skip(by:): Don’t skip fewer than n items unless we reach the end 2026-10-21 17:27:51 -07:00
Karoy Lorentey bf9b4623a1 UniqueDeque.prepend: Add perf FIXME 2026-10-21 16:04:49 -07:00
Swastik TripathiandClaude Opus 5.5 5d4a707373 [UniqueDeque] Fix prepend(from:) reversing batch order when producer needs multiple passes
prepend(from:) looped calling uncheckedPrepend, which each time placed the
new batch at index 0 of the deque. Later batches ended up in front of earlier
ones, producing items in the wrong order.

Fix: use uncheckedInsert(addingCount:at:added) so each new batch is inserted
immediately after the items already prepended in earlier passes. Promote the
overload from internal to package so ContainersPreview can reach it.

Adds a regression test covering single- and multi-batch producers prepending
into empty and non-empty deques. Fixes #763.

Co-Authored-By: Claude Opus 5.5 (1M context) <noreply@anthropic.com>
2026-10-19 08:35:03 +05:30
Karoy Lorentey 35aedf3937 Remove unnecessary explanation 2026-10-12 11:29:41 -07:00
hamedandCursor a4f5085a7c Copy every source span in replaceSubrange(copying:).
The replacement callback took a single span and then required the source count to be exhausted, so a container stored in more than one span trapped.

Fixes #751

Co-authored-by: Cursor <cursoragent@cursor.com>
2026-10-10 22:56:07 +03:30
Karoy Lorentey 463946edae ContainersPreview: Adjust import statements in Foundation toolchain module mode 2026-10-08 18:32:47 -07:00
Karoy Lorentey 9cabf522ec CMake: Fix building ContainersPreview as a Foundation toolchain module 2026-10-08 18:32:15 -07:00
Karoy Lorentey d07dc32dfa Sources: Add unsafe keywords where needed 2026-10-01 11:14:29 -07:00
Karoy Lorentey 44b674265c Update import statements 2026-09-29 15:41:05 -07:00
Karoy Lorentey 1be474f795 Xcode, CMake: Spin off ContainersPreview into its own target 2026-09-29 15:41:03 -07:00
Karoy Lorentey e2c040bcaa BorrowingIteratorProtocol.map: Hide map2 and map3 behind underscores
`map2` and `map3` are merely illustrating problems with the throwing Iterable in higher-order functions in Swift 6.4; they aren’t really suitable for exposing as API, even behind a package trait.
2026-09-22 19:04:12 -07:00
Karoy Lorentey 2dcded505e Stop shipping retroactive Iterable conformances on standard types 2026-09-22 19:04:09 -07:00
Karoy Lorentey 9bf8a9763b Merge pull request #729 from lorentey/release-prep
1.7.0 release preparations
2026-09-22 12:42:05 -07:00
Karoy Lorentey 537bf9cbfb Drop support for Swift 6.0 and 6.1
This allows the use of Span types without `#if compiler` guards.
2026-09-21 13:34:39 -07:00
Karoy Lorentey 8e4f078441 Producer.generate(into:): Switch to saturating semantics
This noticeable simplifies client code, as clients invariably want to fully populate their buffer (when possible). It also is consistent with the semantics of `Iterable.skip(by:)`.
2026-09-21 13:07:01 -07:00
Karoy Lorentey 45e7f63387 Merge pull request #725 from eliorpom-cmd/fix-typos-20260918
Fix typos in documentation and comments
2026-09-21 12:54:16 -07:00
Karoy Lorentey b2424210b4 Container: Reinstate requirement for Comparable indices
I have a linked list prototype that can support comparable indices (and an O(1) `count`); accordingly, reinstate the requirement for index comparability. This eliminates a potential performance footgun for custom containers that define their own Index, as an incomparable index would make `func distance` 2x slower.
2026-09-21 10:41:46 -07:00
Karoy Lorentey d392f0cbff MutableContainer: Add tests; resolve issues uncovered 2026-09-21 09:54:29 -07:00
Elior Pommier cabf7390ce Fix typos in documentation and comments
Corrects 25 misspellings across DocC articles, design documentation and doc
comments. Prose only: no identifiers, no public API, no behaviour change.

| Typo | Correction | Count |
|---|---|---|
| `offseting` | `offsetting` | 7 |
| `valud` | `value` | 4 |
| `necessarilly` | `necessarily` | 3 |
| `recommmend` | `recommend` | 2 |
| `Mutablility` | `Mutability` | 1 |
| `childs` | `child's` | 1 |
| `constaints` | `constraints` | 1 |
| `destintion` | `destination` | 1 |
| `explan` | `explain` | 1 |
| `forcuses` | `focuses` | 1 |
| `ot` | `or` | 1 |
| `succcess` | `success` | 1 |
| `unqiue` | `unique` | 1 |

Two of these are worth a second look, since they are not pure spelling:

- `_HTable+Removal.swift:18` reads "without marking it as unoccupied ot
  restoring the hash table's other invariants". Read as `or`, matching the
  sentence, and deliberately not as a prefix of `other` later on the line.
- `_Node.UnsafeHandle+Deletion.swift:369` reads "reuse the left childs node".
  Corrected to the possessive `child's` rather than `children`, which is what
  a plain spellchecker suggests but does not fit the sentence.

`valud` is corrected to `value` to match the wording of the equivalent
parameter documentation on `swapAt(_:_:)`.

One change is outside documentation: `CheckContainer.swift:476` fixes
`succcess` inside a test assertion message. It is a human-readable string, not
an expected value, so no test behaviour changes.

Deliberately left alone:

- `isDisjoint(with:)-54iy6` in `OrderedSet.md` is a DocC disambiguation hash,
  not a misspelling.
- `Peristent` in the 2022 ShareableHashedCollections review document, which is
  an archived record of a past review rather than living documentation.

Found with `typos-cli`, then reviewed by hand; the tool's raw output also
flagged identifiers and symbol hashes, which are not included here.
2026-09-18 14:31:47 +02:00
Karoy Lorentey 4ea0e4443d MutableContainer: Also add copying variants of bulk updates 2026-09-16 20:44:13 -07:00
Karoy Lorentey c031de73d0 MutableContainer: Add some bulk update operations 2026-09-16 19:58:28 -07:00
Karoy Lorentey 5cebba6f29 Refactor DrainableContainer/RangeReplaceableContainer/DynamicContainer
Range replacement operations generally need to invalidate all indices, and that means that we lose our position in the container after each insertion/removal, unless we happen to be using a container with looser index invalidation (such as arrays or deques).

A linked list is an example for a container type where insertions/removals need to invalidate all indices — as we need to track index validation using a single version counter that is stored in the list’s head. However, it would not be acceptable to lose our place whenever we insert a new item to the list; therefore, to mitigate the validation issue, this commit changes all range-replacement operations to return a valid index range to the affected items in the container.

This is a radical break from `RangeReplaceableCollection`. It fixes a long-standing defect with it, but it also makes it tricky to conform the same type to both protocol families, as the two require the “same” methods to return different types (`Void` vs `Range<Index>`).

Given that the LSG has intentionally diverged `UniqueArray.removeAll()` from RangeReplaceableCollection semantics, I expect this isn’t going to be an issue. For example, types with existing collection conformances can expose container views, mitigating such semantic differences.

To allow SubrangeConsumers to work without losing position, add a new protocol, `ContainerDrain` with a consuming `finalize` operation that returns a valid index in the resulting container state.

While we’re here, apply the API tweaks from SE-0527:
- Revert the `replace(removing:…:)` names, rolling back to `replaceSubrange(_:…:)` .
- Similarly, rename `consume(_:)` → `consumeSubrange(_:)`
- Rename `reallocate(capacity:)` → `setCapacity(_:)`.
2026-09-14 20:37:12 -07:00
Karoy Lorentey 225bd07e56 RigidSet, UniqueSet: Add Container conformance 2026-09-01 09:34:05 -07:00
Karoy Lorentey 842f125c47 Invert dependencies to ContainersPreview, moving all container APIs there
- Move `InputSpan` into its own module, `SpanPreview`. Add dependencies to it.
- Invert dependencies to `ContainersPreview`, so that no production target imports it, but it now depends on its previous dependents.
- Move all generic APIs and conformances using `Producer`/`Drain`/`Container` to the `ContainersPreview` module.
- Remove `UnstableContainersPreview` conditions around `Iterable` APIs

In summary, importing `BasicContainers` and `DequeModule` continue to get us the basic definitions for `RigidArray`, `UniqueSet`, `RigidDeque` etc., without most of their unstable APIs. (With the exception of core APIs that require `InputSpan`.)

To get any API that uses an unstable protocol like `Container` or `Drain`, we’ll now need to import `ContainersPreview` in addition to the type-defining module.

This will provide a slightly less horrible migration path when (if) the container/producer protocol family gets adopted/adapted into the stdlib.
2026-08-25 18:29:58 -07:00
Karoy Lorentey 1574bed0dc [ContainersPreview] Spin off removal/consumption operations from RangeReplaceableContainer into a new DrainableContainer protocol
We have types that can usefully conform to `DrainableContainer` but not the full `RangeReplaceableContainer`; `OrderedSet` is one obvious example.
2026-08-25 14:10:06 -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 2e10584446 Add a default implementation for MutableContainer.swapAt (for copyable elements) 2026-07-28 19:43:07 -07:00
Karoy Lorentey ec66640a15 Add some (untested) PermutableContainer algorithms 2026-07-28 19:43:07 -07:00
Karoy Lorentey fbe36a7af5 Rearrange Sources/ContainersPreview/Protocols/* 2026-07-28 19:43:06 -07:00
Karoy Lorentey 669eb09cea Use Iterable from the Standard Library, replacing the local definition 2026-07-27 13:32:46 -07:00
Karoy Lorentey 6b76536758 BidirectionalContainer: don’t re-declare distance(from:to:) as a non-overriding method
The original `Container` requirement is defined with the same semantics.
2026-07-22 19:07:41 -07:00
Karoy Lorentey 58e13a0525 Stop requiring BidirectionalContainer to provide comparable indices
This allows doubly linked lists to conform to the protocol.
2026-07-22 19:07:13 -07:00
Karoy Lorentey 06f6b6bf49 Use borrow & mutate accessors in InputSpan’s unchecked subscript 2026-07-21 16:32:03 -07:00
Karoy Lorentey 232dc7f9ee Add second parameter to Container.makeBorrowingIterator(from:to:) 2026-07-21 15:21:45 -07:00