// 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.common.base.Preconditions;
import com.google.common.collect.MapMaker;
import com.google.common.hash.Hashing;
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.Map;
import java.util.concurrent.ConcurrentHashMap;
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. */
interface NestedSetStorageEndpoint {
/** Associates a fingerprint with the serialized representation of some NestedSet contents. */
void put(ByteString fingerprint, byte[] serializedBytes);
/**
* Retrieves the serialized bytes for the NestedSet contents associated with this fingerprint.
*/
byte[] get(ByteString fingerprint);
}
/** An in-memory {@link NestedSetStorageEndpoint} */
private static class InMemoryNestedSetStorageEndpoint implements NestedSetStorageEndpoint {
private final ConcurrentHashMap fingerprintToContents =
new ConcurrentHashMap<>();
@Override
public void put(ByteString fingerprint, byte[] serializedBytes) {
fingerprintToContents.put(fingerprint, serializedBytes);
}
@Override
public byte[] get(ByteString fingerprint) {
return fingerprintToContents.get(fingerprint);
}
}
/** An in-memory cache for fingerprint <-> NestedSet associations. */
private static class NestedSetCache {
private final Map fingerprintToContents =
new MapMaker()
.concurrencyLevel(SerializationConstants.DESERIALIZATION_POOL_SIZE)
.weakValues()
.makeMap();
/** Object/Object[] contents to fingerprint. Maintained for fast fingerprinting. */
private final Map