Skip to main content

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}