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

1 files changed, 73 insertions, 13 deletions

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;
+      }
     }
   }
 }