Introduction

Advanced Swift is quite a bold title for a book, so perhaps we should start with what we mean by it.

When we began writing the first edition of this book, Swift was barely a year old. We did so before the beta of 2.0 was released — albeit tentatively, because we suspected the language would continue to evolve as it entered its second year. Few languages — perhaps no other language — have been adopted so rapidly by so many developers.

But that left people with unanswered questions. How do you write “idiomatic” Swift? Is there a correct way to do certain things? The standard library provided some clues, but even that has changed over time, dropping some conventions and adopting others. Over the past two years, Swift has evolved at a high pace, and it has become clearer what idiomatic Swift is.

To someone coming from another language, Swift can resemble everything you like about your language of choice. Low-level bit twiddling can look very similar to (and can be as performant as) C, but without many of the undefined behavior gotchas. The lightweight trailing closure syntax of map or filter will be familiar to Rubyists. Swift generics are similar to C++ templates, but with type constraints to ensure generic functions are correct at the time of definition rather than at the time of use. The flexibility of higher-order functions and operator overloading means you can write code that’s similar in style to Haskell or F#. And the @objc keyword allows you to use selectors and runtime dynamism in ways you would in Objective-C.

Given these resemblances, it’s tempting to adopt the idioms of other languages. Case in point: Objective-C example projects can almost be mechanically ported to Swift. The same is true for Java or C# design patterns. And monad tutorials appeared to be everyone’s favorite blog post topic in the first few months after Swift’s introduction.

But then comes the frustration. Why can’t we use protocol extensions with associated types like interfaces in Java? Why are arrays not covariant in the way we expect? Why can’t we write “functor?” Sometimes the answer is because the part of Swift in question isn’t yet implemented. But more often, it’s either because there’s a different Swift-like way to do what you want to do, or because the Swift feature you thought was like the equivalent in some other language is not quite what you think.

Swift is a complex language — most programming languages are. But it hides that complexity well. You can get up and running developing apps in Swift without needing to know about generics or overloading or the difference between static and dynamic dispatch. You may never need to call into a C library or write your own collection type, but after a while, we think you’ll find it necessary to know about these things — either to improve your code’s performance, to make it more elegant or expressive, or just to get certain things done.

Learning more about these features is what this book is about. We intend to answer many of the “How do I do this?” or “Why does Swift behave like that?” questions we’ve seen come up on various forums. Hopefully, once you’ve read our book, you’ll have gone from being aware of the basics of the language to knowing about many advanced features and having a much better understanding of how Swift works. Being familiar with the material presented is probably necessary, if not sufficient, for calling yourself an advanced Swift programmer.

Who Is This Book For?

This book targets experienced (though not necessarily expert) programmers — such as existing Apple-platform developers, or those coming from other languages such as Java or C++ — who want to bring their knowledge of Swift to the same level as that of Objective-C or some other language. It’s also suitable for new programmers who started on Swift, have grown familiar with the basics, and are looking to take things to the next level.

It’s not meant as an introduction to Swift; it assumes you’re familiar with the syntax and structure of the language. If you want some good, compact coverage of the basics of Swift, the best source is the official Apple Swift book (available on iBooks or on Apple’s website). If you’re already a confident programmer, you could try reading both our book and the Apple Swift book in parallel.

This is also not a book about programming for OS X or iOS devices. Of course, since Swift is currently mainly used on Apple platforms, we’ve tried to include examples of practical use, but we hope this book will be useful for non-Apple-platform programmers as well.

Themes

We’ve organized the book under the heading of basic concepts. There are in-depth chapters on some fundamental basic concepts like optionals or strings, and some deeper dives into topics like C interoperability. But throughout the book, hopefully a few themes regarding Swift emerge:

Swift is both a high- and low-level language. Swift allows you to write code similarly to Ruby and Python, with map and reduce, and to write your own higher-order functions easily. Swift also allows you to write fast code that compiles directly to native binaries with performance similar to code written in C.

What’s exciting to us, and what’s possibly the aspect of Swift we most admire, is that you’re able to do both these things at the same time. Mapping a closure expression over an array compiles to the same assembly code as looping over a contiguous block of memory does.

However, there are some things you need to know about to make the most of this feature. For example, it will benefit you to have a strong grasp on how structs and classes differ, or an understanding of the difference between dynamic and static method dispatch. We’ll cover topics such as these in more depth later on.

Swift is a multi-paradigm language. You can use it to write object-oriented code or pure functional code using immutable values, or you can write imperative C-like code using pointer arithmetic.

This is both a blessing and a curse. It’s great, in that you have a lot of tools available to you, and you aren’t forced into writing code one way. But it also exposes you to the risk of writing Java or C or Objective-C in Swift.

Swift still has access to most of the capabilities of Objective-C, including message sending, runtime type identification, and KVO. But Swift introduces many capabilities not available in Objective-C.

Erik Meijer, a well-known programming language expert, tweeted the following in October 2015:

At this point, @SwiftLang is probably a better, and more valuable, vehicle for learning functional programming than Haskell.

Swift is a good introduction to a more functional style through its use of generics, protocols, value types, and closures. It’s even possible to write operators that compose functions together. The early months of Swift brought many functional programming blog posts into the world. But since the release of Swift 2.0 and the introduction of protocol extensions, this trend has shifted.

Swift is very flexible. In the introduction to the book On Lisp, Paul Graham writes that:

Experienced Lisp programmers divide up their programs differently. As well as top-down design, they follow a principle which could be called bottom-up design– changing the language to suit the problem. In Lisp, you don’t just write your program down toward the language, you also build the language up toward your program. As you’re writing a program you may think “I wish Lisp had such-and-such an operator.” So you go and write it. Afterward you realize that using the new operator would simplify the design of another part of the program, and so on. Language and program evolve together.

Swift is a long way from Lisp. But still, we feel like Swift shares this characteristic of encouraging “bottom-up” programming — of making it easy to write very general reusable building blocks that you then combine into larger features, which you then use to solve your actual problem. Swift is particularly good at making these building blocks feel like primitives — like part of the language. A good demonstration of this is that the many features you might think of as fundamental building blocks, like optionals or basic operators, are actually defined in a library — the Swift standard library — rather than directly in the language. Trailing closures enable you to extend the language with features that feel like they’re built in.

Swift code can be compact and concise while still being clear. Swift lends itself to relatively terse code. There’s an underlying goal here, and it isn’t to save on typing. The idea is to get to the point quicker and to make code readable by dropping a lot of the “ceremonial” boilerplate you often see in other languages that obscure rather than clarify the meaning of the code.

For example, type inference removes the clutter of type declarations that are obvious from the context. Semicolons and parentheses that add little or no value are gone. Generics and protocol extensions encourage you to avoid repeating yourself by packaging common operations into reusable functions. The goal is to write code that’s readable at a glance.

At first, this can be off-putting. If you’ve never used functions like map, filter, and reduce before, they might look harder to read than a simple for loop. But our hope is that this is a short learning curve and that the reward is code that is more “obviously correct” at first glance.

Swift tries to be as safe as is practical, until you tell it not to be. This is unlike languages such as C and C++ (where you can be unsafe easily just by forgetting to do something), or like Haskell or Java (which are sometimes safe whether or not you like it).

Eric Lippert, one of the principal designers of C#, wrote about his 10 regrets of C#, including the lesson that:

sometimes you need to implement features that are only for experts who are building infrastructure; those features should be clearly marked as dangerous—not invitingly similar to features from other languages.

Eric was specifically referring to C#’s finalizers, which are similar to C++ destructors. But unlike destructors, they run at a nondeterministic time (perhaps never) at the behest of the garbage collector (and on the garbage collector’s thread). However, Swift, being reference counted, does execute a class’s deinit deterministically.

Swift embodies this sentiment in other ways. Undefined and unsafe behavior is avoided by default. For example, a variable can’t be used until it’s been initialized, and using out-of-bounds subscripts on an array will trap, as opposed to continuing with possibly garbage values.

There are a number of “unsafe” options available (such as the unsafeBitcast function, or the UnsafeMutablePointer type) for when you really need them. But with great power comes great undefined behavior. You can write the following:

var someArray = [1,2,3]
let uhOh = someArray.withUnsafeBufferPointer { ptr in
    // ptr is only valid within this block, but
    // there is nothing stopping you letting it
    // escape into the wild:
    return ptr
}
// Later...
print(uhOh[10])

It’ll compile, but who knows what it’ll do. However, you can’t say nobody warned you.

Swift is an opinionated language. We as authors have strong opinions about the “right” way to write Swift. You’ll see many of them in this book, sometimes expressed as if they’re facts. But they’re just, like, our opinions, man. Feel free to disagree! Swift is still a young language, and many things aren’t settled. What’s more is that many blog posts are flat-out wrong or outdated (including several ones we wrote, especially in the early days). Whatever you’re reading, the most important thing is to try things out for yourself, check how they behave, and decide how you feel about them. Think critically, and beware of out-of-date information.

Terminology

‘When I use a word,’ Humpty Dumpty said, in rather a scornful tone, ‘it means just what I choose it to mean — neither more nor less.’

— Through the Looking Glass, by Lewis Carroll

Programmers throw around terms of art a lot. To avoid confusion, what follows are some definitions of terms we use throughout this book. Where possible, we’re trying to adhere to the same usage as the official documentation, or sometimes a definition that’s been widely adopted by the Swift community. Many of these definitions are covered in more detail in later chapters, so don’t worry if not everything makes sense on first reading. If you’re already familiar with all of these terms, it’s still best to skim through to make sure your accepted meanings don’t differ from ours.

In Swift, we make the distinctions between values, variables, references, and constants.

A value is immutable and forever — it never changes. For example, 1, true, and [1,2,3] are all values. These are examples of literals, but values can also be generated at runtime. The number you get when you square the number five is a value.

When we assign a value to a name using var x = [1,2], we’re creating a variable named x that holds the value [1,2]. By changing x, e.g. by performing x.append(3), we didn’t change the original value. Rather, we replaced the value that x holds with the new value, [1,2,3] — at least logically, if not in the actual implementation (which might actually just tack a new entry on the back of some existing memory). We refer to this as mutating the variable.

We can declare constant variables (constants, for short) with let instead of var. Once a constant has been assigned a value, it can never be assigned a new value.

We also don’t need to give a variable a value immediately. We can declare the variable first (let x: Int) and then later assign a value to it (x = 1). Swift, with its emphasis on safety, will check that all possible code paths lead to a variable being assigned a value before its value can be read. There’s no concept of a variable having an as-yet-undefined value. Of course, if the variable was declared with let, it can only be assigned to once.

Structs and enums are value types. When you assign one struct variable to another, the two variables will then contain the same value. You can think of the contents as being copied, but it’s more accurate to say that one variable was changed to contain the same value as the other.

A reference is a special kind of value: a value that “points to” another value. Because two references can refer to the same value, this introduces the possibility of that value getting mutated by two different parts of the program at once.

Classes are reference types. You can’t hold an instance of a class (which we might occasionally call an object — a term fraught with troublesome overloading!) directly in a variable. Instead, you must hold a reference to it in a variable and access it via that reference.

Reference types have identity — you can check if two variables are referring to the exact same object by using ===. You can also check if they’re equal, assuming == is implemented for the relevant type. Two objects with different identity can still be equal.

Value types don’t have identity. You can’t check if a particular variable holds the “same” number 2 as another. You can only check if they both contain the value 2. === is really asking: “Do both these variables hold the same reference as their value?” In programming language literature, == is sometimes called structural equality, and === is called pointer equality or reference equality.

Class references aren’t the only kind of reference in Swift. For example, there are also pointers, accessed through withUnsafeMutablePointer functions and the like. But classes are the simplest reference type to use, in part because their reference-like nature is partially hidden from you by syntactic sugar. You don’t need to do any explicit “dereferencing” like you do with pointers in some other languages. (We’ll cover the other kind of references in more detail in the chapter on interoperability.)

A variable that holds a reference can be declared with let — that is, the reference is constant. This means that the variable can never be changed to refer to something else. But — and this is important — it doesn’t mean that the object it refers to can’t be changed. So when referring to a variable as a constant, be careful — it’s only constant in what it points to. It doesn’t mean what it points to is constant. (Note: if those last few sentences sound like doublespeak, don’t worry, as we cover this again in the chapter on structs and classes). Unfortunately, this means that when looking at a declaration of a variable with let, you can’t tell at a glance whether or not what’s being declared is completely immutable. Instead, you have to know whether it’s holding a value type or a reference type.

We refer to types as having value semantics to distinguish a value type that performs a deep copy. This copy can occur eagerly (whenever a new variable is introduced) or lazily (whenever a variable gets mutated).

Here we hit another complication. If our struct contains reference types, the reference types won’t automatically get copied upon assigning the struct to a new variable. Instead, the references themselves get copied. This is called a shallow copy.

For example, the Data struct in Foundation is a wrapper around the NSData reference type. However, the authors of the Data struct took extra steps to also perform a deep copy of the NSData object whenever the Data struct is mutated. They do this efficiently using a technique called copy-on-write, which we’ll explain in the chapter on structs and classes. For now, it’s important to know that this behavior doesn’t come for free.

The collections in Swift are also wrapping reference types and use copy-on-write to efficiently provide value semantics. However, if the elements in a collection are references (for example, an array containing objects), the objects won’t get copied. Instead, only the references get copied. This means that a Swift array only has value semantics if the elements have value semantics too. In the next chapter, we’ll look at how Swift’s collections differ from Foundation collections such as NSArray and NSDictionary.

Some classes are completely immutable — that is, they provide no methods for changing their internal state after they’re created. This means that even though they’re classes, they also have value semantics (because even if they’re shared, they can never change). Be careful though — only final classes can be guaranteed not to be subclassed with added mutable state.

In Swift, functions are also values. You can assign a function to a variable, have an array of functions, and call the function held in a variable. Functions that take other functions as arguments (such as map, which takes a function to transform every element of a sequence) or return functions are referred to as higher-order functions.

Functions don’t have to be declared at the top level — you can declare a function within another function or in a do or other scope. Functions defined within an outer scope, but passed out from it (say, as the returned value of a function), can “capture” local variables, in which case those local variables aren’t destroyed when the local scope ends, and the function can hold state through them. This behavior is called “closing over” variables, and functions that do this are called closures.

Functions can be declared either with the func keyword or by using a shorthand { } syntax called a closure expression. Sometimes this gets shortened to “closures,” but don’t let it give you the impression that only closure expressions can be closures. Functions declared with the func keyword are closures too.

Functions are held by reference. This means assigning a function that has state via closed-over variables to another variable doesn’t copy that state; it shares it, similar to object references. What’s more is that when two closures close over the same local variable, they both share that variable, so they share state. This can be quite surprising, and we’ll discuss this more in the chapter on functions.

Functions defined inside a class or protocol are methods, and they have an implicit self parameter. A function that, instead of taking multiple arguments, takes some arguments and returns another function representing the partial application of the arguments to that function, is a curried function. Sometimes we call functions that aren’t methods free functions. This is to distinguish them from methods.

Free functions, and methods called on structs, are statically dispatched. This means the function that’ll be called is known at compile time. This also means the compiler might be able to inline the function, i.e. not call the function at all, but instead replace it with the code the function would execute. It can also discard or simplify code that it can prove at compile time won’t actually run.

Methods on classes or protocols might be dynamically dispatched. This means the compiler doesn’t necessarily know at compile time which function will run. This dynamic behavior is done either by using vtables (similar to how Java or C++ dynamic dispatch works), or in the case of @objc classes and protocols, by using selectors and objc_msgSend.

Subtyping and method overriding is one way of getting polymorphic behavior, i.e. behavior that varies depending on the types involved. A second way is function overloading, where a function is written multiple times for different types. (It’s important not to mix up overriding and overloading, as they behave very differently.) A third way is via generics, where a function or method is written once to take any type that provides certain functions or methods, but the implementations of those functions can vary. Unlike method overriding, the results of function overloading and generics are known statically at compile time. We’ll cover this more in the generics chapter.

Swift Style Guide

When writing this book, and when writing Swift code for our own projects, we try to stick to the following rules:

• For naming, clarity at the point of use is the most important consideration. Since APIs are used many more times than they’re declared, their names should be optimized for how well they work at the call site. Familiarize yourself with the Swift API Design Guidelines and try to adhere to them in your own code.

• Clarity is often helped by conciseness, but brevity should never be a goal in and of itself.

• Always add documentation comments to functions — especially generic ones.

• Types start with UpperCaseLetters. Functions, variables, and enum cases start with lowerCaseLetters.

• Use type inference. Explicit but obvious types get in the way of readability.

• Don’t use type inference in cases of ambiguity or when defining contracts (which is why, for example, funcs have an explicit return type).

• Default to structs unless you actually need a class-only feature or reference semantics.

• Mark classes as final unless you’ve explicitly designed them to be inheritable. If you want to use inheritance internally but not allow subclassing for external clients, mark a class public but not open.

• Use the trailing closure syntax, except when that closure is immediately followed by another opening brace.

• Use guard to exit functions early.

• Eschew force-unwraps and implicitly unwrapped optionals. They’re occasionally useful, but needing them constantly is usually a sign something is wrong.

• Don’t repeat yourself. If you find you’ve written a very similar piece of code more than a couple of times, extract it into a function. Consider making that function a protocol extension.

• Favor map and filter. But don’t force it: use a for loop when it makes sense. The purpose of higher-order functions is to make code more readable. An obfuscated use of reduce when a simple for loop would be clearer defeats this purpose.

• Favor immutable variables: default to let unless you know you need mutation. But use mutation when it makes the code clearer or more efficient. Again, don’t force it: a mutating method on structs is often more idiomatic and efficient than returning a brand new struct.

• Swift generics tend to lead to very long function signatures. Unfortunately, we have yet to settle on a good way of breaking up long function declarations into multiple lines. We’ll try to be consistent in how we do this in sample code.

• Leave off self. when you don’t need it. In closure expressions, it’s a clear signal that self is being captured by the closure.

• Write extensions on existing types and protocols, instead of free functions, whenever you can. This helps readability and discoverability.

Built-In Collections

Collections of elements are among the most important data types in any programming language. Good language support for different kinds of containers has a big impact on programmer productivity and happiness. Swift places special emphasis on sequences and collections — so much of the standard library is dedicated to this topic that we sometimes have the feeling it deals with little else. The resulting model is way more extensible than what you may be used to from other languages, but it’s also quite complex.

In this chapter, we’re going to take a look at the major collection types Swift ships with, with a focus on how to work with them effectively and idiomatically. In the next chapter, we’ll climb up the abstraction ladder and see how the collection protocols in the standard library work.

Arrays

Arrays and Mutability

Arrays are the most common collections in Swift. An array is an ordered container of elements that all have the same type, with random access to each element. As an example, to create an array of numbers, we can write the following:

// The Fibonacci numbers
let fibs = [0, 1, 1, 2, 3, 5]

If we try to modify the array defined above (by using append(_:), for example), we get a compile error. This is because the array is defined as a constant, using let. In many cases, this is exactly the right thing to do; it prevents us from accidentally changing the array. If we want the array to be a variable, we have to define it using var:

var mutableFibs = [0, 1, 1, 2, 3, 5]

Now we can easily append a single element or a sequence of elements:

mutableFibs.append(8)
mutableFibs.append(contentsOf: [13, 21])
mutableFibs // [0, 1, 1, 2, 3, 5, 8, 13, 21]

There are a couple of benefits that come with making the distinction between var and let. Constants defined with let are easier to reason about because they’re immutable. When you read a declaration like let fibs = ..., you know that the value of fibs will never change — it’s enforced by the compiler. This helps greatly when reading through code. However, note that this is only true for types that have value semantics. A let variable to a class instance (i.e. a reference type) guarantees that the reference will never change, i.e. you can’t assign another object to that variable. However, the object the reference points to can change. We’ll go into more detail on these differences in the chapter on structs and classes.

Arrays, like all collection types in the standard library, have value semantics. When you assign an existing array to another variable, the array contents are copied over. For example, in the following code snippet, x is never modified:

var x = [1,2,3]
var y = x
y.append(4)
y // [1, 2, 3, 4]
x // [1, 2, 3]

The statement var y = x makes a copy of x, so appending 4 to y won’t change x — the value of x will still be [1, 2, 3]. The same thing happens when you pass an array into a function; the function gets a local copy, and any changes it makes don’t affect the caller.

Contrast this with the approach to mutability taken by NSArray in Foundation. NSArray has no mutating methods — to mutate an array, you need an NSMutableArray. But just because you have a non-mutating NSArray reference does not mean the array can’t be mutated underneath you:

let a = NSMutableArray(array: [1,2,3])

// I don't want to be able to mutate b
let b: NSArray = a

// But it can still be mutated - via a
a.insert(4, at: 3)
b // ( 1, 2, 3, 4 )

The correct way to write this is to manually create a copy upon assignment:

let c = NSMutableArray(array: [1,2,3])

// I don't want to be able to mutate d
let d = c.copy() as! NSArray

c.insert(4, at: 3)
d // ( 1, 2, 3 )

In the example above, it’s very clear that we need to make a copy — a is mutable, after all. However, when passing around arrays between methods and functions, this isn’t always so easy to see.

In Swift, instead of needing two types, there’s just one, and mutability is defined by declaring with var instead of let. But there’s no reference sharing — when you declare a second array with let, you’re guaranteed it’ll never change.

Making so many copies could be a performance problem, but in practice, all collection types in the Swift standard library are implemented using a technique called copy-on-write, which makes sure the data is only copied when necessary. So in our example, x and y shared internal storage up the point where y.append was called. In the chapter on structs and classes, we’ll take a deeper look at value semantics, including how to implement copy-on-write for your own types.

Arrays and Optionals

Swift arrays provide all the usual operations you’d expect, like isEmpty and count. Arrays also allow for direct access of elements at a specific index through subscripting, like fibs[3]. Keep in mind that you need to make sure the index is within bounds before getting an element via subscript. Fetch the element at index 3, and you’d better be sure the array has at least four elements in it. Otherwise, your program will trap, i.e. abort with a fatal error.

The reason for this is mainly driven by how array indices are used. It’s pretty rare in Swift to actually need to calculate an index:

• Want to iterate over the array?
  for x in array

• Want to iterate over all but the first element of an array? for x in array.dropFirst()

• Want to iterate over all but the last 5 elements? for x in array.dropLast(5)

• Want to number all the elements in an array? for (num, element) in collection.enumerated()

• Want to find the location of a specific element? if let idx = array.index { someMatchingLogic($0) }

• Want to transform all the elements in an array? array.map { someTransformation($0) }

• Want to fetch only the elements matching a specific criterion?
  array.filter { someCriteria($0) }

Another sign that Swift wants to discourage you from doing index math is the removal of traditional C-style for loops from the language in Swift 3. Manually fiddling with indices is a rich seam of bugs to mine, so it’s often best avoided. And if it can’t be, well, we’ll see in the generics chapter that it’s easy enough to write a new reusable general function that does what you need and in which you can wrap your carefully tested index calculations.

But sometimes you do have to use an index. And with array indices, the expectation is that when you do, you’ll have thought very carefully about the logic behind the index calculation. So to have to unwrap the value of a subscript operation is probably overkill — it means you don’t trust your code. But chances are you do trust your code, so you’ll probably resort to force-unwrapping the result, because you know that the index must be valid. This is (a) annoying, and (b) a bad habit to get into. When force-unwrapping becomes routine, eventually you’re going to slip up and force-unwrap something you don’t mean to. So to avoid this habit becoming routine, arrays don’t give you the option.

While a subscripting operation that responds to a invalid index with a controlled crash could arguably be called unsafe, that’s only one aspect of safety. Subscripting is totally safe in regard to memory safety — the standard library collections always perform bounds checks to prevent unauthorized memory access with an out-of-bounds index.

Other operations behave differently. The first and last properties return an optional; they return nil if the array is empty. first is equivalent to isEmpty ? nil : self[0]. Similarly, the removeLast method will trap if you call it on an empty array, whereas popLast will only delete and return the last element if the array isn’t empty and otherwise do nothing and return nil. Which one you’d want to use depends on your use case. When you’re using the array as a stack, you’ll probably always want to combine checking for empty and removing the last entry. On the other hand, if you already know through invariants whether or not the array is empty, dealing with the optional is fiddly.

We’ll encounter these tradeoffs again later in this chapter when we talk about dictionaries. Additionally, there’s an entire chapter dedicated to optionals.

Transforming Arrays

Map

It’s common to need to perform a transformation on every value in an array. Every programmer has written similar code hundreds of times: create a new array, loop over all elements in an existing array, perform an operation on an element, and append the result of that operation to the new array. For example, the following code squares an array of integers:

var squared: [Int] = []
for fib in fibs {
    squared.append(fib * fib)
}
squared // [0, 1, 1, 4, 9, 25]

Swift arrays have a map method, adopted from the world of functional programming. Here’s the exact same operation, using map:

let squares = fibs.map { fib in fib * fib }
squares // [0, 1, 1, 4, 9, 25]

This version has three main advantages. It’s shorter, of course. There’s also less room for error. But more importantly, it’s clearer. All the clutter has been removed. Once you’re used to seeing and using map everywhere, it acts as a signal — you see map, and you know immediately what’s happening: a function is going to be applied to every element, returning a new array of the transformed elements.

The declaration of squared no longer needs to be made with var, because we aren’t mutating it any longer — it’ll be delivered out of the map fully formed, so we can declare squares with let, if appropriate. And because the type of the contents can be inferred from the function passed to map, squares no longer needs to be explicitly typed.

map isn’t hard to write — it’s just a question of wrapping up the boilerplate parts of the for loop into a generic function. Here’s one possible implementation (though in Swift, it’s actually an extension of Sequence, something we’ll cover in the chapter on writing generic algorithms):

extension Array {
    func map<T>(_ transform: (Element) -> T) -> [T] {
        var result: [T] = []
        result.reserveCapacity(count)
        for x in self {
            result.append(transform(x))
        }
        return result
    }
}

Element is the generic placeholder for whatever type the array contains. And T is a new placeholder that can represent the result of the element transformation. The map function itself doesn’t care what Element and T are; they can be anything at all. The concrete type T of the transformed elements is defined by the return type of the transform function the caller passes to map.

Really, the signature of this method should be func map<T>(_ transform: (Element) throws -> T) rethrows -> [T], indicating that map will forward any error the transformation function might throw to the caller. We’ll cover this in detail in the errors chapter. We’ve left the error handling annotations out here for simplicity. If you’d like, you can check out the source code for Sequence.map in the Swift repository on GitHub.

Parameterizing Behavior with Functions

Even if you’re already familiar with map, take a moment and consider the map code. What makes it so general yet so useful?

map manages to separate out the boilerplate — which doesn’t vary from call to call — from the functionality that always varies: the logic of how exactly to transform each element. It does this through a parameter the caller supplies: the transformation function.

This pattern of parameterizing behavior is found throughout the standard library. There are more than a dozen separate functions that take a closure that allows the caller to customize the key step:

• map and flatMap — how to transform an element

• filter — should an element be included?

• reduce — how to fold an element into an aggregate value

• sequence — what should the next element of the sequence be?

• forEach — what side effect to perform with an element

• sort, lexicographicallyPrecedes, and partition — in what order should two elements come?

• index, first, and contains — does this element match?

• min and max — which is the min/max of two elements?

• elementsEqual and starts — are two elements equivalent?

• split — is this element a separator?

The goal of all these functions is to get rid of the clutter of the uninteresting parts of the code, such as the creation of a new array, the for loop over the source data, and the like. Instead, the clutter is replaced with a single word that describes what’s being done. This brings the important code – the logic the programmer wants to express – to the forefront.

Several of these functions have a default behavior. sort sorts elements in ascending order when they’re comparable, unless you specify otherwise. contains can take a value to check for, so long as the elements are equatable. These help make the code even more readable. Ascending order sort is natural, so the meaning of array.sort() is intuitive. array.index(of: "foo") is clearer than array.index { $0 == "foo" }.

But in every instance, these are just shorthand for the common cases. Elements don’t have to be comparable or equatable, and you don’t have to compare the whole element — you can sort an array of people by their ages (people.sort { $0.age < $1.age }) or check if the array contains anyone underage (people.contains { $0.age < 18 }). You can also compare some transformation of the element. For example, an admittedly inefficient case-insensitive sort could be performed via people.sort { $0.name.uppercased() < $1.name.uppercased() }.

There are other functions of similar usefulness that would also take a closure to specify their behaviors but aren’t in the standard library. You could easily define them yourself (and might like to try):

• accumulate — combine elements into an array of running values (like reduce, but returning an array of each interim combination)

• all(matching:) and none(matching:) — test if all or no elements in a sequence match a criterion (can be built with contains, with some carefully placed negation)

• count(where:) — count the number of elements that match (similar to filter, but without constructing an array)

• indices(where:) — return a list of indices matching a criteria (similar to index(where:), but doesn’t stop on the first one)

• prefix(while:) — filter elements while a predicate returns true, then drop the rest (similar to filter, but with an early exit, and useful for infinite or lazily computed sequences)

• drop(while:) — drop elements until the predicate ceases to be true, and then return the rest (similar to prefix(while:), but this returns the inverse)

Many of these we define elsewhere in the book. (prefix(while:) and drop(while:) are actually planned additions to the standard library, but they didn’t make the cut for Swift 3.0. They’ll be added in a future release.)

You might find yourself writing something that fits a pattern more than a couple of times — something like this, where you search an array in reverse order for the first element that matches a certain condition:

let names = ["Paula", "Elena", "Zoe"]

var lastNameEndingInA: String?
for name in names.reversed() where name.hasSuffix("a") {
    lastNameEndingInA = name
    break
}
lastNameEndingInA // Optional("Elena")

If that’s the case, consider writing a short extension to Sequence. The method last(where:) wraps this logic — we use a closure to abstract over the part of our for loop that varies:

extension Sequence {
    func last(where predicate: (Iterator.Element) -> Bool) -> Iterator.Element? {
        for element in reversed() where predicate(element) {
            return element
        }
        return nil
    }
}

This then allows you to replace your for loop with the following:

let match = names.last { $0.hasSuffix("a") }
match // Optional("Elena")

This has all the same benefits we described for map. The example with last(where:) is more readable than the example with the for loop; even though the for loop is simple, you still have to run the loop through in your head, which is a small mental tax. Using last(where:) introduces less chance of error (such as accidentally forgetting to reverse the array), and it allows you to declare the result variable with let instead of var.

It also works nicely with guard — in all likelihood, you’re going to terminate a flow early if the element isn’t found:

guard let match = someSequence.last(where: { $0.passesTest() })
    else { return }
// Do something with match

We’ll say more about extending collections and using functions later in the book.

Mutation and Stateful Closures

When iterating over an array, you could use map to perform side effects (e.g. inserting the elements into some lookup table). We don’t recommend doing this. Take a look at the following:

array.map { item in
    table.insert(item)
}

This hides the side effect (the mutation of the lookup table) in a construct that looks like a transformation of the array. If you ever see something like the above, then it’s a clear case for using a plain for loop instead of a function like map. The forEach method would also be more appropriate than map in this case, but it has its own issues. We’ll look at forEach in a bit.

Performing side effects is different than deliberately giving the closure local state, which is a particularly useful technique, and it’s what makes closures — functions that can capture and mutate variables outside their scope — so powerful a tool when combined with higher-order functions. For example, the accumulate function described above could be implemented with map and a stateful closure, like this:

extension Array {
    func accumulate<Result>(_ initialResult: Result, 
        _ nextPartialResult: (Result, Element) -> Result) -> [Result] 
    {
        var running = initialResult
        return map { next in
            running = nextPartialResult(running, next)
            return running
        }
    }
}

This creates a temporary variable to store the running value and then uses map to create an array of the running value as it progresses:

[1,2,3,4].accumulate(0, +) // [1, 3, 6, 10]

Filter

Another very common operation is to take an array and create a new array that only includes those elements that match a certain condition. The pattern of looping over an array and selecting the elements that match the given predicate is captured in the filter method:

nums.filter { num in num % 2 == 0 } // [2, 4, 6, 8, 10]

We can use Swift’s shorthand notation for arguments of a closure expression to make this even shorter. Instead of naming the num argument, we can write the above code like this:

nums.filter { $0 % 2 == 0 } // [2, 4, 6, 8, 10]

For very short closures, this can be more readable. If the closure is more complicated, it’s almost always a better idea to name the arguments explicitly, as we’ve done before. It’s really a matter of personal taste — choose whichever is more readable at a glance. A good rule of thumb is this: if the closure fits neatly on one line, shorthand argument names are a good fit.

By combining map and filter, we can easily write a lot of operations on arrays without having to introduce a single intermediate array, and the resulting code will become shorter and easier to read. For example, to find all squares under 100 that are even, we could map the range 0..<10 in order to square it, and then filter out all odd numbers:

(1..<10).map { $0 * $0 }.filter { $0 % 2 == 0 } // [4, 16, 36, 64]

The implementation of filter looks much the same as map:

extension Array {
    func filter(_ isIncluded: (Element) -> Bool) -> [Element] {
        var result: [Element] = []
        for x in self where isIncluded(x) {
            result.append(x)
        }
        return result
    }
}

For more on the where clause we use in the for loop, see the optionals chapter.

One quick performance tip: if you ever find yourself writing something like the following, stop!

bigArray.filter { someCondition }.count > 0

filter creates a brand new array and processes every element in the array. But this is unnecessary. This code only needs to check if one element matches — in which case, contains(where:) will do the job:

bigArray.contains { someCondition }

This is much faster for two reasons: it doesn’t create a whole new array of the filtered elements just to count them, and it exits early, as soon as it matches the first element. Generally, only ever use filter if you want all the results.

Often you want to do something that can be done by contains, but it looks pretty ugly. For example, you can check if every element of a sequence matches a predicate using !sequence.contains { !condition }, but it’s much more readable to wrap this in a new function that has a more descriptive name:

extension Sequence {
    public func all(matching predicate: (Iterator.Element) -> Bool) -> Bool {
        // Every element matches a predicate if no element doesn't match it:
        return !contains { !predicate($0) }
    }
}

let evenNums = nums.filter { $0 % 2 == 0 } // [2, 4, 6, 8, 10]
evenNums.all { $0 % 2 == 0 } // true

Reduce

Both map and filter take an array and produce a new, modified array. Sometimes, however, you want to combine all elements into a new value. For example, to sum up all the elements, we could write the following code:

var total = 0
for num in fibs {
    total = total + num
}
total // 12

The reduce method takes this pattern and abstracts two parts: the initial value (in this case, zero), and the function for combining the intermediate value (total) and the element (num). Using reduce, we can write the same example like this:

let sum = fibs.reduce(0) { total, num in total + num } // 12

Operators are functions too, so we could’ve also written the same example like this:

fibs.reduce(0, +) // 12

The output type of reduce doesn’t have to be the same as the element type. For example, if we want to convert a list of integers into a string, with each number followed by a space, we can do the following:

fibs.reduce("") { str, num in str + "\(num) " } // 0 1 1 2 3 5 

Here’s the implementation for reduce:

extension Array {
    func reduce<Result>(_ initialResult: Result, 
        _ nextPartialResult: (Result, Element) -> Result) -> Result 
    {
        var result = initialResult
        for x in self {
            result = nextPartialResult(result, x)
        }
        return result
    }
}

Another performance tip: reduce is very flexible, and it’s common to see it used to build arrays and perform other operations. For example, you can implement map and filter using only reduce:

extension Array {
    func map2<T>(_ transform: (Element) -> T) -> [T] {
        return reduce([]) {
            $0 + [transform($1)]
        }
    }

    func filter2(_ isIncluded: (Element) -> Bool) -> [Element] {
        return reduce([]) {
            isIncluded($1) ? $0 + [$1] : $0
        }
    }
}

This is kind of beautiful and has the benefit of not needing those icky imperative for loops. But Swift isn’t Haskell, and Swift arrays aren’t lists. What’s happening here is that every time, through the combine function, a brand new array is being created by appending the transformed or included element to the previous one. This means that both these implementations are O(n²), not O(n) — as the length of the array increases, the time these functions take increases quadratically.

A Flattening Map

Sometimes, you want to map an array where the transformation function returns another array and not a single element.

For example, let’s say we have a function, links, which reads a Markdown file and returns an array containing the URLs of all the links in the file. The function type looks like this:

func extractLinks(markdownFile: String) -> [URL]

If we have a bunch of Markdown files and want to extract the links from all files into a single array, we could try to write something like markdownFiles.map(extractLinks). But this returns an array of arrays containing the URLs: one array per file. Now you could just perform the map, get back an array of arrays, and then call joined to flatten the results into a single array:

let markdownFiles: [String] = // ...
let nestedLinks = markdownFiles.map(extractLinks)
let links = nestedLinks.joined()

The flatMap method combines these two operations into a single step. So markdownFiles.flatMap(extractLinks) returns all the URLs in an array of Markdown files as a single array.

The implementation for flatMap is almost identical to map, except it takes a function argument that returns an array. It uses append(contentsOf:) instead of append(_:) to flatten the results when appending:

extension Array {
    func flatMap<T>(_ transform: (Element) -> [T]) -> [T] {
        var result: [T] = []
        for x in self {
            result.append(contentsOf: transform(x))
        }
        return result
    }
}

Another great use case for flatMap is combining elements from different arrays. To get all possible pairs of two arrays, flatMap over one array and then map over the other:

let ranks = ["J","Q","K","A"]

let result = suits.flatMap { suit in
    ranks.map { rank in
        (suit, rank)
    }
}

Iteration using forEach

The final operation we’d like to discuss is forEach. It works almost like a for loop: the passed-in function is executed once for each element in the sequence. And unlike map, forEach doesn’t return anything. Let’s start by mechanically replacing a loop with forEach:

for element in [1,2,3] {
    print(element)
}

[1,2,3].forEach { element in
    print(element)
}

This isn’t a big win, but it can be handy if the action you want to perform is a single function call on each element in a collection. Passing a function name to forEach instead of a closure expression can lead to clear and concise code. For example, if you’re inside a view controller and want to add an array of subviews to the main view, you can just do theViews.forEach(view.addSubview).

However, there are some subtle differences between for loops and forEach. For instance, if a for loop has a return statement in it, rewriting it with forEach can significantly change the code’s behavior. Consider the following example, which is written using a for loop with a where condition:

extension Array where Element: Equatable {
    func index(of element: Element) -> Int? {
        for idx in self.indices where self[idx] == element {
            return idx
        }
        return nil
    }
}

We can’t directly replicate the where clause in the forEach construct, so we might (incorrectly) rewrite this using filter:

extension Array where Element: Equatable {
    func index_foreach(of element: Element) -> Int? {
        self.indices.filter { idx in
            self[idx] == element
        }.forEach { idx in
            return idx
        }
        return nil
    }
}

The return inside the forEach closure doesn’t return out of the outer function; it only returns from the closure itself. In this particular case, we’d probably have found the bug because the compiler generates a warning that the argument to the return statement is unused, but you shouldn’t rely on it finding every such issue.

Also, consider the following simple example:

(1..<10).forEach { number in
    print(number)
    if number > 2 { return }
}

It’s not immediately obvious that this prints out all the numbers in the input range. The return statement isn’t breaking the loop, rather it’s returning from the closure.

In some situations, such as the addSubview example above, forEach can be nicer than a for loop. And it really shines as part of a sequence of chained operations. For instance, imagine you’ve chained several calls to map and filter in a single statement, and during debugging you want to log the intermediate values somewhere in the middle of the chain. Inserting a forEach step at the desired position is probably the quickest way to do this.

However, because of the non-obvious behavior with return, we recommend against most other uses of forEach. Just use a regular for loop instead.

Array Types

Slices

In addition to accessing a single element of an array by subscript (e.g. fibs[0]), we can also access a range of elements by subscript. For example, to get all but the first element of an array, we can do the following:

let slice = fibs[1..<fibs.endIndex]
slice // [1, 1, 2, 3, 5]
type(of: slice) // ArraySlice<Int>

This gets us a slice of the array starting at the second element, including the last element. The type of the result is ArraySlice, not Array. ArraySlice is a view on arrays. It’s backed by the original array, yet it provides a view on just the slice. This makes certain the array doesn’t need to get copied. The ArraySlice type has the same methods defined as Array does, so you can use them as if they were arrays. If you do need to convert them into an array, you can just construct a new array out of the slice:

Array(fibs[1..<fibs.endIndex]) // [1, 1, 2, 3, 5]

Array Slices

Bridging

Swift arrays can bridge to Objective-C. They can also be used with C, but we’ll cover that in a later chapter. Because NSArray can only hold objects, there used to be a requirement that the elements of a Swift array had to be convertible to AnyObject in order for it to be bridgeable. This constrained the bridging to class instances and a small number of value types (such as Int, Bool, and String) that supported automatic bridging to their Objective-C counterparts.

This limitation no longer exists in Swift 3. The Objective-C id type is now imported into Swift as Any instead of AnyObject, which means that any Swift array is now bridgeable to NSArray. NSArray still always expects objects, of course, so the compiler and runtime will automatically wrap incompatible values in an opaque box class behind the scenes. Unwrapping in the reverse direction also happens automatically.

A universal bridging mechanism for all Swift types to Objective-C doesn’t just make working with arrays more pleasant. It also applies to other collections, like dictionaries and sets, and it opens up a lot of potential for future enhancements to the interoperability between Swift and Objective-C. For example, now that Swift values can be bridged to Objective-C objects, a future Swift version could conceivably allow Swift value types to conform to @objc protocols.

Dictionaries

Another key data structure in Swift is Dictionary. A dictionary contains keys with corresponding values; duplicate keys aren’t supported. Retrieving a value by its key takes constant time on average, whereas searching an array for a particular element grows linearly with the array’s size. Unlike arrays, dictionaries aren’t ordered. The order in which pairs are enumerated in a for loop is undefined.

In the following example, we use a dictionary as the model data for a fictional settings screen in a smartphone app. The screen consists of a list of settings, and each individual setting has a name (the keys in our dictionary) and a value. A value can be one of several data types, such as text, numbers, or booleans. We use an enum with associated values to model this:

enum Setting {
    case text(String)
    case int(Int)
    case bool(Bool)
}

let defaultSettings: [String:Setting] = [
    "Airplane Mode": .bool(true),
    "Name": .text("My iPhone"),
]

defaultSettings["Name"] // Optional(Setting.text("My iPhone"))

We use subscripting to get the value of a setting (for example, defaultSettings["Name"]). Dictionary lookup always returns an optional value. When the specified key doesn’t exist, it returns nil. Contrast this with arrays, which respond to an out-of-bounds access by crashing the program.

The rationale for this difference is that array indices and dictionary keys are used very differently. We’ve already seen that it’s quite rare that you actually need to work with array indices directly. And if you do, an array index is usually directly derived from the array in some way (e.g. from a range like 0..<array.count); thus, using an invalid index is a programmer error. On the other hand, it’s very common for dictionary keys to come from some source other than the dictionary itself.

Unlike arrays, dictionaries are also sparse. The existence of the value under the key "name" doesn’t tell you anything about whether or not the key “address” also exists.

Mutation

Just like with arrays, dictionaries defined using let are immutable: no entries can be added, removed, or changed. And just like with arrays, we can define a mutable variant using var. To remove a value from a dictionary, we can either set it to nil using subscripting or call removeValue(forKey:). The latter additionally returns the deleted value, or nil if the key didn’t exist. If we want to take an immutable dictionary and make changes to it, we have to make a copy:

var localizedSettings = defaultSettings
localizedSettings["Name"] = .text("Mein iPhone")
localizedSettings["Do Not Disturb"] = .bool(true)

let oldName = localizedSettings
    .updateValue(.text("Il mio iPhone"), forKey: "Name")
localizedSettings["Name"] // Optional(Setting.text("Il mio iPhone"))
oldName // Optional(Setting.text("Mein iPhone"))

Some Useful Dictionary Extensions

What if we wanted to combine the default settings dictionary with any custom settings the user has changed? Custom settings should override defaults, but the resulting dictionary should still include default values for any keys that haven’t been customized. Essentially, we want to merge two dictionaries, where the dictionary that’s being merged in overwrites duplicate keys. The standard library doesn’t include a function for this, so let’s write one.

We can extend Dictionary with a merge method that takes the key-value pairs to be merged in as its only argument. We could make this argument another Dictionary, but this is a good opportunity for a more generic solution. Our requirements for the argument are that it must be a sequence we can loop over, and the sequence’s elements must be key-value pairs of the same type as the receiving dictionary. Any Sequence whose Iterator.Element is a (Key, Value) pair meets these requirements, so that’s what the method’s generic constraints should express (Key and Value here are the generic type parameters of the Dictionary type we’re extending):

extension Dictionary {
    mutating func merge<S>(_ other: S)
        where S: Sequence, S.Iterator.Element == (key: Key, value: Value) {
        for (k, v) in other {
            self[k] = v
        }
    }
}

We can use this to merge one dictionary into another, as shown in the following example, but the method argument could just as well be an array of key-value pairs or any other sequence:

var settings = defaultSettings
let overriddenSettings: [String:Setting] = ["Name": .text("Jane's iPhone")]
settings.merge(overriddenSettings)
settings
// ["Name": Setting.text("Jane\'s iPhone"), "Airplane Mode": Setting.bool(true)]

Another interesting extension is creating a dictionary from a sequence of (Key, Value) pairs. The standard library provides a similar initializer for arrays that comes up very frequently; you use it every time you create an array from a range (Array(1...10)) or convert an ArraySlice back into a proper array (Array(someSlice)). However, there’s no such initializer for Dictionary. (There is a Swift-Evolution proposal to add one, though, so we may see it in the future.)

We can start with an empty dictionary and then just merge in the sequence. This makes use of the merge method defined above to do the heavy lifting:

extension Dictionary {
    init<S: Sequence>(_ sequence: S)
        where S.Iterator.Element == (key: Key, value: Value) {
        self = [:]
        self.merge(sequence)
    }
}

// All alarms are turned off by default
let defaultAlarms = (1..<5).map { (key: "Alarm \($0)", value: false) }
let alarmsDictionary = Dictionary(defaultAlarms)

A third useful extension is a map over the dictionary’s values. Because Dictionary is a Sequence, it already has a map method that produces an array. However, sometimes we want to keep the dictionary structure intact and only transform its values. Our mapValues method first calls the standard map to create an array of (key, transformed value) pairs and then uses the new initializer we defined above to turn it back into a dictionary:

extension Dictionary {
    func mapValues<NewValue>(transform: (Value) -> NewValue)
        -> [Key:NewValue] {
            return Dictionary<Key, NewValue>(map { (key, value) in
                return (key, transform(value))
            })
    }
}

let settingsAsStrings = settings.mapValues { setting -> String in
    switch setting {
    case .text(let text): return text
    case .int(let number): return String(number)
    case .bool(let value): return String(value)
    }
}
settingsAsStrings // ["Name": "Jane\'s iPhone", "Airplane Mode": "true"]

Hashable Requirement

Dictionaries are hash tables. The dictionary assigns each key a position in its underlying storage array based on the key’s hashValue. This is why Dictionary requires its Key type to conform to the Hashable protocol. All the basic data types in the standard library already do, including strings, integers, floating-point, and Boolean values. Enumerations without associated values also get automatic Hashable conformance for free.

If you want to use your own custom types as dictionary keys, you must add Hashable conformance manually. This requires an implementation of the hashValue property and, because Hashable extends Equatable, an overload of the == operator function for your type. Your implementation must hold an important invariant: two instances that are equal (as defined by your == implementation) must have the same hash value. The reverse isn’t true: two instances with the same hash value don’t necessarily compare equally. This makes sense, considering that there’s only a finite number of distinct hash values, while many hashable types (like strings) have essentially infinite cardinality.

The potential for duplicate hash values means that Dictionary must be able to handle collisions. Nevertheless, a good hash function should strive for a minimal number of collisions in order to preserve the collection’s performance characteristics, i.e. the hash function should produce a uniform distribution over the full integer range. In the extreme case where your implementation returns the same hash value (e.g. zero) for every instance, a dictionary’s lookup performance degrades to O(n).

The second characteristic of a good hash function is that it’s fast. Keep in mind that the hash value is computed every time a key is inserted, removed, or looked up. If your hashValue implementation takes too much time, it might eat up any gains you got from the O(1) complexity.

Writing a good hash function that meets these requirements isn’t easy. For types that are composed of basic data types that are Hashable themselves, XOR’ing the members’ hash values can be a good starting point:

struct Person {
    var name: String
    var zipCode: Int
    var birthday: Date
}

extension Person: Equatable {
    static func ==(lhs: Person, rhs: Person) -> Bool {
        return lhs.name == rhs.name
            && lhs.zipCode == rhs.zipCode
            && lhs.birthday == rhs.birthday
    }
}

extension Person: Hashable {
    var hashValue: Int {
        return name.hashValue ^ zipCode.hashValue ^ birthday.hashValue
    }
}

One limitation of this technique is that XOR is symmetric (i.e. a ^ b == b ^ a), which, depending on the characteristics of the data being hashed, could make collisions more likely than necessary. You can add a bitwise rotation to the mix to avoid this.

Finally, be extra careful when you use types that don’t have value semantics (e.g. mutable objects) as dictionary keys. If you mutate an object after using it as a dictionary key in a way that changes its hash value and/or equality, you’ll not be able to find it again in the dictionary. The dictionary now stores the object in the wrong slot, effectively corrupting its internal storage. This isn’t a problem with value types because the key in the dictionary doesn’t share your copy’s storage and therefore can’t be mutated from the outside.

Sets

The third major collection type in the standard library is Set. A set is an unordered collection of elements, with each element appearing only once. You can essentially think of a set as a dictionary that only stores keys and no values. Like Dictionary, Set is implemented with a hash table and has similar performance characteristics and requirements. Testing a value for membership in the set is a constant-time operation, and set elements must be Hashable, just like dictionary keys.

Use a set instead of an array when you need to test efficiently for membership (an O(n) operation for arrays) and the order of the elements is not important, or when you need to ensure that a collection contains no duplicates.

Set conforms to the ExpressibleByArrayLiteral protocol, which means that we can initialize it with an array literal like this:

let naturals: Set = [1, 2, 3, 2]
naturals // [2, 3, 1]
naturals.contains(3) // true
naturals.contains(0) // false

Like all collections, sets support the common operations we’ve already seen: you can iterate over the elements in a for loop, map or filter them, and do all other sorts of things.

Set Algebra

As the name implies, Set is closely related to the mathematical concept of a set; it supports all common set operations you learned in math class. For example, we can subtract one set from another:

let iPods: Set = ["iPod touch", "iPod nano", "iPod mini", 
    "iPod shuffle", "iPod Classic"]
let discontinuedIPods: Set = ["iPod mini", "iPod Classic"]
let currentIPods = iPods.subtracting(discontinuedIPods)
// ["iPod shuffle", "iPod nano", "iPod touch"]

We can also form the intersection of two sets, i.e. find all elements that are in both:

let touchscreen: Set = ["iPhone", "iPad", "iPod touch", "iPod nano"]
let iPodsWithTouch = iPods.intersection(touchscreen)
// ["iPod touch", "iPod nano"]

Or, we can form the union of two sets, i.e. combine them into one (removing duplicates, of course):

var discontinued: Set = ["iBook", "Powerbook", "Power Mac"]
discontinued.formUnion(discontinuedIPods) // ()

Here, we used the mutating variant formUnion to mutate the original set (which, as a result, must be declared with var). Almost all set operations have both non-mutating and mutating forms, the latter beginning with form.... For even more set operations, check out the SetAlgebra protocol.

Index Sets and Character Sets

Set is the only type in the standard library that conforms to SetAlgebra, but the protocol is also adopted by two interesting types in Foundation: IndexSet and CharacterSet. Both of these date back to a time long before Swift was a thing. The way these and other Objective-C classes are now bridged into Swift as fully featured value types — adopting common standard library protocols in the process — is great because they’ll instantly feel familiar to Swift developers.

IndexSet represents a set of positive integer values. You can, of course, do this with a Set<Int>, but IndexSet is way more storage efficient because it uses a list of ranges internally. Say you have a table view with 1,000 elements and you want to use a set to manage the indices of the rows the user has selected. A Set<Int> needs to store up to 1,000 elements, depending on how many rows are selected. An IndexSet, on the other hand, stores continuous ranges, so a selection of the first 500 rows in the table only takes two integers to store (the selection’s lower and upper bounds).

However, as a user of an IndexSet, you don’t have to worry about the internal structure, as it’s completely hidden behind the familiar SetAlgebra and Collection interfaces. (Unless you want to work on the ranges directly, that is. IndexSet exposes a view to them via its rangeView property, which itself is a collection.) For example, you can add a few ranges to an index set and then map over the indices as if they were individual members:

var indices = IndexSet()
indices.insert(integersIn: 1..<5)
indices.insert(integersIn: 11..<15)
let evenIndices = indices.filter { $0 % 2 == 0 } // [2, 4, 12, 14]

CharacterSet is an equally efficient way to store a set of Unicode characters. It’s often used to check if a particular string only contains characters from a specific character subset, such as alphanumerics or decimalDigits. Unlike IndexSet, CharacterSet isn’t a collection, though. We’ll talk a bit more about CharacterSet in the chapter on strings.

Using Sets Inside Closures

Dictionaries and sets can be very handy data structures to use inside your functions, even when you’re not exposing them to the caller. For example, if we want to write an extension on Sequence to retrieve all unique elements in the sequence, we could easily put the elements in a set and return its contents. However, that won’t be stable: because a set has no defined order, the input elements might get reordered in the result. To fix this, we can write an extension that maintains the order by using an internal Set for bookkeeping:

extension Sequence where Iterator.Element: Hashable {
    func unique() -> [Iterator.Element] {
        var seen: Set<Iterator.Element> = []
        return filter {
            if seen.contains($0) {
                return false
            } else {
                seen.insert($0)
                return true
            }
        }
    }
}

[1,2,3,12,1,3,4,5,6,4,6].unique() // [1, 2, 3, 12, 4, 5, 6]

The method above allows us to find all unique elements in a sequence while still maintaining the original order (with the constraint that the elements must be Hashable). Inside the closure we pass to filter, we refer to the variable seen that we defined outside the closure, thus maintaining state over multiple iterations of the closure. In the chapter on functions, we’ll look at this technique in more detail.

Ranges

A range is an interval of values, defined by its lower and upper bounds. You create ranges with the two range operators: ..< for half-open ranges that don’t include their upper bound, and ... for closed ranges that include both bounds:

// 0 to 9, 10 is not included
let singleDigitNumbers = 0..<10

// "z" is included
let lowercaseLetters = Character("a")...Character("z")

Ranges seem like a natural fit to be sequences or collections, so it may surprise you to learn that they’re neither — at least not all of them are.

There are now four range types in the standard library. They can be classified in a two-by-two matrix, as follows:

The columns of the matrix correspond to the two range operators we saw above, which create a [Countable]Range (half-open) or a [Countable]ClosedRange (closed), respectively. Half-open and closed ranges both have their place:

• Only a half-open range can represent an empty interval (when the lower and upper bounds are equal, as in 5..<5).

• Only a closed range can contain the maximum value its element type can represent (e.g. 0...Int.max). A half-open range always requires at least one representable value that’s greater than the highest value in the range.

(In Swift 2, all ranges were technically half-open ranges, even if they were created with the ... operator; no range could contain the maximum expressible value. The standard library used to have additional types, HalfOpenInterval and ClosedInterval, to remedy this. They’ve been removed in Swift 3.)

The rows in the table distinguish between “normal” ranges whose element type only conforms to the Comparable protocol (which is the minimum requirement), and ranges over types that are Strideable and use integer steps between elements. Only the latter ranges are collections, inheriting all the powerful functionality we’ve seen in this chapter.

Swift calls these more capable ranges countable because only they can be iterated over. Valid bounds for countable ranges include integer and pointer types, but not floating-point types, because of the integer constraint on the type’s Stride. If you need to iterate over consecutive floating-point values, you can use the stride(from:to:by) and stride(from:through:by) functions to create such a sequence.

This means that you can iterate over some ranges but not over others. For example, the range of Character values we defined above isn’t a sequence, so this won’t work:

for char in lowercaseLetters {
    // ...
}
// Error: Type 'ClosedRange<Character>' does not conform to protocol 'Sequence'

(The answer why iterating over characters isn’t as straightforward as it would seem has to do with Unicode, and we’ll cover it at length in the chapter on strings.)

Meanwhile, the following is no problem because an integer range is a countable range and thus a collection:

singleDigitNumbers.map { $0 * $0 } // [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

The standard library currently has to have separate types for countable ranges, CountableRange and CountableClosedRange. Ideally, these wouldn’t be distinct types, but rather extensions on Range and ClosedRange that add collection conformance on the condition that the generic parameters meet the required constraints. We’ll talk a lot more about this in the next chapter, but the code would look like this:

// Invalid in Swift 3
extension Range: RandomAccessCollection
    where Bound: Strideable, Bound.Stride: SignedInteger
{
    // Implement RandomAccessCollection
}

Alas, Swift 3’s type system can’t express this idea, so separate types are needed. Support for conditional conformance is expected for Swift 4, and CountableRange and CountableClosedRange will be folded into Range and ClosedRange when it lands.

The distinction between the half-open Range and the closed ClosedRange will likely remain, and it can sometimes make working with ranges harder than it used to be. Say you have a function that takes a Range<Character> and you want to pass it the closed character range we created above. You may be surprised to find out that it’s not possible! Inexplicably, there appears to be no way to convert a ClosedRange into a Range. But why? Well, to turn a closed range into an equivalent half-open range, you’d have to find the element that comes after the original range’s upper bound. And that’s simply not possible unless the element is Strideable, which is only guaranteed for countable ranges.

This means the caller of such a function will have to provide the correct type. If the function expects a Range, you can’t use the ... operator to create it. We’re not certain how big of a limitation this is in practice, since most ranges are likely integer based, but it’s definitely unintuitive.

Collection Protocols

We saw in the previous chapter that Array, Dictionary, and Set don’t exist in a vacuum. They’re all implemented on top of a rich set of abstractions for processing series of elements, provided by the Swift standard library. This chapter is all about the Sequence and Collection protocols, which form the cornerstones of this model. We’ll cover how these protocols work, why they work they way they do, and how you can write your own sequences and collections.

Sequences

The Sequence protocol stands at the base of the hierarchy. A sequence is a series of values of the same type that lets you iterate over the values. The most common way to traverse a sequence is a for loop:

for element in someSequence {
    doSomething(with: element)
}

This seemingly simple capability of stepping over elements forms the foundation for a large number of useful operations Sequence provides to adopters of the protocol. We already mentioned many of them in the previous chapter. Whenever you come up with a common operation that depends on sequential access to a series of values, you should consider implementing it on top of Sequence, too. We’ll see many examples of how to do this throughout this chapter and the rest of the book.

The requirements for a type to conform to Sequence are fairly small. All it must do is provide a makeIterator() method that returns an iterator:

protocol Sequence {
    associatedtype Iterator: IteratorProtocol
    func makeIterator() -> Iterator
}

The only thing we learn about iterators from the definition of Sequence is that they’re types that conform to IteratorProtocol. So let’s first take a closer look at them.

Collections

Conforming to Collection

Indices

Slices

Specialized Collections

Conclusion

Optionals

Sentinel Values

An extremely common pattern in programming is to have an operation that may or may not return a value.

Perhaps not returning a value is an expected outcome when you’ve reached the end of a file you were reading, as in the following C snippet:

int ch;
while ((ch = getchar()) != EOF) {
    printf("Read character %c\n", ch);
}
printf("Reached end-of-file\n");

EOF is just a #define for -1. As long as there are more characters in the file, getchar returns them. But if the end of the file is reached, getchar returns -1.

Or perhaps returning no value means “not found,” as in this bit of C++:

auto vec = {1, 2, 3};
auto iterator = std::find(vec.begin(), vec.end(), someValue);
if (iterator != vec.end()) {
    std::cout << "vec contains " << *iterator << std::endl;
}

Here, vec.end() is the iterator “one past the end” of the container; it’s a special iterator you can check against the container’s end, but that you mustn’t ever actually use to access a value — similar to a collection’s endIndex in Swift. find uses it to indicate that no such value is present in the container.

Or maybe the value can’t be returned because something went wrong during the function’s processing. Probably the most notorious example is that of the null pointer. This innocuous-looking piece of Java code will likely throw a NullPointerException:

int i = Integer.getInteger("123")

It happens that Integer.getInteger doesn’t parse strings into integers, but rather gets the integer value of a system property named “123.” This property probably doesn’t exist, in which case getInteger returns null. When the null then gets auto unboxed into an int, Java throws an exception.

Or take this example in Objective-C:

[[NSString alloc] initWithContentsOfURL:url 
    encoding:NSUTF8StringEncoding error:&e];

Here, the NSString might be nil, in which case — and only then — the error pointer should be checked. There’s no guarantee the error pointer is valid if the result is non-nil.

In all of the above examples, the function returns a special “magic” value to indicate that it hasn’t returned a real value. Magic values like these are called “sentinel values.”

But this approach is problematic. The result returned looks and feels like a real value. An int of -1 is still a valid integer, but you don’t ever want to print it out. v.end() is an iterator, but the results are undefined if you try to use it. And everyone loves seeing a stack dump when your Java program throws a NullPointerException.

So sentinel values are error prone — you can forget to check the sentinel value and accidentally use it instead. They also require prior knowledge. Sometimes there’s an idiom, as with the C++ end iterator, but not always. Often, you need to check the documentation. And there’s no way for the function to indicate it can’t fail. If a call returns a pointer, that pointer might never be nil. But there’s no way to tell except by reading the documentation, and even then, perhaps the documentation is wrong.

In Objective-C, it’s possible to safely send messages to nil. If the message signature returns an object, it’ll return nil instead, and if the message should return a struct, all its values will be zeroed. However, consider the following snippet:

NSString *someString = ...;
if ([someString rangeOfString:@"swift"].location != NSNotFound) {
    NSLog(@"Someone mentioned swift!");
}

If someString is nil, the rangeOfString: message will return a zeroed NSRange. Hence, the .location will be zero, and NSNotFound is defined as NSIntegerMax. Therefore, the body of the if-statement will be executed if someString is nil.

Null references cause so much heartache that Tony Hoare, credited with their creation in 1965, calls them his “billion-dollar mistake”:

At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn’t resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

Solving the Magic Value Problem with Enumerations

A Tour of Optional Techniques

When to Force-Unwrap

Living Dangerously: Implicit Optionals

Conclusion

Structs and Classes

In Swift, we can choose from multiple options to store structured data: structs, enums, classes, and capturing variables with closures. Most of the public types in Swift’s standard library are defined as structs, with enums and classes making up a much smaller percentage. Part of this may be the nature of the types in the standard library, but it does give an indication as to the importance of structs in Swift. Likewise, in Swift, 3 many of the classes in Foundation now have struct counterparts specifically built for Swift. That said, we’ll focus on the differences between structs and classes in this chapter. Meanwhile, enums behave in a way that’s similar to structs.

Here are some of the major things that help distinguish between structs and classes:

• Structs (and enums) are value types, whereas classes are reference types. When designing with structs, we can ask the compiler to enforce immutability. With classes, we have to enforce it ourselves.

• How memory is managed differs. Structs can be held and accessed directly, whereas class instances are always accessed indirectly through their references. Structs aren’t referenced but instead copied. Structs have a single owner, whereas classes can have many owners.

• With classes, we can use inheritance to share code. With structs (and enums), inheritance isn’t possible. Instead, to share code using structs and enums, we need to use different techniques, such as composition, generics, and protocol extensions.

In this chapter, we’ll explore these differences in more detail. We’ll start by looking at the differences between entities and values. Next, we’ll continue by discussing issues with mutability. Then we’ll take a look at structs and mutability. After that, we’ll demonstrate how to wrap a reference type in a struct in order to use it as an efficient value type. Finally, we’ll compare the differences in how memory is managed — particularly how memory is managed in combination with closures, and how to avoid reference cycles.

Value Types

Mutability

Structs

Copy-On-Write

Closures and Mutability

Memory

Closures and Memory

Conclusion

Functions

To open this chapter, let’s recap some main points regarding functions. If you’re already very familiar with first-class functions, feel free to skip ahead to the next section. But if you’re even slightly hazy, skim through what’s below.

To understand functions and closures in Swift, you really need to understand three things, in roughly this order of importance:

1. Functions can be assigned to variables and passed in and out of other functions as arguments, just as an Int or a String can be.

2. Functions can capture variables that exist outside of their local scope.

3. There are two ways of creating functions — either with the func keyword, or with { }. Swift calls the latter closure expressions.

Sometimes people new to the topic of closures come at it in reverse order and maybe miss one of these points, or conflate the terms closure and closure expression — and this can cause a lot of confusion. It’s a three-legged stool, and if you miss one of the three points above, you’ll fall over when you try to sit down.

1. Functions can be assigned to variables and passed in and out of other functions as arguments.

In Swift, as in many modern languages, functions are referred to as “first-class objects.” You can assign functions to variables, and you can pass them in and out of other functions to be called later.

This is the most important thing to understand. “Getting” this for functional programming is akin to “getting” pointers in C. If you don’t quite grasp this part, everything else will just be noise.

Let’s start with a function that simply prints an integer:

func printInt(i: Int) {
    print("you passed \(i)")
}

To assign the function to a variable, funVar, we just use the function name as the value. Note the absence of parentheses after the function name:

let funVar = printInt

Now we can call the printInt function using the funVar variable. Note the use of parentheses after the variable name:

funVar(2) // you passed 2

We can also write a function that takes a function as an argument:

func useFunction(function: (Int) -> () ) {
    function(3)
}

useFunction(function: printInt) // you passed 3
useFunction(function: funVar) // you passed 3

Why is being able to treat functions like this such a big deal? Because it allows you to easily write “higher-order” functions, which take functions as arguments and apply them in useful ways, as we saw in the chapter on built-in collections.

You can also return functions from other functions:

func returnFunc() -> (Int) -> String {
    func innerFunc(i: Int) -> String {
        return "you passed \(i)"
    }
    return innerFunc
}
let myFunc = returnFunc()
myFunc(3) // you passed 3

2. Functions can capture variables that exist outside of their local scope.

When a function references variables outside the function’s scope, those variables are captured and stick around after they would otherwise fall out of scope and be destroyed.

To see this, let’s revisit our returnFunc function but add a counter that increases each time we call it:

func counterFunc() -> (Int) -> String {
    var counter = 0
    func innerFunc(i: Int) -> String {
        counter += i   // counter is captured
        return "running total: \(counter)"
    }
    return innerFunc
}

Normally counter, being a local variable of counterFunc, would go out of scope just after the return statement, and it’d be destroyed. Instead, because it’s captured by innerFunc, it’ll be kept alive. As we discussed in structs and classes, counter will exist on the heap rather than on the stack. We can call the inner function multiple times, and we see that the running total increases:

let f = counterFunc()
f(3) // running total: 3
f(4) // running total: 7

If we call counterFunc() again, a fresh counter variable will be created and captured:

let g = counterFunc()
g(2) // running total: 2
g(2) // running total: 4

This doesn’t affect our first function, which still has its own captured version of counter:

f(2) // running total: 9

Think of these functions combined with their captured variables as similar to instances of classes with a single method (the function) and some member variables (the captured variables).

In programming terminology, a combination of a function and an environment of captured variables is called a closure. So f and g above are examples of closures, because they capture and use a non-local variable (counter) that was declared outside of them.

3. Functions can be declared using the { } syntax for closure expressions.

In Swift, you can declare functions in two ways. One is with the func keyword demonstrated above. The other way is to use a closure expression. Consider this simple function to double a number:

func doubler(i: Int) -> Int { 
  return i * 2 
}
[1, 2, 3, 4].map(doubler) // [2, 4, 6, 8]

And here’s the same function written using the closure expression syntax. Just like before, we can pass it to map:

let doublerAlt = { (i: Int) -> Int in return i*2 }
[1, 2, 3, 4].map(doublerAlt) // [2, 4, 6, 8]

Functions declared as closure expressions can be thought of as function literals in the same way that 1 and "hello" are integer and string literals. They’re also anonymous — they aren’t named, unlike with the func keyword. The only way they can be used is if you assign them to a variable when they’re created (as we do here with doubler), or if you pass them to another function or method.

The doubler declared using the closure expression, and the one declared earlier using the func keyword, are completely equivalent. They even exist in the same “namespace,” unlike in some languages.

Why is the { } syntax useful then? Why not just use func every time? Well, it can be a lot more compact, especially when writing quick functions to pass into other functions, such as map. Here’s our doubler map example written in a much shorter form:

[1, 2, 3].map { $0 * 2 } // [2, 4, 6]

This looks very different because we’ve leveraged several features of Swift to make code more concise. Here they are one by one:

1. If you’re passing the closure in as an argument and that’s all you need it for, there’s no need to store it in a local variable first. Think of this like passing in a numeric expression, such as 5*i, to a function that takes an Int as a parameter.

2. If the compiler can infer a type from the context, you don’t need to specify it. In our example, the function passed to map takes an Int (inferred from the type of the array elements) and returns an Int (inferred from the type of the multiplication expression).

3. If the closure expression’s body contains just a single expression, it’ll automatically return the value of the expression, and you can leave off the return.

4. Swift automatically provides shorthand names for the arguments to the function — $0 for the first, $1 for the second, etc.

5. If the last argument to a function is a closure expression, you can move the expression outside the parentheses of the function call. This trailing closure syntax is nice if you have a multi-line closure expression, as it more closely resembles a regular function definition or other block statement such as if (expr) { }.

6. Finally, if a function has no arguments other than a closure expression, you can leave off the parentheses after the function name altogether.

Using each of these rules, we can boil down the expression below to the form shown above:

[1, 2, 3].map( { (i: Int) -> Int in return i * 2 } )
[1, 2, 3].map( { i in return i * 2 } )
[1, 2, 3].map( { i in i * 2 } )
[1, 2, 3].map( { $0 * 2 } )
[1, 2, 3].map() { $0 * 2 }
[1, 2, 3].map { $0 * 2 }

If you’re new to Swift’s syntax, and to functional programming in general, these compact function declarations might seem daunting at first. But as you get more comfortable with the syntax and the functional programming style, they’ll start to feel more natural, and you’ll be grateful for the ability to remove the clutter so you can see more clearly what the code is doing. Once you get used to reading code written like this, it’ll be much clearer to you at a glance than the equivalent code written with a conventional for loop.

Sometimes, Swift needs a helping hand with inferring the types. And sometimes, you may get something wrong and the types aren’t what you think they should be. If ever you get a mysterious error when trying to supply a closure expression, it’s a good idea to write out the full form (first version above), complete with types. In many cases, that will help clear up where things are going wrong. Once you have the long form compiling, take the types out again one by one until the compiler complains. And if the error was yours, you’ll have fixed your code in the process.

Swift will also insist you be more explicit sometimes. For example, you can’t completely ignore input parameters. Suppose you wanted an array of random numbers. A quick way to do this is to map a range with a function that just generates random numbers. But you must supply an argument nonetheless. You can use _ in such a case to indicate to the compiler that you acknowledge there’s an argument but that you don’t care what it is:

(0..<3).map { _ in arc4random() } // [3212516738, 784764561, 1751958349]

When you need to explicitly type the variables, you don’t have to do it inside the closure expression. For example, try defining isEven without any types:

let isEven = { $0 % 2 == 0 }

Above, the type of isEven is inferred to be (Int) -> Bool in the same way that let i = 1 is inferred to be Int — because Int is the default type for integer literals.

This is because of a typealias, IntegerLiteralType, in the standard library:

protocol ExpressibleByIntegerLiteral {
    associatedtype IntegerLiteralType
    /// Create an instance initialized to `value`.
    init(integerLiteral value: Self.IntegerLiteralType)
}

/// The default type for an otherwise unconstrained integer literal.
typealias IntegerLiteralType = Int

If you were to define your own typealias, it would override the default one and change this behavior:

typealias IntegerLiteralType = UInt32
let i = 1  // i will be of type UInt32.

This is almost certainly a bad idea.

If, however, you needed a version of isEven for a different type, you could type the argument and return value inside the closure expression:

let isEvenAlt = { (i: Int8) -> Bool in i % 2 == 0 }

But you could also supply the context from outside the closure:

let isEvenAlt2: (Int8) -> Bool = { $0 % 2 == 0 }
let isEvenAlt3 = { $0 % 2 == 0 } as (Int8) -> Bool

Since closure expressions are most commonly used in some context of existing input or output types, adding an explicit type isn’t often necessary, but it’s useful to know.

Flexibility through Functions

Local Functions and Variable Capture

Functions as Delegates

inout Parameters and Mutating Methods

Properties and Subscripts

Automatic Closures

The @escaping Annotation

Conclusion

Strings

No More Fixed Width

Things used to be so simple. ASCII strings were a sequence of integers between 0 and 127. If you stored them in an 8-bit byte, you even had a bit to spare! Since every character was of a fixed size, ASCII strings could be random access.

But this is only if you were writing in English for a U.S. audience; other countries and languages needed other characters (even English-speaking Britain needed a £ sign). Most of them needed more characters than would fit into seven bits. ISO/IEC 8859 takes the extra bit and defines 16 different encodings above the ASCII range, such as Part 1 (ISO/IEC 8859-1, aka Latin-1), covering several Western European languages; and Part 5, covering languages that use the Cyrillic alphabet.

But this is still limiting. If you want use ISO/IEC 8859 to write in Turkish about Ancient Greek, you’re out of luck, since you’d need to pick either Part 7 (Latin/Greek) or Part 9 (Turkish). And eight bits is still not enough to encode many languages. For example, Part 6 (Latin/Arabic) doesn’t include the characters needed to write Arabic-script languages such as Urdu or Persian. Meanwhile, Vietnamese — which is based on the Latin alphabet but with a large number of diacritic combinations — only fits into eight bits by replacing a handful of ASCII characters from the lower half. And this isn’t even an option for other East Asian languages.

When you run out of room with a fixed-width encoding, you have a choice: either increase the size, or switch to variable-width encoding. Initially, Unicode was defined as a 2-byte fixed-width format, now called UCS-2. This was before reality set in, and it was accepted that even two bytes would not be sufficient, while four would be horribly inefficient for most purposes.

So today, Unicode is a variable-width format, and it’s variable in two different senses: in the combining of code units into code points, and in the combining of code points into characters.

Unicode data can be encoded with many different widths of “code unit,” most commonly 8 (UTF-8) or 16 (UTF-16) bits. UTF-8 has the added benefit of being backwardly compatible with 8-bit ASCII — something that’s helped it overtake ASCII as the most popular encoding on the web.

A “code point” in Unicode is a single value in the Unicode code space with a possible value from 0 to 0x10FFFF. Only about 128,000 of the 1.1 million code points possible are currently in use, so there’s a lot of room for more emoji. A given code point might take a single code unit if you’re using UTF-32, or it might take between one and four if you’re using UTF-8. The first 256 Unicode code points match the characters found in Latin-1.

Unicode “scalars” are another unit. They’re all the code points except the “surrogate” code points, i.e. the code points used for the leading and trailing codes that indicate pairs in UTF-16 encoding. Scalars are represented in Swift string literals as "\u{xxxx}", where xxxx represents hex digits. So the euro sign, €, can be written in Swift as "\u{20AC}".

But even when encoded using 32-bit code units, what a user might consider “a single character” — as displayed on the screen — might require multiple code points composed together. Most string manipulation code exhibits a certain level of denial about Unicode’s variable-width nature. This can lead to some unpleasant bugs.

Swift’s string implementation goes to heroic efforts to be as Unicode-correct as possible, or at least when it’s not, to make sure you acknowledge the fact. This comes at a price. String in Swift isn’t a collection. Instead, it’s a type that presents multiple ways of viewing the string: as a collection of Character values; or as a collection of UTF-8, UTF-16, or Unicode scalars.

The Swift Character type is unlike the other views, in that it can encode an arbitrary number of code points, composed together into a single “grapheme cluster.” We’ll see some examples of this shortly.

For all but the UTF-16 view, these views do not support random access, i.e. measuring the distance between two indices or advancing an index by some number of steps is generally not an O(1) operation. Even the UTF-16 view is only random access when you import Foundation (more on that below). Some of the views can also be slower than others when performing heavy text processing. In this chapter, we’ll look at the reasons behind this, as well as some techniques for dealing with both functionality and performance.

Grapheme Clusters and Canonical Equivalence

A quick way to see the difference between Swift.String and NSString in handling Unicode data is to look at the two different ways to write é. Unicode defines U+00E9, “LATIN SMALL LETTER E WITH ACUTE,” as a single value. But you can also write it as the plain letter e, followed by U+0301, “COMBINING ACUTE ACCENT.” In both cases, what’s displayed is é, and a user probably has a reasonable expectation that two strings displayed as “résumé” would not only be equal to each other but also have a “length” of six characters, no matter which technique was used to produce the é in either one. They would be what the Unicode specification describes as “canonically equivalent.”

And in Swift, this is exactly the behavior you get:

let single = "Pok\u{00E9}mon"
let double = "Pok\u{0065}\u{0301}mon"

They both display identically:

And both have the same character count:

single.characters.count // 7
double.characters.count // 7

Only if you drop down to a view of the underlying representation can you see that they’re different:

single.utf16.count // 7
double.utf16.count // 8

Contrast this with NSString: the two strings aren’t equal, and the length property — which many programmers probably use to count the number of characters to be displayed on the screen — gives different results:

let nssingle = NSString(characters: [0x0065,0x0301], length: 2)
nssingle.length // 2
let nsdouble = NSString(characters: [0x00e9], length: 1)
nsdouble.length // 1
nssingle == nsdouble // false

Here, == is defined as the version for comparing two NSObjects:

extension NSObject: Equatable {
    static func ==(lhs: NSObject, rhs: NSObject) -> Bool {
        return lhs.isEqual(rhs)
    }
}

In the case of NSString, this will do a literal comparison, rather than one accounting for equivalent but differently composed characters. NSString.isEqualToString will do the same, and most string APIs in other languages work this way too. If you really want to perform a canonical comparison, you must use NSString.compare. Didn’t know that? Enjoy your future undiagnosable bugs and grumpy international user base.

Of course, there’s one big benefit to just comparing code units: it’s a lot faster! This is an effect that can still be achieved with Swift strings, via the utf16 view:

single.utf16.elementsEqual(double.utf16) // false

Why does Unicode support multiple representations at all? The existence of precomposed characters is what enables the opening range of Unicode code points to be compatible with Latin-1, which already had characters like é and ñ. While they might be a pain to deal with, it makes conversion between the two quick and simple.

Ditching them wouldn’t have helped, because composition doesn’t just stop at pairs; you can compose more than one diacritic together. For example, Yoruba has the character ọ́, which could be written three different ways: by composing ó with a dot, or by composing ọ with an acute, or by composing o with both an acute and a dot. And for that last one, the two diacritics can be in either order! So these are all equal:

let chars: [Character] = [
    "\u{1ECD}\u{300}",      // ọ́
    "\u{F2}\u{323}",        // ọ́
    "\u{6F}\u{323}\u{300}", // ọ́
    "\u{6F}\u{300}\u{323}"  // ọ́
]
chars.dropFirst().all { $0 == chars.first } // true

(The all method checks if the condition is true for all elements in a sequence and is defined in the chapter on built-in collections.)

In fact, some diacritics can be added ad infinitum:

In the above, zalgo.characters.count returns 4, while zalgo.utf16.count returns 36. And if your code doesn’t work correctly with Internet memes, then what good is it, really?

Strings containing emoji can also be a little surprising. For example, a row of emoji flags is considered a single character:

On the other hand, returns 2 (one for the generic character, one for the skin tone), and returns 4 in Swift 3.0, as the multi-person groupings are composed from individual member emoji joined with the zero-width joiner:

While counting the concatenated flags as one character is a weird but expected behavior, these emoji should really be treated as a single character. Expect these results to change as soon as Swift updates its rules for grapheme cluster boundaries to Unicode 9.0, which was released in June 2016.

Strings and Collections

Strings in Swift have an Index associated type, startIndex and endIndex properties, a subscript that takes the index to fetch a specific character, and an index(after:) method that advances an index by one.

This means that String meets all the criteria needed to qualify as conforming to Collection. Yet String is not a collection. You can’t use it with for...in, nor does it inherit all the protocol extensions of Collection or Sequence.

In theory, you can change this yourself by extending String:

extension String: Collection {
    // Nothing needed here – it already has the necessary implementations
}

var greeting = "Hello, world!"
greeting.dropFirst(7) // "world!"

However, this is probably not wise. Strings aren’t collections for a reason — this isn’t just because the Swift team forgot. When Swift 2.0 introduced protocol extensions, this had the huge benefit of granting all collections and sequences method-like access to dozens of useful algorithms. But this also led to some concerns that collection-processing algorithms presenting themselves as methods on strings would give the implicit indication that such methods are completely safe and Unicode-correct, which wouldn’t necessarily be true. Even though Character does its best to present combining character sequences as single values, as seen above, there are still some cases where processing a string character by character can result in incorrect results.

To this end, the collection-of-characters view of strings was moved to a property, characters, which put it on a footing similar to the other collection views: unicodeScalars, utf8, and utf16. Picking a specific view prompts you to acknowledge that you’re moving into a “collection-processing” mode and that you should consider the consequences of the algorithm you’re about to run.

CharacterView, however, has a special place among those views. String.Index is actually just a type alias for CharacterView.Index. This means that once you’ve found an index into the character view, you can then index directly into the string with it.

But for reasons that should be clear from the examples in the previous section, the characters view isn’t a random-access collection. How could it be, when knowing where the n^th character of a particular string is involves evaluating just how many code points precede that character?

For this reason, CharacterView conforms only to BidirectionalCollection. You can start at either end of the string, moving forward or backward, and the code will look at the composition of the adjacent characters and skip over the correct number of bytes. However, you need to iterate up and down one character at a time.

Like all collection indices, string indices conform to Comparable. You might not know how many characters lie between two indices, but you do at least know that one lies before the other.

You can automate iterating over multiple characters in one go via the index(_:offsetBy:) method:

let s = "abcdef"
// Advance 5 from the start
let idx = s.index(s.startIndex, offsetBy: 5)
s[idx] // f

If there’s a risk of advancing past the end of the string, you can add a limitedBy: parameter. The method returns nil if it hits the limit before reaching the target index:

let safeIdx = s.index(s.startIndex, offsetBy: 400, limitedBy: s.endIndex)
safeIdx // nil

This behavior is new in Swift 3.0. The corresponding method in Swift 2.2, advancedBy(_:limit:), didn’t differentiate between hitting the limit and going beyond it — it returned the end value in both situations. By returning an optional, the new API is more expressive.

Now, you might look at this and think, “I know! I can use this to give strings integer subscripting!” So you might do something like this:

extension String {
    subscript(idx: Int) -> Character {
        guard let strIdx = index(startIndex, offsetBy: idx, limitedBy: endIndex)
            else { fatalError("String index out of bounds") }
        return self[strIdx]
    }
}
s[5]  // returns "f"

However, just as is the case with extending String to make it a collection, this kind of extension is best avoided. You might otherwise be tempted to start writing code like this:

for i in 0..<5 {
    print(s[i])
}

As simple as this code looks, it’s horribly inefficient. Every time s is accessed with an integer, an O(n) function to advance its starting index is run. Running a linear loop inside another linear loop means this for loop is accidentally O(n²) — as the length of the string increases, the time this loop takes increases quadratically.

To someone used to dealing with fixed-width characters, this seems challenging at first — how will you navigate without integer indices? And indeed, some seemingly simple tasks like extracting the first four characters of a string can turn into monstrosities like this one:

s[s.startIndex..<s.index(s.startIndex, offsetBy: 4)] // abcd

But thankfully, String providing access to characters via a collection also means you have several helpful techniques at your disposal. Many of the methods that operate on Array also work on String.characters. Using the prefix method, the same thing looks much clearer (note that this returns a CharacterView; to convert it back into a String, we need to wrap it in a String.init):

String(s.characters.prefix(4)) // abcd

Iterating over characters in a string is easy without integer indices; just use a for loop. If you want to number each character in turn, use enumerated():

for (i, c) in "hello".characters.enumerated() {
    print("\(i): \(c)")
}

Or say you want to find a specific character. In that case, you can use index(of:):

var hello = "Hello!"
if let idx = hello.characters.index(of: "!") {
    hello.insert(contentsOf: ", world".characters, at: idx)
}
hello // Hello, world!

Just like Array, String meets all the criteria to conform to RangeReplaceableCollection — but again, it doesn’t conform to it. You could add the conformance manually, but we once more advise against it because it falsely implies that all collection operations are Unicode-safe in every situation:

extension String: RangeReplaceableCollection { }

if let comma = greeting.index(of: ",") {
    print(greeting[greeting.startIndex..<comma])
    greeting.replaceSubrange(greeting.startIndex..<greeting.endIndex,
        with: "How about some original example strings?")
}

One collection-like feature strings do not provide is that of MutableCollection. This protocol adds one feature to a collection — that of the single-element subscript set — in addition to get. This isn’t to say strings aren’t mutable — they have several mutating methods. But what you can’t do is replace a single character using the subscript operator. The reason comes back to variable-length characters. Most people can probably intuit that a single-element subscript update would happen in constant time, as it does for Array. But since a character in a string may be of variable width, updating a single character could take linear time in proportion to the length of the string, because changing the width of a single element might require shuffling all the later elements up or down in memory. Moreover, indices that come after the replaced index would become invalid through the shuffling, which is equally unintuitive. For these reasons, you have to use replaceSubrange, even if the range you pass in is only a single element.

Strings and Slicing

A good sign that a collection function will work well with strings is if the result is a SubSequence of the input. Performing slicing operations on arrays is a bit awkward, as the value you get back isn’t an Array, but rather an ArraySlice. This makes writing recursive functions that slice up their input especially painful.

String’s collection views have no such trouble. They define their SubSequence to be an instance of Self, so the generic functions that take a sliceable type and return a subsequence work very well with strings. For example, world here will be of type String.CharacterView:

let world = "Hello, world!".characters.suffix(6).dropLast()
String(world) // world

split, which returns an array of subsequences, is also useful for string processing. It’s defined like so:

extension Collection {
    func split(maxSplits: Int = default,
        omittingEmptySubsequences: Bool = default,
        whereSeparator isSeparator: (Self.Iterator.Element) throws -> Bool) 
        rethrows -> [AnySequence<Self.Iterator.Element>]
}

You can use its simplest form like this:

let commaSeparatedArray = "a,b,c".characters.split { $0 == "," }
commaSeparatedArray.map(String.init) // ["a", "b", "c"]

This can serve a function similar to the components(separatedBy:) method String inherits from NSString, but with added configurations for whether or not to drop empty components. But since it takes a closure, it can do more than just compare characters. Here’s an example of a primitive word wrap, where the closure captures a count of the length of the line thus far:

extension String {
    func wrapped(after: Int = 70) -> String {
        var i = 0
        let lines = self.characters.split(omittingEmptySubsequences: false) { 
            character in
            switch character {
            case "\n", 
                 " " where i >= after:
                i = 0
                return true
            default:
                i += 1
                return false
            }
        }.map(String.init)
        return lines.joined(separator: "\n")
    }
}

let paragraph = "The quick brown fox jumped over the lazy dog."
paragraph.wrapped(after: 15)
/*
 The quick brown
 fox jumped over
 the lazy dog.
*/

The map on the end of the split is necessary because we want an array of String, not an array of String.CharacterView.

That said, chances are that you’ll want to split things by character most of the time, so you might find it convenient to use the variant of split that takes a single separator:

extension Collection where Iterator.Element: Equatable {
    public func split(separator: Self.Iterator.Element,
        maxSplits: Int = default,
        omittingEmptySubsequences: Bool = default)
        -> [Self.SubSequence]
}

"1,2,3".characters.split(separator: ",").map(String.init) // ["1", "2", "3"]

Or, consider writing a version that takes a sequence of multiple separators:

extension Collection where Iterator.Element: Equatable {
    func split<S: Sequence>(separators: S) -> [SubSequence]
        where Iterator.Element == S.Iterator.Element
    {
        return split { separators.contains($0) }
    }
}

This way, you can write the following:

"Hello, world!".characters.split(separators: ",! ".characters).map(String.init)
// ["Hello", "world"]

A Simple Regular Expression Matcher

ExpressibleByStringLiteral

Internal Structure of String

Code Unit Views

CustomStringConvertible and CustomDebugStringConvertible

Text Output Streams

String Performance

Outlook

Error Handling

Swift provides multiple ways for dealing with errors and even allows us to build our own mechanisms. In the chapter on optionals, we looked at two of them: optionals and assertions. An optional indicates that a value may or may not be there; we have to inspect the optional and unwrap the value before we can use it. An assertion validates that a condition is true; if the condition doesn’t hold, the program crashes.

Looking at the interfaces of types in the standard library can give us a good feel for when to use an optional and when not to. Optionals are used for operations that have a clear and commonly used “not found” or “invalid input” case. For instance, consider the failable initializer for Int that takes a string: it returns nil if the input isn’t a valid integer. Another example: when you look up a key in a dictionary, it’s often expected that the key might not be present. Therefore, a dictionary lookup returns an optional result.

Contrast this with arrays: when looking up an element at a specific index, the element is returned directly and isn’t wrapped in an optional. This is because the programmer is expected to know if an array index is valid. Accessing an array with an index that’s out of bounds is considered a programmer error, and consequently, this will crash your application. If you’re unsure whether or not an index is within bounds, you need to check beforehand.

Assertions are a great tool for identifying bugs in your code. Used correctly, they show you at the earliest possible moment when your program is in a state you didn’t expect. They should never be used to signal expected errors such as a network error.

An alternative to returning an optional from a function that can fail is to mark the function as throws. Besides a different syntax for how the caller must handle the success and failure cases, the key difference to returning an optional is that throwing functions can return a rich error value that carries information about the error that occurred.

This difference is a good guideline for when to use one approach over the other. Consider the first and last properties on Collection again. They have exactly one error condition (the collection is empty) — returning a rich error wouldn’t give the caller more information than what’s already present in the optional value. Compare this to a function that executes a network request: many things can fail, from the network being down, to being unable to parse the server’s response. Rich error information is necessary to allow the caller to react differently to different errors (or just to show the user what exactly went wrong).

The Result Type

Throwing and Catching

Typed Errors

Bridging Errors to Objective-C

Errors and Function Parameters

Cleaning Up Using defer

Errors and Optionals

Chaining Errors

Higher-Order Functions and Errors

Conclusion

Generics

Like most modern languages, Swift has a number of features that can all be grouped under generic programming. Generic code allows you to write reusable functions and data types that can work with any type that matches the constraints you define. For example, types such as Array and Set are generic over their elements. Generic functions are generic over their input and/or output types. The definition func identity<A>(input: A) -> A defines a function that works on any type, identified by the placeholder A. In a way, we can also think of protocols with an associated type as “generic protocols.” The associated type allows us to abstract over specific implementations. IteratorProtocol is an example of such a protocol: it’s generic over the Element type it produces.

The goal of generic programming is to express the essential interface an algorithm or data structure requires. For example, consider the last(where:) method we wrote in the built-in collections chapter. Writing this method as an extension on Array would’ve been the obvious choice, but an Array has lots of capabilities last(where:) doesn’t need. By asking ourselves what the essential interface is — that is, the minimal set of features required to implement the desired functionality — we can make the function available to a much broader set of types. In this example, last(where:) has only one requirement: it needs to traverse a sequence of elements in reverse order. This makes an extension on Sequence the right place for this algorithm.

In this chapter, we’ll look at how to write generic code. We’ll start by talking about overloading because this concept is closely related to generics. We’ll use generic programming to provide multiple implementations of an algorithm, each relying on a different set of assumptions. We’ll also discuss some common difficulties you may encounter when writing generic algorithms for collections. We’ll then look at how you can use generic data types to refactor code to make it testable and more flexible. Finally, we’ll cover how the compiler handles generic code and what we can do to get the best performance for our own generic code.

Overloading

Overloaded functions, i.e. multiple functions that have the same name but different argument and/or return types, are not generic per se. But like generics, they allow us to make one interface available to multiple types.

Overload Resolution for Free Functions

For example, we could define a function named raise(_:to:) to perform exponentiation and provide separate overloads for Double and Float arguments. Based on the types, the right overload gets picked by the compiler:

Operating Generically on Collections

Designing with Generics

How Generics Work

Conclusion

Protocols

In previous chapters, we saw how functions and generics can help us write very dynamic programs. Protocols work together with functions and generics to enable even more dynamic behavior.

Swift protocols aren’t unlike Objective-C protocols. They can be used for delegation, and they allow you to specify abstract interfaces (such as IteratorProtocol or Sequence). Yet, at the same time, they’re very different from Objective-C protocols. For example, we can make structs and enums conform to protocols. Additionally, protocols can have associated types. We can even add method implementations to protocols using protocol extensions. We’ll look at all these things in the section on protocol-oriented programming.

Protocols allow for dynamic dispatch: the correct method implementation is selected at runtime based on the type of the receiver. However, when a method is or isn’t dynamically dispatched is sometimes unintuitive, and this can lead to surprising behavior. We’ll look at this issue in the next section.

Regular protocols can be used either as type constraints or as standalone types. Protocols with associated types and protocols with Self requirements, however, are special: we can’t use them as standalone types; we can only use them as type constraints. This may sound like a small limitation, but it makes protocols with associated types almost entirely different things in practice. We’ll take a closer look at this later. We’ll also discuss type erasers (such as AnyIterator) as a way of making it easier to work with protocols with associated types.

In object-oriented programming, subclassing is a powerful way to share code among multiple classes. A subclass inherits all the methods from its superclass and can choose to override some of the methods. For example, we could have an AbstractSequence class and subclasses such as Array and Dictionary. Doing so allows us to add methods to AbstractSequence, and all the subclasses would automatically inherit those methods.

Yet in Swift, the code sharing in Sequence is implemented using protocols and protocol extensions. In this way, the Sequence protocol and its extensions also work with value types, such as structs and enums, which don’t support subclassing.

Not relying on subclassing also makes types more flexible. In Swift, a class can only have a single superclass. When we create a class, we have to choose the superclass well, because we can only pick one; we can’t subclass both AbstractSequence, and, say, Stream. This can sometimes be a problem. There are examples in Cocoa — e.g. with NSMutableAttributedString, where the designers had to choose between NSAttributedString and NSMutableString as a superclass.

Some languages have multiple inheritance, the most famous being C++. But this leads to something called the “diamond problem.” For example, if multiple inheritance were possible, we could envision an NSMutableAttributedString that inherits from both NSMutableString and NSAttributedString. But what happens if both of those classes override a method of NSString? You could deal with it by just picking one of the methods. But what if that method is isEqual:? Providing good behavior for multiple inheritance is really hard.

Because multiple inheritance is so complicated, most languages don’t support it. Yet many languages do support conforming to multiple protocols, which doesn’t have the same problems. In Swift, we can conform to multiple protocols, and the compiler warns us when the use of a method is ambiguous.

Protocol extensions are a way of sharing code without sharing base classes. Protocols define a minimal viable set of methods for a type to implement. Extensions can then build on these minimal methods to implement more complex features.

For example, to implement a generic algorithm that sorts any sequence, you need two things. First, you need a way to iterate over the elements. Second, you need to be able to compare the elements. That’s it. There are no demands as to how the elements are held. They could be in a linked list, an array, or any iterable container. What they are doesn’t matter, either — they could be strings, integers, dates, or people. As long as you write down the two aforementioned constraints in the type system, you can implement sort:

extension Sequence where Iterator.Element: Comparable {
    func sorted() -> [Self.Iterator.Element]
}

To implement an in-place sort, you need more building blocks. More specifically, you need index-based access to the elements rather than just linear iteration. Collection captures this and MutableCollection adds mutation to it. Finally, you need to compare and offset indices in constant time. RandomAccessCollection allows for that. This may sound complex, but it captures the prerequisites needed to perform an in-place sort:

extension MutableCollection where
    Self: RandomAccessCollection,
    Self.Iterator.Element: Comparable {
        mutating func sort()
}

Minimal capabilities described by protocols compose well. You can add different capabilities of different protocols to a type, bit by bit. We saw this in the collection protocols chapter when we first built a List type by giving it a single method, cons. Without changing the original List struct, we made it conform to Sequence. In fact, we could’ve done this even if we weren’t the original authors of this type, using a technique called retroactive modeling. By adding conformance to Sequence, we get all the extension methods of Sequence for free.

Adding new shared features via a common superclass isn’t this flexible; you can’t just decide later to add a new common base class to many different classes. When you do, you risk major refactoring. And if you aren’t the owner of these subclasses, you can’t do it at all!

Subclasses have to know which methods they can override without breaking the superclass. For example, when a method is overridden, a subclass might need to call the superclass method at the right moment: either at the beginning, somewhere in the middle, or at the end of the method. This moment is often unspecified. Also, by overriding the wrong method, a subclass might break the superclass without warning.

Protocol-Oriented Programming

Two Types of Protocols

Protocols with Self Requirements

Protocol Internals

Conclusion

Interoperability

Hands-On: Wrapping CommonMark

Notice that we force-unwrap the string pointer the function returns. We can safely do this because we know that cmark_markdown_to_html always returns a valid string. By force-unwrapping inside the method, the library user can call the markdownToHTML method without having to worry about optionals — the result would never be nil anyway.

The automatic bridging of native Swift strings to C strings assumes that the C function you want to call expects the string to be UTF-8 encoded. This is the correct choice in most cases, but if the C API assumes a different encoding, you can’t use the automatic bridging. However, it’s often still easy. For example, if you need an array of UTF-16 code points, you can use Array(string.utf16).

Wrapping the cmark_node Type

In addition to the straight HTML output, the cmark library also provides a way to parse a Markdown text into a structured tree of elements. For example, a simple text could be transformed into a list of block-level nodes such as paragraphs, quotes, lists, code blocks, headers, and so on. Some block-level elements contain other block-level elements (for example, quotes can contain multiple paragraphs), whereas others contain only inline elements (for example, a header can contain a part that’s emphasized). No element can contain both (for example, the inline elements of a list item are always wrapped in a paragraph element).

The C library uses a single data type, cmark_node, to represent the nodes. It’s opaque, meaning the authors of the library chose to hide its definition. All we see in the headers are functions that operate on or return pointers to cmark_node. Swift imports these pointers as OpaquePointers. (We’ll take a closer look at the differences between the many pointer types in the standard library, such as OpaquePointer and UnsafeMutablePointer, later in this chapter.)

In the future, we might be able to use the “import as member” feature of Swift to import these functions as methods on cmark_node. Apple has used this to provide more “object-oriented” APIs for Core Graphics and Grand Central Dispatch in Swift. It works by annotating the C source code with the swift_name attribute. Alas, this feature doesn’t really work for the cmark library yet. It might work for your own C library. There are some bugs around import as member, for example, it doesn’t always work with opaque pointers (which is exactly what’s used in cmark).

Let’s wrap a node in a native Swift type to make it easier to work with. As we saw in the chapter on structs and classes, we need to think about value semantics whenever we create a custom type: is the type a value, or does it make sense for instances to have identity? In the former case, we should favor a struct or enum, whereas the latter requires a class. Our case is interesting: on one hand, the node of a Markdown document is a value — two nodes that have the same element type and contents should be indistinguishable, hence they shouldn’t have identity. On the other hand, since we don’t know the internals of cmark_node, there’s no straightforward way to make a copy of a node, so we can’t guarantee value semantics. For this reason, we start with a class. Later on, we’ll write another layer on top of this class to provide an interface with value semantics.

Our class simply stores the opaque pointer and frees the memory cmark_node uses on deinit when there are no references left to an instance of this class. We only free memory at the document level, because otherwise we might free nodes that are still in use. Freeing the document will also automatically free all the children recursively. Wrapping the opaque pointer in this way will give us automatic reference counting for free:

public class Node {
    let node: OpaquePointer

    init(node: OpaquePointer) {
        self.node = node
    }

    deinit {
        guard type == CMARK_NODE_DOCUMENT else { return }
        cmark_node_free(node)
    }
}

The next step is to wrap the cmark_parse_document function, which parses a Markdown text and returns the document’s root node. It takes the same arguments as cmark_markdown_to_html: the string, its length, and an integer describing parse options. The return type of the cmark_parse_document function in Swift is OpaquePointer, which represents the node:

func cmark_parse_document
    (_ buffer: UnsafePointer<Int8>!, _ len: Int, _ options: Int32)
    -> OpaquePointer!

We turn the function into a convenience initializer for our class. Note that the function can return nil if parsing fails. Therefore, our initializer should be failable and return nil (the optional value, not the null pointer) if this occurs:

public init?(markdown: String) {
    let parsed = cmark_parse_document(markdown, markdown.utf8.count, 0)
    guard let node = parsed else { return nil }
    self.node = node
}

As mentioned above, there are a couple of interesting functions that operate on nodes. For example, there’s one that returns the type of a node, such as paragraph or header:

cmark_node_type cmark_node_get_type(cmark_node *node);

In Swift, it looks like this:

func cmark_node_get_type(_ node: OpaquePointer!) -> cmark_node_type

cmark_node_type is a C enum that has cases for the various block-level and inline elements that are defined in Markdown, as well as one case to signify errors:

typedef enum {
    /* Error status */
    CMARK_NODE_NONE,

    /* Block */
    CMARK_NODE_DOCUMENT,
    CMARK_NODE_BLOCK_QUOTE,
    ...

    /* Inline */
    CMARK_NODE_TEXT,
    CMARK_NODE_EMPH,
    ...
} cmark_node_type;

Swift imports plain C enums as structs containing only an Int32. Additionally, for every case in an enum, a top-level variable is generated. Enums marked with the NS_ENUM macro, used by Apple in its Objective-C frameworks, are imported as native Swift enumerations. Additionally, you can annotate your enum cases with swift_name to make them member variables:

struct cmark_node_type : RawRepresentable, Equatable {
    public init(_ rawValue: UInt32)
    public init(rawValue: UInt32)
    public var rawValue: UInt32
}

var CMARK_NODE_NONE: cmark_node_type { get }
var CMARK_NODE_DOCUMENT: cmark_node_type { get }

In Swift, the type of a node should be a property of the Node data type, so we turn the cmark_node_get_type function into a computed property of our class:

var type: cmark_node_type {
    return cmark_node_get_type(node)
}

Now we can just write node.type to get an element’s type.

There are a couple more node properties we can access. For example, if a node is a list, it can have one of two list types: bulleted or ordered. All other nodes have the list type “no list.” Again, Swift represents the corresponding C enum as a struct, with a top-level variable for each case, and we can write a similar wrapper property. In this case, we also provide a setter, which will come in handy later in this chapter:

var listType: cmark_list_type {
    get { return cmark_node_get_list_type(node) }
    set { cmark_node_set_list_type(node, newValue) }
}

There are similar functions for all the other node properties (such as header level, fenced code block info, and link URLs and titles). These properties often only make sense for specific types of nodes, and we can choose to provide an interface either with an optional (e.g. for the link URL) or with a default value (e.g. the default header level is zero). This illustrates a major weakness of the library’s C API that we can model much better in Swift. We’ll talk more about this below.

Some nodes can also have children. For iterating over them, the CommonMark library provides the functions cmark_node_first_child and cmark_node_next. We want our Node class to provide an array of its children. To generate this array, we start with the first child and keep adding children until either cmark_node_first_child or cmark_node_next returns nil, signaling the end of the list. Note that this C null pointer automatically gets converted to an optional:

var children: [Node] {
    var result: [Node] = []
    var child = cmark_node_first_child(node)
    while let unwrapped = child {
        result.append(Node(node: unwrapped))
        child = cmark_node_next(child)
    }
    return result
}

We could also have chosen to return a lazy sequence rather than an array (for example, by using sequence or AnySequence). However, there’s a problem with this: the node structure might change between creation and consumption of the sequence. In that case, the code below will return wrong values, or even worse, crash. Depending on your use case, returning a lazily constructed sequence might be exactly what you want, but if your data structure can change, returning an array is a much safer choice.

With this simple wrapper class for nodes, accessing the abstract syntax tree produced by the CommonMark library from Swift becomes a lot easier. Instead of having to call functions like cmark_node_get_list_type, we can just write node.listType and get autocompletion and type safety. However, we aren’t done yet. Even though the Node class feels much more native than the C functions, Swift allows us to express a node in an even more natural and safer way, using enums with associated values.

A Safer Interface

As we mentioned above, there are many node properties that only apply in certain contexts. For example, it doesn’t make any sense to access the headerLevel of a list or the listType of a code block. Enumerations with associated values allow us to specify only the metadata that makes sense for each specific case. We’ll create one enum for all possible inline elements, and another one for block-level items. That way, we can enforce the structure of a CommonMark document. For example, a plain text element just stores a String, whereas emphasis nodes contain an array of other inline elements. These enumerations will be the public interface to our library, turning the Node class into an internal implementation detail:

public enum Inline {
    case text(text: String)
    case softBreak
    case lineBreak
    case code(text: String)
    case html(text: String)
    case emphasis(children: [Inline])
    case strong(children: [Inline])
    case custom(literal: String)
    case link(children: [Inline], title: String?, url: String?)
    case image(children: [Inline], title: String?, url: String?)
}

Similarly, paragraphs and headers can only contain inline elements, whereas block quotations always contain other block-level elements. A list is defined as an array of Block elements that represent the list items:

public enum Block {
    case list(items: [[Block]], type: ListType)
    case blockQuote(items: [Block])
    case codeBlock(text: String, language: String?)
    case html(text: String)
    case paragraph(text: [Inline])
    case heading(text: [Inline], level: Int)
    case custom(literal: String)
    case thematicBreak
}

The ListType is just a simple enum that states whether a list is ordered or unordered:

public enum ListType {
    case Unordered
    case Ordered
}

Since enums are value types, this also lets us treat nodes as values by converting them to their enum representations. We follow the API Design Guidelines by using initializers for type conversions. We write two pairs of initializers: one pair creates Block and InlineElement values from the Node type, and another pair reconstructs a Node from these enums. This allows us to write functions that transform either InlineElement or Block values and reconstruct a CommonMark document, which can then be rendered into HTML, into man pages, or back into Markdown text.

Let’s start by writing an initializer that converts a Node into an InlineElement. We switch on the node’s type and construct the corresponding Inline value. For example, for a text node, we take the node’s string contents, which we access through the literal property in the cmark library. We can safely force-unwrap literal because we know that text nodes always have this value, whereas other node types might have nil values for literal. For example, emphasis and strong nodes only have child nodes, and no literal value. To parse the latter, we map over the node’s children and call our initializer recursively. Instead of duplicating that code, we create an inline function, inlineChildren, that only gets called when needed. The default case should never get reached, so we choose to trap the program if it does. This follows the convention that returning an optional or using throws should generally only be used for expected errors, and not to signify programmer errors:

extension Inline {
    init(_ node: Node) {
        let inlineChildren = { node.children.map(Inline.init) }
        switch node.type {
        case CMARK_NODE_TEXT:
            self = .text(text: node.literal!)
        case CMARK_NODE_SOFTBREAK:
            self = .softBreak
        case CMARK_NODE_LINEBREAK:
            self = .lineBreak
        case CMARK_NODE_CODE:
            self = .code(text: node.literal!)
        case CMARK_NODE_HTML_INLINE:
            self = .html(text: node.literal!)
        case CMARK_NODE_CUSTOM_INLINE:
            self = .custom(literal: node.literal!)
        case CMARK_NODE_EMPH:
            self = .emphasis(children: inlineChildren())
        case CMARK_NODE_STRONG:
            self = .strong(children: inlineChildren())
        case CMARK_NODE_LINK:
            self = .link(children: inlineChildren(), title: node.title, url: node.urlString)
        case CMARK_NODE_IMAGE:
            self = .image(children: inlineChildren(), title: node.title, url: node.urlString)
        default:
            fatalError("Unrecognized node: \(node.typeString)")
        }
    }
}

Converting block-level elements follows the same pattern. Note that block-level elements can have either inline elements, list items, or other block-level elements as children, depending on the node type. In the cmark_node syntax tree, list items get wrapped with an extra node. In the listItem property on Node, we remove that layer and directly return an array of block-level elements:

extension Block {
    init(_ node: Node) {
        let parseInlineChildren = { node.children.map(Inline.init) }
        let parseBlockChildren = { node.children.map(Block.init) }
        switch node.type {
        case CMARK_NODE_PARAGRAPH:
            self = .paragraph(text: parseInlineChildren())
        case CMARK_NODE_BLOCK_QUOTE:
            self = .blockQuote(items: parseBlockChildren())
        case CMARK_NODE_LIST:
            let type = node.listType == CMARK_BULLET_LIST ?
                ListType.Unordered : ListType.Ordered
            self = .list(items: node.children.map { $0.listItem }, type: type)
        case CMARK_NODE_CODE_BLOCK:
            self = .codeBlock(text: node.literal!, language: node.fenceInfo)
        case CMARK_NODE_HTML_BLOCK:
            self = .html(text: node.literal!)
        case CMARK_NODE_CUSTOM_BLOCK:
            self = .custom(literal: node.literal!)
        case CMARK_NODE_HEADING:
            self = .heading(text: parseInlineChildren(), level: node.headerLevel)
        case CMARK_NODE_THEMATIC_BREAK:
            self = .thematicBreak
        default:
            fatalError("Unrecognized node: \(node.typeString)")
        }
    }
}

Now, given a document-level Node, we can easily convert it into an array of Block elements. The Block elements are values: we can freely copy or change them without having to worry about references. This is very powerful for manipulating nodes. Since values, by definition, don’t care how they were created, we can also create a Markdown syntax tree in code, from scratch, without using the CommonMark library at all. The types are much clearer too; you can’t accidentally do things that wouldn’t make sense — such as accessing the title of a list — as the compiler won’t allow it. Aside from making your code safer, this is a very robust form of documentation — by just looking at the types, it’s obvious how a CommonMark document is structured. And unlike comments, the compiler will make sure that this form of documentation is never outdated.

It’s now very easy to write simple functions that operate on our new data types. For example, if we want to build a list of all the level one and two headers from a Markdown document for a table of contents, we can just loop over all children and check whether they are headers and have the correct level:

func tableOfContents(document: String) -> [Block] {
    let blocks = Node(markdown: document)?.children.map(Block.init) ?? []
    return blocks.filter {
        switch $0 {
        case .heading(_, let level) where level < 3: return true
        default: return false
        }
    }
}

Before we build more operations like this, let’s tackle the inverse transformation: converting a Block back into a Node. We need this because we ultimately want to use the CommonMark library to generate HTML or other text formats from the Markdown syntax tree we’ve built or manipulated, and the library can only deal with cmark_node_type.

Our plan is to add two initializers on Node: one that converts an Inline value to a node, and another that handles Block elements. We start by extending Node with a new initializer that creates a new cmark_node from scratch with the specified type and children. Recall that we wrote a deinit, which frees the root node of the tree (and recursively, all its children). This deinit will make sure that the node we allocate here gets freed eventually:

extension Node {
    convenience init(type: cmark_node_type, children: [Node] = []) {
        self.init(node: cmark_node_new(type))
        for child in children {
            cmark_node_append_child(node, child.node)
        }
    }
}

We’ll frequently need to create text-only nodes, or nodes with a number of children, so let’s add three convenience initializers to make that easier:

extension Node {
    convenience init(type: cmark_node_type, literal: String) {
        self.init(type: type)
        self.literal = literal
    }
    convenience init(type: cmark_node_type, blocks: [Block]) {
        self.init(type: type, children: blocks.map(Node.init))
    }
    convenience init(type: cmark_node_type, elements: [Inline]) {
        self.init(type: type, children: elements.map(Node.init))
    }
}

Now we’re ready to write the two conversion initializers. Using the initializers we just defined, it becomes very straightforward: we switch on the element and create a node with the correct type. Here’s the version for inline elements:

extension Node {
    convenience init(element: Inline) {
        switch element {
        case .text(let text):
            self.init(type: CMARK_NODE_TEXT, literal: text)
        case .emphasis(let children):
            self.init(type: CMARK_NODE_EMPH, elements: children)
        case .code(let text):
            self.init(type: CMARK_NODE_CODE, literal: text)
        case .strong(let children):
            self.init(type: CMARK_NODE_STRONG, elements: children)
        case .html(let text):
            self.init(type: CMARK_NODE_HTML_INLINE, literal: text)
        case .custom(let literal):
            self.init(type: CMARK_NODE_CUSTOM_INLINE, literal: literal)
        case let .link(children, title, url):
            self.init(type: CMARK_NODE_LINK, elements: children)
            self.title = title
            self.urlString = url
        case let .image(children, title, url):
            self.init(type: CMARK_NODE_IMAGE, elements: children)
            self.title = title
            urlString = url
        case .softBreak:
            self.init(type: CMARK_NODE_SOFTBREAK)
        case .lineBreak:
            self.init(type: CMARK_NODE_LINEBREAK)
        }
    }
}

Creating a node from a block-level element is very similar. The only slightly more complicated case is lists. Recall that in the above conversion from Node to Block, we removed the extra node the CommonMark library uses to represent lists, so we need to add that back in here:

extension Node {
    convenience init(block: Block) {
        switch block {
        case .paragraph(let children):
            self.init(type: CMARK_NODE_PARAGRAPH, elements: children)
        case let .list(items, type):
            let listItems = items.map { Node(type: CMARK_NODE_ITEM, blocks: $0) }
            self.init(type: CMARK_NODE_LIST, children: listItems)
            listType = type == .Unordered 
                ? CMARK_BULLET_LIST 
                : CMARK_ORDERED_LIST
        case .blockQuote(let items):
            self.init(type: CMARK_NODE_BLOCK_QUOTE, blocks: items)
        case let .codeBlock(text, language):
            self.init(type: CMARK_NODE_CODE_BLOCK, literal: text)
            fenceInfo = language
        case .html(let text):
            self.init(type: CMARK_NODE_HTML_BLOCK, literal: text)
        case .custom(let literal):
            self.init(type: CMARK_NODE_CUSTOM_BLOCK, literal: literal)
        case let .heading(text, level):
            self.init(type: CMARK_NODE_HEADING, elements: text)
            headerLevel = level
        case .thematicBreak:
            self.init(type: CMARK_NODE_THEMATIC_BREAK)
        }
    }
}

Finally, to provide a nice interface for the user, we define a public initializer that takes an array of block-level elements and produces a document node, which we can then render into one of the different output formats:

extension Node {
    public convenience init(blocks: [Block]) {
        self.init(type: CMARK_NODE_DOCUMENT, blocks: blocks)
    }
}

Now we can go in both directions: we can load a document, convert it into [Block] elements, modify those elements, and turn them back into a Node. This allows us to write programs that extract information from Markdown or even change the Markdown dynamically. By first creating a thin wrapper around the C library (the Node class), we abstracted the conversion from the underlying C API. This allowed us to focus on providing an interface that feels like idiomatic Swift. The entire project is available on GitHub.

An Overview of Low-Level Types

There are many types in the standard library that provide low-level access to memory. Their sheer number can be overwhelming, but they’re named consistently. Here are the most important naming parts:

• A managed type has automatic memory management. The compiler will allocate, initialize, and free the memory for you.

• An unsafe type doesn’t provide automated memory management (as opposed to managed) . You have to allocate, initialize, deallocate, and deinitialize the memory explicitly.

• A buffer type works on multiple (contiguously stored) elements, rather than a single element.

• A pointer type has pointer semantics (just like a C pointer).

• A raw type contains untyped data. It’s the equivalent of a void* in C. Types that don’t contain raw in their name have typed data.

• A mutable type allows the mutation of the memory it points to.

If you want raw storage but don’t need to interact with C, you can use the ManagedBuffer class to allocate the memory. This is what Swift’s collections use under the hood to manage their memory. It consists of a single header value (for storing data such as the number of elements) and contiguous memory for the elements. It also has a capacity property, which isn’t the same as the number of actual elements: for example, an Array with a count of 17 might own a buffer with a capacity of 32, meaning that 15 elements can be added before the Array allocates more memory. There’s also a variant called ManagedBufferPointer, which we won’t discuss here.

Sometimes you need to do manual memory management. For example, in a C API, you might pass in an object as context for a function. However, C doesn’t know about Swift’s memory management. If the API is synchronous, you can just pass in a Swift object, convert it back, and all will be fine (we’ll look at this in detail in the next section). However, if the API is asynchronous, you have to manually retain and release that object, because otherwise it might get deinitialized once it goes out of scope. In order to do that, there’s the Unmanaged type. It has methods for retain and release, as well as initializers that either modify or keep the current retain count.

An UnsafePointer is the simplest of the pointer types and similar to a const pointer in C. It’s generic over the data type of the memory it points to. You can create an unsafe pointer from one of the other pointer types using an initializer. Swift also supports a special syntax for calling functions that take unsafe pointers. You can pass any mutable variable of the correct type to such a function by prefixing it with an ampersand, thereby making it an in-out expression:

var x = 5
func fetch(p: UnsafePointer<Int>) -> Int {
    return p.pointee
}
fetch(p: &x) // 5

This looks exactly like the inout parameters we covered in the functions chapter, and it works in a similar manner — although in this case, nothing is passed back to the caller via this value because the pointer isn’t mutable. The pointer that Swift creates behind the scenes and passes to the function is guaranteed to be valid only for the duration of the function call. Don’t try to return the pointer from the function and access it after the function has returned — the result is undefined. As we stated before, an Unsafe type doesn’t provide any memory management, so we’re relying on the fact that x is still in scope when we call fetch:

There’s also a mutable variant, named UnsafeMutablePointer. This struct works just like a regular C pointer; you can dereference the pointer and change the value of the memory, which then gets passed back to the caller via the in-out expression:

func increment(p: UnsafeMutablePointer<Int>) {
    p.pointee += 1
}
var y = 0
increment(p: &y)
y // 1

Rather than using an in-out expression, you can also allocate memory directly using UnsafeMutablePointer. The rules for allocating memory in Swift are similar to the rules in C: after allocating the memory, you first need to initialize it before you can use it. Once you’re done with the pointer, you need to deallocate the memory:

// Allocate and initialize memory for two Ints
let z = UnsafeMutablePointer<Int>.allocate(capacity: 2)
z.initialize(to: 42, count: 2)
z.pointee // 42
// Pointer arithmetic:
(z+1).pointee = 43
// Subscripts:
z[1] // 43
z.deallocate(capacity: 2)
// Garbage memory
z.pointee // 42

In C APIs, it’s also very common to have a pointer to a sequence of bytes with no specific element type (void* or const void*). The equivalent counterparts in Swift are the UnsafeMutableRawPointer and UnsafeRawPointer types. C APIs that use void* or const void* get imported as these types. Usually, you’d directly convert these types into Unsafe[Mutable]Pointer or other typed variants by using one of their instance methods (such as assumingMemoryBound(to:), bindMemory(to:), or load(fromByteOffset:as:)).

Sometimes a C API has an opaque pointer type. For example, in the cmark library, we saw that the type cmark_node* gets imported as an OpaquePointer. The definition of cmark_node isn’t exposed in the header, and therefore, we can’t access the pointee’s memory. You can convert opaque pointers to other pointers using an initializer.

In Swift, we usually use the Array type to store a sequence of values contiguously. In C, a sequence is often returned as a pointer to the first element and a number of elements. If we want to use such a sequence as a collection, we could turn the sequence into an Array, but that makes a copy of the elements. This is often a good thing (because once they’re in an array, the elements are memory managed by the Swift runtime). However, sometimes you don’t want to make copies of each element. For those cases, there are the Unsafe[Mutable]BufferPointer types. You initialize them with a pointer to the start element and a count. From then on, you have a (mutable) random-access collection. The buffer pointers make it a lot easier to work with C collections.

Finally, in a future version of Swift, the Unsafe[Mutable]RawBufferPointer types will be added. These make it easier to work with raw memory as collections (they provide the low-level equivalent to Data and NSData).

Function Pointers

Let’s have a look at wrapping the standard C qsort sorting function. The type as it’s imported in Swift’s Darwin module (or if you’re on Linux, Glibc) is given below:

public func qsort(
    _ __base: UnsafeMutableRawPointer!,
    _ __nel: Int,
    _ __width: Int,
    _ __compar: @escaping @convention(c) (UnsafeRawPointer?, 
        UnsafeRawPointer?)
    -> Int32)

The man page (man qsort) describes how to use the qsort function:

The qsort() and heapsort() functions sort an array of nel objects, the initial member of which is pointed to by base. The size of each object is specified by width.

The contents of the array base are sorted in ascending order according to a comparison function pointed to by compar, which requires two arguments pointing to the objects being compared.

And here’s a wrapper function that uses qsort to sort an array of Swift strings:

func qsortStrings(array: inout [String]) {
    qsort(&array, array.count, MemoryLayout<String>.stride) { a, b in
        let l = a!.assumingMemoryBound(to: String.self).pointee
        let r = b!.assumingMemoryBound(to: String.self).pointee
        if r > l { return -1 }
        else if r == l { return 0 }
        else { return 1 }
    }
}

Let’s look at each of the arguments being passed to qsort:

• The first argument is a pointer to the base of the array. Swift arrays automatically convert to C-style base pointers when you pass them into a function that takes an UnsafePointer. We have to use the & prefix because it’s an UnsafeMutableRawPointer (a void *base in the C declaration). If the function didn’t need to mutate its input and were declared in C as const void *base, the ampersand wouldn’t be needed. This matches the difference with inout arguments in Swift functions.

• Second, we have to provide the number of elements. This one is easy; we can use the count property of the array.

• Third, to get the width of each element, we use MemoryLayout.stride, not MemoryLayout.size. In Swift, MemoryLayout.size returns the true size of a type, but when locating elements in memory, platform alignment rules may lead to gaps between adjacent elements. The stride is the size of the type, plus some padding (which may be zero) to account for this gap. For strings, size and stride are currently the same on Apple’s platforms, but this won’t be the case for all types — for example, MemoryLayout<Character>.size is 9 and MemoryLayout<Character>.stride is 16. When translating code from C to Swift, you probably want to write MemoryLayout.stride in cases where you would have written sizeof in C.

• The last parameter is a pointer to a C function that’s used to compare two elements from the array. Swift automatically bridges a Swift function type to a C function pointer, so we can pass any function that has a matching signature. However, there’s one big caveat: C function pointers are just pointers; they can’t capture any values. For that reason, the compiler will only allow you to provide functions that don’t capture any external state (for example, no local variables and no generics). It signifies this with the @convention(c) attribute.

The compar function accepts two raw pointers. Such an UnsafeRawPointer can be a pointer to anything. The reason we have to deal with UnsafeRawPointer (and not UnsafePointer<String>) is because C doesn’t have generics. However, we know that we get passed in a String, so we can interpret it as a pointer to a String. We also know the pointers are never nil here, so we can safely force-unwrap them. Finally, the function needs to return an Int32: a positive number if the first element is greater than the second, zero if they’re equal, and a negative number if the first is less than the second.

It’s easy enough to create another wrapper that works for a different type of elements; we can copy and paste the code and change String to a different type and we’re done. But we should really make the code generic. This is where we hit the limit of C function pointers. At the time of writing this book, the Swift compiler segfaulted on the code below. And even if it hadn’t, the code is still impossible: it captures things from outside the closure. More specifically, it captures the comparison and equality operators, which are different for each generic parameter. There’s nothing we can do about this — we simply encountered a limitation of the way C works:

// Valid syntax, but invalid code
extension Array where Element: Comparable {
    mutating func quicksort() {
        qsort(&self, self.count, MemoryLayout<Element>.stride) { a, b in
            let l = a!.assumingMemoryBound(to: Element.self).pointee
            let r = b!.assumingMemoryBound(to: Element.self).pointee
            if r > l { return -1 }
            else if r == l { return 0 }
            else { return 1 }
        }
    }
}

One way to think about this limitation is by thinking like the compiler. A C function pointer is just an address in memory that points to a block of code. In the case of functions that don’t have any context, this address will be static and known at compile time. However, in case of a generic function, an extra parameter (the generic type) is passed in. Therefore, there are no addresses for specialized generic functions. This is the same for closures. Even if the compiler could rewrite a closure in such a way that it’d be possible to pass it as a function pointer, the memory management couldn’t be done automatically — there’s no way to know when to release the closure.

In practice, this is a problem for many C programmers as well. On OS X, there’s a variant of qsort called qsort_b, which takes a block — instead of a function pointer — as the last parameter. If we replace qsort with qsort_b in the code above, it’ll compile and run fine.

However, qsort_b isn’t available on most platforms. And other functions aside from qsort might not have a block-based variant, either. Most C APIs that work with callbacks offer a different solution. They take an extra UnsafeRawPointer as a parameter and pass that pointer on to the callback function. The user of the API can then use this to pass an arbitrary piece of data to each invocation of the callback function. qsort also has a variant, qsort_r, which does exactly this. Its type signature includes an extra parameter, thunk, which is an UnsafeRawPointer. Note that this parameter has also been added to the type of the comparison function pointer because qsort_r passes the value to that function on every invocation:

public func qsort_r(
    _ __base: UnsafeMutableRawPointer!,
    _ __nel: Int,
    _ __width: Int,
    _: UnsafeMutableRawPointer!,
    _ __compar: @escaping @convention(c) 
    (UnsafeMutableRawPointer?, UnsafeRawPointer?, UnsafeRawPointer?) 
        -> Int32
)

If qsort_b isn’t available on our platform, we can reconstruct it in Swift using qsort_r. We can pass anything we want as the thunk parameter, as long as we cast it to an UnsafeRawPointer. In our case, we want to pass the comparison closure. We can automatically create an UnsafeRawPointer out of a variable defined with var by using an in-out expression. So all we need to do is store the comparison closure that’s passed as an argument to our qsort_b variant in a variable named thunk. Then we can pass the reference to the thunk variable into qsort_r. Inside the callback, we cast the void pointer back to its real type, Block, and then simply call the closure:

typealias Block = (UnsafeRawPointer?, UnsafeRawPointer?) -> Int32
func qsort_block(_ array: UnsafeMutableRawPointer, _ count: Int,
                 _ width: Int, f: @escaping Block)
{
    var thunk = f
    qsort_r(array, count, width, &thunk) { (ctx, p1, p2) -> Int32 in
        let comp = ctx!.assumingMemoryBound(to: Block.self).pointee
        return comp(p1, p2)
    }
}

Using qsort_block, we can redefine our qsortWrapper function and provide a nice generic interface to the qsort algorithm that’s in the C standard library:

extension Array where Element: Comparable {
    mutating func quicksort() {
        qsort_block(&self, self.count, MemoryLayout<Element>.stride) { a, b in
            let l = a!.assumingMemoryBound(to: Element.self).pointee
            let r = b!.assumingMemoryBound(to: Element.self).pointee
            if r > l { return -1 }
            else if r == l { return 0 }
            else { return 1 }
        }
    }
}

var x = [3,1,2]
x.quicksort()
x // [1, 2, 3]

It might seem like a lot of work to use a sorting algorithm from the C standard library. After all, Swift’s built-in sort function is much easier to use, and it’s faster in most cases. However, there are many other interesting C APIs out there that we can wrap with a type-safe and generic interface using the same technique.