Need Help Understanding Protocols and Generics

Using Swift
1

My question is at the end of this program:

//-------------------------------------------------------------------------
// Simple construct of two protocols P and Q:
//-------------------------------------------------------------------------

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" }
}


//-------------------------------------------------------------------------
// Concrete types X Y Z, each conforming to P and Q, but in different ways:
//-------------------------------------------------------------------------

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 {}


//-------------------------------------------------------------------------
// Instances x: X, y: Y and z: Z. Their .id and .id2 are printed, first in
// the same context as their declaration, then in generic context <T: Q>.
//-------------------------------------------------------------------------

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)
print(z.id, z.id2)            // Q Q   (3)

printGenericConstrainedToQ(x) // Q Q   (4)
printGenericConstrainedToQ(y) // P P   (5)
printGenericConstrainedToQ(z) // Q Q   (6)

//------------------------------------------------------------------------
// Question: Are all of these six printed results as intended?
// - If so, can anyone help me wrap my head around (2) and (5)?
// - If not, what should they be?
//------------------------------------------------------------------------

(This program is based on an example by @dabrahams which is based on an example by @mattrips in this thread).

3 Likes
2

The member id2, written in an extension of P, is statically dispatched because it is not a protocol requirement. Therefore, within its body, the use of id refers to the property that witnesses the id requirement of P for the type it is accessed on.

At the point where X and Z conform to P, they also conform to Q with the same constraints. Therefore both implementations of id are visible as candidates to witness the id requirement of P for them.

Since extension Q is more specialized than extension P, the compiler chooses the implementation from extension Q as the witness for P.id on both X and Z. So id2 on an X or Z will print "Q".

However the case of Y is different. At the point where Y conforms to P, it does not necessarily also conform to Q. Therefore only one candidate is available to witness the id requirement of P for Y, namely the one in extension P. That is why id2 on a Y instance always prints "P".

This fully accounts for the right-hand column of your example.

The left-hand column in the first 3 examples always prints "Q" because each of the instances have both candidate implementations visible, and the one in extension Q is more specialized so it is chosen. This does not use protocol witnesses nor dynamic dispatch, because the types are concrete.

The left-hand column in the last 3 examples is a bit different. The only thing known about a within the generic function is that it conforms to Q. In the body of that function, id refers to the member that witnesses the protocol requirement P.id, because protocol requirements must be dynamically dispatched. And as we saw above, the witnesses for X and Z print "Q", but the witness for Y prints "P".

7 Likes
3

With P.id means id used for P conformance, I think:

  • X, Y, and Z each have only have one P.id regardless of generic parameter, because they're generic,
  • X and Z uses id in Q extension for P.id since it conforms to Q wherever it conforms to P,
  • Y uses id in P extension for P.id since it may not conform to Q where it conforms to P,
  • id2 always uses P.id, because it's a P extension and not configuration point (both protocol requirement and extension),

With that (1,3,4,5,6) both part, and (2) id2 part would make sense, since they all use P.id.

The extra is (2) id. It simply uses id in Q extension, which is not part of P conformance, but is shadowing the P.id. Rather (1,2,3) id part would simply use id in Q extension, which is the same as P.id for (1,3), so it's kinda hard to tell.

4 Likes
4

Thanks @Nevin and @Lantua for you explanations.

I can follow and understand what you write, but I can't seem to fully internalize it. To me, when I read this:

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 {}

I can't seem to stop my brain from having this "obvious" thought:

Well, Int is Equatable, so X<Int>, Y<Int> and Z<Int> will all conform to Q, and since none of them implement any requirements on their own, they will all behave the same way for this example.

But this is false (for the reasons you explained above).

1 Like
6

I think it's much closer to idea that constraint can affect chosen implementation:

protocol P { var id: String { get } }
extension P { var id: String { "Normal P" } }
extension P where Self: Equatable { var id: String { "Equatable P" } }

extension Int: P { } // Equatable P
struct S: P { } // Normal P

only now that there are two protocols, interacting in a less obvious way. Though it's reasonable to be surprised by the different between X and Y even with that notion.

7

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

9

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.

10

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?

11

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.

12

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

13

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.

14

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

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
16

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.

17

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.

18

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

19

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
20

…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
21

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

1 Like
22

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