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);