Skip to main content

tabnas/
rule.rs

1// Copyright (c) 2013-2026 Richard Rodger, MIT License
2
3use crate::token::{Tin, Token};
4use crate::value::Value;
5use crate::Lexer;
6use crate::{ActionError, Context, ContextAction};
7use std::cell::RefCell;
8use std::collections::HashMap;
9use std::fmt;
10use std::rc::Rc;
11use std::sync::Arc;
12
13/// Function-valued alternate condition. The candidate's matched tokens have
14/// already been copied onto `rule` when this callback runs.
15pub type AltCondition = Arc<dyn Fn(&mut Rule, &mut Context) -> bool + Send + Sync>;
16
17/// Canonical condition shape, including the effective match record being
18/// assembled for this candidate.
19pub type AltConditionWithMatch =
20    Arc<dyn Fn(&mut Rule, &mut Context, &mut AltMatch) -> bool + Send + Sync>;
21
22/// Condition with access to the live lexer. This is the imperative form used
23/// by plugins that perform controlled lookahead from a condition.
24pub type AltConditionWithLexer =
25    Arc<dyn for<'source> Fn(&mut Rule, &mut Context, &mut Lexer<'source>) -> bool + Send + Sync>;
26
27/// Complete canonical condition shape: the live effective match plus access
28/// to the lexer for bounded, plugin-controlled lookahead.
29pub type AltConditionWithLexerAndMatch = Arc<
30    dyn for<'source> Fn(&mut Rule, &mut Context, &mut AltMatch, &mut Lexer<'source>) -> bool
31        + Send
32        + Sync,
33>;
34
35/// Function-valued push/replace route.
36pub type AltNext = Arc<dyn Fn(&mut Rule, &mut Context) -> Option<String> + Send + Sync>;
37pub type AltNextWithMatch =
38    Arc<dyn Fn(&mut Rule, &mut Context, &mut AltMatch) -> Option<String> + Send + Sync>;
39
40/// Function-valued token backtrack count.
41pub type AltBack = Arc<dyn Fn(&mut Rule, &mut Context) -> usize + Send + Sync>;
42pub type AltBackWithMatch =
43    Arc<dyn Fn(&mut Rule, &mut Context, &mut AltMatch) -> usize + Send + Sync>;
44
45/// Function-valued alternate error. Returning a token rejects the alternate
46/// at its match site and uses the token's `err`/`why` field as the error code.
47pub type AltError = Arc<dyn Fn(&mut Rule, &mut Context) -> Option<Token> + Send + Sync>;
48pub type AltErrorWithMatch =
49    Arc<dyn Fn(&mut Rule, &mut Context, &mut AltMatch) -> Option<Token> + Send + Sync>;
50
51/// Post-match alternate modifier. It takes and returns the effective match so
52/// replacement is explicit rather than mutating shared grammar state.
53pub type AltModifier = Arc<dyn Fn(AltSpec, &mut Rule, &mut Context) -> AltSpec + Send + Sync>;
54
55/// Full canonical alternate modifier. `next` is the pre-routing next-rule
56/// view (`Some(current)` during open, `None` during close). The returned
57/// match is the one used for erroring, state mutation, action, and routing.
58pub type AltModifierWithMatch =
59    Arc<dyn Fn(AltMatch, &mut Rule, &mut Context, Option<&RuleSnapshot>) -> AltMatch + Send + Sync>;
60
61/// Full canonical alternate action. A returned error token aborts the pass;
62/// other returned tokens are ignored by the mature engine and should be
63/// expressed as `None` here.
64pub type AltAction = Arc<
65    dyn Fn(&mut Rule, &mut Context, &mut AltMatch) -> Result<Option<Token>, ActionError>
66        + Send
67        + Sync,
68>;
69
70#[derive(Clone)]
71pub enum AltActionBinding {
72    Named(String),
73    Context(ContextAction),
74    Matched(AltAction),
75}
76
77/// One executable action in its exact declaration position. The mature
78/// engines allow named function references and direct callbacks to be mixed;
79/// retaining this sequence avoids losing prepend/append order while keeping
80/// the serialized `a`/`bo`/`ao`/`bc`/`ac` lists available for inspection.
81#[derive(Clone)]
82pub enum ActionBinding {
83    Named(String),
84    Callback(ContextAction),
85    State(StateAction),
86}
87
88/// Canonical rule lifecycle callback (`bo`/`ao`/`bc`/`ac`). `next` is the
89/// rule selected for the following pass, or `None` for the no-rule sentinel;
90/// `out` is the previous handler's token result in the same phase.
91pub type StateAction = Arc<
92    dyn Fn(
93            &mut Rule,
94            &mut Context,
95            Option<&RuleSnapshot>,
96            Option<Token>,
97        ) -> Result<Option<Token>, ActionError>
98        + Send
99        + Sync,
100>;
101
102/// Effective result of matching one alternate. Dynamic error/routing/backtrack
103/// callbacks are resolved into this record before the modifier runs, matching
104/// TypeScript's `AltMatch` contract.
105#[derive(Clone, Default)]
106pub struct AltMatch {
107    pub p: Option<String>,
108    pub r: Option<String>,
109    pub b: usize,
110    pub n: HashMap<String, i32>,
111    pub u: HashMap<String, Value>,
112    pub k: HashMap<String, Value>,
113    pub g: Vec<String>,
114    /// The alternate's error token, boxed. A `Token` is 248 bytes and this
115    /// record is moved twice per rule step, so carrying one inline made
116    /// `AltMatch` 560 bytes of which 248 were an error almost no alternate
117    /// raises. The box costs an allocation only on the error path, which
118    /// is already the expensive one.
119    pub e: Option<Box<Token>>,
120    /// Canonical post-match modifier attached to the selected alternate.
121    /// It remains visible to the modifier itself and later actions even
122    /// though changing it after selection does not rerun the phase.
123    pub h: Option<AltModifierWithMatch>,
124    pub actions: Vec<AltActionBinding>,
125    pub action_configs: HashMap<String, Value>,
126}
127
128impl AltMatch {
129    /// Return the record to the state `AltMatch::default()` would give it,
130    /// without giving up the buffers it has already allocated.
131    ///
132    /// The parse loop keeps one record for the whole parse and resets it at
133    /// the head of each rule step, the shape TypeScript's `ctx._palt` has
134    /// (ts/src/rules.ts): building a fresh 320-byte record twice per step
135    /// and moving it twice more cost more than the nine fields are worth.
136    /// Every field an earlier step or a rejected alternate can leave behind
137    /// has to be cleared here -- a step can leave by the error path with
138    /// `e`, `p`, `r`, `b` and `g` still set -- and the maps and vectors are
139    /// cleared rather than replaced so the next step writes into the
140    /// capacity the last one left.
141    pub(crate) fn reset(&mut self) {
142        self.p = None;
143        self.r = None;
144        self.b = 0;
145        self.e = None;
146        self.h = None;
147        if !self.n.is_empty() {
148            self.n.clear();
149        }
150        if !self.u.is_empty() {
151            self.u.clear();
152        }
153        if !self.k.is_empty() {
154            self.k.clear();
155        }
156        if !self.g.is_empty() {
157            self.g.clear();
158        }
159        if !self.actions.is_empty() {
160            self.actions.clear();
161        }
162        if !self.action_configs.is_empty() {
163            self.action_configs.clear();
164        }
165    }
166}
167
168#[derive(Debug, Clone, Copy, PartialEq, Eq)]
169pub enum RuleState {
170    Open,
171    Close,
172}
173
174#[derive(Debug, Clone, PartialEq)]
175pub struct RuleDoneAlt {
176    pub b: usize,
177    pub g: Vec<String>,
178    pub p: String,
179    pub r: String,
180    pub err: Option<Token>,
181}
182
183#[derive(Debug, Clone, PartialEq)]
184pub struct RuleDone {
185    /// Rule state before the completed pass.
186    pub state: RuleState,
187    /// `None` only when that state declared no alternatives.
188    pub alt: Option<RuleDoneAlt>,
189    /// True only for a close synthesized by recovery.
190    pub forced: bool,
191    /// True for a pass made while a probe is open
192    /// ([`crate::Context::probe_open`]): speculative work the grammar
193    /// rewinds, never the document's. The pass that opens the probe and
194    /// the one that closes it are included. TS: `done.probe`.
195    pub probe: bool,
196}
197
198#[derive(Debug, Clone, Copy, PartialEq, Eq)]
199pub enum CompareOp {
200    Eq,
201    Ne,
202    Lt,
203    Lte,
204    Gt,
205    Gte,
206    Exist,
207}
208
209#[derive(Debug, Clone, PartialEq)]
210pub struct Condition {
211    pub path: Vec<String>,
212    pub op: CompareOp,
213    pub value: Value,
214}
215
216#[derive(Clone, Default)]
217pub struct AltSpec {
218    pub s: Vec<Vec<Tin>>,
219    /// The token names each `s` slot was declared with, when the
220    /// alternate came from a serialized grammar; empty for an alternate
221    /// built from tins directly. A slot naming a token set (`#KEY`,
222    /// `#VAL`, a custom set) is resolved again against the instance's
223    /// options whenever the parser is rebuilt, so a set overridden after
224    /// the alternate was installed still reaches it, as in TypeScript and
225    /// Go (tabnas/parser#217).
226    pub s_names: Vec<Vec<String>>,
227    /// What `s_names` last resolved to, slot by slot. A slot whose `s`
228    /// no longer equals this was set by hand after the alternate was
229    /// installed, and that edit wins: the names are not applied over it.
230    pub s_bound: Vec<Vec<Tin>>,
231    pub p: Option<String>,
232    pub p_fn: Option<AltNext>,
233    pub p_match: Option<AltNextWithMatch>,
234    pub r: Option<String>,
235    pub r_fn: Option<AltNext>,
236    pub r_match: Option<AltNextWithMatch>,
237    pub b: usize,
238    pub b_fn: Option<AltBack>,
239    pub b_match: Option<AltBackWithMatch>,
240    pub a: Vec<String>,
241    /// Imperative actions installed directly by a native Rust plugin.
242    /// Named actions in `a` remain the serialized grammar representation;
243    /// `action_order` retains their exact interleaving with direct callbacks.
244    pub action_fns: Vec<ContextAction>,
245    pub action_order: Vec<AltActionBinding>,
246    pub matched_action_fns: Vec<AltAction>,
247    pub action_configs: HashMap<String, Value>,
248    pub c: Vec<Condition>,
249    pub c_ref: Option<String>,
250    pub c_fn: Option<AltCondition>,
251    pub c_match: Option<AltConditionWithMatch>,
252    pub c_lex: Option<AltConditionWithLexer>,
253    pub c_lex_match: Option<AltConditionWithLexerAndMatch>,
254    pub n: HashMap<String, i32>,
255    pub u: HashMap<String, Value>,
256    pub k: HashMap<String, Value>,
257    pub g: String,
258    pub h: Option<AltModifier>,
259    pub h_match: Option<AltModifierWithMatch>,
260    pub e: Option<AltError>,
261    pub e_match: Option<AltErrorWithMatch>,
262}
263
264impl AltSpec {
265    pub fn new() -> Self {
266        Self::default()
267    }
268}
269
270#[derive(Clone)]
271pub struct RuleSpec {
272    pub name: String,
273    pub open: Vec<AltSpec>,
274    pub close: Vec<AltSpec>,
275    pub bo: Vec<String>,
276    pub ao: Vec<String>,
277    pub bc: Vec<String>,
278    pub ac: Vec<String>,
279    /// Imperative lifecycle callbacks, parallel to the named serialized
280    /// callback lists above.
281    pub bo_fns: Vec<ContextAction>,
282    pub ao_fns: Vec<ContextAction>,
283    pub bc_fns: Vec<ContextAction>,
284    pub ac_fns: Vec<ContextAction>,
285    pub bo_state_fns: Vec<StateAction>,
286    pub ao_state_fns: Vec<StateAction>,
287    pub bc_state_fns: Vec<StateAction>,
288    pub ac_state_fns: Vec<StateAction>,
289    pub bo_order: Vec<ActionBinding>,
290    pub ao_order: Vec<ActionBinding>,
291    pub bc_order: Vec<ActionBinding>,
292    pub ac_order: Vec<ActionBinding>,
293}
294
295impl fmt::Debug for RuleSpec {
296    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
297        formatter
298            .debug_struct("RuleSpec")
299            .field("name", &self.name)
300            .field("open", &self.open.len())
301            .field("close", &self.close.len())
302            .field("bo", &self.bo.len())
303            .field("ao", &self.ao.len())
304            .field("bc", &self.bc.len())
305            .field("ac", &self.ac.len())
306            .finish_non_exhaustive()
307    }
308}
309
310impl RuleSpec {
311    pub fn new(name: impl Into<String>) -> Self {
312        RuleSpec {
313            name: name.into(),
314            open: Vec::new(),
315            close: Vec::new(),
316            bo: Vec::new(),
317            ao: Vec::new(),
318            bc: Vec::new(),
319            ac: Vec::new(),
320            bo_fns: Vec::new(),
321            ao_fns: Vec::new(),
322            bc_fns: Vec::new(),
323            ac_fns: Vec::new(),
324            bo_state_fns: Vec::new(),
325            ao_state_fns: Vec::new(),
326            bc_state_fns: Vec::new(),
327            ac_state_fns: Vec::new(),
328            bo_order: Vec::new(),
329            ao_order: Vec::new(),
330            bc_order: Vec::new(),
331            ac_order: Vec::new(),
332        }
333    }
334
335    /// Remove all alternates and lifecycle actions from this rule.
336    pub fn clear(&mut self) -> &mut Self {
337        self.open.clear();
338        self.close.clear();
339        self.clear_actions(&[]);
340        self
341    }
342
343    pub fn add_open(&mut self, alt: AltSpec) -> &mut Self {
344        self.open.push(alt);
345        self
346    }
347
348    pub fn prepend_open(&mut self, alt: AltSpec) -> &mut Self {
349        self.open.insert(0, alt);
350        self
351    }
352
353    pub fn add_close(&mut self, alt: AltSpec) -> &mut Self {
354        self.close.push(alt);
355        self
356    }
357
358    pub fn prepend_close(&mut self, alt: AltSpec) -> &mut Self {
359        self.close.insert(0, alt);
360        self
361    }
362
363    pub fn clear_open(&mut self) -> &mut Self {
364        self.open.clear();
365        self
366    }
367
368    pub fn clear_close(&mut self) -> &mut Self {
369        self.close.clear();
370        self
371    }
372
373    /// Delete then move entries using the same signed-index rules as the
374    /// serialized grammar `inject` object.
375    pub fn modify_open(&mut self, mods: &crate::utility::ListMods<AltSpec>) -> &mut Self {
376        self.open = crate::utility::modlist(std::mem::take(&mut self.open), Some(mods));
377        self
378    }
379
380    pub fn modify_close(&mut self, mods: &crate::utility::ListMods<AltSpec>) -> &mut Self {
381        self.close = crate::utility::modlist(std::mem::take(&mut self.close), Some(mods));
382        self
383    }
384
385    pub fn add_bo(
386        &mut self,
387        action: impl Fn(&mut Rule, &mut Context) + Send + Sync + 'static,
388    ) -> &mut Self {
389        prepare_order(
390            &self.bo,
391            &self.bo_fns,
392            &self.bo_state_fns,
393            &mut self.bo_order,
394        );
395        let action = infallible_action(action);
396        self.bo_fns.push(action.clone());
397        self.bo_order.push(ActionBinding::Callback(action));
398        self
399    }
400
401    pub fn prepend_bo(
402        &mut self,
403        action: impl Fn(&mut Rule, &mut Context) + Send + Sync + 'static,
404    ) -> &mut Self {
405        prepare_order(
406            &self.bo,
407            &self.bo_fns,
408            &self.bo_state_fns,
409            &mut self.bo_order,
410        );
411        let action = infallible_action(action);
412        self.bo_fns.insert(0, action.clone());
413        self.bo_order.insert(0, ActionBinding::Callback(action));
414        self
415    }
416
417    pub fn add_ao(
418        &mut self,
419        action: impl Fn(&mut Rule, &mut Context) + Send + Sync + 'static,
420    ) -> &mut Self {
421        prepare_order(
422            &self.ao,
423            &self.ao_fns,
424            &self.ao_state_fns,
425            &mut self.ao_order,
426        );
427        let action = infallible_action(action);
428        self.ao_fns.push(action.clone());
429        self.ao_order.push(ActionBinding::Callback(action));
430        self
431    }
432
433    pub fn prepend_ao(
434        &mut self,
435        action: impl Fn(&mut Rule, &mut Context) + Send + Sync + 'static,
436    ) -> &mut Self {
437        prepare_order(
438            &self.ao,
439            &self.ao_fns,
440            &self.ao_state_fns,
441            &mut self.ao_order,
442        );
443        let action = infallible_action(action);
444        self.ao_fns.insert(0, action.clone());
445        self.ao_order.insert(0, ActionBinding::Callback(action));
446        self
447    }
448
449    pub fn add_bc(
450        &mut self,
451        action: impl Fn(&mut Rule, &mut Context) + Send + Sync + 'static,
452    ) -> &mut Self {
453        prepare_order(
454            &self.bc,
455            &self.bc_fns,
456            &self.bc_state_fns,
457            &mut self.bc_order,
458        );
459        let action = infallible_action(action);
460        self.bc_fns.push(action.clone());
461        self.bc_order.push(ActionBinding::Callback(action));
462        self
463    }
464
465    pub fn prepend_bc(
466        &mut self,
467        action: impl Fn(&mut Rule, &mut Context) + Send + Sync + 'static,
468    ) -> &mut Self {
469        prepare_order(
470            &self.bc,
471            &self.bc_fns,
472            &self.bc_state_fns,
473            &mut self.bc_order,
474        );
475        let action = infallible_action(action);
476        self.bc_fns.insert(0, action.clone());
477        self.bc_order.insert(0, ActionBinding::Callback(action));
478        self
479    }
480
481    pub fn add_ac(
482        &mut self,
483        action: impl Fn(&mut Rule, &mut Context) + Send + Sync + 'static,
484    ) -> &mut Self {
485        prepare_order(
486            &self.ac,
487            &self.ac_fns,
488            &self.ac_state_fns,
489            &mut self.ac_order,
490        );
491        let action = infallible_action(action);
492        self.ac_fns.push(action.clone());
493        self.ac_order.push(ActionBinding::Callback(action));
494        self
495    }
496
497    pub fn prepend_ac(
498        &mut self,
499        action: impl Fn(&mut Rule, &mut Context) + Send + Sync + 'static,
500    ) -> &mut Self {
501        prepare_order(
502            &self.ac,
503            &self.ac_fns,
504            &self.ac_state_fns,
505            &mut self.ac_order,
506        );
507        let action = infallible_action(action);
508        self.ac_fns.insert(0, action.clone());
509        self.ac_order.insert(0, ActionBinding::Callback(action));
510        self
511    }
512
513    pub fn add_bo_result(&mut self, action: ContextAction) -> &mut Self {
514        prepare_order(
515            &self.bo,
516            &self.bo_fns,
517            &self.bo_state_fns,
518            &mut self.bo_order,
519        );
520        self.bo_fns.push(action.clone());
521        self.bo_order.push(ActionBinding::Callback(action));
522        self
523    }
524
525    pub fn add_ao_result(&mut self, action: ContextAction) -> &mut Self {
526        prepare_order(
527            &self.ao,
528            &self.ao_fns,
529            &self.ao_state_fns,
530            &mut self.ao_order,
531        );
532        self.ao_fns.push(action.clone());
533        self.ao_order.push(ActionBinding::Callback(action));
534        self
535    }
536
537    pub fn add_bc_result(&mut self, action: ContextAction) -> &mut Self {
538        prepare_order(
539            &self.bc,
540            &self.bc_fns,
541            &self.bc_state_fns,
542            &mut self.bc_order,
543        );
544        self.bc_fns.push(action.clone());
545        self.bc_order.push(ActionBinding::Callback(action));
546        self
547    }
548
549    pub fn add_ac_result(&mut self, action: ContextAction) -> &mut Self {
550        prepare_order(
551            &self.ac,
552            &self.ac_fns,
553            &self.ac_state_fns,
554            &mut self.ac_order,
555        );
556        self.ac_fns.push(action.clone());
557        self.ac_order.push(ActionBinding::Callback(action));
558        self
559    }
560
561    pub fn add_bo_with_state(&mut self, action: StateAction) -> &mut Self {
562        prepare_order(
563            &self.bo,
564            &self.bo_fns,
565            &self.bo_state_fns,
566            &mut self.bo_order,
567        );
568        self.bo_state_fns.push(action.clone());
569        self.bo_order.push(ActionBinding::State(action));
570        self
571    }
572
573    pub fn prepend_bo_with_state(&mut self, action: StateAction) -> &mut Self {
574        prepare_order(
575            &self.bo,
576            &self.bo_fns,
577            &self.bo_state_fns,
578            &mut self.bo_order,
579        );
580        self.bo_state_fns.insert(0, action.clone());
581        self.bo_order.insert(0, ActionBinding::State(action));
582        self
583    }
584
585    pub fn add_ao_with_state(&mut self, action: StateAction) -> &mut Self {
586        prepare_order(
587            &self.ao,
588            &self.ao_fns,
589            &self.ao_state_fns,
590            &mut self.ao_order,
591        );
592        self.ao_state_fns.push(action.clone());
593        self.ao_order.push(ActionBinding::State(action));
594        self
595    }
596
597    pub fn prepend_ao_with_state(&mut self, action: StateAction) -> &mut Self {
598        prepare_order(
599            &self.ao,
600            &self.ao_fns,
601            &self.ao_state_fns,
602            &mut self.ao_order,
603        );
604        self.ao_state_fns.insert(0, action.clone());
605        self.ao_order.insert(0, ActionBinding::State(action));
606        self
607    }
608
609    pub fn add_bc_with_state(&mut self, action: StateAction) -> &mut Self {
610        prepare_order(
611            &self.bc,
612            &self.bc_fns,
613            &self.bc_state_fns,
614            &mut self.bc_order,
615        );
616        self.bc_state_fns.push(action.clone());
617        self.bc_order.push(ActionBinding::State(action));
618        self
619    }
620
621    pub fn prepend_bc_with_state(&mut self, action: StateAction) -> &mut Self {
622        prepare_order(
623            &self.bc,
624            &self.bc_fns,
625            &self.bc_state_fns,
626            &mut self.bc_order,
627        );
628        self.bc_state_fns.insert(0, action.clone());
629        self.bc_order.insert(0, ActionBinding::State(action));
630        self
631    }
632
633    pub fn add_ac_with_state(&mut self, action: StateAction) -> &mut Self {
634        prepare_order(
635            &self.ac,
636            &self.ac_fns,
637            &self.ac_state_fns,
638            &mut self.ac_order,
639        );
640        self.ac_state_fns.push(action.clone());
641        self.ac_order.push(ActionBinding::State(action));
642        self
643    }
644
645    pub fn prepend_ac_with_state(&mut self, action: StateAction) -> &mut Self {
646        prepare_order(
647            &self.ac,
648            &self.ac_fns,
649            &self.ac_state_fns,
650            &mut self.ac_order,
651        );
652        self.ac_state_fns.insert(0, action.clone());
653        self.ac_order.insert(0, ActionBinding::State(action));
654        self
655    }
656
657    pub fn add_bo_ref(&mut self, action: impl Into<String>) -> &mut Self {
658        add_named(
659            &mut self.bo,
660            &mut self.bo_fns,
661            &mut self.bo_state_fns,
662            &mut self.bo_order,
663            action.into(),
664            false,
665        );
666        self
667    }
668
669    pub fn prepend_bo_ref(&mut self, action: impl Into<String>) -> &mut Self {
670        add_named(
671            &mut self.bo,
672            &mut self.bo_fns,
673            &mut self.bo_state_fns,
674            &mut self.bo_order,
675            action.into(),
676            true,
677        );
678        self
679    }
680
681    pub fn add_ao_ref(&mut self, action: impl Into<String>) -> &mut Self {
682        add_named(
683            &mut self.ao,
684            &mut self.ao_fns,
685            &mut self.ao_state_fns,
686            &mut self.ao_order,
687            action.into(),
688            false,
689        );
690        self
691    }
692
693    pub fn prepend_ao_ref(&mut self, action: impl Into<String>) -> &mut Self {
694        add_named(
695            &mut self.ao,
696            &mut self.ao_fns,
697            &mut self.ao_state_fns,
698            &mut self.ao_order,
699            action.into(),
700            true,
701        );
702        self
703    }
704
705    pub fn add_bc_ref(&mut self, action: impl Into<String>) -> &mut Self {
706        add_named(
707            &mut self.bc,
708            &mut self.bc_fns,
709            &mut self.bc_state_fns,
710            &mut self.bc_order,
711            action.into(),
712            false,
713        );
714        self
715    }
716
717    pub fn prepend_bc_ref(&mut self, action: impl Into<String>) -> &mut Self {
718        add_named(
719            &mut self.bc,
720            &mut self.bc_fns,
721            &mut self.bc_state_fns,
722            &mut self.bc_order,
723            action.into(),
724            true,
725        );
726        self
727    }
728
729    pub fn add_ac_ref(&mut self, action: impl Into<String>) -> &mut Self {
730        add_named(
731            &mut self.ac,
732            &mut self.ac_fns,
733            &mut self.ac_state_fns,
734            &mut self.ac_order,
735            action.into(),
736            false,
737        );
738        self
739    }
740
741    pub fn prepend_ac_ref(&mut self, action: impl Into<String>) -> &mut Self {
742        add_named(
743            &mut self.ac,
744            &mut self.ac_fns,
745            &mut self.ac_state_fns,
746            &mut self.ac_order,
747            action.into(),
748            true,
749        );
750        self
751    }
752
753    /// Clear named and imperative lifecycle actions. An empty phase slice
754    /// clears all four; otherwise accepted phase names are `bo`, `ao`, `bc`,
755    /// and `ac`.
756    pub fn clear_actions(&mut self, phases: &[&str]) -> &mut Self {
757        let clear_all = phases.is_empty();
758        for phase in ["bo", "ao", "bc", "ac"] {
759            if clear_all || phases.contains(&phase) {
760                match phase {
761                    "bo" => {
762                        self.bo.clear();
763                        self.bo_fns.clear();
764                        self.bo_state_fns.clear();
765                        self.bo_order.clear();
766                    }
767                    "ao" => {
768                        self.ao.clear();
769                        self.ao_fns.clear();
770                        self.ao_state_fns.clear();
771                        self.ao_order.clear();
772                    }
773                    "bc" => {
774                        self.bc.clear();
775                        self.bc_fns.clear();
776                        self.bc_state_fns.clear();
777                        self.bc_order.clear();
778                    }
779                    "ac" => {
780                        self.ac.clear();
781                        self.ac_fns.clear();
782                        self.ac_state_fns.clear();
783                        self.ac_order.clear();
784                    }
785                    _ => unreachable!(),
786                }
787            }
788        }
789        self
790    }
791}
792
793fn infallible_action(
794    action: impl Fn(&mut Rule, &mut Context) + Send + Sync + 'static,
795) -> ContextAction {
796    Arc::new(move |rule, context| {
797        action(rule, context);
798        Ok::<(), ActionError>(())
799    })
800}
801
802impl AltSpec {
803    /// Append an imperative Rust action to this alternate.
804    pub fn add_action(
805        &mut self,
806        action: impl Fn(&mut Rule, &mut Context) + Send + Sync + 'static,
807    ) -> &mut Self {
808        prepare_alt_order(
809            &self.a,
810            &self.action_fns,
811            &self.matched_action_fns,
812            &mut self.action_order,
813        );
814        let action = infallible_action(action);
815        self.action_fns.push(action.clone());
816        self.action_order.push(AltActionBinding::Context(action));
817        self
818    }
819
820    /// Prepend an imperative Rust action ahead of existing named or direct
821    /// actions.
822    pub fn prepend_action(
823        &mut self,
824        action: impl Fn(&mut Rule, &mut Context) + Send + Sync + 'static,
825    ) -> &mut Self {
826        prepare_alt_order(
827            &self.a,
828            &self.action_fns,
829            &self.matched_action_fns,
830            &mut self.action_order,
831        );
832        let action = infallible_action(action);
833        self.action_fns.insert(0, action.clone());
834        self.action_order
835            .insert(0, AltActionBinding::Context(action));
836        self
837    }
838
839    /// Append a fallible imperative Rust action to this alternate.
840    pub fn add_action_result(&mut self, action: ContextAction) -> &mut Self {
841        prepare_alt_order(
842            &self.a,
843            &self.action_fns,
844            &self.matched_action_fns,
845            &mut self.action_order,
846        );
847        self.action_fns.push(action.clone());
848        self.action_order.push(AltActionBinding::Context(action));
849        self
850    }
851
852    pub fn prepend_action_result(&mut self, action: ContextAction) -> &mut Self {
853        prepare_alt_order(
854            &self.a,
855            &self.action_fns,
856            &self.matched_action_fns,
857            &mut self.action_order,
858        );
859        self.action_fns.insert(0, action.clone());
860        self.action_order
861            .insert(0, AltActionBinding::Context(action));
862        self
863    }
864
865    /// Append an action with the complete matched-alternate argument.
866    pub fn add_action_with_match(
867        &mut self,
868        action: impl Fn(&mut Rule, &mut Context, &AltMatch) -> Option<Token> + Send + Sync + 'static,
869    ) -> &mut Self {
870        self.add_action_with_match_result(Arc::new(move |rule, context, matched| {
871            Ok(action(rule, context, matched))
872        }))
873    }
874
875    pub fn prepend_action_with_match(
876        &mut self,
877        action: impl Fn(&mut Rule, &mut Context, &AltMatch) -> Option<Token> + Send + Sync + 'static,
878    ) -> &mut Self {
879        self.prepend_action_with_match_result(Arc::new(move |rule, context, matched| {
880            Ok(action(rule, context, matched))
881        }))
882    }
883
884    pub fn add_action_with_match_result(&mut self, action: AltAction) -> &mut Self {
885        prepare_alt_order(
886            &self.a,
887            &self.action_fns,
888            &self.matched_action_fns,
889            &mut self.action_order,
890        );
891        self.matched_action_fns.push(action.clone());
892        self.action_order.push(AltActionBinding::Matched(action));
893        self
894    }
895
896    pub fn prepend_action_with_match_result(&mut self, action: AltAction) -> &mut Self {
897        prepare_alt_order(
898            &self.a,
899            &self.action_fns,
900            &self.matched_action_fns,
901            &mut self.action_order,
902        );
903        self.matched_action_fns.insert(0, action.clone());
904        self.action_order
905            .insert(0, AltActionBinding::Matched(action));
906        self
907    }
908
909    pub fn add_action_ref(&mut self, action: impl Into<String>) -> &mut Self {
910        add_alt_named(
911            &mut self.a,
912            &mut self.action_fns,
913            &mut self.matched_action_fns,
914            &mut self.action_order,
915            action.into(),
916            false,
917        );
918        self
919    }
920
921    pub fn prepend_action_ref(&mut self, action: impl Into<String>) -> &mut Self {
922        add_alt_named(
923            &mut self.a,
924            &mut self.action_fns,
925            &mut self.matched_action_fns,
926            &mut self.action_order,
927            action.into(),
928            true,
929        );
930        self
931    }
932}
933
934fn alt_order_matches(
935    named: &[String],
936    callbacks: &[ContextAction],
937    matched: &[AltAction],
938    order: &[AltActionBinding],
939) -> bool {
940    if order.len() != named.len() + callbacks.len() + matched.len() {
941        return false;
942    }
943    // One pass. Written as three filtered views compared against their
944    // lists, this walked `order` five times over -- once per view plus a
945    // second walk of two of them to count -- and the parse loop asks this
946    // question once per rule step. Taking the next expected entry from
947    // whichever list a binding names says the same thing in one walk.
948    let (mut next_name, mut next_callback, mut next_matched) = (0, 0, 0);
949    for binding in order {
950        match binding {
951            AltActionBinding::Named(name) => {
952                if named.get(next_name) != Some(name) {
953                    return false;
954                }
955                next_name += 1;
956            }
957            AltActionBinding::Context(callback) => {
958                if !callbacks
959                    .get(next_callback)
960                    .is_some_and(|expected| Arc::ptr_eq(expected, callback))
961                {
962                    return false;
963                }
964                next_callback += 1;
965            }
966            AltActionBinding::Matched(callback) => {
967                if !matched
968                    .get(next_matched)
969                    .is_some_and(|expected| Arc::ptr_eq(expected, callback))
970                {
971                    return false;
972                }
973                next_matched += 1;
974            }
975        }
976    }
977    next_name == named.len() && next_callback == callbacks.len() && next_matched == matched.len()
978}
979
980fn prepare_alt_order(
981    named: &[String],
982    callbacks: &[ContextAction],
983    matched: &[AltAction],
984    order: &mut Vec<AltActionBinding>,
985) {
986    if !alt_order_matches(named, callbacks, matched, order) {
987        *order = named
988            .iter()
989            .cloned()
990            .map(AltActionBinding::Named)
991            .chain(callbacks.iter().cloned().map(AltActionBinding::Context))
992            .chain(matched.iter().cloned().map(AltActionBinding::Matched))
993            .collect();
994    }
995}
996
997fn add_alt_named(
998    named: &mut Vec<String>,
999    callbacks: &mut Vec<ContextAction>,
1000    matched: &mut Vec<AltAction>,
1001    order: &mut Vec<AltActionBinding>,
1002    action: String,
1003    prepend: bool,
1004) {
1005    prepare_alt_order(named, callbacks, matched, order);
1006    if prepend {
1007        named.insert(0, action.clone());
1008        order.insert(0, AltActionBinding::Named(action));
1009    } else {
1010        named.push(action.clone());
1011        order.push(AltActionBinding::Named(action));
1012    }
1013}
1014
1015pub(crate) fn resolved_alt_action_order(
1016    named: &[String],
1017    callbacks: &[ContextAction],
1018    matched: &[AltAction],
1019    order: &[AltActionBinding],
1020) -> Vec<AltActionBinding> {
1021    if alt_order_matches(named, callbacks, matched, order) {
1022        order.to_vec()
1023    } else {
1024        named
1025            .iter()
1026            .cloned()
1027            .map(AltActionBinding::Named)
1028            .chain(callbacks.iter().cloned().map(AltActionBinding::Context))
1029            .chain(matched.iter().cloned().map(AltActionBinding::Matched))
1030            .collect()
1031    }
1032}
1033
1034fn order_matches(
1035    named: &[String],
1036    callbacks: &[ContextAction],
1037    states: &[StateAction],
1038    order: &[ActionBinding],
1039) -> bool {
1040    if order.len() != named.len() + callbacks.len() + states.len() {
1041        return false;
1042    }
1043    // One pass, for the reason given on `alt_order_matches`.
1044    let (mut next_name, mut next_callback, mut next_state) = (0, 0, 0);
1045    for binding in order {
1046        match binding {
1047            ActionBinding::Named(name) => {
1048                if named.get(next_name) != Some(name) {
1049                    return false;
1050                }
1051                next_name += 1;
1052            }
1053            ActionBinding::Callback(callback) => {
1054                if !callbacks
1055                    .get(next_callback)
1056                    .is_some_and(|expected| Arc::ptr_eq(expected, callback))
1057                {
1058                    return false;
1059                }
1060                next_callback += 1;
1061            }
1062            ActionBinding::State(callback) => {
1063                if !states
1064                    .get(next_state)
1065                    .is_some_and(|expected| Arc::ptr_eq(expected, callback))
1066                {
1067                    return false;
1068                }
1069                next_state += 1;
1070            }
1071        }
1072    }
1073    next_name == named.len() && next_callback == callbacks.len() && next_state == states.len()
1074}
1075
1076fn prepare_order(
1077    named: &[String],
1078    callbacks: &[ContextAction],
1079    states: &[StateAction],
1080    order: &mut Vec<ActionBinding>,
1081) {
1082    if !order_matches(named, callbacks, states, order) {
1083        *order = named
1084            .iter()
1085            .cloned()
1086            .map(ActionBinding::Named)
1087            .chain(callbacks.iter().cloned().map(ActionBinding::Callback))
1088            .chain(states.iter().cloned().map(ActionBinding::State))
1089            .collect();
1090    }
1091}
1092
1093fn add_named(
1094    named: &mut Vec<String>,
1095    callbacks: &mut Vec<ContextAction>,
1096    states: &mut Vec<StateAction>,
1097    order: &mut Vec<ActionBinding>,
1098    action: String,
1099    prepend: bool,
1100) {
1101    prepare_order(named, callbacks, states, order);
1102    if prepend {
1103        named.insert(0, action.clone());
1104        order.insert(0, ActionBinding::Named(action));
1105    } else {
1106        named.push(action.clone());
1107        order.push(ActionBinding::Named(action));
1108    }
1109}
1110
1111pub(crate) fn resolved_action_order(
1112    named: &[String],
1113    callbacks: &[ContextAction],
1114    states: &[StateAction],
1115    order: &[ActionBinding],
1116) -> Vec<ActionBinding> {
1117    if order_matches(named, callbacks, states, order) {
1118        order.to_vec()
1119    } else {
1120        named
1121            .iter()
1122            .cloned()
1123            .map(ActionBinding::Named)
1124            .chain(callbacks.iter().cloned().map(ActionBinding::Callback))
1125            .chain(states.iter().cloned().map(ActionBinding::State))
1126            .collect()
1127    }
1128}
1129
1130/// A rule's name.
1131///
1132/// Rules are pushed and popped for every construct in a parse, so the
1133/// name is shared between a rule, its snapshots and whatever the next
1134/// rule records, rather than being copied at each step. It still
1135/// behaves like the `String` it replaced: compare it with a literal,
1136/// print it, or take a `&str` from it.
1137#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
1138pub struct RuleName(Arc<str>);
1139
1140impl RuleName {
1141    pub fn as_str(&self) -> &str {
1142        &self.0
1143    }
1144}
1145
1146impl std::ops::Deref for RuleName {
1147    type Target = str;
1148
1149    fn deref(&self) -> &str {
1150        &self.0
1151    }
1152}
1153
1154impl AsRef<str> for RuleName {
1155    fn as_ref(&self) -> &str {
1156        &self.0
1157    }
1158}
1159
1160/// Keyed lookups borrow the name as a `str`, so `Hash` and `Eq` have to
1161/// agree with `str`'s. Both reach `str` through the `Arc`, so they do.
1162impl std::borrow::Borrow<str> for RuleName {
1163    fn borrow(&self) -> &str {
1164        &self.0
1165    }
1166}
1167
1168/// Printed as the bare name, so a `{:?}` of a rule or a snapshot reads
1169/// the way it did when this was a `String`.
1170impl fmt::Debug for RuleName {
1171    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1172        fmt::Debug::fmt(&*self.0, f)
1173    }
1174}
1175
1176impl fmt::Display for RuleName {
1177    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1178        f.write_str(&self.0)
1179    }
1180}
1181
1182impl PartialEq<str> for RuleName {
1183    fn eq(&self, other: &str) -> bool {
1184        &*self.0 == other
1185    }
1186}
1187
1188impl PartialEq<&str> for RuleName {
1189    fn eq(&self, other: &&str) -> bool {
1190        &*self.0 == *other
1191    }
1192}
1193
1194impl PartialEq<String> for RuleName {
1195    fn eq(&self, other: &String) -> bool {
1196        &*self.0 == other.as_str()
1197    }
1198}
1199
1200impl PartialEq<RuleName> for str {
1201    fn eq(&self, other: &RuleName) -> bool {
1202        self == &*other.0
1203    }
1204}
1205
1206impl PartialEq<RuleName> for &str {
1207    fn eq(&self, other: &RuleName) -> bool {
1208        *self == &*other.0
1209    }
1210}
1211
1212impl PartialEq<RuleName> for String {
1213    fn eq(&self, other: &RuleName) -> bool {
1214        self.as_str() == &*other.0
1215    }
1216}
1217
1218impl From<&str> for RuleName {
1219    fn from(name: &str) -> Self {
1220        RuleName(Arc::from(name))
1221    }
1222}
1223
1224impl From<String> for RuleName {
1225    fn from(name: String) -> Self {
1226        RuleName(Arc::from(name.as_str()))
1227    }
1228}
1229
1230impl From<&String> for RuleName {
1231    fn from(name: &String) -> Self {
1232        RuleName(Arc::from(name.as_str()))
1233    }
1234}
1235
1236impl From<Arc<str>> for RuleName {
1237    fn from(name: Arc<str>) -> Self {
1238        RuleName(name)
1239    }
1240}
1241
1242impl From<RuleName> for String {
1243    fn from(name: RuleName) -> Self {
1244        name.0.to_string()
1245    }
1246}
1247
1248/// A rule as the parse loop sees it.
1249///
1250/// Its state lives behind an `Rc` that it shares with every snapshot
1251/// taken of it, so `snapshot()` is a pointer copy. The copy happens
1252/// instead on the next write, and only while a snapshot is still
1253/// holding the current value — so a rule that is snapshotted several
1254/// times between writes pays for one copy, not several, and a rule
1255/// nobody snapshotted pays for none. Reads and writes both go through
1256/// `Deref`, so `rule.state` and `rule.state = ..` are unchanged at
1257/// every call site.
1258#[derive(Clone)]
1259pub struct Rule {
1260    shared: Rc<RuleSnapshot>,
1261    /// Not shared with snapshots, which do not carry it.
1262    pub parent_node: Option<Rc<RefCell<Value>>>,
1263    /// The completed child's node, likewise not shared. A `Value` is 72
1264    /// bytes, which was a third of a `RuleSnapshot`, and copy-on-write
1265    /// copied all of it on the next write to any field. Nothing reads
1266    /// this through a snapshot: every use in the engine and in the
1267    /// plugin repos is `rule.child_node` on a live rule.
1268    ///
1269    /// `Undefined` when the child shared this rule's node cell, so that
1270    /// this field is never a second handle on this rule's own
1271    /// accumulator (#195); [`Rule::child_value`] answers from the node
1272    /// in that case.
1273    pub child_node: Value,
1274    pub(crate) skip_befores: bool,
1275    pub(crate) child_node_is_self: bool,
1276    /// Whether the child link below still names the rule this one PUSHED,
1277    /// and that rule is still running.
1278    ///
1279    /// The link is frozen ONCE, by the first `freeze_child` after the push,
1280    /// and this says whether that has happened yet. It is deliberately not
1281    /// an identity carried on the child: a rule is handed to callbacks as
1282    /// `&mut Rule`, so an imperative action can assign `*rule = ...` and
1283    /// replace the whole value, resetting any field on it. Anything the
1284    /// engine needs to trust therefore cannot live there. This flag lives
1285    /// on the PARENT, which is buried on the parse stack for the whole of
1286    /// the child's life and is never handed to a callback, so no grammar
1287    /// can reach it.
1288    ///
1289    /// Getting this wrong is not a stale-looking value but a wrong one:
1290    /// `@node$`, `@value$`, `@object$`, `@fold$` and `@bubble$` all REPLACE
1291    /// `rule.node` with a fresh cell rather than writing through it
1292    /// (`rs/src/builtins.rs`), so a link left at its push-time cell holds
1293    /// the value from before the child did any work.
1294    ///
1295    /// TypeScript links `rule.child` at the push (`ts/src/rules.ts:665`)
1296    /// and never relinks it; Go does the same (`go/rule.go:1280`). A child
1297    /// that REPLACES itself therefore leaves the parent reading the first
1298    /// instance of the chain, which is why `@fold$` exists at all (see its
1299    /// doc comment in `ts/src/builtins.ts`). Closing the link on the first
1300    /// freeze is how that survives here, where the replaced rule is dropped
1301    /// rather than kept alive by a reference.
1302    pub(crate) child_link_open: bool,
1303    pub(crate) child_cell: Option<Rc<RefCell<Value>>>,
1304    /// The pushed rule's record, frozen at the moment it stopped being the
1305    /// current rule. Deliberately NOT a [`RuleSnapshot`] field: the parse
1306    /// loop writes it on a rule that is still buried on the stack, and
1307    /// `Context::sync_rule_stack` requires a buried frame's snapshot to
1308    /// keep describing it. It reaches `child_rule` only when the rule is
1309    /// resumed, which is the moment TypeScript's live reference would
1310    /// first be read from that rule again.
1311    pub(crate) child_record: Option<Rc<RuleSnapshot>>,
1312    /// Where this rule's prepared state sits in the parser's table, or
1313    /// `usize::MAX` for a rule the parser did not bind.
1314    ///
1315    /// A plain `usize` rather than a handle on the prepared record itself:
1316    /// the parse loop clones a `Rule` once per close and snapshots it
1317    /// several times per step, and an `Arc` here would make every one of
1318    /// those a pair of atomics. The table is reached through the parser's
1319    /// `&self` instead, and this only says where to look. It is a hint,
1320    /// not a fact -- a callback can write `spec` or `name` out from under
1321    /// it -- so the loop checks the record it finds against both before
1322    /// trusting it.
1323    pub(crate) slot: usize,
1324}
1325
1326impl Drop for RuleSnapshot {
1327    /// Unlink iteratively, because the derived drop recurses and the links
1328    /// below form a chain as long as the input.
1329    ///
1330    /// `parent_rule`, `child_rule`, `prev_rule` and `next_rule` each own an
1331    /// `Rc<RuleSnapshot>`, so the generated glue walks a chain with the call
1332    /// stack: `drop_in_place<RuleSnapshot>` calls `Rc::drop_slow` calls
1333    /// `drop_in_place<RuleSnapshot>` again, one frame per link. A grammar
1334    /// that pushes or replaces a rule per input element builds one link per
1335    /// element, so a flat JSON array of 150,000 numbers -- nesting depth
1336    /// ONE, nothing recursive about the document -- overflowed the default
1337    /// 8 MiB main-thread stack and aborted the process.
1338    ///
1339    /// Fat LTO makes it worse rather than better: inlining the cycle into
1340    /// itself multiplies the per-link frame, so a default release build
1341    /// survived an input that a build in the configuration rs/README.md
1342    /// documents for shipping did not. That is the wrong way round, and it
1343    /// is why this is a `Drop` impl rather than advice about stack size.
1344    ///
1345    /// The scratch is a local rather than a thread-local. A thread-local
1346    /// is faster and was wrong twice over: its key can be destroyed before
1347    /// another thread-local holding a snapshot is, and touching a
1348    /// destroyed key panics from inside a destructor; and re-entering this
1349    /// function while its `RefCell` is borrowed panics too. A local is
1350    /// immune to both, and the early return below means most drops never
1351    /// reach it.
1352    fn drop(&mut self) {
1353        // The overwhelmingly common case, and the one on the parse loop's
1354        // hot path: nothing is linked, so there is nothing to walk. Four
1355        // loads and a branch, no scratch, no allocation.
1356        if self.parent_rule.is_none()
1357            && self.child_rule.is_none()
1358            && self.prev_rule.is_none()
1359            && self.next_rule.is_none()
1360        {
1361            return;
1362        }
1363
1364        /// Move a snapshot's links out, preferring the single-slot
1365        /// `cursor` so that a pure chain -- one link per snapshot, which
1366        /// is what a rule replaced once per input element builds -- is
1367        /// walked without allocating anything at all. `pending` is only
1368        /// reached for a snapshot holding more than one link, and a `Vec`
1369        /// that is never pushed to never allocates.
1370        fn unlink(
1371            snapshot: &mut RuleSnapshot,
1372            cursor: &mut Option<Rc<RuleSnapshot>>,
1373            pending: &mut Vec<Rc<RuleSnapshot>>,
1374        ) {
1375            let mut hold = |held: Option<Rc<RuleSnapshot>>| {
1376                if let Some(held) = held {
1377                    if cursor.is_none() {
1378                        *cursor = Some(held);
1379                    } else {
1380                        pending.push(held);
1381                    }
1382                }
1383            };
1384            hold(snapshot.parent_rule.take());
1385            hold(snapshot.child_rule.take());
1386            hold(snapshot.prev_rule.take());
1387            hold(snapshot.next_rule.take());
1388        }
1389
1390        let mut cursor: Option<Rc<RuleSnapshot>> = None;
1391        let mut pending: Vec<Rc<RuleSnapshot>> = Vec::new();
1392        unlink(self, &mut cursor, &mut pending);
1393        while let Some(mut link) = cursor.take().or_else(|| pending.pop()) {
1394            if Rc::weak_count(&link) == 0 {
1395                // No weak observers, so `get_mut` answers "am I the last
1396                // handle" without moving anything. `RuleSnapshot` is a
1397                // twenty-field struct carrying eight reference-counted
1398                // handles, and this is the path the parse loop takes.
1399                if let Some(owned) = Rc::get_mut(&mut link) {
1400                    unlink(owned, &mut cursor, &mut pending);
1401                }
1402            } else if let Ok(mut owned) = Rc::try_unwrap(link) {
1403                // `Rule::snapshot` is public and `Context` hands out
1404                // `Rc<RuleSnapshot>`, so an embedder can hold a `Weak` to
1405                // one. `get_mut` refuses while any weak observer exists,
1406                // even when we ARE the last strong owner and dropping will
1407                // run the destructor; `try_unwrap` is the one that
1408                // distinguishes those. Getting this wrong left the links
1409                // in place and recursed after all.
1410                unlink(&mut owned, &mut cursor, &mut pending);
1411            }
1412            // Anything reached here drops with its links already taken, so
1413            // its own `drop` returns at the check above.
1414        }
1415    }
1416}
1417
1418impl std::ops::Deref for Rule {
1419    type Target = RuleSnapshot;
1420
1421    fn deref(&self) -> &RuleSnapshot {
1422        &self.shared
1423    }
1424}
1425
1426/// Every write to a rule's shared state goes through here, which is
1427/// what makes the copy happen on write rather than on snapshot.
1428///
1429/// The obvious next step — stop copying at all, so a snapshot aliases
1430/// the live rule the way TypeScript's and Go's rule handles do — was
1431/// measured here by making this return an aliasing pointer. It is
1432/// faster where it works: a 512-character palindrome drops from 31.7M
1433/// to 24.6M instructions, and a 16K-term adder from 72.7 ms to 57.8 ms.
1434/// But `next_rule` and the parent and child links then point at rules
1435/// that point back, and an `Rc` cycle is never freed: peak memory for
1436/// the benchmark set goes from 71 MB to 1214 MB, and a 32K-character
1437/// palindrome slows from 111 ms to 270 ms once the leak outweighs the
1438/// saving. Doing it properly needs `Weak` on every back-reference and
1439/// an upgrade on every traversal, which spends some of the same 1.3x
1440/// it is chasing. Worth knowing before anyone tries it again.
1441impl std::ops::DerefMut for Rule {
1442    fn deref_mut(&mut self) -> &mut RuleSnapshot {
1443        Rc::make_mut(&mut self.shared)
1444    }
1445}
1446
1447#[derive(Debug, Clone)]
1448pub struct RuleSnapshot {
1449    pub i: usize,
1450    pub d: usize,
1451    pub name: RuleName,
1452    pub spec: Arc<RuleSpec>,
1453    pub state: RuleState,
1454    pub bo: bool,
1455    pub ao: bool,
1456    pub bc: bool,
1457    pub ac: bool,
1458    pub need: i32,
1459    pub node: Rc<RefCell<Value>>,
1460    pub parent_rule: Option<Rc<RuleSnapshot>>,
1461    pub child_rule: Option<Rc<RuleSnapshot>>,
1462    pub prev_rule: Option<Rc<RuleSnapshot>>,
1463    pub next_rule: Option<Rc<RuleSnapshot>>,
1464    pub next_rule_name: Option<RuleName>,
1465    pub n: Rc<HashMap<String, i32>>,
1466    pub u: Rc<HashMap<String, Value>>,
1467    pub k: Rc<HashMap<String, Value>>,
1468    /// Matched open and close tokens. Shared rather than owned: the parse
1469    /// loop only ever replaces these wholesale, and a snapshot that copied
1470    /// them copied every `Token`'s name and source text with them.
1471    pub o: Rc<Vec<Token>>,
1472    pub c: Rc<Vec<Token>>,
1473}
1474
1475/// One shared empty map per thread, so a rule that never writes to `n`,
1476/// `u` or `k` costs no allocation for them. `Rc::make_mut` copies on the
1477/// first write, which for an empty map is close to free.
1478fn empty_counters() -> Rc<HashMap<String, i32>> {
1479    thread_local! {
1480        static EMPTY: Rc<HashMap<String, i32>> = Rc::new(HashMap::new());
1481    }
1482    EMPTY.with(Rc::clone)
1483}
1484
1485fn empty_values() -> Rc<HashMap<String, Value>> {
1486    thread_local! {
1487        static EMPTY: Rc<HashMap<String, Value>> = Rc::new(HashMap::new());
1488    }
1489    EMPTY.with(Rc::clone)
1490}
1491
1492/// The matched-token lists start empty and are replaced wholesale when an
1493/// alternate matches, so every rule created allocated two `Rc` boxes for two
1494/// vectors that never grew. Shared like the counter and value bags above.
1495fn empty_tokens() -> Rc<Vec<Token>> {
1496    thread_local! {
1497        static EMPTY: Rc<Vec<Token>> = Rc::new(Vec::new());
1498    }
1499    EMPTY.with(Rc::clone)
1500}
1501
1502impl Rule {
1503    /// Mutable access to the per-rule counters and state. Copies only when
1504    /// a snapshot is still holding the current value.
1505    pub fn n_mut(&mut self) -> &mut HashMap<String, i32> {
1506        Rc::make_mut(&mut self.n)
1507    }
1508
1509    pub fn u_mut(&mut self) -> &mut HashMap<String, Value> {
1510        Rc::make_mut(&mut self.u)
1511    }
1512
1513    pub fn k_mut(&mut self) -> &mut HashMap<String, Value> {
1514        Rc::make_mut(&mut self.k)
1515    }
1516
1517    pub fn new(name: impl Into<RuleName>, initial_node: Value) -> Self {
1518        let name: RuleName = name.into();
1519        let spec = Arc::new(RuleSpec::new(name.as_str()));
1520        Rule {
1521            shared: Rc::new(RuleSnapshot {
1522                i: 0,
1523                d: 0,
1524                name,
1525                spec,
1526                state: RuleState::Open,
1527                bo: true,
1528                ao: true,
1529                bc: true,
1530                ac: true,
1531                need: 0,
1532                node: Rc::new(RefCell::new(initial_node)),
1533                parent_rule: None,
1534                child_rule: None,
1535                prev_rule: None,
1536                next_rule: None,
1537                next_rule_name: None,
1538                n: empty_counters(),
1539                u: empty_values(),
1540                k: empty_values(),
1541                o: empty_tokens(),
1542                c: empty_tokens(),
1543            }),
1544            parent_node: None,
1545            child_node: Value::Undefined,
1546            skip_befores: false,
1547            child_node_is_self: false,
1548            child_link_open: false,
1549            child_cell: None,
1550            child_record: None,
1551            slot: usize::MAX,
1552        }
1553    }
1554
1555    pub fn with_shared_node(name: impl Into<RuleName>, node: Rc<RefCell<Value>>) -> Self {
1556        Self::bound(name.into(), node, None, usize::MAX)
1557    }
1558
1559    /// Build a rule already bound to its installed spec.
1560    ///
1561    /// An unbound rule reports its own name through `spec.name`, so building
1562    /// one with no spec has to invent a placeholder `RuleSpec` carrying that
1563    /// name: a `String` and an `Arc` box. Every push and replace in the parse
1564    /// loop then bound the installed spec straight over the placeholder, so
1565    /// both were allocated and freed once per rule step for nothing. The
1566    /// placeholder is still built for a name that names no installed rule,
1567    /// which is the case it exists for.
1568    pub(crate) fn bound(
1569        name: RuleName,
1570        node: Rc<RefCell<Value>>,
1571        installed: Option<&Arc<RuleSpec>>,
1572        slot: usize,
1573    ) -> Self {
1574        let spec = match installed {
1575            Some(spec) => Arc::clone(spec),
1576            None => Arc::new(RuleSpec::new(name.as_str())),
1577        };
1578        Rule {
1579            shared: Rc::new(RuleSnapshot {
1580                i: 0,
1581                d: 0,
1582                name,
1583                spec,
1584                state: RuleState::Open,
1585                bo: true,
1586                ao: true,
1587                bc: true,
1588                ac: true,
1589                need: 0,
1590                node,
1591                parent_rule: None,
1592                child_rule: None,
1593                prev_rule: None,
1594                next_rule: None,
1595                next_rule_name: None,
1596                n: empty_counters(),
1597                u: empty_values(),
1598                k: empty_values(),
1599                o: empty_tokens(),
1600                c: empty_tokens(),
1601            }),
1602            parent_node: None,
1603            child_node: Value::Undefined,
1604            skip_befores: false,
1605            child_node_is_self: false,
1606            child_link_open: false,
1607            child_cell: None,
1608            child_record: None,
1609            slot,
1610        }
1611    }
1612
1613    /// `name` arrives already shared: the parser interns one handle per
1614    /// installed rule, so binding copies a pointer rather than the text.
1615    ///
1616    /// `slot` is the rule's position in the parser's prepared table, which
1617    /// the same lookup that found the spec already returned.
1618    pub(crate) fn bind_spec(&mut self, spec: &Arc<RuleSpec>, name: RuleName, slot: usize) {
1619        self.name = name;
1620        self.spec = Arc::clone(spec);
1621        self.slot = slot;
1622        // Rust RuleSpec lifecycle lists are always present (possibly empty),
1623        // matching the canonical normalized definition's non-null defaults.
1624        self.bo = true;
1625        self.ao = true;
1626        self.bc = true;
1627        self.ac = true;
1628    }
1629
1630    pub fn o0(&self) -> Option<&Token> {
1631        self.o.first()
1632    }
1633
1634    pub fn o1(&self) -> Option<&Token> {
1635        self.o.get(1)
1636    }
1637
1638    pub fn c0(&self) -> Option<&Token> {
1639        self.c.first()
1640    }
1641
1642    pub fn c1(&self) -> Option<&Token> {
1643        self.c.get(1)
1644    }
1645
1646    pub fn os(&self) -> usize {
1647        self.o.len()
1648    }
1649
1650    pub fn cs(&self) -> usize {
1651        self.c.len()
1652    }
1653
1654    /// Resolve a matched opening token's eager or lazy semantic value without
1655    /// exposing the temporary token clone needed by Rust's borrow rules.
1656    pub fn resolve_open_value(&mut self, index: usize, context: &mut Context) -> Value {
1657        self.o
1658            .get(index)
1659            .cloned()
1660            .map_or(Value::Undefined, |token| token.resolve_val(self, context))
1661    }
1662
1663    /// Resolve a matched closing token's eager or lazy semantic value.
1664    pub fn resolve_close_value(&mut self, index: usize, context: &mut Context) -> Value {
1665        self.c
1666            .get(index)
1667            .cloned()
1668            .map_or(Value::Undefined, |token| token.resolve_val(self, context))
1669    }
1670
1671    /// Counter comparisons use zero for an unset counter, matching the
1672    /// canonical engine. `exist` distinguishes unset from explicitly zero.
1673    pub fn eq(&self, counter: &str, limit: i32) -> bool {
1674        self.n.get(counter).copied().unwrap_or(0) == limit
1675    }
1676
1677    pub fn lt(&self, counter: &str, limit: i32) -> bool {
1678        self.n.get(counter).copied().unwrap_or(0) < limit
1679    }
1680
1681    pub fn gt(&self, counter: &str, limit: i32) -> bool {
1682        self.n.get(counter).copied().unwrap_or(0) > limit
1683    }
1684
1685    pub fn lte(&self, counter: &str, limit: i32) -> bool {
1686        self.n.get(counter).copied().unwrap_or(0) <= limit
1687    }
1688
1689    pub fn gte(&self, counter: &str, limit: i32) -> bool {
1690        self.n.get(counter).copied().unwrap_or(0) >= limit
1691    }
1692
1693    pub fn exist(&self, counter: &str) -> bool {
1694        self.n.contains_key(counter)
1695    }
1696
1697    /// The rule's state as it stands, shared rather than copied. The
1698    /// copy, if one is still needed, happens on the rule's next write.
1699    pub fn snapshot(&self) -> Rc<RuleSnapshot> {
1700        Rc::clone(&self.shared)
1701    }
1702
1703    /// Remember which rule this one pushed, and where its node cell was at
1704    /// the push. Called by the parse loop's push arm.
1705    pub(crate) fn note_child_push(&mut self, child: &Rule) {
1706        self.child_link_open = true;
1707        self.child_cell = Some(Rc::clone(&child.node));
1708        self.child_record = Some(child.snapshot());
1709    }
1710
1711    /// Link the pushed child again, from its snapshot as it now stands.
1712    /// Called by the push arm, with no history bound, once the child's
1713    /// `parent_rule` is this rule with the child linked: the snapshot
1714    /// taken at the push carries this rule as it stood BEFORE the push,
1715    /// whose `child` is the child pushed before, and a grammar reading
1716    /// `parent.child.parent.child` from the child found that one where
1717    /// TypeScript and Go, which link live rules, find the child itself
1718    /// (parser #259). `child` and `next`, the links a grammar reads, move
1719    /// together; `child_record` moves with them so the three agree, though
1720    /// `freeze_child` replaces it before `accept_child` reads it on resume.
1721    pub(crate) fn relink_child(&mut self, child: &Rule) {
1722        let snapshot = child.snapshot();
1723        self.child_record = Some(Rc::clone(&snapshot));
1724        self.next_rule = Some(Rc::clone(&snapshot));
1725        self.child_rule = Some(snapshot);
1726    }
1727
1728    /// Whether `child` and `next` are still the link the push arm made,
1729    /// `linked`. The push arm relinks only then: an after action that
1730    /// cleared or repointed either link keeps its edit, as it does in
1731    /// TypeScript and Go, which link before the after actions run and do
1732    /// not touch the links again.
1733    pub(crate) fn links_unchanged(&self, linked: &Option<Rc<RuleSnapshot>>) -> bool {
1734        let same = |link: &Option<Rc<RuleSnapshot>>| match (link, linked) {
1735            (Some(now), Some(made)) => Rc::ptr_eq(now, made),
1736            _ => false,
1737        };
1738        same(&self.child_rule) && same(&self.next_rule)
1739    }
1740
1741    /// The pushed child is about to stop being the current rule, either
1742    /// because it is being replaced or because it is popping. Freeze both
1743    /// halves of the link: the cell its `node` field ended on, and its
1744    /// record as it stands. That pair is what TypeScript would go on
1745    /// reading through the live `rule.child` reference.
1746    ///
1747    /// Only the FIRST call after the push freezes; the link is closed
1748    /// afterwards. A later link of a replacement chain would otherwise
1749    /// overwrite it and report a `rule.child` no canonical runtime can
1750    /// produce -- the pushed rule's node under the chain tail's name.
1751    /// Closing the link rather than comparing an identity on the child is
1752    /// deliberate: see `Rule::child_link_open`.
1753    /// Holding the cell costs a refcount and no copy-on-write: the `Value`
1754    /// itself is read out only when this rule is resumed. The record is
1755    /// `Rc<RuleSnapshot>`, which the replaced rule is about to stop
1756    /// writing to in any case.
1757    pub(crate) fn freeze_child(&mut self, child: &Rule) {
1758        if self.child_link_open {
1759            self.child_cell = Some(Rc::clone(&child.node));
1760            self.child_record = Some(child.snapshot());
1761            self.child_link_open = false;
1762        }
1763    }
1764
1765    pub(crate) fn accept_child_node(&mut self, child: &Rule) {
1766        self.freeze_child(child);
1767        let cell = self
1768            .child_cell
1769            .clone()
1770            .unwrap_or_else(|| Rc::clone(&child.node));
1771        self.child_node_is_self = Rc::ptr_eq(&self.node, &cell);
1772        // A child that shared this rule's node cell wrote into this
1773        // rule's own container, so the value it hands back IS this
1774        // rule's node. Holding a clone of it here would be a second
1775        // `Arc` handle on the accumulator this rule is about to write
1776        // into again, and `Arc::make_mut` then copies the whole
1777        // container once per element: one rule with N elements cost
1778        // O(N^2), 46 seconds for 800 fields where TypeScript took a
1779        // tenth of a second (#195). The field stays `Undefined` in that
1780        // case and `child_value()` answers from the node instead, which
1781        // is what TypeScript's `rule.child.node` (the same object as
1782        // `rule.node` then) gives.
1783        self.child_node = if self.child_node_is_self {
1784            Value::Undefined
1785        } else {
1786            cell.borrow().clone()
1787        };
1788    }
1789
1790    /// The completed child's value, as TypeScript's `rule.child.node`
1791    /// reads: `child_node` when the child had a node of its own, and
1792    /// this rule's own node when the child shared this rule's cell (see
1793    /// `Rule::accept_child_node`, which is crate-private, so this is a
1794    /// name and not a link). Read this rather than `child_node`
1795    /// wherever the shared case must be seen as a value.
1796    pub fn child_value(&self) -> Value {
1797        if self.child_node_is_self {
1798            self.node.borrow().clone()
1799        } else {
1800            self.child_node.clone()
1801        }
1802    }
1803
1804    /// Whether [`Rule::child_value`] is defined.
1805    pub fn has_child_value(&self) -> bool {
1806        if self.child_node_is_self {
1807            !self.node.borrow().is_undefined()
1808        } else {
1809            !self.child_node.is_undefined()
1810        }
1811    }
1812
1813    /// Resume this rule with the child that has just stopped running: its
1814    /// node, and the `rule.child` / `rule.next` links a grammar reads from
1815    /// the resumed rule.
1816    ///
1817    /// Both links name the rule this one PUSHED, never whichever link of a
1818    /// replacement chain happened to pop. TypeScript assigns `rule.child`
1819    /// and `rule.next` once, in the push arm (`ts/src/rules.ts:665`,
1820    /// `:720`), and relinks neither when a descendant pops; Go does the
1821    /// same (`go/rule.go:1280`, `:1343`). The chain's later links are
1822    /// separate rule objects there, so the parent goes on reading the
1823    /// first. Here that rule has been dropped, so [`Rule::freeze_child`]
1824    /// captured it at its replace and this call leaves that capture alone.
1825    pub(crate) fn accept_child(&mut self, child: &Rule) {
1826        self.accept_child_node(child);
1827        // `child_record` is `None` only for a rule resumed by a child it
1828        // did not push. No parse-loop path reaches that today -- the one
1829        // `stack.push` is the push arm, which records the child first --
1830        // and falling back to the popping rule keeps the link honest
1831        // rather than leaving a stale one behind.
1832        self.child_rule = self.child_record.clone().or_else(|| Some(child.snapshot()));
1833        self.next_rule = self.child_rule.clone();
1834    }
1835
1836    /// Let go of `child_node` while this rule sits on the parse stack, in
1837    /// the one case where holding it is not free.
1838    ///
1839    /// A pushed child starts out on its PARENT's node cell, and a child
1840    /// that never installs a cell of its own still has it when it closes
1841    /// -- `child_node_is_self`. [`Rule::accept_child_node`] then leaves
1842    /// `child_node` holding a second `Value` handle on the very container
1843    /// the next child will write into. Containers are copy-on-write
1844    /// (`value.rs`), so that second handle turns the next `push` or
1845    /// `insert` into a copy of the whole container, and a rule with one
1846    /// such child per element copies its accumulated node once per
1847    /// element: quadratic in the number of elements inside ONE rule,
1848    /// where TypeScript and Go, whose nodes are plain references, stay
1849    /// linear.
1850    ///
1851    /// Parking is invisible because every pop that resumes a parked rule
1852    /// OVERWRITES the field before anything reads that rule. There are
1853    /// four pops in `parser.rs`: the two close-phase pops and the
1854    /// forced-close loop hand the popped rule to `accept_child`, which
1855    /// writes both `child_node` and `child_node_is_self` outright,
1856    /// and nothing touches the rule in between. The fourth, the
1857    /// fixed-depth recovery pop in `attempt_recover`, does not, and that
1858    /// pop is taken only when `recover.pop_until_valid` is off -- which
1859    /// is why `parser.rs` parks only when that option is on.
1860    /// `pop_until_valid` is read through `&self` and cannot change
1861    /// during a parse, so a rule parks exactly when the pop that will
1862    /// resume it is one of the three that overwrite.
1863    ///
1864    /// The field itself is only ever read on the CURRENT rule in any
1865    /// case: by the built-ins, by grammar actions and by the plugin
1866    /// repos, all of which are handed the rule the loop is working on.
1867    /// Snapshots do not carry it (see its declaration) and
1868    /// `Context::rule_stack` is snapshots, so no callback can reach a
1869    /// stacked rule's copy either. That is the second line of defence,
1870    /// not the argument: the argument is the overwrite.
1871    pub(crate) fn park_child_node(&mut self) {
1872        if self.child_node_is_self {
1873            self.child_node = Value::Undefined;
1874        }
1875    }
1876}
1877
1878impl fmt::Display for Rule {
1879    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
1880        write!(formatter, "[Rule {}~{}]", self.name, self.i)
1881    }
1882}
1883
1884#[cfg(test)]
1885mod tests {
1886    use super::*;
1887
1888    fn cell(text: &str) -> Rc<RefCell<Value>> {
1889        Rc::new(RefCell::new(Value::String(text.into())))
1890    }
1891
1892    /// The first freeze after the push is the one that lands.
1893    ///
1894    /// `@node$` and its relatives REPLACE `rule.node` with a fresh cell
1895    /// rather than writing through it, so a link left at the push-time cell
1896    /// holds the value from before the child ran. Freezing at the moment the
1897    /// child stops being current is what makes the parent read what the
1898    /// child actually produced.
1899    #[test]
1900    fn freeze_child_takes_the_cell_the_child_ended_on() {
1901        let mut parent = Rule::new("parent", Value::Undefined);
1902        let mut child = Rule::new("child", Value::Undefined);
1903        parent.note_child_push(&child);
1904
1905        child.node = cell("done");
1906        parent.freeze_child(&child);
1907
1908        assert_eq!(
1909            *parent
1910                .child_cell
1911                .as_ref()
1912                .expect("a frozen child cell")
1913                .borrow(),
1914            Value::String("done".into()),
1915            "the freeze kept the push-time cell instead of the one the child ended on"
1916        );
1917    }
1918
1919    /// A later link of a replacement chain must not overwrite the link.
1920    ///
1921    /// TypeScript and Go both keep `rule.child` on the rule the parent
1922    /// PUSHED, so the parent must go on reading the first link of the chain
1923    /// and not its tail.
1924    #[test]
1925    fn freeze_child_ignores_every_link_after_the_first() {
1926        let mut parent = Rule::new("parent", Value::Undefined);
1927        let mut pushed = Rule::new("pushed", Value::Undefined);
1928        parent.note_child_push(&pushed);
1929
1930        pushed.node = cell("pushed rule");
1931        parent.freeze_child(&pushed);
1932
1933        // `pushed` is replaced; the chain runs on and each link stops being
1934        // current in turn.
1935        let mut tail = Rule::new("tail", Value::Undefined);
1936        tail.node = cell("chain tail");
1937        parent.freeze_child(&tail);
1938
1939        assert_eq!(
1940            *parent
1941                .child_cell
1942                .as_ref()
1943                .expect("a frozen child cell")
1944                .borrow(),
1945            Value::String("pushed rule".into()),
1946            "a later link of the replacement chain overwrote the child link"
1947        );
1948    }
1949
1950    /// A callback cannot break the link by replacing the whole rule.
1951    ///
1952    /// An imperative action holds `&mut Rule`, so `*rule = Rule::new(..)` is
1953    /// legal and resets every field on the value, `i` included. While the
1954    /// link was keyed on an identity carried by the child, that assignment
1955    /// silently cost the parent its link and left it on the push-time cell.
1956    /// The flag lives on the parent, which is buried on the parse stack for
1957    /// the whole of the child's life and is never handed to a callback, so
1958    /// the freeze still lands and the parent sees what the replacement
1959    /// holds.
1960    #[test]
1961    fn a_callback_replacing_the_whole_child_rule_does_not_break_the_link() {
1962        let mut parent = Rule::new("parent", Value::Undefined);
1963        let mut child = Rule::new("child", Value::Undefined);
1964        parent.note_child_push(&child);
1965
1966        // What an imperative action is able to do to the rule it is given.
1967        child = Rule::new("child", Value::Undefined);
1968        child.node = cell("done");
1969
1970        parent.freeze_child(&child);
1971
1972        assert_eq!(
1973            *parent
1974                .child_cell
1975                .as_ref()
1976                .expect("a frozen child cell")
1977                .borrow(),
1978            Value::String("done".into()),
1979            "replacing the rule value cost the parent its child link"
1980        );
1981    }
1982}