-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathhow-collection-diffing-works-internally-in-swift.html
474 lines (409 loc) · 29.7 KB
/
how-collection-diffing-works-internally-in-swift.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
<!DOCTYPE html>
<html lang="en">
<head>
<script src="https://use.fontawesome.com/afd448ce82.js"></script>
<!-- Meta Tag -->
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<!-- SEO -->
<meta name="author" content="Bruno Rocha">
<meta name="keywords" content="Software, Engineering, Blog, Posts, iOS, Xcode, Swift, Articles, Tutorials, OBJ-C, Objective-C, Apple">
<meta name="description" content="Ordered Collection Diffing is a feature added in Swift 5.1 that allows you to calculate and apply the difference between two collections. Using diffing libraries is common in iOS for a few reasons, the most popular one being to handle the addition and removal of elements in UITableViews. With the addition of this feature, developers can now diff Collections without having to bother with external libraries. Have you wondered what efficiently diffing something looks like? In this article, we'll see and analyze the diffing APIs as well as the diffing algorithm used by the Swift Standard Library.">
<meta name="title" content="How Collection Diffing works in Swift">
<meta name="url" content="https://swiftrocks.com/how-collection-diffing-works-internally-in-swift">
<meta name="image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4">
<meta name="copyright" content="Bruno Rocha">
<meta name="robots" content="index,follow">
<meta property="og:title" content="How Collection Diffing works in Swift"/>
<meta property="og:image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4"/>
<meta property="og:description" content="Ordered Collection Diffing is a feature added in Swift 5.1 that allows you to calculate and apply the difference between two collections. Using diffing libraries is common in iOS for a few reasons, the most popular one being to handle the addition and removal of elements in UITableViews. With the addition of this feature, developers can now diff Collections without having to bother with external libraries. Have you wondered what efficiently diffing something looks like? In this article, we'll see and analyze the diffing APIs as well as the diffing algorithm used by the Swift Standard Library."/>
<meta property="og:type" content="website"/>
<meta property="og:url" content="https://swiftrocks.com/how-collection-diffing-works-internally-in-swift"/>
<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4"/>
<meta name="twitter:image:alt" content="Page Thumbnail"/>
<meta name="twitter:title" content="How Collection Diffing works in Swift"/>
<meta name="twitter:description" content="Ordered Collection Diffing is a feature added in Swift 5.1 that allows you to calculate and apply the difference between two collections. Using diffing libraries is common in iOS for a few reasons, the most popular one being to handle the addition and removal of elements in UITableViews. With the addition of this feature, developers can now diff Collections without having to bother with external libraries. Have you wondered what efficiently diffing something looks like? In this article, we'll see and analyze the diffing APIs as well as the diffing algorithm used by the Swift Standard Library."/>
<meta name="twitter:site" content="@rockbruno_"/>
<!-- Favicon -->
<link rel="icon" type="image/png" href="images/favicon/iconsmall2.png" sizes="32x32" />
<link rel="apple-touch-icon" href="images/favicon/iconsmall2.png">
<link rel="preconnect" href="https://fonts.googleapis.com">
<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
<link href="https://fonts.googleapis.com/css2?family=Source+Sans+3:ital,wght@0,200..900;1,200..900&display=swap" rel="stylesheet">
<!-- Bootstrap CSS Plugins -->
<link rel="stylesheet" type="text/css" href="css/bootstrap.css">
<!-- Prism CSS Stylesheet -->
<link rel="stylesheet" type="text/css" href="css/prism4.css">
<!-- Main CSS Stylesheet -->
<link rel="stylesheet" type="text/css" href="css/style48.css">
<link rel="stylesheet" type="text/css" href="css/sponsor4.css">
<!-- HTML5 shiv and Respond.js support IE8 or Older for HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/html5shiv/3.7.3/html5shiv.min.js"></script>
<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
<![endif]-->
<script type="application/ld+json">
{
"@context": "https://schema.org",
"@type": "BlogPosting",
"mainEntityOfPage": {
"@type": "WebPage",
"@id": "https://swiftrocks.com/how-collection-diffing-works-internally-in-swift"
},
"image": [
"https://swiftrocks.com/images/thumbs/thumb.jpg"
],
"datePublished": "2020-03-18T07:25:00+00:00",
"dateModified": "2020-04-12T14:00:00+02:00",
"author": {
"@type": "Person",
"name": "Bruno Rocha"
},
"publisher": {
"@type": "Organization",
"name": "SwiftRocks",
"logo": {
"@type": "ImageObject",
"url": "https://swiftrocks.com/images/thumbs/thumb.jpg"
}
},
"headline": "How Collection Diffing works in Swift",
"abstract": "Ordered Collection Diffing is a feature added in Swift 5.1 that allows you to calculate and apply the difference between two collections. Using diffing libraries is common in iOS for a few reasons, the most popular one being to handle the addition and removal of elements in UITableViews. With the addition of this feature, developers can now diff Collections without having to bother with external libraries. Have you wondered what efficiently diffing something looks like? In this article, we'll see and analyze the diffing APIs as well as the diffing algorithm used by the Swift Standard Library."
}
</script>
</head>
<body>
<div id="main">
<!-- Blog Header -->
<!-- Blog Post (Right Sidebar) Start -->
<div class="container">
<div class="col-xs-12">
<div class="page-body">
<div class="row">
<div><a href="https://swiftrocks.com">
<img id="logo" class="logo" alt="SwiftRocks" src="images/bg/logo2light.png">
</a>
<div class="menu-large">
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-large">
<div class="menu-item">
<a href="blog">blog</a>
</div>
<div class="menu-item">
<a href="about">about</a>
</div>
<div class="menu-item">
<a href="talks">talks</a>
</div>
<div class="menu-item">
<a href="projects">projects</a>
</div>
<div class="menu-item">
<a href="software-engineering-book-recommendations">book recs</a>
</div>
<div class="menu-item">
<a href="games">game recs</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
</div>
<div class="menu-small">
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-small-1">
<div class="menu-item">
<a href="blog">blog</a>
</div>
<div class="menu-item">
<a href="about">about</a>
</div>
<div class="menu-item">
<a href="talks">talks</a>
</div>
<div class="menu-item">
<a href="projects">projects</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-small-2">
<div class="menu-item">
<a href="software-engineering-book-recommendations">book recs</a>
</div>
<div class="menu-item">
<a href="games">game recs</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
</div>
</div>
<div class="content-page" id="WRITEIT_DYNAMIC_CONTENT">
<!--WRITEIT_POST_NAME=How Collection Diffing works in Swift-->
<!--WRITEIT_POST_HTML_NAME=how-collection-diffing-works-internally-in-swift-->
<!--WRITEIT_POST_SITEMAP_DATE_LAST_MOD=2020-04-12T14:00:00+02:00-->
<!--WRITEIT_POST_SITEMAP_DATE=2020-03-18T07:25:00+00:00-->
<!--Add here the additional properties that you want each page to possess.-->
<!--These properties can be used to change content in the template page or in the page itself as shown here.-->
<!--Properties must start with 'WRITEIT_POST'.-->
<!--Writeit provides and injects WRITEIT_POST_NAME and WRITEIT_POST_HTML_NAME by default.-->
<!--WRITEIT_POST_SHORT_DESCRIPTION=Ordered Collection Diffing is a feature added in Swift 5.1 that allows you to calculate and apply the difference between two collections. Using diffing libraries is common in iOS for a few reasons, the most popular one being to handle the addition and removal of elements in UITableViews. With the addition of this feature, developers can now diff Collections without having to bother with external libraries. Have you wondered what efficiently diffing something looks like? In this article, we'll see and analyze the diffing APIs as well as the diffing algorithm used by the Swift Standard Library.-->
<title>How Collection Diffing works in Swift</title>
<div class="blog-post">
<div class="post-title-index">
<h1>How Collection Diffing works in Swift</h1>
</div>
<div class="post-info">
<div class="post-info-text">
Published on 18 Mar 2020
</div>
</div>
<p><b>Ordered Collection Diffing</b> is a feature added in Swift 5.1 that allows you to calculate and apply the difference between two collections. Using diffing libraries is common in iOS for a few reasons, the most popular one being to handle the addition and removal of elements in <code>UITableViews</code>. With the addition of this feature, developers can now diff <code>Collections</code> without having to bother with external libraries.</p>
<div class="sponsor-article-ad-auto hidden"></div>
<p>Have you wondered what efficiently diffing something looks like? In this article, we'll see and analyze the diffing APIs as well as the <b>Myers's Diffing Algorithm</b> used by the Swift Standard Library -- the same used in <b>git</b>.</p>
<h2>Collection Diffing APIs</h2>
<p>The diffing APIs are available as an extension for any <code>BidirectionalCollection</code>, with an abstracted helper type for ones whose's elements are <code>Equatable</code>:</p>
<pre><code>extension BidirectionalCollection {
public func difference<C: BidirectionalCollection>(
from other: C,
by areEquivalent: (C.Element, Element) -> Bool
) -> CollectionDifference<Element>
where C.Element == Self.Element {
return ... // Article spoilers removed!
}
}</code></pre>
<pre><code>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: ==)
}
}</code></pre>
<p>The return type for diffing operations is an <code>CollectionDifference</code> object -- basically an array of "moves" necessary to turn the first collection into the second one. The "moves" are represented as an enum of additions and removals, and the <code>CollectionDifference</code> object holds all of them.</p>
<pre><code>public struct CollectionDifference<ChangeElement> {
/// A single change to a collection.
@frozen
public enum Change {
case insert(offset: Int, element: ChangeElement, associatedWith: Int?)
case remove(offset: Int, element: ChangeElement, associatedWith: Int?)
}
public let insertions: [Change]
public let removals: [Change]
}</code></pre>
<p><code>CollectionDifference</code> is a <code>Collection</code> itself, which means that it can be iterated. <b>An important aspect of this is that the iteration will happen in a specific order: First, all the removals from highest to lowest offset, followed by insertions from lowest to highest.</b> This is both for performance reasons (removing elements from the end of an array is faster from the beginning, and adding elements to the front when there are fewer elements is faster than when there's a lot), and for visual reasons as we'll see when the underlying algorithm is inspected.</p>
<p>We can see this behavior with a real example. Let's calculate the difference between these two strings:</p>
<pre><code>let a = "ABCABBA"
let b = "CBABAC"</code></pre>
<p>There are tons of ways of transforming <code>a</code> into <code>b</code>, but our interest is doing so in the least amount of steps. When calling <code>difference(_:)</code> and iterating the result, we'll see one of these solutions:</p>
<pre><code>let diff = b.difference(from: a)
diff.forEach { print($0) }
// remove(offset: 5, element: "B", associatedWith: nil)
// remove(offset: 1, element: "B", associatedWith: nil)
// remove(offset: 0, element: "A", associatedWith: nil)
// insert(offset: 1, element: "B", associatedWith: nil)
// insert(offset: 5, element: "C", associatedWith: nil)</code></pre>
<p>(We'll leave the explanation of the algorithm itself for the last section because it's a bit complicated.)</p>
<p>From here, you can use the resulting <code>CollectionDifference</code> object as you see fit, like animating the addition and removal of rows from an <code>UITableView</code>. The neat thing is that Swift provides an <code>applying(_:)</code> method that allows you to directly apply a <code>CollectionDifference</code> object into a <code>Collection</code>:</p>
<pre><code>let newB = a.applying(diff)
//CBABAC</code></pre>
<p>This particular example looks useless, so here's something where applying diffs is useful: The same three-way merge process that <b>git</b> uses as a strategy to merge commits!</p>
<pre><code>// Split the contents of the sources into lines
let baseLines = base.components(separatedBy: "\n")
let theirLines = theirs.components(separatedBy: "\n")
let myLines = mine.components(separatedBy: "\n")
// Create a difference from base to theirs
let diff = theirLines.difference(from:baseLines)
// Apply it to mine, if possible
guard let patchedLines = myLines.applying(diff) else {
print("Merge conflict applying patch, manual merge required")
return
}
// Reassemble the result
let patched = patchedLines.joined(separator: "\n")
print(patched)</code></pre>
<h2>How applying() works</h2>
<p>The <code>applying(_:)</code> method works by creating a new, empty <code>Collection</code> instance that gets filled as the changes are iterated. Because the changes are iterated in the specific high removals -> low removals -> low insertions -> high insertions, the algorithm is able to build the final result through ranges instead of individual elements. For example, if you have a 10 character string and the first step is to remove the 5th character, we know right off the bat that the final result will contain the range <code>5...9</code> in that same order, so "removing the 5th character" is equivalent to adding everything that comes after it. The same logic is applied until all the changes are processed. Because of the interaction with ranges, <code>applying(_:)</code> is only available to <code>RangeReplaceableCollections</code>.</p>
<p>It is possible for this process to fail, for example, when the desired element to be removed doesn't exist, which is possible in cases like the <b>git</b> example due to conflicting information in the data. In these cases, <code>applying(_:)</code> returns <code>nil</code>.</p>
<p>The actual method is a bit long and hard to read, <a href="https://github.com/apple/swift/blob/master/stdlib/public/core/Diffing.swift#L71">so I'll leave the link to it</a> instead of showing it here.</p>
<h2>The complex part: How difference() works</h2>
<p>Now that we've seen how the APIs work, we're ready to take a look at what Swift does to generate the final <code>CollectionDifference</code> object.</p>
<p>As stated before, there are many ways to transform a <code>Collection</code> into another one. For example, to transform <code>a: ABCABBA</code> to <code>b: CBABAC</code>, we could simply remove every single element from <code>a</code> and append the ones from <code>b</code>. Easy peasy!</p>
<p>However, at a best case of <code>a.count + b.count</code> "moves", that would be very inefficient. One way to find the best way possible to do this change is to transform this into a <b>graph problem</b>. Imagine that we have a <b>matrix</b> where the columns are characters from <code>a</code> and rows are characters from <code>b</code>:</p>
<pre><code>- A B C A B B A
-
C
B
A
B
A
C</code></pre>
<p>In this matrix, the top-left position 0,0 represents the original <code>ABCABBA</code> string, while the bottom-right position represents the final <code>CBABAC</code> string. Moving <b>right</b> in this matrix represents <b>removing</b> an element from the original string, while moving <b>down</b> represents <b>adding</b> an element from the new one. Each of these movements counts as a step, but if the elements from both strings at a specific position <b>match</b> (like the position 1,3 - two Cs), you can <b>diagonally move down and to the right</b> for "free", as no changes are necessary for that position.</p>
<p>Given this description, we can transform this problem into another one: <b>How can we reach the bottom right of the matrix in the least amount of steps (a.k.a maximizing the number of diagonal moves)?</b></p>
<p>If you ever studied graphs you might remember that finding the shortest path between two nodes in an unweighted graph is a classical computer science problem! This problem is solved by the popular graph search algorithm <a href="https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/">Breadth-First Search</a> -- because the graph is unweighted, taking turns on checking the neighbors of each node is guaranteed to discover the shortest path between a source node to a target one. Applying the algorithm in the previous example will show us a path that transforms our string in <b>5</b> moves (remember that diagonal moves do not count as moves):</p>
<pre><code>- A B C A B B A
- 0 1 2
C 2 3
B 3
A 4
B 4
A 4
C 5</code></pre>
<p>The implementation behind the true diffing algorithms is very similar to this, but with a few (unfortunately, relatively complicated) important twists. Although we're looking for the shortest edit path between two <code>Collections</code>, we're not exactly looking for <b>any</b> short path. Especially for visual applications like <b>git</b>, the overall order of how deletions and insertions are present is important. When you're looking at the merge diff in git, you would expect the diff to be somewhat "intelligent" in terms of knowing what was really added and deleted by your changes instead of randomly saying that things were "added" and "deleted" because it fulfills the shortest path condition.</p>
<pre><code>Good: class Foo { Bad: class Foo {
init(bar: String) { init(bar: String) {
self.bar = bar self.bar = bar
} + }
+ +
+ func inspect() { + func inspect() {
+ print(bar) + print(bar)
+ } }
} }</code></pre>
<p>Diffing algorithms carefully choose the paths that Breadth-First Search is going to traverse in order to provide a meaningful diff.</p>
<h2>Swift's Diffing Algorithm: Myers's Diffing Algorithm</h2>
<p>Swift uses Myers's Diffing Algorithm <a href="http://www.xmailserver.org/diff2.pdf">(paper here)</a> as part of the diffing APIs. Given two collections, the result is the <b>Shortest Edit Script</b> that transforms A into B. Much like the abstracted <code>CollectionDifference</code> type, the Shortest Edit Script is a list of additions and removals. In order to provide a good diff, Myers's prefers deleting over inserting, and it differs from Breadth-First Search by prioritizing what seems to be "good" paths instead of blindly switching nodes like the original algorithm.</p>
<p>This is done by adding two additional components to the matrix: How <b>deep</b> we are into the graph (number of moves, in the X-axis), and the <b>ratio</b> of additions versus deletions, which is a value <b>k</b> that increases by one every time we remove a value (moving right), and decreases by one every time we add a value (moving down), in the Y-axis. This is better seen if we shift a graph by 45 degrees (note that this graph doesn't contain the diagonal connections that make the paths shorter):</p>
<pre><code>| 0 1 2 3 4 5
+--------------------------------------
5 | 5,0
| /
4 | 4,0
| / \
3 | 3,0 4,1
| / \ /
2 | 2,0 3,1
| / \ / \
1 | 1,0 2,1 3,2
| / \ / \ / ...
0 | 0,0 1,1 2,2
| \ / \ / \
-1 | 0,1 1,2 2,3
| \ / \ /
-2 | 0,2 1,3
| \ / \
-3 | 0,3 ... 1,4</code></pre>
<p>To find the perfect path, the algorithm iterates the possible <b>depth</b> values. For each <b>depth</b>, it iterates the possible <b>k values</b> at that depth (<code>-d...d</code>) and determines the best move it can make at that point for that <b>k value</b>.</p>
<p>The best move is determined based on a few rules we'll see soon, but the important part here is that this is done based on the decisions made on the previous depth iteration. To make the current iteration not mess with the previous moves, the <b>k values</b> are iterated in steps of 2.</p>
<pre><code>var result = [KValues]()
var currentKValues = KValues()
currentKValues[1] = 0 // Ignore this for now, explained later!
outer: for d in 0...(a.count + b.count) {
result.append(currentKValues)
let previousKValues = currentKValues
currentKValues = KValues()
for k in stride(from: -d, through: d, by: 2)
// Determine the best moves for the current K values
}
}
return backtrackPath(fromKValues: result) // Additions and Deletions</code></pre>
<p>"Determining" the best move means deciding to go right or down from the positions recorded in the previous depth iteration. We should always move right if <code>k == -d</code> (bottom of the currently "accessible" graph), and always down if <code>k == +d</code> (right edge of the currently "accessible" graph). Otherwise, we should pick the position based on the current adjacent k's best values that leads us to the highest x value -- this way, we prioritize deletion.</p>
<pre><code>let currX: Int
if k == -d {
currX = previousKValues[k+1] // Moving down
} else if k == d {
currX = previousKValues[k-1] + 1 // Moving to the right
} else if previousKValues[k-1] < previousKValues[k+1] {
currX = previousKValues[k+1] // Moving down
} else {
currX = previousKValues[k-1] + 1 // Moving to the right
}
let currY = currX - k</code></pre>
<p>This loop is the reason why we need to start the algorithm with the <code>1</code> <b>k value</b> set to 0. This makes sure that the first iteration determines that the "first best move" is to go down to 0,0 -- the beginning of the graph. This allows everything else to proceed as normal.</p>
<p>Once the best move is found, we try to move diagonally as much as we can to claim our free steps.</p>
<pre><code>while currX < a.count && currY < b.count {
if a[currX] == b[currY] {
break
}
x &+= 1
y &+= 1
}</code></pre>
<p>Finally, we store the best X value we've found for the current <b>k value</b> and halt the algorithm if we've reached the bottom right. Note how we only store X: Because <b>k</b> is a ratio of X and Y, we can infer Y from it and thus do not need to store Y.</p>
<pre><code>currentKValues[k] = currX
if currX >= a.count && currY >= b.count {
break outer
}</code></pre>
<p>You might wonder how subscripting <code>currentKValues</code> works if k can be negative -- the Standard Library <a href="https://github.com/apple/swift/blob/9de3db97bdbabc503a2445ceb2f6699755aace23/stdlib/public/core/Diffing.swift#L189">created a custom type</a> that translates such negative indexes into positive ones. The idea is to create an array long enough to fit both positive and negative values and treat the indexes inside.</p>
<p><a href="https://github.com/apple/swift/blob/9de3db97bdbabc503a2445ceb2f6699755aace23/stdlib/public/core/Diffing.swift#L228">The complete algorithm from Swift can be found here.</a></p>
<p>The result of this implementation of Myers's is an array representing how far each <b>k value</b> has traveled in the X-axis in a specific depth. To get the actual path, all we have to do is backtrack from the only <b>k value</b> that has reached the maximum depth. This is done through a similar loop: For each current value, move up or to the left based on who has the largest X value in the previous iteration of the original method. Here's how this is implemented in the Standard Library (with <code>_V</code> being their version of my <code>KValues</code> type):</p>
<pre><code>// Backtrack through the trace generated by the Myers descent to produce the changes that make up the diff
func _formChanges(
from a: UnsafeBufferPointer<C.Element>,
to b: UnsafeBufferPointer<C.Element>,
using trace: [_V]
) -> [CollectionDifference<C.Element>.Change] {
var changes = [CollectionDifference<C.Element>.Change]()
changes.reserveCapacity(trace.count)
var x = a.count
var y = b.count
for d in stride(from: trace.count &- 1, to: 0, by: -1) {
let v = trace[d]
let k = x &- y
let prev_k = (k == -d || (k != d && v[k &- 1] < v[k &+ 1])) ? k &+ 1 : k &- 1
let prev_x = v[prev_k]
let prev_y = prev_x &- prev_k
while x > prev_x && y > prev_y {
// No change at this position.
x &-= 1
y &-= 1
}
if y != prev_y {
changes.append(.insert(offset: prev_y, element: b[prev_y], associatedWith: nil))
} else {
changes.append(.remove(offset: prev_x, element: a[prev_x], associatedWith: nil))
}
x = prev_x
y = prev_y
}
return changes
}</code></pre>
<div class="sponsor-article-ad-auto hidden"></div>
<p>Now that we have the final <code>CollectionDifference</code> type, we can finally return it and conclude the diffing algorithm. The worst case for Myers's is <code>O(a * b)</code> as it is possible for us to traverse all of the nodes of the graph.</p>
<h2>Conclusion</h2>
<p>As always, I like to finish these by saying that knowing what's inside of what you're using allows you to make better decisions in code. Different algorithms are meant for different use-cases, and knowing how to make trade-offs is useful everywhere. Plus, you get to learn cool little pieces of trivia -- did you know that Myers's is one of the merging strategies in <b>git</b>? :)</p>
<h2>References and Good Reads</h2>
<a href="http://www.xmailserver.org/diff2.pdf">Myers's Paper</a>
<br>
<a href="https://github.com/apple/swift/blob/master/stdlib/public/core/Diffing.swift">Diffing.swift</a>
<br>
<a href="https://github.com/apple/swift/blob/master/stdlib/public/core/CollectionDifference.swift">CollectionDifference.swift</a>
<br>
<a href="https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/">The Myers Diff Algorithm Explanation - Great read!</a>
<br>
</div></div>
<div class="blog-post footer-main">
<div class="footer-logos">
<a href="https://swiftrocks.com/rss.xml"><i class="fa fa-rss"></i></a>
<a href="https://twitter.com/rockbruno_"><i class="fa fa-twitter"></i></a>
<a href="https://github.com/rockbruno"><i class="fa fa-github"></i></a>
</div>
<div class="footer-text">
© 2025 Bruno Rocha
</div>
<div class="footer-text">
<p><a href="https://swiftrocks.com">Home</a> / <a href="blog">See all posts</a></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<!-- Blog Post (Right Sidebar) End -->
</div>
</div>
</div>
<!-- All Javascript Plugins -->
<script type="text/javascript" src="js/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/bootstrap@5.0.2/dist/js/bootstrap.bundle.min.js" integrity="sha384-MrcW6ZMFYlzcLA8Nl+NtUVF0sA7MsXsP1UyJoMp4YLEuNSfAP+JcXn/tWtIaxVXM" crossorigin="anonymous"></script>
<script type="text/javascript" src="js/prism4.js"></script>
<!-- Main Javascript File -->
<script type="text/javascript" src="js/scripts30.js"></script>
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-H8KZTWSQ1R"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-H8KZTWSQ1R');
</script>
</body>
</html>