Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Parsing is slow #79

Open
uncomputable opened this issue Aug 21, 2024 · 0 comments
Open

Parsing is slow #79

uncomputable opened this issue Aug 21, 2024 · 0 comments

Comments

@uncomputable
Copy link
Collaborator

The PEST parser struggles with series of open brackets that are not closed. This means that the fuzzer runs slow units that take up to hundreds of seconds to parse.

fn n(){ { (s,(( (Ns,(s,(x,(((s,((s,(s,(s,(x,(( {5
fn fnnfn(MMet:(((sssss,((((((sssss,ssssss,ss,((((((sssss,ss,((((((sssss,ssssss,ss,((((((sssss,ssssss,((((((sssss,sssssssss,(((((((sssss,sssssssss,(((((ssss,((((((sssss,sssssssss,(((((((sssss,ssss,((((((sssss,ss,((((((sssss,ssssss,ss,((((((sssss,ssssss,((((((sssss,sssssssss,(((((((sssss,sssssssss,(((((ssss,((((((sssss,sssssssss,(((((((sssss,sssssssssssss,(((((((((((u|(
fn nf224(jet:J ){{{{{{{{{{{{ {     {{ {  { {   {{

Maybe the grammar file that I wrote contains anti patterns that needlessly slow down the parser. So far I haven't found a resource on these, but I will keep looking and I will try to rewrite the file.

It could also be that the PEST parser is inherently slow. In this case, we will have to move to a different parser. However, I will hold off on such a massive change until more important work has been done.
@uncomputable uncomputable mentioned this issue Aug 21, 2024
Merged
apoelstra added a commit that referenced this issue Aug 21, 2024
@apoelstra
Merge #78: Add fuzzing + CI
26ece01 
fcc9c6f test: Add Github CI (Christian Lewe)
cd8cb5e feat: Add justfile (Christian Lewe)
2cb71d0 feat: Add nix flake (Christian Lewe)
f782a80 doc: Add fuzz README (Christian Lewe)
96bab4d feat: Add fuzz subcrate (Christian Lewe)
6526f0d feat: Impl Arbitrary for parse tree (Christian Lewe)
65aebc8 feat: Impl Arbitrary for Pattern (Christian Lewe)
c50f59c feat: Impl Arbitrary for AliasedType (Christian Lewe)
3d7fcb6 feat: Impl Arbitrary for Value (Christian Lewe)
27fcf68 feat: Impl Arbitrary for str and num types (Christian Lewe)
75c033e feat: Add ArbitraryRec trait (Christian Lewe)
6ab0c9f Cargo: Add arbitrary (Christian Lewe)

Pull request description:

  Fixes #72

  Implement fuzzing (`Arbitrary`) for the Simfony parse tree and write three fuzz targets:

  1. `compile_text`: try to compile random ASCII strings; slow because of parser (#79)
  2. `compile_parse_tree`: try to compile random parse trees; ~10x faster than `compile_text` and better coverage
  3. `display_parse_tree`: check that `Display` → `ParseFromStr` is the identity function

  Write a simple CI that uses nix flakes and dev shells. This CI is not more reproducible than regular GitHub CI, but it saves me time because I already have nix infrastructure in place. I will switch the CI to something reproducible in the near future.

  Run the linter, unit tests (stable + MSRV) and the fuzzer in CI. For now, coverage is ignored in CI.

ACKs for top commit:
  apoelstra:
    ACK fcc9c6f successfully ran local tests

Tree-SHA512: bad0ea7ec838b3b31e74d2d8c8c41497e86e474e011c49b40b1dccd18bc69a4b58d238a51189517667256fe5aba2e81dc87e4c76333ab672c800c942c085ad98
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@uncomputable