I'm having trouble getting the default algorithm to do replacements instead of deletes followed by inserts. Even this basic code...

let old = [
    "New York",
    "Imagine City",
    "London"
]

let new = [
    "New York",
    "Oslo",
    "London",
    ]

let changes = diff(old: old, new: new)

...gives me a delete followed by an insert. Whereas using let changes = diff(old: old, new: new, algorithm: WagnerFischer()) makes everything work correctly.

Is this an intentional attribute of the Heckel algorithm?

like this

let old = [
  User(id: "1eqw", name: "Captain America"),
  User(id: "12ed", name: "Captain Marvel"),
  User(id: "3r35s", name: "Thor"),
]

let new = [
  User(id: "1eqw", name: "Captain America"),
  User(id: "sac45", name: "The Binary"),
  User(id: "3r35s", name: "Thor"),
]

let changes = diff(old: old, new: new)

Hi, I am trying to use DeepDiff and my models are sql objects that are returned from my backend. To enable the use of deepdiff, I need to be able to return a diffId in the to conform to the protocol DiffAware.

The problem arises that my sql objects have composite primary keys, meaning that it requires more than just one element to compare each object's uniqueness. It is easy to do checks in the compareContent function, but I am very puzzled to how one would go about declaring the diffId to ensure that these types can return a hash, and that being a string has since all of my attributes are composed of strings.

An example object is instantiated like Object(place: String, date: String, time: String, reason: String). Where the primary key is composed of the place, date and time values. How would one go about setting the diffId for this object?

I hope this example makes sense.

Thank you.

Could you explain why we need to use DiffAware protocol when Hashable do the same thing and there is a lot of helper functional out-of-the-box like Hasher etc.

For example, we have a simple struct:

struct SomeStruct<T: DiffAware, U: DiffAware> {
  var value: T
  var valuesArray: [U]
}

And if we want to conform DiffAware protocol, we need to calculate diffId something like this:

 var diffId: Int {
    let valueIds = self.values.map({ $0.diffId })
    
    var hasher = Hasher()
    hasher.combine(self.value.diffId)
    hasher.combine(valueIds)
    
    return hasher.finalize()
}

And if all the objects conformed Hashable protocol, I will not need to use map in this case and it will affect the performance.

As I remember map complexity is O(n).

Hi Khoa,

 It seems that the API has been updated and the option to prevent reduceMove has been removed. Can you update with the correct documentation?

Since the beta release of Xcode 11, it would be lovely to have DeepDiff available as a Swift Package.

Hi,
i am trying to implement a text-base diff viewer, my code looks like the following:

let originalLines = originalSource.split(separator: "\n", omittingEmptySubsequences: false).map{String($0)}


let diffLines = diffSource.split(separator: "\n", omittingEmptySubsequences: false).map{String($0)}
            
            
let algorithmStart = CACurrentMediaTime()
let diffchecker = WagnerFischer<String>(reduceMove: false)
let changes = diffchecker.diff(old: originalLines, new: diffLines)
DC_LOG_INFO("DiffVC, diff algorithm cost \(CACurrentMediaTime() - algorithmStart)")

my sample files are 2 objc source files with 650+lines, and only 1 line is different , and the log prints out:
DiffVC, diff algorithm cost 6.890240641998389

Any idea of why this is so slow?

While this issue is related to #1 , what I propose is to make DeepDiff applicable to calculate Diff in any section other than 0.
Currently, the section number is hardcoded to be 0.

What I propose, is to add a section parameter to the API to generate valid IndexPaths, for example:

let changes = diff(old: oldItems, new: items, section: 4)

Hi! It would be honest to add Swift's CollectionDifference to the Performance project and to the Among different frameworks section in Readme. Of course, it's iOS 13+ only but why not.

What do you think?

Both UICollectionView+Extensions and UITableView+Extensions need to add closures for updating the data model after performBatchUpdates is called but before updates are applied (Example fix below):

public func reload<T: Hashable>(
    changes: [Change<T>],
    section: Int = 0,
    updateModel: (() -> Void)? = nil, // <===== This should fix #8 
    completion: ((Bool) -> Void)? = nil) {
    
    let changesWithIndexPath = IndexPathConverter().convert(changes: changes, section: section)
    
    // reloadRows needs to be called outside the batch
    
    performBatchUpdates({
      updateModel?()                  // <===== This should fix #8 
      internalBatchUpdates(changesWithIndexPath: changesWithIndexPath)
    }, completion: { finished in
      completion?(finished)
    })
    
    changesWithIndexPath.replaces.executeIfPresent {
      self.reloadItems(at: $0)
    }
  }

Otherwise, you'll see NSInternalInconsistencyExceptions since the model will already have the same number of items before and after update.

I am trying to build Example target using Xcode9.2 with Swift 4.0 it failed. The error I am getting is

Value of type '[Change]' has no member 'compactMap'

Is there any problem with current swift version or any thing, can anyone help me out

I've been testing a variation of your Heckel implementation in a macOS CollectionView project and found an issue. Using hashValue as the key in the table is not reliable. I've made this same mistake myself in early versions of the data structures used in that collection view implementation. My basic solution for now is to replace with [T.Element:TableEntry] and the issue hasn't come up again.

From the Apple Docs

A hash value, provided by a type’s hashValue property, is an integer that is the same for any two instances that compare equally. That is, for two instances a and b of the same type, if a == b, then a.hashValue == b.hashValue. The reverse is not true: Two instances with equal hash values are not necessarily equal to each other.

This project is amazing and has been a huge help in bringing some sanity to collection views for me, thank you!

I'm migrating a project from Cocoapods to SPM and I noticed that this package produces the following warning in Xcode 12:

The iOS Simulator deployment target 'IPHONEOS_DEPLOYMENT_TARGET' is 
set to 8.0, but the range of supported deployment target versions
is 9.0 to 14.0.99.

It seems there is an easy way to fix this, but it needs to be done from the package side. I'm a bit clueless about Swift packages, or I'd submit a PR, but the info here seems simple enough and should fix this issue: https://josephduffy.co.uk/posts/supporting-multiple-swift-package-versions-without-breaking-compatibility

I hope I'm making some sense - If I'm just not understanding SPM well enough, please feel free to close this and ignore me :)

Current API only supports diffs of two arrays. But iOS table views and collection views often needs support for sections. It can be represented as array of arrays.

Is it possible to add support for diff of array of arrays?

Hi,
Thanks for the great work done on this. I'm running into an issue adding a new section that did not exist in the first place. Is there any way to handle a diff such that it creates a new section altoegther and then inserts the diff row ?

Error is below.
Invalid update: invalid number of sections. The number of sections contained in the collection view after the update (2) must be equal to the number of sections contained in the collection view before the update (1), plus or minus the number of sections inserted or deleted (0 inserted, 0 deleted).

I am using ver.1.1.1 and the app crashes sometimes with:

Terminating app due to uncaught exception 'NSInternalInconsistencyException', reason: 'attempt to delete row 0 from section 0, but there are only 0 sections before the update'

Has this been fixed in 1.1.2? I saw here that it could take a while to fix: https://medium.com/flawless-app-stories/a-better-way-to-update-uicollectionview-data-in-swift-with-diff-framework-924db158db86

Hi,

I have a problem with the Hecker algorithm, I think it doesn't detect replaces correctly. A simple example:

diff(old: Array("abc"), new: Array("adc"))
This will return delete at 1 and insert at 1.

Using WagnerFischer, it works as expected:
diff(old: Array("abc"), new: Array("adc"), algorithm: WagnerFischer())
This returns replace at 1.

Is this algorithm specific or just a bug?

Thanks!

I found this problem when I wrote a comparison in the README of my diffing library DifferenceKit.

As described in the Apple document, it's obviously wrong to use hashValue to identify the elements.

In heckel algorithm, It's necessary to use Hashable compliant object itself for the key of symbolic-table.
Since this has a big impact on performance, you should also update the README.

I know that this issue duplicated with #13.
Why did you close it?

Pod has a lot of warnings. Could you update to swift 5 and create public tag in repo and update podspec file?

In your list of examples, you have this piece of code:

let old = Array("abcd")
let new = Array("adbc")
let changes = diff(old: old, new: new)

// Move "d" from index 3 to index 1

Is this indeed correct or was this before introducing the Heckel algorithm?

Haven't verified this, but doesn't Heckel produce all three moves in this case? I.e.:

// Move "d" from index 3 to index 1
// Move "b" from index 1 to index 2
// Move "c" from index 2 to index 3

I made a PR to this end. It can be useful when looking at changes while hiding private implementation. See #33 .

I need make custom reload cell animation.
How can i get reloading indices instead of insertion and deletion pairs?

For some reason, even if you specify reload(replacementAnimations: .none) the tableView still updates the item with an animation the first time it replaces it.

It seems that stackoverflow suggests wrapping the reloadRows logic in a UIView.performWithoutAnimation {} ` block. Could you handle this case @onmyway133 ?

Cant use this class 'IndexPathConverter' in my project.
have installed the pod using:-- pod 'DeepDiff'

on Xcode 9.3 and using swift 4
pod --version
1.5.2

hey! I was surprised to see that Heckel didn't have static functions, and instead expects diffs to be carried out on an instance.
i noticed that in my usage of the class, i have

    public func update(data: [ListSection], animating: Bool = false, completion: (() -> Void)? = nil) {
        if self.data.isNotEmpty {
            let diff = HeckelDiffingAlgorithm().diff(old: self.data, new: data)

where I create a new instance each time. Is that required? or can I create one instance and reuse it each time my data changes?

I propose simplifying the demo, so that it would be quicker to compile and run.
E.g. removing Texture from the UIKit demos.

E.g. "Hue" & "Anchors" could be dropped without increasing complexity...

In my situation, I make diffing between two different classes packaged by the same enum.
As:
enum PackagingEnum: DiffAware {
case a(ClassA)
case b(ClassB)

var diffId: Int {
    switch self {
    case a(let classA):
        return classA.hashValue
    case b(let classB)
        return classB.hashValue
    }
}

}
in this case, I want to make diffing [ClassA] to [ClassB] via DeepDiff.

but when I get the changes by 'diff(old: [Enum-B], new: [Enum-A])'

I traverse the changes, and invoke 'insert/remove/move' in [Enum-B](the old), I get crashed because of 'Out of Range'

hi! wondering if you'd be able to set the Build Libraries For Distribution flag to YES in the project's build settings. i use deep diff through Carthage and this would help to ensure support for new swift versions which seem to come with every new xcode release.

thank you !

public inits for all types please

Hi,

Is it possible to have diffId be a function that returns an Int instead of it being a var. I'm running into the issue of the following: I have a BaseWrapper class, that holds an item and a cell basically for collecitonview rendering.

This Basewrapper is being extended by different types. Bassically each cell has a wrapper that corresponds to it.

When I call commitUpdate on my collectionview it will diff the oldwrappers from the newwrappers.

However there is no way for me to se the diffId unique for each wrapper implementation because diffId is there before self is.

Can i make the implementation of BaseWrapper responsible for supplying diffId? but still be able to call diff(old: [BaseWrapper], new: [BaseWrapper])

I gets crash:
Terminating app due to uncaught exception 'NSInternalInconsistencyException', reason: 'attempt to delete item 20 from section 0 which only contains 20 items before the update'

My changes:
First Changes
insert(0), insert(1), insert(2), insert(3), insert(4), insert(5), insert(6), insert(7), insert(8), insert(9), insert(10), insert(11), insert(12), insert(13), insert(14), insert(15), insert(16), insert(17), insert(18), insert(19)
Second Changes
insert(0), insert(1), insert(2), insert(3), insert(4), insert(5), insert(6), insert(7), insert(8), insert(9), insert(10), insert(11), insert(12), insert(13), insert(14), insert(15), insert(16), insert(17), insert(18), insert(19), update(20(was 0))
Crash!

I think changes update(20) should be update(0). Maybe collection view sees the changed items before inserted

Hi,

First of all thanks a lot for such useful library. I have a list interface which loads old items on scroll. My problem is after applying changes i am collectionView is loosing the current position after inserting new items above. To overcome i applied a technique i found in SO but it causes a flicker effect. Here what i used:

let contentHeight = collectionView!.contentSize.height
let offsetY = collectionView!.contentOffset.y
let bottomOffset = contentHeight - offsetY

let changes = diff(old: messages.old, new: messages.new)
collectionView!.reload(changes: changes, section: 0, completion: { _ in
    self.collectionView!.contentOffset = CGPoint(x: 0, y: self.collectionView!.contentSize.height - bottomOffset)
    })

Any suggestions?

Best

Hey! We're trying to use DeepDiff with UIStackView which does not offer batch updates support as UITableView and UICollectionView. This means that when we get an insert we insert a new arrangedSubview, when we get a delete we delete it, and so on.

We narrowed down the problem to the following example:

var old = ["Category3", "Category2", "Category4", "Category5", "Category1"]
let new = ["Category1", "Category2", "Category3", "Category4", "Category5"]

let algorithm = WagnerFischer<String>()
let changes = algorithm.diff(old: old, new: new)

changes.forEach { change in
    switch change {
    case .insert(let info):
        old.insert(info.item, at: info.index)
    case .delete(let info):
        old.remove(at: info.index)
    case .move(let info):
        old.remove(at: info.fromIndex)
        old.insert(info.item, at: info.toIndex)
    case .replace(let info):
        old.remove(at: info.index)
        old.insert(info.newItem, at: info.index)
    }
}

print(old) // ["Category1", "Category2", "Category3", "Category4", "Category1"]

(lldb) po changes
▿ replace : Replace<String>
  - oldItem : "Category3"
  - newItem : "Category1"
  - index : 0
▿ insert : Insert<String>
  - item : "Category3"
  - index : 2
▿ delete : Delete<String>
  - item : "Category1"
  - index : 4

As you can see the output is not correct.
We're probably missing something at some point but cannot identify where.

Let us know. Thanks!

For example, in my code i have a very common case:

protocol BaseClassProtocol { }
class ConcreteClass1: BaseClassProtocol { } 
class ConcreteClass2: BaseClassProtocol { }

Anywere in my codebase, there is only BaseClassProtocol being used. For example:

let array:[BaseClassProtocol] = ...

this array contains various classes/structs with the same protocol.
How can I apply DeepDiff library and DiffAware protocol to compare various arrays of BaseClassProtocol objects?

I suggest making the completion handler optional, similar to the other Cocoa Touch API, e.g. UIVIew Animation or UIViewController presentation to keep it consistent.

Hey @onmyway133

I've faced a crash when using sections in UITableView. I have a regular controller with some array of data

var data: Array<ParticipantData> = []

By design I want to use each item of this array as a section and inner array (items) as rows in this section. Here is ParticipantData:

class ParticipantData {
 let id: Int
 let items: Array<Item>

    class func compareContent(_ a: ParticipantData, _ b: ParticipantData) -> Bool {
       // Compare ids and items
        return a.id == b.id && Comparator.compare(a.items, b.items)
    }

    public var diffId: Int {
        return self.id
    }
}

For calculating difference between collections I'm calling following code:

if (!newData.isEmpty) {
               // Calculate diff between old and new data
                let changes = diff(old: self.data, new: newData)

               // deliver results
              // Neither section: self.data.count nor newData.count works
                self.tableView.reload(changes: changes, section: self.data.count, replacementAnimation: UITableView.RowAnimation.none, updateData: {
                    self.data = newData
                })
} else {
               // Tried a fix with reloading data when it's empty
                self.tableView.reloadData()
}

And code which is responsible for displaying sections and rows:

extension MainController: UITableViewDataSource, UITableViewDelegate {
    public func tableView(_ tableView: UITableView, numberOfRowsInSection section: Int) -> Int {
       // Each section has as many rows as it has items 
       return data[section].items.count
    }

    public func tableView(_ tableView: UITableView, cellForRowAt indexPath: IndexPath) -> UITableViewCell {
        let cell = UITableViewCell()
        cell.textLabel?.text = "\(indexPath.section): \(indexPath.row)"
        return cell
    }

    public func numberOfSections(in tableView: UITableView) -> Int {
        // We have as many sections as items in array
        return data.count
    }

    public func tableView(_ tableView: UITableView, titleForHeaderInSection section: Int) -> String? {
        return "Title"
    }
}

As result I have a crash
'NSInternalInconsistencyException', reason: 'Invalid update: invalid number of sections. The number of sections contained in the table view after the update (1) must be equal to the number of sections contained in the table view before the update (0), plus or minus the number of sections inserted or deleted (0 inserted, 0 deleted).'

Interesting thing: it's working when there is no numberOfSections method

I have try to make extension for ASTableNode & ASCollectionNode (both from ASDK) with DeepDiff.
So the ChangeWithIndexPath, IndexPathConverter & Array.executeIfPresent need to be public.

Could you make it happen?

Wondering what the impact is of replicating the reload logic from the UICollectionView+Extensions with the corresponding section-updating methods (reloadSections, deleteSections, insertSections, moveSections). I could submit a PR for this if this change hasn't been scoped out or hasn't been intentionally omitted.

Can also please add "append" method, it will be very useful for pagination.
I want to do pagination in tableView by appending data to the existing array.

Can you please guide me ?

Hello,

Should I implement diifId If object is already conforming Hashable? I am using RealmSwift and my class conforms Object protocol which also conforms Hashable. My problem is that I have an unique string as primary key and that value is used as hashValue. (I don't know how Realm handles it). Therefore, I believe It generates unique int from that string which is used on hash function. When I add below code, I can't be sure If id is unique every time. Therefore, I don't wanna add it.

    var diffId: Int {
        return identifier.hashValue
    }

HI,
is it possible to use DeepDiff with NSFetchedResultsController and UICollectionView to update cells when CoreData updates? I couldnt figure it out by myself.
Thank You

invalidManifestFormat("/var/folders/6q/wgy6jtp12w5gzgm9lzcglpqw0000gn/T/TemporaryFile.rCB6P4.swift:11:19: error: 'v6' is unavailable\n .watchOS(.v6)\n ^~\nPackageDescription.SupportedPlatform:45:27: note: 'v6' was introduced in PackageDescription 5.1\n public static var v6: PackageDescription.SupportedPlatform.WatchOSVersion\n ^", diagnosticFile: Optional(AbsolutePath:"/Users/vagrant/Library/Developer/Xcode/DerivedData/Harper-cxngxloxijxbllfwrovkiaxoqvem/SourcePackages/ManifestLoading/deepdiff.dia")) in https://github.com/onmyway133/DeepDiff

Introduced in 2.3.2.

Caused by this change: 86d6b51#diff-f913940c58e8744a2af1c68b909bb6383e49007e6c5a12fb03104a9006ae677eR11

I'm not getting this on all versions of Xcode. For example, it's working on Xcode 12.5 RC on my machine. But it fails consistently on Bitrise with Xcode 12.4 and 12.5.

Hi @onmyway133 ,

I am using DeepDiff and I have the following problem I can't figure out what is wrong:

I have a class (Hashable):

class Foo: Hashable {
let models: [String]
}

In the begging I have one instance of class Foo called A in an array and DeepDiff correctly instructs for an insert as the initial state is an empty uitableview. Then I have two instances of class Foo called A and B in the following order: [B, A], and DeepDiff correctly instructs for an insert for instance B but for instance A it doesn't instruct anything ex. move. I am missing something? Is this a bug?

Wondering why reload requires Hashable as a generic constraint, since changes are generated using DiffAware and reload never refers to any Hashable property within T.

WagnerFischer.swift:25:22 use of unresolved identifier 'DeepDiff'

log info

/Users/~~~/Carthage/Checkouts/DeepDiff/Sources/Shared/Algorithms/WagnerFischer.swift:25:22: error: use of unresolved identifier 'DeepDiff'
    if let changes = DeepDiff.preprocess(old: old, new: new) {
                     ^~~~~~~~

I would love to use this library, but I can't build it for Mojave! It seems like a fairly simple pure-swift library, is there any reason it couldn't support older versions of macOS?

Hi. I think the last version number 3.2.3 (tag) should have been named 2.3.3, not 3.2.3.

Initial state:
3 sections, the first one contains one row, other contain 2 rows

Destination state:
all the sections except of the first one are removed

Error:
attempt to delete row 2 from section 0 which only contains 1 rows before the update

Additionally: how diff(old:new:) works if it tries to delete and reinsert the first section - extra action?!