In Dave Abraham’s WWDC talk, Embracing Algorithms, he talks about finding common algorithms and extracting them into the generic (and testable) functions. One thing in this vein that I like to look for is a few collection operations that cluster together that can be collected into a single operation. Often times, when combining these operations, you’ll also find a beneficial optimization that can be drawn out..

The first example of this is a method added in Swift 3:

// when you see:
myArray.filter({ /* some test */ }).first

// you should change it to:
myArray.first(where: { /* some test */ })

The predicate block stays exactly the same and the result is the same, but it’s shorter, more semantic, and more performant, since it’s not allocating a new array and finding every single object in the array that passes the test — just the first.

Another example is the count(where:) function that I helped add to Swift 5:

// when you see:
myArray.filter({ /* some test */ }).count

// you should change it to:
myArray.count(where: { /* some test */ })

Again: shorter, more semantic, and more performant. No arrays allocated, no extra work done.

In a particular project of ours, we had one common pattern where we would do a sort followed by a prefix. This code, for example, needed to find the 20 most recently created images.

    return images
        .sorted(by: { $0.createdAt > $1.createdAt })
        .prefix(20)

You could also imagine something like a leaderboard, where you want the top 5 users with the highest scores.

I stared at this code until my eyes began to bleed. Something was fishy about it. I started thinking about the time complexity. If you think of the length of the original array as n, and the number of items you want to end up with as m, you can start to analyze the code. The sort is O(nlogn), and prefixing is a very cheap operation, O(1). (Prefixing can be as slow as O(m), but arrays, which are what we are dealing with here, are random access collections and can prefix in constant time.

Here’s what was bugging me: Getting the single smallest element of a sequence (using min()) requires only a single pass over the all of its contents, or O(n). Getting all of the elements ordered by size is a full sort, or O(nlogn). Getting some number m of them where m is smaller than n should be somewhere in between, and if m is much, much smaller than n, it should be even closer to O(n).

In our case, there are lots of images (n is about 55,000) and the amount we’re actually interested in small (m is 20). There should be something to optimize here. Can we optimize sorting such that will only sort the first m elements?

It turns out that, yes, we can do something along those lines. I call this function smallest(_:by:). It takes both the parameters of the sort and the prefix, which are the number m and the comparator to sort with:

func smallest(_ m: Int, by areInIncreasingOrder: (Element, Element) -> Bool) -> [Element] {

Starting with an empty array:

    var result: [Element] = []

We loop over all the elements:

    for element in self {

For each element, we need to find the index of the first item that’s larger than it. Given our areInIncreasingOrder function, we can do this by passing the element first, and each element of result second.

        if let insertionIndex = result.index(where: { areInIncreasingOrder(element, $0) }) {

If an index is found, that means that there’s a value less than element in our result array, and if we insert our new value at that index, it’ll be correctly sorted:

            result.insert(element, at: insertionIndex)

And remove the last element (which is now out of bounds of our number m.

            result.removeLast()

If the index wasn’t found, we can generally ignore the value — except in one specific case. If it’s very early in the algorithm, and the result array hasn’t been filled with the values yet, we know this value is bigger than all the other values currently in the array, and we can just drop it on the end.

        } else if result.count < m {
            result.append(e)
        }
    }

As a side note, it does seem a bit backwards that the code that will get executed first (appending items to the empty array or filling a too-small array) is written after the other if condition (that inserts elements). However, it needs to happen this way, so that elements are inserted at the correct indices, and the final array is correctly sorted.

Lastly, once the for loop is done, we can return the result:

    return result
}

The whole function looks like this:

extension Sequence {
    func smallest(_ m: Int, by areInIncreasingOrder: (Element, Element) -> Bool) -> [Element] {
        var result: [Element] = []
        
        for element in self {
            if let insertionIndex = result.index(where: { areInIncreasingOrder(element, $0) }) {
                result.insert(element, at: insertionIndex)
                result.removeLast()
            } else if result.count < m {
                result.append(element)
            }
        }
        
        return result
    }
}

If this is reminding of you of your early coursework in computer science classes, that’s good! This is very similar to selection sort. (They aren’t exactly the same, because selection sort is a mutating algorithm and this isn’t, and of course because selection sort sorts the whole array.)

The time complexity of this is a bit tougher to analyze, but we can do it. The big outer loop is O(n), and each time it loops, it calls index(where:) (O(m)) and insert(_:at:) (O(m) as well). (Insertion is O(m) because it potentially has to slide all the elements down to make space for the new element.) Therefore, the time complexity of this is O(n * (m + m)), or O(2nm). Constants fall out, leaving us with O(nm).

At this point, we can do a little gut check. If we want m to be all the items in the original array, m and n become equal and O(nm) becomes O(n²), which is what we expected (since selection sort is also O(n²)).

If m is much, much smaller than n, you end up with O(n). That’s a good improvement over our original O(nlogn)! For our original numbers of 55,000 images, that’s should be a roughly five-fold improvement.

This function that we’ve written is broadly an optimization over prefix + sort, but there are two smaller optimizations that I want to discuss here as well.

There’s one pretty low hanging fruit optimization here. We’re looking for the smallest 20 items in an array of 55,000 elements. Most (almost all!) of the elements we check are not going to be needed for our result array. If we throw in one check to see if the element we’re looking at is larger than the last element in the result array, and if it is, just skip it entirely. There’s no sense searching through the array for its insertion index the array is already full and the element is larger than the last element of result.

if let last = result.last, result.count >= m, areInIncreasingOrder(last, element) { continue }

Testing with this check enabled caused a 99.5% drop in linear searches through the result array, and the whole algorithm increased roughly 10x in speed. I want to credit to Greg Titus for pointing this optimization out to me — I would have missed it entirely.

If you want to go take another step, you can do one more (slightly harder to implement) optimization. This one relies on two facts. First, we’re using index(where:) to find the insertion in the result array; second, the result is always sorted. index(where:) is a linear operation by default, but if we’re searching through an already-sorted list, it can be tempting try and replace the linear search with a binary search. I took a crack at this.

To understand how these optimizations affected the performance of the algorithm, Nate Cook helped me become familiar with Karoy Lorentey’s Attabench tool, benchmarking each of these solutions. Because all of our complexity analysis until this point was theoretical, until we actually profile the code we’re concerned with (and ideally on the devices in question), any conclusions are just educated guesses. For example, sort generally is O(nlogn), but different algorithms handle different kinds of data differently. For example, already sorted data might be slower or faster to sort for a particular algorithm.

Attabench showed me a few things.

Profiling data

First, my guess that searching through the array a single time was faster than fully sorting the array was correct. Especially as the sequence in question gets long, sorting gets worse but our “naive optimization” stays constant. (The Y axis represents the time spent per item, rather than total, meaning that O(n) algorithms should be a flat line.)

Second, the “last check” and the binary search optimizations have almost exactly the same performance characteristics when they are on their own (you can’t actually see the yellow line because it’s behind the green), but they provide a little boost to each other when they’re used together. However, because binary search is hard to write and even harder to get right, you may decide it isn’t worth it to add.

The takeaway here for me is that profiling and optimizing is hard. While complexity analysis can seem a bit academic — “When am I going to use this in my real career?” one asks — understanding the time and space complexity of your algorithms can help you decide which directions to explore. In this case, understanding the time complexity of sorting led us towards a broad idea which bore fruit. Finally, benchmarking and profiling with a wide variety of data leads to the most accurate information about how your code will work in production.

And also, next time you see a sort followed by a prefix, think about replacing it with smallest(_: by:).

Foundation’s URL loading is robust. iOS 7 brought the new URLSession architecture, making it even more robust. However, one thing that it’s never been able to do natively is multipart file uploads.

What is a multipart request?

Multipart encoding is the de facto way of sending large files over the internet. When you select a file as part of a form in a browser, that file is uploaded via a multipart request.

A multipart request mostly looks like a normal request, but it specifies a unqiue encoding for the HTTP request’s body. Unlike JSON encoding ({ "key": "value" }) or URL string encoding (key=value), multipart encoding does something a little bit different. Because of the body of a request is just a long stream of bytes, the entity parsing the data on the other side needs to be able to determine when one part ends and another begins. Multipart requests solve this problem using a concept of “boundaries”. In the Content-Type header of the request, you define a boundary:

Accept: application/json
Content-Type: multipart/form-data; boundary=khanlou.comNczcJGcxe

The exact content of the boundary is not important, it just needs to be a series of bytes that is not present in the rest of the body (so that it can meaningfully act as a boundary). You can use a UUID if you like.

Each part can be data (say, an image) or metadata (usually text, associated with a name, to form a key-value pair). If it’s an image, it looks something like this:

--<boundary>
Content-Disposition: form-data; name=<name>; filename=<filename.jpg>
Content-Type: image/jpeg

<image data>

And if it’s simple text:

--<boundary>
Content-Disposition: form-data; name=<name>
Content-Type: text/plain

<some text>

After the last part in the request, there’s one more boundary, which includes an extra two hyphens, --<boundary>--. (Also, note that the new lines all have to be CRLF.)

That’s pretty much it. It’s not a particularly complicated spec. In fact, when I was writing my first client-side implementation of multipart encoding, I was a bit scared to read the RFC for multipart/form-data. Once I took a look at it, however, I understood the protocol a lot better. It’s surprisingly readable, and nice to go straight to the source for stuff like this.

That first implementation was in the Backchannel SDK, which is still open source. You can see the BAKUploadAttachmentRequest and the BAKMultipartRequestBuilder, which combine to perform the bulk of the multipart handling code. This particular implementation only handles a single file and no metadata, but it serves as an example of how this request can be constructed. You could modify it to support metadata or multiple files by adding extra “parts”.

However, if you want to upload multiple files, whether your service expects one request with many files or many requests with one file each, you’ll soon run into a problem. If you try to upload too many files at once, your app will crash. Because this version of the code loads the data that will be uploaded into memory, a few dozen full-size images can crash even the most modern phones.

Streaming files off the disk

The typical solution to this is to “stream” the files off the disk. The idea is that the bytes for any given file stay on the disk, until the moment they’re needed, at which point they’re read off the disk and sent straight to the network machinery. Only a small amount of the bytes for the images is in memory at any given time.

I came up with two broad approaches to solving this problem. First, I could write the entire data for the multipart request body to a new file on disk, and use an API like URLSession’s uploadTask(with request: URLRequest, fromFile fileURL: URL) to stream that file to the API. This would work, but it seemed like it should be possible to accomplish this without writing a new file to the disk for each request. There would also be a bit of cleanup to handle after the request has been sent.

The second approach is to build a way to mix data in memory with data on the disk, and present an interface to the network loading architecture that looks like a chunk of data from a single source, rather than many.

If you’re thinking this sounds like a case for class clusters, you’re dead on. Many common Cocoa classes allow you to make a subclass that can act as the super class by implementing a few “primitive” methods. Think -count and -objectAtIndex: on NSArray. Since every other method on NSArray is implemented in terms of those two, you can write optimized NSArray subclasses very easily.

You can create an NSData that doesn’t actually read any data off the disk, but rather creates a pointer directly to the data on disk, so that it never has to load the data into memory to read it. This is called memory mapping, and it’s built on a Unix function called mmap. You can use this feature of NSData by using the .mappedIfSafe or .alwaysMapped reading options. And NSData is a class cluster, so if we could make a ConcatenatedData subclass (that works like FlattenCollection in Swift) that allows you treat many NSData objects as one continuous NSData, we would have everything we need to solve this problem.

However, when we look at the primitive methods of NSData, we see that they are -count and -bytes. -count isn’t a big deal, since we can easily sum up the counts of all the child datas; -bytes, however, poses a problem. -bytes should return a pointer to a single continuous buffer, which we won’t have.

To handle discontinuous data, Foundation gives us NSInputStream. Fortunately, NSInputStream is also a class cluster. We can create a subclass that makes many streams look like one. And with APIs like +inputStreamWithData: and +inputStreamWithURL:, we can easily create input streams that represent the files on the disk and the data in memory (such as our boundaries).

If you look at the major third-party networking libraries, you’ll see that this is how AFNetworking actually works. (Alamofire, the Swift version of AFNetworking, loads everything into memory but writes it to a file on disk if it is too big.)

Putting all the pieces together

You can see my implementation of a serial InputStream here (Objective-C, but I’ll probably write a Swift version soon as well).

Once you have something like SKSerialInputStream, you can combine streams together. Given a way to make the prefix and postfix data for a single part:

extension MultipartComponent {
    var prefixData: Data {
        let string = """
        \(self.boundary)
        Content-Disposition: form-data; name="\(self.name); filename="\(self.filename)"
        """
        return string.data(using: .utf8)
    }
    
    var postfixData: Data {
        return "\r\n".data(using: .utf8)
    }
}

You can compose the metadata for the upload and the dataStream for the file to upload together into one big stream.

extension MultipartComponent {
    var inputStream: NSInputStream {
        
        let streams = [
            NSInputStream(data: prefixData),
            self.fileDataStream,
            NSInputStream(data: postfixData),
        ]
    
        return SKSerialInputStream(inputStreams: streams)
    }
}

Once you can create an input stream for each part, you can join them all together to make an input stream for the whole request, with one extra boundary at the end to signal the end of the request:

extension RequestBuilder {
    var bodyInputStream: NSInputStream {
        let stream = parts
            .map({ $0.inputStream })
            + [NSInputStream(data: "--\(self.boundary)--".data(using: .utf8))]
    
        return SKSerialInputStream(inputStreams: streams)
    }
}

Finally, assigning that to the httpBodyStream of your URL request completes the process:

let urlRequest = URLRequest(url: url)

urlRequest.httpBodyStream = requestBuilder.bodyInputStream;

The httpBodyStream and httpBody fields are exclusive — only one can be set. Setting the input stream invalidates the Data version and vice versa.

The key to streaming file uploads is being able to compose many disparate input streams into one. Something like SKSerialInputStream makes the process a lot more manageable. Even though subclassing NSInputStream can be a bit perilous, as we’ll see, once it’s solved the solution to the problem falls out more or less naturally.

Subclassing notes

The actual process of subclassing NSInputStream wasn’t fun. Broadly put, subclassing NSInputStream is hard. You have to implement 9 methods, 7 of which can have trivial default implementations that the superclass should handle. The documentation only mentions 3 of the 9 methods, and you have to dig to find out that you have to implement 6 more methods from NSStream (the superclass of NSInputStream) including two run loop methods where empty implementations are valid. There also used to be 3 private methods that you had to implement, though they don’t seem to be a concern any longer. Once you’ve implemented these methods, you also have to support several readonly properties as well: streamStatus, streamError, and delegate need to be defined.

Once you get all the details about subclassing right, you get to the challenge of providing an NSInputStream that behaves in a way that other consumers would expect. The state of this class is heavily coupled in non-obvious ways.

There are a few pieces of state, and they all need to act in concert at all times. For example, hasBytesAvailable is defined separately from the other state, but there are still subtle interactions. I found a late-breaking bug where my serial stream would ideally return self.currentIndex != self.inputStreams.count for hasBytesAvailable, but that caused a bug where the stream stayed open forever and would cause a timeout for the request. I patched over this bug by always returning YES, but I never figured out the root of it.

Another piece of state, streamStatus, has many possible values, but the only ones that seem to matter are NSStreamStatusOpen and NSStreamStatusClosed.

The final interesting piece of state is the byte count, returned from the read method. In addition to returning a positive integer for the byte count, a stream can return a byte count of -1, which indicates an error, which then has to be checked by via the streamError property, which must no longer be nil. It can also return a byte count of 0, which, according to the documentation, is another way that to indicate that the end of the stream has been reached.

The documentation doesn’t guide you what combinations of states are valid. If my stream has a streamError, but the status is NSStreamStatusClosed rather than NSStreamStatusError, will that cause a problem? Managing all this state is harder than it needs to be, but it can be done.

I’m still not fully confident that SKSerialStream behaves perfectly in all situations, but it seems to support uploading multipart data via URLSession well. If you use this code and find any issues, please reach out and we can make the class better for everyone.

Swift 4.2 brings some new changes to how hashing works in Swift. Previously, hashing was fully delegated to the object itself. You would ask an object for its hashValue, and it would respond with the fully cooked integer representing the hash. Now, objects that conform to Hashable describe how to combine their constituent components into a Hasher object that’s passed in as a parameter. This is great for a few reasons.

  • Good hashing algorithms are hard to write. End users of Swift shouldn’t be responsible for knowing the best way to combine their constituent components into a good hash value.
  • Hash values should be different for each execution of the program, to discourage users from storing them in any way and for security reasons. Descriptive hashing allows the seeds of the hashing function to change each time you run the program.
  • It makes more interesting data structures possible, which is what we’re going to focus on in this post.

I’ve written here before about how to use Swift’s Hashable protocol to write a Dictionary from scratch (and it will help to read that post before this one, but isn’t necessary). Today, I want to talk about a different kind of data structure, one that’s probabilistic rather than definite: the Bloom filter. As we build it, we’ll use a few new features in Swift 4.2, including the new hashing model.

Bloom filters are weird. Imagine a data structure where:

  • you can insert values into it
  • you can query it to see if a value is contained in it
  • it can use a tiny amount of storage to a store a huge amount of objects

but:

  • you can’t enumerate the objects in it
  • it sometimes has false positives (but never false negatives)
  • you can’t remove values from them

When would you want something like this? Medium uses them to keep track of the read status of posts. Bing uses them for search indexes. You could use them to build a cache for if a username is valid (in an @-mention, for example) without having to hit the database. They’re particularly useful on the server, where you could have immense scale but not necessarily immense resources.

(If you’ve ever done any graphics work, you might be wondering how this relates to the other bloom filter. The answer is, it doesn’t. That bloom filter is a lowercase b bloom, like a flower. This one is named after a person named Bloom. Total coincidence.)

How do they work?

Putting an object into a Bloom filter is sort of like putting it into a set or a dictionary: you need to calculate a hash value for the object and mod the hash value by the size of your storage array. At that point, instead of storing the value at that position in the index (like you would with a set or a dictionary), you simply flip a bit at that index: change a value from false to true.

Let’s take a simple example to understand how the filter works, and then we’ll crank it up to make it web scale. Imagine a boolean array (sometimes called a bit array) of 8 false values:

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---------------------------------
|   |   |   |   |   |   |   |   |

This represents our Bloom filter. I’d like to insert the string “soroush” into it. The string hashes to 9192644045266971309, which, when modded by 8, yields 5. I’ll flip the bit at that index.

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---------------------------------
|   |   |   |   |   | * |   |   |

Next, I’d like to insert the string, “swift”. It yields a hash of 7052914221234348788, which we then mod by 8: flip the bit at index 4.

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---------------------------------
|   |   |   |   | * | * |   |   |

To test if the Bloom filter contains the string “soroush”, I hash and mod again, yielding 5 again, which is set to true. “soroush” is indeed in the Bloom filter.

You can’t just test the cases where your thing works though, so let’s write some negative tests. Testing the string “khanlou” yields an index of 2, so we know it’s not in the bloom filter. So far, so good. Next test: the string “hashable” yields an index of 5, which…causes a collision! It returns true even though the value was never inserted into the Bloom filter. This is an example of a Bloom filter giving you a false positive.

Since we want to minimize these false positives, there are two main strategies we can use. First, and the more interesting of the two: instead of hashing the value once, we can hash it twice, or three times, with different hashing functions. As long as they are all well-behaved hashing functions (evenly distributed, consistent, minimal collisions), we can generate multiple indices to flip for each value. Now, when we hash “soroush”, we do it twice, and generate two indices, and flip the bools there. But now, when we go to check if “khanlou” is included in the Bloom filter, one of its hashes will collide with one of the hashes for “soroush”, but the chance that both of its hashes will collide has become smaller. You can scale this number up. I’ll use the 3 hashes in the code below, but you could use more.

Of course, if you use more hashes, each element will take up more space in the bit array. However, we’re using practically nothing right now. Our data array is 8 booleans (or bits) which is 1 byte. So the second tactic for minimizing false positives is to scale the bit array up. We can make it pretty big before we even start noticing it. We’ll use a default of 512 bits for the code example below.

Now, even using both of these strategies, you’ll still get collisions, and thus false positives, but you’ll get fewer of them. This is one of the downsides of using Bloom filters, but in the right circumstances, the speed and space savings are a worthwhile tradeoff.

I want to touch on three other things to note before we get into code. First, you can’t resize a Bloom filter. When you mod the hash value, you’re destroying information, and you can’t get that information back unless you keep the original hashes around — defeating the dramatic space savings you can get with this data structure.

Secondly, you can see how it would be impossible to enumerate the elements in a Bloom filter. You don’t have them anymore, just some of their artifacts (in the form of hashes).

Lastly, you can also see how you can’t remove elements from a Bloom filter. If you try to flip the bits back to false, you don’t know who had originally flipped them to true. The value you’re trying to remove, or a different value? You’d start causing false negatives as well as false positives. (This may actually be a worthwhile tradeoff for you!) You could get around this by keeping a count at each index instead of a boolean, which would also have storage implications, but again, could be worthwhile depending on your use case.

So, let’s get to some code. There are some choices that I’ll make here that you might choose to make differently, starting with whether or not to make the object generic. I think it makes sense to have the object have a little more metadata about what it’s supposed to be storing, but if you find that too restrictive, you can change it.

struct BloomFilter<Element: Hashable> {
	// ...
}

We need to store two main things in this type. First, data, which represent our bit array. This will store all the flags that correspond to the hashes:

private var data: [Bool]

Next, we need our different hash functions. Some Bloom filters use actually different methods of computing the hash, but I think it’s easier to use the same algorithm, but mix in one additional randomly generated value.

private let seeds: [Int]

When setting up the Bloom filter, we need to set up both instance variables. Our bit array is going to simply repeat the false value, and our seeds will use Swift 4.2’s new Int.random API to generate the seeds we need.

init(size: Int, hashCount: Int) {
	data = Array(repeating: false, count: size)
	seeds = (0..<hashCount).map({ _ in Int.random(in: 0..<Int.max) })
}

I also included a convenience initializer with some nice defaults.

init() {
	self.init(size: 512, hashCount: 3)
}

There are two main functions we need to write: insert and contains. They both need to take the element and calculate one hash value for each of the seeds. Great fodder for a private helper function. We need to create one hash value for each seed, because our seed values represent the “different” hashing functions.

private func hashes(for element: Element) -> [Int] {
	return seeds.map({ seed -> Int in
		// ...
	})
}

To write the body of this function, we need to create a Hasher (new in Swift 4.2), and pass in the object we want to hash. Mixing in the seed as well ensures that the hashes won’t collide.

private func hashes(for element: Element) -> [Int] {
	return seeds.map({ seed -> Int in
		var hasher = Hasher()
		hasher.combine(element)
		hasher.combine(seed)
		let hashValue = abs(hasher.finalize())
		return hashValue
	})
}

Also, note the absolute value on the hash value. Hashes can come back as negative, which will crash our array access later. This removes one bit of entropy, which is probably fine.

Ideally, you’d be able to initialize the Hasher with a seed, instead of mixing it in. Swift’s Hasher uses a different seed for each launch of the application (unless you set an environment variable which they added for consistent hashing between launch, mostly for testing purposes), meaning you can’t write these values to disk. If we controlled the seed of the Hasher, then we could write these values to disk as well. As this Bloom filter currently stands, it should only be used for in-memory caches.

The hashes(for:) function does a lot of the heavy lifting, and makes our insert method very straightforward:

mutating func insert(_ element: Element) {
	hashes(for: element)
		.forEach({ hash in
			data[hash % data.count] = true
		})
}

Generate all the hashes, mod each one by the length of the data array, and set the bit at that index to true.

contains is likewise simple, and gives us a chance to use another new Swift 4.2 feature, allSatisfy. This new function tells you if all of the objects in the sequence pass some test, represented by a block:

func contains(_ element: Element) -> Bool {
	return hashes(for: element)
		.allSatisfy({ hash in
			data[hash % data.count]
		})
}

Because the result of data[hash % size] is already a boolean, it fits quite nicely into allSatisfy.

You can also add an isEmpty method that checks if all of the values in the data are false.

Bloom filters are one of the weirder data structures. Most of the data structures we deal with are deterministic. When you put an object in a dictionary, you know it’ll be there later. Bloom filters, on the other hand, are probabilistic, sacrificing certainty for space and speed. Bloom filters aren’t something that you’ll use every day, but when you do need them, you’ll be happy to know they exist.

Back in the days before Crusty taught us “protocol-oriented programming”, sharing of implementations happened mostly via inheritance. In an average day of UIKit programming, you might subclass UIView, add some child views, override -layoutSubviews, and repeat. Maybe you’ll override -drawRect. But on weird days, when you need to do weird things, you start to look at those other methods on UIView that you can override.

One of the more eccentric corners of UIKit is the touch handling subsystem. This primarily includes the two methods -pointInside:withEvent: and -hitTest:withEvent:.

-pointInside: tells the caller if a given point is inside a given view. -hitTest: uses -pointInside: to tell the caller which subview (if any) would be the receiver for a touch at a given point. It’s this latter method that I’m interested in today.

Apple gives you barely enough documentation to figure out how to reimplement this method. Until you learn to reimplement it, you can’t change how it works. Let’s check out the documentation and try to write the function.

override func hitTest(_ point: CGPoint, with event: UIEvent?) -> UIView? {
	// ...
}

First, let’s start with a bit from the second paragraph:

This method ignores view objects that are hidden, that have disabled user interactions, or have an alpha level less than 0.01.

Let’s put some quick guard statements up front to handle these preconditions.

override func hitTest(_ point: CGPoint, with event: UIEvent?) -> UIView? {

	guard isUserInteractionEnabled else { return nil }
	
	guard !isHidden else { return nil }
	
	guard alpha >= 0.01 else { return nil }
			
	// ...

Easy enough. What’s next?

This method traverses the view hierarchy by calling the -pointInside:withEvent: method of each subview to determine which subview should receive a touch event.

While a literal reading of the documentation makes it sound like -pointInside: is called on each of the subviews inside a for loop, this isn’t quite correct.

Thanks to a reader dropping breakpoints in -hitTest: and -pointInside:, we know -pointInside: is called on self (with the other guards), rather than on each of the subviews. So we can add this line of code to the other guards:

guard self.point(inside: point, with: event) else { return nil }

-pointInside: is another override point for UIView. Its default implementation checks if the point that is passed in is contained within the bounds of the view. If a view returns true for the -pointInside: call, that means the touch event was contained within its bounds.

With that minor discrepency out of the way, we can continue with the documentation:

If -pointInside:withEvent: returns YES, then the subview’s hierarchy is similarly traversed until the frontmost view containing the specified point is found.

So, from this, we know we need to iterate over the view tree. This means looping over all the views, and calling -hitTest: on each of those to find the proper child. In this way, the method is recursive.

To iterate the view hierarchy, we’re going to need a loop. However, one of the more counterintuitive things about this method is we need to iterate the views in reverse. Views that are toward the end of the subviews array are higher in Z axis, and so they should be checked out first. (I wouldn’t quite have picked up on this point without this blog post.)

// ...
for subview in subviews.reversed() {

}
// ...

The point that we are passed is defined relative to the coordinate system of this view, not the subview that we’re interested in. Fortunately UIKit gives us a handy function to convert points from our reference to the reference frame of any other view.

// ...
for subview in subviews.reversed() {
	let convertedPoint = subview.convert(point, from: self)
	// ...
}
// ...

Once we have a converted point, we can simply ask each subview what view it thinks is at that point. Remember, if the point lies outside that view (i.e., -pointInside: returns false), the -hitTest will return nil, and we’ll check the next subview in the hierarchy.

// ...
let convertedPoint = subview.convert(point, from: self)
if let candidate = subview.hitTest(convertedPoint, with: event) {
	return candidate
}
//...

Once we have our loop in place, the last thing we need to do is return self. If the view is tappable (which all of our guard statements assert), but none of our subviews want to take this touch, that means that the current view, self, is the correct target for the touch.

Here’s the whole algorithm:

override func hitTest(_ point: CGPoint, with event: UIEvent?) -> UIView? {
	
	guard isUserInteractionEnabled else { return nil }
	
	guard !isHidden else { return nil }
	
	guard alpha >= 0.01 else { return nil }
	
	guard self.point(inside: point, with: event) else { return nil }	
	
	for subview in subviews.reversed() {
		let convertedPoint = subview.convert(point, from: self)
		if let candidate = subview.hitTest(convertedPoint, with: event) {
			return candidate
		}
	}
	return self
}

Now that we have a reference implementation, we can begin to modify it to enable specific behaviors.

I’ve discussed one of those behaviors on this blog before, in Changing the size of a paging scroll view, I talked about the “old and busted” way to create this effect. Essentially, you’d

  1. turn off clipsToBounds.
  2. put an invisible view over the scrollable area.
  3. override -hitTest: on the invisible view to pass all touches through to the scrollview.

The -hitTest: method was the cornerstone of this technique. Because hit testing in UIKit is delegated to each view, each view gets to decide which view receives its touches. This enables you to override the default implementation (which does something expected and normal) and replace it with whatever you want, even returning a view that’s not a direct child of the original view. Pretty wild.

Let’s take a look at a different example. If you’ve played with this year’s version of Beacon, you might have noticed that the physics for the swipe-to-delete behavior on events feel a little different from the built-in stuff that the rest of the OS uses. This is because we couldn’t quite get the appearance we wanted with the system approach, and we had to reimplement the feature.

As you can imagine, rewriting the physics of swiping and bouncing is needlessly complicated, so we used a UIScrollView with pagingEnabled set to true to get as much of the mechanics of the bouncing for free. Using a technique similar to an older post on this blog, we set a custom page size by making our scroll view bounds smaller and moving the panGestureRecognizer to an overlay view on top of the event cell.

However, while the overlay correctly passes touch events through to the scroll view, there are other events that the overlay incorrectly intercepts. The cell contains buttons, like the “join event” button and the “delete event” button that need to be able to receive touches. There are a few custom implementations of the -hitTest: method that would work for this situation; one such implementation is to explicitly check the two button subviews:

override func hitTest(_ point: CGPoint, with event: UIEvent?) -> UIView? {

	guard isUserInteractionEnabled else { return nil }
	
	guard !isHidden else { return nil }
	
	guard alpha >= 0.01 else { return nil }

	guard self.point(inside: point, with: event) else { return nil }

	if joinButton.point(inside: convert(point, to: joinButton), with: event) {
		return joinButton
	}
	
	if isDeleteButtonOpen && deleteButton.point(inside: convert(point, to: deleteButton), with: event) {
		return deleteButton
	}
	return super.hitTest(point, with: event)
}

This correctly forwards the right tap events to the right buttons without breaking the scrolling behavior that reveals the delete button. (You could try ignoring just the deletionOverlay, but then it won’t correctly forward scroll events.)

-hitTest: is an override point for views that is rarely used, but when needed, can provide behaviors that are hard to build using other tools. Knowing how to implement it yourself gives you the ability to replace it at will. You can use the technique to make tap targets bigger, remove certain subviews from touch handling without removing them from the visible hierarchy, or use one view as a sink for touches that will affect a different view. All things are possible!

Martin Fowler’s seminal 1999 book Refactoring includes a chapter with Kent Beck on “code smells”. Code smells, they say, are “certain structures in the code that suggest (sometimes they scream for) the possibility of refactoring”. One of the code smells they talk about is the Data Clump.

Often you’ll see the same three or four data items together in lots of places: fields in a couple of classes, parameters in many method signatures. Bunches of data that hang around together really ought to be made into their own object.

They give a quick test for a data clump: if you delete one of the data values, would the others make sense?

This is a good test, and in today’s article, I’d like to propose another useful way to detect data clumps. To be honest, I thought I’d read this elsewhere, but I’ve done some deep googling and scouring of the original texts, and I can’t find any reference to it anywhere. If you do find a good reference to this thought technology, please be sure to reach out. Update: I found it. In Sandi Metz’s 2014 RailsConf talk, All the Little Things, she discusses this at ~22:30.

If two or more instance variables (or parameters in a parameter list, etc) have a similar prefix or suffix, they’re probably a data clump. They should be associated with each other more closely than being placed next to each other.

Three distinct examples of this stick out to me.

The second app I ever made, Fireside, was a podcast player, and (among its many mistakes) it had the following in its Podcast model:

@property (nonatomic, copy) NSString *filePath;
@property (nonatomic, assign) BOOL isDownloaded;
@property (nonatomic, assign) BOOL fullyDownloaded;
@property (nonatomic, strong) NSDate *expirationDate;

@property (nonatomic, copy) NSString *streamedCopyFilePath;
@property (nonatomic, assign) BOOL streamedCopyIsDownloaded;
@property (nonatomic, assign) BOOL streamedCopyFullyDownloaded;
@property (nonatomic, strong) NSDate *streamedCopyExpirationDate;

(Pardon the Objective-C, this code is from 2011.)

In the fullness of time, it’s so obvious that this is a bad model. These four properties, filePath, isDownloaded, isFullyDownloaded, and expirationDate, should live on a new class, maybe called DownloadDetails, which would also serve as a nice home for any logic around this data, such as if the download is past its expiration date.

(If you’re wondering why there are two boolean values for the downloaded state, fullyDownloaded represents if the podcast is downloaded from the first byte to the end, and isDownloaded represents if the podcast has been downloaded from any point, such as a point the user has scrubbed to, to the end. These days, I’d probably make it an enum with three states: not downloaded, downloaded, and fully downloaded, but that’s another post.)

The matching prefixes on the properties are the clue here that concepts are duplicated. Seeing them now, they’re begging for refactoring.

Another classic example of similar prefixes can be found in the view layer. Raise your hand if you’ve done this one:

let headerContainer = UIView()

let headerBackgroundImage = UIImageView()

let headerAvatarImage = UIImageView()

let headerTitle = UILabel()

let headerDescription = UILabel()

If you’re making a bunch of views that all have the same prefix, chances are they represent a logical unit. In this case, they even have a common superview, the headerContainer. Are you really sure you’re not going to reuse these 5 views and their layout? Make the HeaderView class, don’t be lazy. (H/t to Rosa McGee for this example, and John Sundell for a blog post in a similar vein.)

The last example I want to look at happened recently, and was the impetus for this blog post. The original code wasn’t the worst code, but it was sprinkled into 600 lines of unrelated singleton code:

private var sequenceStartTime: Date?
private var sequencePauseTime: Date?

// 150 lines of other stuff

func startSequenceTimer() {		
	self.sequenceStartTime = Date()
}

func pauseSequenceTimer() {		
	self.sequencePauseTime = Date()
}

// 50 lines of unrelated responsibilities 

func resumeSequenceTimer() {		
	let pauseEndTime = Date()		
	let duration = pauseEndTime.timeIntervalSince1970 - sequencePauseTime.timeIntervalSince1970
	self.sequenceStartTime = Date().addingTimeInterval(duration)
}

// 100 more lines of just whatever

func calculateDuration() {
	let sequenceEndTime = Date()
	let duration: Double		
	if let startTime = sequenceStartTime {
		duration = Double(sequenceEndTime.timeIntervalSince1970 - sequenceStartTimetimeIntervalSince1970) / 1_000
	} else {
		duration = 0.0
	}
	return duration
}

This is clearly its own responsibility, and the start and end time variables are the first clue into that. This singleton doesn’t care about how to pause the timer or calculate the current running duration, it just needs to be able to pause a timer. This eventually became its own type and the two instance variables became the central identity of the type:

struct Milliseconds {
	let rawValue: Int
}

protocol Clock {
	func now() -> Milliseconds
}

class Stopwatch {
 
	let clock: Clock
	
	private var startTime: Milliseconds?
	 
	private var pauseTime: Milliseconds?

	// ...
	
}

The Clock protocol also enables the type to be tested, which wasn’t possible before. (H/t to Olivier Halligon showing me how to test this class.) The tests also enabled me to fix a few bugs in the original code. (If you’re wondering what kinds of bugs, look at the original code: what happens if you’ve currently paused and you try to check the duration?)

Extracting data clumps is a great way to find hidden classes and responsibilities within your code, and a great way to locate their hiding spots is to look at the language you use to define the variables. If there is a relationship between the language of the two properties, perhaps there is a deeper relationship is waiting to be drawn out as well. Expressing those relationships explicitly can lead to cleaner, more testable, and more reusable code.

A lot of what I do for my clients is code review. Code review is one of the better ways we know of to catch bugs early. I’ve been doing more code review in my day-to-day, and I’ve started to notice patterns arising out of the mire — little things that I see and can flag for deeper attention. One of these little smells is the case of the missing else branch.

Let’s say we’re trying to enable a button when a UITextField has more than 8 characters:

@objc func textChanged(_ sender: UITextField) {
	if (sender.text ?? "").count >= 8 {
		submitButton.isEnabled = true
	}
}

There’s a bug here. UIKit warriors have probably seen this particular bug many times and solved it an equal number of times. But because our programming tools are stuck in the Dark Ages, we can’t see the bug, so let’s spin up a little virtual machine in our brains. We’ll need to keep track of the text of the sender, the user’s keyboard entry, and the enabled state of the submitButton.

What happens when if the user types their 8 characters and then deletes one? The button becomes enabled, but stays enabled when they delete a character.

The bug is hard to spot, but, if the title of the blog post doesn’t give it away, easy to fix.

@objc func textChanged(_ sender: UITextField) {
	if (sender.text ?? "").count >= 8 {
		submitButton.isEnabled = true
	} else {
		submitButton.isEnabled = false
	}
}

Now, when the user types in their 8 characters and deletes one, the submit button is correctly disabled. Leaving out the else branch meant that a path of code wasn’t fully handled. Swift lets us elide the else branch, which it conceals its true nature: the code path was empty.

Let’s look at another example. This time, we do have an else branch:

if let location = venue.location {
	cell.addressLabel?.text = location.address
} else {
	cell.addressLabel?.isHidden = true
}

At first glance, the code seems sensible. If there’s no address, hide the addressLabel. That probably causes some side effect in layout, maybe moving some neighboring views around.

But similar to the last example, there’s a bug. Let’s spin up another virtual machine to model all this state. This particular code has an issue on reuse. What happens if the cell is used for a venue without an address, then used for a venue with an address?

The addressLabel is hidden and never unhidden.

Like the last snippet, we could solve this by adding another line of code, this time to our if branch rather than our else branch. However, I think the code is served better by assigning the isHidden property to a computed boolean, instead of manually branching on that boolean with an if/else. Here’s what that looks like:

if let location = venue.location {
	cell.addressLabel?.text = location.address
}
cell.addressLabel?.isHidden = venue.location == nil

We can even take this a step further and remove the branching entirely, since text accepts an optional String:

cell.addressLabel?.text = venue.location?.address
cell.addressLabel?.isHidden = venue.location == nil

Much simpler, with zero branching.

It should be said that the first snippet can be written in this terse style as well. This is how I prefer to write it:

@objc func textChanged(_ sender: UITextField) {
	submitButton.isEnabled = (sender.text ?? "").count >= 8
}

What’s interesting about this class of bug is that some languages simply don’t let you write code like this. For example, Haskell has an if..then..else construct, and the else branch is required. This Haskell won’t compile without the last line:

if a
  then b
  else c

Haskell’s if..then..else is an expression, so it has a result (either b or c in this case) and that result has a type. Without an else branch, what would that result evaluate to? It’s an impossible question to answer, so Haskell makes it invalid at a code level as well. (A functional way to think about this: side effects aren’t allowed in Haskell. In the same way a Void-returning function must perform a side effect (or do nothing), an if with no else must also perform a side effect.)

You can approximate this behavior in Swift by returning something — you have to include an else branch. For example, this code won’t compile. How could it?

func addressLength() -> Int {
	if let address = self.address {
		return address.count
	}
} // Missing return in a function expected to return 'Int'

If you think about the myriad ways Swift gives you to handle branching — stuff like guard, assigning a boolean, ternaries, and of course, our friendly neighborhood if statement — the if statement is the only that lets the user leave out one of the branches. Even switch requires you to either exhaustively handle all cases or include a default case. From that perspective, leaving the else out is almost syntactic sugar. In some ways, it’s comparable to using a exclamation point to force unwrap. You can do it, but you’re leaving code paths unwritten.

Writing an if with no else isn’t wrong per se, it’s just a smell. When you see it, give it a second pass and really make sure that if it were there, the else branch would actually have no code in it.

There’s quite a bit of conversation on Swift Evolution about the potential future of Sequence and Collection hierarchy. There’s a number of problems that the community is trying to solve and a variety of approaches that have been presented to solve them. Several of these approaches include the ability to create infinite collections, and every time anyone brings this up, someone invariably asks how they would work. Nothing in the type system prevents us from making an infinite collection — it’s purely a semantic constraint — meaning that while we can write infinite collections in Swift today, we’re not supposed to. It violates the assumptions that other people’s code will make about our object. In this post, I’ll take an infinite sequence and demonstrate how we could turn it into an infinite collection.

The Fibonacci numbers are a great example of an infinite sequence. For a quick refresher, each element in that sequence is the sum of the previous two numbers.

Swift has pretty good facility for defining new sequences quickly. Two useful functions are sequence(state:next:) and sequence(first:next). Here, we’ll use the state version:

let fib = sequence(state: (0, 1), next: { state -> Int? in
    let next = state.0 + state.1
    state = (state.1, next)
    return next
})

Calling fib.prefix(10) will give you the first 10 Fibonacci numbers.

Note that this is an infinite sequence! If you try to map over this sequence (which the type system fully allows!), your program will just spin infinitely until it runs out of integers or the heat death of the universe, whichever comes first.

To convert this into an infinite collection, we need to think about a few things. First, how will we represent an index to a value? For an array, this is a number that probably represents a memory offset. For a string, this might represents a byte offset that that character starts at. It needs to be some value that lets us retrieve the value at that index at constant time, or O(1).

One of the interesting things about iterators is that their current state represents the data that you need to get to the next value in constant time. So any deterministic sequence can be represented as a collection, by using its iterator’s state as an index. Our state before is (Int, Int), so we can start off by using that type for our Index. These are the four methods we need to define a Collection:

struct FibonacciCollection: Collection {

	typealias Index = (Int, Int)
	
	var startIndex: Index {
		return (0, 1)
	}
	
	func index(after previous: Index) -> Index {
		return (previous.1, previous.0 + previous.1)
	}
	
	var endIndex: Index {
		fatalError("This collection has no endIndex, because it is infinite")
	}
	
	subscript(index: Index) -> Int {
		return index.0 + index.1
	}
}

We can use (Int, Int) (our state from the fibonacci numbers when they were a sequence) as the index, and use (0, 1) as our starting value (just like our sequence).

But there are a few problems with this approach. To iterate over an arbitrary collection, you can imagine constructing a big while loop:

var index = collection.startIndex
while index < endIndex {
	let value = collection[index]
	// use `value` somehow
	index = collection.index(after: index)
}

(This isn’t how we’d use our collection, since we know it’s infinite, but this is how normal collections work.) Two things stand out. First, we need the Index type to be Comparable — so we can’t use a tuple — and we need endIndex to be defined so that we can check against it — so we can’t fatalError (ding!).

So we need a new index type: something that’s Comparable and something that’s unreachable. The unreachable value should compute to being “greater” than all the reachable values (since it goes at the “end” of the collection). Our first attack is to model this as a struct of two integers, to solve the comparability problem:

struct FibIndex {
	let first: Int
	let second: Int
}

extension FibIndex: Comparable {
	static func == (lhs: FibIndex, rhs: FibIndex) -> Bool {
		return lhs.first == rhs.first && lhs.second == rhs.second
	}
	
	static func < (lhs: FibIndex, rhs: FibIndex) -> Bool {
		return lhs.first < rhs.first
	}
}

This solves the comparability problem, but not the unreachability problem. We need a way to represent one more value, a value that’s separate from all the others. Let’s start over, but with an enum this time:

enum FibIndex {
	case reachable(Int, Int)
	case unreachable
}

This could solve both of our problems. Unfortunately, it makes writing == and < pretty messy:

extension FibIndex: Comparable {
	static func == (lhs: FibIndex, rhs: FibIndex) -> Bool {
		switch (lhs, rhs) {
		case (.unreachable, .unreachable):
			return true
		case let (.reachable(l1, l2), .reachable(r1, r2)):
			return l1 == r1 && l2 == r2
		case (.reachable, .unreachable):
			return false
		case (.unreachable, .reachable):
			return false
		}
	}
	
	static func < (lhs: FibIndex, rhs: FibIndex) -> Bool {
		switch (lhs, rhs) {
		case (.unreachable, .unreachable):
			return false
		case let (.reachable(l1, l2), .reachable(r1, r2)):
			return l1 < r1
		case (.reachable, .unreachable):
			return true
		case (.unreachable, .reachable):
			return false
		}
	}
}

(There are some ways to clean this up with better pattern matching, but I’m going with the explicitness of the full patterns here.)

Let’s add some helpers:

extension FibIndex {
	var sum: Int {
		switch self {
		case .unreachable:
			fatalError("Can't get the sum at an unreachable index")
		case let .reachable(first, second): 
			return first + second
		}
	}
	
	var next: FibIndex {
		switch self {
		case .unreachable:
			fatalError("Can't get the next value of an unreachable index")
		case let .reachable(first, second): 
			return .reachable(second, first + second)
		}
	}
}

And now we can complete our FibonacciCollection:

struct FibonacciCollection: Collection {

	typealias Index = FibIndex
	
	var startIndex: Index {
		return .reachable(0, 1)
	}
	
	func index(after previous: Index) -> Index {
		return previous.next
	}
	
	var endIndex: Index {
		return .unreachable
	}
	
	subscript(index: Index) -> Int {
		return index.sum
	}
}

This is pretty good! We get all of the methods from the Sequence and Collection protocols for free. Unfortunately, this is still an infinite collection, and just like the infinite sequence, we can’t map over it, or we’ll risk looping forever. There are new things on the Collection protocol that we also can’t do — like get the count of this collection. That will also spin forever.

There is one more tweak I’d like to show here, which is extracting the Fibonacci-specific parts of this and making a generic InfiniteCollectionIndex. To do this, we’d keep our basic enum’s structure, but instead of the .reachable case having type (Int, Int), we’d need to put a generic placeholder there. How would that look?

Let’s call the inner index type WrappedIndex. We need to make sure that the wrapped Index is comparable:

enum InfiniteCollectionIndex<WrappedIndex: Comparable>: Comparable {
	case reachable(WrappedIndex)
	case unreachable
}

The Equatable and Comparable implementation stay mostly the same, but instead of comparing integers, they just forward to WrappedIndex:

extension InfiniteCollectionIndex: Comparable {
	static func == (lhs: InfiniteCollectionIndex, rhs: InfiniteCollectionIndex) -> Bool {
		switch (lhs, rhs) {
		case (.unreachable, .unreachable):
		    return true
		case let (.reachable(left), .reachable(right)):
		    return left == right
		case (.reachable, .unreachable):
		    return false
		case (.unreachable, .reachable):
		    return false
		}
	}
	
	static func < (lhs: InfiniteCollectionIndex, rhs: InfiniteCollectionIndex) -> Bool {
		switch (lhs, rhs) {
		case (.unreachable, .unreachable):
			return false
		case let (.reachable(left), .reachable(right)):
			return left < right
		case (.reachable, .unreachable):
			return true
		case (.unreachable, .reachable):
			return false
		}
	}
}

And one more helper, because there will be a lot of situations where we want to assume that that the .unreachable value is, well, unreachable:

extension InfiniteCollectionIndex {
	func assumingReachable<T>(_ block: (WrappedIndex) -> T) -> T {
		switch self {
		case .unreachable:
			fatalError("You can't operate on an unreachable index")
		case let .reachable(wrapped):
			return block(wrapped)
		}
	}
	
	func makeNextReachableIndex(_ block: (WrappedIndex) -> WrappedIndex) -> InfiniteCollectionIndex {
		return .reachable(assumingReachable(block))
	}
}

This function takes a block that assumes that the value is .reachable, and returns whatever that block returns. If the value is .unreachable, it crashes.

We can now use the struct form of FibIndex from above:

struct FibIndex {
	let first: Int
	let second: Int
}

extension FibIndex: Comparable {
	static func == (lhs: FibIndex, rhs: FibIndex) -> Bool {
		return lhs.first == rhs.first && lhs.second == rhs.second
	}
	
	static func < (lhs: FibIndex, rhs: FibIndex) -> Bool {
		return lhs.first < rhs.first
	}
}

I won’t go into too much of the details here, but this allows us to define simple Comparable index types, and make them into infinite indexes easily:

struct FibonacciCollection: Collection {

	typealias Index = InfiniteCollectionIndex<FibIndex>
	
	var startIndex: Index {
		return .reachable(FibIndex(first: 0, second: 1))
	}
	
	func index(after previous: Index) -> Index {
		return previous.makeNextReachableIndex({
			FibIndex(first: $0.second, second: $0.first + $0.second)
		})
	}
	
	var endIndex: Index {
		return .unreachable
	}
	
	subscript(index: Index) -> Int {
		return index.assumingReachable({ $0.first + $0.second })
	}
}

It’s not clear which way the tides will ultimately shift with Swift’s Collection model, but if and when infinite collections become legal in Swift, this technique will help you define them easily.

Last year I wrote a post about how adding simple optional properties to your classes is the easy thing to do when you want to extend functionality, but can actually subtly harm your codebase in the long run. This post is the spiritual successor to that one.

Let’s say you’re designing the auth flow in your app. You know this flow isn’t going to be simple or linear, so you want to make some very testable code. Your approach to this is to first think through all the screens in that flow and put them in an enum:

enum AuthFlowStep {
    case collectUsernameAndPassword
    case findFriends
    case uploadAvatar
}

Then you put all your complicated logic into a single function that takes a the current step and the current state, and spits out the next step of the flow:

func stepAfter(_ currentStep: AuthFlowStep, context: UserState) -> AuthFlowStep

This should be very easy to test. So far, so good.

Except — you’re working through the logic, and you realize that sometimes you won’t always be able to return a AuthFlowStep. Once the user has submitted all the data they need to fully auth, you need something that will signal that the flow is over. You’re working right there in the function, and you want to want to return a special case of the thing that you already have. What do you do? You change the return type to an optional:

func stepAfter(_ currentStep: AuthFlowStep, context: UserState) -> AuthFlowStep?

This solution works. You go to your coordinator and call this function, and start working with it:

func finished(flowStep: AuthFlowStep, state: UserState, from vc: SomeViewController) {
	let nextState = stepAfter(flowStep, context: state)

When we get nextState, it’s optional, so the default move here is to guard it to a non-optional value.

	guard let nextState = stepAfter(flowStep, context: state) else {
		self.parentCoordinator.authFlowFinished(on: self)
	}
	switch nextState {
	case .collectUsernameAndPassword:
		//build and present next view controller

This feels a bit weird, but I remember Olivier’s guide on pattern matching in Swift, and I remember that I can switch on the optional and my enum at the same time:

func finished(flowStep: AuthFlowStep, state: UserState, from viewController: SomeViewController) {
	let nextState = stepAfter(flowStep, context: state) // Optional<AuthFlowStep>
	switch nextState {
	case nil:
		self.parentCoordinator.authFlowFinished(on: self)
	case .collectUsernameAndPassword?:
		//build and present next view controller

That little question mark lets me match an optional case of an enum. It makes for better code, but something still isn’t sitting right. If I’m doing one big switch, why am I trying to unwrap a nested thing? What does nil mean in this context again?

If you paid attention to the title of the post, perhaps you’ve already figured out where this is going. Let’s look at the definition of Optional. Under the hood, it’s just an enum, like AuthFlowState:

enum Optional<Wrapped> {
	case some(Wrapped)
	case none
}

When you slot an enum into the Optional type, you’re essentially just adding one more case to the Wrapped enum. But we have total control over our AuthFlowStep enum! We can change it and add our new case directly to it.

enum AuthFlowStep {
    case collectUsernameAndPassword
    case findFriends
    case uploadAvatar
    case finished
}

We can now remove the ? from our function’s signature:

func stepAfter(_ currentStep: AuthFlowStep, context: UserState) -> AuthFlowStep

And our switch statement now switches directly over all the cases, with no special handling for the nil cases.

Why is this better? A few reasons:

First, what was once nil is now named. Before, users of this function might not know exactly what it means when the function returns nil. They either have to resort to reading documentation, or worse, reading the code of the function, to understand when nil might be returned.

Second, simplicity is king. No need to have a guard then a switch, or a switch that digs through two layers of enums. One layer of thing, always easy to handle.

Lastly, precision. Having return nil available as a bail-out at any point in a function can be a crutch. The next developer might find themselves in an exceptional situation where they’d like to jump out of the function, and so they drop a return nil Except now, nil has two meanings, and you’re not handling one of them correctly.

When you add your own special cases to enums, it’s also worth thinking about the name you’ll use. There are lots of names available, any of which might make sense in your context: .unknown, .none, .finished, .initial, .notFound, .default, .nothing, .unspecified, and so on. (One other thing to note is that if you have a .none case, and you do happen to make that value optional, then whether it will use Optional.none or YourEnum.none is ambiguous.)

I’m using flow states as a general example here, but I think the pattern can be expanded to fit other situations as well — anytime you have an enum and want to wrap it in an optional, it’s worth thinking if there’s another enum case hiding there, begging to be drawn out.

Thanks to Bryan Irace for feedback and the example for this post.

In Apple’s documentation, they suggest you use a pattern called MVC to structure your apps. However, the pattern they describe isn’t true MVC in the original sense of the term. I’ve touched on this point here before, but MVC was a design pattern created for Smalltalk. In Smalltalk’s formulation, each of the 3 components, model, view, and controller, each talked directly to each other. This means that either the view knows how to apply a model to itself, or the model knows how to apply itself to a view.

When we write iOS apps, we consider models and views that talk directly to each other as an anti-pattern. What we call MVC is more accurately described as model-view-adapter. Our “view controllers” (the “adapters”) sit in between the model and view and mediate their interactions. In general, I think this is a good modification to MVC — the model and view not being directly coupled together and instead connected via an intermediary seems like a positive step. However, I will caveat this by saying that I haven’t worked with many systems that don’t maintain this separation.

So, that’s why we have view controllers in iOS. They serve to glue the model and view together. Now, there are downstream problems with this style of coding: code that doesn’t obviously belong in models or views ends up in the view controller, and you end up with gigantic view controllers. I’ve discussed that particular problem on this blog many times, but it’s not exactly what I want to talk about today.


I’ve heard whispers through the grapevine of what’s going on under the hood with UIViewController. I think the longer you’ve been working with UIKit, the more obvious this is, but the UIViewController base class is not pretty. I’ve heard that, in terms of lines of code, it’s on the higher end of 10,000 to 20,000 lines (and this was a few years ago, so they’ve maybe broken past the 20 kloc mark at this point).

When you want the benefits of an object to glue a UIView and a model object (or collection thereof) together, typically, we use view controller containment to break the view controller up into smaller pieces, and compose them back together.

However, containment can be finicky. It subtly breaks things if you don’t do it right, with no indication of how to fix any issues. Then, when you finally do see your bug, which was probably a misordering of calls to didMove or willMove or whatever, everything magically starts working. In fact, the very presence of willMove and didMove suggest that containment has some invisible internal state that needs to be cleaned up.

I’ve seen this firsthand in two particular situations. First, I’ve seen this issue pop up with putting view controllers in cells. When I first did this, I had a bug in the app where some content in the table view would randomly disappear. This bug went on for months, until I realized I misunderstood the lifecycle of table view cells, and I wasn’t correctly respecting containment. Once I added the correct -addChildViewController calls, everything started working great.

To me, this showed a big thing: a view controller’s view isn’t just a dumb view. It knows that it’s not just a regular view, but that it’s a view controller’s view, and its qualities change in order to accommodate that. In retrospect, it should have been obvious. How does UIViewController know when to call -viewDidLayoutSubviews? The view must be telling it, which means the view has some knowledge of the view controller.

The second case where I’ve more recently run into this is trying to use a view controller’s view as a text field’s inputAccessoryView. Getting this behavior to play nicely with the behavior from messaging apps (like iMessage) of having the textField stick to the bottom was very frustrating. I spent over a day trying to get this to work, with minimal success to show for it. I ended up reverting to a plain view.

I think at a point like that, when you’ve spent over a day wrestling with UIKit, it’s time to ask: is it really worth it to subclass from UIViewController here? Do you really need 20,000 lines of dead weight to to make an object that binds a view and a model? Do you really need viewWillAppear and rotation callbacks that badly?


So, what does UIViewController do that we always want?

  • Hold a view.
  • Bind a model to a view.

What does it do that we usually don’t care about?

  • Provide storage for child view controllers.
  • Forward appearance (-viewWillAppear:, etc) and transition coordination to children.
  • Can be presented in container view controllers like UINavigationController.
  • Notify on low memory.
  • Handle status bars.
  • Preserve and restore state.

So, with this knowledge, we now know what to build in order to replace view controllers for the strange edge cases where we don’t necessarily want all their baggage. I like this pattern because it tickles my “just build it yourself” bone and solves real problems quickly, at the exact same time.

There is one open question, which is what to name it. I don’t think it should be named a view controller, because it might be easy to confuse for a UIViewController subclass. We could just call it a regular Controller? I don’t hate this solution (despite any writings in the past) because it serves this same purpose a controller in iOS’s MVC (bind a view and model together), but there are other options as well: Binder, Binding, Pair, Mediator, Concierge.

The other nice thing about this pattern is how easy it is to build.

class DestinationTextFieldController {

    var destination: Destination?

    weak var delegate: DestinationTextFieldControllerDelegate?

    let textField = UITextField().configure({
        $0.autocorrectionType = .no
        $0.clearButtonMode = .always
    })
    
}

It almost seems like heresy to create an object like this and not subclass UIViewController, but when UIViewController isn’t pulling its weight, it’s gotta go.

You already know how to add functionality to your new object. In this case, the controller ends up being the delegate of the textField, emitting events (and domain metadata) when the text changes, and providing hooks into updating its view (the textField in this case).

extension DestinationTextFieldController {
	var isActive: Bool {
		return self.textField.isFirstResponder
	}

	func update(with destination: Destination) {
		self.destination = destination
		configureView()
	}
	
	private func configureView() {
		textField.text = destination.descriptionForDisplay
	}
}

There are a few new things you’re responsible with this new type of controller:

  • you have to make an instance variable to store it
  • you’re responsible for triggering events on it — because it’s not a real view controller, there’s no more -viewDidAppear:
  • you’re not in UIKit anymore, so you can’t directly rely on things like trait collections or safe area insets or the responder chain — you have to pass those things to your controller explicitly

Using this new object isn’t too hard, even thought you do have to explicitly store it so it doesn’t deallocate:

class MyViewController: UIViewController, DestinationTextFieldControllerDelegate {


	let destinationViewController = DestinationTextFieldController()
	
	override func viewDidLoad() {
		super.viewDidLoad()
		destinationViewController.delegate = self
		view.addSubview(destinationViewController.view)
	}
	
	//handle any delegate methods

}

Even if you use this pattern, most of your view controllers will still be view controllers and subclass from UIViewController. However, in those special cases where integrating a view controller causes you hours and hours of pain, this can be a perfect way to simply opt out of the torment that UIKit brings to your life daily.

If you want some extreme bikeshedding on a very simple topic, this is the post for you.

For the folks who have been at any of the recent conferences I’ve presented at, you’ve probably seen my talk, You Deserve Nice Things. The talk is about Apple’s reticence to provide conveniences for its various libraries. It draws a lot on an old post of mine, Categorical, as well as bringing in a lot of new Swift stuff.

One part of the standard library that’s eminently extendable is Sequence and friends. Because of the number of different operations we want to perform on these components, even the large amount of affordances that the standard library does provide (standard stuff like map, filter, as well as more abstruse stuff like partition(by:) and lexicographicallyPrecedes), it still doesn’t cover the breadth of operations that are useful in our day to day programming life.

In the talk, I propose a few extensions that I think are useful, including any, all, none, and count(where:), eachPair, chunking, and a few others. None of these ideas are original to me. They’re ideas lifted wholesale from other languages, primary Ruby and its Enumerable module. Enumerable is a useful case study because anything that’s even marginally useful gets added to this module, and Ruby developers reap the benefits.

Swift’s standard library is a bit more conservative, but its ability to extend types and specifically protocols makes the point mostly moot. You can bring your own methods as needed. (In Categorical, I make the case that this is the responsibility of the vendor, but until they’re willing to step up, we’re on our own.)


I have an app where I need to break up a gallery of images in groups based on date. The groups could be based on individual days, but we thought grouping into “sessions” would be better. Each session is defined by starting more than an hour after the last session ended. More simply, if there’s a gap between two photos of more than hour, that should signal the start of a new session.

Since we’re splitting a Sequence, the first thought is to use something built in: there’s a function called split, which takes a bunch of parameters (maxSplits, omittingEmptySubsequences and a block called isSeparator to determine if an element defines a split). However, we can already see from the type signature that this function isn’t quite going to do what we want. The isSeparator function yields only one element, which makes it hard to tell if there should be a split between two consecutive elements, which is what we’re actually trying to do. In point of fact, this function is consumes the separators, because it’s a more generic version of the String function split, which is useful in its own right.

No, we need something different.


In her post, Erica Sadun has some answers for us: she’s got a function that works sort of like what we want. In this case, the block takes the current element and the current partition, and you can determine if the current element fits in the current partition.

extension Sequence {
    public func partitioned(at predicate: (_ element: Iterator.Element, _ currentPartition: [Iterator.Element]) -> Bool ) -> [[Iterator.Element]] {
        var current: [Iterator.Element] = []
        var results: [[Iterator.Element]] = []
        for element in self {
            guard !current.isEmpty else { current = [element]; continue }
            switch predicate(element, current) {
            case true: results.append(current); current = [element]
            case false: current.append(element)
            }
        }
        guard !current.isEmpty else { return results }
        results.append(current)
        return results
    }
}

I’ve got a few small gripes with this function as implemented:

The name. Partitioning in the standard library currently refers to changing the order of a MutableCollection and returning a pivot where the collection switches from one partition to another. I wouldn’t mind calling it something with split in the name, but as mentioned before, that usually consumes the elements. I think calling this slicing is the best thing to do. Slicing is also a concept that already exists in the standard library (taking a small part of an existing Collection) but in a lot of ways, that’s actually what we’re doing in this case. We’re just generating more than one slice.

The name again. Specifically, the at in partition(at:) doesn’t seem exactly right. Since we’re not consuming elements anymore, the new partition has to happen either before the given element, or after it. The function’s name doesn’t tell us which. If we change the signature of the function to return a consecutive pair of elements, we can change its name to slice(between:).

This has the added benefit of no longer requiring a force unwrap in usage. Erica’s whole problem with this code is that passing back a collection that is known to be non-empty (*COUGH*), means that she has to force unwrap access to the last element:

testArray.partitioned(at: { $0 != $1.last! })

If we change the function to slice(between:), we can simplify this way down, to:

testArray.slice(between: !=)

Way nicer.

Now that we’ve beaten the name into the ground, let’s move onto discussion about the implementation. Specifically, there is some duplication in the code that I find problematic. Two expressions in particular:

First,

current = [element]

Second,

results.append(current)

This code may not look like much — only a few characters, you protest! — but it represents a duplication in concept. If these expressions needed to expand to do more, they’d have to be expanded in two places. This was excruciatingly highlighted when porting this code over to my gallery app (which is Objective-C) I wanted to wrap the image collections in a class called a PhotoSection. Creating the PhotoSection in two places made it painfully obvious that this algorithm duplicates code.

This code is ugly and frustrating: the important part of the code, the actual logic of what’s happening is tucked away in the middle there.

[photosForCurrentSection.lastObject.date timeIntervalSinceDate:photo.date] > 60*60

The entire rest of the code could be abstracted away. Part of this is Objective-C’s fault, but this version of the code really does highlight the duplication that happens when modifying the code that creates a new section.


The last piece of the puzzle here is how Ruby’s Enumerable comes into play. When exploring that module, you can see three functions that look like they could be related: slice_when, slice_before, and slice_after. What is the relationship between these functions?

It seems obvious now that I know, but I did have to do some searching around for blog posts to explain it. Essentially, slice_when is like our slice(between:). It gives you two elements and you tell it if there should be a division there. slice(before:) and slice(after:) each yield only one element in their block, and slice before or after that element. This clears up the confusion with Erica’s original function — we now know if it’ll slice before or after our element, based on the name of the function.


As for implementation, you could use a for loop and the slight duplication of Erica’s code, but I’ve recently been trying to express more code in terms of chains of functions that express a whole operation that happens to the collection all at once. I find this kind of code more elegant, easier to read, and less prone to error, even though it does pass over the relevant collection multiple times.

To write our slice(between:) function in that style, we first need two helpers:

extension Collection {
	func eachPair() -> Zip2Sequence<Self, Self.SubSequence> {
		return zip(self, self.dropFirst())
	}

	func indexed() -> [(index: Index, element: Element)] {
		return zip(indices, self).map({ (index: $0, element: $1) })
	}
}

I’m a big fan of composing these operations together, from smaller, simpler concepts into bigger, more complex ones. There are slightly more performant ways to write both of those functions, but these simple implementations will do for now.

extension Collection {
	func slice(between predicate: (Element, Element) -> Bool) -> [SubSequence] {
		let innerSlicingPoints = self
			.indexed()
			.eachPair()
			.map({ (indexAfter: $0.1.index, shouldSlice: predicate($0.0.element, $0.1.element)) })
			.filter({ $0.shouldSlice })
			.map({ $0.indexAfter })

		let slicingPoints = [self.startIndex] + innerSlicingPoints + [self.endIndex]

		return slicingPoints
			.eachPair()
			.map({ self[$0..<$1] })
	}
}

This function is broken up into 3 main sections:

  1. Find the indexes after any point where the caller wants to divide the sequence.
  2. Add the startIndex and the endIndex.
  3. Create slices of for each consecutive pair of those indexes.

Again, this isn’t the most performant implementation. Namely, it does quite a few iterations, and requires Collection where Erica’s solution required just a Sequence. But I do think it’s easier to read and understand. As I discussed in the post about refactoring, distilling an algorithm into forms straightforward, simple forms, operating at the highest possible level of abstraction, enables you to see the structure of our algorithm and potential transforms that it can undergo to create other algorithms.

Erica’s original example is a lot simpler now:

let groups = [1, 1, 2, 3, 3, 2, 3, 3, 4].slice(between: !=)

To close this post out, the implementations for slice(before:) and slice(after:) practically fall out of the ether, now that we have slice(between:):

extension Collection {
	func slice(before predicate: (Element) -> Bool) -> [SubSequence] {
		return self.slice(between: { left, right in
			return predicate(right)
		})
	}

	func slice(after predicate: (Element) -> Bool) -> [SubSequence] {
		return self.slice(between: { left, right in
			return predicate(left)
		})
	}
}

This enables weird things to become easy, like splitting a CamelCased type name:

let components = "GalleryDataSource"
	.slice(before: { ("A"..."Z").contains($0) })
	.map({ String($0) })

(Don’t try it with type name with a initialism in it, like URLSession.)