Refactor NodeEntry to be an interface.

--
MOS_MIGRATED_REVID=85946859

6 files changed, 526 insertions, 381 deletions

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 f93f51aeee..c410a4199c 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
@@ -41,24 +41,6 @@ import java.util.Set;
  */
 @ThreadCompatible
 final class BuildingState implements Serializable {
-  enum DirtyState {
-    /**
-     * The node's dependencies need to be checked to see if it needs to be rebuilt. The
-     * dependencies must be obtained through calls to {@link #getNextDirtyDirectDeps} and checked.
-     */
-    CHECK_DEPENDENCIES,
-    /**
-     * All of the node's dependencies are unchanged, and the value itself was not marked changed,
-     * so its current value is still valid -- it need not be rebuilt.
-     */
-    VERIFIED_CLEAN,
-    /**
-     * A rebuilding is required or in progress, because either the node itself changed or one of
-     * its dependencies did.
-     */
-    REBUILDING
-  }
-
   /**
    * During its life, a node can go through states as follows:
    * <ol>
@@ -91,7 +73,7 @@ final class BuildingState implements Serializable {
    * 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;
+  private NodeEntry.DirtyState dirtyState = null;
 
   /**
    * The number of dependencies that are known to be done in a {@link NodeEntry}. There is a
@@ -197,8 +179,9 @@ final class BuildingState implements Serializable {
     this.lastBuildValue = Preconditions.checkNotNull(lastBuildValue);
     Preconditions.checkState(isChanged || !this.lastBuildDirectDeps.isEmpty(),
         "is being marked dirty, not changed, but has no children that could have dirtied it", this);
-    dirtyState = isChanged ? DirtyState.REBUILDING : DirtyState.CHECK_DEPENDENCIES;
-    if (dirtyState == DirtyState.CHECK_DEPENDENCIES) {
+    dirtyState = isChanged ? NodeEntry.DirtyState.REBUILDING
+        : NodeEntry.DirtyState.CHECK_DEPENDENCIES;
+    if (dirtyState == NodeEntry.DirtyState.CHECK_DEPENDENCIES) {
       // We need to iterate through the deps to see if they have changed. Initialize the iterator.
       dirtyDirectDepIterator = lastBuildDirectDeps.iterator();
     }
@@ -213,7 +196,7 @@ final class BuildingState implements Serializable {
     Preconditions.checkState(isDirty(), this);
     Preconditions.checkState(!isChanged(), this);
     Preconditions.checkState(!evaluating, this);
-    dirtyState = DirtyState.REBUILDING;
+    dirtyState = NodeEntry.DirtyState.REBUILDING;
   }
 
   void forceChanged() {
@@ -221,7 +204,7 @@ final class BuildingState implements Serializable {
     Preconditions.checkState(!isChanged(), this);
     Preconditions.checkState(evaluating, this);
     Preconditions.checkState(isReady(), this);
-    dirtyState = DirtyState.REBUILDING;
+    dirtyState = NodeEntry.DirtyState.REBUILDING;
   }
 
   /**
@@ -249,11 +232,11 @@ final class BuildingState implements Serializable {
    * @see NodeEntry#isChanged()
    */
   boolean isChanged() {
-    return dirtyState == DirtyState.REBUILDING;
+    return dirtyState == NodeEntry.DirtyState.REBUILDING;
   }
 
   private boolean rebuilding() {
-    return dirtyState == DirtyState.REBUILDING;
+    return dirtyState == NodeEntry.DirtyState.REBUILDING;
   }
 
   /**
@@ -263,7 +246,7 @@ final class BuildingState implements Serializable {
    */
   private void checkNotProcessing() {
     Preconditions.checkState(evaluating, "not started building %s", this);
-    Preconditions.checkState(!isDirty() || dirtyState == DirtyState.VERIFIED_CLEAN
+    Preconditions.checkState(!isDirty() || dirtyState == NodeEntry.DirtyState.VERIFIED_CLEAN
         || rebuilding(), "not done building %s", this);
     Preconditions.checkState(isReady(), "not done building %s", this);
   }
@@ -297,12 +280,12 @@ final class BuildingState implements Serializable {
       // Synchronization isn't needed here because the only caller is ValueEntry, which does it
       // through the synchronized method signalDep(long).
       if (childChanged) {
-        dirtyState = DirtyState.REBUILDING;
-      } else if (dirtyState == DirtyState.CHECK_DEPENDENCIES && isReady()
+        dirtyState = NodeEntry.DirtyState.REBUILDING;
+      } else if (dirtyState == NodeEntry.DirtyState.CHECK_DEPENDENCIES && isReady()
           && dirtyDirectDepIterator == null) {
         // No other dep already marked this as REBUILDING, no deps outstanding, and this was
         // the last block of deps to be checked.
-        dirtyState = DirtyState.VERIFIED_CLEAN;
+        dirtyState = NodeEntry.DirtyState.VERIFIED_CLEAN;
       }
     }
     return isReady();
@@ -329,11 +312,11 @@ final class BuildingState implements Serializable {
   /**
    * 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}.
+   * as enumerated by {@link NodeEntry.DirtyState}.
    *
    * @see NodeEntry#getDirtyState()
    */
-  DirtyState getDirtyState() {
+  NodeEntry.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);
@@ -351,7 +334,7 @@ final class BuildingState implements Serializable {
    */
   Collection<SkyKey> getNextDirtyDirectDeps() {
     Preconditions.checkState(isDirty(), this);
-    Preconditions.checkState(dirtyState == DirtyState.CHECK_DEPENDENCIES, this);
+    Preconditions.checkState(dirtyState == NodeEntry.DirtyState.CHECK_DEPENDENCIES, this);
     Preconditions.checkState(evaluating, this);
     List<SkyKey> nextDeps = ImmutableList.copyOf(dirtyDirectDepIterator.next());
     if (!dirtyDirectDepIterator.hasNext()) {
diff --git a/src/main/java/com/google/devtools/build/skyframe/EdgelessNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/EdgelessInMemoryNodeEntry.java
index 98fb61e243..c76ecfb9e4 100644
--- a/src/main/java/com/google/devtools/build/skyframe/EdgelessNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/EdgelessInMemoryNodeEntry.java
@@ -24,9 +24,9 @@ package com.google.devtools.build.skyframe;
  * node is done and written to the graph. Any attempt to access the edges once the node is done will
  * fail the build fast.
  */
-class EdgelessNodeEntry extends NodeEntry {
+class EdgelessInMemoryNodeEntry extends InMemoryNodeEntry {
   @Override
-  protected boolean keepEdges() {
+  public boolean keepEdges() {
     return false;
   }
 }
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 44956da25e..28ba49a7ea 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraph.java
@@ -58,7 +58,7 @@ public class InMemoryGraph implements ProcessableGraph {
 
   @Override
   public NodeEntry createIfAbsent(SkyKey key) {
-    NodeEntry newval = keepEdges ? new NodeEntry() : new EdgelessNodeEntry();
+    NodeEntry newval = keepEdges ? new InMemoryNodeEntry() : new EdgelessInMemoryNodeEntry();
     NodeEntry oldval = nodeMap.putIfAbsent(key, newval);
     return oldval == null ? newval : oldval;
   }
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
new file mode 100644
index 0000000000..2872c90601
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -0,0 +1,428 @@
+// Copyright 2014 Google Inc. 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.annotations.VisibleForTesting;
+import com.google.common.base.Objects;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.util.GroupedList;
+import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
+import com.google.devtools.build.lib.util.Pair;
+
+import java.io.Serializable;
+import java.util.Collection;
+import java.util.List;
+import java.util.Set;
+
+import javax.annotation.Nullable;
+
+/**
+ * In-memory implementation of {@link NodeEntry}. All operations on this class are thread-safe.
+ *
+ * <p>Care was taken to provide certain compound operations to avoid certain check-then-act races.
+ * That means this class is somewhat closely tied to the exact Evaluator implementation.
+ *
+ * <p>Consider the example with two threads working on two nodes, where one depends on the other,
+ * say b depends on a. If a completes first, it's done. If it completes second, it needs to signal
+ * b, and potentially re-schedule it. If b completes first, it must exit, because it will be
+ * signaled (and re-scheduled) by a. If it completes second, it must signal (and re-schedule)
+ * itself. However, if the Evaluator supported re-entrancy for a node, then this wouldn't have to
+ * be so strict, because duplicate scheduling would be less problematic.
+ *
+ * <p>The transient state of an {@code InMemoryNodeEntry} is kept in a {@link BuildingState} object.
+ * Many of the methods of {@code InMemoryNodeEntry} are just wrappers around the corresponding
+ * {@link BuildingState} methods.
+ * 
+ * <p>This class is public only for the benefit of alternative graph implementations outside of the
+ * package.
+ */
+public class InMemoryNodeEntry implements NodeEntry, Serializable {
+
+  /** Actual data stored in this entry when it is done. */
+  private SkyValue value = null;
+
+  /**
+   * The last version of the graph at which this node entry was changed. In {@link #setValue} it
+   * may be determined that the data being written to the graph at a given version is the same as
+   * the already-stored data. In that case, the version will remain the same. The version can be
+   * thought of as the latest timestamp at which this entry was changed.
+   */
+  private Version version = MinimalVersion.INSTANCE;
+
+  /**
+   * This object represents a {@link GroupedList}<SkyKey> in a memory-efficient way. It stores the
+   * direct dependencies of this node, in groups if the {@code SkyFunction} requested them that way.
+   */
+  private Object directDeps = null;
+
+  /**
+   * This list stores the reverse dependencies of this node that have been declared so far.
+   *
+   * <p>In case of a single object we store the object unwrapped, without the list, for
+   * memory-efficiency.
+   */
+  @VisibleForTesting
+  protected Object reverseDeps = ImmutableList.of();
+
+  /**
+   * We take advantage of memory alignment to avoid doing a nasty {@code instanceof} for knowing
+   * if {@code reverseDeps} is a single object or a list.
+   */
+  protected boolean reverseDepIsSingleObject = false;
+
+  /**
+   * During the invalidation we keep the reverse deps to be removed in this list instead of directly
+   * removing them from {@code reverseDeps}. That is because removals from reverseDeps are O(N).
+   * Originally reverseDeps was a HashSet, but because of memory consumption we switched to a list.
+   *
+   * <p>This requires that any usage of reverseDeps (contains, add, the list of reverse deps) call
+   * {@code consolidateReverseDepsRemovals} first. While this operation is not free, it can be done
+   * more effectively than trying to remove each dirty reverse dependency individually (O(N) each
+   * time).
+   */
+  private List<SkyKey> reverseDepsToRemove = null;
+
+  private static final ReverseDepsUtil<InMemoryNodeEntry> REVERSE_DEPS_UTIL =
+      new ReverseDepsUtil<InMemoryNodeEntry>() {
+    @Override
+    void setReverseDepsObject(InMemoryNodeEntry container, Object object) {
+      container.reverseDeps = object;
+    }
+
+    @Override
+    void setSingleReverseDep(InMemoryNodeEntry container, boolean singleObject) {
+      container.reverseDepIsSingleObject = singleObject;
+    }
+
+    @Override
+    void setReverseDepsToRemove(InMemoryNodeEntry container, List<SkyKey> object) {
+      container.reverseDepsToRemove = object;
+    }
+
+    @Override
+    Object getReverseDepsObject(InMemoryNodeEntry container) {
+      return container.reverseDeps;
+    }
+
+    @Override
+    boolean isSingleReverseDep(InMemoryNodeEntry container) {
+      return container.reverseDepIsSingleObject;
+    }
+
+    @Override
+    List<SkyKey> getReverseDepsToRemove(InMemoryNodeEntry container) {
+      return container.reverseDepsToRemove;
+    }
+  };
+
+  /**
+   * The transient state of this entry, after it has been created but before it is done. It allows
+   * us to keep the current state of the entry across invalidation and successive evaluations.
+   */
+  @VisibleForTesting
+  protected BuildingState buildingState = new BuildingState();
+
+  /**
+   * Construct a InMemoryNodeEntry. Use ONLY in Skyframe evaluation and graph implementations.
+   */
+  public InMemoryNodeEntry() {
+  }
+
+  @Override
+  public boolean keepEdges() {
+    return true;
+  }
+
+  @Override
+  public synchronized boolean isDone() {
+    return buildingState == null;
+  }
+
+  @Override
+  public synchronized SkyValue getValue() {
+    Preconditions.checkState(isDone(), "no value until done. ValueEntry: %s", this);
+    return ValueWithMetadata.justValue(value);
+  }
+
+  @Override
+  public synchronized ValueWithMetadata getValueWithMetadata() {
+    Preconditions.checkState(isDone(), "no value until done: %s", this);
+    return ValueWithMetadata.wrapWithMetadata(value);
+  }
+
+  @Override
+  public synchronized SkyValue toValue() {
+    if (isDone()) {
+      return getErrorInfo() == null ? getValue() : null;
+    } else if (isChanged() || isDirty()) {
+      return (buildingState.getLastBuildValue() == null)
+              ? null
+          : ValueWithMetadata.justValue(buildingState.getLastBuildValue());
+    }
+    throw new AssertionError("Value in bad state: " + this);
+  }
+
+  @Override
+  public synchronized Iterable<SkyKey> getDirectDeps() {
+    assertKeepEdges();
+    Preconditions.checkState(isDone(), "no deps until done. ValueEntry: %s", this);
+    return GroupedList.<SkyKey>create(directDeps).toSet();
+  }
+
+  @Override
+  @Nullable
+  public synchronized ErrorInfo getErrorInfo() {
+    Preconditions.checkState(isDone(), "no errors until done. ValueEntry: %s", this);
+    return ValueWithMetadata.getMaybeErrorInfo(value);
+  }
+
+  private synchronized Set<SkyKey> setStateFinishedAndReturnReverseDeps() {
+    // Get reverse deps that need to be signaled.
+    ImmutableSet<SkyKey> reverseDepsToSignal = buildingState.getReverseDepsToSignal();
+    REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this);
+    REVERSE_DEPS_UTIL.addReverseDeps(this, reverseDepsToSignal);
+    this.directDeps = buildingState.getFinishedDirectDeps().compress();
+
+    // Set state of entry to done.
+    buildingState = null;
+
+    if (!keepEdges()) {
+      this.directDeps = null;
+      this.reverseDeps = null;
+    }
+    return reverseDepsToSignal;
+  }
+
+  @Override
+  public synchronized Set<SkyKey> getInProgressReverseDeps() {
+    Preconditions.checkState(!isDone(), this);
+    return buildingState.getReverseDepsToSignal();
+  }
+
+  @Override
+  public synchronized Set<SkyKey> setValue(SkyValue value, Version version) {
+    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(this.version.atMost(version),
+        "%s %s %s", this, version, value);
+
+    if (isDirty() && buildingState.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();
+    } else {
+      // If this is a new value, or it has changed since the last build, set the version to the
+      // current graph version.
+      this.version = version;
+      this.value = value;
+    }
+
+    return setStateFinishedAndReturnReverseDeps();
+  }
+
+  @Override
+  public synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
+    if (reverseDep != null) {
+      if (keepEdges()) {
+        REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this);
+        REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(this, reverseDep);
+      }
+      if (isDone()) {
+        if (keepEdges()) {
+          REVERSE_DEPS_UTIL.addReverseDeps(this, ImmutableList.of(reverseDep));
+        }
+      } else {
+        // Parent should never register itself twice in the same build.
+        buildingState.addReverseDepToSignal(reverseDep);
+      }
+    }
+    if (isDone()) {
+      return DependencyState.DONE;
+    }
+    return buildingState.startEvaluating() ? DependencyState.NEEDS_SCHEDULING
+                                           : DependencyState.ADDED_DEP;
+  }
+
+  @Override
+  public synchronized void removeReverseDep(SkyKey reverseDep) {
+    if (!keepEdges()) {
+      return;
+    }
+    REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
+    if (!isDone()) {
+      // This is currently unnecessary -- the only time we remove a reverse dep that was added this
+      // build is during the clean following a build failure. In that case, this node that is not
+      // done will be deleted soon, so clearing the reverse dep is not required.
+      buildingState.removeReverseDepToSignal(reverseDep);
+    }
+  }
+
+  @Override
+  public synchronized Iterable<SkyKey> getReverseDeps() {
+    assertKeepEdges();
+    Preconditions.checkState(isDone() || buildingState.getReverseDepsToSignal().isEmpty(),
+        "Reverse deps should only be queried before the build has begun "
+            + "or after the node is done %s", this);
+    return REVERSE_DEPS_UTIL.getReverseDeps(this);
+  }
+
+  @Override
+  public synchronized boolean signalDep() {
+    return signalDep(/*childVersion=*/new IntVersion(Long.MAX_VALUE));
+  }
+
+  @Override
+  public synchronized boolean signalDep(Version childVersion) {
+    Preconditions.checkState(!isDone(), "Value must not be done in signalDep %s", this);
+    return buildingState.signalDep(/*childChanged=*/!childVersion.atMost(getVersion()));
+  }
+
+  @Override
+  public synchronized boolean isDirty() {
+    return !isDone() && buildingState.isDirty();
+  }
+
+  @Override
+  public synchronized boolean isChanged() {
+    return !isDone() && buildingState.isChanged();
+  }
+
+  /** Checks that a caller is not trying to access not-stored graph edges. */
+  private void assertKeepEdges() {
+    Preconditions.checkState(keepEdges(), "Graph edges not stored. %s", this);
+  }
+
+  @Override
+  @Nullable
+  public synchronized Pair<? extends Iterable<SkyKey>, ? extends SkyValue> markDirty(
+      boolean isChanged) {
+    assertKeepEdges();
+    if (isDone()) {
+      GroupedList<SkyKey> lastDirectDeps = GroupedList.create(directDeps);
+      buildingState = BuildingState.newDirtyState(isChanged, lastDirectDeps, value);
+      Pair<? extends Iterable<SkyKey>, ? extends SkyValue> result =
+          Pair.of(lastDirectDeps.toSet(), value);
+      value = null;
+      directDeps = null;
+      return result;
+    }
+    // The caller may be simultaneously trying to mark this node dirty and changed, and the dirty
+    // thread may have lost the race, but it is the caller's responsibility not to try to mark
+    // this node changed twice. The end result of racing markers must be a changed node, since one
+    // of the markers is trying to mark the node changed.
+    Preconditions.checkState(isChanged != isChanged(),
+        "Cannot mark node dirty twice or changed twice: %s", this);
+    Preconditions.checkState(value == null, "Value should have been reset already %s", this);
+    Preconditions.checkState(directDeps == null, "direct deps not already reset %s", this);
+    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();
+    }
+    return null;
+  }
+
+  @Override
+  public synchronized Set<SkyKey> markClean() {
+    this.value = buildingState.getLastBuildValue();
+    // This checks both the value and the direct deps, but since we're passing in the same value,
+    // the value check should be trivial.
+    Preconditions.checkState(buildingState.unchangedFromLastBuild(this.value),
+        "Direct deps must be the same as those found last build for node to be marked clean: %s",
+        this);
+    Preconditions.checkState(isDirty(), this);
+    Preconditions.checkState(!buildingState.isChanged(), "shouldn't be changed: %s", this);
+    return setStateFinishedAndReturnReverseDeps();
+  }
+
+  @Override
+  public synchronized void forceRebuild() {
+    buildingState.forceChanged();
+  }
+
+  @Override
+  public synchronized Version getVersion() {
+    return version;
+  }
+
+  /**  @see BuildingState#getDirtyState() */
+  @Override
+  public synchronized NodeEntry.DirtyState getDirtyState() {
+    return buildingState.getDirtyState();
+  }
+
+  /**  @see BuildingState#getNextDirtyDirectDeps() */
+  @Override
+  public synchronized Collection<SkyKey> getNextDirtyDirectDeps() {
+    return buildingState.getNextDirtyDirectDeps();
+  }
+
+  @Override
+  public synchronized Set<SkyKey> getTemporaryDirectDeps() {
+    Preconditions.checkState(!isDone(), "temporary shouldn't be done: %s", this);
+    return buildingState.getDirectDepsForBuild();
+  }
+
+  @Override
+  public synchronized boolean noDepsLastBuild() {
+    return buildingState.noDepsLastBuild();
+  }
+
+  @Override
+  public synchronized void removeUnfinishedDeps(Set<SkyKey> unfinishedDeps) {
+    buildingState.removeDirectDeps(unfinishedDeps);
+  }
+
+  @Override
+  public synchronized void addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
+    Preconditions.checkState(!isDone(), "add temp shouldn't be done: %s %s", helper, this);
+    buildingState.addDirectDeps(helper);
+  }
+
+  @Override
+  public synchronized boolean isReady() {
+    Preconditions.checkState(!isDone(), "can't be ready if done: %s", this);
+    return buildingState.isReady();
+  }
+
+  @Override
+  @SuppressWarnings("deprecation")
+  public String toString() {
+    return Objects.toStringHelper(this)  // MoreObjects is not in Guava
+        .add("value", value)
+        .add("version", version)
+        .add("directDeps", directDeps == null ? null : GroupedList.create(directDeps))
+        .add("reverseDeps", REVERSE_DEPS_UTIL.toString(this))
+        .add("buildingState", buildingState).toString();
+  }
+
+  /**
+   * Do not use except in custom evaluator implementations! Added only temporarily.
+   *
+   * <p>Clones a InMemoryMutableNodeEntry iff it is a done node. Otherwise it fails.
+   */
+  public synchronized InMemoryNodeEntry cloneNodeEntry() {
+    // As this is temporary, for now lets limit to done nodes
+    Preconditions.checkState(isDone(), "Only done nodes can be copied");
+    InMemoryNodeEntry nodeEntry = new InMemoryNodeEntry();
+    nodeEntry.value = value;
+    nodeEntry.version = this.version;
+    REVERSE_DEPS_UTIL.addReverseDeps(nodeEntry, REVERSE_DEPS_UTIL.getReverseDeps(this));
+    nodeEntry.directDeps = directDeps;
+    nodeEntry.buildingState = null;
+    return nodeEntry;
+  }
+}
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 91d5664251..ac108441cd 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -13,43 +13,22 @@
 // limitations under the License.
 package com.google.devtools.build.skyframe;
 
-import com.google.common.annotations.VisibleForTesting;
-import com.google.common.base.Objects;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
-import com.google.devtools.build.lib.util.GroupedList;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
 import com.google.devtools.build.lib.util.Pair;
 
-import java.io.Serializable;
 import java.util.Collection;
-import java.util.List;
 import java.util.Set;
 
 import javax.annotation.Nullable;
 
 /**
- * A node in the graph. All operations on this class are thread-safe. Care was taken to provide
- * certain compound operations to avoid certain check-then-act races. That means this class is
- * somewhat closely tied to the exact Evaluator implementation.
+ * A node in the graph. All operations on this class are thread-safe.
  *
- * <p>Consider the example with two threads working on two nodes, where one depends on the other,
- * say b depends on a. If a completes first, it's done. If it completes second, it needs to signal
- * b, and potentially re-schedule it. If b completes first, it must exit, because it will be
- * signaled (and re-scheduled) by a. If it completes second, it must signal (and re-schedule)
- * itself. However, if the Evaluator supported re-entrancy for a node, then this wouldn't have to
- * be so strict, because duplicate scheduling would be less problematic.
- *
- * <p>The transient state of a {@code NodeEntry} is kept in a {@link BuildingState} object. Many of
- * the methods of {@code NodeEntry} are just wrappers around the corresponding
- * {@link BuildingState} methods.
- *
- * <p>This class is non-final only for testing purposes.
- * <p>This class is public only for the benefit of alternative graph implementations outside of the
- * package.
+ * <p>This interface is public only for the benefit of alternative graph implementations outside of
+ * the package.
  */
-public class NodeEntry implements Serializable {
+public interface NodeEntry {
   /**
    * Return code for {@link #addReverseDepAndCheckIfDone(SkyKey)}.
    */
@@ -70,137 +49,54 @@ public class NodeEntry implements Serializable {
     ADDED_DEP;
   }
 
-  /** Actual data stored in this entry when it is done. */
-  private SkyValue value = null;
-
-  /**
-   * The last version of the graph at which this node entry was changed. In {@link #setValue} it
-   * may be determined that the data being written to the graph at a given version is the same as
-   * the already-stored data. In that case, the version will remain the same. The version can be
-   * thought of as the latest timestamp at which this entry was changed.
-   */
-  private Version version = MinimalVersion.INSTANCE;
-
-  /**
-   * This object represents a {@link GroupedList}<SkyKey> in a memory-efficient way. It stores the
-   * direct dependencies of this node, in groups if the {@code SkyFunction} requested them that way.
-   */
-  private Object directDeps = null;
-
-  /**
-   * This list stores the reverse dependencies of this node that have been declared so far.
-   *
-   * <p>In case of a single object we store the object unwrapped, without the list, for
-   * memory-efficiency.
-   */
-  @VisibleForTesting
-  protected Object reverseDeps = ImmutableList.of();
-
-  /**
-   * We take advantage of memory alignment to avoid doing a nasty {@code instanceof} for knowing
-   * if {@code reverseDeps} is a single object or a list.
-   */
-  protected boolean reverseDepIsSingleObject = false;
-
-  /**
-   * During the invalidation we keep the reverse deps to be removed in this list instead of directly
-   * removing them from {@code reverseDeps}. That is because removals from reverseDeps are O(N).
-   * Originally reverseDeps was a HashSet, but because of memory consumption we switched to a list.
-   *
-   * <p>This requires that any usage of reverseDeps (contains, add, the list of reverse deps) call
-   * {@code consolidateReverseDepsRemovals} first. While this operation is not free, it can be done
-   * more effectively than trying to remove each dirty reverse dependency individually (O(N) each
-   * time).
-   */
-  private List<SkyKey> reverseDepsToRemove = null;
-
-  private static final ReverseDepsUtil<NodeEntry> REVERSE_DEPS_UTIL =
-      new ReverseDepsUtil<NodeEntry>() {
-    @Override
-    void setReverseDepsObject(NodeEntry container, Object object) {
-      container.reverseDeps = object;
-    }
-
-    @Override
-    void setSingleReverseDep(NodeEntry container, boolean singleObject) {
-      container.reverseDepIsSingleObject = singleObject;
-    }
-
-    @Override
-    void setReverseDepsToRemove(NodeEntry container, List<SkyKey> object) {
-      container.reverseDepsToRemove = object;
-    }
-
-    @Override
-    Object getReverseDepsObject(NodeEntry container) {
-      return container.reverseDeps;
-    }
-
-    @Override
-    boolean isSingleReverseDep(NodeEntry container) {
-      return container.reverseDepIsSingleObject;
-    }
-
-    @Override
-    List<SkyKey> getReverseDepsToRemove(NodeEntry container) {
-      return container.reverseDepsToRemove;
-    }
-  };
-
   /**
-   * The transient state of this entry, after it has been created but before it is done. It allows
-   * us to keep the current state of the entry across invalidation and successive evaluations.
+   * Return code for {@link #getDirtyState}.
    */
-  @VisibleForTesting
-  protected BuildingState buildingState = new BuildingState();
-
-  /**
-   * Construct a NodeEntry. Use ONLY in Skyframe evaluation and graph implementations.
-   */
-  public NodeEntry() {
+  enum DirtyState {
+    /**
+     * The node's dependencies need to be checked to see if it needs to be rebuilt. The
+     * dependencies must be obtained through calls to {@link #getNextDirtyDirectDeps} and checked.
+     */
+    CHECK_DEPENDENCIES,
+    /**
+     * All of the node's dependencies are unchanged, and the value itself was not marked changed,
+     * so its current value is still valid -- it need not be rebuilt.
+     */
+    VERIFIED_CLEAN,
+    /**
+     * A rebuilding is required or in progress, because either the node itself changed or one of
+     * its dependencies did.
+     */
+    REBUILDING
   }
 
-  protected boolean keepEdges() {
-    return true;
-  }
+  boolean keepEdges();
 
   /** Returns whether the entry has been built and is finished evaluating. */
-  synchronized boolean isDone() {
-    return buildingState == null;
-  }
+  @ThreadSafe
+  boolean isDone();
 
   /**
    * Returns the value stored in this entry. This method may only be called after the evaluation of
    * this node is complete, i.e., after {@link #setValue} has been called.
    */
-  synchronized SkyValue getValue() {
-    Preconditions.checkState(isDone(), "no value until done. ValueEntry: %s", this);
-    return ValueWithMetadata.justValue(value);
-  }
+  @ThreadSafe
+  SkyValue getValue();
+   
 
   /**
    * Returns the {@link SkyValue} for this entry and the metadata associated with it (Like events
    * and errors). This method may only be called after the evaluation of this node is complete,
    * i.e., after {@link #setValue} has been called.
    */
-  synchronized ValueWithMetadata getValueWithMetadata() {
-    Preconditions.checkState(isDone(), "no value until done: %s", this);
-    return ValueWithMetadata.wrapWithMetadata(value);
-  }
+  @ThreadSafe
+  ValueWithMetadata getValueWithMetadata();
 
   /**
    * Returns the value, even if dirty or changed. Returns null otherwise.
    */
-  public synchronized SkyValue toValue() {
-    if (isDone()) {
-      return getErrorInfo() == null ? getValue() : null;
-    } else if (isChanged() || isDirty()) {
-      return (buildingState.getLastBuildValue() == null)
-              ? null
-          : ValueWithMetadata.justValue(buildingState.getLastBuildValue());
-    }
-    throw new AssertionError("Value in bad state: " + this);
-  }
+  @ThreadSafe
+  SkyValue toValue();
 
   /**
    * Returns an immutable iterable of the direct deps of this node. This method may only be called
@@ -211,48 +107,24 @@ public class NodeEntry implements Serializable {
    * which case the overhead is not so bad). It should not be called repeatedly for the same node,
    * since each call takes time proportional to the number of direct deps of the node.
    */
-  synchronized Iterable<SkyKey> getDirectDeps() {
-    assertKeepEdges();
-    Preconditions.checkState(isDone(), "no deps until done. ValueEntry: %s", this);
-    return GroupedList.<SkyKey>create(directDeps).toSet();
-  }
+  @ThreadSafe
+  Iterable<SkyKey> getDirectDeps();
 
   /**
    * 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
-  synchronized ErrorInfo getErrorInfo() {
-    Preconditions.checkState(isDone(), "no errors until done. ValueEntry: %s", this);
-    return ValueWithMetadata.getMaybeErrorInfo(value);
-  }
-
-  private synchronized Set<SkyKey> setStateFinishedAndReturnReverseDeps() {
-    // Get reverse deps that need to be signaled.
-    ImmutableSet<SkyKey> reverseDepsToSignal = buildingState.getReverseDepsToSignal();
-    REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this);
-    REVERSE_DEPS_UTIL.addReverseDeps(this, reverseDepsToSignal);
-    this.directDeps = buildingState.getFinishedDirectDeps().compress();
-
-    // Set state of entry to done.
-    buildingState = null;
-
-    if (!keepEdges()) {
-      this.directDeps = null;
-      this.reverseDeps = null;
-    }
-    return reverseDepsToSignal;
-  }
+  @ThreadSafe
+  ErrorInfo getErrorInfo();
 
   /**
    * Returns the set of reverse deps that have been declared so far this build. Only for use in
    * debugging and when bubbling errors up in the --nokeep_going case, where we need to know what
    * parents this entry has.
    */
-  synchronized Set<SkyKey> getInProgressReverseDeps() {
-    Preconditions.checkState(!isDone(), this);
-    return buildingState.getReverseDepsToSignal();
-  }
+  @ThreadSafe
+  Set<SkyKey> getInProgressReverseDeps();
 
   /**
    * Transitions the node from the EVALUATING to the DONE state and simultaneously sets it to the
@@ -270,25 +142,8 @@ public class NodeEntry implements Serializable {
    * current version. Callers can query that version to see if the node considers its value to have
    * changed.
    */
-  public synchronized Set<SkyKey> setValue(SkyValue value, Version version) {
-    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(this.version.atMost(version),
-        "%s %s %s", this, version, value);
-
-    if (isDirty() && buildingState.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();
-    } else {
-      // If this is a new value, or it has changed since the last build, set the version to the
-      // current graph version.
-      this.version = version;
-      this.value = value;
-    }
-
-    return setStateFinishedAndReturnReverseDeps();
-  }
+  @ThreadSafe
+  Set<SkyKey> setValue(SkyValue value, Version version);
 
   /**
    * Queries if the node is done and adds the given key as a reverse dependency. The return code
@@ -308,55 +163,21 @@ public class NodeEntry implements Serializable {
    * <p>If the parameter is {@code null}, then no reverse dependency is added, but we still check
    * if the node needs to be scheduled.
    */
-  synchronized DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep) {
-    if (reverseDep != null) {
-      if (keepEdges()) {
-        REVERSE_DEPS_UTIL.consolidateReverseDepsRemovals(this);
-        REVERSE_DEPS_UTIL.maybeCheckReverseDepNotPresent(this, reverseDep);
-      }
-      if (isDone()) {
-        if (keepEdges()) {
-          REVERSE_DEPS_UTIL.addReverseDeps(this, ImmutableList.of(reverseDep));
-        }
-      } else {
-        // Parent should never register itself twice in the same build.
-        buildingState.addReverseDepToSignal(reverseDep);
-      }
-    }
-    if (isDone()) {
-      return DependencyState.DONE;
-    }
-    return buildingState.startEvaluating() ? DependencyState.NEEDS_SCHEDULING
-                                           : DependencyState.ADDED_DEP;
-  }
+  @ThreadSafe
+  DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep);
 
   /**
    * Removes a reverse dependency.
    */
-  synchronized void removeReverseDep(SkyKey reverseDep) {
-    if (!keepEdges()) {
-      return;
-    }
-    REVERSE_DEPS_UTIL.removeReverseDep(this, reverseDep);
-    if (!isDone()) {
-      // This is currently unnecessary -- the only time we remove a reverse dep that was added this
-      // build is during the clean following a build failure. In that case, this node that is not
-      // done will be deleted soon, so clearing the reverse dep is not required.
-      buildingState.removeReverseDepToSignal(reverseDep);
-    }
-  }
+  @ThreadSafe
+  void removeReverseDep(SkyKey reverseDep);
 
   /**
    * Returns a copy of the set of reverse dependencies. Note that this introduces a potential
    * check-then-act race; {@link #removeReverseDep} may fail for a key that is returned here.
    */
-  synchronized Iterable<SkyKey> getReverseDeps() {
-    assertKeepEdges();
-    Preconditions.checkState(isDone() || buildingState.getReverseDepsToSignal().isEmpty(),
-        "Reverse deps should only be queried before the build has begun "
-            + "or after the node is done %s", this);
-    return REVERSE_DEPS_UTIL.getReverseDeps(this);
-  }
+  @ThreadSafe
+  Iterable<SkyKey> getReverseDeps();
 
   /**
    * Tell this node that one of its dependencies is now done. Callers must check the return value,
@@ -365,9 +186,8 @@ public class NodeEntry implements Serializable {
    * {@link Long#MAX_VALUE}, informing this entry that a child of it has version
    * {@link Long#MAX_VALUE} will force it to re-evaluate.
    */
-  synchronized boolean signalDep() {
-    return signalDep(/*childVersion=*/new IntVersion(Long.MAX_VALUE));
-  }
+  @ThreadSafe
+  boolean signalDep();
 
   /**
    * Tell this entry that one of its dependencies is now done. Callers must check the return value,
@@ -377,33 +197,24 @@ public class NodeEntry implements Serializable {
    * {@link #getVersion()}, then this entry records that one of its children has changed since it
    * was last evaluated (namely, it was last evaluated at version {@link #getVersion()} and the
    * child was last evaluated at {@code childVersion}. Thus, the next call to
-   * {@link #getDirtyState()} will return {@link BuildingState.DirtyState#REBUILDING}.
+   * {@link #getDirtyState()} will return {@link DirtyState#REBUILDING}.
    */
-  synchronized boolean signalDep(Version childVersion) {
-    Preconditions.checkState(!isDone(), "Value must not be done in signalDep %s", this);
-    return buildingState.signalDep(/*childChanged=*/!childVersion.atMost(getVersion()));
-  }
+  @ThreadSafe
+  boolean signalDep(Version childVersion);
 
   /**
    * Returns true if the entry is marked dirty, meaning that at least one of its transitive
    * dependencies is marked changed.
    */
-  public synchronized boolean isDirty() {
-    return !isDone() && buildingState.isDirty();
-  }
+  @ThreadSafe
+  boolean isDirty();
 
   /**
    * Returns true if the entry is marked changed, meaning that it must be re-evaluated even if its
    * dependencies' values have not changed.
    */
-  synchronized boolean isChanged() {
-    return !isDone() && buildingState.isChanged();
-  }
-
-  /** Checks that a caller is not trying to access not-stored graph edges. */
-  private void assertKeepEdges() {
-    Preconditions.checkState(keepEdges(), "Graph edges not stored. %s", this);
-  }
+  @ThreadSafe
+  boolean isChanged();
 
   /**
    * Marks this node dirty, or changed if {@code isChanged} is true. The node  is put in the
@@ -415,49 +226,16 @@ public class NodeEntry implements Serializable {
    * thread is already dealing with it.
    */
   @Nullable
-  synchronized Pair<? extends Iterable<SkyKey>, ? extends SkyValue> markDirty(boolean isChanged) {
-    assertKeepEdges();
-    if (isDone()) {
-      GroupedList<SkyKey> lastDirectDeps = GroupedList.create(directDeps);
-      buildingState = BuildingState.newDirtyState(isChanged, lastDirectDeps, value);
-      Pair<? extends Iterable<SkyKey>, ? extends SkyValue> result =
-          Pair.of(lastDirectDeps.toSet(), value);
-      value = null;
-      directDeps = null;
-      return result;
-    }
-    // The caller may be simultaneously trying to mark this node dirty and changed, and the dirty
-    // thread may have lost the race, but it is the caller's responsibility not to try to mark
-    // this node changed twice. The end result of racing markers must be a changed node, since one
-    // of the markers is trying to mark the node changed.
-    Preconditions.checkState(isChanged != isChanged(),
-        "Cannot mark node dirty twice or changed twice: %s", this);
-    Preconditions.checkState(value == null, "Value should have been reset already %s", this);
-    Preconditions.checkState(directDeps == null, "direct deps not already reset %s", this);
-    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();
-    }
-    return null;
-  }
+  @ThreadSafe
+  Pair<? extends Iterable<SkyKey>, ? extends SkyValue> markDirty(boolean isChanged);
 
   /**
    * Marks this entry as up-to-date at this version.
    *
    * @return {@link Set} of reverse dependencies to signal that this node is done.
    */
-  synchronized Set<SkyKey> markClean() {
-    this.value = buildingState.getLastBuildValue();
-    // This checks both the value and the direct deps, but since we're passing in the same value,
-    // the value check should be trivial.
-    Preconditions.checkState(buildingState.unchangedFromLastBuild(this.value),
-        "Direct deps must be the same as those found last build for node to be marked clean: %s",
-        this);
-    Preconditions.checkState(isDirty(), this);
-    Preconditions.checkState(!buildingState.isChanged(), "shouldn't be changed: %s", this);
-    return setStateFinishedAndReturnReverseDeps();
-  }
+  @ThreadSafe
+  Set<SkyKey> markClean();
 
   /**
    * Forces this node to be reevaluated, even if none of its dependencies are known to have
@@ -467,33 +245,28 @@ public class NodeEntry implements Serializable {
    * result. This method should not be used if one of the normal deps of this node has changed,
    * the usual change-pruning process should work in that case.
    */
-  synchronized void forceRebuild() {
-    buildingState.forceChanged();
-  }
+  @ThreadSafe
+  void forceRebuild();
 
   /**
    * Gets the current version of this entry.
    */
-  synchronized Version getVersion() {
-    return version;
-  }
+  @ThreadSafe
+  Version getVersion();
 
   /**
    * 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 BuildingState.DirtyState}.
-   *
-   * @see BuildingState#getDirtyState()
+   * as enumerated by {@link NodeEntry.DirtyState}.
    */
-  synchronized BuildingState.DirtyState getDirtyState() {
-    return buildingState.getDirtyState();
-  }
+  @ThreadSafe
+  NodeEntry.DirtyState getDirtyState();
 
   /**
    * Should only be called if the entry is dirty. During the examination to see if the entry must be
    * re-evaluated, this method returns the next group of children to be checked. Callers should
    * have already called {@link #getDirtyState} and received a return value of
-   * {@link BuildingState.DirtyState#CHECK_DEPENDENCIES} before calling this method -- any other
+   * {@link DirtyState#CHECK_DEPENDENCIES} before calling this method -- any other
    * return value from {@link #getDirtyState} means that this method must not be called, since
    * whether or not the node needs to be rebuilt is already known.
    *
@@ -508,22 +281,18 @@ public class NodeEntry implements Serializable {
    *
    * @see BuildingState#getNextDirtyDirectDeps()
    */
-  synchronized Collection<SkyKey> getNextDirtyDirectDeps() {
-    return buildingState.getNextDirtyDirectDeps();
-  }
+  @ThreadSafe
+  Collection<SkyKey> getNextDirtyDirectDeps();
 
   /**
    * Returns the set of direct dependencies. This may only be called while the node is being
    * evaluated, that is, before {@link #setValue} and after {@link #markDirty}.
    */
-  synchronized Set<SkyKey> getTemporaryDirectDeps() {
-    Preconditions.checkState(!isDone(), "temporary shouldn't be done: %s", this);
-    return buildingState.getDirectDepsForBuild();
-  }
+  @ThreadSafe
+  Set<SkyKey> getTemporaryDirectDeps();
 
-  synchronized boolean noDepsLastBuild() {
-    return buildingState.noDepsLastBuild();
-  }
+  @ThreadSafe
+  boolean noDepsLastBuild();
 
   /**
    * Remove dep from direct deps. This should only be called if this entry is about to be
@@ -532,51 +301,17 @@ public class NodeEntry implements Serializable {
    * chance to finish before the evaluator aborted; or too many cycles were found when it came time
    * to check the children.
    */
-  synchronized void removeUnfinishedDeps(Set<SkyKey> unfinishedDeps) {
-    buildingState.removeDirectDeps(unfinishedDeps);
-  }
+  @ThreadSafe
+  void removeUnfinishedDeps(Set<SkyKey> unfinishedDeps);
 
-  synchronized void addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper) {
-    Preconditions.checkState(!isDone(), "add temp shouldn't be done: %s %s", helper, this);
-    buildingState.addDirectDeps(helper);
-  }
+  @ThreadSafe
+  void addTemporaryDirectDeps(GroupedListHelper<SkyKey> helper);
 
   /**
    * Returns true if the node is ready to be evaluated, i.e., it has been signaled exactly as many
    * times as it has temporary dependencies. This may only be called while the node is being
    * evaluated, that is, before {@link #setValue} and after {@link #markDirty}.
    */
-  synchronized boolean isReady() {
-    Preconditions.checkState(!isDone(), "can't be ready if done: %s", this);
-    return buildingState.isReady();
-  }
-
-  @Override
-  @SuppressWarnings("deprecation")
-  public String toString() {
-    return Objects.toStringHelper(this)  // MoreObjects is not in Guava
-        .add("value", value)
-        .add("version", version)
-        .add("directDeps", directDeps == null ? null : GroupedList.create(directDeps))
-        .add("reverseDeps", REVERSE_DEPS_UTIL.toString(this))
-        .add("buildingState", buildingState).toString();
-  }
-
-  /**
-   * Do not use except in custom evaluator implementations! Added only temporarily.
-   *
-   * <p>Clones a NodeEntry iff it is a done node. Otherwise it fails.
-   */
-  @Deprecated
-  public synchronized NodeEntry cloneNodeEntry() {
-    // As this is temporary, for now lets limit to done nodes
-    Preconditions.checkState(isDone(), "Only done nodes can be copied");
-    NodeEntry nodeEntry = new NodeEntry();
-    nodeEntry.value = value;
-    nodeEntry.version = this.version;
-    REVERSE_DEPS_UTIL.addReverseDeps(nodeEntry, REVERSE_DEPS_UTIL.getReverseDeps(this));
-    nodeEntry.directDeps = directDeps;
-    nodeEntry.buildingState = null;
-    return nodeEntry;
-  }
+  @ThreadSafe
+  boolean isReady();
 }
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 39f11d79ab..a99105847b 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ParallelEvaluator.java
@@ -40,7 +40,6 @@ import com.google.devtools.build.lib.events.StoredEventHandler;
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.util.GroupedList.GroupedListHelper;
-import com.google.devtools.build.skyframe.BuildingState.DirtyState;
 import com.google.devtools.build.skyframe.EvaluationProgressReceiver.EvaluationState;
 import com.google.devtools.build.skyframe.NodeEntry.DependencyState;
 import com.google.devtools.build.skyframe.Scheduler.SchedulerException;
@@ -1580,7 +1579,7 @@ public final class ParallelEvaluator implements Evaluator {
         cyclesFound++;
         Iterable<SkyKey> cycle = graphPath.subList(cycleStart, graphPath.size());
         // Put this node into a consistent state for building if it is dirty.
-        if (entry.isDirty() && entry.getDirtyState() == DirtyState.CHECK_DEPENDENCIES) {
+        if (entry.isDirty() && entry.getDirtyState() == NodeEntry.DirtyState.CHECK_DEPENDENCIES) {
           // In the check deps state, entry has exactly one child not done yet. Note that this node
           // must be part of the path to the cycle we have found (since done nodes cannot be in
           // cycles, and this is the only missing one). Thus, it will not be removed below in