diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
index 6587424..254be3c 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
@@ -146,7 +146,7 @@
   public <T, E extends Exception> void eval(
       TargetPatternResolver<T> resolver, BatchCallback<T, E> callback)
       throws TargetParsingException, E, InterruptedException {
-    eval(resolver, ImmutableSet.<String>of(), callback);
+    eval(resolver, ImmutableSet.<PathFragment>of(), callback);
   }
 
   /**
@@ -158,7 +158,7 @@
    */
   public abstract <T, E extends Exception> void eval(
       TargetPatternResolver<T> resolver,
-      ImmutableSet<String> excludedSubdirectories,
+      ImmutableSet<PathFragment> excludedSubdirectories,
       BatchCallback<T, E> callback)
       throws TargetParsingException, E, InterruptedException;
 
@@ -210,7 +210,7 @@
     @Override
     public <T, E extends Exception> void eval(
         TargetPatternResolver<T> resolver,
-        ImmutableSet<String> excludedSubdirectories,
+        ImmutableSet<PathFragment> excludedSubdirectories,
         BatchCallback<T, E> callback)
         throws TargetParsingException, E, InterruptedException {
       Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
@@ -264,7 +264,7 @@
     @Override
     public <T, E extends Exception> void eval(
         TargetPatternResolver<T> resolver,
-        ImmutableSet<String> excludedSubdirectories,
+        ImmutableSet<PathFragment> excludedSubdirectories,
         BatchCallback<T, E> callback)
         throws TargetParsingException, E, InterruptedException {
       Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
@@ -353,7 +353,7 @@
     @Override
     public <T, E extends Exception> void eval(
         TargetPatternResolver<T> resolver,
-        ImmutableSet<String> excludedSubdirectories,
+        ImmutableSet<PathFragment> excludedSubdirectories,
         BatchCallback<T, E> callback)
         throws TargetParsingException, E, InterruptedException {
       Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
@@ -463,7 +463,7 @@
     @Override
     public <T, E extends Exception> void eval(
         TargetPatternResolver<T> resolver,
-        ImmutableSet<String> excludedSubdirectories,
+        ImmutableSet<PathFragment> excludedSubdirectories,
         BatchCallback<T, E> callback)
         throws TargetParsingException, E, InterruptedException {
       resolver.findTargetsBeneathDirectory(
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java
index d98f78f..6cf7ddc 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java
@@ -17,6 +17,7 @@
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier.RepositoryName;
 import com.google.devtools.build.lib.util.BatchCallback;
+import com.google.devtools.build.lib.vfs.PathFragment;
 
 /**
  * A callback interface that is used during the process of converting target patterns (such as
@@ -86,7 +87,7 @@
       String originalPattern,
       String directory,
       boolean rulesOnly,
-      ImmutableSet<String> excludedSubdirectories,
+      ImmutableSet<PathFragment> excludedSubdirectories,
       BatchCallback<T, E> callback)
       throws TargetParsingException, E, InterruptedException;
 
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternResolverUtil.java b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternResolverUtil.java
index d7d9fd0..413eb1c 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternResolverUtil.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternResolverUtil.java
@@ -13,7 +13,6 @@
 // limitations under the License.
 package com.google.devtools.build.lib.pkgcache;
 
-import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.cmdline.LabelValidator;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets;
@@ -80,13 +79,4 @@
     }
     return directory;
   }
-
-  public static ImmutableSet<PathFragment> getPathFragments(ImmutableSet<String> pathPrefixes)
-      throws TargetParsingException {
-    ImmutableSet.Builder<PathFragment> pathFragmentsBuilder = ImmutableSet.builder();
-    for (String pathPrefix : pathPrefixes) {
-      pathFragmentsBuilder.add(TargetPatternResolverUtil.getPathFragment(pathPrefix));
-    }
-    return pathFragmentsBuilder.build();
-  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java
index cc12e3d..14c83ed 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java
@@ -81,7 +81,7 @@
     try {
       TargetPattern parsedPattern = patternKey.getParsedPattern();
       DepsOfPatternPreparer preparer = new DepsOfPatternPreparer(env, pkgPath.get());
-      ImmutableSet<String> excludedSubdirectories = patternKey.getExcludedSubdirectories();
+      ImmutableSet<PathFragment> excludedSubdirectories = patternKey.getExcludedSubdirectories();
       parsedPattern.<Void, RuntimeException>eval(
           preparer, excludedSubdirectories, NullCallback.<Void>instance());
     } catch (TargetParsingException e) {
@@ -215,13 +215,11 @@
         String originalPattern,
         String directory,
         boolean rulesOnly,
-        ImmutableSet<String> excludedSubdirectories,
+        ImmutableSet<PathFragment> excludedSubdirectories,
         BatchCallback<Void, E> callback)
         throws TargetParsingException, E, InterruptedException {
       FilteringPolicy policy =
           rulesOnly ? FilteringPolicies.RULES_ONLY : FilteringPolicies.NO_FILTER;
-      ImmutableSet<PathFragment> excludedPathFragments =
-          TargetPatternResolverUtil.getPathFragments(excludedSubdirectories);
       PathFragment pathFragment = TargetPatternResolverUtil.getPathFragment(directory);
       List<Path> roots = new ArrayList<>();
       if (repository.isDefault()) {
@@ -238,8 +236,10 @@
 
       for (Path root : roots) {
         RootedPath rootedPath = RootedPath.toRootedPath(root, pathFragment);
-        SkyValue token = env.getValue(PrepareDepsOfTargetsUnderDirectoryValue.key(
-            repository, rootedPath, excludedPathFragments, policy));
+        SkyValue token =
+            env.getValue(
+                PrepareDepsOfTargetsUnderDirectoryValue.key(
+                    repository, rootedPath, excludedSubdirectories, policy));
         if (token == null) {
           // A null token value means there is a missing dependency, because RecursivePkgFunction
           // never throws.
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java
index 572974a..48ef204 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternValue.java
@@ -22,6 +22,7 @@
 import com.google.devtools.build.lib.pkgcache.FilteringPolicies;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternSkyKeyOrException;
+import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
@@ -120,15 +121,17 @@
     return builder.build();
   }
 
-  private static TargetPatternKey setExcludedDirectories(TargetPatternKey original,
-      ImmutableSet<String> excludedSubdirectories) {
+  private static TargetPatternKey setExcludedDirectories(
+      TargetPatternKey original, ImmutableSet<PathFragment> excludedSubdirectories) {
     return new TargetPatternKey(original.getParsedPattern(), original.getPolicy(),
         original.isNegative(), original.getOffset(), excludedSubdirectories);
   }
 
-  private static ImmutableSet<String> excludedDirectoriesBeneath(TargetPatternKey targetPatternKey,
-      int position, List<TargetPatternSkyKeyOrException> keysMaybe) {
-    ImmutableSet.Builder<String> excludedDirectoriesBuilder = ImmutableSet.builder();
+  private static ImmutableSet<PathFragment> excludedDirectoriesBeneath(
+      TargetPatternKey targetPatternKey,
+      int position,
+      List<TargetPatternSkyKeyOrException> keysMaybe) {
+    ImmutableSet.Builder<PathFragment> excludedDirectoriesBuilder = ImmutableSet.builder();
     for (int j = position + 1; j < keysMaybe.size(); j++) {
       TargetPatternSkyKeyOrException laterPatternMaybe = keysMaybe.get(j);
       SkyKey laterSkyKey;
@@ -142,8 +145,7 @@
         TargetPattern laterParsedPattern = laterTargetPatternKey.getParsedPattern();
         if (laterTargetPatternKey.isNegative()
             && targetPatternKey.getParsedPattern().containsBelowDirectory(laterParsedPattern)) {
-          excludedDirectoriesBuilder.add(
-              laterParsedPattern.getDirectory().getPackageFragment().getPathString());
+          excludedDirectoriesBuilder.add(laterParsedPattern.getDirectory().getPackageFragment());
         }
       }
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
index 21c9482..5764b6c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
@@ -167,18 +167,16 @@
       String originalPattern,
       String directory,
       boolean rulesOnly,
-      ImmutableSet<String> excludedSubdirectories,
+      ImmutableSet<PathFragment> excludedSubdirectories,
       BatchCallback<Target, E> callback)
       throws TargetParsingException, E, InterruptedException {
     FilteringPolicy actualPolicy = rulesOnly
         ? FilteringPolicies.and(FilteringPolicies.RULES_ONLY, policy)
         : policy;
-    ImmutableSet<PathFragment> excludedPathFragments =
-        TargetPatternResolverUtil.getPathFragments(excludedSubdirectories);
     PathFragment pathFragment = TargetPatternResolverUtil.getPathFragment(directory);
     Iterable<PathFragment> packagesUnderDirectory =
         recursivePackageProvider.getPackagesUnderDirectory(
-            repository, pathFragment, excludedPathFragments);
+            repository, pathFragment, excludedSubdirectories);
 
     Iterable<PackageIdentifier> pkgIds = Iterables.transform(packagesUnderDirectory,
             new Function<PathFragment, PackageIdentifier>() {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternFunction.java
index 127d9b38..58c32ce 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternFunction.java
@@ -24,6 +24,7 @@
 import com.google.devtools.build.lib.skyframe.EnvironmentBackedRecursivePackageProvider.MissingDepException;
 import com.google.devtools.build.lib.util.BatchCallback;
 import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -55,7 +56,7 @@
           new RecursivePackageProviderBackedTargetPatternResolver(provider, env.getListener(),
               patternKey.getPolicy());
       TargetPattern parsedPattern = patternKey.getParsedPattern();
-      ImmutableSet<String> excludedSubdirectories = patternKey.getExcludedSubdirectories();
+      ImmutableSet<PathFragment> excludedSubdirectories = patternKey.getExcludedSubdirectories();
       final Set<Target> results = CompactHashSet.create();
       BatchCallback<Target, RuntimeException> callback =
           new BatchCallback<Target, RuntimeException>() {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java
index b419c77..bbf9277 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternValue.java
@@ -27,6 +27,7 @@
 import com.google.devtools.build.lib.pkgcache.FilteringPolicies;
 import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
 import com.google.devtools.build.lib.util.Preconditions;
+import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
@@ -136,9 +137,13 @@
         builder.add(new TargetPatternSkyKeyException(e, absoluteValueOfPattern));
         continue;
       }
-      TargetPatternKey targetPatternKey = new TargetPatternKey(targetPattern,
-          positive ? policy : FilteringPolicies.NO_FILTER, /*isNegative=*/!positive, offset,
-          ImmutableSet.<String>of());
+      TargetPatternKey targetPatternKey =
+          new TargetPatternKey(
+              targetPattern,
+              positive ? policy : FilteringPolicies.NO_FILTER, /*isNegative=*/
+              !positive,
+              offset,
+              ImmutableSet.<PathFragment>of());
       SkyKey skyKey = new SkyKey(SkyFunctions.TARGET_PATTERN, targetPatternKey);
       builder.add(new TargetPatternSkyKeyValue(skyKey));
     }
@@ -161,10 +166,14 @@
     private final boolean isNegative;
 
     private final String offset;
-    private final ImmutableSet<String> excludedSubdirectories;
+    private final ImmutableSet<PathFragment> excludedSubdirectories;
 
-    public TargetPatternKey(TargetPattern parsedPattern, FilteringPolicy policy,
-        boolean isNegative, String offset, ImmutableSet<String> excludedSubdirectories) {
+    public TargetPatternKey(
+        TargetPattern parsedPattern,
+        FilteringPolicy policy,
+        boolean isNegative,
+        String offset,
+        ImmutableSet<PathFragment> excludedSubdirectories) {
       this.parsedPattern = Preconditions.checkNotNull(parsedPattern);
       this.policy = Preconditions.checkNotNull(policy);
       this.isNegative = isNegative;
@@ -192,7 +201,7 @@
       return offset;
     }
 
-    public ImmutableSet<String> getExcludedSubdirectories() {
+    public ImmutableSet<PathFragment> getExcludedSubdirectories() {
       return excludedSubdirectories;
     }