This is an accompanying PR to my blog post at https://isuffix.com/runtime-math-parsing arguing that we should revert #6442 and use runtime parsing for Typst's math syntax. The blog post argues why, while this description discusses the implementation.

Also, since this is my first PR as @isuffix, I'll mention that I've changed my account over from @wrzian so that I can use isuffix as a consistent username around the internet. Hi!

As usual for my PRs, this is best reviewed commit-by-commit.

(1,2) Two independent commits

The first two commits are used by the later changes, but would likely be useful outside of this PR. However, they're small enough that I didn't want to separate out two other PRs for them. If you would prefer them as separate PRs, let me know and I can split those out.

The first commit turns a potentially $O(n)$ runtime in the sibling node calculation to $O(1)$.

The second commit simplifies MathPrimes by removing the unnecessary Prime SyntaxKind, and also adds a new Bang kind for passing info about exclamation points in math mode from the lexer to the current parser. However, the Bang kind should never be observeable outside the parser in the normal math parsing.

(3) Adding tests

The third commit adds tests that pass with the existing code. These are modified alongside other tests in the next commits as the runtime parser is implemented.

(4) AST Preparation

This commit updates the existing lexer, parser, and AST to output a flat list of math tokens when the MATH_RUNTIME boolean is set to true (but leaves it false). Instead of the Math SyntaxKind, we now output a MathTokens SyntaxKind. This also adds new SyntaxKinds for opening and closing delimiters, MathOpening and MathClosing, so that the AST can avoid extra analysis of token characters. And ast.rs has plenty of comments for the new ast structs/enums.

I also updated the highlighter to ensure tokens are highlighted as before when MATH_RUNTIME is true. This is tested by the raw-highlight-typm-extra test from the previous commit.

(5) Implementation

This commit toggles MATH_RUNTIME to true, implements the runtime parser in typst-eval/src/math_parser/{mod, parser, tokens}.rs, updates many tests with new error messages or results.

The math_parser/parser.rs and math_parser/tokens.rs files are heavily commented, and should be the main part of this review. I've iterated on these files a ton, but I'm still open to feedback and changes. And I'm certain that I've become blind to a bunch of possible simplifications or helpful renamings since I've been writing this for a while, so I'm excited to see what you think of the interface!

This PR does not lex math shorthands at runtime, but has been designed so that lexing shorthands at runtime (and adding runtime configuration of shorthands) should be straightforward if desired in the future.

This commit also changes the test runner at tests/src/run.rs to not fail tests when error ranges differ. This avoids a lot of noise when checking tests and is reverted in the SpanPlus commit.

(6) Fix deparenthesizing fractions

Three tests were added to skip.txt in the previous commit because they involved the new fraction variants and require deparenthesizing logic. This commit is a simple hacking to get the necessary information in the right spots to make the fraction variants work with deparenthesizing.

My original work on this PR was largely before the new fraction variants were added, so it was more natural to leave this as a separate commit.

The reason I still have this split out from the overall implementation is to highlight these changes and, because I think there's likely a better design for fraction deparenthesizing if we do go with runtime math parsing.

(7) Add SpanPlus to diagnostics

This adds the SpanPlus concept and wires it up in the runtime parser so that we can have accurate error ranges despite the math tokens being a flat list. Most of the implementation is making sure that users of SourceDiagnostic use the correct range. This had a surprisingly long tail of changes that led to a series of tricky compiler errors, but I believe the implementation is now correct.

I was not bold enough to add this concept to spans themselves, as that would have a much higher implementation/performance cost at relatively little gain. This means that spanned values may still only use their initial span, causing some error messages to be worse.

You can see some worse error ranges in math-{cases,mat,vec}-linebreaks and math-call-named-single-char-error. However some errors now have better ranges, such as math-call-unclosed-func and math-call-spread-multiple-exprs

(8) Fix IDE tests

I kept this commit separate to highlight that the VM tracing is solely for autocompletion support. This is a part of the compiler I'm not confident in, so I've left a TODO comment since I'm unsure if tracing should happen in those locations or elsewhere. Feedback is appreciated :)

(9) Purge

The final commit, purging the existing math parser, isn't actually present yet. And won't be needed until the final direction is chosen, so I've declined to implement it for now as it would consistently conflict with changes made to previous commits making rebasing a hassle.

However an initial attempt shows that it would delete roughly 800 lines, leading this PR to be somewhere around +1800, -800, or roughly 1000 new lines of code to implement runtime parsing. I'm overall pretty happy with this number, especially since more than 10% of the new lines are descriptive comments.