Duplicate items with some edge cases in AppKitExtension

[paxos]

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

Screen.Recording.2022-02-09.at.18.12.02.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:

DifferenceKit/Sources/Extensions/AppKitExtension.swift

Lines 50 to 91 in 62745d7

	func reload<C>(
	using stagedChangeset: StagedChangeset<C>,
	deleteRowsAnimation: @autoclosure () -> NSTableView.AnimationOptions,
	insertRowsAnimation: @autoclosure () -> NSTableView.AnimationOptions,
	reloadRowsAnimation: @autoclosure () -> NSTableView.AnimationOptions,
	interrupt: ((Changeset<C>) -> Bool)? = nil,
	setData: (C) -> Void
	) {
	if case .none = window, let data = stagedChangeset.last?.data {
	setData(data)
	return reloadData()
	}
	for changeset in stagedChangeset {
	if let interrupt = interrupt, interrupt(changeset), let data = stagedChangeset.last?.data {
	setData(data)
	return reloadData()
	}
	beginUpdates()
	setData(changeset.data)
	if !changeset.elementDeleted.isEmpty {
	removeRows(at: IndexSet(changeset.elementDeleted.map { $0.element }), withAnimation: deleteRowsAnimation())
	}
	if !changeset.elementInserted.isEmpty {
	insertRows(at: IndexSet(changeset.elementInserted.map { $0.element }), withAnimation: insertRowsAnimation())
	}
	if !changeset.elementUpdated.isEmpty {
	reloadData(forRowIndexes: IndexSet(changeset.elementUpdated.map { $0.element }), columnIndexes: IndexSet(changeset.elementUpdated.map { $0.section }))
	}
	for (source, target) in changeset.elementMoved {
	moveRow(at: source.element, to: target.element)
	}
	endUpdates()
	}
	}
	}

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: paxos#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

Screen.Recording.2022-02-09.at.18.16.08.mov

Checklist

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

[paxos]

I found another sequence that does not produce the correct results:

StagedChangeset(source: ["1", "2", "3", "4", "5", "6", "7", "8", "9", "10"], target: ["5", "1", "7", "4", "2", "10"])

If this gets applied via AppKit extension tableView.reload, the result is as follow:

Should be: ["5", "1", "7", "4", "2", "10"]
But is: ["5", "1", "2", "7", "4", "10"]

[paxos]

I dont think any of the unit tests will capture this, as none of them check what the actual state is that AppKit ends up in. Any advice how this could be fixed?

Unfortunately, this is a serious issue and produces wrong results in some scenarios.

[paxos]

I added some code that compares data vs AppKit state and demonstrates the mentioned error sequence:

paxos#2

[martindufort]

Any resolution on this as I'm seeing the same issue in the Appkit extension.

[ra1028]

I actually am not quite familiar with AppKit and the AppKit extension was added by another developer in this PR. So I won't give you any good resolution on the issue but if the proposed way works in any cases including edge cases and it's proved somehow, I would accept it to merge.

[paxos]

The only working solution that I could find in the whole internet that is working reliably for AppKit was written by @GilesHammond and a version of it can be found here: paxos/NSOutlineViewPatchTestSuite#1

We added a test suite with randomized tests to verify this, and so far it has been working flawlessly.

[ra1028]

Interesting. It must be worth trying to incorporate into DifferenceKit if it really did pass 50k randomized test cases. Can you create a PR for it?

[paxos]

I am not sure. The solution is based on native Swift CollectionDifference.
I believe the steps returned by DifferenceKit are not 100% compatible with the Sequence that AppKit expects each step to get applied.

[tobiasjordan]

Can anyone run the 50k randomized test cases for my PR #144? Would be really great as I haven't found the time yet to implement some tests for my proposed solution.

[paxos]

@tobiasjordan I have updated the testsuite to use differencekit here:
https://github.com/paxos/NSOutlineViewPatchTestSuite/tree/use-differencekit

Your fix is used starting in 6a31c8ab9dfa3f0d84e90653ba6906bd8345cc19 and so far it looks promising. 10K run successfully, 50K is still running.

[paxos]

Update: 50K look good as well ✅

[GilesHammond]

Sorry Patrick. I’ve been slack on sharing this as a package! Would that be helpful in this case? Giles

…

On 27 May 2022, at 19:28, Patrick Dinger ***@***.***> wrote:  I am not sure. The solution is based on native Swift CollectionDifference. I believe the steps returned by DifferenceKit are not 100% compatible with the Sequence that AppKit expects each step to get applied. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.

[paxos]

Sorry Patrick. I’ve been slack on sharing this as a package! Would that be helpful in this case? Giles
…
On 27 May 2022, at 19:28, Patrick Dinger @.***> wrote:  I am not sure. The solution is based on native Swift CollectionDifference. I believe the steps returned by DifferenceKit are not 100% compatible with the Sequence that AppKit expects each step to get applied. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.

no worries, i am good for now! thanks