Refactor NodeEntry, create node representation without a value

This CL introduces a ThinNodeEntry, which is a NodeEntry without the
means of accessing its value. The InvalidatingNodeVisitor does not
need to access nodes' values while doing its work, so it is provided
with a ThinNodeQueryableGraph, capable of producing only
ThinNodeEntries.

--
MOS_MIGRATED_REVID=102088111

6 files changed, 240 insertions, 142 deletions

diff --git a/src/main/java/com/google/devtools/build/skyframe/EagerInvalidator.java b/src/main/java/com/google/devtools/build/skyframe/EagerInvalidator.java
index cfe03e2fc6..6e553be7b6 100644
--- a/src/main/java/com/google/devtools/build/skyframe/EagerInvalidator.java
+++ b/src/main/java/com/google/devtools/build/skyframe/EagerInvalidator.java
@@ -44,18 +44,22 @@ public final class EagerInvalidator {
   public static void delete(DirtiableGraph graph, Iterable<SkyKey> diff,
       EvaluationProgressReceiver invalidationReceiver, InvalidationState state,
       boolean traverseGraph, DirtyKeyTracker dirtyKeyTracker) throws InterruptedException {
-    InvalidatingNodeVisitor visitor =
-        createDeletingVisitorIfNeeded(graph, diff, invalidationReceiver, state, traverseGraph,
-            dirtyKeyTracker);
+    DeletingNodeVisitor visitor =
+        createDeletingVisitorIfNeeded(
+            graph, diff, invalidationReceiver, state, traverseGraph, dirtyKeyTracker);
     if (visitor != null) {
       visitor.run();
     }
   }
 
   @Nullable
-  static InvalidatingNodeVisitor createDeletingVisitorIfNeeded(DirtiableGraph graph,
-      Iterable<SkyKey> diff, EvaluationProgressReceiver invalidationReceiver,
-      InvalidationState state, boolean traverseGraph, DirtyKeyTracker dirtyKeyTracker) {
+  static DeletingNodeVisitor createDeletingVisitorIfNeeded(
+      DirtiableGraph graph,
+      Iterable<SkyKey> diff,
+      EvaluationProgressReceiver invalidationReceiver,
+      InvalidationState state,
+      boolean traverseGraph,
+      DirtyKeyTracker dirtyKeyTracker) {
     state.update(diff);
     return state.isEmpty() ? null
         : new DeletingNodeVisitor(graph, invalidationReceiver, state, traverseGraph,
@@ -63,9 +67,12 @@ public final class EagerInvalidator {
   }
 
   @Nullable
-  static InvalidatingNodeVisitor createInvalidatingVisitorIfNeeded(DirtiableGraph graph,
-      Iterable<SkyKey> diff, EvaluationProgressReceiver invalidationReceiver,
-      InvalidationState state, DirtyKeyTracker dirtyKeyTracker,
+  static DirtyingNodeVisitor createInvalidatingVisitorIfNeeded(
+      ThinNodeQueryableGraph graph,
+      Iterable<SkyKey> diff,
+      EvaluationProgressReceiver invalidationReceiver,
+      InvalidationState state,
+      DirtyKeyTracker dirtyKeyTracker,
       Function<ThreadPoolExecutorParams, ThreadPoolExecutor> executorFactory) {
     state.update(diff);
     return state.isEmpty() ? null
@@ -74,9 +81,12 @@ public final class EagerInvalidator {
   }
 
   @Nullable
-  static InvalidatingNodeVisitor createInvalidatingVisitorIfNeeded(DirtiableGraph graph,
-      Iterable<SkyKey> diff, EvaluationProgressReceiver invalidationReceiver,
-      InvalidationState state, DirtyKeyTracker dirtyKeyTracker) {
+  static DirtyingNodeVisitor createInvalidatingVisitorIfNeeded(
+      DirtiableGraph graph,
+      Iterable<SkyKey> diff,
+      EvaluationProgressReceiver invalidationReceiver,
+      InvalidationState state,
+      DirtyKeyTracker dirtyKeyTracker) {
     return createInvalidatingVisitorIfNeeded(graph, diff, invalidationReceiver, state,
         dirtyKeyTracker, AbstractQueueVisitor.EXECUTOR_FACTORY);
   }
@@ -85,18 +95,21 @@ public final class EagerInvalidator {
    * Invalidates given values and their upward transitive closure in the graph, using an executor
    * constructed with the provided factory, if necessary.
    */
-  public static void invalidate(DirtiableGraph graph, Iterable<SkyKey> diff,
-      EvaluationProgressReceiver invalidationReceiver, InvalidationState state,
+  public static void invalidate(
+      ThinNodeQueryableGraph graph,
+      Iterable<SkyKey> diff,
+      EvaluationProgressReceiver invalidationReceiver,
+      InvalidationState state,
       DirtyKeyTracker dirtyKeyTracker,
       Function<ThreadPoolExecutorParams, ThreadPoolExecutor> executorFactory)
-          throws InterruptedException {
+      throws InterruptedException {
     // If we are invalidating, we must be in an incremental build by definition, so we must
     // maintain a consistent graph state by traversing the graph and invalidating transitive
     // dependencies. If edges aren't present, it would be impossible to check the dependencies of
     // a dirty node in any case.
-    InvalidatingNodeVisitor visitor =
-        createInvalidatingVisitorIfNeeded(graph, diff, invalidationReceiver, state,
-            dirtyKeyTracker, executorFactory);
+    DirtyingNodeVisitor visitor =
+        createInvalidatingVisitorIfNeeded(
+            graph, diff, invalidationReceiver, state, dirtyKeyTracker, executorFactory);
     if (visitor != null) {
       visitor.run();
     }
diff --git a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
index 13d4dc1bcc..3f4a86362a 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InvalidatingNodeVisitor.java
@@ -50,7 +50,8 @@ import javax.annotation.Nullable;
  *
  * <p>This is intended only for use in alternative {@code MemoizingEvaluator} implementations.
  */
-public abstract class InvalidatingNodeVisitor extends AbstractQueueVisitor {
+public abstract class InvalidatingNodeVisitor<TGraph extends ThinNodeQueryableGraph>
+    extends AbstractQueueVisitor {
 
   // Default thread count is equal to the number of cores to exploit
   // that level of hardware parallelism, since invalidation should be CPU-bound.
@@ -59,21 +60,25 @@ public abstract class InvalidatingNodeVisitor extends AbstractQueueVisitor {
 
   private static final boolean MUST_EXIST = true;
 
-  protected final DirtiableGraph graph;
+  protected final TGraph graph;
   @Nullable protected final EvaluationProgressReceiver invalidationReceiver;
   protected final DirtyKeyTracker dirtyKeyTracker;
   // Aliased to InvalidationState.pendingVisitations.
   protected final Set<Pair<SkyKey, InvalidationType>> pendingVisitations;
 
   protected InvalidatingNodeVisitor(
-      DirtiableGraph graph, @Nullable EvaluationProgressReceiver invalidationReceiver,
-      InvalidationState state, DirtyKeyTracker dirtyKeyTracker) {
+      TGraph graph,
+      @Nullable EvaluationProgressReceiver invalidationReceiver,
+      InvalidationState state,
+      DirtyKeyTracker dirtyKeyTracker) {
     this(graph, invalidationReceiver, state, dirtyKeyTracker, EXECUTOR_FACTORY);
   }
 
   protected InvalidatingNodeVisitor(
-      DirtiableGraph graph, @Nullable EvaluationProgressReceiver invalidationReceiver,
-      InvalidationState state, DirtyKeyTracker dirtyKeyTracker,
+      TGraph graph,
+      @Nullable EvaluationProgressReceiver invalidationReceiver,
+      InvalidationState state,
+      DirtyKeyTracker dirtyKeyTracker,
       Function<ThreadPoolExecutorParams, ThreadPoolExecutor> executorFactory) {
     super(/*concurrent=*/true,
         /*corePoolSize=*/DEFAULT_THREAD_COUNT,
@@ -189,7 +194,7 @@ public abstract class InvalidatingNodeVisitor extends AbstractQueueVisitor {
   /**
    * A node-deleting implementation.
    */
-  static class DeletingNodeVisitor extends InvalidatingNodeVisitor {
+  static class DeletingNodeVisitor extends InvalidatingNodeVisitor<DirtiableGraph> {
 
     private final Set<SkyKey> visitedValues = Sets.newConcurrentHashSet();
     private final boolean traverseGraph;
@@ -266,12 +271,14 @@ public abstract class InvalidatingNodeVisitor extends AbstractQueueVisitor {
   /**
    * A node-dirtying implementation.
    */
-  static class DirtyingNodeVisitor extends InvalidatingNodeVisitor {
+  static class DirtyingNodeVisitor extends InvalidatingNodeVisitor<ThinNodeQueryableGraph> {
 
     private final Set<Pair<SkyKey, InvalidationType>> visited = Sets.newConcurrentHashSet();
 
-    protected DirtyingNodeVisitor(DirtiableGraph graph,
-        EvaluationProgressReceiver invalidationReceiver, InvalidationState state,
+    protected DirtyingNodeVisitor(
+        ThinNodeQueryableGraph graph,
+        EvaluationProgressReceiver invalidationReceiver,
+        InvalidationState state,
         DirtyKeyTracker dirtyKeyTracker,
         Function<ThreadPoolExecutorParams, ThreadPoolExecutor> executorFactory) {
       super(graph, invalidationReceiver, state, dirtyKeyTracker, executorFactory);
@@ -319,60 +326,68 @@ public abstract class InvalidatingNodeVisitor extends AbstractQueueVisitor {
         return;
       }
       pendingVisitations.add(invalidationPair);
-      enqueue(new Runnable() {
-        @Override
-        public void run() {
-          NodeEntry entry = graph.get(key);
-
-          if (entry == null) {
-            Preconditions.checkState(!mustExist,
-                "%s does not exist in the graph but was enqueued for dirtying by another node",
-                key);
-            pendingVisitations.remove(invalidationPair);
-            return;
-          }
+      enqueue(
+          new Runnable() {
+            @Override
+            public void run() {
+              ThinNodeEntry entry = graph.get(key);
+
+              if (entry == null) {
+                Preconditions.checkState(
+                    !mustExist,
+                    "%s does not exist in the graph but was enqueued for dirtying by another node",
+                    key);
+                pendingVisitations.remove(invalidationPair);
+                return;
+              }
 
-          if (entry.isChanged() || (!isChanged && entry.isDirty())) {
-            // If this node is already marked changed, or we are only marking this node dirty, and
-            // it already is, move along.
-            pendingVisitations.remove(invalidationPair);
-            return;
-          }
+              if (entry.isChanged() || (!isChanged && entry.isDirty())) {
+                // If this node is already marked changed, or we are only marking this node
+                // dirty, and it already is, move along.
+                pendingVisitations.remove(invalidationPair);
+                return;
+              }
 
-          // This entry remains in the graph in this dirty state until it is re-evaluated.
-          Iterable<SkyKey> deps = entry.markDirty(isChanged);
-          // It is not safe to interrupt the logic from this point until the end of the method.
-          // Any exception thrown should be unrecoverable.
-          if (deps == null) {
-            // Another thread has already dirtied this node. Don't do anything in this thread.
-            pendingVisitations.remove(invalidationPair);
-            return;
-          }
-          // Propagate dirtiness upwards and mark this node dirty/changed. Reverse deps should only
-          // be marked dirty (because only a dependency of theirs has changed).
-          for (SkyKey reverseDep : entry.getReverseDeps()) {
-            visit(reverseDep, InvalidationType.DIRTIED, MUST_EXIST);
-          }
+              // This entry remains in the graph in this dirty state until it is re-evaluated.
+              Iterable<SkyKey> deps = entry.markDirty(isChanged);
+              // It is not safe to interrupt the logic from this point until the end of the method.
+              // Any exception thrown should be unrecoverable.
+              if (deps == null) {
+                // Another thread has already dirtied this node. Don't do anything in this thread.
+                pendingVisitations.remove(invalidationPair);
+                return;
+              }
+              // Propagate dirtiness upwards and mark this node dirty/changed. Reverse deps
+              // should only be marked dirty (because only a dependency of theirs has changed).
+              for (SkyKey reverseDep : entry.getReverseDeps()) {
+                visit(reverseDep, InvalidationType.DIRTIED, MUST_EXIST);
+              }
 
-          // Remove this node as a reverse dep from its children, since we have reset it and it no
-          // longer lists its children as direct deps.
-          Map<SkyKey, NodeEntry> children = graph.getBatch(deps);
-          if (children.size() != Iterables.size(deps)) {
-            Set<SkyKey> depsSet = ImmutableSet.copyOf(deps);
-            throw new IllegalStateException("Mismatch in getBatch: " + key + ", " + entry + "\n"
-                + Sets.difference(depsSet, children.keySet()) + "\n"
-                + Sets.difference(children.keySet(), depsSet));
-          }
-          for (NodeEntry child : children.values()) {
-            child.removeReverseDep(key);
-          }
+              // Remove this node as a reverse dep from its children, since we have reset it and
+              // it no longer lists its children as direct deps.
+              Map<SkyKey, ? extends ThinNodeEntry> children = graph.getBatch(deps);
+              if (children.size() != Iterables.size(deps)) {
+                Set<SkyKey> depsSet = ImmutableSet.copyOf(deps);
+                throw new IllegalStateException(
+                    "Mismatch in getBatch: "
+                        + key
+                        + ", "
+                        + entry
+                        + "\n"
+                        + Sets.difference(depsSet, children.keySet())
+                        + "\n"
+                        + Sets.difference(children.keySet(), depsSet));
+              }
+              for (ThinNodeEntry child : children.values()) {
+                child.removeReverseDep(key);
+              }
 
-          informInvalidationReceiver(key, EvaluationProgressReceiver.InvalidationState.DIRTY);
-          dirtyKeyTracker.dirty(key);
-          // Remove the node from the set as the last operation.
-          pendingVisitations.remove(invalidationPair);
-        }
-      });
+              informInvalidationReceiver(key, EvaluationProgressReceiver.InvalidationState.DIRTY);
+              dirtyKeyTracker.dirty(key);
+              // Remove the node from the set as the last operation.
+              pendingVisitations.remove(invalidationPair);
+            }
+          });
     }
   }
 }
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 daf1ffca5b..56f89978ae 100644
--- a/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
+++ b/src/main/java/com/google/devtools/build/skyframe/NodeEntry.java
@@ -27,7 +27,7 @@ import javax.annotation.Nullable;
  * <p>This interface is public only for the benefit of alternative graph implementations outside of
  * the package.
  */
-public interface NodeEntry {
+public interface NodeEntry extends ThinNodeEntry {
   /**
    * Return code for {@link #addReverseDepAndCheckIfDone(SkyKey)}.
    */
@@ -71,10 +71,6 @@ public interface NodeEntry {
 
   boolean keepEdges();
 
-  /** Returns whether the entry has been built and is finished evaluating. */
-  @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.
@@ -100,18 +96,6 @@ public interface NodeEntry {
   SkyValue toValue();
 
   /**
-   * Returns an immutable iterable of the direct deps of this node. This method may only be called
-   * after the evaluation of this node is complete, i.e., after {@link #setValue} has been called.
-   *
-   * <p>This method is not very efficient, but is only be called in limited circumstances --
-   * when the node is about to be deleted, or when the node is expected to have no direct deps (in
-   * 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.
-   */
-  @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.
    */
@@ -168,19 +152,6 @@ public interface NodeEntry {
   DependencyState addReverseDepAndCheckIfDone(SkyKey reverseDep);
 
   /**
-   * Removes a reverse dependency.
-   */
-  @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.
-   */
-  @ThreadSafe
-  Iterable<SkyKey> getReverseDeps();
-
-  /**
    * Tell this node that one of its dependencies is now done. Callers must check the return value,
    * and if true, they must re-schedule this node for evaluation. Equivalent to
    * {@code #signalDep(Long.MAX_VALUE)}. Since this entry's version is less than
@@ -204,39 +175,6 @@ public interface NodeEntry {
   boolean signalDep(Version childVersion);
 
   /**
-   * Returns true if the entry is marked dirty, meaning that at least one of its transitive
-   * dependencies is marked changed.
-   */
-  @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.
-   */
-  @ThreadSafe
-  boolean isChanged();
-
-  /**
-   * Marks this node dirty, or changed if {@code isChanged} is true. The node is put in the
-   * just-created state. It will be re-evaluated if necessary during the evaluation phase,
-   * but if it has not changed, it will not force a re-evaluation of its parents.
-   *
-   * <p>{@code markDirty(b)} must not be called on an undone node if {@code isChanged() == b}.
-   * It is the caller's responsibility to ensure that this does not happen.  Calling
-   * {@code markDirty(false)} when {@code isChanged() == true} has no effect. The idea here is that
-   * the caller will only ever want to call {@code markDirty()} a second time if a transition from a
-   * dirty-unchanged state to a dirty-changed state is required.
-   *
-   * @return The direct deps of this entry, or null if the entry has already been marked
-   * dirty. In the latter case, the caller should abort its handling of this node, since another
-   * thread is already dealing with it.
-   */
-  @Nullable
-  @ThreadSafe
-  Iterable<SkyKey> 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.
diff --git a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
index 5fe8c649b9..60f2bc15f5 100644
--- a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
@@ -23,11 +23,12 @@ import javax.annotation.Nullable;
  * A graph that exposes its entries and structure, for use by classes that must traverse it.
  */
 @ThreadSafe
-public interface QueryableGraph {
+public interface QueryableGraph extends ThinNodeQueryableGraph {
   /**
    * Returns the node with the given name, or {@code null} if the node does not exist.
    */
   @Nullable
+  @Override
   NodeEntry get(SkyKey key);
 
   /**
@@ -35,5 +36,6 @@ public interface QueryableGraph {
    * {@code keys}, {@code m.get(k).equals(e)} iff {@code get(k) == e} and {@code e != null}, and
    * {@code !m.containsKey(k)} iff {@code get(k) == null}.
    */
+  @Override
   Map<SkyKey, NodeEntry> getBatch(Iterable<SkyKey> keys);
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
new file mode 100644
index 0000000000..661b52141d
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/ThinNodeEntry.java
@@ -0,0 +1,90 @@
+// Copyright 2015 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.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+
+import javax.annotation.Nullable;
+
+/**
+ * A node in the graph without the means to access its value. All operations on this class are
+ * thread-safe.
+ *
+ * <p>This interface is public only for the benefit of alternative graph implementations outside of
+ * the package.
+ */
+public interface ThinNodeEntry {
+
+  /** Returns whether the entry has been built and is finished evaluating. */
+  @ThreadSafe
+  boolean isDone();
+
+  /**
+   * Returns an immutable iterable of the direct deps of this node. This method may only be called
+   * after the evaluation of this node is complete.
+   *
+   * <p>This method is not very efficient, but is only be called in limited circumstances --
+   * when the node is about to be deleted, or when the node is expected to have no direct deps (in
+   * 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.
+   */
+  @ThreadSafe
+  Iterable<SkyKey> getDirectDeps();
+
+  /**
+   * Removes a reverse dependency.
+   */
+  @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.
+   */
+  @ThreadSafe
+  Iterable<SkyKey> getReverseDeps();
+
+  /**
+   * Returns true if the entry is marked dirty, meaning that at least one of its transitive
+   * dependencies is marked changed.
+   */
+  @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.
+   */
+  @ThreadSafe
+  boolean isChanged();
+
+  /**
+   * Marks this node dirty, or changed if {@code isChanged} is true. The node is put in the
+   * just-created state. It will be re-evaluated if necessary during the evaluation phase,
+   * but if it has not changed, it will not force a re-evaluation of its parents.
+   *
+   * <p>{@code markDirty(b)} must not be called on an undone node if {@code isChanged() == b}.
+   * It is the caller's responsibility to ensure that this does not happen.  Calling
+   * {@code markDirty(false)} when {@code isChanged() == true} has no effect. The idea here is that
+   * the caller will only ever want to call {@code markDirty()} a second time if a transition from a
+   * dirty-unchanged state to a dirty-changed state is required.
+   *
+   * @return The direct deps of this entry, or null if the entry has already been marked
+   * dirty. In the latter case, the caller should abort its handling of this node, since another
+   * thread is already dealing with it.
+   */
+  @Nullable
+  @ThreadSafe
+  Iterable<SkyKey> markDirty(boolean isChanged);
+}
diff --git a/src/main/java/com/google/devtools/build/skyframe/ThinNodeQueryableGraph.java b/src/main/java/com/google/devtools/build/skyframe/ThinNodeQueryableGraph.java
new file mode 100644
index 0000000000..7ad18e98fe
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/skyframe/ThinNodeQueryableGraph.java
@@ -0,0 +1,40 @@
+// 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.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+
+import java.util.Map;
+
+import javax.annotation.Nullable;
+
+/**
+ * A graph that exposes thin representations of its entries and structure, for use by classes that
+ * must traverse it, but not read its entries' values.
+ */
+@ThreadSafe
+public interface ThinNodeQueryableGraph {
+  /**
+   * Returns the thin node with the given name, or {@code null} if the node does not exist.
+   */
+  @Nullable
+  ThinNodeEntry get(SkyKey key);
+
+  /**
+   * Fetches all the given thin nodes. Returns a map {@code m} such that, for all {@code k} in
+   * {@code keys}, {@code m.get(k).equals(e)} iff {@code get(k) == e} and {@code e != null}, and
+   * {@code !m.containsKey(k)} iff {@code get(k) == null}.
+   */
+  Map<SkyKey, ? extends ThinNodeEntry> getBatch(Iterable<SkyKey> keys);
+}