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/main/java/com/google/devtools/build/lib/analysis/AspectCompleteEvent.java b/src/main/java/com/google/devtools/build/lib/analysis/AspectCompleteEvent.java
index 3d42896..80cb378 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/AspectCompleteEvent.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/AspectCompleteEvent.java
@@ -31,7 +31,6 @@
import com.google.devtools.build.lib.causes.Cause;
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.collect.nestedset.Order;
import com.google.devtools.build.skyframe.SkyValue;
import java.util.Collection;
@@ -146,9 +145,7 @@
for (ArtifactsInOutputGroup artifactsInGroup : artifactOutputGroups.toList()) {
OutputGroup.Builder groupBuilder = OutputGroup.newBuilder();
groupBuilder.setName(artifactsInGroup.getOutputGroup());
- groupBuilder.addFileSets(
- namer.apply(
- (new NestedSetView<Artifact>(artifactsInGroup.getArtifacts())).identifier()));
+ groupBuilder.addFileSets(namer.apply(artifactsInGroup.getArtifacts().toNode()));
builder.addOutputGroup(groupBuilder.build());
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/TargetCompleteEvent.java b/src/main/java/com/google/devtools/build/lib/analysis/TargetCompleteEvent.java
index 0a04ec5..ce2e8f5 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/TargetCompleteEvent.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/TargetCompleteEvent.java
@@ -48,7 +48,6 @@
import com.google.devtools.build.lib.cmdline.Label;
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.collect.nestedset.Order;
import com.google.devtools.build.lib.packages.AttributeMap;
import com.google.devtools.build.lib.packages.ConfiguredAttributeMapper;
@@ -465,18 +464,14 @@
}
OutputGroup.Builder groupBuilder = OutputGroup.newBuilder();
groupBuilder.setName(artifactsInOutputGroup.getOutputGroup());
- groupBuilder.addFileSets(
- namer.apply(
- (new NestedSetView<Artifact>(artifactsInOutputGroup.getArtifacts())).identifier()));
+ groupBuilder.addFileSets(namer.apply(artifactsInOutputGroup.getArtifacts().toNode()));
groups.add(groupBuilder.build());
}
if (baselineCoverageArtifacts != null) {
groups.add(
OutputGroup.newBuilder()
.setName(BASELINE_COVERAGE)
- .addFileSets(
- namer.apply(
- (new NestedSetView<Artifact>(baselineCoverageArtifacts).identifier())))
+ .addFileSets(namer.apply(baselineCoverageArtifacts.toNode()))
.build());
}
return groups.build();
diff --git a/src/main/java/com/google/devtools/build/lib/buildeventstream/ArtifactGroupNamer.java b/src/main/java/com/google/devtools/build/lib/buildeventstream/ArtifactGroupNamer.java
index c68442e..00a732f 100644
--- a/src/main/java/com/google/devtools/build/lib/buildeventstream/ArtifactGroupNamer.java
+++ b/src/main/java/com/google/devtools/build/lib/buildeventstream/ArtifactGroupNamer.java
@@ -13,15 +13,17 @@
// limitations under the License.
package com.google.devtools.build.lib.buildeventstream;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
+
/** Interface for conversion of paths to URIs. */
// TODO(lpino): This interface shouldn't exist since there's only trivial implementation of it.
// However, it's really hard to move this class to the right package because of package boundaries.
public interface ArtifactGroupNamer {
/**
- * Return the name of a declared group of artifacts, identified by the identifier of their {@link
- * NestedSetView}. A {@link BuildEvent} should only assume that this function is defined if the
- * corresponding {@link NestedSet<Artifact>} is declared via the {@link EventReportingArtifacts}
- * interface. On undefined positions, the value null is returned.
+ * Return the name of a NestedSet of artifacts, identified by its Node. A {@link BuildEvent}
+ * should only assume that this function is defined if the corresponding {@link
+ * NestedSet<Artifact>} is declared via the {@link EventReportingArtifacts} interface. On
+ * undefined positions, the value null is returned.
*/
- BuildEventStreamProtos.BuildEventId.NamedSetOfFilesId apply(Object id);
+ BuildEventStreamProtos.BuildEventId.NamedSetOfFilesId apply(NestedSet.Node node);
}
diff --git a/src/main/java/com/google/devtools/build/lib/buildeventstream/BUILD b/src/main/java/com/google/devtools/build/lib/buildeventstream/BUILD
index 909dc34..cc0ffd8 100644
--- a/src/main/java/com/google/devtools/build/lib/buildeventstream/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/buildeventstream/BUILD
@@ -18,6 +18,7 @@
deps = [
"//src/main/java/com/google/devtools/build/lib/buildeventstream/proto:build_event_stream_java_proto",
"//src/main/java/com/google/devtools/build/lib/cmdline",
+ "//src/main/java/com/google/devtools/build/lib/collect/nestedset",
"//src/main/java/com/google/devtools/build/lib/events",
"//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
"//src/main/java/com/google/devtools/build/lib/util",
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/BUILD b/src/main/java/com/google/devtools/build/lib/collect/nestedset/BUILD
index 690de2f..77109dc 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/BUILD
@@ -19,7 +19,6 @@
"NestedSetCodecWithStore.java",
"NestedSetExpander.java",
"NestedSetStore.java",
- "NestedSetView.java",
"NestedSetVisitor.java",
"Order.java",
],
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
index 2e5918d..217b5f8 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
@@ -37,10 +37,33 @@
import java.util.concurrent.TimeUnit;
import java.util.concurrent.TimeoutException;
import java.util.concurrent.atomic.AtomicInteger;
+import java.util.function.Consumer;
+import java.util.function.Predicate;
import javax.annotation.Nullable;
/**
- * A list-like iterable that supports efficient nesting.
+ * A NestedSet is an immutable ordered set of element values of type {@code E}. Elements must not be
+ * arrays.
+ *
+ * <p>Conceptually, NestedSet values form a directed acyclic graph (DAG). Each leaf node represents
+ * a set containing a single element; there is also a distinguished leaf node representing the empty
+ * set. Each non-leaf node represents the union of the sets represented by its successors.
+ *
+ * <p>A NestedSet value represents a node in this graph. The elements of a NestedSet may be
+ * enumerated by traversing the complete DAG, eliminating duplicates using an ephemeral hash table.
+ * The {@link #toList} and {@link #toSet} methods provide the result of this traversal as a list or
+ * a set, respectively. These operations, which are relatively expensive, are known as "flattening".
+ * Computing the size of the set requires flattening.
+ *
+ * <p>By contrast, construction of a new set as a union of existing sets is relatively cheap. The
+ * constructor accepts a list of "direct" elements and list of "transitive" nodes. The resulting
+ * NestedSet refers to a new graph node representing their union. The relative order of direct and
+ * transitive successors is governed by the Order parameter. Duplicates among the "direct" elements
+ * are eliminated at construction, again with an ephemeral hash table. If after duplicate
+ * elimination the new node would have exactly one successor, whether "direct" or "transitive", the
+ * resulting NestedSet reuses the existing node for the sole successor.
+ *
+ * <p>The implementation has been highly optimized as it is crucial to Blaze's performance.
*
* @see NestedSetBuilder
*/
@@ -56,7 +79,20 @@
*/
private int orderAndSize;
- private final Object children;
+ // children contains the "direct" elements and "transitive" nested sets.
+ // Direct elements are never arrays.
+ // Transitive elements may be arrays, but singletons are replaced by their sole element
+ // (thus transitive arrays always contain at least two logical elements).
+ // The relative order of direct and transitive is determined by the Order.
+ // All empty sets have children==EMPTY_CHILDREN, not null.
+ //
+ // Please be careful to use the terms of the conceptual model in the API documentation,
+ // and the terms of the physical representation in internal comments. They are not the same.
+ //
+ // TODO(adonovan): rename this field and related accessors to something less suggestive,
+ // such as 'state' or 'repr' or 'node'. The public API no longer mentions "children".
+ final Object children;
+
@Nullable private byte[] memo;
/**
@@ -171,7 +207,10 @@
private NestedSet(Order order, Object children, @Nullable byte[] memo) {
this.orderAndSize = order.ordinal();
- this.children = children;
+ this.children =
+ children instanceof Object[] && ((Object[]) children).length == 0
+ ? EMPTY_CHILDREN
+ : children;
this.memo = memo;
}
@@ -202,8 +241,7 @@
/**
* Returns the internal item or array. If the internal item is a deserialization future, blocks on
- * completion. For external use only by NestedSetVisitor and NestedSetView. Those two classes also
- * have knowledge of the internal implementation of NestedSet.
+ * completion. For use only by NestedSetVisitor.
*/
Object getChildren() {
return getChildrenUninterruptibly();
@@ -259,18 +297,34 @@
}
/**
- * Public version of {@link #getChildren}.
+ * forEachElement applies function {@code f} to each element of the NestedSet.
*
- * <p>Strongly prefer {@link NestedSetVisitor}. Internal representation subject to change without
- * notice.
+ * <p>The {@code descend} function is called for each node in the DAG, and if it returns false,
+ * the traversal is pruned and does not descend into that node; if the node was a leaf, {@code f}
+ * is not called.
+ *
+ * <p>Clients must treat the {@code descend} function's argument as an opaque reference: only
+ * {@link System#identityHashCode} and {@code ==} should be applied to it.
*/
- public Object getChildrenUnsafe() {
- return getChildren();
+ // TODO(b/157992832): this function is an encapsulation-breaking hack for the function named in
+ // the bug report. Eliminate it, and make it use NestedSetVisitor instead.
+ public void forEachElement(Predicate<Object> descend, Consumer<E> f) {
+ forEachElementImpl(descend, f, getChildren());
}
- /** Returns the internal item, array, or future. */
- Object rawChildren() {
- return children;
+ private static <E> void forEachElementImpl(
+ Predicate<Object> descend, Consumer<E> f, Object node) {
+ if (descend.test(node)) {
+ if (node instanceof Object[]) {
+ for (Object child : (Object[]) node) {
+ forEachElementImpl(descend, f, child);
+ }
+ } else {
+ @SuppressWarnings("unchecked")
+ E elem = (E) node;
+ f.accept(elem);
+ }
+ }
}
/** Returns true if the set is empty. Runs in O(1) time (i.e. does not flatten the set). */
@@ -412,11 +466,11 @@
return other != null
&& getOrder() == other.getOrder()
- && (rawChildren().equals(other.rawChildren())
+ && (children.equals(other.children)
|| (!isSingleton()
&& !other.isSingleton()
- && rawChildren() instanceof Object[]
- && other.rawChildren() instanceof Object[]
+ && children instanceof Object[]
+ && other.children instanceof Object[]
&& Arrays.equals((Object[]) children, (Object[]) other.children)));
}
@@ -439,39 +493,19 @@
@Override
public String toString() {
- String specialCase = specialCaseChildrenToString(children);
- return specialCase != null ? specialCase : nestedSetToString(this);
- }
-
- /** Returned string iterates over {@code children} in {@link Order#STABLE_ORDER}. */
- public static String childrenToString(Object children) {
- String specialCase = specialCaseChildrenToString(children);
- return specialCase != null
- ? specialCase
- : nestedSetToString(new NestedSet<>(Order.STABLE_ORDER, children, null));
- }
-
- @Nullable
- private static String specialCaseChildrenToString(Object children) {
if (isSingleton(children)) {
return "[" + children + "]";
}
- if (children instanceof Future) {
- if (!((Future<Object[]>) children).isDone()) {
- return "Deserializing NestedSet with future: " + children;
- }
+ if (children instanceof Future && !((Future<Object[]>) children).isDone()) {
+ return "Deserializing NestedSet with future: " + children;
}
- return null;
- }
-
- private static String nestedSetToString(NestedSet<?> nestedSet) {
- ImmutableList<?> expandedList = nestedSet.toList();
- if (expandedList.size() <= MAX_ELEMENTS_TO_STRING) {
- return expandedList.toString();
+ ImmutableList<?> elems = toList();
+ if (elems.size() <= MAX_ELEMENTS_TO_STRING) {
+ return elems.toString();
}
- return expandedList.subList(0, MAX_ELEMENTS_TO_STRING)
+ return elems.subList(0, MAX_ELEMENTS_TO_STRING)
+ " (truncated, full size "
- + expandedList.size()
+ + elems.size()
+ ")";
}
@@ -641,4 +675,108 @@
return depthLimit;
}
}
+
+ /**
+ * Returns a new NestedSet containing the same elements, but represented using a logical graph
+ * with the specified maximum out-degree, which must be at least 2. The resulting set's iteration
+ * order is undefined.
+ */
+ public NestedSet<E> splitIfExceedsMaximumSize(int maximumSize) {
+ Preconditions.checkArgument(maximumSize >= 2, "maximumSize must be at least 2");
+ Object children = getChildren(); // may wait for a future
+ if (!(children instanceof Object[])) {
+ return this;
+ }
+ Object[] arr = (Object[]) children;
+ int size = arr.length;
+ if (size <= maximumSize) {
+ return this;
+ }
+ Object[][] pieces = new Object[((size + maximumSize - 1) / maximumSize)][];
+ for (int i = 0; i < pieces.length; i++) {
+ int max = Math.min((i + 1) * maximumSize, arr.length);
+ pieces[i] = Arrays.copyOfRange(arr, i * maximumSize, max);
+ }
+
+ // TODO(adonovan): why is this recursive call here? It looks like it is intended to propagate
+ // the split down to each subgraph, but it clearly never did that, because it would have to be
+ // applied to each element of pieces[i]. More surprising is that it does anything at all: pieces
+ // has already been split. Yet a test breaks if it is removed. Investigate and simplify.
+ return new NestedSet<E>(getOrder(), pieces, null).splitIfExceedsMaximumSize(maximumSize);
+ }
+
+ /** Returns the list of this node's successors that are themselves non-leaf nodes. */
+ public ImmutableList<NestedSet<E>> getNonLeaves() {
+ Object children = getChildren(); // may wait for a future
+ if (!(children instanceof Object[])) {
+ return ImmutableList.of();
+ }
+ ImmutableList.Builder<NestedSet<E>> res = ImmutableList.builder();
+ for (Object c : (Object[]) children) {
+ if (c instanceof Object[]) {
+ res.add(new NestedSet<>(getOrder(), c, null));
+ }
+ }
+ return res.build();
+ }
+
+ /**
+ * Returns the list of elements (leaf nodes) of this set that are reached by following at most one
+ * graph edge.
+ */
+ @SuppressWarnings("unchecked")
+ public ImmutableList<E> getLeaves() {
+ Object children = getChildren(); // may wait for a future
+ if (!(children instanceof Object[])) {
+ return ImmutableList.of((E) children);
+ }
+ ImmutableList.Builder<E> res = ImmutableList.builder();
+ for (Object c : (Object[]) children) {
+ if (!(c instanceof Object[])) {
+ res.add((E) c);
+ }
+ }
+ return res.build();
+ }
+
+ /**
+ * Returns a Node, an opaque reference to the logical node of the DAG that this NestedSet
+ * represents.
+ */
+ public Node toNode() {
+ return new Node(children);
+ }
+
+ /**
+ * A Node is an opaque reference to a logical node of the NestedSet DAG.
+ *
+ * <p>The only operation it supports is {@link Object#equals}. Branch nodes are equal if and only
+ * if they refer to the same logical graph node. Leaf nodes are equal if they refer to equal
+ * elements. Two distinct NestedSets may have equal elements.
+ *
+ * <p>Node is provided so that clients can implement their own traversals and detect when they
+ * have encountered a subgraph already visited.
+ */
+ public static class Node {
+ private final Object children;
+
+ private Node(Object children) {
+ this.children = children;
+ }
+
+ @Override
+ public int hashCode() {
+ return children.hashCode();
+ }
+
+ @Override
+ public boolean equals(Object that) {
+ return that instanceof Node && this.children.equals(((Node) that).children);
+ }
+
+ @Override
+ public String toString() {
+ return "NestedSet.Node@" + hashCode(); // intentionally opaque
+ }
+ }
}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java
index a98f936..444db9d 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java
@@ -152,19 +152,19 @@
@Override
public int hashCode() {
int childrenHashCode;
- if (nestedSet.rawChildren() instanceof ListenableFuture
- && ((ListenableFuture) nestedSet.rawChildren()).isDone()) {
+ if (nestedSet.children instanceof ListenableFuture
+ && ((ListenableFuture) nestedSet.children).isDone()) {
try {
- childrenHashCode = Futures.getDone((ListenableFuture) nestedSet.rawChildren()).hashCode();
+ childrenHashCode = Futures.getDone((ListenableFuture) nestedSet.children).hashCode();
} catch (ExecutionException e) {
// If the future failed, we can treat it as unequal to all non-future NestedSet instances
// (using the hashCode of the Future object) and hide the exception until the NestedSet is
// truly needed (i.e. unrolled). Note that NestedSetStore already attaches a listener to
// this future that sends a bug report if it fails.
- childrenHashCode = nestedSet.rawChildren().hashCode();
+ childrenHashCode = nestedSet.children.hashCode();
}
} else {
- childrenHashCode = nestedSet.rawChildren().hashCode();
+ childrenHashCode = nestedSet.children.hashCode();
}
return 37 * nestedSet.getOrder().hashCode() + childrenHashCode;
@@ -196,21 +196,19 @@
// Both sets contain Object[] or both sets contain ListenableFuture<Object[]>
NestedSet<?> thatSet = ((EqualsWrapper) obj).nestedSet;
if (this.nestedSet.getOrder().equals(thatSet.getOrder())
- && this.nestedSet.rawChildren().equals(thatSet.rawChildren())) {
+ && this.nestedSet.children.equals(thatSet.children)) {
return true;
}
// One set contains Object[], while the other contains ListenableFuture<Object[]>
- if (this.nestedSet.rawChildren() instanceof ListenableFuture
- && thatSet.rawChildren() instanceof Object[]) {
+ if (this.nestedSet.children instanceof ListenableFuture
+ && thatSet.children instanceof Object[]) {
return deserializingAndMaterializedSetsAreEqual(
- (Object[]) thatSet.rawChildren(),
- (ListenableFuture<Object[]>) this.nestedSet.rawChildren());
- } else if (thatSet.rawChildren() instanceof ListenableFuture
- && this.nestedSet.rawChildren() instanceof Object[]) {
+ (Object[]) thatSet.children, (ListenableFuture<Object[]>) this.nestedSet.children);
+ } else if (thatSet.children instanceof ListenableFuture
+ && this.nestedSet.children instanceof Object[]) {
return deserializingAndMaterializedSetsAreEqual(
- (Object[]) this.nestedSet.rawChildren(),
- (ListenableFuture<Object[]>) thatSet.rawChildren());
+ (Object[]) this.nestedSet.children, (ListenableFuture<Object[]>) thatSet.children);
} else {
return false;
}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java
deleted file mode 100644
index 216817a..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java
+++ /dev/null
@@ -1,131 +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 com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableSet;
-import java.util.Arrays;
-import java.util.Set;
-
-/**
- * Class presenting the logical structure of a {@link NestedSet}.
- *
- * <p>The main use case for this class are situations were a larger number of related nested sets
- * needs to be serialized in an efficient way, as is the case when reporting artifacts in the build
- * event protocol.
- *
- * <p>Note that a {@link NestedSet} does not preserve all structure provided to the {@link
- * NestedSetBuilder}; in fact, it may decide to inline the contents of small nested sets as direct
- * members. This view class provides a view on the structure that is still present in a {@link
- * NestedSet}. As there is a fixed limit on the size a transitive member can have to still be
- * eligible for inlining, this is enough to allow an efficient deduplicated presentation.
- */
-public class NestedSetView<E> {
- private final Object set;
-
- public NestedSetView(Object set) {
- this.set = set;
- }
-
- /** Construct a view of a given NestedSet. */
- public NestedSetView(NestedSet<E> set) {
- this(set.getChildren());
- }
-
- public static <E> Object getRawChildren(NestedSet<E> set) {
- return set.getChildren();
- }
-
- /**
- * Splits the current view into multiple views if the number of entries in the current set exceeds
- * the given limit, which has to be at least 2. This method guarantees that the resulting view
- * contains the same elements (direct and transitive) overall, and that each node's size is less
- * than or equal to the given limit. It makes no guarantees about the resulting structure of the
- * graph, and this may affect the traversal order if it is converted back to a nested set.
- */
- public NestedSetView<E> splitIfExceedsMaximumSize(int maximumSize) {
- Preconditions.checkArgument(maximumSize >= 2, "maximumSize must be at least 2");
- if (!(set instanceof Object[])) {
- return this;
- }
- Object[] arr = (Object[]) set;
- int size = arr.length;
- if (size <= maximumSize) {
- return this;
- }
- Object[][] pieces = new Object[((size + maximumSize - 1) / maximumSize)][];
- for (int i = 0; i < pieces.length; i++) {
- int max = Math.min((i + 1) * maximumSize, arr.length);
- pieces[i] = Arrays.copyOfRange(arr, i * maximumSize, max);
- }
- return new NestedSetView<E>(pieces).splitIfExceedsMaximumSize(maximumSize);
- }
-
- /**
- * Return an object where the {@link #equals} method provides the correct notion of (intensional)
- * equality of the set viewed. Consumers of this method should not assume any properties of the
- * returned object apart from its {@link #equals} method.
- *
- * <p>The identifier is meant as an abstract, but memory efficient way of remembering nested sets
- * directly or indirectly seen. Storing the identifier of a nested-set view will not retain more
- * memory than storing the underlying nested set; in particular, it will not prevent the view
- * object from being garbage collected.
- *
- * <p>The equality of the view itself is the one inherited from Object, i.e., you can have many
- * views of the same set that are not equal as views.
- */
- public Object identifier() {
- return set;
- }
-
- /**
- * Return the set of transitive members.
- *
- * <p>This refers to the transitive members after any inlining that might have happened at
- * construction of the nested set.
- */
- public Set<NestedSetView<E>> transitives() {
- if (!(set instanceof Object[])) {
- return ImmutableSet.of();
- }
- ImmutableSet.Builder<NestedSetView<E>> nestedSetViewSetBuilder = new ImmutableSet.Builder<>();
- for (Object c : (Object[]) set) {
- if (c instanceof Object[]) {
- nestedSetViewSetBuilder.add(new NestedSetView<>(c));
- }
- }
- return nestedSetViewSetBuilder.build();
- }
-
- /**
- * Return the set of direct members.
- *
- * <p>This refers to the direct members after any inlining that might have happened at
- * construction of the nested set.
- */
- @SuppressWarnings("unchecked")
- public Set<E> directs() {
- if (!(set instanceof Object[])) {
- return ImmutableSet.of((E) set);
- }
- ImmutableSet.Builder<E> setBuilder = new ImmutableSet.Builder<>();
- for (Object c : (Object[]) set) {
- if (!(c instanceof Object[])) {
- setBuilder.add((E) c);
- }
- }
- return setBuilder.build();
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/BuildEventStreamer.java b/src/main/java/com/google/devtools/build/lib/runtime/BuildEventStreamer.java
index 092e132..11cb44b 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/BuildEventStreamer.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/BuildEventStreamer.java
@@ -29,6 +29,7 @@
import com.google.common.eventbus.Subscribe;
import com.google.common.util.concurrent.ListenableFuture;
import com.google.devtools.build.lib.actions.ActionExecutedEvent;
+import com.google.devtools.build.lib.actions.Artifact;
import com.google.devtools.build.lib.actions.BuildConfigurationEvent;
import com.google.devtools.build.lib.actions.CompletionContext;
import com.google.devtools.build.lib.actions.EventReportingArtifacts;
@@ -58,7 +59,6 @@
import com.google.devtools.build.lib.buildtool.buildevent.NoAnalyzeEvent;
import com.google.devtools.build.lib.buildtool.buildevent.NoExecutionEvent;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetView;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
import com.google.devtools.build.lib.pkgcache.TargetParsingCompleteEvent;
@@ -370,12 +370,12 @@
halfCloseFuturesMap = halfCloseFuturesMapBuilder.build();
}
- private void maybeReportArtifactSet(CompletionContext ctx, NestedSetView<?> view) {
- String name = artifactGroupNamer.maybeName(view);
+ private void maybeReportArtifactSet(CompletionContext ctx, NestedSet<?> set) {
+ String name = artifactGroupNamer.maybeName(set);
if (name == null) {
return;
}
- view = NamedArtifactGroup.expandView(ctx, view);
+ set = NamedArtifactGroup.expandSet(ctx, set);
// We only split if the max number of entries is at least 2 (it must be at least a binary tree).
// The method throws for smaller values.
@@ -383,16 +383,12 @@
// We only split the event after naming it to avoid splitting the same node multiple times.
// Note that the artifactGroupNames keeps references to the individual pieces, so this can
// double the memory consumption of large nested sets.
- view = view.splitIfExceedsMaximumSize(besOptions.maxNamedSetEntries);
+ set = set.splitIfExceedsMaximumSize(besOptions.maxNamedSetEntries);
}
- for (NestedSetView<?> transitive : view.transitives()) {
- maybeReportArtifactSet(ctx, transitive);
+ for (NestedSet<?> succ : set.getNonLeaves()) {
+ maybeReportArtifactSet(ctx, succ);
}
- post(new NamedArtifactGroup(name, ctx, view));
- }
-
- private void maybeReportArtifactSet(CompletionContext ctx, NestedSet<?> set) {
- maybeReportArtifactSet(ctx, new NestedSetView<>(set));
+ post(new NamedArtifactGroup(name, ctx, set));
}
private void maybeReportConfiguration(BuildEvent configuration) {
@@ -427,7 +423,6 @@
@Subscribe
@AllowConcurrentEvents
- @SuppressWarnings("unchecked")
public void buildEvent(BuildEvent event) {
if (finalEventsToCome != null) {
synchronized (this) {
@@ -458,9 +453,8 @@
if (event instanceof EventReportingArtifacts) {
ReportedArtifacts reportedArtifacts = ((EventReportingArtifacts) event).reportedArtifacts();
- for (NestedSet<?> artifactSet : reportedArtifacts.artifacts) {
- maybeReportArtifactSet(
- reportedArtifacts.completionContext, (NestedSet<Object>) artifactSet);
+ for (NestedSet<Artifact> artifactSet : reportedArtifacts.artifacts) {
+ maybeReportArtifactSet(reportedArtifacts.completionContext, artifactSet);
}
}
@@ -806,4 +800,3 @@
}
}
}
-
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/CountingArtifactGroupNamer.java b/src/main/java/com/google/devtools/build/lib/runtime/CountingArtifactGroupNamer.java
index ef07bf8..c68d5e2 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/CountingArtifactGroupNamer.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/CountingArtifactGroupNamer.java
@@ -15,26 +15,22 @@
import com.google.devtools.build.lib.buildeventstream.ArtifactGroupNamer;
import com.google.devtools.build.lib.buildeventstream.BuildEventStreamProtos.BuildEventId.NamedSetOfFilesId;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetView;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import java.util.HashMap;
import java.util.Map;
-import javax.annotation.concurrent.GuardedBy;
import javax.annotation.concurrent.ThreadSafe;
/** Conversion of paths to URIs. */
@ThreadSafe
public class CountingArtifactGroupNamer implements ArtifactGroupNamer {
- @GuardedBy("this")
- private final Map<Object, Long> reportedArtifactNames = new HashMap<>();
- @GuardedBy("this")
- private long nextArtifactName;
+ private final Map<NestedSet.Node, Integer> nodeNames = new HashMap<>();
@Override
- public NamedSetOfFilesId apply(Object id) {
- Long name;
+ public NamedSetOfFilesId apply(NestedSet.Node id) {
+ Integer name;
synchronized (this) {
- name = reportedArtifactNames.get(id);
+ name = nodeNames.get(id);
}
if (name == null) {
return null;
@@ -43,16 +39,15 @@
}
/**
- * If the {@link NestedSetView} has no name already, return a new name for it. Return null
- * otherwise.
+ * If the {@link NestedSet} has no name already, return a new name for it. Return null otherwise.
*/
- public synchronized String maybeName(NestedSetView<?> view) {
- if (reportedArtifactNames.containsKey(view.identifier())) {
+ public synchronized String maybeName(NestedSet<?> set) {
+ NestedSet.Node id = set.toNode();
+ if (nodeNames.containsKey(id)) {
return null;
}
- Long name = nextArtifactName;
- nextArtifactName++;
- reportedArtifactNames.put(view.identifier(), name);
+ Integer name = nodeNames.size();
+ nodeNames.put(id, name);
return name.toString();
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/NamedArtifactGroup.java b/src/main/java/com/google/devtools/build/lib/runtime/NamedArtifactGroup.java
index ad03ceb..5f90065 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/NamedArtifactGroup.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/NamedArtifactGroup.java
@@ -30,11 +30,12 @@
import com.google.devtools.build.lib.buildeventstream.BuildEventStreamProtos.BuildEventId;
import com.google.devtools.build.lib.buildeventstream.GenericBuildEvent;
import com.google.devtools.build.lib.buildeventstream.PathConverter;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetView;
+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.Order;
import com.google.devtools.build.lib.vfs.Path;
import com.google.devtools.build.lib.vfs.PathFragment;
import java.util.Collection;
-import java.util.Set;
import javax.annotation.Nullable;
/**
@@ -45,16 +46,16 @@
class NamedArtifactGroup implements BuildEvent {
private final String name;
private final CompletionContext completionContext;
- private final NestedSetView<?> view;
+ private final NestedSet<?> set; // of Artifact or ExpandedArtifact
/**
- * Create a {@link NamedArtifactGroup}. The view may contain as direct entries {@link Artifact} or
+ * Create a {@link NamedArtifactGroup}. The set may contain as direct entries {@link Artifact} or
* {@link ExpandedArtifact}.
*/
- NamedArtifactGroup(String name, CompletionContext completionContext, NestedSetView<?> view) {
+ NamedArtifactGroup(String name, CompletionContext completionContext, NestedSet<?> set) {
this.name = name;
this.completionContext = completionContext;
- this.view = view;
+ this.set = set;
}
@Override
@@ -70,8 +71,8 @@
@Override
public Collection<LocalFile> referencedLocalFiles() {
ImmutableList.Builder<LocalFile> artifacts = ImmutableList.builder();
- for (Object o : view.directs()) {
- ExpandedArtifact expandedArtifact = (ExpandedArtifact) o;
+ for (Object elem : set.getLeaves()) {
+ ExpandedArtifact expandedArtifact = (ExpandedArtifact) elem;
if (expandedArtifact.relPath == null) {
artifacts.add(
new LocalFile(
@@ -94,8 +95,8 @@
BuildEventStreamProtos.NamedSetOfFiles.Builder builder =
BuildEventStreamProtos.NamedSetOfFiles.newBuilder();
- for (Object o : view.directs()) {
- ExpandedArtifact expandedArtifact = (ExpandedArtifact) o;
+ for (Object elem : set.getLeaves()) {
+ ExpandedArtifact expandedArtifact = (ExpandedArtifact) elem;
if (expandedArtifact.relPath == null) {
String uri =
pathConverter.apply(completionContext.pathResolver().toPath(expandedArtifact.artifact));
@@ -116,53 +117,45 @@
}
}
- for (NestedSetView<?> child : view.transitives()) {
- builder.addFileSets(namer.apply(child.identifier()));
+ for (NestedSet<?> succ : set.getNonLeaves()) {
+ builder.addFileSets(namer.apply(succ.toNode()));
}
return GenericBuildEvent.protoChaining(this).setNamedSetOfFiles(builder.build()).build();
}
/**
- * Given a view with direct entries of {@link Artifact} and {@link ExpandedArtifact}, return a
- * transformed view with any {@link Artifact} expanded to a set of {@link ExpandedArtifact}.
+ * Given a set whose leaf successors are {@link Artifact} and {@link ExpandedArtifact}, returns a
+ * weird Frankenstein object with each leaf successor replaced by ExpandedArtifact. Non-leaf
+ * successors are unaltered.
*/
- static NestedSetView<Object> expandView(CompletionContext ctx, NestedSetView<?> artifacts) {
- ImmutableList.Builder<ExpandedArtifact> expandedArtifacts = ImmutableList.builder();
- for (Object artifact : artifacts.directs()) {
+ static NestedSet<?> expandSet(CompletionContext ctx, NestedSet<?> artifacts) {
+ NestedSetBuilder<Object> res = new NestedSetBuilder<>(Order.STABLE_ORDER);
+ for (Object artifact : artifacts.getLeaves()) {
if (artifact instanceof ExpandedArtifact) {
- expandedArtifacts.add((ExpandedArtifact) artifact);
+ res.add(artifact);
} else if (artifact instanceof Artifact) {
ctx.visitArtifacts(
ImmutableList.of((Artifact) artifact),
new ArtifactReceiver() {
@Override
public void accept(Artifact artifact) {
- expandedArtifacts.add(new ExpandedArtifact(artifact, null, null));
+ res.add(new ExpandedArtifact(artifact, null, null));
}
@Override
public void acceptFilesetMapping(
Artifact fileset, PathFragment relName, Path targetFile) {
- expandedArtifacts.add(new ExpandedArtifact(fileset, relName, targetFile));
+ res.add(new ExpandedArtifact(fileset, relName, targetFile));
}
});
} else {
- throw new IllegalStateException("Unexpected type in artifact view: " + artifact);
+ throw new IllegalStateException("Unexpected type in artifact set: " + artifact);
}
}
- ImmutableList<ExpandedArtifact> expandedDirects = expandedArtifacts.build();
-
- Set<? extends NestedSetView<?>> transitives = artifacts.transitives();
- Object[] directAndTransitiveArtifacts = new Object[expandedDirects.size() + transitives.size()];
- int i = 0;
- for (ExpandedArtifact a : expandedDirects) {
- directAndTransitiveArtifacts[i++] = a;
+ for (NestedSet<?> succ : artifacts.getNonLeaves()) {
+ res.addTransitive(succ);
}
- for (NestedSetView<?> t : transitives) {
- directAndTransitiveArtifacts[i++] = t.identifier();
- }
-
- return new NestedSetView<>(directAndTransitiveArtifacts);
+ return res.build();
}
private static final class ExpandedArtifact {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
index d8bc97ef..c4e2eb0 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ActionExecutionFunction.java
@@ -61,7 +61,6 @@
import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
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.collect.nestedset.Order;
import com.google.devtools.build.lib.events.ExtendedEventHandler;
import com.google.devtools.build.lib.profiler.Profiler;
@@ -358,13 +357,12 @@
// - It's uncommon that 2 actions share the exact same set of inputs
// => the top layer offers little in terms of reusability.
// More details: b/143205147.
- NestedSetView<Artifact> nestedSetView = new NestedSetView<>(allInputs);
- Iterable<SkyKey> directKeys = Artifact.keys(nestedSetView.directs());
+ Iterable<SkyKey> directKeys = Artifact.keys(allInputs.getLeaves());
if (state.requestedArtifactNestedSetKeys == null) {
state.requestedArtifactNestedSetKeys = CompactHashSet.create();
- for (NestedSetView<Artifact> transitive : nestedSetView.transitives()) {
+ for (NestedSet<Artifact> nonleaf : allInputs.getNonLeaves()) {
state.requestedArtifactNestedSetKeys.add(
- new ArtifactNestedSetKey(transitive.identifier()));
+ new ArtifactNestedSetKey(nonleaf, nonleaf.toNode()));
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactNestedSetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactNestedSetFunction.java
index be9eb65..bfe2936 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactNestedSetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactNestedSetFunction.java
@@ -18,6 +18,7 @@
import com.google.common.collect.MapMaker;
import com.google.common.collect.Maps;
import com.google.devtools.build.lib.actions.ActionExecutionException;
+import com.google.devtools.build.lib.actions.Artifact;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
import com.google.devtools.build.lib.util.Pair;
@@ -27,6 +28,7 @@
import com.google.devtools.build.skyframe.SkyValue;
import com.google.devtools.build.skyframe.ValueOrException3;
import java.io.IOException;
+import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentMap;
@@ -101,10 +103,11 @@
* Maps the NestedSets' underlying objects to the corresponding SkyKey. This is to avoid
* re-creating SkyKey for the same nested set upon reevaluation because of e.g. a missing value.
*
- * <p>The map has weak references to keys to prevent memory leaks: if a nested set no longer
- * exists, its entry would be automatically removed from the map by the GC.
+ * <p>The map weakly references its values: when the ArtifactNestedSetKey becomes otherwise
+ * unreachable, the map entry is collected.
*/
- private final ConcurrentMap<Object, SkyKey> nestedSetToSkyKey;
+ private final ConcurrentMap<NestedSet.Node, ArtifactNestedSetKey>
+ nestedSetToSkyKey; // note: weak values!
private static ArtifactNestedSetFunction singleton = null;
@@ -115,7 +118,7 @@
private ArtifactNestedSetFunction() {
artifactSkyKeyToSkyValue = Maps.newConcurrentMap();
artifactSkyKeyToValueOrException = Maps.newConcurrentMap();
- nestedSetToSkyKey = new MapMaker().weakKeys().makeMap();
+ nestedSetToSkyKey = new MapMaker().weakValues().makeMap();
}
@Override
@@ -126,24 +129,25 @@
return evalDepsInOneGroup(skyKey, env);
}
- ArtifactNestedSetKey artifactNestedSetKey = (ArtifactNestedSetKey) skyKey;
+ ArtifactNestedSetKey key = (ArtifactNestedSetKey) skyKey;
Map<
SkyKey,
ValueOrException3<
IOException, ActionExecutionException, ArtifactNestedSetEvalException>>
directArtifactsEvalResult =
env.getValuesOrThrow(
- artifactNestedSetKey.directKeys(),
+ Iterables.transform(key.getSet().getLeaves(), Artifact::key),
IOException.class,
ActionExecutionException.class,
ArtifactNestedSetEvalException.class);
// Evaluate all children.
- List<Object> transitiveMembers = artifactNestedSetKey.transitiveMembers();
- List<SkyKey> transitiveKeys = Lists.newArrayListWithCapacity(transitiveMembers.size());
- for (Object transitiveMember : transitiveMembers) {
+ List<NestedSet<Artifact>> nonleaves = key.getSet().getNonLeaves();
+ List<SkyKey> transitiveKeys = Lists.newArrayListWithCapacity(nonleaves.size());
+ for (NestedSet<Artifact> nonleaf : nonleaves) {
transitiveKeys.add(
- nestedSetToSkyKey.computeIfAbsent(transitiveMember, ArtifactNestedSetKey::new));
+ nestedSetToSkyKey.computeIfAbsent(
+ nonleaf.toNode(), (node) -> new ArtifactNestedSetKey(nonleaf, node)));
}
env.getValues(transitiveKeys);
@@ -159,13 +163,15 @@
/** The main path with --experimental_nsos_eval_keys_as_one_group. */
private SkyValue evalDepsInOneGroup(SkyKey skyKey, Environment env)
throws InterruptedException, ArtifactNestedSetFunctionException {
- ArtifactNestedSetKey artifactNestedSetKey = (ArtifactNestedSetKey) skyKey;
- Iterable<SkyKey> directKeys = artifactNestedSetKey.directKeys();
- List<Object> transitiveMembers = artifactNestedSetKey.transitiveMembers();
- List<SkyKey> transitiveKeys = Lists.newArrayListWithCapacity(transitiveMembers.size());
- for (Object transitiveMember : transitiveMembers) {
- transitiveKeys.add(
- nestedSetToSkyKey.computeIfAbsent(transitiveMember, ArtifactNestedSetKey::new));
+ NestedSet<Artifact> set = ((ArtifactNestedSetKey) skyKey).getSet();
+ List<SkyKey> keys = new ArrayList<>();
+ for (Artifact file : set.getLeaves()) {
+ keys.add(Artifact.key(file));
+ }
+ for (NestedSet<Artifact> nonleaf : set.getNonLeaves()) {
+ keys.add(
+ nestedSetToSkyKey.computeIfAbsent(
+ nonleaf.toNode(), (node) -> new ArtifactNestedSetKey(nonleaf, node)));
}
Map<
SkyKey,
@@ -173,7 +179,7 @@
IOException, ActionExecutionException, ArtifactNestedSetEvalException>>
depsEvalResult =
env.getValuesOrThrow(
- Iterables.concat(directKeys, transitiveKeys),
+ keys,
IOException.class,
ActionExecutionException.class,
ArtifactNestedSetEvalException.class);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactNestedSetKey.java b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactNestedSetKey.java
index b2ed5b7..7a696ae 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactNestedSetKey.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ArtifactNestedSetKey.java
@@ -14,8 +14,6 @@
package com.google.devtools.build.lib.skyframe;
import com.google.common.base.MoreObjects;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
import com.google.devtools.build.lib.actions.Artifact;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import com.google.devtools.build.skyframe.SkyFunctionName;
@@ -23,93 +21,38 @@
/** SkyKey for {@code NestedSet<Artifact>}. */
final class ArtifactNestedSetKey implements SkyKey {
- private final Object rawChildren;
+
+ private final NestedSet<Artifact> set;
+ private final NestedSet.Node node;
@Override
public SkyFunctionName functionName() {
return SkyFunctions.ARTIFACT_NESTED_SET;
}
- /**
- * We use Object instead of NestedSet to store children as a measure to save memory, and to be
- * consistent with the implementation of NestedSet.
- *
- * @param rawChildren the underlying members of the nested set.
- */
- ArtifactNestedSetKey(Object rawChildren) {
- Preconditions.checkState(rawChildren instanceof Object[] || rawChildren instanceof Artifact);
- this.rawChildren = rawChildren;
+ ArtifactNestedSetKey(NestedSet<Artifact> set, NestedSet.Node node) {
+ this.set = set;
+ this.node = node;
+ }
+
+ /** Returns the set of artifacts that this key represents. */
+ public NestedSet<Artifact> getSet() {
+ return set;
}
@Override
public int hashCode() {
- return rawChildren.hashCode();
+ return node.hashCode();
}
@Override
public boolean equals(Object that) {
- if (this == that) {
- return true;
- }
-
- if (!(that instanceof ArtifactNestedSetKey)) {
- return false;
- }
-
- Object theirRawChildren = ((ArtifactNestedSetKey) that).rawChildren;
- if (rawChildren == theirRawChildren) {
- return true;
- }
-
- if (rawChildren instanceof Artifact && theirRawChildren instanceof Artifact) {
- return rawChildren.equals(theirRawChildren);
- }
-
- return false;
+ return that instanceof ArtifactNestedSetKey
+ && this.node.equals(((ArtifactNestedSetKey) that).node);
}
@Override
public String toString() {
- return MoreObjects.toStringHelper(this)
- .add("rawChildren", NestedSet.childrenToString(rawChildren))
- .toString();
- }
-
- /**
- * Return the set of transitive members.
- *
- * <p>This refers to the transitive members after any inlining that might have happened at
- * construction of the nested set.
- */
- ImmutableList<Object> transitiveMembers() {
- if (!(rawChildren instanceof Object[])) {
- return ImmutableList.of();
- }
- ImmutableList.Builder<Object> listBuilder = new ImmutableList.Builder<>();
- for (Object c : (Object[]) rawChildren) {
- if (c instanceof Object[]) {
- listBuilder.add(c);
- }
- }
- return listBuilder.build();
- }
-
- /**
- * Return the set of direct members.
- *
- * <p>This refers to the direct members after any inlining that might have happened at
- * construction of the nested set.
- */
- ImmutableList<SkyKey> directKeys() {
- if (!(rawChildren instanceof Object[])) {
- return ImmutableList.of(Artifact.key((Artifact) rawChildren));
- }
- ImmutableList.Builder<SkyKey> listBuilder = new ImmutableList.Builder<>();
- for (Object c : (Object[]) rawChildren) {
- if (!(c instanceof Object[])) {
- listBuilder.add(Artifact.key((Artifact) c));
- }
- }
- return listBuilder.build();
+ return MoreObjects.toStringHelper(this).add("rawChildren", set).toString();
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/ActionGraphDump.java b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/ActionGraphDump.java
index 8a7bed6..8ddff93 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/ActionGraphDump.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/ActionGraphDump.java
@@ -34,7 +34,6 @@
import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget;
import com.google.devtools.build.lib.buildeventstream.BuildEvent;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetView;
import com.google.devtools.build.lib.packages.AspectDescriptor;
import com.google.devtools.build.lib.query2.aquery.AqueryActionFilter;
import com.google.devtools.build.lib.query2.aquery.AqueryUtils;
@@ -225,10 +224,8 @@
if (includeArtifacts) {
// Store inputs
NestedSet<Artifact> inputs = action.getInputs();
- NestedSetView<Artifact> nestedSetView = new NestedSetView<>(inputs);
-
- if (nestedSetView.directs().size() > 0 || nestedSetView.transitives().size() > 0) {
- actionBuilder.addInputDepSetIds(knownNestedSets.dataToId(nestedSetView));
+ if (!inputs.isEmpty()) {
+ actionBuilder.addInputDepSetIds(knownNestedSets.dataToId(inputs));
}
// store outputs
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/KnownNestedSets.java b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/KnownNestedSets.java
index 73bbfc2..b6e33a7 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/KnownNestedSets.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/KnownNestedSets.java
@@ -16,7 +16,7 @@
import com.google.devtools.build.lib.actions.Artifact;
import com.google.devtools.build.lib.analysis.AnalysisProtos;
import com.google.devtools.build.lib.analysis.AnalysisProtos.ActionGraphContainer;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetView;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
/**
* Cache for NestedSets in the action graph.
@@ -30,24 +30,21 @@
}
@Override
- protected Object transformToKey(Object nestedSetViewObject) {
- NestedSetView<?> nestedSetView = (NestedSetView<?>) nestedSetViewObject;
- // The NestedSet is identified by their raw 'children' object since multiple NestedSetViews
- // can point to the same object.
- return nestedSetView.identifier();
+ protected Object transformToKey(Object nestedSet) {
+ return ((NestedSet) nestedSet).toNode();
}
@Override
- AnalysisProtos.DepSetOfFiles createProto(Object nestedSetViewObject, String id) {
- NestedSetView<?> nestedSetView = (NestedSetView) nestedSetViewObject;
+ AnalysisProtos.DepSetOfFiles createProto(Object nestedSetObject, String id) {
+ NestedSet<?> nestedSet = (NestedSet) nestedSetObject;
AnalysisProtos.DepSetOfFiles.Builder depSetBuilder = AnalysisProtos.DepSetOfFiles
.newBuilder()
.setId(id);
- for (NestedSetView<?> transitiveNestedSet : nestedSetView.transitives()) {
- depSetBuilder.addTransitiveDepSetIds(this.dataToId(transitiveNestedSet));
+ for (NestedSet<?> succ : nestedSet.getNonLeaves()) {
+ depSetBuilder.addTransitiveDepSetIds(this.dataToId(succ));
}
- for (Object directArtifact : nestedSetView.directs()) {
- depSetBuilder.addDirectArtifactIds(knownArtifacts.dataToId((Artifact) directArtifact));
+ for (Object elem : nestedSet.getLeaves()) {
+ depSetBuilder.addDirectArtifactIds(knownArtifacts.dataToId((Artifact) elem));
}
return depSetBuilder.build();
}
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/ActionGraphDump.java b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/ActionGraphDump.java
index 4aefaae..204b525 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/ActionGraphDump.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/ActionGraphDump.java
@@ -33,7 +33,6 @@
import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget;
import com.google.devtools.build.lib.buildeventstream.BuildEvent;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetView;
import com.google.devtools.build.lib.packages.AspectDescriptor;
import com.google.devtools.build.lib.query2.aquery.AqueryActionFilter;
import com.google.devtools.build.lib.query2.aquery.AqueryUtils;
@@ -218,11 +217,8 @@
if (includeArtifacts) {
// Store inputs
NestedSet<Artifact> inputs = action.getInputs();
- NestedSetView<Artifact> nestedSetView = new NestedSetView<>(inputs);
-
- if (!nestedSetView.directs().isEmpty() || !nestedSetView.transitives().isEmpty()) {
- actionBuilder.addInputDepSetIds(
- knownNestedSets.dataToIdAndStreamOutputProto(nestedSetView));
+ if (!inputs.isEmpty()) {
+ actionBuilder.addInputDepSetIds(knownNestedSets.dataToIdAndStreamOutputProto(inputs));
}
// store outputs
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/KnownNestedSets.java b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/KnownNestedSets.java
index 990131c..411db0f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/KnownNestedSets.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/KnownNestedSets.java
@@ -15,7 +15,7 @@
import com.google.devtools.build.lib.actions.Artifact;
import com.google.devtools.build.lib.analysis.AnalysisProtosV2.DepSetOfFiles;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetView;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import java.io.IOException;
/** Cache for NestedSets in the action graph. */
@@ -28,23 +28,20 @@
}
@Override
- protected Object transformToKey(Object nestedSetViewObject) {
- NestedSetView<?> nestedSetView = (NestedSetView<?>) nestedSetViewObject;
- // The NestedSet is identified by their raw 'children' object since multiple NestedSetViews
- // can point to the same object.
- return nestedSetView.identifier();
+ protected Object transformToKey(Object nestedSet) {
+ return ((NestedSet) nestedSet).toNode();
}
@Override
- DepSetOfFiles createProto(Object nestedSetViewObject, int id) throws IOException {
- NestedSetView<?> nestedSetView = (NestedSetView) nestedSetViewObject;
+ DepSetOfFiles createProto(Object nestedSetObject, int id) throws IOException {
+ NestedSet<?> nestedSet = (NestedSet) nestedSetObject;
DepSetOfFiles.Builder depSetBuilder = DepSetOfFiles.newBuilder().setId(id);
- for (NestedSetView<?> transitiveNestedSet : nestedSetView.transitives()) {
- depSetBuilder.addTransitiveDepSetIds(this.dataToIdAndStreamOutputProto(transitiveNestedSet));
+ for (NestedSet<?> succ : nestedSet.getNonLeaves()) {
+ depSetBuilder.addTransitiveDepSetIds(this.dataToIdAndStreamOutputProto(succ));
}
- for (Object directArtifact : nestedSetView.directs()) {
+ for (Object elem : nestedSet.getLeaves()) {
depSetBuilder.addDirectArtifactIds(
- knownArtifacts.dataToIdAndStreamOutputProto((Artifact) directArtifact));
+ knownArtifacts.dataToIdAndStreamOutputProto((Artifact) elem));
}
return depSetBuilder.build();
}
diff --git a/src/main/java/com/google/devtools/build/lib/starlarkdebug/server/DebuggerSerialization.java b/src/main/java/com/google/devtools/build/lib/starlarkdebug/server/DebuggerSerialization.java
index a16f8c7..bb28d50 100644
--- a/src/main/java/com/google/devtools/build/lib/starlarkdebug/server/DebuggerSerialization.java
+++ b/src/main/java/com/google/devtools/build/lib/starlarkdebug/server/DebuggerSerialization.java
@@ -17,7 +17,7 @@
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Ordering;
import com.google.devtools.build.lib.collect.nestedset.Depset;
-import com.google.devtools.build.lib.collect.nestedset.NestedSetView;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import com.google.devtools.build.lib.starlarkdebugging.StarlarkDebuggingProtos;
import com.google.devtools.build.lib.starlarkdebugging.StarlarkDebuggingProtos.Value;
import com.google.devtools.build.lib.syntax.CallUtils;
@@ -57,7 +57,7 @@
if (value instanceof Depset) {
return true;
}
- if (value instanceof NestedSetView) {
+ if (value instanceof NestedSet) {
return true;
}
if (value instanceof Map) {
@@ -85,8 +85,8 @@
if (value instanceof Depset) {
return getChildren(objectMap, (Depset) value);
}
- if (value instanceof NestedSetView) {
- return getChildren(objectMap, (NestedSetView) value);
+ if (value instanceof NestedSet) {
+ return getChildren(objectMap, (NestedSet) value);
}
if (value instanceof Map) {
return getChildren(objectMap, ((Map) value).entrySet());
@@ -150,23 +150,23 @@
return children.build();
}
- private static ImmutableList<Value> getChildren(ThreadObjectMap objectMap, Depset nestedSet) {
+ private static ImmutableList<Value> getChildren(ThreadObjectMap objectMap, Depset depset) {
return ImmutableList.<Value>builder()
.add(
Value.newBuilder()
.setLabel("order")
.setType("Traversal order")
- .setDescription(nestedSet.getOrder().getStarlarkName())
+ .setDescription(depset.getOrder().getStarlarkName())
.build())
- .addAll(getChildren(objectMap, new NestedSetView<>(nestedSet.getSet())))
+ .addAll(getChildren(objectMap, depset.getSet()))
.build();
}
private static ImmutableList<Value> getChildren(
- ThreadObjectMap objectMap, NestedSetView<?> nestedSet) {
+ ThreadObjectMap objectMap, NestedSet<?> nestedSet) {
return ImmutableList.of(
- getValueProto(objectMap, "directs", nestedSet.directs()),
- getValueProto(objectMap, "transitives", nestedSet.transitives()));
+ getValueProto(objectMap, "directs", nestedSet.getLeaves()),
+ getValueProto(objectMap, "transitives", nestedSet.getNonLeaves()));
}
private static ImmutableList<Value> getChildren(
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());
