Repository: rust
Issue: Compile slow down against trait bound of nested structs 
Labels: A-trait-system,I-compiletime,T-compiler,regression-from-stable-to-stable

<!--
Thank you for filing a regression report! 🐛 A regression is something that changed between versions of Rust but was not supposed to.

Please provide a short summary of the regression, along with any information you feel is relevant to replicate it.
-->

I'm not sure if this should be reported as a regression. I found compiling my code with Rust 1.41.0 took triple time compared to the previous version. It occurred 1 year ago and [filed at my repo](https://github.com/KeenS/webml/issues/78), so this is a bit old issue.

The code contains nested structs with trait bounds. It took some time to compile in the previous version too. I guess compiling this code take exponential time even in older versions of rust compiler because when I add a pass to the chain, compile time increases under certain multiplier. The issue is the multiplier increased in Rust 1.41.0.

Here is some brief measures:

```console
$ time rustc +1.36.0 slow_compilation.rs
rustc +1.36.0 slow_compilation.rs  16.25s user 0.68s system 99% cpu 16.939 total
$ time rustc +1.40.0 slow_compilation.rs
rustc +1.40.0 slow_compilation.rs  21.16s user 0.58s system 99% cpu 21.743 total
$ time rustc +1.41.0 slow_compilation.rs
rustc +1.41.0 slow_compilation.rs  59.95s user 0.69s system 99% cpu 1:00.66 total
$ time rustc +1.50.0 slow_compilation.rs
rustc +1.50.0 slow_compilation.rs  48.87s user 0.75s system 99% cpu 49.634 total
$ time rustc +nightly slow_compilation.rs
rustc +nightly slow_compilation.rs  50.08s user 0.60s system 100% cpu 50.671 total
```

Compiling slowed down in 1.41.0. Though there are some improvements in the latest versions, it is still slow.

Here is flamegraph of rust compiler against compiling the code:

![flamegraph](https://user-images.githubusercontent.com/4434568/106348141-59f3c180-6307-11eb-818e-75d0e0723a70.png)

I `git bisect`ed and found the problem is introduced in this PR: https://github.com/rust-lang/rust/pull/66408

### Code

I tried this code:

```rust
use std::fmt::Display;
use std::marker::PhantomData;

pub trait Pass<T, E> {
    type Target;
    fn trans(&mut self, t: T) -> Result<Self::Target, E>;
}

pub struct PrintablePass<T>(pub T, pub &'static str);

impl<T, In, Out, Err> Pass<In, Err> for PrintablePass<T>
where
    T: Pass<In, Err, Target = Out>,
    Out: Display,
{
    type Target = Out;

    fn trans(&mut self, i: In) -> Result<Self::Target, Err> {
        let o = self.0.trans(i)?;
        Ok(o)
    }
}

pub struct Chain<F, FO, S, SO> {
    pub fst: F,
    pub snd: S,
    phantom: PhantomData<(FO, SO)>,
}

impl<F, FO, S, SO> Chain<F, FO, S, SO> {
    pub fn new(fst: F, snd: S) -> Self {
        Chain {
            fst,
            snd,
            phantom: PhantomData,
        }
    }
}

impl<F, E, S, T, In, Out> Pass<In, E> for Chain<F, T, S, Out>
where
    F: Pass<In, E, Target = T>,
    S: Pass<T, E, Target = Out>,
{
    type Target = Out;

    fn trans(&mut self, i: In) -> Result<Self::Target, E> {
        let &mut Chain {
            ref mut fst,
            ref mut snd,
            ..
        } = self;
        let t = fst.trans(i)?;
        let o = snd.trans(t)?;
        Ok(o)
    }
}

#[macro_export]
macro_rules! compile_pass {
    ($($labels: ident : $passes: expr,)*) => {
        compile_pass!($($labels: $passes),*)
    };
    ($label: ident : $pass: expr, $($labels: ident : $passes: expr),*) => {
        Chain::new(PrintablePass($pass, stringify!($label)), compile_pass!($($labels: $passes),*))
    };
    ($label: ident : $pass: expr) => {
        PrintablePass($pass, stringify!($label))
    };
}

macro_rules! def_pass {
    ($name: ident) => {
        struct $name;
        impl<'a> Pass<&'a str, ()> for $name {
            type Target = &'a str;
            fn trans(&mut self, i: &'a str) -> Result<Self::Target, ()> {
                Ok(i)
            }
        }
    };
}

def_pass!(Parse);
def_pass!(Desugar);
def_pass!(Rename);
def_pass!(VarToConstructor);
def_pass!(Typer);
def_pass!(CaseSimplify);
def_pass!(AST2HIR);
def_pass!(ConstructorToEnum);
def_pass!(Simplify);
def_pass!(FlatExpr);
def_pass!(FlatLet);
def_pass!(UnnestFunc);
def_pass!(ForceClosure);
def_pass!(HIR2MIR);
def_pass!(UnAlias);
def_pass!(BlockArrange);
def_pass!(MIR2LIR);
def_pass!(LIR2WASM);

pub fn compile_str<'a>(input: &'a str) -> Result<&'a str, ()> {
    let mut passes = compile_pass![
        parse: Parse,
        desugar: Desugar,
        rename: Rename,
        var_to_constructor: VarToConstructor,
        typing: Typer,
        case_simplify: CaseSimplify,
        ast_to_hir: AST2HIR,
        constructor_to_enum: ConstructorToEnum,
        simplify: Simplify,
        flattening_expression: FlatExpr,
        flattening_let: FlatLet,
        unnest_functions: UnnestFunc,
        closure_conversion: ForceClosure,
        hir_to_mir: HIR2MIR,
        unalias: UnAlias,
        block_arrange: BlockArrange,
        mir_to_lir: MIR2LIR,
        backend: LIR2WASM,
    ];

    passes.trans(input)
}

fn main() {}

```

I expected to see this happen: compiles in < 30s

Instead, this happened: compiles in > 60s

### Version it worked on

<!--
Provide the most recent version this worked on, for example:

It most recently worked on: Rust 1.47
-->

It most recently worked on: 1.40.0

### Version with regression

<!--
Provide the version you are using that has the regression.
-->

`rustc --version --verbose`: 
```
rustc +1.41.0 --version --verbose
rustc 1.41.0 (5e1a79984 2020-01-27)
binary: rustc
commit-hash: 5e1a799842ba6ed4a57e91f7ab9435947482f7d8
commit-date: 2020-01-27
host: x86_64-unknown-linux-gnu
release: 1.41.0
LLVM version: 9.0
```

<!--
Did the compiler crash? If so, please provide a backtrace.
-->

### Backtrace
<!--
Include a backtrace in the code block by setting `RUST_BACKTRACE=1` in your
environment. E.g. `RUST_BACKTRACE=1 cargo build`.
-->
<details><summary>Backtrace</summary>
<p>

```
<backtrace>
```

</p>
</details>

<!--
If you know when this regression occurred, please add a line like below, replacing `{channel}` with one of stable, beta, or nightly.

@rustbot modify labels: +regression-from-stable-to-{channel} -regression-untriaged
-->