Rust: ICE rink: higher-rank trait bound (HRTB) `for<'a> ...` hits OutputTypeParameterMismatch in librustc/traits/codegen

[pnkfelix]

I have seen many OutputTypeParameterMismatch ICEs filed, so I decided to try to make a single representative issue for all of them.

• Its possible that not all of these share the same root cause. But until I see a more fine grain way to categorize them, I'm going to at least try to track them in a single place.

Below are transcribed minimized versions of each of the original issues, labelled accordingly, so that we remember to double check each of their behavior before closing this issue as fixed in the future.

60070 (play):

Click to expand the code for minimized example

// FamilyType (GAT workaround)
pub trait FamilyLt<'a> {
    type Out;
}

struct RefMutFamily<T>(std::marker::PhantomData<T>, ());
impl<'a, T: 'a> FamilyLt<'a> for RefMutFamily<T> {
    type Out = &'a mut T;
}

pub trait Execute {
    type E: Inject;
    fn execute(self, value: <<Self::E as Inject>::I as FamilyLt>::Out);
}

pub trait Inject
where
    Self: Sized,
{
    type I: for<'a> FamilyLt<'a>;
    fn inject(_: &()) -> <Self::I as FamilyLt>::Out;
}

impl<T: 'static> Inject for RefMutFamily<T> {
    type I = Self;
    fn inject(_: &()) -> <Self::I as FamilyLt>::Out {
        unimplemented!()
    }
}

// This struct is only used to give a hint to the compiler about the type `Q`
struct Annotate<Q>(std::marker::PhantomData<Q>);
impl<Q> Annotate<Q> {
    fn new() -> Self {
        Self(std::marker::PhantomData)
    }
}

// This function annotate a closure so it can have Higher-Rank Lifetime Bounds
//
// See 'annotate' workaround: https://github.com/rust-lang/rust/issues/58052
fn annotate<F, Q>(_q: Annotate<Q>, func: F) -> impl Execute + 'static
where
    F: for<'r> FnOnce(<<Q as Inject>::I as FamilyLt<'r>>::Out) + 'static,
    Q: Inject + 'static,
{
    let wrapper: Wrapper<Q, F> = Wrapper(std::marker::PhantomData, func);
    wrapper
}

struct Wrapper<Q, F>(std::marker::PhantomData<Q>, F);
impl<Q, F> Execute for Wrapper<Q, F>
    where
        Q: Inject,
        F: for<'r> FnOnce(<<Q as Inject>::I as FamilyLt<'r>>::Out),
{
    type E = Q;

    fn execute(self, value: <<Self::E as Inject>::I as FamilyLt>::Out) {
        (self.1)(value)
    }
}

struct Task {
    _processor: Box<dyn FnOnce()>,
}

// This function consume the closure
fn task<P>(processor: P) -> Task
where P: Execute + 'static {
    Task {
        _processor: Box::new(move || {
            let q = P::E::inject(&());
            processor.execute(q);
        })
    }
}

fn main() {
    task(annotate(
        Annotate::<RefMutFamily<usize>>::new(),
        |value: &mut usize| {
            *value = 2;
        }
    ));
}

57485 (play):

Click to expand the code for minimized example

use std::marker::PhantomData;
use std::mem;

trait Container<'a> {
    type Root: 'a;
}

type RootOf<'a, T> = <T as Container<'a>>::Root;

struct Test<'a, T> where T: Container<'a> {
    pub root: T::Root,
    marker: PhantomData<&'a mut &'a mut ()>,
}

impl<'a, 'b> Container<'b> for &'a str {
    type Root = &'b str;
}

impl<'a, T> Test<'a, T> where T: for<'b> Container<'b> {
    fn new(root: RootOf<'a, T>) -> Test<'a, T> {
        Test {
            root: root,
            marker: PhantomData
        }
    }

    fn with_mut<F, R>(&mut self, f: F) -> R where
            F: for<'b> FnOnce(&'b mut RootOf<'b, T>) -> R {
        f(unsafe { mem::transmute(&mut self.root) })
    }
}

fn main() {
    let val = "root";
    let mut test: Test<&str> = Test::new(val);
    test.with_mut(|_| { });
}

53420 (play):

Click to expand the code for minimized example

use std::marker::PhantomData;

trait Lt<'a> {
    type T;
}
struct Id<T>(PhantomData<T>);
impl<'a,T> Lt<'a> for Id<T> {
    type T = T;
}

struct Ref<T>(PhantomData<T>) where T: ?Sized;
impl<'a,T> Lt<'a> for Ref<T>
where T: 'a + Lt<'a> + ?Sized
{
    type T = &'a T;
}
struct Mut<T>(PhantomData<T>) where T: ?Sized;
impl<'a,T> Lt<'a> for Mut<T>
where T: 'a + Lt<'a> + ?Sized
{
    type T = &'a mut T;
}

struct C<I,O>(for<'a> fn(<I as Lt<'a>>::T) -> O) where I: for<'a> Lt<'a>;


fn main() {
    let c = C::<Id<_>,_>(|()| 3);
    c.0(());

}

52812 (play):

Click to expand the code for minimized example

trait ATC<'a> {
    type Type: Sized;
}

trait WithDefault: for<'a> ATC<'a> {
    fn with_default<F: for<'a> Fn(<Self as ATC<'a>>::Type)>(f: F);
}

fn call<'b, T: for<'a> ATC<'a>, F: for<'a> Fn(<T as ATC<'a>>::Type)>(
    f: F,
    x: <T as ATC<'b>>::Type,
) {
    f(x);
}

impl<'a> ATC<'a> for () {
    type Type = Self;
}

impl WithDefault for () {
    fn with_default<F: for<'a> Fn(<Self as ATC<'a>>::Type)>(f: F) {
        // Errors with a bogus type mismatch.
        //f(());
        // Going through another generic function works fine.
        call(f, ());
    }
}

fn main() {
    // <()>::with_default(|_| {});
}

50886 (play):

Click to expand the code for minimized example

pub struct Struct {}

pub trait Trait<'a> {
    type Assoc;

    fn method() -> Self::Assoc;
}

impl<'a> Trait<'a> for Struct {
    type Assoc = ();

    fn method() -> Self::Assoc {}
}

pub fn function<F, T>(f: F)
where
    F: for<'a> FnOnce(<T as Trait<'a>>::Assoc),
    T: for<'b> Trait<'b>,
{
    f(T::method());
}

fn main() {
    function::<_, Struct>(|_| {});
}

48112 (play):

Click to expand the code for minimized example

use std::cell::RefMut;

fn main() {
    StateMachine2::Init.resume();
}

enum StateMachine2<'a> {
    Init,
    #[allow(dead_code)] // match required for ICE
    AfterTwoYields {
        p: Backed<'a, *mut String>,
    },
}

impl<'a> StateMachine2<'a> {
    fn take(&self) -> Self {
        StateMachine2::Init
    }
}

impl<'a> StateMachine2<'a> {
    fn resume(&mut self) -> () {
        use StateMachine2::*;
        match self.take() {
            AfterTwoYields { p } => {
                p.with(|_| {});
            }
            _ => panic!("Resume after completed."),
        }
    }
}

unsafe trait Unpack<'a> {
    type Unpacked: 'a;

    fn unpack(&self) -> Self::Unpacked {
        unsafe { std::mem::transmute_copy(&self) }
    }
}

unsafe trait Pack {
    type Packed;

    fn pack(&self) -> Self::Packed {
        unsafe { std::mem::transmute_copy(&self) }
    }
}

unsafe impl<'a> Unpack<'a> for String {
    type Unpacked = String;
}

unsafe impl Pack for String {
    type Packed = String;
}

unsafe impl<'a> Unpack<'a> for *mut String {
    type Unpacked = &'a mut String;
}

unsafe impl<'a> Pack for &'a mut String {
    type Packed = *mut String;
}

struct Backed<'a, U>(RefMut<'a, Option<String>>, U);

impl<'a, 'b, U: Unpack<'b>> Backed<'a, U> {
    fn with<F>(self, f: F) -> Backed<'a, ()>
    where
        F: for<'f> FnOnce(<U as Unpack<'f>>::Unpacked) -> (),
    {
        let result = f(self.1.unpack());
        Backed(self.0, result)
    }
}

42950 (play):

Click to expand the code for minimized example

struct D;

trait Tr {
    type It;
    fn foo(self) -> Option<Self::It>;
}

impl<'a> Tr for &'a D {
    type It = ();
    fn foo(self) -> Option<()> { None }
}

fn run<F>(f: F)
    where for<'a> &'a D: Tr,
          F: Fn(<&D as Tr>::It),
{
    let d = &D;
    while let Some(i) = d.foo() {
        f(i);
    }
}

fn main() {
    run(|_| {});
}

• This one (and #29997) are potentially different/interesting because it has the for<'a> ... on the left-hand side of a constraint, where for<'a> &'a D: Tr; most of the other examples have it on the right-hand side

33364 (play):

Click to expand the code for minimized example

use std::marker::PhantomData;

trait Foo<'a> {
    type Item;
    fn consume<F>(self, f: F) where F: Fn(Self::Item);
}
struct Consume<A>(PhantomData<A>);

impl<'a, A:'a> Foo<'a> for Consume<A> {
    type Item = &'a A;

    fn consume<F>(self, _f: F) where F: Fn(Self::Item) {
        if blackbox() {
            _f(any()); // Gotta keep this (1.)
        }
    }
}

#[derive(Clone)]
struct Wrap<T> { foo: T }

impl<T: for <'a> Foo<'a>> Wrap<T> {
    fn consume<F>(self, f: F) where F: for <'b> Fn(<T as Foo<'b>>::Item) {
        self.foo.consume(f);
    }
}

fn main() {
    // This works
    Consume(PhantomData::<u32>).consume(|item| { let _a = item; });

    // This does not (but is only noticed if you call the closure).
    let _wrap = Wrap { foo: Consume(PhantomData::<u32>,) };
    _wrap.consume(|item| { let _a = item; }); // Gotta keep this (2.)
}

pub static mut FLAG: bool = false;
fn blackbox() -> bool { unsafe { FLAG } }
fn any<T>() -> T { loop { } }

https://github.com/rust-lang/rust/issues/30860#issuecomment-171075273 (play):

Click to expand the code for minimized example

use std::marker::PhantomData;

// Borrowing encoding of paramaterized types from
// https://github.com/rust-lang/rfcs/blob/master/text/0195-associated-items.md#encoding-higher-kinded-types

trait TypeWithLifetime<'a> {
    type Type: Copy;
}

// type At<'a,T> where T: TypeWithLifetime<'a> = T::Type;

struct Str;

impl<'a> TypeWithLifetime<'a> for Str {
    type Type = &'a str;
}

trait Consumer<T> where T: for<'a> TypeWithLifetime<'a> {
    fn accept(&mut self, arg: <T as TypeWithLifetime>::Type);
}

impl Consumer<Str> for String {
    fn accept(&mut self, arg: &str) { self.push_str(arg) }
}

struct FilterConsumer<F,T,C> {
    function: F,
    consumer: C,
    phantom: PhantomData<T>,
}

impl<F,T,C> Consumer<T> for FilterConsumer<F,T,C> where F: Fn(<T as TypeWithLifetime>::Type) -> bool, T: for<'a> TypeWithLifetime<'a>, C: Consumer<T> {
    fn accept(&mut self, arg: <T as TypeWithLifetime>::Type) {
        if (self.function)(arg) { self.consumer.accept(arg) }
    }
}

fn main() {
    let mut consumer = FilterConsumer{
        function: |x:<Str as TypeWithLifetime>::Type| x.chars().all(char::is_alphabetic),
        consumer: String::new(),
        phantom: PhantomData,
    };
    consumer.accept("hi");
}

29997 (play):

Click to expand the code for minimized #29997

trait Mirror { type Image; }
impl<T> Mirror for T { type Image = T; }

fn test<L,T>(l: L) where L: FnOnce(Option<<&T as Mirror>::Image>),
                         for<'a> &'a T: Mirror
{ l(None); }
fn main() {
    test::<_,u8>(|_| {});
}

• This one (and #42950) are potentially different/interesting because it has the for<'a> ... on the left-hand side of a constraint, where for<'a> &'a D: Tr; most of the other examples have it on the right-hand side

68578 (play):

Click to expand the code for minimized example

trait Trait { type Resources: Resources; }
impl Trait for () {
    type Resources = usize;
}


trait ResourceFamily<'a> { type Output; }

struct UsizeResourceFamily;
impl<'a> ResourceFamily<'a> for UsizeResourceFamily {
    type Output = &'a usize;
}

trait Resources { type Family: for<'a> ResourceFamily<'a>; }
impl Resources for usize {
    type Family = UsizeResourceFamily;
}

fn test<T: Trait>() {
    let _: Box<dyn Fn(&mut <<<T as Trait>::Resources as Resources>::Family as ResourceFamily>::Output)> = Box::new(|_| {});
}

fn main() {
    test::<()>();
}

70120

(needs its minimized example to be transcribed...)

70243

[pnkfelix]

There is a good chance that all of these would be resolved by implementing lazy normalization, #60471

[wagnerf42]

hi, I think I just go bitten by that too.

Not sure if you are interested but my code is here :
https://github.com/wagnerf42/rayon-adaptive/commit/8294776a3ac6fd86e84f98a1d87b8985b275bb11

it's not a minimized version, sorry.

i'm a bit sad, it took me so much time to write it. well, life is hard.

[Frizi]

Adding slightly smaller repro than any of the mentioned above (play).

trait Trait<'a> {
    type Out;
    fn out(self) -> Self::Out;
}
impl<'a> Trait<'a> for u8 {
    type Out = u8;
    fn out(self) -> Self::Out {
        self
    }
}
fn call<F, D>(d: D, f: F) where
    for<'a> D: Trait<'a>,
    for<'a> F: Fn(<D as Trait<'a>>::Out),
{
    f(d.out())
}
fn main() {
    call(5, |_| ());
}

Seems like the issue is actually triggered on f(d.out()) line, when the call function is monomorphised with the passed closure. Substituting that line with unimplemented!() macro makes the code compile.

Pretty-printed ICE:

OutputTypeParameterMismatch(
    Binder(<[closure@src/main.rs:21:13] as Fn<(<u8 as Trait<'_>>::Out)>>),
    Binder(<[closure@src/main.rs:21:13] as Fn<(u8)>>),
    Sorts(ExpectedFound {
        expected: u8,
        found: <u8 as Trait<'_>>::Out
    })
)

[Kixunil]

Heh, I just thought I can have ATC in Rust already. I have an example which doesn't work even when called through another generic function (unlike #52812 ).

[Ralith]

I think I hit this in https://github.com/Ralith/hecs/pull/20:

OutputTypeParameterMismatch(
    Binder(<[closure@src/world.rs:10:5: 10:26] as std::ops::FnMut<(hecs::Entity, <hecs::query::FetchRead<bool> as hecs::Fetch<'_>>::Item)>>),
    Binder(<[closure@src/world.rs:10:5: 10:26] as std::ops::FnMut<(hecs::Entity, &bool)>>),
    Sorts(ExpectedFound { expected: &bool, found: <hecs::query::FetchRead<bool> as hecs::Fetch<'_>>::Item })
)

selecting Binder(<[closure@src/world.rs:10:5: 10:26] as std::ops::FnMut<(hecs::Entity, &bool)>>) during codegen

[pnkfelix]

Nominating for discussion at compiler team meeting: Do we think we might try to address lazy-norm this year?

[abonander]

I just ran into this and put the time in to generate a minimal repro before I found this meta issue. I don't know if it's significantly different from all of the above cases but I'll provide it for posterity: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=1e916cf884e3b516691ae44455be31ca

[pnkfelix]

Discussed in T-compiler meeting.

There has been some movement on lazy-normalization this year. But its not something that we are actively prioritizing.

Removing nomination.

[abonander]

@pnkfelix I'd like to request that the team re-address this at the next meeting because this is requiring some ugly workarounds in SQLx:

• A special trait for each instantiation of QueryAs<DB>: https://github.com/launchbadge/sqlx/blob/283f0ef6d86729cdd6561b1ee2475fb3759d3024/sqlx-core/src/query_as.rs#L66
• Traits instead of taking closures directly for for<'a> FnMut(<DB as HasRow<'a>>::Row) -> ...:
  https://github.com/launchbadge/sqlx/blob/283f0ef6d86729cdd6561b1ee2475fb3759d3024/sqlx-core/src/query.rs#L207-L222

Additionally, lack of lazy normalization may be responsible for requiring this trait as otherwise the compiler tries to resolve an implementation of Executor for an infinitely recursive type that cannot actually exist in practice (PoolConnection<PoolConnection<PoolConnection<... even though PoolConnection cannot contain itself because it's generically bounded by a trait it does not implement):
https://github.com/launchbadge/sqlx/blob/283f0ef6d86729cdd6561b1ee2475fb3759d3024/sqlx-core/src/executor.rs#L62

(The comment mentions GATs which would also clean a lot of this up but that's orthogonal to this discussion.)

[Alfriadox]

It appears that #71955 may be related to this issue, if not a duplicate. Is there any known workaround? Also is there any progress being made on resolving this? Based on some of the other issues referenced here, this has been a consistent issue on every stable version of rust for at least 2 years. In my opinion, this should be a high priority issue.

[fanninpm]

Mind if I added these to the glacier?

[Alfriadox]

not quite sure what "the glacier" is but yes please do

[bjorn3]

https://github.com/rust-lang/glacier/ checks every day if ICEs still happen.