diff --git a/src/main/java/com/google/devtools/build/lib/rules/apple/cpp/AppleCcToolchain.java b/src/main/java/com/google/devtools/build/lib/rules/apple/cpp/AppleCcToolchain.java
index 93f1555..5d07a2b 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/apple/cpp/AppleCcToolchain.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/apple/cpp/AppleCcToolchain.java
@@ -27,7 +27,7 @@
 import com.google.devtools.build.lib.rules.apple.XcodeConfig;
 import com.google.devtools.build.lib.rules.apple.XcodeConfigProvider;
 import com.google.devtools.build.lib.rules.cpp.CcToolchain;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables;
 import java.util.LinkedHashMap;
 import java.util.Map;
 
@@ -56,7 +56,7 @@
   public static final String APPLE_SDK_PLATFORM_VALUE_KEY = "apple_sdk_platform_value";
 
   @Override
-  protected void addBuildVariables(RuleContext ruleContext, Variables.Builder variables)
+  protected void addBuildVariables(RuleContext ruleContext, CcToolchainVariables.Builder variables)
       throws RuleErrorException {
     AppleConfiguration appleConfiguration = ruleContext.getFragment(AppleConfiguration.class);
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
index 4d6cb3a..ebf00f8 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCommon.java
@@ -46,7 +46,6 @@
 import com.google.devtools.build.lib.rules.cpp.CcCompilationHelper.SourceCategory;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.CollidingProvidesException;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import com.google.devtools.build.lib.rules.cpp.CppConfiguration.DynamicMode;
 import com.google.devtools.build.lib.rules.cpp.CppConfiguration.HeadersCheckingMode;
 import com.google.devtools.build.lib.rules.cpp.FdoSupport.FdoMode;
@@ -900,7 +899,7 @@
       return null;
     }
 
-    Variables buildVariables = toolchainProvider.getBuildVariables();
+    CcToolchainVariables buildVariables = toolchainProvider.getBuildVariables();
     String toolchainCcFlags =
         Joiner.on(" ")
             .join(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java
index 0ce68ce..981152c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcCompilationHelper.java
@@ -48,8 +48,7 @@
 import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
 import com.google.devtools.build.lib.rules.cpp.CcCommon.CoptsFilter;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.VariablesExtension;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.VariablesExtension;
 import com.google.devtools.build.lib.rules.cpp.CppConfiguration.HeadersCheckingMode;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
@@ -1474,7 +1473,7 @@
     return flagsBuilder.build();
   }
 
-  private Variables setupCompileBuildVariables(
+  private CcToolchainVariables setupCompileBuildVariables(
       CppCompileActionBuilder builder,
       Label sourceLabel,
       String outputName,
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingHelper.java
index dc65052..e794eb5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcLinkingHelper.java
@@ -43,7 +43,7 @@
 import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
 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.VariablesExtension;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.VariablesExtension;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkTargetType;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkerOrArchiver;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkingMode;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchain.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchain.java
index 7e92423..ab37119 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchain.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchain.java
@@ -53,7 +53,6 @@
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.packages.License;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import com.google.devtools.build.lib.rules.cpp.CppConfiguration.Tool;
 import com.google.devtools.build.lib.rules.cpp.FdoSupport.FdoException;
 import com.google.devtools.build.lib.rules.cpp.FdoSupport.FdoMode;
@@ -844,16 +843,17 @@
   }
 
   /**
-   * Returns {@link Variables} instance with build variables that only depend on the toolchain.
+   * Returns {@link com.google.devtools.build.lib.rules.cpp.CcToolchainVariables} instance with
+   * build variables that only depend on the toolchain.
    *
    * @param ruleContext the rule context
    * @param defaultSysroot the default sysroot
    * @throws RuleErrorException if there are configuration errors making it impossible to resolve
    *     certain build variables of this toolchain
    */
-  private final Variables getBuildVariables(RuleContext ruleContext, PathFragment defaultSysroot)
-      throws RuleErrorException {
-    Variables.Builder variables = new Variables.Builder();
+  private final CcToolchainVariables getBuildVariables(
+      RuleContext ruleContext, PathFragment defaultSysroot) throws RuleErrorException {
+    CcToolchainVariables.Builder variables = new CcToolchainVariables.Builder();
 
     PathFragment sysroot = calculateSysroot(ruleContext, defaultSysroot);
     if (sysroot != null) {
@@ -866,12 +866,13 @@
   }
 
   /**
-   * Add local build variables from subclasses into {@link Variables} returned from {@link
+   * Add local build variables from subclasses into {@link
+   * com.google.devtools.build.lib.rules.cpp.CcToolchainVariables} returned from {@link
    * #getBuildVariables(RuleContext, PathFragment)}.
    *
    * <p>This method is meant to be overridden by subclasses of CcToolchain.
    */
-  protected void addBuildVariables(RuleContext ruleContext, Variables.Builder variables)
+  protected void addBuildVariables(RuleContext ruleContext, CcToolchainVariables.Builder variables)
       throws RuleErrorException {
     // To be overridden in subclasses.
   }
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 2e215f5..5091a36 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
@@ -17,7 +17,6 @@
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
 import com.google.common.base.Strings;
-import com.google.common.base.Supplier;
 import com.google.common.base.Throwables;
 import com.google.common.cache.CacheBuilder;
 import com.google.common.cache.CacheLoader;
@@ -27,15 +26,13 @@
 import com.google.common.collect.ImmutableMultimap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.Sets;
-import com.google.common.collect.Sets.SetView;
-import com.google.common.collect.Streams;
-import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.actions.Artifact.ArtifactExpander;
-import com.google.devtools.build.lib.analysis.RuleContext;
 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.CcToolchainVariables.Expandable;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.SingleVariables;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.StringChunk;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.StringValueParser;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.VisibleForSerialization;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
@@ -50,13 +47,11 @@
 import java.util.Collection;
 import java.util.HashMap;
 import java.util.HashSet;
-import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Objects;
 import java.util.Optional;
 import java.util.Set;
-import java.util.Stack;
 import java.util.concurrent.ExecutionException;
 import javax.annotation.Nullable;
 
@@ -107,228 +102,6 @@
       "Symbol %s is provided by all of the following features: %s";
 
   /**
-   * A piece of a single string value.
-   *
-   * <p>A single value can contain a combination of text and variables (for example "-f
-   * %{var1}/%{var2}"). We split the string into chunks, where each chunk represents either a text
-   * snippet, or a variable that is to be replaced.
-   */
-  interface StringChunk {
-    /**
-     * Expands this chunk.
-     *
-     * @param variables binding of variable names to their values for a single flag expansion.
-     */
-    String expand(Variables variables);
-  }
-
-  /** A plain text chunk of a string (containing no variables). */
-  @Immutable
-  @AutoCodec
-  @VisibleForSerialization
-  static class StringLiteralChunk implements StringChunk, Serializable {
-    private final String text;
-
-    @VisibleForSerialization
-    StringLiteralChunk(String text) {
-      this.text = text;
-    }
-
-    @Override
-    public String expand(Variables variables) {
-      return text;
-    }
-
-    @Override
-    public boolean equals(@Nullable Object object) {
-      if (this == object) {
-        return true;
-      }
-      if (object instanceof StringLiteralChunk) {
-        StringLiteralChunk that = (StringLiteralChunk) object;
-        return text.equals(that.text);
-      }
-      return false;
-    }
-
-    @Override
-    public int hashCode() {
-      return Objects.hash(text);
-    }
-  }
-
-  /** A chunk of a string value into which a variable should be expanded. */
-  @Immutable
-  @AutoCodec
-  static class VariableChunk implements StringChunk, Serializable {
-    private final String variableName;
-
-    @VisibleForSerialization
-    VariableChunk(String variableName) {
-      this.variableName = variableName;
-    }
-
-    @Override
-    public String expand(Variables variables) {
-      // 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.
-      return variables.getStringVariable(variableName);
-    }
-
-    @Override
-    public boolean equals(@Nullable Object object) {
-      if (this == object) {
-        return true;
-      }
-      if (object instanceof VariableChunk) {
-        VariableChunk that = (VariableChunk) object;
-        return variableName.equals(that.variableName);
-      }
-      return false;
-    }
-
-    @Override
-    public int hashCode() {
-      return Objects.hash(variableName);
-    }
-  }
-  
-  /**
-   * Parser for toolchain string values.
-   *
-   * <p>A string value contains a snippet of text supporting variable expansion. For example, a
-   * string value "-f %{var1}/%{var2}" will expand the values of the variables "var1" and "var2" in
-   * the corresponding places in the string.
-   *
-   * <p>The {@code StringValueParser} takes a string and parses it into a list of {@link
-   * StringChunk} objects, where each chunk represents either a snippet of text or a variable to be
-   * expanded. In the above example, the resulting chunks would be ["-f ", var1, "/", var2].
-   *
-   * <p>In addition to the list of chunks, the {@link StringValueParser} also provides the set of
-   * variables necessary for the expansion of this flag via {@link #getUsedVariables}.
-   *
-   * <p>To get a literal percent character, "%%" can be used in the string.
-   */
-  static class StringValueParser {
-
-    private final String value;
-    
-    /**
-     * The current position in {@value} during parsing.
-     */
-    private int current = 0;
-    
-    private final ImmutableList.Builder<StringChunk> chunks = ImmutableList.builder();
-    private final ImmutableSet.Builder<String> usedVariables = ImmutableSet.builder();
-    
-    StringValueParser(String value) throws InvalidConfigurationException {
-      this.value = value;
-      parse();
-    }
-    
-    /** @return the parsed chunks for this string. */
-    ImmutableList<StringChunk> getChunks() {
-      return chunks.build();
-    }
-    
-    /** @return all variable names needed to expand this string. */
-    ImmutableSet<String> getUsedVariables() {
-      return usedVariables.build();
-    }
-    
-    /**
-     * Parses the string.
-     * 
-     * @throws InvalidConfigurationException if there is a parsing error.
-     */
-    private void parse() throws InvalidConfigurationException {
-      while (current < value.length()) {
-        if (atVariableStart()) {
-          parseVariableChunk();
-        } else {
-          parseStringChunk();
-        }
-      }
-    }
-    
-    /**
-     * @return whether the current position is the start of a variable.
-     */
-    private boolean atVariableStart() {
-      // We parse a variable when value starts with '%', but not '%%'.
-      return value.charAt(current) == '%'
-          && (current + 1 >= value.length() || value.charAt(current + 1) != '%');
-    }
-    
-    /**
-     * Parses a chunk of text until the next '%', which indicates either an escaped literal '%'
-     * or a variable. 
-     */
-    private void parseStringChunk() {
-      int start = current;
-      // We only parse string chunks starting with '%' if they also start with '%%'.
-      // In that case, we want to have a single '%' in the string, so we start at the second
-      // character.
-      // Note that for strings like "abc%%def" this will lead to two string chunks, the first
-      // referencing the subtring "abc", and a second referencing the substring "%def".
-      if (value.charAt(current) == '%') {
-        current = current + 1;
-        start = current;
-      }
-      current = value.indexOf('%', current + 1);
-      if (current == -1) {
-        current = value.length();
-      }
-      final String text = value.substring(start, current);
-      chunks.add(new StringLiteralChunk(text));
-    }
-    
-    /**
-     * Parses a variable to be expanded.
-     * 
-     * @throws InvalidConfigurationException if there is a parsing error.
-     */
-    private void parseVariableChunk() throws InvalidConfigurationException {
-      current = current + 1;
-      if (current >= value.length() || value.charAt(current) != '{') {
-        abort("expected '{'");
-      }
-      current = current + 1;
-      if (current >= value.length() || value.charAt(current) == '}') {
-        abort("expected variable name");
-      }
-      int end = value.indexOf('}', current);
-      final String name = value.substring(current, end);
-      usedVariables.add(name);
-      chunks.add(new VariableChunk(name));
-      current = end + 1;
-    }
-    
-    /**
-     * @throws InvalidConfigurationException with the given error text, adding information about
-     * the current position in the string.
-     */
-    private void abort(String error) throws InvalidConfigurationException {
-      throw new InvalidConfigurationException("Invalid toolchain configuration: " + error
-          + " at position " + current + " while parsing a flag containing '" + value + "'");
-    }
-  }
-
-  /** A flag or flag group that can be expanded under a set of variables. */
-  interface Expandable {
-    /**
-     * Expands the current expandable under the given {@code view}, adding new flags to {@code
-     * commandLine}.
-     *
-     * <p>The {@code variables} controls which variables are visible during the expansion and allows
-     * to recursively expand nested flag groups.
-     */
-    void expand(Variables variables, @Nullable ArtifactExpander expander, List<String> commandLine);
-  }
-
-  /**
    * A single flag to be expanded under a set of variables.
    */
   @Immutable
@@ -345,7 +118,9 @@
     /** Expand this flag into a single new entry in {@code commandLine}. */
     @Override
     public void expand(
-        Variables variables, @Nullable ArtifactExpander expander, List<String> commandLine) {
+        CcToolchainVariables variables,
+        @Nullable ArtifactExpander expander,
+        List<String> commandLine) {
       StringBuilder flag = new StringBuilder();
       for (StringChunk chunk : chunks) {
         flag.append(chunk.expand(variables));
@@ -392,7 +167,7 @@
 
       @Override
       public void expand(
-          Variables variables,
+          CcToolchainVariables variables,
           @Nullable ArtifactExpander artifactExpander,
           List<String> commandLine) {
         commandLine.add(chunk.expand(variables));
@@ -439,10 +214,11 @@
     }
 
     /**
-     * Adds the key/value pair this object represents to the given map of environment variables.
-     * The value of the entry is expanded with the given {@code variables}.
+     * Adds the key/value pair this object represents to the given map of environment variables. The
+     * value of the entry is expanded with the given {@code variables}.
      */
-    public void addEnvEntry(Variables variables, ImmutableMap.Builder<String, String> envBuilder) {
+    public void addEnvEntry(
+        CcToolchainVariables variables, ImmutableMap.Builder<String, String> envBuilder) {
       StringBuilder value = new StringBuilder();
       for (StringChunk chunk : valueChunks) {
         value.append(chunk.expand(variables));
@@ -554,14 +330,16 @@
 
     @Override
     public void expand(
-        Variables variables, @Nullable ArtifactExpander expander, final List<String> commandLine) {
+        CcToolchainVariables variables,
+        @Nullable ArtifactExpander expander,
+        final List<String> commandLine) {
       if (!canBeExpanded(variables, expander)) {
         return;
       }
       if (iterateOverVariable != null) {
-        for (Variables.VariableValue variableValue :
+        for (CcToolchainVariables.VariableValue variableValue :
             variables.getSequenceVariable(iterateOverVariable, expander)) {
-          Variables nestedVariables =
+          CcToolchainVariables nestedVariables =
               new SingleVariables(variables, iterateOverVariable, variableValue);
           for (Expandable expandable : expandables) {
             expandable.expand(nestedVariables, expander, commandLine);
@@ -574,7 +352,8 @@
       }
     }
 
-    private boolean canBeExpanded(Variables variables, @Nullable ArtifactExpander expander) {
+    private boolean canBeExpanded(
+        CcToolchainVariables variables, @Nullable ArtifactExpander expander) {
       for (String variable : expandIfAllAvailable) {
         if (!variables.isAvailable(variable, expander)) {
           return false;
@@ -622,7 +401,9 @@
      * </ul>
      */
     private void expandCommandLine(
-        Variables variables, @Nullable ArtifactExpander expander, final List<String> commandLine) {
+        CcToolchainVariables variables,
+        @Nullable ArtifactExpander expander,
+        final List<String> commandLine) {
       expand(variables, expander, commandLine);
     }
 
@@ -726,7 +507,7 @@
     /** Adds the flags that apply to the given {@code action} to {@code commandLine}. */
     private void expandCommandLine(
         String action,
-        Variables variables,
+        CcToolchainVariables variables,
         Set<String> enabledFeatureNames,
         @Nullable ArtifactExpander expander,
         List<String> commandLine) {
@@ -846,12 +627,12 @@
     }
 
     /**
-     * Adds the environment key/value pairs that apply to the given {@code action} to
-     * {@code envBuilder}.
+     * Adds the environment key/value pairs that apply to the given {@code action} to {@code
+     * envBuilder}.
      */
     private void expandEnvironment(
         String action,
-        Variables variables,
+        CcToolchainVariables variables,
         Set<String> enabledFeatureNames,
         ImmutableMap.Builder<String, String> envBuilder) {
       if (!actions.contains(action)) {
@@ -939,7 +720,7 @@
     /** Adds environment variables for the given action to the provided builder. */
     private void expandEnvironment(
         String action,
-        Variables variables,
+        CcToolchainVariables variables,
         Set<String> enabledFeatureNames,
         ImmutableMap.Builder<String, String> envBuilder) {
       for (EnvSet envSet : envSets) {
@@ -950,7 +731,7 @@
     /** Adds the flags that apply to the given {@code action} to {@code commandLine}. */
     private void expandCommandLine(
         String action,
-        Variables variables,
+        CcToolchainVariables variables,
         Set<String> enabledFeatureNames,
         @Nullable ArtifactExpander expander,
         List<String> commandLine) {
@@ -1140,7 +921,7 @@
 
     /** Adds the flags that apply to this action to {@code commandLine}. */
     private void expandCommandLine(
-        Variables variables,
+        CcToolchainVariables variables,
         Set<String> enabledFeatureNames,
         @Nullable ArtifactExpander expander,
         List<String> commandLine) {
@@ -1189,8 +970,8 @@
      */
     public String getArtifactName(Map<String, String> variables) {
       StringBuilder resultBuilder = new StringBuilder();
-      Variables artifactNameVariables =
-          new Variables.Builder().addAllStringVariables(variables).build();
+      CcToolchainVariables artifactNameVariables =
+          new CcToolchainVariables.Builder().addAllStringVariables(variables).build();
       for (StringChunk chunk : chunks) {
         resultBuilder.append(chunk.expand(artifactNameVariables));
       }
@@ -1199,924 +980,6 @@
     }
   }
 
-  /**
-   * Configured build variables usable by the toolchain configuration.
-   *
-   * <p>TODO(b/32655571): Investigate cleanup once implicit iteration is not needed. Variables
-   * instance could serve as a top level View used to expand all flag_groups.
-   */
-  @SkylarkModule(
-    name = "variables",
-    documented = false,
-    category = SkylarkModuleCategory.BUILTIN,
-    doc = "Class encapsulating build variables."
-  )
-  public abstract static class Variables {
-    /** An empty variables instance. */
-    public static final Variables EMPTY = new Variables.Builder().build();
-
-    /**
-     * Retrieves a {@link StringSequence} variable named {@code variableName} from {@code variables}
-     * and converts it into a list of plain strings.
-     *
-     * <p>Throws {@link ExpansionException} when the variable is not a {@link StringSequence}.
-     */
-    public static final ImmutableList<String> toStringList(
-        CcToolchainFeatures.Variables variables, String variableName) {
-      return Streams
-          .stream(variables.getSequenceVariable(variableName))
-          .map(variable -> variable.getStringValue(variableName))
-          .collect(ImmutableList.toImmutableList());
-    }
-
-    /**
-     * Get a variable value named @param name. Supports accessing fields in structures (e.g.
-     * 'libraries_to_link.interface_libraries')
-     *
-     * @throws ExpansionException when no such variable or no such field are present, or when
-     *     accessing a field of non-structured variable
-     */
-    VariableValue getVariable(String name) {
-      return lookupVariable(name, true, null);
-    }
-
-    VariableValue getVariable(String name, @Nullable ArtifactExpander expander) {
-      return lookupVariable(name, true, expander);
-    }
-
-    /**
-     * Lookup a variable named @param name or return a reason why the variable was not found.
-     * Supports accessing fields in structures.
-     *
-     * @return Pair<VariableValue, String> returns either (variable value, null) or (null, string
-     *     reason why variable was not found)
-     */
-    private VariableValue lookupVariable(
-        String name, boolean throwOnMissingVariable, @Nullable ArtifactExpander expander) {
-      VariableValue nonStructuredVariable = getNonStructuredVariable(name);
-      if (nonStructuredVariable != null) {
-        return nonStructuredVariable;
-      }
-      VariableValue structuredVariable =
-          getStructureVariable(name, throwOnMissingVariable, expander);
-      if (structuredVariable != null) {
-        return structuredVariable;
-      } else if (throwOnMissingVariable) {
-        throw new ExpansionException(
-            String.format(
-                "Invalid toolchain configuration: Cannot find variable named '%s'.", name));
-      } else {
-        return null;
-      }
-    }
-
-    private VariableValue getStructureVariable(
-        String name, boolean throwOnMissingVariable, @Nullable ArtifactExpander expander) {
-      if (!name.contains(".")) {
-        return null;
-      }
-
-      Stack<String> fieldsToAccess = new Stack<>();
-      String structPath = name;
-      VariableValue variable;
-
-      do {
-        fieldsToAccess.push(structPath.substring(structPath.lastIndexOf('.') + 1));
-        structPath = structPath.substring(0, structPath.lastIndexOf('.'));
-        variable = getNonStructuredVariable(structPath);
-      } while (variable == null && structPath.contains("."));
-
-      if (variable == null) {
-        return null;
-      }
-
-      while (!fieldsToAccess.empty()) {
-        String field = fieldsToAccess.pop();
-        variable = variable.getFieldValue(structPath, field, expander);
-        if (variable == null) {
-          if (throwOnMissingVariable) {
-            throw new ExpansionException(
-                String.format(
-                    "Invalid toolchain configuration: Cannot expand variable '%s.%s': structure %s "
-                        + "doesn't have a field named '%s'",
-                    structPath, field, structPath, field));
-          } else {
-            return null;
-          }
-        }
-      }
-      return variable;
-    }
-
-    public String getStringVariable(String variableName) {
-      return getVariable(variableName, null).getStringValue(variableName);
-    }
-
-    public Iterable<? extends VariableValue> getSequenceVariable(String variableName) {
-      return getVariable(variableName, null).getSequenceValue(variableName);
-    }
-
-    public Iterable<? extends VariableValue> getSequenceVariable(
-        String variableName, @Nullable ArtifactExpander expander) {
-      return getVariable(variableName, expander).getSequenceValue(variableName);
-    }
-
-    /** Returns whether {@code variable} is set. */
-    boolean isAvailable(String variable) {
-      return isAvailable(variable, null);
-    }
-
-    boolean isAvailable(String variable, @Nullable ArtifactExpander expander) {
-      return lookupVariable(variable, false, expander) != null;
-    }
-
-    abstract Map<String, VariableValue> getVariablesMap();
-
-    abstract Map<String, String> getStringVariablesMap();
-
-    @Nullable
-    abstract VariableValue getNonStructuredVariable(String name);
-
-    /**
-     * Value of a build variable exposed to the CROSSTOOL used for flag expansion.
-     *
-     * <p>{@link VariableValue} represent either primitive values or an arbitrarily deeply nested
-     * recursive structures or sequences. Since there are builds with millions of values, some
-     * implementations might exist only to optimize memory usage.
-     *
-     * <p>Implementations must be immutable and without any side-effects. They will be expanded and
-     * queried multiple times.
-     */
-    interface VariableValue {
-      /**
-       * Returns string value of the variable, if the variable type can be converted to string (e.g.
-       * StringValue), or throw exception if it cannot (e.g. Sequence).
-       *
-       * @param variableName name of the variable value at hand, for better exception message.
-       */
-      String getStringValue(String variableName);
-
-      /**
-       * Returns Iterable value of the variable, if the variable type can be converted to a Iterable
-       * (e.g. Sequence), or throw exception if it cannot (e.g. StringValue).
-       *
-       * @param variableName name of the variable value at hand, for better exception message.
-       */
-      Iterable<? extends VariableValue> getSequenceValue(String variableName);
-
-      /**
-       * Returns value of the field, if the variable is of struct type or throw exception if it is
-       * not or no such field exists.
-       *
-       * @param variableName name of the variable value at hand, for better exception message.
-       */
-      VariableValue getFieldValue(String variableName, String field);
-
-      VariableValue getFieldValue(
-          String variableName, String field, @Nullable ArtifactExpander expander);
-
-      /** Returns true if the variable is truthy */
-      boolean isTruthy();
-    }
-
-    /**
-     * Adapter for {@link VariableValue} predefining error handling methods. Override {@link
-     * #getVariableTypeName()}, {@link #isTruthy()}, and one of {@link #getFieldValue(String,
-     * String)}, {@link #getSequenceValue(String)}, or {@link #getStringValue(String)}, and you'll
-     * get error handling for the other methods for free.
-     */
-    abstract static class VariableValueAdapter implements VariableValue {
-
-      /** Returns human-readable variable type name to be used in error messages. */
-      public abstract String getVariableTypeName();
-
-      @Override
-      public abstract boolean isTruthy();
-
-      @Override
-      public VariableValue getFieldValue(String variableName, String field) {
-        return getFieldValue(variableName, field, null);
-      }
-
-      @Override
-      public VariableValue getFieldValue(
-          String variableName, String field, @Nullable ArtifactExpander expander) {
-        throw new ExpansionException(
-            String.format(
-                "Invalid toolchain configuration: Cannot expand variable '%s.%s': variable '%s' is "
-                    + "%s, expected structure",
-                variableName, field, variableName, getVariableTypeName()));
-      }
-
-      @Override
-      public String getStringValue(String variableName) {
-        throw new ExpansionException(
-            String.format(
-                "Invalid toolchain configuration: Cannot expand variable '%s': expected string, "
-                    + "found %s",
-                variableName, getVariableTypeName()));
-      }
-
-      @Override
-      public Iterable<? extends VariableValue> getSequenceValue(String variableName) {
-        throw new ExpansionException(
-            String.format(
-                "Invalid toolchain configuration: Cannot expand variable '%s': expected sequence, "
-                    + "found %s",
-                variableName, getVariableTypeName()));
-      }
-    }
-
-    /** Interface for VariableValue builders */
-    public interface VariableValueBuilder {
-      VariableValue 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) {
-        Preconditions.checkArgument(value != null, "Cannot use null builder for a sequence value");
-        values.add(value.build());
-        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) {
-        Preconditions.checkArgument(
-            valueBuilder != null,
-            "Cannot use null builder to get a field value for field '%s'",
-            name);
-        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());
-      }
-    }
-
-    /**
-     * Lazily computed string sequence. Exists as a memory optimization. Make sure the {@param
-     * supplier} doesn't capture anything that shouldn't outlive analysis phase (e.g. {@link
-     * RuleContext}).
-     */
-    @AutoCodec
-    @VisibleForSerialization
-    static final class LazyStringSequence extends VariableValueAdapter {
-      private final Supplier<ImmutableList<String>> supplier;
-
-      @VisibleForSerialization
-      LazyStringSequence(Supplier<ImmutableList<String>> supplier) {
-        this.supplier = Preconditions.checkNotNull(supplier);
-      }
-
-      @Override
-      public Iterable<? extends VariableValue> getSequenceValue(String variableName) {
-        return supplier
-            .get()
-            .stream()
-            .map(flag -> new StringValue(flag))
-            .collect(ImmutableList.toImmutableList());
-      }
-
-      @Override
-      public String getVariableTypeName() {
-        return Sequence.SEQUENCE_VARIABLE_TYPE_NAME;
-      }
-
-      @Override
-      public boolean isTruthy() {
-        return !supplier.get().isEmpty();
-      }
-    }
-
-    /**
-     * 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
-    @AutoCodec
-    public static class LibraryToLinkValue extends VariableValueAdapter {
-      public static final String OBJECT_FILES_FIELD_NAME = "object_files";
-      public static final String NAME_FIELD_NAME = "name";
-      public static final String TYPE_FIELD_NAME = "type";
-      public static final String IS_WHOLE_ARCHIVE_FIELD_NAME = "is_whole_archive";
-
-      private static final String LIBRARY_TO_LINK_VARIABLE_TYPE_NAME = "structure (LibraryToLink)";
-
-      @VisibleForSerialization
-      enum Type {
-        OBJECT_FILE("object_file"),
-        OBJECT_FILE_GROUP("object_file_group"),
-        INTERFACE_LIBRARY("interface_library"),
-        STATIC_LIBRARY("static_library"),
-        DYNAMIC_LIBRARY("dynamic_library"),
-        VERSIONED_DYNAMIC_LIBRARY("versioned_dynamic_library");
-
-        private final String name;
-
-        Type(String name) {
-          this.name = name;
-        }
-      }
-
-      private final String name;
-      private final ImmutableList<Artifact> objectFiles;
-      private final boolean isWholeArchive;
-      private final Type type;
-
-      public static LibraryToLinkValue forDynamicLibrary(String name) {
-        return new LibraryToLinkValue(
-            Preconditions.checkNotNull(name), null, false, Type.DYNAMIC_LIBRARY);
-      }
-
-      public static LibraryToLinkValue forVersionedDynamicLibrary(
-          String name) {
-        return new LibraryToLinkValue(
-            Preconditions.checkNotNull(name), null, false, Type.VERSIONED_DYNAMIC_LIBRARY);
-      }
-
-      public static LibraryToLinkValue forInterfaceLibrary(String name) {
-        return new LibraryToLinkValue(
-            Preconditions.checkNotNull(name), null, false, Type.INTERFACE_LIBRARY);
-      }
-
-      public static LibraryToLinkValue forStaticLibrary(String name, boolean isWholeArchive) {
-        return new LibraryToLinkValue(
-            Preconditions.checkNotNull(name), null, isWholeArchive, Type.STATIC_LIBRARY);
-      }
-
-      public static LibraryToLinkValue forObjectFile(String name, boolean isWholeArchive) {
-        return new LibraryToLinkValue(
-            Preconditions.checkNotNull(name), null, isWholeArchive, Type.OBJECT_FILE);
-      }
-
-      public static LibraryToLinkValue forObjectFileGroup(
-          ImmutableList<Artifact> objects, boolean isWholeArchive) {
-        Preconditions.checkNotNull(objects);
-        Preconditions.checkArgument(!objects.isEmpty());
-        return new LibraryToLinkValue(null, objects, isWholeArchive, Type.OBJECT_FILE_GROUP);
-      }
-
-      @VisibleForSerialization
-      LibraryToLinkValue(
-          String name, ImmutableList<Artifact> objectFiles, boolean isWholeArchive, Type type) {
-        this.name = name;
-        this.objectFiles = objectFiles;
-        this.isWholeArchive = isWholeArchive;
-        this.type = type;
-      }
-
-      @Override
-      public VariableValue getFieldValue(
-          String variableName, String field, @Nullable ArtifactExpander expander) {
-        Preconditions.checkNotNull(field);
-        if (NAME_FIELD_NAME.equals(field) && !type.equals(Type.OBJECT_FILE_GROUP)) {
-          return new StringValue(name);
-        } else if (OBJECT_FILES_FIELD_NAME.equals(field) && type.equals(Type.OBJECT_FILE_GROUP)) {
-          ImmutableList.Builder<String> expandedObjectFiles = ImmutableList.builder();
-          for (Artifact objectFile : objectFiles) {
-            if (objectFile.isTreeArtifact() && (expander != null)) {
-              List<Artifact> artifacts = new ArrayList<>();
-              expander.expand(objectFile, artifacts);
-              expandedObjectFiles.addAll(
-                  Iterables.transform(artifacts, artifact -> artifact.getExecPathString()));
-            } else {
-              expandedObjectFiles.add(objectFile.getExecPathString());
-            }
-          }
-          return new StringSequence(expandedObjectFiles.build());
-        } else if (TYPE_FIELD_NAME.equals(field)) {
-          return new StringValue(type.name);
-        } else if (IS_WHOLE_ARCHIVE_FIELD_NAME.equals(field)) {
-          return new IntegerValue(isWholeArchive ? 1 : 0);
-        } else {
-          return null;
-        }
-      }
-
-      @Override
-      public String getVariableTypeName() {
-        return LIBRARY_TO_LINK_VARIABLE_TYPE_NAME;
-      }
-
-      @Override
-      public boolean isTruthy() {
-        return true;
-      }
-    }
-
-    /** Sequence of arbitrary VariableValue objects. */
-    @Immutable
-    @AutoCodec
-    @VisibleForSerialization
-    static final class Sequence extends VariableValueAdapter {
-      private static final String SEQUENCE_VARIABLE_TYPE_NAME = "sequence";
-
-      private final ImmutableList<VariableValue> values;
-
-      public Sequence(ImmutableList<VariableValue> values) {
-        this.values = values;
-      }
-
-      @Override
-      public Iterable<? extends VariableValue> getSequenceValue(String variableName) {
-        return values;
-      }
-
-      @Override
-      public String getVariableTypeName() {
-        return SEQUENCE_VARIABLE_TYPE_NAME;
-      }
-
-      @Override
-      public boolean isTruthy() {
-        return values.isEmpty();
-      }
-    }
-
-    /**
-     * 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
-    @AutoCodec
-    @VisibleForSerialization
-    static final class StructureSequence extends VariableValueAdapter {
-      private final ImmutableList<ImmutableMap<String, VariableValue>> values;
-
-      @VisibleForSerialization
-      StructureSequence(ImmutableList<ImmutableMap<String, VariableValue>> values) {
-        Preconditions.checkNotNull(values);
-        this.values = values;
-      }
-
-      @Override
-      public Iterable<? extends VariableValue> getSequenceValue(String variableName) {
-        final ImmutableList.Builder<VariableValue> sequences = ImmutableList.builder();
-        for (ImmutableMap<String, VariableValue> value : values) {
-          sequences.add(new StructureValue(value));
-        }
-        return sequences.build();
-      }
-
-      @Override
-      public String getVariableTypeName() {
-        return Sequence.SEQUENCE_VARIABLE_TYPE_NAME;
-      }
-
-      @Override
-      public boolean isTruthy() {
-        return !values.isEmpty();
-      }
-    }
-
-    /**
-     * A sequence of simple string values. Exists as a memory optimization - a typical build can
-     * contain millions of feature values, so getting rid of the overhead of {@code StringValue}
-     * objects significantly reduces memory overhead.
-     */
-    @Immutable
-    @AutoCodec
-    static final class StringSequence extends VariableValueAdapter {
-      private final Iterable<String> values;
-
-      public StringSequence(Iterable<String> values) {
-        Preconditions.checkNotNull(values);
-        this.values = values;
-      }
-
-      @Override
-      public Iterable<? extends VariableValue> getSequenceValue(String variableName) {
-        final ImmutableList.Builder<VariableValue> sequences = ImmutableList.builder();
-        for (String value : values) {
-          sequences.add(new StringValue(value));
-        }
-        return sequences.build();
-      }
-
-      @Override
-      public String getVariableTypeName() {
-        return Sequence.SEQUENCE_VARIABLE_TYPE_NAME;
-      }
-
-      @Override
-      public boolean isTruthy() {
-        return !Iterables.isEmpty(values);
-      }
-    }
-
-    /**
-     * Single structure value. Be careful not to create sequences of single structures, as the
-     * memory overhead is prohibitively big. Use optimized {@link StructureSequence} instead.
-     */
-    @Immutable
-    @AutoCodec
-    @VisibleForSerialization
-    static final class StructureValue extends VariableValueAdapter {
-      private static final String STRUCTURE_VARIABLE_TYPE_NAME = "structure";
-
-      private final ImmutableMap<String, VariableValue> value;
-
-      public StructureValue(ImmutableMap<String, VariableValue> value) {
-        this.value = value;
-      }
-
-      @Override
-      public VariableValue getFieldValue(
-          String variableName, String field, @Nullable ArtifactExpander expander) {
-        if (value.containsKey(field)) {
-          return value.get(field);
-        } else {
-          return null;
-        }
-      }
-
-      @Override
-      public String getVariableTypeName() {
-        return STRUCTURE_VARIABLE_TYPE_NAME;
-      }
-
-      @Override
-      public boolean isTruthy() {
-        return !value.isEmpty();
-      }
-    }
-
-    /**
-     * The leaves in the variable sequence node tree are simple string values. Note that this should
-     * never live outside of {@code expand}, as the object overhead is prohibitively expensive.
-     */
-    @Immutable
-    @AutoCodec
-    @VisibleForSerialization
-    static final class StringValue extends VariableValueAdapter {
-      private static final String STRING_VARIABLE_TYPE_NAME = "string";
-
-      private final String value;
-
-      public StringValue(String value) {
-        Preconditions.checkNotNull(value, "Cannot create StringValue from null");
-        this.value = value;
-      }
-
-      @Override
-      public String getStringValue(String variableName) {
-        return value;
-      }
-
-      @Override
-      public String getVariableTypeName() {
-        return STRING_VARIABLE_TYPE_NAME;
-      }
-
-      @Override
-      public boolean isTruthy() {
-        return !value.isEmpty();
-      }
-    }
-
-    /**
-     * The leaves in the variable sequence node tree are simple integer values. Note that this
-     * should never live outside of {@code expand}, as the object overhead is prohibitively
-     * expensive.
-     */
-    @Immutable
-    @AutoCodec
-    static final class IntegerValue extends VariableValueAdapter {
-      private static final String INTEGER_VALUE_TYPE_NAME = "integer";
-      private final int value;
-
-      public IntegerValue(int value) {
-        this.value = value;
-      }
-
-      @Override
-      public String getStringValue(String variableName) {
-        return Integer.toString(value);
-      }
-
-      @Override
-      public String getVariableTypeName() {
-        return INTEGER_VALUE_TYPE_NAME;
-      }
-
-      @Override
-      public boolean isTruthy() {
-        return value != 0;
-      }
-    }
-
-    /**
-     * Builder for {@code Variables}.
-     */
-    // TODO(b/65472725): Forbid sequences with empty string in them.
-    public static class Builder {
-      private final Map<String, VariableValue> variablesMap = new LinkedHashMap<>();
-      private final Map<String, String> stringVariablesMap = new LinkedHashMap<>();
-      private final Variables parent;
-
-      public Builder() {
-        parent = null;
-      }
-
-      public Builder(@Nullable Variables parent) {
-        this.parent = parent;
-      }
-
-      /** Add an integer variable that expands {@code name} to {@code value}. */
-      public Builder addIntegerVariable(String name, int value) {
-        variablesMap.put(name, new IntegerValue(value));
-        return this;
-      }
-
-      /** Add a string variable that expands {@code name} to {@code value}. */
-      public Builder addStringVariable(String name, String value) {
-        checkVariableNotPresentAlready(name);
-        Preconditions.checkNotNull(
-            value, "Cannot set null as a value for variable '%s'", name);
-        stringVariablesMap.put(name, value);
-        return this;
-      }
-
-      /** Overrides a variable to expands {@code name} to {@code value} instead. */
-      public Builder overrideStringVariable(String name, String value) {
-        Preconditions.checkNotNull(
-            value, "Cannot set null as a value for variable '%s'", name);
-        stringVariablesMap.put(name, value);
-        return this;
-      }
-
-      /** Overrides a variable to expands {@code name} to {@code value} instead. */
-      public Builder overrideLazyStringSequenceVariable(
-          String name, Supplier<ImmutableList<String>> supplier) {
-        Preconditions.checkNotNull(supplier, "Cannot set null as a value for variable '%s'", name);
-        variablesMap.put(name, new LazyStringSequence(supplier));
-        return this;
-      }
-
-      /**
-       * Add a sequence variable that expands {@code name} to {@code values}.
-       *
-       * <p>Accepts values as ImmutableSet. As ImmutableList has smaller memory footprint, we copy
-       * the values into a new list.
-       */
-      public Builder addStringSequenceVariable(String name, ImmutableSet<String> values) {
-        checkVariableNotPresentAlready(name);
-        Preconditions.checkNotNull(values, "Cannot set null as a value for variable '%s'", name);
-        ImmutableList.Builder<String> builder = ImmutableList.builder();
-        builder.addAll(values);
-        variablesMap.put(name, new StringSequence(builder.build()));
-        return this;
-      }
-
-      /**
-       * Add a sequence variable that expands {@code name} to {@code values}.
-       *
-       * <p>Accepts values as NestedSet. Nested set is stored directly, not cloned, not flattened.
-       */
-      public Builder addStringSequenceVariable(String name, NestedSet<String> values) {
-        checkVariableNotPresentAlready(name);
-        Preconditions.checkNotNull(values, "Cannot set null as a value for variable '%s'", name);
-        variablesMap.put(name, new StringSequence(values));
-        return this;
-      }
-
-      /**
-       * Add a sequence variable that expands {@code name} to {@code values}.
-       *
-       * <p>Accepts values as Iterable. The iterable is stored directly, not cloned, not iterated.
-       * Be mindful of memory consumption of the particular Iterable. Prefer ImmutableList, or
-       * be sure that the iterable always returns the same elements in the same order, without any
-       * side effects.
-       */
-      public Builder addStringSequenceVariable(String name, Iterable<String> values) {
-        checkVariableNotPresentAlready(name);
-        Preconditions.checkNotNull(values, "Cannot set null as a value for variable '%s'", name);
-        variablesMap.put(name, new StringSequence(values));
-        return this;
-      }
-
-      public Builder addLazyStringSequenceVariable(
-          String name, Supplier<ImmutableList<String>> supplier) {
-        checkVariableNotPresentAlready(name);
-        Preconditions.checkNotNull(supplier, "Cannot set null as a value for variable '%s'", name);
-        variablesMap.put(name, new LazyStringSequence(supplier));
-        return this;
-      }
-
-      /**
-       * Add a variable built using {@code VariableValueBuilder} api that expands {@code name} to
-       * the value returned by the {@code builder}.
-       */
-      public Builder addCustomBuiltVariable(String name, Variables.VariableValueBuilder builder) {
-        checkVariableNotPresentAlready(name);
-        Preconditions.checkNotNull(
-            builder,
-            "Cannot use null builder to get variable value for variable '%s'",
-            name);
-        variablesMap.put(name, builder.build());
-        return this;
-      }
-
-      /** Add all string variables in a map. */
-      public Builder addAllStringVariables(Map<String, String> variables) {
-        for (String name : variables.keySet()) {
-          checkVariableNotPresentAlready(name);
-        }
-        stringVariablesMap.putAll(variables);
-        return this;
-      }
-
-      private void checkVariableNotPresentAlready(String name) {
-        Preconditions.checkNotNull(name);
-        Preconditions.checkArgument(
-            !variablesMap.containsKey(name), "Cannot overwrite variable '%s'", name);
-        Preconditions.checkArgument(
-            !stringVariablesMap.containsKey(name), "Cannot overwrite variable '%s'", name);
-      }
-
-      /**
-       * Adds all variables to this builder. Cannot override already added variables. Does not add
-       * variables defined in the {@code parent} variables.
-       */
-      public Builder addAllNonTransitive(Variables variables) {
-        SetView<String> intersection =
-            Sets.intersection(variables.getVariablesMap().keySet(), variablesMap.keySet());
-        SetView<String> stringIntersection =
-            Sets.intersection(
-                variables.getStringVariablesMap().keySet(), stringVariablesMap.keySet());
-        Preconditions.checkArgument(
-            intersection.isEmpty(), "Cannot overwrite existing variables: %s", intersection);
-        Preconditions.checkArgument(
-            stringIntersection.isEmpty(),
-            "Cannot overwrite existing variables: %s", stringIntersection);
-        this.variablesMap.putAll(variables.getVariablesMap());
-        this.stringVariablesMap.putAll(variables.getStringVariablesMap());
-        return this;
-      }
-
-      /** @return a new {@link Variables} object. */
-      public Variables build() {
-        if (stringVariablesMap.isEmpty() && variablesMap.size() == 1) {
-          return new SingleVariables(
-              parent,
-              variablesMap.keySet().iterator().next(),
-              variablesMap.values().iterator().next());
-        }
-        return new MapVariables(
-            parent, ImmutableMap.copyOf(variablesMap), ImmutableMap.copyOf(stringVariablesMap));
-      }
-    }
-    
-    /**
-     * A group of extra {@code Variable} instances, packaged as logic for adding to a
-     * {@code Builder}
-     */
-    public interface VariablesExtension {
-      void addVariables(Builder builder);
-    }
-  }
-
-  @Immutable
-  @AutoCodec.VisibleForSerialization
-  @AutoCodec
-  static class MapVariables extends Variables {
-    private final ImmutableMap<String, VariableValue> variablesMap;
-    private final ImmutableMap<String, String> stringVariablesMap;
-    private final Variables parent;
-
-    @AutoCodec.Instantiator
-    @VisibleForSerialization
-    MapVariables(
-        Variables parent,
-        ImmutableMap<String, VariableValue> variablesMap,
-        ImmutableMap<String, String> stringVariablesMap) {
-      this.variablesMap = variablesMap;
-      this.stringVariablesMap = stringVariablesMap;
-      this.parent = parent;
-    }
-
-    @Override
-    Map<String, VariableValue> getVariablesMap() {
-      return variablesMap;
-    }
-
-    @Override
-    Map<String, String> getStringVariablesMap() {
-      return stringVariablesMap;
-    }
-
-    @Override
-    VariableValue getNonStructuredVariable(String name) {
-      if (variablesMap.containsKey(name)) {
-        return variablesMap.get(name);
-      }
-      if (stringVariablesMap.containsKey(name)) {
-        return new StringValue(stringVariablesMap.get(name));
-      }
-
-      if (parent != null) {
-        return parent.getNonStructuredVariable(name);
-      }
-
-      return null;
-    }
-  }
-
-  @Immutable
-  private static class SingleVariables extends Variables {
-    private final Variables parent;
-    private final String name;
-    private final VariableValue variableValue;
-
-    SingleVariables(Variables parent, String name, VariableValue variableValue) {
-      this.parent = parent;
-      this.name = name;
-      this.variableValue = variableValue;
-    }
-
-    @Override
-    Map<String, VariableValue> getVariablesMap() {
-      return ImmutableMap.of(name, variableValue);
-    }
-
-    @Override
-    Map<String, String> getStringVariablesMap() {
-      return ImmutableMap.of();
-    }
-
-    @Override
-    VariableValue getNonStructuredVariable(String name) {
-      if (this.name.equals(name)) {
-        return variableValue;
-      }
-      return parent == null ? null : parent.getNonStructuredVariable(name);
-    }
-  }
-
   /** Captures the set of enabled features and action configs for a rule. */
   @Immutable
   @AutoCodec
@@ -2178,12 +1041,12 @@
     }
 
     /** @return the command line for the given {@code action}. */
-    public List<String> getCommandLine(String action, Variables variables) {
+    public List<String> getCommandLine(String action, CcToolchainVariables variables) {
       return getCommandLine(action, variables, null);
     }
 
     public List<String> getCommandLine(
-        String action, Variables variables, @Nullable ArtifactExpander expander) {
+        String action, CcToolchainVariables variables, @Nullable ArtifactExpander expander) {
       List<String> commandLine = new ArrayList<>();
       if (actionIsConfigured(action)) {
         actionConfigByActionName
@@ -2200,12 +1063,12 @@
 
     /** @return the flags expanded for the given {@code action} in per-feature buckets. */
     public ImmutableList<Pair<String, List<String>>> getPerFeatureExpansions(
-        String action, Variables variables) {
+        String action, CcToolchainVariables variables) {
       return getPerFeatureExpansions(action, variables, null);
     }
 
     public ImmutableList<Pair<String, List<String>>> getPerFeatureExpansions(
-        String action, Variables variables, @Nullable ArtifactExpander expander) {
+        String action, CcToolchainVariables variables, @Nullable ArtifactExpander expander) {
       ImmutableList.Builder<Pair<String, List<String>>> perFeatureExpansions =
           ImmutableList.builder();
       if (actionIsConfigured(action)) {
@@ -2226,7 +1089,7 @@
 
     /** @return the environment variables (key/value pairs) for the given {@code action}. */
     public ImmutableMap<String, String> getEnvironmentVariables(
-        String action, Variables variables) {
+        String action, CcToolchainVariables variables) {
       ImmutableMap.Builder<String, String> envBuilder = ImmutableMap.builder();
       for (Feature feature : enabledFeatures) {
         feature.expandEnvironment(action, variables, enabledFeatureNames, envBuilder);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainProvider.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainProvider.java
index 66650d0..df328fb 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainProvider.java
@@ -29,7 +29,6 @@
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import com.google.devtools.build.lib.rules.cpp.CppConfiguration.Tool;
 import com.google.devtools.build.lib.rules.cpp.FdoSupport.FdoMode;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkingMode;
@@ -78,7 +77,7 @@
           CcCompilationContext.EMPTY,
           /* supportsParamFiles= */ false,
           /* supportsHeaderParsing= */ false,
-          Variables.EMPTY,
+          CcToolchainVariables.EMPTY,
           /* builtinIncludeFiles= */ ImmutableList.<Artifact>of(),
           /* coverageEnvironment= */ NestedSetBuilder.emptySet(Order.COMPILE_ORDER),
           /* linkDynamicLibraryTool= */ null,
@@ -112,7 +111,7 @@
   private final CcCompilationContext ccCompilationContext;
   private final boolean supportsParamFiles;
   private final boolean supportsHeaderParsing;
-  private final Variables buildVariables;
+  private final CcToolchainVariables buildVariables;
   private final ImmutableList<Artifact> builtinIncludeFiles;
   private final NestedSet<Pair<String, String>> coverageEnvironment;
   @Nullable private final Artifact linkDynamicLibraryTool;
@@ -150,7 +149,7 @@
       CcCompilationContext ccCompilationContext,
       boolean supportsParamFiles,
       boolean supportsHeaderParsing,
-      Variables buildVariables,
+      CcToolchainVariables buildVariables,
       ImmutableList<Artifact> builtinIncludeFiles,
       NestedSet<Pair<String, String>> coverageEnvironment,
       Artifact linkDynamicLibraryTool,
@@ -548,7 +547,7 @@
   }
 
   /** Returns build variables to be templated into the crosstool. */
-  public Variables getBuildVariables() {
+  public CcToolchainVariables getBuildVariables() {
     return buildVariables;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainVariables.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainVariables.java
new file mode 100644
index 0000000..093837c
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CcToolchainVariables.java
@@ -0,0 +1,1204 @@
+// Copyright 2018 The Bazel Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.devtools.build.lib.rules.cpp;
+
+import com.google.common.base.Preconditions;
+import com.google.common.base.Supplier;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
+import com.google.common.collect.Sets.SetView;
+import com.google.common.collect.Streams;
+import com.google.devtools.build.lib.actions.Artifact;
+import com.google.devtools.build.lib.actions.Artifact.ArtifactExpander;
+import com.google.devtools.build.lib.analysis.RuleContext;
+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.ExpansionException;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
+import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.VisibleForSerialization;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
+import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Stack;
+import javax.annotation.Nullable;
+
+/**
+ * Configured build variables usable by the toolchain configuration.
+ *
+ * <p>TODO(b/32655571): Investigate cleanup once implicit iteration is not needed. Variables
+ * instance could serve as a top level View used to expand all flag_groups.
+ */
+@SkylarkModule(
+    name = "variables",
+    documented = false,
+    category = SkylarkModuleCategory.BUILTIN,
+    doc = "Class encapsulating build variables.")
+public abstract class CcToolchainVariables {
+
+  /**
+   * A piece of a single string value.
+   *
+   * <p>A single value can contain a combination of text and variables (for example "-f
+   * %{var1}/%{var2}"). We split the string into chunks, where each chunk represents either a text
+   * snippet, or a variable that is to be replaced.
+   */
+  interface StringChunk {
+    /**
+     * Expands this chunk.
+     *
+     * @param variables binding of variable names to their values for a single flag expansion.
+     */
+    String expand(CcToolchainVariables variables);
+  }
+
+  /** A plain text chunk of a string (containing no variables). */
+  @Immutable
+  @AutoCodec
+  @VisibleForSerialization
+  static class StringLiteralChunk implements StringChunk, Serializable {
+    private final String text;
+
+    @VisibleForSerialization
+    StringLiteralChunk(String text) {
+      this.text = text;
+    }
+
+    @Override
+    public String expand(CcToolchainVariables variables) {
+      return text;
+    }
+
+    @Override
+    public boolean equals(@Nullable Object object) {
+      if (this == object) {
+        return true;
+      }
+      if (object instanceof StringLiteralChunk) {
+        StringLiteralChunk that = (StringLiteralChunk) object;
+        return text.equals(that.text);
+      }
+      return false;
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hash(text);
+    }
+  }
+
+  /** A chunk of a string value into which a variable should be expanded. */
+  @Immutable
+  @AutoCodec
+  static class VariableChunk implements StringChunk, Serializable {
+    private final String variableName;
+
+    @VisibleForSerialization
+    VariableChunk(String variableName) {
+      this.variableName = variableName;
+    }
+
+    @Override
+    public String expand(CcToolchainVariables variables) {
+      // 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.
+      return variables.getStringVariable(variableName);
+    }
+
+    @Override
+    public boolean equals(@Nullable Object object) {
+      if (this == object) {
+        return true;
+      }
+      if (object instanceof VariableChunk) {
+        VariableChunk that = (VariableChunk) object;
+        return variableName.equals(that.variableName);
+      }
+      return false;
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hash(variableName);
+    }
+  }
+
+  /**
+   * Parser for toolchain string values.
+   *
+   * <p>A string value contains a snippet of text supporting variable expansion. For example, a
+   * string value "-f %{var1}/%{var2}" will expand the values of the variables "var1" and "var2" in
+   * the corresponding places in the string.
+   *
+   * <p>The {@code StringValueParser} takes a string and parses it into a list of {@link
+   * StringChunk} objects, where each chunk represents either a snippet of text or a variable to be
+   * expanded. In the above example, the resulting chunks would be ["-f ", var1, "/", var2].
+   *
+   * <p>In addition to the list of chunks, the {@link StringValueParser} also provides the set of
+   * variables necessary for the expansion of this flag via {@link #getUsedVariables}.
+   *
+   * <p>To get a literal percent character, "%%" can be used in the string.
+   */
+  static class StringValueParser {
+
+    private final String value;
+
+    /**
+     * The current position in {@value} during parsing.
+     */
+    private int current = 0;
+
+    private final ImmutableList.Builder<StringChunk> chunks = ImmutableList.builder();
+    private final ImmutableSet.Builder<String> usedVariables = ImmutableSet.builder();
+
+    StringValueParser(String value) throws InvalidConfigurationException {
+      this.value = value;
+      parse();
+    }
+
+    /** @return the parsed chunks for this string. */
+    ImmutableList<StringChunk> getChunks() {
+      return chunks.build();
+    }
+
+    /** @return all variable names needed to expand this string. */
+    ImmutableSet<String> getUsedVariables() {
+      return usedVariables.build();
+    }
+
+    /**
+     * Parses the string.
+     *
+     * @throws InvalidConfigurationException if there is a parsing error.
+     */
+    private void parse() throws InvalidConfigurationException {
+      while (current < value.length()) {
+        if (atVariableStart()) {
+          parseVariableChunk();
+        } else {
+          parseStringChunk();
+        }
+      }
+    }
+
+    /**
+     * @return whether the current position is the start of a variable.
+     */
+    private boolean atVariableStart() {
+      // We parse a variable when value starts with '%', but not '%%'.
+      return value.charAt(current) == '%'
+          && (current + 1 >= value.length() || value.charAt(current + 1) != '%');
+    }
+
+    /**
+     * Parses a chunk of text until the next '%', which indicates either an escaped literal '%' or a
+     * variable.
+     */
+    private void parseStringChunk() {
+      int start = current;
+      // We only parse string chunks starting with '%' if they also start with '%%'.
+      // In that case, we want to have a single '%' in the string, so we start at the second
+      // character.
+      // Note that for strings like "abc%%def" this will lead to two string chunks, the first
+      // referencing the subtring "abc", and a second referencing the substring "%def".
+      if (value.charAt(current) == '%') {
+        current = current + 1;
+        start = current;
+      }
+      current = value.indexOf('%', current + 1);
+      if (current == -1) {
+        current = value.length();
+      }
+      final String text = value.substring(start, current);
+      chunks.add(new StringLiteralChunk(text));
+    }
+
+    /**
+     * Parses a variable to be expanded.
+     *
+     * @throws InvalidConfigurationException if there is a parsing error.
+     */
+    private void parseVariableChunk() throws InvalidConfigurationException {
+      current = current + 1;
+      if (current >= value.length() || value.charAt(current) != '{') {
+        abort("expected '{'");
+      }
+      current = current + 1;
+      if (current >= value.length() || value.charAt(current) == '}') {
+        abort("expected variable name");
+      }
+      int end = value.indexOf('}', current);
+      final String name = value.substring(current, end);
+      usedVariables.add(name);
+      chunks.add(new VariableChunk(name));
+      current = end + 1;
+    }
+
+    /**
+     * @throws InvalidConfigurationException with the given error text, adding information about
+     * the current position in the string.
+     */
+    private void abort(String error) throws InvalidConfigurationException {
+      throw new InvalidConfigurationException("Invalid toolchain configuration: " + error
+          + " at position " + current + " while parsing a flag containing '" + value + "'");
+    }
+  }
+
+  /** A flag or flag group that can be expanded under a set of variables. */
+  interface Expandable {
+    /**
+     * Expands the current expandable under the given {@code view}, adding new flags to {@code
+     * commandLine}.
+     *
+     * <p>The {@code variables} controls which variables are visible during the expansion and allows
+     * to recursively expand nested flag groups.
+     */
+    void expand(
+        CcToolchainVariables variables,
+        @Nullable ArtifactExpander expander,
+        List<String> commandLine);
+  }
+
+  /** An empty variables instance. */
+  public static final CcToolchainVariables EMPTY = new CcToolchainVariables.Builder().build();
+
+  /**
+   * Retrieves a {@link StringSequence} variable named {@code variableName} from {@code variables}
+   * and converts it into a list of plain strings.
+   *
+   * <p>Throws {@link ExpansionException} when the variable is not a {@link StringSequence}.
+   */
+  public static final ImmutableList<String> toStringList(
+      CcToolchainVariables variables, String variableName) {
+      return Streams
+          .stream(variables.getSequenceVariable(variableName))
+          .map(variable -> variable.getStringValue(variableName))
+          .collect(ImmutableList.toImmutableList());
+    }
+
+    /**
+     * Get a variable value named @param name. Supports accessing fields in structures (e.g.
+     * 'libraries_to_link.interface_libraries')
+     *
+     * @throws ExpansionException when no such variable or no such field are present, or when
+     *     accessing a field of non-structured variable
+     */
+    VariableValue getVariable(String name) {
+    return lookupVariable(name, /* throwOnMissingVariable= */ true, /* expander= */ null);
+    }
+
+    VariableValue getVariable(String name, @Nullable ArtifactExpander expander) {
+    return lookupVariable(name, /* throwOnMissingVariable= */ true, expander);
+    }
+
+    /**
+     * Lookup a variable named @param name or return a reason why the variable was not found.
+     * Supports accessing fields in structures.
+     *
+     * @return Pair<VariableValue, String> returns either (variable value, null) or (null, string
+     *     reason why variable was not found)
+     */
+    private VariableValue lookupVariable(
+        String name, boolean throwOnMissingVariable, @Nullable ArtifactExpander expander) {
+      VariableValue nonStructuredVariable = getNonStructuredVariable(name);
+      if (nonStructuredVariable != null) {
+        return nonStructuredVariable;
+      }
+      VariableValue structuredVariable =
+          getStructureVariable(name, throwOnMissingVariable, expander);
+      if (structuredVariable != null) {
+        return structuredVariable;
+      } else if (throwOnMissingVariable) {
+        throw new ExpansionException(
+            String.format(
+                "Invalid toolchain configuration: Cannot find variable named '%s'.", name));
+      } else {
+        return null;
+      }
+    }
+
+    private VariableValue getStructureVariable(
+        String name, boolean throwOnMissingVariable, @Nullable ArtifactExpander expander) {
+      if (!name.contains(".")) {
+        return null;
+      }
+
+      Stack<String> fieldsToAccess = new Stack<>();
+      String structPath = name;
+      VariableValue variable;
+
+      do {
+        fieldsToAccess.push(structPath.substring(structPath.lastIndexOf('.') + 1));
+        structPath = structPath.substring(0, structPath.lastIndexOf('.'));
+        variable = getNonStructuredVariable(structPath);
+      } while (variable == null && structPath.contains("."));
+
+      if (variable == null) {
+        return null;
+      }
+
+      while (!fieldsToAccess.empty()) {
+        String field = fieldsToAccess.pop();
+        variable = variable.getFieldValue(structPath, field, expander);
+        if (variable == null) {
+          if (throwOnMissingVariable) {
+            throw new ExpansionException(
+                String.format(
+                    "Invalid toolchain configuration: Cannot expand variable '%s.%s': structure %s "
+                        + "doesn't have a field named '%s'",
+                    structPath, field, structPath, field));
+          } else {
+            return null;
+          }
+        }
+      }
+      return variable;
+    }
+
+    public String getStringVariable(String variableName) {
+    return getVariable(variableName, /* expander= */ null).getStringValue(variableName);
+    }
+
+    public Iterable<? extends VariableValue> getSequenceVariable(String variableName) {
+    return getVariable(variableName, /* expander= */ null).getSequenceValue(variableName);
+    }
+
+    public Iterable<? extends VariableValue> getSequenceVariable(
+        String variableName, @Nullable ArtifactExpander expander) {
+      return getVariable(variableName, expander).getSequenceValue(variableName);
+    }
+
+    /** Returns whether {@code variable} is set. */
+    boolean isAvailable(String variable) {
+    return isAvailable(variable, /* expander= */ null);
+    }
+
+    boolean isAvailable(String variable, @Nullable ArtifactExpander expander) {
+    return lookupVariable(variable, /* throwOnMissingVariable= */ false, expander) != null;
+    }
+
+    abstract Map<String, VariableValue> getVariablesMap();
+
+    abstract Map<String, String> getStringVariablesMap();
+
+    @Nullable
+    abstract VariableValue getNonStructuredVariable(String name);
+
+    /**
+     * Value of a build variable exposed to the CROSSTOOL used for flag expansion.
+     *
+     * <p>{@link VariableValue} represent either primitive values or an arbitrarily deeply nested
+     * recursive structures or sequences. Since there are builds with millions of values, some
+     * implementations might exist only to optimize memory usage.
+     *
+     * <p>Implementations must be immutable and without any side-effects. They will be expanded and
+     * queried multiple times.
+     */
+    interface VariableValue {
+      /**
+       * Returns string value of the variable, if the variable type can be converted to string (e.g.
+       * StringValue), or throw exception if it cannot (e.g. Sequence).
+       *
+       * @param variableName name of the variable value at hand, for better exception message.
+       */
+      String getStringValue(String variableName);
+
+      /**
+       * Returns Iterable value of the variable, if the variable type can be converted to a Iterable
+       * (e.g. Sequence), or throw exception if it cannot (e.g. StringValue).
+       *
+       * @param variableName name of the variable value at hand, for better exception message.
+       */
+      Iterable<? extends VariableValue> getSequenceValue(String variableName);
+
+      /**
+       * Returns value of the field, if the variable is of struct type or throw exception if it is
+       * not or no such field exists.
+       *
+       * @param variableName name of the variable value at hand, for better exception message.
+       */
+      VariableValue getFieldValue(String variableName, String field);
+
+      VariableValue getFieldValue(
+          String variableName, String field, @Nullable ArtifactExpander expander);
+
+      /** Returns true if the variable is truthy */
+      boolean isTruthy();
+    }
+
+    /**
+     * Adapter for {@link VariableValue} predefining error handling methods. Override {@link
+     * #getVariableTypeName()}, {@link #isTruthy()}, and one of {@link #getFieldValue(String,
+     * String)}, {@link #getSequenceValue(String)}, or {@link #getStringValue(String)}, and you'll
+     * get error handling for the other methods for free.
+     */
+    abstract static class VariableValueAdapter implements VariableValue {
+
+      /** Returns human-readable variable type name to be used in error messages. */
+      public abstract String getVariableTypeName();
+
+      @Override
+      public abstract boolean isTruthy();
+
+      @Override
+      public VariableValue getFieldValue(String variableName, String field) {
+      return getFieldValue(variableName, field, /* expander= */ null);
+      }
+
+      @Override
+      public VariableValue getFieldValue(
+          String variableName, String field, @Nullable ArtifactExpander expander) {
+        throw new ExpansionException(
+            String.format(
+                "Invalid toolchain configuration: Cannot expand variable '%s.%s': variable '%s' is "
+                    + "%s, expected structure",
+                variableName, field, variableName, getVariableTypeName()));
+      }
+
+      @Override
+      public String getStringValue(String variableName) {
+        throw new ExpansionException(
+            String.format(
+                "Invalid toolchain configuration: Cannot expand variable '%s': expected string, "
+                    + "found %s",
+                variableName, getVariableTypeName()));
+      }
+
+      @Override
+      public Iterable<? extends VariableValue> getSequenceValue(String variableName) {
+        throw new ExpansionException(
+            String.format(
+                "Invalid toolchain configuration: Cannot expand variable '%s': expected sequence, "
+                    + "found %s",
+                variableName, getVariableTypeName()));
+      }
+    }
+
+    /** Interface for VariableValue builders */
+    public interface VariableValueBuilder {
+      VariableValue 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) {
+        Preconditions.checkArgument(value != null, "Cannot use null builder for a sequence value");
+        values.add(value.build());
+        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) {
+        Preconditions.checkArgument(
+            valueBuilder != null,
+            "Cannot use null builder to get a field value for field '%s'",
+            name);
+        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());
+      }
+    }
+
+    /**
+     * Lazily computed string sequence. Exists as a memory optimization. Make sure the {@param
+     * supplier} doesn't capture anything that shouldn't outlive analysis phase (e.g. {@link
+     * RuleContext}).
+     */
+    @AutoCodec
+    @VisibleForSerialization
+    static final class LazyStringSequence extends VariableValueAdapter {
+      private final Supplier<ImmutableList<String>> supplier;
+
+      @VisibleForSerialization
+      LazyStringSequence(Supplier<ImmutableList<String>> supplier) {
+        this.supplier = Preconditions.checkNotNull(supplier);
+      }
+
+      @Override
+      public Iterable<? extends VariableValue> getSequenceValue(String variableName) {
+        return supplier
+            .get()
+            .stream()
+            .map(flag -> new StringValue(flag))
+            .collect(ImmutableList.toImmutableList());
+      }
+
+      @Override
+      public String getVariableTypeName() {
+        return Sequence.SEQUENCE_VARIABLE_TYPE_NAME;
+      }
+
+      @Override
+      public boolean isTruthy() {
+        return !supplier.get().isEmpty();
+      }
+    }
+
+    /**
+     * 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
+    @AutoCodec
+    public static class LibraryToLinkValue extends VariableValueAdapter {
+      public static final String OBJECT_FILES_FIELD_NAME = "object_files";
+      public static final String NAME_FIELD_NAME = "name";
+      public static final String TYPE_FIELD_NAME = "type";
+      public static final String IS_WHOLE_ARCHIVE_FIELD_NAME = "is_whole_archive";
+
+      private static final String LIBRARY_TO_LINK_VARIABLE_TYPE_NAME = "structure (LibraryToLink)";
+
+      @VisibleForSerialization
+      enum Type {
+        OBJECT_FILE("object_file"),
+        OBJECT_FILE_GROUP("object_file_group"),
+        INTERFACE_LIBRARY("interface_library"),
+        STATIC_LIBRARY("static_library"),
+        DYNAMIC_LIBRARY("dynamic_library"),
+        VERSIONED_DYNAMIC_LIBRARY("versioned_dynamic_library");
+
+        private final String name;
+
+        Type(String name) {
+          this.name = name;
+        }
+      }
+
+      private final String name;
+      private final ImmutableList<Artifact> objectFiles;
+      private final boolean isWholeArchive;
+      private final Type type;
+
+      public static LibraryToLinkValue forDynamicLibrary(String name) {
+      return new LibraryToLinkValue(
+          Preconditions.checkNotNull(name),
+          /* objectFiles= */ null,
+          /* isWholeArchive= */ false,
+          Type.DYNAMIC_LIBRARY);
+      }
+
+      public static LibraryToLinkValue forVersionedDynamicLibrary(
+          String name) {
+      return new LibraryToLinkValue(
+          Preconditions.checkNotNull(name),
+          /* objectFiles= */ null,
+          /* isWholeArchive= */ false,
+          Type.VERSIONED_DYNAMIC_LIBRARY);
+      }
+
+      public static LibraryToLinkValue forInterfaceLibrary(String name) {
+      return new LibraryToLinkValue(
+          Preconditions.checkNotNull(name),
+          /* objectFiles= */ null,
+          /* isWholeArchive= */ false,
+          Type.INTERFACE_LIBRARY);
+      }
+
+      public static LibraryToLinkValue forStaticLibrary(String name, boolean isWholeArchive) {
+      return new LibraryToLinkValue(
+          Preconditions.checkNotNull(name),
+          /* objectFiles= */ null,
+          isWholeArchive,
+          Type.STATIC_LIBRARY);
+      }
+
+      public static LibraryToLinkValue forObjectFile(String name, boolean isWholeArchive) {
+      return new LibraryToLinkValue(
+          Preconditions.checkNotNull(name),
+          /* objectFiles= */ null,
+          isWholeArchive,
+          Type.OBJECT_FILE);
+      }
+
+      public static LibraryToLinkValue forObjectFileGroup(
+          ImmutableList<Artifact> objects, boolean isWholeArchive) {
+        Preconditions.checkNotNull(objects);
+        Preconditions.checkArgument(!objects.isEmpty());
+      return new LibraryToLinkValue(
+          /* name= */ null, objects, isWholeArchive, Type.OBJECT_FILE_GROUP);
+      }
+
+      @VisibleForSerialization
+      LibraryToLinkValue(
+          String name, ImmutableList<Artifact> objectFiles, boolean isWholeArchive, Type type) {
+        this.name = name;
+        this.objectFiles = objectFiles;
+        this.isWholeArchive = isWholeArchive;
+        this.type = type;
+      }
+
+      @Override
+      public VariableValue getFieldValue(
+          String variableName, String field, @Nullable ArtifactExpander expander) {
+        Preconditions.checkNotNull(field);
+        if (NAME_FIELD_NAME.equals(field) && !type.equals(Type.OBJECT_FILE_GROUP)) {
+          return new StringValue(name);
+        } else if (OBJECT_FILES_FIELD_NAME.equals(field) && type.equals(Type.OBJECT_FILE_GROUP)) {
+          ImmutableList.Builder<String> expandedObjectFiles = ImmutableList.builder();
+          for (Artifact objectFile : objectFiles) {
+            if (objectFile.isTreeArtifact() && (expander != null)) {
+              List<Artifact> artifacts = new ArrayList<>();
+              expander.expand(objectFile, artifacts);
+              expandedObjectFiles.addAll(
+                  Iterables.transform(artifacts, artifact -> artifact.getExecPathString()));
+            } else {
+              expandedObjectFiles.add(objectFile.getExecPathString());
+            }
+          }
+          return new StringSequence(expandedObjectFiles.build());
+        } else if (TYPE_FIELD_NAME.equals(field)) {
+          return new StringValue(type.name);
+        } else if (IS_WHOLE_ARCHIVE_FIELD_NAME.equals(field)) {
+          return new IntegerValue(isWholeArchive ? 1 : 0);
+        } else {
+          return null;
+        }
+      }
+
+      @Override
+      public String getVariableTypeName() {
+        return LIBRARY_TO_LINK_VARIABLE_TYPE_NAME;
+      }
+
+      @Override
+      public boolean isTruthy() {
+        return true;
+      }
+    }
+
+    /** Sequence of arbitrary VariableValue objects. */
+    @Immutable
+    @AutoCodec
+    @VisibleForSerialization
+    static final class Sequence extends VariableValueAdapter {
+      private static final String SEQUENCE_VARIABLE_TYPE_NAME = "sequence";
+
+      private final ImmutableList<VariableValue> values;
+
+      public Sequence(ImmutableList<VariableValue> values) {
+        this.values = values;
+      }
+
+      @Override
+      public Iterable<? extends VariableValue> getSequenceValue(String variableName) {
+        return values;
+      }
+
+      @Override
+      public String getVariableTypeName() {
+        return SEQUENCE_VARIABLE_TYPE_NAME;
+      }
+
+      @Override
+      public boolean isTruthy() {
+        return values.isEmpty();
+      }
+    }
+
+    /**
+     * 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
+    @AutoCodec
+    @VisibleForSerialization
+    static final class StructureSequence extends VariableValueAdapter {
+      private final ImmutableList<ImmutableMap<String, VariableValue>> values;
+
+      @VisibleForSerialization
+      StructureSequence(ImmutableList<ImmutableMap<String, VariableValue>> values) {
+        Preconditions.checkNotNull(values);
+        this.values = values;
+      }
+
+      @Override
+      public Iterable<? extends VariableValue> getSequenceValue(String variableName) {
+        final ImmutableList.Builder<VariableValue> sequences = ImmutableList.builder();
+        for (ImmutableMap<String, VariableValue> value : values) {
+          sequences.add(new StructureValue(value));
+        }
+        return sequences.build();
+      }
+
+      @Override
+      public String getVariableTypeName() {
+        return Sequence.SEQUENCE_VARIABLE_TYPE_NAME;
+      }
+
+      @Override
+      public boolean isTruthy() {
+        return !values.isEmpty();
+      }
+    }
+
+    /**
+     * A sequence of simple string values. Exists as a memory optimization - a typical build can
+     * contain millions of feature values, so getting rid of the overhead of {@code StringValue}
+     * objects significantly reduces memory overhead.
+     */
+    @Immutable
+    @AutoCodec
+    static final class StringSequence extends VariableValueAdapter {
+      private final Iterable<String> values;
+
+      public StringSequence(Iterable<String> values) {
+        Preconditions.checkNotNull(values);
+        this.values = values;
+      }
+
+      @Override
+      public Iterable<? extends VariableValue> getSequenceValue(String variableName) {
+        final ImmutableList.Builder<VariableValue> sequences = ImmutableList.builder();
+        for (String value : values) {
+          sequences.add(new StringValue(value));
+        }
+        return sequences.build();
+      }
+
+      @Override
+      public String getVariableTypeName() {
+        return Sequence.SEQUENCE_VARIABLE_TYPE_NAME;
+      }
+
+      @Override
+      public boolean isTruthy() {
+        return !Iterables.isEmpty(values);
+      }
+    }
+
+    /**
+     * Single structure value. Be careful not to create sequences of single structures, as the
+     * memory overhead is prohibitively big. Use optimized {@link StructureSequence} instead.
+     */
+    @Immutable
+    @AutoCodec
+    @VisibleForSerialization
+    static final class StructureValue extends VariableValueAdapter {
+      private static final String STRUCTURE_VARIABLE_TYPE_NAME = "structure";
+
+      private final ImmutableMap<String, VariableValue> value;
+
+      public StructureValue(ImmutableMap<String, VariableValue> value) {
+        this.value = value;
+      }
+
+      @Override
+      public VariableValue getFieldValue(
+          String variableName, String field, @Nullable ArtifactExpander expander) {
+        if (value.containsKey(field)) {
+          return value.get(field);
+        } else {
+          return null;
+        }
+      }
+
+      @Override
+      public String getVariableTypeName() {
+        return STRUCTURE_VARIABLE_TYPE_NAME;
+      }
+
+      @Override
+      public boolean isTruthy() {
+        return !value.isEmpty();
+      }
+    }
+
+    /**
+     * The leaves in the variable sequence node tree are simple string values. Note that this should
+     * never live outside of {@code expand}, as the object overhead is prohibitively expensive.
+     */
+    @Immutable
+    @AutoCodec
+    @VisibleForSerialization
+    static final class StringValue extends VariableValueAdapter {
+      private static final String STRING_VARIABLE_TYPE_NAME = "string";
+
+      private final String value;
+
+      public StringValue(String value) {
+        Preconditions.checkNotNull(value, "Cannot create StringValue from null");
+        this.value = value;
+      }
+
+      @Override
+      public String getStringValue(String variableName) {
+        return value;
+      }
+
+      @Override
+      public String getVariableTypeName() {
+        return STRING_VARIABLE_TYPE_NAME;
+      }
+
+      @Override
+      public boolean isTruthy() {
+        return !value.isEmpty();
+      }
+    }
+
+    /**
+     * The leaves in the variable sequence node tree are simple integer values. Note that this
+     * should never live outside of {@code expand}, as the object overhead is prohibitively
+     * expensive.
+     */
+    @Immutable
+    @AutoCodec
+    static final class IntegerValue extends VariableValueAdapter {
+      private static final String INTEGER_VALUE_TYPE_NAME = "integer";
+      private final int value;
+
+      public IntegerValue(int value) {
+        this.value = value;
+      }
+
+      @Override
+      public String getStringValue(String variableName) {
+        return Integer.toString(value);
+      }
+
+      @Override
+      public String getVariableTypeName() {
+        return INTEGER_VALUE_TYPE_NAME;
+      }
+
+      @Override
+      public boolean isTruthy() {
+        return value != 0;
+      }
+    }
+
+    /**
+     * Builder for {@code Variables}.
+     */
+    // TODO(b/65472725): Forbid sequences with empty string in them.
+    public static class Builder {
+      private final Map<String, VariableValue> variablesMap = new LinkedHashMap<>();
+      private final Map<String, String> stringVariablesMap = new LinkedHashMap<>();
+    private final CcToolchainVariables parent;
+
+      public Builder() {
+        parent = null;
+      }
+
+    public Builder(@Nullable CcToolchainVariables parent) {
+        this.parent = parent;
+      }
+
+      /** Add an integer variable that expands {@code name} to {@code value}. */
+      public Builder addIntegerVariable(String name, int value) {
+        variablesMap.put(name, new IntegerValue(value));
+        return this;
+      }
+
+      /** Add a string variable that expands {@code name} to {@code value}. */
+      public Builder addStringVariable(String name, String value) {
+        checkVariableNotPresentAlready(name);
+        Preconditions.checkNotNull(
+            value, "Cannot set null as a value for variable '%s'", name);
+        stringVariablesMap.put(name, value);
+        return this;
+      }
+
+      /** Overrides a variable to expands {@code name} to {@code value} instead. */
+      public Builder overrideStringVariable(String name, String value) {
+        Preconditions.checkNotNull(
+            value, "Cannot set null as a value for variable '%s'", name);
+        stringVariablesMap.put(name, value);
+        return this;
+      }
+
+    /** Overrides a variable to expand {@code name} to {@code value} instead. */
+    public Builder overrideLazyStringSequenceVariable(
+        String name, Supplier<ImmutableList<String>> supplier) {
+        Preconditions.checkNotNull(supplier, "Cannot set null as a value for variable '%s'", name);
+        variablesMap.put(name, new LazyStringSequence(supplier));
+        return this;
+      }
+
+      /**
+       * Add a sequence variable that expands {@code name} to {@code values}.
+       *
+       * <p>Accepts values as ImmutableSet. As ImmutableList has smaller memory footprint, we copy
+       * the values into a new list.
+       */
+      public Builder addStringSequenceVariable(String name, ImmutableSet<String> values) {
+        checkVariableNotPresentAlready(name);
+        Preconditions.checkNotNull(values, "Cannot set null as a value for variable '%s'", name);
+        ImmutableList.Builder<String> builder = ImmutableList.builder();
+        builder.addAll(values);
+        variablesMap.put(name, new StringSequence(builder.build()));
+        return this;
+      }
+
+      /**
+       * Add a sequence variable that expands {@code name} to {@code values}.
+       *
+       * <p>Accepts values as NestedSet. Nested set is stored directly, not cloned, not flattened.
+       */
+      public Builder addStringSequenceVariable(String name, NestedSet<String> values) {
+        checkVariableNotPresentAlready(name);
+        Preconditions.checkNotNull(values, "Cannot set null as a value for variable '%s'", name);
+        variablesMap.put(name, new StringSequence(values));
+        return this;
+      }
+
+      /**
+       * Add a sequence variable that expands {@code name} to {@code values}.
+       *
+       * <p>Accepts values as Iterable. The iterable is stored directly, not cloned, not iterated.
+       * Be mindful of memory consumption of the particular Iterable. Prefer ImmutableList, or
+       * be sure that the iterable always returns the same elements in the same order, without any
+       * side effects.
+       */
+      public Builder addStringSequenceVariable(String name, Iterable<String> values) {
+        checkVariableNotPresentAlready(name);
+        Preconditions.checkNotNull(values, "Cannot set null as a value for variable '%s'", name);
+        variablesMap.put(name, new StringSequence(values));
+        return this;
+      }
+
+      public Builder addLazyStringSequenceVariable(
+          String name, Supplier<ImmutableList<String>> supplier) {
+        checkVariableNotPresentAlready(name);
+        Preconditions.checkNotNull(supplier, "Cannot set null as a value for variable '%s'", name);
+        variablesMap.put(name, new LazyStringSequence(supplier));
+        return this;
+      }
+
+    /**
+     * Add a variable built using {@code VariableValueBuilder} api that expands {@code name} to the
+     * value returned by the {@code builder}.
+     */
+    public Builder addCustomBuiltVariable(
+        String name, CcToolchainVariables.VariableValueBuilder builder) {
+        checkVariableNotPresentAlready(name);
+        Preconditions.checkNotNull(
+            builder,
+            "Cannot use null builder to get variable value for variable '%s'",
+            name);
+        variablesMap.put(name, builder.build());
+        return this;
+      }
+
+      /** Add all string variables in a map. */
+      public Builder addAllStringVariables(Map<String, String> variables) {
+        for (String name : variables.keySet()) {
+          checkVariableNotPresentAlready(name);
+        }
+        stringVariablesMap.putAll(variables);
+        return this;
+      }
+
+      private void checkVariableNotPresentAlready(String name) {
+        Preconditions.checkNotNull(name);
+        Preconditions.checkArgument(
+            !variablesMap.containsKey(name), "Cannot overwrite variable '%s'", name);
+        Preconditions.checkArgument(
+            !stringVariablesMap.containsKey(name), "Cannot overwrite variable '%s'", name);
+      }
+
+    /**
+     * Adds all variables to this builder. Cannot override already added variables. Does not add
+     * variables defined in the {@code parent} variables.
+     */
+    public Builder addAllNonTransitive(CcToolchainVariables variables) {
+        SetView<String> intersection =
+            Sets.intersection(variables.getVariablesMap().keySet(), variablesMap.keySet());
+        SetView<String> stringIntersection =
+            Sets.intersection(
+                variables.getStringVariablesMap().keySet(), stringVariablesMap.keySet());
+        Preconditions.checkArgument(
+            intersection.isEmpty(), "Cannot overwrite existing variables: %s", intersection);
+        Preconditions.checkArgument(
+            stringIntersection.isEmpty(),
+            "Cannot overwrite existing variables: %s", stringIntersection);
+        this.variablesMap.putAll(variables.getVariablesMap());
+        this.stringVariablesMap.putAll(variables.getStringVariablesMap());
+        return this;
+      }
+
+    /** @return a new {@link CcToolchainVariables} object. */
+    public CcToolchainVariables build() {
+        if (stringVariablesMap.isEmpty() && variablesMap.size() == 1) {
+          return new SingleVariables(
+              parent,
+              variablesMap.keySet().iterator().next(),
+              variablesMap.values().iterator().next());
+        }
+        return new MapVariables(
+            parent, ImmutableMap.copyOf(variablesMap), ImmutableMap.copyOf(stringVariablesMap));
+      }
+    }
+    
+    /**
+     * A group of extra {@code Variable} instances, packaged as logic for adding to a
+     * {@code Builder}
+     */
+    public interface VariablesExtension {
+      void addVariables(Builder builder);
+    }
+
+  @Immutable
+  @AutoCodec.VisibleForSerialization
+  @AutoCodec
+  static class MapVariables extends CcToolchainVariables {
+    private final ImmutableMap<String, VariableValue> variablesMap;
+    private final ImmutableMap<String, String> stringVariablesMap;
+    private final CcToolchainVariables parent;
+
+    @AutoCodec.Instantiator
+    @VisibleForSerialization
+    MapVariables(
+        CcToolchainVariables parent,
+        ImmutableMap<String, VariableValue> variablesMap,
+        ImmutableMap<String, String> stringVariablesMap) {
+      this.variablesMap = variablesMap;
+      this.stringVariablesMap = stringVariablesMap;
+      this.parent = parent;
+    }
+
+    @Override
+    Map<String, VariableValue> getVariablesMap() {
+      return variablesMap;
+    }
+
+    @Override
+    Map<String, String> getStringVariablesMap() {
+      return stringVariablesMap;
+    }
+
+    @Override
+    VariableValue getNonStructuredVariable(String name) {
+      if (variablesMap.containsKey(name)) {
+        return variablesMap.get(name);
+      }
+      if (stringVariablesMap.containsKey(name)) {
+        return new StringValue(stringVariablesMap.get(name));
+      }
+
+      if (parent != null) {
+        return parent.getNonStructuredVariable(name);
+      }
+
+      return null;
+    }
+  }
+
+  @Immutable
+  static class SingleVariables extends CcToolchainVariables {
+    private final CcToolchainVariables parent;
+    private final String name;
+    private final VariableValue variableValue;
+
+    SingleVariables(CcToolchainVariables parent, String name, VariableValue variableValue) {
+      this.parent = parent;
+      this.name = name;
+      this.variableValue = variableValue;
+    }
+
+    @Override
+    Map<String, VariableValue> getVariablesMap() {
+      return ImmutableMap.of(name, variableValue);
+    }
+
+    @Override
+    Map<String, String> getStringVariablesMap() {
+      return ImmutableMap.of();
+    }
+
+    @Override
+    VariableValue getNonStructuredVariable(String name) {
+      if (this.name.equals(name)) {
+        return variableValue;
+      }
+      return parent == null ? null : parent.getNonStructuredVariable(name);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CompileBuildVariables.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CompileBuildVariables.java
index 166805d..3aa90dd 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CompileBuildVariables.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CompileBuildVariables.java
@@ -22,9 +22,8 @@
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
-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.CcToolchainVariables.StringSequenceBuilder;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.VariablesExtension;
 import com.google.devtools.build.lib.syntax.EvalException;
 import com.google.devtools.build.lib.util.FileType;
 import com.google.devtools.build.lib.vfs.PathFragment;
@@ -104,7 +103,7 @@
     this.variableName = variableName;
   }
 
-  public static Variables setupVariablesOrReportRuleError(
+  public static CcToolchainVariables setupVariablesOrReportRuleError(
       RuleContext ruleContext,
       FeatureConfiguration featureConfiguration,
       CcToolchainProvider ccToolchainProvider,
@@ -156,11 +155,11 @@
               || CppFileTypes.CLIF_INPUT_PROTO.matches(sourceFile));
     } catch (EvalException e) {
       ruleContext.ruleError(e.getMessage());
-      return Variables.EMPTY;
+      return CcToolchainVariables.EMPTY;
     }
   }
 
-  public static Variables setupVariablesOrThrowEvalException(
+  public static CcToolchainVariables setupVariablesOrThrowEvalException(
       FeatureConfiguration featureConfiguration,
       CcToolchainProvider ccToolchainProvider,
       String sourceFile,
@@ -191,8 +190,8 @@
     Preconditions.checkNotNull(quoteIncludeDirs);
     Preconditions.checkNotNull(systemIncludeDirs);
     Preconditions.checkNotNull(defines);
-    Variables.Builder buildVariables =
-        new Variables.Builder(ccToolchainProvider.getBuildVariables());
+    CcToolchainVariables.Builder buildVariables =
+        new CcToolchainVariables.Builder(ccToolchainProvider.getBuildVariables());
 
     buildVariables.addStringSequenceVariable(
         USER_COMPILE_FLAGS.getVariableName(), userCompileFlags);
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CompileCommandLine.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CompileCommandLine.java
index 2d28909..878391f 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CompileCommandLine.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CompileCommandLine.java
@@ -19,7 +19,6 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.rules.cpp.CcCommon.CoptsFilter;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import com.google.devtools.build.lib.rules.cpp.CppCompileAction.DotdFile;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.VisibleForSerialization;
@@ -35,7 +34,7 @@
   private final Artifact sourceFile;
   private final CoptsFilter coptsFilter;
   private final FeatureConfiguration featureConfiguration;
-  private final CcToolchainFeatures.Variables variables;
+  private final CcToolchainVariables variables;
   private final String actionName;
   private final DotdFile dotdFile;
 
@@ -45,7 +44,7 @@
       Artifact sourceFile,
       CoptsFilter coptsFilter,
       FeatureConfiguration featureConfiguration,
-      CcToolchainFeatures.Variables variables,
+      CcToolchainVariables variables,
       String actionName,
       DotdFile dotdFile) {
     this.sourceFile = Preconditions.checkNotNull(sourceFile);
@@ -81,8 +80,7 @@
    * @param overwrittenVariables: Variables that will overwrite original build variables. When null,
    *     unmodified original variables are used.
    */
-  protected List<String> getArguments(
-      @Nullable CcToolchainFeatures.Variables overwrittenVariables) {
+  protected List<String> getArguments(@Nullable CcToolchainVariables overwrittenVariables) {
     List<String> commandLine = new ArrayList<>();
 
     // first: The command name.
@@ -93,14 +91,12 @@
     return commandLine;
   }
 
-  public List<String> getCompilerOptions(
-      @Nullable CcToolchainFeatures.Variables overwrittenVariables) {
+  public List<String> getCompilerOptions(@Nullable CcToolchainVariables overwrittenVariables) {
     List<String> options = new ArrayList<>();
 
-    CcToolchainFeatures.Variables updatedVariables = variables;
+    CcToolchainVariables updatedVariables = variables;
     if (variables != null && overwrittenVariables != null) {
-      CcToolchainFeatures.Variables.Builder variablesBuilder =
-          new CcToolchainFeatures.Variables.Builder(variables);
+      CcToolchainVariables.Builder variablesBuilder = new CcToolchainVariables.Builder(variables);
       variablesBuilder.addAllNonTransitive(overwrittenVariables);
       updatedVariables = variablesBuilder.build();
     }
@@ -131,7 +127,7 @@
     return dotdFile;
   }
 
-  public Variables getVariables() {
+  public CcToolchainVariables getVariables() {
     return variables;
   }
 
@@ -144,7 +140,7 @@
    */
   public ImmutableList<String> getCopts() {
     if (variables.isAvailable(CompileBuildVariables.USER_COMPILE_FLAGS.getVariableName())) {
-      return Variables.toStringList(
+      return CcToolchainVariables.toStringList(
           variables, CompileBuildVariables.USER_COMPILE_FLAGS.getVariableName());
     } else {
       return ImmutableList.of();
@@ -164,7 +160,7 @@
     private final Artifact sourceFile;
     private CoptsFilter coptsFilter;
     private FeatureConfiguration featureConfiguration;
-    private CcToolchainFeatures.Variables variables = Variables.EMPTY;
+    private CcToolchainVariables variables = CcToolchainVariables.EMPTY;
     private final String actionName;
     @Nullable private final DotdFile dotdFile;
 
@@ -195,7 +191,7 @@
       return this;
     }
 
-    public Builder setVariables(Variables variables) {
+    public Builder setVariables(CcToolchainVariables variables) {
       this.variables = variables;
       return this;
     }
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 9ff24cf..d5e692f 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
@@ -220,7 +220,7 @@
   /** Used modules that are not transitively used through other topLevelModules. */
   private Iterable<Artifact> topLevelModules = null;
 
-  private CcToolchainFeatures.Variables overwrittenVariables = null;
+  private CcToolchainVariables overwrittenVariables = null;
 
   /**
    * Creates a new action to compile C/C++ source files.
@@ -260,7 +260,7 @@
       ActionOwner owner,
       NestedSet<Artifact> allInputs,
       FeatureConfiguration featureConfiguration,
-      CcToolchainFeatures.Variables variables,
+      CcToolchainVariables variables,
       Artifact sourceFile,
       boolean shouldScanIncludes,
       boolean shouldPruneModules,
@@ -371,7 +371,7 @@
       Iterable<Artifact> additionalInputs,
       Collection<Artifact> usedModules,
       Iterable<Artifact> topLevelModules,
-      CcToolchainFeatures.Variables overwrittenVariables,
+      CcToolchainVariables overwrittenVariables,
       boolean needsDotdInputPruning,
       boolean needsIncludeValidation,
       IncludeProcessing includeProcessing,
@@ -1021,16 +1021,14 @@
    * Extracts all module (.pcm) files from potentialModules and returns a Variables object where
    * their exec paths are added to the value "module_files".
    */
-  private static CcToolchainFeatures.Variables getOverwrittenVariables(
-      Iterable<Artifact> potentialModules) {
+  private static CcToolchainVariables getOverwrittenVariables(Iterable<Artifact> potentialModules) {
     ImmutableList.Builder<String> usedModulePaths = ImmutableList.builder();
     for (Artifact input : potentialModules) {
       if (input.isFileType(CppFileTypes.CPP_MODULE)) {
         usedModulePaths.add(input.getExecPathString());
       }
     }
-    CcToolchainFeatures.Variables.Builder variableBuilder =
-        new CcToolchainFeatures.Variables.Builder();
+    CcToolchainVariables.Builder variableBuilder = new CcToolchainVariables.Builder();
     variableBuilder.addStringSequenceVariable("module_files", usedModulePaths.build());
     return variableBuilder.build();
   }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
index da8bcdb..866d1a5 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionBuilder.java
@@ -32,7 +32,6 @@
 import com.google.devtools.build.lib.packages.RuleClass.ConfiguredTargetFactory.RuleErrorException;
 import com.google.devtools.build.lib.rules.cpp.CcCommon.CoptsFilter;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import com.google.devtools.build.lib.rules.cpp.CppCompileAction.DotdFile;
 import com.google.devtools.build.lib.util.FileType;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
@@ -54,7 +53,7 @@
   private final ActionOwner owner;
   private final BuildConfiguration configuration;
   private CcToolchainFeatures.FeatureConfiguration featureConfiguration;
-  private CcToolchainFeatures.Variables variables = Variables.EMPTY;
+  private CcToolchainVariables variables = CcToolchainVariables.EMPTY;
   private Artifact sourceFile;
   private final NestedSetBuilder<Artifact> mandatoryInputsBuilder;
   private Artifact optionalSourceFile;
@@ -529,16 +528,14 @@
     return this;
   }
 
-  /**
-   * Sets the feature build variables to be used for the action.
-   */
-  public CppCompileActionBuilder setVariables(CcToolchainFeatures.Variables variables) {
+  /** Sets the feature build variables to be used for the action. */
+  public CppCompileActionBuilder setVariables(CcToolchainVariables variables) {
     this.variables = variables;
     return this;
   }
 
   /** Returns the build variables to be used for the action. */
-  public CcToolchainFeatures.Variables getVariables() {
+  public CcToolchainVariables getVariables() {
     return variables;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionTemplate.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionTemplate.java
index 7cc7dc3..5592c4f 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionTemplate.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppCompileActionTemplate.java
@@ -104,8 +104,8 @@
     builder.setSourceFile(sourceTreeFileArtifact);
     builder.setOutputs(outputTreeFileArtifact, null);
 
-    CcToolchainFeatures.Variables.Builder buildVariables =
-        new CcToolchainFeatures.Variables.Builder(cppCompileActionBuilder.getVariables());
+    CcToolchainVariables.Builder buildVariables =
+        new CcToolchainVariables.Builder(cppCompileActionBuilder.getVariables());
     buildVariables.overrideStringVariable(
         "source_file", sourceTreeFileArtifact.getExecPathString());
     buildVariables.overrideStringVariable(
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppHelper.java
index eed0942..07082ad 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppHelper.java
@@ -60,7 +60,6 @@
 import com.google.devtools.build.lib.rules.cpp.CcLinkParams.Linkstamp;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Tool;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import com.google.devtools.build.lib.rules.cpp.CppConfiguration.DynamicMode;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkTargetType;
 import com.google.devtools.build.lib.shell.ShellUtils;
@@ -906,8 +905,8 @@
     Tool stripTool =
         Preconditions.checkNotNull(
             featureConfiguration.getToolForAction(CppCompileAction.STRIP_ACTION_NAME));
-    Variables variables =
-        new Variables.Builder(toolchain.getBuildVariables())
+    CcToolchainVariables variables =
+        new CcToolchainVariables.Builder(toolchain.getBuildVariables())
             .addStringVariable(
                 StripBuildVariables.OUTPUT_FILE.getVariableName(), output.getExecPathString())
             .addStringSequenceVariable(
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 40af3b8..9ec07a3 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
@@ -44,8 +44,7 @@
 import com.google.devtools.build.lib.packages.RuleErrorConsumer;
 import com.google.devtools.build.lib.rules.cpp.CcLinkParams.Linkstamp;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.VariablesExtension;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.VariablesExtension;
 import com.google.devtools.build.lib.rules.cpp.CppConfiguration.Tool;
 import com.google.devtools.build.lib.rules.cpp.CppLinkAction.Context;
 import com.google.devtools.build.lib.rules.cpp.CppLinkAction.LinkArtifactFactory;
@@ -954,7 +953,8 @@
             : null;
 
     // Add build variables necessary to template link args into the crosstool.
-    Variables.Builder buildVariablesBuilder = new Variables.Builder(toolchain.getBuildVariables());
+    CcToolchainVariables.Builder buildVariablesBuilder =
+        new CcToolchainVariables.Builder(toolchain.getBuildVariables());
     Preconditions.checkState(!isLtoIndexing || allowLtoIndexing);
     Preconditions.checkState(allowLtoIndexing || thinltoParamFile == null);
     Preconditions.checkState(allowLtoIndexing || thinltoMergedObjectFile == null);
@@ -992,7 +992,7 @@
     ImmutableSet<Artifact> expandedLinkerArtifactsNoLinkstamps =
         Sets.difference(expandedLinkerArtifacts, linkstampObjectArtifacts).immutableCopy();
 
-    Variables variables =
+    CcToolchainVariables variables =
         LinkBuildVariables.setupVariables(
             getLinkType().linkerOrArchiver().equals(LinkerOrArchiver.LINKER),
             configuration,
@@ -1020,7 +1020,7 @@
       extraVariablesExtension.addVariables(buildVariablesBuilder);
     }
 
-    Variables buildVariables = buildVariablesBuilder.build();
+    CcToolchainVariables buildVariables = buildVariablesBuilder.build();
 
     Preconditions.checkArgument(
         linkType != LinkTargetType.INTERFACE_DYNAMIC_LIBRARY,
@@ -1086,8 +1086,8 @@
             : linkoptsForVariables;
     linkCommandLineBuilder.setLinkopts(linkoptsForVariables);
 
-    Variables patchedVariables =
-        new Variables.Builder(buildVariables)
+    CcToolchainVariables patchedVariables =
+        new CcToolchainVariables.Builder(buildVariables)
             .addStringSequenceVariable(
                 LinkBuildVariables.LEGACY_LINK_FLAGS.getVariableName(),
                 getToolchainFlags(linkoptsForVariables))
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkstampCompileHelper.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkstampCompileHelper.java
index 5d23af9..67d020f 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkstampCompileHelper.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/CppLinkstampCompileHelper.java
@@ -20,7 +20,6 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.regex.Pattern;
 
@@ -125,7 +124,7 @@
         .collect(ImmutableList.toImmutableList());
   }
 
-  private static Variables getVariables(
+  private static CcToolchainVariables getVariables(
       RuleContext ruleContext,
       Artifact sourceFile,
       Artifact outputFile,
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/FakeCppCompileAction.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/FakeCppCompileAction.java
index e4f36ef..ab00b5c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/FakeCppCompileAction.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/FakeCppCompileAction.java
@@ -59,7 +59,7 @@
       ActionOwner owner,
       NestedSet<Artifact> allInputs,
       FeatureConfiguration featureConfiguration,
-      CcToolchainFeatures.Variables variables,
+      CcToolchainVariables variables,
       Artifact sourceFile,
       boolean shouldScanIncludes,
       boolean shouldPruneModules,
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 0a1223f..e10ca70 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
@@ -787,26 +787,27 @@
   }
 
   /**
-   * Adds the FDO profile output path to the variable builder.
-   * If FDO is disabled, no build variable is added.
+   * Adds the FDO profile output path to the variable builder. If FDO is disabled, no build variable
+   * is added.
    */
   @ThreadSafe
-  public void getLinkOptions(FeatureConfiguration featureConfiguration,
-      CcToolchainFeatures.Variables.Builder buildVariables
-      ) {
+  public void getLinkOptions(
+      FeatureConfiguration featureConfiguration, CcToolchainVariables.Builder buildVariables) {
     if (featureConfiguration.isEnabled(CppRuleClasses.FDO_INSTRUMENT)) {
       buildVariables.addStringVariable("fdo_instrument_path", fdoInstrument);
     }
   }
 
   /**
-   * Adds the AutoFDO profile path to the variable builder and returns the profile artifact.
-   * If AutoFDO is disabled, no build variable is added and returns null.
+   * Adds the AutoFDO profile path to the variable builder and returns the profile artifact. If
+   * AutoFDO is disabled, no build variable is added and returns null.
    */
   @ThreadSafe
-  public Artifact buildProfileForLtoBackend(FdoSupportProvider fdoSupportProvider,
+  public Artifact buildProfileForLtoBackend(
+      FdoSupportProvider fdoSupportProvider,
       FeatureConfiguration featureConfiguration,
-      CcToolchainFeatures.Variables.Builder buildVariables, RuleContext ruleContext) {
+      CcToolchainVariables.Builder buildVariables,
+      RuleContext ruleContext) {
     if (!featureConfiguration.isEnabled(CppRuleClasses.AUTOFDO)) {
       return null;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/LibrariesToLinkCollector.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/LibrariesToLinkCollector.java
index 56f361f..ad262b8 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/LibrariesToLinkCollector.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/LibrariesToLinkCollector.java
@@ -20,8 +20,8 @@
 import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.LibraryToLinkValue;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.SequenceBuilder;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.LibraryToLinkValue;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.SequenceBuilder;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkTargetType;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkingMode;
 import com.google.devtools.build.lib.util.Pair;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/LinkBuildVariables.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/LinkBuildVariables.java
index 826bf6a..34d39c3 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/LinkBuildVariables.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/LinkBuildVariables.java
@@ -18,8 +18,7 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.SequenceBuilder;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.SequenceBuilder;
 import com.google.devtools.build.lib.vfs.PathFragment;
 
 /** Enum covering all build variables we create for all various {@link CppLinkAction}. */
@@ -92,7 +91,7 @@
     return variableName;
   }
 
-  public static Variables setupVariables(
+  public static CcToolchainVariables setupVariables(
       boolean isUsingLinkerNotArchiver,
       BuildConfiguration configuration,
       Artifact outputArtifact,
@@ -113,7 +112,7 @@
       Iterable<String> runtimeLibrarySearchDirectories,
       SequenceBuilder librariesToLink,
       Iterable<String> librarySearchDirectories) {
-    Variables.Builder buildVariables = new Variables.Builder();
+    CcToolchainVariables.Builder buildVariables = new CcToolchainVariables.Builder();
 
     // symbol counting
     if (symbolCounts != null) {
diff --git a/src/main/java/com/google/devtools/build/lib/rules/cpp/LinkCommandLine.java b/src/main/java/com/google/devtools/build/lib/rules/cpp/LinkCommandLine.java
index 545dd9e..a1c037f 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/cpp/LinkCommandLine.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/cpp/LinkCommandLine.java
@@ -24,7 +24,6 @@
 import com.google.devtools.build.lib.collect.CollectionUtils;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkTargetType;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkerOrArchiver;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
@@ -44,7 +43,7 @@
 public final class LinkCommandLine extends CommandLine {
   private final String actionName;
   private final String forcedToolPath;
-  private final CcToolchainFeatures.Variables variables;
+  private final CcToolchainVariables variables;
   // The feature config can be null for tests.
   @Nullable private final FeatureConfiguration featureConfiguration;
   private final ImmutableList<Artifact> buildInfoHeaderArtifacts;
@@ -71,7 +70,7 @@
       boolean nativeDeps,
       boolean useTestOnlyFlags,
       @Nullable Artifact paramFile,
-      CcToolchainFeatures.Variables variables,
+      CcToolchainVariables variables,
       @Nullable FeatureConfiguration featureConfiguration) {
 
     this.actionName = actionName;
@@ -159,7 +158,7 @@
 
   /** Returns the build variables used to template the crosstool for this linker invocation. */
   @VisibleForTesting
-  public Variables getBuildVariables() {
+  public CcToolchainVariables getBuildVariables() {
     return this.variables;
   }
 
@@ -213,7 +212,7 @@
     private final String forcedToolPath;
     private final FeatureConfiguration featureConfiguration;
     private final String actionName;
-    private final Variables variables;
+    private final CcToolchainVariables variables;
 
     public ParamFileCommandLine(
         Artifact paramsFile,
@@ -221,7 +220,7 @@
         String forcedToolPath,
         FeatureConfiguration featureConfiguration,
         String actionName,
-        Variables variables) {
+        CcToolchainVariables variables) {
       this.paramsFile = paramsFile;
       this.linkTargetType = linkTargetType;
       this.forcedToolPath = forcedToolPath;
@@ -366,7 +365,7 @@
       FeatureConfiguration featureConfiguration,
       String actionName,
       LinkTargetType linkTargetType,
-      Variables variables) {
+      CcToolchainVariables variables) {
     List<String> argv = new ArrayList<>();
     if (forcedToolPath != null) {
       argv.add(forcedToolPath);
@@ -419,7 +418,7 @@
     private boolean nativeDeps;
     private boolean useTestOnlyFlags;
     @Nullable private Artifact paramFile;
-    private Variables variables;
+    private CcToolchainVariables variables;
     private FeatureConfiguration featureConfiguration;
 
     public Builder(RuleContext ruleContext) {
@@ -440,7 +439,7 @@
       }
       
       if (variables == null) {
-        variables = Variables.EMPTY;
+        variables = CcToolchainVariables.EMPTY;
       }
 
       String actionName = linkTargetType.getActionName();
@@ -550,8 +549,8 @@
       this.paramFile = paramFile;
       return this;
     }
-    
-    public Builder setBuildVariables(Variables variables) {
+
+    public Builder setBuildVariables(CcToolchainVariables variables) {
       this.variables = variables;
       return this;
     }
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 5aaf1c1..df6dba7 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
@@ -20,7 +20,6 @@
 import com.google.devtools.build.lib.analysis.RuleContext;
 import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import com.google.devtools.build.lib.rules.cpp.CppConfiguration.Tool;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec.VisibleForSerialization;
@@ -217,8 +216,8 @@
     PathFragment compiler = ccToolchain.getToolPathFragment(Tool.GCC);
 
     builder.setExecutable(compiler);
-    Variables.Builder buildVariablesBuilder =
-        new Variables.Builder(ccToolchain.getBuildVariables());
+    CcToolchainVariables.Builder buildVariablesBuilder =
+        new CcToolchainVariables.Builder(ccToolchain.getBuildVariables());
     if (index != null) {
       buildVariablesBuilder.addStringVariable("thinlto_index", index.getExecPath().toString());
     } else {
@@ -250,7 +249,7 @@
 
     List<String> execArgs = new ArrayList<>();
     execArgs.addAll(commandLine);
-    Variables buildVariables = buildVariablesBuilder.build();
+    CcToolchainVariables buildVariables = buildVariablesBuilder.build();
     // Feature options should go after --copt for consistency with compile actions.
     execArgs.addAll(featureConfiguration.getCommandLine("lto-backend", buildVariables));
     // If this is a PIC compile (set based on the CppConfiguration), the PIC
diff --git a/src/main/java/com/google/devtools/build/lib/rules/objc/CompilationSupport.java b/src/main/java/com/google/devtools/build/lib/rules/objc/CompilationSupport.java
index 3d93874..7ebb7aa 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/objc/CompilationSupport.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/objc/CompilationSupport.java
@@ -100,8 +100,8 @@
 import com.google.devtools.build.lib.rules.cpp.CcToolchain;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.CollidingProvidesException;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.VariablesExtension;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainProvider;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.VariablesExtension;
 import com.google.devtools.build.lib.rules.cpp.CppCompileAction;
 import com.google.devtools.build.lib.rules.cpp.CppFileTypes;
 import com.google.devtools.build.lib.rules.cpp.CppHelper;
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 6040007..f7df33f 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
@@ -27,9 +27,9 @@
 import com.google.devtools.build.lib.packages.BuildType;
 import com.google.devtools.build.lib.rules.apple.AppleConfiguration;
 import com.google.devtools.build.lib.rules.apple.ApplePlatform;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures;
-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.CcToolchainVariables;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.StringSequenceBuilder;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.VariablesExtension;
 import com.google.devtools.build.lib.vfs.FileSystemUtils;
 import java.util.Set;
 
@@ -128,7 +128,7 @@
   }
 
   @Override
-  public void addVariables(CcToolchainFeatures.Variables.Builder builder) {
+  public void addVariables(CcToolchainVariables.Builder builder) {
     addPchVariables(builder);
     addFrameworkVariables(builder);
     addModuleMapVariables(builder);
@@ -157,7 +157,7 @@
     }
   }
 
-  private void addPchVariables(CcToolchainFeatures.Variables.Builder builder) {
+  private void addPchVariables(CcToolchainVariables.Builder builder) {
     if (ruleContext.attributes().has("pch", BuildType.LABEL)
         && ruleContext.getPrerequisiteArtifact("pch", Mode.TARGET) != null) {
       builder.addStringVariable(
@@ -166,7 +166,7 @@
     }
   }
 
-  private void addFrameworkVariables(CcToolchainFeatures.Variables.Builder builder) {
+  private void addFrameworkVariables(CcToolchainVariables.Builder builder) {
     ApplePlatform applePlatform =
         buildConfiguration.getFragment(AppleConfiguration.class).getSingleArchPlatform();
     StringSequenceBuilder frameworkSequence = new StringSequenceBuilder();
@@ -177,7 +177,7 @@
     builder.addCustomBuiltVariable(FRAMEWORKS_VARIABLE_NAME, frameworkSequence);
   }
 
-  private void addModuleMapVariables(CcToolchainFeatures.Variables.Builder builder) {
+  private void addModuleMapVariables(CcToolchainVariables.Builder builder) {
     builder.addStringVariable(
         MODULES_MAPS_DIR_NAME,
         intermediateArtifacts
@@ -191,7 +191,7 @@
         buildConfiguration.getGenfilesFragment() + "/" + OBJC_MODULE_CACHE_DIR_NAME);
   }
 
-  private void addArchiveVariables(CcToolchainFeatures.Variables.Builder builder) {
+  private void addArchiveVariables(CcToolchainVariables.Builder builder) {
     builder.addStringVariable(
         OBJ_LIST_PATH_VARIABLE_NAME,
         intermediateArtifacts.archiveObjList().getExecPathString());
@@ -199,7 +199,7 @@
         ARCHIVE_PATH_VARIABLE_NAME, compilationArtifacts.getArchive().get().getExecPathString());
   }
 
-  private void addFullyLinkArchiveVariables(CcToolchainFeatures.Variables.Builder builder) {
+  private void addFullyLinkArchiveVariables(CcToolchainVariables.Builder builder) {
     builder.addStringVariable(
         FULLY_LINKED_ARCHIVE_PATH_VARIABLE_NAME, fullyLinkArchive.getExecPathString());
     builder.addStringSequenceVariable(
@@ -213,7 +213,7 @@
         Artifact.toExecPaths(objcProvider.get(IMPORTED_LIBRARY)));
   }
 
-  private void addExecutableLinkVariables(CcToolchainFeatures.Variables.Builder builder) {
+  private void addExecutableLinkVariables(CcToolchainVariables.Builder builder) {
     builder.addStringSequenceVariable(
         FRAMEWORK_NAMES_VARIABLE_NAME, frameworkNames);
     builder.addStringSequenceVariable(
@@ -235,7 +235,7 @@
     builder.addStringSequenceVariable(ATTR_LINKOPTS_VARIABLE_NAME, attributeLinkopts);
   }
 
-  private void addDsymVariables(CcToolchainFeatures.Variables.Builder builder) {
+  private void addDsymVariables(CcToolchainVariables.Builder builder) {
     builder.addStringVariable(
         DSYM_BUNDLE_ZIP_VARIABLE_NAME, dsymBundleZip.getShellEscapedExecPathString());
     builder.addStringVariable(
@@ -243,11 +243,11 @@
         FileSystemUtils.removeExtension(dsymBundleZip.getExecPath()).getPathString());
   }
 
-  private void addLinkmapVariables(CcToolchainFeatures.Variables.Builder builder) {
+  private void addLinkmapVariables(CcToolchainVariables.Builder builder) {
     builder.addStringVariable(LINKMAP_EXEC_PATH, linkmap.getExecPathString());
   }
 
-  private void addBitcodeVariables(CcToolchainFeatures.Variables.Builder builder) {
+  private void addBitcodeVariables(CcToolchainVariables.Builder builder) {
     builder.addStringVariable(
         BITCODE_SYMBOL_MAP_PATH_VARAIBLE_NAME, bitcodeSymbolMap.getExecPathString());
   }
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeaturesTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeaturesTest.java
index 82f4e74..6c04b60 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeaturesTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainFeaturesTest.java
@@ -30,14 +30,13 @@
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.ActionConfig;
 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;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.IntegerValue;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.LibraryToLinkValue;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.SequenceBuilder;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.StringSequenceBuilder;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.StructureBuilder;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.VariableValue;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.VariableValueBuilder;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.IntegerValue;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.LibraryToLinkValue;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.SequenceBuilder;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.StringSequenceBuilder;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.StructureBuilder;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.VariableValue;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.VariableValueBuilder;
 import com.google.devtools.build.lib.skyframe.serialization.AutoRegistry;
 import com.google.devtools.build.lib.skyframe.serialization.ObjectCodecs;
 import com.google.devtools.build.lib.skyframe.serialization.testutils.SerializationTester;
@@ -66,7 +65,7 @@
    * <p>If there are multiple entries with the same key, the variable will be treated as sequence
    * type.
    */
-  private Variables createVariables(String... entries) {
+  private CcToolchainVariables createVariables(String... entries) {
     if (entries.length % 2 != 0) {
       throw new IllegalArgumentException(
           "createVariables takes an even number of arguments (key/value pairs)");
@@ -75,7 +74,7 @@
     for (int i = 0; i < entries.length; i += 2) {
       entryMap.put(entries[i], entries[i + 1]);
     }
-    Variables.Builder variables = new Variables.Builder();
+    CcToolchainVariables.Builder variables = new CcToolchainVariables.Builder();
     for (String name : entryMap.keySet()) {
       Collection<String> value = entryMap.get(name);
       if (value.size() == 1) {
@@ -302,7 +301,11 @@
     return getExpansionOfFlag(value, createVariables());
   }
 
-  private List<String> getCommandLineForFlagGroups(String groups, Variables variables)
+  private String getExpansionOfFlag(String value, CcToolchainVariables variables) throws Exception {
+    return getCommandLineForFlag(value, variables).get(0);
+  }
+
+  private List<String> getCommandLineForFlagGroups(String groups, CcToolchainVariables variables)
       throws Exception {
     FeatureConfiguration configuration =
         buildFeatures(
@@ -317,14 +320,11 @@
     return configuration.getCommandLine(CppCompileAction.CPP_COMPILE, variables);
   }
 
-  private List<String> getCommandLineForFlag(String value, Variables variables) throws Exception {
+  private List<String> getCommandLineForFlag(String value, CcToolchainVariables variables)
+      throws Exception {
     return getCommandLineForFlagGroups("flag_group { flag: '" + value + "' }", variables);
   }
 
-  private String getExpansionOfFlag(String value, Variables variables) throws Exception {
-    return getCommandLineForFlag(value, variables).get(0);
-  }
-
   private String getFlagParsingError(String value) throws Exception {
     try {
       getExpansionOfFlag(value);
@@ -335,7 +335,8 @@
     }
   }
 
-  private String getFlagExpansionError(String value, Variables variables) throws Exception {
+  private String getFlagExpansionError(String value, CcToolchainVariables variables)
+      throws Exception {
     try {
       getExpansionOfFlag(value, variables);
       fail("Expected ExpansionException");
@@ -345,7 +346,7 @@
     }
   }
 
-  private String getFlagGroupsExpansionError(String flagGroups, Variables variables)
+  private String getFlagGroupsExpansionError(String flagGroups, CcToolchainVariables variables)
       throws Exception {
     try {
       getCommandLineForFlagGroups(flagGroups, variables).get(0);
@@ -371,7 +372,7 @@
     assertThat(
             getCommandLineForFlagGroups(
                 "flag_group{ iterate_over: 'v' flag: '%{v}' }",
-                new Variables.Builder()
+                new CcToolchainVariables.Builder()
                     .addStringSequenceVariable("v", ImmutableList.<String>of())
                     .build()))
         .isEmpty();
@@ -384,23 +385,24 @@
     assertThat(
             getCommandLineForFlagGroups(
                 "flag_group { iterate_over: 'lazy' flag: '-lazy-%{lazy}' }",
-                new Variables.Builder()
+                new CcToolchainVariables.Builder()
                     .addLazyStringSequenceVariable("lazy", () -> ImmutableList.of("a", "b", "c"))
                     .build()))
         .containsExactly("-lazy-a", "-lazy-b", "-lazy-c")
         .inOrder();
   }
 
-  private Variables createStructureSequenceVariables(String name, StructureBuilder... values) {
+  private CcToolchainVariables createStructureSequenceVariables(
+      String name, StructureBuilder... values) {
     SequenceBuilder builder = new SequenceBuilder();
     for (StructureBuilder value : values) {
       builder.addValue(value.build());
     }
-    return new Variables.Builder().addCustomBuiltVariable(name, builder).build();
+    return new CcToolchainVariables.Builder().addCustomBuiltVariable(name, builder).build();
   }
 
-  private Variables createStructureVariables(String name, StructureBuilder value) {
-    return new Variables.Builder().addCustomBuiltVariable(name, value).build();
+  private CcToolchainVariables createStructureVariables(String name, StructureBuilder value) {
+    return new CcToolchainVariables.Builder().addCustomBuiltVariable(name, value).build();
   }
 
   @Test
@@ -521,7 +523,7 @@
                     + "    }"
                     + "  }"
                     + "}",
-                new Variables.Builder()
+                new CcToolchainVariables.Builder()
                     .addCustomBuiltVariable(
                         "struct",
                         new StructureBuilder()
@@ -542,7 +544,7 @@
                     + "}",
                 createStructureVariables(
                     "struct",
-                    new Variables.StructureBuilder()
+                    new CcToolchainVariables.StructureBuilder()
                         .addField("foo", "fooValue")
                         .addField("bar", "barValue"))))
         .containsExactly("-AfooValue", "-BbarValue");
@@ -559,7 +561,7 @@
                     + "}",
                 createStructureVariables(
                     "struct",
-                    new Variables.StructureBuilder()
+                    new CcToolchainVariables.StructureBuilder()
                         .addField("foo", "fooValue")
                         .addField("bar", "barValue"))))
         .isEmpty();
@@ -602,7 +604,7 @@
                     + "}",
                 createStructureVariables(
                     "struct",
-                    new Variables.StructureBuilder()
+                    new CcToolchainVariables.StructureBuilder()
                         .addField("foo", "fooValue")
                         .addField("bar", "barValue"))))
         .containsExactly("-AfooValue", "-BbarValue");
@@ -618,7 +620,8 @@
                     + "  flag: '-B%{struct.bar}'"
                     + "}",
                 createStructureVariables(
-                    "struct", new Variables.StructureBuilder().addField("bar", "barValue"))))
+                    "struct",
+                    new CcToolchainVariables.StructureBuilder().addField("bar", "barValue"))))
         .isEmpty();
   }
 
@@ -636,7 +639,8 @@
                     + "  }"
                     + "}",
                 createStructureVariables(
-                    "struct", new Variables.StructureBuilder().addField("bar", "barValue"))))
+                    "struct",
+                    new CcToolchainVariables.StructureBuilder().addField("bar", "barValue"))))
         .containsExactly("-BbarValue");
   }
 
@@ -705,7 +709,7 @@
                     + "}",
                 createStructureVariables(
                     "struct",
-                    new Variables.StructureBuilder()
+                    new CcToolchainVariables.StructureBuilder()
                         .addField("bool", new IntegerValue(1))
                         .addField("foo", "fooValue")
                         .addField("bar", "barValue"))))
@@ -728,7 +732,7 @@
                     + "}",
                 createStructureVariables(
                     "struct",
-                    new Variables.StructureBuilder()
+                    new CcToolchainVariables.StructureBuilder()
                         .addField("bool", new IntegerValue(0))
                         .addField("foo", "fooValue")
                         .addField("bar", "barValue"))))
@@ -841,8 +845,8 @@
     }
   }
 
-  private Variables createNestedVariables(String name, int depth, int count) {
-    return new Variables.Builder()
+  private CcToolchainVariables createNestedVariables(String name, int depth, int count) {
+    return new CcToolchainVariables.Builder()
         .addCustomBuiltVariable(name, createNestedSequence(depth, count, ""))
         .build();
   }
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainProviderTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainProviderTest.java
index d039539..6835970 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainProviderTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CcToolchainProviderTest.java
@@ -20,7 +20,6 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import com.google.devtools.build.lib.rules.cpp.FdoSupport.FdoMode;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import org.junit.Test;
@@ -60,7 +59,7 @@
             CcCompilationContext.EMPTY,
             /* supportsParamFiles= */ false,
             /* supportsHeaderParsing= */ false,
-            Variables.EMPTY,
+            CcToolchainVariables.EMPTY,
             /* builtinIncludeFiles= */ ImmutableList.<Artifact>of(),
             /* coverageEnvironment= */ NestedSetBuilder.emptySet(Order.COMPILE_ORDER),
             /* linkDynamicLibraryTool= */ null,
@@ -97,7 +96,7 @@
             CcCompilationContext.EMPTY,
             /* supportsParamFiles= */ false,
             /* supportsHeaderParsing= */ false,
-            Variables.EMPTY,
+            CcToolchainVariables.EMPTY,
             /* builtinIncludeFiles= */ ImmutableList.<Artifact>of(),
             /* coverageEnvironment= */ NestedSetBuilder.emptySet(Order.COMPILE_ORDER),
             /* linkDynamicLibraryTool= */ null,
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CompileBuildVariablesTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CompileBuildVariablesTest.java
index 2714ef5..0e6caea 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CompileBuildVariablesTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CompileBuildVariablesTest.java
@@ -22,7 +22,6 @@
 import com.google.devtools.build.lib.actions.Artifact;
 import com.google.devtools.build.lib.analysis.util.AnalysisMock;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -48,7 +47,8 @@
   }
 
   /** Returns active build variables for a compile action of given type for given target. */
-  protected Variables getCompileBuildVariables(String label, String name) throws Exception {
+  protected CcToolchainVariables getCompileBuildVariables(String label, String name)
+      throws Exception {
     return getCppCompileAction(label, name).getCompileCommandLine().getVariables();
   }
 
@@ -57,7 +57,7 @@
     scratch.file("x/BUILD", "cc_binary(name = 'bin', srcs = ['bin.cc'])");
     scratch.file("x/bin.cc");
 
-    Variables variables = getCompileBuildVariables("//x:bin", "bin");
+    CcToolchainVariables variables = getCompileBuildVariables("//x:bin", "bin");
 
     assertThat(variables.getStringVariable(CompileBuildVariables.SOURCE_FILE.getVariableName()))
         .contains("x/bin.cc");
@@ -73,10 +73,10 @@
     scratch.file("x/BUILD", "cc_binary(name = 'bin', srcs = ['bin.cc'])");
     scratch.file("x/bin.cc");
 
-    Variables variables = getCompileBuildVariables("//x:bin", "bin");
+    CcToolchainVariables variables = getCompileBuildVariables("//x:bin", "bin");
 
     ImmutableList<String> copts =
-        Variables.toStringList(
+        CcToolchainVariables.toStringList(
             variables, CompileBuildVariables.LEGACY_COMPILE_FLAGS.getVariableName());
     assertThat(copts).contains("-foo");
   }
@@ -89,15 +89,15 @@
     scratch.file("x/BUILD", "cc_binary(name = 'bin', srcs = ['bin.cc'], copts = ['-bar'],)");
     scratch.file("x/bin.cc");
 
-    Variables variables = getCompileBuildVariables("//x:bin", "bin");
+    CcToolchainVariables variables = getCompileBuildVariables("//x:bin", "bin");
 
     ImmutableList<String> userCopts =
-        Variables.toStringList(
+        CcToolchainVariables.toStringList(
             variables, CompileBuildVariables.USER_COMPILE_FLAGS.getVariableName());
     assertThat(userCopts).containsAllIn(ImmutableList.<String>of("-foo", "-bar")).inOrder();
 
     ImmutableList<String> legacyCopts =
-        Variables.toStringList(
+        CcToolchainVariables.toStringList(
             variables, CompileBuildVariables.LEGACY_COMPILE_FLAGS.getVariableName());
     assertThat(legacyCopts).doesNotContain("-foo");
   }
@@ -110,10 +110,10 @@
     scratch.file("x/BUILD", "cc_binary(name = 'bin', srcs = ['bin.cc'], copts = ['-foo'])");
     scratch.file("x/bin.cc");
 
-    Variables variables = getCompileBuildVariables("//x:bin", "bin");
+    CcToolchainVariables variables = getCompileBuildVariables("//x:bin", "bin");
 
     ImmutableList<String> copts =
-        Variables.toStringList(
+        CcToolchainVariables.toStringList(
             variables, CompileBuildVariables.USER_COMPILE_FLAGS.getVariableName());
     assertThat(copts).contains("-foo");
   }
@@ -128,10 +128,10 @@
     scratch.file("x/BUILD", "cc_binary(name = 'bin', srcs = ['bin.cc'])");
     scratch.file("x/bin.cc");
 
-    Variables variables = getCompileBuildVariables("//x:bin", "bin");
+    CcToolchainVariables variables = getCompileBuildVariables("//x:bin", "bin");
 
     ImmutableList<String> unfilteredCompileFlags =
-        Variables.toStringList(
+        CcToolchainVariables.toStringList(
             variables, CompileBuildVariables.UNFILTERED_COMPILE_FLAGS.getVariableName());
     assertThat(unfilteredCompileFlags).contains("--i_ll_live_forever");
   }
@@ -142,10 +142,10 @@
     scratch.file("x/bin.cc");
     useConfiguration("--per_file_copt=//x:bin@-foo", "--per_file_copt=//x:bar\\.cc@-bar");
 
-    Variables variables = getCompileBuildVariables("//x:bin", "bin");
+    CcToolchainVariables variables = getCompileBuildVariables("//x:bin", "bin");
 
     ImmutableList<String> copts =
-        Variables.toStringList(
+        CcToolchainVariables.toStringList(
             variables, CompileBuildVariables.USER_COMPILE_FLAGS.getVariableName());
     assertThat(copts).containsExactly("-foo").inOrder();
   }
@@ -160,7 +160,7 @@
     scratch.file("x/BUILD", "cc_binary(name = 'bin', srcs = ['bin.cc'])");
     scratch.file("x/bin.cc");
 
-    Variables variables = getCompileBuildVariables("//x:bin", "bin");
+    CcToolchainVariables variables = getCompileBuildVariables("//x:bin", "bin");
 
     assertThat(variables.getStringVariable(CcCommon.SYSROOT_VARIABLE_NAME))
         .isEqualTo("/usr/local/custom-sysroot");
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java
index 42673d9..8aaefcc 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/CppLinkActionTest.java
@@ -46,7 +46,7 @@
 import com.google.devtools.build.lib.collect.nestedset.Order;
 import com.google.devtools.build.lib.packages.util.MockCcSupport;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.VariableValue;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.VariableValue;
 import com.google.devtools.build.lib.rules.cpp.CppActionConfigs.CppPlatform;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkTargetType;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkerOrArchiver;
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/LinkBuildVariablesTest.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/LinkBuildVariablesTest.java
index 1eed5db..bc463b0 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/LinkBuildVariablesTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/LinkBuildVariablesTest.java
@@ -22,9 +22,8 @@
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.util.AnalysisMock;
 import com.google.devtools.build.lib.packages.util.MockCcSupport;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.LibraryToLinkValue;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables.VariableValue;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.LibraryToLinkValue;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables.VariableValue;
 import com.google.devtools.build.lib.rules.cpp.Link.LinkTargetType;
 import com.google.devtools.build.lib.util.OsUtils;
 import java.util.List;
@@ -43,7 +42,7 @@
     scratch.file("x/a.cc");
 
     ConfiguredTarget target = getConfiguredTarget("//x:bin");
-    Variables variables = getLinkBuildVariables(target, Link.LinkTargetType.EXECUTABLE);
+    CcToolchainVariables variables = getLinkBuildVariables(target, Link.LinkTargetType.EXECUTABLE);
     String variableValue =
         getVariableValue(variables, LinkBuildVariables.FORCE_PIC.getVariableName());
     assertThat(variableValue).contains("");
@@ -58,7 +57,8 @@
     scratch.file("x/a.cc");
 
     ConfiguredTarget target = getConfiguredTarget("//x:foo");
-    Variables variables = getLinkBuildVariables(target, LinkTargetType.NODEPS_DYNAMIC_LIBRARY);
+    CcToolchainVariables variables =
+        getLinkBuildVariables(target, LinkTargetType.NODEPS_DYNAMIC_LIBRARY);
     VariableValue librariesToLinkSequence =
         variables.getVariable(LinkBuildVariables.LIBRARIES_TO_LINK.getVariableName());
     assertThat(librariesToLinkSequence).isNotNull();
@@ -87,7 +87,7 @@
     scratch.file("x/some-dir/bar.so");
 
     ConfiguredTarget target = getConfiguredTarget("//x:bin");
-    Variables variables = getLinkBuildVariables(target, Link.LinkTargetType.EXECUTABLE);
+    CcToolchainVariables variables = getLinkBuildVariables(target, Link.LinkTargetType.EXECUTABLE);
     List<String> variableValue =
         getSequenceVariableValue(
             variables, LinkBuildVariables.LIBRARY_SEARCH_DIRECTORIES.getVariableName());
@@ -103,7 +103,7 @@
     scratch.file("x/some-dir/bar.so");
 
     ConfiguredTarget target = getConfiguredTarget("//x:bin");
-    Variables variables = getLinkBuildVariables(target, Link.LinkTargetType.EXECUTABLE);
+    CcToolchainVariables variables = getLinkBuildVariables(target, Link.LinkTargetType.EXECUTABLE);
     String variableValue =
         getVariableValue(variables, LinkBuildVariables.LINKER_PARAM_FILE.getVariableName());
     assertThat(variableValue).matches(".*bin/x/bin" + OsUtils.executableExtension() + "-2.params$");
@@ -122,7 +122,8 @@
     scratch.file("x/a.cc");
 
     ConfiguredTarget target = getConfiguredTarget("//x:foo");
-    Variables variables = getLinkBuildVariables(target, LinkTargetType.NODEPS_DYNAMIC_LIBRARY);
+    CcToolchainVariables variables =
+        getLinkBuildVariables(target, LinkTargetType.NODEPS_DYNAMIC_LIBRARY);
 
     String interfaceLibraryBuilder =
         getVariableValue(variables, LinkBuildVariables.INTERFACE_LIBRARY_BUILDER.getVariableName());
@@ -170,7 +171,7 @@
         (CppLinkAction)
             getPredecessorByInputName(
                 backendAction, "x/libfoo.so.lto/x/_objs/foo/x/a.pic.o.thinlto.bc");
-    Variables variables = indexAction.getLinkCommandLine().getBuildVariables();
+    CcToolchainVariables variables = indexAction.getLinkCommandLine().getBuildVariables();
 
     String interfaceLibraryBuilder =
         getVariableValue(variables, LinkBuildVariables.INTERFACE_LIBRARY_BUILDER.getVariableName());
@@ -201,7 +202,7 @@
     scratch.file("x/a.cc");
 
     ConfiguredTarget target = getConfiguredTarget("//x:foo");
-    Variables variables = getLinkBuildVariables(target, LinkTargetType.STATIC_LIBRARY);
+    CcToolchainVariables variables = getLinkBuildVariables(target, LinkTargetType.STATIC_LIBRARY);
 
     String interfaceLibraryBuilder =
         getVariableValue(variables, LinkBuildVariables.INTERFACE_LIBRARY_BUILDER.getVariableName());
@@ -227,7 +228,8 @@
     scratch.file("x/a.cc");
 
     ConfiguredTarget target = getConfiguredTarget("//x:foo");
-    Variables variables = getLinkBuildVariables(target, LinkTargetType.NODEPS_DYNAMIC_LIBRARY);
+    CcToolchainVariables variables =
+        getLinkBuildVariables(target, LinkTargetType.NODEPS_DYNAMIC_LIBRARY);
 
     assertThat(getVariableValue(variables, LinkBuildVariables.OUTPUT_EXECPATH.getVariableName()))
         .endsWith("x/libfoo.so");
@@ -262,7 +264,7 @@
         (CppLinkAction)
             getPredecessorByInputName(
                 backendAction, "x/libfoo.so.lto/x/_objs/foo/x/a.pic.o.thinlto.bc");
-    Variables variables = indexAction.getLinkCommandLine().getBuildVariables();
+    CcToolchainVariables variables = indexAction.getLinkCommandLine().getBuildVariables();
 
     assertThat(variables.isAvailable(LinkBuildVariables.OUTPUT_EXECPATH.getVariableName()))
         .isFalse();
@@ -276,14 +278,16 @@
     scratch.file("x/a.cc");
 
     ConfiguredTarget testTarget = getConfiguredTarget("//x:foo_test");
-    Variables testVariables = getLinkBuildVariables(testTarget, LinkTargetType.EXECUTABLE);
+    CcToolchainVariables testVariables =
+        getLinkBuildVariables(testTarget, LinkTargetType.EXECUTABLE);
 
     assertThat(
             testVariables.getVariable(LinkBuildVariables.IS_CC_TEST.getVariableName()).isTruthy())
         .isTrue();
 
     ConfiguredTarget binaryTarget = getConfiguredTarget("//x:foo");
-    Variables binaryVariables = getLinkBuildVariables(binaryTarget, LinkTargetType.EXECUTABLE);
+    CcToolchainVariables binaryVariables =
+        getLinkBuildVariables(binaryTarget, LinkTargetType.EXECUTABLE);
 
     assertThat(
             binaryVariables.getVariable(LinkBuildVariables.IS_CC_TEST.getVariableName()).isTruthy())
@@ -310,7 +314,7 @@
       String stripMode, String compilationMode, boolean isEnabled) throws Exception {
     useConfiguration("--strip=" + stripMode, "--compilation_mode=" + compilationMode);
     ConfiguredTarget target = getConfiguredTarget("//x:foo");
-    Variables variables = getLinkBuildVariables(target, LinkTargetType.EXECUTABLE);
+    CcToolchainVariables variables = getLinkBuildVariables(target, LinkTargetType.EXECUTABLE);
     assertThat(variables.isAvailable(LinkBuildVariables.STRIP_DEBUG_SYMBOLS.getVariableName()))
         .isEqualTo(isEnabled);
   }
@@ -327,13 +331,14 @@
 
     useConfiguration("--fission=no");
     ConfiguredTarget target = getConfiguredTarget("//x:foo");
-    Variables variables = getLinkBuildVariables(target, LinkTargetType.EXECUTABLE);
+    CcToolchainVariables variables = getLinkBuildVariables(target, LinkTargetType.EXECUTABLE);
     assertThat(variables.isAvailable(LinkBuildVariables.IS_USING_FISSION.getVariableName()))
         .isFalse();
 
     useConfiguration("--fission=yes");
     ConfiguredTarget fissionTarget = getConfiguredTarget("//x:foo");
-    Variables fissionVariables = getLinkBuildVariables(fissionTarget, LinkTargetType.EXECUTABLE);
+    CcToolchainVariables fissionVariables =
+        getLinkBuildVariables(fissionTarget, LinkTargetType.EXECUTABLE);
     assertThat(fissionVariables.isAvailable(LinkBuildVariables.IS_USING_FISSION.getVariableName()))
         .isTrue();
   }
@@ -349,7 +354,8 @@
     scratch.file("x/a.cc");
 
     ConfiguredTarget testTarget = getConfiguredTarget("//x:foo");
-    Variables testVariables = getLinkBuildVariables(testTarget, LinkTargetType.EXECUTABLE);
+    CcToolchainVariables testVariables =
+        getLinkBuildVariables(testTarget, LinkTargetType.EXECUTABLE);
 
     assertThat(testVariables.isAvailable(CcCommon.SYSROOT_VARIABLE_NAME)).isTrue();
   }
diff --git a/src/test/java/com/google/devtools/build/lib/rules/cpp/LinkBuildVariablesTestCase.java b/src/test/java/com/google/devtools/build/lib/rules/cpp/LinkBuildVariablesTestCase.java
index 3eab78d..f2ba846 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/cpp/LinkBuildVariablesTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/cpp/LinkBuildVariablesTestCase.java
@@ -21,7 +21,6 @@
 import com.google.devtools.build.lib.analysis.ConfiguredTarget;
 import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
 import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.FeatureConfiguration;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.view.config.crosstool.CrosstoolConfig.CToolchain;
 import com.google.protobuf.TextFormat;
@@ -61,7 +60,8 @@
   }
 
   /** Returns active build variables for a link action of given type for given target. */
-  protected Variables getLinkBuildVariables(ConfiguredTarget target, Link.LinkTargetType type) {
+  protected CcToolchainVariables getLinkBuildVariables(
+      ConfiguredTarget target, Link.LinkTargetType type) {
     return getCppLinkAction(target, type).getLinkCommandLine().getBuildVariables();
   }
 
@@ -76,7 +76,7 @@
   }
 
   /** Returns the value of a given sequence variable in context of the given Variables instance. */
-  protected List<String> getSequenceVariableValue(Variables variables, String variable)
+  protected List<String> getSequenceVariableValue(CcToolchainVariables variables, String variable)
       throws Exception {
     FeatureConfiguration mockFeatureConfiguration =
         buildFeatures(
@@ -95,7 +95,8 @@
   }
 
   /** Returns the value of a given string variable in context of the given Variables instance. */
-  protected String getVariableValue(Variables variables, String variable) throws Exception {
+  protected String getVariableValue(CcToolchainVariables variables, String variable)
+      throws Exception {
     FeatureConfiguration mockFeatureConfiguration =
         buildFeatures(
                 "feature {",
diff --git a/src/test/java/com/google/devtools/build/lib/rules/objc/ObjcBuildVariablesTest.java b/src/test/java/com/google/devtools/build/lib/rules/objc/ObjcBuildVariablesTest.java
index e49d647..5d2eed5 100644
--- a/src/test/java/com/google/devtools/build/lib/rules/objc/ObjcBuildVariablesTest.java
+++ b/src/test/java/com/google/devtools/build/lib/rules/objc/ObjcBuildVariablesTest.java
@@ -26,7 +26,7 @@
 import com.google.devtools.build.lib.packages.util.MockObjcSupport;
 import com.google.devtools.build.lib.rules.apple.AppleCommandLineOptions;
 import com.google.devtools.build.lib.rules.apple.cpp.AppleCcToolchain;
-import com.google.devtools.build.lib.rules.cpp.CcToolchainFeatures.Variables;
+import com.google.devtools.build.lib.rules.cpp.CcToolchainVariables;
 import com.google.devtools.build.lib.rules.cpp.CppLinkAction;
 import com.google.devtools.build.lib.rules.cpp.Link;
 import com.google.devtools.build.lib.rules.cpp.LinkBuildVariablesTestCase;
@@ -39,7 +39,7 @@
 /**
  * Tests that {@code CppLinkAction} is populated with the correct build variables for objective C
  * builds.
- **/
+ */
 @RunWith(JUnit4.class)
 public class ObjcBuildVariablesTest extends LinkBuildVariablesTestCase {
 
@@ -78,7 +78,7 @@
     scratch.file("x/a.cc");
 
     ConfiguredTarget target = getConfiguredTarget("//x:bin");
-    Variables variables = getLinkBuildVariables(target, Link.LinkTargetType.EXECUTABLE);
+    CcToolchainVariables variables = getLinkBuildVariables(target, Link.LinkTargetType.EXECUTABLE);
     assertThat(
             getVariableValue(variables, AppleCcToolchain.XCODE_VERISON_OVERRIDE_VALUE_KEY))
         .contains("5.8");
@@ -126,7 +126,7 @@
         ActionsTestUtil.getFirstArtifactEndingWith(appleBinLinkAction.getInputs(), "liba.a");
     CppLinkAction ccArchiveAction = (CppLinkAction) getGeneratingAction(archive);
 
-    Variables variables = ccArchiveAction.getLinkCommandLine().getBuildVariables();
+    CcToolchainVariables variables = ccArchiveAction.getLinkCommandLine().getBuildVariables();
     assertThat(
             getVariableValue(variables, AppleCcToolchain.XCODE_VERISON_OVERRIDE_VALUE_KEY))
         .contains("5.8");
@@ -174,7 +174,7 @@
         ActionsTestUtil.getFirstArtifactEndingWith(appleBinLinkAction.getInputs(), "liba.a");
     CppLinkAction ccArchiveAction = (CppLinkAction) getGeneratingAction(archive);
 
-    Variables variables = ccArchiveAction.getLinkCommandLine().getBuildVariables();
+    CcToolchainVariables variables = ccArchiveAction.getLinkCommandLine().getBuildVariables();
     assertThat(getVariableValue(variables, AppleCcToolchain.VERSION_MIN_KEY))
         .contains(dummyMinimumOsValue);
   }
@@ -193,7 +193,7 @@
     scratch.file("x/a.cc");
 
     ConfiguredTarget target = getConfiguredTarget("//x:bin");
-    Variables variables = getLinkBuildVariables(target, Link.LinkTargetType.EXECUTABLE);
+    CcToolchainVariables variables = getLinkBuildVariables(target, Link.LinkTargetType.EXECUTABLE);
     assertThat(
             getVariableValue(variables, AppleCcToolchain.XCODE_VERISON_OVERRIDE_VALUE_KEY))
         .contains(MockObjcSupport.DEFAULT_XCODE_VERSION);
@@ -239,7 +239,7 @@
         ActionsTestUtil.getFirstArtifactEndingWith(appleBinLinkAction.getInputs(), "liba.a");
     CppLinkAction ccArchiveAction = (CppLinkAction) getGeneratingAction(archive);
 
-    Variables variables = ccArchiveAction.getLinkCommandLine().getBuildVariables();
+    CcToolchainVariables variables = ccArchiveAction.getLinkCommandLine().getBuildVariables();
     assertThat(getVariableValue(variables, AppleCcToolchain.VERSION_MIN_KEY))
         .contains(dummyMinimumOsValue);
   }