[swift-evolution] [Review] SE-0143: Conditional Conformances

[Douglas Gregor]

> On Sep 29, 2016, at 10:16 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> Obviously I'm a huge +1 for this feature, but I have some concerns and
> questions about the particulars.
> 
> on Wed Sep 28 2016, Joe Groff <swift-evolution at swift.org> wrote:
> 
>> 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:
>> 
>> ```swift
>> 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(_:)` 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.
> 
> Whether a dynamic evaluation is required at this point seems to depend
> on how you represent conformance.  Saying “Array conforms conditionally”
> treats Array as a type, but it might be simpler to treat Array as a
> family of concrete types.

This is already the case in the runtime; we specialize the metadata for generic types.

>  I always envisined it this way: at the moment
> a module using the concrete type Array<Foo> comes together with an
> extension (either in that module or in another) that makes Array<T>
> conform to Equatable depending on properties of T, that extension is
> evaluated and Array<Foo> is marked as conforming or not.

If the protocol, Array, and Foo all come from different modules, this process happens at runtime. Yes, the optimizer could specialize the conformance at compile time in many common cases, but you can’t see every possible specialization without whole-program analysis, so it doesn’t change the model.


>  Then asking
> about a type's conformance is always a simple thing.  But I suppose
> which approach wins is dependent on many factors, and the other way can
> be thought of as adding lazy evaluation to the basic model, so if this
> adds nothing to your thinking please excuse the static.

Without whole-program information, you need to have the runtime capability (or disallow the use of this feature in runtime queries). Static specialization can be considered an optimization to this model.

>> Note that, for an arbitrary type `T`, there are four potential answers to
>> the question of whether `SomeWrapper<T>` conforms to `Equatable`:
>> 
>> 1. No, it does not conform because `T` is neither `Equatable` nor
>> `HasIdentity`.
>> 2. Yes, it conforms via the first extension of `SomeWrapper` because
>> `T` conforms to `Equatable`.
>> 3. Yes, it conforms via the second extension of `SomeWrapper` because
>> `T` conforms to `HasIdentity`.
>> 4. Ambiguity, because `T` conforms to both `Equatable` and
>> `HasIdentity`.
> 
> Arguably in this case you could say yes it conforms and it doesn't
> matter which extension you use because there's only one sensible
> semantics for Equatable.

Sure, we know the semantics of these protocols: === should imply ==.

>  Other protocols are less obvious, though
> (c.f. Int's conformance to Monoid with +/0 vs */1).

Right.

>> 2. 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. 
> 
> I'm pretty sure we already have that.  Array<T> would have hashValue if
> T were hashable, and < if T were comparable, and never the twain shall
> meet.

The first sentence of (2) meant “to a *given* protocol”, not just “to any protocol." But, yes, you’re right that (e.g.) overloading across differently-constrained extensions and protocol extensions means dealing with divergent interfaces… and it’s been a problem for type checker and humans both.

> 
>> 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.
>> 
>> 3. 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:
>> 
>> ```swift
>> protocol P { }
>> 
>> struct S : P { }
>> extension S : P { } // error: S already conforms to P
>> ```
> 
> I think that's the real answer to “why don't we want to allow it?”
> 
> Also, these overlapping constraints are effectively equivalent to “or”
> constraints, which I think we know are trouble, from a type checking
> POV.

Right.

> 
> [By the way, what is the status of our enforcement of this rule across
> modules?  I do think that library interop will eventually oblige us to
> allow different overlapping conformances to appear in separate modules
> that don't also define the conforming type].

IIRC, we get runtime failures for overlapping conformances across modules.

>> ### 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:
>> 
>> ```swift
>> 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"
> 
> What difference does it make which one “wins?”  Even if P had
> requirements and we were fulfilling them in these extensions, my mental
> model has always been that they get thrown into a big soup and we let
> overload resolution sort it out (or declare ambiguity).  So I've never
> had any idea that “winning” was happening.

In Swift 3, it doesn’t actually matter who “wins”: it’s just an implementation detail whose only user-visible effect right now is on the near-miss diagnostics for @objc optional requirements. My obtuse way of saying this in the proposal was to point out that, with conditional conformances, now it *does* matter to the user model, because overload resolution would get different answers depending on which extension is asking the question.

>> 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:
>> 
>> ```swift
>> 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.
> 
> Doesn't this break, then?
> 
>   protocol Equatable { ... }
>   protocol Comparable : Equatable { ... }
>   protocol Hashable : Equatable { ... }
> 
>   extension Array : Comparable where T : Comparable {}
>   extension Array : Hashable where T : Hashable {}
> 
> I hope not, beause personally, I don't see how breaking the ability to
> do things like that could be acceptable.  The protocols such as
> Equatable et al. that form the components of “Regular” types are *going*
> to be inherited by many other protocols, so this isn't just going to
> happen in a nice localized context, either.

The above is ill-formed as written, because we can’t associate ‘Equatable’ with either conformance without excluding the other—and putting it in both places would create an overlapping conformance. So, the fix is to explicitly spell out the Equatable conformance:

	extension Array: Equatable where T: Equatable { } okay! this is the Equatable conformance for Array

Note that this conformance is less-specialized than both the “Array: Comparable” and “Array: Hashable” conformances, which is important: one cannot satisfy “Hashable” (or “Comparable”) without satisfying “Equatable”, so that Equatable conformance has to exist and has to be usable from the Hashable and Comparable conformances.

> 
>> 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. 
> 
> “Less specialized wins” is surprising at the very least!  I've only ever
> seen the opposite rule (e.g. in overload resolution).  What's the
> rationale for this approach?

You need the most-general implementation so that conformance can be used by other constrained extensions, the way the ‘Array: Equatable’ gets used by ‘Array: Hashable’ and ‘Array: Comparable’.

> 
>> Continuing the example from above:
>> 
>> ```swift
>> protocol S: R { }
>> 
>> struct X5<T> { }
>> 
>> extension X5: S where T: S { }
>> 
>> // This last extension "wins" the implied conformance to P, because
>> // the extension where "T: R" is less specialized than the one
>> // where "T: S".
>> extension X5: R 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:
>> 
>> 1. 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, 
> 
> Surely that can't be the right long-term design?

When all of the extensions are unconstrained, it still doesn’t matter to the user where the conformance goes. In truth, this rule extends to groups of extensions that have the *same* constraints—it doesn’t matter which one we pick.

> 
>> or
>> 
>> 2. 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.
> 
> I'm really concerned about the understandability of this model.  It
> doesn't seem rational or consistent with other choices in the
> language. Now maybe I'm missing something, but in that case I think you
> haven't given a clear/precise enough description of the rules.  But the
> next section looks like it might clear things up for me...
> 
> ...(I'm sorry to say it didn’t)

While the exposition can be improved somewhat, placement of implied conformances is fairly tricky and low-level. It will surface to the user in cases where the user writes something like your Comparable/Hashable example:

>   extension Array : Comparable where T : Comparable {}
>   extension Array : Hashable where T : Hashable {}


and the compiler needs to complain about the inability to place ‘Equatable’ in a way that directs the user to the correct answer without exposing them to the entire chain of reasoning we’re going through. The diagnostic would need some thought:

	error: ‘Array' requires an explicit conformance to ‘Equatable’ due to conflicting implied conformances (from ‘Comparable’ and ‘Hashable’)

We can easily produce a Fix-It to create the skeleton of the conformance:

	extension Array: Equatable {
	  // … 
	}

With some heroics involving, e.g., intersecting the requirements, we might be able to have the Fix-It put in a guess at the ‘where’ clause:

	extension Array: Equatable where T: Equatable {
	  // … 
	}

but that might not be necessary.

Now, I do think it’s important to note that neither of the Comparable or Hashable conformances we’ve shown actually has what Equatable needs—it doesn’t provide an ‘==‘ operator. The problems become clearer if we try to write that in both places:

	extension Array: Comparable where T: Comparable {
	  static func ==(lhs: Self, rhs: Self) -> Bool { … }
	}

	extension Array: Comparable where T: Comparable {
	  static func ==(lhs: Self, rhs: Self) -> Bool { … }
	}

Which ‘==‘ makes Array Equatable? The answer depends on the capabilities of ’T’.


>> ### 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:
>> 
>> 
>> ```swift
>> 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. 
> 
> AFAICT, this is the first time that an extension's association to a
> conformance has ever been visible in the user model, and I am not sure
> that we want to expose it.  I'm *not* saying we *don't* want to; I'm
> saying it isn't obvious why we should.

I guess it’s technically been visible in cross-module cases—you can see where the implied protocols ended up in the generated interface of a compiled module—but nobody noticed or cared, so it’s not really part of the model. It might be that we don’t need to make this concept visible at all—we just need to tell users when we require them to write an explicit conformance. We could even omit the “why” from the diagnostic.

> 
>> 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`. 
> 
> I don't see how that's any different from the `f()` in the first
> extension, which won't necessarily always be available because `T` may
> not conform to `Q`.

If you’re looking from the point of view of the first extension, T does conform to P. That’s the “placement” part: when you say that a conformance is placed on a particular extension, it’s requirements are satisfied based on the constraints of that extension.

> 
>> 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. 
> 
> Let me be absolutely clear that I'm *not* questioning this scheme on
> those grounds.  I think it makes sense for static and dynamic (or
> generic) behaviors of the same spelling to differ sometimes, and it's
> even a useful design tool (c.f. someCollection.lazy).  However, the fact
> that it arises in some situations and is even sometimes the best design
> choice doesn't mean that's the way *this* feature should act in *this*
> situation.  I can't tell whether you're suggesting:
> 
> a) type safety demands this behavior
> b) it's the only behavior that's efficiently implementable
> c) it's actually the best behavior for the common use cases, or
> d) something else

It’s weakened forms of (a)-(c):

aa) It’s guaranteed to provide type safety, without the possibility for run-time ambiguities or other failures
bb) It’s efficiently implementable and fits well into the existing model. I know of partial solutions that allow some late resolution here that are efficiently implementable and can maintain a lack of run-time failures, but they require nontrivial engineering effort and I don’t know how to generalize them
cc) I suspect that the vast majority of use cases don’t need this kind of late resolution


>> 2. Eliminating repetition: the `lazy` wrappers described in the
>> [motivation](#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.
> 
> I think the description “eliminating repetition” does a disservice to
> the actual impact of this feature.  It will result in a massive decrease
> in API surface area, which simplifies the implementation of the library,
> yes, but also makes it far more accessible to users.

Okay, fair point.

> 
>> 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. 
> 
> It would also mean carrying forward all that implementation and API
> complexity for the forseeable future.

Yup.

> 
>> 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.
>> 
>> ## Effect on Resilience
>> 
>> One of the primary goals of Swift 4 is resilience, which allows
>> libraries to evolve without breaking binary compatibility with the
>> applications that use them. While the specific details of the impact
>> of conditional conformances on resilience will be captured in a
>> more-complete proposal on resilience, possible rules are summarized
>> here:
>> 
>> * A conditional conformance cannot be removed in the new version of a
>> library, because existing clients might depend on it.
> 
> I think that applies to all conformances.

Yes, it does.

> 
>> * A conditional conformance can be added in a new version of a
>> library, roughly following the rules described in the [library
>> evolution
>> document](https://github.com/apple/swift/blob/master/docs/LibraryEvolution.rst#new-conformances). The
>> conformance itself will need to be annotated with the version in which
>> it was introduced.
> 
> Presumably this is an ABI-preserving but potentially source-breaking
> change, because of the implied conformance ambiguity issues you
> mentioned earlier... and because of changing overload resolution, etc.?

Yeah, the issue here is that the conditional conformance would overlap existing concrete conformances, so you would need to remove those concrete conformances… except when using an old version of the library.

>> * A conditional conformance can be *generalized* in a new version of
>> the library, i.e., it can be effectively replaced by a (possibly
>> conditional) conformance in a new version of the library that is less
>> specialized than the conditional conformance in the older version of
>> the library. For example.
>> 
>>  ```swift
>>  public struct X<T> { }
>> 
>>  // Conformance in version 1.0
>>  public extension X: Sequence where T: Collection { ... }
>> 
>>  // Can be replaced by this less-specialized conformance in version 1.1
>>  public extension X: Sequence where T: Sequence { ... }
>>  ```
>> 
>>  Such conformances would likely need some kind of annotation.
> 
> Ditto?

Yup.

> 
>> ## 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:
>> 
>> ```swift
>> 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.
> 
> ...which is part of why I think we need better rules about overlap than
> the ones proposed here.  I anticipate a repetition of the pattern we
> have today, where Array provides == and != but can't conform to
> Equatable, just on a different level.  That has always felt wrong.  Now
> we'll do the same thing with Collection, so *at least* you don't have to
> write the == operator when you write the conditional conformance.

Yes, there will be repetition. To be concrete, one would end up with this:

extension RangeReplaceableCollection where Iterator.Element: Equatable {
  static func ==(lhs: Self, rhs: Self) -> Bool {
    // implement == efficiently...
  }
}

but each type that forms to Collection will still have to state its conformance to Equatable, even though it will often be empty, e.g.,

	extension Array: Equatable where Element: Equatable { }

We are still in a better place than we were in Swift 3, where there was *no* way to make Array conform to Equatable, but in these cases it’ll still feel boilerplate-y.

	- Doug