tabnas/context.rs
1// Copyright (c) 2013-2026 Richard Rodger, MIT License
2
3use crate::error::TabnasError;
4use crate::options::Options;
5use crate::rule::{Rule, RuleSnapshot};
6use crate::token::Token;
7use crate::value::unwrap_arc;
8use crate::value::Value;
9use indexmap::IndexMap;
10use std::cell::RefCell;
11use std::collections::VecDeque;
12use std::fmt;
13use std::rc::Rc;
14use std::sync::Arc;
15
16#[derive(Debug, Clone, PartialEq, Eq)]
17pub struct ActionError {
18 pub code: String,
19 pub detail: String,
20}
21
22impl ActionError {
23 pub fn new(code: impl Into<String>, detail: impl Into<String>) -> Self {
24 Self {
25 code: code.into(),
26 detail: detail.into(),
27 }
28 }
29}
30
31impl fmt::Display for ActionError {
32 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
33 formatter.write_str(&self.detail)
34 }
35}
36
37impl std::error::Error for ActionError {}
38
39/// Read-only identity and grammar summary for the owning parser instance.
40/// Callbacks that need to mutate grammar receive `&mut Tabnas` during plugin
41/// installation; parse-time callbacks use this stable per-parse snapshot.
42#[derive(Debug, Clone, Default, PartialEq, Eq)]
43pub struct InstanceInfo {
44 pub id: String,
45 pub parent_id: Option<String>,
46 pub tag: String,
47 pub plugins: Vec<String>,
48 pub rule_names: Vec<String>,
49}
50
51/// Typed form of TypeScript's `parent_ctx` parse argument. Custom metadata
52/// and plugin state are deep-merged into the new Context, while errors and
53/// parser-owned cursor/rule fields always start fresh for each parse.
54#[derive(Debug, Clone, Default, PartialEq)]
55pub struct ContextSeed {
56 pub meta: Option<Value>,
57 pub u: IndexMap<String, Value>,
58}
59
60impl From<ActionError> for TabnasError {
61 fn from(action_error: ActionError) -> Self {
62 let mut error = TabnasError::new(action_error.code, "", "", 0, 1, 1);
63 error.detail = action_error.detail;
64 error
65 }
66}
67
68/// Drop the frames that left the stack, snapshot the frames that arrived.
69fn follow_stack(frames: &mut Vec<Rc<RuleSnapshot>>, stack: &[Rule]) {
70 frames.truncate(stack.len());
71 for rule in &stack[frames.len()..] {
72 frames.push(rule.snapshot());
73 }
74}
75
76/// Debug-only equality between a retained snapshot and the rule it describes.
77/// It covers the state a snapshot copies by value; `node` is shared through
78/// an `Rc`, and the rule links are snapshots in their own right, so neither
79/// can drift.
80///
81/// Values go through `deep_equal` rather than `==`. A grammar may put a NaN
82/// on a rule, `Value` derives `PartialEq`, and NaN is not equal to itself,
83/// so `==` would report an unchanged frame as drifted and panic a debug
84/// build over a legitimate parse.
85#[cfg(debug_assertions)]
86fn same_rule(snapshot: &crate::RuleSnapshot, rule: &Rule) -> bool {
87 snapshot.i == rule.i
88 && snapshot.d == rule.d
89 // `child_node` is deliberately absent: it lives on the rule
90 // rather than the snapshot, so there is nothing to compare.
91 && snapshot.name == rule.name
92 && snapshot.state == rule.state
93 && snapshot.need == rule.need
94 && snapshot.bo == rule.bo
95 && snapshot.ao == rule.ao
96 && snapshot.bc == rule.bc
97 && snapshot.ac == rule.ac
98 && snapshot.next_rule_name == rule.next_rule_name
99 && snapshot.n == rule.n
100 && same_values(&snapshot.u, &rule.u)
101 && same_values(&snapshot.k, &rule.k)
102 && same_tokens(&snapshot.o, &rule.o)
103 && same_tokens(&snapshot.c, &rule.c)
104 && same_link(&snapshot.parent_rule, &rule.parent_rule)
105 && same_link(&snapshot.child_rule, &rule.child_rule)
106 && same_link(&snapshot.prev_rule, &rule.prev_rule)
107 && same_link(&snapshot.next_rule, &rule.next_rule)
108}
109
110#[cfg(debug_assertions)]
111fn same_values(
112 left: &std::collections::HashMap<String, Value>,
113 right: &std::collections::HashMap<String, Value>,
114) -> bool {
115 left.len() == right.len()
116 && left
117 .iter()
118 .all(|(key, value)| right.get(key).is_some_and(|other| value.deep_equal(other)))
119}
120
121/// `val_fn` is a callback and `ignored` is trivia the lexer attaches once;
122/// neither is state the parse loop revises, so the comparison stops at the
123/// fields a moved frame would show.
124#[cfg(debug_assertions)]
125fn same_tokens(left: &[Token], right: &[Token]) -> bool {
126 left.len() == right.len()
127 && left.iter().zip(right).all(|(left, right)| {
128 left.name == right.name
129 && left.tin == right.tin
130 && left.src == right.src
131 && left.len == right.len
132 && left.site == right.site
133 && left.err == right.err
134 && left.why == right.why
135 && left.val.deep_equal(&right.val)
136 && same_values(left.use_data(), right.use_data())
137 })
138}
139
140/// The rule links are snapshots themselves, so identity is the question
141/// worth asking: a relinked frame points at a different snapshot, and
142/// comparing the pointers says so without walking the ancestry.
143#[cfg(debug_assertions)]
144fn same_link(
145 snapshot: &Option<std::rc::Rc<crate::RuleSnapshot>>,
146 rule: &Option<std::rc::Rc<crate::RuleSnapshot>>,
147) -> bool {
148 match (snapshot, rule) {
149 (None, None) => true,
150 (Some(left), Some(right)) => std::rc::Rc::ptr_eq(left, right),
151 _ => false,
152 }
153}
154
155/// Mutable state for one parse run.
156///
157/// Consumed tokens are retained in `v` so actions can mark and rewind the
158/// parser without asking the lexer to scan source text a second time. Marks
159/// are absolute (`v_abs`), so bounded-history eviction does not change their
160/// meaning.
161#[derive(Debug)]
162pub struct Context {
163 /// Zero-based rule-loop iteration currently being processed.
164 pub iteration: usize,
165 /// Full source text for plugin callbacks and diagnostics.
166 pub source: String,
167 /// Caller-supplied per-parse metadata.
168 pub meta: Value,
169 /// Custom per-parse plugin data bag.
170 pub u: IndexMap<String, Value>,
171 /// Errors recorded so far during recovery.
172 pub errs: Vec<TabnasError>,
173 /// Resolved options for this parse. Shared with the parser and its
174 /// lexer, which is sound because nothing writes to them once a parse
175 /// has started. Each parse still gets the options as they stood when
176 /// it began, so
177 /// callbacks cannot mutate the shared parser configuration.
178 pub options: Arc<Options>,
179 /// Owning instance identity, installed plugins, and grammar names.
180 pub instance: InstanceInfo,
181 /// Snapshot of the current rule and its ancestor stack. The live rule is
182 /// still supplied separately to callbacks so mutation remains explicit.
183 pub rule: Option<Rc<RuleSnapshot>>,
184 pub rule_stack: Vec<Rc<RuleSnapshot>>,
185 /// The same stack as the engine wrote it, kept only where debug
186 /// assertions are on. `rule_stack` is public and a callback may write to
187 /// it; this one is what the engine checks itself against.
188 #[cfg(debug_assertions)]
189 rule_stack_shadow: Vec<Rc<RuleSnapshot>>,
190 /// Retained consumed-token history, oldest first.
191 /// A `VecDeque` because the history is trimmed from its front once
192 /// it outgrows `options.rewind.history`. As a `Vec` that trim moved
193 /// every retained token, which amortised to one `Token` memmove per
194 /// token consumed -- 1.8% of a parse, for a buffer nothing reads
195 /// unless a rewind happens.
196 pub v: VecDeque<Token>,
197 /// Absolute number of tokens consumed minus tokens rewound.
198 pub v_abs: usize,
199 /// Current lookahead buffer, oldest first.
200 pub t: Vec<Token>,
201 replay: VecDeque<Token>,
202 history_limit: Option<usize>,
203 root: Option<Rc<RefCell<Value>>>,
204 pub(crate) recover_at: Option<usize>,
205 pub(crate) recover_si: Option<usize>,
206 pub(crate) bad_to: Option<usize>,
207 pub(crate) bad_error: Option<usize>,
208 /// The stack depth of the rule that opened each open probe,
209 /// innermost last: a grammar that parses ahead and then rewinds to a
210 /// mark opens one with [`Context::probe_open`] and closes it with
211 /// [`Context::probe_close`]. TS: `ctx.probeOwners`.
212 probe_owners: Vec<usize>,
213 /// Whether the current pass opened or closed a probe; the parse
214 /// loop reads and clears it once per pass (`probe_take`).
215 probe_pass: bool,
216}
217
218impl Context {
219 pub(crate) fn new(
220 history_limit: Option<usize>,
221 source: impl Into<String>,
222 meta: Value,
223 options: Arc<Options>,
224 instance: InstanceInfo,
225 ) -> Self {
226 Self {
227 iteration: 0,
228 source: source.into(),
229 meta,
230 u: IndexMap::new(),
231 errs: Vec::new(),
232 options,
233 instance,
234 rule: None,
235 rule_stack: Vec::new(),
236 #[cfg(debug_assertions)]
237 rule_stack_shadow: Vec::new(),
238 v: VecDeque::new(),
239 v_abs: 0,
240 t: Vec::with_capacity(8),
241 replay: VecDeque::new(),
242 history_limit,
243 root: None,
244 recover_at: None,
245 recover_si: None,
246 bad_to: None,
247 bad_error: None,
248 probe_owners: Vec::new(),
249 probe_pass: false,
250 }
251 }
252
253 /// Open a probe in `rule`: the grammar is about to parse ahead and
254 /// then rewind to a mark, so the passes until the matching
255 /// [`Context::probe_close`] are speculative, never the document's.
256 /// `@probeInit$` calls it, as must any grammar that probes with
257 /// actions of its own. Every [`crate::RuleDone`] reports `probe` for
258 /// a pass made while a probe is open, the pass that opens it and the
259 /// pass that closes it included. The probe belongs to the rule's
260 /// stack depth, so that error recovery can close it when it abandons
261 /// the rule ([`Context::probe_abandon`]). TS: `ctx.probeOpen(rule)`.
262 pub fn probe_open(&mut self, rule: &RuleSnapshot) {
263 self.probe_owners.push(rule.d);
264 self.probe_pass = true;
265 }
266
267 /// Close the innermost open probe (`@probeDecide$` calls it, after
268 /// its rewind). The pass that closes it is still reported as the
269 /// probe's. TS: `ctx.probeClose()`.
270 pub fn probe_close(&mut self) {
271 self.probe_owners.pop();
272 self.probe_pass = true;
273 }
274
275 /// How many probes are open. TS: `ctx.probeDepth()`.
276 pub fn probe_depth(&self) -> usize {
277 self.probe_owners.len()
278 }
279
280 /// Error recovery abandons `rule`, popping it without the pass that
281 /// would close the probes it, or a rule above it, opened: close them
282 /// here, or every later pass would be reported as a probe's. Returns
283 /// whether the abandoned rule's synthesized close is a probe's. TS:
284 /// `ctx.probeAbandon(rule)`.
285 pub fn probe_abandon(&mut self, rule: &RuleSnapshot) -> bool {
286 let probe = !self.probe_owners.is_empty();
287 while self
288 .probe_owners
289 .last()
290 .is_some_and(|depth| rule.d <= *depth)
291 {
292 self.probe_owners.pop();
293 }
294 probe
295 }
296
297 /// Whether the pass that just ran opened or closed a probe, or ends
298 /// inside one, clearing the per-pass flag for the next one. The parse
299 /// loop calls it once after every pass, subscribed or not; a pass that
300 /// began inside a probe is the probe's too, which the loop adds, since
301 /// recovery may close the probe before the pass is reported. TS:
302 /// `ctx.probeTake()`.
303 pub fn probe_take(&mut self) -> bool {
304 let probe = !self.probe_owners.is_empty() || self.probe_pass;
305 self.probe_pass = false;
306 probe
307 }
308
309 /// Record the current absolute parse position for a later rewind.
310 pub fn mark(&self) -> usize {
311 self.v_abs
312 }
313
314 /// Most recently consumed token.
315 pub fn v1(&self) -> Option<&Token> {
316 self.v.back()
317 }
318
319 /// Token consumed immediately before `v1`.
320 pub fn v2(&self) -> Option<&Token> {
321 self.v.get(self.v.len().wrapping_sub(2))
322 }
323
324 pub fn t0(&self) -> Option<&Token> {
325 self.t.first()
326 }
327
328 pub fn t1(&self) -> Option<&Token> {
329 self.t.get(1)
330 }
331
332 pub fn set_t0(&mut self, token: Token) {
333 if self.t.is_empty() {
334 self.t.push(token);
335 } else {
336 self.t[0] = token;
337 }
338 }
339
340 pub fn set_t1(&mut self, token: Token) {
341 while self.t.len() < 2 {
342 self.t.push(Token::no_token());
343 }
344 self.t[1] = token;
345 }
346
347 pub fn set_v1(&mut self, token: Token) {
348 if let Some(last) = self.v.back_mut() {
349 *last = token;
350 } else {
351 self.v.push_back(token);
352 }
353 }
354
355 pub fn set_v2(&mut self, token: Token) {
356 match self.v.len() {
357 0 => self.v.push_back(token),
358 1 => self.v.push_front(token),
359 length => self.v[length - 2] = token,
360 }
361 }
362
363 pub fn root(&self) -> Option<Value> {
364 self.root.as_ref().map(|root| root.borrow().clone())
365 }
366
367 pub(crate) fn set_root(&mut self, root: Rc<RefCell<Value>>) {
368 self.root = Some(root);
369 }
370
371 pub(crate) fn set_active(&mut self, rule: &Rule, stack: &[Rule]) {
372 self.set_rule(rule);
373 self.sync_rule_stack(stack);
374 }
375
376 /// Bring `rule_stack` into step with the parse loop's ancestor stack.
377 ///
378 /// Rebuilding every entry here, which is what this used to do, costs one
379 /// deep snapshot per ancestor per loop iteration. A grammar whose rules
380 /// nest with the input pays that on every step, so a recogniser like the
381 /// even-palindrome one runs in O(n^2) where the TypeScript and Go engines
382 /// run in O(n) — they publish the stack as live rule handles and copy
383 /// nothing. Measured on a 16 KiB palindrome: 155 s before, 0.25 s after.
384 ///
385 /// A frame is only ever mutated while it is the rule the loop is working
386 /// on, and that rule is not in `stack` — it is passed separately and
387 /// re-snapshotted every call. So a frame's snapshot, taken when the frame
388 /// was pushed, still describes it for as long as it stays buried.
389 ///
390 /// This is how the mature engines carry it. TypeScript writes
391 /// `ctx.rs[ctx.rsI++] = rule` and reads back `ctx.rs[--ctx.rsI]`; Go does
392 /// the same through `ctx.RS` and `ctx.RSI`. Neither rebuilds, and both
393 /// leave the stack as reachable from a callback as this one is. Rust was
394 /// the outlier, and being the outlier is what cost it the extra order.
395 ///
396 /// `rule_stack` is a public field, so a callback can write to it, and a
397 /// write that keeps the length is carried forward from here rather than
398 /// overwritten. That matches what a callback writing to `ctx.rs` gets
399 /// from the other two engines. It is also why the assertion below reads
400 /// `rule_stack_shadow` and not `rule_stack`: the claim being checked is
401 /// about the engine's own bookkeeping, and a debug build must not panic
402 /// because a callback reached into a field the engine publishes.
403 ///
404 /// That a buried frame does not move is a claim about the whole parse
405 /// loop, recovery paths included, so it is checked rather than asserted
406 /// in prose: the assertion compares every retained frame against the live
407 /// rule it describes, on every call, and the test suite runs with debug
408 /// assertions on.
409 fn sync_rule_stack(&mut self, stack: &[Rule]) {
410 follow_stack(&mut self.rule_stack, stack);
411 #[cfg(debug_assertions)]
412 {
413 follow_stack(&mut self.rule_stack_shadow, stack);
414 debug_assert!(
415 self.rule_stack_shadow
416 .iter()
417 .zip(stack)
418 .all(|(snapshot, rule)| same_rule(snapshot, rule)),
419 "the incremental rule stack drifted from the live parse stack"
420 );
421 }
422 }
423
424 pub(crate) fn set_rule(&mut self, rule: &Rule) {
425 self.rule = Some(rule.snapshot());
426 }
427
428 pub(crate) fn apply_seed(&mut self, seed: &ContextSeed) {
429 if let Some(meta) = &seed.meta {
430 self.meta = merge_seed_value(self.meta.clone(), meta.clone());
431 }
432 for (key, value) in &seed.u {
433 let previous = self.u.shift_remove(key).unwrap_or(Value::Undefined);
434 self.u
435 .insert(key.clone(), merge_seed_value(previous, value.clone()));
436 }
437 self.errs.clear();
438 }
439
440 /// Replay every token consumed since `mark`.
441 ///
442 /// Already-fetched lookahead remains behind the rewound tokens. An error
443 /// means the requested mark has fallen outside the retained history
444 /// window; callers can increase `options.rewind.history` or select
445 /// unbounded history.
446 pub fn rewind(&mut self, mark: usize) -> Result<(), ActionError> {
447 let Some(count) = self.v_abs.checked_sub(mark) else {
448 return Ok(());
449 };
450 if count == 0 {
451 return Ok(());
452 }
453 if count > self.v.len() {
454 return Err(ActionError::new(
455 "internal",
456 format!(
457 "tabnas: ctx.rewind target {mark} is outside the retained history window \
458 (oldest mark available is {}, current is {}); increase \
459 options.rewind.history",
460 self.v_abs - self.v.len(),
461 self.v_abs,
462 ),
463 ));
464 }
465
466 let retained_at = self.v.len() - count;
467 let rewound = self.v.split_off(retained_at);
468 let lookahead = std::mem::take(&mut self.t);
469 let pending = std::mem::take(&mut self.replay);
470 self.replay = rewound
471 .into_iter()
472 .chain(lookahead)
473 .chain(pending)
474 .collect();
475 self.v_abs -= count;
476 Ok(())
477 }
478
479 pub(crate) fn record_consumed(&mut self, count: usize) {
480 if count == 0 {
481 return;
482 }
483 let count = count.min(self.t.len());
484 self.v.extend(self.t.drain(0..count));
485 self.v_abs += count;
486
487 if let Some(limit) = self.history_limit {
488 if self.v.len() > 2 * limit {
489 let remove = self.v.len() - limit;
490 self.v.drain(0..remove);
491 }
492 }
493 }
494
495 /// Where the oldest token the parser holds starts: its lookahead's,
496 /// the tokens a rewind replays, and its consumed history, which a
497 /// rewind may replay and a re-cut read again. `None` when it holds
498 /// none. A window keeps the source from there on.
499 ///
500 /// The answer matters only down to `floor`, the least a window drops
501 /// to: the first token found to start before it settles that nothing
502 /// is dropped, and ends the scan. The consumed history comes first,
503 /// oldest first, so its first token usually does. Walking every token
504 /// held on every fetch cost a parse from a reader that keeps a long
505 /// history O(n × history) (#334), where TypeScript's and Go's scans
506 /// stop at the floor alike.
507 pub(crate) fn oldest_held(&self, floor: usize) -> Option<usize> {
508 let mut oldest: Option<usize> = None;
509 for token in self.v.iter().chain(self.replay.iter()).chain(self.t.iter()) {
510 let pos = token.site.pos;
511 if oldest.is_none_or(|oldest| pos < oldest) {
512 oldest = Some(pos);
513 if pos < floor {
514 break;
515 }
516 }
517 }
518 oldest
519 }
520
521 pub(crate) fn next_replay(&mut self) -> Option<Token> {
522 self.replay.pop_front()
523 }
524
525 pub(crate) fn take_replay(&mut self) -> VecDeque<Token> {
526 std::mem::take(&mut self.replay)
527 }
528
529 pub(crate) fn restore_replay(&mut self, replay: VecDeque<Token>) {
530 self.replay = replay;
531 }
532}
533
534fn merge_seed_value(base: Value, overlay: Value) -> Value {
535 match (base, overlay) {
536 (base, Value::Undefined) => base,
537 (Value::Object(base), Value::Object(overlay)) => {
538 let mut base = unwrap_arc(base);
539 for (key, value) in unwrap_arc(overlay) {
540 let previous = base.shift_remove(&key).unwrap_or(Value::Undefined);
541 base.insert(key, merge_seed_value(previous, value));
542 }
543 Value::object(base)
544 }
545 (_, overlay) => overlay,
546 }
547}
548
549#[cfg(test)]
550mod probe_tests {
551 use super::*;
552
553 fn context() -> Context {
554 let options = Arc::new(Options::default());
555 Context::new(
556 options.rewind.history,
557 "",
558 Value::Undefined,
559 Arc::clone(&options),
560 InstanceInfo::default(),
561 )
562 }
563
564 fn rule_at(d: usize) -> crate::Rule {
565 let mut rule = crate::Rule::new("r", Value::Undefined);
566 rule.d = d;
567 rule
568 }
569
570 // The twin of the TypeScript and Go nesting tests: probes nest, the
571 // pass that opens or closes one is the probe's, and a close with
572 // nothing open does not underflow.
573 #[test]
574 fn probes_nest_and_flag_the_passes_that_open_and_close_them() {
575 let mut ctx = context();
576 assert!(!ctx.probe_take());
577 ctx.probe_open(&rule_at(2));
578 assert!(ctx.probe_take(), "the pass that opens a probe");
579 ctx.probe_open(&rule_at(4));
580 ctx.probe_close();
581 assert!(ctx.probe_take(), "still inside the outer probe");
582 ctx.probe_close();
583 assert_eq!(ctx.probe_depth(), 0);
584 assert!(ctx.probe_take(), "the pass that closes the outer probe");
585 assert!(!ctx.probe_take(), "the next pass is the document again");
586 ctx.probe_close();
587 assert_eq!(
588 ctx.probe_depth(),
589 0,
590 "an unmatched close does not underflow"
591 );
592 }
593
594 // Recovery abandoning a rule closes the probes it opened, and only
595 // those, and leaves nothing to leak onto the next pass.
596 #[test]
597 fn abandoning_a_rule_closes_its_probes_and_only_those() {
598 let mut ctx = context();
599 ctx.probe_open(&rule_at(2));
600 ctx.probe_open(&rule_at(4));
601 ctx.probe_take();
602 // (abandoned depth, a probe's close, probes left open)
603 for (d, probe, depth) in [(5, true, 2), (4, true, 1), (3, true, 1), (2, true, 0)] {
604 assert_eq!(ctx.probe_abandon(&rule_at(d)), probe, "abandon d={d}");
605 assert_eq!(ctx.probe_depth(), depth, "abandon d={d}");
606 }
607 assert!(!ctx.probe_take(), "the next pass is the document again");
608 assert!(!ctx.probe_abandon(&rule_at(1)), "outside every probe");
609 }
610}