The secret life of types in Swift

(Disclaimer: This is a post on my personal blog, not officially endorsed by Apple. It does not discuss any commitments to future plans, or official descriptions of anything we have done in the past. For that, see the Swift web site).

Being part of the Swift team has been very exciting for me since the open source release last December. When I joined Apple, I thought it would be great if the compiler were to be open sourced one day, but I did not really consider it a certainty when I went in for my interview and subsequently accepted the offer. So it truly blew my mind when I learned that not only would we release the compiler, but do all development in the open on GitHub, with a community-driven language evolution process.

The project has certainly generated a considerable amount of interest, attracting both outside contributions in the form of pull requests, as well as passionate discussion on the swift-evolution mailing list. The team has put considerable time and energy into driving the language evolution discussions. Unfortunately, I myself have not engaged much in this area, mostly because I feel my views on language design are biased by my previous experience, which has mostly consisted of low-level systems programming, and not applications for end-users; and also, because I’ve been too busy ramping up on the code base and trying to chip away at the very long list of tasks that still remain to be done on the implementation.

However, I think one area where we could do better with community engagement is spreading knowledge about the Swift implementation itself. Certainly when I first jumped into the codebase, I found it rather intimidating — coming from a dynamic language background, I realized I didn’t know how much I didn’t know! Static typing, runtime generics, and separate compilation introduce a level of complexity that can take some time to wrap one’s head around.

For the most part, the Swift compiler source code is well-structured with detailed comments, what seems to be missing is a “big picture” view of what’s going on. So I thought I could give back to the community by finding some time to write a few blog posts that discuss these things, to encourage contributors and hopefully make it easier for those who do not have the luxury of being able to stroll down the hallway to incessantly bug the original architects of the code (whose patience during my learning process is something I’m very grateful for).

So without further ado, I’m going to attempt to start by giving an overview of how types work in Swift, from the parser down to the lower layers of code generation in the frontend. Swift is a strong, statically-typed language with an advanced type system more reminisicent of functional languages such as OCaml and Haskell than something like C, so this seems like as good a place to start as any. Due to length, I’m going to split this writeup into four posts:

  • This first post will start by discussing type representations in the parser and semantic checking; so-called “formal types”
  • The second post (update: now up) will discuss SIL types, and the “SIL type lowering” process used to derive SIL types from formal types
  • The third post will discuss LLVM types, and IRGen’s “type lowering” which produces LLVM types from SIL types
  • The fourth and final post will dive into some more details of generic parameter types, shedding some light on the rather tricky “interface type” vs “archetype” distinction

For now, I’m intentionally going to skip over all of the type inference machinery; this is a huge topic in itself. Instead, I will focus on how types are represented, and the operations on types that are provided for use throughout the compiler.

If you’re just writing Swift code, this stuff will probably be of limited utility; certainly you should not feel like there is any need to understand this stuff, but perhaps peeking under the covers will help you figure out the more obscure corners of the language better.

A quick look at the Swift AST

The output of the parser is a syntax tree with three kinds of nodes:

  • Declarations — this includes structs, enums, classes, extensions, methods, and so on. Typically, a declaration has a name (except for extensions, which extend an existing named type), some kind of declared type, optional attributes, and a body, which might contain more declarations, or perhaps statements or expressions. Declarations are represented as subclasses of the Decl class, defined in include/swift/AST/Decl.h.
  • Statements — a statement is a line of code executed for its side effect. Statements include assignment operations, conditionals, loops, as well as miscallaneous control flow operations such as “return” and “break”. Unlike some functional languages, Swift separates statements from expressions. While we can debate the pros and cons of this all day, let’s take this as a given for now. In my opinion, this particular design choice simplifies some aspects of the grammar, and also allows the type inference to be limited to solving a local, per-statement problem, which helps reduce the algorithmic complexity of the problem, and produces more accurate, targeted diagnostics. Note that statements can contain things that have types, but themselves do not have a type. Statements are represented as subclasses of the Stmt class, defined in include/swift/AST/Stmt.h.
  • Expressions — an expression is a piece of code which evalutes to a value. Expressions can contain other expressions, essentially forming a tree. The leaf nodes among the expression kinds include literals, as well as declaration references, which includes references to local variables, functions, and so on. Examples of interior nodes here would be function calls, forming array and tuple literals, and so on. After type checking, each expression has a type. Expressions are represented as subclasses of the Expr class, defined in include/swift/AST/Expr.h.

The basic rule for how these nodes nest is that at the top level, you have a list of declarations. Some declarations, like class declarations, contain other declarations. Function declarations contain a body consisting of zero or more statements. Statements contain expressions. Some declarations, like variable declarations with an initial value, can directly contain expressions. Furthermore, Swift allows types and functions to be nested inside other functions, so functions can contain declarations also. Statements written at the top level of a file, which in Swift takes the place of an explicit “main” function, are actually nested inside a special ‘TopLevelCodeDecl’ by the parser.

Like most modern languages, Swift entirely separates parsing from name lookup and type checking. So you can imagine that the output of the parser is syntactically valid, but the names referenced within do not have any semantic meaning, and are resolved as part of semantic analysis.

TypeLocs, TypeReprs, and Types

The three most important data types for representing types in the AST are the following:

  • A TypeLoc or “type location” is a source location where a type can be written down by the user. A TypeLoc consists of a TypeRepr together with a Type; initially, there is no Type, only a TypeRepr. During semantic checking, the TypeRepr is resolved to a Type and stored back into the TypeLoc.
  • A TypeRepr or “type representation” is a purely syntactic representation of a written type in source form. It might reference a named type declaration, or a type alias, or a type nested inside some other type, or it may not be valid at all. TypeReprs do not directly reference declarations; the declarations are resolved via unqualified or qualified name lookups when we build Types.
  • A Type is a fully-parsed semantic type that either consists of a composition of simpler types, or directly references a declaration. Note that the Type class is a value type wrapping a pointer to a TypeBase, much like a smart pointer. TypeBase defines most of the methods for manipulating types, and ‘operator->’ is overloaded on Type to delegate to the underlying TypeBase. For the most part, you write code to pass around Types, not ‘TypeBase *’.

Examples of TypeLocs include the parameter types and return type in a function declaration:

func square(x: Int) -> Int { return x * x }
func map(fn: (T) -> T) -> [T] { ... }

Another example is the superclass of a class, or the declared type of a variable:

class FileTreeModel : TreeModel<File> {
var folder: Folder
}

Note that most expressions do not have a corresponding TypeLoc, except for expressions with explicit types written, such as casts or metatype references (like “Int.self”). Expressions do have a Type though, after type checking, which is the formal type of their evaluated value.

In the above examples, the following are all TypeReprs:

Int  // a simple TypeRepr consisting of a single named component
T // another simple TypeRepr -- presumably this names a generic parameter, but until semantic analysis completes, we do not know the difference
(T) -> T // a FunctionTypeRepr, with child TypeReprs for the input and result type
[T] // an ArrayTypeRepr, with a child TypeRepr for the element type
TreeModel<File> // a BoundGenericTypeRepr, with a child TypeRepr for the base type, and a list of TypeReprs for the generic parameters

The main entry point for resolving a TypeRepr to a Type is the resolveType() function, defined in TypeCheckType.cpp. This file also contains a large number of other functions, used elsewhere in semantic analysis to look up and manipulate types.

Note that in some compilers, the operation of resolving a type is called realizing a type. I prefer this term myself, since “resolve” tends to be somewhat ambiguous — we talk about resolving overloads, resolving method overrides, resolving names, and so on.

Unless you are working in the parser or early phases of semantic analysis, for example adding fixits or similar, you will very rarely encounter TypeLocs or TypeReprs. For the most part in Swift, we only need to manipulate fully-formed Types.

Different kinds of types

So now, let’s leave the land of parsing and move on to semantic analysis. You can think of the class hierarchy under the TypeBase class as defining a simple language for representing types in the rest of the compiler. The common kinds are familiar to any Swift programmer:

// NominalType -- a non-generic struct, enum or class
Int, NSPostingStyle, UIView
// ProtocolType -- a type of some value conforming to a protocol, whose concrete type is only known at run time
UIApplicationDelegate
// ProtocolCompositionType -- a type of some value conforming to zero or more protocols
protocol<> // More commonly known as 'Any'
protocol<StringLiteralConvertible, IntegerLiteralConvertible>
// BoundGenericType -- a generic struct, enum or class
Array<String>, Optional<Int>, Cache<NSString, UIImage>
// TupleType -- a product of zero or more types
()
(Int, String, Set<Character>)
// FunctionType -- a function value with an input and result type, and possibly some attributes
(Array<String>) -> String
@convention(c) (Int) -> Int
(Int) throws -> ()
// MetatypeType -- the type of a type
Int.Type
UIApplicationDelegate.Protocol
// ExistentialMetatypeType -- the type of all types conforming to a protocol
UIApplicationDelegate.Type

Note how some types are “leaf” nodes in the sense that they reference declarations, whereas others are structural types, consisting of a composition of zero or more subordinate types. While the basic Type type is defined in include/swift/AST/Type.h, specific subclasses are all found in include/swift/AST/Types.h.

An aside — when working with Type values in the debugger, you can call the dump() method on one to dump it in a longer, “s-expression” like form — this is very useful for understanding exactly what’s going on:

(lldb) print ((ValueDecl *)D)->getType().dump()
(function_type
(input=tuple_type num_elements=2
(tuple_type_elt name=x
(struct_type decl=Swift.(file).Int))
(tuple_type_elt name=y
(struct_type decl=Swift.(file).String)))
(output=tuple_type num_elements=0))

Also, notice how I intentionally omitted certain “sugared” types that have a more explicit written representation, including the built-in shorthand for optionals, arrays, dictionaries, as well as type aliases:

Int?  // Can also be written as Optional<Int>
[String] // Can also be written as Array<String>
[Int : String] // Can also be written as Dictionary<Int, String>
typealias T = <some type goes here>
T // Can always be written as <some type goes here>

I’ll discuss sugared types very shortly.

Finally, I haven’t talked about generic type parameters or associated types either. These are somewhat special, since their meaning is derived from the lexical context in which they appear; more on that below.

Sugared types and canonical types

As promised, let’s look more closely at sugared types. You will notice that with the language of types as defined above, there are multiple ways to write the same semantic type in the language:

(Array<Optional<Int>>) -> Bool
([Int?]) -> Bool
(Flag, Flag) -> ()  // assuming we have 'typealias Flag = Bool'
(Bool, Bool) -> ()
typealias Void = ()  // defined in standard library
(Int) -> ()
(Int) -> Void

Generally, we want to preserve the sugar so that diagnostics can spit out types in the same form that they were written by the user; in particular, you can imagine code that makes heavy use of typealiases would be considerably more difficult to debug if your compiler errors stripped them away.

On the other hand, this sugaring has no semantic meaning — for example, it does not make sense to provide two overloads of the same method that only differ by sugared types. Further down in the compiler, once we are done producing diagnostics, the sugaring serves no purpose at all.

So we want a convenient way to strip off type sugar, and also ensure that structural equality of types corresponds to semantic equality.

The CanType data type, defined in Type.h, represents a desugared Type which has furthermore been memoized. The ‘TypeBase::getCanonicalType()’ method returns a CanType. This method first canonicalizes any subordinate types of the given type, and then either produces a new unique CanType, or returns an existing CanType. This allows CanTypes to be compared for pointer equality, and used as hashtable keys. Lower-level code for manipulating types always tends to use CanTypes for this reason, since it gives a small performance boost, and simplifies logic from having to look at sugared types at all.

Generic type parameters and associated types

Generic type parameters appear inside lexical contexts that have a generic signature. Generic signatures are either attached to type declarations, or function declarations:

struct Box<Contents> {
let value: Contents // Contents is a generic parameter

func transform<NewContents>(fn: (Contents) -> NewContents)
-> Box<NewContents> {
// Both Contents and NewContents are generic parameters,
// coming from two different generic signatures
return Box<NewContents>(value: fn(value))
}
}

A GenericTypeParamType is uniquely identified by two indices:

  • A depth, which identifies the generic signature it is part of — depth 0 is the outermost generic signature, depth 1 is the next innermost signature, and so on
  • An index, which identifies a generic parameter of a generic signature at the given depth

In the above example, we have two generic parameters appearing in the type of the transform() method:

  • ‘Contents’, which has depth 0, index 0
  • ‘NewContents’, which has depth 1, index 0

When a GenericTypeParamType is realized from a TypeRepr, it references the original GenericTypeParamDecl. After canonicalization, a GenericTypeParamType loses any association with its original lexical declaration, consisting only of a depth and index. This is why non-canonical GenericTypeParamTypes print as the name of the original generic parameter in the source, whereas canonical GenericTypeParamTypes have a more opaque printed representation, which you can find in SIL code, consisting of τ followed by the depth and index, for example ‘τ_0_1’.

Generic signatures are represented by the GenericSignature class, defined in include/swift/AST/GenericSignature.h. Roughly speaking, a generic signature is a list of generic type parameters, together with constraints placed upon them. The above examples do not place any constraints on generic parameters; examples of constraints include conformance requirements, same-type constraints, and so on:

func flip<T : Sequence>(t: T)
func parallelWalk<Left : Sequence, Right : Sequence>(
left: Left, right: Right)
where Left.Iterator.Element == Right.Iterator.Element

(Aside — the syntactic representation of a generic parameter list is the GenericParamList type, defined in include/swift/AST/Decl.h. GenericSignatures are formed as part of semantic checking. There is a rough analogy between GenericParamList and TypeRepr, and their realized representation, GenericSignature and Type).

Here are some types containing generic parameters:

// GenericFunctionType -- a function type with a generic signature
<T, U> (T, U) -> (U, T)
// A BoundGenericType containing a GenericTypeParamType -- the type of a generic parameter
Array<T>
// A FunctionType containing a DependentMemberType -- the type of an associated type of a generic parameter conforming to a protocol
(T.Element) -> ()

Generic function types are funny in that we can never have values carry a generic function type — Swift’s type system does not support rank-2 polymorphism. Instead, generic function types are reserved for the types of named declarations only, which ML geeks will recognize as analogous to the “let polymorphism” restriction in ML. While we’re on the subject of type theoretic geekery, it is also worth mentioning that the left-hand side of a BoundGenericType cannot be a type parameter either, and must always name a nominal type declaration; again, for various reasons, mostly sanity, Swift does not support higher-kinded types.

Back to reality. A DependentMemberType always has a base type which is another DependentMemberType, or a GenericTypeParamType. When you reference an associated type of a concrete type, for example something silly like the following, the type is desugared at the same time it is realized, so you should never see DependentMemberTypes of concrete types in SIL, for example:

Array<Int>.Iterator.Element  // just desugars to Int

(An aside — Swift appropriates the C++ definition of “dependent type”, which simply means a type containing generic parameter types. When we talk about dependent types, we always mean this definition, and not the more common definition from type theory which is a type parametrized by a value — a much more advanced concept that Swift’s type checker does not support).

Now if you’re reading this and you have some experience with the Swift compiler, you might actually know that the above is itself a simplification, since there are two representations of generic parameters in Swift:

  • “Interface types”, which are the GenericTypeParamTypes and DependentMemberTypes I mentioned above
  • “ArchetypeTypes”, which are a lower-level representation, more convenient to use in some cases, as well as the PolymorphicFunctionType which we are working on eliminating at some point (don’t get me started on this one… suffice to say I will not discuss it in these posts)

I’ll leave a detailed discussion of interface types and archetypes for the final post — for now, the main thing to remember is that the types of declarations are written in terms of interface types, whereas the types of expressions are written in terms of archetypes. For the rest of the below discussion, I’ll focus on interface types.

Substitutions

Types containing generic parameters give rise to the first interesting operation that we see performed on types, and it is one that appears throughout the codebase. This operation is substitution. Substitution is performed by invoking the ‘Type::subst()’ method on an instance of the Type class.

Conceptually, substitution is very simple — given a type containing generic parameter types, we provide a mapping from each generic parameter to some concrete type, and we replace each occurrence of the generic parameter with the replacement type.

The major complication here is DependentMemberTypes. Suppose we are given a type like the following, where we have a generic signature with ‘<T : Sequence>’, and the substitution maps ‘T’ to ‘Array<Int>’:

(T.Iterator.Element) -> T

Substitution walks into the FunctionType, recursively applying the substitution to the input and result types. Upon encountering the DependentMemberType ‘T.Iterator.Element’, it needs to perform a conformance lookup to get the concrete type for the associated type Iterator in the Sequence protocol, followed by another conformance lookup to get the concrete type for the associated type Element in IteratorProtocol.

In fact, there are two representations used for substitution mapping in the compiler; one, named TypeSubstitutionMap, is a straightforward hashtable mapping generic parameter types to concrete types:

typedef llvm::DenseMap<TypeBase *, Type> TypeSubstitutionMap

The other is a lower-level array whose elements are a special Substitution type, defined in include/swift/AST/Substitution.h. The two differences between these representations are the following:

  • With the former, the substitution operation must perform conformance lookups, whereas in the latter, the Substitution values carry conformances within them, saving a lookup and potentially allowing local conformances.
  • With the former, the generic parameters being substituted are part of the map, where as in the latter, they are implicit; the array elements must correspond to the order of generic parameters defined in the generic signature, otherwise the substitution makes no sense.

The post discussing interface types vs archetypes will also go into more detail about when these two representations are used, and why.

For now, don’t worry about it too much. The ‘ArrayRef<Substitution>’ representation is important with some cases involving same-type constraints, as well as being central to the implementation of Joe Groff’s experimental property behaviors feature. If you are writing some code and you are given an ‘ArrayRef<Substitution>’ but you really want a TypeSubstitutionMap, you need to get the right GenericSignature, and use the ‘GenericSignature::getSubstitutionMap()’ method to convert between the two representations.

Finally, a word about GenericFunctionTypes. Technically speaking, the generic type parameters appearing inside a GenericFunctionType are not “free”, because they are bound by the GenericFunctionType’s generic signature. So the subst() method does not walk into GenericFunctionTypes. Substituting the generic parameters of a GenericFunctionType is conceptually a separate operation, performed by calling the ‘GenericFunctionType::substGenericArgs()’ method. This method returns a FunctionType.

Types of members

Consider some code like the following:

struct TransformableBox<Contents> {
var value: Contents
var transform: (Contents) -> Contents
}
let myBox: TransformableBox<Int>

What is the type of ‘myBox.transform’? Intuitively, you would guess it is ‘Int -> Int’, and you would be right. How do we get that inside the compiler, though? The type of the declaration of transform is ‘Contents -> Contents’, written in terms of the generic parameters of TransformableBox’s generic signature. Clearly, we need to apply some kind of substitution mapping to it.

The substitutions come from the type of the value ‘myBox’. The type of myBox is a BoundGenericType that points to the declaration of TransformableBox. However, it also has a list of generic parameters. The ‘TypeBase::gatherAllSubstitutions()’ method returns all substitutions that are necessary, if there are any, that must be applied to the members of the referenced declaration. In our case, it produces a substitution map with a single element, mapping the Contents generic parameter to ‘Int’.

There are some utility methods that grab the substitution and apply it in one shot, most importantly ‘TypeBase::getTypeOfMember()’. In particular, there is a tricky case with inheritance where this method provides additional logic necessary for correctness; we’ll discuss this after looking briefly at nested generic types below.

Nested types

While no released version of the Swift compiler fully supports nested generic types, there is some support now in the master branch, guarded by the ‘-enable-experimental-nested-generic-types’ flag. The flag is a mouthful, because not everything works yet. However, it is worth discussing some issues specific to this feature, since going forward it would be great if everyone could do the right thing with nested generic types.

Consider some code like the following:

struct Outer<T> {
let value: T

struct Inner<U> {
let operation: (T) -> U
}
}
let myValue: Outer<Int>.Inner<String>

What is the type of ‘myValue’? At the very least, it is a BoundGenericType which references the ‘Inner’ declaration, with a generic parameter list consisting of ‘String’. However that in itself is not enough. Indeed, both BoundGenericType and NominalType also have a parent type, which provides generic substitutions for outer generic contexts. So in this case, the parent type of the type of ‘myValue’ is ‘Outer<Int>’. The ‘TypeBase::gatherAllSubstitutions()’ method knows to walk parent types, in this collecting a substitution map mapping ‘T’ to ‘Int’ and ‘U’ to ‘String’. It is important for this reason to use ‘TypeBase::gatherAllSubstitutions()’ where possible, instead of walking the generic parameters yourself, to avoid missing the parent substitutions.

Types of members versus inheritance

You will notice the superclass of a class is represented as a type, not a declaration. This is because we can apply generic parameters of the superclass when inheriting from it, for example:

class BaseClass<T> {
var value: T
}
class DerivedClass : BaseClass<String> {}
var myInstance: DerivedClass

What is the type of ‘myInstance.value’? The member comes from a different declaration than the declaration of the type of the instance, so we have to walk the inheritance hierarchy, very carefully tracking substitutions along the way. The ‘TypeBase::getTypeOfMember()’ method encapsulates the logic for doing this; save yourself some effort by not duplicating it yourself.

Unbound generic types

In some contexts, Swift allows you to omit the generic parameters of a generic type. For example,

struct Box<Contents> {
let value: Contents
}
func giveMeABox() -> Box<Int> {
return Box(value: 123)
}

Here, the generic parameters of ‘Box’ are inferred from context. To represent a generic type whose parameters are not known yet, the special UnboundGenericType type is used. This type tends to only appear early on in semantic analysis, and not in SILGen or below. Keep an eye out for it, since it often creates interesting special cases that are easy to miss.

Higher-order operations on types

Sometimes it is necessary to walk all the structural components of a Type, either collecting some information about them, or transforming them to produce new Types (type substitution is a special case of the latter). For this purpose, Swift defines various utilities to save you considerable effort:

  • The TypeVisitor class is an abstract base class, defining a ‘visit*()’ method for each TypeBase subclass. It has a single concrete method ‘visit()’, which takes a Type and dispatches to one of the subordinate ‘visit*()’ methods.
  • The ‘TypeBase::visit()’ method is a simpler version of the above, taking a lambda which is invoked on each structural component of the type.
  • The ‘TypeBase::findIf()’ method is a variant which takes a lambda returning a boolean; the overall method returns true if the lambda returned true for any structural component of the type.
  • The ‘TypeBase::transform()’ method takes a lambda which returns a new Type; it walks each structural component of the type, transforming it by calling the lambda, and forming a new overall type with all structural components transformed.

Often, it is necessary to check if a type contains a structural component that satisfies one of a common set of properties. For example, we might want to know if a type is fully concrete, or contains at least one unsubstituted generic parameter. Or, we might want to know if a type contains the special “dynamic Self” type, used in methods with covariant returns.

Instead of calling ‘findIf()’ with a predicate, it is faster to pre-compute these predicates when types are formed. For this reason, you will find methods such as ‘hasTypeParameter()’, ‘hasArchetype()’, ‘hasDynamicSelf()’, and others, which perform these checks more efficiently than ‘findIf()’. Watch out when calling these checks on non-canonical types though — they do not walk into the underlying types of type aliases. It generally only makes sense to perform these checks on canonical types, although you will find cases where they can be correctly used with sugared types also.

Next steps

Now that we’ve looked at formal types, the next frontier is to understand how SIL views types. In SIL, a lower-level notion of type makes certain aspects of the function calling convention more explicit, such as whether values can be passed directly in registers or passed indirectly. This is very important for Swift’s implementation of runtime generics. Finally, we’ll look at how IRGen maps operations on values of different types to low-level LLVM IR, at which point details such as the size and alignment of types become explicit.

Conclusion

Types in Swift form a mini-language in of themselves, with a grammar consisting of nominal types as leaves, and structural types such as function types as interior nodes. Types are formed from TypeLocs and TypeReprs early on in semantic analysis. Further down in the compiler, sugar is removed and types are canonicalized, simplifying structural walks and equality comparisons. Substitution is a fundamental operation frequently used in the implementation of generics, and it is important to think about the role of types and declarations when performing substitutions for member access. Various higher-order operations simplify tedious boilerplate when manipulating types throughout the compiler.

But this is only the beginning — SIL types can get pretty hairy! Stay tuned.