Trait selection caching does not handle subtyping properly

[arielb1]

STR

trait Foo<U,V> : Sized {
    fn foo(self, u: Option<U>, v: Option<V>) {}
}

struct A;
struct B;

impl Foo<A, B> for () {}      // impl A

fn toxic() {
    // cache the resolution <() as Foo<$0,$1>> = impl A
    let u = None;
    let v = None;
    Foo::foo((), u, v);
}

fn bomb() {
    let mut u = None; // type is Option<$0>
    let mut v = None; // type is Option<$1>
    let mut x = None; // type is Option<$2>

    Foo::foo(x.unwrap(),u,v); // register <$2 as Foo<$0, $1>>
    u = v; // mark $0 and $1 in a subtype relationship
    x = Some(()); // set $2 = (), allowing impl selection
                  // to proceed for <() as Foo<$0, $1>> = impl A.
                  // kaboom
                  // NOTE: the obligation's resolution must be delayed for the
                  // ICE to occur to prevent coercions from interfering.
}

fn main() {}

Results

error: internal compiler error: Impl DefId { krate: 0, node: DefIndex(15) => ().Foo<A, B> } was matchable against Obligation(predicate=Binder(TraitPredicate(<_ as Foo<_, _>>)),depth=0) but now is not
note: the compiler unexpectedly panicked. this is a bug.
note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports
note: run with `RUST_BACKTRACE=1` for a backtrace
thread 'rustc' panicked at 'Box<Any>', ../src/libsyntax/diagnostic.rs:253

Comments

@nikomatsakis and me were worried that this might be possible since we had multidispatch, but this is the first working example. I found this while poking with the unification machinery.

[nikomatsakis]

Yeah, I've been waiting for someone to make an example for this. I had a strategy for fixing it but never got around to implementing it. Thanks for making an example @arielb1 !

[nikomatsakis]

triage: P-medium

[brson]

@nikomatsakis can mentor.

[cramertj]

@nikomatsakis I'd be interested in working on this if you're still willing to mentor.

[nikomatsakis]

@cramertj hmm, at this point I think the way I want to solve this is as part of a bigger refactoring to overhaul trait system. I recently wrote the very first post of a series of posts that I hope to write explaining the approach; I need to think about the actual steps for making that transition. Would you maybe be interested in helping with that task?

[cramertj]

@nikomatsakis I would absolutely be interested in helping!