restricting AnySequence.init


(Maxim Moiseev) #1

Hi all,

Here is the proposal to add more constraints to AnySequence.init in order to implement delegation of method calls to the underlying SequnceType implementation.
https://github.com/moiseev/swift-evolution/blob/restricted-anyseq/proposals/0008-constrained-AnySequence.md

(Including full text of the proposal at the bottom for your convenience).

Final goal would be to eventually properly delegate all the calls to `SequenceType` and `CollectionType` methods inside `AnySequence` and `Any${Traversal}Collection`.

Any thoughts and comments are welcome (not creating a PR just yet).

max

Constraining AnySequence.init

Proposal:
SE-0008 <https://github.com/apple/swift-evolution/blob/master/proposals/0008-constrained-AnySequence.md>
Author(s): Max Moiseev <https://github.com/moiseev>
Status: Review
Review manager: TBD
<https://github.com/moiseev/swift-evolution/blob/restricted-anyseq/proposals/0008-constrained-AnySequence.md#introduction>Introduction

In order to allow AnySequence delegate calls to the underlying sequence, its initializer should have extra constraints.

<https://github.com/moiseev/swift-evolution/blob/restricted-anyseq/proposals/0008-constrained-AnySequence.md#motivation>Motivation

At the moment AnyCollection does not delegate calls to SequenceType protocol methods to the underlying base sequence, which results in dynamic downcasts in places where this behavior is needed (see default implementations ofSequenceType.dropFirst or SequenceType.prefix). Besides, and this is even more important, customized implementations of SequenceType methods would be ignored without delegation.

<https://github.com/moiseev/swift-evolution/blob/restricted-anyseq/proposals/0008-constrained-AnySequence.md#proposed-solution>Proposed solution

See the implementation in this PR <https://github.com/apple/swift/pull/220>.

In order for this kind of delegation to become possible, _SequenceBox needs to be able to 'wrap' not only the base sequence but also it's associated SubSequence. So instead of being declared like this:

internal class _SequenceBox<S : SequenceType>
    : _AnySequenceBox<S.Generator.Element> { ... }
it would become this:

internal class _SequenceBox<
  S : SequenceType
  where
    S.SubSequence : SequenceType,
    S.SubSequence.Generator.Element == S.Generator.Element,
    S.SubSequence.SubSequence == S.SubSequence

: _AnySequenceBox<S.Generator.Element> { ... }

Which, in it's turn, will lead to AnySequence.init getting a new set of constraints as follows.

Before the change:

public struct AnySequence<Element> : SequenceType {
  public init<
    S: SequenceType
    where
      S.Generator.Element == Element
  >(_ base: S) { ... }
}
After the change:

public struct AnySequence<Element> : SequenceType {
  public init<
    S: SequenceType
    where
      S.Generator.Element == Element,
      S.SubSequence : SequenceType,
      S.SubSequence.Generator.Element == Element,
      S.SubSequence.SubSequence == S.SubSequence
  >(_ base: S) { ... }
}
These constraints, in fact, should be applied to SequenceType protocol itself (although, that is not currently possible), as we expect every SequenceType implementation to satisfy them already.

<https://github.com/moiseev/swift-evolution/blob/restricted-anyseq/proposals/0008-constrained-AnySequence.md#impact-on-existing-code>Impact on existing code

New constraints do not affect any built-in types that conform to SequenceType protocol as they are essentially constructed like this (SubSequence.SubSequence == SubSequence). 3rd party collections, if they use the default SubSequence (i.e. Slice), should also be fine. Those having custom SubSequences may stop conforming to the protocol.


(Dmitri Gribenko) #2

Thanks, Max!

I reviewed this proposal with Max offline and it LGTM. The biggest
question that we have to answer is if this change is small enough to be
included in Swift 2.2. I would say yes, since the only collections that
are affected by this change are collections that we don't consider valid,
where the author went an extra mile to declare an improper SubSequence type
-- and they would stop working anyway once we can constrain the SubSequence
the way we want.

What does everyone think?

Dmitri

···

On Mon, Dec 7, 2015 at 12:43 PM, Maxim Moiseev via swift-evolution < swift-evolution@swift.org> wrote:

Hi all,

Here is the proposal to add more constraints to AnySequence.init in order
to implement delegation of method calls to the underlying SequnceType
implementation.

https://github.com/moiseev/swift-evolution/blob/restricted-anyseq/proposals/0008-constrained-AnySequence.md

(Including full text of the proposal at the bottom for your convenience).

Final goal would be to eventually properly delegate all the calls to
`SequenceType` and `CollectionType` methods inside `AnySequence` and
`Any${Traversal}Collection`.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Andrew Bennett) #3

+1 looks good to me, I also feel like this is an important bug fix. It
would be nice if Swift had some kind of automatic process for type erasure
that delegates all calls the the underlying implementation.

As a more concrete example for why this is important, try running these two
lines in a playground:

print(Array((0...1000000000).suffix(2)))
print(Array(AnySequence(0...1000000000).suffix(2)))

The second line will take a very long time to run.

···

On Tue, Dec 8, 2015 at 7:50 AM, Dmitri Gribenko via swift-evolution < swift-evolution@swift.org> wrote:

On Mon, Dec 7, 2015 at 12:43 PM, Maxim Moiseev via swift-evolution < > swift-evolution@swift.org> wrote:

Hi all,

Here is the proposal to add more constraints to AnySequence.init in order
to implement delegation of method calls to the underlying SequnceType
implementation.

https://github.com/moiseev/swift-evolution/blob/restricted-anyseq/proposals/0008-constrained-AnySequence.md

(Including full text of the proposal at the bottom for your convenience).

Final goal would be to eventually properly delegate all the calls to
`SequenceType` and `CollectionType` methods inside `AnySequence` and
`Any${Traversal}Collection`.

Thanks, Max!

I reviewed this proposal with Max offline and it LGTM. The biggest
question that we have to answer is if this change is small enough to be
included in Swift 2.2. I would say yes, since the only collections that
are affected by this change are collections that we don't consider valid,
where the author went an extra mile to declare an improper SubSequence type
-- and they would stop working anyway once we can constrain the SubSequence
the way we want.

What does everyone think?

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution