tonyarnold/differ

Swift library to generate differences and patches between collections.

Differ

Differ generates the differences between Collection instances (this includes Strings!).

It uses a fast algorithm (O((N+M)*D)) to do this.

Features

• ⚡️ It is fast
• Differ supports three types of operations:
  • Insertions
  • Deletions
  • Moves (when using ExtendedDiff)
• Arbitrary sorting of patches (Patch)
• Utilities for updating UITableView and UICollectionView in UIKit, and NSTableView and NSCollectionView in AppKit
• Calculating differences between collections containing collections (use NestedDiff)

Why do I need it?

There's a lot more to calculating diffs than performing table view animations easily!

Wherever you have code that propagates added/removed/moved callbacks from your model to your user interface, you should consider using a library that can calculate differences. Animating small batches of changes is usually going to be faster and provide a more responsive experience than reloading all of your data.

Calculating and acting on differences should also aid you in making a clear separation between data and user interface, and hopefully provide a more declarative approach: your model performs state transition, then your UI code performs appropriate actions based on the calculated differences to that state.

Diffs, patches and sorting

Let's consider a simple example of using a patch to transform string "a" into "b". The following steps describe the patches required to move between these states:

Change	Result
Delete the item at index 0	""
Insert b at index 0	"b"

If we want to perform these operations in different order, simple reordering of the existing patches won't work:

Change	Result
Insert b at index 0	"ba"
Delete the item at index 0	"a"

...whoops!

To get to the correct outcome, we need to shift the order of insertions and deletions so that we get this:

Change	Result
Insert b at index 1	"ab"
Delete the item at index 0	"b"

Solution

In order to mitigate this issue, there are two types of output:

• Diff
  • A sequence of deletions, insertions, and moves (if using ExtendedDiff) where deletions point to locations of an item to be deleted in the source and insertions point to the items in the output. Differ produces just one Diff.
• Patch
  • An ordered sequence of steps to be applied to the source collection that will result in the second collection. This is based on a Diff, but it can be arbitrarily sorted.

Practical sorting

In practice, this means that a diff to transform the string 1234 into 1 could be described as the following set of steps:

DELETE 1
DELETE 2
DELETE 3

The patch to describe the same change would be:

DELETE 1
DELETE 1
DELETE 1

However, if we decided to sort it so that deletions and higher indices are processed first, we get this patch:

DELETE 3
DELETE 2
DELETE 1

How to use

Table and Collection Views

The following will automatically animate deletions, insertions, and moves:

tableView.animateRowChanges(oldData: old, newData: new)

collectionView.animateItemChanges(oldData: old, newData: new, updateData: { self.dataSource = new })

It can work with sections, too!

tableView.animateRowAndSectionChanges(oldData: old, newData: new)

collectionView.animateItemAndSectionChanges(oldData: old, newData: new, updateData: { self.dataSource = new })

You can also calculate diff separately and use it later:

// Generate the difference first
let diff = dataSource.extendedDiff(newDataSource)

// This will apply changes to dataSource.
let dataSourceUpdate = { self.dataSource = newDataSource }

// ...

tableView.apply(diff)

collectionView.apply(diff, updateData: dataSourceUpdate)

Please see the included examples for a working sample.

Note about updateData

Since version 2.0.0 there is now an updateData closure which notifies you when it's an appropriate time to update dataSource of your UICollectionView. This addition refers to UICollectionView's performbatchUpdates:

If the collection view's layout is not up to date before you call this method, a reload may occur. To avoid problems, you should update your data model inside the updates block or ensure the layout is updated before you call performBatchUpdates(_:completion:).

Thus, it is recommended to update your dataSource inside updateData closure to avoid potential crashes during animations.

Using Patch and Diff

When you want to determine the steps to transform one collection into another (e.g. you want to animate your user interface according to changes in your model), you could do the following:

let from: T
let to: T

// patch() only includes insertions and deletions
let patch: [Patch<T.Iterator.Element>] = patch(from: from, to: to)

// extendedPatch() includes insertions, deletions and moves
let patch: [ExtendedPatch<T.Iterator.Element>] = extendedPatch(from: from, to: to)

When you need additional control over ordering, you could use the following:

let insertionsFirst = { element1, element2 -> Bool in
    switch (element1, element2) {
    case (.insert(let at1), .insert(let at2)):
        return at1 < at2
    case (.insert, .delete):
        return true
    case (.delete, .insert):
        return false
    case (.delete(let at1), .delete(let at2)):
        return at1 < at2
    default: fatalError() // Unreachable
    }
}

// Results in a list of patches with insertions preceding deletions
let patch = patch(from: from, to: to, sort: insertionsFirst)

An advanced example: you would like to calculate the difference first, and then generate a patch. In certain cases this can result in a performance improvement.

D is the length of a diff:

• Generating a sorted patch takes O(D^2) time.
• The default order takes O(D) to generate.

// Generate the difference first
let diff = from.diff(to)

// Now generate the list of patches utilising the diff we've just calculated
let patch = diff.patch(from: from, to: to)

If you'd like to learn more about how this library works, Graph.playground is a great place to start.

Performance notes

Differ is fast. Many of the other Swift diff libraries use a simple O(n*m) algorithm, which allocates a 2 dimensional array and then walks through every element. This can use a lot of memory.

In the following benchmarks, you should see an order of magnitude difference in calculation time between the two algorithms.

Each measurement is the mean time in seconds it takes to calculate a diff, over 10 runs on an iPhone 6.

	Diff	Dwifft
same	0.0213	52.3642
created	0.0188	0.0033
deleted	0.0184	0.0050
diff	0.1320	63.4084

You can run these benchmarks yourself by checking out the Diff Performance Suite.

All of the above being said, the algorithm used by Diff works best for collections with small differences between them. However, even for big differences this library is still likely to be faster than those that use the simple O(n*m) algorithm. If you need better performance with large differences between collections, please consider implementing a more suitable approach such as Hunt & Szymanski's algorithm and/or Hirschberg's algorithm.

Requirements

Differ requires at least Swift 5.4 or Xcode 12.5 to compile.

Installation

You can add Differ to your project using Carthage, CocoaPods, Swift Package Manager, or as an Xcode subproject.

Carthage

github "tonyarnold/Differ"

CocoaPods

pod 'Differ'

Acknowledgements

Differ is a modified fork of Wojtek Czekalski's Diff.swift - Wojtek deserves all the credit for the original implementation, I am merely its present custodian.

Please, file issues with this fork here in this repository, not in Wojtek's original repository.

differ's Issues

Help / Documentation needed

Hi,

Thanks for this wonderful project.

I'm working with a UICollectionView with sections and items. I use differ API animateItemAndSectionChanges to animate my sections / items changes according to my data source.

Question 1

I can't find anyway to change the animation order (insert items first, delete after etc.). I saw Patch and Diff object, but no API to use them (except the apply buf NestedExtendedDiff does not allow ordering animation.

Question 2

Maybe not related to this project, but I have sections header / footer views, and after cells animation with differ, the headers are not correctly layout (the view moves up and down, and stay above cell). Small scroll or layout invalidation solves the issue... Strange.

Thanks.

Does it work asynchronously?

I tried to use code like
DispatchQueue.global().async {
....patch(from:to:)...
}
and it always throws a "EXC_BAD_ACCESS" error with long texts(4000 elements each). What can I do about it?

Comparison with Swift's CollectionDifference (SE-0240)

How does this compare with the Swift development proposal that plans to add Ordered Collection Diffing? Are you involved with that project in any way?

https://github.com/apple/swift-evolution/blob/master/proposals/0240-ordered-collection-diffing.md

Draft release

Can we please submit a release for this since it's currently impossible to submit to Apple off of the last release!

Thanks

Missing pod(CocoaPods) of Differ 1.0.2?

Extended diff produces unexpected results

I am not sure if this is an issue, or I just don't understand how it works. I am really confused and looking for help, thanks in advance for your support.

I have an array of Int, from 1 to 4. I swap first and last elements:

let old = [1, 2, 3, 4]
let new = [4, 2, 3, 1]
old.diff(new).elements // [D(0), I(0), D(3), I(3)]
old.extendedDiff(new).elements // [M(0,3), M(3,0)]

I can do the same for array of Int with more elements:

let old = [1, 2, 3, 4, 5]
let new = [5, 2, 3, 4, 1]
old.diff(new).elements // [D(0), I(0), D(4), I(4)]
old.extendedDiff(new).elements // [M(0,4), M(4,0)]

However, for array with only three elements, the result is something that I don't understand:

let old = [1, 2, 3]
let new = [3, 2, 1]
old.diff(new).elements // [D(0), D(1), I(1), I(2)]
old.extendedDiff(new).elements // [M(0,2), M(1,1)]

Is it a bug or expected behavior?

Crash and inconsistent results when doing slight modifications to Example Code

I am interested to find a good solution for multi-section diffing. So I came across Differ and though I am missing the functionality for detecting an update to an existing object I gave it a try.

A dataset like this creates a crash:

let items = [
       [
           StringArray(
               elements: [
                   "🌞",
                   "🐩",
               ],
               key: "First"
           ),
           StringArray(
               elements: [
                   "👋🏻",
                   "🎁",
                   "🐩",
               ],
               key: "Second"
           ),
       ],
       [
           StringArray(
               elements: [
                   "🎁",
                   "👋🏻",
               ],
               key: "Second"
           ),
           StringArray(
               elements: [
                   "🌞",
               ],
               key: "First"
           ),
           StringArray(
               elements: [
                   "🌞",
               ],
               key: "First"
           )
       ],
   ]

A dataset like this create inconsistant data when shuffling. Sometimes the order is correct, but sometimes it is't (see screenshot):

    let items = [
        [
            StringArray(
                elements: [
                    "🌞",
                    "🐩",
                ],
                key: "First"
            ),
            StringArray(
                elements: [
                    "👋🏻",
                    "🎁",
                    "🐩",
                ],
                key: "Second"
            ),
        ],
        [
            StringArray(
                elements: [
                    "🎁",
                    "👋🏻",
                ],
                key: "Second"
            ),
            StringArray(
                elements: [
                    "🌞",
                ],
                key: "First"
            ),
        ],
    ]

animateRowAndSectionChanges works for particular types of nested collections only

I have the following code:

class Item {
...
}
class Group {
...
var items = [Item]()
}
var groups = [Group]()

groups is a nested collection too but your code doesn't work with it.

Stack Overflow with an array of 2000 rows

I have an array with an item count of 4 in which we add 2000 items. When I call Differ to generate a patch based on an extendedDiff, it crashes in shiftPatchElement of GenericPatch.swift when generating the patch. This method make recursive calls to itself which is raising a stack overflow after 1753 calls.

I read the code but I cannot see how to fix it without rewriting a lot of things in this function. Can you help me? Thank you!

Reordering section and rows ends up in a total mess

I have performed the following:

data before:

[
    TestData(id: "SECTION_0", rows: [
        "S0_R0",
        "S0_R1",
        "S0_R2",
        "S0_R3",
        "S0_R4",
        "S0_R5"
    ]),
    TestData(id: "SECTION_1", rows: [
        "S1_R0",
        "S1_R1"
    ]),
]

data after:

[
    TestData(id: "SECTION_1", rows: [
        "S1_R0",
        "S1_R1"
    ]),
    TestData(id: "SECTION_0", rows: [
        "S0_R0",
        "S0_R4", // <-
        "S0_R1",
        "S0_R2",
        "S0_R3", // ->
        "S0_R5"
    ]),
]

We move 1 section up,
and we move 1 row up
As a result i see a total mess of rows and sections
What am i doing wrong?

This behavior is easily reproduced by the following code:

import Foundation
import UIKit

struct TestData: CollectionDecorator {
    let id: String
    let rows: [String]
    
    typealias InnerCollectionType = [String]
    var collection: [String] { rows }
}

class TestController2: UIViewController {
    
    let mTableView = UITableView()
    
    var data: [TestData] = [
        TestData(id: "SECTION_0", rows: [
            "S0_R0",
            "S0_R1",
            "S0_R2",
            "S0_R3",
            "S0_R4",
            "S0_R5"
        ]),
        TestData(id: "SECTION_1", rows: [
            "S1_R0",
            "S1_R1"
        ]),
    ]
    
    override func viewDidLoad() {
        super.viewDidLoad()
        
        addSubview(mTableView)
        mTableView.translatesAutoresizingMaskIntoConstraints = false
        mTableView.leftAnchor.constraint(equalTo: view.leftAnchor).isActive = true
        mTableView.rightAnchor.constraint(equalTo: view.rightAnchor).isActive = true
        mTableView.topAnchor.constraint(equalTo: view.topAnchor).isActive = true
        mTableView.bottomAnchor.constraint(equalTo: view.bottomAnchor).isActive = true
        mTableView.register(UITableViewCell.self, forCellReuseIdentifier: "Cell")
        mTableView.dataSource = self
        
        DispatchQueue.main.asyncAfter(deadline: .now() + 1.0) { [weak self] in
            guard let self = self else { return }
            self.recursiveShuffle()
        }
    }
    
    func recursiveShuffle() {
        
        let newData = [
            TestData(id: "SECTION_1", rows: [
                "S1_R0",
                "S1_R1"
            ]),
            TestData(id: "SECTION_0", rows: [
                "S0_R0",
                "S0_R4", // <-
                "S0_R1",
                "S0_R2",
                "S0_R3", // ->
                "S0_R5"
            ]),
        ]
        
        updateTable(newData: newData) {
            DispatchQueue.main.asyncAfter(deadline: .now() + 1.0) { [weak self] in
                guard let self = self else { return }
                
                let newDataBack = [
                    TestData(id: "SECTION_0", rows: [
                        "S0_R0",
                        "S0_R1", //->
                        "S0_R2",
                        "S0_R3",
                        "S0_R4", //<-
                        "S0_R5"
                    ]),
                    TestData(id: "SECTION_1", rows: [
                        "S1_R0",
                        "S1_R1"
                    ]),
                ]
                
                self.updateTable(newData: newDataBack) {
                    DispatchQueue.main.asyncAfter(deadline: .now() + 1.0) { [weak self] in
                        guard let self = self else { return }
                        self.recursiveShuffle()
                    }
                }
            }
        }
    }
}

extension TestController2: UITableViewDataSource {
    
    func numberOfSections(in tableView: UITableView) -> Int {
        return data.count
    }
    
    func tableView(_ tableView: UITableView, numberOfRowsInSection section: Int) -> Int {
        return data[section].count
    }
    
    func tableView(_ tableView: UITableView, cellForRowAt indexPath: IndexPath) -> UITableViewCell {
        let cell = tableView.dequeueReusableCell(withIdentifier: "Cell", for: indexPath)
        let text = data[indexPath.section][indexPath.row]
        cell.textLabel?.text = text
        
        if text.hasPrefix("S0") {
            cell.backgroundColor = .green
        } else {
            cell.backgroundColor = .red
        }
        
        return cell
    }
    
    func updateTable(newData: [TestData], completion: @escaping () -> Void) {
        
        let diff = data.nestedExtendedDiff(to: newData, isEqualSection: { $0.id == $1.id }, isEqualElement: { $0 == $1 })
        
        CATransaction.begin()
        CATransaction.setCompletionBlock(completion)
        data = newData
        mTableView.apply(diff, indexPathTransform: { $0 }, sectionTransform: { $0 })
        CATransaction.commit()
    }
}

/// Simply need to make something a collection is easy, if it has a collection inside
protocol CollectionDecorator: Collection {
    associatedtype InnerCollectionType: Collection
    var collection: InnerCollectionType { get }
}

extension CollectionDecorator {
    
    typealias Index = InnerCollectionType.Index
    typealias Element = InnerCollectionType.Element
    typealias Iterator = InnerCollectionType.Iterator
    typealias SubSequence = InnerCollectionType.SubSequence
    typealias Indices = InnerCollectionType.Indices
    
    func makeIterator() -> InnerCollectionType.Iterator { collection.makeIterator() }
    var underestimatedCount: Int { collection.underestimatedCount }
    func withContiguousStorageIfAvailable<R>(_ body: (UnsafeBufferPointer<Element>) throws -> R) rethrows -> R? {
        try collection.withContiguousStorageIfAvailable(body)
    }
    
    var startIndex: Self.Index { collection.startIndex }
    var endIndex: Self.Index { collection.endIndex }
    
    
    
    subscript(position: Self.Index) -> Self.Element {
        return collection[position]
    }
    
    subscript(bounds: Range<Self.Index>) -> Self.SubSequence {
        return collection[bounds]
    }
    
    var indices: Self.Indices { return collection.indices }
    var isEmpty: Bool { return collection.isEmpty }
    var count: Int { return collection.count }
    
    func index(_ i: Self.Index, offsetBy distance: Int) -> Self.Index {
        return collection.index(i, offsetBy: distance)
    }
    
    func index(_ i: Self.Index, offsetBy distance: Int, limitedBy limit: Self.Index) -> Self.Index? {
        return collection.index(i, offsetBy: distance, limitedBy: limit)
    }
    
    func distance(from start: Self.Index, to end: Self.Index) -> Int {
        return collection.distance(from: start, to: end)
    }
    
    func index(after i: Self.Index) -> Self.Index {
        collection.index(after: i)
    }
    
    func formIndex(after i: inout Self.Index) {
        collection.formIndex(after: &i)
    }
}

Diff.patch function has unused and redundant `from` argument

In Patch.swift, the patch function has a from argument which is unused and not needed since we already have a diff. Its presence almost suggests a recalculation, which is what prompted me to look.

(And FWIW: collecetion -> collection)

The following:

public extension Diff {

    /// Generates a patch sequence based on a diff. It is a list of steps to be applied to obtain the `to` collection from the `from` one.
    ///
    /// - Complexity: O(N)
    ///
    /// - Parameters:
    ///   - from: The source collection (usually the source collecetion of the callee)
    ///   - to: The target collection (usually the target collecetion of the callee)
    /// - Returns: A sequence of steps to obtain `to` collection from the `from` one.
    public func patch<T: Collection>(
        from: T,
        to: T
    ) -> [Patch<T.Iterator.Element>] {
        var shift = 0
        return map { element in
            switch element {
            case let .delete(at):
                shift -= 1
                return .deletion(index: at + shift + 1)
            case let .insert(at):
                shift += 1
                return .insertion(index: at, element: to.itemOnStartIndex(advancedBy: at))
            }
        }
    }
}

Should be:

public extension Diff {

    /// Generates a patch sequence based on a diff. It is a list of steps to be applied to obtain the `to` collection from the `from` one.
    ///
    /// - Complexity: O(N)
    ///
    /// - Parameters:
    ///   - from: The source collection (usually the source collection of the callee)
    ///   - to: The target collection (usually the target collection of the callee)
    /// - Returns: A sequence of steps to obtain `to` collection from the `from` one.
    public func patch<T: Collection>(to: T) -> [Patch<T.Iterator.Element>] {
        var shift = 0
        return map { element in
            switch element {
            case let .delete(at):
                shift -= 1
                return .deletion(index: at + shift + 1)
            case let .insert(at):
                shift += 1
                return .insertion(index: at, element: to.itemOnStartIndex(advancedBy: at))
            }
        }
    }
}

Throw exception, invalid number of rows

Revision of UIKit Overlay's API

I would like to revise Differ's public API in terms of its UIKit overlay. The changes I would like to make are the following:

1. Optional completion handlers for methods on UITableView

The UICollectionView already has this parameter and it seems reasonable to support this on UITableView as well. The intuitive approach to implement this would be using performBatchUpdates(_:completion:) instead of beginUpdates()/endUpdates(). This method, however, is only available on iOS 11+.

Alternatively, we could keep the old methods and add extra @available(iOS 11.0, *) methods with completion handlers.

Another idea would be to hook into CATransaction, wrapping beginUpdates()/endUpdates() in CATransaction.begin()/CATransaction.commit() and registering the completion handler using CATransaction.setCompletionBlock(_:). I highly doubt that this would have the same semantics as using performBatchUpdates(_:completion:)'s completion handler.

Personally, I would make this a major version bump (see other changes below), drop support for iOS 10 and earlier, and simply use the modern performBatchUpdates(_:completion:) API.

The update block passed to performBatchUpdates(_:completion:) is also optional, meaning it is implicitly escaping, requiring us to annotate things like indexPathTransform as @escaping as well. I don't think that's a huge deal, though. I'm not sure if the block even escapes; we could try using withoutActuallyEscaping(_:do) if there are strong reasons to not annotate the closures as @escaping, though I'd try to avoid that if possible in case the block actually does escape.

2. Mandatory updateData parameter for UITableView

Again, this is a feature we already have for UICollectionView, and we should port it to UITableView as well. Currently, it is very easy to use the Differ/UITableView/UICollectionView APIs incorrectly, as #62 shows. Adding this parameter alone is not going to solve these issues, but it at least tells users of the library at which point they are supposed to update the data source.

Unfortunately, the intuitive way of using Differ calls things like animateRowChanges(oldData:newData:) when the underlying data has already changed, e.g., from inside a didSet property observer, which is incorrect. This causes crashes when a UITableView/UICollectionView has not queried its data source or the cache has been invalidated prior to scheduling an animation. In these cases, the UITableView/UICollectionView query its data twice, before and after the changes specified by the diff, but ends up querying the new data twice, thus crashing with an NSInternalInconsistencyException. Problems like this may be anchored deeply within an app's architecture and it might not be feasible to call Differ before the data changes and update the data source only once Differ tells you to.

We could try to prevent the crashes by checking if a diff is compatible with the current state of a UITableView/UICollectionView before applying it, and calling reloadData() instead if it is not. I'm not sure how this interacts with nested calls to performBatchUpdates(_:completion:) and will need to investigate a bit more. If you have any other ideas to address this issue, please let me know.

Even with this safeguard in place, I believe we should make the parameter mandatory to force users to think about when they update the data source. This way, users would need to opt in to using the APIs incorrectly.

Personally, I have no experience with making breaking changes in a library. Do you think we should keep the old signatures around and annotate them as @available(*, deprecated, message: "") to make migration to 2.0 easier?

3. Optional animated: Bool parameter for UITableView and UICollectionView.

Sometimes, we may want to update the UITableView's data without animation, for example, if the UITableView is currently offscreen or if the user has the "Reduce Motion" accessibility feature enabled. In these cases, updating the relevant parts of the UITableView via performBatchUpdates(_:completion:) is much more efficient than simply calling reloadData(), which causes all cells to be reloaded. reloadData() also has the nasty side effect of cancelling touches if the user is currently interacting with the cells.

If animated is false, we could simply wrap the call to performBatchUpdates(_:completion:) in UIView.performWithoutAnimation(_:).

---

In summary, here are the changes I would like to make to the UIKit overlay. Analogous changes to the animateRowChanges, animateRowAndSectionChanges, animateItemChanges, and animateItemAndSectionChanges families of methods are intentionally left out here. Having the methods begin with "animated" and then having an animated: Bool parameter might be a bit strange — maybe we should rename the methods to "applyRowChanges" or "transitionRows" or something else?

extension UITableView {
    func apply(
        _ diff: ExtendedDiff,
        deletionAnimation: DiffRowAnimation = .automatic,
        insertionAnimation: DiffRowAnimation = .automatic,
-       indexPathTransform: (IndexPath) -> IndexPath = { $0 },
+       indexPathTransform: @escaping (IndexPath) -> IndexPath = { $0 },
+       updateData: () -> Void,
+       animated: Bool = true,
+       completion: ((_ finished: Bool) -> Void)? = nil,
    )

    func apply(
        _ diff: NestedExtendedDiff,
        rowDeletionAnimation: DiffRowAnimation = .automatic,
        rowInsertionAnimation: DiffRowAnimation = .automatic,
        sectionDeletionAnimation: DiffRowAnimation = .automatic,
        sectionInsertionAnimation: DiffRowAnimation = .automatic,
-       indexPathTransform: (IndexPath) -> IndexPath,
+       indexPathTransform: @escaping (IndexPath) -> IndexPath,
-       sectionTransform: (Int) -> Int,
+       sectionTransform: @escaping (Int) -> Int,
+       updateData: () -> Void,
+       animated: Bool = true,
+       completion: ((_ finished: Bool) -> Void)? = nil,
    )
}

extension UICollectionView {
    func apply(
        _ diff: ExtendedDiff,
        updateData: () -> Void,
+       animated: Bool = true,
        completion: ((Bool) -> Void)? = nil,
        indexPathTransform: @escaping (IndexPath) -> IndexPath = { $0 },
    )

    func apply(
        _ diff: NestedExtendedDiff,
        indexPathTransform: @escaping (IndexPath) -> IndexPath = { $0 },
        sectionTransform: @escaping (Int) -> Int = { $0 },
        updateData: () -> Void,
+       animated: Bool = true,
        completion: ((Bool) -> Void)? = nil,
    )
}

Move row in moving section failed in TableView

Hi,
I just reached to problem with moving rows inside of section that is moved in the same update. Example app (NestedTableViewController) have this issue. I updated items in https://github.com/EtneteraMobile/Differ/tree/test-move to highlight invalid behaviour.

This is result of update, where section are switched and rows inside are switched too.
Expected result: Second – 2, 1; First – 2, 1
Invalid result: Second – 2, 1; First – 1, 2

It seems to be bug in UITableView that doesn't perform move in section that is moving.

`NSInternalInconsistencyException` using MVVM approach

Hi and thank you for this library. I am new to diffing.
I tested the example project and I am now trying to use Diffing with MMVM.

Here is the simple MVVM code I am using to try it:

protocol InteractorDelegate: class {
    func viewModelDidChange(_ old: ViewModel?, _ new: ViewModel)
}

class Interactor {

    weak var delegate: InteractorDelegate?

    var items = [
            [1,5,6,7,4,6,7,1,5],
            [1,5,2,1,0,6,7],
    ]

    var viewModel: ViewModel? {
        didSet {
            delegate?.viewModelDidChange(oldValue, viewModel!)
        }
    }

    var currentObjects: Int = 0 {
        didSet {
            viewModel = .init(with: .loaded(items[currentObjects]))
        }
    }

    init() {
        viewModel = .init(with: .initialized)
    }

    func fetchValue() {
        currentObjects = currentObjects == 0 ? 1 : 0
    }
}

struct ViewModel {

    enum ViewModelType: Equatable {
        case cell(CellViewModel)
    }

    enum State {
        case initialized
        case loaded([Int])
    }

    let state: State
    let viewModels: [ViewModelType]

    init(with state: State) {
        self.state = state
        switch state {
        case .initialized: viewModels = []
        case .loaded(let values):
            viewModels = CellViewModel.from(values).map(ViewModelType.cell)
        }
    }
}

extension ViewModel: Equatable {

    static func ==(left: ViewModel, right: ViewModel) -> Bool {
        return left.state == left.state
    }
}

extension ViewModel.State: Equatable {

    static func ==(left: ViewModel.State, right: ViewModel.State) -> Bool {
        switch (left, right) {
        case (.initialized, .initialized): return true
        case let (.loaded(l), .loaded(r)): return l == r
        default: return false
        }
    }
}

struct CellViewModel {
    let description: String
}

extension CellViewModel {

    static func from(_ values: [Int]) -> [CellViewModel] {
        return values.map { CellViewModel(description: String($0)) }
    }
}

extension CellViewModel: Equatable {

    static func ==(left: CellViewModel, right: CellViewModel) -> Bool {
        return left.description == right.description
    }
}

Here for the Controller part:

import UIKit
import Differ

class ViewController: UIViewController {

    ...

    override func viewDidLoad() {
        super.viewDidLoad()
        ...

        interactor.fetchValue()
    }

    @objc
    func onRefresh() {
        interactor.fetchValue()
    }
}

extension ViewController: UITableViewDataSource {
    func tableView(_ tableView: UITableView, numberOfRowsInSection section: Int) -> Int {
        return interactor.viewModel.value.viewModels.count
    }

    func tableView(_ tableView: UITableView, cellForRowAt indexPath: IndexPath) -> UITableViewCell {
        let cellViewModel = interactor.viewModel.value.viewModels[indexPath.row]
        switch cellViewModel {
        case .cell(let viewModel):
            let cell = tableView.dequeueReusableCell(withIdentifier: "cell", for: indexPath)
            cell.textLabel?.text = viewModel.description
            return cell
        }
    }
}

extension ViewController: InteractorDelegate {

    func viewModelDidChange(_ old: ViewModel?, _ new: ViewModel) {

        if let prev = old {
            print("Previous => State: \(prev.state) | ViewModelType.count: \(prev.viewModels.count)")
        } else {
            print("Previous => State: nil | ViewModelType.count: nil")
        }
        print("Current => State: \(new.state) | ViewModelType.count: \(new.viewModels.count)")
        DispatchQueue.main.async {
            self.tableView.animateRowChanges(oldData: old?.viewModels ?? [], newData: new.viewModels)
        }
    }
}

Here is what I got:

Previous => State: initialized | ViewModelType.count: 0
Current => State: loaded([1, 5, 2, 1, 0, 6, 7]) | ViewModelType.count: 7
2019-10-29 13:45:56.636678+0900 TestDiffer[93631:21379549] *** Terminating app due to uncaught exception 'NSInternalInconsistencyException', reason: 'Invalid update: invalid number of rows in section 0. The number of rows contained in an existing section after the update (7) must be equal to the number of rows contained in that section before the update (7), plus or minus the number of rows inserted or deleted from that section (7 inserted, 0 deleted) and plus or minus the number of rows moved into or out of that section (0 moved in, 0 moved out).'

I first posted the question on stack overflow but maybe this is where it should be asked.

Is there something wrong with Equatable or am I missing something?
Thank you.

Items that do not move show as being moved

I am seeing some weird behavior when diffing arrays which have contents that do not move. Here is the scenario:

I have two arrays, which look like this:

Old array: ([Int]) $R90 = 20 values {
  [0] = 63
  [1] = 5
  [2] = 112
  [3] = 48
  [4] = 100006
  [5] = 121
  [6] = 33
  [7] = 65
  [8] = 100003
  [9] = 57
  [10] = 100007
  [11] = 117
  [12] = 108
  [13] = 1
  [14] = 118
  [15] = 100688
  [16] = 18
  [17] = 54
  [18] = 116
  [19] = 110
}
New array: ([Int]) $R91 = 20 values {
  [0] = 65
  [1] = 118
  [2] = 110
  [3] = 117
  [4] = 100006
  [5] = 112
  [6] = 1
  [7] = 54
  [8] = 116
  [9] = 100688
  [10] = 48
  [11] = 57
  [12] = 108
  [13] = 63
  [14] = 121
  [15] = 33
  [16] = 18
  [17] = 5
  [18] = 100003
  [19] = 100007
}

One of the patches returned the extendedPatch() function looks like this:

 [13] = move {
    move = (from = 20, to = 16)
  }

This is causing a crash in my app, because there is no item at index 20 in the array. You can see that the object at index 16 doesn't move, but for some reason the library is saying that it has moved.

Privacy manifest adoption

Do we know that is the status of Privacy manifest adoption for this lib?
I guess that Differ probably does not need one?

Deprecated methods in Swift 4.1

Hey @tonyarnold, just wanted to let you know that Xcode 9.3 (just released today) ships with Swift 4.1, and is warning of several deprecated methods used in Differ.

High Memory Usage extended diffing two arrays of quite differently ordered results

Hello, I've come across a particular case where I'm seeing a really high memory usage and wanted to make sure I wasn't doing something wrong or extended diffing in some unintended way.

I was extended diffing two seemingly small arrays of items which happened to be the same (or very similar, give or take a few items) but in two different orders. Though my data was from a different source, I've reproduced the issue with the following example but just creating an array of 5,000 random Ints, uniquing and then shuffling the first array of items to create the second set of items to diff.

DispatchQueue(label: "test").async {
   let pool = (0...999_999)
   let getRandom: () -> [Int] = {
       (0..<5_000).map { _ in
           pool.randomElement()!
       }
   }
   let previous = Set(getRandom()).shuffled()
   let current = previous.shuffled()
   let before = Date()
   let _ = previous.extendedDiff(current)
   print("finished. took:", Date().timeIntervalSince(before))
}

Running this code appears to reach a memory usage of around ~1GB, and take ~27 seconds.
For reference, 10,000 items seems to hit ~6GB and take ~111 seconds.

Also for reference, using two random sets of 10,000 items also hits about ~5GB and takes ~113 seconds. eg.:

let previous = Set(getRandom()).sorted()
let current = Set(getRandom()).sorted()

The reason this is a problem is that iOS (or at least debugging device in Xcode) seems to have a memory limit of about 2GB before you get terminated.

In my case, all I really care about is the deleted indexes and not the order, so I've found that in the case where the two arrays are very similar but in different orders, if I sort both arrays of items beforehand so that they're as similar as possible and then run the diff, it takes negligible memory and finishes in no time at all even with 10,000 items. Unfortunately in the case of two random sets of items, sorting won't help and will hit those limits/take a while.

I just wanted to make sure that I'm not doing something else wrong here, or if there's a different approach I should be taking for extended diffing two sets of items that could for all I know be two sets of different items.

Edit: Clarify that I was extended diffing (both seem to be problematic, but still)

Sections diff improvements

Hi, currently Differ support calculating extended diffs of two dimensional arrays.

But what can I do if I have an array of some objects where internal object has array and some additional data:

Section
- header: String
- items: [Item]

Would it be possible to add new KeyPath feature, for example:

sections.nestedDiff(to: newSections, item: \.items, ...)

Move Elements from one Section to another

Correct me if i'am wrong, but as I could figure out, the lib doesn't support movements of an element between sections. It only detects movements of sections or movements of elements in a section.
At the current state the lib generates a DE "Delete Element" in one section and a IE "Insert Element" in the other section instead of a movement.

It would be pretty nice if this could be accomplished by a NestedExtendedDiff ;-)

Cocoapods version doesn't support Swift 4.2

I'm new to all of this, so this might be silly and stupid.

I'm installing differ from Cocoapods and can't get it to install a version that supports Swift 4.2

The current version on Cocoapods is 1.2.3.

Looking at the code in the repo there was obviously work done to update the codebase to 4.2

Any plans on updating Cocoapods version, or I do I work around it?

Cocoapods release for 1.4.3

1.4.1 is the currently available pod version.

Can we push the latest to Cocoapods?

Comparision with Hackel Diff algo

Thanks for contributing to the swift community.

As an author of my own implementation of Diff based on Heckel's algorithm I wanted to know if you did try the comparision with implementation based on Heckel's algo?

Im working on this www.github.com/kandelvijaya/fastdiff while there are few others around. The next immediate one is DeepDiff (should be).

Broken sources or obsolete readme?

From your readme:

let diff = dataSource.diff(newDataSource)
tableView.apply(diff)

It doesn't work because diff is Diff but apply method requires ExtendedDiff and these 2 classes are incompatible

Build errors under Swift 4.1 on Linux

Swift version: 4.1
Differ version: 1.2.0
Expected result: Compilation to work.
Actual result: Compilation does not work. 😞

Output:

Compile Swift Module 'Differ' (15 sources)
/home/ryan/stuff/Amai/.build/checkouts/Differ-2633178418749090106/Sources/Differ/NestedBatchUpdate.swift:30:57: error: cannot invoke initializer for type 'IndexPath' with an argument list of type '(item: Int, section: Int)'
                itemDeletions.append(indexPathTransform(IndexPath(item: at, section: section)))
                                                        ^
/home/ryan/stuff/Amai/.build/checkouts/Differ-2633178418749090106/Sources/Differ/NestedBatchUpdate.swift:30:57: note: overloads for 'IndexPath' exist with these partially matching parameter lists: (), (indexes: ElementSequence), (arrayLiteral: IndexPath.Element...), (indexes: Array<IndexPath.Element>), (index: IndexPath.Element), (from: Decoder)
                itemDeletions.append(indexPathTransform(IndexPath(item: at, section: section)))
                                                        ^
/home/ryan/stuff/Amai/.build/checkouts/Differ-2633178418749090106/Sources/Differ/NestedBatchUpdate.swift:32:58: error: cannot invoke initializer for type 'IndexPath' with an argument list of type '(item: Int, section: Int)'
                itemInsertions.append(indexPathTransform(IndexPath(item: at, section: section)))
                                                         ^
/home/ryan/stuff/Amai/.build/checkouts/Differ-2633178418749090106/Sources/Differ/NestedBatchUpdate.swift:32:58: note: overloads for 'IndexPath' exist with these partially matching parameter lists: (), (indexes: ElementSequence), (arrayLiteral: IndexPath.Element...), (indexes: Array<IndexPath.Element>), (index: IndexPath.Element), (from: Decoder)
                itemInsertions.append(indexPathTransform(IndexPath(item: at, section: section)))
                                                         ^
/home/ryan/stuff/Amai/.build/checkouts/Differ-2633178418749090106/Sources/Differ/NestedBatchUpdate.swift:34:54: error: cannot invoke initializer for type 'IndexPath' with an argument list of type '(item: Int, section: Int)'
                itemMoves.append((indexPathTransform(IndexPath(item: from.item, section: from.section)), indexPathTransform(IndexPath(item: to.item, section: to.section))))
                                                     ^
/home/ryan/stuff/Amai/.build/checkouts/Differ-2633178418749090106/Sources/Differ/NestedBatchUpdate.swift:34:54: note: overloads for 'IndexPath' exist with these partially matching parameter lists: (), (indexes: ElementSequence), (arrayLiteral: IndexPath.Element...), (indexes: Array<IndexPath.Element>), (index: IndexPath.Element), (from: Decoder)
                itemMoves.append((indexPathTransform(IndexPath(item: from.item, section: from.section)), indexPathTransform(IndexPath(item: to.item, section: to.section))))
                                                     ^
error: terminated(1): /usr/lib/swift/bin/swift-build-tool -f /home/ryan/stuff/Amai/.build/debug.yaml main output:

Differ does not build universal for Apple Silicon Macs

Due to the explicit architectures listed in Universal-Target-Base.xcconfig, Differ will not build universal for Apple Silicon Macs.

Differ does not perform row reloading if the changes is happening on same row. (macOS)

Hey there,

I've started implementing Differ in our app to drive changes to our TableView.
As our app needs to support 10.15+, we cannot use the native DiffableSource implementation.

So using extendingDiff and patch, I realized that the current AppKit extension that applies the patch to the NSTableView is not using the reloadData(forRowIndexes: IndexSet, columnIndexes: IndexSet) when changes are applicable to a single row.

Here's our patch description:

EmailList DiffPatch [D(4), I(4,<Ocean.EmailListSource: 0x600002d323c0>)]

Why is this important?

By using Delete and Insert, if the selected row was 4, then it is automatically deselected.
This behavior, instead of using reloadDate(forRow...) makes for a pretty bad UX in our case.

Any suggestions on how to circumvent that? Thanks

Can't compile in objective-c project

How can I use it in objective-c project?

I tried @import Differ; but can't use functions like animateItemChanges... probably it's not open to objc.

What classes/files to read to learn from the solution and apply it on my own

Hi,
I have a use case for favorites table in tab controller, it needs to be updated with whatever products added/removed from other tabs while user experiencing the products there.

I cannot upgrade Xcode for now, I thought to ask, what classes/files to read as a beginner to learn how to approach a solution for this use case.

I am asking because I am kinda overwhelmed.

Sorry if not the appropriate place to open this issue.

Can't build in Xcode 12 with Differ as an spm sub-dependency

I have a project using Bond and and Differ, both imported with Xcode's spm integration. When I open this project in Xcode 12, Xcode fails to build, with the following error:

error: The package product 'Differ' requires minimum platform version 9.0 for the
 iOS platform, but this target supports 8.0 (in target 'Bond' from project 'Bond')

This problem seems to occur because Differ doesn't declare a minimum platform version, which makes Xcode interpret its minimum platform as 9.0 (the new default for Xcode 12), which clashes with what Bond declares in its Package.swift:

    platforms: [
        .macOS(.v10_11), .iOS(.v8), .tvOS(.v9)
    ],

I verified that this problem is not tied to my specific project by creating an entirely new project, adding just the Bond package (which automatically pulls in Differ), and seeing the same error in Xcode 12. I think that adding the same platforms declaration that Bond has would solve this problem.

Module compiled with Swift 5.3.1 cannot be imported by the Swift 5.5 compiler:

Is there an update to 5.5?

Trouble with NSCollectionView usage

I'm having some trouble using Differ with an NSCollectionView, specifically the function animateItemsAndSectionChanges(oldData: , newData:)

Here's a quick example of the code I'm using:

struct MySection: Equatable {
  let name = "Test"
  var items = [String]()
}

func quickRefreshTest(oldData: [MySection], newData: [MySection]) {
  collectionView.animateItemAndSectionChanges(oldData: oldData, newData: newData)
}

But the compiler complains Generic parameter 'T' could not be inferred.

Edit: This doesn't seem to be a bug, I think it was just a compiler/generics/protocols difficulty. I'll post more details tomorrow

Potential optimisations & refinements

@wokalski identified potential optimisations and refinements that could be made to this library - I'd be grateful for contributions if anyone feels like tackling any of these, but mainly I'm just making sure they're documented for future me:

• https://neil.fraser.name/writing/diff/ (from https://github.com/wokalski/Diff.swift/issues/5)
• The current implementation is the simplest version of Myers' algorithm. Linear space refinement as described in the paper would improve our implementation. (from https://github.com/wokalski/Diff.swift/issues/6)

Cocoapods release for swift 4.2?

Completion handlers for UITableView-based animations

I recently found myself in need of a completion handlers when using Differ to run an animation on UITableView. Differ is still using the beginUpdates()/endUpdates() APIs for UITableView which do not support completion handlers. However, since iOS 11, UITableView too supports performBatchUpdates(_:completion:).

I would love to see an overloaded animateRowChanges and animateRowAndSectionChanges which use the performBatchUpdates API and support a completion handler. We can obviously keep the old methods around to support older OSes. Is this something that you would be interested in having in this project, or is this something you already decided against?

Can't build via Carthage

Xcode Version 9.3 (9E145)
Swift 4.1
Command which I use: carthage bootstrap --platform ios --no-use-binaries
As far as I know this issue is connected with New Xcode Build system.

Compilation error of TableViewExample

TableViewExample.project -> Graph.playground -> Sources -> CharacterLabels.swift -> line 17

'characters' is unavailable: Please use String directly

Can't compile Differ with Carthage to generate a StaticFramework.

Following the steps identified here:
https://github.com/Carthage/Carthage/blob/master/Documentation/StaticFrameworks.md

I can't compile Differ to generate a StaticFramework.

`*** Building scheme "Differ" in Differ.xcodeproj
Build Failed
Task failed with exit code 65:
/usr/bin/xcrun xcodebuild -project /Users/peter/Carthage/Checkouts/Differ/Differ.xcodeproj -scheme Differ -configuration Release -derivedDataPath /Users/peter/Library/Caches/org.carthage.CarthageKit/DerivedData/9.4_9F1027a/Differ/1.2.3 -sdk watchos ONLY_ACTIVE_ARCH=NO BITCODE_GENERATION_MODE=bitcode CODE_SIGNING_REQUIRED=NO CODE_SIGN_IDENTITY= CARTHAGE=YES archive -archivePath /var/folders/2x/_53hdv7j2ts7yrqbhbjbghgw0000gn/T/Differ SKIP_INSTALL=YES GCC_INSTRUMENT_PROGRAM_FLOW_ARCS=NO CLANG_ENABLE_CODE_COVERAGE=NO STRIP_INSTALLED_PRODUCT=NO (launched in /Users/peter/Carthage/Checkouts/Differ)

This usually indicates that project itself failed to compile. Please check the xcodebuild log for more details: /var/folders/2x/_53hdv7j2ts7yrqbhbjbghgw0000gn/T/carthage-xcodebuild.wzz23x.log`

carthage-xcodebuild.wzz23x.log

Generic parameter 'T' could not be inferred

Is there a way to make the following situation work.

I have an enum as follows

public enum PlaylistItem {
    case previous(Video)
    case current(Video)
    case next(Video)
}

The datasource for the collectionView is an Array of the PlaylistItem enum, when I attempt to animate changes I get Generic parameter 'T' could not be inferred

 let newPlayList: [PlaylistItem] = [.current(Video(id: "123"))]
 let oldPlayList: [PlaylistItem] = [.previous(Video(id: "12334")), .current(Video(id: "1234453"))]
 self?.mixCollectionView.animateItemChanges(oldData: oldPlayList, newData: newPlayList)

Is there any way I can make this work?

Crash error: can't allocate region

Hi @tonyarnold , I'm playing with different diffing algorithms, and want to give them some benchmarks https://github.com/onmyway133/DeepDiff#among-different-frameworks. When comparing Differ on some data sets, I get a crash. I run on device iPhone 6, iOS 11, Xcode 9.2. Maybe the datset is wrong, but it runs fine with many other diffing framworks

Benchmark(1924,0x1b545bb80) malloc: *** mach_vm_map(size=1073741824) failed (error code=3)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug

Here is how such a data set gets generated

private func generate() -> (old: Array<String>, new: Array<String>) {
    let old = Array(repeating: UUID().uuidString, count: 10000)
    var new = old

    new.removeSubrange(100..<200)
    new.insert(
      contentsOf: Array(repeating: UUID().uuidString, count: 500),
      at: new.endIndex.advanced(by: -20)
    )

    return (old: old, new: new)
  }

Is there a reason that `patch` is restricted to `Equatable` elements?

This feels like a cut and paste issue, but patch seems unnecessarily constrained to Equatable when there is an equality closure on diff, and it compiles without the Equatable requirement, see the example below.

Am I missing something?

public extension Diff {

    /// Generates a patch sequence based on a diff. It is a list of steps to be applied to obtain the `to` collection from the `from` one.
    ///
    /// - Complexity: O(N)
    ///
    /// - Parameters:
    ///   - from: The source collection (usually the source collecetion of the callee)
    ///   - to: The target collection (usually the target collecetion of the callee)
    /// - Returns: A sequence of steps to obtain `to` collection from the `from` one.
    public func patch<T: Collection>(
        from: T,
        to: T
    ) -> [Patch<T.Iterator.Element>] where T.Iterator.Element: Equatable {
        var shift = 0
        return map { element in
            switch element {
            case let .delete(at):
                shift -= 1
                return .deletion(index: at + shift + 1)
            case let .insert(at):
                shift += 1
                return .insertion(index: at, element: to.itemOnStartIndex(advancedBy: at))
            }
        }
    }

    /// Generates a patch sequence based on a diff. It is a list of steps to be applied to obtain the `to` collection from the `from` one.
    ///
    /// - Complexity: O(N)
    ///
    /// - Parameters:
    ///   - from: The source collection (usually the source collecetion of the callee)
    ///   - to: The target collection (usually the target collecetion of the callee)
    /// - Returns: A sequence of steps to obtain `to` collection from the `from` one.
    public func patchDoesntNeedEquatable<T: Collection>(
        from: T,
        to: T
        ) -> [Patch<T.Iterator.Element>] {
        var shift = 0
        return map { element in
            switch element {
            case let .delete(at):
                shift -= 1
                return .deletion(index: at + shift + 1)
            case let .insert(at):
                shift += 1
                return .insertion(index: at, element: to.itemOnStartIndex(advancedBy: at))
            }
        }
    }
}

Thanks.

Move lib into an org

@tonyarnold I just noticed that the Diff pod is now Differ and that has been "moved" to your account.

To avoid issues like that if you ever stop supporting it and needs to move it to someone else, I'd like to suggest the repo to be moved into an organization and that would allow an easier transition of maintainers.

If possible, it would be awesome to get @wokalski to do that on his side, with the original Diff repo.

I'm happy to help with that.

Crash when inserting items into empty collection view

Hey @tonyarnold, the latest version of Differ is causing a crash when inserting items into an empty collection view. Specifically, the crash started with commit 9db06bb (Use array literals to provide IndexPaths for compatibility with Swift Package Manager).

This crash did not occur prior to this commit.

I’ve attached sample projects, one using Differ as of commit 30d9b35 (no crash) and one using commit 9db06bb (crashes).

Tested using Xcode 9.3 and iOS 11.3.

(Not sure why just using different syntax for IndexPath is causing a crash ¯_(ツ)_/¯)

Differ Crash Sample Projects.zip