Replace path implementation.

Path and PathFragment have been replaced with String-based implementations. They are pretty similar, but each method is dissimilar enough that I did not feel sharing code was appropriate.

A summary of changes:

PATH
====

* Subsumes LocalPath (deleted, its tests repurposed)
* Use a simple string to back Path
* Path instances are no longer interned; Reference equality will no longer work
* Always normalized (same as before)
* Some operations will now be slower, like instance compares (which were previously just a reference check)
* Multiple identical paths will now consume more memory since they are not interned

PATH FRAGMENT
=============

* Use a simple string to back PathFragment
* No more segment arrays with interned strings
* Always normalized
* Remove isNormalized
* Replace some isNormalizied uses with containsUpLevelReferences() to check if path fragments try to escape their scope
* To check if user input is normalized, supply static methods on PathFragment to validate the string before constructing a PathFragment
* Because PathFragments are always normalized, we have to replace checks for literal "." from PathFragment#getPathString to PathFragment#getSafePathString. The latter returns "." for the empty string.
* The previous implementation supported efficient segment semantics (segment count, iterating over segments). This is now expensive since we do longer have a segment array.

ARTIFACT
========

* Remove Path instance. It is instead dynamically constructed on request. This is necessary to avoid this CL becoming a memory regression.

RELNOTES: None
PiperOrigin-RevId: 185062932

19 files changed, 1388 insertions, 2575 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/vfs/BUILD b/src/main/java/com/google/devtools/build/lib/vfs/BUILD
index f7a57bee03..b829858847 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/vfs/BUILD
@@ -10,8 +10,9 @@ PATH_FRAGMENT_SOURCES = [
     "Canonicalizer.java",
     "PathFragment.java",
     "PathFragmentSerializationProxy.java",
-    "UnixPathFragment.java",
-    "WindowsPathFragment.java",
+    "OsPathPolicy.java",
+    "UnixOsPathPolicy.java",
+    "WindowsOsPathPolicy.java",
 ]
 
 java_library(
@@ -25,6 +26,8 @@ java_library(
         "//src/main/java/com/google/devtools/build/lib:skylarkinterface",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization",
+        "//src/main/java/com/google/devtools/build/lib/windows:windows_short_path",
+        "//src/main/java/com/google/devtools/build/lib/windows/jni",
         "//third_party:guava",
         "//third_party/protobuf:protobuf_java",
     ],
@@ -47,7 +50,6 @@ java_library(
         ":pathfragment",
         "//src/main/java/com/google/devtools/build/lib:base-util",
         "//src/main/java/com/google/devtools/build/lib:filetype",
-        "//src/main/java/com/google/devtools/build/lib:os_util",
         "//src/main/java/com/google/devtools/build/lib:skylarkinterface",
         "//src/main/java/com/google/devtools/build/lib/clock",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
@@ -55,8 +57,6 @@ java_library(
         "//src/main/java/com/google/devtools/build/lib/shell",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
-        "//src/main/java/com/google/devtools/build/lib/windows:windows_short_path",
-        "//src/main/java/com/google/devtools/build/lib/windows/jni",
         "//src/main/java/com/google/devtools/common/options",
         "//third_party:guava",
         "//third_party:jsr305",
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/FileSystem.java b/src/main/java/com/google/devtools/build/lib/vfs/FileSystem.java
index aaaacd93d2..38da81c6d9 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/FileSystem.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/FileSystem.java
@@ -23,7 +23,6 @@ import com.google.common.io.ByteSource;
 import com.google.common.io.CharStreams;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.vfs.Dirent.Type;
-import com.google.devtools.build.lib.vfs.Path.PathFactory;
 import com.google.devtools.common.options.EnumConverter;
 import java.io.FileNotFoundException;
 import java.io.IOException;
@@ -84,25 +83,6 @@ public abstract class FileSystem {
     return digestFunction;
   }
 
-  private enum UnixPathFactory implements PathFactory {
-    INSTANCE {
-      @Override
-      public Path createRootPath(FileSystem filesystem) {
-        return new Path(filesystem, PathFragment.ROOT_DIR, null);
-      }
-
-      @Override
-      public Path createChildPath(Path parent, String childName) {
-        return new Path(parent.getFileSystem(), childName, parent);
-      }
-
-      @Override
-      public Path getCachedChildPathInternal(Path path, String childName) {
-        return Path.getCachedChildPathInternal(path, childName, /*cacheable=*/ true);
-      }
-    };
-  }
-
   /**
    * An exception thrown when attempting to resolve an ordinary file as a symlink.
    */
@@ -112,53 +92,23 @@ public abstract class FileSystem {
     }
   }
 
-  /** Lazy-initialized on first access, always use {@link FileSystem#getRootDirectory} */
-  private volatile Path rootPath;
-
   private final Root absoluteRoot = new Root.AbsoluteRoot(this);
 
-  /** Returns filesystem-specific path factory. */
-  protected PathFactory getPathFactory() {
-    return UnixPathFactory.INSTANCE;
-  }
-
-  /**
-   * Returns an absolute path instance, given an absolute path name, without
-   * double slashes, .., or . segments. While this method will normalize the
-   * path representation by creating a structured/parsed representation, it will
-   * not cause any IO. (e.g., it will not resolve symbolic links if it's a Unix
-   * file system.
-   */
-  public Path getPath(String pathName) {
-    return getPath(PathFragment.create(pathName));
-  }
-
   /**
-   * Returns an absolute path instance, given an absolute path name, without
-   * double slashes, .., or . segments. While this method will normalize the
-   * path representation by creating a structured/parsed representation, it will
-   * not cause any IO. (e.g., it will not resolve symbolic links if it's a Unix
-   * file system.
+   * Returns an absolute path instance, given an absolute path name, without double slashes, .., or
+   * . segments. While this method will normalize the path representation by creating a
+   * structured/parsed representation, it will not cause any IO. (e.g., it will not resolve symbolic
+   * links if it's a Unix file system.
    */
-  public Path getPath(PathFragment pathName) {
-    if (!pathName.isAbsolute()) {
-      throw new IllegalArgumentException(pathName.getPathString()  + " (not an absolute path)");
-    }
-    return getRootDirectory().getRelative(pathName);
+  public Path getPath(String path) {
+    return Path.create(path, this);
   }
 
-  /**
-   * Returns a path representing the root directory of the current file system.
-   */
-  public final Path getRootDirectory() {
-    if (rootPath == null) {
-      synchronized (this) {
-        if (rootPath == null) {
-          rootPath = getPathFactory().createRootPath(this);
-        }
-      }
-    }
-    return rootPath;
+  /** Returns an absolute path instance, given an absolute path fragment. */
+  public Path getPath(PathFragment pathFragment) {
+    Preconditions.checkArgument(pathFragment.isAbsolute());
+    return Path.createAlreadyNormalized(
+        pathFragment.getPathString(), pathFragment.getDriveStrLength(), this);
   }
 
   final Root getAbsoluteRoot() {
@@ -401,7 +351,7 @@ public abstract class FileSystem {
       throw new IOException(naive + " (Too many levels of symbolic links)");
     }
     if (linkTarget.isAbsolute()) {
-      dir = getRootDirectory();
+      dir = getPath(linkTarget.getDriveStr());
     }
     for (String name : linkTarget.segments()) {
       if (name.equals(".") || name.isEmpty()) {
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/FileSystemUtils.java b/src/main/java/com/google/devtools/build/lib/vfs/FileSystemUtils.java
index adeb9c847c..b7fd8d2a43 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/FileSystemUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/FileSystemUtils.java
@@ -25,7 +25,6 @@ import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import java.io.IOException;
 import java.io.InputStream;
 import java.io.OutputStream;
-import java.io.PrintStream;
 import java.nio.charset.Charset;
 import java.util.ArrayList;
 import java.util.Arrays;
@@ -90,25 +89,13 @@ public class FileSystemUtils {
 
     return a;
   }
-  /**
-   * Returns a path fragment from a given from-dir to a given to-path. May be
-   * either a short relative path "foo/bar", an up'n'over relative path
-   * "../../foo/bar" or an absolute path.
-   */
-  public static PathFragment relativePath(Path fromDir, Path to) {
-    if (to.getFileSystem() != fromDir.getFileSystem()) {
-      throw new IllegalArgumentException("fromDir and to must be on the same FileSystem");
-    }
-
-    return relativePath(fromDir.asFragment(), to.asFragment());
-  }
 
   /**
    * Returns a path fragment from a given from-dir to a given to-path.
    */
   public static PathFragment relativePath(PathFragment fromDir, PathFragment to) {
     if (to.equals(fromDir)) {
-      return PathFragment.create(".");  // same dir, just return '.'
+      return PathFragment.EMPTY_FRAGMENT;
     }
     if (to.startsWith(fromDir)) {
       return to.relativeTo(fromDir);  // easy case--it's a descendant
@@ -883,30 +870,6 @@ public class FileSystemUtils {
   }
 
   /**
-   * Dumps diagnostic information about the specified filesystem to {@code out}.
-   * This is the implementation of the filesystem part of the 'blaze dump'
-   * command. It lives here, rather than in DumpCommand, because it requires
-   * privileged access to members of this package.
-   *
-   * <p>Its results are unspecified and MUST NOT be interpreted programmatically.
-   */
-  public static void dump(FileSystem fs, final PrintStream out) {
-    // Unfortunately there's no "letrec" for anonymous functions so we have to
-    // (a) name the function, (b) put it in a box and (c) use List not array
-    // because of the generic type.  *sigh*.
-    final List<Predicate<Path>> dumpFunction = new ArrayList<>();
-    dumpFunction.add(
-        child -> {
-          Path path = child;
-          out.println("  " + path + " (" + path.toDebugString() + ")");
-          path.applyToChildren(dumpFunction.get(0));
-          return false;
-        });
-
-    fs.getRootDirectory().applyToChildren(dumpFunction.get(0));
-  }
-
-  /**
    * Returns the type of the file system path belongs to.
    */
   public static String getFileSystem(Path path) {
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/JavaIoFileSystem.java b/src/main/java/com/google/devtools/build/lib/vfs/JavaIoFileSystem.java
index 5bba53533f..f5b0220e32 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/JavaIoFileSystem.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/JavaIoFileSystem.java
@@ -281,7 +281,7 @@ public class JavaIoFileSystem extends AbstractFileSystemWithCustomStat {
       throws IOException {
     java.nio.file.Path nioPath = getNioPath(linkPath);
     try {
-      Files.createSymbolicLink(nioPath, Paths.get(targetFragment.getPathString()));
+      Files.createSymbolicLink(nioPath, Paths.get(targetFragment.getSafePathString()));
     } catch (java.nio.file.FileAlreadyExistsException e) {
       throw new IOException(linkPath + ERR_FILE_EXISTS);
     } catch (java.nio.file.AccessDeniedException e) {
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/LocalPath.java b/src/main/java/com/google/devtools/build/lib/vfs/LocalPath.java
deleted file mode 100644
index a32a4e356c..0000000000
--- a/src/main/java/com/google/devtools/build/lib/vfs/LocalPath.java
+++ /dev/null
@@ -1,715 +0,0 @@
-// Copyright 2017 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.common.annotations.VisibleForTesting;
-import com.google.common.base.Preconditions;
-import com.google.devtools.build.lib.util.OS;
-import com.google.devtools.build.lib.windows.WindowsShortPath;
-import com.google.devtools.build.lib.windows.jni.WindowsFileOperations;
-import java.io.IOException;
-import java.util.Arrays;
-import java.util.concurrent.atomic.AtomicReference;
-import javax.annotation.Nullable;
-
-/**
- * A local file path representing a file on the host machine. You should use this when you want to
- * access local files via the file system.
- *
- * <p>Paths are either absolute or relative.
- *
- * <p>Strings are normalized with '.' and '..' removed and resolved (if possible), any multiple
- * slashes ('/') removed, and any trailing slash also removed. The current implementation does not
- * touch the incoming path string unless the string actually needs to be normalized.
- *
- * <p>There is some limited support for Windows-style paths. Most importantly, drive identifiers in
- * front of a path (c:/abc) are supported and such paths are correctly recognized as absolute, as
- * are paths with backslash separators (C:\\foo\\bar). However, advanced Windows-style features like
- * \\\\network\\paths and \\\\?\\unc\\paths are not supported. We are currently using forward
- * slashes ('/') even on Windows, so backslashes '\' get converted to forward slashes during
- * normalization.
- *
- * <p>Mac and Windows file paths are case insensitive. Case is preserved.
- *
- * <p>This class is replaces {@link Path} as the way to access the host machine's file system.
- * Developers should use this class instead of {@link Path}.
- */
-public final class LocalPath implements Comparable<LocalPath> {
-  private static final OsPathPolicy DEFAULT_OS = createFilePathOs();
-
-  public static final LocalPath EMPTY = create("");
-
-  private final String path;
-  private final int driveStrLength; // 0 for relative paths, 1 on Unix, 3 on Windows
-  private final OsPathPolicy os;
-
-  /** Creates a local path that is specific to the host OS. */
-  public static LocalPath create(String path) {
-    return createWithOs(path, DEFAULT_OS);
-  }
-
-  @VisibleForTesting
-  static LocalPath createWithOs(String path, OsPathPolicy os) {
-    Preconditions.checkNotNull(path);
-    int normalizationLevel = os.needsToNormalize(path);
-    String normalizedPath = os.normalize(path, normalizationLevel);
-    int driveStrLength = os.getDriveStrLength(normalizedPath);
-    return new LocalPath(normalizedPath, driveStrLength, os);
-  }
-
-  /** This method expects path to already be normalized. */
-  private LocalPath(String path, int driveStrLength, OsPathPolicy os) {
-    this.path = Preconditions.checkNotNull(path);
-    this.driveStrLength = driveStrLength;
-    this.os = Preconditions.checkNotNull(os);
-  }
-
-  public String getPathString() {
-    return path;
-  }
-
-  /**
-   * If called on a {@link LocalPath} instance for a mount name (eg. '/' or 'C:/'), the empty string
-   * is returned.
-   */
-  public String getBaseName() {
-    int lastSeparator = path.lastIndexOf(os.getSeparator());
-    return lastSeparator < driveStrLength
-        ? path.substring(driveStrLength)
-        : path.substring(lastSeparator + 1);
-  }
-
-  /**
-   * Returns a {@link LocalPath} instance representing the relative path between this {@link
-   * LocalPath} and the given {@link LocalPath}.
-   *
-   * <pre>
-   *   Example:
-   *
-   *   LocalPath.create("/foo").getRelative(LocalPath.create("bar/baz"))
-   *   -> "/foo/bar/baz"
-   * </pre>
-   *
-   * <p>If the passed path is absolute it is returned untouched. This can be useful to resolve
-   * symlinks.
-   */
-  public LocalPath getRelative(LocalPath other) {
-    Preconditions.checkNotNull(other);
-    Preconditions.checkArgument(os == other.os);
-    return getRelative(other.getPathString(), other.driveStrLength);
-  }
-
-  /**
-   * Returns a {@link LocalPath} instance representing the relative path between this {@link
-   * LocalPath} and the given path.
-   *
-   * <p>See {@link #getRelative(LocalPath)} for details.
-   */
-  public LocalPath getRelative(String other) {
-    Preconditions.checkNotNull(other);
-    return getRelative(other, os.getDriveStrLength(other));
-  }
-
-  private LocalPath getRelative(String other, int otherDriveStrLength) {
-    if (path.isEmpty()) {
-      return create(other);
-    }
-    if (other.isEmpty()) {
-      return this;
-    }
-    // Note that even if other came from a LocalPath instance we still might
-    // need to normalize the result if (for instance) other is a path that
-    // starts with '..'
-    int normalizationLevel = os.needsToNormalize(other);
-    // This is an absolute path, simply return it
-    if (otherDriveStrLength > 0) {
-      String normalizedPath = os.normalize(other, normalizationLevel);
-      return new LocalPath(normalizedPath, otherDriveStrLength, os);
-    }
-    String newPath;
-    if (path.length() == driveStrLength) {
-      newPath = path + other;
-    } else {
-      newPath = path + '/' + other;
-    }
-    newPath = os.normalize(newPath, normalizationLevel);
-    return new LocalPath(newPath, driveStrLength, os);
-  }
-
-  /**
-   * Returns the parent directory of this {@link LocalPath}.
-   *
-   * <p>If this is called on an single directory for a relative path, this returns an empty relative
-   * path. If it's called on a root (like '/') or the empty string, it returns null.
-   */
-  @Nullable
-  public LocalPath getParentDirectory() {
-    int lastSeparator = path.lastIndexOf(os.getSeparator());
-
-    // For absolute paths we need to specially handle when we hit root
-    // Relative paths can't hit this path as driveStrLength == 0
-    if (driveStrLength > 0) {
-      if (lastSeparator < driveStrLength) {
-        if (path.length() > driveStrLength) {
-          String newPath = path.substring(0, driveStrLength);
-          return new LocalPath(newPath, driveStrLength, os);
-        } else {
-          return null;
-        }
-      }
-    } else {
-      if (lastSeparator == -1) {
-        if (!path.isEmpty()) {
-          return EMPTY;
-        } else {
-          return null;
-        }
-      }
-    }
-    String newPath = path.substring(0, lastSeparator);
-    return new LocalPath(newPath, driveStrLength, os);
-  }
-
-  /**
-   * Returns the {@link LocalPath} relative to the base {@link LocalPath}.
-   *
-   * <p>For example, <code>LocalPath.create("foo/bar/wiz").relativeTo(LocalPath.create("foo"))
-   * </code> returns <code>LocalPath.create("bar/wiz")</code>.
-   *
-   * <p>If the {@link LocalPath} is not a child of the passed {@link LocalPath} an {@link
-   * IllegalArgumentException} is thrown. In particular, this will happen whenever the two {@link
-   * LocalPath} instances aren't both absolute or both relative.
-   */
-  public LocalPath relativeTo(LocalPath base) {
-    Preconditions.checkNotNull(base);
-    Preconditions.checkArgument(os == base.os);
-    if (isAbsolute() != base.isAbsolute()) {
-      throw new IllegalArgumentException(
-          "Cannot relativize an absolute and a non-absolute path pair");
-    }
-    String basePath = base.path;
-    if (!os.startsWith(path, basePath)) {
-      throw new IllegalArgumentException(
-          String.format("Path '%s' is not under '%s', cannot relativize", this, base));
-    }
-    int bn = basePath.length();
-    if (bn == 0) {
-      return this;
-    }
-    if (path.length() == bn) {
-      return EMPTY;
-    }
-    final int lastSlashIndex;
-    if (basePath.charAt(bn - 1) == '/') {
-      lastSlashIndex = bn - 1;
-    } else {
-      lastSlashIndex = bn;
-    }
-    if (path.charAt(lastSlashIndex) != '/') {
-      throw new IllegalArgumentException(
-          String.format("Path '%s' is not under '%s', cannot relativize", this, base));
-    }
-    String newPath = path.substring(lastSlashIndex + 1);
-    return new LocalPath(newPath, 0 /* Always a relative path */, os);
-  }
-
-  /**
-   * Splits a path into its constituent parts. The root is not included. This is an inefficient
-   * operation and should be avoided.
-   */
-  public String[] split() {
-    String[] segments = path.split("/");
-    if (driveStrLength > 0) {
-      // String#split("/") for some reason returns a zero-length array
-      // String#split("/hello") returns a 2-length array, so this makes little sense
-      if (segments.length == 0) {
-        return segments;
-      }
-      return Arrays.copyOfRange(segments, 1, segments.length);
-    }
-    return segments;
-  }
-
-  /**
-   * Returns whether this path is an ancestor of another path.
-   *
-   * <p>A path is considered an ancestor of itself.
-   *
-   * <p>An absolute path can never be an ancestor of a relative path, and vice versa.
-   */
-  public boolean startsWith(LocalPath other) {
-    Preconditions.checkNotNull(other);
-    Preconditions.checkArgument(os == other.os);
-    if (other.path.length() > path.length()) {
-      return false;
-    }
-    if (driveStrLength != other.driveStrLength) {
-      return false;
-    }
-    if (!os.startsWith(path, other.path)) {
-      return false;
-    }
-    return path.length() == other.path.length()
-        || other.path.length() == driveStrLength
-        || path.charAt(other.path.length()) == os.getSeparator();
-  }
-
-  public boolean isAbsolute() {
-    return driveStrLength > 0;
-  }
-
-  @Override
-  public String toString() {
-    return path;
-  }
-
-  @Override
-  public boolean equals(Object o) {
-    if (this == o) {
-      return true;
-    }
-    if (o == null || getClass() != o.getClass()) {
-      return false;
-    }
-    return os.compare(this.path, ((LocalPath) o).path) == 0;
-  }
-
-  @Override
-  public int hashCode() {
-    return os.hashPath(this.path);
-  }
-
-  @Override
-  public int compareTo(LocalPath o) {
-    return os.compare(this.path, o.path);
-  }
-
-  /**
-   * An interface class representing the differences in path style between different OSs.
-   *
-   * <p>Eg. case sensitivity, '/' mounts vs. 'C:/', etc.
-   */
-  @VisibleForTesting
-  interface OsPathPolicy {
-    int NORMALIZED = 0; // Path is normalized
-    int NEEDS_NORMALIZE = 1; // Path requires normalization
-
-    /** Returns required normalization level, passed to {@link #normalize}. */
-    int needsToNormalize(String path);
-
-    /**
-     * Normalizes the passed string according to the passed normalization level.
-     *
-     * @param normalizationLevel The normalizationLevel from {@link #needsToNormalize}
-     */
-    String normalize(String path, int normalizationLevel);
-
-    /**
-     * Returns the length of the mount, eg. 1 for unix '/', 3 for Windows 'C:/'.
-     *
-     * <p>If the path is relative, 0 is returned
-     */
-    int getDriveStrLength(String path);
-
-    /** Compares two path strings, using the given OS case sensitivity. */
-    int compare(String s1, String s2);
-
-    /** Computes the hash code for a path string. */
-    int hashPath(String s);
-
-    /**
-     * Returns whether the passed string starts with the given prefix, given the OS case
-     * sensitivity.
-     *
-     * <p>This is a pure string operation and doesn't need to worry about matching path segments.
-     */
-    boolean startsWith(String path, String prefix);
-
-    char getSeparator();
-
-    boolean isCaseSensitive();
-  }
-
-  @VisibleForTesting
-  static class UnixOsPathPolicy implements OsPathPolicy {
-
-    @Override
-    public int needsToNormalize(String path) {
-      int n = path.length();
-      int dotCount = 0;
-      char prevChar = 0;
-      for (int i = 0; i < n; i++) {
-        char c = path.charAt(i);
-        if (c == '/') {
-          if (prevChar == '/') {
-            return NEEDS_NORMALIZE;
-          }
-          if (dotCount == 1 || dotCount == 2) {
-            return NEEDS_NORMALIZE;
-          }
-        }
-        dotCount = c == '.' ? dotCount + 1 : 0;
-        prevChar = c;
-      }
-      if (prevChar == '/' || dotCount == 1 || dotCount == 2) {
-        return NEEDS_NORMALIZE;
-      }
-      return NORMALIZED;
-    }
-
-    @Override
-    public String normalize(String path, int normalizationLevel) {
-      if (normalizationLevel == NORMALIZED) {
-        return path;
-      }
-      if (path.isEmpty()) {
-        return path;
-      }
-      boolean isAbsolute = path.charAt(0) == '/';
-      String[] segments = path.split("/+");
-      int segmentCount = removeRelativePaths(segments, isAbsolute ? 1 : 0);
-      StringBuilder sb = new StringBuilder(path.length());
-      if (isAbsolute) {
-        sb.append('/');
-      }
-      for (int i = 0; i < segmentCount; ++i) {
-        sb.append(segments[i]);
-        sb.append('/');
-      }
-      if (segmentCount > 0) {
-        sb.deleteCharAt(sb.length() - 1);
-      }
-      return sb.toString();
-    }
-
-    @Override
-    public int getDriveStrLength(String path) {
-      if (path.length() == 0) {
-        return 0;
-      }
-      return (path.charAt(0) == '/') ? 1 : 0;
-    }
-
-    @Override
-    public int compare(String s1, String s2) {
-      return s1.compareTo(s2);
-    }
-
-    @Override
-    public int hashPath(String s) {
-      return s.hashCode();
-    }
-
-    @Override
-    public boolean startsWith(String path, String prefix) {
-      return path.startsWith(prefix);
-    }
-
-    @Override
-    public char getSeparator() {
-      return '/';
-    }
-
-    @Override
-    public boolean isCaseSensitive() {
-      return true;
-    }
-  }
-
-  /** Mac is a unix file system that is case insensitive. */
-  @VisibleForTesting
-  static class MacOsPathPolicy extends UnixOsPathPolicy {
-    @Override
-    public int compare(String s1, String s2) {
-      return s1.compareToIgnoreCase(s2);
-    }
-
-    @Override
-    public int hashPath(String s) {
-      return s.toLowerCase().hashCode();
-    }
-
-    @Override
-    public boolean isCaseSensitive() {
-      return false;
-    }
-  }
-
-  @VisibleForTesting
-  static class WindowsOsPathPolicy implements OsPathPolicy {
-
-    private static final int NEEDS_SHORT_PATH_NORMALIZATION = NEEDS_NORMALIZE + 1;
-
-    // msys root, used to resolve paths from msys starting with "/"
-    private static final AtomicReference<String> UNIX_ROOT = new AtomicReference<>(null);
-    private final ShortPathResolver shortPathResolver;
-
-    interface ShortPathResolver {
-      String resolveShortPath(String path);
-    }
-
-    static class DefaultShortPathResolver implements ShortPathResolver {
-      @Override
-      public String resolveShortPath(String path) {
-        try {
-          return WindowsFileOperations.getLongPath(path);
-        } catch (IOException e) {
-          return path;
-        }
-      }
-    }
-
-    WindowsOsPathPolicy() {
-      this(new DefaultShortPathResolver());
-    }
-
-    WindowsOsPathPolicy(ShortPathResolver shortPathResolver) {
-      this.shortPathResolver = shortPathResolver;
-    }
-
-    @Override
-    public int needsToNormalize(String path) {
-      int n = path.length();
-      int normalizationLevel = 0;
-      // Check for unix path
-      if (n > 0 && path.charAt(0) == '/') {
-        normalizationLevel = Math.max(normalizationLevel, NEEDS_NORMALIZE);
-      }
-      int dotCount = 0;
-      char prevChar = 0;
-      int segmentBeginIndex = 0; // The start index of the current path index
-      boolean segmentHasShortPathChar = false; // Triggers more expensive short path regex test
-      for (int i = 0; i < n; i++) {
-        char c = path.charAt(i);
-        if (c == '/' || c == '\\') {
-          if (c == '\\') {
-            normalizationLevel = Math.max(normalizationLevel, NEEDS_NORMALIZE);
-          }
-          // No need to check for '\' here because that already causes normalization
-          if (prevChar == '/') {
-            normalizationLevel = Math.max(normalizationLevel, NEEDS_NORMALIZE);
-          }
-          if (dotCount == 1 || dotCount == 2) {
-            normalizationLevel = Math.max(normalizationLevel, NEEDS_NORMALIZE);
-          }
-          if (segmentHasShortPathChar) {
-            if (WindowsShortPath.isShortPath(path.substring(segmentBeginIndex, i))) {
-              normalizationLevel = Math.max(normalizationLevel, NEEDS_SHORT_PATH_NORMALIZATION);
-            }
-          }
-          segmentBeginIndex = i + 1;
-          segmentHasShortPathChar = false;
-        } else if (c == '~') {
-          // This path segment might be a Windows short path segment
-          segmentHasShortPathChar = true;
-        }
-        dotCount = c == '.' ? dotCount + 1 : 0;
-        prevChar = c;
-      }
-      if (prevChar == '/' || dotCount == 1 || dotCount == 2) {
-        normalizationLevel = Math.max(normalizationLevel, NEEDS_NORMALIZE);
-      }
-      return normalizationLevel;
-    }
-
-    @Override
-    public String normalize(String path, int normalizationLevel) {
-      if (normalizationLevel == NORMALIZED) {
-        return path;
-      }
-      if (normalizationLevel == NEEDS_SHORT_PATH_NORMALIZATION) {
-        String resolvedPath = shortPathResolver.resolveShortPath(path);
-        if (resolvedPath != null) {
-          path = resolvedPath;
-        }
-      }
-      String[] segments = path.split("[\\\\/]+");
-      int driveStrLength = getDriveStrLength(path);
-      boolean isAbsolute = driveStrLength > 0;
-      int segmentSkipCount = isAbsolute ? 1 : 0;
-
-      StringBuilder sb = new StringBuilder(path.length());
-      if (isAbsolute) {
-        char driveLetter = path.charAt(0);
-        sb.append(Character.toUpperCase(driveLetter));
-        sb.append(":/");
-      }
-      // unix path support
-      if (!path.isEmpty() && path.charAt(0) == '/') {
-        if (path.length() == 2 || (path.length() > 2 && path.charAt(2) == '/')) {
-          sb.append(Character.toUpperCase(path.charAt(1)));
-          sb.append(":/");
-          segmentSkipCount = 2;
-        } else {
-          String unixRoot = getUnixRoot();
-          sb.append(unixRoot);
-        }
-      }
-      int segmentCount = removeRelativePaths(segments, segmentSkipCount);
-      for (int i = 0; i < segmentCount; ++i) {
-        sb.append(segments[i]);
-        sb.append('/');
-      }
-      if (segmentCount > 0) {
-        sb.deleteCharAt(sb.length() - 1);
-      }
-      return sb.toString();
-    }
-
-    @Override
-    public int getDriveStrLength(String path) {
-      int n = path.length();
-      if (n < 3) {
-        return 0;
-      }
-      if (isDriveLetter(path.charAt(0))
-          && path.charAt(1) == ':'
-          && (path.charAt(2) == '/' || path.charAt(2) == '\\')) {
-        return 3;
-      }
-      return 0;
-    }
-
-    private static boolean isDriveLetter(char c) {
-      return ((c >= 'a') && (c <= 'z')) || ((c >= 'A') && (c <= 'Z'));
-    }
-
-    @Override
-    public int compare(String s1, String s2) {
-      // Windows is case-insensitive
-      return s1.compareToIgnoreCase(s2);
-    }
-
-    @Override
-    public int hashPath(String s) {
-      // Windows is case-insensitive
-      return s.toLowerCase().hashCode();
-    }
-
-    @Override
-    public boolean startsWith(String path, String prefix) {
-      int pathn = path.length();
-      int prefixn = prefix.length();
-      if (pathn < prefixn) {
-        return false;
-      }
-      for (int i = 0; i < prefixn; ++i) {
-        if (Character.toLowerCase(path.charAt(i)) != Character.toLowerCase(prefix.charAt(i))) {
-          return false;
-        }
-      }
-      return true;
-    }
-
-    @Override
-    public char getSeparator() {
-      return '/';
-    }
-
-    @Override
-    public boolean isCaseSensitive() {
-      return false;
-    }
-
-    private String getUnixRoot() {
-      String value = UNIX_ROOT.get();
-      if (value == null) {
-        String jvmFlag = "bazel.windows_unix_root";
-        value = determineUnixRoot(jvmFlag);
-        if (value == null) {
-          throw new IllegalStateException(
-              String.format(
-                  "\"%1$s\" JVM flag is not set. Use the --host_jvm_args flag or export the "
-                      + "BAZEL_SH environment variable. For example "
-                      + "\"--host_jvm_args=-D%1$s=c:/tools/msys64\" or "
-                      + "\"set BAZEL_SH=c:/tools/msys64/usr/bin/bash.exe\".",
-                  jvmFlag));
-        }
-        if (getDriveStrLength(value) != 3) {
-          throw new IllegalStateException(
-              String.format("\"%s\" must be an absolute path, got: \"%s\"", jvmFlag, value));
-        }
-        value = value.replace('\\', '/');
-        if (value.length() > 3 && value.endsWith("/")) {
-          value = value.substring(0, value.length() - 1);
-        }
-        UNIX_ROOT.set(value);
-      }
-      return value;
-    }
-
-    private String determineUnixRoot(String jvmArgName) {
-      // Get the path from a JVM flag, if specified.
-      String path = System.getProperty(jvmArgName);
-      if (path == null) {
-        return null;
-      }
-      path = path.trim();
-      if (path.isEmpty()) {
-        return null;
-      }
-      return path;
-    }
-  }
-
-  private static OsPathPolicy createFilePathOs() {
-    switch (OS.getCurrent()) {
-      case LINUX:
-      case FREEBSD:
-      case UNKNOWN:
-        return new UnixOsPathPolicy();
-      case DARWIN:
-        return new MacOsPathPolicy();
-      case WINDOWS:
-        return new WindowsOsPathPolicy();
-      default:
-        throw new AssertionError("Not covering all OSs");
-    }
-  }
-
-  /**
-   * Normalizes any '.' and '..' in-place in the segment array by shifting other segments to the
-   * front. Returns the remaining number of items.
-   */
-  private static int removeRelativePaths(String[] segments, int starti) {
-    int segmentCount = 0;
-    int shift = starti;
-    for (int i = starti; i < segments.length; ++i) {
-      String segment = segments[i];
-      switch (segment) {
-        case ".":
-          // Just discard it
-          ++shift;
-          break;
-        case "..":
-          if (segmentCount > 0 && !segments[segmentCount - 1].equals("..")) {
-            // Remove the last segment, if there is one and it is not "..". This
-            // means that the resulting path can still contain ".."
-            // segments at the beginning.
-            segmentCount--;
-            shift += 2;
-            break;
-          }
-          // Fall through
-        default:
-          ++segmentCount;
-          if (shift > 0) {
-            segments[i - shift] = segments[i];
-          }
-          break;
-      }
-    }
-    return segmentCount;
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/OsPathPolicy.java b/src/main/java/com/google/devtools/build/lib/vfs/OsPathPolicy.java
new file mode 100644
index 0000000000..6b0380f8c8
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/vfs/OsPathPolicy.java
@@ -0,0 +1,144 @@
+// Copyright 2017 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.util.OS;
+
+/**
+ * An interface class representing the differences in path style between different OSs.
+ *
+ * <p>Eg. case sensitivity, '/' mounts vs. 'C:/', etc.
+ */
+public interface OsPathPolicy {
+  int NORMALIZED = 0; // Path is normalized
+  int NEEDS_NORMALIZE = 1; // Path requires normalization
+
+  /** Returns required normalization level, passed to {@link #normalize}. */
+  int needsToNormalize(String path);
+
+  /**
+   * Returns the required normalization level if an already normalized string is concatenated with
+   * another normalized path fragment.
+   *
+   * <p>This method may be faster than {@link #needsToNormalize(String)}.
+   */
+  int needsToNormalizeSuffix(String normalizedSuffix);
+
+  /**
+   * Normalizes the passed string according to the passed normalization level.
+   *
+   * @param normalizationLevel The normalizationLevel from {@link #needsToNormalize}
+   */
+  String normalize(String path, int normalizationLevel);
+
+  /**
+   * Returns the length of the mount, eg. 1 for unix '/', 3 for Windows 'C:/'.
+   *
+   * <p>If the path is relative, 0 is returned
+   */
+  int getDriveStrLength(String path);
+
+  /** Compares two path strings, using the given OS case sensitivity. */
+  int compare(String s1, String s2);
+
+  /** Compares two characters, using the given OS case sensitivity. */
+  int compare(char c1, char c2);
+
+  /** Tests two path strings for equality, using the given OS case sensitivity. */
+  boolean equals(String s1, String s2);
+
+  /** Computes the hash code for a path string. */
+  int hash(String s);
+
+  /**
+   * Returns whether the passed string starts with the given prefix, given the OS case sensitivity.
+   *
+   * <p>This is a pure string operation and doesn't need to worry about matching path segments.
+   */
+  boolean startsWith(String path, String prefix);
+
+  /**
+   * Returns whether the passed string ends with the given prefix, given the OS case sensitivity.
+   *
+   * <p>This is a pure string operation and doesn't need to worry about matching path segments.
+   */
+  boolean endsWith(String path, String suffix);
+
+  /** Returns the separator used for normalized paths. */
+  char getSeparator();
+
+  /** Returns whether the unnormalized character c is a separator. */
+  boolean isSeparator(char c);
+
+  boolean isCaseSensitive();
+
+  static OsPathPolicy getFilePathOs() {
+    switch (OS.getCurrent()) {
+      case LINUX:
+      case FREEBSD:
+      case UNKNOWN:
+        return UnixOsPathPolicy.INSTANCE;
+      case DARWIN:
+        // NOTE: We *should* return a path policy that is case insensitive,
+        // but we currently don't handle this
+        return UnixOsPathPolicy.INSTANCE;
+      case WINDOWS:
+        return WindowsOsPathPolicy.INSTANCE;
+      default:
+        throw new AssertionError("Not covering all OSs");
+    }
+  }
+
+  /** Utilities for implementations of {@link OsPathPolicy}. */
+  class Utils {
+    /**
+     * Normalizes any '.' and '..' in-place in the segment array by shifting other segments to the
+     * front. Returns the remaining number of items.
+     */
+    static int removeRelativePaths(String[] segments, int starti, boolean isAbsolute) {
+      int segmentCount = 0;
+      int shift = starti;
+      int n = segments.length;
+      for (int i = starti; i < n; ++i) {
+        String segment = segments[i];
+        switch (segment) {
+          case ".":
+            ++shift;
+            break;
+          case "..":
+            if (segmentCount > 0 && !segments[segmentCount - 1].equals("..")) {
+              // Remove the last segment, if there is one and it is not "..". This
+              // means that the resulting path can still contain ".."
+              // segments at the beginning.
+              segmentCount--;
+              shift += 2;
+              break;
+            } else if (isAbsolute) {
+              // If this is absolute, then just pop it the ".." off and remain at root
+              ++shift;
+              break;
+            }
+            // Fall through
+          default:
+            ++segmentCount;
+            if (shift > 0) {
+              segments[i - shift] = segments[i];
+            }
+            break;
+        }
+      }
+      return segmentCount;
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/Path.java b/src/main/java/com/google/devtools/build/lib/vfs/Path.java
index 9549d25bab..075c47bd07 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/Path.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/Path.java
@@ -14,14 +14,14 @@
 package com.google.devtools.build.lib.vfs;
 
 import com.google.common.base.Preconditions;
-import com.google.common.base.Predicate;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.skyframe.serialization.InjectingObjectCodec;
+import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
+import com.google.devtools.build.lib.skyframe.serialization.strings.StringCodecs;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrintable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
 import com.google.devtools.build.lib.util.FileType;
-import com.google.devtools.build.lib.util.StringCanonicalizer;
 import com.google.devtools.build.lib.vfs.FileSystem.HashFunction;
 import com.google.protobuf.CodedInputStream;
 import com.google.protobuf.CodedOutputStream;
@@ -33,28 +33,29 @@ import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.OutputStream;
 import java.io.Serializable;
-import java.lang.ref.Reference;
-import java.lang.ref.ReferenceQueue;
-import java.lang.ref.WeakReference;
-import java.net.URI;
-import java.net.URISyntaxException;
 import java.util.ArrayList;
 import java.util.Collection;
-import java.util.IdentityHashMap;
-import java.util.Objects;
+import javax.annotation.Nullable;
 
 /**
- * Instances of this class represent pathnames, forming a tree structure to implement sharing of
- * common prefixes (parent directory names). A node in these trees is something like foo, bar, ..,
- * ., or /. If the instance is not a root path, it will have a parent path. A path can also have
- * children, which are indexed by name in a map.
+ * A local file path representing a file on the host machine. You should use this when you want to
+ * access local files via the file system.
+ *
+ * <p>Paths are always absolute.
+ *
+ * <p>Strings are normalized with '.' and '..' removed and resolved (if possible), any multiple
+ * slashes ('/') removed, and any trailing slash also removed. Windows drive letters are uppercased.
+ * The current implementation does not touch the incoming path string unless the string actually
+ * needs to be normalized.
  *
  * <p>There is some limited support for Windows-style paths. Most importantly, drive identifiers in
- * front of a path (c:/abc) are supported. However, Windows-style backslash separators
- * (C:\\foo\\bar) and drive-relative paths ("C:foo") are explicitly not supported, same with
- * advanced features like \\\\network\\paths and \\\\?\\unc\\paths.
+ * front of a path (c:/abc) are supported and such paths are correctly recognized as absolute, as
+ * are paths with backslash separators (C:\\foo\\bar). However, advanced Windows-style features like
+ * \\\\network\\paths and \\\\?\\unc\\paths are not supported. We are currently using forward
+ * slashes ('/') even on Windows, so backslashes '\' get converted to forward slashes during
+ * normalization.
  *
- * <p>{@link FileSystem} implementations maintain pointers into this graph.
+ * <p>Mac and Windows file paths are case insensitive. Case is preserved.
  */
 @ThreadSafe
 public class Path
@@ -62,34 +63,6 @@ public class Path
   public static final InjectingObjectCodec<Path, FileSystemProvider> CODEC =
       new PathCodecWithInjectedFileSystem();
 
-  /** Filesystem-specific factory for {@link Path} objects. */
-  public static interface PathFactory {
-    /**
-     * Creates the root of all paths used by a filesystem.
-     *
-     * <p>All other paths are instantiated via {@link Path#createChildPath(String)} which calls
-     * {@link #createChildPath(Path, String)}.
-     *
-     * <p>Beware: this is called during the FileSystem constructor which may occur before subclasses
-     * are completely initialized.
-     */
-    Path createRootPath(FileSystem filesystem);
-
-    /**
-     * Create a child path of the given parent.
-     *
-     * <p>All {@link Path} objects are instantiated via this method, with the sole exception of the
-     * filesystem root, which is created by {@link #createRootPath(FileSystem)}.
-     */
-    Path createChildPath(Path parent, String childName);
-
-    /**
-     * Makes the proper invocation of {@link FileSystem#getCachedChildPathInternal}, doing
-     * filesystem-specific logic if necessary.
-     */
-    Path getCachedChildPathInternal(Path path, String childName);
-  }
-
   private static FileSystem fileSystemForSerialization;
 
   /**
@@ -106,398 +79,279 @@ public class Path
     return fileSystemForSerialization;
   }
 
-  // These are basically final, but can't be marked as such in order to support serialization.
-  private FileSystem fileSystem;
-  private String name;
-  private Path parent;
-  private int depth;
-  private int hashCode;
-
-  private static final ReferenceQueue<Path> REFERENCE_QUEUE = new ReferenceQueue<>();
+  private static final OsPathPolicy OS = OsPathPolicy.getFilePathOs();
+  private static final char SEPARATOR = OS.getSeparator();
 
-  private static class PathWeakReferenceForCleanup extends WeakReference<Path> {
-    final Path parent;
-    final String baseName;
+  private String path;
+  private int driveStrLength; // 1 on Unix, 3 on Windows
+  private FileSystem fileSystem;
 
-    PathWeakReferenceForCleanup(Path referent, ReferenceQueue<Path> referenceQueue) {
-      super(referent, referenceQueue);
-      parent = referent.getParentDirectory();
-      baseName = referent.getBaseName();
-    }
+  /** Creates a local path that is specific to the host OS. */
+  static Path create(String path, FileSystem fileSystem) {
+    Preconditions.checkNotNull(path);
+    int normalizationLevel = OS.needsToNormalize(path);
+    String normalizedPath = OS.normalize(path, normalizationLevel);
+    return createAlreadyNormalized(normalizedPath, fileSystem);
   }
 
-  private static final Thread PATH_CHILD_CACHE_CLEANUP_THREAD = new Thread("Path cache cleanup") {
-    @Override
-    public void run() {
-      while (true) {
-        try {
-          PathWeakReferenceForCleanup ref = (PathWeakReferenceForCleanup) REFERENCE_QUEUE.remove();
-          Path parent = ref.parent;
-          synchronized (parent) {
-            // It's possible that since this reference was enqueued for deletion, the Path was
-            // recreated with a new entry in the map. We definitely shouldn't delete that entry, so
-            // check to make sure they're the same.
-            Reference<Path> currentRef = ref.parent.children.get(ref.baseName);
-            if (currentRef == ref) {
-              ref.parent.children.remove(ref.baseName);
-            }
-          }
-        } catch (InterruptedException e) {
-          // Ignored.
-        }
-      }
-    }
-  };
-
-  static {
-    PATH_CHILD_CACHE_CLEANUP_THREAD.setDaemon(true);
-    PATH_CHILD_CACHE_CLEANUP_THREAD.start();
+  static Path createAlreadyNormalized(String path, FileSystem fileSystem) {
+    int driveStrLength = OS.getDriveStrLength(path);
+    return createAlreadyNormalized(path, driveStrLength, fileSystem);
   }
 
-  /**
-   * A mapping from a child file name to the {@link Path} representing it.
-   *
-   * <p>File names must be a single path segment.  The strings must be
-   * canonical.  We use IdentityHashMap instead of HashMap for reasons of space
-   * efficiency: instances are smaller by a single word.  Also, since all path
-   * segments are interned, the universe of Paths holds a minimal number of
-   * references to strings.  (It's doubtful that there's any time gain from use
-   * of an IdentityHashMap, since the time saved by avoiding string equality
-   * tests during hash lookups is probably equal to the time spent eagerly
-   * interning strings, unless the collision rate is high.)
-   *
-   * <p>The Paths are stored as weak references to ensure that a live
-   * Path for a directory does not hold a strong reference to all of its
-   * descendants, which would prevent collection of paths we never intend to
-   * use again.  Stale references in the map must be treated as absent.
-   *
-   * <p>A Path may be recycled once there is no Path that refers to it or
-   * to one of its descendants.  This means that any data stored in the
-   * Path instance by one of its subclasses must be recoverable: it's ok to
-   * store data in Paths as an optimization, but there must be another
-   * source for that data in case the Path is recycled.
-   *
-   * <p>We intentionally avoid using the existing library classes for reasons of
-   * space efficiency: while ConcurrentHashMap would reduce our locking
-   * overhead, and ReferenceMap would simplify the code a little, both of those
-   * classes have much higher per-instance overheads than IdentityHashMap.
-   *
-   * <p>The Path object must be synchronized while children is being
-   * accessed.
-   */
-  private volatile IdentityHashMap<String, Reference<Path>> children;
-
-  /**
-   * Create a path instance.
-   *
-   * <p>Should only be called by {@link PathFactory#createChildPath(Path, String)}.
-   *
-   * @param name the name of this path; it must be canonicalized with {@link
-   *     StringCanonicalizer#intern}
-   * @param parent this path's parent
-   */
-  protected Path(FileSystem fileSystem, String name, Path parent) {
-    this.fileSystem = fileSystem;
-    this.name = name;
-    this.parent = parent;
-    this.depth = parent == null ? 0 : parent.depth + 1;
-
-    // No need to include the drive letter in the hash code, because it's derived from the parent
-    // and/or the name.
-    if (fileSystem == null || fileSystem.isFilePathCaseSensitive()) {
-      this.hashCode = Objects.hash(parent, name);
-    } else {
-      this.hashCode = Objects.hash(parent, name.toLowerCase());
-    }
+  static Path createAlreadyNormalized(String path, int driveStrLength, FileSystem fileSystem) {
+    return new Path(path, driveStrLength, fileSystem);
   }
 
-  /**
-   * Create the root path.
-   *
-   * <p>Should only be called by {@link PathFactory#createRootPath(FileSystem)}.
-   */
-  protected Path(FileSystem fileSystem) {
-    this(fileSystem, StringCanonicalizer.intern("/"), null);
+  /** This method expects path to already be normalized. */
+  private Path(String path, int driveStrLength, FileSystem fileSystem) {
+    Preconditions.checkArgument(driveStrLength > 0, "Paths must be absolute: '%s'", path);
+    this.path = Preconditions.checkNotNull(path);
+    this.driveStrLength = driveStrLength;
+    this.fileSystem = fileSystem;
   }
 
-  private void writeObject(ObjectOutputStream out) throws IOException {
-    Preconditions.checkState(
-        fileSystem == fileSystemForSerialization, "%s %s", fileSystem, fileSystemForSerialization);
-    out.writeUTF(getPathString());
+  public String getPathString() {
+    return path;
   }
 
-  private void readObject(ObjectInputStream in) throws IOException {
-    fileSystem = fileSystemForSerialization;
-    String p = in.readUTF();
-    PathFragment pf = PathFragment.create(p);
-    PathFragment parentDir = pf.getParentDirectory();
-    if (parentDir == null) {
-      this.name = "/";
-      this.parent = null;
-      this.depth = 0;
-    } else {
-      this.name = pf.getBaseName();
-      this.parent = fileSystem.getPath(parentDir);
-      this.depth = this.parent.depth + 1;
-    }
-    this.hashCode = Objects.hash(parent, name);
-    reinitializeAfterDeserialization();
+  @Override
+  public String filePathForFileTypeMatcher() {
+    return path;
   }
 
   /**
-   * Returns the filesystem instance to which this path belongs.
+   * Returns the name of the leaf file or directory.
+   *
+   * <p>If called on a {@link Path} instance for a mount name (eg. '/' or 'C:/'), the empty string
+   * is returned.
    */
-  public FileSystem getFileSystem() {
-    return fileSystem;
-  }
-
-  public boolean isRootDirectory() {
-    return parent == null;
+  public String getBaseName() {
+    int lastSeparator = path.lastIndexOf(SEPARATOR);
+    return lastSeparator < driveStrLength
+        ? path.substring(driveStrLength)
+        : path.substring(lastSeparator + 1);
   }
 
-  protected Path createChildPath(String childName) {
-    return fileSystem.getPathFactory().createChildPath(this, childName);
+  /** Synonymous with {@link Path#getRelative(String)}. */
+  public Path getChild(String child) {
+    FileSystemUtils.checkBaseName(child);
+    return getRelative(child);
   }
 
   /**
-   * Reinitializes this object after deserialization.
-   *
-   * <p>Derived classes should use this hook to initialize additional state.
+   * Returns a {@link Path} instance representing the relative path between this {@link Path} and
+   * the given path.
    */
-  protected void reinitializeAfterDeserialization() {}
-
-  /**
-   * Returns true if {@code ancestorPath} may be an ancestor of {@code path}.
-   *
-   * <p>The return value may be a false positive, but it cannot be a false negative. This means that
-   * a true return value doesn't mean the ancestor candidate is really an ancestor, however a false
-   * return value means it's guaranteed that {@code ancestorCandidate} is not an ancestor of this
-   * path.
-   *
-   * <p>Subclasses may override this method with filesystem-specific logic, e.g. a Windows
-   * filesystem may return false if the ancestor path is on a different drive than this one, because
-   * it is then guaranteed that the ancestor candidate cannot be an ancestor of this path.
-   *
-   * @param ancestorCandidate the path that may or may not be an ancestor of this one
-   */
-  protected boolean isMaybeRelativeTo(Path ancestorCandidate) {
-    return true;
+  public Path getRelative(PathFragment other) {
+    Preconditions.checkNotNull(other);
+    String otherStr = other.getPathString();
+    // Fast-path: The path fragment is already normal, use cheaper normalization check
+    return getRelative(otherStr, other.getDriveStrLength(), OS.needsToNormalizeSuffix(otherStr));
   }
 
   /**
-   * Returns true if this directory is top-level, i.e. it is its own parent.
-   *
-   * <p>When canonicalizing paths the ".." segment of a top-level directory always resolves to the
-   * directory itself.
-   *
-   * <p>On Unix, a top-level directory would be just the filesystem root ("/), on Windows it would
-   * be the filesystem root and the volume roots.
+   * Returns a {@link Path} instance representing the relative path between this {@link Path} and
+   * the given path.
    */
-  protected boolean isTopLevelDirectory() {
-    return isRootDirectory();
+  public Path getRelative(String other) {
+    Preconditions.checkNotNull(other);
+    return getRelative(other, OS.getDriveStrLength(other), OS.needsToNormalize(other));
   }
 
-  /**
-   * Returns the child path named name, or creates such a path (and caches it)
-   * if it doesn't already exist.
-   */
-  private Path getCachedChildPath(String childName) {
-    return fileSystem.getPathFactory().getCachedChildPathInternal(this, childName);
+  private Path getRelative(String other, int otherDriveStrLength, int normalizationLevel) {
+    if (other.isEmpty()) {
+      return this;
+    }
+    // This is an absolute path, simply return it
+    if (otherDriveStrLength > 0) {
+      String normalizedPath = OS.normalize(other, normalizationLevel);
+      return new Path(normalizedPath, otherDriveStrLength, fileSystem);
+    }
+    String newPath;
+    if (path.length() == driveStrLength) {
+      newPath = path + other;
+    } else {
+      newPath = path + '/' + other;
+    }
+    // Note that even if other came from a PathFragment instance we still might
+    // need to normalize the result if (for instance) other is a path that
+    // starts with '..'
+    newPath = OS.normalize(newPath, normalizationLevel);
+    return new Path(newPath, driveStrLength, fileSystem);
   }
 
   /**
-   * Internal method only intended to be called by {@link PathFactory#getCachedChildPathInternal}.
+   * Returns the parent directory of this {@link Path}.
+   *
+   * <p>If called on a root (like '/'), it returns null.
    */
-  public static Path getCachedChildPathInternal(Path parent, String childName, boolean cacheable) {
-    // We get a canonical instance since 'children' is an IdentityHashMap.
-    childName = StringCanonicalizer.intern(childName);
-    if (!cacheable) {
-      // Non-cacheable children won't show up in `children` so applyToChildren won't run for these.
-      return parent.createChildPath(childName);
-    }
-
-    synchronized (parent) {
-      if (parent.children == null) {
-        // 66% of Paths have size == 1, 80% <= 2
-        parent.children = new IdentityHashMap<>(1);
-      }
-      Reference<Path> childRef = parent.children.get(childName);
-      Path child;
-      if (childRef == null || (child = childRef.get()) == null) {
-        child = parent.createChildPath(childName);
-        parent.children.put(childName, new PathWeakReferenceForCleanup(child, REFERENCE_QUEUE));
+  @Nullable
+  public Path getParentDirectory() {
+    int lastSeparator = path.lastIndexOf(SEPARATOR);
+    if (lastSeparator < driveStrLength) {
+      if (path.length() > driveStrLength) {
+        String newPath = path.substring(0, driveStrLength);
+        return new Path(newPath, driveStrLength, fileSystem);
+      } else {
+        return null;
       }
-      return child;
     }
+    String newPath = path.substring(0, lastSeparator);
+    return new Path(newPath, driveStrLength, fileSystem);
   }
 
   /**
-   * Applies the specified function to each {@link Path} that is an existing direct
-   * descendant of this one.  The Predicate is evaluated only for its
-   * side-effects.
+   * Returns the drive.
    *
-   * <p>This function exists to hide the "children" field, whose complex
-   * synchronization and identity requirements are too unsafe to be exposed to
-   * subclasses.  For example, the "children" field must be synchronized for
-   * the duration of any iteration over it; it may be null; and references
-   * within it may be stale, and must be ignored.
+   * <p>On unix, this will return "/". On Windows it will return the drive letter, like "C:/".
    */
-  protected synchronized void applyToChildren(Predicate<Path> function) {
-    if (children != null) {
-      for (Reference<Path> childRef : children.values()) {
-        Path child = childRef.get();
-        if (child != null) {
-          function.apply(child);
-        }
-      }
-    }
+  public String getDriveStr() {
+    return path.substring(0, driveStrLength);
   }
 
   /**
-   * Returns whether this path is recursively "under" {@code prefix} - that is,
-   * whether {@code path} is a prefix of this path.
+   * Returns the {@link Path} relative to the base {@link Path}.
    *
-   * <p>This method returns {@code true} when called with this path itself. This
-   * method acts independently of the existence of files or folders.
+   * <p>For example, <code>Path.create("foo/bar/wiz").relativeTo(Path.create("foo"))
+   * </code> returns <code>Path.create("bar/wiz")</code>.
    *
-   * @param prefix a path which may or may not be a prefix of this path
+   * <p>If the {@link Path} is not a child of the passed {@link Path} an {@link
+   * IllegalArgumentException} is thrown. In particular, this will happen whenever the two {@link
+   * Path} instances aren't both absolute or both relative.
    */
-  public boolean startsWith(Path prefix) {
-    Path n = this;
-    for (int i = 0, len = depth - prefix.depth; i < len; i++) {
-      n = n.getParentDirectory();
+  public PathFragment relativeTo(Path base) {
+    Preconditions.checkNotNull(base);
+    checkSameFileSystem(base);
+    String basePath = base.path;
+    if (!OS.startsWith(path, basePath)) {
+      throw new IllegalArgumentException(
+          String.format("Path '%s' is not under '%s', cannot relativize", this, base));
+    }
+    int bn = basePath.length();
+    if (bn == 0) {
+      return PathFragment.createAlreadyNormalized(path, driveStrLength);
+    }
+    if (path.length() == bn) {
+      return PathFragment.EMPTY_FRAGMENT;
+    }
+    final int lastSlashIndex;
+    if (basePath.charAt(bn - 1) == '/') {
+      lastSlashIndex = bn - 1;
+    } else {
+      lastSlashIndex = bn;
+    }
+    if (path.charAt(lastSlashIndex) != '/') {
+      throw new IllegalArgumentException(
+          String.format("Path '%s' is not under '%s', cannot relativize", this, base));
     }
-    return prefix.equals(n);
+    String newPath = path.substring(lastSlashIndex + 1);
+    return PathFragment.createAlreadyNormalized(newPath, 0);
   }
 
   /**
-   * Computes a string representation of this path, and writes it to the given string builder. Only
-   * called locally with a new instance.
+   * Returns whether this path is an ancestor of another path.
+   *
+   * <p>A path is considered an ancestor of itself.
    */
-  protected void buildPathString(StringBuilder result) {
-    if (isRootDirectory()) {
-      result.append(PathFragment.ROOT_DIR);
-    } else {
-      parent.buildPathString(result);
-      if (!parent.isRootDirectory()) {
-        result.append(PathFragment.SEPARATOR_CHAR);
-      }
-      result.append(name);
+  public boolean startsWith(Path other) {
+    if (fileSystem != other.fileSystem) {
+      return false;
     }
+    return startsWith(other.path, other.driveStrLength);
   }
 
   /**
-   * Returns the path encoded as an {@link URI}.
+   * Returns whether this path is an ancestor of another path.
    *
-   * <p>This concrete implementation returns URIs with "file" as the scheme.
-   * For Example:
-   *  - On Unix the path "/tmp/foo bar.txt" will be encoded as
-   *    "file:///tmp/foo%20bar.txt".
-   *  - On Windows the path "C:\Temp\Foo Bar.txt" will be encoded as
-   *    "file:///C:/Temp/Foo%20Bar.txt"
+   * <p>A path is considered an ancestor of itself.
    *
-   * <p>Implementors extending this class for special filesystems will likely need to override
-   * this method.
-   *
-   * @throws URISyntaxException if the URI cannot be constructed.
+   * <p>An absolute path can never be an ancestor of a relative path fragment.
    */
-  public URI toURI() {
-    String ps = getPathString();
-    if (!ps.startsWith("/")) {
-      // On Windows URI's need to start with a '/'. i.e. C:\Foo\Bar would be file:///C:/Foo/Bar
-      ps = "/" + ps;
-    }
-    try {
-      return new URI("file",
-          // Needs to be "" instead of null, so that toString() will append "//" after the scheme.
-          // We need this for backwards compatibility reasons as some consumers of the BEP are
-          // broken.
-          "",
-          ps, null, null);
-    } catch (URISyntaxException e) {
-      throw new IllegalStateException(e);
+  public boolean startsWith(PathFragment other) {
+    if (!other.isAbsolute()) {
+      return false;
     }
+    String otherPath = other.getPathString();
+    return startsWith(otherPath, OS.getDriveStrLength(otherPath));
   }
 
-  /**
-   * Returns the path as a string.
-   */
-  public String getPathString() {
-    // Profile driven optimization:
-    // Preallocate a size determined by the depth, so that
-    // we do not have to expand the capacity of the StringBuilder
-    StringBuilder builder = new StringBuilder(depth * 20);
-    buildPathString(builder);
-    return builder.toString();
+  private boolean startsWith(String otherPath, int otherDriveStrLength) {
+    Preconditions.checkNotNull(otherPath);
+    if (otherPath.length() > path.length()) {
+      return false;
+    }
+    if (driveStrLength != otherDriveStrLength) {
+      return false;
+    }
+    if (!OS.startsWith(path, otherPath)) {
+      return false;
+    }
+    return path.length() == otherPath.length() // Handle equal paths
+        || otherPath.length() == driveStrLength // Handle (eg.) 'C:/foo' starts with 'C:/'
+        // Handle 'true' ancestors, eg. "foo/bar" starts with "foo", but does not start with "fo"
+        || path.charAt(otherPath.length()) == SEPARATOR;
   }
 
-  @Override
-  public void repr(SkylarkPrinter printer) {
-    printer.append(getPathString());
+  public FileSystem getFileSystem() {
+    return fileSystem;
   }
 
-  @Override
-  public String filePathForFileTypeMatcher() {
-    return name;
+  public PathFragment asFragment() {
+    return PathFragment.createAlreadyNormalized(path, driveStrLength);
   }
 
-  /**
-   * Returns the path as a string.
-   */
   @Override
   public String toString() {
-    return getPathString();
+    return path;
   }
 
   @Override
-  public int hashCode() {
-    return hashCode;
-  }
-
-  @Override
-  public boolean equals(Object other) {
-    if (this == other) {
+  public boolean equals(Object o) {
+    if (this == o) {
       return true;
     }
-    if (!(other instanceof Path)) {
+    if (o == null || getClass() != o.getClass()) {
       return false;
     }
-
-    Path otherPath = (Path) other;
-    if (hashCode != otherPath.hashCode) {
+    Path other = (Path) o;
+    if (fileSystem != other.fileSystem) {
       return false;
     }
+    return OS.equals(this.path, other.path);
+  }
 
-    if (!fileSystem.equals(otherPath.fileSystem)) {
-      return false;
-    }
+  @Override
+  public int hashCode() {
+    // Do not include file system for efficiency.
+    // In practice we never construct paths from different file systems.
+    return OS.hash(this.path);
+  }
 
-    if (fileSystem.isFilePathCaseSensitive()) {
-      return name.equals(otherPath.name)
-          && Objects.equals(parent, otherPath.parent);
-    } else {
-      return name.toLowerCase().equals(otherPath.name.toLowerCase())
-          && Objects.equals(parent, otherPath.parent);
+  @Override
+  public int compareTo(Path o) {
+    // If they are on different file systems, the file system decides the ordering.
+    FileSystem otherFs = o.getFileSystem();
+    if (!fileSystem.equals(otherFs)) {
+      int thisFileSystemHash = System.identityHashCode(fileSystem);
+      int otherFileSystemHash = System.identityHashCode(otherFs);
+      if (thisFileSystemHash < otherFileSystemHash) {
+        return -1;
+      } else if (thisFileSystemHash > otherFileSystemHash) {
+        return 1;
+      }
     }
+    return OS.compare(this.path, o.path);
   }
 
-  /**
-   * Returns a string of debugging information associated with this path.
-   * The results are unspecified and MUST NOT be interpreted programmatically.
-   */
-  protected String toDebugString() {
-    return "";
+  @Override
+  public void repr(SkylarkPrinter printer) {
+    printer.append(path);
   }
 
-  /**
-   * Returns a path representing the parent directory of this path,
-   * or null iff this Path represents the root of the filesystem.
-   *
-   * <p>Note: This method normalises ".."  and "." path segments by string
-   * processing, not by directory lookups.
-   */
-  public Path getParentDirectory() {
-    return parent;
+  @Override
+  public void str(SkylarkPrinter printer) {
+    repr(printer);
   }
 
   /** Returns true iff this path denotes an existing file of any kind. Follows symbolic links. */
@@ -662,157 +516,6 @@ public class Path
   }
 
   /**
-   * Returns the last segment of this path, or "/" for the root directory.
-   */
-  public String getBaseName() {
-    return name;
-  }
-
-  /**
-   * Interprets the name of a path segment relative to the current path and
-   * returns the result.
-   *
-   * <p>This is a purely syntactic operation, i.e. it does no I/O, it does not
-   * validate the existence of any path, nor resolve symbolic links. If 'prefix'
-   * is not canonical, then a 'name' of '..' will be interpreted incorrectly.
-   *
-   * @precondition segment contains no slashes.
-   */
-  private Path getCanonicalPath(String segment) {
-    if (segment.equals(".") || segment.isEmpty()) {
-      return this; // that's a noop
-    } else if (segment.equals("..")) {
-      // top-level directory's parent is root, when canonicalising:
-      return isTopLevelDirectory() ? this : parent;
-    } else {
-      return getCachedChildPath(segment);
-    }
-  }
-
-  /**
-   * Returns the path formed by appending the single non-special segment
-   * "baseName" to this path.
-   *
-   * <p>You should almost always use {@link #getRelative} instead, which has
-   * the same performance characteristics if the given name is a valid base
-   * name, and which also works for '.', '..', and strings containing '/'.
-   *
-   * @throws IllegalArgumentException if {@code baseName} is not a valid base
-   *     name according to {@link FileSystemUtils#checkBaseName}
-   */
-  public Path getChild(String baseName) {
-    FileSystemUtils.checkBaseName(baseName);
-    return getCachedChildPath(baseName);
-  }
-
-  protected Path getRootForRelativePathComputation(PathFragment suffix) {
-    return suffix.isAbsolute() ? fileSystem.getRootDirectory() : this;
-  }
-
-  /**
-   * Returns the path formed by appending the relative or absolute path fragment
-   * {@code suffix} to this path.
-   *
-   * <p>If suffix is absolute, the current path will be ignored; otherwise, they
-   * will be combined. Up-level references ("..") cause the preceding path
-   * segment to be elided; this interpretation is only correct if the base path
-   * is canonical.
-   */
-  public Path getRelative(PathFragment suffix) {
-    Path result = getRootForRelativePathComputation(suffix);
-    for (String segment : suffix.segments()) {
-      result = result.getCanonicalPath(segment);
-    }
-    return result;
-  }
-
-  /**
-   * Returns the path formed by appending the relative or absolute string
-   * {@code path} to this path.
-   *
-   * <p>If the given path string is absolute, the current path will be ignored;
-   * otherwise, they will be combined. Up-level references ("..") cause the
-   * preceding path segment to be elided.
-   *
-   * <p>This is a purely syntactic operation, i.e. it does no I/O, it does not
-   * validate the existence of any path, nor resolve symbolic links.
-   */
-  public Path getRelative(String path) {
-    // Fast path for valid base names.
-    if ((path.length() == 0) || (path.equals("."))) {
-      return this;
-    } else if (path.equals("..")) {
-      return isTopLevelDirectory() ? this : parent;
-    } else if (PathFragment.containsSeparator(path)) {
-      return getRelative(PathFragment.create(path));
-    } else {
-      return getCachedChildPath(path);
-    }
-  }
-
-  protected final String[] getSegments() {
-    String[] resultSegments = new String[depth];
-    Path currentPath = this;
-    for (int pos = depth - 1; pos >= 0; pos--) {
-      resultSegments[pos] = currentPath.getBaseName();
-      currentPath = currentPath.getParentDirectory();
-    }
-    return resultSegments;
-  }
-
-  /** Returns an absolute PathFragment representing this path. */
-  public PathFragment asFragment() {
-    return PathFragment.createAlreadyInterned('\0', true, getSegments());
-  }
-
-  /**
-   * Returns a relative path fragment to this path, relative to {@code
-   * ancestorDirectory}. {@code ancestorDirectory} must be on the same
-   * filesystem as this path. (Currently, both this path and "ancestorDirectory"
-   * must be absolute, though this restriction could be loosened.)
-   * <p>
-   * <code>x.relativeTo(z) == y</code> implies
-   * <code>z.getRelative(y.getPathString()) == x</code>.
-   * <p>
-   * For example, <code>"/foo/bar/wiz".relativeTo("/foo")</code> returns
-   * <code>"bar/wiz"</code>.
-   *
-   * @throws IllegalArgumentException if this path is not beneath {@code
-   *         ancestorDirectory} or if they are not part of the same filesystem
-   */
-  public PathFragment relativeTo(Path ancestorPath) {
-    checkSameFilesystem(ancestorPath);
-
-    if (isMaybeRelativeTo(ancestorPath)) {
-      // Fast path: when otherPath is the ancestor of this path
-      int resultSegmentCount = depth - ancestorPath.depth;
-      if (resultSegmentCount >= 0) {
-        String[] resultSegments = new String[resultSegmentCount];
-        Path currentPath = this;
-        for (int pos = resultSegmentCount - 1; pos >= 0; pos--) {
-          resultSegments[pos] = currentPath.getBaseName();
-          currentPath = currentPath.getParentDirectory();
-        }
-        if (ancestorPath.equals(currentPath)) {
-          return PathFragment.createAlreadyInterned('\0', false, resultSegments);
-        }
-      }
-    }
-
-    throw new IllegalArgumentException("Path " + this + " is not beneath " + ancestorPath);
-  }
-
-  /**
-   * Checks that "this" and "that" are paths on the same filesystem.
-   */
-  protected void checkSameFilesystem(Path that) {
-    if (this.fileSystem != that.fileSystem) {
-      throw new IllegalArgumentException("Files are on different filesystems: "
-          + this + ", " + that);
-    }
-  }
-
-  /**
    * Returns an output stream to the file denoted by the current path, creating it and truncating it
    * if necessary. The stream is opened for writing.
    *
@@ -868,7 +571,7 @@ public class Path
    * @throws IOException if the creation of the symbolic link was unsuccessful for any reason
    */
   public void createSymbolicLink(Path target) throws IOException {
-    checkSameFilesystem(target);
+    checkSameFileSystem(target);
     fileSystem.createSymbolicLink(this, target.asFragment());
   }
 
@@ -943,7 +646,7 @@ public class Path
    * @throws IOException if the rename failed for any reason
    */
   public void renameTo(Path target) throws IOException {
-    checkSameFilesystem(target);
+    checkSameFileSystem(target);
     fileSystem.renameTo(this, target);
   }
 
@@ -1183,69 +886,28 @@ public class Path
     fileSystem.prefetchPackageAsync(this, maxDirs);
   }
 
-  /**
-   * Compare Paths of the same file system using their PathFragments.
-   *
-   * <p>Paths from different filesystems will be compared using the identity
-   * hash code of their respective filesystems.
-   */
-  @Override
-  public int compareTo(Path o) {
-    // Fast-path.
-    if (equals(o)) {
-      return 0;
+  private void checkSameFileSystem(Path that) {
+    if (this.fileSystem != that.fileSystem) {
+      throw new IllegalArgumentException(
+          "Files are on different filesystems: " + this + ", " + that);
     }
+  }
 
-    // If they are on different file systems, the file system decides the ordering.
-    FileSystem otherFs = o.getFileSystem();
-    if (!fileSystem.equals(otherFs)) {
-      int thisFileSystemHash = System.identityHashCode(fileSystem);
-      int otherFileSystemHash = System.identityHashCode(otherFs);
-      if (thisFileSystemHash < otherFileSystemHash) {
-        return -1;
-      } else if (thisFileSystemHash > otherFileSystemHash) {
-        return 1;
-      } else {
-        // TODO(bazel-team): Add a name to every file system to be used here.
-        return 0;
-      }
-    }
+  private void writeObject(ObjectOutputStream out) throws IOException {
+    Preconditions.checkState(
+        fileSystem == fileSystemForSerialization, "%s %s", fileSystem, fileSystemForSerialization);
+    out.writeUTF(path);
+  }
 
-    // Equal file system, but different paths, because of the canonicalization.
-    // We expect to often compare Paths that are very similar, for example for files in the same
-    // directory. This can be done efficiently by going up segment by segment until we get the
-    // identical path (canonicalization again), and then just compare the immediate child segments.
-    // Overall this is much faster than creating PathFragment instances, and comparing those, which
-    // requires us to always go up to the top-level directory and copy all segments into a new
-    // string array.
-    // This was previously showing up as a hotspot in a profile of globbing a large directory.
-    Path a = this;
-    Path b = o;
-    int maxDepth = Math.min(a.depth, b.depth);
-    while (a.depth > maxDepth) {
-      a = a.getParentDirectory();
-    }
-    while (b.depth > maxDepth) {
-      b = b.getParentDirectory();
-    }
-    // One is the child of the other.
-    if (a.equals(b)) {
-      // If a is the same as this, this.depth must be less than o.depth.
-      return equals(a) ? -1 : 1;
-    }
-    Path previousa;
-    Path previousb;
-    do {
-      previousa = a;
-      previousb = b;
-      a = a.getParentDirectory();
-      b = b.getParentDirectory();
-    } while (!a.equals(b)); // This has to happen eventually.
-    return previousa.name.compareTo(previousb.name);
+  private void readObject(ObjectInputStream in) throws IOException {
+    path = in.readUTF();
+    fileSystem = fileSystemForSerialization;
+    driveStrLength = OS.getDriveStrLength(path);
   }
 
   private static class PathCodecWithInjectedFileSystem
       implements InjectingObjectCodec<Path, FileSystemProvider> {
+    private final ObjectCodec<String> stringCodec = StringCodecs.asciiOptimized();
 
     @Override
     public Class<Path> getEncodedClass() {
@@ -1256,14 +918,14 @@ public class Path
     public void serialize(FileSystemProvider fsProvider, Path path, CodedOutputStream codedOut)
         throws IOException, SerializationException {
       Preconditions.checkArgument(path.getFileSystem() == fsProvider.getFileSystem());
-      PathFragment.CODEC.serialize(path.asFragment(), codedOut);
+      stringCodec.serialize(path.getPathString(), codedOut);
     }
 
     @Override
     public Path deserialize(FileSystemProvider fsProvider, CodedInputStream codedIn)
         throws IOException, SerializationException {
-      PathFragment pathFragment = PathFragment.CODEC.deserialize(codedIn);
-      return fsProvider.getFileSystem().getPath(pathFragment);
+      return Path.createAlreadyNormalized(
+          stringCodec.deserialize(codedIn), fsProvider.getFileSystem());
     }
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/PathCodec.java b/src/main/java/com/google/devtools/build/lib/vfs/PathCodec.java
index ee0ef364e3..c7644ed960 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/PathCodec.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/PathCodec.java
@@ -17,6 +17,7 @@ package com.google.devtools.build.lib.vfs;
 import com.google.common.base.Preconditions;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
+import com.google.devtools.build.lib.skyframe.serialization.strings.StringCodecs;
 import com.google.protobuf.CodedInputStream;
 import com.google.protobuf.CodedOutputStream;
 import java.io.IOException;
@@ -24,6 +25,7 @@ import java.io.IOException;
 /** Custom serialization for {@link Path}s. */
 public class PathCodec implements ObjectCodec<Path> {
 
+  private final ObjectCodec<String> stringCodec = StringCodecs.asciiOptimized();
   private final FileSystem fileSystem;
 
   /** Create an instance for serializing and deserializing {@link Path}s on {@code fileSystem}. */
@@ -41,15 +43,15 @@ public class PathCodec implements ObjectCodec<Path> {
       throws IOException, SerializationException {
     Preconditions.checkState(
         path.getFileSystem() == fileSystem,
-        "Path's FileSystem (%s) did not match the configured FileSystem (%s)",
+        "Path's FileSystem (%s) did not match the configured FileSystem (%s) for path (%s)",
         path.getFileSystem(),
-        fileSystem);
-    PathFragment.CODEC.serialize(path.asFragment(), codedOut);
+        fileSystem,
+        path);
+    stringCodec.serialize(path.getPathString(), codedOut);
   }
 
   @Override
   public Path deserialize(CodedInputStream codedIn) throws IOException, SerializationException {
-    PathFragment pathFragment = PathFragment.CODEC.deserialize(codedIn);
-    return fileSystem.getPath(pathFragment);
+    return fileSystem.getPath(stringCodec.deserialize(codedIn));
   }
 }
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 572042a7d7..88ae732590 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
@@ -1,4 +1,4 @@
-// Copyright 2014 The Bazel Authors. All rights reserved.
+// Copyright 2017 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.
@@ -16,630 +16,470 @@ package com.google.devtools.build.lib.vfs;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.analysis.actions.CommandLineItem;
-import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
-import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodec;
 import com.google.devtools.build.lib.skyframe.serialization.SerializationException;
 import com.google.devtools.build.lib.skyframe.serialization.strings.StringCodecs;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrintable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkPrinter;
 import com.google.devtools.build.lib.util.FileType;
-import com.google.devtools.build.lib.util.OS;
-import com.google.devtools.build.lib.util.StringCanonicalizer;
 import com.google.protobuf.CodedInputStream;
 import com.google.protobuf.CodedOutputStream;
-import java.io.File;
 import java.io.IOException;
-import java.io.InvalidObjectException;
-import java.io.ObjectInputStream;
 import java.io.Serializable;
-import java.util.Arrays;
-import java.util.List;
 import java.util.Set;
+import javax.annotation.Nullable;
 
 /**
- * This class represents an immutable filesystem path, which may be absolute or relative. The path
- * is maintained as a simple ordered list of path segment strings.
+ * A path segment representing a path fragment using the host machine's path style. That is; If you
+ * are running on a Unix machine, the path style will be unix, on Windows it is the windows path
+ * style.
  *
- * <p>This class is independent from other VFS classes, especially anything requiring native code.
- * It is safe to use in places that need simple segmented string path functionality.
+ * <p>Path fragments are either absolute or relative.
+ *
+ * <p>Strings are normalized with '.' and '..' removed and resolved (if possible), any multiple
+ * slashes ('/') removed, and any trailing slash also removed. Windows drive letters are uppercased.
+ * The current implementation does not touch the incoming path string unless the string actually
+ * needs to be normalized.
  *
  * <p>There is some limited support for Windows-style paths. Most importantly, drive identifiers in
  * front of a path (c:/abc) are supported and such paths are correctly recognized as absolute, as
  * are paths with backslash separators (C:\\foo\\bar). However, advanced Windows-style features like
- * \\\\network\\paths and \\\\?\\unc\\paths are not supported.
+ * \\\\network\\paths and \\\\?\\unc\\paths are not supported. We are currently using forward
+ * slashes ('/') even on Windows.
+ *
+ * <p>Mac and Windows path fragments are case insensitive.
  */
-@Immutable
-@javax.annotation.concurrent.Immutable
-@ThreadSafe
-public abstract class PathFragment
+public final class PathFragment
     implements Comparable<PathFragment>,
         Serializable,
-        SkylarkPrintable,
         FileType.HasFileType,
+        SkylarkPrintable,
         CommandLineItem {
-  private static final Helper HELPER =
-      OS.getCurrent() == OS.WINDOWS ? WindowsPathFragment.HELPER : UnixPathFragment.HELPER;
-
-  public static final char SEPARATOR_CHAR = HELPER.getPrimarySeparatorChar();
+  private static final OsPathPolicy OS = OsPathPolicy.getFilePathOs();
 
-  public static final int INVALID_SEGMENT = -1;
-
-  public static final String ROOT_DIR = "/";
-
-  /** An empty path fragment. */
   public static final PathFragment EMPTY_FRAGMENT = create("");
+  public static final char SEPARATOR_CHAR = OS.getSeparator();
+  public static final int INVALID_SEGMENT = -1;
 
-  /** The path fragment representing the root directory. */
-  public static final PathFragment ROOT_FRAGMENT = create(ROOT_DIR);
+  private final String path;
+  private final int driveStrLength; // 0 for relative paths, 1 on Unix, 3 on Windows
 
   public static final ObjectCodec<PathFragment> CODEC = new PathFragmentCodec();
 
-  /**
-   * A helper object for manipulating the various internal {@link PathFragment} implementations.
-   *
-   * <p>There will be exactly one {@link Helper} instance used to manipulate all the {@link
-   * PathFragment} instances (see {@link PathFragment#HELPER}). All of the various {@link Helper}
-   * and {@link PathFragment} implementations may assume this property.
-   */
-  protected abstract static class Helper {
-    /**
-     * Returns whether the two given arrays of segments have the same length and should be
-     * considered have logically equal contents.
-     */
-    protected final boolean segmentsEqual(String[] segments1, String[] segments2) {
-      return segments1.length == segments2.length
-          && segmentsEqual(segments1.length, segments1, 0, segments2);
-    }
-
-    /**
-     * Returns whether the {@code length} segments in {@code segments1}, starting at {@code offset1}
-     * should be considered to be logically equal to the first {@code length} segments in {@code
-     * segments2}.
-     */
-    abstract boolean segmentsEqual(int length, String[] segments1, int offset1, String[] segments2);
-
-    /** Returns the comparison result of two {@link PathFragment} instances. */
-    protected abstract int compare(PathFragment pathFragment1, PathFragment pathFragment2);
-
-    /** Returns a fresh {@link PathFragment} instance from the given path string. */
-    abstract PathFragment create(String path);
-    /**
-     * Returns a fresh {@link PathFragment} instance from the given information, taking ownership of
-     * {@code segments} and assuming the {@link String}s within have already been interned.
-     */
-    abstract PathFragment createAlreadyInterned(
-        char driveLetter, boolean isAbsolute, String[] segments);
-
-    /** Returns whether {@code c} is a path separator. */
-    abstract boolean isSeparator(char c);
-    /** Returns the primary path separator. */
-    abstract char getPrimarySeparatorChar();
-    /** Return whether the given {@code path} contains a path separator. */
-    abstract boolean containsSeparatorChar(String path);
-
-    /**
-     * Splits the given {@code toSegment} into path segments, starting at the given {@code offset}.
-     */
-    protected final String[] segment(String toSegment, int offset) {
-      int length = toSegment.length();
-
-      // We make two passes through the array of characters: count & alloc,
-      // because simply using ArrayList was a bottleneck showing up during profiling.
-      int seg = 0;
-      int start = offset;
-      for (int i = offset; i < length; i++) {
-        if (isSeparator(toSegment.charAt(i))) {
-          if (i > start) { // to skip repeated separators
-            seg++;
-          }
-          start = i + 1;
-        }
-      }
-      if (start < length) {
-        seg++;
-      }
-      String[] result = new String[seg];
-      seg = 0;
-      start = offset;
-      for (int i = offset; i < length; i++) {
-        if (isSeparator(toSegment.charAt(i))) {
-          if (i > start) { // to skip repeated separators
-            result[seg] = StringCanonicalizer.intern(toSegment.substring(start, i));
-            seg++;
-          }
-          start = i + 1;
-        }
-      }
-      if (start < length) {
-        result[seg] = StringCanonicalizer.intern(toSegment.substring(start, length));
-      }
-      return result;
-    }
-  }
-
-  /** Lower-level API. Create a PathFragment, interning segments. */
-  public static PathFragment create(char driveLetter, boolean isAbsolute, String[] segments) {
-    String[] internedSegments = new String[segments.length];
-    for (int i = 0; i < segments.length; i++) {
-      internedSegments[i] = StringCanonicalizer.intern(segments[i]);
-    }
-    return createAlreadyInterned(driveLetter, isAbsolute, internedSegments);
-  }
-
-  /** Same as {@link #create(char, boolean, String[])}, except for {@link List}s of segments. */
-  public static PathFragment create(char driveLetter, boolean isAbsolute, List<String> segments) {
-    String[] internedSegments = new String[segments.size()];
-    for (int i = 0; i < segments.size(); i++) {
-      internedSegments[i] = StringCanonicalizer.intern(segments.get(i));
-    }
-    return createAlreadyInterned(driveLetter, isAbsolute, internedSegments);
-  }
-
-  /**
-   * Construct a PathFragment from a java.io.File, which is an absolute or
-   * relative UNIX path.  Does not support Windows-style Files.
-   */
-  public static PathFragment create(File path) {
-    return HELPER.create(path.getPath());
-  }
-
-  /**
-   * Construct a PathFragment from a string, which is an absolute or relative UNIX or Windows path.
-   */
+  /** Creates a new normalized path fragment. */
   public static PathFragment create(String path) {
-    return HELPER.create(path);
+    int normalizationLevel = OS.needsToNormalize(path);
+    String normalizedPath =
+        normalizationLevel != OsPathPolicy.NORMALIZED
+            ? OS.normalize(path, normalizationLevel)
+            : path;
+    int driveStrLength = OS.getDriveStrLength(normalizedPath);
+    return new PathFragment(normalizedPath, driveStrLength);
   }
 
   /**
-   * Constructs a PathFragment, taking ownership of {@code segments} and assuming the {@link
-   * String}s within have already been interned.
+   * Creates a new path fragment, where the caller promises that the path is normalized.
    *
-   * <p>Package-private because it does not perform a defensive copy of the segments array. Used
-   * here in PathFragment, and by Path.asFragment() and Path.relativeTo().
+   * <p>WARNING! Make sure the path fragment is in fact already normalized. The rest of the code
+   * assumes this is the case.
    */
-  static PathFragment createAlreadyInterned(
-      char driveLetter, boolean isAbsolute, String[] segments) {
-    return HELPER.createAlreadyInterned(driveLetter, isAbsolute, segments);
-  }
-
-  /** Returns whether the current {@code path} contains a path separator. */
-  static boolean containsSeparator(String path) {
-    return HELPER.containsSeparatorChar(path);
+  public static PathFragment createAlreadyNormalized(String normalizedPath) {
+    int driveStrLength = OS.getDriveStrLength(normalizedPath);
+    return createAlreadyNormalized(normalizedPath, driveStrLength);
   }
 
   /**
-   * Construct a PathFragment from a sequence of other PathFragments. The new fragment will be
-   * absolute iff the first fragment was absolute.
+   * Creates a new path fragment, where the caller promises that the path is normalized.
+   *
+   * <p>Should only be used internally.
    */
-  // TODO(bazel-team): Most usages of this method are wasteful from a garbage perspective. Refactor
-  // to something better.
-  public static PathFragment create(PathFragment first, PathFragment second, PathFragment... more) {
-    String[] segments = new String[sumLengths(first, second, more)];
-    int offset = 0;
-    offset += addSegmentsTo(segments, offset, first);
-    offset += addSegmentsTo(segments, offset, second);
-    for (PathFragment fragment : more) {
-      offset += addSegmentsTo(segments, offset, fragment);
-    }
-    boolean isAbsolute = first.isAbsolute();
-    char driveLetter = first.getDriveLetter();
-    return HELPER.createAlreadyInterned(driveLetter, isAbsolute, segments);
+  static PathFragment createAlreadyNormalized(String normalizedPath, int driveStrLength) {
+    return new PathFragment(normalizedPath, driveStrLength);
   }
 
-  // Medium sized builds can easily hold millions of live PathFragments, so the per-instance size of
-  // PathFragment is a concern.
-  //
-  // We have two oop-sized fields (segments, path), and one 4-byte-sized one (hashCode).
-  //
-  // If Blaze is run on a jvm with -XX:+UseCompressedOops, each PathFragment instance is 24 bytes
-  // and so adding any additional field will increase the per-instance size to at least 32 bytes.
-  //
-  // If Blaze is run on a jvm with -XX:-UseCompressedOops, each PathFragment instance is 32 bytes
-  // and so adding any additional field will increase the per-instance size to at least 40 bytes.
-  //
-  // Therefore, do not add any additional fields unless you have considered the memory implications.
-
-  // The individual path components.
-  // Does *not* include the Windows drive letter.
-  protected final String[] segments;
-
-  // hashCode and path are lazily initialized but semantically immutable.
-  private int hashCode;
-  private String path;
-
-  protected PathFragment(String[] segments) {
-    this.segments = segments;
-  }
-
-  private static int addSegmentsTo(String[] segments, int offset, PathFragment fragment) {
-    int count = fragment.segmentCount();
-    System.arraycopy(fragment.segments, 0, segments, offset, count);
-    return count;
+  /** This method expects path to already be normalized. */
+  private PathFragment(String path, int driveStrLength) {
+    this.path = Preconditions.checkNotNull(path);
+    this.driveStrLength = driveStrLength;
   }
 
-  private static int sumLengths(PathFragment first, PathFragment second, PathFragment[] more) {
-    int total = first.segmentCount() + second.segmentCount();
-    for (PathFragment fragment : more) {
-      total += fragment.segmentCount();
-    }
-    return total;
+  public String getPathString() {
+    return path;
   }
 
-  protected Object writeReplace() {
-    return new PathFragmentSerializationProxy(toString());
+  public boolean isEmpty() {
+    return path.isEmpty();
   }
 
-  protected void readObject(ObjectInputStream stream) throws InvalidObjectException {
-    throw new InvalidObjectException("Serialization is allowed only by proxy");
+  int getDriveStrLength() {
+    return driveStrLength;
   }
 
   /**
-   * Returns the path string using '/' as the name-separator character.  Returns "" if the path
-   * is both relative and empty.
+   * If called on a {@link PathFragment} instance for a mount name (eg. '/' or 'C:/'), the empty
+   * string is returned.
+   *
+   * <p>This operation allocates a new string.
    */
-  public String getPathString() {
-    // Double-checked locking works, even without volatile, because path is a String, according to:
-    // http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
-    if (path == null) {
-      synchronized (this) {
-        if (path == null) {
-          path = StringCanonicalizer.intern(joinSegments(HELPER.getPrimarySeparatorChar()));
-        }
-      }
-    }
-    return path;
+  public String getBaseName() {
+    int lastSeparator = path.lastIndexOf(SEPARATOR_CHAR);
+    return lastSeparator < driveStrLength
+        ? path.substring(driveStrLength)
+        : path.substring(lastSeparator + 1);
   }
 
   /**
-   * Returns "." if the path fragment is both relative and empty, or {@link
-   * #getPathString} otherwise.
+   * Returns a {@link PathFragment} instance representing the relative path between this {@link
+   * PathFragment} and the given {@link PathFragment}.
+   *
+   * <p>If the passed path is absolute it is returned untouched. This can be useful to resolve
+   * symlinks.
    */
-  // TODO(bazel-team): Change getPathString to do this - this behavior makes more sense.
-  public String getSafePathString() {
-    return (!isAbsolute() && (segmentCount() == 0)) ? "." : getPathString();
+  public PathFragment getRelative(PathFragment other) {
+    Preconditions.checkNotNull(other);
+    // Fast-path: The path fragment is already normal, use cheaper normalization check
+    String otherStr = other.path;
+    return getRelative(otherStr, other.getDriveStrLength(), OS.needsToNormalizeSuffix(otherStr));
   }
 
   /**
-   * Returns the path string using '/' as the name-separator character, but do so in a way
-   * unambiguously recognizable as path. In other words, return "." for relative and empty paths,
-   * and prefix relative paths with one segment by "./".
+   * Returns a {@link PathFragment} instance representing the relative path between this {@link
+   * PathFragment} and the given path.
    *
-   * <p>In this way, a shell will always interpret such a string as path (absolute or relative to
-   * the working directory) and not as command to be searched for in the search path.
+   * <p>See {@link #getRelative(PathFragment)} for details.
    */
-  public String getCallablePathString() {
-    if (isAbsolute()) {
-      return getPathString();
-    } else if (segmentCount() == 0) {
-      return ".";
-    } else if (segmentCount() == 1) {
-      return "." + HELPER.getPrimarySeparatorChar() + getPathString();
-    } else {
-      return getPathString();
-    }
+  public PathFragment getRelative(String other) {
+    Preconditions.checkNotNull(other);
+    return getRelative(other, OS.getDriveStrLength(other), OS.needsToNormalize(other));
   }
 
-  /**
-  * Throws {@link IllegalArgumentException} if {@code paths} contains any paths that
-  * are equal to {@code startingWithPath} or that are not beneath {@code startingWithPath}.
-  */
-  public static void checkAllPathsAreUnder(Iterable<PathFragment> paths,
-      PathFragment startingWithPath) {
-    for (PathFragment path : paths) {
-      Preconditions.checkArgument(
-          !path.equals(startingWithPath) && path.startsWith(startingWithPath),
-              "%s is not beneath %s", path, startingWithPath);
+  private PathFragment getRelative(String other, int otherDriveStrLength, int normalizationLevel) {
+    if (path.isEmpty()) {
+      return create(other);
     }
-  }
-
-  private String joinSegments(char separatorChar) {
-    if (segments.length == 0 && isAbsolute()) {
-      return windowsVolume() + ROOT_DIR;
+    if (other.isEmpty()) {
+      return this;
     }
-
-    // Profile driven optimization:
-    // Preallocate a size determined by the number of segments, so that
-    // we do not have to expand the capacity of the StringBuilder.
-    // Heuristically, this estimate is right for about 99% of the time.
-    int estimateSize =
-        ((getDriveLetter() != '\0') ? 2 : 0)
-            + ((segments.length == 0) ? 0 : (segments.length + 1) * 20);
-    StringBuilder result = new StringBuilder(estimateSize);
-    if (isAbsolute()) {
-      // Only print the Windows volume label if the PathFragment is absolute. Do not print relative
-      // Windows paths like "C:foo/bar", it would break all kinds of things, e.g. glob().
-      result.append(windowsVolume());
-    }
-    boolean initialSegment = true;
-    for (String segment : segments) {
-      if (!initialSegment || isAbsolute()) {
-        result.append(separatorChar);
-      }
-      initialSegment = false;
-      result.append(segment);
+    // This is an absolute path, simply return it
+    if (otherDriveStrLength > 0) {
+      String normalizedPath =
+          normalizationLevel != OsPathPolicy.NORMALIZED
+              ? OS.normalize(other, normalizationLevel)
+              : other;
+      return new PathFragment(normalizedPath, otherDriveStrLength);
+    }
+    String newPath;
+    if (path.length() == driveStrLength) {
+      newPath = path + other;
+    } else {
+      newPath = path + '/' + other;
     }
-    return result.toString();
+    newPath =
+        normalizationLevel != OsPathPolicy.NORMALIZED
+            ? OS.normalize(newPath, normalizationLevel)
+            : newPath;
+    return new PathFragment(newPath, driveStrLength);
   }
 
-  /**
-   * Return true iff none of the segments are either "." or "..".
-   */
-  public boolean isNormalized() {
-    for (String segment : segments) {
-      if (segment.equals(".") || segment.equals("..")) {
-        return false;
-      }
+  public PathFragment getChild(String baseName) {
+    checkBaseName(baseName);
+    String newPath;
+    if (path.length() == driveStrLength) {
+      newPath = path + baseName;
+    } else {
+      newPath = path + '/' + baseName;
     }
-    return true;
-  }
-
-  public static boolean isNormalized(String path) {
-    return PathFragment.create(path).isNormalized();
+    return new PathFragment(newPath, driveStrLength);
   }
 
   /**
-   * Normalizes the path fragment: removes "." and ".." segments if possible
-   * (if there are too many ".." segments, the resulting PathFragment will still
-   * start with "..").
+   * Returns the parent directory of this {@link PathFragment}.
+   *
+   * <p>If this is called on an single directory for a relative path, this returns an empty relative
+   * path. If it's called on a root (like '/') or the empty string, it returns null.
    */
-  public PathFragment normalize() {
-    String[] scratchSegments = new String[segments.length];
-    int segmentCount = 0;
-
-    for (String segment : segments) {
-      switch (segment) {
-        case ".":
-          // Just discard it
-          break;
-        case "..":
-          if (segmentCount > 0 && !scratchSegments[segmentCount - 1].equals("..")) {
-            // Remove the last segment, if there is one and it is not "..". This
-            // means that the resulting PathFragment can still contain ".."
-            // segments at the beginning.
-            segmentCount--;
-          } else {
-            scratchSegments[segmentCount++] = segment;
-          }
-          break;
-        default:
-          scratchSegments[segmentCount++] = segment;
+  @Nullable
+  public PathFragment getParentDirectory() {
+    int lastSeparator = path.lastIndexOf(SEPARATOR_CHAR);
+
+    // For absolute paths we need to specially handle when we hit root
+    // Relative paths can't hit this path as driveStrLength == 0
+    if (driveStrLength > 0) {
+      if (lastSeparator < driveStrLength) {
+        if (path.length() > driveStrLength) {
+          String newPath = path.substring(0, driveStrLength);
+          return new PathFragment(newPath, driveStrLength);
+        } else {
+          return null;
+        }
+      }
+    } else {
+      if (lastSeparator == -1) {
+        if (!path.isEmpty()) {
+          return EMPTY_FRAGMENT;
+        } else {
+          return null;
+        }
       }
     }
-
-    if (segmentCount == segments.length) {
-      // Optimization, no new PathFragment needs to be created.
-      return this;
-    }
-
-    return HELPER.createAlreadyInterned(
-        getDriveLetter(), isAbsolute(), subarray(scratchSegments, 0, segmentCount));
+    String newPath = path.substring(0, lastSeparator);
+    return new PathFragment(newPath, driveStrLength);
   }
 
   /**
-   * Returns the path formed by appending the relative or absolute path fragment
-   * {@code otherFragment} to this path.
+   * Returns the {@link PathFragment} relative to the base {@link PathFragment}.
    *
-   * <p>If {@code otherFragment} is absolute, the current path will be ignored;
-   * otherwise, they will be concatenated. This is a purely syntactic operation,
-   * with no path normalization or I/O performed.
+   * <p>For example, <code>FilePath.create("foo/bar/wiz").relativeTo(FilePath.create("foo"))</code>
+   * returns <code>"bar/wiz"</code>.
+   *
+   * <p>If the {@link PathFragment} is not a child of the passed {@link PathFragment} an {@link
+   * IllegalArgumentException} is thrown. In particular, this will happen whenever the two {@link
+   * PathFragment} instances aren't both absolute or both relative.
    */
-  public PathFragment getRelative(PathFragment otherFragment) {
-    if (otherFragment == EMPTY_FRAGMENT) {
+  public PathFragment relativeTo(PathFragment base) {
+    Preconditions.checkNotNull(base);
+    if (isAbsolute() != base.isAbsolute()) {
+      throw new IllegalArgumentException(
+          "Cannot relativize an absolute and a non-absolute path pair");
+    }
+    String basePath = base.path;
+    if (!OS.startsWith(path, basePath)) {
+      throw new IllegalArgumentException(
+          String.format("Path '%s' is not under '%s', cannot relativize", this, base));
+    }
+    int bn = basePath.length();
+    if (bn == 0) {
       return this;
     }
-
-    if (otherFragment.isAbsolute()) {
-      char driveLetter = getDriveLetter();
-      return driveLetter == '\0' || otherFragment.getDriveLetter() != '\0'
-          ? otherFragment
-          : createAlreadyInterned(driveLetter, true, otherFragment.segments);
+    if (path.length() == bn) {
+      return EMPTY_FRAGMENT;
+    }
+    final int lastSlashIndex;
+    if (basePath.charAt(bn - 1) == '/') {
+      lastSlashIndex = bn - 1;
     } else {
-      return create(this, otherFragment);
+      lastSlashIndex = bn;
+    }
+    if (path.charAt(lastSlashIndex) != '/') {
+      throw new IllegalArgumentException(
+          String.format("Path '%s' is not under '%s', cannot relativize", this, base));
     }
+    String newPath = path.substring(lastSlashIndex + 1);
+    return new PathFragment(newPath, 0 /* Always a relative path */);
   }
 
-  /**
-   * Returns the path formed by appending the relative or absolute string
-   * {@code path} to this path.
-   *
-   * <p>If the given path string is absolute, the current path will be ignored;
-   * otherwise, they will be concatenated. This is a purely syntactic operation,
-   * with no path normalization or I/O performed.
-   */
-  public PathFragment getRelative(String path) {
-    return getRelative(create(path));
+  public PathFragment relativeTo(String base) {
+    return relativeTo(PathFragment.create(base));
   }
 
   /**
-   * Returns the path formed by appending the single non-special segment "baseName" to this path.
+   * Returns whether this path is an ancestor of another path.
    *
-   * <p>You should almost always use {@link #getRelative} instead, which has the same performance
-   * characteristics if the given name is a valid base name, and which also works for '.', '..', and
-   * strings containing '/'.
+   * <p>If this == other, true is returned.
    *
-   * @throws IllegalArgumentException if {@code baseName} is not a valid base name according to
-   *     {@link #checkBaseName}
+   * <p>An absolute path can never be an ancestor of a relative path, and vice versa.
    */
-  public PathFragment getChild(String baseName) {
-    checkBaseName(baseName);
-    baseName = StringCanonicalizer.intern(baseName);
-    String[] newSegments = Arrays.copyOf(segments, segments.length + 1);
-    newSegments[newSegments.length - 1] = baseName;
-    return createAlreadyInterned(getDriveLetter(), isAbsolute(), newSegments);
+  public boolean startsWith(PathFragment other) {
+    Preconditions.checkNotNull(other);
+    if (other.path.length() > path.length()) {
+      return false;
+    }
+    if (driveStrLength != other.driveStrLength) {
+      return false;
+    }
+    if (!OS.startsWith(path, other.path)) {
+      return false;
+    }
+    return path.length() == other.path.length()
+        || other.path.length() == driveStrLength
+        || path.charAt(other.path.length()) == SEPARATOR_CHAR;
   }
 
   /**
-   * Returns the last segment of this path, or "" for the empty fragment.
+   * Returns true iff {@code suffix}, considered as a list of path segments, is relative and a
+   * suffix of {@code this}, or both are absolute and equal.
+   *
+   * <p>This is a reflexive, transitive, anti-symmetric relation (i.e. a partial order)
    */
-  public String getBaseName() {
-    return (segments.length == 0) ? "" : segments[segments.length - 1];
+  public boolean endsWith(PathFragment other) {
+    Preconditions.checkNotNull(other);
+    if (other.path.length() > path.length()) {
+      return false;
+    }
+    if (other.isAbsolute()) {
+      return this.equals(other);
+    }
+    if (!OS.endsWith(path, other.path)) {
+      return false;
+    }
+    return path.length() == other.path.length()
+        || other.path.length() == 0
+        || path.charAt(path.length() - other.path.length() - 1) == SEPARATOR_CHAR;
   }
 
-  /**
-   * Returns the file extension of this path, excluding the period, or "" if there is no extension.
-   */
-  public String getFileExtension() {
-    String baseName = getBaseName();
+  public boolean isAbsolute() {
+    return driveStrLength > 0;
+  }
 
-    int lastIndex = baseName.lastIndexOf('.');
-    if (lastIndex != -1) {
-      return baseName.substring(lastIndex + 1);
-    }
+  public static boolean isAbsolute(String path) {
+    return OS.getDriveStrLength(path) > 0;
+  }
 
-    return "";
+  @Override
+  public String toString() {
+    return path;
   }
 
-  /**
-   * Returns a relative path fragment to this path, relative to
-   * {@code ancestorDirectory}.
-   * <p>
-   * <code>x.relativeTo(z) == y</code> implies
-   * <code>z.getRelative(y) == x</code>.
-   * <p>
-   * For example, <code>"foo/bar/wiz".relativeTo("foo")</code>
-   * returns <code>"bar/wiz"</code>.
-   */
-  public PathFragment relativeTo(PathFragment ancestorDirectory) {
-    String[] ancestorSegments = ancestorDirectory.segments();
-    int ancestorLength = ancestorSegments.length;
+  @Override
+  public void repr(SkylarkPrinter printer) {
+    printer.append(path);
+  }
 
-    if (isAbsolute() != ancestorDirectory.isAbsolute() || segments.length < ancestorLength) {
-      throw new IllegalArgumentException("PathFragment " + this
-          + " is not beneath " + ancestorDirectory);
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) {
+      return true;
     }
-
-    if (!HELPER.segmentsEqual(ancestorLength, segments, 0, ancestorSegments)) {
-      throw new IllegalArgumentException(
-          "PathFragment " + this + " is not beneath " + ancestorDirectory);
+    if (o == null || getClass() != o.getClass()) {
+      return false;
     }
-
-    int length = segments.length - ancestorLength;
-    String[] resultSegments = subarray(segments, ancestorLength, length);
-    return createAlreadyInterned('\0', false, resultSegments);
+    return OS.equals(this.path, ((PathFragment) o).path);
   }
 
-  /**
-   * Returns a relative path fragment to this path, relative to {@code path}.
-   */
-  public PathFragment relativeTo(String path) {
-    return relativeTo(create(path));
+  @Override
+  public int hashCode() {
+    return OS.hash(this.path);
   }
 
-  /**
-   * Returns a new PathFragment formed by appending {@code newName} to the
-   * parent directory. Null is returned iff this method is called on a
-   * PathFragment with zero segments.  If {@code newName} designates an absolute path,
-   * the value of {@code this} will be ignored and a PathFragment corresponding to
-   * {@code newName} will be returned.  This behavior is consistent with the behavior of
-   * {@link #getRelative(String)}.
-   */
-  public PathFragment replaceName(String newName) {
-    return segments.length == 0 ? null : getParentDirectory().getRelative(newName);
+  @Override
+  public int compareTo(PathFragment o) {
+    return OS.compare(this.path, o.path);
   }
 
-  /**
-   * Returns a path representing the parent directory of this path,
-   * or null iff this Path represents the root of the filesystem.
-   *
-   * <p>Note: This method DOES NOT normalize ".."  and "." path segments.
-   */
-  public PathFragment getParentDirectory() {
-    return segments.length == 0 ? null : subFragment(0, segments.length - 1);
-  }
+  ////////////////////////////////////////////////////////////////////////
 
   /**
-   * Returns true iff {@code prefix}, considered as a list of path segments, is
-   * a prefix of {@code this}, and that they are both relative or both
-   * absolute.
+   * Returns the number of segments in this path.
    *
-   * <p>This is a reflexive, transitive, anti-symmetric relation (i.e. a partial
-   * order)
+   * <p>This operation is O(N) on the length of the string.
    */
-  public boolean startsWith(PathFragment prefix) {
-    if (isAbsolute() != prefix.isAbsolute()
-        || this.segments.length < prefix.segments.length
-        || (isAbsolute() && getDriveLetter() != prefix.getDriveLetter())) {
-      return false;
+  public int segmentCount() {
+    int n = path.length();
+    int segmentCount = 0;
+    int i;
+    for (i = driveStrLength; i < n; ++i) {
+      if (path.charAt(i) == SEPARATOR_CHAR) {
+        ++segmentCount;
+      }
     }
-    return HELPER.segmentsEqual(prefix.segments.length, segments, 0, prefix.segments);
-  }
-
-  /**
-   * Returns true iff {@code suffix}, considered as a list of path segments, is
-   * relative and a suffix of {@code this}, or both are absolute and equal.
-   *
-   * <p>This is a reflexive, transitive, anti-symmetric relation (i.e. a partial
-   * order)
-   */
-  public boolean endsWith(PathFragment suffix) {
-    if ((suffix.isAbsolute() && !suffix.equals(this))
-        || this.segments.length < suffix.segments.length) {
-      return false;
+    // Add last segment if one exists.
+    if (i > driveStrLength) {
+      ++segmentCount;
     }
-    int offset = this.segments.length - suffix.segments.length;
-    return HELPER.segmentsEqual(suffix.segments.length, segments, offset, suffix.segments);
-  }
-
-  private static String[] subarray(String[] array, int start, int length) {
-    String[] subarray = new String[length];
-    System.arraycopy(array, start, subarray, 0, length);
-    return subarray;
+    return segmentCount;
   }
 
   /**
-   * Returns a new path fragment that is a sub fragment of this one.
-   * The sub fragment begins at the specified <code>beginIndex</code> segment
-   * and ends at the segment at index <code>endIndex - 1</code>. Thus the number
-   * of segments in the new PathFragment is <code>endIndex - beginIndex</code>.
+   * Returns the specified segment of this path; index must be positive and less than numSegments().
    *
-   * @param      beginIndex   the beginning index, inclusive.
-   * @param      endIndex     the ending index, exclusive.
-   * @return     the specified sub fragment, never null.
-   * @exception  IndexOutOfBoundsException  if the
-   *             <code>beginIndex</code> is negative, or
-   *             <code>endIndex</code> is larger than the length of
-   *             this <code>String</code> object, or
-   *             <code>beginIndex</code> is larger than
-   *             <code>endIndex</code>.
+   * <p>This operation is O(N) on the length of the string.
    */
-  public PathFragment subFragment(int beginIndex, int endIndex) {
-    int count = segments.length;
-    if ((beginIndex < 0) || (beginIndex > endIndex) || (endIndex > count)) {
-      throw new IndexOutOfBoundsException(String.format("path: %s, beginIndex: %d endIndex: %d",
-          toString(), beginIndex, endIndex));
+  public String getSegment(int index) {
+    int n = path.length();
+    int segmentCount = 0;
+    int i;
+    for (i = driveStrLength; i < n && segmentCount < index; ++i) {
+      if (path.charAt(i) == SEPARATOR_CHAR) {
+        ++segmentCount;
+      }
+    }
+    int starti = i;
+    for (; i < n; ++i) {
+      if (path.charAt(i) == SEPARATOR_CHAR) {
+        break;
+      }
     }
-    boolean isAbsolute = (beginIndex == 0) && isAbsolute();
-    return ((beginIndex == 0) && (endIndex == count))
-        ? this
-        : createAlreadyInterned(
-            getDriveLetter(), isAbsolute, subarray(segments, beginIndex, endIndex - beginIndex));
+    // Add last segment if one exists.
+    if (i > driveStrLength) {
+      ++segmentCount;
+    }
+    int endi = i;
+    if (index < 0 || index >= segmentCount) {
+      throw new IllegalArgumentException("Illegal segment index: " + index);
+    }
+    return path.substring(starti, endi);
   }
 
   /**
    * Returns a new path fragment that is a sub fragment of this one. The sub fragment begins at the
-   * specified <code>beginIndex</code> segment and contains the rest of the original path fragment.
+   * specified <code>beginIndex</code> segment and ends at the segment at index <code>endIndex - 1
+   * </code>. Thus the number of segments in the new PathFragment is <code>endIndex - beginIndex
+   * </code>.
+   *
+   * <p>This operation is O(N) on the length of the string.
    *
    * @param beginIndex the beginning index, inclusive.
+   * @param endIndex the ending index, exclusive.
    * @return the specified sub fragment, never null.
    * @exception IndexOutOfBoundsException if the <code>beginIndex</code> is negative, or <code>
    *     endIndex</code> is larger than the length of this <code>String</code> object, or <code>
    *     beginIndex</code> is larger than <code>endIndex</code>.
    */
-  public PathFragment subFragment(int beginIndex) {
-    return subFragment(beginIndex, segments.length);
+  public PathFragment subFragment(int beginIndex, int endIndex) {
+    if (beginIndex < 0 || beginIndex > endIndex) {
+      throw new IndexOutOfBoundsException(
+          String.format("path: %s, beginIndex: %d endIndex: %d", toString(), beginIndex, endIndex));
+    }
+    return subFragmentImpl(beginIndex, endIndex);
   }
 
-  /**
-   * Returns true iff the path represented by this object is absolute.
-   *
-   * <p>True both for UNIX-style absolute paths ("/foo") and Windows-style ("C:/foo"). False for a
-   * Windows-style volume label ("C:") which is actually a relative path.
-   */
-  public abstract boolean isAbsolute();
+  public PathFragment subFragment(int beginIndex) {
+    if (beginIndex < 0) {
+      throw new IndexOutOfBoundsException(
+          String.format("path: %s, beginIndex: %d", toString(), beginIndex));
+    }
+    return subFragmentImpl(beginIndex, -1);
+  }
 
-  public static boolean isAbsolute(String path) {
-    return PathFragment.create(path).isAbsolute();
+  private PathFragment subFragmentImpl(int beginIndex, int endIndex) {
+    int n = path.length();
+    int segmentIndex = 0;
+    int i;
+    for (i = driveStrLength; i < n && segmentIndex < beginIndex; ++i) {
+      if (path.charAt(i) == SEPARATOR_CHAR) {
+        ++segmentIndex;
+      }
+    }
+    int starti = i;
+    if (segmentIndex < endIndex) {
+      for (; i < n; ++i) {
+        if (path.charAt(i) == SEPARATOR_CHAR) {
+          ++segmentIndex;
+          if (segmentIndex == endIndex) {
+            break;
+          }
+        }
+      }
+    } else if (endIndex == -1) {
+      i = path.length();
+    }
+    int endi = i;
+    // Add last segment if one exists for verification
+    if (i == n && i > driveStrLength) {
+      ++segmentIndex;
+    }
+    if (beginIndex > segmentIndex || endIndex > segmentIndex) {
+      throw new IndexOutOfBoundsException(
+          String.format("path: %s, beginIndex: %d endIndex: %d", toString(), beginIndex, endIndex));
+    }
+    // If beginIndex is 0 we include the drive. Very odd semantics.
+    int driveStrLength = 0;
+    if (beginIndex == 0) {
+      starti = 0;
+      driveStrLength = this.driveStrLength;
+      endi = Math.max(endi, driveStrLength);
+    }
+    return new PathFragment(path.substring(starti, endi), driveStrLength);
   }
 
   /**
@@ -647,62 +487,104 @@ public abstract class PathFragment
    * modified.
    */
   String[] segments() {
+    int segmentCount = segmentCount();
+    String[] segments = new String[segmentCount];
+    int segmentIndex = 0;
+    int nexti = driveStrLength;
+    int n = path.length();
+    for (int i = driveStrLength; i < n; ++i) {
+      if (path.charAt(i) == SEPARATOR_CHAR) {
+        segments[segmentIndex++] = path.substring(nexti, i);
+        nexti = i + 1;
+      }
+    }
+    // Add last segment if one exists.
+    if (nexti < n) {
+      segments[segmentIndex] = path.substring(nexti);
+    }
     return segments;
   }
 
+  /**
+   * Returns a list of the segments.
+   *
+   * <p>This operation is O(N) on the length of the string.
+   */
   public ImmutableList<String> getSegments() {
-    return ImmutableList.copyOf(segments);
+    return ImmutableList.copyOf(segments());
   }
 
-  public abstract String windowsVolume();
-
-  /** Return the drive letter or '\0' if not applicable. */
-  // TODO(bazel-team): This doesn't need to pollute the PathFragment interface (ditto for
-  // windowsVolume).
-  public abstract char getDriveLetter();
+  public int getFirstSegment(Set<String> values) {
+    String[] segments = segments();
+    for (int i = 0; i < segments.length; ++i) {
+      if (values.contains(segments[i])) {
+        return i;
+      }
+    }
+    return INVALID_SEGMENT;
+  }
 
-  public boolean isEmpty() {
-    return segments.length == 0;
+  /** Returns the path string, or '.' if the path is empty. */
+  public String getSafePathString() {
+    return !path.isEmpty() ? path : ".";
   }
 
   /**
-   * Returns the number of segments in this path.
+   * Returns the path string using '/' as the name-separator character, but do so in a way
+   * unambiguously recognizable as path. In other words, return "." for relative and empty paths,
+   * and prefix relative paths with one segment by "./".
+   *
+   * <p>In this way, a shell will always interpret such a string as path (absolute or relative to
+   * the working directory) and not as command to be searched for in the search path.
    */
-  public int segmentCount() {
-    return segments.length;
+  public String getCallablePathString() {
+    if (isAbsolute()) {
+      return path;
+    } else if (path.isEmpty()) {
+      return ".";
+    } else if (path.indexOf(SEPARATOR_CHAR) == -1) {
+      return "." + SEPARATOR_CHAR + path;
+    } else {
+      return path;
+    }
   }
 
   /**
-   * Returns the specified segment of this path; index must be positive and
-   * less than numSegments().
+   * Returns the file extension of this path, excluding the period, or "" if there is no extension.
    */
-  public String getSegment(int index) {
-    return segments[index];
+  public String getFileExtension() {
+    int n = path.length();
+    for (int i = n - 1; i > driveStrLength; --i) {
+      char c = path.charAt(i);
+      if (c == '.') {
+        return path.substring(i + 1, n);
+      } else if (c == SEPARATOR_CHAR) {
+        break;
+      }
+    }
+    return "";
   }
 
   /**
-   * Returns the index of the first segment which equals one of the input values
-   * or {@link PathFragment#INVALID_SEGMENT} if none of the segments match.
+   * Returns a new PathFragment formed by appending {@code newName} to the parent directory. Null is
+   * returned iff this method is called on a PathFragment with zero segments. If {@code newName}
+   * designates an absolute path, the value of {@code this} will be ignored and a PathFragment
+   * corresponding to {@code newName} will be returned. This behavior is consistent with the
+   * behavior of {@link #getRelative(String)}.
    */
-  public int getFirstSegment(Set<String> values) {
-    for (int i = 0; i < segments.length; i++) {
-      if (values.contains(segments[i])) {
-        return i;
-      }
-    }
-    return INVALID_SEGMENT;
+  public PathFragment replaceName(String newName) {
+    PathFragment parent = getParentDirectory();
+    return parent != null ? parent.getRelative(newName) : null;
   }
 
   /**
-   * Returns true iff this path contains uplevel references "..".
+   * Returns the drive for an absolute path fragment.
+   *
+   * <p>On unix, this will return "/". On Windows it will return the drive letter, like "C:/".
    */
-  public boolean containsUplevelReferences() {
-    for (String segment : segments) {
-      if (segment.equals("..")) {
-        return true;
-      }
-    }
-    return false;
+  public String getDriveStr() {
+    Preconditions.checkArgument(isAbsolute());
+    return path.substring(0, driveStrLength);
   }
 
   /**
@@ -711,60 +593,129 @@ public abstract class PathFragment
    */
   public PathFragment toRelative() {
     Preconditions.checkArgument(isAbsolute());
-    return HELPER.createAlreadyInterned(getDriveLetter(), false, segments);
+    return new PathFragment(path.substring(driveStrLength), 0);
   }
 
-  @Override
-  public final int hashCode() {
-    // We use the hash code caching strategy employed by java.lang.String. There are three subtle
-    // things going on here:
-    //
-    // (1) We use a value of 0 to indicate that the hash code hasn't been computed and cached yet.
-    // Yes, this means that if the hash code is really 0 then we will "recompute" it each time. But
-    // this isn't a problem in practice since a hash code of 0 is rare.
-    //
-    // (2) Since we have no synchronization, multiple threads can race here thinking they are the
-    // first one to compute and cache the hash code.
-    //
-    // (3) Moreover, since 'hashCode' is non-volatile, the cached hash code value written from one
-    // thread may not be visible by another. Note that we don't need to worry about multiple
-    // inefficient reads of 'hashCode' on the same thread since it's non-volatile.
-    //
-    // All three of these issues are benign from a correctness perspective; in the end we have no
-    // overhead from synchronization, at the cost of potentially computing the hash code more than
-    // once.
-    if (hashCode == 0) {
-      hashCode = computeHashCode();
-    }
-    return hashCode;
-  }
-
-  protected abstract int computeHashCode();
-
-  @Override
-  public abstract boolean equals(Object other);
+  /**
+   * Returns true if this path contains uplevel references "..".
+   *
+   * <p>Since path fragments are normalized, this implies that the uplevel reference is at the start
+   * of the path fragment.
+   */
+  public boolean containsUplevelReferences() {
+    // Path is normalized, so any ".." would have to be at the very start
+    return path.startsWith("..");
+  }
 
   /**
-   * Compares two PathFragments using the lexicographical order.
+   * Returns true if the passed path contains uplevel references ".." or single-dot references "."
+   *
+   * <p>This is useful to check a string for normalization before constructing a PathFragment, since
+   * these are always normalized and will throw uplevel references away.
    */
-  @Override
-  public int compareTo(PathFragment p2) {
-    return HELPER.compare(this, p2);
+  public static boolean isNormalized(String path) {
+    return isNormalizedImpl(path, true /* lookForSameLevelReferences */);
   }
 
-  @Override
-  public String toString() {
-    return getPathString();
+  /**
+   * Returns true if the passed path contains uplevel references "..".
+   *
+   * <p>This is useful to check a string for '..' segments before constructing a PathFragment, since
+   * these are always normalized and will throw uplevel references away.
+   */
+  public static boolean containsUplevelReferences(String path) {
+    return !isNormalizedImpl(path, false /* lookForSameLevelReferences */);
+  }
+
+  private enum NormalizedImplState {
+    Base, /* No particular state, eg. an 'a' or 'L' character */
+    Separator, /* We just saw a separator */
+    Dot, /* We just saw a dot after a separator */
+    DotDot, /* We just saw two dots after a separator */
+  }
+
+  private static boolean isNormalizedImpl(String path, boolean lookForSameLevelReferences) {
+    // Starting state is equivalent to having just seen a separator
+    NormalizedImplState state = NormalizedImplState.Separator;
+    int n = path.length();
+    for (int i = 0; i < n; ++i) {
+      char c = path.charAt(i);
+      boolean isSeparator = OS.isSeparator(c);
+      switch (state) {
+        case Base:
+          if (isSeparator) {
+            state = NormalizedImplState.Separator;
+          } else {
+            state = NormalizedImplState.Base;
+          }
+          break;
+        case Separator:
+          if (isSeparator) {
+            state = NormalizedImplState.Separator;
+          } else if (c == '.') {
+            state = NormalizedImplState.Dot;
+          } else {
+            state = NormalizedImplState.Base;
+          }
+          break;
+        case Dot:
+          if (isSeparator) {
+            if (lookForSameLevelReferences) {
+              // "." segment found
+              return false;
+            }
+            state = NormalizedImplState.Separator;
+          } else if (c == '.') {
+            state = NormalizedImplState.DotDot;
+          } else {
+            state = NormalizedImplState.Base;
+          }
+          break;
+        case DotDot:
+          if (isSeparator) {
+            // ".." segment found
+            return false;
+          } else {
+            state = NormalizedImplState.Base;
+          }
+          break;
+        default:
+          throw new IllegalStateException("Unhandled state: " + state);
+      }
+    }
+    // The character just after the string is equivalent to a separator
+    switch (state) {
+      case Dot:
+        if (lookForSameLevelReferences) {
+          // "." segment found
+          return false;
+        }
+        break;
+      case DotDot:
+        return false;
+      default:
+    }
+    return true;
   }
 
-  @Override
-  public void repr(SkylarkPrinter printer) {
-    printer.append(getPathString());
+  /**
+   * Throws {@link IllegalArgumentException} if {@code paths} contains any paths that are equal to
+   * {@code startingWithPath} or that are not beneath {@code startingWithPath}.
+   */
+  public static void checkAllPathsAreUnder(
+      Iterable<PathFragment> paths, PathFragment startingWithPath) {
+    for (PathFragment path : paths) {
+      Preconditions.checkArgument(
+          !path.equals(startingWithPath) && path.startsWith(startingWithPath),
+          "%s is not beneath %s",
+          path,
+          startingWithPath);
+    }
   }
 
   @Override
   public String filePathForFileTypeMatcher() {
-    return getBaseName();
+    return path;
   }
 
   @Override
@@ -783,25 +734,13 @@ public abstract class PathFragment
     @Override
     public void serialize(PathFragment pathFragment, CodedOutputStream codedOut)
         throws IOException, SerializationException {
-      codedOut.writeInt32NoTag(pathFragment.getDriveLetter());
-      codedOut.writeBoolNoTag(pathFragment.isAbsolute());
-      codedOut.writeInt32NoTag(pathFragment.segmentCount());
-      for (int i = 0; i < pathFragment.segmentCount(); i++) {
-        stringCodec.serialize(pathFragment.getSegment(i), codedOut);
-      }
+      stringCodec.serialize(pathFragment.getPathString(), codedOut);
     }
 
     @Override
     public PathFragment deserialize(CodedInputStream codedIn)
         throws IOException, SerializationException {
-      char driveLetter = (char) codedIn.readInt32();
-      boolean isAbsolute = codedIn.readBool();
-      int segmentCount = codedIn.readInt32();
-      String[] segments = new String[segmentCount];
-      for (int i = 0; i < segmentCount; i++) {
-        segments[i] = stringCodec.deserialize(codedIn);
-      }
-      return PathFragment.create(driveLetter, isAbsolute, segments);
+      return PathFragment.createAlreadyNormalized(stringCodec.deserialize(codedIn));
     }
   }
 
@@ -816,4 +755,8 @@ public abstract class PathFragment
       throw new IllegalArgumentException("baseName must not contain a slash: '" + baseName + "'");
     }
   }
+
+  private Object writeReplace() {
+    return new PathFragmentSerializationProxy(path);
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/PathFragmentSerializationProxy.java b/src/main/java/com/google/devtools/build/lib/vfs/PathFragmentSerializationProxy.java
index 39aefd1318..4ba66be7fc 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/PathFragmentSerializationProxy.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/PathFragmentSerializationProxy.java
@@ -17,7 +17,6 @@ import java.io.Externalizable;
 import java.io.IOException;
 import java.io.ObjectOutput;
 
-
 /**
  * A helper proxy for serializing immutable {@link PathFragment} objects.
  */
@@ -44,7 +43,7 @@ public final class PathFragmentSerializationProxy implements Externalizable {
   }
 
   private Object readResolve() {
-    return PathFragment.create(pathFragmentString);
+    return PathFragment.createAlreadyNormalized(pathFragmentString);
   }
 }
 
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
deleted file mode 100644
index fd783c5929..0000000000
--- a/src/main/java/com/google/devtools/build/lib/vfs/PathTrie.java
+++ /dev/null
@@ -1,82 +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.vfs;
-
-import com.google.common.base.Preconditions;
-import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
-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/RootedPath.java b/src/main/java/com/google/devtools/build/lib/vfs/RootedPath.java
index 9182f10c0f..09ab3139a4 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/RootedPath.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/RootedPath.java
@@ -30,9 +30,8 @@ import java.util.Objects;
  * <p>Two {@link RootedPath}s are considered equal iff they have equal roots and equal relative
  * paths.
  *
- * <p>TODO(bazel-team): refactor Artifact to use this instead of Root. TODO(bazel-team): use an
- * opaque root representation so as to not expose the absolute path to clients via #asPath or
- * #getRoot.
+ * <p>TODO(bazel-team): use an opaque root representation so as to not expose the absolute path to
+ * clients via #asPath or #getRoot.
  */
 public class RootedPath implements Serializable {
 
@@ -48,7 +47,7 @@ public class RootedPath implements Serializable {
         rootRelativePath,
         root);
     this.root = root;
-    this.rootRelativePath = rootRelativePath.normalize();
+    this.rootRelativePath = rootRelativePath;
     this.path = root.getRelative(this.rootRelativePath);
   }
 
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 d924e19d45..a929f1435d 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
@@ -15,12 +15,14 @@
 package com.google.devtools.build.lib.vfs;
 
 import com.google.common.base.Preconditions;
-import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.concurrent.ThreadSafety;
 import java.io.IOException;
 import java.io.InputStream;
 import java.io.OutputStream;
+import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Comparator;
+import java.util.List;
 import java.util.Map;
 import javax.annotation.Nullable;
 
@@ -42,12 +44,21 @@ import javax.annotation.Nullable;
  * are not currently supported.
  */
 @ThreadSafety.ThreadSafe
-public class UnionFileSystem extends FileSystem {
+public final class UnionFileSystem extends FileSystem {
 
-  // Prefix trie index, allowing children to easily inherit prefix mappings
-  // of their parents.
-  // This does not currently handle unicode filenames.
-  private final PathTrie<FileSystem> pathDelegate;
+  private static class FileSystemAndPrefix {
+    final PathFragment prefix;
+    final FileSystem fileSystem;
+
+    public FileSystemAndPrefix(PathFragment prefix, FileSystem fileSystem) {
+      this.prefix = prefix;
+      this.fileSystem = fileSystem;
+    }
+  }
+
+  // List of file systems and their mappings, sorted by prefix length descending.
+  private final List<FileSystemAndPrefix> fileSystems;
+  private final FileSystem rootFileSystem;
 
   // True if the file path is case-sensitive on all the FileSystem
   // or False if they are all case-insensitive, otherwise error.
@@ -65,11 +76,12 @@ public class UnionFileSystem extends FileSystem {
     Preconditions.checkNotNull(rootFileSystem);
     Preconditions.checkArgument(rootFileSystem != this, "Circular root filesystem.");
     Preconditions.checkArgument(
-        !prefixMapping.containsKey(PathFragment.EMPTY_FRAGMENT),
+        prefixMapping.keySet().stream().noneMatch(p -> p.getPathString().equals("/")),
         "Attempted to specify an explicit root prefix mapping; "
             + "please use the rootFileSystem argument instead.");
 
-    this.pathDelegate = new PathTrie<>();
+    this.fileSystems = new ArrayList<>();
+    this.rootFileSystem = rootFileSystem;
     this.isCaseSensitive = rootFileSystem.isFilePathCaseSensitive();
 
     for (Map.Entry<PathFragment, FileSystem> prefix : prefixMapping.entrySet()) {
@@ -80,9 +92,13 @@ public class UnionFileSystem extends FileSystem {
       PathFragment prefixPath = prefix.getKey();
 
       // Extra slash prevents within-directory mappings, which Path can't handle.
-      pathDelegate.put(prefixPath, delegate);
+      fileSystems.add(new FileSystemAndPrefix(prefixPath, delegate));
     }
-    pathDelegate.put(PathFragment.ROOT_FRAGMENT, rootFileSystem);
+    // Order by length descending. This ensures that more specific mapping takes precedence
+    // when we try to find the file system of a given path.
+    Comparator<FileSystemAndPrefix> comparator =
+        Comparator.comparing(f -> f.prefix.getPathString().length());
+    fileSystems.sort(comparator.reversed());
   }
 
   /**
@@ -92,19 +108,24 @@ public class UnionFileSystem extends FileSystem {
    * @param path the {@link Path} to map to a filesystem
    * @throws IllegalArgumentException if no delegate exists for the path
    */
-  protected FileSystem getDelegate(Path path) {
+  FileSystem getDelegate(Path path) {
     Preconditions.checkNotNull(path);
-    FileSystem immediateDelegate = pathDelegate.get(path.asFragment());
-
-    // Should never actually happen if the root delegate is present.
-    Preconditions.checkNotNull(immediateDelegate, "No delegate filesystem exists for %s", path);
-    return immediateDelegate;
+    FileSystem delegate = null;
+    // Linearly iterate over each mapped file system and find the one that handles this path.
+    // For small number of mappings, this will be more efficient than using a trie
+    for (FileSystemAndPrefix fileSystemAndPrefix : this.fileSystems) {
+      if (path.startsWith(fileSystemAndPrefix.prefix)) {
+        delegate = fileSystemAndPrefix.fileSystem;
+        break;
+      }
+    }
+    return delegate != null ? delegate : rootFileSystem;
   }
 
   // Associates the path with the root of the given delegate filesystem.
   // Necessary to avoid null pointer problems inside of the delegates.
-  protected Path adjustPath(Path path, FileSystem delegate) {
-    return delegate.getPath(path.asFragment());
+  Path adjustPath(Path path, FileSystem delegate) {
+    return delegate.getPath(path.getPathString());
   }
 
   /**
@@ -344,12 +365,7 @@ public class UnionFileSystem extends FileSystem {
     path = internalResolveSymlink(path);
     FileSystem delegate = getDelegate(path);
     Path resolvedPath = adjustPath(path, delegate);
-    Collection<Path> entries = resolvedPath.getDirectoryEntries();
-    Collection<String> result = Lists.newArrayListWithCapacity(entries.size());
-    for (Path entry : entries) {
-      result.add(entry.getBaseName());
-    }
-    return result;
+    return delegate.getDirectoryEntries(resolvedPath);
   }
 
   // No need for the more complex logic of getDirectoryEntries; it calls it implicitly.
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/UnixOsPathPolicy.java b/src/main/java/com/google/devtools/build/lib/vfs/UnixOsPathPolicy.java
new file mode 100644
index 0000000000..8576643267
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/vfs/UnixOsPathPolicy.java
@@ -0,0 +1,138 @@
+// Copyright 2017 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.common.annotations.VisibleForTesting;
+import com.google.common.base.Splitter;
+import com.google.common.collect.Iterables;
+
+@VisibleForTesting
+class UnixOsPathPolicy implements OsPathPolicy {
+
+  static final UnixOsPathPolicy INSTANCE = new UnixOsPathPolicy();
+  private static final Splitter PATH_SPLITTER = Splitter.onPattern("/+").omitEmptyStrings();
+
+  @Override
+  public int needsToNormalize(String path) {
+    int n = path.length();
+    int dotCount = 0;
+    char prevChar = 0;
+    for (int i = 0; i < n; i++) {
+      char c = path.charAt(i);
+      if (c == '\\') {
+        return NEEDS_NORMALIZE;
+      }
+      if (c == '/') {
+        if (prevChar == '/') {
+          return NEEDS_NORMALIZE;
+        }
+        if (dotCount == 1 || dotCount == 2) {
+          return NEEDS_NORMALIZE;
+        }
+      }
+      dotCount = c == '.' ? dotCount + 1 : 0;
+      prevChar = c;
+    }
+    if (prevChar == '/' || dotCount == 1 || dotCount == 2) {
+      return NEEDS_NORMALIZE;
+    }
+    return NORMALIZED;
+  }
+
+  @Override
+  public int needsToNormalizeSuffix(String normalizedSuffix) {
+    // We know that the string is normalized
+    // In this case only suffixes starting with ".." may cause
+    // normalization once concatenated with other strings
+    return normalizedSuffix.startsWith("..") ? NEEDS_NORMALIZE : NORMALIZED;
+  }
+
+  @Override
+  public String normalize(String path, int normalizationLevel) {
+    if (normalizationLevel == NORMALIZED) {
+      return path;
+    }
+    if (path.isEmpty()) {
+      return path;
+    }
+    boolean isAbsolute = path.charAt(0) == '/';
+    StringBuilder sb = new StringBuilder(path.length());
+    if (isAbsolute) {
+      sb.append('/');
+    }
+    String[] segments = Iterables.toArray(PATH_SPLITTER.splitToList(path), String.class);
+    int segmentCount = Utils.removeRelativePaths(segments, 0, isAbsolute);
+    for (int i = 0; i < segmentCount; ++i) {
+      sb.append(segments[i]);
+      sb.append('/');
+    }
+    if (segmentCount > 0) {
+      sb.deleteCharAt(sb.length() - 1);
+    }
+    return sb.toString();
+  }
+
+  @Override
+  public int getDriveStrLength(String path) {
+    if (path.length() == 0) {
+      return 0;
+    }
+    return (path.charAt(0) == '/') ? 1 : 0;
+  }
+
+  @Override
+  public int compare(String s1, String s2) {
+    return s1.compareTo(s2);
+  }
+
+  @Override
+  public int compare(char c1, char c2) {
+    return Character.compare(c1, c2);
+  }
+
+  @Override
+  public boolean equals(String s1, String s2) {
+    return s1.equals(s2);
+  }
+
+  @Override
+  public int hash(String s) {
+    return s.hashCode();
+  }
+
+  @Override
+  public boolean startsWith(String path, String prefix) {
+    return path.startsWith(prefix);
+  }
+
+  @Override
+  public boolean endsWith(String path, String suffix) {
+    return path.endsWith(suffix);
+  }
+
+  @Override
+  public char getSeparator() {
+    return '/';
+  }
+
+  @Override
+  public boolean isSeparator(char c) {
+    return c == '/';
+  }
+
+  @Override
+  public boolean isCaseSensitive() {
+    return true;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/UnixPathFragment.java b/src/main/java/com/google/devtools/build/lib/vfs/UnixPathFragment.java
deleted file mode 100644
index b581d4375a..0000000000
--- a/src/main/java/com/google/devtools/build/lib/vfs/UnixPathFragment.java
+++ /dev/null
@@ -1,220 +0,0 @@
-// Copyright 2017 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.common.base.Preconditions;
-import java.io.InvalidObjectException;
-import java.io.ObjectInputStream;
-
-/**
- * Abstract base class for {@link PathFragment} instances that will be allocated when Blaze is run
- * on a non-Windows platform.
- */
-abstract class UnixPathFragment extends PathFragment {
-  static final Helper HELPER = new Helper();
-  /**
-    * We have two concrete subclasses with zero per-instance additional memory overhead. Do not add
-    * any fields. See the comment on memory use in PathFragment for details on the current
-    * per-instance memory usage.
-    */
-
-  protected UnixPathFragment(String[] segments) {
-    super(segments);
-  }
-
-  @Override
-  protected int computeHashCode() {
-    int h = 0;
-    for (String segment : segments) {
-      int segmentHash = segment.hashCode();
-      h = h * 31 + segmentHash;
-    }
-    return h;
-  }
-
-  @Override
-  public String windowsVolume() {
-    return "";
-  }
-
-  @Override
-  public char getDriveLetter() {
-    return '\0';
-  }
-
-  private static class Helper extends PathFragment.Helper {
-    private static final char SEPARATOR_CHAR = '/';
-
-    @Override
-    PathFragment create(String path) {
-      boolean isAbsolute = path.length() > 0 && isSeparator(path.charAt(0));
-      return isAbsolute
-          ? new AbsoluteUnixPathFragment(segment(path, 1))
-          : new RelativeUnixPathFragment(segment(path, 0));
-    }
-
-    @Override
-    PathFragment createAlreadyInterned(char driveLetter, boolean isAbsolute, String[] segments) {
-      Preconditions.checkState(driveLetter == '\0', driveLetter);
-      return isAbsolute
-          ? new AbsoluteUnixPathFragment(segments)
-          : new RelativeUnixPathFragment(segments);
-    }
-
-    @Override
-    char getPrimarySeparatorChar() {
-      return SEPARATOR_CHAR;
-    }
-
-    @Override
-    boolean isSeparator(char c) {
-      return c == SEPARATOR_CHAR;
-    }
-
-    @Override
-    boolean containsSeparatorChar(String path) {
-      return path.indexOf(SEPARATOR_CHAR) != -1;
-    }
-
-    @Override
-    boolean segmentsEqual(int length, String[] segments1, int offset1, String[] segments2) {
-      if ((segments1.length - offset1) < length || segments2.length < length) {
-        return false;
-      }
-      for (int i = 0; i < length; ++i) {
-        String seg1 = segments1[i + offset1];
-        String seg2 = segments2[i];
-        if ((seg1 == null) != (seg2 == null)) {
-          return false;
-        }
-        if (seg1 == null) {
-          continue;
-        }
-        if (!seg1.equals(seg2)) {
-          return false;
-        }
-      }
-      return true;
-    }
-
-    @Override
-    protected int compare(PathFragment pathFragment1, PathFragment pathFragment2) {
-      if (pathFragment1.isAbsolute() != pathFragment2.isAbsolute()) {
-        return pathFragment1.isAbsolute() ? -1 : 1;
-      }
-      String[] segments1 = pathFragment1.segments();
-      String[] segments2 = pathFragment2.segments();
-      int len1 = segments1.length;
-      int len2 = segments2.length;
-      int n = Math.min(len1, len2);
-      for (int i = 0; i < n; i++) {
-        String seg1 = segments1[i];
-        String seg2 = segments2[i];
-        int cmp = seg1.compareTo(seg2);
-        if (cmp != 0) {
-          return cmp;
-        }
-      }
-      return len1 - len2;
-    }
-  }
-
-  private static final class AbsoluteUnixPathFragment extends UnixPathFragment {
-    private AbsoluteUnixPathFragment(String[] segments) {
-      super(segments);
-    }
-
-    @Override
-    public boolean isAbsolute() {
-      return true;
-    }
-
-    @Override
-    protected int computeHashCode() {
-      int h = Boolean.TRUE.hashCode();
-      h = h * 31 + super.computeHashCode();
-      return h;
-    }
-
-    @Override
-    public boolean equals(Object other) {
-      if (!(other instanceof AbsoluteUnixPathFragment)) {
-        return false;
-      }
-      if (this == other) {
-        return true;
-      }
-      AbsoluteUnixPathFragment otherAbsoluteUnixPathFragment = (AbsoluteUnixPathFragment) other;
-      return HELPER.segmentsEqual(this.segments, otherAbsoluteUnixPathFragment.segments);
-    }
-
-    // Java serialization looks for the presence of this method in the concrete class. It is not
-    // inherited from the parent class.
-    @Override
-    protected Object writeReplace() {
-      return super.writeReplace();
-    }
-
-    // Java serialization looks for the presence of this method in the concrete class. It is not
-    // inherited from the parent class.
-    @Override
-    protected void readObject(ObjectInputStream stream) throws InvalidObjectException {
-      super.readObject(stream);
-    }
-  }
-
-  private static final class RelativeUnixPathFragment extends UnixPathFragment {
-    private RelativeUnixPathFragment(String[] segments) {
-      super(segments);
-    }
-
-    @Override
-    public boolean isAbsolute() {
-      return false;
-    }
-
-    @Override
-    protected int computeHashCode() {
-      int h = Boolean.FALSE.hashCode();
-      h = h * 31 + super.computeHashCode();
-      return h;
-    }
-
-    @Override
-    public boolean equals(Object other) {
-      if (!(other instanceof RelativeUnixPathFragment)) {
-        return false;
-      }
-      if (this == other) {
-        return true;
-      }
-      RelativeUnixPathFragment otherRelativeUnixPathFragment = (RelativeUnixPathFragment) other;
-      return HELPER.segmentsEqual(this.segments, otherRelativeUnixPathFragment.segments);
-    }
-
-    // Java serialization looks for the presence of this method in the concrete class. It is not
-    // inherited from the parent class.
-    @Override
-    protected Object writeReplace() {
-      return super.writeReplace();
-    }
-
-    // Java serialization looks for the presence of this method in the concrete class. It is not
-    // inherited from the parent class.
-    @Override
-    protected void readObject(ObjectInputStream stream) throws InvalidObjectException {
-      super.readObject(stream);
-    }
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/WindowsOsPathPolicy.java b/src/main/java/com/google/devtools/build/lib/vfs/WindowsOsPathPolicy.java
new file mode 100644
index 0000000000..f420683b75
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/vfs/WindowsOsPathPolicy.java
@@ -0,0 +1,240 @@
+// Copyright 2017 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.common.annotations.VisibleForTesting;
+import com.google.common.base.Splitter;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.windows.WindowsShortPath;
+import com.google.devtools.build.lib.windows.jni.WindowsFileOperations;
+import java.io.IOException;
+
+@VisibleForTesting
+class WindowsOsPathPolicy implements OsPathPolicy {
+
+  static final WindowsOsPathPolicy INSTANCE = new WindowsOsPathPolicy();
+
+  static final int NEEDS_SHORT_PATH_NORMALIZATION = NEEDS_NORMALIZE + 1;
+
+  private static final Splitter WINDOWS_PATH_SPLITTER =
+      Splitter.onPattern("[\\\\/]+").omitEmptyStrings();
+
+  private final ShortPathResolver shortPathResolver;
+
+  interface ShortPathResolver {
+    String resolveShortPath(String path);
+  }
+
+  static class DefaultShortPathResolver implements ShortPathResolver {
+    @Override
+    public String resolveShortPath(String path) {
+      try {
+        return WindowsFileOperations.getLongPath(path);
+      } catch (IOException e) {
+        return path;
+      }
+    }
+  }
+
+  WindowsOsPathPolicy() {
+    this(new DefaultShortPathResolver());
+  }
+
+  WindowsOsPathPolicy(ShortPathResolver shortPathResolver) {
+    this.shortPathResolver = shortPathResolver;
+  }
+
+  @Override
+  public int needsToNormalize(String path) {
+    int n = path.length();
+    int normalizationLevel = NORMALIZED;
+    int dotCount = 0;
+    char prevChar = 0;
+    int segmentBeginIndex = 0; // The start index of the current path index
+    boolean segmentHasShortPathChar = false; // Triggers more expensive short path regex test
+    for (int i = 0; i < n; i++) {
+      char c = path.charAt(i);
+      if (isSeparator(c)) {
+        if (c == '\\') {
+          normalizationLevel = Math.max(normalizationLevel, NEEDS_NORMALIZE);
+        }
+        // No need to check for '\\' here because that already causes normalization
+        if (prevChar == '/') {
+          normalizationLevel = Math.max(normalizationLevel, NEEDS_NORMALIZE);
+        }
+        if (dotCount == 1 || dotCount == 2) {
+          normalizationLevel = Math.max(normalizationLevel, NEEDS_NORMALIZE);
+        }
+        if (segmentHasShortPathChar) {
+          if (WindowsShortPath.isShortPath(path.substring(segmentBeginIndex, i))) {
+            normalizationLevel = Math.max(normalizationLevel, NEEDS_SHORT_PATH_NORMALIZATION);
+          }
+        }
+        segmentBeginIndex = i + 1;
+        segmentHasShortPathChar = false;
+      } else if (c == '~') {
+        // This path segment might be a Windows short path segment
+        segmentHasShortPathChar = true;
+      }
+      dotCount = c == '.' ? dotCount + 1 : 0;
+      prevChar = c;
+    }
+    if (segmentHasShortPathChar) {
+      if (WindowsShortPath.isShortPath(path.substring(segmentBeginIndex))) {
+        normalizationLevel = Math.max(normalizationLevel, NEEDS_SHORT_PATH_NORMALIZATION);
+      }
+    }
+    if ((n > 1 && isSeparator(prevChar)) || dotCount == 1 || dotCount == 2) {
+      normalizationLevel = Math.max(normalizationLevel, NEEDS_NORMALIZE);
+    }
+    return normalizationLevel;
+  }
+
+  @Override
+  public int needsToNormalizeSuffix(String normalizedSuffix) {
+    // On Windows, all bets are off because of short paths, so we have to check the entire string
+    return needsToNormalize(normalizedSuffix);
+  }
+
+  @Override
+  public String normalize(String path, int normalizationLevel) {
+    if (normalizationLevel == NORMALIZED) {
+      return path;
+    }
+    if (normalizationLevel == NEEDS_SHORT_PATH_NORMALIZATION) {
+      String resolvedPath = shortPathResolver.resolveShortPath(path);
+      if (resolvedPath != null) {
+        path = resolvedPath;
+      }
+    }
+    String[] segments = Iterables.toArray(WINDOWS_PATH_SPLITTER.splitToList(path), String.class);
+    int driveStrLength = getDriveStrLength(path);
+    boolean isAbsolute = driveStrLength > 0;
+    int segmentSkipCount = isAbsolute && driveStrLength > 1 ? 1 : 0;
+
+    StringBuilder sb = new StringBuilder(path.length());
+    if (isAbsolute) {
+      char c = path.charAt(0);
+      if (isSeparator(c)) {
+        sb.append('/');
+      } else {
+        sb.append(Character.toUpperCase(c));
+        sb.append(":/");
+      }
+    }
+    int segmentCount = Utils.removeRelativePaths(segments, segmentSkipCount, isAbsolute);
+    for (int i = 0; i < segmentCount; ++i) {
+      sb.append(segments[i]);
+      sb.append('/');
+    }
+    if (segmentCount > 0) {
+      sb.deleteCharAt(sb.length() - 1);
+    }
+    return sb.toString();
+  }
+
+  @Override
+  public int getDriveStrLength(String path) {
+    int n = path.length();
+    if (n == 0) {
+      return 0;
+    }
+    char c0 = path.charAt(0);
+    if (isSeparator(c0)) {
+      return 1;
+    }
+    if (n < 3) {
+      return 0;
+    }
+    char c1 = path.charAt(1);
+    char c2 = path.charAt(2);
+    if (isDriveLetter(c0) && c1 == ':' && isSeparator(c2)) {
+      return 3;
+    }
+    return 0;
+  }
+
+  private static boolean isDriveLetter(char c) {
+    return ((c >= 'a') && (c <= 'z')) || ((c >= 'A') && (c <= 'Z'));
+  }
+
+  @Override
+  public int compare(String s1, String s2) {
+    // Windows is case-insensitive
+    return s1.compareToIgnoreCase(s2);
+  }
+
+  @Override
+  public int compare(char c1, char c2) {
+    return Character.compare(Character.toLowerCase(c1), Character.toLowerCase(c2));
+  }
+
+  @Override
+  public boolean equals(String s1, String s2) {
+    return s1.equalsIgnoreCase(s2);
+  }
+
+  @Override
+  public int hash(String s) {
+    // Windows is case-insensitive
+    return s.toLowerCase().hashCode();
+  }
+
+  @Override
+  public boolean startsWith(String path, String prefix) {
+    int pathn = path.length();
+    int prefixn = prefix.length();
+    if (pathn < prefixn) {
+      return false;
+    }
+    for (int i = 0; i < prefixn; ++i) {
+      if (Character.toLowerCase(path.charAt(i)) != Character.toLowerCase(prefix.charAt(i))) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  @Override
+  public boolean endsWith(String path, String suffix) {
+    int pathn = path.length();
+    int suffixLength = suffix.length();
+    if (pathn < suffixLength) {
+      return false;
+    }
+    int offset = pathn - suffixLength;
+    for (int i = 0; i < suffixLength; ++i) {
+      if (Character.toLowerCase(path.charAt(i + offset))
+          != Character.toLowerCase(suffix.charAt(i))) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  @Override
+  public char getSeparator() {
+    return '/';
+  }
+
+  @Override
+  public boolean isSeparator(char c) {
+    return c == '/' || c == '\\';
+  }
+
+  @Override
+  public boolean isCaseSensitive() {
+    return false;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/WindowsPathFragment.java b/src/main/java/com/google/devtools/build/lib/vfs/WindowsPathFragment.java
deleted file mode 100644
index ac3be0f524..0000000000
--- a/src/main/java/com/google/devtools/build/lib/vfs/WindowsPathFragment.java
+++ /dev/null
@@ -1,254 +0,0 @@
-// Copyright 2017 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 java.io.InvalidObjectException;
-import java.io.ObjectInputStream;
-
-/**
- * Abstract base class for {@link PathFragment} instances that will be allocated when Blaze is run
- * on a Windows platform.
- */
-abstract class WindowsPathFragment extends PathFragment {
-  static final Helper HELPER = new Helper();
-
-  // The drive letter of an absolute path, eg. 'C' for 'C:/foo'.
-  // We deliberately ignore "C:foo" style paths and treat them like a literal "C:foo" path segment.
-  protected final char driveLetter;
-
-  protected WindowsPathFragment(char driveLetter, String[] segments) {
-    super(segments);
-    this.driveLetter = driveLetter;
-  }
-
-  @Override
-  public String windowsVolume() {
-    return (driveLetter != '\0') ? driveLetter + ":" : "";
-  }
-
-  @Override
-  public char getDriveLetter() {
-    return driveLetter;
-  }
-
-  @Override
-  protected int computeHashCode() {
-    int h = 0;
-    for (String segment : segments) {
-      int segmentHash = segment.toLowerCase().hashCode();
-      h = h * 31 + segmentHash;
-    }
-    return h;
-  }
-
-  private static class Helper extends PathFragment.Helper {
-    private static final char SEPARATOR_CHAR = '/';
-    // TODO(laszlocsomor): Lots of internal PathFragment operations, e.g. getPathString, use the
-    // primary separator char and do not use this.
-    private static final char EXTRA_SEPARATOR_CHAR = '\\';
-
-    private static boolean isDriveLetter(char c) {
-      return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
-    }
-
-    @Override
-    PathFragment create(String path) {
-      char driveLetter =
-          path.length() >= 3
-                  && path.charAt(1) == ':'
-                  && isSeparator(path.charAt(2))
-                  && isDriveLetter(path.charAt(0))
-              ? Character.toUpperCase(path.charAt(0))
-              : '\0';
-      if (driveLetter != '\0') {
-        path = path.substring(2);
-      }
-      boolean isAbsolute = path.length() > 0 && isSeparator(path.charAt(0));
-      return isAbsolute
-          ? new AbsoluteWindowsPathFragment(driveLetter, segment(path, 1))
-          : new RelativeWindowsPathFragment(driveLetter, segment(path, 0));
-    }
-
-    @Override
-    PathFragment createAlreadyInterned(char driveLetter, boolean isAbsolute, String[] segments) {
-      return isAbsolute
-          ? new AbsoluteWindowsPathFragment(driveLetter, segments)
-          : new RelativeWindowsPathFragment(driveLetter, segments);
-    }
-
-    @Override
-    char getPrimarySeparatorChar() {
-      return SEPARATOR_CHAR;
-    }
-
-    @Override
-    boolean isSeparator(char c) {
-      return c == SEPARATOR_CHAR || c == EXTRA_SEPARATOR_CHAR;
-    }
-
-    @Override
-    boolean containsSeparatorChar(String path) {
-      // TODO(laszlocsomor): This is inefficient.
-      return path.indexOf(SEPARATOR_CHAR) != -1 || path.indexOf(EXTRA_SEPARATOR_CHAR) != -1;
-    }
-
-    @Override
-    boolean segmentsEqual(int length, String[] segments1, int offset1, String[] segments2) {
-      if ((segments1.length - offset1) < length || segments2.length < length) {
-        return false;
-      }
-      for (int i = 0; i < length; ++i) {
-        String seg1 = segments1[i + offset1];
-        String seg2 = segments2[i];
-        if ((seg1 == null) != (seg2 == null)) {
-          return false;
-        }
-        if (seg1 == null) {
-          continue;
-        }
-        // TODO(laszlocsomor): The calls to String#toLowerCase are inefficient and potentially
-        // repeated too. Also, why not use String#equalsIgnoreCase.
-        seg1 = seg1.toLowerCase();
-        seg2 = seg2.toLowerCase();
-        if (!seg1.equals(seg2)) {
-          return false;
-        }
-      }
-      return true;
-    }
-
-    @Override
-    protected int compare(PathFragment pathFragment1, PathFragment pathFragment2) {
-      if (pathFragment1.isAbsolute() != pathFragment2.isAbsolute()) {
-        return pathFragment1.isAbsolute() ? -1 : 1;
-      }
-      int cmp = Character.compare(pathFragment1.getDriveLetter(), pathFragment2.getDriveLetter());
-      if (cmp != 0) {
-        return cmp;
-      }
-      String[] segments1 = pathFragment1.segments();
-      String[] segments2 = pathFragment2.segments();
-      int len1 = segments1.length;
-      int len2 = segments2.length;
-      int n = Math.min(len1, len2);
-      for (int i = 0; i < n; i++) {
-        String seg1 = segments1[i].toLowerCase();
-        String seg2 = segments2[i].toLowerCase();
-        cmp = seg1.compareTo(seg2);
-        if (cmp != 0) {
-          return cmp;
-        }
-      }
-      return len1 - len2;
-    }
-  }
-
-  private static final class AbsoluteWindowsPathFragment extends WindowsPathFragment {
-    private AbsoluteWindowsPathFragment(char driveLetter, String[] segments) {
-      super(driveLetter, segments);
-    }
-
-    @Override
-    public boolean isAbsolute() {
-      return true;
-    }
-
-    @Override
-    protected int computeHashCode() {
-      int h = Boolean.TRUE.hashCode();
-      h = h * 31 + super.computeHashCode();
-      h = h * 31 + Character.valueOf(getDriveLetter()).hashCode();
-      return h;
-    }
-
-    @Override
-    public boolean equals(Object other) {
-      if (!(other instanceof AbsoluteWindowsPathFragment)) {
-        return false;
-      }
-      if (this == other) {
-        return true;
-      }
-      AbsoluteWindowsPathFragment otherAbsoluteWindowsPathFragment =
-          (AbsoluteWindowsPathFragment) other;
-      return this.driveLetter == otherAbsoluteWindowsPathFragment.driveLetter
-          && HELPER.segmentsEqual(this.segments, otherAbsoluteWindowsPathFragment.segments);
-    }
-
-    // Java serialization looks for the presence of this method in the concrete class. It is not
-    // inherited from the parent class.
-    @Override
-    protected Object writeReplace() {
-      return super.writeReplace();
-    }
-
-    // Java serialization looks for the presence of this method in the concrete class. It is not
-    // inherited from the parent class.
-    @Override
-    protected void readObject(ObjectInputStream stream) throws InvalidObjectException {
-      super.readObject(stream);
-    }
-  }
-
-  private static final class RelativeWindowsPathFragment extends WindowsPathFragment {
-    private RelativeWindowsPathFragment(char driveLetter, String[] segments) {
-      super(driveLetter, segments);
-    }
-
-    @Override
-    public boolean isAbsolute() {
-      return false;
-    }
-
-    @Override
-    protected int computeHashCode() {
-      int h = Boolean.FALSE.hashCode();
-      h = h * 31 + super.computeHashCode();
-      if (!isEmpty()) {
-        h = h * 31 + Character.valueOf(getDriveLetter()).hashCode();
-      }
-      return h;
-    }
-
-    @Override
-    public boolean equals(Object other) {
-      if (!(other instanceof RelativeWindowsPathFragment)) {
-        return false;
-      }
-      if (this == other) {
-        return true;
-      }
-      RelativeWindowsPathFragment otherRelativeWindowsPathFragment =
-          (RelativeWindowsPathFragment) other;
-      return isEmpty() && otherRelativeWindowsPathFragment.isEmpty()
-          ? true
-          : this.driveLetter == otherRelativeWindowsPathFragment.driveLetter
-              && HELPER.segmentsEqual(this.segments, otherRelativeWindowsPathFragment.segments);
-    }
-
-    // Java serialization looks for the presence of this method in the concrete class. It is not
-    // inherited from the parent class.
-    @Override
-    protected Object writeReplace() {
-      return super.writeReplace();
-    }
-
-    // Java serialization looks for the presence of this method in the concrete class. It is not
-    // inherited from the parent class.
-    @Override
-    protected void readObject(ObjectInputStream stream) throws InvalidObjectException {
-      super.readObject(stream);
-    }
-  }
-}
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs/InMemoryFileSystem.java b/src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs/InMemoryFileSystem.java
index 8fd21180b4..c2a52a5b3d 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs/InMemoryFileSystem.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs/InMemoryFileSystem.java
@@ -350,7 +350,8 @@ public class InMemoryFileSystem extends FileSystem {
 
     Stack<String> stack = new Stack<>();
     for (Path p = path; !isRootDirectory(p); p = p.getParentDirectory()) {
-      stack.push(p.getBaseName());
+      String name = baseNameOrWindowsDrive(p);
+      stack.push(name);
     }
 
     InMemoryContentInfo inode = rootInode;
@@ -381,6 +382,13 @@ public class InMemoryFileSystem extends FileSystem {
         for (int ii = segments.size() - 1; ii >= 0; --ii) {
           stack.push(segments.get(ii)); // Note this may include ".." segments.
         }
+        // Push Windows drive if there is one
+        if (linkTarget.isAbsolute()) {
+          String driveStr = linkTarget.getDriveStr();
+          if (driveStr.length() > 1) {
+            stack.push(driveStr);
+          }
+        }
       } else {
         inode = child;
       }
@@ -412,7 +420,7 @@ public class InMemoryFileSystem extends FileSystem {
   private synchronized InMemoryContentInfo getNoFollowStatOrOutOfScopeParent(Path path)
       throws IOException  {
     InMemoryDirectoryInfo dirInfo = getDirectory(path.getParentDirectory());
-    return directoryLookup(dirInfo, path.getBaseName(), /*create=*/ false, path);
+    return directoryLookup(dirInfo, baseNameOrWindowsDrive(path), /*create=*/ false, path);
   }
 
   /**
@@ -606,7 +614,7 @@ public class InMemoryFileSystem extends FileSystem {
     InMemoryDirectoryInfo parent;
     synchronized (this) {
       parent = getDirectory(path.getParentDirectory());
-      InMemoryContentInfo child = parent.getChild(path.getBaseName());
+      InMemoryContentInfo child = parent.getChild(baseNameOrWindowsDrive(path));
       if (child != null) { // already exists
         if (child.isDirectory()) {
           return false;
@@ -618,7 +626,7 @@ public class InMemoryFileSystem extends FileSystem {
       InMemoryDirectoryInfo newDir = new InMemoryDirectoryInfo(clock);
       newDir.addChild(".", newDir);
       newDir.addChild("..", parent);
-      insert(parent, path.getBaseName(), newDir, path);
+      insert(parent, baseNameOrWindowsDrive(path), newDir, path);
 
       return true;
     }
@@ -649,10 +657,11 @@ public class InMemoryFileSystem extends FileSystem {
 
     synchronized (this) {
       InMemoryDirectoryInfo parent = getDirectory(path.getParentDirectory());
-      if (parent.getChild(path.getBaseName()) != null) {
+      if (parent.getChild(baseNameOrWindowsDrive(path)) != null) {
         throw Error.EEXIST.exception(path);
       }
-      insert(parent, path.getBaseName(), new InMemoryLinkInfo(clock, targetFragment), path);
+      insert(
+          parent, baseNameOrWindowsDrive(path), new InMemoryLinkInfo(clock, targetFragment), path);
     }
   }
 
@@ -703,11 +712,11 @@ public class InMemoryFileSystem extends FileSystem {
 
     synchronized (this) {
       InMemoryDirectoryInfo parent = getDirectory(path.getParentDirectory());
-      InMemoryContentInfo child = parent.getChild(path.getBaseName());
+      InMemoryContentInfo child = parent.getChild(baseNameOrWindowsDrive(path));
       if (child.isDirectory() && child.getSize() > 2) {
         throw Error.ENOTEMPTY.exception(path);
       }
-      unlink(parent, path.getBaseName(), path);
+      unlink(parent, baseNameOrWindowsDrive(path), path);
       return true;
     }
   }
@@ -780,13 +789,13 @@ public class InMemoryFileSystem extends FileSystem {
       InMemoryDirectoryInfo sourceParent = getDirectory(sourcePath.getParentDirectory());
       InMemoryDirectoryInfo targetParent = getDirectory(targetPath.getParentDirectory());
 
-      InMemoryContentInfo sourceInode = sourceParent.getChild(sourcePath.getBaseName());
+      InMemoryContentInfo sourceInode = sourceParent.getChild(baseNameOrWindowsDrive(sourcePath));
       if (sourceInode == null) {
         throw Error.ENOENT.exception(sourcePath);
       }
-      InMemoryContentInfo targetInode = targetParent.getChild(targetPath.getBaseName());
+      InMemoryContentInfo targetInode = targetParent.getChild(baseNameOrWindowsDrive(targetPath));
 
-      unlink(sourceParent, sourcePath.getBaseName(), sourcePath);
+      unlink(sourceParent, baseNameOrWindowsDrive(sourcePath), sourcePath);
       try {
         // TODO(bazel-team): (2009) test with symbolic links.
 
@@ -802,15 +811,19 @@ public class InMemoryFileSystem extends FileSystem {
           } else if (sourceInode.isDirectory()) {
             throw new IOException(sourcePath + " -> " + targetPath + " (" + Error.ENOTDIR + ")");
           }
-          unlink(targetParent, targetPath.getBaseName(), targetPath);
+          unlink(targetParent, baseNameOrWindowsDrive(targetPath), targetPath);
         }
         sourceInode.movedTo(targetPath);
-        insert(targetParent, targetPath.getBaseName(), sourceInode, targetPath);
+        insert(targetParent, baseNameOrWindowsDrive(targetPath), sourceInode, targetPath);
         return;
 
       } catch (IOException e) {
         sourceInode.movedTo(sourcePath);
-        insert(sourceParent, sourcePath.getBaseName(), sourceInode, sourcePath); // restore source
+        insert(
+            sourceParent,
+            baseNameOrWindowsDrive(sourcePath),
+            sourceInode,
+            sourcePath); // restore source
         throw e;
       }
     }
@@ -828,18 +841,33 @@ public class InMemoryFileSystem extends FileSystem {
     synchronized (this) {
       InMemoryDirectoryInfo linkParent = getDirectory(linkPath.getParentDirectory());
       // Same check used when creating a symbolic link
-      if (linkParent.getChild(linkPath.getBaseName()) != null) {
+      if (linkParent.getChild(baseNameOrWindowsDrive(linkPath)) != null) {
         throw Error.EEXIST.exception(linkPath);
       }
       insert(
           linkParent,
-          linkPath.getBaseName(),
-          getDirectory(originalPath.getParentDirectory()).getChild(originalPath.getBaseName()),
+          baseNameOrWindowsDrive(linkPath),
+          getDirectory(originalPath.getParentDirectory())
+              .getChild(baseNameOrWindowsDrive(originalPath)),
           linkPath);
     }
   }
 
-  private boolean isRootDirectory(Path path) {
-    return path.isRootDirectory();
+  /**
+   * On Unix the root directory is "/". On Windows there isn't one, so we reach null from
+   * getParentDirectory.
+   */
+  private boolean isRootDirectory(@Nullable Path path) {
+    return path == null || path.getPathString().equals("/");
+  }
+
+  /**
+   * Returns either the base name of the path, or the drive (if referring to a Windows drive).
+   *
+   * <p>This allows the file system to treat windows drives much like directories.
+   */
+  private static String baseNameOrWindowsDrive(Path path) {
+    String name = path.getBaseName();
+    return !name.isEmpty() ? name : path.getDriveStr();
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs/InMemoryLinkInfo.java b/src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs/InMemoryLinkInfo.java
index 107f319115..dabbbcefeb 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs/InMemoryLinkInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/inmemoryfs/InMemoryLinkInfo.java
@@ -31,7 +31,7 @@ class InMemoryLinkInfo extends InMemoryContentInfo {
   InMemoryLinkInfo(Clock clock, PathFragment linkContent) {
     super(clock);
     this.linkContent = linkContent;
-    this.normalizedLinkContent = linkContent.normalize();
+    this.normalizedLinkContent = linkContent;
   }
 
   @Override
@@ -56,7 +56,7 @@ class InMemoryLinkInfo extends InMemoryContentInfo {
 
   @Override
   public long getSize() {
-    return linkContent.toString().length();
+    return linkContent.getSafePathString().length();
   }
 
   /**