As discussed on the forum, `BidirectionalCollection` requirements as
currently stated can be interpreted to forbid conforming types from
accepting indices that lie between valid (i.e., reachable) indices
in the collection. Among other undesirable effects, this
interpretation would render SE-0180 (String.Index overhaul)
incompatible with these requirements.
Update the wording to clarify that the requirements only apply to
valid indices. (Collection protocols do not constrain the behavior of
invalid indices — it’s up to individual collection types to implement
them as they wish.)
https://forums.swift.org/t/string-index-unification-vs-bidirectionalcollection-requirements/55946
rdar://92297280
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.
* [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
If a type conditionally conforms to BidirectionalCollection, suffix's (and the
others) use of `index` ends up dispatching through `Collection.index` seemingly
because it is a protocol requirement. The intended function is
BidirectionalCollection's overloaded `index` (which _isn't_ connected to a
protocol requirement), which is called for non-conditional conformances. As
such, this is a work-around to stop code crashing.
Noticed in SR-8022, rdar://problem/41216424.
Refactor out the implementation of index(_:offsetBy) and others from
BidirectionalCollection so that conformers can choose to invoke the
default implementations explicitly. This is very useful for types such
as String which have common fast-paths to check before falling back on
the general approach.
* 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
* 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.
Make the Indices types conform to the appropriate Collection protocol:
* Collection.Indices: Collection
* BidirectionalCollection.Indices: BidirectionalCollection
* RandomAccessCollection.Indices: RandomAccessCollection
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.
* Unify the capitalization across all user-visible error messages (fatal errors, assertion failures, precondition failures) produced by the runtime, standard library and the compiler.
* Update some more tests to the new expectations.
* 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
There isn't any work related to SE-0142 associated type where clauses
for these particular ABI FIXMEs. Rather, we get all of the constraints
we need from Collection and the recursive constraint we cannot yet
express, all of which are covered by other ABI FIXMEs.
The BidirectionalCollection protocol has no requirements that mention
the associated type 'SubSequence', which means it cannot be easily
inferred. Duplicate the subscript requirement from Collection into
BidirectionalCollection to aid type witness inference.
It's important to let people know that, in contrast with existing
practice in other frameworks, we really are going to remove the
deprecated API, and soon.
This resolves the issue described in SR-1922, where conformance
to a bidirectional collection gives errors when implemented using
only the minimal protocol requirements.
