Improve CustomCommandLine.

Instead of having custom ArgvFragments for every combination of desired things, we make a combined "interpreter" of argvs. This saves memory and simplifies things as we do not have to allocate a strategy instance per call to args (instead pushing a single shared instance, followed by the args).

The generic interpreter does have a lot of branching compared to the bespoke implementations, but because the branch is always the same for long stretches the branch predictor should easily be able to handle it with minimal overhead (~1 cycle per branch IIRC).

This CL also elevates that we either want a NestedSet or an ImmutableCollection to the surface of the API, so consumers understand the cost when they call it with a non-immutable collection. Most of the changes in clients is due to this.

To cut down on CL churn, @Deprecated forwarding methods are added to CustomCommandLine. These will be removed in a separate CL using IDE inlining.

RELNOTES: None
PiperOrigin-RevId: 164725370

23 files changed, 610 insertions, 499 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/CustomCommandLine.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/CustomCommandLine.java
index b4ac7aa7d2..a2a7c9bd65 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/CustomCommandLine.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/CustomCommandLine.java
@@ -17,21 +17,22 @@ package com.google.devtools.build.lib.analysis.actions;
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Function;
 import com.google.common.base.Joiner;
+import com.google.common.base.Objects;
+import com.google.common.collect.ImmutableCollection;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableList.Builder;
 import com.google.common.collect.ImmutableMap;
-import com.google.common.collect.Iterables;
+import com.google.common.collect.Interner;
+import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.ArtifactExpander;
 import com.google.devtools.build.lib.actions.Artifact.TreeFileArtifact;
-import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.collect.CollectionUtils;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
+import com.google.devtools.build.lib.concurrent.BlazeInterners;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.ArrayList;
-import java.util.Iterator;
+import java.util.Collections;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -44,10 +45,269 @@ import javax.annotation.Nullable;
 @Immutable
 public final class CustomCommandLine extends CommandLine {
 
-  private abstract static class ArgvFragment {
+  private interface ArgvFragment {
+    /**
+     * Expands this fragment into the passed command line vector.
+     *
+     * @param arguments The command line's argument vector.
+     * @param argi The index of the next available argument.
+     * @param builder The command line builder to which we should add arguments.
+     * @return The index of the next argument, after the ArgvFragment has consumed its args.
+     *   If the ArgvFragment doesn't have any args, it should return {@code argi} unmodified.
+     */
+    int eval(List<Object> arguments, int argi, ImmutableList.Builder<String> builder);
+  }
+
+  /**
+   * Helper base class for an ArgvFragment that doesn't use the input argument vector.
+   *
+   * <p>This can be used for any ArgvFragments that self-contain all the necessary state.
+   */
+  private abstract static class StandardArgvFragment implements ArgvFragment {
+    @Override
+    public final int eval(List<Object> arguments, int argi, ImmutableList.Builder<String> builder) {
+      eval(builder);
+      return argi; // Doesn't consume any arguments, so return argi unmodified
+    }
+
     abstract void eval(ImmutableList.Builder<String> builder);
   }
 
+  // TODO(bazel-team): CustomArgv and CustomMultiArgv is  going to be difficult to expose
+  // in Skylark. Maybe we can get rid of them by refactoring JavaCompileAction. It also
+  // raises immutability / serialization issues.
+  /** Custom Java code producing a String argument. Usage of this class is discouraged. */
+  public abstract static class CustomArgv extends StandardArgvFragment {
+
+    @Override
+    void eval(ImmutableList.Builder<String> builder) {
+      builder.add(argv());
+    }
+
+    public abstract String argv();
+  }
+
+  /**
+   * Custom Java code producing a List of String arguments.
+   *
+   * <p>Usage of this class is discouraged. Please see {@link CustomArgv}.
+   */
+  public abstract static class CustomMultiArgv extends StandardArgvFragment {
+
+    @Override
+    void eval(ImmutableList.Builder<String> builder) {
+      builder.addAll(argv());
+    }
+
+    public abstract Iterable<String> argv();
+  }
+
+  /**
+   * An ArgvFragment that expands a collection of objects in a user-specified way.
+   *
+   * <p>To construct one, use {@link VectorArg#of} with your collection of objects,
+   * and configure the returned object depending on how you want the expansion to
+   * take place. Finally, pass it to {@link CustomCommandLine.Builder#add(VectorArg.Builder}.
+   */
+  public static final class VectorArg implements ArgvFragment {
+    private static Interner<VectorArg> interner = BlazeInterners.newStrongInterner();
+
+    private final boolean hasMapEach;
+    private final boolean hasFormatEach;
+    private final boolean hasBeforeEach;
+    private final boolean hasJoinWith;
+
+    private VectorArg(
+        boolean hasMapEach, boolean hasFormatEach, boolean hasBeforeEach, boolean hasJoinWith) {
+      this.hasMapEach = hasMapEach;
+      this.hasFormatEach = hasFormatEach;
+      this.hasBeforeEach = hasBeforeEach;
+      this.hasJoinWith = hasJoinWith;
+    }
+
+    private static void push(List<Object> arguments, Builder argv) {
+      VectorArg vectorArg =
+          new VectorArg(
+              argv.mapFn != null,
+              argv.formatEach != null,
+              argv.beforeEach != null,
+              argv.joinWith != null);
+      vectorArg = interner.intern(vectorArg);
+      arguments.add(vectorArg);
+      arguments.add(argv.values);
+      if (vectorArg.hasMapEach) {
+        arguments.add(argv.mapFn);
+      }
+      if (vectorArg.hasFormatEach) {
+        arguments.add(argv.formatEach);
+      }
+      if (vectorArg.hasBeforeEach) {
+        arguments.add(argv.beforeEach);
+      }
+      if (vectorArg.hasJoinWith) {
+        arguments.add(argv.joinWith);
+      }
+    }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public int eval(List<Object> arguments, int argi, ImmutableList.Builder<String> builder) {
+      Iterable<Object> values = (Iterable<Object>) arguments.get(argi++);
+      List<Object> mutatedValues = Lists.newArrayList(values);
+      int count = mutatedValues.size();
+      if (hasMapEach) {
+        Function<Object, Object> mapFn = (Function<Object, Object>) arguments.get(argi++);
+        for (int i = 0; i < count; ++i) {
+          mutatedValues.set(i, mapFn.apply(mutatedValues.get(i)));
+        }
+      }
+      for (int i = 0; i < count; ++i) {
+        mutatedValues.set(i, valueToString(mutatedValues.get(i)));
+      }
+      if (hasFormatEach) {
+        String formatStr = (String) arguments.get(argi++);
+        for (int i = 0; i < count; ++i) {
+          mutatedValues.set(i, String.format(formatStr, mutatedValues.get(i)));
+        }
+      }
+      if (hasBeforeEach) {
+        String beforeEach = (String) arguments.get(argi++);
+        for (int i = 0; i < count; ++i) {
+          builder.add(beforeEach);
+          builder.add((String) mutatedValues.get(i));
+        }
+      } else if (hasJoinWith) {
+        String joinWith = (String) arguments.get(argi++);
+        builder.add(Joiner.on(joinWith).join(mutatedValues));
+      } else {
+        for (int i = 0; i < count; ++i) {
+          builder.add((String) mutatedValues.get(i));
+        }
+      }
+      return argi;
+    }
+
+    public static Builder of(@Nullable ImmutableCollection<?> values) {
+      return new Builder(values);
+    }
+
+    public static Builder of(@Nullable NestedSet<?> values) {
+      return new Builder(values);
+    }
+
+    /** Builder for a VectorArg */
+    public static class Builder {
+      @Nullable private final Iterable<?> values;
+      private final boolean isEmpty;
+      private String formatEach;
+      private String beforeEach;
+      private Function<?, String> mapFn;
+      private String joinWith;
+
+      private Builder(@Nullable ImmutableCollection<?> values) {
+        this(values, values == null || values.isEmpty());
+      }
+
+      private Builder(@Nullable NestedSet<?> values) {
+        this(values, values == null || values.isEmpty());
+      }
+
+      private Builder(@Nullable Iterable<?> values, boolean isEmpty) {
+        this.values = values;
+        this.isEmpty = isEmpty;
+      }
+
+      /** Each argument is formatted via {@link String#format}. */
+      public Builder formatEach(String formatEach) {
+        Preconditions.checkNotNull(formatEach);
+        this.formatEach = formatEach;
+        return this;
+      }
+
+      /** Each argument is prepended by the beforeEach param. */
+      public Builder beforeEach(String beforeEach) {
+        Preconditions.checkNotNull(beforeEach);
+        this.beforeEach = beforeEach;
+        return this;
+      }
+
+      /** Each argument is mapped using the supplied map function */
+      public <T> Builder mapEach(Function<T, String> mapFn) {
+        Preconditions.checkNotNull(mapFn);
+        this.mapFn = mapFn;
+        return this;
+      }
+
+      /** Once all arguments have been evaluated, they are joined with this delimiter */
+      public Builder joinWith(String delimiter) {
+        Preconditions.checkNotNull(delimiter);
+        this.joinWith = delimiter;
+        return this;
+      }
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      if (this == o) {
+        return true;
+      }
+      if (o == null || getClass() != o.getClass()) {
+        return false;
+      }
+      VectorArg vectorArg = (VectorArg) o;
+      return hasMapEach == vectorArg.hasMapEach
+          && hasFormatEach == vectorArg.hasFormatEach
+          && hasBeforeEach == vectorArg.hasBeforeEach
+          && hasJoinWith == vectorArg.hasJoinWith;
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hashCode(hasMapEach, hasFormatEach, hasBeforeEach, hasJoinWith);
+    }
+  }
+
+  private static class FormatArg implements ArgvFragment {
+    private static final FormatArg INSTANCE = new FormatArg();
+
+    private static void push(List<Object> arguments, String formatStr, Object... args) {
+      arguments.add(INSTANCE);
+      arguments.add(args.length);
+      arguments.add(formatStr);
+      Collections.addAll(arguments, args);
+    }
+
+    @Override
+    public int eval(List<Object> arguments, int argi, ImmutableList.Builder<String> builder) {
+      int argCount = (Integer) arguments.get(argi++);
+      String formatStr = (String) arguments.get(argi++);
+      Object[] args = new Object[argCount];
+      for (int i = 0; i < argCount; ++i) {
+        args[i] = valueToString(arguments.get(argi++));
+      }
+      builder.add(String.format(formatStr, args));
+      return argi;
+    }
+  }
+
+  private static class PrefixArg implements ArgvFragment {
+    private static final PrefixArg INSTANCE = new PrefixArg();
+
+    private static void push(List<Object> arguments, String before, Object arg) {
+      arguments.add(INSTANCE);
+      arguments.add(before);
+      arguments.add(arg);
+    }
+
+    @Override
+    public int eval(List<Object> arguments, int argi, ImmutableList.Builder<String> builder) {
+      String before = (String) arguments.get(argi++);
+      Object arg = arguments.get(argi++);
+      builder.add(before + valueToString(arg));
+      return argi;
+    }
+  }
+
   /**
    * A command line argument for {@link TreeFileArtifact}.
    *
@@ -68,16 +328,15 @@ public final class CustomCommandLine extends CommandLine {
   }
 
   /**
-   * A command line argument that can expand enclosed TreeArtifacts into a list of child
-   * {@link TreeFileArtifact}s at execution time before argument evaluation.
+   * A command line argument that can expand enclosed TreeArtifacts into a list of child {@link
+   * TreeFileArtifact}s at execution time before argument evaluation.
    *
    * <p>The main difference between this class and {@link TreeFileArtifactArgvFragment} is that
    * {@link TreeFileArtifactArgvFragment} is used in {@link SpawnActionTemplate} to substitutes a
    * TreeArtifact with *one* of its child TreeFileArtifacts, while this class expands a TreeArtifact
    * into *all* of its child TreeFileArtifacts.
-   *
    */
-  private abstract static class TreeArtifactExpansionArgvFragment extends ArgvFragment {
+  private abstract static class TreeArtifactExpansionArgvFragment extends StandardArgvFragment {
     /**
      * Evaluates this argument fragment into an argument string and adds it into {@code builder}.
      * The enclosed TreeArtifact will be expanded using {@code artifactExpander}.
@@ -104,30 +363,6 @@ public final class CustomCommandLine extends CommandLine {
     }
   }
 
-  // It's better to avoid anonymous classes if we want to serialize command lines
-  private static final class JoinExecPathsArg extends ArgvFragment {
-
-    private final String arg;
-    private final String delimiter;
-    private final Iterable<Artifact> artifacts;
-
-    private JoinExecPathsArg(String arg, String delimiter, Iterable<Artifact> artifacts) {
-      this.arg = arg;
-      this.delimiter = delimiter;
-      this.artifacts = CollectionUtils.makeImmutable(artifacts);
-    }
-
-    @Override
-    void eval(ImmutableList.Builder<String> builder) {
-      Iterator<Artifact> it = artifacts.iterator();
-      if (!it.hasNext()) {
-        return;
-      }
-      builder.add(arg);
-      builder.add(Artifact.joinExecPaths(delimiter, artifacts));
-    }
-  }
-
   private static final class JoinExpandedTreeArtifactExecPathsArg
       extends TreeArtifactExpansionArgvFragment {
 
@@ -188,38 +423,6 @@ public final class CustomCommandLine extends CommandLine {
     }
   }
 
-  private static final class PathWithTemplateArg extends ArgvFragment {
-
-    private final String template;
-    private final PathFragment[] paths;
-
-    private PathWithTemplateArg(String template, PathFragment... paths) {
-      this.template = template;
-      this.paths = paths;
-    }
-
-    @Override
-    void eval(ImmutableList.Builder<String> builder) {
-      // PathFragment.toString() uses getPathString()
-      builder.add(String.format(template, (Object[]) paths));
-    }
-  }
-
-  private static final class ParamFileArgument extends ArgvFragment {
-    private final String paramFilePrefix;
-    private final PathFragment path;
-
-    private ParamFileArgument(String paramFilePrefix, PathFragment path) {
-      this.paramFilePrefix = paramFilePrefix;
-      this.path = path;
-    }
-
-    @Override
-    void eval(ImmutableList.Builder<String> builder) {
-      builder.add(paramFilePrefix + path);
-    }
-  }
-
   /**
    * An argument object that evaluates to a formatted string for {@link TreeFileArtifact} exec
    * paths, enclosing the associated string format template and {@link TreeFileArtifact}s.
@@ -238,202 +441,14 @@ public final class CustomCommandLine extends CommandLine {
     }
 
     @Override
-    ArgvFragment substituteTreeArtifact(Map<Artifact, TreeFileArtifact> substitutionMap) {
+    Object substituteTreeArtifact(Map<Artifact, TreeFileArtifact> substitutionMap) {
       Artifact treeFileArtifact = substitutionMap.get(placeHolderTreeArtifact);
       Preconditions.checkNotNull(treeFileArtifact, "Artifact to substitute: %s",
           placeHolderTreeArtifact);
-
-      return new PathWithTemplateArg(template, treeFileArtifact.getExecPath());
+      return String.format(template, treeFileArtifact.getExecPath());
     }
   }
 
-  // TODO(bazel-team): CustomArgv and CustomMultiArgv is  going to be difficult to expose
-  // in Skylark. Maybe we can get rid of them by refactoring JavaCompileAction. It also
-  // raises immutability / serialization issues.
-  /**
-   * Custom Java code producing a String argument. Usage of this class is discouraged.
-   */
-  public abstract static class CustomArgv extends ArgvFragment {
-
-    @Override
-    void eval(ImmutableList.Builder<String> builder) {
-      builder.add(argv());
-    }
-
-    public abstract String argv();
-  }
-
-  /**
-   * Custom Java code producing a List of String arguments. Usage of this class is discouraged.
-   */
-  public abstract static class CustomMultiArgv extends ArgvFragment {
-
-    @Override
-    void eval(ImmutableList.Builder<String> builder) {
-      builder.addAll(argv());
-    }
-
-    public abstract Iterable<String> argv();
-  }
-
-  private static final class JoinPathsArg extends ArgvFragment {
-
-    private final String delimiter;
-    private final Iterable<PathFragment> paths;
-
-    private JoinPathsArg(String delimiter, Iterable<PathFragment> paths) {
-      this.delimiter = delimiter;
-      this.paths = CollectionUtils.makeImmutable(paths);
-    }
-
-    @Override
-    void eval(ImmutableList.Builder<String> builder) {
-      builder.add(Joiner.on(delimiter).join(paths));
-    }
-  }
-
-  private static final class JoinStringsArg extends ArgvFragment {
-
-    private final String arg;
-    private final String delimiter;
-    private final Iterable<String> strings;
-
-    private JoinStringsArg(String arg, String delimiter, Iterable<String> strings) {
-      this.arg = arg;
-      this.delimiter = delimiter;
-      this.strings = CollectionUtils.makeImmutable(strings);
-    }
-
-    @Override
-    void eval(ImmutableList.Builder<String> builder) {
-      Iterator<String> parts = strings.iterator();
-      if (!parts.hasNext()) {
-        return;
-      }
-      builder.add(this.arg);
-      StringBuilder arg = new StringBuilder();
-      arg.append(parts.next());
-      while (parts.hasNext()) {
-        arg.append(delimiter);
-        arg.append(parts.next());
-      }
-      builder.add(arg.toString());
-    }
-  }
-
-  private static final class JoinValuesTransformed<T> extends ArgvFragment {
-
-    private final String arg;
-    private final String delimiter;
-    private final Iterable<T> values;
-    private final Function<T, String> toString;
-
-    private JoinValuesTransformed(
-        String arg, String delimiter, Iterable<T> values, Function<T, String> toString) {
-      this.arg = arg;
-      this.delimiter = delimiter;
-      this.values = CollectionUtils.makeImmutable(values);
-      this.toString = toString;
-    }
-
-    @Override
-    void eval(ImmutableList.Builder<String> builder) {
-      Iterator<T> parts = values.iterator();
-      if (!parts.hasNext()) {
-        return;
-      }
-      builder.add(this.arg);
-      StringBuilder arg = new StringBuilder();
-      arg.append(toString.apply(parts.next()));
-      while (parts.hasNext()) {
-        arg.append(delimiter);
-        arg.append(toString.apply(parts.next()));
-      }
-      builder.add(arg.toString());
-    }
-  }
-
-  /**
-   * Arguments that intersperse strings between the items in a sequence. There are two forms of
-   * interspersing, and either may be used by this implementation:
-   * <ul>
-   *   <li>before each - a string is added before each item in a sequence. e.g.
-   *       {@code -f foo -f bar -f baz}
-   *   <li>format each - a format string is used to format each item in a sequence. e.g.
-   *       {@code -I/foo -I/bar -I/baz} for the format {@code "-I%s"}
-   * </ul>
-   *
-   * <p>This class could be used both with both the "before" and "format" features at the same
-   * time, but this is probably more confusion than it is worth. If you need this functionality,
-   * consider using "before" only but storing the strings pre-formatted in a {@link NestedSet}.
-   */
-  private static final class InterspersingArgs extends ArgvFragment {
-    @Nullable private final String arg;
-    private final Iterable<?> sequence;
-    @Nullable private final String beforeEach;
-    @Nullable private final String formatEach;
-
-    /**
-     * Do not call from outside this class because this does not guarantee that {@code sequence} is
-     * immutable.
-     */
-    private InterspersingArgs(
-        @Nullable String arg,
-        Iterable<?> sequence,
-        @Nullable String beforeEach,
-        @Nullable String formatEach) {
-      this.arg = arg;
-      this.sequence = sequence;
-      this.beforeEach = beforeEach;
-      this.formatEach = formatEach;
-    }
-
-    static InterspersingArgs fromStrings(
-        @Nullable String arg,
-        Iterable<?> sequence,
-        @Nullable String beforeEach,
-        @Nullable String formatEach) {
-      return new InterspersingArgs(
-          arg, CollectionUtils.makeImmutable(sequence), beforeEach, formatEach);
-    }
-
-    static InterspersingArgs fromExecPaths(
-        @Nullable String arg,
-        Iterable<Artifact> sequence,
-        @Nullable String beforeEach,
-        @Nullable String formatEach) {
-      return new InterspersingArgs(
-          arg,
-          Artifact.toExecPaths(CollectionUtils.makeImmutable(sequence)),
-          beforeEach,
-          formatEach);
-    }
-
-    @Override
-    void eval(ImmutableList.Builder<String> builder) {
-      Iterator<?> it = sequence.iterator();
-      if (arg != null && it.hasNext()) {
-        builder.add(arg);
-      }
-      while (it.hasNext()) {
-        Object item = it.next();
-        if (item == null) {
-          continue;
-        }
-
-        if (beforeEach != null) {
-          builder.add(beforeEach);
-        }
-        String arg = item.toString();
-        if (formatEach != null) {
-          arg = String.format(formatEach, arg);
-        }
-        builder.add(arg);
-      }
-    }
-  }
-
-
   /**
    * An argument object that evaluates to the exec path of a {@link TreeFileArtifact}, enclosing
    * the associated {@link TreeFileArtifact}.
@@ -476,166 +491,160 @@ public final class CustomCommandLine extends CommandLine {
     // toString() results.
     private final List<Object> arguments = new ArrayList<>();
 
-    public Builder add(@Nullable CharSequence arg) {
-      if (arg != null) {
-        arguments.add(arg);
+    /**
+     * Adds a value to the argument list.
+     *
+     * <p>At expansion time, the object is turned into a string by calling {@link Object#toString},
+     * unless it is an {@link Artifact}, in which case the exec path is used.
+     */
+    public Builder add(@Nullable Object value) {
+      if (value != null) {
+        arguments.add(value);
       }
       return this;
     }
 
-    public Builder add(@Nullable Label arg) {
-      if (arg != null) {
+    /** Adds the arg and the passed value if the value is non-null. */
+    public Builder add(String arg, @Nullable Object value) {
+      Preconditions.checkNotNull(arg);
+      if (value != null) {
         arguments.add(arg);
+        add(value);
       }
       return this;
     }
 
-    public Builder add(String arg, @Nullable Iterable<String> args) {
-      Preconditions.checkNotNull(arg);
-      if (args != null) {
-        arguments.add(
-            InterspersingArgs.fromStrings(arg, args, /*beforeEach=*/ null, /*formatEach=*/ null));
+    /** Adds the string representation of the passed values. */
+    public Builder add(@Nullable ImmutableCollection<?> values) {
+      if (values != null) {
+        arguments.add(values);
       }
       return this;
     }
 
-    public Builder add(@Nullable Iterable<String> args) {
-      if (args != null) {
-        arguments.add(
-            InterspersingArgs.fromStrings(null, args, /*beforeEach=*/ null, /*formatEach=*/ null));
+    /** Adds the string representation of the passed values. */
+    public Builder add(@Nullable NestedSet<?> values) {
+      if (values != null) {
+        arguments.add(values);
       }
       return this;
     }
 
-    public Builder addExecPath(String arg, @Nullable Artifact artifact) {
+    /**
+     * Adds the arg followed by the string representation of the passed values.
+     *
+     * <p>If values is empty, the arg isn't added.
+     */
+    public Builder add(String arg, @Nullable ImmutableCollection<?> values) {
       Preconditions.checkNotNull(arg);
-      if (artifact != null) {
+      if (values != null && !values.isEmpty()) {
         arguments.add(arg);
-        arguments.add(artifact.getExecPath());
+        add(values);
       }
       return this;
     }
 
-    public Builder addExecPaths(String arg, @Nullable Iterable<Artifact> artifacts) {
+    /**
+     * Adds the arg followed by the string representation of the passed values.
+     *
+     * <p>If values is empty, the arg isn't added.
+     */
+    public Builder add(String arg, @Nullable NestedSet<?> values) {
       Preconditions.checkNotNull(arg);
-      if (artifacts != null) {
-        arguments.add(
-            InterspersingArgs.fromExecPaths(
-                arg, artifacts, /*beforeEach=*/ null, /*formatEach=*/ null));
-      }
-      return this;
-    }
-
-    public Builder addExecPaths(@Nullable Iterable<Artifact> artifacts) {
-      if (artifacts != null) {
-        arguments.add(
-            InterspersingArgs.fromExecPaths(
-                null, artifacts, /*beforeEach=*/ null, /*formatEach=*/ null));
+      if (values != null && !values.isEmpty()) {
+        arguments.add(arg);
+        add(values);
       }
       return this;
     }
 
     /**
-     * Adds a flag with the exec path of a placeholder TreeArtifact. When the command line is used
-     * in an action template, the placeholder will be replaced by the exec path of a {@link
-     * TreeFileArtifact} inside the TreeArtifact at execution time for each expanded action.
+     * Adds the expansion of the passed vector arg.
      *
-     * @param arg the name of the argument
-     * @param treeArtifact the TreeArtifact that will be evaluated to one of its child {@link
-     *     TreeFileArtifact} at execution time
+     * <p>Please see {@link VectorArg} for more information.
      */
-    public Builder addPlaceholderTreeArtifactExecPath(String arg, @Nullable Artifact treeArtifact) {
-      Preconditions.checkNotNull(arg);
-      if (treeArtifact != null) {
-        arguments.add(arg);
-        arguments.add(new TreeFileArtifactExecPathArg(treeArtifact));
+    public Builder add(VectorArg.Builder vectorArg) {
+      if (!vectorArg.isEmpty) {
+        VectorArg.push(arguments, vectorArg);
       }
       return this;
     }
 
     /**
-     * Adds a placeholder TreeArtifact exec path. When the command line is used in an action
-     * template, the placeholder will be replaced by the exec path of a {@link TreeFileArtifact}
-     * inside the TreeArtifact at execution time for each expanded action.
+     * Adds the arg followed by the expansion of the vector arg.
      *
-     * @param treeArtifact the TreeArtifact that will be evaluated to one of its child {@link
-     *     TreeFileArtifact} at execution time
+     * <p>Please see {@link VectorArg} for more information.
+     * <p>If values is empty, the arg isn't added.
      */
-    public Builder addPlaceholderTreeArtifactExecPath(@Nullable Artifact treeArtifact) {
-      if (treeArtifact != null) {
-        arguments.add(new TreeFileArtifactExecPathArg(treeArtifact));
+    public Builder add(String arg, VectorArg.Builder vectorArg) {
+      Preconditions.checkNotNull(arg);
+      if (!vectorArg.isEmpty) {
+        arguments.add(arg);
+        add(vectorArg);
       }
       return this;
     }
 
-    public Builder addJoinStrings(
-        String arg, String delimiter, @Nullable Iterable<String> strings) {
-      Preconditions.checkNotNull(arg);
-      Preconditions.checkNotNull(delimiter);
-      if (strings != null) {
-        arguments.add(new JoinStringsArg(arg, delimiter, strings));
+    public Builder add(@Nullable CustomArgv arg) {
+      if (arg != null) {
+        arguments.add(arg);
       }
       return this;
     }
 
-    /**
-     * Adds a list of values transformed by a function and delimited by a string.
-     *
-     * <p>Prefer this to transforming nested sets yourself as it is more memory-efficient. By using
-     * this class, expansion of the nested set is deferred until action execution instead of
-     * retained on the heap.
-     *
-     * @param arg The argument
-     * @param delimiter A delimiter string placed in between each transformed value
-     * @param values The values to expand into a list
-     * @param toString A function that transforms a value into a string
-     */
-    public <T> Builder addJoinValues(
-        String arg, String delimiter, @Nullable Iterable<T> values, Function<T, String> toString) {
-      Preconditions.checkNotNull(arg);
-      Preconditions.checkNotNull(delimiter);
-      Preconditions.checkNotNull(toString);
-      if (values != null) {
-        arguments.add(new JoinValuesTransformed<>(arg, delimiter, values, toString));
+    public Builder add(@Nullable CustomMultiArgv arg) {
+      if (arg != null) {
+        arguments.add(arg);
       }
       return this;
     }
 
-    public Builder addJoinExecPaths(
-        String arg, String delimiter, @Nullable Iterable<Artifact> artifacts) {
-      Preconditions.checkNotNull(arg);
-      Preconditions.checkNotNull(delimiter);
-      if (artifacts != null) {
-        arguments.add(new JoinExecPathsArg(arg, delimiter, artifacts));
-      }
+    /** Calls {@link String#format} at command line expansion time. */
+    public Builder addFormat(String formatStr, Object... args) {
+      Preconditions.checkNotNull(formatStr);
+      FormatArg.push(arguments, formatStr, args);
       return this;
     }
 
-    public Builder addPath(@Nullable PathFragment path) {
-      if (path != null) {
-        arguments.add(path);
+    /** Cancatenates the passed prefix string and the object's string representation. */
+    public Builder addWithPrefix(String prefix, @Nullable Object arg) {
+      Preconditions.checkNotNull(prefix);
+      if (arg != null) {
+        PrefixArg.push(arguments, prefix, arg);
       }
       return this;
     }
 
-    public Builder addPaths(String template, @Nullable PathFragment... path) {
-      Preconditions.checkNotNull(template);
-      if (path != null) {
-        arguments.add(new PathWithTemplateArg(template, path));
+    /**
+     * Adds a flag with the exec path of a placeholder TreeArtifact. When the command line is used
+     * in an action template, the placeholder will be replaced by the exec path of a {@link
+     * TreeFileArtifact} inside the TreeArtifact at execution time for each expanded action.
+     *
+     * @param arg the name of the argument
+     * @param treeArtifact the TreeArtifact that will be evaluated to one of its child {@link
+     *     TreeFileArtifact} at execution time
+     */
+    public Builder addPlaceholderTreeArtifactExecPath(String arg, @Nullable Artifact treeArtifact) {
+      Preconditions.checkNotNull(arg);
+      if (treeArtifact != null) {
+        arguments.add(arg);
+        arguments.add(new TreeFileArtifactExecPathArg(treeArtifact));
       }
       return this;
     }
 
     /**
-     * Adds a param file as an argument.
+     * Adds a placeholder TreeArtifact exec path. When the command line is used in an action
+     * template, the placeholder will be replaced by the exec path of a {@link TreeFileArtifact}
+     * inside the TreeArtifact at execution time for each expanded action.
      *
-     * @param paramFilePrefix The character that denotes a param file, commonly '@'
-     * @param paramFile The param file artifact
+     * @param treeArtifact the TreeArtifact that will be evaluated to one of its child {@link
+     *     TreeFileArtifact} at execution time
      */
-    public Builder addParamFile(String paramFilePrefix, @Nullable Artifact paramFile) {
-      Preconditions.checkNotNull(paramFilePrefix);
-      Preconditions.checkNotNull(paramFile);
-      arguments.add(new ParamFileArgument(paramFilePrefix, paramFile.getExecPath()));
+    public Builder addPlaceholderTreeArtifactExecPath(@Nullable Artifact treeArtifact) {
+      if (treeArtifact != null) {
+        arguments.add(new TreeFileArtifactExecPathArg(treeArtifact));
+      }
       return this;
     }
 
@@ -659,14 +668,6 @@ public final class CustomCommandLine extends CommandLine {
       return this;
     }
 
-    public Builder addJoinPaths(String delimiter, @Nullable Iterable<PathFragment> paths) {
-      Preconditions.checkNotNull(delimiter);
-      if (paths != null && !Iterables.isEmpty(paths)) {
-        arguments.add(new JoinPathsArg(delimiter, paths));
-      }
-      return this;
-    }
-
     /**
      * Adds a string joined together by the exec paths of all {@link TreeFileArtifact}s under
      * {@code treeArtifact}.
@@ -693,51 +694,132 @@ public final class CustomCommandLine extends CommandLine {
       return this;
     }
 
-    public Builder addBeforeEachPath(String repeated, @Nullable Iterable<PathFragment> paths) {
-      Preconditions.checkNotNull(repeated);
-      if (paths != null) {
-        arguments.add(InterspersingArgs.fromStrings(null, paths, repeated, /*formatEach=*/ null));
-      }
-      return this;
+    @Deprecated
+    public Builder addPath(PathFragment pathFragment) {
+      return add(pathFragment);
     }
 
-    public Builder addBeforeEach(String repeated, @Nullable Iterable<String> strings) {
-      Preconditions.checkNotNull(repeated);
-      if (strings != null) {
-        arguments.add(InterspersingArgs.fromStrings(null, strings, repeated, /*formatEach=*/ null));
-      }
-      return this;
+    @Deprecated
+    public Builder addExecPath(String arg, @Nullable Artifact artifact) {
+      return add(arg, artifact);
     }
 
-    public Builder addBeforeEachExecPath(String repeated, @Nullable Iterable<Artifact> artifacts) {
-      Preconditions.checkNotNull(repeated);
-      if (artifacts != null) {
-        arguments.add(
-            InterspersingArgs.fromExecPaths(null, artifacts, repeated, /*formatEach=*/ null));
-      }
-      return this;
+    @Deprecated
+    public Builder addExecPaths(@Nullable ImmutableCollection<Artifact> artifacts) {
+      return add(artifacts);
     }
 
-    public Builder addFormatEach(String format, @Nullable Iterable<String> strings) {
-      Preconditions.checkNotNull(format);
-      if (strings != null) {
-        arguments.add(InterspersingArgs.fromStrings(null, strings, /*beforeEach=*/ null, format));
-      }
-      return this;
+    @Deprecated
+    public Builder addExecPaths(@Nullable NestedSet<Artifact> artifacts) {
+      return add(artifacts);
     }
 
-    public Builder add(@Nullable CustomArgv arg) {
-      if (arg != null) {
-        arguments.add(arg);
-      }
-      return this;
+    @Deprecated
+    public Builder addExecPaths(String arg, @Nullable ImmutableCollection<Artifact> artifacts) {
+      return add(arg, artifacts);
     }
 
-    public Builder add(@Nullable CustomMultiArgv arg) {
-      if (arg != null) {
-        arguments.add(arg);
-      }
-      return this;
+    @Deprecated
+    public Builder addExecPaths(String arg, @Nullable NestedSet<Artifact> artifacts) {
+      return add(arg, artifacts);
+    }
+
+    @Deprecated
+    public Builder addJoinExecPaths(
+        String arg, String delimiter, @Nullable ImmutableCollection<?> values) {
+      return add(arg, VectorArg.of(values).joinWith(delimiter));
+    }
+
+    @Deprecated
+    public Builder addJoinExecPaths(String arg, String delimiter, @Nullable NestedSet<?> values) {
+      return add(arg, VectorArg.of(values).joinWith(delimiter));
+    }
+
+    @Deprecated
+    public Builder addPaths(String formatStr, PathFragment path) {
+      Preconditions.checkNotNull(path);
+      return addFormat(formatStr, path);
+    }
+
+    @Deprecated
+    public Builder addPaths(String formatStr, PathFragment path0, PathFragment path1) {
+      Preconditions.checkNotNull(path0);
+      Preconditions.checkNotNull(path1);
+      return addFormat(formatStr, path0, path1);
+    }
+
+    @Deprecated
+    public Builder addBeforeEachExecPath(
+        String beforeEach, @Nullable ImmutableCollection<Artifact> values) {
+      return add(VectorArg.of(values).beforeEach(beforeEach));
+    }
+
+    @Deprecated
+    public Builder addBeforeEachExecPath(String beforeEach, @Nullable NestedSet<Artifact> values) {
+      return add(VectorArg.of(values).beforeEach(beforeEach));
+    }
+
+    @Deprecated
+    public Builder addJoinPaths(
+        String delimiter, @Nullable ImmutableCollection<PathFragment> pathFragments) {
+      return add(VectorArg.of(pathFragments).joinWith(delimiter));
+    }
+
+    public Builder addBeforeEach(String beforeEach, @Nullable ImmutableCollection<?> values) {
+      return add(VectorArg.of(values).beforeEach(beforeEach));
+    }
+
+    @Deprecated
+    public Builder addBeforeEachPath(
+        String beforeEach, @Nullable ImmutableCollection<PathFragment> values) {
+      return add(VectorArg.of(values).beforeEach(beforeEach));
+    }
+
+    @Deprecated
+    public Builder addBeforeEachPath(String beforeEach, @Nullable NestedSet<PathFragment> values) {
+      return add(VectorArg.of(values).beforeEach(beforeEach));
+    }
+
+    @Deprecated
+    public <T> Builder addJoinValues(
+        String arg,
+        String join,
+        @Nullable ImmutableCollection<?> values,
+        Function<T, String> mapFn) {
+      return add(arg, VectorArg.of(values).joinWith(join).mapEach(mapFn));
+    }
+
+    @Deprecated
+    public <T> Builder addJoinValues(
+        String arg, String join, @Nullable NestedSet<?> values, Function<T, String> mapFn) {
+      return add(arg, VectorArg.of(values).joinWith(join).mapEach(mapFn));
+    }
+
+    @Deprecated
+    public Builder addFormatEach(String formatStr, @Nullable ImmutableCollection<?> values) {
+      return add(VectorArg.of(values).formatEach(formatStr));
+    }
+
+    @Deprecated
+    public Builder addFormatEach(String formatStr, @Nullable NestedSet<?> values) {
+      return add(VectorArg.of(values).formatEach(formatStr));
+    }
+
+    @Deprecated
+    public Builder addJoinStrings(
+        String arg, String delimiter, @Nullable ImmutableCollection<?> values) {
+      return add(arg, VectorArg.of(values).joinWith(delimiter));
+    }
+
+    /**
+     * Adds a param file as an argument.
+     *
+     * @param paramFilePrefix The character that denotes a param file, commonly '@'
+     * @param paramFile The param file artifact
+     */
+    @Deprecated
+    public Builder addParamFile(String paramFilePrefix, @Nullable Artifact paramFile) {
+      return addWithPrefix(paramFilePrefix, paramFile);
     }
 
     public CustomCommandLine build() {
@@ -751,13 +833,12 @@ public final class CustomCommandLine extends CommandLine {
 
   private final ImmutableList<Object> arguments;
 
-
   /**
-   * A map between enclosed TreeArtifacts and their associated {@link TreeFileArtifacts} for
+   * A map between enclosed TreeArtifacts and their associated {@link TreeFileArtifact}s for
    * substitution.
    *
-   * <p> This map is used to support TreeArtifact substitutions in
-   * {@link TreeFileArtifactArgvFragment}s.
+   * <p>This map is used to support TreeArtifact substitutions in {@link
+   * TreeFileArtifactArgvFragment}s.
    */
   private final Map<Artifact, TreeFileArtifact> substitutionMap;
 
@@ -799,24 +880,34 @@ public final class CustomCommandLine extends CommandLine {
 
   private Iterable<String> argumentsInternal(@Nullable ArtifactExpander artifactExpander) {
     ImmutableList.Builder<String> builder = ImmutableList.builder();
-    for (Object arg : arguments) {
+    int count = arguments.size();
+    for (int i = 0; i < count; ) {
+      Object arg = arguments.get(i++);
       Object substitutedArg = substituteTreeFileArtifactArgvFragment(arg);
-      if (substitutedArg instanceof ArgvFragment) {
+      if (substitutedArg instanceof Iterable) {
+        evalSimpleVectorArg((Iterable<?>) substitutedArg, builder);
+      } else if (substitutedArg instanceof ArgvFragment) {
         if (artifactExpander != null
             && substitutedArg instanceof TreeArtifactExpansionArgvFragment) {
           TreeArtifactExpansionArgvFragment expansionArg =
               (TreeArtifactExpansionArgvFragment) substitutedArg;
           expansionArg.eval(builder, artifactExpander);
         } else {
-          ((ArgvFragment) substitutedArg).eval(builder);
+          i = ((ArgvFragment) substitutedArg).eval(arguments, i, builder);
         }
       } else {
-        builder.add(substitutedArg.toString());
+        builder.add(valueToString(substitutedArg));
       }
     }
     return builder.build();
   }
 
+  private void evalSimpleVectorArg(Iterable<?> arg, ImmutableList.Builder<String> builder) {
+    for (Object value : arg) {
+      builder.add(valueToString(value));
+    }
+  }
+
   /**
    * If the given arg is a {@link TreeFileArtifactArgvFragment} and we have its associated
    * TreeArtifact substitution map, returns another argument object that has its enclosing
@@ -832,4 +923,10 @@ public final class CustomCommandLine extends CommandLine {
       return arg;
     }
   }
+
+  private static String valueToString(Object value) {
+    return value instanceof Artifact
+        ? ((Artifact) value).getExecPath().getPathString()
+        : value.toString();
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/ParamFileHelper.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/ParamFileHelper.java
index 7a3e16b207..d364f924c0 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/ParamFileHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/ParamFileHelper.java
@@ -88,7 +88,7 @@ public final class ParamFileHelper {
    * @param parameterFile the output parameter file artifact
    */
   public static CommandLine createWithParamsFile(
-      List<String> executableArgs, ParamFileInfo paramFileInfo, Artifact parameterFile) {
+      ImmutableList<String> executableArgs, ParamFileInfo paramFileInfo, Artifact parameterFile) {
     return CustomCommandLine.builder()
         .add(executableArgs)
         .addParamFile(paramFileInfo.getFlag(), parameterFile)
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java
index 54f1d9e7f0..ffbd8bcdf5 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/SpawnAction.java
@@ -637,7 +637,7 @@ public class SpawnAction extends AbstractAction implements ExecutionInfoSpecifie
         @Nullable ActionEnvironment configEnv,
         @Nullable PathFragment defaultShellExecutable,
         @Nullable Artifact paramsFile) {
-      List<String> argv = buildExecutableArgs(defaultShellExecutable);
+      ImmutableList<String> argv = buildExecutableArgs(defaultShellExecutable);
       Iterable<String> arguments = argumentsBuilder.build();
       CommandLine actualCommandLine;
       if (paramsFile != null) {
@@ -717,7 +717,8 @@ public class SpawnAction extends AbstractAction implements ExecutionInfoSpecifie
           extraActionInfoSupplier);
     }
 
-    private List<String> buildExecutableArgs(@Nullable PathFragment defaultShellExecutable) {
+    private ImmutableList<String> buildExecutableArgs(
+        @Nullable PathFragment defaultShellExecutable) {
       if (isShellCommand && executable == null) {
         Preconditions.checkNotNull(defaultShellExecutable);
         executable = defaultShellExecutable;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java
index 8381d03591..14d22abaa2 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidBinary.java
@@ -1295,10 +1295,11 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
 
       Artifact classesDex = getDxArtifact(ruleContext, "classes.dex.zip");
       if (dexShards > 1) {
-        List<Artifact> shards = new ArrayList<>(dexShards);
+        ImmutableList.Builder<Artifact> shardsBuilder = ImmutableList.builder();
         for (int i = 1; i <= dexShards; i++) {
-          shards.add(getDxArtifact(ruleContext, "shard" + i + ".jar"));
+          shardsBuilder.add(getDxArtifact(ruleContext, "shard" + i + ".jar"));
         }
+        ImmutableList<Artifact> shards = shardsBuilder.build();
 
         Artifact javaResourceJar =
             createShuffleJarAction(
@@ -1314,11 +1315,11 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
                 derivedJarFunction,
                 mainDexList);
 
-        List<Artifact> shardDexes = new ArrayList<>(dexShards);
+        ImmutableList.Builder<Artifact> shardDexesBuilder = ImmutableList.builder();
         for (int i = 1; i <= dexShards; i++) {
           Artifact shard = shards.get(i - 1);
           Artifact shardDex = getDxArtifact(ruleContext, "shard" + i + ".dex.zip");
-          shardDexes.add(shardDex);
+          shardDexesBuilder.add(shardDex);
           if (incrementalDexing.contains(AndroidBinaryType.MULTIDEX_SHARDED)) {
             // If there's a main dex list then the first shard contains exactly those files.
             // To work with devices that lack native multi-dex support we need to make sure that
@@ -1333,11 +1334,13 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
                 ruleContext, shard, shardDex, dexopts, /* multidex */ true, (Artifact) null);
           }
         }
+        ImmutableList<Artifact> shardDexes = shardDexesBuilder.build();
 
-        CommandLine mergeCommandLine = CustomCommandLine.builder()
-            .addBeforeEachExecPath("--input_zip", shardDexes)
-            .addExecPath("--output_zip", classesDex)
-            .build();
+        CommandLine mergeCommandLine =
+            CustomCommandLine.builder()
+                .addBeforeEachExecPath("--input_zip", shardDexes)
+                .addExecPath("--output_zip", classesDex)
+                .build();
         ruleContext.registerAction(
             new SpawnAction.Builder()
                 .setMnemonic("MergeDexZips")
@@ -1535,7 +1538,7 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
       RuleContext ruleContext,
       boolean useDexArchives,
       @Nullable Artifact proguardedJar,
-      List<Artifact> shards,
+      ImmutableList<Artifact> shards,
       AndroidCommon common,
       @Nullable Artifact inclusionFilterJar,
       List<String> dexopts,
@@ -1557,9 +1560,10 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
             .addOutputs(shards)
             .addOutput(javaResourceJar);
 
-    CustomCommandLine.Builder shardCommandLine = CustomCommandLine.builder()
-        .addBeforeEachExecPath("--output_jar", shards)
-        .addExecPath("--output_resources", javaResourceJar);
+    CustomCommandLine.Builder shardCommandLine =
+        CustomCommandLine.builder()
+            .addBeforeEachExecPath("--output_jar", shards)
+            .addExecPath("--output_resources", javaResourceJar);
 
     if (mainDexList != null) {
       shardCommandLine.addExecPath("--main_dex_filter", mainDexList);
@@ -1577,8 +1581,11 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
       shardCommandLine.addExecPath("--input_jar", proguardedJar);
       shardAction.addInput(proguardedJar);
     } else {
-      Iterable<Artifact> classpath =
-          Iterables.concat(common.getRuntimeJars(), attributes.getRuntimeClassPathForArchive());
+      ImmutableList<Artifact> classpath =
+          ImmutableList.<Artifact>builder()
+              .addAll(common.getRuntimeJars())
+              .addAll(attributes.getRuntimeClassPathForArchive())
+              .build();
       // Check whether we can use dex archives.  Besides the --incremental_dexing flag, also
       // make sure the "dexopts" attribute on this target doesn't mention any problematic flags.
       if (useDexArchives) {
@@ -1608,7 +1615,7 @@ public abstract class AndroidBinary implements RuleConfiguredTargetFactory {
         classpath = dexedClasspath.build();
         shardCommandLine.add("--split_dexed_classes");
       } else {
-        classpath = Iterables.transform(classpath, derivedJarFunction);
+        classpath = classpath.stream().map(derivedJarFunction::apply).collect(toImmutableList());
       }
       shardCommandLine.addBeforeEachExecPath("--input_jar", classpath);
       shardAction.addInputs(classpath);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdlHelper.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdlHelper.java
index b2de617bdf..7e0dfbb075 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdlHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidIdlHelper.java
@@ -341,7 +341,7 @@ public class AndroidIdlHelper {
                     .addExecPath("--output_source_jar", idlSourceJar)
                     .add("--temp_dir")
                     .addPath(idlTempDir)
-                    .addExecPaths(generatedIdlJavaFiles)
+                    .addExecPaths(ImmutableList.copyOf(generatedIdlJavaFiles))
                     .build())
             .useParameterFile(ParameterFileType.SHELL_QUOTED)
             .setProgressMessage("Building idl jars %s", idlClassJar.prettyPrint())
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesProcessorBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesProcessorBuilder.java
index 4d4143c2ca..f171ec6971 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesProcessorBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesProcessorBuilder.java
@@ -461,13 +461,14 @@ public class AndroidResourcesProcessorBuilder {
       builder.addJoinStrings("--prefilteredResources", ",", filteredResources);
     }
     if (!uncompressedExtensions.isEmpty()) {
-      builder.addJoinStrings("--uncompressedExtensions", ",", uncompressedExtensions);
+      builder.addJoinStrings(
+          "--uncompressedExtensions", ",", ImmutableList.copyOf(uncompressedExtensions));
     }
     if (!crunchPng) {
       builder.add("--useAaptCruncher=no");
     }
     if (!assetsToIgnore.isEmpty()) {
-      builder.addJoinStrings("--assetsToIgnore", ",", assetsToIgnore);
+      builder.addJoinStrings("--assetsToIgnore", ",", ImmutableList.copyOf(assetsToIgnore));
     }
     if (debug) {
       builder.add("--debug");
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveAspect.java b/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveAspect.java
index afad30bafc..441be7ae9a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/DexArchiveAspect.java
@@ -422,11 +422,12 @@ public final class DexArchiveAspect extends NativeAspectClass implements Configu
   private static Artifact createDexArchiveAction(RuleContext ruleContext, String dexbuilderPrereq,
       Artifact jar, Set<String> incrementalDexopts, Artifact dexArchive) {
     // Write command line arguments into a params file for compatibility with WorkerSpawnStrategy
-    CustomCommandLine args = new CustomCommandLine.Builder()
-        .addExecPath("--input_jar", jar)
-        .addExecPath("--output_zip", dexArchive)
-        .add(incrementalDexopts)
-        .build();
+    CustomCommandLine args =
+        new CustomCommandLine.Builder()
+            .addExecPath("--input_jar", jar)
+            .addExecPath("--output_zip", dexArchive)
+            .add(ImmutableList.copyOf(incrementalDexopts))
+            .build();
     Artifact paramFile =
         ruleContext.getDerivedArtifact(
             ParameterFile.derivePath(dexArchive.getRootRelativePath()), dexArchive.getRoot());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/LibraryRGeneratorActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/android/LibraryRGeneratorActionBuilder.java
index bd866ee778..184a8f0c87 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/LibraryRGeneratorActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/LibraryRGeneratorActionBuilder.java
@@ -13,6 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.lib.rules.android;
 
+import static com.google.common.collect.ImmutableList.toImmutableList;
+
 import com.google.common.base.Strings;
 import com.google.common.collect.FluentIterable;
 import com.google.common.collect.ImmutableList;
@@ -72,10 +74,10 @@ public class LibraryRGeneratorActionBuilder {
         FluentIterable.from(deps).append(resourceContainer);
 
     if (!symbolProviders.isEmpty()) {
-      builder.addExecPaths("--symbols", symbolProviders.transform(c -> c.getSymbols()));
-      inputs.addTransitive(
-          NestedSetBuilder.wrap(
-              Order.NAIVE_LINK_ORDER, symbolProviders.transform(ResourceContainer::getSymbols)));
+      ImmutableList<Artifact> symbols =
+          symbolProviders.stream().map(ResourceContainer::getSymbols).collect(toImmutableList());
+      builder.addExecPaths("--symbols", symbols);
+      inputs.addTransitive(NestedSetBuilder.wrap(Order.NAIVE_LINK_ORDER, symbols));
     }
 
     builder.addExecPath("--classJarOutput", rJavaClassJar);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/RClassGeneratorActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/android/RClassGeneratorActionBuilder.java
index 149368391a..3039d68b36 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/RClassGeneratorActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/RClassGeneratorActionBuilder.java
@@ -103,7 +103,8 @@ public class RClassGeneratorActionBuilder {
       Iterable<ResourceContainer> depResources = dependencies.getResources();
       if (!Iterables.isEmpty(depResources)) {
         builder.addBeforeEach(
-            "--library", Iterables.transform(depResources, chooseDepsToArg(version)));
+            "--library",
+            ImmutableList.copyOf(Iterables.transform(depResources, chooseDepsToArg(version))));
         inputs.addTransitive(
             NestedSetBuilder.wrap(
                 Order.NAIVE_LINK_ORDER,
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/ResourceDependencies.java b/src/main/java/com/google/devtools/build/lib/rules/android/ResourceDependencies.java
index b72e105c5d..945fd1a603 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/ResourceDependencies.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/ResourceDependencies.java
@@ -202,10 +202,8 @@ public final class ResourceDependencies {
     return AndroidResourcesProvider.create(label, transitiveResources, directResources);
   }
 
-  /**
-   * Provides an NestedSet of the direct and transitive resources.
-   */
-  public Iterable<ResourceContainer> getResources() {
+  /** Provides an NestedSet of the direct and transitive resources. */
+  public NestedSet<ResourceContainer> getResources() {
     return NestedSetBuilder.<ResourceContainer>naiveLinkOrder()
         .addTransitive(directResources)
         .addTransitive(transitiveResources)
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/ResourceShrinkerActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/android/ResourceShrinkerActionBuilder.java
index 33436cd110..d87b7dbd0d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/ResourceShrinkerActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/ResourceShrinkerActionBuilder.java
@@ -170,10 +170,11 @@ public class ResourceShrinkerActionBuilder {
     inputs.add(sdk.getAndroidJar());
 
     if (!uncompressedExtensions.isEmpty()) {
-      commandLine.addJoinStrings("--uncompressedExtensions", ",", uncompressedExtensions);
+      commandLine.addJoinStrings(
+          "--uncompressedExtensions", ",", ImmutableList.copyOf(uncompressedExtensions));
     }
     if (!assetsToIgnore.isEmpty()) {
-      commandLine.addJoinStrings("--assetsToIgnore", ",", assetsToIgnore);
+      commandLine.addJoinStrings("--assetsToIgnore", ",", ImmutableList.copyOf(assetsToIgnore));
     }
     if (ruleContext.getConfiguration().getCompilationMode() != CompilationMode.OPT) {
       commandLine.add("--debug");
@@ -205,13 +206,14 @@ public class ResourceShrinkerActionBuilder {
     commandLine.addExecPath("--primaryManifest", primaryResources.getManifest());
     inputs.add(primaryResources.getManifest());
 
-    List<Artifact> dependencyManifests = getManifests(dependencyResources);
+    ImmutableList<Artifact> dependencyManifests = getManifests(dependencyResources);
     if (!dependencyManifests.isEmpty()) {
       commandLine.addExecPaths("--dependencyManifest", dependencyManifests);
       inputs.addAll(dependencyManifests);
     }
 
-    List<String> resourcePackages = getResourcePackages(primaryResources, dependencyResources);
+    ImmutableList<String> resourcePackages =
+        getResourcePackages(primaryResources, dependencyResources);
     commandLine.addJoinStrings("--resourcePackages", ",", resourcePackages);
 
     commandLine.addExecPath("--shrunkResourceApk", resourceApkOut);
@@ -239,7 +241,7 @@ public class ResourceShrinkerActionBuilder {
     return resourceApkOut;
   }
 
-  private List<Artifact> getManifests(ResourceDependencies resourceDependencies) {
+  private ImmutableList<Artifact> getManifests(ResourceDependencies resourceDependencies) {
     ImmutableList.Builder<Artifact> manifests = ImmutableList.builder();
     for (ResourceContainer resources : resourceDependencies.getResources()) {
       if (resources.getManifest() != null) {
@@ -249,8 +251,8 @@ public class ResourceShrinkerActionBuilder {
     return manifests.build();
   }
 
-  private List<String> getResourcePackages(ResourceContainer primaryResources,
-      ResourceDependencies resourceDependencies) {
+  private ImmutableList<String> getResourcePackages(
+      ResourceContainer primaryResources, ResourceDependencies resourceDependencies) {
     ImmutableList.Builder<String> resourcePackages = ImmutableList.builder();
     resourcePackages.add(primaryResources.getJavaPackage());
     for (ResourceContainer resources : resourceDependencies.getResources()) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/DeployArchiveBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/java/DeployArchiveBuilder.java
index d34b32c30f..e33fd68b86 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/DeployArchiveBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/DeployArchiveBuilder.java
@@ -199,7 +199,9 @@ public class DeployArchiveBuilder {
     }
 
     args.addExecPaths("--classpath_resources", classpathResources);
-    args.addExecPaths("--sources", runtimeClasspath);
+    if (runtimeClasspath != null) {
+      args.addExecPaths("--sources", ImmutableList.copyOf(runtimeClasspath));
+    }
     return args;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
index 56eac18a53..80774a48f6 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompilationHelper.java
@@ -33,7 +33,6 @@ import com.google.devtools.build.lib.analysis.actions.CustomCommandLine;
 import com.google.devtools.build.lib.analysis.actions.SpawnAction;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration.StrictDepsMode;
-import com.google.devtools.build.lib.collect.ImmutableIterable;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.packages.AttributeMap;
@@ -321,7 +320,7 @@ public final class JavaCompilationHelper {
     builder.addSourceJars(attributes.getSourceJars());
     builder.setClasspathEntries(attributes.getCompileTimeClassPath());
     builder.setBootclasspathEntries(
-        ImmutableIterable.from(Iterables.concat(getBootclasspathOrDefault(), getExtdirInputs())));
+        ImmutableList.copyOf(Iterables.concat(getBootclasspathOrDefault(), getExtdirInputs())));
 
     // only run API-generating annotation processors during header compilation
     builder.setProcessorPaths(attributes.getApiGeneratingProcessorPath());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java
index f1dbe1013b..95e83c1086 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaCompileAction.java
@@ -27,7 +27,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.devtools.build.lib.actions.Action;
 import com.google.devtools.build.lib.actions.ActionEnvironment;
 import com.google.devtools.build.lib.actions.ActionOwner;
@@ -432,7 +431,7 @@ public final class JavaCompileAction extends SpawnAction {
               .addJoinExecPaths(
                   "-cp",
                   pathDelimiter,
-                  Iterables.concat(instrumentationJars, ImmutableList.of(javaBuilderJar)))
+                  ImmutableList.builder().addAll(instrumentationJars).add(javaBuilderJar).build())
               .add(javaBuilderMainClass);
         } else {
           // If there are no instrumentation jars, use simpler '-jar' option to launch JavaBuilder.
@@ -701,19 +700,19 @@ public final class JavaCompileAction extends SpawnAction {
         result.addExecPaths("--processorpath", processorPath);
       }
       if (!processorNames.isEmpty()) {
-        result.add("--processors", processorNames);
+        result.add("--processors", ImmutableList.copyOf(processorNames));
       }
       if (!processorFlags.isEmpty()) {
-        result.add("--javacopts", processorFlags);
+        result.add("--javacopts", ImmutableList.copyOf(processorFlags));
       }
       if (!sourceJars.isEmpty()) {
-        result.addExecPaths("--source_jars", sourceJars);
+        result.addExecPaths("--source_jars", ImmutableList.copyOf(sourceJars));
       }
       if (!sourceFiles.isEmpty()) {
         result.addExecPaths("--sources", sourceFiles);
       }
       if (!javacOpts.isEmpty()) {
-        result.add("--javacopts", javacOpts);
+        result.add("--javacopts", ImmutableList.copyOf(javacOpts));
       }
       if (ruleKind != null) {
         result.add("--rule_kind");
@@ -723,11 +722,11 @@ public final class JavaCompileAction extends SpawnAction {
         result.add("--target_label");
         if (targetLabel.getPackageIdentifier().getRepository().isDefault()
             || targetLabel.getPackageIdentifier().getRepository().isMain()) {
-          result.add(targetLabel.toString());
+          result.add(targetLabel);
         } else {
           // @-prefixed strings will be assumed to be filenames and expanded by
           // {@link JavaLibraryBuildRequest}, so add an extra &at; to escape it.
-          result.add("@" + targetLabel);
+          result.addWithPrefix("@", targetLabel);
         }
       }
       if (testOnly) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileAction.java
index 015261d6f3..e7ccb8df35 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/JavaHeaderCompileAction.java
@@ -42,7 +42,6 @@ import com.google.devtools.build.lib.analysis.actions.ParameterFileWriteAction;
 import com.google.devtools.build.lib.analysis.actions.SpawnAction;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.cmdline.Label;
-import com.google.devtools.build.lib.collect.ImmutableIterable;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
@@ -171,8 +170,7 @@ public class JavaHeaderCompileAction extends SpawnAction {
     private final Collection<Artifact> sourceJars = new ArrayList<>();
     private NestedSet<Artifact> classpathEntries =
         NestedSetBuilder.emptySet(Order.NAIVE_LINK_ORDER);
-    private ImmutableIterable<Artifact> bootclasspathEntries =
-        ImmutableIterable.from(ImmutableList.<Artifact>of());
+    private ImmutableList<Artifact> bootclasspathEntries = ImmutableList.<Artifact>of();
     @Nullable private String ruleKind;
     @Nullable private Label targetLabel;
     private PathFragment tempDirectory;
@@ -250,7 +248,7 @@ public class JavaHeaderCompileAction extends SpawnAction {
     }
 
     /** Sets the compilation bootclasspath entries. */
-    public Builder setBootclasspathEntries(ImmutableIterable<Artifact> bootclasspathEntries) {
+    public Builder setBootclasspathEntries(ImmutableList<Artifact> bootclasspathEntries) {
       checkNotNull(bootclasspathEntries, "bootclasspathEntries must not be null");
       this.bootclasspathEntries = bootclasspathEntries;
       return this;
@@ -530,7 +528,7 @@ public class JavaHeaderCompileAction extends SpawnAction {
       result.addExecPaths("--sources", sourceFiles);
 
       if (!sourceJars.isEmpty()) {
-        result.addExecPaths("--source_jars", sourceJars);
+        result.addExecPaths("--source_jars", ImmutableList.copyOf(sourceJars));
       }
 
       result.add("--javacopts", javacOpts);
@@ -543,11 +541,11 @@ public class JavaHeaderCompileAction extends SpawnAction {
         result.add("--target_label");
         if (targetLabel.getPackageIdentifier().getRepository().isDefault()
             || targetLabel.getPackageIdentifier().getRepository().isMain()) {
-          result.add(targetLabel.toString());
+          result.add(targetLabel);
         } else {
           // @-prefixed strings will be assumed to be params filenames and expanded,
           // so add an extra @ to escape it.
-          result.add("@" + targetLabel);
+          result.addWithPrefix("@", targetLabel);
         }
       }
       result.addExecPaths("--classpath", classpathEntries);
@@ -559,10 +557,10 @@ public class JavaHeaderCompileAction extends SpawnAction {
       CustomCommandLine.Builder result = CustomCommandLine.builder();
       baseCommandLine(result, classpathEntries);
       if (!processorNames.isEmpty()) {
-        result.add("--processors", processorNames);
+        result.add("--processors", ImmutableList.copyOf(processorNames));
       }
       if (!processorFlags.isEmpty()) {
-        result.add("--javacopts", processorFlags);
+        result.add("--javacopts", ImmutableList.copyOf(processorFlags));
       }
       if (!processorPath.isEmpty()) {
         result.addExecPaths("--processorpath", processorPath);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/ResourceJarActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/java/ResourceJarActionBuilder.java
index eaa06555fb..e8902f49ec 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/ResourceJarActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/ResourceJarActionBuilder.java
@@ -38,7 +38,7 @@ public class ResourceJarActionBuilder {
   private Artifact outputJar;
   private Map<PathFragment, Artifact> resources = ImmutableMap.of();
   private NestedSet<Artifact> resourceJars = NestedSetBuilder.emptySet(Order.STABLE_ORDER);
-  private List<Artifact> classpathResources = ImmutableList.of();
+  private ImmutableList<Artifact> classpathResources = ImmutableList.of();
   private List<Artifact> messages = ImmutableList.of();
   private JavaToolchainProvider javaToolchain;
   private NestedSet<Artifact> javabase;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/java/SingleJarActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/java/SingleJarActionBuilder.java
index a610ea0651..fffeb69549 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/java/SingleJarActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/java/SingleJarActionBuilder.java
@@ -94,7 +94,7 @@ public final class SingleJarActionBuilder {
     CustomCommandLine.Builder args = CustomCommandLine.builder();
     args.addExecPath("--output", outputJar);
     args.add(SOURCE_JAR_COMMAND_LINE_ARGS);
-    args.addExecPaths("--sources", resourceJars);
+    args.addExecPaths("--sources", ImmutableList.copyOf(resourceJars));
     if (!resources.isEmpty()) {
       args.add("--resources");
       for (Map.Entry<PathFragment, Artifact> resource : resources.entrySet()) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/BundleSupport.java b/src/main/java/com/google/devtools/build/lib/rules/objc/BundleSupport.java
index 2708a7b2aa..b353ad1d6b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/BundleSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/BundleSupport.java
@@ -21,6 +21,7 @@ import static com.google.devtools.build.lib.rules.objc.ObjcProvider.XCASSETS_DIR
 
 import com.google.common.base.Optional;
 import com.google.common.base.Verify;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Artifact;
@@ -447,8 +448,8 @@ final class BundleSupport {
     }
 
     return commandLine
-        .add(PathFragment.safePathStrings(provider.get(XCASSETS_DIR)))
-        .add(extraActoolArgs)
+        .add(ImmutableList.copyOf(PathFragment.safePathStrings(provider.get(XCASSETS_DIR))))
+        .add(ImmutableList.copyOf(extraActoolArgs))
         .build();
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/CompilationSupport.java b/src/main/java/com/google/devtools/build/lib/rules/objc/CompilationSupport.java
index 285fbd0fe5..4df8db9732 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/CompilationSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/CompilationSupport.java
@@ -1161,7 +1161,7 @@ public abstract class CompilationSupport {
   }
 
   private static CommandLine symbolStripCommandLine(
-      Iterable<String> extraFlags, Artifact unstrippedArtifact, Artifact strippedArtifact) {
+      ImmutableList<String> extraFlags, Artifact unstrippedArtifact, Artifact strippedArtifact) {
     return CustomCommandLine.builder()
         .add(STRIP)
         .add(extraFlags)
@@ -1180,7 +1180,7 @@ public abstract class CompilationSupport {
    * subject to the given {@link StrippingType}.
    */
   protected void registerBinaryStripAction(Artifact binaryToLink, StrippingType strippingType) {
-    final Iterable<String> stripArgs;
+    final ImmutableList<String> stripArgs;
     if (isTestRule) {
       // For test targets, only debug symbols are stripped off, since /usr/bin/strip is not able
       // to strip off all symbols in XCTest bundle.
@@ -1394,8 +1394,7 @@ public abstract class CompilationSupport {
             .add("--");
     for (ObjcHeaderThinningInfo info : infos) {
       cmdLine.addJoinPaths(
-          ":",
-          Lists.newArrayList(info.sourceFile.getExecPath(), info.headersListFile.getExecPath()));
+          ":", ImmutableList.of(info.sourceFile.getExecPath(), info.headersListFile.getExecPath()));
       builder.addInput(info.sourceFile).addOutput(info.headersListFile);
     }
     ruleContext.registerAction(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/J2ObjcAspect.java b/src/main/java/com/google/devtools/build/lib/rules/objc/J2ObjcAspect.java
index 61e99ec6d9..1c17394a30 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/J2ObjcAspect.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/J2ObjcAspect.java
@@ -461,7 +461,7 @@ public class J2ObjcAspect extends NativeAspectClass implements ConfiguredAspectF
         j2objcSourceJarTranslatedHeaderFiles(ruleContext));
   }
 
-  private static List<String> sourceJarFlags(RuleContext ruleContext) {
+  private static ImmutableList<String> sourceJarFlags(RuleContext ruleContext) {
     return ImmutableList.of(
         "--output_gen_source_dir",
         j2ObjcSourceJarTranslatedSourceFiles(ruleContext).getExecPathString(),
@@ -492,14 +492,14 @@ public class J2ObjcAspect extends NativeAspectClass implements ConfiguredAspectF
     ImmutableList.Builder<Artifact> sourceJarOutputFiles = ImmutableList.builder();
     if (!Iterables.isEmpty(sourceJars)) {
       sourceJarOutputFiles.addAll(sourceJarOutputs(ruleContext));
-      argBuilder.addJoinExecPaths("--src_jars", ",", sourceJars);
+      argBuilder.addJoinExecPaths("--src_jars", ",", ImmutableList.copyOf(sourceJars));
       argBuilder.add(sourceJarFlags(ruleContext));
     }
 
     Iterable<String> translationFlags = ruleContext
         .getFragment(J2ObjcConfiguration.class)
         .getTranslationFlags();
-    argBuilder.add(translationFlags);
+    argBuilder.add(ImmutableList.copyOf(translationFlags));
 
     NestedSet<Artifact> depsHeaderMappingFiles =
         depJ2ObjcMappingFileProvider.getHeaderMappingFiles();
@@ -541,7 +541,7 @@ public class J2ObjcAspect extends NativeAspectClass implements ConfiguredAspectF
       argBuilder.addJoinExecPaths("-classpath", ":", compileTimeJars);
     }
 
-    argBuilder.addExecPaths(sources);
+    argBuilder.addExecPaths(ImmutableList.copyOf(sources));
 
     Artifact paramFile = j2ObjcOutputParamFile(ruleContext);
     ruleContext.registerAction(new ParameterFileWriteAction(
@@ -584,10 +584,11 @@ public class J2ObjcAspect extends NativeAspectClass implements ConfiguredAspectF
     if (experimentalJ2ObjcHeaderMap) {
       CustomCommandLine.Builder headerMapCommandLine = CustomCommandLine.builder();
       if (!Iterables.isEmpty(sources)) {
-        headerMapCommandLine.addJoinExecPaths("--source_files", ",", sources);
+        headerMapCommandLine.addJoinExecPaths("--source_files", ",", ImmutableList.copyOf(sources));
       }
       if (!Iterables.isEmpty(sourceJars)) {
-        headerMapCommandLine.addJoinExecPaths("--source_jars", ",", sourceJars);
+        headerMapCommandLine.addJoinExecPaths(
+            "--source_jars", ",", ImmutableList.copyOf(sourceJars));
       }
       headerMapCommandLine.addExecPath("--output_mapping_file", outputHeaderMappingFile);
       ruleContext.registerAction(new SpawnAction.Builder()
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/LegacyCompilationSupport.java b/src/main/java/com/google/devtools/build/lib/rules/objc/LegacyCompilationSupport.java
index 8f490626cb..0329afa5b3 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/LegacyCompilationSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/LegacyCompilationSupport.java
@@ -289,7 +289,7 @@ public class LegacyCompilationSupport extends CompilationSupport {
       commandLine.add("-g");
     }
 
-    List<String> coverageFlags = ImmutableList.of();
+    ImmutableList<String> coverageFlags = ImmutableList.of();
     if (collectCodeCoverage) {
       if (buildConfiguration.isLLVMCoverageMapFormatEnabled()) {
         coverageFlags = CLANG_LLVM_COVERAGE_FLAGS;
@@ -299,19 +299,19 @@ public class LegacyCompilationSupport extends CompilationSupport {
     }
 
     commandLine
-        .add(compileFlagsForClang(appleConfiguration))
+        .add(ImmutableList.copyOf(compileFlagsForClang(appleConfiguration)))
         .add(commonLinkAndCompileFlagsForClang(objcProvider, objcConfiguration, appleConfiguration))
         .add(objcConfiguration.getCoptsForCompilationMode())
         .addBeforeEachPath(
             "-iquote", ObjcCommon.userHeaderSearchPaths(objcProvider, buildConfiguration))
-        .addBeforeEachExecPath("-include", pchFile.asSet())
-        .addBeforeEachPath("-I", priorityHeaders)
+        .addBeforeEachExecPath("-include", ImmutableList.copyOf(pchFile.asSet()))
+        .addBeforeEachPath("-I", ImmutableList.copyOf(priorityHeaders))
         .addBeforeEachPath("-I", objcProvider.get(INCLUDE))
         .addBeforeEachPath("-isystem", objcProvider.get(INCLUDE_SYSTEM))
-        .add(otherFlags)
+        .add(ImmutableList.copyOf(otherFlags))
         .addFormatEach("-D%s", objcProvider.get(DEFINE))
         .add(coverageFlags)
-        .add(getCompileRuleCopts());
+        .add(ImmutableList.copyOf(getCompileRuleCopts()));
 
     // Add input source file arguments
     commandLine.add("-c");
@@ -529,10 +529,13 @@ public class LegacyCompilationSupport extends CompilationSupport {
             .setCommandLine(
                 new CustomCommandLine.Builder()
                     .add("-static")
-                    .add("-arch_only").add(appleConfiguration.getSingleArchitecture())
-                    .add("-syslibroot").add(AppleToolchain.sdkDir())
-                    .add("-o").add(outputArchive.getExecPathString())
-                    .addExecPaths(inputArtifacts)
+                    .add("-arch_only")
+                    .add(appleConfiguration.getSingleArchitecture())
+                    .add("-syslibroot")
+                    .add(AppleToolchain.sdkDir())
+                    .add("-o")
+                    .add(outputArchive.getExecPathString())
+                    .addExecPaths(ImmutableList.copyOf(inputArtifacts))
                     .build())
             .addInputs(inputArtifacts)
             .addOutput(outputArchive)
@@ -660,7 +663,7 @@ public class LegacyCompilationSupport extends CompilationSupport {
       Iterable<Artifact> bazelBuiltLibraries,
       Optional<Artifact> linkmap,
       Optional<Artifact> bitcodeSymbolMap) {
-    Iterable<String> libraryNames = libraryNames(objcProvider);
+    ImmutableList<String> libraryNames = libraryNames(objcProvider);
 
     CustomCommandLine.Builder commandLine = CustomCommandLine.builder()
             .addPath(xcrunwrapper(ruleContext).getExecutable().getExecPath());
@@ -724,12 +727,12 @@ public class LegacyCompilationSupport extends CompilationSupport {
         .add("@executable_path/Frameworks")
         .add("-fobjc-link-runtime")
         .add(DEFAULT_LINKER_FLAGS)
-        .addBeforeEach("-framework", frameworkNames(objcProvider))
+        .addBeforeEach("-framework", ImmutableList.copyOf(frameworkNames(objcProvider)))
         .addBeforeEach("-weak_framework", SdkFramework.names(objcProvider.get(WEAK_SDK_FRAMEWORK)))
         .addFormatEach("-l%s", libraryNames)
         .addExecPath("-o", linkedBinary)
         .addBeforeEachExecPath("-force_load", forceLinkArtifacts)
-        .add(extraLinkArgs)
+        .add(ImmutableList.copyOf(extraLinkArgs))
         .add(objcProvider.get(ObjcProvider.LINKOPT));
 
     if (buildConfiguration.isCodeCoverageEnabled()) {
@@ -819,8 +822,9 @@ public class LegacyCompilationSupport extends CompilationSupport {
   }
 
   /** Returns a list of clang flags used for all link and compile actions executed through clang. */
-  private List<String> commonLinkAndCompileFlagsForClang(
-      ObjcProvider provider, ObjcConfiguration objcConfiguration,
+  private ImmutableList<String> commonLinkAndCompileFlagsForClang(
+      ObjcProvider provider,
+      ObjcConfiguration objcConfiguration,
       AppleConfiguration appleConfiguration) {
     ImmutableList.Builder<String> builder = new ImmutableList.Builder<>();
     ApplePlatform platform = appleConfiguration.getSingleArchPlatform();
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/SdkFramework.java b/src/main/java/com/google/devtools/build/lib/rules/objc/SdkFramework.java
index 8b33d5665c..337af77f74 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/SdkFramework.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/SdkFramework.java
@@ -34,10 +34,8 @@ final class SdkFramework extends Value<SdkFramework> {
     return name;
   }
 
-  /**
-   * Returns an iterable which contains the name of each given framework in the same order.
-   */
-  static Iterable<String> names(Iterable<SdkFramework> frameworks) {
+  /** Returns an iterable which contains the name of each given framework in the same order. */
+  static ImmutableList<String> names(Iterable<SdkFramework> frameworks) {
     ImmutableList.Builder<String> result = new ImmutableList.Builder<>();
     for (SdkFramework framework : frameworks) {
       result.add(framework.getName());
diff --git a/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilder.java
index a7a9b89722..35e98ed712 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/proto/ProtoCompileActionBuilder.java
@@ -324,7 +324,7 @@ public class ProtoCompileActionBuilder {
     }
 
     if (additionalCommandLineArguments != null) {
-      result.add(additionalCommandLineArguments);
+      result.add(ImmutableList.copyOf(additionalCommandLineArguments));
     }
 
     return result;