Exponential compile time with recursive opaque type

[Skepfyr]

Code

I tried this code:

fn bar() -> impl Fn() {
    wrap(wrap(wrap(wrap(foo()))))
}

fn foo() -> impl Fn() {
    wrap(wrap(wrap(wrap(wrap(wrap(wrap(foo())))))))
}

fn wrap(f: impl Fn()) -> impl Fn() {
    move || f()
}

I expected running cargo check to produce an error like:

error[E0720]: cannot resolve opaque type
 --> src/lib.rs:5:13
  |
5 | fn foo() -> impl Fn() {
  |             ^^^^^^^^^ recursive opaque type
6 |     ((wrap(wrap(wrap(wrap(wrap(foo())))))))
  |     --------------------------------------- returning here with type `impl Fn<()>`
...
9 | fn wrap(f: impl Fn()) -> impl Fn() {
  |                          --------- returning this opaque type `impl Fn<()>`

It does, but cargo check takes time exponential in the number of wrap calls, although doesn't appear to use any extra memory.
In foo the time take looks like:

Num wrapss	Time taken (s)
4	0.5
5	2.1
6	28
7	436

I believe it's also exponential in the number of wrap calls in bar.

The reason I had code like this was because I was using nom's parser combinators which results in lots of nested closures. I spotted it because this caused rust-analyzer to hang because cargo clippy hung (it looks like check was the issue), I had to kill clippy to fix it.

Bisection results

I bisected this (with cargo-bisect-rustc) to find the regression in nightly-2019-10-16, which contained the following bors commits:

1. Auto merge of Rollup of 4 pull requests #65433 - Centril:rollup-rzvry15, r=Centril
2. Auto merge of Rollup of 14 pull requests #65454 - tmandry:rollup-0k6jiik, r=tmandry
3. Auto merge of Update clippy #65450 - Manishearth:clippyup, r=Manishearth
4. Auto merge of use precalculated dominators in explain_borrow #65172 - tanriol:explain_borrow-use-context-dominators, r=nagisa
5. Auto merge of Update cargo, books #65445 - ehuss:update-cargo-books, r=alexcrichton

@rustbot modify labels: +regression-from-stable-to-stable -regression-untriaged

[jyn514]

@Skepfyr what version of rust are you using? Is this also present on nightly?

[Skepfyr]

Good question! This repros on the latest nightly (nightly-2021-07-24) and on stable (1.53.0 2021-06-17).

[klensy]

I bisected this (with cargo-bisect-rustc) to find the regression in nightly-2019-10-16, which contained the following bors commits:

Regression means that it was linear, or exponential, but smaller?

[Skepfyr]

I didn't check....it looks to still be exponential just much quicker, and with a smaller base (~2 vs ~14):

nightly-2019-10-16

Num calls	Time (s)
15	0.68
16	1.3
17	2.7
18	5.6
19	12
20	25

[ibraheemdev]

#65293 looks related

[hkratz]

Bisected to innocent-looking commit fe09bb5. Removing the caching from OpaqueTypeExpander in master does indeed fix the issue. I haven't looked at the how or why or where that causes (other) problems though.

cc @tmandry

[jyn514]

Hmm, the only thing that looks expensive there is the hashing - I wonder if it's hashing substs over and over again without ever getting a cache hit? Hashing DefId has a fixed cost, but SubstsRef can be an arbitrary length: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/subst/type.InternalSubsts.html

[hkratz]

#87546 cuts down on time for this testcase and others with invalid recursive opaque types by bailing out early if a recursion is found.

This fixes the regression but the check time is still exponential in the recursion:

#wraps	time (s)
23	9.2
24	18.3
25	36.6

Not sure if that matters in practice though.

[apiraino]

Assigning priority as discussed in the Zulip thread of the Prioritization Working Group.

@rustbot label -I-prioritize +P-high

[jyn514]

This fixes the regression but the check time is still exponential in the recursion:

That's the same as before the regression, right? I definitely think that's a change worth making :) I expect the doubling will have a completely different cause.

[hkratz]

That's the same as before the regression, right?

Yes, same ballpark.