bazel: encapsulate the representation of NestedSet
Before, NestedSet exposed its representation far and wide
in ways obvious (getChildrenUnsafe) and subtle (downcasting
NestedSetView.identity()).
This change encapsulates the representation of NestedSet,
allowing it to be improved in future. It also documents the
data type's conceptual model.
The API has changed as follows:
- NestedSetView is deleted. Its split, getDirect, and getTransitive
methods have been moved to NestedSet itself, since they have
always been well defined by the core abstraction.
getDirect is now getLeaves and getTransitive is getNonLeaves.
- NestedSetView.identifier is gone. Instead, NestedSet.Node is a
truly opaque identifier for a node in the graph's internal
representation. It provides only the hash and equals operations.
(It might seem more logical for getLeaves/NonLeaves to be defined
over Nodes, returning Nodes, but in practice no client seems
to need that.)
- NestedSet.getChildrenUnsafe is replaced by forEachElement,
which provides the pruned traversal needed by [redacted;
see b/157992832]. Unfortunately it still
exposes the internal node to the 'prune' callback, violating
encapsulation, though it is much less invasive than before.
Functionally, this method could be completely replaced
by NestedSetVisitor or by use of Node, but performance may
be a concern. Will address in a follow-up.
- Delete childrenToString.
- The public API no longer mentions "children".
Also, delete rawChildren() and expose NestedSet.children to the package.
This is a preparatory cleanup for CL 310551947, which will
represent the depth of the graph in the graph, obviating the
problem of set flattening throwing unchecked exceptions at
surprising times, the catching of which creates a bad dependency
from the Starlark interpreter to NestedSet.
PiperOrigin-RevId: 315079199
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java
index 90b0f88..83c2397 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetImplTest.java
@@ -68,9 +68,6 @@
NestedSet<String> linkOrderSet =
NestedSetBuilder.<String>linkOrder().add("a").addTransitive(b).addTransitive(c).build();
assertThat(linkOrderSet.toString()).isEqualTo("[a, b2, b1, c2, c1]");
- // Stable order when printing children directly.
- assertThat(NestedSet.childrenToString(linkOrderSet.getChildren()))
- .isEqualTo("[c1, c2, b1, b2, a]");
assertThat(nestedSetBuilder().addTransitive(b).build().toString()).isEqualTo("[b1, b2]");
}
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetTopologyTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetTopologyTest.java
new file mode 100644
index 0000000..5846eb8
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetTopologyTest.java
@@ -0,0 +1,180 @@
+// Copyright 2017 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.nestedset;
+
+import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.assertThrows;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests of NestedSet topology methods: toNode, getNonLeaves, getLeaves. */
+@RunWith(JUnit4.class)
+public class NestedSetTopologyTest {
+
+ @Test
+ public void testToNode() {
+ NestedSet<String> inner = NestedSetBuilder.<String>stableOrder().add("a").add("b").build();
+ NestedSet<String> outer =
+ NestedSetBuilder.<String>stableOrder().addTransitive(inner).add("c").build();
+ NestedSet<String> flat =
+ NestedSetBuilder.<String>stableOrder().add("a").add("b").add("c").build();
+
+ assertThat(inner.toNode()).isEqualTo(inner.toNode());
+
+ // Sets with different internal structure should have different nodes
+ assertThat(flat.toNode()).isNotEqualTo(outer.toNode());
+
+ // Decomposing a set, the transitive sets should be correctly identified.
+ List<NestedSet<String>> succs = outer.getNonLeaves();
+ assertThat(succs).hasSize(1);
+ NestedSet<String> succ0 = succs.get(0);
+ assertThat(succ0.toNode()).isEqualTo(inner.toNode());
+ }
+
+ @Test
+ public void testGetLeaves() {
+ NestedSet<String> inner = NestedSetBuilder.<String>stableOrder().add("a").add("b").build();
+ NestedSet<String> outer =
+ NestedSetBuilder.<String>stableOrder()
+ .add("c")
+ .addTransitive(inner)
+ .add("d")
+ .add("e")
+ .build();
+
+ // The direct members should correctly be identified.
+ assertThat(outer.getLeaves()).containsExactly("c", "d", "e");
+ }
+
+ @Test
+ public void testGetNonLeaves() {
+ // The inner sets must have at least two elements, as NestedSet inlines singleton sets.
+ NestedSet<String> innerA = NestedSetBuilder.<String>stableOrder().add("a1").add("a2").build();
+ NestedSet<String> innerB = NestedSetBuilder.<String>stableOrder().add("b1").add("b2").build();
+ NestedSet<String> innerC = NestedSetBuilder.<String>stableOrder().add("c1").add("c2").build();
+ NestedSet<String> outer =
+ NestedSetBuilder.<String>stableOrder()
+ .add("x")
+ .add("y")
+ .addTransitive(innerA)
+ .addTransitive(innerB)
+ .addTransitive(innerC)
+ .add("z")
+ .build();
+
+ // Decomposing the nested set should give us the correct list of transitive members.
+ // Compare using strings as NestedSet.equals uses identity.
+ assertThat(outer.getNonLeaves().toString())
+ .isEqualTo(ImmutableList.of(innerA, innerB, innerC).toString());
+ }
+
+ /** Naively traverse a view and collect all elements reachable. */
+ private static ImmutableSet<String> contents(NestedSet<String> set) {
+ ImmutableSet.Builder<String> builder = new ImmutableSet.Builder<String>();
+ builder.addAll(set.getLeaves());
+ for (NestedSet<String> nonleaf : set.getNonLeaves()) {
+ builder.addAll(contents(nonleaf));
+ }
+ return builder.build();
+ }
+
+ private static ImmutableSet<Object> nodes(Collection<NestedSet<String>> sets) {
+ ImmutableSet.Builder<Object> builder = new ImmutableSet.Builder<Object>();
+ for (NestedSet<String> set : sets) {
+ builder.add(set.toNode());
+ }
+ return builder.build();
+ }
+
+ @Test
+ public void testContents() {
+ // Verify that the elements reachable from view are the correct ones, regardless if singletons
+ // are inlined or not. Also verify that sets with at least two elements are never inlined.
+ NestedSet<String> singleA = NestedSetBuilder.<String>stableOrder().add("a").build();
+ NestedSet<String> singleB = NestedSetBuilder.<String>stableOrder().add("b").build();
+ NestedSet<String> multi = NestedSetBuilder.<String>stableOrder().add("c1").add("c2").build();
+ NestedSet<String> outer =
+ NestedSetBuilder.<String>stableOrder()
+ .add("x")
+ .add("y")
+ .addTransitive(multi)
+ .addTransitive(singleA)
+ .addTransitive(singleB)
+ .add("z")
+ .build();
+
+ assertThat(contents(outer)).containsExactly("a", "b", "c1", "c2", "x", "y", "z");
+ assertThat(nodes(outer.getNonLeaves())).contains(multi.toNode());
+ }
+
+ @Test
+ public void testSplitFails() {
+ NestedSet<String> a = NestedSetBuilder.<String>stableOrder().add("a").add("b").build();
+ assertThrows(IllegalArgumentException.class, () -> a.splitIfExceedsMaximumSize(-100));
+ assertThrows(IllegalArgumentException.class, () -> a.splitIfExceedsMaximumSize(1));
+ }
+
+ @Test
+ public void testSplitNoSplit() {
+ NestedSet<String> a = NestedSetBuilder.<String>stableOrder().add("a").add("b").build();
+ assertThat(a.splitIfExceedsMaximumSize(2)).isSameInstanceAs(a);
+ assertThat(a.splitIfExceedsMaximumSize(100)).isSameInstanceAs(a);
+ }
+
+ @Test
+ public void testSplit() {
+ NestedSet<String> a =
+ NestedSetBuilder.<String>stableOrder()
+ .addAll(Arrays.asList("a", "b", "c"))
+ .build();
+ NestedSet<String> v = a;
+ NestedSet<String> s = v.splitIfExceedsMaximumSize(2);
+ assertThat(s).isNotSameInstanceAs(v);
+ assertThat(collectCheckSize(s, 2)).containsExactly("a", "b", "c");
+ }
+
+ @Test
+ public void testRecursiveSplit() {
+ NestedSet<String> a =
+ NestedSetBuilder.<String>stableOrder()
+ .addAll(Arrays.asList("a", "b", "c", "d", "e"))
+ .build();
+ NestedSet<String> v = a;
+ NestedSet<String> s = v.splitIfExceedsMaximumSize(2);
+ assertThat(s).isNotSameInstanceAs(v);
+ assertThat(collectCheckSize(s, 2)).containsExactly("a", "b", "c", "d", "e");
+ }
+
+ private static <T> List<T> collectCheckSize(NestedSet<T> set, int maxSize) {
+ return collectCheckSize(new ArrayList<>(), set, maxSize);
+ }
+
+ private static <T> List<T> collectCheckSize(List<T> result, NestedSet<T> set, int maxSize) {
+ assertThat(set.getLeaves().size()).isAtMost(maxSize);
+ assertThat(set.getNonLeaves().size()).isAtMost(maxSize);
+ for (NestedSet<T> nonleaf : set.getNonLeaves()) {
+ collectCheckSize(result, nonleaf, maxSize);
+ }
+ result.addAll(set.getLeaves());
+ return result;
+ }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetViewTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetViewTest.java
deleted file mode 100644
index 8ff8741..0000000
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/NestedSetViewTest.java
+++ /dev/null
@@ -1,194 +0,0 @@
-// Copyright 2017 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.nestedset;
-
-import static com.google.common.truth.Truth.assertThat;
-import static org.junit.Assert.assertThrows;
-
-import com.google.common.collect.ImmutableSet;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.List;
-import java.util.Set;
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-
-/** Tests for {@link com.google.devtools.build.lib.collect.nestedset.NestedSetView}. */
-@RunWith(JUnit4.class)
-public class NestedSetViewTest {
-
- @Test
- public void testIdentifier() {
- NestedSet<String> inner = NestedSetBuilder.<String>stableOrder().add("a").add("b").build();
- NestedSet<String> outer =
- NestedSetBuilder.<String>stableOrder().addTransitive(inner).add("c").build();
- NestedSet<String> flat =
- NestedSetBuilder.<String>stableOrder().add("a").add("b").add("c").build();
-
- // The identifier should be independent of the view instance.
- assertThat(new NestedSetView<String>(inner).identifier())
- .isEqualTo(new NestedSetView<String>(inner).identifier());
-
- // Sets with different internal structure should have different identifiers
- assertThat(new NestedSetView<String>(flat).identifier())
- .isNotEqualTo(new NestedSetView<String>(outer).identifier());
-
- // Decomposing a set, the transitive sets should be correctly identified.
- Set<NestedSetView<String>> transitives = new NestedSetView<String>(outer).transitives();
- assertThat(transitives).hasSize(1);
- NestedSetView<String> extracted = transitives.iterator().next();
- assertThat(extracted.identifier()).isEqualTo(new NestedSetView<String>(inner).identifier());
- }
-
- @Test
- public void testDirects() {
- NestedSet<String> inner = NestedSetBuilder.<String>stableOrder().add("a").add("b").build();
- NestedSet<String> outer =
- NestedSetBuilder.<String>stableOrder()
- .add("c")
- .addTransitive(inner)
- .add("d")
- .add("e")
- .build();
-
- // The direct members should correctly be identified.
- assertThat(new NestedSetView<String>(outer).directs()).containsExactly("c", "d", "e");
- }
-
- @Test
- public void testTransitives() {
- // The inner sets have to have at least two elements, as NestedSet may decide to inline
- // singleton sets; however, we do not want to assert the inlining in the test.
- NestedSet<String> innerA = NestedSetBuilder.<String>stableOrder().add("a1").add("a2").build();
- NestedSet<String> innerB = NestedSetBuilder.<String>stableOrder().add("b1").add("b2").build();
- NestedSet<String> innerC = NestedSetBuilder.<String>stableOrder().add("c1").add("c2").build();
- NestedSet<String> outer =
- NestedSetBuilder.<String>stableOrder()
- .add("x")
- .add("y")
- .addTransitive(innerA)
- .addTransitive(innerB)
- .addTransitive(innerC)
- .add("z")
- .build();
-
- // Decomposing the nested set, should give us the correct set of transitive members.
- ImmutableSet<Object> expected =
- ImmutableSet.of(
- new NestedSetView<String>(innerA).identifier(),
- new NestedSetView<String>(innerB).identifier(),
- new NestedSetView<String>(innerC).identifier());
- ImmutableSet.Builder<Object> found = new ImmutableSet.Builder<Object>();
- for (NestedSetView<String> transitive : new NestedSetView<String>(outer).transitives()) {
- found.add(transitive.identifier());
- }
- assertThat(found.build()).isEqualTo(expected);
- }
-
- /** Naively traverse a view and collect all elements reachable. */
- private static Set<String> contents(NestedSetView<String> view) {
- ImmutableSet.Builder<String> builder = new ImmutableSet.Builder<String>();
- builder.addAll(view.directs());
- for (NestedSetView<String> transitive : view.transitives()) {
- builder.addAll(contents(transitive));
- }
- return builder.build();
- }
-
- private static Set<Object> identifiers(Set<NestedSetView<String>> sets) {
- ImmutableSet.Builder<Object> builder = new ImmutableSet.Builder<Object>();
- for (NestedSetView<String> set : sets) {
- builder.add(set.identifier());
- }
- return builder.build();
- }
-
- @Test
- public void testContents() {
- // Verify that the elements reachable from view are the correct ones, regardless if singletons
- // are inlined or not. Also verify that sets with at least two elements are never inlined.
- NestedSet<String> singleA = NestedSetBuilder.<String>stableOrder().add("a").build();
- NestedSet<String> singleB = NestedSetBuilder.<String>stableOrder().add("b").build();
- NestedSet<String> multi = NestedSetBuilder.<String>stableOrder().add("c1").add("c2").build();
- NestedSet<String> outer =
- NestedSetBuilder.<String>stableOrder()
- .add("x")
- .add("y")
- .addTransitive(multi)
- .addTransitive(singleA)
- .addTransitive(singleB)
- .add("z")
- .build();
-
- NestedSetView<String> view = new NestedSetView<String>(outer);
- assertThat(contents(view)).containsExactly("a", "b", "c1", "c2", "x", "y", "z");
- assertThat(identifiers(view.transitives()))
- .contains(new NestedSetView<String>(multi).identifier());
- }
-
- @Test
- public void testSplitFails() {
- NestedSet<String> a = NestedSetBuilder.<String>stableOrder().add("a").add("b").build();
- NestedSetView<String> v = new NestedSetView<>(a);
- assertThrows(IllegalArgumentException.class, () -> v.splitIfExceedsMaximumSize(-100));
- assertThrows(IllegalArgumentException.class, () -> v.splitIfExceedsMaximumSize(1));
- }
-
- @Test
- public void testSplitNoSplit() {
- NestedSet<String> a = NestedSetBuilder.<String>stableOrder().add("a").add("b").build();
- NestedSetView<String> v = new NestedSetView<>(a);
- assertThat(v.splitIfExceedsMaximumSize(2)).isSameInstanceAs(v);
- assertThat(v.splitIfExceedsMaximumSize(100)).isSameInstanceAs(v);
- }
-
- @Test
- public void testSplit() {
- NestedSet<String> a =
- NestedSetBuilder.<String>stableOrder()
- .addAll(Arrays.asList("a", "b", "c"))
- .build();
- NestedSetView<String> v = new NestedSetView<>(a);
- NestedSetView<String> s = v.splitIfExceedsMaximumSize(2);
- assertThat(s).isNotSameInstanceAs(v);
- assertThat(collectCheckSize(s, 2)).containsExactly("a", "b", "c");
- }
-
- @Test
- public void testRecursiveSplit() {
- NestedSet<String> a =
- NestedSetBuilder.<String>stableOrder()
- .addAll(Arrays.asList("a", "b", "c", "d", "e"))
- .build();
- NestedSetView<String> v = new NestedSetView<>(a);
- NestedSetView<String> s = v.splitIfExceedsMaximumSize(2);
- assertThat(s).isNotSameInstanceAs(v);
- assertThat(collectCheckSize(s, 2)).containsExactly("a", "b", "c", "d", "e");
- }
-
- private <T> List<T> collectCheckSize(NestedSetView<T> view, int maxSize) {
- return collectCheckSize(new ArrayList<>(), view, maxSize);
- }
-
- private <T> List<T> collectCheckSize(List<T> result, NestedSetView<T> view, int maxSize) {
- assertThat(view.directs().size()).isAtMost(maxSize);
- assertThat(view.transitives().size()).isAtMost(maxSize);
- for (NestedSetView<T> t : view.transitives()) {
- collectCheckSize(result, t, maxSize);
- }
- result.addAll(view.directs());
- return result;
- }
-}
diff --git a/src/test/java/com/google/devtools/build/lib/runtime/BuildEventStreamerTest.java b/src/test/java/com/google/devtools/build/lib/runtime/BuildEventStreamerTest.java
index 12e29b7..de31ed7 100644
--- a/src/test/java/com/google/devtools/build/lib/runtime/BuildEventStreamerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/runtime/BuildEventStreamerTest.java
@@ -67,7 +67,6 @@
import com.google.devtools.build.lib.buildtool.buildevent.NoAnalyzeEvent;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetView;
import com.google.devtools.build.lib.server.FailureDetails.FailureDetail;
import com.google.devtools.build.lib.server.FailureDetails.Spawn;
import com.google.devtools.build.lib.server.FailureDetails.Spawn.Code;
@@ -278,10 +277,7 @@
BuildEventStreamProtos.NamedSetOfFiles.Builder builder =
BuildEventStreamProtos.NamedSetOfFiles.newBuilder();
for (NestedSet<Artifact> artifactset : artifacts) {
- builder.addFileSets(
- converters
- .artifactGroupNamer()
- .apply((new NestedSetView<Artifact>(artifactset)).identifier()));
+ builder.addFileSets(converters.artifactGroupNamer().apply(artifactset.toNode()));
}
return GenericBuildEvent.protoChaining(this).setNamedSetOfFiles(builder.build()).build();
}
diff --git a/src/test/java/com/google/devtools/build/lib/starlarkdebug/server/DebuggerSerializationTest.java b/src/test/java/com/google/devtools/build/lib/starlarkdebug/server/DebuggerSerializationTest.java
index 74fc489..adca3ae 100644
--- a/src/test/java/com/google/devtools/build/lib/starlarkdebug/server/DebuggerSerializationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/starlarkdebug/server/DebuggerSerializationTest.java
@@ -22,7 +22,6 @@
import com.google.devtools.build.lib.collect.nestedset.Depset;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetView;
import com.google.devtools.build.lib.starlarkdebugging.StarlarkDebuggingProtos.Value;
import com.google.devtools.build.lib.syntax.Printer;
import com.google.devtools.build.lib.syntax.Starlark;
@@ -112,8 +111,7 @@
assertEqualIgnoringTypeDescriptionAndId(
childValues.get(1), getValueProto("directs", directChildren));
assertEqualIgnoringTypeDescriptionAndId(
- childValues.get(2),
- getValueProto("transitives", ImmutableList.of(new NestedSetView<>(innerNestedSet))));
+ childValues.get(2), getValueProto("transitives", ImmutableList.of(innerNestedSet)));
}
@Test
@@ -267,10 +265,7 @@
assertThat(value.getDescription()).isEqualTo(Starlark.repr(object));
}
- /**
- * Type, description, and ID are implementation dependent (e.g. NestedSetView#directs returns a
- * list instead of a set if there are no duplicates, which changes both 'type' and 'description').
- */
+ // Type, description, and ID are implementation dependent.
private void assertEqualIgnoringTypeDescriptionAndId(Value value1, Value value2) {
assertThat(value1.getLabel()).isEqualTo(value2.getLabel());
