diff --git a/src/main/java/com/google/devtools/build/skyframe/AbstractSkyFunctionEnvironment.java b/src/main/java/com/google/devtools/build/skyframe/AbstractSkyFunctionEnvironment.java
index a91fdbf..a4954e9 100644
--- a/src/main/java/com/google/devtools/build/skyframe/AbstractSkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/AbstractSkyFunctionEnvironment.java
@@ -18,11 +18,9 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Maps;
 import com.google.devtools.build.skyframe.ValueOrExceptionUtils.BottomException;
-
 import java.util.Collections;
 import java.util.Map;
 import java.util.Set;
-
 import javax.annotation.Nullable;
 
 /**
@@ -32,14 +30,16 @@
 @VisibleForTesting
 public abstract class AbstractSkyFunctionEnvironment implements SkyFunction.Environment {
   protected boolean valuesMissing = false;
-  private <E extends Exception> ValueOrException<E> getValueOrException(SkyKey depKey,
-      Class<E> exceptionClass) {
+  private <E extends Exception> ValueOrException<E> getValueOrException(
+      SkyKey depKey, Class<E> exceptionClass) throws InterruptedException {
     return ValueOrExceptionUtils.downconvert(
         getValueOrException(depKey, exceptionClass, BottomException.class), exceptionClass);
   }
 
-  private <E1 extends Exception, E2 extends Exception> ValueOrException2<E1, E2>
-  getValueOrException(SkyKey depKey, Class<E1> exceptionClass1, Class<E2> exceptionClass2) {
+  private <E1 extends Exception, E2 extends Exception>
+      ValueOrException2<E1, E2> getValueOrException(
+          SkyKey depKey, Class<E1> exceptionClass1, Class<E2> exceptionClass2)
+          throws InterruptedException {
     return ValueOrExceptionUtils.downconvert(getValueOrException(depKey, exceptionClass1,
         exceptionClass2, BottomException.class), exceptionClass1, exceptionClass2);
   }
@@ -49,7 +49,8 @@
           SkyKey depKey,
           Class<E1> exceptionClass1,
           Class<E2> exceptionClass2,
-          Class<E3> exceptionClass3) {
+          Class<E3> exceptionClass3)
+          throws InterruptedException {
     return ValueOrExceptionUtils.downconvert(
         getValueOrException(depKey, exceptionClass1, exceptionClass2, exceptionClass3,
             BottomException.class),
@@ -64,7 +65,8 @@
           Class<E1> exceptionClass1,
           Class<E2> exceptionClass2,
           Class<E3> exceptionClass3,
-          Class<E4> exceptionClass4) {
+          Class<E4> exceptionClass4)
+          throws InterruptedException {
     return ValueOrExceptionUtils.downconvert(
         getValueOrException(depKey, exceptionClass1, exceptionClass2, exceptionClass3,
             exceptionClass4, BottomException.class),
@@ -74,15 +76,20 @@
         exceptionClass4);
   }
 
-  private <E1 extends Exception, E2 extends Exception, E3 extends Exception,
-           E4 extends Exception, E5 extends Exception>
+  private <
+          E1 extends Exception,
+          E2 extends Exception,
+          E3 extends Exception,
+          E4 extends Exception,
+          E5 extends Exception>
       ValueOrException5<E1, E2, E3, E4, E5> getValueOrException(
           SkyKey depKey,
           Class<E1> exceptionClass1,
           Class<E2> exceptionClass2,
           Class<E3> exceptionClass3,
           Class<E4> exceptionClass4,
-          Class<E5> exceptionClass5) {
+          Class<E5> exceptionClass5)
+          throws InterruptedException {
     return getValueOrExceptions(
         ImmutableSet.of(depKey),
         exceptionClass1,
@@ -92,7 +99,11 @@
         exceptionClass5).get(depKey);
   }
 
-  private <E1 extends Exception, E2 extends Exception, E3 extends Exception, E4 extends Exception,
+  private <
+          E1 extends Exception,
+          E2 extends Exception,
+          E3 extends Exception,
+          E4 extends Exception,
           E5 extends Exception>
       Map<SkyKey, ValueOrException5<E1, E2, E3, E4, E5>> getValueOrExceptions(
           Set<SkyKey> depKeys,
@@ -100,7 +111,8 @@
           final Class<E2> exceptionClass2,
           final Class<E3> exceptionClass3,
           final Class<E4> exceptionClass4,
-          final Class<E5> exceptionClass5) {
+          final Class<E5> exceptionClass5)
+          throws InterruptedException {
     SkyFunctionException.validateExceptionType(exceptionClass1);
     SkyFunctionException.validateExceptionType(exceptionClass2);
     SkyFunctionException.validateExceptionType(exceptionClass3);
@@ -158,11 +170,11 @@
 
   /** Implementations should set {@link #valuesMissing} as necessary. */
   protected abstract Map<SkyKey, ValueOrUntypedException> getValueOrUntypedExceptions(
-      Set<SkyKey> depKeys);
+      Set<SkyKey> depKeys) throws InterruptedException;
 
   @Override
   @Nullable
-  public SkyValue getValue(SkyKey depKey) {
+  public SkyValue getValue(SkyKey depKey) throws InterruptedException {
     try {
       return getValueOrThrow(depKey, BottomException.class);
     } catch (BottomException e) {
@@ -173,16 +185,15 @@
   @Override
   @Nullable
   public <E extends Exception> SkyValue getValueOrThrow(SkyKey depKey, Class<E> exceptionClass)
-      throws E {
+      throws E, InterruptedException {
     return getValueOrException(depKey, exceptionClass).get();
   }
 
   @Override
   @Nullable
   public <E1 extends Exception, E2 extends Exception> SkyValue getValueOrThrow(
-      SkyKey depKey,
-      Class<E1> exceptionClass1,
-      Class<E2> exceptionClass2) throws E1, E2 {
+      SkyKey depKey, Class<E1> exceptionClass1, Class<E2> exceptionClass2)
+      throws E1, E2, InterruptedException {
     return getValueOrException(depKey, exceptionClass1, exceptionClass2).get();
   }
 
@@ -193,7 +204,8 @@
           SkyKey depKey,
           Class<E1> exceptionClass1,
           Class<E2> exceptionClass2,
-          Class<E3> exceptionClass3) throws E1, E2, E3 {
+          Class<E3> exceptionClass3)
+          throws E1, E2, E3, InterruptedException {
     return getValueOrException(depKey, exceptionClass1, exceptionClass2, exceptionClass3).get();
   }
 
@@ -204,7 +216,8 @@
           Class<E1> exceptionClass1,
           Class<E2> exceptionClass2,
           Class<E3> exceptionClass3,
-          Class<E4> exceptionClass4) throws E1, E2, E3, E4 {
+          Class<E4> exceptionClass4)
+          throws E1, E2, E3, E4, InterruptedException {
     return getValueOrException(
         depKey,
         exceptionClass1,
@@ -214,7 +227,11 @@
   }
 
   @Override
-  public <E1 extends Exception, E2 extends Exception, E3 extends Exception, E4 extends Exception,
+  public <
+          E1 extends Exception,
+          E2 extends Exception,
+          E3 extends Exception,
+          E4 extends Exception,
           E5 extends Exception>
       SkyValue getValueOrThrow(
           SkyKey depKey,
@@ -222,8 +239,8 @@
           Class<E2> exceptionClass2,
           Class<E3> exceptionClass3,
           Class<E4> exceptionClass4,
-          Class<E5> exceptionClass5
-  ) throws E1, E2, E3, E4, E5 {
+          Class<E5> exceptionClass5)
+          throws E1, E2, E3, E4, E5, InterruptedException {
     return getValueOrException(
         depKey,
         exceptionClass1,
@@ -234,14 +251,14 @@
   }
 
   @Override
-  public Map<SkyKey, SkyValue> getValues(Iterable<SkyKey> depKeys) {
+  public Map<SkyKey, SkyValue> getValues(Iterable<SkyKey> depKeys) throws InterruptedException {
     return Maps.transformValues(getValuesOrThrow(depKeys, BottomException.class),
         GET_VALUE_FROM_VOE);
   }
 
   @Override
   public <E extends Exception> Map<SkyKey, ValueOrException<E>> getValuesOrThrow(
-      Iterable<SkyKey> depKeys, Class<E> exceptionClass) {
+      Iterable<SkyKey> depKeys, Class<E> exceptionClass) throws InterruptedException {
     return Maps.transformValues(
         getValuesOrThrow(depKeys, exceptionClass, BottomException.class),
         makeSafeDowncastToVOEFunction(exceptionClass));
@@ -250,9 +267,8 @@
   @Override
   public <E1 extends Exception, E2 extends Exception>
       Map<SkyKey, ValueOrException2<E1, E2>> getValuesOrThrow(
-          Iterable<SkyKey> depKeys,
-          Class<E1> exceptionClass1,
-          Class<E2> exceptionClass2) {
+          Iterable<SkyKey> depKeys, Class<E1> exceptionClass1, Class<E2> exceptionClass2)
+          throws InterruptedException {
     return Maps.transformValues(
         getValuesOrThrow(depKeys, exceptionClass1, exceptionClass2, BottomException.class),
         makeSafeDowncastToVOE2Function(exceptionClass1, exceptionClass2));
@@ -264,7 +280,8 @@
           Iterable<SkyKey> depKeys,
           Class<E1> exceptionClass1,
           Class<E2> exceptionClass2,
-          Class<E3> exceptionClass3) {
+          Class<E3> exceptionClass3)
+          throws InterruptedException {
     return Maps.transformValues(
         getValuesOrThrow(depKeys, exceptionClass1, exceptionClass2, exceptionClass3,
             BottomException.class),
@@ -278,7 +295,8 @@
           Class<E1> exceptionClass1,
           Class<E2> exceptionClass2,
           Class<E3> exceptionClass3,
-          Class<E4> exceptionClass4) {
+          Class<E4> exceptionClass4)
+          throws InterruptedException {
     return Maps.transformValues(
         getValuesOrThrow(depKeys, exceptionClass1, exceptionClass2, exceptionClass3,
             exceptionClass4, BottomException.class),
@@ -287,15 +305,20 @@
   }
 
   @Override
-  public <E1 extends Exception, E2 extends Exception, E3 extends Exception,
-          E4 extends Exception, E5 extends Exception>
+  public <
+          E1 extends Exception,
+          E2 extends Exception,
+          E3 extends Exception,
+          E4 extends Exception,
+          E5 extends Exception>
       Map<SkyKey, ValueOrException5<E1, E2, E3, E4, E5>> getValuesOrThrow(
           Iterable<SkyKey> depKeys,
           Class<E1> exceptionClass1,
           Class<E2> exceptionClass2,
           Class<E3> exceptionClass3,
           Class<E4> exceptionClass4,
-          Class<E5> exceptionClass5) {
+          Class<E5> exceptionClass5)
+          throws InterruptedException {
     Set<SkyKey> keys = ImmutableSet.copyOf(depKeys);
     Map<SkyKey, ValueOrException5<E1, E2, E3, E4, E5>> result = getValueOrExceptions(keys,
         exceptionClass1, exceptionClass2, exceptionClass3, exceptionClass4, exceptionClass5);
diff --git a/src/main/java/com/google/devtools/build/skyframe/BuildDriver.java b/src/main/java/com/google/devtools/build/skyframe/BuildDriver.java
index 3172b4a..4ebe244 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildDriver.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildDriver.java
@@ -17,7 +17,6 @@
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.util.AbruptExitException;
 import com.google.devtools.common.options.OptionsClassProvider;
-
 import javax.annotation.Nullable;
 
 /** A BuildDriver wraps a MemoizingEvaluator, passing along the proper Version. */
@@ -41,11 +40,11 @@
   MemoizingEvaluator getGraphForTesting();
 
   @Nullable
-  SkyValue getExistingValueForTesting(SkyKey key);
+  SkyValue getExistingValueForTesting(SkyKey key) throws InterruptedException;
 
   @Nullable
-  ErrorInfo getExistingErrorForTesting(SkyKey key);
+  ErrorInfo getExistingErrorForTesting(SkyKey key) throws InterruptedException;
 
   @Nullable
-  NodeEntry getEntryForTesting(SkyKey key);
+  NodeEntry getEntryForTesting(SkyKey key) throws InterruptedException;
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
index d714924..6bf77ec4 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingNodeEntry.java
@@ -15,10 +15,8 @@
 
 import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
-
 import java.util.Collection;
 import java.util.Set;
-
 import javax.annotation.Nullable;
 
 /** Convenience class for {@link NodeEntry} implementations that delegate many operations. */
@@ -35,23 +33,23 @@
   }
 
   @Override
-  public SkyValue getValue() {
+  public SkyValue getValue() throws InterruptedException {
     return getDelegate().getValue();
   }
 
   @Override
-  public SkyValue getValueMaybeWithMetadata() {
+  public SkyValue getValueMaybeWithMetadata() throws InterruptedException {
     return getDelegate().getValueMaybeWithMetadata();
   }
 
   @Override
-  public SkyValue toValue() {
+  public SkyValue toValue() throws InterruptedException {
     return getDelegate().toValue();
   }
 
   @Nullable
   @Override
-  public ErrorInfo getErrorInfo() {
+  public ErrorInfo getErrorInfo() throws InterruptedException {
     return getDelegate().getErrorInfo();
   }
 
@@ -61,7 +59,7 @@
   }
 
   @Override
-  public Set<SkyKey> setValue(SkyValue value, Version version) {
+  public Set<SkyKey> setValue(SkyValue value, Version version) throws InterruptedException {
     return getDelegate().setValue(value, version);
   }
 
@@ -86,7 +84,7 @@
   }
 
   @Override
-  public Set<SkyKey> markClean() {
+  public Set<SkyKey> markClean() throws InterruptedException {
     return getDelegate().markClean();
   }
 
@@ -156,7 +154,7 @@
   }
 
   @Override
-  public Iterable<SkyKey> getDirectDeps() {
+  public Iterable<SkyKey> getDirectDeps() throws InterruptedException {
     return getDelegate().getDirectDeps();
   }
 
@@ -187,7 +185,7 @@
 
   @Override
   @Nullable
-  public MarkedDirtyResult markDirty(boolean isChanged) {
+  public MarkedDirtyResult markDirty(boolean isChanged) throws InterruptedException {
     return getThinDelegate().markDirty(isChanged);
   }
 
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 c56bf55..5c22a05 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
@@ -13,8 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
-import com.google.common.base.Function;
-import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -22,7 +20,6 @@
 import java.util.HashMap;
 import java.util.Map;
 import java.util.Map.Entry;
-
 import javax.annotation.Nullable;
 
 /**
@@ -35,7 +32,7 @@
     this.graph = graph;
   }
 
-  private NodeEntry getEntryForValue(SkyKey key) {
+  private NodeEntry getEntryForValue(SkyKey key) throws InterruptedException {
     NodeEntry entry =
         Preconditions.checkNotNull(
             graph.getBatch(null, Reason.WALKABLE_GRAPH_VALUE, ImmutableList.of(key)).get(key),
@@ -45,7 +42,7 @@
   }
 
   @Override
-  public boolean exists(SkyKey key) {
+  public boolean exists(SkyKey key) throws InterruptedException {
     NodeEntry entry =
         graph.getBatch(null, Reason.EXISTENCE_CHECKING, ImmutableList.of(key)).get(key);
     return entry != null && entry.isDone();
@@ -53,32 +50,35 @@
 
   @Nullable
   @Override
-  public SkyValue getValue(SkyKey key) {
+  public SkyValue getValue(SkyKey key) throws InterruptedException {
     return getEntryForValue(key).getValue();
   }
 
-  private static final Function<NodeEntry, SkyValue> GET_SKY_VALUE_FUNCTION =
-      new Function<NodeEntry, SkyValue>() {
-        @Nullable
-        @Override
-        public SkyValue apply(NodeEntry entry) {
-          return entry.isDone() ? entry.getValue() : null;
-        }
-      };
-
-  @Override
-  public Map<SkyKey, SkyValue> getSuccessfulValues(Iterable<SkyKey> keys) {
-    return Maps.filterValues(
-        Maps.transformValues(
-            graph.getBatch(null, Reason.WALKABLE_GRAPH_VALUE, keys),
-            GET_SKY_VALUE_FUNCTION),
-        Predicates.notNull());
+  private static SkyValue getValue(NodeEntry entry) throws InterruptedException {
+    return entry.isDone() ? entry.getValue() : null;
   }
 
   @Override
-  public Map<SkyKey, Exception> getMissingAndExceptions(Iterable<SkyKey> keys) {
+  public Map<SkyKey, SkyValue> getSuccessfulValues(Iterable<SkyKey> keys)
+      throws InterruptedException {
+    Map<SkyKey, ? extends NodeEntry> batchGet =
+        graph.getBatch(null, Reason.WALKABLE_GRAPH_VALUE, keys);
+    Map<SkyKey, SkyValue> result = Maps.newHashMapWithExpectedSize(batchGet.size());
+    for (Entry<SkyKey, ? extends NodeEntry> entryPair : batchGet.entrySet()) {
+      SkyValue value = getValue(entryPair.getValue());
+      if (value != null) {
+        result.put(entryPair.getKey(), value);
+      }
+    }
+    return result;
+  }
+
+  @Override
+  public Map<SkyKey, Exception> getMissingAndExceptions(Iterable<SkyKey> keys)
+      throws InterruptedException {
     Map<SkyKey, Exception> result = new HashMap<>();
-    Map<SkyKey, NodeEntry> graphResult = graph.getBatch(null, Reason.WALKABLE_GRAPH_VALUE, keys);
+    Map<SkyKey, ? extends NodeEntry> graphResult =
+        graph.getBatch(null, Reason.WALKABLE_GRAPH_VALUE, keys);
     for (SkyKey key : keys) {
       NodeEntry nodeEntry = graphResult.get(key);
       if (nodeEntry == null || !nodeEntry.isDone()) {
@@ -95,16 +95,18 @@
 
   @Nullable
   @Override
-  public Exception getException(SkyKey key) {
+  public Exception getException(SkyKey key) throws InterruptedException {
     ErrorInfo errorInfo = getEntryForValue(key).getErrorInfo();
     return errorInfo == null ? null : errorInfo.getException();
   }
 
   @Override
-  public Map<SkyKey, Iterable<SkyKey>> getDirectDeps(Iterable<SkyKey> keys) {
-    Map<SkyKey, NodeEntry> entries = graph.getBatch(null, Reason.WALKABLE_GRAPH_DEPS, keys);
+  public Map<SkyKey, Iterable<SkyKey>> getDirectDeps(Iterable<SkyKey> keys)
+      throws InterruptedException {
+    Map<SkyKey, ? extends NodeEntry> entries =
+        graph.getBatch(null, Reason.WALKABLE_GRAPH_DEPS, keys);
     Map<SkyKey, Iterable<SkyKey>> result = new HashMap<>(entries.size());
-    for (Entry<SkyKey, NodeEntry> entry : entries.entrySet()) {
+    for (Entry<SkyKey, ? extends NodeEntry> entry : entries.entrySet()) {
       Preconditions.checkState(entry.getValue().isDone(), entry);
       result.put(entry.getKey(), entry.getValue().getDirectDeps());
     }
@@ -112,10 +114,12 @@
   }
 
   @Override
-  public Map<SkyKey, Iterable<SkyKey>> getReverseDeps(Iterable<SkyKey> keys) {
-    Map<SkyKey, NodeEntry> entries = graph.getBatch(null, Reason.WALKABLE_GRAPH_RDEPS, keys);
+  public Map<SkyKey, Iterable<SkyKey>> getReverseDeps(Iterable<SkyKey> keys)
+      throws InterruptedException {
+    Map<SkyKey, ? extends NodeEntry> entries =
+        graph.getBatch(null, Reason.WALKABLE_GRAPH_RDEPS, keys);
     Map<SkyKey, Iterable<SkyKey>> result = new HashMap<>(entries.size());
-    for (Entry<SkyKey, NodeEntry> entry : entries.entrySet()) {
+    for (Entry<SkyKey, ? extends NodeEntry> entry : entries.entrySet()) {
       Preconditions.checkState(entry.getValue().isDone(), entry);
       result.put(entry.getKey(), entry.getValue().getReverseDeps());
     }
diff --git a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
index e8c5a46..a476275 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
@@ -18,7 +18,6 @@
 import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.NodeEntry.DirtyState;
-
 import java.util.Collection;
 import java.util.Set;
 
@@ -48,7 +47,7 @@
   protected final GroupedList<SkyKey> lastBuildDirectDeps;
 
   /** The value of the node the last time it was built. */
-  protected abstract SkyValue getLastBuildValue();
+  protected abstract SkyValue getLastBuildValue() throws InterruptedException;
 
   /**
    * Group of children to be checked next in the process of determining if this entry needs to be
@@ -144,7 +143,7 @@
    * <p>Changes in direct deps do <i>not</i> force this to return false. Only the value is
    * considered.
    */
-  final boolean unchangedFromLastBuild(SkyValue newValue) {
+  final boolean unchangedFromLastBuild(SkyValue newValue) throws InterruptedException {
     checkFinishedBuildingWhenAboutToSetValue();
     return !(newValue instanceof NotComparableSkyValue) && getLastBuildValue().equals(newValue);
   }
diff --git a/src/main/java/com/google/devtools/build/skyframe/EagerInvalidator.java b/src/main/java/com/google/devtools/build/skyframe/EagerInvalidator.java
index 5dba03d..71537e8 100644
--- a/src/main/java/com/google/devtools/build/skyframe/EagerInvalidator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/EagerInvalidator.java
@@ -20,10 +20,8 @@
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DeletingNodeVisitor;
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.DirtyingNodeVisitor;
 import com.google.devtools.build.skyframe.InvalidatingNodeVisitor.InvalidationState;
-
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.ForkJoinPool;
-
 import javax.annotation.Nullable;
 
 /**
@@ -106,8 +104,7 @@
             state,
             dirtyKeyTracker,
             forkJoinPool,
-            supportInterruptions,
-            errorHandler);
+            supportInterruptions);
   }
 
   /**
@@ -141,8 +138,7 @@
       InvalidationState state,
       DirtyKeyTracker dirtyKeyTracker,
       ForkJoinPool forkJoinPool,
-      boolean supportInterruptions,
-      ErrorHandler errorHandler)
+      boolean supportInterruptions)
       throws InterruptedException {
     DirtyingNodeVisitor visitor =
         createInvalidatingVisitorIfNeeded(
@@ -153,7 +149,7 @@
             dirtyKeyTracker,
             forkJoinPool,
             supportInterruptions,
-            errorHandler);
+            ErrorHandler.NullHandler.INSTANCE);
     if (visitor != null) {
       visitor.run();
     }
diff --git a/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java b/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java
index 6e93ce4..51ba403 100644
--- a/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/EvaluableGraph.java
@@ -20,18 +20,21 @@
 /**
  * Interface between a single version of the graph and the evaluator. Supports mutation of that
  * single version of the graph.
+ *
+ * <p>Certain graph implementations can throw {@link InterruptedException} when trying to retrieve
+ * node entries. Such exceptions should not be caught locally -- they should be allowed to propagate
+ * up.
  */
 @ThreadSafe
 interface EvaluableGraph extends QueryableGraph, DeletableGraph {
   /**
-   * Like {@link QueryableGraph#getBatch}, except it creates a new node for each key
-   * not already present in the graph. Thus, the returned map will have an entry for each key in
-   * {@code keys}.
+   * Like {@link QueryableGraph#getBatch}, except it creates a new node for each key not already
+   * present in the graph. Thus, the returned map will have an entry for each key in {@code keys}.
    *
    * @param requestor if non-{@code null}, the node on behalf of which the given {@code keys} are
    *     being requested.
    * @param reason the reason the nodes are being requested.
    */
-  Map<SkyKey, NodeEntry> createIfAbsentBatch(
-      @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys);
+  Map<SkyKey, ? extends NodeEntry> createIfAbsentBatch(
+      @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys) throws InterruptedException;
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
index 02735c0..edb80f0 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
@@ -14,9 +14,22 @@
 package com.google.devtools.build.skyframe;
 
 import java.util.Map;
+import javax.annotation.Nullable;
 
 /** {@link ProcessableGraph} that exposes the contents of the entire graph. */
 interface InMemoryGraph extends ProcessableGraph {
+  @Override
+  Map<SkyKey, ? extends NodeEntry> createIfAbsentBatch(
+      @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys);
+
+  @Nullable
+  @Override
+  NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey key);
+
+  @Override
+  Map<SkyKey, ? extends NodeEntry> getBatch(
+      @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys);
+
   /**
    * Returns a read-only live view of the nodes in the graph. All node are included. Dirty values
    * include their Node value. Values in error have a null value.
@@ -30,5 +43,5 @@
   Map<SkyKey, SkyValue> getDoneValues();
 
   // Only for use by MemoizingEvaluator#delete
-  Map<SkyKey, NodeEntry> getAllValues();
+  Map<SkyKey, ? extends NodeEntry> getAllValues();
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java
index eca58b3..b5d2472 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java
@@ -32,7 +32,7 @@
  */
 public class InMemoryGraphImpl implements InMemoryGraph {
 
-  protected final ConcurrentMap<SkyKey, NodeEntry> nodeMap =
+  protected final ConcurrentMap<SkyKey, InMemoryNodeEntry> nodeMap =
       new MapMaker().initialCapacity(1024).concurrencyLevel(200).makeMap();
   private final boolean keepEdges;
 
@@ -50,7 +50,7 @@
   }
 
   @Override
-  public NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey skyKey) {
+  public InMemoryNodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey skyKey) {
     return nodeMap.get(skyKey);
   }
 
@@ -58,7 +58,7 @@
   public Map<SkyKey, NodeEntry> getBatch(SkyKey requestor, Reason reason, Iterable<SkyKey> keys) {
     ImmutableMap.Builder<SkyKey, NodeEntry> builder = ImmutableMap.builder();
     for (SkyKey key : keys) {
-      NodeEntry entry = get(null, reason, key);
+      InMemoryNodeEntry entry = get(null, Reason.OTHER, key);
       if (entry != null) {
         builder.put(key, entry);
       }
@@ -66,16 +66,17 @@
     return builder.build();
   }
 
-  protected NodeEntry createIfAbsent(SkyKey key) {
-    NodeEntry newval = keepEdges ? new InMemoryNodeEntry() : new EdgelessInMemoryNodeEntry();
-    NodeEntry oldval = nodeMap.putIfAbsent(key, newval);
+  protected InMemoryNodeEntry createIfAbsent(SkyKey key) {
+    InMemoryNodeEntry newval =
+        keepEdges ? new InMemoryNodeEntry() : new EdgelessInMemoryNodeEntry();
+    InMemoryNodeEntry oldval = nodeMap.putIfAbsent(key, newval);
     return oldval == null ? newval : oldval;
   }
 
   @Override
-  public Map<SkyKey, NodeEntry> createIfAbsentBatch(
+  public Map<SkyKey, InMemoryNodeEntry> createIfAbsentBatch(
       @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys) {
-    ImmutableMap.Builder<SkyKey, NodeEntry> builder = ImmutableMap.builder();
+    ImmutableMap.Builder<SkyKey, InMemoryNodeEntry> builder = ImmutableMap.builder();
     for (SkyKey key : keys) {
       builder.put(key, createIfAbsent(key));
     }
@@ -87,9 +88,9 @@
     return Collections.unmodifiableMap(
         Maps.transformValues(
             nodeMap,
-            new Function<NodeEntry, SkyValue>() {
+            new Function<InMemoryNodeEntry, SkyValue>() {
               @Override
-              public SkyValue apply(NodeEntry entry) {
+              public SkyValue apply(InMemoryNodeEntry entry) {
                 return entry.toValue();
               }
             }));
@@ -101,9 +102,9 @@
         Maps.filterValues(
             Maps.transformValues(
                 nodeMap,
-                new Function<NodeEntry, SkyValue>() {
+                new Function<InMemoryNodeEntry, SkyValue>() {
                   @Override
-                  public SkyValue apply(NodeEntry entry) {
+                  public SkyValue apply(InMemoryNodeEntry entry) {
                     return entry.isDone() ? entry.getValue() : null;
                   }
                 }),
@@ -111,12 +112,12 @@
   }
 
   @Override
-  public Map<SkyKey, NodeEntry> getAllValues() {
+  public Map<SkyKey, InMemoryNodeEntry> getAllValues() {
     return Collections.unmodifiableMap(nodeMap);
   }
 
   @VisibleForTesting
-  protected ConcurrentMap<SkyKey, NodeEntry> getNodeMap() {
+  protected ConcurrentMap<SkyKey, ? extends NodeEntry> getNodeMap() {
     return nodeMap;
   }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
index 38604ed..972d020 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryMemoizingEvaluator.java
@@ -39,7 +39,6 @@
 import java.util.Map.Entry;
 import java.util.Set;
 import java.util.concurrent.atomic.AtomicBoolean;
-
 import javax.annotation.Nullable;
 
 /**
@@ -112,13 +111,16 @@
   @Override
   public void delete(final Predicate<SkyKey> deletePredicate) {
     valuesToDelete.addAll(
-        Maps.filterEntries(graph.getAllValues(), new Predicate<Entry<SkyKey, NodeEntry>>() {
-          @Override
-          public boolean apply(Entry<SkyKey, NodeEntry> input) {
-            Preconditions.checkNotNull(input.getKey(), "Null SkyKey in entry: %s", input);
-            return input.getValue().isDirty() || deletePredicate.apply(input.getKey());
-          }
-        }).keySet());
+        Maps.filterEntries(
+                graph.getAllValues(),
+                new Predicate<Entry<SkyKey, ? extends NodeEntry>>() {
+                  @Override
+                  public boolean apply(Entry<SkyKey, ? extends NodeEntry> input) {
+                    Preconditions.checkNotNull(input.getKey(), "Null SkyKey in entry: %s", input);
+                    return input.getValue().isDirty() || deletePredicate.apply(input.getKey());
+                  }
+                })
+            .keySet());
   }
 
   @Override
@@ -209,12 +211,18 @@
       SkyValue newValue = entry.getValue();
       NodeEntry prevEntry = graph.get(null, Reason.OTHER, key);
       if (prevEntry != null && prevEntry.isDone()) {
-        Iterable<SkyKey> directDeps = prevEntry.getDirectDeps();
-        Preconditions.checkState(Iterables.isEmpty(directDeps),
-            "existing entry for %s has deps: %s", key, directDeps);
-        if (newValue.equals(prevEntry.getValue())
-            && !valuesToDirty.contains(key) && !valuesToDelete.contains(key)) {
-          it.remove();
+        try {
+          Iterable<SkyKey> directDeps = prevEntry.getDirectDeps();
+          Preconditions.checkState(
+              Iterables.isEmpty(directDeps), "existing entry for %s has deps: %s", key, directDeps);
+          if (newValue.equals(prevEntry.getValue())
+              && !valuesToDirty.contains(key)
+              && !valuesToDelete.contains(key)) {
+            it.remove();
+          }
+        } catch (InterruptedException e) {
+          throw new IllegalStateException(
+              "InMemoryGraph does not throw: " + entry + ", " + prevEntry, e);
         }
       }
     }
@@ -227,7 +235,11 @@
     if (valuesToInject.isEmpty()) {
       return;
     }
-    ParallelEvaluator.injectValues(valuesToInject, version, graph, dirtyKeyTracker);
+    try {
+      ParallelEvaluator.injectValues(valuesToInject, version, graph, dirtyKeyTracker);
+    } catch (InterruptedException e) {
+      throw new IllegalStateException("InMemoryGraph doesn't throw interrupts", e);
+    }
     // Start with a new map to avoid bloat since clear() does not downsize the map.
     valuesToInject = new HashMap<>();
   }
@@ -268,13 +280,21 @@
   @Override
   @Nullable public SkyValue getExistingValueForTesting(SkyKey key) {
     NodeEntry entry = getExistingEntryForTesting(key);
-    return isDone(entry) ? entry.getValue() : null;
+    try {
+      return isDone(entry) ? entry.getValue() : null;
+    } catch (InterruptedException e) {
+      throw new IllegalStateException("InMemoryGraph does not throw" + key + ", " + entry, e);
+    }
   }
 
   @Override
   @Nullable public ErrorInfo getExistingErrorForTesting(SkyKey key) {
     NodeEntry entry = getExistingEntryForTesting(key);
-    return isDone(entry) ? entry.getErrorInfo() : null;
+    try {
+      return isDone(entry) ? entry.getErrorInfo() : null;
+    } catch (InterruptedException e) {
+      throw new IllegalStateException("InMemoryGraph does not throw" + key + ", " + entry, e);
+    }
   }
 
   @Nullable
@@ -300,7 +320,11 @@
       for (NodeEntry entry : graph.getAllValues().values()) {
         nodes++;
         if (entry.isDone()) {
-          edges += Iterables.size(entry.getDirectDeps());
+          try {
+            edges += Iterables.size(entry.getDirectDeps());
+          } catch (InterruptedException e) {
+            throw new IllegalStateException("InMemoryGraph doesn't throw: " + entry, e);
+          }
         }
       }
       out.println("Node count: " + nodes);
@@ -315,14 +339,18 @@
             }
           };
 
-      for (Entry<SkyKey, NodeEntry> mapPair : graph.getAllValues().entrySet()) {
+      for (Entry<SkyKey, ? extends NodeEntry> mapPair : graph.getAllValues().entrySet()) {
         SkyKey key = mapPair.getKey();
         NodeEntry entry = mapPair.getValue();
         if (entry.isDone()) {
           out.print(keyFormatter.apply(key));
           out.print("|");
-          out.println(Joiner.on('|').join(
-              Iterables.transform(entry.getDirectDeps(), keyFormatter)));
+          try {
+            out.println(
+                Joiner.on('|').join(Iterables.transform(entry.getDirectDeps(), keyFormatter)));
+          } catch (InterruptedException e) {
+            throw new IllegalStateException("InMemoryGraph doesn't throw: " + entry, e);
+          }
         }
       }
     }
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
index 9ba0dbe..82d6922 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -21,11 +21,9 @@
 import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
 import com.google.devtools.build.lib.util.Preconditions;
-
 import java.util.Collection;
 import java.util.List;
 import java.util.Set;
-
 import javax.annotation.Nullable;
 
 /**
@@ -163,9 +161,13 @@
     if (isDone()) {
       return getErrorInfo() == null ? getValue() : null;
     } else if (isChanged() || isDirty()) {
-      return (getDirtyBuildingState().getLastBuildValue() == null)
-          ? null
-          : ValueWithMetadata.justValue(getDirtyBuildingState().getLastBuildValue());
+      SkyValue lastBuildValue = null;
+      try {
+        lastBuildValue = getDirtyBuildingState().getLastBuildValue();
+      } catch (InterruptedException e) {
+        throw new IllegalStateException("Interruption unexpected: " + this, e);
+      }
+      return (lastBuildValue == null) ? null : ValueWithMetadata.justValue(lastBuildValue);
     } else {
       // Value has not finished evaluating. It's probably about to be cleaned from the graph.
       return null;
@@ -230,7 +232,8 @@
   }
 
   @Override
-  public synchronized Set<SkyKey> setValue(SkyValue value, Version version) {
+  public synchronized Set<SkyKey> setValue(SkyValue value, Version version)
+      throws InterruptedException {
     Preconditions.checkState(isReady(), "%s %s", this, value);
     // This check may need to be removed when we move to a non-linear versioning sequence.
     Preconditions.checkState(
@@ -370,7 +373,7 @@
   }
 
   @Override
-  public synchronized Set<SkyKey> markClean() {
+  public synchronized Set<SkyKey> markClean() throws InterruptedException {
     this.value = getDirtyBuildingState().getLastBuildValue();
     Preconditions.checkState(isReady(), "Should be ready when clean: %s", this);
     Preconditions.checkState(
diff --git a/src/main/java/com/google/devtools/build/skyframe/InterruptibleSupplier.java b/src/main/java/com/google/devtools/build/skyframe/InterruptibleSupplier.java
new file mode 100644
index 0000000..5f4ab55
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/InterruptibleSupplier.java
@@ -0,0 +1,63 @@
+// Copyright 2016 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.skyframe;
+
+import javax.annotation.Nullable;
+
+/** Supplier that may throw {@link InterruptedException} when value is retrieved. */
+public interface InterruptibleSupplier<T> {
+  T get() throws InterruptedException;
+
+  class Instance<T> implements InterruptibleSupplier<T> {
+    private final T instance;
+
+    public Instance(T instance) {
+      this.instance = instance;
+    }
+
+    @Override
+    public T get() {
+      return instance;
+    }
+  }
+
+  class Memoize<T> implements InterruptibleSupplier<T> {
+    private final InterruptibleSupplier<T> delegate;
+    private @Nullable T value = null;
+
+    private Memoize(InterruptibleSupplier<T> delegate) {
+      this.delegate = delegate;
+    }
+
+    public static <S> InterruptibleSupplier<S> of(InterruptibleSupplier<S> delegate) {
+      if (delegate instanceof Memoize) {
+        return delegate;
+      }
+      return new Memoize<>(delegate);
+    }
+
+    @Override
+    public T get() throws InterruptedException {
+      if (value != null) {
+        return value;
+      }
+      synchronized (this) {
+        if (value == null) {
+          value = delegate.get();
+        }
+      }
+      return value;
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
index 543ccf4..096fc2d 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -22,7 +22,6 @@
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
 import com.google.devtools.build.lib.concurrent.ErrorClassifier;
-import com.google.devtools.build.lib.concurrent.ErrorHandler;
 import com.google.devtools.build.lib.concurrent.ExecutorParams;
 import com.google.devtools.build.lib.concurrent.ForkJoinQuiescingExecutor;
 import com.google.devtools.build.lib.concurrent.QuiescingExecutor;
@@ -31,7 +30,6 @@
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import com.google.devtools.build.skyframe.ThinNodeEntry.MarkedDirtyResult;
-
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Map;
@@ -41,7 +39,6 @@
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.ForkJoinPool;
 import java.util.concurrent.TimeUnit;
-
 import javax.annotation.Nullable;
 
 /**
@@ -113,8 +110,7 @@
             /*failFastOnException=*/ true,
             "skyframe-invalidator",
             executorFactory,
-            errorClassifier,
-            ErrorHandler.NullHandler.INSTANCE);
+            errorClassifier);
     this.graph = Preconditions.checkNotNull(graph);
     this.invalidationReceiver = invalidationReceiver;
     this.dirtyKeyTracker = Preconditions.checkNotNull(dirtyKeyTracker);
@@ -126,9 +122,8 @@
       @Nullable EvaluationProgressReceiver invalidationReceiver,
       InvalidationState state,
       DirtyKeyTracker dirtyKeyTracker,
-      ForkJoinPool forkJoinPool,
-      ErrorHandler errorHandler) {
-    this.executor = new ForkJoinQuiescingExecutor(forkJoinPool, errorClassifier, errorHandler);
+      ForkJoinPool forkJoinPool) {
+    this.executor = new ForkJoinQuiescingExecutor(forkJoinPool, errorClassifier);
     this.graph = Preconditions.checkNotNull(graph);
     this.invalidationReceiver = invalidationReceiver;
     this.dirtyKeyTracker = Preconditions.checkNotNull(dirtyKeyTracker);
@@ -270,7 +265,7 @@
       for (SkyKey key : unvisitedKeys) {
         pendingVisitations.add(Pair.of(key, InvalidationType.DELETED));
       }
-      final Map<SkyKey, NodeEntry> entries =
+      final Map<SkyKey, ? extends NodeEntry> entries =
           graph.getBatch(null, Reason.INVALIDATION, unvisitedKeys);
       for (final SkyKey key : unvisitedKeys) {
         executor.execute(
@@ -303,13 +298,23 @@
                       entry.isDone()
                           ? ImmutableSet.<SkyKey>of()
                           : entry.getTemporaryDirectDeps().toSet();
-                  Iterable<SkyKey> directDeps =
-                      entry.isDone()
-                          ? entry.getDirectDeps()
-                          : entry.getAllDirectDepsForIncompleteNode();
-                  Map<SkyKey, NodeEntry> depMap =
+                  Iterable<SkyKey> directDeps;
+                  try {
+                    directDeps =
+                        entry.isDone()
+                            ? entry.getDirectDeps()
+                            : entry.getAllDirectDepsForIncompleteNode();
+                  } catch (InterruptedException e) {
+                    throw new IllegalStateException(
+                        "Deletion cannot happen on a graph that may have blocking operations: "
+                            + key
+                            + ", "
+                            + entry,
+                        e);
+                  }
+                  Map<SkyKey, ? extends NodeEntry> depMap =
                       graph.getBatch(key, Reason.INVALIDATION, directDeps);
-                  for (Map.Entry<SkyKey, NodeEntry> directDepEntry : depMap.entrySet()) {
+                  for (Map.Entry<SkyKey, ? extends NodeEntry> directDepEntry : depMap.entrySet()) {
                     NodeEntry dep = directDepEntry.getValue();
                     if (dep != null) {
                       if (dep.isDone() || !signalingDeps.contains(directDepEntry.getKey())) {
@@ -373,9 +378,8 @@
         InvalidationState state,
         DirtyKeyTracker dirtyKeyTracker,
         ForkJoinPool forkJoinPool,
-        boolean supportInterruptions,
-        ErrorHandler errorHandler) {
-      super(graph, invalidationReceiver, state, dirtyKeyTracker, forkJoinPool, errorHandler);
+        boolean supportInterruptions) {
+      super(graph, invalidationReceiver, state, dirtyKeyTracker, forkJoinPool);
       this.supportInterruptions = supportInterruptions;
     }
 
@@ -435,8 +439,16 @@
           pendingVisitations.add(Pair.of(key, invalidationType));
         }
       }
-      final Map<SkyKey, ? extends ThinNodeEntry> entries =
-          graph.getBatch(null, Reason.INVALIDATION, keysToGet);
+      final Map<SkyKey, ? extends ThinNodeEntry> entries;
+      try {
+        entries = graph.getBatch(null, Reason.INVALIDATION, keysToGet);
+      } catch (InterruptedException e) {
+        Thread.currentThread().interrupt();
+        // This can only happen if the main thread has been interrupted, and so the
+        // AbstractQueueVisitor is shutting down. We haven't yet removed the pending visitations, so
+        // we can resume next time.
+        return;
+      }
       if (enqueueingKeyForExistenceCheck != null && entries.size() != keysToGet.size()) {
         Set<SkyKey> missingKeys = Sets.difference(ImmutableSet.copyOf(keysToGet), entries.keySet());
         throw new IllegalStateException(
@@ -471,7 +483,16 @@
                 // method.
                 // Any exception thrown should be unrecoverable.
                 // This entry remains in the graph in this dirty state until it is re-evaluated.
-                MarkedDirtyResult markedDirtyResult = entry.markDirty(isChanged);
+                MarkedDirtyResult markedDirtyResult = null;
+                try {
+                  markedDirtyResult = entry.markDirty(isChanged);
+                } catch (InterruptedException e) {
+                  Thread.currentThread().interrupt();
+                  // This can only happen if the main thread has been interrupted, and so the
+                  // AbstractQueueVisitor is shutting down. We haven't yet removed the pending
+                  // visitation, so we can resume next time.
+                  return;
+                }
                 if (markedDirtyResult == null) {
                   // Another thread has already dirtied this node. Don't do anything in this thread.
                   if (supportInterruptions) {
diff --git a/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java
index cfbff0a..5c8236a 100644
--- a/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/MemoizingEvaluator.java
@@ -19,10 +19,8 @@
 import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadHostile;
 import com.google.devtools.build.lib.events.EventHandler;
-
 import java.io.PrintStream;
 import java.util.Map;
-
 import javax.annotation.Nullable;
 
 /**
@@ -118,7 +116,7 @@
    */
   @VisibleForTesting
   @Nullable
-  ErrorInfo getExistingErrorForTesting(SkyKey key);
+  ErrorInfo getExistingErrorForTesting(SkyKey key) throws InterruptedException;
 
   @Nullable
   NodeEntry getExistingEntryForTesting(SkyKey key);
diff --git a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
index 8b7b091..82df6fa 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -16,10 +16,8 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.util.GroupedList;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
-
 import java.util.Collection;
 import java.util.Set;
-
 import javax.annotation.Nullable;
 
 /**
@@ -27,6 +25,9 @@
  *
  * <p>This interface is public only for the benefit of alternative graph implementations outside of
  * the package.
+ *
+ * <p>Certain graph implementations' node entries can throw {@link InterruptedException} on various
+ * accesses. Such exceptions should not be caught locally -- they should be allowed to propagate up.
  */
 public interface NodeEntry extends ThinNodeEntry {
   /**
@@ -81,7 +82,7 @@
    * this node is complete, i.e., after {@link #setValue} has been called.
    */
   @ThreadSafe
-  SkyValue getValue();
+  SkyValue getValue() throws InterruptedException;
 
   /**
    * Returns an immutable iterable of the direct deps of this node. This method may only be called
@@ -93,7 +94,7 @@
    * each call takes time proportional to the number of direct deps of the node.
    */
   @ThreadSafe
-  Iterable<SkyKey> getDirectDeps();
+  Iterable<SkyKey> getDirectDeps() throws InterruptedException;
 
   /** Removes a reverse dependency. */
   @ThreadSafe
@@ -123,21 +124,19 @@
    * <p>Use the static methods of {@link ValueWithMetadata} to extract metadata if necessary.
    */
   @ThreadSafe
-  SkyValue getValueMaybeWithMetadata();
+  SkyValue getValueMaybeWithMetadata() throws InterruptedException;
 
-  /**
-   * Returns the value, even if dirty or changed. Returns null otherwise.
-   */
+  /** Returns the value, even if dirty or changed. Returns null otherwise. */
   @ThreadSafe
-  SkyValue toValue();
+  SkyValue toValue() throws InterruptedException;
 
   /**
-   * Returns the error, if any, associated to this node. This method may only be called after
-   * the evaluation of this node is complete, i.e., after {@link #setValue} has been called.
+   * Returns the error, if any, associated to this node. This method may only be called after the
+   * evaluation of this node is complete, i.e., after {@link #setValue} has been called.
    */
   @Nullable
   @ThreadSafe
-  ErrorInfo getErrorInfo();
+  ErrorInfo getErrorInfo() throws InterruptedException;
 
   /**
    * Returns the set of reverse deps that have been declared so far this build. Only for use in
@@ -153,10 +152,9 @@
    * signaled.
    *
    * <p>This is an atomic operation to avoid a race where two threads work on two nodes, where one
-   * node depends on another (b depends on a). When a finishes, it signals <b>exactly</b> the set
-   * of reverse dependencies that are registered at the time of the {@code setValue} call. If b
-   * comes in before a, it is signaled (and re-scheduled) by a, otherwise it needs to do that
-   * itself.
+   * node depends on another (b depends on a). When a finishes, it signals <b>exactly</b> the set of
+   * reverse dependencies that are registered at the time of the {@code setValue} call. If b comes
+   * in before a, it is signaled (and re-scheduled) by a, otherwise it needs to do that itself.
    *
    * <p>{@code version} indicates the graph version at which this node is being written. If the
    * entry determines that the new value is equal to the previous value, the entry will keep its
@@ -164,7 +162,7 @@
    * changed.
    */
   @ThreadSafe
-  Set<SkyKey> setValue(SkyValue value, Version version);
+  Set<SkyKey> setValue(SkyValue value, Version version) throws InterruptedException;
 
   /**
    * Queries if the node is done and adds the given key as a reverse dependency. The return code
@@ -238,7 +236,7 @@
    * @return {@link Set} of reverse dependencies to signal that this node is done.
    */
   @ThreadSafe
-  Set<SkyKey> markClean();
+  Set<SkyKey> markClean() throws InterruptedException;
 
   /**
    * Forces this node to be re-evaluated, even if none of its dependencies are known to have
diff --git a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
index 7353e54..834a614 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -31,7 +31,6 @@
 import com.google.devtools.build.lib.collect.nestedset.NestedSetVisitor;
 import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
 import com.google.devtools.build.lib.concurrent.ErrorClassifier;
-import com.google.devtools.build.lib.concurrent.ErrorHandler;
 import com.google.devtools.build.lib.concurrent.ForkJoinQuiescingExecutor;
 import com.google.devtools.build.lib.concurrent.QuiescingExecutor;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
@@ -132,7 +131,16 @@
 
     @Override
     public SkyValue get() {
-      return state.getValue();
+      try {
+        return state.getValue();
+      } catch (InterruptedException e) {
+        throw new IllegalStateException(
+            "Graph implementations in which value retrieval can block should not be used in "
+                + "frameworks that use the value in EvaluationProgressReceiver, since that could "
+                + "result in significant slowdowns: "
+                + state,
+            e);
+      }
     }
   }
 
@@ -157,7 +165,6 @@
   private final DirtyKeyTracker dirtyKeyTracker;
   private final Receiver<Collection<SkyKey>> inflightKeysReceiver;
   private final EventFilter storedEventFilter;
-  private final ErrorHandler errorHandler;
 
   public ParallelEvaluator(
       ProcessableGraph graph,
@@ -185,7 +192,6 @@
         new NestedSetVisitor<>(new NestedSetEventReceiver(reporter), emittedEventState);
     this.storedEventFilter = storedEventFilter;
     this.forkJoinPool = null;
-    this.errorHandler = ErrorHandler.NullHandler.INSTANCE;
   }
 
   public ParallelEvaluator(
@@ -200,8 +206,7 @@
       @Nullable EvaluationProgressReceiver progressReceiver,
       DirtyKeyTracker dirtyKeyTracker,
       Receiver<Collection<SkyKey>> inflightKeysReceiver,
-      ForkJoinPool forkJoinPool,
-      ErrorHandler errorHandler) {
+      ForkJoinPool forkJoinPool) {
     this.graph = graph;
     this.skyFunctions = skyFunctions;
     this.graphVersion = graphVersion;
@@ -217,13 +222,10 @@
         new NestedSetVisitor<>(new NestedSetEventReceiver(reporter), emittedEventState);
     this.storedEventFilter = storedEventFilter;
     this.forkJoinPool = Preconditions.checkNotNull(forkJoinPool);
-    this.errorHandler = errorHandler;
   }
 
-  private Map<SkyKey, NodeEntry> getBatchValues(
-      SkyKey parent,
-      Reason reason,
-      Iterable<SkyKey> keys) {
+  private Map<SkyKey, ? extends NodeEntry> getBatchValues(
+      SkyKey parent, Reason reason, Iterable<SkyKey> keys) throws InterruptedException {
     return graph.getBatch(parent, reason, keys);
   }
 
@@ -301,7 +303,8 @@
         };
 
     private SkyFunctionEnvironment(
-        SkyKey skyKey, GroupedList<SkyKey> directDeps, Set<SkyKey> oldDeps, ValueVisitor visitor) {
+        SkyKey skyKey, GroupedList<SkyKey> directDeps, Set<SkyKey> oldDeps, ValueVisitor visitor)
+        throws InterruptedException {
       this(skyKey, directDeps, null, oldDeps, visitor);
     }
 
@@ -310,7 +313,8 @@
         GroupedList<SkyKey> directDeps,
         @Nullable Map<SkyKey, ValueWithMetadata> bubbleErrorInfo,
         Set<SkyKey> oldDeps,
-        ValueVisitor visitor) {
+        ValueVisitor visitor)
+        throws InterruptedException {
       this.skyKey = skyKey;
       this.oldDeps = oldDeps;
       this.directDeps = Collections.unmodifiableMap(batchPrefetch(
@@ -323,9 +327,13 @@
           skyKey);
     }
 
-    private Map<SkyKey, NodeEntry> batchPrefetch(
-        SkyKey requestor, GroupedList<SkyKey> depKeys, Set<SkyKey> oldDeps, boolean assertDone,
-        SkyKey keyForDebugging) {
+    private Map<SkyKey, ? extends NodeEntry> batchPrefetch(
+        SkyKey requestor,
+        GroupedList<SkyKey> depKeys,
+        Set<SkyKey> oldDeps,
+        boolean assertDone,
+        SkyKey keyForDebugging)
+        throws InterruptedException {
       Iterable<SkyKey> depKeysAsIterable = Iterables.concat(depKeys);
       Iterable<SkyKey> keysToPrefetch = depKeysAsIterable;
       if (PREFETCH_OLD_DEPS) {
@@ -333,10 +341,12 @@
         keysToPrefetchBuilder.addAll(depKeysAsIterable).addAll(oldDeps);
         keysToPrefetch = keysToPrefetchBuilder.build();
       }
-      Map<SkyKey, NodeEntry> batchMap = getBatchValues(requestor, Reason.PREFETCH, keysToPrefetch);
+      Map<SkyKey, ? extends NodeEntry> batchMap =
+          getBatchValues(requestor, Reason.PREFETCH, keysToPrefetch);
       if (PREFETCH_OLD_DEPS) {
-        batchMap = ImmutableMap.copyOf(
-            Maps.filterKeys(batchMap, Predicates.in(ImmutableSet.copyOf(depKeysAsIterable))));
+        batchMap =
+            ImmutableMap.<SkyKey, NodeEntry>copyOf(
+                Maps.filterKeys(batchMap, Predicates.in(ImmutableSet.copyOf(depKeysAsIterable))));
       }
       if (batchMap.size() != depKeys.numElements()) {
         throw new IllegalStateException(
@@ -346,7 +356,7 @@
                 + Sets.difference(depKeys.toSet(), batchMap.keySet()));
       }
       if (assertDone) {
-        for (Map.Entry<SkyKey, NodeEntry> entry : batchMap.entrySet()) {
+        for (Map.Entry<SkyKey, ? extends NodeEntry> entry : batchMap.entrySet()) {
           Preconditions.checkState(
               entry.getValue().isDone(), "%s had not done %s", keyForDebugging, entry);
         }
@@ -358,7 +368,8 @@
       Preconditions.checkState(building, skyKey);
     }
 
-    private NestedSet<TaggedEvents> buildEvents(NodeEntry entry, boolean missingChildren) {
+    private NestedSet<TaggedEvents> buildEvents(NodeEntry entry, boolean missingChildren)
+        throws InterruptedException {
       // Aggregate the nested set of events from the direct deps, also adding the events from
       // building this value.
       NestedSetBuilder<TaggedEvents> eventBuilder = NestedSetBuilder.stableOrder();
@@ -426,7 +437,8 @@
      * dependencies of this node <i>must</i> already have been registered, since this method may
      * register a dependence on the error transience node, which should always be the last dep.
      */
-    private void setError(NodeEntry state, ErrorInfo errorInfo, boolean isDirectlyTransient) {
+    private void setError(NodeEntry state, ErrorInfo errorInfo, boolean isDirectlyTransient)
+        throws InterruptedException {
       Preconditions.checkState(value == null, "%s %s %s", skyKey, value, errorInfo);
       Preconditions.checkState(this.errorInfo == null,
           "%s %s %s", skyKey, this.errorInfo, errorInfo);
@@ -454,7 +466,8 @@
         @Nullable SkyKey requestor,
         Iterable<SkyKey> keys,
         @Nullable Map<SkyKey, ValueWithMetadata> bubbleErrorInfo,
-        int keySize) {
+        int keySize)
+        throws InterruptedException {
       ImmutableMap.Builder<SkyKey, SkyValue> builder = ImmutableMap.builder();
       ArrayList<SkyKey> missingKeys = new ArrayList<>(keySize);
       for (SkyKey key : keys) {
@@ -468,7 +481,7 @@
           missingKeys.add(key);
         }
       }
-      Map<SkyKey, NodeEntry> missingEntries =
+      Map<SkyKey, ? extends NodeEntry> missingEntries =
           getBatchValues(requestor, Reason.DEP_REQUESTED, missingKeys);
       for (SkyKey key : missingKeys) {
         builder.put(key, maybeGetValueFromError(key, missingEntries.get(key), bubbleErrorInfo));
@@ -477,8 +490,8 @@
     }
 
     @Override
-    protected Map<SkyKey, ValueOrUntypedException> getValueOrUntypedExceptions(
-        Set<SkyKey> depKeys) {
+    protected Map<SkyKey, ValueOrUntypedException> getValueOrUntypedExceptions(Set<SkyKey> depKeys)
+        throws InterruptedException {
       checkActive();
       Preconditions.checkState(
           !depKeys.contains(ErrorTransienceValue.KEY),
@@ -578,15 +591,20 @@
     }
 
     @Override
-    public <E1 extends Exception, E2 extends Exception, E3 extends Exception,
-            E4 extends Exception, E5 extends Exception>
+    public <
+            E1 extends Exception,
+            E2 extends Exception,
+            E3 extends Exception,
+            E4 extends Exception,
+            E5 extends Exception>
         Map<SkyKey, ValueOrException5<E1, E2, E3, E4, E5>> getValuesOrThrow(
             Iterable<SkyKey> depKeys,
             Class<E1> exceptionClass1,
             Class<E2> exceptionClass2,
             Class<E3> exceptionClass3,
             Class<E4> exceptionClass4,
-            Class<E5> exceptionClass5) {
+            Class<E5> exceptionClass5)
+            throws InterruptedException {
       newlyRequestedDeps.startGroup();
       Map<SkyKey, ValueOrException5<E1, E2, E3, E4, E5>> result = super.getValuesOrThrow(
           depKeys,
@@ -638,7 +656,7 @@
      * <p>The node entry is informed if the node's value and error are definitive via the flag
      * {@code completeValue}.
      */
-    void commit(NodeEntry primaryEntry, boolean enqueueParents) {
+    void commit(NodeEntry primaryEntry, boolean enqueueParents) throws InterruptedException {
       // Construct the definitive error info, if there is one.
       finalizeErrorInfo();
 
@@ -664,10 +682,8 @@
         // Remove the rdep on this entry for each of its old deps that is no longer a direct dep.
         Set<SkyKey> depsToRemove =
             Sets.difference(oldDeps, primaryEntry.getTemporaryDirectDeps().toSet());
-        Collection<NodeEntry> oldDepEntries = graph.getBatch(
-            skyKey,
-            Reason.RDEP_REMOVAL,
-            depsToRemove).values();
+        Collection<? extends NodeEntry> oldDepEntries =
+            graph.getBatch(skyKey, Reason.RDEP_REMOVAL, depsToRemove).values();
         for (NodeEntry oldDepEntry : oldDepEntries) {
           oldDepEntry.removeReverseDep(skyKey);
         }
@@ -754,7 +770,7 @@
 
     private ValueVisitor(ForkJoinPool forkJoinPool) {
       quiescingExecutor =
-          new ForkJoinQuiescingExecutor(forkJoinPool, VALUE_VISITOR_ERROR_CLASSIFIER, errorHandler);
+          new ForkJoinQuiescingExecutor(forkJoinPool, VALUE_VISITOR_ERROR_CLASSIFIER);
     }
 
     private ValueVisitor(int threadCount) {
@@ -766,8 +782,7 @@
               TimeUnit.SECONDS,
               /*failFastOnException*/ true,
               "skyframe-evaluator",
-              VALUE_VISITOR_ERROR_CLASSIFIER,
-              errorHandler);
+              VALUE_VISITOR_ERROR_CLASSIFIER);
     }
 
     private void waitForCompletion() throws InterruptedException {
@@ -884,14 +899,15 @@
      * Returns true if this depGroup consists of the error transience value and the error transience
      * value is newer than the entry, meaning that the entry must be re-evaluated.
      */
-    private boolean invalidatedByErrorTransience(Collection<SkyKey> depGroup, NodeEntry entry) {
+    private boolean invalidatedByErrorTransience(Collection<SkyKey> depGroup, NodeEntry entry)
+        throws InterruptedException {
       return depGroup.size() == 1
           && depGroup.contains(ErrorTransienceValue.KEY)
           && !graph.get(
               null, Reason.OTHER, ErrorTransienceValue.KEY).getVersion().atMost(entry.getVersion());
     }
 
-    private DirtyOutcome maybeHandleDirtyNode(NodeEntry state) {
+    private DirtyOutcome maybeHandleDirtyNode(NodeEntry state) throws InterruptedException {
       if (!state.isDirty()) {
         return DirtyOutcome.NEEDS_EVALUATION;
       }
@@ -934,9 +950,9 @@
             // is done, then it is the parent's responsibility to notice that, which we do here.
             // We check the deps for errors so that we don't continue building this node if it has
             // a child error.
-            Map<SkyKey, NodeEntry> entriesToCheck =
+            Map<SkyKey, ? extends NodeEntry> entriesToCheck =
                 graph.getBatch(skyKey, Reason.OTHER, directDepsToCheck);
-            for (Map.Entry<SkyKey, NodeEntry> entry : entriesToCheck.entrySet()) {
+            for (Entry<SkyKey, ? extends NodeEntry> entry : entriesToCheck.entrySet()) {
               if (entry.getValue().isDone() && entry.getValue().getErrorInfo() != null) {
                 // If any child has an error, we arbitrarily add a dep on the first one (needed
                 // for error bubbling) and throw an exception coming from it.
@@ -945,7 +961,7 @@
                 state.addTemporaryDirectDeps(GroupedListHelper.create(ImmutableList.of(errorKey)));
                 errorEntry.checkIfDoneForDirtyReverseDep(skyKey);
                 // Perform the necessary bookkeeping for any deps that are not being used.
-                for (Map.Entry<SkyKey, NodeEntry> depEntry : entriesToCheck.entrySet()) {
+                for (Entry<SkyKey, ? extends NodeEntry> depEntry : entriesToCheck.entrySet()) {
                   if (!depEntry.getKey().equals(errorKey)) {
                     depEntry.getValue().removeReverseDep(skyKey);
                   }
@@ -969,8 +985,10 @@
 
           // TODO(bazel-team): If this signals the current node, consider falling through to the
           // VERIFIED_CLEAN case below directly, without scheduling a new Evaluate().
-          for (Map.Entry<SkyKey, NodeEntry> e : graph.createIfAbsentBatch(
-              skyKey, Reason.ENQUEUING_CHILD, directDepsToCheck).entrySet()) {
+          for (Map.Entry<SkyKey, ? extends NodeEntry> e :
+              graph
+                  .createIfAbsentBatch(skyKey, Reason.ENQUEUING_CHILD, directDepsToCheck)
+                  .entrySet()) {
             SkyKey directDep = e.getKey();
             NodeEntry directDepEntry = e.getValue();
             enqueueChild(skyKey, state, directDep, directDepEntry, /*depAlreadyExists=*/ true);
@@ -1005,6 +1023,7 @@
 
     @Override
     public void run() {
+      try {
       NodeEntry state = Preconditions.checkNotNull(
           graph.get(null, Reason.EVALUATION, skyKey),
           skyKey);
@@ -1047,8 +1066,8 @@
             }
           }
 
-          Map<SkyKey, NodeEntry> newlyRequestedDeps =
-              getBatchValues(skyKey, Reason.RDEP_ADDITION, env.newlyRequestedDeps);
+            Map<SkyKey, ? extends NodeEntry> newlyRequestedDeps =
+                getBatchValues(skyKey, Reason.RDEP_ADDITION, env.newlyRequestedDeps);
           boolean isTransitivelyTransient = reifiedBuilderException.isTransient();
           for (NodeEntry depEntry
               : Iterables.concat(env.directDeps.values(), newlyRequestedDeps.values())) {
@@ -1073,11 +1092,6 @@
           }
           throw SchedulerException.ofError(errorInfo, skyKey);
         }
-      } catch (InterruptedException ie) {
-        // InterruptedException cannot be thrown by Runnable.run, so we must wrap it.
-        // Interrupts can be caught by both the Evaluator and the AbstractQueueVisitor.
-        // The former will unwrap the IE and propagate it as is; the latter will throw a new IE.
-        throw SchedulerException.ofInterruption(ie, skyKey);
       } catch (RuntimeException re) {
         // Programmer error (most likely NPE or a failed precondition in a SkyFunction). Output
         // some context together with the exception.
@@ -1127,24 +1141,24 @@
             skyKey,
             state,
             childErrorKey);
-        if (newDirectDeps.contains(childErrorKey)) {
-          // Add this dep if it was just requested. In certain rare race conditions (see
-          // MemoizingEvaluatorTest.cachedErrorCausesRestart) this dep may have already been
-          // requested.
-          state.addTemporaryDirectDeps(GroupedListHelper.create(ImmutableList.of(childErrorKey)));
-          DependencyState childErrorState;
-          if (oldDeps.contains(childErrorKey)) {
-            childErrorState = childErrorEntry.checkIfDoneForDirtyReverseDep(skyKey);
-          } else {
-            childErrorState = childErrorEntry.addReverseDepAndCheckIfDone(skyKey);
-          }
-          Preconditions.checkState(
-              childErrorState == DependencyState.DONE,
-              "skyKey: %s, state: %s childErrorKey: %s",
-              skyKey,
-              state,
-              childErrorKey,
-              childErrorEntry);
+          if (newDirectDeps.contains(childErrorKey)) {
+            // Add this dep if it was just requested. In certain rare race conditions (see
+            // MemoizingEvaluatorTest.cachedErrorCausesRestart) this dep may have already been
+            // requested.
+            state.addTemporaryDirectDeps(GroupedListHelper.create(ImmutableList.of(childErrorKey)));
+            DependencyState childErrorState;
+            if (oldDeps.contains(childErrorKey)) {
+              childErrorState = childErrorEntry.checkIfDoneForDirtyReverseDep(skyKey);
+            } else {
+              childErrorState = childErrorEntry.addReverseDepAndCheckIfDone(skyKey);
+            }
+            Preconditions.checkState(
+                childErrorState == DependencyState.DONE,
+                "skyKey: %s, state: %s childErrorKey: %s",
+                skyKey,
+                state,
+                childErrorKey,
+                childErrorEntry);
         }
         ErrorInfo childErrorInfo = Preconditions.checkNotNull(childErrorEntry.getErrorInfo());
         visitor.preventNewEvaluations();
@@ -1180,8 +1194,8 @@
         return;
       }
 
-      for (Map.Entry<SkyKey, NodeEntry> e
-          : graph.createIfAbsentBatch(skyKey, Reason.ENQUEUING_CHILD, newDirectDeps).entrySet()) {
+        for (Entry<SkyKey, ? extends NodeEntry> e :
+            graph.createIfAbsentBatch(skyKey, Reason.ENQUEUING_CHILD, newDirectDeps).entrySet()) {
         SkyKey newDirectDep = e.getKey();
         NodeEntry newDirectDepEntry = e.getValue();
         enqueueChild(
@@ -1191,6 +1205,12 @@
             newDirectDepEntry,
             /*depAlreadyExists=*/ oldDeps.contains(newDirectDep));
       }
+      } catch (InterruptedException ie) {
+        // InterruptedException cannot be thrown by Runnable.run, so we must wrap it.
+        // Interrupts can be caught by both the Evaluator and the AbstractQueueVisitor.
+        // The former will unwrap the IE and propagate it as is; the latter will throw a new IE.
+        throw SchedulerException.ofInterruption(ie, skyKey);
+      }
       // It is critical that there is no code below this point.
     }
 
@@ -1219,17 +1239,16 @@
 
   /**
    * Signals all parents that this node is finished. If visitor is not null, also enqueues any
-   * parents that are ready. If visitor is null, indicating that we are building this node after
-   * the main build aborted, then skip any parents that are already done (that can happen with
-   * cycles).
+   * parents that are ready. If visitor is null, indicating that we are building this node after the
+   * main build aborted, then skip any parents that are already done (that can happen with cycles).
    */
   private void signalValuesAndEnqueueIfReady(
-      @Nullable ValueVisitor visitor, SkyKey skyKey, Iterable<SkyKey> keys, Version version) {
+      @Nullable ValueVisitor visitor, SkyKey skyKey, Iterable<SkyKey> keys, Version version)
+      throws InterruptedException {
     // No fields of the entry are needed here, since we're just enqueuing for evaluation, but more
     // importantly, these hints are not respected for not-done nodes. If they are, we may need to
     // alter this hint.
-    Map<SkyKey, NodeEntry> batch =
-        graph.getBatch(skyKey, Reason.SIGNAL_DEP, keys);
+    Map<SkyKey, ? extends NodeEntry> batch = graph.getBatch(skyKey, Reason.SIGNAL_DEP, keys);
     if (visitor != null) {
       for (SkyKey key : keys) {
         NodeEntry entry = Preconditions.checkNotNull(batch.get(key), key);
@@ -1252,7 +1271,8 @@
    * If child is not done, removes {@param inProgressParent} from {@param child}'s reverse deps.
    * Returns whether child should be removed from inProgressParent's entry's direct deps.
    */
-  private boolean removeIncompleteChildForCycle(SkyKey inProgressParent, SkyKey child) {
+  private boolean removeIncompleteChildForCycle(SkyKey inProgressParent, SkyKey child)
+      throws InterruptedException {
     NodeEntry childEntry = graph.get(inProgressParent, Reason.CYCLE_CHECKING, child);
     if (!isDoneForBuild(childEntry)) {
       childEntry.removeInProgressReverseDep(inProgressParent);
@@ -1272,7 +1292,7 @@
   private static void registerNewlyDiscoveredDepsForDoneEntry(
       SkyKey skyKey,
       NodeEntry entry,
-      Map<SkyKey, NodeEntry> newlyRequestedDepMap,
+      Map<SkyKey, ? extends NodeEntry> newlyRequestedDepMap,
       Set<SkyKey> oldDeps,
       SkyFunctionEnvironment env) {
     Set<SkyKey> unfinishedDeps = new HashSet<>();
@@ -1300,7 +1320,8 @@
     Preconditions.checkState(entry.isReady(), "%s %s %s", skyKey, entry, env.newlyRequestedDeps);
   }
 
-  private void informProgressReceiverThatValueIsDone(SkyKey key, NodeEntry entry) {
+  private void informProgressReceiverThatValueIsDone(SkyKey key, NodeEntry entry)
+      throws InterruptedException {
     if (progressReceiver != null) {
       Preconditions.checkState(entry.isDone(), entry);
       SkyValue value = entry.getValue();
@@ -1327,7 +1348,8 @@
     // directly without launching the heavy machinery, spawning threads, etc.
     // Inform progressReceiver that these nodes are done to be consistent with the main code path.
     boolean allAreDone = true;
-    Map<SkyKey, NodeEntry> batch = getBatchValues(null, Reason.PRE_OR_POST_EVALUATION, skyKeySet);
+    Map<SkyKey, ? extends NodeEntry> batch =
+        getBatchValues(null, Reason.PRE_OR_POST_EVALUATION, skyKeySet);
     for (SkyKey key : skyKeySet) {
       if (!isDoneForBuild(batch.get(key))) {
         allAreDone = false;
@@ -1401,8 +1423,8 @@
           graph,
           dirtyKeyTracker);
     }
-    for (Map.Entry<SkyKey, NodeEntry> e
-        : graph.createIfAbsentBatch(null, Reason.PRE_OR_POST_EVALUATION, skyKeys).entrySet()) {
+    for (Entry<SkyKey, ? extends NodeEntry> e :
+        graph.createIfAbsentBatch(null, Reason.PRE_OR_POST_EVALUATION, skyKeys).entrySet()) {
       SkyKey skyKey = e.getKey();
       NodeEntry entry = e.getValue();
       // This must be equivalent to the code in enqueueChild above, in order to be thread-safe.
@@ -1477,23 +1499,31 @@
   }
 
   /**
-   * Walk up graph to find a top-level node (without parents) that wanted this failure. Store
-   * the failed nodes along the way in a map, with ErrorInfos that are appropriate for that layer.
+   * Walk up graph to find a top-level node (without parents) that wanted this failure. Store the
+   * failed nodes along the way in a map, with ErrorInfos that are appropriate for that layer.
    * Example:
+   *
+   * <pre>
    *                      foo   bar
    *                        \   /
    *           unrequested   baz
    *                     \    |
    *                      failed-node
+   * </pre>
+   *
    * User requests foo, bar. When failed-node fails, we look at its parents. unrequested is not
    * in-flight, so we replace failed-node by baz and repeat. We look at baz's parents. foo is
-   * in-flight, so we replace baz by foo. Since foo is a top-level node and doesn't have parents,
-   * we then break, since we know a top-level node, foo, that depended on the failed node.
+   * in-flight, so we replace baz by foo. Since foo is a top-level node and doesn't have parents, we
+   * then break, since we know a top-level node, foo, that depended on the failed node.
    *
-   * There's the potential for a weird "track jump" here in the case:
+   * <p>There's the potential for a weird "track jump" here in the case:
+   *
+   * <pre>
    *                        foo
    *                       / \
    *                   fail1 fail2
+   * </pre>
+   *
    * If fail1 and fail2 fail simultaneously, fail2 may start propagating up in the loop below.
    * However, foo requests fail1 first, and then throws an exception based on that. This is not
    * incorrect, but may be unexpected.
@@ -1506,8 +1536,9 @@
    * <p>Note that we are not propagating error to the first top-level node but to the highest one,
    * because during this process we can add useful information about error from other nodes.
    */
-  private Map<SkyKey, ValueWithMetadata> bubbleErrorUp(final ErrorInfo leafFailure,
-      SkyKey errorKey, Iterable<SkyKey> skyKeys, ValueVisitor visitor) {
+  private Map<SkyKey, ValueWithMetadata> bubbleErrorUp(
+      final ErrorInfo leafFailure, SkyKey errorKey, Iterable<SkyKey> skyKeys, ValueVisitor visitor)
+      throws InterruptedException {
     Set<SkyKey> rootValues = ImmutableSet.copyOf(skyKeys);
     ErrorInfo error = leafFailure;
     Map<SkyKey, ValueWithMetadata> bubbleErrorInfo = new HashMap<>();
@@ -1651,9 +1682,9 @@
   }
 
   /**
-   * Constructs an {@link EvaluationResult} from the {@link #graph}.  Looks for cycles if there
-   * are unfinished nodes but no error was already found through bubbling up
-   * (as indicated by {@code bubbleErrorInfo} being null).
+   * Constructs an {@link EvaluationResult} from the {@link #graph}. Looks for cycles if there are
+   * unfinished nodes but no error was already found through bubbling up (as indicated by {@code
+   * bubbleErrorInfo} being null).
    *
    * <p>{@code visitor} may be null, but only in the case where all graph entries corresponding to
    * {@code skyKeys} are known to be in the DONE state ({@code entry.isDone()} returns true).
@@ -1662,7 +1693,8 @@
       @Nullable ValueVisitor visitor,
       Iterable<SkyKey> skyKeys,
       @Nullable Map<SkyKey, ValueWithMetadata> bubbleErrorInfo,
-      boolean catastrophe) {
+      boolean catastrophe)
+      throws InterruptedException {
     Preconditions.checkState(
         catastrophe == (keepGoing && bubbleErrorInfo != null),
         "Catastrophe not consistent with keepGoing mode and bubbleErrorInfo: %s %s %s %s",
@@ -1739,8 +1771,11 @@
   }
 
   private <T extends SkyValue> void checkForCycles(
-      Iterable<SkyKey> badRoots, EvaluationResult.Builder<T> result, final ValueVisitor visitor,
-      boolean keepGoing) {
+      Iterable<SkyKey> badRoots,
+      EvaluationResult.Builder<T> result,
+      final ValueVisitor visitor,
+      boolean keepGoing)
+      throws InterruptedException {
     try (AutoProfiler p = AutoProfiler.logged("Checking for Skyframe cycles", LOG, 10)) {
       for (SkyKey root : badRoots) {
         ErrorInfo errorInfo = checkForCycles(root, visitor, keepGoing);
@@ -1774,13 +1809,13 @@
   /**
    * The algorithm for this cycle detector is as follows. We visit the graph depth-first, keeping
    * track of the path we are currently on. We skip any DONE nodes (they are transitively
-   * error-free). If we come to a node already on the path, we immediately construct a cycle. If
-   * we are in the noKeepGoing case, we return ErrorInfo with that cycle to the caller. Otherwise,
-   * we continue. Once all of a node's children are done, we construct an error value for it, based
-   * on those children. Finally, when the original root's node is constructed, we return its
-   * ErrorInfo.
+   * error-free). If we come to a node already on the path, we immediately construct a cycle. If we
+   * are in the noKeepGoing case, we return ErrorInfo with that cycle to the caller. Otherwise, we
+   * continue. Once all of a node's children are done, we construct an error value for it, based on
+   * those children. Finally, when the original root's node is constructed, we return its ErrorInfo.
    */
-  private ErrorInfo checkForCycles(SkyKey root, ValueVisitor visitor, boolean keepGoing) {
+  private ErrorInfo checkForCycles(SkyKey root, ValueVisitor visitor, boolean keepGoing)
+      throws InterruptedException {
     // The number of cycles found. Do not keep on searching for more cycles after this many were
     // found.
     int cyclesFound = 0;
@@ -1926,7 +1961,7 @@
       // out.
       // TODO(janakr): If graph implementations start using these hints for not-done nodes, we may
       // have to change this.
-      Map<SkyKey, NodeEntry> childrenNodes =
+      Map<SkyKey, ? extends NodeEntry> childrenNodes =
           graph.getBatch(key, Reason.EXISTENCE_CHECKING, children);
       Preconditions.checkState(childrenNodes.size() == Iterables.size(children), childrenNodes);
       children = Maps.filterValues(childrenNodes, new Predicate<NodeEntry>() {
@@ -1962,7 +1997,8 @@
    * @param children child nodes to query for errors.
    * @return List of ErrorInfos from all children that had errors.
    */
-  private List<ErrorInfo> getChildrenErrorsForCycle(SkyKey parent, Iterable<SkyKey> children) {
+  private List<ErrorInfo> getChildrenErrorsForCycle(SkyKey parent, Iterable<SkyKey> children)
+      throws InterruptedException {
     List<ErrorInfo> allErrors = new ArrayList<>();
     boolean foundCycle = false;
     for (NodeEntry childNode : getAndCheckDoneBatchForCycle(parent, children).values()) {
@@ -1984,11 +2020,11 @@
    * @return List of ErrorInfos from all children that had errors.
    */
   private List<ErrorInfo> getChildrenErrorsForCycleChecking(
-      Iterable<SkyKey> children, SkyKey unfinishedChild) {
+      Iterable<SkyKey> children, SkyKey unfinishedChild) throws InterruptedException {
     List<ErrorInfo> allErrors = new ArrayList<>();
-    Set<Entry<SkyKey, NodeEntry>> childEntries =
+    Set<? extends Entry<SkyKey, ? extends NodeEntry>> childEntries =
         getBatchValues(null, Reason.CYCLE_CHECKING, children).entrySet();
-    for (Entry<SkyKey, NodeEntry> childMapEntry : childEntries) {
+    for (Entry<SkyKey, ? extends NodeEntry> childMapEntry : childEntries) {
       SkyKey childKey = childMapEntry.getKey();
       NodeEntry childNodeEntry = childMapEntry.getValue();
       ErrorInfo errorInfo = getErrorMaybe(childKey, childNodeEntry,
@@ -2001,7 +2037,8 @@
   }
 
   @Nullable
-  private ErrorInfo getErrorMaybe(SkyKey key, NodeEntry childNodeEntry, boolean allowUnfinished) {
+  private static ErrorInfo getErrorMaybe(
+      SkyKey key, NodeEntry childNodeEntry, boolean allowUnfinished) throws InterruptedException {
     Preconditions.checkNotNull(childNodeEntry, key);
     if (!allowUnfinished) {
       return checkDone(key, childNodeEntry).getErrorInfo();
@@ -2027,7 +2064,8 @@
       NodeEntry entry,
       @Nullable SkyKey cycleChild,
       Iterable<SkyKey> toVisit,
-      int cycleLength) {
+      int cycleLength)
+      throws InterruptedException {
     GroupedList<SkyKey> directDeps = entry.getTemporaryDirectDeps();
     Set<SkyKey> unvisitedDeps = Sets.newHashSetWithExpectedSize(directDeps.numElements());
     Iterables.addAll(unvisitedDeps, Iterables.concat(directDeps));
@@ -2069,7 +2107,7 @@
   }
 
   private Set<SkyKey> removeIncompleteChildrenForCycle(
-      SkyKey key, NodeEntry entry, Iterable<SkyKey> children) {
+      SkyKey key, NodeEntry entry, Iterable<SkyKey> children) throws InterruptedException {
     Set<SkyKey> unfinishedDeps = new HashSet<>();
     for (SkyKey child : children) {
       if (removeIncompleteChildForCycle(key, child)) {
@@ -2086,14 +2124,14 @@
     return entry;
   }
 
-  private NodeEntry getAndCheckDoneForCycle(SkyKey key) {
+  private NodeEntry getAndCheckDoneForCycle(SkyKey key) throws InterruptedException {
     return checkDone(key, graph.get(null, Reason.CYCLE_CHECKING, key));
   }
 
-  private Map<SkyKey, NodeEntry> getAndCheckDoneBatchForCycle(
-      SkyKey parent, Iterable<SkyKey> keys) {
-    Map<SkyKey, NodeEntry> nodes = getBatchValues(parent, Reason.CYCLE_CHECKING, keys);
-    for (Map.Entry<SkyKey, NodeEntry> nodeEntryMapEntry : nodes.entrySet()) {
+  private Map<SkyKey, ? extends NodeEntry> getAndCheckDoneBatchForCycle(
+      SkyKey parent, Iterable<SkyKey> keys) throws InterruptedException {
+    Map<SkyKey, ? extends NodeEntry> nodes = getBatchValues(parent, Reason.CYCLE_CHECKING, keys);
+    for (Entry<SkyKey, ? extends NodeEntry> nodeEntryMapEntry : nodes.entrySet()) {
       checkDone(nodeEntryMapEntry.getKey(), nodeEntryMapEntry.getValue());
     }
     return nodes;
@@ -2104,7 +2142,8 @@
   private static SkyValue maybeGetValueFromError(
       SkyKey key,
       @Nullable NodeEntry entry,
-      @Nullable Map<SkyKey, ValueWithMetadata> bubbleErrorInfo) {
+      @Nullable Map<SkyKey, ValueWithMetadata> bubbleErrorInfo)
+      throws InterruptedException {
     SkyValue value = bubbleErrorInfo == null ? null : bubbleErrorInfo.get(key);
     if (value != null) {
       Preconditions.checkNotNull(
@@ -2127,8 +2166,9 @@
       Map<SkyKey, SkyValue> injectionMap,
       Version version,
       EvaluableGraph graph,
-      DirtyKeyTracker dirtyKeyTracker) {
-    Map<SkyKey, NodeEntry> prevNodeEntries =
+      DirtyKeyTracker dirtyKeyTracker)
+      throws InterruptedException {
+    Map<SkyKey, ? extends NodeEntry> prevNodeEntries =
         graph.createIfAbsentBatch(null, Reason.OTHER, injectionMap.keySet());
     for (Map.Entry<SkyKey, SkyValue> injectionEntry : injectionMap.entrySet()) {
       SkyKey key = injectionEntry.getKey();
diff --git a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
index f76c0ae..0286844 100644
--- a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
@@ -15,10 +15,15 @@
 
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import java.util.Map;
-
 import javax.annotation.Nullable;
 
-/** A graph that exposes its entries and structure, for use by classes that must traverse it. */
+/**
+ * A graph that exposes its entries and structure, for use by classes that must traverse it.
+ *
+ * <p>Certain graph implementations can throw {@link InterruptedException} when trying to retrieve
+ * node entries. Such exceptions should not be caught locally -- they should be allowed to propagate
+ * up.
+ */
 @ThreadSafe
 public interface QueryableGraph {
   /**
@@ -29,18 +34,19 @@
    * @param reason the reason the node is being requested.
    */
   @Nullable
-  NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey key);
+  NodeEntry get(@Nullable SkyKey requestor, Reason reason, SkyKey key) throws InterruptedException;
 
   /**
    * Fetches all the given nodes. Returns a map {@code m} such that, for all {@code k} in {@code
    * keys}, {@code m.get(k).equals(e)} iff {@code get(k) == e} and {@code e != null}, and {@code
    * !m.containsKey(k)} iff {@code get(k) == null}.
-   * 
+   *
    * @param requestor if non-{@code null}, the node on behalf of which the given {@code keys} are
    *     being requested.
    * @param reason the reason the nodes are being requested.
    */
-  Map<SkyKey, NodeEntry> getBatch(@Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys);
+  Map<SkyKey, ? extends NodeEntry> getBatch(
+      @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys) throws InterruptedException;
 
   /**
    * The reason that a node is being looked up in the Skyframe graph.
diff --git a/src/main/java/com/google/devtools/build/skyframe/QueryableGraphBackedSkyFunctionEnvironment.java b/src/main/java/com/google/devtools/build/skyframe/QueryableGraphBackedSkyFunctionEnvironment.java
index 79ed640..ef96167 100644
--- a/src/main/java/com/google/devtools/build/skyframe/QueryableGraphBackedSkyFunctionEnvironment.java
+++ b/src/main/java/com/google/devtools/build/skyframe/QueryableGraphBackedSkyFunctionEnvironment.java
@@ -13,19 +13,14 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
-import com.google.common.base.Function;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
-import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.skyframe.QueryableGraph.Reason;
-import java.util.HashMap;
 import java.util.Map;
 import java.util.Set;
 
-import javax.annotation.Nullable;
-
 /**
  * A {@link SkyFunction.Environment} backed by a {@link QueryableGraph}. For use when a single
  * SkyFunction needs recomputation, and its dependencies do not need to be evaluated. Any missing
@@ -41,41 +36,40 @@
     this.eventHandler = eventHandler;
   }
 
-  private static final Function<NodeEntry, ValueOrUntypedException> NODE_ENTRY_TO_UNTYPED_VALUE =
-      new Function<NodeEntry, ValueOrUntypedException>() {
-        @Override
-        public ValueOrUntypedException apply(@Nullable NodeEntry nodeEntry) {
-          if (nodeEntry == null || !nodeEntry.isDone()) {
-            return ValueOrExceptionUtils.ofNull();
-          }
-          SkyValue maybeWrappedValue = nodeEntry.getValueMaybeWithMetadata();
-          SkyValue justValue = ValueWithMetadata.justValue(maybeWrappedValue);
-          if (justValue != null) {
-            return ValueOrExceptionUtils.ofValueUntyped(justValue);
-          }
-          ErrorInfo errorInfo =
-              Preconditions.checkNotNull(ValueWithMetadata.getMaybeErrorInfo(maybeWrappedValue));
-          Exception exception = errorInfo.getException();
+  private static ValueOrUntypedException toUntypedValue(NodeEntry nodeEntry)
+      throws InterruptedException {
+    if (nodeEntry == null || !nodeEntry.isDone()) {
+      return ValueOrExceptionUtils.ofNull();
+    }
+    SkyValue maybeWrappedValue = nodeEntry.getValueMaybeWithMetadata();
+    SkyValue justValue = ValueWithMetadata.justValue(maybeWrappedValue);
+    if (justValue != null) {
+      return ValueOrExceptionUtils.ofValueUntyped(justValue);
+    }
+    ErrorInfo errorInfo =
+        Preconditions.checkNotNull(ValueWithMetadata.getMaybeErrorInfo(maybeWrappedValue));
+    Exception exception = errorInfo.getException();
 
-          if (exception != null) {
-            // Give SkyFunction#compute a chance to handle this exception.
-            return ValueOrExceptionUtils.ofExn(exception);
-          }
-          // In a cycle.
-          Preconditions.checkState(
-              !Iterables.isEmpty(errorInfo.getCycleInfo()), "%s %s", errorInfo, maybeWrappedValue);
-          return ValueOrExceptionUtils.ofNull();
-        }
-      };
+    if (exception != null) {
+      // Give SkyFunction#compute a chance to handle this exception.
+      return ValueOrExceptionUtils.ofExn(exception);
+    }
+    // In a cycle.
+    Preconditions.checkState(
+        !Iterables.isEmpty(errorInfo.getCycleInfo()), "%s %s", errorInfo, maybeWrappedValue);
+    return ValueOrExceptionUtils.ofNull();
+  }
 
   @Override
-  protected Map<SkyKey, ValueOrUntypedException> getValueOrUntypedExceptions(Set<SkyKey> depKeys) {
-    Map<SkyKey, NodeEntry> resultMap = queryableGraph.getBatch(null, Reason.DEP_REQUESTED, depKeys);
-    Map<SkyKey, NodeEntry> resultWithMissingKeys = new HashMap<>(resultMap);
-    for (SkyKey missingDep : Sets.difference(depKeys, resultMap.keySet())) {
-      resultWithMissingKeys.put(missingDep, null);
+  protected Map<SkyKey, ValueOrUntypedException> getValueOrUntypedExceptions(Set<SkyKey> depKeys)
+      throws InterruptedException {
+    Map<SkyKey, ? extends NodeEntry> resultMap =
+        queryableGraph.getBatch(null, Reason.DEP_REQUESTED, depKeys);
+    Map<SkyKey, ValueOrUntypedException> result = Maps.newHashMapWithExpectedSize(depKeys.size());
+    for (SkyKey dep : depKeys) {
+      result.put(dep, toUntypedValue(resultMap.get(dep)));
     }
-    return Maps.transformValues(resultWithMissingKeys, NODE_ENTRY_TO_UNTYPED_VALUE);
+    return result;
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/skyframe/SequentialBuildDriver.java b/src/main/java/com/google/devtools/build/skyframe/SequentialBuildDriver.java
index c65f681..905c25f 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SequentialBuildDriver.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SequentialBuildDriver.java
@@ -16,7 +16,6 @@
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.common.options.OptionsClassProvider;
-
 import javax.annotation.Nullable;
 
 /**
@@ -60,7 +59,7 @@
 
   @Nullable
   @Override
-  public ErrorInfo getExistingErrorForTesting(SkyKey key) {
+  public ErrorInfo getExistingErrorForTesting(SkyKey key) throws InterruptedException {
     return memoizingEvaluator.getExistingErrorForTesting(key);
   }
 
diff --git a/src/main/java/com/google/devtools/build/skyframe/SkyFunction.java b/src/main/java/com/google/devtools/build/skyframe/SkyFunction.java
index 637c202..6bd52c6 100644
--- a/src/main/java/com/google/devtools/build/skyframe/SkyFunction.java
+++ b/src/main/java/com/google/devtools/build/skyframe/SkyFunction.java
@@ -16,9 +16,7 @@
 import com.google.common.annotations.VisibleForTesting;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.events.EventHandler;
-
 import java.util.Map;
-
 import javax.annotation.Nullable;
 
 /**
@@ -67,56 +65,83 @@
   String extractTag(SkyKey skyKey);
 
   /**
-   * The services provided to the {@link SkyFunction} implementation by the graph implementation.
+   * The services provided to the {@link SkyFunction#compute} implementation by the Skyframe
+   * evaluation framework.
    */
   interface Environment {
     /**
      * Returns a direct dependency. If the specified value is not in the set of already evaluated
-     * direct dependencies, returns {@code null}. Also returns {@code null} if the specified
-     * value has already been evaluated and found to be in error.
+     * direct dependencies, returns {@code null}. Also returns {@code null} if the specified value
+     * has already been evaluated and found to be in error.
      *
      * <p>On a subsequent evaluation, if any of this value's dependencies have changed they will be
-     * re-evaluated in the same order as originally requested by the {@code SkyFunction} using
-     * this {@code getValue} call (see {@link #getValues} for when preserving the order is not
+     * re-evaluated in the same order as originally requested by the {@code SkyFunction} using this
+     * {@code getValue} call (see {@link #getValues} for when preserving the order is not
      * important).
+     *
+     * <p>This method and the ones below may throw {@link InterruptedException}. Such exceptions
+     * must not be caught by the {@link SkyFunction#compute} implementation. Instead, they should be
+     * propagated up to the caller of {@link SkyFunction#compute}.
      */
     @Nullable
-    SkyValue getValue(SkyKey valueName);
+    SkyValue getValue(SkyKey valueName) throws InterruptedException;
 
     /**
      * Returns a direct dependency. If the specified value is not in the set of already evaluated
-     * direct dependencies, returns {@code null}. If the specified value has already been
-     * evaluated and found to be in error, throws the exception coming from the error, so long as
-     * the exception is of one of the specified types. SkyFunction implementations may use this
-     * method to continue evaluation even if one of their dependencies is in error by catching
-     * the thrown exception and proceeding. The caller must specify the exception type(s) that
-     * might be thrown using the {@code exceptionClass} argument(s). If the dependency's
-     * exception is not an instance of {@code exceptionClass}, {@code null} is returned.
+     * direct dependencies, returns {@code null}. If the specified value has already been evaluated
+     * and found to be in error, throws the exception coming from the error, so long as the
+     * exception is of one of the specified types. SkyFunction implementations may use this method
+     * to continue evaluation even if one of their dependencies is in error by catching the thrown
+     * exception and proceeding. The caller must specify the exception type(s) that might be thrown
+     * using the {@code exceptionClass} argument(s). If the dependency's exception is not an
+     * instance of {@code exceptionClass}, {@code null} is returned.
      *
      * <p>The exception class given cannot be a supertype or a subtype of {@link RuntimeException},
-     * or a subtype of {@link InterruptedException}. See
-     * {@link SkyFunctionException#validateExceptionType} for details.
+     * or a subtype of {@link InterruptedException}. See {@link
+     * SkyFunctionException#validateExceptionType} for details.
      */
     @Nullable
-    <E extends Exception> SkyValue getValueOrThrow(SkyKey depKey, Class<E> exceptionClass) throws E;
+    <E extends Exception> SkyValue getValueOrThrow(SkyKey depKey, Class<E> exceptionClass)
+        throws E, InterruptedException;
+
     @Nullable
-    <E1 extends Exception, E2 extends Exception> SkyValue getValueOrThrow(SkyKey depKey,
-        Class<E1> exceptionClass1, Class<E2> exceptionClass2) throws E1, E2;
+    <E1 extends Exception, E2 extends Exception> SkyValue getValueOrThrow(
+        SkyKey depKey, Class<E1> exceptionClass1, Class<E2> exceptionClass2)
+        throws E1, E2, InterruptedException;
+
     @Nullable
     <E1 extends Exception, E2 extends Exception, E3 extends Exception> SkyValue getValueOrThrow(
-        SkyKey depKey, Class<E1> exceptionClass1, Class<E2> exceptionClass2,
-        Class<E3> exceptionClass3) throws E1, E2, E3;
+        SkyKey depKey,
+        Class<E1> exceptionClass1,
+        Class<E2> exceptionClass2,
+        Class<E3> exceptionClass3)
+        throws E1, E2, E3, InterruptedException;
+
     @Nullable
     <E1 extends Exception, E2 extends Exception, E3 extends Exception, E4 extends Exception>
-        SkyValue getValueOrThrow(SkyKey depKey, Class<E1> exceptionClass1,
-        Class<E2> exceptionClass2, Class<E3> exceptionClass3, Class<E4> exceptionClass4)
-            throws E1, E2, E3, E4;
+        SkyValue getValueOrThrow(
+            SkyKey depKey,
+            Class<E1> exceptionClass1,
+            Class<E2> exceptionClass2,
+            Class<E3> exceptionClass3,
+            Class<E4> exceptionClass4)
+            throws E1, E2, E3, E4, InterruptedException;
+
     @Nullable
-    <E1 extends Exception, E2 extends Exception, E3 extends Exception, E4 extends Exception,
-     E5 extends Exception>
-        SkyValue getValueOrThrow(SkyKey depKey, Class<E1> exceptionClass1,
-        Class<E2> exceptionClass2, Class<E3> exceptionClass3, Class<E4> exceptionClass4,
-        Class<E5> exceptionClass5) throws E1, E2, E3, E4, E5;
+    <
+            E1 extends Exception,
+            E2 extends Exception,
+            E3 extends Exception,
+            E4 extends Exception,
+            E5 extends Exception>
+        SkyValue getValueOrThrow(
+            SkyKey depKey,
+            Class<E1> exceptionClass1,
+            Class<E2> exceptionClass2,
+            Class<E3> exceptionClass3,
+            Class<E4> exceptionClass4,
+            Class<E5> exceptionClass5)
+            throws E1, E2, E3, E4, E5, InterruptedException;
 
     /**
      * Requests {@code depKeys} "in parallel", independent of each others' values. These keys may be
@@ -131,27 +156,27 @@
      * <p>This means that on subsequent evaluations, when checking to see if dependencies require
      * re-evaluation, all the values in this group may be simultaneously checked. A SkyFunction
      * should request a dependency group if checking the deps serially on a subsequent evaluation
-     * would take too long, and if the {@link #compute} method would request all deps anyway as
-     * long as no earlier deps had changed. SkyFunction.Environment implementations may also
-     * choose to request these deps in parallel on the first evaluation, potentially speeding it up.
+     * would take too long, and if the {@link #compute} method would request all deps anyway as long
+     * as no earlier deps had changed. SkyFunction.Environment implementations may also choose to
+     * request these deps in parallel on the first evaluation, potentially speeding it up.
      *
-     * <p>While re-evaluating every value in the group may take longer than re-evaluating just
-     * the first one and finding that it has changed, no extra work is done: the contract of the
+     * <p>While re-evaluating every value in the group may take longer than re-evaluating just the
+     * first one and finding that it has changed, no extra work is done: the contract of the
      * dependency group means that the {@link #compute} method, when called to re-evaluate this
      * value, will request all values in the group again anyway, so they would have to have been
      * built in any case.
      *
      * <p>Example of when to use getValues: A ListProcessor value is built with key inputListRef.
-     * The {@link #compute} method first calls getValue(InputList.key(inputListRef)), and
-     * retrieves inputList. It then iterates through inputList, calling getValue on each input.
-     * Finally, it processes the whole list and returns. Say inputList is (a, b, c). Since the
-     * {@link #compute} method will unconditionally call getValue(a), getValue(b), and getValue
-     * (c), the {@link #compute} method can instead just call getValues({a, b, c}). If the value
-     * is later dirtied the evaluator will evaluate a, b, and c in parallel (assuming the inputList
-     * value was unchanged), and re-evaluate the ListProcessor value only if at least one of them
-     * was changed. On the other hand, if the InputList changes to be (a, b, d), then the
-     * evaluator will see that the first dep has changed, and call the {@link #compute} method to
-     * re-evaluate from scratch, without considering the dep group of {a, b, c}.
+     * The {@link #compute} method first calls getValue(InputList.key(inputListRef)), and retrieves
+     * inputList. It then iterates through inputList, calling getValue on each input. Finally, it
+     * processes the whole list and returns. Say inputList is (a, b, c). Since the {@link #compute}
+     * method will unconditionally call getValue(a), getValue(b), and getValue (c), the {@link
+     * #compute} method can instead just call getValues({a, b, c}). If the value is later dirtied
+     * the evaluator will evaluate a, b, and c in parallel (assuming the inputList value was
+     * unchanged), and re-evaluate the ListProcessor value only if at least one of them was changed.
+     * On the other hand, if the InputList changes to be (a, b, d), then the evaluator will see that
+     * the first dep has changed, and call the {@link #compute} method to re-evaluate from scratch,
+     * without considering the dep group of {a, b, c}.
      *
      * <p>Example of when not to use getValues: A BestMatch value is built with key
      * &lt;potentialMatchesRef, matchCriterion&gt;. The {@link #compute} method first calls
@@ -165,43 +190,64 @@
      * is {@code true}, and, {@code m.get(k) != null} iff the dependency was already evaluated and
      * was not in error.
      */
-    Map<SkyKey, SkyValue> getValues(Iterable<SkyKey> depKeys);
+    Map<SkyKey, SkyValue> getValues(Iterable<SkyKey> depKeys) throws InterruptedException;
 
     /**
-     * Similar to {@link #getValues} but allows the caller to specify a set of types that are
-     * proper subtypes of Exception (see {@link SkyFunctionException} for more details) to find
-     * out whether any of the dependencies' evaluations resulted in exceptions of those types.
-     * The returned objects may throw when attempting to retrieve their value.
+     * Similar to {@link #getValues} but allows the caller to specify a set of types that are proper
+     * subtypes of Exception (see {@link SkyFunctionException} for more details) to find out whether
+     * any of the dependencies' evaluations resulted in exceptions of those types. The returned
+     * objects may throw when attempting to retrieve their value.
      *
-     * <p>Callers should prioritize their responsibility to detect and handle errors in the
-     * returned map over their responsibility to return {@code null} if values are missing. This
-     * is because in nokeep_going evaluations, an error from a low level dependency is given a
-     * chance to be enriched by its reverse-dependencies, if possible.
+     * <p>Callers should prioritize their responsibility to detect and handle errors in the returned
+     * map over their responsibility to return {@code null} if values are missing. This is because
+     * in nokeep_going evaluations, an error from a low level dependency is given a chance to be
+     * enriched by its reverse-dependencies, if possible.
      *
-     * <p>Returns a map, {@code m}. For all {@code k} in {@code depKeys}, {@code m.get(k) !=
-     * null}. For all {@code v} such that there is some {@code k} such that {@code m.get(k) ==
-     * v}, the following is true: {@code v.get() != null} iff the dependency {@code k} was
-     * already evaluated and was not in error. {@code v.get()} throws {@code E} iff the
-     * dependency {@code k} was already evaluated with an error in the specified set of {@link
-     * Exception} types.
+     * <p>Returns a map, {@code m}. For all {@code k} in {@code depKeys}, {@code m.get(k) != null}.
+     * For all {@code v} such that there is some {@code k} such that {@code m.get(k) == v}, the
+     * following is true: {@code v.get() != null} iff the dependency {@code k} was already evaluated
+     * and was not in error. {@code v.get()} throws {@code E} iff the dependency {@code k} was
+     * already evaluated with an error in the specified set of {@link Exception} types.
      */
     <E extends Exception> Map<SkyKey, ValueOrException<E>> getValuesOrThrow(
-        Iterable<SkyKey> depKeys, Class<E> exceptionClass);
-    <E1 extends Exception, E2 extends Exception> Map<SkyKey, ValueOrException2<E1, E2>>
-    getValuesOrThrow(Iterable<SkyKey> depKeys, Class<E1> exceptionClass1,
-        Class<E2> exceptionClass2);
+        Iterable<SkyKey> depKeys, Class<E> exceptionClass) throws InterruptedException;
+
+    <E1 extends Exception, E2 extends Exception>
+        Map<SkyKey, ValueOrException2<E1, E2>> getValuesOrThrow(
+            Iterable<SkyKey> depKeys, Class<E1> exceptionClass1, Class<E2> exceptionClass2)
+            throws InterruptedException;
+
     <E1 extends Exception, E2 extends Exception, E3 extends Exception>
-    Map<SkyKey, ValueOrException3<E1, E2, E3>> getValuesOrThrow(Iterable<SkyKey> depKeys,
-        Class<E1> exceptionClass1, Class<E2> exceptionClass2, Class<E3> exceptionClass3);
+        Map<SkyKey, ValueOrException3<E1, E2, E3>> getValuesOrThrow(
+            Iterable<SkyKey> depKeys,
+            Class<E1> exceptionClass1,
+            Class<E2> exceptionClass2,
+            Class<E3> exceptionClass3)
+            throws InterruptedException;
+
     <E1 extends Exception, E2 extends Exception, E3 extends Exception, E4 extends Exception>
-    Map<SkyKey, ValueOrException4<E1, E2, E3, E4>> getValuesOrThrow(Iterable<SkyKey> depKeys,
-        Class<E1> exceptionClass1, Class<E2> exceptionClass2, Class<E3> exceptionClass3,
-        Class<E4> exceptionClass4);
-    <E1 extends Exception, E2 extends Exception, E3 extends Exception, E4 extends Exception,
-     E5 extends Exception>
-    Map<SkyKey, ValueOrException5<E1, E2, E3, E4, E5>> getValuesOrThrow(Iterable<SkyKey> depKeys,
-        Class<E1> exceptionClass1, Class<E2> exceptionClass2, Class<E3> exceptionClass3,
-        Class<E4> exceptionClass4, Class<E5> exceptionClass5);
+        Map<SkyKey, ValueOrException4<E1, E2, E3, E4>> getValuesOrThrow(
+            Iterable<SkyKey> depKeys,
+            Class<E1> exceptionClass1,
+            Class<E2> exceptionClass2,
+            Class<E3> exceptionClass3,
+            Class<E4> exceptionClass4)
+            throws InterruptedException;
+
+    <
+            E1 extends Exception,
+            E2 extends Exception,
+            E3 extends Exception,
+            E4 extends Exception,
+            E5 extends Exception>
+        Map<SkyKey, ValueOrException5<E1, E2, E3, E4, E5>> getValuesOrThrow(
+            Iterable<SkyKey> depKeys,
+            Class<E1> exceptionClass1,
+            Class<E2> exceptionClass2,
+            Class<E3> exceptionClass3,
+            Class<E4> exceptionClass4,
+            Class<E5> exceptionClass5)
+            throws InterruptedException;
 
     /**
      * Returns whether there was a previous getValue[s][OrThrow] that indicated a missing
diff --git a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
index f81355c..1ef077c 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
@@ -15,7 +15,6 @@
 
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.util.Preconditions;
-
 import javax.annotation.Nullable;
 
 /**
@@ -47,23 +46,23 @@
 
   /**
    * Marks this node dirty, or changed if {@code isChanged} is true. The node is put in the
-   * just-created state. It will be re-evaluated if necessary during the evaluation phase,
-   * but if it has not changed, it will not force a re-evaluation of its parents.
+   * just-created state. It will be re-evaluated if necessary during the evaluation phase, but if it
+   * has not changed, it will not force a re-evaluation of its parents.
    *
-   * <p>{@code markDirty(b)} must not be called on an undone node if {@code isChanged() == b}.
-   * It is the caller's responsibility to ensure that this does not happen.  Calling
-   * {@code markDirty(false)} when {@code isChanged() == true} has no effect. The idea here is that
-   * the caller will only ever want to call {@code markDirty()} a second time if a transition from a
+   * <p>{@code markDirty(b)} must not be called on an undone node if {@code isChanged() == b}. It is
+   * the caller's responsibility to ensure that this does not happen. Calling {@code
+   * markDirty(false)} when {@code isChanged() == true} has no effect. The idea here is that the
+   * caller will only ever want to call {@code markDirty()} a second time if a transition from a
    * dirty-unchanged state to a dirty-changed state is required.
    *
-   * @return A {@link ThinNodeEntry.MarkedDirtyResult} if the node was previously clean, and
-   * {@code null} if it was already dirty. If it was already dirty, the caller should abort its
-   * handling of this node, since another thread is already dealing with it. Note the warning on
-   * {@link ThinNodeEntry.MarkedDirtyResult} regarding the collection it provides.
+   * @return A {@link ThinNodeEntry.MarkedDirtyResult} if the node was previously clean, and {@code
+   *     null} if it was already dirty. If it was already dirty, the caller should abort its
+   *     handling of this node, since another thread is already dealing with it. Note the warning on
+   *     {@link ThinNodeEntry.MarkedDirtyResult} regarding the collection it provides.
    */
   @Nullable
   @ThreadSafe
-  MarkedDirtyResult markDirty(boolean isChanged);
+  MarkedDirtyResult markDirty(boolean isChanged) throws InterruptedException;
 
   /**
    * Returned by {@link #markDirty} if that call changed the node from clean to dirty. Contains an
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 7c7a7e8..9f71f1f 100644
--- a/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
@@ -15,15 +15,17 @@
 
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.events.EventHandler;
-
 import java.util.Collection;
 import java.util.Map;
-
 import javax.annotation.Nullable;
 
 /**
  * Read-only graph that exposes the dependents, dependencies (reverse dependents), and value and
  * exception (if any) of a given node.
+ *
+ * <p>Certain graph implementations can throw {@link InterruptedException} when trying to retrieve
+ * node entries. Such exceptions should not be caught locally -- they should be allowed to propagate
+ * up.
  */
 @ThreadSafe
 public interface WalkableGraph {
@@ -33,21 +35,21 @@
    * given node does not exist, this method should be called before any others, since the others
    * throw a {@link RuntimeException} on failure to access a node.
    */
-  boolean exists(SkyKey key);
+  boolean exists(SkyKey key) throws InterruptedException;
 
   /**
    * Returns the value of the given key, or {@code null} if it has no value due to an error during
    * its computation. A node with this key must exist in the graph.
    */
   @Nullable
-  SkyValue getValue(SkyKey key);
+  SkyValue getValue(SkyKey key) throws InterruptedException;
 
   /**
    * 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.
+   * computed. Or in other words, it filters out non-existent nodes, pending nodes and nodes that
+   * produced an exception.
    */
-  Map<SkyKey, SkyValue> getSuccessfulValues(Iterable<SkyKey> keys);
+  Map<SkyKey, SkyValue> getSuccessfulValues(Iterable<SkyKey> keys) throws InterruptedException;
 
   /**
    * Returns a map giving exceptions associated to the given keys for done keys. Keys not present in
@@ -56,26 +58,27 @@
    * for {@code key} if and only if the node for {@code key} did <i>not</i> evaluate successfully
    * without error.
    */
-  Map<SkyKey, Exception> getMissingAndExceptions(Iterable<SkyKey> keys);
+  Map<SkyKey, Exception> getMissingAndExceptions(Iterable<SkyKey> keys) throws InterruptedException;
 
   /**
    * Returns the exception thrown when computing the node with the given key, if any. If the node
    * was computed successfully, returns null. A node with this key must exist and be done in the
    * graph.
    */
-  @Nullable Exception getException(SkyKey key);
+  @Nullable
+  Exception getException(SkyKey key) throws InterruptedException;
 
   /**
    * Returns a map giving the direct dependencies of the nodes with the given keys. A node for each
    * given key must exist and be done in the graph.
    */
-  Map<SkyKey, Iterable<SkyKey>> getDirectDeps(Iterable<SkyKey> keys);
+  Map<SkyKey, Iterable<SkyKey>> getDirectDeps(Iterable<SkyKey> keys) throws InterruptedException;
 
   /**
    * Returns a map giving the reverse dependencies of the nodes with the given keys. A node for each
    * given key must exist and be done in the graph.
    */
-  Map<SkyKey, Iterable<SkyKey>> getReverseDeps(Iterable<SkyKey> keys);
+  Map<SkyKey, Iterable<SkyKey>> getReverseDeps(Iterable<SkyKey> keys) throws InterruptedException;
 
   /** Provides a WalkableGraph on demand after preparing it. */
   interface WalkableGraphFactory {