ICE on generic impl trait convergence

[leops]

Using a generic function to "converge" two impl Trait<T> into T when T is an associated type for another trait causes the following error:

error: internal compiler error: broken MIR in DefId(0/0:14 ~ playground[c5d2]::main[0]) (NoSolution): could not prove Binder(TraitPredicate(<impl Trait<<u32 as std::ops::Add>::Output> as Trait<u32>>))

error: internal compiler error: broken MIR in DefId(0/0:14 ~ playground[c5d2]::main[0]) (Terminator { source_info: SourceInfo { span: src/main.rs:46:5: 46:26, scope: scope[0] }, kind: _1 = const <Either<L, R>>::converge(move _2) -> [return: bb3, unwind: bb4] }): call dest mismatch (<u32 as std::ops::Add>::Output <- u32): NoSolution
  --> src/main.rs:45:1
   |
45 | / pub fn main() {
46 | |     add_one(3).converge();
47 | | }
   | |_^

Example code (Playground link):

use std::ops::Add;

trait Trait<T> {
    fn get(self) -> T;
}

struct Holder<T>(T);

impl<T> Trait<T> for Holder<T> {
    fn get(self) -> T {
        self.0
    }
}

enum Either<L, R> {
    Left(L),
    Right(R),
}

impl<L, R> Either<L, R> {
    fn converge<T>(self) -> T where L: Trait<T>, R: Trait<T> {
        match self {
            Either::Left(val) => val.get(),
            Either::Right(val) => val.get(),
        }
    }
}

fn add_generic<A: Add<B>, B>(lhs: A, rhs: B) -> Either<
    impl Trait<<A as Add<B>>::Output>,
    impl Trait<<A as Add<B>>::Output>
> {
    if true {
        Either::Left(Holder(lhs + rhs))
    } else {
        Either::Right(Holder(lhs + rhs))
    }
}

// FAIL: fn add_one(value: u32) -> Either<impl Trait<u32>, impl Trait<u32>> {
fn add_one(value: u32) -> Either<impl Trait<<u32 as Add<u32>>::Output>, impl Trait<<u32 as Add<u32>>::Output>> {
    add_generic(value, 1u32)
}

pub fn main() {
    add_one(3).converge();
}

This may or may not be related to the compiler seemingly failing to assert that <u32 as Add<u32>>::Output == u32, an error that can be triggered by using the alternate signature for add_one at line 40 of the example.

Meta

I tested this with the linked playground on the latest stable (1.32.0), as well as a recent nightly:

rustc 1.33.0-nightly (bf669d1e3 2019-01-25)
binary: rustc
commit-hash: bf669d1e3295bc688f71b8c91f48a6beaf895f67
commit-date: 2019-01-25
host: x86_64-pc-windows-msvc
release: 1.33.0-nightly
LLVM version: 8.0

Compiling with RUST_BACKTRACE=1 doesn't seem to yield a very useful stack but here it is:

thread 'rustc' panicked at 'no errors encountered even though `delay_span_bug` issued', src\librustc_errors\lib.rs:323:17
stack backtrace:
   0: std::sys_common::alloc::realloc_fallback
   1: std::panicking::take_hook
   2: std::panicking::take_hook
   3: <rustc::ty::SymbolName as core::fmt::Debug>::fmt
   4: std::panicking::rust_panic_with_hook
   5: <rustc_errors::Level as core::fmt::Debug>::fmt
   6: <rustc_errors::Handler as core::ops::drop::Drop>::drop
   7: <rustc_driver::CompilationFailure as core::fmt::Debug>::fmt
   8: <rustc_driver::CompilationFailure as core::fmt::Debug>::fmt
   9: <rustc_driver::CompilationFailure as core::fmt::Debug>::fmt
  10: <rustc_driver::CompilationFailure as core::fmt::Debug>::fmt
  11: <humantime::duration::Error as std::error::Error>::cause
  12: _rust_maybe_catch_panic
  13: <humantime::duration::Error as std::error::Error>::cause
  14: std::sys::windows::thread::Thread::new
  15: BaseThreadInitThunk
  16: RtlUserThreadStart
query stack during panic:
end of query stack

[jonas-schievink]

Another example by @hellow554 that causes only the second "call dest mismatch" ICE:

use std::ops::Add;

fn add_generic<A>() -> impl IntoIterator<Item = A> {
    vec![]
}

pub fn add_one() -> impl IntoIterator<Item = <u32 as Add<u32>>::Output> {
    add_generic()
}

[pnkfelix]

P-medium. Removing nomination label. (But maybe we should have a WG-impl-trait to provide a structured effort for working through the bugs with impl trait?)

[jakubadamw]

This has been fixed in 1.38.0 as, while I can reproduce the ICE in 1.37.0, I am not observing it in neither of: stable (1.38.0), beta nor nightly.

@rustbot modify labels: E-needstest