Replace path implementation.

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

A summary of changes:

PATH
====

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

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

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

ARTIFACT
========

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

RELNOTES: None
PiperOrigin-RevId: 185062932

14 files changed, 46 insertions, 53 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
index fa2c96e789..e9ae312128 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
@@ -545,8 +545,8 @@ public final class CcCommon {
             "ignoring invalid absolute path '" + includesAttr + "'");
         continue;
       }
-      PathFragment includesPath = packageFragment.getRelative(includesAttr).normalize();
-      if (!includesPath.isNormalized()) {
+      PathFragment includesPath = packageFragment.getRelative(includesAttr);
+      if (includesPath.containsUplevelReferences()) {
         ruleContext.attributeError("includes",
             "Path references a path above the execution root.");
       }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java
index d6464d1340..a7c1615d92 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java
@@ -757,15 +757,25 @@ public final class CcCompilationHelper {
           null);
     }
 
-    PathFragment prefix =
-        ruleContext.attributes().isAttributeValueExplicitlySpecified("include_prefix")
-            ? PathFragment.create(ruleContext.attributes().get("include_prefix", Type.STRING))
-            : null;
+    PathFragment prefix = null;
+    if (ruleContext.attributes().isAttributeValueExplicitlySpecified("include_prefix")) {
+      String prefixAttr = ruleContext.attributes().get("include_prefix", Type.STRING);
+      prefix = PathFragment.create(prefixAttr);
+      if (PathFragment.containsUplevelReferences(prefixAttr)) {
+        ruleContext.attributeError("include_prefix", "should not contain uplevel references");
+      }
+      if (prefix.isAbsolute()) {
+        ruleContext.attributeError("include_prefix", "should be a relative path");
+      }
+    }
 
     PathFragment stripPrefix;
     if (ruleContext.attributes().isAttributeValueExplicitlySpecified("strip_include_prefix")) {
-      stripPrefix =
-          PathFragment.create(ruleContext.attributes().get("strip_include_prefix", Type.STRING));
+      String stripPrefixAttr = ruleContext.attributes().get("strip_include_prefix", Type.STRING);
+      if (PathFragment.containsUplevelReferences(stripPrefixAttr)) {
+        ruleContext.attributeError("strip_include_prefix", "should not contain uplevel references");
+      }
+      stripPrefix = PathFragment.create(stripPrefixAttr);
       if (stripPrefix.isAbsolute()) {
         stripPrefix =
             ruleContext
@@ -791,18 +801,6 @@ public final class CcCompilationHelper {
           null);
     }
 
-    if (stripPrefix.containsUplevelReferences()) {
-      ruleContext.attributeError("strip_include_prefix", "should not contain uplevel references");
-    }
-
-    if (prefix != null && prefix.containsUplevelReferences()) {
-      ruleContext.attributeError("include_prefix", "should not contain uplevel references");
-    }
-
-    if (prefix != null && prefix.isAbsolute()) {
-      ruleContext.attributeError("include_prefix", "should be a relative path");
-    }
-
     if (ruleContext.hasErrors()) {
       return new PublicHeaders(ImmutableList.<Artifact>of(), ImmutableList.<Artifact>of(), null);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcIncLibrary.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcIncLibrary.java
index a844ef6375..9101e9b768 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcIncLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcIncLibrary.java
@@ -98,13 +98,12 @@ public abstract class CcIncLibrary implements RuleConfiguredTargetFactory {
 
     // For every source artifact, we compute a virtual artifact that is below the include directory.
     // These are used for include checking.
-    PathFragment prefixFragment = packageFragment.getRelative(expandedIncSymlinkAttr);
-    if (!prefixFragment.isNormalized()) {
+    if (!PathFragment.isNormalized(expandedIncSymlinkAttr)) {
       ruleContext.attributeWarning("prefix", "should not contain '.' or '..' elements");
     }
+    PathFragment prefixFragment = packageFragment.getRelative(expandedIncSymlinkAttr);
     ImmutableSortedMap.Builder<Artifact, Artifact> virtualArtifactMapBuilder =
         ImmutableSortedMap.orderedBy(Artifact.EXEC_PATH_COMPARATOR);
-    prefixFragment = prefixFragment.normalize();
     ImmutableList<Artifact> hdrs = ruleContext.getPrerequisiteArtifacts("hdrs", Mode.TARGET).list();
     for (Artifact src : hdrs) {
       // All declared header files must start with package/targetPrefix.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchain.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchain.java
index 122fc14914..5f848b4a29 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchain.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchain.java
@@ -169,10 +169,10 @@ public class CcToolchain implements RuleConfiguredTargetFactory {
       }
     }
 
-    PathFragment path = PathFragment.create(pathString);
-    if (!path.isNormalized()) {
+    if (!PathFragment.isNormalized(pathString)) {
       throw new InvalidConfigurationException("The include path '" + s + "' is not normalized.");
     }
+    PathFragment path = PathFragment.create(pathString);
     return pathPrefix.getRelative(path);
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompilationContext.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompilationContext.java
index da8827d6ac..ea12fadece 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompilationContext.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompilationContext.java
@@ -512,7 +512,7 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
      * absolute. Before it is stored, the include directory is normalized.
      */
     public Builder addIncludeDir(PathFragment includeDir) {
-      includeDirs.add(includeDir.normalize());
+      includeDirs.add(includeDir);
       return this;
     }
 
@@ -536,7 +536,7 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
      * is stored, the include directory is normalized.
      */
     public Builder addQuoteIncludeDir(PathFragment quoteIncludeDir) {
-      quoteIncludeDirs.add(quoteIncludeDir.normalize());
+      quoteIncludeDirs.add(quoteIncludeDir);
       return this;
     }
 
@@ -547,7 +547,7 @@ public final class CppCompilationContext implements TransitiveInfoProvider {
      * is stored, the include directory is normalized.
      */
     public Builder addSystemIncludeDir(PathFragment systemIncludeDir) {
-      systemIncludeDirs.add(systemIncludeDir.normalize());
+      systemIncludeDirs.add(systemIncludeDir);
       return this;
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
index 247d3ef91f..e462a03822 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
@@ -488,8 +488,7 @@ public class CppCompileActionBuilder {
       if (includePath.startsWith(Label.EXTERNAL_PATH_PREFIX)) {
         includePath = includePath.relativeTo(Label.EXTERNAL_PATH_PREFIX);
       }
-      if (includePath.isAbsolute()
-          || !PathFragment.EMPTY_FRAGMENT.getRelative(includePath).normalize().isNormalized()) {
+      if (includePath.isAbsolute() || includePath.containsUplevelReferences()) {
         errorReporter.accept(
             String.format(
                 "The include path '%s' references a path outside of the execution root.",
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppConfiguration.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppConfiguration.java
index 058f34db51..107a4cce77 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppConfiguration.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppConfiguration.java
@@ -1381,15 +1381,15 @@ public final class CppConfiguration extends BuildConfiguration.Fragment {
   }
 
   public static PathFragment computeDefaultSysroot(CToolchain toolchain) {
-    PathFragment defaultSysroot =
-        toolchain.getBuiltinSysroot().length() == 0
-            ? null
-            : PathFragment.create(toolchain.getBuiltinSysroot());
-    if ((defaultSysroot != null) && !defaultSysroot.isNormalized()) {
+    String builtInSysroot = toolchain.getBuiltinSysroot();
+    if (builtInSysroot.isEmpty()) {
+      return null;
+    }
+    if (!PathFragment.isNormalized(builtInSysroot)) {
       throw new IllegalArgumentException(
-          "The built-in sysroot '" + defaultSysroot + "' is not normalized.");
+          "The built-in sysroot '" + builtInSysroot + "' is not normalized.");
     }
-    return defaultSysroot;
+    return PathFragment.create(builtInSysroot);
   }
 
   @Override
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppToolchainInfo.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppToolchainInfo.java
index 135b70be3b..91f95020b8 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppToolchainInfo.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppToolchainInfo.java
@@ -794,11 +794,11 @@ public final class CppToolchainInfo {
       CToolchain toolchain, PathFragment crosstoolTopPathFragment) {
     Map<String, PathFragment> toolPathsCollector = Maps.newHashMap();
     for (CrosstoolConfig.ToolPath tool : toolchain.getToolPathList()) {
-      PathFragment path = PathFragment.create(tool.getPath());
-      if (!path.isNormalized()) {
-        throw new IllegalArgumentException(
-            "The include path '" + tool.getPath() + "' is not normalized.");
+      String pathStr = tool.getPath();
+      if (!PathFragment.isNormalized(pathStr)) {
+        throw new IllegalArgumentException("The include path '" + pathStr + "' is not normalized.");
       }
+      PathFragment path = PathFragment.create(pathStr);
       toolPathsCollector.put(tool.getName(), crosstoolTopPathFragment.getRelative(path));
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCommon.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCommon.java
index 458ac578d1..b2394ca51d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCommon.java
@@ -505,9 +505,9 @@ public class JavaCommon {
 
     if (!javaExecutable.isAbsolute()) {
       javaExecutable =
-          PathFragment.create(PathFragment.create(ruleContext.getWorkspaceName()), javaExecutable);
+          PathFragment.create(ruleContext.getWorkspaceName()).getRelative(javaExecutable);
     }
-    return javaExecutable.normalize().getPathString();
+    return javaExecutable.getPathString();
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/rules/nativedeps/NativeDepsHelper.java b/src/main/java/com/google/devtools/build/lib/rules/nativedeps/NativeDepsHelper.java
index 7f6437ed24..e15c7485a3 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/nativedeps/NativeDepsHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/nativedeps/NativeDepsHelper.java
@@ -312,7 +312,7 @@ public abstract class NativeDepsHelper {
     PathFragment libParentDir =
         relativePath.replaceName(lib.getExecPath().getParentDirectory().getBaseName());
     String libName = lib.getExecPath().getBaseName();
-    return PathFragment.create(libParentDir, PathFragment.create(libName));
+    return libParentDir.getRelative(libName);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleStubBinary.java b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleStubBinary.java
index 2e84f6f491..e73c66572a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/AppleStubBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/AppleStubBinary.java
@@ -188,8 +188,7 @@ public class AppleStubBinary implements RuleConfiguredTargetFactory {
 
     makeVariableContext.validatePathRoot(pathString);
 
-    PathFragment pathFragment = PathFragment.create(pathString);
-    if (!pathFragment.isNormalized()) {
+    if (!PathFragment.isNormalized(pathString)) {
       throw ruleContext.throwWithAttributeError(
           AppleStubBinaryRule.XCENV_BASED_PATH_ATTR, PATH_NOT_NORMALIZED_ERROR);
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/CompilationAttributes.java b/src/main/java/com/google/devtools/build/lib/rules/objc/CompilationAttributes.java
index 39c28b750a..f3c79b270b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/CompilationAttributes.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/CompilationAttributes.java
@@ -403,7 +403,7 @@ final class CompilationAttributes {
           Iterables.filter(includes(), Predicates.not(PathFragment::isAbsolute));
       for (PathFragment include : relativeIncludes) {
         for (PathFragment rootFragment : rootFragments) {
-          paths.add(rootFragment.getRelative(include).normalize());
+          paths.add(rootFragment.getRelative(include));
         }
       }
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/J2ObjcLibrary.java b/src/main/java/com/google/devtools/build/lib/rules/objc/J2ObjcLibrary.java
index 27c1f67b5e..61bbb37431 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/J2ObjcLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/J2ObjcLibrary.java
@@ -130,7 +130,7 @@ public class J2ObjcLibrary implements RuleConfiguredTargetFactory {
     // We add another header search path with gen root if we have generated sources to translate.
     for (Artifact sourceToTranslate : sourcesToTranslate) {
       if (!sourceToTranslate.isSourceArtifact()) {
-        headerSearchPaths.add(PathFragment.create(objcFileRootExecPath, genRoot));
+        headerSearchPaths.add(objcFileRootExecPath.getRelative(genRoot));
         return headerSearchPaths.build();
       }
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/ProtobufSupport.java b/src/main/java/com/google/devtools/build/lib/rules/objc/ProtobufSupport.java
index 1a7e1e28f6..b3c6d7e93c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/ProtobufSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/ProtobufSupport.java
@@ -515,8 +515,7 @@ final class ProtobufSupport {
     // of dependers.
     PathFragment rootRelativeOutputDir = ruleContext.getUniqueDirectory(UNIQUE_DIRECTORY_NAME);
 
-    return PathFragment.create(
-        buildConfiguration.getBinDirectory().getExecPath(), rootRelativeOutputDir);
+    return buildConfiguration.getBinDirectory().getExecPath().getRelative(rootRelativeOutputDir);
   }
 
   private Iterable<Artifact> getGeneratedProtoOutputs(
@@ -526,9 +525,8 @@ final class ProtobufSupport {
       String protoFileName = FileSystemUtils.removeExtension(protoFile.getFilename());
       String generatedOutputName = attributes.getGeneratedProtoFilename(protoFileName, true);
 
-      PathFragment generatedFilePath = PathFragment.create(
-          protoFile.getRootRelativePath().getParentDirectory(),
-          PathFragment.create(generatedOutputName));
+      PathFragment generatedFilePath =
+          protoFile.getRootRelativePath().getParentDirectory().getRelative(generatedOutputName);
 
       PathFragment outputFile = FileSystemUtils.appendExtension(generatedFilePath, extension);