Sometimes I have a crash when one item is deleted and another one is inserted in the same section. Their diff identifiers are not equal. It looks that issue occurs when a table view is updated the second time or later (not the first).

The data structure looks in the following way. before = [s1 :[1, 2], s2: [3]] current = [s1 :[1, 2], s2: [4]]

So library calculates only delete of 3 in the section s2, but not insert of 4.

I don't have a good sample yet. But I'll do as soon as I catch it during debug.

In some edge cases, the AppKit extension (and possibly UIKit extension) will produce duplicate items:

https://user-images.githubusercontent.com/121539/153323882-db1cb3dc-8d8f-4dce-8ea3-4105b3a2e4fc.mov

Example:

StagedChangeset(source: ["1","3"], target: ["3","2","1"])

This will produce the following changeset:

▿ [
    Changeset(
        data: [
            3,
            2,
            1
        ],
        elementInserted: [
            [element: 1, section: 0]
        ],
        elementMoved: [
            (source: [element: 1, section: 0], target: [element: 0, section: 0])
        ]
    )
]

The current implementation, as found here: https://github.com/ra1028/DifferenceKit/blob/62745d7780deef4a023a792a1f8f763ec7bf9705/Sources/Extensions/AppKitExtension.swift#L50-L91

will execute the following actions:

removeRows [[element: 1, section: 0]]
InsertRows [[element: 1, section: 0]]
Move [element: 1, section: 0] [element: 0, section: 0]
viewFor:row 0 😂

(The code that produced those logs can be found here: https://github.com/paxos/DifferenceKit/pull/1)

The problem: AppKit will ask the datasource for the element at position 0, while it should ask for the element at position 1. It turns out that, if you add a new element and then move it (before calling endUpdates()), AppKit will request the element from the new position.

Possible solution

A possible solution could be to change the order of things, for example:

view.beginUpdates()
handleDeletes…
handleInserts…
view.endUpdates() <-- this will cause AppKit to reach out to the datasource with the correct index
view.beginUpdates()
handleMoves…
view.endUpdates

https://user-images.githubusercontent.com/121539/153324303-c2032ce6-87af-466b-a628-a25720cd6bfe.mov

Checklist

• [x] This is not a Apple's bug.
• [x] Reviewed the README and documents.
• [X] Searched existing issues for ensure not duplicated.

This resolves #54. I also added the Swift 5 changes that are needed as well; those are gated by #if swift(5.0). Other changes should be backwards compatible with 4.2.x versions of Swift with Xcode 10.

I am integrating differencekit with asyncdisplaykit's collectionNode in my application. I followed the instructions as mentioned in the doc and examples. But getting weird error I couldn't figure out where exactly it is happening. Normal reloadData() works perfectly fine. But using

//self is a ASCollectionNode
self.view.reload(using: changeset) { (data) in
                    self.products = newValue
                }

Making the application to crash.

*** Terminating app due to uncaught exception 'NSInvalidArgumentException', reason: '*** -[__NSDictionaryM setObject:forKey:]: key cannot be nil'
*** First throw call stack:
(
	0   CoreFoundation                      0x0000000102e9b1e6 __exceptionPreprocess + 294
	1   libobjc.A.dylib                     0x0000000101feb031 objc_exception_throw + 48
	2   CoreFoundation                      0x0000000102edb0bc _CFThrowFormattedException + 194
	3   CoreFoundation                      0x0000000102dae72a -[__NSDictionaryM setObject:forKey:] + 1002
	4   UIKit                               0x00000001044faf07 -[UICollectionView _setVisibleView:forLayoutAttributes:] + 171
	5   UIKit                               0x0000000104513dcb __71-[UICollectionView _updateWithItems:tentativelyForReordering:animator:]_block_invoke.1997 + 744
	6   UIKit                               0x0000000103aef537 +[UIView(UIViewAnimationWithBlocks) _setupAnimationWithDuration:delay:view:options:factory:animations:start:animationStateGenerator:completion:] + 560
	7   UIKit                               0x0000000103aefa0f +[UIView(UIViewAnimationWithBlocks) animateWithDuration:delay:options:animations:completion:] + 99
	8   UIKit                               0x00000001045130f5 -[UICollectionView _updateWithItems:tentativelyForReordering:animator:] + 6349
	9   UIKit                               0x000000010450ccc3 -[UICollectionView _endItemAnimationsWithInvalidationContext:tentativelyForReordering:animator:] + 17420
	10  UIKit                               0x000000010451500e -[UICollectionView _endUpdatesWithInvalidationContext:tentativelyForReordering:animator:] + 71
	11  UIKit                               0x0000000104515357 -[UICollectionView _performBatchUpdates:completion:invalidationContext:tentativelyForReordering:animator:] + 439
	12  UIKit                               0x000000010451517d -[UICollectionView _performBatchUpdates:completion:invalidationContext:tentativelyForReordering:] + 91
	13  UIKit                               0x00000001045150ff -[UICollectionView _performBatchUpdates:completion:invalidationContext:] + 74
	14  UIKit                               0x0000000104515054 -[UICollectionView performBatchUpdates:completion:] + 53
	15  AsyncDisplayKit                     0x0000000100cd3e3b -[ASCollectionView _superPerformBatchUpdates:completion:] + 571
	16  AsyncDisplayKit                     0x0000000100ce9552 __64-[ASCollectionView rangeController:updateWithChangeSet:updates:]_block_invoke + 882
	17  AsyncDisplayKit                     0x0000000100ce91ab _ZL30ASPerformBlockWithoutAnimationbU13block_pointerFvvE + 123
	18  AsyncDisplayKit                     0x0000000100ce8e83 -[ASCollectionView rangeController:updateWithChangeSet:updates:] + 3859
	19  AsyncDisplayKit                     0x0000000100df694d -[ASRangeController dataController:updateWithChangeSet:updates:] + 717
	20  AsyncDisplayKit                     0x0000000100d02bf6 __40-[ASDataController updateWithChangeSet:]_block_invoke_2.224 + 230
	21  AsyncDisplayKit                     0x0000000100dcb0b4 __30-[ASMainSerialQueue runBlocks]_block_invoke + 308
	22  libdispatch.dylib                   0x00000001075c27ab _dispatch_call_block_and_release + 12
	23  libdispatch.dylib                   0x00000001075c37ec _dispatch_client_callout + 8
	24  libdispatch.dylib                   0x00000001075ce8cf _dispatch_main_queue_callback_4CF + 628
	25  CoreFoundation                      0x0000000102e5dc99 __CFRUNLOOP_IS_SERVICING_THE_MAIN_DISPATCH_QUEUE__ + 9
	26  CoreFoundation                      0x0000000102e21ea6 __CFRunLoopRun + 2342
	27  CoreFoundation                      0x0000000102e2130b CFRunLoopRunSpecific + 635
	28  GraphicsServices                    0x000000010ae53a73 GSEventRunModal + 62
	29  UIKit                               0x0000000103a2d057 UIApplicationMain + 159
	30  Sodimac                             0x0000000100705027 main + 55
	31  libdyld.dylib                       0x0000000107640955 start + 1
	32  ???                                 0x0000000000000001 0x0 + 1
)
libc++abi.dylib: terminating with uncaught exception of type NSException

I don't know what I am missing. Any help would be much appreciated. Thanks in advance.

Checklist

• [X] This is not a Apple's bug.
• [X] Reviewed the README and documents.
• [X] Searched existing issues for ensure not duplicated.

Example Test Scenario

    func testMovedIssue() {
        let section = 1
        
        let source1 = [1, 2, 3]
        let target1 = [3, 2, 1]

        // Test1: This test passes, but it should fail.
        XCTAssertExactDifferences(
            source: source1,
            target: target1,
            section: section,
            expected: [
                Changeset(
                    data: target1,
                    elementMoved: [
                        (source: ElementPath(element: 2, section: section), target: ElementPath(element: 0, section: section)),
                        (source: ElementPath(element: 1, section: section), target: ElementPath(element: 1, section: section)),
                    ]
                )
            ]
        )
        
        // Test2: This test fails, but it should pass.
        XCTAssertExactDifferences(
            source: source1,
            target: target1,
            section: section,
            expected: [
                Changeset(
                    data: target1,
                    elementMoved: [
                        (source: ElementPath(element: 2, section: section), target: ElementPath(element: 0, section: section)),
                    ]
                )
            ]
        )
    }

Expected Behavior

Test1 should fail, Test2 should pass.

Moves contains (2 -> 0), (1 -> 1).

Current Behavior

Test1 passes, Test2 fails.

Moves should contain (2 -> 0).

Steps to Reproduce

Add the test I wrote above and run the unit tests.

Detailed Description (Include Screenshots)

Moving the item from the same index to the same index should always be unnecessary. In general optimizing to make moves correct and minimal is preferred.

Environments

• Library version: Master

• Swift version: 4.2

• iOS version: 12

• Xcode version: 10.1

• Devices/Simulators: DifferenceKit, "My Mac", CMD+U

• CocoaPods/Carthage version: N/A

I created a blank swift 4.2 project with Xcode 10.2 & cocoapods 1.6.0 and I specified the following Podfile:

platform :ios, '11.0'

target 'Test' do
  use_frameworks!

  pod 'DifferenceKit', '~> 1.0'

end

The project does not compile.

The DifferenceKit project compiles correctly on Xcode 10.2. So it seems to be only related to cocoapods.

While NSOutlineView is a subclass of NSTableView, the existing NSTableView extension is insufficient if you're using an NSOutlineView, because it has its own insertion/deletion/reload API.

I want my collection handle multiple sections with different Items.

Section1: Int Section2: String

how is it possible? you have showcased one section with multiple items with AnyDifferentiable, but what about multiple sections with multiple types.

Thanks for releasing DifferenceKit, it looks really cool.

I’m the author of Changeset, another fairly popular lightweight diffing framework. When you have the time, maybe I can persuade you to include it in your comparison?

Thanks in advance.

Fixes #139.

A while ago I was working on a simple one-level animatable NSOutlineView (similar to the Finder's sidebar) powered by DifferenceKit, and I remember I stumbled upon issues trying to get the row move animation to work reliably for arbitrary move/delete/insert operations.

After lots of experimentation and debugging I finally found and fixed the problem which was affecting NSTableView in the same way so I decided now to take the time and share this story with you, mainly because at the time I was working on this, I didn't know there was an AppKit extension in the project here which suffers from the same problems I had.

As it turns out, NSTableView/NSOutlineView's beginUpdates() and endUpdates() methods do not really do batch updates. It rather seems like they just offer animation optimizations, as described in the method's discussion part of the Apple docs:

The main reason for doing a batch update of changes to a table view is to avoid having the table animate unnecessarily.

What that means is, in contrast to NSCollectionViews performBatchUpdates(), it inserts, deletes and moves elements immediately, updating any row index after every operation which is why the current implementation is unable to move elements to the correct positions and under certain scenarios even unable to correctly insert new elements either.

With that in mind, a potential solution was relatively simple to implement. Provided that move changes are always sorted ascendingly by their target index which is always the case for changesets generated by DifferenceKit (and potentially other diffing frameworks), here's a hopefully complete list of index issues and how to solve them:

1. Moves

Problem

As mentioned, NSTableView doesn't do batch updating so one change will immediately change element indexes, resulting in past moves messing with the source index of future moves.

Solution

Whenever an element is moved, its source index must be offset by the total number of previous moves' source indexes that were greater than (visually speaking below) itself.

In the code, that means having to collect the moved source indexes and checking how many elements with a source index greater than the current move's source index are contained. This number represents the offset to be added to the source index of each move.

Example

Source: ["D", "C", "B", "A"] Target: ["A", "B", "C", "D"] Moves: (3, 0), (2, 1), (1, 2)

NSTableView will incorrectly produce: ["A", "D", "C", "B"] because after it has moved A -> 0, subsequent moves with a source index greater than 0 (which in this example are all elements), will be off by the number of moves made above it. Here's the list of incorrect moves NSTableView does for this changeset:

1st Move: (3, 0) -> ["A", "D", "C", "B"] - OK 2nd Move: (2, 1) -> ["A", "C", "D", "B"] - source index off by one, should be (3, 1) -> ["A", "B", "D", "C"] 3rd Move: (1, 2) -> ["A", "D", "C", "B"] - source index off by two, should be (3, 2) -> ["A", "B", "C", "D"]

2. Moves with inserts

Problem

As part of DifferenceKit's 3rd stage changeset, not only are elements moved but also new ones inserted which then messes with the target index of the moves.

Solution

Applying moves after inserts is the first mistake because not only does a move to an index above an inserted element consequently move down all elements below, creating many additional unwanted moves (from which recovery would not be easily possible I guess) which change the actual target index of a move that is below the inserted element but it also changes the source index of every element to-be-moved that is below an inserted element.

So to be able to properly move elements, inserts must be deferred until after all moves were made and then processed ascendingly by the element's index to avoid scrambling with the indexes even further, which however, seems to be always the case for DifferenceKit changesets, so no extra sorting needed here.

Now that elements are inserted after the moves, the second issue must be taken care of which is that moves provided by DifferenceKit's diffing algorithm already account for the inserted indexes but since the items haven't been inserted yet and table views can't have "holes" in it, every target index of a move that is below an inserted element will be offset by the number of inserted elements above it.

To fix this, a list of all insert indexes can be created in advance which is then used during a move to determine how many elements are going to be inserted above the move's target index. This number represents the offset and must be subtracted from the target index of a move to allow for performing all move operations according to the changeset.

Example

For this example, it is already assumed that inserts are made after moves because otherwise, the correct order cannot be restored, not even by simple index adjustments.

Source: ["D", "C", "B"] Target: ["A", "B", "C", "D"] Moves: (2, 1), (1, 2) Inserts: ("A", 0)

NSTableView will incorrectly produce ["A", "D", "C", "B"] because due to the insert of A -> 0 every move's target index greater than 0 (in our case every element) will be off by one, in addition to the first move causing an offset by one for the second move, due to the mentioned first problem when moving items. Again, here's the list of incorrect moves NSTableView does for this changeset:

1st move: (2, 1) -> ["D", "B", "C"] - source index off by one, should be (3, 1) -> ["B", "D", "C"] 2nd move: (1, 2) -> ["D", "C", "B"] - source & target index off by one, should be (2, 1) -> ["B", "C", "D"] Insert: ("A", 0) -> ["A", "D", "C", "B"] - OK (will then be ["A", "B", "C", "D"] for the corrected moves)

Note that by ensuring inserts come after moves, inserted elements will already be at the correct position but without applying both offsets to every move, the order will be incorrect.

Screenshot

Here's a screenshot for comparison with the fix applied on the right. The source is a scrambled alphanumeric character set that is missing the letters B, C, F, K, U, W, numbers 1, 4, 7 and includes the emojis 😀, 😁, 😂. 😃, 😄, 😅, 😆, 😇: ["J", "😁", "E", "T", "6", "😆", "😂", "😃", "M", "I", "2", "😇", "😅", "O", "G", "H", "0", "😄", "5", "V", "Z", "D", "R", "9", "8", "3", "Q", "S", "L", "Y", "A", "X", "P", "😀", "N"]

The target is the alphanumeric character set: ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"]

Some notes

By using Swift's IndexSet I was able to reduce the performance overhead a bit so that in the end, this extra logic should be tolerable, considering that the biggest portion of computation time is probably being consumed by the AppKit anyway, but I haven't specifically tested that yet.

During my tests, I've frequently shuffled the emoji dataset in the sample project while also trying out datasets with random inserts, moves and deletions and I could not find any mistakes in the resulting table view. Real tests comparing the data set with the actual NSTableView cells however, would be more appropriate, of course. Note that while trying to break the table view's animations by quickly shuffling many times in a row, I was able to partially scramble the NSCollectionView's order, the table view's animations though seemed very robust to me so it looks like it's just NSCollectionView's performBatchUpdates not being able to handle too many move/insert/delete operations in a row very well.

Before I forget it, awesome project by the way, really appreciate it and thanks for reading this long story, of course! 🤓

TL;DR

NSTableView doesn't support batch updating so every change (insert, delete, move) may alter its row indexes, making it difficult to apply moves generated from a StagedChangeset unless indexes are corrected accordingly and it is ensured that inserts are always performed after any moves.

Checklist

• [x] All tests are passed.
• [ ] Added tests.
• [x] Documented the code using Xcode markup.
• [x] Searched existing pull requests for ensure not duplicated.
• [x] Updated Example

Description

As discussed in https://github.com/ra1028/DiffableDataSources/pull/10 a completion block is needed in DiffableDataSource to mirror Apple's APIs as closely as possible. Moreover, having a completion block when Differences are applied might be very handy for client to have.

Related Issue

https://github.com/ra1028/DiffableDataSources/pull/10

Motivation and Context

Provides better usage of the API with having a Completion block.

Impact on Existing Code

APIs will not break as the completion block is Optional and defaulted to nil

Checklist

• [x] Reviewed the README and documents.
• [x] Searched existing issues for ensure not duplicated.

Expected Behavior

The docs (README) specifies that:

There are default implementations of Differentiable for the types that conforming to Equatable [or] Hashable

Current Behavior

Differentiable is defined as such:

public typealias Differentiable = ContentIdentifiable & ContentEquatable

Detailed Description (Include Screenshots)

This discrepancy cost me a few days of refactoring, due to having many nested types that aren't all Equatable or Hashable. I conformed them to Equatable, and theoretically they should be Differentiable, but they don't seem to be. Any advice or workarounds appreciated here, but, this seems like a difference between the docs + code.

Environment

• Library version: 1.1.5

• Swift version: 5.7

• iOS version: 16.0

• Xcode version: 14.0

• Devices/Simulators: Sim

• CocoaPods/Carthage version: 1.11.3

If I have two arrays like below:

A: [a, b, c]
B: [b, c, a]

the diff result will be:

[
(source:1, target:0),
(source:2,target:1)
]

In fact, we just need 1 move:

(source:0, target 2)

Is this algorithm not able to get best diff results?

Checklist

• [x] This is not a Apple's bug.
• [x] Reviewed the README and documents.
• [x] Searched existing issues for ensure not duplicated.

Expected Behavior

DifferenceKit should be crash-free

Current Behavior

Our application is getting crash reports related to Difference Kit UICollectionView.reload<A>(using:interrupt:setData:) (UIKitExtension.swift:0)

Detailed Description (Include Screenshots)

Our developers are unable to reproduce locally but we are seeing increasing crash rates in our analytics. We realize we have limited information to diagnose but any advice or suggestions would be appreciated.

Environments

• Library version: 1.3.0

• Swift version: 5

• iOS version: tvOS 15.6

• Xcode version: 13.2.1

Bumps tzinfo from 1.2.5 to 1.2.10.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Bumps tzinfo from 1.2.5 to 1.2.10.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Checklist

• [x] This is not a Apple's bug.
• [x] Reviewed the README and documents.
• [x] Searched existing issues for ensure not duplicated.

Current Behavior

When performing a NSTableView.reload a reloadRowsAnimation can be specified but this is not a valid option for a reloadData operation

Expected Behavior

That parameter should be removed.