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());