Exponential parse time with nested and out-of-order attributes

[jruderman]

Found with a modified fuzz-rustc

Code

#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]
#![a = { #[y] #![x]

Time complexity

Each additional line roughly doubles the time taken to reject the input.

Where it's slow

From -Z time-passes:

• the slow pass is parse_crate

From sample-head.txt:

• annotate_following_item_if_applicable is on the stack repeatedly

Regression

Regression in nightly-2021-09-06, likely from #88257 (@estebank)

Version

rustc 1.67.0-nightly (1eb62b123 2022-11-27)
binary: rustc
commit-hash: 1eb62b1235fd77200e6bd967d70e83c0f2497233
commit-date: 2022-11-27
host: x86_64-apple-darwin
release: 1.67.0-nightly
LLVM version: 15.0.4

@rustbot label +I-compiletime