An Implementation Model for Rational Protocol Conformance Behavior

[mattrips]

@dabrahams

I find that mostly unsurprising given the (always re-surprising!) fact that X<T> can only conform to P “in one way.” ... Also, all of these semantics seem consistent with what @Jens pointed out about the original proposals: we were warned.

Ok. This is awful, wonderful, ironic, annoying and hopeful. Awful: my mental model of the system is broken. Wonderful: my eyes have been opened, now, thanks to patient feedback from you and several others. Ironic: my mental model was learned from experimenting with Sequence, Collection, et al. Annoying: it is remarkable how much isn't written down. Hopeful: mental models can be repaired.

After very carefully re-reading SE-0143 and, especially, the parts pointed to by @Jens, I can say that @Douglas_Gregor certainly used some very precise language ("When satisfying a protocol requirement, Swift chooses the most specific member that can be used given the constraints of the conformance") to explain a very specific example ((X1<X2>() as P).f()). Originally, I'd understood, "given the constraints of the conformance," to refer to the constraints imposed at the point of use of the type. I also understood that (X1<X2>() as Q).f() (note the Q rather than P) would yield the specialized implementation of f(), as defined on Q. As I'll explain in a moment, there exists good precedent for that (mis-)interpretation.

BTW, hats off to the compiler engineers. After digging into the guts of the implementation, I am amazed by the level of complexity required to model the semantics, by the precision with which they do so, and by the enormous amounts of care and attention that must go into making all the parts work together correctly. I have a great deal of respect for them and what they do.

"In One Way"

So, about the in-one-way rule: exactly how is it defined? It sounds simple enough, but, in practice, it appears more nuanced. In the context of my example, I see at least three different ways that it could be applied:

Sequentially conforming to `P` and then to `Q`.

X<T> conforms to P, as follows:

1. P requires that a conforming type have a var id: Int { get }.
2. X<T> is unconditionally conformed to P.
3. X<T> itself does not implement P's id requirement, and so it needs to rely upon a default implementation of id.
4. In the context of X<T> conforming to P, the only default implementation available is P.id, and so, through that implementation, X<T> satisfies the requirement.

X<T> conditionally conforms to Q, as follows:

1. Q: P.
2. Q has no requirements of its own other than that the conforming type must conform to P.
3. The conformance to P already is satisfied, and so X<T> conforms to Q.
4. Since the Q.id implementation is not used by X<T> to conform to Q, it merely "shadows" P.id.

OR

Holistically conforming to both `P` and `Q` in the most specialized way possible.

X<T> conforms to both P and Q, as follows:

1. The conformance to P is unconditional.
2. The conformance to Q is conditional.
3. The only requirement is the P.id requirement.
4. X<T> itself does not implement P's id requirement, and so it needs to rely upon a default implementation of id.
5. Both P and Q have default implementations of id.
6. We would prefer the Q.id implementation, as the more specialized implementation of id.
7. But Q.id is available only when the condition for the Q conformance is satisfied, so Q.id is not always available to satisfy the id requirement.
8. Since X<T> can conform to P only in one way, the sometimes not available Q.id implementation cannot be used to satisfy the requirement.
9. The P.id default implementation is available at all times, and can satisfy the requirement, so it is used by X<T> to conform to P.
10. Since Q has no requirements of its own other than conformance to P, X<T> conforms to Q by virtue of its having satisfied the requirements of P in the manner specified, here. In other words, for purposes of conforming to Q, X<T> does not independently redetermine if there is a better way to conform to P under the state that exists when the condition to the conditional conformance is satisfied.

OR

Independently conforming to each of `P` and `Q`.

As described, above, X<T> satisfies the requirements of P via the default implementation provided by P.id. Then, independently, the best possible conformance for X<T> to Q is determined, with the conformance to P effectively being re-evaluated on the basis of the condition to the Q conformance assumed to be true. On that basis, Q.id would be selected as the implementation that satisfies the id requirement for purposes of Q.

I'm not sure there are on-point discussions or examples in SE-0143 that clearly specifies the intent. And, AFAICT, the formal documentation of protocol conformance does not address this aspect of the matter.

It seems that, what I characterize as the "holistic" conformance method, is closest to what the compiler actually does and what those well-versed in the system understand it to be doing.

If the possibility of revising conformance behavior is put on the table, I'd suggest consideration of whether the "independent" conformance method (A) is better aligned with what intuition would provide and (B) might help to facilitate providing more specialized conformances at the ultimate point of use.

The Collection Protocol Irony

The irony is that (unless I am mistaken) the "expected" behavior of P, Q and X<T> in my example in the post, above, is the behavior that is actually provided today by Swift via the canonical example of Collection, BidirectionalCollection and custom collection types.

I first learned about conditional conformance and the power of a protocol hierarchy by progressively conforming types to Sequence, Collection/MutableCollection, BidirectionalCollection, et al. I observed and internalized their behavior.

Of particular relevance, I saw and appreciated that, as a type was progressively, conditionally conformed through the steps of the hierarchy, certain methods gained functionality and/or improved in efficiency. Using our standby example of Collection's requirement of distance(from:to:), it goes from a default implementation of one-way on Collection to bidirectional on BidirectionalCollection. That enhanced capability is available both on concrete instances and in appropriately-constrained generic contexts.

Take for example:

A walk through a custom type conformed to `Collection`, and its protocol conformance behavior.

// Create a type.
public struct Things<T> {
  private var _elements: [T]
  init(_ elements: T...) { _elements = elements }
}

// Extend it to conform to MutableCollection with just a few keystrokes.
extension Things: MutableCollection {
  public var startIndex: Int { 0 }
  public var endIndex: Int  { 3 }
  public func index(after i: Int) -> Int { _elements.index(after: i) }
  public subscript(position: Int) -> T {
    get { _elements[position] }
    set { _elements[position] = newValue }
  }
}

// Use Collection's algorithms, like its distance(from:to:) requierment.
let fourStrings = Things("A", "B", "C", "D")
let d1 = fourStrings.distance(from: 0, to: 3) // 3

// The default implementation of distance(from:to:) declared by Collection is restricted to forwards-only traversal.
let d2 = fourStrings.distance(from: 3, to: 0) // TRAP: Can't go backwards

// Extend it to conform to BidirectionalCollection.
extension Things: BidirectionalCollection where T: StringProtocol {
  public func index(before i: Int) -> Int { _elements.index(before: i) }
}

// Now, distance(from:to:) works backwards.  BidirectionalCollection declares a better default implementation in one of its extensions.
//let d2 = fourStrings.distance(from: 3, to: 0) // -3

// We can use it in a generic context.
// And we still get that cool bidirectional implementation of distance(from:to:).
func distanceFromEndToStart<T: BidirectionalCollection>(from t: T) -> Int {
  t.distance(from: t.endIndex, to: t.startIndex)
}
let d3 = distanceFromEndToStart(from: fourStrings) // -3

// But, wait. The methods distance(from:to) is a requirement of 
// Collection, and the conformance of Things to BidirectionalCollection 
// is conditional, and since Things<T> can conform in "only 
// one way" to Collection's requirement of distance(from:to), 
// that one way should be the unconditional Collection.distance(from:to:)
// implementation.  But, Collection and BidirectionalCollection 
// aren't playing by that rule.

My example, in the post, above, mirrors this sort of usage of the Collection hierarchy:
X<T> = a generic type ready to be turned into a collection
P = Collection
Q = BidirectionalCollection
id = direction(from:to)

I posit that, what people intended with conditional conformance is the behavior exhibited by direction(from:to). In a generic context constrained to BidirectionalCollection, when one calls direction(from:to), they get the more-specialized BidirectionalCollection implementation. By contrast in my example in the previous post, in a generic context constrained to Q, when one calls id, they get the less-specialized P implementation.

Miscellaneous

some specific responses that may not be of general interest

@dabrahams

AFAICT this code is almost the same as my earlier example.

Plagiarism.

@dabrahams

My id2 (which corresponds to callID in your example) would be on an extension of Q rather than of P . So your example effectively points out that the P requirement id is satisfied the same way for the X<T>:P witness table as for the X<T>:Q witness table.

Precisely. I posit that, by not specializing the PWT for X<T>:Q, the system may be missing an opportunity. In my (totally incomplete and ill-informed) look at the implementation details, it seems that Q.id could be noted and used in the X<T>:Q PWT without any impact on the runtime and with little impact on binary size and compile times. I must be wrong, but until someone shows me why, I'll keep asking about it.

At the end of the day, it doesn't get you all the way to being able to have a P.id2 default implementation that can dynamically dispatch to P.id or Q.id depending upon the underlying concrete type, but it gets you pretty far down that road.

@dabrahams

It's also nearly the same as your earlier example except in that example your P requirement a() (which corresponds to id ) is being accessed through a different P requirement b() , rather than a non-requirement ( callId / id2 ).

I simplified it (taking your suggestion), and then moved it into a generic function to highlight that the context is constrained to Q.