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
We trust the internal implementation of the stdlib to not cause any unintentional buffer overflows.
In such cases we can use the "unprotected" address-to-pointer conversions.
This avoids inserting stack protections where it's not needed.
* First draft of incorporating material from #38891
* Apply suggestions from Alex's review
Co-authored-by: Alex Martini <amartini@apple.com>
* Rephrase suggested by Alex.
* Remove redundancy re: "don't replace buffer".
* Apply changes from editorial review.
* Apply Sequence edits (a3a3ff1) to MutableCollect'n
* Remove errant space.
Co-authored-by: Guillaume Lessard <glessard@users.noreply.github.com>
Co-authored-by: Chris Adamson <cadamson@apple.com>
Co-authored-by: Alex Martini <amartini@apple.com>
Co-authored-by: Guillaume Lessard <glessard@users.noreply.github.com>
- clarify the requirement that the entire collection must be accessible
- clarify the requirement surrounding subsequences / slices
- add parameter descriptions
- specify that buffer cannot be replaced
- add a default implementation of MutableCollection’s
subscript(bounds: Range<_>) with the most general signature possible
- it is marked unavailable in order to prevent the
infinite recursion bug reported in SR-14848
- add a conditionally-available subscript(bounds: Range<_>) -> Slice<Self>
only when Subsequence is Slice<Self>. This will supersede
the unconditional extension that provides the same signature.
* [stdlib] Deprecate MutableCollection._withUnsafeMutableBufferPointerIfSupported
In Swift 5.0, [SE-0237] introduced the public `MutableCollection.withContiguousMutableStorageIfAvailable` method. It’s time we migrated off the old, underscored variant and deprecated it.
The default `MutableCollection.sort` and `.partition(by:)` implementations are currently calling this hidden method rather than the documented interface, preventing custom Collection implementations from achieving good performance, even if they have contiguous storage.
[SE-0237]: https://github.com/apple/swift-evolution/blob/master/proposals/0237-contiguous-collection.md
* [test] Update tests for stdlib behavior changes
* Update stdlib/private/StdlibCollectionUnittest/CheckMutableCollectionType.swift
Co-authored-by: Nate Cook <natecook@apple.com>
* Update stdlib/private/StdlibCollectionUnittest/CheckMutableCollectionType.swift
Co-authored-by: Nate Cook <natecook@apple.com>
* Apply suggestions from code review
Co-authored-by: Nate Cook <natecook@apple.com>
* [test] LoggingMutableCollection: Fix logging targets
* [stdlib] Fix warning by restoring original workaround
Co-authored-by: Nate Cook <natecook@apple.com>
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.
Most of the stdlib's properties don't need @_borrowed because they're
@inlinable, but I did find one place in an overlay where it's probably
sensible to make the operation use generalized accessors even if
they're resilient.
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.
* [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
* Refactor Indices and Slice to use conditional conformance
* Replace ReversedRandomAccessCollection with a conditional extension
* Refactor some types into struct+extensions
* Revise Slice documentation
* Fix test cases for adoption of conditional conformances.
* [RangeReplaceableCollection] Eliminate unnecessary slicing subscript operator.
* Add -enable-experimental-conditional-conformances to test.
* Gruesome workaround for crasher in MutableSlice tests
The various _*Indexable protocols only exist to work around the lack of
recursive protocol constraints. Eliminate all of the *_Indexable protocols,
collapsing their requirements into the corresponding Collection protocol
(e.g., _MutableIndexable —> Collection).
This introduces a number of extraneous requirements into the various
Collection protocols to work around bugs in associated type
inference. Specifically, to work around the lack of "global" inference
of associated type witnesses. These hacks were implicitly present in
the *Indexable protocols; I've made marked them as ABI FIXMEs here so
we can remove them when associated type inference improves.
Fixes rdar://problem/21935030 and a number of ABI FIXMEs in the library.
Introduce (recursive) constraints that make the *Collection constraint
of SubSequence match that of its enclosing *Collection, e.g.,
MutableCollection.SubSequence conforms to MutableCollection.
Fixes rdar://problem/20715031 and more of SR-3453.
* Give Sequence a top-level Element, constrain Iterator to match
* Remove many instances of Iterator.
* Fixed various hard-coded tests
* XFAIL a few tests that need further investigation
* Change assoc type for arrayLiteralConvertible
* Mop up remaining "better expressed as a where clause" warnings
* Fix UnicodeDecoders prototype test
* Fix UIntBuffer
* Fix hard-coded Element identifier in CSDiag
* Fix up more tests
* Account for flatMap changes
