Make UnionFileSystem accept all paths Bazel can throw at it.
Instead of relying on a character-by-character StringTrie, segment paths based on PathFragments. This means UnionFS can accept any path that Bazel stores internally, removing the ASCII limitations.
This also means removing the ability to have a filesystem bound for sub-PathFragments, /foo/barbar, /foo/barqux could have the same filesystem bound at /foo/bar. This feature was tested for when a use case was envisioned, but it was never used, so removing it is safe.
RELNOTES: None.
PiperOrigin-RevId: 170054656
diff --git a/src/main/java/com/google/devtools/build/lib/BUILD b/src/main/java/com/google/devtools/build/lib/BUILD
index 2f783f9..b8f6e9c 100644
--- a/src/main/java/com/google/devtools/build/lib/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/BUILD
@@ -94,7 +94,6 @@
name = "base-util",
srcs = [
"util/StringCanonicalizer.java",
- "util/StringTrie.java",
"util/VarInt.java",
],
deps = [
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java b/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
index b904e1d..2bbdb48 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/BlazeRuntime.java
@@ -808,7 +808,7 @@
}
}
- private static FileSystem fileSystemImplementation() {
+ private static FileSystem defaultFileSystemImplementation() {
if ("0".equals(System.getProperty("io.bazel.EnableJni"))) {
// Ignore UnixFileSystem, to be used for bootstrapping.
return OS.getCurrent() == OS.WINDOWS ? new WindowsFileSystem() : new JavaIoFileSystem();
@@ -943,7 +943,7 @@
}
if (fs == null) {
- fs = fileSystemImplementation();
+ fs = defaultFileSystemImplementation();
}
Path.setFileSystemForSerialization(fs);
diff --git a/src/main/java/com/google/devtools/build/lib/util/StringTrie.java b/src/main/java/com/google/devtools/build/lib/util/StringTrie.java
deleted file mode 100644
index 0b5d6e4..0000000
--- a/src/main/java/com/google/devtools/build/lib/util/StringTrie.java
+++ /dev/null
@@ -1,87 +0,0 @@
-// Copyright 2014 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.util;
-
-/**
- * A trie that operates on path segments of an input string instead of individual characters.
- *
- * <p>Only accepts strings that contain only low-ASCII characters (0-127)
- *
- * @param <T> the type of the values
- */
-public class StringTrie<T> {
- private static final int RANGE = 128;
-
- @SuppressWarnings("unchecked")
- private static class Node<T> {
- private Node() {
- children = new Node[RANGE];
- }
-
- private T value;
- private Node<T> children[];
- }
-
- private final Node<T> root;
-
- public StringTrie() {
- root = new Node<T>();
- }
-
- /**
- * Puts a value in the trie.
- */
- public void put(CharSequence key, T value) {
- Node<T> current = root;
-
- for (int i = 0; i < key.length(); i++) {
- char ch = key.charAt(i);
- Preconditions.checkState(ch < RANGE);
- Node<T> next = current.children[ch];
- if (next == null) {
- next = new Node<T>();
- current.children[ch] = next;
- }
-
- current = next;
- }
-
- current.value = value;
- }
-
- /**
- * Gets a value from the trie. If there is an entry with the same key, that will be returned,
- * otherwise, the value corresponding to the key that matches the longest prefix of the input.
- */
- public T get(String key) {
- Node<T> current = root;
- T lastValue = current.value;
-
- for (int i = 0; i < key.length(); i++) {
- char ch = key.charAt(i);
- Preconditions.checkState(ch < RANGE);
-
- current = current.children[ch];
- if (current == null) {
- break;
- }
-
- if (current.value != null) {
- lastValue = current.value;
- }
- }
-
- return lastValue;
- }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/PathFragment.java b/src/main/java/com/google/devtools/build/lib/vfs/PathFragment.java
index cc9aa19..c47a5f7 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/PathFragment.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/PathFragment.java
@@ -58,6 +58,9 @@
/** An empty path fragment. */
public static final PathFragment EMPTY_FRAGMENT = create("");
+ /** The path fragment representing the root directory. */
+ public static final PathFragment ROOT_FRAGMENT = create(ROOT_DIR);
+
/**
* A helper object for manipulating the various internal {@link PathFragment} implementations.
*
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/PathTrie.java b/src/main/java/com/google/devtools/build/lib/vfs/PathTrie.java
new file mode 100644
index 0000000..86bc226
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/vfs/PathTrie.java
@@ -0,0 +1,82 @@
+// Copyright 2014 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.vfs;
+
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
+import com.google.devtools.build.lib.util.Preconditions;
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * A trie that operates on path segments.
+ *
+ * @param <T> the type of the values.
+ */
+@ThreadCompatible
+public class PathTrie<T> {
+ @SuppressWarnings("unchecked")
+ private static class Node<T> {
+ private Node() {
+ children = new HashMap<>();
+ }
+
+ private T value;
+ private Map<String, Node<T>> children;
+ }
+
+ private final Node<T> root;
+
+ public PathTrie() {
+ root = new Node<T>();
+ }
+
+ /**
+ * Puts a value in the trie.
+ *
+ * @param key must be an absolute path.
+ */
+ public void put(PathFragment key, T value) {
+ Preconditions.checkArgument(key.isAbsolute(), "PathTrie only accepts absolute paths as keys.");
+ Node<T> current = root;
+ for (String segment : key.getSegments()) {
+ current.children.putIfAbsent(segment, new Node<T>());
+ current = current.children.get(segment);
+ }
+ current.value = value;
+ }
+
+ /**
+ * Gets a value from the trie. If there is an entry with the same key, that will be returned,
+ * otherwise, the value corresponding to the key that matches the longest prefix of the input.
+ */
+ public T get(PathFragment key) {
+ Node<T> current = root;
+ T lastValue = current.value;
+
+ for (String segment : key.getSegments()) {
+ if (current.children.containsKey(segment)) {
+ current = current.children.get(segment);
+ // Track the values of increasing matching prefixes.
+ if (current.value != null) {
+ lastValue = current.value;
+ }
+ } else {
+ // We've reached the longest prefix, no further to go.
+ break;
+ }
+ }
+
+ return lastValue;
+ }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/UnionFileSystem.java b/src/main/java/com/google/devtools/build/lib/vfs/UnionFileSystem.java
index d1d82d9..de65cf7 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/UnionFileSystem.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/UnionFileSystem.java
@@ -17,8 +17,6 @@
import com.google.common.collect.Lists;
import com.google.devtools.build.lib.concurrent.ThreadSafety;
import com.google.devtools.build.lib.util.Preconditions;
-import com.google.devtools.build.lib.util.StringTrie;
-import com.google.devtools.build.lib.vfs.FileSystem.HashFunction;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
@@ -28,21 +26,20 @@
/**
* Presents a unified view of multiple virtual {@link FileSystem} instances, to which requests are
- * delegated based on a {@link PathFragment} prefix mapping.
- * If multiple prefixes apply to a given path, the *longest* (i.e. most specific) match is used.
- * The order in which the delegates are specified does not influence the mapping.
+ * delegated based on a {@link PathFragment} prefix mapping. If multiple prefixes apply to a given
+ * path, the *longest* (i.e. most specific) match is used. The order in which the delegates are
+ * specified does not influence the mapping.
*
- * <p>Paths are preserved absolutely, contrary to how "mount" works, e.g.:
- * /foo/bar maps to /foo/bar on the delegate, even if it is mounted at /foo.
+ * <p>Paths are preserved absolutely, contrary to how "mount" works, e.g.: /foo/bar maps to /foo/bar
+ * on the delegate, even if it is mounted at /foo.
*
- * <p>For example:
- * "/in" maps to InFileSystem, "/" maps to OtherFileSystem.
- * Reading from "/in/base/BUILD" through the UnionFileSystem will delegate the read operation to
- * InFileSystem, which will read "/in/base/BUILD" relative to its root.
- * ("mount" behavior would remap it to "/base/BUILD" on the delegate).
+ * <p>For example: "/in" maps to InFileSystem, "/" maps to OtherFileSystem. Reading from
+ * "/in/base/BUILD" through the UnionFileSystem will delegate the read operation to InFileSystem,
+ * which will read "/in/base/BUILD" relative to its root. ("mount" behavior would remap it to
+ * "/base/BUILD" on the delegate).
*
- * <p>Intra-filesystem symbolic links are resolved to their ultimate targets.
- * Cross-filesystem links are not currently supported.
+ * <p>Intra-filesystem symbolic links are resolved to their ultimate targets. Cross-filesystem links
+ * are not currently supported.
*/
@ThreadSafety.ThreadSafe
public class UnionFileSystem extends FileSystem {
@@ -50,7 +47,7 @@
// Prefix trie index, allowing children to easily inherit prefix mappings
// of their parents.
// This does not currently handle unicode filenames.
- private StringTrie<FileSystem> pathDelegate;
+ private final PathTrie<FileSystem> pathDelegate;
// True iff the filesystem can be modified. If false, mutating operations
// will throw UnsupportedOperationExceptions.
@@ -61,37 +58,35 @@
private final boolean isCaseSensitive;
/**
- * Creates a new modifiable UnionFileSystem with prefix mappings
- * specified by a map.
+ * Creates a new modifiable UnionFileSystem with prefix mappings specified by a map.
*
* @param prefixMapping map of path prefixes to {@link FileSystem}s
*/
- public UnionFileSystem(Map<PathFragment, FileSystem> prefixMapping,
- FileSystem rootFileSystem) {
+ public UnionFileSystem(Map<PathFragment, FileSystem> prefixMapping, FileSystem rootFileSystem) {
this(prefixMapping, rootFileSystem, /* readOnly */ false);
}
/**
- * Creates a new modifiable or read-only UnionFileSystem with prefix mappings
- * specified by a map.
+ * Creates a new modifiable or read-only UnionFileSystem with prefix mappings specified by a map.
*
- * @param prefixMapping map of path prefixes to delegate {@link FileSystem}s
+ * @param prefixMapping map of path prefixes to delegate {@link FileSystem} instances to use for
+ * paths of that prefix. Note that all prefixes must be absolute paths.
* @param rootFileSystem root for default requests; i.e. mapping of "/"
* @param readOnly if true, mutating operations will throw
*/
- public UnionFileSystem(Map<PathFragment, FileSystem> prefixMapping,
- FileSystem rootFileSystem, boolean readOnly) {
+ public UnionFileSystem(
+ Map<PathFragment, FileSystem> prefixMapping, FileSystem rootFileSystem, boolean readOnly) {
super();
Preconditions.checkNotNull(prefixMapping);
Preconditions.checkNotNull(rootFileSystem);
Preconditions.checkArgument(rootFileSystem != this, "Circular root filesystem.");
Preconditions.checkArgument(
!prefixMapping.containsKey(PathFragment.EMPTY_FRAGMENT),
- "Attempted to specify an explicit root prefix mapping; " +
- "please use the rootFileSystem argument instead.");
+ "Attempted to specify an explicit root prefix mapping; "
+ + "please use the rootFileSystem argument instead.");
this.readOnly = readOnly;
- this.pathDelegate = new StringTrie<>();
+ this.pathDelegate = new PathTrie<>();
this.isCaseSensitive = rootFileSystem.isFilePathCaseSensitive();
for (Map.Entry<PathFragment, FileSystem> prefix : prefixMapping.entrySet()) {
@@ -102,29 +97,24 @@
PathFragment prefixPath = prefix.getKey();
// Extra slash prevents within-directory mappings, which Path can't handle.
- String path = prefixPath.getPathString();
- pathDelegate.put(path, delegate);
+ pathDelegate.put(prefixPath, delegate);
}
- pathDelegate.put(PathFragment.EMPTY_FRAGMENT.getPathString(), rootFileSystem);
+ pathDelegate.put(PathFragment.ROOT_FRAGMENT, rootFileSystem);
}
/**
- * Retrieves the filesystem delegate of a path mapping.
- * Does not follow symlinks (but you can call on a path preprocessed with
- * {@link #resolveSymbolicLinks} to support this use case).
+ * Retrieves the filesystem delegate of a path mapping. Does not follow symlinks (but you can call
+ * on a path preprocessed with {@link #resolveSymbolicLinks} to support this use case).
*
* @param path the {@link Path} to map to a filesystem
* @throws IllegalArgumentException if no delegate exists for the path
*/
protected FileSystem getDelegate(Path path) {
Preconditions.checkNotNull(path);
-
- String pathString = path.getPathString();
- FileSystem immediateDelegate = pathDelegate.get(pathString);
+ FileSystem immediateDelegate = pathDelegate.get(path.asFragment());
// Should never actually happen if the root delegate is present.
- Preconditions.checkArgument(immediateDelegate != null, "No delegate filesystem exists for %s",
- pathString);
+ Preconditions.checkNotNull(immediateDelegate, "No delegate filesystem exists for %s", path);
return immediateDelegate;
}
@@ -135,8 +125,8 @@
}
/**
- * Follow a symbolic link once using the appropriate delegate filesystem, also
- * resolving parent directory symlinks.
+ * Follow a symbolic link once using the appropriate delegate filesystem, also resolving parent
+ * directory symlinks.
*
* @param path {@link Path} to the symbolic link
*/
@@ -157,7 +147,7 @@
private void checkModifiable() {
if (!supportsModifications()) {
throw new UnsupportedOperationException(
- "Modifications to this " + getClass().getSimpleName() + " are disabled.");
+ String.format("Modifications to this %s are disabled.", getClass().getSimpleName()));
}
}
@@ -311,9 +301,8 @@
}
/**
- * Retrieves the directory entries for the specified path under the assumption
- * that {@code resolvedPath} is the resolved path of {@code path} in one of the
- * underlying file systems.
+ * Retrieves the directory entries for the specified path under the assumption that {@code
+ * resolvedPath} is the resolved path of {@code path} in one of the underlying file systems.
*
* @param path the {@link Path} whose children are to be retrieved
*/
@@ -409,16 +398,18 @@
FileSystem sourceDelegate = getDelegate(sourcePath);
if (!sourceDelegate.supportsModifications()) {
throw new UnsupportedOperationException(
- "The filesystem for the source path "
- + sourcePath.getPathString() + " does not support modifications.");
+ String.format(
+ "The filesystem for the source path %s does not support modifications.",
+ sourcePath.getPathString()));
}
sourcePath = adjustPath(sourcePath, sourceDelegate);
FileSystem targetDelegate = getDelegate(targetPath);
if (!targetDelegate.supportsModifications()) {
throw new UnsupportedOperationException(
- "The filesystem for the target path "
- + targetPath.getPathString() + " does not support modifications.");
+ String.format(
+ "The filesystem for the target path %s does not support modifications.",
+ targetPath.getPathString()));
}
targetPath = adjustPath(targetPath, targetDelegate);
@@ -435,8 +426,7 @@
}
@Override
- protected void createFSDependentHardLink(Path linkPath, Path originalPath)
- throws IOException {
+ protected void createFSDependentHardLink(Path linkPath, Path originalPath) throws IOException {
checkModifiable();
FileSystem originalDelegate = getDelegate(originalPath);
