Sort DirectoryNode children to ensure validity.
InputTree will create DirectoryNodes with non-sequential additions of
directory children. These must be maintained in order for representation
within remote Directory messages (and to properly compute action keys).
Co-Author=buchgr
Closes #8008.
PiperOrigin-RevId: 243235156
diff --git a/src/main/java/com/google/devtools/build/lib/remote/merkletree/InputTree.java b/src/main/java/com/google/devtools/build/lib/remote/merkletree/InputTree.java
index 9e1c7aa..749ab27 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/merkletree/InputTree.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/merkletree/InputTree.java
@@ -16,6 +16,7 @@
import build.bazel.remote.execution.v2.Digest;
import com.google.common.base.Preconditions;
import com.google.common.base.Strings;
+import com.google.common.collect.Sets;
import com.google.devtools.build.lib.actions.ActionInput;
import com.google.devtools.build.lib.actions.ActionInputHelper;
import com.google.devtools.build.lib.actions.FileArtifactValue;
@@ -34,6 +35,7 @@
import java.util.Map;
import java.util.Objects;
import java.util.SortedMap;
+import java.util.SortedSet;
import java.util.TreeMap;
/**
@@ -46,7 +48,7 @@
void visitDirectory(PathFragment dirname, List<FileNode> files, List<DirectoryNode> dirs);
}
- abstract static class Node {
+ abstract static class Node implements Comparable<Node> {
private final String pathSegment;
Node(String pathSegment) {
@@ -58,6 +60,11 @@
}
@Override
+ public int compareTo(Node other) {
+ return pathSegment.compareTo(other.pathSegment);
+ }
+
+ @Override
public int hashCode() {
return pathSegment.hashCode();
}
@@ -108,7 +115,7 @@
}
static class DirectoryNode extends Node {
- private final List<Node> children = new ArrayList<>();
+ private final SortedSet<Node> children = Sets.newTreeSet();
DirectoryNode(String pathSegment) {
super(pathSegment);
diff --git a/src/test/java/com/google/devtools/build/lib/remote/merkletree/InputTreeTest.java b/src/test/java/com/google/devtools/build/lib/remote/merkletree/InputTreeTest.java
index bed2b4b..5f7663a 100644
--- a/src/test/java/com/google/devtools/build/lib/remote/merkletree/InputTreeTest.java
+++ b/src/test/java/com/google/devtools/build/lib/remote/merkletree/InputTreeTest.java
@@ -169,6 +169,30 @@
assertThat(fileNodesAtDepth(tree, 3)).containsExactly(expectedBuzzNode);
}
+ @Test
+ public void testLexicographicalOrder() throws Exception {
+ // Regression test for https://github.com/bazelbuild/bazel/pull/8008
+ //
+ // The issue was that before #8008 we wrongly assumed that a sorted full list of inputs would
+ // also lead to sorted tree nodes. Thereby not taking into account that the path separator '/'
+ // influences the sorting of the full list but not that of the tree nodes as its stripped there.
+ // For example, the below full list is lexicographically sorted
+ // srcs/system-root/bar.txt
+ // srcs/system/foo.txt
+ //
+ // However, the tree node [system-root, system] is not (note the missing / suffix).
+
+ SortedMap<PathFragment, ActionInput> sortedInputs = new TreeMap<>();
+ Map<ActionInput, FileArtifactValue> metadata = new HashMap<>();
+
+ addFile("srcs/system/foo.txt", "foo", sortedInputs, metadata);
+ addFile("srcs/system-root/bar.txt", "bar", sortedInputs, metadata);
+
+ InputTree tree =
+ InputTree.build(sortedInputs, new StaticMetadataProvider(metadata), execRoot, digestUtil);
+ assertLexicographicalOrder(tree);
+ }
+
private Artifact addFile(
String path,
String content,
@@ -193,28 +217,18 @@
}
private static void assertLexicographicalOrder(InputTree tree) {
- int depth = 0;
- while (true) {
- // String::compareTo implements lexicographical order
- List<String> files = filesAtDepth(depth, tree);
- assertThat(files).isStrictlyOrdered();
- List<String> directories = directoriesAtDepth(depth, tree);
- assertThat(directories).isStrictlyOrdered();
- if (directories.isEmpty()) {
- break;
- }
- depth++;
- }
+ // Assert the lexicographical order as defined by the remote execution protocol
+ tree.visit(
+ (PathFragment dirname, List<FileNode> files, List<DirectoryNode> dirs) -> {
+ assertThat(files).isStrictlyOrdered();
+ assertThat(dirs).isStrictlyOrdered();
+ });
}
private static List<String> directoriesAtDepth(int depth, InputTree tree) {
return asPathSegments(directoryNodesAtDepth(tree, depth));
}
- private static List<String> filesAtDepth(int depth, InputTree tree) {
- return asPathSegments(fileNodesAtDepth(tree, depth));
- }
-
private static List<String> asPathSegments(List<? extends Node> nodes) {
return nodes.stream().map(Node::getPathSegment).collect(Collectors.toList());
}
