Objects with duplicate diffIdentifiers but different values break updates

[rnystrom]

This is a really weird case that I haven't spent a ton of time thinking about a fix. Without trying to explain too much, let me just paste a failing unit test added to the e2e tests.

- (void)test_ {
  [self setupWithObjects:@[
                           // using string values IGTestDelegateController always returns 1 cell
                           genTestObject(@1, @"a"),
                           genTestObject(@2, @"a"),
                           genTestObject(@3, @"a"),
                           genTestObject(@4, @"b"), // problem item w/ key 4, value "b"
                           ]];

  // delete the last object from the original array
  self.dataSource.objects = @[
                              genTestObject(@1, @"a"),
                              genTestObject(@5, @"a"),
                              genTestObject(@6, @"a"),
                              genTestObject(@7, @"a"),
                              genTestObject(@4, @"a"), // key 4 but value "a", so this needs reloaded
                              genTestObject(@8, @"a"),
                              genTestObject(@4, @"b"), // key 4 but value didn't change
                              ];
  XCTestExpectation *expectation = genExpectation;

  [self.adapter performUpdatesAnimated:YES completion:^(BOOL finished) {
    [expectation fulfill];
  }];

  [self waitForExpectationsWithTimeout:15 handler:nil];
}

This throws within -[UICollectionView performBatchUpdates:completion:]:

*** Assertion failure in -[IGListCollectionView _endItemAnimationsWithInvalidationContext:tentativelyForReordering:animator:], /BuildRoot/Library/Caches/com.apple.xbs/Sources/UIKit_Sim/UIKit-3599.6/UICollectionView.m:5569
*** Terminating app due to uncaught exception 'NSInternalInconsistencyException', reason: 'Invalid update: invalid number of sections.  The number of sections contained in the collection view after the update (7) must be equal to the number of sections contained in the collection view before the update (4), plus or minus the number of sections inserted or deleted (5 inserted, 3 deleted).'
*** First throw call stack:
(
    0   CoreFoundation                      0x000000010228f34b __exceptionPreprocess + 171
    1   libobjc.A.dylib                     0x0000000101cf021e objc_exception_throw + 48
    2   CoreFoundation                      0x0000000102293442 +[NSException raise:format:arguments:] + 98
    3   Foundation                          0x0000000101886edd -[NSAssertionHandler handleFailureInMethod:object:file:lineNumber:description:] + 195
    4   UIKit                               0x00000001030e8115 -[UICollectionView _endItemAnimationsWithInvalidationContext:tentativelyForReordering:animator:] + 16065
    5   UIKit                               0x00000001030f120a -[UICollectionView _endUpdatesWithInvalidationContext:tentativelyForReordering:animator:] + 71
    6   UIKit                               0x00000001030f154c -[UICollectionView _performBatchUpdates:completion:invalidationContext:tentativelyForReordering:animator:] + 432
    7   UIKit                               0x00000001030f1379 -[UICollectionView _performBatchUpdates:completion:invalidationContext:tentativelyForReordering:] + 91
    8   UIKit                               0x00000001030f12fb -[UICollectionView _performBatchUpdates:completion:invalidationContext:] + 74
    9   UIKit                               0x00000001030f1250 -[UICollectionView performBatchUpdates:completion:] + 53
    10  IGListKit                           0x000000010e097eff -[IGListAdapterUpdater performBatchUpdatesWithCollectionView:] + 3375
    11  IGListKit                           0x000000010e09ad8d __54-[IGListAdapterUpdater queueUpdateWithCollectionView:]_block_invoke + 429

This makes sense because the update that is applied looks like:

• Delete sections 1, 2, 3
• Insert sections 1, 2, 3, 5, 6

Deleting sections 1 and 2 are correct. So are the inserts to 1, 2, 3, and 5. However a duplicate entry for object with key @4 is inserted. The infra has another insert at section 6, but skips section 4.

[rnystrom]

I think we need a system in place to pluck objects with duped diffIdentifiers. There should be asserting when this happens locally.

Recovering from this state is a little trickier because we want to dedupe our objects quickly before entering the diff (I think?). We only have to do this to the toObjects before diffing. Something like:

NSMutableSet *identifiers = [NSMutableSet new];
NSMutableArray *deduped = [NSMutableArray new];
for (id<IGListDiffable> obj in toObjects) {
  if (![identifiers containsObject:[obj diffIdentifier]]) {
    [deduped addObject: obj];
    [identifiers addObject:[obj diffIdentifier]];
  }
}
// then diff w/ array deduped

This adds another O(n) step before diffing, but should be pretty cheap.

[jessesquires]

But isn't diffIdentifier required to be unique across objects?

Seems like this scenario has invalid pre-conditions...

[rnystrom]

@jessesquires theoretically yes, but the implementation doesn't enforce it. I think it probably should.

Note though that I think the diffing algorithm should still support duped identifiers.