hang/slowdown in rustc_middle::traits::ObligationCauseCode

[matthiaskrgr]

see also #90180

pub struct B0;
pub struct B1;
use std::ops::Shl;
use std::ops::Sub;
pub type Shleft<A, B> = <A as Shl<B>>::Output;
pub type Sub1<A> = <A as Sub<B1>>::Output;
pub struct UInt<U, B> {
    pub(crate) msb: U,
    pub(crate) lsb: B,
}
impl<U, B, Ur, Br> Shl<UInt<Ur, Br>> for UInt<U, B>
where
    UInt<Ur, Br>: Sub<Br>,
    UInt<UInt<B, U>, B0>: Shl<Self::Output>,
{
    type Output = Shleft<UInt<UInt<U, B>, B0>, Sub1<UInt<Ur, Br>>>;
    fn shl(self, rhs: UInt<Ur, Br>) -> Sub1<UInt<Ur, B1>> {
        unimplemented!()
    }
}

rustc --crate-type lib -Ztime-passes hang.rs

time:   0.018; rss:   37MB ->   39MB (   +2MB)	parse_crate
time:   0.011; rss:   42MB ->   57MB (  +15MB)	expand_crate
time:   0.011; rss:   42MB ->   57MB (  +15MB)	macro_expand_crate
time:   0.000; rss:   57MB ->   59MB (   +2MB)	finalize_macro_resolutions
time:   0.001; rss:   59MB ->   62MB (   +3MB)	late_resolve_crate
time:   0.002; rss:   57MB ->   62MB (   +5MB)	resolve_crate
time:   0.013; rss:   39MB ->   62MB (  +23MB)	configure_and_expand
time:   0.001; rss:   62MB ->   65MB (   +3MB)	looking_for_derive_registrar
time:   0.001; rss:   62MB ->   65MB (   +3MB)	misc_checking_1
time:   0.001; rss:   65MB ->   69MB (   +4MB)	type_collecting
time:   0.001; rss:   69MB ->   71MB (   +3MB)	coherence_checking
<freeze>

perf top shows a lot of processing in <rustc_middle::traits::ObligationCauseCode as core::cmp::PartialEq>::eq

[jruderman]

Reduced a bit:

trait Shel<T> {
    type Output;
}

struct MyTuple<U, B>(U, B);

impl<U, B, Ur, Br> Shel<MyTuple<Ur, Br>> for MyTuple<U, B>
where
    MyTuple<B, U>: Shel<Self::Output>,
{
    type Output = <MyTuple<B, ()> as Shel<MyTuple<Ur, Br>>>::Output;
}

fn main(){}

With #![recursion_limit = "30"], it finishes in 10 seconds (mostly wf_checking) and reports an 'overflow evaluating requirement' error:

Output with low recursion limit

error[E0275]: overflow evaluating the requirement `MyTuple<B, U>: Shel<MyTuple<_, _>>`
 --> q_105269.rs:7:1
  |
7 | impl<U, B, Ur, Br> Shel<MyTuple<Ur, Br>> for MyTuple<U, B>
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = help: consider increasing the recursion limit by adding a `#![recursion_limit = "80"]` attribute to your crate (`q_105269`)
note: required for `MyTuple<U, B>` to implement `Shel<MyTuple<Ur, Br>>`
 --> q_105269.rs:7:20
  |
7 | impl<U, B, Ur, Br> Shel<MyTuple<Ur, Br>> for MyTuple<U, B>
  |                    ^^^^^^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^

Regression in nightly-2020-08-21, perhaps from #75494 (@spastorino, @nikomatsakis, @matthewjasper).

May be related to #104230, although that issue has a later regression date.