diff options
Diffstat (limited to 'jimfs/src/main/java/com/google/common/jimfs/FileTree.java')
-rw-r--r-- | jimfs/src/main/java/com/google/common/jimfs/FileTree.java | 221 |
1 files changed, 221 insertions, 0 deletions
diff --git a/jimfs/src/main/java/com/google/common/jimfs/FileTree.java b/jimfs/src/main/java/com/google/common/jimfs/FileTree.java new file mode 100644 index 0000000..c480942 --- /dev/null +++ b/jimfs/src/main/java/com/google/common/jimfs/FileTree.java @@ -0,0 +1,221 @@ +/* + * Copyright 2013 Google Inc. + * + * 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.common.jimfs; + +import static com.google.common.base.Preconditions.checkNotNull; + +import com.google.common.collect.ImmutableList; +import com.google.common.collect.ImmutableSortedMap; +import com.google.common.collect.ImmutableSortedSet; +import java.io.IOException; +import java.nio.file.LinkOption; +import java.nio.file.NoSuchFileException; +import java.util.Iterator; +import java.util.Map; +import java.util.Set; +import org.checkerframework.checker.nullness.compatqual.NullableDecl; + +/** + * The tree of directories and files for the file system. Contains the file system root directories + * and provides the ability to look up files by path. One piece of the file store implementation. + * + * @author Colin Decker + */ +final class FileTree { + + /** + * Doesn't much matter, but this number comes from MIN_ELOOP_THRESHOLD <a + * href="https://sourceware.org/git/gitweb.cgi?p=glibc.git;a=blob_plain;f=sysdeps/generic/eloop-threshold.h;hb=HEAD"> + * here</a> + */ + private static final int MAX_SYMBOLIC_LINK_DEPTH = 40; + + private static final ImmutableList<Name> EMPTY_PATH_NAMES = ImmutableList.of(Name.SELF); + + /** Map of root names to root directories. */ + private final ImmutableSortedMap<Name, Directory> roots; + + /** Creates a new file tree with the given root directories. */ + FileTree(Map<Name, Directory> roots) { + this.roots = ImmutableSortedMap.copyOf(roots, Name.canonicalOrdering()); + } + + /** Returns the names of the root directories in this tree. */ + public ImmutableSortedSet<Name> getRootDirectoryNames() { + return roots.keySet(); + } + + /** + * Gets the directory entry for the root with the given name or {@code null} if no such root + * exists. + */ + @NullableDecl + public DirectoryEntry getRoot(Name name) { + Directory dir = roots.get(name); + return dir == null ? null : dir.entryInParent(); + } + + /** Returns the result of the file lookup for the given path. */ + public DirectoryEntry lookUp( + File workingDirectory, JimfsPath path, Set<? super LinkOption> options) throws IOException { + checkNotNull(path); + checkNotNull(options); + + DirectoryEntry result = lookUp(workingDirectory, path, options, 0); + if (result == null) { + // an intermediate file in the path did not exist or was not a directory + throw new NoSuchFileException(path.toString()); + } + return result; + } + + @NullableDecl + private DirectoryEntry lookUp( + File dir, JimfsPath path, Set<? super LinkOption> options, int linkDepth) throws IOException { + ImmutableList<Name> names = path.names(); + + if (path.isAbsolute()) { + // look up the root directory + DirectoryEntry entry = getRoot(path.root()); + if (entry == null) { + // root not found; always return null as no real parent directory exists + // this prevents new roots from being created in file systems supporting multiple roots + return null; + } else if (names.isEmpty()) { + // root found, no more names to look up + return entry; + } else { + // root found, more names to look up; set dir to the root directory for the path + dir = entry.file(); + } + } else if (isEmpty(names)) { + // set names to the canonical list of names for an empty path (singleton list of ".") + names = EMPTY_PATH_NAMES; + } + + return lookUp(dir, names, options, linkDepth); + } + + /** + * Looks up the given names against the given base file. If the file is not a directory, the + * lookup fails. + */ + @NullableDecl + private DirectoryEntry lookUp( + File dir, Iterable<Name> names, Set<? super LinkOption> options, int linkDepth) + throws IOException { + Iterator<Name> nameIterator = names.iterator(); + Name name = nameIterator.next(); + while (nameIterator.hasNext()) { + Directory directory = toDirectory(dir); + if (directory == null) { + return null; + } + + DirectoryEntry entry = directory.get(name); + if (entry == null) { + return null; + } + + File file = entry.file(); + if (file.isSymbolicLink()) { + DirectoryEntry linkResult = followSymbolicLink(dir, (SymbolicLink) file, linkDepth); + + if (linkResult == null) { + return null; + } + + dir = linkResult.fileOrNull(); + } else { + dir = file; + } + + name = nameIterator.next(); + } + + return lookUpLast(dir, name, options, linkDepth); + } + + /** Looks up the last element of a path. */ + @NullableDecl + private DirectoryEntry lookUpLast( + @NullableDecl File dir, Name name, Set<? super LinkOption> options, int linkDepth) + throws IOException { + Directory directory = toDirectory(dir); + if (directory == null) { + return null; + } + + DirectoryEntry entry = directory.get(name); + if (entry == null) { + return new DirectoryEntry(directory, name, null); + } + + File file = entry.file(); + if (!options.contains(LinkOption.NOFOLLOW_LINKS) && file.isSymbolicLink()) { + return followSymbolicLink(dir, (SymbolicLink) file, linkDepth); + } + + return getRealEntry(entry); + } + + /** + * Returns the directory entry located by the target path of the given symbolic link, resolved + * relative to the given directory. + */ + @NullableDecl + private DirectoryEntry followSymbolicLink(File dir, SymbolicLink link, int linkDepth) + throws IOException { + if (linkDepth >= MAX_SYMBOLIC_LINK_DEPTH) { + throw new IOException("too many levels of symbolic links"); + } + + return lookUp(dir, link.target(), Options.FOLLOW_LINKS, linkDepth + 1); + } + + /** + * Returns the entry for the file in its parent directory. This will be the given entry unless the + * name for the entry is "." or "..", in which the directory linking to the file is not the file's + * parent directory. In that case, we know the file must be a directory ("." and ".." can only + * link to directories), so we can just get the entry in the directory's parent directory that + * links to it. So, for example, if we have a directory "foo" that contains a directory "bar" and + * we find an entry [bar -> "." -> bar], we instead return the entry for bar in its parent, [foo + * -> "bar" -> bar]. + */ + @NullableDecl + private DirectoryEntry getRealEntry(DirectoryEntry entry) { + Name name = entry.name(); + + if (name.equals(Name.SELF) || name.equals(Name.PARENT)) { + Directory dir = toDirectory(entry.file()); + assert dir != null; + return dir.entryInParent(); + } else { + return entry; + } + } + + @NullableDecl + private Directory toDirectory(@NullableDecl File file) { + return file == null || !file.isDirectory() ? null : (Directory) file; + } + + private static boolean isEmpty(ImmutableList<Name> names) { + // the empty path (created by FileSystem.getPath("")), has no root and a single name, "" + return names.isEmpty() || (names.size() == 1 && names.get(0).toString().isEmpty()); + } +} |