| // Copyright 2017 The Bazel Authors. 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.lib.collect.nestedset; |
| |
| import com.github.benmanes.caffeine.cache.Cache; |
| import com.github.benmanes.caffeine.cache.Caffeine; |
| 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; |
| import com.google.devtools.build.lib.skyframe.serialization.SerializationContext; |
| import com.google.devtools.build.lib.skyframe.serialization.SerializationException; |
| import com.google.protobuf.ByteString; |
| import com.google.protobuf.CodedInputStream; |
| import com.google.protobuf.CodedOutputStream; |
| import java.io.IOException; |
| import java.util.concurrent.ExecutionException; |
| |
| /** Codec for {@link NestedSet} that uses the {@link NestedSetStore}. */ |
| public class NestedSetCodecWithStore implements ObjectCodec<NestedSet<?>> { |
| |
| private enum NestedSetSize { |
| EMPTY, // distinguished empty node; size = 0, depth = 0 |
| LEAF, // a single element; size = 1, depth = 1 |
| NONLEAF // more than one element; size > 1, depth > 1 |
| } |
| |
| private final NestedSetStore nestedSetStore; |
| |
| /** |
| * Used to preserve the invariant that if NestedSets inside two different objects are |
| * reference-equal, they will continue to be reference-equal after deserialization. |
| * |
| * <p>Suppose NestedSet N is contained in objects A and B. If A is deserialized and then B is |
| * deserialized, then when we create N inside B, we will use the version already created inside A. |
| * This depends on the fact that NestedSets with the same underlying Object[] children and order |
| * are equal, and that we have a cache of children Object[] that will contain N's children field |
| * as long as it is in memory. |
| * |
| * <p>If A and B are created, then B is serialized and deserialized while A remains in memory, the |
| * first serialization will put N into this interner, and so the deserialization will reuse it. |
| */ |
| private final Cache<EqualsWrapper, NestedSet<?>> interner = |
| Caffeine.newBuilder().weakValues().build(); |
| |
| /** Creates a NestedSetCodecWithStore that will use the given {@link NestedSetStore}. */ |
| public NestedSetCodecWithStore(NestedSetStore nestedSetStore) { |
| this.nestedSetStore = nestedSetStore; |
| } |
| |
| @SuppressWarnings("unchecked") |
| @Override |
| public Class<NestedSet<?>> getEncodedClass() { |
| // Compiler doesn't like cast from Class<NestedSet> -> Class<NestedSet<T>>, but it |
| // does allow what we see below. Type is lost at runtime anyway, so while gross this works. |
| return (Class<NestedSet<?>>) ((Class<?>) NestedSet.class); |
| } |
| |
| @Override |
| public void serialize(SerializationContext context, NestedSet<?> obj, CodedOutputStream codedOut) |
| throws SerializationException, IOException { |
| context.serialize(obj.getOrder(), codedOut); |
| if (obj.isEmpty()) { |
| // If the NestedSet is empty, it needs to be assigned to the EMPTY_CHILDREN constant on |
| // deserialization. |
| codedOut.writeEnumNoTag(NestedSetSize.EMPTY.ordinal()); |
| } else if (obj.isSingleton()) { |
| // If the NestedSet is a singleton, we serialize directly as an optimization. |
| codedOut.writeEnumNoTag(NestedSetSize.LEAF.ordinal()); |
| context.serialize(obj.getChildren(), codedOut); |
| } else { |
| codedOut.writeEnumNoTag(NestedSetSize.NONLEAF.ordinal()); |
| codedOut.writeInt32NoTag(obj.getApproxDepth()); |
| FingerprintComputationResult fingerprintComputationResult = |
| nestedSetStore.computeFingerprintAndStore((Object[]) obj.getChildren(), context); |
| context.addFutureToBlockWritingOn(fingerprintComputationResult.writeStatus()); |
| codedOut.writeByteArrayNoTag(fingerprintComputationResult.fingerprint().toByteArray()); |
| } |
| interner.put(new EqualsWrapper(obj), obj); |
| } |
| |
| @Override |
| public NestedSet<?> deserialize(DeserializationContext context, CodedInputStream codedIn) |
| throws SerializationException, IOException { |
| Order order = context.deserialize(codedIn); |
| NestedSetSize nestedSetSize = NestedSetSize.values()[codedIn.readEnum()]; |
| switch (nestedSetSize) { |
| case EMPTY: |
| return NestedSetBuilder.emptySet(order); |
| case LEAF: |
| Object contents = context.deserialize(codedIn); |
| return intern(order, /*depth=*/ 1, contents); |
| case NONLEAF: |
| int depth = codedIn.readInt32(); |
| ByteString fingerprint = ByteString.copyFrom(codedIn.readByteArray()); |
| return intern(order, depth, nestedSetStore.getContentsAndDeserialize(fingerprint, context)); |
| } |
| throw new IllegalStateException("NestedSet size " + nestedSetSize + " not known"); |
| } |
| |
| /** |
| * 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#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#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. |
| */ |
| @SuppressWarnings("unchecked") |
| private NestedSet<?> intern(Order order, int depth, Object contents) { |
| NestedSet<?> result; |
| if (contents instanceof ListenableFuture) { |
| result = NestedSet.withFuture(order, depth, (ListenableFuture<Object[]>) contents); |
| } else { |
| result = NestedSet.forDeserialization(order, depth, contents); |
| } |
| return interner.get(new EqualsWrapper(result), unused -> result); |
| } |
| |
| private static final class EqualsWrapper { |
| private final Order order; |
| private final Object children; |
| |
| private EqualsWrapper(NestedSet<?> nestedSet) { |
| // Unwrap the fields we need so that we don't strongly retain the NestedSet. |
| this.order = nestedSet.getOrder(); |
| this.children = nestedSet.children; |
| } |
| |
| @Override |
| public int hashCode() { |
| int childrenHashCode; |
| if (children instanceof ListenableFuture && ((ListenableFuture<?>) children).isDone()) { |
| try { |
| childrenHashCode = Futures.getDone((ListenableFuture<?>) children).hashCode(); |
| } catch (ExecutionException e) { |
| // If the future failed, we can treat it as unequal to all non-future NestedSet instances |
| // (using the hashCode of the Future object) and hide the exception until the NestedSet is |
| // truly needed (i.e. unrolled). Note that NestedSetStore already attaches a listener to |
| // this future that sends a bug report if it fails. |
| childrenHashCode = children.hashCode(); |
| } |
| } else { |
| childrenHashCode = children.hashCode(); |
| } |
| |
| return 37 * order.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) { |
| return false; // Treat a failure to fetch as unequal to a non-future NestedSet. |
| } |
| } |
| |
| @SuppressWarnings("unchecked") |
| @Override |
| public boolean equals(Object obj) { |
| if (this == obj) { |
| return true; |
| } |
| if (!(obj instanceof EqualsWrapper)) { |
| return false; |
| } |
| |
| // Both sets contain Object[] or both sets contain ListenableFuture<Object[]> |
| EqualsWrapper that = (EqualsWrapper) obj; |
| if (this.order.equals(that.order) && this.children.equals(that.children)) { |
| return true; |
| } |
| |
| // One set contains Object[], while the other contains ListenableFuture<Object[]> |
| if (this.children instanceof ListenableFuture && that.children instanceof Object[]) { |
| return deserializingAndMaterializedSetsAreEqual( |
| (Object[]) that.children, (ListenableFuture<Object[]>) this.children); |
| } else if (that.children instanceof ListenableFuture && this.children instanceof Object[]) { |
| return deserializingAndMaterializedSetsAreEqual( |
| (Object[]) this.children, (ListenableFuture<Object[]>) that.children); |
| } else { |
| return false; |
| } |
| } |
| } |
| } |