Fix bug with streaming bounded deps/allrdeps/rdeps.

--
PiperOrigin-RevId: 149431500
MOS_MIGRATED_REVID=149431500

10 files changed, 229 insertions, 80 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java
index 644adcf93d..307e73cdec 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java
@@ -24,6 +24,7 @@ import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.packages.DependencyFilter;
 import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.query2.engine.KeyExtractor;
 import com.google.devtools.build.lib.query2.engine.OutputFormatterCallback;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment;
 import com.google.devtools.build.lib.query2.engine.QueryEvalResult;
@@ -294,4 +295,17 @@ public abstract class AbstractBlazeQueryEnvironment<T>
   public QueryExpressionEvalListener<T> getEvalListener() {
     return evalListener;
   }
+
+  /** A {@link KeyExtractor} that extracts {@code Label}s out of {@link Target}s. */
+  protected static class TargetKeyExtractor implements KeyExtractor<Target, Label> {
+    protected static final TargetKeyExtractor INSTANCE = new TargetKeyExtractor();
+
+    private TargetKeyExtractor() {
+    }
+
+    @Override
+    public Label extractKey(Target element) {
+      return element.getLabel();
+    }
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
index 867ec3d8bf..e9a9dca254 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
@@ -37,14 +37,16 @@ import com.google.devtools.build.lib.pkgcache.TargetProvider;
 import com.google.devtools.build.lib.pkgcache.TransitivePackageLoader;
 import com.google.devtools.build.lib.query2.engine.Callback;
 import com.google.devtools.build.lib.query2.engine.DigraphQueryEvalResult;
+import com.google.devtools.build.lib.query2.engine.MinDepthUniquifier;
 import com.google.devtools.build.lib.query2.engine.OutputFormatterCallback;
 import com.google.devtools.build.lib.query2.engine.QueryEvalResult;
 import com.google.devtools.build.lib.query2.engine.QueryException;
 import com.google.devtools.build.lib.query2.engine.QueryExpression;
 import com.google.devtools.build.lib.query2.engine.QueryExpressionEvalListener;
 import com.google.devtools.build.lib.query2.engine.QueryUtil;
-import com.google.devtools.build.lib.query2.engine.QueryUtil.AbstractUniquifier;
 import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback;
+import com.google.devtools.build.lib.query2.engine.QueryUtil.ThreadSafeMinDepthUniquifierImpl;
+import com.google.devtools.build.lib.query2.engine.QueryUtil.UniquifierImpl;
 import com.google.devtools.build.lib.query2.engine.SkyframeRestartQueryException;
 import com.google.devtools.build.lib.query2.engine.ThreadSafeCallback;
 import com.google.devtools.build.lib.query2.engine.Uniquifier;
@@ -302,12 +304,13 @@ public class BlazeQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
 
   @Override
   public Uniquifier<Target> createUniquifier() {
-    return new AbstractUniquifier<Target, Label>() {
-      @Override
-      protected Label extractKey(Target target) {
-        return target.getLabel();
-      }
-    };
+    return new UniquifierImpl<>(TargetKeyExtractor.INSTANCE);
+  }
+
+  @Override
+  public MinDepthUniquifier<Target> createMinDepthUniquifier() {
+    return new ThreadSafeMinDepthUniquifierImpl<>(
+        TargetKeyExtractor.INSTANCE, /*concurrencyLevel=*/ 1);
   }
 
   private void preloadTransitiveClosure(Set<Target> targets, int maxDepth)
diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
index 3e1410f582..9a5ffd4b34 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
@@ -55,17 +55,21 @@ import com.google.devtools.build.lib.profiler.AutoProfiler;
 import com.google.devtools.build.lib.query2.engine.AllRdepsFunction;
 import com.google.devtools.build.lib.query2.engine.Callback;
 import com.google.devtools.build.lib.query2.engine.FunctionExpression;
+import com.google.devtools.build.lib.query2.engine.KeyExtractor;
+import com.google.devtools.build.lib.query2.engine.MinDepthUniquifier;
 import com.google.devtools.build.lib.query2.engine.OutputFormatterCallback;
 import com.google.devtools.build.lib.query2.engine.QueryEvalResult;
 import com.google.devtools.build.lib.query2.engine.QueryException;
 import com.google.devtools.build.lib.query2.engine.QueryExpression;
 import com.google.devtools.build.lib.query2.engine.QueryExpressionEvalListener;
 import com.google.devtools.build.lib.query2.engine.QueryExpressionMapper;
-import com.google.devtools.build.lib.query2.engine.QueryUtil.AbstractThreadSafeUniquifier;
+import com.google.devtools.build.lib.query2.engine.QueryUtil.ThreadSafeMinDepthUniquifierImpl;
+import com.google.devtools.build.lib.query2.engine.QueryUtil.ThreadSafeUniquifierImpl;
 import com.google.devtools.build.lib.query2.engine.RdepsFunction;
 import com.google.devtools.build.lib.query2.engine.StreamableQueryEnvironment;
 import com.google.devtools.build.lib.query2.engine.TargetLiteral;
 import com.google.devtools.build.lib.query2.engine.ThreadSafeCallback;
+import com.google.devtools.build.lib.query2.engine.ThreadSafeMinDepthUniquifier;
 import com.google.devtools.build.lib.query2.engine.ThreadSafeUniquifier;
 import com.google.devtools.build.lib.query2.engine.Uniquifier;
 import com.google.devtools.build.lib.query2.engine.VariableContext;
@@ -585,18 +589,26 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
   }
 
   @ThreadSafe
+  @Override
+  public ThreadSafeMinDepthUniquifier<Target> createMinDepthUniquifier() {
+    return new ThreadSafeMinDepthUniquifierImpl<>(
+        TargetKeyExtractor.INSTANCE, DEFAULT_THREAD_COUNT);
+  }
+
+  @ThreadSafe
   ThreadSafeUniquifier<Target> createTargetUniquifier() {
-    return new ThreadSafeTargetUniquifier(DEFAULT_THREAD_COUNT);
+    return new ThreadSafeUniquifierImpl<>(TargetKeyExtractor.INSTANCE, DEFAULT_THREAD_COUNT);
   }
 
   @ThreadSafe
   ThreadSafeUniquifier<SkyKey> createSkyKeyUniquifier() {
-    return new ThreadSafeSkyKeyUniquifier(DEFAULT_THREAD_COUNT);
+    return new ThreadSafeUniquifierImpl<>(SkyKeyKeyExtractor.INSTANCE, DEFAULT_THREAD_COUNT);
   }
 
   @ThreadSafe
   ThreadSafeUniquifier<Pair<SkyKey, SkyKey>> createReverseDepSkyKeyUniquifier() {
-    return new ThreadSafeReverseDepSkyKeyUniquifier(DEFAULT_THREAD_COUNT);
+    return new ThreadSafeUniquifierImpl<>(
+        ReverseDepSkyKeyKeyExtractor.INSTANCE, DEFAULT_THREAD_COUNT);
   }
 
   private Pair<TargetPattern, ImmutableSet<PathFragment>> getPatternAndExcludes(String pattern)
@@ -1034,7 +1046,8 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
   void getRBuildFiles(Collection<PathFragment> fileIdentifiers, Callback<Target> callback)
       throws QueryException, InterruptedException {
     Collection<SkyKey> files = getSkyKeysForFileFragments(fileIdentifiers);
-    Uniquifier<SkyKey> keyUniquifier = new ThreadSafeSkyKeyUniquifier(/*concurrencyLevel=*/ 1);
+    Uniquifier<SkyKey> keyUniquifier =
+        new ThreadSafeUniquifierImpl<>(SkyKeyKeyExtractor.INSTANCE, /*concurrencyLevel=*/ 1);
     Collection<SkyKey> current = keyUniquifier.unique(graph.getSuccessfulValues(files).keySet());
     Set<SkyKey> resultKeys = CompactHashSet.create();
     while (!current.isEmpty()) {
@@ -1093,42 +1106,31 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
     }
   }
 
-  private static class ThreadSafeTargetUniquifier
-      extends AbstractThreadSafeUniquifier<Target, Label> {
-    protected ThreadSafeTargetUniquifier(int concurrencyLevel) {
-      super(concurrencyLevel);
-    }
-
-    @Override
-    protected Label extractKey(Target element) {
-      return element.getLabel();
-    }
-  }
+  private static class SkyKeyKeyExtractor implements KeyExtractor<SkyKey, SkyKey> {
+    private static final SkyKeyKeyExtractor INSTANCE = new SkyKeyKeyExtractor();
 
-  private static class ThreadSafeSkyKeyUniquifier
-      extends AbstractThreadSafeUniquifier<SkyKey, SkyKey> {
-    protected ThreadSafeSkyKeyUniquifier(int concurrencyLevel) {
-      super(concurrencyLevel);
+    private SkyKeyKeyExtractor() {
     }
 
     @Override
-    protected SkyKey extractKey(SkyKey element) {
+    public SkyKey extractKey(SkyKey element) {
       return element;
     }
   }
 
   /**
-   * A uniquifer which takes a pair of parent and reverse dep, and uniquify based on the second
-   * element (reverse dep).
+   * A {@link KeyExtractor} which takes a pair of parent and reverse dep, and uses the second
+   * element (reverse dep) as the key.
    */
-  private static class ThreadSafeReverseDepSkyKeyUniquifier
-      extends AbstractThreadSafeUniquifier<Pair<SkyKey, SkyKey>, SkyKey> {
-    protected ThreadSafeReverseDepSkyKeyUniquifier(int concurrencyLevel) {
-      super(concurrencyLevel);
+  private static class ReverseDepSkyKeyKeyExtractor
+      implements KeyExtractor<Pair<SkyKey, SkyKey>, SkyKey> {
+    private static final ReverseDepSkyKeyKeyExtractor INSTANCE = new ReverseDepSkyKeyKeyExtractor();
+
+    private ReverseDepSkyKeyKeyExtractor() {
     }
 
     @Override
-    protected SkyKey extractKey(Pair<SkyKey, SkyKey> element) {
+    public SkyKey extractKey(Pair<SkyKey, SkyKey> element) {
       return element.second;
     }
   }
@@ -1152,7 +1154,7 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
 
     private final OutputFormatterCallback<Target> callback;
     private final ThreadSafeUniquifier<Target> uniquifier =
-        new ThreadSafeTargetUniquifier(DEFAULT_THREAD_COUNT);
+        new ThreadSafeUniquifierImpl<>(TargetKeyExtractor.INSTANCE, DEFAULT_THREAD_COUNT);
     private final Object pendingLock = new Object();
     private List<Target> pending = new ArrayList<>();
     private int batchThreshold;
@@ -1238,27 +1240,27 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
       int depth,
       int batchSize)
       throws QueryException, InterruptedException {
-    Uniquifier<Target> uniquifier = createUniquifier();
+    MinDepthUniquifier<Target> minDepthUniquifier = createMinDepthUniquifier();
     eval(
         expression,
         context,
-        new BatchAllRdepsCallback(uniquifier, universe, callback, depth, batchSize));
+        new BatchAllRdepsCallback(minDepthUniquifier, universe, callback, depth, batchSize));
   }
 
   private class BatchAllRdepsCallback implements Callback<Target> {
-    private final Uniquifier<Target> uniquifier;
+    private final MinDepthUniquifier<Target> minDepthUniquifier;
     private final Predicate<Target> universe;
     private final Callback<Target> callback;
     private final int depth;
     private final int batchSize;
 
     private BatchAllRdepsCallback(
-        Uniquifier<Target> uniquifier,
+        MinDepthUniquifier<Target> minDepthUniquifier,
         Predicate<Target> universe,
         Callback<Target> callback,
         int depth,
         int batchSize) {
-      this.uniquifier = uniquifier;
+      this.minDepthUniquifier = minDepthUniquifier;
       this.universe = universe;
       this.callback = callback;
       this.depth = depth;
@@ -1268,7 +1270,8 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
     @Override
     public void process(Iterable<Target> targets) throws QueryException, InterruptedException {
       Iterable<Target> currentInUniverse = Iterables.filter(targets, universe);
-      ImmutableList<Target> uniqueTargets = uniquifier.unique(currentInUniverse);
+      ImmutableList<Target> uniqueTargets =
+          minDepthUniquifier.uniqueAtDepthLessThanOrEqualTo(currentInUniverse, 0);
       callback.process(uniqueTargets);
 
       // Maintain a queue to allow tracking rdep relationships in BFS order. Rdeps are stored
@@ -1283,7 +1286,7 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
       // processed by callback, the targets are dequeued and not referenced any more, making
       // them available for garbage collection.
 
-      for (int i = 0; i < depth; i++) {
+      for (int curDepth = 1; curDepth <= depth; curDepth++) {
         // The mappings between nodes and their reverse deps must be preserved instead of the
         // reverse deps alone. Later when deserializing dependent nodes using SkyKeys, we need to
         // check if their allowed deps contain the dependencies.
@@ -1321,7 +1324,8 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
               // separately.
               for (Iterable<SkyKey> subList : Iterables.partition(entry.getValue(), batchSize)) {
                 reverseDepsMap.put(entry.getKey(), subList);
-                processReverseDepsMap(uniquifier, reverseDepsMap, callback, reverseDepsQueue);
+                processReverseDepsMap(
+                    minDepthUniquifier, reverseDepsMap, callback, reverseDepsQueue, curDepth);
               }
 
               reverseDepsQueue.poll();
@@ -1329,14 +1333,16 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
             } else {
               // There are some nodes in the pending process list. Process them first and come
               // back to this node later (in next iteration).
-              processReverseDepsMap(uniquifier, reverseDepsMap, callback, reverseDepsQueue);
+              processReverseDepsMap(
+                  minDepthUniquifier, reverseDepsMap, callback, reverseDepsQueue, curDepth);
               batch = 0;
             }
           }
         }
 
         if (!reverseDepsMap.isEmpty()) {
-          processReverseDepsMap(uniquifier, reverseDepsMap, callback, reverseDepsQueue);
+          processReverseDepsMap(
+              minDepthUniquifier, reverseDepsMap, callback, reverseDepsQueue, curDepth);
         }
 
         // If the queue is empty after all nodes in the current level are processed, stop
@@ -1352,14 +1358,16 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
      * list and add next level reverse dep mappings of {@link SkyKey}s to the queue.
      */
     private void processReverseDepsMap(
-        Uniquifier<Target> uniquifier,
+        MinDepthUniquifier<Target> minDepthUniquifier,
         Map<SkyKey, Iterable<SkyKey>> reverseDepsMap,
         Callback<Target> callback,
-        Queue<Map.Entry<SkyKey, Iterable<SkyKey>>> reverseDepsQueue)
+        Queue<Map.Entry<SkyKey, Iterable<SkyKey>>> reverseDepsQueue,
+        int depth)
         throws QueryException, InterruptedException {
       Collection<Target> children = processRawReverseDeps(targetifyValues(reverseDepsMap));
       Iterable<Target> currentInUniverse = Iterables.filter(children, universe);
-      ImmutableList<Target> uniqueChildren = uniquifier.unique(currentInUniverse);
+      ImmutableList<Target> uniqueChildren =
+          minDepthUniquifier.uniqueAtDepthLessThanOrEqualTo(currentInUniverse, depth);
       reverseDepsMap.clear();
 
       if (!uniqueChildren.isEmpty()) {
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.
+}