Changeset produces bad edit steps, crashes UICollectionView.

[bwhiteley]

I have a couple of examples of edit steps that are incorrect.

'64927513' -> '917546832':
delete 4 at index 1
replace with 1 at index 1
replace with 4 at index 4
move 6 from index 0 to 5
insert 8 at index 6
insert 2 at index 8
UICollectionView error: attempt to delete and reload the same index path (path = 0 - 1)

'8C9A2574361B' -> '897A34B215C6':
replace with 3 at index 4
delete 5 at index 5
move 7 from index 6 to 2
replace with B at index 6
replace with 2 at index 7
replace with 5 at index 9
move C from index 1 to 10
insert 6 at index 11
UICollectionView error: attempt to perform a delete and a move from the same index path (path = 0 - 6)

[hfossli]

Do you need to commit each step? Are you doing all in one edit block?

[bwhiteley]

All edits are performed in performBatchUpdates.

[hfossli]

Have you tried to do each step in its own performBatchUpdates? Or won't it make a difference?

[bwhiteley]

You don't need to run them through a collection view to see that they are wrong. Just try the edits yourself and you'll see they don't produce the target. Or just look at the first two edits of the first example.

[osteslag]

@bwhiteley, I have drafted an extension on UITableView and UICollectionView (see this Gist). I have only used it lightly in my app so far, and I am not using it on UICollectionView at all at the moment. So even though I have not encountered any misbehaviour, there may very well be bugs in it. You would call it like this: tableView.updateWithEdits(changeset.edits, inSection: 0)

A couple of questions:

1. How does your code look?
2. How should the changeset have looked in order to work as expected?
3. Can you point out what/where the Changeset bug is?

Thanks,
Joachim

[osteslag]

The problem may be with the order in which you do your edits, @bwhiteley, or maybe UICollectionView applies changes differently than UITableView. I haven’t checked. Keep in mind this paragraph from the README:

In short; first all deletions are made relative to the source collection, then, relative to the resulting collection, insertions and substitutions. A move is just a deletion followed by an insertion on the resulting collection. This is explained in much more detail under Batch Insertion, Deletion, and Reloading of Rows and Sections in Apple’s Table View Programming Guide for iOS.

Back to your comment:

You don't need to run them through a collection view to see that they are wrong. Just try the edits yourself and you'll see they don't produce the target. Or just look at the first two edits of the first example.

OK, let’s check it out and play back the edits in the order dictated by Apple’s documentation, first the deletions:

Step	Edit	Input	Output
1	delete 4 at index 1	64927513	6927513
2	delete 6 at index 0	6927513	927513

Note that step 2 is the deletion part of the move. We will do the insertion part in step 5 below. In the resulting array, we now do the insertions and replacements:

Step	Edit	Input	Output
3	replace with 1 at index 1	927513	917513
4	replace with 4 at index 4	917513	917543
5	insert 6 at 5	917543	9175463
6	insert 8 at index 6	9175463	91754683
7	insert 2 at index 8	91754683	917546832

In both table views and collection views, there are move commands. I would expect that to “just work” like the individual steps above, but I haven’t checked. But maybe that’s what causes the problem.

In case one doesn’t want to use moves, I could easily add a function argument to suppress the reduction of delete/insert edits of the same value. I have been been thinking about that for a while already.

[bwhiteley]

Thanks for looking into this.

I don't think the order matters inside performBatchUpdates. UICollectionView will reorder them as indicated in the docs. The indexPaths just need to be correct according to the order that UICollectionView will apply them.

My UICollectionView extension is similar to yours.

extension UICollectionView {
    /// Run this within `performBatchUpdates`
    public func applyEdits<T: Equatable> (edits: [Edit<T>],
                           numberOfOldSections:Int, numberOfNewSections:Int,
                           indexPathTransform:(index:Int) -> NSIndexPath) {
        var deletes:[NSIndexPath] = []
        var inserts:[NSIndexPath] = []
        var moves:[(NSIndexPath, NSIndexPath)] = []
        var reloads:[NSIndexPath] = []

        if numberOfNewSections > numberOfOldSections {
            let range = NSRange(location: numberOfOldSections, length: numberOfNewSections - numberOfOldSections)
            self.insertSections(NSIndexSet(indexesInRange: range))
        } else if numberOfNewSections < numberOfOldSections {
            let range = NSRange(location: numberOfNewSections, length: numberOfOldSections - numberOfNewSections)
            self.deleteSections(NSIndexSet(indexesInRange: range))
        }

        edits.forEach { edit in
            switch edit.operation {
            case .Deletion:
                deletes.append(indexPathTransform(index: edit.destination))
            case .Insertion:
                inserts.append(indexPathTransform(index: edit.destination))
            case let .Move(origin):
                let originIndexPath = indexPathTransform(index: origin)
                let destinationIndexPath = indexPathTransform(index: edit.destination)
                if originIndexPath.section >= numberOfNewSections || destinationIndexPath.section >= numberOfOldSections {
                    // UICollectionView does not allow moves from deleted 
                    // sections or moves to inserted sections.
                    // https://github.com/wtmoose/TLIndexPathTools/issues/18
                    deletes.append(originIndexPath)
                    inserts.append(destinationIndexPath)
                } else {
                    moves.append((indexPathTransform(index: origin), indexPathTransform(index: edit.destination)))
                }
            case .Substitution:
                reloads.append(indexPathTransform(index: edit.destination))
            }
        }

        self.deleteItemsAtIndexPaths(deletes)
        self.insertItemsAtIndexPaths(inserts)
        self.reloadItemsAtIndexPaths(reloads)
        moves.forEach { (old, new) in
            self.moveItemAtIndexPath(old, toIndexPath: new)
        }
    }
}

Just for fun I switched to your UICollectionView extension and limited it to one section.

Here is a crash:
source: 5198427
target: 768952413
replace with 7 at index 0
replace with 6 at index 1
insert 8 at index 2
replace with 5 at index 4
insert 2 at index 5
replace with 1 at index 7
replace with 3 at index 8
2016-02-07 21:31:11.093 Notables[1424:82780] *** Assertion failure in -[UICollectionView _endItemAnimationsWithInvalidationContext:tentativelyForReordering:], /BuildRoot/Library/Caches/com.apple.xbs/Sources/UIKit_Sim/UIKit-3512.29.5/UICollectionView.m:4039
2016-02-07 21:31:11.102 *** Terminating app due to uncaught exception 'NSInternalInconsistencyException', reason: 'attempt to delete item 8 from section 0 which only contains 7 items before the update'

A naive implementation doesn't crash:

    public static func naiveEditDistance(source s: T, target t: T) -> [Edit<T.Generator.Element>] {
        var rv:[Edit<T.Generator.Element>] = []
        for (oldIndex, item) in s.enumerate() {
            guard let newIndex = t.indexOf(item) else {
                rv.append(Edit(.Deletion, value:item, destination:oldIndex))
                continue
            }
            let newIndexI = t.startIndex.distanceTo(newIndex)
            if newIndexI != oldIndex {
                rv.append(Edit(.Move(origin: oldIndex), value:item, destination:newIndexI))
            }
        }

        for (newIndex, item) in t.enumerate() {
            if !s.contains(item) {
                rv.append(Edit(.Insertion, value:item, destination:newIndex))
            }
        }
        return rv
    }   

[andreyz]

Can confirm that the original change set generation does cause crashes. The naive implementation from the comment before works reliably.

[andreyz]

@osteslag any thoughts or updates on the issue?

[osteslag]

@andreyz, I’ll start squeezing in some time this week. Unfortunately this collides with a major project I’m finishing up a work. You are welcome to work on the problem in the meantime, of course. Even just identifying where exactly the problem lies would speed things up.

These are some of the questions I start searching for answers to:

1. Why does it (seemingly) work on table views (I’ll be verifying this), but not on collection views?
2. Are the indices interpreted differently between the two view classes? In what way? (Hopefully not)
3. What should the changeset edits be in order for it to work as expected?

@bwhiteley’s “naïve” approach has the answer to the latter, I suspect.

[osteslag]

I have made a quick-fix for the problem that you can use until I can take the time to fully understand what’s happening and document the solution. It’s committed in 9fed7bb:

This commit is strictly experimental.

Substitutions are now recorded using indexes into the source collection, not the target.

Also, when used in conjunction with UITableView and UICollectionView data sources in the test app, moves are ignored and reported as separate deletes and inserts.

It would be interesting to see what indexes moves require in order to work.

Note, because indexes for substitutions have now changed, some tests will fail.

[osteslag]

@bwhiteley, @andreyz: This issue is now fixed in the v1.0.4 release.