RFC: Use a non-regex parser

[epage]

This is a possible enhancement that could make it easier to address some of our bugs and missing features.

The downside is that shopofy/liquid uses regex iirc so it'll be more difficult to follow their grammar. I have heard that there are some differences in the regex engines that already cause some problems.

Goals

• Performance (faster than what we have now at least)
• Making it easier to implement features, for example
  • More complex indexing (Allow expressions in indexed variables #145)
  • Variable includes (Add variable support ({% include {{ page.my_variable }} %}) to our Jekyll-style include #142)
  • Named arguments for filters (Support for named arguments in filters #92, also requires changes to filter API)
  • nil literals (Support nil literals #223)
  • blank / empty keywords (Support blank and empty literals #222)
• Generally easier to maintain
• A concise top-level that reduces churn (all helpers can be moved into a sub-crate and break compat whenever)
• File location information in errors (formerly Display line (and column?) in syntax errors #232)

Background

There are really to main issues with the current parser

• The performance of the lexer (I'm assuming thats whats so slow)
• The maintainability of the parser

The parser right now is cobbled together functions that have too much logic in them, causing others to duplicate it. For example, the for-block has named arguments but not filters, because we don't have reusable argument parsing. The parser is also inconsistent on how it consumes tokens. A consistent, composible model would be a big help.

Solutions

Patch up the current approach.

The parser could be made more maintainable while keeping the current token stream if desired. We could make combinators for token processing, that return where they left off parsing (maybe even on failure like nom's IResult). We can then refactor all of our parsers into using these combinators so we can have an easier to maintain code base.

Parser comparison

• nom
• Combine
  • Author moved on to lalrop
• Chomp
• pest
• lalrop
• pom

Benchmarks

• https://github.com/Geal/parser_benchmarks
• https://m4rw3r.github.io/parser-combinator-experiments-rust
• https://m4rw3r.github.io/parser-combinator-experiments-errors
• https://m4rw3r.github.io/parser-combinator-experiments-part-3
• https://m4rw3r.github.io/parser-combinators-road-chomp-0-1
• https://github.com/J-F-Liu/pom

Good

• nom
• pest
• chomp

Bad

• Combine
• pom (order of magnitude slower than pest)

Line numbers

Good:

• Pest has it native
• Nom has nom_locate

Composability

Can plugins reuse the grammar without centralizing all token processing which also hurts correctness?

Good:

• Nom

Bad:

• Pest

Partial parsing

An idea to improve performance and API stability.

Good:

• Nom: slice of str
  • Downside is if you need to store the parse results with what you parsed
• Pest: byte position
  • Good for parse results being in a struct with what was parsed

Maintenance

Bad

• Chomp hasn't had a commit in over a year

Brittleness

Bad

• Pest
  • Requires 100% test coverage to ensure grammar changes don't break code.
  • See https://www.reddit.com/r/rust/comments/9xt5sh/introducing_pest_into_glsl_and_hindsight_about/?st=jooy4jhz&sh=dab05392
  • See https://www.reddit.com/r/rust/comments/9xz9c7/introducing_pest_into_glsl_and_hindsight_about/?st=jooy4k81&sh=39cafabf

Ergonomics and Docs

Good

• Pest: only thing to complain about is the syntax is less familiar

Mixed

• Nom: bad ergonomics due to the macros but docs are pretty ok

[epage]

Looks like nom can take in some amount of state. How much we can "plugin" other parsers, no idea.
https://users.rust-lang.org/t/nom-referencing-external-variables-from-parser-s/21249/5

[epage]

Re-openeing because I want to consider this topic some more.