All posts by Drew McCormack

About Drew McCormack

Decentral data systems enthusiast. Co-founder of agenda.com and founder of ensembles.io

The Danger of Playing it Safe

It’s an old chestnut that Swift developers love to sink their teeth into: Should you force unwrap optionals? Everyone has an opinion about it, and I’m going to state mine as clearly as I can — forcefully unwrap early and often.

Of course, this is just one opinion. We even disagree about it within our two man Agenda team, so there is probably not much hope for the world. But I want to explain when and why I think it is good to force unwrap, and give a recent real world example that demonstrates the cost of not doing it.

First, my reasoning. I think you should force unwrap in any situation where logic tells you that an optional simply cannot be nil. A standard example might look like this.

var count: Int?
count = 0
print("\(count!)")

Could count end up being nil in this case? Perhaps, through some strange memory corruption or solar flare. Do I want my app to continue to run if count is nil? No. To put it bluntly, that is cancer. The app would be in an undefined state, which may well be dangerous. I don’t want it deleting user data or causing any other havoc — it should just crash. I will be informed of the problem, and it can’t do any more damage.

But what is wrong with the softly, softly approach? Shouldn’t we be defensive here? Here is how you could do it.

var count: Int?
count = 0
if let count = count {
    print("\(count)")
} else {
    print("error!")
}

There are several problems with this. Firstly, it is more verbose, making it more difficult to read. Secondly, and even more importantly, it disguises developer intentions. It says to the next developer “count could conceivably be nil, so we will check for it”, even though it was clear to the original developer that it should never be nil in any well-defined circumstance. Lastly, where is the app at after this code runs? Who knows? The state is completely unclear.

So be assertive with forced unwrapping. If there is no case where the optional should ever be nil, force unwrap. But don’t force unwrap in cases where there is a valid situation in which nil could arise. If a foreseen error could lead to nil, that requires explicit handling.

I mentioned that I wanted to finish off with a recent real-world example. When Apple announced iOS 14 would ship, they only gave about a day’s notice, leaving most of us scrambling to get ready. For Agenda, we had done a lot of work on widgets, but we had never had them in a beta, or extensively tested on the device. That was planned for the week or so that we usually have following release of the Xcode GM, but before the new iOS is available. Alas, in 2020, that was a luxury we didn’t have.

So I merged our branches in Git, and uploaded the binary. Downloaded from TestFlight, and — you guessed it — the widgets were broken. It was just showing a placeholder, which I later learned is what you get when a widget crashes.

I dug into the code, and I found that the problem was an incorrect file path. I had been testing with a special development target, and hadn’t properly tested the production target. The faulty code was as follows:

let identifierSuffix = (Bundle.main.object(forInfoDictionaryKey: "AgendaIdentifierSuffix") as? String) ?? ".development"

It is attempting to get a string from the Info.plist, which it will then use in the aforementioned path, but I had forgotten to put the string in the Info.plist. That wasn’t the real crime though: As you can see, in the case of nil being returned, it tries to play it safe by falling back on the development target’s string.

This was bad. It meant the production app had the wrong path, so it crashed, but I didn’t see the crash until very late in the development cycle, even though it was there the whole time. And the cost? I probably wasted an hour or two uploading the binary, then sluthing the problem. “What’s an hour or two?” I hear you ask. Well, Apple were pushing us to submit our new widget feature so that Agenda could be considered for featuring. I don’t think two hours was enough to jeopardize that, but you never know. I’m sure the App Store is a madhouse on release day.

Here is how I think the code should have been written.

let identifierSuffix = (Bundle.main.object(forInfoDictionaryKey: "AgendaIdentifierSuffix") as? String)!

It is simpler, clearly stating that I am assuming the entry is in the Info.plist, and the widget only works if that assumption is fulfilled. If there is no entry in there, the widget is entirely useless, and should crash before causing more damage. And, with this code, it will crash early in development. I would have discovered the issue as soon as I tried to run a debug version, and fixed it long before it hit the App Store.

(Update: It has been pointed out that the last line of code is a bit convoluted. It would read better as

let identifierSuffix = Bundle.main.object(forInfoDictionaryKey: "AgendaIdentifierSuffix") as! String

That’s very true. I wanted to change the original code as little as possible, to stay on message. The point is the same: defensive coding did more damage than good, and an assertive force-unwrap would have been better.)

Replicants All the Way Down

In the previous installment of this ongoing series on Conflict-Free Replicated Data Types (CRDTs) in Swift, I introduced you to tombstones and Lamport counts, in constructing a replicating set. This time we’ll take a similar approach for a more common data type: the dictionary or map.

The code for our ReplicatingDictionary will be quite similar to what we used in the ReplicatingSet, so I won’t focus too much on those repetitious aspects. Instead, we will look in detail at a new trick the dictionary type has up its sleeve: the ability to recursively merge whenever the values it contains are also of a replicating type.

This ability to compose new types out of existing replicating types is one of the strengths of the CRDT approach. We’ll see in a few posts from now that you can construct your app’s data model entirely out of replicating types — the whole model becomes one monstrous replicating type, and merging across devices becomes a single function call. Simple — and completely robust — sync.

Introducing the ReplicatingDictionary

As usual, you can find all the code from the series in this GitHub repo. The core of the dictionary type is very similar to the set type from last time.

public struct ReplicatingDictionary<Key, Value> where Key: Hashable {
    
    fileprivate struct ValueContainer {
        var isDeleted: Bool
        var lamportTimestamp: LamportTimestamp
        var value: Value
        
        init(value: Value, lamportTimestamp: LamportTimestamp) {
            self.isDeleted = false
            self.lamportTimestamp = lamportTimestamp
            self.value = value
        }
    }
    
    private var valueContainersByKey: Dictionary<Key, ValueContainer>
    private var currentTimestamp: LamportTimestamp

The data is stored in the valueContainersByKey dictionary, but instead of just storing the values directly, like in a ‘normal’ dictionary, we wrap the values in a struct with some extra metadata. The metadata in question is a Lamport timestamp, and an isDeleted flag, which gives us tombstone functionality.

Just as for the replicating set type, this metadata allows values modified on different peers to be merged in a deterministic way, so that each peer ends up with the same set of key-value pairs. The mechanics of the dictionary type are almost identical to the set type; the main difference is that the set is just storing values, and the dictionary is storing values and keys. Whereas last time the entries in the set were used as the keys of the storage dictionary, this time we have a dedicated key for that, and the values get boxed with the metadata.

The rest of the type is fairly straightforward. The main challenge is taking into account the tombstones. For example, here is the set block of the subscript func.

        set(newValue) {
            currentTimestamp.tick()
            if let newValue = newValue {
                let container = ValueContainer(value: newValue, lamportTimestamp: currentTimestamp)
                valueContainersByKey[key] = container
            } else if let oldContainer = valueContainersByKey[key] {
                var newContainer = ValueContainer(value: oldContainer.value, lamportTimestamp: currentTimestamp)
                newContainer.isDeleted = true
                valueContainersByKey[key] = newContainer
            }
        }

It begins by incrementing the Lamport timestamp, because the contents of the type are being changed. It then checks if the newValue being set is non-nil; if it is, it creates a new ValueContainer box, with the new timestamp and value, and puts that in the valueContainersByKey storage. If newValue is nil, the function looks to see if there is an old value already stored for the key, because if there is, it needs to be marked deleted. We don’t just remove the entry from valueContainersByKey, we update it with the isDeleted flag set to true.

Recursive Merging

The RecursiveDictionary type has a standard merge method very similar to the one in ReplicatingSet, but it has an extra string to its merging bow: an extra merge method specialized for the case when the value type is also Replicable.

Why would we want this? The standard merge treats values atomically. If two devices update the value for a given key at the same time, later — when they sync up — one of the two values will win. You can never get half of one value, and half of the other — it’s an atomic merge.

But what if it actually would be useful to partially merge the values? Imagine you have written a nice replicating type to store the first name and last name of a contact, and you store values of this type in a ReplicatingDictionary. With the standard merge, if the first name of a contact was edited on one device, and the last name on another device, the eventual result would not be correct. One of the two values would win, and either the first name or the last name would still be wrong. But if the merge func of the values themselves could be called, we could have our replicating name type properly integrate the two edits, and both names would end up correct.

The specialized merged method looks like this.

extension ReplicatingDictionary where Value: Replicable {
   
    public func merged(with other: ReplicatingDictionary) -> ReplicatingDictionary {
        var haveTicked = false
        var resultDictionary = self
        resultDictionary.currentTimestamp = max(self.currentTimestamp, other.currentTimestamp)
        resultDictionary.valueContainersByKey = other.valueContainersByKey.reduce(into: valueContainersByKey) { result, entry in
            let first = result[entry.key]
            let second = entry.value
            if let first = first {
                if !first.isDeleted, !second.isDeleted {
                    // Merge the values
                    if !haveTicked {
                        resultDictionary.currentTimestamp.tick()
                        haveTicked = true
                    }
                    let newValue = first.value.merged(with: second.value)
                    let newValueContainer = ValueContainer(value: newValue, lamportTimestamp: resultDictionary.currentTimestamp)
                    result[entry.key] = newValueContainer
                } else {
                    // At least one deletion, so just revert to atomic merge
                    result[entry.key] = first.lamportTimestamp > second.lamportTimestamp ? first : second
                }
            } else {
                result[entry.key] = second
            }
        }
        return resultDictionary
    }
    
}

The two valueContainersByKey get merged together with a reduce, just like in the other merged functions we have seen, but the details are a bit different. It is very important to take into account the tombstones. If either of the values is deleted, the method just reverts back to the standard merge algorithm, picking the one that is ‘most recent’. If the value exists in both copies of valueContainersByKey, and is not deleted, rather than picking one value or the other, it calls the merged method of the value itself, and stores the result.

                    let newValue = first.value.merged(with: second.value)
                    let newValueContainer = ValueContainer(value: newValue, lamportTimestamp: resultDictionary.currentTimestamp)
                    result[entry.key] = newValueContainer

The rest of the function is just taking care to increase the Lamport timestamp appropriately.

Using Recursive Merge

That’s how the ReplicatingDictionary works, but how do you use it? In particular, how do you use that recursive merging functionality? There’s no better place to find out than in the unit tests.

final class ReplicatingDictionaryTests: XCTestCase {
    
    ...
    
    var dictOfSetsA: ReplicatingDictionary<String, ReplicatingSet<Int>>!
    var dictOfSetsB: ReplicatingDictionary<String, ReplicatingSet<Int>>!

    override func setUp() {
        super.setUp()
        ...
        dictOfSetsA = .init()
        dictOfSetsB = .init()
    }

    ...

    func testNonAtomicMergingOfReplicatingValues() {
        dictOfSetsA["1"] = .init(array: [1,2,3])
        dictOfSetsA["2"] = .init(array: [3,4,5])
        dictOfSetsA["3"] = .init(array: [1])
        
        dictOfSetsB["1"] = .init(array: [1,2,3,4])
        dictOfSetsB["3"] = .init(array: [3,4,5])
        dictOfSetsB["1"] = nil
        dictOfSetsB["3"]!.insert(6)
        
        let dictOfSetC = dictOfSetsA.merged(with: dictOfSetsB)
        let dictOfSetD = dictOfSetsB.merged(with: dictOfSetsA)
        XCTAssertEqual(dictOfSetC["3"]!.values, [1,3,4,5,6])
        XCTAssertNil(dictOfSetC["1"])
        XCTAssertEqual(dictOfSetC["2"]!.values, [3,4,5])
        
        let valuesC = dictOfSetC.dictionary.values.flatMap({ $0.values }).sorted()
        let valuesD = dictOfSetD.dictionary.values.flatMap({ $0.values }).sorted()
        XCTAssertEqual(valuesC, valuesD)
    }

This test sets up two ReplicatingDictionary’s, which contain ReplicatingSet’s as values. We introduced the ReplicatingSet last time; because it also conforms to Replicable, the specialized merged function is used.

Concentrate on the code for the key “3”.

    func testNonAtomicMergingOfReplicatingValues() {
        dictOfSetsA["3"] = .init(array: [1])
        
        ...
        dictOfSetsB["3"] = .init(array: [3,4,5])
        ...
        dictOfSetsB["3"]!.insert(6)
        
        let dictOfSetC = dictOfSetsA.merged(with: dictOfSetsB)
        ...
        XCTAssertEqual(dictOfSetC["3"]!.values, [1,3,4,5,6])

        ...
    }

The set in the first dictionary just contains the value 1. The second dictionary has a set containing 3, 4, and 5, and is updated to also include 6. The two dictionaries get merged to form dictOfSetC, and the test shows that the value for key “3” contains 1, 3, 4, 5 and 6. In other words, it has merged the two sets together, rather than atomically picking the first or the second.

This recursive merging is very powerful, and it doesn’t just work with sets. You can put any replicating data type you like in the dictionary, and it will undergo partial merging. With this tool at our disposal, we can build up complex data models that sync up autonomously.

Next time…

We have one more replicating type to go before we are ready to build our distributed text editing app. Next time we will develop a replicating array — the most complex type we will encounter in this series. It will act as the textual engine of our collaborative editor.

Time for Tombstones

Other Posts in Series

Last time we introduced our first replicating collection, an add-only set. Although useful in some specific circumstances, it isn’t a generally applicable set type, because it can only grow — you can’t remove entries from an add-only set. In this post, we are going to build a more advanced set which is capable of handling removals.

But what you find below is designed to do more than just introduce a new collection type. It also introduces some important concepts and tools you can use for building other replicating types. In particular, we will see how you can handle deleted values, and meet a more robust way to track time.

Introducing the ReplicatingSet

The add-only set was simple, because it was really just a standard set with the removal functions…err…removed. The data storage was exactly the same as a Swift Set, and merging involved nothing more that taking the union of the two sets.

As we touched upon, the add-only set was incapable of handling removal, because it couldn’t distinguish between the case where an entry did exist and was removed, and that the entry was never added in the first place. This meant it was impossible to decide how merging should proceed.

To get around this, we will include some metadata in our type, and store it in a dictionary keyed by the values themselves. Here is what it looks like.

public struct ReplicatingSet<T: Hashable> {
    
    fileprivate struct Metadata {
        var isDeleted: Bool
        var lamportTimestamp: LamportTimestamp
        
        init(lamportTimestamp: LamportTimestamp) {
            self.isDeleted = false
            self.lamportTimestamp = lamportTimestamp
        }
    }

    private var metadataByValue: Dictionary<T, Metadata>
    private var currentTimestamp: LamportTimestamp

The Metadata struct includes a flag isDeleted. If this is set to true, we know that the value once did exist in the set, but has been removed. We call this a tombstone, because it acts as evidence that something did exist, but has since deceased.

Also included in the metadata is a timestamp, but it is no ordinary timestamp. I will discuss that aspect more below, but for now, just think of it is the time of the last change to that particular entry in the set.

Inserting Values

So how does the ReplicatingSet work? The initializers allow you to create an empty set, or one prepopulated by an array of entries.

   public init() {
        self.metadataByValue = .init()
        self.currentTimestamp = .init()
    }
    
    public init(array elements: [T]) {
        self = .init()
        elements.forEach { self.insert($0) }
    }

You can insert entries in an existing ReplicatingSet just like you would the standard Set type

    @discardableResult 
    public mutating func insert(_ value: T) -> Bool {
        currentTimestamp.tick()
        
        let metadata = Metadata(lamportTimestamp: currentTimestamp)
        let isNewInsert: Bool
        
        if let oldMetadata = metadataByValue[value] {
            isNewInsert = oldMetadata.isDeleted
        } else {
            isNewInsert = true
        }
        metadataByValue[value] = metadata
        
        return isNewInsert
    }

This function begins with a call to the tick function on the current timestamp; think of this as simply incrementing the time. We need to do this whenever something changes.

New metadata is then created with this timestamp, and that metadata is set in the metadataByValue dictionary. There is a little more code there to check if there was already a value in the dictionary, but that is purely needed so that we can return if the value was new or not.

Handling Removal with Tombstones

You can also remove entries.

    @discardableResult 
    public mutating func remove(_ value: T) -> T? {
        let returnValue: T?
    
        if let oldMetadata = 
            metadataByValue[value], !oldMetadata.isDeleted {
            currentTimestamp.tick()
            var metadata = 
                Metadata(lamportTimestamp: currentTimestamp)
            metadata.isDeleted = true
            metadataByValue[value] = metadata
            returnValue = value
        } else {
            returnValue = nil
        }
        
        return returnValue
    }

Removing doesn’t actually remove anything from the metadataByValue dictionary, it just changes the metadata so that it becomes a tombstone. Again, the timestamp is updated first, and new metadata is created with the isDeleted flag set to true. The result is stored in the dictionary.

Accessing Values

The rest of the struct is straightforward. Each function has to be careful to account for tombstones. For example, to get all the current values, we have to filter them out.

    public var values: Set<T> {
        let values = metadataByValue
             .filter({ !$1.isDeleted })
             .map({ $0.key })
        return Set(values)
    }

The same is true when checking if a particular value is in the set. It is not enough to just check if the key exists in the dictionary; the isDeleted property of the metadata also needs to be taken into account.

    public func contains(_ value: T) -> Bool {
        !(metadataByValue[value]?.isDeleted ?? true)
    }

Merging

As you know by now, replicating types are types where a value can be modified independently on different devices, and merged back together in a deterministic way. The ReplicatingSet is no different, and the algorithm used is much the same as that of the ReplicatingRegister. For each entry, the value with the latest time wins.

extension ReplicatingSet: Replicable {
    
    public func merged(with other: ReplicatingSet) -> ReplicatingSet {
        var result = self
        result.metadataByValue = other.metadataByValue.reduce(into: metadataByValue) { result, entry in
            let firstMetadata = result[entry.key]
            let secondMetadata = entry.value
            if let firstMetadata = firstMetadata {
                result[entry.key] = 
                    firstMetadata.lamportTimestamp > secondMetadata.lamportTimestamp ? firstMetadata : secondMetadata
            } else {
                result[entry.key] = secondMetadata
            }
        }
        result.currentTimestamp = Swift.max(self.currentTimestamp, other.currentTimestamp)
        return result
    }
    
}

Note also that the currentTimestamp is also set to the largest of the two values before the merge. It is important that the timestamp keep increasing; if it were to decrease, we would risk losing more recent changes in future merges.

Pros and Cons

We’ve touched on the pros and cons of our new set type in passing above, but let’s address it head on. The big pro is of course that we can both add and remove values, like a real Set, and yet merge things back together consistently when changes are made on different devices.

On the negative side, we have had to introduce extra metadata, which takes up more memory and consumes network bandwidth. Even worse, because we have had to introduce tombstones, the data usage of the ReplicatingSet can only increase. Even when we do remove an element, it remains in the set as a tombstone — no memory is freed at all. Even a deleted item takes up space

Lamport Counts

Let’s finish off by addressing the handling of time, which I skipped over earlier. We could use standard timestamps for this, exactly like we did for the ReplicatingRegister, but there are some risks with that. For example, imagine your iPhone has some issues with the clock, and jumps forward a year for a few hours. No big deal, right? That depends on what you do in those few hours. Imagine you make significant changes in an app that is using standard Date values to merge data. Any changes you make will effectively be locked in for the next year. Any attempt to change those values after the clock recovers will fail, because the new timestamps will be smaller than the timestamps used during the glitch.

Some argue you can work around this type of issue with some ad hoc checks. For example, you could save the date occasionally, and if you see a large jump, you could warn the user and refuse to save changes. But what if someone puts a device in a drawer for a few months? In reality, it is quite difficult to correctly identify issues with the clock. Probably the best you can do is regularly check with a reliable time server, though even this will not help if the device is offline.

The ReplicatingSet uses a different approach: a Lamport count. It’s really very simple. A Lamport count is nothing more than an integer value that increases as each change is made. This is rock solid, in the sense that it doesn’t depend on the real time at all. Your iPhone’s clock could be completely messed up, and the Lamport count would be unphased.

The strength of the Lamport count is that it has no relation to the actual time, other than that it can only increase, just like real time. But that is also a weakness: When changes are made on different devices to the same value, you can determine a winner using the Lamport count, but there is nothing to say that the winning change was actually the most recent. As long as changes are made serially on a single device, the ordering is well defined, as the Lamport count will continually grow, but when changes are made concurrently on different devices, the winner is largely unpredictable, though importantly, completely deterministic.

The history of a single replicating value over time, with the corresponding Lamport count. It begins at the bottom, with a count of 0, and time evolves upwards. The color represents the value at any given moment. After the change made with a Lamport count of 1, concurrent changes are made on two different devices, and later merged again. You can see that the winning value after the merge is the one with the highest count, but it doesn’t correspond to the most recent change in this case.

Next time…

That’s it for sets. Next time we are going to move on to the Dictionary type, and see if we can apply a similar approach there. But we will go one step further, by making our dictionary type merge recursively. This opens up much more interesting possibilities, as we can start to build more complex replicating types out of simple building blocks.

A First Replicating Collection

Other Posts in Series

In the last post I introduced you to the first replicating type in this series: a register. A register is a simple type, one that you may even have used yourself at some point, which keeps the most recent value that has been set, together with the timestamp of the update, so it can merge conflicting values from other devices. Even with this very simple type, you can develop complete distributed-data apps.

But there are limitations. A value in a replicating register can only be changed atomically. When it comes time to merge conflicting values, the register will choose one or the other, but cannot merge the two together. For example, if you stored a full name in a register, and edited the first name on one device, and the surname on another, the merged result would lose one of the two edits. Either the first name would be reverted, or the surname.

To go beyond atomic merging, we need to have new types that are capable of partial merging. Often, this means a collection. Collections can be added to, and removed from, on different devices, and the results merged at the element level, to give a combined result of the changes made on each device. Think about a collaborative editor like Google Docs. You can be editing some text at the same time as a colleague, and both edits will survive in the final document.

In this post, we will start our journey into collection types with the simplest of them all: the add-only set. It is so simple in fact, all you need to do to make one is remove one of the capabilities of the standard Set type…

The Add-Only Set

Imagine a Set where you can add new elements, but never remove them, and what you have is an add-only set. And the code is just as simple as the description

public struct ReplicatingAddOnlySet<T: Hashable> {
    
    private var storage: Set<T>
    
    public mutating func insert(_ entry: T) {
        storage.insert(entry)
    }
    
    public var values: Set<T> {
        storage
    }
    
    public init() {
        storage = .init()
    }
    
    public init(_ values: Set<T>) {
        storage = values
    }
}

The storage property holds the values in a standard mutable Set, which is kept private so that it can’t be changed from outside our replicating type. We then allow public access only to insert values, or retrieve all values, but not to remove values from the set.

You’ll recall from last time that a replicating type needs to have the ability to be merged with related copies of itself from other devices. Merging in this case just involves taking the union of the two copies of the set.

extension ReplicatingAddOnlySet: Replicable {
    
    public func merged(with other: ReplicatingAddOnlySet) 
        -> ReplicatingAddOnlySet {
        ReplicatingAddOnlySet(storage.union(other.storage))
    }
    
}

The union of the two storage sets is taken, and used to create a new add-only set, which is returned. Note that there is no tracking of timestamps, because there is no need: we don’t care when the values were inserted; once they are inserted, they are permanently in the set, and can never be removed — the add-only set can only grow.

Checking the Math

You should add unit tests for new replicating types, including tests for the three musketeers: associativity, commutativity and idempotency. I won’t got through these in detail here, but think about what they mean for a minute, and I am pretty sure you will see that it is self-evident that the add-only set conforms.

For example, the order of sets is unimportant when taking the union, so commutativity is a no brainer. And taking the union of two sets, and then taking the union of the result with either of the two original sets clearly changes nothing — idempotency is also a cinch.

How is this useful?

The add-only set is simple, but is it at all useful? What problems does it solve?

Clearly, it is not as powerful as a general purpose set which allows for removal, but there are situations where an add-only set can be used to good effect. In general, any time you are tracking a transactional history, this type is a good choice. It could be literal transactions, such as records in a banking system, or transaction-like values like entries in a log. If your values accumulate over time, don’t change once created, and are never removed, the add-only set will work great.

There are other types of replicating sets that can handle removal, so why would you ever choose the add-only set over those? The answer there is that an add-only set is very cheap. Recall that we didn’t have to save any timestamps, unique identifiers, or other metadata that was needed for the replicating register type. The space occupied by an add-only set is actually the same as that of a standard set. This makes it a cheap option for storage, and data transfer.

When nothing is something

To finish off, I want to address ‘nothing’. In particular, when ‘nothing’ is ‘something’. In the coming posts, this will become a recurring theme. It is typically one of the main challenges you need to solve when designing a replicating type — how do you represent nothing.

See, there are different types of nothing. There is the nothing you get when you create a new replicating value, and it is empty. And there is the nothing you get when you remove a value from a replicating type. The two are generally not the same.

How to represent and store the absense of a value in a replicating type is key to satisfying our mathematical requirements. In the add-only set, we solved this problem by simply excluding one type of nothing, namely, the one you get when you remove an element. With that option gone, if a value is not in our storage, we know it was never added.

Why a Swift Set is not a replicating type

As an exercise, let’s take a standard Swift Set, and run through some tests in our collective heads. Note that a standard Set does allow removal of elements. Imagine that we have two devices (A and B), with the same set of values on each. Then, on device A, a value is removed, and now device B has to merge that change in.

Device B sees that it has one extra value in its own copy of the set, but what does that mean? Did A remove that value, or did B add it since the last sync? There is no way to know, and that is all because there is no entry in the set to represent a removed entry.

When we start to look at more advanced types, we will see how you introduce something to represent nothing.

Next Time…

The add-only set is a very basic type, but does have its uses, is easy to implement, and cheap in terms of storage space and data transfer. If we want something that behaves more like a standard set, with removals, we need a more advanced collection. We will take a look at how you can do that in the next post.

Feature image from here and licensed Creative Commons.

A First Replicating Type

Source code for this series is in this GitHub repo. It will be extended with each post. Other Posts in Series

When I first started reading about Conflict-Free Replicated Data Types (CRDTs), I expected a fertile new field of Computer Science dedicated to a whole new approach to managing data. I was soon somewhat disappointed, because everything I learned was accompanied by a generaous slather of déjà vu (yes, I Googled the accents). It felt like every replicating type encountered was already in widespread use. Heck, I had used half of them myself!

So CRDTs are not always new, but it is still good that they are being baptised and catagorized. It’s important to recognize patterns in solutions; it makes ideas easier to convey to others, gives a common language, and allows a new generation of types to be built up on the shoulders of existing ones.

Today we are going to look at a replicating type — our first in this series — that I am pretty sure you will have seen before in some way, shape or form. Your reaction may be to ask “How is that a CRDT when I already use it regularly?” Don’t get discouraged. There are more advanced types coming down the pipe, but walk before run you must.

The Replicating Register

Ask yourself what most people expect to happen when they make changes to the same data on two different devices. In nearly all cases, they would expect the most recent change to survive after the data is merged. In many apps, this is all the merge logic you need — last change wins.

What would a type that encapsulated this simple behavior look like? Well, like this

public struct ReplicatingRegister<T> {
    
    fileprivate struct Entry: Identifiable {
        var value: T
        var timestamp: TimeInterval
        var id: UUID
        
        init(value: T, 
            timestamp: TimeInterval = 
                Date().timeIntervalSinceReferenceDate, 
            id: UUID = UUID()) {
            self.value = value
            self.timestamp = timestamp
            self.id = id
        }
        
        func isOrdered(after other: Entry) -> Bool {
            (timestamp, id.uuidString) > 
                (other.timestamp, other.id.uuidString)
        }
    }
    
    private var entry: Entry
    
    public var value: T {
        get {
            entry.value
        }
        set {
            entry = Entry(value: newValue)
        }
    }
    
    public init(_ value: T) {
        entry = Entry(value: value)
    }
}

Aside from a few odds and ends, which we will deal with below, this code is the whole type. It’s really very simple: a ReplicatingRegister is a type that stores a value together with the timestamp at which the value was last changed.

The ReplicatingRegister is generic on the type of the value it contains. You can put any value you like in a register. Here is how you would create a register for an Int.

var a = ReplicatingRegister(5)

We can update the value like this

a.value = 6

and get the value out again like this

let number = a.value // number becomes 6

The Workings of a Register

You can see from the code above that the ReplicatingRegister contains a helper struct called Entry.

fileprivate struct Entry: Identifiable {
    var value: T
    var timestamp: TimeInterval
    var id: UUID

    init(value: T, 
        timestamp: TimeInterval = 
            Date().timeIntervalSinceReferenceDate, 
        id: UUID = UUID()) {
        self.value = value
        self.timestamp = timestamp
        self.id = id
    }

    func isOrdered(after other: Entry) -> Bool {
        (timestamp, id.uuidString) > 
            (other.timestamp, other.id.uuidString)
    }
}

Entry contains the actual value, but also a timestamp. When the value of the register gets set, a whole new Entry is created, with a new timestamp.

public var value: T {
    get {
        entry.value
    }
    set {
        entry = Entry(value: newValue)
    }
}

The isOrdered function determines which of two entries is most recent, which we will need when we come to merge registers a bit later.

Murphy’s Law and Unique Identifiers

You may be wondering why the Entry type includes a UUID identifier. It already has a timestamp, which is an identity of a sort. Isn’t that timestamp unique enough?

Maybe, but you will sleep better at night if you assume it is not unique enough. A timestamp has something like millisecond accuracy. A computing device can do thousands, even millions of operations in that time. Two changes to the same value on the same device may very well fall on exactly the same tick of the timestamp clock.

What would happen if we used the timestamp in isolation? If two changes collided — had the same timestamp — the ‘winner’ would effectively be random. Your devices could easily pick different outcomes, and your type will have diverged — your app is no longer in sync. To avoid this, we need some way to pick the same winner on all devices, even if the timestamps are exactly the same. For that, we add the UUID. It ensures a deterministic result in cases where the timestamps collide.

Merging Registers

There is one ability that all replicating types must have: merging with other replicas. We can capture this in a very simple protocol.

public protocol Replicable {
    func merged(with other: Self) -> Self
}

Merging two values of the same register simply involves picking the latest one.

extension ReplicatingRegister: Replicable {
    
    public func merged(with other: ReplicatingRegister) -> 
        ReplicatingRegister {
        entry.isOrdered(after: other.entry) ? self : other
    }
    
}

It’s so simple, it probably should be forbidden. With just this type in your arsenal, you can build very robust distributed data applications.

Testing the Type

Writing unit tests for replicating types is generally pretty straightforward, because they are so self contained. Typically you add a few basic creation and update tests

final class ReplicatingArrayTests: XCTestCase {
    
    var a: ReplicatingRegister<Int>!
    var b: ReplicatingRegister<Int>!

    override func setUp() {
        super.setUp()
        a = .init(1)
        b = .init(2)
    }
    
    func testInitialCreation() {
        XCTAssertEqual(a.value, 1)
    }
    
    func testSettingValue() {
        a.value = 2
        XCTAssertEqual(a.value, 2)
        a.value = 3
        XCTAssertEqual(a.value, 3)
    }

Then you will want to test merging

func testMergeOfInitiallyUnrelated() {
    let c = a.merged(with: b)
    XCTAssertEqual(c.value, b.value)
}

func testLastChangeWins() {
    a.value = 3
    let c = a.merged(with: b)
    XCTAssertEqual(c.value, a.value)
}

And lastly, you should run through the mathematical requirements we discussed in the first post of the series: associativity, commutativity, and idempotency.

If you recall, merging is associative if it doesn’t matter how you group values. It should not matter if we merge register a with b, and the result with c; or we begin with b and c, and merge the result with a.

func testAssociativity() {
    let c: ReplicatingRegister<Int> = .init(3)
    let e = a.merged(with: b).merged(with: c)
    let f = a.merged(with: b.merged(with: c))
    XCTAssertEqual(e.value, f.value)
}

Commutativity of registers means that it doesn’t matter whether you merge a with b, or b with a.

func testCommutativity() {
    let c = a.merged(with: b)
    let d = b.merged(with: a)
    XCTAssertEqual(d.value, c.value)
}

And idempotency simply means that merging the same values multiple times has no effect on the outcome: you get the same answer as the first time you merge.

func testIdempotency() {
    let c = a.merged(with: b)
    let d = c.merged(with: b)
    let e = c.merged(with: a)
    XCTAssertEqual(c.value, d.value)
    XCTAssertEqual(c.value, e.value)
}

The Weaknesses of a Register

If registers are so simple, and you can build whole apps with them, why do we need other, more complex replicating types? Registers work fine for simple values that we want to change atomically. Numbers, simple strings, enums and the like, all work well with registers. All changes are atomic. We don’t want changes from one device ‘mixing’ with those from another, to give half the value from each. We want one of the changes to win outright.

But there are many cases where this is undesirable. Imagine you have someone’s full name. It would be a shame if you couldn’t edit the first and last names independently. The solution in this case could be as simple as using two different registers, but in other cases, even that may not suffice. Imagine you are developing a collaborative text editor. It would be very limiting if someone entering some text on one device caused all the changes made by someone on another device to be overridden and lost. In that situation, we want to combine the changes; we need a more sophisticated replicating type, capable of partial merges.

Conditional Conformance to Protocols

That covers the replication of registers, but there are a few other Swifty aspects you will probably want to include in your replicating types. For example, you may wish to make them conform to protocols like Equatable and Hashable. Of course, this will only work if the contained value also conforms to the protocol, so we use conditional conformance for this.

extension ReplicatingRegister: Equatable where T: Equatable {
}

extension ReplicatingRegister.Entry: Equatable where T: Equatable {
}

extension ReplicatingRegister: Hashable where T: Hashable {
}

extension ReplicatingRegister.Entry: Hashable where T: Hashable {
}

You need to be a bit careful here. It is very easy to confuse the equality or hashability of the contained value with that of the replicating type. They aren’t the same. It is possible that two replicas have the same value, but the replicas themselves are not equal, having been set on different devices with different timestamps. Keep clear in your head whether you want to test the whole state of the replicating type, or just the value it contains.

Codability

One of the more important conditional conformances for replicating types is the Codable protocol. Without a way to serialize the replicating types, we have no way to transfer them between devices for sync purposes. In most cases, it is trivial to add.

extension ReplicatingRegister: Codable where T: Codable {
}

extension ReplicatingRegister.Entry: Codable where T: Codable {
}

And a test confirms that it works as expected.

func testCodable() {
    let data = try! JSONEncoder().encode(a)
    let d = try! JSONDecoder().decode(ReplicatingRegister<Int>.self, 
        from: data)
    XCTAssertEqual(a, d)
}

Property Wrappers

The ReplicatingRegister struct is so simple, you may be tempted to use it as a property wrapper. You could certainly do that, but I have avoided the urge, because the goal of property wrappers is to hide the enclosing type and have things just work as if it weren’t there. With replicating types, you often need to manipulate the type directly — it is not just a decorative shell around your data. This is even more the case with the advanced types we will meet later in the series. For this reason, I resist the urge to hide away the replicating type containers. They are first class citizens here.

Next Time…

That’s it. Your first replicating type! Simple really, but very powerful. Next time we will move to containers, and start to build replicating types for storing multiple values.

Conflict-Free Replicated Data Types (CRDTs) in Swift

Other Posts in Series

If you read any of my earlier posts here, you were probably left wondering what the name of the blog was all about. When I came up with the idea, I was planning to blog about decentralized approaches to handling app data, ie, how to sync with other devices, servers, extensions, and even multiple windows within the same app. Today I will finally begin on that journey…

Introducing Replicating Types

I want to begin a series of posts on the new coolness in the world of sync: Conflict-Free Replicated Data Types (CRDTs). CRDTs, which I will simply call ‘replicating types’ from here on, are data types that have the ability to merge themselves when changes are made on different devices, in order to reach a consistent state. They have built-in logic which allows them to be updated independently, and then merged back together in a completely deterministic way, such that all syncing devices end up with the same value.

What does this mean in practice? When using replicating types in Swift, you will typically replace the standard data types of your properties (eg String, Int) with more advanced types, like so

struct Note {
    enum Priority {
        case low, normal, high
    }

    var title: ReplicatingRegister<String> = .init("Untitled Note")
    var text: ReplicatingArray<Character> = .init()
    var priority: ReplicatingRegister<Priority> = .init(.normal)
}

These new types still hold the value you need in your model, but also have the ‘intelligence’ to be able to merge in changes made on other devices, and reach a consistent value on all devices.

Where is the Server?

Note that I ascribe the sync ‘intelligence’ to the type itself, rather than to any framework or server. There is no central server deciding which values to keep, and which to discard. There is no truth — decentral apps rely on trust rather than truth. Each device follows the same set of well structured rules, and stays consistent with the other devices without any direct means of communication.

There is no truth — decentral apps rely on trust rather than truth.

Servers and cloud services, where they are used, are purely for data transport and storage. They aren’t actively involved in the policy making of sync. This makes replicating types ideal for utilizing with CloudKit, Dropbox, Firebase, MondoDB, Amazon DynamoDB, WebDAV, S3 and any other online data storage. No need to write any Node.js or Go; everything you need to have a robust syncing app already exists right in the client OS.

A Look Ahead

I’ll start this series off with the fundamental maths of replicating types. Don’t fret, I will make it very short, and very approachable, describing things in everyday terms.

In the coming posts, we’ll start to build simple replicating types, and eventually more advanced ones. By the end of the series, we will have a kit of types that can be used to develop an app with full sync capability.

And that is exactly what we will do: we’ll make a basic note taking app with offline storage, which syncs across devices via CloudKit, and allows simultaneous edits to the same note.

Roll Your Own

You may ask, “Why doesn’t he just give us the code and be done with it, instead of writing a blog series?” If the goal was simply to produce a library of replicating types, that would have made sense, but I aspire to something more — I want you to be able to build your own replicating types.

Yes, you can take the types we make here and use them in your own apps, but the broader goal is to get you to start thinking about how replicating data types work, the aspects they have in common, and the tricks you can use to design them. Ultimately, you will be able to design and build your own replicating types tailored to the specific challenges you encounter in your own apps.

Math Made Manageable

I promised a little math, and I promise this will be the last little math. But it is useful to understand a few mathematical aspects of replicating types before we start. It will make it easier to evaluate data types, to understand which fit in the scope of replicating types, and which don’t. And most importantly, how we might convert a standard data type into a replicating type.

The replicating types we will design are state-based CRDTs. What this means is that when we come to sync, we will copy the whole value of the replicating type to other devices, rather than just any changes that have been made since the last sync. (The latter would be an operation-based CRDT.)

State-based replicating types all share the ability to merge. A single value may be copied to other devices, edited in different ways, and then transferred back to the original device. We can then ask the replicated value to merge with each of the modified values, resulting in a single value that is the same on every device.

The merging of state-based CRDTs must conform to a few basic mathematical principles. It must be associative, commutative, and idempotent. These terms may seem intimidating, but they are really just a way of saying that it doesn’t matter…

  1. How the replicated values get paired together for merging.
  2. What order the merging of values takes place.
  3. Whether a given value is merged just once, or multiple times.


It is largely common sense. You could imagine that if any of these points were not true, the data would quickly get out of sync, as each device syncs values from other devices in different orders, and perhaps multiple times. (With no central server, there is no coordination between devices to avoid such scenarios.)

Associative

Imagine you are an app with some piece of text, running on Device A. You receive two edited values of that text, made on Devices B and C. And imagine the other devices also get the recent text from their counterparts, and the goal is that they all eventually agree on what the final value of the text should be.

On Device A, we might merge together the text from B and C first, then merge the result with our own version of the text. Device B may merge the text from A with its own value first, and then the result with the text from C.

If we are going to end up with the same answer, it should not matter how the values are paired up during the merge. The values can be associated (paired) with each other in any way, and we should still get the same result.

(A merged-with B) merged-with C = A merged-with (B merged-with C)

In short, the type is associative if it doesn’t matter how you pair the merge operations from different devices. Whichever pairing you use, you will get the same answer.

(As an common example, addition is an operation that we are all familiar with which is associative. Eg 1+(2+3) = (1+2)+3.)

Commutative

Operations are commutative if they can be reordered, and the answer remains the same. Addition is commutative, as well as associative. For example,

2 + 3 + 4 = 4 + 3 + 2

In the context of replicating types, the merge function is commutative if the order of the values doesn’t matter.

A merged-with B = B merged-with A

Idempotent

We are all familiar with associative and commutive operators in basic arithmetic, even if we have never heard the terms before, but idempotency is a little more obscure. It just means that after an operator has been applied once, applying it again has no effect.

There are no really simple arithmetic operator that exhibits this behavior. For example, addition is not idempotent. An operator that adds 1 will produce ever larger results when applied multiple times.

3 + 1 ≠ 3 + 1 + 1

But you also don’t have to look very far to find fairly simple idempotent operators. An example from Swift is the max function. Imagine an operator that takes the maximum of some variable with the integer 10.

f(x) := max(x, 10)

Applying this function twice will be equivalent to applying it once. The second application will have no effect, because the result will already be the maximum of the two values.

max(max(x, 10), 10) = max(x, 10)

For our replicating types, idempotency implies that if we merge the same value twice (or more), we will get the same answer as if we only merged once. In short, each change will be incorporated once, and only once. Additional attempts to apply exactly the same edit will be ignored.

Next Time…

In the next installment, we we build our first replicating type. We’ll start with something simple, but nonetheless useful. There is even a strong possibility you have used it yourself at some point…

Why grokking flatMap is essential to effective Combine

It’s perhaps suicidal to talk about the Combine framework on the eve of WWDC2020, but I’m going to take a stab at it. Combine will no doubt change a lot on Monday, but I don’t expect the aspect I wish to discuss to change drastically.

I have worked a lot with asynchronous code over the years. When developing an app, you can usually get away with a bare minimum of it, perhaps just the code needed to query a web server. The rest, from disk store queries to UI updates, is generally synchronous.

But when you develop sync frameworks like Ensembles and LLVS, asynchronicity is everywhere. There is the obvious networking involved, such as querying CloudKit, but there are also long running consolidation tasks that cannot be executed synchronously on the main thread. Performing a “sync” operation in a framework like Ensembles can take a few seconds, but I even know extreme cases that can take hours. In a system like that, just about everything is asynchronous.

When you are developing in a codebase like that, it is of fundamental importance to begin with a strategy for handling asynchronicity. You can do a lot worse than good ol’ completion handlers, but they cop a bit of flack for the dreaded Pyramid of Doom. Don’t let that put you off: completion handlers are extremely easy to understand, because they offer a clear serial path through the code. And you can combat the ‘pyramid’ by using extra functions, or an asynchronous queueing approach, which is what I usually do.

Combine is Apple’s official approach to asynchronous programming. It is still too new for me to consider using in any of my existing products, but I have been working with it from time to time in smaller side projects, in order to learn the framework, and understand how to think in this new paradigm.

I won’t provide a complete introduction to Combine here. There are plenty of resources out there to get started. (Personally, I took a course with the great Daniel Steinberg to kick off my learning.) The nutshell intro is that Combine is a framework for building asynchronous pipelines. You have a number of tasks that need to be done asynchronously, often in order, and sometimes concurrently. Combine gives you tools to build a dynamic structure in memory that will ensure that these tasks execute in the required order, passing the results of one task on to the next, and also offering a means of propagating and handling errors. I like to think about it as building the same sort of operations and structures you have in standard serial Swift code, but dynamically with types. (I’m sure one day programming languages will evolve to do these same things, but for now it is all in the framework space.)

Standard introductions usually start with a URLSession fetching some data from a web service, which then channels the downloaded data into a map operator that transforms it into some model objects, with the pipeline terminating in a sink that presents the data in the UI. This is a completely logical way to get started, but it doesn’t offer much more than your standard completion handler.

I want to skip over that to a much more advanced aspect of pipeline building that took me a long time to really grok. But until you do grok it, you won’t be able to do much more with Combine than replace some of your completion blocks with slightly more elegant code.

The operator I want to discuss is flatMap. A lot of Swift developers still carry the scars of the early days of the language, and twitch at the sight of it. When we first started using flatMap, on arrays and other containers, it was wrongly named; it wasn’t a true flatMap in the functional sense, and that confused things greatly. It has since been renamed to compactMap, but the confusion reigns on. (If you want to know all about the theory behind flatMap, you can better ask Daniel Steinberg — functional programming is one of his passions.)

If you still carry these scars, and are assuming that flatMap will remove nil values from an array, let that go right now! And also, let go of the notion that it is related to map. Maybe that is true in some theoretical way, but if you start from that position, you will just end up confused. Combine’s map transforms the data values that get passed along the pipeline in the same way the map function transforms the elements in an array one at a time. flatMap is a completely different animal: The way I think about flatMap is that it squashes down the upstream part of the pipeline, replacing it with an entirely new upstream pipeline. In other words, flatMap flattens the pipeline itself — the publishers and operators that came before — into some other publisher.

“OK, …”, I hear you say, “… let’s assume I accept this. So what? Why does that matter?” It matters a whole lot. It is this quality that allows you to build powerful asynchronous Combine pipelines. Without it, you can only build static, unchanging pipelines, which only solve the simplest of problems. What flatMap introduces is the possibility of changing the pipeline on-the-fly. It provides a mechanism for branching. And I want to spend the rest of this post looking at a concrete example to demonstrate.

I first realized the importance of flatMap in Combine when I was working with CloudKit. I was writing code to setup a CKRecordZone. The goal was to come up with a fire-and-forget Combine pipeline to query the cloud to see if the zone already existed, and if not, create the zone. This sort of branching is extremely common in every piece of code we write, but how do you setup a Combine pipeline to handle the same branching?

First, let’s take a look at the zone setup function.

var zone: CKRecordZone?

func setupZone() -> AnyCancellable {
    retrieveZone()
        .retry(3)
        .map { CKRecordZone?.init($0) }
        .replaceError(with: nil) // We are giving up
        .receive(on: RunLoop.main)
        .assign(to: \.zone, on: self)
}

When you see code like this, you are seeing Combine at its best. It is simple to read, and yet there are some pretty powerful asynchronous operations going on behind the scenes.

We will look at retrieveZone in a minute. For now just accept that it returns a publisher which provides a record zone, or gives an error.

func retrieveZone() -> AnyPublisher<CKRecordZone, Swift.Error>

In setupZone, we take the publisher returned by retrieveZone, and add a retry in case an error occurred during the retrieval. It will retry the retrieval three times, before giving up. When it does give up, the replaceError will come into play, setting the result to nil. The retrieve simply makes sure we are on the main thread, and the final assign sets a property to the zone value that resulted (…or nil if an error arose).

You may be wondering about the map. I had to think twice about it myself when I saw it again. It’s there because we are eventually assigning to an optional CKRecordZone property; to make all the types in the pipeline match up, we have to the convert the non-optional CKRecordZone that retrieveZone gives us, into an optional. We can do that with a map. It’s a bit silly, but hey, that’s strict static typing for you (…and that is a whole other discussion).

To use the setupZone function, we simply call it to build the pipeline, and retain the result in a property. (One of the most common mistakes you will make when first using Combine is to forget to retain the pipeline, in which case it gets cancelled immediately.)

var setupZoneSubscription: AnyCancellable?

init() {
    setupZoneSubscription = setupZone()
}

So far, so good, but what about retrieveZone, and weren’t we going to talk about flatMap? The moment of truth has arrived.

retrieveZone begins by wrapping a CloudKit zone fetch in a future.

func retrieveZone() -> AnyPublisher<CKRecordZone, Swift.Error> {
    let fetchZone = Future<CKRecordZone?, Swift.Error> { 
        [unowned self] promise in
        self.cloudKitDatabase.fetch(withRecordZoneID: self.zoneId) { 
            zone, error in
            if let error = error {
                promise(.failure(error))
            } else {
                promise(.success(zone))
            }
        }
    }

If you are wrapping older asynchronous APIs for use in Combine, you will nearly always reach for Future. It is basically the Combine equivalent of a completion handler. The future has a result type, in this case CKRecordZone?, and an error type. The block where the CloudKit fetch takes place is passed a promise; when the asynchronous task is complete, the promise is called, passing in either a .failure result, or a .success result, with the corresponding associated value.

If the fetchZone future indicates there is no zone in CloudKit, we want to create one. For that we need another future, again wrapping around a CloudKit operation.

    let createZone = Future<CKRecordZone, Swift.Error> { 
        [unowned self] promise in
        let newZone = CKRecordZone(zoneID: self.zoneId)
        let operation =
            CKModifyRecordZonesOperation(recordZonesToSave: [newZone], 
                recordZoneIDsToDelete: nil)
        operation.modifyRecordZonesCompletionBlock = { 
            savedZones, _, error in
            if let error = error {
                promise(.failure(error))
            } else {
                promise(.success(savedZones!.first!))
            }
        }
        self.cloudKitDatabase.add(operation)
    }

This future returns a non-optional CKRecordZone. The CKModifyRecordZonesOperation will either succeed, leading to a CKRecordZone, or it will fail, and give an error. (The fetchZone future used an optional, because it was valid for it to return a nil value, indicating the zone was not found.)

Now we are ready to put it all together, and more importantly, see how flatMap allows us to adapt dynamically as the pipeline executes.

    return fetchZone
        .flatMap { existingZone in
            if let existingZone = existingZone {
                return Result<CKRecordZone, Swift.Error>
                           .Publisher(.success(existingZone))
                           .eraseToAnyPublisher()
            } else {
                return createZone.eraseToAnyPublisher()
            }
        }.eraseToAnyPublisher()
}

Our returned pipeline begins with the fetchZone. A flatMap intercepts the result, and we add our branching code. If the zone is non-nil, we just put it straight into a Result publisher with a success value and the associated zone. If, on the other hand, the zone from fetchZone was nil, we return the createZone future we built above. Whichever publisher is returned from flatMap will replace whatever came earlier, in this case, the fetchZone.

Of course, you aren’t restricted to just simple if-else statements in a flatMap. You can do whatever you like in there. But whatever it is that you do, you have to end up returning a publisher with the correct result type and error type. That is really the only restriction: the publisher returned can be anything you like, but every return must have matching types.

Hopefully this has delivered an ah-ha moment for you. If you are very new to Combine, it may be a bridge too far, but keep it in the back of your head, because you will need it at some point. The first time you come across some Combine code where you wish you could branch when the pipeline is halfway though executing, think about this post, and most of all, think about flatMap.

Why TextView is my SwiftUI canary

WWDC is just around the corner, and most of us will be fully focussed on what happens with SwiftUI. The unveiling last year generated great excitement, but there are still plenty of holes to be filled before it is a solid replacement for UIKit and AppKit (…or even a solid complement).

One of the big questions on my mind is how well the fully declarative approach scales to complex apps. You can already build quite reasonable portal apps for your favorite web service with SwiftUI, which is 90% of the iOS app market, but I am much more interested in the other 10%. Can you build an advanced iOS app or serious macOS app with SwiftUI? Could you develop an app like Keynote or Xcode using SwiftUI?

I spent a lot of time this year — probably more than desirable — working with the framework. At Agenda, we decided to ‘kick the tyres’ by adopting it in a new internal tool that we wanted to develop. The tool was not trivial either: it loaded significant amounts of data, shared it between multiple users with LLVS backed by the CloudKit public store, and allowed collaborative editing and discussion. Effectively, it was like a fully decentralized web app, built with native UI.

Ambitious? Sure. Too ambitious? Undoubtedly. But we learnt a lot before abandoning the idea. And it did actually work, though after a while we concluded ironing out the performance issues was not really worth the effort.

And this brings me back to the present day, and what we should be looking for at WWDC. One thing I learned from our SwiftUI tool is that a fully declarative style presents some performance challenges. By its nature, SwiftUI is based around view tree diff-ing. When something in the model changes, it triggers a binding to fire, which in turn invalidates the view tree. In order to update the screen, SwiftUI now compares the new tree with the old, and determines what changes are needed to the scene that the user sees.

This process is fast for a few standard views, but there are bigger challenges looming. For example, take a large array of values that you want to present in a List. We encountered some serious performance issues when updating data in such a List, as SwiftUI would attempt to diff thousands of View nodes. You could restructure your UI in order to avoid such large lists, but that is a bit of a cop out, because the technologies SwiftUI is designed to supplant can handle such large lists.

The problem is perhaps even more apparent in a text view. We briefly saw a TextView type appear during the SwiftUI beta in 2019, but it didn’t make the final release. My guess — and it is just a guess — is that someone in Apple concluded that it worked fine if you were presenting tweets, but things fell apart when you wanted real-time editing on Chapter 5 of “War and Peace”.

You can bind a TextField to a model String property, and it will work fine, but do you really want to bind the contents of a TextView to an AttributedString the length of a novel? Diff-ing that is not going to cut it.

One way they could take SwiftUI in order to solve this is to introduce a new type of text model, one with internal hierarchy that makes diff-ing extremely efficient. Think about a tree-like structure, so that it could very quickly establish which subtrees were altered, and ignore all other parts of the tree. Effectively, it would be introducing a structure similar to the view tree itself, but inside the model.

This option would see NSTextStorage replaced with a highly diff-able structure, but it may also be possible to introduce a similar approach at a different level. Perhaps the model data would be left unchanged, and a specialized TextStorageBinding type added, which would embellish the model with metadata to make diff-ing efficient. Or could they even introduce View types such as Paragraph which shadow the model text content, and allow exactly the same diff-ing mechanism to be used as in the rest of SwiftUI?

Some of these proposals may seem far fetched, but this is exactly how we structured the text in the Agenda notes app. First, our model has finer granularity than just putting the complete text of a note into a single property. Each note is broken into paragraphs, meaning that a user edit doesn’t require a complete refresh of the whole note. Instead, just the affected paragraphs can be saved, refreshed on screen, and synced to other devices. This approach does require extra bookkeeping — we have to pass around the ‘edited’ paragraph identifiers — but it is this type of data that SwiftUI will no doubt need to introduce if it is ever to host an editable TextView containing the whole of Tolstoy’s classic novel.

At this point, it is anyone’s guess which direction SwiftUI will take. Perhaps Apple figure the days of complex apps are over, and they are not going to do anything to address such concerns. Or perhaps it is just a question of priorities, and we will see how they intend to tackle these scaling issues at WWDC2020. Either way, I will be seeking out the documentation for TextView; that’ll be my canary for where SwiftUI is headed, and whether it will soon evolve into a capable replacement for UIKit/AppKit.