guava

1
/*
2
 * Copyright (C) 2008 The Guava Authors
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.google.common.collect.testing;
18

19
import static java.util.Collections.singleton;
20

21
import com.google.common.annotations.GwtCompatible;
22
import com.google.common.annotations.J2ktIncompatible;
23
import java.util.Arrays;
24
import java.util.Collection;
25
import java.util.Collections;
26
import java.util.HashSet;
27
import java.util.Iterator;
28
import java.util.Map;
29
import java.util.Map.Entry;
30
import java.util.Set;
31
import junit.framework.TestCase;
32
import org.checkerframework.checker.nullness.qual.Nullable;
33

34
/**
35
 * Tests representing the contract of {@link Map}. Concrete subclasses of this base class test
36
 * conformance of concrete {@link Map} subclasses to that contract.
37
 *
38
 * @param <K> the type of keys used by the maps under test
39
 * @param <V> the type of mapped values used the maps under test
40
 * @author George van den Driessche
41
 */
42
// TODO: Descriptive assertion messages, with hints as to probable fixes.
43
// TODO: Add another constructor parameter indicating whether the class under test is ordered, and
44
// check the order if so.
45
// TODO: Refactor to share code with SetTestBuilder etc.
46
@GwtCompatible
47
@ElementTypesAreNonnullByDefault
48
public abstract class MapInterfaceTest<K extends @Nullable Object, V extends @Nullable Object>
49
    extends TestCase {
50

51
  /** A key type that is not assignable to any classes but Object. */
52
  private static final class IncompatibleKeyType {
53
    @Override
54
    public String toString() {
55
      return "IncompatibleKeyType";
56
    }
57
  }
58

59
  protected final boolean supportsPut;
60
  protected final boolean supportsRemove;
61
  protected final boolean supportsClear;
62
  protected final boolean allowsNullKeys;
63
  protected final boolean allowsNullValues;
64
  protected final boolean supportsIteratorRemove;
65

66
  /**
67
   * Creates a new, empty instance of the class under test.
68
   *
69
   * @return a new, empty map instance.
70
   * @throws UnsupportedOperationException if it's not possible to make an empty instance of the
71
   *     class under test.
72
   */
73
  protected abstract Map<K, V> makeEmptyMap() throws UnsupportedOperationException;
74

75
  /**
76
   * Creates a new, non-empty instance of the class under test.
77
   *
78
   * @return a new, non-empty map instance.
79
   * @throws UnsupportedOperationException if it's not possible to make a non-empty instance of the
80
   *     class under test.
81
   */
82
  protected abstract Map<K, V> makePopulatedMap() throws UnsupportedOperationException;
83

84
  /**
85
   * Creates a new key that is not expected to be found in {@link #makePopulatedMap()}.
86
   *
87
   * @return a key.
88
   * @throws UnsupportedOperationException if it's not possible to make a key that will not be found
89
   *     in the map.
90
   */
91
  protected abstract K getKeyNotInPopulatedMap() throws UnsupportedOperationException;
92

93
  /**
94
   * Creates a new value that is not expected to be found in {@link #makePopulatedMap()}.
95
   *
96
   * @return a value.
97
   * @throws UnsupportedOperationException if it's not possible to make a value that will not be
98
   *     found in the map.
99
   */
100
  protected abstract V getValueNotInPopulatedMap() throws UnsupportedOperationException;
101

102
  /**
103
   * Constructor that assigns {@code supportsIteratorRemove} the same value as {@code
104
   * supportsRemove}.
105
   */
106
  protected MapInterfaceTest(
107
      boolean allowsNullKeys,
108
      boolean allowsNullValues,
109
      boolean supportsPut,
110
      boolean supportsRemove,
111
      boolean supportsClear) {
112
    this(
113
        allowsNullKeys,
114
        allowsNullValues,
115
        supportsPut,
116
        supportsRemove,
117
        supportsClear,
118
        supportsRemove);
119
  }
120

121
  /** Constructor with an explicit {@code supportsIteratorRemove} parameter. */
122
  protected MapInterfaceTest(
123
      boolean allowsNullKeys,
124
      boolean allowsNullValues,
125
      boolean supportsPut,
126
      boolean supportsRemove,
127
      boolean supportsClear,
128
      boolean supportsIteratorRemove) {
129
    this.supportsPut = supportsPut;
130
    this.supportsRemove = supportsRemove;
131
    this.supportsClear = supportsClear;
132
    this.allowsNullKeys = allowsNullKeys;
133
    this.allowsNullValues = allowsNullValues;
134
    this.supportsIteratorRemove = supportsIteratorRemove;
135
  }
136

137
  /**
138
   * Used by tests that require a map, but don't care whether it's populated or not.
139
   *
140
   * @return a new map instance.
141
   */
142
  protected Map<K, V> makeEitherMap() {
143
    try {
144
      return makePopulatedMap();
145
    } catch (UnsupportedOperationException e) {
146
      return makeEmptyMap();
147
    }
148
  }
149

150
  protected final boolean supportsValuesHashCode(Map<K, V> map) {
151
    // get the first non-null value
152
    Collection<V> values = map.values();
153
    for (V value : values) {
154
      if (value != null) {
155
        try {
156
          int unused = value.hashCode();
157
        } catch (Exception e) {
158
          return false;
159
        }
160
        return true;
161
      }
162
    }
163
    return true;
164
  }
165

166
  /**
167
   * Checks all the properties that should always hold of a map. Also calls {@link
168
   * #assertMoreInvariants} to check invariants that are peculiar to specific implementations.
169
   *
170
   * @see #assertMoreInvariants
171
   * @param map the map to check.
172
   */
173
  protected final void assertInvariants(Map<K, V> map) {
174
    Set<K> keySet = map.keySet();
175
    Collection<V> valueCollection = map.values();
176
    Set<Entry<K, V>> entrySet = map.entrySet();
177

178
    assertEquals(map.size() == 0, map.isEmpty());
179
    assertEquals(map.size(), keySet.size());
180
    assertEquals(keySet.size() == 0, keySet.isEmpty());
181
    assertEquals(!keySet.isEmpty(), keySet.iterator().hasNext());
182

183
    int expectedKeySetHash = 0;
184
    for (K key : keySet) {
185
      V value = map.get(key);
186
      expectedKeySetHash += key != null ? key.hashCode() : 0;
187
      assertTrue(map.containsKey(key));
188
      assertTrue(map.containsValue(value));
189
      assertTrue(valueCollection.contains(value));
190
      assertTrue(valueCollection.containsAll(Collections.singleton(value)));
191
      assertTrue(entrySet.contains(mapEntry(key, value)));
192
      assertTrue(allowsNullKeys || (key != null));
193
    }
194
    assertEquals(expectedKeySetHash, keySet.hashCode());
195

196
    assertEquals(map.size(), valueCollection.size());
197
    assertEquals(valueCollection.size() == 0, valueCollection.isEmpty());
198
    assertEquals(!valueCollection.isEmpty(), valueCollection.iterator().hasNext());
199
    for (V value : valueCollection) {
200
      assertTrue(map.containsValue(value));
201
      assertTrue(allowsNullValues || (value != null));
202
    }
203

204
    assertEquals(map.size(), entrySet.size());
205
    assertEquals(entrySet.size() == 0, entrySet.isEmpty());
206
    assertEquals(!entrySet.isEmpty(), entrySet.iterator().hasNext());
207
    assertEntrySetNotContainsString(entrySet);
208

209
    boolean supportsValuesHashCode = supportsValuesHashCode(map);
210
    if (supportsValuesHashCode) {
211
      int expectedEntrySetHash = 0;
212
      for (Entry<K, V> entry : entrySet) {
213
        assertTrue(map.containsKey(entry.getKey()));
214
        assertTrue(map.containsValue(entry.getValue()));
215
        int expectedHash =
216
            (entry.getKey() == null ? 0 : entry.getKey().hashCode())
217
                ^ (entry.getValue() == null ? 0 : entry.getValue().hashCode());
218
        assertEquals(expectedHash, entry.hashCode());
219
        expectedEntrySetHash += expectedHash;
220
      }
221
      assertEquals(expectedEntrySetHash, entrySet.hashCode());
222
      assertTrue(entrySet.containsAll(new HashSet<Entry<K, V>>(entrySet)));
223
      assertTrue(entrySet.equals(new HashSet<Entry<K, V>>(entrySet)));
224
    }
225

226
    Object[] entrySetToArray1 = entrySet.toArray();
227
    assertEquals(map.size(), entrySetToArray1.length);
228
    assertTrue(Arrays.asList(entrySetToArray1).containsAll(entrySet));
229

230
    Entry<?, ?>[] entrySetToArray2 = new Entry<?, ?>[map.size() + 2];
231
    entrySetToArray2[map.size()] = mapEntry("foo", 1);
232
    assertSame(entrySetToArray2, entrySet.toArray(entrySetToArray2));
233
    assertNull(entrySetToArray2[map.size()]);
234
    assertTrue(Arrays.asList(entrySetToArray2).containsAll(entrySet));
235

236
    Object[] valuesToArray1 = valueCollection.toArray();
237
    assertEquals(map.size(), valuesToArray1.length);
238
    assertTrue(Arrays.asList(valuesToArray1).containsAll(valueCollection));
239

240
    Object[] valuesToArray2 = new Object[map.size() + 2];
241
    valuesToArray2[map.size()] = "foo";
242
    assertSame(valuesToArray2, valueCollection.toArray(valuesToArray2));
243
    assertNull(valuesToArray2[map.size()]);
244
    assertTrue(Arrays.asList(valuesToArray2).containsAll(valueCollection));
245

246
    if (supportsValuesHashCode) {
247
      int expectedHash = 0;
248
      for (Entry<K, V> entry : entrySet) {
249
        expectedHash += entry.hashCode();
250
      }
251
      assertEquals(expectedHash, map.hashCode());
252
    }
253

254
    assertMoreInvariants(map);
255
  }
256

257
  @SuppressWarnings("CollectionIncompatibleType")
258
  private void assertEntrySetNotContainsString(Set<Entry<K, V>> entrySet) {
259
    // Very unlikely that a buggy collection would ever return true. It might accidentally throw.
260
    assertFalse(entrySet.contains("foo"));
261
  }
262

263
  /**
264
   * Override this to check invariants which should hold true for a particular implementation, but
265
   * which are not generally applicable to every instance of Map.
266
   *
267
   * @param map the map whose additional invariants to check.
268
   */
269
  protected void assertMoreInvariants(Map<K, V> map) {}
270

271
  public void testClear() {
272
    Map<K, V> map;
273
    try {
274
      map = makePopulatedMap();
275
    } catch (UnsupportedOperationException e) {
276
      return;
277
    }
278

279
    if (supportsClear) {
280
      map.clear();
281
      assertTrue(map.isEmpty());
282
    } else {
283
      try {
284
        map.clear();
285
        fail("Expected UnsupportedOperationException.");
286
      } catch (UnsupportedOperationException expected) {
287
      }
288
    }
289
    assertInvariants(map);
290
  }
291

292
  @J2ktIncompatible // https://youtrack.jetbrains.com/issue/KT-58242/ undefined behavior (crash)
293
  public void testContainsKey() {
294
    Map<K, V> map;
295
    K unmappedKey;
296
    try {
297
      map = makePopulatedMap();
298
      unmappedKey = getKeyNotInPopulatedMap();
299
    } catch (UnsupportedOperationException e) {
300
      return;
301
    }
302
    assertFalse(map.containsKey(unmappedKey));
303
    try {
304
      assertFalse(map.containsKey(new IncompatibleKeyType()));
305
    } catch (ClassCastException tolerated) {
306
    }
307
    assertTrue(map.containsKey(map.keySet().iterator().next()));
308
    if (allowsNullKeys) {
309
      boolean unused = map.containsKey(null);
310
    } else {
311
      try {
312
        boolean unused2 = map.containsKey(null);
313
      } catch (NullPointerException optional) {
314
      }
315
    }
316
    assertInvariants(map);
317
  }
318

319
  public void testContainsValue() {
320
    Map<K, V> map;
321
    V unmappedValue;
322
    try {
323
      map = makePopulatedMap();
324
      unmappedValue = getValueNotInPopulatedMap();
325
    } catch (UnsupportedOperationException e) {
326
      return;
327
    }
328
    assertFalse(map.containsValue(unmappedValue));
329
    assertTrue(map.containsValue(map.values().iterator().next()));
330
    if (allowsNullValues) {
331
      boolean unused = map.containsValue(null);
332
    } else {
333
      try {
334
        boolean unused2 = map.containsKey(null);
335
      } catch (NullPointerException optional) {
336
      }
337
    }
338
    assertInvariants(map);
339
  }
340

341
  public void testEntrySet() {
342
    Map<K, V> map;
343
    Set<Entry<K, V>> entrySet;
344
    try {
345
      map = makePopulatedMap();
346
    } catch (UnsupportedOperationException e) {
347
      return;
348
    }
349
    assertInvariants(map);
350

351
    entrySet = map.entrySet();
352
    K unmappedKey;
353
    V unmappedValue;
354
    try {
355
      unmappedKey = getKeyNotInPopulatedMap();
356
      unmappedValue = getValueNotInPopulatedMap();
357
    } catch (UnsupportedOperationException e) {
358
      return;
359
    }
360
    for (Entry<K, V> entry : entrySet) {
361
      assertFalse(unmappedKey.equals(entry.getKey()));
362
      assertFalse(unmappedValue.equals(entry.getValue()));
363
    }
364
  }
365

366
  public void testEntrySetForEmptyMap() {
367
    Map<K, V> map;
368
    try {
369
      map = makeEmptyMap();
370
    } catch (UnsupportedOperationException e) {
371
      return;
372
    }
373
    assertInvariants(map);
374
  }
375

376
  @J2ktIncompatible // https://youtrack.jetbrains.com/issue/KT-58242/ undefined behavior (crash)
377
  public void testEntrySetContainsEntryIncompatibleKey() {
378
    Map<K, V> map;
379
    Set<Entry<K, V>> entrySet;
380
    try {
381
      map = makeEitherMap();
382
    } catch (UnsupportedOperationException e) {
383
      return;
384
    }
385
    assertInvariants(map);
386

387
    entrySet = map.entrySet();
388
    V unmappedValue;
389
    try {
390
      unmappedValue = getValueNotInPopulatedMap();
391
    } catch (UnsupportedOperationException e) {
392
      return;
393
    }
394
    Entry<IncompatibleKeyType, V> entry = mapEntry(new IncompatibleKeyType(), unmappedValue);
395
    try {
396
      assertFalse(entrySet.contains(entry));
397
    } catch (ClassCastException tolerated) {
398
    }
399
  }
400

401
  public void testEntrySetContainsEntryNullKeyPresent() {
402
    if (!allowsNullKeys || !supportsPut) {
403
      return;
404
    }
405
    Map<K, V> map;
406
    Set<Entry<K, V>> entrySet;
407
    try {
408
      map = makeEitherMap();
409
    } catch (UnsupportedOperationException e) {
410
      return;
411
    }
412
    assertInvariants(map);
413

414
    entrySet = map.entrySet();
415
    V unmappedValue;
416
    try {
417
      unmappedValue = getValueNotInPopulatedMap();
418
    } catch (UnsupportedOperationException e) {
419
      return;
420
    }
421

422
    map.put(null, unmappedValue);
423
    Entry<@Nullable K, V> entry = mapEntry(null, unmappedValue);
424
    assertTrue(entrySet.contains(entry));
425
    Entry<@Nullable K, @Nullable V> nonEntry = mapEntry(null, null);
426
    assertFalse(entrySet.contains(nonEntry));
427
  }
428

429
  public void testEntrySetContainsEntryNullKeyMissing() {
430
    Map<K, V> map;
431
    Set<Entry<K, V>> entrySet;
432
    try {
433
      map = makeEitherMap();
434
    } catch (UnsupportedOperationException e) {
435
      return;
436
    }
437
    assertInvariants(map);
438

439
    entrySet = map.entrySet();
440
    V unmappedValue;
441
    try {
442
      unmappedValue = getValueNotInPopulatedMap();
443
    } catch (UnsupportedOperationException e) {
444
      return;
445
    }
446
    Entry<@Nullable K, V> nullKeyEntry = mapEntry(null, unmappedValue);
447
    try {
448
      assertFalse(entrySet.contains(nullKeyEntry));
449
    } catch (NullPointerException e) {
450
      assertFalse(allowsNullKeys);
451
    }
452
    Entry<@Nullable K, @Nullable V> nullKeyValueEntry = mapEntry(null, null);
453
    try {
454
      assertFalse(entrySet.contains(nullKeyValueEntry));
455
    } catch (NullPointerException e) {
456
      assertFalse(allowsNullKeys && allowsNullValues);
457
    }
458
  }
459

460
  public void testEntrySetIteratorRemove() {
461
    Map<K, V> map;
462
    try {
463
      map = makePopulatedMap();
464
    } catch (UnsupportedOperationException e) {
465
      return;
466
    }
467

468
    Set<Entry<K, V>> entrySet = map.entrySet();
469
    Iterator<Entry<K, V>> iterator = entrySet.iterator();
470
    if (supportsIteratorRemove) {
471
      int initialSize = map.size();
472
      Entry<K, V> entry = iterator.next();
473
      Entry<K, V> entryCopy = Helpers.mapEntry(entry.getKey(), entry.getValue());
474

475
      iterator.remove();
476
      assertEquals(initialSize - 1, map.size());
477

478
      // Use "entryCopy" instead of "entry" because "entry" might be invalidated after
479
      // iterator.remove().
480
      assertFalse(entrySet.contains(entryCopy));
481
      assertInvariants(map);
482
      try {
483
        iterator.remove();
484
        fail("Expected IllegalStateException.");
485
      } catch (IllegalStateException expected) {
486
      }
487
    } else {
488
      iterator.next();
489
      try {
490
        iterator.remove();
491
        fail("Expected UnsupportedOperationException.");
492
      } catch (UnsupportedOperationException expected) {
493
      }
494
    }
495
    assertInvariants(map);
496
  }
497

498
  public void testEntrySetRemove() {
499
    Map<K, V> map;
500
    try {
501
      map = makePopulatedMap();
502
    } catch (UnsupportedOperationException e) {
503
      return;
504
    }
505

506
    Set<Entry<K, V>> entrySet = map.entrySet();
507
    if (supportsRemove) {
508
      int initialSize = map.size();
509
      boolean didRemove = entrySet.remove(entrySet.iterator().next());
510
      assertTrue(didRemove);
511
      assertEquals(initialSize - 1, map.size());
512
    } else {
513
      try {
514
        entrySet.remove(entrySet.iterator().next());
515
        fail("Expected UnsupportedOperationException.");
516
      } catch (UnsupportedOperationException expected) {
517
      }
518
    }
519
    assertInvariants(map);
520
  }
521

522
  public void testEntrySetRemoveMissingKey() {
523
    Map<K, V> map;
524
    K key;
525
    try {
526
      map = makeEitherMap();
527
      key = getKeyNotInPopulatedMap();
528
    } catch (UnsupportedOperationException e) {
529
      return;
530
    }
531

532
    Set<Entry<K, V>> entrySet = map.entrySet();
533
    Entry<K, V> entry = mapEntry(key, getValueNotInPopulatedMap());
534
    int initialSize = map.size();
535
    if (supportsRemove) {
536
      boolean didRemove = entrySet.remove(entry);
537
      assertFalse(didRemove);
538
    } else {
539
      try {
540
        boolean didRemove = entrySet.remove(entry);
541
        assertFalse(didRemove);
542
      } catch (UnsupportedOperationException optional) {
543
      }
544
    }
545
    assertEquals(initialSize, map.size());
546
    assertFalse(map.containsKey(key));
547
    assertInvariants(map);
548
  }
549

550
  public void testEntrySetRemoveDifferentValue() {
551
    Map<K, V> map;
552
    try {
553
      map = makePopulatedMap();
554
    } catch (UnsupportedOperationException e) {
555
      return;
556
    }
557

558
    Set<Entry<K, V>> entrySet = map.entrySet();
559
    K key = map.keySet().iterator().next();
560
    Entry<K, V> entry = mapEntry(key, getValueNotInPopulatedMap());
561
    int initialSize = map.size();
562
    if (supportsRemove) {
563
      boolean didRemove = entrySet.remove(entry);
564
      assertFalse(didRemove);
565
    } else {
566
      try {
567
        boolean didRemove = entrySet.remove(entry);
568
        assertFalse(didRemove);
569
      } catch (UnsupportedOperationException optional) {
570
      }
571
    }
572
    assertEquals(initialSize, map.size());
573
    assertTrue(map.containsKey(key));
574
    assertInvariants(map);
575
  }
576

577
  public void testEntrySetRemoveNullKeyPresent() {
578
    if (!allowsNullKeys || !supportsPut || !supportsRemove) {
579
      return;
580
    }
581
    Map<K, V> map;
582
    Set<Entry<K, V>> entrySet;
583
    try {
584
      map = makeEitherMap();
585
    } catch (UnsupportedOperationException e) {
586
      return;
587
    }
588
    assertInvariants(map);
589

590
    entrySet = map.entrySet();
591
    V unmappedValue;
592
    try {
593
      unmappedValue = getValueNotInPopulatedMap();
594
    } catch (UnsupportedOperationException e) {
595
      return;
596
    }
597

598
    map.put(null, unmappedValue);
599
    assertEquals(unmappedValue, map.get(null));
600
    assertTrue(map.containsKey(null));
601
    Entry<@Nullable K, V> entry = mapEntry(null, unmappedValue);
602
    assertTrue(entrySet.remove(entry));
603
    assertNull(map.get(null));
604
    assertFalse(map.containsKey(null));
605
  }
606

607
  public void testEntrySetRemoveNullKeyMissing() {
608
    Map<K, V> map;
609
    try {
610
      map = makeEitherMap();
611
    } catch (UnsupportedOperationException e) {
612
      return;
613
    }
614

615
    Set<Entry<K, V>> entrySet = map.entrySet();
616
    Entry<@Nullable K, V> entry = mapEntry(null, getValueNotInPopulatedMap());
617
    int initialSize = map.size();
618
    if (supportsRemove) {
619
      try {
620
        boolean didRemove = entrySet.remove(entry);
621
        assertFalse(didRemove);
622
      } catch (NullPointerException e) {
623
        assertFalse(allowsNullKeys);
624
      }
625
    } else {
626
      try {
627
        boolean didRemove = entrySet.remove(entry);
628
        assertFalse(didRemove);
629
      } catch (UnsupportedOperationException optional) {
630
      }
631
    }
632
    assertEquals(initialSize, map.size());
633
    assertInvariants(map);
634
  }
635

636
  public void testEntrySetRemoveAll() {
637
    Map<K, V> map;
638
    try {
639
      map = makePopulatedMap();
640
    } catch (UnsupportedOperationException e) {
641
      return;
642
    }
643

644
    Set<Entry<K, V>> entrySet = map.entrySet();
645

646
    Entry<K, V> entryToRemove = entrySet.iterator().next();
647
    Set<Entry<K, V>> entriesToRemove = singleton(entryToRemove);
648
    if (supportsRemove) {
649
      // We use a copy of "entryToRemove" in the assertion because "entryToRemove" might be
650
      // invalidated and have undefined behavior after entrySet.removeAll(entriesToRemove),
651
      // for example entryToRemove.getValue() might be null.
652
      Entry<K, V> entryToRemoveCopy =
653
          Helpers.mapEntry(entryToRemove.getKey(), entryToRemove.getValue());
654

655
      int initialSize = map.size();
656
      boolean didRemove = entrySet.removeAll(entriesToRemove);
657
      assertTrue(didRemove);
658
      assertEquals(initialSize - entriesToRemove.size(), map.size());
659

660
      // Use "entryToRemoveCopy" instead of "entryToRemove" because it might be invalidated and
661
      // have undefined behavior after entrySet.removeAll(entriesToRemove),
662
      assertFalse(entrySet.contains(entryToRemoveCopy));
663
    } else {
664
      try {
665
        entrySet.removeAll(entriesToRemove);
666
        fail("Expected UnsupportedOperationException.");
667
      } catch (UnsupportedOperationException expected) {
668
      }
669
    }
670
    assertInvariants(map);
671
  }
672

673
  public void testEntrySetRemoveAllNullFromEmpty() {
674
    Map<K, V> map;
675
    try {
676
      map = makeEmptyMap();
677
    } catch (UnsupportedOperationException e) {
678
      return;
679
    }
680

681
    Set<Entry<K, V>> entrySet = map.entrySet();
682
    if (supportsRemove) {
683
      try {
684
        entrySet.removeAll(null);
685
        fail("Expected NullPointerException.");
686
      } catch (NullPointerException expected) {
687
      }
688
    } else {
689
      try {
690
        entrySet.removeAll(null);
691
        fail("Expected UnsupportedOperationException or NullPointerException.");
692
      } catch (UnsupportedOperationException | NullPointerException e) {
693
        // Expected.
694
      }
695
    }
696
    assertInvariants(map);
697
  }
698

699
  public void testEntrySetRetainAll() {
700
    Map<K, V> map;
701
    try {
702
      map = makePopulatedMap();
703
    } catch (UnsupportedOperationException e) {
704
      return;
705
    }
706

707
    Set<Entry<K, V>> entrySet = map.entrySet();
708
    Set<Entry<K, V>> entriesToRetain = singleton(entrySet.iterator().next());
709
    if (supportsRemove) {
710
      boolean shouldRemove = (entrySet.size() > entriesToRetain.size());
711
      boolean didRemove = entrySet.retainAll(entriesToRetain);
712
      assertEquals(shouldRemove, didRemove);
713
      assertEquals(entriesToRetain.size(), map.size());
714
      for (Entry<K, V> entry : entriesToRetain) {
715
        assertTrue(entrySet.contains(entry));
716
      }
717
    } else {
718
      try {
719
        entrySet.retainAll(entriesToRetain);
720
        fail("Expected UnsupportedOperationException.");
721
      } catch (UnsupportedOperationException expected) {
722
      }
723
    }
724
    assertInvariants(map);
725
  }
726

727
  public void testEntrySetRetainAllNullFromEmpty() {
728
    Map<K, V> map;
729
    try {
730
      map = makeEmptyMap();
731
    } catch (UnsupportedOperationException e) {
732
      return;
733
    }
734

735
    Set<Entry<K, V>> entrySet = map.entrySet();
736
    if (supportsRemove) {
737
      try {
738
        entrySet.retainAll(null);
739
        // Returning successfully is not ideal, but tolerated.
740
      } catch (NullPointerException tolerated) {
741
      }
742
    } else {
743
      try {
744
        entrySet.retainAll(null);
745
        // We have to tolerate a successful return (Sun bug 4802647)
746
      } catch (UnsupportedOperationException | NullPointerException e) {
747
        // Expected.
748
      }
749
    }
750
    assertInvariants(map);
751
  }
752

753
  public void testEntrySetClear() {
754
    Map<K, V> map;
755
    try {
756
      map = makePopulatedMap();
757
    } catch (UnsupportedOperationException e) {
758
      return;
759
    }
760

761
    Set<Entry<K, V>> entrySet = map.entrySet();
762
    if (supportsClear) {
763
      entrySet.clear();
764
      assertTrue(entrySet.isEmpty());
765
    } else {
766
      try {
767
        entrySet.clear();
768
        fail("Expected UnsupportedOperationException.");
769
      } catch (UnsupportedOperationException expected) {
770
      }
771
    }
772
    assertInvariants(map);
773
  }
774

775
  public void testEntrySetAddAndAddAll() {
776
    Map<K, V> map = makeEitherMap();
777

778
    Set<Entry<K, V>> entrySet = map.entrySet();
779
    Entry<@Nullable K, @Nullable V> entryToAdd = mapEntry(null, null);
780
    try {
781
      entrySet.add((Entry<K, V>) entryToAdd);
782
      fail("Expected UnsupportedOperationException or NullPointerException.");
783
    } catch (UnsupportedOperationException | NullPointerException e) {
784
      // Expected.
785
    }
786
    assertInvariants(map);
787

788
    try {
789
      entrySet.addAll(singleton((Entry<K, V>) entryToAdd));
790
      fail("Expected UnsupportedOperationException or NullPointerException.");
791
    } catch (UnsupportedOperationException | NullPointerException e) {
792
      // Expected.
793
    }
794
    assertInvariants(map);
795
  }
796

797
  public void testEntrySetSetValue() {
798
    // TODO: Investigate the extent to which, in practice, maps that support
799
    // put() also support Entry.setValue().
800
    if (!supportsPut) {
801
      return;
802
    }
803

804
    Map<K, V> map;
805
    V valueToSet;
806
    try {
807
      map = makePopulatedMap();
808
      valueToSet = getValueNotInPopulatedMap();
809
    } catch (UnsupportedOperationException e) {
810
      return;
811
    }
812

813
    Set<Entry<K, V>> entrySet = map.entrySet();
814
    Entry<K, V> entry = entrySet.iterator().next();
815
    V oldValue = entry.getValue();
816
    V returnedValue = entry.setValue(valueToSet);
817
    assertEquals(oldValue, returnedValue);
818
    assertTrue(entrySet.contains(mapEntry(entry.getKey(), valueToSet)));
819
    assertEquals(valueToSet, map.get(entry.getKey()));
820
    assertInvariants(map);
821
  }
822

823
  public void testEntrySetSetValueSameValue() {
824
    // TODO: Investigate the extent to which, in practice, maps that support
825
    // put() also support Entry.setValue().
826
    if (!supportsPut) {
827
      return;
828
    }
829

830
    Map<K, V> map;
831
    try {
832
      map = makePopulatedMap();
833
    } catch (UnsupportedOperationException e) {
834
      return;
835
    }
836

837
    Set<Entry<K, V>> entrySet = map.entrySet();
838
    Entry<K, V> entry = entrySet.iterator().next();
839
    V oldValue = entry.getValue();
840
    V returnedValue = entry.setValue(oldValue);
841
    assertEquals(oldValue, returnedValue);
842
    assertTrue(entrySet.contains(mapEntry(entry.getKey(), oldValue)));
843
    assertEquals(oldValue, map.get(entry.getKey()));
844
    assertInvariants(map);
845
  }
846

847
  public void testEqualsForEqualMap() {
848
    Map<K, V> map;
849
    try {
850
      map = makePopulatedMap();
851
    } catch (UnsupportedOperationException e) {
852
      return;
853
    }
854

855
    // Explicitly call `equals`; `assertEquals` might return fast
856
    assertTrue(map.equals(map));
857
    assertTrue(makePopulatedMap().equals(map));
858
    assertFalse(map.equals(Collections.emptyMap()));
859
    // no-inspection ObjectEqualsNull
860
    assertFalse(map.equals(null));
861
  }
862

863
  public void testEqualsForLargerMap() {
864
    if (!supportsPut) {
865
      return;
866
    }
867

868
    Map<K, V> map;
869
    Map<K, V> largerMap;
870
    try {
871
      map = makePopulatedMap();
872
      largerMap = makePopulatedMap();
873
      largerMap.put(getKeyNotInPopulatedMap(), getValueNotInPopulatedMap());
874
    } catch (UnsupportedOperationException e) {
875
      return;
876
    }
877

878
    assertFalse(map.equals(largerMap));
879
  }
880

881
  public void testEqualsForSmallerMap() {
882
    if (!supportsRemove) {
883
      return;
884
    }
885

886
    Map<K, V> map;
887
    Map<K, V> smallerMap;
888
    try {
889
      map = makePopulatedMap();
890
      smallerMap = makePopulatedMap();
891
      smallerMap.remove(smallerMap.keySet().iterator().next());
892
    } catch (UnsupportedOperationException e) {
893
      return;
894
    }
895

896
    assertFalse(map.equals(smallerMap));
897
  }
898

899
  public void testEqualsForEmptyMap() {
900
    Map<K, V> map;
901
    try {
902
      map = makeEmptyMap();
903
    } catch (UnsupportedOperationException e) {
904
      return;
905
    }
906

907
    // Explicitly call `equals`; `assertEquals` might return fast
908
    assertTrue(map.equals(map));
909
    assertTrue(makeEmptyMap().equals(map));
910
    assertEquals(Collections.emptyMap(), map);
911
    assertFalse(map.equals(Collections.emptySet()));
912
    // noinspection ObjectEqualsNull
913
    assertFalse(map.equals(null));
914
  }
915

916
  public void testGet() {
917
    Map<K, V> map;
918
    try {
919
      map = makePopulatedMap();
920
    } catch (UnsupportedOperationException e) {
921
      return;
922
    }
923

924
    for (Entry<K, V> entry : map.entrySet()) {
925
      assertEquals(entry.getValue(), map.get(entry.getKey()));
926
    }
927

928
    K unmappedKey = null;
929
    try {
930
      unmappedKey = getKeyNotInPopulatedMap();
931
    } catch (UnsupportedOperationException e) {
932
      return;
933
    }
934
    assertNull(map.get(unmappedKey));
935
  }
936

937
  public void testGetForEmptyMap() {
938
    Map<K, V> map;
939
    K unmappedKey = null;
940
    try {
941
      map = makeEmptyMap();
942
      unmappedKey = getKeyNotInPopulatedMap();
943
    } catch (UnsupportedOperationException e) {
944
      return;
945
    }
946
    assertNull(map.get(unmappedKey));
947
  }
948

949
  public void testGetNull() {
950
    Map<K, V> map = makeEitherMap();
951
    if (allowsNullKeys) {
952
      if (allowsNullValues) {
953
        // TODO: decide what to test here.
954
      } else {
955
        assertEquals(map.containsKey(null), map.get(null) != null);
956
      }
957
    } else {
958
      try {
959
        map.get(null);
960
      } catch (NullPointerException optional) {
961
      }
962
    }
963
    assertInvariants(map);
964
  }
965

966
  public void testHashCode() {
967
    Map<K, V> map;
968
    try {
969
      map = makePopulatedMap();
970
    } catch (UnsupportedOperationException e) {
971
      return;
972
    }
973
    assertInvariants(map);
974
  }
975

976
  public void testHashCodeForEmptyMap() {
977
    Map<K, V> map;
978
    try {
979
      map = makeEmptyMap();
980
    } catch (UnsupportedOperationException e) {
981
      return;
982
    }
983
    assertInvariants(map);
984
  }
985

986
  public void testPutNewKey() {
987
    Map<K, V> map = makeEitherMap();
988
    K keyToPut;
989
    V valueToPut;
990
    try {
991
      keyToPut = getKeyNotInPopulatedMap();
992
      valueToPut = getValueNotInPopulatedMap();
993
    } catch (UnsupportedOperationException e) {
994
      return;
995
    }
996
    if (supportsPut) {
997
      int initialSize = map.size();
998
      V oldValue = map.put(keyToPut, valueToPut);
999
      assertEquals(valueToPut, map.get(keyToPut));
1000
      assertTrue(map.containsKey(keyToPut));
1001
      assertTrue(map.containsValue(valueToPut));
1002
      assertEquals(initialSize + 1, map.size());
1003
      assertNull(oldValue);
1004
    } else {
1005
      try {
1006
        map.put(keyToPut, valueToPut);
1007
        fail("Expected UnsupportedOperationException.");
1008
      } catch (UnsupportedOperationException expected) {
1009
      }
1010
    }
1011
    assertInvariants(map);
1012
  }
1013

1014
  public void testPutExistingKey() {
1015
    Map<K, V> map;
1016
    K keyToPut;
1017
    V valueToPut;
1018
    try {
1019
      map = makePopulatedMap();
1020
      valueToPut = getValueNotInPopulatedMap();
1021
    } catch (UnsupportedOperationException e) {
1022
      return;
1023
    }
1024
    keyToPut = map.keySet().iterator().next();
1025
    if (supportsPut) {
1026
      int initialSize = map.size();
1027
      map.put(keyToPut, valueToPut);
1028
      assertEquals(valueToPut, map.get(keyToPut));
1029
      assertTrue(map.containsKey(keyToPut));
1030
      assertTrue(map.containsValue(valueToPut));
1031
      assertEquals(initialSize, map.size());
1032
    } else {
1033
      try {
1034
        map.put(keyToPut, valueToPut);
1035
        fail("Expected UnsupportedOperationException.");
1036
      } catch (UnsupportedOperationException expected) {
1037
      }
1038
    }
1039
    assertInvariants(map);
1040
  }
1041

1042
  public void testPutNullKey() {
1043
    if (!supportsPut) {
1044
      return;
1045
    }
1046
    Map<K, V> map = makeEitherMap();
1047
    V valueToPut;
1048
    try {
1049
      valueToPut = getValueNotInPopulatedMap();
1050
    } catch (UnsupportedOperationException e) {
1051
      return;
1052
    }
1053
    if (allowsNullKeys) {
1054
      V oldValue = map.get(null);
1055
      V returnedValue = map.put(null, valueToPut);
1056
      assertEquals(oldValue, returnedValue);
1057
      assertEquals(valueToPut, map.get(null));
1058
      assertTrue(map.containsKey(null));
1059
      assertTrue(map.containsValue(valueToPut));
1060
    } else {
1061
      try {
1062
        map.put(null, valueToPut);
1063
        fail("Expected RuntimeException");
1064
      } catch (RuntimeException expected) {
1065
      }
1066
    }
1067
    assertInvariants(map);
1068
  }
1069

1070
  public void testPutNullValue() {
1071
    if (!supportsPut) {
1072
      return;
1073
    }
1074
    Map<K, V> map = makeEitherMap();
1075
    K keyToPut;
1076
    try {
1077
      keyToPut = getKeyNotInPopulatedMap();
1078
    } catch (UnsupportedOperationException e) {
1079
      return;
1080
    }
1081
    if (allowsNullValues) {
1082
      int initialSize = map.size();
1083
      V oldValue = map.get(keyToPut);
1084
      V returnedValue = map.put(keyToPut, null);
1085
      assertEquals(oldValue, returnedValue);
1086
      assertNull(map.get(keyToPut));
1087
      assertTrue(map.containsKey(keyToPut));
1088
      assertTrue(map.containsValue(null));
1089
      assertEquals(initialSize + 1, map.size());
1090
    } else {
1091
      try {
1092
        map.put(keyToPut, null);
1093
        fail("Expected RuntimeException");
1094
      } catch (RuntimeException expected) {
1095
      }
1096
    }
1097
    assertInvariants(map);
1098
  }
1099

1100
  public void testPutNullValueForExistingKey() {
1101
    if (!supportsPut) {
1102
      return;
1103
    }
1104
    Map<K, V> map;
1105
    K keyToPut;
1106
    try {
1107
      map = makePopulatedMap();
1108
      keyToPut = map.keySet().iterator().next();
1109
    } catch (UnsupportedOperationException e) {
1110
      return;
1111
    }
1112
    if (allowsNullValues) {
1113
      int initialSize = map.size();
1114
      V oldValue = map.get(keyToPut);
1115
      V returnedValue = map.put(keyToPut, null);
1116
      assertEquals(oldValue, returnedValue);
1117
      assertNull(map.get(keyToPut));
1118
      assertTrue(map.containsKey(keyToPut));
1119
      assertTrue(map.containsValue(null));
1120
      assertEquals(initialSize, map.size());
1121
    } else {
1122
      try {
1123
        map.put(keyToPut, null);
1124
        fail("Expected RuntimeException");
1125
      } catch (RuntimeException expected) {
1126
      }
1127
    }
1128
    assertInvariants(map);
1129
  }
1130

1131
  public void testPutAllNewKey() {
1132
    Map<K, V> map = makeEitherMap();
1133
    K keyToPut;
1134
    V valueToPut;
1135
    try {
1136
      keyToPut = getKeyNotInPopulatedMap();
1137
      valueToPut = getValueNotInPopulatedMap();
1138
    } catch (UnsupportedOperationException e) {
1139
      return;
1140
    }
1141
    Map<K, V> mapToPut = Collections.singletonMap(keyToPut, valueToPut);
1142
    if (supportsPut) {
1143
      int initialSize = map.size();
1144
      map.putAll(mapToPut);
1145
      assertEquals(valueToPut, map.get(keyToPut));
1146
      assertTrue(map.containsKey(keyToPut));
1147
      assertTrue(map.containsValue(valueToPut));
1148
      assertEquals(initialSize + 1, map.size());
1149
    } else {
1150
      try {
1151
        map.putAll(mapToPut);
1152
        fail("Expected UnsupportedOperationException.");
1153
      } catch (UnsupportedOperationException expected) {
1154
      }
1155
    }
1156
    assertInvariants(map);
1157
  }
1158

1159
  public void testPutAllExistingKey() {
1160
    Map<K, V> map;
1161
    K keyToPut;
1162
    V valueToPut;
1163
    try {
1164
      map = makePopulatedMap();
1165
      valueToPut = getValueNotInPopulatedMap();
1166
    } catch (UnsupportedOperationException e) {
1167
      return;
1168
    }
1169
    keyToPut = map.keySet().iterator().next();
1170
    Map<K, V> mapToPut = Collections.singletonMap(keyToPut, valueToPut);
1171
    int initialSize = map.size();
1172
    if (supportsPut) {
1173
      map.putAll(mapToPut);
1174
      assertEquals(valueToPut, map.get(keyToPut));
1175
      assertTrue(map.containsKey(keyToPut));
1176
      assertTrue(map.containsValue(valueToPut));
1177
    } else {
1178
      try {
1179
        map.putAll(mapToPut);
1180
        fail("Expected UnsupportedOperationException.");
1181
      } catch (UnsupportedOperationException expected) {
1182
      }
1183
    }
1184
    assertEquals(initialSize, map.size());
1185
    assertInvariants(map);
1186
  }
1187

1188
  public void testRemove() {
1189
    Map<K, V> map;
1190
    K keyToRemove;
1191
    try {
1192
      map = makePopulatedMap();
1193
    } catch (UnsupportedOperationException e) {
1194
      return;
1195
    }
1196
    keyToRemove = map.keySet().iterator().next();
1197
    if (supportsRemove) {
1198
      int initialSize = map.size();
1199
      V expectedValue = map.get(keyToRemove);
1200
      V oldValue = map.remove(keyToRemove);
1201
      assertEquals(expectedValue, oldValue);
1202
      assertFalse(map.containsKey(keyToRemove));
1203
      assertEquals(initialSize - 1, map.size());
1204
    } else {
1205
      try {
1206
        map.remove(keyToRemove);
1207
        fail("Expected UnsupportedOperationException.");
1208
      } catch (UnsupportedOperationException expected) {
1209
      }
1210
    }
1211
    assertInvariants(map);
1212
  }
1213

1214
  public void testRemoveMissingKey() {
1215
    Map<K, V> map;
1216
    K keyToRemove;
1217
    try {
1218
      map = makePopulatedMap();
1219
      keyToRemove = getKeyNotInPopulatedMap();
1220
    } catch (UnsupportedOperationException e) {
1221
      return;
1222
    }
1223
    if (supportsRemove) {
1224
      int initialSize = map.size();
1225
      assertNull(map.remove(keyToRemove));
1226
      assertEquals(initialSize, map.size());
1227
    } else {
1228
      try {
1229
        map.remove(keyToRemove);
1230
        fail("Expected UnsupportedOperationException.");
1231
      } catch (UnsupportedOperationException expected) {
1232
      }
1233
    }
1234
    assertInvariants(map);
1235
  }
1236

1237
  public void testSize() {
1238
    assertInvariants(makeEitherMap());
1239
  }
1240

1241
  public void testKeySetRemove() {
1242
    Map<K, V> map;
1243
    try {
1244
      map = makePopulatedMap();
1245
    } catch (UnsupportedOperationException e) {
1246
      return;
1247
    }
1248

1249
    Set<K> keys = map.keySet();
1250
    K key = keys.iterator().next();
1251
    if (supportsRemove) {
1252
      int initialSize = map.size();
1253
      keys.remove(key);
1254
      assertEquals(initialSize - 1, map.size());
1255
      assertFalse(map.containsKey(key));
1256
    } else {
1257
      try {
1258
        keys.remove(key);
1259
        fail("Expected UnsupportedOperationException.");
1260
      } catch (UnsupportedOperationException expected) {
1261
      }
1262
    }
1263
    assertInvariants(map);
1264
  }
1265

1266
  public void testKeySetRemoveAll() {
1267
    Map<K, V> map;
1268
    try {
1269
      map = makePopulatedMap();
1270
    } catch (UnsupportedOperationException e) {
1271
      return;
1272
    }
1273

1274
    Set<K> keys = map.keySet();
1275
    K key = keys.iterator().next();
1276
    if (supportsRemove) {
1277
      int initialSize = map.size();
1278
      assertTrue(keys.removeAll(Collections.singleton(key)));
1279
      assertEquals(initialSize - 1, map.size());
1280
      assertFalse(map.containsKey(key));
1281
    } else {
1282
      try {
1283
        keys.removeAll(Collections.singleton(key));
1284
        fail("Expected UnsupportedOperationException.");
1285
      } catch (UnsupportedOperationException expected) {
1286
      }
1287
    }
1288
    assertInvariants(map);
1289
  }
1290

1291
  public void testKeySetRetainAll() {
1292
    Map<K, V> map;
1293
    try {
1294
      map = makePopulatedMap();
1295
    } catch (UnsupportedOperationException e) {
1296
      return;
1297
    }
1298

1299
    Set<K> keys = map.keySet();
1300
    K key = keys.iterator().next();
1301
    if (supportsRemove) {
1302
      keys.retainAll(Collections.singleton(key));
1303
      assertEquals(1, map.size());
1304
      assertTrue(map.containsKey(key));
1305
    } else {
1306
      try {
1307
        keys.retainAll(Collections.singleton(key));
1308
        fail("Expected UnsupportedOperationException.");
1309
      } catch (UnsupportedOperationException expected) {
1310
      }
1311
    }
1312
    assertInvariants(map);
1313
  }
1314

1315
  public void testKeySetClear() {
1316
    Map<K, V> map;
1317
    try {
1318
      map = makeEitherMap();
1319
    } catch (UnsupportedOperationException e) {
1320
      return;
1321
    }
1322

1323
    Set<K> keySet = map.keySet();
1324
    if (supportsClear) {
1325
      keySet.clear();
1326
      assertTrue(keySet.isEmpty());
1327
    } else {
1328
      try {
1329
        keySet.clear();
1330
        fail("Expected UnsupportedOperationException.");
1331
      } catch (UnsupportedOperationException expected) {
1332
      }
1333
    }
1334
    assertInvariants(map);
1335
  }
1336

1337
  public void testKeySetRemoveAllNullFromEmpty() {
1338
    Map<K, V> map;
1339
    try {
1340
      map = makeEmptyMap();
1341
    } catch (UnsupportedOperationException e) {
1342
      return;
1343
    }
1344

1345
    Set<K> keySet = map.keySet();
1346
    if (supportsRemove) {
1347
      try {
1348
        keySet.removeAll(null);
1349
        fail("Expected NullPointerException.");
1350
      } catch (NullPointerException expected) {
1351
      }
1352
    } else {
1353
      try {
1354
        keySet.removeAll(null);
1355
        fail("Expected UnsupportedOperationException or NullPointerException.");
1356
      } catch (UnsupportedOperationException | NullPointerException e) {
1357
        // Expected.
1358
      }
1359
    }
1360
    assertInvariants(map);
1361
  }
1362

1363
  public void testKeySetRetainAllNullFromEmpty() {
1364
    Map<K, V> map;
1365
    try {
1366
      map = makeEmptyMap();
1367
    } catch (UnsupportedOperationException e) {
1368
      return;
1369
    }
1370

1371
    Set<K> keySet = map.keySet();
1372
    if (supportsRemove) {
1373
      try {
1374
        keySet.retainAll(null);
1375
        // Returning successfully is not ideal, but tolerated.
1376
      } catch (NullPointerException tolerated) {
1377
      }
1378
    } else {
1379
      try {
1380
        keySet.retainAll(null);
1381
        // We have to tolerate a successful return (Sun bug 4802647)
1382
      } catch (UnsupportedOperationException | NullPointerException e) {
1383
        // Expected.
1384
      }
1385
    }
1386
    assertInvariants(map);
1387
  }
1388

1389
  public void testValues() {
1390
    Map<K, V> map;
1391
    Collection<V> valueCollection;
1392
    try {
1393
      map = makePopulatedMap();
1394
    } catch (UnsupportedOperationException e) {
1395
      return;
1396
    }
1397
    assertInvariants(map);
1398

1399
    valueCollection = map.values();
1400
    V unmappedValue;
1401
    try {
1402
      unmappedValue = getValueNotInPopulatedMap();
1403
    } catch (UnsupportedOperationException e) {
1404
      return;
1405
    }
1406
    for (V value : valueCollection) {
1407
      assertFalse(unmappedValue.equals(value));
1408
    }
1409
  }
1410

1411
  public void testValuesIteratorRemove() {
1412
    Map<K, V> map;
1413
    try {
1414
      map = makePopulatedMap();
1415
    } catch (UnsupportedOperationException e) {
1416
      return;
1417
    }
1418

1419
    Collection<V> valueCollection = map.values();
1420
    Iterator<V> iterator = valueCollection.iterator();
1421
    if (supportsIteratorRemove) {
1422
      int initialSize = map.size();
1423
      iterator.next();
1424
      iterator.remove();
1425
      assertEquals(initialSize - 1, map.size());
1426
      // (We can't assert that the values collection no longer contains the
1427
      // removed value, because the underlying map can have multiple mappings
1428
      // to the same value.)
1429
      assertInvariants(map);
1430
      try {
1431
        iterator.remove();
1432
        fail("Expected IllegalStateException.");
1433
      } catch (IllegalStateException expected) {
1434
      }
1435
    } else {
1436
      iterator.next();
1437
      try {
1438
        iterator.remove();
1439
        fail("Expected UnsupportedOperationException.");
1440
      } catch (UnsupportedOperationException expected) {
1441
      }
1442
    }
1443
    assertInvariants(map);
1444
  }
1445

1446
  public void testValuesRemove() {
1447
    Map<K, V> map;
1448
    try {
1449
      map = makePopulatedMap();
1450
    } catch (UnsupportedOperationException e) {
1451
      return;
1452
    }
1453

1454
    Collection<V> valueCollection = map.values();
1455
    if (supportsRemove) {
1456
      int initialSize = map.size();
1457
      valueCollection.remove(valueCollection.iterator().next());
1458
      assertEquals(initialSize - 1, map.size());
1459
      // (We can't assert that the values collection no longer contains the
1460
      // removed value, because the underlying map can have multiple mappings
1461
      // to the same value.)
1462
    } else {
1463
      try {
1464
        valueCollection.remove(valueCollection.iterator().next());
1465
        fail("Expected UnsupportedOperationException.");
1466
      } catch (UnsupportedOperationException expected) {
1467
      }
1468
    }
1469
    assertInvariants(map);
1470
  }
1471

1472
  public void testValuesRemoveMissing() {
1473
    Map<K, V> map;
1474
    V valueToRemove;
1475
    try {
1476
      map = makeEitherMap();
1477
      valueToRemove = getValueNotInPopulatedMap();
1478
    } catch (UnsupportedOperationException e) {
1479
      return;
1480
    }
1481

1482
    Collection<V> valueCollection = map.values();
1483
    int initialSize = map.size();
1484
    if (supportsRemove) {
1485
      assertFalse(valueCollection.remove(valueToRemove));
1486
    } else {
1487
      try {
1488
        assertFalse(valueCollection.remove(valueToRemove));
1489
      } catch (UnsupportedOperationException e) {
1490
        // Tolerated.
1491
      }
1492
    }
1493
    assertEquals(initialSize, map.size());
1494
    assertInvariants(map);
1495
  }
1496

1497
  public void testValuesRemoveAll() {
1498
    Map<K, V> map;
1499
    try {
1500
      map = makePopulatedMap();
1501
    } catch (UnsupportedOperationException e) {
1502
      return;
1503
    }
1504

1505
    Collection<V> valueCollection = map.values();
1506
    Set<V> valuesToRemove = singleton(valueCollection.iterator().next());
1507
    if (supportsRemove) {
1508
      valueCollection.removeAll(valuesToRemove);
1509
      for (V value : valuesToRemove) {
1510
        assertFalse(valueCollection.contains(value));
1511
      }
1512
      for (V value : valueCollection) {
1513
        assertFalse(valuesToRemove.contains(value));
1514
      }
1515
    } else {
1516
      try {
1517
        valueCollection.removeAll(valuesToRemove);
1518
        fail("Expected UnsupportedOperationException.");
1519
      } catch (UnsupportedOperationException expected) {
1520
      }
1521
    }
1522
    assertInvariants(map);
1523
  }
1524

1525
  public void testValuesRemoveAllNullFromEmpty() {
1526
    Map<K, V> map;
1527
    try {
1528
      map = makeEmptyMap();
1529
    } catch (UnsupportedOperationException e) {
1530
      return;
1531
    }
1532

1533
    Collection<V> values = map.values();
1534
    if (supportsRemove) {
1535
      try {
1536
        values.removeAll(null);
1537
        // Returning successfully is not ideal, but tolerated.
1538
      } catch (NullPointerException tolerated) {
1539
      }
1540
    } else {
1541
      try {
1542
        values.removeAll(null);
1543
        // We have to tolerate a successful return (Sun bug 4802647)
1544
      } catch (UnsupportedOperationException | NullPointerException e) {
1545
        // Expected.
1546
      }
1547
    }
1548
    assertInvariants(map);
1549
  }
1550

1551
  public void testValuesRetainAll() {
1552
    Map<K, V> map;
1553
    try {
1554
      map = makePopulatedMap();
1555
    } catch (UnsupportedOperationException e) {
1556
      return;
1557
    }
1558

1559
    Collection<V> valueCollection = map.values();
1560
    Set<V> valuesToRetain = singleton(valueCollection.iterator().next());
1561
    if (supportsRemove) {
1562
      valueCollection.retainAll(valuesToRetain);
1563
      for (V value : valuesToRetain) {
1564
        assertTrue(valueCollection.contains(value));
1565
      }
1566
      for (V value : valueCollection) {
1567
        assertTrue(valuesToRetain.contains(value));
1568
      }
1569
    } else {
1570
      try {
1571
        valueCollection.retainAll(valuesToRetain);
1572
        fail("Expected UnsupportedOperationException.");
1573
      } catch (UnsupportedOperationException expected) {
1574
      }
1575
    }
1576
    assertInvariants(map);
1577
  }
1578

1579
  public void testValuesRetainAllNullFromEmpty() {
1580
    Map<K, V> map;
1581
    try {
1582
      map = makeEmptyMap();
1583
    } catch (UnsupportedOperationException e) {
1584
      return;
1585
    }
1586

1587
    Collection<V> values = map.values();
1588
    if (supportsRemove) {
1589
      try {
1590
        values.retainAll(null);
1591
        // Returning successfully is not ideal, but tolerated.
1592
      } catch (NullPointerException tolerated) {
1593
      }
1594
    } else {
1595
      try {
1596
        values.retainAll(null);
1597
        // We have to tolerate a successful return (Sun bug 4802647)
1598
      } catch (UnsupportedOperationException | NullPointerException e) {
1599
        // Expected.
1600
      }
1601
    }
1602
    assertInvariants(map);
1603
  }
1604

1605
  public void testValuesClear() {
1606
    Map<K, V> map;
1607
    try {
1608
      map = makePopulatedMap();
1609
    } catch (UnsupportedOperationException e) {
1610
      return;
1611
    }
1612

1613
    Collection<V> valueCollection = map.values();
1614
    if (supportsClear) {
1615
      valueCollection.clear();
1616
      assertTrue(valueCollection.isEmpty());
1617
    } else {
1618
      try {
1619
        valueCollection.clear();
1620
        fail("Expected UnsupportedOperationException.");
1621
      } catch (UnsupportedOperationException expected) {
1622
      }
1623
    }
1624
    assertInvariants(map);
1625
  }
1626

1627
  static <K extends @Nullable Object, V extends @Nullable Object> Entry<K, V> mapEntry(
1628
      K key, V value) {
1629
    return Collections.singletonMap(key, value).entrySet().iterator().next();
1630
  }
1631
}
1632