src/test/java/com/google/devtools/build/lib/packages/SnapshottableBiMapTest.java

// 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);
  }
}