Description redacted.
--
MOS_MIGRATED_REVID=125013752
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
index 975c292..b3b8682 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
@@ -147,6 +147,7 @@
}
};
+ private final int hashCode;
private final Path path;
private final Root root;
private final PathFragment execPath;
@@ -180,6 +181,7 @@
throw new IllegalArgumentException(execPath + ": illegal execPath for " + path
+ " (root: " + root + ")");
}
+ this.hashCode = path.hashCode();
this.path = path;
this.root = root;
this.execPath = execPath;
@@ -572,7 +574,10 @@
@Override
public final int hashCode() {
- return path.hashCode();
+ // This is just path.hashCode(). We cache a copy in the Artifact object to reduce LLC misses
+ // during operations which build a HashSet out of many Artifacts. This is a slight loss for
+ // memory but saves ~1% overall CPU in some real builds.
+ return hashCode;
}
@Override
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/CompileOrderExpander.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/CompileOrderExpander.java
deleted file mode 100644
index aceebcc65..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/CompileOrderExpander.java
+++ /dev/null
@@ -1,48 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableCollection;
-
-/**
- * A nested set expander that implements left-to-right postordering.
- *
- * <p>For example, for the nested set {B, D, {A, C}}, the iteration order is "A C B D"
- * (child-first).
- *
- * <p>This type of set would typically be used for artifacts where elements of nested sets go before
- * the direct members of a set, for example in the case of Javascript dependencies.
- */
-final class CompileOrderExpander<E> implements NestedSetExpander<E> {
-
- // We suppress unchecked warning so that we can access the internal raw structure of the
- // NestedSet.
- @SuppressWarnings("unchecked")
- @Override
- public void expandInto(NestedSet<E> set, Uniqueifier uniqueifier,
- ImmutableCollection.Builder<E> builder) {
- for (NestedSet<E> subset : set.transitiveSets()) {
- if (!subset.isEmpty() && uniqueifier.isUnique(subset)) {
- expandInto(subset, uniqueifier, builder);
- }
- }
-
- // This switch is here to compress the memo used by the uniqueifier
- for (Object e : set.directMembers()) {
- if (uniqueifier.isUnique(e)) {
- builder.add((E) e);
- }
- }
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/CompileOrderNestedSetFactory.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/CompileOrderNestedSetFactory.java
deleted file mode 100644
index 382d54e..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/CompileOrderNestedSetFactory.java
+++ /dev/null
@@ -1,152 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableList;
-
-/**
- * Compile order {@code NestedSet} factory.
- */
-final class CompileOrderNestedSetFactory implements NestedSetFactory {
-
- @Override
- public <E> NestedSet<E> onlyDirects(Object[] directs) {
- return new CompileOnlyDirectsNestedSet<>(directs);
- }
-
- @Override
- public <E> NestedSet<E> onlyDirects(ImmutableList<E> directs) {
- return new CompileOrderImmutableListDirectsNestedSet<>(directs);
- }
-
- @Override
- public <E> NestedSet<E> oneDirectOneTransitive(E direct, NestedSet<E> transitive) {
- return new CompileOneDirectOneTransitiveNestedSet<>(direct, transitive);
- }
-
- @Override
- public <E> NestedSet<E> manyDirectsOneTransitive(Object[] direct,
- NestedSet<E> transitive) {
- return new CompileManyDirectOneTransitiveNestedSet<>(direct, transitive);
- }
-
- @Override
- public <E> NestedSet<E> onlyOneTransitive(NestedSet<E> transitive) {
- return new CompileOnlyOneTransitiveNestedSet<>(transitive);
- }
-
- @Override
- public <E> NestedSet<E> onlyManyTransitives(NestedSet[] transitives) {
- return new CompileOnlyTransitivesNestedSet<>(transitives);
- }
-
- @Override
- public <E> NestedSet<E> oneDirectManyTransitive(Object direct, NestedSet[] transitives) {
- return new CompileOneDirectManyTransitive<>(direct, transitives);
- }
-
- @Override
- public <E> NestedSet<E> manyDirectManyTransitive(Object[] directs, NestedSet[] transitives) {
- return new CompileManyDirectManyTransitive<>(directs, transitives);
- }
-
- @Override
- public <E> NestedSet<E> oneDirect(E element) {
- return new CompileSingleDirectNestedSet<>(element);
- }
-
- private static class CompileOnlyDirectsNestedSet<E> extends OnlyDirectsNestedSet<E> {
-
- CompileOnlyDirectsNestedSet(Object[] directs) { super(directs); }
-
- @Override
- public Order getOrder() { return Order.COMPILE_ORDER; }
- }
-
- private static class CompileOneDirectOneTransitiveNestedSet<E> extends
- OneDirectOneTransitiveNestedSet<E> {
-
- private CompileOneDirectOneTransitiveNestedSet(E direct, NestedSet<E> transitive) {
- super(direct, transitive);
- }
-
- @Override
- public Order getOrder() { return Order.COMPILE_ORDER; }
- }
-
- private static class CompileOneDirectManyTransitive<E> extends OneDirectManyTransitive<E> {
-
- private CompileOneDirectManyTransitive(Object direct, NestedSet[] transitive) {
- super(direct, transitive);
- }
-
- @Override
- public Order getOrder() { return Order.COMPILE_ORDER; }
- }
-
- private static class CompileManyDirectManyTransitive<E> extends ManyDirectManyTransitive<E> {
-
- private CompileManyDirectManyTransitive(Object[] directs, NestedSet[] transitives) {
- super(directs, transitives);
- }
-
- @Override
- public Order getOrder() { return Order.COMPILE_ORDER; }
- }
-
- private static class CompileOnlyOneTransitiveNestedSet<E> extends OnlyOneTransitiveNestedSet<E> {
-
- private CompileOnlyOneTransitiveNestedSet(NestedSet<E> transitive) { super(transitive); }
-
- @Override
- public Order getOrder() { return Order.COMPILE_ORDER; }
- }
-
- private static class CompileManyDirectOneTransitiveNestedSet<E> extends
- ManyDirectOneTransitiveNestedSet<E> {
-
- private CompileManyDirectOneTransitiveNestedSet(Object[] direct,
- NestedSet<E> transitive) { super(direct, transitive); }
-
- @Override
- public Order getOrder() { return Order.COMPILE_ORDER; }
- }
-
- private static class CompileOnlyTransitivesNestedSet<E> extends OnlyTransitivesNestedSet<E> {
-
- private CompileOnlyTransitivesNestedSet(NestedSet[] transitives) { super(transitives); }
-
- @Override
- public Order getOrder() { return Order.COMPILE_ORDER; }
- }
-
- private static class CompileOrderImmutableListDirectsNestedSet<E> extends
- ImmutableListDirectsNestedSet<E> {
-
- private CompileOrderImmutableListDirectsNestedSet(ImmutableList<E> directs) { super(directs); }
-
- @Override
- public Order getOrder() {
- return Order.COMPILE_ORDER;
- }
- }
-
- private static class CompileSingleDirectNestedSet<E> extends SingleDirectNestedSet<E> {
-
- private CompileSingleDirectNestedSet(E element) { super(element); }
-
- @Override
- public Order getOrder() { return Order.COMPILE_ORDER; }
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/EmptyNestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/EmptyNestedSet.java
deleted file mode 100644
index 5359a9f..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/EmptyNestedSet.java
+++ /dev/null
@@ -1,87 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
-
-import java.util.Iterator;
-import java.util.List;
-import java.util.Objects;
-import java.util.Set;
-
-import javax.annotation.Nullable;
-
-/**
- * An empty nested set.
- */
-final class EmptyNestedSet<E> extends NestedSet<E> {
- private static final NestedSet[] EMPTY_NESTED_SET = new NestedSet[0];
- private static final Object[] EMPTY_ELEMENTS = new Object[0];
- private final Order order;
-
- EmptyNestedSet(Order type) {
- this.order = type;
- }
-
- @Override
- public Iterator<E> iterator() {
- return ImmutableList.<E>of().iterator();
- }
-
- @Override
- Object[] directMembers() {
- return EMPTY_ELEMENTS;
- }
-
- @Override
- NestedSet[] transitiveSets() {
- return EMPTY_NESTED_SET;
- }
-
- @Override
- public boolean isEmpty() {
- return true;
- }
-
- @Override
- public List<E> toList() {
- return ImmutableList.of();
- }
-
- @Override
- public Set<E> toSet() {
- return ImmutableSet.of();
- }
-
- @Override
- public String toString() {
- return "{}";
- }
-
- @Override
- public Order getOrder() {
- return order;
- }
-
- @Override
- public boolean shallowEquals(@Nullable NestedSet<? extends E> other) {
- return other != null && getOrder() == other.getOrder() && other.isEmpty();
- }
-
- @Override
- public int shallowHashCode() {
- return Objects.hashCode(getOrder());
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/ImmutableListDirectsNestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/ImmutableListDirectsNestedSet.java
deleted file mode 100644
index 24454a7..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/ImmutableListDirectsNestedSet.java
+++ /dev/null
@@ -1,91 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
-
-import java.util.List;
-import java.util.Set;
-
-import javax.annotation.Nullable;
-
-/**
- * Memory-optimized NestedSet implementation for NestedSets without transitive dependencies that
- * allows us to share an ImmutableList.
- */
-abstract class ImmutableListDirectsNestedSet<E> extends NestedSet<E> {
-
- @SuppressWarnings("rawtypes")
- private static final NestedSet[] EMPTY = new NestedSet[0];
-
- private final ImmutableList<E> directDeps;
-
- public ImmutableListDirectsNestedSet(ImmutableList<E> directDeps) {
- this.directDeps = directDeps;
- }
-
- @Override
- public abstract Order getOrder();
-
- @Override
- Object[] directMembers() {
- return directDeps.toArray();
- }
-
- @SuppressWarnings({"cast", "unchecked"})
- @Override
- NestedSet<? extends E>[] transitiveSets() {
- return (NestedSet<? extends E>[]) EMPTY;
- }
-
- @Override
- public boolean isEmpty() {
- return directDeps.isEmpty();
- }
-
- /**
- * Currently all the Order implementations return the direct elements in the same order if they do
- * not have transitive elements. So we skip calling order.getExpander().
- */
- @SuppressWarnings("unchecked")
- @Override
- public List<E> toList() {
- return directDeps;
- }
-
- @SuppressWarnings("unchecked")
- @Override
- public Set<E> toSet() {
- return ImmutableSet.copyOf(directDeps);
- }
-
- @Override
- public boolean shallowEquals(@Nullable NestedSet<? extends E> other) {
- if (this == other) {
- return true;
- }
- if (other == null) {
- return false;
- }
- return getOrder().equals(other.getOrder())
- && other instanceof ImmutableListDirectsNestedSet
- && directDeps.equals(((ImmutableListDirectsNestedSet<? extends E>) other).directDeps);
- }
-
- @Override
- public int shallowHashCode() {
- return directDeps.hashCode();
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderExpander.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderExpander.java
deleted file mode 100644
index a4c1f3e..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderExpander.java
+++ /dev/null
@@ -1,105 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableCollection;
-import com.google.common.collect.ImmutableList;
-
-/**
- * A nested set expander that implements a variation of left-to-right preordering.
- *
- * <p>For example, for the nested set {A, C, {B, D}}, the iteration order is "A C B D"
- * (parent-first).
- *
- * <p>This type of set would typically be used for artifacts where elements of
- * nested sets go after the direct members of a set, for example when providing
- * a list of libraries to the C++ compiler.
- *
- * <p>The custom ordering has the property that elements of nested sets always come
- * before elements of descendant nested sets. Left-to-right order is preserved if
- * possible, both for items and for references to nested sets.
- *
- * <p>The left-to-right pre-order-like ordering is implemented by running a
- * right-to-left postorder traversal and then reversing the result.
- *
- * <p>The reason naive left-to left-to-right preordering is not used here is that
- * it does not handle diamond-like structures properly. For example, take the
- * following structure (nesting downwards):
- *
- * <pre>
- * A
- * / \
- * B C
- * \ /
- * D
- * </pre>
- *
- * <p>Naive preordering would produce "A B D C", which does not preserve the
- * "parent before child" property: C is a parent of D, so C should come before
- * D. Either "A B C D" or "A C B D" would be acceptable. This implementation
- * returns the first option of the two so that left-to-right order is preserved.
- *
- * <p>In case the nested sets form a tree, the ordering algorithm is equivalent to
- * standard left-to-right preorder.
- *
- * <p>Sometimes it may not be possible to preserve left-to-right order:
- *
- * <pre>
- * A
- * / \
- * B C
- * / \ / \
- * \ E /
- * \ /
- * \ /
- * D
- * </pre>
- *
- * <p>The left branch (B) would indicate "D E" ordering and the right branch (C)
- * dictates "E D". In such cases ordering is decided by the rightmost branch
- * because of the list reversing behind the scenes, so the ordering in the final
- * enumeration will be "E D".
- */
-
-final class LinkOrderExpander<E> implements NestedSetExpander<E> {
- @Override
- public void expandInto(NestedSet<E> nestedSet, Uniqueifier uniqueifier,
- ImmutableCollection.Builder<E> builder) {
- ImmutableList.Builder<E> result = ImmutableList.builder();
- internalEnumerate(nestedSet, uniqueifier, result);
- builder.addAll(result.build().reverse());
- }
-
- // We suppress unchecked warning so that we can access the internal raw structure of the
- // NestedSet.
- @SuppressWarnings("unchecked")
- private void internalEnumerate(NestedSet<E> set, Uniqueifier uniqueifier,
- ImmutableCollection.Builder<E> builder) {
- NestedSet[] transitiveSets = set.transitiveSets();
- for (int i = transitiveSets.length - 1; i >= 0; i--) {
- NestedSet<E> subset = transitiveSets[i];
- if (!subset.isEmpty() && uniqueifier.isUnique(subset)) {
- internalEnumerate(subset, uniqueifier, builder);
- }
- }
-
- Object[] directMembers = set.directMembers();
- for (int i = directMembers.length - 1; i >= 0; i--) {
- Object e = directMembers[i];
- if (uniqueifier.isUnique(e)) {
- builder.add((E) e);
- }
- }
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderNestedSetFactory.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderNestedSetFactory.java
deleted file mode 100644
index a6e78d0..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderNestedSetFactory.java
+++ /dev/null
@@ -1,152 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableList;
-
-/**
- * Link order {@code NestedSet} factory.
- */
-final class LinkOrderNestedSetFactory implements NestedSetFactory {
-
- @Override
- public <E> NestedSet<E> onlyDirects(Object[] directs) {
- return new LinkOnlyDirectsNestedSet<>(directs);
- }
-
- @Override
- public <E> NestedSet<E> onlyDirects(ImmutableList<E> directs) {
- return new LinkImmutableListDirectsNestedSet<>(directs);
- }
-
- @Override
- public <E> NestedSet<E> oneDirectOneTransitive(E direct, NestedSet<E> transitive) {
- return new LinkOneDirectOneTransitiveNestedSet<>(direct, transitive);
- }
-
- @Override
- public <E> NestedSet<E> manyDirectsOneTransitive(Object[] direct,
- NestedSet<E> transitive) {
- return new LinkManyDirectOneTransitiveNestedSet<>(direct, transitive);
- }
-
- @Override
- public <E> NestedSet<E> onlyOneTransitive(NestedSet<E> transitive) {
- return new LinkOnlyOneTransitiveNestedSet<>(transitive);
- }
-
- @Override
- public <E> NestedSet<E> onlyManyTransitives(NestedSet[] transitives) {
- return new LinkOnlyTransitivesNestedSet<>(transitives);
- }
-
- @Override
- public <E> NestedSet<E> oneDirectManyTransitive(Object direct, NestedSet[] transitives) {
- return new LinkOneDirectManyTransitive<>(direct, transitives);
- }
-
- @Override
- public <E> NestedSet<E> manyDirectManyTransitive(Object[] directs, NestedSet[] transitives) {
- return new LinkManyDirectManyTransitive<>(directs, transitives);
- }
-
- @Override
- public <E> NestedSet<E> oneDirect(E element) {
- return new LinkSingleDirectNestedSet<>(element);
- }
-
- private static class LinkOnlyDirectsNestedSet<E> extends OnlyDirectsNestedSet<E> {
-
- LinkOnlyDirectsNestedSet(Object[] directs) { super(directs); }
-
- @Override
- public Order getOrder() { return Order.LINK_ORDER; }
- }
-
- private static class LinkOneDirectOneTransitiveNestedSet<E> extends
- OneDirectOneTransitiveNestedSet<E> {
-
- private LinkOneDirectOneTransitiveNestedSet(E direct, NestedSet<E> transitive) {
- super(direct, transitive);
- }
-
- @Override
- public Order getOrder() { return Order.LINK_ORDER; }
- }
-
- private static class LinkOneDirectManyTransitive<E> extends OneDirectManyTransitive<E> {
-
- private LinkOneDirectManyTransitive(Object direct, NestedSet[] transitive) {
- super(direct, transitive);
- }
-
- @Override
- public Order getOrder() { return Order.LINK_ORDER; }
- }
-
- private static class LinkManyDirectManyTransitive<E> extends ManyDirectManyTransitive<E> {
-
- private LinkManyDirectManyTransitive(Object[] directs, NestedSet[] transitives) {
- super(directs, transitives);
- }
-
- @Override
- public Order getOrder() { return Order.LINK_ORDER; }
- }
-
- private static class LinkOnlyOneTransitiveNestedSet<E> extends OnlyOneTransitiveNestedSet<E> {
-
- private LinkOnlyOneTransitiveNestedSet(NestedSet<E> transitive) { super(transitive); }
-
- @Override
- public Order getOrder() { return Order.LINK_ORDER; }
- }
-
- private static class LinkManyDirectOneTransitiveNestedSet<E> extends
- ManyDirectOneTransitiveNestedSet<E> {
-
- private LinkManyDirectOneTransitiveNestedSet(Object[] direct,
- NestedSet<E> transitive) { super(direct, transitive); }
-
- @Override
- public Order getOrder() { return Order.LINK_ORDER; }
- }
-
- private static class LinkOnlyTransitivesNestedSet<E> extends OnlyTransitivesNestedSet<E> {
-
- private LinkOnlyTransitivesNestedSet(NestedSet[] transitives) { super(transitives); }
-
- @Override
- public Order getOrder() { return Order.LINK_ORDER; }
- }
-
- private static class LinkImmutableListDirectsNestedSet<E> extends
- ImmutableListDirectsNestedSet<E> {
-
- private LinkImmutableListDirectsNestedSet(ImmutableList<E> directs) { super(directs); }
-
- @Override
- public Order getOrder() {
- return Order.LINK_ORDER;
- }
- }
-
- private static class LinkSingleDirectNestedSet<E> extends SingleDirectNestedSet<E> {
-
- private LinkSingleDirectNestedSet(E element) { super(element); }
-
- @Override
- public Order getOrder() { return Order.LINK_ORDER; }
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/ManyDirectManyTransitive.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/ManyDirectManyTransitive.java
deleted file mode 100644
index e96b76b..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/ManyDirectManyTransitive.java
+++ /dev/null
@@ -1,63 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import java.util.Arrays;
-import java.util.Objects;
-
-import javax.annotation.Nullable;
-
-/**
- * NestedSet implementation that can have many direct elements and many transitive
- * {@code NestedSet}s.
- */
-abstract class ManyDirectManyTransitive<E> extends MemoizedUniquefierNestedSet<E> {
-
- private final Object[] directs;
- private final NestedSet[] transitives;
- private Object memo;
-
- ManyDirectManyTransitive(Object[] directs, NestedSet[] transitives) {
- this.directs = directs;
- this.transitives = transitives;
- }
-
- @Override
- Object getMemo() { return memo; }
-
- @Override
- void setMemo(Object memo) { this.memo = memo; }
-
- @Override
- Object[] directMembers() { return directs; }
-
- @Override
- NestedSet[] transitiveSets() { return transitives; }
-
- @Override
- public boolean shallowEquals(@Nullable NestedSet<? extends E> other) {
- if (this == other) {
- return true;
- }
- return other != null
- && getOrder().equals(other.getOrder())
- && other instanceof ManyDirectManyTransitive
- && Arrays.equals(directs, ((ManyDirectManyTransitive<? extends E>) other).directs)
- && Arrays.equals(transitives, ((ManyDirectManyTransitive<? extends E>) other).transitives);
- }
-
- @Override
- public int shallowHashCode() {
- return Objects.hash(getOrder(), Arrays.hashCode(directs), Arrays.hashCode(transitives)); }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/ManyDirectOneTransitiveNestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/ManyDirectOneTransitiveNestedSet.java
deleted file mode 100644
index a98edac..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/ManyDirectOneTransitiveNestedSet.java
+++ /dev/null
@@ -1,63 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import java.util.Arrays;
-import java.util.Objects;
-
-import javax.annotation.Nullable;
-
-/**
- * Memory-efficient implementation for the case where we have many direct elements and one
- * transitive NestedSet.
- */
-abstract class ManyDirectOneTransitiveNestedSet<E> extends MemoizedUniquefierNestedSet<E> {
-
- private final Object[] directs;
- private final NestedSet<E> transitive;
- private Object memo;
-
- public ManyDirectOneTransitiveNestedSet(Object[] directs, NestedSet<E> transitive) {
- this.directs = directs;
- this.transitive = transitive;
- }
-
- @Override
- Object getMemo() { return memo; }
-
- @Override
- void setMemo(Object memo) { this.memo = memo; }
-
- @Override
- Object[] directMembers() { return directs; }
-
- @Override
- NestedSet[] transitiveSets() { return new NestedSet[]{transitive}; }
-
- @Override
- public boolean shallowEquals(@Nullable NestedSet<? extends E> other) {
- if (this == other) {
- return true;
- }
- return other != null
- && getOrder().equals(other.getOrder())
- && other instanceof ManyDirectOneTransitiveNestedSet
- && Arrays.equals(directs, ((ManyDirectOneTransitiveNestedSet<? extends E>) other).directs)
- && transitive == ((ManyDirectOneTransitiveNestedSet<? extends E>) other).transitive;
- }
-
- @Override
- public int shallowHashCode() {
- return Objects.hash(getOrder(), Arrays.hashCode(directs), transitive); }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/MemoizedUniquefierNestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/MemoizedUniquefierNestedSet.java
deleted file mode 100644
index 5ef0cd6..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/MemoizedUniquefierNestedSet.java
+++ /dev/null
@@ -1,74 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableCollection;
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
-
-import java.util.List;
-import java.util.Set;
-
-/**
- * A NestedSet that keeps a memoized uniquifier so that it is faster to fill a set.
- *
- * <p>This class does not keep the memoized object itself so that we can take advantage of the
- * memory field alignment (Memory alignment does not put in the same structure the fields of a
- * class and its extensions).
- */
-public abstract class MemoizedUniquefierNestedSet<E> extends NestedSet<E> {
-
- @Override
- public List<E> toList() {
- ImmutableList.Builder<E> builder = new ImmutableList.Builder<>();
- memoizedFill(builder);
- return builder.build();
- }
-
- @Override
- public Set<E> toSet() {
- ImmutableSet.Builder<E> builder = new ImmutableSet.Builder<>();
- memoizedFill(builder);
- return builder.build();
- }
-
- /**
- * It does not make sense to have a {@code MemoizedUniquefierNestedSet} if it is empty.
- */
- @Override
- public boolean isEmpty() { return false; }
-
- abstract Object getMemo();
-
- abstract void setMemo(Object object);
-
- /**
- * Fill a collection builder by using a memoized {@code Uniqueifier} for faster uniqueness check.
- */
- final void memoizedFill(ImmutableCollection.Builder<E> builder) {
- Uniqueifier memoed;
- synchronized (this) {
- Object memo = getMemo();
- if (memo == null) {
- RecordingUniqueifier uniqueifier = new RecordingUniqueifier();
- getOrder().<E>expander().expandInto(this, uniqueifier, builder);
- setMemo(uniqueifier.getMemo());
- return;
- } else {
- memoed = RecordingUniqueifier.createReplayUniqueifier(memo);
- }
- }
- getOrder().<E>expander().expandInto(this, memoed, builder);
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderExpander.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderExpander.java
deleted file mode 100644
index ec8bd87..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderExpander.java
+++ /dev/null
@@ -1,54 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableCollection;
-
-/**
- * A nested set expander that implements naive left-to-right preordering.
- *
- * <p>For example, for the nested set {B, D, {A, C}}, the iteration order is "B D A C".
- *
- * <p>This implementation is intended for backwards-compatible nested set replacements of code that
- * uses naive preordering.
- *
- * <p>The implementation is called naive because it does no special treatment of dependency graphs
- * that are not trees. For such graphs the property of parent-before-dependencies in the iteration
- * order will not be upheld. For example, the diamond-shape graph A->{B, C}, B->{D}, C->{D} will be
- * enumerated as "A B D C" rather than "A B C D" or "A C B D".
- *
- * <p>The difference from {@link LinkOrderNestedSet} is that this implementation gives priority to
- * left-to-right order over dependencies-after-parent ordering. Note that the latter is usually more
- * important, so please use {@link LinkOrderNestedSet} whenever possible.
- */
-final class NaiveLinkOrderExpander<E> implements NestedSetExpander<E> {
-
- @SuppressWarnings("unchecked")
- @Override
- public void expandInto(NestedSet<E> set, Uniqueifier uniqueifier,
- ImmutableCollection.Builder<E> builder) {
-
- for (Object e : set.directMembers()) {
- if (uniqueifier.isUnique(e)) {
- builder.add((E) e);
- }
- }
-
- for (NestedSet<E> subset : set.transitiveSets()) {
- if (!subset.isEmpty() && uniqueifier.isUnique(subset)) {
- expandInto(subset, uniqueifier, builder);
- }
- }
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderNestedSetFactory.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderNestedSetFactory.java
deleted file mode 100644
index 7305bce..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderNestedSetFactory.java
+++ /dev/null
@@ -1,153 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableList;
-
-/**
- * NaiveLink order {@code NestedSet} factory.
- */
-final class NaiveLinkOrderNestedSetFactory implements NestedSetFactory {
-
- @Override
- public <E> NestedSet<E> onlyDirects(Object[] directs) {
- return new NaiveLinkOnlyDirectsNestedSet<>(directs);
- }
-
- @Override
- public <E> NestedSet<E> onlyDirects(ImmutableList<E> directs) {
- return new NaiveLinkImmutableListDirectsNestedSet<>(directs);
- }
-
- @Override
- public <E> NestedSet<E> oneDirectOneTransitive(E direct, NestedSet<E> transitive) {
- return new NaiveLinkOneDirectOneTransitiveNestedSet<>(direct, transitive);
- }
-
- @Override
- public <E> NestedSet<E> manyDirectsOneTransitive(Object[] direct,
- NestedSet<E> transitive) {
- return new NaiveLinkManyDirectOneTransitiveNestedSet<>(direct, transitive);
- }
-
- @Override
- public <E> NestedSet<E> onlyOneTransitive(NestedSet<E> transitive) {
- return new NaiveLinkOnlyOneTransitiveNestedSet<>(transitive);
- }
-
- @Override
- public <E> NestedSet<E> onlyManyTransitives(NestedSet[] transitives) {
- return new NaiveLinkOnlyTransitivesNestedSet<>(transitives);
- }
-
- @Override
- public <E> NestedSet<E> oneDirectManyTransitive(Object direct, NestedSet[] transitives) {
- return new NaiveLinkOneDirectManyTransitive<>(direct, transitives);
- }
-
- @Override
- public <E> NestedSet<E> manyDirectManyTransitive(Object[] directs, NestedSet[] transitives) {
- return new NaiveLinkManyDirectManyTransitive<>(directs, transitives);
- }
-
- @Override
- public <E> NestedSet<E> oneDirect(final E element) {
- return new NaiveLinkSingleDirectNestedSet<>(element);
- }
-
- private static class NaiveLinkOnlyDirectsNestedSet<E> extends OnlyDirectsNestedSet<E> {
-
- NaiveLinkOnlyDirectsNestedSet(Object[] directs) { super(directs); }
-
- @Override
- public Order getOrder() { return Order.NAIVE_LINK_ORDER; }
- }
-
- private static class NaiveLinkOneDirectOneTransitiveNestedSet<E> extends
- OneDirectOneTransitiveNestedSet<E> {
-
- private NaiveLinkOneDirectOneTransitiveNestedSet(E direct, NestedSet<E> transitive) {
- super(direct, transitive);
- }
-
- @Override
- public Order getOrder() { return Order.NAIVE_LINK_ORDER; }
- }
-
- private static class NaiveLinkOneDirectManyTransitive<E> extends OneDirectManyTransitive<E> {
-
- private NaiveLinkOneDirectManyTransitive(Object direct, NestedSet[] transitive) {
- super(direct, transitive);
- }
-
- @Override
- public Order getOrder() { return Order.NAIVE_LINK_ORDER; }
- }
-
- private static class NaiveLinkManyDirectManyTransitive<E> extends ManyDirectManyTransitive<E> {
-
- private NaiveLinkManyDirectManyTransitive(Object[] directs, NestedSet[] transitives) {
- super(directs, transitives);
- }
-
- @Override
- public Order getOrder() { return Order.NAIVE_LINK_ORDER; }
- }
-
- private static class NaiveLinkOnlyOneTransitiveNestedSet<E>
- extends OnlyOneTransitiveNestedSet<E> {
-
- private NaiveLinkOnlyOneTransitiveNestedSet(NestedSet<E> transitive) { super(transitive); }
-
- @Override
- public Order getOrder() { return Order.NAIVE_LINK_ORDER; }
- }
-
- private static class NaiveLinkManyDirectOneTransitiveNestedSet<E> extends
- ManyDirectOneTransitiveNestedSet<E> {
-
- private NaiveLinkManyDirectOneTransitiveNestedSet(Object[] direct,
- NestedSet<E> transitive) { super(direct, transitive); }
-
- @Override
- public Order getOrder() { return Order.NAIVE_LINK_ORDER; }
- }
-
- private static class NaiveLinkOnlyTransitivesNestedSet<E> extends OnlyTransitivesNestedSet<E> {
-
- private NaiveLinkOnlyTransitivesNestedSet(NestedSet[] transitives) { super(transitives); }
-
- @Override
- public Order getOrder() { return Order.NAIVE_LINK_ORDER; }
- }
-
- private static class NaiveLinkImmutableListDirectsNestedSet<E> extends
- ImmutableListDirectsNestedSet<E> {
-
- private NaiveLinkImmutableListDirectsNestedSet(ImmutableList<E> directs) { super(directs); }
-
- @Override
- public Order getOrder() {
- return Order.NAIVE_LINK_ORDER;
- }
- }
-
- private static class NaiveLinkSingleDirectNestedSet<E> extends SingleDirectNestedSet<E> {
-
- private NaiveLinkSingleDirectNestedSet(E element) { super(element); }
-
- @Override
- public Order getOrder() { return Order.NAIVE_LINK_ORDER; }
- }
-}
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 f7e3f57..39265a6 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
@@ -13,12 +13,19 @@
// limitations under the License.
package com.google.devtools.build.lib.collect.nestedset;
+import com.google.common.base.Function;
import com.google.common.base.Joiner;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.collect.CompactHashSet;
-import java.io.Serializable;
+import java.util.AbstractCollection;
+import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
+import java.util.Objects;
import java.util.Set;
import javax.annotation.Nullable;
@@ -28,41 +35,134 @@
*
* @see NestedSetBuilder
*/
-public abstract class NestedSet<E> implements Iterable<E>, Serializable {
+@SuppressWarnings("unchecked")
+public final class NestedSet<E> implements Iterable<E> {
- NestedSet() {}
+ private final Order order;
+ private final Object children;
+ private byte[] memo;
+
+ private static final byte[] LEAF_MEMO = {};
+ private static final Object[] EMPTY_CHILDREN = {};
+
+ /**
+ * Construct an empty NestedSet. Should only be called by Order's class initializer.
+ */
+ NestedSet(Order order) {
+ this.order = order;
+ this.children = EMPTY_CHILDREN;
+ this.memo = LEAF_MEMO;
+ }
+
+ NestedSet(Order order, Set<E> direct, Set<NestedSet<E>> transitive) {
+ this.order = order;
+
+ // The iteration order of these collections is the order in which we add the items.
+ Collection<E> directOrder = direct;
+ Collection<NestedSet<E>> transitiveOrder = transitive;
+ // True if we visit the direct members before the transitive members.
+ boolean preorder;
+
+ switch(order) {
+ case LINK_ORDER:
+ directOrder = ImmutableList.copyOf(direct).reverse();
+ transitiveOrder = ImmutableList.copyOf(transitive).reverse();
+ preorder = false;
+ break;
+ case STABLE_ORDER:
+ case COMPILE_ORDER:
+ preorder = false;
+ break;
+ case NAIVE_LINK_ORDER:
+ preorder = true;
+ break;
+ default:
+ throw new AssertionError(order);
+ }
+
+ // Remember children we extracted from one-element subsets.
+ // Otherwise we can end up with two of the same child, which is a
+ // problem for the fast path in toList().
+ Set<E> alreadyInserted = ImmutableSet.of();
+ // The candidate array of children.
+ Object[] children = new Object[direct.size() + transitive.size()];
+ int n = 0; // current position in children
+ boolean leaf = true; // until we find otherwise
+
+ for (int pass = 0; pass <= 1; ++pass) {
+ if ((pass == 0) == preorder && !direct.isEmpty()) {
+ for (E member : directOrder) {
+ if (member instanceof Object[]) {
+ throw new IllegalArgumentException("cannot store Object[] in NestedSet");
+ }
+ if (!alreadyInserted.contains(member)) {
+ children[n++] = member;
+ }
+ }
+ alreadyInserted = direct;
+ } else if ((pass == 1) == preorder && !transitive.isEmpty()) {
+ CompactHashSet<E> hoisted = CompactHashSet.create();
+ for (NestedSet<E> subset : transitiveOrder) {
+ Object c = subset.children;
+ if (c instanceof Object[]) {
+ Object[] a = (Object[]) c;
+ if (a.length < 2) {
+ throw new AssertionError(a.length);
+ }
+ children[n++] = a;
+ leaf = false;
+ } else {
+ if (!alreadyInserted.contains((E) c) && hoisted.add((E) c)) {
+ children[n++] = c;
+ }
+ }
+ }
+ alreadyInserted = hoisted;
+ }
+ }
+
+ // If we ended up wrapping exactly one item or one other set, dereference it.
+ if (n == 1) {
+ this.children = children[0];
+ } else if (n == 0) {
+ this.children = EMPTY_CHILDREN;
+ } else if (n < children.length) {
+ this.children = Arrays.copyOf(children, n);
+ } else {
+ this.children = children;
+ }
+ if (leaf) {
+ this.memo = LEAF_MEMO;
+ }
+ }
/**
* Returns the ordering of this nested set.
*/
- public abstract Order getOrder();
+ public Order getOrder() {
+ return order;
+ }
/**
- * Returns a collection of elements added to this specific set in an implementation-specified
- * order.
- *
- * <p>Elements from subsets are not taken into account.
- *
- * <p>The reason for using Object[] instead of E[] is that when we build the NestedSet we
- * would need to have access to the specific class that E represents in order to create an E
- * array. Since this method is only designed to be used internally it is fine to keep it as
- * Object[].
- *
- * <p>Callers of this method should only consume the objects and not modify the array.
+ * Returns the internal item or array. For use by NestedSetVisitor.
*/
- abstract Object[] directMembers();
-
- /**
- * Returns the collection of sets included as subsets in this set.
- *
- * <p>Callers of this method should only consume the objects and not modify the array.
- */
- abstract NestedSet[] transitiveSets();
+ Object rawChildren() {
+ return children;
+ }
/**
* Returns true if the set is empty.
*/
- public abstract boolean isEmpty();
+ public boolean isEmpty() {
+ return children == EMPTY_CHILDREN;
+ }
+
+ /**
+ * Returns true if the set has exactly one element.
+ */
+ private boolean isSingleton() {
+ return !(children instanceof Object[]);
+ }
/**
* Returns a collection of all unique elements of this set (including subsets)
@@ -81,7 +181,15 @@
*
* <p>Use {@link #toCollection} when possible for better efficiency.
*/
- public abstract List<E> toList();
+ public List<E> toList() {
+ if (isSingleton()) {
+ return ImmutableList.of((E) children);
+ }
+ if (isEmpty()) {
+ return ImmutableList.of();
+ }
+ return order == Order.LINK_ORDER ? expand().reverse() : expand();
+ }
/**
* Returns a collection of all unique elements of this set (including subsets)
@@ -89,7 +197,9 @@
*
* <p>Use {@link #toCollection} when possible for better efficiency.
*/
- public abstract Set<E> toSet();
+ public Set<E> toSet() {
+ return ImmutableSet.copyOf(toList());
+ }
/**
* Returns true if this set is equal to {@code other} based on the top-level
@@ -100,7 +210,16 @@
*
* @param other the {@code NestedSet} to compare against.
*/
- public abstract boolean shallowEquals(@Nullable NestedSet<? extends E> other);
+ public boolean shallowEquals(@Nullable NestedSet<? extends E> other) {
+ if (this == other) {
+ return true;
+ }
+ return other != null
+ && order == other.order
+ && (children.equals(other.children)
+ || (!isSingleton() && !other.isSingleton()
+ && Arrays.equals((Object[]) children, (Object[]) other.children)));
+ }
/**
* Returns a hash code that produces a notion of identity that is consistent with
@@ -111,17 +230,165 @@
* the standard equals/hashCode is to minimize accidental use, since they are
* different from both standard Java objects and collection-like objects.
*/
- public abstract int shallowHashCode();
-
- @Override
- public String toString() {
- String members = Joiner.on(", ").join(directMembers());
- String nestedSets = Joiner.on(", ").join(transitiveSets());
- String separator = members.length() > 0 && nestedSets.length() > 0 ? ", " : "";
- return "{" + members + separator + nestedSets + "}";
+ public int shallowHashCode() {
+ if (isSingleton()) {
+ return Objects.hash(order, children);
+ } else {
+ return Objects.hash(order, Arrays.hashCode((Object[]) children));
+ }
}
@Override
- public Iterator<E> iterator() { return new NestedSetLazyIterator<>(this); }
+ public String toString() {
+ return isSingleton() ? "{" + children + "}" : childrenToString(children);
+ }
+ // TODO: this leaves LINK_ORDER backwards
+ private static String childrenToString(Object children) {
+ if (children instanceof Object[]) {
+ return "{" + Joiner.on(", ").join(Iterables.transform(
+ Arrays.asList((Object[]) children), Stringer.INSTANCE)) + "}";
+ } else {
+ return children.toString();
+ }
+ }
+
+ private static enum Stringer implements Function<Object, String> {
+ INSTANCE;
+ @Override public String apply(Object o) {
+ return childrenToString(o);
+ }
+ };
+
+ @Override
+ public Iterator<E> iterator() {
+ // TODO: would it help to have a proper lazy iterator? seems like it might reduce garbage.
+ return toCollection().iterator();
+ }
+
+ /**
+ * Implementation of {@link #toList}. Uses one of three strategies based on the value of
+ * {@code this.memo}: wrap our direct items in a list, call {@link #lockedExpand} to perform
+ * the initial {@link #walk}, or call {@link #replay} if we have a nontrivial memo.
+ */
+ private ImmutableList<E> expand() {
+ // This value is only set in the constructor, so safe to test here with no lock.
+ if (memo == LEAF_MEMO) {
+ return ImmutableList.<E>copyOf(new ArraySharingCollection<E>((Object[]) children));
+ }
+ CompactHashSet<E> members = lockedExpand();
+ if (members != null) {
+ return ImmutableList.copyOf(members);
+ }
+ Object[] children = (Object[]) this.children;
+ // TODO: We could record the exact size (inside memo, or by making order an int with two bits
+ // for Order.ordinal()) and avoid an array copy here. It's not directly visible in profiles but
+ // it would reduce garbage generated.
+ ImmutableList.Builder<E> output = ImmutableList.builder();
+ replay(output, children, memo, 0);
+ return output.build();
+ }
+
+ // Hack to share our internal array with ImmutableList/ImmutableSet, or avoid
+ // a copy in cases where we can preallocate an array of the correct size.
+ private static final class ArraySharingCollection<E> extends AbstractCollection<E> {
+ private final Object[] array;
+ ArraySharingCollection(Object[] array) {
+ this.array = array;
+ }
+ @Override public Object[] toArray() {
+ return array;
+ }
+ @Override public int size() {
+ return array.length;
+ }
+ @Override public Iterator<E> iterator() {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ /**
+ * If this is the first call for this object, fills {@code this.memo} and returns a set from
+ * {@link #walk}. Otherwise returns null; the caller should use {@link #replay} instead.
+ */
+ private synchronized CompactHashSet<E> lockedExpand() {
+ if (memo != null) {
+ return null;
+ }
+ Object[] children = (Object[]) this.children;
+ CompactHashSet<E> members = CompactHashSet.createWithExpectedSize(128);
+ CompactHashSet<Object> sets = CompactHashSet.createWithExpectedSize(128);
+ sets.add(children);
+ memo = new byte[Math.min((children.length + 7) / 8, 8)];
+ int pos = walk(sets, members, children, 0);
+ int bytes = (pos + 7) / 8;
+ if (bytes <= memo.length - 16) {
+ memo = Arrays.copyOf(memo, bytes);
+ }
+ return members;
+ }
+
+ /**
+ * Perform a depth-first traversal of {@code children}, tracking visited
+ * arrays in {@code sets} and visited leaves in {@code members}. We also
+ * record which edges were taken in {@code this.memo} starting at {@code pos}.
+ *
+ * Returns the final value of {@code pos}.
+ */
+ private int walk(CompactHashSet<Object> sets, CompactHashSet<E> members,
+ Object[] children, int pos) {
+ int n = children.length;
+ for (int i = 0; i < n; ++i) {
+ if ((pos>>3) >= memo.length) {
+ memo = Arrays.copyOf(memo, memo.length * 2);
+ }
+ Object c = children[i];
+ if (c instanceof Object[]) {
+ if (sets.add(c)) {
+ int prepos = pos;
+ int presize = members.size();
+ pos = walk(sets, members, (Object[]) c, pos + 1);
+ if (presize < members.size()) {
+ memo[prepos>>3] |= 1<<(prepos&7);
+ } else {
+ // We didn't find any new nodes, so don't mark this branch as taken.
+ // Rewind pos. The rest of the array is still zeros because no one
+ // deeper in the traversal set any bits.
+ pos = prepos + 1;
+ }
+ } else {
+ ++pos;
+ }
+ } else {
+ if (members.add((E) c)) {
+ memo[pos>>3] |= 1<<(pos&7);
+ }
+ ++pos;
+ }
+ }
+ return pos;
+ }
+
+ /**
+ * Repeat a previous traversal of {@code children} performed by {@link #walk}
+ * and recorded in {@code memo}, appending leaves to {@code output}.
+ */
+ private static <E> int replay(ImmutableList.Builder<E> output, Object[] children,
+ byte[] memo, int pos) {
+ int n = children.length;
+ for (int i = 0; i < n; ++i) {
+ Object c = children[i];
+ if ((memo[pos>>3] & (1<<(pos&7))) != 0) {
+ if (c instanceof Object[]) {
+ pos = replay(output, (Object[]) c, memo, pos + 1);
+ } else {
+ output.add((E) c);
+ ++pos;
+ }
+ } else {
+ ++pos;
+ }
+ }
+ return pos;
+ }
}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetBuilder.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetBuilder.java
index 9cd15c2..e767789 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetBuilder.java
@@ -17,22 +17,24 @@
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
+import com.google.common.collect.MapMaker;
+import com.google.devtools.build.lib.collect.CompactHashSet;
import com.google.devtools.build.lib.util.Preconditions;
-import java.util.LinkedHashSet;
+import java.util.concurrent.ConcurrentMap;
/**
* A builder for nested sets.
*
* <p>The builder supports the standard builder interface (that is, {@code #add}, {@code #addAll}
- * and {@code #addTransitive} followed by {@code build}), in addition to shortcut methods
- * {@code #wrap} and {@code #of}.
+ * and {@code #addTransitive} followed by {@code build}), in addition to shortcut method
+ * {@code #wrap}.
*/
public final class NestedSetBuilder<E> {
private final Order order;
- private final LinkedHashSet<E> items = new LinkedHashSet<>();
- private final LinkedHashSet<NestedSet<? extends E>> transitiveSets = new LinkedHashSet<>();
+ private final CompactHashSet<E> items = CompactHashSet.create();
+ private final CompactHashSet<NestedSet<? extends E>> transitiveSets = CompactHashSet.create();
public NestedSetBuilder(Order order) {
this.order = order;
@@ -105,7 +107,7 @@
* addTransitive calls matters, but the order between add/addAll and addTransitive does not.
*
* <p>An error will be thrown if the ordering of {@code subset} is incompatible with the ordering
- * of this set. Either they must match or this set must be a {@code STABLE_ORDER} set.
+ * of this set. Either they must match or one must be a {@code STABLE_ORDER} set.
*
* @return the builder.
*/
@@ -132,8 +134,8 @@
* <p>This method may be called multiple times with interleaved {@link #add}, {@link #addAll} and
* {@link #addTransitive} calls.
*/
- // Casting from LinkedHashSet<NestedSet<? extends E>> to LinkedHashSet<NestedSet<E>> by way of
- // LinkedHashSet<?>.
+ // Casting from CompactHashSet<NestedSet<? extends E>> to CompactHashSet<NestedSet<E>> by way of
+ // CompactHashSet<?>.
@SuppressWarnings("unchecked")
public NestedSet<E> build() {
if (isEmpty()) {
@@ -143,74 +145,45 @@
// This cast is safe because NestedSets are immutable -- we will never try to add an element to
// these nested sets, only to retrieve elements from them. Thus, treating them as NestedSet<E>
// is safe.
- LinkedHashSet<NestedSet<E>> transitiveSetsCast =
- (LinkedHashSet<NestedSet<E>>) (LinkedHashSet<?>) transitiveSets;
+ CompactHashSet<NestedSet<E>> transitiveSetsCast =
+ (CompactHashSet<NestedSet<E>>) (CompactHashSet<?>) transitiveSets;
if (items.isEmpty() && (transitiveSetsCast.size() == 1)) {
NestedSet<E> candidate = getOnlyElement(transitiveSetsCast);
if (candidate.getOrder().equals(order)) {
return candidate;
}
}
- int transitiveSize = transitiveSets.size();
- int directSize = items.size();
-
- switch (transitiveSize) {
- case 0:
- switch (directSize) {
- case 0:
- return order.emptySet();
- case 1:
- return order.factory.oneDirect(getOnlyElement(items));
- default:
- return order.factory.onlyDirects(items.toArray());
- }
- case 1:
- switch (directSize) {
- case 0:
- return order.factory.onlyOneTransitive(getOnlyElement(transitiveSetsCast));
- case 1:
- return order.factory.oneDirectOneTransitive(getOnlyElement(items),
- getOnlyElement(transitiveSetsCast));
- default:
- return order.factory.manyDirectsOneTransitive(items.toArray(),
- getOnlyElement(transitiveSetsCast));
- }
- default:
- switch (directSize) {
- case 0:
- return order.factory.onlyManyTransitives(
- transitiveSetsCast.toArray(new NestedSet[transitiveSize]));
- case 1:
- return order.factory.oneDirectManyTransitive(getOnlyElement(items), transitiveSetsCast
- .toArray(new NestedSet[transitiveSize]));
- default:
- return order.factory.manyDirectManyTransitive(items.toArray(),
- transitiveSetsCast.toArray(new NestedSet[transitiveSize]));
- }
- }
+ return new NestedSet<E>(order, items, transitiveSetsCast);
}
+ private static final ConcurrentMap<ImmutableList<?>, NestedSet<?>> immutableListCache =
+ new MapMaker().weakKeys().makeMap();
+
/**
* Creates a nested set from a given list of items.
- *
- * <p>If the list of items is an {@link ImmutableList}, reuses the list as the backing store for
- * the nested set.
*/
+ @SuppressWarnings("unchecked")
public static <E> NestedSet<E> wrap(Order order, Iterable<E> wrappedItems) {
ImmutableList<E> wrappedList = ImmutableList.copyOf(wrappedItems);
if (wrappedList.isEmpty()) {
return order.emptySet();
- } else if (wrappedList.size() == 1) {
- return order.factory.oneDirect(getOnlyElement(wrappedItems));
+ } else if (order == Order.STABLE_ORDER
+ && wrappedList == wrappedItems && wrappedList.size() > 1) {
+ NestedSet<?> cached = immutableListCache.get(wrappedList);
+ if (cached != null) {
+ return (NestedSet<E>) cached;
+ }
+ NestedSet<E> built = new NestedSetBuilder<E>(order).addAll(wrappedList).build();
+ immutableListCache.putIfAbsent(wrappedList, built);
+ return built;
} else {
- return order.factory.onlyDirects(wrappedList);
+ return new NestedSetBuilder<E>(order).addAll(wrappedList).build();
}
}
-
- /**
- * Creates a nested set with the given list of items as its elements.
- */
+ /**
+ * Creates a nested set with the given list of items as its elements.
+ */
@SuppressWarnings("unchecked")
public static <E> NestedSet<E> create(Order order, E... elems) {
return wrap(order, ImmutableList.copyOf(elems));
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetExpander.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetExpander.java
deleted file mode 100644
index d79fb98..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetExpander.java
+++ /dev/null
@@ -1,30 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableCollection;
-
-/**
- * An expander that converts a nested set into a flattened collection.
- *
- * <p>Expanders are initialized statically (there is one for each order), so they should
- * contain no state and all methods must be threadsafe.
- */
-interface NestedSetExpander<E> {
- /**
- * Flattens the NestedSet into the builder.
- */
- void expandInto(NestedSet<E> nestedSet, Uniqueifier uniqueifier,
- ImmutableCollection.Builder<E> builder);
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFactory.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFactory.java
deleted file mode 100644
index 29a3a52..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFactory.java
+++ /dev/null
@@ -1,55 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableList;
-
-/**
- * Factory methods for creating {@link NestedSet}s of specific shapes. This allows the
- * implementation to be memory efficient (e.g. a specialized implementation for the case where
- * there are only direct elements, etc).
- *
- * <p>It's intended for each {@link Order} to have its own factory implementation. That way we can
- * be even more efficient since the {@link NestedSet}s instances don't need to store their
- * {@link Order}.
- */
-interface NestedSetFactory {
-
- /** Create a NestedSet with just one direct element and not transitive elements. */
- <E> NestedSet<E> oneDirect(E element);
-
- /** Create a NestedSet with only direct elements. */
- <E> NestedSet<E> onlyDirects(Object[] directs);
-
- /** Create a NestedSet with only direct elements potentially sharing the ImmutableList. */
- <E> NestedSet<E> onlyDirects(ImmutableList<E> directs);
-
- /** Create a NestedSet with one direct element and one transitive {@code NestedSet}. */
- <E> NestedSet<E> oneDirectOneTransitive(E direct, NestedSet<E> transitive);
-
- /** Create a NestedSet with many direct elements and one transitive {@code NestedSet}. */
- <E> NestedSet<E> manyDirectsOneTransitive(Object[] direct, NestedSet<E> transitive);
-
- /** Create a NestedSet with no direct elements and one transitive {@code NestedSet.} */
- <E> NestedSet<E> onlyOneTransitive(NestedSet<E> transitive);
-
- /** Create a NestedSet with no direct elements and many transitive {@code NestedSet}s. */
- <E> NestedSet<E> onlyManyTransitives(NestedSet[] transitives);
-
- /** Create a NestedSet with one direct elements and many transitive {@code NestedSet}s. */
- <E> NestedSet<E> oneDirectManyTransitive(Object direct, NestedSet[] transitive);
-
- /** Create a NestedSet with many direct elements and many transitive {@code NestedSet}s. */
- <E> NestedSet<E> manyDirectManyTransitive(Object[] directs, NestedSet[] transitive);
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetLazyIterator.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetLazyIterator.java
deleted file mode 100644
index 8caffbb..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetLazyIterator.java
+++ /dev/null
@@ -1,53 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import java.util.Iterator;
-
-/**
- * A NestedSet iterator that only expands the NestedSet when the first element is requested. This
- * allows code that calls unconditionally to {@code hasNext} to check if the iterator is empty
- * to not expand the nested set.
- */
-final class NestedSetLazyIterator<E> implements Iterator<E> {
-
- private NestedSet<E> nestedSet;
- private Iterator<E> delegate = null;
-
- NestedSetLazyIterator(NestedSet<E> nestedSet) {
- this.nestedSet = nestedSet;
- }
-
- @Override
- public boolean hasNext() {
- if (delegate == null) {
- return !nestedSet.isEmpty();
- }
- return delegate.hasNext();
- }
-
- @Override
- public E next() {
- if (delegate == null) {
- delegate = nestedSet.toCollection().iterator();
- nestedSet = null;
- }
- return delegate.next();
- }
-
- @Override
- public void remove() {
- throw new UnsupportedOperationException();
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java
index 935212a..705653f 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java
@@ -34,7 +34,7 @@
public final class NestedSetVisitor<E> {
/**
- * For each element of the NestedSet the {@code Reciver} will receive one element during the
+ * For each element of the NestedSet the {@code Receiver} will receive one element during the
* visitation.
*/
public interface Receiver<E> {
@@ -56,41 +56,34 @@
* @param nestedSet the nested set to visit transitively.
*
*/
- @SuppressWarnings("unchecked")
public void visit(NestedSet<E> nestedSet) {
- // This method suppresses the unchecked warning so that it can access the internal NestedSet
- // raw structure.
Preconditions.checkArgument(nestedSet.getOrder() == Order.STABLE_ORDER);
- if (!visited.add(nestedSet)) {
- return;
- }
+ visitRaw(nestedSet.rawChildren());
+ }
- for (NestedSet<E> subset : nestedSet.transitiveSets()) {
- visit(subset);
- }
- for (Object member : nestedSet.directMembers()) {
- if (visited.add((E) member)) {
- callback.accept((E) member);
+ @SuppressWarnings("unchecked")
+ private void visitRaw(Object node) {
+ if (visited.add(node)) {
+ if (node instanceof Object[]) {
+ for (Object child : (Object[]) node) {
+ visitRaw(child);
+ }
+ } else {
+ callback.accept((E) node);
}
}
}
/** A class that allows us to keep track of the seen nodes and transitive sets. */
public static class VisitedState<E> {
- private final Set<NestedSet<E>> seenSets = Sets.newConcurrentHashSet();
- private final Set<E> seenNodes = Sets.newConcurrentHashSet();
+ private final Set<Object> seenNodes = Sets.newConcurrentHashSet();
public void clear() {
- seenSets.clear();
seenNodes.clear();
}
- private boolean add(E node) {
+ private boolean add(Object node) {
return seenNodes.add(node);
}
-
- private boolean add(NestedSet<E> set) {
- return !set.isEmpty() && seenSets.add(set);
- }
}
}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/OneDirectManyTransitive.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/OneDirectManyTransitive.java
deleted file mode 100644
index 5469420..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/OneDirectManyTransitive.java
+++ /dev/null
@@ -1,63 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import java.util.Arrays;
-import java.util.Objects;
-
-import javax.annotation.Nullable;
-
-/**
- * Memory-optimized NestedSet implementation for NestedSets with one direct element and
- * many transitive dependencies.
- */
-abstract class OneDirectManyTransitive<E> extends MemoizedUniquefierNestedSet<E> {
-
- private final Object direct;
- private final NestedSet[] transitives;
- private Object memo;
-
- OneDirectManyTransitive(Object direct, NestedSet[] transitives) {
- this.direct = direct;
- this.transitives = transitives;
- }
-
- @Override
- Object getMemo() { return memo; }
-
- @Override
- void setMemo(Object memo) { this.memo = memo; }
-
- @Override
- Object[] directMembers() { return new Object[]{direct}; }
-
- @Override
- NestedSet[] transitiveSets() { return transitives; }
-
- @Override
- public boolean shallowEquals(@Nullable NestedSet<? extends E> other) {
- if (this == other) {
- return true;
- }
- return other != null
- && getOrder().equals(other.getOrder())
- && other instanceof OneDirectManyTransitive
- && direct.equals(((OneDirectManyTransitive) other).direct)
- && Arrays.equals(transitives, ((OneDirectManyTransitive) other).transitives);
- }
-
- @Override
- public int shallowHashCode() {
- return Objects.hash(getOrder(), direct, Arrays.hashCode(transitives)); }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/OneDirectOneTransitiveNestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/OneDirectOneTransitiveNestedSet.java
deleted file mode 100644
index 802963d..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/OneDirectOneTransitiveNestedSet.java
+++ /dev/null
@@ -1,61 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import java.util.Objects;
-
-import javax.annotation.Nullable;
-
-/**
- * Memory-efficient implementation for the case where we have one direct element and one
- * transitive NestedSet.
- */
-abstract class OneDirectOneTransitiveNestedSet<E> extends MemoizedUniquefierNestedSet<E> {
-
- private final E direct;
- private final NestedSet<E> transitive;
- private Object memo;
-
- OneDirectOneTransitiveNestedSet(E direct, NestedSet<E> transitive) {
- this.direct = direct;
- this.transitive = transitive;
- }
-
- @Override
- Object getMemo() { return memo; }
-
- @Override
- void setMemo(Object memo) { this.memo = memo; }
-
- @Override
- Object[] directMembers() { return new Object[]{direct}; }
-
- @Override
- NestedSet[] transitiveSets() { return new NestedSet[]{transitive}; }
-
- @Override
- public boolean shallowEquals(@Nullable NestedSet<? extends E> other) {
- if (this == other) {
- return true;
- }
- return other != null
- && getOrder().equals(other.getOrder())
- && other instanceof OneDirectOneTransitiveNestedSet
- && direct.equals(((OneDirectOneTransitiveNestedSet) other).direct)
- && transitive == ((OneDirectOneTransitiveNestedSet) other).transitive;
- }
-
- @Override
- public int shallowHashCode() { return Objects.hash(getOrder(), direct, transitive); }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/OnlyDirectsNestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/OnlyDirectsNestedSet.java
deleted file mode 100644
index 1c9cf33..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/OnlyDirectsNestedSet.java
+++ /dev/null
@@ -1,88 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
-
-import java.util.Arrays;
-import java.util.List;
-import java.util.Set;
-
-import javax.annotation.Nullable;
-
-/**
- * Memory-optimized NestedSet implementation for NestedSets without transitive dependencies.
- *
- */
-abstract class OnlyDirectsNestedSet<E> extends NestedSet<E> {
-
- private static final NestedSet[] EMPTY = new NestedSet[0];
- private final Object[] directDeps;
-
- public OnlyDirectsNestedSet(Object[] directDeps) { this.directDeps = directDeps; }
-
- @Override
- public abstract Order getOrder();
-
- @Override
- Object[] directMembers() {
- return directDeps;
- }
-
- @Override
- NestedSet[] transitiveSets() {
- return EMPTY;
- }
-
- @Override
- public boolean isEmpty() {
- return false;
- }
-
- /**
- * Currently all the Order implementations return the direct elements in the same order if they
- * do not have transitive elements. So we skip calling order.getExpander()... and return a view
- * of the array.
- */
- @SuppressWarnings("unchecked")
- @Override
- public List<E> toList() {
- return (List<E>) ImmutableList.copyOf(directDeps);
- }
-
- @SuppressWarnings("unchecked")
- @Override
- public Set<E> toSet() {
- return (Set<E>) ImmutableSet.copyOf(directDeps);
- }
-
- @Override
- public boolean shallowEquals(@Nullable NestedSet<? extends E> other) {
- if (this == other) {
- return true;
- }
- if (other == null) {
- return false;
- }
- return getOrder().equals(other.getOrder())
- && other instanceof OnlyDirectsNestedSet
- && Arrays.equals(directDeps, ((OnlyDirectsNestedSet) other).directDeps);
- }
-
- @Override
- public int shallowHashCode() {
- return Arrays.hashCode(directDeps);
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/OnlyOneTransitiveNestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/OnlyOneTransitiveNestedSet.java
deleted file mode 100644
index c7daaf8..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/OnlyOneTransitiveNestedSet.java
+++ /dev/null
@@ -1,68 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import java.util.Objects;
-
-import javax.annotation.Nullable;
-
-/**
- * Memory-efficient implementation for the case where we only have one transitive NestedSet.
- *
- * <p>Note that we cannot simply delegate to the inner NestedSet because the order could be
- * different and the top-level order is the correct one.
- */
-abstract class OnlyOneTransitiveNestedSet<E> extends MemoizedUniquefierNestedSet<E> {
-
- private static final Object[] EMPTY = new Object[0];
-
- private final NestedSet<E> transitive;
- private Object memo;
-
- public OnlyOneTransitiveNestedSet(NestedSet<E> transitive) {
- this.transitive = transitive;
- }
-
- @Override
- Object getMemo() { return memo; }
-
- @Override
- void setMemo(Object memo) { this.memo = memo; }
-
- @Override
- Object[] directMembers() {
- return EMPTY;
- }
-
- @Override
- NestedSet[] transitiveSets() {
- return new NestedSet[]{transitive};
- }
-
- @Override
- public boolean shallowEquals(@Nullable NestedSet<? extends E> other) {
- if (this == other) {
- return true;
- }
- return other != null
- && getOrder().equals(other.getOrder())
- && other instanceof OnlyOneTransitiveNestedSet
- && transitive == ((OnlyOneTransitiveNestedSet) other).transitive;
- }
-
- @Override
- public int shallowHashCode() {
- return Objects.hash(getOrder(), transitive);
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/OnlyTransitivesNestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/OnlyTransitivesNestedSet.java
deleted file mode 100644
index b813e0b..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/OnlyTransitivesNestedSet.java
+++ /dev/null
@@ -1,62 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import java.util.Arrays;
-import java.util.Objects;
-
-import javax.annotation.Nullable;
-
-/**
- * Memory-efficient implementation for the case where we have one direct element and one
- * transitive NestedSet.
- */
-abstract class OnlyTransitivesNestedSet<E> extends MemoizedUniquefierNestedSet<E> {
-
- private static final NestedSet[] EMPTY = new NestedSet[0];
-
- private final NestedSet[] transitives;
- private Object memo;
-
- OnlyTransitivesNestedSet(NestedSet[] transitives) {
- this.transitives = transitives;
- }
-
- @Override
- Object getMemo() { return memo; }
-
- @Override
- void setMemo(Object memo) { this.memo = memo; }
-
- @Override
- Object[] directMembers() { return EMPTY; }
-
- @Override
- NestedSet[] transitiveSets() { return transitives; }
-
- @Override
- public boolean shallowEquals(@Nullable NestedSet<? extends E> other) {
- if (this == other) {
- return true;
- }
- return other != null
- && getOrder().equals(other.getOrder())
- && other instanceof OnlyTransitivesNestedSet
- && Arrays.equals(transitives, ((OnlyTransitivesNestedSet) other).transitives);
- }
-
- @Override
- public int shallowHashCode() {
- return Objects.hash(getOrder(), Arrays.hashCode(transitives)); }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
index 2b41969..175ea3e 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
@@ -23,25 +23,19 @@
* see CompileOrderExpander, LinkOrderExpander, NaiveLinkOrderExpander.
*/
public enum Order {
-
- STABLE_ORDER("stable", new CompileOrderExpander<>(), new StableOrderNestedSetFactory()),
- COMPILE_ORDER("compile", new CompileOrderExpander<>(), new CompileOrderNestedSetFactory()),
- LINK_ORDER("link", new LinkOrderExpander<>(), new LinkOrderNestedSetFactory()),
- NAIVE_LINK_ORDER("naive_link", new NaiveLinkOrderExpander<>(),
- new NaiveLinkOrderNestedSetFactory());
+ STABLE_ORDER("stable"),
+ COMPILE_ORDER("compile"),
+ LINK_ORDER("link"),
+ NAIVE_LINK_ORDER("naive_link");
private static final ImmutableMap<String, Order> VALUES;
private final String name;
- private final NestedSetExpander<?> expander;
- final NestedSetFactory factory;
private final NestedSet<?> emptySet;
- private Order(String name, NestedSetExpander<?> expander, NestedSetFactory factory) {
+ private Order(String name) {
this.name = name;
- this.expander = expander;
- this.factory = factory;
- this.emptySet = new EmptyNestedSet<>(this);
+ this.emptySet = new NestedSet<>(this);
}
/**
@@ -52,14 +46,6 @@
return (NestedSet<E>) emptySet;
}
- /**
- * Returns an empty set of the given ordering.
- */
- @SuppressWarnings("unchecked") // Nested set expanders contain no data themselves.
- <E> NestedSetExpander<E> expander() {
- return (NestedSetExpander<E>) expander;
- }
-
public String getName() {
return name;
}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifier.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifier.java
deleted file mode 100644
index 7a46606..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifier.java
+++ /dev/null
@@ -1,150 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.annotations.VisibleForTesting;
-import com.google.devtools.build.lib.collect.CompactHashSet;
-import com.google.devtools.build.lib.util.Preconditions;
-
-import java.util.BitSet;
-import java.util.Set;
-
-/**
- * A Uniqueifier that records a transcript of its interactions with the underlying Set. A memo can
- * then be retrieved in the form of another Uniqueifier, and given the same sequence of isUnique
- * calls, the Set interactions can be avoided.
- */
-class RecordingUniqueifier implements Uniqueifier {
- /**
- * Unshared byte memos under this length are not constructed.
- */
- @VisibleForTesting static final int LENGTH_THRESHOLD = 4096 / 8; // bits -> bytes
-
- /**
- * Returned as a marker that memoization was not worthwhile.
- */
- private static final Object NO_MEMO = new Object();
-
- /**
- * Shared one-byte memos.
- */
- private static final byte[][] SHARED_SMALL_MEMOS_1;
-
- /**
- * Shared two-byte memos.
- */
- private static final byte[][] SHARED_SMALL_MEMOS_2;
-
- static {
- // Create interned arrays for one and two byte memos
- // The memos always start with 0x3, so some one and two byte arrays can be skipped.
-
- byte[][] memos1 = new byte[64][1];
- for (int i = 0; i < 64; i++) {
- memos1[i][0] = (byte) ((i << 2) | 0x3);
- }
- SHARED_SMALL_MEMOS_1 = memos1;
-
- byte[][] memos2 = new byte[16384][2];
- for (int i = 0; i < 64; i++) {
- byte iAdj = (byte) (0x3 | (i << 2));
- for (int j = 0; j < 256; j++) {
- int idx = i | (j << 6);
- memos2[idx][0] = iAdj;
- memos2[idx][1] = (byte) j;
- }
- }
- SHARED_SMALL_MEMOS_2 = memos2;
- }
-
- private final Set<Object> witnessed;
- private final BitSet memo = new BitSet();
- private int idx = 0;
-
- RecordingUniqueifier() {
- this(256);
- }
-
- RecordingUniqueifier(int expectedSize) {
- this.witnessed = CompactHashSet.createWithExpectedSize(expectedSize);
- }
-
- static Uniqueifier createReplayUniqueifier(Object memo) {
- if (memo == NO_MEMO) {
- // We receive NO_MEMO for nested sets that are under a size threshold. Therefore, use a
- // smaller initial size than the default.
- return new RecordingUniqueifier(64);
- } else if (memo instanceof Integer) {
- BitSet bs = new BitSet();
- bs.set(0, (Integer) memo);
- return new ReplayUniqueifier(bs);
- }
- return new ReplayUniqueifier(BitSet.valueOf((byte[]) memo));
- }
-
- @Override
- public boolean isUnique(Object o) {
- boolean firstInstance = witnessed.add(o);
- memo.set(idx++, firstInstance);
- return firstInstance;
- }
-
- /**
- * Gets the memo of the set interactions. Do not call isUnique after this point.
- */
- Object getMemo() {
- this.idx = -1; // will cause failures if isUnique is called after getMemo.
-
- // If the bitset is just a contiguous block of ones, use a length memo
- int length = memo.length();
- if (memo.cardinality() == length) {
- return length; // length-based memo
- }
-
- byte[] ba = memo.toByteArray();
-
- Preconditions.checkState(
- (length < 2) || ((ba[0] & 3) == 3),
- "The memo machinery expects memos to always begin with two 1 bits, "
- + "but instead, this memo starts with %s.", ba[0]);
-
- // For short memos, use an interned array for the memo
- if (ba.length == 1) {
- return SHARED_SMALL_MEMOS_1[(0xFF & ba[0]) >>> 2]; // shared memo
- } else if (ba.length == 2) {
- return SHARED_SMALL_MEMOS_2[((ba[1] & 0xFF) << 6) | ((0xFF & ba[0]) >>> 2)];
- }
-
- // For mid-sized cases, skip the memo since it is not worthwhile
- if (ba.length < LENGTH_THRESHOLD) {
- return NO_MEMO; // skipped memo
- }
-
- return ba; // normal memo
- }
-
- private static final class ReplayUniqueifier implements Uniqueifier {
- private final BitSet memo;
- private int idx = 0;
-
- ReplayUniqueifier(BitSet memo) {
- this.memo = memo;
- }
-
- @Override
- public boolean isUnique(Object o) {
- return memo.get(idx++);
- }
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/SingleDirectNestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/SingleDirectNestedSet.java
deleted file mode 100644
index 8f49e4b..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/SingleDirectNestedSet.java
+++ /dev/null
@@ -1,68 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Iterators;
-import com.google.devtools.build.lib.util.Preconditions;
-
-import java.util.Iterator;
-import java.util.List;
-import java.util.Set;
-
-import javax.annotation.Nullable;
-
-/**
- * Memory-efficient implementation for nested sets with one element.
- */
-public abstract class SingleDirectNestedSet<E> extends NestedSet<E> {
-
- private static final NestedSet[] EMPTY = new NestedSet[0];
- private final E e;
-
- public SingleDirectNestedSet(E e) { this.e = Preconditions.checkNotNull(e); }
-
- @Override
- public Iterator<E> iterator() { return Iterators.singletonIterator(e); }
-
- @Override
- Object[] directMembers() { return new Object[]{e}; }
-
- @Override
- NestedSet[] transitiveSets() { return EMPTY; }
-
- @Override
- public boolean isEmpty() { return false; }
-
- @Override
- public List<E> toList() { return ImmutableList.of(e); }
-
- @Override
- public Set<E> toSet() { return ImmutableSet.of(e); }
-
- @Override
- public boolean shallowEquals(@Nullable NestedSet<? extends E> other) {
- if (this == other) {
- return true;
- }
- return other instanceof SingleDirectNestedSet
- && e.equals(((SingleDirectNestedSet) other).e);
- }
-
- @Override
- public int shallowHashCode() {
- return e.hashCode();
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/StableOrderNestedSetFactory.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/StableOrderNestedSetFactory.java
deleted file mode 100644
index 56bfd37..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/StableOrderNestedSetFactory.java
+++ /dev/null
@@ -1,152 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import com.google.common.collect.ImmutableList;
-
-/**
- * Stable order {@code NestedSet} factory.
- */
-final class StableOrderNestedSetFactory implements NestedSetFactory {
-
- @Override
- public <E> NestedSet<E> onlyDirects(Object[] directs) {
- return new StableOnlyDirectsNestedSet<>(directs);
- }
-
- @Override
- public <E> NestedSet<E> onlyDirects(ImmutableList<E> directs) {
- return new StableImmutableListDirectsNestedSet<>(directs);
- }
-
- @Override
- public <E> NestedSet<E> oneDirectOneTransitive(E direct, NestedSet<E> transitive) {
- return new StableOneDirectOneTransitiveNestedSet<>(direct, transitive);
- }
-
- @Override
- public <E> NestedSet<E> manyDirectsOneTransitive(Object[] direct,
- NestedSet<E> transitive) {
- return new StableManyDirectOneTransitiveNestedSet<>(direct, transitive);
- }
-
- @Override
- public <E> NestedSet<E> onlyOneTransitive(NestedSet<E> transitive) {
- return new StableOnlyOneTransitiveNestedSet<>(transitive);
- }
-
- @Override
- public <E> NestedSet<E> onlyManyTransitives(NestedSet[] transitives) {
- return new StableOnlyTransitivesNestedSet<>(transitives);
- }
-
- @Override
- public <E> NestedSet<E> oneDirectManyTransitive(Object direct, NestedSet[] transitives) {
- return new StableOneDirectManyTransitive<>(direct, transitives);
- }
-
- @Override
- public <E> NestedSet<E> manyDirectManyTransitive(Object[] directs, NestedSet[] transitives) {
- return new StableManyDirectManyTransitive<>(directs, transitives);
- }
-
- @Override
- public <E> NestedSet<E> oneDirect(final E element) {
- return new StableSingleDirectNestedSet<>(element);
- }
-
- private static class StableOnlyDirectsNestedSet<E> extends OnlyDirectsNestedSet<E> {
-
- StableOnlyDirectsNestedSet(Object[] directs) { super(directs); }
-
- @Override
- public Order getOrder() { return Order.STABLE_ORDER; }
- }
-
- private static class StableOneDirectOneTransitiveNestedSet<E> extends
- OneDirectOneTransitiveNestedSet<E> {
-
- private StableOneDirectOneTransitiveNestedSet(E direct, NestedSet<E> transitive) {
- super(direct, transitive);
- }
-
- @Override
- public Order getOrder() { return Order.STABLE_ORDER; }
- }
-
- private static class StableOneDirectManyTransitive<E> extends OneDirectManyTransitive<E> {
-
- private StableOneDirectManyTransitive(Object direct, NestedSet[] transitive) {
- super(direct, transitive);
- }
-
- @Override
- public Order getOrder() { return Order.STABLE_ORDER; }
- }
-
- private static class StableManyDirectManyTransitive<E> extends ManyDirectManyTransitive<E> {
-
- private StableManyDirectManyTransitive(Object[] directs, NestedSet[] transitives) {
- super(directs, transitives);
- }
-
- @Override
- public Order getOrder() { return Order.STABLE_ORDER; }
- }
-
- private static class StableOnlyOneTransitiveNestedSet<E> extends OnlyOneTransitiveNestedSet<E> {
-
- private StableOnlyOneTransitiveNestedSet(NestedSet<E> transitive) { super(transitive); }
-
- @Override
- public Order getOrder() { return Order.STABLE_ORDER; }
- }
-
- private static class StableManyDirectOneTransitiveNestedSet<E> extends
- ManyDirectOneTransitiveNestedSet<E> {
-
- private StableManyDirectOneTransitiveNestedSet(Object[] direct,
- NestedSet<E> transitive) { super(direct, transitive); }
-
- @Override
- public Order getOrder() { return Order.STABLE_ORDER; }
- }
-
- private static class StableOnlyTransitivesNestedSet<E> extends OnlyTransitivesNestedSet<E> {
-
- private StableOnlyTransitivesNestedSet(NestedSet[] transitives) { super(transitives); }
-
- @Override
- public Order getOrder() { return Order.STABLE_ORDER; }
- }
-
- private static class StableImmutableListDirectsNestedSet<E> extends
- ImmutableListDirectsNestedSet<E> {
-
- private StableImmutableListDirectsNestedSet(ImmutableList<E> directs) { super(directs); }
-
- @Override
- public Order getOrder() {
- return Order.STABLE_ORDER;
- }
- }
-
- private static class StableSingleDirectNestedSet<E> extends SingleDirectNestedSet<E> {
-
- private StableSingleDirectNestedSet(E element) { super(element); }
-
- @Override
- public Order getOrder() { return Order.STABLE_ORDER; }
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Uniqueifier.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Uniqueifier.java
deleted file mode 100644
index ef17173..0000000
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Uniqueifier.java
+++ /dev/null
@@ -1,26 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-/**
- * Helps reduce a sequence of potentially duplicated elements to a sequence of unique elements.
- */
-interface Uniqueifier {
-
- /**
- * Returns true if-and-only-if this is the first time that this {@link Uniqueifier}'s method has
- * been called with this Object. This uses Object.equals-type equality for the comparison.
- */
- public boolean isUnique(Object o);
-}
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/ProtoSupport.java b/src/main/java/com/google/devtools/build/lib/rules/objc/ProtoSupport.java
index 715920b..d53d37d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/ProtoSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/ProtoSupport.java
@@ -26,6 +26,7 @@
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
+import com.google.common.collect.Ordering;
import com.google.devtools.build.lib.actions.Artifact;
import com.google.devtools.build.lib.analysis.PrerequisiteArtifacts;
import com.google.devtools.build.lib.analysis.RuleConfiguredTarget.Mode;
@@ -401,7 +402,10 @@
}
private String getProtoInputListFileContents() {
- return Artifact.joinExecPaths("\n", getFilteredProtoSources());
+ // Sort the file names to make the remote action key independent of the precise deps structure.
+ // compile_protos.py will sort the input list anyway.
+ Iterable<Artifact> sorted = Ordering.natural().immutableSortedCopy(getFilteredProtoSources());
+ return Artifact.joinExecPaths("\n", sorted);
}
private PathFragment getWorkspaceRelativeOutputDir() {
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/ExpanderTestBase.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/ExpanderTestBase.java
index aff8e2c..8877f71 100644
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/ExpanderTestBase.java
+++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/ExpanderTestBase.java
@@ -23,7 +23,6 @@
import org.junit.Test;
-import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
@@ -45,7 +44,7 @@
public void simple() {
NestedSet<String> s = prepareBuilder("c", "a", "b").build();
- assertTrue(Arrays.equals(simpleResult().toArray(), s.directMembers()));
+ assertEquals(simpleResult(), s.toList());
assertSetContents(simpleResult(), s);
}
@@ -53,7 +52,7 @@
public void simpleNoDuplicates() {
NestedSet<String> s = prepareBuilder("c", "a", "a", "a", "b").build();
- assertTrue(Arrays.equals(simpleResult().toArray(), s.directMembers()));
+ assertEquals(simpleResult(), s.toList());
assertSetContents(simpleResult(), s);
}
@@ -94,7 +93,6 @@
NestedSet<String> s1 = prepareBuilder().add("a").add("c").add("b").build();
NestedSet<String> s2 = prepareBuilder().addAll(ImmutableList.of("a", "c", "b")).build();
- assertTrue(Arrays.equals(s1.directMembers(), s2.directMembers()));
assertCollectionsEqual(s1.toCollection(), s2.toCollection());
assertCollectionsEqual(s1.toList(), s2.toList());
assertCollectionsEqual(Lists.newArrayList(s1), Lists.newArrayList(s2));
@@ -106,7 +104,6 @@
NestedSet<String> s2 = prepareBuilder().add("a").addAll(ImmutableList.of("b", "c")).add("d")
.build();
- assertTrue(Arrays.equals(s1.directMembers(), s2.directMembers()));
assertCollectionsEqual(s1.toCollection(), s2.toCollection());
assertCollectionsEqual(s1.toList(), s2.toList());
assertCollectionsEqual(Lists.newArrayList(s1), Lists.newArrayList(s2));
@@ -140,7 +137,6 @@
NestedSet<String> b = prepareBuilder("b").addTransitive(c).build();
NestedSet<String> a = prepareBuilder("a").addTransitive(b).build();
- assertTrue(Arrays.equals(new String[]{"a"}, a.directMembers()));
assertSetContents(chainResult(), a);
}
@@ -151,7 +147,6 @@
NestedSet<String> b = prepareBuilder("b").addTransitive(d).build();
NestedSet<String> a = prepareBuilder("a").addTransitive(b).addTransitive(c).build();
- assertTrue(Arrays.equals(new String[]{"a"}, a.directMembers()));
assertSetContents(diamondResult(), a);
}
@@ -208,20 +203,6 @@
assertEquals(expanderOrder(), s.getOrder());
}
- /**
- * In case we have inner NestedSets with different order (allowed by the builder). We should
- * maintain the order of the top-level NestedSet.
- */
- @Test
- public void regressionOnOneTransitiveDep() {
- NestedSet<String> subsub = NestedSetBuilder.<String>stableOrder().add("c").add("a").add("e")
- .build();
- NestedSet<String> sub = NestedSetBuilder.<String>stableOrder().add("b").add("d")
- .addTransitive(subsub).build();
- NestedSet<String> top = prepareBuilder().addTransitive(sub).build();
- assertSetContents(nestedResult(), top);
- }
-
@Test
public void nestingValidation() {
for (Order ordering : Order.values()) {
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 5ffc7f1..b72f89c 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
@@ -13,7 +13,6 @@
// 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.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
@@ -27,8 +26,6 @@
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;
-import java.util.Arrays;
-
/**
* Tests for {@link com.google.devtools.build.lib.collect.nestedset.NestedSet}.
*/
@@ -45,8 +42,7 @@
public void simple() {
NestedSet<String> set = nestedSetBuilder("a").build();
- assertTrue(Arrays.equals(new String[]{"a"}, set.directMembers()));
- assertThat(set.transitiveSets()).isEmpty();
+ assertEquals(ImmutableList.of("a"), set.toList());
assertFalse(set.isEmpty());
}
@@ -59,15 +55,15 @@
@Test
public void nestedToString() {
- NestedSet<String> b = nestedSetBuilder("b").build();
- NestedSet<String> c = nestedSetBuilder("c").build();
+ NestedSet<String> b = nestedSetBuilder("b1", "b2").build();
+ NestedSet<String> c = nestedSetBuilder("c1", "c2").build();
- assertEquals("{a, {b}}",
+ assertEquals("{{b1, b2}, a}",
nestedSetBuilder("a").addTransitive(b).build().toString());
- assertEquals("{a, {b}, {c}}",
+ assertEquals("{{b1, b2}, {c1, c2}, a}",
nestedSetBuilder("a").addTransitive(b).addTransitive(c).build().toString());
- assertEquals("{b}", nestedSetBuilder().addTransitive(b).build().toString());
+ assertEquals("{b1, b2}", nestedSetBuilder().addTransitive(b).build().toString());
}
@Test
@@ -148,13 +144,6 @@
return new SetWrapper<E>(builder.build());
}
- // Same as flat(), but allows duplicate elements.
- @SafeVarargs
- private static <E> SetWrapper<E> flatWithDuplicates(E... directMembers) {
- return new SetWrapper<E>(
- NestedSetBuilder.wrap(Order.STABLE_ORDER, ImmutableList.copyOf(directMembers)));
- }
-
@SafeVarargs
private static <E> SetWrapper<E> nest(SetWrapper<E>... nested) {
NestedSetBuilder<E> builder = NestedSetBuilder.stableOrder();
@@ -191,16 +180,16 @@
.addEqualityGroup(flat(3),
flat(3),
flat(3, 3)) // Element de-duplication.
- .addEqualityGroup(flatWithDuplicates(3, 3))
.addEqualityGroup(flat(4),
nest(flat(4))) // Automatic elision of one-element nested sets.
.addEqualityGroup(NestedSetBuilder.<Integer>linkOrder().add(4).build())
.addEqualityGroup(nestedSetBuilder("4").build()) // Like flat("4").
.addEqualityGroup(flat(3, 4),
flat(3, 4))
- // Shallow equality means that {{3},{5}} != {{3},{5}}.
- .addEqualityGroup(nest(flat(3), flat(5)))
- .addEqualityGroup(nest(flat(3), flat(5)))
+ // Make a couple sets deep enough that shallowEquals() fails.
+ // If this test case fails because you improve the representation, just delete it.
+ .addEqualityGroup(nest(nest(flat(3, 4), flat(5)), nest(flat(6, 7), flat(8))))
+ .addEqualityGroup(nest(nest(flat(3, 4), flat(5)), nest(flat(6, 7), flat(8))))
.addEqualityGroup(nest(myRef),
nest(myRef),
nest(myRef, myRef)) // Set de-duplication.
diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifierTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifierTest.java
deleted file mode 100644
index 13b363b..0000000
--- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifierTest.java
+++ /dev/null
@@ -1,132 +0,0 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.collect.nestedset;
-
-import static org.junit.Assert.assertEquals;
-
-import com.google.common.collect.ImmutableList;
-import com.google.devtools.build.lib.util.Preconditions;
-
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.LinkedHashSet;
-import java.util.List;
-import java.util.Random;
-
-/**
- * Tests for {@link RecordingUniqueifier}.
- */
-@RunWith(JUnit4.class)
-public class RecordingUniqueifierTest {
-
- private static final Random RANDOM = new Random();
-
- private static final int VERY_SMALL = 3; // one byte
- private static final int SMALL = 11; // two bytes
- private static final int MEDIUM = 18; // three bytes -- unmemoed
- // For this one, the "* 8" is a bytes to bits (1 memo is 1 bit)
- private static final int LARGE = (RecordingUniqueifier.LENGTH_THRESHOLD * 8) + 3;
-
- private static final int[] SIZES = new int[] {VERY_SMALL, SMALL, MEDIUM, LARGE};
-
- private void doTest(int uniqueInputs, int deterministicHeadSize) throws Exception {
- Preconditions.checkArgument(deterministicHeadSize <= uniqueInputs,
- "deterministicHeadSize must be smaller than uniqueInputs");
-
- // Setup
-
- List<Integer> inputList = new ArrayList<>(uniqueInputs);
- Collection<Integer> inputsDeduped = new LinkedHashSet<>(uniqueInputs);
-
- for (int i = 0; i < deterministicHeadSize; i++) { // deterministic head
- inputList.add(i);
- inputsDeduped.add(i);
- }
-
- while (inputsDeduped.size() < uniqueInputs) { // random selectees
- Integer i = RANDOM.nextInt(uniqueInputs);
- inputList.add(i);
- inputsDeduped.add(i);
- }
-
- // Unmemoed run
-
- List<Integer> firstList = new ArrayList<>(uniqueInputs);
- RecordingUniqueifier recordingUniqueifier = new RecordingUniqueifier();
- for (Integer i : inputList) {
- if (recordingUniqueifier.isUnique(i)) {
- firstList.add(i);
- }
- }
-
- // Potentially memo'ed run
-
- List<Integer> secondList = new ArrayList<>(uniqueInputs);
- Object memo = recordingUniqueifier.getMemo();
- Uniqueifier uniqueifier = RecordingUniqueifier.createReplayUniqueifier(memo);
- for (Integer i : inputList) {
- if (uniqueifier.isUnique(i)) {
- secondList.add(i);
- }
- }
-
- // Evaluate results
-
- inputsDeduped = ImmutableList.copyOf(inputsDeduped);
- assertEquals("Unmemo'ed run has unexpected contents", inputsDeduped, firstList);
- assertEquals("Memo'ed run has unexpected contents", inputsDeduped, secondList);
- }
-
- private void doTestWithLucidException(int uniqueInputs, int deterministicHeadSize)
- throws Exception {
- try {
- doTest(uniqueInputs, deterministicHeadSize);
- } catch (Exception e) {
- throw new Exception("Failure in size: " + uniqueInputs, e);
- }
- }
-
- @Test
- public void noInputs() throws Exception {
- doTestWithLucidException(0, 0);
- }
-
- @Test
- public void allUnique() throws Exception {
- for (int size : SIZES) {
- doTestWithLucidException(size, size);
- }
- }
-
- @Test
- public void fuzzedWithDeterministic2() throws Exception {
- // The way that it is used, we know that the first two additions are not equal.
- // Optimizations were made for this case in small memos.
- for (int size : SIZES) {
- doTestWithLucidException(size, 2);
- }
- }
-
- @Test
- public void fuzzedWithDeterministic2_otherSizes() throws Exception {
- for (int i = 0; i < 100; i++) {
- int size = RANDOM.nextInt(10000) + 2;
- doTestWithLucidException(size, 2);
- }
- }
-}
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
index 7679e39..73e5f1b 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
@@ -654,7 +654,7 @@
public void testClassObjectCannotAccessNestedSet() throws Exception {
new SkylarkTest()
.update("mock", new MockClassObject())
- .testIfExactError("Type is not allowed in Skylark: EmptyNestedSet", "v = mock.nset");
+ .testIfExactError("Type is not allowed in Skylark: NestedSet", "v = mock.nset");
}
@Test
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java
index 979b945..dae2667 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java
@@ -178,38 +178,6 @@
}
@Test
- public void testSetOuterOrderWins() throws Exception {
- // The order of the outer set should define the final iteration order,
- // no matter what the order of nested sets is
- /*
- * Set: {4, 44, {1, 11, {2, 22}}}
- * PRE: 4, 44, 1, 11, 2, 22 (Link)
- * POST: 2, 22, 1, 11, 4, 44 (Stable)
- *
- */
- Order[] orders = {Order.STABLE_ORDER, Order.LINK_ORDER};
- String[] expected = {
- "set([\"2\", \"22\", \"1\", \"11\", \"4\", \"44\"])",
- "set([\"4\", \"44\", \"1\", \"11\", \"2\", \"22\"], order = \"link\")"};
-
- for (int i = 0; i < 2; ++i) {
- Order outerOrder = orders[i];
- Order innerOrder = orders[1 - i];
-
- SkylarkNestedSet inner1 =
- new SkylarkNestedSet(innerOrder, Tuple.of("1", "11"), null);
- SkylarkNestedSet inner2 =
- new SkylarkNestedSet(innerOrder, Tuple.of("2", "22"), null);
- SkylarkNestedSet innerUnion = new SkylarkNestedSet(inner1, inner2, null);
- SkylarkNestedSet result =
- new SkylarkNestedSet(outerOrder, Tuple.of("4", "44"), null);
- result = new SkylarkNestedSet(result, innerUnion, null);
-
- assertThat(result.toString()).isEqualTo(expected[i]);
- }
- }
-
- @Test
public void testSetOrderCompatibility() throws Exception {
// Two sets are compatible if
// (a) both have the same order or
