[RFC] Associated type inference

Hello Swift community,

Associated type inference, which is the process by which the Swift compiler attempts to infer typealiases to satisfy associated-type requirements based on other requirements, has caused both implementation problems and user confusion for a long time. Some of you might remember a previous (failed) attempt to remove this feature from the Swift language, in SE-0108 “Remove associated type inference”. <https://github.com/apple/swift-evolution/blob/master/proposals/0108-remove-assoctype-inference.md&gt;

I’m not sure we can remove this feature outright (i.e., the concerns that sank that proposal are still absolutely valid), because it is so very convenient and a lot of user code likely depends on it in some form or other. So, here I’d like to describe the uses of the feature, its current (very problematic) implementation approach, and a half-baked proposal to narrow the scope of associated type inference to something that I think is more tractable. I need help with the design of this feature, because I feel like it’s going to be a delicate balance between implementability and expressiveness.

A Motivating Example
As a motivating example, let’s consider a “minimal” random access collection:

struct MyCollection<T> {
    var contents: [T]
}

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

This is actually pretty awesome: by providing just two properties and a subscript, we get the full breadth of the random access collection API! This is relying heavily on associated type inference (for associated type requirements) and default implementations specified on protocol extensions. Without associated type inference, we would have had to write:

extension MyCollection: RandomAccessCollection {
    typealias Element = T
    typealias Index = Int
    typealias Indices = CountableRange<Int>
    typealias Iterator = IndexingIterator<MyCollection<T>>
    typealias SubSequence = RandomAccessSlice<MyCollection<T>>
    
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

where the bolded typealiases are currently inferred. It was worse back when we reviewed SE-0108, because IIRC there were a few underscored associated types (e.g., _Element) that have since been removed. Still, that’s a bit of additional work to define a “minimal” collection, and requires quite a bit more understanding: how do I know to choose IndexingIterator, and CountableRange, and RandomAccessSlice?

The issue would get worse with, e.g., SE-0174 “Change filter to return an associated type” <https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md&gt;, which adds an associated type Filtered that almost nobody will ever customize, and isn’t really fundamental to the way collections work. Adding Filtered to the standard library would be a source-breaking change, because users would have to write a typealias giving it its default.

Associated Type Defaults
One of the ways in which we avoid having to specify typealiases is to use associated type defaults. For example, the standard library contains associated type defaults for Indices, Iterator, and SubSequence. Let’s focus on Indices:

protocol Collection : Sequence {
  associatedtype Indices = DefaultIndices<Self>
  // ...
}

protocol BidirectionalCollection : Collection {
  associatedtype Indices = DefaultBidirectionalIndices<Self>
  // ...
}

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Indices = DefaultRandomAccessIndices<Self>
  // ...
}

The basic idea here is that different protocols in the hierarchy provide different defaults, and you presumably want the default from the most specific protocol. If I define a type and make it conform to BidirectionalCollection, I’d expect to get DefaultBidirectionalIndices<Self> for Indices. If a define a type and make it conform to RandomAccessIterator, I’d expect to get DefaultRandomAccessIndices<Self>.

(Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got collapsed into DefaultIndices now that we have conditional conformances for the standard library <https://github.com/apple/swift/pull/12913&gt;, but the issues I’m describing remain).

Associated type defaults seem like a reasonable feature that fits well enough into the design. However, it’s not the only thing in place with our MyCollection example, for which Indices was inferred to CountableRange. How’s that happen?

Associated Type Inference
Associated type inference attempts to look at the requirements of a protocol, and then looks into the conforming type for declarations that might satisfy those requirements, and infers associated types from the types of those declarations. Let’s look at some examples. RandomAccessCollection has some requirements that mention the Index and Element types:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Element
  associatedtype Index

  var startIndex: Index { get }
  var endIndex: Index { get }
  subscript (i: Index) -> Element { get }
}

Associated type inference wil try to satisfy those requirements for MyCollection, and will find these declarations:

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

and match them up. From startIndex, we infer Index := Int. From endIndex, we infer Index := Int. From subscript, we infer Index := Int and Element := T. Those results are all consistent, so we’ve properly inferred Index and Element. Yay.

Associated type inference often has to deal with ambiguities. For example, there is an extension of Collection that provides a range subscript operator:

extension Collection {
  subscript (bounds: Range<Index>) -> Slice<Self> { … }
}

When we look at that and match it to the subscript requirement in RandomAccessCollection (remembering that argument labels aren’t significant for subscripts by default!), we infer Index := Range<Index> (admittedly weird) and Element := Slice<Self> (could be legitimate). We have to discard this candidate because the deduction from startIndex/endIndex (Index := Int) collides with this deduction (Index := Range<Index>).

In our initial example, we saw that Indices was inferred to CountableRange<Int>. Let’s look at another slice of the RandomAccessCollection protocol that’s relevant to this associated type:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Index
  associatedtype Indices: RandomAccessCollection where Indices.Element == Index

  var indices: Indices { get }
}

We will match that requirement for an “indices” property against a member of a constrained protocol extension of RandomAccessCollection:

extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance, Indices == CountableRange<Index> {
  public var indices: CountableRange<Index> {
    return startIndex..<endIndex
  }
}

Associated type inference can determine here that Indices := CountableRange<Index>, but only when Index: Strideable and Index.Stride == IndexDistance. In other words, there are a whole bunch of other constraints to verify before we can accept this inference for Indices.

What’s a Good Solution Look Like?
Our current system for associated type inference and associated type defaults is buggy and complicated. The compiler gets it right often enough that people depend on it, but I don’t think anyone can reasonably be expected to puzzle out what’s going to happen, and this area is rife with bugs. If we were to design a new solution from scratch, what properties should it have?

It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them
It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults
It shouldn’t infer an inconsistent set of typealiases
It should be something that a competent Swift programmer could reason about when it will succeed, when and why it will fail, and what the resulting inferred typealiases would be
It should admit a reasonable implementation in the compiler that is performant and robust

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

Associated type defaults, which are specified with the associated type itself, e.g.,

  associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
Typealiases in (possibly constrained) protocol extensions, e.g.,

  extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
    typealias RandomAccessCollection.Indices = CountableRange<Index>
  }

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols <swift/GenericsManifesto.md at main · apple/swift · GitHub; are merely syntactic sugar.
Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

  extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
  }

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Thoughts?
I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

  - Doug

1 Like

Hi Doug,

···

On Nov 30, 2017, at 4:28 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

I don’t have a lot to add here, except to say: Yes, this makes sense to me, and is much easier to reason about. The three new rough rules covers all of the Swift protocol code I can think of that I’ve written, and seems complete for any reasonable set of thought experiments I’ve come up with so far.

Thanks!
  - Greg

Hello Swift community,

Associated type inference, which is the process by which the Swift compiler attempts to infer typealiases to satisfy associated-type requirements based on other requirements, has caused both implementation problems and user confusion for a long time. Some of you might remember a previous (failed) attempt to remove this feature from the Swift language, in SE-0108 “Remove associated type inference”. <https://github.com/apple/swift-evolution/blob/master/proposals/0108-remove-assoctype-inference.md&gt;

I’m not sure we can remove this feature outright (i.e., the concerns that sank that proposal are still absolutely valid), because it is so very convenient and a lot of user code likely depends on it in some form or other. So, here I’d like to describe the uses of the feature, its current (very problematic) implementation approach, and a half-baked proposal to narrow the scope of associated type inference to something that I think is more tractable. I need help with the design of this feature, because I feel like it’s going to be a delicate balance between implementability and expressiveness.

A Motivating Example
As a motivating example, let’s consider a “minimal” random access collection:

struct MyCollection<T> {
    var contents: [T]
}

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

This is actually pretty awesome: by providing just two properties and a subscript, we get the full breadth of the random access collection API! This is relying heavily on associated type inference (for associated type requirements) and default implementations specified on protocol extensions. Without associated type inference, we would have had to write:

extension MyCollection: RandomAccessCollection {
    typealias Element = T
    typealias Index = Int
    typealias Indices = CountableRange<Int>
    typealias Iterator = IndexingIterator<MyCollection<T>>
    typealias SubSequence = RandomAccessSlice<MyCollection<T>>
    
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

where the bolded typealiases are currently inferred. It was worse back when we reviewed SE-0108, because IIRC there were a few underscored associated types (e.g., _Element) that have since been removed. Still, that’s a bit of additional work to define a “minimal” collection, and requires quite a bit more understanding: how do I know to choose IndexingIterator, and CountableRange, and RandomAccessSlice?

The issue would get worse with, e.g., SE-0174 “Change filter to return an associated type” <https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md&gt;, which adds an associated type Filtered that almost nobody will ever customize, and isn’t really fundamental to the way collections work. Adding Filtered to the standard library would be a source-breaking change, because users would have to write a typealias giving it its default.

Associated Type Defaults
One of the ways in which we avoid having to specify typealiases is to use associated type defaults. For example, the standard library contains associated type defaults for Indices, Iterator, and SubSequence. Let’s focus on Indices:

protocol Collection : Sequence {
  associatedtype Indices = DefaultIndices<Self>
  // ...
}

protocol BidirectionalCollection : Collection {
  associatedtype Indices = DefaultBidirectionalIndices<Self>
  // ...
}

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Indices = DefaultRandomAccessIndices<Self>
  // ...
}

The basic idea here is that different protocols in the hierarchy provide different defaults, and you presumably want the default from the most specific protocol. If I define a type and make it conform to BidirectionalCollection, I’d expect to get DefaultBidirectionalIndices<Self> for Indices. If a define a type and make it conform to RandomAccessIterator, I’d expect to get DefaultRandomAccessIndices<Self>.

(Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got collapsed into DefaultIndices now that we have conditional conformances for the standard library <https://github.com/apple/swift/pull/12913&gt;, but the issues I’m describing remain).

Associated type defaults seem like a reasonable feature that fits well enough into the design. However, it’s not the only thing in place with our MyCollection example, for which Indices was inferred to CountableRange. How’s that happen?

Associated Type Inference
Associated type inference attempts to look at the requirements of a protocol, and then looks into the conforming type for declarations that might satisfy those requirements, and infers associated types from the types of those declarations. Let’s look at some examples. RandomAccessCollection has some requirements that mention the Index and Element types:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Element
  associatedtype Index

  var startIndex: Index { get }
  var endIndex: Index { get }
  subscript (i: Index) -> Element { get }
}

Associated type inference wil try to satisfy those requirements for MyCollection, and will find these declarations:

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

and match them up. From startIndex, we infer Index := Int. From endIndex, we infer Index := Int. From subscript, we infer Index := Int and Element := T. Those results are all consistent, so we’ve properly inferred Index and Element. Yay.

Associated type inference often has to deal with ambiguities. For example, there is an extension of Collection that provides a range subscript operator:

extension Collection {
  subscript (bounds: Range<Index>) -> Slice<Self> { … }
}

When we look at that and match it to the subscript requirement in RandomAccessCollection (remembering that argument labels aren’t significant for subscripts by default!), we infer Index := Range<Index> (admittedly weird) and Element := Slice<Self> (could be legitimate). We have to discard this candidate because the deduction from startIndex/endIndex (Index := Int) collides with this deduction (Index := Range<Index>).

In our initial example, we saw that Indices was inferred to CountableRange<Int>. Let’s look at another slice of the RandomAccessCollection protocol that’s relevant to this associated type:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Index
  associatedtype Indices: RandomAccessCollection where Indices.Element == Index

  var indices: Indices { get }
}

We will match that requirement for an “indices” property against a member of a constrained protocol extension of RandomAccessCollection:

extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance, Indices == CountableRange<Index> {
  public var indices: CountableRange<Index> {
    return startIndex..<endIndex
  }
}

Associated type inference can determine here that Indices := CountableRange<Index>, but only when Index: Strideable and Index.Stride == IndexDistance. In other words, there are a whole bunch of other constraints to verify before we can accept this inference for Indices.

What’s a Good Solution Look Like?
Our current system for associated type inference and associated type defaults is buggy and complicated. The compiler gets it right often enough that people depend on it, but I don’t think anyone can reasonably be expected to puzzle out what’s going to happen, and this area is rife with bugs. If we were to design a new solution from scratch, what properties should it have?

It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them
It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults
It shouldn’t infer an inconsistent set of typealiases
It should be something that a competent Swift programmer could reason about when it will succeed, when and why it will fail, and what the resulting inferred typealiases would be
It should admit a reasonable implementation in the compiler that is performant and robust

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

Associated type defaults, which are specified with the associated type itself, e.g.,

  associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
Typealiases in (possibly constrained) protocol extensions, e.g.,

  extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
    typealias RandomAccessCollection.Indices = CountableRange<Index>
  }

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#default-implementations-in-protocols-&gt; are merely syntactic sugar.
Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

  extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
  }

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Hey Doug,

I'm very much in favour of reducing the scope of associated type inference. Can you outline why you believe that (3) is necessary? If I am following correctly, if we had (1) and (2) the only thing you'd need to add to the "minimal collection" implementation would be a typealias for `Element`, which seems reasonable to me.

Ben

···

On Nov 30, 2017, at 4:28 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

Thoughts?
I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

  - Doug

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

Hi Douglas,

First of all, thanks very much for looking into this seemingly dark corner of the compiler. This caused us a lot of trouble already.

Comments inline.

Hello Swift community,

Associated type inference, which is the process by which the Swift compiler attempts to infer typealiases to satisfy associated-type requirements based on other requirements, has caused both implementation problems and user confusion for a long time. Some of you might remember a previous (failed) attempt to remove this feature from the Swift language, in SE-0108 “Remove associated type inference”.

I’m not sure we can remove this feature outright (i.e., the concerns that sank that proposal are still absolutely valid), because it is so very convenient and a lot of user code likely depends on it in some form or other. So, here I’d like to describe the uses of the feature, its current (very problematic) implementation approach, and a half-baked proposal to narrow the scope of associated type inference to something that I think is more tractable. I need help with the design of this feature, because I feel like it’s going to be a delicate balance between implementability and expressiveness.

A Motivating Example
As a motivating example, let’s consider a “minimal” random access collection:

struct MyCollection<T> {
    var contents: [T]
}

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

This is actually pretty awesome: by providing just two properties and a subscript, we get the full breadth of the random access collection API! This is relying heavily on associated type inference (for associated type requirements) and default implementations specified on protocol extensions. Without associated type inference, we would have had to write:

extension MyCollection: RandomAccessCollection {
    typealias Element = T
    typealias Index = Int
    typealias Indices = CountableRange<Int>
    typealias Iterator = IndexingIterator<MyCollection<T>>
    typealias SubSequence = RandomAccessSlice<MyCollection<T>>
    
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

where the bolded typealiases are currently inferred. It was worse back when we reviewed SE-0108, because IIRC there were a few underscored associated types (e.g., _Element) that have since been removed. Still, that’s a bit of additional work to define a “minimal” collection, and requires quite a bit more understanding: how do I know to choose IndexingIterator, and CountableRange, and RandomAccessSlice?

The issue would get worse with, e.g., SE-0174 “Change filter to return an associated type”, which adds an associated type Filtered that almost nobody will ever customize, and isn’t really fundamental to the way collections work. Adding Filtered to the standard library would be a source-breaking change, because users would have to write a typealias giving it its default.

Associated Type Defaults
One of the ways in which we avoid having to specify typealiases is to use associated type defaults. For example, the standard library contains associated type defaults for Indices, Iterator, and SubSequence. Let’s focus on Indices:

protocol Collection : Sequence {
  associatedtype Indices = DefaultIndices<Self>
  // ...
}

protocol BidirectionalCollection : Collection {
  associatedtype Indices = DefaultBidirectionalIndices<Self>
  // ...
}

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Indices = DefaultRandomAccessIndices<Self>
  // ...
}

The basic idea here is that different protocols in the hierarchy provide different defaults, and you presumably want the default from the most specific protocol. If I define a type and make it conform to BidirectionalCollection, I’d expect to get DefaultBidirectionalIndices<Self> for Indices. If a define a type and make it conform to RandomAccessIterator, I’d expect to get DefaultRandomAccessIndices<Self>.

(Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got collapsed into DefaultIndices now that we have conditional conformances for the standard library, but the issues I’m describing remain).

Associated type defaults seem like a reasonable feature that fits well enough into the design. However, it’s not the only thing in place with our MyCollection example, for which Indices was inferred to CountableRange. How’s that happen?

Associated Type Inference
Associated type inference attempts to look at the requirements of a protocol, and then looks into the conforming type for declarations that might satisfy those requirements, and infers associated types from the types of those declarations. Let’s look at some examples. RandomAccessCollection has some requirements that mention the Index and Element types:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Element
  associatedtype Index

  var startIndex: Index { get }
  var endIndex: Index { get }
  subscript (i: Index) -> Element { get }
}

Associated type inference wil try to satisfy those requirements for MyCollection, and will find these declarations:

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

and match them up. From startIndex, we infer Index := Int. From endIndex, we infer Index := Int. From subscript, we infer Index := Int and Element := T. Those results are all consistent, so we’ve properly inferred Index and Element. Yay.

Associated type inference often has to deal with ambiguities. For example, there is an extension of Collection that provides a range subscript operator:

extension Collection {
  subscript (bounds: Range<Index>) -> Slice<Self> { … }
}

When we look at that and match it to the subscript requirement in RandomAccessCollection (remembering that argument labels aren’t significant for subscripts by default!), we infer Index := Range<Index> (admittedly weird) and Element := Slice<Self> (could be legitimate). We have to discard this candidate because the deduction from startIndex/endIndex (Index := Int) collides with this deduction (Index := Range<Index>).

In our initial example, we saw that Indices was inferred to CountableRange<Int>. Let’s look at another slice of the RandomAccessCollection protocol that’s relevant to this associated type:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Index
  associatedtype Indices: RandomAccessCollection where Indices.Element == Index

  var indices: Indices { get }
}

We will match that requirement for an “indices” property against a member of a constrained protocol extension of RandomAccessCollection:

extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance, Indices == CountableRange<Index> {
  public var indices: CountableRange<Index> {
    return startIndex..<endIndex
  }
}

Associated type inference can determine here that Indices := CountableRange<Index>, but only when Index: Strideable and Index.Stride == IndexDistance. In other words, there are a whole bunch of other constraints to verify before we can accept this inference for Indices.

What’s a Good Solution Look Like?
Our current system for associated type inference and associated type defaults is buggy and complicated. The compiler gets it right often enough that people depend on it, but I don’t think anyone can reasonably be expected to puzzle out what’s going to happen, and this area is rife with bugs. If we were to design a new solution from scratch, what properties should it have?

  • It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them
  • It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults
  • It shouldn’t infer an inconsistent set of typealiases
  • It should be something that a competent Swift programmer could reason about when it will succeed, when and why it will fail, and what the resulting inferred typealiases would be
  • It should admit a reasonable implementation in the compiler that is performant and robust

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

  • Associated type defaults, which are specified with the associated type itself, e.g.,

  associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
  • Typealiases in (possibly constrained) protocol extensions, e.g.,

  extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
    typealias RandomAccessCollection.Indices = CountableRange<Index>
  }

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols are merely syntactic sugar.
  • Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

  extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
  }

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Thoughts?
I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

This seems entirely reasonable to me and makes this a lot easier to understand :100:. The only requirement I'd have is that a use case as described in SR-6516 [1] will work. That is

--- SNIP ---
public struct Foo<A, B, C> {}

public protocol P {
    associatedtype PA /* an implementation must set `PA` */
    associatedtype PB = Never /* an implementation may set `PB` and `PC` */
    associatedtype PC = Never

    associatedtype Context = Foo<PA, PB, PC> /* in our real-world example the right side of this associated type is a very ugly type that we don't want the user to ever write. That's why we want to define an alias "Context" here */

    func f1(_ x: Context, _ y: PA) /* some protocol requirements */
    func f2(_ x: Context, _ y: PB)
    func f3(_ x: Context, _ y: PC)
    func f4(_ x: Context)
}

public extension P {
    /* defaults implementations for all of those */
    public func f1(_ x: Context, _ y: PA) {
    }
    public func f2(_ x: Context, _ y: PB) {
    }
    public func f3(_ x: Context, _ y: PC) {
    }
    public func f4(_ x: Context) {
    }
}

public struct S: P {
    /* the implementation sets `PA` as required, chooses to also set `PB` but lets `PC` alone (defaults to `Never`))
    public typealias PA = String
    public typealias PB = Int

    /* implementations for two out of the four protocol methods using the associated types */
    public func f1(_ x: Context, _ y: PA) {
    }
    public func f2(_ x: Context, _ y: PB) {
    }
}
--- SNAP ---

[1]: [SR-6516] error: reference to invalid associated type 'Context' of type 'S' · Issue #49066 · apple/swift · GitHub

-- Johannes

···

On 1 Dec 2017, at 12:28 am, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

  - Doug

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

How does this work with retroactive conformance, especially where all the
protocol requirements already exist on a type and an empty extension
declares conformance? For example, suppose Module A declares a protocol
with associated types, and Module B has a struct which naturally possesses
all the required members to conform (maybe B handles Double concretely,
while A can work with any FloatingPoint, or some such). As a client
importing both modules and providing an empty extension to conform B’s
struct to A’s protocol, will the associated types be inferred?

Also, have you considered the possibility of allowing protocol authors to
specify which types should be inferred from which requirements? For example
Collection might demarcate “startIndex” as the source-of-truth for
inferring “Index”, and “subscript (Index)->Element” as the source-of-truth
for inferring “Element”.

Nevin

···

On Thu, Nov 30, 2017 at 7:28 PM, Douglas Gregor via swift-evolution < swift-evolution@swift.org> wrote:

*A Rough Proposal*
I’ve been thinking about this for a bit, and I think there are three ways
in which we should be able to infer an associated type witness:

   1. Associated type defaults, which are specified with the associated
   type itself, e.g.,

     associatedtype Indices = DefaultIndices<Self>

   These are easy to reason about for both the programmer and the
   compiler.
   2. Typealiases in (possibly constrained) protocol extensions, e.g.,

     extension RandomAccessCollection where Index : Strideable,
   Index.Stride == IndexDistance {
       typealias RandomAccessCollection.Indices = CountableRange<Index>
     }

   I’m intentionally using some odd ‘.’ syntax here to indicate that this
   typealias is intended only to be found when trying to satisfy an associated
   type requirement, and is not a general typealias that could be found by
   normal name lookup. Let’s set the syntax bike shed aside for the moment.
   The primary advantage of this approach (vs. inferring Indices from “var
   Indices: CountableRange<Index>” in a constrained protocol extension) is
   that there’s a real typealias declaration that compiler and programmer
   alike can look at and reason about based just on the name “Indices”.

   Note that this mechanism technically obviates the need for (1), in the
   same sense that default implementations in protocols
   <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#default-implementations-in-protocols-&gt; are
   merely syntactic sugar.
   3. Declarations within the nominal type declaration or extension that
   declares conformance to the protocol in question. This is generally the
   same approach as described in “associated type inference” above, where we
   match requirements of the protocol against declarations that could satisfy
   those requirements and infer associated types from there. However, I want
   to turn it around: instead of starting with the requirements of the
   protocol any looking basically anywhere in the type or any protocol to
   which it conforms (for implementations in protocol extensions), start with
   the declarations that the user explicitly wrote at the point of the
   conformance and look for requirements they might satisfy. For example,
   consider our initial example:

     extension MyCollection: RandomAccessCollection {
       var startIndex: Int { return contents.startIndex }
       var endIndex: Int { return contents.endIndex }
       subscript(index: Int) -> T { return contents[index] }
     }

   Since startIndex, endIndex, and subscript(_:) are declared in the same
   extension that declares conformance to RandomAccessIterator, we should look
   for requirements with the same name as these properties and subscript
   within RandomAccessCollection (or any protocol it inherits) and infer Index
   := Int and Element := T by matching the type signatures. This is still the
   most magical inference rule, because there is no declaration named “Index”
   or “Element” to look at. However, it is much narrower in scope than the
   current implementation, because it’s only going to reason from the
   (probably small) set of declarations that the user wrote alongside the
   conformance, so it’s more likely to be intentional. Note that this is again
   nudging programmers toward the style of programming where one puts one
   protocol conformance per extension, which is admittedly my personal
   preference.

*Thoughts?*
I think this approach is more predictable and more implementable than the
current model. I’m curious whether the above makes sense to someone other
than me, and whether it covers existing use cases well enough. Thoughts?

- Doug

Hello Swift community,

Associated type inference, which is the process by which the Swift compiler attempts to infer typealiases to satisfy associated-type requirements based on other requirements, has caused both implementation problems and user confusion for a long time. Some of you might remember a previous (failed) attempt to remove this feature from the Swift language, in SE-0108 “Remove associated type inference”. <https://github.com/apple/swift-evolution/blob/master/proposals/0108-remove-assoctype-inference.md&gt;

I’m not sure we can remove this feature outright (i.e., the concerns that sank that proposal are still absolutely valid), because it is so very convenient and a lot of user code likely depends on it in some form or other. So, here I’d like to describe the uses of the feature, its current (very problematic) implementation approach, and a half-baked proposal to narrow the scope of associated type inference to something that I think is more tractable. I need help with the design of this feature, because I feel like it’s going to be a delicate balance between implementability and expressiveness.

A Motivating Example
As a motivating example, let’s consider a “minimal” random access collection:

struct MyCollection<T> {
    var contents: [T]
}

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

This is actually pretty awesome: by providing just two properties and a subscript, we get the full breadth of the random access collection API! This is relying heavily on associated type inference (for associated type requirements) and default implementations specified on protocol extensions. Without associated type inference, we would have had to write:

extension MyCollection: RandomAccessCollection {
    typealias Element = T
    typealias Index = Int
    typealias Indices = CountableRange<Int>
    typealias Iterator = IndexingIterator<MyCollection<T>>
    typealias SubSequence = RandomAccessSlice<MyCollection<T>>
    
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

where the bolded typealiases are currently inferred. It was worse back when we reviewed SE-0108, because IIRC there were a few underscored associated types (e.g., _Element) that have since been removed. Still, that’s a bit of additional work to define a “minimal” collection, and requires quite a bit more understanding: how do I know to choose IndexingIterator, and CountableRange, and RandomAccessSlice?

The issue would get worse with, e.g., SE-0174 “Change filter to return an associated type” <https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md&gt;, which adds an associated type Filtered that almost nobody will ever customize, and isn’t really fundamental to the way collections work. Adding Filtered to the standard library would be a source-breaking change, because users would have to write a typealias giving it its default.

Associated Type Defaults
One of the ways in which we avoid having to specify typealiases is to use associated type defaults. For example, the standard library contains associated type defaults for Indices, Iterator, and SubSequence. Let’s focus on Indices:

protocol Collection : Sequence {
  associatedtype Indices = DefaultIndices<Self>
  // ...
}

protocol BidirectionalCollection : Collection {
  associatedtype Indices = DefaultBidirectionalIndices<Self>
  // ...
}

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Indices = DefaultRandomAccessIndices<Self>
  // ...
}

The basic idea here is that different protocols in the hierarchy provide different defaults, and you presumably want the default from the most specific protocol. If I define a type and make it conform to BidirectionalCollection, I’d expect to get DefaultBidirectionalIndices<Self> for Indices. If a define a type and make it conform to RandomAccessIterator, I’d expect to get DefaultRandomAccessIndices<Self>.

(Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got collapsed into DefaultIndices now that we have conditional conformances for the standard library <https://github.com/apple/swift/pull/12913&gt;, but the issues I’m describing remain).

Associated type defaults seem like a reasonable feature that fits well enough into the design. However, it’s not the only thing in place with our MyCollection example, for which Indices was inferred to CountableRange. How’s that happen?

Associated Type Inference
Associated type inference attempts to look at the requirements of a protocol, and then looks into the conforming type for declarations that might satisfy those requirements, and infers associated types from the types of those declarations. Let’s look at some examples. RandomAccessCollection has some requirements that mention the Index and Element types:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Element
  associatedtype Index

  var startIndex: Index { get }
  var endIndex: Index { get }
  subscript (i: Index) -> Element { get }
}

Associated type inference wil try to satisfy those requirements for MyCollection, and will find these declarations:

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

and match them up. From startIndex, we infer Index := Int. From endIndex, we infer Index := Int. From subscript, we infer Index := Int and Element := T. Those results are all consistent, so we’ve properly inferred Index and Element. Yay.

Associated type inference often has to deal with ambiguities. For example, there is an extension of Collection that provides a range subscript operator:

extension Collection {
  subscript (bounds: Range<Index>) -> Slice<Self> { … }
}

When we look at that and match it to the subscript requirement in RandomAccessCollection (remembering that argument labels aren’t significant for subscripts by default!), we infer Index := Range<Index> (admittedly weird) and Element := Slice<Self> (could be legitimate). We have to discard this candidate because the deduction from startIndex/endIndex (Index := Int) collides with this deduction (Index := Range<Index>).

In our initial example, we saw that Indices was inferred to CountableRange<Int>. Let’s look at another slice of the RandomAccessCollection protocol that’s relevant to this associated type:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Index
  associatedtype Indices: RandomAccessCollection where Indices.Element == Index

  var indices: Indices { get }
}

We will match that requirement for an “indices” property against a member of a constrained protocol extension of RandomAccessCollection:

extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance, Indices == CountableRange<Index> {
  public var indices: CountableRange<Index> {
    return startIndex..<endIndex
  }
}

Associated type inference can determine here that Indices := CountableRange<Index>, but only when Index: Strideable and Index.Stride == IndexDistance. In other words, there are a whole bunch of other constraints to verify before we can accept this inference for Indices.

What’s a Good Solution Look Like?
Our current system for associated type inference and associated type defaults is buggy and complicated. The compiler gets it right often enough that people depend on it, but I don’t think anyone can reasonably be expected to puzzle out what’s going to happen, and this area is rife with bugs. If we were to design a new solution from scratch, what properties should it have?

It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them
It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults
It shouldn’t infer an inconsistent set of typealiases
It should be something that a competent Swift programmer could reason about when it will succeed, when and why it will fail, and what the resulting inferred typealiases would be
It should admit a reasonable implementation in the compiler that is performant and robust

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

Associated type defaults, which are specified with the associated type itself, e.g.,

  associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
Typealiases in (possibly constrained) protocol extensions, e.g.,

  extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
    typealias RandomAccessCollection.Indices = CountableRange<Index>
  }

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#default-implementations-in-protocols-&gt; are merely syntactic sugar.
Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

  extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
  }

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Thoughts?
I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

Hi Doug. I’ve had a chance to give this some thought and spent a little bit of time looking at some code. This approach would be sufficient for some use cases I’ve been having trouble with lately. If it can be implemented correctly and can be relied upon to consistently produce the correct result it would be a huge improvement to the feature. That would be a good baseline from which we could always consider targeted relaxations if we identify additional heuristics that would also be reliable and would simplify a common use case.

One other heuristic that may make sense comes to mind: piggyback on other conformances that are visible where the conformance in question is declared. If an associated type can’t be inferred where T: P is declared but an associated type with the same name is inferred in another conformance of T visible from the T: P declaration use that type. I’ll leave it up to you to evaluate if and when this might be worth considering, you’re the expert!

···

On Nov 30, 2017, at 6:28 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

  - Doug

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

Hello Swift community,

Associated type inference, which is the process by which the Swift compiler attempts to infer typealiases to satisfy associated-type requirements based on other requirements, has caused both implementation problems and user confusion for a long time. Some of you might remember a previous (failed) attempt to remove this feature from the Swift language, in SE-0108 “Remove associated type inference”.

I’m not sure we can remove this feature outright (i.e., the concerns that sank that proposal are still absolutely valid), because it is so very convenient and a lot of user code likely depends on it in some form or other. So, here I’d like to describe the uses of the feature, its current (very problematic) implementation approach, and a half-baked proposal to narrow the scope of associated type inference to something that I think is more tractable. I need help with the design of this feature, because I feel like it’s going to be a delicate balance between implementability and expressiveness.

Aloha, Doug!

A Motivating Example
As a motivating example, let’s consider a “minimal” random access collection:

struct MyCollection<T> {
    var contents: [T]
}

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

This is actually pretty awesome: by providing just two properties and a subscript, we get the full breadth of the random access collection API! This is relying heavily on associated type inference (for associated type requirements) and default implementations specified on protocol extensions. Without associated type inference, we would have had to write:

extension MyCollection: RandomAccessCollection {
    typealias Element = T
    typealias Index = Int
    typealias Indices = CountableRange<Int>
    typealias Iterator = IndexingIterator<MyCollection<T>>
    typealias SubSequence = RandomAccessSlice<MyCollection<T>>
    
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

where the bolded typealiases are currently inferred. It was worse back when we reviewed SE-0108, because IIRC there were a few underscored associated types (e.g., _Element) that have since been removed. Still, that’s a bit of additional work to define a “minimal” collection, and requires quite a bit more understanding: how do I know to choose IndexingIterator, and CountableRange, and RandomAccessSlice?

The issue would get worse with, e.g., SE-0174 “Change filter to return an associated type”, which adds an associated type Filtered that almost nobody will ever customize, and isn’t really fundamental to the way collections work. Adding Filtered to the standard library would be a source-breaking change, because users would have to write a typealias giving it its default.

Associated Type Defaults
One of the ways in which we avoid having to specify typealiases is to use associated type defaults. For example, the standard library contains associated type defaults for Indices, Iterator, and SubSequence. Let’s focus on Indices:

protocol Collection : Sequence {
  associatedtype Indices = DefaultIndices<Self>
  // ...
}

protocol BidirectionalCollection : Collection {
  associatedtype Indices = DefaultBidirectionalIndices<Self>
  // ...
}

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Indices = DefaultRandomAccessIndices<Self>
  // ...
}

The basic idea here is that different protocols in the hierarchy provide different defaults, and you presumably want the default from the most specific protocol. If I define a type and make it conform to BidirectionalCollection, I’d expect to get DefaultBidirectionalIndices<Self> for Indices. If a define a type and make it conform to RandomAccessIterator, I’d expect to get DefaultRandomAccessIndices<Self>.

(Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got collapsed into DefaultIndices now that we have conditional conformances for the standard library, but the issues I’m describing remain).

Associated type defaults seem like a reasonable feature that fits well enough into the design. However, it’s not the only thing in place with our MyCollection example, for which Indices was inferred to CountableRange. How’s that happen?

Associated Type Inference
Associated type inference attempts to look at the requirements of a protocol, and then looks into the conforming type for declarations that might satisfy those requirements, and infers associated types from the types of those declarations. Let’s look at some examples. RandomAccessCollection has some requirements that mention the Index and Element types:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Element
  associatedtype Index

  var startIndex: Index { get }
  var endIndex: Index { get }
  subscript (i: Index) -> Element { get }
}

Associated type inference wil try to satisfy those requirements for MyCollection, and will find these declarations:

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

and match them up. From startIndex, we infer Index := Int. From endIndex, we infer Index := Int. From subscript, we infer Index := Int and Element := T. Those results are all consistent, so we’ve properly inferred Index and Element. Yay.

Associated type inference often has to deal with ambiguities. For example, there is an extension of Collection that provides a range subscript operator:

extension Collection {
  subscript (bounds: Range<Index>) -> Slice<Self> { … }
}

When we look at that and match it to the subscript requirement in RandomAccessCollection (remembering that argument labels aren’t significant for subscripts by default!), we infer Index := Range<Index> (admittedly weird) and Element := Slice<Self> (could be legitimate). We have to discard this candidate because the deduction from startIndex/endIndex (Index := Int) collides with this deduction (Index := Range<Index>).

In our initial example, we saw that Indices was inferred to CountableRange<Int>. Let’s look at another slice of the RandomAccessCollection protocol that’s relevant to this associated type:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Index
  associatedtype Indices: RandomAccessCollection where Indices.Element == Index

  var indices: Indices { get }
}

We will match that requirement for an “indices” property against a member of a constrained protocol extension of RandomAccessCollection:

extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance, Indices == CountableRange<Index> {
  public var indices: CountableRange<Index> {
    return startIndex..<endIndex
  }
}

Associated type inference can determine here that Indices := CountableRange<Index>, but only when Index: Strideable and Index.Stride == IndexDistance. In other words, there are a whole bunch of other constraints to verify before we can accept this inference for Indices.

So, what’s the problem? ;-)

What’s a Good Solution Look Like?
Our current system for associated type inference and associated type defaults is buggy and complicated.

Well, that’s the problem, then. Don’t worry, I won’t suggest that you simply fix the implementation, because even if there weren’t bugs and the system were predictable I’d still think we could improve the situation for users by making associated type default declarations more explicit.

The compiler gets it right often enough that people depend on it, but I don’t think anyone can reasonably be expected to puzzle out what’s going to happen, and this area is rife with bugs. If we were to design a new solution from scratch, what properties should it have?

It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them
It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults
It shouldn’t infer an inconsistent set of typealiases
It should be something that a competent Swift programmer could reason about when it will succeed, when and why it will fail, and what the resulting inferred typealiases would be
It should admit a reasonable implementation in the compiler that is performant and robust

• It should cover all of the existing use cases.
• It should not break code at this point.
• We should have a migration strategy for existing code that avoids traps like silent semantic changes.

My bullet is important to me; I don’t think existing use cases are (inherently) so complex that we can sacrifice almost any of them and still end up with a sufficiently useful system. At the very least, existing use cases provide the only guidance we really have as to what the feature should do.

I think we need to acknowledge that my second bullet is unattainable, at least if we want to improve type checking performance. Not breaking any code means that given any existing code, the compiler would have to explore the same solution space it currently does, and come up with the same answers. Improving performance would require new declarations to use totally optional explicit syntax to prevent some explorations, and that’s an untenable user experience.

Which brings me to my third bullet: unless we are willing to break the code of protocol users (as opposed to vendors) we need to ensure that vendors can confidently convert code to use the new system without changing semantics.

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

Associated type defaults, which are specified with the associated type itself, e.g.,

  associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
Typealiases in (possibly constrained) protocol extensions, e.g.,

  extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
    typealias RandomAccessCollection.Indices = CountableRange<Index>
  }

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols are merely syntactic sugar.
Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

  extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
  }

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Thoughts?

The thing that strikes me most about these is that the first two are explicit declarations of intent: “In the absences of an explicit declaration, deduce this associated type as follows,” while the third is still extremely indirect. While it hints to the compiler about which conformances’ associated type requirements we are trying to satisfy, it never comes out and says straight out what the associated type should be, even though it needs to be mentioned. As a generic programmer, I don’t value the concision gained over the clarity lost, and I’d like to see the solutions to these problems follow the explicit-declaration-of-intent pattern. However, the code in #3 is not written by the protocol vendor, and for me it is (at least currently) a stretch to think of breaking the code of protocol users, so I grudgingly accept it.

If we were really starting from scratch I might suggest requiring that conformances use the associated type name rather than some concrete type, e.g.

extension MyCollection: RandomAccessCollection {
    typealias RandomAccessCollection.Index = Int
    var startIndex: Index { return contents.startIndex }
    var endIndex: Index { return contents.endIndex }
    subscript(index: Index) -> Element { return contents[index] }
  }

But I suspect we’re well past the point in the language’s evolution where that sort of change is possible.

As for migration of protocol user code, I think we’d need to run both the new and the old slow inference in the migrator and flag any differences. I don’t know what to do about protocol vendors’ code though.

I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

Well, covering the use cases is definitely still a concern for me. I don’t think we’ll know for sure until we try it, but have you thought about how to migrate each piece of code in the standard library? Does it cover those cases?

-Dave

···

On Nov 30, 2017, at 2:28 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

Sent from my iPad

If nothing else, dropping (3) would be source breaking for 90%+ of current associated type uses. Whereas even the very minimal inference in (3) probably brings that figure down to 1% or so (outside of the stdlib, which would need to adopt a bunch of (2)). Obviously these percentages are just my guesses and not based on any real survey, but certainly would be the case for all Swift code I’ve seen.

  - Greg

···

On Dec 1, 2017, at 9:11 AM, Ben Langmuir via swift-evolution <swift-evolution@swift.org> wrote:
Hey Doug,

I'm very much in favour of reducing the scope of associated type inference. Can you outline why you believe that (3) is necessary? If I am following correctly, if we had (1) and (2) the only thing you'd need to add to the "minimal collection" implementation would be a typealias for `Element`, which seems reasonable to me.

Ben

Hello Swift community,

Associated type inference, which is the process by which the Swift compiler attempts to infer typealiases to satisfy associated-type requirements based on other requirements, has caused both implementation problems and user confusion for a long time. Some of you might remember a previous (failed) attempt to remove this feature from the Swift language, in SE-0108 “Remove associated type inference”. <https://github.com/apple/swift-evolution/blob/master/proposals/0108-remove-assoctype-inference.md&gt;

I’m not sure we can remove this feature outright (i.e., the concerns that sank that proposal are still absolutely valid), because it is so very convenient and a lot of user code likely depends on it in some form or other. So, here I’d like to describe the uses of the feature, its current (very problematic) implementation approach, and a half-baked proposal to narrow the scope of associated type inference to something that I think is more tractable. I need help with the design of this feature, because I feel like it’s going to be a delicate balance between implementability and expressiveness.

A Motivating Example
As a motivating example, let’s consider a “minimal” random access collection:

struct MyCollection<T> {
    var contents: [T]
}

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

This is actually pretty awesome: by providing just two properties and a subscript, we get the full breadth of the random access collection API! This is relying heavily on associated type inference (for associated type requirements) and default implementations specified on protocol extensions. Without associated type inference, we would have had to write:

extension MyCollection: RandomAccessCollection {
    typealias Element = T
    typealias Index = Int
    typealias Indices = CountableRange<Int>
    typealias Iterator = IndexingIterator<MyCollection<T>>
    typealias SubSequence = RandomAccessSlice<MyCollection<T>>
    
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

where the bolded typealiases are currently inferred. It was worse back when we reviewed SE-0108, because IIRC there were a few underscored associated types (e.g., _Element) that have since been removed. Still, that’s a bit of additional work to define a “minimal” collection, and requires quite a bit more understanding: how do I know to choose IndexingIterator, and CountableRange, and RandomAccessSlice?

The issue would get worse with, e.g., SE-0174 “Change filter to return an associated type” <https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md&gt;, which adds an associated type Filtered that almost nobody will ever customize, and isn’t really fundamental to the way collections work. Adding Filtered to the standard library would be a source-breaking change, because users would have to write a typealias giving it its default.

Associated Type Defaults
One of the ways in which we avoid having to specify typealiases is to use associated type defaults. For example, the standard library contains associated type defaults for Indices, Iterator, and SubSequence. Let’s focus on Indices:

protocol Collection : Sequence {
  associatedtype Indices = DefaultIndices<Self>
  // ...
}

protocol BidirectionalCollection : Collection {
  associatedtype Indices = DefaultBidirectionalIndices<Self>
  // ...
}

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Indices = DefaultRandomAccessIndices<Self>
  // ...
}

The basic idea here is that different protocols in the hierarchy provide different defaults, and you presumably want the default from the most specific protocol. If I define a type and make it conform to BidirectionalCollection, I’d expect to get DefaultBidirectionalIndices<Self> for Indices. If a define a type and make it conform to RandomAccessIterator, I’d expect to get DefaultRandomAccessIndices<Self>.

(Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got collapsed into DefaultIndices now that we have conditional conformances for the standard library <https://github.com/apple/swift/pull/12913&gt;, but the issues I’m describing remain).

Associated type defaults seem like a reasonable feature that fits well enough into the design. However, it’s not the only thing in place with our MyCollection example, for which Indices was inferred to CountableRange. How’s that happen?

Associated Type Inference
Associated type inference attempts to look at the requirements of a protocol, and then looks into the conforming type for declarations that might satisfy those requirements, and infers associated types from the types of those declarations. Let’s look at some examples. RandomAccessCollection has some requirements that mention the Index and Element types:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Element
  associatedtype Index

  var startIndex: Index { get }
  var endIndex: Index { get }
  subscript (i: Index) -> Element { get }
}

Associated type inference wil try to satisfy those requirements for MyCollection, and will find these declarations:

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

and match them up. From startIndex, we infer Index := Int. From endIndex, we infer Index := Int. From subscript, we infer Index := Int and Element := T. Those results are all consistent, so we’ve properly inferred Index and Element. Yay.

Associated type inference often has to deal with ambiguities. For example, there is an extension of Collection that provides a range subscript operator:

extension Collection {
  subscript (bounds: Range<Index>) -> Slice<Self> { … }
}

When we look at that and match it to the subscript requirement in RandomAccessCollection (remembering that argument labels aren’t significant for subscripts by default!), we infer Index := Range<Index> (admittedly weird) and Element := Slice<Self> (could be legitimate). We have to discard this candidate because the deduction from startIndex/endIndex (Index := Int) collides with this deduction (Index := Range<Index>).

In our initial example, we saw that Indices was inferred to CountableRange<Int>. Let’s look at another slice of the RandomAccessCollection protocol that’s relevant to this associated type:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Index
  associatedtype Indices: RandomAccessCollection where Indices.Element == Index

  var indices: Indices { get }
}

We will match that requirement for an “indices” property against a member of a constrained protocol extension of RandomAccessCollection:

extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance, Indices == CountableRange<Index> {
  public var indices: CountableRange<Index> {
    return startIndex..<endIndex
  }
}

Associated type inference can determine here that Indices := CountableRange<Index>, but only when Index: Strideable and Index.Stride == IndexDistance. In other words, there are a whole bunch of other constraints to verify before we can accept this inference for Indices.

What’s a Good Solution Look Like?
Our current system for associated type inference and associated type defaults is buggy and complicated. The compiler gets it right often enough that people depend on it, but I don’t think anyone can reasonably be expected to puzzle out what’s going to happen, and this area is rife with bugs. If we were to design a new solution from scratch, what properties should it have?

It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them
It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults
It shouldn’t infer an inconsistent set of typealiases
It should be something that a competent Swift programmer could reason about when it will succeed, when and why it will fail, and what the resulting inferred typealiases would be
It should admit a reasonable implementation in the compiler that is performant and robust

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

Associated type defaults, which are specified with the associated type itself, e.g.,

  associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
Typealiases in (possibly constrained) protocol extensions, e.g.,

  extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
    typealias RandomAccessCollection.Indices = CountableRange<Index>
  }

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#default-implementations-in-protocols-&gt; are merely syntactic sugar.
Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

  extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
  }

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Hey Doug,

I'm very much in favour of reducing the scope of associated type inference. Can you outline why you believe that (3) is necessary? If I am following correctly, if we had (1) and (2) the only thing you'd need to add to the "minimal collection" implementation would be a typealias for `Element`, which seems reasonable to me.

If we had (1) and (2) but not (3), we’d need to specify both Element and Index in the “minimal collection”:

extension MyCollection: RandomAccessCollection {
    typealias Element = T
    typealias Index = Int
    
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

Indices would come from (2) and Iterator and SubSequence would come from (1).

  - Doug

···

On Dec 1, 2017, at 9:11 AM, Ben Langmuir <blangmuir@apple.com> wrote:

On Nov 30, 2017, at 4:28 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hello Swift community,

Associated type inference, which is the process by which the Swift compiler attempts to infer typealiases to satisfy associated-type requirements based on other requirements, has caused both implementation problems and user confusion for a long time. Some of you might remember a previous (failed) attempt to remove this feature from the Swift language, in SE-0108 “Remove associated type inference”.

I’m not sure we can remove this feature outright (i.e., the concerns that sank that proposal are still absolutely valid), because it is so very convenient and a lot of user code likely depends on it in some form or other. So, here I’d like to describe the uses of the feature, its current (very problematic) implementation approach, and a half-baked proposal to narrow the scope of associated type inference to something that I think is more tractable. I need help with the design of this feature, because I feel like it’s going to be a delicate balance between implementability and expressiveness.

A Motivating Example
As a motivating example, let’s consider a “minimal” random access collection:

struct MyCollection<T> {
    var contents: [T]
}

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

This is actually pretty awesome: by providing just two properties and a subscript, we get the full breadth of the random access collection API! This is relying heavily on associated type inference (for associated type requirements) and default implementations specified on protocol extensions. Without associated type inference, we would have had to write:

extension MyCollection: RandomAccessCollection {
    typealias Element = T
    typealias Index = Int
    typealias Indices = CountableRange<Int>
    typealias Iterator = IndexingIterator<MyCollection<T>>
    typealias SubSequence = RandomAccessSlice<MyCollection<T>>
    
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

where the bolded typealiases are currently inferred. It was worse back when we reviewed SE-0108, because IIRC there were a few underscored associated types (e.g., _Element) that have since been removed. Still, that’s a bit of additional work to define a “minimal” collection, and requires quite a bit more understanding: how do I know to choose IndexingIterator, and CountableRange, and RandomAccessSlice?

The issue would get worse with, e.g., SE-0174 “Change filter to return an associated type”, which adds an associated type Filtered that almost nobody will ever customize, and isn’t really fundamental to the way collections work. Adding Filtered to the standard library would be a source-breaking change, because users would have to write a typealias giving it its default.

Associated Type Defaults
One of the ways in which we avoid having to specify typealiases is to use associated type defaults. For example, the standard library contains associated type defaults for Indices, Iterator, and SubSequence. Let’s focus on Indices:

protocol Collection : Sequence {
  associatedtype Indices = DefaultIndices<Self>
  // ...
}

protocol BidirectionalCollection : Collection {
  associatedtype Indices = DefaultBidirectionalIndices<Self>
  // ...
}

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Indices = DefaultRandomAccessIndices<Self>
  // ...
}

The basic idea here is that different protocols in the hierarchy provide different defaults, and you presumably want the default from the most specific protocol. If I define a type and make it conform to BidirectionalCollection, I’d expect to get DefaultBidirectionalIndices<Self> for Indices. If a define a type and make it conform to RandomAccessIterator, I’d expect to get DefaultRandomAccessIndices<Self>.

(Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got collapsed into DefaultIndices now that we have conditional conformances for the standard library, but the issues I’m describing remain).

Associated type defaults seem like a reasonable feature that fits well enough into the design. However, it’s not the only thing in place with our MyCollection example, for which Indices was inferred to CountableRange. How’s that happen?

Associated Type Inference
Associated type inference attempts to look at the requirements of a protocol, and then looks into the conforming type for declarations that might satisfy those requirements, and infers associated types from the types of those declarations. Let’s look at some examples. RandomAccessCollection has some requirements that mention the Index and Element types:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Element
  associatedtype Index

  var startIndex: Index { get }
  var endIndex: Index { get }
  subscript (i: Index) -> Element { get }
}

Associated type inference wil try to satisfy those requirements for MyCollection, and will find these declarations:

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

and match them up. From startIndex, we infer Index := Int. From endIndex, we infer Index := Int. From subscript, we infer Index := Int and Element := T. Those results are all consistent, so we’ve properly inferred Index and Element. Yay.

Associated type inference often has to deal with ambiguities. For example, there is an extension of Collection that provides a range subscript operator:

extension Collection {
  subscript (bounds: Range<Index>) -> Slice<Self> { … }
}

When we look at that and match it to the subscript requirement in RandomAccessCollection (remembering that argument labels aren’t significant for subscripts by default!), we infer Index := Range<Index> (admittedly weird) and Element := Slice<Self> (could be legitimate). We have to discard this candidate because the deduction from startIndex/endIndex (Index := Int) collides with this deduction (Index := Range<Index>).

In our initial example, we saw that Indices was inferred to CountableRange<Int>. Let’s look at another slice of the RandomAccessCollection protocol that’s relevant to this associated type:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Index
  associatedtype Indices: RandomAccessCollection where Indices.Element == Index

  var indices: Indices { get }
}

We will match that requirement for an “indices” property against a member of a constrained protocol extension of RandomAccessCollection:

extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance, Indices == CountableRange<Index> {
  public var indices: CountableRange<Index> {
    return startIndex..<endIndex
  }
}

Associated type inference can determine here that Indices := CountableRange<Index>, but only when Index: Strideable and Index.Stride == IndexDistance. In other words, there are a whole bunch of other constraints to verify before we can accept this inference for Indices.

What’s a Good Solution Look Like?
Our current system for associated type inference and associated type defaults is buggy and complicated. The compiler gets it right often enough that people depend on it, but I don’t think anyone can reasonably be expected to puzzle out what’s going to happen, and this area is rife with bugs. If we were to design a new solution from scratch, what properties should it have?

It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them
It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults
It shouldn’t infer an inconsistent set of typealiases
It should be something that a competent Swift programmer could reason about when it will succeed, when and why it will fail, and what the resulting inferred typealiases would be
It should admit a reasonable implementation in the compiler that is performant and robust

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

Associated type defaults, which are specified with the associated type itself, e.g.,

  associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
Typealiases in (possibly constrained) protocol extensions, e.g.,

  extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
    typealias RandomAccessCollection.Indices = CountableRange<Index>
  }

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols are merely syntactic sugar.
Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

  extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
  }

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Thoughts?
I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

Hi Doug. I’ve had a chance to give this some thought and spent a little bit of time looking at some code. This approach would be sufficient for some use cases I’ve been having trouble with lately.

Thank you for staying this further!

One other heuristic that may make sense comes to mind: piggyback on other conformances that are visible where the conformance in question is declared. If an associated type can’t be inferred where T: P is declared but an associated type with the same name is inferred in another conformance of T visible from the T: P declaration use that type. I’ll leave it up to you to evaluate if and when this might be worth considering, you’re the expert!

Yes, this is a good point. The tricky thing here is that it’s a different kind of “global” inference, where at worst we are considering all of the protocols to which a given type conforms at once... but I suspect we have to do something along these lines.

  - Doug

···

Sent from my iPhone

On Dec 2, 2017, at 1:37 PM, Matthew Johnson <matthew@anandabits.com> wrote:

On Nov 30, 2017, at 6:28 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

  - Doug

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

Sent from my iPhone

Hello Swift community,

Associated type inference, which is the process by which the Swift compiler attempts to infer typealiases to satisfy associated-type requirements based on other requirements, has caused both implementation problems and user confusion for a long time. Some of you might remember a previous (failed) attempt to remove this feature from the Swift language, in SE-0108 “Remove associated type inference”.

I’m not sure we can remove this feature outright (i.e., the concerns that sank that proposal are still absolutely valid), because it is so very convenient and a lot of user code likely depends on it in some form or other. So, here I’d like to describe the uses of the feature, its current (very problematic) implementation approach, and a half-baked proposal to narrow the scope of associated type inference to something that I think is more tractable. I need help with the design of this feature, because I feel like it’s going to be a delicate balance between implementability and expressiveness.

A Motivating Example
As a motivating example, let’s consider a “minimal” random access collection:

struct MyCollection<T> {
    var contents: [T]
}

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

This is actually pretty awesome: by providing just two properties and a subscript, we get the full breadth of the random access collection API! This is relying heavily on associated type inference (for associated type requirements) and default implementations specified on protocol extensions. Without associated type inference, we would have had to write:

extension MyCollection: RandomAccessCollection {
    typealias Element = T
    typealias Index = Int
    typealias Indices = CountableRange<Int>
    typealias Iterator = IndexingIterator<MyCollection<T>>
    typealias SubSequence = RandomAccessSlice<MyCollection<T>>
    
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

where the bolded typealiases are currently inferred. It was worse back when we reviewed SE-0108, because IIRC there were a few underscored associated types (e.g., _Element) that have since been removed. Still, that’s a bit of additional work to define a “minimal” collection, and requires quite a bit more understanding: how do I know to choose IndexingIterator, and CountableRange, and RandomAccessSlice?

The issue would get worse with, e.g., SE-0174 “Change filter to return an associated type”, which adds an associated type Filtered that almost nobody will ever customize, and isn’t really fundamental to the way collections work. Adding Filtered to the standard library would be a source-breaking change, because users would have to write a typealias giving it its default.

Associated Type Defaults
One of the ways in which we avoid having to specify typealiases is to use associated type defaults. For example, the standard library contains associated type defaults for Indices, Iterator, and SubSequence. Let’s focus on Indices:

protocol Collection : Sequence {
  associatedtype Indices = DefaultIndices<Self>
  // ...
}

protocol BidirectionalCollection : Collection {
  associatedtype Indices = DefaultBidirectionalIndices<Self>
  // ...
}

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Indices = DefaultRandomAccessIndices<Self>
  // ...
}

The basic idea here is that different protocols in the hierarchy provide different defaults, and you presumably want the default from the most specific protocol. If I define a type and make it conform to BidirectionalCollection, I’d expect to get DefaultBidirectionalIndices<Self> for Indices. If a define a type and make it conform to RandomAccessIterator, I’d expect to get DefaultRandomAccessIndices<Self>.

(Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got collapsed into DefaultIndices now that we have conditional conformances for the standard library, but the issues I’m describing remain).

Associated type defaults seem like a reasonable feature that fits well enough into the design. However, it’s not the only thing in place with our MyCollection example, for which Indices was inferred to CountableRange. How’s that happen?

Associated Type Inference
Associated type inference attempts to look at the requirements of a protocol, and then looks into the conforming type for declarations that might satisfy those requirements, and infers associated types from the types of those declarations. Let’s look at some examples. RandomAccessCollection has some requirements that mention the Index and Element types:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Element
  associatedtype Index

  var startIndex: Index { get }
  var endIndex: Index { get }
  subscript (i: Index) -> Element { get }
}

Associated type inference wil try to satisfy those requirements for MyCollection, and will find these declarations:

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

and match them up. From startIndex, we infer Index := Int. From endIndex, we infer Index := Int. From subscript, we infer Index := Int and Element := T. Those results are all consistent, so we’ve properly inferred Index and Element. Yay.

Associated type inference often has to deal with ambiguities. For example, there is an extension of Collection that provides a range subscript operator:

extension Collection {
  subscript (bounds: Range<Index>) -> Slice<Self> { … }
}

When we look at that and match it to the subscript requirement in RandomAccessCollection (remembering that argument labels aren’t significant for subscripts by default!), we infer Index := Range<Index> (admittedly weird) and Element := Slice<Self> (could be legitimate). We have to discard this candidate because the deduction from startIndex/endIndex (Index := Int) collides with this deduction (Index := Range<Index>).

In our initial example, we saw that Indices was inferred to CountableRange<Int>. Let’s look at another slice of the RandomAccessCollection protocol that’s relevant to this associated type:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Index
  associatedtype Indices: RandomAccessCollection where Indices.Element == Index

  var indices: Indices { get }
}

We will match that requirement for an “indices” property against a member of a constrained protocol extension of RandomAccessCollection:

extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance, Indices == CountableRange<Index> {
  public var indices: CountableRange<Index> {
    return startIndex..<endIndex
  }
}

Associated type inference can determine here that Indices := CountableRange<Index>, but only when Index: Strideable and Index.Stride == IndexDistance. In other words, there are a whole bunch of other constraints to verify before we can accept this inference for Indices.

What’s a Good Solution Look Like?
Our current system for associated type inference and associated type defaults is buggy and complicated. The compiler gets it right often enough that people depend on it, but I don’t think anyone can reasonably be expected to puzzle out what’s going to happen, and this area is rife with bugs. If we were to design a new solution from scratch, what properties should it have?

It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them
It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults
It shouldn’t infer an inconsistent set of typealiases
It should be something that a competent Swift programmer could reason about when it will succeed, when and why it will fail, and what the resulting inferred typealiases would be
It should admit a reasonable implementation in the compiler that is performant and robust

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

Associated type defaults, which are specified with the associated type itself, e.g.,

  associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
Typealiases in (possibly constrained) protocol extensions, e.g.,

  extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
    typealias RandomAccessCollection.Indices = CountableRange<Index>
  }

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols are merely syntactic sugar.
Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

  extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
  }

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Thoughts?
I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

Hi Doug. I’ve had a chance to give this some thought and spent a little bit of time looking at some code. This approach would be sufficient for some use cases I’ve been having trouble with lately.

Thank you for staying this further!

One other heuristic that may make sense comes to mind: piggyback on other conformances that are visible where the conformance in question is declared. If an associated type can’t be inferred where T: P is declared but an associated type with the same name is inferred in another conformance of T visible from the T: P declaration use that type. I’ll leave it up to you to evaluate if and when this might be worth considering, you’re the expert!

Yes, this is a good point. The tricky thing here is that it’s a different kind of “global” inference, where at worst we are considering all of the protocols to which a given type conforms at once... but I suspect we have to do something along these lines.

The global nature of this and potential complexity associated with that is exactly why I’m happy leaving it to your judgement.

···

Sent from my iPad

On Dec 2, 2017, at 4:40 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Dec 2, 2017, at 1:37 PM, Matthew Johnson <matthew@anandabits.com> wrote:

On Nov 30, 2017, at 6:28 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

  - Doug

  - Doug

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

Definitely in favour of doing something, I always define the associated types since I have had so much trouble with the inference.

Personally I would prefer just 1 and 2 and forget 3. I know this would break a lot of code, but I think we should do that because it is the lesser of the evils.

-- Howard.

···

On 1 Dec 2017, at 11:20 pm, Johannes Weiß via swift-evolution <swift-evolution@swift.org> wrote:

Hi Douglas,

First of all, thanks very much for looking into this seemingly dark corner of the compiler. This caused us a lot of trouble already.

Comments inline.

On 1 Dec 2017, at 12:28 am, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

Hello Swift community,

Associated type inference, which is the process by which the Swift compiler attempts to infer typealiases to satisfy associated-type requirements based on other requirements, has caused both implementation problems and user confusion for a long time. Some of you might remember a previous (failed) attempt to remove this feature from the Swift language, in SE-0108 “Remove associated type inference”.

I’m not sure we can remove this feature outright (i.e., the concerns that sank that proposal are still absolutely valid), because it is so very convenient and a lot of user code likely depends on it in some form or other. So, here I’d like to describe the uses of the feature, its current (very problematic) implementation approach, and a half-baked proposal to narrow the scope of associated type inference to something that I think is more tractable. I need help with the design of this feature, because I feel like it’s going to be a delicate balance between implementability and expressiveness.

A Motivating Example
As a motivating example, let’s consider a “minimal” random access collection:

struct MyCollection<T> {
var contents: [T]
}

extension MyCollection: RandomAccessCollection {
var startIndex: Int { return contents.startIndex }
var endIndex: Int { return contents.endIndex }
subscript(index: Int) -> T { return contents[index] }
}

This is actually pretty awesome: by providing just two properties and a subscript, we get the full breadth of the random access collection API! This is relying heavily on associated type inference (for associated type requirements) and default implementations specified on protocol extensions. Without associated type inference, we would have had to write:

extension MyCollection: RandomAccessCollection {
typealias Element = T
typealias Index = Int
typealias Indices = CountableRange<Int>
typealias Iterator = IndexingIterator<MyCollection<T>>
typealias SubSequence = RandomAccessSlice<MyCollection<T>>

var startIndex: Int { return contents.startIndex }
var endIndex: Int { return contents.endIndex }
subscript(index: Int) -> T { return contents[index] }
}

where the bolded typealiases are currently inferred. It was worse back when we reviewed SE-0108, because IIRC there were a few underscored associated types (e.g., _Element) that have since been removed. Still, that’s a bit of additional work to define a “minimal” collection, and requires quite a bit more understanding: how do I know to choose IndexingIterator, and CountableRange, and RandomAccessSlice?

The issue would get worse with, e.g., SE-0174 “Change filter to return an associated type”, which adds an associated type Filtered that almost nobody will ever customize, and isn’t really fundamental to the way collections work. Adding Filtered to the standard library would be a source-breaking change, because users would have to write a typealias giving it its default.

Associated Type Defaults
One of the ways in which we avoid having to specify typealiases is to use associated type defaults. For example, the standard library contains associated type defaults for Indices, Iterator, and SubSequence. Let’s focus on Indices:

protocol Collection : Sequence {
associatedtype Indices = DefaultIndices<Self>
// ...
}

protocol BidirectionalCollection : Collection {
associatedtype Indices = DefaultBidirectionalIndices<Self>
// ...
}

protocol RandomAccessCollection : BidirectionalCollection {
associatedtype Indices = DefaultRandomAccessIndices<Self>
// ...
}

The basic idea here is that different protocols in the hierarchy provide different defaults, and you presumably want the default from the most specific protocol. If I define a type and make it conform to BidirectionalCollection, I’d expect to get DefaultBidirectionalIndices<Self> for Indices. If a define a type and make it conform to RandomAccessIterator, I’d expect to get DefaultRandomAccessIndices<Self>.

(Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got collapsed into DefaultIndices now that we have conditional conformances for the standard library, but the issues I’m describing remain).

Associated type defaults seem like a reasonable feature that fits well enough into the design. However, it’s not the only thing in place with our MyCollection example, for which Indices was inferred to CountableRange. How’s that happen?

Associated Type Inference
Associated type inference attempts to look at the requirements of a protocol, and then looks into the conforming type for declarations that might satisfy those requirements, and infers associated types from the types of those declarations. Let’s look at some examples. RandomAccessCollection has some requirements that mention the Index and Element types:

protocol RandomAccessCollection : BidirectionalCollection {
associatedtype Element
associatedtype Index

var startIndex: Index { get }
var endIndex: Index { get }
subscript (i: Index) -> Element { get }
}

Associated type inference wil try to satisfy those requirements for MyCollection, and will find these declarations:

extension MyCollection: RandomAccessCollection {
var startIndex: Int { return contents.startIndex }
var endIndex: Int { return contents.endIndex }
subscript(index: Int) -> T { return contents[index] }
}

and match them up. From startIndex, we infer Index := Int. From endIndex, we infer Index := Int. From subscript, we infer Index := Int and Element := T. Those results are all consistent, so we’ve properly inferred Index and Element. Yay.

Associated type inference often has to deal with ambiguities. For example, there is an extension of Collection that provides a range subscript operator:

extension Collection {
subscript (bounds: Range<Index>) -> Slice<Self> { … }
}

When we look at that and match it to the subscript requirement in RandomAccessCollection (remembering that argument labels aren’t significant for subscripts by default!), we infer Index := Range<Index> (admittedly weird) and Element := Slice<Self> (could be legitimate). We have to discard this candidate because the deduction from startIndex/endIndex (Index := Int) collides with this deduction (Index := Range<Index>).

In our initial example, we saw that Indices was inferred to CountableRange<Int>. Let’s look at another slice of the RandomAccessCollection protocol that’s relevant to this associated type:

protocol RandomAccessCollection : BidirectionalCollection {
associatedtype Index
associatedtype Indices: RandomAccessCollection where Indices.Element == Index

var indices: Indices { get }
}

We will match that requirement for an “indices” property against a member of a constrained protocol extension of RandomAccessCollection:

extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance, Indices == CountableRange<Index> {
public var indices: CountableRange<Index> {
return startIndex..<endIndex
}
}

Associated type inference can determine here that Indices := CountableRange<Index>, but only when Index: Strideable and Index.Stride == IndexDistance. In other words, there are a whole bunch of other constraints to verify before we can accept this inference for Indices.

What’s a Good Solution Look Like?
Our current system for associated type inference and associated type defaults is buggy and complicated. The compiler gets it right often enough that people depend on it, but I don’t think anyone can reasonably be expected to puzzle out what’s going to happen, and this area is rife with bugs. If we were to design a new solution from scratch, what properties should it have?

• It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them
• It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults
• It shouldn’t infer an inconsistent set of typealiases
• It should be something that a competent Swift programmer could reason about when it will succeed, when and why it will fail, and what the resulting inferred typealiases would be
• It should admit a reasonable implementation in the compiler that is performant and robust

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

• Associated type defaults, which are specified with the associated type itself, e.g.,

associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
• Typealiases in (possibly constrained) protocol extensions, e.g.,

extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
typealias RandomAccessCollection.Indices = CountableRange<Index>
}

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols are merely syntactic sugar.
• Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

extension MyCollection: RandomAccessCollection {
var startIndex: Int { return contents.startIndex }
var endIndex: Int { return contents.endIndex }
subscript(index: Int) -> T { return contents[index] }
}

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Thoughts?
I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

This seems entirely reasonable to me and makes this a lot easier to understand :100:. The only requirement I'd have is that a use case as described in SR-6516 [1] will work. That is

--- SNIP ---
public struct Foo<A, B, C> {}

public protocol P {
associatedtype PA /* an implementation must set `PA` */
associatedtype PB = Never /* an implementation may set `PB` and `PC` */
associatedtype PC = Never

associatedtype Context = Foo<PA, PB, PC> /* in our real-world example the right side of this associated type is a very ugly type that we don't want the user to ever write. That's why we want to define an alias "Context" here */

func f1(_ x: Context, _ y: PA) /* some protocol requirements */
func f2(_ x: Context, _ y: PB)
func f3(_ x: Context, _ y: PC)
func f4(_ x: Context)
}

public extension P {
/* defaults implementations for all of those */
public func f1(_ x: Context, _ y: PA) {
}
public func f2(_ x: Context, _ y: PB) {
}
public func f3(_ x: Context, _ y: PC) {
}
public func f4(_ x: Context) {
}
}

public struct S: P {
/* the implementation sets `PA` as required, chooses to also set `PB` but lets `PC` alone (defaults to `Never`))
public typealias PA = String
public typealias PB = Int

/* implementations for two out of the four protocol methods using the associated types */
public func f1(_ x: Context, _ y: PA) {
}
public func f2(_ x: Context, _ y: PB) {
}
}
--- SNAP ---

[1]: [SR-6516] error: reference to invalid associated type 'Context' of type 'S' · Issue #49066 · apple/swift · GitHub

-- Johannes

- Doug

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

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

Would this help sorting out the behavior of typealiases in constrained
extensions?

If not, please ignore the following and accept my apologies for posting OT.

Typealiases in constrained extensions are - and have been, for a long time
- very broken.
The following program (which is clearly crazy in several ways) compiles and
runs using the latest version of the compiler:

struct S<T> {
  var v: This
}
extension S where T == Int {
  typealias This = Is
}
extension S where T == Bool {
  typealias Is = Fine
}
extension S where T == String {
  typealias Fine = T
}
let x = S<Float80>(v: "uh")
print(x.v) // uh

( SR-5440 )
The current behavior is so allowing and strange that I'm having trouble
seeing what the correct behavior would be if things worked as intended.
For example should the following program still compile, and if so, should
the last line also compile (if uncommented)?

protocol P {
    associatedtype A = Int
    associatedtype B = Bool
    typealias C = Float
}
extension P where B == A {
    typealias C = String
}
struct S<A, B> : P {
    var v: (A, B, C)
}
extension S where A == Int, B == Bool {
    typealias C = [String]
}
let s1 = S(v: (1, true, [""]))
// let s2 = S(v: ("a", "b", "c")) // Not (currently) ok.

Again, sorry for the noise if this is unrelated to the discussion.
/Jens

···

On Sun, Dec 3, 2017 at 6:23 AM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

On Nov 30, 2017, at 2:28 PM, Douglas Gregor via swift-evolution < > swift-evolution@swift.org> wrote:

Hello Swift community,

Associated type inference, which is the process by which the Swift
compiler attempts to infer typealiases to satisfy associated-type
requirements based on other requirements, has caused both implementation
problems and user confusion for a long time. Some of you might remember a
previous (failed) attempt to remove this feature from the Swift language,
in SE-0108 “Remove associated type inference”.
<https://github.com/apple/swift-evolution/blob/master/proposals/0108-remove-assoctype-inference.md&gt;

I’m not sure we can remove this feature outright (i.e., the concerns that
sank that proposal are still absolutely valid), because it is so very
convenient and a lot of user code likely depends on it in some form or
other. So, here I’d like to describe the uses of the feature, its current
(very problematic) implementation approach, and a half-baked proposal to
narrow the scope of associated type inference to something that I think is
more tractable. I need help with the design of this feature, because I feel
like it’s going to be a delicate balance between implementability and
expressiveness.

Aloha, Doug!

*A Motivating Example*
As a motivating example, let’s consider a “minimal” random access
collection:

struct MyCollection<T> {
    var contents: [T]
}

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

This is actually pretty awesome: by providing just two properties and a
subscript, we get the full breadth of the random access collection API!
This is relying heavily on associated type inference (for associated type
requirements) and default implementations specified on protocol extensions.
Without associated type inference, we would have had to write:

extension MyCollection: RandomAccessCollection {
* typealias Element = T*
* typealias Index = Int*
* typealias Indices = CountableRange<Int>*
* typealias Iterator = IndexingIterator<MyCollection<T>>*
* typealias SubSequence = RandomAccessSlice<MyCollection<T>>*

    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

where the bolded typealiases are currently inferred. It was worse back
when we reviewed SE-0108, because IIRC there were a few underscored
associated types (e.g., _Element) that have since been removed. Still,
that’s a bit of additional work to define a “minimal” collection, and
requires quite a bit more understanding: how do I know to choose
IndexingIterator, and CountableRange, and RandomAccessSlice?

The issue would get worse with, e.g., SE-0174 “Change filter to return an
associated type”
<https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md&gt;,
which adds an associated type Filtered that almost nobody will ever
customize, and isn’t really fundamental to the way collections work. Adding
Filtered to the standard library would be a source-breaking change, because
users would have to write a typealias giving it its default.

*Associated Type Defaults*
One of the ways in which we avoid having to specify typealiases is to use
associated type defaults. For example, the standard library contains
associated type defaults for Indices, Iterator, and SubSequence. Let’s
focus on Indices:

protocol Collection : Sequence {
  associatedtype Indices = DefaultIndices<Self>
  // ...
}

protocol BidirectionalCollection : Collection {
  associatedtype Indices = DefaultBidirectionalIndices<Self>
  // ...
}

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Indices = DefaultRandomAccessIndices<Self>
  // ...
}

The basic idea here is that different protocols in the hierarchy provide
different defaults, and you presumably want the default from the most
specific protocol. If I define a type and make it conform to
BidirectionalCollection, I’d expect to get DefaultBidirectionalIndices<Self>
for Indices. If a define a type and make it conform to
RandomAccessIterator, I’d expect to get DefaultRandomAccessIndices<Self>.

(Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got
collapsed into DefaultIndices now that we have conditional conformances
for the standard library <https://github.com/apple/swift/pull/12913&gt;, but
the issues I’m describing remain).

Associated type defaults seem like a reasonable feature that fits well
enough into the design. However, it’s not the only thing in place with our
MyCollection example, for which Indices was inferred to CountableRange.
How’s that happen?

*Associated Type Inference*
Associated type inference attempts to look at the requirements of a
protocol, and then looks into the conforming type for declarations that
might satisfy those requirements, and infers associated types from the
types of those declarations. Let’s look at some examples.
RandomAccessCollection has some requirements that mention the Index and
Element types:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Element
  associatedtype Index

  var startIndex: Index { get }
  var endIndex: Index { get }
  subscript (i: Index) -> Element { get }
}

Associated type inference wil try to satisfy those requirements for
MyCollection, and will find these declarations:

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

and match them up. From startIndex, we infer Index := Int. From endIndex,
we infer Index := Int. From subscript, we infer Index := Int and Element :=
T. Those results are all consistent, so we’ve properly inferred Index and
Element. Yay.

Associated type inference often has to deal with ambiguities. For example,
there is an extension of Collection that provides a range subscript
operator:

extension Collection {
  subscript (bounds: Range<Index>) -> Slice<Self> { … }
}

When we look at that and match it to the subscript requirement in
RandomAccessCollection (remembering that argument labels aren’t significant
for subscripts by default!), we infer Index := Range<Index> (admittedly
weird) and Element := Slice<Self> (could be legitimate). We have to discard
this candidate because the deduction from startIndex/endIndex (Index :=
Int) collides with this deduction (Index := Range<Index>).

In our initial example, we saw that Indices was inferred to
CountableRange<Int>. Let’s look at another slice of the
RandomAccessCollection protocol that’s relevant to this associated type:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Index
  associatedtype Indices: RandomAccessCollection where Indices.Element ==
Index

  var indices: Indices { get }
}

We will match that requirement for an “indices” property against a member
of a constrained protocol extension of RandomAccessCollection:

extension RandomAccessCollection where Index : Strideable, Index.Stride ==
IndexDistance, Indices == CountableRange<Index> {
  public var indices: CountableRange<Index> {
    return startIndex..<endIndex
  }
}

Associated type inference can determine here that Indices :=
CountableRange<Index>, but only when Index: Strideable and Index.Stride ==
IndexDistance. In other words, there are a whole bunch of other constraints
to verify before we can accept this inference for Indices.

So, what’s the problem? ;-)

*What’s a Good Solution Look Like?*
Our current system for associated type inference and associated type
defaults is buggy and complicated.

Well, *that’s* the problem, then. Don’t worry, I won’t suggest that you
simply fix the implementation, because even if there weren’t bugs and the
system were predictable I’d still think we could improve the situation for
users by making associated type default declarations more explicit.

The compiler gets it right often enough that people depend on it, but I
don’t think anyone can reasonably be expected to puzzle out what’s going to
happen, and this area is rife with bugs. If we were to design a new
solution from scratch, what properties should it have?

   - It should allow the author of a protocol to provide reasonable
   defaults, so the user doesn’t have to write them
   - It shouldn’t require users to write typealiases for “obvious” cases,
   even when they aren’t due to defaults
   - It shouldn’t infer an inconsistent set of typealiases
   - It should be something that a competent Swift programmer could
   reason about when it will succeed, when and why it will fail, and what the
   resulting inferred typealiases would be
   - It should admit a reasonable implementation in the compiler that is
   performant and robust

• It should cover all of the existing use cases.
• It should not break code at this point.
• We should have a migration strategy for existing code that avoids traps
like silent semantic changes.

My bullet is important to me; I don’t think existing use cases are
(inherently) so complex that we can sacrifice almost any of them and still
end up with a sufficiently useful system. At the very least, existing use
cases provide the only guidance we really have as to what the feature
should do.

I think we need to acknowledge that my second bullet is unattainable, at
least if we want to improve type checking performance. Not breaking any
code means that given any existing code, the compiler would have to explore
the same solution space it currently does, and come up with the same
answers. Improving performance would require new declarations to use
totally optional explicit syntax to prevent some explorations, and that’s
an untenable user experience.

Which brings me to my third bullet: unless we are willing to break the
code of protocol *users* (as opposed to vendors) we need to ensure that
vendors can confidently convert code to use the new system without changing
semantics.

*A Rough Proposal*
I’ve been thinking about this for a bit, and I think there are three ways
in which we should be able to infer an associated type witness:

   1. Associated type defaults, which are specified with the associated
   type itself, e.g.,

     associatedtype Indices = DefaultIndices<Self>

   These are easy to reason about for both the programmer and the
   compiler.
   2. Typealiases in (possibly constrained) protocol extensions, e.g.,

     extension RandomAccessCollection where Index : Strideable,
   Index.Stride == IndexDistance {
       typealias RandomAccessCollection.Indices = CountableRange<Index>
     }

   I’m intentionally using some odd ‘.’ syntax here to indicate that this
   typealias is intended only to be found when trying to satisfy an associated
   type requirement, and is not a general typealias that could be found by
   normal name lookup. Let’s set the syntax bike shed aside for the moment.
   The primary advantage of this approach (vs. inferring Indices from “var
   Indices: CountableRange<Index>” in a constrained protocol extension) is
   that there’s a real typealias declaration that compiler and programmer
   alike can look at and reason about based just on the name “Indices”.

   Note that this mechanism technically obviates the need for (1), in the
   same sense that default implementations in protocols
   <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#default-implementations-in-protocols-&gt; are
   merely syntactic sugar.
   3. Declarations within the nominal type declaration or extension that
   declares conformance to the protocol in question. This is generally the
   same approach as described in “associated type inference” above, where we
   match requirements of the protocol against declarations that could satisfy
   those requirements and infer associated types from there. However, I want
   to turn it around: instead of starting with the requirements of the
   protocol any looking basically anywhere in the type or any protocol to
   which it conforms (for implementations in protocol extensions), start with
   the declarations that the user explicitly wrote at the point of the
   conformance and look for requirements they might satisfy. For example,
   consider our initial example:

     extension MyCollection: RandomAccessCollection {
       var startIndex: Int { return contents.startIndex }
       var endIndex: Int { return contents.endIndex }
       subscript(index: Int) -> T { return contents[index] }
     }

   Since startIndex, endIndex, and subscript(_:) are declared in the same
   extension that declares conformance to RandomAccessIterator, we should look
   for requirements with the same name as these properties and subscript
   within RandomAccessCollection (or any protocol it inherits) and infer Index
   := Int and Element := T by matching the type signatures. This is still the
   most magical inference rule, because there is no declaration named “Index”
   or “Element” to look at. However, it is much narrower in scope than the
   current implementation, because it’s only going to reason from the
   (probably small) set of declarations that the user wrote alongside the
   conformance, so it’s more likely to be intentional. Note that this is again
   nudging programmers toward the style of programming where one puts one
   protocol conformance per extension, which is admittedly my personal
   preference.

*Thoughts?*

The thing that strikes me most about these is that the first two are
explicit declarations of intent: “In the absences of an explicit
declaration, deduce this associated type as follows,” while the third is
still extremely indirect. While it hints to the compiler about which
conformances’ associated type requirements we are trying to satisfy, it
never comes out and says straight out what the associated type should be,
even though it needs to be mentioned. As a generic programmer, I don’t
value the concision gained over the clarity lost, and I’d like to see the
solutions to these problems follow the explicit-declaration-of-intent
pattern. However, the code in #3 is not written by the protocol vendor,
and for me it is (at least currently) a stretch to think of breaking the
code of protocol users, so I grudgingly accept it.

If we were *really* starting from scratch I might suggest requiring that
conformances use the associated type name rather than some concrete type,
e.g.

extension MyCollection: RandomAccessCollection {
    typealias RandomAccessCollection.Index = Int
    var startIndex: Index { return contents.startIndex }
    var endIndex: Index { return contents.endIndex }
    subscript(index: Index) -> Element { return contents[index] }
  }

But I suspect we’re well past the point in the language’s evolution where
that sort of change is possible.

As for migration of protocol user code, I think we’d need to run both the
new and the old slow inference in the migrator and flag any differences. I
don’t know what to do about protocol vendors’ code though.

I think this approach is more predictable and more implementable than the
current model. I’m curious whether the above makes sense to someone other
than me, and whether it covers existing use cases well enough. Thoughts?

Well, covering the use cases is definitely still a concern for me. I
don’t think we’ll know for sure until we try it, but have you thought about
how to migrate each piece of code in the standard library? Does it cover
those cases?

-Dave

Sent from my iPad

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

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

Associated type defaults, which are specified with the associated type itself, e.g.,

  associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
Typealiases in (possibly constrained) protocol extensions, e.g.,

  extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
    typealias RandomAccessCollection.Indices = CountableRange<Index>
  }

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#default-implementations-in-protocols-&gt; are merely syntactic sugar.
Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

  extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
  }

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Thoughts?
I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

  - Doug

How does this work with retroactive conformance, especially where all the protocol requirements already exist on a type and an empty extension declares conformance? For example, suppose Module A declares a protocol with associated types, and Module B has a struct which naturally possesses all the required members to conform (maybe B handles Double concretely, while A can work with any FloatingPoint, or some such). As a client importing both modules and providing an empty extension to conform B’s struct to A’s protocol, will the associated types be inferred?

No, the associated types will not be inferred in this case. That will be a change in behavior (and a source compatibility regression).

Also, have you considered the possibility of allowing protocol authors to specify which types should be inferred from which requirements? For example Collection might demarcate “startIndex” as the source-of-truth for inferring “Index”, and “subscript (Index)->Element” as the source-of-truth for inferring “Element”.

This did come up a while ago, but it always felt like a hack… why infer from startIndex/endIndex rather than from “indices”, given that one set can be implemented in terms of the other with sufficiently-good inference? Why should the protocol author have to make sure a decision?

  - Doug

···

On Dec 1, 2017, at 11:42 AM, Nevin Brackett-Rozinsky <nevin.brackettrozinsky@gmail.com> wrote:
On Thu, Nov 30, 2017 at 7:28 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

What’s a Good Solution Look Like?
Our current system for associated type inference and associated type defaults is buggy and complicated.

Well, that’s the problem, then. Don’t worry, I won’t suggest that you simply fix the implementation, because even if there weren’t bugs and the system were predictable I’d still think we could improve the situation for users by making associated type default declarations more explicit.

The compiler gets it right often enough that people depend on it, but I don’t think anyone can reasonably be expected to puzzle out what’s going to happen, and this area is rife with bugs. If we were to design a new solution from scratch, what properties should it have?

It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them
It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults
It shouldn’t infer an inconsistent set of typealiases
It should be something that a competent Swift programmer could reason about when it will succeed, when and why it will fail, and what the resulting inferred typealiases would be
It should admit a reasonable implementation in the compiler that is performant and robust

• It should cover all of the existing use cases.
• It should not break code at this point.
• We should have a migration strategy for existing code that avoids traps like silent semantic changes.

My bullet is important to me; I don’t think existing use cases are (inherently) so complex that we can sacrifice almost any of them and still end up with a sufficiently useful system. At the very least, existing use cases provide the only guidance we really have as to what the feature should do.

I honestly don’t feel like a have a good handle on all of the use cases for associated type inference, and it’s not something we can simply search for on GitHub. But I think it covers most of them—and Matthew and Greg’s positive feedback helps my confidence here. The biggest potential issue, I think, is that we’ll no longer infer associated types from default implementations, which protocol vendors might be relying on.

I think we need to acknowledge that my second bullet is unattainable, at least if we want to improve type checking performance. Not breaking any code means that given any existing code, the compiler would have to explore the same solution space it currently does, and come up with the same answers. Improving performance would require new declarations to use totally optional explicit syntax to prevent some explorations, and that’s an untenable user experience.

Yes, I agree.

Which brings me to my third bullet: unless we are willing to break the code of protocol users (as opposed to vendors) we need to ensure that vendors can confidently convert code to use the new system without changing semantics.

Yeah, (2) below is basically that feature.

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

Associated type defaults, which are specified with the associated type itself, e.g.,

  associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
Typealiases in (possibly constrained) protocol extensions, e.g.,

  extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
    typealias RandomAccessCollection.Indices = CountableRange<Index>
  }

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#default-implementations-in-protocols-&gt; are merely syntactic sugar.
Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

  extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
  }

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Thoughts?

The thing that strikes me most about these is that the first two are explicit declarations of intent: “In the absences of an explicit declaration, deduce this associated type as follows,” while the third is still extremely indirect. While it hints to the compiler about which conformances’ associated type requirements we are trying to satisfy, it never comes out and says straight out what the associated type should be, even though it needs to be mentioned. As a generic programmer, I don’t value the concision gained over the clarity lost, and I’d like to see the solutions to these problems follow the explicit-declaration-of-intent pattern. However, the code in #3 is not written by the protocol vendor, and for me it is (at least currently) a stretch to think of breaking the code of protocol users, so I grudgingly accept it.

Sums up my feelings about #3 pretty well.

If we were really starting from scratch I might suggest requiring that conformances use the associated type name rather than some concrete type, e.g.

extension MyCollection: RandomAccessCollection {
    typealias RandomAccessCollection.Index = Int
    var startIndex: Index { return contents.startIndex }
    var endIndex: Index { return contents.endIndex }
    subscript(index: Index) -> Element { return contents[index] }
  }

But I suspect we’re well past the point in the language’s evolution where that sort of change is possible.

I’d like to *allow* that, for all declarations that are meant to conform to a protocol, but we can’t (and IMO shouldn’t) require it.

As for migration of protocol user code, I think we’d need to run both the new and the old slow inference in the migrator and flag any differences. I don’t know what to do about protocol vendors’ code though.

Yeah. We might simply need to run the old inference in Swift 4 mode when the new inference doesn’t succeed, and warn + Fix-It the missing typealiases when the old succeeds but the new fails.

I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

Well, covering the use cases is definitely still a concern for me. I don’t think we’ll know for sure until we try it, but have you thought about how to migrate each piece of code in the standard library? Does it cover those cases?

I’ve looked at the various defaulted associated types in the Sequence/Collection hierarchy, and I think they’ll work better with this scheme than they do currently. Honestly, I think I have to go implement it to see how things work out.

  - Doug

···

On Dec 2, 2017, at 9:23 PM, Dave Abrahams <dabrahams@apple.com> wrote:
On Nov 30, 2017, at 2:28 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Many of the associated-type inference bugs I’ve seen were from people expecting something like (3), but the current implementation either fails to infer anything (the common case!) or we get inference from some seemingly-unrelated place. I included (3) specifically because I think taking away (3) will break source compatibility significantly (as Greg suggests)… and despite the fact that the complexity of implementation for (3) is fairly high.

  - Doug

···

On Dec 1, 2017, at 10:07 AM, Greg Titus <greg@omnigroup.com> wrote:

On Dec 1, 2017, at 9:11 AM, Ben Langmuir via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Hey Doug,

I'm very much in favour of reducing the scope of associated type inference. Can you outline why you believe that (3) is necessary? If I am following correctly, if we had (1) and (2) the only thing you'd need to add to the "minimal collection" implementation would be a typealias for `Element`, which seems reasonable to me.

Ben

If nothing else, dropping (3) would be source breaking for 90%+ of current associated type uses. Whereas even the very minimal inference in (3) probably brings that figure down to 1% or so (outside of the stdlib, which would need to adopt a bunch of (2)). Obviously these percentages are just my guesses and not based on any real survey, but certainly would be the case for all Swift code I’ve seen.

As Doug wrote, an approach that's essentially that was reviewed and
rejected in SE-0108. We already know that it's not acceptable to a great
proportion of the community.

···

On Sat, Dec 2, 2017 at 2:30 PM, Howard Lovatt via swift-evolution < swift-evolution@swift.org> wrote:

Definitely in favour of doing something, I always define the associated
types since I have had so much trouble with the inference.

Personally I would prefer just 1 and 2 and forget 3. I know this would
break a lot of code, but I think we should do that because it is the lesser
of the evils.

We also know that the current situation isn’t acceptable to a great proposition of the community, that is why we are still discussing the issue!

A notable example of reversal of an evolution decision is String’s conformance to Collection. Which I think on the 2nd attempt was a much better decision.

For requiring typedefs for associated types, a fix it and error would be quite successful, e.g. Xcode already suggests the typedefs (which I currently accept before letting Xcode insert blanks for the missing methods etc.).

-- Howard.

···

On 3 Dec 2017, at 8:15 am, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sat, Dec 2, 2017 at 2:30 PM, Howard Lovatt via swift-evolution <swift-evolution@swift.org> wrote:
Definitely in favour of doing something, I always define the associated types since I have had so much trouble with the inference.

Personally I would prefer just 1 and 2 and forget 3. I know this would break a lot of code, but I think we should do that because it is the lesser of the evils.

As Doug wrote, an approach that's essentially that was reviewed and rejected in SE-0108. We already know that it's not acceptable to a great proportion of the community.

Would this help sorting out the behavior of typealiases in constrained extensions?

Sadly, no.

If not, please ignore the following and accept my apologies for posting OT.

Typealiases in constrained extensions are - and have been, for a long time - very broken.
The following program (which is clearly crazy in several ways) compiles and runs using the latest version of the compiler:

struct S<T> {
  var v: This
}
extension S where T == Int {
  typealias This = Is
}
extension S where T == Bool {
  typealias Is = Fine
}
extension S where T == String {
  typealias Fine = T
}
let x = S<Float80>(v: "uh")
print(x.v) // uh

( SR-5440 )
The current behavior is so allowing and strange that I'm having trouble seeing what the correct behavior would be if things worked as intended.

I’d said that “var v: This”, “typealias This = Is”, and “typealias Is = Fine” are ill-formed and the compiler should reject them. You should only be able to use types from another extension if your extra constraints imply the constraints of that extension. I *think* it’s actually a simple model, but it didn’t get implemented.

For example should the following program still compile, and if so, should the last line also compile (if uncommented)?

protocol P {
    associatedtype A = Int
    associatedtype B = Bool
    typealias C = Float
}
extension P where B == A {
    typealias C = String
}

I think this should be ill-formed, because we shouldn’t allow two typealiases with the same name to “overload” within the same type.

struct S<A, B> : P {
    var v: (A, B, C)
}
extension S where A == Int, B == Bool {
    typealias C = [String]
}
let s1 = S(v: (1, true, [""]))
// let s2 = S(v: ("a", "b", "c")) // Not (currently) ok.

Again, sorry for the noise if this is unrelated to the discussion.

  - Doug

···

On Dec 3, 2017, at 2:39 PM, Jens Persson <jens@bitcycle.com> wrote:

/Jens

On Sun, Dec 3, 2017 at 6:23 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Nov 30, 2017, at 2:28 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hello Swift community,

Associated type inference, which is the process by which the Swift compiler attempts to infer typealiases to satisfy associated-type requirements based on other requirements, has caused both implementation problems and user confusion for a long time. Some of you might remember a previous (failed) attempt to remove this feature from the Swift language, in SE-0108 “Remove associated type inference”. <https://github.com/apple/swift-evolution/blob/master/proposals/0108-remove-assoctype-inference.md&gt;

I’m not sure we can remove this feature outright (i.e., the concerns that sank that proposal are still absolutely valid), because it is so very convenient and a lot of user code likely depends on it in some form or other. So, here I’d like to describe the uses of the feature, its current (very problematic) implementation approach, and a half-baked proposal to narrow the scope of associated type inference to something that I think is more tractable. I need help with the design of this feature, because I feel like it’s going to be a delicate balance between implementability and expressiveness.

Aloha, Doug!

A Motivating Example
As a motivating example, let’s consider a “minimal” random access collection:

struct MyCollection<T> {
    var contents: [T]
}

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

This is actually pretty awesome: by providing just two properties and a subscript, we get the full breadth of the random access collection API! This is relying heavily on associated type inference (for associated type requirements) and default implementations specified on protocol extensions. Without associated type inference, we would have had to write:

extension MyCollection: RandomAccessCollection {
    typealias Element = T
    typealias Index = Int
    typealias Indices = CountableRange<Int>
    typealias Iterator = IndexingIterator<MyCollection<T>>
    typealias SubSequence = RandomAccessSlice<MyCollection<T>>
    
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

where the bolded typealiases are currently inferred. It was worse back when we reviewed SE-0108, because IIRC there were a few underscored associated types (e.g., _Element) that have since been removed. Still, that’s a bit of additional work to define a “minimal” collection, and requires quite a bit more understanding: how do I know to choose IndexingIterator, and CountableRange, and RandomAccessSlice?

The issue would get worse with, e.g., SE-0174 “Change filter to return an associated type” <https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md&gt;, which adds an associated type Filtered that almost nobody will ever customize, and isn’t really fundamental to the way collections work. Adding Filtered to the standard library would be a source-breaking change, because users would have to write a typealias giving it its default.

Associated Type Defaults
One of the ways in which we avoid having to specify typealiases is to use associated type defaults. For example, the standard library contains associated type defaults for Indices, Iterator, and SubSequence. Let’s focus on Indices:

protocol Collection : Sequence {
  associatedtype Indices = DefaultIndices<Self>
  // ...
}

protocol BidirectionalCollection : Collection {
  associatedtype Indices = DefaultBidirectionalIndices<Self>
  // ...
}

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Indices = DefaultRandomAccessIndices<Self>
  // ...
}

The basic idea here is that different protocols in the hierarchy provide different defaults, and you presumably want the default from the most specific protocol. If I define a type and make it conform to BidirectionalCollection, I’d expect to get DefaultBidirectionalIndices<Self> for Indices. If a define a type and make it conform to RandomAccessIterator, I’d expect to get DefaultRandomAccessIndices<Self>.

(Aside: DefaultRandomAccessIndices and DefaultBidirectionalIndices got collapsed into DefaultIndices now that we have conditional conformances for the standard library <https://github.com/apple/swift/pull/12913&gt;, but the issues I’m describing remain).

Associated type defaults seem like a reasonable feature that fits well enough into the design. However, it’s not the only thing in place with our MyCollection example, for which Indices was inferred to CountableRange. How’s that happen?

Associated Type Inference
Associated type inference attempts to look at the requirements of a protocol, and then looks into the conforming type for declarations that might satisfy those requirements, and infers associated types from the types of those declarations. Let’s look at some examples. RandomAccessCollection has some requirements that mention the Index and Element types:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Element
  associatedtype Index

  var startIndex: Index { get }
  var endIndex: Index { get }
  subscript (i: Index) -> Element { get }
}

Associated type inference wil try to satisfy those requirements for MyCollection, and will find these declarations:

extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
}

and match them up. From startIndex, we infer Index := Int. From endIndex, we infer Index := Int. From subscript, we infer Index := Int and Element := T. Those results are all consistent, so we’ve properly inferred Index and Element. Yay.

Associated type inference often has to deal with ambiguities. For example, there is an extension of Collection that provides a range subscript operator:

extension Collection {
  subscript (bounds: Range<Index>) -> Slice<Self> { … }
}

When we look at that and match it to the subscript requirement in RandomAccessCollection (remembering that argument labels aren’t significant for subscripts by default!), we infer Index := Range<Index> (admittedly weird) and Element := Slice<Self> (could be legitimate). We have to discard this candidate because the deduction from startIndex/endIndex (Index := Int) collides with this deduction (Index := Range<Index>).

In our initial example, we saw that Indices was inferred to CountableRange<Int>. Let’s look at another slice of the RandomAccessCollection protocol that’s relevant to this associated type:

protocol RandomAccessCollection : BidirectionalCollection {
  associatedtype Index
  associatedtype Indices: RandomAccessCollection where Indices.Element == Index

  var indices: Indices { get }
}

We will match that requirement for an “indices” property against a member of a constrained protocol extension of RandomAccessCollection:

extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance, Indices == CountableRange<Index> {
  public var indices: CountableRange<Index> {
    return startIndex..<endIndex
  }
}

Associated type inference can determine here that Indices := CountableRange<Index>, but only when Index: Strideable and Index.Stride == IndexDistance. In other words, there are a whole bunch of other constraints to verify before we can accept this inference for Indices.

So, what’s the problem? ;-)

What’s a Good Solution Look Like?
Our current system for associated type inference and associated type defaults is buggy and complicated.

Well, that’s the problem, then. Don’t worry, I won’t suggest that you simply fix the implementation, because even if there weren’t bugs and the system were predictable I’d still think we could improve the situation for users by making associated type default declarations more explicit.

The compiler gets it right often enough that people depend on it, but I don’t think anyone can reasonably be expected to puzzle out what’s going to happen, and this area is rife with bugs. If we were to design a new solution from scratch, what properties should it have?

It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them
It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults
It shouldn’t infer an inconsistent set of typealiases
It should be something that a competent Swift programmer could reason about when it will succeed, when and why it will fail, and what the resulting inferred typealiases would be
It should admit a reasonable implementation in the compiler that is performant and robust

• It should cover all of the existing use cases.
• It should not break code at this point.
• We should have a migration strategy for existing code that avoids traps like silent semantic changes.

My bullet is important to me; I don’t think existing use cases are (inherently) so complex that we can sacrifice almost any of them and still end up with a sufficiently useful system. At the very least, existing use cases provide the only guidance we really have as to what the feature should do.

I think we need to acknowledge that my second bullet is unattainable, at least if we want to improve type checking performance. Not breaking any code means that given any existing code, the compiler would have to explore the same solution space it currently does, and come up with the same answers. Improving performance would require new declarations to use totally optional explicit syntax to prevent some explorations, and that’s an untenable user experience.

Which brings me to my third bullet: unless we are willing to break the code of protocol users (as opposed to vendors) we need to ensure that vendors can confidently convert code to use the new system without changing semantics.

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

Associated type defaults, which are specified with the associated type itself, e.g.,

  associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
Typealiases in (possibly constrained) protocol extensions, e.g.,

  extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
    typealias RandomAccessCollection.Indices = CountableRange<Index>
  }

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#default-implementations-in-protocols-&gt; are merely syntactic sugar.
Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

  extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
  }

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Thoughts?

The thing that strikes me most about these is that the first two are explicit declarations of intent: “In the absences of an explicit declaration, deduce this associated type as follows,” while the third is still extremely indirect. While it hints to the compiler about which conformances’ associated type requirements we are trying to satisfy, it never comes out and says straight out what the associated type should be, even though it needs to be mentioned. As a generic programmer, I don’t value the concision gained over the clarity lost, and I’d like to see the solutions to these problems follow the explicit-declaration-of-intent pattern. However, the code in #3 is not written by the protocol vendor, and for me it is (at least currently) a stretch to think of breaking the code of protocol users, so I grudgingly accept it.

If we were really starting from scratch I might suggest requiring that conformances use the associated type name rather than some concrete type, e.g.

extension MyCollection: RandomAccessCollection {
    typealias RandomAccessCollection.Index = Int
    var startIndex: Index { return contents.startIndex }
    var endIndex: Index { return contents.endIndex }
    subscript(index: Index) -> Element { return contents[index] }
  }

But I suspect we’re well past the point in the language’s evolution where that sort of change is possible.

As for migration of protocol user code, I think we’d need to run both the new and the old slow inference in the migrator and flag any differences. I don’t know what to do about protocol vendors’ code though.

I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

Well, covering the use cases is definitely still a concern for me. I don’t think we’ll know for sure until we try it, but have you thought about how to migrate each piece of code in the standard library? Does it cover those cases?

-Dave

Sent from my iPad

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

What’s a Good Solution Look Like?
Our current system for associated type inference and associated type defaults is buggy and complicated.

Well, that’s the problem, then. Don’t worry, I won’t suggest that you simply fix the implementation, because even if there weren’t bugs and the system were predictable I’d still think we could improve the situation for users by making associated type default declarations more explicit.

The compiler gets it right often enough that people depend on it, but I don’t think anyone can reasonably be expected to puzzle out what’s going to happen, and this area is rife with bugs. If we were to design a new solution from scratch, what properties should it have?

It should allow the author of a protocol to provide reasonable defaults, so the user doesn’t have to write them
It shouldn’t require users to write typealiases for “obvious” cases, even when they aren’t due to defaults
It shouldn’t infer an inconsistent set of typealiases
It should be something that a competent Swift programmer could reason about when it will succeed, when and why it will fail, and what the resulting inferred typealiases would be
It should admit a reasonable implementation in the compiler that is performant and robust

• It should cover all of the existing use cases.
• It should not break code at this point.
• We should have a migration strategy for existing code that avoids traps like silent semantic changes.

My bullet is important to me; I don’t think existing use cases are (inherently) so complex that we can sacrifice almost any of them and still end up with a sufficiently useful system. At the very least, existing use cases provide the only guidance we really have as to what the feature should do.

I honestly don’t feel like a have a good handle on all of the use cases for associated type inference, and it’s not something we can simply search for on GitHub. But I think it covers most of them—and Matthew and Greg’s positive feedback helps my confidence here. The biggest potential issue, I think, is that we’ll no longer infer associated types from default implementations, which protocol vendors might be relying on.

Hi Doug. FWIW, I always explicitly state defaults in protocol declarations so inference in default implementations is something that I don’t use. I think it’s very reasonable to require explicit declaration of the default.

There are a few areas where I can imagine a real impact. The main one that I don’t think has been discussed yet is when conformance is declared in an extension but inference would need to consider a member declared in the original declaration. This is likely to be pretty common given the requirement to declare stored properties in the original declaration and the common pattern of declaring conformance in an extension. If implementation is feasible you might want to also consider the original declaration for a conformance that is stated in the same module (or even just the same file).

I think we need to acknowledge that my second bullet is unattainable, at least if we want to improve type checking performance. Not breaking any code means that given any existing code, the compiler would have to explore the same solution space it currently does, and come up with the same answers. Improving performance would require new declarations to use totally optional explicit syntax to prevent some explorations, and that’s an untenable user experience.

Yes, I agree.

Which brings me to my third bullet: unless we are willing to break the code of protocol users (as opposed to vendors) we need to ensure that vendors can confidently convert code to use the new system without changing semantics.

Yeah, (2) below is basically that feature.

A Rough Proposal
I’ve been thinking about this for a bit, and I think there are three ways in which we should be able to infer an associated type witness:

Associated type defaults, which are specified with the associated type itself, e.g.,

  associatedtype Indices = DefaultIndices<Self>

These are easy to reason about for both the programmer and the compiler.
Typealiases in (possibly constrained) protocol extensions, e.g.,

  extension RandomAccessCollection where Index : Strideable, Index.Stride == IndexDistance {
    typealias RandomAccessCollection.Indices = CountableRange<Index>
  }

I’m intentionally using some odd ‘.’ syntax here to indicate that this typealias is intended only to be found when trying to satisfy an associated type requirement, and is not a general typealias that could be found by normal name lookup. Let’s set the syntax bike shed aside for the moment. The primary advantage of this approach (vs. inferring Indices from “var Indices: CountableRange<Index>” in a constrained protocol extension) is that there’s a real typealias declaration that compiler and programmer alike can look at and reason about based just on the name “Indices”.

Note that this mechanism technically obviates the need for (1), in the same sense that default implementations in protocols are merely syntactic sugar.
Declarations within the nominal type declaration or extension that declares conformance to the protocol in question. This is generally the same approach as described in “associated type inference” above, where we match requirements of the protocol against declarations that could satisfy those requirements and infer associated types from there. However, I want to turn it around: instead of starting with the requirements of the protocol any looking basically anywhere in the type or any protocol to which it conforms (for implementations in protocol extensions), start with the declarations that the user explicitly wrote at the point of the conformance and look for requirements they might satisfy. For example, consider our initial example:

  extension MyCollection: RandomAccessCollection {
    var startIndex: Int { return contents.startIndex }
    var endIndex: Int { return contents.endIndex }
    subscript(index: Int) -> T { return contents[index] }
  }

Since startIndex, endIndex, and subscript(_:) are declared in the same extension that declares conformance to RandomAccessIterator, we should look for requirements with the same name as these properties and subscript within RandomAccessCollection (or any protocol it inherits) and infer Index := Int and Element := T by matching the type signatures. This is still the most magical inference rule, because there is no declaration named “Index” or “Element” to look at. However, it is much narrower in scope than the current implementation, because it’s only going to reason from the (probably small) set of declarations that the user wrote alongside the conformance, so it’s more likely to be intentional. Note that this is again nudging programmers toward the style of programming where one puts one protocol conformance per extension, which is admittedly my personal preference.

Thoughts?

The thing that strikes me most about these is that the first two are explicit declarations of intent: “In the absences of an explicit declaration, deduce this associated type as follows,” while the third is still extremely indirect. While it hints to the compiler about which conformances’ associated type requirements we are trying to satisfy, it never comes out and says straight out what the associated type should be, even though it needs to be mentioned. As a generic programmer, I don’t value the concision gained over the clarity lost, and I’d like to see the solutions to these problems follow the explicit-declaration-of-intent pattern. However, the code in #3 is not written by the protocol vendor, and for me it is (at least currently) a stretch to think of breaking the code of protocol users, so I grudgingly accept it.

Sums up my feelings about #3 pretty well.

If we were really starting from scratch I might suggest requiring that conformances use the associated type name rather than some concrete type, e.g.

extension MyCollection: RandomAccessCollection {
    typealias RandomAccessCollection.Index = Int
    var startIndex: Index { return contents.startIndex }
    var endIndex: Index { return contents.endIndex }
    subscript(index: Index) -> Element { return contents[index] }
  }

But I suspect we’re well past the point in the language’s evolution where that sort of change is possible.

I’d like to *allow* that, for all declarations that are meant to conform to a protocol, but we can’t (and IMO shouldn’t) require it.

IMO we should allow this for all protocol requirements. I used C# for a while many years ago and it proved very useful in a few cases.

···

Sent from my iPad

On Dec 7, 2017, at 5:27 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 2, 2017, at 9:23 PM, Dave Abrahams <dabrahams@apple.com> wrote:

On Nov 30, 2017, at 2:28 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

As for migration of protocol user code, I think we’d need to run both the new and the old slow inference in the migrator and flag any differences. I don’t know what to do about protocol vendors’ code though.

Yeah. We might simply need to run the old inference in Swift 4 mode when the new inference doesn’t succeed, and warn + Fix-It the missing typealiases when the old succeeds but the new fails.

I think this approach is more predictable and more implementable than the current model. I’m curious whether the above makes sense to someone other than me, and whether it covers existing use cases well enough. Thoughts?

Well, covering the use cases is definitely still a concern for me. I don’t think we’ll know for sure until we try it, but have you thought about how to migrate each piece of code in the standard library? Does it cover those cases?

I’ve looked at the various defaulted associated types in the Sequence/Collection hierarchy, and I think they’ll work better with this scheme than they do currently. Honestly, I think I have to go implement it to see how things work out.

  - Doug

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