diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsFunctionTest.java
index 7ebc55b..c002619 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RegisteredExecutionPlatformsFunctionTest.java
@@ -23,6 +23,7 @@
 import com.google.devtools.build.lib.analysis.platform.PlatformInfo.DuplicateConstraintException;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.rules.platform.ToolchainTestCase;
+import com.google.devtools.build.lib.skyframe.ToolchainUtil.InvalidPlatformException;
 import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
 import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.SkyKey;
@@ -115,13 +116,16 @@
     SkyKey executionPlatformsKey = RegisteredExecutionPlatformsValue.key(targetConfigKey);
     EvaluationResult<RegisteredExecutionPlatformsValue> result =
         requestExecutionPlatformsFromSkyframe(executionPlatformsKey);
+    assertThatEvaluationResult(result).hasError();
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(executionPlatformsKey)
+        .hasExceptionThat()
+        .isInstanceOf(InvalidPlatformException.class);
     assertThatEvaluationResult(result)
         .hasErrorEntryForKeyThat(executionPlatformsKey)
         .hasExceptionThat()
         .hasMessageThat()
-        .contains(
-            "invalid registered execution platform '//error:not_an_execution_platform': "
-                + "target does not provide the PlatformInfo provider");
+        .contains("//error:not_an_execution_platform");
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunctionTest.java
index 0194819..702929b 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainResolutionFunctionTest.java
@@ -88,7 +88,7 @@
 
     ToolchainResolutionValue toolchainResolutionValue = result.get(key);
     assertThat(toolchainResolutionValue.availableToolchainLabels())
-        .containsExactly(macPlatform, makeLabel("//toolchain:toolchain_2_impl"));
+        .containsExactly(MAC_CTKEY, makeLabel("//toolchain:toolchain_2_impl"));
   }
 
   @Test
@@ -118,9 +118,9 @@
     ToolchainResolutionValue toolchainResolutionValue = result.get(key);
     assertThat(toolchainResolutionValue.availableToolchainLabels())
         .containsExactly(
-            linuxPlatform,
+            LINUX_CTKEY,
             makeLabel("//extra:extra_toolchain_impl"),
-            macPlatform,
+            MAC_CTKEY,
             makeLabel("//toolchain:toolchain_2_impl"));
   }
 
@@ -146,37 +146,27 @@
     new EqualsTester()
         .addEqualityGroup(
             ToolchainResolutionValue.create(
-                ImmutableMap.<PlatformInfo, Label>builder()
-                    .put(linuxPlatform, makeLabel("//test:toolchain_impl_1"))
-                    .build()),
+                ImmutableMap.of(LINUX_CTKEY, makeLabel("//test:toolchain_impl_1"))),
             ToolchainResolutionValue.create(
-                ImmutableMap.<PlatformInfo, Label>builder()
-                    .put(linuxPlatform, makeLabel("//test:toolchain_impl_1"))
-                    .build()))
+                ImmutableMap.of(LINUX_CTKEY, makeLabel("//test:toolchain_impl_1"))))
         // Different execution platform, same label.
         .addEqualityGroup(
             ToolchainResolutionValue.create(
-                ImmutableMap.<PlatformInfo, Label>builder()
-                    .put(macPlatform, makeLabel("//test:toolchain_impl_1"))
-                    .build()))
+                ImmutableMap.of(MAC_CTKEY, makeLabel("//test:toolchain_impl_1"))))
         // Same execution platform, different label.
         .addEqualityGroup(
             ToolchainResolutionValue.create(
-                ImmutableMap.<PlatformInfo, Label>builder()
-                    .put(linuxPlatform, makeLabel("//test:toolchain_impl_2"))
-                    .build()))
+                ImmutableMap.of(LINUX_CTKEY, makeLabel("//test:toolchain_impl_2"))))
         // Different execution platform, different label.
         .addEqualityGroup(
             ToolchainResolutionValue.create(
-                ImmutableMap.<PlatformInfo, Label>builder()
-                    .put(macPlatform, makeLabel("//test:toolchain_impl_2"))
-                    .build()))
+                ImmutableMap.of(MAC_CTKEY, makeLabel("//test:toolchain_impl_2"))))
         // Multiple execution platforms.
         .addEqualityGroup(
             ToolchainResolutionValue.create(
-                ImmutableMap.<PlatformInfo, Label>builder()
-                    .put(linuxPlatform, makeLabel("//test:toolchain_impl_1"))
-                    .put(macPlatform, makeLabel("//test:toolchain_impl_1"))
+                ImmutableMap.<ConfiguredTargetKey, Label>builder()
+                    .put(LINUX_CTKEY, makeLabel("//test:toolchain_impl_1"))
+                    .put(MAC_CTKEY, makeLabel("//test:toolchain_impl_1"))
                     .build()));
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainUtilTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainUtilTest.java
index 442f5de..166bc22 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainUtilTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/ToolchainUtilTest.java
@@ -18,14 +18,15 @@
 import static com.google.devtools.build.skyframe.EvaluationResultSubjectFactory.assertThatEvaluationResult;
 
 import com.google.auto.value.AutoValue;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.lib.analysis.BlazeDirectories;
 import com.google.devtools.build.lib.analysis.ToolchainContext;
-import com.google.devtools.build.lib.analysis.config.BuildConfiguration;
 import com.google.devtools.build.lib.analysis.util.AnalysisMock;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.rules.platform.ToolchainTestCase;
+import com.google.devtools.build.lib.skyframe.ToolchainUtil.InvalidPlatformException;
 import com.google.devtools.build.lib.skyframe.ToolchainUtil.ToolchainContextException;
 import com.google.devtools.build.lib.skyframe.ToolchainUtil.UnresolvedToolchainsException;
 import com.google.devtools.build.lib.skyframe.util.SkyframeExecutorTestUtils;
@@ -72,11 +73,28 @@
 
   @Test
   public void createToolchainContext() throws Exception {
-    useConfiguration(
-        "--host_platform=//platforms:linux",
-        "--platforms=//platforms:mac");
+    // This should select platform mac, toolchain extra_toolchain_mac, because platform
+    // mac is listed first.
+    addToolchain(
+        "extra",
+        "extra_toolchain_linux",
+        ImmutableList.of("//constraints:linux"),
+        ImmutableList.of("//constraints:linux"),
+        "baz");
+    addToolchain(
+        "extra",
+        "extra_toolchain_mac",
+        ImmutableList.of("//constraints:mac"),
+        ImmutableList.of("//constraints:linux"),
+        "baz");
+    rewriteWorkspace(
+        "register_toolchains('//extra:extra_toolchain_linux', '//extra:extra_toolchain_mac')",
+        "register_execution_platforms('//platforms:mac', '//platforms:linux')");
+
+    useConfiguration("--platforms=//platforms:linux");
     CreateToolchainContextKey key =
-        CreateToolchainContextKey.create("test", ImmutableSet.of(testToolchainType), targetConfig);
+        CreateToolchainContextKey.create(
+            "test", ImmutableSet.of(testToolchainType), targetConfigKey);
 
     EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
 
@@ -86,15 +104,15 @@
 
     assertThat(toolchainContext.getRequiredToolchains()).containsExactly(testToolchainType);
     assertThat(toolchainContext.getResolvedToolchainLabels())
-        .containsExactly(Label.parseAbsoluteUnchecked("//toolchain:toolchain_1_impl"));
+        .containsExactly(Label.parseAbsoluteUnchecked("//extra:extra_toolchain_mac_impl"));
 
     assertThat(toolchainContext.getExecutionPlatform()).isNotNull();
     assertThat(toolchainContext.getExecutionPlatform().label())
-        .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:linux"));
+        .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:mac"));
 
     assertThat(toolchainContext.getTargetPlatform()).isNotNull();
     assertThat(toolchainContext.getTargetPlatform().label())
-        .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:mac"));
+        .isEqualTo(Label.parseAbsoluteUnchecked("//platforms:linux"));
   }
 
   @Test
@@ -107,7 +125,7 @@
             "test",
             ImmutableSet.of(
                 testToolchainType, Label.parseAbsoluteUnchecked("//fake/toolchain:type_1")),
-            targetConfig);
+            targetConfigKey);
 
     EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
 
@@ -140,7 +158,7 @@
                 testToolchainType,
                 Label.parseAbsoluteUnchecked("//fake/toolchain:type_1"),
                 Label.parseAbsoluteUnchecked("//fake/toolchain:type_2")),
-            targetConfig);
+            targetConfigKey);
 
     EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
 
@@ -156,6 +174,90 @@
     // Only one of the missing types will be reported, so do not check the specific error message.
   }
 
+  @Test
+  public void createToolchainContext_invalidTargetPlatform() throws Exception {
+    scratch.file("invalid/BUILD", "filegroup(name = 'not_a_platform')");
+    useConfiguration("--platforms=//invalid:not_a_platform");
+    CreateToolchainContextKey key =
+        CreateToolchainContextKey.create(
+            "test", ImmutableSet.of(testToolchainType), targetConfigKey);
+
+    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+
+    assertThatEvaluationResult(result).hasError();
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .isInstanceOf(ToolchainContextException.class);
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .hasCauseThat()
+        .isInstanceOf(InvalidPlatformException.class);
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .hasCauseThat()
+        .hasMessageThat()
+        .contains("//invalid:not_a_platform");
+  }
+
+  @Test
+  public void createToolchainContext_invalidHostPlatform() throws Exception {
+    scratch.file("invalid/BUILD", "filegroup(name = 'not_a_platform')");
+    useConfiguration("--host_platform=//invalid:not_a_platform");
+    CreateToolchainContextKey key =
+        CreateToolchainContextKey.create(
+            "test", ImmutableSet.of(testToolchainType), targetConfigKey);
+
+    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+
+    assertThatEvaluationResult(result).hasError();
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .isInstanceOf(ToolchainContextException.class);
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .hasCauseThat()
+        .isInstanceOf(InvalidPlatformException.class);
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .hasCauseThat()
+        .hasMessageThat()
+        .contains("//invalid:not_a_platform");
+  }
+
+  @Test
+  public void createToolchainContext_invalidExecutionPlatform() throws Exception {
+    scratch.file("invalid/BUILD", "filegroup(name = 'not_a_platform')");
+    useConfiguration("--extra_execution_platforms=//invalid:not_a_platform");
+    CreateToolchainContextKey key =
+        CreateToolchainContextKey.create(
+            "test", ImmutableSet.of(testToolchainType), targetConfigKey);
+
+    EvaluationResult<CreateToolchainContextValue> result = createToolchainContext(key);
+
+    assertThatEvaluationResult(result).hasError();
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .isInstanceOf(ToolchainContextException.class);
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .hasCauseThat()
+        .isInstanceOf(InvalidPlatformException.class);
+    assertThatEvaluationResult(result)
+        .hasErrorEntryForKeyThat(key)
+        .hasExceptionThat()
+        .hasCauseThat()
+        .hasMessageThat()
+        .contains("//invalid:not_a_platform");
+  }
+
   // Calls ToolchainUtil.createToolchainContext.
   private static final SkyFunctionName CREATE_TOOLCHAIN_CONTEXT_FUNCTION =
       SkyFunctionName.create("CREATE_TOOLCHAIN_CONTEXT_FUNCTION");
@@ -171,12 +273,14 @@
 
     abstract Set<Label> requiredToolchains();
 
-    abstract BuildConfiguration configuration();
+    abstract BuildConfigurationValue.Key configurationKey();
 
     public static CreateToolchainContextKey create(
-        String targetDescription, Set<Label> requiredToolchains, BuildConfiguration configuration) {
+        String targetDescription,
+        Set<Label> requiredToolchains,
+        BuildConfigurationValue.Key configurationKey) {
       return new AutoValue_ToolchainUtilTest_CreateToolchainContextKey(
-          targetDescription, requiredToolchains, configuration);
+          targetDescription, requiredToolchains, configurationKey);
     }
   }
 
@@ -212,14 +316,7 @@
       try {
         toolchainContext =
             ToolchainUtil.createToolchainContext(
-                env,
-                key.targetDescription(),
-                key.requiredToolchains(),
-                key.configuration(),
-                key.configuration() == null
-                    ? null
-                    : BuildConfigurationValue.key(
-                        key.configuration().fragmentClasses(), key.configuration().getOptions()));
+                env, key.targetDescription(), key.requiredToolchains(), key.configurationKey());
         if (toolchainContext == null) {
           return null;
         }