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());
+  }
+}