Need Help Understanding Protocols and Generics

Using Swift
23

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
24

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

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
26

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.

27

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
28

A) Yes, each conformance is a separate use site, which can be important if they're in different modules.

B) There's one witness table template for every protocol/type combination, i.e. one for Y: P and one for Y: Q. When coming up with an actual witness table, there is an instantiation step for the given concrete type, so e.g. Y<Int>: Q is different from Y<Float>: Q. I believe this instantiation step can do arbitrary work, at least currently. In theory Y<Int>: P and Y<Float>: P could also be different, but there's no reason to waste memory on that, so I think the "template" is just used as is. I could be misremembering that, though. (It's definitely true for non-generic types.)

C) Protocol metadata records are part of the declaration of the protocol (unlike in Objective-C). Generic argument vectors are part of each instantiated type (Y<Int>). Protocol conformance records are generated for every type/protocol pair, whether in an extension or on the type itself (Y: Q, not Y<Int>: Q).

D) Y<Int>: Q is not generated by the compiler, though it may be able to do so as an optimization. It's not possible to do so in all cases, since the generic argument may be passed in as an argument and the client may not even know that Y is in use:

public func test<T>(_ type: T) where T: Equatable {
  Y<T>().doQThing()
}
2 Likes
29

Thanks, Jordan. Much appreciated. I'm going to internalize those concepts, and then surely will return with more questions. :wink:

And, Dan, great stuff. I wasn't aware of those capabilities, and will try to take advantage of them as part of the learning process.

1 Like
30

I will begin by acknowledging that this post is enormous. It is asking a lot to expect that anyone will be able and willing to provide answers. Thank you for reading this, and thank you to anyone that might rise to the challenge of educating. Hopefully, this thread will become a resource for others.

Continuing from where I left off, above, I'll repeat the examples, along with the information gleaned from the prior responses from @jrose, plus summaries of documentation, notes and investigations that others might find useful (behind hide/reveal triangles).

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" }
}
When a protocol is declared, an instance of Protocol Metadata is formed.

When a protocol is declared, an instance of Protocol Metadata is formed.

The Protocol Metadata includes the common metadata layout fields (a pointer to a Value Witness Table, and a "kind" field containing the value 12), followed by:

  • a word containing "layout flags"
  • a word containing the number of protocols
  • if applicable, superclass type metadata
  • the "protocol vector"

If the "superclass constraint indicator" is set in the layout flags, the superclass type metadata is between the number of protocols and the protocol vector.

The layout flags include the number of witness tables, the "special protocol kind", the superclass constraint indicator, and the "class constraint". The only special protocol kind is Error, which is indicated by 1; otherwise, the value is 0. The class constraint indicates whether the protocol is constrained to use with classes, with 1 meaning no and 0 meaning yes.

The number of protocols is 1 if only a single protocol is represented. The number is 0 if Any or AnyObject is represented. If a protocol composition (e.g., P & Q & R) is represented, the number is equal to the number of protocols in the composition.

The protocol vector "is an inline array of pointers to descriptions of each protocol in the composition. Each pointer references either a Swift Protocol Descriptor or an Objective-C protocol." For Any or AnyObject, there is no Protocol Descriptor.

When Protocol Metadata is formed, a Protocol Descriptor is created.

When Protocol Metadata is formed, a Protocol Descriptor is created (unless the protocol merely is Any, AnyObject or a composition of other protocols). The Protocol Descriptor is pointed to by the Protocol Metadata.

The Protocol Descriptor describes the requirements of a protocol.

The Protocol Descriptor layout includes:

  • context descriptor (what does this mean?)
  • kind-specific flags
  • a pointer to the name of the protocol
  • the number of generic requirements within the protocol's requirement signature
  • the number of protocol requirements
  • a string containing the associated type names, whitespace separated
  • a table of the generic requirements that form the requirement signature
  • a table of the protocol requirements

There is no reference to the non-required functions that might be declared in a protocol extension. Since calls to those functions are statically dispatched at compile time and since the Protocol Descriptor is used at run time, there is no need to reference those functions in the Protocol Descriptor. Is that correct?

To Investigate:
What does the term "generic requirements" mean, here?
What is the requirement signature of a protocol?
How are the generic requirements and the protocol requirements described?

So, at this point, we have Protocol Metadata with a Protocol Descriptor for each of P and Q. The Protocol Descriptor for a protocol provides, among other things, descriptions of each of the protocol's requirements.

(Question E) I do not see any metadata that would capture the fact that Q inherits from P. How is that relationship tracked?

(Question F) I do not see any metadata to track non-required implementations provided in a protocol extension, such as P.id2. I assume that is because those implementations are dispatched statically at compile time, so there is no need to reference them in metadata intended for use by the runtime. Is that correct?

struct Y<T> {}
extension Y: P {}
extension Y: Q where T: Equatable {}
When a type is declared to conform to a protocol, a Protocol Conformance Record is created.

When a type is declared to conform to a protocol, a Protocol Conformance Record is created. The record states that a given type conforms to a particular protocol.

The record contains:

  • a pointer to the Protocol Descriptor for the protocol
  • a pointer to the conforming type
  • a pointer to the Protocol Witness Table for the type/protocol combination
  • a flag indicating the representation type of the Protocol Witness Table
    • 0 = a standard witness table
    • 1 = an accessor function to a unconditional witness table
    • 2 = an accessor function to a conditional witness table
    • 3 is reserved for future use.
  • a 32-bit value reserved for future use

"Protocol conformance records are emitted into their own section, which is scanned by the Swift runtime when needed (e.g., in response to a swift_conformsToProtocol() query)."

With respect to generic types, the Protocol Conformance Record is generated for the type/protocol pair. In other words, for Y<T: Equatable> and protocol P, the record is created with respect to Y: P, not with respect to Y<Int>: P.

It has been noted that, as an optimization, it may be possible for the compiler to generate a record with respect to the conformance of a protocol to a specific Y<T> where T has been specified or constrained. I believe the same concept was discussed, here, with it further being noted that the many combinations of types and protocols could result in unacceptable increases in binary size.

When a Protocol Conformance Record is created, a Protocol Witness Table is created.

When a type is declared to conform to a protocol, a Protocol Witness Table is created with respect to the combination of the protocol and the type.

I cannot find any substantive documentation of Protocol Witness Tables. The following notes are based on secondary sources and my own, very limited investigation and supposition.

Conceptually, the Protocol Witness Table is understood to be a table of pointers, one for each requirement of the protocol, pointing to the implementation of the requirement. The implementation itself may have been declared (1) in an extension of the protocol (as a default implementation), or (2) in the declaration of the type or an extension thereof, or (3) in an extension of another protocol to which the type conforms, whether or not the implementation is a requirement of the other protocol.

Taking note of the apparent fact that a type may conform to one protocol's requirement by using an implementation of the same name from another protocol, it appears that the process of determining protocol conformances is holistic, taking into account all possible conformances from the visible scope. Is that correct?

When a protocol is imported into, and then extended within, a scope outside the scope of its original declaration, a Protocol Witness Table is created. Do the conformances selected for that table take into account all of the possible conformances available from both the current scope and the original scope in which the protocol was declared?

If a type conforms to more than one protocol, a distinct Protocol Witness Table is created for each type/protocol combination. Is this true where the conformance is implicit [e.g., protocol Q inherits from protocol P, and type X explicitly unconditionally conforms to Q, so type X also implicitly conforms to P]?.

It appears that a Protocol Witness Table may be represented as a literal table or via an accessor. If represented as an accessor, it appears there are two distinct types of accessors, those that handle unconditional conformances and those that handle conditional conformances.

If the conformance is conditional, it appears that the conditionality of the conformance is analyzed via the accessor. Presumably, the accessor is a function that takes arguments necessary for determining whether the condition to the conformance is satisfied. Presumably, if the condition is not satisfied, the accessor reports the same back to the caller. Presumably, this all happens at runtime. Is that even close to correct? Which functions in the runtime deal with this?

Investigation:
Analyze ProtocolConformance.cpp.

So, at this point, we now have two Protocol Witness Tables (PWTs), one for Y: P and one for Y: Q.

(Question G) It seems that the first PWT, for Y: P, will be unconditional in nature, and will have just one requirement, P.id. Will the entry for that requirement point at both the default implementation provided in P and the default implementation provided in Q? (If not, please see my notes hidden under the PWT reveal, which explain why I so surmise.)

(Question H) The second PWT, for Y: Q, will be conditional in nature. If I understand this correctly, this table will not have any entries, because Q has no requirements of its own. The id requirement belongs to P. Is that correct? It doesn't feel right...

(Question I) I find virtually no documentation for PWTs. Aside from the source code and pull requests, does any documentation exist? Are there specific source files that would be useful to review?

(Question J) For a conditional conformance, is seems that the PWT is provided via an accessor, which I take to be a function. Is that correct?

(Question K) Does the runtime use the PWT accessor to determine whether a given instance of a generic type satisfies a conditional conformance?

(Question L) What does the signature of the PWT accessor look like? How does it behave, and how is it used?

(Question M) I assume the "template" to which @jrose referred, upthread, is used solely by the compiler, and so is not persisted in the metadata. Is that correct?

let y = Y<Int>()
When an instance of a generic type is created, a Generic Argument Vector is created.

When an instance of a generic type is created, a Generic Argument Vector is created. The Generic Argument Vector is part of the concrete type's metadata. It contains information about the type's generic parameters (e.g., for X<T, U>, the T and the U).

The documentation of the Generic Argument Vector seems to use the terms "parameter" and "argument" loosely and interchangeably.

"Metadata records for instances of generic types contain information about their generic arguments. For each parameter of the type, a reference to the metadata record for the type argument is stored. After all of the type argument metadata references, for each type parameter, if there are protocol requirements on that type parameter, a reference to the witness table for each protocol it is required to conform to is stored in declaration order."

"For example, given a generic type with the parameters <T, U, V> , its generic parameter record will consist of references to the metadata records for T , U , and V in succession, as if laid out in a C struct. If we add protocol requirements to the parameters, for example, <T: Runcible, U: Fungible & Ansible, V> , then the type's generic parameter vector contains witness tables for those protocols, as if laid out:"

struct GenericParameterVector {
  TypeMetadata *T, *U, *V;
  RuncibleWitnessTable *T_Runcible;
  FungibleWitnessTable *U_Fungible;
  AnsibleWitnessTable *U_Ansible;
};

Investigate:
How does this information play into protocol conformance behavior at runtime?

In other words,

When an instance of generic type is created, the type's Nominal Type Descriptor includes relevant information.

When an instance of generic type is created, the type's Nominal Type Descriptor includes:

  • a pointer to the metadata pattern used to form instances of the type
  • the generic parameter descriptor

The generic parameter descriptor describes the layout of the "generic parameter vector" (? same as Generic Argument Vector ?), in four words, as follows:

  • the offset of the generic parameter vector within the metadata record
  • the number of type parameters, inclusive of associated types of type parameters
  • the number of type parameters, including only the primary formal type parameters
  • for each of the n type parameters, the number of witness table pointers stored for the type parameter in the "generic parameter vector"

*So, at this point, we know have a Generic Argument Vector that presumably will tell the runtime how to work with our instance of Y<Int>.

(Question N) The documentation loosely refers to a Generic Argument Vector and a Generic Parameter Vector. Are those one and the same?

(Question O) The documentation refers to a generic parameter descriptor (as part of the Nominal Type Descriptor). Is that descriptor describing the layout of the Generic Argument Vector?

(Question P) In what ways is the Generic Argument Vector used by the runtime?

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

print(y.id, y.id2)

Here, we finally put our PWTs to work. The dispatching will be determined dynamically, at run time.

(Question Q) To select a witness for y.id, are the PWTs for Y: P and Y: Q both accessed (and why or why not)? What does each PWT report back?

(Question R) How does the runtime determine that Q is more specialized than P?

(Question S) The call to y.id2 was dispatched statically, at compile time. The call goes to the implementation at P.id2. Inside that getter, a call is made to id. That call is to a protocol requirement, so it dispatched dynamically, correct?

(Question T) To select a witness for the call to id inside of P.id2, which PWTs are accessed, and why? What is reported back by the consulted PWT(s)?

Thanks again for your time and attention.

3 Likes
31

Wow, you weren't kidding. :-) I'll try to answer these as best I can, though in the interest of time I'm not going to try to verify all the little statements in the details disclosures. (I noticed a few are a little off but they seem mostly correct.)

(Question E) I do not see any metadata that would capture the fact that Q inherits from P . How is that relationship tracked?

E) Inheriting from another protocol is essentially the same as saying where Self: P from the runtime's perspective, so I believe that's part of the requirement signature in a protocol descriptor.

(Question F) I do not see any metadata to track non-required implementations provided in a protocol extension, such as P.id2 . I assume that is because those implementations are dispatched statically at compile time, so there is no need to reference them in metadata intended for use by the runtime. Is that correct?

F) It's correct that protocol descriptors do not include protocol extension members. In general, it's not possible to include all protocol extension members, because they might be defined in downstream modules. But it's certainly technically feasible to give protocol extension members in the same module some kind of special privileges; doing so for arbitrary protocol extension members would require some more thought on implementation. (See also a very old pitch of mine: [Pitch] Overridable Members in Extensions)

When a Protocol Conformance Record is created, a Protocol Witness Table is created.

This one's off enough that I do have to call it out for further answers to make sense. A conformance record is created for Y: Q, but each instantiation of Y is going to get its own witness table Y<Int>: Q, Y<String>: Q. That has to happen at run time for a generic type.

(Question G) It seems that the first PWT, for Y: P , will be unconditional in nature, and will have just one requirement, P.id . Will the entry for that requirement point at both the default implementation provided in P and the default implementation provided in Q ? (If not, please see my notes hidden under the PWT reveal, which explain why I so surmise.)

G) No, a witness table contains a single "witness" reference for each requirement. (With the caveat that an associated type requirement can have more than one datum associated with a witness: the type itself, plus references to witness tables for protocols that are specified as constraints.) All your PWT notes seem correct for me, so I'm not sure why you'd come to this conclusion; today, the compiler's going to pick exactly one witness based on an overload-resolution-like process and that's what's going to go into the conformance record, which is used to generate the witness table.

(Question H) The second PWT, for Y: Q , will be conditional in nature. If I understand this correctly, this table will not have any entries, because Q has no requirements of its own. The id requirement belongs to P. Is that correct? It doesn't feel right...

H) That's correct…nearly. In practice, because of what I said before about inheritance, the protocol witness table for Y<T>: Q will have one entry, which is a reference to the protocol witness table for Y<T>: P. (Arguably the compiler could optimize away "marker" protocols like this, where there's only one parent and no requirements, but that would make things more complicated, so there's no such optimization implemented today.)

(Question I) I find virtually no documentation for PWTs. Aside from the source code and pull requests, does any documentation exist? Are there specific source files that would be useful to review?

I) Good question. It doesn't help that we talk about "witness tables" and "conformances" at different parts of the compiler stack, and then in the runtime you have to think about both. Someone else might be able to talk about this better, but you can look at FragileWitnessTableBuilder and ProtocolConformanceDescriptorBuilder in GenProto.cpp to get the general idea. There's not much documentation because it's treated as an opaque structure by the runtime; any time you need something from a protocol witness table, you're usually just selecting one item at a known offset (say, the witness for P.id). The protocol conformance descriptor has a little more structure, but only enough to understand how to instantiate witness tables.

(Question J) For a conditional conformance, is seems that the PWT is provided via an accessor, which I take to be a function. Is that correct?

J) I'm not sure, and part of that is that I think you're conflating references to protocol witness tables in code with references in data. In data sections, you'd want to reference a witness table by its symbol, but if it needs instantiation (like for a generic type), you'd have to call a function instead. I'd expect the PWT-by-accessor to happen for any generic type, but maybe the compiler is smart enough to realize that Y: P doesn't actually depend on T. (I'm also not sure if the accessors are generated once-per-protocol, or once-per-use-site, since they'll be small calls to a runtime function anyway.)

(Question K) Does the runtime use the PWT accessor to determine whether a given instance of a generic type satisfies a conditional conformance?

K) It looks like the checking of requirements happens in the runtime function ProtocolConformanceDescriptor::getWitnessTable and a (complex) helper swift::_checkGenericRequirements. I'm not quite sure how this relates to your question, though, because when a witness table is referenced in code I'm not sure it goes through the accessor functions I talked about in (J).

(Question L) What does the signature of the PWT accessor look like? How does it behave, and how is it used?

L) I'm gonna pass on answering this one because I'm not sure which accessors you're talking about. :-(

(Question M) I assume the "template" to which @jrose referred, upthread, is used solely by the compiler, and so is not persisted in the metadata. Is that correct?

M) That's incorrect. It's called the witness table "pattern" in the runtime; I called it a template because it's used to fill out parts of an instantiated witness table that won't change. Some conformances seem to put everything in the instantiation function, though.

(Question N) The documentation loosely refers to a Generic Argument Vector and a Generic Parameter Vector. Are those one and the same?

N) Not sure but probably.

(Question O) The documentation refers to a generic parameter descriptor (as part of the Nominal Type Descriptor). Is that descriptor describing the layout of the Generic Argument Vector?

O) Yes.

(Question P) In what ways is the Generic Argument Vector used by the runtime?

P) As a whole unit, not much. But this is where generic arguments and any associated conformances are stored, and so if a method on a generic type wants to reference a generic argument, that's how it'll do it: by going to the type metadata and looking at the right offset.

(Question Q) To select a witness for y.id , are the PWTs for Y: P and Y: Q both accessed (and why or why not)? What does each PWT report back?

Q) The compiler chooses what to call for y.id using overload resolution; it finds a requirement on P, a method on an extension on P, and a method on an extension on Q. The last is the most specific, so it gets chosen. Nothing ever looks at the contents of any witness tables for this to happen.

(Question R) How does the runtime determine that Q is more specialized than P ?

R) N/A

(Question S) The call to y.id2 was dispatched statically, at compile time. The call goes to the implementation at P.id2 . Inside that getter, a call is made to id . That call is to a protocol requirement, so it dispatched dynamically, correct?

S) Correct. Inside P.id2, there are only two options: the requirement on P, and the extension method on P. I can't remember the specific rules that make the requirement better than the extension method; in particular, I can't remember if a constrained extension method on P will ever be chosen when calling from an identically-constrained extension method on P.

(Question T) To select a witness for the call to id inside of P.id2 , which PWTs are accessed, and why? What is reported back by the consulted PWT(s)?

T) Protocol extension methods are basically generic methods in disguise, so at run time, P.id2 has two additional hidden parameters: the concrete type it's being called on, and the conformance of that type to P (i.e. the witness table). This means it's the caller that chooses what witness table to pass when calling P.id2; the compiler sees that the concrete type is Y<Int> and the method in question is on an extension of P, so it's going to pass Y<Int>: P. At this point there's information about the generic arguments of Y, but no information about overloads of id; the one-size-fits-all implementation has already been chosen by the compiler back when we said Y: P.

I could use double-checking from someone else on all of these, but especially I-N and P.

5 Likes
32

First, again, THANK YOU. Your responses highlights a couple of critical points that I'd like to hone.

Does the compiler create and pass the PWT, or does the compiler write instructions that ultimately trigger the run time to create and pass the PWT for Y<Int>: P?

This last sentence of your reply was a wonderful tie-back to the beginning of my inquiry: exploring exactly what it means to for the use site to be the point at which a conformance is declared.

So, when we call id2 on Y<Int>, the caller knows that Y<Int> conforms to P and Q. Why does the caller choose to send the PWT for Y<Int>: P but not the PWT for Y<Int>: Q? I believe the answer is that the caller chooses the witness table for Y<Int>: P, because the implementation of id2 is declared on P. Correct?

If we add an extension member on Q: var id2: String { id }, should the caller resolve a call to id2 on Y<Int> as being a call to id2 on P or Q? And, so should the PWT that is passed to id2 be for Y<Int>: P or Y<Int>: Q?
[HINT: It calls id2 on Q but seems to pass a PWT for Y<Int>: P (or, at least, the behavior is that Q.id2 ends up calling P.id).]

[UPDATE: Regarding the last paragraph and the footnote, as discussed, in the thread, below, when the caller calls id2 on Y<Int>, it is dispatched statically as a call to Q.id2. The caller passes to Q.id2 a copy of the PWT for Y<Int>: Q where T: Equatable. However, the information inside that PWT ultimately points to a requirement/witness pairing of id/P.id, so the control flow ultimately goes to P.id. Why that happens, and whether it makes sense, is discussed, below. ]

1 Like
33

This is great. (I should have used all caps, now I feel bad.)

I'm writing down what I think I just learned about this, not asserting the truth that I understand below.

Just reiterating a couple of things:

  1. Protocol inheritance is equivalent to a where clause Self : Superprotocol but does not add a Self restriction to the protocol. Is this strictly correct or just morally correct? (Sometimes when things mean the same thing they are different in code, obviously.)

  2. Protocol witness tables are a runtime structure, The are instantiated from a protocol witness table pattern and the runtime data when a specific concrete type is needed.

  3. protocol witness tables are made up of witnesses. The offsets/indexes of the witnesses are known at compile time so the compiler can just make an indirect call through the witness offset in the runtime protocol witness table. Choosing the specific witness goes through something like overload resolution. Does this mean that conformances with the same name might have different witnesses? I was envisioning overload resolution working more like in a vtable where different overloads have the same offset and the specific table in place automatically chooses the right one. Maybe I am confused there.

  4. Does this mean that witnesses (the actual offsets into a witness table) are always compile-time known? It sounds like it but maybe I'm confused.

  5. Are protocol extension methods really (or morally) equivalent to generics? This is an interesting way to think about it but I want to make sure I have the right understanding before I start thinking.

Matt replied while I was writing this, so we might overlap. This was supposed to be 'Too short, did read' but maybe it's not quite.

34

Dan. Digging in with with your suggested tools has been helpful to fill in some of the technical details. I've gone with a pair of oxymoronic parameters to see a little bit deeper:

nm <filename> | xcrun swift-demangle -simplified -expand

2 Likes
35

Both are possible. The compiler definitely creates a fully-functional, fully-realized PWT in the case of non-generic types, and there are cases with generic types where the runtime runs arbitrary code (an instantiation function) in order to take a PWT initialized from a pattern and fill it in the rest of the way. The instantiation function gets the partially-initialized PWT; the concrete type that conforms to the protocol; and some "instantiation arguments" that are related to the conditions of a conditional conformance (I don't know much about this).

Yep, that's correct. There are several layers to this:

  • P.id2 expects a certain number of arguments; if more witness tables are passed as extra arguments, it won't actually know to look at them.

  • There's nothing in the definition or call to P.id2 that implies that Y<Int>: Q is interesting. What about Y<Int>: R? What about a conformance I add in my own separate module, if I then call id2 in that same module?

  • Even if Y<Int>: Q were passed, it wouldn't change anything, because PWTs only contain witnesses to protocol requirements (because that's what it means to be a protocol requirement: that the behavior can vary across implementing types).

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

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

print(Y<Int>().id2) // prints "P"

The compiler would pick Q.id2 (at point A) because that's "more specific" than P.id2 (because conforming to Q implies conforming to P as well). That means it gets the witness table for Y<Int>: Q. What does it do with that witness table? It uses the implied conformance to P to extract Y<Int>: P referenced by Y<Int>: Q, and uses that to call the id requirement. So the result is "P", not "Q".

(This answers a point I was unsure of before: does the requirement id on P take priority over the extension property on Q from within another extension property on Q? The answer is yes, because the requirement is assumed to resolve to the most specific thing possible in the concrete type. I believe that assumption predates constrained protocol extensions, though.)

2 Likes
36

Protocol inheritance is equivalent to a where clause Self : Superprotocol but does not add a Self restriction to the protocol. Is this strictly correct or just morally correct? (Sometimes when things mean the same thing they are different in code, obviously.)

The two are completely identical as far as the runtime is concerned, but the compiler may still treat them slightly differently (not sure). I'm not sure what you mean by "does not add a Self restriction to the protocol"; if you're referring to the restriction on protocol-valued types if one of the requirements references Self, that doesn't apply here since it's not a "requirement" that references Self. It's just a constraint on which protocols types can conform. (EDIT: oops)

Protocol witness tables are a runtime structure, The are instantiated from a protocol witness table pattern and the runtime data when a specific concrete type is needed.

Seems about right, with the caveat that they can be created ready-to-go by the compiler when possible.

protocol witness tables are made up of witnesses. The offsets/indexes of the witnesses are known at compile time so the compiler can just make an indirect call through the witness offset in the runtime protocol witness table. Choosing the specific witness goes through something like overload resolution. Does this mean that conformances with the same name might have different witnesses? I was envisioning overload resolution working more like in a vtable where different overloads have the same offset and the specific table in place automatically chooses the right one. Maybe I am confused there.

I think you're mixing up overloads and overrides. Protocol witness tables are indeed basically the same as vtables, but without inheritance. The requirements define the layout of the table, and a particular conformance defines the content.

Does this mean that witnesses (the actual offsets into a witness table) are always compile-time known? It sounds like it but maybe I'm confused.

Witnesses are the methods (and properties, and types) that satisfy requirements, but your question stands. I'm glossing over the capabilities for library evolution completed in Swift 5, but they basically work in two stages: the compiler generates a list of requirement/witness pairs, and the runtime assembles them into a normal, fast, offset-based witness table. Calling a requirement also has an extra bit of indirection (either looking up the offset, or just calling a trampoline function in the protocol's module; I forget which). This allows reordering requirements and even adding additional requirements (with defaults).

All of this only happens if the protocol part of a module compiled with -enable-library-evolution; otherwise, the compiler does hardcode the offsets for each requirement. I don't think it's going to majorly change our discussion.

Are protocol extension methods really (or morally) equivalent to generics? This is an interesting way to think about it but I want to make sure I have the right understanding before I start thinking.

:-) Yes, they are…except that they're also members, which means they can satisfy requirements, and they work with properties and subscripts too. So maybe it'd be better to say "they work the same as generics".

1 Like
37

THANK YOU! (all caps this time). I was in fact mixing up overloads and overrides there.

1 Like
38

Why?

Y<Int>().id2 calls Q::id2, 
Q::id2 which returns id that is NOT Q::id but P::id ... ?

Why P::id take priority over the override Q::id ?
I think Q::id should be more specific than P::id.

39

The protocol requirement Q.id is the same as the protocol requirement P.id. The former is an override of the latter, since it is not marked @_nonoverride.

Inside the body of the extension method Q.id2, the call self.id refers to the protocol requirement id, of which there is only one.

40

Thanks, Jordan.

I've been drilling into the assembly code underlying this modified version of the example. Everything you've written tracks right along with what I've found thus far. I'm at the stage of trying to delve into the runtime's construction of the Protocol Witness Table (PWT) for Y<Int>: Q where T: Equatable. With your answer in hand, I believe I can stop.

A Hole in the System's Logic

Focussing on the reason stated as to why P.id takes precedence of Q.id, "because the requirement is assumed to resolve to the most specific thing possible in the concrete type," I do not understand. To get at that from a different angle, I'll explain, as follows, using the context of the example code from your post.

The template for the PWT for Y: Q where T: Equatable is nailed down in the compiler at the time that the conformance is declared. At that point, if I understand the system correctly, that particular PWT template effectively includes a requirement/witness pair for the id requirement that points to the P.id witness. And, if I understand the logic being applied by the system, the compiler so chooses the P.id implementation over the Q.id implementation for the following reason: Since the conformance to Q is conditional, a particular instantiation of the generic type Y may not be a Q, so instead the compiler chooses the witness available on the more general P.

I believe there is a hole in the system's logic. The only circumstance in which the PWT for Y: Q where T: Equatable would actually be used is one in which the condition itself is satisfied. If a T of a Y is not Equatable, then that particular Y does not conform to Q, and so the PWT for the Q conformance would not be used (instead the PWT for the P conformance would be used). Since the condition to the Q conformance is satisfied in all possible cases in which the PWT for the Q conformance would apply, there is no need to choose the implementation provided by the more general P. The implementation provided by Q should be selected for the pairing in all those cases.

Am I missing something? Is a pairing from the PWT for Y: Q where T: Equatable ever used in a scenario in which the conditional conformance is not satisfied?

The @_nonoverride Workaround

As a related matter, I surmise that the behavior we are observing, here, partially explains why the Standard Library uses @_nonoverride. If we further modify our example to add an id requirement on Q: @_nonoverride var id: String { get }, the program prints "Q". The @_nonoverride attribute changes the protocol conformance behavior.

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

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

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

print(Y<Int>().id2) // prints "Q"

Am I surmising correctly that @_nonoverride is motivated, at least in part, to provide a magical mechanism by which the intuitively correct witness is chosen?

[Update: To avoid any overstatement, here, it is note that @_nonoverrride is used on only two protocols, for three requirements, each, with those protocols being BidirectionalCollection and RandomAccessCollection.]

1 Like
41

It looks like the general/unconditional requirement P.id override the conditional requirement Q.id by default.
If you want to use conditional requirement Q.id by default add @_nonoverride to tackle it.

42

@Nevin, regarding the concept of one protocol that refines another "overriding" the behavior of the latter, recently, I saw this statement (which might refer to the entire concept of overriding, or might merely refer to usage of the keyword override):

Thus far, my experimentation with the Q: P relationship, and having the Q protocol restate a requirement of the P protocol has not identified any change to witness-selection (a/k/a conformance) behavior. I've experimented both with and without an override keyword. My experiments have not been exhaustive. Have you seen a case in which merely repeating the existence of the requirement actually changes behavior?

No error is produced by usage of the override keyword with a protocol requirement, but I'm not sure it is legal. I believe it works only because it was made legal for private usage in the Standard Library to give the compiler a hint that the restatement of a requirement ought not generate all the boilerplate that goes with a requirement. The restatement of the requirement seems to be in support of giving the compiler hints for inference of associatedtypes. In turn, the usage of override seems to be an assertion that the requirement is merely a restatement, which helps keep binary size down.

In this same context, @_nonoverride was introduced. Its purpose is not so clear to me. Somewhat contradictorily, its effect seems to be to force an override. I believe it is spelled as it is, because override is used to tell the compiler, in this context: "I know this looks like a declaration of a requirement, but it is really just a restatement of a requirement that already exists, so ignore it (except for type inference)." While @_nonoverride is telling the compiler: "I know that this declaration of a requirement looks like it merely is a meaningless restatement, but let's pretend it is a brand new requirement, and wire this protocol's PWT on that basis." All of that is 100% supposition based on observations and a couple of pull request comments.

I will emphasize to those who might read this post, I believe override and @_nonoverride are private, undocumented, and should not be used in the wild, as they could be changed at any time, without warning.

Does anyone have any insight about override / @_nonoverride? @Douglas_Gregor, @jrose, @Slava_Pestov, @xwu, to name some possibilities.

[Update: For one the pull request comments to which I refer, see [Standard library] Audit protocol member overrides in protocols.]