Make PathFragment an abstract class.

There are now four concrete implementations: RelativeUnixPathFragment, AbsoluteUnixPathFragment, RelativeWindowsPathFragment, AbsoluteWindowsPathFragment.

Goals:
-Reduce memory usage of PathFragment on non-Windows platforms while maintaining existing semantics.
-Make a few simple performance improvements along the way.
-Add TODOs for a few more simple performance improvements.
-Open the way for reducing code complexity of PathFragment. All of the Windows-specific stuff ought not complicate the code so much.

Non goals:
-Make the entire codebase as pretty as possible wrt PathFragment & Windows.
-Make PathFragment usage more sane in general (e.g. change semantics to ban coexistence of Windows and Unix PathFragments).
-Optimize PathFragment as much as possible wrt memory or even in any other dimensions (e.g. gc churn, cpu).

To elaborate, the primary motivation is per-instance memory usage of PathFragment on Unix platforms:

Before this change
------------------
+UseCompressedOops --> 32 bytes per instance
-UseCompressedOops --> 40 bytes per instance

After this change
------------------
+UseCompressedOops --> 24 bytes per instance
-UseCompressedOops --> 32 bytes per instance

Since Bazel can retain lots of PathFragments, the memory savings of this CL are fairly large.

RELNOTES: None
PiperOrigin-RevId: 154052905

7 files changed, 673 insertions, 282 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
index 75b9a6b91e..34ab3f3fd1 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
@@ -152,7 +152,7 @@ public final class EvalUtils {
         || SkylarkInterfaceUtils.getSkylarkModule(c) != null
         || ImmutableMap.class.isAssignableFrom(c) // will be converted to SkylarkDict
         || NestedSet.class.isAssignableFrom(c) // will be converted to SkylarkNestedSet
-        || c.equals(PathFragment.class); // other known class
+        || PathFragment.class.isAssignableFrom(c); // other known class
   }
 
   // TODO(bazel-team): move the following few type-related functions to SkylarkType
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 ac8b756696..bf8c612d66 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
@@ -724,9 +724,7 @@ public class Path implements Comparable<Path>, Serializable {
       return this;
     } else if (path.equals("..")) {
       return isTopLevelDirectory() ? this : parent;
-    } else if (path.indexOf('/') != -1) {
-      return getRelative(PathFragment.create(path));
-    } else if (path.indexOf(PathFragment.EXTRA_SEPARATOR_CHAR) != -1) {
+    } else if (PathFragment.containsSeparator(path)) {
       return getRelative(PathFragment.create(path));
     } else {
       return getCachedChildPath(path);
@@ -745,7 +743,7 @@ public class Path implements Comparable<Path>, Serializable {
 
   /** Returns an absolute PathFragment representing this path. */
   public PathFragment asFragment() {
-    return PathFragment.createNoClone('\0', true, getSegments());
+    return PathFragment.createAlreadyInterned('\0', true, getSegments());
   }
 
   /**
@@ -777,7 +775,7 @@ public class Path implements Comparable<Path>, Serializable {
           currentPath = currentPath.getParentDirectory();
         }
         if (ancestorPath.equals(currentPath)) {
-          return PathFragment.createNoClone('\0', false, resultSegments);
+          return PathFragment.createAlreadyInterned('\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 e08a6d4465..41e45b1944 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,7 +14,6 @@
 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;
@@ -33,26 +32,26 @@ import java.util.List;
 import java.util.Set;
 
 /**
- * This class represents an immutable UNIX filesystem path, which may be absolute or relative. The
- * path is maintained as a simple ordered list of path segment strings.
+ * 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.
  *
  * <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>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
+ * <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.
  */
-@Immutable @ThreadSafe
-public final class PathFragment implements Comparable<PathFragment>, Serializable {
+@Immutable
+@ThreadSafe
+public abstract class PathFragment implements Comparable<PathFragment>, Serializable {
+  private static final Helper HELPER =
+      OS.getCurrent() == OS.WINDOWS ? WindowsPathFragment.HELPER : UnixPathFragment.HELPER;
 
-  public static final int INVALID_SEGMENT = -1;
-
-  public static final char SEPARATOR_CHAR = '/';
+  public static final char SEPARATOR_CHAR = HELPER.getPrimarySeparatorChar();
 
-  public static final char EXTRA_SEPARATOR_CHAR =
-      (OS.getCurrent() == OS.WINDOWS) ? '\\' : '/';
+  public static final int INVALID_SEGMENT = -1;
 
   public static final String ROOT_DIR = "/";
 
@@ -83,13 +82,96 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
         }
       };
 
+  /**
+   * 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 createNoClone(driveLetter, isAbsolute, internedSegments);
+    return createAlreadyInterned(driveLetter, isAbsolute, internedSegments);
   }
 
   /** Same as {@link #create(char, boolean, String[])}, except for {@link List}s of segments. */
@@ -98,7 +180,7 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     for (int i = 0; i < segments.size(); i++) {
       internedSegments[i] = StringCanonicalizer.intern(segments.get(i));
     }
-    return createNoClone(driveLetter, isAbsolute, internedSegments);
+    return createAlreadyInterned(driveLetter, isAbsolute, internedSegments);
   }
 
   /**
@@ -106,112 +188,80 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
    * relative UNIX path.  Does not support Windows-style Files.
    */
   public static PathFragment create(File path) {
-    return new PathFragment(path);
+    return HELPER.create(path.getPath());
   }
 
   /**
    * Construct a PathFragment from a string, which is an absolute or relative UNIX or Windows path.
    */
   public static PathFragment create(String path) {
-    return new PathFragment(path);
+    return HELPER.create(path);
   }
 
   /**
-   * Constructs a PathFragment, taking ownership of segments. Package-private,
-   * because it does not perform a defensive clone of the segments array. Used
+   * Constructs a PathFragment, taking ownership of {@code segments} and assuming the {@link
+   * String}s within have already been interned.
+   *
+   * <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().
    */
-  static PathFragment createNoClone(
+  static PathFragment createAlreadyInterned(
       char driveLetter, boolean isAbsolute, String[] segments) {
-    return new PathFragment(driveLetter, isAbsolute, 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);
   }
 
   /**
-   * Construct a PathFragment from a sequence of other PathFragments. The new
-   * fragment will be absolute iff the first fragment was absolute.
+   * Construct a PathFragment from a sequence of other PathFragments. The new fragment will be
+   * absolute iff the first fragment was absolute.
    */
+  // 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) {
-    return new PathFragment(first, second, more);
-  }
-
-  // We have 3 word-sized fields (segments, hashCode and path), and 2
-  // byte-sized ones, which fits in 16 bytes. Object sizes are rounded
-  // to 16 bytes.  Medium sized builds can easily hold millions of
-  // live PathFragments, so do not add further fields on a whim.
+    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);
+  }
+
+  // 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.
-  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 or unknown.
-  private final char driveLetter;
+  protected final String[] segments;
 
   // hashCode and path are lazily initialized but semantically immutable.
   private int hashCode;
   private String path;
 
-  private PathFragment(String path) {
-    this.driveLetter =
-        (OS.getCurrent() == OS.WINDOWS
-                && path.length() >= 2
-                && path.charAt(1) == ':'
-                && Character.isLetter(path.charAt(0)))
-            ? Character.toUpperCase(path.charAt(0))
-            : '\0';
-
-    if (driveLetter != '\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.segments = segment(path, isAbsolute ? 1 : 0);
-  }
-
-  private static boolean isSeparator(char c) {
-    return c == SEPARATOR_CHAR || c == EXTRA_SEPARATOR_CHAR;
-  }
-
-  private PathFragment(File path) {
-    this(path.getPath());
-  }
-
-  private 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;
+  protected PathFragment(String[] segments) {
     this.segments = segments;
   }
 
-  private PathFragment(PathFragment first, PathFragment second, PathFragment... more) {
-    // TODO(bazel-team): The handling of absolute path fragments in this constructor is unexpected.
-    this.segments = new String[sumLengths(first, second, more)];
-    int offset = 0;
-    offset += addSegments(offset, first);
-    offset += addSegments(offset, second);
-    for (PathFragment fragment : more) {
-      offset += addSegments(offset, fragment);
-    }
-    this.isAbsolute = first.isAbsolute;
-    this.driveLetter = first.driveLetter;
-  }
-
-  private int addSegments(int offset, PathFragment fragment) {
+  private static int addSegmentsTo(String[] segments, int offset, PathFragment fragment) {
     int count = fragment.segmentCount();
-    System.arraycopy(fragment.segments, 0, this.segments, offset, count);
+    System.arraycopy(fragment.segments, 0, segments, offset, count);
     return count;
   }
 
@@ -223,60 +273,11 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     return total;
   }
 
-  /**
-   * Segments the string passed in as argument and returns an array of strings.
-   * The split is performed along occurrences of (sequences of) the slash
-   * character.
-   *
-   * @param toSegment the string to segment
-   * @param offset how many characters from the start of the string to ignore.
-   */
-  private static String[] segment(String toSegment, int offset) {
-    int length = toSegment.length();
-
-    // Handle "/" and "" quickly.
-    if (length == offset) {
-      return new String[0];
-    }
-
-    // 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;
-  }
-
-  private Object writeReplace() {
+  protected Object writeReplace() {
     return new PathFragmentSerializationProxy(toString());
   }
 
-  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
+  protected void readObject(ObjectInputStream stream) throws InvalidObjectException {
     throw new InvalidObjectException("Serialization is allowed only by proxy");
   }
 
@@ -290,7 +291,7 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     if (path == null) {
       synchronized (this) {
         if (path == null) {
-          path = StringCanonicalizer.intern(joinSegments(SEPARATOR_CHAR));
+          path = StringCanonicalizer.intern(joinSegments(HELPER.getPrimarySeparatorChar()));
         }
       }
     }
@@ -303,7 +304,7 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
    */
   // TODO(bazel-team): Change getPathString to do this - this behavior makes more sense.
   public String getSafePathString() {
-    return (!isAbsolute && (segmentCount() == 0)) ? "." : getPathString();
+    return (!isAbsolute() && (segmentCount() == 0)) ? "." : getPathString();
   }
 
   /**
@@ -315,12 +316,12 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
    * the working directory) and not as command to be searched for in the search path.
    */
   public String getCallablePathString() {
-    if (isAbsolute) {
+    if (isAbsolute()) {
       return getPathString();
     } else if (segmentCount() == 0) {
       return ".";
     } else if (segmentCount() == 1) {
-      return "." + SEPARATOR_CHAR + getPathString();
+      return "." + HELPER.getPrimarySeparatorChar() + getPathString();
     } else {
       return getPathString();
     }
@@ -363,7 +364,7 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
   }
 
   private String joinSegments(char separatorChar) {
-    if (segments.length == 0 && isAbsolute) {
+    if (segments.length == 0 && isAbsolute()) {
       return windowsVolume() + ROOT_DIR;
     }
 
@@ -372,17 +373,17 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     // we do not have to expand the capacity of the StringBuilder.
     // Heuristically, this estimate is right for about 99% of the time.
     int estimateSize =
-        ((driveLetter != '\0') ? 2 : 0)
-        + ((segments.length == 0) ? 0 : (segments.length + 1) * 20);
+        ((getDriveLetter() != '\0') ? 2 : 0)
+            + ((segments.length == 0) ? 0 : (segments.length + 1) * 20);
     StringBuilder result = new StringBuilder(estimateSize);
-    if (isAbsolute) {
+    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) {
+      if (!initialSegment || isAbsolute()) {
         result.append(separatorChar);
       }
       initialSegment = false;
@@ -437,7 +438,8 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
       return this;
     }
 
-    return createNoClone(driveLetter, isAbsolute, subarray(scratchSegments, 0, segmentCount));
+    return HELPER.createAlreadyInterned(
+        getDriveLetter(), isAbsolute(), subarray(scratchSegments, 0, segmentCount));
   }
 
   /**
@@ -454,9 +456,10 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     }
 
     if (otherFragment.isAbsolute()) {
-      return this.driveLetter == '\0' || otherFragment.driveLetter != '\0'
+      char driveLetter = getDriveLetter();
+      return driveLetter == '\0' || otherFragment.getDriveLetter() != '\0'
           ? otherFragment
-          : createNoClone(this.driveLetter, true, otherFragment.segments);
+          : createAlreadyInterned(driveLetter, true, otherFragment.segments);
     } else {
       return create(this, otherFragment);
     }
@@ -490,7 +493,7 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     baseName = StringCanonicalizer.intern(baseName);
     String[] newSegments = Arrays.copyOf(segments, segments.length + 1);
     newSegments[newSegments.length - 1] = baseName;
-    return createNoClone(driveLetter, isAbsolute, newSegments);
+    return createAlreadyInterned(getDriveLetter(), isAbsolute(), newSegments);
   }
 
   /**
@@ -528,20 +531,19 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     String[] ancestorSegments = ancestorDirectory.segments();
     int ancestorLength = ancestorSegments.length;
 
-    if (isAbsolute != ancestorDirectory.isAbsolute()
-        || segments.length < ancestorLength) {
+    if (isAbsolute() != ancestorDirectory.isAbsolute() || segments.length < ancestorLength) {
       throw new IllegalArgumentException("PathFragment " + this
           + " is not beneath " + ancestorDirectory);
     }
 
-    if (!segmentsEqual(ancestorLength, segments, 0, ancestorSegments)) {
+    if (!HELPER.segmentsEqual(ancestorLength, segments, 0, ancestorSegments)) {
       throw new IllegalArgumentException(
           "PathFragment " + this + " is not beneath " + ancestorDirectory);
     }
 
     int length = segments.length - ancestorLength;
     String[] resultSegments = subarray(segments, ancestorLength, length);
-    return createNoClone('\0', false, resultSegments);
+    return createAlreadyInterned('\0', false, resultSegments);
   }
 
   /**
@@ -582,12 +584,12 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
    * order)
    */
   public boolean startsWith(PathFragment prefix) {
-    if (this.isAbsolute != prefix.isAbsolute
+    if (isAbsolute() != prefix.isAbsolute()
         || this.segments.length < prefix.segments.length
-        || (isAbsolute && this.driveLetter != prefix.driveLetter)) {
+        || (isAbsolute() && getDriveLetter() != prefix.getDriveLetter())) {
       return false;
     }
-    return segmentsEqual(prefix.segments.length, segments, 0, prefix.segments);
+    return HELPER.segmentsEqual(prefix.segments.length, segments, 0, prefix.segments);
   }
 
   /**
@@ -598,12 +600,12 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
    * order)
    */
   public boolean endsWith(PathFragment suffix) {
-    if ((suffix.isAbsolute && !suffix.equals(this)) ||
-        this.segments.length < suffix.segments.length) {
+    if ((suffix.isAbsolute() && !suffix.equals(this))
+        || this.segments.length < suffix.segments.length) {
       return false;
     }
     int offset = this.segments.length - suffix.segments.length;
-    return segmentsEqual(suffix.segments.length, segments, offset, suffix.segments);
+    return HELPER.segmentsEqual(suffix.segments.length, segments, offset, suffix.segments);
   }
 
   private static String[] subarray(String[] array, int start, int length) {
@@ -634,21 +636,20 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
       throw new IndexOutOfBoundsException(String.format("path: %s, beginIndex: %d endIndex: %d",
           toString(), beginIndex, endIndex));
     }
-    boolean isAbsolute = (beginIndex == 0) && this.isAbsolute;
+    boolean isAbsolute = (beginIndex == 0) && isAbsolute();
     return ((beginIndex == 0) && (endIndex == count))
         ? this
-        : createNoClone(
-            driveLetter,
-            isAbsolute,
-            subarray(segments, beginIndex, endIndex - beginIndex));
+        : createAlreadyInterned(
+            getDriveLetter(), isAbsolute, subarray(segments, beginIndex, endIndex - beginIndex));
   }
 
   /**
    * 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 boolean isAbsolute() {
-    return isAbsolute;
-  }
+  public abstract boolean isAbsolute();
 
   /**
    * Returns the segments of this path fragment. This array should not be
@@ -662,14 +663,12 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     return ImmutableList.copyOf(segments);
   }
 
-  public String windowsVolume() {
-    return (driveLetter != '\0') ? driveLetter + ":" : "";
-  }
+  public abstract String windowsVolume();
 
   /** Return the drive letter or '\0' if not applicable. */
-  public char getDriveLetter() {
-    return driveLetter;
-  }
+  // TODO(bazel-team): This doesn't need to pollute the PathFragment interface (ditto for
+  // windowsVolume).
+  public abstract char getDriveLetter();
 
   /**
    * Returns the number of segments in this path.
@@ -716,16 +715,12 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
    * same segments and drive letter.
    */
   public PathFragment toRelative() {
-    Preconditions.checkArgument(isAbsolute);
-    return createNoClone(driveLetter, false, segments);
-  }
-
-  private boolean isEmpty() {
-    return !isAbsolute && segments.length == 0;
+    Preconditions.checkArgument(isAbsolute());
+    return HELPER.createAlreadyInterned(getDriveLetter(), false, segments);
   }
 
   @Override
-  public int hashCode() {
+  public final int hashCode() {
     // We use the hash code caching strategy employed by java.lang.String. There are three subtle
     // things going on here:
     //
@@ -737,104 +732,29 @@ public final class PathFragment implements Comparable<PathFragment>, Serializabl
     // 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.
+    // 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.
-    int h = hashCode;
-    boolean isWindows = OS.getCurrent() == OS.WINDOWS;
-    if (h == 0) {
-      h = Boolean.valueOf(isAbsolute).hashCode();
-      for (String segment : segments) {
-        int segmentHash = isWindows ? segment.toLowerCase().hashCode() : segment.hashCode();
-        h = h * 31 + segmentHash;
-      }
-      if (!isEmpty()) {
-        h = h * 31 + Character.valueOf(driveLetter).hashCode();
-      }
-      hashCode = h;
+    if (hashCode == 0) {
+      hashCode = computeHashCode();
     }
-    return h;
+    return hashCode;
   }
 
-  @Override
-  public boolean equals(Object other) {
-    if (this == other) {
-      return true;
-    }
-    if (!(other instanceof PathFragment)) {
-      return false;
-    }
-    PathFragment otherPath = (PathFragment) other;
-    if (isEmpty() && otherPath.isEmpty()) {
-      return true;
-    } else {
-      return isAbsolute == otherPath.isAbsolute
-          && driveLetter == otherPath.driveLetter
-          && segments.length == otherPath.segments.length
-          && segmentsEqual(segments.length, segments, 0, otherPath.segments);
-    }
-  }
+  protected abstract int computeHashCode();
 
-  private static boolean segmentsEqual(
-      int length, String[] segments1, int offset1, String[] segments2) {
-    if ((segments1.length - offset1) < length || segments2.length < length) {
-      return false;
-    }
-    boolean isWindows = OS.getCurrent() == OS.WINDOWS;
-    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 (isWindows) {
-        seg1 = seg1.toLowerCase();
-        seg2 = seg2.toLowerCase();
-      }
-      if (!seg1.equals(seg2)) {
-        return false;
-      }
-    }
-    return true;
-  }
+  @Override
+  public abstract boolean equals(Object other);
 
   /**
    * Compares two PathFragments using the lexicographical order.
    */
   @Override
   public int compareTo(PathFragment p2) {
-    if (isAbsolute != p2.isAbsolute) {
-      return isAbsolute ? -1 : 1;
-    }
-    int cmp = Character.compare(driveLetter, p2.driveLetter);
-    if (cmp != 0) {
-      return cmp;
-    }
-    PathFragment p1 = this;
-    String[] segments1 = p1.segments;
-    String[] segments2 = p2.segments;
-    int len1 = segments1.length;
-    int len2 = segments2.length;
-    int n = Math.min(len1, len2);
-    boolean isWindows = OS.getCurrent() == OS.WINDOWS;
-    for (int i = 0; i < n; i++) {
-      String seg1 = segments1[i];
-      String seg2 = segments2[i];
-      if (isWindows) {
-        seg1 = seg1.toLowerCase();
-        seg2 = seg2.toLowerCase();
-      }
-      cmp = seg1.compareTo(seg2);
-      if (cmp != 0) {
-        return cmp;
-      }
-    }
-    return len1 - len2;
+    return HELPER.compare(this, p2);
   }
 
   @Override
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
new file mode 100644
index 0000000000..d83386affb
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/vfs/UnixPathFragment.java
@@ -0,0 +1,220 @@
+// 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.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/WindowsPathFragment.java b/src/main/java/com/google/devtools/build/lib/vfs/WindowsPathFragment.java
new file mode 100644
index 0000000000..4f94535acf
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/vfs/WindowsPathFragment.java
@@ -0,0 +1,252 @@
+// 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();
+
+  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 = '\\';
+
+    @Override
+    PathFragment create(String path) {
+      // TODO(laszlocsomor): Character#isLetter returns true for some non ASCII characters.
+      char driveLetter =
+          path.length() >= 2 && path.charAt(1) == ':' && Character.isLetter(path.charAt(0))
+              ? Character.toUpperCase(path.charAt(0))
+              : '\0';
+      if (driveLetter != '\0') {
+        path = path.substring(2);
+        // TODO(bazel-team): Decide what to do about non-absolute paths with a volume name, e.g.
+        // C:x.
+      }
+      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);
+    }
+
+    private boolean isEmpty() {
+      return segmentCount() == 0;
+    }
+
+    // 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/test/java/com/google/devtools/build/lib/vfs/PathFragmentTest.java b/src/test/java/com/google/devtools/build/lib/vfs/PathFragmentTest.java
index 2e455ccae8..4b84903601 100644
--- a/src/test/java/com/google/devtools/build/lib/vfs/PathFragmentTest.java
+++ b/src/test/java/com/google/devtools/build/lib/vfs/PathFragmentTest.java
@@ -73,7 +73,8 @@ public class PathFragmentTest {
         .addEqualityGroup(
             PathFragment.create("../relative/path"),
             PathFragment.create("..").getRelative("relative").getRelative("path"),
-            PathFragment.createNoClone('\0', false, new String[] {"..", "relative", "path"}),
+            PathFragment.createAlreadyInterned(
+                '\0', false, new String[] {"..", "relative", "path"}),
             PathFragment.create(new File("../relative/path")))
         .addEqualityGroup(PathFragment.create("something/else"))
         .addEqualityGroup(PathFragment.create("/something/else"))
diff --git a/src/test/java/com/google/devtools/build/lib/vfs/PathFragmentWindowsTest.java b/src/test/java/com/google/devtools/build/lib/vfs/PathFragmentWindowsTest.java
index 4915a889ff..90cc615836 100644
--- a/src/test/java/com/google/devtools/build/lib/vfs/PathFragmentWindowsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/vfs/PathFragmentWindowsTest.java
@@ -131,7 +131,7 @@ public class PathFragmentWindowsTest {
 
   private void assertRelativeTo(String path, String relativeTo, String... expectedPathSegments)
       throws Exception {
-    PathFragment expected = PathFragment.createNoClone('\0', false, expectedPathSegments);
+    PathFragment expected = PathFragment.createAlreadyInterned('\0', false, expectedPathSegments);
     PathFragment actual = PathFragment.create(path).relativeTo(relativeTo);
     assertThat(actual.getPathString()).isEqualTo(expected.getPathString());
     assertThat(actual).isEqualTo(expected);
@@ -149,7 +149,7 @@ public class PathFragmentWindowsTest {
   }
 
   private static PathFragment makePath(char drive, boolean absolute, String... segments) {
-    return PathFragment.createNoClone(drive, absolute, segments);
+    return PathFragment.createAlreadyInterned(drive, absolute, segments);
   }
 
   @Test
@@ -235,9 +235,9 @@ public class PathFragmentWindowsTest {
         PathFragment.EMPTY_FRAGMENT,
         PathFragment.create("C:"),
         PathFragment.create("D:"),
-        PathFragment.createNoClone('\0', false, new String[0]),
-        PathFragment.createNoClone('C', false, new String[0]),
-        PathFragment.createNoClone('D', false, new String[0]));
+        PathFragment.createAlreadyInterned('\0', false, new String[0]),
+        PathFragment.createAlreadyInterned('C', false, new String[0]),
+        PathFragment.createAlreadyInterned('D', false, new String[0]));
     assertAllEqual(PathFragment.create("/c"), PathFragment.create("/c/"));
     assertThat(PathFragment.create("C:/")).isNotEqualTo(PathFragment.create("/c"));
     assertThat(PathFragment.create("C:/foo")).isNotEqualTo(PathFragment.create("/c/foo"));