diff --git a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
index edddd83..e931a12 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
@@ -18,71 +18,54 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
-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.Collections;
 import java.util.List;
-import java.util.Set;
 
 /**
- * Data the NodeEntry uses to maintain its state before it is done building. It allows the
- * {@link NodeEntry} to keep the current state of the entry across invalidation and successive
- * evaluations. A done node does not contain any of this data. However, if a node is marked dirty,
- * its entry acquires a new {@code BuildingState} object, which persists until it is done again.
+ * Data the NodeEntry uses to maintain its state before it is done building. It allows the {@link
+ * NodeEntry} to keep the current state of the entry across invalidation and successive evaluations.
+ * A done node does not contain any of this data. However, if a node is marked dirty, its entry
+ * acquires a new {@link DirtyBuildingState} object, which persists until it is done again.
  *
- * <p>This class should be considered a private inner class of {@link NodeEntry} -- no other
- * classes should instantiate a {@code BuildingState} object or call any of its methods directly.
- * It is in a separate file solely to keep the {@link NodeEntry} class readable. In particular, the
+ * <p>This class should be considered a private inner class of {@link InMemoryNodeEntry} -- no other
+ * classes should instantiate a {@code BuildingState} object or call any of its methods directly. It
+ * is in a separate file solely to keep the {@link NodeEntry} class readable. In particular, the
  * caller must synchronize access to this class.
  *
- * <p>This class is public only for the benefit of alternative graph implementations outside of the
- * package.
+ * <p>During its life, a node can go through states as follows:
+ *
+ * <ol>
+ * <li>Non-existent
+ * <li>Just created ({@link #isEvaluating} is false)
+ * <li>Evaluating ({@link #isEvaluating} is true)
+ * <li>Done (meaning this buildingState object is null)
+ * <li>Just created (when it is dirtied during evaluation)
+ * <li>Reset (just before it is re-evaluated)
+ * <li>Evaluating
+ * <li>Done
+ * </ol>
+ *
+ * <p>The "just created" state is there to allow the {@link EvaluableGraph#createIfAbsentBatch} and
+ * {@link NodeEntry#addReverseDepAndCheckIfDone} methods to be separate. All callers have to call
+ * both methods in that order if they want to create a node. The second method calls {@link
+ * #startEvaluating}, which transitions the current node to the "evaluating" state and returns true
+ * only the first time it was called. A caller that gets "true" back from that call must start the
+ * evaluation of this node, while any subsequent callers must not.
+ *
+ * <p>An entry is set to "evaluating" as soon as it is scheduled for evaluation. Thus, even a node
+ * that is never actually built (for instance, a dirty node that is verified as clean) is in the
+ * "evaluating" state until it is done.
  */
 @ThreadCompatible
-public class BuildingState {
+class BuildingState {
   /**
-   * During its life, a node can go through states as follows:
-   * <ol>
-   * <li>Non-existent
-   * <li>Just created ({@code evaluating} is false)
-   * <li>Evaluating ({@code evaluating} is true)
-   * <li>Done (meaning this buildingState object is null)
-   * <li>Just created (when it is dirtied during evaluation)
-   * <li>Reset (just before it is re-evaluated)
-   * <li>Evaluating
-   * <li>Done
-   * </ol>
-   *
-   * <p>The "just created" state is there to allow the {@link EvaluableGraph#createIfAbsentBatch}
-   * and {@link NodeEntry#addReverseDepAndCheckIfDone} methods to be separate. All callers have to
-   * call both methods in that order if they want to create a node. The second method calls
-   * {@link #startEvaluating}, which transitions the current node to the "evaluating" state and
-   * returns true only the first time it was called. A caller that gets "true" back from that call
-   * must start the evaluation of this node, while any subsequent callers must not.
-   *
-   * <p>An entry is set to "evaluating" as soon as it is scheduled for evaluation. Thus, even a
-   * node that is never actually built (for instance, a dirty node that is verified as clean) is
-   * in the "evaluating" state until it is done.
-   */
-  boolean evaluating = false;
-
-  /**
-   * The state of a dirty node. A node is marked dirty in the BuildingState constructor, and goes
-   * into either the state {@link DirtyState#CHECK_DEPENDENCIES} or
-   * {@link DirtyState#NEEDS_REBUILDING}, depending on whether the caller specified that the node
-   * was itself changed or not. A non-null {@code dirtyState} indicates that the node
-   * {@link #isDirty} in some way.
-   */
-  private DirtyState dirtyState = null;
-
-  /**
-   * The number of dependencies that are known to be done in a {@link NodeEntry}. There is a
-   * potential check-then-act race here, so we need to make sure that when this is increased, we
-   * always check if the new value is equal to the number of required dependencies, and if so, we
-   * must re-schedule the node for evaluation.
+   * The number of dependencies that are known to be done in a {@link NodeEntry} if it is already
+   * evaluating, and a sentinel (-1) indicating that it has not yet started evaluating otherwise.
+   * There is a potential check-then-act race here during evaluation, so we need to make sure that
+   * when this is increased, we always check if the new value is equal to the number of required
+   * dependencies, and if so, we must re-schedule the node for evaluation.
    *
    * <p>There are two potential pitfalls here: 1) If multiple dependencies signal this node in close
    * succession, this node should be scheduled exactly once. 2) If a thread is still working on this
@@ -98,7 +81,7 @@
    * thread is not working on the node anymore. Note that this requires that there is no code after
    * the loop in {@code ParallelEvaluator.Evaluate#run}.
    */
-  private int signaledDeps = 0;
+  int signaledDeps = -1;
 
   /**
    * The set of reverse dependencies that are registered before the node has finished building. Upon
@@ -137,64 +120,8 @@
         }
       };
 
-  // Below are fields that are used for dirty nodes.
-
-  /**
-   * The dependencies requested (with group markers) last time the node was built (and below, the
-   * value last time the node was built). They will be compared to dependencies requested on this
-   * build to check whether this node has changed in {@link NodeEntry#setValue}. If they are null,
-   * it means that this node is being built for the first time. See {@link
-   * InMemoryNodeEntry#directDeps} for more on dependency group storage.
-   */
-  protected final GroupedList<SkyKey> lastBuildDirectDeps;
-
-  /**
-   * Group of children to be checked next in the process of determining if this entry needs to be
-   * re-evaluated. Used by {@link #getNextDirtyDirectDeps} and {@link #signalDep(boolean)}.
-   */
-  private int dirtyDirectDepIndex = -1;
-
-  BuildingState() {
-    lastBuildDirectDeps = null;
-  }
-
-  protected BuildingState(boolean isChanged, GroupedList<SkyKey> lastBuildDirectDeps) {
-    this.lastBuildDirectDeps = lastBuildDirectDeps;
-    Preconditions.checkState(isChanged || !this.lastBuildDirectDeps.isEmpty(),
-        "%s is being marked dirty, not changed, but has no children that could have dirtied it",
-        this);
-    dirtyState = isChanged ? DirtyState.NEEDS_REBUILDING : DirtyState.CHECK_DEPENDENCIES;
-    // We need to iterate through the deps to see if they have changed, or to remove them if one
-    // has. Initialize the iterating index.
-    dirtyDirectDepIndex = 0;
-  }
-
-  static BuildingState newDirtyState(boolean isChanged,
-      GroupedList<SkyKey> lastBuildDirectDeps, SkyValue lastBuildValue) {
-    return new DirtyBuildingState(isChanged, lastBuildDirectDeps, lastBuildValue);
-  }
-
-  void markChanged() {
-    Preconditions.checkState(isDirty(), this);
-    Preconditions.checkState(!isChanged(), this);
-    Preconditions.checkState(!evaluating, this);
-    dirtyState = DirtyState.NEEDS_REBUILDING;
-  }
-
-  void forceChanged() {
-    Preconditions.checkState(isDirty(), this);
-    Preconditions.checkState(!isChanged(), this);
-    Preconditions.checkState(evaluating, this);
-    Preconditions.checkState(lastBuildDirectDeps.listSize() == dirtyDirectDepIndex, this);
-    dirtyState = DirtyState.REBUILDING;
-  }
-
-  int getSignaledDeps() {
-    return signaledDeps;
-  }
-
   /** Returns whether all known children of this node have signaled that they are done. */
-  boolean isReady(int numDirectDeps) {
+  final boolean isReady(int numDirectDeps) {
     Preconditions.checkState(signaledDeps <= numDirectDeps, "%s %s", numDirectDeps, this);
     return signaledDeps == numDirectDeps;
   }
@@ -206,7 +133,7 @@
    * @see NodeEntry#isDirty()
    */
   boolean isDirty() {
-    return dirtyState != null;
+    return false;
   }
 
   /**
@@ -215,154 +142,60 @@
    * @see NodeEntry#isChanged()
    */
   boolean isChanged() {
-    return dirtyState == DirtyState.NEEDS_REBUILDING || dirtyState == DirtyState.REBUILDING;
+    return false;
   }
 
   /**
    * Helper method to assert that node has finished building, as far as we can tell. We would
-   * actually like to check that the node has been evaluated, but that is not available in
-   * this context.
+   * actually like to check that the node has been evaluated, but that is not available in this
+   * context.
    */
-  private void checkFinishedBuildingWhenAboutToSetValue() {
-    Preconditions.checkState(evaluating, "not started building %s", this);
-    Preconditions.checkState(
-        !isDirty()
-            || dirtyState == DirtyState.VERIFIED_CLEAN
-            || dirtyState == DirtyState.REBUILDING,
-        "not done building %s",
-        this);
+  protected void checkFinishedBuildingWhenAboutToSetValue() {
+    Preconditions.checkState(isEvaluating(), "not started building %s", this);
+    Preconditions.checkState(!isDirty(), "not done building %s", this);
   }
 
   /**
-   * Puts the node in the "evaluating" state if it is not already in it. Returns true if the
-   * node wasn't already evaluating and false otherwise. Should only be called by
-   * {@link NodeEntry#addReverseDepAndCheckIfDone}.
+   * Puts the node in the "evaluating" state if it is not already in it. Returns true if the node
+   * wasn't already evaluating and false otherwise. Should only be called by {@link
+   * NodeEntry#addReverseDepAndCheckIfDone}.
    */
-  boolean startEvaluating() {
-    boolean result = !evaluating;
-    evaluating = true;
+  final boolean startEvaluating() {
+    boolean result = !isEvaluating();
+    if (result) {
+      signaledDeps = 0;
+    }
     return result;
   }
 
+  final boolean isEvaluating() {
+    return signaledDeps > -1;
+  }
+
   /**
    * Increments the number of children known to be finished. Returns true if the number of children
    * finished is equal to the number of known children.
    *
-   * <p>If the node is dirty and checking its deps for changes, this also updates {@link
-   * #dirtyState} as needed -- {@link DirtyState#NEEDS_REBUILDING} if the child has changed, and
-   * {@link DirtyState#VERIFIED_CLEAN} if the child has not changed and this was the last child to
-   * be checked (as determined by {@link #isReady} and comparing {@link #dirtyDirectDepIndex} and
-   * {@link #lastBuildDirectDeps#listSize}.
+   * <p>If the node is dirty and checking its deps for changes, this also updates dirty state as
+   * needed, via {@link #signalDepInternal}.
    *
    * @see NodeEntry#signalDep(Version)
    */
-  boolean signalDep(boolean childChanged, int numDirectDeps) {
+  final boolean signalDep(boolean childChanged, int numDirectDeps) {
+    Preconditions.checkState(isEvaluating(), this);
     signaledDeps++;
-    if (isDirty() && !isChanged()) {
-      // Synchronization isn't needed here because the only caller is NodeEntry, which does it
-      // through the synchronized method signalDep(Version).
-      if (childChanged) {
-        dirtyState = DirtyState.NEEDS_REBUILDING;
-      } else if (dirtyState == DirtyState.CHECK_DEPENDENCIES
-          && isReady(numDirectDeps)
-          && lastBuildDirectDeps.listSize() == dirtyDirectDepIndex) {
-        // No other dep already marked this as NEEDS_REBUILDING, no deps outstanding, and this was
-        // the last block of deps to be checked.
-        dirtyState = DirtyState.VERIFIED_CLEAN;
-      }
-    }
+    signalDepInternal(childChanged, numDirectDeps);
     return isReady(numDirectDeps);
   }
 
-  /**
-   * Returns true if {@code newValue}.equals the value from the last time this node was built.
-   * Should only be used by {@link NodeEntry#setValue}.
-   *
-   * <p>Changes in direct deps do <i>not</i> force this to return false. Only the value is
-   * considered.
-   */
-  boolean unchangedFromLastBuild(SkyValue newValue) {
-    checkFinishedBuildingWhenAboutToSetValue();
-    if (newValue instanceof NotComparableSkyValue) {
-      return false;
-    }
-    return getLastBuildValue().equals(newValue);
-  }
-
-  /**
-   * Returns true if the deps requested during this evaluation ({@code directDeps}) are exactly
-   * those requested the last time this node was built, in the same order.
-   */
-  boolean depsUnchangedFromLastBuild(GroupedList<SkyKey> directDeps) {
-    checkFinishedBuildingWhenAboutToSetValue();
-    return lastBuildDirectDeps.equals(directDeps);
-  }
-
-  boolean noDepsLastBuild() {
-    return lastBuildDirectDeps.isEmpty();
-  }
-
-  protected SkyValue getLastBuildValue() {
-    // Default BuildingState isn't dirty.
-    throw new UnsupportedOperationException(this.toString());
-  }
-
-  /**
-   * Gets the current state of checking this dirty entry to see if it must be re-evaluated. Must be
-   * called each time evaluation of a dirty entry starts to find the proper action to perform next,
-   * as enumerated by {@link DirtyState}.
-   *
-   * @see NodeEntry#getDirtyState()
-   */
-  DirtyState getDirtyState() {
-    // Entry may not be ready if being built just for its errors.
-    Preconditions.checkState(isDirty(), "must be dirty to get dirty state %s", this);
-    Preconditions.checkState(evaluating, "must be evaluating to get dirty state %s", this);
-    return dirtyState;
-  }
-
-  /**
-   * Gets the next children to be re-evaluated to see if this dirty node needs to be re-evaluated.
-   *
-   * See {@link NodeEntry#getNextDirtyDirectDeps}.
-   */
-  Collection<SkyKey> getNextDirtyDirectDeps() {
-    Preconditions.checkState(isDirty(), this);
-    Preconditions.checkState(dirtyState == DirtyState.CHECK_DEPENDENCIES, this);
-    Preconditions.checkState(evaluating, this);
-    Preconditions.checkState(dirtyDirectDepIndex < lastBuildDirectDeps.listSize(), this);
-    return lastBuildDirectDeps.get(dirtyDirectDepIndex++);
-  }
-
-  /**
-   * Returns the remaining direct deps that have not been checked. If {@code preservePosition} is
-   * true, this method is non-mutating. If {@code preservePosition} is false, the caller must
-   * process the returned set, and so subsequent calls to this method will return the empty set.
-   */
-  Set<SkyKey> getAllRemainingDirtyDirectDeps(boolean preservePosition) {
-    Preconditions.checkState(isDirty(), this);
-    ImmutableSet.Builder<SkyKey> result = ImmutableSet.builder();
-
-    for (int ind = dirtyDirectDepIndex; ind < lastBuildDirectDeps.listSize(); ind++) {
-      result.addAll(lastBuildDirectDeps.get(ind));
-    }
-    if (!preservePosition) {
-      dirtyDirectDepIndex = lastBuildDirectDeps.listSize();
-    }
-    return result.build();
-  }
-
-  protected void markRebuilding() {
-    Preconditions.checkState(dirtyState == DirtyState.NEEDS_REBUILDING, this);
-    dirtyState = DirtyState.REBUILDING;
-  }
+  void signalDepInternal(boolean childChanged, int numDirectDeps) {}
 
   /**
    * Returns reverse deps to signal that have been registered this build.
    *
    * @see NodeEntry#getReverseDeps()
    */
-  ImmutableSet<SkyKey> getReverseDepsToSignal() {
+  final ImmutableSet<SkyKey> getReverseDepsToSignal() {
     return REVERSE_DEPS_UTIL.getReverseDeps(this);
   }
 
@@ -371,48 +204,23 @@
    *
    * @see NodeEntry#addReverseDepAndCheckIfDone(SkyKey)
    */
-  void addReverseDepToSignal(SkyKey newReverseDep) {
+  final void addReverseDepToSignal(SkyKey newReverseDep) {
     REVERSE_DEPS_UTIL.addReverseDeps(this, Collections.singleton(newReverseDep));
   }
 
-  /**
-   * @see NodeEntry#removeReverseDep(SkyKey)
-   */
-  void removeReverseDepToSignal(SkyKey reverseDep) {
+  /** @see NodeEntry#removeReverseDep(SkyKey) */
+  final void removeReverseDepToSignal(SkyKey reverseDep) {
     REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
   }
 
   protected ToStringHelper getStringHelper() {
     return MoreObjects.toStringHelper(this)
         .add("hash", System.identityHashCode(this))
-        .add("evaluating", evaluating)
-        .add("dirtyState", dirtyState)
-        .add("signaledDeps", signaledDeps)
-        .add("reverseDepsToSignal", REVERSE_DEPS_UTIL.toString(this))
-        .add("lastBuildDirectDeps", lastBuildDirectDeps)
-        .add("dirtyDirectDepIndex", dirtyDirectDepIndex);
+        .add("signaledDeps/evaluating state", signaledDeps)
+        .add("reverseDepsToSignal", REVERSE_DEPS_UTIL.toString(this));
   }
   @Override
-  public String toString() {
+  public final String toString() {
     return getStringHelper().toString();
   }
-
-  private static class DirtyBuildingState extends BuildingState {
-    private final SkyValue lastBuildValue;
-    private DirtyBuildingState(boolean isChanged, GroupedList<SkyKey> lastBuildDirectDeps,
-        SkyValue lastBuildValue) {
-      super(isChanged, lastBuildDirectDeps);
-      this.lastBuildValue = Preconditions.checkNotNull(lastBuildValue);
-    }
-
-    @Override
-    protected SkyValue getLastBuildValue() {
-      return lastBuildValue;
-    }
-
-    @Override
-    public String toString() {
-      return getStringHelper().add("lastBuildValue", lastBuildValue).toString();
-    }
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
new file mode 100644
index 0000000..e8c5a46
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/DirtyBuildingState.java
@@ -0,0 +1,241 @@
+// 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 com.google.common.base.MoreObjects;
+import com.google.common.collect.ImmutableSet;
+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;
+
+/**
+ * A {@link BuildingState} for a node that has been dirtied, and will be checked to see if it needs
+ * re-evaluation, and either marked clean or re-evaluated. See {@link BuildingState} for more.
+ *
+ * <p>This class is public only for the benefit of alternative graph implementations outside of the
+ * package.
+ */
+public abstract class DirtyBuildingState extends BuildingState {
+  /**
+   * The state of a dirty node. A node is marked dirty in the DirtyBuildingState constructor, and
+   * goes into either the state {@link DirtyState#CHECK_DEPENDENCIES} or {@link
+   * DirtyState#NEEDS_REBUILDING}, depending on whether the caller specified that the node was
+   * itself changed or not. Never null.
+   */
+  private DirtyState dirtyState;
+
+  /**
+   * The dependencies requested (with group markers) last time the node was built (and below, the
+   * value last time the node was built). They will be compared to dependencies requested on this
+   * build to check whether this node has changed in {@link NodeEntry#setValue}. If they are null,
+   * it means that this node is being built for the first time. See {@link
+   * InMemoryNodeEntry#directDeps} for more on dependency group storage.
+   */
+  protected final GroupedList<SkyKey> lastBuildDirectDeps;
+
+  /** The value of the node the last time it was built. */
+  protected abstract SkyValue getLastBuildValue();
+
+  /**
+   * Group of children to be checked next in the process of determining if this entry needs to be
+   * re-evaluated. Used by {@link DirtyBuildingState#getNextDirtyDirectDeps} and {@link #signalDep}.
+   */
+  private int dirtyDirectDepIndex = -1;
+
+  protected DirtyBuildingState(boolean isChanged, GroupedList<SkyKey> lastBuildDirectDeps) {
+    this.lastBuildDirectDeps = lastBuildDirectDeps;
+    Preconditions.checkState(
+        isChanged || !this.lastBuildDirectDeps.isEmpty(),
+        "%s is being marked dirty, not changed, but has no children that could have dirtied it",
+        this);
+    dirtyState = isChanged ? DirtyState.NEEDS_REBUILDING : DirtyState.CHECK_DEPENDENCIES;
+    // We need to iterate through the deps to see if they have changed, or to remove them if one
+    // has. Initialize the iterating index.
+    dirtyDirectDepIndex = 0;
+  }
+
+  static BuildingState create(
+      boolean isChanged, GroupedList<SkyKey> lastBuildDirectDeps, SkyValue lastBuildValue) {
+    return new DirtyBuildingStateWithValue(isChanged, lastBuildDirectDeps, lastBuildValue);
+  }
+
+  final void markChanged() {
+    Preconditions.checkState(isDirty(), this);
+    Preconditions.checkState(!isChanged(), this);
+    Preconditions.checkState(!isEvaluating(), this);
+    dirtyState = DirtyState.NEEDS_REBUILDING;
+  }
+
+  final void forceChanged() {
+    Preconditions.checkState(isDirty(), this);
+    Preconditions.checkState(!isChanged(), this);
+    Preconditions.checkState(isEvaluating(), this);
+    Preconditions.checkState(lastBuildDirectDeps.listSize() == dirtyDirectDepIndex, this);
+    dirtyState = DirtyState.REBUILDING;
+  }
+
+  final int getSignaledDeps() {
+    return signaledDeps;
+  }
+
+  @Override
+  final boolean isDirty() {
+    return true;
+  }
+
+  @Override
+  final boolean isChanged() {
+    return dirtyState == DirtyState.NEEDS_REBUILDING || dirtyState == DirtyState.REBUILDING;
+  }
+
+  @Override
+  protected final void checkFinishedBuildingWhenAboutToSetValue() {
+    Preconditions.checkState(isEvaluating(), "not started building %s", this);
+    Preconditions.checkState(
+        !isDirty()
+            || dirtyState == DirtyState.VERIFIED_CLEAN
+            || dirtyState == DirtyState.REBUILDING,
+        "not done building %s",
+        this);
+  }
+
+  /**
+   * If this node is not yet known to need rebuilding, sets {@link #dirtyState} to {@link
+   * DirtyState#NEEDS_REBUILDING} if the child has changed, and {@link DirtyState#VERIFIED_CLEAN} if
+   * the child has not changed and this was the last child to be checked (as determined by {@link
+   * #isReady} and comparing {@link #dirtyDirectDepIndex} and {@link
+   * DirtyBuildingState#lastBuildDirectDeps#listSize}.
+   */
+  @Override
+  final void signalDepInternal(boolean childChanged, int numDirectDeps) {
+    if (!isChanged()) {
+      // Synchronization isn't needed here because the only caller is NodeEntry, which does it
+      // through the synchronized method signalDep(Version).
+      if (childChanged) {
+        dirtyState = DirtyState.NEEDS_REBUILDING;
+      } else if (dirtyState == DirtyState.CHECK_DEPENDENCIES
+          && isReady(numDirectDeps)
+          && lastBuildDirectDeps.listSize() == dirtyDirectDepIndex) {
+        // No other dep already marked this as NEEDS_REBUILDING, no deps outstanding, and this was
+        // the last block of deps to be checked.
+        dirtyState = DirtyState.VERIFIED_CLEAN;
+      }
+    }
+  }
+
+  /**
+   * Returns true if {@code newValue}.equals the value from the last time this node was built.
+   * Should only be used by {@link NodeEntry#setValue}.
+   *
+   * <p>Changes in direct deps do <i>not</i> force this to return false. Only the value is
+   * considered.
+   */
+  final boolean unchangedFromLastBuild(SkyValue newValue) {
+    checkFinishedBuildingWhenAboutToSetValue();
+    return !(newValue instanceof NotComparableSkyValue) && getLastBuildValue().equals(newValue);
+  }
+
+  /**
+   * Returns true if the deps requested during this evaluation ({@code directDeps}) are exactly
+   * those requested the last time this node was built, in the same order.
+   */
+  final boolean depsUnchangedFromLastBuild(GroupedList<SkyKey> directDeps) {
+    checkFinishedBuildingWhenAboutToSetValue();
+    return lastBuildDirectDeps.equals(directDeps);
+  }
+
+  final boolean noDepsLastBuild() {
+    return lastBuildDirectDeps.isEmpty();
+  }
+
+  /**
+   * Gets the current state of checking this dirty entry to see if it must be re-evaluated. Must be
+   * called each time evaluation of a dirty entry starts to find the proper action to perform next,
+   * as enumerated by {@link DirtyState}.
+   *
+   * @see NodeEntry#getDirtyState()
+   */
+  final DirtyState getDirtyState() {
+    // Entry may not be ready if being built just for its errors.
+    Preconditions.checkState(isEvaluating(), "must be evaluating to get dirty state %s", this);
+    return dirtyState;
+  }
+
+  /**
+   * Gets the next children to be re-evaluated to see if this dirty node needs to be re-evaluated.
+   *
+   * <p>See {@link NodeEntry#getNextDirtyDirectDeps}.
+   */
+  final Collection<SkyKey> getNextDirtyDirectDeps() {
+    Preconditions.checkState(isDirty(), this);
+    Preconditions.checkState(dirtyState == DirtyState.CHECK_DEPENDENCIES, this);
+    Preconditions.checkState(isEvaluating(), this);
+    Preconditions.checkState(dirtyDirectDepIndex < lastBuildDirectDeps.listSize(), this);
+    return lastBuildDirectDeps.get(dirtyDirectDepIndex++);
+  }
+
+  /**
+   * Returns the remaining direct deps that have not been checked. If {@code preservePosition} is
+   * true, this method is non-mutating. If {@code preservePosition} is false, the caller must
+   * process the returned set, and so subsequent calls to this method will return the empty set.
+   */
+  Set<SkyKey> getAllRemainingDirtyDirectDeps(boolean preservePosition) {
+    Preconditions.checkState(isDirty(), this);
+    ImmutableSet.Builder<SkyKey> result = ImmutableSet.builder();
+
+    for (int ind = dirtyDirectDepIndex; ind < lastBuildDirectDeps.listSize(); ind++) {
+      result.addAll(lastBuildDirectDeps.get(ind));
+    }
+    if (!preservePosition) {
+      dirtyDirectDepIndex = lastBuildDirectDeps.listSize();
+    }
+    return result.build();
+  }
+
+  protected void markRebuilding() {
+    Preconditions.checkState(dirtyState == DirtyState.NEEDS_REBUILDING, this);
+    dirtyState = DirtyState.REBUILDING;
+  }
+
+  @Override
+  protected MoreObjects.ToStringHelper getStringHelper() {
+    return super.getStringHelper()
+        .add("dirtyState", dirtyState)
+        .add("lastBuildDirectDeps", lastBuildDirectDeps)
+        .add("dirtyDirectDepIndex", dirtyDirectDepIndex);
+  }
+
+  private static class DirtyBuildingStateWithValue extends DirtyBuildingState {
+    private final SkyValue lastBuildValue;
+
+    private DirtyBuildingStateWithValue(
+        boolean isChanged, GroupedList<SkyKey> lastBuildDirectDeps, SkyValue lastBuildValue) {
+      super(isChanged, lastBuildDirectDeps);
+      this.lastBuildValue = lastBuildValue;
+    }
+
+    @Override
+    protected SkyValue getLastBuildValue() {
+      return lastBuildValue;
+    }
+
+    @Override
+    protected MoreObjects.ToStringHelper getStringHelper() {
+      return super.getStringHelper().add("lastBuildValue", lastBuildValue);
+    }
+  }
+}
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 63eb7fd..9ba0dbe 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -163,9 +163,9 @@
     if (isDone()) {
       return getErrorInfo() == null ? getValue() : null;
     } else if (isChanged() || isDirty()) {
-      return (buildingState.getLastBuildValue() == null)
-              ? null
-          : ValueWithMetadata.justValue(buildingState.getLastBuildValue());
+      return (getDirtyBuildingState().getLastBuildValue() == null)
+          ? null
+          : ValueWithMetadata.justValue(getDirtyBuildingState().getLastBuildValue());
     } else {
       // Value has not finished evaluating. It's probably about to be cleaned from the graph.
       return null;
@@ -194,6 +194,10 @@
     return ValueWithMetadata.getMaybeErrorInfo(value);
   }
 
+  private DirtyBuildingState getDirtyBuildingState() {
+    return (DirtyBuildingState) Preconditions.checkNotNull(buildingState, this);
+  }
+
   /**
    * Puts entry in "done" state, as checked by {@link #isDone}. Subclasses that override one may
    * need to override the other.
@@ -235,10 +239,10 @@
         this.lastEvaluatedVersion.atMost(version), "%s %s %s", this, version, value);
     this.lastEvaluatedVersion = version;
 
-    if (isDirty() && buildingState.unchangedFromLastBuild(value)) {
+    if (isDirty() && getDirtyBuildingState().unchangedFromLastBuild(value)) {
       // If the value is the same as before, just use the old value. Note that we don't use the new
       // value, because preserving == equality is even better than .equals() equality.
-      this.value = buildingState.getLastBuildValue();
+      this.value = getDirtyBuildingState().getLastBuildValue();
     } else {
       // If this is a new value, or it has changed since the last build, set the version to the
       // current graph version.
@@ -345,7 +349,7 @@
     assertKeepEdges();
     if (isDone()) {
       buildingState =
-          BuildingState.newDirtyState(isChanged, GroupedList.<SkyKey>create(directDeps), value);
+          DirtyBuildingState.create(isChanged, GroupedList.<SkyKey>create(directDeps), value);
       value = null;
       directDeps = null;
       return new MarkedDirtyResult(getReverseDepsUtil().getReverseDeps(this));
@@ -360,17 +364,17 @@
     if (isChanged) {
       // If the changed marker lost the race, we just need to mark changed in this method -- all
       // other work was done by the dirty marker.
-      buildingState.markChanged();
+      getDirtyBuildingState().markChanged();
     }
     return null;
   }
 
   @Override
   public synchronized Set<SkyKey> markClean() {
-    this.value = buildingState.getLastBuildValue();
+    this.value = getDirtyBuildingState().getLastBuildValue();
     Preconditions.checkState(isReady(), "Should be ready when clean: %s", this);
     Preconditions.checkState(
-        buildingState.depsUnchangedFromLastBuild(getTemporaryDirectDeps()),
+        getDirtyBuildingState().depsUnchangedFromLastBuild(getTemporaryDirectDeps()),
         "Direct deps must be the same as those found last build for node to be marked clean: %s",
         this);
     Preconditions.checkState(isDirty(), this);
@@ -381,8 +385,8 @@
   @Override
   public synchronized void forceRebuild() {
     Preconditions.checkState(
-        getTemporaryDirectDeps().numElements() == buildingState.getSignaledDeps(), this);
-    buildingState.forceChanged();
+        getTemporaryDirectDeps().numElements() == getDirtyBuildingState().getSignaledDeps(), this);
+    getDirtyBuildingState().forceChanged();
   }
 
   @Override
@@ -390,17 +394,17 @@
     return lastChangedVersion;
   }
 
-  /**  @see BuildingState#getDirtyState() */
+  /** @see DirtyBuildingState#getDirtyState() */
   @Override
   public synchronized NodeEntry.DirtyState getDirtyState() {
-    return buildingState.getDirtyState();
+    return getDirtyBuildingState().getDirtyState();
   }
 
-  /**  @see BuildingState#getNextDirtyDirectDeps() */
+  /** @see DirtyBuildingState#getNextDirtyDirectDeps() */
   @Override
   public synchronized Collection<SkyKey> getNextDirtyDirectDeps() {
     Preconditions.checkState(isReady(), this);
-    return buildingState.getNextDirtyDirectDeps();
+    return getDirtyBuildingState().getNextDirtyDirectDeps();
   }
 
   @Override
@@ -414,7 +418,8 @@
       for (Iterable<SkyKey> group : getTemporaryDirectDeps()) {
         result.addAll(group);
       }
-      result.addAll(buildingState.getAllRemainingDirtyDirectDeps(/*preservePosition=*/ false));
+      result.addAll(
+          getDirtyBuildingState().getAllRemainingDirtyDirectDeps(/*preservePosition=*/ false));
       return result.build();
     }
   }
@@ -422,17 +427,18 @@
   @Override
   public synchronized Set<SkyKey> getAllRemainingDirtyDirectDeps() {
     if (isDirty()) {
-      Preconditions.checkState(buildingState.getDirtyState() == DirtyState.REBUILDING, this);
-      return buildingState.getAllRemainingDirtyDirectDeps(/*preservePosition=*/ true);
+      Preconditions.checkState(
+          getDirtyBuildingState().getDirtyState() == DirtyState.REBUILDING, this);
+      return getDirtyBuildingState().getAllRemainingDirtyDirectDeps(/*preservePosition=*/ true);
     } else {
-      Preconditions.checkState(buildingState.evaluating, this);
+      Preconditions.checkState(buildingState.isEvaluating(), this);
       return ImmutableSet.of();
     }
   }
 
   @Override
   public synchronized void markRebuilding() {
-    buildingState.markRebuilding();
+    getDirtyBuildingState().markRebuilding();
   }
 
   @SuppressWarnings("unchecked")
@@ -448,7 +454,7 @@
 
   @Override
   public synchronized boolean noDepsLastBuild() {
-    return buildingState.noDepsLastBuild();
+    return getDirtyBuildingState().noDepsLastBuild();
   }
 
   /**
diff --git a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
index 080c546..23c1fca 100644
--- a/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/InMemoryNodeEntryTest.java
@@ -189,6 +189,9 @@
     assertTrue(entry.isDirty());
     assertFalse(entry.isChanged());
     assertFalse(entry.isDone());
+    assertThatNodeEntry(entry)
+        .addReverseDepAndCheckIfDone(null)
+        .isEqualTo(DependencyState.NEEDS_SCHEDULING);
     assertTrue(entry.isReady());
     assertThat(entry.getTemporaryDirectDeps()).isEmpty();
     SkyKey parent = key("parent");
@@ -218,6 +221,9 @@
     assertTrue(entry.isDirty());
     assertTrue(entry.isChanged());
     assertFalse(entry.isDone());
+    assertThatNodeEntry(entry)
+        .addReverseDepAndCheckIfDone(null)
+        .isEqualTo(DependencyState.NEEDS_SCHEDULING);
     assertTrue(entry.isReady());
     SkyKey parent = key("parent");
     entry.addReverseDepAndCheckIfDone(parent);
@@ -243,11 +249,13 @@
     assertTrue(entry.isDirty());
     assertFalse(entry.isChanged());
     assertFalse(entry.isDone());
-    assertTrue(entry.isReady());
     entry.markDirty(/*isChanged=*/true);
     assertTrue(entry.isDirty());
     assertTrue(entry.isChanged());
     assertFalse(entry.isDone());
+    assertThatNodeEntry(entry)
+        .addReverseDepAndCheckIfDone(null)
+        .isEqualTo(DependencyState.NEEDS_SCHEDULING);
     assertTrue(entry.isReady());
   }
 
@@ -265,11 +273,13 @@
     assertTrue(entry.isDirty());
     assertTrue(entry.isChanged());
     assertFalse(entry.isDone());
-    assertTrue(entry.isReady());
     entry.markDirty(/*isChanged=*/false);
     assertTrue(entry.isDirty());
     assertTrue(entry.isChanged());
     assertFalse(entry.isDone());
+    assertThatNodeEntry(entry)
+        .addReverseDepAndCheckIfDone(null)
+        .isEqualTo(DependencyState.NEEDS_SCHEDULING);
     assertTrue(entry.isReady());
   }
 
@@ -367,6 +377,9 @@
     assertTrue(entry.isDirty());
     assertFalse(entry.isChanged());
     assertFalse(entry.isDone());
+    assertThatNodeEntry(entry)
+        .addReverseDepAndCheckIfDone(null)
+        .isEqualTo(DependencyState.NEEDS_SCHEDULING);
     assertTrue(entry.isReady());
     SkyKey parent = key("parent");
     entry.addReverseDepAndCheckIfDone(parent);
@@ -435,6 +448,9 @@
     assertTrue(entry.isDirty());
     assertFalse(entry.isChanged());
     assertFalse(entry.isDone());
+    assertThatNodeEntry(entry)
+        .addReverseDepAndCheckIfDone(null)
+        .isEqualTo(DependencyState.NEEDS_SCHEDULING);
     assertTrue(entry.isReady());
     SkyKey parent = key("parent");
     entry.addReverseDepAndCheckIfDone(parent);
@@ -473,6 +489,9 @@
     assertTrue(entry.isDirty());
     assertFalse(entry.isChanged());
     assertFalse(entry.isDone());
+    assertThatNodeEntry(entry)
+        .addReverseDepAndCheckIfDone(null)
+        .isEqualTo(DependencyState.NEEDS_SCHEDULING);
     assertTrue(entry.isReady());
     entry.addReverseDepAndCheckIfDone(null);
     assertEquals(NodeEntry.DirtyState.CHECK_DEPENDENCIES, entry.getDirtyState());
@@ -643,6 +662,9 @@
     IntVersion version = IntVersion.of(0);
     IntegerValue originalValue = new IntegerValue(42);
     SkyKey originalChild = key("child");
+    assertThatNodeEntry(entry)
+        .addReverseDepAndCheckIfDone(null)
+        .isEqualTo(DependencyState.NEEDS_SCHEDULING);
     addTemporaryDirectDep(entry, originalChild);
     entry.signalDep();
     entry.setValue(originalValue, version);
@@ -686,6 +708,9 @@
         ImmutableSet.of(key("2A"), key("2B")),
         ImmutableSet.of(key("3A"), key("3B"), key("3C")),
         ImmutableSet.of(key("4A"), key("4B"), key("4C"), key("4D")));
+    assertThatNodeEntry(entry)
+        .addReverseDepAndCheckIfDone(null)
+        .isEqualTo(DependencyState.NEEDS_SCHEDULING);
     for (Set<SkyKey> depGroup : groupedDirectDeps) {
       entry.addTemporaryDirectDeps(GroupedListHelper.create(depGroup));
       for (int i = 0; i < depGroup.size(); i++) {
diff --git a/src/test/java/com/google/devtools/build/skyframe/NodeEntrySubject.java b/src/test/java/com/google/devtools/build/skyframe/NodeEntrySubject.java
index 50ed287..1b5911f 100644
--- a/src/test/java/com/google/devtools/build/skyframe/NodeEntrySubject.java
+++ b/src/test/java/com/google/devtools/build/skyframe/NodeEntrySubject.java
@@ -16,11 +16,14 @@
 import static com.google.common.truth.Truth.assertThat;
 
 import com.google.common.collect.Iterables;
+import com.google.common.truth.ComparableSubject;
 import com.google.common.truth.DefaultSubject;
 import com.google.common.truth.FailureStrategy;
 import com.google.common.truth.IterableSubject;
 import com.google.common.truth.Subject;
 
+import javax.annotation.Nullable;
+
 /**
  * {@link Subject} for {@link NodeEntry}. Please add to this class if you need more
  * functionality!
@@ -39,6 +42,12 @@
         .named(detail("TemporaryDirectDeps"));
   }
 
+  ComparableSubject<?, NodeEntry.DependencyState> addReverseDepAndCheckIfDone(
+      @Nullable SkyKey reverseDep) {
+    return assertThat(getSubject().addReverseDepAndCheckIfDone(reverseDep))
+        .named(detail("AddReverseDepAndCheckIfDone"));
+  }
+
   private String detail(String descriptor) {
     return descriptor + " for" + getDisplaySubject();
   }