Need Help Understanding Protocols and Generics

@Nevin, great answer. Please allow me to pose a couple of questions to explore the meaning of what you've written.

If id2 also was a protocol requirement of P, then, within its body, to what would the use of id refer?

Focussing on the last sentence, what would you call the sort of dispatch that it uses to access the default implementation of the protocol requirement?

Please elaborate on why a.id refers "to the member that witnesses the protocol requirement P.id"? You say that is is "because protocol requirements must be dynamically dispatched." But, I don't see how the latter results in the former.

[UPDATE: Ah, yes. The id requirement is declared on P. The requirement is inherited by Q. But, for witness table/dispatch purposes, the requirement remains designated as a requirement of P. Is that correct?

But, then, that takes me to your last sentence:

And as we saw above, the witnesses for X and Z print "Q", but the witness for Y prints "P".

I'm not sure what you mean. That sentence seems to be incorrect. The left-hand column for the first three examples printed "Q" in all cases, and did not print "P" as the witness for Y. How do you explain the "P" for the left-hand side of example 5?
]

Thank you again for your time and insight.

What bothers me is that even if you add

extension Q {
  var id2: String { id }
}

(2 right) remains the same (I don't think it should). Q.id2 is used, but id in that context is still P witness, not Q. And I couldn't figure out the proper explanation. Since in this case (2 left) and (2 right) should have about the same amount of context.

Indeed, it is bothersome. I'd call it a bug, but I'm halfway expecting that someone will have an explanation.

How does one keep all of this straight when writing a program that uses protocols and generics together?

Sorry for the serial posts, but something interesting popped up. If the id protocol requirement is restated on Q using the @_nonoverride attribute, like so:

protocol Q: P {
  @_nonoverride var id: String { get }
}

... then (5) produces "Q P" rather than "P P".

See, here, regarding the meaning of the @_nonoverride attribute.

I'll try to answer this below. But first, let me just restate your question within the program, updated with your modification:

protocol P {
  var id: String { get }
}
extension P {
  var id: String { "P" }
  var id2: String { id }
}
protocol Q: P {}
extension Q {
  var id: String { "Q" }
  var id2: String { id } // <-- Added this line (the only change compared to prg in OP)
}
struct X<T> {}; extension X: P {}
                extension X: Q {}
struct Y<T> {}; extension Y: P {}
                extension Y: Q where T: Equatable {}
struct Z<T> {}; extension Z: P where T: Equatable {}
                extension Z: Q where T: Equatable {}
func printGenericConstrainedToQ<T: Q>(_ a: T) { print(a.id, a.id2) }
let (x, y, z) = (X<Int>(), Y<Int>(), Z<Int>())
print(x.id, x.id2)            // Q Q   (1)
print(y.id, y.id2)            // Q P   (2) <-- Why still Q P and not Q Q?
print(z.id, z.id2)            // Q Q   (3)
printGenericConstrainedToQ(x) // Q Q   (4)
printGenericConstrainedToQ(y) // P P   (5)
printGenericConstrainedToQ(z) // Q Q   (6)

AFAICS, the answer to why (2) hasn't changed to Q Q is just the same as before. I'll restate the answer as I understand it here:

Yes, all six will now use Q's id2 (since id2 is not a requirement), but this will not change the result, because Y<Int> still conforms to P and Q using different constraints, and id is still a requirement of P, so when Y<Int> conforms to P the compiler can't assume that it also conforms to Q, and the witness for id will (still) be P's id.

Note that if (in this modified version of the program) we make id not be a requirement of P, ie

protocol P {
  // var id: String { get }
}

then all six will print "Q Q".

The problem is that in both (2left) and (2right), the context has Q.id, P.id, P witness, and the fact that self conforms to P and Q. So why does y.id refers to Q.id, but self.id within y refers to P witness.id. It’d be fine if both prints P, or both print Q, but that’s not the case.

As is, there is something difference between the two, there must be, but both the conformance information, and implementation availability are the same, which is a problem. The only difference I can see now is the fact that I’m calling one inside a Self method, and another is outside, but that’s hardly a justification.

I could explain away why (2right) is P or why (2left) is Q, the problem now is that there’s nothing preventing me from applying (2right) explanation to (2left), and vice versa.

I can't. Sometimes think I fully understand it, especially with some help, like here, at least for a while, until I slip back into being confused again, and need to repeat some exercise like this, and so on ...

Now for example, I cannot easily answer @Lantua's follow up question, at least not without giving it a lot of time and effort, and I'm beginning to doubt my explanation above, or wonder if there might be some bug somewhere that confuses us, either way, it's complicated.

In my day to day code, which happens to be mostly library-like in-house code where performance matters (graphics, geometry, physics, ...), I've adopted the following rule to be able to reason about my code:

  • Never implement protocol requirements in protocol extensions.

So I only implement protocol requirements in conforming types (that would be X, Y and Z here). And the members I add in protocol extensions are never requirements.

The resulting subset of Swift's protocols and generics is enough for most of what I do, and the most reoccurring serious limitation I face is one which I think has nothing to do with limiting myself to my subset.

Namely this.

While it is possible to write specific implementations that are more efficient for some generic type parameters, these faster implementations will only be available to call sites that are in the same generic context. This is a problem if you're trying to write code that is both reusable and efficient ... Let me explain by example instead:

  • We have a protocol P with associated type A.
  • In an extension to P we have a (non-requirement) method bar that works for all A.
  • We've also implemented a faster bar where A: Q.
  • Now, we want to add methods baz, qux, grault etc, all using bar.
  • We are faced with the following AFAICS 3 options:
    1. Implement all of them once, for any A, meaning all of them will have to use the general (slow) bar. (dynamic cast is not an option, too slow, because methods are called with high frequency.)
    2. Implement all of them twice, once for the general case and once for the case where A: Q, and make sure that whatever future methods we write that happens to use one of these methods are also implemented for both cases ... This doesn't scale.
    3. Jump through some hoops where we effectively access the efficient implementations via some required static method available via concrete As, This can be done via some EfficientBarSupporting protocol with a requirement that conforming A-types implements. ... It's too complicated to explain clearly here, but it kind of works, and is much too complicated to feel nice.

Also the witness. The point is that within a P context, id refers to the protocol requirement P.id.

These are concrete instances, and they use static dispatch. The implementations in extensions on P and Q are both “visible” on a concrete instance, and they are treated as overloads. The one that comes from extension Q is “more specific”, so it is used.

This is not a generic context, so no dynamic dispatch occurs.

In a generic context, protocol requirements are dynamically dispatched through witness tables. That is how Swift generics work.

So a.id is looked up in the witness table for the conformance of T to Q. That table includes an entry for id, since it is a requirement of P and Q refines P.

From an implementation perspective, the witness table for Q has a reference to the witness table for P, and finds the requirement id there.

If instead the witness table for Q had its own separate entry for the id requirement, which can be achieved with the undocumented, unsupported, underscored attribute @_nonoverride:

protocol Q: P {
  @_nonoverride var id: String { get }
}

Then a type like Y would provide different implementations for its P.id and Q.id witnesses. This means that the left side of line (5) now prints "Q", because it uses the witness for Q.id.

However, the right side of line (5) still prints "P", because id2 comes from a P context and thus calls the witness for P.id.

Note however that if we include the @_nonoverride line in Q, and also reimplement id2 in an extension of Q, then, finally, the program will print "Q" in all 6 spots.

Even then, though, we don’t get the fully dynamic behavior we are used to from class inheritance. For example, in a context expecting a superclass, calling a member that is overridden by a subclass will dispatch to the subclass implementation.

Conversely, with our @_nonoverride shenanigans, in a context expecting a type conforming to P, accessing id will still use the witness for the P.id requirement, even if the type actually conforms to Q as well.

Right, the protocol P has a requirement id. The protocol Q inherits it without change (unless redeclared as @_nonoverride, in which case both requirements exist side-by-side and get used in different generic contexts).

In the first three examples, the left-hand column does not use protocol witnesses at all. It uses static overload resolution to choose the most specific match available.

It is the right side of the first three examples that uses the protocol witness for id, within the implementation for id2, as I explained previously.

2-right is dynamically dispatched from a generic context (the implementation of id2 in extension P), and thus uses the protocol witness for the conforming type.

2-left is statically dispatched from a concrete instance, and thus uses the most-specific overload available.

2 Likes

Later we added id2 to extension Q (around this point). That Q.id2 is being used (you can have extra print to confirm it). So now the most specific overloads in Q.id2 should still be Q.id since that's about the same information that the concrete type is having, but the compiler actually choose P witness.id.

In a generic context, protocol requirements are dispatched dynamically.

Period.

There is no sense of “choosing the best overload”, because it is not a matter of overload resolution. It is a call to a protocol requirement, and nothing else.

No, but yes. That's what I'm looking for. That the preference over overloads (Q.id, P.id, P witness.id) are different in different context. We can't just say that it's a dynamic dispatch, calling P witness.id IS THE DYNAMIC DISPATCH. We haven't gone that far as to say why it's choosing dynamic P witness.id over static Q.id or static P.id yet.

At best you're saying that, in generic/protocol context, it always prefer P witness.id over static Q.id, P.id, which is something I can palate (perhaps grumpily so).

If that’s how you want to understand it, sure.

The point is, in a generic context, default implementations for protocol requirements do not come into play. They cannot be accessed. They are simply not a possibility.

The only things that can be called in such a context are dynamically-dispatched protocol requirements, and statically-dispatched protocol extension methods.

The presence of a default implementation for a protocol requirement has no effect here. The requirement is still a requirement, so it is the only choice. It must be dynamically dispatched through the witness table.

Edit:
If the context were also constrained to a superclass, then members of that class would also be possible (and higher priority) even if they don’t serve as the protocol witness:

class C: P {}
class D: C { var id: String { "D" } }
class E: D, Q {
  override var id: String { "E" }
  var id2: String { id }
}
func testDQ<T: D & Q>(_ t: T) { print(t.id, t.id2) }

let e = E()
print(e.id, e.id2)            // E E
testDQ(e)                     // E P
printGenericConstrainedToQ(e) // P P
1 Like

…okay, now I’ve found something even more mind-bending. We can apparently get static dispatch in a generic context constrained to a composition of a class and protocol.

And it is different from what we would get on either the concrete class itself, or the base class in the constraint, or when generically constrained to the protocol, or in an existential of the protocol:

class C: P {}
class D: C, Q { var id: String { "D" } }
func testCQ<T: C & Q>(_ t: T) { print(t.id, t.id2) }

let d = D()
print(d.id, d.id2)            // D P   (7)
testCQ(d)                     // Q P   (8)
printGenericConstrainedToQ(d) // P P   (9)

Specifically, the left side of (8) prints "Q".

The only difference between testCQ and printGenericConstrainedToQ is the presence of “C &” in the generic constraint on testCQ.

Both are constrained to Q.

C itself is only constrained to P, which Q also inherits from P so that is no new information.

C does not provide any concrete implementations, so its witness for P.id is the default provided in extension P, which prints “P”.

The concrete implementation of D.id is unavailable inside testCQ, and indeed it is not called.

Instead we get the overload from extension Q, which I can only reconcile as being due to static overload resolution on the composition C & Q.

But I would have expected dynamic dispatch to the protocol requirement, meaning d’s witness for P.id, which prints “P”.

I think the fact that (8) does not print “P P” is a bug.

(Although, the fact that (9) does not print “D P” could also be considered a bug, in which case (8) should print the same.)

1 Like

This implicates bug SR-103. See also this thread.

1 Like

Right, I’m well aware and that’s why I knew how to construct the example. It’s what I was alluding to in my final (parenthetical) paragraph.

That behavior explains why (9) prints “P P”, which was my intention.

I had expected that (8) would do the same and also print “P P”.

I was surprised to find that (8) actually prints “Q P”.

Do you have an explanation for why (8) does not print “P P” as (9) does?

1 Like

Looking into that behavior doesn't require reconstructing the example in SR-103. Let's simplify into this self-containing example:

protocol P {
    var id: String { get }
}
extension P {
    var id: String { "P" }
    var id2: String { id }
}

protocol Q: P {}
extension Q {
    var id: String { "Q" }
}

class C: P {}
class D: C, Q {}
func testCQ<T: C & Q>(_ t: T) { print(t.id, t.id2) }
func testAnyObjectQ<T: AnyObject & Q>(_ t: T) { print(t.id, t.id2) }
func testD<T: D>(_ t: T) { print(t.id, t.id2) }

let d = D()
testCQ(d)         // Q P
testAnyObjectQ(d) // P P
testD(d)          // Q P

My understanding is as follows: we are now dealing with dynamic dispatch as it applies to classes. Since id is part of the API of C, dynamic dispatch behavior as implemented for classes is engaged when the constraint is C & Q. (By contrast, id is not part of the API of AnyObject, so dynamic dispatch behavior as implemented for classes is not engaged when the constraint is AnyObject & Q.)

It appears that, for these purposes (i.e., for dynamic dispatch as it applies to classes), Swift treats implementations in protocol extensions just like overriding implementations in subclasses (despite SR-103 not permitting the latter).

1 Like

@Nevin, thank you for your reply of earlier, today. Quite illuminating. Spelling out the extra details really helped me to understand how you are analyzing these examples.

1 Like

Well, if we're gonna have fun destructuring this, might as well decouple left side and right side:

Protocols & Conformance are the same:
protocol P { var id: String {get} }
protocol Q: P {}

extension P { var id: String { "P" } }
extension Q { var id: String { "Q" } }

struct X<T> {}
extension X: P {}
extension X: Q {}

struct Y<T> {}
extension Y: P {}
extension Y: Q where T: Equatable {}

struct Z<T> {}
extension Z: P where T: Equatable {}
extension Z: Q where T: Equatable {}

class C: P {}
class D: C, Q { var id: String { "D" } }

The left part is (pretty much) the same

let (x, y, z, d) = (X<Int>(), Y<Int>(), Z<Int>(), D())

print(x.id)            // Q (1L)
print(y.id)            // Q (2L)
print(z.id)            // Q (3L)
print((x as Q).id)     // Q (4L)
print((y as Q).id)     // P (5L)
print((z as Q).id)     // Q (6L)
print(d.id)            // D (7L)
print((d as C & Q).id) // Q (8L)
print((d as Q).id)     // P (9L)

Now separate the right part

extension P { var id2: String { "P2" } }

// Should actually point to (as P) rows, but there is none, and I’m just too lazy to make one.
print(x.id2)            // P2 (1R) -> (4L) Q
print(y.id2)            // P2 (2R) -> (5L) P
print(z.id2)            // P2 (3R) -> (6L) Q
print((x as Q).id2)     // P2 (4R) -> (4L) Q
print((y as Q).id2)     // P2 (5R) -> (5L) P
print((z as Q).id2)     // P2 (6R) -> (6L) Q
print(d.id2)            // P2 (7R) -> (9L) P
print((d as C & Q).id2) // P2 (8R) -> (9L) P
print((d as Q).id2)     // P2 (9R) -> (9L) P

So then we can focus on the left part, since that's where the interesting stuff lies (and the right part is redundant anyway).

1 Like

Continuing my quest to better comprehend the mechanics of protocol conformance behavior (in hope of documenting it), I'm wondering if someone could shed light on (1) the specifics of instantiation of protocol witness tables and (2) their subsequent use. To provide context, @Joe_Groff wrote, recently in another thread:

Swift does overload resolution to pick the most specialized implementation that applies at a use site . Once it picks one, it doesn't change that based on parameters to the use site. ... For protocol conformances, the use site is the point at which the conformance is declared, on the type or extension declaration.

In the context of the example upon which this thread is based, looking at Y's protocol conformances, we have the following use sites for protocols P and Q:

struct Y<T> {}
extension Y: P {}
extension Y: Q where T: Equatable {}

(Question A) Is that actually two protocol use sites? In other words, is the conformance to P a separate use site from the conditional conformance to Q?

(Question B) Is a single protocol witness table instantiated, or is it two tables, one for P and one for P with conditional Q?

(Question C) Approaching questions A and B from a different angle--the context provided by the Type Metadata document--are Protocol Metadata records generated as part of the declaration of a protocol or as part of the declaration of a type that uses the protocol? I think it is the former. If I'm correct, then, turning to the Generic Argument Vector part of that document, I understand that that metadata is created at the time that generic type Y is declared, with references to the applicable protocol witness tables. But, then, I wonder about extensions of Y that conform Y to protocols. Do those extensions result in the generation of a new set of Generic Argument Vector metadata that replaces the one created with the initial declaration of Y?

Then, we have the use sites for the generic type Y:

let y = Y<Int>()

(Question D) At this stage, it becomes knowable that, since Int conforms to Equatable, all instances of Y<Int> conform to Q. Does the compiler do anything with that knowledge in terms of protocol conformance? Is a Protocol Conformance Record generated that is specific to Y<Int>?

Then, we have the first use site for the instance y of type Y<Int>:

print(y.id, y.id2)

I'll hold questions about that usage pending a solidification of my understanding of the subject matter, above.

I cannot imagine that you would have the free time available to address these questions, but just in case you might: @Joe_Groff and @Nevin and @jrose.

Re this, there's a swift-inspect tool in the most recent source that should show the runtime behavior of things. I have been having trouble getting it to build unfortunately.

Another simple way to get some idea of what's happening is to run

nm whatever.o | xcrun swift-demangle

(whatever.o is the object file of your compiled swift code). It will give you list of the various compiled pieces. The protocol metadata shows up in the list, along with value witness tables, protocol metadata, etc. Obviously if there's dynamic linking happening you won't see everything but you can see exactly what gets compiled in a swift -c situation, which might help focus some questions.

There are a lot of small pieces that go into the object files to support protocols. I was working in the background on making sure I understood all of them but have not quite reached full understanding.

--Dan

2 Likes