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 f18b5b3..1945c45 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
@@ -26,7 +26,6 @@
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
 import com.google.common.collect.Multimap;
-import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.cmdline.TargetPattern;
@@ -87,6 +86,13 @@
  * even if the full closure isn't needed.
  */
 public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target> {
+
+  private static final Predicate<Exception> NON_NULL_EXCEPTION = new Predicate<Exception>() {
+    @Override
+    public boolean apply(@Nullable Exception e) {
+      return e != null;
+    }
+  };
   private WalkableGraph graph;
 
   private ImmutableList<TargetPatternKey> universeTargetPatternKeys;
@@ -386,7 +392,7 @@
 
   private Set<Target> filterTargetsNotInGraph(Set<Target> targets) {
     Map<Target, SkyKey> map = Maps.toMap(targets, TARGET_TO_SKY_KEY);
-    Set<SkyKey> present = graph.getDoneValues(map.values()).keySet();
+    Set<SkyKey> present = graph.getSuccessfulValues(map.values()).keySet();
     if (present.size() == targets.size()) {
       // Optimize for case of all targets being in graph.
       return targets;
@@ -493,7 +499,7 @@
       }
     }
     ImmutableMap.Builder<E, Target> result = ImmutableMap.builder();
-    Map<SkyKey, SkyValue> packageMap = graph.getDoneValues(packageKeyToTargetKeyMap.keySet());
+    Map<SkyKey, SkyValue> packageMap = graph.getSuccessfulValues(packageKeyToTargetKeyMap.keySet());
     for (Map.Entry<SkyKey, SkyValue> entry : packageMap.entrySet()) {
       for (E targetKey : packageKeyToTargetKeyMap.get(entry.getKey())) {
         try {
@@ -542,7 +548,7 @@
             PackageLookupValue.key(PackageIdentifier.createInDefaultRepo(pathFragment)),
             pathFragment);
       }
-      Map<SkyKey, SkyValue> lookupValues = graph.getDoneValues(keys.keySet());
+      Map<SkyKey, SkyValue> lookupValues = graph.getSuccessfulValues(keys.keySet());
       for (Map.Entry<SkyKey, SkyValue> entry : lookupValues.entrySet()) {
         PackageLookupValue packageLookupValue = (PackageLookupValue) entry.getValue();
         if (packageLookupValue.packageExists()) {
@@ -575,7 +581,7 @@
   @Nullable
   Set<Target> getRBuildFiles(Collection<PathFragment> fileIdentifiers) {
     Collection<SkyKey> files = getSkyKeysForFileFragments(fileIdentifiers);
-    Collection<SkyKey> current = graph.getDoneValues(files).keySet();
+    Collection<SkyKey> current = graph.getSuccessfulValues(files).keySet();
     Set<SkyKey> resultKeys = CompactHashSet.create();
     while (!current.isEmpty()) {
       Collection<Iterable<SkyKey>> reverseDeps = graph.getReverseDeps(current).values();
@@ -589,11 +595,7 @@
         }
       }
     }
-    Map<SkyKey, SkyValue> packageValues = graph.getDoneValues(resultKeys);
-    if (packageValues.size() != resultKeys.size()) {
-      throw new IllegalStateException(
-          "Missing values: " + Sets.difference(resultKeys, packageValues.keySet()));
-    }
+    Map<SkyKey, SkyValue> packageValues = graph.getSuccessfulValues(resultKeys);
     ImmutableSet.Builder<Target> result = ImmutableSet.builder();
     for (SkyValue value : packageValues.values()) {
       result.add(((PackageValue) value).getPackage().getBuildFile());
diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
index 0e4e86b..47b6a31 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
@@ -71,7 +71,7 @@
       };
 
   @Override
-  public Map<SkyKey, SkyValue> getDoneValues(Iterable<SkyKey> keys) {
+  public Map<SkyKey, SkyValue> getSuccessfulValues(Iterable<SkyKey> keys) {
     return Maps.filterValues(Maps.transformValues(graph.getBatch(keys), GET_SKY_VALUE_FUNCTION),
         Predicates.notNull());
   }
diff --git a/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
index cd87633..a8c18ea 100644
--- a/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
@@ -41,10 +41,11 @@
   SkyValue getValue(SkyKey key);
 
   /**
-   * Returns a map giving the values of the given keys for done keys. Keys not present in the graph
-   * or whose nodes are not done will not be present in the returned map.
+   * Returns a map giving the values of the given keys for done keys that were successfully
+   * computed. Or in other words, it filters out non-existent nodes, pending nodes and nodes
+   * that produced an exception.
    */
-  Map<SkyKey, SkyValue> getDoneValues(Iterable<SkyKey> keys);
+  Map<SkyKey, SkyValue> getSuccessfulValues(Iterable<SkyKey> keys);
 
   /**
    * Returns a map giving exceptions associated to the given keys for done keys. Keys not present in