Delete `ImmutableSortedKeyMap` in favor of `ImmutableSortedMap`, which is essentially the same thing but likely less prone to performance issues. There don't seem to be any issues with the way we use it currently, but using the well-supported guava type provides stronger guarantees that it will stay that way. PiperOrigin-RevId: 382780837
diff --git a/src/main/java/com/google/devtools/build/lib/collect/ImmutableSortedKeyMap.java b/src/main/java/com/google/devtools/build/lib/collect/ImmutableSortedKeyMap.java deleted file mode 100644 index 16ee19a..0000000 --- a/src/main/java/com/google/devtools/build/lib/collect/ImmutableSortedKeyMap.java +++ /dev/null
@@ -1,296 +0,0 @@ -// Copyright 2014 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.collect; - -import static com.google.common.collect.ImmutableSet.toImmutableSet; -import static java.util.stream.Collectors.joining; - -import com.google.common.base.Preconditions; -import com.google.common.collect.ImmutableSet; -import com.google.common.collect.Streams; -import java.util.AbstractCollection; -import java.util.AbstractMap.SimpleImmutableEntry; -import java.util.Arrays; -import java.util.Collection; -import java.util.Collections; -import java.util.HashMap; -import java.util.Iterator; -import java.util.Map; -import java.util.NoSuchElementException; -import java.util.Set; -import java.util.stream.Stream; -import javax.annotation.Nullable; - -/** - * A immutable map implementation for maps with comparable keys. It uses a sorted array - * and binary search to return the correct values. Its only purpose is to save memory - for n - * entries, it consumes 8n + 64 bytes, much less than a normal HashMap (43n + 128) or an - * ImmutableMap (35n + 81). - * - * <p>Only a few methods are efficiently implemented: {@link #isEmpty} is O(1), {@link #get} and - * {@link #containsKey} are O(log(n)), using binary search; {@link #keySet} and {@link #values} - * refer to the parent instance. All other methods can take O(n) or even make a copy of the - * contents. - * - * <p>This implementation supports neither {@code null} keys nor {@code null} values. - * - * @param <K> the type of keys maintained by this map; keys must be comparable - * @param <V> the type of mapped values - */ -public final class ImmutableSortedKeyMap<K extends Comparable<K>, V> implements Map<K, V> { - - @SuppressWarnings({"rawtypes", "unchecked"}) - private static final ImmutableSortedKeyMap EMPTY_MAP = - new ImmutableSortedKeyMap(new Comparable<?>[0], new Object[0]); - - /** Returns the empty multimap. */ - @SuppressWarnings("unchecked") - public static <K extends Comparable<K>, V> ImmutableSortedKeyMap<K, V> of() { - // Safe because the multimap will never hold any elements. - return EMPTY_MAP; - } - - public static <K extends Comparable<K>, V> ImmutableSortedKeyMap<K, V> of(K key0, V value0) { - return ImmutableSortedKeyMap.<K, V>builder() - .put(key0, value0) - .build(); - } - - public static <K extends Comparable<K>, V> ImmutableSortedKeyMap<K, V> of( - K key0, V value0, K key1, V value1) { - return ImmutableSortedKeyMap.<K, V>builder() - .put(key0, value0) - .put(key1, value1) - .build(); - } - - @SuppressWarnings("unchecked") - public static <K extends Comparable<K>, V> ImmutableSortedKeyMap<K, V> copyOf(Map<K, V> data) { - if (data.isEmpty()) { - return EMPTY_MAP; - } - if (data instanceof ImmutableSortedKeyMap) { - return (ImmutableSortedKeyMap<K, V>) data; - } - Set<K> keySet = data.keySet(); - int size = keySet.size(); - K[] sortedKeys = (K[]) new Comparable<?>[size]; - int index = 0; - for (K key : keySet) { - sortedKeys[index] = Preconditions.checkNotNull(key); - index++; - } - Arrays.sort(sortedKeys); - V[] values = (V[]) new Object[size]; - for (int i = 0; i < size; i++) { - values[i] = data.get(sortedKeys[i]); - } - return new ImmutableSortedKeyMap<>(sortedKeys, values); - } - - public static <K extends Comparable<K>, V> Builder<K, V> builder() { - return new Builder<>(); - } - - /** - * A builder class for ImmutableSortedKeyListMultimap<K, V> instances. - */ - public static final class Builder<K extends Comparable<K>, V> { - private final Map<K, V> builderMap = new HashMap<>(); - - Builder() { - // Not public so you must call builder() instead. - } - - public ImmutableSortedKeyMap<K, V> build() { - return ImmutableSortedKeyMap.copyOf(builderMap); - } - - public Builder<K, V> put(K key, V value) { - builderMap.put(Preconditions.checkNotNull(key), Preconditions.checkNotNull(value)); - return this; - } - - public Builder<K, V> putAll(Map<? extends K, ? extends V> map) { - map.forEach((key, value) -> put(key, value)); - return this; - } - } - - private class ValuesCollection extends AbstractCollection<V> { - - ValuesCollection() { - } - - @Override - public int size() { - return ImmutableSortedKeyMap.this.size(); - } - - @Override - public boolean isEmpty() { - return sortedKeys.length == 0; - } - - @Override - public boolean contains(Object o) { - return ImmutableSortedKeyMap.this.containsValue(o); - } - - @Override - public Iterator<V> iterator() { - if (isEmpty()) { - return Collections.emptyIterator(); - } - return new Iterator<V>() { - private int currentIndex = 0; - - @Override - public boolean hasNext() { - return currentIndex < values.length; - } - - @Override - public V next() { - if (currentIndex >= values.length) { - throw new NoSuchElementException(); - } - return values[currentIndex++]; - } - }; - } - - @Override - public boolean remove(Object o) { - throw new UnsupportedOperationException(); - } - - @Override - public boolean removeAll(Collection<?> c) { - throw new UnsupportedOperationException(); - } - - @Override - public boolean retainAll(Collection<?> c) { - throw new UnsupportedOperationException(); - } - - @Override - public void clear() { - throw new UnsupportedOperationException(); - } - } - - private final K[] sortedKeys; - private final V[] values; - - private ImmutableSortedKeyMap(K[] sortedKeys, V[] values) { - this.sortedKeys = sortedKeys; - this.values = values; - } - - @Override - public int size() { - return sortedKeys.length; - } - - @Override - public boolean isEmpty() { - return sortedKeys.length == 0; - } - - @Override - public boolean containsKey(@Nullable Object key) { - if (key == null) { - return false; - } - int index = Arrays.binarySearch(sortedKeys, key); - return index >= 0; - } - - @Override - public boolean containsValue(@Nullable Object value) { - return value != null && Arrays.stream(values).anyMatch(v -> v.equals(value)); - } - - @Override - public V put(K key, V value) { - throw new UnsupportedOperationException(); - } - - @Override - public V remove(Object key) { - throw new UnsupportedOperationException(); - } - - @Override - public void putAll(Map<? extends K, ? extends V> map) { - throw new UnsupportedOperationException(); - } - - @Override - public void clear() { - throw new UnsupportedOperationException(); - } - - @Override - public V get(@Nullable Object key) { - if (key == null) { - return null; - } - int index = Arrays.binarySearch(sortedKeys, key); - return index >= 0 ? values[index] : null; - } - - @Override - public Set<K> keySet() { - return ImmutableSet.copyOf(sortedKeys); - } - - @Override - public Collection<V> values() { - return new ValuesCollection(); - } - - @Override - public Set<Entry<K, V>> entrySet() { - return entryStream().collect(toImmutableSet()); - } - - @Override - public String toString() { - return Streams.zip(Arrays.stream(sortedKeys), Arrays.stream(values), (k, v) -> k + "=" + v) - .collect(joining(", ", "{", "}")); - } - - @Override - public int hashCode() { - return entryStream().mapToInt(Entry::hashCode).sum(); - } - - @Override - public boolean equals(@Nullable Object object) { - if (this == object) { - return true; - } - if (object instanceof Map) { - throw new UnsupportedOperationException(); - } - return false; - } - - private Stream<Entry<K, V>> entryStream() { - return Streams.zip(Arrays.stream(sortedKeys), Arrays.stream(values), SimpleImmutableEntry::new); - } -}
diff --git a/src/main/java/com/google/devtools/build/lib/packages/Package.java b/src/main/java/com/google/devtools/build/lib/packages/Package.java index af3c802..2a5754e 100644 --- a/src/main/java/com/google/devtools/build/lib/packages/Package.java +++ b/src/main/java/com/google/devtools/build/lib/packages/Package.java
@@ -23,6 +23,7 @@ import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; import com.google.common.collect.ImmutableSet; +import com.google.common.collect.ImmutableSortedMap; import com.google.common.collect.ImmutableSortedSet; import com.google.common.collect.Interner; import com.google.common.collect.Iterables; @@ -34,7 +35,6 @@ import com.google.devtools.build.lib.cmdline.PackageIdentifier; import com.google.devtools.build.lib.cmdline.RepositoryName; import com.google.devtools.build.lib.collect.CollectionUtils; -import com.google.devtools.build.lib.collect.ImmutableSortedKeyMap; import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible; import com.google.devtools.build.lib.events.Event; import com.google.devtools.build.lib.events.EventHandler; @@ -137,7 +137,7 @@ private ImmutableMap<String, String> makeEnv; /** The collection of all targets defined in this package, indexed by name. */ - private ImmutableSortedKeyMap<String, Target> targets; + private ImmutableSortedMap<String, Target> targets; /** * Default visibility for rules that do not specify it. @@ -445,7 +445,7 @@ } this.makeEnv = ImmutableMap.copyOf(builder.makeEnv); - this.targets = ImmutableSortedKeyMap.copyOf(builder.targets); + this.targets = ImmutableSortedMap.copyOf(builder.targets); this.defaultVisibility = builder.defaultVisibility; this.defaultVisibilitySet = builder.defaultVisibilitySet; this.configSettingVisibilityPolicy = builder.configSettingVisibilityPolicy; @@ -600,7 +600,7 @@ } /** Returns an (immutable, ordered) view of all the targets belonging to this package. */ - public ImmutableSortedKeyMap<String, Target> getTargets() { + public ImmutableSortedMap<String, Target> getTargets() { return targets; }
diff --git a/src/test/java/com/google/devtools/build/lib/collect/ImmutableSortedKeyMapTest.java b/src/test/java/com/google/devtools/build/lib/collect/ImmutableSortedKeyMapTest.java deleted file mode 100644 index d6b13c5..0000000 --- a/src/test/java/com/google/devtools/build/lib/collect/ImmutableSortedKeyMapTest.java +++ /dev/null
@@ -1,275 +0,0 @@ -// Copyright 2014 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.collect; - -import static com.google.common.truth.Truth.assertThat; -import static org.junit.Assert.assertThrows; - -import com.google.common.collect.Maps; -import com.google.common.testing.NullPointerTester; -import java.io.Serializable; -import java.util.Collections; -import java.util.Iterator; -import java.util.LinkedHashMap; -import java.util.Map; -import org.junit.Test; -import org.junit.runner.RunWith; -import org.junit.runners.JUnit4; - -/** - * A test for {@link ImmutableSortedKeyListMultimap}. Started out as a blatant copy of - * ImmutableListMapTest. - */ -@RunWith(JUnit4.class) -public class ImmutableSortedKeyMapTest { - - @Test - public void emptyBuilder() { - ImmutableSortedKeyMap<String, Integer> map - = ImmutableSortedKeyMap.<String, Integer>builder().build(); - assertThat(map).isEmpty(); - } - - @Test - public void singletonBuilder() { - ImmutableSortedKeyMap<String, Integer> map = ImmutableSortedKeyMap.<String, Integer>builder() - .put("one", 1) - .build(); - assertMapEquals(map, "one", 1); - } - - @Test - public void builder() { - ImmutableSortedKeyMap<String, Integer> map = ImmutableSortedKeyMap.<String, Integer>builder() - .put("one", 1) - .put("two", 2) - .put("three", 3) - .put("four", 4) - .put("five", 5) - .build(); - assertMapEquals(map, - "five", 5, "four", 4, "one", 1, "three", 3, "two", 2); - } - - @Test - public void builderPutAllWithEmptyMap() { - ImmutableSortedKeyMap<String, Integer> map = ImmutableSortedKeyMap.<String, Integer>builder() - .putAll(Collections.<String, Integer>emptyMap()) - .build(); - assertThat(map).isEmpty(); - } - - @Test - public void builderPutAll() { - Map<String, Integer> toPut = new LinkedHashMap<>(); - toPut.put("one", 1); - toPut.put("two", 2); - toPut.put("three", 3); - Map<String, Integer> moreToPut = new LinkedHashMap<>(); - moreToPut.put("four", 4); - moreToPut.put("five", 5); - - ImmutableSortedKeyMap<String, Integer> map = ImmutableSortedKeyMap.<String, Integer>builder() - .putAll(toPut) - .putAll(moreToPut) - .build(); - assertMapEquals(map, - "five", 5, "four", 4, "one", 1, "three", 3, "two", 2); - } - - @Test - public void builderReuse() { - ImmutableSortedKeyMap.Builder<String, Integer> builder = - ImmutableSortedKeyMap.<String, Integer>builder(); - ImmutableSortedKeyMap<String, Integer> mapOne = builder - .put("one", 1) - .put("two", 2) - .build(); - ImmutableSortedKeyMap<String, Integer> mapTwo = builder - .put("three", 3) - .put("four", 4) - .build(); - - assertMapEquals(mapOne, "one", 1, "two", 2); - assertMapEquals(mapTwo, "four", 4, "one", 1, "three", 3, "two", 2); - } - - @Test - public void builderPutNullKey() { - ImmutableSortedKeyMap.Builder<String, Integer> builder = new ImmutableSortedKeyMap.Builder<>(); - assertThrows(NullPointerException.class, () -> builder.put(null, 1)); - } - - @Test - public void builderPutNullValue() { - ImmutableSortedKeyMap.Builder<String, Integer> builder = new ImmutableSortedKeyMap.Builder<>(); - assertThrows(NullPointerException.class, () -> builder.put("one", null)); - } - - @Test - public void builderPutNullKeyViaPutAll() { - ImmutableSortedKeyMap.Builder<String, Integer> builder = new ImmutableSortedKeyMap.Builder<>(); - assertThrows( - NullPointerException.class, - () -> builder.putAll(Collections.<String, Integer>singletonMap(null, 1))); - } - - @Test - public void builderPutNullValueViaPutAll() { - ImmutableSortedKeyMap.Builder<String, Integer> builder = new ImmutableSortedKeyMap.Builder<>(); - assertThrows( - NullPointerException.class, - () -> builder.putAll(Collections.<String, Integer>singletonMap("one", null))); - } - - @Test - public void of() { - assertMapEquals( - ImmutableSortedKeyMap.of("one", 1), - "one", 1); - assertMapEquals( - ImmutableSortedKeyMap.of("one", 1, "two", 2), - "one", 1, "two", 2); - } - - @Test - public void ofNullKey() { - assertThrows(NullPointerException.class, () -> ImmutableSortedKeyMap.of((String) null, 1)); - - assertThrows(NullPointerException.class, () -> ImmutableSortedKeyMap.of("one", 1, null, 2)); - } - - @Test - public void ofNullValue() { - assertThrows(NullPointerException.class, () -> ImmutableSortedKeyMap.of("one", null)); - - assertThrows(NullPointerException.class, () -> ImmutableSortedKeyMap.of("one", 1, "two", null)); - } - - @Test - public void copyOfEmptyMap() { - ImmutableSortedKeyMap<String, Integer> copy - = ImmutableSortedKeyMap.copyOf(Collections.<String, Integer>emptyMap()); - assertThat(copy).isEmpty(); - assertThat(ImmutableSortedKeyMap.copyOf(copy)).isSameInstanceAs(copy); - } - - @Test - public void copyOfSingletonMap() { - ImmutableSortedKeyMap<String, Integer> copy - = ImmutableSortedKeyMap.copyOf(Collections.singletonMap("one", 1)); - assertMapEquals(copy, "one", 1); - assertThat(ImmutableSortedKeyMap.copyOf(copy)).isSameInstanceAs(copy); - } - - @Test - public void copyOf() { - Map<String, Integer> original = new LinkedHashMap<>(); - original.put("one", 1); - original.put("two", 2); - original.put("three", 3); - - ImmutableSortedKeyMap<String, Integer> copy = ImmutableSortedKeyMap.copyOf(original); - assertMapEquals(copy, "one", 1, "three", 3, "two", 2); - assertThat(ImmutableSortedKeyMap.copyOf(copy)).isSameInstanceAs(copy); - } - - @Test - public void nullGet() { - ImmutableSortedKeyMap<String, Integer> map = ImmutableSortedKeyMap.of("one", 1); - assertThat(map).doesNotContainKey(null); - } - - @Test - public void nullPointers() { - NullPointerTester tester = new NullPointerTester(); - tester.testAllPublicStaticMethods(ImmutableSortedKeyMap.class); - tester.testAllPublicInstanceMethods( - new ImmutableSortedKeyMap.Builder<String, Object>()); - tester.testAllPublicInstanceMethods(ImmutableSortedKeyMap.<String, Integer>of()); - tester.testAllPublicInstanceMethods(ImmutableSortedKeyMap.of("one", 1)); - tester.testAllPublicInstanceMethods( - ImmutableSortedKeyMap.of("one", 1, "two", 2)); - } - - private static <K, V> void assertMapEquals(Map<K, V> map, - Object... alternatingKeysAndValues) { - assertThat(alternatingKeysAndValues.length / 2).isEqualTo(map.size()); - int i = 0; - for (Map.Entry<K, V> entry : map.entrySet()) { - assertThat(entry.getKey()).isEqualTo(alternatingKeysAndValues[i++]); - assertThat(entry.getValue()).isEqualTo(alternatingKeysAndValues[i++]); - } - } - - private static class IntHolder implements Serializable { - public int value; - - public IntHolder(int value) { - this.value = value; - } - - @Override public boolean equals(Object o) { - return (o instanceof IntHolder) && ((IntHolder) o).value == value; - } - - @Override public int hashCode() { - return value; - } - - private static final long serialVersionUID = 5; - } - - @Test - public void mutableValues() { - IntHolder holderA = new IntHolder(1); - IntHolder holderB = new IntHolder(2); - Map<String, IntHolder> map = ImmutableSortedKeyMap.of("a", holderA, "b", holderB); - holderA.value = 3; - assertThat(map.entrySet()).contains(Maps.immutableEntry("a", new IntHolder(3))); - Map<String, Integer> intMap = ImmutableSortedKeyMap.of("a", 3, "b", 2); - assertThat(map.entrySet().hashCode()).isEqualTo(intMap.hashCode()); - assertThat(map.hashCode()).isEqualTo(intMap.hashCode()); - } - - @Test - public void toStringTest() { - Map<String, Integer> map = ImmutableSortedKeyMap.of("a", 1, "b", 2); - assertThat(map.toString()).isEqualTo("{a=1, b=2}"); - map = ImmutableSortedKeyMap.of(); - assertThat(map.toString()).isEqualTo("{}"); - } - - @Test - public void emptyValuesCollectionTest() { - Map<String, Integer> map = ImmutableSortedKeyMap.of(); - assertThat(map.values().size()).isEqualTo(0); - assertThat(map.values()).containsExactly(); - Iterator<Integer> it = map.values().iterator(); - assertThat(it.hasNext()).isFalse(); - } - - @Test - public void valuesCollectionTest() { - Map<String, Integer> map = ImmutableSortedKeyMap.of("a", 1, "b", 2); - assertThat(map.values().size()).isEqualTo(2); - assertThat(map.values()).containsExactly(1, 2); - Iterator<Integer> it = map.values().iterator(); - assertThat(it.hasNext()).isTrue(); - assertThat(it.next()).isEqualTo(1); - assertThat(it.hasNext()).isTrue(); - assertThat(it.next()).isEqualTo(2); - assertThat(it.hasNext()).isFalse(); - } -}
diff --git a/src/test/java/com/google/devtools/build/lib/packages/metrics/BUILD b/src/test/java/com/google/devtools/build/lib/packages/metrics/BUILD index 2fa85d9..79683c2 100644 --- a/src/test/java/com/google/devtools/build/lib/packages/metrics/BUILD +++ b/src/test/java/com/google/devtools/build/lib/packages/metrics/BUILD
@@ -20,12 +20,10 @@ srcs = ["PackageMetricsPackageLoadingListenerTest.java"], deps = [ "//src/main/java/com/google/devtools/build/lib/cmdline", - "//src/main/java/com/google/devtools/build/lib/collect", "//src/main/java/com/google/devtools/build/lib/packages", "//src/main/java/com/google/devtools/build/lib/packages/metrics", "//src/main/java/com/google/devtools/build/lib/packages/metrics:package_metrics_java_proto", "//src/main/java/net/starlark/java/eval", - "//src/main/java/net/starlark/java/syntax", "//third_party:guava", "//third_party:junit4", "//third_party:mockito",
diff --git a/src/test/java/com/google/devtools/build/lib/packages/metrics/PackageMetricsPackageLoadingListenerTest.java b/src/test/java/com/google/devtools/build/lib/packages/metrics/PackageMetricsPackageLoadingListenerTest.java index 390f077..47a4fca 100644 --- a/src/test/java/com/google/devtools/build/lib/packages/metrics/PackageMetricsPackageLoadingListenerTest.java +++ b/src/test/java/com/google/devtools/build/lib/packages/metrics/PackageMetricsPackageLoadingListenerTest.java
@@ -19,9 +19,9 @@ import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableMap; +import com.google.common.collect.ImmutableSortedMap; import com.google.devtools.build.lib.cmdline.Label; import com.google.devtools.build.lib.cmdline.PackageIdentifier; -import com.google.devtools.build.lib.collect.ImmutableSortedKeyMap; import com.google.devtools.build.lib.packages.Package; import com.google.devtools.build.lib.packages.Target; import com.google.protobuf.util.Durations; @@ -569,7 +569,7 @@ Package mockPackage = mock(Package.class); when(mockPackage.getPackageIdentifier()) .thenReturn(PackageIdentifier.createInMainRepo(pkgIdString)); - when(mockPackage.getTargets()).thenReturn(ImmutableSortedKeyMap.copyOf(targets)); + when(mockPackage.getTargets()).thenReturn(ImmutableSortedMap.copyOf(targets)); when(mockPackage.getStarlarkFileDependencies()) .thenReturn(ImmutableList.copyOf(starlarkDependencies)); return mockPackage;