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 a1acb5c..759f296 100644
--- a/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
+++ b/src/main/java/com/google/devtools/build/skyframe/BuildingState.java
@@ -14,12 +14,14 @@
 package com.google.devtools.build.skyframe;
 
 import com.google.common.base.MoreObjects;
+import com.google.common.base.MoreObjects.ToStringHelper;
 import com.google.common.base.Preconditions;
 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.GroupedList.GroupedListHelper;
+import com.google.devtools.build.skyframe.NodeEntry.DirtyState;
 
 import java.util.Collection;
 import java.util.Collections;
@@ -38,10 +40,11 @@
  * 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 not intended to be used outside of Skyframe.
+ * <p>This class is public only for the benefit of alternative graph implementations outside of the
+ * package.
  */
 @ThreadCompatible
-final class BuildingState {
+public class BuildingState {
   /**
    * During its life, a node can go through states as follows:
    * <ol>
@@ -74,7 +77,7 @@
    * 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 NodeEntry.DirtyState dirtyState = null;
+  private DirtyState dirtyState = null;
 
   /**
    * The number of dependencies that are known to be done in a {@link NodeEntry}. There is a
@@ -161,7 +164,6 @@
    * dependency group storage.
    */
   private final GroupedList<SkyKey> lastBuildDirectDeps;
-  private final SkyValue lastBuildValue;
 
   /**
    * Which child should be re-evaluated next in the process of determining if this entry needs to
@@ -171,18 +173,16 @@
 
   BuildingState() {
     lastBuildDirectDeps = null;
-    lastBuildValue = null;
   }
 
-  private BuildingState(boolean isChanged, GroupedList<SkyKey> lastBuildDirectDeps,
-      SkyValue lastBuildValue) {
+  protected BuildingState(boolean isChanged, GroupedList<SkyKey> lastBuildDirectDeps) {
     this.lastBuildDirectDeps = lastBuildDirectDeps;
-    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 ? NodeEntry.DirtyState.REBUILDING
-        : NodeEntry.DirtyState.CHECK_DEPENDENCIES;
-    if (dirtyState == NodeEntry.DirtyState.CHECK_DEPENDENCIES) {
+        "%s 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) {
       // We need to iterate through the deps to see if they have changed. Initialize the iterator.
       dirtyDirectDepIterator = lastBuildDirectDeps.iterator();
     }
@@ -190,14 +190,14 @@
 
   static BuildingState newDirtyState(boolean isChanged,
       GroupedList<SkyKey> lastBuildDirectDeps, SkyValue lastBuildValue) {
-    return new BuildingState(isChanged, lastBuildDirectDeps, lastBuildValue);
+    return new DirtyBuildingState(isChanged, lastBuildDirectDeps, lastBuildValue);
   }
 
   void markChanged() {
     Preconditions.checkState(isDirty(), this);
     Preconditions.checkState(!isChanged(), this);
     Preconditions.checkState(!evaluating, this);
-    dirtyState = NodeEntry.DirtyState.REBUILDING;
+    dirtyState = DirtyState.REBUILDING;
   }
 
   void forceChanged() {
@@ -205,7 +205,7 @@
     Preconditions.checkState(!isChanged(), this);
     Preconditions.checkState(evaluating, this);
     Preconditions.checkState(isReady(), this);
-    dirtyState = NodeEntry.DirtyState.REBUILDING;
+    dirtyState = DirtyState.REBUILDING;
   }
 
   /**
@@ -233,11 +233,11 @@
    * @see NodeEntry#isChanged()
    */
   boolean isChanged() {
-    return dirtyState == NodeEntry.DirtyState.REBUILDING;
+    return dirtyState == DirtyState.REBUILDING;
   }
 
   private boolean rebuilding() {
-    return dirtyState == NodeEntry.DirtyState.REBUILDING;
+    return dirtyState == DirtyState.REBUILDING;
   }
 
   /**
@@ -247,7 +247,7 @@
    */
   private void checkNotProcessing() {
     Preconditions.checkState(evaluating, "not started building %s", this);
-    Preconditions.checkState(!isDirty() || dirtyState == NodeEntry.DirtyState.VERIFIED_CLEAN
+    Preconditions.checkState(!isDirty() || dirtyState == DirtyState.VERIFIED_CLEAN
         || rebuilding(), "not done building %s", this);
     Preconditions.checkState(isReady(), "not done building %s", this);
   }
@@ -268,8 +268,8 @@
    * 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 NodeEntry.DirtyState#REBUILDING} if the child has changed,
-   * and {@link NodeEntry.DirtyState#VERIFIED_CLEAN} if the child has not changed and this was the
+   * #dirtyState} as needed -- {@link DirtyState#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 #dirtyDirectDepIterator} == null, isReady(),
    * and a flag set in {@link #getNextDirtyDirectDeps}).
    *
@@ -281,12 +281,12 @@
       // Synchronization isn't needed here because the only caller is ValueEntry, which does it
       // through the synchronized method signalDep(long).
       if (childChanged) {
-        dirtyState = NodeEntry.DirtyState.REBUILDING;
-      } else if (dirtyState == NodeEntry.DirtyState.CHECK_DEPENDENCIES && isReady()
+        dirtyState = DirtyState.REBUILDING;
+      } else if (dirtyState == 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 = NodeEntry.DirtyState.VERIFIED_CLEAN;
+        dirtyState = DirtyState.VERIFIED_CLEAN;
       }
     }
     return isReady();
@@ -299,25 +299,26 @@
    */
   boolean unchangedFromLastBuild(SkyValue newValue) {
     checkNotProcessing();
-    return lastBuildValue.equals(newValue) && lastBuildDirectDeps.equals(directDeps);
+    return getLastBuildValue().equals(newValue) && lastBuildDirectDeps.equals(directDeps);
   }
 
   boolean noDepsLastBuild() {
     return lastBuildDirectDeps.isEmpty();
   }
 
-  SkyValue getLastBuildValue() {
-    return Preconditions.checkNotNull(lastBuildValue, this);
+  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 NodeEntry.DirtyState}.
+   * as enumerated by {@link DirtyState}.
    *
    * @see NodeEntry#getDirtyState()
    */
-  NodeEntry.DirtyState 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);
@@ -335,7 +336,7 @@
    */
   Collection<SkyKey> getNextDirtyDirectDeps() {
     Preconditions.checkState(isDirty(), this);
-    Preconditions.checkState(dirtyState == NodeEntry.DirtyState.CHECK_DEPENDENCIES, this);
+    Preconditions.checkState(dirtyState == DirtyState.CHECK_DEPENDENCIES, this);
     Preconditions.checkState(evaluating, this);
     List<SkyKey> nextDeps = ImmutableList.copyOf(dirtyDirectDepIterator.next());
     if (!dirtyDirectDepIterator.hasNext()) {
@@ -363,7 +364,7 @@
    * Returns the direct deps (in groups) found on this build. Should only be called when the node
    * is done.
    *
-   * @see NodeEntry#setStateFinishedAndReturnReverseDeps
+   * @see InMemoryNodeEntry#setStateFinishedAndReturnReverseDeps
    */
   GroupedList<SkyKey> getFinishedDirectDeps() {
     return directDeps;
@@ -406,8 +407,7 @@
     directDeps.remove(unfinishedDeps);
   }
 
-  @Override
-  public String toString() {
+  protected ToStringHelper getStringHelper() {
     return MoreObjects.toStringHelper(this)
         .add("evaluating", evaluating)
         .add("dirtyState", dirtyState)
@@ -415,7 +415,29 @@
         .add("directDeps", directDeps)
         .add("reverseDepsToSignal", REVERSE_DEPS_UTIL.toString(this))
         .add("lastBuildDirectDeps", lastBuildDirectDeps)
-        .add("lastBuildValue", lastBuildValue)
-        .add("dirtyDirectDepIterator", dirtyDirectDepIterator).toString();
+        .add("dirtyDirectDepIterator", dirtyDirectDepIterator);
+  }
+  @Override
+  public 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/InMemoryNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
index 16dbe24..1351d46 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryNodeEntry.java
@@ -59,7 +59,7 @@
    * 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;
+  protected Version version = MinimalVersion.INSTANCE;
 
   /**
    * This object represents a {@link GroupedList}<SkyKey> in a memory-efficient way. It stores the
@@ -94,7 +94,7 @@
    */
   private List<SkyKey> reverseDepsToRemove = null;
 
-  private static final ReverseDepsUtil<InMemoryNodeEntry> REVERSE_DEPS_UTIL =
+  protected static final ReverseDepsUtil<InMemoryNodeEntry> REVERSE_DEPS_UTIL =
       new ReverseDepsUtil<InMemoryNodeEntry>() {
     @Override
     void setReverseDepsObject(InMemoryNodeEntry container, Object object) {
diff --git a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
index b5b295b..26f1136 100644
--- a/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
+++ b/src/main/java/com/google/devtools/build/skyframe/ReverseDepsUtil.java
@@ -32,10 +32,13 @@
  *
  * <p>The reason of this class it to share non-trivial code between BuildingState and NodeEntry. We
  * could simply make those two classes extend this class instead, but we would be less
- * memory-efficient since object memory alignment does not cross classes ( you would have two memory
+ * memory-efficient since object memory alignment does not cross classes (you would have two memory
  * alignments, one for the base class and one for the extended one).
+ *
+ * <p>This class is public only for the benefit of alternative graph implementations outside of the
+ * package.
  */
-abstract class ReverseDepsUtil<T> {
+public abstract class ReverseDepsUtil<T> {
 
   static final int MAYBE_CHECK_THRESHOLD = 10;
 
@@ -82,7 +85,7 @@
    * object directly instead of a wrapper list.
    */
   @SuppressWarnings("unchecked")
-  void addReverseDeps(T container, Collection<SkyKey> newReverseDeps) {
+  public void addReverseDeps(T container, Collection<SkyKey> newReverseDeps) {
     if (newReverseDeps.isEmpty()) {
       return;
     }