Simplify Crosstool Build Variables context

This cl merges two classes used to hold build variables context into one. Those
classes are (previously top-level) jcgd.build.lib.rules.cpp.Variables, and its
inner class View. Both represent a collection of build variables and imo it
makes sense to merge them to make the code simpler.

Also, I cleaned up the build variables api to use primitive strings or instances of VariableValueBuilders, and I've hidden subclasses of VariableValues.

Last but not least, I refactored the code to use immutable collections exclusively. That revealed that 'module_files' variable is sometimes registered twice. I want to clean this eventually ([]).

--
MOS_MIGRATED_REVID=139329823

7 files changed, 413 insertions, 441 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java
index bf9e7c5367..776135cade 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeatures.java
@@ -26,11 +26,12 @@ import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableMultimap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+import com.google.common.collect.Sets.SetView;
 import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
+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.CcToolchainFeatures.Variables.VariableValue;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.View;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.view.config.crosstool.CrosstoolConfig.CToolchain;
 import java.io.IOException;
@@ -43,6 +44,7 @@ import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Queue;
@@ -96,10 +98,10 @@ public class CcToolchainFeatures implements Serializable {
     /**
      * Expands this chunk.
      *
-     * @param view binding of variable names to their values for a single flag expansion.
+     * @param variables binding of variable names to their values for a single flag expansion.
      * @param flag the flag content to append to.
      */
-    void expand(View view, StringBuilder flag);
+    void expand(Variables variables, StringBuilder flag);
   }
   
   /**
@@ -114,7 +116,7 @@ public class CcToolchainFeatures implements Serializable {
     }
     
     @Override
-    public void expand(View view, StringBuilder flag) {
+    public void expand(Variables variables, StringBuilder flag) {
       flag.append(text);
     }
   }
@@ -131,12 +133,12 @@ public class CcToolchainFeatures implements Serializable {
     }
     
     @Override
-    public void expand(View view, StringBuilder stringBuilder) {
+    public void expand(Variables variables, StringBuilder stringBuilder) {
       // We check all variables in FlagGroup.expandCommandLine.
       // If we arrive here with the variable not being available, the variable was provided, but
       // the nesting level of the NestedSequence was deeper than the nesting level of the flag
       // groups.
-      stringBuilder.append(view.getStringVariable(variableName));
+      stringBuilder.append(variables.getStringVariable(variableName));
     }
   }
   
@@ -269,12 +271,10 @@ public class CcToolchainFeatures implements Serializable {
      * Expands the current expandable under the given {@code view}, adding new flags to {@code
      * commandLine}.
      *
-     * <p>TODO(b/32655571): Get rid of @arg 'variables' once implicit iteration is not needed
-     *
-     * <p>The {@code view} controls which variables are visible during the expansion and allows to
-     * recursively expand nested flag groups.
+     * <p>The {@code variables} controls which variables are visible during the expansion and allows
+     * to recursively expand nested flag groups.
      */
-    void expand(View view, Variables variables, List<String> commandLine);
+    void expand(Variables variables, List<String> commandLine);
   }
 
   /**
@@ -293,10 +293,10 @@ public class CcToolchainFeatures implements Serializable {
     
     /** Expand this flag into a single new entry in {@code commandLine}. */
     @Override
-    public void expand(View view, Variables variables, List<String> commandLine) {
+    public void expand(Variables variables, List<String> commandLine) {
       StringBuilder flag = new StringBuilder();
       for (StringChunk chunk : chunks) {
-        chunk.expand(view, flag);
+        chunk.expand(variables, flag);
       }
       commandLine.add(flag.toString());
     }
@@ -309,13 +309,11 @@ public class CcToolchainFeatures implements Serializable {
   private static class EnvEntry implements Serializable {
     private final String key;
     private final ImmutableList<StringChunk> valueChunks;
-    private final ImmutableSet<String> usedVariables;
-    
+
     private EnvEntry(CToolchain.EnvEntry envEntry) throws InvalidConfigurationException {
       this.key = envEntry.getKey();
       StringValueParser parser = new StringValueParser(envEntry.getValue());
       this.valueChunks = parser.getChunks();
-      this.usedVariables = parser.getUsedVariables();
     }
 
     /**
@@ -323,10 +321,9 @@ public class CcToolchainFeatures implements Serializable {
      * The value of the entry is expanded with the given {@code variables}.
      */
     public void addEnvEntry(Variables variables, ImmutableMap.Builder<String, String> envBuilder) {
-      View view = variables.getView(usedVariables);
       StringBuilder value = new StringBuilder();
       for (StringChunk chunk : valueChunks) {
-        chunk.expand(view, value);
+        chunk.expand(variables, value);
       }
       envBuilder.put(key, value.toString());
     }
@@ -378,21 +375,21 @@ public class CcToolchainFeatures implements Serializable {
     }
     
     @Override
-    public void expand(View view, Variables variables, final List<String> commandLine) {
+    public void expand(Variables variables, final List<String> commandLine) {
       if (iterateOverVariable == null) {
         // TODO(b/32655571): Remove branch once implicit iteration is not needed anymore.
-        iterateOverVariable = variables.guessIteratedOverVariable(view, usedVariables);
+        iterateOverVariable = variables.guessIteratedOverVariable(usedVariables);
       }
       if (iterateOverVariable != null) {
-        for (VariableValue variableValue : view.getSequenceVariable(iterateOverVariable)) {
-          View nestedView = new View(view, iterateOverVariable, variableValue);
+        for (VariableValue variableValue : variables.getSequenceVariable(iterateOverVariable)) {
+          Variables nestedVariables = new Variables(variables, iterateOverVariable, variableValue);
           for (Expandable expandable : expandables) {
-            expandable.expand(nestedView, variables, commandLine);
+            expandable.expand(nestedVariables, commandLine);
           }
         }
       } else {
         for (Expandable expandable : expandables) {
-          expandable.expand(view, variables, commandLine);
+          expandable.expand(variables, commandLine);
         }
       }
     }
@@ -417,8 +414,7 @@ public class CcToolchainFeatures implements Serializable {
      * </ul>
      */
     private void expandCommandLine(Variables variables, final List<String> commandLine) {
-      View view = variables.getView(getUsedVariables());
-      expand(view, variables, commandLine);
+      expand(variables, commandLine);
     }
   }
   
@@ -704,7 +700,6 @@ public class CcToolchainFeatures implements Serializable {
   private static class ArtifactNamePattern {
 
     private final ArtifactCategory artifactCategory;
-    private final ImmutableSet<String> variables;
     private final ImmutableList<StringChunk> chunks;
 
     private ArtifactNamePattern(CToolchain.ArtifactNamePattern artifactNamePattern)
@@ -724,7 +719,6 @@ public class CcToolchainFeatures implements Serializable {
       this.artifactCategory = foundCategory;
       
       StringValueParser parser = new StringValueParser(artifactNamePattern.getPattern());
-      this.variables = parser.getUsedVariables();
       this.chunks = parser.getChunks();
     }
 
@@ -738,8 +732,8 @@ public class CcToolchainFeatures implements Serializable {
      */
     public String getArtifactName(Map<String, String> variables) {
       StringBuilder resultBuilder = new StringBuilder();
-      View artifactNameVariables =
-          new Variables.Builder().addAllVariables(variables).build().getView(this.variables);
+      Variables artifactNameVariables =
+          new Variables.Builder().addAllStringVariables(variables).build();
       for (StringChunk chunk : chunks) {
         chunk.expand(artifactNameVariables, resultBuilder);
       }
@@ -799,39 +793,125 @@ public class CcToolchainFeatures implements Serializable {
     }
 
     /** Interface for VariableValue builders */
-    interface VariableValueBuilder {
+    public interface VariableValueBuilder {
       VariableValue build();
     }
 
+    /** Builder for StructureSequence. */
+    public static class StructureSequenceBuilder implements VariableValueBuilder {
+
+      private final ImmutableList.Builder<ImmutableMap<String, VariableValue>> values =
+          ImmutableList.builder();
+
+      /** Adds a structure to the sequence. */
+      public StructureSequenceBuilder addValue(ImmutableMap<String, VariableValue> value) {
+        values.add(value);
+        return this;
+      }
+
+      /** Returns an immutable structure sequence. */
+      @Override
+      public StructureSequence build() {
+        return new StructureSequence(values.build());
+      }
+    }
+
+    /** Builder for StringSequence. */
+    public static class StringSequenceBuilder implements VariableValueBuilder {
+
+      private final ImmutableList.Builder<String> values = ImmutableList.builder();
+
+      /** Adds a value to the sequence. */
+      public StringSequenceBuilder addValue(String value) {
+        values.add(value);
+        return this;
+      }
+
+      /** Returns an immutable string sequence. */
+      @Override
+      public StringSequence build() {
+        return new StringSequence(values.build());
+      }
+    }
+
+    /** Builder for Sequence. */
+    public static class SequenceBuilder implements VariableValueBuilder {
+
+      private final ImmutableList.Builder<VariableValue> values = ImmutableList.builder();
+
+      /** Adds a value to the sequence. */
+      public SequenceBuilder addValue(VariableValue value) {
+        values.add(value);
+        return this;
+      }
+
+      /** Adds a value to the sequence. */
+      public SequenceBuilder addValue(VariableValueBuilder value) {
+        values.add(value.build());
+        return this;
+      }
+
+      /** Adds a value to the sequence. */
+      public SequenceBuilder addValues(ImmutableList<VariableValueBuilder> builders) {
+        for (VariableValueBuilder builder : builders) {
+          addValue(builder);
+        }
+        return this;
+      }
+
+      /** Returns an immutable sequence. */
+      @Override
+      public Sequence build() {
+        return new Sequence(values.build());
+      }
+    }
+
+    /** Builder for StructureValue. */
+    public static class StructureBuilder implements VariableValueBuilder {
+
+      private final ImmutableMap.Builder<String, VariableValue> fields = ImmutableMap.builder();
+
+      /** Adds a field to the structure. */
+      public StructureBuilder addField(String name, VariableValue value) {
+        fields.put(name, value);
+        return this;
+      }
+
+      /** Adds a field to the structure. */
+      public StructureBuilder addField(String name, VariableValueBuilder valueBuilder) {
+        fields.put(name, valueBuilder.build());
+        return this;
+      }
+
+      /** Adds a field to the structure. */
+      public StructureBuilder addField(String name, String value) {
+        fields.put(name, new StringValue(value));
+        return this;
+      }
+
+      /** Adds a field to the structure. */
+      public StructureBuilder addField(String name, ImmutableList<String> values) {
+        fields.put(name, new StringSequence(values));
+        return this;
+      }
+
+      /** Returns an immutable structure. */
+      @Override
+      public StructureValue build() {
+        return new StructureValue(fields.build());
+      }
+    }
+
     /**
      * A sequence of structure values. Exists as a memory optimization - a typical build can contain
      * millions of feature values, so getting rid of the overhead of {@code StructureValue} objects
      * significantly reduces memory overhead.
      */
     @Immutable
-    public static final class StructureSequence implements VariableValue {
+    private static final class StructureSequence implements VariableValue {
 
       private final ImmutableList<ImmutableMap<String, VariableValue>> values;
 
-      /** Builder for StructureSequence. */
-      public static class Builder implements VariableValueBuilder {
-
-        private final ImmutableList.Builder<ImmutableMap<String, VariableValue>> values =
-            ImmutableList.builder();
-
-        /** Adds a structure to the sequence. */
-        public Builder addValue(ImmutableMap<String, VariableValue> value) {
-          values.add(value);
-          return this;
-        }
-
-        /** Returns an immutable structure sequence. */
-        @Override
-        public StructureSequence build() {
-          return new StructureSequence(values.build());
-        }
-      }
-
       private StructureSequence(ImmutableList<ImmutableMap<String, VariableValue>> values) {
         this.values = values;
       }
@@ -854,7 +934,8 @@ public class CcToolchainFeatures implements Serializable {
       public VariableValue getFieldValue(String variableName, String field) {
         throw new ExpansionException(
             String.format(
-                "Cannot expand variable '%s.%s': variable '%s' is sequence, expected structure",
+                "Invalid toolchain configuration: Cannot expand variable '%s.%s': variable '%s' is "
+                    + "sequence, expected structure",
                 variableName, field, variableName));
       }
 
@@ -862,7 +943,9 @@ public class CcToolchainFeatures implements Serializable {
       public String getStringValue(String variableName) {
         throw new ExpansionException(
             String.format(
-                "Cannot expand variable '%s': expected string, found sequence", variableName));
+                "Invalid toolchain configuration: Cannot expand variable '%s': expected string, "
+                    + "found sequence",
+                variableName));
       }
     }
 
@@ -872,29 +955,15 @@ public class CcToolchainFeatures implements Serializable {
      * objects significantly reduces memory overhead.
      */
     @Immutable
-    public static final class StringSequence implements VariableValue {
+    private static final class StringSequence implements VariableValue {
 
-      private final ImmutableList<String> values;
+      private final Iterable<String> values;
 
-      /** Builder for StringSequence. */
-      public static class Builder implements VariableValueBuilder {
-
-        private final ImmutableList.Builder<String> values = ImmutableList.builder();
-
-        /** Adds a value to the sequence. */
-        public Builder addValue(String value) {
-          values.add(value);
-          return this;
-        }
-
-        /** Returns an immutable string sequence. */
-        @Override
-        public StringSequence build() {
-          return new StringSequence(values.build());
-        }
+      public StringSequence(ImmutableList<String> values) {
+        this.values = values;
       }
 
-      public StringSequence(ImmutableList<String> values) {
+      StringSequence(NestedSet<String> values) {
         this.values = values;
       }
 
@@ -916,7 +985,8 @@ public class CcToolchainFeatures implements Serializable {
       public VariableValue getFieldValue(String variableName, String field) {
         throw new ExpansionException(
             String.format(
-                "Cannot expand variable '%s.%s': variable '%s' is sequence, expected structure",
+                "Invalid toolchain configuration: Cannot expand variable '%s.%s': variable '%s' is "
+                    + "sequence, expected structure",
                 variableName, field, variableName));
       }
 
@@ -924,40 +994,18 @@ public class CcToolchainFeatures implements Serializable {
       public String getStringValue(String variableName) {
         throw new ExpansionException(
             String.format(
-                "Cannot expand variable '%s': expected string, found sequence", variableName));
+                "Invalid toolchain configuration: Cannot expand variable '%s': expected string, "
+                    + "found sequence",
+                variableName));
       }
     }
 
     /** Sequence of arbitrary VariableValue objects. */
     @Immutable
-    public static final class Sequence implements VariableValue {
+    private static final class Sequence implements VariableValue {
 
       private final ImmutableList<VariableValue> values;
 
-      /** Builder for Sequence. */
-      public static class Builder implements VariableValueBuilder {
-
-        private final ImmutableList.Builder<VariableValue> values = ImmutableList.builder();
-
-        /** Adds a value to the sequence. */
-        public Builder addValue(VariableValue value) {
-          values.add(value);
-          return this;
-        }
-
-        /** Adds a value to the sequence. */
-        public Builder addValue(VariableValueBuilder value) {
-          values.add(value.build());
-          return this;
-        }
-
-        /** Returns an immutable sequence. */
-        @Override
-        public Sequence build() {
-          return new Sequence(values.build());
-        }
-      }
-
       public Sequence(ImmutableList<VariableValue> values) {
         this.values = values;
       }
@@ -976,7 +1024,8 @@ public class CcToolchainFeatures implements Serializable {
       public VariableValue getFieldValue(String variableName, String field) {
         throw new ExpansionException(
             String.format(
-                "Cannot expand variable '%s.%s': variable '%s' is sequence, expected structure",
+                "Invalid toolchain configuration: Cannot expand variable '%s.%s': variable '%s' is "
+                    + "sequence, expected structure",
                 variableName, field, variableName));
       }
 
@@ -984,7 +1033,9 @@ public class CcToolchainFeatures implements Serializable {
       public String getStringValue(String variableName) {
         throw new ExpansionException(
             String.format(
-                "Cannot expand variable '%s': expected string, found sequence", variableName));
+                "Invalid toolchain configuration: Cannot expand variable '%s': expected string, "
+                    + "found sequence",
+                variableName));
       }
     }
 
@@ -993,44 +1044,10 @@ public class CcToolchainFeatures implements Serializable {
      * memory overhead is prohibitively big. Use optimized {@link StructureSequence} instead.
      */
     @Immutable
-    public static final class StructureValue implements VariableValue {
+    private static final class StructureValue implements VariableValue {
 
       private final ImmutableMap<String, VariableValue> value;
 
-      /** Builder for StructureValue. */
-      public static class Builder implements VariableValueBuilder {
-
-        private final ImmutableMap.Builder<String, VariableValue> fields = ImmutableMap.builder();
-
-        /** Adds a field to the structure. */
-        public Builder addField(String name, VariableValue value) {
-          fields.put(name, value);
-          return this;
-        }
-
-        /** Adds a field to the structure. */
-        public Builder addField(String name, VariableValueBuilder valueBuilder) {
-          fields.put(name, valueBuilder.build());
-          return this;
-        }
-
-        /** Adds a field to the structure. */
-        public Builder addField(String name, String... values) {
-          if (values.length == 1) {
-            fields.put(name, new StringValue(values[0]));
-          } else {
-            fields.put(name, new StringSequence(ImmutableList.copyOf(values)));
-          }
-          return this;
-        }
-
-        /** Returns an immutable structure. */
-        @Override
-        public StructureValue build() {
-          return new StructureValue(fields.build());
-        }
-      }
-
       public StructureValue(ImmutableMap<String, VariableValue> value) {
         this.value = value;
       }
@@ -1039,14 +1056,18 @@ public class CcToolchainFeatures implements Serializable {
       public String getStringValue(String variableName) {
         throw new ExpansionException(
             String.format(
-                "Cannot expand variable '%s': expected string, found structure", variableName));
+                "Invalid toolchain configuration: Cannot expand variable '%s': expected string, "
+                    + "found structure",
+                variableName));
       }
 
       @Override
       public Iterable<? extends VariableValue> getSequenceValue(String variableName) {
         throw new ExpansionException(
             String.format(
-                "Cannot expand variable '%s': expected sequence, found structure", variableName));
+                "Invalid toolchain configuration: Cannot expand variable '%s': expected sequence, "
+                    + "found structure",
+                variableName));
       }
 
       @Override
@@ -1056,7 +1077,8 @@ public class CcToolchainFeatures implements Serializable {
         } else {
           throw new ExpansionException(
               String.format(
-                  "Cannot expand variable '%s.%s': structure %s doesn't have a field named '%s'",
+                  "Invalid toolchain configuration: Cannot expand variable '%s.%s': structure %s "
+                      + "doesn't have a field named '%s'",
                   variableName, field, variableName, field));
         }
       }
@@ -1072,7 +1094,7 @@ public class CcToolchainFeatures implements Serializable {
      * never live outside of {@code expand}, as the object overhead is prohibitively expensive.
      */
     @Immutable
-    public static final class StringValue implements VariableValue {
+    private static final class StringValue implements VariableValue {
 
       private final String value;
 
@@ -1089,14 +1111,17 @@ public class CcToolchainFeatures implements Serializable {
       public Iterable<? extends VariableValue> getSequenceValue(String variableName) {
         throw new ExpansionException(
             String.format(
-                "Cannot expand variable '%s': expected sequence, found string", variableName));
+                "Invalid toolchain configuration: Cannot expand variable '%s': expected sequence, "
+                    + "found string",
+                variableName));
       }
 
       @Override
       public VariableValue getFieldValue(String variableName, String field) {
         throw new ExpansionException(
             String.format(
-                "Cannot expand variable '%s.%s': variable '%s' is string, expected structure",
+                "Invalid toolchain configuration: Cannot expand variable '%s.%s': variable '%s' is "
+                    + "string, expected structure",
                 variableName, field, variableName));
       }
 
@@ -1110,66 +1135,78 @@ public class CcToolchainFeatures implements Serializable {
      * Builder for {@code Variables}.
      */
     public static class Builder {
-      private final Map<String, String> variables = Maps.newLinkedHashMap();
-      private final Map<String, VariableValue> sequenceVariables = Maps.newLinkedHashMap();
-      private final Map<String, VariableValue> structureVariables = Maps.newLinkedHashMap();
+      private final Map<String, VariableValue> variablesMap = new LinkedHashMap<>();
 
-      /**
-       * Add a variable that expands {@code name} to {@code value}.
-       */
-      public Builder addVariable(String name, String value) {
-        variables.put(name, value);
+      /** Add a variable that expands {@code name} to {@code value}. */
+      public Builder addStringVariable(String name, String value) {
+        Preconditions.checkArgument(
+            !variablesMap.containsKey(name), "Cannot overwrite variable '%s'", name);
+        variablesMap.put(name, new StringValue(value));
         return this;
       }
-     
-      /**
-       * Add all variables in a map.
-       */
-      public Builder addAllVariables(Map<String, String> variableMap) {
-        variables.putAll(variableMap);
+
+      /** Add a sequence variable that expands {@code name} to {@code values}. */
+      public Builder addStringSequenceVariable(String name, ImmutableList<String> values) {
+        Preconditions.checkArgument(
+            !variablesMap.containsKey(name), "Cannot overwrite variable '%s'", name);
+        variablesMap.put(name, new StringSequence(values));
         return this;
       }
-      
-      /** Add a nested variableValue that expands {@code name} recursively. */
-      public Builder addSequence(String name, VariableValue variableValue) {
-        sequenceVariables.put(name, variableValue);
+
+      /** Add a sequence variable that expands {@code name} to {@code values}. */
+      public Builder addStringSequenceVariable(String name, NestedSet<String> values) {
+        Preconditions.checkArgument(
+            !variablesMap.containsKey(name), "Cannot overwrite variable '%s'", name);
+        variablesMap.put(name, new StringSequence(values));
         return this;
       }
 
       /**
-       * Adds all variables to this builder.
+       * Add a variable built using {@code VariableValueBuilder} api that expands {@code name} to
+       * the value returned by the {@code builder}.
        */
-      public Builder addAll(Variables variables) {
-        this.variables.putAll(variables.variables);
-        this.sequenceVariables.putAll(variables.sequenceVariables);
-        this.structureVariables.putAll(variables.structureVariables);
+      public Builder addCustomBuiltVariable(String name, Variables.VariableValueBuilder builder) {
+        Preconditions.checkArgument(
+            !variablesMap.containsKey(name), "Cannot overwrite variable '%s'", name);
+        variablesMap.put(name, builder.build());
         return this;
       }
 
-      /**
-       * Add a variable that expands a flag group containing a reference to {@code name} for each
-       * entry in {@code values}.
-       */
-      public Builder addSequenceVariable(String name, Iterable<String> values) {
-        StringSequence.Builder sequenceBuilder = new StringSequence.Builder();
-        for (String value : values) {
-          sequenceBuilder.addValue(value);
+      /** Add all string variables in a map. */
+      public Builder addAllStringVariables(Map<String, String> variables) {
+        for (String name : variables.keySet()) {
+          Preconditions.checkArgument(
+              !variablesMap.containsKey(name), "Cannot overwrite variable '%s'", name);
+          variablesMap.put(name, new StringValue(variables.get(name)));
         }
-        return addSequence(name, sequenceBuilder.build());
+        return this;
       }
 
-      public void addStructureVariable(String name, VariableValue value) {
-        this.structureVariables.put(name, value);
+      /** Adds all variables to this builder. Note: cannot override already added variables. */
+      public Builder addAll(Variables variables) {
+        SetView<String> intersection =
+            Sets.intersection(variables.variablesMap.keySet(), variablesMap.keySet());
+        Preconditions.checkArgument(
+            intersection.isEmpty(), "Cannot overwrite existing variables: %s", intersection);
+        this.variablesMap.putAll(variables.variablesMap);
+        return this;
+      }
+
+      /**
+       * Add all variables to this builder, possibly overriding variables already present in the
+       * builder. Use cautiously, prefer {@code addAll} if possible.
+       * TODO(b/32893861) Clean 'module_files' to be registered only once and remove this method.
+       */
+      Builder addAndOverwriteAll(Variables overwrittenVariables) {
+        this.variablesMap.putAll(overwrittenVariables.variablesMap);
+        return this;
       }
 
       /**
        * @return a new {@Variables} object.
        */
       Variables build() {
-        return new Variables(
-            ImmutableMap.copyOf(variables),
-            ImmutableMap.copyOf(sequenceVariables),
-            ImmutableMap.copyOf(structureVariables));
+        return new Variables(ImmutableMap.copyOf(variablesMap));
       }
     }
     
@@ -1181,130 +1218,90 @@ public class CcToolchainFeatures implements Serializable {
       void addVariables(Builder builder);
     }
     
+    private final ImmutableMap<String, VariableValue> variablesMap;
+    private final Variables parent;
+
+    private Variables(ImmutableMap<String, VariableValue> variablesMap) {
+      this.variablesMap = variablesMap;
+      this.parent = null;
+    }
+
     /**
-     * Represents a set of variables visible during an expansion of a variable. If nested (by
-     * specifying a parent), and variable is not present in the current view, it continues the look
-     * up in the parent view.
+     * Creates a variables instance nested under the @param parent, and binds variable named @param
+     * name to @param value
      */
-    @Immutable
-    protected static final class View {
-      private final ImmutableMap<String, VariableValue> viewMap;
-      private final View parent;
+    Variables(Variables parent, String name, VariableValue value) {
+      this.variablesMap = ImmutableMap.of(name, value);
+      this.parent = parent;
+    }
 
-      /**
-       * Creates top level view
-       *
-       * @param viewMap binding of variable names to variable values
-       */
-      View(ImmutableMap<String, VariableValue> viewMap) {
-        this.viewMap = viewMap;
-        this.parent = null;
+    public VariableValue getVariable(String name) {
+      VariableValue variableValue = lookupVariable(name);
+      if (variableValue == null) {
+        throw new ExpansionException(
+            "Invalid toolchain configuration: Cannot find variable named '" + name + "'");
+      } else {
+        return variableValue;
       }
+    }
 
-      /**
-       * Creates a view nested under the @param parent, and binds variable named @param name
-       * to @param value
-       */
-      View(View parent, String name, VariableValue value) {
-        this.viewMap = ImmutableMap.of(name, value);
-        this.parent = parent;
+    private VariableValue lookupVariable(String name) {
+      VariableValue variableValue = getNonStructuredVariable(name);
+      if (variableValue == null) {
+        variableValue = getStructureVariable(name);
       }
+      return variableValue;
+    }
 
-      /** Returns all bound variables in the current view. */
-      Map<String, VariableValue> getVariables() {
-        return viewMap;
-      }
+    public String getStringVariable(String variableName) {
+      return getVariable(variableName).getStringValue(variableName);
+    }
 
-      VariableValue getVariable(String name) {
-        VariableValue variableValue = getNonStructuredVariable(name);
-        if (variableValue == null) {
-          variableValue = getStructureVariable(name);
-        }
-        if (variableValue == null) {
-          throw new ExpansionException("Build variable named '" + name + "' was not found");
-        } else {
-          return variableValue;
-        }
+    public Iterable<? extends VariableValue> getSequenceVariable(String variableName) {
+      return getVariable(variableName).getSequenceValue(variableName);
+    }
+
+    private VariableValue getNonStructuredVariable(String name) {
+      if (variablesMap.containsKey(name)) {
+        return variablesMap.get(name);
       }
 
-      private VariableValue getNonStructuredVariable(String name) {
-        if (viewMap.containsKey(name)) {
-          return viewMap.get(name);
-        }
+      if (parent != null) {
+        return parent.getNonStructuredVariable(name);
+      }
 
-        if (parent != null) {
-          return parent.getNonStructuredVariable(name);
-        }
+      return null;
+    }
 
+    private VariableValue getStructureVariable(String name) {
+      if (!name.contains(".")) {
         return null;
       }
 
-      private VariableValue getStructureVariable(String name) {
-        if (!name.contains(".")) {
-          return null;
-        }
-
-        Stack<String> fieldsToAccess = new Stack<>();
-        String structPath = name;
-        VariableValue structure;
-
-        do {
-          fieldsToAccess.push(structPath.substring(structPath.lastIndexOf('.') + 1));
-          structPath = structPath.substring(0, structPath.lastIndexOf('.'));
-          structure = getNonStructuredVariable(structPath);
-        } while (structure == null && structPath.contains("."));
+      Stack<String> fieldsToAccess = new Stack<>();
+      String structPath = name;
+      VariableValue structure;
 
-        if (structure == null) {
-          return null;
-        }
-        while (!fieldsToAccess.empty()) {
-          structure = structure.getFieldValue(structPath, fieldsToAccess.pop());
-        }
-        return structure;
-      }
+      do {
+        fieldsToAccess.push(structPath.substring(structPath.lastIndexOf('.') + 1));
+        structPath = structPath.substring(0, structPath.lastIndexOf('.'));
+        structure = getNonStructuredVariable(structPath);
+      } while (structure == null && structPath.contains("."));
 
-      public String getStringVariable(String variableName) {
-        VariableValue variable = getVariable(variableName);
-        if (variable == null) {
-          throw new ExpansionException(
-              String.format("Cannot find variable named '%s'", variableName));
-        }
-        return variable.getStringValue(variableName);
+      if (structure == null) {
+        return null;
       }
-
-      public Iterable<? extends VariableValue> getSequenceVariable(String variableName) {
-        VariableValue variable = getVariable(variableName);
-        if (variable == null) {
-          throw new ExpansionException(
-              String.format("Cannot find variable named '%s'", variableName));
-        }
-        return variable.getSequenceValue(variableName);
+      while (!fieldsToAccess.empty()) {
+        structure = structure.getFieldValue(structPath, fieldsToAccess.pop());
       }
+      return structure;
     }
 
-    private final ImmutableMap<String, String> variables;
-    private final ImmutableMap<String, VariableValue> sequenceVariables;
-    private final ImmutableMap<String, VariableValue> structureVariables;
-
-    private Variables(
-        ImmutableMap<String, String> variables,
-        ImmutableMap<String, VariableValue> sequenceVariables,
-        ImmutableMap<String, VariableValue> structures) {
-      this.variables = variables;
-      this.sequenceVariables = sequenceVariables;
-      this.structureVariables = structures;
-    }
-
-    public String guessIteratedOverVariable(View view, ImmutableSet<String> usedVariables) {
+    public String guessIteratedOverVariable(ImmutableSet<String> usedVariables) {
       String sequenceName = null;
       for (String usedVariable : usedVariables) {
-        if (sequenceVariables.containsKey(usedVariable)) {
-          if (variables.containsKey(usedVariable)) {
-            throw new ExpansionException(
-                "Internal error: variable '"
-                    + usedVariable
-                    + "' provided both as sequence and standard variable.");
-          }
+        VariableValue variableValue = getVariable(usedVariable);
+        if (variableValue.isSequence()) {
           if (sequenceName != null) {
             throw new ExpansionException(
                 "Invalid toolchain configuration: trying to expand two variable list in one "
@@ -1313,8 +1310,7 @@ public class CcToolchainFeatures implements Serializable {
                     + "' and '"
                     + usedVariable
                     + "'");
-          }
-          if (view.getVariable(usedVariable).isSequence()) {
+          } else {
             sequenceName = usedVariable;
           }
         }
@@ -1322,40 +1318,9 @@ public class CcToolchainFeatures implements Serializable {
       return sequenceName;
     }
 
-    /**
-     * Returns a view of the current variables under the given {@code controllingVariables}.
-     * Verifies that all controlling variables are available.
-     */
-    View getView(Collection<String> controllingVariables) {
-      ImmutableSet.Builder<String> topLevelVariables = ImmutableSet.builder();
-      for (String name : controllingVariables) {
-        if (name.contains(".")) {
-          topLevelVariables.add(name.substring(0, name.indexOf('.')));
-        } else {
-          topLevelVariables.add(name);
-        }
-      }
-      ImmutableMap.Builder<String, VariableValue> viewMapBuilder = new ImmutableMap.Builder<>();
-      for (String name : topLevelVariables.build()) {
-        if (sequenceVariables.containsKey(name)) {
-          viewMapBuilder.put(name, sequenceVariables.get(name));
-        } else if (variables.containsKey(name)) {
-          viewMapBuilder.put(name, new StringValue(variables.get(name)));
-        } else if (structureVariables.containsKey(name)) {
-          viewMapBuilder.put(name, structureVariables.get(name));
-        } else {
-          throw new ExpansionException(
-              "Invalid toolchain configuration: unknown variable '"
-                  + name
-                  + "' can not be expanded.");
-        }
-      }
-      return new View(viewMapBuilder.build());
-    }
-
     /** Returns whether {@code variable} is set. */
     boolean isAvailable(String variable) {
-      return variables.containsKey(variable) || sequenceVariables.containsKey(variable);
+      return lookupVariable(variable) != null;
     }
   }
   
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
index bc428c05bb..1ef044feec 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileAction.java
@@ -20,7 +20,6 @@ import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.actions.AbstractAction;
 import com.google.devtools.build.lib.actions.ActionExecutionContext;
@@ -981,7 +980,7 @@ public class CppCompileAction extends AbstractAction
    */
   private static CcToolchainFeatures.Variables getOverwrittenVariables(
       Iterable<Artifact> potentialModules) {
-    List<String> usedModulePaths = Lists.newArrayList();
+    ImmutableList.Builder<String> usedModulePaths = ImmutableList.builder();
     for (Artifact input : potentialModules) {
       if (CppFileTypes.CPP_MODULE.matches(input.getFilename())) {
         usedModulePaths.add(input.getExecPathString());
@@ -989,7 +988,7 @@ public class CppCompileAction extends AbstractAction
     }
     CcToolchainFeatures.Variables.Builder variableBuilder =
         new CcToolchainFeatures.Variables.Builder();
-    variableBuilder.addSequenceVariable("module_files", usedModulePaths);
+    variableBuilder.addStringSequenceVariable("module_files", usedModulePaths.build());
     return variableBuilder.build();
   }
 
@@ -1442,7 +1441,7 @@ public class CppCompileAction extends AbstractAction
         CcToolchainFeatures.Variables.Builder variablesBuilder =
             new CcToolchainFeatures.Variables.Builder();
         variablesBuilder.addAll(variables);
-        variablesBuilder.addAll(overwrittenVariables);
+        variablesBuilder.addAndOverwriteAll(overwrittenVariables);
         updatedVariables = variablesBuilder.build();
       }
       addFilteredOptions(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
index 9fe8673389..032624bdd6 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionBuilder.java
@@ -1179,33 +1179,33 @@ public class CppLinkActionBuilder {
 
   private static class LinkArgCollector {
     String rpathRoot;
-    List<String> rpathEntries;
-    Set<String> libopts;
-    List<String> linkerInputParams;
-    List<String> wholeArchiveLinkerInputParams;
-    List<String> noWholeArchiveInputs;
+    ImmutableList<String> rpathEntries;
+    ImmutableSet<String> libopts;
+    ImmutableList<String> linkerInputParams;
+    ImmutableList<String> wholeArchiveLinkerInputParams;
+    ImmutableList<String> noWholeArchiveInputs;
 
     public void setRpathRoot(String rPathRoot) {
       this.rpathRoot = rPathRoot;
     }
 
-    public void setRpathEntries(List<String> rpathEntries) {
+    public void setRpathEntries(ImmutableList<String> rpathEntries) {
       this.rpathEntries = rpathEntries;
     }
 
-    public void setLibopts(Set<String> libopts) {
+    public void setLibopts(ImmutableSet<String> libopts) {
       this.libopts = libopts;
     }
 
-    public void setLinkerInputParams(List<String> linkerInputParams) {
+    public void setLinkerInputParams(ImmutableList<String> linkerInputParams) {
       this.linkerInputParams = linkerInputParams;
     }
 
-    public void setWholeArchiveLinkerInputParams(List<String> wholeArchiveInputParams) {
+    public void setWholeArchiveLinkerInputParams(ImmutableList<String> wholeArchiveInputParams) {
       this.wholeArchiveLinkerInputParams = wholeArchiveInputParams;
     }
 
-    public void setNoWholeArchiveInputs(List<String> noWholeArchiveInputs) {
+    public void setNoWholeArchiveInputs(ImmutableList<String> noWholeArchiveInputs) {
       this.noWholeArchiveInputs = noWholeArchiveInputs;
     }
 
@@ -1213,23 +1213,23 @@ public class CppLinkActionBuilder {
       return rpathRoot;
     }
 
-    public List<String> getRpathEntries() {
+    public ImmutableList<String> getRpathEntries() {
       return rpathEntries;
     }
 
-    public Set<String> getLibopts() {
-      return libopts;
+    public ImmutableList<String> getLibopts() {
+      return libopts.asList();
     }
 
-    public List<String> getLinkerInputParams() {
+    public ImmutableList<String> getLinkerInputParams() {
       return linkerInputParams;
     }
 
-    public List<String> getWholeArchiveLinkerInputParams() {
+    public ImmutableList<String> getWholeArchiveLinkerInputParams() {
       return wholeArchiveLinkerInputParams;
     }
 
-    public List<String> getNoWholeArchiveInputs() {
+    public ImmutableList<String> getNoWholeArchiveInputs() {
       return noWholeArchiveInputs;
     }
   }
@@ -1289,7 +1289,8 @@ public class CppLinkActionBuilder {
 
       // symbol counting
       if (symbolCounts != null) {
-        buildVariables.addVariable(SYMBOL_COUNTS_OUTPUT_VARIABLE, symbolCounts.getExecPathString());
+        buildVariables.addStringVariable(
+            SYMBOL_COUNTS_OUTPUT_VARIABLE, symbolCounts.getExecPathString());
       }
 
       // linkstamp
@@ -1298,54 +1299,57 @@ public class CppLinkActionBuilder {
         linkstampPaths.add(linkstampOutput.getExecPathString());
       }
 
-      buildVariables.addSequenceVariable(LINKSTAMP_PATHS_VARIABLE, linkstampPaths.build());
+      buildVariables.addStringSequenceVariable(
+          LINKSTAMP_PATHS_VARIABLE, linkstampPaths.build().asList());
 
       // pic
       boolean forcePic = cppConfiguration.forcePic();
       if (forcePic) {
-        buildVariables.addVariable(FORCE_PIC_VARIABLE, "");
+        buildVariables.addStringVariable(FORCE_PIC_VARIABLE, "");
       }
 
       // rpath
       if (linkArgCollector.getRpathRoot() != null) {
-        buildVariables.addVariable(RUNTIME_ROOT_FLAGS_VARIABLE, linkArgCollector.getRpathRoot());
+        buildVariables.addStringVariable(
+            RUNTIME_ROOT_FLAGS_VARIABLE, linkArgCollector.getRpathRoot());
       }
 
       if (linkArgCollector.getRpathEntries() != null) {
-        buildVariables.addSequenceVariable(
+        buildVariables.addStringSequenceVariable(
             RUNTIME_ROOT_ENTRIES_VARIABLE, linkArgCollector.getRpathEntries());
       }
 
-      buildVariables.addSequenceVariable(LIBOPTS_VARIABLE, linkArgCollector.getLibopts());
-      buildVariables.addSequenceVariable(
+      buildVariables.addStringSequenceVariable(LIBOPTS_VARIABLE, linkArgCollector.getLibopts());
+      buildVariables.addStringSequenceVariable(
           LINKER_INPUT_PARAMS_VARIABLE, linkArgCollector.getLinkerInputParams());
-      buildVariables.addSequenceVariable(
+      buildVariables.addStringSequenceVariable(
           WHOLE_ARCHIVE_LINKER_INPUT_PARAMS_VARIABLE,
           linkArgCollector.getWholeArchiveLinkerInputParams());
 
       // global archive
       if (needWholeArchive) {
-        buildVariables.addVariable(GLOBAL_WHOLE_ARCHIVE_VARIABLE, "");
+        buildVariables.addStringVariable(GLOBAL_WHOLE_ARCHIVE_VARIABLE, "");
       }
 
       // mostly static
       if (linkStaticness == LinkStaticness.MOSTLY_STATIC && cppConfiguration.skipStaticOutputs()) {
-        buildVariables.addVariable(SKIP_MOSTLY_STATIC_VARIABLE, "");
+        buildVariables.addStringVariable(SKIP_MOSTLY_STATIC_VARIABLE, "");
       }
 
       // output exec path
       if (outputArtifact != null) {
-        buildVariables.addVariable(OUTPUT_EXECPATH_VARIABLE, outputArtifact.getExecPathString());
+        buildVariables.addStringVariable(
+            OUTPUT_EXECPATH_VARIABLE, outputArtifact.getExecPathString());
       }
 
       if (!ltoOutputRootPrefix.equals(PathFragment.EMPTY_FRAGMENT)) {
         if (linkerParamsFile != null) {
-          buildVariables.addVariable(
+          buildVariables.addStringVariable(
               "thinlto_optional_params_file", "=" + linkerParamsFile.getExecPathString());
         } else {
-          buildVariables.addVariable("thinlto_optional_params_file", "");
+          buildVariables.addStringVariable("thinlto_optional_params_file", "");
         }
-        buildVariables.addVariable(
+        buildVariables.addStringVariable(
             "thinlto_prefix_replace",
             configuration.getBinDirectory().getExecPathString()
                 + ";"
@@ -1355,21 +1359,21 @@ public class CppLinkActionBuilder {
           outputArtifact != null
               && interfaceLibraryBuilder != null
               && interfaceLibraryOutput != null;
-      buildVariables.addVariable(
+      buildVariables.addStringVariable(
           GENERATE_INTERFACE_LIBRARY_VARIABLE, shouldGenerateInterfaceLibrary ? "yes" : "no");
-      buildVariables.addVariable(
+      buildVariables.addStringVariable(
           INTERFACE_LIBRARY_BUILDER_VARIABLE,
           shouldGenerateInterfaceLibrary ? interfaceLibraryBuilder.getExecPathString() : "ignored");
-      buildVariables.addVariable(
+      buildVariables.addStringVariable(
           INTERFACE_LIBRARY_INPUT_VARIABLE,
           shouldGenerateInterfaceLibrary ? outputArtifact.getExecPathString() : "ignored");
-      buildVariables.addVariable(
+      buildVariables.addStringVariable(
           INTERFACE_LIBRARY_OUTPUT_VARIABLE,
           shouldGenerateInterfaceLibrary ? interfaceLibraryOutput.getExecPathString() : "ignored");
 
       // Variables arising from the toolchain
       buildVariables
-          .addAllVariables(CppHelper.getToolchain(ruleContext).getBuildVariables())
+          .addAllStringVariables(CppHelper.getToolchain(ruleContext).getBuildVariables())
           .build();
       CppHelper.getFdoSupport(ruleContext).getLinkOptions(featureConfiguration, buildVariables);
     }
@@ -1399,11 +1403,11 @@ public class CppLinkActionBuilder {
     private void addInputFileLinkOptions(LinkArgCollector linkArgCollector) {
 
       // Used to collect -L and -Wl,-rpath options, ensuring that each used only once.
-      Set<String> libOpts = new LinkedHashSet<>();
+      ImmutableSet.Builder<String> libOpts = ImmutableSet.builder();
 
       // List of command line parameters that need to be placed *outside* of
       // --whole-archive ... --no-whole-archive.
-      List<String> noWholeArchiveInputs = new ArrayList<>();
+      ImmutableList.Builder<String> noWholeArchiveInputs = ImmutableList.builder();
 
       PathFragment solibDir =
           configuration
@@ -1418,7 +1422,7 @@ public class CppLinkActionBuilder {
                       && linkStaticness == LinkStaticness.DYNAMIC));
 
       String rpathRoot = null;
-      List<String> runtimeRpathEntries = new ArrayList<>();
+      ImmutableList.Builder<String> runtimeRpathEntries = ImmutableList.builder();
 
       if (output != null) {
         String origin =
@@ -1499,8 +1503,8 @@ public class CppLinkActionBuilder {
         }
       }
 
-      List<String> wholeArchiveInputParams = new ArrayList<>();
-      List<String> standardArchiveInputParams = new ArrayList<>();
+      ImmutableList.Builder<String> wholeArchiveInputParams = ImmutableList.builder();
+      ImmutableList.Builder<String> standardArchiveInputParams = ImmutableList.builder();
 
       for (LinkerInput input : linkerInputs) {
         if (input.getArtifactCategory() == ArtifactCategory.DYNAMIC_LIBRARY) {
@@ -1524,8 +1528,8 @@ public class CppLinkActionBuilder {
       boolean includeRuntimeSolibDir = false;
 
       for (LinkerInput input : runtimeLinkerInputs) {
-        List<String> optionsList = needWholeArchive
-            ? noWholeArchiveInputs : standardArchiveInputParams;
+        ImmutableList.Builder<String> optionsList =
+            needWholeArchive ? noWholeArchiveInputs : standardArchiveInputParams;
 
         if (input.getArtifactCategory() == ArtifactCategory.DYNAMIC_LIBRARY) {
           PathFragment libDir = input.getArtifact().getExecPath().getParentDirectory();
@@ -1552,14 +1556,14 @@ public class CppLinkActionBuilder {
         linkArgCollector.setRpathRoot(rpathRoot);
       }
       if (includeRuntimeSolibDir) {
-        linkArgCollector.setRpathEntries(runtimeRpathEntries);
+        linkArgCollector.setRpathEntries(runtimeRpathEntries.build());
       }
 
-      linkArgCollector.setLibopts(libOpts);
+      linkArgCollector.setLibopts(libOpts.build());
 
-      linkArgCollector.setLinkerInputParams(standardArchiveInputParams);
-      linkArgCollector.setWholeArchiveLinkerInputParams(wholeArchiveInputParams);
-      linkArgCollector.setNoWholeArchiveInputs(noWholeArchiveInputs);
+      linkArgCollector.setLinkerInputParams(standardArchiveInputParams.build());
+      linkArgCollector.setWholeArchiveLinkerInputParams(wholeArchiveInputParams.build());
+      linkArgCollector.setNoWholeArchiveInputs(noWholeArchiveInputs.build());
 
       if (ltoMap != null) {
         Preconditions.checkState(ltoMap.isEmpty(), "Still have LTO objects left: %s", ltoMap);
@@ -1569,8 +1573,8 @@ public class CppLinkActionBuilder {
     /** Adds command-line options for a dynamic library input file into options and libOpts. */
     private void addDynamicInputLinkOptions(
         LinkerInput input,
-        List<String> options,
-        Set<String> libOpts,
+        ImmutableList.Builder<String> options,
+        ImmutableSet.Builder<String> libOpts,
         PathFragment solibDir,
         String rpathRoot) {
       Preconditions.checkState(input.getArtifactCategory() == ArtifactCategory.DYNAMIC_LIBRARY);
@@ -1613,7 +1617,9 @@ public class CppLinkActionBuilder {
      *     be supplied for LTO final links.
      */
     private void addStaticInputLinkOptions(
-        LinkerInput input, List<String> wholeArchiveOptions, List<String> standardOptions,
+        LinkerInput input,
+        ImmutableList.Builder<String> wholeArchiveOptions,
+        ImmutableList.Builder<String> standardOptions,
         @Nullable Map<Artifact, Artifact> ltoMap) {
       Preconditions.checkState(!(input.getArtifactCategory() == ArtifactCategory.DYNAMIC_LIBRARY));
       // If we had any LTO artifacts, ltoMap whould be non-null. In that case,
@@ -1647,8 +1653,8 @@ public class CppLinkActionBuilder {
           }
         }
       } else {
-        List<String> options = inputNeedsWholeArchive(input)
-            ? wholeArchiveOptions : standardOptions;
+        ImmutableList.Builder<String> options =
+            inputNeedsWholeArchive(input) ? wholeArchiveOptions : standardOptions;
         // For anything else, add the input directly.
         Artifact inputArtifact = input.getArtifact();
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModel.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModel.java
index f5aaae3d40..d1eadd4e1e 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModel.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppModel.java
@@ -30,7 +30,7 @@ import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.
 import com.google.devtools.build.lib.rules.cpp.CcCompilationOutputs.Builder;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.ExpansionException;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.StringSequence;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.StringSequenceBuilder;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.VariablesExtension;
 import com.google.devtools.build.lib.rules.cpp.CppCompileAction.DotdFile;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkStaticness;
@@ -341,23 +341,22 @@ public final class CppModel {
     return builder;
   }
 
-  /**
-   * Get the safe path strings for a list of paths to use in the build variables.
-   */
-  private Collection<String> getSafePathStrings(Collection<PathFragment> paths) {
+  /** Get the safe path strings for a list of paths to use in the build variables. */
+  private ImmutableList<String> getSafePathStrings(Collection<PathFragment> paths) {
     ImmutableSet.Builder<String> result = ImmutableSet.builder();
     for (PathFragment path : paths) {
       result.add(path.getSafePathString());
     }
-    return result.build();
+    return result.build().asList();
   }
 
   /**
    * Select .pcm inputs to pass on the command line depending on whether we are in pic or non-pic
    * mode.
    */
-  private Collection<String> getHeaderModulePaths(CppCompileActionBuilder builder, boolean usePic) {
-    Collection<String> result = new LinkedHashSet<>();
+  private ImmutableList<String> getHeaderModulePaths(
+      CppCompileActionBuilder builder, boolean usePic) {
+    ImmutableSet.Builder<String> result = ImmutableSet.builder();
     Iterable<Artifact> artifacts =
         featureConfiguration.isEnabled(CppRuleClasses.HEADER_MODULE_INCLUDES_DEPENDENCIES)
             ? builder.getContext().getTopLevelModules(usePic)
@@ -365,7 +364,7 @@ public final class CppModel {
     for (Artifact artifact : artifacts) {
       result.add(artifact.getExecPathString());
     }
-    return result;
+    return result.build().asList();
   }
 
   private void setupCompileBuildVariables(
@@ -387,8 +386,8 @@ public final class CppModel {
     Artifact outputFile = builder.getOutputFile();
     String realOutputFilePath;
 
-    buildVariables.addVariable("source_file", sourceFile.getExecPathString());
-    buildVariables.addVariable("output_file", outputFile.getExecPathString());
+    buildVariables.addStringVariable("source_file", sourceFile.getExecPathString());
+    buildVariables.addStringVariable("output_file", outputFile.getExecPathString());
 
     if (builder.getTempOutputFile() != null) {
       realOutputFilePath = builder.getTempOutputFile().getPathString();
@@ -397,44 +396,46 @@ public final class CppModel {
     }
 
     if (FileType.contains(outputFile, CppFileTypes.ASSEMBLER, CppFileTypes.PIC_ASSEMBLER)) {
-      buildVariables.addVariable("output_assembly_file", realOutputFilePath);
+      buildVariables.addStringVariable("output_assembly_file", realOutputFilePath);
     } else if (FileType.contains(outputFile, CppFileTypes.PREPROCESSED_C,
         CppFileTypes.PREPROCESSED_CPP, CppFileTypes.PIC_PREPROCESSED_C,
         CppFileTypes.PIC_PREPROCESSED_CPP)) {
-      buildVariables.addVariable("output_preprocess_file", realOutputFilePath);
+      buildVariables.addStringVariable("output_preprocess_file", realOutputFilePath);
     } else {
-      buildVariables.addVariable("output_object_file", realOutputFilePath);
+      buildVariables.addStringVariable("output_object_file", realOutputFilePath);
     }
 
     DotdFile dotdFile = CppFileTypes.mustProduceDotdFile(sourceFile.getPath().toString())
         ? Preconditions.checkNotNull(builder.getDotdFile()) : null;
     // Set dependency_file to enable <object>.d file generation.
     if (dotdFile != null) {
-      buildVariables.addVariable("dependency_file", dotdFile.getSafeExecPath().getPathString());
+      buildVariables.addStringVariable(
+          "dependency_file", dotdFile.getSafeExecPath().getPathString());
     }
 
     if (featureConfiguration.isEnabled(CppRuleClasses.MODULE_MAPS) && cppModuleMap != null) {
       // If the feature is enabled and cppModuleMap is null, we are about to fail during analysis
       // in any case, but don't crash.
-      buildVariables.addVariable("module_name", cppModuleMap.getName());
-      buildVariables.addVariable("module_map_file",
-          cppModuleMap.getArtifact().getExecPathString());
-      StringSequence.Builder sequence = new StringSequence.Builder();
+      buildVariables.addStringVariable("module_name", cppModuleMap.getName());
+      buildVariables.addStringVariable(
+          "module_map_file", cppModuleMap.getArtifact().getExecPathString());
+      StringSequenceBuilder sequence = new StringSequenceBuilder();
       for (Artifact artifact : builderContext.getDirectModuleMaps()) {
         sequence.addValue(artifact.getExecPathString());
       }
-      buildVariables.addSequence("dependent_module_map_files", sequence.build());
+      buildVariables.addCustomBuiltVariable("dependent_module_map_files", sequence);
     }
     if (featureConfiguration.isEnabled(CppRuleClasses.USE_HEADER_MODULES)) {
-      buildVariables.addSequenceVariable("module_files", getHeaderModulePaths(builder, usePic));
+      buildVariables.addStringSequenceVariable(
+          "module_files", getHeaderModulePaths(builder, usePic));
     }
     if (featureConfiguration.isEnabled(CppRuleClasses.INCLUDE_PATHS)) {
-      buildVariables.addSequenceVariable("include_paths",
-          getSafePathStrings(builderContext.getIncludeDirs()));
-      buildVariables.addSequenceVariable("quote_include_paths",
-          getSafePathStrings(builderContext.getQuoteIncludeDirs()));
-      buildVariables.addSequenceVariable("system_include_paths",
-          getSafePathStrings(builderContext.getSystemIncludeDirs()));
+      buildVariables.addStringSequenceVariable(
+          "include_paths", getSafePathStrings(builderContext.getIncludeDirs()));
+      buildVariables.addStringSequenceVariable(
+          "quote_include_paths", getSafePathStrings(builderContext.getQuoteIncludeDirs()));
+      buildVariables.addStringSequenceVariable(
+          "system_include_paths", getSafePathStrings(builderContext.getSystemIncludeDirs()));
     }
 
     if (featureConfiguration.isEnabled(CppRuleClasses.PREPROCESSOR_DEFINES)) {
@@ -451,14 +452,14 @@ public final class CppModel {
         defines = builderContext.getDefines();
       }
 
-      buildVariables.addSequenceVariable("preprocessor_defines", defines);
+      buildVariables.addStringSequenceVariable("preprocessor_defines", defines);
     }
 
     if (usePic) {
       if (!featureConfiguration.isEnabled(CppRuleClasses.PIC)) {
         ruleContext.ruleError("PIC compilation is requested but the toolchain does not support it");
       }
-      buildVariables.addVariable("pic", "");
+      buildVariables.addStringVariable("pic", "");
     }
 
     if (ccRelativeName != null) {
@@ -466,16 +467,16 @@ public final class CppModel {
           ruleContext, ccRelativeName, autoFdoImportPath, usePic, featureConfiguration);
     }
     if (gcnoFile != null) {
-      buildVariables.addVariable("gcov_gcno_file", gcnoFile.getExecPathString());
+      buildVariables.addStringVariable("gcov_gcno_file", gcnoFile.getExecPathString());
     }
 
     if (dwoFile != null) {
-      buildVariables.addVariable("per_object_debug_info_file", dwoFile.getExecPathString());
+      buildVariables.addStringVariable("per_object_debug_info_file", dwoFile.getExecPathString());
     }
 
-    buildVariables.addAllVariables(CppHelper.getToolchain(ruleContext).getBuildVariables());
-    
-    buildVariables.addAllVariables(sourceSpecificBuildVariables);
+    buildVariables.addAllStringVariables(CppHelper.getToolchain(ruleContext).getBuildVariables());
+
+    buildVariables.addAllStringVariables(sourceSpecificBuildVariables);
 
     for (VariablesExtension extension : variablesExtensions) {
       extension.addVariables(buildVariables);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoSupport.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoSupport.java
index 9e09b0643c..1e37bda60c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/FdoSupport.java
@@ -514,8 +514,7 @@ public class FdoSupport {
     }
 
     if (featureConfiguration.isEnabled(CppRuleClasses.FDO_INSTRUMENT)) {
-      buildVariables.addVariable("fdo_instrument_path",
-          fdoInstrument.getPathString());
+      buildVariables.addStringVariable("fdo_instrument_path", fdoInstrument.getPathString());
     }
 
     // Optimization phase
@@ -530,16 +529,16 @@ public class FdoSupport {
       builder.addMandatoryInputs(auxiliaryInputs);
       if (!Iterables.isEmpty(auxiliaryInputs)) {
         if (featureConfiguration.isEnabled(CppRuleClasses.AUTOFDO)) {
-          buildVariables.addVariable("fdo_profile_path",
-              getAutoProfilePath(fdoProfile, fdoRootExecPath).getPathString());
+          buildVariables.addStringVariable(
+              "fdo_profile_path", getAutoProfilePath(fdoProfile, fdoRootExecPath).getPathString());
         }
         if (featureConfiguration.isEnabled(CppRuleClasses.FDO_OPTIMIZE)) {
           if (fdoMode == FdoMode.LLVM_FDO) {
-            buildVariables.addVariable("fdo_profile_path",
+            buildVariables.addStringVariable(
+                "fdo_profile_path",
                 getLLVMProfilePath(fdoProfile, fdoRootExecPath).getPathString());
           } else {
-            buildVariables.addVariable("fdo_profile_path",
-                fdoRootExecPath.getPathString());
+            buildVariables.addStringVariable("fdo_profile_path", fdoRootExecPath.getPathString());
           }
         }
       }
@@ -698,8 +697,7 @@ public class FdoSupport {
       CcToolchainFeatures.Variables.Builder buildVariables
       ) {
     if (featureConfiguration.isEnabled(CppRuleClasses.FDO_INSTRUMENT)) {
-      buildVariables.addVariable("fdo_instrument_path",
-          fdoInstrument.getPathString());
+      buildVariables.addStringVariable("fdo_instrument_path", fdoInstrument.getPathString());
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/LTOBackendArtifacts.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/LTOBackendArtifacts.java
index d04c187d6c..e23176b303 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/LTOBackendArtifacts.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/LTOBackendArtifacts.java
@@ -128,12 +128,12 @@ public final class LTOBackendArtifacts {
 
     builder.setExecutable(compiler);
     Variables.Builder buildVariablesBuilder = new Variables.Builder();
-    buildVariablesBuilder.addVariable("thinlto_index", index.getExecPath().toString());
+    buildVariablesBuilder.addStringVariable("thinlto_index", index.getExecPath().toString());
     // The output from the LTO backend step is a native object file.
-    buildVariablesBuilder.addVariable(
+    buildVariablesBuilder.addStringVariable(
         "thinlto_output_object_file", objectFile.getExecPath().toString());
     // The input to the LTO backend step is the bitcode file.
-    buildVariablesBuilder.addVariable(
+    buildVariablesBuilder.addStringVariable(
         "thinlto_input_bitcode_file", bitcodeFile.getExecPath().toString());
     Variables buildVariables = buildVariablesBuilder.build();
     List<String> execArgs = new ArrayList<>();
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcVariablesExtension.java b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcVariablesExtension.java
index 851af8d32e..8d872b0493 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcVariablesExtension.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/ObjcVariablesExtension.java
@@ -28,7 +28,7 @@ import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.rules.apple.AppleConfiguration;
 import com.google.devtools.build.lib.rules.apple.Platform;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.StringSequence;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.StringSequenceBuilder;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.VariablesExtension;
 import java.util.Set;
 
@@ -121,23 +121,23 @@ class ObjcVariablesExtension implements VariablesExtension {
 
   private void addPchVariables(CcToolchainFeatures.Variables.Builder builder) {
     if (ruleContext.getPrerequisiteArtifact("pch", Mode.TARGET) != null) {
-      builder.addVariable(
+      builder.addStringVariable(
           PCH_FILE_VARIABLE_NAME,
           ruleContext.getPrerequisiteArtifact("pch", Mode.TARGET).getExecPathString());
     }
   }
 
   private void addFrameworkVariables(CcToolchainFeatures.Variables.Builder builder) {
-    StringSequence.Builder frameworkSequence = new StringSequence.Builder();
+    StringSequenceBuilder frameworkSequence = new StringSequenceBuilder();
     for (String framework :
         CompilationSupport.commonFrameworkNames(objcProvider, appleConfiguration)) {
       frameworkSequence.addValue(framework);
     }
-    builder.addSequence(FRAMEWORKS_VARIABLE_NAME, frameworkSequence.build());
+    builder.addCustomBuiltVariable(FRAMEWORKS_VARIABLE_NAME, frameworkSequence);
   }
 
   private void addModuleMapVariables(CcToolchainFeatures.Variables.Builder builder) {
-    builder.addVariable(
+    builder.addStringVariable(
         MODULES_MAPS_DIR_NAME,
         intermediateArtifacts
             .moduleMap()
@@ -145,58 +145,61 @@ class ObjcVariablesExtension implements VariablesExtension {
             .getExecPath()
             .getParentDirectory()
             .toString());
-    builder.addVariable(
+    builder.addStringVariable(
         OBJC_MODULE_CACHE_KEY,
         buildConfiguration.getGenfilesFragment() + "/" + OBJC_MODULE_CACHE_DIR_NAME);
   }
 
   private void addArchVariables(CcToolchainFeatures.Variables.Builder builder) {
     Platform platform = appleConfiguration.getSingleArchPlatform();
-    builder.addVariable(VERSION_MIN_VARIABLE_NAME,
+    builder.addStringVariable(
+        VERSION_MIN_VARIABLE_NAME,
         appleConfiguration.getMinimumOsForPlatformType(platform.getType()).toString());
   }
 
   private void addArchiveVariables(CcToolchainFeatures.Variables.Builder builder) {
-    builder.addVariable(
+    builder.addStringVariable(
         OBJ_LIST_PATH_VARIABLE_NAME,
         ObjcRuleClasses.intermediateArtifacts(ruleContext).archiveObjList().getExecPathString());
-    builder.addVariable(
+    builder.addStringVariable(
         ARCHIVE_PATH_VARIABLE_NAME, compilationArtifacts.getArchive().get().getExecPathString());
   }
 
   private void addFullyLinkArchiveVariables(CcToolchainFeatures.Variables.Builder builder) {
-    builder.addVariable(
+    builder.addStringVariable(
         FULLY_LINKED_ARCHIVE_PATH_VARIABLE_NAME, fullyLinkArchive.getExecPathString());
-    builder.addSequenceVariable(
+    builder.addStringSequenceVariable(
         OBJC_LIBRARY_EXEC_PATHS_VARIABLE_NAME,
         ImmutableList.copyOf(Artifact.toExecPaths(objcProvider.getObjcLibraries())));
-    builder.addSequenceVariable(
+    builder.addStringSequenceVariable(
         CC_LIBRARY_EXEC_PATHS_VARIABLE_NAME,
         ImmutableList.copyOf(Artifact.toExecPaths(objcProvider.getCcLibraries())));
-    builder.addSequenceVariable(
+    builder.addStringSequenceVariable(
         IMPORTED_LIBRARY_EXEC_PATHS_VARIABLE_NAME,
         ImmutableList.copyOf(Artifact.toExecPaths(objcProvider.get(IMPORTED_LIBRARY))));
   }
 
   private void addExecutableLinkVariables(CcToolchainFeatures.Variables.Builder builder) {
-    builder.addSequenceVariable(FRAMEWORK_NAMES_VARIABLE_NAME, frameworkNames);
-    builder.addSequenceVariable(
+    builder.addStringSequenceVariable(
+        FRAMEWORK_NAMES_VARIABLE_NAME, ImmutableList.copyOf(frameworkNames));
+    builder.addStringSequenceVariable(
         WEAK_FRAMEWORK_NAMES_VARIABLE_NAME,
-        SdkFramework.names(objcProvider.get(ObjcProvider.WEAK_SDK_FRAMEWORK)));
-    builder.addSequenceVariable(LIBRARY_NAMES_VARIABLE_NAME, libraryNames);
-    builder.addVariable(
+        ImmutableList.copyOf(
+            SdkFramework.names(objcProvider.get(ObjcProvider.WEAK_SDK_FRAMEWORK))));
+    builder.addStringSequenceVariable(LIBRARY_NAMES_VARIABLE_NAME, libraryNames);
+    builder.addStringVariable(
         FILELIST_VARIABLE_NAME, intermediateArtifacts.linkerObjList().getExecPathString());
-    builder.addVariable(
+    builder.addStringVariable(
         LINKED_BINARY_VARIABLE_NAME,
         ruleContext.getFragment(ObjcConfiguration.class).shouldStripBinary()
             ? intermediateArtifacts.unstrippedSingleArchitectureBinary().getExecPathString()
             : intermediateArtifacts.strippedSingleArchitectureBinary().getExecPathString());
 
-    builder.addSequenceVariable(
+    builder.addStringSequenceVariable(
         FORCE_LOAD_EXEC_PATHS_VARIABLE_NAME,
-        Artifact.toExecPaths(forceLoadArtifacts));
-    builder.addSequenceVariable(DEP_LINKOPTS_VARIABLE_NAME, objcProvider.get(LINKOPT));
-    builder.addSequenceVariable(ATTR_LINKOPTS_VARIABLE_NAME, attributeLinkopts);
+        ImmutableList.copyOf(Artifact.toExecPaths(forceLoadArtifacts)));
+    builder.addStringSequenceVariable(DEP_LINKOPTS_VARIABLE_NAME, objcProvider.get(LINKOPT));
+    builder.addStringSequenceVariable(ATTR_LINKOPTS_VARIABLE_NAME, attributeLinkopts);
   }
 
   /** A Builder for {@link ObjcVariablesExtension}. */