Swift 5.1 Collection Diffing
Disclaimer: this article refers to the first Swift implementation of collection diffing. The implementation itself has already been improved, however the concepts behind this article are exactly the same.
Until recently, dealing with dynamic tables/collection views meant one of the following:
 Call
reloadData()
at every change  Use a dependency like IGListKit or DifferenceKit
 Manually deal with every possible change (while praying to not miss anything 🤞🏻)
Swift 5.1 introduces a new alternative: Use the new Collection
’s difference(from:)
.
Want to know about what else is new Swift 5.1? Check out my lightning talk here.
Unlike other features, Swift collection diffing is entirely additive and it is completely written in Swift:
this presents us an unique opportunity to learn how the collection diffing is actually implemented without digging into any other lower level language.
In this article I’m going to do exactly that: at over 5000 words with a lot of technicalities and code, you might want to find a confortable place before digging in.
Ready? Let’s go!
CollectionDifference
Before talking about the function itself, I want to focus on what it returns:
an instance of CollectionDifference<ChangeElement>
.
CollectionDifference is a generic Collection
defined as “A collection of insertions and removals that describe the difference between two ordered collection states”.
The generic type ChangeElement
is the element type of the two collections that we are diffing, note that, if we look solely at the CollectionDifference
definition, ChangeElement
is completely unconstrained: it doesn’t even need to conform to Equatable
!
The elements of this collection are of type CollectionDifference.Change
, which is a new enum with two cases: .insert
and .remove
. Before moving into this enum, there are a couple of points that must be disclosed about CollectionDifference
:
 The collection returns first all the removals (all the
.remove
cases), and then all the insertions (all the.insert
cases).
This is assured by an internal initializer: even if we try to initialize this collection with changes in random order, the initialized collection will be always ordered properly.  The collection insertions, deletions, and association between the two must be unique (more on this later).
This is assured by an internal validator: while trying to initialize an unsortedCollectionDifference
is allowed, failing this uniqueness validation will fail the collection initialization.
Insertions and Removals
If we’re interested exclusively on the insertions or the removals of a CollectionDifference
, instead of traversing the collection itself, we can use its public properties insertions
and removals
, which are two arrays (with elements of type CollectionDifference.Change
).
These arrays are actually where the elements of the main collection are stored, and accessing them directly is more performant the traversing the collection itself.
CollectionDifference.Change
When comparing two collections, you can think of any change between the collections elements as either:
 an insertion (a new element has been added)
 a removal (an element has been removed)
 or both (when an element changes position, it is removed from the current position and added to the new position).
With that being said, it comes as no surprise that CollectionDifference.Change
is an Enum
with two cases: insert
and remove
.
Both cases come with three associated values: an offset, an element, and an optional association.
Change Offset
The offset is the position of the change.
In case of a removal, it reflects the position where the element used to be:
let oldArray = ["a", "b", "c", "d"]
let newArray = ["a", "b", "d"]
// The element "c" at index 2 has been removed
let difference = newArray.difference(from: oldArray)
// difference is a oneelement collection
// where the element is of type `.remove` with `offset` 2
In the case of an insertion, it reflects the position of the element in the final collection:
let oldArray = ["a", "b", "c", "d"]
let newArray = ["a", "b", "c", "d", "e"]
// A new element "e" has been added at index 4
let difference = newArray.difference(from: oldArray)
// difference is a oneelement collection
// where the element is of type `.insert` with `offset` 4
Change Element
This element is the whole reason why CollectionDifference
is declared generic:
the change element is the actual collection element that has been removed or inserted.
let oldArray = ["a", "b", "c", "d"]
let newArray = ["a", "b", "d", "e"]
// The element "c" at index 2 has been removed
// A new element "e" has been added at index 3
let difference = newArray.difference(from: oldArray)
// difference is a two elements collection:
//  the first element is of type `.remove` (with offset 2) with element "c"
//  the second element is of type `.insert` (with offset 3) with element "e"
Change Association
Again, when an element moves position between two collection states, the change can be considered as a deletion (from the old position) and as an insertion (to the new position).
This is what the Change
association is for: to link that removal and that insertion.
The association, called associatedWith
, is an index representing the other change offset:
if we’re looking at a .insert
change, the associatedWith
index will be equal to the associated .remove
offset
index, and vice versa.
As change associations add an extra cost on the diffing, they’re not computed by default:
the difference(from:)
result is a collection of .remove
/.insert
elements all with associatedWith
value set to nil
. If we’re also interested in this association, we need to call .inferringMoves()
in our difference collection:
let oldArray = ["a", "b", "d", "e", "c"]
let newArray = ["a", "b", "c", "d", "e"]
// the element "c" has moved from index 4 to 2
// therefore we can think it as:
//  a removal from position 4
//  and an insertion at position 2
let difference = newArray.difference(from: oldArray)
// difference is a two elements collection
//  the first element is a `.remove` with offset 4
// and associated offset of `nil`
//  the second element is an `.insert` with offset 2
// and associated offset of `nil`
let differenceWithMoves = difference.inferringMoves()
// differenceWithMoves is a two elements collection
//  the first element is a `.remove` with offset 4
// and associated offset 2
//  the second element is an `.insert` with offset 2
// and associated offset 4
InferringMoves
This function is straightforward: it scans the whole CollectionDifference
instance and adds an association when an element change matches both among the removals and the insertions, otherwise it just returns the Change unchanged.
A Look Back to CollectionDifference’s Rules
Now that we have a clear definition of what the Change
type is, we can look back to the CollectionDifference
definition and have a clearer understanding of some of its rules:
 Having nonunique removals would mean having multiple removals at the same index:
it’s impossible.  Same with additions: having multiple additions at the same offset would mean having multiple elements at the same index in the final collection state.
 Lastly, associations must always come in pairs (an insertion linked to a removal and vice versa):
there can’t be a one way association.
A Second CollectionDifference Order
If we look at the how the collection internal init is defined, we can see that CollectionDifference
has a clear order that goes beyond “removals first and insertions second”:
all the insertions are stored in the insertions
array in order from lowest to highest offset
, and same goes for the deletions with the removals
array.
However, if we look at the CollectionDifference
subscript
, we can see that the collection is exposed in, again, a different order:
the removals are exposed from highest to lowest offset
, while the insertions from lowest to highest offset
.
This exposed order allows us to use the returned CollectionDifference
instance to transform a collection from the old state to the new state by applying, one by one, the collection Change
s:
let oldArray = ["a", "b", "c", "d"]
let newArray = ["x", "a", "e", "c"]
var anotherArray = oldArray
let difference = newArray.difference(from: oldArray)
// difference is a four elements collection:
// 1. `.remove` at offset 3
// 2. `.remove` at offset 1
// 3. `.insert` at offset 0
// 4. `.insert` at offset 2
for change in difference {
switch change {
case let .remove(offset, _, _):
anotherArray.remove(at: offset)
case let .insert(offset, newElement, _):
anotherArray.insert(newElement, at: offset)
}
}
// at this point `anotherArray` is equal to `newArray`
anotherArray
starts in the same state of oldArray
and ends up like newArray
by following the difference
collection order:
["a", "b", "c", "d"] // initial state
["a", "b", "c"] // removal at index 3
["a", "c"] // removal at index 1
["x", "a", "c"] // insertion at index 0
["x", "a", "e", "c"] // insertion at index 2
If the collection was ordered in any another way, we would have obtained a different outcome (or even a crash!).
Applying
If we need to apply the difference
result to a collection, we don’t have to do it ourselves (like in the example above):
Swift offers a new method, applying(_:)
, that does it for us.
Therefore the example above could have been written entirely as:
let oldArray = ["a", "b", "c", "d"]
let newArray = ["x", "a", "e", "c"]
var anotherArray = oldArray
let difference = newArray.difference(from: oldArray)
// applying the difference here 👇🏻
anotherArray = anotherArray.applying(difference)!
// at this point `anotherArray` is equal to `newArray`
Since this method can be called on any collection (as long the collection elements are compatible), instead of applying the difference
in place, it returns a new optional collection with the difference applied.
The reason why the return type is optional is clear as soon as we imagine doing a remove
or an insert
to an index out of range:
instead of crashing, the function will return nil
when the difference is applied to an incompatible collection.
difference(from:)
Now that we’ve covered the basics, it’s time to uncover what this method actually does, it might take you by surprise (it did to me!) but the whole implementation is a one liner:
extension BidirectionalCollection where Element : Equatable {
public func difference<C: BidirectionalCollection>(
from other: C
) > CollectionDifference<Element> where C.Element == Self.Element {
return difference(from: other, by: ==)
}
}
It turns out that we were using a convenience method all along!
Before digging into the real difference(from:by:)
method, it’s important to note how it’s difference(from:)
that requires the elements of the collections to conform to Equatable
, this requirement is nowhere to be seen in difference(from:by:)
👍🏻.
difference(from:by:)
So far we’ve used CollectionDifference
to compute the difference in the equality of two states of a collection, however the truth is that this comparison could be used for many more use cases:
in fact, the original pitch for collection diffing describes the feature as a “diffing functionality […] necessary to provide easy creation, representation, and application of ordered collection state transitions”.
A state transition can have different meanings based on the context, therefore it makes a lot of sense for Swift to set no limits on what this transition can be.
With that being said, it should come with no surprise that the real difference
function signature is:
public func difference<C: BidirectionalCollection>(
from other: C,
by areEquivalent: (Element, C.Element) > Bool
) > CollectionDifference<Element>
where C.Element == Self.Element
Note how nonconstraining this function is:
all it requires is two BidirectionalCollection
s (two collections that can be traversed both by moving backward and/or forward) with the same associated types.
The associated types don’t need to conform to any specific protocol, all it matters is that we pass a method that takes two elements of this type and returns a boolean:
what this comparison method does, and what it means, is entirely up to the developer.
An Example
As a fun example, let’s run difference(from:by:)
with two identical collections and a comparison method that returns always false
:
let oldArray = ["a", "b", "c"]
let newArray = ["a", "b", "c"] // same as `oldArray`
let difference = newArray.difference(from: oldArray,
by: { _, _ in false })
// `difference` is a 6 elements collection with:
//  three removals
//  three insertions
The result is a collection with three removals and three insertions:
this is because our comparison method (which, again, returns always false
in this example) removes any connection between any element in either state, therefore the difference
algorithm will see this transition as a complete rewrite of the array, regardless of the contents of those arrays!
A Note on difference(from:by:) Return Type
difference
returns a nonoptional CollectionDifference
.
Previously I’ve mentioned that a CollectionDifference
initialization fails when we try to initialize it with elements that do not comply to its rules. How does Swift guarantees a nonoptional CollectionDifference
instance?
While Swift exposes only one failable initializer for CollectionDifference
, it turns out that there’s also a nonfailable initializer:
this second initializer is marked as internal
, therefore it can only be used within the Swift repository, and it is not exposed when we use Swift from a toolchain in Xcode.
This is because the internal initializer is used only with algorithms that have been mathematically proven to instantiate a correct CollectionDifference
, therefore it is ok for Swift to return a nonoptional collection.
Inside difference(from:by:)
The first thing that this method does is creating two collections, source
and target
, of internal type _CountingIndexCollection
:
the source
reflects the old state of the original collection, while target
reflects the new state of the original collection.
If we call ["a","b","c"].difference(from: ["e", "f", "g"])
for example, source
mirrors ["e", "f", "g"]
while target
mirrors ["a", "b", "c"]
.
_CountingIndexCollection
is a wrapper of the real collection, with an easy way to get the offset of its indices from its start index.
let originalCollection = ["a", "b", "c", "d"]
Let offsetCollection = _CountingIndexCollection(originalCollection)
if let index = offsetCollection.index(of: "d") {
print(index.offset) // prints "3"
print(offsetCollection[index]) // prints "d"
}
Lastly, the method creates an instance of internal type _CollectionChanges
, which takes the newly created source
and target
collections along with our injected comparison block.
After the _CollectionChanges
initialization is complete, the difference
method maps back the _CollectionChanges
instance into an array of Change
instances, and returns a CollectionDifference
initialized with these changes.
Therefore, the real diffing doesn’t happen in this method, but inside the _CollectionChanges
initialization:
we need to explore what this _CollectionChanges
is all about.
_CollectionChanges
_CollectionChanges
is a generic collection of changes (duh!) between a source and target collection. In the documentation it is stated that an instance of this type can be used to:

Traverse the longest common subsequence of
source
andtarget
, which means the longest subsequence common between the two collections.
For example, the longest common sequence between XMJYAUZ and MZJAWXU is MJAU:
the subsequence, as long as it is found while traversing both collections in the same direction, doesn’t have to occupy consecutive positions within the original collections. 
Traverse the shortest edit script of remove and insert operations, which means finding the minimum number of operations needed to transform the
source
collection into thetarget
.
These definitions/challenges are actually dual:
if we solve one, we’ve also found a way to solve the other as well!
Both challenges are very valuable to our diffing: since additions and removals are costly, and no change is free, solving those problems means finding the cheapest (read: fastest) way to turn our old collection state into the new collection.
Let’s take two collections for example, ABCABBA
and CBABAC
: how many ways there are to transform one into the other?
The answer is several: _CollectionChanges
promises to find the most efficient one.
Endpoint
The first declaration that we met inside the _CollectionChanges
body is a new typealias
that forms a tuple by taking one index of the source
collection and one from the target
collection:
typealias Endpoint = (x: SourceIndex, y: TargetIndex)
This is what we will use when associating two locations of the two collections:
For example, if we want to associate the first element of the source
with the second element of the target
, we will define the tuple (nee, the Endpoint
) as (1, 2)
.
PathStorage: An Hidden Swift Game 👾
Let’s assume to have a 2D chart in front of us. The Xaxis is our source
collection and our Yaxis is our target
collection.
 •  X  A  B  C  D 
•       
X       
Y       
C       
D       
You’re now tasked to draw a path that goes:
 from
(0,0)
 to
(lastIndexOfTarget, lastIndexOfSource)
 •  X  A  B  C  D 
•  S      
X        // S: Start Here
Y        // T: Target Destination
C       
D       T 
// Start Position S: (0,0)
// Target Position T: (4,5)
Rules:
 You can only advance left to right (no going back)
 You can only advance top to bottom (no going back)
 You can advance left to right and top to bottom at the same time (diagonal move) only if you advance equally in both directions
 You can advance left to right and top to bottom at the same time (diagonal move) only when the Xaxis and Yaxis elements are the same
Note: I’m using the equality as a comparison for simplicity sake, however the rules above are still applied in general sense.
The game is to find the allowed path with the most diagonal moves.
Sounds familiar? Because it is:
this game is exactly what we introduced before in _CollectionChanges
as the longest common subsequence challenge.
Finding the path with the most diagonal moves is the same as finding the longest common subsequence of our two collections, and finding the path with the most diagonal moves means finding the path with as little nondiagonal moves as possible. Nondiagonal moves correspond to a change:
 a vertical move (top to bottom) is an insertion
 while an horizontal move correspond to a deletion.
Here’s the solution of the game above:
 •  X  A  B  C  D 
•  S      
X   x  x  x    // S: Start Here
Y     x    // T: Target Destination
C      x  
D       T 
// Final path:
(0,0) → (1,1) → (1,2) → (1,3) → (2,3) → (3,4) → (4,5)
Let’s look at the moves, one by one:
 we start at
(0,0)
, nothing to see here  we first move diagonally to
(1,1)
, as both axis have the valueX
at that position  then we move horizontally to
(1,2)
, which is equivalent to removingA
 then we move horizontally to
(1,3)
, which is equivalent to removingB
 then we move vertically to
(2,3)
, which is equal to insertingY
to our collection  the we move diagonally to
(3,4)
which is allowed because we haveC
in both axis  lastly we move diagonally to
(4,5)
, which is allowed because we haveD
in both axis, arriving to our target destination.
In other words, we can use this path to find the difference operations necessary to go from target
to destination
, looking back again to the path:
 the two horizontal moves,
(1,1) → (1,2)
and(1,2) → (1,3)
, correspond to two deletions  the one vertical move,
(1,3) → (2,3)
, correspond to an insertion
Before translating those moves to an
offset
ofCollectionDifference.Change
we must remember that the indexes of this path are shifted by one, as(0,0)
is the initial position in the chart, and not the start index of each collection.
Remember our Endpoint
definition?
typealias Endpoint = (x: SourceIndex, y: TargetIndex)
The path that we have just found is just an array of endpoints:
the second declaration that we find in _CollectionChanges
is PathStorage
: which is where we store this path.
pathStartIndex
Our final property found inside _CollectionChanges
is pathStartIndex
, which is the index in pathStorage
of the first segment in the difference path.
This is an internal optimization:
if two collections have the same prefix, like AEOS and AEFT, it’s no use to start doing our diffing in the common prefix AE, therefore we skip it and do all our diffing operations starting from the pathStartIndex
instead.
enum Element
This is an internal
enum declaration that will help us when we need to transform the path found above into a CollectionDifference.Change
instance:
enum Element {
case removed(Range<SourceIndex>)
case inserted(Range<TargetIndex>)
case matched(Range<SourceIndex>, Range<TargetIndex>)
}
Note how the associated values of each case is a range instead of a simple index:
while in the example above we’ve separated each move to one step, multiple consecutive moves in the same direction can be grouped together into one move, therefore moves like our two horizontal moves (1,1) → (1,2) → (1,3)
can be grouped into one as (1,1) → (1,3)
, therefore we can describe our path succinctly, and this contraction allows us to use ranges.
If you recall were we started, we’ve said that our diffing method initializes a _CollectionChanges
instance:
After the
_CollectionChanges
initialization is complete, thedifference
method maps back the_CollectionChanges
instance into an array ofChange
instances, and returns aCollectionDifference
initialized with these changes.
This Element
definition is exactly what _CollectionChanges
is a collection of, therefore what our original difference
method does is take these Element
instances and, one by one, turn them into Change
s (while ignoring all the matches).
We’ve covered the basics: it’s time to look at the _CollectionChanges
initialization.
_CollectionChanges Main init
As a reminder, this
init
has three parameters: our two collection states and the comparison method.
This init does two things:
 initialize the
pathStartIndex
with value0
and thePathStorage
array to an empty array  call a
private
methodformChanges
while passing to it all theinit
parameters.
_CollectionChanges formChanges
As a reminder, what we want to do now is filling the
_CollectionChanges
’sPathStorage
(which is an array ofEndpoint
s, which correspond to our path as we’ve seen above).
Once called, this method does some initial checks.
If both collection states are empty (e.g. we’re comparing two empty arrays), this method stops immediately: the difference is empty as there’s nothing to compare.
If we continue, it means that at least one of the collection states is not empty.
This is the point where our method finds the common prefix among the collection states (according to our comparison method):

if the common prefix is equal to at least one of the two collections, then the change between the two collections is trivial:
going back to our path game, having a collection equal to the prefix of the other means that we can use diagonal moves until we hit one of the edges. Once we hit the edge, we are only allowed to move either by going down (insertions) or right (deletions).
Here are three examples where the collections are one the prefix of the other.// source = ASDFO // target = ASD // the target is a prefix of the source:  •  A  S  D  F  O  •  S       A   x      // S: Start Here S    x     // T: Target Destination D     x  x  T  ↑ we hit the edge here // Final path: (0,0) → (3,3) → (3,5) // Which translates into: //  three matches (0,0) → (3,3) //  two deletions (of letter F, and O), (3,3) → (3,5) // source = ASD // target = ASDFO // the source is a prefix of the target:  •  A  S  D  •  S     // S: Start Here A   x    // T: Target Destination S    x   D     x  ← we hit the edge here F     x  O     x  // Final path: (0,0) → (3,3) → (5,3) // Which translates into: //  three matches (0,0) → (3,3) //  two insertions (of letter F, and O), (3,3) → (5,3) // source = ASD // target = ASD // both collections are equal, therefore they are each other's prefixes  •  A  S  D  •  S     // S: Start Here A   x    // T: Target Destination S    x   D     T  ← we hit the edge here // Final path: (0,0) → (3,3) // Which translates into: //  three matches (0,0) → (3,3)
Once again I’m using the equality as a comparison for simplicity sake.
Based on which of the three cases we fall into, our final
pathStorage
will have two or three elements (endpoints) and the method returns. 
Lastly, if we arrive here, it means that our collection states are:
 Not the same (according to our comparison method)
 Not empty
 Might have a common prefix
This is when our method
formChanges
calls another method,formChangesCore
.
_CollectionChanges formChangesCore
Remember what we are accomplishing:
we are trying to find the most efficient way to go from one collection state to another, by using as little insertions/deletions as possible, while reusing thesource
collection elements as much as possible (a.k.a. finding the path with the the most diagonal moves in our path game).
This method is invoked with a few parameters: the usual original collections and comparison method, plus the end indexes on each collection of their common prefix (that we have just computed above).
Since we’ve already got rid of the base cases, this method is (finally!) where the magic happens.
To put it simply, this method implements the “Greedy LCS/SES Algorithm” published in 1986 (!) by Eugene W. Myers.
The Greedy LCS/SES Algorithm
Curious on which algorithm IGListKit uses? Check out Paul Heckel’s paper here. Here’s a Swift implementation of said algorithm.
Without going too deeply on the theory behind the algorithm, which is explained and demonstrated very clearly in the original paper (approachable by everyone), the algorithm is based on three steps:

Find the furthest valid path that starts at
(0,0)
and has up toD
nondiagonal moves. 
If we’ve reached the Target Destination, end the algorithm.

If not, increase
D
by one (initially set to0
) and start again.
In order to get to the Target Destination, instead of computing over and over all the possible valid paths with D
nondiagonal moves, the algorithm stores the previous explored paths.
However, not all possible paths are stored, nor all the possible paths are explored.
Instead, the algorithm bases its research for the best path on the diagonals of our 2D chart game, these diagonals are defined as k = x  y
. Here are a few examples:
diagonal with k = 0 diagonal with k = 1 diagonal with k = 2
 •  A  S  D   •  A  S  D   •  A  S  D 
•  k     •   k    •    k  
A   k    A    k   A     k 
S    k   S     k  S     
D     k  D      D     
F      F      F     
O      O      O     
diagonal with k = 1 diagonal with k = 2 diagonal with k = 3
 •  A  S  D   •  A  S  D   •  A  S  D 
•      •      •     
A  k     A      A     
S   k    S  k     S     
D    k   D   k    D  k    
F     k  F    k   F   k   
O      O     k  O    k  
Here are the first few iterations of the algorithm:

Initially, the algorithm starts at
(0,0)
and finds the furthest path with0
non diagonal moves, which will necessarily end its path in the 0th diagonal (k = 0
). 
On the first iteration (if we haven’t reached the Target Destination yet), we try to find the furthest paths that have
1
non diagonal moves, starting from where we left in the previous found path. We will necessarily end up on a diagonal with k equal to 1 or 1 (remember, by moving to the diagonal withk = 1
it means that we do an insertion, dually, we perform a removal by moving into the diagonal withk = 1
).
Assuming that we haven’t arrived to the final destination yet, we have 2 potential paths now: one that ends in diagonal 1 and one in diagonal 1. We keep both and keep iterating. 
On the next iteration we will try to find the furthest path with
2
non diagonal moves, instead of starting from scratch, again, we use the two potential paths from the previous iteration. Starting from the previous two potential paths that ended in diagonal 1 and 1, this iteration paths will necessarily end in either diagonal 2, 0, or 2.
If we haven’t found the Target Destination yet, we keep the furthest path on each diagonal (three in total) and keep iterating.
Would you like to see this process in action? Robert Elder has an interactive Visualization here (jump to step 5!)
This iteration keeps going until we finally reach the Target Point.
A few important observations:

a path at a given iteration with “x” nondiagonal moves is just a path from the previous iteration, with “x1” moves, and an extra non diagonal move (and potentially multiple diagonal moves).
 we grow the number of potential paths by one at every iteration:
 we start with one (that lies at diagonal 0)
 then we grow to 2 (one that lies at diagonal 1, one at diagonal 1)
 then 3 (diagonals 2, 0, 2)
 etcetera

at a given iteration D, all the recorded path will end in one of the following diagonals: { −D, −D+2, … D−2, D }.
 we start with one path that lays at diagonal 0 (iteration D = 0 > diagonals {0})
 at the first iteration we have two paths, one at diagonal 1, one at diagonal 1 (iteration D = 1 > diagonals {1, 1})
 at the next iteration we have three paths, one at diagonal 2, one at diagonal 0, one at diagonal 2 (iteration D = 2 > diagonals {2, 0, 2})
 etcetera
We’re basically alternating diagonals (while also expanding at each iteration).
All these observations are demonstrated in the original paper.
That’s the whole algorithm! Let’s see how to implement it in Swift.
The Greedy LCS/SES Algorithm in Swift
Since formChanges
passes the computed end indexes of the common prefix of our two collection states, the first iteration has been done already:
computing the common prefix of the two collections is equivalent to finding the furthest path with 0
non diagonal moves.
All we have to do now is to store this first path somewhere.
_SearchState
As we’ve observed during the explanation of the algorithm, at every interation we increase the potential paths by one, and one potential path at a given iteration is exactly a potential path from the previous interation with one extra nondiagonal move.
Therefore we can describe each potential path by pointing at its last move, which is an Endpoint
instance as we’ve defined before, and then refer to its previous path from the previous iteration.
This is exactly what the private _SearchState
generic struct does.
This struct relies on an internal generic storage called _LowerTriangularMatrix
:
by definition, a square matrix is called lower triangular if all the entries above the main diagonal are zero.
Example:
 *  0  0  0 
 *  *  0  0 
 *  *  *  0 
 *  *  *  * 
In order to optimize perfomance and allocation, this _LowerTriangularMatrix
externally behaves like a real lower triangular matrix (with subscript and all), however internally is just an array of elements along with a dimension
property (this is all this type needs to mirror a real lower triangular matrix).
Going back to _SearchState
, the struct considers every row of its storage (which, again, is a lower triangular matrix) as the search frontier of each iteration, while the columns represent the furthest path on the xth diagonal for that search frontier.
In other words:
 the position
(0,0)
in the storage contains the final position of our furthest path with0
nondiagonal moves starting at(0,0)
in our game chart.  the positions
(1,0)
and(1,1)
in the storage contain the furthest paths with1
nondiagonal moves, the former contains the one that ends in diagonal 1, while the latter contains the one that ends in diagonal 1.  etcetera
The Algorithm
Finally let’s take a look at the algorithm.
Each line comes with extended explanation, to associate everything with what we’ve discussed so far.
private mutating func formChangesCore<Source: BidirectionalCollection,
Target: BidirectionalCollection>(
from a: Source, to b: Target,
x: Source.Index, y: Target.Index,
by areEquivalent: (Source.Element, Target.Element) > Bool
) where
Source.Element == Target.Element, Source.Index == SourceIndex,
Target.Index == TargetIndex
{
// current furtherst position coordinate,
// according to our collection common prefix.
// a.k.a. the furthest path with `0` nondiagonal moves
var (x, y) = (x, y)
// our Target Destination coordinates
let (n, m) = (a.endIndex, b.endIndex)
// initialize the storage
var v = _SearchState<Source.Index, Target.Index>(consuming: &pathStorage)
// put the end of the common prefix endpoint
// at position `(0,0)` of our storage
v.appendFrontier(repeating: (x, y))
// set the iteration number
var d = 1
// used later
var delta = 0
// iteration body
outer: while true {
// expand our storage to contain a new row of _search frontier_
// a.k.a. the furthest paths endpoints of the `d`th iteration
v.appendFrontier(repeating: (n, m))
// one of the observations of the algorithm was about the fact
// that at a given iteration D, all the furthest paths would
// lie at the diagonals { D, D + 2, ... D 2, D }
// This observation explains the following stride
for k in stride(from: d, through: d, by: 2) {
// if we're finding the leftmost new path, a.k.a. the one with
// diagonal d, or if we're finding the new furthest path at a
// diagonal kth, which is not the right most new diagonal,
// a.k.a. k == t, and if the furthest path in diagonal k1 has
// traveled our `target` collection less than or furthest path
// in diagonal k+1 in our previous iteration...
if k == d  (k != d && v[d  1, k  1].x < v[d  1, k + 1].x) {
// ...then we start computing our new furthest path by
// reading the previous iteration furthest path at diagonal
// k+1
(x, y) = v[d  1, k + 1]
// if we are not at the edge, move down by one
if y != m { b.formIndex(after: &y) }
} else {
// like above, but this time we use the previous iteration
// furthest path at diagonal k1
(x, y) = v[d  1, k  1]
// if we are not at the edge, move right by one
if x != n { a.formIndex(after: &x) }
}
// with the if/else above we have just "used" our nondiagonal
// move of this iteration
// now that we've moved either down or right by one, check if
// we can move diagonally, and do it as long as you can.
// find the common prefix, according to our comparison method,
// from the current position in the two collection states
let matches = a[x..<n]._commonPrefix(with: b[y..<m],
by: areEquivalent)
// our new furthest path at the *d*th iteration for diagonal
// *k*th is equivalent to the end of the prefix that we've
// just found
(x, y) = (matches.0.endIndex, matches.1.endIndex)
// store the new endpoint
v[d, k] = (x, y)
// if this new endpoint matches the target destination...
if x == n && y == m {
// ...note down at which diagonal we've stopped at..
delta = k
// ...and end the algorithm.
break outer
}
}
// if we haven't found found the target destination yet,
// increase the depth by one and iterate again.
d += 1
}
// after finding the cheapest path at the *d*th iteration, on
// the *delta*th diagonal, convert our `_SearchState` instance
// storage into the final `_CollectionChanges` instance.
self = v.removeCollectionChanges(a: a, b: b, d: d, delta: delta)
}
Conclusions
There you have it: if you’ve come so far, congratulations! You now know exactly how Swift implements the diffing between two collections.
It took us a long journey to arrive here, however, for something nontrivial and errorprone like collection diffing, it’s very good to have a native, efficient solution implemented right into the language itself.
Lastly, if you are an iOS or mac developer, I would like to remind you that you shouldn’t use this in collection and table views:
with the upcoming iOS and macOS releases, we will have an even better API that takes care of diffing and more for us.
You can watch and hear all about Collection and Table Diffable Data Sources in the WWDC19 session here, or, if you prefer an article form, you can read about them in John Sundell’s article here.
Thank you for reading and stay tuned for more articles!
References
 The original pitch.
 The Swift Evolution proposal.
 The proposal review thread.
 The Swift implementation here and here.