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]));
}

[Dylan-DPC-zz]

marking this as p-medium as per the prioritization discussion

[nikomatsakis]

@rustbot labels +T-types

This seems like a problem around higher ranked normalization etc, so we are tagging as T-types. We think it may have been fixed as a side-effect of some LLVM change or other (cc @compiler-errors for the details).

[jackh726]

Seems to be fixed since 1.23.

[JohnTitor]

Triage: The issue hasn't been fixed actually, at least on CI (CI stderr from #105691):

 ---- [ui] src/test/ui/codegen/issue-55976.rs stdout ----

error: test compilation failed although it shouldn't!
status: exit status: 101
command: "/checkout/obj/build/x86_64-unknown-linux-gnu/stage2/bin/rustc" "/checkout/src/test/ui/codegen/issue-55976.rs" "-Zthreads=1" "--target=x86_64-unknown-linux-gnu" "-O" "--error-format" "json" "--json" "future-incompat" "-Ccodegen-units=1" "-Zui-testing" "-Zsimulate-remapped-rust-src-base=/rustc/FAKE_PREFIX" "-Ztranslate-remapped-path-to-local-path=no" "-Zdeduplicate-diagnostics=no" "-Cstrip=debuginfo" "-C" "prefer-dynamic" "-o" "/checkout/obj/build/x86_64-unknown-linux-gnu/test/ui/codegen/issue-55976/a" "-Crpath" "-Cdebuginfo=0" "-Lnative=/checkout/obj/build/x86_64-unknown-linux-gnu/native/rust-test-helpers" "-L" "/checkout/obj/build/x86_64-unknown-linux-gnu/test/ui/codegen/issue-55976/auxiliary"
stdout: none
--- stderr -------------------------------
Function return type does not match operand type of return inst!
  ret %"alloc::vec::Vec<alloc::boxed::Box<dyn for<'a> core::ops::function::Fn(&'a u8)>>"* %4
 %"alloc::vec::Vec<alloc::boxed::Box<dyn core::ops::function::Fn(&u8)>>"*LLVM ERROR: Broken module found, compilation aborted!

[jackh726]

That's interesting. It doesn't fail in a playground. Is this a debug assert now or something?

[matthiaskrgr]

The build says CI / PR (x86_64-gnu-llvm-13 ... so maybe this is fixed with nighty that uses llvm 15.0.6 but llvm 13 still causes problems?

[JohnTitor]

The build says CI / PR (x86_64-gnu-llvm-13 ... so maybe this is fixed with nighty that uses llvm 15.0.6 but llvm 13 still causes problems?

Likely, we could use min-llvm-version if so. Is there a CI builder that uses a newer LLVM on bors?

[compiler-errors]

Yeah, this is fixed by LLVM using its opaque pointers, so that's why it's possibly broken on LLVM 13?

[JohnTitor]

Re-submitted a PR with min-llvm-version: #105785