Doc comments for DiscontiguousSlice, MutableCollection, RangeSet, and
RangeReplaceableCollection all refer to a Collection method subranges(where:)
which is intended to return a RangeSet of matching ranges. I believe this is
likely an old or formerly-contemplated spelling of the method now known as
indices(where:). This commit changes "subranges" to "indices".
* Adds RangeSet/DiscontiguousSlice to the stdlib
* Remove redundant DiscontiguousSlice.Index: Comparable conformance
* Attempt to fix embedded build
* Attempt to fix macOS test failures
* Fix Constaints/members.swift failure on linux
* Add exceptions to ABI/source checker to fix macOS tests
* Fix incremental dependency test failure
* Remove inlining/unfreeze implementation for future improvements
* Simplify indices(where:) implementation
* Address review feedback
* Add test for underscored, public slice members
* Address feedback on inlining, hashing, and initializing with unordered arrays
* Fix ABI checker issues
* Remove MutableCollection extension for DiscontiguousSlice
* Make insertion return a discardable Bool
* Fix ABI checker tests
* Fix other ABI checker tests due to dropping MutableCollection subscript
This adds the RangeSet and DiscontiguousSlice types, as well as collection
operations for working with discontiguous ranges of elements. This also adds
a COWLoggingArray type to the test suite to verify that mutable collection
algorithms don't perform unexpected copy-on-write operations when mutating
slices mid-operation.
Without this change, SILGen will crash when compiling a use of the
derived protocol's requirement: it will instead attempt to use
the base protocol's requirement, but the code will have been
type-checked incorrectly for that.
This has a potential for source-compatibility impact if anyone's
using explicit override checking for their protocol requirements:
reasonable idioms like overriding a mutating requirement with a
non-mutating one will no longer count as an override. However,
this is arguably a bug-fix, because the current designed intent
of protocol override checking is to not allow any differences in
type, even "covariant" changes like making a mutating requirement
non-mutating. Moreover, we believe explicit override checking in
protocols is quite uncommon, so the overall compatibility impact
will be low.
This also has a potential for ABI impact whenever something that
was once an override becomes a non-override and thus requires a
new entry. It might require a contrived test case to demonstrate
that while using the derived entry, but it's quite possible to
imagine a situation where the derived entry is not used directly
but nonetheless has ABI impact.
Furthermore, as part of developing this patch (earlier versions of
which used stricter rules in places), I discovered a number of
places where the standard library was unintentionally introducing
a new requirement in a derived protocol when it intended only to
guide associated type deduction. Fixing that (as I have in this
patch) *definitely* has ABI impact.
Now that we have removed overriding protocol requirements from witness
tables, they no longer have any effect on the ABI. Replace the FIXME
(ABI) comments with normal FIXMEs: there is no more ABI work to do
here.
Add the `-warn-implicit-overrides` flag when building the standard library
and overlays, so that each protocol member that overrides a member of an
inherited protocol will produce a warning unless annotated with either
‘override’ or ‘@_nonoverride’.
An annotation of `override` will mean that the overriding requirement will be treated identically to the overridden declaration. If for some reason a concrete type’s conformance to the inheriting protocol provides a different witness for the overriding requirement than the conformance to the inherited protocol’s witness for the overridden requirement, the witness for the inheriting (more-specialized) protocol will be ignored. A protocol requirement marked ‘override’ only makes sense when the declaration is needed to help associated type inference, which is why the ‘override’ annotations correlate so closely with ABI FIXMEs.
An annotation of `@_nonoverride` means that the two protocol requirements will be treated independently, and may be bound to different witnesses. Use `@_nonoverride` when we might need different witnesses, e.g., because the semantics of the potentially-overriding declaration differ from that of the potentially-overridden declaration. `BidirectionalCollection.index(_:offsetBy:)` is the most obvious example, because the `BidirectionalCollection` ’s version of `index(_:offsetBy:)` allows negative indices. `RandomAccessCollection` ’s version is also marked `@_nonoverride` because it is required to be asymptotically faster than the `Collection` or `BidirectionalCollection` versions.
* Document that removeAll(where:) doesn't reorder the remaining elements.
Per Swift Forums discussion on the topic:
"Does removeAll(where:) on arrays guarantee preserved order of elements?"
* Copy docs from the first default impl up to the protocol requirement.
Per Nate's feedback on PR#18803.
The protocol requirement was missing a few extra sentences and a
code example.
* Fix a code example that would fail to remove negative odd integers.
Per feedback on the forums from Jens,
swap `== 1` with `!= 0` so that negative odd numbers would be
removed, too, if the example were modified to include some negative
numbers in the input array.
* [stdlib] Update complexity docs for seq/collection algorithms
This corrects and standardizes the complexity documentation for Sequence
and Collection methods. The use of constants is more consistent, with `n`
equal to the length of the target collection, `m` equal to the length of
a collection passed in as a parameter, and `k` equal to any other passed
or calculated constant.
* Apply notes from @brentdax about complexity nomenclature
* Change `n` to `distance` in `index(_:offsetBy:)`
* Use equivalency language more places; sync across array types
* Use k instead of n for parameter names
* Slight changes to index(_:offsetBy:) discussion.
* Update tests with new parameter names
We would like to eventually extend Array, Dictionary, and Set to support move-only element types when the language does. To that end, we need to get the `consuming`-ness of protocol requirements on Sequence, Collection, and related protocols right for forward compatibility so that a future version of Swift that extends these types to support move-only data structures remains ABI- and API-compatible with older versions of the language. Mark requirements as `__consuming` where it would be necessary for a move-only implementation of one of these types.
This includes various revisions to the APIs landing in Swift 4.2, including:
- Random and other randomness APIs
- Hashable changes
- MemoryLayout.offset(of:)
- Make RawRepresentable Codable abstracts distinguishable
- Make the UnboundedRange example a little more user friendly
- Correct the RangeReplaceableCollection example description
- Revise CaseIterable discussion
* Eradicate IndexDistance associated type, replacing with Int everywhere
* Consistently use Int for ExistentialCollection’s IndexDistance type.
* Fix test for IndexDistance removal
* Remove a handful of no-longer-needed explicit types
* Add compatibility shims for non-Int index distances
* Test compatibility shim
* Move IndexDistance typealias into the Collection protocol
