ICE While Testing generic_const_exprs, adt_const_params, & const_fn_trait_bound features

[philliard3]

I was testing the limits of Rust's experimental const generics capabilities, and I came across this bug. The bug seems to occur only when remove_key is used.

I've had trouble minimizing this bug, so for context, I'll explain the program's purpose. The goal is to create a HashMap that has compile-time restrictions on what keys can be inserted. The first part of this program establishes a compile-time-checkable list of keys that can be any value that can be a const generic. In this case I've replaced my "Key" type alias with &'static str because that's where the error came up, as well as for readability. The second part of the program makes up the definition of the hashmap itself, which relies on the invariant that its "schema" contains a specific const-evaluable key in order to insert or remove a value. This also requires being able to build out a schema by adding and removing keys, producing a new type in the process because the types are what track the schema. The third part of the program is a small test for adding and removing keys, and it's when these tests are run that the error occurs.

This code compiles and runs if we do not run the test involving removing a key from a map that has already been created. Something about resolving the requirements in that test produces an error in the compiler.

Code (playground link)

#![feature(adt_const_params)]
#![feature(generic_const_exprs)]
#![feature(const_fn_trait_bound)]

use core::marker::PhantomData;
use std::collections::HashMap;

// const-evaluable equality for string slices
pub const fn str_eq(lhs: &str, rhs: &str) -> bool {
    let lhs_bytes = lhs.as_bytes();
    let rhs_bytes = rhs.as_bytes();
    let mut i = 0;
    let bytes = if lhs_bytes.len() == rhs_bytes.len() {
        lhs_bytes.len()
    } else {
        return false;
    };

    while i < bytes {
        if lhs_bytes[i] != rhs_bytes[i] {
            return false;
        }
        i += 1;
    }
    return true;
}

pub trait ContainsKey<const K: &'static str> {}

// trait used to compare two types that have type-encoded lists of keys (in this cast static strings)
pub trait KeySchema {
    const KEYS: &'static [&'static str];
    const SIZE: usize;
}

pub struct KeyNil;
impl KeySchema for KeyNil {
    const KEYS: &'static [&'static str] = &[];
    const SIZE: usize = 0;
}

pub struct KeyCons<Tail, const KEY_ID: &'static str>
where
    Tail: KeySchema,
{
    _tail: PhantomData<Tail>,
}

pub const fn compute_successor_size<T: KeySchema>() -> usize {
    T::SIZE + 1
}

pub const fn construct_successor_array<Tail: KeySchema>(
    successor_key: &'static str,
) -> [&'static str; compute_successor_size::<Tail>()]
where
    [&'static str; compute_successor_size::<Tail>()]: Sized,
{
    let mut keys = [""; compute_successor_size::<Tail>()];
    let tail_keys = Tail::KEYS;
    let mut i = 0;
    let old_array_size: usize = compute_successor_size::<Tail>() - 1;
    while i < old_array_size {
        keys[i] = tail_keys[i];
        i += 1;
    }
    keys[old_array_size] = successor_key;
    keys
}

pub const fn is_equivalent_except<const K: &'static str>(
    with_k: &[&'static str],
    without_k: &[&'static str],
) -> bool {
    let mut i = 0;
    while i < with_k.len() {
        if str_eq(with_k[i], K) {
            i += 1;
            continue;
        }
        let mut j = 0;
        let mut match_found = false;
        while j < without_k.len() {
            if str_eq(with_k[i], without_k[j]) {
                match_found = true;
                break;
            }
            j += 1;
        }
        if !match_found {
            return false;
        }
        i += 1;
    }
    return true;
}

// Outputs a usize in order to make the array invalid by underflowing
// Alternatively this could use const_panic to produce good error messages
pub const fn check_valid_subset<S1: KeySchema, S2: KeySchema, const K: &'static str>() -> usize
where
    S1: ContainsKey<K>,
{
    let with_k: &[&'static str] = &S1::KEYS;
    let without_k: &[&'static str] = &S2::KEYS;

    if with_k.len() <= without_k.len() {
        // panic because S1 isn't bigger
        return (with_k.len() - 1) - without_k.len(); // panic using underflow
    }

    if !is_equivalent_except::<K>(with_k, without_k) {
        // panic because S2 doesn't have the rest of S1's elements
        return (without_k.len() - 1) - with_k.len(); // panic using underflow
    }

    return 1;
}

pub trait SubsetExcept<Parent: KeySchema, const K: &'static str>: KeySchema
where
    [(); Parent::SIZE - Self::SIZE]: Sized,
    Parent: ContainsKey<K>,
{
}

impl<Schema, PossibleParent, const K: &'static str> SubsetExcept<PossibleParent, K> for Schema
where
    Schema: KeySchema,
    PossibleParent: KeySchema,
    PossibleParent: ContainsKey<K>,
    [(); PossibleParent::SIZE - Schema::SIZE]: Sized,
    [(); check_valid_subset::<PossibleParent, Schema, K>()]: Sized,
{
}

impl<Tail, const KEY_ID: &'static str> KeySchema for KeyCons<Tail, KEY_ID>
where
    Tail: KeySchema,
    [(); compute_successor_size::<Tail>()]: Sized,
{
    const KEYS: &'static [&'static str] = &construct_successor_array::<Tail>(KEY_ID);
    const SIZE: usize = compute_successor_size::<Tail>();
}

// thanks to matt1992#5582 on the Rust Programming Language Community Discord for offering this strategy
// a const expression calls a function, which provides a "proof" that a given type should always use a given implementation
pub trait ContainsKeyHelper<const IS_EQUAL: bool, const K: &'static str> {}

const fn contains_key_helper_helper<const KEY_ID: &'static str, const K: &'static str>() -> bool
{
    str_eq(KEY_ID, K)
}
impl<Tail, const KEY_ID: &'static str, const K: &'static str> ContainsKey<K>
    for KeyCons<Tail, KEY_ID>
where
    Tail: KeySchema,
    Self: ContainsKeyHelper<{ contains_key_helper_helper::<KEY_ID, K>() }, K>,
{
}

impl<Tail, const KEY_ID: &'static str, const K: &'static str> ContainsKeyHelper<false, K>
    for KeyCons<Tail, KEY_ID>
where
    Tail: KeySchema + ContainsKey<K>,
{
}

impl<Tail, const KEY_ID: &'static str, const K: &'static str> ContainsKeyHelper<true, K>
    for KeyCons<Tail, KEY_ID>
where
    Tail: KeySchema,
{
}

pub struct RestrictedStringMap<S: KeySchema> {
    inner: HashMap<&'static str, Option<String>>,
    // schemas should be 0-sized, but I use a phantom data here just to emphasize that there's no data dependency
    _schema: PhantomData<S>,
}
impl<S: KeySchema, const K: &'static str> ContainsKey<K> for RestrictedStringMap<S> where
    S: ContainsKey<K>
{
}
impl<S: KeySchema> RestrictedStringMap<S>
where
    [(); compute_successor_size::<S>()]: Sized,
{
    pub fn empty_schema() -> RestrictedStringMap<KeyNil> {
        RestrictedStringMap::<_> {
            inner: HashMap::new(),
            // schemas should be 0-sized, but I use a phantom data here just to emphasize that there's no data dependency
            _schema: PhantomData::<_>,
        }
    }

    pub fn new() -> Self {
        let mut hm: HashMap<&'static str, Option<String>> = HashMap::new();

        for k in S::KEYS {
            hm.insert(*k, None);
        }

        hm.shrink_to_fit();

        Self {
            inner: hm,
            _schema: PhantomData::<_>,
        }
    }

    /// Adds a possible &'static str to the HashMap.
    /// This requires consuming the map since our type must change to reflect the new schema.
    pub fn add_key<const K: &'static str>(self) -> RestrictedStringMap<KeyCons<S, K>>
    where
        // Proof asserting that one size larger is still a valid schema
        // this should only be untrue if the number of keys exceeds usize::MAX
        [(); compute_successor_size::<S>()]: Sized,
    {
        let Self { mut inner, .. } = self;
        inner.insert(K, None);
        RestrictedStringMap::<_> {
            inner: inner,
            _schema: PhantomData::<_>,
        }
    }

    // I don't know of a way to remove the &'static str other than having the user provide their own new schema.
    // This is because I can't use a dependently typed function to construct a return type.
    // That's the only way I can think of to compute what the return type of such a function would look like without user input.
    pub fn remove_key<NewSchema: KeySchema, const K: &'static str>(
        self,
    ) -> RestrictedStringMap<NewSchema>
    where
        Self: ContainsKey<K>,
        S: ContainsKey<K>,
        // the schema that the user provides must be a valid subset of the old schema
        NewSchema: SubsetExcept<S, K>,
        [(); S::SIZE - NewSchema::SIZE]: Sized,
    {
        let Self { mut inner, .. } = self;
        inner.remove(&K);
        RestrictedStringMap::<_> {
            inner: inner,
            _schema: PhantomData::<_>,
        }
    }
}

#[cfg(test)]
mod static_string_map_tests {
    use super::*;
    #[test]
    fn tests() {
        let map: RestrictedStringMap<KeyNil> = RestrictedStringMap::<KeyNil>::empty_schema();
        let mut map: RestrictedStringMap<KeyCons<KeyCons<KeyNil, "k1">, "k2">> =
            map.add_key::<"k1">().add_key::<"k2">();
        let map: RestrictedStringMap<KeyCons<KeyNil, "k1">> = map.remove_key::<_, "k2">();
    }
}

fn main() {
    println!("Hello, world!");
}

Meta

rustc --version --verbose:

rustc 1.57.0-nightly (2c7bc5e33 2021-09-15)
binary: rustc
commit-hash: 2c7bc5e33c25e29058cbafefe680da8d5e9220e9
commit-date: 2021-09-15
host: x86_64-pc-windows-msvc
release: 1.57.0-nightly
LLVM version: 13.0.0

This ICE also appears on the playground.

Error output

$ cargo test
   Compiling restricted-hashmap v0.1.0 (<my_drive>\restricted-hashmap)
warning: the feature `adt_const_params` is incomplete and may not be safe to use and/or cause compiler crashes
 --> src\main.rs:1:12
  |
1 | #![feature(adt_const_params)]
  |            ^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(incomplete_features)]` on by default
  = note: see issue #44580 <https://github.com/rust-lang/rust/issues/44580> for more information

warning: the feature `generic_const_exprs` is incomplete and may not be safe to use and/or cause compiler crashes
 --> src\main.rs:2:12
  |
2 | #![feature(generic_const_exprs)]
  |            ^^^^^^^^^^^^^^^^^^^
  |
  = note: see issue #76560 <https://github.com/rust-lang/rust/issues/76560> for more information

warning: unused variable: `map`
   --> src\main.rs:256:13
    |
256 |         let map: RestrictedStringMap<KeyCons<KeyNil, "k1">> = map.remove_key::<_, "k2">();
    |             ^^^ help: if this is intentional, prefix it with an underscore: `_map`
    |
    = note: `#[warn(unused_variables)]` on by default

thread 'rustc' panicked at 'Unknown variable: 0', compiler\rustc_ty_utils\src\instance.rs:46:17
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/issues/new?labels=C-bug%2C+I-ICE%2C+T-compiler&template=ice.md

note: rustc 1.57.0-nightly (2c7bc5e33 2021-09-15) running on x86_64-pc-windows-msvc

note: compiler flags: -C embed-bitcode=no -C debuginfo=2 -C incremental

note: some of the compiler flags provided by cargo are hidden

query stack during panic:
thread 'rustc' panicked at 'substs of instance DefId(0:14 ~ restricted_hashmap[71dd]::KeySchema::SIZE) not normalized for codegen: [KeyCons<KeyNil, "k1">]', compiler\rustc_middle\src\ty\instance.rs:286:9
stack backtrace:
   0:     0x7ff959487acf - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h342cfc1ba001a676
   1:     0x7ff9594b25fa - core::fmt::write::h6ee6bf7a74285425
   2:     0x7ff95947acc8 - <std::io::IoSlice as core::fmt::Debug>::fmt::h17b1ea376e0c1040
   3:     0x7ff95948b5b6 - std::panicking::take_hook::h4296061bae338923
   4:     0x7ff95948b0a4 - std::panicking::take_hook::h4296061bae338923
   5:     0x7ff9185cabf5 - <tracing_subscriber::fmt::writer::TestWriter as std::io::Write>::flush::hf3a8e2c91526b5de
   6:     0x7ff95948bec9 - std::panicking::rust_panic_with_hook::ha779c25870ce0d16
   7:     0x7ff95948b96b - rust_begin_unwind
   8:     0x7ff959488417 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h342cfc1ba001a676
   9:     0x7ff95948b8c9 - rust_begin_unwind
  10:     0x7ff9594e843c - std::panicking::begin_panic_fmt::h5143997943c25f25
  11:     0x7ff91ca4ff22 - rustc_middle::ty::instance::Instance::new::h58316db868a53f6e
  12:     0x7ff91bc723a4 - rustc_query_impl::<impl rustc_query_system::query::config::QueryAccessors<rustc_query_impl::plumbing::QueryCtxt> for rustc_query_impl::queries::limits>::hash_result::h20a077ec97750c6d
  13:     0x7ff91bca1f3c - rustc_query_impl::<impl rustc_query_system::query::config::QueryAccessors<rustc_query_impl::plumbing::QueryCtxt> for rustc_query_impl::queries::limits>::hash_result::h20a077ec97750c6d
  14:     0x7ff91bb91cc9 - <rustc_mir_dataflow::move_paths::abs_domain::AbstractType as core::fmt::Debug>::fmt::h8b62500dcb970d5e
  15:     0x7ff91bd46ab4 - rustc_query_impl::Queries::new::h9a4baaccfd058802
  16:     0x7ff91bc4acce - <rustc_mir_dataflow::move_paths::abs_domain::AbstractType as core::fmt::Debug>::fmt::h8b62500dcb970d5e
  17:     0x7ff9187bb677 - rustc_interface::interface::try_print_query_stack::hac1fcf40214f4a7b
  18:     0x7ff9185dba35 - rustc_driver::report_ice::h1f24ef77b729f9ed
  19:     0x7ff95948bec9 - std::panicking::rust_panic_with_hook::ha779c25870ce0d16
  20:     0x7ff95948b96b - rust_begin_unwind
  21:     0x7ff959488417 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h342cfc1ba001a676
  22:     0x7ff95948b8c9 - rust_begin_unwind
  23:     0x7ff9594e843c - std::panicking::begin_panic_fmt::h5143997943c25f25
  24:     0x7ff91b1274e2 - rustc_ty_utils::instance::provide::hc2a45cf611c0a117
  25:     0x7ff91b124012 - rustc_ty_utils::instance::provide::hc2a45cf611c0a117
  26:     0x7ff91be1d80c - rustc_query_impl::on_disk_cache::__ty_decoder_impl::<impl rustc_serialize::serialize::Decoder for rustc_query_impl::on_disk_cache::CacheDecoder>::error::hddf217cc58743922
  27:     0x7ff91bdbd456 - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  28:     0x7ff91bcef672 - rustc_query_impl::profiling_support::alloc_self_profile_query_strings::h32189f35e5eeb88d
  29:     0x7ff91bc112f7 - <rustc_mir_dataflow::move_paths::abs_domain::AbstractType as core::fmt::Debug>::fmt::h8b62500dcb970d5e
  30:     0x7ff91bd4fcb6 - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  31:     0x7ff91ca55702 - rustc_middle::ty::instance::Instance::resolve_opt_const_arg::hd0e45fa8d543603d
  32:     0x7ff91c9b8592 - rustc_middle::mir::interpret::queries::<impl rustc_middle::ty::context::TyCtxt>::const_eval_resolve::h0edf7881a2b9d54d
  33:     0x7ff91c7cc9aa - <rustc_trait_selection::traits::query::normalize::QueryNormalizer as rustc_middle::ty::fold::TypeFolder>::fold_const::hcdecfce3ce2b4efa
  34:     0x7ff91c7ccb70 - <rustc_trait_selection::traits::query::normalize::QueryNormalizer as rustc_middle::ty::fold::TypeFolder>::fold_mir_const::h0ee425c1c312e6a6
  35:     0x7ff91b93e934 - <rustc_middle::ty::consts::Const as rustc_traits::chalk::lowering::LowerInto<chalk_ir::Const<rustc_middle::traits::chalk::RustInterner>>>::lower_into::h0b242d9bfec0ebf7
  36:     0x7ff91b86d452 - rustc_traits::provide::h2832a03d36b09929
  37:     0x7ff91b929ca4 - <rustc_middle::ty::sty::TraitRef as rustc_traits::chalk::lowering::LowerInto<chalk_solve::rust_ir::TraitBound<rustc_middle::traits::chalk::RustInterner>>>::lower_into::ha76f262a6fedabbb
  38:     0x7ff91be23bdc - rustc_query_impl::on_disk_cache::__ty_decoder_impl::<impl rustc_serialize::serialize::Decoder for rustc_query_impl::on_disk_cache::CacheDecoder>::error::hddf217cc58743922
  39:     0x7ff91bd87a0b - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  40:     0x7ff91bcef926 - rustc_query_impl::profiling_support::alloc_self_profile_query_strings::h32189f35e5eeb88d
  41:     0x7ff91bc2c8a8 - <rustc_mir_dataflow::move_paths::abs_domain::AbstractType as core::fmt::Debug>::fmt::h8b62500dcb970d5e
  42:     0x7ff91bd4f4bb - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  43:     0x7ff91b710db0 - <rustc_const_eval::const_eval::machine::MemoryKind as core::fmt::Debug>::fmt::h4cbc226550db7246
  44:     0x7ff91b6ce89e - rustc_const_eval::interpret::eval_context::mir_assign_valid_types::hc90d76d5cb9f7d32
  45:     0x7ff91b72765d - rustc_const_eval::const_eval::eval_queries::eval_to_allocation_raw_provider::h0a00d3cd803ba3c6
  46:     0x7ff91be1cd44 - rustc_query_impl::on_disk_cache::__ty_decoder_impl::<impl rustc_serialize::serialize::Decoder for rustc_query_impl::on_disk_cache::CacheDecoder>::error::hddf217cc58743922
  47:     0x7ff91bd8eb53 - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  48:     0x7ff91bcead16 - rustc_query_impl::profiling_support::alloc_self_profile_query_strings::h32189f35e5eeb88d
  49:     0x7ff91bc1a805 - <rustc_mir_dataflow::move_paths::abs_domain::AbstractType as core::fmt::Debug>::fmt::h8b62500dcb970d5e
  50:     0x7ff91bd4a86d - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  51:     0x7ff91b7240a0 - rustc_const_eval::const_eval::eval_queries::eval_to_const_value_raw_provider::h7c6df3f6760843cf
  52:     0x7ff91be1cd44 - rustc_query_impl::on_disk_cache::__ty_decoder_impl::<impl rustc_serialize::serialize::Decoder for rustc_query_impl::on_disk_cache::CacheDecoder>::error::hddf217cc58743922
  53:     0x7ff91bda63af - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  54:     0x7ff91bcdeab2 - rustc_query_impl::profiling_support::alloc_self_profile_query_strings::h32189f35e5eeb88d
  55:     0x7ff91bbe8eaa - <rustc_mir_dataflow::move_paths::abs_domain::AbstractType as core::fmt::Debug>::fmt::h8b62500dcb970d5e
  56:     0x7ff91bd4a8dd - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  57:     0x7ff91c98ab48 - rustc_middle::mir::interpret::queries::<impl rustc_middle::ty::context::TyCtxt>::const_eval_global_id::h5500487045595d12
  58:     0x7ff91c9b85f2 - rustc_middle::mir::interpret::queries::<impl rustc_middle::ty::context::TyCtxt>::const_eval_resolve::h0edf7881a2b9d54d
  59:     0x7ff91c86391a - rustc_infer::infer::InferCtxt::const_eval_resolve::h63a215128af233cc
  60:     0x7ff91c7b7ae7 - rustc_trait_selection::traits::const_evaluatable::is_const_evaluatable::h720b6cf39a3297b2
  61:     0x7ff91c725184 - rustc_trait_selection::traits::fulfill::FulfillProcessor::progress_changed_obligations::hc375055e042d6808
  62:     0x7ff91c76a3e8 - <rustc_trait_selection::traits::specialize::OverlapError as core::fmt::Debug>::fmt::hc009c74dcab86291
  63:     0x7ff91c723fbc - rustc_trait_selection::traits::fulfill::FulfillmentContext::new_ignoring_regions::h984cc50c29e431a4
  64:     0x7ff91c7247b8 - <rustc_trait_selection::traits::fulfill::FulfillmentContext as rustc_infer::traits::engine::TraitEngine>::select_where_possible::h8ffd7290e30f369c
  65:     0x7ff91b86ee9e - rustc_traits::provide::h2832a03d36b09929
  66:     0x7ff91b86a598 - rustc_traits::provide::h2832a03d36b09929
  67:     0x7ff91b8a180a - <rustc_middle::traits::chalk::ChalkEnvironmentAndGoal as rustc_traits::chalk::lowering::LowerInto<chalk_ir::InEnvironment<chalk_ir::Goal<rustc_middle::traits::chalk::RustInterner>>>>::lower_into::hc427bae7a5efc8d2
  68:     0x7ff91be24244 - rustc_query_impl::on_disk_cache::__ty_decoder_impl::<impl rustc_serialize::serialize::Decoder for rustc_query_impl::on_disk_cache::CacheDecoder>::error::hddf217cc58743922
  69:     0x7ff91bdacbdf - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  70:     0x7ff91bce9ac5 - rustc_query_impl::profiling_support::alloc_self_profile_query_strings::h32189f35e5eeb88d
  71:     0x7ff91bc01bec - <rustc_mir_dataflow::move_paths::abs_domain::AbstractType as core::fmt::Debug>::fmt::h8b62500dcb970d5e
  72:     0x7ff91bd4f669 - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  73:     0x7ff91c7bbdd7 - rustc_trait_selection::traits::query::type_op::ascribe_user_type::<impl rustc_trait_selection::traits::query::type_op::QueryTypeOp 
for rustc_middle::traits::query::type_op::AscribeUserType>::perform_query::haf266b700d91b6ae
  74:     0x7ff91b5b8d23 - <rustc_borrowck::constraints::graph::Reverse as core::fmt::Debug>::fmt::h154f94f1ab49d905
  75:     0x7ff91b63d767 - <rustc_borrowck::InitializationRequiringAction as core::fmt::Debug>::fmt::h7470bc523eb27e9d
  76:     0x7ff91b69b6db - <rustc_borrowck::location::RichLocation as core::fmt::Debug>::fmt::h9ad304d0418581a2
  77:     0x7ff91b69f36b - <rustc_borrowck::location::RichLocation as core::fmt::Debug>::fmt::h9ad304d0418581a2
  78:     0x7ff91b5ce815 - <rustc_borrowck::dataflow::BorrowIndex as rustc_mir_dataflow::framework::fmt::DebugWithContext<rustc_borrowck::dataflow::Borrows>>::fmt_with::he5c9f5dbd2c564b8
  79:     0x7ff91b62e1cc - rustc_borrowck::provide::hdfb9892d24be5102
  80:     0x7ff91b59eda0 - <rustc_borrowck::constraints::graph::Reverse as core::fmt::Debug>::fmt::h154f94f1ab49d905
  81:     0x7ff91b62cd79 - rustc_borrowck::provide::hdfb9892d24be5102
  82:     0x7ff91b5f874b - <rustc_borrowck::diagnostics::region_errors::ErrorConstraintInfo as core::fmt::Debug>::fmt::h222413fcafe75f3d
  83:     0x7ff91be1ba66 - rustc_query_impl::on_disk_cache::__ty_decoder_impl::<impl rustc_serialize::serialize::Decoder for rustc_query_impl::on_disk_cache::CacheDecoder>::error::hddf217cc58743922
  84:     0x7ff91bd82f8c - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  85:     0x7ff91bcd1621 - rustc_query_impl::profiling_support::alloc_self_profile_query_strings::h32189f35e5eeb88d
  86:     0x7ff91bb0bee3 - <rustc_mir_dataflow::move_paths::abs_domain::AbstractType as core::fmt::Debug>::fmt::h8b62500dcb970d5e
  87:     0x7ff91bd4a46d - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  88:     0x7ff91870321b - <rls_span::OneIndexed as core::fmt::Debug>::fmt::hf0520c7788563bf2
  89:     0x7ff91870c4ba - rustc_interface::passes::analysis::h83cea03508abe5ea
  90:     0x7ff91be19ccb - rustc_query_impl::on_disk_cache::__ty_decoder_impl::<impl rustc_serialize::serialize::Decoder for rustc_query_impl::on_disk_cache::CacheDecoder>::error::hddf217cc58743922
  91:     0x7ff91bd80a5b - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  92:     0x7ff91bce3462 - rustc_query_impl::profiling_support::alloc_self_profile_query_strings::h32189f35e5eeb88d
  93:     0x7ff91bb2e5b6 - <rustc_mir_dataflow::move_paths::abs_domain::AbstractType as core::fmt::Debug>::fmt::h8b62500dcb970d5e
  94:     0x7ff91bd47438 - <rustc_query_impl::Queries as rustc_middle::ty::query::QueryEngine>::try_mark_green::hc1a377735056b620
  95:     0x7ff918621aeb - <regex_syntax::hir::literal::Literal as core::convert::AsRef<[u8]>>::as_ref::hef8a3a16126ef78f
  96:     0x7ff9185e9ec5 - rustc_driver::pretty::print_after_hir_lowering::h4697bd9116993fd8
  97:     0x7ff918623387 - <regex_syntax::hir::literal::Literal as core::convert::AsRef<[u8]>>::as_ref::hef8a3a16126ef78f
  98:     0x7ff9185ee670 - <tracing_subscriber::util::TryInitError as core::fmt::Display>::fmt::h05e1aa411f5833f8
  99:     0x7ff9185ea728 - rustc_driver::pretty::print_after_hir_lowering::h4697bd9116993fd8
 100:     0x7ff9185defdd - <rustc_driver::Compilation as core::fmt::Debug>::fmt::hd354aca17f5d886d
 101:     0x7ff95949a1ac - std::sys::windows::thread::Thread::new::hd7c7d6731c34176f
 102:     0x7ff9ae997034 - BaseThreadInitThunk
 103:     0x7ff9afb42651 - RtlUserThreadStart

error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/issues/new?labels=C-bug%2C+I-ICE%2C+T-compiler&template=ice.md

note: rustc 1.57.0-nightly (2c7bc5e33 2021-09-15) running on x86_64-pc-windows-msvc

note: compiler flags: -C embed-bitcode=no -C debuginfo=2 -C incremental

note: some of the compiler flags provided by cargo are hidden

query stack during panic:
end of query stack
thread panicked while panicking. aborting.
warning: `restricted-hashmap` (bin "restricted-hashmap" test) generated 3 warnings
error: could not compile `restricted-hashmap`; 3 warnings emitted

Caused by:
  process didn't exit successfully: `rustc --crate-name restricted_hashmap --edition=2018 'src\main.rs' --error-format=json --json=diagnostic-rendered-ansi --emit=dep-info,link -C embed-bitcode=no -C debuginfo=2 --test -C metadata=e74c30747549fc79 -C extra-filename=-e74c30747549fc79 --out-dir '<my_drive>\restricted-hashmap\target\debug\deps' -C 'incremental=<my_drive>\restricted-hashmap\target\debug\incremental' -L 'dependency=<my_drive>\restricted-hashmap\target\debug\deps'` (exit code: 0xc000001d, STATUS_ILLEGAL_INSTRUCTION) 

Different ICE upon minimalization (playground link) (the error appears differently on the playground than on my local machine)

While attempting to minimize this example, I came across a different ICE when I removed the new function (since it was not used in the test) and made the contains_key_helper_helper function public. (For context, this function was just made to handle complaints that certain const expressions were too complex). The definitions for this ICE look like this:

pub const fn contains_key_helper_helper<const KEY_ID: &'static str, const K: &'static str>() -> bool {
    str_eq(KEY_ID, K)
}

impl<S: KeySchema> RestrictedStringMap<S>
where
    [(); compute_successor_size::<S>()]: Sized,
{
    pub fn empty_schema() -> RestrictedStringMap<KeyNil> {
        RestrictedStringMap::<_> {
            inner: HashMap::new(),
            // schemas should be 0-sized, but I use a phantom data here just to emphasize that there's no data dependency
            _schema: PhantomData::<_>,
        }
    }

    /// Adds a possible &'static str to the HashMap.
    /// This requires consuming the map since our type must change to reflect the new schema.
    pub fn add_key<const K: &'static str>(self) -> RestrictedStringMap<KeyCons<S, K>>
    where
        // Proof asserting that one size larger is still a valid schema
        // this should only be untrue if the number of keys exceeds usize::MAX
        [(); compute_successor_size::<S>()]: Sized,
    {
        let Self { mut inner, .. } = self;
        inner.insert(K, None);
        RestrictedStringMap::<_> {
            inner: inner,
            _schema: PhantomData::<_>,
        }
    }

    // I don't know of a way to remove the &'static str other than having the user provide their own new schema.
    // This is because I can't use a dependently typed function to construct a return type.
    // That's the only way I can think of to compute what the return type of such a function would look like without user input.
    pub fn remove_key<NewSchema: KeySchema, const K: &'static str>(
        self,
    ) -> RestrictedStringMap<NewSchema>
    where
        Self: ContainsKey<K>,
        S: ContainsKey<K>,
        // the schema that the user provides must be a valid subset of the old schema
        NewSchema: SubsetExcept<S, K>,
        [(); S::SIZE - NewSchema::SIZE]: Sized,
    {
        let Self { mut inner, .. } = self;
        inner.remove(&K);
        RestrictedStringMap::<_> {
            inner: inner,
            _schema: PhantomData::<_>,
        }
    }
}

The error message looks like this on my computer (but is different on the Playground):
The error on my computer appears to be from the same place as #88975

$ cargo test RUST_BACKTRACE=1
   Compiling restricted-hashmap v0.1.0 (<my_drive>\restricted-hashmap)
warning: the feature `adt_const_params` is incomplete and may not be safe to use and/or cause compiler crashes
 --> src\main.rs:1:12
  |
1 | #![feature(adt_const_params)]
  |            ^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(incomplete_features)]` on by default
  = note: see issue #44580 <https://github.com/rust-lang/rust/issues/44580> for more information

warning: the feature `generic_const_exprs` is incomplete and may not be safe to use and/or cause compiler crashes
 --> src\main.rs:2:12
  |
2 | #![feature(generic_const_exprs)]
  |            ^^^^^^^^^^^^^^^^^^^
  |
  = note: see issue #76560 <https://github.com/rust-lang/rust/issues/76560> for more information

thread 'rustc' panicked at 'attempted to read from stolen value', /rustc/2c7bc5e33c25e29058cbafefe680da8d5e9220e9\compiler\rustc_data_structures\src\steal.rs:37:21
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

error: internal compiler error: unexpected panic

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/issues/new?labels=C-bug%2C+I-ICE%2C+T-compiler&template=ice.md

note: rustc 1.57.0-nightly (2c7bc5e33 2021-09-15) running on x86_64-pc-windows-msvc

note: compiler flags: -C embed-bitcode=no -C debuginfo=2 -C incremental

note: some of the compiler flags provided by cargo are hidden

query stack during panic:
#0 [thir_abstract_const_of_const_arg] building an abstract representation for the const argument <impl at src\main.rs:154:1: 160:2>::{constant#0}
#1 [thir_abstract_const] building an abstract representation for <impl at src\main.rs:154:1: 160:2>::{constant#0}
end of query stack
warning: `restricted-hashmap` (bin "restricted-hashmap" test) generated 2 warnings
error: could not compile `restricted-hashmap`; 2 warnings emitted