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 79ff3a9..e7992f4 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
@@ -200,11 +200,29 @@
   }
 
   @Override
+  public Collection<Target> getFwdDeps(Iterable<Target> targets) {
+    Set<Target> result = new HashSet<>();
+    for (Target target : targets) {
+      result.addAll(getFwdDeps(target));
+    }
+    return result;
+  }
+
+  @Override
   public Collection<Target> getReverseDeps(Target target) {
     return getTargetsFromNodes(getNode(target).getPredecessors());
   }
 
   @Override
+  public Collection<Target> getReverseDeps(Iterable<Target> targets) {
+    Set<Target> result = new HashSet<>();
+    for (Target target : targets) {
+      result.addAll(getReverseDeps(target));
+    }
+    return result;
+  }
+
+  @Override
   public Set<Target> getTransitiveClosure(Set<Target> targetNodes) {
     for (Target node : targetNodes) {
       checkBuilt(node);
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 d76a45e..6129c64 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
@@ -167,6 +167,15 @@
   }
 
   @Override
+  public Collection<Target> getFwdDeps(Iterable<Target> targets) {
+    Set<Target> result = new HashSet<>();
+    for (Target target : targets) {
+      result.addAll(getFwdDeps(target));
+    }
+    return result;
+  }
+
+  @Override
   public Collection<Target> getReverseDeps(final Target target) {
     return Collections2.filter(getRawReverseDeps(target), new Predicate<Target>() {
       @Override
@@ -178,6 +187,15 @@
   }
 
   @Override
+  public Collection<Target> getReverseDeps(Iterable<Target> targets) {
+    Set<Target> result = new HashSet<>();
+    for (Target target : targets) {
+      result.addAll(getReverseDeps(target));
+    }
+    return result;
+  }
+
+  @Override
   public Set<Target> getTransitiveClosure(Set<Target> targets) {
     Set<Target> visited = new HashSet<>();
     List<Target> result = new ArrayList<>(targets);
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 2b693eb..25b1da7 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,7 +13,9 @@
 // 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.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;
@@ -66,16 +68,12 @@
     // We need to iterate depthBound + 1 times.
     for (int i = 0; i <= depthBound; i++) {
       List<T> next = new ArrayList<>();
-      for (T node : current) {
-        if (!visited.add(node)) {
-          // Already visited; 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.
-          continue;
-        }
-
-        next.addAll(env.getFwdDeps(node));
-      }
+      // 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;
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 1a7d8d8..a6d6156 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
@@ -155,9 +155,15 @@
   /** Returns the direct forward dependencies of the specified target. */
   Collection<T> getFwdDeps(T target);
 
+  /** Returns the direct forward dependencies of the specified targets. */
+  Collection<T> getFwdDeps(Iterable<T> targets);
+
   /** Returns the direct reverse dependencies of the specified target. */
   Collection<T> getReverseDeps(T target);
 
+  /** Returns the direct reverse dependencies of the specified targets. */
+  Collection<T> getReverseDeps(Iterable<T> targets);
+
   /**
    * Returns the forward transitive closure of all of the targets in
    * "targets".  Callers must ensure that {@link #buildTransitiveClosure}
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 6a8734b..9c61139 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,7 +13,9 @@
 // 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.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;
@@ -72,21 +74,15 @@
     // We need to iterate depthBound + 1 times.
     for (int i = 0; i <= depthBound; i++) {
       List<T> next = new ArrayList<>();
-      for (T node : current) {
-        if (!reachableFromUniverse.contains(node)) {
-          // Traversed outside the transitive closure of the universe.
-          continue;
-        }
-
-        if (!visited.add(node)) {
-          // Already visited; 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.
-          continue;
-        }
-
-        next.addAll(env.getReverseDeps(node));
-      }
+      // Restrict to nodes in our universe.
+      Iterable<T> currentInUniverse = Iterables.filter(current,
+          Predicates.in(reachableFromUniverse));
+      // 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.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;