Debian Codegraph @

lezer-lr/src/parse.ts

raw
1 import {DefaultBufferLength, Tree, TreeFragment, NodeSet, NodeType, NodeProp, NodePropSource,
2 Input, PartialParse, Parser, ParseWrapper, IterMode} from "@lezer/common"
3 import {Stack, StackBufferCursor, Lookahead} from "./stack"
4 import {Action, Specialize, Term, Seq, StateFlag, ParseState, File} from "./constants"
5 import {Tokenizer, TokenGroup, ExternalTokenizer, CachedToken, InputStream} from "./token"
6 import {decodeArray} from "./decode"
7
8 // Environment variable used to control console output
9 const verbose = typeof process != "undefined" && process.env && /\bparse\b/.test(process.env.LOG!)
10
11 let stackIDs: WeakMap<Stack, string> | null = null
12
13 function cutAt(tree: Tree, pos: number, side: 1 | -1) {
14 let cursor = tree.cursor(IterMode.IncludeAnonymous)
15 cursor.moveTo(pos)
16 for (;;) {
17 if (!(side < 0 ? cursor.childBefore(pos) : cursor.childAfter(pos))) for (;;) {
18 if ((side < 0 ? cursor.to < pos : cursor.from > pos) && !cursor.type.isError)
19 return side < 0 ? Math.max(0, Math.min(cursor.to - 1, pos - Lookahead.Margin))
20 : Math.min(tree.length, Math.max(cursor.from + 1, pos + Lookahead.Margin))
21 if (side < 0 ? cursor.prevSibling() : cursor.nextSibling()) break
22 if (!cursor.parent()) return side < 0 ? 0 : tree.length
23 }
24 }
25 }
26
27 class FragmentCursor {
28 i = 0
29 fragment: TreeFragment | null = null
30 safeFrom = -1
31 safeTo = -1
32 trees: Tree[] = []
33 start: number[] = []
34 index: number[] = []
35 nextStart!: number
36
37 constructor(readonly fragments: readonly TreeFragment[],
38 readonly nodeSet: NodeSet) {
39 this.nextFragment()
40 }
41
42 nextFragment() {
43 let fr = this.fragment = this.i == this.fragments.length ? null : this.fragments[this.i++]
44 if (fr) {
45 this.safeFrom = fr.openStart ? cutAt(fr.tree, fr.from + fr.offset, 1) - fr.offset : fr.from
46 this.safeTo = fr.openEnd ? cutAt(fr.tree, fr.to + fr.offset, -1) - fr.offset : fr.to
47 while (this.trees.length) { this.trees.pop(); this.start.pop(); this.index.pop() }
48 this.trees.push(fr.tree)
49 this.start.push(-fr.offset)
50 this.index.push(0)
51 this.nextStart = this.safeFrom
52 } else {
53 this.nextStart = 1e9
54 }
55 }
56
57 // `pos` must be >= any previously given `pos` for this cursor
58 nodeAt(pos: number): Tree | null {
59 if (pos < this.nextStart) return null
60 while (this.fragment && this.safeTo <= pos) this.nextFragment()
61 if (!this.fragment) return null
62
63 for (;;) {
64 let last = this.trees.length - 1
65 if (last < 0) { // End of tree
66 this.nextFragment()
67 return null
68 }
69 let top = this.trees[last], index = this.index[last]
70 if (index == top.children.length) {
71 this.trees.pop()
72 this.start.pop()
73 this.index.pop()
74 continue
75 }
76 let next = top.children[index]
77 let start = this.start[last] + top.positions[index]
78 if (start > pos) {
79 this.nextStart = start
80 return null
81 }
82 if (next instanceof Tree) {
83 if (start == pos) {
84 if (start < this.safeFrom) return null
85 let end = start + next.length
86 if (end <= this.safeTo) {
87 let lookAhead = next.prop(NodeProp.lookAhead)
88 if (!lookAhead || end + lookAhead < this.fragment.to) return next
89 }
90 }
91 this.index[last]++
92 if (start + next.length >= Math.max(this.safeFrom, pos)) { // Enter this node
93 this.trees.push(next)
94 this.start.push(start)
95 this.index.push(0)
96 }
97 } else {
98 this.index[last]++
99 this.nextStart = start + next.length
100 }
101 }
102 }
103 }
104
105 class TokenCache {
106 tokens: CachedToken[] = []
107 mainToken: CachedToken | null = null
108
109 actions: number[] = []
110
111 constructor(parser: LRParser, readonly stream: InputStream) {
112 this.tokens = parser.tokenizers.map(_ => new CachedToken)
113 }
114
115 getActions(stack: Stack) {
116 let actionIndex = 0
117 let main: CachedToken | null = null
118 let {parser} = stack.p, {tokenizers} = parser
119
120 let mask = parser.stateSlot(stack.state, ParseState.TokenizerMask)
121 let context = stack.curContext ? stack.curContext.hash : 0
122 let lookAhead = 0
123 for (let i = 0; i < tokenizers.length; i++) {
124 if (((1 << i) & mask) == 0) continue
125 let tokenizer = tokenizers[i], token = this.tokens[i]
126 if (main && !tokenizer.fallback) continue
127 if (tokenizer.contextual || token.start != stack.pos || token.mask != mask || token.context != context) {
128 this.updateCachedToken(token, tokenizer, stack)
129 token.mask = mask
130 token.context = context
131 }
132 if (token.lookAhead > token.end + Lookahead.Margin)
133 lookAhead = Math.max(token.lookAhead, lookAhead)
134
135 if (token.value != Term.Err) {
136 let startIndex = actionIndex
137 if (token.extended > -1) actionIndex = this.addActions(stack, token.extended, token.end, actionIndex)
138 actionIndex = this.addActions(stack, token.value, token.end, actionIndex)
139 if (!tokenizer.extend) {
140 main = token
141 if (actionIndex > startIndex) break
142 }
143 }
144 }
145
146 while (this.actions.length > actionIndex) this.actions.pop()
147 if (lookAhead) stack.setLookAhead(lookAhead)
148 if (!main && stack.pos == this.stream.end) {
149 main = new CachedToken
150 main.value = stack.p.parser.eofTerm
151 main.start = main.end = stack.pos
152 actionIndex = this.addActions(stack, main.value, main.end, actionIndex)
153 }
154 this.mainToken = main
155 return this.actions
156 }
157
158 getMainToken(stack: Stack) {
159 if (this.mainToken) return this.mainToken
160 let main = new CachedToken, {pos, p} = stack
161 main.start = pos
162 main.end = Math.min(pos + 1, p.stream.end)
163 main.value = pos == p.stream.end ? p.parser.eofTerm : Term.Err
164 return main
165 }
166
167 updateCachedToken(token: CachedToken, tokenizer: Tokenizer, stack: Stack) {
168 let start = this.stream.clipPos(stack.pos)
169 tokenizer.token(this.stream.reset(start, token), stack)
170 if (token.value > -1) {
171 let {parser} = stack.p
172
173 for (let i = 0; i < parser.specialized.length; i++) if (parser.specialized[i] == token.value) {
174 let result = parser.specializers[i](this.stream.read(token.start, token.end), stack)
175 if (result >= 0 && stack.p.parser.dialect.allows(result >> 1)) {
176 if ((result & 1) == Specialize.Specialize) token.value = result >> 1
177 else token.extended = result >> 1
178 break
179 }
180 }
181 } else {
182 token.value = Term.Err
183 token.end = this.stream.clipPos(start + 1)
184 }
185 }
186
187 putAction(action: number, token: number, end: number, index: number) {
188 // Don't add duplicate actions
189 for (let i = 0; i < index; i += 3) if (this.actions[i] == action) return index
190 this.actions[index++] = action
191 this.actions[index++] = token
192 this.actions[index++] = end
193 return index
194 }
195
196 addActions(stack: Stack, token: number, end: number, index: number) {
197 let {state} = stack, {parser} = stack.p, {data} = parser
198 for (let set = 0; set < 2; set++) {
199 for (let i = parser.stateSlot(state, set ? ParseState.Skip : ParseState.Actions);; i += 3) {
200 if (data[i] == Seq.End) {
201 if (data[i + 1] == Seq.Next) {
202 i = pair(data, i + 2)
203 } else {
204 if (index == 0 && data[i + 1] == Seq.Other)
205 index = this.putAction(pair(data, i + 2), token, end, index)
206 break
207 }
208 }
209 if (data[i] == token) index = this.putAction(pair(data, i + 1), token, end, index)
210 }
211 }
212 return index
213 }
214 }
215
216 const enum Rec {
217 Distance = 5,
218 MaxRemainingPerStep = 3,
219 // When two stacks have been running independently long enough to
220 // add this many elements to their buffers, prune one.
221 MinBufferLengthPrune = 500,
222 ForceReduceLimit = 10,
223 // Once a stack reaches this depth (in .stack.length) force-reduce
224 // it back to CutTo to avoid creating trees that overflow the stack
225 // on recursive traversal.
226 CutDepth = 2800 * 3,
227 CutTo = 2000 * 3,
228 MaxLeftAssociativeReductionCount = 300,
229 // The maximum number of non-recovering stacks to explore (to avoid
230 // getting bogged down with exponentially multiplying stacks in
231 // ambiguous content)
232 MaxStackCount = 12
233 }
234
235 export class Parse implements PartialParse {
236 // Active parse stacks.
237 stacks: Stack[]
238 recovering = 0
239 fragments: FragmentCursor | null
240 nextStackID = 0x2654 // ♔, ♕, ♖, ♗, ♘, ♙, ♠, ♡, ♢, ♣, ♤, ♥, ♦, ♧
241 minStackPos = 0
242
243 reused: Tree[] = []
244 stream: InputStream
245 tokens: TokenCache
246 topTerm: number
247 stoppedAt: null | number = null
248
249 lastBigReductionStart = -1
250 lastBigReductionSize = 0
251 bigReductionCount = 0
252
253 constructor(
254 readonly parser: LRParser,
255 readonly input: Input,
256 fragments: readonly TreeFragment[],
257 readonly ranges: readonly {from: number, to: number}[]
258 ) {
259 this.stream = new InputStream(input, ranges)
260 this.tokens = new TokenCache(parser, this.stream)
261 this.topTerm = parser.top[1]
262 let {from} = ranges[0]
263 this.stacks = [Stack.start(this, parser.top[0], from)]
264 this.fragments = fragments.length && this.stream.end - from > parser.bufferLength * 4
265 ? new FragmentCursor(fragments, parser.nodeSet) : null
266 }
267
268 get parsedPos() {
269 return this.minStackPos
270 }
271
272 // Move the parser forward. This will process all parse stacks at
273 // `this.pos` and try to advance them to a further position. If no
274 // stack for such a position is found, it'll start error-recovery.
275 //
276 // When the parse is finished, this will return a syntax tree. When
277 // not, it returns `null`.
278 advance() {
279 let stacks = this.stacks, pos = this.minStackPos
280 // This will hold stacks beyond `pos`.
281 let newStacks: Stack[] = this.stacks = []
282 let stopped: Stack[] | undefined, stoppedTokens: number[] | undefined
283
284 // If a large amount of reductions happened with the same start
285 // position, force the stack out of that production in order to
286 // avoid creating a tree too deep to recurse through.
287 // (This is an ugly kludge, because unfortunately there is no
288 // straightforward, cheap way to check for this happening, due to
289 // the history of reductions only being available in an
290 // expensive-to-access format in the stack buffers.)
291 if (this.bigReductionCount > Rec.MaxLeftAssociativeReductionCount && stacks.length == 1) {
292 let [s] = stacks
293 while (s.forceReduce() && s.stack.length && s.stack[s.stack.length - 2] >= this.lastBigReductionStart) {}
294 this.bigReductionCount = this.lastBigReductionSize = 0
295 }
296
297 // Keep advancing any stacks at `pos` until they either move
298 // forward or can't be advanced. Gather stacks that can't be
299 // advanced further in `stopped`.
300 for (let i = 0; i < stacks.length; i++) {
301 let stack = stacks[i]
302 for (;;) {
303 this.tokens.mainToken = null
304 if (stack.pos > pos) {
305 newStacks.push(stack)
306 } else if (this.advanceStack(stack, newStacks, stacks)) {
307 continue
308 } else {
309 if (!stopped) { stopped = []; stoppedTokens = [] }
310 stopped.push(stack)
311 let tok = this.tokens.getMainToken(stack)
312 stoppedTokens!.push(tok.value, tok.end)
313 }
314 break
315 }
316 }
317
318 if (!newStacks.length) {
319 let finished = stopped && findFinished(stopped)
320 if (finished) {
321 if (verbose) console.log("Finish with " + this.stackID(finished))
322 return this.stackToTree(finished)
323 }
324
325 if (this.parser.strict) {
326 if (verbose && stopped)
327 console.log("Stuck with token " + (this.tokens.mainToken ? this.parser.getName(this.tokens.mainToken.value) : "none"))
328 throw new SyntaxError("No parse at " + pos)
329 }
330 if (!this.recovering) this.recovering = Rec.Distance
331 }
332
333 if (this.recovering && stopped) {
334 let finished = this.stoppedAt != null && stopped[0].pos > this.stoppedAt ? stopped[0]
335 : this.runRecovery(stopped, stoppedTokens!, newStacks)
336 if (finished) {
337 if (verbose) console.log("Force-finish " + this.stackID(finished))
338 return this.stackToTree(finished.forceAll())
339 }
340 }
341
342 if (this.recovering) {
343 let maxRemaining = this.recovering == 1 ? 1 : this.recovering * Rec.MaxRemainingPerStep
344 if (newStacks.length > maxRemaining) {
345 newStacks.sort((a, b) => b.score - a.score)
346 while (newStacks.length > maxRemaining) newStacks.pop()
347 }
348 if (newStacks.some(s => s.reducePos > pos)) this.recovering--
349 } else if (newStacks.length > 1) {
350 // Prune stacks that are in the same state, or that have been
351 // running without splitting for a while, to avoid getting stuck
352 // with multiple successful stacks running endlessly on.
353 outer: for (let i = 0; i < newStacks.length - 1; i++) {
354 let stack = newStacks[i]
355 for (let j = i + 1; j < newStacks.length; j++) {
356 let other = newStacks[j]
357 if (stack.sameState(other) ||
358 stack.buffer.length > Rec.MinBufferLengthPrune && other.buffer.length > Rec.MinBufferLengthPrune) {
359 if (((stack.score - other.score) || (stack.buffer.length - other.buffer.length)) > 0) {
360 newStacks.splice(j--, 1)
361 } else {
362 newStacks.splice(i--, 1)
363 continue outer
364 }
365 }
366 }
367 }
368 if (newStacks.length > Rec.MaxStackCount)
369 newStacks.splice(Rec.MaxStackCount, newStacks.length - Rec.MaxStackCount)
370 }
371
372 this.minStackPos = newStacks[0].pos
373 for (let i = 1; i < newStacks.length; i++) if (newStacks[i].pos < this.minStackPos) this.minStackPos = newStacks[i].pos
374 return null
375 }
376
377 stopAt(pos: number) {
378 if (this.stoppedAt != null && this.stoppedAt < pos) throw new RangeError("Can't move stoppedAt forward")
379 this.stoppedAt = pos
380 }
381
382 // Returns an updated version of the given stack, or null if the
383 // stack can't advance normally. When `split` and `stacks` are
384 // given, stacks split off by ambiguous operations will be pushed to
385 // `split`, or added to `stacks` if they move `pos` forward.
386 private advanceStack(stack: Stack, stacks: null | Stack[], split: null | Stack[]) {
387 let start = stack.pos, {parser} = this
388 let base = verbose ? this.stackID(stack) + " -> " : ""
389
390 if (this.stoppedAt != null && start > this.stoppedAt)
391 return stack.forceReduce() ? stack : null
392
393 if (this.fragments) {
394 let strictCx = stack.curContext && stack.curContext.tracker.strict, cxHash = strictCx ? stack.curContext!.hash : 0
395 for (let cached = this.fragments.nodeAt(start); cached;) {
396 let match = this.parser.nodeSet.types[cached.type.id] == cached.type ? parser.getGoto(stack.state, cached.type.id) : -1
397 if (match > -1 && cached.length && (!strictCx || (cached.prop(NodeProp.contextHash) || 0) == cxHash)) {
398 stack.useNode(cached, match)
399 if (verbose) console.log(base + this.stackID(stack) + ` (via reuse of ${parser.getName(cached.type.id)})`)
400 return true
401 }
402 if (!(cached instanceof Tree) || cached.children.length == 0 || cached.positions[0] > 0) break
403 let inner = cached.children[0]
404 if (inner instanceof Tree && cached.positions[0] == 0) cached = inner
405 else break
406 }
407 }
408
409 let defaultReduce = parser.stateSlot(stack.state, ParseState.DefaultReduce)
410 if (defaultReduce > 0) {
411 stack.reduce(defaultReduce)
412 if (verbose)
413 console.log(base + this.stackID(stack) + ` (via always-reduce ${parser.getName(defaultReduce & Action.ValueMask)})`)
414 return true
415 }
416
417 if (stack.stack.length >= Rec.CutDepth) {
418 while (stack.stack.length > Rec.CutTo && stack.forceReduce()) {}
419 }
420
421 let actions = this.tokens.getActions(stack)
422 for (let i = 0; i < actions.length;) {
423 let action = actions[i++], term = actions[i++], end = actions[i++]
424 let last = i == actions.length || !split
425 let localStack = last ? stack : stack.split()
426 let main = this.tokens.mainToken
427 localStack.apply(action, term, main ? main.start : localStack.pos, end)
428 if (verbose)
429 console.log(base + this.stackID(localStack) + ` (via ${(action & Action.ReduceFlag) == 0 ? "shift"
430 : `reduce of ${parser.getName(action & Action.ValueMask)}`} for ${
431 parser.getName(term)} @ ${start}${localStack == stack ? "" : ", split"})`)
432 if (last) return true
433 else if (localStack.pos > start) stacks!.push(localStack)
434 else split!.push(localStack)
435 }
436
437 return false
438 }
439
440 // Advance a given stack forward as far as it will go. Returns the
441 // (possibly updated) stack if it got stuck, or null if it moved
442 // forward and was given to `pushStackDedup`.
443 private advanceFully(stack: Stack, newStacks: Stack[]) {
444 let pos = stack.pos
445 for (;;) {
446 if (!this.advanceStack(stack, null, null)) return false
447 if (stack.pos > pos) {
448 pushStackDedup(stack, newStacks)
449 return true
450 }
451 }
452 }
453
454 private runRecovery(stacks: Stack[], tokens: number[], newStacks: Stack[]) {
455 let finished: Stack | null = null, restarted = false
456 for (let i = 0; i < stacks.length; i++) {
457 let stack = stacks[i], token = tokens[i << 1], tokenEnd = tokens[(i << 1) + 1]
458 let base = verbose ? this.stackID(stack) + " -> " : ""
459
460 if (stack.deadEnd) {
461 if (restarted) continue
462 restarted = true
463 stack.restart()
464 if (verbose) console.log(base + this.stackID(stack) + " (restarted)")
465 let done = this.advanceFully(stack, newStacks)
466 if (done) continue
467 }
468
469 let force = stack.split(), forceBase = base
470 for (let j = 0; force.forceReduce() && j < Rec.ForceReduceLimit; j++) {
471 if (verbose) console.log(forceBase + this.stackID(force) + " (via force-reduce)")
472 let done = this.advanceFully(force, newStacks)
473 if (done) break
474 if (verbose) forceBase = this.stackID(force) + " -> "
475 }
476
477 for (let insert of stack.recoverByInsert(token)) {
478 if (verbose) console.log(base + this.stackID(insert) + " (via recover-insert)")
479 this.advanceFully(insert, newStacks)
480 }
481
482 if (this.stream.end > stack.pos) {
483 if (tokenEnd == stack.pos) {
484 tokenEnd++
485 token = Term.Err
486 }
487 stack.recoverByDelete(token, tokenEnd)
488 if (verbose) console.log(base + this.stackID(stack) + ` (via recover-delete ${this.parser.getName(token)})`)
489 pushStackDedup(stack, newStacks)
490 } else if (!finished || finished.score < stack.score) {
491 finished = stack
492 }
493 }
494
495 return finished
496 }
497
498 // Convert the stack's buffer to a syntax tree.
499 stackToTree(stack: Stack): Tree {
500 stack.close()
501 return Tree.build({buffer: StackBufferCursor.create(stack),
502 nodeSet: this.parser.nodeSet,
503 topID: this.topTerm,
504 maxBufferLength: this.parser.bufferLength,
505 reused: this.reused,
506 start: this.ranges[0].from,
507 length: stack.pos - this.ranges[0].from,
508 minRepeatType: this.parser.minRepeatTerm})
509 }
510
511 private stackID(stack: Stack) {
512 let id = (stackIDs || (stackIDs = new WeakMap)).get(stack)
513 if (!id) stackIDs.set(stack, id = String.fromCodePoint(this.nextStackID++))
514 return id + stack
515 }
516 }
517
518 function pushStackDedup(stack: Stack, newStacks: Stack[]) {
519 for (let i = 0; i < newStacks.length; i++) {
520 let other = newStacks[i]
521 if (other.pos == stack.pos && other.sameState(stack)) {
522 if (newStacks[i].score < stack.score) newStacks[i] = stack
523 return
524 }
525 }
526 newStacks.push(stack)
527 }
528
529 export class Dialect {
530 constructor(readonly source: string | undefined,
531 readonly flags: readonly boolean[],
532 readonly disabled: null | Uint8Array) {}
533
534 allows(term: number) { return !this.disabled || this.disabled[term] == 0 }
535 }
536
537 const id: <T>(x: T) => T = x => x
538
539 /// Context trackers are used to track stateful context (such as
540 /// indentation in the Python grammar, or parent elements in the XML
541 /// grammar) needed by external tokenizers. You declare them in a
542 /// grammar file as `@context exportName from "module"`.
543 ///
544 /// Context values should be immutable, and can be updated (replaced)
545 /// on shift or reduce actions.
546 ///
547 /// The export used in a `@context` declaration should be of this
548 /// type.
549 export class ContextTracker<T> {
550 /// @internal
551 start: T
552 /// @internal
553 shift: (context: T, term: number, stack: Stack, input: InputStream) => T
554 /// @internal
555 reduce: (context: T, term: number, stack: Stack, input: InputStream) => T
556 /// @internal
557 reuse: (context: T, node: Tree, stack: Stack, input: InputStream) => T
558 /// @internal
559 hash: (context: T) => number
560 /// @internal
561 strict: boolean
562
563 /// Define a context tracker.
564 constructor(spec: {
565 /// The initial value of the context at the start of the parse.
566 start: T,
567 /// Update the context when the parser executes a
568 /// [shift](https://en.wikipedia.org/wiki/LR_parser#Shift_and_reduce_actions)
569 /// action.
570 shift?(context: T, term: number, stack: Stack, input: InputStream): T
571 /// Update the context when the parser executes a reduce action.
572 reduce?(context: T, term: number, stack: Stack, input: InputStream): T
573 /// Update the context when the parser reuses a node from a tree
574 /// fragment.
575 reuse?(context: T, node: Tree, stack: Stack, input: InputStream): T
576 /// Reduce a context value to a number (for cheap storage and
577 /// comparison). Only needed for strict contexts.
578 hash?(context: T): number
579 /// By default, nodes can only be reused during incremental
580 /// parsing if they were created in the same context as the one in
581 /// which they are reused. Set this to false to disable that
582 /// check (and the overhead of storing the hashes).
583 strict?: boolean
584 }) {
585 this.start = spec.start
586 this.shift = spec.shift || id
587 this.reduce = spec.reduce || id
588 this.reuse = spec.reuse || id
589 this.hash = spec.hash || (() => 0)
590 this.strict = spec.strict !== false
591 }
592 }
593
594 type SpecializerSpec = {
595 term: number,
596 get?: (value: string, stack: Stack) => number,
597 external?: any,
598 extend?: boolean
599 }
600
601 type ParserSpec = {
602 version: number,
603 states: string | Uint32Array,
604 stateData: string | Uint16Array,
605 goto: string | Uint16Array,
606 nodeNames: string,
607 maxTerm: number,
608 repeatNodeCount: number,
609 nodeProps?: [NodeProp<any> | string, ...(string | number)[]][],
610 propSources?: NodePropSource[],
611 skippedNodes?: number[],
612 tokenData: string,
613 tokenizers: (Tokenizer | number)[],
614 topRules: {[name: string]: [number, number]},
615 context: ContextTracker<any> | null,
616 dialects?: {[name: string]: number},
617 dynamicPrecedences?: {[term: number]: number},
618 specialized?: SpecializerSpec[],
619 tokenPrec: number,
620 termNames?: {[id: number]: string}
621 }
622
623 /// Configuration options when
624 /// [reconfiguring](#lr.LRParser.configure) a parser.
625 export interface ParserConfig {
626 /// Node prop values to add to the parser's node set.
627 props?: readonly NodePropSource[]
628 /// The name of the `@top` declaration to parse from. If not
629 /// specified, the first top rule declaration in the grammar is
630 /// used.
631 top?: string
632 /// A space-separated string of dialects to enable.
633 dialect?: string
634 /// Replace the given external tokenizers with new ones.
635 tokenizers?: {from: ExternalTokenizer, to: ExternalTokenizer}[]
636 /// Replace external specializers with new ones.
637 specializers?: {from: (value: string, stack: Stack) => number, to: (value: string, stack: Stack) => number}[],
638 /// Replace the context tracker with a new one.
639 contextTracker?: ContextTracker<any>,
640 /// When true, the parser will raise an exception, rather than run
641 /// its error-recovery strategies, when the input doesn't match the
642 /// grammar.
643 strict?: boolean
644 /// Add a wrapper, which can extend parses created by this parser
645 /// with additional logic (usually used to add
646 /// [mixed-language](#common.parseMixed) parsing).
647 wrap?: ParseWrapper
648 /// The maximum length of the TreeBuffers generated in the output
649 /// tree. Defaults to 1024.
650 bufferLength?: number
651 }
652
653 /// Holds the parse tables for a given grammar, as generated by
654 /// `lezer-generator`, and provides [methods](#common.Parser) to parse
655 /// content with.
656 export class LRParser extends Parser {
657 /// The parse states for this grammar @internal
658 readonly states: Readonly<Uint32Array>
659 /// A blob of data that the parse states, as well as some
660 /// of `LRParser`'s fields, point into @internal
661 readonly data: Readonly<Uint16Array>
662 /// The goto table. See `computeGotoTable` in
663 /// lezer-generator for details on the format @internal
664 readonly goto: Readonly<Uint16Array>
665 /// The highest term id @internal
666 readonly maxTerm: number
667 /// The first repeat-related term id @internal
668 readonly minRepeatTerm: number
669 /// The tokenizer objects used by the grammar @internal
670 readonly tokenizers: readonly Tokenizer[]
671 /// Maps top rule names to [state ID, top term ID] pairs. @internal
672 readonly topRules: {[name: string]: [number, number]}
673 /// @internal
674 readonly context: ContextTracker<unknown> | null
675 /// A mapping from dialect names to the tokens that are exclusive
676 /// to them. @internal
677 readonly dialects: {[name: string]: number}
678 /// Null if there are no dynamic precedences, a map from term ids
679 /// to precedence otherwise. @internal
680 readonly dynamicPrecedences: {[term: number]: number} | null
681 /// The token types have specializers (in this.specializers) @internal
682 readonly specialized: Uint16Array
683 /// The specializer functions for the token types in specialized @internal
684 readonly specializers: ((value: string, stack: Stack) => number)[]
685 /// FIXME @internal
686 readonly specializerSpecs: SpecializerSpec[]
687 /// Points into this.data at an array that holds the
688 /// precedence order (higher precedence first) for ambiguous
689 /// tokens @internal
690 readonly tokenPrecTable: number
691 /// An optional object mapping term ids to name strings @internal
692 readonly termNames: null | {[id: number]: string}
693 /// @internal
694 readonly maxNode: number
695 /// @internal
696 readonly dialect: Dialect
697 /// @internal
698 readonly wrappers: readonly ParseWrapper[] = []
699 /// @internal
700 readonly top: [number, number]
701 /// @internal
702 readonly bufferLength: number
703 /// @internal
704 readonly strict: boolean
705 /// The nodes used in the trees emitted by this parser.
706 readonly nodeSet: NodeSet
707
708 /// @internal
709 constructor(spec: ParserSpec) {
710 super()
711 if (spec.version != File.Version)
712 throw new RangeError(`Parser version (${spec.version}) doesn't match runtime version (${File.Version})`)
713 let nodeNames = spec.nodeNames.split(" ")
714 this.minRepeatTerm = nodeNames.length
715 for (let i = 0; i < spec.repeatNodeCount; i++) nodeNames.push("")
716 let topTerms = Object.keys(spec.topRules).map(r => spec.topRules[r][1])
717 let nodeProps: [NodeProp<any>, any][][] = []
718 for (let i = 0; i < nodeNames.length; i++) nodeProps.push([])
719 function setProp(nodeID: number, prop: NodeProp<any>, value: any) {
720 nodeProps[nodeID].push([prop, prop.deserialize(String(value))])
721 }
722 if (spec.nodeProps) for (let propSpec of spec.nodeProps) {
723 let prop = propSpec[0]
724 if (typeof prop == "string") prop = (NodeProp as unknown as {[name: string]: NodeProp<any>})[prop]
725 for (let i = 1; i < propSpec.length;) {
726 let next = propSpec[i++] as number
727 if (next >= 0) {
728 setProp(next as number, prop, propSpec[i++] as string)
729 } else {
730 let value = propSpec[i + -next] as string
731 for (let j = -next; j > 0; j--) setProp(propSpec[i++] as number, prop, value)
732 i++
733 }
734 }
735 }
736 this.nodeSet = new NodeSet(nodeNames.map((name, i) => NodeType.define({
737 name: i >= this.minRepeatTerm ? undefined: name,
738 id: i,
739 props: nodeProps[i],
740 top: topTerms.indexOf(i) > -1,
741 error: i == 0,
742 skipped: spec.skippedNodes && spec.skippedNodes.indexOf(i) > -1
743 })))
744 if (spec.propSources) this.nodeSet = this.nodeSet.extend(...spec.propSources)
745 this.strict = false
746 this.bufferLength = DefaultBufferLength
747
748 let tokenArray = decodeArray<Uint16Array>(spec.tokenData)
749 this.context = spec.context
750 this.specializerSpecs = spec.specialized || []
751 this.specialized = new Uint16Array(this.specializerSpecs.length)
752 for (let i = 0; i < this.specializerSpecs.length; i++) this.specialized[i] = this.specializerSpecs[i].term
753 this.specializers = this.specializerSpecs.map(getSpecializer)
754
755 this.states = decodeArray(spec.states, Uint32Array)
756 this.data = decodeArray(spec.stateData)
757 this.goto = decodeArray(spec.goto)
758 this.maxTerm = spec.maxTerm
759 this.tokenizers = spec.tokenizers.map(value => typeof value == "number" ? new TokenGroup(tokenArray, value) : value)
760 this.topRules = spec.topRules
761 this.dialects = spec.dialects || {}
762 this.dynamicPrecedences = spec.dynamicPrecedences || null
763 this.tokenPrecTable = spec.tokenPrec
764 this.termNames = spec.termNames || null
765 this.maxNode = this.nodeSet.types.length - 1
766
767 this.dialect = this.parseDialect()
768 this.top = this.topRules[Object.keys(this.topRules)[0]]
769 }
770
771 createParse(input: Input, fragments: readonly TreeFragment[], ranges: readonly {from: number, to: number}[]): PartialParse {
772 let parse: PartialParse = new Parse(this, input, fragments, ranges)
773 for (let w of this.wrappers) parse = w(parse, input, fragments, ranges)
774 return parse
775 }
776
777 /// Get a goto table entry @internal
778 getGoto(state: number, term: number, loose = false) {
779 let table = this.goto
780 if (term >= table[0]) return -1
781 for (let pos = table[term + 1];;) {
782 let groupTag = table[pos++], last = groupTag & 1
783 let target = table[pos++]
784 if (last && loose) return target
785 for (let end = pos + (groupTag >> 1); pos < end; pos++)
786 if (table[pos] == state) return target
787 if (last) return -1
788 }
789 }
790
791 /// Check if this state has an action for a given terminal @internal
792 hasAction(state: number, terminal: number) {
793 let data = this.data
794 for (let set = 0; set < 2; set++) {
795 for (let i = this.stateSlot(state, set ? ParseState.Skip : ParseState.Actions), next;; i += 3) {
796 if ((next = data[i]) == Seq.End) {
797 if (data[i + 1] == Seq.Next) next = data[i = pair(data, i + 2)]
798 else if (data[i + 1] == Seq.Other) return pair(data, i + 2)
799 else break
800 }
801 if (next == terminal || next == Term.Err) return pair(data, i + 1)
802 }
803 }
804 return 0
805 }
806
807 /// @internal
808 stateSlot(state: number, slot: number) {
809 return this.states[(state * ParseState.Size) + slot]
810 }
811
812 /// @internal
813 stateFlag(state: number, flag: number) {
814 return (this.stateSlot(state, ParseState.Flags) & flag) > 0
815 }
816
817 /// @internal
818 validAction(state: number, action: number) {
819 return !!this.allActions(state, a => a == action ? true : null)
820 }
821
822 /// @internal
823 allActions<T>(state: number, action: (action: number) => void | T): void | T {
824 let deflt = this.stateSlot(state, ParseState.DefaultReduce)
825 let result: void | T = deflt ? action(deflt) : undefined
826 for (let i = this.stateSlot(state, ParseState.Actions); result == null; i += 3) {
827 if (this.data[i] == Seq.End) {
828 if (this.data[i + 1] == Seq.Next) i = pair(this.data, i + 2)
829 else break
830 }
831 result = action(pair(this.data, i + 1))
832 }
833 return result
834 }
835
836 /// Get the states that can follow this one through shift actions or
837 /// goto jumps. @internal
838 nextStates(state: number): readonly number[] {
839 let result: number[] = []
840 for (let i = this.stateSlot(state, ParseState.Actions);; i += 3) {
841 if (this.data[i] == Seq.End) {
842 if (this.data[i + 1] == Seq.Next) i = pair(this.data, i + 2)
843 else break
844 }
845 if ((this.data[i + 2] & (Action.ReduceFlag >> 16)) == 0) {
846 let value = this.data[i + 1]
847 if (!result.some((v, i) => (i & 1) && v == value)) result.push(this.data[i], value)
848 }
849 }
850 return result
851 }
852
853 /// Configure the parser. Returns a new parser instance that has the
854 /// given settings modified. Settings not provided in `config` are
855 /// kept from the original parser.
856 configure(config: ParserConfig) {
857 // Hideous reflection-based kludge to make it easy to create a
858 // slightly modified copy of a parser.
859 let copy = Object.assign(Object.create(LRParser.prototype), this)
860 if (config.props)
861 copy.nodeSet = this.nodeSet.extend(...config.props)
862 if (config.top) {
863 let info = this.topRules[config.top!]
864 if (!info) throw new RangeError(`Invalid top rule name ${config.top}`)
865 copy.top = info
866 }
867 if (config.tokenizers)
868 copy.tokenizers = this.tokenizers.map(t => {
869 let found = config.tokenizers!.find(r => r.from == t)
870 return found ? found.to : t
871 })
872 if (config.specializers) {
873 copy.specializers = this.specializers.slice()
874 copy.specializerSpecs = this.specializerSpecs.map((s, i) => {
875 let found = config.specializers!.find(r => r.from == s.external)
876 if (!found) return s
877 let spec = {...s, external: found.to}
878 copy.specializers[i] = getSpecializer(spec)
879 return spec
880 })
881 }
882 if (config.contextTracker)
883 copy.context = config.contextTracker
884 if (config.dialect)
885 copy.dialect = this.parseDialect(config.dialect)
886 if (config.strict != null)
887 copy.strict = config.strict
888 if (config.wrap)
889 copy.wrappers = copy.wrappers.concat(config.wrap)
890 if (config.bufferLength != null)
891 copy.bufferLength = config.bufferLength
892 return copy as LRParser
893 }
894
895 /// Tells you whether any [parse wrappers](#lr.ParserConfig.wrap)
896 /// are registered for this parser.
897 hasWrappers() {
898 return this.wrappers.length > 0
899 }
900
901 /// Returns the name associated with a given term. This will only
902 /// work for all terms when the parser was generated with the
903 /// `--names` option. By default, only the names of tagged terms are
904 /// stored.
905 getName(term: number): string {
906 return this.termNames ? this.termNames[term] : String(term <= this.maxNode && this.nodeSet.types[term].name || term)
907 }
908
909 /// The eof term id is always allocated directly after the node
910 /// types. @internal
911 get eofTerm() { return this.maxNode + 1 }
912
913 /// The type of top node produced by the parser.
914 get topNode() { return this.nodeSet.types[this.top[1]] }
915
916 /// @internal
917 dynamicPrecedence(term: number) {
918 let prec = this.dynamicPrecedences
919 return prec == null ? 0 : prec[term] || 0
920 }
921
922 /// @internal
923 parseDialect(dialect?: string) {
924 let values = Object.keys(this.dialects), flags = values.map(() => false)
925 if (dialect) for (let part of dialect.split(" ")) {
926 let id = values.indexOf(part)
927 if (id >= 0) flags[id] = true
928 }
929 let disabled: Uint8Array | null = null
930 for (let i = 0; i < values.length; i++) if (!flags[i]) {
931 for (let j = this.dialects[values[i]], id; (id = this.data[j++]) != Seq.End;)
932 (disabled || (disabled = new Uint8Array(this.maxTerm + 1)))[id] = 1
933 }
934 return new Dialect(dialect, flags, disabled)
935 }
936
937 /// Used by the output of the parser generator. Not available to
938 /// user code. @hide
939 static deserialize(spec: any): LRParser {
940 return new LRParser(spec as ParserSpec)
941 }
942 }
943
944 function pair(data: Readonly<Uint16Array>, off: number) { return data[off] | (data[off + 1] << 16) }
945
946 function findFinished(stacks: Stack[]) {
947 let best: Stack | null = null
948 for (let stack of stacks) {
949 let stopped = stack.p.stoppedAt
950 if ((stack.pos == stack.p.stream.end || stopped != null && stack.pos > stopped) &&
951 stack.p.parser.stateFlag(stack.state, StateFlag.Accepting) &&
952 (!best || best.score < stack.score))
953 best = stack
954 }
955 return best
956 }
957
958 function getSpecializer(spec: SpecializerSpec) {
959 if (spec.external) {
960 let mask = spec.extend ? Specialize.Extend : Specialize.Specialize
961 return (value: string, stack: Stack) => (spec.external!(value, stack) << 1) | mask
962 }
963 return spec.get!
964 }