Auto merge of #135318 - compiler-errors:vtable-fixes, r=lcnr

Fix deduplication mismatches in vtables leading to upcasting unsoundness

We currently have two cases where subtleties in supertraits can trigger disagreements in the vtable layout, e.g. leading to a different vtable layout being accessed at a callsite compared to what was prepared during unsizing. Namely:

### #135315

In this example, we were not normalizing supertraits when preparing vtables. In the example,

```
trait Supertrait<T> {
    fn _print_numbers(&self, mem: &[usize; 100]) {
        println!("{mem:?}");
    }
}
impl<T> Supertrait<T> for () {}

trait Identity {
    type Selff;
}
impl<Selff> Identity for Selff {
    type Selff = Selff;
}

trait Middle<T>: Supertrait<()> + Supertrait<T> {
    fn say_hello(&self, _: &usize) {
        println!("Hello!");
    }
}
impl<T> Middle<T> for () {}

trait Trait: Middle<<() as Identity>::Selff> {}
impl Trait for () {}

fn main() {
    (&() as &dyn Trait as &dyn Middle<()>).say_hello(&0);
}
```

When we prepare `dyn Trait`, we see a supertrait of `Middle<<() as Identity>::Selff>`, which itself has two supertraits `Supertrait<()>` and `Supertrait<<() as Identity>::Selff>`. These two supertraits are identical, but they are not duplicated because we were using structural equality and *not* considering normalization. This leads to a vtable layout with two trait pointers.

When we upcast to `dyn Middle<()>`, those two supertraits are now the same, leading to a vtable layout with only one trait pointer. This leads to an offset error, and we call the wrong method.

### #135316

This one is a bit more interesting, and is the bulk of the changes in this PR. It's a bit similar, except it uses binder equality instead of normalization to make the compiler get confused about two vtable layouts. In the example,

```
trait Supertrait<T> {
    fn _print_numbers(&self, mem: &[usize; 100]) {
        println!("{mem:?}");
    }
}
impl<T> Supertrait<T> for () {}

trait Trait<T, U>: Supertrait<T> + Supertrait<U> {
    fn say_hello(&self, _: &usize) {
        println!("Hello!");
    }
}
impl<T, U> Trait<T, U> for () {}

fn main() {
    (&() as &'static dyn for<'a> Trait<&'static (), &'a ()>
        as &'static dyn Trait<&'static (), &'static ()>)
        .say_hello(&0);
}
```

When we prepare the vtable for `dyn for<'a> Trait<&'static (), &'a ()>`, we currently consider the PolyTraitRef of the vtable as the key for a supertrait. This leads two two supertraits -- `Supertrait<&'static ()>` and `for<'a> Supertrait<&'a ()>`.

However, we can upcast[^up] without offsetting the vtable from `dyn for<'a> Trait<&'static (), &'a ()>` to `dyn Trait<&'static (), &'static ()>`. This is just instantiating the principal trait ref for a specific `'a = 'static`. However, when considering those supertraits, we now have only one distinct supertrait -- `Supertrait<&'static ()>` (which is deduplicated since there are two supertraits with the same substitutions). This leads to similar offsetting issues, leading to the wrong method being called.

[^up]: I say upcast but this is a cast that is allowed on stable, since it's not changing the vtable at all, just instantiating the binder of the principal trait ref for some lifetime.

The solution here is to recognize that a vtable isn't really meaningfully higher ranked, and to just treat a vtable as corresponding to a `TraitRef` so we can do this deduplication more faithfully. That is to say, the vtable for `dyn for<'a> Tr<'a>` and `dyn Tr<'x>` are always identical, since they both would correspond to a set of free regions on an impl... Do note that `Tr<for<'a> fn(&'a ())>` and `Tr<fn(&'static ())>` are still distinct.

----

There's a bit more that can be cleaned up. In codegen, we can stop using `PolyExistentialTraitRef` basically everywhere. We can also fix SMIR to stop storing `PolyExistentialTraitRef` in its vtable allocations.

As for testing, it's difficult to actually turn this into something that can be tested with `rustc_dump_vtable`, since having multiple supertraits that are identical is a recipe for ambiguity errors. Maybe someone else is more creative with getting that attr to work, since the tests I added being run-pass tests is a bit unsatisfying. Miri also doesn't help here, since it doesn't really generate vtables that are offset by an index in the same way as codegen.

r? `@lcnr` for the vibe check? Or reassign, idk. Maybe let's talk about whether this makes sense.

<sup>(I guess an alternative would also be to not do any deduplication of vtable supertraits (or only a really conservative subset) rather than trying to normalize and deduplicate more faithfully here. Not sure if that works and is sufficient tho.)</sup>

cc `@steffahn` -- ty for the minimizations
cc `@WaffleLapkin` -- since you're overseeing the feature stabilization :3

Fixes #135315
Fixes #135316

1 files changed, 0 insertions, 91 deletions

diff --git a/compiler/rustc_interface/src/passes.rs b/compiler/rustc_interface/src/passes.rs
index 241bc35857a..0b91c023cfc 100644
--- a/compiler/rustc_interface/src/passes.rs
+++ b/compiler/rustc_interface/src/passes.rs
@@ -26,7 +26,6 @@ use rustc_parse::{
 };
 use rustc_passes::{abi_test, input_stats, layout_test};
 use rustc_resolve::Resolver;
-use rustc_session::code_stats::VTableSizeInfo;
 use rustc_session::config::{CrateType, Input, OutFileName, OutputFilenames, OutputType};
 use rustc_session::cstore::Untracked;
 use rustc_session::output::{collect_crate_types, filename_for_input, find_crate_name};
@@ -989,90 +988,6 @@ fn analysis(tcx: TyCtxt<'_>, (): ()) {
         // we will fail to emit overlap diagnostics. Thus we invoke it here unconditionally.
         let _ = tcx.all_diagnostic_items(());
     });
-
-    if sess.opts.unstable_opts.print_vtable_sizes {
-        let traits = tcx.traits(LOCAL_CRATE);
-
-        for &tr in traits {
-            if !tcx.is_dyn_compatible(tr) {
-                continue;
-            }
-
-            let name = ty::print::with_no_trimmed_paths!(tcx.def_path_str(tr));
-
-            let mut first_dsa = true;
-
-            // Number of vtable entries, if we didn't have upcasting
-            let mut entries_ignoring_upcasting = 0;
-            // Number of vtable entries needed solely for upcasting
-            let mut entries_for_upcasting = 0;
-
-            let trait_ref = ty::Binder::dummy(ty::TraitRef::identity(tcx, tr));
-
-            // A slightly edited version of the code in
-            // `rustc_trait_selection::traits::vtable::vtable_entries`, that works without self
-            // type and just counts number of entries.
-            //
-            // Note that this is technically wrong, for traits which have associated types in
-            // supertraits:
-            //
-            //   trait A: AsRef<Self::T> + AsRef<()> { type T; }
-            //
-            // Without self type we can't normalize `Self::T`, so we can't know if `AsRef<Self::T>`
-            // and `AsRef<()>` are the same trait, thus we assume that those are different, and
-            // potentially over-estimate how many vtable entries there are.
-            //
-            // Similarly this is wrong for traits that have methods with possibly-impossible bounds.
-            // For example:
-            //
-            //   trait B<T> { fn f(&self) where T: Copy; }
-            //
-            // Here `dyn B<u8>` will have 4 entries, while `dyn B<String>` will only have 3.
-            // However, since we don't know `T`, we can't know if `T: Copy` holds or not,
-            // thus we lean on the bigger side and say it has 4 entries.
-            traits::vtable::prepare_vtable_segments(tcx, trait_ref, |segment| {
-                match segment {
-                    traits::vtable::VtblSegment::MetadataDSA => {
-                        // If this is the first dsa, it would be included either way,
-                        // otherwise it's needed for upcasting
-                        if std::mem::take(&mut first_dsa) {
-                            entries_ignoring_upcasting += 3;
-                        } else {
-                            entries_for_upcasting += 3;
-                        }
-                    }
-
-                    traits::vtable::VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => {
-                        // Lookup the shape of vtable for the trait.
-                        let own_existential_entries =
-                            tcx.own_existential_vtable_entries(trait_ref.def_id());
-
-                        // The original code here ignores the method if its predicates are
-                        // impossible. We can't really do that as, for example, all not trivial
-                        // bounds on generic parameters are impossible (since we don't know the
-                        // parameters...), see the comment above.
-                        entries_ignoring_upcasting += own_existential_entries.len();
-
-                        if emit_vptr {
-                            entries_for_upcasting += 1;
-                        }
-                    }
-                }
-
-                std::ops::ControlFlow::Continue::<std::convert::Infallible>(())
-            });
-
-            sess.code_stats.record_vtable_size(tr, &name, VTableSizeInfo {
-                trait_name: name.clone(),
-                entries: entries_ignoring_upcasting + entries_for_upcasting,
-                entries_ignoring_upcasting,
-                entries_for_upcasting,
-                upcasting_cost_percent: entries_for_upcasting as f64
-                    / entries_ignoring_upcasting as f64
-                    * 100.,
-            })
-        }
-    }
 }
 
 /// Check for the `#[rustc_error]` annotation, which forces an error in codegen. This is used
@@ -1153,12 +1068,6 @@ pub(crate) fn start_codegen<'tcx>(
         tcx.sess.code_stats.print_type_sizes();
     }
 
-    if tcx.sess.opts.unstable_opts.print_vtable_sizes {
-        let crate_name = tcx.crate_name(LOCAL_CRATE);
-
-        tcx.sess.code_stats.print_vtable_sizes(crate_name);
-    }
-
     codegen
 }