diffdown.com
Diffdown is a real-time collaborative Markdown editor/previewer built on the AT Protocol
diffdown.com
1'use strict';
2
3var common = require('@lezer/common');
4
5/**
6A parse stack. These are used internally by the parser to track
7parsing progress. They also provide some properties and methods
8that external code such as a tokenizer can use to get information
9about the parse state.
10*/
11class Stack {
12 /**
13 @internal
14 */
15 constructor(
16 /**
17 The parse that this stack is part of @internal
18 */
19 p,
20 /**
21 Holds state, input pos, buffer index triplets for all but the
22 top state @internal
23 */
24 stack,
25 /**
26 The current parse state @internal
27 */
28 state,
29 // The position at which the next reduce should take place. This
30 // can be less than `this.pos` when skipped expressions have been
31 // added to the stack (which should be moved outside of the next
32 // reduction)
33 /**
34 @internal
35 */
36 reducePos,
37 /**
38 The input position up to which this stack has parsed.
39 */
40 pos,
41 /**
42 The dynamic score of the stack, including dynamic precedence
43 and error-recovery penalties
44 @internal
45 */
46 score,
47 // The output buffer. Holds (type, start, end, size) quads
48 // representing nodes created by the parser, where `size` is
49 // amount of buffer array entries covered by this node.
50 /**
51 @internal
52 */
53 buffer,
54 // The base offset of the buffer. When stacks are split, the split
55 // instance shared the buffer history with its parent up to
56 // `bufferBase`, which is the absolute offset (including the
57 // offset of previous splits) into the buffer at which this stack
58 // starts writing.
59 /**
60 @internal
61 */
62 bufferBase,
63 /**
64 @internal
65 */
66 curContext,
67 /**
68 @internal
69 */
70 lookAhead = 0,
71 // A parent stack from which this was split off, if any. This is
72 // set up so that it always points to a stack that has some
73 // additional buffer content, never to a stack with an equal
74 // `bufferBase`.
75 /**
76 @internal
77 */
78 parent) {
79 this.p = p;
80 this.stack = stack;
81 this.state = state;
82 this.reducePos = reducePos;
83 this.pos = pos;
84 this.score = score;
85 this.buffer = buffer;
86 this.bufferBase = bufferBase;
87 this.curContext = curContext;
88 this.lookAhead = lookAhead;
89 this.parent = parent;
90 }
91 /**
92 @internal
93 */
94 toString() {
95 return `[${this.stack.filter((_, i) => i % 3 == 0).concat(this.state)}]@${this.pos}${this.score ? "!" + this.score : ""}`;
96 }
97 // Start an empty stack
98 /**
99 @internal
100 */
101 static start(p, state, pos = 0) {
102 let cx = p.parser.context;
103 return new Stack(p, [], state, pos, pos, 0, [], 0, cx ? new StackContext(cx, cx.start) : null, 0, null);
104 }
105 /**
106 The stack's current [context](#lr.ContextTracker) value, if
107 any. Its type will depend on the context tracker's type
108 parameter, or it will be `null` if there is no context
109 tracker.
110 */
111 get context() { return this.curContext ? this.curContext.context : null; }
112 // Push a state onto the stack, tracking its start position as well
113 // as the buffer base at that point.
114 /**
115 @internal
116 */
117 pushState(state, start) {
118 this.stack.push(this.state, start, this.bufferBase + this.buffer.length);
119 this.state = state;
120 }
121 // Apply a reduce action
122 /**
123 @internal
124 */
125 reduce(action) {
126 var _a;
127 let depth = action >> 19 /* Action.ReduceDepthShift */, type = action & 65535 /* Action.ValueMask */;
128 let { parser } = this.p;
129 let lookaheadRecord = this.reducePos < this.pos - 25 /* Lookahead.Margin */ && this.setLookAhead(this.pos);
130 let dPrec = parser.dynamicPrecedence(type);
131 if (dPrec)
132 this.score += dPrec;
133 if (depth == 0) {
134 this.pushState(parser.getGoto(this.state, type, true), this.reducePos);
135 // Zero-depth reductions are a special case—they add stuff to
136 // the stack without popping anything off.
137 if (type < parser.minRepeatTerm)
138 this.storeNode(type, this.reducePos, this.reducePos, lookaheadRecord ? 8 : 4, true);
139 this.reduceContext(type, this.reducePos);
140 return;
141 }
142 // Find the base index into `this.stack`, content after which will
143 // be dropped. Note that with `StayFlag` reductions we need to
144 // consume two extra frames (the dummy parent node for the skipped
145 // expression and the state that we'll be staying in, which should
146 // be moved to `this.state`).
147 let base = this.stack.length - ((depth - 1) * 3) - (action & 262144 /* Action.StayFlag */ ? 6 : 0);
148 let start = base ? this.stack[base - 2] : this.p.ranges[0].from, size = this.reducePos - start;
149 // This is a kludge to try and detect overly deep left-associative
150 // trees, which will not increase the parse stack depth and thus
151 // won't be caught by the regular stack-depth limit check.
152 if (size >= 2000 /* Recover.MinBigReduction */ && !((_a = this.p.parser.nodeSet.types[type]) === null || _a === void 0 ? void 0 : _a.isAnonymous)) {
153 if (start == this.p.lastBigReductionStart) {
154 this.p.bigReductionCount++;
155 this.p.lastBigReductionSize = size;
156 }
157 else if (this.p.lastBigReductionSize < size) {
158 this.p.bigReductionCount = 1;
159 this.p.lastBigReductionStart = start;
160 this.p.lastBigReductionSize = size;
161 }
162 }
163 let bufferBase = base ? this.stack[base - 1] : 0, count = this.bufferBase + this.buffer.length - bufferBase;
164 // Store normal terms or `R -> R R` repeat reductions
165 if (type < parser.minRepeatTerm || (action & 131072 /* Action.RepeatFlag */)) {
166 let pos = parser.stateFlag(this.state, 1 /* StateFlag.Skipped */) ? this.pos : this.reducePos;
167 this.storeNode(type, start, pos, count + 4, true);
168 }
169 if (action & 262144 /* Action.StayFlag */) {
170 this.state = this.stack[base];
171 }
172 else {
173 let baseStateID = this.stack[base - 3];
174 this.state = parser.getGoto(baseStateID, type, true);
175 }
176 while (this.stack.length > base)
177 this.stack.pop();
178 this.reduceContext(type, start);
179 }
180 // Shift a value into the buffer
181 /**
182 @internal
183 */
184 storeNode(term, start, end, size = 4, mustSink = false) {
185 if (term == 0 /* Term.Err */ &&
186 (!this.stack.length || this.stack[this.stack.length - 1] < this.buffer.length + this.bufferBase)) {
187 // Try to omit/merge adjacent error nodes
188 let cur = this, top = this.buffer.length;
189 if (top == 0 && cur.parent) {
190 top = cur.bufferBase - cur.parent.bufferBase;
191 cur = cur.parent;
192 }
193 if (top > 0 && cur.buffer[top - 4] == 0 /* Term.Err */ && cur.buffer[top - 1] > -1) {
194 if (start == end)
195 return;
196 if (cur.buffer[top - 2] >= start) {
197 cur.buffer[top - 2] = end;
198 return;
199 }
200 }
201 }
202 if (!mustSink || this.pos == end) { // Simple case, just append
203 this.buffer.push(term, start, end, size);
204 }
205 else { // There may be skipped nodes that have to be moved forward
206 let index = this.buffer.length;
207 if (index > 0 && (this.buffer[index - 4] != 0 /* Term.Err */ || this.buffer[index - 1] < 0)) {
208 let mustMove = false;
209 for (let scan = index; scan > 0 && this.buffer[scan - 2] > end; scan -= 4) {
210 if (this.buffer[scan - 1] >= 0) {
211 mustMove = true;
212 break;
213 }
214 }
215 if (mustMove)
216 while (index > 0 && this.buffer[index - 2] > end) {
217 // Move this record forward
218 this.buffer[index] = this.buffer[index - 4];
219 this.buffer[index + 1] = this.buffer[index - 3];
220 this.buffer[index + 2] = this.buffer[index - 2];
221 this.buffer[index + 3] = this.buffer[index - 1];
222 index -= 4;
223 if (size > 4)
224 size -= 4;
225 }
226 }
227 this.buffer[index] = term;
228 this.buffer[index + 1] = start;
229 this.buffer[index + 2] = end;
230 this.buffer[index + 3] = size;
231 }
232 }
233 // Apply a shift action
234 /**
235 @internal
236 */
237 shift(action, type, start, end) {
238 if (action & 131072 /* Action.GotoFlag */) {
239 this.pushState(action & 65535 /* Action.ValueMask */, this.pos);
240 }
241 else if ((action & 262144 /* Action.StayFlag */) == 0) { // Regular shift
242 let nextState = action, { parser } = this.p;
243 this.pos = end;
244 let skipped = parser.stateFlag(nextState, 1 /* StateFlag.Skipped */);
245 // Skipped or zero-length non-tree tokens don't move reducePos
246 if (!skipped && (end > start || type <= parser.maxNode))
247 this.reducePos = end;
248 this.pushState(nextState, skipped ? start : Math.min(start, this.reducePos));
249 this.shiftContext(type, start);
250 if (type <= parser.maxNode)
251 this.buffer.push(type, start, end, 4);
252 }
253 else { // Shift-and-stay, which means this is a skipped token
254 this.pos = end;
255 this.shiftContext(type, start);
256 if (type <= this.p.parser.maxNode)
257 this.buffer.push(type, start, end, 4);
258 }
259 }
260 // Apply an action
261 /**
262 @internal
263 */
264 apply(action, next, nextStart, nextEnd) {
265 if (action & 65536 /* Action.ReduceFlag */)
266 this.reduce(action);
267 else
268 this.shift(action, next, nextStart, nextEnd);
269 }
270 // Add a prebuilt (reused) node into the buffer.
271 /**
272 @internal
273 */
274 useNode(value, next) {
275 let index = this.p.reused.length - 1;
276 if (index < 0 || this.p.reused[index] != value) {
277 this.p.reused.push(value);
278 index++;
279 }
280 let start = this.pos;
281 this.reducePos = this.pos = start + value.length;
282 this.pushState(next, start);
283 this.buffer.push(index, start, this.reducePos, -1 /* size == -1 means this is a reused value */);
284 if (this.curContext)
285 this.updateContext(this.curContext.tracker.reuse(this.curContext.context, value, this, this.p.stream.reset(this.pos - value.length)));
286 }
287 // Split the stack. Due to the buffer sharing and the fact
288 // that `this.stack` tends to stay quite shallow, this isn't very
289 // expensive.
290 /**
291 @internal
292 */
293 split() {
294 let parent = this;
295 let off = parent.buffer.length;
296 // Because the top of the buffer (after this.pos) may be mutated
297 // to reorder reductions and skipped tokens, and shared buffers
298 // should be immutable, this copies any outstanding skipped tokens
299 // to the new buffer, and puts the base pointer before them.
300 while (off > 0 && parent.buffer[off - 2] > parent.reducePos)
301 off -= 4;
302 let buffer = parent.buffer.slice(off), base = parent.bufferBase + off;
303 // Make sure parent points to an actual parent with content, if there is such a parent.
304 while (parent && base == parent.bufferBase)
305 parent = parent.parent;
306 return new Stack(this.p, this.stack.slice(), this.state, this.reducePos, this.pos, this.score, buffer, base, this.curContext, this.lookAhead, parent);
307 }
308 // Try to recover from an error by 'deleting' (ignoring) one token.
309 /**
310 @internal
311 */
312 recoverByDelete(next, nextEnd) {
313 let isNode = next <= this.p.parser.maxNode;
314 if (isNode)
315 this.storeNode(next, this.pos, nextEnd, 4);
316 this.storeNode(0 /* Term.Err */, this.pos, nextEnd, isNode ? 8 : 4);
317 this.pos = this.reducePos = nextEnd;
318 this.score -= 190 /* Recover.Delete */;
319 }
320 /**
321 Check if the given term would be able to be shifted (optionally
322 after some reductions) on this stack. This can be useful for
323 external tokenizers that want to make sure they only provide a
324 given token when it applies.
325 */
326 canShift(term) {
327 for (let sim = new SimulatedStack(this);;) {
328 let action = this.p.parser.stateSlot(sim.state, 4 /* ParseState.DefaultReduce */) || this.p.parser.hasAction(sim.state, term);
329 if (action == 0)
330 return false;
331 if ((action & 65536 /* Action.ReduceFlag */) == 0)
332 return true;
333 sim.reduce(action);
334 }
335 }
336 // Apply up to Recover.MaxNext recovery actions that conceptually
337 // inserts some missing token or rule.
338 /**
339 @internal
340 */
341 recoverByInsert(next) {
342 if (this.stack.length >= 300 /* Recover.MaxInsertStackDepth */)
343 return [];
344 let nextStates = this.p.parser.nextStates(this.state);
345 if (nextStates.length > 4 /* Recover.MaxNext */ << 1 || this.stack.length >= 120 /* Recover.DampenInsertStackDepth */) {
346 let best = [];
347 for (let i = 0, s; i < nextStates.length; i += 2) {
348 if ((s = nextStates[i + 1]) != this.state && this.p.parser.hasAction(s, next))
349 best.push(nextStates[i], s);
350 }
351 if (this.stack.length < 120 /* Recover.DampenInsertStackDepth */)
352 for (let i = 0; best.length < 4 /* Recover.MaxNext */ << 1 && i < nextStates.length; i += 2) {
353 let s = nextStates[i + 1];
354 if (!best.some((v, i) => (i & 1) && v == s))
355 best.push(nextStates[i], s);
356 }
357 nextStates = best;
358 }
359 let result = [];
360 for (let i = 0; i < nextStates.length && result.length < 4 /* Recover.MaxNext */; i += 2) {
361 let s = nextStates[i + 1];
362 if (s == this.state)
363 continue;
364 let stack = this.split();
365 stack.pushState(s, this.pos);
366 stack.storeNode(0 /* Term.Err */, stack.pos, stack.pos, 4, true);
367 stack.shiftContext(nextStates[i], this.pos);
368 stack.reducePos = this.pos;
369 stack.score -= 200 /* Recover.Insert */;
370 result.push(stack);
371 }
372 return result;
373 }
374 // Force a reduce, if possible. Return false if that can't
375 // be done.
376 /**
377 @internal
378 */
379 forceReduce() {
380 let { parser } = this.p;
381 let reduce = parser.stateSlot(this.state, 5 /* ParseState.ForcedReduce */);
382 if ((reduce & 65536 /* Action.ReduceFlag */) == 0)
383 return false;
384 if (!parser.validAction(this.state, reduce)) {
385 let depth = reduce >> 19 /* Action.ReduceDepthShift */, term = reduce & 65535 /* Action.ValueMask */;
386 let target = this.stack.length - depth * 3;
387 if (target < 0 || parser.getGoto(this.stack[target], term, false) < 0) {
388 let backup = this.findForcedReduction();
389 if (backup == null)
390 return false;
391 reduce = backup;
392 }
393 this.storeNode(0 /* Term.Err */, this.pos, this.pos, 4, true);
394 this.score -= 100 /* Recover.Reduce */;
395 }
396 this.reducePos = this.pos;
397 this.reduce(reduce);
398 return true;
399 }
400 /**
401 Try to scan through the automaton to find some kind of reduction
402 that can be applied. Used when the regular ForcedReduce field
403 isn't a valid action. @internal
404 */
405 findForcedReduction() {
406 let { parser } = this.p, seen = [];
407 let explore = (state, depth) => {
408 if (seen.includes(state))
409 return;
410 seen.push(state);
411 return parser.allActions(state, (action) => {
412 if (action & (262144 /* Action.StayFlag */ | 131072 /* Action.GotoFlag */)) ;
413 else if (action & 65536 /* Action.ReduceFlag */) {
414 let rDepth = (action >> 19 /* Action.ReduceDepthShift */) - depth;
415 if (rDepth > 1) {
416 let term = action & 65535 /* Action.ValueMask */, target = this.stack.length - rDepth * 3;
417 if (target >= 0 && parser.getGoto(this.stack[target], term, false) >= 0)
418 return (rDepth << 19 /* Action.ReduceDepthShift */) | 65536 /* Action.ReduceFlag */ | term;
419 }
420 }
421 else {
422 let found = explore(action, depth + 1);
423 if (found != null)
424 return found;
425 }
426 });
427 };
428 return explore(this.state, 0);
429 }
430 /**
431 @internal
432 */
433 forceAll() {
434 while (!this.p.parser.stateFlag(this.state, 2 /* StateFlag.Accepting */)) {
435 if (!this.forceReduce()) {
436 this.storeNode(0 /* Term.Err */, this.pos, this.pos, 4, true);
437 break;
438 }
439 }
440 return this;
441 }
442 /**
443 Check whether this state has no further actions (assumed to be a direct descendant of the
444 top state, since any other states must be able to continue
445 somehow). @internal
446 */
447 get deadEnd() {
448 if (this.stack.length != 3)
449 return false;
450 let { parser } = this.p;
451 return parser.data[parser.stateSlot(this.state, 1 /* ParseState.Actions */)] == 65535 /* Seq.End */ &&
452 !parser.stateSlot(this.state, 4 /* ParseState.DefaultReduce */);
453 }
454 /**
455 Restart the stack (put it back in its start state). Only safe
456 when this.stack.length == 3 (state is directly below the top
457 state). @internal
458 */
459 restart() {
460 this.storeNode(0 /* Term.Err */, this.pos, this.pos, 4, true);
461 this.state = this.stack[0];
462 this.stack.length = 0;
463 }
464 /**
465 @internal
466 */
467 sameState(other) {
468 if (this.state != other.state || this.stack.length != other.stack.length)
469 return false;
470 for (let i = 0; i < this.stack.length; i += 3)
471 if (this.stack[i] != other.stack[i])
472 return false;
473 return true;
474 }
475 /**
476 Get the parser used by this stack.
477 */
478 get parser() { return this.p.parser; }
479 /**
480 Test whether a given dialect (by numeric ID, as exported from
481 the terms file) is enabled.
482 */
483 dialectEnabled(dialectID) { return this.p.parser.dialect.flags[dialectID]; }
484 shiftContext(term, start) {
485 if (this.curContext)
486 this.updateContext(this.curContext.tracker.shift(this.curContext.context, term, this, this.p.stream.reset(start)));
487 }
488 reduceContext(term, start) {
489 if (this.curContext)
490 this.updateContext(this.curContext.tracker.reduce(this.curContext.context, term, this, this.p.stream.reset(start)));
491 }
492 /**
493 @internal
494 */
495 emitContext() {
496 let last = this.buffer.length - 1;
497 if (last < 0 || this.buffer[last] != -3)
498 this.buffer.push(this.curContext.hash, this.pos, this.pos, -3);
499 }
500 /**
501 @internal
502 */
503 emitLookAhead() {
504 let last = this.buffer.length - 1;
505 if (last < 0 || this.buffer[last] != -4)
506 this.buffer.push(this.lookAhead, this.pos, this.pos, -4);
507 }
508 updateContext(context) {
509 if (context != this.curContext.context) {
510 let newCx = new StackContext(this.curContext.tracker, context);
511 if (newCx.hash != this.curContext.hash)
512 this.emitContext();
513 this.curContext = newCx;
514 }
515 }
516 /**
517 @internal
518 */
519 setLookAhead(lookAhead) {
520 if (lookAhead <= this.lookAhead)
521 return false;
522 this.emitLookAhead();
523 this.lookAhead = lookAhead;
524 return true;
525 }
526 /**
527 @internal
528 */
529 close() {
530 if (this.curContext && this.curContext.tracker.strict)
531 this.emitContext();
532 if (this.lookAhead > 0)
533 this.emitLookAhead();
534 }
535}
536class StackContext {
537 constructor(tracker, context) {
538 this.tracker = tracker;
539 this.context = context;
540 this.hash = tracker.strict ? tracker.hash(context) : 0;
541 }
542}
543// Used to cheaply run some reductions to scan ahead without mutating
544// an entire stack
545class SimulatedStack {
546 constructor(start) {
547 this.start = start;
548 this.state = start.state;
549 this.stack = start.stack;
550 this.base = this.stack.length;
551 }
552 reduce(action) {
553 let term = action & 65535 /* Action.ValueMask */, depth = action >> 19 /* Action.ReduceDepthShift */;
554 if (depth == 0) {
555 if (this.stack == this.start.stack)
556 this.stack = this.stack.slice();
557 this.stack.push(this.state, 0, 0);
558 this.base += 3;
559 }
560 else {
561 this.base -= (depth - 1) * 3;
562 }
563 let goto = this.start.p.parser.getGoto(this.stack[this.base - 3], term, true);
564 this.state = goto;
565 }
566}
567// This is given to `Tree.build` to build a buffer, and encapsulates
568// the parent-stack-walking necessary to read the nodes.
569class StackBufferCursor {
570 constructor(stack, pos, index) {
571 this.stack = stack;
572 this.pos = pos;
573 this.index = index;
574 this.buffer = stack.buffer;
575 if (this.index == 0)
576 this.maybeNext();
577 }
578 static create(stack, pos = stack.bufferBase + stack.buffer.length) {
579 return new StackBufferCursor(stack, pos, pos - stack.bufferBase);
580 }
581 maybeNext() {
582 let next = this.stack.parent;
583 if (next != null) {
584 this.index = this.stack.bufferBase - next.bufferBase;
585 this.stack = next;
586 this.buffer = next.buffer;
587 }
588 }
589 get id() { return this.buffer[this.index - 4]; }
590 get start() { return this.buffer[this.index - 3]; }
591 get end() { return this.buffer[this.index - 2]; }
592 get size() { return this.buffer[this.index - 1]; }
593 next() {
594 this.index -= 4;
595 this.pos -= 4;
596 if (this.index == 0)
597 this.maybeNext();
598 }
599 fork() {
600 return new StackBufferCursor(this.stack, this.pos, this.index);
601 }
602}
603
604// See lezer-generator/src/encode.ts for comments about the encoding
605// used here
606function decodeArray(input, Type = Uint16Array) {
607 if (typeof input != "string")
608 return input;
609 let array = null;
610 for (let pos = 0, out = 0; pos < input.length;) {
611 let value = 0;
612 for (;;) {
613 let next = input.charCodeAt(pos++), stop = false;
614 if (next == 126 /* Encode.BigValCode */) {
615 value = 65535 /* Encode.BigVal */;
616 break;
617 }
618 if (next >= 92 /* Encode.Gap2 */)
619 next--;
620 if (next >= 34 /* Encode.Gap1 */)
621 next--;
622 let digit = next - 32 /* Encode.Start */;
623 if (digit >= 46 /* Encode.Base */) {
624 digit -= 46 /* Encode.Base */;
625 stop = true;
626 }
627 value += digit;
628 if (stop)
629 break;
630 value *= 46 /* Encode.Base */;
631 }
632 if (array)
633 array[out++] = value;
634 else
635 array = new Type(value);
636 }
637 return array;
638}
639
640class CachedToken {
641 constructor() {
642 this.start = -1;
643 this.value = -1;
644 this.end = -1;
645 this.extended = -1;
646 this.lookAhead = 0;
647 this.mask = 0;
648 this.context = 0;
649 }
650}
651const nullToken = new CachedToken;
652/**
653[Tokenizers](#lr.ExternalTokenizer) interact with the input
654through this interface. It presents the input as a stream of
655characters, tracking lookahead and hiding the complexity of
656[ranges](#common.Parser.parse^ranges) from tokenizer code.
657*/
658class InputStream {
659 /**
660 @internal
661 */
662 constructor(
663 /**
664 @internal
665 */
666 input,
667 /**
668 @internal
669 */
670 ranges) {
671 this.input = input;
672 this.ranges = ranges;
673 /**
674 @internal
675 */
676 this.chunk = "";
677 /**
678 @internal
679 */
680 this.chunkOff = 0;
681 /**
682 Backup chunk
683 */
684 this.chunk2 = "";
685 this.chunk2Pos = 0;
686 /**
687 The character code of the next code unit in the input, or -1
688 when the stream is at the end of the input.
689 */
690 this.next = -1;
691 /**
692 @internal
693 */
694 this.token = nullToken;
695 this.rangeIndex = 0;
696 this.pos = this.chunkPos = ranges[0].from;
697 this.range = ranges[0];
698 this.end = ranges[ranges.length - 1].to;
699 this.readNext();
700 }
701 /**
702 @internal
703 */
704 resolveOffset(offset, assoc) {
705 let range = this.range, index = this.rangeIndex;
706 let pos = this.pos + offset;
707 while (pos < range.from) {
708 if (!index)
709 return null;
710 let next = this.ranges[--index];
711 pos -= range.from - next.to;
712 range = next;
713 }
714 while (assoc < 0 ? pos > range.to : pos >= range.to) {
715 if (index == this.ranges.length - 1)
716 return null;
717 let next = this.ranges[++index];
718 pos += next.from - range.to;
719 range = next;
720 }
721 return pos;
722 }
723 /**
724 @internal
725 */
726 clipPos(pos) {
727 if (pos >= this.range.from && pos < this.range.to)
728 return pos;
729 for (let range of this.ranges)
730 if (range.to > pos)
731 return Math.max(pos, range.from);
732 return this.end;
733 }
734 /**
735 Look at a code unit near the stream position. `.peek(0)` equals
736 `.next`, `.peek(-1)` gives you the previous character, and so
737 on.
738
739 Note that looking around during tokenizing creates dependencies
740 on potentially far-away content, which may reduce the
741 effectiveness incremental parsing—when looking forward—or even
742 cause invalid reparses when looking backward more than 25 code
743 units, since the library does not track lookbehind.
744 */
745 peek(offset) {
746 let idx = this.chunkOff + offset, pos, result;
747 if (idx >= 0 && idx < this.chunk.length) {
748 pos = this.pos + offset;
749 result = this.chunk.charCodeAt(idx);
750 }
751 else {
752 let resolved = this.resolveOffset(offset, 1);
753 if (resolved == null)
754 return -1;
755 pos = resolved;
756 if (pos >= this.chunk2Pos && pos < this.chunk2Pos + this.chunk2.length) {
757 result = this.chunk2.charCodeAt(pos - this.chunk2Pos);
758 }
759 else {
760 let i = this.rangeIndex, range = this.range;
761 while (range.to <= pos)
762 range = this.ranges[++i];
763 this.chunk2 = this.input.chunk(this.chunk2Pos = pos);
764 if (pos + this.chunk2.length > range.to)
765 this.chunk2 = this.chunk2.slice(0, range.to - pos);
766 result = this.chunk2.charCodeAt(0);
767 }
768 }
769 if (pos >= this.token.lookAhead)
770 this.token.lookAhead = pos + 1;
771 return result;
772 }
773 /**
774 Accept a token. By default, the end of the token is set to the
775 current stream position, but you can pass an offset (relative to
776 the stream position) to change that.
777 */
778 acceptToken(token, endOffset = 0) {
779 let end = endOffset ? this.resolveOffset(endOffset, -1) : this.pos;
780 if (end == null || end < this.token.start)
781 throw new RangeError("Token end out of bounds");
782 this.token.value = token;
783 this.token.end = end;
784 }
785 /**
786 Accept a token ending at a specific given position.
787 */
788 acceptTokenTo(token, endPos) {
789 this.token.value = token;
790 this.token.end = endPos;
791 }
792 getChunk() {
793 if (this.pos >= this.chunk2Pos && this.pos < this.chunk2Pos + this.chunk2.length) {
794 let { chunk, chunkPos } = this;
795 this.chunk = this.chunk2;
796 this.chunkPos = this.chunk2Pos;
797 this.chunk2 = chunk;
798 this.chunk2Pos = chunkPos;
799 this.chunkOff = this.pos - this.chunkPos;
800 }
801 else {
802 this.chunk2 = this.chunk;
803 this.chunk2Pos = this.chunkPos;
804 let nextChunk = this.input.chunk(this.pos);
805 let end = this.pos + nextChunk.length;
806 this.chunk = end > this.range.to ? nextChunk.slice(0, this.range.to - this.pos) : nextChunk;
807 this.chunkPos = this.pos;
808 this.chunkOff = 0;
809 }
810 }
811 readNext() {
812 if (this.chunkOff >= this.chunk.length) {
813 this.getChunk();
814 if (this.chunkOff == this.chunk.length)
815 return this.next = -1;
816 }
817 return this.next = this.chunk.charCodeAt(this.chunkOff);
818 }
819 /**
820 Move the stream forward N (defaults to 1) code units. Returns
821 the new value of [`next`](#lr.InputStream.next).
822 */
823 advance(n = 1) {
824 this.chunkOff += n;
825 while (this.pos + n >= this.range.to) {
826 if (this.rangeIndex == this.ranges.length - 1)
827 return this.setDone();
828 n -= this.range.to - this.pos;
829 this.range = this.ranges[++this.rangeIndex];
830 this.pos = this.range.from;
831 }
832 this.pos += n;
833 if (this.pos >= this.token.lookAhead)
834 this.token.lookAhead = this.pos + 1;
835 return this.readNext();
836 }
837 setDone() {
838 this.pos = this.chunkPos = this.end;
839 this.range = this.ranges[this.rangeIndex = this.ranges.length - 1];
840 this.chunk = "";
841 return this.next = -1;
842 }
843 /**
844 @internal
845 */
846 reset(pos, token) {
847 if (token) {
848 this.token = token;
849 token.start = pos;
850 token.lookAhead = pos + 1;
851 token.value = token.extended = -1;
852 }
853 else {
854 this.token = nullToken;
855 }
856 if (this.pos != pos) {
857 this.pos = pos;
858 if (pos == this.end) {
859 this.setDone();
860 return this;
861 }
862 while (pos < this.range.from)
863 this.range = this.ranges[--this.rangeIndex];
864 while (pos >= this.range.to)
865 this.range = this.ranges[++this.rangeIndex];
866 if (pos >= this.chunkPos && pos < this.chunkPos + this.chunk.length) {
867 this.chunkOff = pos - this.chunkPos;
868 }
869 else {
870 this.chunk = "";
871 this.chunkOff = 0;
872 }
873 this.readNext();
874 }
875 return this;
876 }
877 /**
878 @internal
879 */
880 read(from, to) {
881 if (from >= this.chunkPos && to <= this.chunkPos + this.chunk.length)
882 return this.chunk.slice(from - this.chunkPos, to - this.chunkPos);
883 if (from >= this.chunk2Pos && to <= this.chunk2Pos + this.chunk2.length)
884 return this.chunk2.slice(from - this.chunk2Pos, to - this.chunk2Pos);
885 if (from >= this.range.from && to <= this.range.to)
886 return this.input.read(from, to);
887 let result = "";
888 for (let r of this.ranges) {
889 if (r.from >= to)
890 break;
891 if (r.to > from)
892 result += this.input.read(Math.max(r.from, from), Math.min(r.to, to));
893 }
894 return result;
895 }
896}
897/**
898@internal
899*/
900class TokenGroup {
901 constructor(data, id) {
902 this.data = data;
903 this.id = id;
904 }
905 token(input, stack) {
906 let { parser } = stack.p;
907 readToken(this.data, input, stack, this.id, parser.data, parser.tokenPrecTable);
908 }
909}
910TokenGroup.prototype.contextual = TokenGroup.prototype.fallback = TokenGroup.prototype.extend = false;
911/**
912@hide
913*/
914class LocalTokenGroup {
915 constructor(data, precTable, elseToken) {
916 this.precTable = precTable;
917 this.elseToken = elseToken;
918 this.data = typeof data == "string" ? decodeArray(data) : data;
919 }
920 token(input, stack) {
921 let start = input.pos, skipped = 0;
922 for (;;) {
923 let atEof = input.next < 0, nextPos = input.resolveOffset(1, 1);
924 readToken(this.data, input, stack, 0, this.data, this.precTable);
925 if (input.token.value > -1)
926 break;
927 if (this.elseToken == null)
928 return;
929 if (!atEof)
930 skipped++;
931 if (nextPos == null)
932 break;
933 input.reset(nextPos, input.token);
934 }
935 if (skipped) {
936 input.reset(start, input.token);
937 input.acceptToken(this.elseToken, skipped);
938 }
939 }
940}
941LocalTokenGroup.prototype.contextual = TokenGroup.prototype.fallback = TokenGroup.prototype.extend = false;
942/**
943`@external tokens` declarations in the grammar should resolve to
944an instance of this class.
945*/
946class ExternalTokenizer {
947 /**
948 Create a tokenizer. The first argument is the function that,
949 given an input stream, scans for the types of tokens it
950 recognizes at the stream's position, and calls
951 [`acceptToken`](#lr.InputStream.acceptToken) when it finds
952 one.
953 */
954 constructor(
955 /**
956 @internal
957 */
958 token, options = {}) {
959 this.token = token;
960 this.contextual = !!options.contextual;
961 this.fallback = !!options.fallback;
962 this.extend = !!options.extend;
963 }
964}
965// Tokenizer data is stored a big uint16 array containing, for each
966// state:
967//
968// - A group bitmask, indicating what token groups are reachable from
969// this state, so that paths that can only lead to tokens not in
970// any of the current groups can be cut off early.
971//
972// - The position of the end of the state's sequence of accepting
973// tokens
974//
975// - The number of outgoing edges for the state
976//
977// - The accepting tokens, as (token id, group mask) pairs
978//
979// - The outgoing edges, as (start character, end character, state
980// index) triples, with end character being exclusive
981//
982// This function interprets that data, running through a stream as
983// long as new states with the a matching group mask can be reached,
984// and updating `input.token` when it matches a token.
985function readToken(data, input, stack, group, precTable, precOffset) {
986 let state = 0, groupMask = 1 << group, { dialect } = stack.p.parser;
987 scan: for (;;) {
988 if ((groupMask & data[state]) == 0)
989 break;
990 let accEnd = data[state + 1];
991 // Check whether this state can lead to a token in the current group
992 // Accept tokens in this state, possibly overwriting
993 // lower-precedence / shorter tokens
994 for (let i = state + 3; i < accEnd; i += 2)
995 if ((data[i + 1] & groupMask) > 0) {
996 let term = data[i];
997 if (dialect.allows(term) &&
998 (input.token.value == -1 || input.token.value == term ||
999 overrides(term, input.token.value, precTable, precOffset))) {
1000 input.acceptToken(term);
1001 break;
1002 }
1003 }
1004 let next = input.next, low = 0, high = data[state + 2];
1005 // Special case for EOF
1006 if (input.next < 0 && high > low && data[accEnd + high * 3 - 3] == 65535 /* Seq.End */) {
1007 state = data[accEnd + high * 3 - 1];
1008 continue scan;
1009 }
1010 // Do a binary search on the state's edges
1011 for (; low < high;) {
1012 let mid = (low + high) >> 1;
1013 let index = accEnd + mid + (mid << 1);
1014 let from = data[index], to = data[index + 1] || 0x10000;
1015 if (next < from)
1016 high = mid;
1017 else if (next >= to)
1018 low = mid + 1;
1019 else {
1020 state = data[index + 2];
1021 input.advance();
1022 continue scan;
1023 }
1024 }
1025 break;
1026 }
1027}
1028function findOffset(data, start, term) {
1029 for (let i = start, next; (next = data[i]) != 65535 /* Seq.End */; i++)
1030 if (next == term)
1031 return i - start;
1032 return -1;
1033}
1034function overrides(token, prev, tableData, tableOffset) {
1035 let iPrev = findOffset(tableData, tableOffset, prev);
1036 return iPrev < 0 || findOffset(tableData, tableOffset, token) < iPrev;
1037}
1038
1039// Environment variable used to control console output
1040const verbose = typeof process != "undefined" && process.env && /\bparse\b/.test(process.env.LOG);
1041let stackIDs = null;
1042function cutAt(tree, pos, side) {
1043 let cursor = tree.cursor(common.IterMode.IncludeAnonymous);
1044 cursor.moveTo(pos);
1045 for (;;) {
1046 if (!(side < 0 ? cursor.childBefore(pos) : cursor.childAfter(pos)))
1047 for (;;) {
1048 if ((side < 0 ? cursor.to < pos : cursor.from > pos) && !cursor.type.isError)
1049 return side < 0 ? Math.max(0, Math.min(cursor.to - 1, pos - 25 /* Lookahead.Margin */))
1050 : Math.min(tree.length, Math.max(cursor.from + 1, pos + 25 /* Lookahead.Margin */));
1051 if (side < 0 ? cursor.prevSibling() : cursor.nextSibling())
1052 break;
1053 if (!cursor.parent())
1054 return side < 0 ? 0 : tree.length;
1055 }
1056 }
1057}
1058class FragmentCursor {
1059 constructor(fragments, nodeSet) {
1060 this.fragments = fragments;
1061 this.nodeSet = nodeSet;
1062 this.i = 0;
1063 this.fragment = null;
1064 this.safeFrom = -1;
1065 this.safeTo = -1;
1066 this.trees = [];
1067 this.start = [];
1068 this.index = [];
1069 this.nextFragment();
1070 }
1071 nextFragment() {
1072 let fr = this.fragment = this.i == this.fragments.length ? null : this.fragments[this.i++];
1073 if (fr) {
1074 this.safeFrom = fr.openStart ? cutAt(fr.tree, fr.from + fr.offset, 1) - fr.offset : fr.from;
1075 this.safeTo = fr.openEnd ? cutAt(fr.tree, fr.to + fr.offset, -1) - fr.offset : fr.to;
1076 while (this.trees.length) {
1077 this.trees.pop();
1078 this.start.pop();
1079 this.index.pop();
1080 }
1081 this.trees.push(fr.tree);
1082 this.start.push(-fr.offset);
1083 this.index.push(0);
1084 this.nextStart = this.safeFrom;
1085 }
1086 else {
1087 this.nextStart = 1e9;
1088 }
1089 }
1090 // `pos` must be >= any previously given `pos` for this cursor
1091 nodeAt(pos) {
1092 if (pos < this.nextStart)
1093 return null;
1094 while (this.fragment && this.safeTo <= pos)
1095 this.nextFragment();
1096 if (!this.fragment)
1097 return null;
1098 for (;;) {
1099 let last = this.trees.length - 1;
1100 if (last < 0) { // End of tree
1101 this.nextFragment();
1102 return null;
1103 }
1104 let top = this.trees[last], index = this.index[last];
1105 if (index == top.children.length) {
1106 this.trees.pop();
1107 this.start.pop();
1108 this.index.pop();
1109 continue;
1110 }
1111 let next = top.children[index];
1112 let start = this.start[last] + top.positions[index];
1113 if (start > pos) {
1114 this.nextStart = start;
1115 return null;
1116 }
1117 if (next instanceof common.Tree) {
1118 if (start == pos) {
1119 if (start < this.safeFrom)
1120 return null;
1121 let end = start + next.length;
1122 if (end <= this.safeTo) {
1123 let lookAhead = next.prop(common.NodeProp.lookAhead);
1124 if (!lookAhead || end + lookAhead < this.fragment.to)
1125 return next;
1126 }
1127 }
1128 this.index[last]++;
1129 if (start + next.length >= Math.max(this.safeFrom, pos)) { // Enter this node
1130 this.trees.push(next);
1131 this.start.push(start);
1132 this.index.push(0);
1133 }
1134 }
1135 else {
1136 this.index[last]++;
1137 this.nextStart = start + next.length;
1138 }
1139 }
1140 }
1141}
1142class TokenCache {
1143 constructor(parser, stream) {
1144 this.stream = stream;
1145 this.tokens = [];
1146 this.mainToken = null;
1147 this.actions = [];
1148 this.tokens = parser.tokenizers.map(_ => new CachedToken);
1149 }
1150 getActions(stack) {
1151 let actionIndex = 0;
1152 let main = null;
1153 let { parser } = stack.p, { tokenizers } = parser;
1154 let mask = parser.stateSlot(stack.state, 3 /* ParseState.TokenizerMask */);
1155 let context = stack.curContext ? stack.curContext.hash : 0;
1156 let lookAhead = 0;
1157 for (let i = 0; i < tokenizers.length; i++) {
1158 if (((1 << i) & mask) == 0)
1159 continue;
1160 let tokenizer = tokenizers[i], token = this.tokens[i];
1161 if (main && !tokenizer.fallback)
1162 continue;
1163 if (tokenizer.contextual || token.start != stack.pos || token.mask != mask || token.context != context) {
1164 this.updateCachedToken(token, tokenizer, stack);
1165 token.mask = mask;
1166 token.context = context;
1167 }
1168 if (token.lookAhead > token.end + 25 /* Lookahead.Margin */)
1169 lookAhead = Math.max(token.lookAhead, lookAhead);
1170 if (token.value != 0 /* Term.Err */) {
1171 let startIndex = actionIndex;
1172 if (token.extended > -1)
1173 actionIndex = this.addActions(stack, token.extended, token.end, actionIndex);
1174 actionIndex = this.addActions(stack, token.value, token.end, actionIndex);
1175 if (!tokenizer.extend) {
1176 main = token;
1177 if (actionIndex > startIndex)
1178 break;
1179 }
1180 }
1181 }
1182 while (this.actions.length > actionIndex)
1183 this.actions.pop();
1184 if (lookAhead)
1185 stack.setLookAhead(lookAhead);
1186 if (!main && stack.pos == this.stream.end) {
1187 main = new CachedToken;
1188 main.value = stack.p.parser.eofTerm;
1189 main.start = main.end = stack.pos;
1190 actionIndex = this.addActions(stack, main.value, main.end, actionIndex);
1191 }
1192 this.mainToken = main;
1193 return this.actions;
1194 }
1195 getMainToken(stack) {
1196 if (this.mainToken)
1197 return this.mainToken;
1198 let main = new CachedToken, { pos, p } = stack;
1199 main.start = pos;
1200 main.end = Math.min(pos + 1, p.stream.end);
1201 main.value = pos == p.stream.end ? p.parser.eofTerm : 0 /* Term.Err */;
1202 return main;
1203 }
1204 updateCachedToken(token, tokenizer, stack) {
1205 let start = this.stream.clipPos(stack.pos);
1206 tokenizer.token(this.stream.reset(start, token), stack);
1207 if (token.value > -1) {
1208 let { parser } = stack.p;
1209 for (let i = 0; i < parser.specialized.length; i++)
1210 if (parser.specialized[i] == token.value) {
1211 let result = parser.specializers[i](this.stream.read(token.start, token.end), stack);
1212 if (result >= 0 && stack.p.parser.dialect.allows(result >> 1)) {
1213 if ((result & 1) == 0 /* Specialize.Specialize */)
1214 token.value = result >> 1;
1215 else
1216 token.extended = result >> 1;
1217 break;
1218 }
1219 }
1220 }
1221 else {
1222 token.value = 0 /* Term.Err */;
1223 token.end = this.stream.clipPos(start + 1);
1224 }
1225 }
1226 putAction(action, token, end, index) {
1227 // Don't add duplicate actions
1228 for (let i = 0; i < index; i += 3)
1229 if (this.actions[i] == action)
1230 return index;
1231 this.actions[index++] = action;
1232 this.actions[index++] = token;
1233 this.actions[index++] = end;
1234 return index;
1235 }
1236 addActions(stack, token, end, index) {
1237 let { state } = stack, { parser } = stack.p, { data } = parser;
1238 for (let set = 0; set < 2; set++) {
1239 for (let i = parser.stateSlot(state, set ? 2 /* ParseState.Skip */ : 1 /* ParseState.Actions */);; i += 3) {
1240 if (data[i] == 65535 /* Seq.End */) {
1241 if (data[i + 1] == 1 /* Seq.Next */) {
1242 i = pair(data, i + 2);
1243 }
1244 else {
1245 if (index == 0 && data[i + 1] == 2 /* Seq.Other */)
1246 index = this.putAction(pair(data, i + 2), token, end, index);
1247 break;
1248 }
1249 }
1250 if (data[i] == token)
1251 index = this.putAction(pair(data, i + 1), token, end, index);
1252 }
1253 }
1254 return index;
1255 }
1256}
1257class Parse {
1258 constructor(parser, input, fragments, ranges) {
1259 this.parser = parser;
1260 this.input = input;
1261 this.ranges = ranges;
1262 this.recovering = 0;
1263 this.nextStackID = 0x2654; // ♔, ♕, ♖, ♗, ♘, ♙, ♠, ♡, ♢, ♣, ♤, ♥, ♦, ♧
1264 this.minStackPos = 0;
1265 this.reused = [];
1266 this.stoppedAt = null;
1267 this.lastBigReductionStart = -1;
1268 this.lastBigReductionSize = 0;
1269 this.bigReductionCount = 0;
1270 this.stream = new InputStream(input, ranges);
1271 this.tokens = new TokenCache(parser, this.stream);
1272 this.topTerm = parser.top[1];
1273 let { from } = ranges[0];
1274 this.stacks = [Stack.start(this, parser.top[0], from)];
1275 this.fragments = fragments.length && this.stream.end - from > parser.bufferLength * 4
1276 ? new FragmentCursor(fragments, parser.nodeSet) : null;
1277 }
1278 get parsedPos() {
1279 return this.minStackPos;
1280 }
1281 // Move the parser forward. This will process all parse stacks at
1282 // `this.pos` and try to advance them to a further position. If no
1283 // stack for such a position is found, it'll start error-recovery.
1284 //
1285 // When the parse is finished, this will return a syntax tree. When
1286 // not, it returns `null`.
1287 advance() {
1288 let stacks = this.stacks, pos = this.minStackPos;
1289 // This will hold stacks beyond `pos`.
1290 let newStacks = this.stacks = [];
1291 let stopped, stoppedTokens;
1292 // If a large amount of reductions happened with the same start
1293 // position, force the stack out of that production in order to
1294 // avoid creating a tree too deep to recurse through.
1295 // (This is an ugly kludge, because unfortunately there is no
1296 // straightforward, cheap way to check for this happening, due to
1297 // the history of reductions only being available in an
1298 // expensive-to-access format in the stack buffers.)
1299 if (this.bigReductionCount > 300 /* Rec.MaxLeftAssociativeReductionCount */ && stacks.length == 1) {
1300 let [s] = stacks;
1301 while (s.forceReduce() && s.stack.length && s.stack[s.stack.length - 2] >= this.lastBigReductionStart) { }
1302 this.bigReductionCount = this.lastBigReductionSize = 0;
1303 }
1304 // Keep advancing any stacks at `pos` until they either move
1305 // forward or can't be advanced. Gather stacks that can't be
1306 // advanced further in `stopped`.
1307 for (let i = 0; i < stacks.length; i++) {
1308 let stack = stacks[i];
1309 for (;;) {
1310 this.tokens.mainToken = null;
1311 if (stack.pos > pos) {
1312 newStacks.push(stack);
1313 }
1314 else if (this.advanceStack(stack, newStacks, stacks)) {
1315 continue;
1316 }
1317 else {
1318 if (!stopped) {
1319 stopped = [];
1320 stoppedTokens = [];
1321 }
1322 stopped.push(stack);
1323 let tok = this.tokens.getMainToken(stack);
1324 stoppedTokens.push(tok.value, tok.end);
1325 }
1326 break;
1327 }
1328 }
1329 if (!newStacks.length) {
1330 let finished = stopped && findFinished(stopped);
1331 if (finished) {
1332 if (verbose)
1333 console.log("Finish with " + this.stackID(finished));
1334 return this.stackToTree(finished);
1335 }
1336 if (this.parser.strict) {
1337 if (verbose && stopped)
1338 console.log("Stuck with token " + (this.tokens.mainToken ? this.parser.getName(this.tokens.mainToken.value) : "none"));
1339 throw new SyntaxError("No parse at " + pos);
1340 }
1341 if (!this.recovering)
1342 this.recovering = 5 /* Rec.Distance */;
1343 }
1344 if (this.recovering && stopped) {
1345 let finished = this.stoppedAt != null && stopped[0].pos > this.stoppedAt ? stopped[0]
1346 : this.runRecovery(stopped, stoppedTokens, newStacks);
1347 if (finished) {
1348 if (verbose)
1349 console.log("Force-finish " + this.stackID(finished));
1350 return this.stackToTree(finished.forceAll());
1351 }
1352 }
1353 if (this.recovering) {
1354 let maxRemaining = this.recovering == 1 ? 1 : this.recovering * 3 /* Rec.MaxRemainingPerStep */;
1355 if (newStacks.length > maxRemaining) {
1356 newStacks.sort((a, b) => b.score - a.score);
1357 while (newStacks.length > maxRemaining)
1358 newStacks.pop();
1359 }
1360 if (newStacks.some(s => s.reducePos > pos))
1361 this.recovering--;
1362 }
1363 else if (newStacks.length > 1) {
1364 // Prune stacks that are in the same state, or that have been
1365 // running without splitting for a while, to avoid getting stuck
1366 // with multiple successful stacks running endlessly on.
1367 outer: for (let i = 0; i < newStacks.length - 1; i++) {
1368 let stack = newStacks[i];
1369 for (let j = i + 1; j < newStacks.length; j++) {
1370 let other = newStacks[j];
1371 if (stack.sameState(other) ||
1372 stack.buffer.length > 500 /* Rec.MinBufferLengthPrune */ && other.buffer.length > 500 /* Rec.MinBufferLengthPrune */) {
1373 if (((stack.score - other.score) || (stack.buffer.length - other.buffer.length)) > 0) {
1374 newStacks.splice(j--, 1);
1375 }
1376 else {
1377 newStacks.splice(i--, 1);
1378 continue outer;
1379 }
1380 }
1381 }
1382 }
1383 if (newStacks.length > 12 /* Rec.MaxStackCount */) {
1384 newStacks.sort((a, b) => b.score - a.score);
1385 newStacks.splice(12 /* Rec.MaxStackCount */, newStacks.length - 12 /* Rec.MaxStackCount */);
1386 }
1387 }
1388 this.minStackPos = newStacks[0].pos;
1389 for (let i = 1; i < newStacks.length; i++)
1390 if (newStacks[i].pos < this.minStackPos)
1391 this.minStackPos = newStacks[i].pos;
1392 return null;
1393 }
1394 stopAt(pos) {
1395 if (this.stoppedAt != null && this.stoppedAt < pos)
1396 throw new RangeError("Can't move stoppedAt forward");
1397 this.stoppedAt = pos;
1398 }
1399 // Returns an updated version of the given stack, or null if the
1400 // stack can't advance normally. When `split` and `stacks` are
1401 // given, stacks split off by ambiguous operations will be pushed to
1402 // `split`, or added to `stacks` if they move `pos` forward.
1403 advanceStack(stack, stacks, split) {
1404 let start = stack.pos, { parser } = this;
1405 let base = verbose ? this.stackID(stack) + " -> " : "";
1406 if (this.stoppedAt != null && start > this.stoppedAt)
1407 return stack.forceReduce() ? stack : null;
1408 if (this.fragments) {
1409 let strictCx = stack.curContext && stack.curContext.tracker.strict, cxHash = strictCx ? stack.curContext.hash : 0;
1410 for (let cached = this.fragments.nodeAt(start); cached;) {
1411 let match = this.parser.nodeSet.types[cached.type.id] == cached.type ? parser.getGoto(stack.state, cached.type.id) : -1;
1412 if (match > -1 && cached.length && (!strictCx || (cached.prop(common.NodeProp.contextHash) || 0) == cxHash)) {
1413 stack.useNode(cached, match);
1414 if (verbose)
1415 console.log(base + this.stackID(stack) + ` (via reuse of ${parser.getName(cached.type.id)})`);
1416 return true;
1417 }
1418 if (!(cached instanceof common.Tree) || cached.children.length == 0 || cached.positions[0] > 0)
1419 break;
1420 let inner = cached.children[0];
1421 if (inner instanceof common.Tree && cached.positions[0] == 0)
1422 cached = inner;
1423 else
1424 break;
1425 }
1426 }
1427 let defaultReduce = parser.stateSlot(stack.state, 4 /* ParseState.DefaultReduce */);
1428 if (defaultReduce > 0) {
1429 stack.reduce(defaultReduce);
1430 if (verbose)
1431 console.log(base + this.stackID(stack) + ` (via always-reduce ${parser.getName(defaultReduce & 65535 /* Action.ValueMask */)})`);
1432 return true;
1433 }
1434 if (stack.stack.length >= 8400 /* Rec.CutDepth */) {
1435 while (stack.stack.length > 6000 /* Rec.CutTo */ && stack.forceReduce()) { }
1436 }
1437 let actions = this.tokens.getActions(stack);
1438 for (let i = 0; i < actions.length;) {
1439 let action = actions[i++], term = actions[i++], end = actions[i++];
1440 let last = i == actions.length || !split;
1441 let localStack = last ? stack : stack.split();
1442 let main = this.tokens.mainToken;
1443 localStack.apply(action, term, main ? main.start : localStack.pos, end);
1444 if (verbose)
1445 console.log(base + this.stackID(localStack) + ` (via ${(action & 65536 /* Action.ReduceFlag */) == 0 ? "shift"
1446 : `reduce of ${parser.getName(action & 65535 /* Action.ValueMask */)}`} for ${parser.getName(term)} @ ${start}${localStack == stack ? "" : ", split"})`);
1447 if (last)
1448 return true;
1449 else if (localStack.pos > start)
1450 stacks.push(localStack);
1451 else
1452 split.push(localStack);
1453 }
1454 return false;
1455 }
1456 // Advance a given stack forward as far as it will go. Returns the
1457 // (possibly updated) stack if it got stuck, or null if it moved
1458 // forward and was given to `pushStackDedup`.
1459 advanceFully(stack, newStacks) {
1460 let pos = stack.pos;
1461 for (;;) {
1462 if (!this.advanceStack(stack, null, null))
1463 return false;
1464 if (stack.pos > pos) {
1465 pushStackDedup(stack, newStacks);
1466 return true;
1467 }
1468 }
1469 }
1470 runRecovery(stacks, tokens, newStacks) {
1471 let finished = null, restarted = false;
1472 for (let i = 0; i < stacks.length; i++) {
1473 let stack = stacks[i], token = tokens[i << 1], tokenEnd = tokens[(i << 1) + 1];
1474 let base = verbose ? this.stackID(stack) + " -> " : "";
1475 if (stack.deadEnd) {
1476 if (restarted)
1477 continue;
1478 restarted = true;
1479 stack.restart();
1480 if (verbose)
1481 console.log(base + this.stackID(stack) + " (restarted)");
1482 let done = this.advanceFully(stack, newStacks);
1483 if (done)
1484 continue;
1485 }
1486 let force = stack.split(), forceBase = base;
1487 for (let j = 0; j < 10 /* Rec.ForceReduceLimit */ && force.forceReduce(); j++) {
1488 if (verbose)
1489 console.log(forceBase + this.stackID(force) + " (via force-reduce)");
1490 let done = this.advanceFully(force, newStacks);
1491 if (done)
1492 break;
1493 if (verbose)
1494 forceBase = this.stackID(force) + " -> ";
1495 }
1496 for (let insert of stack.recoverByInsert(token)) {
1497 if (verbose)
1498 console.log(base + this.stackID(insert) + " (via recover-insert)");
1499 this.advanceFully(insert, newStacks);
1500 }
1501 if (this.stream.end > stack.pos) {
1502 if (tokenEnd == stack.pos) {
1503 tokenEnd++;
1504 token = 0 /* Term.Err */;
1505 }
1506 stack.recoverByDelete(token, tokenEnd);
1507 if (verbose)
1508 console.log(base + this.stackID(stack) + ` (via recover-delete ${this.parser.getName(token)})`);
1509 pushStackDedup(stack, newStacks);
1510 }
1511 else if (!finished || finished.score < force.score) {
1512 finished = force;
1513 }
1514 }
1515 return finished;
1516 }
1517 // Convert the stack's buffer to a syntax tree.
1518 stackToTree(stack) {
1519 stack.close();
1520 return common.Tree.build({ buffer: StackBufferCursor.create(stack),
1521 nodeSet: this.parser.nodeSet,
1522 topID: this.topTerm,
1523 maxBufferLength: this.parser.bufferLength,
1524 reused: this.reused,
1525 start: this.ranges[0].from,
1526 length: stack.pos - this.ranges[0].from,
1527 minRepeatType: this.parser.minRepeatTerm });
1528 }
1529 stackID(stack) {
1530 let id = (stackIDs || (stackIDs = new WeakMap)).get(stack);
1531 if (!id)
1532 stackIDs.set(stack, id = String.fromCodePoint(this.nextStackID++));
1533 return id + stack;
1534 }
1535}
1536function pushStackDedup(stack, newStacks) {
1537 for (let i = 0; i < newStacks.length; i++) {
1538 let other = newStacks[i];
1539 if (other.pos == stack.pos && other.sameState(stack)) {
1540 if (newStacks[i].score < stack.score)
1541 newStacks[i] = stack;
1542 return;
1543 }
1544 }
1545 newStacks.push(stack);
1546}
1547class Dialect {
1548 constructor(source, flags, disabled) {
1549 this.source = source;
1550 this.flags = flags;
1551 this.disabled = disabled;
1552 }
1553 allows(term) { return !this.disabled || this.disabled[term] == 0; }
1554}
1555const id = x => x;
1556/**
1557Context trackers are used to track stateful context (such as
1558indentation in the Python grammar, or parent elements in the XML
1559grammar) needed by external tokenizers. You declare them in a
1560grammar file as `@context exportName from "module"`.
1561
1562Context values should be immutable, and can be updated (replaced)
1563on shift or reduce actions.
1564
1565The export used in a `@context` declaration should be of this
1566type.
1567*/
1568class ContextTracker {
1569 /**
1570 Define a context tracker.
1571 */
1572 constructor(spec) {
1573 this.start = spec.start;
1574 this.shift = spec.shift || id;
1575 this.reduce = spec.reduce || id;
1576 this.reuse = spec.reuse || id;
1577 this.hash = spec.hash || (() => 0);
1578 this.strict = spec.strict !== false;
1579 }
1580}
1581/**
1582Holds the parse tables for a given grammar, as generated by
1583`lezer-generator`, and provides [methods](#common.Parser) to parse
1584content with.
1585*/
1586class LRParser extends common.Parser {
1587 /**
1588 @internal
1589 */
1590 constructor(spec) {
1591 super();
1592 /**
1593 @internal
1594 */
1595 this.wrappers = [];
1596 if (spec.version != 14 /* File.Version */)
1597 throw new RangeError(`Parser version (${spec.version}) doesn't match runtime version (${14 /* File.Version */})`);
1598 let nodeNames = spec.nodeNames.split(" ");
1599 this.minRepeatTerm = nodeNames.length;
1600 for (let i = 0; i < spec.repeatNodeCount; i++)
1601 nodeNames.push("");
1602 let topTerms = Object.keys(spec.topRules).map(r => spec.topRules[r][1]);
1603 let nodeProps = [];
1604 for (let i = 0; i < nodeNames.length; i++)
1605 nodeProps.push([]);
1606 function setProp(nodeID, prop, value) {
1607 nodeProps[nodeID].push([prop, prop.deserialize(String(value))]);
1608 }
1609 if (spec.nodeProps)
1610 for (let propSpec of spec.nodeProps) {
1611 let prop = propSpec[0];
1612 if (typeof prop == "string")
1613 prop = common.NodeProp[prop];
1614 for (let i = 1; i < propSpec.length;) {
1615 let next = propSpec[i++];
1616 if (next >= 0) {
1617 setProp(next, prop, propSpec[i++]);
1618 }
1619 else {
1620 let value = propSpec[i + -next];
1621 for (let j = -next; j > 0; j--)
1622 setProp(propSpec[i++], prop, value);
1623 i++;
1624 }
1625 }
1626 }
1627 this.nodeSet = new common.NodeSet(nodeNames.map((name, i) => common.NodeType.define({
1628 name: i >= this.minRepeatTerm ? undefined : name,
1629 id: i,
1630 props: nodeProps[i],
1631 top: topTerms.indexOf(i) > -1,
1632 error: i == 0,
1633 skipped: spec.skippedNodes && spec.skippedNodes.indexOf(i) > -1
1634 })));
1635 if (spec.propSources)
1636 this.nodeSet = this.nodeSet.extend(...spec.propSources);
1637 this.strict = false;
1638 this.bufferLength = common.DefaultBufferLength;
1639 let tokenArray = decodeArray(spec.tokenData);
1640 this.context = spec.context;
1641 this.specializerSpecs = spec.specialized || [];
1642 this.specialized = new Uint16Array(this.specializerSpecs.length);
1643 for (let i = 0; i < this.specializerSpecs.length; i++)
1644 this.specialized[i] = this.specializerSpecs[i].term;
1645 this.specializers = this.specializerSpecs.map(getSpecializer);
1646 this.states = decodeArray(spec.states, Uint32Array);
1647 this.data = decodeArray(spec.stateData);
1648 this.goto = decodeArray(spec.goto);
1649 this.maxTerm = spec.maxTerm;
1650 this.tokenizers = spec.tokenizers.map(value => typeof value == "number" ? new TokenGroup(tokenArray, value) : value);
1651 this.topRules = spec.topRules;
1652 this.dialects = spec.dialects || {};
1653 this.dynamicPrecedences = spec.dynamicPrecedences || null;
1654 this.tokenPrecTable = spec.tokenPrec;
1655 this.termNames = spec.termNames || null;
1656 this.maxNode = this.nodeSet.types.length - 1;
1657 this.dialect = this.parseDialect();
1658 this.top = this.topRules[Object.keys(this.topRules)[0]];
1659 }
1660 createParse(input, fragments, ranges) {
1661 let parse = new Parse(this, input, fragments, ranges);
1662 for (let w of this.wrappers)
1663 parse = w(parse, input, fragments, ranges);
1664 return parse;
1665 }
1666 /**
1667 Get a goto table entry @internal
1668 */
1669 getGoto(state, term, loose = false) {
1670 let table = this.goto;
1671 if (term >= table[0])
1672 return -1;
1673 for (let pos = table[term + 1];;) {
1674 let groupTag = table[pos++], last = groupTag & 1;
1675 let target = table[pos++];
1676 if (last && loose)
1677 return target;
1678 for (let end = pos + (groupTag >> 1); pos < end; pos++)
1679 if (table[pos] == state)
1680 return target;
1681 if (last)
1682 return -1;
1683 }
1684 }
1685 /**
1686 Check if this state has an action for a given terminal @internal
1687 */
1688 hasAction(state, terminal) {
1689 let data = this.data;
1690 for (let set = 0; set < 2; set++) {
1691 for (let i = this.stateSlot(state, set ? 2 /* ParseState.Skip */ : 1 /* ParseState.Actions */), next;; i += 3) {
1692 if ((next = data[i]) == 65535 /* Seq.End */) {
1693 if (data[i + 1] == 1 /* Seq.Next */)
1694 next = data[i = pair(data, i + 2)];
1695 else if (data[i + 1] == 2 /* Seq.Other */)
1696 return pair(data, i + 2);
1697 else
1698 break;
1699 }
1700 if (next == terminal || next == 0 /* Term.Err */)
1701 return pair(data, i + 1);
1702 }
1703 }
1704 return 0;
1705 }
1706 /**
1707 @internal
1708 */
1709 stateSlot(state, slot) {
1710 return this.states[(state * 6 /* ParseState.Size */) + slot];
1711 }
1712 /**
1713 @internal
1714 */
1715 stateFlag(state, flag) {
1716 return (this.stateSlot(state, 0 /* ParseState.Flags */) & flag) > 0;
1717 }
1718 /**
1719 @internal
1720 */
1721 validAction(state, action) {
1722 return !!this.allActions(state, a => a == action ? true : null);
1723 }
1724 /**
1725 @internal
1726 */
1727 allActions(state, action) {
1728 let deflt = this.stateSlot(state, 4 /* ParseState.DefaultReduce */);
1729 let result = deflt ? action(deflt) : undefined;
1730 for (let i = this.stateSlot(state, 1 /* ParseState.Actions */); result == null; i += 3) {
1731 if (this.data[i] == 65535 /* Seq.End */) {
1732 if (this.data[i + 1] == 1 /* Seq.Next */)
1733 i = pair(this.data, i + 2);
1734 else
1735 break;
1736 }
1737 result = action(pair(this.data, i + 1));
1738 }
1739 return result;
1740 }
1741 /**
1742 Get the states that can follow this one through shift actions or
1743 goto jumps. @internal
1744 */
1745 nextStates(state) {
1746 let result = [];
1747 for (let i = this.stateSlot(state, 1 /* ParseState.Actions */);; i += 3) {
1748 if (this.data[i] == 65535 /* Seq.End */) {
1749 if (this.data[i + 1] == 1 /* Seq.Next */)
1750 i = pair(this.data, i + 2);
1751 else
1752 break;
1753 }
1754 if ((this.data[i + 2] & (65536 /* Action.ReduceFlag */ >> 16)) == 0) {
1755 let value = this.data[i + 1];
1756 if (!result.some((v, i) => (i & 1) && v == value))
1757 result.push(this.data[i], value);
1758 }
1759 }
1760 return result;
1761 }
1762 /**
1763 Configure the parser. Returns a new parser instance that has the
1764 given settings modified. Settings not provided in `config` are
1765 kept from the original parser.
1766 */
1767 configure(config) {
1768 // Hideous reflection-based kludge to make it easy to create a
1769 // slightly modified copy of a parser.
1770 let copy = Object.assign(Object.create(LRParser.prototype), this);
1771 if (config.props)
1772 copy.nodeSet = this.nodeSet.extend(...config.props);
1773 if (config.top) {
1774 let info = this.topRules[config.top];
1775 if (!info)
1776 throw new RangeError(`Invalid top rule name ${config.top}`);
1777 copy.top = info;
1778 }
1779 if (config.tokenizers)
1780 copy.tokenizers = this.tokenizers.map(t => {
1781 let found = config.tokenizers.find(r => r.from == t);
1782 return found ? found.to : t;
1783 });
1784 if (config.specializers) {
1785 copy.specializers = this.specializers.slice();
1786 copy.specializerSpecs = this.specializerSpecs.map((s, i) => {
1787 let found = config.specializers.find(r => r.from == s.external);
1788 if (!found)
1789 return s;
1790 let spec = Object.assign(Object.assign({}, s), { external: found.to });
1791 copy.specializers[i] = getSpecializer(spec);
1792 return spec;
1793 });
1794 }
1795 if (config.contextTracker)
1796 copy.context = config.contextTracker;
1797 if (config.dialect)
1798 copy.dialect = this.parseDialect(config.dialect);
1799 if (config.strict != null)
1800 copy.strict = config.strict;
1801 if (config.wrap)
1802 copy.wrappers = copy.wrappers.concat(config.wrap);
1803 if (config.bufferLength != null)
1804 copy.bufferLength = config.bufferLength;
1805 return copy;
1806 }
1807 /**
1808 Tells you whether any [parse wrappers](#lr.ParserConfig.wrap)
1809 are registered for this parser.
1810 */
1811 hasWrappers() {
1812 return this.wrappers.length > 0;
1813 }
1814 /**
1815 Returns the name associated with a given term. This will only
1816 work for all terms when the parser was generated with the
1817 `--names` option. By default, only the names of tagged terms are
1818 stored.
1819 */
1820 getName(term) {
1821 return this.termNames ? this.termNames[term] : String(term <= this.maxNode && this.nodeSet.types[term].name || term);
1822 }
1823 /**
1824 The eof term id is always allocated directly after the node
1825 types. @internal
1826 */
1827 get eofTerm() { return this.maxNode + 1; }
1828 /**
1829 The type of top node produced by the parser.
1830 */
1831 get topNode() { return this.nodeSet.types[this.top[1]]; }
1832 /**
1833 @internal
1834 */
1835 dynamicPrecedence(term) {
1836 let prec = this.dynamicPrecedences;
1837 return prec == null ? 0 : prec[term] || 0;
1838 }
1839 /**
1840 @internal
1841 */
1842 parseDialect(dialect) {
1843 let values = Object.keys(this.dialects), flags = values.map(() => false);
1844 if (dialect)
1845 for (let part of dialect.split(" ")) {
1846 let id = values.indexOf(part);
1847 if (id >= 0)
1848 flags[id] = true;
1849 }
1850 let disabled = null;
1851 for (let i = 0; i < values.length; i++)
1852 if (!flags[i]) {
1853 for (let j = this.dialects[values[i]], id; (id = this.data[j++]) != 65535 /* Seq.End */;)
1854 (disabled || (disabled = new Uint8Array(this.maxTerm + 1)))[id] = 1;
1855 }
1856 return new Dialect(dialect, flags, disabled);
1857 }
1858 /**
1859 Used by the output of the parser generator. Not available to
1860 user code. @hide
1861 */
1862 static deserialize(spec) {
1863 return new LRParser(spec);
1864 }
1865}
1866function pair(data, off) { return data[off] | (data[off + 1] << 16); }
1867function findFinished(stacks) {
1868 let best = null;
1869 for (let stack of stacks) {
1870 let stopped = stack.p.stoppedAt;
1871 if ((stack.pos == stack.p.stream.end || stopped != null && stack.pos > stopped) &&
1872 stack.p.parser.stateFlag(stack.state, 2 /* StateFlag.Accepting */) &&
1873 (!best || best.score < stack.score))
1874 best = stack;
1875 }
1876 return best;
1877}
1878function getSpecializer(spec) {
1879 if (spec.external) {
1880 let mask = spec.extend ? 1 /* Specialize.Extend */ : 0 /* Specialize.Specialize */;
1881 return (value, stack) => (spec.external(value, stack) << 1) | mask;
1882 }
1883 return spec.get;
1884}
1885
1886exports.ContextTracker = ContextTracker;
1887exports.ExternalTokenizer = ExternalTokenizer;
1888exports.InputStream = InputStream;
1889exports.LRParser = LRParser;
1890exports.LocalTokenGroup = LocalTokenGroup;
1891exports.Stack = Stack;