pest-parser / pest-parser/pest

Stack overflow, long compile times with large repetition values

Open
#596 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug compilation-time
Dominant language
Rust
Stars
5.4k
Forks
307
Avg merge
8h 23m
Merged PRs (30d)
5

Description

When implementing a spec based on an RFC, I wrote a rule like text{0,998}, as the spec (RFC5322) dictates that lines cannot exceed 998 characters.

This dramatically increased compile times from negligible to many seconds. Changing this to text* and doing that validation step in other code eliminates the problem.

By varying the repeat count in the rule and running tests on an Mac Mini (M1 2020):

  • text{0,2048} = 36.04s
  • text{0,998} = 8.77s
  • text{0,512} = 2.94s
  • text{0,256} = 1.12s
  • text{0,128} = 0.62s

Beyond a certain point it's just a "stack overflow":

  • text{0,3000} = fatal runtime error: stack overflow

Is this a known limitation of the implementation of limited repeat?

Sample grammar:

CRLF = _{ "\r"? ~ "\n" } // Relaxed definition

body = { (text{0,2600} ~ CRLF)* ~ text{0,2600} ~ CRLF? }
text = { '\u{01}'..'\u{09}' | '\u{0b}'..'\u{0c}' | '\u{0e}'..'\u{7f}' }

I tried this in the snippet generator but I think it can't handle it because of this issue.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reproducing the sample grammar and varying the limited repeat values, using the reported timings and stack-overflow threshold as a baseline. Check the limited-repeat implementation and the snippet generator behavior; done means large repeat values no longer cause prohibitive compile times or a stack overflow, with regression coverage added where the implementation's tests belong.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.