Thanks for the report, I'll look into this today. It should definitely be a warning, not a hard crash. The actual cycle is this:
- //tests:expansion_test
- needs a toolchain of type @io_bazel_rules_m4//m4:toolchain_type
- depends on all registered toolchains
- includes @io_bazel_rules_m4//m4/toolchains:v1.4.18
- depends on @io_bazel_rules_m4//m4/internal:deny_shell
- needs a toolchain of type @bazel_tools//tools/cpp:toolchain_type
- depends on all registered toolchains
- cycle

So, as you said, the real error here is that RegisteredToolchainsFunction has a dependency on something that isn't providing ToolchainRuleInfo.

Normally, RegisteredToolchainsFunction only accepts targets of a rule named "toolchain", 
which prevents this in the typical case, but still allows for the odd case where someone writes a Starlark rule named "toolchain" and uses that incorrectly as the argument to register_toolchains. This rule is applied when expanding target patterns, such as if you wrote `register_toolchains('//toolchains:all')`.

The reason you see this error is because RegisteredToolchainsFunction tries to be forgiving, so that if a target is directly specified as the argument to register_toolchains, it is kept even if the rule name is not "toolchain". The assumption here being that the user knows what they are doing and intended wrat they wrote.

Given this, the best way forward is to try to add better error handling in RegisteredToolchainsFunction, which I will look into adding. Reproduction:
```sh
$ git clone git@github.com:jmillikin/rules_m4.git
$ cd rules_m4
$ bazel build //tests:expansion_test --extra_toolchains=//m4/internal:toolchain_v1.4.18
```

Oddly, a simpler reproduction test case I tried to wrote did show an error message:
```
$ bazel build --extra_toolchains=//:demo //:sample
Starting local Bazel server and connecting to it...
INFO: Invocation ID: 5958e443-ec4a-4054-8cc6-112d98bd94bf
ERROR: While resolving toolchains for target //:sample: invalid registered toolchain '//:demo': target does not provide the DeclaredToolchainInfo provider
WARNING: errors encountered while analyzing target '//:sample': it will not be built
INFO: Analysed target //:sample (6 packages loaded, 23 targets configured).
INFO: Found 0 targets...
ERROR: command succeeded, but not all targets were analyzed
INFO: Elapsed time: 2.956s, Critical Path: 0.02s
INFO: 0 processes.
FAILED: Build did NOT complete successfully
``` Okay, managed to get a simpler reproduction, because this relies on their being two toolchains, one of which depends on the other, and the top-level one being mis-configured in register_toolchains.

Looking into implementing a cycle reporter to make the problem clear. I'm not sure there's any level of introspection in RegisteredToolchainsFunction that can catch this, due to the fact that the error happens while the toolchain targets are being loaded.
java.lang.IllegalStateException when referencing ToolchainInfo targets instead of ToolchainRuleInfo
Bazel's toolchain registration involves two targets: a "toolchain info" that returns a `platform_common.ToolchainInfo` with arbitrary content, and a "toolchain" that registers the toolchain info with execution constraints.

If the user confuses these two (either when calling `native.register_toolchains()` or with the `--extra_toolchains` flag) then Bazel will crash during analysis.

example BUILD ([`rules_m4/m4/toolchains/BUILD`](https://github.com/jmillikin/rules_m4/blob/5a8562a8796963da93b6ed8e6c205551cbf949b5/m4/toolchains/BUILD)):
```
load("//m4:m4.bzl", "M4_VERSIONS")
load("//m4:toolchain.bzl", "m4_toolchain_info")

[m4_toolchain_info(
    name = "v{}".format(version),
    m4 = "@m4_v{}//bin:m4".format(version),
    tags = ["manual"],
    visibility = ["//visibility:public"],
) for version in M4_VERSIONS]

[toolchain(
    name = "v{}_toolchain".format(version),
    toolchain = ":v{}".format(version),
    toolchain_type = "//m4:toolchain_type",
) for version in M4_VERSIONS]
```

Full error output when the user forgets the `_toolchain` suffix:
```
$ ./bazel-0.22.0rc1-darwin-x86_64 build //tests:expansion_test --extra_toolchains=@io_bazel_rules_m4//m4/toolchains:v1.4.18
Starting local Bazel server and connecting to it...
INFO: Invocation ID: 2780f5f3-5e47-4588-805e-0b2ce38fc86e
Internal error thrown during build. Printing stack trace: java.lang.IllegalStateException: topLevelKey: //tests:expansion_test BuildConfigurationValue.Key[94f032dd1c40f99180ff553125967cf3] false
alreadyReported: false
path to cycle:
//tests:expansion_test BuildConfigurationValue.Key[94f032dd1c40f99180ff553125967cf3] false
Key{configurationKey=BuildConfigurationValue.Key[94f032dd1c40f99180ff553125967cf3], toolchainTypeLabel=@io_bazel_rules_m4//m4:toolchain_type, targetPlatformKey=@bazel_tools//platforms:target_platform BuildConfigurationValue.Key[94f032dd1c40f99180ff553125967cf3] false, availableExecutionPlatformKeys=[@bazel_tools//platforms:host_platform BuildConfigurationValue.Key[94f032dd1c40f99180ff553125967cf3] false]}
RegisteredToolchainsValue.Key{configurationKey: BuildConfigurationValue.Key[94f032dd1c40f99180ff553125967cf3]}
@io_bazel_rules_m4//m4/toolchains:v1.4.18 BuildConfigurationValue.Key[94f032dd1c40f99180ff553125967cf3] false
cycle:
@io_bazel_rules_m4//m4/internal:deny_shell BuildConfigurationValue.Key[a1782a45cb1a1c8fbec9cef9245c752c] true
Key{configurationKey=BuildConfigurationValue.Key[a1782a45cb1a1c8fbec9cef9245c752c], toolchainTypeLabel=@bazel_tools//tools/cpp:toolchain_type, targetPlatformKey=@bazel_tools//platforms:host_platform BuildConfigurationValue.Key[a1782a45cb1a1c8fbec9cef9245c752c] true, availableExecutionPlatformKeys=[@bazel_tools//platforms:host_platform BuildConfigurationValue.Key[a1782a45cb1a1c8fbec9cef9245c752c] true]}
RegisteredToolchainsValue.Key{configurationKey: BuildConfigurationValue.Key[a1782a45cb1a1c8fbec9cef9245c752c]}
@io_bazel_rules_m4//m4/toolchains:v1.4.18 BuildConfigurationValue.Key[a1782a45cb1a1c8fbec9cef9245c752c] true

	at com.google.common.base.Preconditions.checkState(Preconditions.java:507)
	at com.google.devtools.build.skyframe.CyclesReporter.reportCycles(CyclesReporter.java:85)
	at com.google.devtools.build.lib.skyframe.SkyframeBuildView.processErrors(SkyframeBuildView.java:527)
	at com.google.devtools.build.lib.skyframe.SkyframeBuildView.configureTargets(SkyframeBuildView.java:444)
	at com.google.devtools.build.lib.analysis.BuildView.update(BuildView.java:369)
	at com.google.devtools.build.lib.buildtool.AnalysisPhaseRunner.runAnalysisPhase(AnalysisPhaseRunner.java:209)
	at com.google.devtools.build.lib.buildtool.AnalysisPhaseRunner.execute(AnalysisPhaseRunner.java:118)
	at com.google.devtools.build.lib.buildtool.BuildTool.buildTargets(BuildTool.java:143)
	at com.google.devtools.build.lib.buildtool.BuildTool.processRequest(BuildTool.java:253)
	at com.google.devtools.build.lib.runtime.commands.BuildCommand.exec(BuildCommand.java:83)
	at com.google.devtools.build.lib.runtime.BlazeCommandDispatcher.execExclusively(BlazeCommandDispatcher.java:477)
	at com.google.devtools.build.lib.runtime.BlazeCommandDispatcher.exec(BlazeCommandDispatcher.java:205)
	at com.google.devtools.build.lib.server.GrpcServerImpl.executeCommand(GrpcServerImpl.java:749)
	at com.google.devtools.build.lib.server.GrpcServerImpl.access$1600(GrpcServerImpl.java:103)
	at com.google.devtools.build.lib.server.GrpcServerImpl$2.lambda$run$0(GrpcServerImpl.java:818)
	at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(Unknown Source)
	at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(Unknown Source)
	at java.base/java.lang.Thread.run(Unknown Source)

INFO: Elapsed time: 4.065s
```
src/main/java/com/google/devtools/build/lib/analysis/ToolchainResolver.java
src/main/java/com/google/devtools/build/lib/analysis/ToolchainResolver.java
diff --git a/src/main/java/com/google/devtools/build/lib/analysis/ToolchainResolver.java b/src/main/java/com/google/devtools/build/lib/analysis/ToolchainResolver.java
index 1f3470a8a1eac0..283780d12588cf 100644
--- a/src/main/java/com/google/devtools/build/lib/analysis/ToolchainResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/analysis/ToolchainResolver.java
@@ -543,7 +543,7 @@ public ToolchainContext load(
           if (toolchainType != null) {
             ToolchainInfo toolchainInfo =
                 PlatformProviderUtils.toolchain(target.getConfiguredTarget());
-            if (toolchainType != null) {
+            if (toolchainInfo != null) {
               toolchains.put(toolchainType, toolchainInfo);
             }
           }
