diff options
Diffstat (limited to 'src/main/java/com/google/devtools/build/lib/query2/engine')
7 files changed, 155 insertions, 31 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/AllRdepsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/AllRdepsFunction.java index 518b67497b..ca3db15a79 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/AllRdepsFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/AllRdepsFunction.java @@ -74,7 +74,7 @@ public class AllRdepsFunction implements QueryFunction { ((StreamableQueryEnvironment<T>) env) .getAllRdeps(args.get(0).getExpression(), universe, context, callback, depth); } else { - final Uniquifier<T> uniquifier = env.createUniquifier(); + final MinDepthUniquifier<T> minDepthUniquifier = env.createMinDepthUniquifier(); env.eval( args.get(0).getExpression(), context, @@ -91,7 +91,8 @@ public class AllRdepsFunction implements QueryFunction { // Filter already visited nodes: if we see a node in a later round, then we don't // need to visit it again, because the depth at which we see it must be greater // than or equal to the last visit. - next.addAll(env.getReverseDeps(uniquifier.unique(currentInUniverse))); + next.addAll(env.getReverseDeps( + minDepthUniquifier.uniqueAtDepthLessThanOrEqualTo(currentInUniverse, i))); callback.process(currentInUniverse); if (next.isEmpty()) { // Exit when there are no more nodes to visit. diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java index 5eca701702..0e618fbb16 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java @@ -60,7 +60,7 @@ final class DepsFunction implements QueryFunction { List<Argument> args, final Callback<T> callback) throws QueryException, InterruptedException { final int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE; - final Uniquifier<T> uniquifier = env.createUniquifier(); + final MinDepthUniquifier<T> minDepthUniquifier = env.createMinDepthUniquifier(); env.eval(args.get(0).getExpression(), context, new Callback<T>() { @Override public void process(Iterable<T> partialResult) throws QueryException, InterruptedException { @@ -72,7 +72,8 @@ final class DepsFunction implements QueryFunction { // Filter already visited nodes: if we see a node in a later round, then we don't need to // visit it again, because the depth at which we see it at must be greater than or equal // to the last visit. - ImmutableList<T> toProcess = uniquifier.unique(current); + ImmutableList<T> toProcess = + minDepthUniquifier.uniqueAtDepthLessThanOrEqualTo(current, i); callback.process(toProcess); current = ImmutableList.copyOf(env.getFwdDeps(toProcess)); if (current.isEmpty()) { diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/KeyExtractor.java b/src/main/java/com/google/devtools/build/lib/query2/engine/KeyExtractor.java new file mode 100644 index 0000000000..37b9ff8ec4 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/KeyExtractor.java @@ -0,0 +1,27 @@ +// Copyright 2017 The Bazel Authors. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; + +/** + * Helper for extracting a key of type {@code K} from an element of type {@code T}. + * + * <p>Depending on the choice of {@code K}, this enables potential memory optimizations. + */ +@ThreadSafe +public interface KeyExtractor<T, K> { + /** Extracts an unique key that can be used to dedupe the given {@code element}. */ + K extractKey(T element); +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/MinDepthUniquifier.java b/src/main/java/com/google/devtools/build/lib/query2/engine/MinDepthUniquifier.java new file mode 100644 index 0000000000..86170047fd --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/MinDepthUniquifier.java @@ -0,0 +1,29 @@ +// Copyright 2017 The Bazel Authors. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.common.collect.ImmutableList; + +/** + * A helper for deduping values that have already been seen at certain "depths". + * + * <p>This is similar to {@link Uniquifier}. + */ +public interface MinDepthUniquifier<T> { + /** + * Returns the subset of {@code newElements} that haven't been seen before at depths less than or + * equal to {@code depth} + */ + ImmutableList<T> uniqueAtDepthLessThanOrEqualTo(Iterable<T> newElements, int depth); +} diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java index bcee46f4c4..ce0ae83521 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java @@ -213,12 +213,20 @@ public interface QueryEnvironment<T> { throws QueryException, InterruptedException; /** - * Creates a Uniquifier for use in a {@code QueryExpression}. Note that the usage of this an + * Creates a Uniquifier for use in a {@code QueryExpression}. Note that the usage of this * uniquifier should not be used for returning unique results to the parent callback. It should * only be used to avoid processing the same elements multiple times within this QueryExpression. */ Uniquifier<T> createUniquifier(); + /** + * Creates a {@link MinDepthUniquifier} for use in a {@code QueryExpression}. Note that the usage + * of this uniquifier should not be used for returning unique results to the parent callback. It + * should only be used to try to avoid processing the same elements multiple times at the same + * depth bound within this QueryExpression. + */ + MinDepthUniquifier<T> createMinDepthUniquifier(); + void reportBuildFileError(QueryExpression expression, String msg) throws QueryException; /** diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryUtil.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryUtil.java index 2d7be2ed74..a558e4581d 100644 --- a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryUtil.java +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryUtil.java @@ -13,13 +13,14 @@ // limitations under the License. package com.google.devtools.build.lib.query2.engine; - 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 java.util.Collections; import java.util.Set; +import java.util.concurrent.ConcurrentMap; +import java.util.concurrent.atomic.AtomicInteger; /** Several query utilities to make easier to work with query callbacks and uniquifiers. */ public final class QueryUtil { @@ -86,53 +87,84 @@ public final class QueryUtil { return callback.getResult(); } - /** A trivial {@link Uniquifier} base class. */ - public abstract static class AbstractUniquifier<T, K> - extends AbstractUniquifierBase<T, K> { + private abstract static class AbstractUniquifierBase<T, K> implements Uniquifier<T> { + @Override + public final ImmutableList<T> unique(Iterable<T> newElements) { + ImmutableList.Builder<T> result = ImmutableList.builder(); + for (T element : newElements) { + if (unique(element)) { + result.add(element); + } + } + return result.build(); + } + } + + /** A trivial {@link Uniquifier} implementation. */ + public static class UniquifierImpl<T, K> extends AbstractUniquifierBase<T, K> { + private final KeyExtractor<T, K> extractor; private final CompactHashSet<K> alreadySeen = CompactHashSet.create(); + public UniquifierImpl(KeyExtractor<T, K> extractor) { + this.extractor = extractor; + } + @Override public final boolean unique(T element) { - return alreadySeen.add(extractKey(element)); + return alreadySeen.add(extractor.extractKey(element)); } - - /** - * Extracts an unique key that can be used to dedupe the given {@code element}. - * - * <p>Depending on the choice of {@code K}, this enables potential memory optimizations. - */ - protected abstract K extractKey(T element); } - /** A trivial {@link ThreadSafeUniquifier} base class. */ - public abstract static class AbstractThreadSafeUniquifier<T, K> + /** A trvial {@link ThreadSafeUniquifier} implementation. */ + public static class ThreadSafeUniquifierImpl<T, K> extends AbstractUniquifierBase<T, K> implements ThreadSafeUniquifier<T> { + private final KeyExtractor<T, K> extractor; private final Set<K> alreadySeen; - protected AbstractThreadSafeUniquifier(int concurrencyLevel) { + public ThreadSafeUniquifierImpl(KeyExtractor<T, K> extractor, int concurrencyLevel) { + this.extractor = extractor; this.alreadySeen = Collections.newSetFromMap( new MapMaker().concurrencyLevel(concurrencyLevel).<K, Boolean>makeMap()); } @Override public final boolean unique(T element) { - return alreadySeen.add(extractKey(element)); + return alreadySeen.add(extractor.extractKey(element)); } - - /** - * Extracts an unique key that can be used to dedupe the given {@code element}. - * - * <p>Depending on the choice of {@code K}, this enables potential memory optimizations. - */ - protected abstract K extractKey(T element); } - private abstract static class AbstractUniquifierBase<T, K> implements Uniquifier<T> { + /** A trivial {@link ThreadSafeMinDepthUniquifier} implementation. */ + public static class ThreadSafeMinDepthUniquifierImpl<T, K> + implements ThreadSafeMinDepthUniquifier<T> { + private final KeyExtractor<T, K> extractor; + private final ConcurrentMap<K, AtomicInteger> alreadySeenAtDepth; + + public ThreadSafeMinDepthUniquifierImpl( + KeyExtractor<T, K> extractor, int concurrencyLevel) { + this.extractor = extractor; + this.alreadySeenAtDepth = new MapMaker().concurrencyLevel(concurrencyLevel).makeMap(); + } + @Override - public final ImmutableList<T> unique(Iterable<T> newElements) { + public final ImmutableList<T> uniqueAtDepthLessThanOrEqualTo( + Iterable<T> newElements, int depth) { ImmutableList.Builder<T> result = ImmutableList.builder(); for (T element : newElements) { - if (unique(element)) { + AtomicInteger newDepth = new AtomicInteger(depth); + AtomicInteger previousDepth = + alreadySeenAtDepth.putIfAbsent(extractor.extractKey(element), newDepth); + if (previousDepth != null) { + if (depth < previousDepth.get()) { + synchronized (previousDepth) { + if (depth < previousDepth.get()) { + // We've seen the element before, but never at a depth this shallow. + previousDepth.set(depth); + result.add(element); + } + } + } + } else { + // We've never seen the element before. result.add(element); } } diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeMinDepthUniquifier.java b/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeMinDepthUniquifier.java new file mode 100644 index 0000000000..9c2b429aa4 --- /dev/null +++ b/src/main/java/com/google/devtools/build/lib/query2/engine/ThreadSafeMinDepthUniquifier.java @@ -0,0 +1,26 @@ +// Copyright 2017 The Bazel Authors. All rights reserved. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +package com.google.devtools.build.lib.query2.engine; + +import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe; + +/** Marker interface for a {@link ThreadSafe} {@link MinDepthUniquifier}. */ +@ThreadSafe +public interface ThreadSafeMinDepthUniquifier<T> extends MinDepthUniquifier<T> { + // There's a natural benign check-then-act race in all concurrent uses of this interface. Thread + // T1 may think it's about to be the first one to process an element at a depth no greater than + // d1. But before t1 finishes processing the element, Thread T2 may think _it's_ about to be first + // one to process an element at a depth no greater than d2. If d2 < d1, then T1's work is probably + // wasted. +} |