ICE with higher order associated types

[LHolten]

Code

pub fn into_vec<'inner>(dummy: impl FromRow<'inner>) {
    let _f = dummy.prepare();
}

pub fn test() {
    into_vec(Assume(Some("test")));
}

pub trait FromRow<'t> {
    type Out<'a>;
    fn prepare(self) -> impl for<'a> FnMut(&'a ()) -> Self::Out<'a>;
}

impl<'t, T: Value<'t, Typ: MyTyp>> FromRow<'t> for T {
    type Out<'a> = <T::Typ as MyTyp>::Out<'a>;

    fn prepare(self) -> impl for<'a> FnMut(&'a ()) -> Self::Out<'a> {
        move |_| loop {}
    }
}

pub struct Assume<A>(pub(crate) A);

impl<'t, T, A: Value<'t, Typ = Option<T>>> Value<'t> for Assume<A> {
    type Typ = T;
}

pub trait Value<'t> {
    type Typ;
}

impl<'t> Value<'t> for &str {
    type Typ = String;
}

impl<'t, T: Value<'t, Typ = X>, X: MyTyp> Value<'t> for Option<T> {
    type Typ = Option<T::Typ>;
}

pub trait MyTyp: 'static {
    type Out<'t>;
}

impl MyTyp for String {
    type Out<'t> = Self;
}

Meta

rustc --version --verbose:

rustc 1.82.0-nightly (5aea14073 2024-08-20)
binary: rustc
commit-hash: 5aea14073eee9e403c3bb857490cd6aa4a395531
commit-date: 2024-08-20
host: x86_64-unknown-linux-gnu
release: 1.82.0-nightly
LLVM version: 19.1.0

Error output

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

Backtrace

thread 'rustc' panicked at compiler/rustc_codegen_llvm/src/debuginfo/metadata/type_map.rs:52:9:
assertion `left == right` failed
  left: Closure(DefId(0:19 ~ rust_query[ff33]::{impl#0}::prepare::{closure#0}), ['{erased}, Assume<std::option::Option<&'{erased} str>>, i16, Binder { value: extern "RustCall" fn((&'^0 (),)) -> Alias(Projection, AliasTy { args: [std::string::String, '^0], def_id: DefId(0:37 ~ rust_query[ff33]::MyTyp::Out), .. }), bound_vars: [Region(BrAnon)] }, ()])
 right: Closure(DefId(0:19 ~ rust_query[ff33]::{impl#0}::prepare::{closure#0}), ['{erased}, Assume<std::option::Option<&'{erased} str>>, i16, Binder { value: extern "RustCall" fn((&'^0 (),)) -> std::string::String, bound_vars: [Region(BrAnon)] }, ()])
stack backtrace:
   0: rust_begin_unwind
   1: core::panicking::panic_fmt
   2: core::panicking::assert_failed_inner
   3: core::panicking::assert_failed::<rustc_middle::ty::Ty, rustc_middle::ty::Ty>
   4: rustc_codegen_llvm::debuginfo::metadata::type_di_node
   5: rustc_codegen_ssa::mir::codegen_mir::<rustc_codegen_llvm::builder::Builder>
   6: rustc_codegen_llvm::base::compile_codegen_unit::module_codegen
   7: <rustc_codegen_llvm::LlvmCodegenBackend as rustc_codegen_ssa::traits::backend::ExtraBackendMethods>::compile_codegen_unit
   8: <rustc_codegen_llvm::LlvmCodegenBackend as rustc_codegen_ssa::traits::backend::CodegenBackend>::codegen_crate
   9: <rustc_interface::queries::Linker>::codegen_and_build_linker
  10: rustc_interface::interface::run_compiler::<core::result::Result<(), rustc_span::ErrorGuaranteed>, rustc_driver_impl::run_compiler::{closure#0}>::{closure#1}
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

rustc-ice-2024-08-21T20_21_27-40569.txt

[jdonszelmann]

Can be somewhat reproduced on stable with

pub fn into_vec<'inner>(dummy: impl FromRow<'inner>) {
    let _f = dummy.prepare();
}

pub fn test() {
    into_vec(Assume(Some("test")));
}

pub trait FromRow<'t> {
    type Out<'a>;
    fn prepare(self) -> impl for<'a> FnMut(&'a ()) -> Self::Out<'a>;
}

impl<'t, T: Value<'t>> FromRow<'t> for T
where
    <T as Value<'t>>::Typ: MyTyp,
{
    type Out<'a> = <T::Typ as MyTyp>::Out<'a>;

    fn prepare(self) -> impl for<'a> FnMut(&'a ()) -> Self::Out<'a> {
        move |_| loop {}
    }
}

pub struct Assume<A>(pub(crate) A);

impl<'t, T, A: Value<'t, Typ = Option<T>>> Value<'t> for Assume<A> {
    type Typ = T;
}

pub trait Value<'t> {
    type Typ;
}

impl<'t> Value<'t> for &str {
    type Typ = String;
}

impl<'t, T: Value<'t, Typ = X>, X: MyTyp> Value<'t> for Option<T> {
    type Typ = Option<T::Typ>;
}

pub trait MyTyp: 'static {
    type Out<'t>;
}

impl MyTyp for String {
    type Out<'t> = Self;
}

giving

WARN rustc_codegen_ssa::mir::locals Unexpected initial operand type: expected Closure(DefId(0:19 ~ unnamed_1[0fad]::{impl#0}::prepare::{closure#0}), [ReErased, Assume<s
td::option::Option<&ReErased str>>, i16, Binder(extern "RustCall" fn((&ReBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrAnon }) (),)) -> Alias(Projection, AliasT
y { args: [std::string::String, ReBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrAnon })], def_id: DefId(0:41 ~ unnamed_1[0fad]::MyTyp::Out) }), [Region(BrAnon)]
), ()]), found Closure(DefId(0:19 ~ unnamed_1[0fad]::{impl#0}::prepare::{closure#0}), [ReErased, Assume<std::option::Option<&ReErased str>>, i16, Binder(extern "RustCal
l" fn((&ReBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrAnon }) (),)) -> std::string::String, [Region(BrAnon)]), ()]).See <https://github.com/rust-lang/rust/iss
ues/114858>.

(but no ICE)

warning links to #114858 and seems related although the setup is very different

It seems like this is a bug in normalization somewhere, but this specific ICE happens as part of getting debug info for types. So, building in release (or rather, without debug info) actually prevents the ICE but then still hits the same warning.

[jdonszelmann]

So in that sense (last part of last comment) this ICE was technically introduced by #127995 though the root cause is certainly not that and seems to be the same as #114858

[cyrgani]

Slightly reduced:

fn into_vec(dummy: impl FromRow) {
    let _f = dummy.prepare();
}

pub fn test() {
    into_vec(Assume(()));
}

trait FromRow {
    type Out<'a>;
    fn prepare(self) -> impl for<'a> FnMut(&'a ()) -> Self::Out<'a>;
}

impl<T: Value<Typ: MyTyp>> FromRow for T {
    type Out<'a> = <T::Typ as MyTyp>::Out<'a>;
    fn prepare(self) -> impl for<'a> FnMut(&'a ()) -> Self::Out<'a> {
        |_| loop {}
    }
}

struct Assume<A>(A);

impl<T, A: Value<Typ = T>> Value for Assume<A> {
    type Typ = T;
}

trait Value {
    type Typ;
}

impl Value for () {
    type Typ = ();
}

trait MyTyp {
    type Out<'t>;
}

impl MyTyp for () {
    type Out<'t> = ();
}

[jdonszelmann]

So I had my own smaller reproducer, but still bigger than @cyrgani. However, after seeing theirs, I minimized it further similar to @cyrgani's version, except some of my comments might be useful. They're based on tracing the right parts of the compiler:

pub struct Wrapper<T>(T);
struct Struct;

pub trait TraitA {
    // NEEDS TO BE GAT
    type AssocA<'t>;
}
pub trait TraitB {
    type AssocB;
}

pub fn helper(v: impl MethodTrait) {
    // monomorphization instantiates something it then normalizes to:
    //
    // Closure(
    //   DefId(0:27 ~ unnamed_1[00e7]::{impl#0}::method::{closure#0}),
    //   [
    //     Wrapper1<StructX>,
    //     i16,
    //     Binder {
    //       value: extern "RustCall" fn((&'^0 (),)) -> Alias(Projection, AliasTy { args: [StructX, '^0], def_id: DefId(0:10 ~ unnamed_1[00e7]::TraitA::AssocA), .. }),
    //       bound_vars: [Region(BrAnon)]
    //     },
    //     ()
    //   ]
    // ),
    //
    // This should be completely normalized but isn't.
    // so, normalizing again gives (StructX is inserted) for
    // Alias(Projection, AliasTy { args: [StructX, '^0], def_id: DefId(0:10 ~ unnamed_1[00e7]::TraitA::AssocA), .. })
    //
    // Closure(
    //   DefId(0:27 ~ unnamed_1[00e7]::{impl#0}::method::{closure#0}),
    //   [
    //     Wrapper1<StructX>,
    //     i16,
    //     Binder {
    //       value: extern "RustCall" fn((&'^0 (),)) -> StructX, bound_vars: [Region(BrAnon)]
    //     },
    //     ()
    //   ]
    // ).
    let _local_that_causes_ice = v.method();
}

pub fn main() {
    helper(Wrapper(Struct));
}

pub trait MethodTrait {
    type Assoc<'a>;

    fn method(self) -> impl for<'a> FnMut(&'a ()) -> Self::Assoc<'a>;
}

impl<T: TraitB> MethodTrait for T
where
    <T as TraitB>::AssocB: TraitA,
{
    type Assoc<'a> = <T::AssocB as TraitA>::AssocA<'a>;

    // must be a method (through Self), the example below doesn't work (as a standalone function)
    // fn helper2<M: MethodTrait>(_v: M) -> impl for<'a> FnMut(&'a ()) -> M::Assoc<'a> {
    //    move |_| loop {}
    // }
    fn method(self) -> impl for<'a> FnMut(&'a ()) -> Self::Assoc<'a> {
        move |_| loop {}
    }
}

impl<T, B> TraitB for Wrapper<B>
where
    B: TraitB<AssocB = T>,
{
    type AssocB = T;
}

impl TraitB for Struct {
    type AssocB = Struct;
}

impl TraitA for Struct {
    type AssocA<'t> = Self;
}

So the specific ICE, like I said before, is essentially unrelated. It's because some debug assertion got changed into an actual assertion here. The problem is actually easier to see when you don't look at this assertion, but wait until the same root cause causes a warning later in the compiler when a sanity check is done here.

What's going on is that the warning triggers when the initialization of a MIR local doesn't match the type of its declaration. In this case we're talking about a ZST function item, and in that codepath, to get the type of the function item at the declaration site, the declaration type is monomorphized, and then layout_of is used. Both monomorphize and layout_of normalize, so the type is normalized twice.

However, to check for the warning the type is only monomorphized, causing only one normalization: here

As I show in my comment in the code example, the monomorphized type normalized once gives:

Closure(
  DefId(0:27 ~ unnamed_1[00e7]::{impl#0}::method::{closure#0}),
  [
    Wrapper1<StructX>,
    i16,
    Binder {
      value: extern "RustCall" fn((&'^0 (),)) -> Alias(Projection, AliasTy { args: [StructX, '^0], def_id: DefId(0:10 ~ unnamed_1[00e7]::TraitA::AssocA), .. }),
      bound_vars: [Region(BrAnon)]
    },
    ()
  ]
),

and the second normalization gives:

Closure(
  DefId(0:27 ~ unnamed_1[00e7]::{impl#0}::method::{closure#0}),
  [
    Wrapper1<StructX>,
    i16,
    Binder {
      value: extern "RustCall" fn((&'^0 (),)) -> StructX, bound_vars: [Region(BrAnon)]
    },
    ()
  ]
)

which, notably, is different!

For some reason the first normalization round, rust is happy to normalize to something still containing a Projection which is normalized away in round two.

In the assertion that causes the ICE, essentially the same happens. The compiler sees if normalizing is idempotent and doesn't change the type anymore, but it still does.

[jdonszelmann]

Well, I thought I tried this at the start, but apparently not. Dumb me, whatever. The next solver (#107374) fixes all this so this will soon be a non-issue.

Try it with RUSTFLAGS="-Znext-solver"

[cyrgani]

@rustbot label +S-bug-has-test

[rustbot]

Error: Label fixed-by-next-solver can only be set by Rust team members

Please file an issue on GitHub at triagebot if there's a problem with this bot, or reach out on #t-infra on Zulip.