NLL exponential(?) increase in compile times when nesting borrowed futures

[david-mcgillicuddy-moixa]

When nesting futures in the pattern:

trait Foo<'a> {
    fn get_unit(&'a self) -> Box<dyn Future<Item=(), Error=Box<dyn Error+'a>> + 'a>;
    fn foo(&'a self) -> Box<dyn Future<Item=Vec<()>, Error=Box<dyn Error+'a>> + 'a> {
        Box::new(
            self.get_unit().and_then(move |unit1| {
                self.get_unit().and_then(move |unit2| {
                    ...

I get a blow up in complation times at around n = 10 or 11.
N = 9 takes 15 seconds, N = 10 takes 83 seconds, and N = 11 takes 18 minutes.

Switching things to the static lifetime make the times reasonable again.

Playground link showing the full example: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=136faa5e507b53e587480d23f9fc87d8

It happens on both nightly and stable. I ran with cargo rustc -- -Z time-passes and got:

...
  time: 0.862	item-bodies checking
    time: 0.029	rvalue promotion + match checking
    time: 0.002	liveness checking + intrinsic checking
  time: 0.031	misc checking 2
  time: 0.000	borrow checking
    time: 0.000	solve_nll_region_constraints(DefId(0:38 ~ my_crate[cd01]::async_mod[0]::Foo[0]::get_unit[0]))
    time: 0.000	solve_nll_region_constraints(DefId(0:50 ~ my_crate[cd01]::async_mod[0]::Foo[0]::foo[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]))
    time: 0.000	solve_nll_region_constraints(DefId(0:49 ~ my_crate[cd01]::async_mod[0]::Foo[0]::foo[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]))
    time: 0.000	solve_nll_region_constraints(DefId(0:48 ~ my_crate[cd01]::async_mod[0]::Foo[0]::foo[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]))
    time: 0.001	solve_nll_region_constraints(DefId(0:47 ~ my_crate[cd01]::async_mod[0]::Foo[0]::foo[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]))
    time: 0.006	solve_nll_region_constraints(DefId(0:46 ~ my_crate[cd01]::async_mod[0]::Foo[0]::foo[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]))
    time: 0.040	solve_nll_region_constraints(DefId(0:45 ~ my_crate[cd01]::async_mod[0]::Foo[0]::foo[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]))
    time: 0.207	solve_nll_region_constraints(DefId(0:44 ~ my_crate[cd01]::async_mod[0]::Foo[0]::foo[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]))
    time: 1.486	solve_nll_region_constraints(DefId(0:43 ~ my_crate[cd01]::async_mod[0]::Foo[0]::foo[0]::{{closure}}[0]::{{closure}}[0]::{{closure}}[0]))
    time: 13.384	solve_nll_region_constraints(DefId(0:42 ~ my_crate[cd01]::async_mod[0]::Foo[0]::foo[0]::{{closure}}[0]::{{closure}}[0]))
    time: 124.880	solve_nll_region_constraints(DefId(0:41 ~ my_crate[cd01]::async_mod[0]::Foo[0]::foo[0]::{{closure}}[0]))
    time: 0.000	solve_nll_region_constraints(DefId(0:40 ~ my_crate[cd01]::async_mod[0]::Foo[0]::foo[0]))
  time: 143.577	MIR borrow checking
...
   Finished dev [unoptimized + debuginfo] target(s) in 2m 28s

[david-mcgillicuddy-moixa]

It might be the same issue as #58178 which also talks about closure borrows in NLL checking, not sure though.

[david-mcgillicuddy-moixa]

After a little more investigation it does actually still happen when the closures are static, just not as badly.

[david-mcgillicuddy-moixa]

I notice that the issue #58178 was closed due to large improvements so I checked again and unfortunately there's no change of behaviour here on both 1.38.0 and 7th Oct 1.40.0-nightly. You still get timeouts (i.e. compilation time blow up) when nesting too much.

[david-mcgillicuddy-moixa]

So I did actually revisit this, just to update it to modern futures and interestingly it no longer happens without the error:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=59c236b82d60dd14dd4233fc6724b66b

but it does seem to still happen when the borrowed error is included (but has been improved, I had to add a few more cases to get back to the same playground timeout):
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=a3b7c5ab355532e27a686705a78171fc