ICE: Broken MIR equate_normalized_input_or_output: failed with `NoSolution`

[Manishearth]

This is related to #89196 and #85636 ; but is not the same issue: #85636 is already resolved and #89196 is dealing with a more complex case where inference is lacking.

Also perhaps related to #56556

I'm filing an ICE because that's what I'm hitting as I try to reduce it, however I have a related bug where the workaround from #85636 doesn't actually work. I wonder if fixing the ICE will make this code compile or if it will hit code that needs to be worked around (My unreduced code is at https://github.com/Manishearth/icu4x/tree/rm-rcstruct , cd provider/core && cargo check --all-features)

Code

Code

trait Yokeable<'a>: 'static {
    type Output: 'a;
}

trait IsCovariant<'a> {}

struct Yoke<Y: for<'a> Yokeable<'a>> {
    data: Y,
}


impl<Y: for<'a> Yokeable<'a>> Yoke<Y> {
    fn project<Y2: for<'a> Yokeable<'a>>(&self, f: for<'a> fn(<Y as Yokeable<'a>>::Output, &'a ()) -> <Y2 as Yokeable<'a>>::Output) -> Yoke<Y2> {
        unimplemented!()
    }
}

fn upcast<Y>(x: Yoke<Y>) -> Yoke<Box<dyn IsCovariant<'static> + 'static>> where
    Y: for<'a> Yokeable<'a>,
    for<'a> <Y as Yokeable<'a>>::Output: IsCovariant<'a>
    {
    x.project(|data, _| {
        Box::new(data)
    })
}


impl<'a> Yokeable<'a> for Box<dyn IsCovariant<'static> + 'static> {
    type Output = Box<dyn IsCovariant<'a> + 'a>;
}

// this impl is mostly an example and unnecessary for the pure repro
use std::borrow::Cow;
impl<'a, T: Clone> Yokeable<'a> for Cow<'static, T> {
    type Output = Cow<'a, T>;
}
impl<'a, T: Clone> IsCovariant<'a> for Cow<'a, T> {}
fn main() {}

Meta

rustc --version --verbose:

<version>

playpen

Error output

error: internal compiler error: broken MIR in DefId(0:23 ~ test[68ae]::upcast::{closure#0}) (bb0[0]): equate_normalized_input_or_output: `&[closure@test.rs:23:15: 25:6]==&[closure@test.rs:23:15: 25:6]` failed with `NoSolution`
  --> test.rs:23:15
   |
23 |       x.project(|data, _| {
   |  _______________^
24 | |         Box::new(data)
25 | |     })
   | |_____^
   |
   = note: delayed at compiler/rustc_borrowck/src/type_check/mod.rs:319:27

Backtrace

error: internal compiler error: broken MIR in DefId(0:23 ~ test[68ae]::upcast::{closure#0}) (bb0[0]): equate_normalized_input_or_output: `&[closure@test.rs:23:15: 25:6]==&[closure@test.rs:23:15: 25:6]` failed with `NoSolution`
  --> test.rs:23:15
   |
23 |       x.project(|data, _| {
   |  _______________^
24 | |         Box::new(data)
25 | |     })
   | |_____^
   |
   = note: delayed at compiler/rustc_borrowck/src/type_check/mod.rs:319:27

thread 'rustc' panicked at 'no errors encountered even though `delay_span_bug` issued', compiler/rustc_errors/src/lib.rs:1166:13
stack backtrace:
   0: rust_begin_unwind
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72/library/std/src/panicking.rs:495:5
   1: core::panicking::panic_fmt
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72/library/core/src/panicking.rs:107:14
   2: core::panicking::panic_display
   3: rustc_errors::HandlerInner::flush_delayed
   4: <rustc_errors::HandlerInner as core::ops::drop::Drop>::drop
   5: core::ptr::drop_in_place<rustc_session::parse::ParseSess>
   6: <alloc::rc::Rc<T> as core::ops::drop::Drop>::drop
   7: core::ptr::drop_in_place<rustc_interface::interface::Compiler>
   8: rustc_span::with_source_map
   9: scoped_tls::ScopedKey<T>::set
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

error: internal compiler error: unexpected panic

cc @jackh726 @eddyb

[jackh726]

Probably related to #88382

[b-naber]

I've looked into this:

The problem here is that we try to equate the normalized inputs_and_output (coming from here and being normalized here) with the unnormalized closure type from the mir.

The normalized input ty in this example corresponds to a closure with substs:
[Y, i8, for<'r> extern "rust-call" fn((<Y as Yokeable<'r>>::Output, &'r ())) -> std::boxed::Box<(dyn for<'r> IsCovariant<'r> + 'r)>, ()]

and the unnormalized input ty from the mir is a closure with substs:

[Y, i8, for<'r> extern "rust-call" fn((<Y as Yokeable<'r>>::Output, &'r ())) -> <std::boxed::Box<dyn IsCovariant<'_>> as Yokeable<'r>>::Output, ()]. This fails since the output types cannot be equalized.

We can make this compile by normalizing mir_input_ty (note that we cannot normalize the FnSig for the closure during typecheck since this leads to other type relation problems), but I feel that this misses the actual problem. I would expect that we would get problems when actually building this if some associated type in the mir is not normalized.

@Manishearth Can you give me an example including a main function that uses upcast? I had problems fulfilling the for<'a> <Y as Yokeable<'a>>::Output: IsCovariant<'a> bound when supplying an argument to upcast.

[jackh726]

Wait I'm a bit confused...does the hack that I added literally right there not work?

[b-naber]

Yes, that fails to normalize it.

[jackh726]

Ah, I see, it's a that is unnormalized. Can we just repeat the hack to normalize a? As you stated (and I found previously), this does miss the problem, but it's a difficult problem to solve.

[Manishearth]

@jackh726 trying to write the upcast displays the related bug that I was trying to reduce in the first place:

playpen

impl<'a> Yokeable<'a> for Box<dyn IsCovariant<'static> + 'static> {
    type Output = Box<dyn IsCovariant<'a> + 'a>;
}

// this impl is mostly an example and unnecessary for the pure repro
use std::borrow::*;
impl<'a, T: ToOwned + ?Sized> Yokeable<'a> for Cow<'static, T> {
    type Output = Cow<'a, T>;
}
impl<'a, T: ToOwned + ?Sized> IsCovariant<'a> for Cow<'a, T> {}

fn upcast_yoke(y: Yoke<Cow<'static, str>>) -> Yoke<Box<dyn IsCovariant<'static> + 'static>> {
    upcast(y)
}

which throws

error[E0277]: the trait bound `for<'a> <_ as Yokeable<'a>>::Output: IsCovariant<'a>` is not satisfied
  --> test.rs:41:5
   |
41 |     upcast(y)
   |     ^^^^^^ the trait `for<'a> IsCovariant<'a>` is not implemented for `<_ as Yokeable<'a>>::Output`
   |
note: required by a bound in `upcast`
  --> test.rs:21:42
   |
19 | fn upcast<Y>(x: Yoke<Y>) -> Yoke<Box<dyn IsCovariant<'static> + 'static>> where
   |    ------ required by a bound in this
20 |     Y: for<'a> Yokeable<'a>,
21 |     for<'a> <Y as Yokeable<'a>>::Output: IsCovariant<'a>
   |                                          ^^^^^^^^^^^^^^^ required by this bound in `upcast`

As mentioned before, this is along the same vein as #89196 and #85636 : The trait bound is satisfied by the type, rustc just can't figure it out.

[b-naber]

Ah, I see, it's a that is unnormalized. Can we just repeat the hack to normalize a? As you stated (and I found previously), this does miss the problem, but it's a difficult problem to solve.

@jackh726 No 'b' is unnormalized, the problem seems to be that an empty param_env is passed to normalize. I can open a PR for that. One question though, when we normalize a we add region constraints by using type_op::Normalize, can we ignore these constraints here?

[jackh726]

No 'b' is unnormalized

Ah I see; I was reading it as the first arg.

So,

a=for<'r> extern "rust-call" fn((<Y as Yokeable<'r>>::Output, &'r ())) -> std::boxed::Box<(dyn for<'r> IsCovariant<'r> + 'r)>
b=for<'r> extern "rust-call" fn((<Y as Yokeable<'r>>::Output, &'r ())) -> <std::boxed::Box<dyn IsCovariant<'_>> as Yokeable<'r>>::Output

In equate_input_and_output, the first eq fails, so we try to normalize b. Now, specifically, we need to normalize <std::boxed::Box<dyn IsCovariant<'_>> as Yokeable<'r>>::Output to std::boxed::Box<(dyn for<'r> IsCovariant<'r> + 'r)>. The question is why. We shouldn't need the param_env here. The problem might be related to the fact that the impl is implemented for the 'static lifetime whereas this looks like some inference region var (but that should just come out as region constraints which we maybe should ignore).

can we ignore these constraints here

We should be able to, yes.