diff options
Diffstat (limited to 'src/main/java/com/google/devtools/build/lib/collect/nestedset')
27 files changed, 2433 insertions, 0 deletions
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 new file mode 100644 index 0000000000..5ac8610438 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/CompileOrderExpander.java @@ -0,0 +1,48 @@ +// Copyright 2014 Google Inc. 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 constructing Java classpaths. + */ +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 new file mode 100644 index 0000000000..178f9a50b3 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/CompileOrderNestedSetFactory.java @@ -0,0 +1,152 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..5889ba8bf1 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/EmptyNestedSet.java @@ -0,0 +1,87 @@ +// Copyright 2014 Google Inc. 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.hash(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 new file mode 100644 index 0000000000..12bf222be5 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/ImmutableListDirectsNestedSet.java @@ -0,0 +1,88 @@ +// Copyright 2014 Google Inc. 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> { + + 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(); + } + + @Override + NestedSet[] transitiveSets() { + return 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) 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 new file mode 100644 index 0000000000..603ac15201 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderExpander.java @@ -0,0 +1,105 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..9e23793ac7 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderNestedSetFactory.java @@ -0,0 +1,152 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..05ba2e8f14 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/ManyDirectManyTransitive.java @@ -0,0 +1,63 @@ +// Copyright 2014 Google Inc. 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) other).directs) + && Arrays.equals(transitives, ((ManyDirectManyTransitive) 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 new file mode 100644 index 0000000000..cdb4f04b1a --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/ManyDirectOneTransitiveNestedSet.java @@ -0,0 +1,63 @@ +// Copyright 2014 Google Inc. 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) other).directs) + && transitive == ((ManyDirectOneTransitiveNestedSet) 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 new file mode 100644 index 0000000000..2a7f1b6c1f --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/MemoizedUniquefierNestedSet.java @@ -0,0 +1,74 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..6c49103168 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderExpander.java @@ -0,0 +1,54 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..4677938222 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderNestedSetFactory.java @@ -0,0 +1,153 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..da074e04f6 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java @@ -0,0 +1,127 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.collect.nestedset; + +import com.google.common.base.Joiner; + +import java.io.Serializable; +import java.util.Collection; +import java.util.Iterator; +import java.util.List; +import java.util.Set; + +import javax.annotation.Nullable; + +/** + * A list-like iterable that supports efficient nesting. + * + * @see NestedSetBuilder + */ +public abstract class NestedSet<E> implements Iterable<E>, Serializable { + + NestedSet() {} + + /** + * Returns the ordering of this nested set. + */ + public abstract Order getOrder(); + + /** + * 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. + */ + 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(); + + /** + * Returns true if the set is empty. + */ + public abstract boolean isEmpty(); + + /** + * Returns a collection of all unique elements of this set (including subsets) + * in an implementation-specified order as a {@code Collection}. + * + * <p>If you do not need a Collection and an Iterable is enough, use the + * nested set itself as an Iterable. + */ + public Collection<E> toCollection() { + return toList(); + } + + /** + * Returns a collection of all unique elements of this set (including subsets) + * in an implementation-specified order as a {code List}. + * + * <p>Use {@link #toCollection} when possible for better efficiency. + */ + public abstract List<E> toList(); + + /** + * Returns a collection of all unique elements of this set (including subsets) + * in an implementation-specified order as a {@code Set}. + * + * <p>Use {@link #toCollection} when possible for better efficiency. + */ + public abstract Set<E> toSet(); + + /** + * Returns true if this set is equal to {@code other} based on the top-level + * elements and object identity (==) of direct subsets. As such, this function + * can fail to equate {@code this} with another {@code NestedSet} that holds + * the same elements. It will never fail to detect that two {@code NestedSet}s + * are different, however. + * + * @param other the {@code NestedSet} to compare against. + */ + public abstract boolean shallowEquals(@Nullable NestedSet<? extends E> other); + + /** + * Returns a hash code that produces a notion of identity that is consistent with + * {@link #shallowEquals}. In other words, if two {@code NestedSet}s are equal according + * to {@code #shallowEquals}, then they return the same {@code shallowHashCode}. + * + * <p>The main reason for having these separate functions instead of reusing + * 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 + "}"; + } + + @Override + public Iterator<E> iterator() { return new NestedSetLazyIterator<>(this); } + +} 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 new file mode 100644 index 0000000000..327fcdbe5c --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetBuilder.java @@ -0,0 +1,253 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.collect.nestedset; + +import static com.google.common.collect.Iterables.getOnlyElement; + +import com.google.common.base.Preconditions; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.Iterables; + +import java.util.LinkedHashSet; + +/** + * 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}. + */ +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<>(); + + public NestedSetBuilder(Order order) { + this.order = order; + } + + /** Returns whether the set to be built is empty. */ + public boolean isEmpty() { + return items.isEmpty() && transitiveSets.isEmpty(); + } + + /** + * Add an element. + * + * <p>Preserves ordering of added elements. Discards duplicate values. + * Throws an exception if a null value is passed in. + * + * <p>The collections of the direct members of the set and the nested sets are + * kept separate, so the order between multiple add/addAll calls matters, + * and the order between multiple addTransitive calls matters, but the order + * between add/addAll and addTransitive does not. + * + * @return the builder. + */ + @SuppressWarnings("unchecked") // B is the type of the concrete subclass + public NestedSetBuilder<E> add(E element) { + Preconditions.checkNotNull(element); + items.add(element); + return this; + } + + /** + * Adds a collection of elements to the set. + * + * <p>This is equivalent to invoking {@code add} for every item of the collection in iteration + * order. + * + * <p>The collections of the direct members of the set and the nested sets are kept separate, so + * the order between multiple add/addAll calls matters, and the order between multiple + * addTransitive calls matters, but the order between add/addAll and addTransitive does not. + * + * @return the builder. + */ + @SuppressWarnings("unchecked") // B is the type of the concrete subclass + public NestedSetBuilder<E> addAll(Iterable<? extends E> elements) { + Preconditions.checkNotNull(elements); + Iterables.addAll(items, elements); + return this; + } + + /** + * @deprecated Use {@link #addTransitive} to avoid excessive memory use. + */ + @Deprecated + public NestedSetBuilder<E> addAll(NestedSet<E> elements) { + // Do not delete this method, or else addAll(Iterable) calls with a NestedSet argument + // will not be flagged. + Iterable<E> it = elements; + addAll(it); + return this; + } + + /** + * Adds another nested set to this set. + * + * <p>Preserves ordering of added nested sets. Discards duplicate values. Throws an exception if + * a null value is passed in. + * + * <p>The collections of the direct members of the set and the nested sets are kept separate, so + * the order between multiple add/addAll calls matters, and the order between multiple + * 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. + * + * @return the builder. + */ + public NestedSetBuilder<E> addTransitive(NestedSet<? extends E> subset) { + Preconditions.checkNotNull(subset); + if (subset.getOrder() != order && order != Order.STABLE_ORDER + && subset.getOrder() != Order.STABLE_ORDER) { + // Note that this check is not strictly necessary, although keeping the nested set types + // consistent helps readability and protects against bugs. The polymorphism regarding + // STABLE_ORDER is allowed in order to be able to, e.g., include an arbitrary nested set in + // the inputs of an action, or include a nested set that is indifferent to its order in + // multiple nested sets. + throw new IllegalStateException(subset.getOrder() + " != " + order); + } + if (!subset.isEmpty()) { + transitiveSets.add(subset); + } + return this; + } + + /** + * Builds the actual nested set. + * + * <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<?>. + @SuppressWarnings("unchecked") + public NestedSet<E> build() { + if (isEmpty()) { + return order.emptySet(); + } + + // 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; + 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])); + } + } + } + + /** + * 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. + */ + 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 { + return order.factory.onlyDirects(wrappedList); + } + } + + + /** + * 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)); + } + + /** + * Creates an empty nested set. + */ + public static <E> NestedSet<E> emptySet(Order order) { + return order.emptySet(); + } + + /** + * Creates a builder for stable order nested sets. + */ + public static <E> NestedSetBuilder<E> stableOrder() { + return new NestedSetBuilder<>(Order.STABLE_ORDER); + } + + /** + * Creates a builder for compile order nested sets. + */ + public static <E> NestedSetBuilder<E> compileOrder() { + return new NestedSetBuilder<>(Order.COMPILE_ORDER); + } + + /** + * Creates a builder for link order nested sets. + */ + public static <E> NestedSetBuilder<E> linkOrder() { + return new NestedSetBuilder<>(Order.LINK_ORDER); + } + + /** + * Creates a builder for naive link order nested sets. + */ + public static <E> NestedSetBuilder<E> naiveLinkOrder() { + return new NestedSetBuilder<>(Order.NAIVE_LINK_ORDER); + } +} 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 new file mode 100644 index 0000000000..c04c39d0ba --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetExpander.java @@ -0,0 +1,30 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..99fb8bbfd3 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFactory.java @@ -0,0 +1,55 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..c873d56eef --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetLazyIterator.java @@ -0,0 +1,53 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..ea8b81093f --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java @@ -0,0 +1,96 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.collect.nestedset; + +import com.google.common.base.Preconditions; +import com.google.common.collect.Sets; + +import java.util.Set; + +/** + * NestedSetVisitor facilitates a transitive visitation over a NestedSet, which must be in STABLE + * order. The callback may be called from multiple threads, and must be thread-safe. + * + * <p>The visitation is iterative: The caller may invoke a NestedSet within the top-level NestedSet + * in any order. + * + * <p>Currently this class is only used in Skyframe to facilitate iterative replay of transitive + * warnings/errors. + * + * @param <E> the data type + */ +// @ThreadSafety.ThreadSafe +public final class NestedSetVisitor<E> { + + /** + * For each element of the NestedSet the {@code Reciver} will receive one element during the + * visitation. + */ + public interface Receiver<E> { + void accept(E arg); + } + + private final Receiver<E> callback; + + private final VisitedState<E> visited; + + public NestedSetVisitor(Receiver<E> callback, VisitedState<E> visited) { + this.callback = Preconditions.checkNotNull(callback); + this.visited = Preconditions.checkNotNull(visited); + } + + /** + * Transitively visit a nested set. + * + * @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; + } + + for (NestedSet<E> subset : nestedSet.transitiveSets()) { + visit(subset); + } + for (Object member : nestedSet.directMembers()) { + if (visited.add((E) member)) { + callback.accept((E) member); + } + } + } + + /** 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(); + + public void clear() { + seenSets.clear(); + seenNodes.clear(); + } + + private boolean add(E node) { + return seenNodes.add(node); + } + + private boolean add(NestedSet<E> set) { + return 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 new file mode 100644 index 0000000000..a99883c2d5 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/OneDirectManyTransitive.java @@ -0,0 +1,63 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..9acdba1761 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/OneDirectOneTransitiveNestedSet.java @@ -0,0 +1,61 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..9f7588df08 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/OnlyDirectsNestedSet.java @@ -0,0 +1,88 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..a3e2d1d711 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/OnlyOneTransitiveNestedSet.java @@ -0,0 +1,68 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..5a570538c7 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/OnlyTransitivesNestedSet.java @@ -0,0 +1,62 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..38e663311b --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java @@ -0,0 +1,52 @@ +// Copyright 2014 Google Inc. 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; + +/** + * Type of a nested set (defines order). + */ +public enum Order { + + STABLE_ORDER(new CompileOrderExpander<>(), new StableOrderNestedSetFactory()), + COMPILE_ORDER(new CompileOrderExpander<>(), new CompileOrderNestedSetFactory()), + LINK_ORDER(new LinkOrderExpander<>(), new LinkOrderNestedSetFactory()), + NAIVE_LINK_ORDER(new NaiveLinkOrderExpander<>(), new NaiveLinkOrderNestedSetFactory()); + + private final NestedSetExpander<?> expander; + final NestedSetFactory factory; + private final NestedSet<?> emptySet; + + private Order(NestedSetExpander<?> expander, NestedSetFactory factory) { + this.expander = expander; + this.factory = factory; + this.emptySet = new EmptyNestedSet<Object>(this); + } + + /** + * Returns an empty set of the given ordering. + */ + @SuppressWarnings("unchecked") // Nested sets are immutable, so a downcast is fine. + <E> NestedSet<E> emptySet() { + 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; + } + +} 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 new file mode 100644 index 0000000000..c71f2006c8 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/RecordingUniqueifier.java @@ -0,0 +1,140 @@ +// Copyright 2014 Google Inc. 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.common.base.Preconditions; + +import java.util.BitSet; +import java.util.HashSet; +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 = new HashSet<>(256); + private final BitSet memo = new BitSet(); + private int idx = 0; + + static Uniqueifier createReplayUniqueifier(Object memo) { + if (memo == NO_MEMO) { + return new RecordingUniqueifier(); + } 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 %X.", 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 new file mode 100644 index 0000000000..dc4a5fb2e5 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/SingleDirectNestedSet.java @@ -0,0 +1,68 @@ +// Copyright 2014 Google Inc. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.collect.nestedset; + +import com.google.common.base.Preconditions; +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSet; +import com.google.common.collect.Iterators; + +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 new file mode 100644 index 0000000000..cd0b6183c7 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/StableOrderNestedSetFactory.java @@ -0,0 +1,152 @@ +// Copyright 2014 Google Inc. 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 new file mode 100644 index 0000000000..9421a57f2b --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Uniqueifier.java @@ -0,0 +1,26 @@ +// Copyright 2014 Google Inc. 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); +} |