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 ICE OutputTypeParameterMismatch #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 { } }

#30860 (comment) (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 ICE on all current Rust channels #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 :
wagnerf42/rayon-adaptive@8294776

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 Ralith/hecs#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?

[Manishearth]

Here's another: #86703

[hellow554]

And yet another one #87531