docs/proposals/RemoteMirrors.rst - third_party/swift - Git at Google

 :orphan:

 Remote mirrors proposal
 =======================

 .. contents::

 This proposal describes a new implementation for nominal type metadata which
 will enable out-of-process heap inspection, intended for use by debugging tools
 for detecting leaks and cycles. This implementation will subsume the existing
 reflection support for Mirrors, enabling out-of-process usage while also
 reducing generated binary size.

 Radars tracking this work:

 - rdar://problem/15617914
 - rdar://problem/17019505
 - rdar://problem/20771693

 Goals and non-goals
 -------------------

 We wish to do post-mortem debugging of memory allocations in a Swift program.
 Debugging tools can already introspect the memory allocator to identify all
 live memory allocations in the program's heap.

 If the compiler were to emit the necessary metadata, the layout of most
 allocations can be ascertained, and in particular we can identify any
 references inside the heap object. This metadata can be used together with the
 core dump of a program to build a graph of objects.

 We have to be able to get all the necessary information without executing any
 code in the address space of the target, since it may be dead or otherwise in a
 funny state.

 In order to identify strong retain cycles, we need to know for each reference
 if it is strong, weak, or unowned.

 We wish to be able to opt out of metadata selectively. For secrecy, we might
 want to strip out field names, but keep metadata about which fields contain
 references. For release builds, we might want to strip out most of the field
 metadata altogether, except where explicitly required for code that relies on
 reflection for functionality.

 It would be better if the new functionality subsumes some of the existing
 metadata, instead of adding a whole new set of structures that the compiler and
 runtime must keep in sync.

 While this should have zero runtime overhead when not in use, it is OK if
 introspection requires some additional computation, especially if it can be
 front-loaded or memoized.

 It is OK if in rare cases the metadata is not precise -- for some allocations,
 we might not be able to figure out the runtime type of the contained value.
 Also we will not attempt to verify the "roots" of the object graph by walking
 the stack for pointers.

 Types of heap allocations
 -------------------------

 There are several types of heap allocations in Swift. We mostly concern
 ourselves with class instances for now, but in the fullness of time we would
 like to have accurate metadata for all heap allocations.

 Swift class instances
 ~~~~~~~~~~~~~~~~~~~~~

 These have an isa pointer that points to a class metadata record.

 Objective-C class instances
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~

 These also have an isa pointer, but the class metadata record has the
 Objective-C bit set.

 Boxes
 ~~~~~

 These are used for heap-allocating mutable values captured in closures, for
 indirect enum cases, and for Error existential values. They have an
 identifying isa pointer and reference count, but the isa pointer is shared by
 all boxes and thus does not describe the heap layout of the box.

 Contexts
 ~~~~~~~~

 The context for a thick function is laid out like a tuple consisting of the
 captured values. Currently, the only aspect of the layout that is needed by the
 runtime is knowledge of which captured values are heap pointers. A unique isa
 pointer is created for each possible layout here.

 Blocks
 ~~~~~~

 Blocks are similar to contexts but have a common header and package the
 function pointer and captured values in a single retainable heap object.

 Metatypes
 ~~~~~~~~~

 Runtime-allocated metatypes will appear in the malloc heap. They themselves
 cannot contain heap references though.


 Opaque value buffers
 ~~~~~~~~~~~~~~~~~~~~

 These come up when a value is too large to fit inside of an existential's
 inline storage, for example. They do not have a header, so we will not attempt
 to introspect them at first -- eventually, we could identify pointers to buffers
 where the existential is itself inside of a heap-allocated object.

 Existing metadata
 -----------------

 Swift already has a lot of reflective features and much of the groundwork for
 this exists in some form or another, but each one is lacking in at least one
 important respect.

 Generic type metadata
 ~~~~~~~~~~~~~~~~~~~~~

 The isa pointer of an object points to a metadata record. For instances of
 generic class types, the metadata is lazily instantiated from the generic
 metadata template together with the concrete types that are bound to generic
 parameters.

 Generic type metadata is instantiated for generic classes with live instances,
 and for metatype records of value types which are explicitly referenced from
 source.

 When the compiler needs to emit a generic type metadata record, it uses one of
 several strategies depending on the type being referenced. For concrete
 non-generic types, a direct call to a lazy accessor can be generated. For bound
 generic types T<P1, ..., Pn>, we recursively emit metadata references for the
 generic parameters Pn, then call the getter for the bound type T. For
 archetypes -- that is, generic type parameters which are free variables in the
 function body being compiled -- the metadata is passed in as a value, so the
 compiler simply emits a copy of that.

 Generic type metadata tells us the size of each heap allocation, but does not
 by itself tell us the types of the fields or what references they contain.

 Mirrors and NominalTypeDescriptors
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 The implementation of Mirrors uses runtime primitives which introspect the
 fields of an opaque value by looking at the NominalTypeDescriptor embedded in a
 type's metadata record.

 For structures and classes, the NominalTypeDescriptor contains a function
 pointer which returns an array of field types. The function pointer points to a
 "field type metadata function" emitted by the compiler. This function emits
 metadata record references for each field type and collects them in an array.
 Since the isa pointer of a class instance points at an instantiated type, the
 field types of such a NominalTypeDescriptor are also all concrete types.

 NominalTypeDescriptors record field names, in addition to types. Right now, all
 of this information is stored together, without any way of stripping it out.
 Also, NominalTypeDescriptors do not record whether a reference is strong, weak
 or unowned, but that would be simple to fix.

 A bigger problem is that we have to call a function to lazily generate the
 field type metadata. While a NominalTypeDescriptor for every instantiated class
 type appears in a crashed process, the field types do not, because only a call
 to the field type function will instantiate them.

 Objective-C instance variable metadata
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 The Objective-C runtime keeps track of the types of instance variables of
 classes, and there is enough information here to identify pointers in instances
 of concrete types, however there's no support for generic types. We could have
 generic type metadata instantiation also clone and fill in templates for
 Objective-C instance variables, but this would add a runtime cost to a feature
 that is primarily intended for debugging.

 DWARF metadata
 ~~~~~~~~~~~~~~

 IRGen emits some minimal amount of DWARF metadata for non-generic types, but
 makes no attempt to describe generic type layout to the debugger in this
 manner.

 However, DWARF has the advantage that it can be introspected without running
 code, and stripped out.

 New field type metadata format
 ------------------------------

 The main limitation of all of the above is either an inability to reason about
 generic types, or the requirement to run code in the target.

 Suppose T is a generic type, and S is some set of substitutions.

 The compiler conceptually implements an operation G(T, S) which returns a
 lazily-instantiated type descriptor for the given input parameters. However,
 its really performing a partial evaluation G(T)(S), with the "G(T)" part
 happening at compile time.

 Similarly, we can think of the field type access function as an operation F(T,
 S) which returns the types of the fields of T, with T again fixed at compile
 time.

 What we really want here is to build an "interpreter" -- or really, a parser for
 a simple serialized graph -- which understands how to parse uninstantiated
 generic metadata, keep track of substitutions, and calculate field offsets,
 sizes, and locations of references.

 This "interpreter" has to be able to find metadata for leaf types "from
 scratch", and calculate field sizes and offsets in the same way that generic
 type metadata instantiation calculates object sizes.

 The "interpreter" will take the form of a library for understanding field type
 metadata records and symbolic type references. This will be a C++ library and
 it needs to support the following use cases:

 #. In-process reflection, for backing the current Mirrors in the standard
    library
 #. Out-of-process reflection, for heap debugging tools
 #. Out-of-process reflection, for a new remote Mirrors feature in the library
    (optional)

 The API will be somewhat similar to Mirrors as they are in the stdlib today.

 The details are described below.

 Symbolic type references
 ~~~~~~~~~~~~~~~~~~~~~~~~

 Since we're operating on uninstantiated generic metadata, we need some way to
 describe compositions of types. Instead of using metadata record pointers,
 which are now insufficient, we use type references written in a mini-language.

 A symbolic type reference is a recursive structure describing an arbitrary
 Swift AST type in terms of nominal types, generic type parameters, and
 compositions of them, such as tuple types.

 For each AST type, we can distinguish between the minimum information we need
 to identify heap references therein, and the full type for reflection. The
 former could be retained while the latter could be stripped out in certain
 builds.

 We already have a very similar encoding -- parameter type mangling in SIL. It
 would be good to re-use this encoding, but for completeness, the full format of
 a type reference is described below:


 #. **A built-in type reference.** Special tokens can be used to refer to
    various built-in types that have runtime support.

 #. **A concrete type reference.** This can either be a mangled name of a type,
    or a GOT offset in the target.

 #. **A heap reference.** This consists of:

    - strong, weak or unowned
    - (optional) a reference to the class type itself

 #. **A bound generic type.** This consists of:

    - A concrete or built-in type reference
    - A nested symbolic type reference for each generic parameter

 #. **A tuple type.** This consists of:

    - A recursive sequence of symbolic type references.

 #. **A function type.** This consists of:

    - A representation,
    - (optional) input and output types

 #. **A protocol composition type.** This consists of:

    - A flag indicating if any of the protocols are class-constrained, which
      changes the representation
    - The number of non-@objc protocols in the composition
    - (optional) references to all protocols in the composition

 #. **A metatype.** This consists of:

    - (optional) a type reference to the instance type
    - there's no required information -- a metatype is always a single pointer to
      a heap object which itself does not reference any other heap objects.

 #. **An existential metatype.** This consists of:

    - The number of protocols in the composition.
    - (optional) type references to the protocol members.

 #. **A generic parameter.** Within the field types of a generic type,
    references to generic parameters can appear. Generic parameters are uniquely
    identifiable by an index here (and once we add nested generic types, a depth).

 You can visualize type references as if they are written in an S-expression
 format -- but in reality, it would be serialized in a compact binary form:

 ::

   (tuple_type
     (bound_generic_type
       (concrete_type "Array")
       (concrete_type "Int"))
     (bound_generic_type
       (builtin_type "Optional")
       (generic_type_parameter_type index=0)))

 We will provide a library of standalone routines for decoding, encoding and
 manipulating symbolic type references.

 Field type metadata records
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~

 We introduce a new type of metadata, stored in its own section so that it can
 be stripped out, called "field type metadata". For each nominal type, we emit a
 record containing the following:

 #. the name of the nominal type,
 #. the number of generic parameters,
 #. type references, written in the mini-language above, for each of its field
    types.
 #. field names, if enabled.

 Field type metadata is linked together so that it can be looked up by name,
 post-mortem by introspecting the core dump.

 We add a new field to the NominalTypeDescriptor to store a pointer to field
 type metadata for this nominal type. In "new-style" NominalTypeDescriptors that
 contain this field, the existing field type function will point to a common
 field type function, defined in the runtime, which instantiates the field type
 metadata. This allows for backward compatibility with old code, if desired.

 Field type metadata instantiation
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 First, given an isa pointer in the target, we need to build the symbolic type
 reference by walking backwards from instantiated to uninstantiated metadata,
 collecting generic parameters. This operation is lazy, caching the result for
 each isa pointer.

 ::

   enum SymbolicTypeReference {
     case Concrete(String)
     case BoundGeneric(String, [SymbolicTypeReference])
     case Tuple([SymbolicTypeReference])
     ...
   }

   func getSymbolicTypeOfObject(_ isa: void*) -> SymbolicTypeReference

 Next, we define an "instantiation" operation, which takes a completely
 substituted symbolic type reference, and returns a list of concrete field types
 and offsets.

 This operation will need to recursively visit field metadata records and keep
 track of generic parameter substitutions in order to correctly calculate all
 field offsets and sizes.

 The result of instantiating metadata for each given SymbolicTypeReference can
 be cached for faster lookup.

 This library has to be careful when following any pointers in the target, to
 properly handle partially-initialized objects, runtime bugs that led to memory
 corruption, or malicious code, without crashing or exploiting the debugging
 tools.

 ::

   enum FieldLayout {
     // the field contains a heap reference
     case Strong, Weak, Unowned
     // the field is an opaque binary blob, contents unknown.
     case Opaque
     // the field is a value type -- look inside recursively.
     case ValueType(indirect field: FieldDescriptor)
   }

   struct FieldDescriptor {
     let size: UInt
     let align: UInt
     let offset: UInt
     let layout: FieldLayout
   }

   func instantiateSymbolicType(_ ref: SymbolicTypeReference) -> [FieldTypeDescriptor]

 Field type metadata can have circular references -- for example, consider two
 classes which contain optionals of each other. In order to calculate field
 offsets correctly, we need to break cycles when we know something is a class
 type, and use a work-list algorithm instead of unbounded recursion to ensure
 forward progress.

 Enum type metadata
 ~~~~~~~~~~~~~~~~~~

 For enums, the field metadata record will also need to contain enough
 information about the spare bits and tag bits of the payload types that we can
 at runtime determine the case of an enum and project the payload, again without
 running code in the target.

 This will allow us to remove a pair of value witness functions generated purely
 for reflection, since they don't seem to be performance-critical.

 Closures
 ~~~~~~~~

 For closure contexts and blocks, it would be nice to emit metadata, too.

 Secrecy and release builds
 ~~~~~~~~~~~~~~~~~~~~~~~~~~

 There are several levels of metadata we can choose to emit here:

 #. For code that requires runtime for functional purposes, or for the standard
    library in debug builds, we can have a protocol conformance or compiler flag
    enable unconditional emission of all metadata.
 #. For system frameworks, we can omit field names and replace class names with
    unique identifiers, but keep the type metadata to help users debug memory leaks
    where framework classes are retaining instances of user classes.
 #. For release builds, we can strip out all the metadata except where
    explicitly required in 1).

 This probably requires putting the required metadata in a different section
 from the debug metadata. Perhaps field names should be separate from symbolic
 type references too.

 Performance
 ~~~~~~~~~~~

 Since the field type metadata instantiation only happens once per isa pointer,
 mirrors will not suffer a performance impact beyond the initial warm-up time.
 Once the field type descriptor has been constructed, reflective access of
 fields will proceed as before.

 There might also be a marginal performance gain from removing all the field
 type functions from the text segment, where they're currently interspersed with
 other code, and replacing them with read only data containing no relocations,
 which won't get paged in until needed.

 Resilience
 ~~~~~~~~~~

 We may choose to implement the new metadata facility after stabilizing the ABI.
 In this case, we should front-load some engineering work on
 NominalTypeDescriptors first, to make them more amenable to future extension.

 We need to carefully review the new metadata format and make sure it is
 flexible enough to support future language features, such as bound generic
 existentials, which may further complicate heap layout.

 As described above, it is possible to introduce this change in a
 backwards-compatible manner. We keep the field type function field in the
 NominalTypeDescriptor, but for "new-style" records, set it to point to a common
 function, defined in the runtime, which parses the new metadata and returns an
 array of field types that can be used by old clients.

 Testing
 ~~~~~~~

 By transitioning mirrors to use the new metadata, existing tests can be used to
 verify behavior. Additional tests can be developed to perform various
 allocations and assert properties of the resulting object graph, either from
 in- or out-of-process.

 If we go with the gradual approach where we have both field type functions and
 field type metadata, we can also instantiate the former and compare it against
 the result of invoking the latter, for all types in the system, as a means of
 validating the field type metadata.
	:orphan:

	Remote mirrors proposal
	=======================

	.. contents::

	This proposal describes a new implementation for nominal type metadata which
	will enable out-of-process heap inspection, intended for use by debugging tools
	for detecting leaks and cycles. This implementation will subsume the existing
	reflection support for Mirrors, enabling out-of-process usage while also
	reducing generated binary size.

	Radars tracking this work:

	- rdar://problem/15617914
	- rdar://problem/17019505
	- rdar://problem/20771693

	Goals and non-goals
	-------------------

	We wish to do post-mortem debugging of memory allocations in a Swift program.
	Debugging tools can already introspect the memory allocator to identify all
	live memory allocations in the program's heap.

	If the compiler were to emit the necessary metadata, the layout of most
	allocations can be ascertained, and in particular we can identify any
	references inside the heap object. This metadata can be used together with the
	core dump of a program to build a graph of objects.

	We have to be able to get all the necessary information without executing any
	code in the address space of the target, since it may be dead or otherwise in a
	funny state.

	In order to identify strong retain cycles, we need to know for each reference
	if it is strong, weak, or unowned.

	We wish to be able to opt out of metadata selectively. For secrecy, we might
	want to strip out field names, but keep metadata about which fields contain
	references. For release builds, we might want to strip out most of the field
	metadata altogether, except where explicitly required for code that relies on
	reflection for functionality.

	It would be better if the new functionality subsumes some of the existing
	metadata, instead of adding a whole new set of structures that the compiler and
	runtime must keep in sync.

	While this should have zero runtime overhead when not in use, it is OK if
	introspection requires some additional computation, especially if it can be
	front-loaded or memoized.

	It is OK if in rare cases the metadata is not precise -- for some allocations,
	we might not be able to figure out the runtime type of the contained value.
	Also we will not attempt to verify the "roots" of the object graph by walking
	the stack for pointers.

	Types of heap allocations
	-------------------------

	There are several types of heap allocations in Swift. We mostly concern
	ourselves with class instances for now, but in the fullness of time we would
	like to have accurate metadata for all heap allocations.

	Swift class instances
	~~~~~~~~~~~~~~~~~~~~~

	These have an isa pointer that points to a class metadata record.

	Objective-C class instances
	~~~~~~~~~~~~~~~~~~~~~~~~~~~

	These also have an isa pointer, but the class metadata record has the
	Objective-C bit set.

	Boxes
	~~~~~

	These are used for heap-allocating mutable values captured in closures, for
	indirect enum cases, and for Error existential values. They have an
	identifying isa pointer and reference count, but the isa pointer is shared by
	all boxes and thus does not describe the heap layout of the box.

	Contexts
	~~~~~~~~

	The context for a thick function is laid out like a tuple consisting of the
	captured values. Currently, the only aspect of the layout that is needed by the
	runtime is knowledge of which captured values are heap pointers. A unique isa
	pointer is created for each possible layout here.

	Blocks
	~~~~~~

	Blocks are similar to contexts but have a common header and package the
	function pointer and captured values in a single retainable heap object.

	Metatypes
	~~~~~~~~~

	Runtime-allocated metatypes will appear in the malloc heap. They themselves
	cannot contain heap references though.


	Opaque value buffers
	~~~~~~~~~~~~~~~~~~~~

	These come up when a value is too large to fit inside of an existential's
	inline storage, for example. They do not have a header, so we will not attempt
	to introspect them at first -- eventually, we could identify pointers to buffers
	where the existential is itself inside of a heap-allocated object.

	Existing metadata
	-----------------

	Swift already has a lot of reflective features and much of the groundwork for
	this exists in some form or another, but each one is lacking in at least one
	important respect.

	Generic type metadata
	~~~~~~~~~~~~~~~~~~~~~

	The isa pointer of an object points to a metadata record. For instances of
	generic class types, the metadata is lazily instantiated from the generic
	metadata template together with the concrete types that are bound to generic
	parameters.

	Generic type metadata is instantiated for generic classes with live instances,
	and for metatype records of value types which are explicitly referenced from
	source.

	When the compiler needs to emit a generic type metadata record, it uses one of
	several strategies depending on the type being referenced. For concrete
	non-generic types, a direct call to a lazy accessor can be generated. For bound
	generic types T<P1, ..., Pn>, we recursively emit metadata references for the
	generic parameters Pn, then call the getter for the bound type T. For
	archetypes -- that is, generic type parameters which are free variables in the
	function body being compiled -- the metadata is passed in as a value, so the
	compiler simply emits a copy of that.

	Generic type metadata tells us the size of each heap allocation, but does not
	by itself tell us the types of the fields or what references they contain.

	Mirrors and NominalTypeDescriptors
	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

	The implementation of Mirrors uses runtime primitives which introspect the
	fields of an opaque value by looking at the NominalTypeDescriptor embedded in a
	type's metadata record.

	For structures and classes, the NominalTypeDescriptor contains a function
	pointer which returns an array of field types. The function pointer points to a
	"field type metadata function" emitted by the compiler. This function emits
	metadata record references for each field type and collects them in an array.
	Since the isa pointer of a class instance points at an instantiated type, the
	field types of such a NominalTypeDescriptor are also all concrete types.

	NominalTypeDescriptors record field names, in addition to types. Right now, all
	of this information is stored together, without any way of stripping it out.
	Also, NominalTypeDescriptors do not record whether a reference is strong, weak
	or unowned, but that would be simple to fix.

	A bigger problem is that we have to call a function to lazily generate the
	field type metadata. While a NominalTypeDescriptor for every instantiated class
	type appears in a crashed process, the field types do not, because only a call
	to the field type function will instantiate them.

	Objective-C instance variable metadata
	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

	The Objective-C runtime keeps track of the types of instance variables of
	classes, and there is enough information here to identify pointers in instances
	of concrete types, however there's no support for generic types. We could have
	generic type metadata instantiation also clone and fill in templates for
	Objective-C instance variables, but this would add a runtime cost to a feature
	that is primarily intended for debugging.

	DWARF metadata
	~~~~~~~~~~~~~~

	IRGen emits some minimal amount of DWARF metadata for non-generic types, but
	makes no attempt to describe generic type layout to the debugger in this
	manner.

	However, DWARF has the advantage that it can be introspected without running
	code, and stripped out.

	New field type metadata format
	------------------------------

	The main limitation of all of the above is either an inability to reason about
	generic types, or the requirement to run code in the target.

	Suppose T is a generic type, and S is some set of substitutions.

	The compiler conceptually implements an operation G(T, S) which returns a
	lazily-instantiated type descriptor for the given input parameters. However,
	its really performing a partial evaluation G(T)(S), with the "G(T)" part
	happening at compile time.

	Similarly, we can think of the field type access function as an operation F(T,
	S) which returns the types of the fields of T, with T again fixed at compile
	time.

	What we really want here is to build an "interpreter" -- or really, a parser for
	a simple serialized graph -- which understands how to parse uninstantiated
	generic metadata, keep track of substitutions, and calculate field offsets,
	sizes, and locations of references.

	This "interpreter" has to be able to find metadata for leaf types "from
	scratch", and calculate field sizes and offsets in the same way that generic
	type metadata instantiation calculates object sizes.

	The "interpreter" will take the form of a library for understanding field type
	metadata records and symbolic type references. This will be a C++ library and
	it needs to support the following use cases:

	#. In-process reflection, for backing the current Mirrors in the standard
	library
	#. Out-of-process reflection, for heap debugging tools
	#. Out-of-process reflection, for a new remote Mirrors feature in the library
	(optional)

	The API will be somewhat similar to Mirrors as they are in the stdlib today.

	The details are described below.

	Symbolic type references
	~~~~~~~~~~~~~~~~~~~~~~~~

	Since we're operating on uninstantiated generic metadata, we need some way to
	describe compositions of types. Instead of using metadata record pointers,
	which are now insufficient, we use type references written in a mini-language.

	A symbolic type reference is a recursive structure describing an arbitrary
	Swift AST type in terms of nominal types, generic type parameters, and
	compositions of them, such as tuple types.

	For each AST type, we can distinguish between the minimum information we need
	to identify heap references therein, and the full type for reflection. The
	former could be retained while the latter could be stripped out in certain
	builds.

	We already have a very similar encoding -- parameter type mangling in SIL. It
	would be good to re-use this encoding, but for completeness, the full format of
	a type reference is described below:


	#. A built-in type reference. Special tokens can be used to refer to
	various built-in types that have runtime support.

	#. A concrete type reference. This can either be a mangled name of a type,
	or a GOT offset in the target.

	#. A heap reference. This consists of:

	- strong, weak or unowned
	- (optional) a reference to the class type itself

	#. A bound generic type. This consists of:

	- A concrete or built-in type reference
	- A nested symbolic type reference for each generic parameter

	#. A tuple type. This consists of:

	- A recursive sequence of symbolic type references.

	#. A function type. This consists of:

	- A representation,
	- (optional) input and output types

	#. A protocol composition type. This consists of:

	- A flag indicating if any of the protocols are class-constrained, which
	changes the representation
	- The number of non-@objc protocols in the composition
	- (optional) references to all protocols in the composition

	#. A metatype. This consists of:

	- (optional) a type reference to the instance type
	- there's no required information -- a metatype is always a single pointer to
	a heap object which itself does not reference any other heap objects.

	#. An existential metatype. This consists of:

	- The number of protocols in the composition.
	- (optional) type references to the protocol members.

	#. A generic parameter. Within the field types of a generic type,
	references to generic parameters can appear. Generic parameters are uniquely
	identifiable by an index here (and once we add nested generic types, a depth).

	You can visualize type references as if they are written in an S-expression
	format -- but in reality, it would be serialized in a compact binary form:

	::

	(tuple_type
	(bound_generic_type
	(concrete_type "Array")
	(concrete_type "Int"))
	(bound_generic_type
	(builtin_type "Optional")
	(generic_type_parameter_type index=0)))

	We will provide a library of standalone routines for decoding, encoding and
	manipulating symbolic type references.

	Field type metadata records
	~~~~~~~~~~~~~~~~~~~~~~~~~~~

	We introduce a new type of metadata, stored in its own section so that it can
	be stripped out, called "field type metadata". For each nominal type, we emit a
	record containing the following:

	#. the name of the nominal type,
	#. the number of generic parameters,
	#. type references, written in the mini-language above, for each of its field
	types.
	#. field names, if enabled.

	Field type metadata is linked together so that it can be looked up by name,
	post-mortem by introspecting the core dump.

	We add a new field to the NominalTypeDescriptor to store a pointer to field
	type metadata for this nominal type. In "new-style" NominalTypeDescriptors that
	contain this field, the existing field type function will point to a common
	field type function, defined in the runtime, which instantiates the field type
	metadata. This allows for backward compatibility with old code, if desired.

	Field type metadata instantiation
	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

	First, given an isa pointer in the target, we need to build the symbolic type
	reference by walking backwards from instantiated to uninstantiated metadata,
	collecting generic parameters. This operation is lazy, caching the result for
	each isa pointer.

	::

	enum SymbolicTypeReference {
	case Concrete(String)
	case BoundGeneric(String, [SymbolicTypeReference])
	case Tuple([SymbolicTypeReference])
	...
	}

	func getSymbolicTypeOfObject(_ isa: void*) -> SymbolicTypeReference

	Next, we define an "instantiation" operation, which takes a completely
	substituted symbolic type reference, and returns a list of concrete field types
	and offsets.

	This operation will need to recursively visit field metadata records and keep
	track of generic parameter substitutions in order to correctly calculate all
	field offsets and sizes.

	The result of instantiating metadata for each given SymbolicTypeReference can
	be cached for faster lookup.

	This library has to be careful when following any pointers in the target, to
	properly handle partially-initialized objects, runtime bugs that led to memory
	corruption, or malicious code, without crashing or exploiting the debugging
	tools.

	::

	enum FieldLayout {
	// the field contains a heap reference
	case Strong, Weak, Unowned
	// the field is an opaque binary blob, contents unknown.
	case Opaque
	// the field is a value type -- look inside recursively.
	case ValueType(indirect field: FieldDescriptor)
	}

	struct FieldDescriptor {
	let size: UInt
	let align: UInt
	let offset: UInt
	let layout: FieldLayout
	}

	func instantiateSymbolicType(_ ref: SymbolicTypeReference) -> [FieldTypeDescriptor]

	Field type metadata can have circular references -- for example, consider two
	classes which contain optionals of each other. In order to calculate field
	offsets correctly, we need to break cycles when we know something is a class
	type, and use a work-list algorithm instead of unbounded recursion to ensure
	forward progress.

	Enum type metadata
	~~~~~~~~~~~~~~~~~~

	For enums, the field metadata record will also need to contain enough
	information about the spare bits and tag bits of the payload types that we can
	at runtime determine the case of an enum and project the payload, again without
	running code in the target.

	This will allow us to remove a pair of value witness functions generated purely
	for reflection, since they don't seem to be performance-critical.

	Closures
	~~~~~~~~

	For closure contexts and blocks, it would be nice to emit metadata, too.

	Secrecy and release builds
	~~~~~~~~~~~~~~~~~~~~~~~~~~

	There are several levels of metadata we can choose to emit here:

	#. For code that requires runtime for functional purposes, or for the standard
	library in debug builds, we can have a protocol conformance or compiler flag
	enable unconditional emission of all metadata.
	#. For system frameworks, we can omit field names and replace class names with
	unique identifiers, but keep the type metadata to help users debug memory leaks
	where framework classes are retaining instances of user classes.
	#. For release builds, we can strip out all the metadata except where
	explicitly required in 1).

	This probably requires putting the required metadata in a different section
	from the debug metadata. Perhaps field names should be separate from symbolic
	type references too.

	Performance
	~~~~~~~~~~~

	Since the field type metadata instantiation only happens once per isa pointer,
	mirrors will not suffer a performance impact beyond the initial warm-up time.
	Once the field type descriptor has been constructed, reflective access of
	fields will proceed as before.

	There might also be a marginal performance gain from removing all the field
	type functions from the text segment, where they're currently interspersed with
	other code, and replacing them with read only data containing no relocations,
	which won't get paged in until needed.

	Resilience
	~~~~~~~~~~

	We may choose to implement the new metadata facility after stabilizing the ABI.
	In this case, we should front-load some engineering work on
	NominalTypeDescriptors first, to make them more amenable to future extension.

	We need to carefully review the new metadata format and make sure it is
	flexible enough to support future language features, such as bound generic
	existentials, which may further complicate heap layout.

	As described above, it is possible to introduce this change in a
	backwards-compatible manner. We keep the field type function field in the
	NominalTypeDescriptor, but for "new-style" records, set it to point to a common
	function, defined in the runtime, which parses the new metadata and returns an
	array of field types that can be used by old clients.

	Testing
	~~~~~~~

	By transitioning mirrors to use the new metadata, existing tests can be used to
	verify behavior. Additional tests can be developed to perform various
	allocations and assert properties of the resulting object graph, either from
	in- or out-of-process.

	If we go with the gradual approach where we have both field type functions and
	field type metadata, we can also instantiate the former and compare it against
	the result of invoking the latter, for all types in the system, as a means of
	validating the field type metadata.