// Copyright 2018 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.google.auto.value.AutoValue;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.cache.Cache;
import com.google.common.cache.CacheBuilder;
import com.google.common.collect.ImmutableList;
import com.google.common.hash.Hashing;
import com.google.common.util.concurrent.Futures;
import com.google.common.util.concurrent.ListenableFuture;
import com.google.common.util.concurrent.MoreExecutors;
import com.google.common.util.concurrent.SettableFuture;
import com.google.devtools.build.lib.skyframe.serialization.DeserializationContext;
import com.google.devtools.build.lib.skyframe.serialization.SerializationConstants;
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.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;
/**
* Supports association between fingerprints and NestedSet contents. A single NestedSetStore
* instance should be globally available across a single process.
*
*
Maintains the fingerprint -> contents side of the bimap by decomposing nested Object[]'s.
*
*
For example, suppose the NestedSet A can be drawn as:
*
*
* A
* / \
* B C
* / \
* D E
*
*
*
Then, in memory, A = [[D, E], C]. To store the NestedSet, we would rely on the fingerprint
* value FPb = fingerprint([D, E]) and write
*
*
A -> fingerprint(FPb, C)
*
*
On retrieval, A will be reconstructed by first retrieving A using its fingerprint, and then
* recursively retrieving B using its fingerprint.
*/
public class NestedSetStore {
/** Stores fingerprint -> NestedSet associations. */
public interface NestedSetStorageEndpoint {
/**
* Associates a fingerprint with the serialized representation of some NestedSet contents.
* Returns a future that completes when the write completes.
*
*
It is the responsibility of the caller to deduplicate {@code put} calls, to avoid multiple
* writes of the same fingerprint.
*/
ListenableFuture put(ByteString fingerprint, byte[] serializedBytes) throws IOException;
/**
* Retrieves the serialized bytes for the NestedSet contents associated with this fingerprint.
*
*
It is the responsibility of the caller to deduplicate {@code get} calls, to avoid multiple
* fetches of the same fingerprint.
*/
ListenableFuture get(ByteString fingerprint) throws IOException;
}
/** An in-memory {@link NestedSetStorageEndpoint} */
@VisibleForTesting
public static class InMemoryNestedSetStorageEndpoint implements NestedSetStorageEndpoint {
private final ConcurrentHashMap fingerprintToContents =
new ConcurrentHashMap<>();
@Override
public ListenableFuture put(ByteString fingerprint, byte[] serializedBytes) {
fingerprintToContents.put(fingerprint, serializedBytes);
return Futures.immediateFuture(null);
}
@Override
public ListenableFuture get(ByteString fingerprint) {
return Futures.immediateFuture(fingerprintToContents.get(fingerprint));
}
}
/** An in-memory cache for fingerprint <-> NestedSet associations. */
@VisibleForTesting
public static class NestedSetCache {
private final Cache> fingerprintToContents =
CacheBuilder.newBuilder()
.concurrencyLevel(SerializationConstants.DESERIALIZATION_POOL_SIZE)
.weakValues()
.build();
/** Object/Object[] contents to fingerprint. Maintained for fast fingerprinting. */
private final Cache