Repository: rust
Issue: exponential build times when returning `impl T`
Labels: I-compiletime,T-compiler,C-bug

I work on the [`s2n-quic`](https://github.com/aws/s2n-quic) project. We have [`Client`](https://docs.rs/s2n-quic/latest/s2n_quic/client/struct.Builder.html) and [`Server`](https://docs.rs/s2n-quic/latest/s2n_quic/server/struct.Builder.html) builders that allow applications to configure the behavior of the library through several "providers":

```rust
Server::builder()
    .with_connection_id(MyConnectionId)?
    .with_limits(MyLimits)?
    .with_tls(MyTls)?
    .with_io(MyIo)?
    .build()?;
```

We noticed that as the number of configured providers increased, the time that `rustc` spends type checking exponentially increases. I've created a standalone example of this behavior [in a gist](https://gist.github.com/camshaft/a13940a5c4bd8d204bade82a69eb0ff6). Note that it doesn't even need to call different providers; the example calls `with_a` over and over again with the same type.

The issue seems to be with the use of `impl T` in each of the `with_*` functions:

```rust
    pub fn with_a<T, U>(self, value: T) -> Builder<impl Providers>
    where
        T: a::Provider,
        U: Providers,
        Self: a::With<T, Output = U>,
```

If the return type is changed to `Builder<U>`, the compile time is unchanged in relation to the number of calls.

|         | impl T | U     |
|---------|--------|-------|
| depth 1 | 0.12s  | 0.12s |
| depth 2 | 0.12s  | 0.12s |
| depth 3 | 0.13s  | 0.12s |
| depth 4 | 0.15s  | 0.12s |
| depth 5 | 0.44s  | 0.12s |
| depth 6 | 5.45s  | 0.12s |
| depth 7 | 1m10s  | 0.12s |

Here's a summary from the self-profile:

| Item                                            | Self time | % of total time | Time     | Item count |
|---------|--------|-------|---|---|
| evaluate_obligation                             | 17.58s    | 31.904          | 17.58s   | 340        |
| check_mod_privacy                               | 13.71s    | 24.876          | 13.71s   | 2          |
| typeck                                          | 10.95s    | 19.881          | 19.21s   | 10         |
| type_op_prove_predicate                         | 7.05s     | 12.803          | 16.38s   | 121        |
| mir_borrowck                                    | 4.43s     | 8.035           | 22.13s   | 10         |
| normalize_projection_ty                         | 1.32s     | 2.387           | 1.32s    | 131        |
| self_profile_alloc_query_strings                | 14.69ms   | 0.027           | 26.63ms  | 1          |

My expectation is that `impl T` would be equivalent to `U` in the amount of type checking needed. My preference would be to use `impl T`, as it keeps the display size of the type in the UI minimal.

Let me know if you need any additional details 😃.

### Meta
<!--
If you're using the stable version of the compiler, you should also check if the
bug also exists in the beta or nightly versions.
-->

`rustc --version --verbose`:
```
rustc 1.63.0 (4b91a6ea7 2022-08-08)
binary: rustc
commit-hash: 4b91a6ea7258a947e59c6522cd5898e7c0a6a88f
commit-date: 2022-08-08
host: x86_64-apple-darwin
release: 1.63.0
LLVM version: 14.0.5
```

nightly (for the self-profile):
```
rustc 1.65.0-nightly (0b79f758c 2022-08-18)
binary: rustc
commit-hash: 0b79f758c9aa6646606662a6d623a0752286cd17
commit-date: 2022-08-18
host: x86_64-apple-darwin
release: 1.65.0-nightly
LLVM version: 15.0.0
```

I also tested this behavior on an old version of `rustc` (1.35) and compile times were actually worse so there has been some improvement since then.

```
rustc 1.35.0 (3c235d560 2019-05-20)
binary: rustc
commit-hash: 3c235d5600393dfe6c36eeed34042efad8d4f26e
commit-date: 2019-05-20
host: x86_64-apple-darwin
release: 1.35.0
LLVM version: 8.0
```