Investigate rolling PEG parser for Textmate scope selectors in WASM format

[zm-cttae]

⚡️️ Feature Request

• I'm using the latest version of vscode-textmate-languageservice available.
• I searched existing issues, open & closed. Yes, my feature request is new.

Is your feature request related to a problem?

The Textmate scope selector shows below-par performance due to exponential expense in path in grammar specification.

Describe the solution you'd like

• Port PEG parser to Rust using pest (rust-peg).
• Build parser using Rust toolchain for WASM generation.
• Confirm WASM code & bindings works vs specification with no regressions.

Describe alternatives you've considered

Already written FastScopeSelector for scope & path in linear time O(cN)
c = the number of alphanumeric scope atoms.

[zm-cttae]

changed due date to March 31, 2023

[zm-cttae]

removed due date

[zm-cttae]

https://pest.rs/

PEG grammar in Rust

space = _{ " " | "\t" }
string = @{ ASCII_ALPHANUMERIC | "_" | "+" }
segment = @{ ( string ~ (string | "-")* | "*") }
atom = { space* ~ segment ~ space* }
scope = { atom ~ ( "." ~ atom )* }
prefix = { "L" | "R" | "B" }
path = { (prefix ~ ":")? ~ scope ~ (space* ~ scope)* }
group = { (prefix ~ ":")? ~ "(" ~ space* ~ selector ~ space* ~ ")" }
negation = { "-" }
expression = { (negation ~ group) | (negation ~ path) | group | path }
operator = { "|" | "&" | "-" }
composite = { (expression ~ space* ~ operator ~ space* ~ composite) | expression }
selector = { (composite ~ space* ~ "," ~ space* ~ selector?) | composite }
start = { selector }

[zm-cttae]

Optimised Pest parser:

WHITESPACE          = _{ " " | "\t" }

atom                = { !("-") ~ (ASCII_ALPHANUMERIC | "+" | "_" | "-")+ }
asterisk            = { "*" }
segment             = { atom | asterisk }

scope               = { segment ~ ("." ~ segment)* }

prefix              = { "L" | "R" | "B" }

path                = { (prefix ~ ":")? ~ scope ~ (WHITESPACE+ ~ scope)* }
group               = { (prefix ~ ":")? ~ "(" ~ selector ~ ")" }

MINUS_OPERATOR      = { "-" }
expression          = { MINUS_OPERATOR? ~ (group | path) }

COMPOSITE_OPERATOR  = { "|" | "&" | "-" }

composite           = { expression ~ (COMPOSITE_OPERATOR ~ composite)? }
selector            = { composite ~ ("," ~ selector)? }

start               = { selector }

Let's try rust-peg first though..

[zm-cttae]

Cost saving is 10-40% using rust-peg compiled to WASM. This isn't good enough to justify switching.