diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FileFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/FileFunction.java
index 76414eb..0ba6700 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FileFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FileFunction.java
@@ -78,10 +78,10 @@
     // In the course of resolving the real path of p, there will be a logical chain of paths we
     // consider. Going with the example from above, the full chain of paths we consider is
     // [a/b, c/b].
-    ArrayList<RootedPath> logicalChain = new ArrayList<>();
-    // Same contents as 'logicalChain', except stored as an sorted TreeSet for efficiency reasons.
+    final ArrayList<RootedPath> logicalChain = new ArrayList<>();
+    // Same contents as 'logicalChain', except stored as a sorted TreeSet for efficiency reasons.
     // See the usage in checkPathSeenDuringPartialResolutionInternal.
-    TreeSet<Path> sortedLogicalChain = Sets.newTreeSet();
+    final TreeSet<Path> sortedLogicalChain = Sets.newTreeSet();
 
     ImmutableList<RootedPath> pathToUnboundedAncestorSymlinkExpansionChain = null;
     ImmutableList<RootedPath> unboundedAncestorSymlinkExpansionChain = null;
@@ -145,9 +145,13 @@
         realFileStateValue);
   }
 
-  private static RootedPath getChild(RootedPath parentRootedPath, String baseName) {
+  private static RootedPath getChild(
+      RootedPath parent, String baseName, RootedPath originalParent, RootedPath originalChild) {
+    if (parent.equals(originalParent)) {
+      return originalChild; // Avoid constructing a new instance if we already have the child.
+    }
     return RootedPath.toRootedPath(
-        parentRootedPath.getRoot(), parentRootedPath.getRootRelativePath().getChild(baseName));
+        parent.getRoot(), parent.getRootRelativePath().getChild(baseName));
   }
 
   private RootedPath toRootedPath(Path path) {
@@ -180,14 +184,15 @@
       Environment env)
       throws InterruptedException, FileFunctionException {
     PathFragment relativePath = rootedPath.getRootRelativePath();
-    RootedPath rootedPathFromAncestors;
     String baseName = relativePath.getBaseName();
 
     FileValue parentFileValue = (FileValue) env.getValue(FileValue.key(parentRootedPath));
     if (parentFileValue == null) {
       return null;
     }
-    rootedPathFromAncestors = getChild(parentFileValue.realRootedPath(), baseName);
+
+    RootedPath rootedPathFromAncestors =
+        getChild(parentFileValue.realRootedPath(), baseName, parentRootedPath, rootedPath);
 
     if (!parentFileValue.exists() || !parentFileValue.isDirectory()) {
       return new PartialResolutionResult(
@@ -196,7 +201,9 @@
 
     for (RootedPath parentPartialRootedPath : parentFileValue.logicalChainDuringResolution()) {
       checkAndNotePathSeenDuringPartialResolution(
-          getChild(parentPartialRootedPath, baseName), symlinkResolutionState, env);
+          getChild(parentPartialRootedPath, baseName, parentRootedPath, rootedPath),
+          symlinkResolutionState,
+          env);
       if (env.valuesMissing()) {
         return null;
       }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java
index d3245b2..87ec403 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageLookupFunction.java
@@ -57,7 +57,7 @@
     /** Ignore the violation. */
     IGNORE,
     /** Generate an error. */
-    ERROR;
+    ERROR
   }
 
   private final AtomicReference<ImmutableSet<PackageIdentifier>> deletedPackages;
@@ -253,7 +253,6 @@
       BuildFileName buildFileName)
       throws InterruptedException, PackageLookupFunctionException {
     PathFragment buildFileFragment = buildFileName.getBuildFileFragment(packageIdentifier);
-    RootedPath buildFileRootedPath = RootedPath.toRootedPath(packagePathEntry, buildFileFragment);
 
     if (crossRepositoryLabelViolationStrategy == CrossRepositoryLabelViolationStrategy.ERROR) {
       // Is this path part of a local repository?
@@ -308,6 +307,7 @@
     }
 
     // Check for the existence of the build file.
+    RootedPath buildFileRootedPath = RootedPath.toRootedPath(packagePathEntry, buildFileFragment);
     FileValue fileValue = getFileValue(buildFileRootedPath, env, packageIdentifier);
     if (fileValue == null) {
       return null;
@@ -436,16 +436,15 @@
    * recursive target pattern (like foo/...).
    */
   private static final class PackageLookupFunctionException extends SkyFunctionException {
-    public PackageLookupFunctionException(BuildFileNotFoundException e, Transience transience) {
+    PackageLookupFunctionException(BuildFileNotFoundException e, Transience transience) {
       super(e, transience);
     }
 
-    public PackageLookupFunctionException(RepositoryFetchException e, Transience transience) {
+    PackageLookupFunctionException(RepositoryFetchException e, Transience transience) {
       super(e, transience);
     }
 
-    public PackageLookupFunctionException(
-        InconsistentFilesystemException e, Transience transience) {
+    PackageLookupFunctionException(InconsistentFilesystemException e, Transience transience) {
       super(e, transience);
     }
   }
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 c11c398..50d3095 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
@@ -13,10 +13,11 @@
 // limitations under the License.
 package com.google.devtools.build.lib.vfs;
 
-import com.google.common.base.Preconditions;
+import static com.google.common.base.Preconditions.checkArgument;
+
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.skyframe.SkyKey;
 import java.util.Comparator;
-import java.util.Objects;
 import javax.annotation.Nullable;
 
 /**
@@ -28,6 +29,9 @@
  */
 @AutoCodec
 public final class RootedPath implements Comparable<RootedPath>, FileStateKey {
+
+  private static final SkyKeyInterner<RootedPath> interner = SkyKey.newInterner();
+
   private final Root root;
   private final PathFragment rootRelativePath;
 
@@ -38,12 +42,16 @@
   /** Constructs a {@link RootedPath} from a {@link Root} and path fragment relative to the root. */
   @AutoCodec.Instantiator
   @AutoCodec.VisibleForSerialization
-  RootedPath(Root root, PathFragment rootRelativePath) {
-    Preconditions.checkState(
+  static RootedPath createInternal(Root root, PathFragment rootRelativePath) {
+    checkArgument(
         rootRelativePath.isAbsolute() == root.isAbsolute(),
         "rootRelativePath: %s root: %s",
         rootRelativePath,
         root);
+    return interner.intern(new RootedPath(root, rootRelativePath));
+  }
+
+  private RootedPath(Root root, PathFragment rootRelativePath) {
     this.root = root;
     this.rootRelativePath = rootRelativePath;
     this.hashCode = 31 * root.hashCode() + rootRelativePath.hashCode();
@@ -51,25 +59,20 @@
 
   /** Returns a rooted path representing {@code rootRelativePath} relative to {@code root}. */
   public static RootedPath toRootedPath(Root root, PathFragment rootRelativePath) {
-    if (rootRelativePath.isAbsolute()) {
-      if (root.isAbsolute()) {
-        return new RootedPath(root, rootRelativePath);
-      } else {
-        Preconditions.checkArgument(
-            root.contains(rootRelativePath),
-            "rootRelativePath '%s' is absolute, but it's not under root '%s'",
-            rootRelativePath,
-            root);
-        return new RootedPath(root, root.relativize(rootRelativePath));
-      }
-    } else {
-      return new RootedPath(root, rootRelativePath);
+    if (rootRelativePath.isAbsolute() && !root.isAbsolute()) {
+      checkArgument(
+          root.contains(rootRelativePath),
+          "rootRelativePath '%s' is absolute, but it's not under root '%s'",
+          rootRelativePath,
+          root);
+      rootRelativePath = root.relativize(rootRelativePath);
     }
+    return createInternal(root, rootRelativePath);
   }
 
   /** Returns a rooted path representing {@code path} under the root {@code root}. */
   public static RootedPath toRootedPath(Root root, Path path) {
-    Preconditions.checkState(root.contains(path), "path: %s root: %s", path, root);
+    checkArgument(root.contains(path), "path: %s root: %s", path, root);
     return toRootedPath(root, path.asFragment());
   }
 
@@ -105,7 +108,7 @@
     if (rootRelativeParentDirectory == null) {
       return null;
     }
-    return new RootedPath(root, rootRelativeParentDirectory);
+    return createInternal(root, rootRelativeParentDirectory);
   }
 
   @Override
@@ -117,8 +120,9 @@
       return false;
     }
     RootedPath other = (RootedPath) obj;
-    return Objects.equals(root, other.root)
-        && Objects.equals(rootRelativePath, other.rootRelativePath);
+    return hashCode == other.hashCode
+        && root.equals(other.root)
+        && rootRelativePath.equals(other.rootRelativePath);
   }
 
   @Override
@@ -143,4 +147,9 @@
   public RootedPath argument() {
     return this;
   }
+
+  @Override
+  public SkyKeyInterner<?> getSkyKeyInterner() {
+    return interner;
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/RootedPathAndCasing.java b/src/main/java/com/google/devtools/build/lib/vfs/RootedPathAndCasing.java
deleted file mode 100644
index 0cbeb2a..0000000
--- a/src/main/java/com/google/devtools/build/lib/vfs/RootedPathAndCasing.java
+++ /dev/null
@@ -1,76 +0,0 @@
-// Copyright 2019 The Bazel Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//    http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-package com.google.devtools.build.lib.vfs;
-
-import com.google.common.base.Preconditions;
-import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
-import java.util.Objects;
-
-/**
- * A {@link RootedPath} and its String representation.
- *
- * <p>This object stores not just a path but also the particular casing of it. On case-sensitive
- * filesystems, the paths "foo/Bar.txt" and "FOO/bar.TXT" are different files, but on
- * case-insensitive (or case-ignoring) they refer to the same file.
- *
- * <p>The {@code RootedPathAndCasing} class therefore allows comparing equal {@link RootedPath}s
- * that might use different casing.
- */
-@AutoCodec
-public final class RootedPathAndCasing {
-  private final RootedPath path;
-  private final String casing;
-  private final int hash;
-
-  /** Constructs a {@link RootedPath} from a {@link Root} and path fragment relative to the root. */
-  @AutoCodec.Instantiator
-  @AutoCodec.VisibleForSerialization
-  RootedPathAndCasing(RootedPath path, String casing) {
-    this.path = Preconditions.checkNotNull(path);
-    this.casing = Preconditions.checkNotNull(casing);
-    this.hash = Objects.hash(path, casing);
-  }
-
-  public static RootedPathAndCasing create(RootedPath path) {
-    return new RootedPathAndCasing(path, path.getRootRelativePath().getPathString());
-  }
-
-  public RootedPath getPath() {
-    return path;
-  }
-
-  @Override
-  public boolean equals(Object obj) {
-    if (this == obj) {
-      return true;
-    }
-    if (!(obj instanceof RootedPathAndCasing)) {
-      return false;
-    }
-    RootedPathAndCasing other = (RootedPathAndCasing) obj;
-    return hash == other.hash // fast track for unequal objects
-        && Objects.equals(path, other.path)
-        && Objects.equals(casing, other.casing);
-  }
-
-  @Override
-  public int hashCode() {
-    return hash;
-  }
-
-  @Override
-  public String toString() {
-    return "[" + path.getRoot() + "]/[" + casing + "]";
-  }
-}
diff --git a/src/test/java/com/google/devtools/build/lib/vfs/BUILD b/src/test/java/com/google/devtools/build/lib/vfs/BUILD
index d68268d..8b9e008 100644
--- a/src/test/java/com/google/devtools/build/lib/vfs/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/vfs/BUILD
@@ -18,7 +18,6 @@
 # Tests for Windows-specific functionality that can run cross-platform.
 CROSS_PLATFORM_WINDOWS_TESTS = [
     "PathFragmentWindowsTest.java",
-    "RootedPathAndCasingTest.java",
     "WindowsPathTest.java",
 ]
 
diff --git a/src/test/java/com/google/devtools/build/lib/vfs/RootedPathAndCasingTest.java b/src/test/java/com/google/devtools/build/lib/vfs/RootedPathAndCasingTest.java
deleted file mode 100644
index 48414fc..0000000
--- a/src/test/java/com/google/devtools/build/lib/vfs/RootedPathAndCasingTest.java
+++ /dev/null
@@ -1,82 +0,0 @@
-// Copyright 2019 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 static com.google.common.truth.Truth.assertThat;
-
-import com.google.devtools.build.lib.clock.BlazeClock;
-import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
-import org.junit.Test;
-import org.junit.runner.RunWith;
-import org.junit.runners.JUnit4;
-
-/** Tests for {@link RootedPathAndCasing}. */
-@RunWith(JUnit4.class)
-public class RootedPathAndCasingTest {
-  private final Path root =
-      new InMemoryFileSystem(BlazeClock.instance(), DigestHashFunction.SHA256).getPath("c:/");
-
-  @Test
-  public void testSanityCheckFilesystemIsCaseInsensitive() {
-    Path p1 = root.getRelative("Foo/Bar");
-    Path p2 = root.getRelative("FOO/BAR");
-    Path p3 = root.getRelative("control");
-    assertThat(p1).isNotSameInstanceAs(p2);
-    assertThat(p1).isNotSameInstanceAs(p3);
-    assertThat(p2).isNotSameInstanceAs(p3);
-    assertThat(p1).isEqualTo(p2);
-    assertThat(p1).isNotEqualTo(p3);
-  }
-
-  @Test
-  public void testEqualsAndHashCodeContract() {
-    PathFragment pf1 = PathFragment.create("Foo/Bar");
-    PathFragment pf2 = PathFragment.create("FOO/baR");
-    PathFragment pf3 = PathFragment.create("FOO/baR");
-    assertThat(pf1).isNotSameInstanceAs(pf2);
-    assertThat(pf2).isNotSameInstanceAs(pf3);
-    assertThat(pf1).isEqualTo(pf2);
-    assertThat(pf1).isEqualTo(pf3);
-
-    RootedPath rp1 = RootedPath.toRootedPath(Root.fromPath(root), pf1);
-    RootedPath rp2 = RootedPath.toRootedPath(Root.fromPath(root), pf2);
-    RootedPath rp3 = RootedPath.toRootedPath(Root.fromPath(root), pf3);
-    assertThat(rp1).isNotSameInstanceAs(rp2);
-    assertThat(rp2).isNotSameInstanceAs(rp3);
-    assertThat(rp1).isEqualTo(rp2);
-    assertThat(rp1).isEqualTo(rp3);
-    assertThat(rp1.hashCode()).isEqualTo(rp2.hashCode());
-    assertThat(rp1.hashCode()).isEqualTo(rp3.hashCode());
-
-    RootedPathAndCasing rpac1 = RootedPathAndCasing.create(rp1);
-    RootedPathAndCasing rpac2 = RootedPathAndCasing.create(rp2);
-    RootedPathAndCasing rpac3 = RootedPathAndCasing.create(rp3);
-    assertThat(rpac1).isNotSameInstanceAs(rpac2);
-    assertThat(rpac2).isNotSameInstanceAs(rpac3);
-    assertThat(rpac1).isNotEqualTo(rpac2);
-    assertThat(rpac2).isEqualTo(rpac3);
-    assertThat(rpac1.hashCode()).isNotEqualTo(rpac2.hashCode());
-    assertThat(rpac2.hashCode()).isEqualTo(rpac3.hashCode());
-  }
-
-  @Test
-  public void testToStringRespectsCasing() {
-    RootedPath rp1 = RootedPath.toRootedPath(Root.fromPath(root), PathFragment.create("Foo/Bar"));
-    RootedPath rp2 = RootedPath.toRootedPath(Root.fromPath(root), PathFragment.create("FOO/baR"));
-    RootedPathAndCasing rpac1 = RootedPathAndCasing.create(rp1);
-    RootedPathAndCasing rpac2 = RootedPathAndCasing.create(rp2);
-    assertThat(rpac1.toString()).contains("Foo/Bar");
-    assertThat(rpac2.toString()).contains("FOO/baR");
-  }
-}