ICE with "Encountered error `OutputTypeParameterMismatch" on stable rust

[nbliznashki]

I have encountered an ICE in stable rust, please see the code and error below. The issue seems to be present also on nightly and also older rust compiler versions like 1.45.

Code

trait ColumnOutput<'a, T> {
    type Output: Sized;
}

struct C;

impl<'a, T> ColumnOutput<'a, T> for C {
    type Output = T;
}

fn calc<'a, T1: Default, T2, O1, O2, F1>(f: F1)
where
    O1: ColumnOutput<'a, T1>,
    O2: ColumnOutput<'a, T2>,
    F1: Fn(&<O2 as ColumnOutput<T2>>::Output) -> T1,
{
    let c2_data: Vec<<O2 as ColumnOutput<T2>>::Output> = Vec::new();
    let mut dummy: Vec<T1> = Vec::new();
    dummy.extend(c2_data.iter().map(|c2_value| f(c2_value)));
}

pub fn run_calc() {
    calc::<u64, u64, C, C, _>(|c2_data| *c2_data)
}

fn main() {
    run_calc();
}

Meta

The ICE happens also on nightly

rustc --version --verbose:

<version>
rustc 1.48.0 (7eac88abb 2020-11-16)
binary: rustc
commit-hash: 7eac88abb2e57e752f3302f02be5f3ce3d7adfb4
commit-date: 2020-11-16
host: x86_64-pc-windows-msvc
release: 1.48.0
LLVM version: 11.0

Error output

<output>

error: internal compiler error: compiler\rustc_trait_selection\src\traits\codegen\mod.rs:75:17: Encountered error `OutputTypeParameterMismatch(Binder(<[closure@src\operations\generic_functions_3.rs:23:31: 23:49] as std::ops::Fn<(&<operations::generic_functions_3::C as operations::generic_functions_3::ColumnOutput<'_, u64>>::Output,)>>), Binder(<[closure@src\operations\generic_functions_3.rs:23:31: 23:49] as std::ops::Fn<(&u64,)>>), Sorts(ExpectedFound { expected: u64, found: 
<operations::generic_functions_3::C as operations::generic_functions_3::ColumnOutput<'_, u64>>::Output }))` selecting `Binder(<[closure@src\operations\generic_functions_3.rs:23:31: 23:49] as std::ops::Fn<(&u64,)>>)` during codegen

Backtrace

error: internal compiler error: compiler\rustc_trait_selection\src\traits\codegen\mod.rs:75:17: Encountered error `OutputTypeParameterMismatch(Binder(<[closure@src\operations\generic_functions_3.rs:23:31: 23:49] as std::ops::Fn<(&<operations::generic_functions_3::C as operations::generic_functions_3::ColumnOutput<'_, u64>>::Output,)>>), Binder(<[closure@src\operations\generic_functions_3.rs:23:31: 23:49] as std::ops::Fn<(&u64,)>>), Sorts(ExpectedFound { expected: u64, found: 
<operations::generic_functions_3::C as operations::generic_functions_3::ColumnOutput<'_, u64>>::Output }))` selecting `Binder(<[closure@src\operations\generic_functions_3.rs:23:31: 23:49] as std::ops::Fn<(&u64,)>>)` during codegen

thread 'rustc' panicked at 'Box<Any>', compiler\rustc_errors\src\lib.rs:945:9
stack backtrace:
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

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.48.0 (7eac88abb 2020-11-16) running on x86_64-pc-windows-msvc

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

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

query stack during panic:
#0 [codegen_fulfill_obligation] checking if `std::ops::Fn` fulfills its obligations
#1 [resolve_instance] resolving instance `<[closure@src\operations\generic_functions_3.rs:23:31: 23:49] as std::ops::Fn<(&u64,)>>::call`
#2 [collect_and_partition_mono_items] collect_and_partition_mono_items
#3 [exported_symbols] exported_symbols
end of query stack
<backtrace>

[nbliznashki]

if the trait bound on F1 is changed and a lifetime added, then the ICA disappears:

trait ColumnOutput<'a, T> {
    type Output: Sized;
}

struct C;

impl<'a, T> ColumnOutput<'a, T> for C {
    type Output = T;
}

fn calc<'a, T1: Default, T2, O1, O2, F1>(f: F1)
where
    O1: ColumnOutput<'a, T1>,
    O2: ColumnOutput<'a, T2>,
    F1: Fn(&<O2 as ColumnOutput<'a, T2>>::Output) -> T1, //Lifetime added
{
    let c2_data: Vec<<O2 as ColumnOutput<T2>>::Output> = Vec::new();
    let mut dummy: Vec<T1> = Vec::new();
    dummy.extend(c2_data.iter().map(|c2_value| f(c2_value)));
}

pub fn run_calc() {
    calc::<u64, u64, C, C, _>(|c2_data| *c2_data)
}

fn main() {
    run_calc();
}

[jyn514]

Minimized:

trait ColumnOutput<'a> {
    type Output;
}

struct C {}

impl<'a> ColumnOutput<'a> for C {
    type Output = u64;
}

fn calc<'a, O, F>(f: F)
where
    O: ColumnOutput<'a>,
    F: Fn(<O as ColumnOutput>::Output) -> u64,
{
    f(vec![].pop().unwrap());
}

fn main() {
    calc::<C, _>(|_| unimplemented!());
}

[jyn514]

I think the issue is that the lifetime of ColumnOutput is inferred to something other than 'a - if you change it to ColumnOutput<'a> or O::Output it works fine.

[steffahn]

AFAIK Fn(<O as ColumnOutput>::Output) is desugared to Fn(<O as ColumnOutput<'_>>::Output) which then desugars further to for<'b> Fn(<O as ColumnOutput<'b>>::Output). By the way, it is actually slightly surprising to me that writing such a higher-ranked trait bound even works with a type O for which only O: ColumnOutput<'a> for a single concrete lifetime 'a is known.

[jackh726]

Fixed by #85499, closing since lots of added tests cover this pattern