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.