diff --git a/src/main/java/com/google/devtools/build/lib/actions/ActionOwner.java b/src/main/java/com/google/devtools/build/lib/actions/ActionOwner.java
index b0b163e..82e6797 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/ActionOwner.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/ActionOwner.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.actions;
 
 import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.util.Preconditions;
 
@@ -26,6 +27,7 @@
  * but to avoid storing heavyweight analysis objects in actions, and to avoid coupling between the
  * analysis and actions packages, the RuleConfiguredTarget provides an instance of this class.
  */
+@Immutable
 public final class ActionOwner {
   /** An action owner for special cases. Usage is strongly discouraged. */
   public static final ActionOwner SYSTEM_ACTION_OWNER =
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
index 57e6808..0b1248c 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java
@@ -131,7 +131,7 @@
      * Targets from FilesetEntry.files, or null if the user omitted it.
      */
     @Nullable
-    public List<TransitiveInfoCollection> getFiles() {
+    public ImmutableList<TransitiveInfoCollection> getFiles() {
       return files;
     }
   }
@@ -782,7 +782,7 @@
    * @param attributeName the name of the attribute to process
    * @return a list of strings containing the expanded and tokenized values for the attribute
    */
-  public List<String> getTokenizedStringListAttr(String attributeName) {
+  public ImmutableList<String> getTokenizedStringListAttr(String attributeName) {
     return getExpandedStringListAttr(attributeName, Tokenize.YES);
   }
 
@@ -793,7 +793,7 @@
    * @param attributeName the name of the attribute to process
    * @return a list of strings containing the processed values for the attribute
    */
-  public List<String> getExpandedStringListAttr(String attributeName, Tokenize tokenize) {
+  public ImmutableList<String> getExpandedStringListAttr(String attributeName, Tokenize tokenize) {
     if (!getRule().isAttrDefined(attributeName, Type.STRING_LIST)) {
       // TODO(bazel-team): This should be an error.
       return ImmutableList.of();
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java b/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
index 04792e8..f1e6339 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/SourceManifestAction.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.actions.AbstractFileWriteAction;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -49,12 +50,14 @@
  * <p>Note that this action carefully avoids building the manifest content in
  * memory.
  */
-public class SourceManifestAction extends AbstractFileWriteAction {
+@Immutable // if all ManifestWriter implementations are immutable
+public final class SourceManifestAction extends AbstractFileWriteAction {
 
   private static final String GUID = "07459553-a3d0-4d37-9d78-18ed942470f4";
 
   /**
-   * Interface for defining manifest formatting and reporting specifics.
+   * Interface for defining manifest formatting and reporting specifics. Implementations must be
+   * immutable.
    */
   @VisibleForTesting
   interface ManifestWriter {
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/BinaryFileWriteAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/BinaryFileWriteAction.java
index 3e235bb..d87772d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/BinaryFileWriteAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/BinaryFileWriteAction.java
@@ -20,6 +20,7 @@
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.Preconditions;
 
@@ -30,6 +31,7 @@
 /**
  * Action to write a binary file.
  */
+@Immutable // if source is immutable
 public final class BinaryFileWriteAction extends AbstractFileWriteAction {
 
   private static final String GUID = "eeee07fe-4b40-11e4-82d6-eba0b4f713e2";
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/FileWriteAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/FileWriteAction.java
index 1907f7c..23c1484 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/FileWriteAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/FileWriteAction.java
@@ -20,6 +20,7 @@
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.RuleContext;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Fingerprint;
 
 import java.io.IOException;
@@ -31,7 +32,8 @@
  * <p>TODO(bazel-team): Choose a better name to distinguish this class from
  * {@link BinaryFileWriteAction}.
  */
-public class FileWriteAction extends AbstractFileWriteAction {
+@Immutable // if fileContents is immutable
+public final class FileWriteAction extends AbstractFileWriteAction {
 
   private static final String GUID = "332877c7-ca9f-4731-b387-54f620408522";
 
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/ParameterFileWriteAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/ParameterFileWriteAction.java
index 939d9fc..2a1c9b8 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/ParameterFileWriteAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/ParameterFileWriteAction.java
@@ -20,6 +20,7 @@
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ParameterFile.ParameterFileType;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.ShellEscaper;
 
@@ -31,6 +32,7 @@
 /**
  * Action to write a parameter file for a {@link CommandLine}.
  */
+@Immutable // if commandLine and charset are immutable
 public final class ParameterFileWriteAction extends AbstractFileWriteAction {
 
   private static final String GUID = "45f678d8-e395-401e-8446-e795ccc6361f";
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/actions/TemplateExpansionAction.java b/src/main/java/com/google/devtools/build/lib/analysis/actions/TemplateExpansionAction.java
index 10d4d72..fe404e1 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/actions/TemplateExpansionAction.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/actions/TemplateExpansionAction.java
@@ -18,10 +18,12 @@
 import com.google.common.base.Joiner;
 import com.google.common.base.Objects;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
 import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.ResourceFileLoader;
 import com.google.devtools.build.lib.util.StringUtilities;
@@ -34,12 +36,12 @@
 import java.nio.charset.StandardCharsets;
 import java.util.Collection;
 import java.util.List;
-import java.util.Map;
 
 /**
  * Action to expand a template and write the expanded content to a file.
  */
-public class TemplateExpansionAction extends AbstractFileWriteAction {
+@Immutable // if all substitutions are immutable
+public final class TemplateExpansionAction extends AbstractFileWriteAction {
 
   private static final String GUID = "786c1fe0-dca8-407a-b108-e1ecd6d1bc7f";
 
@@ -52,6 +54,7 @@
    * <p>It should be assumed that the {@link #getKey} invocation is cheap, and
    * that the {@link #getValue} invocation is expensive.
    */
+  @Immutable // if the keys and values in the passed in lists and maps are all immutable
   public abstract static class Substitution {
     private Substitution() {
     }
@@ -80,7 +83,8 @@
      * Returns an immutable Substitution instance for the key and list of values. The
      * values will be joined by spaces before substitution.
      */
-    public static Substitution ofSpaceSeparatedList(final String key, final List<?> value) {
+    public static Substitution ofSpaceSeparatedList(
+        final String key, final ImmutableList<?> value) {
       return new Substitution() {
         @Override
         public String getKey() {
@@ -101,7 +105,8 @@
      *
      * <p>For example, the map <(a,1), (b,2), (c,3)> will become "a=1 b=2 c=3".
      */
-    public static Substitution ofSpaceSeparatedMap(final String key, final Map<?, ?> value) {
+    public static Substitution ofSpaceSeparatedMap(
+        final String key, final ImmutableMap<?, ?> value) {
       return new Substitution() {
         @Override
         public String getKey() {
@@ -164,6 +169,7 @@
    * A template that contains text content, or alternatively throws an {@link
    * IOException}.
    */
+  @Immutable // all subclasses are immutable
   public abstract static class Template {
 
     private static final Charset DEFAULT_CHARSET = StandardCharsets.UTF_8;
@@ -258,7 +264,7 @@
   }
 
   private final Template template;
-  private final List<Substitution> substitutions;
+  private final ImmutableList<Substitution> substitutions;
 
   /**
    * Creates a new TemplateExpansionAction instance.
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
index 349d6d4..fd7671d 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/config/BuildConfiguration.java
@@ -2200,7 +2200,7 @@
    * Returns user-specified test environment variables and their values, as
    * set by the --test_env options.
    */
-  public Map<String, String> getTestEnv() {
+  public ImmutableMap<String, String> getTestEnv() {
     return testEnvironment;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java b/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java
index b140349..fae681b 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/rules/java/BazelJavaSemantics.java
@@ -181,7 +181,7 @@
 
     arguments.add(Substitution.of("%java_start_class%",
         ShellEscaper.escapeString(javaStartClass)));
-    arguments.add(Substitution.ofSpaceSeparatedList("%jvm_flags%", jvmFlags));
+    arguments.add(Substitution.ofSpaceSeparatedList("%jvm_flags%", ImmutableList.copyOf(jvmFlags)));
 
     ruleContext.registerAction(new TemplateExpansionAction(
         ruleContext.getActionOwner(), executable, STUB_SCRIPT, arguments, true));
diff --git a/src/main/java/com/google/devtools/build/lib/collect/IterablesChain.java b/src/main/java/com/google/devtools/build/lib/collect/IterablesChain.java
index 7900cab..69abf33 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/IterablesChain.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/IterablesChain.java
@@ -34,6 +34,9 @@
  * @see CollectionUtils#checkImmutable(Iterable)
  */
 public final class IterablesChain<T> implements Iterable<T> {
+  public static <T> Iterable<T> concat(Iterable<? extends T> a, Iterable<? extends T> b) {
+    return IterablesChain.<T>builder().add(a).add(b).build();
+  }
 
   private final Iterable<T> chain;
 
@@ -61,7 +64,7 @@
  *
    */
   public static class Builder<T> {
-    private List<Iterable<T>> iterables = new ArrayList<>();
+    private List<Iterable<? extends T>> iterables = new ArrayList<>();
     private boolean deduplicate;
 
     private Builder() {
@@ -72,7 +75,7 @@
      *
      * <p>If the iterable can not be confirmed to be immutable, a runtime error is thrown.
      */
-    public Builder<T> add(Iterable<T> iterable) {
+    public Builder<T> add(Iterable<? extends T> iterable) {
       CollectionUtils.checkImmutable(iterable);
       if (!Iterables.isEmpty(iterable)) {
         iterables.add(iterable);
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 48a8a93..8c9fc5f 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
@@ -41,6 +41,7 @@
 import com.google.devtools.build.lib.analysis.actions.SpawnAction;
 import com.google.devtools.build.lib.analysis.actions.SpawnAction.Builder;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
+import com.google.devtools.build.lib.collect.IterablesChain;
 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;
@@ -769,7 +770,7 @@
       ResourceApk resourceApk,
       NativeLibs nativeLibs) {
 
-    Iterable<Artifact> jars = Iterables.concat(
+    Iterable<Artifact> jars = IterablesChain.concat(
         resourceClasses.getArchiveInputs(true), androidCommon.getRuntimeJars());
 
     AndroidSdkProvider sdk = AndroidSdkProvider.fromRuleContext(ruleContext);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesProvider.java b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesProvider.java
index fcd16af..9adf9eb 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/AndroidResourcesProvider.java
@@ -103,7 +103,7 @@
     private final boolean manifestExported;
     private final Artifact javaSourceJar;
     private final Artifact rTxt;
-    private Artifact symbolsTxt;
+    private final Artifact symbolsTxt;
 
     public ResourceContainer(Label label,
         String javaPackage,
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/ApkManifestAction.java b/src/main/java/com/google/devtools/build/lib/rules/android/ApkManifestAction.java
index 8218156..d78f976 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/ApkManifestAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/ApkManifestAction.java
@@ -22,6 +22,8 @@
 import com.google.devtools.build.lib.actions.cache.MetadataHandler;
 import com.google.devtools.build.lib.analysis.FilesToRunProvider;
 import com.google.devtools.build.lib.analysis.actions.AbstractFileWriteAction;
+import com.google.devtools.build.lib.collect.CollectionUtils;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.rules.android.apkmanifest.ApkManifestOuterClass;
 import com.google.devtools.build.lib.rules.android.apkmanifest.ApkManifestOuterClass.ApkManifest;
 import com.google.devtools.build.lib.util.Fingerprint;
@@ -33,7 +35,8 @@
 import java.io.PrintStream;
 import java.util.Map;
 
-public class ApkManifestAction extends AbstractFileWriteAction {
+@Immutable
+public final class ApkManifestAction extends AbstractFileWriteAction {
 
   private static Iterable<Artifact> makeInputs(
       AndroidSdkProvider sdk,
@@ -92,8 +95,8 @@
       Iterable<Artifact> jars,
       ResourceApk resourceApk,
       NativeLibs nativeLibs) {
-
     super(owner, makeInputs(sdk, jars, resourceApk, nativeLibs), outputFile, false);
+    CollectionUtils.checkImmutable(jars);
     this.textOutput = textOutput;
     this.sdk = sdk;
     this.jars = jars;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/NativeLibs.java b/src/main/java/com/google/devtools/build/lib/rules/android/NativeLibs.java
index 78c8db2..dbcf0bf 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/NativeLibs.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/NativeLibs.java
@@ -26,6 +26,7 @@
 import com.google.devtools.build.lib.analysis.actions.FileWriteAction;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.rules.cpp.CcLinkParams;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainProvider;
 import com.google.devtools.build.lib.rules.cpp.CppFileTypes;
@@ -43,6 +44,7 @@
 import javax.annotation.Nullable;
 
 /** Represents the collection of native libraries (.so) to be installed in the APK. */
+@Immutable
 public final class NativeLibs {
   public static final NativeLibs EMPTY =
       new NativeLibs(ImmutableMap.<String, Iterable<Artifact>>of(), null);
@@ -105,10 +107,10 @@
   }
 
   // Map from architecture (CPU folder to place the library in) to libraries for that CPU
-  private final Map<String, Iterable<Artifact>> nativeLibs;
+  private final ImmutableMap<String, Iterable<Artifact>> nativeLibs;
   private final Artifact nativeLibsName;
 
-  private NativeLibs(Map<String, Iterable<Artifact>> nativeLibs, Artifact nativeLibsName) {
+  private NativeLibs(ImmutableMap<String, Iterable<Artifact>> nativeLibs, Artifact nativeLibsName) {
     this.nativeLibs = nativeLibs;
     this.nativeLibsName = nativeLibsName;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/ResourceApk.java b/src/main/java/com/google/devtools/build/lib/rules/android/ResourceApk.java
index 8a14507..0b7bbfc 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/ResourceApk.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/ResourceApk.java
@@ -25,7 +25,7 @@
  * unsigned APKs.
  */
 @Immutable
-public class ResourceApk {
+public final class ResourceApk {
   // TODO(bazel-team): The only field that is legitimately nullable is javaSrcJar. The rest is
   // marked as such due to .fromTransitiveResources(). It seems like there should be a better way
   // to do this.
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 dfd4df3..f8309de 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
@@ -20,6 +20,7 @@
 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;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.rules.android.AndroidResourcesProvider.ResourceContainer;
 
@@ -32,7 +33,8 @@
  * library is included in both the transitive and direct dependencies, it will appear twice. This
  * requires consumers to manage duplicated resources gracefully.
  */
-public class ResourceDependencies {
+@Immutable
+public final class ResourceDependencies {
   /**
    * Contains all the transitive resources that are not generated by the direct ancestors of the
    * current rule.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/android/WriteAdbArgsAction.java b/src/main/java/com/google/devtools/build/lib/rules/android/WriteAdbArgsAction.java
index 0adf008..6ddf13d 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/android/WriteAdbArgsAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/android/WriteAdbArgsAction.java
@@ -19,6 +19,7 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ExecException;
 import com.google.devtools.build.lib.analysis.actions.AbstractFileWriteAction;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.common.options.EnumConverter;
 import com.google.devtools.common.options.Option;
@@ -33,7 +34,8 @@
  * An action that writes the a parameter file to {@code incremental_install.py} based on the command
  * line arguments to {@code blaze mobile-install}.
  */
-public class WriteAdbArgsAction extends AbstractFileWriteAction {
+@Immutable // note that it accesses data non-hermetically during the execution phase
+public final class WriteAdbArgsAction extends AbstractFileWriteAction {
   private static final String GUID = "16720416-3c01-4b0a-a543-ead7e563a1ca";
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModuleMap.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModuleMap.java
index 651eed4..aa365d4 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModuleMap.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModuleMap.java
@@ -20,7 +20,7 @@
  * Structure for C++ module maps. Stores the name of the module and a .cppmap artifact.
  */
 @Immutable
-public class CppModuleMap {
+public final class CppModuleMap {
   // NOTE: If you add a field here, you'll likely need to update CppModuleMapAction.computeKey().
   private final Artifact artifact;
   private final String name;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModuleMapAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModuleMapAction.java
index 71e491d..3fea2c4 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModuleMapAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModuleMapAction.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.ResourceSet;
 import com.google.devtools.build.lib.analysis.actions.AbstractFileWriteAction;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
@@ -36,7 +37,8 @@
  * Creates C++ module map artifact genfiles. These are then passed to Clang to
  * do dependency checking.
  */
-public class CppModuleMapAction extends AbstractFileWriteAction {
+@Immutable
+public final class CppModuleMapAction extends AbstractFileWriteAction {
 
   private static final String GUID = "4f407081-1951-40c1-befc-d6b4daff5de3";
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/WriteBuildInfoHeaderAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/WriteBuildInfoHeaderAction.java
index b0151eb..1edef18 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/WriteBuildInfoHeaderAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/WriteBuildInfoHeaderAction.java
@@ -23,6 +23,7 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.WorkspaceStatusAction;
 import com.google.devtools.build.lib.analysis.actions.AbstractFileWriteAction;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.Preconditions;
 
@@ -38,6 +39,7 @@
  * An action that creates a C++ header containing the build information in the
  * form of #define directives.
  */
+@Immutable
 public final class WriteBuildInfoHeaderAction extends AbstractFileWriteAction {
   private static final String GUID = "b0798174-1352-4a54-854a-9785aaea491b";
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/extra/ExtraActionInfoFileWriteAction.java b/src/main/java/com/google/devtools/build/lib/rules/extra/ExtraActionInfoFileWriteAction.java
index bc3f79d..817234c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/extra/ExtraActionInfoFileWriteAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/extra/ExtraActionInfoFileWriteAction.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.lib.actions.ExecException;
 import com.google.devtools.build.lib.actions.extra.ExtraActionInfo;
 import com.google.devtools.build.lib.analysis.actions.AbstractFileWriteAction;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.Preconditions;
 
@@ -32,11 +33,12 @@
  * .xa file for use by an extra action. This can only be done at execution time because actions may
  * store information only known at execution time into the protocol buffer.
  */
-public class ExtraActionInfoFileWriteAction extends AbstractFileWriteAction {
-  private final Action shadowedAction;
-
+@Immutable // if shadowedAction is immutable
+public final class ExtraActionInfoFileWriteAction extends AbstractFileWriteAction {
   private static final String UUID = "1759f81d-e72e-477d-b182-c4532bdbaeeb";
 
+  private final Action shadowedAction;
+
   ExtraActionInfoFileWriteAction(ActionOwner owner, Artifact extraActionInfoFile,
       Action shadowedAction) {
     super(owner, ImmutableList.<Artifact>of(), extraActionInfoFile, false);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/BUILD b/src/main/java/com/google/devtools/build/lib/rules/genquery/BUILD
index b6c9dde..46edcfa 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/BUILD
@@ -12,6 +12,7 @@
         "//src/main/java/com/google/devtools/build/lib:build-base",
         "//src/main/java/com/google/devtools/build/lib:collect",
         "//src/main/java/com/google/devtools/build/lib:common",
+        "//src/main/java/com/google/devtools/build/lib:concurrent",
         "//src/main/java/com/google/devtools/build/lib:events",
         "//src/main/java/com/google/devtools/build/lib:packages-internal",
         "//src/main/java/com/google/devtools/build/lib:util",
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
index b61d6ac..3f2cd64 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
@@ -22,6 +22,7 @@
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
+import com.google.devtools.build.lib.actions.ActionOwner;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.RuleConfiguredTargetBuilder;
@@ -37,6 +38,7 @@
 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;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
@@ -82,7 +84,6 @@
 import java.io.PrintStream;
 import java.nio.channels.ClosedByInterruptException;
 import java.util.Collection;
-import java.util.Collections;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
@@ -150,25 +151,7 @@
     }
 
     ruleContext.registerAction(
-        new AbstractFileWriteAction(
-            ruleContext.getActionOwner(), Collections.<Artifact>emptySet(), outputArtifact, false) {
-          @Override
-          public DeterministicWriter newDeterministicWriter(ActionExecutionContext ctx) {
-            return new DeterministicWriter() {
-              @Override
-              public void writeOutputFile(OutputStream out) throws IOException {
-                out.write(result);
-              }
-            };
-          }
-
-          @Override
-          protected String computeKey() {
-            Fingerprint f = new Fingerprint();
-            f.addBytes(result);
-            return f.hexDigestAndReset();
-          }
-        });
+        new QueryResultAction(ruleContext.getActionOwner(), outputArtifact, result));
 
     NestedSet<Artifact> filesToBuild = NestedSetBuilder.create(Order.STABLE_ORDER, outputArtifact);
     return new RuleConfiguredTargetBuilder(ruleContext)
@@ -329,6 +312,33 @@
     return outputStream.toByteArray();
   }
 
+  @Immutable // assuming no other reference to result
+  private static final class QueryResultAction extends AbstractFileWriteAction {
+    private final byte[] result;
+
+    private QueryResultAction(ActionOwner owner, Artifact output, byte[] result) {
+      super(owner, ImmutableList.<Artifact>of(), output, /*makeExecutable=*/false);
+      this.result = result;
+    }
+
+    @Override
+    public DeterministicWriter newDeterministicWriter(ActionExecutionContext ctx) {
+      return new DeterministicWriter() {
+        @Override
+        public void writeOutputFile(OutputStream out) throws IOException {
+          out.write(result);
+        }
+      };
+    }
+
+    @Override
+    protected String computeKey() {
+      Fingerprint f = new Fingerprint();
+      f.addBytes(result);
+      return f.hexDigestAndReset();
+    }
+  }
+
   /**
    * Provide target pattern evaluation to the query operations using Skyframe dep lookup. For thread
    * safety, we must synchronize access to the SkyFunction.Environment.
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/TestSupport.java b/src/main/java/com/google/devtools/build/lib/rules/objc/TestSupport.java
index fd94eab..00e54ea 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/TestSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/TestSupport.java
@@ -79,7 +79,7 @@
     String runMemleaks =
         ruleContext.getFragment(ObjcConfiguration.class).runMemleaks() ? "true" : "false";
 
-    Map<String, String> testEnv = ruleContext.getConfiguration().getTestEnv();
+    ImmutableMap<String, String> testEnv = ruleContext.getConfiguration().getTestEnv();
 
     // The substitutions below are common for simulator and lab device.
     ImmutableList.Builder<Substitution> substitutions =
diff --git a/src/main/java/com/google/devtools/build/lib/rules/test/BaselineCoverageAction.java b/src/main/java/com/google/devtools/build/lib/rules/test/BaselineCoverageAction.java
index 20ae43e..99626d2 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/test/BaselineCoverageAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/test/BaselineCoverageAction.java
@@ -29,6 +29,7 @@
 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;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
@@ -42,12 +43,13 @@
  * Generates baseline (empty) coverage for the given non-test target.
  */
 @VisibleForTesting
+@Immutable
 public final class BaselineCoverageAction extends AbstractFileWriteAction
     implements NotifyOnActionCacheHit {
-  private final Iterable<Artifact> instrumentedFiles;
+  private final NestedSet<Artifact> instrumentedFiles;
 
   private BaselineCoverageAction(
-      ActionOwner owner, Iterable<Artifact> instrumentedFiles, Artifact output) {
+      ActionOwner owner, NestedSet<Artifact> instrumentedFiles, Artifact output) {
     super(owner, ImmutableList.<Artifact>of(), output, false);
     this.instrumentedFiles = instrumentedFiles;
   }
@@ -110,7 +112,8 @@
    * Returns collection of baseline coverage artifacts associated with the given target.
    * Will always return 0 or 1 elements.
    */
-  static NestedSet<Artifact> create(RuleContext ruleContext, Iterable<Artifact> instrumentedFiles) {
+  static NestedSet<Artifact> create(
+      RuleContext ruleContext, NestedSet<Artifact> instrumentedFiles) {
     // Baseline coverage artifacts will still go into "testlogs" directory.
     Artifact coverageData = ruleContext.getPackageRelativeArtifact(
         new PathFragment(ruleContext.getTarget().getName()).getChild("baseline_coverage.dat"),
diff --git a/src/main/java/com/google/devtools/build/lib/rules/test/InstrumentedFileManifestAction.java b/src/main/java/com/google/devtools/build/lib/rules/test/InstrumentedFileManifestAction.java
index 96224f0..4f1884b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/test/InstrumentedFileManifestAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/test/InstrumentedFileManifestAction.java
@@ -24,6 +24,7 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.actions.AbstractFileWriteAction;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.util.Fingerprint;
 import com.google.devtools.build.lib.util.Preconditions;
 import com.google.devtools.build.lib.util.RegexFilter;
@@ -33,21 +34,20 @@
 import java.io.OutputStreamWriter;
 import java.io.Writer;
 import java.util.Arrays;
-import java.util.Collection;
 
 /**
  * Creates instrumented file manifest to list instrumented source files.
  */
-class InstrumentedFileManifestAction extends AbstractFileWriteAction {
-
+@Immutable
+final class InstrumentedFileManifestAction extends AbstractFileWriteAction {
   private static final String GUID = "d9ddb800-f9a1-01Da-238d-988311a8475b";
 
-  private final Collection<Artifact> collectedSourceFiles;
-  private final Collection<Artifact> metadataFiles;
+  private final ImmutableList<Artifact> collectedSourceFiles;
+  private final ImmutableList<Artifact> metadataFiles;
   private final RegexFilter instrumentationFilter;
 
-  private InstrumentedFileManifestAction(ActionOwner owner, Collection<Artifact> inputs,
-      Collection<Artifact> additionalSourceFiles, Collection<Artifact> gcnoFiles,
+  private InstrumentedFileManifestAction(ActionOwner owner, ImmutableList<Artifact> inputs,
+      ImmutableList<Artifact> additionalSourceFiles, ImmutableList<Artifact> gcnoFiles,
       Artifact output, RegexFilter instrumentationFilter) {
     super(owner, inputs, output, false);
     this.collectedSourceFiles = additionalSourceFiles;
@@ -102,17 +102,14 @@
    * @param metadataFiles *.gcno/*.em files collected by the {@link InstrumentedFilesCollector}
    * @return instrumented file manifest artifact
    */
-  public static Artifact getInstrumentedFileManifest(final RuleContext ruleContext,
-      final Collection<Artifact> additionalSourceFiles, final Collection<Artifact> metadataFiles) {
+  public static Artifact getInstrumentedFileManifest(RuleContext ruleContext,
+      ImmutableList<Artifact> additionalSourceFiles, ImmutableList<Artifact> metadataFiles) {
     // Instrumented manifest makes sense only for rules with binary output.
     Preconditions.checkState(ruleContext.getRule().hasBinaryOutput());
     Artifact instrumentedFileManifest = ruleContext.getPackageRelativeArtifact(
         ruleContext.getTarget().getName()  + ".instrumented_files",
         ruleContext.getConfiguration().getBinDirectory());
 
-    // Instrumented manifest artifact might already exist in case when multiple test
-    // actions that use slightly different subsets of runfiles set are generated for the same rule.
-    // So check whether we need to create a new action instance.
     ImmutableList<Artifact> inputs = ImmutableList.<Artifact>builder()
         .addAll(additionalSourceFiles)
         .addAll(metadataFiles)
diff --git a/src/main/java/com/google/devtools/build/lib/rules/test/TestActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/test/TestActionBuilder.java
index 856d41d..73235cd 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/test/TestActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/test/TestActionBuilder.java
@@ -39,7 +39,6 @@
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.common.options.EnumConverter;
 
-import java.util.Collection;
 import java.util.List;
 import java.util.Map;
 
@@ -204,7 +203,7 @@
     if (collectCodeCoverage) {
       // Add instrumented file manifest artifact to the list of inputs. This file will contain
       // exec paths of all source files that should be included into the code coverage output.
-      Collection<Artifact> metadataFiles =
+      ImmutableList<Artifact> metadataFiles =
           ImmutableList.copyOf(instrumentedFiles.getInstrumentationMetadataFiles());
       inputsBuilder.addTransitive(NestedSetBuilder.wrap(Order.STABLE_ORDER, metadataFiles));
       for (TransitiveInfoCollection dep :
diff --git a/src/main/java/com/google/devtools/build/lib/util/RegexFilter.java b/src/main/java/com/google/devtools/build/lib/util/RegexFilter.java
index 8484f44..950e276 100644
--- a/src/main/java/com/google/devtools/build/lib/util/RegexFilter.java
+++ b/src/main/java/com/google/devtools/build/lib/util/RegexFilter.java
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.util;
 
 import com.google.common.base.Joiner;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.common.options.Converter;
 import com.google.devtools.common.options.OptionsParsingException;
 
@@ -33,7 +34,8 @@
  * any of the excluded regex expressions and if it matches at least one
  * included regex expression.
  */
-public class RegexFilter implements Serializable {
+@Immutable
+public final class RegexFilter implements Serializable {
   private final Pattern inclusionPattern;
   private final Pattern exclusionPattern;
   private final int hashCode;