VFS: implement a Windows-specific Path subclass

This change rolls forward commit e0d7a540e3c615c628f63fcaaaba0c47fca2cb25 and
commit 8bb4299b28de14eed9d3b57bcaeb9350c81c7db3, and adds a bugfix:
- FileSystem.PathFactory got a new translatePath
  method that WindowsFileSystem.PathFactory
  overrides to translate absolute Unix paths to
  MSYS-relative paths
- Path.getCachedChildPath calls this translatePath
  method so the child path is registered with the
  correct (translated) parent and under the
  correct name (e.g. "C:" instead of say "c")

Below is the rest of the original change
description:

The new subclass WindowsFileSystem.WindowsPath is
aware of Windows drives.

This change:
- introduces a new factory for Path objects so
  FileSystems can return a custom implementation
  that instantiates filesystem-specific Paths
- implements the WindowsPath subclass of Path that
  is aware of Windows drives
- introduces the bazel.windows_unix_root JVM
  argument that defines the MSYS root, which
  defines the absolute Windows path that is the
  root of all Unix paths that Bazel creates (e.g.
  "/usr/lib" -> "C:/tools/msys64/usr/lib") except
  if the path is of the form "/c/foo" which is
  treated as "C:/foo"
- removes all Windows-specific logic from Path

PathFragment is still aware of drive letters and
it has to remain so because it is unaware of file
systems.

WindowsPath restricts the allowed path strings to
absolute Unix paths where the first segment, if
any, is a volume specifier. From now on if Bazel
attempts to create a WindowsPath from an absolute
Unix path, Bazel will make it relative to
WindowsPath.UNIX_ROOT, unless the first component
is a single-letter name (e.g. "/c/foo" which is
"C:/foo").

Subclassing Path is necessary because a Unix-style
absolute path doesn't sufficiently define a full
Windows path, as it may be relative to any drive.

Fixes https://github.com/bazelbuild/bazel/issues/1463

--
MOS_MIGRATED_REVID=137149483

6 files changed, 532 insertions, 124 deletions

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 e7f1fa2513..90aac0e130 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
@@ -22,6 +22,8 @@ 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.build.lib.vfs.Path.PathFactory.TranslatedPath;
 import java.io.FileNotFoundException;
 import java.io.IOException;
 import java.io.InputStream;
@@ -37,6 +39,25 @@ import java.util.List;
 @ThreadSafe
 public abstract class FileSystem {
 
+  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 TranslatedPath translatePath(Path parent, String child) {
+        return new TranslatedPath(parent, child);
+      }
+    };
+  }
+
   /**
    * An exception thrown when attempting to resolve an ordinary file as a symlink.
    */
@@ -49,19 +70,12 @@ public abstract class FileSystem {
   protected final Path rootPath;
 
   protected FileSystem() {
-    this.rootPath = createRootPath();
+    this.rootPath = getPathFactory().createRootPath(this);
   }
 
-  /**
-   * Creates the root of all paths used by this filesystem. This is a hook
-   * allowing subclasses to define their own root path class. All other paths
-   * are created via the root path's {@link Path#createChildPath(String)} method.
-   * <p>
-   * Beware: this is called during the FileSystem constructor which may occur
-   * before subclasses are completely initialized.
-   */
-  protected Path createRootPath() {
-    return new Path(this);
+  /** Returns filesystem-specific path factory. */
+  protected PathFactory getPathFactory() {
+    return UnixPathFactory.INSTANCE;
   }
 
   /**
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 dbec227a22..6599952541 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
@@ -17,7 +17,6 @@ import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
-import com.google.devtools.build.lib.util.OS;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.util.StringCanonicalizer;
 import java.io.File;
@@ -31,7 +30,6 @@ import java.io.Serializable;
 import java.lang.ref.Reference;
 import java.lang.ref.ReferenceQueue;
 import java.lang.ref.WeakReference;
-import java.util.Arrays;
 import java.util.Collection;
 import java.util.IdentityHashMap;
 import java.util.Objects;
@@ -53,6 +51,53 @@ import java.util.Objects;
 @ThreadSafe
 public class Path implements Comparable<Path>, Serializable {
 
+  /** Filesystem-specific factory for {@link Path} objects. */
+  public static interface PathFactory {
+
+    /**
+     * A translated path, i.e. where the parent and name are potentially different from the input.
+     *
+     * <p>See {@link PathFactory#translatePath} for details.
+     */
+    public static final class TranslatedPath {
+      public final Path parent;
+      public final String child;
+
+      public TranslatedPath(Path parent, String child) {
+        this.parent = parent;
+        this.child = child;
+      }
+    }
+
+    /**
+     * 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);
+
+    /**
+     * Translate the input path in a filesystem-specific way if necessary.
+     *
+     * <p>On Unix filesystems this operation is typically idempotent, but on Windows this can be
+     * used to translate absolute Unix paths to absolute Windows paths, e.g. "/c" to "C:/" or "/usr"
+     * to "C:/tools/msys64/usr".
+     */
+    TranslatedPath translatePath(Path parent, String child);
+  }
+
   private static FileSystem fileSystemForSerialization;
 
   /**
@@ -151,10 +196,12 @@ public class Path implements Comparable<Path>, Serializable {
   private volatile IdentityHashMap<String, Reference<Path>> children;
 
   /**
-   * Create a path instance.  Should only be called by {@link #createChildPath}.
+   * 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}
+   *     StringCanonicalizer#intern}
    * @param parent this path's parent
    */
   protected Path(FileSystem fileSystem, String name, Path parent) {
@@ -162,6 +209,9 @@ public class Path implements Comparable<Path>, Serializable {
     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 {
@@ -170,8 +220,9 @@ public class Path implements Comparable<Path>, Serializable {
   }
 
   /**
-   * Create the root path.  Should only be called by
-   * {@link FileSystem#createRootPath()}.
+   * Create the root path.
+   *
+   * <p>Should only be called by {@link PathFactory#createRootPath(FileSystem)}.
    */
   protected Path(FileSystem fileSystem) {
     this(fileSystem, StringCanonicalizer.intern("/"), null);
@@ -197,6 +248,7 @@ public class Path implements Comparable<Path>, Serializable {
       this.depth = this.parent.depth + 1;
     }
     this.hashCode = Objects.hash(parent, name);
+    reinitializeAfterDeserialization();
   }
 
   /**
@@ -211,7 +263,45 @@ public class Path implements Comparable<Path>, Serializable {
   }
 
   protected Path createChildPath(String childName) {
-    return new Path(fileSystem, childName, this);
+    return fileSystem.getPathFactory().createChildPath(this, childName);
+  }
+
+  /**
+   * Reinitializes this object after deserialization.
+   *
+   * <p>Derived classes should use this hook to initialize additional state.
+   */
+  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;
+  }
+
+  /**
+   * 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.
+   */
+  protected boolean isTopLevelDirectory() {
+    return isRootDirectory();
   }
 
   /**
@@ -219,26 +309,31 @@ public class Path implements Comparable<Path>, Serializable {
    * if it doesn't already exist.
    */
   private Path getCachedChildPath(String childName) {
+    return getCachedChildPath(fileSystem.getPathFactory().translatePath(this, childName));
+  }
+
+  private static Path getCachedChildPath(PathFactory.TranslatedPath translated) {
+    Path parent = translated.parent;
     // We get a canonical instance since 'children' is an IdentityHashMap.
-    childName = StringCanonicalizer.intern(childName);
+    String childName = StringCanonicalizer.intern(translated.child);
     // We use double-checked locking so that we only hold the lock when we might need to mutate the
     // 'children' variable. 'children' will never become null if it's already non-null, so we only
     // need to worry about the case where it's currently null and we race with another thread
     // executing getCachedChildPath(<doesn't matter>) trying to set 'children' to a non-null value.
-    if (children == null) {
-      synchronized (this) {
-        if (children == null) {
+    if (parent.children == null) {
+      synchronized (parent) {
+        if (parent.children == null) {
           // 66% of Paths have size == 1, 80% <= 2
-          children = new IdentityHashMap<>(1);
+          parent.children = new IdentityHashMap<>(1);
         }
       }
     }
-    synchronized (this) {
-      Reference<Path> childRef = children.get(childName);
+    synchronized (parent) {
+      Reference<Path> childRef = parent.children.get(childName);
       Path child;
       if (childRef == null || (child = childRef.get()) == null) {
-        child = createChildPath(childName);
-        children.put(childName, new PathWeakReferenceForCleanup(child, REFERENCE_QUEUE));
+        child = parent.fileSystem.getPathFactory().createChildPath(parent, childName);
+        parent.children.put(childName, new PathWeakReferenceForCleanup(child, REFERENCE_QUEUE));
       }
       return child;
     }
@@ -284,37 +379,22 @@ public class Path implements Comparable<Path>, Serializable {
   }
 
   /**
-   * Computes a string representation of this path, and writes it to the
-   * given string builder. Only called locally with a new instance.
+   * Computes a string representation of this path, and writes it to the given string builder. Only
+   * called locally with a new instance.
    */
-  private void buildPathString(StringBuilder result) {
+  protected void buildPathString(StringBuilder result) {
     if (isRootDirectory()) {
-      result.append('/');
+      result.append(PathFragment.ROOT_DIR);
     } else {
-      if (parent.isWindowsVolumeName()) {
-        result.append(parent.name);
-      } else {
-        parent.buildPathString(result);
-      }
+      parent.buildPathString(result);
       if (!parent.isRootDirectory()) {
-        result.append('/');
+        result.append(PathFragment.SEPARATOR_CHAR);
       }
       result.append(name);
     }
   }
 
   /**
-   * Returns true if the current path represents a Windows volume name (such as "c:" or "d:").
-   *
-   * <p>Paths such as '\\\\vol\\foo' are not supported.
-   */
-  private boolean isWindowsVolumeName() {
-    return OS.getCurrent() == OS.WINDOWS
-        && parent != null && parent.isRootDirectory() && name.length() == 2
-        && PathFragment.getWindowsDriveLetter(name) != '\0';
-  }
-
-  /**
    * Returns the path as a string.
    */
   public String getPathString() {
@@ -597,8 +677,8 @@ public class Path implements Comparable<Path>, Serializable {
     if (segment.equals(".") || segment.isEmpty()) {
       return this; // that's a noop
     } else if (segment.equals("..")) {
-      // root's parent is root, when canonicalising:
-      return parent == null || isWindowsVolumeName() ? this : parent;
+      // top-level directory's parent is root, when canonicalising:
+      return isTopLevelDirectory() ? this : parent;
     } else {
       return getCachedChildPath(segment);
     }
@@ -620,6 +700,10 @@ public class Path implements Comparable<Path>, Serializable {
     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.
@@ -630,10 +714,7 @@ public class Path implements Comparable<Path>, Serializable {
    * is canonical.
    */
   public Path getRelative(PathFragment suffix) {
-    Path result = suffix.isAbsolute() ? fileSystem.getRootDirectory() : this;
-    if (!suffix.windowsVolume().isEmpty()) {
-      result = result.getCanonicalPath(suffix.windowsVolume());
-    }
+    Path result = getRootForRelativePathComputation(suffix);
     for (String segment : suffix.segments()) {
       result = result.getCanonicalPath(segment);
     }
@@ -656,7 +737,7 @@ public class Path implements Comparable<Path>, Serializable {
     if ((path.length() == 0) || (path.equals("."))) {
       return this;
     } else if (path.equals("..")) {
-      return parent == null ? this : parent;
+      return isTopLevelDirectory() ? this : parent;
     } else if (path.indexOf('/') != -1) {
       return getRelative(new PathFragment(path));
     } else if (path.indexOf(PathFragment.EXTRA_SEPARATOR_CHAR) != -1) {
@@ -666,29 +747,20 @@ public class Path implements Comparable<Path>, Serializable {
     }
   }
 
-  /**
-   * Returns an absolute PathFragment representing this path.
-   */
-  public PathFragment asFragment() {
+  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();
     }
-
-    char driveLetter = '\0';
-    if (resultSegments.length > 0) {
-      driveLetter = PathFragment.getWindowsDriveLetter(resultSegments[0]);
-      if (driveLetter != '\0') {
-        // Strip off the first segment that contains the volume name.
-        resultSegments = Arrays.copyOfRange(resultSegments, 1, resultSegments.length);
-      }
-    }
-
-    return new PathFragment(driveLetter, true, resultSegments);
+    return resultSegments;
   }
 
+  /** Returns an absolute PathFragment representing this path. */
+  public PathFragment asFragment() {
+    return new PathFragment('\0', true, getSegments());
+  }
 
   /**
    * Returns a relative path fragment to this path, relative to {@code
@@ -708,17 +780,19 @@ public class Path implements Comparable<Path>, Serializable {
   public PathFragment relativeTo(Path ancestorPath) {
     checkSameFilesystem(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 new PathFragment('\0', false, resultSegments);
+    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 new PathFragment('\0', false, resultSegments);
+        }
       }
     }
 
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 14593791c8..c6a6ad601a 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
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.vfs;
 
 import com.google.common.base.Function;
+import com.google.common.base.Joiner;
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
@@ -106,13 +107,14 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
   // live PathFragments, so do not add further fields on a whim.
 
   // The individual path components.
+  // Does *not* include the Windows drive letter.
   private final String[] segments;
 
   // 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.
   private final boolean isAbsolute;
 
-  // Upper case windows drive letter, or '\0' if none. While a volumeName string is more
-  // general, we create a lot of these objects, so space is at a premium.
+  // Upper case Windows drive letter, or '\0' if none or unknown.
   private final char driveLetter;
 
   // hashCode and path are lazily initialized but semantically immutable.
@@ -123,13 +125,47 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
    * Construct a PathFragment from a string, which is an absolute or relative UNIX or Windows path.
    */
   public PathFragment(String path) {
-    this.driveLetter = getWindowsDriveLetter(path);
-    if (driveLetter != '\0') {
+    char drive = '\0';
+    boolean abs = false;
+    if (OS.getCurrent() == OS.WINDOWS) {
+      if (path.length() == 2 && isSeparator(path.charAt(0)) && Character.isLetter(path.charAt(1))) {
+        // Path is "/C" or other drive letter
+        drive = Character.toUpperCase(path.charAt(1));
+        abs = true;
+      } else if (path.length() >= 2
+          && Character.isLetter(path.charAt(0))
+          && path.charAt(1) == ':') {
+        // Path is like "C:", "C:/", "C:foo", or "C:/foo"
+        drive = Character.toUpperCase(path.charAt(0));
+      } else if (path.length() >= 3
+          && isSeparator(path.charAt(0))
+          && Character.isLetter(path.charAt(1))) {
+        if (isSeparator(path.charAt(2))) {
+          // Path is like "/C/" or "/C/foo"
+          drive = Character.toUpperCase(path.charAt(1));
+          abs = true;
+        } else if (path.charAt(2) == ':') {
+          // Path is like "/C:" or "/C:/" or "/C:/foo", neither of which is a valid path on MSYS.
+          // They are also very confusing because they would be valid, absolute PathFragments with
+          // no drive letters and the first segment being "C:".
+          // We should not be constructing such PathFragments on Windows because it would allow
+          // creating a valid Path object that would nevertheless be non-equal to "C:/" (because
+          // the internal representation would be different).
+          throw new IllegalArgumentException("Illegal path string \"" + path + "\"");
+        }
+      }
+    }
+
+    if (drive != '\0') {
       path = path.substring(2);
-      // TODO(bazel-team): Decide what to do about non-absolute paths with a volume name, e.g. C:x.
     }
-    this.isAbsolute = path.length() > 0 && isSeparator(path.charAt(0));
+    this.isAbsolute = abs || (path.length() > 0 && isSeparator(path.charAt(0)));
     this.segments = segment(path, isAbsolute ? 1 : 0);
+
+    // If the only difference between this object and EMPTY_FRAGMENT is the drive letter, then this
+    // object is equivalent with the empty fragment. To make them compare equal we must use a null
+    // drive letter.
+    this.driveLetter = (this.isAbsolute || this.segments.length > 0) ? drive : '\0';
   }
 
   private static boolean isSeparator(char c) {
@@ -150,6 +186,17 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
    * here in PathFragment, and by Path.asFragment() and Path.relativeTo().
    */
   PathFragment(char driveLetter, boolean isAbsolute, String[] segments) {
+    driveLetter = Character.toUpperCase(driveLetter);
+    if (OS.getCurrent() == OS.WINDOWS
+        && segments.length > 0
+        && segments[0].length() == 2
+        && Character.toUpperCase(segments[0].charAt(0)) == driveLetter
+        && segments[0].charAt(1) == ':') {
+      throw new IllegalStateException(
+          String.format(
+              "the drive letter should not be a path segment; drive='%c', segments=[%s]",
+              driveLetter, Joiner.on(", ").join(segments)));
+    }
     this.driveLetter = driveLetter;
     this.isAbsolute = isAbsolute;
     this.segments = segments;
@@ -338,7 +385,11 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
         ((driveLetter != '\0') ? 2 : 0)
         + ((segments.length == 0) ? 0 : (segments.length + 1) * 20);
     StringBuilder result = new StringBuilder(estimateSize);
-    result.append(windowsVolume());
+    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) {
@@ -412,9 +463,14 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     if (otherFragment == EMPTY_FRAGMENT) {
       return this;
     }
-    return otherFragment.isAbsolute()
-        ? otherFragment
-        : new PathFragment(this, otherFragment);
+
+    if (otherFragment.isAbsolute()) {
+      return this.driveLetter == '\0' || otherFragment.driveLetter != '\0'
+          ? otherFragment
+          : new PathFragment(this.driveLetter, true, otherFragment.segments);
+    } else {
+      return new PathFragment(this, otherFragment);
+    }
   }
 
   /**
@@ -539,9 +595,9 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
    * order)
    */
   public boolean startsWith(PathFragment prefix) {
-    if (this.isAbsolute != prefix.isAbsolute ||
-        this.segments.length < prefix.segments.length ||
-        this.driveLetter != prefix.driveLetter) {
+    if (this.isAbsolute != prefix.isAbsolute
+        || this.segments.length < prefix.segments.length
+        || (isAbsolute && this.driveLetter != prefix.driveLetter)) {
       return false;
     }
     for (int i = 0, len = prefix.segments.length; i < len; i++) {
@@ -627,9 +683,6 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
   }
 
   public String windowsVolume() {
-    if (OS.getCurrent() != OS.WINDOWS) {
-      return "";
-    }
     return (driveLetter != '\0') ? driveLetter + ":" : "";
   }
 
@@ -687,16 +740,8 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     return new PathFragment(driveLetter, false, segments);
   }
 
-  /**
-   * Given a path, returns the Windows drive letter ('X'), or an null character if no volume
-   * name was specified.
-   */
-  static char getWindowsDriveLetter(String path) {
-    if (OS.getCurrent() == OS.WINDOWS
-        && path.length() >= 2 && path.charAt(1) == ':' && Character.isLetter(path.charAt(0))) {
-      return Character.toUpperCase(path.charAt(0));
-    }
-    return '\0';
+  private boolean isEmpty() {
+    return !isAbsolute && segments.length == 0;
   }
 
   @Override
@@ -708,7 +753,7 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     // 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 there are the
+    // (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
@@ -719,10 +764,13 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     // once.
     int h = hashCode;
     if (h == 0) {
-      h = isAbsolute ? 1 : 0;
+      h = Boolean.hashCode(isAbsolute);
       for (String segment : segments) {
         h = h * 31 + segment.hashCode();
       }
+      if (!isEmpty()) {
+        h = h * 31 + Character.hashCode(driveLetter);
+      }
       hashCode = h;
     }
     return h;
@@ -737,8 +785,13 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
       return false;
     }
     PathFragment otherPath = (PathFragment) other;
-    return isAbsolute == otherPath.isAbsolute &&
-        Arrays.equals(otherPath.segments, segments);
+    if (isEmpty() && otherPath.isEmpty()) {
+      return true;
+    } else {
+      return isAbsolute == otherPath.isAbsolute
+          && driveLetter == otherPath.driveLetter
+          && Arrays.equals(otherPath.segments, segments);
+    }
   }
 
   /**
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 a9825959a8..23e7ad79ed 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
@@ -14,7 +14,6 @@
 package com.google.devtools.build.lib.vfs;
 
 import com.google.devtools.build.lib.util.Preconditions;
-
 import java.io.Serializable;
 import java.util.Objects;
 
@@ -49,7 +48,21 @@ public class RootedPath implements Serializable {
    * Returns a rooted path representing {@code relativePath} relative to {@code root}.
    */
   public static RootedPath toRootedPath(Path root, PathFragment relativePath) {
-    return new RootedPath(root, relativePath);
+    if (relativePath.isAbsolute()) {
+      if (root.isRootDirectory()) {
+        return new RootedPath(
+            root.getRelative(relativePath.windowsVolume()), relativePath.toRelative());
+      } else {
+        Preconditions.checkArgument(
+            relativePath.startsWith(root.asFragment()),
+            "relativePath '%s' is absolute, but it's not under root '%s'",
+            relativePath,
+            root);
+        return new RootedPath(root, relativePath.relativeTo(root.asFragment()));
+      }
+    } else {
+      return new RootedPath(root, relativePath);
+    }
   }
 
   /**
@@ -57,7 +70,7 @@ public class RootedPath implements Serializable {
    */
   public static RootedPath toRootedPath(Path root, Path path) {
     Preconditions.checkState(path.startsWith(root), "path: %s root: %s", path, root);
-    return new RootedPath(root, path.relativeTo(root));
+    return toRootedPath(root, path.asFragment());
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/WindowsFileSystem.java b/src/main/java/com/google/devtools/build/lib/vfs/WindowsFileSystem.java
index da04735831..13a7dd9976 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/WindowsFileSystem.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/WindowsFileSystem.java
@@ -15,22 +15,205 @@ package com.google.devtools.build.lib.vfs;
 
 import com.google.common.annotations.VisibleForTesting;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.lib.vfs.Path.PathFactory;
 import java.io.File;
 import java.io.FileNotFoundException;
 import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
 import java.nio.file.Files;
 import java.nio.file.LinkOption;
 import java.nio.file.attribute.BasicFileAttributes;
 import java.nio.file.attribute.DosFileAttributes;
+import java.util.Arrays;
+import java.util.concurrent.TimeUnit;
 
 /** Jury-rigged file system for Windows. */
 @ThreadSafe
 public class WindowsFileSystem extends JavaIoFileSystem {
 
+  @VisibleForTesting
+  enum WindowsPathFactory implements PathFactory {
+    INSTANCE {
+      @Override
+      public Path createRootPath(FileSystem filesystem) {
+        return new WindowsPath(filesystem, PathFragment.ROOT_DIR, null);
+      }
+
+      @Override
+      public Path createChildPath(Path parent, String childName) {
+        Preconditions.checkState(parent instanceof WindowsPath);
+        return new WindowsPath(parent.getFileSystem(), childName, (WindowsPath) parent);
+      }
+
+      @Override
+      public TranslatedPath translatePath(Path parent, String child) {
+        if (parent != null && parent.isRootDirectory()) {
+          // This is a top-level directory. It's either a drive name ("C:" or "c") or some other
+          // Unix path (e.g. "/usr").
+          //
+          // We need to translate it to an absolute Windows path. The correct way would be looking
+          // up /etc/mtab to see if any mount point matches the prefix of the path, and change the
+          // prefix to the mounted path. Looking up /etc/mtab each time we create a path however
+          // would be too expensive so we use a heuristic instead.
+          //
+          // If the name looks like a volume name ("C:" or "c") then we treat it as such, otherwise
+          // we make it relative to UNIX_ROOT, thus "/usr" becomes "C:/tools/msys64/usr".
+          //
+          // This heuristic ignores other mount points as well as procfs.
+
+          // TODO(bazel-team): get rid of this heuristic and translate paths using /etc/mtab.
+          // Figure out how to handle non-top-level mount points (e.g. "/usr/bin" is mounted to
+          // "/bin"), which is problematic because Paths are created segment by segment, so
+          // individual Path objects don't know they are parts of a mount point path.
+          // Another challenge is figuring out how and when to read /etc/mtab. A simple approach is
+          // to do it in determineUnixRoot, but then we won't pick up mount changes during the
+          // lifetime of the Bazel server process. A correct approach would be to establish a
+          // Skyframe FileValue-dependency on it, but it's unclear how this class could request or
+          // retrieve Skyframe-computed data.
+
+          if (WindowsPath.isWindowsVolumeName(child)) {
+            child = WindowsPath.getDriveLetter((WindowsPath) parent, child) + ":";
+          } else {
+            Preconditions.checkNotNull(
+                UNIX_ROOT,
+                "Could not determine Unix path root or it is not an absolute Windows path. Set the "
+                    + "\"%s\" JVM argument, or export the \"%s\" environment variable for the MSYS "
+                    + "bash and have /usr/bin/cygpath installed. Parent is \"%s\", name is \"%s\".",
+                WINDOWS_UNIX_ROOT_JVM_ARG,
+                BAZEL_SH_ENV_VAR,
+                parent,
+                child);
+            parent = parent.getRelative(UNIX_ROOT);
+          }
+        }
+        return new TranslatedPath(parent, child);
+      }
+    };
+  }
+
+  private static final class WindowsPath extends Path {
+
+    // The drive letter is '\0' if and only if this Path is the filesystem root "/".
+    private char driveLetter;
+
+    private WindowsPath(FileSystem fileSystem) {
+      super(fileSystem);
+      this.driveLetter = '\0';
+    }
+
+    private WindowsPath(FileSystem fileSystem, String name, WindowsPath parent) {
+      super(fileSystem, name, parent);
+      this.driveLetter = getDriveLetter(parent, name);
+    }
+
+    @Override
+    protected void buildPathString(StringBuilder result) {
+      if (isRootDirectory()) {
+        result.append(PathFragment.ROOT_DIR);
+      } else {
+        if (isTopLevelDirectory()) {
+          result.append(driveLetter).append(':').append(PathFragment.SEPARATOR_CHAR);
+        } else {
+          getParentDirectory().buildPathString(result);
+          if (!getParentDirectory().isTopLevelDirectory()) {
+            result.append(PathFragment.SEPARATOR_CHAR);
+          }
+          result.append(getBaseName());
+        }
+      }
+    }
+
+    @Override
+    public void reinitializeAfterDeserialization() {
+      Preconditions.checkState(
+          getParentDirectory().isRootDirectory() || getParentDirectory() instanceof WindowsPath);
+      this.driveLetter =
+          (getParentDirectory() != null) ? ((WindowsPath) getParentDirectory()).driveLetter : '\0';
+    }
+
+    @Override
+    public boolean isMaybeRelativeTo(Path ancestorCandidate) {
+      Preconditions.checkState(ancestorCandidate instanceof WindowsPath);
+      return ancestorCandidate.isRootDirectory()
+          || driveLetter == ((WindowsPath) ancestorCandidate).driveLetter;
+    }
+
+    @Override
+    public boolean isTopLevelDirectory() {
+      return isRootDirectory() || getParentDirectory().isRootDirectory();
+    }
+
+    @Override
+    public PathFragment asFragment() {
+      String[] segments = getSegments();
+      if (segments.length > 0) {
+        // Strip off the first segment that contains the volume name.
+        segments = Arrays.copyOfRange(segments, 1, segments.length);
+      }
+
+      return new PathFragment(driveLetter, true, segments);
+    }
+
+    @Override
+    protected Path getRootForRelativePathComputation(PathFragment relative) {
+      Path result = this;
+      if (relative.isAbsolute()) {
+        result = getFileSystem().getRootDirectory();
+        if (!relative.windowsVolume().isEmpty()) {
+          result = result.getRelative(relative.windowsVolume());
+        }
+      }
+      return result;
+    }
+
+    private static boolean isWindowsVolumeName(String name) {
+      return (name.length() == 1 || (name.length() == 2 && name.charAt(1) == ':'))
+          && Character.isLetter(name.charAt(0));
+    }
+
+    private static char getDriveLetter(WindowsPath parent, String name) {
+      if (parent == null) {
+        return '\0';
+      } else {
+        if (parent.isRootDirectory()) {
+          Preconditions.checkState(
+              isWindowsVolumeName(name),
+              "top-level directory on Windows must be a drive (name = '%s')",
+              name);
+          return Character.toUpperCase(name.charAt(0));
+        } else {
+          return parent.driveLetter;
+        }
+      }
+    }
+  }
+
+  private static final String WINDOWS_UNIX_ROOT_JVM_ARG = "bazel.windows_unix_root";
+  private static final String BAZEL_SH_ENV_VAR = "BAZEL_SH";
+
+  // Absolute Windows path specifying the root of absolute Unix paths.
+  // This is typically the MSYS installation root, e.g. C:\\tools\\msys64
+  private static final PathFragment UNIX_ROOT =
+      determineUnixRoot(WINDOWS_UNIX_ROOT_JVM_ARG, BAZEL_SH_ENV_VAR);
+
   public static final LinkOption[] NO_OPTIONS = new LinkOption[0];
   public static final LinkOption[] NO_FOLLOW = new LinkOption[] {LinkOption.NOFOLLOW_LINKS};
 
   @Override
+  protected PathFactory getPathFactory() {
+    return WindowsPathFactory.INSTANCE;
+  }
+
+  @Override
+  public String getFileSystemType(Path path) {
+    // TODO(laszlocsomor): implement this properly, i.e. actually query this information from
+    // somewhere (java.nio.Filesystem? System.getProperty? implement JNI method and use WinAPI?).
+    return "ntfs";
+  }
+
+  @Override
   protected void createSymbolicLink(Path linkPath, PathFragment targetFragment) throws IOException {
     // TODO(lberki): Add some JNI to create hard links/junctions instead of calling out to
     // cmd.exe
@@ -213,4 +396,57 @@ public class WindowsFileSystem extends JavaIoFileSystem {
     }
     return false;
   }
+
+  private static PathFragment determineUnixRoot(String jvmArgName, String bazelShEnvVar) {
+    // Get the path from a JVM argument, if specified.
+    String path = System.getProperty(jvmArgName);
+
+    if (path == null || path.isEmpty()) {
+      path = "";
+
+      // Fall back to executing cygpath.
+      String bash = System.getenv(bazelShEnvVar);
+      Process process = null;
+      try {
+        process = Runtime.getRuntime().exec("cmd.exe /C " + bash + " -c \"/usr/bin/cygpath -m /\"");
+
+        // Wait 3 seconds max, that should be enough to run this command.
+        process.waitFor(3, TimeUnit.SECONDS);
+
+        if (process.exitValue() == 0) {
+          path = readAll(process.getInputStream());
+        } else {
+          System.err.print(
+              String.format(
+                  "ERROR: %s (exit code: %d)%n",
+                  readAll(process.getErrorStream()), process.exitValue()));
+        }
+      } catch (InterruptedException | IOException e) {
+        // Silently ignore failure. Either MSYS is installed at a different location, or not
+        // installed at all, or some error occurred. We can't do anything anymore but throw an
+        // exception if someone tries to create a Path from an absolute Unix path.
+        return null;
+      }
+    }
+
+    path = path.trim();
+    PathFragment result = new PathFragment(path);
+    if (path.isEmpty() || result.getDriveLetter() == '\0' || !result.isAbsolute()) {
+      return null;
+    } else {
+      return result;
+    }
+  }
+
+  private static String readAll(InputStream s) throws IOException {
+    String result = "";
+    int len;
+    char[] buf = new char[4096];
+    try (InputStreamReader r = new InputStreamReader(s)) {
+      while ((len = r.read(buf)) > 0) {
+        result += new String(buf, 0, len);
+      }
+    }
+    return result;
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/ZipFileSystem.java b/src/main/java/com/google/devtools/build/lib/vfs/ZipFileSystem.java
index 4830d8fe19..1eedcd5858 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/ZipFileSystem.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/ZipFileSystem.java
@@ -16,7 +16,8 @@ package com.google.devtools.build.lib.vfs;
 import com.google.common.base.Predicate;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.util.Preconditions;
-
+import com.google.devtools.build.lib.vfs.Path.PathFactory;
+import com.google.devtools.build.lib.vfs.Path.PathFactory.TranslatedPath;
 import java.io.Closeable;
 import java.io.File;
 import java.io.FileNotFoundException;
@@ -96,6 +97,28 @@ public class ZipFileSystem extends ReadonlyFileSystem implements Closeable {
   // #getDirectoryEntries}.  Then this field becomes redundant.
   @ThreadSafe
   private static class ZipPath extends Path {
+
+    private enum Factory implements PathFactory {
+      INSTANCE {
+        @Override
+        public Path createRootPath(FileSystem filesystem) {
+          Preconditions.checkArgument(filesystem instanceof ZipFileSystem);
+          return new ZipPath((ZipFileSystem) filesystem);
+        }
+
+        @Override
+        public Path createChildPath(Path parent, String childName) {
+          Preconditions.checkState(parent instanceof ZipPath);
+          return new ZipPath((ZipFileSystem) parent.getFileSystem(), childName, (ZipPath) parent);
+        }
+
+        @Override
+        public TranslatedPath translatePath(Path parent, String child) {
+          return new TranslatedPath(parent, child);
+        }
+      };
+    }
+
     /**
      * Non-null iff this file/directory exists.  Set by setZipEntry for files
      * explicitly mentioned in the zipfile's table of contents, or implicitly
@@ -104,12 +127,12 @@ public class ZipFileSystem extends ReadonlyFileSystem implements Closeable {
     ZipEntry entry = null;
 
     // Root path.
-    ZipPath(ZipFileSystem fileSystem) {
+    private ZipPath(ZipFileSystem fileSystem) {
       super(fileSystem);
     }
 
     // Non-root paths.
-    ZipPath(ZipFileSystem fileSystem, String name, ZipPath parent) {
+    private ZipPath(ZipFileSystem fileSystem, String name, ZipPath parent) {
       super(fileSystem, name, parent);
     }
 
@@ -128,11 +151,6 @@ public class ZipFileSystem extends ReadonlyFileSystem implements Closeable {
         path.setZipEntry(new ZipEntry(path + "/")); // trailing "/" => isDir
       }
     }
-
-    @Override
-    protected ZipPath createChildPath(String childName) {
-      return new ZipPath((ZipFileSystem) getFileSystem(), childName, this);
-    }
   }
 
   /**
@@ -157,8 +175,8 @@ public class ZipFileSystem extends ReadonlyFileSystem implements Closeable {
   }
 
   @Override
-  protected Path createRootPath() {
-    return new ZipPath(this);
+  protected PathFactory getPathFactory() {
+    return ZipPath.Factory.INSTANCE;
   }
 
   /** Returns the ZipEntry associated with a given path name, if any. */