tabnas-parser 0.12.20

A dynamic JSON parser that isn't strict and can be customized.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
// Copyright (c) 2013-2026 Richard Rodger, MIT License

use crate::error::TabnasError;
use crate::options::Options;
use crate::rule::{Rule, RuleSnapshot};
use crate::token::Token;
use crate::value::unwrap_arc;
use crate::value::Value;
use indexmap::IndexMap;
use std::cell::RefCell;
use std::collections::VecDeque;
use std::fmt;
use std::rc::Rc;
use std::sync::Arc;

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ActionError {
    pub code: String,
    pub detail: String,
}

impl ActionError {
    pub fn new(code: impl Into<String>, detail: impl Into<String>) -> Self {
        Self {
            code: code.into(),
            detail: detail.into(),
        }
    }
}

impl fmt::Display for ActionError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        formatter.write_str(&self.detail)
    }
}

impl std::error::Error for ActionError {}

/// Read-only identity and grammar summary for the owning parser instance.
/// Callbacks that need to mutate grammar receive `&mut Tabnas` during plugin
/// installation; parse-time callbacks use this stable per-parse snapshot.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct InstanceInfo {
    pub id: String,
    pub parent_id: Option<String>,
    pub tag: String,
    pub plugins: Vec<String>,
    pub rule_names: Vec<String>,
}

/// Typed form of TypeScript's `parent_ctx` parse argument. Custom metadata
/// and plugin state are deep-merged into the new Context, while errors and
/// parser-owned cursor/rule fields always start fresh for each parse.
#[derive(Debug, Clone, Default, PartialEq)]
pub struct ContextSeed {
    pub meta: Option<Value>,
    pub u: IndexMap<String, Value>,
}

impl From<ActionError> for TabnasError {
    fn from(action_error: ActionError) -> Self {
        let mut error = TabnasError::new(action_error.code, "", "", 0, 1, 1);
        error.detail = action_error.detail;
        error
    }
}

/// Drop the frames that left the stack, snapshot the frames that arrived.
fn follow_stack(frames: &mut Vec<Rc<RuleSnapshot>>, stack: &[Rule]) {
    frames.truncate(stack.len());
    for rule in &stack[frames.len()..] {
        frames.push(rule.snapshot());
    }
}

/// Debug-only equality between a retained snapshot and the rule it describes.
/// It covers the state a snapshot copies by value; `node` is shared through
/// an `Rc`, and the rule links are snapshots in their own right, so neither
/// can drift.
///
/// Values go through `deep_equal` rather than `==`. A grammar may put a NaN
/// on a rule, `Value` derives `PartialEq`, and NaN is not equal to itself,
/// so `==` would report an unchanged frame as drifted and panic a debug
/// build over a legitimate parse.
#[cfg(debug_assertions)]
fn same_rule(snapshot: &crate::RuleSnapshot, rule: &Rule) -> bool {
    snapshot.i == rule.i
        && snapshot.d == rule.d
        // `child_node` is deliberately absent: it lives on the rule
        // rather than the snapshot, so there is nothing to compare.
        && snapshot.name == rule.name
        && snapshot.state == rule.state
        && snapshot.need == rule.need
        && snapshot.bo == rule.bo
        && snapshot.ao == rule.ao
        && snapshot.bc == rule.bc
        && snapshot.ac == rule.ac
        && snapshot.next_rule_name == rule.next_rule_name
        && snapshot.n == rule.n
        && same_values(&snapshot.u, &rule.u)
        && same_values(&snapshot.k, &rule.k)
        && same_tokens(&snapshot.o, &rule.o)
        && same_tokens(&snapshot.c, &rule.c)
        && same_link(&snapshot.parent_rule, &rule.parent_rule)
        && same_link(&snapshot.child_rule, &rule.child_rule)
        && same_link(&snapshot.prev_rule, &rule.prev_rule)
        && same_link(&snapshot.next_rule, &rule.next_rule)
}

#[cfg(debug_assertions)]
fn same_values(
    left: &std::collections::HashMap<String, Value>,
    right: &std::collections::HashMap<String, Value>,
) -> bool {
    left.len() == right.len()
        && left
            .iter()
            .all(|(key, value)| right.get(key).is_some_and(|other| value.deep_equal(other)))
}

/// `val_fn` is a callback and `ignored` is trivia the lexer attaches once;
/// neither is state the parse loop revises, so the comparison stops at the
/// fields a moved frame would show.
#[cfg(debug_assertions)]
fn same_tokens(left: &[Token], right: &[Token]) -> bool {
    left.len() == right.len()
        && left.iter().zip(right).all(|(left, right)| {
            left.name == right.name
                && left.tin == right.tin
                && left.src == right.src
                && left.len == right.len
                && left.site == right.site
                && left.err == right.err
                && left.why == right.why
                && left.val.deep_equal(&right.val)
                && same_values(left.use_data(), right.use_data())
        })
}

/// The rule links are snapshots themselves, so identity is the question
/// worth asking: a relinked frame points at a different snapshot, and
/// comparing the pointers says so without walking the ancestry.
#[cfg(debug_assertions)]
fn same_link(
    snapshot: &Option<std::rc::Rc<crate::RuleSnapshot>>,
    rule: &Option<std::rc::Rc<crate::RuleSnapshot>>,
) -> bool {
    match (snapshot, rule) {
        (None, None) => true,
        (Some(left), Some(right)) => std::rc::Rc::ptr_eq(left, right),
        _ => false,
    }
}

/// Mutable state for one parse run.
///
/// Consumed tokens are retained in `v` so actions can mark and rewind the
/// parser without asking the lexer to scan source text a second time. Marks
/// are absolute (`v_abs`), so bounded-history eviction does not change their
/// meaning.
#[derive(Debug)]
pub struct Context {
    /// Zero-based rule-loop iteration currently being processed.
    pub iteration: usize,
    /// Full source text for plugin callbacks and diagnostics.
    pub source: String,
    /// Caller-supplied per-parse metadata.
    pub meta: Value,
    /// Custom per-parse plugin data bag.
    pub u: IndexMap<String, Value>,
    /// Errors recorded so far during recovery.
    pub errs: Vec<TabnasError>,
    /// Resolved options for this parse. Shared with the parser and its
    /// lexer, which is sound because nothing writes to them once a parse
    /// has started. Each parse still gets the options as they stood when
    /// it began, so
    /// callbacks cannot mutate the shared parser configuration.
    pub options: Arc<Options>,
    /// Owning instance identity, installed plugins, and grammar names.
    pub instance: InstanceInfo,
    /// Snapshot of the current rule and its ancestor stack. The live rule is
    /// still supplied separately to callbacks so mutation remains explicit.
    pub rule: Option<Rc<RuleSnapshot>>,
    pub rule_stack: Vec<Rc<RuleSnapshot>>,
    /// The same stack as the engine wrote it, kept only where debug
    /// assertions are on. `rule_stack` is public and a callback may write to
    /// it; this one is what the engine checks itself against.
    #[cfg(debug_assertions)]
    rule_stack_shadow: Vec<Rc<RuleSnapshot>>,
    /// Retained consumed-token history, oldest first.
    /// A `VecDeque` because the history is trimmed from its front once
    /// it outgrows `options.rewind.history`. As a `Vec` that trim moved
    /// every retained token, which amortised to one `Token` memmove per
    /// token consumed -- 1.8% of a parse, for a buffer nothing reads
    /// unless a rewind happens.
    pub v: VecDeque<Token>,
    /// Absolute number of tokens consumed minus tokens rewound.
    pub v_abs: usize,
    /// Current lookahead buffer, oldest first.
    pub t: Vec<Token>,
    replay: VecDeque<Token>,
    history_limit: Option<usize>,
    root: Option<Rc<RefCell<Value>>>,
    pub(crate) recover_at: Option<usize>,
    pub(crate) recover_si: Option<usize>,
    pub(crate) bad_to: Option<usize>,
    pub(crate) bad_error: Option<usize>,
    /// The stack depth of the rule that opened each open probe,
    /// innermost last: a grammar that parses ahead and then rewinds to a
    /// mark opens one with [`Context::probe_open`] and closes it with
    /// [`Context::probe_close`]. TS: `ctx.probeOwners`.
    probe_owners: Vec<usize>,
    /// Whether the current pass opened or closed a probe; the parse
    /// loop reads and clears it once per pass (`probe_take`).
    probe_pass: bool,
}

impl Context {
    pub(crate) fn new(
        history_limit: Option<usize>,
        source: impl Into<String>,
        meta: Value,
        options: Arc<Options>,
        instance: InstanceInfo,
    ) -> Self {
        Self {
            iteration: 0,
            source: source.into(),
            meta,
            u: IndexMap::new(),
            errs: Vec::new(),
            options,
            instance,
            rule: None,
            rule_stack: Vec::new(),
            #[cfg(debug_assertions)]
            rule_stack_shadow: Vec::new(),
            v: VecDeque::new(),
            v_abs: 0,
            t: Vec::with_capacity(8),
            replay: VecDeque::new(),
            history_limit,
            root: None,
            recover_at: None,
            recover_si: None,
            bad_to: None,
            bad_error: None,
            probe_owners: Vec::new(),
            probe_pass: false,
        }
    }

    /// Open a probe in `rule`: the grammar is about to parse ahead and
    /// then rewind to a mark, so the passes until the matching
    /// [`Context::probe_close`] are speculative, never the document's.
    /// `@probeInit$` calls it, as must any grammar that probes with
    /// actions of its own. Every [`crate::RuleDone`] reports `probe` for
    /// a pass made while a probe is open, the pass that opens it and the
    /// pass that closes it included. The probe belongs to the rule's
    /// stack depth, so that error recovery can close it when it abandons
    /// the rule ([`Context::probe_abandon`]). TS: `ctx.probeOpen(rule)`.
    pub fn probe_open(&mut self, rule: &RuleSnapshot) {
        self.probe_owners.push(rule.d);
        self.probe_pass = true;
    }

    /// Close the innermost open probe (`@probeDecide$` calls it, after
    /// its rewind). The pass that closes it is still reported as the
    /// probe's. TS: `ctx.probeClose()`.
    pub fn probe_close(&mut self) {
        self.probe_owners.pop();
        self.probe_pass = true;
    }

    /// How many probes are open. TS: `ctx.probeDepth()`.
    pub fn probe_depth(&self) -> usize {
        self.probe_owners.len()
    }

    /// Error recovery abandons `rule`, popping it without the pass that
    /// would close the probes it, or a rule above it, opened: close them
    /// here, or every later pass would be reported as a probe's. Returns
    /// whether the abandoned rule's synthesized close is a probe's. TS:
    /// `ctx.probeAbandon(rule)`.
    pub fn probe_abandon(&mut self, rule: &RuleSnapshot) -> bool {
        let probe = !self.probe_owners.is_empty();
        while self
            .probe_owners
            .last()
            .is_some_and(|depth| rule.d <= *depth)
        {
            self.probe_owners.pop();
        }
        probe
    }

    /// Whether the pass that just ran opened or closed a probe, or ends
    /// inside one, clearing the per-pass flag for the next one. The parse
    /// loop calls it once after every pass, subscribed or not; a pass that
    /// began inside a probe is the probe's too, which the loop adds, since
    /// recovery may close the probe before the pass is reported. TS:
    /// `ctx.probeTake()`.
    pub fn probe_take(&mut self) -> bool {
        let probe = !self.probe_owners.is_empty() || self.probe_pass;
        self.probe_pass = false;
        probe
    }

    /// Record the current absolute parse position for a later rewind.
    pub fn mark(&self) -> usize {
        self.v_abs
    }

    /// Most recently consumed token.
    pub fn v1(&self) -> Option<&Token> {
        self.v.back()
    }

    /// Token consumed immediately before `v1`.
    pub fn v2(&self) -> Option<&Token> {
        self.v.get(self.v.len().wrapping_sub(2))
    }

    pub fn t0(&self) -> Option<&Token> {
        self.t.first()
    }

    pub fn t1(&self) -> Option<&Token> {
        self.t.get(1)
    }

    pub fn set_t0(&mut self, token: Token) {
        if self.t.is_empty() {
            self.t.push(token);
        } else {
            self.t[0] = token;
        }
    }

    pub fn set_t1(&mut self, token: Token) {
        while self.t.len() < 2 {
            self.t.push(Token::no_token());
        }
        self.t[1] = token;
    }

    pub fn set_v1(&mut self, token: Token) {
        if let Some(last) = self.v.back_mut() {
            *last = token;
        } else {
            self.v.push_back(token);
        }
    }

    pub fn set_v2(&mut self, token: Token) {
        match self.v.len() {
            0 => self.v.push_back(token),
            1 => self.v.push_front(token),
            length => self.v[length - 2] = token,
        }
    }

    pub fn root(&self) -> Option<Value> {
        self.root.as_ref().map(|root| root.borrow().clone())
    }

    pub(crate) fn set_root(&mut self, root: Rc<RefCell<Value>>) {
        self.root = Some(root);
    }

    pub(crate) fn set_active(&mut self, rule: &Rule, stack: &[Rule]) {
        self.set_rule(rule);
        self.sync_rule_stack(stack);
    }

    /// Bring `rule_stack` into step with the parse loop's ancestor stack.
    ///
    /// Rebuilding every entry here, which is what this used to do, costs one
    /// deep snapshot per ancestor per loop iteration. A grammar whose rules
    /// nest with the input pays that on every step, so a recogniser like the
    /// even-palindrome one runs in O(n^2) where the TypeScript and Go engines
    /// run in O(n) — they publish the stack as live rule handles and copy
    /// nothing. Measured on a 16 KiB palindrome: 155 s before, 0.25 s after.
    ///
    /// A frame is only ever mutated while it is the rule the loop is working
    /// on, and that rule is not in `stack` — it is passed separately and
    /// re-snapshotted every call. So a frame's snapshot, taken when the frame
    /// was pushed, still describes it for as long as it stays buried.
    ///
    /// This is how the mature engines carry it. TypeScript writes
    /// `ctx.rs[ctx.rsI++] = rule` and reads back `ctx.rs[--ctx.rsI]`; Go does
    /// the same through `ctx.RS` and `ctx.RSI`. Neither rebuilds, and both
    /// leave the stack as reachable from a callback as this one is. Rust was
    /// the outlier, and being the outlier is what cost it the extra order.
    ///
    /// `rule_stack` is a public field, so a callback can write to it, and a
    /// write that keeps the length is carried forward from here rather than
    /// overwritten. That matches what a callback writing to `ctx.rs` gets
    /// from the other two engines. It is also why the assertion below reads
    /// `rule_stack_shadow` and not `rule_stack`: the claim being checked is
    /// about the engine's own bookkeeping, and a debug build must not panic
    /// because a callback reached into a field the engine publishes.
    ///
    /// That a buried frame does not move is a claim about the whole parse
    /// loop, recovery paths included, so it is checked rather than asserted
    /// in prose: the assertion compares every retained frame against the live
    /// rule it describes, on every call, and the test suite runs with debug
    /// assertions on.
    fn sync_rule_stack(&mut self, stack: &[Rule]) {
        follow_stack(&mut self.rule_stack, stack);
        #[cfg(debug_assertions)]
        {
            follow_stack(&mut self.rule_stack_shadow, stack);
            debug_assert!(
                self.rule_stack_shadow
                    .iter()
                    .zip(stack)
                    .all(|(snapshot, rule)| same_rule(snapshot, rule)),
                "the incremental rule stack drifted from the live parse stack"
            );
        }
    }

    pub(crate) fn set_rule(&mut self, rule: &Rule) {
        self.rule = Some(rule.snapshot());
    }

    pub(crate) fn apply_seed(&mut self, seed: &ContextSeed) {
        if let Some(meta) = &seed.meta {
            self.meta = merge_seed_value(self.meta.clone(), meta.clone());
        }
        for (key, value) in &seed.u {
            let previous = self.u.shift_remove(key).unwrap_or(Value::Undefined);
            self.u
                .insert(key.clone(), merge_seed_value(previous, value.clone()));
        }
        self.errs.clear();
    }

    /// Replay every token consumed since `mark`.
    ///
    /// Already-fetched lookahead remains behind the rewound tokens. An error
    /// means the requested mark has fallen outside the retained history
    /// window; callers can increase `options.rewind.history` or select
    /// unbounded history.
    pub fn rewind(&mut self, mark: usize) -> Result<(), ActionError> {
        let Some(count) = self.v_abs.checked_sub(mark) else {
            return Ok(());
        };
        if count == 0 {
            return Ok(());
        }
        if count > self.v.len() {
            return Err(ActionError::new(
                "internal",
                format!(
                    "tabnas: ctx.rewind target {mark} is outside the retained history window \
                 (oldest mark available is {}, current is {}); increase \
                 options.rewind.history",
                    self.v_abs - self.v.len(),
                    self.v_abs,
                ),
            ));
        }

        let retained_at = self.v.len() - count;
        let rewound = self.v.split_off(retained_at);
        let lookahead = std::mem::take(&mut self.t);
        let pending = std::mem::take(&mut self.replay);
        self.replay = rewound
            .into_iter()
            .chain(lookahead)
            .chain(pending)
            .collect();
        self.v_abs -= count;
        Ok(())
    }

    pub(crate) fn record_consumed(&mut self, count: usize) {
        if count == 0 {
            return;
        }
        let count = count.min(self.t.len());
        self.v.extend(self.t.drain(0..count));
        self.v_abs += count;

        if let Some(limit) = self.history_limit {
            if self.v.len() > 2 * limit {
                let remove = self.v.len() - limit;
                self.v.drain(0..remove);
            }
        }
    }

    /// Where the oldest token the parser holds starts: its lookahead's,
    /// the tokens a rewind replays, and its consumed history, which a
    /// rewind may replay and a re-cut read again. `None` when it holds
    /// none. A window keeps the source from there on.
    ///
    /// The answer matters only down to `floor`, the least a window drops
    /// to: the first token found to start before it settles that nothing
    /// is dropped, and ends the scan. The consumed history comes first,
    /// oldest first, so its first token usually does. Walking every token
    /// held on every fetch cost a parse from a reader that keeps a long
    /// history O(n × history) (#334), where TypeScript's and Go's scans
    /// stop at the floor alike.
    pub(crate) fn oldest_held(&self, floor: usize) -> Option<usize> {
        let mut oldest: Option<usize> = None;
        for token in self.v.iter().chain(self.replay.iter()).chain(self.t.iter()) {
            let pos = token.site.pos;
            if oldest.is_none_or(|oldest| pos < oldest) {
                oldest = Some(pos);
                if pos < floor {
                    break;
                }
            }
        }
        oldest
    }

    pub(crate) fn next_replay(&mut self) -> Option<Token> {
        self.replay.pop_front()
    }

    pub(crate) fn take_replay(&mut self) -> VecDeque<Token> {
        std::mem::take(&mut self.replay)
    }

    pub(crate) fn restore_replay(&mut self, replay: VecDeque<Token>) {
        self.replay = replay;
    }
}

fn merge_seed_value(base: Value, overlay: Value) -> Value {
    match (base, overlay) {
        (base, Value::Undefined) => base,
        (Value::Object(base), Value::Object(overlay)) => {
            let mut base = unwrap_arc(base);
            for (key, value) in unwrap_arc(overlay) {
                let previous = base.shift_remove(&key).unwrap_or(Value::Undefined);
                base.insert(key, merge_seed_value(previous, value));
            }
            Value::object(base)
        }
        (_, overlay) => overlay,
    }
}

#[cfg(test)]
mod probe_tests {
    use super::*;

    fn context() -> Context {
        let options = Arc::new(Options::default());
        Context::new(
            options.rewind.history,
            "",
            Value::Undefined,
            Arc::clone(&options),
            InstanceInfo::default(),
        )
    }

    fn rule_at(d: usize) -> crate::Rule {
        let mut rule = crate::Rule::new("r", Value::Undefined);
        rule.d = d;
        rule
    }

    // The twin of the TypeScript and Go nesting tests: probes nest, the
    // pass that opens or closes one is the probe's, and a close with
    // nothing open does not underflow.
    #[test]
    fn probes_nest_and_flag_the_passes_that_open_and_close_them() {
        let mut ctx = context();
        assert!(!ctx.probe_take());
        ctx.probe_open(&rule_at(2));
        assert!(ctx.probe_take(), "the pass that opens a probe");
        ctx.probe_open(&rule_at(4));
        ctx.probe_close();
        assert!(ctx.probe_take(), "still inside the outer probe");
        ctx.probe_close();
        assert_eq!(ctx.probe_depth(), 0);
        assert!(ctx.probe_take(), "the pass that closes the outer probe");
        assert!(!ctx.probe_take(), "the next pass is the document again");
        ctx.probe_close();
        assert_eq!(
            ctx.probe_depth(),
            0,
            "an unmatched close does not underflow"
        );
    }

    // Recovery abandoning a rule closes the probes it opened, and only
    // those, and leaves nothing to leak onto the next pass.
    #[test]
    fn abandoning_a_rule_closes_its_probes_and_only_those() {
        let mut ctx = context();
        ctx.probe_open(&rule_at(2));
        ctx.probe_open(&rule_at(4));
        ctx.probe_take();
        // (abandoned depth, a probe's close, probes left open)
        for (d, probe, depth) in [(5, true, 2), (4, true, 1), (3, true, 1), (2, true, 0)] {
            assert_eq!(ctx.probe_abandon(&rule_at(d)), probe, "abandon d={d}");
            assert_eq!(ctx.probe_depth(), depth, "abandon d={d}");
        }
        assert!(!ctx.probe_take(), "the next pass is the document again");
        assert!(!ctx.probe_abandon(&rule_at(1)), "outside every probe");
    }
}