Debian Codegraph @

lezer-lr/src/stack.ts

raw
1 import {Action, Term, StateFlag, ParseState, Seq} from "./constants"
2 import {Parse, ContextTracker} from "./parse"
3 import {Tree, BufferCursor} from "@lezer/common"
4
5 export const enum Lookahead {
6 // Every token is assumed to have looked this far ahead, so that
7 // small lookahead values don't have to be separately stored.
8 // Lookaheads further than this are attached to the tree with props.
9 Margin = 25
10 }
11
12 /// A parse stack. These are used internally by the parser to track
13 /// parsing progress. They also provide some properties and methods
14 /// that external code such as a tokenizer can use to get information
15 /// about the parse state.
16 export class Stack {
17 /// @internal
18 constructor(
19 /// The parse that this stack is part of @internal
20 readonly p: Parse,
21 /// Holds state, input pos, buffer index triplets for all but the
22 /// top state @internal
23 readonly stack: number[],
24 /// The current parse state @internal
25 public state: number,
26 // The position at which the next reduce should take place. This
27 // can be less than `this.pos` when skipped expressions have been
28 // added to the stack (which should be moved outside of the next
29 // reduction)
30 /// @internal
31 public reducePos: number,
32 /// The input position up to which this stack has parsed.
33 public pos: number,
34 /// The dynamic score of the stack, including dynamic precedence
35 /// and error-recovery penalties
36 /// @internal
37 public score: number,
38 // The output buffer. Holds (type, start, end, size) quads
39 // representing nodes created by the parser, where `size` is
40 // amount of buffer array entries covered by this node.
41 /// @internal
42 public buffer: number[],
43 // The base offset of the buffer. When stacks are split, the split
44 // instance shared the buffer history with its parent up to
45 // `bufferBase`, which is the absolute offset (including the
46 // offset of previous splits) into the buffer at which this stack
47 // starts writing.
48 /// @internal
49 public bufferBase: number,
50 /// @internal
51 public curContext: StackContext | null,
52 /// @internal
53 public lookAhead = 0,
54 // A parent stack from which this was split off, if any. This is
55 // set up so that it always points to a stack that has some
56 // additional buffer content, never to a stack with an equal
57 // `bufferBase`.
58 /// @internal
59 public parent: Stack | null
60 ) {}
61
62 /// @internal
63 toString() {
64 return `[${this.stack.filter((_, i) => i % 3 == 0).concat(this.state)}]@${this.pos}${this.score ? "!" + this.score : ""}`
65 }
66
67 // Start an empty stack
68 /// @internal
69 static start(p: Parse, state: number, pos = 0) {
70 let cx = p.parser.context
71 return new Stack(p, [], state, pos, pos, 0, [], 0, cx ? new StackContext(cx, cx.start) : null, 0, null)
72 }
73
74 /// The stack's current [context](#lr.ContextTracker) value, if
75 /// any. Its type will depend on the context tracker's type
76 /// parameter, or it will be `null` if there is no context
77 /// tracker.
78 get context() { return this.curContext ? this.curContext.context : null }
79
80 // Push a state onto the stack, tracking its start position as well
81 // as the buffer base at that point.
82 /// @internal
83 pushState(state: number, start: number) {
84 this.stack.push(this.state, start, this.bufferBase + this.buffer.length)
85 this.state = state
86 }
87
88 // Apply a reduce action
89 /// @internal
90 reduce(action: number) {
91 let depth = action >> Action.ReduceDepthShift, type = action & Action.ValueMask
92 let {parser} = this.p
93
94 let lookaheadRecord = this.reducePos < this.pos - Lookahead.Margin
95 if (lookaheadRecord) this.setLookAhead(this.pos)
96
97 let dPrec = parser.dynamicPrecedence(type)
98 if (dPrec) this.score += dPrec
99
100 if (depth == 0) {
101 this.pushState(parser.getGoto(this.state, type, true), this.reducePos)
102 // Zero-depth reductions are a special case—they add stuff to
103 // the stack without popping anything off.
104 if (type < parser.minRepeatTerm) this.storeNode(type, this.reducePos, this.reducePos, lookaheadRecord ? 8 : 4, true)
105 this.reduceContext(type, this.reducePos)
106 return
107 }
108
109 // Find the base index into `this.stack`, content after which will
110 // be dropped. Note that with `StayFlag` reductions we need to
111 // consume two extra frames (the dummy parent node for the skipped
112 // expression and the state that we'll be staying in, which should
113 // be moved to `this.state`).
114 let base = this.stack.length - ((depth - 1) * 3) - (action & Action.StayFlag ? 6 : 0)
115 let start = base ? this.stack[base - 2] : this.p.ranges[0].from, size = this.reducePos - start
116
117 // This is a kludge to try and detect overly deep left-associative
118 // trees, which will not increase the parse stack depth and thus
119 // won't be caught by the regular stack-depth limit check.
120 if (size >= Recover.MinBigReduction && !this.p.parser.nodeSet.types[type]?.isAnonymous) {
121 if (start == this.p.lastBigReductionStart) {
122 this.p.bigReductionCount++
123 this.p.lastBigReductionSize = size
124 } else if (this.p.lastBigReductionSize < size) {
125 this.p.bigReductionCount = 1
126 this.p.lastBigReductionStart = start
127 this.p.lastBigReductionSize = size
128 }
129 }
130
131 let bufferBase = base ? this.stack[base - 1] : 0, count = this.bufferBase + this.buffer.length - bufferBase
132
133 // Store normal terms or `R -> R R` repeat reductions
134 if (type < parser.minRepeatTerm || (action & Action.RepeatFlag)) {
135 let pos = parser.stateFlag(this.state, StateFlag.Skipped) ? this.pos : this.reducePos
136 this.storeNode(type, start, pos, count + 4, true)
137 }
138 if (action & Action.StayFlag) {
139 this.state = this.stack[base]
140 } else {
141 let baseStateID = this.stack[base - 3]
142 this.state = parser.getGoto(baseStateID, type, true)
143 }
144 while (this.stack.length > base) this.stack.pop()
145 this.reduceContext(type, start)
146 }
147
148 // Shift a value into the buffer
149 /// @internal
150 storeNode(term: number, start: number, end: number, size = 4, mustSink = false) {
151 if (term == Term.Err &&
152 (!this.stack.length || this.stack[this.stack.length - 1] < this.buffer.length + this.bufferBase)) {
153 // Try to omit/merge adjacent error nodes
154 let cur: Stack | null = this, top = this.buffer.length
155 if (top == 0 && cur.parent) {
156 top = cur.bufferBase - cur.parent.bufferBase
157 cur = cur.parent
158 }
159 if (top > 0 && cur.buffer[top - 4] == Term.Err && cur.buffer[top - 1] > -1) {
160 if (start == end) return
161 if (cur.buffer[top - 2] >= start) { cur.buffer[top - 2] = end; return }
162 }
163 }
164
165 if (!mustSink || this.pos == end) { // Simple case, just append
166 this.buffer.push(term, start, end, size)
167 } else { // There may be skipped nodes that have to be moved forward
168 let index = this.buffer.length
169 if (index > 0 && this.buffer[index - 4] != Term.Err) {
170 let mustMove = false
171 for (let scan = index; scan > 0 && this.buffer[scan - 2] > end; scan -= 4) {
172 if (this.buffer[scan - 1] >= 0) { mustMove = true; break }
173 }
174 if (mustMove) while (index > 0 && this.buffer[index - 2] > end) {
175 // Move this record forward
176 this.buffer[index] = this.buffer[index - 4]
177 this.buffer[index + 1] = this.buffer[index - 3]
178 this.buffer[index + 2] = this.buffer[index - 2]
179 this.buffer[index + 3] = this.buffer[index - 1]
180 index -= 4
181 if (size > 4) size -= 4
182 }
183 }
184 this.buffer[index] = term
185 this.buffer[index + 1] = start
186 this.buffer[index + 2] = end
187 this.buffer[index + 3] = size
188 }
189 }
190
191 // Apply a shift action
192 /// @internal
193 shift(action: number, type: number, start: number, end: number) {
194 if (action & Action.GotoFlag) {
195 this.pushState(action & Action.ValueMask, this.pos)
196 } else if ((action & Action.StayFlag) == 0) { // Regular shift
197 let nextState = action, {parser} = this.p
198 if (end > this.pos || type <= parser.maxNode) {
199 this.pos = end
200 if (!parser.stateFlag(nextState, StateFlag.Skipped)) this.reducePos = end
201 }
202 this.pushState(nextState, start)
203 this.shiftContext(type, start)
204 if (type <= parser.maxNode)
205 this.buffer.push(type, start, end, 4)
206 } else { // Shift-and-stay, which means this is a skipped token
207 this.pos = end
208 this.shiftContext(type, start)
209 if (type <= this.p.parser.maxNode)
210 this.buffer.push(type, start, end, 4)
211 }
212 }
213
214 // Apply an action
215 /// @internal
216 apply(action: number, next: number, nextStart: number, nextEnd: number) {
217 if (action & Action.ReduceFlag) this.reduce(action)
218 else this.shift(action, next, nextStart, nextEnd)
219 }
220
221 // Add a prebuilt (reused) node into the buffer.
222 /// @internal
223 useNode(value: Tree, next: number) {
224 let index = this.p.reused.length - 1
225 if (index < 0 || this.p.reused[index] != value) {
226 this.p.reused.push(value)
227 index++
228 }
229 let start = this.pos
230 this.reducePos = this.pos = start + value.length
231 this.pushState(next, start)
232 this.buffer.push(index, start, this.reducePos, -1 /* size == -1 means this is a reused value */)
233 if (this.curContext)
234 this.updateContext(this.curContext.tracker.reuse(this.curContext.context, value, this,
235 this.p.stream.reset(this.pos - value.length)))
236 }
237
238 // Split the stack. Due to the buffer sharing and the fact
239 // that `this.stack` tends to stay quite shallow, this isn't very
240 // expensive.
241 /// @internal
242 split() {
243 let parent: Stack | null = this
244 let off = parent.buffer.length
245 // Because the top of the buffer (after this.pos) may be mutated
246 // to reorder reductions and skipped tokens, and shared buffers
247 // should be immutable, this copies any outstanding skipped tokens
248 // to the new buffer, and puts the base pointer before them.
249 while (off > 0 && parent.buffer[off - 2] > parent.reducePos) off -= 4
250 let buffer = parent.buffer.slice(off), base = parent.bufferBase + off
251 // Make sure parent points to an actual parent with content, if there is such a parent.
252 while (parent && base == parent.bufferBase) parent = parent.parent
253 return new Stack(this.p, this.stack.slice(), this.state, this.reducePos, this.pos,
254 this.score, buffer, base, this.curContext, this.lookAhead, parent)
255 }
256
257 // Try to recover from an error by 'deleting' (ignoring) one token.
258 /// @internal
259 recoverByDelete(next: number, nextEnd: number) {
260 let isNode = next <= this.p.parser.maxNode
261 if (isNode) this.storeNode(next, this.pos, nextEnd, 4)
262 this.storeNode(Term.Err, this.pos, nextEnd, isNode ? 8 : 4)
263 this.pos = this.reducePos = nextEnd
264 this.score -= Recover.Delete
265 }
266
267 /// Check if the given term would be able to be shifted (optionally
268 /// after some reductions) on this stack. This can be useful for
269 /// external tokenizers that want to make sure they only provide a
270 /// given token when it applies.
271 canShift(term: number) {
272 for (let sim = new SimulatedStack(this);;) {
273 let action = this.p.parser.stateSlot(sim.state, ParseState.DefaultReduce) || this.p.parser.hasAction(sim.state, term)
274 if (action == 0) return false
275 if ((action & Action.ReduceFlag) == 0) return true
276 sim.reduce(action)
277 }
278 }
279
280 // Apply up to Recover.MaxNext recovery actions that conceptually
281 // inserts some missing token or rule.
282 /// @internal
283 recoverByInsert(next: number): Stack[] {
284 if (this.stack.length >= Recover.MaxInsertStackDepth) return []
285
286 let nextStates = this.p.parser.nextStates(this.state)
287 if (nextStates.length > Recover.MaxNext << 1 || this.stack.length >= Recover.DampenInsertStackDepth) {
288 let best = []
289 for (let i = 0, s; i < nextStates.length; i += 2) {
290 if ((s = nextStates[i + 1]) != this.state && this.p.parser.hasAction(s, next))
291 best.push(nextStates[i], s)
292 }
293 if (this.stack.length < Recover.DampenInsertStackDepth)
294 for (let i = 0; best.length < Recover.MaxNext << 1 && i < nextStates.length; i += 2) {
295 let s = nextStates[i + 1]
296 if (!best.some((v, i) => (i & 1) && v == s)) best.push(nextStates[i], s)
297 }
298 nextStates = best
299 }
300 let result: Stack[] = []
301 for (let i = 0; i < nextStates.length && result.length < Recover.MaxNext; i += 2) {
302 let s = nextStates[i + 1]
303 if (s == this.state) continue
304 let stack = this.split()
305 stack.pushState(s, this.pos)
306 stack.storeNode(Term.Err, stack.pos, stack.pos, 4, true)
307 stack.shiftContext(nextStates[i], this.pos)
308 stack.reducePos = this.pos
309 stack.score -= Recover.Insert
310 result.push(stack)
311 }
312 return result
313 }
314
315 // Force a reduce, if possible. Return false if that can't
316 // be done.
317 /// @internal
318 forceReduce() {
319 let {parser} = this.p
320 let reduce = parser.stateSlot(this.state, ParseState.ForcedReduce)
321 if ((reduce & Action.ReduceFlag) == 0) return false
322 if (!parser.validAction(this.state, reduce)) {
323 let depth = reduce >> Action.ReduceDepthShift, term = reduce & Action.ValueMask
324 let target = this.stack.length - depth * 3
325 if (target < 0 || parser.getGoto(this.stack[target], term, false) < 0) {
326 let backup = this.findForcedReduction()
327 if (backup == null) return false
328 reduce = backup
329 }
330 this.storeNode(Term.Err, this.pos, this.pos, 4, true)
331 this.score -= Recover.Reduce
332 }
333 this.reducePos = this.pos
334 this.reduce(reduce)
335 return true
336 }
337
338 /// Try to scan through the automaton to find some kind of reduction
339 /// that can be applied. Used when the regular ForcedReduce field
340 /// isn't a valid action. @internal
341 findForcedReduction() {
342 let {parser} = this.p, seen: number[] = []
343 let explore = (state: number, depth: number): number | void => {
344 if (seen.includes(state)) return
345 seen.push(state)
346 return parser.allActions(state, (action): number | void => {
347 if (action & (Action.StayFlag | Action.GotoFlag)) {
348 } else if (action & Action.ReduceFlag) {
349 let rDepth = (action >> Action.ReduceDepthShift) - depth
350 if (rDepth > 1) {
351 let term = action & Action.ValueMask, target = this.stack.length - rDepth * 3
352 if (target >= 0 && parser.getGoto(this.stack[target], term, false) >= 0)
353 return (rDepth << Action.ReduceDepthShift) | Action.ReduceFlag | term
354 }
355 } else {
356 let found = explore(action, depth + 1)
357 if (found != null) return found
358 }
359 })
360 }
361 return explore(this.state, 0)
362 }
363
364 /// @internal
365 forceAll() {
366 while (!this.p.parser.stateFlag(this.state, StateFlag.Accepting)) {
367 if (!this.forceReduce()) {
368 this.storeNode(Term.Err, this.pos, this.pos, 4, true)
369 break
370 }
371 }
372 return this
373 }
374
375 /// Check whether this state has no further actions (assumed to be a direct descendant of the
376 /// top state, since any other states must be able to continue
377 /// somehow). @internal
378 get deadEnd() {
379 if (this.stack.length != 3) return false
380 let {parser} = this.p
381 return parser.data[parser.stateSlot(this.state, ParseState.Actions)] == Seq.End &&
382 !parser.stateSlot(this.state, ParseState.DefaultReduce)
383 }
384
385 /// Restart the stack (put it back in its start state). Only safe
386 /// when this.stack.length == 3 (state is directly below the top
387 /// state). @internal
388 restart() {
389 this.storeNode(Term.Err, this.pos, this.pos, 4, true)
390 this.state = this.stack[0]
391 this.stack.length = 0
392 }
393
394 /// @internal
395 sameState(other: Stack) {
396 if (this.state != other.state || this.stack.length != other.stack.length) return false
397 for (let i = 0; i < this.stack.length; i += 3)
398 if (this.stack[i] != other.stack[i]) return false
399 return true
400 }
401
402 /// Get the parser used by this stack.
403 get parser() { return this.p.parser }
404
405 /// Test whether a given dialect (by numeric ID, as exported from
406 /// the terms file) is enabled.
407 dialectEnabled(dialectID: number) { return this.p.parser.dialect.flags[dialectID] }
408
409 private shiftContext(term: number, start: number) {
410 if (this.curContext)
411 this.updateContext(this.curContext.tracker.shift(this.curContext.context, term, this, this.p.stream.reset(start)))
412 }
413
414 private reduceContext(term: number, start: number) {
415 if (this.curContext)
416 this.updateContext(this.curContext.tracker.reduce(this.curContext.context, term, this, this.p.stream.reset(start)))
417 }
418
419 /// @internal
420 private emitContext() {
421 let last = this.buffer.length - 1
422 if (last < 0 || this.buffer[last] != -3)
423 this.buffer.push(this.curContext!.hash, this.pos, this.pos, -3)
424 }
425
426 /// @internal
427 emitLookAhead() {
428 let last = this.buffer.length - 1
429 if (last < 0 || this.buffer[last] != -4)
430 this.buffer.push(this.lookAhead, this.pos, this.pos, -4)
431 }
432
433 private updateContext(context: any) {
434 if (context != this.curContext!.context) {
435 let newCx = new StackContext(this.curContext!.tracker, context)
436 if (newCx.hash != this.curContext!.hash) this.emitContext()
437 this.curContext = newCx
438 }
439 }
440
441 /// @internal
442 setLookAhead(lookAhead: number) {
443 if (lookAhead > this.lookAhead) {
444 this.emitLookAhead()
445 this.lookAhead = lookAhead
446 }
447 }
448
449 /// @internal
450 close() {
451 if (this.curContext && this.curContext!.tracker.strict) this.emitContext()
452 if (this.lookAhead > 0) this.emitLookAhead()
453 }
454 }
455
456 class StackContext {
457 readonly hash: number
458 constructor(readonly tracker: ContextTracker<any>, readonly context: any) {
459 this.hash = tracker.strict ? tracker.hash(context) : 0
460 }
461 }
462
463 export const enum Recover {
464 Insert = 200,
465 Delete = 190,
466 Reduce = 100,
467 MaxNext = 4,
468 MaxInsertStackDepth = 300,
469 DampenInsertStackDepth = 120,
470 MinBigReduction = 2000
471 }
472
473 // Used to cheaply run some reductions to scan ahead without mutating
474 // an entire stack
475 class SimulatedStack {
476 state: number
477 stack: number[]
478 base: number
479
480 constructor(readonly start: Stack) {
481 this.state = start.state
482 this.stack = start.stack
483 this.base = this.stack.length
484 }
485
486 reduce(action: number) {
487 let term = action & Action.ValueMask, depth = action >> Action.ReduceDepthShift
488 if (depth == 0) {
489 if (this.stack == this.start.stack) this.stack = this.stack.slice()
490 this.stack.push(this.state, 0, 0)
491 this.base += 3
492 } else {
493 this.base -= (depth - 1) * 3
494 }
495 let goto = this.start.p.parser.getGoto(this.stack[this.base - 3], term, true)
496 this.state = goto
497 }
498 }
499
500 // This is given to `Tree.build` to build a buffer, and encapsulates
501 // the parent-stack-walking necessary to read the nodes.
502 export class StackBufferCursor implements BufferCursor {
503 buffer: number[]
504
505 constructor(public stack: Stack, public pos: number, public index: number) {
506 this.buffer = stack.buffer
507 if (this.index == 0) this.maybeNext()
508 }
509
510 static create(stack: Stack, pos = stack.bufferBase + stack.buffer.length) {
511 return new StackBufferCursor(stack, pos, pos - stack.bufferBase)
512 }
513
514 maybeNext() {
515 let next = this.stack.parent
516 if (next != null) {
517 this.index = this.stack.bufferBase - next.bufferBase
518 this.stack = next
519 this.buffer = next.buffer
520 }
521 }
522
523 get id() { return this.buffer[this.index - 4] }
524 get start() { return this.buffer[this.index - 3] }
525 get end() { return this.buffer[this.index - 2] }
526 get size() { return this.buffer[this.index - 1] }
527
528 next() {
529 this.index -= 4
530 this.pos -= 4
531 if (this.index == 0) this.maybeNext()
532 }
533
534 fork() {
535 return new StackBufferCursor(this.stack, this.pos, this.index)
536 }
537 }