Allow deserialization futures as NestedSet contents, with unrolling blocking on that future.

This allows NestedSet deserialization not to block on storage reads - in-progress deserializations are simply made a member of the NestedSets they produce.

PiperOrigin-RevId: 200440131

7 files changed, 280 insertions, 106 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
index 52df58e36a..5371c306eb 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSet.java
@@ -19,6 +19,7 @@ import com.google.common.base.Function;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.util.concurrent.ListenableFuture;
 import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.protobuf.ByteString;
@@ -29,6 +30,7 @@ import java.util.Iterator;
 import java.util.List;
 import java.util.Objects;
 import java.util.Set;
+import java.util.concurrent.ExecutionException;
 import javax.annotation.Nullable;
 
 /**
@@ -55,9 +57,7 @@ public final class NestedSet<E> implements Iterable<E> {
   private static final byte[] LEAF_MEMO = {};
   @AutoCodec static final Object[] EMPTY_CHILDREN = {};
 
-  /**
-   * Construct an empty NestedSet.  Should only be called by Order's class initializer.
-   */
+  /** Construct an empty NestedSet. Should only be called by Order's class initializer. */
   NestedSet(Order order) {
     this.orderAndSize = order.ordinal();
     this.children = EMPTY_CHILDREN;
@@ -116,7 +116,8 @@ public final class NestedSet<E> implements Iterable<E> {
       } else if ((pass == 1) == preorder && !transitive.isEmpty()) {
         CompactHashSet<E> hoisted = CompactHashSet.create();
         for (NestedSet<E> subset : transitiveOrder) {
-          Object c = subset.children;
+          // If this is a deserialization future, this call blocks.
+          Object c = subset.getChildren();
           if (c instanceof Object[]) {
             Object[] a = (Object[]) c;
             if (a.length < 2) {
@@ -149,63 +150,93 @@ public final class NestedSet<E> implements Iterable<E> {
     }
   }
 
-  // Only used by deserialization
-  @AutoCodec.Instantiator
-  NestedSet(Order order, Object children) {
+  private NestedSet(Order order, Object children, byte[] memo) {
     this.orderAndSize = order.ordinal();
     this.children = children;
+    this.memo = memo;
+  }
+
+  /**
+   * Constructs a NestedSet that is currently being deserialized. The provided future, when
+   * complete, gives the contents of the NestedSet.
+   */
+  static <E> NestedSet<E> withFuture(
+      Order order, ListenableFuture<Object[]> deserializationFuture) {
+    return new NestedSet<>(order, deserializationFuture, /*memo=*/ null);
+  }
+
+  // Only used by deserialization
+  @AutoCodec.Instantiator
+  static <E> NestedSet<E> forDeserialization(Order order, Object children) {
+    Preconditions.checkState(!(children instanceof ListenableFuture));
     boolean hasChildren =
         children instanceof Object[]
             && (Arrays.stream((Object[]) children).anyMatch(child -> child instanceof Object[]));
-    this.memo = hasChildren ? null : LEAF_MEMO;
+    byte[] memo = hasChildren ? null : LEAF_MEMO;
+    return new NestedSet<>(order, children, memo);
   }
 
-  /**
-   * Returns the ordering of this nested set.
-   */
+  /** Returns the ordering of this nested set. */
   public Order getOrder() {
     return Order.getOrder(orderAndSize & 3);
   }
 
   /**
-   * Returns the internal item or array. For use by NestedSetVisitor and NestedSetView. Those two
-   * classes also have knowledge of the internal implementation of NestedSet.
+   * Returns the internal item or array. If the internal item is a deserialization future, blocks on
+   * completion. For external use only by NestedSetVisitor and NestedSetView. Those two classes also
+   * have knowledge of the internal implementation of NestedSet.
    */
+  Object getChildren() {
+    if (children instanceof ListenableFuture) {
+      try {
+        return ((ListenableFuture<Object[]>) children).get();
+      } catch (InterruptedException | ExecutionException e) {
+        throw new IllegalStateException(e);
+      }
+    } else {
+      return children;
+    }
+  }
+
+  /** Returns the internal item, array, or future. */
   Object rawChildren() {
     return children;
   }
 
-  /**
-   * Returns true if the set is empty. Runs in O(1) time (i.e. does not flatten the set).
-   */
+  /** Returns true if the set is empty. Runs in O(1) time (i.e. does not flatten the set). */
   public boolean isEmpty() {
+    // We don't check for future members here, since empty sets are special-cased in serialization
+    // and do not make requests against storage.
     return children == EMPTY_CHILDREN;
   }
 
   /** Returns true if the set has exactly one element. */
   public boolean isSingleton() {
-    return !(children instanceof Object[]);
+    // Singleton sets are special cased in serialization, and make no calls to storage.  Therefore,
+    // we know that any NestedSet with a ListenableFuture member is not a singleton.
+    return !(children instanceof Object[] || children instanceof ListenableFuture);
   }
 
   /**
-   * Returns a collection of all unique elements of this set (including subsets)
-   * in an implementation-specified order as a {@code Collection}.
+   * Returns a collection of all unique elements of this set (including subsets) in an
+   * implementation-specified order as a {@code Collection}.
    *
-   * <p>If you do not need a Collection and an Iterable is enough, use the
-   * nested set itself as an Iterable.
+   * <p>If you do not need a Collection and an Iterable is enough, use the nested set itself as an
+   * Iterable.
    */
   public Collection<E> toCollection() {
     return toList();
   }
 
   /**
-   * Returns a collection of all unique elements of this set (including subsets)
-   * in an implementation-specified order as a {code List}.
+   * Returns a collection of all unique elements of this set (including subsets) in an
+   * implementation-specified order as a {code List}.
    *
    * <p>Use {@link #toCollection} when possible for better efficiency.
    */
   public List<E> toList() {
     if (isSingleton()) {
+      // No need to check for ListenableFuture members - singletons can't have them.
       return ImmutableList.of((E) children);
     }
     if (isEmpty()) {
@@ -215,8 +246,8 @@ public final class NestedSet<E> implements Iterable<E> {
   }
 
   /**
-   * Returns a collection of all unique elements of this set (including subsets)
-   * in an implementation-specified order as a {@code Set}.
+   * Returns a collection of all unique elements of this set (including subsets) in an
+   * implementation-specified order as a {@code Set}.
    *
    * <p>Use {@link #toCollection} when possible for better efficiency.
    */
@@ -225,11 +256,13 @@ public final class NestedSet<E> implements Iterable<E> {
   }
 
   /**
-   * Returns true if this set is equal to {@code other} based on the top-level
-   * elements and object identity (==) of direct subsets.  As such, this function
-   * can fail to equate {@code this} with another {@code NestedSet} that holds
-   * the same elements.  It will never fail to detect that two {@code NestedSet}s
-   * are different, however.
+   * Returns true if this set is equal to {@code other} based on the top-level elements and object
+   * identity (==) of direct subsets. As such, this function can fail to equate {@code this} with
+   * another {@code NestedSet} that holds the same elements. It will never fail to detect that two
+   * {@code NestedSet}s are different, however.
+   *
+   * <p>If one of the sets is in the process of deserialization, returns true iff both sets depend
+   * on the same future.
    *
    * @param other the {@code NestedSet} to compare against.
    */
@@ -237,25 +270,28 @@ public final class NestedSet<E> implements Iterable<E> {
     if (this == other) {
       return true;
     }
+
     return other != null
         && getOrder() == other.getOrder()
-        && (children.equals(other.children)
+        && (rawChildren().equals(other.rawChildren())
             || (!isSingleton()
                 && !other.isSingleton()
+                && rawChildren() instanceof Object[]
+                && other.rawChildren() instanceof Object[]
                 && Arrays.equals((Object[]) children, (Object[]) other.children)));
   }
 
   /**
-   * Returns a hash code that produces a notion of identity that is consistent with
-   * {@link #shallowEquals}. In other words, if two {@code NestedSet}s are equal according
-   * to {@code #shallowEquals}, then they return the same {@code shallowHashCode}.
+   * Returns a hash code that produces a notion of identity that is consistent with {@link
+   * #shallowEquals}. In other words, if two {@code NestedSet}s are equal according to {@code
+   * #shallowEquals}, then they return the same {@code shallowHashCode}.
    *
-   * <p>The main reason for having these separate functions instead of reusing
-   * the standard equals/hashCode is to minimize accidental use, since they are
-   * different from both standard Java objects and collection-like objects.
+   * <p>The main reason for having these separate functions instead of reusing the standard
+   * equals/hashCode is to minimize accidental use, since they are different from both standard Java
+   * objects and collection-like objects.
    */
   public int shallowHashCode() {
-    return isSingleton()
+    return isSingleton() || children instanceof ListenableFuture
         ? Objects.hash(getOrder(), children)
         : Objects.hash(getOrder(), Arrays.hashCode((Object[]) children));
   }
@@ -278,7 +314,9 @@ public final class NestedSet<E> implements Iterable<E> {
 
   private enum Stringer implements Function<Object, String> {
     INSTANCE;
-    @Override public String apply(Object o) {
+
+    @Override
+    public String apply(Object o) {
       return childrenToString(o);
     }
   }
@@ -290,9 +328,9 @@ public final class NestedSet<E> implements Iterable<E> {
   }
 
   /**
-   * Implementation of {@link #toList}.  Uses one of three strategies based on the value of
-   * {@code this.memo}: wrap our direct items in a list, call {@link #lockedExpand} to perform
-   * the initial {@link #walk}, or call {@link #replay} if we have a nontrivial memo.
+   * Implementation of {@link #toList}. Uses one of three strategies based on the value of {@code
+   * this.memo}: wrap our direct items in a list, call {@link #lockedExpand} to perform the initial
+   * {@link #walk}, or call {@link #replay} if we have a nontrivial memo.
    */
   private ImmutableList<E> expand() {
     // This value is only set in the constructor, so safe to test here with no lock.
@@ -303,7 +341,7 @@ public final class NestedSet<E> implements Iterable<E> {
     if (members != null) {
       return ImmutableList.copyOf(members);
     }
-    Object[] children = (Object[]) this.children;
+    Object[] children = (Object[]) this.getChildren();
     ImmutableList.Builder<E> output = ImmutableList.builderWithExpectedSize(orderAndSize >> 2);
     replay(output, children, memo, 0);
     return output.build();
@@ -316,26 +354,32 @@ public final class NestedSet<E> implements Iterable<E> {
     ArraySharingCollection(Object[] array) {
       this.array = array;
     }
-    @Override public Object[] toArray() {
+
+    @Override
+    public Object[] toArray() {
       return array;
     }
-    @Override public int size() {
+
+    @Override
+    public int size() {
       return array.length;
     }
-    @Override public Iterator<E> iterator() {
+
+    @Override
+    public Iterator<E> iterator() {
       throw new UnsupportedOperationException();
     }
   }
 
   /**
    * If this is the first call for this object, fills {@code this.memo} and returns a set from
-   * {@link #walk}.  Otherwise returns null; the caller should use {@link #replay} instead.
+   * {@link #walk}. Otherwise returns null; the caller should use {@link #replay} instead.
    */
   private synchronized CompactHashSet<E> lockedExpand() {
     if (memo != null) {
       return null;
     }
-    Object[] children = (Object[]) this.children;
+    Object[] children = (Object[]) this.getChildren();
     CompactHashSet<E> members = CompactHashSet.createWithExpectedSize(128);
     CompactHashSet<Object> sets = CompactHashSet.createWithExpectedSize(128);
     sets.add(children);
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTestUtils.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTestUtils.java
index ea455f87e1..36171b5cdc 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTestUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecTestUtils.java
@@ -23,6 +23,7 @@ import com.google.devtools.build.lib.skyframe.serialization.SerializationExcepti
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.VisibleForSerialization;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
+import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester.VerificationFunction;
 import java.io.IOException;
 
 /** Utilities for testing NestedSet serialization. */
@@ -49,7 +50,7 @@ public class NestedSetCodecTestUtils {
         return false;
       }
       HasNestedSet that = (HasNestedSet) o;
-      return Objects.equal(nestedSetField.rawChildren(), that.nestedSetField.rawChildren());
+      return Objects.equal(nestedSetField.getChildren(), that.nestedSetField.getChildren());
     }
 
     @Override
@@ -59,7 +60,8 @@ public class NestedSetCodecTestUtils {
   }
 
   /** Perform serialization/deserialization checks for several simple NestedSet examples. */
-  public static void checkCodec(ObjectCodecs objectCodecs, boolean allowFutureBlocking)
+  public static void checkCodec(
+      ObjectCodecs objectCodecs, boolean allowFutureBlocking, boolean assertSymmetricEquality)
       throws Exception {
     new SerializationTester(
             NestedSetBuilder.emptySet(Order.STABLE_ORDER),
@@ -86,7 +88,7 @@ public class NestedSetCodecTestUtils {
                 new HasNestedSet(NestedSetBuilder.create(Order.STABLE_ORDER, "a"))))
         .setObjectCodecs(objectCodecs)
         .makeMemoizingAndAllowFutureBlocking(allowFutureBlocking)
-        .setVerificationFunction(NestedSetCodecTestUtils::verifyDeserialization)
+        .setVerificationFunction(verificationFunction(assertSymmetricEquality))
         .runTests();
   }
 
@@ -94,15 +96,21 @@ public class NestedSetCodecTestUtils {
       NestedSetStore store, NestedSet<?> nestedSet, SerializationContext serializationContext)
       throws IOException, SerializationException {
     return store
-        .computeFingerprintAndStore((Object[]) nestedSet.rawChildren(), serializationContext)
+        .computeFingerprintAndStore((Object[]) nestedSet.getChildren(), serializationContext)
         .writeStatus();
   }
 
-  private static void verifyDeserialization(
-      NestedSet<String> subject, NestedSet<String> deserialized) {
-    assertThat(subject.getOrder()).isEqualTo(deserialized.getOrder());
-    assertThat(subject.toSet()).isEqualTo(deserialized.toSet());
-    verifyStructure(subject.rawChildren(), deserialized.rawChildren());
+  private static VerificationFunction<NestedSet<String>> verificationFunction(
+      boolean assertSymmetricEquality) {
+    return (subject, deserialized) -> {
+      if (assertSymmetricEquality) {
+        assertThat(subject).isEqualTo(deserialized);
+        assertThat(deserialized).isEqualTo(subject);
+      }
+      assertThat(subject.getOrder()).isEqualTo(deserialized.getOrder());
+      assertThat(subject.toSet()).isEqualTo(deserialized.toSet());
+      verifyStructure(subject.getChildren(), deserialized.getChildren());
+    };
   }
 
   private static void verifyStructure(Object lhs, Object rhs) {
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java
index 081fd674f8..acd7ec5931 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetCodecWithStore.java
@@ -15,6 +15,8 @@ package com.google.devtools.build.lib.collect.nestedset;
 
 import com.google.common.cache.Cache;
 import com.google.common.cache.CacheBuilder;
+import com.google.common.util.concurrent.Futures;
+import com.google.common.util.concurrent.ListenableFuture;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetStore.FingerprintComputationResult;
 import com.google.devtools.build.lib.skyframe.serialization.DeserializationContext;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec;
@@ -86,11 +88,11 @@ public class NestedSetCodecWithStore<T> implements ObjectCodec<NestedSet<T>> {
     } else if (obj.isSingleton()) {
       // If the NestedSet is a singleton, we serialize directly as an optimization.
       codedOut.writeEnumNoTag(NestedSetSize.SINGLETON.ordinal());
-      context.serialize(obj.rawChildren(), codedOut);
+      context.serialize(obj.getChildren(), codedOut);
     } else {
       codedOut.writeEnumNoTag(NestedSetSize.GROUP.ordinal());
       FingerprintComputationResult fingerprintComputationResult =
-          nestedSetStore.computeFingerprintAndStore((Object[]) obj.rawChildren(), context);
+          nestedSetStore.computeFingerprintAndStore((Object[]) obj.getChildren(), context);
       context.addFutureToBlockWritingOn(fingerprintComputationResult.writeStatus());
       codedOut.writeByteArrayNoTag(fingerprintComputationResult.fingerprint().toByteArray());
     }
@@ -115,8 +117,9 @@ public class NestedSetCodecWithStore<T> implements ObjectCodec<NestedSet<T>> {
         return intern(order, contents);
       case GROUP:
         ByteString fingerprint = ByteString.copyFrom(codedIn.readByteArray());
-        Object members = nestedSetStore.getContentsAndDeserialize(fingerprint, context);
-        return intern(order, members);
+        ListenableFuture<Object[]> deserializationFuture =
+            nestedSetStore.getContentsAndDeserialize(fingerprint, context);
+        return intern(order, deserializationFuture);
     }
     throw new IllegalStateException("NestedSet size " + nestedSetSize + " not known");
   }
@@ -125,20 +128,31 @@ public class NestedSetCodecWithStore<T> implements ObjectCodec<NestedSet<T>> {
    * Morally, NestedSets are compared using reference equality, to avoid the cost of unrolling them.
    * However, when deserializing NestedSet, we don't want to end up with two sets that "should" be
    * reference-equal, but are not. Since our codec implementation caches the underlying {@link
-   * NestedSet#children} Object[], two nested sets that should be the same will have equal
-   * underlying {@link NestedSet#children}, so we can use that for an equality check.
+   * NestedSet#getChildren()} Object[], two nested sets that should be the same will have equal
+   * underlying {@link NestedSet#getChildren()}, so we can use that for an equality check.
+   *
+   * <p>We also would like to prevent the existence of two equal NestedSets in a single JVM, in
+   * which one NestedSet contains an Object[] and the other contains a ListenableFuture<Object[]>
+   * for the same contents. This can happen if a NestedSet is serialized, and then deserialized with
+   * a call to storage for those contents. In order to guarantee that only one NestedSet exists for
+   * a given Object[], the interner checks the doneness of any ListenableFuture, and if done, holds
+   * on only to the "materialized" NestedSet, with the Object[] as its children object.
    *
    * <p>Note that singleton NestedSets' underlying children are not cached, but we must still
    * enforce equality for them. To do that, we use the #hashCode and #equals of the {@link
-   * NestedSet#children}. When that field is an Object[], this is just identity hash code and
+   * NestedSet#getChildren()}. When that field is an Object[], this is just identity hash code and
    * reference equality, but when it is something else (like an Artifact), we will do an actual
    * equality comparison. This may make some singleton NestedSets reference-equal where they were
    * not before. This should be ok as long as the contained object properly implements equality.
-   *
-   * <p>TODO(janakr): Fix this bug.
    */
+  @SuppressWarnings("unchecked")
   private NestedSet<T> intern(Order order, Object contents) {
-    NestedSet<T> result = new NestedSet<>(order, contents);
+    NestedSet<T> result;
+    if (contents instanceof ListenableFuture) {
+      result = NestedSet.withFuture(order, (ListenableFuture<Object[]>) contents);
+    } else {
+      result = NestedSet.forDeserialization(order, contents);
+    }
     try {
       return interner.get(new EqualsWrapper<>(result), () -> result);
     } catch (ExecutionException e) {
@@ -153,11 +167,38 @@ public class NestedSetCodecWithStore<T> implements ObjectCodec<NestedSet<T>> {
       this.nestedSet = nestedSet;
     }
 
+    @SuppressWarnings("unchecked")
     @Override
     public int hashCode() {
-      return 37 * nestedSet.getOrder().hashCode() + nestedSet.rawChildren().hashCode();
+      int childrenHashCode;
+      if (nestedSet.rawChildren() instanceof ListenableFuture
+          && ((ListenableFuture) nestedSet.rawChildren()).isDone()) {
+        try {
+          childrenHashCode = Futures.getDone((ListenableFuture) nestedSet.rawChildren()).hashCode();
+        } catch (ExecutionException e) {
+          throw new IllegalStateException(e);
+        }
+      } else {
+        childrenHashCode = nestedSet.rawChildren().hashCode();
+      }
+
+      return 37 * nestedSet.getOrder().hashCode() + childrenHashCode;
     }
 
+    private static boolean deserializingAndMaterializedSetsAreEqual(
+        Object[] contents, ListenableFuture<Object[]> contentsFuture) {
+      if (!contentsFuture.isDone()) {
+        return false;
+      }
+
+      try {
+        return Futures.getDone(contentsFuture) == contents;
+      } catch (ExecutionException e) {
+        throw new IllegalStateException(e);
+      }
+    }
+
+    @SuppressWarnings("unchecked")
     @Override
     public boolean equals(Object obj) {
       if (this == obj) {
@@ -166,9 +207,28 @@ public class NestedSetCodecWithStore<T> implements ObjectCodec<NestedSet<T>> {
       if (!(obj instanceof EqualsWrapper)) {
         return false;
       }
+
+      // Both sets contain Object[] or both sets contain ListenableFuture<Object[]>
       NestedSet<?> thatSet = ((EqualsWrapper<?>) obj).nestedSet;
-      return this.nestedSet.getOrder().equals(thatSet.getOrder())
-          && this.nestedSet.rawChildren().equals(thatSet.rawChildren());
+      if (this.nestedSet.getOrder().equals(thatSet.getOrder())
+          && this.nestedSet.rawChildren().equals(thatSet.rawChildren())) {
+        return true;
+      }
+
+      // One set contains Object[], while the other contains ListenableFuture<Object[]>
+      if (this.nestedSet.rawChildren() instanceof ListenableFuture
+          && thatSet.rawChildren() instanceof Object[]) {
+        return deserializingAndMaterializedSetsAreEqual(
+            (Object[]) thatSet.rawChildren(),
+            (ListenableFuture<Object[]>) this.nestedSet.rawChildren());
+      } else if (thatSet.rawChildren() instanceof ListenableFuture
+          && this.nestedSet.rawChildren() instanceof Object[]) {
+        return deserializingAndMaterializedSetsAreEqual(
+            (Object[]) this.nestedSet.rawChildren(),
+            (ListenableFuture<Object[]>) thatSet.rawChildren());
+      } else {
+        return false;
+      }
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
index f0b1c2a8db..8eb4131793 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetFingerprintCache.java
@@ -53,7 +53,7 @@ public class NestedSetFingerprintCache {
     }
     DigestMap digestMap = mapFnToDigestMap.computeIfAbsent(mapFn, this::newDigestMap);
     fingerprint.addInt(nestedSet.getOrder().ordinal());
-    Object children = nestedSet.rawChildren();
+    Object children = nestedSet.getChildren();
     addToFingerprint(mapFn, fingerprint, digestMap, children);
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetStore.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetStore.java
index 52d7769a2c..173420aa1d 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetStore.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetStore.java
@@ -31,7 +31,11 @@ import com.google.protobuf.CodedInputStream;
 import com.google.protobuf.CodedOutputStream;
 import java.io.ByteArrayOutputStream;
 import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
 import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.Executor;
 import javax.annotation.Nullable;
 
 /**
@@ -70,11 +74,12 @@ public class NestedSetStore {
     /**
      * Retrieves the serialized bytes for the NestedSet contents associated with this fingerprint.
      */
-    byte[] get(ByteString fingerprint) throws IOException;
+    ListenableFuture<byte[]> get(ByteString fingerprint) throws IOException;
   }
 
   /** An in-memory {@link NestedSetStorageEndpoint} */
-  private static class InMemoryNestedSetStorageEndpoint implements NestedSetStorageEndpoint {
+  @VisibleForTesting
+  static class InMemoryNestedSetStorageEndpoint implements NestedSetStorageEndpoint {
     private final ConcurrentHashMap<ByteString, byte[]> fingerprintToContents =
         new ConcurrentHashMap<>();
 
@@ -85,14 +90,15 @@ public class NestedSetStore {
     }
 
     @Override
-    public byte[] get(ByteString fingerprint) {
-      return fingerprintToContents.get(fingerprint);
+    public ListenableFuture<byte[]> get(ByteString fingerprint) {
+      return Futures.immediateFuture(fingerprintToContents.get(fingerprint));
     }
   }
 
   /** An in-memory cache for fingerprint <-> NestedSet associations. */
-  private static class NestedSetCache {
-    private final Cache<ByteString, Object[]> fingerprintToContents =
+  @VisibleForTesting
+  static class NestedSetCache {
+    private final Cache<ByteString, ListenableFuture<Object[]>> fingerprintToContents =
         CacheBuilder.newBuilder()
             .concurrencyLevel(SerializationConstants.DESERIALIZATION_POOL_SIZE)
             .weakValues()
@@ -110,7 +116,7 @@ public class NestedSetStore {
      * fingerprint is not known.
      */
     @Nullable
-    public Object[] contentsForFingerprint(ByteString fingerprint) {
+    public ListenableFuture<Object[]> contentsForFingerprint(ByteString fingerprint) {
       return fingerprintToContents.getIfPresent(fingerprint);
     }
 
@@ -124,9 +130,29 @@ public class NestedSetStore {
     }
 
     /** Associates the provided fingerprint and NestedSet contents. */
+    public void put(
+        FingerprintComputationResult fingerprintComputationResult,
+        ListenableFuture<Object[]> contents) {
+      contents.addListener(
+          () -> {
+            try {
+              contentsToFingerprint.put(Futures.getDone(contents), fingerprintComputationResult);
+            } catch (ExecutionException e) {
+              throw new AssertionError(
+                  "Expected write for "
+                      + fingerprintComputationResult.fingerprint()
+                      + " to be complete",
+                  e.getCause());
+            }
+          },
+          MoreExecutors.directExecutor());
+      fingerprintToContents.put(fingerprintComputationResult.fingerprint(), contents);
+    }
+
     public void put(FingerprintComputationResult fingerprintComputationResult, Object[] contents) {
       contentsToFingerprint.put(contents, fingerprintComputationResult);
-      fingerprintToContents.put(fingerprintComputationResult.fingerprint(), contents);
+      fingerprintToContents.put(
+          fingerprintComputationResult.fingerprint(), Futures.immediateFuture(contents));
     }
   }
 
@@ -145,12 +171,31 @@ public class NestedSetStore {
     public abstract ListenableFuture<Void> writeStatus();
   }
 
-  private final NestedSetCache nestedSetCache = new NestedSetCache();
+  private final NestedSetCache nestedSetCache;
   private final NestedSetStorageEndpoint nestedSetStorageEndpoint;
+  private final Executor executor;
 
   /** Creates a NestedSetStore with the provided {@link NestedSetStorageEndpoint} as a backend. */
   public NestedSetStore(NestedSetStorageEndpoint nestedSetStorageEndpoint) {
+    this(nestedSetStorageEndpoint, new NestedSetCache(), MoreExecutors.directExecutor());
+  }
+
+  /**
+   * Creates a NestedSetStore with the provided {@link NestedSetStorageEndpoint} and executor for
+   * deserialization.
+   */
+  public NestedSetStore(NestedSetStorageEndpoint nestedSetStorageEndpoint, Executor executor) {
+    this(nestedSetStorageEndpoint, new NestedSetCache(), executor);
+  }
+
+  @VisibleForTesting
+  public NestedSetStore(
+      NestedSetStorageEndpoint nestedSetStorageEndpoint,
+      NestedSetCache nestedSetCache,
+      Executor executor) {
     this.nestedSetStorageEndpoint = nestedSetStorageEndpoint;
+    this.nestedSetCache = nestedSetCache;
+    this.executor = executor;
   }
 
   /** Creates a NestedSetStore with an in-memory storage backend. */
@@ -226,37 +271,54 @@ public class NestedSetStore {
   }
 
   /** Retrieves and deserializes the NestedSet contents associated with the given fingerprint. */
-  public Object[] getContentsAndDeserialize(
-      ByteString fingerprint, DeserializationContext deserializationContext)
-      throws SerializationException, IOException {
-    Object[] contents = nestedSetCache.contentsForFingerprint(fingerprint);
+  public ListenableFuture<Object[]> getContentsAndDeserialize(
+      ByteString fingerprint, DeserializationContext deserializationContext) throws IOException {
+    ListenableFuture<Object[]> contents = nestedSetCache.contentsForFingerprint(fingerprint);
     if (contents != null) {
       return contents;
     }
+    ListenableFuture<byte[]> retrieved = nestedSetStorageEndpoint.get(fingerprint);
+    ListenableFuture<Object[]> result =
+        Futures.transformAsync(
+            retrieved,
+            bytes -> {
+              CodedInputStream codedIn = CodedInputStream.newInstance(bytes);
+              int numberOfElements = codedIn.readInt32();
+              DeserializationContext newDeserializationContext =
+                  deserializationContext.getNewMemoizingContext();
 
-    byte[] retrieved = nestedSetStorageEndpoint.get(fingerprint);
-    if (retrieved == null) {
-      throw new AssertionError("Fingerprint " + fingerprint + " not found in NestedSetStore");
-    }
+              // The elements of this list are futures for the deserialized values of these
+              // NestedSet contents.  For direct members, the futures complete immediately and yield
+              // an Object.  For transitive members (fingerprints), the futures complete with the
+              // underlying fetch, and yield Object[]s.
+              List<ListenableFuture<?>> deserializationFutures = new ArrayList<>();
+              for (int i = 0; i < numberOfElements; i++) {
+                Object deserializedElement = newDeserializationContext.deserialize(codedIn);
+                if (deserializedElement instanceof ByteString) {
+                  deserializationFutures.add(
+                      getContentsAndDeserialize(
+                          (ByteString) deserializedElement, deserializationContext));
+                } else {
+                  deserializationFutures.add(Futures.immediateFuture(deserializedElement));
+                }
+              }
 
-    CodedInputStream codedIn = CodedInputStream.newInstance(retrieved);
-    DeserializationContext newDeserializationContext =
-        deserializationContext.getNewMemoizingContext();
-
-    int numberOfElements = codedIn.readInt32();
-    Object[] dereferencedContents = new Object[numberOfElements];
-    for (int i = 0; i < numberOfElements; i++) {
-      Object deserializedElement = newDeserializationContext.deserialize(codedIn);
-      dereferencedContents[i] =
-          deserializedElement instanceof ByteString
-              ? getContentsAndDeserialize(
-                  (ByteString) deserializedElement, deserializationContext)
-              : deserializedElement;
-    }
+              return Futures.whenAllComplete(deserializationFutures)
+                  .call(
+                      () -> {
+                        Object[] deserializedContents = new Object[deserializationFutures.size()];
+                        for (int i = 0; i < deserializationFutures.size(); i++) {
+                          deserializedContents[i] = Futures.getDone(deserializationFutures.get(i));
+                        }
+                        return deserializedContents;
+                      },
+                      executor);
+            },
+            executor);
 
     FingerprintComputationResult fingerprintComputationResult =
         FingerprintComputationResult.create(fingerprint, Futures.immediateFuture(null));
-    nestedSetCache.put(fingerprintComputationResult, dereferencedContents);
-    return dereferencedContents;
+    nestedSetCache.put(fingerprintComputationResult, result);
+    return result;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java
index 2d81b8ef66..26487b0915 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetView.java
@@ -42,7 +42,7 @@ public class NestedSetView<E> {
 
   /** Construct a view of a given NestedSet. */
   public NestedSetView(NestedSet<E> set) {
-    this(set.rawChildren());
+    this(set.getChildren());
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java
index 090b8e33bb..c6e0e87133 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetVisitor.java
@@ -59,7 +59,7 @@ public final class NestedSetVisitor<E> {
     // We can short-circuit empty nested set visitation here, avoiding load on the shared map
     // VisitedState#seenNodes.
     if (!nestedSet.isEmpty()) {
-      visitRaw(nestedSet.rawChildren());
+      visitRaw(nestedSet.getChildren());
     }
   }