| // Copyright 2021 The Bazel Authors. All rights reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| package com.google.devtools.build.lib.packages; |
| |
| import static com.google.common.truth.Truth.assertThat; |
| import static org.junit.Assert.assertThrows; |
| |
| import com.google.auto.value.AutoValue; |
| import com.google.common.base.Preconditions; |
| import com.google.common.collect.BiMap; |
| import com.google.common.collect.ImmutableBiMap; |
| import com.google.common.collect.ImmutableMap; |
| import java.util.AbstractMap; |
| import java.util.Collection; |
| import java.util.Iterator; |
| import java.util.Map; |
| import org.junit.Test; |
| import org.junit.runner.RunWith; |
| import org.junit.runners.JUnit4; |
| |
| /** Tests for {@link SnapshottableBiMap}. */ |
| @RunWith(JUnit4.class) |
| public final class SnapshottableBiMapTest { |
| // Dummy value type for maps under test. AutoValue for correct hash/equals behavior. |
| @AutoValue |
| abstract static class Value { |
| static Value trackedOf(String name) { |
| return new AutoValue_SnapshottableBiMapTest_Value(name, true); |
| } |
| |
| static Value untrackedOf(String name) { |
| return new AutoValue_SnapshottableBiMapTest_Value(name, false); |
| } |
| |
| static boolean track(Value value) { |
| return value.tracked(); |
| } |
| |
| abstract String name(); |
| |
| abstract boolean tracked(); |
| } |
| |
| private static <E> void verifyCollectionSizeAndContentsInOrder( |
| Collection<E> collection, Collection<E> expected) { |
| // Exhaustive testing of a collection's methods; we cannot rely on a minimal usual set of JUnit |
| // helpers because we want to verify that the collection has valid Collection semantics. |
| if (expected.isEmpty()) { |
| assertThat(collection).isEmpty(); |
| } else { |
| assertThat(collection).isNotEmpty(); |
| } |
| assertThat(collection).hasSize(expected.size()); |
| assertThat(collection).containsExactlyElementsIn(expected).inOrder(); |
| for (E entry : expected) { |
| // JUnit's containsExactlyElementsIn iterates over the collection under test, but doesn't call |
| // its contains() method. |
| assertThat(collection).contains(entry); |
| } |
| } |
| |
| private static <K, V> void verifyMapSizeAndContentsInOrder(Map<K, V> map, Map<K, V> expectedMap) { |
| // Exhaustive testing of a map's methods; we cannot rely on a minimal usual set of JUnit helpers |
| // because we want to verify that the map has valid Map semantics. |
| if (expectedMap.isEmpty()) { |
| assertThat(map).isEmpty(); |
| } else { |
| assertThat(map).isNotEmpty(); |
| } |
| |
| assertThat(map).hasSize(expectedMap.size()); |
| assertThat(map).containsExactlyEntriesIn(expectedMap).inOrder(); |
| |
| for (Map.Entry<K, V> entry : expectedMap.entrySet()) { |
| assertThat(map.containsKey(entry.getKey())) |
| .isTrue(); // JUnit's containsKey implementation does not explicitly call map.containsKey |
| assertThat(map.containsValue(entry.getValue())).isTrue(); |
| } |
| |
| verifyCollectionSizeAndContentsInOrder(map.entrySet(), expectedMap.entrySet()); |
| verifyCollectionSizeAndContentsInOrder(map.keySet(), expectedMap.keySet()); |
| verifyCollectionSizeAndContentsInOrder(map.values(), expectedMap.values()); |
| } |
| |
| @SuppressWarnings("unchecked") // test-only convenience vararg transformation |
| private static <K, V> void verifyMapSizeAndContentsInOrder( |
| Map<K, V> map, K key0, V value0, Object... rest) { |
| ImmutableMap.Builder<K, V> expectedBuilder = ImmutableMap.builder(); |
| expectedBuilder.put(key0, value0); |
| Preconditions.checkArgument( |
| rest.length % 2 == 0, "rest must be a flattened list of key-value pairs"); |
| for (int i = 0; i < rest.length; i += 2) { |
| expectedBuilder.put((K) rest[i], (V) rest[i + 1]); |
| } |
| Map<K, V> expectedMap = expectedBuilder.build(); |
| verifyMapSizeAndContentsInOrder(map, expectedMap); |
| } |
| |
| private static <K, V> void verifyMapDoesNotContainEntry(Map<K, V> map, K key, V value) { |
| Map.Entry<K, V> entry = new AbstractMap.SimpleEntry<>(key, value); |
| |
| // Exhaustive testing of a map's methods; we cannot rely on a minimal usual set of JUnit helpers |
| // because we want to verify that the map has valid Map semantics. |
| assertThat(map.containsKey(key)) |
| .isFalse(); // JUnit's containsKey implementation does not explicitly call map.containsKeys |
| assertThat(map.containsValue(value)).isFalse(); |
| assertThat(map.entrySet()).doesNotContain(entry); |
| assertThat(map.keySet()).doesNotContain(key); |
| assertThat(map.values()).doesNotContain(value); |
| } |
| |
| private static <K, V> void verifyMapIsEmpty(Map<K, V> map) { |
| verifyMapSizeAndContentsInOrder(map, ImmutableMap.of()); |
| } |
| |
| private static <E> void verifyIteratorDoesNotAllowDeletions(Iterator<E> iterator) { |
| while (iterator.hasNext()) { |
| iterator.next(); |
| assertThrows(UnsupportedOperationException.class, iterator::remove); |
| } |
| } |
| |
| private static <K, V> void verifyMapDoesNotAllowDeletions(Map<K, V> map) { |
| for (Map.Entry<K, V> entry : map.entrySet()) { |
| K key = entry.getKey(); |
| V value = entry.getValue(); |
| assertThrows(UnsupportedOperationException.class, () -> map.remove(key)); |
| assertThrows(UnsupportedOperationException.class, () -> map.keySet().remove(key)); |
| assertThrows(UnsupportedOperationException.class, () -> map.values().remove(value)); |
| assertThrows(UnsupportedOperationException.class, () -> map.entrySet().remove(entry)); |
| } |
| |
| verifyIteratorDoesNotAllowDeletions(map.keySet().iterator()); |
| verifyIteratorDoesNotAllowDeletions(map.values().iterator()); |
| verifyIteratorDoesNotAllowDeletions(map.entrySet().iterator()); |
| |
| assertThrows(UnsupportedOperationException.class, map::clear); |
| } |
| |
| @SuppressWarnings("unchecked") // test-only convenience vararg transformation |
| private static <K, V> void verifyBiMapSizeAndContentsInOrder( |
| BiMap<K, V> bimap, K key0, V value0, Object... rest) { |
| ImmutableBiMap.Builder<K, V> expectedBuilder = ImmutableBiMap.builder(); |
| expectedBuilder.put(key0, value0); |
| Preconditions.checkArgument( |
| rest.length % 2 == 0, "rest must be a flattened list of key-value pairs"); |
| for (int i = 0; i < rest.length; i += 2) { |
| expectedBuilder.put((K) rest[i], (V) rest[i + 1]); |
| } |
| BiMap<K, V> expectedBiMap = expectedBuilder.buildOrThrow(); |
| verifyMapSizeAndContentsInOrder(bimap, expectedBiMap); |
| verifyMapSizeAndContentsInOrder(bimap.inverse(), expectedBiMap.inverse()); |
| } |
| |
| private static <K, V> void verifyBiMapIsEmpty(BiMap<K, V> bimap) { |
| verifyMapSizeAndContentsInOrder(bimap, ImmutableMap.of()); |
| verifyMapSizeAndContentsInOrder(bimap.inverse(), ImmutableMap.of()); |
| } |
| |
| @Test |
| public void containsInsertedEntries() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| verifyBiMapIsEmpty(map); |
| Value a = Value.trackedOf("a"); |
| Value b = Value.untrackedOf("b"); |
| Value c = Value.trackedOf("c"); |
| Value z = Value.trackedOf("z"); |
| |
| map.put("a", a); |
| verifyBiMapSizeAndContentsInOrder(map, "a", a); |
| |
| map.put("b", b); |
| verifyBiMapSizeAndContentsInOrder(map, "a", a, "b", b); |
| |
| map.put("c", c); |
| verifyBiMapSizeAndContentsInOrder(map, "a", a, "b", b, "c", c); |
| |
| // verify that the map's various contains*() methods don't always return true. |
| verifyMapDoesNotContainEntry(map, "z", z); |
| } |
| |
| @Test |
| public void put_replacesEntries() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| Value trackedA = Value.trackedOf("a"); |
| Value replaceA = Value.trackedOf("replace a"); |
| Value untrackedB = Value.untrackedOf("b"); |
| Value replaceB = Value.untrackedOf("b"); |
| |
| map.put("a", trackedA); |
| map.put("a", replaceA); |
| map.put("b", untrackedB); |
| map.put("b", replaceB); |
| verifyBiMapSizeAndContentsInOrder(map, "a", replaceA, "b", replaceB); |
| } |
| |
| @Test |
| public void put_nonUniqueValue_illegal() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| Value tracked = Value.trackedOf("a"); |
| Value untracked = Value.untrackedOf("b"); |
| |
| map.put("a", tracked); |
| assertThrows(IllegalArgumentException.class, () -> map.put("aa", tracked)); |
| map.put("b", untracked); |
| assertThrows(IllegalArgumentException.class, () -> map.put("bb", untracked)); |
| } |
| |
| @Test |
| public void put_replacingUntrackedWithTracked_legal() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| Value tracked = Value.trackedOf("a"); |
| Value untracked = Value.untrackedOf("A"); |
| |
| map.getTrackedSnapshot(); // start tracking |
| map.put("a", untracked); |
| map.put("a", tracked); |
| verifyBiMapSizeAndContentsInOrder(map, "a", tracked); |
| } |
| |
| @Test |
| public void put_replacingTrackedWithUntracked_illegal() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| Value tracked = Value.trackedOf("a"); |
| Value untracked = Value.untrackedOf("A"); |
| |
| map.getTrackedSnapshot(); // start tracking |
| map.put("a", tracked); |
| assertThrows(IllegalArgumentException.class, () -> map.put("a", untracked)); |
| } |
| |
| @Test |
| @SuppressWarnings("deprecation") // test verifying that deprecated methods don't work |
| public void deletions_unsupported() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| Value value = Value.trackedOf("a"); |
| Value replacement = Value.trackedOf("replacement a"); |
| |
| map.put("a", value); |
| verifyMapDoesNotAllowDeletions(map); |
| verifyMapDoesNotAllowDeletions(map.inverse()); |
| assertThrows(UnsupportedOperationException.class, () -> map.forcePut("a", replacement)); |
| assertThrows(UnsupportedOperationException.class, () -> map.inverse().forcePut(value, "aa")); |
| } |
| |
| @Test |
| public void getUnderlyingBiMap_returnsBiMapSupportingRemove() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| Value a = Value.trackedOf("a"); |
| Value b = Value.untrackedOf("b"); |
| Value c = Value.trackedOf("c"); |
| |
| map.put("a", a); |
| map.put("b", b); |
| map.put("c", c); |
| BiMap<String, Value> underlying = map.getUnderlyingBiMap(); |
| verifyBiMapSizeAndContentsInOrder(underlying, "a", a, "b", b, "c", c); |
| |
| underlying.remove("a"); |
| verifyBiMapSizeAndContentsInOrder(underlying, "b", b, "c", c); |
| } |
| |
| @Test |
| public void snapshot_containsExpectedEntries() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| Value trackedA = Value.trackedOf("a"); |
| Value untrackedB = Value.untrackedOf("b"); |
| Value trackedC = Value.trackedOf("c"); |
| Value z = Value.trackedOf("z"); |
| |
| Map<String, Value> snapshot0 = map.getTrackedSnapshot(); |
| verifyMapIsEmpty(snapshot0); |
| |
| map.put("a", trackedA); |
| Map<String, Value> snapshot1 = map.getTrackedSnapshot(); |
| verifyMapIsEmpty(snapshot0); |
| verifyMapSizeAndContentsInOrder(snapshot1, "a", trackedA); |
| |
| map.put("b", untrackedB); |
| Map<String, Value> snapshot2 = map.getTrackedSnapshot(); |
| verifyMapIsEmpty(snapshot0); |
| verifyMapSizeAndContentsInOrder(snapshot1, "a", trackedA); |
| verifyMapSizeAndContentsInOrder(snapshot2, "a", trackedA); // b is untracked |
| |
| map.put("c", Value.trackedOf("c")); |
| Map<String, Value> snapshot3 = map.getTrackedSnapshot(); |
| verifyMapIsEmpty(snapshot0); |
| verifyMapSizeAndContentsInOrder(snapshot1, "a", trackedA); // c was added after snapshot |
| verifyMapSizeAndContentsInOrder(snapshot2, "a", trackedA); |
| verifyMapSizeAndContentsInOrder(snapshot3, "a", trackedA, "c", trackedC); |
| |
| // verify that a snapshot's various contains*() methods don't always return true. |
| verifyMapDoesNotContainEntry(snapshot1, "z", z); |
| verifyMapDoesNotContainEntry(snapshot2, "z", z); |
| verifyMapDoesNotContainEntry(snapshot3, "z", z); |
| } |
| |
| @Test |
| public void snapshot_isUnmodifiable() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| map.put("a", Value.trackedOf("a")); |
| map.put("b", Value.untrackedOf("b")); |
| map.put("c", Value.trackedOf("c")); |
| Map<String, Value> snapshot = map.getTrackedSnapshot(); |
| |
| verifyMapDoesNotAllowDeletions(snapshot); |
| assertThrows( |
| UnsupportedOperationException.class, () -> snapshot.put("a", Value.trackedOf("replace a"))); |
| assertThrows( |
| UnsupportedOperationException.class, () -> snapshot.put("d", Value.trackedOf("d"))); |
| } |
| |
| @Test |
| public void snapshot_containsReplacementsPerformedBeforeSnapshotCreation() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| Value trackedA = Value.trackedOf("a"); |
| Value replacementA = Value.trackedOf("replacement a"); |
| Value untrackedB = Value.untrackedOf("b"); |
| Value replacementB = Value.trackedOf("replacement b"); |
| |
| map.put("a", trackedA); |
| map.put("b", untrackedB); |
| verifyMapSizeAndContentsInOrder(map, "a", trackedA, "b", untrackedB); |
| map.put("a", replacementA); |
| map.put("b", replacementB); |
| verifyMapSizeAndContentsInOrder(map, "a", replacementA, "b", replacementB); |
| |
| Map<String, Value> snapshot = map.getTrackedSnapshot(); |
| verifyMapSizeAndContentsInOrder(snapshot, "a", replacementA, "b", replacementB); |
| } |
| |
| @Test |
| public void snapshot_afterReplacingEntryInSnapshot_containsReplacement() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| Value original = Value.trackedOf("a"); |
| Value replacement = Value.trackedOf("replacement a"); |
| |
| map.put("a", original); |
| Map<String, Value> snapshot = map.getTrackedSnapshot(); |
| verifyMapSizeAndContentsInOrder(snapshot, "a", original); |
| |
| map.put("a", replacement); |
| verifyMapSizeAndContentsInOrder(snapshot, "a", replacement); |
| } |
| |
| @Test |
| public void snapshot_afterReplacingEntryNotInSnapshot_doesNotContainReplacement() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| Value untrackedA = Value.untrackedOf("a"); |
| Value replacementA = Value.trackedOf("replacement a"); |
| Value trackedB = Value.trackedOf("b"); |
| Value replacementB = Value.trackedOf("replacement b"); |
| |
| map.put("a", untrackedA); |
| Map<String, Value> snapshot = map.getTrackedSnapshot(); |
| verifyMapIsEmpty(snapshot); |
| |
| map.put("a", replacementA); |
| map.put("b", trackedB); |
| map.put("b", replacementB); |
| verifyMapSizeAndContentsInOrder(map, "a", replacementA, "b", replacementB); |
| verifyMapIsEmpty(snapshot); |
| } |
| |
| @Test |
| public void snapshot_containsReplacementEntries_inOriginalKeyInsertionOrder() { |
| SnapshottableBiMap<String, Value> map = new SnapshottableBiMap<>(Value::track); |
| Value a = Value.trackedOf("a"); |
| Value b = Value.trackedOf("b"); |
| Value replaceB = Value.trackedOf("replacement b"); |
| Value c = Value.trackedOf("c"); |
| Value replaceC = Value.trackedOf("replacement c"); |
| |
| map.put("a", a); |
| map.put("b", b); |
| map.put("c", c); |
| |
| Map<String, Value> snapshot = map.getTrackedSnapshot(); |
| verifyMapSizeAndContentsInOrder(snapshot, "a", a, "b", b, "c", c); |
| |
| map.put("c", replaceC); |
| map.put("b", replaceB); |
| verifyMapSizeAndContentsInOrder(snapshot, "a", a, "b", replaceB, "c", replaceC); |
| } |
| } |