Exponential compile time with nested `&dyn Fn` type and lifetime
Open
Nobody has claimed this yet.
C-bug
I-compiletime
T-types
- Dominant language
- Rust
- Stars
- 119k
- Forks
- 16.1k
- PR merge metrics
- PR metrics pending
Description
Found with a modified fuzz-rustc (variant of #104583 that is still slow)
Code
fn main() {}
fn q<'b>(_a: &'b u32)
-> &dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&dyn Fn(&'b u16)))))))))))))
{
3_u8
}
Time complexity
Seems exponential:
| Nesting level | Time |
|---|---|
| 9 | 0.4 sec |
| 10 | 1.6 sec |
| 11 | 6.7 sec |
| 12 | 33 sec |
Where it's slow
- From
-Z time-passes:type_check_crate(full output) - From sampling: seems like recursion involving type comparison (head of sample tree)
Version
rustc 1.75.0-nightly (a2f5f9691 2023-11-02)
binary: rustc
commit-hash: a2f5f9691b6ce64c1703feaf9363710dfd7a56cf
commit-date: 2023-11-02
host: x86_64-apple-darwin
release: 1.75.0-nightly
LLVM version: 17.0.4
@rustbot label +I-compiletime
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by compiling the nested &dyn Fn reproducer from the issue and measuring the nesting levels listed in its timing table. Use the -Z time-passes output for type_check_crate and the sampling output to investigate the recursive type-comparison path. Done means the reproducer no longer shows exponential compile-time growth, with the observed behavior checked against the reported baseline.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers, performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 28/100