rustc seemingly generates invalid IR

[TChatzigiannakis]

I may have found a bug in the compiler.

Source

The entirety of the code to reproduce this bug is this:

fn main() {
    let callbacks = Callbacks::new();
    callbacks.type_error(|x| &x.field);
}

pub struct Callbacks {
    field: Vec<Box<Fn(&u8)>>,
}

impl Callbacks {
    pub fn new() -> Callbacks {
        Callbacks { field: Vec::new() }
    }

    pub fn no_type_error(&self, _selector: fn(&Callbacks) -> &Vec<Box<Fn(&u8)>>) {}
    pub fn type_error<T>(&self, _selector: fn(&Callbacks) -> &Vec<Box<Fn(T)>>) {}
}

Expected behavior

The program should build successfully, assuming the rustc type checker does not detect any errors at the level of the Rust type system.

Actual behavior

The rustc type checker seems happy with the program. However, presumably after the LLVM IR generation phase, and during some IR verification phase, I get this type error:

   Compiling some_program_name v0.1.0 (SomePath\some_program_name)
Function return type does not match operand type of return inst!
  ret %"alloc::vec::Vec<alloc::boxed::Box<core::ops::function::Fn<(&u8), Output=()>>>.0"* %6, !dbg !84
 %"alloc::vec::Vec<alloc::boxed::Box<core::ops::function::Fn<(&u8), Output=()>>>"*LLVM ERROR: Broken function found, compilation aborted!
error: Could not compile `some_program_name`.

[Centril]

Reduced:

fn main() {
    type_error(|x| &x);
}

fn type_error<T>(
    _selector:
        for<'a> fn(
            &'a Vec<Box<dyn for<'b> Fn(&'b u8)>>
        ) -> &'a Vec<Box<dyn Fn(T)>>
) {}

[arielb1]

I thought we already fixed that by adding casts.

One possible fix that might be less harmful would be to give all types that are subtyping-equivalent the same LLVM type. They should be having the same layout anyway, and their fields should be subtyping-equivalent (because that's what subtyping-equivalence means).

The other option would be to insert casts when subtyping is taking place.

[nikic]

This looks like a new instance of #47638.

cc @eddyb

[eddyb]

#47638 was just an instance of the general problem, we just started generating named types for trait objects then, which made the problem show up in more cases.

I agree with @arielb1's first proposal, i.e. destroy the distinction ahead of time. We're only wasting time by inserting casts and LLVM wastes time ignoring those casts (insert rant about how counterproductive LLVM's types are).

[arielb1]

Reduced to its essence:

pub struct Foo<T>(T, [u8; 64]);

pub fn abc<'a>(x: &Foo<Box<for<'b> Fn(&'b u8)>>) -> &Foo<Box<Fn(&'a u8)>> { x }

fn main() {
    abc(&Foo(Box::new(|_x| ()), [0; 64]));
}

[arielb1]

An example that my previous approach will not make compile (but currently gives an ICE outputtypeparametermismatch):

// run-pass

// check that we handle subtyping between types with a different binding structure correctly,
// especially in LLVM - see issues #55976 & #47638

pub struct Foo<T> {
    t: T,
    force_in_memory_layout: [u8; 64]
}

pub trait MirrorT<'a> {
    type Image;
}

impl<'a, T: Copy> MirrorT<'a> for T {
    type Image = T;
}

type Mirror<'a, T> = <T as MirrorT<'a>>::Image;

// This is the "core problem": this function performs subtyping from
// `&Foo<Box<for<'b> Fn(&'b u8) -> u32>>` to `&Foo<Box<Fn(&'a u8) -> u32>>`
pub fn abc<'a, T: for<'s> MirrorT<'s> + 'static> (
    x: &Foo<Box<for<'b> Fn(Mirror<'b, T>) -> u32>>) -> &Foo<Box<Fn(Mirror<'static, T>) -> u32>> { 
    x
}

// check that it runs
fn main() {
    match abc::<u8>(&Foo {
        t: Box::new(|_x| 42),
        force_in_memory_layout: [1; 64]
    }) {
        v => {
            assert_eq!((v.t)(0u8), 42);
            assert_eq!(&v.force_in_memory_layout as &[u8], &[1u8; 64] as &[u8]);
        }
    };
}

[arielb1]

Nah you can do it without an OutputTypeParameterMismatch ICE, but you're still within deep ICE territory

// run-pass

// check that we handle subtyping between types with a different binding structure correctly,
// especially in LLVM - see issues #55976 & #47638

pub struct Foo<T> {
    t: T,
    force_in_memory_layout: [u8; 64]
}

pub trait MirrorT<'a> {
    type Image;
}

impl<'a, T: Copy> MirrorT<'a> for T {
    type Image = T;
}

pub trait H<T> {}
impl<T> H<T> for () {}

// This is the "core problem": this function performs subtyping from
// `&Foo<Box<for<'b> Fn(&'b u8) -> u32>>` to `&Foo<Box<Fn(&'a u8) -> u32>>`
pub fn abc<'a, T: for<'s> MirrorT<'s> + 'static> (
    x: &Foo<Box<dyn for<'b> H<<T as MirrorT<'b>>::Image>>>) 
    -> &Foo<Box<dyn H<<T as MirrorT<'static>>::Image>>> 
{ 
    x
}

// check that it runs
fn main() {
    match abc::<u8>(&Foo {
        t: Box::new(()),
        force_in_memory_layout: [1; 64]
    }) {
        _v => {
//            assert_eq!((v.t)(0u8), 42);
//            assert_eq!(&v.force_in_memory_layout as &[u8], &[1u8; 64] as &[u8]);
        }
    };
}

[arielb1]

This is making me suspect, that when we get higher-ranked type bounds, finding a "canonical form for subtyping" will be impossible (note: don't be so sure. You can't? (shouldn't?) have higher-ranged type bounds in trait objects, so life might be better). Might as well insert casts.

Note that my old approach has problems with anonymization in invariant types:

use std::marker::PhantomData;

pub struct Invariant<T>(T, PhantomData<*mut T>);
pub struct Foo<T>(T, [u8; 64]);

pub fn abc<'a>(x: &Foo<Invariant<Box<for<'b> fn(&'b u8, &'b u8)>>>)
    -> &Foo<Invariant<Box<for<'b, 'c> fn(&'b u8, &'c u8)>>> { x }

fn main() {
    abc(&Foo(Invariant(Box::new(|_x, _y| ()), PhantomData), [0; 64]));
}