Should non-final classes be allowed to conform to Collection?

Hi all,

Consider this code,

class Base : Collection {
  var startIndex: Int { return 0 }

  var endIndex: Int { return 10 }

  func index(after i: Int) -> Int { return i + 1 }

  subscript(index: Int) -> Int { return index }
}

We infer the associated type ‘Iterator’ as ‘IndexingIterator<Base>’. I can use an instance of Base as a sequence just fine:

for x in Base() {} // OK

Now if I subclass Base, the associated type is still ‘IndexingIterator<Base>’:

class Derived : Base {}

However the implementation of makeIterator is defined in a constrained extension by the standard library,

extension Collection where Self.Iterator == IndexingIterator<Self> {
  func makeIterator() -> IndexingIterator<Self> { … }
}

So I cannot call it on a subclass:

for x in Derived() {} // fails

The error is bizarre, "'IndexingIterator<Base>' is not convertible to 'IndexingIterator<Derived>’” — I’m not doing a conversion here.

If you try to call makeIterator() directly, you get an ambiguity error instead:

col.swift:17:5: error: ambiguous reference to member 'makeIterator()'
_ = Derived().makeIterator()
    ^~~~~~~~~
Swift.Collection:6:17: note: found this candidate
    public func makeIterator() -> IndexingIterator<Self>
                ^
Swift.Sequence:5:17: note: found this candidate
    public func makeIterator() -> Self
                ^

Now I couldn’t come up with an example where the code compiles but crashes at runtime because of a type mismatch, but it’s not outside the realm of possibility.

With my PR here the conformance itself no longer type checks: https://github.com/apple/swift/pull/12174

col.swift:1:7: error: type 'Base' does not conform to protocol 'Collection'
class Base : Collection {
      ^
Swift.Sequence:5:17: note: candidate has non-matching type '<Self> () -> Self' [with Element = Int, Index = Int, IndexDistance = Int, Iterator = IndexingIterator<Base>, SubSequence = Slice<Base>, Indices = DefaultIndices<Base>]
    public func makeIterator() -> Self
                ^
Swift.Collection:6:17: note: candidate has non-matching type '<Self> () -> IndexingIterator<Self>' [with Element = Int, Index = Int, IndexDistance = Int, Iterator = IndexingIterator<Base>, SubSequence = Slice<Base>, Indices = DefaultIndices<Base>]
    public func makeIterator() -> IndexingIterator<Self>

I found one example in our code base where this pattern comes up, and that’s SyntaxCollection in tools/SwiftSyntax/SyntaxCollection.swift. It has no subclasses so making it final works there.

This was reported externally as https://bugs.swift.org/browse/SR-1863\. I’m not sure if the user expects it to work or just to produce a reasonable diagnostic instructing them to make the class final.

What does everyone think of this?

1) Can anyone suggest a way to make it work, so that ‘for x in Derived()’ type checks and the correct Self type (Base, not Derived) for the substitution?

2) Should we just ban such ’non-covariant’ conformances? There is precedent for this — in Swift 3, we used to allow non-final classes to conform to protocols whose requirements had same-type constraints with the right hand side equal to ‘Self’, and Doug closed this hole in Swift 4. My PR is essentially a more comprehensive fix for this hole.

3) Should we allow the hole to remain in place, admitting non-final classes that model Collection, at the cost of not being able to ever fix [SR-617] `Self` not always resolved dynamically with Generics · Issue #43234 · apple/swift · GitHub?

Slava

Another solution is to change the Collection protocol as follows,

protocol Collection {
  associatedtype ConformingType = Self
  associatedtype Iterator = IndexingIterator<ConformingType>

  …
}

extension Collection where Iterator == IndexingIterator<ConformingType> {
  func makeIterator() -> IndexingIterator<ConformingType> { … }
}

I believe this will fix the source compatibility issue and also make ‘for x in Derived()’ type check. The downside is that the witness table for a Collection conformance now stores an additional associated type for the static conforming class type. However that’s exactly what you need to store somewhere to make this work for non-final classes.

Slava

···

On Oct 6, 2017, at 12:25 AM, Slava Pestov via swift-dev <swift-dev@swift.org> wrote:

Hi all,

Consider this code,

class Base : Collection {
  var startIndex: Int { return 0 }

  var endIndex: Int { return 10 }

  func index(after i: Int) -> Int { return i + 1 }

  subscript(index: Int) -> Int { return index }
}

We infer the associated type ‘Iterator’ as ‘IndexingIterator<Base>’. I can use an instance of Base as a sequence just fine:

for x in Base() {} // OK

Now if I subclass Base, the associated type is still ‘IndexingIterator<Base>’:

class Derived : Base {}

However the implementation of makeIterator is defined in a constrained extension by the standard library,

extension Collection where Self.Iterator == IndexingIterator<Self> {
  func makeIterator() -> IndexingIterator<Self> { … }
}

So I cannot call it on a subclass:

for x in Derived() {} // fails

The error is bizarre, "'IndexingIterator<Base>' is not convertible to 'IndexingIterator<Derived>’” — I’m not doing a conversion here.

If you try to call makeIterator() directly, you get an ambiguity error instead:

col.swift:17:5: error: ambiguous reference to member 'makeIterator()'
_ = Derived().makeIterator()
    ^~~~~~~~~
Swift.Collection:6:17: note: found this candidate
    public func makeIterator() -> IndexingIterator<Self>
                ^
Swift.Sequence:5:17: note: found this candidate
    public func makeIterator() -> Self
                ^

Now I couldn’t come up with an example where the code compiles but crashes at runtime because of a type mismatch, but it’s not outside the realm of possibility.

With my PR here the conformance itself no longer type checks: https://github.com/apple/swift/pull/12174

col.swift:1:7: error: type 'Base' does not conform to protocol 'Collection'
class Base : Collection {
      ^
Swift.Sequence:5:17: note: candidate has non-matching type '<Self> () -> Self' [with Element = Int, Index = Int, IndexDistance = Int, Iterator = IndexingIterator<Base>, SubSequence = Slice<Base>, Indices = DefaultIndices<Base>]
    public func makeIterator() -> Self
                ^
Swift.Collection:6:17: note: candidate has non-matching type '<Self> () -> IndexingIterator<Self>' [with Element = Int, Index = Int, IndexDistance = Int, Iterator = IndexingIterator<Base>, SubSequence = Slice<Base>, Indices = DefaultIndices<Base>]
    public func makeIterator() -> IndexingIterator<Self>

I found one example in our code base where this pattern comes up, and that’s SyntaxCollection in tools/SwiftSyntax/SyntaxCollection.swift. It has no subclasses so making it final works there.

This was reported externally as https://bugs.swift.org/browse/SR-1863\. I’m not sure if the user expects it to work or just to produce a reasonable diagnostic instructing them to make the class final.

What does everyone think of this?

1) Can anyone suggest a way to make it work, so that ‘for x in Derived()’ type checks and the correct Self type (Base, not Derived) for the substitution?

2) Should we just ban such ’non-covariant’ conformances? There is precedent for this — in Swift 3, we used to allow non-final classes to conform to protocols whose requirements had same-type constraints with the right hand side equal to ‘Self’, and Doug closed this hole in Swift 4. My PR is essentially a more comprehensive fix for this hole.

3) Should we allow the hole to remain in place, admitting non-final classes that model Collection, at the cost of not being able to ever fix [SR-617] `Self` not always resolved dynamically with Generics · Issue #43234 · apple/swift · GitHub?

Slava

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

I just tried this and it causes major breakage with associated type inference and the expression checker so its probably more trouble than its worth.

So back to the three options:

1) Do nothing, and give up on fixing [SR-617] `Self` not always resolved dynamically with Generics · Issue #43234 · apple/swift · GitHub for now
2) Finish https://github.com/apple/swift/pull/12174 and make the new semantics only take effect in -swift-version 5
3) ??? Magic

Slava

···

On Oct 6, 2017, at 12:37 AM, Slava Pestov <spestov@apple.com> wrote:

Another solution is to change the Collection protocol as follows,

protocol Collection {
  associatedtype ConformingType = Self
  associatedtype Iterator = IndexingIterator<ConformingType>

  …
}

extension Collection where Iterator == IndexingIterator<ConformingType> {
  func makeIterator() -> IndexingIterator<ConformingType> { … }
}

I believe this will fix the source compatibility issue and also make ‘for x in Derived()’ type check. The downside is that the witness table for a Collection conformance now stores an additional associated type for the static conforming class type. However that’s exactly what you need to store somewhere to make this work for non-final classes.

Slava

On Oct 6, 2017, at 12:25 AM, Slava Pestov via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

Hi all,

Consider this code,

class Base : Collection {
  var startIndex: Int { return 0 }

  var endIndex: Int { return 10 }

  func index(after i: Int) -> Int { return i + 1 }

  subscript(index: Int) -> Int { return index }
}

We infer the associated type ‘Iterator’ as ‘IndexingIterator<Base>’. I can use an instance of Base as a sequence just fine:

for x in Base() {} // OK

Now if I subclass Base, the associated type is still ‘IndexingIterator<Base>’:

class Derived : Base {}

However the implementation of makeIterator is defined in a constrained extension by the standard library,

extension Collection where Self.Iterator == IndexingIterator<Self> {
  func makeIterator() -> IndexingIterator<Self> { … }
}

So I cannot call it on a subclass:

for x in Derived() {} // fails

The error is bizarre, "'IndexingIterator<Base>' is not convertible to 'IndexingIterator<Derived>’” — I’m not doing a conversion here.

If you try to call makeIterator() directly, you get an ambiguity error instead:

col.swift:17:5: error: ambiguous reference to member 'makeIterator()'
_ = Derived().makeIterator()
    ^~~~~~~~~
Swift.Collection:6:17: note: found this candidate
    public func makeIterator() -> IndexingIterator<Self>
                ^
Swift.Sequence:5:17: note: found this candidate
    public func makeIterator() -> Self
                ^

Now I couldn’t come up with an example where the code compiles but crashes at runtime because of a type mismatch, but it’s not outside the realm of possibility.

With my PR here the conformance itself no longer type checks: https://github.com/apple/swift/pull/12174

col.swift:1:7: error: type 'Base' does not conform to protocol 'Collection'
class Base : Collection {
      ^
Swift.Sequence:5:17: note: candidate has non-matching type '<Self> () -> Self' [with Element = Int, Index = Int, IndexDistance = Int, Iterator = IndexingIterator<Base>, SubSequence = Slice<Base>, Indices = DefaultIndices<Base>]
    public func makeIterator() -> Self
                ^
Swift.Collection:6:17: note: candidate has non-matching type '<Self> () -> IndexingIterator<Self>' [with Element = Int, Index = Int, IndexDistance = Int, Iterator = IndexingIterator<Base>, SubSequence = Slice<Base>, Indices = DefaultIndices<Base>]
    public func makeIterator() -> IndexingIterator<Self>

I found one example in our code base where this pattern comes up, and that’s SyntaxCollection in tools/SwiftSyntax/SyntaxCollection.swift. It has no subclasses so making it final works there.

This was reported externally as https://bugs.swift.org/browse/SR-1863\. I’m not sure if the user expects it to work or just to produce a reasonable diagnostic instructing them to make the class final.

What does everyone think of this?

1) Can anyone suggest a way to make it work, so that ‘for x in Derived()’ type checks and the correct Self type (Base, not Derived) for the substitution?

2) Should we just ban such ’non-covariant’ conformances? There is precedent for this — in Swift 3, we used to allow non-final classes to conform to protocols whose requirements had same-type constraints with the right hand side equal to ‘Self’, and Doug closed this hole in Swift 4. My PR is essentially a more comprehensive fix for this hole.

3) Should we allow the hole to remain in place, admitting non-final classes that model Collection, at the cost of not being able to ever fix [SR-617] `Self` not always resolved dynamically with Generics · Issue #43234 · apple/swift · GitHub?

Slava

_______________________________________________
swift-dev mailing list
swift-dev@swift.org <mailto:swift-dev@swift.org>
https://lists.swift.org/mailman/listinfo/swift-dev

Actually I think I figured out a solution. If the witness has ‘Self’ in a non-covariant position, we use the concrete type for Self. Otherwise, we do it the new way. This makes both examples in puzzle.swift · GitHub work.

Sorry for the noise!

Slava

···

On Oct 6, 2017, at 12:46 AM, Slava Pestov <spestov@apple.com> wrote:

I just tried this and it causes major breakage with associated type inference and the expression checker so its probably more trouble than its worth.

So back to the three options:

1) Do nothing, and give up on fixing [SR-617] `Self` not always resolved dynamically with Generics · Issue #43234 · apple/swift · GitHub for now
2) Finish https://github.com/apple/swift/pull/12174 and make the new semantics only take effect in -swift-version 5
3) ??? Magic

Slava

On Oct 6, 2017, at 12:37 AM, Slava Pestov <spestov@apple.com <mailto:spestov@apple.com>> wrote:

Another solution is to change the Collection protocol as follows,

protocol Collection {
  associatedtype ConformingType = Self
  associatedtype Iterator = IndexingIterator<ConformingType>

  …
}

extension Collection where Iterator == IndexingIterator<ConformingType> {
  func makeIterator() -> IndexingIterator<ConformingType> { … }
}

I believe this will fix the source compatibility issue and also make ‘for x in Derived()’ type check. The downside is that the witness table for a Collection conformance now stores an additional associated type for the static conforming class type. However that’s exactly what you need to store somewhere to make this work for non-final classes.

Slava

On Oct 6, 2017, at 12:25 AM, Slava Pestov via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

Hi all,

Consider this code,

class Base : Collection {
  var startIndex: Int { return 0 }

  var endIndex: Int { return 10 }

  func index(after i: Int) -> Int { return i + 1 }

  subscript(index: Int) -> Int { return index }
}

We infer the associated type ‘Iterator’ as ‘IndexingIterator<Base>’. I can use an instance of Base as a sequence just fine:

for x in Base() {} // OK

Now if I subclass Base, the associated type is still ‘IndexingIterator<Base>’:

class Derived : Base {}

However the implementation of makeIterator is defined in a constrained extension by the standard library,

extension Collection where Self.Iterator == IndexingIterator<Self> {
  func makeIterator() -> IndexingIterator<Self> { … }
}

So I cannot call it on a subclass:

for x in Derived() {} // fails

The error is bizarre, "'IndexingIterator<Base>' is not convertible to 'IndexingIterator<Derived>’” — I’m not doing a conversion here.

If you try to call makeIterator() directly, you get an ambiguity error instead:

col.swift:17:5: error: ambiguous reference to member 'makeIterator()'
_ = Derived().makeIterator()
    ^~~~~~~~~
Swift.Collection:6:17: note: found this candidate
    public func makeIterator() -> IndexingIterator<Self>
                ^
Swift.Sequence:5:17: note: found this candidate
    public func makeIterator() -> Self
                ^

Now I couldn’t come up with an example where the code compiles but crashes at runtime because of a type mismatch, but it’s not outside the realm of possibility.

With my PR here the conformance itself no longer type checks: https://github.com/apple/swift/pull/12174

col.swift:1:7: error: type 'Base' does not conform to protocol 'Collection'
class Base : Collection {
      ^
Swift.Sequence:5:17: note: candidate has non-matching type '<Self> () -> Self' [with Element = Int, Index = Int, IndexDistance = Int, Iterator = IndexingIterator<Base>, SubSequence = Slice<Base>, Indices = DefaultIndices<Base>]
    public func makeIterator() -> Self
                ^
Swift.Collection:6:17: note: candidate has non-matching type '<Self> () -> IndexingIterator<Self>' [with Element = Int, Index = Int, IndexDistance = Int, Iterator = IndexingIterator<Base>, SubSequence = Slice<Base>, Indices = DefaultIndices<Base>]
    public func makeIterator() -> IndexingIterator<Self>

I found one example in our code base where this pattern comes up, and that’s SyntaxCollection in tools/SwiftSyntax/SyntaxCollection.swift. It has no subclasses so making it final works there.

This was reported externally as https://bugs.swift.org/browse/SR-1863\. I’m not sure if the user expects it to work or just to produce a reasonable diagnostic instructing them to make the class final.

What does everyone think of this?

1) Can anyone suggest a way to make it work, so that ‘for x in Derived()’ type checks and the correct Self type (Base, not Derived) for the substitution?

2) Should we just ban such ’non-covariant’ conformances? There is precedent for this — in Swift 3, we used to allow non-final classes to conform to protocols whose requirements had same-type constraints with the right hand side equal to ‘Self’, and Doug closed this hole in Swift 4. My PR is essentially a more comprehensive fix for this hole.

3) Should we allow the hole to remain in place, admitting non-final classes that model Collection, at the cost of not being able to ever fix [SR-617] `Self` not always resolved dynamically with Generics · Issue #43234 · apple/swift · GitHub?

Slava

_______________________________________________
swift-dev mailing list
swift-dev@swift.org <mailto:swift-dev@swift.org>
https://lists.swift.org/mailman/listinfo/swift-dev

1 Like