| 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 |
} |