Explicit ordering of multiple conditional conformances

Evolution Pitches
1

There has been some past discussion about overlapping conformances in the past, both in the conditional conformances proposal, and in some previous discussions (here, here and here, for example).

I understand some of the complexities around completely opening this up, including determining which conformance applies when they overlap and how to handle dynamic casts. Instead of allowing multiple conformances everywhere, what if there was a single point of conformance, but allowing multiple ways of conforming declared at that point with clear ordering? Something like the syntax described in Instance Chains could be used to provide the different ways of conforming while keeping the decision of which conformance applies unambiguous.

Possible syntax could be added else where and else clauses to the conditional conformance syntax. To borrow the example from the overlapping conformances section of the conditional conformance proposal, something like this:

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<Wrapped>) -> Bool {
    return lhs.wrapped == rhs.wrapped
  }
} else where Wrapped: HasIdentity {
  static func ==(lhs: SomeWrapper<Wrapped>, rhs: SomeWrapper<Wrapped>) -> Bool {
    return lhs.wrapped === rhs.wrapped
  }
}

There would still be a single point of conformance. You couldn't conform in multiple places, but you could provide multiple ways of conforming as long as you can reason about them up front. Would this balance complexity and utility? Is there anything here that would conflict with or prevent a more open approach to overlapping conformances in the future (such as the non-queryable conformances mentioned in the condition conformance proposal)?

4 Likes
2

Thanks for reminding about this problem and putting thoughts into a possible implementation strategy. I do not have much to add on a proposal itself. To have the ball rolling it is probably better to find scenarios where standard library can benefit from it. This was the moving factor behind conditional conformances as I understood. Does anyone know how standard library may benefit from the proposal?
Also, I do think will be interesting to explore alternative syntax, but it can be postponed to a stage after general acceptance.

ps Should it be in Pitches instead of Discussion?

3

Just to be explicit, are you meaning the following? When looking for a conformance for SomeWrapper: Equatable (I think you missed a :, BTW), we first see if Wrapped: Equatable is satisfied, and then, if not, if Wrapped: HasIdentity is satisfied. Meaning, if ConformsToBoth: Equatable & HasIdentity, then SomeWrapper< ConformsToBoth>: Equatable uses the first one.

This (let's call it "conformance chains" ala Instance Chains, maybe?) certainly seems like it may be restricted enough to avoid many of the problems with arbitrary overlapping conformances, e.g. for the ones listed in the conditional conformances proposal that you link to:

  1. 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).

This doesn't apply to conformance chains, since they're just ordered. If one wants to do something special for an intersection, write an explicit one (e.g. the first line becomes extension SomeWrapper: Equatable where Wrapped: Equatable & HasIdentity and the where Wrapped: Equatable moves to an else for the example you give) and put it first, but otherwise the behaviour is just picked up off the first one.

The compiler even knows enough about the where clauses to notice mistakes like putting an intersection last, and so could flag it with an error/warning.

  1. 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.

This one is the least resolved, I think. For instance, given

func doSomethingSometimes<T>(x: SomeWrapper<T>, y: SomeWrapper<T>) {
    if x == y {
        print("the same")
    }
}

how do we express the maximally-flexible bounds for this function? We want to be able to write bounds that mean "T: Equatable or T: HasIdentity". And, if we have that, then the == call is not able to be statically resolved: it can be either of SomeWrappers == functions.

Lastly, associated types could be a little tricky too. For an associated type, it seems like there's two basic options:

  1. all conformances have the same type
  2. each conformance has different type

Just thinking off the top of my head, it seems like we may want to explicitly support both of these. If we can guarantee that all values of an associated type AT are the same, then X<T>.AT (even if T is a parameter constrained with a disjunction like doSomethingSometimes) is interchangeable with the underlying type, and if it has different types, then it has to be treated as an opaque value, similar to T.AT for a completely generic T.

  1. 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.

I think conformance chains resolves this one nicely too: there's currently a loop that runs over the conditional requirements checking them for a dynamic cast, and this could move to a nested loop within an outer loop over the possible sets of generic requirements. There's likely a little bit of fiddle with making sure the requirements end up in the right place: once we've found a conformance branch that works, we need to get the dynamic record that contains its implementations, not one of the other ones, but having everything in exactly one place makes that easier (it allows using static buffers of size "number of conformance branches", plus integer indices, etc.)

3 Likes
4

This one is the least resolved, I think. For instance, given

func doSomethingSometimes<T>(x: SomeWrapper<T>, y: SomeWrapper<T>) {
    if x == y {
        print("the same")
    }
}

how do we express the maximally-flexible bounds for this function? We want to be able to write bounds that mean "T: Equatable or T: HasIdentity". And, if we have that, then the == call is not able to be statically resolved: it can be either of SomeWrappers == functions.

I'm not certain what the additional overhead to checking conformance of concrete types in where clauses would be, but that might be a way forward. Maybe something like the following:

func doSomethingSometimes<T>(x: SomeWrapper<T>, y: SomeWrapper<T>) where SomeWrapper<T>: Equatable

That sort of constraint would definitely be useful, but if it proved problematic to implement, multiple conformances would still be beneficial without it. I would expect you could still constrain generic parameters to write functions when the conformance is guaranteed, and that dynamic dispatch would still hold up.

func doSomethingSometimes<T: Equatable>(x: SomeWrapper<T>, y: SomeWrapper<T>)

would be valid, as would

func doSomethingSometimes<T: HasIdentity>(x: SomeWrapper<T>, y: SomeWrapper<T>)

, and in the latter case, if T also happened to be Equatable, the first branch in the conformance chain would be followed in calls to ==.

5

Probably does belong in pitches. Moved there.

6

Yeah, that definitely covers some cases (I'd guess most cases, in fact), but doesn't work when the type is an implementation detail/isn't meant to be part of the public API of code, e.g.

internal struct SomethingSpecial<T> { var x: T }

extension SomethingSpecial: P where T: Q {} else where T: R {}

public func doIt<T>(input: T) {
     let value = SomethingSpecial<T>(x: input);
     operation(value as P)
}

That doesn't quite match with Swift's behaviour elsewhere. Except for classes, choosing method overloads on concrete types is done with the static information available, and there's no dynamic dispatch. For instance:

struct X<T> {}

extension X {
    func foo() { print("no constraints") }
}
extension X where T == Int {
    func foo() { print("T == Int") }
}

// concrete
X<Int>().foo()
// generic
func callFooGenerically<T>(_: T.Type) { X<T>().foo() }
callFooGenerically(Int.self)
7

Yeah, that definitely covers some cases (I'd guess most cases, in fact), but doesn't work when the type is an implementation detail/isn't meant to be part of the public API of code, e.g.

I'm trying to understand the impact in your example. Maybe there's something I'm missing. You would not be able to non-optionally cast to P in that case since T is not constrained to Q or R. You could optionally cast, which would check the conditions at runtime and fail if T did not meet the requirements.

That doesn't quite match with Swift's behaviour elsewhere. Except for classes, choosing method overloads on concrete types is done with the static information available, and there's no dynamic dispatch.

This is true for functions that are only added in extensions, but protocol-required methods are dynamically dispatched such that they will not call default implementations from extensions to the protocol if the concrete type explicitly provides the requirement even if the only type info at the call site is the protocol conformance.

8

Sorry, it was meant to be similar to doSomethingSometimes where we wanted to express the optimal bounds in the signature, but in this case it isn't okay to mention SomethingSpecial in the signature. That is, it could've been, say, public func doIt<T>(input: T) where <what goes here?> { ... }.

I'm not quite sure exactly what you're referring to here, but I suspect it's what I was thinking of when I qualified with "on concrete types", as I wasn't considering protocol existentials as concrete types (along with generics).

Is it something like the following? (If not, could you provide a code example)

protocol P { func f() }
extension P { func f() { print("default") } }

struct X: P { func f() { print("not default") } }

let onlyP = X() as P
onlyP.f() // "not default"

If so, this form of dynamic dispatch is slightly different (and significantly cheaper) than what's required for dynamically dispatching on arbitrary requirements.

Each type that conforms to a protocol ends up with a "witness table", which is essentially the same as a class vtable: a record of function pointers to the implementations of the protocol requirements. All of those requirements are statically resolved, when the type (or extension declaring the conformance) is being compiled, and (approximately) written directly into the binary. If there's a default implementation for a requirement, and a type doesn't have its own implementation, this is noticed at compile time and the function pointer to the default requirement is put into the witness table. If the type does have its own implementation, the function pointer to that is put into the witness table instead.

Calling a function on a protocol existential like onlyP, or on a generic T: P, then just requires loading the function pointer from the table and calling it, rather than doing any "interesting" computation.

9

Sorry, it was meant to be similar to doSomethingSometimes where we wanted to express the optimal bounds in the signature, but in this case it isn't okay to mention SomethingSpecial in the signature. That is, it could've been, say, public func doIt(input: T) where <what goes here?> { ... }.

I would expect this to still be

public func doIt<T>(input: T) where SomethingSpecial<T>: P

We would be checking the conformance of something concrete, so inclusion in the signature becomes less critical (at least logically, not sure about implementation). Alternatively, if the concrete type is not exposed, then maybe the optional cast is the only way to handle it. Any concrete types in the clause have to be as accessible as the function.

Is it something like the following? (If not, could you provide a code example)

If so, this form of dynamic dispatch is slightly different (and significantly cheaper) than what's required for dynamically dispatching on arbitrary requirements.

Each type that conforms to a protocol ends up with a "witness table", which is essentially the same as a class vtable: a record of function pointers to the implementations of the protocol requirements. All of those requirements are statically resolved, when the type (or extension declaring the conformance) is being compiled, and (approximately) written directly into the binary. If there's a default implementation for a requirement, and a type doesn't have its own implementation, this is noticed at compile time and the function pointer to the default requirement is put into the witness table. If the type does have its own implementation, the function pointer to that is put into the witness table instead.

Yeah, that's what I was thinking of. So the witness table is for each type-conformance pair, and since conformance could only happen once, if the type conforms, then it has to use that table. If we add multiple conformances, then there are multiple ways to conform, each with a different witness table, and figuring out which to use would add overhead at the call site. Is my understanding correct?

10

I think in terms of implementation, allowing less-visible concrete types in constraints in signatures is unlikely to be much incremental work over allowing them at all.

However, my main problem with this is when someone is looking at such a signature, they have no idea what it means: without finding the non-public type in the source code (which may not be accessible), there's not really a way to work out how to satisfy that other than experimentation and hoping for good compiler errors. There's definitely ways tooling could help here, e.g. "expanding" such constraints into (in pseudo-Swift syntax) the actual generic constraints they mean, but that's suboptimal for various reasons (such as having to invent a syntax for this concept for documentation, and then we might as well invent one for real Swift too).

Yeah, you're pretty much correct. The only detail is the witness table is not computed at the call site; it is computed when the type is moved into a "protocol context", such as at the as P cast for onlyP, or, given func generic<T: P>(_: T), at the call generic(x). The cost of checking multiple requirements isn't so bad here, since it only happens once per-entry-into-generic-context (in theory, anyway).

However, note that the compiler doesn't go through the witness table for calls on concrete types, even if they are calls to protocol methods. This is the case in my example above, and, modulo the compiler getting smarter (certainly possible), means that every call in such a case would end up having to do the checking. This adds that direct cost, but would also inhibit other optimisations because all the branching makes the code much less obvious (e.g. for the original SomeWrapper example.

11

However, my main problem with this is when someone is looking at such a signature, they have no idea what it means: without finding the non-public type in the source code (which may not be accessible), there's not really a way to work out how to satisfy that other than experimentation and hoping for good compiler errors.

Agreed, it does make figuring out the requirements difficult. Without multiple conformances, it could just show the same requirements that are imposed on the conformance as applied to any generic parameters. With multiple conformances, definitely gets more complicated.

There's definitely ways tooling could help here, e.g. "expanding" such constraints into (in pseudo-Swift syntax) the actual generic constraints they mean, but that's suboptimal for various reasons (such as having to invent a syntax for this concept for documentation, and then we might as well invent one for real Swift too).

Would we want to add a disjunctive requirement syntax to the language as well? The person writing that function does not want to have to spell out all the branches of requirements, and the person consuming it does not need to spell it out either, just read it. I would think having disjunctive requirements supported outside the checks to a specifically ordered protocol conformance would add substantial amounts of complexity, no? Maybe the list of conformance conditions for the concrete type could be inlined into the documentation and diagnostics? Not a new syntax, just a list of the where clauses for that conformance?

Yeah, you're pretty much correct. The only detail is the witness table is not computed at the call site; it is computed when the type is moved into a "protocol context", such as at the as P cast for onlyP, or, given func generic<T: P>(_: T), at the call generic(x). The cost of checking multiple requirements isn't so bad here, since it only happens once per-entry-into-generic-context (in theory, anyway).

This is what I was already thinking if it wasn't done this way. Good to know.

However, note that the compiler doesn't go through the witness table for calls on concrete types, even if they are calls to protocol methods. This is the case in my example above, and, modulo the compiler getting smarter (certainly possible), means that every call in such a case would end up having to do the checking. This adds that direct cost, but would also inhibit other optimisations because all the branching makes the code much less obvious (e.g. for the original SomeWrapper example.

How does this work currently for constrained extensions without conformances? For example:

struct X<T> { }

extension X where T == String {
    func f() { print("T == String") }
}

extension X where T == Int {
    func f() { print("T == Int") }
}

extension X where T: Comparable {
    func f() { print("T: Comparable") }
}

X<String>().f() // T == String
X<Int>().f()    // T == Int
X<Float>().f()  // T: Comparable

Would this be substantially different from the following?

protocol P {
    func f()
}

struct X<T> { }

extension X: P where T == String {
    func f() { print("T == String") }
} else where T == Int {
    func f() { print("T == Int") }
} else where T: Comparable {
    func f() { print("T: Comparable") }
}

X<String>().f() // T == String
X<Int>().f()    // T == Int
X<Float>().f()  // T: Comparable
12

+1 for conformance chains! I have encountered a number of use cases for this feature and would love to have it!

I wouldn't expect to be able to mention a less-visible entity in the declaration of a more-visible entity. Assuming Q and R are public I would expect to be able to do:

public func doIt<T>(input: T) where T: Q

and

public func doIt<T>(input: T) where T: R
13

AFAIK, not allowing disjunction in requirements is an intentional design decision that is not going to change. My understanding is that it introduces substantial complexity in the implementation and would have an undesirable impact on type checking performance.

14

I have encountered a number of use cases for this feature and would love to have it!

Definitely! There are a lot of baseline use cases, but assuming we are able to support the concrete type conformance reference in where clauses as well, I've got my eye on being able to write some logic at the type level for constraints like ContainsType<F, G>: True. That along with conformance chains to support the multiple cases where ContainsType would conform to True might be able to help on the extensible effects front.

15

I have explored things like this myself and I think you're right that instance chains might help. I've actually become less enamored with that approach myself though. I have come to the conclusion that the tagless final approach will work better in Swift. My impression is that the Scala FP community has also been coming to that conclusion recently.

1 Like
16

@anandabits Would conformance chains help with composing tagless final interpreters as well? You could write extensions to Pair<A, B> to conform when either A or B conform. Then you could combine interpreters in any order with nested Pairs as long as the effect you need is in there somewhere.

17

I wouldn't expect to be able to mention a less-visible entity in the declaration of a more-visible entity.

That's what I was thinking as well. If SomethingSpecial was public, then my example would be valid. If it is not, then that would be an error. You could either promote it to public or constrain T such that it matches one of the conformances.

I agree with @huon though about the potential for that to be confusing in the valid case. Having to look at the conformance chain to see what conditions would satisfy it is a pain, especially since jumping to the type definition might not put you anywhere near that conformance chain. We would need a way to convey the requirements as they pertain to the signature without forcing the user to go searching for it.

I guess if this information was all available and separated from the original type that should not leak, maybe it is okay to require conformance from less visible types? Not allowing it would put fewer constraints on the documentation, though, since we wouldn't have to worry about internals leaking.

18

Sure, that could be useful.

I actually just ran into a use case for them in my code today and have a TODO comment to revisit if / when conformance chains are added. In this case, I have a protocol which can be conformed to by Array, Optional, etc (i.e. functors that store values of their type parameter) in a couple of different ways depending on what constraints Element, Wrapped, etc meet. I think this kind of use case is the bread and butter of conformance chains and will motivate the most people to be interested in them.

FWIW, this is actually asking for a second new feature in the generics system. Constraints are not currently allowed to reference types other than generic parameters and associated types even when they accept a generic parameter or associated type as a type argument. This would actually be a cool feature, but it is independent of instance chains.

See this code for the existing behavior:

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

func operation(_ p: P) {}

internal struct SomethingSpecial<T> { var x: T }
extension SomethingSpecial: P where T: Q {} /*else where T: R {}*/

// Type 'SomethingSpecial<T>' in conformance requirement does not refer to a generic parameter or associated type
func doIt<T>(input: T) where SomethingSpecial<T>: P {
    let value = SomethingSpecial<T>(x: input);
    operation(value as P)
}

If I understand correctly, what you are suggesting is that it doesn't really matter to users if the type is internal as long as all of the entities involved in constraining the visible type parameters (or associated types) are public, right? It seems like that would work ok in theory as long as generated header and documentation reified the implied constraints on the type parameters / ATs. It could be a very useful mechanism for abstracting over sets of constraints, even on publicly visible APIs.

1 Like
19

I agree that it'd be an unfortunate bit of additional complexity, but it may be necessary, for things like API evolution (i.e. ensuring people are able to express the external API they want, and not have it accidentally change as they refactor elsewhere[1]). Additionally, it is only adding complexity to the surface language; I believe the type checker itself would have to be able to model disjunctions, whether or not it is exposed directly to the programmer.

As you say, there's definitely ways we could turn this into documentation, by expanding any concrete type conformance requirements.

These are statically dispatched, meaning if T is lexically a generic type that is only known to be Comparable, that's the function that will always be called, even if it ends up being Int or String at runtime. E.g.

// ...

func foo<T: Comparable>(x: X<T>) {
    x.f()
}

foo(x: X<Int>()) // prints "T: Comparable"

In other words, the checking of requirements is done completely at compile time, and the runtime behaviour is just calling the chosen f directly, without having to decide between them.

20

FWIW, this is actually asking for a second new feature in the generics system. Constraints are not currently allowed to reference types other than generic parameters and associated types even when they accept a generic parameter or associated type as a type argument. This would actually be a cool feature, but it is independent of instance chains.

Yeah, definitely separate. It came out of the desire to be able to describe generic requirements that satisfy at least one of the conditional conformances in the chain of some concrete type. Definitely not required for conformance chains to be useful, but would be useful in some related contexts.

It seems like that would work ok in theory as long as generated header and documentation reified the implied constraints on the type parameters / ATs. It could be a very useful mechanism for abstracting over sets of constraints, even on publicly visible APIs.

This motivation what I had in mind, but reifying the implied constraints is where it gets rough. If it is over a conformance chain, then the constraints are disjunctive, and we don't really have a way to represent that (and previous discussion suggests we don't want to). Requiring the concrete type to satisfy the conformance would get you that abstraction, but maybe having the visibility requirement is what prevents the need for actual syntax around the disjunctive requirements. It could be documentation only.