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