How to get input change ranges in `createParse`?

Lezer
1

I have implemented a Parser for typst language not by writing lezer grammar but by modifying the official typst-syntax rust library and compile it to WebAssembly: GitHub - kxxt/codemirror-lang-typst: (Experimental) Typst language support for CodeMirror editor .

The typst wasm parser implements incremental parsing by accepting edits to the Input in the form of “(start, end) range of document is replaced by new string S”.

However, lezer takes a different approach for incremental parsing and instead provides TreeFragments. Thus when implementing the Parser interface I cannot get the original changes that I could feed into the Typst wasm parser.

Thus I have taken a hacky approach. By adding a StateField that is purely used to listen for document changes, I could use transaction.changes.iterChanges to feed the document changes into Typst wasm parser and update the syntax tree. Then the createParse function and the returned PartialParse becomes a thin wrapper for retrieving the updated syntax tree.

There doesn’t appear to be any troubles with this approach at first. However, recently I discovered that there is a problem with that approach. I noticed that when using Alt + Up/Down shortcuts to swapping the lines, the syntax highlighting goes wrong.

I added some logging and found that it is caused by codemirror calling createParse before calling the update hook of my StateField. Thus codemirror uses the old syntax tree before update hook updates the syntax tree:

Create parse 
Array [ {…} ]
 
Array [ {…} ]
index.js:117:17
Getting tree tree@http://127.0.0.1:5173/@fs/home/kxxt/repos/frontend/codemirror-lang-typst/dist/index.js?t=1764856939048:172:37
advance@http://127.0.0.1:5173/@fs/home/kxxt/repos/frontend/codemirror-lang-typst/dist/index.js?t=1764856939048:32:28
work/<@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-GDXMNLOU.js?v=c2f469c4:280:31
withContext@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-GDXMNLOU.js?v=c2f469c4:318:14
work@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-GDXMNLOU.js?v=c2f469c4:269:17
apply@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-GDXMNLOU.js?v=c2f469c4:452:16
update@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-GDXMNLOU.js?v=c2f469c4:472:18
update@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-JEVQZFNC.js?v=c2f469c4:1699:26
applyTransaction/<@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-JEVQZFNC.js?v=c2f469c4:2344:85
ensureAddr@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-JEVQZFNC.js?v=c2f469c4:1925:23
field@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-JEVQZFNC.js?v=c2f469c4:2293:15
syntaxTree@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-GDXMNLOU.js?v=c2f469c4:175:21
matchBrackets@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-GDXMNLOU.js?v=c2f469c4:1619:24
update@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-GDXMNLOU.js?v=c2f469c4:1586:32
update@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-JEVQZFNC.js?v=c2f469c4:1699:26
applyTransaction/<@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-JEVQZFNC.js?v=c2f469c4:2344:85
ensureAddr@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-JEVQZFNC.js?v=c2f469c4:1925:23
_EditorState@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-JEVQZFNC.js?v=c2f469c4:2283:17
applyTransaction@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-JEVQZFNC.js?v=c2f469c4:2344:5
get state@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-JEVQZFNC.js?v=c2f469c4:2083:23
update@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-Y5U2FH3O.js?v=c2f469c4:7237:7
_EditorView/this.dispatchTransactions<@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-Y5U2FH3O.js?v=c2f469c4:7197:145
dispatch@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-Y5U2FH3O.js?v=c2f469c4:7219:10
moveLine@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-NO7WYYRO.js?v=c2f469c4:1022:11
moveLineUp@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-NO7WYYRO.js?v=c2f469c4:1030:51
runFor@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-Y5U2FH3O.js?v=c2f469c4:8226:18
runHandlers@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-Y5U2FH3O.js?v=c2f469c4:8242:15
keydown@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-Y5U2FH3O.js?v=c2f469c4:8123:12
bindHandler/<@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-Y5U2FH3O.js?v=c2f469c4:4225:22
runHandlers@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-Y5U2FH3O.js?v=c2f469c4:4137:20
handleEvent@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-Y5U2FH3O.js?v=c2f469c4:4127:12
EventListener.handleEvent*ensureHandlers@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-Y5U2FH3O.js?v=c2f469c4:4155:15
_EditorView@http://127.0.0.1:5173/node_modules/.vite/deps/chunk-Y5U2FH3O.js?v=c2f469c4:7208:21
setupEditor@http://127.0.0.1:5173/src/editor.ts:17:10
@http://127.0.0.1:5173/src/main.ts?t=1764857413708:29:21

I think the correct fix requires removing the StateField hack and properly save the document changes in createParse() and pass them into the Typst wasm parser during advance().

However, it is unclear to me how to get the document changes in createParse as Lezer uses a different incremental parsing model.

Could anyone suggest a solution (or more hacks to make a hook run before functions like moveLineUp)?

Thanks!

2

Isn’t it possible to construct these replacements from the tree fragments? Those represent unchanged ranges, which are more or less the dual of changed ranges.

3

Thanks for the suggestion!

I indeed tried to map the TreeFragments back to replacements.
But it appears that they are not equivalent. For example, when swapping == Why and are lines in the following document

== Hello
World

== Why
are

= You
hrere

The fragments passed to createParse is

Array [ {…} ]
​
0: Object { from: 26, to: 39, offset: 0, … }
​​
from: 26
​​
offset: 0
​​
open: 1
​​
to: 39
​​
tree: Object { kind: 6, length: 39, erroneous: false, … }
​​
<prototype>: Object { … }
​
length: 1
​
<prototype>: Array []

contains the tail part of this document after are.

However, the first three lines of the document is also unchanged but I couldn’t know it from the fragments. In an update() hook of a StateField, I could retrieve the exact change information.

4

The lezer tree fragments will indeed not be precise—they are conservative, in that they don’t include a range directly around changes because the Lezer LR parser has a certain minimum re-parse distance so that it can avoid marking every tree with a lookahead.

This sounds like you want to do your own parsing scheduling, rather than relying on the one in @codemirror/language. Maybe the way forward here would be to make the parse worker implementation pluggable, so you can do your own thing, without changing the way the existing worker is structured?

5

That sounds great. But I checked the current parser worker implementation and found that it needs a lot internal types and fields so it might not be easy to be made pluggable.

Typst’s official web editor (typst.app) is also using codemirror but I am not exactly sure how they do it. The only thing I know is that they also don’t lezer grammar and implements almost everything in a WASM blob.

I also tried to write a lezer grammar before hacking together lezer and a wasm parser.
But I abandoned that after seeing that Markdown parsing is implemented through a custom parser.

6

They don’t appear to use the tree functionality at all (the editor has no syntax tree). I suppose there’s a custom highlighter running on top of their own parse tree, without ever converting it to Lezer.

That may actually be a reasonable way to do this.