typecheck_ice when attempting to type check trait object with duplicate associated types

[KenDJohnson]

Code

Link to gist

use std::ops::Index;

pub trait Indexable {
    type Index;
}
struct Foo;
struct Bar;
impl Indexable for Foo { type Index = u8; }
impl Indexable for Bar { type Index = u16; }

pub trait Indexer<T: Indexable>: Index<T::Index, Output=T> {}

struct Store;

impl Index<u8> for Store {
    type Output = Foo;
    fn index(&self, _: u8) -> &Foo { panic!() }
}
impl Index<u16> for Store {
    type Output = Bar;
    fn index(&self, _: u16) -> &Bar { panic!() }
}
impl Indexer<Foo> for Store { }
impl Indexer<Bar> for Store { }

// implies StoreIndex: Index<u8, Output=Foo> + Index<u16, Output=Bar>
trait StoreIndex: Indexer<Foo> + Indexer<Bar> {}

impl StoreIndex for Store {}

struct Collection {
    stores: Vec<Store>,
}

trait StoreCollection {
    fn get_store(&self, _: usize) -> Option<&dyn StoreIndex>;
}

impl StoreCollection for Collection {
    //  Fails to compile:
    //    expected:
    //      Option<&dyn StoreIndex<Output = Bar, Output = Foo>
    //    found:
    //      Option<&Store>
    /*
    fn get_store(&self, i: usize) -> Option<&dyn StoreIndex> {
        self.stores.get(i)
    }
    */

    // ICE
    fn get_store(&self, i: usize) -> Option<&dyn StoreIndex> {
        if let Some(s) = self.stores.get(i) {
            Some(s as &dyn StoreIndex)
        } else {
            None
        }
    }

    // However, if the above is removed in favor of Indexing
    // type checking succeeds and the type of `&self.stores[i]`
    // is properly inferred
    /*
    fn get_store(&self, i: usize) -> Option<&dyn StoreIndex> {
        if i < self.stores.len() {
            Some(&self.stores[i])
        } else {
            None
        }
    }
    */
}

fn main() {}

Meta

rustc --version --verbose:

rustc 1.49.0 (e1884a8e3 2020-12-29)
binary: rustc
commit-hash: e1884a8e3c3e813aada8254edfa120e85bf5ffca
commit-date: 2020-12-29
host: x86_64-apple-darwin
release: 1.49.0

Error output

error: internal compiler error: broken MIR in DefId(0:33 ~ typecheck_ice[8acc]::{impl#7}::get_store) (CanonicalUserTypeAnnotation { user_ty: Canonical { max_universe: U0, variables: [CanonicalVarInfo { kind: Region(U0) }, CanonicalVarInfo { kind: Region(U0) }], value: Ty(&dyn StoreIndex<Output = Bar, Output = Foo>) }, span: src/main.rs:53:18: 53:38 (#0), inferred_ty: &dyn StoreIndex<Output = Bar, Output = Foo> }): bad user type (&dyn StoreIndex<Output = Bar, Output = Foo> = &dyn StoreIndex<Output = Bar, Output = Foo>): NoSolution
  |
  = note: delayed at compiler/rustc_mir/src/borrow_check/type_check/mod.rs:253:27

thread 'rustc' panicked at 'no errors encountered even though `delay_span_bug` issued', compiler/rustc_errors/src/lib.rs:974:13
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

error: internal compiler error: unexpected panic

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.49.0 (e1884a8e3 2020-12-29) running on x86_64-apple-darwin

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

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

query stack during panic:
end of query stack
error: could not compile `typecheck_ice`

Backtrace

thread 'rustc' panicked at 'no errors encountered even though `delay_span_bug` issued', compiler/rustc_errors/src/lib.rs:974:13
stack backtrace:
   0:        0x108a44934 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::ha0848bb2602b5d05
   1:        0x108aad0c0 - core::fmt::write::h9f3ccac2ef682b93
   2:        0x108a361f6 - std::io::Write::write_fmt::h0a47673aab280496
   3:        0x108a495b9 - std::panicking::default_hook::{{closure}}::h850c6aaf5e80c2f5
   4:        0x108a4927d - std::panicking::default_hook::h037801299da6e1c6
   5:        0x10bf29413 - rustc_driver::report_ice::h0fe9f8647d245792
   6:        0x108a49d9e - std::panicking::rust_panic_with_hook::h76436d4cf7a368ac
   7:        0x108a498a5 - std::panicking::begin_panic_handler::{{closure}}::h516c76d70abf04f6
   8:        0x108a44da8 - std::sys_common::backtrace::__rust_end_short_backtrace::h653290b4f930faed
   9:        0x108a4980a - _rust_begin_unwind
  10:        0x108ad0b0b - std::panicking::begin_panic_fmt::he778de6995efc6f5
  11:        0x1104eae96 - rustc_errors::HandlerInner::flush_delayed::hdb4fff43f77edaab
  12:        0x1104e700b - <rustc_errors::HandlerInner as core::ops::drop::Drop>::drop::hb7966f169f0d6c15
  13:        0x10bf1c26a - core::ptr::drop_in_place::hf30dd4a15888f71a
  14:        0x10bf1a666 - core::ptr::drop_in_place::hb8793afd37ab302e
  15:        0x10bf1e918 - <alloc::rc::Rc<T> as core::ops::drop::Drop>::drop::hb604ec874b74dec0
  16:        0x10bf339d2 - core::ptr::drop_in_place::hb2a870b8e6fe6c59
  17:        0x10bf2c272 - rustc_span::with_source_map::h687022d7ebb49e8d
  18:        0x10bf39ac1 - rustc_interface::interface::create_compiler_and_run::hea278ab322b44c40
  19:        0x10bf2c96f - rustc_span::with_session_globals::h7023df1cf3c9e104
  20:        0x10bf3e5b1 - std::sys_common::backtrace::__rust_begin_short_backtrace::hf0d8ecab3037d14f
  21:        0x10bebfa28 - core::ops::function::FnOnce::call_once{{vtable.shim}}::hd9d084f81e0dfcf8
  22:        0x108a581fd - std::sys::unix::thread::Thread::new::thread_start::hedb7cc0d930a8f40
  23:     0x7fff20482950 - __pthread_start

I did my best to create a small example for this, and I think this is a minimal instance of the problem. Looks like there is an error when trying to type check a cast to &dyn StoreIndex, for which the super traits expand to &dyn Index<u8, Output=Foo> + Index<u16, Output=Bar> which the typechecker seems to have issue by considering both constraints on Output regardless of the T indexing type (as StoreIndex<Output = Bar, Output = Foo> which it considers unsolvable since Bar != Foo.

The other two cases here are interesting as well. When get() is used directly, type checking fails but there is no ICE, but when the Vec<Store> is indexed directly &Store is automatically cast to &dyn StoreIndex and compilation succeeds.

[FabianWolff]

Reduced (same ICE as above):

pub trait Indexable { type Idx; }
impl Indexable for u8 { type Idx = u8; }
impl Indexable for u16 { type Idx = u16; }

pub trait Indexer<T: Indexable>: std::ops::Index<T::Idx, Output=T> {}

trait StoreIndex: Indexer<u8> + Indexer<u16> {}

fn foo(st: &impl StoreIndex) -> &dyn StoreIndex {
    st as &dyn StoreIndex
}

fn main() {}

[jackh726]

Fixed by #85499, not 100% sure what's going on here. But it's a different test case, so marking as needs-test.