1 /*
<lambda>null2  * Copyright 2018 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package androidx.recyclerview.widget
17 
18 import java.util.Random
19 import java.util.UUID
20 import org.hamcrest.CoreMatchers.equalTo
21 import org.hamcrest.CoreMatchers.`is`
22 import org.hamcrest.CoreMatchers.not
23 import org.hamcrest.CoreMatchers.nullValue
24 import org.hamcrest.MatcherAssert.assertThat
25 import org.junit.Assert
26 import org.junit.Assert.assertEquals
27 import org.junit.Assert.assertFalse
28 import org.junit.Rule
29 import org.junit.Test
30 import org.junit.rules.TestWatcher
31 import org.junit.runner.Description
32 import org.junit.runner.RunWith
33 import org.junit.runners.JUnit4
34 
35 @RunWith(JUnit4::class)
36 class DiffUtilTest {
37     private val before = mutableListOf<Item>()
38     private val after = mutableListOf<Item>()
39     private val log = StringBuilder()
40     private val callback = ItemListCallback(oldList = before, newList = after, assertCalls = true)
41 
42     init {
43         Item.idCounter = 0
44     }
45 
46     @Rule
47     @JvmField
48     val logOnExceptionWatcher: TestWatcher =
49         object : TestWatcher() {
50             override fun failed(e: Throwable, description: Description) {
51                 System.err.println(
52                     """
53                     LOG:
54                     $log
55                     END_LOG
56                     """
57                         .trimIndent()
58                 )
59             }
60         }
61 
62     @Test
63     fun testNoChange() {
64         initWithSize(5)
65         check()
66     }
67 
68     @Test
69     fun testAddItems() {
70         initWithSize(2)
71         add(1)
72         check()
73     }
74 
75     // @Test
76     // Used for development
77     // @Suppress("unused")
78     fun testRandom() {
79         for (x in 0..99) {
80             for (i in 0..99) {
81                 for (j in 2..39) {
82                     testRandom(i, j)
83                 }
84             }
85         }
86     }
87 
88     @Test
89     fun testGen2() {
90         initWithSize(5)
91         add(5)
92         delete(3)
93         delete(1)
94         check()
95     }
96 
97     @Test
98     fun testGen3() {
99         initWithSize(5)
100         add(0)
101         delete(1)
102         delete(3)
103         check()
104     }
105 
106     @Test
107     fun testGen4() {
108         initWithSize(5)
109         add(5)
110         add(1)
111         add(4)
112         add(4)
113         check()
114     }
115 
116     @Test
117     fun testGen5() {
118         initWithSize(5)
119         delete(0)
120         delete(2)
121         add(0)
122         add(2)
123         check()
124     }
125 
126     @Test
127     fun testGen6() {
128         initWithSize(2)
129         delete(0)
130         delete(0)
131         check()
132     }
133 
134     @Test
135     fun testGen7() {
136         initWithSize(3)
137         move(2, 0)
138         delete(2)
139         add(2)
140         check()
141     }
142 
143     @Test
144     fun testGen8() {
145         initWithSize(3)
146         delete(1)
147         add(0)
148         move(2, 0)
149         check()
150     }
151 
152     @Test
153     fun testGen9() {
154         initWithSize(2)
155         add(2)
156         move(0, 2)
157         check()
158     }
159 
160     @Test
161     fun testGen10() {
162         initWithSize(3)
163         move(0, 1)
164         move(1, 2)
165         add(0)
166         check()
167     }
168 
169     @Test
170     fun testGen11() {
171         initWithSize(4)
172         move(2, 0)
173         move(2, 3)
174         check()
175     }
176 
177     @Test
178     fun testGen12() {
179         initWithSize(4)
180         move(3, 0)
181         move(2, 1)
182         check()
183     }
184 
185     @Test
186     fun testGen13() {
187         initWithSize(4)
188         move(3, 2)
189         move(0, 3)
190         check()
191     }
192 
193     @Test
194     fun testGen14() {
195         initWithSize(4)
196         move(3, 2)
197         add(4)
198         move(0, 4)
199         check()
200     }
201 
202     @Test
203     fun testGen15() {
204         initWithSize(1)
205         update(0)
206         update(0)
207         update(0)
208         check()
209     }
210 
211     @Test
212     fun testGen16() {
213         initWithSize(1)
214         update(0)
215         move(0, 0)
216         move(0, 0)
217         add(0)
218         check()
219     }
220 
221     @Test
222     fun testGen17() {
223         initWithSize(2)
224         move(1, 0)
225         add(2)
226         update(1)
227         add(0)
228         check()
229     }
230 
231     @Test
232     fun testGen18() {
233         initWithSize(2)
234         updateWithPayload(0)
235         check()
236     }
237 
238     @Test
239     fun testGen19() {
240         initWithSize(3)
241         move(1, 1)
242         delete(2)
243         move(0, 1)
244         add(0)
245         update(1)
246         add(1)
247         updateWithPayload(2)
248         add(1)
249         delete(1)
250         updateWithPayload(3)
251         add(2)
252         move(2, 1)
253         add(2)
254         delete(2)
255         delete(1)
256         check()
257     }
258 
259     @Test
260     fun testOneItem() {
261         initWithSize(1)
262         check()
263     }
264 
265     @Test
266     fun testEmpty() {
267         initWithSize(0)
268         check()
269     }
270 
271     @Test
272     fun testAdd1() {
273         initWithSize(1)
274         add(1)
275         check()
276     }
277 
278     @Test
279     fun testMove1() {
280         initWithSize(3)
281         move(0, 2)
282         check()
283     }
284 
285     @Test
286     fun tmp() {
287         initWithSize(4)
288         move(0, 2)
289         check()
290     }
291 
292     @Test
293     fun testUpdate1() {
294         initWithSize(3)
295         update(2)
296         check()
297     }
298 
299     @Test
300     fun testUpdate2() {
301         initWithSize(2)
302         add(1)
303         update(1)
304         update(2)
305         check()
306     }
307 
308     @Test
309     fun testDisableMoveDetection() {
310         initWithSize(5)
311         move(0, 4)
312         val applied = applyUpdates(before, DiffUtil.calculateDiff(callback, false))
313         assertThat(applied.size, `is`(5))
314         assertThat(applied[4].newItem, `is`(true))
315         assertThat(applied.contains(before[0]), `is`(false))
316     }
317 
318     @Test(expected = IndexOutOfBoundsException::class)
319     fun convertOldPositionToNew_tooSmall() {
320         initWithSize(2)
321         update(2)
322         calculate().convertOldPositionToNew(-1)
323     }
324 
325     @Test(expected = IndexOutOfBoundsException::class)
326     fun convertOldPositionToNew_tooLarge() {
327         initWithSize(2)
328         update(2)
329         calculate().convertOldPositionToNew(2)
330     }
331 
332     @Test(expected = IndexOutOfBoundsException::class)
333     fun convertNewPositionToOld_tooSmall() {
334         initWithSize(2)
335         update(2)
336         calculate().convertNewPositionToOld(-1)
337     }
338 
339     @Test(expected = IndexOutOfBoundsException::class)
340     fun convertNewPositionToOld_tooLarge() {
341         initWithSize(2)
342         update(2)
343         calculate().convertNewPositionToOld(2)
344     }
345 
346     private fun calculate() = DiffUtil.calculateDiff(callback, true)
347 
348     @Test
349     fun duplicate() {
350         before.addAll(listOf(Item(false), Item(false)))
351         after.addAll(listOf(before[0], before[1], Item(true), before[1]))
352         check()
353     }
354 
355     private fun testRandom(initialSize: Int, operationCount: Int) {
356         log.setLength(0)
357         Item.idCounter = 0
358         initWithSize(initialSize)
359         for (i in 0 until operationCount) {
360             val op = sRand.nextInt(6)
361             when (op) {
362                 0 -> add(sRand.nextInt(after.size + 1))
363                 1 ->
364                     if (after.isNotEmpty()) {
365                         delete(sRand.nextInt(after.size))
366                     }
367                 2 -> // move
368                 if (after.size > 0) {
369                         move(sRand.nextInt(after.size), sRand.nextInt(after.size))
370                     }
371                 3 -> // update
372                 if (after.size > 0) {
373                         update(sRand.nextInt(after.size))
374                     }
375                 4 -> // update with payload
376                 if (after.size > 0) {
377                         updateWithPayload(sRand.nextInt(after.size))
378                     }
379                 5 -> // duplicate
380                 if (after.size > 0) {
381                         duplicate(sRand.nextInt(after.size), sRand.nextInt(after.size))
382                     }
383             }
384         }
385         check()
386     }
387 
388     private fun check() {
389         val result = calculate()
390         log("before", before)
391         log("after", after)
392         // test diff dispatch
393         val applied = applyUpdates(before, result)
394 
395         assertEquals(applied, after)
396         // test position conversion
397         val missingBeforePosition = mutableSetOf<Int>()
398         val afterCopy = after.toMutableList()
399         before.indices.forEach { oldPos ->
400             val newPos = result.convertOldPositionToNew(oldPos)
401             if (newPos != DiffUtil.DiffResult.NO_POSITION) {
402                 assertEquals(before[oldPos].id, after[newPos].id)
403                 // remove from the copy so that we can do not exists checks for unfound elements
404                 afterCopy.remove(after[newPos])
405             } else {
406                 missingBeforePosition.add(oldPos)
407             }
408         }
409         missingBeforePosition.forEach { assertFalse(afterCopy.contains(before[it])) }
410 
411         try {
412             result.convertOldPositionToNew(before.size)
413             Assert.fail("out of bounds should occur")
414         } catch (e: IndexOutOfBoundsException) { // expected
415         }
416 
417         val missingAfterPositions = mutableSetOf<Int>()
418         val beforeCopy = before.toMutableList()
419         after.indices.forEach { newPos ->
420             val oldPos = result.convertNewPositionToOld(newPos)
421             if (oldPos != DiffUtil.DiffResult.NO_POSITION) {
422                 assertEquals(after[newPos].id, before[oldPos].id)
423                 beforeCopy.remove(before[oldPos])
424             } else {
425                 missingAfterPositions.add(newPos)
426             }
427         }
428         missingAfterPositions.forEach { assertFalse(beforeCopy.contains(after[it])) }
429 
430         try {
431             result.convertNewPositionToOld(after.size)
432             Assert.fail("out of bounds should occur")
433         } catch (e: IndexOutOfBoundsException) { // expected
434         }
435     }
436 
437     private fun initWithSize(size: Int) {
438         before.clear()
439         after.clear()
440         repeat(size) { before.add(Item(false)) }
441         after.addAll(before)
442         log.append("initWithSize($size);\n")
443     }
444 
445     private fun log(title: String, items: List<*>) {
446         log.append(title).append(":").append(items.size).append("\n")
447         items.forEach { item -> log.append("  ").append(item).append("\n") }
448     }
449 
450     private fun assertEquals(applied: List<Item>, after: List<Item>) {
451         log("applied", applied)
452         val report = log.toString()
453         val duplicateDiffs = computeExpectedNewItemsForExisting(after)
454 
455         // in theory we can get duplicateDiff[it.id] time "Add" event for existing items
456         assertThat(report, applied.size, `is`(after.size))
457         after.indices.forEach { index ->
458             val item = applied[index]
459             if (after[index].newItem) {
460                 assertThat(report, item.newItem, `is`(true))
461             } else if (duplicateDiffs.getOrElse(after[index].id) { 0 } > 0 && item.newItem) {
462                 // a duplicated item might come as a new item, be OK with it
463                 duplicateDiffs[after[index].id] = duplicateDiffs[after[index].id]!! - 1
464             } else if (after[index].changed) {
465                 assertThat(report, item.newItem, `is`(false))
466                 assertThat(report, item.changed, `is`(true))
467                 assertThat(report, item.id, `is`(after[index].id))
468                 assertThat(report, item.payload, `is`(after[index].payload))
469             } else {
470                 assertThat(report, item, equalTo(after[index]))
471             }
472         }
473     }
474 
475     /**
476      * When an item is duplicated more than once in the new list, some of those will show up as new
477      * items, we should be OK with that but still verify
478      *
479      * @return mapping for <itemId -> max # of duplicates show up as new in the new list>
480      */
481     private fun computeExpectedNewItemsForExisting(after: List<Item>): MutableMap<Long, Int> {
482         // we might create list w/ duplicates.
483         val duplicateDiffs = mutableMapOf<Long, Int>() // id to count
484         after
485             .filterNot { it.newItem }
486             .forEach { duplicateDiffs[it.id] = 1 + duplicateDiffs.getOrElse(it.id) { 1 } }
487         before.forEach { duplicateDiffs[it.id] = -1 + duplicateDiffs.getOrElse(it.id) { 0 } }
488         return duplicateDiffs
489     }
490 
491     private fun applyUpdates(before: List<Item>, result: DiffUtil.DiffResult): List<Item> {
492         val target = mutableListOf<Item>()
493         target.addAll(before)
494         result.dispatchUpdatesTo(
495             object : ListUpdateCallback {
496                 override fun onInserted(position: Int, count: Int) {
497                     repeat(count) { target.add(it + position, Item(true)) }
498                 }
499 
500                 override fun onRemoved(position: Int, count: Int) {
501                     repeat(count) { target.removeAt(position) }
502                 }
503 
504                 override fun onMoved(fromPosition: Int, toPosition: Int) {
505                     val item = target.removeAt(fromPosition)
506                     target.add(toPosition, item)
507                 }
508 
509                 override fun onChanged(position: Int, count: Int, payload: Any?) {
510                     repeat(count) { offset ->
511                         val positionInList = position + offset
512                         val existing = target[positionInList]
513                         // make sure we don't update same item twice in callbacks
514                         assertThat(existing.changed, `is`(false))
515                         assertThat(existing.newItem, `is`(false))
516                         assertThat(existing.payload, `is`(nullValue()))
517                         val replica = existing.copy(changed = true, payload = payload as? String)
518                         target.removeAt(positionInList)
519                         target.add(positionInList, replica)
520                     }
521                 }
522             }
523         )
524         return target
525     }
526 
527     private fun add(index: Int) {
528         after.add(index, Item(true))
529         log.append("add(").append(index).append(");\n")
530     }
531 
532     private fun delete(index: Int) {
533         after.removeAt(index)
534         log.append("delete(").append(index).append(");\n")
535     }
536 
537     private fun update(index: Int) {
538         val existing = after[index]
539         if (existing.newItem) {
540             return // new item cannot be changed
541         }
542         // clean the payload since this might be after an updateWithPayload call
543         val replica =
544             existing.copy(changed = true, payload = null, data = UUID.randomUUID().toString())
545         after[index] = replica
546         log.append("update(").append(index).append(");\n")
547     }
548 
549     private fun updateWithPayload(index: Int) {
550         val existing = after[index]
551         if (existing.newItem) {
552             return // new item cannot be changed
553         }
554         val replica =
555             existing.copy(
556                 changed = true,
557                 data = UUID.randomUUID().toString(),
558                 payload = UUID.randomUUID().toString()
559             )
560         after[index] = replica
561         log.append("updateWithPayload(").append(index).append(");\n")
562     }
563 
564     private fun move(from: Int, to: Int) {
565         val removed = after.removeAt(from)
566         after.add(to, removed)
567         log.append("move(").append(from).append(",").append(to).append(");\n")
568     }
569 
570     private fun duplicate(pos: Int, to: Int) {
571         val item = after[pos]
572         after.add(pos, item) // re-use the item so that changes happen on it
573         log.append("duplicate(").append(pos).append(",").append(to).append(");\n")
574     }
575 
576     internal data class Item(
577         val id: Long,
578         val newItem: Boolean,
579         var changed: Boolean = false,
580         var payload: String? = null,
581         var data: String = UUID.randomUUID().toString()
582     ) {
583         constructor(newItem: Boolean) : this(id = idCounter++, newItem = newItem)
584 
585         companion object {
586             var idCounter: Long = 0
587         }
588     }
589 
590     private class ItemListCallback(
591         private val oldList: List<Item>,
592         private val newList: List<Item>,
593         private val assertCalls: Boolean = true
594     ) : DiffUtil.Callback() {
595         override fun getOldListSize() = oldList.size
596 
597         override fun getNewListSize() = newList.size
598 
599         override fun areItemsTheSame(oldItemIndex: Int, newItemIndex: Int): Boolean {
600             return oldList[oldItemIndex].id == newList[newItemIndex].id
601         }
602 
603         override fun areContentsTheSame(oldItemIndex: Int, newItemIndex: Int): Boolean {
604             if (assertCalls) {
605                 assertThat(oldList[oldItemIndex].id, equalTo(newList[newItemIndex].id))
606             }
607             return oldList[oldItemIndex].data == newList[newItemIndex].data
608         }
609 
610         override fun getChangePayload(oldItemIndex: Int, newItemIndex: Int): Any? {
611             if (assertCalls) {
612                 assertThat(oldList[oldItemIndex].id, equalTo(newList[newItemIndex].id))
613                 assertThat(oldList[oldItemIndex].data, not(equalTo(newList[newItemIndex].data)))
614             }
615 
616             return newList[newItemIndex].payload
617         }
618     }
619 
620     companion object {
621         private val sRand = Random(System.nanoTime())
622     }
623 }
624