exponential build times when returning impl T

[camshaft]

I work on the s2n-quic project. We have Client and Server builders that allow applications to configure the behavior of the library through several "providers":

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. 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:

    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

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

[epage]

Unsure if winnow-rs/winnow#322 is the same or not. It was fixed on my side with winnow-rs/winnow#323 which didn't remove impl Trait but instead replacing one of the closures with an explicit struct that gets returned through impl Trait.

For the user reporting it, enabling the wrapping function (trace) took build times from 0.3s to 30 minutes.