diff --git a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
index 7797838..d8007c1 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/BuildView.java
@@ -1253,7 +1253,7 @@
       throws EvalException, InvalidConfigurationException, InterruptedException,
           InconsistentAspectOrderException, ToolchainContextException {
     BuildConfiguration targetConfig = target.getConfiguration();
-    List<Label> requiredToolchains =
+    Set<Label> requiredToolchains =
         target.getTarget().getAssociatedRule().getRuleClassObject().getRequiredToolchains();
     ToolchainContext toolchainContext =
         skyframeExecutor.getToolchainContextForTesting(
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ToolchainContext.java b/src/main/java/com/google/devtools/build/lib/analysis/ToolchainContext.java
index 8754c3e..7327c53 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ToolchainContext.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ToolchainContext.java
@@ -38,7 +38,6 @@
 import com.google.devtools.build.lib.syntax.SkylarkIndexable;
 import com.google.devtools.build.lib.util.OrderedSetMultimap;
 import com.google.devtools.build.lib.util.Preconditions;
-import java.util.List;
 import java.util.Optional;
 import java.util.Set;
 import javax.annotation.Nullable;
@@ -54,7 +53,7 @@
 public class ToolchainContext {
   public static ToolchainContext create(
       String targetDescription,
-      List<Label> requiredToolchains,
+      Set<Label> requiredToolchains,
       ImmutableBiMap<Label, Label> resolvedLabels) {
     ToolchainContext toolchainContext =
         new ToolchainContext(
@@ -76,7 +75,7 @@
 
   private ToolchainContext(
       String targetDescription,
-      List<Label> requiredToolchains,
+      Set<Label> requiredToolchains,
       ResolvedToolchainLabels resolvedToolchainLabels) {
     this.targetDescription = targetDescription;
     this.requiredToolchains = ImmutableList.copyOf(requiredToolchains);
diff --git a/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java b/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
index 7fcd60f..5570c3f 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/AspectDefinition.java
@@ -60,7 +60,7 @@
   private final RequiredProviders requiredProviders;
   private final RequiredProviders requiredProvidersForAspects;
   private final ImmutableMap<String, Attribute> attributes;
-  private final ImmutableList<Label> requiredToolchains;
+  private final ImmutableSet<Label> requiredToolchains;
 
   /**
    * Which attributes aspect should propagate along:
@@ -83,7 +83,7 @@
       RequiredProviders requiredProviders,
       RequiredProviders requiredAspectProviders,
       ImmutableMap<String, Attribute> attributes,
-      ImmutableList<Label> requiredToolchains,
+      ImmutableSet<Label> requiredToolchains,
       @Nullable ImmutableSet<String> restrictToAttributes,
       @Nullable ConfigurationFragmentPolicy configurationFragmentPolicy,
       boolean applyToFiles) {
@@ -117,7 +117,7 @@
   }
 
   /** Returns the required toolchains declared by this aspect. */
-  public ImmutableList<Label> getRequiredToolchains() {
+  public ImmutableSet<Label> getRequiredToolchains() {
     return requiredToolchains;
   }
 
@@ -485,7 +485,7 @@
           requiredProviders.build(),
           requiredAspectProviders.build(),
           ImmutableMap.copyOf(attributes),
-          ImmutableList.copyOf(requiredToolchains),
+          ImmutableSet.copyOf(requiredToolchains),
           propagateAlongAttributes == null ? null : ImmutableSet.copyOf(propagateAlongAttributes),
           configurationFragmentPolicy.build(),
           applyToFiles);
diff --git a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
index 3a222db..dcf6092 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/RuleClass.java
@@ -59,6 +59,7 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -483,7 +484,7 @@
     private boolean supportsConstraintChecking = true;
 
     private final Map<String, Attribute> attributes = new LinkedHashMap<>();
-    private final List<Label> requiredToolchains = new ArrayList<>();
+    private final Set<Label> requiredToolchains = new HashSet<>();
 
     /**
      * Constructs a new {@code RuleClassBuilder} using all attributes from all
@@ -1115,7 +1116,7 @@
    */
   private final boolean supportsConstraintChecking;
 
-  private final ImmutableList<Label> requiredToolchains;
+  private final ImmutableSet<Label> requiredToolchains;
 
   /**
    * Constructs an instance of RuleClass whose name is 'name', attributes are 'attributes'. The
@@ -1163,7 +1164,7 @@
       String ruleDefinitionEnvironmentHashCode,
       ConfigurationFragmentPolicy configurationFragmentPolicy,
       boolean supportsConstraintChecking,
-      List<Label> requiredToolchains,
+      Set<Label> requiredToolchains,
       Attribute... attributes) {
     this.name = name;
     this.isSkylark = isSkylark;
@@ -1192,7 +1193,7 @@
     this.outputsDefaultExecutable = outputsDefaultExecutable;
     this.configurationFragmentPolicy = configurationFragmentPolicy;
     this.supportsConstraintChecking = supportsConstraintChecking;
-    this.requiredToolchains = ImmutableList.copyOf(requiredToolchains);
+    this.requiredToolchains = ImmutableSet.copyOf(requiredToolchains);
 
     // Create the index and collect non-configurable attributes.
     int index = 0;
@@ -2002,7 +2003,7 @@
     return outputsDefaultExecutable;
   }
 
-  public ImmutableList<Label> getRequiredToolchains() {
+  public ImmutableSet<Label> getRequiredToolchains() {
     return requiredToolchains;
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
index f9ae4cf..ce8405b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java
@@ -17,6 +17,7 @@
 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.devtools.build.lib.actions.ActionAnalysisMetadata;
 import com.google.devtools.build.lib.actions.ActionLookupValue;
 import com.google.devtools.build.lib.analysis.AliasProvider;
@@ -275,7 +276,7 @@
       // Determine what toolchains are needed by this target.
       ToolchainContext toolchainContext;
       try {
-        ImmutableList<Label> requiredToolchains = aspect.getDefinition().getRequiredToolchains();
+        ImmutableSet<Label> requiredToolchains = aspect.getDefinition().getRequiredToolchains();
         toolchainContext =
             ToolchainUtil.createToolchainContext(
                 env,
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
index 7e396ec..9832487 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java
@@ -232,7 +232,7 @@
       // Determine what toolchains are needed by this target.
       if (target instanceof Rule) {
         Rule rule = ((Rule) target);
-        ImmutableList<Label> requiredToolchains = rule.getRuleClassObject().getRequiredToolchains();
+        ImmutableSet<Label> requiredToolchains = rule.getRuleClassObject().getRequiredToolchains();
         toolchainContext =
             ToolchainUtil.createToolchainContext(
                 env, rule.toString(), requiredToolchains, configuration);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index d6aec31..f592d39 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -834,7 +834,7 @@
 
   @VisibleForTesting
   public ToolchainContext getToolchainContextForTesting(
-      List<Label> requiredToolchains, BuildConfiguration config, ExtendedEventHandler eventHandler)
+      Set<Label> requiredToolchains, BuildConfiguration config, ExtendedEventHandler eventHandler)
       throws ToolchainContextException, InterruptedException {
     SkyFunctionEnvironmentForTesting env =
         new SkyFunctionEnvironmentForTesting(buildDriver, eventHandler);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainUtil.java b/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainUtil.java
index 0f2a352..13e055b 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainUtil.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ToolchainUtil.java
@@ -38,6 +38,7 @@
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import javax.annotation.Nullable;
 
 /**
@@ -53,7 +54,7 @@
   public static ToolchainContext createToolchainContext(
       Environment env,
       String targetDescription,
-      List<Label> requiredToolchains,
+      Set<Label> requiredToolchains,
       BuildConfiguration configuration)
       throws ToolchainContextException, InterruptedException {
     ImmutableBiMap<Label, Label> resolvedLabels =
@@ -131,7 +132,7 @@
 
   @Nullable
   private static ImmutableBiMap<Label, Label> resolveToolchainLabels(
-      Environment env, List<Label> requiredToolchains, BuildConfiguration configuration)
+      Environment env, Set<Label> requiredToolchains, BuildConfiguration configuration)
       throws InterruptedException, ToolchainContextException {
 
     // If there are no required toolchains, bail out early.