1 /**
2  * Copyright (c) 2020, 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 
17 package com.android.server.utils;
18 
19 import static org.junit.Assert.assertEquals;
20 import static org.junit.Assert.assertNotNull;
21 import static org.junit.Assert.assertTrue;
22 import static org.junit.Assert.fail;
23 
24 import android.util.ArrayMap;
25 import android.util.ArraySet;
26 import android.util.LongSparseArray;
27 import android.util.SparseArray;
28 import android.util.SparseBooleanArray;
29 import android.util.SparseIntArray;
30 
31 import androidx.test.filters.SmallTest;
32 
33 import org.junit.After;
34 import org.junit.Before;
35 import org.junit.Test;
36 
37 import java.util.ArrayList;
38 import java.util.Random;
39 
40 /**
41  * Test class for various utility classes that support the Watchable or Snappable
42  * features.  This covers {@link Watcher}, {@link Watchable}, {@link WatchableImpl},
43  * {@link WatchedArrayMap}, {@link WatchedSparseArray}, and
44  * {@link WatchedSparseBooleanArray}.
45  *
46  * Build/Install/Run:
47  *  atest PackageManagerServiceTest:WatcherTest
48  */
49 @SmallTest
50 public class WatcherTest {
51 
52     // A counter to generate unique IDs for Leaf elements.
53     private int mLeafId = 0;
54 
55     // Useful indices used in the tests.
56     private static final int INDEX_A = 1;
57     private static final int INDEX_B = 2;
58     private static final int INDEX_C = 3;
59     private static final int INDEX_D = 4;
60 
61     // A small Watchable leaf node
62     private class Leaf extends WatchableImpl implements Snappable {
63         private int mId;
64         private int mDatum;
65 
Leaf()66         Leaf() {
67             mDatum = 0;
68             mId = mLeafId++;
69         }
70 
set(int i)71         void set(int i) {
72             if (mDatum != i) {
73                 mDatum = i;
74                 dispatchChange(this);
75             }
76         }
get()77         int get() {
78             return mDatum;
79         }
tick()80         void tick() {
81             set(mDatum + 1);
82         }
snapshot()83         public Leaf snapshot() {
84             Leaf result = new Leaf();
85             result.mDatum = mDatum;
86             result.mId = mId;
87             result.seal();
88             return result;
89         }
90         @Override
equals(Object o)91         public boolean equals(Object o) {
92             if (o instanceof Leaf) {
93                 return mDatum == ((Leaf) o).mDatum && mId == ((Leaf) o).mId;
94             } else {
95                 return false;
96             }
97         }
98         @Override
toString()99         public String toString() {
100             return "Leaf(" + mDatum + "," + mId + ")";
101         }
102     }
103 
104     // Execute the {@link Runnable} and if {@link UnsupportedOperationException} is
105     // thrown, do nothing.  If no exception is thrown, fail the test.
verifySealed(String msg, Runnable test)106     private void verifySealed(String msg, Runnable test) {
107         try {
108             test.run();
109             fail(msg + " should be sealed");
110         } catch (IllegalStateException e) {
111             // The exception was expected.
112         }
113     }
114 
115     // Execute the {@link Runnable} and if {@link UnsupportedOperationException} is
116     // thrown, fail the test.  If no exception is thrown, do nothing.
verifyNotSealed(String msg, Runnable test)117     private void verifyNotSealed(String msg, Runnable test) {
118         try {
119             test.run();
120         } catch (IllegalStateException e) {
121             fail(msg + " should be not sealed");
122         }
123     }
124 
125     @Before
setUp()126     public void setUp() throws Exception {
127     }
128 
129     @After
tearDown()130     public void tearDown() throws Exception {
131     }
132 
133     @Test
testBasicBehavior()134     public void testBasicBehavior() {
135         WatchableTester tester;
136 
137         // Create a few leaves
138         Leaf leafA = new Leaf();
139 
140         // Basic test.  Create a leaf and verify that changes to the leaf get notified to
141         // the tester.
142         tester = new WatchableTester(leafA, "Leaf");
143         tester.verify(0, "Initial leaf - no registration");
144         leafA.tick();
145         tester.verify(0, "Updates with no registration");
146         tester.register();
147         leafA.tick();
148         tester.verify(1, "Updates with registration");
149         leafA.tick();
150         leafA.tick();
151         tester.verify(3, "Updates with registration");
152         // Create a snapshot.  Verify that the snapshot matches the
153         Leaf leafASnapshot = leafA.snapshot();
154         assertEquals("Leaf snapshot", leafA.get(), leafASnapshot.get());
155         leafA.tick();
156         assertTrue(leafA.get() != leafASnapshot.get());
157         tester.verify(4, "Tick after snapshot");
158         verifySealed("Leaf", ()->leafASnapshot.tick());
159 
160         // Add the same leaf to more than one tester.  Verify that a change to the leaf is seen by
161         // all registered listeners.
162         tester.clear();
163         WatchableTester buddy1 = new WatchableTester(leafA, "Leaf2");
164         WatchableTester buddy2 = new WatchableTester(leafA, "Leaf3");
165         buddy1.verify(0, "Initial leaf - no registration");
166         buddy2.verify(0, "Initial leaf - no registration");
167         leafA.tick();
168         tester.verify(1, "Updates with buddies");
169         buddy1.verify(0, "Updates - no registration");
170         buddy2.verify(0, "Updates - no registration");
171         buddy1.register();
172         buddy2.register();
173         buddy1.verify(0, "No updates - registered");
174         buddy2.verify(0, "No updates - registered");
175         leafA.tick();
176         buddy1.verify(1, "First update");
177         buddy2.verify(1, "First update");
178         buddy1.unregister();
179         leafA.tick();
180         buddy1.verify(1, "Second update - unregistered");
181         buddy2.verify(2, "Second update");
182     }
183 
184     @Test
testWatchedArrayMap()185     public void testWatchedArrayMap() {
186         final String name = "WatchedArrayMap";
187         WatchableTester tester;
188 
189         // Create a few leaves
190         Leaf leafA = new Leaf();
191         Leaf leafB = new Leaf();
192         Leaf leafC = new Leaf();
193         Leaf leafD = new Leaf();
194 
195         // Test WatchedArrayMap
196         WatchedArrayMap<Integer, Leaf> array = new WatchedArrayMap<>();
197         array.put(INDEX_A, leafA);
198         array.put(INDEX_B, leafB);
199         tester = new WatchableTester(array, name);
200         tester.verify(0, "Initial array - no registration");
201         leafA.tick();
202         tester.verify(0, "Updates with no registration");
203         tester.register();
204         tester.verify(0, "Updates with no registration");
205         leafA.tick();
206         tester.verify(1, "Updates with registration");
207         leafB.tick();
208         tester.verify(2, "Updates with registration");
209         array.remove(INDEX_B);
210         tester.verify(3, "Removed b");
211         leafB.tick();
212         tester.verify(3, "Updates with b not watched");
213         array.put(INDEX_B, leafB);
214         array.put(INDEX_C, leafB);
215         tester.verify(5, "Added b twice");
216         leafB.tick();
217         tester.verify(6, "Changed b - single notification");
218         array.remove(INDEX_C);
219         tester.verify(7, "Removed first b");
220         leafB.tick();
221         tester.verify(8, "Changed b - single notification");
222         array.remove(INDEX_B);
223         tester.verify(9, "Removed second b");
224         leafB.tick();
225         tester.verify(9, "Updated b - no change");
226         array.clear();
227         tester.verify(10, "Cleared array");
228         leafB.tick();
229         tester.verify(10, "Change to b not in array");
230 
231         // Special methods
232         array.put(INDEX_C, leafC);
233         tester.verify(11, "Added c");
234         leafC.tick();
235         tester.verify(12, "Ticked c");
236         array.setValueAt(array.indexOfKey(INDEX_C), leafD);
237         tester.verify(13, "Replaced c with d");
238         leafC.tick();
239         leafD.tick();
240         tester.verify(14, "Ticked d and c (c not registered)");
241 
242         // Snapshot
243         {
244             final WatchedArrayMap<Integer, Leaf> arraySnap = array.snapshot();
245             tester.verify(14, "Generate snapshot (no changes)");
246             // Verify that the snapshot is a proper copy of the source.
247             assertEquals(name + " snap same size",
248                          array.size(), arraySnap.size());
249             for (int i = 0; i < array.size(); i++) {
250                 for (int j = 0; j < arraySnap.size(); j++) {
251                     assertTrue(name + " elements differ",
252                                array.valueAt(i) != arraySnap.valueAt(j));
253                 }
254                 assertTrue(name + " element copy",
255                            array.valueAt(i).equals(arraySnap.valueAt(i)));
256             }
257             leafD.tick();
258             tester.verify(15, "Tick after snapshot");
259             // Verify that the snapshot is sealed
260             verifySealed(name, ()->arraySnap.put(INDEX_A, leafA));
261             assertTrue(!array.isSealed());
262             assertTrue(arraySnap.isSealed());
263         }
264         // Recreate the snapshot since the test corrupted it.
265         {
266             final WatchedArrayMap<Integer, Leaf> arraySnap = array.snapshot();
267             // Verify that elements are also snapshots
268             final Leaf arraySnapElement = arraySnap.valueAt(0);
269             verifySealed("ArraySnapshotElement", ()->arraySnapElement.tick());
270         }
271         // Verify copy-in/out
272         {
273             final String msg = name + " copy-in/out failed";
274             ArrayMap<Integer, Leaf> base = new ArrayMap<>();
275             array.copyTo(base);
276             WatchedArrayMap<Integer, Leaf> copy = new WatchedArrayMap<>();
277             copy.copyFrom(base);
278             if (!array.equals(copy)) {
279                 fail(msg);
280             }
281         }
282     }
283 
284     @Test
testWatchedArraySet()285     public void testWatchedArraySet() {
286         final String name = "WatchedArraySet";
287         WatchableTester tester;
288 
289         // Create a few leaves
290         Leaf leafA = new Leaf();
291         Leaf leafB = new Leaf();
292         Leaf leafC = new Leaf();
293         Leaf leafD = new Leaf();
294 
295         // Test WatchedArraySet
296         WatchedArraySet<Leaf> array = new WatchedArraySet<>();
297         array.add(leafA);
298         array.add(leafB);
299         tester = new WatchableTester(array, name);
300         tester.verify(0, "Initial array - no registration");
301         leafA.tick();
302         tester.verify(0, "Updates with no registration");
303         tester.register();
304         tester.verify(0, "Updates with no registration");
305         leafA.tick();
306         tester.verify(1, "Updates with registration");
307         leafB.tick();
308         tester.verify(2, "Updates with registration");
309         array.remove(leafB);
310         tester.verify(3, "Removed b");
311         leafB.tick();
312         tester.verify(3, "Updates with b not watched");
313         array.add(leafB);
314         array.add(leafB);
315         tester.verify(5, "Added b once");
316         leafB.tick();
317         tester.verify(6, "Changed b - single notification");
318         array.remove(leafB);
319         tester.verify(7, "Removed b");
320         leafB.tick();
321         tester.verify(7, "Changed b - not watched");
322         array.remove(leafB);
323         tester.verify(7, "Removed non-existent b");
324         array.clear();
325         tester.verify(8, "Cleared array");
326         leafA.tick();
327         tester.verify(8, "Change to a not in array");
328 
329         // Special methods
330         array.add(leafA);
331         array.add(leafB);
332         array.add(leafC);
333         tester.verify(11, "Added a, b, c");
334         leafC.tick();
335         tester.verify(12, "Ticked c");
336         array.removeAt(array.indexOf(leafC));
337         tester.verify(13, "Removed c");
338         leafC.tick();
339         tester.verify(13, "Ticked c, not registered");
340         array.append(leafC);
341         tester.verify(14, "Append c");
342         leafC.tick();
343         leafD.tick();
344         tester.verify(15, "Ticked d and c");
345         assertEquals("Verify three elements", 3, array.size());
346 
347         // Snapshot
348         {
349             final WatchedArraySet<Leaf> arraySnap = array.snapshot();
350             tester.verify(15, "Generate snapshot (no changes)");
351             // Verify that the snapshot is a proper copy of the source.
352             assertEquals(name + " snap same size",
353                          array.size(), arraySnap.size());
354             for (int i = 0; i < array.size(); i++) {
355                 for (int j = 0; j < arraySnap.size(); j++) {
356                     assertTrue(name + " elements differ",
357                                array.valueAt(i) != arraySnap.valueAt(j));
358                 }
359             }
360             leafC.tick();
361             tester.verify(16, "Tick after snapshot");
362             // Verify that the array snapshot is sealed
363             verifySealed(name, ()->arraySnap.add(leafB));
364             assertTrue(!array.isSealed());
365             assertTrue(arraySnap.isSealed());
366         }
367         // Recreate the snapshot since the test corrupted it.
368         {
369             final WatchedArraySet<Leaf> arraySnap = array.snapshot();
370             // Verify that elements are also snapshots
371             final Leaf arraySnapElement = arraySnap.valueAt(0);
372             verifySealed(name + " snap element", ()->arraySnapElement.tick());
373         }
374         // Verify copy-in/out
375         {
376             final String msg = name + " copy-in/out";
377             ArraySet<Leaf> base = new ArraySet<>();
378             array.copyTo(base);
379             WatchedArraySet<Leaf> copy = new WatchedArraySet<>();
380             copy.copyFrom(base);
381             if (!array.equals(copy)) {
382                 fail(msg);
383             }
384         }
385     }
386 
387     @Test
testWatchedArrayList()388     public void testWatchedArrayList() {
389         final String name = "WatchedArrayList";
390         WatchableTester tester;
391 
392         // Create a few leaves
393         Leaf leafA = new Leaf();
394         Leaf leafB = new Leaf();
395         Leaf leafC = new Leaf();
396         Leaf leafD = new Leaf();
397 
398         // Redefine the indices used in the tests to be zero-based
399         final int indexA = 0;
400         final int indexB = 1;
401         final int indexC = 2;
402         final int indexD = 3;
403 
404         // Test WatchedArrayList
405         WatchedArrayList<Leaf> array = new WatchedArrayList<>();
406         // A spacer that takes up index 0 (and is not Watchable).
407         array.add(indexA, leafA);
408         array.add(indexB, leafB);
409         tester = new WatchableTester(array, name);
410         tester.verify(0, "Initial array - no registration");
411         leafA.tick();
412         tester.verify(0, "Updates with no registration");
413         tester.register();
414         tester.verify(0, "Updates with no registration");
415         leafA.tick();
416         tester.verify(1, "Updates with registration");
417         leafB.tick();
418         tester.verify(2, "Updates with registration");
419         array.remove(indexB);
420         tester.verify(3, "Removed b");
421         leafB.tick();
422         tester.verify(3, "Updates with b not watched");
423         array.add(indexB, leafB);
424         array.add(indexC, leafB);
425         tester.verify(5, "Added b twice");
426         leafB.tick();
427         tester.verify(6, "Changed b - single notification");
428         array.remove(indexC);
429         tester.verify(7, "Removed first b");
430         leafB.tick();
431         tester.verify(8, "Changed b - single notification");
432         array.remove(indexB);
433         tester.verify(9, "Removed second b");
434         leafB.tick();
435         tester.verify(9, "Updated leafB - no change");
436         array.clear();
437         tester.verify(10, "Cleared array");
438         leafB.tick();
439         tester.verify(10, "Change to b not in array");
440 
441         // Special methods
442         array.add(indexA, leafA);
443         array.add(indexB, leafB);
444         array.add(indexC, leafC);
445         tester.verify(13, "Added c");
446         leafC.tick();
447         tester.verify(14, "Ticked c");
448         array.set(array.indexOf(leafC), leafD);
449         tester.verify(15, "Replaced c with d");
450         leafC.tick();
451         leafD.tick();
452         tester.verify(16, "Ticked d and c (c not registered)");
453         array.add(leafC);
454         tester.verify(17, "Append c");
455         leafC.tick();
456         leafD.tick();
457         tester.verify(19, "Ticked d and c");
458 
459         // Snapshot
460         {
461             final WatchedArrayList<Leaf> arraySnap = array.snapshot();
462             tester.verify(19, "Generate snapshot (no changes)");
463             // Verify that the snapshot is a proper copy of the source.
464             assertEquals(name + " snap same size",
465                          array.size(), arraySnap.size());
466             for (int i = 0; i < array.size(); i++) {
467                 for (int j = 0; j < arraySnap.size(); j++) {
468                     assertTrue(name + " elements differ",
469                                array.get(i) != arraySnap.get(j));
470                 }
471                 assertTrue(name + " element copy",
472                            array.get(i).equals(arraySnap.get(i)));
473             }
474             leafD.tick();
475             tester.verify(20, "Tick after snapshot");
476             // Verify that the array snapshot is sealed
477             verifySealed(name, ()->arraySnap.add(indexA, leafB));
478             assertTrue(!array.isSealed());
479             assertTrue(arraySnap.isSealed());
480         }
481         // Recreate the snapshot since the test corrupted it.
482         {
483             final WatchedArrayList<Leaf> arraySnap = array.snapshot();
484             // Verify that elements are also snapshots
485             final Leaf arraySnapElement = arraySnap.get(0);
486             verifySealed("ArraySnapshotElement", ()->arraySnapElement.tick());
487         }
488         // Verify copy-in/out
489         {
490             final String msg = name + " copy-in/out";
491             ArrayList<Leaf> base = new ArrayList<>();
492             array.copyTo(base);
493             WatchedArrayList<Leaf> copy = new WatchedArrayList<>();
494             copy.copyFrom(base);
495             if (!array.equals(copy)) {
496                 fail(msg);
497             }
498         }
499     }
500 
501     @Test
testWatchedSparseArray()502     public void testWatchedSparseArray() {
503         final String name = "WatchedSparseArray";
504         WatchableTester tester;
505 
506         // Create a few leaves
507         Leaf leafA = new Leaf();
508         Leaf leafB = new Leaf();
509         Leaf leafC = new Leaf();
510         Leaf leafD = new Leaf();
511 
512         // Test WatchedSparseArray
513         WatchedSparseArray<Leaf> array = new WatchedSparseArray<>();
514         array.put(INDEX_A, leafA);
515         array.put(INDEX_B, leafB);
516         tester = new WatchableTester(array, name);
517         tester.verify(0, "Initial array - no registration");
518         leafA.tick();
519         tester.verify(0, "Updates with no registration");
520         tester.register();
521         tester.verify(0, "Updates with no registration");
522         leafA.tick();
523         tester.verify(1, "Updates with registration");
524         leafB.tick();
525         tester.verify(2, "Updates with registration");
526         array.remove(INDEX_B);
527         tester.verify(3, "Removed b");
528         leafB.tick();
529         tester.verify(3, "Updates with b not watched");
530         array.put(INDEX_B, leafB);
531         array.put(INDEX_C, leafB);
532         tester.verify(5, "Added b twice");
533         leafB.tick();
534         tester.verify(6, "Changed b - single notification");
535         array.remove(INDEX_C);
536         tester.verify(7, "Removed first b");
537         leafB.tick();
538         tester.verify(8, "Changed b - single notification");
539         array.remove(INDEX_B);
540         tester.verify(9, "Removed second b");
541         leafB.tick();
542         tester.verify(9, "Updated leafB - no change");
543         array.clear();
544         tester.verify(10, "Cleared array");
545         leafB.tick();
546         tester.verify(10, "Change to b not in array");
547 
548         // Special methods
549         array.put(INDEX_A, leafA);
550         array.put(INDEX_B, leafB);
551         array.put(INDEX_C, leafC);
552         tester.verify(13, "Added c");
553         leafC.tick();
554         tester.verify(14, "Ticked c");
555         array.setValueAt(array.indexOfKey(INDEX_C), leafD);
556         tester.verify(15, "Replaced c with d");
557         leafC.tick();
558         leafD.tick();
559         tester.verify(16, "Ticked d and c (c not registered)");
560         array.append(INDEX_D, leafC);
561         tester.verify(17, "Append c");
562         leafC.tick();
563         leafD.tick();
564         tester.verify(19, "Ticked d and c");
565         assertEquals("Verify four elements", 4, array.size());
566         // Figure out which elements are at which indices.
567         Leaf[] x = new Leaf[4];
568         for (int i = 0; i < 4; i++) {
569             x[i] = array.valueAt(i);
570         }
571         array.removeAtRange(0, 2);
572         tester.verify(20, "Removed two elements in one operation");
573         x[0].tick();
574         x[1].tick();
575         tester.verify(20, "Ticked two removed elements");
576         x[2].tick();
577         x[3].tick();
578         tester.verify(22, "Ticked two remaining elements");
579 
580         // Snapshot
581         {
582             final WatchedSparseArray<Leaf> arraySnap = array.snapshot();
583             tester.verify(22, "Generate snapshot (no changes)");
584             // Verify that the snapshot is a proper copy of the source.
585             assertEquals(name + " snap same size",
586                          array.size(), arraySnap.size());
587             for (int i = 0; i < array.size(); i++) {
588                 for (int j = 0; j < arraySnap.size(); j++) {
589                     assertTrue(name + " elements differ",
590                                array.valueAt(i) != arraySnap.valueAt(j));
591                 }
592                 assertTrue(name + " element copy",
593                            array.valueAt(i).equals(arraySnap.valueAt(i)));
594             }
595             leafD.tick();
596             tester.verify(23, "Tick after snapshot");
597             // Verify that the array snapshot is sealed
598             verifySealed(name, ()->arraySnap.put(INDEX_A, leafB));
599             assertTrue(!array.isSealed());
600             assertTrue(arraySnap.isSealed());
601         }
602         // Recreate the snapshot since the test corrupted it.
603         {
604             final WatchedSparseArray<Leaf> arraySnap = array.snapshot();
605             // Verify that elements are also snapshots
606             final Leaf arraySnapElement = arraySnap.valueAt(0);
607             verifySealed("ArraySnapshotElement", ()->arraySnapElement.tick());
608         }
609         // Verify copy-in/out
610         {
611             final String msg = name + " copy-in/out";
612             SparseArray<Leaf> base = new SparseArray<>();
613             array.copyTo(base);
614             WatchedSparseArray<Leaf> copy = new WatchedSparseArray<>();
615             copy.copyFrom(base);
616             final int end = array.size();
617             assertTrue(msg + " size mismatch " + end + " " + copy.size(), end == copy.size());
618             for (int i = 0; i < end; i++) {
619                 final int key = array.keyAt(i);
620                 assertTrue(msg, array.get(i) == copy.get(i));
621             }
622         }
623     }
624 
625     @Test
testWatchedLongSparseArray()626     public void testWatchedLongSparseArray() {
627         final String name = "WatchedLongSparseArray";
628         WatchableTester tester;
629 
630         // Create a few leaves
631         Leaf leafA = new Leaf();
632         Leaf leafB = new Leaf();
633         Leaf leafC = new Leaf();
634         Leaf leafD = new Leaf();
635 
636         // Test WatchedLongSparseArray
637         WatchedLongSparseArray<Leaf> array = new WatchedLongSparseArray<>();
638         array.put(INDEX_A, leafA);
639         array.put(INDEX_B, leafB);
640         tester = new WatchableTester(array, name);
641         tester.verify(0, "Initial array - no registration");
642         leafA.tick();
643         tester.verify(0, "Updates with no registration");
644         tester.register();
645         tester.verify(0, "Updates with no registration");
646         leafA.tick();
647         tester.verify(1, "Updates with registration");
648         leafB.tick();
649         tester.verify(2, "Updates with registration");
650         array.remove(INDEX_B);
651         tester.verify(3, "Removed b");
652         leafB.tick();
653         tester.verify(3, "Updates with b not watched");
654         array.put(INDEX_B, leafB);
655         array.put(INDEX_C, leafB);
656         tester.verify(5, "Added b twice");
657         leafB.tick();
658         tester.verify(6, "Changed b - single notification");
659         array.remove(INDEX_C);
660         tester.verify(7, "Removed first b");
661         leafB.tick();
662         tester.verify(8, "Changed b - single notification");
663         array.remove(INDEX_B);
664         tester.verify(9, "Removed second b");
665         leafB.tick();
666         tester.verify(9, "Updated leafB - no change");
667         array.clear();
668         tester.verify(10, "Cleared array");
669         leafB.tick();
670         tester.verify(10, "Change to b not in array");
671 
672         // Special methods
673         array.put(INDEX_A, leafA);
674         array.put(INDEX_B, leafB);
675         array.put(INDEX_C, leafC);
676         tester.verify(13, "Added c");
677         leafC.tick();
678         tester.verify(14, "Ticked c");
679         array.setValueAt(array.indexOfKey(INDEX_C), leafD);
680         tester.verify(15, "Replaced c with d");
681         leafC.tick();
682         tester.verify(15, "Ticked c (c not registered)");
683         leafD.tick();
684         tester.verify(16, "Ticked d and c (c not registered)");
685         array.append(INDEX_D, leafC);
686         tester.verify(17, "Append c");
687         leafC.tick();
688         leafD.tick();
689         tester.verify(19, "Ticked d and c");
690         assertEquals("Verify four elements", 4, array.size());
691         // Figure out which elements are at which indices.
692         Leaf[] x = new Leaf[4];
693         for (int i = 0; i < 4; i++) {
694             x[i] = array.valueAt(i);
695         }
696         array.removeAt(1);
697         tester.verify(20, "Removed one element");
698         x[1].tick();
699         tester.verify(20, "Ticked one removed element");
700         x[2].tick();
701         tester.verify(21, "Ticked one remaining element");
702 
703         // Snapshot
704         {
705             final WatchedLongSparseArray<Leaf> arraySnap = array.snapshot();
706             tester.verify(21, "Generate snapshot (no changes)");
707             // Verify that the snapshot is a proper copy of the source.
708             assertEquals(name + " snap same size",
709                          array.size(), arraySnap.size());
710             for (int i = 0; i < array.size(); i++) {
711                 for (int j = 0; j < arraySnap.size(); j++) {
712                     assertTrue(name + " elements differ",
713                                array.valueAt(i) != arraySnap.valueAt(j));
714                 }
715                 assertTrue(name + " element copy",
716                            array.valueAt(i).equals(arraySnap.valueAt(i)));
717             }
718             leafD.tick();
719             tester.verify(22, "Tick after snapshot");
720             // Verify that the array snapshot is sealed
721             verifySealed(name, ()->arraySnap.put(INDEX_A, leafB));
722             assertTrue(!array.isSealed());
723             assertTrue(arraySnap.isSealed());
724         }
725         // Recreate the snapshot since the test corrupted it.
726         {
727             final WatchedLongSparseArray<Leaf> arraySnap = array.snapshot();
728             // Verify that elements are also snapshots
729             final Leaf arraySnapElement = arraySnap.valueAt(0);
730             verifySealed("ArraySnapshotElement", ()->arraySnapElement.tick());
731         }
732         // Verify copy-in/out
733         {
734             final String msg = name + " copy-in/out";
735             LongSparseArray<Leaf> base = new LongSparseArray<>();
736             array.copyTo(base);
737             WatchedLongSparseArray<Leaf> copy = new WatchedLongSparseArray<>();
738             copy.copyFrom(base);
739             final int end = array.size();
740             assertTrue(msg + " size mismatch " + end + " " + copy.size(), end == copy.size());
741             for (int i = 0; i < end; i++) {
742                 final long key = array.keyAt(i);
743                 assertTrue(msg, array.get(i) == copy.get(i));
744             }
745         }
746     }
747 
748     @Test
testWatchedSparseBooleanArray()749     public void testWatchedSparseBooleanArray() {
750         final String name = "WatchedSparseBooleanArray";
751         WatchableTester tester;
752 
753         // Test WatchedSparseBooleanArray
754         WatchedSparseBooleanArray array = new WatchedSparseBooleanArray();
755         tester = new WatchableTester(array, name);
756         tester.verify(0, "Initial array - no registration");
757         array.put(INDEX_A, true);
758         tester.verify(0, "Updates with no registration");
759         tester.register();
760         tester.verify(0, "Updates with no registration");
761         array.put(INDEX_B, true);
762         tester.verify(1, "Updates with registration");
763         array.put(INDEX_B, false);
764         array.put(INDEX_C, true);
765         tester.verify(3, "Updates with registration");
766         // Special methods
767         array.setValueAt(array.indexOfKey(INDEX_C), false);
768         tester.verify(4, "Replaced true with false");
769         array.append(INDEX_D, true);
770         tester.verify(5, "Append true");
771 
772         // Snapshot
773         {
774             WatchedSparseBooleanArray arraySnap = array.snapshot();
775             tester.verify(5, "Generate snapshot");
776             // Verify that the snapshot is a proper copy of the source.
777             assertEquals("WatchedSparseBooleanArray snap same size",
778                          array.size(), arraySnap.size());
779             for (int i = 0; i < array.size(); i++) {
780                 assertEquals("WatchedSparseArray element copy",
781                              array.valueAt(i), arraySnap.valueAt(i));
782             }
783             array.put(INDEX_D, false);
784             tester.verify(6, "Tick after snapshot");
785             // Verify that the array is sealed
786             verifySealed(name, ()->arraySnap.put(INDEX_D, false));
787             assertTrue(!array.isSealed());
788             assertTrue(arraySnap.isSealed());
789         }
790         // Verify copy-in/out
791         {
792             final String msg = name + " copy-in/out";
793             SparseBooleanArray base = new SparseBooleanArray();
794             array.copyTo(base);
795             WatchedSparseBooleanArray copy = new WatchedSparseBooleanArray();
796             copy.copyFrom(base);
797             final int end = array.size();
798             assertTrue(msg + " size mismatch/2 " + end + " " + copy.size(), end == copy.size());
799             for (int i = 0; i < end; i++) {
800                 final int key = array.keyAt(i);
801                 assertTrue(msg + " element", array.get(i) == copy.get(i));
802             }
803         }
804     }
805 
806     @Test
testWatchedSparseIntArray()807     public void testWatchedSparseIntArray() {
808         final String name = "WatchedSparseIntArray";
809         WatchableTester tester;
810 
811         // Test WatchedSparseIntArray
812         WatchedSparseIntArray array = new WatchedSparseIntArray();
813         tester = new WatchableTester(array, name);
814         tester.verify(0, "Initial array - no registration");
815         array.put(INDEX_A, 1);
816         tester.verify(0, "Updates with no registration");
817         tester.register();
818         tester.verify(0, "Updates with no registration");
819         array.put(INDEX_B, 2);
820         tester.verify(1, "Updates with registration");
821         array.put(INDEX_B, 4);
822         array.put(INDEX_C, 5);
823         tester.verify(3, "Updates with registration");
824         // Special methods
825         array.setValueAt(array.indexOfKey(INDEX_C), 7);
826         tester.verify(4, "Replaced 6 with 7");
827         array.append(INDEX_D, 8);
828         tester.verify(5, "Append 8");
829 
830         // Snapshot
831         {
832             WatchedSparseIntArray arraySnap = array.snapshot();
833             tester.verify(5, "Generate snapshot");
834             // Verify that the snapshot is a proper copy of the source.
835             assertEquals("WatchedSparseIntArray snap same size",
836                          array.size(), arraySnap.size());
837             for (int i = 0; i < array.size(); i++) {
838                 assertEquals(name + " element copy",
839                              array.valueAt(i), arraySnap.valueAt(i));
840             }
841             array.put(INDEX_D, 9);
842             tester.verify(6, "Tick after snapshot");
843             // Verify that the array is sealed
844             verifySealed(name, ()->arraySnap.put(INDEX_D, 10));
845             assertTrue(!array.isSealed());
846             assertTrue(arraySnap.isSealed());
847         }
848         // Verify copy-in/out
849         {
850             final String msg = name + " copy-in/out";
851             SparseIntArray base = new SparseIntArray();
852             array.copyTo(base);
853             WatchedSparseIntArray copy = new WatchedSparseIntArray();
854             copy.copyFrom(base);
855             final int end = array.size();
856             assertTrue(msg + " size mismatch " + end + " " + copy.size(), end == copy.size());
857             for (int i = 0; i < end; i++) {
858                 final int key = array.keyAt(i);
859                 assertTrue(msg, array.get(i) == copy.get(i));
860             }
861         }
862     }
863 
864     @Test
testWatchedSparseSetArray()865     public void testWatchedSparseSetArray() {
866         final String name = "WatchedSparseSetArray";
867         WatchableTester tester;
868 
869         // Test WatchedSparseSetArray
870         WatchedSparseSetArray array = new WatchedSparseSetArray();
871         tester = new WatchableTester(array, name);
872         tester.verify(0, "Initial array - no registration");
873         array.add(INDEX_A, 1);
874         tester.verify(0, "Updates with no registration");
875         tester.register();
876         tester.verify(0, "Updates with no registration");
877         array.add(INDEX_B, 2);
878         tester.verify(1, "Updates with registration");
879         array.add(INDEX_B, 4);
880         array.add(INDEX_C, 5);
881         tester.verify(3, "Updates with registration");
882         // Special methods
883         assertTrue(array.remove(INDEX_C, 5));
884         tester.verify(4, "Removed 5 from key 3");
885         array.remove(INDEX_B);
886         tester.verify(5, "Removed everything for key 2");
887 
888         // Snapshot
889         {
890             WatchedSparseSetArray arraySnap = (WatchedSparseSetArray) array.snapshot();
891             tester.verify(5, "Generate snapshot");
892             // Verify that the snapshot is a proper copy of the source.
893             assertEquals("WatchedSparseSetArray snap same size",
894                     array.size(), arraySnap.size());
895             for (int i = 0; i < array.size(); i++) {
896                 ArraySet set = array.get(array.keyAt(i));
897                 ArraySet setSnap = arraySnap.get(arraySnap.keyAt(i));
898                 assertNotNull(set);
899                 assertTrue(set.equals(setSnap));
900             }
901             array.add(INDEX_D, 9);
902             tester.verify(6, "Tick after snapshot");
903             // Verify that the array is sealed
904             verifySealed(name, ()->arraySnap.add(INDEX_D, 10));
905             assertTrue(!array.isSealed());
906             assertTrue(arraySnap.isSealed());
907         }
908         array.clear();
909         tester.verify(7, "Cleared all entries");
910     }
911 
912     private static class IndexGenerator {
913         private final int mSeed;
914         private final Random mRandom;
IndexGenerator(int seed)915         public IndexGenerator(int seed) {
916             mSeed = seed;
917             mRandom = new Random(mSeed);
918         }
next()919         public int next() {
920             return mRandom.nextInt(50000);
921         }
reset()922         public void reset() {
923             mRandom.setSeed(mSeed);
924         }
925         // This is an inefficient way to know if a value appears in an array.
contains(int[] s, int length, int k)926         private boolean contains(int[] s, int length, int k) {
927             for (int i = 0; i < length; i++) {
928                 if (s[i] == k) {
929                     return true;
930                 }
931             }
932             return false;
933         }
indexes(int size)934         public int[] indexes(int size) {
935             reset();
936             int[] r = new int[size];
937             for (int i = 0; i < size; i++) {
938                 int key = next();
939                 // Ensure the list of indices are unique.
940                 while (contains(r, i, key)) {
941                     key = next();
942                 }
943                 r[i] = key;
944             }
945             return r;
946         }
947     }
948 
949     // Return a value based on the row and column.  The algorithm tries to avoid simple
950     // patterns like checkerboard.
cellValue(int row, int col)951     private final boolean cellValue(int row, int col) {
952         return (((row * 4 + col) % 3)& 1) == 1;
953     }
954 
955     // Fill a matrix
fill(WatchedSparseBooleanMatrix matrix, int size, int[] indexes)956     private void fill(WatchedSparseBooleanMatrix matrix, int size, int[] indexes) {
957         for (int i = 0; i < size; i++) {
958             int row = indexes[i];
959             for (int j = 0; j < size; j++) {
960                 int col = indexes[j];
961                 boolean want = cellValue(i, j);
962                 matrix.put(row, col, want);
963             }
964         }
965     }
966 
967     // Fill new cells in the matrix which has enlarged capacity.
fillNew(WatchedSparseBooleanMatrix matrix, int initialCapacity, int newCapacity, int[] indexes)968     private void fillNew(WatchedSparseBooleanMatrix matrix, int initialCapacity,
969             int newCapacity, int[] indexes) {
970         final int size = newCapacity;
971         for (int i = 0; i < size; i++) {
972             for (int j = 0; j < size; j++) {
973                 if (i < initialCapacity && j < initialCapacity) {
974                     // Do not touch old cells
975                     continue;
976                 }
977                 final int row = indexes[i];
978                 final int col = indexes[j];
979                 matrix.put(row, col, cellValue(i, j));
980             }
981         }
982     }
983 
984     // Verify the content of a matrix.  This asserts on mismatch.  Selected indices may
985     // have been deleted.
verify(WatchedSparseBooleanMatrix matrix, int[] indexes, boolean[] absent)986     private void verify(WatchedSparseBooleanMatrix matrix, int[] indexes, boolean[] absent) {
987         for (int i = 0; i < matrix.size(); i++) {
988             int row = indexes[i];
989             for (int j = 0; j < matrix.size(); j++) {
990                 int col = indexes[j];
991                 if (absent != null && (absent[i] || absent[j])) {
992                     boolean want = false;
993                     String msg = String.format("matrix(%d:%d, %d:%d) (deleted)", i, row, j, col);
994                     assertEquals(msg, matrix.get(row, col), false);
995                     assertEquals(msg, matrix.get(row, col, false), false);
996                     assertEquals(msg, matrix.get(row, col, true), true);
997                 } else {
998                     boolean want = cellValue(i, j);
999                     String msg = String.format("matrix(%d:%d, %d:%d)", i, row, j, col);
1000                     assertEquals(msg, matrix.get(row, col), want);
1001                     assertEquals(msg, matrix.get(row, col, false), want);
1002                     assertEquals(msg, matrix.get(row, col, true), want);
1003                 }
1004             }
1005         }
1006     }
1007 
matrixGrow(WatchedSparseBooleanMatrix matrix, int size, IndexGenerator indexer)1008     private void matrixGrow(WatchedSparseBooleanMatrix matrix, int size, IndexGenerator indexer) {
1009         int[] indexes = indexer.indexes(size);
1010 
1011         // Set values in the matrix, then read back and verify.
1012         fill(matrix, size, indexes);
1013         assertEquals(matrix.size(), size);
1014         verify(matrix, indexes, null);
1015 
1016         // Test the keyAt/indexOfKey methods
1017         for (int i = 0; i < matrix.size(); i++) {
1018             int key = indexes[i];
1019             assertEquals(matrix.keyAt(matrix.indexOfKey(key)), key);
1020         }
1021     }
1022 
matrixDelete(WatchedSparseBooleanMatrix matrix, int size, IndexGenerator indexer)1023     private void matrixDelete(WatchedSparseBooleanMatrix matrix, int size, IndexGenerator indexer) {
1024         int[] indexes = indexer.indexes(size);
1025         fill(matrix, size, indexes);
1026 
1027         // Delete a bunch of rows.  Verify that reading back results in false and that
1028         // contains() is false.  Recreate the rows and verify that all cells (other than
1029         // the one just created) are false.
1030         boolean[] absent = new boolean[size];
1031         for (int i = 0; i < size; i += 13) {
1032             matrix.deleteKey(indexes[i]);
1033             absent[i] = true;
1034         }
1035         verify(matrix, indexes, absent);
1036     }
1037 
matrixShrink(WatchedSparseBooleanMatrix matrix, int size, IndexGenerator indexer)1038     private void matrixShrink(WatchedSparseBooleanMatrix matrix, int size, IndexGenerator indexer) {
1039         int[] indexes = indexer.indexes(size);
1040         fill(matrix, size, indexes);
1041 
1042         int initialCapacity = matrix.capacity();
1043 
1044         // Delete every other row, remembering which rows were deleted.  The goal is to
1045         // make room for compaction.
1046         boolean[] absent = new boolean[size];
1047         for (int i = 0; i < size; i += 2) {
1048             matrix.deleteKey(indexes[i]);
1049             absent[i] = true;
1050         }
1051 
1052         matrix.compact();
1053         int finalCapacity = matrix.capacity();
1054         assertTrue("Matrix shrink", initialCapacity > finalCapacity);
1055         assertTrue("Matrix shrink", finalCapacity - matrix.size() < matrix.STEP);
1056     }
1057 
matrixSetCapacity(WatchedSparseBooleanMatrix matrix, int newCapacity, IndexGenerator indexer)1058     private void matrixSetCapacity(WatchedSparseBooleanMatrix matrix, int newCapacity,
1059             IndexGenerator indexer) {
1060         final int initialCapacity = matrix.capacity();
1061         final int[] indexes = indexer.indexes(Math.max(initialCapacity, newCapacity));
1062         fill(matrix, initialCapacity, indexes);
1063 
1064         matrix.setCapacity(newCapacity);
1065         fillNew(matrix, initialCapacity, newCapacity, indexes);
1066 
1067         assertEquals(matrix.size(), indexes.length);
1068         verify(matrix, indexes, null);
1069         // Test the keyAt/indexOfKey methods
1070         for (int i = 0; i < matrix.size(); i++) {
1071             int key = indexes[i];
1072             assertEquals(matrix.keyAt(matrix.indexOfKey(key)), key);
1073         }
1074     }
1075 
1076     @Test
testWatchedSparseBooleanMatrix()1077     public void testWatchedSparseBooleanMatrix() {
1078         final String name = "WatchedSparseBooleanMatrix";
1079 
1080         // Test the core matrix functionality.  The three tess are meant to test various
1081         // combinations of auto-grow.
1082         IndexGenerator indexer = new IndexGenerator(3);
1083         matrixGrow(new WatchedSparseBooleanMatrix(), 10, indexer);
1084         matrixGrow(new WatchedSparseBooleanMatrix(1000), 500, indexer);
1085         matrixGrow(new WatchedSparseBooleanMatrix(1000), 2000, indexer);
1086         matrixDelete(new WatchedSparseBooleanMatrix(), 500, indexer);
1087         matrixShrink(new WatchedSparseBooleanMatrix(), 500, indexer);
1088 
1089         // Test Watchable behavior.
1090         WatchedSparseBooleanMatrix matrix = new WatchedSparseBooleanMatrix();
1091         WatchableTester tester = new WatchableTester(matrix, name);
1092         tester.verify(0, "Initial array - no registration");
1093         matrix.put(INDEX_A, INDEX_A, true);
1094         tester.verify(0, "Updates with no registration");
1095         tester.register();
1096         tester.verify(0, "Updates with no registration");
1097         matrix.put(INDEX_A, INDEX_B, true);
1098         tester.verify(1, "Single cell assignment");
1099         matrix.put(INDEX_A, INDEX_B, true);
1100         tester.verify(2, "Single cell assignment - same value");
1101         matrix.put(INDEX_C, INDEX_B, true);
1102         tester.verify(3, "Single cell assignment");
1103         matrix.deleteKey(INDEX_B);
1104         tester.verify(4, "Delete key");
1105         assertEquals(matrix.get(INDEX_B, INDEX_C), false);
1106         assertEquals(matrix.get(INDEX_B, INDEX_C, false), false);
1107         assertEquals(matrix.get(INDEX_B, INDEX_C, true), true);
1108 
1109         matrix.clear();
1110         tester.verify(5, "Clear");
1111         assertEquals(matrix.size(), 0);
1112         fill(matrix, 10, indexer.indexes(10));
1113         int[] keys = matrix.keys();
1114         assertEquals(keys.length, matrix.size());
1115         for (int i = 0; i < matrix.size(); i++) {
1116             assertEquals(matrix.keyAt(i), keys[i]);
1117         }
1118 
1119         WatchedSparseBooleanMatrix a = new WatchedSparseBooleanMatrix();
1120         matrixGrow(a, 10, indexer);
1121         assertEquals(a.size(), 10);
1122         WatchedSparseBooleanMatrix b = new WatchedSparseBooleanMatrix();
1123         matrixGrow(b, 10, indexer);
1124         assertEquals(b.size(), 10);
1125         assertEquals(a.equals(b), true);
1126         int rowIndex = b.keyAt(3);
1127         int colIndex = b.keyAt(4);
1128         b.put(rowIndex, colIndex, !b.get(rowIndex, colIndex));
1129         assertEquals(a.equals(b), false);
1130 
1131         // Test Snappable behavior.
1132         WatchedSparseBooleanMatrix s = a.snapshot();
1133         assertEquals(a.equals(s), true);
1134         a.put(rowIndex, colIndex, !a.get(rowIndex, colIndex));
1135         assertEquals(a.equals(s), false);
1136 
1137         // Verify copy-in/out
1138         {
1139             final String msg = name + " copy";
1140             WatchedSparseBooleanMatrix copy = new WatchedSparseBooleanMatrix();
1141             copy.copyFrom(matrix);
1142             final int end = copy.size();
1143             assertTrue(msg + " size mismatch " + end + " " + matrix.size(), end == matrix.size());
1144             for (int i = 0; i < end; i++) {
1145                 assertEquals(copy.keyAt(i), keys[i]);
1146             }
1147         }
1148     }
1149 
1150     @Test
testWatchedSparseBooleanMatrix_setCapacity()1151     public void testWatchedSparseBooleanMatrix_setCapacity() {
1152         final IndexGenerator indexer = new IndexGenerator(3);
1153         matrixSetCapacity(new WatchedSparseBooleanMatrix(500), 1000, indexer);
1154         matrixSetCapacity(new WatchedSparseBooleanMatrix(1000), 500, indexer);
1155     }
1156 
1157     @Test
testWatchedSparseBooleanMatrix_removeRangeAndShrink()1158     public void testWatchedSparseBooleanMatrix_removeRangeAndShrink() {
1159         final IndexGenerator indexer = new IndexGenerator(3);
1160         final int initialCapacity = 500;
1161         final int removeCounts = 33;
1162         final WatchedSparseBooleanMatrix matrix = new WatchedSparseBooleanMatrix(initialCapacity);
1163         final int[] indexes = indexer.indexes(initialCapacity);
1164         final boolean[] absents = new boolean[initialCapacity];
1165         fill(matrix, initialCapacity, indexes);
1166         assertEquals(matrix.size(), initialCapacity);
1167 
1168         for (int i = 0; i < initialCapacity / removeCounts; i++) {
1169             final int size = matrix.size();
1170             final int fromIndex = (size / 2 < removeCounts ? 0 : size / 2 - removeCounts);
1171             final int toIndex = (fromIndex + removeCounts > size ? size : fromIndex + removeCounts);
1172             for (int index = fromIndex; index < toIndex; index++) {
1173                 final int key = matrix.keyAt(index);
1174                 for (int j = 0; j < indexes.length; j++) {
1175                     if (key == indexes[j]) {
1176                         absents[j] = true;
1177                         break;
1178                     }
1179                 }
1180             }
1181             matrix.removeRange(fromIndex, toIndex);
1182             assertEquals(matrix.size(), size - (toIndex - fromIndex));
1183             verify(matrix, indexes, absents);
1184 
1185             matrix.compact();
1186             verify(matrix, indexes, absents);
1187         }
1188     }
1189 
1190     @Test
testNestedArrays()1191     public void testNestedArrays() {
1192         final String name = "NestedArrays";
1193         WatchableTester tester;
1194 
1195         // Create a few leaves
1196         Leaf leafA = new Leaf();
1197         Leaf leafB = new Leaf();
1198         Leaf leafC = new Leaf();
1199         Leaf leafD = new Leaf();
1200 
1201         // Test nested arrays.
1202         WatchedLongSparseArray<Leaf> lsaA = new WatchedLongSparseArray<>();
1203         lsaA.put(2, leafA);
1204         WatchedLongSparseArray<Leaf> lsaB = new WatchedLongSparseArray<>();
1205         lsaB.put(4, leafB);
1206         WatchedLongSparseArray<Leaf> lsaC = new WatchedLongSparseArray<>();
1207         lsaC.put(6, leafC);
1208 
1209         WatchedArrayMap<String, WatchedLongSparseArray<Leaf>> array =
1210                 new WatchedArrayMap<>();
1211         array.put("A", lsaA);
1212         array.put("B", lsaB);
1213 
1214         // Test WatchedSparseIntArray
1215         tester = new WatchableTester(array, name);
1216         tester.verify(0, "Initial array - no registration");
1217         tester.register();
1218         tester.verify(0, "Initial array - post registration");
1219         leafA.tick();
1220         tester.verify(1, "tick grand-leaf");
1221         lsaA.put(2, leafD);
1222         tester.verify(2, "replace leafA");
1223         leafA.tick();
1224         tester.verify(2, "tick unregistered leafA");
1225         leafD.tick();
1226         tester.verify(3, "tick leafD");
1227     }
1228 
1229     @Test
testSnapshotCache()1230     public void testSnapshotCache() {
1231         final String name = "SnapshotCache";
1232         WatchableTester tester;
1233 
1234         Leaf leafA = new Leaf();
1235         SnapshotCache<Leaf> cache = new SnapshotCache<>(leafA, leafA) {
1236                 @Override
1237                 public Leaf createSnapshot() {
1238                     return mSource.snapshot();
1239                 }};
1240 
1241         Leaf s1 = cache.snapshot();
1242         assertTrue(s1 == cache.snapshot());
1243         leafA.tick();
1244         Leaf s2 = cache.snapshot();
1245         assertTrue(s1 != s2);
1246         assertTrue(leafA.get() == s1.get() + 1);
1247         assertTrue(leafA.get() == s2.get());
1248 
1249         // Test sealed snapshots
1250         SnapshotCache<Leaf> sealed = new SnapshotCache.Sealed();
1251         try {
1252             Leaf x1 = sealed.snapshot();
1253             fail(name + " sealed snapshot did not throw");
1254         } catch (UnsupportedOperationException e) {
1255             // This is the passing scenario - the exception is expected.
1256         }
1257     }
1258 }
1259