diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/BUILD b/src/main/java/com/google/devtools/build/lib/cmdline/BUILD
index e414ea00..9861a47 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/BUILD
@@ -23,7 +23,9 @@
     exports = [":cmdline-primitives"],
     deps = [
         ":LabelValidator",
+        ":batch_callback",
         ":cmdline-primitives",
+        ":query_exception_marker_interface",
         "//src/main/java/com/google/devtools/build/docgen/annot",
         "//src/main/java/com/google/devtools/build/lib/actions:commandline_item",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
@@ -72,6 +74,31 @@
     ],
 )
 
+java_library(
+    name = "parallel_visitor",
+    srcs = ["ParallelVisitor.java"],
+    deps = [
+        ":batch_callback",
+        ":query_exception_marker_interface",
+        "//src/main/java/com/google/devtools/build/lib/concurrent",
+        "//third_party:guava",
+    ],
+)
+
+java_library(
+    name = "batch_callback",
+    srcs = ["BatchCallback.java"],
+    deps = [
+        ":query_exception_marker_interface",
+        "//src/main/java/com/google/devtools/build/lib/concurrent:thread_safety",
+    ],
+)
+
+java_library(
+    name = "query_exception_marker_interface",
+    srcs = ["QueryExceptionMarkerInterface.java"],
+)
+
 # LabelValidator provides validation of Bazel build labels.
 # This is a public API.
 # TODO(adonovan): unsplit the lib.cmdline Java package by moving this logic to a subpackage.
diff --git a/src/main/java/com/google/devtools/build/lib/concurrent/BatchCallback.java b/src/main/java/com/google/devtools/build/lib/cmdline/BatchCallback.java
similarity index 71%
rename from src/main/java/com/google/devtools/build/lib/concurrent/BatchCallback.java
rename to src/main/java/com/google/devtools/build/lib/cmdline/BatchCallback.java
index 7fdf043..1144b02 100644
--- a/src/main/java/com/google/devtools/build/lib/concurrent/BatchCallback.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/BatchCallback.java
@@ -11,17 +11,17 @@
 // 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.concurrent;
+package com.google.devtools.build.lib.cmdline;
 
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 
 /**
- * Callback to be invoked when part of a result has been computed. Allows a client interested in
- * the result to process it as it is computed, for instance by streaming it, if it is too big to
- * fit in memory.
+ * Callback to be invoked when part of a result has been computed. Allows a client interested in the
+ * result to process it as it is computed, for instance by streaming it, if it is too big to fit in
+ * memory.
  */
 @ThreadSafe
-public interface BatchCallback<T, E extends Exception> {
+public interface BatchCallback<T, E extends Exception & QueryExceptionMarkerInterface> {
   /**
    * Called when part of a result has been computed.
    *
@@ -33,8 +33,12 @@
    */
   void process(Iterable<T> partialResult) throws E, InterruptedException;
 
-  /** {@link BatchCallback} that does precisely nothing. */
-  class NullCallback<T> implements BatchCallback<T, RuntimeException> {
+  /** {@link BatchCallback} that doesn't throw. */
+  interface SafeBatchCallback<T>
+      extends BatchCallback<T, QueryExceptionMarkerInterface.MarkerRuntimeException> {}
+
+  /** {@link SafeBatchCallback} that does precisely nothing. */
+  class NullCallback<T> implements SafeBatchCallback<T> {
     private static final NullCallback<Object> INSTANCE = new NullCallback<>();
 
     @Override
diff --git a/src/main/java/com/google/devtools/build/lib/concurrent/ParallelVisitor.java b/src/main/java/com/google/devtools/build/lib/cmdline/ParallelVisitor.java
similarity index 97%
rename from src/main/java/com/google/devtools/build/lib/concurrent/ParallelVisitor.java
rename to src/main/java/com/google/devtools/build/lib/cmdline/ParallelVisitor.java
index 64d2589..78ac151 100644
--- a/src/main/java/com/google/devtools/build/lib/concurrent/ParallelVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/ParallelVisitor.java
@@ -11,12 +11,15 @@
 // 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.concurrent;
+package com.google.devtools.build.lib.cmdline;
 
 import com.google.common.base.Preconditions;
 import com.google.common.base.Throwables;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
+import com.google.devtools.build.lib.concurrent.ErrorClassifier;
+import com.google.devtools.build.lib.concurrent.QuiescingExecutor;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import java.util.ArrayList;
 import java.util.Collection;
@@ -47,7 +50,7 @@
     VisitKeyT,
     OutputKeyT,
     OutputResultT,
-    ExceptionT extends Exception,
+    ExceptionT extends Exception & QueryExceptionMarkerInterface,
     CallbackT extends BatchCallback<OutputResultT, ExceptionT>> {
   protected final CallbackT callback;
   protected final Class<ExceptionT> exceptionClass;
@@ -142,7 +145,7 @@
       VisitKeyT,
       OutputKeyT,
       OutputResultT,
-      ExceptionT extends Exception,
+      ExceptionT extends Exception & QueryExceptionMarkerInterface,
       CallbackT extends BatchCallback<OutputResultT, ExceptionT>> {
     ParallelVisitor<InputT, VisitKeyT, OutputKeyT, OutputResultT, ExceptionT, CallbackT> create();
   }
@@ -166,12 +169,6 @@
   protected abstract Iterable<OutputResultT> outputKeysToOutputValues(
       Iterable<OutputKeyT> targetKeys) throws ExceptionT, InterruptedException;
 
-  /**
-   * Suitable exception type to use with {@link ParallelVisitor} when no checked exception is
-   * appropriate.
-   */
-  public static final class UnusedException extends RuntimeException {}
-
   /** An object to hold keys to visit and keys ready for processing. */
   protected final class Visit {
     private final Iterable<OutputKeyT> keysToUseForResult;
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/QueryExceptionMarkerInterface.java b/src/main/java/com/google/devtools/build/lib/cmdline/QueryExceptionMarkerInterface.java
new file mode 100644
index 0000000..c988f14
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/QueryExceptionMarkerInterface.java
@@ -0,0 +1,39 @@
+// Copyright 2021 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.cmdline;
+
+/**
+ * Marker interface indicating either a {@link
+ * com.google.devtools.build.lib.query2.engine.QueryException} or a {@link MarkerRuntimeException}.
+ * Used with a generic type to indicate that a method can optionally throw {@code QueryException} if
+ * the caller passes {@code QueryException.class} as a parameter to the method.
+ *
+ * <p>The only outside implementation of this interface is {@link
+ * com.google.devtools.build.lib.query2.engine.QueryException}. Do not implement or extend!
+ *
+ * <p>Used to narrow a generic type like {@code E extends Exception} to {@code E extends Exception &
+ * QueryExceptionMarkerInterface}, guaranteeing that the method will only throw {@link
+ * com.google.devtools.build.lib.query2.engine.QueryException} if any exception of type E is thrown.
+ * Because {@code E} will appear in the "throws" clause of a method, it must extend {@link
+ * Exception}.
+ */
+@SuppressWarnings("InterfaceWithOnlyStatics")
+public interface QueryExceptionMarkerInterface {
+  /**
+   * Marker class indicating that a given method does not throw QueryException. Pass {@code
+   * MarkerRuntimeException.class} as a parameter.
+   */
+  class MarkerRuntimeException extends RuntimeException implements QueryExceptionMarkerInterface {}
+}
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 492ebad..ba41c10 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
@@ -29,7 +29,6 @@
 import com.google.common.util.concurrent.ListeningExecutorService;
 import com.google.devtools.build.lib.cmdline.LabelValidator.BadLabelException;
 import com.google.devtools.build.lib.cmdline.LabelValidator.PackageAndTarget;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
 import com.google.devtools.build.lib.server.FailureDetails.TargetPatterns;
 import com.google.devtools.build.lib.server.FailureDetails.TargetPatterns.Code;
 import com.google.devtools.build.lib.supplier.InterruptibleSupplier;
@@ -146,7 +145,7 @@
    *     excludedSubdirectories} is nonempty and this pattern does not have type {@code
    *     Type.TARGETS_BELOW_DIRECTORY}.
    */
-  public abstract <T, E extends Exception> void eval(
+  public abstract <T, E extends Exception & QueryExceptionMarkerInterface> void eval(
       TargetPatternResolver<T> resolver,
       InterruptibleSupplier<ImmutableSet<PathFragment>> ignoredSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories,
@@ -162,12 +161,13 @@
    * ExecutionException}, the cause will be an instance of either {@link TargetParsingException} or
    * the given {@code exceptionClass}.
    */
-  public final <T, E extends Exception> ListenableFuture<Void> evalAdaptedForAsync(
-      TargetPatternResolver<T> resolver,
-      InterruptibleSupplier<ImmutableSet<PathFragment>> ignoredSubdirectories,
-      ImmutableSet<PathFragment> excludedSubdirectories,
-      BatchCallback<T, E> callback,
-      Class<E> exceptionClass) {
+  public final <T, E extends Exception & QueryExceptionMarkerInterface>
+      ListenableFuture<Void> evalAdaptedForAsync(
+          TargetPatternResolver<T> resolver,
+          InterruptibleSupplier<ImmutableSet<PathFragment>> ignoredSubdirectories,
+          ImmutableSet<PathFragment> excludedSubdirectories,
+          BatchCallback<T, E> callback,
+          Class<E> exceptionClass) {
     try {
       eval(resolver, ignoredSubdirectories, excludedSubdirectories, callback, exceptionClass);
       return Futures.immediateFuture(null);
@@ -191,7 +191,7 @@
    * ExecutionException}, the cause will be an instance of either {@link TargetParsingException} or
    * the given {@code exceptionClass}.
    */
-  public <T, E extends Exception> ListenableFuture<Void> evalAsync(
+  public <T, E extends Exception & QueryExceptionMarkerInterface> ListenableFuture<Void> evalAsync(
       TargetPatternResolver<T> resolver,
       InterruptibleSupplier<ImmutableSet<PathFragment>> ignoredSubdirectories,
       ImmutableSet<PathFragment> excludedSubdirectories,
@@ -258,7 +258,7 @@
     }
 
     @Override
-    public <T, E extends Exception> void eval(
+    public <T, E extends Exception & QueryExceptionMarkerInterface> void eval(
         TargetPatternResolver<T> resolver,
         InterruptibleSupplier<ImmutableSet<PathFragment>> ignoredSubdirectories,
         ImmutableSet<PathFragment> excludedSubdirectories,
@@ -320,7 +320,7 @@
     }
 
     @Override
-    public <T, E extends Exception> void eval(
+    public <T, E extends Exception & QueryExceptionMarkerInterface> void eval(
         TargetPatternResolver<T> resolver,
         InterruptibleSupplier<ImmutableSet<PathFragment>> ignoredSubdirectories,
         ImmutableSet<PathFragment> excludedSubdirectories,
@@ -418,7 +418,7 @@
     }
 
     @Override
-    public <T, E extends Exception> void eval(
+    public <T, E extends Exception & QueryExceptionMarkerInterface> void eval(
         TargetPatternResolver<T> resolver,
         InterruptibleSupplier<ImmutableSet<PathFragment>> ignoredSubdirectories,
         ImmutableSet<PathFragment> excludedSubdirectories,
@@ -544,7 +544,7 @@
     }
 
     @Override
-    public <T, E extends Exception> void eval(
+    public <T, E extends Exception & QueryExceptionMarkerInterface> void eval(
         TargetPatternResolver<T> resolver,
         InterruptibleSupplier<ImmutableSet<PathFragment>> ignoredSubdirectories,
         ImmutableSet<PathFragment> excludedSubdirectories,
@@ -573,13 +573,14 @@
     }
 
     @Override
-    public <T, E extends Exception> ListenableFuture<Void> evalAsync(
-        TargetPatternResolver<T> resolver,
-        InterruptibleSupplier<ImmutableSet<PathFragment>> ignoredSubdirectories,
-        ImmutableSet<PathFragment> excludedSubdirectories,
-        BatchCallback<T, E> callback,
-        Class<E> exceptionClass,
-        ListeningExecutorService executor) {
+    public <T, E extends Exception & QueryExceptionMarkerInterface>
+        ListenableFuture<Void> evalAsync(
+            TargetPatternResolver<T> resolver,
+            InterruptibleSupplier<ImmutableSet<PathFragment>> ignoredSubdirectories,
+            ImmutableSet<PathFragment> excludedSubdirectories,
+            BatchCallback<T, E> callback,
+            Class<E> exceptionClass,
+            ListeningExecutorService executor) {
       Preconditions.checkState(
           !excludedSubdirectories.contains(directory.getPackageFragment()),
           "Fully excluded target pattern %s should have already been filtered out (%s)",
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 639f6b3..f1c81df 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
@@ -14,11 +14,13 @@
 
 package com.google.devtools.build.lib.cmdline;
 
+import static com.google.common.util.concurrent.Futures.immediateCancelledFuture;
+import static com.google.common.util.concurrent.Futures.immediateFailedFuture;
+import static com.google.common.util.concurrent.Futures.immediateVoidFuture;
+
 import com.google.common.collect.ImmutableSet;
-import com.google.common.util.concurrent.Futures;
 import com.google.common.util.concurrent.ListenableFuture;
 import com.google.common.util.concurrent.ListeningExecutorService;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.Collection;
 
@@ -88,32 +90,34 @@
    * @param exceptionClass The class type of the parameterized exception.
    * @throws TargetParsingException under implementation-specific failure conditions
    */
-  public abstract <E extends Exception> void findTargetsBeneathDirectory(
-      RepositoryName repository,
-      String originalPattern,
-      String directory,
-      boolean rulesOnly,
-      ImmutableSet<PathFragment> forbiddenSubdirectories,
-      ImmutableSet<PathFragment> excludedSubdirectories,
-      BatchCallback<T, E> callback,
-      Class<E> exceptionClass)
-      throws TargetParsingException, E, InterruptedException;
+  public abstract <E extends Exception & QueryExceptionMarkerInterface>
+      void findTargetsBeneathDirectory(
+          RepositoryName repository,
+          String originalPattern,
+          String directory,
+          boolean rulesOnly,
+          ImmutableSet<PathFragment> forbiddenSubdirectories,
+          ImmutableSet<PathFragment> excludedSubdirectories,
+          BatchCallback<T, E> callback,
+          Class<E> exceptionClass)
+          throws TargetParsingException, E, InterruptedException;
 
   /**
    * Async version of {@link #findTargetsBeneathDirectory}
    *
    * <p>Default implementation is synchronous.
    */
-  public <E extends Exception> ListenableFuture<Void> findTargetsBeneathDirectoryAsync(
-      RepositoryName repository,
-      String originalPattern,
-      String directory,
-      boolean rulesOnly,
-      ImmutableSet<PathFragment> forbiddenSubdirectories,
-      ImmutableSet<PathFragment> excludedSubdirectories,
-      BatchCallback<T, E> callback,
-      Class<E> exceptionClass,
-      ListeningExecutorService executor) {
+  public <E extends Exception & QueryExceptionMarkerInterface>
+      ListenableFuture<Void> findTargetsBeneathDirectoryAsync(
+          RepositoryName repository,
+          String originalPattern,
+          String directory,
+          boolean rulesOnly,
+          ImmutableSet<PathFragment> forbiddenSubdirectories,
+          ImmutableSet<PathFragment> excludedSubdirectories,
+          BatchCallback<T, E> callback,
+          Class<E> exceptionClass,
+          ListeningExecutorService executor) {
       try {
       findTargetsBeneathDirectory(
           repository,
@@ -124,14 +128,14 @@
           excludedSubdirectories,
           callback,
           exceptionClass);
-        return Futures.immediateFuture(null);
+      return immediateVoidFuture();
       } catch (TargetParsingException e) {
-        return Futures.immediateFailedFuture(e);
+      return immediateFailedFuture(e);
       } catch (InterruptedException e) {
-        return Futures.immediateCancelledFuture();
+      return immediateCancelledFuture();
       } catch (Exception e) {
         if (exceptionClass.isInstance(e)) {
-          return Futures.immediateFailedFuture(e);
+        return immediateFailedFuture(e);
         }
         throw new IllegalStateException(e);
       }
diff --git a/src/main/java/com/google/devtools/build/lib/concurrent/BUILD b/src/main/java/com/google/devtools/build/lib/concurrent/BUILD
index b370069..e5a8e3a 100644
--- a/src/main/java/com/google/devtools/build/lib/concurrent/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/concurrent/BUILD
@@ -18,3 +18,8 @@
         "//third_party:jsr305",
     ],
 )
+
+java_library(
+    name = "thread_safety",
+    srcs = ["ThreadSafety.java"],
+)
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/BUILD b/src/main/java/com/google/devtools/build/lib/pkgcache/BUILD
index cf2dee9..37f7e7e 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/BUILD
@@ -27,6 +27,7 @@
         "//src/main/java/com/google/devtools/build/lib/buildeventstream/proto:build_event_stream_java_proto",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
         "//src/main/java/com/google/devtools/build/lib/cmdline:LabelValidator",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:batch_callback",
         "//src/main/java/com/google/devtools/build/lib/collect/compacthashset",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/lib/events",
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
index 4df9df5..94de4cd 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/RecursivePackageProvider.java
@@ -14,11 +14,10 @@
 package com.google.devtools.build.lib.pkgcache;
 
 import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.cmdline.BatchCallback.SafeBatchCallback;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor.UnusedException;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
@@ -55,7 +54,7 @@
    *     SkyKey}s that are created during the traversal, instead filtered out later
    */
   void streamPackagesUnderDirectory(
-      BatchCallback<PackageIdentifier, UnusedException> results,
+      SafeBatchCallback<PackageIdentifier> results,
       ExtendedEventHandler eventHandler,
       RepositoryName repository,
       PathFragment directory,
@@ -121,7 +120,7 @@
 
     @Override
     public void streamPackagesUnderDirectory(
-        BatchCallback<PackageIdentifier, UnusedException> results,
+        SafeBatchCallback<PackageIdentifier> results,
         ExtendedEventHandler eventHandler,
         RepositoryName repository,
         PathFragment directory,
diff --git a/src/main/java/com/google/devtools/build/lib/query2/AbstractSkyKeyParallelVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/AbstractSkyKeyParallelVisitor.java
index 5138a82..8fba9b1 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/AbstractSkyKeyParallelVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/AbstractSkyKeyParallelVisitor.java
@@ -13,7 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.query2;
 
-import com.google.devtools.build.lib.concurrent.ParallelVisitor;
+import com.google.devtools.build.lib.cmdline.ParallelVisitor;
 import com.google.devtools.build.lib.query2.ParallelVisitorUtils.ParallelQueryVisitor;
 import com.google.devtools.build.lib.query2.engine.Callback;
 import com.google.devtools.build.lib.query2.engine.QueryException;
diff --git a/src/main/java/com/google/devtools/build/lib/query2/BUILD b/src/main/java/com/google/devtools/build/lib/query2/BUILD
index b6aa812..ceb4b39 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/query2/BUILD
@@ -55,6 +55,7 @@
         "//src/main/java/com/google/devtools/build/lib/buildeventstream/proto:build_event_stream_java_proto",
         "//src/main/java/com/google/devtools/build/lib/causes",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:parallel_visitor",
         "//src/main/java/com/google/devtools/build/lib/collect/compacthashset",
         "//src/main/java/com/google/devtools/build/lib/collect/nestedset",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
diff --git a/src/main/java/com/google/devtools/build/lib/query2/ParallelVisitorUtils.java b/src/main/java/com/google/devtools/build/lib/query2/ParallelVisitorUtils.java
index c007723..038232b 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/ParallelVisitorUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/ParallelVisitorUtils.java
@@ -14,9 +14,9 @@
 package com.google.devtools.build.lib.query2;
 
 import com.google.common.util.concurrent.ThreadFactoryBuilder;
+import com.google.devtools.build.lib.cmdline.ParallelVisitor;
+import com.google.devtools.build.lib.cmdline.ParallelVisitor.Factory;
 import com.google.devtools.build.lib.concurrent.BlockingStack;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor.Factory;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.query2.engine.Callback;
 import com.google.devtools.build.lib.query2.engine.QueryException;
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 c9247a8..b706e2a 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
@@ -40,6 +40,7 @@
 import com.google.common.util.concurrent.ThreadFactoryBuilder;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.ParallelVisitor.VisitTaskStatusCallback;
 import com.google.devtools.build.lib.cmdline.SignedTargetPattern;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.cmdline.TargetPattern;
@@ -47,7 +48,6 @@
 import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
 import com.google.devtools.build.lib.concurrent.BlockingStack;
 import com.google.devtools.build.lib.concurrent.MultisetSemaphore;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor.VisitTaskStatusCallback;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.events.DelegatingEventHandler;
 import com.google.devtools.build.lib.events.Event;
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/BUILD b/src/main/java/com/google/devtools/build/lib/query2/engine/BUILD
index ce3b371..c70b8e0 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/BUILD
@@ -13,6 +13,8 @@
     srcs = glob(["*.java"]),
     deps = [
         "//src/main/java/com/google/devtools/build/lib/cmdline",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:batch_callback",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:query_exception_marker_interface",
         "//src/main/java/com/google/devtools/build/lib/collect/compacthashset",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/lib/graph",
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/Callback.java b/src/main/java/com/google/devtools/build/lib/query2/engine/Callback.java
index cf4524f..0beb457 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/Callback.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/Callback.java
@@ -13,7 +13,7 @@
 // limitations under the License.
 package com.google.devtools.build.lib.query2.engine;
 
-import com.google.devtools.build.lib.concurrent.BatchCallback;
+import com.google.devtools.build.lib.cmdline.BatchCallback;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 
 /**
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryException.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryException.java
index 162c5f1..68ffbf0 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryException.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryException.java
@@ -14,13 +14,14 @@
 package com.google.devtools.build.lib.query2.engine;
 
 import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.cmdline.QueryExceptionMarkerInterface;
 import com.google.devtools.build.lib.server.FailureDetails.ActionQuery;
 import com.google.devtools.build.lib.server.FailureDetails.ConfigurableQuery;
 import com.google.devtools.build.lib.server.FailureDetails.FailureDetail;
 import com.google.devtools.build.lib.server.FailureDetails.Query;
 
 /** Exception indicating a failure in Blaze query, aquery, or cquery. */
-public class QueryException extends Exception {
+public class QueryException extends Exception implements QueryExceptionMarkerInterface {
 
   /** Returns a better error message for the query. */
   static String describeFailedQuery(QueryException e, QueryExpression toplevel) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/BUILD b/src/main/java/com/google/devtools/build/lib/skyframe/BUILD
index 30cc36f..325bf53 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/BUILD
@@ -286,6 +286,8 @@
         "//src/main/java/com/google/devtools/build/lib/causes",
         "//src/main/java/com/google/devtools/build/lib/clock",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:batch_callback",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:query_exception_marker_interface",
         "//src/main/java/com/google/devtools/build/lib/collect/compacthashset",
         "//src/main/java/com/google/devtools/build/lib/collect/nestedset",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
@@ -1502,6 +1504,7 @@
         ":package_value",
         ":root_package_extractor",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:batch_callback",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/lib/events",
         "//src/main/java/com/google/devtools/build/lib/io:inconsistent_filesystem_exception",
@@ -1685,6 +1688,7 @@
     ],
     deps = [
         "//src/main/java/com/google/devtools/build/lib/cmdline",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:batch_callback",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//third_party:guava",
         "//third_party:jsr305",
@@ -2096,6 +2100,8 @@
     deps = [
         ":package_identifier_batching_callback",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:batch_callback",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:query_exception_marker_interface",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/lib/events",
         "//src/main/java/com/google/devtools/build/lib/packages",
@@ -2177,7 +2183,7 @@
         ":recursive_pkg_value",
         ":root_package_extractor",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
-        "//src/main/java/com/google/devtools/build/lib/concurrent",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:batch_callback",
         "//src/main/java/com/google/devtools/build/lib/events",
         "//src/main/java/com/google/devtools/build/lib/query2/engine",
         "//src/main/java/com/google/devtools/build/lib/vfs",
@@ -2225,7 +2231,7 @@
     srcs = ["RootPackageExtractor.java"],
     deps = [
         "//src/main/java/com/google/devtools/build/lib/cmdline",
-        "//src/main/java/com/google/devtools/build/lib/concurrent",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:batch_callback",
         "//src/main/java/com/google/devtools/build/lib/events",
         "//src/main/java/com/google/devtools/build/lib/query2/engine",
         "//src/main/java/com/google/devtools/build/lib/vfs",
@@ -2656,7 +2662,9 @@
         ":recursive_package_provider_backed_target_pattern_resolver",
         ":root_package_extractor",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
-        "//src/main/java/com/google/devtools/build/lib/concurrent",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:batch_callback",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:parallel_visitor",
+        "//src/main/java/com/google/devtools/build/lib/cmdline:query_exception_marker_interface",
         "//src/main/java/com/google/devtools/build/lib/events",
         "//src/main/java/com/google/devtools/build/lib/vfs",
         "//src/main/java/com/google/devtools/build/lib/vfs:pathfragment",
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java
index 9c24dfb..cd3dcd3 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/EnvironmentBackedRecursivePackageProvider.java
@@ -18,10 +18,9 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.cmdline.BatchCallback.SafeBatchCallback;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor.UnusedException;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.io.InconsistentFilesystemException;
@@ -142,7 +141,7 @@
 
   @Override
   public void streamPackagesUnderDirectory(
-      BatchCallback<PackageIdentifier, UnusedException> results,
+      SafeBatchCallback<PackageIdentifier> results,
       ExtendedEventHandler eventHandler,
       RepositoryName repository,
       PathFragment directory,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
index fec12ce..0f9fdc1 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
@@ -22,12 +22,11 @@
 import com.google.common.collect.Sets;
 import com.google.common.collect.Sets.SetView;
 import com.google.common.flogger.GoogleLogger;
+import com.google.devtools.build.lib.cmdline.BatchCallback.SafeBatchCallback;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.cmdline.TargetPattern;
 import com.google.devtools.build.lib.cmdline.TargetPattern.TargetsBelowDirectory;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor.UnusedException;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
@@ -59,8 +58,8 @@
    * Helper interface for clients of GraphBackedRecursivePackageProvider to indicate what universe
    * packages should be resolved in.
    *
-   * <p>Client can either specify a fixed set of target patterns (using {@link #of()}), or specify
-   * that all targets are valid (using {@link #all()}).
+   * <p>Client can either specify a fixed set of target patterns (using {@link #of}), or specify
+   * that all targets are valid (using {@link #all}).
    */
   public interface UniverseTargetPattern {
     ImmutableList<TargetPattern> patterns();
@@ -240,7 +239,7 @@
 
   @Override
   public void streamPackagesUnderDirectory(
-      BatchCallback<PackageIdentifier, UnusedException> results,
+      SafeBatchCallback<PackageIdentifier> results,
       ExtendedEventHandler eventHandler,
       RepositoryName repository,
       PathFragment directory,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageIdentifierBatchingCallback.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageIdentifierBatchingCallback.java
index daaac76..2bf7e9f1 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageIdentifierBatchingCallback.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageIdentifierBatchingCallback.java
@@ -13,9 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.lib.skyframe;
 
+import com.google.devtools.build.lib.cmdline.BatchCallback.SafeBatchCallback;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor.UnusedException;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 
 /**
@@ -28,12 +27,12 @@
  */
 @ThreadSafe
 public interface PackageIdentifierBatchingCallback
-    extends BatchCallback<PackageIdentifier, UnusedException>, AutoCloseable {
+    extends SafeBatchCallback<PackageIdentifier>, AutoCloseable {
   void close() throws InterruptedException;
 
   /** Factory for {@link PackageIdentifierBatchingCallback}. */
   interface Factory {
     PackageIdentifierBatchingCallback create(
-        BatchCallback<PackageIdentifier, UnusedException> batchResults, int maxBatchSize);
+        SafeBatchCallback<PackageIdentifier> batchResults, int maxBatchSize);
   }
 }
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 b72f383..be7986d 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
@@ -16,15 +16,16 @@
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.cmdline.BatchCallback;
+import com.google.devtools.build.lib.cmdline.BatchCallback.NullCallback;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.QueryExceptionMarkerInterface;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.cmdline.TargetPattern;
 import com.google.devtools.build.lib.cmdline.TargetPatternResolver;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
-import com.google.devtools.build.lib.concurrent.BatchCallback.NullCallback;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
@@ -116,7 +117,7 @@
           () -> repositoryIgnoredPatterns,
           ImmutableSet.of(),
           NullCallback.instance(),
-          RuntimeException.class);
+          QueryExceptionMarkerInterface.MarkerRuntimeException.class);
     } catch (TargetParsingException e) {
       throw new PrepareDepsOfPatternFunctionException(e);
     } catch (MissingDepException e) {
@@ -249,7 +250,7 @@
     }
 
     @Override
-    public <E extends Exception> void findTargetsBeneathDirectory(
+    public <E extends Exception & QueryExceptionMarkerInterface> void findTargetsBeneathDirectory(
         RepositoryName repository,
         String originalPattern,
         String directory,
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 9e52de4..e9abf1b 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
@@ -24,15 +24,16 @@
 import com.google.common.util.concurrent.ListenableFuture;
 import com.google.common.util.concurrent.ListeningExecutorService;
 import com.google.common.util.concurrent.MoreExecutors;
+import com.google.devtools.build.lib.cmdline.BatchCallback;
+import com.google.devtools.build.lib.cmdline.BatchCallback.SafeBatchCallback;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.QueryExceptionMarkerInterface;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.cmdline.TargetPatternResolver;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
 import com.google.devtools.build.lib.concurrent.MultisetSemaphore;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor.UnusedException;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
@@ -178,7 +179,7 @@
   }
 
   @Override
-  public <E extends Exception> void findTargetsBeneathDirectory(
+  public <E extends Exception & QueryExceptionMarkerInterface> void findTargetsBeneathDirectory(
       final RepositoryName repository,
       final String originalPattern,
       String directory,
@@ -206,16 +207,17 @@
   }
 
   @Override
-  public <E extends Exception> ListenableFuture<Void> findTargetsBeneathDirectoryAsync(
-      RepositoryName repository,
-      String originalPattern,
-      String directory,
-      boolean rulesOnly,
-      ImmutableSet<PathFragment> forbiddenSubdirectories,
-      ImmutableSet<PathFragment> excludedSubdirectories,
-      BatchCallback<Target, E> callback,
-      Class<E> exceptionClass,
-      ListeningExecutorService executor) {
+  public <E extends Exception & QueryExceptionMarkerInterface>
+      ListenableFuture<Void> findTargetsBeneathDirectoryAsync(
+          RepositoryName repository,
+          String originalPattern,
+          String directory,
+          boolean rulesOnly,
+          ImmutableSet<PathFragment> forbiddenSubdirectories,
+          ImmutableSet<PathFragment> excludedSubdirectories,
+          BatchCallback<Target, E> callback,
+          Class<E> exceptionClass,
+          ListeningExecutorService executor) {
     return findTargetsBeneathDirectoryAsyncImpl(
         repository,
         originalPattern,
@@ -227,20 +229,21 @@
         executor);
   }
 
-  private <E extends Exception> ListenableFuture<Void> findTargetsBeneathDirectoryAsyncImpl(
-      RepositoryName repository,
-      String pattern,
-      String directory,
-      boolean rulesOnly,
-      ImmutableSet<PathFragment> forbiddenSubdirectories,
-      ImmutableSet<PathFragment> excludedSubdirectories,
-      BatchCallback<Target, E> callback,
-      ListeningExecutorService executor) {
+  private <E extends Exception & QueryExceptionMarkerInterface>
+      ListenableFuture<Void> findTargetsBeneathDirectoryAsyncImpl(
+          RepositoryName repository,
+          String pattern,
+          String directory,
+          boolean rulesOnly,
+          ImmutableSet<PathFragment> forbiddenSubdirectories,
+          ImmutableSet<PathFragment> excludedSubdirectories,
+          BatchCallback<Target, E> callback,
+          ListeningExecutorService executor) {
     FilteringPolicy actualPolicy =
         rulesOnly ? FilteringPolicies.and(FilteringPolicies.RULES_ONLY, policy) : policy;
 
     ArrayList<ListenableFuture<Void>> futures = new ArrayList<>();
-    BatchCallback<PackageIdentifier, UnusedException> getPackageTargetsCallback =
+    SafeBatchCallback<PackageIdentifier> getPackageTargetsCallback =
         (pkgIdBatch) ->
             futures.add(
                 executor.submit(
@@ -278,7 +281,8 @@
    * Task to get all matching targets in the given packages, filter them, and pass them to the
    * target batch callback.
    */
-  private class GetTargetsInPackagesTask<E extends Exception> implements Callable<Void> {
+  private class GetTargetsInPackagesTask<E extends Exception & QueryExceptionMarkerInterface>
+      implements Callable<Void> {
 
     private final Iterable<PackageIdentifier> packageIdentifiers;
     private final String originalPattern;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValueRootPackageExtractor.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValueRootPackageExtractor.java
index bc0e7b5..47b27ea 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValueRootPackageExtractor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePkgValueRootPackageExtractor.java
@@ -16,10 +16,9 @@
 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.BatchCallback.SafeBatchCallback;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor.UnusedException;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.query2.engine.QueryException;
 import com.google.devtools.build.lib.server.FailureDetails.Query.Code;
@@ -34,7 +33,7 @@
 
   @Override
   public void streamPackagesFromRoots(
-      BatchCallback<PackageIdentifier, UnusedException> results,
+      SafeBatchCallback<PackageIdentifier> results,
       WalkableGraph graph,
       List<Root> roots,
       ExtendedEventHandler eventHandler,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RootPackageExtractor.java b/src/main/java/com/google/devtools/build/lib/skyframe/RootPackageExtractor.java
index d77e938..758546a 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RootPackageExtractor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RootPackageExtractor.java
@@ -14,10 +14,9 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.cmdline.BatchCallback.SafeBatchCallback;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor.UnusedException;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.query2.engine.QueryException;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -46,7 +45,7 @@
    *     searched exhaustively
    */
   void streamPackagesFromRoots(
-      BatchCallback<PackageIdentifier, UnusedException> results,
+      SafeBatchCallback<PackageIdentifier> results,
       WalkableGraph graph,
       List<Root> roots,
       ExtendedEventHandler eventHandler,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SimplePackageIdentifierBatchingCallback.java b/src/main/java/com/google/devtools/build/lib/skyframe/SimplePackageIdentifierBatchingCallback.java
index 80ce116..fe93e68 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SimplePackageIdentifierBatchingCallback.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SimplePackageIdentifierBatchingCallback.java
@@ -15,8 +15,6 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor.UnusedException;
 import javax.annotation.concurrent.GuardedBy;
 
 /**
@@ -25,7 +23,7 @@
  * smaller than the others.
  */
 public class SimplePackageIdentifierBatchingCallback implements PackageIdentifierBatchingCallback {
-  private final BatchCallback<PackageIdentifier, UnusedException> batchResults;
+  private final SafeBatchCallback<PackageIdentifier> batchResults;
   private final int batchSize;
 
   @GuardedBy("this")
@@ -35,7 +33,7 @@
   private int bufferedPackageIds;
 
   public SimplePackageIdentifierBatchingCallback(
-      BatchCallback<PackageIdentifier, UnusedException> batchResults, int batchSize) {
+      SafeBatchCallback<PackageIdentifier> batchResults, int batchSize) {
     this.batchResults = batchResults;
     this.batchSize = batchSize;
     reset();
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 081dfd9..e6437fd 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
@@ -17,6 +17,7 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.cmdline.QueryExceptionMarkerInterface;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.SignedTargetPattern;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
@@ -265,7 +266,7 @@
                   partialResult instanceof Collection
                       ? (Collection<Target>) partialResult
                       : ImmutableSet.copyOf(partialResult)),
-          TargetParsingException.class);
+          QueryExceptionMarkerInterface.MarkerRuntimeException.class);
       return result.get();
     }
   }
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 4a3d93e..01bd462 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
@@ -15,12 +15,12 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.cmdline.BatchCallback.SafeBatchCallback;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.QueryExceptionMarkerInterface;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.cmdline.TargetPattern;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
 import com.google.devtools.build.lib.concurrent.MultisetSemaphore;
 import com.google.devtools.build.lib.packages.OutputFile;
 import com.google.devtools.build.lib.packages.Target;
@@ -66,30 +66,26 @@
               provider,
               env.getListener(),
               patternKey.getPolicy(),
-              MultisetSemaphore.<PackageIdentifier>unbounded(),
+              MultisetSemaphore.unbounded(),
               SimplePackageIdentifierBatchingCallback::new);
       ImmutableSet<PathFragment> excludedSubdirectories = patternKey.getExcludedSubdirectories();
       ResolvedTargets.Builder<Target> resolvedTargetsBuilder = ResolvedTargets.builder();
-      BatchCallback<Target, RuntimeException> callback =
-          new BatchCallback<Target, RuntimeException>() {
-            @Override
-            public void process(Iterable<Target> partialResult) {
-              for (Target target : partialResult) {
-                // TODO(b/156899726): This will go away as soon as we remove implicit outputs from
-                // cc_library completely. The only
-                // downside to doing this is that implicit outputs won't be listed when doing
-                // somepackage:* for the handful of cases still on the allowlist. This is only a
-                // google internal problem and the scale of it is acceptable in the short term
-                // while cleaning up the allowlist.
-                if (target instanceof OutputFile
-                    && ((OutputFile) target)
-                        .getGeneratingRule()
-                        .getRuleClass()
-                        .equals("cc_library")) {
-                  continue;
-                }
-                resolvedTargetsBuilder.add(target);
+      SafeBatchCallback<Target> callback =
+          partialResult -> {
+            for (Target target : partialResult) {
+              // TODO(b/156899726): This will go away as soon as we remove implicit outputs from
+              //  cc_library completely. The only downside to doing this is that implicit outputs
+              //  won't be listed when doing somepackage:* for the handful of cases still on the
+              //  allowlist. This is only a Google-internal problem and the scale of it is
+              //  acceptable in the short term while cleaning up the allowlist.
+              if (target instanceof OutputFile
+                  && ((OutputFile) target)
+                      .getGeneratingRule()
+                      .getRuleClass()
+                      .equals("cc_library")) {
+                continue;
               }
+              resolvedTargetsBuilder.add(target);
             }
           };
       parsedPattern.eval(
@@ -97,9 +93,7 @@
           () -> ignoredPatterns,
           excludedSubdirectories,
           callback,
-          // The exception type here has to match the one on the BatchCallback. Since the callback
-          // defined above never throws, the exact type here is not really relevant.
-          RuntimeException.class);
+          QueryExceptionMarkerInterface.MarkerRuntimeException.class);
       if (provider.encounteredPackageErrors()) {
         resolvedTargetsBuilder.setError();
       }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TraversalInfoRootPackageExtractor.java b/src/main/java/com/google/devtools/build/lib/skyframe/TraversalInfoRootPackageExtractor.java
index 85f5d05..978a382 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TraversalInfoRootPackageExtractor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TraversalInfoRootPackageExtractor.java
@@ -21,11 +21,11 @@
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.util.concurrent.ThreadFactoryBuilder;
+import com.google.devtools.build.lib.cmdline.BatchCallback.SafeBatchCallback;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.cmdline.ParallelVisitor;
+import com.google.devtools.build.lib.cmdline.QueryExceptionMarkerInterface;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
-import com.google.devtools.build.lib.concurrent.BatchCallback;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor;
-import com.google.devtools.build.lib.concurrent.ParallelVisitor.UnusedException;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -53,7 +53,7 @@
 
   @Override
   public void streamPackagesFromRoots(
-      BatchCallback<PackageIdentifier, UnusedException> results,
+      SafeBatchCallback<PackageIdentifier> results,
       WalkableGraph graph,
       List<Root> roots,
       ExtendedEventHandler eventHandler,
@@ -96,15 +96,15 @@
           TraversalInfo,
           TraversalInfo,
           PackageIdentifier,
-          UnusedException,
-          BatchCallback<PackageIdentifier, UnusedException>> {
+          QueryExceptionMarkerInterface.MarkerRuntimeException,
+          SafeBatchCallback<PackageIdentifier>> {
 
     private final ExtendedEventHandler eventHandler;
     private final RepositoryName repository;
     private final WalkableGraph graph;
 
     PackageCollectingParallelVisitor(
-        BatchCallback<PackageIdentifier, UnusedException> callback,
+        SafeBatchCallback<PackageIdentifier> callback,
         int visitBatchSize,
         int processResultsBatchSize,
         int minPendingTasks,
@@ -114,7 +114,7 @@
         WalkableGraph graph) {
       super(
           callback,
-          UnusedException.class,
+          QueryExceptionMarkerInterface.MarkerRuntimeException.class,
           visitBatchSize,
           processResultsBatchSize,
           minPendingTasks,