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

\documentclass[../generics]{subfiles}

\begin{document}

\chapter{Substitution Maps}\label{chap:substitution maps}

\lettrine{S}{ubstitution maps} are the semantic objects that describe \emph{references} to generic declarations. If we think of a generic signature as a \emph{contract} between a declaration and its client, then the previous chapter's derived requirements formalism gave us one side of this contract: within the \emph{body} of a generic declaration, we start from the assumption that the concrete replacement types, whatever they might be, must satisfy the generic signature's explicit requirements, and from this, we derive various consequences which then hold. In this chapter, we turn our attention to the client's side of this contract, which leads to the study of \emph{type substitution}.

\paragraph{Input generic signature.}
The ``shape'' of a substitution map is determined by its \IndexDefinition{input generic signature}\emph{input generic signature}. In this chapter, we will primarily focus on the simplest case, where this generic signature has no requirements, but we will summarize the general case shortly. Subsequent chapters will explain how requirements interact with substitution.

\begin{example}
Let's look at this generic function, and think about its callers:
\begin{Verbatim}
func combine<T, U>(_ t: T, _ u: U) -> (T, Array<U>) {
  return (t, [u])
}
\end{Verbatim}
Our generic signature has two generic parameters and no requirements. Let's call it $G$:
\[G := \texttt{<T, U>}, \qquad \text{or} \qquad \texttt{<\rT, \rU>}.\]
Suppose we call our function with these two values; what is the type of the result?
\begin{Verbatim}
let t: Optional<Int> = 3
let u: String = "Hello world"

let result = combine(t, u)  // what is the return type of this call?
\end{Verbatim}
By matching the function's declared parameter types against the types of the argument expressions, the \index{expression type checker}expression type checker can deduce that \tT~must be \texttt{Optional<Int>}, and also that \tU~must be \texttt{String}. This gives us our substitution map; let's call it $\Sigma$:
\begin{align*}
\Sigma := \{&\SubstType{\rT}{Optional<Int>},\\
&\SubstType{\rU}{String}\}
\end{align*}
Our notation for specifying a substitution map lists the \IndexDefinition{replacement type}replacement type for each generic parameter of its input generic signature, in order. Type substitution disregards \index{sugared type}type sugar, and to remind ourselves of this fact, we write the canonical generic parameter type on the left-hand side of the ``$\mapsto$'' symbol. We often name our substitution maps $\Sigma$ or some variation, like $\Sigma_1$, $\Sigma_2$, $\Sigma^\prime$, and so on.

Recall from \ChapRef{chap:types} that types have a tree structure, so the two replacement types in our substitution map~$\Sigma$ have an in-memory form that looks something like this:
\begin{center}
\begin{tikzpicture}[node distance=0.5cm, baseline={([yshift=-2pt]OptionalInt)}]
\node (OptionalInt) [type] {\texttt{Optional<Int>}};

\node (Int) [type, below=of OptionalInt] {\texttt{\vphantom{y}Int}};

\draw [arrow] (OptionalInt) -- (Int);
\end{tikzpicture}\;,
\quad and \quad
\begin{tikzpicture}[node distance=0.5cm, baseline={([yshift=-2pt]String)}]
\node (String) [type] {\texttt{String}};
\end{tikzpicture}\;.
\end{center}
Now, to figure out the inferred type of ``\texttt{result},'' we note that our function's declared return type is the \index{tuple type}tuple type \texttt{(\rT, Array<\rU>)}. Let's call this the \emph{original type}. This type contains the generic parameters of~$G$. To get the \emph{substituted type}, we replace each occurrence of \rT\ and \rU\ in the original type with its replacement type. We conclude that the substituted type is \texttt{(Optional<Int>, Array<String>)}. \FigRef{subst fig} illustrates the transformation.
\end{example}

\begin{figure}\captionabove{Type substitution}\label{subst fig}
\begin{center}
\begin{tabular}{ccc}
\textbf{Original type:}&&\textbf{Substituted type:}\\[\medskipamount]
\begin{tikzpicture}[baseline={([yshift=-3pt]Tuple)}]
\node (Tuple) [type] {\texttt{(\rT, Array<\rU>)}};

\node (T) [type, fill=light-gray, below=of Tuple, xshift=-38] {\texttt{\vphantom{y}}\rT};

\node (ArrayU) [type, below=of Tuple, xshift=38] {\texttt{Array<\rU>}};

\node (U) [type, fill=light-gray, below=of ArrayU] {\texttt{\vphantom{y}}\rU};

\draw [arrow] (Tuple) -- (T);
\draw [arrow] (Tuple) -- (ArrayU);
\draw [arrow] (ArrayU) -- (U);
\end{tikzpicture}&
{\Large $\Rightarrow$}&
\begin{tikzpicture}[baseline={([yshift=-3pt]TupleSubst)}]
\node (TupleSubst) [type, xshift=30] {\texttt{(Optional<Int>, Array<String>)}};

\node (OptionalInt) [type, below=of TupleSubst, xshift=-50] {\texttt{Optional<Int>}};

\node (Int) [type, below=of OptionalInt] {\texttt{\vphantom{y}Int}};

\node (ArrayString) [type, below=of TupleSubst, xshift=50] {\texttt{Array<String>}};

\node (String) [type, below=of ArrayString] {\texttt{String}};

\draw [arrow] (TupleSubst) -- (OptionalInt);
\draw [arrow] (OptionalInt) -- (Int);
\draw [arrow] (TupleSubst) -- (ArrayString);
\draw [arrow] (ArrayString) -- (String);
\end{tikzpicture}
\end{tabular}
\end{center}
\end{figure}

This operation is called \emph{type substitution}. We will introduce some notation to talk about it first, before we look at the formal algorithm. With $\Sigma$ as above, we denote this type substitution operation as follows, with the original type on the left of the $\otimes$ operator, and the substitution map on the right:
\[
\texttt{(\rT, Array<\rU>)} \otimes \Sigma = \texttt{(Optional<Int>, Array<String>)}
\]
The above example showed one way to ``observe'' type substitution: we write down a generic function declaration, call it with some list of generic argument types, and then look at the return type of the call. Here is another similar trick.

\begin{example}
Consider \index{type resolution}type resolution with a \index{generic type alias!type substitution}generic type alias:
\begin{Verbatim}
typealias Foo<T, U> = (T, Array<U>)

let x: Foo<Optional<Int>, String> = ...
\end{Verbatim}
Here, we're referencing \texttt{Foo} with the same generic arguments as before, so we get the same substitution map~$\Sigma$. To resolve the type annotation on ``\texttt{x}'', we apply $\Sigma$ to the \index{underlying type!type substitution}underlying type of \texttt{Foo}:
\[
\texttt{(\rT, Array<\rU>)} \otimes \Sigma = \texttt{(Optional<Int>, Array<String>)}
\]
Since the underlying type of the alias and the generic arguments of a reference are both arbitrary, we can use generic type aliases to encode any type substitution operation. We will discuss type resolution of generic type aliases in \SecRef{identtyperepr} and \SecRef{member type repr}.
\end{example}

\paragraph{Output generic signature.}
In our examples so far, the replacement types in the substitution map were \index{fully-concrete type}fully concrete. To observe a substitution map whose replacement types contain type parameters, we can reference a generic declaration from the body of some other generic declaration. We say that a generic signature $H$ is the \IndexDefinition{output generic signature}\emph{output generic signature} of a substitution map $\Sigma$ if all type parameters that appear in the replacement types of $\Sigma$ are valid type parameters of~$H$.

\begin{example}
In the following, the generic \texttt{callee()} function is referenced from the body of \texttt{caller()}:
\begin{Verbatim}
func callee<T>(_ value: T) -> Array<T> {
  return [value]
}

func caller<X, Y>(_ x: X, y: Y) -> Array<(X, Y)> {
  return callee((x, y))  // call here
}
\end{Verbatim}
The call expression passes in a tuple value as the argument, so the replacement type for \rT\ is the tuple type \texttt{(\rT, \rU)}:
\begin{center}
\begin{tikzpicture}[node distance=0.5cm, baseline={([yshift=-2pt]OptionalInt)}]
\node (Tuple) [type] {\texttt{(\rT, \rU)}};

\node (T) [type, fill=light-gray, below=of Tuple, xshift=-40] {\texttt{\vphantom{y}}\rT};
\node (U) [type, fill=light-gray, below=of Tuple, xshift=40] {\texttt{\vphantom{y}}\rU};

\draw [arrow] (Tuple) -- (T);
\draw [arrow] (Tuple) -- (U);
\end{tikzpicture}
\end{center}
Our input generic signature is the generic signature of \texttt{callee()}:
\[ G := \texttt{<\rT>} \]
Our output generic signature is the generic signature of \texttt{caller()}:
\[ H := \texttt{<\rT, \rU>} \]
Here is the substitution map:
\[ \Sigma := \{ \SubstType{\rT}{(\rT, \rU)} \} \]
Now, we apply $\Sigma$ to the return type of \texttt{callee()} to get the substituted type:
\[ \texttt{Array<\rT>} \otimes \Sigma = \texttt{Array<(\rT, \rU)>} \]
\FigRef{subst fig output sig} illustrates the transformation.
\end{example}

\begin{figure}\captionabove{Type substitution with output generic signature}\label{subst fig output sig}
\begin{center}
\begin{tabular}{ccc}
\textbf{Original type:}&&\textbf{Substituted type:}\\[\medskipamount]
\begin{tikzpicture}[baseline={([yshift=-3pt]ArrayT)}]
\node (ArrayT) [type] {\texttt{Array<\rT>}};

\node (T) [type, fill=light-gray, below=of ArrayT] {\texttt{\vphantom{y}}\rT};

\draw [arrow] (ArrayT) -- (T);
\end{tikzpicture}&
{\Large $\Rightarrow$}&
\begin{tikzpicture}[baseline={([yshift=-3pt]ArrayTuple)}]
\node (ArrayTuple) [type] {\texttt{Array<(\rT, \rU)>}};

\node (Tuple) [type, below=of ArrayTuple] {\texttt{(\rT, \rU)}};

\node (T) [type, fill=light-gray, below=of Tuple, xshift=-40] {\texttt{\vphantom{y}}\rT};

\node (U) [type, fill=light-gray, below=of Tuple, xshift=40] {\texttt{\vphantom{y}}\rU};

\draw [arrow] (ArrayTuple) -- (Tuple);
\draw [arrow] (Tuple) -- (T);
\draw [arrow] (Tuple) -- (U);
\end{tikzpicture}
\end{tabular}
\end{center}
\end{figure}

Next, we introduce a bit of notation to formalize a concept we've already seen:
\begin{definition}\label{interface type def}
Let $G$ be a generic signature. We write \IndexSetDefinition{type}{\TypeObj{G}}$\TypeObj{G}$ to denote the \index{set!types}set of \IndexDefinition{interface type}interface types of $G$. In particular, this set contains the following:
\begin{itemize}
\item All \index{valid type parameter!interface type}valid type parameters of $G$.
\item All \index{nominal type}nominal types, formed from the non-generic nominal type declarations.
\item All \index{generic nominal type}generic nominal types, formed from the generic nominal type declarations and all combinations of generic arguments from $\TypeObj{G}$.
\item All \index{structural type}structural types---such as \index{function type}function types, \index{tuple type}tuple types, and \index{metatype type}metatypes---formed from the elements of $\TypeObj{G}$.
\end{itemize}
\end{definition}

We can also talk about the set of all substitution maps that map the interface types of one fixed generic signature into another:
\begin{definition}
Let $G$ and $H$ be generic signatures. We write \IndexSetDefinition{sub}{\SubMapObj{G}{H}}$\SubMapObj{G}{H}$ to denote the set of all substitution maps that have input generic signature~$G$ and output generic signature~$H$.
\end{definition}

These are \index{infinite set}infinite sets, so we do not realize them in the implementation. Instead, we use them as a notational aid to understand type substitution. An important and subtle point is that the output generic signature is not stored in the substitution map itself; it is implicit from usage. Thus, we must take care not to get our output generic signatures ``mixed up'' by keeping the relationships between these sets in mind.

Suppose we are given a $\Sigma\in\SubMapObj{G}{H}$. Note that the replacement types of $\Sigma$ are elements of $\TypeObj{H}$, and furthermore, if we take some $\tX\in\TypeObj{G}$ and replace each type parameter that occurs in \tX\ with an element of $\TypeObj{H}$, the transformed type will then also be an element of $\TypeObj{H}$. In particular, $\tX\otimes\Sigma\in\TypeObj{H}$, and we can think of type substitution as the following mapping between sets:
\[\TypeObj{G}\otimes\SubMapObj{G}{H}\longrightarrow\TypeObj{H}\]
We model type substitution a binary operation on types and substitution maps, instead of using an ``applicative'' notation like ``$\Sigma(\tT)$'' where the substitution map is represented as a unary function. The reason for this will soon become clear, when we encounter additional forms of the \index{$\otimes$}\index{$\otimes$!z@\igobble|seealso{type substitution}}\index{binary operation}$\otimes$ operator that allow us to write down more complex expressions. The different forms of $\otimes$ will be related by various identities, which will define the \emph{type substitution algebra}.

The below algorithm for \IndexDefinition{type substitution}type substitution formalizes the structural transformation we saw earlier. It also calls out to a handful of subroutines to handle the dependent member type and archetype cases, which we will fill out later.

\begin{algorithm}[Substitute type]\label{type subst algo}
Takes a type \tX, and a substitution map $\Sigma$ with input generic signature $G$. Outputs $\tX\otimes\Sigma$.
\begin{enumerate}
\item (Type parameter) If \tX\ is a type parameter \tT:
\begin{enumerate}
\item If $\Query{isValidTypeParameter}{G,\,\tT}$ is false, return the \index{error type}error type.
\item If \tT\ is a generic parameter type, return the replacement type for \tT\ in~$\Sigma$.
\item If \tT\ is a dependent member type, apply \AlgRef{dependent member type substitution}, and return the result.
\end{enumerate}
\item (Archetype) If \tX\ is a \index{primary archetype!type substitution}primary archetype $\archetype{T}_G$, return $\tT \otimes \Sigma$ (\SecRef{archetypesubst}). If \tX\ is an opaque archetype, call \AlgRef{opaquearchetypesubst}. If \tX\ is existential, call \AlgRef{existential archetype subst}.
\item (Base case) If \tX\ does not contain type parameters or archetypes: return \tX.
\item (Recurse) Apply $\Sigma$ to each child of \tX\ recursively, and form a new type from these substituted child types, preserving any non-type structural components of \tX.
\end{enumerate}
\end{algorithm}

\begin{figure}\captionabove{Type substitution with dependent member type}\label{subst fig dmt}
\begin{center}
\begin{tabular}{ccc}
\textbf{Original type:}&&\textbf{Substituted type:}\\[\medskipamount]
\begin{tikzpicture}[baseline={([yshift=-3pt]ArrayTElement)}]
\node (ArrayTElement) [type] {\texttt{Array<\rT.Element>}};

\node (TElement) [type, fill=light-gray, below=of ArrayTElement] {\texttt{\vphantom{y}\rT.Element}};

\node (T) [type, fill=light-gray, below=of TElement]  {\texttt{\vphantom{y}}\rT};

\draw [arrow] (ArrayTElement) -- (TElement);
\draw [arrow] (TElement) -- (T);

\begin{scope}[on background layer]
  \node (Foo)[fit=(TElement) (T), inner sep=5pt, rounded corners, draw=gray, dashed] {};
\end{scope}

\end{tikzpicture}&
{\quad \Large $\Rightarrow$}&
\begin{tikzpicture}[baseline={([yshift=-3pt]ArrayTuple)}]
\node (ArrayInt) [type] {\texttt{Array<Int>}};

\node (Int) [type, below=of ArrayInt] {\texttt{\vphantom{y}Int}};

\draw [arrow] (ArrayInt) -- (Int);
\end{tikzpicture}
\end{tabular}
\end{center}
\end{figure}

\paragraph{Dependent member types.}
If a generic signature states \index{conformance requirement!type substitution}conformance requirements to protocols with associated types, the generic signature's \index{valid type parameter}valid type parameters also include all \index{dependent member type!type substitution}dependent member types \index{derived requirement}derived from these conformance requirements, in addition to the generic parameters stated in the generic signature.
\begin{Verbatim}
func extract<S: Sequence>(_ s: S) -> Array<S.Element> {...}
let mySet: Set<Int> = [1, 2, 3]
let x = extract(mySet)
\end{Verbatim}
A substitution map records a \index{root conformance}\emph{root conformance} for each conformance requirement of its \index{input generic signature!conformance requirement}input generic signature. In the call to \texttt{extract()}, the substitution map is:
\begin{align*}
\Sigma := \{&\SubstType{\rT}{Set<Int>},\\
&\SubstConf{\rT}{Set<Int>}{Sequence}\}
\end{align*}
Type substitution treats a dependent member type as an indivisible atomic element, and replaces it in one shot with a substituted type. (We do not recurse into the base type.) In \SecRef{abstract conformances}, we will see that the substituted type is computed from one of the conformances stored in the substitution map. We leave this unexplained for now:
\[ \texttt{Array<\rT.Element>} \otimes \Sigma = \texttt{Array<Int>} \]
\FigRef{subst fig dmt} illustrates the transformation.

\paragraph{Archetypes.} In \ChapRef{chap:archetypes}, we will meet \index{archetype type}\emph{archetypes}, an alternate representation which combines a type parameter with a generic signature. There are three kinds of archetype. A \emph{primary} archetype acts like the type parameter it represents, as far as type substitution is concerned. Substitution of \emph{opaque} and \emph{existential} archetypes is different, and will be described in \SecRef{opaquearchetype} and \SecRef{open existential archetypes}.

\paragraph{Substitution failure.}
Type substitution outputs an error type if the original type contains a type parameter that is not valid in the substitution map's input generic signature. Type substitution might also produce an error type if the substitution map's replacement types contain error types, or if one of the conformances stored in the substitution map is invalid. This is called \IndexDefinition{substitution failure}\emph{substitution failure}, and it indicates an error was diagnosed elsewhere in the user's program. The compiler does not proceed to \index{SILGen}SILGen if errors were diagnosed, and so error types should not appear after type checking.

\paragraph{Other requirements.}
Conformance requirements are special, because a substitution map directly records how it fulfills each conformance requirement. Other requirements are instead conditions to check. For example, if the input generic signature states a \index{same-type requirement!type substitution}same-type requirement, then a substitution map for this generic signature must \emph{satisfy} this requirement, in the sense that applying the substitution map to both sides should produce canonically equal substituted types. A substitution map is \emph{well-formed} if it satisfies all derived requirements of its input generic signature. We will discuss the algorithm for checking if requirements are satisfied in \SecRef{checking generic arguments}.

\section{Nominal Types}\label{contextsubstmap}

We're now going to look at the relationship between nominal type declarations, nominal types, and substitution maps. Consider these declarations:
\begin{Verbatim}
struct Bacon<T, U> {
  struct Lettuce<V> {
    struct Tomato {
      var t: T
      var u: U
      var v: V
    }
  }
}
\end{Verbatim}
(We will discuss the stored properties of \texttt{Tomato} shortly.) Given these declarations, we can then write down various nominal types, for example the type of ``\texttt{x}'' below:
\begin{Verbatim}
let x: Bacon<Int, Bool>.Lettuce<Float>.Tomato = ...
\end{Verbatim}
In the implementation, \texttt{Bacon<Int, Bool>} is classified as a \index{generic nominal type}generic nominal type, while both \texttt{Int} and \texttt{Bacon<Int, Bool>.Lettuce<Float>.Tomato} are ``just'' \index{nominal type}nominal types. However, the latter's \index{parent type}\emph{parent} is a generic nominal type. We say that a \IndexDefinition{specialized type}\emph{specialized type} is a nominal type that is either itself generic, or has a generic parent. Equivalently, a nominal type is specialized if its declaration has a non-empty generic signature.

\begin{figure}[b!]\captionabove{Applying the context substitution map}\label{context sub map fig}
\begin{center}
\begin{tabular}{c}
\textbf{Declared interface type:}\\[\medskipamount]
\begin{tikzpicture}[node distance=0.4cm]
\node (Tomato) [type] {\texttt{\vphantom{y}Bacon<\rT, \rU>.Lettuce<\ttgp{1}{0}>.Tomato}};

\node (Lettuce) [type, below=of Tomato] {\texttt{\vphantom{y}Bacon<\rT, \rU>.Lettuce<\ttgp{1}{0}>}};

\node (Bacon) [type, below=of Lettuce] {\texttt{\vphantom{y}Bacon<\rT, \rU>}};
\node (V) [type, fill=light-gray, right=of Lettuce, xshift=20pt] {\texttt{\vphantom{y}\ttgp{1}{0}}};

\node (Dummy) [left=of Lettuce, xshift=-20pt] {\texttt{\phantom{Float}}};

\node (U) [type, fill=light-gray, below=of V] {\texttt{\vphantom{y}\rT}};
\node (T) [type, fill=light-gray, below=of U] {\texttt{\vphantom{y}\rU}};

\draw [arrow] (Tomato) -- (Lettuce);
\draw [arrow] (Lettuce) -- (Bacon);
\draw [arrow] (Lettuce) -- (V);

\draw [arrow] (Bacon) -- (U);
\draw [arrow] (Bacon.east) ++ (0, -0.1) -- ++ (0.5, 0) |- (T);
\end{tikzpicture}\\
\textbf{Specialized type:}\\[\medskipamount]
\begin{tikzpicture}[node distance=0.4cm]
\node (Tomato) [type] {\texttt{\vphantom{y}Bacon<Int, Bool>.Lettuce<Float>.Tomato}};

\node (Lettuce) [type, below=of Tomato] {\texttt{\vphantom{y}Bacon<Int, Bool>.Lettuce<Float>}};

\node (Bacon) [type, below=of Lettuce] {\texttt{\vphantom{y}Bacon<Int, Bool>}};
\node (Float) [type, right=of Lettuce, xshift=28pt] {\texttt{\vphantom{y}Float}};

\node (Dummy) [left=of Lettuce, xshift=-28pt] {\texttt{\phantom{Float}}};

\node (Int) [type, below=of Float] {\texttt{\vphantom{y}Int}};
\node (Bool) [type, below=of Int] {\texttt{\vphantom{y}Bool}};

\draw [arrow] (Tomato) -- (Lettuce);
\draw [arrow] (Lettuce) -- (Bacon);
\draw [arrow] (Lettuce) -- (Float);

\draw [arrow] (Bacon) -- (Int);
\draw [arrow] (Bacon.east) ++ (0, -0.1) -- ++ (0.8, 0) |- (Bool);
\end{tikzpicture}
\end{tabular}
\end{center}
\end{figure}

If we take the \index{generic argument}generic arguments from each level of nesting in the specialized type \texttt{Bacon<Int, Bool>.Lettuce<Float>.Tomato}, we can form a substitution map for the generic signature of the declaration of \texttt{Tomato}, which is \texttt{<\rT, \rU, \ttgp{1}{0}>}:
\[
\Sigma := \SubstMap{ \SubstType{\rT}{Int},\, \SubstType{\rU}{Bool},\, \SubstType{\ttgp{1}{0}}{Float} }
\]
Recall from \ChapRef{chap:decls} that every nominal type declaration has a \index{declared interface type!nominal type declaration}declared interface type. In the case of \texttt{Tomato}, this is \texttt{Bacon<\rT, \rU>.Lettuce<\ttgp{1}{0}>.Tomato}. Now, we see that when we apply our substitution map $\Sigma$ to the declared interface type of \texttt{Tomato}, we get back our specialized type:
\begin{gather*}
\texttt{Bacon<\rT, \rU>.Lettuce<\ttgp{1}{0}>.Tomato} \otimes \Sigma \\
{} \qquad = \texttt{Bacon<Int, Bool>.Lettuce<Float>.Tomato}
\end{gather*}
We say that $\Sigma$ is the \IndexDefinition{context substitution map}\emph{context substitution map} of our specialized type. \FigRef{context sub map fig} illustrates the transformation.

\paragraph{Context substitution map.}
Suppose we have two generic signatures $G$ and $H$, and a \index{nominal type declaration!generic arguments}nominal type declaration $d$ with generic signature $G$. Let $\tXd$ denote the \index{declared interface type!nominal type declaration}declared interface type of $d$. If we are given some other specialized type formed from $d$, call it $\tX\in\TypeObj{H}$, then the context substitution map of \tX\ is the unique substitution map $\Sigma\in\SubMapObj{G}{H}$ that satisfies the identity:
\[ \tXd \otimes \Sigma = \tX \]
The context substitution map is more than just a mathematical trick, because it explains the type of a \index{member reference expression}member reference expression like ``\texttt{foo.bar}''. Recall that \texttt{Tomato} declared three stored properties named \texttt{t}, \texttt{u}, and \texttt{v}, with interface types \rT, \rU, and \ttgp{1}{0}, respectively. Consider this snippet:
\begin{Verbatim}
let x: Bacon<Int, Bool>.Lettuce<Float>.Tomato = ...
let xt = x.t
let xu = x.u
let xv = x.v
\end{Verbatim}
To deduce the inferred types of \texttt{xt}, \texttt{xu}, and \texttt{xv}, we can apply our substitution map~$\Sigma$ to the interface type of each stored property:
\begin{gather*}
\rT \otimes \Sigma = \texttt{Int}\\
\rU \otimes \Sigma = \texttt{Bool}\\
\ttgp{1}{0} \otimes \Sigma = \texttt{Float}
\end{gather*}

\paragraph{Identity substitution map.}
What is the context substitution map of $\tXd$, the declared interface type of $d$? If $\Sigma$ satisfies $\tXd = \tXd \otimes \Sigma$, then in particular, $\Sigma$ replaces every generic parameter of $G$ with itself. We call this the \IndexDefinition{identity substitution map}\emph{identity substitution map} for~$G$ and we denote it by~\index{$1_G$}\index{$1_G$!z@\igobble|seealso{identity substitution map}}$1_G$. Note that $1_G \in \SubMapObj{G}{G}$. For example, if $G$ is the generic signature of \texttt{Tomato} from the above, then:
\[
1_G := \SubstMap{\SubstType{\rT}{\rT},\,\SubstType{\rU}{\rU},\,\SubstType{\ttgp{1}{0}}{\ttgp{1}{0}}}
\]
If $G$ states one or more conformance requirements, the identity substitution map for~$G$ will also record a series of \index{abstract conformance!identity substitution map}\emph{abstract conformances} corresponding to each conformance requirement in $G$. This ensures that applying $1_G$ to a \index{dependent member type!identity substitution map}dependent member type leaves it unchanged. We will discuss abstract conformances in \SecRef{abstract conformances}.

For example, if $G := \texttt{<\rT, \rU\ where \rT:~Sequence, \rU:~Sequence>}$:
\begin{align*}
1_G := \SubstMapC{&\SubstType{\rT}{\rT}}{\\
&\SubstConf{\rT}{\rT}{Sequence},\\
&\SubstConf{\rU}{\rU}{Sequence}}
\end{align*}

In general, if \tX\ is any \index{interface type!identity substitution map}interface type in $\TypeObj{G}$, then $\tX \otimes 1_G = \tX$. In other words, applying the identity substitution map to any interface type of $G$ leaves it unchanged. (This does not hold when the original type is a \index{contextual type}contextual type that contains archetypes; such a type is not an element of $\TypeObj{G}$. We will discuss archetype substitution in \SecRef{archetypesubst}, and encounter another substitution map, the \emph{forwarding substitution map}, which plays the role of the identity on contextual types.)

\paragraph{Empty substitution map.}
A nominal type declaration like \texttt{Int}, with an \index{empty generic signature}empty generic signature, only declares a single nominal type with no generic arguments. The \index{context substitution map!non-generic type}context substitution map of this type is called the \IndexDefinition{empty substitution map}\emph{empty substitution map}, because it does not store any replacement types or conformances. We denote it by $\SubstMap{}$.

This is the \emph{only} possible substitution map for the empty generic signature. If $G$ is the empty generic signature, the set of \index{interface type!empty generic signature}interface types $\TypeObj{G}$ is the set of \index{fully-concrete type}fully-concrete types that do not contain any type parameters. The empty substitution map leaves such a type unchanged, so for example, $\texttt{Int}\otimes\SubstMap{} = \texttt{Int}$.

The empty substitution map should not be confused with the identity substitution map of a non-empty generic signature. If the original type contains any type parameters whatsoever, applying the empty substitution map will replace them with \index{error type}error types:
\[\texttt{\rT.Element} \otimes \SubstMap{} = \texttt{<<error type>>}\]

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

We've seen that generic signatures and substitution maps use a flat representation that collects all outer generic parameters together, while \index{nominal type}nominal types have a recursive structure that reflects the lexical nesting of their nominal type declarations. When we build the \index{context substitution map}context substitution map for a nominal type, we must be able to translate between these two representations. In particular, we must be able to recover a generic argument for each generic parameter of the signature. This imposes some \index{limitation!nominal type nesting}restrictions on how \index{nested type declaration}nominal type declarations can nest:
\begin{enumerate}
\item Structs, enums and classes cannot nest in generic \index{local declaration context}local contexts.
\item Structs, enums and classes cannot nest in protocols or \index{protocol extension}protocol extensions.
\item Protocols cannot nest in other generic contexts.
\end{enumerate}

\paragraph{Types in generic local contexts.} This restriction stems from the fact that a nominal type declaration can only encode generic arguments for outer nominal type contexts. If the parent context of a nominal type declaration is a generic context that is not a type, the \index{local type declaration}nominal type declaration only declares a single nominal type without any generic arguments. This prevents us from being able to properly model the following code, which is rejected today:
\begin{Verbatim}
func f<T>(t: T) {
  struct Nested {  // error
    let t: T

    func printT() {
      print(t)
    }
  }
  
  Nested(t: t).printT()
}
\end{Verbatim}
The \texttt{Nested} local type declaration has a stored property of type \rT, the generic parameter of the outer declaration \texttt{f()}. However, \texttt{Nested} only declares a single nominal type, also written as \texttt{Nested}. This type does not have a parent type or any generic arguments, because it is not nested inside of another nominal type. This means we have to way to fill in the replacement type for \rT\ in the \index{context substitution map!of local type}context substitution map:
\[
\texttt{Nested} \otimes \SubstMap{\rT\mapsto\text{???}} = \texttt{Nested}
\]
If we call our function \texttt{f()} with two generic argument types, the \index{SIL optimizer}SIL optimizer may decide to specialize one or both calls to \texttt{f()}:
\begin{Verbatim}
func g() {
  f(t: 123)
  f(t: "hello")
}
\end{Verbatim}
We will form a substitution map replacing \rT\ with \texttt{Int} or \texttt{String}, respectively, and apply this substitution map to every SIL instruction appearing in the body of \texttt{f()}. To ensure the stored property access has the correct substituted type, we must be able to represent the two distinct \index{specialized type}specializations of \texttt{Nested}. Thus, we actually want the declared interface type of \texttt{Nested} must to store a generic argument for the outer generic parameter, so notionally, we want to be able to write something like:
\[
\texttt{<\rT>.Nested} \otimes \SubstMap{\SubstType{\rT}{Int}} = \texttt{<Int>.Nested}
\]
The representation of \index{runtime type metadata}runtime type metadata is already designed to store a flat list of generic arguments, just like a generic signature or substitution map. 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.} We do not allow struct, enum, and class declarations to appear inside protocols and protocol extensions today. There are two ways to lift this restriction, and they differ in whether the nominal type declaration should capture the \IndexSelf protocol \tSelf\ type. Consider this protocol, and the protocol extension that follows. Note that \texttt{Box} has a stored property of type \texttt{\rT.Contents}, because the declaration of the \texttt{Contents} associated type is visible from \texttt{Holder}'s lexical scope:
\begin{Verbatim}
protocol Holder {
  associatedtype Contents
  var contents: Contents { get }
}

extension Holder {
  struct Box {  // error today
    let contents: Contents  // depends on the outer Self
  }
  
  var box: Box {
    return Box(contents: contents)
  }
}
\end{Verbatim}
Today, we reject the nested struct \texttt{Box}, but one possible interpretation would allow this code. In this model, the declared interface type of \texttt{Box} is something like ``\texttt{\rT.Box},'' but that's not a dependent member type; it's a nominal type whose \index{parent type}parent type is a \emph{type parameter}. Every nominal type that conforms to \texttt{Holder} would gain a new member type declaration named \texttt{Box}, and the generic argument for \tSelf\ would be this parent type. That is, if we conform a type \texttt{Foo} to \texttt{Holder} and call \texttt{box()}, we would receive a value of type \texttt{Foo.Box}:
\begin{Verbatim}
struct Foo: Holder {
  typealias Contents = Int
}

let x: Foo.Box = Foo.box(123)  // imaginary
\end{Verbatim}
The context substitution map of \texttt{Foo.Box} would then be the \index{protocol substitution map}protocol substitution map of the conformance:
\[
\texttt{\rT.Box} \otimes \SubstMapC{\SubstType{\rT}{Foo}}{\SubstConf{\rT}{Foo}{Holder}} = \texttt{Foo.Box}
\]
In this model, it would not make sense to reference \texttt{Box} as a member of the protocol itself; that is, \texttt{Holder.Box} would not be valid.

The alternative would prohibit the nested type declaration from capturing the protocol \tSelf\ type. In this case, the nested type declaration's generic signature would \emph{not} include the protocol \tSelf\ type, so \texttt{Box} would be disallowed as written above, because of its stored property. In this model, the protocol would simply act as a namespace, and the nested type would not depend on the protocol in any other way. a nested type could then be referenced as a member of the protocol type itself, like \texttt{Holder.Box}.

\paragraph{Protocols in generic contexts.} 
Historically, protocols could only be declared at the top level of a source file. In \IndexSwift{5.a@5.10}Swift~5.10 \cite{se0404}, this was relaxed to allow protocols to nest inside other declarations arbitrarily, as long as those declarations are not generic:
\begin{Verbatim}
enum E {
  protocol P {}  // allowed as of SE-0404
}

struct S: E.P {}
\end{Verbatim}
However, protocols are still prohibited from appearing within generic declarations:
\begin{Verbatim}
struct G<T>(_: T) {
  protocol P {  // error
    func f() -> T  // because what would this mean?
  }
}
\end{Verbatim}
If a protocol could depend on outer generic parameters in this way, its \index{protocol generic signature!generic protocol}protocol generic signature would contain those other parameters and their requirements, in addition to \IndexSelf\tSelf. \index{Haskell}Haskell calls this a \index{multi-parameter type class}\emph{multi-parameter type class}.

Effectively, each specialization of a generic protocol would be a distinct type, and the same concrete conforming type could conform to multiple specializations of a generic protocol with different implementations of each conformance:
\begin{Verbatim}
struct S: G<Int>.P {...}
struct S: G<String>.P {...}
\end{Verbatim}
This would be a major change. Today, a conformance requirement $\TP$ is effectively a unary predicate---a true or false statement---about this type parameter. A conformance to a generic protocol, on the other hand, is a more general kind of relation that relates \emph{multiple} type parameters which then all ``participate'' in the conformance. At the very least, this entails a complete rethink of the formal system from the previous chapter, as well as most of the material in \PartRef{part rqm}. To get another sense of the complexity this feature introduces, see~\cite{mptc}.

\section{Composition}\label{sec:composition}

Suppose that we have three generic signatures $G$, $H$, $I$, and a pair of substitution maps $\Sigma_1\in\SubMapObj{G}{H}$, $\Sigma_2\in\SubMapObj{H}{I}$. If we take any interface type $\tX\in\TypeObj{G}$, we can apply $\Sigma_1$ to $\tX$, and we get $\tX\otimes\Sigma_1\in\TypeObj{H}$. If we then apply $\Sigma_2$ to $\tX\otimes\Sigma_1$, we get the following element of $\TypeObj{I}$:
\[(\tX\otimes\Sigma_1)\otimes\Sigma_2\]
Now, consider how we might get from \tX\ to $(\tX\otimes\Sigma_1)\otimes\Sigma_2$ in one step.
\begin{definition}\label{subst map composition}
The \index{composition!of substitution maps}\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 defined as the unique substitution map which satisfies the following identity for all $\tX\in\TypeObj{G}$:
\[\tX\otimes(\Sigma_1\otimes\Sigma_2):=(\tX\otimes\Sigma_1)\otimes\Sigma_2\]

Since $(\tX\otimes\Sigma_1)\otimes\Sigma_2\in\TypeObj{I}$, it follows that $\Sigma_1\otimes\Sigma_2\in\SubMapObj{G}{I}$; that is, the \index{input generic signature}input generic signature of $\Sigma_1 \otimes \Sigma_2$ is the input generic signature of $\Sigma_1$, and the output generic signature of $\Sigma_1 \otimes \Sigma_2$ is the \index{output generic signature}output generic signature of $\Sigma_2$. Substitution map composition gives us this mapping of sets:
\[\SubMapObj{G}{H}\otimes\SubMapObj{H}{I}\longrightarrow\SubMapObj{G}{I}\]
\end{definition}

Simply stated, applying the composition of two substitution maps to an interface type produces the same result as first applying the first substitution map, followed by the second. Now we will see how to construct $\Sigma_1 \otimes \Sigma_2$. First, suppose that~$G$, the input generic signature of~$\Sigma_1$, does not state any conformance requirements, so the behavior of~$\Sigma_1$ is completely determined by its replacement types:
\[\Sigma_1 := \SubstMap{\ldots,\,\SubstType{\ttgp{d}{i}}{$\ttgp{d}{i}\otimes\Sigma_1$},\,\ldots}\]
To construct $\Sigma_1 \otimes \Sigma_2$, we apply $\Sigma_2$ to each replacement type of $\Sigma_1$:
\[
\Sigma_1\otimes\Sigma_2 := \SubstMap{
\ldots,\,
\SubstType{\ttgp{d}{i}}{$\bigl((\ttgp{d}{i}\otimes\Sigma_1)\otimes\Sigma_2\bigr)$},\,
\ldots
}
\]
It is immediate that the following identity now holds all generic parameters $\ttgp{d}{i}$ of $G$, which completely determines $\Sigma_1 \otimes \Sigma_2$:
\[
\ttgp{d}{i}\otimes(\Sigma_1\otimes\Sigma_2)=(\ttgp{d}{i}\otimes\Sigma_1)\otimes\Sigma_2
\]

In the general case where $G$ states one or more conformance requirements, $\Sigma_1$ also stores a list of \index{root conformance!substitution map composition}\emph{root conformances}. In this case, substitution map composition also needs to apply $\Sigma_2$ to each root conformance of $\Sigma_1$ to properly form the new substitution map. Conformance substitution will be explained in \SecRef{conformance subst}.

\newcommand{\FirstMapInExample}{\SubstMap{
\SubstType{\rT}{Optional<\rT>},\,\SubstType{\rU}{Bool}
}}
\newcommand{\SecondMapInExample}{\SubstMap{
\SubstType{\rT}{Int}
}}
\newcommand{\ThirdMapInExample}{\SubstMap{
\SubstType{\rT}{Optional<Int>},\,\SubstType{\rU}{Bool}
}}

\begin{example}\label{composesubstmapexample}
Substitution map composition can help us reason about the types of chained \index{member reference expression}member reference expressions, like the type of ``\texttt{x}'' below:
\begin{Verbatim}
struct Outer<T> {
  var inner: Inner<Optional<T>, Bool>
}

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

let outer: Outer<Int> = ...
let x = outer.inner.value  // What is the type of `x'?
\end{Verbatim}
First, consider the type of the ``\texttt{inner}'' stored property of \texttt{Outer}. Let's denote its context substitution map by $\Sigma_1$:
\[
\Sigma_1 := \FirstMapInExample
\]
Note that the input generic signature of $\Sigma_1$ is the generic signature of \texttt{Inner}, which is the declaration being referenced, and the output generic signature of $\Sigma_1$ is the generic signature of \texttt{Outer}, the declaration the reference appears in.

Now, consider the type of the ``\texttt{outer}'' global variable. We will denote its context substitution map by $\Sigma_2$:
\[
\Sigma_2 := \SecondMapInExample
\]
The input generic signature of $\Sigma_2$ is the generic signature of \texttt{Outer}, which is the output generic signature of $\Sigma_1$, so we can compose the two substitution maps:
\[\Sigma_1\otimes\Sigma_2 = \ThirdMapInExample\]
Finally, consider the interface type of the ``\texttt{value}'' stored property of \texttt{Inner}. This is the tuple type \texttt{(\rT, \rU)}. The type of the expression ``\texttt{outer.inner.value}'' can be derived from this original type in two ways: we can apply each substitution map in turn, or we can apply their composition:
\begin{gather*}
(\texttt{(\rT, \rU)}\otimes\Sigma_1)\otimes \Sigma_2\\
\qquad {} = \texttt{(Optional<\rT>, \rU)}\otimes \Sigma_2\\
\qquad {} = \texttt{(Optional<Int>, Bool)}\\[\medskipamount]
\texttt{(\rT, \rU)}\otimes(\Sigma_1\otimes \Sigma_2)\\
\qquad {} = \texttt{(\rT, \rU)}\otimes \ThirdMapInExample\\
\qquad {} = \texttt{(Optional<Int>, Bool)}
\end{gather*}
\end{example}

\paragraph{Commutative diagrams.}
A \IndexDefinition{commutative diagram}\emph{commutative diagram} exhibits a collection of objects and operations, where each operation is represented by a labeled arrow. When we say this diagram \emph{commutes}, we mean that whenever we have two paths with the same source and destination, we can follow the composition of operations given by either path and arrive at the same result. For example, we can illustrate \DefRef{subst map composition} with this diagram:
\begin{center}
\begin{tikzcd}[column sep=2cm, row sep=2cm]
\tX \arrow[r, "\Sigma_1"] \arrow[rd, "\Sigma_1 \otimes \Sigma_2"'] &{\tX \otimes \Sigma_1}\arrow[d, "\Sigma_2"]\\
&{(\tX \otimes \Sigma_1) \otimes \Sigma_2}
\end{tikzcd}
\end{center}
We will see more interesting commutative diagrams later.

\paragraph{Identity substitution map.}
We saw that every generic signature has an identity substitution map in \SecRef{contextsubstmap}. The identity substitution map comes up whenever we forward the generic parameters as arguments to another generic declaration.  Now, we consider how the identity behaves under composition. There are two possibilities.

If $\Sigma\in\SubMapObj{G}{H}$, we can compose $\Sigma$ with the \index{identity substitution map}identity substitution map $1_G$ on the left. This applies $\Sigma$ to each replacement type of $1_G$, which projects each replacement type of $\Sigma$ in turn; we assemble a new substitution map identical to $\Sigma$:
\[
1_G \otimes \Sigma = \Sigma\tag{1}
\]
We can also compose $\Sigma$ with $1_H$ on the right. This applies $1_H$ to each replacement type of $\Sigma$. From our earlier discussion of the identity substitution map, we know this leaves the replacement types of $\Sigma$ unchanged, so again we get:
\[
\Sigma\otimes 1_H = \Sigma\tag{1}
\]

A remark about \index{primary archetype}primary archetypes, which we won't introduce until \ChapRef{chap:archetypes}. Our definition of $\SubMapObj{G}{H}$ was crafted to exclude substitution maps whose replacement types contain primary archetypes. If we also consider such substitution maps, then (1) still holds, but (2) does not. In \SecRef{archetypesubst}, we will see that a different substitution map, the \emph{forwarding substitution map}, acts as the identity element on such types, that we will refer to as \emph{contextual types}.

\paragraph{Order of operations.}
A fact we will state without proof is that substitution map composition is an \index{associative operation}\emph{associative} operation. That is, if $\Sigma_1$, $\Sigma_2$, and $\Sigma_3$ are any three substitution maps such that all below compositions are defined, then:
\[
(\Sigma_1 \otimes \Sigma_2) \otimes \Sigma_3 = \Sigma_1 \otimes (\Sigma_2 \otimes \Sigma_3)
\]
For example, this means that when \tX\ is any interface type, all of the following expressions must produce the same substituted type:
\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, we can omit parentheses without ambiguity in our notation:
\[\tX\otimes\Sigma_1\otimes\Sigma_2\otimes\Sigma_3\]

\paragraph{Categorically speaking.}
We won't need this elsewhere, but it's worth mentioning briefly that a certain mathematical abstraction captures the properties of substitution map composition. A \IndexDefinition{category}\emph{category} is a collection of \IndexDefinition{object in category}\emph{objects} and \IndexDefinition{morphism in category}\emph{morphisms}. A morphism has a \emph{source} and \emph{destination} object, and the collection of morphisms with source $A$ and destination $B$ is denoted $\mathrm{Hom}(A,B)$. The morphisms must satisfy some axioms:
\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)$, there is a morphism $g\circ f\in\mathrm{Hom}(A,C)$, called the \index{composition!of morphisms}\emph{composition} of $g$ and $f$. (The conventional notation $g\circ f$ mirrors how we write $g(f(x))$ with function application on the left.)
\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}
For example, we could define \emph{the category of interface types} as follows:
\begin{itemize}
\item The objects are the sets $\TypeObj{G}$, for each generic signature $G$.
\item Substitution maps are morphisms, and $\mathrm{Hom}$ is $\textsc{Sub}$.
\item The source of a morphism $\Sigma\in\SubMapObj{G}{H}$ is $\TypeObj{G}$.
\item The destination of a morphism $\Sigma\in\SubMapObj{G}{H}$ is $\TypeObj{H}$.
\item Identity substitution maps are identity morphisms.
\item Morphism composition $g \circ f$ is substitution map composition $f\otimes g$.
\end{itemize}
This happens to be a \emph{concrete} category, where every object is a set and every morphism is a function between sets, but this need not be the case in general. In programming, we often encounter category theory when working with data structures and higher-order functions; an excellent introduction to the topic is \cite{catprogrammer}.

\section{Subclassing}\label{classinheritance}

The Swift language supports \IndexDefinition{subclassing}\emph{subclassing}, or \index{inheritance|see{subclassing}}\emph{inheritance}. After some preliminaries, we will use the type substitution algebra to describe the interaction between subclassing and generics. This will be useful when we discuss the semantics of \index{superclass requirements}superclass requirements in later chapters. Since superclass requirements are not an essential part of the core Swift generics model, the reader can safely skip this section on a first reading.

An inheritance relationship is established when some \index{class declaration!superclass type}class declaration, known as the \emph{subclass}, states a \IndexDefinition{superclass type}\emph{superclass type} in its \index{inheritance clause!class declaration}inheritance clause. Unlike \index{C++}C++, Swift does not allow multiple inheritance, so a class declaration can have at most one superclass type. Unlike \index{Java}Java, there is no distinguished \texttt{Object} class at the root of the hierarchy, so it is common to have class declarations with no superclass type at all.
\begin{example}
First, consider the case where the superclass and the subclass are both non-generic. In the below, \texttt{Apple} and \texttt{Banana} state the superclass type \texttt{Fruit}:
\begin{Verbatim}
class Fruit {
  func eat() {...}
  func juice() {...}
}

class Apple: Fruit {
  override func eat() {...}
}

class Banana: Fruit {}

let f: Fruit = Apple()  // implicit conversion from Apple to Fruit
f.eat()                 // vtable-dispatched call to Apple.eat()
\end{Verbatim}
In the \index{expression type checker}expression type checker, \texttt{Apple}~and~\texttt{Banana} are \index{subtype}\emph{subtypes} of~\texttt{Fruit}. This allows us to assign the result of the \texttt{Apple()}~constructor call to our variable~\texttt{f}, whose type is~\texttt{Fruit}. We can visualize this with a \index{class hierarchy diagram}class hierarchy diagram:
\begin{center}
\begin{tikzpicture}[node distance=0.75cm]
\node (Fruit) [class] {\texttt{\vphantom{p}Fruit}};
\node (Apple) [class, below left=of Fruit, xshift=2em] {\texttt{Apple}};
\node (Banana) [class, below right=of Fruit, xshift=-2em] {\texttt{\vphantom{p}Banana}};
\draw [arrow] (Apple) -- (Fruit);
\draw [arrow] (Banana) -- (Fruit);
\end{tikzpicture}
\end{center}
Qualified lookup walks up the class hierarchy, so a \index{qualified lookup!superclass}qualified lookup into \texttt{Apple} or \texttt{Banana} will also find members of \texttt{Fruit}. Furthermore, subclasses can~\IndexDefinition{override}\emph{override} \index{function declaration!override}methods, \index{variable declaration!override}properties, and \index{subscript declaration!override}subscripts declared in their superclass. In the above, \texttt{Apple} overrides \texttt{Fruit.eat()} with its own implementation.

An instance of~\texttt{Fruit} might actually be an~\texttt{Apple} at run time, so a call to \texttt{eat()} on a value type of \texttt{Fruit} must be dispatched through a \IndexDefinition{vtable}\emph{vtable} stored in the object header. The vtable for~\texttt{Fruit} points at \texttt{Fruit}'s original implementation of \texttt{eat()} and \texttt{juice()}, while the vtable for \texttt{Apple} replaces \texttt{eat()} with a pointer to \texttt{Apple.eat()}.
\end{example}

\begin{example}
Next, suppose we declare a generic subclass of \texttt{Fruit}. Notice how we override \texttt{Fruit.eat()} to print the concrete replacement type for~\rT:
\begin{Verbatim}
class Pear<T>: Fruit {
  override func eat() {
    print(T.self)
  }
}
\end{Verbatim}
With \texttt{Pear} as above, we can form various \index{generic class type}generic class types, such as \texttt{Pear<Int>}, \texttt{Pear<Bool>}, and so on; these are all obtained by applying a \index{substitution map}substitution map to the \index{declared interface type!class declaration}declared interface type \texttt{Pear<\rT>}. The key fact about this example is that every \index{specialized type}specialization of \texttt{Pear} has the same superclass type, \texttt{Fruit}, because \texttt{Pear}'s superclass type does not depend on its generic parameter \rT. Thus, as far as the expression type checker is concerned, all specializations of \texttt{Pear} are subtypes of~\texttt{Fruit}. Our complete class hierarchy diagram is now infinite, but here is one part of it:
\begin{center}
\begin{tikzpicture}
\node (Fruit) [class] {\texttt{\vphantom{p}Fruit}};
\node (PearInt) [class, below left=of Fruit] {\texttt{\vphantom{p}Pear<Int>}};
\node (PearString) [class, below=of Fruit] {\texttt{\vphantom{p}Pear<Bool>}};
\node (PearT) [class, below right=of Fruit] {\texttt{\vphantom{p}Pear<\rT>}};
\draw [arrow] (PearInt) -- (Fruit);
\draw [arrow] (PearString) -- (Fruit);
\draw [arrow] (PearT) -- (Fruit);
\end{tikzpicture}
\end{center}
This example implements a design pattern known as \index{type erasure}\emph{type erasure}. If we take a value of type~\texttt{Pear<X>} for some \tX, we can always convert it to a value of type~\texttt{Fruit}, effectively \emph{erasing} the generic argument \tX\ from the static type of the resulting value. This allows the type \tX\ to vary dynamically. In the below, the static type of~\texttt{f} is just~\texttt{Fruit}, but the dynamic type of the value stored within is either \texttt{Pear<Int>} or \texttt{Pear<String>}, depending on the outcome of an arbitrary check:
\begin{Verbatim}
let someCondition: Bool = ...
let p1 = Pear<Int>()
let p2 = Pear<String>()
let f: Fruit = (someCondition ? p1 : p2)
\end{Verbatim}
In \ChapRef{chap:existential types}, we will learn about \emph{existential types}, another more general type erasure mechanism built into the language, based on protocols.
\end{example}

\paragraph{Generic superclasses.} The interesting case arises when both subclass and superclass are generic. The superclass type of a class declaration is an \index{interface type!superclass type}interface type, so it can contain type parameters from the \index{generic signature!superclass type}generic signature of the subclass. For example:
\begin{Verbatim}
class StoneFruit<T> {}
class Mango<U>: StoneFruit<Array<U>> {}
\end{Verbatim}
In certain situations, we don't care about generic arguments at all, and we say that the \IndexDefinition{superclass declaration}\emph{superclass declaration} of \texttt{Mango} is \texttt{StoneFruit}. However, the full relationship is expressed by the fact that the superclass \emph{type} of \texttt{Mango} is \texttt{StoneFruit<Array<\rT>>}.  We can also obtain the superclass type of a \index{class type!superclass type}class \emph{type}, that is, a reference to a class declaration specialized with a list of generic arguments. This is defined in terms of applying a substitution map to the superclass type of a class declaration.

\begin{algorithm}[Get superclass type]\label{superclass type of type} Takes a class type~\tC\ as input. Returns the superclass type of~\tC, or null if \tC\ does not have a superclass type.
\begin{enumerate}
\item Let $c$ be the class declaration of \tC. If $c$ doesn't have a superclass type, return null.
\item Let \texttt{S} be the superclass type of $c$.
\item Let $\Sigma$ be the \index{context substitution map!superclass type}context substitution map of \tC.
\item Return $\texttt{S}\otimes\Sigma$.
\end{enumerate}
\end{algorithm}
\begin{example}
The class type \texttt{Mango<Int>} is formed by applying the substitution map $\{\SubstType{\rT}{Int}\}$ to the declared interface type \texttt{Mango<\rT>}. To compute the superclass type of \texttt{Mango<Int>}, we apply this substitution map to the superclass type of the declaration, which is  \texttt{StoneFruit<Array<\rT>>}:
\[
\texttt{StoneFruit<Array<\rT>>} \otimes \{\SubstType{\rT}{Int}\} = \texttt{StoneFruit<Array<Int>>}
\]
The below class hierarchy diagram shows the relationship (or lack hereof) between the two types \texttt{Mango<Int>} and \texttt{Mango<Bool>}:
\begin{center}
\begin{tikzpicture}
\node (StoneFruitInt) [class] {\texttt{\vphantom{p}StoneFruit<Array<Int>>}};
\node (MangoInt) [class, below=of StoneFruitInt] {\texttt{Mango<Int>}};

\node (StoneFruitBool) [class, right=of StoneFruitInt] {\texttt{\vphantom{p}StoneFruit<Array<Bool>>}};
\node (MangoBool) [class, below=of StoneFruitBool] {\texttt{Mango<Bool>}};

\draw [arrow] (MangoInt) -- (StoneFruitInt);
\draw [arrow] (MangoBool) -- (StoneFruitBool);
\end{tikzpicture}
\end{center}
Now, consider the superclass type of \texttt{Mango<\rT>}. We saw at the beginning of this chapter that the context substitution map of the declared interface type is the \index{identity substitution map!superclass type}identity substitution map. Indeed, since $\texttt{Mango<\rT>} \otimes \SubstMap{\SubstType{\rT}{\rT}} = \texttt{Mango<\rT>}$, the superclass type of \texttt{Mango<\rT>} is \texttt{StoneFruit<Array<\rT>>}, which is the same as the superclass type of the declaration of \texttt{Mango}.
\end{example}
Suppose that the class type \tC\ given to \AlgRef{superclass type of type} is an \index{interface type!superclass type}interface type for some generic signature~$H$, so that $\tC\in\TypeObj{H}$. If $G$~is the generic signature of~$c$ in Step~2, then $\Sigma\in\SubMapObj{G}{H}$ in Step~1. We already said that \texttt{S}, the superclass type of $c$, is an element of $\TypeObj{G}$, so our result $\texttt{S}\otimes\Sigma\in\TypeObj{H}$. That is, the superclass type of \tC, if it exists, is again an interface type for~$H$.

Not every interface type has a superclass type. Thus, for every generic signature $H$, we get the following \emph{partial} mapping of \index{set!types}sets, which we denote by ``\textsf{superclass}'':
\[
\textsf{superclass}\colon \TypeObj{G} \rightarrow \TypeObj{G}
\]
If \tC\ is a class type, $\tC^\prime$ is the superclass type of \tC, and $\Sigma$ is a substitution map, then the following diagram commutes:
\begin{center}
\begin{tikzcd}[column sep=3cm,row sep=1cm]
\tC \arrow[d, "\textsf{superclass}"{left}] \arrow[r, "\Sigma"] &\tC \otimes \Sigma \arrow[d, "\textsf{superclass}"] \\
\tC^\prime \arrow[r, "\Sigma"]&\tC^\prime \otimes \Sigma
\end{tikzcd}
\end{center}

\begin{example}
We can restate our previous example this way:
\begin{center}
\begin{tikzcd}[column sep=3cm,row sep=1cm]
\texttt{Mango<\rT>} \arrow[d, "\textsf{superclass}"{left}] \arrow[r, "\{\SubstType{\rT}{Int}\}"] &\texttt{Mango<Int>} \arrow[d, "\textsf{superclass}"] \\
\texttt{StoneFruit<Array<\rT>>} \arrow[r, "\{\SubstType{\rT}{Int}\}"]&\texttt{StoneFruit<Array<Int>>}
\end{tikzcd}
\end{center}
\end{example}

\paragraph{Superclass substitution map.} If qualified lookup into a class type finds a member one or more levels up the class hierarchy, we need to form the correct substitution map for the \index{member reference expression}member reference expression.
\begin{example}
When we invoke \texttt{method()} on a value of type \texttt{Top<Int>} below, the substitution map for the call is the \index{context substitution map!class member}context substitution map of \texttt{Top<Int>}, because \texttt{method()} is a direct member of \texttt{Top}:
\begin{Verbatim}
class Top<T> {
  func method() {}
}
Top<Int>().method()
\end{Verbatim}
If we call \texttt{method()} on a subclass of \texttt{Top} though, this is no longer the case:
\begin{Verbatim}
class Mid<X, Y>: Top<(Y, X)> {}
class Bot: Mid<Int, Bool> {}
Bot().method()
\end{Verbatim}
The class type \texttt{Bot} is not generic, so it's context substitution map is \index{empty substitution map}empty. However, we need a substitution map for \texttt{<\rT>}, the generic signature of \texttt{method()}. Notice how starting from \texttt{Bot}, we reach the parent context of \texttt{method()} in two hops; we jump to \texttt{Mid}, and then to \texttt{Top}. The superclass types of \texttt{Mid} and \texttt{Bot} are as follows:
\begin{gather*}
\mathsf{superclass}(\texttt{Mid<\rT, \rU>}) = \texttt{Top<(\rU, \rT)>} = \texttt{Top<\rT>} \otimes \Sigma_1\\
\mathsf{superclass}(\texttt{Bot}) = \texttt{Mid<Int, Bool>} = \texttt{Mid<\rT, \rU>} \otimes \Sigma_2
\end{gather*}
with the two substitution maps below:
\begin{gather*}
\Sigma_1 := \SubstMap{\SubstType{\rT}{(\rU, \rT)}}\\
\Sigma_2 := \SubstMap{\SubstType{\rT}{Int},\,\SubstType{\rU}{Bool}}
\end{gather*}
The input generic signature of~$\Sigma_1$ is the generic signature of \texttt{Top}, and the output generic signature of~$\Sigma_1$ is the generic signature of \texttt{Mid}. Also, the input generic signature of~$\Sigma_2$ is the generic signature of \texttt{Mid}, and its output generic signature is the generic signature of \texttt{Bot}, which is the empty generic signature. If we \index{substitution map composition!superclass type}compose the two substitution maps, we get the following:
\[
\Sigma_1 \otimes \Sigma_2 = \SubstMap{\SubstType{\rT}{(Bool, Int)}}
\]
This is the substitution map for the call. In particular, when we call \texttt{method()} on a value of type \texttt{Bot}, the type of the \texttt{self} parameter inside the method is going to be:
\[
\texttt{Top<\rT>} \otimes \Sigma_1 \otimes \Sigma_2 = \texttt{Top<(Bool, Int)>}
\]
In fact, we can also get the same result if we apply ``\textsf{superclass}'' twice:
\[
\mathsf{superclass}(\mathsf{superclass}(\texttt{Bot})) = (\texttt{Top<\rT>} \otimes \Sigma_1) \otimes \Sigma_2
\]
\end{example}

We can generalize this as follows. We are given a class type together with the parent \index{class declaration}class declaration of some referenced member, so we must walk up the class hierarchy and collect substitutions along the way, until we reach the parent class.

\begin{algorithm}[Get superclass type for declaration]\label{superclassfordecl} As input, takes a class type \tC\ and a class declaration $d$. Returns the superclass type of \tC\ for $d$.
\begin{enumerate}
\item Let $c$ be the class declaration of \tC. If~$c=d$, return \tC.
\item Let \texttt{S} be the superclass type of $c$, or signal an invariant violation if it doesn't have one. (That would indicate $d$~is not a superclass of the original class type~\tC, in which case members of $d$ should not be visible as members of \tC.)
\item Let~$\Sigma$ be the context substitution map of~\tC. Set $\tC \leftarrow \texttt{S} \otimes \Sigma$. Go back to Step~1.
\end{enumerate}
\end{algorithm}

Note that this algorithm returns the type of the \Index{self parameter@\texttt{self} parameter}\texttt{self} parameter as seen ``inside'' the referenced member. To get the substitution map for the reference, we ask this type for its context substitution map. This is known as the \IndexDefinition{superclass substitution map}\emph{superclass substitution map}.

This wraps up our discussion of subclassing for now. In later sections, we will learn more about this topic, and in particular, we will see how this all intersects with superclass requirements in a generic signature:
\begin{itemize}
\item \ChapRef{chap:conformances} explains how a subclass inherits conformances from its superclass.
\item \SecRef{local requirements} explains how archetypes behave when their type parameter is subject to a superclass requirement.
\item \SecRef{identtyperepr} explains how type resolution resolves a reference to a member type declared in the superclass of a base type.
\item \SecRef{checking generic arguments} explains how we can check if a substitution map satisfies a superclass requirement.
\item \SecRef{requirement desugaring} and \SecRef{minimal requirements} explain what it means for the user's program to state a superclass requirement that is either redundant or in conflict with some other requirement.
\end{itemize}

\section{SIL Type Lowering}\label{sec:type lowering}

We end this chapter by taking a brief look at the \index{SIL}SIL type system. Recall that SIL is an intermediate representation, constructed from the \index{abstract syntax tree}abstract syntax tree by the compiler's \index{SILGen}SILGen pass. In this section, the types appearing in the \index{abstract syntax tree}abstract syntax tree will be called \IndexDefinition{formal type}\emph{formal types}, to distinguish them from the \IndexDefinition{lowered type}\emph{lowered types} used by SIL. The translation of formal types into lowered types is the process of \IndexDefinition{SIL type lowering}\index{type lowering|see{SIL type lowering}}\emph{SIL type lowering}.

Our primary focus in this section is the relationship between SIL type lowering and \index{type substitution!lowered type}type substitution. We cannot hope to gain a complete understanding of SIL type lowering here, so certain concepts will be omitted or left unexplained. For more details about SIL and SIL types, see \cite{sil,siltypes}. The reader may also choose to skip this section entirely, because this material is not needed in the rest of this book.

\paragraph{Loadable or address-only.}
Most formal types are also lowered types, and SIL type lowering simply returns the original formal type in this case. One major exception concerns the types of functions. Unlike the \index{function type!SIL type lowering}function types of \SecRef{sec:more types}, which we will refer to as \emph{formal} function types in this section, the type of a function in SIL is a different kind of type that does not appear in the abstract syntax tree: the \IndexDefinition{SIL function type}\emph{SIL function type}. Compared to formal function types, SIL function types encode more details about the \index{calling convention}calling convention. We begin by taking a look at one of these details.

A SIL function type makes explicit whether each \IndexDefinition{lowered parameter}lowered parameter and \IndexDefinition{lowered result}result can be passed in registers, or if it must be passed indirectly, via a pointer to a value stored in memory. If the parameter's lowered type is \IndexDefinition{loadable type}\emph{loadable}, it is passed directly; otherwise, the lowered type is \IndexDefinition{address-only type}\emph{address-only}, and it must be passed indirectly. Almost all lowered types are loadable. The exceptions are the following:
\begin{enumerate}
\item \index{type parameter type!SIL type lowering}Type parameter types and \index{archetype type!SIL type lowering}archetype types are address-only when they are not subject to an \Index{AnyObject@\texttt{AnyObject}}\texttt{AnyObject} layout constraint (\SecRef{sec:requirements}).

(Values of such type have an unknown size at compile time.)

\item \index{weak reference type!SIL type lowering}Weak reference types  (\SecRef{sec:special types}) are address-only.

(While a weak reference is just the address of a class instance, the location of each weak reference must be registered with the Swift runtime at all times, and so they can only ``exist'' in memory.)

\item \index{struct type!SIL type lowering}Struct and \index{enum type}enum types with \index{resilience!SIL type lowering}\emph{resilient} declarations are address-only.

(We briefly talked about the resilience model in \SecRef{module system}, but further discussion is beyond the scope of this book. See \cite{evolutionblog,libraryevolution} for details.)

\item Aggregate types, such as \index{tuple type!SIL type lowering}tuples with address-only elements, structs with address-only \index{stored property}stored properties, and enums with address-only cases, are address-only.

(The property of being address-only is \index{transitive relation}transitive with respect to containment.)

\item \index{existential type!SIL type lowering}Existential types (\ChapRef{chap:existential types}) are address-only when not \texttt{AnyObject} constrained.

(A value of such a type can \emph{contain} a value of address-only type, and so the existential container itself must be address-only.)
\end{enumerate}
We will look at some examples before we discuss the general case.

\begin{example}\label{ex:loadable address only 1}
The \texttt{Int} and \texttt{String} types in the standard library are loadable, and so is the below \texttt{Loadable} struct type, because its stored properties are loadable:
\begin{Verbatim}
struct Loadable {
  var x: Int
  var y: String
}
\end{Verbatim}
On the other hand, the below \texttt{AddressOnly} struct is address-only, because it contains a weak reference:
\begin{Verbatim}
struct AddressOnly {
  weak var x: AnyObject?
}
\end{Verbatim}
\end{example}

For \index{generic nominal type!SIL type lowering}generic nominal types, deciding if a type is address-only requires type substitution.

\begin{example}\label{ex:lowering optional}
First, consider the standard library \texttt{Optional} enum:
\begin{Verbatim}
public enum Optional<Wrapped> {
  case none
  case some(Wrapped)
}
\end{Verbatim}
In this section, we will say that a \index{generic nominal type!SIL type lowering}generic nominal type formed from this declaration is an ``\index{optional type}optional type.'' (Not to be confused with the \index{optional sugared type}optional sugared type that is spelled as \texttt{Int?}, from \SecRef{sec:more types}---however, the latter desugars to the former.)

The generic argument of an optional type is called the \index{payload type of optional}\emph{payload type} of the optional. In memory, a value of optional type must be large enough to store the payload, together with a tag value indicating if the selected case is \texttt{none} or \texttt{some}. (The tag is also sometimes encoded \emph{inside} the payload~\cite{typelayout}.)

An optional type is loadable if and only if its payload type is loadable. Thus, \texttt{Optional<Int>} is loadable, while \texttt{Optional<AddressOnly>}, with \texttt{AddressOnly} as in the previous example, is address-only.
\end{example}

\begin{example}
Next, consider this enum declaration, which is identical to \texttt{Optional} except that the ``\texttt{some}'' case is declared to be \index{indirect enum case}\texttt{indirect}:
\begin{Verbatim}
enum IndirectOptional<Wrapped> {
  case none
  indirect case some(Wrapped)
}
\end{Verbatim}
Instead of storing the payload inline, an \texttt{indirect} enum case is represented by a single reference-counted pointer that refers to a heap-allocated box. For this reason, both \texttt{IndirectOptional<Int>} and \texttt{IndirectOptional<AddressOnly>} are loadable.
\end{example}

\begin{example}
This generic struct declaration has no stored properties at all:
\begin{Verbatim}
struct Phantom<T> {}
\end{Verbatim}
Hence, both \texttt{Phantom<Int>} and \texttt{Phantom<AddressOnly>} are loadable.
\end{example}

\begin{example}
When a type contains \index{type parameter type!SIL type lowering}type parameters, its category depends on the referencing generic context:
\begin{Verbatim}
func f<T, U: AnyObject>(_ t: T, _ u: U) {
  let x: Optional<T> = ...  // address-only
  let y: Optional<U> = ...  // loadable
}
\end{Verbatim}
The type of \texttt{x} is address-only, because \texttt{T} is unconstrained, while the type of \texttt{y} is loadable, because \texttt{U} is subject to an \texttt{AnyObject} layout constraint.
\end{example}

Now, we're going to look at the algorithm. As described here, it accepts both formal and lowered types. In the actual implementation, it operates on lowered types only, and we compute a number of additional properties of the type's layout in the same way.

\begin{algorithm}[Decide if type is address-only]\label{alg:lowered type category}
Receives a type~\tX\ as input, together with an optional \index{generic signature!SIL type lowering}generic signature~$G$ in the case where \tX\ contains type parameters. Returns one of ``\index{loadable type}loadable'' or ``\index{address-only type}address-only'' as output.
\begin{enumerate}
\item If \tX\ is a \index{type parameter!SIL type lowering}\textbf{type parameter}, say $\tX = \tT$: evaluate the \IndexQuery{requiresClass}$\Query{requiresClass}{G,\,\tT}$ generic signature query. If the answer to the query is true, return ``loadable,'' otherwise return ``address-only.''
\item If \tX\ is an \index{archetype type!SIL type lowering}\textbf{archetype type} (\ChapRef{chap:archetypes}): proceed as above, but in place of~$G$, use the generic signature stored within the archetype.
\item If \tX\ is a \index{weak reference type!SIL type lowering}\textbf{weak reference type}, return ``address-only.''
\item If \tX\ is a \index{struct type!SIL type lowering}\textbf{struct type}, say $\tX = \tXd \otimes \Sigma$ where~$\Sigma$ is the \index{context substitution map}context substitution map and~$\tXd$ is the \index{declared interface type!SIL type lowering}declared interface type of its struct declaration~$d$, then, for each \index{stored property!SIL type lowering}stored property of~$d$:
\begin{enumerate}
\item Let \tY\ be the \index{interface type!SIL type lowering}interface type of the stored property.
\item Compute the substituted type $\tY \otimes \Sigma$.
\item Recursively check if $\tY \otimes \Sigma$ is address-only.
\item If it is address-only, immediately return ``address-only.''
\end{enumerate}
Otherwise, if all substituted stored property types are loadable, return ``loadable.''

\item If \tX\ is an \index{enum type!SIL type lowering}\textbf{enum type}:
\begin{enumerate}
\item Check if the \index{enum declaration!SIL type lowering}enum declaration is \texttt{indirect}; if so, return ``loadable.''
\item Otherwise, proceed as in the struct case, but only consider those enum cases \emph{not} declared as \index{indirect enum case}\texttt{indirect}.

(The lowered type of an \index{indirect enum case}\texttt{indirect} case is always a reference-counted pointer to a \index{heap-allocated box}heap-allocated box, and such a pointer is loadable. If the enum itself is \texttt{indirect}, we proceed as if each case was \texttt{indirect}.)
\end{enumerate}

\item If \tX\ is a \index{tuple type!SIL type lowering}\textbf{tuple type}, recursively check if each element type of \tX\ is address-only. If any are address-only, return ``address-only.'' Otherwise, return ``loadable.''

\item If \tX\ is an \index{existential type!SIL type lowering}\textbf{existential type}, check if the existential type satisfies the \texttt{AnyObject} layout constraint. If so, return ``loadable,'' otherwise ``address-only.''

\item If \tX\ is a \index{class type!SIL type lowering}\textbf{class type}, \index{metatype type!SIL type lowering}\textbf{metatype type}, or \index{function type!SIL type lowering}\textbf{(SIL) function type}, return ``loadable.''
\end{enumerate}
\end{algorithm}

\paragraph{Exploding tuples.}
A formal function type has zero or more parameter types, and exactly one return type. This return type can be a \index{tuple type!SIL type lowering}tuple type, which is how we model the case of having no return value, or more than one return value. 

Like a formal function type, a \index{SIL function type}SIL function type has zero or more \index{lowered parameter!tuple type}lowered parameter types, but unlike a formal function type, a SIL function type \emph{also} has zero or more lowered \index{lowered result!tuple type}result types. When a tuple type appears in the parameter list or return type of a formal function type, SIL type lowering will ``explode'' it into multiple lowered parameters or lowered results.

Both lowered parameters and lowered results are annotated with a \index{convention!SIL type lowering}\emph{convention}, which encodes two things: whether the value is passed directly in registers or indirectly via memory, and also, how the \index{ownership}ownership of the value changes during the call:
\begin{enumerate}
\item The directness is determined by the lowered parameter or result type; if the type is loadable, we may pass it directly (but sometimes, we must pass it indirectly, as we will see below); when it is address-only, it must be passed indirectly.
\item A discussion of ownership is beyond the scope of this book. See \cite{siltypes} for details.
\end{enumerate}

A SIL function type also has an overall \index{calling convention}convention specifier. The possible conventions are a superset of those for formal function types, which were listed in \SecRef{sec:more types}. For us, the two that we need are \index{thin function!SIL type lowering}\texttt{@convention(thin)}, for functions that don't capture values (such as global functions and methods), and \index{thick function!SIL type lowering}\texttt{@convention(thick)}, for functions that do (such as \index{closure expression!SIL type lowering}closure expressions). A thick function value consists of a function pointer together with a \index{closure context}context, which can be used to store \index{captured value}captured values---the caller passes the context as an additional parameter. Finally, a SIL function type has a \index{generic signature!SIL function type}generic signature.

\begin{example}
Here is a \index{function declaration}function declaration with two parameters, the second of which is a tuple. The second element of the tuple is our address-only type from \ExRef{ex:loadable address only 1}:
\begin{Verbatim}
func foo(x: Int, y: (String, AddressOnly)) {}
\end{Verbatim}
Here is the notation used by the compiler when printing this declaration's SIL function type (for example, put the above declaration together with the \texttt{AddressOnly} struct from earlier in a source file, and build it the \IndexFlag{emit-silgen}\verb|-emit-silgen| flag):
\begin{quote}
\begin{verbatim}
@convention(thin)
(Int, @guaranteed String, @in_guaranteed AddressOnly) -> ()
\end{verbatim}
\end{quote}
The \texttt{Int} parameter does not have a convention annotation, so it is passed directly. The \texttt{Int} type is \index{trivial type}trivial value, so its values can be moved and copied without ownership concerns. The \texttt{String} parameter is also passed directly, but this time, the \verb|@guaranteed| convention indicates that ownership of the string is retained by the caller. Finally, the \texttt{AddressOnly} parameter is address-only, so the \verb|@in_guaranteed| convention is used to pass the value indirectly, and once again, the caller retains ownership of the value. Since \texttt{foo()} does not state a return type, the SIL function type has zero results.
\end{example}

\begin{example}
Here is a generic function that returns a tuple:
\begin{Verbatim}
func flip<T, U>(t: T, u: U) -> (U, T) {
  return (u, t)
}
\end{Verbatim}
Here is its SIL function type:
\begin{quote}
\begin{verbatim}
@convention(thin)
<T, U> (@in_guaranteed T, @in_guaranteed U) -> (@out U, @out T)
\end{verbatim}
\end{quote}
Both parameters are passed indirectly, with the caller retaining ownership (so in fact the implementation of the function most copy these values). The SIL function type also returns two results indirectly (at the machine level, the caller provides a pair of return buffers, large enough to hold both results.)
\end{example}

\paragraph{Re-abstraction thunks.}
So, to get a SIL function type of a \index{function declaration!SIL type lowering}function declaration or \index{closure expression!SIL type lowering}closure expression, we take its \index{interface type!SIL function type}interface type, which is a formal function type. We explode tuples in the parameter list and return type, compute the category of each parameter and result, and do a few other things. Of course, some of those parameter and result types may themselves be function types, and we recursively lower those function types, too. We then form our SIL function type. This is sufficient to explain SILGen's behavior with direct calls of functions and closures, but it is not the whole story.

To understand what happens when a function value is passed between generic contexts, we need to talk about \IndexDefinition{abstraction pattern}\emph{abstraction patterns}. The operation of SIL type lowering in the compiler receives not just a \index{formal type}formal type, but also an abstraction pattern.

This complication arises for the following reason. When a substitution map is applied to a SIL function type, the type parameters in the SIL function type are replaced with concrete types. However, substitution does not change the directness of the SIL function type's parameters and results. If an original type parameter is address-only but its replacement type is loadable, the resulting SIL function type will differ from what we would get if we just lower the substituted formal type instead. Typically, a closure expression is emitted with a ``natural'' abstraction pattern that is its own formal type. To change the abstraction pattern of a function value, SILGen wraps the function value in a \IndexDefinition{re-abstraction thunk}\emph{re-abstraction thunk}. There are two kinds of thunk:
\begin{enumerate}
\item A \IndexDefinition{substituted-to-original thunk}\textbf{substituted-to-original thunk} appears when a closure is passed in to a generic function. It wraps a function type lowered with itself as the abstraction pattern, with a function type lowered with a more general abstraction pattern.
\item An \IndexDefinition{original-to-substituted thunk}\textbf{original-to-substituted thunk} appears when a closure is returned from a generic function. It wraps a function type lowered with a more general abstraction pattern, with one lowered with the fully substituted abstraction pattern.
\end{enumerate}

\begin{example}\label{ex:abstraction pattern 1}
Consider this rather pointless generic function that applies a closure to a value and returns the result:
\begin{Verbatim}
func apply<T>(_ x: T, _ fn: (T) -> T) -> T {
  return fn(x)
}
\end{Verbatim}
Say we call our function like this, with the substitution map $\Sigma := \SubstMap{\SubstType{\rT}{String}}$:
\begin{Verbatim}
let fn: (String) -> String = { $0.uppercased() }
let result = apply("hello world", fn)
\end{Verbatim}
If we apply $\Sigma$ to the formal type of the ``\texttt{fn}'' parameter to \texttt{apply()}, we get:
\[
\left[ \texttt{(\rT) -> \rT} \right] \otimes \Sigma = \texttt{(String) -> String}
\]
The above formal type is identical to the formal type of the \index{closure expression}closure expression passed in as an argument by the caller. Now, let's take a look at lowered types. Since \texttt{String} is loadable, lowering the above formal type gives:
\begin{quote}
\begin{verbatim}
@convention(thick) (@guaranteed String) -> (@owned String)
\end{verbatim}
\end{quote}
On the other hand, the lowered type of the ``\texttt{fn}'' parameter passes the parameter and returns the result indirectly:
\begin{quote}
\begin{verbatim}
@convention(thick) <T> (@in_guaranteed T) -> (@out T)
\end{verbatim}
\end{quote}
Finally, if we apply $\Sigma$ to this \index{SIL function type!type substitution}SIL function type, we obtain the following:
\begin{quote}
\begin{verbatim}
@convention(thick) (@in_guaranteed String) -> (@out String)
\end{verbatim}
\end{quote}
To reconcile the difference, SILGen wraps the closure with a substituted-to-original thunk before handing it off to \texttt{apply()}. This thunk receives a pointer to a \texttt{String}, loads it, and calls the wrapped closure with the loaded value. The closure returns a new \texttt{String} directly, which the thunk stores into the indirect result buffer before returning.
\end{example}

\paragraph{More about abstraction patterns.}
For our purposes, an \index{abstraction pattern}abstraction pattern simply consists of the unsubstituted \index{formal type!abstraction pattern}formal type for computing the directness of each \index{lowered parameter!abstraction pattern}parameter and \index{lowered result!abstraction pattern}result in the \index{SIL function type!abstraction pattern}SIL function type. (In reality, abstraction patterns also carry a \emph{kind} and some additional information, but we won't need this level of detail here.) So, a \index{re-abstraction thunk}re-abstraction thunk is then basically a closure that wraps another closure. The body of the thunk takes each parameter and forwards it to the wrapped closure, then takes the the wrapped closure's result and returns it to the caller of the thunk. In doing so, a re-abstraction thunk can change the convention of the parameters and results.

There is also a useful peephole optimization that we will mention now. Very often, the closure being re-abstracted is a literal \index{closure expression!re-abstraction thunk}closure expression, in which case SILGen is able to directly emit the closure with the expected abstraction pattern, instead of immediately wrapping it in a thunk. This avoids an unnecessary heap allocation.

\paragraph{Opaque abstraction patterns.}
Type lowering traverses a formal function type ``in parallel'' with the abstraction pattern when in order to build the \index{SIL function type}SIL function type. The abstraction pattern must have the same shape as the formal type, in the sense that the formal type should be obtainable from the abstraction pattern by substitution. For example, the abstraction pattern \texttt{(Int, \rU) -> \rV} is compatible with the formal type \texttt{(Int, (Bool, String) -> Float) -> Bool}, but not with the formal type \texttt{(Bool, Int, String) -> (Float, Float)}---in the latter, the number of parameters doesn't match up, and neither does the return type.

The implementation of this ``parallel decomposition'' is mostly obvious, except when the abstraction pattern consists of a single \index{type parameter}type parameter. This is referred to as an \index{opaque abstraction pattern}\emph{opaque} abstraction pattern in the implementation (not to be confused with opaque parameters or opaque result types). In this situation, we lower the formal function type in the ``most general'' way, as if each one of its parameters and results was passed indirectly, without exploding tuples. The next three examples will illustrate this.

\begin{example}
Let's modify the \texttt{apply()} function from \ExRef{ex:abstraction pattern 1} to receive an array of closures instead, while making the closure's parameter concrete:
\begin{Verbatim}
func apply1<T>(_ x: String, _ fns: [(String) -> T]) -> [T] {
  return fns.map { fn in fn(x) }
}
\end{Verbatim}
We can do the same but make the result concrete instead:
\begin{Verbatim}
func apply2<T>(_ x: T, _ fns: [(T) -> String]) -> [String] {
  return fns.map { fn in fn(x) }
}
\end{Verbatim}
Say we call both functions with an array containing some large number of closures:
\begin{Verbatim}
let fns: [(String) -> String] = [
  { $0.uppercased() },
  /* and more... */
]
apply1("hello ", "world", fns)
apply2("hello ", "world", fns)
\end{Verbatim}
We don't want to re-abstract every closure in the array before we pass it to \texttt{apply1()} and \texttt{apply2()}. Instead, when storing a closure in a generic container,  we re-abstract it into its most general form, where both the parameter and result are passed indirectly. This is accomplished by wrapping each closure in a \index{substituted-to-original thunk}substituted-to-original thunk before storing it in the array, and wrapping it again in an \index{original-to-substituted thunk}original-to-substituted thunk when loading it from the array.
\end{example}

An interesting \index{limitation!re-abstraction thunk}limitation of this implementation model is that re-abstraction thunks can nest, resulting in potentially unbounded memory usage. This was reported by a Swift developer on the forums~\cite{abstractleak}.

\begin{example}
Suppose we take an array of closures, repeatedly load each element from the array, and store it back without modification:
\begin{Verbatim}
var fns: [(String) -> String] = []

// Initialize the array
for n in 0 ..< 100 {
  array.append({ $0.lowercased() })
}

// Repeat this as many times as necessary
for _ in 0 ..< 1000 {
  for n in 0 ..< array.count {
    let fn = array[n]
    array[n] = fn
  }
}
\end{Verbatim}
Each loaded element will be wrapped with an \index{original-to-substituted thunk}original-to-substituted thunk, and this thunk will then be wrapped with a \index{substituted-to-original thunk}substituted-to-original thunk before being stored back to the same location in the array. Thus, each iteration will allocate a pair of closure contexts on the heap, and repeating will consume an arbitrary amount of memory.

For a simple example like the above, we could detect this situation, and either avoid emitting redundant thunks in \index{SILGen}SILGen, or clean up redundant thunks with a \index{SIL optimizer}SIL optimizer pass. A compile-time fix would not completely solve the problem, though, because we can just change the second ``\texttt{for}'' loop into the following:
\begin{Verbatim}
for _ in 0 ..< 1000 {
  for n in 0 ..< array.count {
    let fn = array[n]
    let fn2 = someFunction(fn)
    array[n] = fn2
  }
}
\end{Verbatim}
Perhaps \texttt{someFunction()} just returns its argument unchanged, but if its defined in another module, the compiler has no way to know this, because it cannot analyze its body, so we would encounter the same problem again. To solve this problem completely would require some kind of run time check when forming a re-abstraction thunk, to ``collapse'' multiple levels of nested thunks into one.
\end{example}

Our final example shows that a re-abstraction thunk may also need to explode and implode \index{tuple type!SIL type lowering}tuple types appearing in the formal function type's parameters and result.
\begin{example}
Consider a closure with formal type \texttt{(String, (Int, Bool)) -> ()}. Using its own formal type as the abstraction pattern, we get a SIL function type with three parameters and no results:
\begin{quote}
\begin{verbatim}
(@guaranteed String, Int, Bool) -> ()
\end{verbatim}
\end{quote}
The most general lowered type for this function type, however, is the following:
\begin{quote}
\begin{verbatim}
(@in_guaranteed String, @in (Int, Bool)) -> (@out ())
\end{verbatim}
\end{quote}
The latter lowered type receives the two-element tuple as a single indirect parameter. It also returns an empty tuple indirectly (an empty tuple value does not take up any space in memory, so there is nothing to load or store; however, the \index{calling convention}calling convention still allots a parameter to serve as the indirect result buffer). Now, if we are asked to emit a \index{substituted-to-original thunk!tuple type}substituted-to-original thunk to convert from the first type to the second, the thunk must explode the tuple and load both elements from memory before passing them directly to the wrapped closure. Likewise, an \index{original-to-substituted thunk!tuple type}original-to-substituted thunk must implode the last two lowered parameters into a single tuple value to be passed indirectly.
\end{example}

\paragraph{Optional payloads.}
Most \index{generic nominal type!SIL type lowering}generic nominal types use a uniform representation that does not depend on the abstraction pattern, and type lowering simply returns the original formal type unchanged when given such a formal type, ignoring the abstraction pattern. In particular, the generic arguments of generic nominal types are not themselves lowered.

Optional types are the exception. (Recall the declaration of \texttt{Optional} from \ExRef{ex:lowering optional}.) Optional function types are particularly common, and we don't want to pay the cost of allocating a re-abstraction thunk every time we wrap a function type with an optional, or unwrap an optional function type.

For this reason, SIL type lowering treats \index{optional type!re-abstraction}optional types as a special case. When lowering a formal optional type with an optional type as the abstraction pattern, we lower its payload type with the abstraction pattern's formal type, and form a \IndexDefinition{lowered optional type}lowered optional type from the result.

For example, consider the formal type \texttt{Optional<(String) -> String>}. Lowering this type with itself as the abstraction pattern yields the following---notice how the generic argument becomes a \index{SIL function type!optional payload}SIL function type, and this SIL function type receives its parameter and returns its result directly:
\begin{center}
\texttt{Optional<@convention(thick) (@guaranteed String) -> (@owned String)>}
\end{center}

Since the same formal optional type can map to one of several lowered optional types depending on the abstraction pattern, values of optional types may need to be re-abstracted. We accomplish this  by generating a conditional branch. If the active case is ``\texttt{none}'' we simply return this empty value. If the active case is ``\texttt{some}'' we wrap the payload in a re-abstraction thunk, and then wrap this thunk in a new optional value.

Finally, we are ready to look at the type lowering algorithm.

\begin{algorithm}[Lower type with abstraction pattern]\label{alg:compute lowered type}
Receives a \index{formal type}formal type~\tX\ and an \index{abstraction pattern}abstraction pattern \tY\ as input, together with an optional \index{generic signature!SIL type lowering}generic signature~$G$ in the case where \tY\ \index{type!containing type parameters}contains type parameters. Returns a lowered type. The structure of the abstraction pattern must match the formal type.
\begin{enumerate}
\item If \tX\ is a \index{function type!SIL type lowering}\textbf{function type}:
\begin{enumerate}
\item Walk the formal parameters of \tX\ and \tY\ in parallel:
\begin{enumerate}
\item Lower each formal parameter type using the corresponding formal parameter type of \tY\ as the abstraction pattern.
\item For any formal parameter of \tY\ that is a tuple type, explode the lowered type into multiple lowered parameters.
\item Compute a category for each lowered parameter type using \AlgRef{alg:lowered type category}.
\end{enumerate}
\item Consider the formal result types of \tX\ and \tY:
\begin{enumerate}
\item Lower the formal result type of \tX\ using the result type of \tY\ as the abstraction pattern.
\item If the formal result type of \tY\ is a tuple type, explode the lowered result type into multiple lowered results.
\item Compute a category for each lowered result type using \AlgRef{alg:lowered type category}.
\end{enumerate}
\item Collect the lowered parameter types, lowered result types, and their categories, to form a new \index{SIL function type}SIL function type.
\end{enumerate}

\item If \tX\ is a \index{tuple type!SIL type lowering}\textbf{tuple type}, walk the elements of \tX\ and \tY\ in parallel, and lower each element. Collect the lowered element types to form a lowered tuple type, and return the result.

\item If \tX\ is an \index{optional type!SIL type lowering}\textbf{optional type}:
\begin{enumerate}
\item Lower the payload type of \tX\ using the payload type of \tY\ as the abstraction pattern.
\item Form a new optional type from this lowered payload type.
\end{enumerate}

\item If \tX\ is a \index{struct type!SIL type lowering}\textbf{struct type}, \index{enum type!SIL type lowering}\textbf{enum type} (except for \texttt{Optional}, which was handled above), or \index{class type!SIL type lowering}\textbf{class type}, return \tX\ itself. (The formal type is already a lowered type in this case, and we ignore the abstraction pattern \tY.)
\end{enumerate}
\end{algorithm}

\paragraph{Substitution with lowered types.}
We're now going to investigate the meaning of applying a \index{substitution map!lowered type}substitution map to a \index{lowered type!type substitution}\index{type substitution!lowered type}lowered type. This is a common operation in the \index{SIL optimizer}SIL optimizer; for example, it is used to generate \index{specialization}specializations of generic functions. If the implementation of the function is visible from the call site, the optimizer can generate a specialization by cloning each SIL instruction in the function's body, and applying the substitution map from the call site.

A substitution map's \index{replacement type!SIL type lowering}replacement types are always \index{formal type!type substitution}formal types. When we substitute a type parameter appearing in a lowered type, we must sometimes lower the replacement type if it appears in a certain position. We always lower the replacement type with an opaque abstraction pattern. We do this precisely in those positions where \AlgRef{alg:compute lowered type} would lower a formal type that appears there. Such a position within a type is referred to as \IndexDefinition{lowered position}\emph{lowered position}. Lowered positions are defined recursively. The entire original lowered type is itself in lowered position. Furthermore:
\begin{enumerate}
\item A \index{SIL function type!lowered position}SIL function type can only appear in lowered position, and all of its parameter and result types are also in lowered position.
\item If a \index{tuple type!lowered position}tuple type appears in lowered position, its element types are also in lowered position.
\item If an \index{optional type!lowered position}optional type appears in lowered position, its generic argument is also in lowered position.
\end{enumerate}
If a type parameter occurs in any other position, the replacement type is not lowered, and it is substituted as-is.

Let's say that \tY~is an abstraction pattern, \tX~is a formal type, and $L(\tY, \tX)$ is the lowered type for~\tX\ with respect to~\tY. Finally, let ``$=$'' denote \index{canonical type equality}canonical type equality. In \ExRef{ex:abstraction pattern 1}, we saw that lowering a type with its own abstraction pattern is not, in general, compatible with type substitution---that is, $L(\tX, \tX) \otimes \Sigma \neq L(\tX \otimes \Sigma, \tX \otimes \Sigma)$. However, there is an identity relating type lowering with type substitution. When the abstraction pattern \tY\ remains unsubstituted and we apply a substitution map to both sides, it is always true that $L(\tY, \tX) \otimes \Sigma = L(\tY, \tX \otimes \Sigma)$.

\begin{example}
Let's apply $\SubstMap{\SubstType{\rT}{Int},\,\rU \mapsto \left[ \texttt{() -> String} \right] }$ to a pair of lowered types. First, consider the generic nominal type \texttt{Array<(\rT, \rU)>}. Neither of the two type parameters are in lowered position, so type substitution will replace them without lowering, and we just get \texttt{Array<(Int, () -> String)>}.

Now, suppose we apply $\Sigma$ to \texttt{Optional<(\rT, \rU)>}. Both type parameters are in lowered position, so type substitution will lower the replacement types with an \index{opaque abstraction pattern}opaque abstraction pattern. We see that while \texttt{Int} remains unchanged, the formal function type \texttt{() -> String} becomes a SIL function type, and we get:
\[
\texttt{Optional<(Int, @convention(thick) () -> (@out String))>}
\]
\end{example}

\paragraph{History.}
\IndexSwift{3.1}Swift~3.1 introduced the special type lowering support and re-abstraction for \index{optional type!SIL type lowering}optional payloads; prior to this, optional types were lowered like every other generic nominal type~\cite{optionalpayload}. The \index{opaque abstraction pattern}most general form of a \index{function type!SIL type lowering}function type changed in \IndexSwift{5.0}Swift~5, when \IndexFlag{language-mode}\verb|-swift-version 3| mode was dropped (these days, the \texttt{-swift-version} flag is named \texttt{-language-mode}, and the minimum supported language mode at the time of writing is~\texttt{4}). As we saw in \SecRef{sec:more types}, \IndexSwift{3.0}Swift~3 did not distinguish between function types that receive multiple parameters and function types with a single parameter of \index{tuple type!SIL type lowering}tuple type. Thus, in Swift~3, the most general form of a function type had to implode all parameters into a single indirect parameter of tuple type, which was somewhat inefficient. Resolving this was a strong impetus for dropping Swift~3 source compatibility~\cite{mostopaque}. Finally, \IndexSwift{5.6}Swift~5.6 introduced the peephole optimization allowing \index{SILGen}SILGen to emit a closure expression with an arbitrary abstraction pattern, rather than immediately wrapping it with a substituted-to-original thunk~\cite{emitabstract}.

\section{Source Code Reference}\label{src:substitution maps}

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

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

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

\apiref{GenericSignature}{class}
See also \SecRef{src:generic signatures}.
\begin{itemize}
\item \texttt{getIdentitySubstitutionMap()} returns the \IndexSource{identity substitution map}identity substitution map for this generic signature, that replaces each \IndexSource{generic signature!type substitution}generic parameter with itself.
\end{itemize}

\apiref{SubstitutionMap}{class}
A \IndexSource{substitution map}substitution map. Just like \texttt{Type} and \texttt{GenericSignature}, substitution maps are immutable and uniqued, and the representation of a \texttt{SubstitutionMap} fits in a single pointer, so they are cheap to pass by value.

The default \texttt{SubstitutionMap()} constructor constructs an \IndexSource{empty substitution map}empty substitution map. The implicit \texttt{bool} conversion tests for a non-empty substitution map. We defer our discussion of the entry points that build non-empty substitution maps to \SecRef{src:conformances}, since this involves passing in an array of conformances as well, and we haven't introduced conformances yet.

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 \IndexSource{input generic signature}input generic signature.
\item \texttt{getReplacementTypes()} returns an array of \texttt{Type}.
\item \texttt{hasAnySubstitutableParams()} answers if this substitution map's input generic signature contains at least one generic parameter that is not fixed to a concrete type (see the \texttt{GenericSignatureImpl::areAllParamsConcrete()} method from \SecRef{src:generic signatures}).
\end{itemize}

Recursive properties of replacement types:
\begin{itemize}
\item \texttt{hasPrimaryArchetypes()} answers if any of the replacement types contain \IndexSource{primary archetype}primary archetypes.
\item \texttt{hasOpenedExistential()} answers if any of the replacement types contain an \IndexSource{existential archetype}existential archetype.
\item \texttt{hasDynamicSelf()} answers if any of the replacement types contain the \IndexSource{dynamic Self type@dynamic \tSelf\ type}dynamic Self type.
\end{itemize}

A substitution map is \IndexSource{canonical substitution map}\emph{canonical} if all replacement types are \IndexSource{canonical type}canonical types and all conformances are \IndexSource{canonical conformance}canonical conformances. A substitution map is canonicalized by constructing a new substitution map from the original substitution map's canonicalized replacement types and conformances.
\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}

Substitution map composition (\SecRef{sec:composition}):
\begin{itemize}
\item \texttt{subst()} returns the \IndexSource{substitution map composition}composition of this substitution map on the left with the given substitution map on the right.
\end{itemize}

As with types, substitution maps have two levels of \IndexSource{substitution map equality}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. The \texttt{operator==} overloads implements pointer equality. Canonical equality can be tested by first canonicalizing both sides:
\begin{Verbatim}
if (subMap1.getCanonical() == subMap2.getCanonical())
  ...;
\end{Verbatim}
However, unlike types, checking two substitution maps for equality is rare. The fact that they are uniquely-allocated is more of a performance optimization than anything else.

\subsection*{Subclassing}

\apiref{ClassDecl}{class}
See also \SecRef{src:declarations}.
\begin{itemize}
\item \texttt{getSuperclass()} returns this \IndexSource{class declaration}class declaration's \IndexSource{superclass type}superclass type.
\end{itemize}

\apiref{Type}{class}
\begin{itemize}
\item \texttt{getSuperclass()} returns this \IndexSource{class type}class type's \IndexSource{superclass type}superclass type. This is \AlgRef{superclass type of type}.
\item \texttt{getSuperclassDecl()} returns this \IndexSource{class type}class type's \IndexSource{superclass declaration}superclass declaration. This is \AlgRef{superclassfordecl}.
\end{itemize}

\subsection*{SIL Types}

Key source files:
\begin{itemize}
\item \SourceFile{include/swift/AST/Types.h}
\item \SourceFile{include/swift/SIL/SILType.h}
\item \SourceFile{lib/SIL/IR/SILType.cpp}
\item \SourceFile{lib/SIL/IR/SILFunctionType.cpp}
\end{itemize}

A \IndexSource{lowered type}lowered type is represented as a \texttt{CanType}, just like a \IndexSource{formal type}formal type. Be forewarned that the distinction between the two is not enforced statically, and care must be taken not to get them mixed up.

\apiref{TypeBase}{class}
See also \SecRef{src:types}. Two methods distinguish formal types from lowered types:
\begin{itemize}
\item \texttt{isLegalFormalType()} checks if this is a legal formal type.
\item \texttt{isLegalSILType()} checks if this is a legal lowered type.
\end{itemize}

\apiref{SILValueCategory}{enum class}
In the implementation, whether a type is loadable or address-only is referred to as the lowered type's ``category.''
\begin{itemize}
\item \texttt{SILValueCategory::Object} is the category of loadable types.
\item \texttt{SILValueCategory::Address} is the category of address-only types.
\end{itemize}

\apiref{SILType}{class}
Combines a lowered type together with its category. SIL types can be taken apart:
\begin{itemize}
\item \texttt{getASTType()} returns the SIL type's lowered type as a \texttt{CanType}.
\item \texttt{getCategory()} returns the SIL type's category.
\end{itemize}
New SIL types can be constructed from a lowered type and a category as follows:
\begin{itemize}
\item \texttt{SILType::getPrimitiveObjectType()} is a static factory method that returns a new object SIL type for the given lowered type. The lowered type must be loadable.
\item \texttt{SILType::getPrimitiveAddressType()} is a static factory method that returns a new address SIL type for the given lowered type.
\end{itemize}
One can also call the \texttt{SILType} constructor with a lowered type and a \texttt{SILValueCategory}.

Note that all of the above requires already having a lowered type on hand; attempting to construct a SIL type from a formal type that is not a lowered type will result in a run time assertion. To construct a SIL type from a formal type, the formal type must be lowered first, as discussed below.

SIL types support down-casting to the various \texttt{TypeBase} subclasses that represent different kinds of lowered types. The \texttt{SILType} class declares three template methods, \verb|is<>()|, \verb|getAs<>|, and \verb|castTo<>|. These are equivalent to calling \texttt{getASTType()} and then passing the result to the top-level \verb|isa<>|, \verb|dyn_cast<>|, and \verb|cast<>| template functions discussed in \SecRef{src:types}.

The printed representation of a SIL type is \verb|$type| for a loadable type and \verb|$*type| for an address-only type, where \verb|type| is the printed representation of its lowered type. This printed representation shows up in \IndexFlag{emit-silgen}\verb|-emit-silgen| output, for example.

\apiref{SILFunctionType}{class}
A \texttt{TypeBase} subclass representing a \IndexSource{SIL function type}SIL function type.
\begin{itemize}
\item \texttt{getParameters()} returns an \texttt{ArrayRef<SILParameterInfo>} with the function's \IndexSource{lowered parameter}lowered parameters.
\item \texttt{getResults()} returns an \texttt{ArrayRef<SILResultInfo>} with the function's \IndexSource{lowered result}lowered results.
\item \texttt{getInvocationGenericSignature()} returns the function's \IndexSource{generic signature!SIL function type}generic signature.
\end{itemize}

In reality, generic SIL function types have a more complex representation than what we've described; see~\cite{substfunctype}.

\subsection*{SIL Type Lowering}

Key source files:
\begin{itemize}
\item \SourceFile{include/swift/SIL/AbstractionPattern.h}
\item \SourceFile{include/swift/SIL/TypeLowering.h}
\item \SourceFile{lib/SIL/IR/AbstractionPattern.cpp}
\item \SourceFile{lib/SIL/IR/TypeLowering.cpp}
\end{itemize}

\apiref{AbstractionPattern}{class}
An \IndexSource{abstraction pattern}abstraction pattern.
\begin{itemize}
\item \texttt{getKind()} returns the abstraction pattern's kind. See the source code for an explanation of the possible kinds.
\item \texttt{isTypeParameterOrOpaqueArchetype()} returns if this is an \IndexSource{opaque abstraction pattern}opaque abstraction pattern.
\item \texttt{getType()} returns the abstraction pattern's \IndexSource{formal type!abstraction pattern}formal type.
\end{itemize}

\apiref{TypeConverter}{class}
A singleton object responsible for \IndexSource{SIL type lowering}SIL type lowering.
\begin{itemize}
\item \texttt{getLoweredType()} takes a \texttt{CanType} representing a formal type, and returns a \texttt{SILType} which encodes the lowered type together with its category.
\item \texttt{getTypeLowering()} takes a \texttt{CanType} representing a formal type, and returns a \texttt{TypeLowering} object, which encodes the lowered type together with additional recursive properties computed by type lowering, such as whether the type is \IndexSource{trivial type}trivial.
\end{itemize}

\subsection*{Re-abstraction Thunks}

Key source files:
\begin{itemize}
\item \SourceFile{lib/SILGen/SILGenPoly.cpp}
\item \SourceFile{lib/SILGen/SILGenThunk.cpp}
\end{itemize}

\apiref{SILGenFunction}{class}
A class containing various entry points used by \IndexSource{SILGen}SILGen to emit the SIL functions. The following two entry points emit \IndexSource{re-abstraction thunk}re-abstraction thunks:
\begin{itemize}
\item \texttt{emitOrigToSubstValue()} re-abstracts a value from a given abstraction pattern to the ``natural'' abstraction pattern for its formal type. If the value has function type, this emits an \IndexSource{original-to-substituted thunk}original-to-substituted thunk.
\item \texttt{emitSubstToOrigValue()} re-abstracts a value from the ``natural'' abstraction pattern for its formal type to a given abstraction pattern. If the value has function type, this emits an  \IndexSource{substituted-to-original thunk}substituted-to-original thunk.
\end{itemize}

\subsection*{SIL Type Substitution}

Key source files:
\begin{itemize}
\item \SourceFile{lib/SIL/IR/SILTypeSubstitution.cpp}
\end{itemize}

\apiref{SILType}{class}
\IndexSource{type substitution!lowered type}SIL type substitution:
\begin{itemize}
\item \texttt{subst()} applies a \IndexSource{substitution map!lowered type}substitution map to a SIL type.
\end{itemize}

\apiref{SILTypeSubstituter}{class}
A \texttt{CanTypeVisitor} implementation used to implement the above.

\end{document}