Transform Blaze query to be able to work in streamed mode.

--
MOS_MIGRATED_REVID=107249788

25 files changed, 468 insertions, 186 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 73849928bb..11eef89f1d 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
@@ -35,6 +35,7 @@ import com.google.devtools.build.lib.query2.engine.QueryEnvironment;
 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.QueryUtil;
 import com.google.devtools.build.lib.util.BinaryPredicate;
 import com.google.devtools.build.skyframe.WalkableGraph.WalkableGraphFactory;
 
@@ -153,7 +154,7 @@ public abstract class AbstractBlazeQueryEnvironment<T> implements QueryEnvironme
       }
 
       try {
-        resultNodes = expr.eval(this);
+        resultNodes = QueryUtil.evalAll(this, expr);
       } catch (QueryException e) {
         throw new QueryException(e, expr);
       }
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 7422340f69..55b1bc7be5 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
@@ -38,10 +38,14 @@ import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator;
 import com.google.devtools.build.lib.pkgcache.TargetProvider;
 import com.google.devtools.build.lib.pkgcache.TransitivePackageLoader;
 import com.google.devtools.build.lib.query2.engine.BlazeQueryEvalResult;
+import com.google.devtools.build.lib.query2.engine.Callback;
 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.QueryUtil.AbstractUniquifier;
+import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback;
 import com.google.devtools.build.lib.query2.engine.SkyframeRestartQueryException;
+import com.google.devtools.build.lib.query2.engine.Uniquifier;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
 import java.util.Collection;
@@ -262,6 +266,24 @@ public class BlazeQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
     return getTargetsFromNodes(graph.getShortestPath(getNode(from), getNode(to)));
   }
 
+  @Override
+  public void eval(QueryExpression expr, Callback<Target> callback)
+      throws QueryException, InterruptedException {
+    AggregateAllCallback<Target> aggregator = new AggregateAllCallback<>();
+    expr.eval(this, aggregator);
+    callback.process(aggregator.getResult());
+  }
+
+  @Override
+  public Uniquifier<Target> createUniquifier() {
+    return new AbstractUniquifier<Target, Label>() {
+      @Override
+      protected Label extractKey(Target target) {
+        return target.getLabel();
+      }
+    };
+  }
+
   private void preloadTransitiveClosure(Set<Target> targets, int maxDepth) throws QueryException {
     if (maxDepth >= MAX_DEPTH_FULL_SCAN_LIMIT && transitivePackageLoader != null) {
       // Only do the full visitation if "maxDepth" is large enough. Otherwise, the benefits of
diff --git a/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesFunction.java b/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesFunction.java
index 632cfa2e9c..624573c132 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/RBuildFilesFunction.java
@@ -17,6 +17,7 @@ import com.google.common.base.Function;
 import com.google.common.collect.Collections2;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.query2.engine.Callback;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
@@ -66,8 +67,8 @@ public class RBuildFilesFunction implements QueryFunction {
 
   @Override
   @SuppressWarnings("unchecked") // Cast from <Target> to <T>. This will only be used with <Target>.
-  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
-      throws QueryException {
+  public <T> void eval(QueryEnvironment<T> env, QueryExpression expression,
+      List<Argument> args, Callback<T> callback) throws QueryException, InterruptedException {
     if (!(env instanceof SkyQueryEnvironment)) {
       throw new QueryException("rbuildfiles can only be used with SkyQueryEnvironment");
     }
@@ -75,8 +76,8 @@ public class RBuildFilesFunction implements QueryFunction {
     for (Argument arg : args) {
       fileNames.add(arg.getWord());
     }
-    return (Set<T>)
+    callback.process((Set<T>)
         ((SkyQueryEnvironment) env)
-            .getRBuildFiles(Collections2.transform(args, ARGUMENT_TO_PATH_FRAGMENT));
+            .getRBuildFiles(Collections2.transform(args, ARGUMENT_TO_PATH_FRAGMENT)));
   }
 }
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 8c409fd943..54219cc3b1 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
@@ -47,9 +47,13 @@ import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
 import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator;
 import com.google.devtools.build.lib.profiler.Profiler;
 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.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.QueryUtil.AbstractUniquifier;
+import com.google.devtools.build.lib.query2.engine.QueryUtil.AggregateAllCallback;
+import com.google.devtools.build.lib.query2.engine.Uniquifier;
 import com.google.devtools.build.lib.skyframe.FileValue;
 import com.google.devtools.build.lib.skyframe.GraphBackedRecursivePackageProvider;
 import com.google.devtools.build.lib.skyframe.PackageLookupValue;
@@ -299,6 +303,24 @@ public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target> {
   }
 
   @Override
+  public void eval(QueryExpression expr, Callback<Target> callback)
+      throws QueryException, InterruptedException {
+    AggregateAllCallback<Target> aggregator = new AggregateAllCallback<>();
+    expr.eval(this, aggregator);
+    callback.process(aggregator.getResult());
+  }
+
+  @Override
+  public Uniquifier<Target> createUniquifier() {
+    return new AbstractUniquifier<Target, Label>() {
+      @Override
+      protected Label extractKey(Target target) {
+        return target.getLabel();
+      }
+    };
+  }
+
+  @Override
   public Set<Target> getTargetsMatchingPattern(QueryExpression owner, String pattern)
       throws QueryException {
     Set<Target> targets = new LinkedHashSet<>(resolvedTargetPatterns.get(pattern));
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java
index 967493ca1b..b528127661 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java
@@ -13,13 +13,15 @@
 // limitations under the License.
 package com.google.devtools.build.lib.query2.engine;
 
+import com.google.common.base.Predicate;
+import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
 
-import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashSet;
 import java.util.List;
@@ -48,13 +50,11 @@ public class AllPathsFunction implements QueryFunction {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
-      throws QueryException, InterruptedException {
-    QueryExpression from = args.get(0).getExpression();
-    QueryExpression to = args.get(1).getExpression();
+  public <T> void eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args,
+      Callback<T> callback) throws QueryException, InterruptedException {
 
-    Set<T> fromValue = from.eval(env);
-    Set<T> toValue = to.eval(env);
+    Set<T> fromValue = QueryUtil.evalAll(env, args.get(0).getExpression());
+    Set<T> toValue = QueryUtil.evalAll(env, args.get(1).getExpression());
 
     // Algorithm: compute "reachableFromX", the forward transitive closure of
     // the "from" set, then find the intersection of "reachableFromX" with the
@@ -65,18 +65,16 @@ public class AllPathsFunction implements QueryFunction {
     env.buildTransitiveClosure(expression, fromValue, Integer.MAX_VALUE);
 
     Set<T> reachableFromX = env.getTransitiveClosure(fromValue);
-    Set<T> result = intersection(reachableFromX, toValue);
+    Predicate<T> reachable = Predicates.in(reachableFromX);
+    Uniquifier<T> uniquifier = env.createUniquifier();
+    Collection<T> result = uniquifier.unique(intersection(reachableFromX, toValue));
+    callback.process(result);
     Collection<T> worklist = result;
     while (!worklist.isEmpty()) {
       Collection<T> reverseDeps = env.getReverseDeps(worklist);
-      worklist = new ArrayList<>();
-      for (T np : reverseDeps) {
-        if (reachableFromX.contains(np) && result.add(np)) {
-          worklist.add(np);
-        }
-      }
+      worklist = uniquifier.unique(Iterables.filter(reverseDeps, reachable));
+      callback.process(worklist);
     }
-    return result;
   }
 
   /**
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 f844af97d8..ed49ef4f93 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
@@ -22,10 +22,7 @@ import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
 
 import java.util.ArrayList;
-import java.util.Collection;
-import java.util.LinkedHashSet;
 import java.util.List;
-import java.util.Set;
 
 /**
  * An "allrdeps" query expression, which computes the reverse dependencies of the argument within
@@ -58,39 +55,41 @@ public class AllRdepsFunction implements QueryFunction {
    * Breadth-first search from the argument while sticking to nodes satisfying the {@code universe}
    * predicate.
    */
-  protected <T> Set<T> eval(QueryEnvironment<T> env, List<Argument> args, Predicate<T> universe)
+  protected static <T> void eval(final QueryEnvironment<T> env, final List<Argument> args,
+      final Callback<T> callback, final Predicate<T> universe)
       throws QueryException, InterruptedException {
-    Set<T> argumentValue = args.get(0).getExpression().eval(env);
-    int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE;
-    Set<T> visited = new LinkedHashSet<>();
-    Collection<T> current = argumentValue;
+    final Uniquifier<T> uniquifier = env.createUniquifier();
+    final int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE;
+    env.eval(args.get(0).getExpression(), new Callback<T>() {
+      @Override
+      public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
+        Iterable<T> current = partialResult;
+        // We need to iterate depthBound + 1 times.
+        for (int i = 0; i <= depthBound; i++) {
+          List<T> next = new ArrayList<>();
+          // Restrict to nodes satisfying the universe predicate.
+          Iterable<T> currentInUniverse = Iterables.filter(current, universe);
+          // 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)));
+          callback.process(currentInUniverse);
+          if (next.isEmpty()) {
+            // Exit when there are no more nodes to visit.
+            break;
+          }
+          current = next;
+        }
 
-    // We need to iterate depthBound + 1 times.
-    for (int i = 0; i <= depthBound; i++) {
-      List<T> next = new ArrayList<>();
-      // Restrict to nodes satisfying the universe predicate.
-      Iterable<T> currentInUniverse = Iterables.filter(current, universe);
-      // 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(Iterables.filter(currentInUniverse,
-          Predicates.not(Predicates.in(visited)))));
-      Iterables.addAll(visited, currentInUniverse);
-      if (next.isEmpty()) {
-        // Exit when there are no more nodes to visit.
-        break;
       }
-      current = next;
-    }
-
-    return visited;
+    });
 
   }
 
   /** Breadth-first search from the argument. */
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
-      throws QueryException, InterruptedException {
-    return eval(env, args, Predicates.<T>alwaysTrue());
+  public <T> void eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args,
+      Callback<T> callback) throws QueryException, InterruptedException {
+    eval(env, args, callback, Predicates.<T>alwaysTrue());
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java
index 28bb6e7eca..b62565e3f7 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java
@@ -15,9 +15,9 @@ package com.google.devtools.build.lib.query2.engine;
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.query2.engine.Lexer.TokenKind;
 
 import java.util.Collection;
-import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Set;
 
@@ -46,29 +46,35 @@ class BinaryOperatorExpression extends QueryExpression {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException, InterruptedException {
-    Set<T> lhsValue = new LinkedHashSet<>(operands.get(0).eval(env));
+  public <T> void eval(QueryEnvironment<T> env, Callback<T> callback)
+      throws QueryException, InterruptedException {
 
+    if (operator == TokenKind.PLUS || operator == TokenKind.UNION) {
+      for (QueryExpression operand : operands) {
+        env.eval(operand, callback);
+      }
+      return;
+    }
+    // We cannot do differences with partial results. So we fully evaluate the operands
+    Set<T> lhsValue = QueryUtil.evalAll(env, operands.get(0));
     for (int i = 1; i < operands.size(); i++) {
-      Set<T> rhsValue = operands.get(i).eval(env);
+      Set<T> rhsValue = QueryUtil.evalAll(env, operands.get(i));
       switch (operator) {
         case INTERSECT:
         case CARET:
           lhsValue.retainAll(rhsValue);
           break;
-        case UNION:
-        case PLUS:
-          lhsValue.addAll(rhsValue);
-          break;
         case EXCEPT:
         case MINUS:
           lhsValue.removeAll(rhsValue);
           break;
+        case UNION:
+        case PLUS:
         default:
           throw new IllegalStateException("operator=" + operator);
       }
     }
-    return lhsValue;
+    callback.process(lhsValue);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java
index ca8f102a8a..c36f98a29f 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java
@@ -14,6 +14,8 @@
 package com.google.devtools.build.lib.query2.engine;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.collect.CompactHashSet;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
@@ -39,9 +41,17 @@ class BuildFilesFunction implements QueryFunction {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+  public <T> void eval(final QueryEnvironment<T> env, final QueryExpression expression,
+      List<Argument> args, final Callback<T> callback)
       throws QueryException, InterruptedException {
-    return env.getBuildFiles(expression, args.get(0).getExpression().eval(env));
+    env.eval(args.get(0).getExpression(), new Callback<T>() {
+      @Override
+      public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
+        Set<T> result = CompactHashSet.create();
+        Iterables.addAll(result, partialResult);
+        callback.process(env.getBuildFiles(expression, result));
+      }
+    });
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/Callback.java b/src/main/java/com/google/devtools/build/lib/query2/engine/Callback.java
new file mode 100644
index 0000000000..ef9c3cde18
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/Callback.java
@@ -0,0 +1,35 @@
+// Copyright 2015 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;
+
+/**
+ * Query callback to be called by a {@link QueryExpression} when it has part of the computation
+ * result. Assuming the {@code QueryEnvironment} supports it, it would allow the caller
+ * to stream the results.
+ */
+public interface Callback<T> {
+
+  /**
+   * Called by {@code QueryExpression} when it has been able to compute part of the result.
+   *
+   * <p>Note that this method can be called several times for a QueryExpression. Callers
+   * implementing this method should assume that multiple calls can happen.
+   *
+   * @param partialResult Part of the result. Note that from the caller's perspective, it is
+   * guaranteed that no repeated elements will be returned. However {@code QueryExpression}s calling
+   * the callback do not need to maintain this property, as the {@code QueryEnvironment} should
+   * handle the uniqueness.
+   */
+  void process(Iterable<T> partialResult) throws QueryException, InterruptedException;
+}
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 265de4c60d..b7bc59ae5b 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
@@ -13,16 +13,13 @@
 // limitations under the License.
 package com.google.devtools.build.lib.query2.engine;
 
-import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
 
-import java.util.ArrayList;
 import java.util.Collection;
-import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Set;
 
@@ -56,31 +53,31 @@ final class DepsFunction implements QueryFunction {
    * Breadth-first search from the arguments.
    */
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+  public <T> void eval(final QueryEnvironment<T> env, final QueryExpression expression,
+      List<Argument> args, final Callback<T> callback)
       throws QueryException, InterruptedException {
-    Set<T> argumentValue = args.get(0).getExpression().eval(env);
-    int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE;
-    env.buildTransitiveClosure(expression, argumentValue, depthBound);
+    final int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE;
+    final Uniquifier<T> uniquifier = env.createUniquifier();
+    env.eval(args.get(0).getExpression(), new Callback<T>() {
+      @Override
+      public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
+        Collection<T> current = Sets.newHashSet(partialResult);
+        env.buildTransitiveClosure(expression, (Set<T>) current, depthBound);
 
-    Set<T> visited = new LinkedHashSet<>();
-    Collection<T> current = argumentValue;
-
-    // We need to iterate depthBound + 1 times.
-    for (int i = 0; i <= depthBound; i++) {
-      List<T> next = new ArrayList<>();
-      // 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.
-      next.addAll(env.getFwdDeps(Iterables.filter(current,
-          Predicates.not(Predicates.in(visited)))));
-      visited.addAll(current);
-      if (next.isEmpty()) {
-        // Exit when there are no more nodes to visit.
-        break;
+        // We need to iterate depthBound + 1 times.
+        for (int i = 0; i <= depthBound; i++) {
+          // 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);
+          callback.process(toProcess);
+          current = ImmutableList.copyOf(env.getFwdDeps(toProcess));
+          if (current.isEmpty()) {
+            // Exit when there are no more nodes to visit.
+            break;
+          }
+        }
       }
-      current = next;
-    }
-
-    return visited;
+    });
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java
index 57667a25eb..d74056516f 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java
@@ -23,7 +23,6 @@ import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunctio
 
 import java.util.Collection;
 import java.util.List;
-import java.util.Set;
 
 /**
  * A query expression for user-defined query functions.
@@ -38,8 +37,9 @@ public class FunctionExpression extends QueryExpression {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException, InterruptedException {
-    return function.<T>eval(env, this, args);
+  public <T> void eval(QueryEnvironment<T> env, Callback<T> callback)
+      throws QueryException, InterruptedException {
+    function.eval(env, this, args, callback);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java
index 33dc85c36e..a13f42cfb8 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java
@@ -18,9 +18,8 @@ import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
 
-import java.util.LinkedHashSet;
+import java.util.ArrayList;
 import java.util.List;
-import java.util.Set;
 
 /**
  * A label(attr_name, argument) expression, which computes the set of targets
@@ -53,20 +52,28 @@ class LabelsFunction implements QueryFunction {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+  public <T> void eval(final QueryEnvironment<T> env, final QueryExpression expression,
+      final List<Argument> args, final Callback<T> callback)
       throws QueryException, InterruptedException {
-    Set<T> inputs = args.get(1).getExpression().eval(env);
-    Set<T> result = new LinkedHashSet<>();
-    String attrName = args.get(0).getWord();
-    for (T input : inputs) {
-      if (env.getAccessor().isRule(input)) {
-        List<T> targets = env.getAccessor().getLabelListAttr(expression, input, attrName,
-            "in '" + attrName + "' of rule " + env.getAccessor().getLabel(input) + ": ");
-        for (T target : targets) {
-          result.add(env.getOrCreate(target));
+    final String attrName = args.get(0).getWord();
+    final Uniquifier<T> uniquifier = env.createUniquifier();
+    env.eval(args.get(1).getExpression(), new Callback<T>() {
+      @Override
+      public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
+        for (T input : partialResult) {
+          if (env.getAccessor().isRule(input)) {
+            List<T> targets = uniquifier.unique(
+                env.getAccessor().getLabelListAttr(expression, input, attrName,
+                    "in '" + attrName + "' of rule " + env.getAccessor().getLabel(input) + ": "));
+            List<T> result = new ArrayList<>(targets.size());
+            for (T target : targets) {
+              result.add(env.getOrCreate(target));
+            }
+            callback.process(result);
+          }
         }
+
       }
-    }
-    return result;
+    });
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java
index 0fe8fdfde9..2e198077bb 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java
@@ -52,14 +52,19 @@ class LetExpression extends QueryExpression {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException, InterruptedException {
+  public <T> void eval(QueryEnvironment<T> env, Callback<T> callback)
+      throws QueryException, InterruptedException {
     if (!NAME_PATTERN.matcher(varName).matches()) {
       throw new QueryException(this, "invalid variable name '" + varName + "' in let expression");
     }
-    Set<T> varValue = varExpr.eval(env);
+    // We eval all because we would need a stack of variable contexts for implementing setVariable
+    // correctly.
+    Set<T> varValue = QueryUtil.evalAll(env, varExpr);
     Set<T> prevValue = env.setVariable(varName, varValue);
     try {
-      return bodyExpr.eval(env);
+      // Same as varExpr. We cannot pass partial results to the parent without having
+      // a stack of variable contexts.
+      callback.process(QueryUtil.evalAll(env, bodyExpr));
     } finally {
       env.setVariable(varName, prevValue); // restore
     }
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 9d5d21268c..b8c065f936 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
@@ -116,8 +116,8 @@ public interface QueryEnvironment<T> {
      * @param args the input arguments. These are type-checked against the specification returned
      *     by {@link #getArgumentTypes} and {@link #getMandatoryArguments}
      */
-    <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
-        throws QueryException, InterruptedException;
+    <T> void eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args,
+        Callback<T> callback) throws QueryException, InterruptedException;
   }
 
   /**
@@ -188,6 +188,22 @@ public interface QueryEnvironment<T> {
    */
   Set<T> setVariable(String name, Set<T> value);
 
+  /**
+   * Eval an expression {@code expr} and pass the results to the {@code callback}.
+   *
+   * <p>Note that this method should guarantee that the callback does not see repeated elements.
+   * @param expr The expression to evaluate
+   * @param callback The caller callback to notify when results are available
+   */
+  void eval(QueryExpression expr, Callback<T> callback) throws QueryException, InterruptedException;
+
+  /**
+   * Creates a Uniquifier for use in a {@code QueryExpression}. Note that the usage of this an
+   * 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();
+
   void reportBuildFileError(QueryExpression expression, String msg) throws QueryException;
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java
index 26860ef30b..b0ea774219 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java
@@ -14,7 +14,6 @@
 package com.google.devtools.build.lib.query2.engine;
 
 import java.util.Collection;
-import java.util.Set;
 
 /**
  * Base class for expressions in the Blaze query language, revision 2.
@@ -56,18 +55,19 @@ public abstract class QueryExpression {
   protected QueryExpression() {}
 
   /**
-   * Evaluates this query in the specified environment, and returns a subgraph,
-   * concretely represented a new (possibly-immutable) set of target nodes.
+   * Evaluates this query in the specified environment, and notifies the callback with a the result.
+   * Note that it is allowed to notify the callback with partial results instead of just one final
+   * result.
    *
-   * Failures resulting from evaluation of an ill-formed query cause
+   * <p>Failures resulting from evaluation of an ill-formed query cause
    * QueryException to be thrown.
    *
-   * The reporting of failures arising from errors in BUILD files depends on
+   * <p>The reporting of failures arising from errors in BUILD files depends on
    * the --keep_going flag.  If enabled (the default), then QueryException is
    * thrown.  If disabled, evaluation will stumble on to produce a (possibly
    * inaccurate) result, but a result nonetheless.
    */
-  public abstract <T> Set<T> eval(QueryEnvironment<T> env)
+  public abstract <T> void eval(QueryEnvironment<T> env, Callback<T> callback)
       throws QueryException, InterruptedException;
 
   /**
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
new file mode 100644
index 0000000000..f70dcd08c7
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryUtil.java
@@ -0,0 +1,114 @@
+// Copyright 2015 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.base.Predicate;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.collect.CompactHashSet;
+
+import java.util.Set;
+
+/** Several query utilities to make easier to work with query callbacks and uniquifiers. */
+public final class QueryUtil {
+
+  private QueryUtil() { }
+
+  /** A callback that can aggregate all the partial results in one set */
+  public static class AggregateAllCallback<T> implements Callback<T> {
+
+    private final CompactHashSet<T> result = CompactHashSet.create();
+
+    @Override
+    public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
+      Iterables.addAll(result, partialResult);
+    }
+
+    public Set<T> getResult() {
+      return result;
+    }
+
+    @Override
+    public String toString() {
+      return "Aggregate all: " + result;
+    }
+  }
+
+  /**
+   * Fully evaluate a {@code QueryExpression} and return a set with all the results.
+   *
+   * <p>Should ony be used by QueryExpressions when it is the only way of achieving correctness.
+   */
+  public static <T> Set<T> evalAll(QueryEnvironment<T> env, QueryExpression expr)
+      throws QueryException, InterruptedException {
+    AggregateAllCallback<T> callback = new AggregateAllCallback<>();
+    env.eval(expr, callback);
+    return callback.result;
+  }
+
+  /**
+   * Notify {@code parentCallback} only about the events that match {@code retainIfTrue} predicate.
+   *
+   * @param parentCallback The parent callback to notify with the matching elements
+   * @param retainIfTrue A predicate that defines what elements to notify to the parent callback.
+   */
+  public static <T> Callback<T> filteredCallback(final Callback<T> parentCallback,
+      final Predicate<T> retainIfTrue) {
+    return new Callback<T>() {
+      @Override
+      public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
+        Iterable<T> filter = Iterables.filter(partialResult, retainIfTrue);
+        if (!Iterables.isEmpty(filter)) {
+          parentCallback.process(filter);
+        }
+      }
+
+      @Override
+      public String toString() {
+        return "filtered parentCallback of : " + retainIfTrue;
+      }
+    };
+  }
+
+  /**
+   * An uniquifier that uses a CompactHashSet and a key extractor for making the elements unique.
+   *
+   * <p>Using a key extractor allows to improve memory since we don't have to keep the whole element
+   * in the set but just the key.
+   */
+  public abstract static class AbstractUniquifier<T, K> implements Uniquifier<T> {
+
+    private final CompactHashSet<K> alreadySeen = CompactHashSet.create();
+
+    @Override
+    public final ImmutableList<T> unique(Iterable<T> newElements) {
+      ImmutableList.Builder<T> result = ImmutableList.builder();
+      for (T element : newElements) {
+        if (alreadySeen.add(extractKey(element))) {
+          result.add(element);
+        }
+      }
+      return result.build();
+    }
+
+    /** Extracts an unique key that represents the target. For example the label. */
+    protected abstract K extractKey(T t);
+
+    @Override
+    public String toString() {
+      return this.getClass().getName() + " uniquifier :" + alreadySeen;
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java
index 2a0d41c7cc..24d0334df2 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java
@@ -13,6 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.query2.engine;
 
+import com.google.common.base.Predicate;
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
@@ -53,12 +54,13 @@ final class RdepsFunction extends AllRdepsFunction {
    * towards the universe while staying within the transitive closure.
    */
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+  public <T> void eval(QueryEnvironment<T> env, QueryExpression expression,
+      List<Argument> args, Callback<T> callback)
       throws QueryException, InterruptedException {
-    Set<T> universeValue = args.get(0).getExpression().eval(env);
+    Set<T> universeValue = QueryUtil.evalAll(env, args.get(0).getExpression());
     env.buildTransitiveClosure(expression, universeValue, Integer.MAX_VALUE);
 
-    return eval(env, args.subList(1, args.size()),
-        Predicates.in(env.getTransitiveClosure(universeValue)));
+    Predicate<T> universe = Predicates.in(env.getTransitiveClosure(universeValue));
+    eval(env, args.subList(1, args.size()), callback, universe);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java
index 254e658610..7647f4d211 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java
@@ -13,13 +13,12 @@
 // limitations under the License.
 package com.google.devtools.build.lib.query2.engine;
 
+import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
 
-import java.util.LinkedHashSet;
 import java.util.List;
-import java.util.Set;
 import java.util.regex.Pattern;
 
 /**
@@ -31,9 +30,10 @@ abstract class RegexFilterExpression implements QueryFunction {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+  public <T> void eval(final QueryEnvironment<T> env, QueryExpression expression,
+      final List<Argument> args, final Callback<T> callback)
       throws QueryException, InterruptedException {
-    Pattern compiledPattern;
+    final Pattern compiledPattern;
     try {
       compiledPattern = Pattern.compile(getPattern(args));
     } catch (IllegalArgumentException e) {
@@ -41,18 +41,20 @@ abstract class RegexFilterExpression implements QueryFunction {
                                + e.getMessage());
     }
 
-    QueryExpression argument = args.get(args.size() - 1).getExpression();
-
-    Set<T> result = new LinkedHashSet<>();
-    for (T target : argument.eval(env)) {
-      for (String str : getFilterStrings(env, args, target)) {
-        if ((str != null) && compiledPattern.matcher(str).find()) {
-          result.add(target);
-          break;
+    final Predicate<T> matchFilter = new Predicate<T>() {
+      @Override
+      public boolean apply(T target) {
+        for (String str : getFilterStrings(env, args, target)) {
+          if ((str != null) && compiledPattern.matcher(str).find()) {
+            return true;
+          }
         }
+        return false;
       }
-    }
-    return result;
+    };
+
+    env.eval(args.get(args.size() - 1).getExpression(),
+        QueryUtil.filteredCallback(callback, matchFilter));
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java
index 229e3c7078..41aa9281dc 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java
@@ -16,9 +16,7 @@ package com.google.devtools.build.lib.query2.engine;
 import com.google.common.base.Joiner;
 
 import java.util.Collection;
-import java.util.LinkedHashSet;
 import java.util.List;
-import java.util.Set;
 
 /**
  * A set(word, ..., word) expression, which computes the union of zero or more
@@ -48,12 +46,11 @@ class SetExpression extends QueryExpression {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException {
-    Set<T> result = new LinkedHashSet<>();
+  public <T> void eval(QueryEnvironment<T> env, Callback<T> callback)
+      throws QueryException, InterruptedException {
     for (TargetLiteral expr : words) {
-      result.addAll(expr.eval(env));
+      env.eval(expr, callback);
     }
-    return result;
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java
index f6abf368e5..d6885e44f6 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java
@@ -15,12 +15,13 @@ package com.google.devtools.build.lib.query2.engine;
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
 
 import java.util.List;
-import java.util.Set;
+import java.util.concurrent.atomic.AtomicBoolean;
 
 /**
  * A some(x) filter expression, which returns an arbitrary node in set x, or
@@ -48,12 +49,22 @@ class SomeFunction implements QueryFunction {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+  public <T> void eval(QueryEnvironment<T> env, QueryExpression expression,
+      List<Argument> args, final Callback<T> callback)
       throws QueryException, InterruptedException {
-    Set<T> argumentValue = args.get(0).getExpression().eval(env);
-    if (argumentValue.isEmpty()) {
+    final AtomicBoolean someFound = new AtomicBoolean(false);
+    env.eval(args.get(0).getExpression(), new Callback<T>() {
+      @Override
+      public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
+        if (someFound.get() || Iterables.isEmpty(partialResult)) {
+          return;
+        }
+        callback.process(ImmutableSet.of(partialResult.iterator().next()));
+        someFound.set(true);
+      }
+    });
+    if (!someFound.get()) {
       throw new QueryException(expression, "argument set is empty");
     }
-    return ImmutableSet.of(argumentValue.iterator().next());
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java
index 0471d67944..9e2b44392b 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java
@@ -21,7 +21,6 @@ import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
 
-import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
 
@@ -51,10 +50,11 @@ class SomePathFunction implements QueryFunction {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+  public <T> void eval(QueryEnvironment<T> env, QueryExpression expression,
+      List<Argument> args, final Callback<T> callback)
       throws QueryException, InterruptedException {
-    Set<T> fromValue = args.get(0).getExpression().eval(env);
-    Set<T> toValue = args.get(1).getExpression().eval(env);
+    Set<T> fromValue = QueryUtil.evalAll(env, args.get(0).getExpression());
+    Set<T> toValue = QueryUtil.evalAll(env, args.get(1).getExpression());
 
     // Implementation strategy: for each x in "from", compute its forward
     // transitive closure.  If it intersects "to", then do a path search from x
@@ -64,12 +64,9 @@ class SomePathFunction implements QueryFunction {
     env.buildTransitiveClosure(expression, fromValue, Integer.MAX_VALUE);
 
     // This set contains all nodes whose TC does not intersect "toValue".
-    Set<T> done = new HashSet<>();
+    Uniquifier<T> uniquifier = env.createUniquifier();
 
-    for (T x : fromValue) {
-      if (done.contains(x)) {
-        continue;
-      }
+    for (T x : uniquifier.unique(fromValue)) {
       Set<T> xtc = env.getTransitiveClosure(ImmutableSet.of(x));
       SetView<T> result;
       if (xtc.size() > toValue.size()) {
@@ -78,10 +75,11 @@ class SomePathFunction implements QueryFunction {
         result = Sets.intersection(xtc, toValue);
       }
       if (!result.isEmpty()) {
-        return env.getNodesOnPath(x, result.iterator().next());
+        callback.process(env.getNodesOnPath(x, result.iterator().next()));
+        return;
       }
-      done.addAll(xtc);
+      uniquifier.unique(xtc);
     }
-    return ImmutableSet.of();
+    callback.process(ImmutableSet.<T>of());
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java b/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java
index 7faad47f1a..886d9ce801 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java
@@ -41,17 +41,18 @@ final class TargetLiteral extends QueryExpression {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException {
+  public <T> void eval(QueryEnvironment<T> env, Callback<T> callback)
+      throws QueryException, InterruptedException {
     if (isVariableReference()) {
       String varName = LetExpression.getNameFromReference(pattern);
       Set<T> value = env.getVariable(varName);
       if (value == null) {
         throw new QueryException(this, "undefined variable '" + varName + "'");
       }
-      return env.getVariable(varName);
+      callback.process(value);
+    } else {
+      callback.process(env.getTargetsMatchingPattern(this, pattern));
     }
-
-    return env.getTargetsMatchingPattern(this, pattern);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java
index e1d7727f2e..d5479ee6cf 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java
@@ -62,20 +62,24 @@ class TestsFunction implements QueryFunction {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
-      throws QueryException, InterruptedException {
-    Closure<T> closure = new Closure<>(expression, env);
-    Set<T> result = new HashSet<>();
-    for (T target : args.get(0).getExpression().eval(env)) {
-      if (env.getAccessor().isTestRule(target)) {
-        result.add(target);
-      } else if (env.getAccessor().isTestSuite(target)) {
-        for (T test : closure.getTestsInSuite(target)) {
-          result.add(env.getOrCreate(test));
+  public <T> void eval(final QueryEnvironment<T> env, QueryExpression expression,
+      List<Argument> args, final Callback<T> callback) throws QueryException, InterruptedException {
+    final Closure<T> closure = new Closure<>(expression, env);
+
+    env.eval(args.get(0).getExpression(), new Callback<T>() {
+      @Override
+      public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
+        for (T target : partialResult) {
+          if (env.getAccessor().isTestRule(target)) {
+            callback.process(ImmutableList.of(target));
+          } else if (env.getAccessor().isTestSuite(target)) {
+            for (T test : closure.getTestsInSuite(target)) {
+              callback.process(ImmutableList.of(env.getOrCreate(test)));
+            }
+          }
         }
       }
-    }
-    return result;
+    });
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/Uniquifier.java b/src/main/java/com/google/devtools/build/lib/query2/engine/Uniquifier.java
new file mode 100644
index 0000000000..d401921176
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/Uniquifier.java
@@ -0,0 +1,33 @@
+// Copyright 2015 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 class used for deduplication of {@code Iterable}s. If called with repeated elements or multiple
+ * times with repeated elements between calls, it guarantees to output only those elements exactly once.
+ */
+public interface Uniquifier<T> {
+
+  /**
+   * Receives an iterable and returns the list of elements that were not already seen. The
+   * uniqueness need to be guaranteed for elements of the same iterable and multiple calls to the
+   * {@code unique} method.
+   *
+   * @param newElements The new elements to process.
+   * @return The subset of elements not already seen by this Uniquifier.
+   */
+  ImmutableList<T> unique(Iterable<T> newElements);
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/VisibleFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/VisibleFunction.java
index 1f097f2d27..e4d095eecb 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/VisibleFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/VisibleFunction.java
@@ -15,7 +15,6 @@
 package com.google.devtools.build.lib.query2.engine;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
@@ -53,24 +52,26 @@ public class VisibleFunction implements QueryFunction {
   }
 
   @Override
-  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
-      throws QueryException, InterruptedException {
-    Set<T> toSet = args.get(0).getExpression().eval(env);
-    Set<T> targets = args.get(1).getExpression().eval(env);
-
-    ImmutableSet.Builder<T> visible = ImmutableSet.builder();
-    for (T target : targets) {
-      if (visibleToAll(env, toSet, target)) {
-        visible.add(target);
+  public <T> void eval(final QueryEnvironment<T> env, QueryExpression expression,
+      List<Argument> args,
+      final Callback<T> callback) throws QueryException, InterruptedException {
+    final Set<T> toSet = QueryUtil.evalAll(env, args.get(0).getExpression());
+    env.eval(args.get(1).getExpression(), new Callback<T>() {
+      @Override
+      public void process(Iterable<T> partialResult) throws QueryException, InterruptedException {
+        for (T t : partialResult) {
+          if (visibleToAll(env, toSet, t)) {
+            callback.process(ImmutableList.of(t));
+          }
+        }
       }
-    }
-    return visible.build();
+    });
   }
 
   /**
    * Returns true if {@code target} is visible to all targets in {@code toSet}.
    */
-  private <T> boolean visibleToAll(
+  private static <T> boolean visibleToAll(
       QueryEnvironment<T> env, Set<T> toSet, T target) throws QueryException {
     for (T to : toSet) {
       if (!visible(env, to, target)) {
@@ -83,7 +84,7 @@ public class VisibleFunction implements QueryFunction {
   /**
    * Returns true if the target {@code from} is visible to the target {@code to}.
    */
-  public <T> boolean visible(QueryEnvironment<T> env, T to, T from) throws QueryException {
+  public static <T> boolean visible(QueryEnvironment<T> env, T to, T from) throws QueryException {
     Set<QueryVisibility<T>> visiblePackages = env.getAccessor().getVisibility(from);
     for (QueryVisibility<T> spec : visiblePackages) {
       if (spec.contains(to)) {