[Proposal draft] Conditional conformances


(Douglas Gregor) #1

Conditional conformances

Proposal: SE-NNNN <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/NNNN-conditional-conformances.md>
Author: Doug Gregor <https://github.com/DougGregor>
Review Manager: TBD
Status: Awaiting review
During the review process, add the following fields as needed:

Decision Notes: Rationale <https://lists.swift.org/pipermail/swift-evolution/>, Additional Commentary <https://lists.swift.org/pipermail/swift-evolution/>
Bugs: SR-NNNN <https://bugs.swift.org/browse/SR-NNNN>, SR-MMMM <https://bugs.swift.org/browse/SR-MMMM>
Previous Revision: 1 <https://github.com/apple/swift-evolution/blob/...commit-ID.../proposals/NNNN-filename.md>
Previous Proposal: SE-XXXX <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/XXXX-filename.md>
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#introduction>Introduction

Conditional conformances express the notion that a generic type will conform to a particular protocol only when it's type arguments meet certain requirements. For example, the Array collection can implement the Equatable protocol only when its elements are themselves Equatable, which can be expressed via the following conditional conformance on Equatable:

extension Array: Equatable where Element: Equatable {
  static func ==(lhs: Array<T>, rhs: Array<T>) -> Bool { ... }
}
This feature is part of the generics manifesto <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-> because it's something that fits naturally into the generics model and is expected to have a high impact on the Swift standard library.

Swift-evolution thread: TBD: Discussion thread topic for that proposal <https://lists.swift.org/pipermail/swift-evolution/>
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#motivation>Motivation

Conditional conformances address a hole in the composability of the generics system. Continuing the Array example from above, it's always been the case that one could use the == operator on two arrays of Equatable type, e.g., [Int]() == [Int]() would succeed. However, it doesn't compose: arrays of arrays of Equatable types cannot be compared (e.g.,[Int] <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals>== [Int] <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals>will fail to compile) because, even though there is an==for arrays of Equatabletype, the arrays themselves are neverEquatable`.

Conditional conformances are particularly powerful when building generic adapter types, which are intended to reflect the capabilities of their type arguments. For example, consider the "lazy" functionality of the Swift standard library's collections: using the lazy member of a sequence produces a lazy adapter that conforms to the Sequence protocol, while using the lazy member of a collection produces a lazy adapter that conforms to the Collection protocol. In Swift 3, the only way to model this is with different types. For example, the Swift standard library has four similar generic types to handle a lazy collection: LazySequence, LazyCollection, LazyBidirectionalCollection, and LazyRandomAccessCollection. The Swift standard library uses overloading of the lazy property to decide among these:

extension Sequence {
  var lazy: LazySequence<Self> { ... }
}

extension Collection {
  var lazy: LazyCollection<Self> { ... }
}

extension BidirectionalCollection {
  var lazy: LazyBidirectionalCollection<Self> { ... }
}

extension RandomAccessCollection {
  var lazy: LazyRandomAccessCollection<Self> { ... }
}
This approach causes an enormous amount of repetition, and doesn't scale well because each more-capable type has to re-implement (or somehow forward the implementation of) all of the APIs of the less-capable versions. With conditional conformances, one can provide a single generic wrapper type whose basic requirements meet the lowest common denominator (e.g., Sequence), but which scale their capabilities with their type argument (e.g., the LazySequence conforms to Collection when the type argument does, and so on).

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#proposed-solution>Proposed solution

In a nutshell, the proposed solution is to allow a constrained extension of a struct, enum, or class to declare protocol conformances. No additional syntax is necessary for this change, because it already exists in the grammar; rather, this proposal removes the limitation that results in the following error:

t.swift:1:1: error: extension of type 'Array' with constraints cannot have an inheritance clause
extension Array: Equatable where Element: Equatable { }
^ ~~~~~~~~~
Conditional conformances can only be used when the additional requirements of the constrained extension are satisfied. For example, given the aforementioned Array conformance to Equatable:

func f<T: Equatable>(_: T) { ... }

struct NotEquatable { }

func test(a1: [Int], a2: [NotEquatable]) {
  f(a1) // okay: [Int] conforms to Equatable because Int conforms to Equatable
  f(a2) // error: [NotEquatable] does not conform to Equatable because NotEquatable has no conformance to Equatable
}
Conditional conformances also have a run-time aspect, because a dynamic check for a protocol conformance might rely on the evaluation of the extra requirements needed to successfully use a conditional conformance. For example:

protocol P {
  func doSomething()
}

struct S: P {
  func doSomething() { print("S") }
}

// Array conforms to P if it's element type conforms to P
extension Array: P where Element: P {
  func doSomething() {
    for value in self {
      value.doSomething()
    }
  }
}

// Dynamically query and use conformance to P.
func doSomethingIfP(_ value: Any) {
  if let p = value as? P {
    p.doSomething()
  } else {
    print("Not a P")
  }
}

doSomethingIfP([S(), S(), S()]) // prints "S" three times
doSomethingIfP([1, 2, 3]) // prints "Not a P"
The if-let in doSomethingIfP(_:slight_smile: dynamically queries whether the type stored in value conforms to the protocol P. In the case of an Array, that conformance is conditional, which requires another dynamic lookup to determine whether the element type conforms to P: in the first call to doSomethingIfP(_:), the lookup finds the conformance of S to P. In the second case, there is no conformance of Int to P, so the conditional conformance cannot be used. The desire for this dynamic behavior motivates some of the design decisions in this proposal.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#detailed-design>Detailed design

Most of the semantics of conditional conformances are obvious. However, there are a number of issues (mostly involving multiple conformances) that require more in-depth design.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#disallow-overlapping-conformances>Disallow overlapping conformances

With conditional conformances, it is possible to express that a given generic type can conform to the same protocol in two different ways, depending on the capabilities of its type arguments. For example:

struct SomeWrapper<Wrapped> {
  let wrapped: Wrapped
}

protocol HasIdentity {
  static func ===(lhs: Self, rhs: Self) -> Bool
}

extension SomeWrapper: Equatable where Wrapped: Equatable {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
}

extension SomeWrapper: Equatable where Wrapped: HasIdentity {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped === rhs.wrapped
  }
}
Note that, for an arbitrary type T, there are four potential answers to the question of whether SomeWrapper<T> conforms to Equatable:

No, it does not conform because T is neither Equatable nor HasIdentity.
Yes, it conforms via the first extension of SomeWrapper because T conforms to Equatable.
Yes, it conforms via the second extension of SomeWrapper because T conforms to HasIdentity.
Ambiguity, because T conforms to both Equatable and HasIdentity.
It is due to the possibility of #4 occurring that we refer to the two conditional conformances in the example as overlapping. There are designs that would allow one to address the ambiguity, for example, by writing a third conditional conformance that addresses #4:

// Possible tie-breaker conformance
extension SomeWrapper: Equatable where Wrapped: Equatable & HasIdentity, {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
}
The design is consistent, because this third conditional conformance is more specialized the either of the first two conditional conformances, meaning that its requirements are a strict superset of the requirements of those two conditional conformances. However, there are a few downsides to such a system:

To address all possible ambiguities, one has to write a conditional conformance for every plausible combination of overlapping requirements. To statically resolve all ambiguities, one must also cover nonsensical combinations where the two requirements are mutually exclusive (or invent a way to state mutual-exclusivity).
It is no longer possible to uniquely say what is required to make a generic type conform to a protocol, because there might be several unrelated possibilities. This makes reasoning about the whole system more complex, because it admits divergent interfaces for the same generic type based on their type arguments. At its extreme, this invites the kind of cleverness we've seen in the C++ community with template metaprogramming, which is something Swift has sought to avoid.
All of the disambiguation machinery required at compile time (e.g., to determine whether one conditional conformance is more specialized than another to order them) also needs to implements in the run-time, as part of the dynamic casting machinery. One must also address the possibility of ambiguities occurring at run-time. This is both a sharp increase in the complexity of the system and a potential run-time performance hazard.
For these reasons, this proposal bans overlapping conformances entirely. While the resulting system is less flexible than one that allowed overlapping conformances, the gain in simplicity in this potentially-confusing area is well worth the cost. Moreover, this ban follows with existing Swift rules regarding multiple conformances, which prohibit the same type from conforming to the same protocol in two different ways:

protocol P { }

struct S : P { }
extension S : P { } // error: S already conforms to P
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#implied-conditional-conformances>Implied conditional conformances

Stating conformance to a protocol implicitly states conformances to any of the protocols that it inherits. This is the case in Swift today, although most developers likely don't realize the rules it follows. For example:

protocol P { }
protocol Q : P { }
protocol R : P { }

struct X1 { }
struct X2 { }
struct X3 { }

extension X1: Q { } // implies conformance to P

extension X2: Q { } // would imply conformance to P, but...
extension X2: P { } // explicitly-stated conformance to P "wins"

extension X3: Q { } // implies conformance to P
extension X3: R { } // also implies conformance to P
                     // one will "win"; which is unspecified
With conditional conformances, the question of which extension "wins" the implied conformance begins to matter, because the extensions might have different constraints on them. For example:

struct X4<T> { }

extension X4: Q where T: Q { } // implies conformance to P
extension X4: R where T: R { } // error: implies overlapping conformance to P
Both of these constrained extensions imply a conformance to P, but the actual P implied conformances to P are overlapping and, therefore, result in an error.

However, in cases where there is a reasonable ordering between the two constrained extensions (i.e., one is more specialized than the other), the less specialized constrained extension should "win" the implied conformance. Continuing the example from above:

protocol S: R { }

struct X5<T> { }

extension X5: R where T: R { } // "wins" implied conformance to P, because
extension X5: S where T: S { } // the extension where "T: S" is more specialized
                                // than the one where "T: R"
Thus, the rule for placing implied conformances is to pick the least specialized extension that implies the conformance. If there is more than one such extension, then either:

All such extensions are not constrained extensions (i.e., they have no requirements beyond what the type requires), in which case Swift can continue to choose arbitrarily among the extensions, or
All such extensions are constrained extensions, in which case the program is ill-formed due to the ambiguity. The developer can explicitly specify conformance to the protocol to disambiguate.
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#overloading-across-constrained-extensions>Overloading across constrained extensions

One particularly important aspect of the placement rule for implied conformances is that it affects which declarations are used to satisfy a particular requirement. For example:

protocol P {
  func f()
}

protocol Q: P { }
protocol R: Q { }

struct X1<T> { }

extension X1: Q where T: Q { // note: implied conformance to P here
  func f() {
    // #1: basic implementation of 'f()'
  }
}

extension X1: R where T: R {
  func f() {
    // #2: superfast implementation of f() using some knowledge of 'R'
  }
}

struct X2: R {
  func f() { }
}

(X1<X2>() as P).f() // calls #1, which was used to satisfy the requirement for 'f'
X1<X2>().f() // calls #2, which is preferred by overload resolution
Effectively, when satisfying a protocol requirement, one can only choose from members of the type that are guaranteed to available within the extension with which the conformance is associated. In this case, the conformance to P is placed on the first extension of X1, so the only f() that can be considered is the f() within that extension: the f() in the second extension won't necessarily always be available, because T may not conform to R. Hence, the call that treats an X1<X2>as a P gets the first implementation of X1.f(). When using the concrete type X1<X2>, where X2 conforms to R, both X.f() implementations are visible... and the second is more specialized.

Technically, this issue is no different from surprises where (e.g.) a member added to a concrete type in a different module won't affect an existing protocol conformance. The existing ideas to mediate these problems---warning for nearly-matching functions when they are declared in concrete types, for example---will likely be sufficient to help surprised users. That said, this proposal may increase the likelihood of such problems showing up.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#source-compatibility>Source compatibility

From the language perspective, conditional conformances are purely additive. They introduce no new syntax, but instead provide semantics for existing syntax---an extension that both declares a protocol conformance and has a where clause---whose use currently results in a type checker failure. That said, this is a feature that is expected to be widely adopted within the Swift standard library, which may indirectly affect source compatibility.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#effect-on-abi-stability>Effect on ABI Stability

As noted above, there are a number of places where the standard library is expected to adopt this feature, which fall into two classes:

Improve composability: the example in the introduction <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/Introduction> made Array conform to Equatable when its element type does; there are many places in the Swift standard library that could benefit from this form of conditional conformance, particularly so that collections and other types that contain values (e.g., Optional) can compose better with generic algorithms. Most of these changes won't be ABI- or source-breaking, because they're additive.
Eliminating repetition: the lazy wrappers described in the motivation <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/motivation> section could be collapsed into a single wrapper with several conditional conformances. A similar refactoring could also be applied to the range abstractions and slice types in the standard library, making the library itself simpler and smaller. All of these changes are potentially source-breaking and ABI-breaking, because they would remove types that could be used in Swift 3 code. However, there are mitigations: generic typealiases could provide source compatibility to Swift 3 clients, and the ABI-breaking aspect is only relevant if conditional conformances and the standard library changes they imply aren't part of Swift 4.
Aside from the standard library, conditional conformances have an impact on the Swift runtime, which will require specific support to handle dynamic casting. If that runtime support is not available once ABI stability has been declared, then introducing conditional conformances in a later language version either means the feature cannot be deployed backward or that it would provide only more limited, static behavior when used on older runtimes. Hence, there is significant motivation for doing this feature as part of Swift 4. Even if we waited to introduce conditional conformances, we would want to include a hook in the runtime to allow them to be implemented later, to avoid future backward-compatibility issues.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#alternatives-considered>Alternatives considered

The most common request related to conditional conformances is to allow a (constrained) protocol extension to declare conformance to a protocol. For example:

extension Collection: Equatable where Iterator.Element: Equatable {
  static func ==(lhs: Self, rhs: Self) -> Bool {
    // ...
  }
}
This protocol extension will make any Collection of Equatable elements Equatable, which is a powerful feature that could be put to good use. Introducing conditional conformances for protocol extensions would exacerbate the problem of overlapping conformances, because it would be unreasonable to say that the existence of the above protocol extension means that no type that conforms to Collection could declare its own conformance to Equatable, conditional or otherwise.


(Robert Widmann) #2

+1. I have one purely bureaucratic concern that I couldn't quite find answers to on a read through:

Orphan instances and more generally cross-module uniqueness of instances are not mentioned. What's the policy here? Are we locally unique with respect to imported modules or globally unique with respect to all importable modules?

~Robert Widmann

2016/09/26 20:18、Douglas Gregor via swift-evolution <swift-evolution@swift.org> のメッセージ:

···

Conditional conformances
Proposal: SE-NNNN
Author: Doug Gregor
Review Manager: TBD
Status: Awaiting review
During the review process, add the following fields as needed:

Decision Notes: Rationale, Additional Commentary
Bugs: SR-NNNN, SR-MMMM
Previous Revision: 1
Previous Proposal: SE-XXXX
Introduction

Conditional conformances express the notion that a generic type will conform to a particular protocol only when it's type arguments meet certain requirements. For example, the Array collection can implement the Equatable protocol only when its elements are themselves Equatable, which can be expressed via the following conditional conformance on Equatable:

extension Array: Equatable where Element: Equatable {
  static func ==(lhs: Array<T>, rhs: Array<T>) -> Bool { ... }
}
This feature is part of the generics manifesto because it's something that fits naturally into the generics model and is expected to have a high impact on the Swift standard library.

Swift-evolution thread: TBD: Discussion thread topic for that proposal

Motivation

Conditional conformances address a hole in the composability of the generics system. Continuing the Array example from above, it's always been the case that one could use the == operator on two arrays of Equatable type, e.g., [Int]() == [Int]() would succeed. However, it doesn't compose: arrays of arrays of Equatable types cannot be compared (e.g.,[Int]== [Int]will fail to compile) because, even though there is an==for arrays of Equatabletype, the arrays themselves are neverEquatable`.

Conditional conformances are particularly powerful when building generic adapter types, which are intended to reflect the capabilities of their type arguments. For example, consider the "lazy" functionality of the Swift standard library's collections: using the lazy member of a sequence produces a lazy adapter that conforms to the Sequence protocol, while using the lazy member of a collection produces a lazy adapter that conforms to the Collection protocol. In Swift 3, the only way to model this is with different types. For example, the Swift standard library has four similar generic types to handle a lazy collection: LazySequence, LazyCollection, LazyBidirectionalCollection, and LazyRandomAccessCollection. The Swift standard library uses overloading of the lazy property to decide among these:

extension Sequence {
  var lazy: LazySequence<Self> { ... }
}

extension Collection {
  var lazy: LazyCollection<Self> { ... }
}

extension BidirectionalCollection {
  var lazy: LazyBidirectionalCollection<Self> { ... }
}

extension RandomAccessCollection {
  var lazy: LazyRandomAccessCollection<Self> { ... }
}
This approach causes an enormous amount of repetition, and doesn't scale well because each more-capable type has to re-implement (or somehow forward the implementation of) all of the APIs of the less-capable versions. With conditional conformances, one can provide a single generic wrapper type whose basic requirements meet the lowest common denominator (e.g., Sequence), but which scale their capabilities with their type argument (e.g., the LazySequence conforms to Collection when the type argument does, and so on).

Proposed solution

In a nutshell, the proposed solution is to allow a constrained extension of a struct, enum, or class to declare protocol conformances. No additional syntax is necessary for this change, because it already exists in the grammar; rather, this proposal removes the limitation that results in the following error:

t.swift:1:1: error: extension of type 'Array' with constraints cannot have an inheritance clause
extension Array: Equatable where Element: Equatable { }
^ ~~~~~~~~~
Conditional conformances can only be used when the additional requirements of the constrained extension are satisfied. For example, given the aforementioned Array conformance to Equatable:

func f<T: Equatable>(_: T) { ... }

struct NotEquatable { }

func test(a1: [Int], a2: [NotEquatable]) {
  f(a1) // okay: [Int] conforms to Equatable because Int conforms to Equatable
  f(a2) // error: [NotEquatable] does not conform to Equatable because NotEquatable has no conformance to Equatable
}
Conditional conformances also have a run-time aspect, because a dynamic check for a protocol conformance might rely on the evaluation of the extra requirements needed to successfully use a conditional conformance. For example:

protocol P {
  func doSomething()
}

struct S: P {
  func doSomething() { print("S") }
}

// Array conforms to P if it's element type conforms to P
extension Array: P where Element: P {
  func doSomething() {
    for value in self {
      value.doSomething()
    }
  }
}

// Dynamically query and use conformance to P.
func doSomethingIfP(_ value: Any) {
  if let p = value as? P {
    p.doSomething()
  } else {
    print("Not a P")
  }
}

doSomethingIfP([S(), S(), S()]) // prints "S" three times
doSomethingIfP([1, 2, 3]) // prints "Not a P"
The if-let in doSomethingIfP(_:slight_smile: dynamically queries whether the type stored in value conforms to the protocol P. In the case of an Array, that conformance is conditional, which requires another dynamic lookup to determine whether the element type conforms to P: in the first call to doSomethingIfP(_:), the lookup finds the conformance of S to P. In the second case, there is no conformance of Int to P, so the conditional conformance cannot be used. The desire for this dynamic behavior motivates some of the design decisions in this proposal.

Detailed design

Most of the semantics of conditional conformances are obvious. However, there are a number of issues (mostly involving multiple conformances) that require more in-depth design.

Disallow overlapping conformances

With conditional conformances, it is possible to express that a given generic type can conform to the same protocol in two different ways, depending on the capabilities of its type arguments. For example:

struct SomeWrapper<Wrapped> {
  let wrapped: Wrapped
}

protocol HasIdentity {
  static func ===(lhs: Self, rhs: Self) -> Bool
}

extension SomeWrapper: Equatable where Wrapped: Equatable {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
}

extension SomeWrapper: Equatable where Wrapped: HasIdentity {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped === rhs.wrapped
  }
}
Note that, for an arbitrary type T, there are four potential answers to the question of whether SomeWrapper<T> conforms to Equatable:

No, it does not conform because T is neither Equatable nor HasIdentity.
Yes, it conforms via the first extension of SomeWrapper because T conforms to Equatable.
Yes, it conforms via the second extension of SomeWrapper because T conforms to HasIdentity.
Ambiguity, because T conforms to both Equatable and HasIdentity.
It is due to the possibility of #4 occurring that we refer to the two conditional conformances in the example as overlapping. There are designs that would allow one to address the ambiguity, for example, by writing a third conditional conformance that addresses #4:

// Possible tie-breaker conformance
extension SomeWrapper: Equatable where Wrapped: Equatable & HasIdentity, {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
}
The design is consistent, because this third conditional conformance is more specialized the either of the first two conditional conformances, meaning that its requirements are a strict superset of the requirements of those two conditional conformances. However, there are a few downsides to such a system:

To address all possible ambiguities, one has to write a conditional conformance for every plausible combination of overlapping requirements. To statically resolve all ambiguities, one must also cover nonsensical combinations where the two requirements are mutually exclusive (or invent a way to state mutual-exclusivity).
It is no longer possible to uniquely say what is required to make a generic type conform to a protocol, because there might be several unrelated possibilities. This makes reasoning about the whole system more complex, because it admits divergent interfaces for the same generic type based on their type arguments. At its extreme, this invites the kind of cleverness we've seen in the C++ community with template metaprogramming, which is something Swift has sought to avoid.
All of the disambiguation machinery required at compile time (e.g., to determine whether one conditional conformance is more specialized than another to order them) also needs to implements in the run-time, as part of the dynamic casting machinery. One must also address the possibility of ambiguities occurring at run-time. This is both a sharp increase in the complexity of the system and a potential run-time performance hazard.
For these reasons, this proposal bans overlapping conformances entirely. While the resulting system is less flexible than one that allowed overlapping conformances, the gain in simplicity in this potentially-confusing area is well worth the cost. Moreover, this ban follows with existing Swift rules regarding multiple conformances, which prohibit the same type from conforming to the same protocol in two different ways:

protocol P { }

struct S : P { }
extension S : P { } // error: S already conforms to P
Implied conditional conformances

Stating conformance to a protocol implicitly states conformances to any of the protocols that it inherits. This is the case in Swift today, although most developers likely don't realize the rules it follows. For example:

protocol P { }
protocol Q : P { }
protocol R : P { }

struct X1 { }
struct X2 { }
struct X3 { }

extension X1: Q { } // implies conformance to P

extension X2: Q { } // would imply conformance to P, but...
extension X2: P { } // explicitly-stated conformance to P "wins"

extension X3: Q { } // implies conformance to P
extension X3: R { } // also implies conformance to P
                     // one will "win"; which is unspecified
With conditional conformances, the question of which extension "wins" the implied conformance begins to matter, because the extensions might have different constraints on them. For example:

struct X4<T> { }

extension X4: Q where T: Q { } // implies conformance to P
extension X4: R where T: R { } // error: implies overlapping conformance to P
Both of these constrained extensions imply a conformance to P, but the actual P implied conformances to P are overlapping and, therefore, result in an error.

However, in cases where there is a reasonable ordering between the two constrained extensions (i.e., one is more specialized than the other), the less specialized constrained extension should "win" the implied conformance. Continuing the example from above:

protocol S: R { }

struct X5<T> { }

extension X5: R where T: R { } // "wins" implied conformance to P, because
extension X5: S where T: S { } // the extension where "T: S" is more specialized
                                // than the one where "T: R"
Thus, the rule for placing implied conformances is to pick the least specialized extension that implies the conformance. If there is more than one such extension, then either:

All such extensions are not constrained extensions (i.e., they have no requirements beyond what the type requires), in which case Swift can continue to choose arbitrarily among the extensions, or
All such extensions are constrained extensions, in which case the program is ill-formed due to the ambiguity. The developer can explicitly specify conformance to the protocol to disambiguate.
Overloading across constrained extensions

One particularly important aspect of the placement rule for implied conformances is that it affects which declarations are used to satisfy a particular requirement. For example:

protocol P {
  func f()
}

protocol Q: P { }
protocol R: Q { }

struct X1<T> { }

extension X1: Q where T: Q { // note: implied conformance to P here
  func f() {
    // #1: basic implementation of 'f()'
  }
}

extension X1: R where T: R {
  func f() {
    // #2: superfast implementation of f() using some knowledge of 'R'
  }
}

struct X2: R {
  func f() { }
}

(X1<X2>() as P).f() // calls #1, which was used to satisfy the requirement for 'f'
X1<X2>().f() // calls #2, which is preferred by overload resolution
Effectively, when satisfying a protocol requirement, one can only choose from members of the type that are guaranteed to available within the extension with which the conformance is associated. In this case, the conformance to P is placed on the first extension of X1, so the only f() that can be considered is the f() within that extension: the f() in the second extension won't necessarily always be available, because T may not conform to R. Hence, the call that treats an X1<X2>as a P gets the first implementation of X1.f(). When using the concrete type X1<X2>, where X2 conforms to R, both X.f() implementations are visible... and the second is more specialized.

Technically, this issue is no different from surprises where (e.g.) a member added to a concrete type in a different module won't affect an existing protocol conformance. The existing ideas to mediate these problems---warning for nearly-matching functions when they are declared in concrete types, for example---will likely be sufficient to help surprised users. That said, this proposal may increase the likelihood of such problems showing up.

Source compatibility

From the language perspective, conditional conformances are purely additive. They introduce no new syntax, but instead provide semantics for existing syntax---an extension that both declares a protocol conformance and has a where clause---whose use currently results in a type checker failure. That said, this is a feature that is expected to be widely adopted within the Swift standard library, which may indirectly affect source compatibility.

Effect on ABI Stability

As noted above, there are a number of places where the standard library is expected to adopt this feature, which fall into two classes:

Improve composability: the example in the introduction made Array conform to Equatable when its element type does; there are many places in the Swift standard library that could benefit from this form of conditional conformance, particularly so that collections and other types that contain values (e.g., Optional) can compose better with generic algorithms. Most of these changes won't be ABI- or source-breaking, because they're additive.
Eliminating repetition: the lazy wrappers described in the motivation section could be collapsed into a single wrapper with several conditional conformances. A similar refactoring could also be applied to the range abstractions and slice types in the standard library, making the library itself simpler and smaller. All of these changes are potentially source-breaking and ABI-breaking, because they would remove types that could be used in Swift 3 code. However, there are mitigations: generic typealiases could provide source compatibility to Swift 3 clients, and the ABI-breaking aspect is only relevant if conditional conformances and the standard library changes they imply aren't part of Swift 4.
Aside from the standard library, conditional conformances have an impact on the Swift runtime, which will require specific support to handle dynamic casting. If that runtime support is not available once ABI stability has been declared, then introducing conditional conformances in a later language version either means the feature cannot be deployed backward or that it would provide only more limited, static behavior when used on older runtimes. Hence, there is significant motivation for doing this feature as part of Swift 4. Even if we waited to introduce conditional conformances, we would want to include a hook in the runtime to allow them to be implemented later, to avoid future backward-compatibility issues.

Alternatives considered

The most common request related to conditional conformances is to allow a (constrained) protocol extension to declare conformance to a protocol. For example:

extension Collection: Equatable where Iterator.Element: Equatable {
  static func ==(lhs: Self, rhs: Self) -> Bool {
    // ...
  }
}
This protocol extension will make any Collection of Equatable elements Equatable, which is a powerful feature that could be put to good use. Introducing conditional conformances for protocol extensions would exacerbate the problem of overlapping conformances, because it would be unreasonable to say that the existence of the above protocol extension means that no type that conforms to Collection could declare its own conformance to Equatable, conditional or otherwise.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Jordan Rose) #3

Great job thinking this all through (as usual), and I’ll be very happy to have Optional and Array become Equatable. Here’s some of my thoughts on the library evolution aspect of this:

- Removing a conditional conformance isn’t allowed, obviously.
- Adding a conditional conformance is just like adding an unconditional conformance—it needs availability info.
- It would be nice™ if making a conditional conformance more general was allowed. Since the plan doesn't allow overlapping conformances, I think this is actually implementable: just don’t put the constraints in the symbol name. I don’t know how to represent the backwards-deploying aspects of this right now, so it probably makes sense to forbid it today, but I think it would be nice if the implementation left the door open.

On that note, what happens here?

// Module Lib
public protocol Base {}
public protocol Sub: Base {}
public protocol Special: Sub {}

public struct Impl<T> {}
extension Impl: Special where T: Special {}

// Module Client
import Lib

extension Impl: Sub where T: Sub {}

I think this gets rejected because Impl already has a conformance to Sub—the extension in Client, despite being less specialized, shows up too late to actually declare this conformance “better”. Is that correct?

Jordan


(plx) #4

It’s good to see this starting to happen!

Is the decision on "no-overlapping-conformances” something that’s seen-as set in stone permanently, set in stone for the near future, or perhaps at least somewhat open to reconsideration at the present moment?

···

On Sep 26, 2016, at 7:18 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

Conditional conformances

Proposal: SE-NNNN <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/NNNN-conditional-conformances.md>
Author: Doug Gregor <https://github.com/DougGregor>
Review Manager: TBD
Status: Awaiting review
During the review process, add the following fields as needed:

Decision Notes: Rationale <https://lists.swift.org/pipermail/swift-evolution/>, Additional Commentary <https://lists.swift.org/pipermail/swift-evolution/>
Bugs: SR-NNNN <https://bugs.swift.org/browse/SR-NNNN>, SR-MMMM <https://bugs.swift.org/browse/SR-MMMM>
Previous Revision: 1 <https://github.com/apple/swift-evolution/blob/...commit-ID.../proposals/NNNN-filename.md>
Previous Proposal: SE-XXXX <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/XXXX-filename.md>
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#introduction>Introduction

Conditional conformances express the notion that a generic type will conform to a particular protocol only when it's type arguments meet certain requirements. For example, the Array collection can implement the Equatable protocol only when its elements are themselves Equatable, which can be expressed via the following conditional conformance on Equatable:

extension Array: Equatable where Element: Equatable {
  static func ==(lhs: Array<T>, rhs: Array<T>) -> Bool { ... }
}
This feature is part of the generics manifesto <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-> because it's something that fits naturally into the generics model and is expected to have a high impact on the Swift standard library.

Swift-evolution thread: TBD: Discussion thread topic for that proposal <https://lists.swift.org/pipermail/swift-evolution/>
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#motivation>Motivation

Conditional conformances address a hole in the composability of the generics system. Continuing the Array example from above, it's always been the case that one could use the == operator on two arrays of Equatable type, e.g., [Int]() == [Int]() would succeed. However, it doesn't compose: arrays of arrays of Equatable types cannot be compared (e.g.,[Int] <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals>== [Int] <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals>will fail to compile) because, even though there is an==for arrays of Equatabletype, the arrays themselves are neverEquatable`.

Conditional conformances are particularly powerful when building generic adapter types, which are intended to reflect the capabilities of their type arguments. For example, consider the "lazy" functionality of the Swift standard library's collections: using the lazy member of a sequence produces a lazy adapter that conforms to the Sequence protocol, while using the lazy member of a collection produces a lazy adapter that conforms to the Collection protocol. In Swift 3, the only way to model this is with different types. For example, the Swift standard library has four similar generic types to handle a lazy collection: LazySequence, LazyCollection, LazyBidirectionalCollection, and LazyRandomAccessCollection. The Swift standard library uses overloading of the lazy property to decide among these:

extension Sequence {
  var lazy: LazySequence<Self> { ... }
}

extension Collection {
  var lazy: LazyCollection<Self> { ... }
}

extension BidirectionalCollection {
  var lazy: LazyBidirectionalCollection<Self> { ... }
}

extension RandomAccessCollection {
  var lazy: LazyRandomAccessCollection<Self> { ... }
}
This approach causes an enormous amount of repetition, and doesn't scale well because each more-capable type has to re-implement (or somehow forward the implementation of) all of the APIs of the less-capable versions. With conditional conformances, one can provide a single generic wrapper type whose basic requirements meet the lowest common denominator (e.g., Sequence), but which scale their capabilities with their type argument (e.g., the LazySequence conforms to Collection when the type argument does, and so on).

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#proposed-solution>Proposed solution

In a nutshell, the proposed solution is to allow a constrained extension of a struct, enum, or class to declare protocol conformances. No additional syntax is necessary for this change, because it already exists in the grammar; rather, this proposal removes the limitation that results in the following error:

t.swift:1:1: error: extension of type 'Array' with constraints cannot have an inheritance clause
extension Array: Equatable where Element: Equatable { }
^ ~~~~~~~~~
Conditional conformances can only be used when the additional requirements of the constrained extension are satisfied. For example, given the aforementioned Array conformance to Equatable:

func f<T: Equatable>(_: T) { ... }

struct NotEquatable { }

func test(a1: [Int], a2: [NotEquatable]) {
  f(a1) // okay: [Int] conforms to Equatable because Int conforms to Equatable
  f(a2) // error: [NotEquatable] does not conform to Equatable because NotEquatable has no conformance to Equatable
}
Conditional conformances also have a run-time aspect, because a dynamic check for a protocol conformance might rely on the evaluation of the extra requirements needed to successfully use a conditional conformance. For example:

protocol P {
  func doSomething()
}

struct S: P {
  func doSomething() { print("S") }
}

// Array conforms to P if it's element type conforms to P
extension Array: P where Element: P {
  func doSomething() {
    for value in self {
      value.doSomething()
    }
  }
}

// Dynamically query and use conformance to P.
func doSomethingIfP(_ value: Any) {
  if let p = value as? P {
    p.doSomething()
  } else {
    print("Not a P")
  }
}

doSomethingIfP([S(), S(), S()]) // prints "S" three times
doSomethingIfP([1, 2, 3]) // prints "Not a P"
The if-let in doSomethingIfP(_:slight_smile: dynamically queries whether the type stored in value conforms to the protocol P. In the case of an Array, that conformance is conditional, which requires another dynamic lookup to determine whether the element type conforms to P: in the first call to doSomethingIfP(_:), the lookup finds the conformance of S to P. In the second case, there is no conformance of Int to P, so the conditional conformance cannot be used. The desire for this dynamic behavior motivates some of the design decisions in this proposal.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#detailed-design>Detailed design

Most of the semantics of conditional conformances are obvious. However, there are a number of issues (mostly involving multiple conformances) that require more in-depth design.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#disallow-overlapping-conformances>Disallow overlapping conformances

With conditional conformances, it is possible to express that a given generic type can conform to the same protocol in two different ways, depending on the capabilities of its type arguments. For example:

struct SomeWrapper<Wrapped> {
  let wrapped: Wrapped
}

protocol HasIdentity {
  static func ===(lhs: Self, rhs: Self) -> Bool
}

extension SomeWrapper: Equatable where Wrapped: Equatable {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
}

extension SomeWrapper: Equatable where Wrapped: HasIdentity {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped === rhs.wrapped
  }
}
Note that, for an arbitrary type T, there are four potential answers to the question of whether SomeWrapper<T> conforms to Equatable:

No, it does not conform because T is neither Equatable nor HasIdentity.
Yes, it conforms via the first extension of SomeWrapper because T conforms to Equatable.
Yes, it conforms via the second extension of SomeWrapper because T conforms to HasIdentity.
Ambiguity, because T conforms to both Equatable and HasIdentity.
It is due to the possibility of #4 occurring that we refer to the two conditional conformances in the example as overlapping. There are designs that would allow one to address the ambiguity, for example, by writing a third conditional conformance that addresses #4:

// Possible tie-breaker conformance
extension SomeWrapper: Equatable where Wrapped: Equatable & HasIdentity, {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
}
The design is consistent, because this third conditional conformance is more specialized the either of the first two conditional conformances, meaning that its requirements are a strict superset of the requirements of those two conditional conformances. However, there are a few downsides to such a system:

To address all possible ambiguities, one has to write a conditional conformance for every plausible combination of overlapping requirements. To statically resolve all ambiguities, one must also cover nonsensical combinations where the two requirements are mutually exclusive (or invent a way to state mutual-exclusivity).
It is no longer possible to uniquely say what is required to make a generic type conform to a protocol, because there might be several unrelated possibilities. This makes reasoning about the whole system more complex, because it admits divergent interfaces for the same generic type based on their type arguments. At its extreme, this invites the kind of cleverness we've seen in the C++ community with template metaprogramming, which is something Swift has sought to avoid.
All of the disambiguation machinery required at compile time (e.g., to determine whether one conditional conformance is more specialized than another to order them) also needs to implements in the run-time, as part of the dynamic casting machinery. One must also address the possibility of ambiguities occurring at run-time. This is both a sharp increase in the complexity of the system and a potential run-time performance hazard.
For these reasons, this proposal bans overlapping conformances entirely. While the resulting system is less flexible than one that allowed overlapping conformances, the gain in simplicity in this potentially-confusing area is well worth the cost. Moreover, this ban follows with existing Swift rules regarding multiple conformances, which prohibit the same type from conforming to the same protocol in two different ways:

protocol P { }

struct S : P { }
extension S : P { } // error: S already conforms to P
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#implied-conditional-conformances>Implied conditional conformances

Stating conformance to a protocol implicitly states conformances to any of the protocols that it inherits. This is the case in Swift today, although most developers likely don't realize the rules it follows. For example:

protocol P { }
protocol Q : P { }
protocol R : P { }

struct X1 { }
struct X2 { }
struct X3 { }

extension X1: Q { } // implies conformance to P

extension X2: Q { } // would imply conformance to P, but...
extension X2: P { } // explicitly-stated conformance to P "wins"

extension X3: Q { } // implies conformance to P
extension X3: R { } // also implies conformance to P
                     // one will "win"; which is unspecified
With conditional conformances, the question of which extension "wins" the implied conformance begins to matter, because the extensions might have different constraints on them. For example:

struct X4<T> { }

extension X4: Q where T: Q { } // implies conformance to P
extension X4: R where T: R { } // error: implies overlapping conformance to P
Both of these constrained extensions imply a conformance to P, but the actual P implied conformances to P are overlapping and, therefore, result in an error.

However, in cases where there is a reasonable ordering between the two constrained extensions (i.e., one is more specialized than the other), the less specialized constrained extension should "win" the implied conformance. Continuing the example from above:

protocol S: R { }

struct X5<T> { }

extension X5: R where T: R { } // "wins" implied conformance to P, because
extension X5: S where T: S { } // the extension where "T: S" is more specialized
                                // than the one where "T: R"
Thus, the rule for placing implied conformances is to pick the least specialized extension that implies the conformance. If there is more than one such extension, then either:

All such extensions are not constrained extensions (i.e., they have no requirements beyond what the type requires), in which case Swift can continue to choose arbitrarily among the extensions, or
All such extensions are constrained extensions, in which case the program is ill-formed due to the ambiguity. The developer can explicitly specify conformance to the protocol to disambiguate.
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#overloading-across-constrained-extensions>Overloading across constrained extensions

One particularly important aspect of the placement rule for implied conformances is that it affects which declarations are used to satisfy a particular requirement. For example:

protocol P {
  func f()
}

protocol Q: P { }
protocol R: Q { }

struct X1<T> { }

extension X1: Q where T: Q { // note: implied conformance to P here
  func f() {
    // #1: basic implementation of 'f()'
  }
}

extension X1: R where T: R {
  func f() {
    // #2: superfast implementation of f() using some knowledge of 'R'
  }
}

struct X2: R {
  func f() { }
}

(X1<X2>() as P).f() // calls #1, which was used to satisfy the requirement for 'f'
X1<X2>().f() // calls #2, which is preferred by overload resolution
Effectively, when satisfying a protocol requirement, one can only choose from members of the type that are guaranteed to available within the extension with which the conformance is associated. In this case, the conformance to P is placed on the first extension of X1, so the only f() that can be considered is the f() within that extension: the f() in the second extension won't necessarily always be available, because T may not conform to R. Hence, the call that treats an X1<X2>as a P gets the first implementation of X1.f(). When using the concrete type X1<X2>, where X2 conforms to R, both X.f() implementations are visible... and the second is more specialized.

Technically, this issue is no different from surprises where (e.g.) a member added to a concrete type in a different module won't affect an existing protocol conformance. The existing ideas to mediate these problems---warning for nearly-matching functions when they are declared in concrete types, for example---will likely be sufficient to help surprised users. That said, this proposal may increase the likelihood of such problems showing up.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#source-compatibility>Source compatibility

From the language perspective, conditional conformances are purely additive. They introduce no new syntax, but instead provide semantics for existing syntax---an extension that both declares a protocol conformance and has a where clause---whose use currently results in a type checker failure. That said, this is a feature that is expected to be widely adopted within the Swift standard library, which may indirectly affect source compatibility.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#effect-on-abi-stability>Effect on ABI Stability

As noted above, there are a number of places where the standard library is expected to adopt this feature, which fall into two classes:

Improve composability: the example in the introduction <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/Introduction> made Array conform to Equatable when its element type does; there are many places in the Swift standard library that could benefit from this form of conditional conformance, particularly so that collections and other types that contain values (e.g., Optional) can compose better with generic algorithms. Most of these changes won't be ABI- or source-breaking, because they're additive.
Eliminating repetition: the lazy wrappers described in the motivation <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/motivation> section could be collapsed into a single wrapper with several conditional conformances. A similar refactoring could also be applied to the range abstractions and slice types in the standard library, making the library itself simpler and smaller. All of these changes are potentially source-breaking and ABI-breaking, because they would remove types that could be used in Swift 3 code. However, there are mitigations: generic typealiases could provide source compatibility to Swift 3 clients, and the ABI-breaking aspect is only relevant if conditional conformances and the standard library changes they imply aren't part of Swift 4.
Aside from the standard library, conditional conformances have an impact on the Swift runtime, which will require specific support to handle dynamic casting. If that runtime support is not available once ABI stability has been declared, then introducing conditional conformances in a later language version either means the feature cannot be deployed backward or that it would provide only more limited, static behavior when used on older runtimes. Hence, there is significant motivation for doing this feature as part of Swift 4. Even if we waited to introduce conditional conformances, we would want to include a hook in the runtime to allow them to be implemented later, to avoid future backward-compatibility issues.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#alternatives-considered>Alternatives considered

The most common request related to conditional conformances is to allow a (constrained) protocol extension to declare conformance to a protocol. For example:

extension Collection: Equatable where Iterator.Element: Equatable {
  static func ==(lhs: Self, rhs: Self) -> Bool {
    // ...
  }
}
This protocol extension will make any Collection of Equatable elements Equatable, which is a powerful feature that could be put to good use. Introducing conditional conformances for protocol extensions would exacerbate the problem of overlapping conformances, because it would be unreasonable to say that the existence of the above protocol extension means that no type that conforms to Collection could declare its own conformance to Equatable, conditional or otherwise.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Russ Bishop) #5

Conditional conformances

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#disallow-overlapping-conformances>Disallow overlapping conformances

With conditional conformances, it is possible to express that a given generic type can conform to the same protocol in two different ways, depending on the capabilities of its type arguments. For example:

Note that, for an arbitrary type T, there are four potential answers to the question of whether SomeWrapper<T> conforms to Equatable:

No, it does not conform because T is neither Equatable nor HasIdentity.
Yes, it conforms via the first extension of SomeWrapper because T conforms to Equatable.
Yes, it conforms via the second extension of SomeWrapper because T conforms to HasIdentity.
Ambiguity, because T conforms to both Equatable and HasIdentity.
It is due to the possibility of #4 occurring that we refer to the two conditional conformances in the example as overlapping. There are designs that would allow one to address the ambiguity

For these reasons, this proposal bans overlapping conformances entirely.

What other designs were considered and rejected? It seems like some kind of escape hatch would be preferred if you happen to get into this situation, though you make some really good points about the pitfalls.

Just to clarify when you say “bans” do you mean if Wrapped: Equatable & HasIdentity then SomeWrapper is not Equatable, or do you mean you get a compile error because there are two constrained conformances SomeWrapper: Equatable? What would be the problem with allowing multiple conformances to Equatable so long as the constraints are disjoint or the concrete type only adopts one of the available protocols?

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#implied-conditional-conformances>Implied conditional conformances

Stating conformance to a protocol implicitly states conformances to any of the protocols that it inherits. This is the case in Swift today, although most developers likely don't realize the rules it follows. For example:

protocol P { }
protocol Q : P { }
protocol R : P { }

struct X1 { }
struct X2 { }
struct X3 { }

extension X1: Q { } // implies conformance to P

extension X2: Q { } // would imply conformance to P, but...
extension X2: P { } // explicitly-stated conformance to P "wins"

extension X3: Q { } // implies conformance to P
extension X3: R { } // also implies conformance to P
                     // one will "win"; which is unspecified

On X2 you’re declaring a redundant conformance to P but any protocol extensions will prefer Q and the compiler won’t let you redefine any members so you’ll have an incomplete conformance. Any explicit conformances (on the type or in extensions) are preferred over the defaults from the protocol extension, but that’s not new. I must be missing something, how would this be visible in Swift 3?

On X3, multiple implementations in protocol extensions are errors today and the resolution is to provide an explicit implementation on X3.

With conditional conformances, the question of which extension "wins" the implied conformance begins to matter, because the extensions might have different constraints on them. For example:

struct X4<T> { }

extension X4: Q where T: Q { } // implies conformance to P
extension X4: R where T: R { } // error: implies overlapping conformance to P
Both of these constrained extensions imply a conformance to P, but the actual P implied conformances to P are overlapping and, therefore, result in an error.

If the related P conformance were inherited from conformance to Q or R then the rules would (IMHO) make more sense. Wouldn’t the extra rule you need simply be that either Q or R must provide a complete conformance to P (no mix-n-match)?

If T implements Q & P why not just ignore T: P which means the X4: R extension is no longer relevant.

It seems like the tricky case is T: P and the same question applies - why not just ignore the extensions (X4<T> in that scenario doesn’t implement Q, R, or P).

Not allowing ambiguity seems like it solves the “which one” problem and requiring an extension to provide the entire implementation (no mix-n-match) cuts down on the cleverness problem.

However, in cases where there is a reasonable ordering between the two constrained extensions (i.e., one is more specialized than the other), the less specialized constrained extension should "win" the implied conformance. Continuing the example from above:

protocol S: R { }

struct X5<T> { }

extension X5: R where T: R { } // "wins" implied conformance to P, because
extension X5: S where T: S { } // the extension where "T: S" is more specialized
                                // than the one where "T: R"
Thus, the rule for placing implied conformances is to pick the least specialized extension that implies the conformance. If there is more than one such extension, then either:

All such extensions are not constrained extensions (i.e., they have no requirements beyond what the type requires), in which case Swift can continue to choose arbitrarily among the extensions, or
All such extensions are constrained extensions, in which case the program is ill-formed due to the ambiguity. The developer can explicitly specify conformance to the protocol to disambiguate.

What is the rationale for picking the least specialized extension? That’s not what I would naively expect to happen. If T: R & S then I would expect the more specialized S:R implementation to be preferred, and the explicit R implementation to kick in when T: R.

(Some of these may just be naive questions resulting from my misunderstanding)

Russ

···

On Sep 26, 2016, at 5:18 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:


(Joe Groff) #6

We fundamentally can't guarantee cross-module uniqueness of instances, since we allow arbitrary post-hoc conformance. For the most part, we don't have to, since most operations that require a protocol conformance are able to statically select one at compile-time, and the conformance becomes an implicit part of the parameterization of any generic functions or types that require it. The main problem overlapping conformances pose is for dynamic casts, since the 'x as? P' operation has no static context by which to pick a conformance if there are multiple possibilities for the dynamic type of x to conform to P.

-Joe

···

On Sep 26, 2016, at 5:37 PM, Robert Widmann via swift-evolution <swift-evolution@swift.org> wrote:

+1. I have one purely bureaucratic concern that I couldn't quite find answers to on a read through:

Orphan instances and more generally cross-module uniqueness of instances are not mentioned. What's the policy here? Are we locally unique with respect to imported modules or globally unique with respect to all importable modules?


(Douglas Gregor) #7

+1. I have one purely bureaucratic concern that I couldn't quite find answers to on a read through:

Orphan instances

Not sure what you mean by “orphan instances”?

and more generally cross-module uniqueness of instances are not mentioned. What's the policy here? Are we locally unique with respect to imported modules or globally unique with respect to all importable modules?

Yeah, this is a painfully underspecified area of Swift’s generics system. The compiler diagnoses redundant conformances when it sees both conformances, but that’s not enough to guarantee global uniqueness. The runtime effectively depends on global uniqueness, and there are no mechanisms in the language or runtime to disambiguate if the non-unique conformances occur.

We’re not in an ideal state, although I don’t think the conditional conformances proposal is the place to try to fix it. Personally, I think we should codify the globally-unique model and provide some level of safety in the runtime to detect (lazily) when there is a run-time conflict. It’s probably worthy of a proposal, although it would be an odd sort of proposal—mostly about describing the model and the trade-offs (no private conformances, potential for run-time oddities if a conflict does occur, etc.) vs. allowing multiple conformances to co-exist (dynamic-casting complexity, the need for a disambiguation mechanism, etc.). At most, we could make it clearer in source code when you’re doing something that *could* cause a runtime conflict. For example, writing a conformance in the module that defines the type or the module that defines the protocol is guaranteed to be okay (modulo resilience!), but a retroactive conformance in a third model is potentially unsafe and might be worthy of some kind of attribute.

Anyway, some random thoughts on this issue are in the generics manifesto:

  https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#private-conformances

  - Doug

···

On Sep 26, 2016, at 5:37 PM, Robert Widmann <devteam.codafi@gmail.com> wrote:

~Robert Widmann

2016/09/26 20:18、Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> のメッセージ:

Conditional conformances

Proposal: SE-NNNN <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/NNNN-conditional-conformances.md>
Author: Doug Gregor <https://github.com/DougGregor>
Review Manager: TBD
Status: Awaiting review
During the review process, add the following fields as needed:

Decision Notes: Rationale <https://lists.swift.org/pipermail/swift-evolution/>, Additional Commentary <https://lists.swift.org/pipermail/swift-evolution/>
Bugs: SR-NNNN <https://bugs.swift.org/browse/SR-NNNN>, SR-MMMM <https://bugs.swift.org/browse/SR-MMMM>
Previous Revision: 1 <https://github.com/apple/swift-evolution/blob/...commit-ID.../proposals/NNNN-filename.md>
Previous Proposal: SE-XXXX <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/XXXX-filename.md>
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#introduction>[snip[


(Douglas Gregor) #8

Great job thinking this all through (as usual), and I’ll be very happy to have Optional and Array become Equatable. Here’s some of my thoughts on the library evolution aspect of this:

- Removing a conditional conformance isn’t allowed, obviously.
- Adding a conditional conformance is just like adding an unconditional conformance—it needs availability info.

Right. The main wrinkle I see here is that, when you add a conditional conformance, you will effectively end up with overlapping conformances when running an old application against a new library. Do you want me to capture these cases in the proposal in a section on “Resilience” or “Library Evolution”, like I’ve tried to capture the effect on ABI Stability? (I think that makes sense)

- It would be nice™ if making a conditional conformance more general was allowed. Since the plan doesn't allow overlapping conformances, I think this is actually implementable: just don’t put the constraints in the symbol name. I don’t know how to represent the backwards-deploying aspects of this right now, so it probably makes sense to forbid it today, but I think it would be nice if the implementation left the door open.

Yeah. It’s a different set of witness tables that one would need to gather to use the conditional conformance in the newer version of the library vs. in an older version of a library. That’s okay if we leave the witness-table-gathering to the runtime, but not so great if we statically provide the witness tables.

On that note, what happens here?

// Module Lib
public protocol Base {}
public protocol Sub: Base {}
public protocol Special: Sub {}

public struct Impl<T> {}
extension Impl: Special where T: Special {}

// Module Client
import Lib

extension Impl: Sub where T: Sub {}

I think this gets rejected because Impl already has a conformance to Sub—the extension in Client, despite being less specialized, shows up too late to actually declare this conformance “better”. Is that correct?

Correct. Impl has a conformance to ‘Sub’ in Lib; Client cannot declare a new one, because it overlaps. Had all of this code been in one module, it would be well-formed, because the implied conformance to ’Sub’ in the first extension would lose to the explicit conformance to Sub in the second (less-specialized) extension.

  - Doug

···

On Sep 27, 2016, at 5:06 PM, Jordan Rose <jordan_rose@apple.com> wrote:


(Anton Zhilin) #9

I find the limitation of non-intersection of conditional conformance
reqirements quite limiting. Can it be lifted in case there are no
overloaded functions between extensions?

protocol A { func foo() }
protocol B { func bar() }

extension Array: A where Element: A {
    func foo() { return self.first!.foo() }
}
extension Array: B where Element: B {
    func bar() { return self.first!.bar() }
}

let arr: Array<T>
arr.foo()

What is ambiguous here? When we see arr.foo(), we know it's from Array: A
extension, regardless of T, and we just have to check the requirement of
that extension.


(Douglas Gregor) #10

It’s good to see this starting to happen!

Is the decision on "no-overlapping-conformances” something that’s seen-as set in stone permanently, set in stone for the near future, or perhaps at least somewhat open to reconsideration at the present moment?

There hasn’t been a decision per se, so it that sense it’s open to reconsideration.

I have a strong *personal* bias against overlapping conformances, because I feel that the amount of complexity that they introduce into the language and its implementation far outweigh any benefits. Additionally, they enable use cases (e.g., static metaprogramming-ish tricks) that I feel would be actively harmful to the Swift language’s understandability. Generics systems can get very complicated very quickly, so any extension needs to be strongly motivated by use cases to matter to all or most Swift developers.

  - Doug

···

On Sep 28, 2016, at 1:28 PM, plx via swift-evolution <swift-evolution@swift.org> wrote:

On Sep 26, 2016, at 7:18 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Conditional conformances

Proposal: SE-NNNN <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/NNNN-conditional-conformances.md>
Author: Doug Gregor <https://github.com/DougGregor>
Review Manager: TBD
Status: Awaiting review
During the review process, add the following fields as needed:

Decision Notes: Rationale <https://lists.swift.org/pipermail/swift-evolution/>, Additional Commentary <https://lists.swift.org/pipermail/swift-evolution/>
Bugs: SR-NNNN <https://bugs.swift.org/browse/SR-NNNN>, SR-MMMM <https://bugs.swift.org/browse/SR-MMMM>
Previous Revision: 1 <https://github.com/apple/swift-evolution/blob/...commit-ID.../proposals/NNNN-filename.md>
Previous Proposal: SE-XXXX <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/XXXX-filename.md>
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#introduction>Introduction

Conditional conformances express the notion that a generic type will conform to a particular protocol only when it's type arguments meet certain requirements. For example, the Array collection can implement the Equatable protocol only when its elements are themselves Equatable, which can be expressed via the following conditional conformance on Equatable:

extension Array: Equatable where Element: Equatable {
  static func ==(lhs: Array<T>, rhs: Array<T>) -> Bool { ... }
}
This feature is part of the generics manifesto <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-> because it's something that fits naturally into the generics model and is expected to have a high impact on the Swift standard library.

Swift-evolution thread: TBD: Discussion thread topic for that proposal <https://lists.swift.org/pipermail/swift-evolution/>
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#motivation>Motivation

Conditional conformances address a hole in the composability of the generics system. Continuing the Array example from above, it's always been the case that one could use the == operator on two arrays of Equatable type, e.g., [Int]() == [Int]() would succeed. However, it doesn't compose: arrays of arrays of Equatable types cannot be compared (e.g.,[Int] <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals>== [Int] <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals>will fail to compile) because, even though there is an==for arrays of Equatabletype, the arrays themselves are neverEquatable`.

Conditional conformances are particularly powerful when building generic adapter types, which are intended to reflect the capabilities of their type arguments. For example, consider the "lazy" functionality of the Swift standard library's collections: using the lazy member of a sequence produces a lazy adapter that conforms to the Sequence protocol, while using the lazy member of a collection produces a lazy adapter that conforms to the Collection protocol. In Swift 3, the only way to model this is with different types. For example, the Swift standard library has four similar generic types to handle a lazy collection: LazySequence, LazyCollection, LazyBidirectionalCollection, and LazyRandomAccessCollection. The Swift standard library uses overloading of the lazy property to decide among these:

extension Sequence {
  var lazy: LazySequence<Self> { ... }
}

extension Collection {
  var lazy: LazyCollection<Self> { ... }
}

extension BidirectionalCollection {
  var lazy: LazyBidirectionalCollection<Self> { ... }
}

extension RandomAccessCollection {
  var lazy: LazyRandomAccessCollection<Self> { ... }
}
This approach causes an enormous amount of repetition, and doesn't scale well because each more-capable type has to re-implement (or somehow forward the implementation of) all of the APIs of the less-capable versions. With conditional conformances, one can provide a single generic wrapper type whose basic requirements meet the lowest common denominator (e.g., Sequence), but which scale their capabilities with their type argument (e.g., the LazySequence conforms to Collection when the type argument does, and so on).

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#proposed-solution>Proposed solution

In a nutshell, the proposed solution is to allow a constrained extension of a struct, enum, or class to declare protocol conformances. No additional syntax is necessary for this change, because it already exists in the grammar; rather, this proposal removes the limitation that results in the following error:

t.swift:1:1: error: extension of type 'Array' with constraints cannot have an inheritance clause
extension Array: Equatable where Element: Equatable { }
^ ~~~~~~~~~
Conditional conformances can only be used when the additional requirements of the constrained extension are satisfied. For example, given the aforementioned Array conformance to Equatable:

func f<T: Equatable>(_: T) { ... }

struct NotEquatable { }

func test(a1: [Int], a2: [NotEquatable]) {
  f(a1) // okay: [Int] conforms to Equatable because Int conforms to Equatable
  f(a2) // error: [NotEquatable] does not conform to Equatable because NotEquatable has no conformance to Equatable
}
Conditional conformances also have a run-time aspect, because a dynamic check for a protocol conformance might rely on the evaluation of the extra requirements needed to successfully use a conditional conformance. For example:

protocol P {
  func doSomething()
}

struct S: P {
  func doSomething() { print("S") }
}

// Array conforms to P if it's element type conforms to P
extension Array: P where Element: P {
  func doSomething() {
    for value in self {
      value.doSomething()
    }
  }
}

// Dynamically query and use conformance to P.
func doSomethingIfP(_ value: Any) {
  if let p = value as? P {
    p.doSomething()
  } else {
    print("Not a P")
  }
}

doSomethingIfP([S(), S(), S()]) // prints "S" three times
doSomethingIfP([1, 2, 3]) // prints "Not a P"
The if-let in doSomethingIfP(_:slight_smile: dynamically queries whether the type stored in value conforms to the protocol P. In the case of an Array, that conformance is conditional, which requires another dynamic lookup to determine whether the element type conforms to P: in the first call to doSomethingIfP(_:), the lookup finds the conformance of S to P. In the second case, there is no conformance of Int to P, so the conditional conformance cannot be used. The desire for this dynamic behavior motivates some of the design decisions in this proposal.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#detailed-design>Detailed design

Most of the semantics of conditional conformances are obvious. However, there are a number of issues (mostly involving multiple conformances) that require more in-depth design.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#disallow-overlapping-conformances>Disallow overlapping conformances

With conditional conformances, it is possible to express that a given generic type can conform to the same protocol in two different ways, depending on the capabilities of its type arguments. For example:

struct SomeWrapper<Wrapped> {
  let wrapped: Wrapped
}

protocol HasIdentity {
  static func ===(lhs: Self, rhs: Self) -> Bool
}

extension SomeWrapper: Equatable where Wrapped: Equatable {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
}

extension SomeWrapper: Equatable where Wrapped: HasIdentity {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped === rhs.wrapped
  }
}
Note that, for an arbitrary type T, there are four potential answers to the question of whether SomeWrapper<T> conforms to Equatable:

No, it does not conform because T is neither Equatable nor HasIdentity.
Yes, it conforms via the first extension of SomeWrapper because T conforms to Equatable.
Yes, it conforms via the second extension of SomeWrapper because T conforms to HasIdentity.
Ambiguity, because T conforms to both Equatable and HasIdentity.
It is due to the possibility of #4 occurring that we refer to the two conditional conformances in the example as overlapping. There are designs that would allow one to address the ambiguity, for example, by writing a third conditional conformance that addresses #4:

// Possible tie-breaker conformance
extension SomeWrapper: Equatable where Wrapped: Equatable & HasIdentity, {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
}
The design is consistent, because this third conditional conformance is more specialized the either of the first two conditional conformances, meaning that its requirements are a strict superset of the requirements of those two conditional conformances. However, there are a few downsides to such a system:

To address all possible ambiguities, one has to write a conditional conformance for every plausible combination of overlapping requirements. To statically resolve all ambiguities, one must also cover nonsensical combinations where the two requirements are mutually exclusive (or invent a way to state mutual-exclusivity).
It is no longer possible to uniquely say what is required to make a generic type conform to a protocol, because there might be several unrelated possibilities. This makes reasoning about the whole system more complex, because it admits divergent interfaces for the same generic type based on their type arguments. At its extreme, this invites the kind of cleverness we've seen in the C++ community with template metaprogramming, which is something Swift has sought to avoid.
All of the disambiguation machinery required at compile time (e.g., to determine whether one conditional conformance is more specialized than another to order them) also needs to implements in the run-time, as part of the dynamic casting machinery. One must also address the possibility of ambiguities occurring at run-time. This is both a sharp increase in the complexity of the system and a potential run-time performance hazard.
For these reasons, this proposal bans overlapping conformances entirely. While the resulting system is less flexible than one that allowed overlapping conformances, the gain in simplicity in this potentially-confusing area is well worth the cost. Moreover, this ban follows with existing Swift rules regarding multiple conformances, which prohibit the same type from conforming to the same protocol in two different ways:

protocol P { }

struct S : P { }
extension S : P { } // error: S already conforms to P
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#implied-conditional-conformances>Implied conditional conformances

Stating conformance to a protocol implicitly states conformances to any of the protocols that it inherits. This is the case in Swift today, although most developers likely don't realize the rules it follows. For example:

protocol P { }
protocol Q : P { }
protocol R : P { }

struct X1 { }
struct X2 { }
struct X3 { }

extension X1: Q { } // implies conformance to P

extension X2: Q { } // would imply conformance to P, but...
extension X2: P { } // explicitly-stated conformance to P "wins"

extension X3: Q { } // implies conformance to P
extension X3: R { } // also implies conformance to P
                     // one will "win"; which is unspecified
With conditional conformances, the question of which extension "wins" the implied conformance begins to matter, because the extensions might have different constraints on them. For example:

struct X4<T> { }

extension X4: Q where T: Q { } // implies conformance to P
extension X4: R where T: R { } // error: implies overlapping conformance to P
Both of these constrained extensions imply a conformance to P, but the actual P implied conformances to P are overlapping and, therefore, result in an error.

However, in cases where there is a reasonable ordering between the two constrained extensions (i.e., one is more specialized than the other), the less specialized constrained extension should "win" the implied conformance. Continuing the example from above:

protocol S: R { }

struct X5<T> { }

extension X5: R where T: R { } // "wins" implied conformance to P, because
extension X5: S where T: S { } // the extension where "T: S" is more specialized
                                // than the one where "T: R"
Thus, the rule for placing implied conformances is to pick the least specialized extension that implies the conformance. If there is more than one such extension, then either:

All such extensions are not constrained extensions (i.e., they have no requirements beyond what the type requires), in which case Swift can continue to choose arbitrarily among the extensions, or
All such extensions are constrained extensions, in which case the program is ill-formed due to the ambiguity. The developer can explicitly specify conformance to the protocol to disambiguate.
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#overloading-across-constrained-extensions>Overloading across constrained extensions

One particularly important aspect of the placement rule for implied conformances is that it affects which declarations are used to satisfy a particular requirement. For example:

protocol P {
  func f()
}

protocol Q: P { }
protocol R: Q { }

struct X1<T> { }

extension X1: Q where T: Q { // note: implied conformance to P here
  func f() {
    // #1: basic implementation of 'f()'
  }
}

extension X1: R where T: R {
  func f() {
    // #2: superfast implementation of f() using some knowledge of 'R'
  }
}

struct X2: R {
  func f() { }
}

(X1<X2>() as P).f() // calls #1, which was used to satisfy the requirement for 'f'
X1<X2>().f() // calls #2, which is preferred by overload resolution
Effectively, when satisfying a protocol requirement, one can only choose from members of the type that are guaranteed to available within the extension with which the conformance is associated. In this case, the conformance to P is placed on the first extension of X1, so the only f() that can be considered is the f() within that extension: the f() in the second extension won't necessarily always be available, because T may not conform to R. Hence, the call that treats an X1<X2>as a P gets the first implementation of X1.f(). When using the concrete type X1<X2>, where X2 conforms to R, both X.f() implementations are visible... and the second is more specialized.

Technically, this issue is no different from surprises where (e.g.) a member added to a concrete type in a different module won't affect an existing protocol conformance. The existing ideas to mediate these problems---warning for nearly-matching functions when they are declared in concrete types, for example---will likely be sufficient to help surprised users. That said, this proposal may increase the likelihood of such problems showing up.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#source-compatibility>Source compatibility

From the language perspective, conditional conformances are purely additive. They introduce no new syntax, but instead provide semantics for existing syntax---an extension that both declares a protocol conformance and has a where clause---whose use currently results in a type checker failure. That said, this is a feature that is expected to be widely adopted within the Swift standard library, which may indirectly affect source compatibility.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#effect-on-abi-stability>Effect on ABI Stability

As noted above, there are a number of places where the standard library is expected to adopt this feature, which fall into two classes:

Improve composability: the example in the introduction <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/Introduction> made Array conform to Equatable when its element type does; there are many places in the Swift standard library that could benefit from this form of conditional conformance, particularly so that collections and other types that contain values (e.g., Optional) can compose better with generic algorithms. Most of these changes won't be ABI- or source-breaking, because they're additive.
Eliminating repetition: the lazy wrappers described in the motivation <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/motivation> section could be collapsed into a single wrapper with several conditional conformances. A similar refactoring could also be applied to the range abstractions and slice types in the standard library, making the library itself simpler and smaller. All of these changes are potentially source-breaking and ABI-breaking, because they would remove types that could be used in Swift 3 code. However, there are mitigations: generic typealiases could provide source compatibility to Swift 3 clients, and the ABI-breaking aspect is only relevant if conditional conformances and the standard library changes they imply aren't part of Swift 4.
Aside from the standard library, conditional conformances have an impact on the Swift runtime, which will require specific support to handle dynamic casting. If that runtime support is not available once ABI stability has been declared, then introducing conditional conformances in a later language version either means the feature cannot be deployed backward or that it would provide only more limited, static behavior when used on older runtimes. Hence, there is significant motivation for doing this feature as part of Swift 4. Even if we waited to introduce conditional conformances, we would want to include a hook in the runtime to allow them to be implemented later, to avoid future backward-compatibility issues.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#alternatives-considered>Alternatives considered

The most common request related to conditional conformances is to allow a (constrained) protocol extension to declare conformance to a protocol. For example:

extension Collection: Equatable where Iterator.Element: Equatable {
  static func ==(lhs: Self, rhs: Self) -> Bool {
    // ...
  }
}
This protocol extension will make any Collection of Equatable elements Equatable, which is a powerful feature that could be put to good use. Introducing conditional conformances for protocol extensions would exacerbate the problem of overlapping conformances, because it would be unreasonable to say that the existence of the above protocol extension means that no type that conforms to Collection could declare its own conformance to Equatable, conditional or otherwise.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto: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


(Douglas Gregor) #11

Conditional conformances

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#disallow-overlapping-conformances>Disallow overlapping conformances

With conditional conformances, it is possible to express that a given generic type can conform to the same protocol in two different ways, depending on the capabilities of its type arguments. For example:

Note that, for an arbitrary type T, there are four potential answers to the question of whether SomeWrapper<T> conforms to Equatable:

No, it does not conform because T is neither Equatable nor HasIdentity.
Yes, it conforms via the first extension of SomeWrapper because T conforms to Equatable.
Yes, it conforms via the second extension of SomeWrapper because T conforms to HasIdentity.
Ambiguity, because T conforms to both Equatable and HasIdentity.
It is due to the possibility of #4 occurring that we refer to the two conditional conformances in the example as overlapping. There are designs that would allow one to address the ambiguity

For these reasons, this proposal bans overlapping conformances entirely.

What other designs were considered and rejected? It seems like some kind of escape hatch would be preferred if you happen to get into this situation, though you make some really good points about the pitfalls.

I don’t have a fully-baked alternative proposal—it would probably have to involve some kind of preference rule for picking the “best” set of (consistent!) conformances to satisfy a particular request, introduce a disambiguation syntax for cases where that preference rule does the wrong thing, and some way of teaching the dynamic-casting machinery to do the same thing.

Just to clarify when you say “bans” do you mean if Wrapped: Equatable & HasIdentity then SomeWrapper is not Equatable, or do you mean you get a compile error because there are two constrained conformances SomeWrapper: Equatable?

You get a compile error if there are two conformances of SomeWrapper to Equatable; it doesn’t actually matter whether they are conditional, but people are far more likely to expect to be able to having overlapping conditional conformances.

What would be the problem with allowing multiple conformances to Equatable so long as the constraints are disjoint

From the language perspective, “disjoint” would have to mean that there are requirements that actively conflict, e.g., one extension has “Wrapped.Element == Int” and the other has “Wrapped.Element == String”.

There are implementation issues here deep in the type checker, e.g., because if a given type T can potential conform to a protocol P in multiple ways, it introduces a disjunction in the constraint solver that can push the constraint solver to be Even More Exponential.

For me, there’s also the usability issue, and that’s the key argument: the *human* has to reason about these things, too, and it is a whole lot simpler if “does T conform to P?” can only be answered in one way. I don’t think the use cases for having overlapping conformances justify such a drastic increase in complexity across the feature.

or the concrete type only adopts one of the available protocols?

Unless you assume that you have a fully-determined, closed system where you know about every potential conformance of a concrete type, this isn’t a question that can be answered at compile time.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#implied-conditional-conformances>Implied conditional conformances

Stating conformance to a protocol implicitly states conformances to any of the protocols that it inherits. This is the case in Swift today, although most developers likely don't realize the rules it follows. For example:

protocol P { }
protocol Q : P { }
protocol R : P { }

struct X1 { }
struct X2 { }
struct X3 { }

extension X1: Q { } // implies conformance to P

extension X2: Q { } // would imply conformance to P, but...
extension X2: P { } // explicitly-stated conformance to P "wins"

extension X3: Q { } // implies conformance to P
extension X3: R { } // also implies conformance to P
                     // one will "win"; which is unspecified

On X2 you’re declaring a redundant conformance to P but any protocol extensions will prefer Q and the compiler won’t let you redefine any members so you’ll have an incomplete conformance. Any explicit conformances (on the type or in extensions) are preferred over the defaults from the protocol extension, but that’s not new. I must be missing something, how would this be visible in Swift 3?

X2 states that it conforms to Q. That implies that it also conforms to P, because of course you can’t have a Q that isn’t a P.

Because X2 explicitly states that it conforms to P, the implication of P via Q doesn’t actually realize an actual conformance to P, because that conformance would be redundant. The rule is, basically, that an explicitly-stated conformance to a protocol suppresses any implied conformances to that protocol.

On X3, multiple implementations in protocol extensions are errors today and the resolution is to provide an explicit implementation on X3.

Not true! The code above is well-formed in Swift 3. Each extension of X3 above implies a conformance to P; it simply does not matter which extension actually realizes the conformance to P so long as only one of them does.

You could actually see which one it chooses by putting these into separate files—in the same module—and looking at the generated SIL.

With conditional conformances, the question of which extension "wins" the implied conformance begins to matter, because the extensions might have different constraints on them. For example:

struct X4<T> { }

extension X4: Q where T: Q { } // implies conformance to P
extension X4: R where T: R { } // error: implies overlapping conformance to P
Both of these constrained extensions imply a conformance to P, but the actual P implied conformances to P are overlapping and, therefore, result in an error.

If the related P conformance were inherited from conformance to Q or R then the rules would (IMHO) make more sense. Wouldn’t the extra rule you need simply be that either Q or R must provide a complete conformance to P (no mix-n-match)?

A conformance to P introduced by the first extension would not be usable by the second extension, because the conformance to P introduced by the first extension might depend on details of “T: Q”… and the second extension can’t assume that “T: Q”.

If T implements Q & P why not just ignore T: P which means the X4: R extension is no longer relevant.

Implementing Q implies implementing P.

It seems like the tricky case is T: P and the same question applies - why not just ignore the extensions (X4<T> in that scenario doesn’t implement Q, R, or P).

Not allowing ambiguity seems like it solves the “which one” problem and requiring an extension to provide the entire implementation (no mix-n-match) cuts down on the cleverness problem.

For reference, there was an early point in Swift 3.0 where I had added an error when it wasn’t clear which extension should realize a conformance to a protocol that was implied by multiple extensions (i.e., exactly the case of X3 that we discussed above), thinking that it would clear up the ambiguity and make code more obvious. Developers *hated* this error, because it doesn’t matter to the semantics of the program nor to their mental models, so I took it out.

However, in cases where there is a reasonable ordering between the two constrained extensions (i.e., one is more specialized than the other), the less specialized constrained extension should "win" the implied conformance. Continuing the example from above:

protocol S: R { }

struct X5<T> { }

extension X5: R where T: R { } // "wins" implied conformance to P, because
extension X5: S where T: S { } // the extension where "T: S" is more specialized
                                // than the one where "T: R"
Thus, the rule for placing implied conformances is to pick the least specialized extension that implies the conformance. If there is more than one such extension, then either:

All such extensions are not constrained extensions (i.e., they have no requirements beyond what the type requires), in which case Swift can continue to choose arbitrarily among the extensions, or
All such extensions are constrained extensions, in which case the program is ill-formed due to the ambiguity. The developer can explicitly specify conformance to the protocol to disambiguate.

What is the rationale for picking the least specialized extension? That’s not what I would naively expect to happen. If T: R & S then I would expect the more specialized S:R implementation to be preferred, and the explicit R implementation to kick in when T: R.

We have to pick the least-specialized extension, because it’s the only one that works. If you pick a more-specialized extension to realize the implied conformance to P, the less-specialized extension doesn’t have a conformance to P that it can rely on.

I’ll see about clarifying the proposal here, because the choice of (unique) least-specialized isn’t arbitrary: it’s the only answer that provides a correct result without introducing overlapping conformances.

  - Doug

···

On Sep 28, 2016, at 9:48 PM, Russ Bishop <xenadu@gmail.com> wrote:

On Sep 26, 2016, at 5:18 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:


(Douglas Gregor) #12

Nothing. These conformances are not overlapping, because A and B are independent protocols. The first extension declares a conditional conformance to A, the second declares a conditional conformance to B.

  - Doug

···

On Sep 28, 2016, at 2:55 AM, Anton Zhilin <antonyzhilin@gmail.com> wrote:

I find the limitation of non-intersection of conditional conformance reqirements quite limiting. Can it be lifted in case there are no overloaded functions between extensions?

protocol A { func foo() }
protocol B { func bar() }

extension Array: A where Element: A {
    func foo() { return self.first!.foo() }
}
extension Array: B where Element: B {
    func bar() { return self.first!.bar() }
}

let arr: Array<T>
arr.foo()

What is ambiguous here?


(Jordan Rose) #13

Great job thinking this all through (as usual), and I’ll be very happy to have Optional and Array become Equatable. Here’s some of my thoughts on the library evolution aspect of this:

- Removing a conditional conformance isn’t allowed, obviously.
- Adding a conditional conformance is just like adding an unconditional conformance—it needs availability info.

Right. The main wrinkle I see here is that, when you add a conditional conformance, you will effectively end up with overlapping conformances when running an old application against a new library. Do you want me to capture these cases in the proposal in a section on “Resilience” or “Library Evolution”, like I’ve tried to capture the effect on ABI Stability? (I think that makes sense)

Sure, yes please. (I think the main point is that the "conditional" doesn't make a difference here.)

- It would be nice™ if making a conditional conformance more general was allowed. Since the plan doesn't allow overlapping conformances, I think this is actually implementable: just don’t put the constraints in the symbol name. I don’t know how to represent the backwards-deploying aspects of this right now, so it probably makes sense to forbid it today, but I think it would be nice if the implementation left the door open.

Yeah. It’s a different set of witness tables that one would need to gather to use the conditional conformance in the newer version of the library vs. in an older version of a library. That’s okay if we leave the witness-table-gathering to the runtime, but not so great if we statically provide the witness tables.

This confuses me. Why aren't we just using the minimal (unconditional) conformance representation, and then pulling the associated type witness tables out dynamically? Is that significantly more expensive? (Am I just missing something?)

On that note, what happens here?

// Module Lib
public protocol Base {}
public protocol Sub: Base {}
public protocol Special: Sub {}

public struct Impl<T> {}
extension Impl: Special where T: Special {}

// Module Client
import Lib

extension Impl: Sub where T: Sub {}

I think this gets rejected because Impl already has a conformance to Sub—the extension in Client, despite being less specialized, shows up too late to actually declare this conformance “better”. Is that correct?

Correct. Impl has a conformance to ‘Sub’ in Lib; Client cannot declare a new one, because it overlaps. Had all of this code been in one module, it would be well-formed, because the implied conformance to ’Sub’ in the first extension would lose to the explicit conformance to Sub in the second (less-specialized) extension.

Thanks!

Jordan

···

On Sep 28, 2016, at 9:51, Douglas Gregor <dgregor@apple.com> wrote:

On Sep 27, 2016, at 5:06 PM, Jordan Rose <jordan_rose@apple.com <mailto:jordan_rose@apple.com>> wrote:


(Matthew Johnson) #14

Is the decision on "no-overlapping-conformances” something that’s seen-as set in stone permanently, set in stone for the near future, or perhaps at least somewhat open to reconsideration at the present moment?

There hasn’t been a decision per se, so it that sense it’s open to reconsideration.

I have a strong *personal* bias against overlapping conformances, because I feel that the amount of complexity that they introduce into the language and its implementation far outweigh any benefits.

I would like a bit further clarification on what the prohibition of overlapping conformances implies. For example, consider this modification of your example in a Swift that allows for same type constraints in extensions. Would this be allowed? There would be two different conformances to Foo for SomeWrapper, but they would never “overlap” (i.e. both be candidates for the same concrete type).
struct SomeWrapper<Wrapped> {
  let wrapped: Wrapped
}

protocol Foo {
associatedtype Bar
  func bar() -> Bar
}

extension SomeWrapper: Equatable where Wrapped == String {
  func bar() -> String {
    return “Hello"
  }
}

extension SomeWrapper: Equatable where Wrapped == Int {
  func bar() -> Int {
    return 0
  }
}
Secondarily, I understand the reason for letting the “least specific” candidate conformance win (it is the most general). But I wonder if this might leave performance on the table in some cases where a more specific implementation could use knowledge of the more specific details to implement the members more efficiently. Using the example in your proposal, what if knowing `T` conforms to `S`, not just `R` allows `X5` to provide a more efficient implementation of the members of `P` and `R`? If so, it seems unfortunate to leave that performance on the table. Is this a valid concern? Or is it unlikely to come up often enough in practice to matter?

···

Additionally, they enable use cases (e.g., static metaprogramming-ish tricks) that I feel would be actively harmful to the Swift language’s understandability. Generics systems can get very complicated very quickly, so any extension needs to be strongly motivated by use cases to matter to all or most Swift developers.

  - Doug

On Sep 26, 2016, at 7:18 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Conditional conformances

Proposal: SE-NNNN <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/NNNN-conditional-conformances.md>
Author: Doug Gregor <https://github.com/DougGregor>
Review Manager: TBD
Status: Awaiting review
During the review process, add the following fields as needed:

Decision Notes: Rationale <https://lists.swift.org/pipermail/swift-evolution/>, Additional Commentary <https://lists.swift.org/pipermail/swift-evolution/>
Bugs: SR-NNNN <https://bugs.swift.org/browse/SR-NNNN>, SR-MMMM <https://bugs.swift.org/browse/SR-MMMM>
Previous Revision: 1 <https://github.com/apple/swift-evolution/blob/...commit-ID.../proposals/NNNN-filename.md>
Previous Proposal: SE-XXXX <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/XXXX-filename.md>
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#introduction>Introduction

Conditional conformances express the notion that a generic type will conform to a particular protocol only when it's type arguments meet certain requirements. For example, the Array collection can implement the Equatable protocol only when its elements are themselves Equatable, which can be expressed via the following conditional conformance on Equatable:

extension Array: Equatable where Element: Equatable {
  static func ==(lhs: Array<T>, rhs: Array<T>) -> Bool { ... }
}
This feature is part of the generics manifesto <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-> because it's something that fits naturally into the generics model and is expected to have a high impact on the Swift standard library.

Swift-evolution thread: TBD: Discussion thread topic for that proposal <https://lists.swift.org/pipermail/swift-evolution/>
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#motivation>Motivation

Conditional conformances address a hole in the composability of the generics system. Continuing the Array example from above, it's always been the case that one could use the == operator on two arrays of Equatable type, e.g., [Int]() == [Int]() would succeed. However, it doesn't compose: arrays of arrays of Equatable types cannot be compared (e.g.,[Int] <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals>== [Int] <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals>will fail to compile) because, even though there is an==for arrays of Equatabletype, the arrays themselves are neverEquatable`.

Conditional conformances are particularly powerful when building generic adapter types, which are intended to reflect the capabilities of their type arguments. For example, consider the "lazy" functionality of the Swift standard library's collections: using the lazy member of a sequence produces a lazy adapter that conforms to the Sequence protocol, while using the lazy member of a collection produces a lazy adapter that conforms to the Collection protocol. In Swift 3, the only way to model this is with different types. For example, the Swift standard library has four similar generic types to handle a lazy collection: LazySequence, LazyCollection, LazyBidirectionalCollection, and LazyRandomAccessCollection. The Swift standard library uses overloading of the lazy property to decide among these:

extension Sequence {
  var lazy: LazySequence<Self> { ... }
}

extension Collection {
  var lazy: LazyCollection<Self> { ... }
}

extension BidirectionalCollection {
  var lazy: LazyBidirectionalCollection<Self> { ... }
}

extension RandomAccessCollection {
  var lazy: LazyRandomAccessCollection<Self> { ... }
}
This approach causes an enormous amount of repetition, and doesn't scale well because each more-capable type has to re-implement (or somehow forward the implementation of) all of the APIs of the less-capable versions. With conditional conformances, one can provide a single generic wrapper type whose basic requirements meet the lowest common denominator (e.g., Sequence), but which scale their capabilities with their type argument (e.g., the LazySequence conforms to Collection when the type argument does, and so on).

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#proposed-solution>Proposed solution

In a nutshell, the proposed solution is to allow a constrained extension of a struct, enum, or class to declare protocol conformances. No additional syntax is necessary for this change, because it already exists in the grammar; rather, this proposal removes the limitation that results in the following error:

t.swift:1:1: error: extension of type 'Array' with constraints cannot have an inheritance clause
extension Array: Equatable where Element: Equatable { }
^ ~~~~~~~~~
Conditional conformances can only be used when the additional requirements of the constrained extension are satisfied. For example, given the aforementioned Array conformance to Equatable:

func f<T: Equatable>(_: T) { ... }

struct NotEquatable { }

func test(a1: [Int], a2: [NotEquatable]) {
  f(a1) // okay: [Int] conforms to Equatable because Int conforms to Equatable
  f(a2) // error: [NotEquatable] does not conform to Equatable because NotEquatable has no conformance to Equatable
}
Conditional conformances also have a run-time aspect, because a dynamic check for a protocol conformance might rely on the evaluation of the extra requirements needed to successfully use a conditional conformance. For example:

protocol P {
  func doSomething()
}

struct S: P {
  func doSomething() { print("S") }
}

// Array conforms to P if it's element type conforms to P
extension Array: P where Element: P {
  func doSomething() {
    for value in self {
      value.doSomething()
    }
  }
}

// Dynamically query and use conformance to P.
func doSomethingIfP(_ value: Any) {
  if let p = value as? P {
    p.doSomething()
  } else {
    print("Not a P")
  }
}

doSomethingIfP([S(), S(), S()]) // prints "S" three times
doSomethingIfP([1, 2, 3]) // prints "Not a P"
The if-let in doSomethingIfP(_:slight_smile: dynamically queries whether the type stored in value conforms to the protocol P. In the case of an Array, that conformance is conditional, which requires another dynamic lookup to determine whether the element type conforms to P: in the first call to doSomethingIfP(_:), the lookup finds the conformance of S to P. In the second case, there is no conformance of Int to P, so the conditional conformance cannot be used. The desire for this dynamic behavior motivates some of the design decisions in this proposal.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#detailed-design>Detailed design

Most of the semantics of conditional conformances are obvious. However, there are a number of issues (mostly involving multiple conformances) that require more in-depth design.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#disallow-overlapping-conformances>Disallow overlapping conformances

With conditional conformances, it is possible to express that a given generic type can conform to the same protocol in two different ways, depending on the capabilities of its type arguments. For example:

struct SomeWrapper<Wrapped> {
  let wrapped: Wrapped
}

protocol HasIdentity {
  static func ===(lhs: Self, rhs: Self) -> Bool
}

extension SomeWrapper: Equatable where Wrapped: Equatable {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
}

extension SomeWrapper: Equatable where Wrapped: HasIdentity {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped === rhs.wrapped
  }
}
Note that, for an arbitrary type T, there are four potential answers to the question of whether SomeWrapper<T> conforms to Equatable:

No, it does not conform because T is neither Equatable nor HasIdentity.
Yes, it conforms via the first extension of SomeWrapper because T conforms to Equatable.
Yes, it conforms via the second extension of SomeWrapper because T conforms to HasIdentity.
Ambiguity, because T conforms to both Equatable and HasIdentity.
It is due to the possibility of #4 occurring that we refer to the two conditional conformances in the example as overlapping. There are designs that would allow one to address the ambiguity, for example, by writing a third conditional conformance that addresses #4:

// Possible tie-breaker conformance
extension SomeWrapper: Equatable where Wrapped: Equatable & HasIdentity, {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
}
The design is consistent, because this third conditional conformance is more specialized the either of the first two conditional conformances, meaning that its requirements are a strict superset of the requirements of those two conditional conformances. However, there are a few downsides to such a system:

To address all possible ambiguities, one has to write a conditional conformance for every plausible combination of overlapping requirements. To statically resolve all ambiguities, one must also cover nonsensical combinations where the two requirements are mutually exclusive (or invent a way to state mutual-exclusivity).
It is no longer possible to uniquely say what is required to make a generic type conform to a protocol, because there might be several unrelated possibilities. This makes reasoning about the whole system more complex, because it admits divergent interfaces for the same generic type based on their type arguments. At its extreme, this invites the kind of cleverness we've seen in the C++ community with template metaprogramming, which is something Swift has sought to avoid.
All of the disambiguation machinery required at compile time (e.g., to determine whether one conditional conformance is more specialized than another to order them) also needs to implements in the run-time, as part of the dynamic casting machinery. One must also address the possibility of ambiguities occurring at run-time. This is both a sharp increase in the complexity of the system and a potential run-time performance hazard.
For these reasons, this proposal bans overlapping conformances entirely. While the resulting system is less flexible than one that allowed overlapping conformances, the gain in simplicity in this potentially-confusing area is well worth the cost. Moreover, this ban follows with existing Swift rules regarding multiple conformances, which prohibit the same type from conforming to the same protocol in two different ways:

protocol P { }

struct S : P { }
extension S : P { } // error: S already conforms to P
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#implied-conditional-conformances>Implied conditional conformances

Stating conformance to a protocol implicitly states conformances to any of the protocols that it inherits. This is the case in Swift today, although most developers likely don't realize the rules it follows. For example:

protocol P { }
protocol Q : P { }
protocol R : P { }

struct X1 { }
struct X2 { }
struct X3 { }

extension X1: Q { } // implies conformance to P

extension X2: Q { } // would imply conformance to P, but...
extension X2: P { } // explicitly-stated conformance to P "wins"

extension X3: Q { } // implies conformance to P
extension X3: R { } // also implies conformance to P
                     // one will "win"; which is unspecified
With conditional conformances, the question of which extension "wins" the implied conformance begins to matter, because the extensions might have different constraints on them. For example:

struct X4<T> { }

extension X4: Q where T: Q { } // implies conformance to P
extension X4: R where T: R { } // error: implies overlapping conformance to P
Both of these constrained extensions imply a conformance to P, but the actual P implied conformances to P are overlapping and, therefore, result in an error.

However, in cases where there is a reasonable ordering between the two constrained extensions (i.e., one is more specialized than the other), the less specialized constrained extension should "win" the implied conformance. Continuing the example from above:

protocol S: R { }

struct X5<T> { }

extension X5: R where T: R { } // "wins" implied conformance to P, because
extension X5: S where T: S { } // the extension where "T: S" is more specialized
                                // than the one where "T: R"
Thus, the rule for placing implied conformances is to pick the least specialized extension that implies the conformance. If there is more than one such extension, then either:

All such extensions are not constrained extensions (i.e., they have no requirements beyond what the type requires), in which case Swift can continue to choose arbitrarily among the extensions, or
All such extensions are constrained extensions, in which case the program is ill-formed due to the ambiguity. The developer can explicitly specify conformance to the protocol to disambiguate.
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#overloading-across-constrained-extensions>Overloading across constrained extensions

One particularly important aspect of the placement rule for implied conformances is that it affects which declarations are used to satisfy a particular requirement. For example:

protocol P {
  func f()
}

protocol Q: P { }
protocol R: Q { }

struct X1<T> { }

extension X1: Q where T: Q { // note: implied conformance to P here
  func f() {
    // #1: basic implementation of 'f()'
  }
}

extension X1: R where T: R {
  func f() {
    // #2: superfast implementation of f() using some knowledge of 'R'
  }
}

struct X2: R {
  func f() { }
}

(X1<X2>() as P).f() // calls #1, which was used to satisfy the requirement for 'f'
X1<X2>().f() // calls #2, which is preferred by overload resolution
Effectively, when satisfying a protocol requirement, one can only choose from members of the type that are guaranteed to available within the extension with which the conformance is associated. In this case, the conformance to P is placed on the first extension of X1, so the only f() that can be considered is the f() within that extension: the f() in the second extension won't necessarily always be available, because T may not conform to R. Hence, the call that treats an X1<X2>as a P gets the first implementation of X1.f(). When using the concrete type X1<X2>, where X2 conforms to R, both X.f() implementations are visible... and the second is more specialized.

Technically, this issue is no different from surprises where (e.g.) a member added to a concrete type in a different module won't affect an existing protocol conformance. The existing ideas to mediate these problems---warning for nearly-matching functions when they are declared in concrete types, for example---will likely be sufficient to help surprised users. That said, this proposal may increase the likelihood of such problems showing up.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#source-compatibility>Source compatibility

From the language perspective, conditional conformances are purely additive. They introduce no new syntax, but instead provide semantics for existing syntax---an extension that both declares a protocol conformance and has a where clause---whose use currently results in a type checker failure. That said, this is a feature that is expected to be widely adopted within the Swift standard library, which may indirectly affect source compatibility.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#effect-on-abi-stability>Effect on ABI Stability

As noted above, there are a number of places where the standard library is expected to adopt this feature, which fall into two classes:

Improve composability: the example in the introduction <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/Introduction> made Array conform to Equatable when its element type does; there are many places in the Swift standard library that could benefit from this form of conditional conformance, particularly so that collections and other types that contain values (e.g., Optional) can compose better with generic algorithms. Most of these changes won't be ABI- or source-breaking, because they're additive.
Eliminating repetition: the lazy wrappers described in the motivation <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/motivation> section could be collapsed into a single wrapper with several conditional conformances. A similar refactoring could also be applied to the range abstractions and slice types in the standard library, making the library itself simpler and smaller. All of these changes are potentially source-breaking and ABI-breaking, because they would remove types that could be used in Swift 3 code. However, there are mitigations: generic typealiases could provide source compatibility to Swift 3 clients, and the ABI-breaking aspect is only relevant if conditional conformances and the standard library changes they imply aren't part of Swift 4.
Aside from the standard library, conditional conformances have an impact on the Swift runtime, which will require specific support to handle dynamic casting. If that runtime support is not available once ABI stability has been declared, then introducing conditional conformances in a later language version either means the feature cannot be deployed backward or that it would provide only more limited, static behavior when used on older runtimes. Hence, there is significant motivation for doing this feature as part of Swift 4. Even if we waited to introduce conditional conformances, we would want to include a hook in the runtime to allow them to be implemented later, to avoid future backward-compatibility issues.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#alternatives-considered>Alternatives considered

The most common request related to conditional conformances is to allow a (constrained) protocol extension to declare conformance to a protocol. For example:

extension Collection: Equatable where Iterator.Element: Equatable {
  static func ==(lhs: Self, rhs: Self) -> Bool {
    // ...
  }
}
This protocol extension will make any Collection of Equatable elements Equatable, which is a powerful feature that could be put to good use. Introducing conditional conformances for protocol extensions would exacerbate the problem of overlapping conformances, because it would be unreasonable to say that the existence of the above protocol extension means that no type that conforms to Collection could declare its own conformance to Equatable, conditional or otherwise.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto: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


(Goffredo Marocchi) #15

Great job thinking this all through (as usual), and I’ll be very happy to have Optional and Array become Equatable. Here’s some of my thoughts on the library evolution aspect of this:

- Removing a conditional conformance isn’t allowed, obviously.
- Adding a conditional conformance is just like adding an unconditional conformance—it needs availability info.

Right. The main wrinkle I see here is that, when you add a conditional conformance, you will effectively end up with overlapping conformances when running an old application against a new library. Do you want me to capture these cases in the proposal in a section on “Resilience” or “Library Evolution”, like I’ve tried to capture the effect on ABI Stability? (I think that makes sense)

- It would be nice™ if making a conditional conformance more general was allowed. Since the plan doesn't allow overlapping conformances, I think this is actually implementable: just don’t put the constraints in the symbol name. I don’t know how to represent the backwards-deploying aspects of this right now, so it probably makes sense to forbid it today, but I think it would be nice if the implementation left the door open.

Yeah. It’s a different set of witness tables that one would need to gather to use the conditional conformance in the newer version of the library vs. in an older version of a library. That’s okay if we leave the witness-table-gathering to the runtime, but not so great if we statically provide the witness tables.

Would this be a case in which the win by having this feature and letting the runtime gather the witness tables offset the losses from doing his operations at runtime? I would like to think that in cases like this there is at least the option to opt for more flexibility.

···

Sent from my iPhone

On 28 Sep 2016, at 17:51, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

On Sep 27, 2016, at 5:06 PM, Jordan Rose <jordan_rose@apple.com> wrote:

On that note, what happens here?

// Module Lib
public protocol Base {}
public protocol Sub: Base {}
public protocol Special: Sub {}

public struct Impl<T> {}
extension Impl: Special where T: Special {}

// Module Client
import Lib

extension Impl: Sub where T: Sub {}

I think this gets rejected because Impl already has a conformance to Sub—the extension in Client, despite being less specialized, shows up too late to actually declare this conformance “better”. Is that correct?

Correct. Impl has a conformance to ‘Sub’ in Lib; Client cannot declare a new one, because it overlaps. Had all of this code been in one module, it would be well-formed, because the implied conformance to ’Sub’ in the first extension would lose to the explicit conformance to Sub in the second (less-specialized) extension.

  - Doug

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


(Russ Bishop) #16

What other designs were considered and rejected? It seems like some kind of escape hatch would be preferred if you happen to get into this situation, though you make some really good points about the pitfalls.

I don’t have a fully-baked alternative proposal—it would probably have to involve some kind of preference rule for picking the “best” set of (consistent!) conformances to satisfy a particular request, introduce a disambiguation syntax for cases where that preference rule does the wrong thing, and some way of teaching the dynamic-casting machinery to do the same thing.

Yeah your description is already sounding like a lot of work :slight_smile:

Just to clarify when you say “bans” do you mean if Wrapped: Equatable & HasIdentity then SomeWrapper is not Equatable, or do you mean you get a compile error because there are two constrained conformances SomeWrapper: Equatable?

You get a compile error if there are two conformances of SomeWrapper to Equatable; it doesn’t actually matter whether they are conditional, but people are far more likely to expect to be able to having overlapping conditional conformances.

Just to clarify in my mind, the problem here is that Swift would need runtime machinery to look at Wrapped and select the conformance to Equatable based on whether Wrapped: Equatable or Wrapped: HasIdentity. Is that right? Otherwise with the proposal as written Swift would need to check Wrapped to validate the constraints but once it does there is only one implementation of the conformance to pick from.

I believe you about the type checker, I’m just naively assuming inserting a table to select the correct conformance isn’t a big cost because you would canonicalize the constraints and being disjoint for any type T there would only ever be one matching entry.

What would be the problem with allowing multiple conformances to Equatable so long as the constraints are disjoint

From the language perspective, “disjoint” would have to mean that there are requirements that actively conflict, e.g., one extension has “Wrapped.Element == Int” and the other has “Wrapped.Element == String”.

Yes, I was also imagining protocols so long as there is no protocol they share in common except the empty protocol.

There are implementation issues here deep in the type checker, e.g., because if a given type T can potential conform to a protocol P in multiple ways, it introduces a disjunction in the constraint solver that can push the constraint solver to be Even More Exponential.

That’s Bad ™️

For me, there’s also the usability issue, and that’s the key argument: the *human* has to reason about these things, too, and it is a whole lot simpler if “does T conform to P?” can only be answered in one way. I don’t think the use cases for having overlapping conformances justify such a drastic increase in complexity across the feature.

Constraints are already introducing some complexity there (which is worth it IMHO). You can’t just answer the question is Array: Equatable? You need to know about T.

or the concrete type only adopts one of the available protocols?

Unless you assume that you have a fully-determined, closed system where you know about every potential conformance of a concrete type, this isn’t a question that can be answered at compile time.

The problem is importing a random library can immediately introduce breakage when it is a compile error, or worse if both reference a shared library you also import… unless we’re saying extensions of types outside your module are only visible in the declaring module which is pretty restrictive e.g. some UI toolkit extending UIKit/AppKit classes with conveniences, or extending Array to say it CanLayout if elements are views where calling a.layout() tells all the views in the array to layout. In that example neither the views nor Array would be declared in the module doing the extending.

Now let’s say I want to use the swift-protobuf library and I also use GenericSocialMediaService’ SDK that also incorporates swift-protobuf. I’m just imagining what happens when we both try to define extensions. It would be nice if they could declare Array: ProtobufMessage where Element: GSMSEntityProtocol but I was able to provide Array: ProtobufMessage where Element: MyOwnProtocol.

That said the restrictions can always be relaxed later. I’d rather have this feature without overlapping conformances than not have it.

With conditional conformances, the question of which extension "wins" the implied conformance begins to matter, because the extensions might have different constraints on them. For example:

struct X4<T> { }

extension X4: Q where T: Q { } // implies conformance to P
extension X4: R where T: R { } // error: implies overlapping conformance to P
Both of these constrained extensions imply a conformance to P, but the actual P implied conformances to P are overlapping and, therefore, result in an error.

If the related P conformance were inherited from conformance to Q or R then the rules would (IMHO) make more sense. Wouldn’t the extra rule you need simply be that either Q or R must provide a complete conformance to P (no mix-n-match)?

A conformance to P introduced by the first extension would not be usable by the second extension, because the conformance to P introduced by the first extension might depend on details of “T: Q”… and the second extension can’t assume that “T: Q”.

What I’m saying is that if T: Q then the entire implementation of P must come from the first extension. If T: R then the entire implementation of P must come from the second extension. If T: P then neither extension applies because there are overlapping extensions. Basically if there is any overlap then the compiler only considers explicit extensions that match without ambiguity, otherwise the extension is ignored.

func takes<Value: P>(value: Value) { }

struct CQ: Q { }
struct CR: R { }
struct CP: P { }

takes(X4<CQ>()) //fine, uses first extension
takes(X4<CR>()) //fine, uses second extension
takes(X4<CP>()) //error: ambiguous conformance

This relates to the disjoint discussion above:

extension X4: P where T: P { } //error: ambiguous conformance

Even though there is technically a conformance to P available we just ignore it. Seems like this would be knowable statically by looking at the extensions and the protocol relationships in the constraints?

What is the rationale for picking the least specialized extension? That’s not what I would naively expect to happen. If T: R & S then I would expect the more specialized S:R implementation to be preferred, and the explicit R implementation to kick in when T: R.

We have to pick the least-specialized extension, because it’s the only one that works. If you pick a more-specialized extension to realize the implied conformance to P, the less-specialized extension doesn’t have a conformance to P that it can rely on.

That’s what I was trying to address by saying no mix-n-match. If you’re going to wonder into overlapping territory you must supply two entirely separate implementations of P, one explicit and one inside the Q extension. (I fully admit that might not help the implementation complexity - I don’t know enough about the type checker to answer that).

I’ll see about clarifying the proposal here, because the choice of (unique) least-specialized isn’t arbitrary: it’s the only answer that provides a correct result without introducing overlapping conformances.

  - Doug

Thanks for your work on this proposal!

Russ

···

On Sep 29, 2016, at 11:12 AM, Douglas Gregor <dgregor@apple.com> wrote:

On Sep 28, 2016, at 9:48 PM, Russ Bishop <xenadu@gmail.com <mailto:xenadu@gmail.com>> wrote:


(David Hart) #17

Slightly off-topic but I was hit quick badly by this recently because two libraries I was trying to import both conformed UIControlState to Hashable to be able to use it as Dictionary indices. It seems like something that might happen kind of regularly with important protocols like Hashable and Equatable.

Is there any plans to address those issues and might it have an effect on this proposal?

···

On 29 Sep 2016, at 20:12, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

You get a compile error if there are two conformances of SomeWrapper to Equatable; it doesn’t actually matter whether they are conditional, but people are far more likely to expect to be able to having overlapping conditional conformances.


(plx) #18

It’s good to see this starting to happen!

Is the decision on "no-overlapping-conformances” something that’s seen-as set in stone permanently, set in stone for the near future, or perhaps at least somewhat open to reconsideration at the present moment?

There hasn’t been a decision per se, so it that sense it’s open to reconsideration.

I see. A related question: if overlapping conditional conformances are disallowed in Swift 4, would e.g. ABI concerns make it infeasible to relax that restriction in future Swift (5, 6, X, etc.)?

FWIW my overall 2c is that the right move right now is to leave out overlapping conformances due to the complexity…as long as doing so now doesn’t realistically mean never being able to relax that restriction at some later date. I realize it’s always *possible* to relax it, so to try and be even clearer I really mean “possible to relax it without having to compromise on things like ABI-stability (etc.)”.

Also FWIW my suspicion is that in the absence of overlapping conformances some real pain points will be discovered—and those points *could* be addressed via overlapping conformances—but I also suspect that the majority of these pain points will also be addressable via some simpler mechanism (a constrained form of overlapping, macros, easy wrapper synthesis, etc.).

Thus I’m in favor of banning conditional conformances for now unless doing so now would be the same as doing so “forever”, so to speak.

I have a strong *personal* bias against overlapping conformances, because I feel that the amount of complexity that they introduce into the language and its implementation far outweigh any benefits. Additionally, they enable use cases (e.g., static metaprogramming-ish tricks) that I feel would be actively harmful to the Swift language’s understandability. Generics systems can get very complicated very quickly, so any extension needs to be strongly motivated by use cases to matter to all or most Swift developers.

This is purely anecdotal but I had a lot of utility code laying around that I’d marked with notes like `// TODO: revisit once conditional conformances are available`.

When I was leaving those notes I was expecting to need overlapping conformances often, but I reviewed them *before* replying and I actually haven’t found an example where having overlapping conformances is both (1) a significant win and also (2) a win in a way that’d be of broad, general interest.

- 80% have no real need for overlapping conditional conformances
- 15% might have “elegance gains” but nothing practically-significant
- 5% would *probably* see real gains but are likely not of broad interest

…which wasn’t what I was expecting, but leaves me a lot more comfortable without overlapping conformances for now than I was in the abstract.

···

On Sep 28, 2016, at 5:53 PM, Douglas Gregor <dgregor@apple.com> wrote:

On Sep 28, 2016, at 1:28 PM, plx via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

  - Doug

On Sep 26, 2016, at 7:18 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Conditional conformances

Proposal: SE-NNNN <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/NNNN-conditional-conformances.md>
Author: Doug Gregor <https://github.com/DougGregor>
Review Manager: TBD
Status: Awaiting review
During the review process, add the following fields as needed:

Decision Notes: Rationale <https://lists.swift.org/pipermail/swift-evolution/>, Additional Commentary <https://lists.swift.org/pipermail/swift-evolution/>
Bugs: SR-NNNN <https://bugs.swift.org/browse/SR-NNNN>, SR-MMMM <https://bugs.swift.org/browse/SR-MMMM>
Previous Revision: 1 <https://github.com/apple/swift-evolution/blob/...commit-ID.../proposals/NNNN-filename.md>
Previous Proposal: SE-XXXX <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/XXXX-filename.md>
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#introduction>Introduction

Conditional conformances express the notion that a generic type will conform to a particular protocol only when it's type arguments meet certain requirements. For example, the Array collection can implement the Equatable protocol only when its elements are themselves Equatable, which can be expressed via the following conditional conformance on Equatable:

extension Array: Equatable where Element: Equatable {
  static func ==(lhs: Array<T>, rhs: Array<T>) -> Bool { ... }
}
This feature is part of the generics manifesto <https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#conditional-conformances-> because it's something that fits naturally into the generics model and is expected to have a high impact on the Swift standard library.

Swift-evolution thread: TBD: Discussion thread topic for that proposal <https://lists.swift.org/pipermail/swift-evolution/>
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#motivation>Motivation

Conditional conformances address a hole in the composability of the generics system. Continuing the Array example from above, it's always been the case that one could use the == operator on two arrays of Equatable type, e.g., [Int]() == [Int]() would succeed. However, it doesn't compose: arrays of arrays of Equatable types cannot be compared (e.g.,[Int] <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals>== [Int] <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals>will fail to compile) because, even though there is an==for arrays of Equatabletype, the arrays themselves are neverEquatable`.

Conditional conformances are particularly powerful when building generic adapter types, which are intended to reflect the capabilities of their type arguments. For example, consider the "lazy" functionality of the Swift standard library's collections: using the lazy member of a sequence produces a lazy adapter that conforms to the Sequence protocol, while using the lazy member of a collection produces a lazy adapter that conforms to the Collection protocol. In Swift 3, the only way to model this is with different types. For example, the Swift standard library has four similar generic types to handle a lazy collection: LazySequence, LazyCollection, LazyBidirectionalCollection, and LazyRandomAccessCollection. The Swift standard library uses overloading of the lazy property to decide among these:

extension Sequence {
  var lazy: LazySequence<Self> { ... }
}

extension Collection {
  var lazy: LazyCollection<Self> { ... }
}

extension BidirectionalCollection {
  var lazy: LazyBidirectionalCollection<Self> { ... }
}

extension RandomAccessCollection {
  var lazy: LazyRandomAccessCollection<Self> { ... }
}
This approach causes an enormous amount of repetition, and doesn't scale well because each more-capable type has to re-implement (or somehow forward the implementation of) all of the APIs of the less-capable versions. With conditional conformances, one can provide a single generic wrapper type whose basic requirements meet the lowest common denominator (e.g., Sequence), but which scale their capabilities with their type argument (e.g., the LazySequence conforms to Collection when the type argument does, and so on).

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#proposed-solution>Proposed solution

In a nutshell, the proposed solution is to allow a constrained extension of a struct, enum, or class to declare protocol conformances. No additional syntax is necessary for this change, because it already exists in the grammar; rather, this proposal removes the limitation that results in the following error:

t.swift:1:1: error: extension of type 'Array' with constraints cannot have an inheritance clause
extension Array: Equatable where Element: Equatable { }
^ ~~~~~~~~~
Conditional conformances can only be used when the additional requirements of the constrained extension are satisfied. For example, given the aforementioned Array conformance to Equatable:

func f<T: Equatable>(_: T) { ... }

struct NotEquatable { }

func test(a1: [Int], a2: [NotEquatable]) {
  f(a1) // okay: [Int] conforms to Equatable because Int conforms to Equatable
  f(a2) // error: [NotEquatable] does not conform to Equatable because NotEquatable has no conformance to Equatable
}
Conditional conformances also have a run-time aspect, because a dynamic check for a protocol conformance might rely on the evaluation of the extra requirements needed to successfully use a conditional conformance. For example:

protocol P {
  func doSomething()
}

struct S: P {
  func doSomething() { print("S") }
}

// Array conforms to P if it's element type conforms to P
extension Array: P where Element: P {
  func doSomething() {
    for value in self {
      value.doSomething()
    }
  }
}

// Dynamically query and use conformance to P.
func doSomethingIfP(_ value: Any) {
  if let p = value as? P {
    p.doSomething()
  } else {
    print("Not a P")
  }
}

doSomethingIfP([S(), S(), S()]) // prints "S" three times
doSomethingIfP([1, 2, 3]) // prints "Not a P"
The if-let in doSomethingIfP(_:slight_smile: dynamically queries whether the type stored in value conforms to the protocol P. In the case of an Array, that conformance is conditional, which requires another dynamic lookup to determine whether the element type conforms to P: in the first call to doSomethingIfP(_:), the lookup finds the conformance of S to P. In the second case, there is no conformance of Int to P, so the conditional conformance cannot be used. The desire for this dynamic behavior motivates some of the design decisions in this proposal.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#detailed-design>Detailed design

Most of the semantics of conditional conformances are obvious. However, there are a number of issues (mostly involving multiple conformances) that require more in-depth design.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#disallow-overlapping-conformances>Disallow overlapping conformances

With conditional conformances, it is possible to express that a given generic type can conform to the same protocol in two different ways, depending on the capabilities of its type arguments. For example:

struct SomeWrapper<Wrapped> {
  let wrapped: Wrapped
}

protocol HasIdentity {
  static func ===(lhs: Self, rhs: Self) -> Bool
}

extension SomeWrapper: Equatable where Wrapped: Equatable {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
}

extension SomeWrapper: Equatable where Wrapped: HasIdentity {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped === rhs.wrapped
  }
}
Note that, for an arbitrary type T, there are four potential answers to the question of whether SomeWrapper<T> conforms to Equatable:

No, it does not conform because T is neither Equatable nor HasIdentity.
Yes, it conforms via the first extension of SomeWrapper because T conforms to Equatable.
Yes, it conforms via the second extension of SomeWrapper because T conforms to HasIdentity.
Ambiguity, because T conforms to both Equatable and HasIdentity.
It is due to the possibility of #4 occurring that we refer to the two conditional conformances in the example as overlapping. There are designs that would allow one to address the ambiguity, for example, by writing a third conditional conformance that addresses #4:

// Possible tie-breaker conformance
extension SomeWrapper: Equatable where Wrapped: Equatable & HasIdentity, {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapper>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
}
The design is consistent, because this third conditional conformance is more specialized the either of the first two conditional conformances, meaning that its requirements are a strict superset of the requirements of those two conditional conformances. However, there are a few downsides to such a system:

To address all possible ambiguities, one has to write a conditional conformance for every plausible combination of overlapping requirements. To statically resolve all ambiguities, one must also cover nonsensical combinations where the two requirements are mutually exclusive (or invent a way to state mutual-exclusivity).
It is no longer possible to uniquely say what is required to make a generic type conform to a protocol, because there might be several unrelated possibilities. This makes reasoning about the whole system more complex, because it admits divergent interfaces for the same generic type based on their type arguments. At its extreme, this invites the kind of cleverness we've seen in the C++ community with template metaprogramming, which is something Swift has sought to avoid.
All of the disambiguation machinery required at compile time (e.g., to determine whether one conditional conformance is more specialized than another to order them) also needs to implements in the run-time, as part of the dynamic casting machinery. One must also address the possibility of ambiguities occurring at run-time. This is both a sharp increase in the complexity of the system and a potential run-time performance hazard.
For these reasons, this proposal bans overlapping conformances entirely. While the resulting system is less flexible than one that allowed overlapping conformances, the gain in simplicity in this potentially-confusing area is well worth the cost. Moreover, this ban follows with existing Swift rules regarding multiple conformances, which prohibit the same type from conforming to the same protocol in two different ways:

protocol P { }

struct S : P { }
extension S : P { } // error: S already conforms to P
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#implied-conditional-conformances>Implied conditional conformances

Stating conformance to a protocol implicitly states conformances to any of the protocols that it inherits. This is the case in Swift today, although most developers likely don't realize the rules it follows. For example:

protocol P { }
protocol Q : P { }
protocol R : P { }

struct X1 { }
struct X2 { }
struct X3 { }

extension X1: Q { } // implies conformance to P

extension X2: Q { } // would imply conformance to P, but...
extension X2: P { } // explicitly-stated conformance to P "wins"

extension X3: Q { } // implies conformance to P
extension X3: R { } // also implies conformance to P
                     // one will "win"; which is unspecified
With conditional conformances, the question of which extension "wins" the implied conformance begins to matter, because the extensions might have different constraints on them. For example:

struct X4<T> { }

extension X4: Q where T: Q { } // implies conformance to P
extension X4: R where T: R { } // error: implies overlapping conformance to P
Both of these constrained extensions imply a conformance to P, but the actual P implied conformances to P are overlapping and, therefore, result in an error.

However, in cases where there is a reasonable ordering between the two constrained extensions (i.e., one is more specialized than the other), the less specialized constrained extension should "win" the implied conformance. Continuing the example from above:

protocol S: R { }

struct X5<T> { }

extension X5: R where T: R { } // "wins" implied conformance to P, because
extension X5: S where T: S { } // the extension where "T: S" is more specialized
                                // than the one where "T: R"
Thus, the rule for placing implied conformances is to pick the least specialized extension that implies the conformance. If there is more than one such extension, then either:

All such extensions are not constrained extensions (i.e., they have no requirements beyond what the type requires), in which case Swift can continue to choose arbitrarily among the extensions, or
All such extensions are constrained extensions, in which case the program is ill-formed due to the ambiguity. The developer can explicitly specify conformance to the protocol to disambiguate.
<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#overloading-across-constrained-extensions>Overloading across constrained extensions

One particularly important aspect of the placement rule for implied conformances is that it affects which declarations are used to satisfy a particular requirement. For example:

protocol P {
  func f()
}

protocol Q: P { }
protocol R: Q { }

struct X1<T> { }

extension X1: Q where T: Q { // note: implied conformance to P here
  func f() {
    // #1: basic implementation of 'f()'
  }
}

extension X1: R where T: R {
  func f() {
    // #2: superfast implementation of f() using some knowledge of 'R'
  }
}

struct X2: R {
  func f() { }
}

(X1<X2>() as P).f() // calls #1, which was used to satisfy the requirement for 'f'
X1<X2>().f() // calls #2, which is preferred by overload resolution
Effectively, when satisfying a protocol requirement, one can only choose from members of the type that are guaranteed to available within the extension with which the conformance is associated. In this case, the conformance to P is placed on the first extension of X1, so the only f() that can be considered is the f() within that extension: the f() in the second extension won't necessarily always be available, because T may not conform to R. Hence, the call that treats an X1<X2>as a P gets the first implementation of X1.f(). When using the concrete type X1<X2>, where X2 conforms to R, both X.f() implementations are visible... and the second is more specialized.

Technically, this issue is no different from surprises where (e.g.) a member added to a concrete type in a different module won't affect an existing protocol conformance. The existing ideas to mediate these problems---warning for nearly-matching functions when they are declared in concrete types, for example---will likely be sufficient to help surprised users. That said, this proposal may increase the likelihood of such problems showing up.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#source-compatibility>Source compatibility

From the language perspective, conditional conformances are purely additive. They introduce no new syntax, but instead provide semantics for existing syntax---an extension that both declares a protocol conformance and has a where clause---whose use currently results in a type checker failure. That said, this is a feature that is expected to be widely adopted within the Swift standard library, which may indirectly affect source compatibility.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#effect-on-abi-stability>Effect on ABI Stability

As noted above, there are a number of places where the standard library is expected to adopt this feature, which fall into two classes:

Improve composability: the example in the introduction <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/Introduction> made Array conform to Equatable when its element type does; there are many places in the Swift standard library that could benefit from this form of conditional conformance, particularly so that collections and other types that contain values (e.g., Optional) can compose better with generic algorithms. Most of these changes won't be ABI- or source-breaking, because they're additive.
Eliminating repetition: the lazy wrappers described in the motivation <https://github.com/DougGregor/swift-evolution/blob/conditional-conformances/proposals/motivation> section could be collapsed into a single wrapper with several conditional conformances. A similar refactoring could also be applied to the range abstractions and slice types in the standard library, making the library itself simpler and smaller. All of these changes are potentially source-breaking and ABI-breaking, because they would remove types that could be used in Swift 3 code. However, there are mitigations: generic typealiases could provide source compatibility to Swift 3 clients, and the ABI-breaking aspect is only relevant if conditional conformances and the standard library changes they imply aren't part of Swift 4.
Aside from the standard library, conditional conformances have an impact on the Swift runtime, which will require specific support to handle dynamic casting. If that runtime support is not available once ABI stability has been declared, then introducing conditional conformances in a later language version either means the feature cannot be deployed backward or that it would provide only more limited, static behavior when used on older runtimes. Hence, there is significant motivation for doing this feature as part of Swift 4. Even if we waited to introduce conditional conformances, we would want to include a hook in the runtime to allow them to be implemented later, to avoid future backward-compatibility issues.

<https://github.com/DougGregor/swift-evolution/tree/conditional-conformances#alternatives-considered>Alternatives considered

The most common request related to conditional conformances is to allow a (constrained) protocol extension to declare conformance to a protocol. For example:

extension Collection: Equatable where Iterator.Element: Equatable {
  static func ==(lhs: Self, rhs: Self) -> Bool {
    // ...
  }
}
This protocol extension will make any Collection of Equatable elements Equatable, which is a powerful feature that could be put to good use. Introducing conditional conformances for protocol extensions would exacerbate the problem of overlapping conformances, because it would be unreasonable to say that the existence of the above protocol extension means that no type that conforms to Collection could declare its own conformance to Equatable, conditional or otherwise.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

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


(Douglas Gregor) #19

I’m sure we can find a reasonable solution to this that doesn’t incur a significant runtime penalty, e.g., by teaching the runtime conformance specialization machinery to handle a “redirecting” specialization that maps from the requirements of the older (more specialized) version to the requirements of the newer (less specialized) version.

  - Doug

···

On Sep 28, 2016, at 11:40 AM, Goffredo Marocchi <panajev@gmail.com> wrote:

Sent from my iPhone

On 28 Sep 2016, at 17:51, Douglas Gregor via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Sep 27, 2016, at 5:06 PM, Jordan Rose <jordan_rose@apple.com <mailto:jordan_rose@apple.com>> wrote:

Great job thinking this all through (as usual), and I’ll be very happy to have Optional and Array become Equatable. Here’s some of my thoughts on the library evolution aspect of this:

- Removing a conditional conformance isn’t allowed, obviously.
- Adding a conditional conformance is just like adding an unconditional conformance—it needs availability info.

Right. The main wrinkle I see here is that, when you add a conditional conformance, you will effectively end up with overlapping conformances when running an old application against a new library. Do you want me to capture these cases in the proposal in a section on “Resilience” or “Library Evolution”, like I’ve tried to capture the effect on ABI Stability? (I think that makes sense)

- It would be nice™ if making a conditional conformance more general was allowed. Since the plan doesn't allow overlapping conformances, I think this is actually implementable: just don’t put the constraints in the symbol name. I don’t know how to represent the backwards-deploying aspects of this right now, so it probably makes sense to forbid it today, but I think it would be nice if the implementation left the door open.

Yeah. It’s a different set of witness tables that one would need to gather to use the conditional conformance in the newer version of the library vs. in an older version of a library. That’s okay if we leave the witness-table-gathering to the runtime, but not so great if we statically provide the witness tables.

Would this be a case in which the win by having this feature and letting the runtime gather the witness tables offset the losses from doing his operations at runtime? I would like to think that in cases like this there is at least the option to opt for more flexibility.


(Douglas Gregor) #20

Great job thinking this all through (as usual), and I’ll be very happy to have Optional and Array become Equatable. Here’s some of my thoughts on the library evolution aspect of this:

- Removing a conditional conformance isn’t allowed, obviously.
- Adding a conditional conformance is just like adding an unconditional conformance—it needs availability info.

Right. The main wrinkle I see here is that, when you add a conditional conformance, you will effectively end up with overlapping conformances when running an old application against a new library. Do you want me to capture these cases in the proposal in a section on “Resilience” or “Library Evolution”, like I’ve tried to capture the effect on ABI Stability? (I think that makes sense)

Sure, yes please. (I think the main point is that the "conditional" doesn't make a difference here.)

Done in the updated form of this proposal.

- It would be nice™ if making a conditional conformance more general was allowed. Since the plan doesn't allow overlapping conformances, I think this is actually implementable: just don’t put the constraints in the symbol name. I don’t know how to represent the backwards-deploying aspects of this right now, so it probably makes sense to forbid it today, but I think it would be nice if the implementation left the door open.

Yeah. It’s a different set of witness tables that one would need to gather to use the conditional conformance in the newer version of the library vs. in an older version of a library. That’s okay if we leave the witness-table-gathering to the runtime, but not so great if we statically provide the witness tables.

This confuses me. Why aren't we just using the minimal (unconditional) conformance representation, and then pulling the associated type witness tables out dynamically? Is that significantly more expensive? (Am I just missing something?)

Dynamically looking up witness tables isn’t cheap. Still, we’ll find the right tradeoff here.

  - Doug

···

On Sep 28, 2016, at 1:23 PM, Jordan Rose <jordan_rose@apple.com> wrote:

On Sep 28, 2016, at 9:51, Douglas Gregor <dgregor@apple.com <mailto:dgregor@apple.com>> wrote:

On Sep 27, 2016, at 5:06 PM, Jordan Rose <jordan_rose@apple.com <mailto:jordan_rose@apple.com>> wrote: