common/util/src/test/java/org/opendaylight/yangtools/util/OffsetMapTest.java

   1 /*
   2  * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.util;
   9
  10 import static org.junit.jupiter.api.Assertions.assertEquals;
  11 import static org.junit.jupiter.api.Assertions.assertFalse;
  12 import static org.junit.jupiter.api.Assertions.assertInstanceOf;
  13 import static org.junit.jupiter.api.Assertions.assertNotEquals;
  14 import static org.junit.jupiter.api.Assertions.assertNotSame;
  15 import static org.junit.jupiter.api.Assertions.assertNull;
  16 import static org.junit.jupiter.api.Assertions.assertSame;
  17 import static org.junit.jupiter.api.Assertions.assertThrows;
  18 import static org.junit.jupiter.api.Assertions.assertTrue;
  19
  20 import com.google.common.collect.ImmutableMap;
  21 import com.google.common.collect.Iterables;
  22 import com.google.common.collect.Iterators;
  23 import java.io.ByteArrayInputStream;
  24 import java.io.ByteArrayOutputStream;
  25 import java.io.IOException;
  26 import java.io.ObjectInputStream;
  27 import java.io.ObjectOutputStream;
  28 import java.util.AbstractMap.SimpleEntry;
  29 import java.util.ConcurrentModificationException;
  30 import java.util.Iterator;
  31 import java.util.Map;
  32 import java.util.NoSuchElementException;
  33 import org.junit.jupiter.api.BeforeEach;
  34 import org.junit.jupiter.api.Test;
  35
  36 public class OffsetMapTest {
  37     private final Map<String, String> twoEntryMap = ImmutableMap.of("k1", "v1", "k2", "v2");
  38     private final Map<String, String> threeEntryMap = ImmutableMap.of("k1", "v1", "k2", "v2", "k3", "v3");
  39
  40     private ImmutableOffsetMap<String, String> createMap() {
  41         return (ImmutableOffsetMap<String, String>) ImmutableOffsetMap.orderedCopyOf(twoEntryMap);
  42     }
  43
  44     private ImmutableOffsetMap<String, String> unorderedMap() {
  45         return (ImmutableOffsetMap<String, String>) ImmutableOffsetMap.unorderedCopyOf(twoEntryMap);
  46     }
  47
  48     @BeforeEach
  49     void setup() {
  50         OffsetMapCache.invalidateCache();
  51     }
  52
  53     public void testWrongImmutableConstruction() {
  54         assertThrows(IllegalArgumentException.class,
  55             () -> new ImmutableOffsetMap.Ordered<>(ImmutableMap.of(), new String[1]));
  56     }
  57
  58     @Test
  59     void testCopyEmptyMap() {
  60         final var source = Map.of();
  61         final var result = ImmutableOffsetMap.orderedCopyOf(source);
  62
  63         assertEquals(source, result);
  64         assertInstanceOf(ImmutableMap.class, result);
  65     }
  66
  67     @Test
  68     void testCopySingletonMap() {
  69         final var source = Map.of("a", "b");
  70         final var result = ImmutableOffsetMap.orderedCopyOf(source);
  71
  72         assertEquals(source, result);
  73         assertInstanceOf(SharedSingletonMap.class, result);
  74     }
  75
  76     @Test
  77     void testCopyMap() {
  78         final var map = createMap();
  79
  80         // Equality in both directions
  81         assertEquals(twoEntryMap, map);
  82         assertEquals(map, twoEntryMap);
  83
  84         // hashcode has to match
  85         assertEquals(twoEntryMap.hashCode(), map.hashCode());
  86
  87         // Iterator order needs to be preserved
  88         assertTrue(Iterators.elementsEqual(twoEntryMap.entrySet().iterator(), map.entrySet().iterator()));
  89
  90         // Should result in the same object
  91         assertSame(map, ImmutableOffsetMap.orderedCopyOf(map));
  92
  93         final var mutable = map.toModifiableMap();
  94         final var copy = ImmutableOffsetMap.orderedCopyOf(mutable);
  95
  96         assertEquals(mutable, copy);
  97         assertEquals(map, copy);
  98         assertNotSame(mutable, copy);
  99         assertNotSame(map, copy);
 100     }
 101
 102     @Test
 103     void testImmutableSimpleEquals() {
 104         final var map = createMap();
 105
 106         assertEquals(map, map);
 107         assertNotEquals(null, map);
 108         assertNotEquals("string", map);
 109     }
 110
 111     @Test
 112     void testImmutableGet() {
 113         final var map = createMap();
 114
 115         assertEquals("v1", map.get("k1"));
 116         assertEquals("v2", map.get("k2"));
 117         assertNull(map.get("non-existent"));
 118         assertNull(map.get(null));
 119     }
 120
 121     @Test
 122     void testImmutableGuards() {
 123         final var map = createMap();
 124
 125         final var values = map.values();
 126         assertThrows(UnsupportedOperationException.class, () -> values.add("v1"));
 127         assertThrows(UnsupportedOperationException.class, () -> values.remove("v1"));
 128         assertThrows(UnsupportedOperationException.class, () -> values.clear());
 129
 130         final var vit = values.iterator();
 131         vit.next();
 132         assertThrows(UnsupportedOperationException.class, () -> vit.remove());
 133
 134         final var keySet = map.keySet();
 135         assertThrows(UnsupportedOperationException.class, () -> keySet.add("k1"));
 136         assertThrows(UnsupportedOperationException.class, () -> keySet.clear());
 137         assertThrows(UnsupportedOperationException.class, () -> keySet.remove("k1"));
 138
 139         final var kit = keySet.iterator();
 140         kit.next();
 141         assertThrows(UnsupportedOperationException.class, () -> kit.remove());
 142
 143         final var entrySet = map.entrySet();
 144         assertThrows(UnsupportedOperationException.class, () -> entrySet.clear());
 145         assertThrows(UnsupportedOperationException.class, () -> entrySet.add(new SimpleEntry<>("k1", "v1")));
 146         assertThrows(UnsupportedOperationException.class, () -> entrySet.remove(new SimpleEntry<>("k1", "v1")));
 147
 148         final var eit = entrySet.iterator();
 149         eit.next();
 150         assertThrows(UnsupportedOperationException.class, () -> eit.remove());
 151
 152         assertThrows(UnsupportedOperationException.class, () -> map.clear());
 153         assertThrows(UnsupportedOperationException.class, () -> map.put("k1", "fail"));
 154         assertThrows(UnsupportedOperationException.class, () -> map.putAll(ImmutableMap.of("k1", "fail")));
 155         assertThrows(UnsupportedOperationException.class, () -> map.remove("k1"));
 156     }
 157
 158     @Test
 159     void testMutableGet() {
 160         final var map = createMap().toModifiableMap();
 161
 162         map.put("k3", "v3");
 163         assertEquals("v1", map.get("k1"));
 164         assertEquals("v2", map.get("k2"));
 165         assertEquals("v3", map.get("k3"));
 166         assertNull(map.get("non-existent"));
 167         assertNull(map.get(null));
 168     }
 169
 170     @Test
 171     void testImmutableSize() {
 172         final var map = createMap();
 173         assertEquals(2, map.size());
 174     }
 175
 176     @Test
 177     void testImmutableIsEmpty() {
 178         final var map = createMap();
 179         assertFalse(map.isEmpty());
 180     }
 181
 182     @Test
 183     void testImmutableContains() {
 184         final var map = createMap();
 185         assertTrue(map.containsKey("k1"));
 186         assertTrue(map.containsKey("k2"));
 187         assertFalse(map.containsKey("non-existent"));
 188         assertFalse(map.containsKey(null));
 189         assertTrue(map.containsValue("v1"));
 190         assertFalse(map.containsValue("non-existent"));
 191     }
 192
 193     @Test
 194     void testImmutableEquals() {
 195         final var map = createMap();
 196
 197         assertNotEquals(map, threeEntryMap);
 198         assertNotEquals(map, ImmutableMap.of("k1", "v1", "k3", "v3"));
 199         assertNotEquals(map, ImmutableMap.of("k1", "v1", "k2", "different-value"));
 200     }
 201
 202     @Test
 203     void testMutableContains() {
 204         final var map = createMap().toModifiableMap();
 205         map.put("k3", "v3");
 206         assertTrue(map.containsKey("k1"));
 207         assertTrue(map.containsKey("k2"));
 208         assertTrue(map.containsKey("k3"));
 209         assertFalse(map.containsKey("non-existent"));
 210         assertFalse(map.containsKey(null));
 211     }
 212
 213     @Test
 214     void testtoModifiableMap() {
 215         final var source = createMap();
 216         final var result = source.toModifiableMap();
 217
 218         // The two maps should be equal, but isolated
 219         assertInstanceOf(MutableOffsetMap.class, result);
 220         assertEquals(source, result);
 221         assertEquals(result, source);
 222
 223         // Quick test for clearing MutableOffsetMap
 224         result.clear();
 225         assertEquals(0, result.size());
 226         assertEquals(Map.of(), result);
 227
 228         // The two maps should differ now
 229         assertNotEquals(source, result);
 230         assertNotEquals(result, source);
 231
 232         // The source map should still equal the template
 233         assertEquals(twoEntryMap, source);
 234         assertEquals(source, twoEntryMap);
 235     }
 236
 237     @Test
 238     void testReusedFields() {
 239         final var source = createMap();
 240         final var mutable = source.toModifiableMap();
 241
 242         // Should not affect the result
 243         mutable.remove("non-existent");
 244
 245         // Resulting map should be equal, but not the same object
 246         final var result = (ImmutableOffsetMap<String, String>) mutable
 247                 .toUnmodifiableMap();
 248         assertNotSame(source, result);
 249         assertEquals(source, result);
 250
 251         // Internal fields should be reused
 252         assertSame(source.offsets(), result.offsets());
 253         assertSame(source.objects(), result.objects());
 254     }
 255
 256     @Test
 257     void testReusedOffsets() {
 258         final var source = createMap();
 259         final var mutable = source.toModifiableMap();
 260
 261         mutable.remove("k1");
 262         mutable.put("k1", "v1");
 263
 264         final var result = (ImmutableOffsetMap<String, String>) mutable
 265                 .toUnmodifiableMap();
 266         assertEquals(source, result);
 267         assertEquals(result, source);
 268
 269         // Iterator order must not be preserved
 270         assertFalse(Iterators.elementsEqual(source.entrySet().iterator(), result.entrySet().iterator()));
 271     }
 272
 273     @Test
 274     void testReusedOffsetsUnordered() {
 275         final var source = unorderedMap();
 276         final var mutable = source.toModifiableMap();
 277
 278         mutable.remove("k1");
 279         mutable.put("k1", "v1");
 280
 281         final var result = (ImmutableOffsetMap<String, String>) mutable
 282                 .toUnmodifiableMap();
 283         assertEquals(source, result);
 284
 285         // Only offsets should be shared
 286         assertSame(source.offsets(), result.offsets());
 287         assertNotSame(source.objects(), result.objects());
 288
 289         // Iterator order needs to be preserved
 290         assertTrue(Iterators.elementsEqual(source.entrySet().iterator(), result.entrySet().iterator()));
 291     }
 292
 293     @Test
 294     void testEmptyMutable() throws CloneNotSupportedException {
 295         final var map = MutableOffsetMap.ordered();
 296         assertTrue(map.isEmpty());
 297
 298         final var other = map.clone();
 299         assertEquals(other, map);
 300         assertNotSame(other, map);
 301     }
 302
 303     @Test
 304     void testMutableToEmpty() {
 305         final var mutable = createMap().toModifiableMap();
 306
 307         mutable.remove("k1");
 308         mutable.remove("k2");
 309
 310         assertTrue(mutable.isEmpty());
 311         assertSame(ImmutableMap.of(), mutable.toUnmodifiableMap());
 312     }
 313
 314     @Test
 315     void testMutableToSingleton() {
 316         final var mutable = createMap().toModifiableMap();
 317
 318         mutable.remove("k1");
 319
 320         final var result = mutable.toUnmodifiableMap();
 321
 322         // Should devolve to a singleton
 323         assertInstanceOf(SharedSingletonMap.class, result);
 324         assertEquals(ImmutableMap.of("k2", "v2"), result);
 325     }
 326
 327     @Test
 328     void testMutableToNewSingleton() {
 329         final var mutable = createMap().toModifiableMap();
 330
 331         mutable.remove("k1");
 332         mutable.put("k3", "v3");
 333
 334         final var result = mutable.toUnmodifiableMap();
 335
 336         assertInstanceOf(ImmutableOffsetMap.class, result);
 337         assertEquals(ImmutableMap.of("k2", "v2", "k3", "v3"), result);
 338     }
 339
 340     @Test
 341     void testMutableSize() {
 342         final var mutable = createMap().toModifiableMap();
 343         assertEquals(2, mutable.size());
 344
 345         mutable.put("k3", "v3");
 346         assertEquals(3, mutable.size());
 347         mutable.remove("k2");
 348         assertEquals(2, mutable.size());
 349         mutable.put("k1", "new-v1");
 350         assertEquals(2, mutable.size());
 351     }
 352
 353     @Test
 354     void testExpansionWithOrder() {
 355         final var mutable = createMap().toModifiableMap();
 356
 357         mutable.remove("k1");
 358         mutable.put("k3", "v3");
 359         mutable.put("k1", "v1");
 360
 361         assertEquals(ImmutableMap.of("k1", "v1", "k3", "v3"), mutable.newKeys());
 362
 363         final var result = mutable.toUnmodifiableMap();
 364
 365         assertInstanceOf(ImmutableOffsetMap.class, result);
 366         assertEquals(threeEntryMap, result);
 367         assertEquals(result, threeEntryMap);
 368         assertFalse(Iterators.elementsEqual(threeEntryMap.entrySet().iterator(), result.entrySet().iterator()));
 369     }
 370
 371     @Test
 372     void testExpansionWithoutOrder() {
 373         final var mutable = unorderedMap().toModifiableMap();
 374
 375         mutable.remove("k1");
 376         mutable.put("k3", "v3");
 377         mutable.put("k1", "v1");
 378
 379         assertEquals(ImmutableMap.of("k3", "v3"), mutable.newKeys());
 380
 381         final var result = mutable.toUnmodifiableMap();
 382
 383         assertInstanceOf(ImmutableOffsetMap.class, result);
 384         assertEquals(threeEntryMap, result);
 385         assertEquals(result, threeEntryMap);
 386         assertTrue(Iterators.elementsEqual(threeEntryMap.entrySet().iterator(), result.entrySet().iterator()));
 387     }
 388
 389     @Test
 390     void testReplacedValue() {
 391         final var source = createMap();
 392         final var mutable = source.toModifiableMap();
 393
 394         mutable.put("k1", "replaced");
 395
 396         final var result = (ImmutableOffsetMap<String, String>) mutable
 397                 .toUnmodifiableMap();
 398         final var reference = ImmutableMap.of("k1", "replaced", "k2", "v2");
 399
 400         assertEquals(reference, result);
 401         assertEquals(result, reference);
 402         assertSame(source.offsets(), result.offsets());
 403         assertNotSame(source.objects(), result.objects());
 404     }
 405
 406     @Test
 407     void testCloneableFlipping() throws CloneNotSupportedException {
 408         final var source = createMap().toModifiableMap();
 409
 410         // Must clone before mutation
 411         assertTrue(source.needClone());
 412
 413         // Non-existent entry, should not clone
 414         source.remove("non-existent");
 415         assertTrue(source.needClone());
 416
 417         // Changes the array, should clone
 418         source.remove("k1");
 419         assertFalse(source.needClone());
 420
 421         // Create a clone of the map, which shares the array
 422         final var result = source.clone();
 423         assertFalse(source.needClone());
 424         assertTrue(result.needClone());
 425         assertSame(source.array(), result.array());
 426
 427         // Changes the array, should clone
 428         source.put("k1", "v2");
 429         assertFalse(source.needClone());
 430         assertTrue(result.needClone());
 431
 432         // Forced copy, no cloning needed, but maps are equal
 433         final var immutable = (ImmutableOffsetMap<String, String>) source
 434                 .toUnmodifiableMap();
 435         assertFalse(source.needClone());
 436         assertEquals(source, immutable);
 437         assertEquals(immutable, source);
 438         assertTrue(Iterables.elementsEqual(source.entrySet(), immutable.entrySet()));
 439     }
 440
 441     @Test
 442     void testCloneableFlippingUnordered() throws CloneNotSupportedException {
 443         final var source = unorderedMap().toModifiableMap();
 444
 445         // Must clone before mutation
 446         assertTrue(source.needClone());
 447
 448         // Non-existent entry, should not clone
 449         source.remove("non-existent");
 450         assertTrue(source.needClone());
 451
 452         // Changes the array, should clone
 453         source.remove("k1");
 454         assertFalse(source.needClone());
 455
 456         // Create a clone of the map, which shares the array
 457         final var result = source.clone();
 458         assertFalse(source.needClone());
 459         assertTrue(result.needClone());
 460         assertSame(source.array(), result.array());
 461
 462         // Changes the array, should clone
 463         source.put("k1", "v2");
 464         assertFalse(source.needClone());
 465         assertTrue(result.needClone());
 466
 467         // Creates a immutable view, which shares the array
 468         final var immutable = (ImmutableOffsetMap<String, String>) source.toUnmodifiableMap();
 469         assertTrue(source.needClone());
 470         assertSame(source.array(), immutable.objects());
 471     }
 472
 473     @Test
 474     void testMutableEntrySet() {
 475         final var map = createMap().toModifiableMap();
 476
 477         assertTrue(map.entrySet().add(new SimpleEntry<>("k3", "v3")));
 478         assertTrue(map.containsKey("k3"));
 479         assertEquals("v3", map.get("k3"));
 480
 481         // null is not an Entry: ignore
 482         assertFalse(map.entrySet().remove(null));
 483
 484         // non-matching value: ignore
 485         assertFalse(map.entrySet().remove(new SimpleEntry<>("k1", "other")));
 486         assertTrue(map.containsKey("k1"));
 487
 488         // ignore null values
 489         assertFalse(map.entrySet().remove(new SimpleEntry<>("k1", null)));
 490         assertTrue(map.containsKey("k1"));
 491
 492         assertTrue(map.entrySet().remove(new SimpleEntry<>("k1", "v1")));
 493         assertFalse(map.containsKey("k1"));
 494     }
 495
 496     private static void assertIteratorBroken(final Iterator<?> it) {
 497         assertThrows(ConcurrentModificationException.class, () -> it.hasNext());
 498         assertThrows(ConcurrentModificationException.class, () -> it.next());
 499         assertThrows(ConcurrentModificationException.class, () -> it.remove());
 500     }
 501
 502     @Test
 503     void testMutableSimpleEquals() {
 504         final var source = createMap();
 505         final var map = source.toModifiableMap();
 506
 507         assertEquals(map, map);
 508         assertNotEquals(null, map);
 509         assertNotEquals("string", map);
 510         assertEquals(map, source);
 511     }
 512
 513     @Test
 514     void testMutableSimpleHashCode() {
 515         final var map = createMap().toModifiableMap();
 516
 517         assertEquals(twoEntryMap.hashCode(), map.hashCode());
 518     }
 519
 520     @Test
 521     void testMutableIteratorBasics() {
 522         final var map = createMap().toModifiableMap();
 523         final var it = map.entrySet().iterator();
 524
 525         // Not advanced, remove should fail
 526         assertThrows(IllegalStateException.class, () -> it.remove());
 527
 528         assertTrue(it.hasNext());
 529         assertEquals("k1", it.next().getKey());
 530         assertTrue(it.hasNext());
 531         assertEquals("k2", it.next().getKey());
 532         assertFalse(it.hasNext());
 533
 534         // Check end-of-iteration throw
 535         assertThrows(NoSuchElementException.class, () -> it.next());
 536     }
 537
 538     @Test
 539     void testMutableIteratorWithRemove() {
 540         final var map = createMap().toModifiableMap();
 541         final var it = map.entrySet().iterator();
 542
 543         // Advance one element
 544         assertTrue(it.hasNext());
 545         assertEquals("k1", it.next().getKey());
 546
 547         // Remove k1
 548         it.remove();
 549         assertEquals(1, map.size());
 550         assertFalse(map.containsKey("k1"));
 551
 552         // Iterator should still work
 553         assertTrue(it.hasNext());
 554         assertEquals("k2", it.next().getKey());
 555         assertFalse(it.hasNext());
 556     }
 557
 558     @Test
 559     void testMutableIteratorOffsetReplaceWorks() {
 560         final var map = createMap().toModifiableMap();
 561         final var it = map.entrySet().iterator();
 562         it.next();
 563
 564         map.put("k1", "new-v1");
 565         assertTrue(it.hasNext());
 566     }
 567
 568     @Test
 569     void testMutableIteratorNewReplaceWorks() {
 570         final var map = createMap().toModifiableMap();
 571         map.put("k3", "v3");
 572         final var it = map.entrySet().iterator();
 573         it.next();
 574
 575         map.put("k3", "new-v3");
 576         assertTrue(it.hasNext());
 577     }
 578
 579     @Test
 580     void testMutableIteratorOffsetAddBreaks() {
 581         final var map = createMap().toModifiableMap();
 582         map.put("k3", "v3");
 583         map.remove("k1");
 584
 585         final var it = map.entrySet().iterator();
 586         it.next();
 587
 588         map.put("k1", "new-v1");
 589         assertIteratorBroken(it);
 590     }
 591
 592     @Test
 593     void testMutableIteratorNewAddBreaks() {
 594         final var map = createMap().toModifiableMap();
 595         final var it = map.entrySet().iterator();
 596         it.next();
 597
 598         map.put("k3", "v3");
 599         assertIteratorBroken(it);
 600     }
 601
 602     @Test
 603     void testMutableIteratorOffsetRemoveBreaks() {
 604         final var map = createMap().toModifiableMap();
 605         final var it = map.entrySet().iterator();
 606         it.next();
 607
 608         map.remove("k1");
 609         assertIteratorBroken(it);
 610     }
 611
 612     @Test
 613     void testMutableIteratorNewRemoveBreaks() {
 614         final var map = createMap().toModifiableMap();
 615         map.put("k3", "v3");
 616         final var it = map.entrySet().iterator();
 617         it.next();
 618
 619         map.remove("k3");
 620         assertIteratorBroken(it);
 621     }
 622
 623     @Test
 624     void testMutableCrossIteratorRemove() {
 625         final var map = createMap().toModifiableMap();
 626         final var es = map.entrySet();
 627         final var it1 = es.iterator();
 628         final var it2 = es.iterator();
 629
 630         // Remove k1 via it1
 631         it1.next();
 632         it2.next();
 633         it1.remove();
 634         assertEquals(1, map.size());
 635
 636         // Check it2 was broken
 637         assertIteratorBroken(it2);
 638     }
 639
 640     @Test
 641     void testImmutableSerialization() throws IOException, ClassNotFoundException {
 642         final var source = createMap();
 643
 644         final var bos = new ByteArrayOutputStream();
 645         try (ObjectOutputStream oos = new ObjectOutputStream(bos)) {
 646             oos.writeObject(source);
 647         }
 648
 649         final var ois = new ObjectInputStream(new ByteArrayInputStream(bos.toByteArray()));
 650         @SuppressWarnings("unchecked")
 651         final var result = (Map<String, String>) ois.readObject();
 652
 653         assertEquals(source, result);
 654     }
 655 }