How does Swift achieve extensions at the machine code level?

Question

I am messing around with LLVM right now, and the question came to my mind: How is Swift able to achieve extensions at the binary level?

In Swift, one can provide a basic extension that simply adds methods, but they can also provide an extension that conforms to another protocol. This class is then recognized as having said protocol as a parent and they can be casted from one another. How is this achieved?

I know about vtables and that they can define the location of function definitions and whatnot, but to my knowledge they are fixed length, correct? Is Swift able to achieve this functionality through its runtime library or are types mapped to lower level LLVM and it somehow manipulates the vtables whenever a new extension is defined?

Answer 1

The answers you're looking for are in the Swift ABI documentation, specifically in TypeMetadata.rst and TypeLayout.rst.

Swift uses vtables called witness tables to handle protocol conformances. Every type has one witness table per each protocol it conforms to, and a witness table has one entry per each function required by that protocol.

When we have a variable whose type is an existential (i.e. not statically known), Swift stores that variable in a runtime structure called an existential container. TypeLayout.rst describes the format of an existential container:

Opaque Existential Containers

If there is no class constraint on a protocol or protocol composition type, the existential container has to accommodate a value of arbitrary size and alignment. It does this using a fixed-size buffer, which is three pointers in size and pointer-aligned. This either directly contains the value, if its size and alignment are both less than or equal to the fixed-size buffer's, or contains a pointer to a side allocation owned by the existential container. The type of the contained value is identified by its type metadata record, and witness tables for all of the required protocol conformances are included. The layout is as if declared in the following C struct:

struct OpaqueExistentialContainer {
  void *fixedSizeBuffer[3];
  Metadata *type;
  WitnessTable *witnessTables[NUM_WITNESS_TABLES];
};

The witnessTables array contains one entry for each protocol that our existential is statically known to conform to -- so if our variable has type P1 & P2, the existential will contain exactly two witness table pointers (an existential container is specific to its protocol constraints, so any extra protocols the concrete type conforms to are ignored). As long as we have a witness table describing a type's conformance to a protocol, we can create an existential container, pass it around, and use the witness table to call protocol methods.

So how do we add a conformance to a type via an extension? Well, we don't actually have to modify any properties of the type itself; we just need to create a new witness table. In order to implement dynamic casting between existential types, we need some way to register the conformance with the Swift runtime; this is done by placing a protocol conformance record within a designated section of the binary where the runtime knows to look for it:

Protocol Conformance Records

A protocol conformance record states that a given type conforms to a particular protocol. 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). Each protocol conformance record contains:

• The protocol descriptor describing the protocol of the conformance, represented as an (possibly indirect) 32-bit offset relative to the field. The low bit indicates whether it is an indirect offset; the second lowest bit is reserved for future use.

• A reference to the conforming type, represented as a 32-bit offset relative to the field. The lower two bits indicate how the conforming type is represented:

  • 0: A direct reference to a nominal type descriptor.
  • 1: An indirect reference to a nominal type descriptor.
  • 2: Reserved for future use.
  • 3: A reference to a pointer to an Objective-C class object.

• The witness table field that provides access to the witness table describing the conformance itself, represented as a direct 32-bit relative offset. The lower two bits indicate how the witness table is represented:

  • 0: The witness table field is a reference to a witness table.
  • 1: The witness table field is a reference to a witness table accessor function for an unconditional conformance.
  • 2: The witness table field is a reference to a witness table accessor function for a conditional conformance.
  • 3: Reserved for future use.

• A 32-bit value reserved for future use.