/
IGListDiff.mm
348 lines (306 loc) · 15.5 KB
/
IGListDiff.mm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
/**
* Copyright (c) Facebook, Inc. and its affiliates.
*
* This source code is licensed under the MIT license found in the
* LICENSE file in the root directory of this source tree.
*/
#import "IGListDiff.h"
#import <stack>
#import <unordered_map>
#import <vector>
#import <IGListDiffKit/IGListCompatibility.h>
#import <IGListDiffKit/IGListExperiments.h>
#import "IGListIndexPathResultInternal.h"
#import "IGListIndexSetResultInternal.h"
#import "IGListMoveIndexInternal.h"
#import "IGListMoveIndexPathInternal.h"
using namespace std;
/// Used to track data stats while diffing.
struct IGListEntry {
/// The number of times the data occurs in the old array
NSInteger oldCounter = 0;
/// The number of times the data occurs in the new array
NSInteger newCounter = 0;
/// The indexes of the data in the old array
stack<NSInteger> oldIndexes;
/// Flag marking if the data has been updated between arrays by checking the isEqual: method
BOOL updated = NO;
};
/// Track both the entry and algorithm index. Default the index to NSNotFound
struct IGListRecord {
IGListEntry *entry;
mutable NSInteger index;
IGListRecord() {
entry = NULL;
index = NSNotFound;
}
};
static id<NSObject> IGListTableKey(__unsafe_unretained id<IGListDiffable> object) {
id<NSObject> key = [object diffIdentifier];
NSCAssert(key != nil, @"Cannot use a nil key for the diffIdentifier of object %@", object);
return key;
}
struct IGListEqualID {
bool operator()(const id a, const id b) const {
return (a == b) || [a isEqual: b];
}
};
struct IGListHashID {
size_t operator()(const id o) const {
return (size_t)[o hash];
}
};
static void addIndexToMap(BOOL useIndexPaths, NSInteger section, NSInteger index, __unsafe_unretained id<IGListDiffable> object, __unsafe_unretained NSMapTable *map) {
id value;
if (useIndexPaths) {
value = [NSIndexPath indexPathForItem:index inSection:section];
} else {
value = @(index);
}
[map setObject:value forKey:[object diffIdentifier]];
}
static void addIndexToCollection(BOOL useIndexPaths, __unsafe_unretained id collection, NSInteger section, NSInteger index) {
if (useIndexPaths) {
NSIndexPath *path = [NSIndexPath indexPathForItem:index inSection:section];
[collection addObject:path];
} else {
[collection addIndex:index];
}
};
static NSArray<NSIndexPath *> *indexPathsAndPopulateMap(__unsafe_unretained NSArray<id<IGListDiffable>> *array, NSInteger section, __unsafe_unretained NSMapTable *map) {
NSMutableArray<NSIndexPath *> *paths = [NSMutableArray new];
[array enumerateObjectsUsingBlock:^(id<IGListDiffable> obj, NSUInteger idx, BOOL *stop) {
NSIndexPath *path = [NSIndexPath indexPathForItem:idx inSection:section];
[paths addObject:path];
[map setObject:path forKey:[obj diffIdentifier]];
}];
return paths;
}
static id IGListDiffing(BOOL returnIndexPaths,
NSInteger fromSection,
NSInteger toSection,
NSArray<id<IGListDiffable>> *oldArray,
NSArray<id<IGListDiffable>> *newArray,
IGListDiffOption option,
IGListExperiment experiments) {
const NSInteger newCount = newArray.count;
const NSInteger oldCount = oldArray.count;
NSMapTable *oldMap = [NSMapTable strongToStrongObjectsMapTable];
NSMapTable *newMap = [NSMapTable strongToStrongObjectsMapTable];
// if no new objects, everything from the oldArray is deleted
// take a shortcut and just build a delete-everything result
if (newCount == 0) {
if (returnIndexPaths) {
return [[IGListIndexPathResult alloc] initWithInserts:[NSArray new]
deletes:indexPathsAndPopulateMap(oldArray, fromSection, oldMap)
updates:[NSArray new]
moves:[NSArray new]
oldIndexPathMap:oldMap
newIndexPathMap:newMap];
} else {
[oldArray enumerateObjectsUsingBlock:^(id<IGListDiffable> obj, NSUInteger idx, BOOL *stop) {
addIndexToMap(returnIndexPaths, fromSection, idx, obj, oldMap);
}];
return [[IGListIndexSetResult alloc] initWithInserts:[NSIndexSet new]
deletes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(0, oldCount)]
updates:[NSIndexSet new]
moves:[NSArray new]
oldIndexMap:oldMap
newIndexMap:newMap];
}
}
// if no old objects, everything from the newArray is inserted
// take a shortcut and just build an insert-everything result
if (oldCount == 0) {
if (returnIndexPaths) {
return [[IGListIndexPathResult alloc] initWithInserts:indexPathsAndPopulateMap(newArray, toSection, newMap)
deletes:[NSArray new]
updates:[NSArray new]
moves:[NSArray new]
oldIndexPathMap:oldMap
newIndexPathMap:newMap];
} else {
[newArray enumerateObjectsUsingBlock:^(id<IGListDiffable> obj, NSUInteger idx, BOOL *stop) {
addIndexToMap(returnIndexPaths, toSection, idx, obj, newMap);
}];
return [[IGListIndexSetResult alloc] initWithInserts:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(0, newCount)]
deletes:[NSIndexSet new]
updates:[NSIndexSet new]
moves:[NSArray new]
oldIndexMap:oldMap
newIndexMap:newMap];
}
}
// symbol table uses the old/new array diffIdentifier as the key and IGListEntry as the value
// using id<NSObject> as the key provided by https://lists.gnu.org/archive/html/discuss-gnustep/2011-07/msg00019.html
unordered_map<id<NSObject>, IGListEntry, IGListHashID, IGListEqualID> table;
// pass 1
// create an entry for every item in the new array
// increment its new count for each occurence
vector<IGListRecord> newResultsArray(newCount);
for (NSInteger i = 0; i < newCount; i++) {
id<NSObject> key = IGListTableKey(newArray[i]);
IGListEntry &entry = table[key];
entry.newCounter++;
// add NSNotFound for each occurence of the item in the new array
entry.oldIndexes.push(NSNotFound);
// note: the entry is just a pointer to the entry which is stack-allocated in the table
newResultsArray[i].entry = &entry;
}
// pass 2
// update or create an entry for every item in the old array
// increment its old count for each occurence
// record the original index of the item in the old array
// MUST be done in descending order to respect the oldIndexes stack construction
vector<IGListRecord> oldResultsArray(oldCount);
for (NSInteger i = oldCount - 1; i >= 0; i--) {
id<NSObject> key = IGListTableKey(oldArray[i]);
IGListEntry &entry = table[key];
entry.oldCounter++;
// push the original indices where the item occurred onto the index stack
entry.oldIndexes.push(i);
// note: the entry is just a pointer to the entry which is stack-allocated in the table
oldResultsArray[i].entry = &entry;
}
// pass 3
// handle data that occurs in both arrays
for (NSInteger i = 0; i < newCount; i++) {
IGListEntry *entry = newResultsArray[i].entry;
// grab and pop the top original index. if the item was inserted this will be NSNotFound
NSCAssert(!entry->oldIndexes.empty(), @"Old indexes is empty while iterating new item %li. Should have NSNotFound", (long)i);
const NSInteger originalIndex = entry->oldIndexes.top();
entry->oldIndexes.pop();
if (originalIndex < oldCount) {
const id<IGListDiffable> n = newArray[i];
const id<IGListDiffable> o = oldArray[originalIndex];
switch (option) {
case IGListDiffPointerPersonality:
// flag the entry as updated if the pointers are not the same
if (n != o) {
entry->updated = YES;
}
break;
case IGListDiffEquality:
// use -[IGListDiffable isEqualToDiffableObject:] between both version of data to see if anything has changed
// skip the equality check if both indexes point to the same object
if (n != o && ![n isEqualToDiffableObject:o]) {
entry->updated = YES;
}
break;
}
}
if (originalIndex != NSNotFound
&& entry->newCounter > 0
&& entry->oldCounter > 0) {
// if an item occurs in the new and old array, it is unique
// assign the index of new and old records to the opposite index (reverse lookup)
newResultsArray[i].index = originalIndex;
oldResultsArray[originalIndex].index = i;
}
}
// storage for final NSIndexPaths or indexes
id mInserts, mMoves, mUpdates, mDeletes;
if (returnIndexPaths) {
mInserts = [NSMutableArray<NSIndexPath *> new];
mMoves = [NSMutableArray<IGListMoveIndexPath *> new];
mUpdates = [NSMutableArray<NSIndexPath *> new];
mDeletes = [NSMutableArray<NSIndexPath *> new];
} else {
mInserts = [NSMutableIndexSet new];
mMoves = [NSMutableArray<IGListMoveIndex *> new];
mUpdates = [NSMutableIndexSet new];
mDeletes = [NSMutableIndexSet new];
}
// track offsets from deleted items to calculate where items have moved
vector<NSInteger> deleteOffsets(oldCount), insertOffsets(newCount);
NSInteger runningOffset = 0;
// iterate old array records checking for deletes
// incremement offset for each delete
for (NSInteger i = 0; i < oldCount; i++) {
deleteOffsets[i] = runningOffset;
const IGListRecord record = oldResultsArray[i];
// if the record index in the new array doesn't exist, its a delete
if (record.index == NSNotFound) {
addIndexToCollection(returnIndexPaths, mDeletes, fromSection, i);
runningOffset++;
}
addIndexToMap(returnIndexPaths, fromSection, i, oldArray[i], oldMap);
}
// reset and track offsets from inserted items to calculate where items have moved
runningOffset = 0;
for (NSInteger i = 0; i < newCount; i++) {
insertOffsets[i] = runningOffset;
const IGListRecord record = newResultsArray[i];
const NSInteger oldIndex = record.index;
// add to inserts if the opposing index is NSNotFound
if (record.index == NSNotFound) {
addIndexToCollection(returnIndexPaths, mInserts, toSection, i);
runningOffset++;
} else {
// note that an entry can be updated /and/ moved
if (record.entry->updated) {
addIndexToCollection(returnIndexPaths, mUpdates, fromSection, oldIndex);
}
// calculate the offset and determine if there was a move
// if the indexes match, ignore the index
const NSInteger insertOffset = insertOffsets[i];
const NSInteger deleteOffset = deleteOffsets[oldIndex];
if ((oldIndex - deleteOffset + insertOffset) != i) {
id move;
if (returnIndexPaths) {
NSIndexPath *from = [NSIndexPath indexPathForItem:oldIndex inSection:fromSection];
NSIndexPath *to = [NSIndexPath indexPathForItem:i inSection:toSection];
move = [[IGListMoveIndexPath alloc] initWithFrom:from to:to];
} else {
move = [[IGListMoveIndex alloc] initWithFrom:oldIndex to:i];
}
[mMoves addObject:move];
}
}
addIndexToMap(returnIndexPaths, toSection, i, newArray[i], newMap);
}
NSCAssert((oldCount + [mInserts count] - [mDeletes count]) == newCount,
@"Sanity check failed applying %lu inserts and %lu deletes to old count %li equaling new count %li",
(unsigned long)[mInserts count], (unsigned long)[mDeletes count], (long)oldCount, (long)newCount);
if (returnIndexPaths) {
return [[IGListIndexPathResult alloc] initWithInserts:mInserts
deletes:mDeletes
updates:mUpdates
moves:mMoves
oldIndexPathMap:oldMap
newIndexPathMap:newMap];
} else {
return [[IGListIndexSetResult alloc] initWithInserts:mInserts
deletes:mDeletes
updates:mUpdates
moves:mMoves
oldIndexMap:oldMap
newIndexMap:newMap];
}
}
IGListIndexSetResult *IGListDiff(NSArray<id<IGListDiffable> > *oldArray,
NSArray<id<IGListDiffable>> *newArray,
IGListDiffOption option) {
return IGListDiffing(NO, 0, 0, oldArray, newArray, option, 0);
}
IGListIndexPathResult *IGListDiffPaths(NSInteger fromSection,
NSInteger toSection,
NSArray<id<IGListDiffable>> *oldArray,
NSArray<id<IGListDiffable>> *newArray,
IGListDiffOption option) {
return IGListDiffing(YES, fromSection, toSection, oldArray, newArray, option, 0);
}
IGListIndexSetResult *IGListDiffExperiment(NSArray<id<IGListDiffable>> *_Nullable oldArray,
NSArray<id<IGListDiffable>> *_Nullable newArray,
IGListDiffOption option,
IGListExperiment experiments) {
return IGListDiffing(NO, 0, 0, oldArray, newArray, option, experiments);
}
IGListIndexPathResult *IGListDiffPathsExperiment(NSInteger fromSection,
NSInteger toSection,
NSArray<id<IGListDiffable>> *_Nullable oldArray,
NSArray<id<IGListDiffable>> *_Nullable newArray,
IGListDiffOption option,
IGListExperiment experiments) {
return IGListDiffing(YES, fromSection, toSection, oldArray, newArray, option, experiments);
}