src/test/java/net/starlark/java/eval/CompactImmutableDictTest.java

// Copyright 2026 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 net.starlark.java.eval;

import static com.google.common.truth.Truth.assertThat;
import static org.junit.Assert.assertThrows;

import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Maps;
import com.google.common.testing.EqualsTester;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.NoSuchElementException;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

/** Tests for {@link CompactImmutableDict}. */
@RunWith(JUnit4.class)
public final class CompactImmutableDictTest {

  @Test
  public void emptyDict() {
    CompactImmutableDict<String, Integer> dict = CompactImmutableDict.copyOf(ImmutableMap.of());
    performUniversalChecks(dict);

    assertThat(dict.isEmpty()).isTrue();
    assertThat(dict.size()).isEqualTo(0);
    assertThat(dict.get("a")).isNull();
    assertThat(dict.containsKey("a")).isFalse();
    assertThat(dict.containsValue(1)).isFalse();

    assertThat(dict.keySet()).isEmpty();
    assertThat(dict.values()).isEmpty();
    assertThat(dict.entrySet()).isEmpty();

    dict.forEach(
        (k, v) -> {
          throw new AssertionError("Should not be called");
        });
  }

  @Test
  public void singletonDict() {
    CompactImmutableDict<String, Integer> dict =
        CompactImmutableDict.copyOf(ImmutableMap.of("a", 1));
    performUniversalChecks(dict);

    assertThat(dict.isEmpty()).isFalse();
    assertThat(dict.size()).isEqualTo(1);
    assertThat(dict.get("a")).isEqualTo(1);
    assertThat(dict.get("b")).isNull();
    assertThat(dict.containsKey("a")).isTrue();
    assertThat(dict.containsKey("b")).isFalse();
    assertThat(dict.containsValue(1)).isTrue();
    assertThat(dict.containsValue(2)).isFalse();

    assertThat(dict.keySet()).containsExactly("a");
    assertThat(dict.values()).containsExactly(1);
    assertThat(dict.entrySet()).hasSize(1);

    Map<String, Integer> visited = new HashMap<>();
    dict.forEach(visited::put);
    assertThat(visited).containsExactly("a", 1);
  }

  @Test
  public void doubletonDict() {
    CompactImmutableDict<String, Integer> dict =
        CompactImmutableDict.copyOf(ImmutableMap.of("a", 1, "b", 2));
    performUniversalChecks(dict);

    assertThat(dict.isEmpty()).isFalse();
    assertThat(dict.size()).isEqualTo(2);
    assertThat(dict.get("a")).isEqualTo(1);
    assertThat(dict.get("b")).isEqualTo(2);
    assertThat(dict.get("c")).isNull();
    assertThat(dict.containsKey("a")).isTrue();
    assertThat(dict.containsKey("b")).isTrue();
    assertThat(dict.containsKey("c")).isFalse();
    assertThat(dict.containsValue(1)).isTrue();
    assertThat(dict.containsValue(2)).isTrue();
    assertThat(dict.containsValue(3)).isFalse();

    assertThat(dict.keySet()).containsExactly("a", "b").inOrder();
    assertThat(dict.values()).containsExactly(1, 2).inOrder();
    assertThat(dict.entrySet()).hasSize(2);

    Map<String, Integer> visited = new LinkedHashMap<>();
    dict.forEach(visited::put);
    assertThat(visited).containsExactly("a", 1, "b", 2).inOrder();
  }

  @Test
  public void linearDict() {
    Map<String, Integer> source = new LinkedHashMap<>();
    for (int i = 0; i < 6; i++) {
      source.put("k" + i, i);
    }
    CompactImmutableDict<String, Integer> dict = CompactImmutableDict.copyOf(source);
    performUniversalChecks(dict);

    assertThat(dict.isEmpty()).isFalse();
    assertThat(dict.size()).isEqualTo(6);
    assertThat(dict.get("k3")).isEqualTo(3);
    assertThat(dict.get("k9")).isNull();
    assertThat(dict.containsKey("k3")).isTrue();
    assertThat(dict.containsKey("k9")).isFalse();
    assertThat(dict.containsValue(3)).isTrue();
    assertThat(dict.containsValue(9)).isFalse();

    assertThat(dict.keySet()).containsExactly("k0", "k1", "k2", "k3", "k4", "k5").inOrder();
    assertThat(dict.values()).containsExactly(0, 1, 2, 3, 4, 5).inOrder();

    Map<String, Integer> visited = new LinkedHashMap<>();
    dict.forEach(visited::put);
    assertThat(visited).containsExactlyEntriesIn(source).inOrder();
  }

  @Test
  public void hashDict() {
    Map<String, Integer> source = new LinkedHashMap<>();
    for (int i = 0; i < 12; i++) {
      source.put("k" + i, i);
    }
    CompactImmutableDict<String, Integer> dict = CompactImmutableDict.copyOf(source);
    performUniversalChecks(dict);

    assertThat(dict.isEmpty()).isFalse();
    assertThat(dict.size()).isEqualTo(12);
    assertThat(dict.get("k7")).isEqualTo(7);
    assertThat(dict.get("k99")).isNull();
    assertThat(dict.containsKey("k7")).isTrue();
    assertThat(dict.containsKey("k99")).isFalse();
    assertThat(dict.containsValue(7)).isTrue();
    assertThat(dict.containsValue(99)).isFalse();

    assertThat(dict.keySet())
        .containsExactly("k0", "k1", "k2", "k3", "k4", "k5", "k6", "k7", "k8", "k9", "k10", "k11")
        .inOrder();
    assertThat(dict.values()).containsExactly(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11).inOrder();

    Map<String, Integer> visited = new LinkedHashMap<>();
    dict.forEach(visited::put);
    assertThat(visited).containsExactlyEntriesIn(source).inOrder();
  }

  @Test
  public void iteratorNoSuchElementException() {
    CompactImmutableDict<String, Integer> dict =
        CompactImmutableDict.copyOf(ImmutableMap.of("a", 1, "b", 2, "c", 3));
    var it = dict.entrySet().iterator();

    assertThat(it.hasNext()).isTrue();
    it.next();
    assertThat(it.hasNext()).isTrue();
    it.next();
    assertThat(it.hasNext()).isTrue();
    it.next();
    assertThat(it.hasNext()).isFalse();

    assertThrows(NoSuchElementException.class, it::next);
  }

  @Test
  public void hashCollisions() {
    class BadHashKey {
      private final String val;

      BadHashKey(String val) {
        this.val = val;
      }

      @Override
      public int hashCode() {
        return 42; // Force every key to hash to the same primary slot!
      }

      @Override
      public boolean equals(Object obj) {
        return obj instanceof BadHashKey other && other.val.equals(val);
      }
    }

    Map<BadHashKey, Integer> source = new LinkedHashMap<>();
    for (int i = 0; i < 9; i++) {
      source.put(new BadHashKey("key" + i), i);
    }

    CompactImmutableDict<BadHashKey, Integer> dict = CompactImmutableDict.copyOf(source);

    // Verify all can be retrieved correctly (requires probing since every key collides!)
    for (int i = 0; i < 9; i++) {
      BadHashKey k = new BadHashKey("key" + i);
      assertThat(dict.get(k)).isEqualTo(i);
      assertThat(dict.containsKey(k)).isTrue();
    }

    // Verify absent key lookup works
    assertThat(dict.get(new BadHashKey("absent"))).isNull();
    assertThat(dict.containsKey(new BadHashKey("absent"))).isFalse();
  }

  @Test
  public void equalsAndHashCode() {
    new EqualsTester()
        // Empty
        .addEqualityGroup(createMapEqualityGroup(ImmutableMap.of()))
        // Singleton
        .addEqualityGroup(createMapEqualityGroup(ImmutableMap.of("a", "1")))
        .addEqualityGroup(createMapEqualityGroup(ImmutableMap.of("b", "2")))
        // Doubleton
        .addEqualityGroup(createMapEqualityGroup(ImmutableMap.of("a", "1", "b", "2")))
        .addEqualityGroup(createMapEqualityGroup(ImmutableMap.of("c", "3", "d", "4")))
        // Linear
        .addEqualityGroup(
            createMapEqualityGroup(
                ImmutableMap.of(
                    "a", "1",
                    "b", "2",
                    "c", "3")))
        .addEqualityGroup(
            createMapEqualityGroup(
                ImmutableMap.of(
                    "d", "4",
                    "e", "5",
                    "f", "6")))
        // Hash
        .addEqualityGroup(
            createMapEqualityGroup(
                ImmutableMap.of(
                    "a", "1",
                    "b", "2",
                    "c", "3",
                    "d", "4",
                    "e", "5",
                    "f", "6",
                    "g", "7",
                    "h", "8",
                    "i", "9")))
        .addEqualityGroup(
            createMapEqualityGroup(
                ImmutableMap.of(
                    "j", "10",
                    "k", "11",
                    "l", "12",
                    "m", "13",
                    "n", "14",
                    "o", "15",
                    "p", "16",
                    "q", "17",
                    "r", "18",
                    "s", "19")))
        .testEquals();
  }

  private static Object[] createMapEqualityGroup(ImmutableMap<String, String> m) {
    return new Object[] {
      // ImmutableMap
      m,
      // ImmutableMap with reverse order
      ImmutableMap.copyOf(m.entrySet().asList().reverse()),
      // MutableDict
      Dict.copyOf(Mutability.create(), m),
      // ImmutableMapBackedDict
      Dict.immutableCopyOf(m),
      // CompactImmutableDict
      CompactImmutableDict.copyOf(m)
    };
  }

  private static void performUniversalChecks(Dict<String, Integer> dict) {
    assertImmutable(dict);
    assertStarlarkMethodsRespectGivenMutablility(dict);
    assertNullSafeQueries(dict);
  }

  private static void assertImmutable(Dict<String, Integer> dict) {
    assertThrows(EvalException.class, () -> dict.putEntry("b", 2));
    assertThrows(EvalException.class, () -> dict.putEntries(ImmutableMap.of("b", 2)));
    assertThrows(EvalException.class, dict::clearEntries);
    assertThrows(EvalException.class, () -> dict.pop("a", null, null));
    assertThrows(EvalException.class, dict::popitem);
    assertThrows(EvalException.class, () -> dict.setdefault("b", 2));

    assertThrows(UnsupportedOperationException.class, () -> dict.put("b", 2));
    assertThrows(UnsupportedOperationException.class, () -> dict.putAll(ImmutableMap.of("b", 2)));
    assertThrows(UnsupportedOperationException.class, () -> dict.remove("a"));
    assertThrows(UnsupportedOperationException.class, dict::clear);
  }

  private static void assertStarlarkMethodsRespectGivenMutablility(Dict<?, ?> dict) {
    Mutability mu = Mutability.create();
    StarlarkThread thread = StarlarkThread.createTransient(mu, StarlarkSemantics.DEFAULT);
    assertThat(dict.keys(thread).mutability()).isSameInstanceAs(mu);
    assertThat(dict.values0(thread).mutability()).isSameInstanceAs(mu);
    assertThat(dict.items(thread).mutability()).isSameInstanceAs(mu);
  }

  private static void assertNullSafeQueries(Dict<?, ?> dict) {
    assertThat(dict.containsKey(null)).isFalse();
    assertThat(dict.containsValue(null)).isFalse();
    assertThat(dict.get(null)).isNull();
    assertThat(dict.keySet().contains(null)).isFalse();
    assertThat(dict.values().contains(null)).isFalse();
    assertThat(dict.entrySet().contains(null)).isFalse();
    assertThat(dict.entrySet().contains(Maps.immutableEntry(null, null))).isFalse();
    if (!dict.isEmpty()) {
      var presentKeyNullValueEntry = Maps.immutableEntry(dict.iterator().next(), null);
      assertThat(dict.entrySet().contains(presentKeyNullValueEntry)).isFalse();
    }
  }
}