Allows {@link FileArtifactValue} lookups by exec path or {@link ActionInput}. Also * allows {@link ActionInput} to be looked up by exec path. * *
This class implements a closed hash-map with the "links" of each bucket's linked list being * stored in a flat array to avoid memory allocations and garbage collection. * *
This class is thread-compatible.
*/
public final class ActionInputMap implements InputMetadataProvider, ActionInputMapSink {
private static final Object PLACEHOLDER = new Object();
static class TrieArtifact {
private Map This method is less efficient than {@link #getMetadata(ActionInput)}, please use it instead
* of this one when looking up {@linkplain ActionInput action inputs}.
*/
@Nullable
public FileArtifactValue getMetadata(PathFragment execPath) {
int index = getIndex(execPath.getPathString());
if (index != -1) {
Object value = values[index];
return (value instanceof TrieArtifact)
? ((TrieArtifact) value).treeArtifactValue.getMetadata()
: (FileArtifactValue) value;
}
// Fall back to searching the tree artifacts.
return getMetadataFromTreeArtifacts(execPath);
}
@Nullable
private FileArtifactValue getMetadataFromTreeArtifacts(PathFragment execPath) {
TreeArtifactValue tree = treeArtifactsRoot.findTreeArtifactNodeAtPrefix(execPath);
if (tree == null) {
return null;
}
Map.Entry entry = tree.findChildEntryByExecPath(execPath);
return entry != null ? entry.getValue() : null;
}
/**
* Returns the {@link TreeArtifactValue} for the given path, or {@code null} if no such tree
* artifact exists.
*/
@Nullable
public TreeArtifactValue getTreeMetadata(PathFragment execPath) {
int index = getIndex(execPath.getPathString());
if (index < 0) {
return null;
}
Object value = values[index];
if (!(value instanceof TrieArtifact)) {
return null;
}
return ((TrieArtifact) value).treeArtifactValue;
}
/**
* Returns the {@link TreeArtifactValue} for the shortest prefix of the given path, possibly the
* path itself, that corresponds to a tree artifact; or {@code null} if no such tree artifact
* exists.
*/
@Nullable
public TreeArtifactValue getTreeMetadataForPrefix(PathFragment execPath) {
return treeArtifactsRoot.findTreeArtifactNodeAtPrefix(execPath);
}
@Nullable
@Override
public ActionInput getInput(String execPathString) {
int index = getIndex(execPathString);
if (index != -1) {
return (ActionInput) keys[index];
}
// Search ancestor paths since execPathString may point to a TreeFileArtifact within one of the
// tree artifacts.
PathFragment execPath = PathFragment.create(execPathString);
TreeArtifactValue tree = treeArtifactsRoot.findTreeArtifactNodeAtPrefix(execPath);
if (tree == null) {
return null;
}
// We must return an entry from the map since a duplicate would not have the generating action
// key set.
Map.Entry Top-level means that each tree artifact, counts as 1, irrespective of the number of children
* it has. Same goes for nested trees/files.
*/
public int sizeForDebugging() {
return size;
}
@Override
public boolean put(ActionInput input, FileArtifactValue metadata, @Nullable Artifact depOwner) {
return putWithNoDepOwner(input, metadata);
}
@Override
public void putTreeArtifact(
SpecialArtifact tree, TreeArtifactValue treeArtifactValue, @Nullable Artifact depOwner) {
// Use a placeholder value so that we don't have to create a new trie entry if the entry is
// already in the map.
int oldIndex = putIfAbsent(tree, PLACEHOLDER);
if (oldIndex != -1) {
checkArgument(
isATreeArtifact((ActionInput) keys[oldIndex]),
"Tried to overwrite file with a tree artifact: '%s' with the same exec path",
tree);
return;
}
// Overwrite the placeholder.
values[size - 1] =
treeArtifactValue.equals(TreeArtifactValue.OMITTED_TREE_MARKER)
// No trie entry for omitted tree -- it cannot have any children anyway.
? FileArtifactValue.OMITTED_FILE_MARKER
: treeArtifactsRoot.add(tree.getExecPath(), treeArtifactValue);
}
public boolean putWithNoDepOwner(ActionInput input, FileArtifactValue metadata) {
checkArgument(
!isATreeArtifact(input),
"Can't add tree artifact: %s using put -- please use putTreeArtifact for that",
input);
int oldIndex = putIfAbsent(input, metadata);
checkArgument(
oldIndex == -1 || !isATreeArtifact((ActionInput) keys[oldIndex]),
"Tried to overwrite tree artifact with a file: '%s' with the same exec path",
input);
return oldIndex == -1;
}
private int putIfAbsent(ActionInput input, Object metadata) {
Preconditions.checkNotNull(input);
if (size >= keys.length) {
resize();
}
String path = input.getExecPathString();
int hashCode = path.hashCode();
int index = hashCode & (table.length - 1);
int nextIndex = table[index];
if (nextIndex == -1) {
table[index] = size;
} else {
do {
index = nextIndex;
if (hashCode == paths[index].hashCode() && Objects.equal(path, paths[index])) {
return index;
}
nextIndex = next[index];
} while (nextIndex != -1);
next[index] = size;
}
next[size] = -1;
keys[size] = input;
paths[size] = input.getExecPathString();
values[size] = metadata;
size++;
return -1;
}
@VisibleForTesting
void clear() {
Arrays.fill(table, -1);
Arrays.fill(next, -1);
Arrays.fill(keys, null);
Arrays.fill(paths, null);
Arrays.fill(values, null);
size = 0;
treeArtifactsRoot = new TrieArtifact();
}
private void resize() {
// Resize the data containers.
keys = Arrays.copyOf(keys, size * 2);
paths = Arrays.copyOf(paths, size * 2);
values = Arrays.copyOf(values, size * 2);
next = Arrays.copyOf(next, size * 2);
// Resize and recreate the table and links if necessary. We can take shortcuts here as we know
// there are no duplicate keys.
if (table.length < size * 2) {
table = new int[table.length * 2];
next = new int[size * 2];
Arrays.fill(table, -1);
for (int i = 0; i < size; i++) {
int index = paths[i].hashCode() & (table.length - 1);
next[i] = table[index];
table[index] = i;
}
}
}
@Override
public String toString() {
return MoreObjects.toStringHelper(this)
.add("size", size)
.add("all-files", sizeForDebugging())
.add("first-fifty-keys", Arrays.stream(keys).limit(50).collect(toList()))
.add("first-fifty-values", Arrays.stream(values).limit(50).collect(toList()))
.add("first-fifty-paths", Arrays.stream(paths).limit(50).collect(toList()))
.toString();
}
private static boolean isATreeArtifact(ActionInput input) {
return input instanceof SpecialArtifact && ((SpecialArtifact) input).isTreeArtifact();
}
}