Exponential algorithmic complexity on parsing nested brackets #13944
Description
Describe the bug
This is similar to #10439. Found by using the fuzzer with a timeout:
cargo fuzz run parse out seeds -- -timeout=20
How to reproduce
Try parsing this file
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
$a = { |
After around 30 seconds and 2GB of memory use, you should get a parse error. Each additional copy adds a factor of 3 to the total parse time.
Expected behavior
Parse in linear time or at worst quadratic.
Configuration
| key | value |
|---|---|
| version | 0.98.1 |
| major | 0 |
| minor | 98 |
| patch | 1 |
| branch | fix-9072 |
| commit_hash | 4e2e125 |
| build_os | macos-x86_64 |
| build_target | x86_64-apple-darwin |
| rust_version | rustc 1.83.0-nightly (2bd1e894e 2024-09-26) |
| rust_channel | nightly-x86_64-apple-darwin |
| cargo_version | cargo 1.83.0-nightly (eaee77dc1 2024-09-19) |
| build_time | 2024-09-27 09:58:01 +02:00 |
| build_rust_channel | release |
| allocator | mimalloc |
| features | default, sqlite, trash |
| installed_plugins |