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