Repository: rust
Issue: Inconsistent/wrong choice of trait impls under `miri` with transmuted vtables
Labels: I-ICE,T-compiler,C-bug,A-miri,A-trait-objects

Here is a test case
```rust
#![allow(coherence_leak_check)]

fn main() {
    let x: &dyn Trait<Marker1> = &();
    let y: &dyn Trait<Marker2> = unsafe { std::mem::transmute(x) };
    y.report();
}

type Marker1 = fn(&()) -> (&(), &'static ());
type Marker2 = fn(&()) -> (&'static (), &());

trait Trait<M: 'static> {
    fn report(&self);
}
impl<M: 'static> Trait<M> for () {
    fn report(&self) {
        who_am_i::<M>();
    }
}

fn who_am_i<M: 'static>() {
    let marker1 = std::any::TypeId::of::<Marker1>();
    let marker2 = std::any::TypeId::of::<Marker2>();
    let m = std::any::TypeId::of::<M>();
    let m_is = if m == marker1 {
        "Marker1"
    } else if m == marker2 {
        "Marker2"
    } else {
        unreachable!()
    };
    println!("M == {m_is}");
}
```
([playground](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=f3ea7b28ea1c770d5f84068c2f699e09))

When run normally, this prints
```rust
M == Marker1
```

When run with miri, this prints
```rust
M == Marker2
```

### Expected behavior: Miri either reports UB, or behaves the same way like the actual codegen does.

---

It gets even more interesting if we add a trait bound to the `impl`:
```rust
impl<M: 'static> Trait<M> for ()
where
    M: Bound,
{
    fn report(&self) {
        who_am_i::<M>();
        println!("---");
        M::who_am_i();
    }
}

trait Bound: 'static + Sized {
    fn who_am_i() {
        who_am_i::<Self>();
    }
}
impl Bound for Marker1 {}
```
([playground](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=032bb768232c99aa7316d3cf5c742495))

When run normally, this prints
```rust
M == Marker1
---
M == Marker1
```

When run with miri, this prints
```rust
M == Marker2
---
M == Marker1
```

*Oh wonderful, the type apparently just changes in the middle of it!*

---

If we add a second implementation, Miri reconsiders its choices
```rust
impl Bound for Marker1 {}
impl Bound for Marker2 {}
```
([playground](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=8f46f10cff12456009d7287c428c54f7))

*(Behavior when run normally: unchanged.)*

When run with miri, this prints
```rust
M == Marker2
---
M == Marker2
```

*(still wrong though / [actual execution without `miri` is reporting `Marker1`, `Marker1`])*

---

This behavior must come from some sort of rough heuristic that wasn't supposed to ever matter… because… if the second `impl` *exists* but comes with an impossible trait bound, then miri still seems to try to make use of this `Marker2`-impl nonetheless:
```rust
impl Bound for Marker1 {}
impl Bound for Marker2 where Self: Unimplemented {}

trait Unimplemented {}
```
([playground](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=75708feacbe51b65b17ffa08e0cc4415))

When run normally, this still prints
```rust
M == Marker1
---
M == Marker1
```

When run with miri, you get ICE:
```plain
error: internal compiler error: compiler/rustc_middle/src/ty/instance.rs:585:21: failed to resolve instance for <() as Trait<for<'a> fn(&'a ()) -> (&(), &'a ())>>::report
  --> src/main.rs:13:5
   |
13 |     fn report(&self);
   |     ^^^^^^^^^^^^^^^^^


thread 'rustc' panicked at compiler/rustc_middle/src/ty/instance.rs:585:21:
Box<dyn Any>
stack backtrace:
   0:     0x7d96ae6d260a - <std::sys::backtrace::BacktraceLock::print::DisplayBacktrace as core::fmt::Display>::fmt::hcfde92856b8e7b4d
   1:     0x7d96aee135e6 - core::fmt::write::h8aa28d7c2e766574
   2:     0x7d96afcc0491 - std::io::Write::write_fmt::h0473f60143e76874
   3:     0x7d96ae6d2462 - std::sys::backtrace::BacktraceLock::print::he0a43b48023f5fb3
   4:     0x7d96ae6d4a07 - std::panicking::default_hook::{{closure}}::h16c37508eb1e165d
   5:     0x7d96ae6d47f0 - std::panicking::default_hook::h188c5d4452b2e2a8
   6:     0x7d96ad8518a8 - std[fac44eaeb111bcc8]::panicking::update_hook::<alloc[66489a0f9c76ca63]::boxed::Box<rustc_driver_impl[1ee6f045412d773c]::install_ice_hook::{closure#1}>>::{closure#0}
   7:     0x7d96ae6d5253 - std::panicking::rust_panic_with_hook::h1cf1663d92a293a0
   8:     0x7d96ad889dd1 - std[fac44eaeb111bcc8]::panicking::begin_panic::<rustc_errors[8e1a8b7a3353af80]::ExplicitBug>::{closure#0}
   9:     0x7d96ad87efb6 - std[fac44eaeb111bcc8]::sys::backtrace::__rust_end_short_backtrace::<std[fac44eaeb111bcc8]::panicking::begin_panic<rustc_errors[8e1a8b7a3353af80]::ExplicitBug>::{closure#0}, !>
  10:     0x7d96ad87ef9d - std[fac44eaeb111bcc8]::panicking::begin_panic::<rustc_errors[8e1a8b7a3353af80]::ExplicitBug>
  11:     0x7d96ad893d31 - <rustc_errors[8e1a8b7a3353af80]::diagnostic::BugAbort as rustc_errors[8e1a8b7a3353af80]::diagnostic::EmissionGuarantee>::emit_producing_guarantee
  12:     0x7d96adde29ac - <rustc_errors[8e1a8b7a3353af80]::DiagCtxtHandle>::span_bug::<rustc_span[7d28ac27f72ec6b1]::span_encoding::Span, alloc[66489a0f9c76ca63]::string::String>
  13:     0x7d96ade67927 - rustc_middle[5606c862b127c2dc]::util::bug::opt_span_bug_fmt::<rustc_span[7d28ac27f72ec6b1]::span_encoding::Span>::{closure#0}
  14:     0x7d96ade4c9ca - rustc_middle[5606c862b127c2dc]::ty::context::tls::with_opt::<rustc_middle[5606c862b127c2dc]::util::bug::opt_span_bug_fmt<rustc_span[7d28ac27f72ec6b1]::span_encoding::Span>::{closure#0}, !>::{closure#0}
  15:     0x7d96ade4c85b - rustc_middle[5606c862b127c2dc]::ty::context::tls::with_context_opt::<rustc_middle[5606c862b127c2dc]::ty::context::tls::with_opt<rustc_middle[5606c862b127c2dc]::util::bug::opt_span_bug_fmt<rustc_span[7d28ac27f72ec6b1]::span_encoding::Span>::{closure#0}, !>::{closure#0}, !>
  16:     0x7d96ac8b3e97 - rustc_middle[5606c862b127c2dc]::util::bug::span_bug_fmt::<rustc_span[7d28ac27f72ec6b1]::span_encoding::Span>
  17:     0x7d96af4ae73c - <rustc_middle[5606c862b127c2dc]::ty::instance::Instance>::expect_resolve
  18:     0x7d96af9d0695 - <rustc_middle[5606c862b127c2dc]::ty::instance::Instance>::expect_resolve_for_vtable
  19:     0x7d96af6b28f7 - rustc_trait_selection[d64518d2976bfae4]::traits::vtable::vtable_entries::{closure#0}
  20:     0x7d96af41d9f0 - rustc_trait_selection[d64518d2976bfae4]::traits::vtable::vtable_entries
  21:     0x7d96af41d72a - rustc_query_impl[25a774c2c57585ee]::plumbing::__rust_begin_short_backtrace::<rustc_query_impl[25a774c2c57585ee]::query_impl::vtable_entries::dynamic_query::{closure#2}::{closure#0}, rustc_middle[5606c862b127c2dc]::query::erase::Erased<[u8; 16usize]>>
  22:     0x7d96af41d6f9 - <rustc_query_impl[25a774c2c57585ee]::query_impl::vtable_entries::dynamic_query::{closure#2} as core[249175d58a5edd5c]::ops::function::FnOnce<(rustc_middle[5606c862b127c2dc]::ty::context::TyCtxt, rustc_type_ir[e0f584499d9d9d64]::binder::Binder<rustc_middle[5606c862b127c2dc]::ty::context::TyCtxt, rustc_type_ir[e0f584499d9d9d64]::predicate::TraitRef<rustc_middle[5606c862b127c2dc]::ty::context::TyCtxt>>)>>::call_once
  23:     0x7d96afb91f59 - rustc_query_system[880048adabd2048e]::query::plumbing::try_execute_query::<rustc_query_impl[25a774c2c57585ee]::DynamicConfig<rustc_query_system[880048adabd2048e]::query::caches::DefaultCache<rustc_type_ir[e0f584499d9d9d64]::binder::Binder<rustc_middle[5606c862b127c2dc]::ty::context::TyCtxt, rustc_type_ir[e0f584499d9d9d64]::predicate::TraitRef<rustc_middle[5606c862b127c2dc]::ty::context::TyCtxt>>, rustc_middle[5606c862b127c2dc]::query::erase::Erased<[u8; 16usize]>>, false, false, false>, rustc_query_impl[25a774c2c57585ee]::plumbing::QueryCtxt, false>
  24:     0x7d96afb91cb8 - rustc_query_impl[25a774c2c57585ee]::query_impl::vtable_entries::get_query_non_incr::__rust_end_short_backtrace
  25:     0x574a5c488044 - <rustc_const_eval[e2da1d737b1da01f]::interpret::eval_context::InterpCx<miri[7fefe668a30715d]::machine::MiriMachine>>::vtable_entries
  26:     0x574a5c4ab00b - <rustc_const_eval[e2da1d737b1da01f]::interpret::eval_context::InterpCx<miri[7fefe668a30715d]::machine::MiriMachine>>::init_fn_call
  27:     0x574a5c5245fa - miri[7fefe668a30715d]::eval::eval_entry::{closure#0}
  28:     0x574a5c52072b - miri[7fefe668a30715d]::eval::eval_entry
  29:     0x574a5c3d4216 - <miri[38dcf146ac8aeb09]::MiriCompilerCalls as rustc_driver_impl[1ee6f045412d773c]::Callbacks>::after_analysis
  30:     0x7d96afdf13ab - rustc_interface[a5b8f6a3ca67129a]::passes::create_and_enter_global_ctxt::<core[249175d58a5edd5c]::option::Option<rustc_interface[a5b8f6a3ca67129a]::queries::Linker>, rustc_driver_impl[1ee6f045412d773c]::run_compiler::{closure#0}::{closure#2}>::{closure#2}::{closure#0}
  31:     0x7d96afd116d6 - rustc_interface[a5b8f6a3ca67129a]::interface::run_compiler::<(), rustc_driver_impl[1ee6f045412d773c]::run_compiler::{closure#0}>::{closure#1}
  32:     0x7d96afc14c07 - std[fac44eaeb111bcc8]::sys::backtrace::__rust_begin_short_backtrace::<rustc_interface[a5b8f6a3ca67129a]::util::run_in_thread_with_globals<rustc_interface[a5b8f6a3ca67129a]::util::run_in_thread_pool_with_globals<rustc_interface[a5b8f6a3ca67129a]::interface::run_compiler<(), rustc_driver_impl[1ee6f045412d773c]::run_compiler::{closure#0}>::{closure#1}, ()>::{closure#0}, ()>::{closure#0}::{closure#0}, ()>
  33:     0x7d96afc150a4 - <<std[fac44eaeb111bcc8]::thread::Builder>::spawn_unchecked_<rustc_interface[a5b8f6a3ca67129a]::util::run_in_thread_with_globals<rustc_interface[a5b8f6a3ca67129a]::util::run_in_thread_pool_with_globals<rustc_interface[a5b8f6a3ca67129a]::interface::run_compiler<(), rustc_driver_impl[1ee6f045412d773c]::run_compiler::{closure#0}>::{closure#1}, ()>::{closure#0}, ()>::{closure#0}::{closure#0}, ()>::{closure#1} as core[249175d58a5edd5c]::ops::function::FnOnce<()>>::call_once::{shim:vtable#0}
  34:     0x7d96afc16681 - std::sys::pal::unix::thread::Thread::new::thread_start::h1f4f8d3a2ffc672f
  35:     0x7d96aa08aa94 - <unknown>
  36:     0x7d96aa117a34 - clone
  37:                0x0 - <unknown>
```

To run into this ICE, calling a method of `Bound` isn't actually necessary. Once the `y.report()` call it reached, it already goes ICE:

```rust
#![allow(coherence_leak_check)]

fn main() {
    let x: &dyn Trait<Marker1> = &();
    let y: &dyn Trait<Marker2> = unsafe { std::mem::transmute(x) };
    y.report();
}

type Marker1 = fn(&()) -> (&(), &'static ());
type Marker2 = fn(&()) -> (&'static (), &());

trait Trait<M> {
    fn report(&self) {}
}
impl<M: Bound> Trait<M> for () {}

trait Bound {}
impl Bound for Marker1 {}
impl Bound for Marker2 where Self: Unimplemented {}

trait Unimplemented {}
```
([playground](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=f1f89308af6ac9062053658d8945c8e8))

@rustbot label A-miri, A-trait-objects, I-ICE, T-compiler