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 deeec79..dee9659 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
@@ -53,6 +53,7 @@
   private static final Parser DEFAULT_PARSER = new Parser("");
 
   private final Type type;
+  private final String originalPattern;
 
   /**
    * Returns a parser with no offset. Note that the Parser class is immutable, so this method may
@@ -104,9 +105,10 @@
     return SLASH_JOINER.join(pieces);
   }
 
-  private TargetPattern(Type type) {
+  private TargetPattern(Type type, String originalPattern) {
     // Don't allow inheritance outside this class.
     this.type = type;
+    this.originalPattern = Preconditions.checkNotNull(originalPattern);
   }
 
   /**
@@ -118,6 +120,13 @@
   }
 
   /**
+   * Return the string that was parsed into this pattern.
+   */
+  public String getOriginalPattern() {
+    return originalPattern;
+  }
+
+  /**
    * Evaluates the current target pattern and returns the result.
    */
   public <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver)
@@ -160,8 +169,8 @@
     private final String targetName;
     private final String directory;
 
-    private SingleTarget(String targetName, String directory) {
-      super(Type.SINGLE_TARGET);
+    private SingleTarget(String targetName, String directory, String originalPattern) {
+      super(Type.SINGLE_TARGET, originalPattern);
       this.targetName = Preconditions.checkNotNull(targetName);
       this.directory = Preconditions.checkNotNull(directory);
     }
@@ -172,7 +181,7 @@
         throws TargetParsingException, InterruptedException {
       Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
           "Target pattern \"%s\" of type %s cannot be evaluated with excluded subdirectories: %s.",
-          targetName, getType(), excludedSubdirectories);
+          getOriginalPattern(), getType(), excludedSubdirectories);
       return resolver.getExplicitTarget(targetName);
     }
 
@@ -208,8 +217,8 @@
 
     private final String path;
 
-    private InterpretPathAsTarget(String path) {
-      super(Type.PATH_AS_TARGET);
+    private InterpretPathAsTarget(String path, String originalPattern) {
+      super(Type.PATH_AS_TARGET, originalPattern);
       this.path = normalize(Preconditions.checkNotNull(path));
     }
 
@@ -219,7 +228,7 @@
         throws TargetParsingException, InterruptedException {
       Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
           "Target pattern \"%s\" of type %s cannot be evaluated with excluded subdirectories: %s.",
-          path, getType(), excludedSubdirectories);
+          getOriginalPattern(), getType(), excludedSubdirectories);
       if (resolver.isPackage(path)) {
         // User has specified a package name. lookout for default target.
         return resolver.getExplicitTarget("//" + path);
@@ -271,7 +280,6 @@
 
   private static final class TargetsInPackage extends TargetPattern {
 
-    private final String originalPattern;
     private final String pattern;
     private final String suffix;
     private final boolean isAbsolute;
@@ -280,8 +288,7 @@
 
     private TargetsInPackage(String originalPattern, String pattern, String suffix,
         boolean isAbsolute, boolean rulesOnly, boolean checkWildcardConflict) {
-      super(Type.TARGETS_IN_PACKAGE);
-      this.originalPattern = Preconditions.checkNotNull(originalPattern);
+      super(Type.TARGETS_IN_PACKAGE, originalPattern);
       this.pattern = Preconditions.checkNotNull(pattern);
       this.suffix = Preconditions.checkNotNull(suffix);
       this.isAbsolute = isAbsolute;
@@ -295,14 +302,14 @@
         throws TargetParsingException, InterruptedException {
       Preconditions.checkArgument(excludedSubdirectories.isEmpty(),
           "Target pattern \"%s\" of type %s cannot be evaluated with excluded subdirectories: %s.",
-          originalPattern, getType(), excludedSubdirectories);
+          getOriginalPattern(), getType(), excludedSubdirectories);
       if (checkWildcardConflict) {
         ResolvedTargets<T> targets = getWildcardConflict(resolver);
         if (targets != null) {
           return targets;
         }
       }
-      return resolver.getTargetsInPackage(originalPattern, removeSuffix(pattern, suffix),
+      return resolver.getTargetsInPackage(getOriginalPattern(), removeSuffix(pattern, suffix),
           rulesOnly);
     }
 
@@ -327,13 +334,13 @@
       TargetsInPackage that = (TargetsInPackage) o;
       return isAbsolute == that.isAbsolute && rulesOnly == that.rulesOnly
           && checkWildcardConflict == that.checkWildcardConflict
-          && originalPattern.equals(that.originalPattern)
+          && getOriginalPattern().equals(that.getOriginalPattern())
           && pattern.equals(that.pattern) && suffix.equals(that.suffix);
     }
 
     @Override
     public int hashCode() {
-      return Objects.hash(getType(), originalPattern, pattern, suffix, isAbsolute, rulesOnly,
+      return Objects.hash(getType(), getOriginalPattern(), pattern, suffix, isAbsolute, rulesOnly,
           checkWildcardConflict);
     }
 
@@ -373,13 +380,11 @@
 
   private static final class TargetsBelowDirectory extends TargetPattern {
 
-    private final String originalPattern;
     private final String directory;
     private final boolean rulesOnly;
 
     private TargetsBelowDirectory(String originalPattern, String directory, boolean rulesOnly) {
-      super(Type.TARGETS_BELOW_DIRECTORY);
-      this.originalPattern = Preconditions.checkNotNull(originalPattern);
+      super(Type.TARGETS_BELOW_DIRECTORY, originalPattern);
       this.directory = Preconditions.checkNotNull(directory);
       this.rulesOnly = rulesOnly;
     }
@@ -388,7 +393,7 @@
     public <T> ResolvedTargets<T> eval(TargetPatternResolver<T> resolver,
         ImmutableSet<String> excludedSubdirectories)
         throws TargetParsingException, InterruptedException {
-      return resolver.findTargetsBeneathDirectory(originalPattern, directory, rulesOnly,
+      return resolver.findTargetsBeneathDirectory(getOriginalPattern(), directory, rulesOnly,
           excludedSubdirectories);
     }
 
@@ -415,13 +420,13 @@
         return false;
       }
       TargetsBelowDirectory that = (TargetsBelowDirectory) o;
-      return rulesOnly == that.rulesOnly && originalPattern.equals(that.originalPattern)
+      return rulesOnly == that.rulesOnly && getOriginalPattern().equals(that.getOriginalPattern())
           && directory.equals(that.directory);
     }
 
     @Override
     public int hashCode() {
-      return Objects.hash(getType(), originalPattern, directory, rulesOnly);
+      return Objects.hash(getType(), getOriginalPattern(), directory, rulesOnly);
     }
   }
 
@@ -557,7 +562,7 @@
           String error = "invalid target format '" + originalPattern + "': " + e.getMessage();
           throw new TargetParsingException(error);
         }
-        return new SingleTarget(fullLabel, packageAndTarget.getPackageName());
+        return new SingleTarget(fullLabel, packageAndTarget.getPackageName(), originalPattern);
       }
 
       // This is a stripped-down version of interpretPathAsTarget that does no I/O.  We have a basic
@@ -575,7 +580,7 @@
         throw new TargetParsingException("Bad target pattern '" + originalPattern + "': " +
             errorMessage);
       }
-      return new InterpretPathAsTarget(pattern);
+      return new InterpretPathAsTarget(pattern, originalPattern);
     }
 
     /**
diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
index ec84e1f..c3faec8 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
@@ -361,11 +361,10 @@
       } else {
         // If the graph doesn't contain a value for this target pattern, try to directly evaluate
         // it, by making use of packages already present in the graph.
-        TargetPattern.Parser parser = new TargetPattern.Parser(targetPatternKey.getOffset());
         RecursivePackageProviderBackedTargetPatternResolver resolver =
             new RecursivePackageProviderBackedTargetPatternResolver(provider, eventHandler,
                 targetPatternKey.getPolicy(), pkgPath);
-        TargetPattern parsedPattern = parser.parse(targetPatternKey.getPattern());
+        TargetPattern parsedPattern = targetPatternKey.getParsedPattern();
         try {
           result.put(pattern, parsedPattern.eval(resolver));
         } catch (TargetParsingException e) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunction.java
index bd280dd..6653c48 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunction.java
@@ -15,6 +15,7 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.base.Predicates;
+import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.events.Event;
@@ -24,6 +25,7 @@
 import com.google.devtools.build.lib.pkgcache.ParseFailureListener;
 import com.google.devtools.build.lib.skyframe.PrepareDepsOfPatternsValue.TargetPatternSequence;
 import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternKey;
+import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternSkyKeyOrException;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -50,20 +52,32 @@
   @Nullable
   @Override
   public SkyValue compute(SkyKey skyKey, Environment env) throws InterruptedException {
+    EventHandler eventHandler = env.getListener();
+    boolean handlerIsParseFailureListener = eventHandler instanceof ParseFailureListener;
     TargetPatternSequence targetPatternSequence = (TargetPatternSequence) skyKey.argument();
-    Iterable<SkyKey> patternSkyKeys = TargetPatternValue.keys(targetPatternSequence.getPatterns(),
-        targetPatternSequence.getPolicy(), targetPatternSequence.getOffset());
+    Iterable<TargetPatternSkyKeyOrException> keysMaybe =
+        TargetPatternValue.keys(targetPatternSequence.getPatterns(),
+            targetPatternSequence.getPolicy(), targetPatternSequence.getOffset());
+
+    ImmutableList.Builder<SkyKey> skyKeyBuilder = ImmutableList.builder();
+    for (TargetPatternSkyKeyOrException skyKeyOrException : keysMaybe) {
+      try {
+        skyKeyBuilder.add(skyKeyOrException.getSkyKey());
+      } catch (TargetParsingException e) {
+        handleTargetParsingException(eventHandler, handlerIsParseFailureListener,
+            skyKeyOrException.getOriginalPattern(), e);
+      }
+    }
+    ImmutableList<SkyKey> skyKeys = skyKeyBuilder.build();
+
     Map<SkyKey, ValueOrException<TargetParsingException>> targetPatternValuesByKey =
-        env.getValuesOrThrow(patternSkyKeys, TargetParsingException.class);
+        env.getValuesOrThrow(skyKeys, TargetParsingException.class);
     if (env.valuesMissing()) {
       return null;
     }
 
-    EventHandler eventHandler = env.getListener();
-    boolean handlerIsParseFailureListener = eventHandler instanceof ParseFailureListener;
-
     ResolvedTargets.Builder<Label> builder = ResolvedTargets.builder();
-    for (SkyKey key : patternSkyKeys) {
+    for (SkyKey key : skyKeys) {
       try {
         // The only exception type throwable by TargetPatternFunction is TargetParsingException.
         // Therefore all ValueOrException values in the map will either be non-null or throw
@@ -102,13 +116,18 @@
 
   private static void handleTargetParsingException(EventHandler eventHandler,
       boolean handlerIsParseFailureListener, SkyKey key, TargetParsingException e) {
-    TargetPatternKey pattern = (TargetPatternKey) key.argument();
-    String rawPattern = pattern.getPattern();
+    TargetPatternKey patternKey = (TargetPatternKey) key.argument();
+    String rawPattern = patternKey.getPattern();
+    handleTargetParsingException(eventHandler, handlerIsParseFailureListener, rawPattern, e);
+  }
+
+  private static void handleTargetParsingException(EventHandler eventHandler,
+      boolean handlerIsParseFailureListener, String rawPattern, TargetParsingException e) {
     String errorMessage = e.getMessage();
     eventHandler.handle(Event.error("Skipping '" + rawPattern + "': " + errorMessage));
     if (handlerIsParseFailureListener) {
       ParseFailureListener parseListener = (ParseFailureListener) eventHandler;
-      parseListener.parsingError(rawPattern,  errorMessage);
+      parseListener.parsingError(rawPattern, errorMessage);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsValue.java
index 88f034c..918b31f 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsValue.java
@@ -37,8 +37,7 @@
   }
 
   @ThreadSafe
-  public static SkyKey key(ImmutableList<String> patterns, FilteringPolicy policy,
-      String offset) {
+  public static SkyKey key(ImmutableList<String> patterns, FilteringPolicy policy, String offset) {
     return new SkyKey(SkyFunctions.PREPARE_DEPS_OF_PATTERNS,
         new TargetPatternSequence(patterns, policy, offset));
   }
@@ -50,8 +49,8 @@
     private final FilteringPolicy policy;
     private final String offset;
 
-    public TargetPatternSequence(ImmutableList<String> patterns,
-        FilteringPolicy policy, String offset) {
+    private TargetPatternSequence(ImmutableList<String> patterns, FilteringPolicy policy,
+        String offset) {
       this.patterns = patterns;
       this.policy = policy;
       this.offset = offset;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeTargetPatternEvaluator.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeTargetPatternEvaluator.java
index 979f322..d166126 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeTargetPatternEvaluator.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeTargetPatternEvaluator.java
@@ -30,6 +30,7 @@
 import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
 import com.google.devtools.build.lib.pkgcache.ParseFailureListener;
 import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator;
+import com.google.devtools.build.lib.skyframe.TargetPatternValue.TargetPatternSkyKeyOrException;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.skyframe.ErrorInfo;
@@ -99,8 +100,27 @@
   ResolvedTargets<Target> parseTargetPatternList(String offset, EventHandler eventHandler,
       List<String> targetPatterns, FilteringPolicy policy, boolean keepGoing)
       throws InterruptedException, TargetParsingException {
-    return parseTargetPatternKeys(TargetPatternValue.keys(targetPatterns, policy, offset),
-       SkyframeExecutor.DEFAULT_THREAD_COUNT, keepGoing, eventHandler);
+    Iterable<TargetPatternSkyKeyOrException> keysMaybe =
+        TargetPatternValue.keys(targetPatterns, policy, offset);
+
+    ImmutableList.Builder<SkyKey> builder = ImmutableList.builder();
+    for (TargetPatternSkyKeyOrException skyKeyOrException : keysMaybe) {
+      try {
+        builder.add(skyKeyOrException.getSkyKey());
+      } catch (TargetParsingException e) {
+        if (!keepGoing) {
+          throw e;
+        }
+        String pattern = skyKeyOrException.getOriginalPattern();
+        eventHandler.handle(Event.error("Skipping '" + pattern + "': " + e.getMessage()));
+        if (eventHandler instanceof ParseFailureListener) {
+          ((ParseFailureListener) eventHandler).parsingError(pattern, e.getMessage());
+        }
+      }
+    }
+    ImmutableList<SkyKey> skyKeys = builder.build();
+    return parseTargetPatternKeys(skyKeys, SkyframeExecutor.DEFAULT_THREAD_COUNT, keepGoing,
+        eventHandler);
   }
 
   private static Map<PackageIdentifier, Package> getPackages(
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 97aef98..d805a91 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
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.cmdline.TargetPattern;
@@ -47,16 +48,16 @@
       InterruptedException {
     TargetPatternValue.TargetPatternKey patternKey =
         ((TargetPatternValue.TargetPatternKey) key.argument());
-    TargetPattern.Parser parser = new TargetPattern.Parser(patternKey.getOffset());
-    ResolvedTargets<Target> resolvedTargets = null;
+    ResolvedTargets<Target> resolvedTargets;
     try {
       EnvironmentBackedRecursivePackageProvider provider =
           new EnvironmentBackedRecursivePackageProvider(env);
       RecursivePackageProviderBackedTargetPatternResolver resolver =
           new RecursivePackageProviderBackedTargetPatternResolver(provider, env.getListener(),
               patternKey.getPolicy(), pkgPath.get());
-      TargetPattern resolvedPattern = parser.parse(patternKey.getPattern());
-      resolvedTargets = resolvedPattern.eval(resolver);
+      TargetPattern parsedPattern = patternKey.getParsedPattern();
+      ImmutableSet<String> excludedSubdirectories = patternKey.getExcludedSubdirectories();
+      resolvedTargets = parsedPattern.eval(resolver, excludedSubdirectories);
     } catch (TargetParsingException e) {
       throw new TargetPatternFunctionException(e);
     } catch (MissingDepException e) {
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 1463140..1f665e0 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
@@ -14,9 +14,13 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
-import com.google.common.collect.Lists;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets.Builder;
+import com.google.devtools.build.lib.cmdline.TargetParsingException;
+import com.google.devtools.build.lib.cmdline.TargetPattern;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.pkgcache.FilteringPolicies;
@@ -31,7 +35,6 @@
 import java.io.ObjectOutputStream;
 import java.io.Serializable;
 import java.util.ArrayList;
-import java.util.Collection;
 import java.util.List;
 import java.util.Objects;
 
@@ -93,42 +96,54 @@
   }
 
   /**
-   * Create a target pattern value key.
+   * Create a target pattern {@link SkyKey}. Throws {@link TargetParsingException} if the provided
+   * {@code pattern} cannot be parsed.
    *
-   * @param pattern The pattern, eg "-foo/biz...". If the first character is "-", the pattern
-   *                is treated as a negative pattern.
+   * @param pattern The pattern, eg "-foo/biz...". If the first character is "-", the pattern is
+   *     treated as a negative pattern.
    * @param policy The filtering policy, eg "only return test targets"
    * @param offset The offset to apply to relative target patterns.
    */
   @ThreadSafe
-  public static SkyKey key(String pattern,
-                            FilteringPolicy policy,
-                            String offset) {
-    return new SkyKey(SkyFunctions.TARGET_PATTERN,
-        pattern.startsWith("-")
-        // Don't apply filters to negative patterns.
-        ? new TargetPatternKey(pattern.substring(1), FilteringPolicies.NO_FILTER, true, offset)
-        : new TargetPatternKey(pattern, policy, false, offset));
+  public static SkyKey key(String pattern, FilteringPolicy policy, String offset)
+      throws TargetParsingException {
+    return Iterables.getOnlyElement(keys(ImmutableList.of(pattern), policy, offset)).getSkyKey();
   }
 
   /**
-   * Like above, but accepts a collection of target patterns for the same filtering policy.
+   * Returns an iterable of {@link TargetPatternSkyKeyOrException}, with {@link TargetPatternKey}
+   * arguments, in the same order as the list of patterns provided as input. If a provided pattern
+   * fails to parse, the element in the returned iterable corresponding to it will throw when its
+   * {@link TargetPatternSkyKeyOrException#getSkyKey} method is called.
    *
-   * @param patterns The collection of patterns, eg "-foo/biz...". If the first character is "-",
-   *                 the pattern is treated as a negative pattern.
+   * @param patterns The list of patterns, eg "-foo/biz...". If a pattern's first character is "-",
+   *     it is treated as a negative pattern.
    * @param policy The filtering policy, eg "only return test targets"
    * @param offset The offset to apply to relative target patterns.
    */
   @ThreadSafe
-  public static Iterable<SkyKey> keys(Collection<String> patterns,
-                                       FilteringPolicy policy,
-                                       String offset) {
-    List<SkyKey> keys = Lists.newArrayListWithCapacity(patterns.size());
+  public static Iterable<TargetPatternSkyKeyOrException> keys(List<String> patterns,
+      FilteringPolicy policy, String offset) {
+    TargetPattern.Parser parser = new TargetPattern.Parser(offset);
+    ImmutableList.Builder<TargetPatternSkyKeyOrException> builder = ImmutableList.builder();
     for (String pattern : patterns) {
-      keys.add(key(pattern, policy, offset));
+      boolean positive = !pattern.startsWith("-");
+      String absoluteValueOfPattern = positive ? pattern : pattern.substring(1);
+      TargetPattern targetPattern;
+      try {
+        targetPattern = parser.parse(absoluteValueOfPattern);
+      } catch (TargetParsingException e) {
+        builder.add(new TargetPatternSkyKeyException(e, absoluteValueOfPattern));
+        continue;
+      }
+      TargetPatternKey targetPatternKey = new TargetPatternKey(targetPattern,
+          positive ? policy : FilteringPolicies.NO_FILTER, /*isNegative=*/!positive, offset,
+          ImmutableSet.<String>of());
+      SkyKey skyKey = new SkyKey(SkyFunctions.TARGET_PATTERN, targetPatternKey);
+      builder.add(new TargetPatternSkyKeyValue(skyKey));
     }
-     return keys;
-   }
+    return builder.build();
+  }
 
   public ResolvedTargets<Label> getTargets() {
     return targets;
@@ -136,26 +151,33 @@
 
   /**
    * A TargetPatternKey is a tuple of pattern (eg, "foo/..."), filtering policy, a relative pattern
-   * offset, and whether it is a positive or negative match.
+   * offset, whether it is a positive or negative match, and a set of excluded subdirectories.
    */
   @ThreadSafe
   public static class TargetPatternKey implements Serializable {
-    private final String pattern;
+
+    private final TargetPattern parsedPattern;
     private final FilteringPolicy policy;
     private final boolean isNegative;
 
     private final String offset;
+    private final ImmutableSet<String> excludedSubdirectories;
 
-    public TargetPatternKey(String pattern, FilteringPolicy policy,
-        boolean isNegative, String offset) {
-      this.pattern = Preconditions.checkNotNull(pattern);
+    public TargetPatternKey(TargetPattern parsedPattern, FilteringPolicy policy,
+        boolean isNegative, String offset, ImmutableSet<String> excludedSubdirectories) {
+      this.parsedPattern = Preconditions.checkNotNull(parsedPattern);
       this.policy = Preconditions.checkNotNull(policy);
       this.isNegative = isNegative;
       this.offset = offset;
+      this.excludedSubdirectories = Preconditions.checkNotNull(excludedSubdirectories);
     }
 
     public String getPattern() {
-      return pattern;
+      return parsedPattern.getOriginalPattern();
+    }
+
+    public TargetPattern getParsedPattern() {
+      return parsedPattern;
     }
 
     public boolean isNegative() {
@@ -170,14 +192,19 @@
       return offset;
     }
 
+    public ImmutableSet<String> getExcludedSubdirectories() {
+      return excludedSubdirectories;
+    }
+
     @Override
     public String toString() {
-      return (isNegative ? "-" : "") + pattern;
+      return (isNegative ? "-" : "") + parsedPattern.getOriginalPattern();
     }
 
     @Override
     public int hashCode() {
-      return Objects.hash(pattern, isNegative, policy, offset);
+      return Objects.hash(parsedPattern, isNegative, policy, offset,
+          excludedSubdirectories);
     }
 
     @Override
@@ -187,8 +214,69 @@
       }
       TargetPatternKey other = (TargetPatternKey) obj;
 
-      return other.isNegative == this.isNegative && other.pattern.equals(this.pattern) &&
-          other.offset.equals(this.offset) && other.policy.equals(this.policy);
+      return other.isNegative == this.isNegative && other.parsedPattern.equals(this.parsedPattern)
+          && other.offset.equals(this.offset) && other.policy.equals(this.policy)
+          && other.excludedSubdirectories.equals(this.excludedSubdirectories);
+    }
+  }
+
+  /**
+   * Wrapper for a target pattern {@link SkyKey} or the {@link TargetParsingException} thrown when
+   * trying to compute it.
+   */
+  public interface TargetPatternSkyKeyOrException {
+
+    /**
+     * Returns the stored {@link SkyKey} or throws {@link TargetParsingException} if one was thrown
+     * when computing the key.
+     */
+    SkyKey getSkyKey() throws TargetParsingException;
+
+    /**
+     * Returns the pattern that resulted in the stored {@link SkyKey} or {@link
+     * TargetParsingException}.
+     */
+    String getOriginalPattern();
+  }
+
+  private static final class TargetPatternSkyKeyValue implements TargetPatternSkyKeyOrException {
+
+    private final SkyKey value;
+
+    private TargetPatternSkyKeyValue(SkyKey value) {
+      this.value = value;
+    }
+
+    @Override
+    public SkyKey getSkyKey() throws TargetParsingException {
+      return value;
+    }
+
+    @Override
+    public String getOriginalPattern() {
+      return ((TargetPatternKey) value.argument()).getPattern();
+    }
+  }
+
+  private static final class TargetPatternSkyKeyException implements
+      TargetPatternSkyKeyOrException {
+
+    private final TargetParsingException exception;
+    private final String originalPattern;
+
+    private TargetPatternSkyKeyException(TargetParsingException exception, String originalPattern) {
+      this.exception = exception;
+      this.originalPattern = originalPattern;
+    }
+
+    @Override
+    public SkyKey getSkyKey() throws TargetParsingException {
+      throw exception;
+    }
+
+    @Override
+    public String getOriginalPattern() {
+      return originalPattern;
     }
   }
 }