[SR-3453] Enforce appropriate constraints on Sequences and Collections

[airspeedswift]

Previous ID	SR-3453
Radar	rdar://problem/31411212
Original Reporter	@airspeedswift
Type	Improvement
Status	Resolved
Resolution	Done

Additional Detail from JIRA

Votes	0
Component/s	Standard Library
Labels	Improvement, AffectsABI, swift-evolution-proposal-needed
Assignee	@airspeedswift
Priority	Medium

md5: 6d5849c6136f3cb3c380bcd6362f6e00

Issue Description:

Once it is possible in the language (dependent on associated types with where clauses and recursive protocol constraints), the following rules should be enforced:

• Iterator should be a Sequence

• Sequence.Iterator.Element should become Sequence.Element

• Sequence.SubSequence must be a Sequence

• Sequence.SubSequence.Element must be same type as Sequence.Element

• Collection.SubSequence.Index should be same type as Collection.Index

• BidirectionalCollection.SubSequence should be a BidirectionalCollection

• RandomAccessCollection.SubSequence should be a RandomAccessCollection

• RangeReplaceableCollection.SubSequence should be a RangeReplaceableCollection

• Collection.Indices should be a Collection

• Collection.Indices.Index should be same type as Collection.Index

• Collection.SubSequence.Indices should be same type as Collection.Indices

Enforcing these rules will massively simplify the writing of generic collections, including several instances in the standard library. See most entries marked FIXME(ABI) with (Associated Types with where clauses) or (Recursive Protocol Constraints) for examples.

[bob-wilson]

@swift-ci create

[airspeedswift]

Progress so far:

• [Stdlib] Use associated type where clauses to address various ABI FIXMEs. #8593

• [Stdlib] For Collections, the SubSequence of a Subsequence is SubSequence #8888

• [Stdlib] For Collections, the SubSequence of a Subsequence is SubSequence #8888

• [stdlib] Add Collection constraints via protocol where clauses #9374

[DougGregor]

Several of these were addressed by #11769

• Sequence.SubSequence must be a Sequence

• Sequence.SubSequence.Element must be same type as Sequence.Element

[DougGregor]

#11918 adds:

• Collection.Indices should be a Collection

• BidirectionalCollection.Indices should be a BidirectionalCollection

• RandomAccessCollection.Indices should be a RandomAccessCollection

• Collection.Indices.Index should be same type as Collection.Index

[DougGregor]

#11899 adds:

• Collection.SubSequence should be a Collection

• BidirectionalCollection.SubSequence should be a BidirectionalCollection

• RandomAccessCollection.SubSequence should be a RandomAccessCollection

• MutableCollection.SubSequence should be a MutableCollection

• RangeReplaceableCollection.SubSequence should be a RangeReplaceableCollection

[DougGregor]

I believe that the following need more design discussion and should be split out into a separate proposal if we're going to do them:

• Iterator should be a Sequence

• Collection.SubSequence.Indices should be same type as Collection.Indices

Everything else listed above was already taken care of by @airspeedswift's work. The second of them, for example, means that all of the ``Default*Indices`` types need to use

public typealias Indices = Base.Indices

Which feels a little awkward.

[DougGregor]

24821cc