Debian Codegraph @

frontend/src/codemirror/tree-sitter-parser.ts

raw
1 /**
2 * Use a tree-sitter parser to generate Lezer parse tree.s
3 *
4 * To be able to reuse the existing tree-sitter grammar and parser for the Fava editor,
5 * this module provides functionality to translate between a tree-sitter parse tree and
6 * a Lezer one.
7 */
8
9 import { DocInput } from "@codemirror/language";
10 import type { Text } from "@codemirror/state";
11 import type {
12 Input,
13 NodePropSource,
14 PartialParse,
15 TreeFragment,
16 } from "@lezer/common";
17 import { NodeProp, NodeType, Parser, Tree } from "@lezer/common";
18 import { styleTags, tags } from "@lezer/highlight";
19 import type {
20 Edit as TSEdit,
21 Parser as TSParser,
22 Tree as TSTree,
23 TreeCursor as TSTreeCursor,
24 } from "web-tree-sitter";
25
26 import type { NonEmptyArray } from "../lib/array";
27 import { is_non_empty, last_element } from "../lib/array";
28 import { assert, log_error } from "../log";
29
30 /** The Lezer NodeType for error nodes. */
31 const error = NodeType.define({
32 id: 65535,
33 name: "ERROR",
34 error: true,
35 props: [styleTags({ ERROR: tags.invalid })],
36 });
37
38 // Since we need to pass points (row, column) to some tree-sitter APIs but
39 // we usually do not have this information, pass this dummy point. Should work
40 // as long as we do not use any of the APIs returning points:
41 // https://github.com/tree-sitter/tree-sitter/issues/445
42 const dummyPosition = Object.freeze({ row: 0, column: 0 });
43
44 /** Get a TS edit for the three byte offsets with dummy row/column-offsets. */
45 function ts_edit(
46 startIndex: number,
47 oldEndIndex: number,
48 newEndIndex: number,
49 ): TSEdit {
50 return {
51 startIndex,
52 oldEndIndex,
53 newEndIndex,
54 startPosition: dummyPosition,
55 oldEndPosition: dummyPosition,
56 newEndPosition: dummyPosition,
57 };
58 }
59
60 /** This node prop is used to store the TS tree on the root node of the Lezer tree for reuse. */
61 const TSTreeProp = new NodeProp<TSTree>({ perNode: true });
62
63 class TSParserError extends Error {}
64
65 class InvalidRangeError extends TSParserError {
66 constructor() {
67 super("Only one range spanning the whole document is supported.");
68 }
69 }
70
71 class MissingLanguageError extends TSParserError {
72 constructor() {
73 super("Parser is missing language.");
74 }
75 }
76
77 /** Information about a change between an old parse and a new one. */
78 interface ChangeDetails {
79 /** The edit (to simplify things, we reduce it to a single change) */
80 edit: TSEdit;
81 /** The old Lezer syntax tree (not adjusted for edit). */
82 old_tree: Tree;
83 /** The TS tree, adjusted for the edit - is used to extend the edit for safe reuse of the Lezer tree. */
84 edited_old_ts_tree: TSTree;
85 }
86
87 /** Deduce a TSParser.Edit from the given Lezer TreeFragments. */
88 export function input_edit_for_fragments(
89 fragments: NonEmptyArray<TreeFragment>,
90 input_length: number,
91 ): TSEdit | null {
92 const [fragment] = fragments;
93 const { tree } = fragment;
94
95 if (!fragments.every((f) => f.tree === tree)) {
96 log_error("expect fragments to all have the same tree", fragments);
97 return null;
98 }
99
100 if (fragments.length === 1) {
101 return fragment.offset === 0
102 ? ts_edit(fragment.to - 1, tree.length, input_length)
103 : ts_edit(0, fragment.from + fragment.offset + 1, fragment.from + 1);
104 }
105
106 const before =
107 [...fragments].reverse().find((f) => !f.openStart && f.openEnd) ?? fragment;
108 const after =
109 fragments.find((f) => f.openStart && !f.openEnd) ?? last_element(fragments);
110
111 const from = before.to;
112 const { offset } = after;
113 const newEndIndex = after.from;
114 const oldEndIndex = newEndIndex + offset;
115
116 return ts_edit(from - 1, oldEndIndex + 1, newEndIndex + 1);
117 }
118
119 /**
120 * A parse can to be started for the same document multiple times.
121 *
122 * Since we only do full parses, we can reuse these trees here.
123 */
124 const PARSE_CACHE = new WeakMap<Text, Tree>();
125
126 /**
127 * This does not support any partial parsing since tree-sitter does not either.
128 *
129 * It tries to reuse any existing trees (as passed indirectly via fragments) to
130 * allow for a faster incremental parse.
131 */
132 class Parse implements PartialParse {
133 stoppedAt: number | null = null;
134
135 parsedPos = 0;
136
137 constructor(
138 readonly ts_parser: TSParser,
139 readonly node_types: NodeType[],
140 readonly input: Input,
141 readonly fragments: readonly TreeFragment[],
142 readonly ranges: readonly { from: number; to: number }[],
143 ) {
144 if (
145 ranges.length !== 1 ||
146 ranges[0]?.from !== 0 ||
147 ranges[0]?.to !== input.length
148 ) {
149 throw new InvalidRangeError();
150 }
151 }
152
153 /** Walk over the given node and its children, recursively creating Trees. */
154 private get_tree_for_ts_cursor(ts_cursor: TSTreeCursor): Tree {
155 const { nodeTypeId, startIndex, endIndex } = ts_cursor;
156 const node_type = this.node_types[nodeTypeId] ?? error;
157 const children: Tree[] = [];
158 const positions: number[] = [];
159
160 if (ts_cursor.gotoFirstChild()) {
161 do {
162 positions.push(ts_cursor.startIndex - startIndex);
163 children.push(this.get_tree_for_ts_cursor(ts_cursor));
164 } while (ts_cursor.gotoNextSibling());
165 ts_cursor.gotoParent();
166 }
167
168 return new Tree(node_type, children, positions, endIndex - startIndex);
169 }
170
171 /**
172 * Walk over the given node and its children, recursively creating Trees.
173 *
174 * Tries to reuse parts of an old tree.
175 */
176 private get_tree_for_ts_cursor_reuse(
177 ts_cursor: TSTreeCursor,
178 edit: TSEdit,
179 old_tree: Tree,
180 ): Tree {
181 const { nodeTypeId, startIndex, endIndex } = ts_cursor;
182 const node_type = this.node_types[nodeTypeId] ?? error;
183 const children: Tree[] = [];
184 const positions: number[] = [];
185
186 if (ts_cursor.gotoFirstChild()) {
187 let ended = false;
188 const old_children = old_tree.children;
189
190 // First, we add all children that end before the edit.
191 let child_index = 0;
192 while (!ended && ts_cursor.endIndex < edit.startIndex) {
193 positions.push(ts_cursor.startIndex - startIndex);
194 children.push(old_children[child_index] as Tree);
195 child_index += 1;
196 ended = !ts_cursor.gotoNextSibling();
197 }
198
199 // If there is a node that completely covers the edit, we want to pass
200 // the old tree for the node down so that parts can be reused.
201 if (
202 ts_cursor.startIndex < edit.startIndex &&
203 edit.newEndIndex < ts_cursor.endIndex
204 ) {
205 const old_child = old_children[child_index] as Tree | undefined;
206 if (old_child) {
207 positions.push(ts_cursor.startIndex - startIndex);
208 children.push(
209 this.get_tree_for_ts_cursor_reuse(ts_cursor, edit, old_child),
210 );
211 ended = !ts_cursor.gotoNextSibling();
212 }
213 }
214
215 // Now/alternatively, we add all children contained in/touching the edit.
216 while (!ended && ts_cursor.startIndex < edit.newEndIndex) {
217 positions.push(ts_cursor.startIndex - startIndex);
218 children.push(this.get_tree_for_ts_cursor(ts_cursor));
219 ended = !ts_cursor.gotoNextSibling();
220 }
221
222 // Finally, we add the children after the edit.
223 // We first count them and add their positions and push the trees after that.
224 let children_after_edit = 0;
225 while (!ended) {
226 positions.push(ts_cursor.startIndex - startIndex);
227 children_after_edit += 1;
228 ended = !ts_cursor.gotoNextSibling();
229 }
230 if (children_after_edit > 0) {
231 children.push(...(old_children.slice(-children_after_edit) as Tree[]));
232 }
233 ts_cursor.gotoParent();
234 }
235
236 return new Tree(node_type, children, positions, endIndex - startIndex);
237 }
238
239 /** Convert the tree-sitter Tree to a Lezer tree, possibly reusing parts of an old one. */
240 private convert_tree(
241 ts_tree: TSTree,
242 change: Pick<ChangeDetails, "edit" | "old_tree"> | null,
243 ): Tree {
244 const ts_tree_cursor = ts_tree.rootNode.walk();
245 const tree = change
246 ? this.get_tree_for_ts_cursor_reuse(
247 ts_tree_cursor,
248 change.edit,
249 change.old_tree,
250 )
251 : this.get_tree_for_ts_cursor(ts_tree_cursor);
252 const tree_with_ts_tree_prop = new Tree(
253 tree.type,
254 tree.children,
255 tree.positions,
256 tree.length,
257 [[TSTreeProp, ts_tree]],
258 );
259 return tree_with_ts_tree_prop;
260 }
261
262 /** Gather information about the changes from a previous parse. */
263 private static change_details(
264 fragments: readonly TreeFragment[],
265 input_length: number,
266 ): ChangeDetails | null {
267 if (!is_non_empty(fragments)) {
268 return null;
269 }
270 const edit = input_edit_for_fragments(fragments, input_length);
271 const old_tree = fragments[0].tree;
272 const edited_old_ts_tree = old_tree.prop(TSTreeProp)?.copy();
273
274 if (edit) {
275 if (!edited_old_ts_tree) {
276 log_error("expected old tree when there is an edit");
277 return null;
278 }
279 assert(
280 input_length - old_tree.length === edit.newEndIndex - edit.oldEndIndex,
281 "expect offset to match change in text length",
282 );
283 edited_old_ts_tree.edit(edit);
284 assert(
285 edited_old_ts_tree.rootNode.endIndex === input_length,
286 "expect edited old tree to match text length",
287 );
288 return { edit, old_tree, edited_old_ts_tree };
289 }
290
291 return null;
292 }
293
294 /**
295 * Extend the changed range using the TS getChangedRanges function.
296 *
297 * Outside this extended range, nodes from the old tree can be reused since they
298 * will have the exact same stack of containing nodes (possibly offset after the edit).
299 */
300 private static extend_change(
301 change: ChangeDetails,
302 ts_tree: TSTree,
303 ): Pick<ChangeDetails, "edit" | "old_tree"> | null {
304 const { edit, edited_old_ts_tree } = change;
305 const changed_ranges = edited_old_ts_tree.getChangedRanges(ts_tree);
306 if (!is_non_empty(changed_ranges)) {
307 return change;
308 }
309 const newEndIndex = Math.max(
310 edit.newEndIndex,
311 last_element(changed_ranges).endIndex,
312 );
313 const extended_edit = ts_edit(
314 Math.min(edit.startIndex, changed_ranges[0].startIndex),
315 newEndIndex + (edit.oldEndIndex - edit.newEndIndex),
316 newEndIndex,
317 );
318 return {
319 edit: extended_edit,
320 old_tree: change.old_tree,
321 };
322 }
323
324 advance(): Tree | null {
325 const { fragments, input, stoppedAt, ts_parser } = this;
326 const text = input.read(0, stoppedAt ?? input.length);
327 const input_length = text.length;
328
329 const cm_text = input instanceof DocInput ? input.doc : null;
330 if (cm_text) {
331 const cached = PARSE_CACHE.get(cm_text);
332 if (cached) {
333 return cached;
334 }
335 }
336
337 const change = Parse.change_details(fragments, input_length);
338 let ts_tree = ts_parser.parse(text, change?.edited_old_ts_tree);
339 if (ts_tree?.rootNode.endIndex !== input_length) {
340 log_error(
341 "Mismatch between tree (%s) and document (%s) lengths; reparsing",
342 ts_tree?.rootNode.endIndex,
343 input_length,
344 );
345 ts_tree = ts_parser.parse(text);
346 }
347 if (ts_tree == null) {
348 return null;
349 }
350 const extended_change = change
351 ? Parse.extend_change(change, ts_tree)
352 : null;
353
354 // Convert the Lezer tree to a tree-sitter tree.
355 const tree = this.convert_tree(ts_tree, extended_change);
356 this.parsedPos = input_length;
357 if (cm_text) {
358 PARSE_CACHE.set(cm_text, tree);
359 }
360
361 return tree;
362 }
363
364 stopAt(pos: number): void {
365 this.stoppedAt = pos;
366 }
367 }
368
369 /**
370 * A parser using a tree-sitter parser to create Lezer trees.
371 *
372 * @param ts_parser - The tree-sitter parser (with a language loaded) to use.
373 * @param props - Node props to assign to the node types.
374 * @param top_node - The name of the node type that is the top node in the TS grammar.
375 */
376 export class LezerTSParser extends Parser {
377 /** The Lezer NodeTypes - all node types from the TS grammar with props assigned. */
378 private node_types: NodeType[];
379
380 constructor(
381 readonly ts_parser: TSParser,
382 props: NodePropSource[],
383 top_node: string,
384 ) {
385 super();
386
387 const { language } = ts_parser;
388 if (language == null) {
389 throw new MissingLanguageError();
390 }
391 this.node_types = language.types.map((name, id) =>
392 NodeType.define({ id, name, props, top: name === top_node }),
393 );
394 }
395
396 createParse(
397 input: Input,
398 fragments: readonly TreeFragment[],
399 ranges: readonly { from: number; to: number }[],
400 ): PartialParse {
401 return new Parse(this.ts_parser, this.node_types, input, fragments, ranges);
402 }
403 }