swift-mirror/docs/Generics/chapters/substitution-maps.tex

\documentclass[../generics]{subfiles}

\begin{document}

\chapter{Substitution Maps}\label{substmaps}

\lettrine{S}{ubstitution maps arise} when the type checker needs to reason about a reference to a generic declaration, specialized with list of generic arguments. Abstractly, a \IndexDefinition{substitution map}substitution map defines a \IndexDefinition{replacement type}replacement type corresponding to each type parameter of a generic signature; applying a substitution map to the interface type of a generic declaration recursively replaces the type parameters therein, producing the type of the specialized reference.

The \index{generic signature!type substitution}generic signature of a substitution map is called the \IndexDefinition{input generic signature}\emph{input generic signature}. A substitution map stores its input generic signature, and the generic signature's list of generic parameters and \index{conformance}conformance requirements determine the substitution map's shape:
\begin{quote}
\texttt{<\ttbox{A}, \ttbox{B} where \ttbox{B:\ Sequence}, B.[Sequence]Element == Int>}
\end{quote}
Formally, a substitution map consists of a replacement type for each generic parameter, and a conformance for each conformance requirement:
\begin{quote}
\begin{tabular}{ccc}
\ttbox{A}&\ttbox{B}&\ttbox{B:\ Sequence}\\
$\Downarrow$&$\Downarrow$&$\Downarrow$\\
\ttbox{String}&\ttbox{Array<Int>}&\ttbox{Array<Int>:\ Sequence}
\end{tabular}
\end{quote}
We can collect all of the above information in a table:
\begin{quote}
\begin{tabular}{|lcl|}
\hline
\rule{0pt}{3ex}\textbf{Generic parameters}&&\textbf{Replacement types}\\
\texttt{A}&$\mapsto$&\texttt{String}\\
\texttt{B}&$\mapsto$&\texttt{Array<Int>}\\[\medskipamount]
\textbf{Conformance requirements}&&\textbf{Conformances}\\
$\ConfReq{B}{Sequence}$&$\mapsto$&$\ConfReq{Array<Int>}{Sequence}$\\[\medskipamount]
\hline
\end{tabular}
\end{quote}
Or more concisely,\index{$\mapsto$}\index{$\mapsto$!z@\igobble|seealso{substitution map}}
\begin{align*}
\SubstMapC{
&\SubstType{A}{String},\\
&\SubstType{B}{Array<Int>}
}{\\
&\SubstConf{B}{Array<Int>}{Sequence}
}
\end{align*}

\begin{listing}\captionabove{Substitution maps in type checking}\label{substmaptypecheck}
\begin{Verbatim}
func genericFunction<A, B: Sequence>(_: A, _: B)
    where B.Element == Int {}

struct GenericType<A, B: Sequence> where B.Element == Int {
  func nonGenericMethod() {}
}

// substitution map for the call is {A := String, B := Array<Int>}.
genericFunction("hello", [1, 2, 3])

// the type of `value' is GenericType<String, Array<Int>>.
let value = GenericType<String, Array<Int>>()

// the context substitution map for the type of `value' is
// {A := String, B := Array<Int>}.
value.nonGenericMethod()
\end{Verbatim}
\end{listing}

\begin{example}
We often use the Greek letter $\Sigma$, in various forms, to denote substitution maps. For example, $\Sigma$, $\Sigma_1$, $\Sigma_2$, $\Sigma^\prime$, etc. For now we'll just work with the single substitution map defined above, so let's denote it by $\Sigma$:
\begin{align*}
\Sigma := \SubstMapC{
&\SubstType{A}{String},\\
&\SubstType{B}{Array<Int>}
}{\\
&\SubstConf{B}{Array<Int>}{Sequence}
}
\end{align*}
Our substitution map appears while type checking the program shown in \ListingRef{substmaptypecheck}. Here, all three of \texttt{genericFunction()}, \texttt{GenericType} and \texttt{nonGenericMethod()} have the same generic signature, \texttt{<A, B where B:~Sequence, B.Element == Int>}. When type checking a generic function call, the expression type checker infers the generic arguments from the types of the argument expressions. When referencing a generic type, the generic arguments can be written explicitly. In fact, all three declarations are also referenced with the same substitution map. (In the case of a generic type, this substitution map is called the \emph{context substitution map}, as you will see in \SecRef{contextsubstmap}.)
\end{example}

\paragraph{Type substitution.} Substitution maps operate on interface types. Recall that an \index{interface type!type substitution}interface type is a type \emph{containing} valid type parameters for some generic signature, which may itself not be a type parameter; for example, one possible interface type is \texttt{Array<T>}, if \texttt{T} is a generic parameter type. Let's introduce the formal notation \IndexSetDefinition{type}{\TypeObj{G}}$\TypeObj{G}$ to mean the set of interface types for a generic signature $G$. Then, if $\texttt{T}\in\TypeObj{G}$ and $\Sigma$ is a substitution map with input generic signature $G$, we can \emph{apply} $\Sigma$ to \texttt{T} to get a new type. This operation is called \IndexDefinition{type substitution}\emph{type substitution}. The interface type here is called the \IndexDefinition{original type}\emph{original type}, and the result of the substitution is the \IndexDefinition{substituted type}\emph{substituted type}. We will think of applying a substitution map to an interface type as an binary operation: \[\texttt{T}\otimes\Sigma\]
The \index{$\otimes$}\index{$\otimes$!z@\igobble|seealso{type substitution}}\index{binary operation}$\otimes$ binary operation is a \emph{right action} of substitution maps on types. (We could have instead defined a left action, but later we will see the right action formulation is more natural for expressing certain identities. Indeed, we'll develop this notation further throughout this book.)

Type substitution recursively replaces any type parameters appearing in the original type with new types derived from the substitution map, while preserving the ``concrete structure'' of the original type. Thus the behavior of type substitution is ultimately defined by how substitution maps act the two kinds of type parameters: generic parameters and dependent member types:
\begin{itemize}
\item Applying a substitution map to a generic parameter type returns the corresponding replacement type from the substitution map.

Type substitution does not care about generic parameter sugar in the original type; replacement types for generic parameters are always looked up by depth and index in the substitution map.

\item Applying a substitution map to a dependent member type derives the replacement type from one of the substitution map's conformances.

Now, we haven't talked about conformances yet. There is a circularity between substitution maps and conformances---substitution maps can store conformances, and conformances can store substitution maps. We will look at conformances in great detail in \ChapRef{conformances}. The derivation of replacement types for dependent member types is discussed in \SecRef{abstract conformances}.
\end{itemize}

\begin{example}
Applying the substitution map from our running example to sugared and canonical generic parameter types produces the same results:
\[
\left\{
\begin{array}{l}
\texttt{A}\\
\ttgp{0}{0}\\
\texttt{B}\\
\ttgp{0}{1}
\end{array}\right\}
\otimes
\Sigma
=
\left\{
\begin{array}{l}
\texttt{String}\\
\texttt{String}\\
\texttt{Array<Int>}\\
\texttt{Array<Int>}
\end{array}\right\}
\]
\end{example}
\begin{listing}\captionabove{Applying a substitution map to four interface types}\label{typealiassubstlisting}
\begin{Verbatim}
struct GenericType<A, B: Sequence> where B.Element == Int {
  typealias T1 = A
  typealias T2 = B
  typealias T3 = (A.Type, Float)
  typealias T4 = (Optional<A>) -> B
}

let t1: GenericType<String, Array<Int>>.T1 = ...
let t2: GenericType<String, Array<Int>>.T2 = ...
let t3: GenericType<String, Array<Int>>.T3 = ...
let t4: GenericType<String, Array<Int>>.T4 = ...
\end{Verbatim}
\end{listing}

\begin{example}\label{type alias subst example} \ListingRef{typealiassubstlisting} shows a generic type with four member type alias declarations. There are four global variables, and the type of each global variable is written as a member type alias reference with the same type base type, \texttt{GenericType<String, Array<Int>>}. 

\index{underlying type}
\index{type alias declaration}
\index{substitution map}
Type resolution resolves a member type alias reference by applying a substitution map to the underlying type of the type alias declaration. Here, the underlying type of each type alias declaration is an interface type for the generic signature of \texttt{GenericType}, and the substitution map is the substitution map $\Sigma$ of \ExRef{substmaptypecheck}.

The type of each global variable \texttt{t1}, \texttt{t2}, \texttt{t3} and \texttt{t4} is determined by applying $\Sigma$ to the underlying type of each type alias declaration:
\begin{quote}
\begin{tabular}{lll}
\toprule
&\textbf{Original type}&\textbf{Substituted type}\\
\midrule
\texttt{t1}&\texttt{A}&\texttt{String}\\
\texttt{t2}&\texttt{B}&\texttt{Array<Int>}\\
\texttt{t3}&\texttt{(A.Type, Float)}&\texttt{(String.Type, Float)}\\
\texttt{t4}&\texttt{(Optional<A>) -> B}&\texttt{(Optional<String>) -> Array<Int>}\\
\bottomrule
\end{tabular}
\end{quote}
The first two original types are generic parameters, and substitution directly projects the corresponding replacement type from the substitution map; the second two original types are substituted by recursively replacing generic parameters they contain.
\end{example}

References to generic type alias declarations are more complex because in addition to the generic parameters of the base type, the generic type alias will have generic parameters of its own. \SecRef{identtyperepr} describes how the substitution map is computed in this case.

\paragraph{Substitution failure.}
Substitution of an interface type containing dependent member types can \IndexDefinition{substitution failure}\emph{fail} if any of the conformances in the substitution map are invalid. In this case, an \index{error type}error type is returned instead of signaling an assertion. Invalid conformances can appear in substitution maps when the user's own code is invalid; it is not an invariant violation as long as other errors are diagnosed elsewhere and the compiler does not proceed to \index{SILGen}SILGen with error types in the \index{abstract syntax tree}abstract syntax tree.

\paragraph{Output generic signature.}
If the replacement types in the substitution map are \index{fully-concrete type}fully concrete---that is, they do not contain any type parameters---then all possible substituted types produced by this substitution map will also be fully concrete. If the replacement types are interface types for some \IndexDefinition{output generic signature}\emph{output} generic signature, the substitution map will produce interface types for this generic signature. The output generic signature might be a different from the \emph{input} generic signature of the substitution map. 

The output generic signature is not stored in the substitution map; it is implicit from context. Also, fully-concrete types can be seen as valid interface types for \emph{any} generic signature, because they do not contain type parameters at all. Keeping these caveats in mind, we have this essential principle:
\begin{quote}
\textbf{A substitution map defines a transformation from the interface types of its input generic signature to the interface types of its output generic signature.}
\end{quote}
Recall our notation $\TypeObj{G}$ for the set of interface types of $G$. We also use the notation \IndexSetDefinition{sub}{\SubMapObj{G}{H}}$\SubMapObj{G}{H}$ for the set of substitution maps with input generic signature $G$ and output generic signature $H$. We make use of this notation to formalize our principle. If $\texttt{T}\in\TypeObj{G}$ and $\Sigma\in\SubMapObj{G}{H}$, then $\texttt{T}\otimes\Sigma\in\TypeObj{H}$, and thus the $\otimes$ binary operation is a function between the following sets:
\[\TypeObj{G}\otimes\SubMapObj{G}{H}\longrightarrow\TypeObj{H}\]

\begin{algorithm}[Substitute interface type]\label{type subst algo}
Takes an interface type \tX\ and a substitution map $\Sigma$ as input. The type parameters contained in \tX\ must be valid for the input generic signature of $\Sigma$. Outputs $\tX\otimes\Sigma$.
\begin{enumerate}
\item If \tX\ is a generic parameter type \ttgp{d}{i}, find the replacement type for \ttgp{d}{i} in~$\Sigma$ and return it.
\item If \tX\ is a dependent member type \texttt{T.[P]A}, apply \AlgRef{dependent member type substitution} to \texttt{T.[P]A}~and~$\Sigma$, and return the result.
\item If \tX\ does not recursively contain any type parameters, return \tX.
\item Otherwise, recursively apply this algorithm to each child of \tX, and return the new type formed from the substituted children.
\end{enumerate}
\end{algorithm}

\section{Generic Arguments}\label{contextsubstmap}

A nominal type is \IndexDefinition{specialized type}\emph{specialized} if the type itself or one of its \index{parent type!specialized type}parent types is a generic nominal type. That is, \texttt{Array<Int>} and \texttt{Array<Int>.Iterator} are both specialized types, but \texttt{Int} and \texttt{String.UTF8View} are not. Equivalently, a nominal type is specialized if its nominal type declaration is a generic context---that is, if the type declaration itself has a generic parameter list, or an outer declaration context has one.

Every specialized type determines a unique substitution map for the generic signature of its declaration, called the \IndexDefinition{context substitution map}\emph{context substitution map}. The context substitution map replaces the generic parameters of the type declaration with the corresponding generic arguments of the specialized type.

Let's say that $d$ is a \index{nominal type declaration!generic arguments}nominal type declaration with generic signature $G$. The \index{declared interface type!nominal type declaration}declared interface type of $d$, which we will denote by $\tXd$, is an element of $\TypeObj{G}$. Suppose that \tX\ is some specialized type of $d$ whose generic arguments are interface types for a generic signature $H$, so that $\tX\in\TypeObj{H}$. The context substitution map of \tX\ is a substitution map $\Sigma\in\SubMapObj{G}{H}$, such that applying it to the declared interface type of $d$ gives us back \texttt{T}. That is,
\[
\tX = \tXd\otimes\Sigma
\]
To demonstrate the above identity, consider the generic signature of the \texttt{Dictionary} type declaration in the standard library:
\begin{quote}
\texttt{<Key, Value where Key:\ Hashable>}
\end{quote}
One possible specialized type for \texttt{Dictionary} is the type \texttt{Dictionary<Int, String>}; this type is related to the declared interface type of \texttt{Dictionary} by this substitution map:
\begin{align*}
\texttt{Dictionary<\ttgp{0}{0}, \ttgp{0}{1}>}\otimes
\SubstMapC{
&\SubstType{\ttgp{0}{0}}{Int},\\
&\SubstType{\ttgp{0}{1}}{String}
}{\\
&\SubstConf{\ttgp{0}{0}}{Int}{Hashable}
}\\
{} = \texttt{Dictionary<Int, String>}
\end{align*}
\paragraph{The identity substitution map.}
What is the context substitution map of a type declaration's declared interface type? By definition, if $\Sigma$ is the context substitution map of $\tXd$, then $\tXd\otimes\Sigma=\tXd$; it leaves the declared interface type unchanged. That is, this substitution map maps every generic parameter of the type declaration's generic signature to itself. If we look at the \texttt{Dictionary} type again, we can write down this substitution map:
\begin{align*}
\texttt{Dictionary<\ttgp{0}{0}, \ttgp{0}{1}>}\otimes
\SubstMapC{
&\SubstType{\ttgp{0}{0}}{\ttgp{0}{0}},\\
&\SubstType{\ttgp{0}{1}}{\ttgp{0}{1}}
}{\\
&\SubstConf{\ttgp{0}{0}}{\ttgp{0}{0}}{Hashable}
}\\
{} = \texttt{Dictionary<\ttgp{0}{0}, \ttgp{0}{1}>}
\end{align*}
This is called the \IndexDefinition{identity substitution map}\emph{identity substitution map} for this generic signature; every generic signature has one. We denote the identity substitution map of a generic signature $G$ by \index{$1_G$}\index{$1_G$!z@\igobble|seealso{identity substitution map}}$1_G$. Then, $1_G\in\SubMapObj{G}{G}$, and if $\texttt{T}\in\TypeObj{G}$, we have
\[\tX \otimes 1_G = \tX\]
Applying the identity substitution map to any interface type leaves it unchanged, with three caveats:
\begin{enumerate}
\item The interface type must only contain type parameters which are valid in the input generic signature $G$ of this identity substitution map $1_G$.
\item Substitution might change type sugar, because generic parameters appearing in the original interface type might be sugared differently than the input generic signature of this identity substitution map. Therefore, canonical equality of types is preserved, not necessarily pointer equality.
\item We won't talk about archetypes until \ChapRef{genericenv}, but you may have met them already. Applying the identity substitution map to a contextual type containing archetypes replaces the archetypes with equivalent type parameters. There is a corresponding \emph{forwarding substitution map} which maps all generic parameters to archetypes; the forwarding substitution map acts as the identity in the world of contextual types.
\end{enumerate}

\paragraph{The empty substitution map.}
The \index{empty generic signature}empty generic signature only has a single unique substitution map, the \IndexDefinition{empty substitution map}\emph{empty substitution map}, so the context substitution map of a non-specialized nominal type is the empty substitution map. In our notation, the empty substitution map is denoted $\SubstMap{}$. The only valid interface types of the empty generic signature are the \index{fully-concrete type}fully-concrete types. The action of the empty substitution map leaves fully-concrete types unchanged, so for example, $\texttt{Int}\otimes\SubstMap{} = \texttt{Int}$.

The empty substitution map $\SubstMap{}$ is almost never the same as the identity substitution map $1_G$. In fact, they only coincide if $G$ is the empty generic signature. Applying the empty substitution map to an interface type containing type parameters is a substitution failure and returns an error type.
\[\texttt{\ttgp{0}{0}.[Sequence]Element} \otimes \SubstMap{} = \texttt{<<error type>>}\]

\section{Composing Substitution Maps}\label{submapcomposition}\label{classinheritance}

\iffalse

\SecRef{abstract conformances} talks about composition with root conformances

\fi

Suppose that we have three generic signatures, $G$, $H$ and $I$, and a pair of substitution maps: $\Sigma_1\in\SubMapObj{G}{H}$, and $\Sigma_2\in\SubMapObj{H}{I}$. If we start with an interface type $\tX\in\TypeObj{G}$, then $\tX\otimes\Sigma_1\in\TypeObj{H}$. If we then apply $\Sigma_2$ to $\tX\otimes\Sigma_1$, we get an interface type in $\TypeObj{I}$:
\[(\tX\otimes\Sigma_1)\otimes\Sigma_2\]
The \IndexDefinition{substitution map composition}\emph{composition} of the substitution maps $\Sigma_1$ and $\Sigma_2$, denoted by \index{$\otimes$}$\Sigma_1\otimes\Sigma_2$, is the unique substitution map which satisfies the following equation for all $\tX\in\TypeObj{F}$:
\[\tX\otimes(\Sigma_1\otimes\Sigma_2):=(\tX\otimes\Sigma_1)\otimes\Sigma_2\]
That is, applying the composition of two substitution maps is the same as applying the first substitution map followed by the second. Since $(\tX\otimes\Sigma_1)\otimes\Sigma_2\in\TypeObj{I}$, we see that $\Sigma_1\otimes\Sigma_2\in\SubMapObj{G}{I}$; the \index{input generic signature}input generic signature of the composition is the input generic signature of the first substitution map, and the output generic signature of the composition is the \index{output generic signature}output generic signature of the second. Substitution map composition can thus be understood as a function between sets:
\[\SubMapObj{G}{H}\otimes\SubMapObj{H}{I}\longrightarrow\SubMapObj{G}{I}\]

To understand how the composition $\Sigma_1\otimes\Sigma_2$ is actually constructed from $\Sigma_1$ and $\Sigma_2$ in the implementation, we decompose $\Sigma_1$ by applying it to each \index{generic parameter type!type substitution}generic parameter of generic signature $F$:
\[\Sigma_1 := \SubstMap{\SubstType{\ttgp{0}{0}}{$\ttgp{0}{0}\otimes\Sigma_1$},\,\ldots}\]
This looks like a circular definition, but what it really says is that the behavior of $\Sigma_1$ is completely determined by these primitive elements of its input generic signature. Now, we define $\Sigma_1\otimes\Sigma_2$ by applying $\Sigma_2$ to each element of $\Sigma_1$:
\[
\Sigma_1\otimes\Sigma_2 := \SubstMap{
\SubstType{\ttgp{0}{0}}{$\bigl((\ttgp{0}{0}\otimes\Sigma_1)\otimes\Sigma_2\bigr)$},\,
\ldots
}
\]
Under this definition, if we take a generic parameter \ttgp{d}{i} of $G$, we see that $\Sigma_1\otimes\Sigma_2$ satisfies the necessary identity:
\[
\ttgp{d}{i}\otimes(\Sigma_1\otimes\Sigma_2)=(\ttgp{d}{i}\otimes\Sigma_1)\otimes\Sigma_2
\]
Since the behavior of $\Sigma_1\otimes\Sigma_2$ is completely determined by its replacement types, this is actually true for any interface type $\tX\in\TypeObj{G}$:
\[\tX\otimes(\Sigma_1\otimes\Sigma_2)=(\tX\otimes\Sigma_1)\otimes\Sigma_2\]

\newcommand{\FirstMapInExample}{\SubstMap{
\SubstType{T}{Array<A>},\,\SubstType{U}{A}
}}
\newcommand{\SecondMapInExample}{\SubstMap{
\SubstType{A}{Int}
}}
\newcommand{\ThirdMapInExample}{\SubstMap{
\SubstType{T}{Array<Int>},\,\SubstType{U}{Int}
}}

\begin{listing}\captionabove{Motivating substitution map composition}\label{composesubstmaplisting}
\begin{Verbatim}
struct Outer<A> {
  var inner: Inner<Array<A>, A>
}

struct Inner<T, U> {
  var value: (T) -> U
}

let outer: Outer<Int> = ...
let x = outer.inner.value
\end{Verbatim}
\end{listing}
\begin{example}\label{composesubstmapexample}
\index{expression}
\ListingRef{composesubstmaplisting} shows an example where substitution map composition can help reason about the types of chained \index{member reference expression}member reference expressions. The \texttt{inner} stored property of \texttt{Outer} has type \texttt{Inner<Array<A>, A>}. Here is the context substitution map of this type, which we will refer to as $\Sigma_1$:
\[
\Sigma_1 := \FirstMapInExample
\]
The interface type of the \texttt{inner} stored property is a specialization of the nominal type \texttt{Inner} with generic signature \texttt{<T, U>}, so the input generic signature of $\Sigma_1$ is \texttt{<T, U>}. The interface type of \texttt{inner} is declared inside the nominal type \texttt{Outer} with generic signature \texttt{<A>}, so the output generic signature of $\Sigma_1$ is \texttt{<A>}.

Now, let's look at the \texttt{outer} global variable. It has the type \texttt{Outer<Int>}, with the following context substitution map, which we denote as $\Sigma_2$:
\[
\Sigma_2 := \SecondMapInExample
\]
The input generic signature of $\Sigma_2$ is \texttt{<A>}, the generic signature of \texttt{Outer}. The output generic signature of $\Sigma_2$ is the empty generic signature, because its replacement types are fully concrete. We can compose $\Sigma_1$ and $\Sigma_2$, because the output generic signature of $\Sigma_1$ is the same as the input generic signature of $\Sigma_2$:
\[\Sigma_1\otimes\Sigma_2 = \FirstMapInExample\otimes\SecondMapInExample = \ThirdMapInExample\]

Now, the substituted type of \texttt{outer.inner.value} can be derived from the interface type of \texttt{value} in two equivalent ways:
\begin{enumerate}
\item By applying $\Sigma_1$ to \verb|(T) -> U| and then applying $\Sigma_2$ to the result:
\begin{gather*}
(\texttt{(T) -> U}\otimes\Sigma_1)\otimes \Sigma_2\\
\qquad {} = \texttt{(Array<A>) -> A}\otimes \Sigma_2\\
\qquad {} = \texttt{(Array<Int>) -> Int}
\end{gather*}
\item By applying the composition $\Sigma_1\otimes\Sigma_2$ to \texttt{(T) -> U}:
\begin{gather*}
\texttt{(T) -> U}\otimes(\Sigma_1\otimes \Sigma_2)\\
\qquad {} = \texttt{(T) -> U}\otimes \ThirdMapInExample\\
\qquad {} = \texttt{(Array<Int>) -> Int}
\end{gather*}
\end{enumerate}
The final substituted type, \texttt{(Array<Int>) -> Int}, is the same in both cases.
\end{example}
If $\Sigma\in\SubMapObj{G}{H}$, then the identity substitution maps $1_G$ and $1_H$ have a natural behavior under substitution map composition:
\[1_G\otimes\Sigma = \Sigma\otimes 1_H = \Sigma\]
The second identity carries the same caveat as the identity $\tX\otimes 1_G=\tX$ does for types; it is only true if the replacement types of $\Sigma$ are interface types. If the replacement types are contextual types, they will map to interface types, as we will explain in \SecRef{archetypesubst}.
\begin{example}
Recall the generic signatures $G$ and $H$, and the substitution map $\Sigma_1 := \FirstMapInExample\in\SubMapObj{G}{H}$ from \ExRef{composesubstmapexample}. We can write down the identity substitution maps $1_G$ and $1_H$:
\begin{gather*}
1_G := \SubstMap{\SubstType{T}{T},\,\SubstType{U}{U}}\\
1_H := \SubstMap{\SubstType{A}{A}}
\end{gather*}
Now, one can verify that both of these hold:
\begin{gather*}
\SubstMap{\SubstType{T}{T},\,\SubstType{U}{U}}\otimes\FirstMapInExample=\FirstMapInExample\\
\FirstMapInExample\otimes\SubstMap{\SubstType{A}{A}}=\FirstMapInExample
\end{gather*}
Thus $1_G\otimes\Sigma_1 = \Sigma_1\otimes 1_H=\Sigma_1$. Note that the left and right identity substitution maps are different in this case, because the input and output generic signatures of $\Sigma_1$ are different.
\end{example}
\index{associative operation}
One final rule here is that substitution map composition is \emph{associative}. This means that both possible ways of composing three substitution maps will output the same result:
\[
(\Sigma_1\otimes\Sigma_2)\otimes\Sigma_3=\Sigma_1\otimes(\Sigma_2\otimes\Sigma_3)
\]
Putting everything together, if \tX is some type, all of the following are equivalent when defined (and by our compatibility conditions, if one is defined, all are):
\begin{gather*}
((\tX\otimes\Sigma_1)\otimes\Sigma_2)\otimes\Sigma_3\\
(\tX\otimes\Sigma_1)\otimes(\Sigma_2\otimes\Sigma_3)\\
(\tX\otimes(\Sigma_1\otimes\Sigma_2))\otimes\Sigma_3\\
\tX\otimes((\Sigma_1\otimes\Sigma_2)\otimes\Sigma_3)\\
\tX\otimes(\Sigma_1\otimes(\Sigma_2\otimes\Sigma_3))
\end{gather*}
Thus, our type substitution algebra allows us to omit grouping parentheses without introducing ambiguity:
\[\tX\otimes\Sigma_1\otimes\Sigma_2\otimes\Sigma_3\]

A \IndexDefinition{commutative diagram}\emph{commutative diagram} is one where following the chain of operations along two paths with the same start and end always produces the same result.

\paragraph{Categorically speaking.}
A \IndexDefinition{category}\emph{category} is a collection of \IndexDefinition{object}\emph{objects} and \IndexDefinition{morphism}\emph{morphisms}. (Very often the morphisms are \index{function}functions of some sort, but they might also be completely abstract.) Each morphism is associated with a pair of objects, the \emph{source} and \emph{destination}. The collection of morphisms with source $A$ and destination $B$ is denoted $\mathrm{Hom}(A,B)$. The morphisms of a category must obey certain properties:
\begin{enumerate}
\item For every object $A$, there is an \IndexDefinition{identity morphism}\emph{identity morphism} $1_A\in\mathrm{Hom}(A, A)$.
\item If $f\in\mathrm{Hom}(A, B)$ and $g\in\mathrm{Hom}(B, C)$ are a pair of morphisms, there is a third morphism $g\circ f\in\mathrm{Hom}(A,C)$, called the \emph{composition} of $g$ with $f$.
\item Composition respects the identity: if $f\in\mathrm{Hom}(A, B)$, then $f\circ 1_A=1_B\circ f=f$.
\item Composition is associative: if $f\in\mathrm{Hom}(A, B)$, $g\in\mathrm{Hom}(B, C)$ and $h\in\mathrm{Hom}(C, D)$, then $h\circ(g\circ f)=(h\circ g)\circ f$.
\end{enumerate}
We define \emph{the category of generic signatures} as follows:
\begin{itemize}
\item The objects are generic signatures.
\item The morphisms are substitution maps (a technicality here is that their replacement types must not contain archetypes).
\item The source of a morphism (substitution map) is the input generic signature of the substitution map.
\item The destination of a morphism (substitution map) is the output generic signature of the substitution map.
\item The identity morphism is the identity substitution map (you will see later it does not act as the identity on archetypes, which is why we rule them out above).
\item The composition of morphisms $g\circ f$ is the composition of substitution maps $f\otimes g$ (note that we must reverse the order here for the definition to work).
\end{itemize}
Category theory often comes up in programming when working with data structures and higher-order functions; an excellent introduction to the topic is \cite{catprogrammer}. While we don't need to deal with categories in the abstract here, but we will encounter another idea from category theory, the commutative diagram, in \SecRef{type witnesses}.

\section{Building Substitution Maps}\label{buildingsubmaps}

Now that we've seen how to get substitution maps from types, and how to compose existing substitution maps, it's time to talk about building substitution maps from scratch using the two variants of the \textbf{get substitution map} operation.

\IndexDefinition{get substitution map}
\index{serialized module}
\index{conforming type}
The first variant constructs a substitution map directly from its three constituent parts: a generic signature, an array of replacement types, and an array of conformances. The arrays must have the correct length---equal to the number of generic parameters and \index{conformance requirement!type substitution}conformance requirements, respectively.
This variant of \textbf{get substitution map} is used when constructing a substitution map from a deserialized representation, because a serialized substitution map is guaranteed to satisfy the above invariants.

\IndexDefinition{replacement type callback}
\index{type variable type}
\index{type parameter}
\index{archetype type}
\IndexDefinition{query substitution map callback}
\IndexDefinition{query type map callback}
The second variant takes the input generic signature and a pair of callbacks:
\begin{enumerate}
\item The \textbf{replacement type callback} maps a generic parameter type to a replacement type. It is invoked with each generic parameter type to populate the replacement types array.
\item The \textbf{conformance lookup callback} maps a protocol conformance requirement to a conformance. It is invoked with each conformance requirement to populate the conformances array.
\end{enumerate}
The conformance lookup callback takes three parameters:
\begin{enumerate}
\item The \emph{original type}; this is the subject type of the conformance requirement.
\item The \emph{substituted type}; this is the result of applying the substitution map to the original type, which should be canonically equal to the conforming type of the conformance that will be returned.
\item The protocol declaration named by the conformance requirement.
\end{enumerate}
The callbacks can be arbitrarily defined by the caller. Several pre-existing callbacks also implement common behaviors. For the replacement type callback,
\begin{enumerate}
\item The \textbf{query substitution map} callback looks up a generic parameter in an existing substitution map.
\item The \textbf{query type map} callback looks up a generic parameter in a hashtable.
\end{enumerate}
For the conformance lookup callback,
\begin{enumerate}
\item The \textbf{global conformance lookup} callback performs a global conformance lookup (\SecRef{conformance lookup}).
\item The \textbf{local conformance lookup} callback performs a local conformance lookup into another substitution map (\SecRef{abstract conformances}).
\item The \textbf{make abstract conformance} callback asserts that the substituted type is a type variable, type parameter or archetype, and returns an abstract conformance (also in \SecRef{abstract conformances}). It is used when it is known that the substitution map can be constructed without performing any conformance lookups, as is the case with the identity substitution map.
\end{enumerate}
\IndexDefinition{conformance lookup callback}
\index{abstract conformance}
\index{global conformance lookup!substitution map}
\index{local conformance lookup}
\IndexDefinition{global conformance lookup callback}
\IndexDefinition{local conformance lookup callback}
\IndexDefinition{make abstract conformance callback}

Specialized types only store their generic arguments, not conformances, so the \index{context substitution map!construction}context substitution map of a specialized type is constructed by first populating a \texttt{DenseMap} with the generic arguments of the specialized type and all of its parent types, and then invoking the \textbf{get substitution map} operation with the \textbf{query type map} and \textbf{global conformance lookup} callbacks.

\index{identity substitution map}
The identity substitution map of a generic signature is constructed from a replacement type callback which just returns the input generic parameter together with the \textbf{make abstract conformance} callback.

\iffalse

When a subclass inherits from a superclass, there is a subtype relationship between the subclass and superclass. If neither class is generic, the relationship is straightforward. Here, we have a pair of classes \texttt{C} and \texttt{D}; \texttt{D} inherits from \texttt{C}, so instances of \texttt{D} are also instances of \texttt{C}:
\begin{Verbatim}
class C {}
class D {}

let instanceOfD: D = D()
let instanceOfC: C = instanceOfD  // okay
\end{Verbatim}
With generic classes, the situation is more subtle. The subclass \emph{declaration} states a superclass \emph{type}. The superclass type appears in the inheritance clause of the subclass, and can reference the subclass's generic parameters:
\begin{Verbatim}
class Base<T, U> {}
class Derived<A>: Base<String, A> {}
\end{Verbatim}
Now, the declaration \texttt{Derived} has the generic superclass type \texttt{Base<String, A>}. We expect that \texttt{Derived<A>} is a subtype of \texttt{Base<String, A>}, and \texttt{Derived<Int>} is a subtype of \texttt{Base<String, Int>}, but that \texttt{Derived<Int>} and \texttt{Base<String, String>} are unrelated types.

To get a complete picture of the subtype relationship, we need to define the concept of the superclass type \emph{of a type}, and not just the superclass type of a declaration.

First of all, what is the superclass type of the declared interface type of a class? The superclass type of the class declaration is an interface type for the class declaration's generic signature, so we say that the superclass type of the declared interface type is just the superclass type of the declaration. In our example, this tells us that \texttt{Derived<A>} is a subtype of \texttt{Base<String, A>} and an unrelated type to \texttt{Base<Int, A>}.

What about the superclass type of an arbitrary specialization of the class? Here, we rely on the property that a specialized type is the result of applying its context substitution map to the declared interface type. If we instead apply the context substitution map to the superclass type of the class declaration, we get the superclass type of our specialized type. This can be shown with a commutative diagram:
\begin{quote}
\begin{tikzcd}[column sep=3cm,row sep=1cm]
\mathboxed{declared interface type} \arrow[d, "\text{superclass type}"{left}] \arrow[r, "\text{substitution}"] &\mathboxed{specialized type} \arrow[d, "\text{superclass type}"] \\
\mathboxed{superclass type of declaration} \arrow[r, "\text{substitution}"]&\mathboxed{superclass type of type}
\end{tikzcd}
\end{quote}

Now that we can compute the superclass type of a type, we can walk up the inheritance hierarchy by iterating the process, to get the superclass type of a superclass type, and so on.

\begin{algorithm}[Iterated superclass type]\label{superclassfordecl} As input, takes a class type \texttt{T} and a superclass declaration \texttt{D}. Returns the superclass type of \texttt{T} for \texttt{D}.
\begin{enumerate}
\item Let \texttt{C} be the class declaration referenced by \texttt{T}. If $\texttt{C}=\texttt{D}$, return \texttt{T}.
\item If \texttt{C} does not have a superclass type, fail with an invariant violation; \texttt{D} is not actually a superclass of \texttt{T}.
\item Otherwise, apply the context substitution map of \texttt{T} to the superclass type of \texttt{C}. Assign this new type to \texttt{T}, and go back to Step~1.
\end{enumerate}
\end{algorithm}

\begin{example}\label{genericsuperclassexample}
\ListingRef{generic superclass example listing} shows a class hierarchy demonstrating these behaviors:
\begin{enumerate}
\item The superclass type of \texttt{Derived} is \texttt{Middle<Int, String>}.
\item The superclass type of \texttt{Middle} is \texttt{Base<(T, T)>}.
\end{enumerate}
The superclass type of the type \texttt{Middle<Int, String>} is the superclass type of \texttt{Middle} with the context substitution map of \texttt{Middle<Int, String>} applied:
\[\texttt{Base<(T, T)>}\otimes
\SubstMap{
\SubstType{T}{Int}\\
\SubstType{U}{String}
} = \texttt{Base<(Int, Int)>}
\]
This means the superclass type of \texttt{Derived} with respect to \texttt{Base} is \texttt{Base<(Int, Int)>}.

What is the type \texttt{Derived.C}? The type alias \texttt{C} is declared in \texttt{Base}. The superclass type of \texttt{Derived} with respect to \texttt{Base} is \texttt{Base<(Int, Int)>}. We can apply the context substitution map of this superclass type to the declared interface type of \texttt{C}:
\[\texttt{() -> T}\otimes
\SubstMap{
\SubstType{T}{(Int, Int)}
} = \texttt{() -> (Int, Int)}
\]
\end{example}

\fi

\section{Nested Nominal Types}\label{nested nominal types}

Nominal type declarations can appear \index{nested type declaration}inside other declaration contexts, subject to the following \index{limitation!nested type declarations}restrictions:
\begin{enumerate}
\item Structs, enums and classes cannot be nested in generic \index{local declaration context}local contexts.
\item Structs, enums and classes cannot be nested in protocols or \index{protocol extension}protocol extensions.
\item Protocols cannot be nested in generic contexts.
\end{enumerate}
We're going to explore the implementation limitations behind these restrictions, and possible future directions for lifting them. (The rest of the book talks about what the compiler does, but this section is about what the compiler \emph{doesn't} do.)

\paragraph{Types in generic local contexts.} \index{local declaration context}\index{local type declaration}This restriction is a consequence of a shortcoming in the representation of a nominal type. Recall from \ChapRef{types} that nominal types and generic nominal types store a parent type, and generic nominal types additionally store a list of generic arguments, corresponding to the generic parameter list of the nominal type declaration. This essentially means there is no place to store the generic arguments from outer \index{generic context}local contexts, such as functions.

\begin{listing}\captionabove{A nominal type declaration in a generic local context}\label{nominal type in generic local context}
\begin{Verbatim}
func f<T>(t: T) {
  struct Nested {  // error
    let t: T

    func printT() {
      print(t)
    }
  }
  
  Nested(t: t).printT()
}

func g() {
  f(t: 123)
  f(t: "hello")
}
\end{Verbatim}
\end{listing}

\ListingRef{nominal type in generic local context} shows a nominal type nested inside of a generic function. The generic signature of \texttt{Nested} contains the generic parameter \texttt{T} from the outer generic function \texttt{algorithm()}. However, under our rules, the declared interface type of \texttt{Nested} is a singleton nominal type, because \texttt{Nested} does not have its own generic parameter list, and its parent context is not a nominal type declaration. This means there is no way to recover a \index{context substitution map!of local type}context substitution map for this type because the generic argument for \texttt{T} is not actually stored anywhere.

In the source language, there is no way to specialize \texttt{Nested}; the reference to \texttt{T} inside \texttt{f()} is always understood to be the generic parameter \texttt{T} of the outer function. However, inside the compiler, different generic specializations can still arise. If the two calls to \texttt{f()} from inside \texttt{g()} are specialized and inlined by the SIL optimizer for example, the two temporary instances of \texttt{Nested} must have different in-memory layouts, because in one call \texttt{T} is \texttt{Int}, and in the other \texttt{T} is \texttt{String}.

A better representation for the specializations of nominal types would replace the parent type and list of generic arguments with a single ``flat'' list that includes all outer generic arguments as well. This approach could represent generic arguments coming from outer local contexts without loss of information.

\index{runtime type metadata}
Luckily, this ``flat'' representation is already implemented in the Swift runtime. The runtime type metadata for a nominal type includes all the generic parameters from the nominal type declaration's generic signature, not just the generic parameters of the nominal type declaration itself. So while lifting this restriction would require some engineering effort on the compiler side, it would be a backward-deployable and \index{ABI}ABI-compatible change.

\paragraph{Types in protocol contexts.} Allowing struct, enum and class declarations to appear inside protocols and protocol extensions would come down to deciding if the \IndexSelf protocol \tSelf\ type should be ``captured'' by the nested type.

\begin{listing}\captionabove{A nominal type declaration nested in a protocol context}\label{nominal type in protocol context}
\begin{Verbatim}
protocol P {}

extension P {
  typealias Me = Self

  struct Nested {  // error
    let value: Me  // because what would this mean?

    func method() {
      print(value)
    }
  }
  
  func f() {
    Nested(value: self).method()
  }
}

struct S1: P {}
struct S2: P {}  // are S1.Nested and S2.Nested distinct?
\end{Verbatim}
\end{listing}
If the nested type captures \tSelf, the code shown in \ListingRef{nominal type in generic local context} would become valid. With this model, the \texttt{Nested} struct depends on \tSelf, so it would not make sense to reference it as a member of the protocol itself, like \texttt{P.Nested}. Instead, \texttt{Nested} would behave as if it was a member of every \index{conforming type}conforming type, like \texttt{S.Nested} above (or even \texttt{T.Nested}, if \texttt{T} is a generic parameter conforming to \texttt{P}). At the implementation level, the generic signature of a nominal type nested inside of a protocol context would include the protocol \tSelf\ type, and the \emph{entire} parent type, for example \texttt{S} in \texttt{S.Nested}, would become the replacement type for \tSelf\ in the context substitution map.

The alternative is to prohibit the nested type from referencing the protocol \tSelf\ type. The nested type's generic signature would \emph{not} include the protocol \tSelf\ type, and \texttt{P.Nested} would be a valid member type reference. The protocol would effectively act as a namespace for the nominal types it contains, with the nested type not depending on the conformance to the protocol in any way.

\begin{listing}\captionabove{Protocol declaration nested inside other declaration contexts}\label{protocol nested inside type}
\begin{Verbatim}
struct Outer {
  protocol P {}  // allowed as of SE-0404
}

struct S: Outer.P {}

func generic<T>(_: T) {
  protocol P {  // error
    func f(_: T)  // because what would this mean?
  }
}
\end{Verbatim}
\end{listing}

\paragraph{Protocols in other declaration contexts.} The final possibility is the nesting of protocols inside other declaration contexts, such as functions or nominal types. This breaks down into two cases, illustrated in \ListingRef{protocol nested inside type}:
\begin{enumerate}
\item Protocols inside non-generic declaration contexts.
\item Protocols inside generic declaration contexts.
\end{enumerate}
The first case was originally prohibited, but is now permitted as of \IndexSwift{5.a@5.10}Swift~5.10 \cite{se0404}; the non-generic declaration context acts as a namespace to which the protocol declaration is scoped, but apart from the interaction with name lookup this has no other semantic consequences. The second case is more subtle. If we were to allow a ``generic protocol'' to be parameterized by its outer generic parameters in addition to just the protocol \IndexSelf\tSelf\ type, we would get what \index{Haskell}Haskell calls a \index{multi-parameter type class}``multi-parameter type class.'' Multi-parameter type classes introduce some complications, for example undecidable type inference~\cite{mptc}.

\section{Reabstraction Thunks}

\begin{example}
Unbounded space usage example
\index{limitation!reabstraction thunks}
\end{example}

This is not the whole story; the representation of SIL function type is more elaborate \cite{substfunctype}.

\section{Source Code Reference}\label{substmapsourcecoderef}

Key source files:
\begin{itemize}
\item \SourceFile{include/swift/AST/SubstitutionMap.h}
\item \SourceFile{lib/AST/SubstitutionMap.cpp}
\item \SourceFile{lib/AST/TypeSubstitution.cpp}
\end{itemize}
Other source files:
\begin{itemize}
\item \SourceFile{include/swift/AST/GenericSignature.h}
\item \SourceFile{include/swift/AST/Type.h}
\item \SourceFile{include/swift/AST/Types.h}
\end{itemize}

\IndexSource{type substitution}
\apiref{Type}{class}
See also \SecRef{typesourceref}.
\begin{itemize}
\item \texttt{subst()} applies a substitution map to this type and returns the substituted type.
\end{itemize}

\IndexSource{context substitution map}
\apiref{TypeBase}{class}
See also \SecRef{typesourceref} and \SecRef{genericsigsourceref}.
\begin{itemize}
\item \texttt{getContextSubstitutionMap()} returns this type's context substitution map.
\end{itemize}

\IndexSource{substitution map}
\IndexSource{input generic signature}
\IndexSource{empty substitution map}
\IndexSource{substitution map composition}
\apiref{SubstitutionMap}{class}
Represents an immutable, uniqued substitution map. See also \SecRef{conformancesourceref}.

\paragraph{Canonical substitution maps.}
\IndexDefinition{canonical substitution map}%
\index{canonical type}%
\index{canonical conformance}%
\IndexDefinition{substitution map equality}%
Substitution maps are immutable and uniqued, just like types and generic signatures. A substitution map is canonical if all replacement types are canonical types and all conformances are canonical conformances. A substitution map is canonicalized by constructing a new substitution map from the original substitution map's canonicalized replacement types and conformances.

As with types, canonicalization gives substitution maps two levels of equality; two substitution maps are equal pointers if their replacement types and conformances are equal pointers. Two substitution maps are canonically equal if their canonical substitution maps are equal pointers; or equivalently, if their replacement types and conformances are canonically equal.

Applying a canonical substitution map to a canonical original type is not guaranteed to produce a canonical substituted type. However, there are two important invariants that do hold:
\begin{enumerate}
\item Given two canonically equal original types, applying the same substitution map to both will produce two canonically equal substituted types.
\item Given an original type and two canonically equal substitution maps, applying the two substitution maps to this type will also produce two canonically equal substituted types.
\end{enumerate}

As with \texttt{Type} and \texttt{GenericSignature}, this class stores a single pointer, so substitution maps are cheap to pass around as values. The default constructor \texttt{SubstitutionMap()} constructs an empty substitution map. The implicit \texttt{bool} conversion tests for a non-empty substitution map.

\IndexSource{substitution map equality}
The overload of \texttt{operator==} implements substitution map pointer equality. Canonical equality can be tested by first canonicalizing both sides:
\begin{Verbatim}
if (subMap1.getCanonical() == subMap2.getCanonical())
  ...;
\end{Verbatim}

\index{primary archetype}
\index{opened archetype}
\Index{dynamic Self type@dynamic \tSelf\ type}
\IndexSource{canonical substitution map}
Accessor methods:
\begin{itemize}
\item \texttt{empty()} answers if this is the empty substitution map; this is the logical negation of the \texttt{bool} implicit conversion.
\item \texttt{getGenericSignature()} returns the substitution map's input generic signature.
\item \texttt{getReplacementTypes()} returns an array of \texttt{Type}.
\item \texttt{hasAnySubstitutableParams()} answers if the input generic signature contains at least one generic parameter not fixed to a concrete type; that is, it must be non-empty and not fully concrete (see the \texttt{areAllParamsConcrete()} method of \texttt{GenericSignatureImpl} from \SecRef{genericsigsourceref}).
\end{itemize}
Recursive properties computed from replacement types:
\begin{itemize}
\item \texttt{hasArchetypes()} answers if any of the replacement types contain a primary archetype or opened existential archetype.
\item \texttt{hasOpenedExistential()} answers if any of the replacement types contain an opened existential archetype.
\item \texttt{hasDynamicSelf()} answers if any of the replacement types contain the dynamic Self type.
\end{itemize}
Canonical substitution maps:
\begin{itemize}
\item \texttt{isCanonical()} answers if the replacement types and conformances stored in this substitution map are canonical.
\item \texttt{getCanonical()} constructs a new substitution map by canonicalizing the replacement types and conformances of this substitution map.
\end{itemize}
Composing substitution maps (\SecRef{submapcomposition}):
\begin{itemize}
\item \texttt{subst()} applies another substitution map to this substitution map, producing a new substitution map.
\end{itemize}
Two overloads of the \texttt{get()} static method are defined for constructing substitution maps (\SecRef{buildingsubmaps}).
\IndexSource{get substitution map}

\medskip
\noindent
\texttt{get(GenericSignature, ArrayRef<Type>, ArrayRef<ProtocolConformanceRef>)}\newline builds a new substitution map from an input generic signature, an array of replacement types, and array of conformances.

\medskip
\noindent
\texttt{get(GenericSignature, TypeSubstitutionFn, LookupConformanceFn)} builds a new substitution map by invoking a pair of callbacks to produce each replacement type and conformance.

\IndexSource{replacement type callback}
\apiref{TypeSubstitutionFn}{type alias}
The type signature of a replacement type callback for \texttt{SubstitutionMap::get()}.
\begin{verbatim}
using TypeSubstitutionFn
  = llvm::function_ref<Type(SubstitutableType *dependentType)>;
\end{verbatim}
The parameter type is always a \texttt{GenericTypeParamType *} when the callback is used with \texttt{SubstitutionMap::get()}.

\IndexSource{query substitution map callback}
\apiref{QuerySubstitutionMap}{struct}
A callback intended to be used with \texttt{SubstitutionMap::get()} as a replacement type callback.
Overloads \texttt{operator()} with the signature of \texttt{TypeSubstitutionFn}.

Constructed from a \texttt{SubstitutionMap}:
\begin{Verbatim}
QuerySubstitutionMap{subMap}
\end{Verbatim}

\IndexSource{query type map callback}
\apiref{QueryTypeSubstitutionMap}{struct}
A callback intended to be used with \texttt{SubstitutionMap::get()} as a replacement type callback.
Overloads \texttt{operator()} with the signature of \texttt{TypeSubstitutionFn}.

Constructed from an LLVM \texttt{DenseMap}:
\begin{Verbatim}
DenseMap<SubstitutableType *, Type> typeMap;

QueryTypeSubstitutionMap{typeMap}
\end{Verbatim}

\IndexSource{conformance lookup callback}
\apiref{LookupConformanceFn}{type alias}
The type signature of a conformance lookup callback for \texttt{SubstitutionMap::get()}.
\begin{verbatim}
using LookupConformanceFn = llvm::function_ref<
    ProtocolConformanceRef(CanType origType,
                           Type substType,
                           ProtocolDecl *conformedProtocol)>;
\end{verbatim}

\IndexSource{global conformance lookup callback}
\apiref{LookUpConformanceInModule}{struct}
A callback intended to be used with \texttt{SubstitutionMap::get()} as a conformance lookup callback. Overloads \texttt{operator()} with the signature of \texttt{LookupConformanceFn}.

Performs a global conformance lookup. Constructed without arguments:
\begin{Verbatim}
LookUpConformanceInModule()
\end{Verbatim}

\IndexSource{local conformance lookup callback}
\apiref{LookUpConformanceInSubstitutionMap}{struct}
A callback intended to be used with \texttt{SubstitutionMap::get()} as a conformance lookup callback. Overloads \texttt{operator()} with the signature of \texttt{LookupConformanceFn}.

Constructed with a \texttt{SubstitutionMap}:
\begin{Verbatim}
LookUpConformanceInSubstitutionMap{subMap}
\end{Verbatim}

\IndexSource{make abstract conformance callback}
\apiref{MakeAbstractConformanceForGenericType}{struct}
A callback intended to be used with \texttt{SubstitutionMap::get()} as a conformance lookup callback. Overloads \texttt{operator()} with the signature of \texttt{LookupConformanceFn}.

Constructed without arguments:
\begin{Verbatim}
MakeAbstractConformanceForGenericType()
\end{Verbatim}

\apiref{GenericSignature}{class}
See also \SecRef{genericsigsourceref}.

\begin{itemize}
\item \texttt{getIdentitySubstitutionMap()} returns the \IndexSource{identity substitution map}substitution map that replaces each \IndexSource{generic signature!type substitution}generic parameter with itself.
\end{itemize}

\end{document}