diff --git a/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java b/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java
index 2c05f0f..416d92e 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/CommandHelper.java
@@ -18,7 +18,6 @@
 import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -86,12 +85,12 @@
   private final ImmutableList<Artifact> resolvedTools;
 
   /**
-   * Creates an {@link CommandHelper}.
+   * Creates a {@link CommandHelper}.
    *
-   * @param tools - Resolves set of tools into set of executable binaries. Populates manifests,
-   *        remoteRunfiles and label map where required.
-   * @param labelMap - Adds files to set of known files of label. Used for resolving $(location)
-   *        variables.
+   * @param tools resolves set of tools into set of executable binaries. Populates manifests,
+   *     remoteRunfiles and label map where required.
+   * @param labelMap adds files to set of known files of label. Used for resolving $(location)
+   *     variables.
    */
   public CommandHelper(RuleContext ruleContext,
       Iterable<FilesToRunProvider> tools,
@@ -195,76 +194,22 @@
   }
 
   private static Pair<List<String>, Artifact> buildCommandLineMaybeWithScriptFile(
-      RuleContext ruleContext, String command, String scriptPostFix) {
+      RuleContext ruleContext, String command, String scriptPostFix, PathFragment shellPath) {
     List<String> argv;
     Artifact scriptFileArtifact = null;
     if (command.length() <= maxCommandLength) {
-      argv = buildCommandLineSimpleArgv(ruleContext, command);
+      argv = buildCommandLineSimpleArgv(command, shellPath);
     } else {
       // Use script file.
       scriptFileArtifact = buildCommandLineArtifact(ruleContext, command, scriptPostFix);
-      argv = buildCommandLineArgvWithArtifact(ruleContext, scriptFileArtifact);
+      argv = buildCommandLineArgvWithArtifact(scriptFileArtifact, shellPath);
     }
     return Pair.of(argv, scriptFileArtifact);
-
   }
 
-  /**
-   * Builds the set of command-line arguments. Creates a bash script if the
-   * command line is longer than the allowed maximum {@link
-   * #maxCommandLength}. Fixes up the input artifact list with the
-   * created bash script when required.
-   * TODO(bazel-team): do away with the side effect on inputs (ugh).
-   */
-  public static List<String> buildCommandLine(RuleContext ruleContext,
-      String command, NestedSetBuilder<Artifact> inputs, String scriptPostFix) {
-    Pair<List<String>, Artifact> argvAndScriptFile =
-        buildCommandLineMaybeWithScriptFile(ruleContext, command, scriptPostFix);
-    if (argvAndScriptFile.second != null) {
-      inputs.add(argvAndScriptFile.second);
-    }
-    return argvAndScriptFile.first;
-  }
-
-  /**
-   * Builds the set of command-line arguments. Creates a bash script if the
-   * command line is longer than the allowed maximum {@link
-   * #maxCommandLength}. Fixes up the input artifact list with the
-   * created bash script when required.
-   * TODO(bazel-team): do away with the side effect on inputs (ugh).
-   */
-  public static List<String> buildCommandLine(RuleContext ruleContext,
-      String command, List<Artifact> inputs, String scriptPostFix) {
-    Pair<List<String>, Artifact> argvAndScriptFile =
-        buildCommandLineMaybeWithScriptFile(ruleContext, command, scriptPostFix);
-    if (argvAndScriptFile.second != null) {
-      inputs.add(argvAndScriptFile.second);
-    }
-    return argvAndScriptFile.first;
-  }
-
-  /**
-   * Builds the set of command-line arguments. Creates a bash script if the
-   * command line is longer than the allowed maximum {@link
-   * #maxCommandLength}. Fixes up the input artifact list with the
-   * created bash script when required.
-   * TODO(bazel-team): do away with the side effect on inputs (ugh).
-   */
-  public static List<String> buildCommandLine(RuleContext ruleContext,
-      String command, ImmutableSet.Builder<Artifact> inputs, String scriptPostFix) {
-    Pair<List<String>, Artifact> argvAndScriptFile =
-        buildCommandLineMaybeWithScriptFile(ruleContext, command, scriptPostFix);
-    if (argvAndScriptFile.second != null) {
-      inputs.add(argvAndScriptFile.second);
-    }
-    return argvAndScriptFile.first;
-  }
-
-  private static ImmutableList<String> buildCommandLineArgvWithArtifact(RuleContext ruleContext,
-      Artifact scriptFileArtifact) {
-    return ImmutableList.of(
-        ruleContext.getConfiguration().getShExecutable().getPathString(),
-        scriptFileArtifact.getExecPathString());
+  private static ImmutableList<String> buildCommandLineArgvWithArtifact(Artifact scriptFileArtifact,
+      PathFragment shellPath) {
+    return ImmutableList.of(shellPath.getPathString(), scriptFileArtifact.getExecPathString());
   }
 
   private static Artifact buildCommandLineArtifact(RuleContext ruleContext, String command,
@@ -276,32 +221,53 @@
     return scriptFileArtifact;
   }
 
-  private static ImmutableList<String> buildCommandLineSimpleArgv(RuleContext ruleContext,
-      String command) {
-    return ImmutableList.of(
-        ruleContext.getConfiguration().getShExecutable().getPathString(), "-c", command);
+  private static ImmutableList<String> buildCommandLineSimpleArgv(String command,
+      PathFragment shellPath) {
+    return ImmutableList.of(shellPath.getPathString(), "-c", command);
   }
 
   /**
    * Builds the set of command-line arguments. Creates a bash script if the
-   * command line is longer than the allowed maximum {@link
-   * #maxCommandLength}. Fixes up the input artifact list with the
-   * created bash script when required.
+   * command line is longer than the allowed maximum {@link #maxCommandLength}.
+   * Fixes up the input artifact list with the created bash script when required.
    */
   public List<String> buildCommandLine(
       String command, NestedSetBuilder<Artifact> inputs, String scriptPostFix) {
-    return buildCommandLine(ruleContext, command, inputs, scriptPostFix);
+    return buildCommandLine(command, inputs, scriptPostFix,
+        ruleContext.getConfiguration().getShExecutable());
+  }
+
+  /**
+   * Builds the set of command-line arguments using the specified shell path. Creates a bash script
+   * if the command line is longer than the allowed maximum {@link #maxCommandLength}.
+   * Fixes up the input artifact list with the created bash script when required.
+   *
+   * @param shellPath path to the shell that should invoke this command
+   */
+  public List<String> buildCommandLine(
+      String command, NestedSetBuilder<Artifact> inputs, String scriptPostFix,
+      PathFragment shellPath) {
+    Pair<List<String>, Artifact> argvAndScriptFile =
+        buildCommandLineMaybeWithScriptFile(ruleContext, command, scriptPostFix, shellPath);
+    if (argvAndScriptFile.second != null) {
+      inputs.add(argvAndScriptFile.second);
+    }
+    return argvAndScriptFile.first;
   }
 
   /**
    * Builds the set of command-line arguments. Creates a bash script if the
-   * command line is longer than the allowed maximum {@link
-   * #maxCommandLength}. Fixes up the input artifact list with the
-   * created bash script when required.
+   * command line is longer than the allowed maximum {@link #maxCommandLength}.
+   * Fixes up the input artifact list with the created bash script when required.
    */
   @SkylarkCallable(doc = "")
   public List<String> buildCommandLine(
       String command, List<Artifact> inputs, String scriptPostFix) {
-    return buildCommandLine(ruleContext, command, inputs, scriptPostFix);
+    Pair<List<String>, Artifact> argvAndScriptFile = buildCommandLineMaybeWithScriptFile(
+        ruleContext, command, scriptPostFix, ruleContext.getConfiguration().getShExecutable());
+    if (argvAndScriptFile.second != null) {
+      inputs.add(argvAndScriptFile.second);
+    }
+    return argvAndScriptFile.first;
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/extra/ExtraActionSpec.java b/src/main/java/com/google/devtools/build/lib/rules/extra/ExtraActionSpec.java
index 40a063e..38e4a4b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/extra/ExtraActionSpec.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/extra/ExtraActionSpec.java
@@ -21,9 +21,11 @@
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.CommandHelper;
+import com.google.devtools.build.lib.analysis.FilesToRunProvider;
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.TransitiveInfoProvider;
 import com.google.devtools.build.lib.analysis.actions.CommandLine;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.util.Fingerprint;
@@ -74,7 +76,7 @@
   public Collection<Artifact> addExtraAction(RuleContext owningRule,
       Action actionToShadow) {
     Collection<Artifact> extraActionOutputs = new LinkedHashSet<>();
-    ImmutableSet.Builder<Artifact> extraActionInputs = ImmutableSet.builder();
+    NestedSetBuilder<Artifact> extraActionInputs = NestedSetBuilder.stableOrder();
 
     ActionOwner owner = actionToShadow.getOwner();
     Label ownerLabel = owner.getLabel();
@@ -111,13 +113,17 @@
 
     Map<String, String> env = owningRule.getConfiguration().getDefaultShellEnvironment();
 
-    List<String> argv = CommandHelper.buildCommandLine(owningRule,
-        command, extraActionInputs, ".extra_action_script.sh");
+    CommandHelper commandHelper = new CommandHelper(owningRule,
+        ImmutableList.<FilesToRunProvider>of(),
+        ImmutableMap.<Label, Iterable<Artifact>>of());
+
+    List<String> argv = commandHelper.buildCommandLine(command, extraActionInputs,
+        ".extra_action_script.sh");
 
     String commandMessage = String.format("Executing extra_action %s on %s", label, ownerLabel);
     owningRule.registerAction(new ExtraAction(
         actionToShadow.getOwner(),
-        extraActionInputs.build(),
+        ImmutableSet.copyOf(extraActionInputs.build()),
         manifests,
         extraActionInfoFile,
         extraActionOutputs,