Skip to main content

dbt_antlr_runtime/
parser_interpreter.rs

1//! A parser simulator that mimics what ANTLR's generated parser code does.
2//!
3//! Rust port of Java's `org.antlr.v4.runtime.ParserInterpreter`.
4//!
5//! A [`ParserATNSimulator`](crate::parser_atn_simulator::ParserATNSimulator)
6//! is used to make predictions via `adaptive_predict`, but this type moves a
7//! pointer through the ATN to simulate parsing. The simulator just makes us
8//! efficient rather than having to backtrack, for example.
9//!
10//! This properly creates parse trees even for left recursive rules.
11//!
12//! We rely on the left recursive rule invocation and special predicate
13//! transitions to make left recursive rules work.
14use std::ops::{Deref, DerefMut};
15
16use std::fmt::{Debug, Formatter};
17
18use crate::arena::Arena;
19use crate::atn::ATN;
20use crate::atn_simulator::ParserATNSimulatorManager;
21use crate::atn_state::{
22    ATNState, ATNStateType, RuleStartState, StarLoopEntryState, ATNSTATE_INVALID_STATE_NUMBER,
23};
24use crate::char_stream::CharStream;
25use crate::error_strategy::{DefaultErrorStrategy, ErrorStrategy, ErrorStrategyDelegate};
26use crate::errors::{ANTLRError, ANTLRErrorKind};
27use crate::interpreter_rule_context::{
28    InterpreterNode, InterpreterNodeKind, InterpreterRuleContextExt,
29};
30use crate::parser::{BaseParser, Parser, ParserRecog};
31use crate::parser_rule_context::BaseParserRuleContext;
32use crate::recognizer::{Actions, Recognizer};
33use crate::rule_context::RuleContext as _;
34use crate::token::{Token, TOKEN_DEFAULT_CHANNEL, TOKEN_INVALID_TYPE, TOKEN_MIN_USER_TOKEN_TYPE};
35use crate::token_factory::TokenFactory;
36use crate::token_stream::TokenStream;
37use crate::transition::{
38    ActionTransition, AtomTransition, PrecedencePredicateTransition, PredicateTransition,
39    RuleTransition, TransitionType,
40};
41use crate::tree::TreeNode;
42use crate::vocabulary::Vocabulary;
43
44/// Base parser type the parser interpreter is built on.
45pub type ParserInterpreterBase<'input, 'arena, Input, TF> =
46    BaseParser<'input, 'arena, ParserInterpreterExt, InterpreterNodeKind, Input, TF>;
47
48/// Recognizer data of a [ParserInterpreter].
49///
50/// Unlike generated parsers, which compile this data into statics, the
51/// interpreter receives it at construction time. The ATN and the ATN
52/// simulator manager must live for `'static` because of the runtime's
53/// simulator manager design, so they are leaked on construction; each
54/// interpreter instance gets its own (not shared) decision DFAs, matching the
55/// Java runtime.
56pub struct ParserInterpreterExt {
57    grammar_file_name: &'static str,
58    rule_names: &'static [&'static str],
59    vocabulary: Box<dyn Vocabulary>,
60    atn: &'static ATN,
61    atn_manager: &'static ParserATNSimulatorManager,
62}
63
64impl Debug for ParserInterpreterExt {
65    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
66        f.debug_struct("ParserInterpreterExt")
67            .field("grammar_file_name", &self.grammar_file_name)
68            .field("rule_names", &self.rule_names)
69            .field("vocabulary", &self.vocabulary)
70            .field("atn", &self.atn)
71            .finish_non_exhaustive()
72    }
73}
74
75impl<'input, 'arena, Input, TF>
76    Actions<'input, 'arena, ParserInterpreterBase<'input, 'arena, Input, TF>, TF::Tok>
77    for ParserInterpreterExt
78where
79    'input: 'arena,
80    TF: TokenFactory<'input, 'arena> + 'arena,
81    Input: TokenStream<'input, 'arena, TF> + 'arena,
82{
83    // `sempred` and `action` intentionally keep the default implementations
84    // (return true / do nothing): the interpreter cannot run target code,
85    // exactly like Java's ParserInterpreter which inherits the no-op
86    // `Recognizer.sempred`/`Recognizer.action`.
87
88    fn get_grammar_file_name(&self) -> &str {
89        self.grammar_file_name
90    }
91
92    fn get_rule_names(&self) -> &[&str] {
93        self.rule_names
94    }
95
96    fn get_vocabulary(&self) -> &dyn Vocabulary {
97        &*self.vocabulary
98    }
99}
100
101impl<'input, 'arena, Input, TF>
102    ParserRecog<'input, 'arena, ParserInterpreterBase<'input, 'arena, Input, TF>, TF::Tok>
103    for ParserInterpreterExt
104where
105    'input: 'arena,
106    TF: TokenFactory<'input, 'arena> + 'arena,
107    Input: TokenStream<'input, 'arena, TF> + 'arena,
108{
109    fn get_atn_simulator_man(&self) -> &'static ParserATNSimulatorManager {
110        self.atn_manager
111    }
112}
113
114/// A parser that interprets a deserialized ATN at runtime instead of executing
115/// generated code.
116///
117/// See Java's `ParserInterpreter` for the reference semantics; this port
118/// follows them 1:1, including left-recursion handling, decision overrides and
119/// the "all predicates pass" convention (the interpreter cannot run target
120/// code, so `sempred` always returns true while `precpred` checks the
121/// precedence stack for real).
122pub struct ParserInterpreter<'input, 'arena, Input, TF>
123where
124    'input: 'arena,
125    TF: TokenFactory<'input, 'arena> + 'arena,
126    Input: TokenStream<'input, 'arena, TF> + 'arena,
127{
128    base: ParserInterpreterBase<'input, 'arena, Input, TF>,
129    err_handler:
130        ErrorStrategyDelegate<'input, 'arena, TF, ParserInterpreterBase<'input, 'arena, Input, TF>>,
131
132    /// This stack corresponds to the `_parentctx`, `_parentState` pair of
133    /// locals that would exist on call stack frames with a recursive descent
134    /// parser; in the generated function for a left-recursive rule you'd see:
135    ///
136    /// ```ignore
137    /// fn e(&mut self, _p: i32) {
138    ///     let _parentctx = self.take_ctx();   // pair.0
139    ///     let _parentState = self.get_state(); // pair.1
140    ///     ...
141    /// }
142    /// ```
143    ///
144    /// Those values are used to create new recursive rule invocation contexts
145    /// associated with the left operand of an alt like `expr '*' expr`.
146    parent_context_stack: Vec<(
147        Option<&'arena InterpreterNode<'input, 'arena, TF::Tok>>,
148        i32,
149    )>,
150
151    /// We need a map from (decision, inputIndex) -> forced alt for computing
152    /// ambiguous parse trees. For now, we allow exactly one override.
153    override_decision: i32,
154    override_decision_input_index: isize,
155    override_decision_alt: i32,
156    /// latch and only override once; error might trigger infinite loop
157    override_decision_reached: bool,
158
159    /// What is the current context when we override a decision? This tells
160    /// us what the root of the parse tree is when using override
161    /// for an ambiguity/lookahead check.
162    override_decision_root: Option<&'arena InterpreterNode<'input, 'arena, TF::Tok>>,
163
164    root_context: Option<&'arena InterpreterNode<'input, 'arena, TF::Tok>>,
165
166    /// Opt-in outer alternative number tracking, mirroring the ANTLR tool's
167    /// `GrammarParserInterpreter`: when enabled, [ParserInterpreter::visit_decision_state]
168    /// records the predicted (rewritten) alternative number on the current
169    /// rule context at each state of [ParserInterpreter::outer_alt_decision_states].
170    /// Java's runtime `ParserInterpreter` never sets alt numbers, so this is
171    /// off by default.
172    track_alt_numbers: bool,
173
174    /// State numbers where [GrammarParserInterpreter](https://github.com/antlr/antlr4/blob/master/tool/src/org/antlr/v4/tool/GrammarParserInterpreter.java)'s
175    /// `findOuterMostDecisionStates` would record the outer alternative:
176    /// the outermost block of every rule and the star block holding the
177    /// recursive alternatives of a left-recursive rule. Computed lazily when
178    /// [ParserInterpreter::set_track_alt_numbers] is enabled.
179    outer_alt_decision_states: Option<Vec<bool>>,
180}
181
182impl<'input, 'arena, Input, TF> Debug for ParserInterpreter<'input, 'arena, Input, TF>
183where
184    'input: 'arena,
185    TF: TokenFactory<'input, 'arena> + 'arena,
186    Input: TokenStream<'input, 'arena, TF> + 'arena,
187{
188    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
189        f.debug_struct("ParserInterpreter").finish_non_exhaustive()
190    }
191}
192
193impl<'input, 'arena, Input, TF> Deref for ParserInterpreter<'input, 'arena, Input, TF>
194where
195    'input: 'arena,
196    TF: TokenFactory<'input, 'arena> + 'arena,
197    Input: TokenStream<'input, 'arena, TF> + 'arena,
198{
199    type Target = ParserInterpreterBase<'input, 'arena, Input, TF>;
200
201    fn deref(&self) -> &Self::Target {
202        &self.base
203    }
204}
205
206impl<'input, 'arena, Input, TF> DerefMut for ParserInterpreter<'input, 'arena, Input, TF>
207where
208    'input: 'arena,
209    TF: TokenFactory<'input, 'arena> + 'arena,
210    Input: TokenStream<'input, 'arena, TF> + 'arena,
211{
212    fn deref_mut(&mut self) -> &mut Self::Target {
213        &mut self.base
214    }
215}
216
217impl<'input, 'arena, Input, TF> ParserInterpreter<'input, 'arena, Input, TF>
218where
219    'input: 'arena,
220    TF: TokenFactory<'input, 'arena> + 'arena,
221    Input: TokenStream<'input, 'arena, TF> + 'arena,
222{
223    /// Creates a new parser interpreter with the given error strategy.
224    ///
225    /// `atn` is a ready (already deserialized) parser ATN; it is moved onto
226    /// the heap and leaked because the runtime's ATN simulator machinery
227    /// requires `&'static ATN`. Metadata (`grammar_file_name`, `rule_names`)
228    /// must be `&'static` for the same reason; leak dynamically built strings
229    /// with [Box::leak] if needed.
230    pub fn with_strategy(
231        arena: &'arena Arena,
232        grammar_file_name: &'static str,
233        vocabulary: Box<dyn Vocabulary>,
234        rule_names: &'static [&'static str],
235        atn: ATN,
236        input: Input,
237        strategy: Box<
238            dyn ErrorStrategy<'input, 'arena, TF, ParserInterpreterBase<'input, 'arena, Input, TF>>
239                + 'arena,
240        >,
241    ) -> Self {
242        let atn: &'static ATN = Box::leak(Box::new(atn));
243        let atn_manager: &'static ParserATNSimulatorManager =
244            Box::leak(Box::new(ParserATNSimulatorManager::new(atn)));
245        Self {
246            base: BaseParser::new_base_parser(
247                arena,
248                input,
249                ParserInterpreterExt {
250                    grammar_file_name,
251                    rule_names,
252                    vocabulary,
253                    atn,
254                    atn_manager,
255                },
256            ),
257            err_handler: unsafe { ErrorStrategyDelegate::new(strategy) },
258            parent_context_stack: Vec::new(),
259            override_decision: -1,
260            override_decision_input_index: -1,
261            override_decision_alt: -1,
262            override_decision_reached: false,
263            override_decision_root: None,
264            root_context: None,
265            track_alt_numbers: false,
266            outer_alt_decision_states: None,
267        }
268    }
269
270    /// Creates a new parser interpreter with [DefaultErrorStrategy].
271    ///
272    /// See [ParserInterpreter::with_strategy] for the parameter documentation.
273    pub fn new(
274        arena: &'arena Arena,
275        grammar_file_name: &'static str,
276        vocabulary: Box<dyn Vocabulary>,
277        rule_names: &'static [&'static str],
278        atn: ATN,
279        input: Input,
280    ) -> Self {
281        Self::with_strategy(
282            arena,
283            grammar_file_name,
284            vocabulary,
285            rule_names,
286            atn,
287            input,
288            Box::new(DefaultErrorStrategy::new()),
289        )
290    }
291
292    /// Replaces the error strategy of this interpreter.
293    pub fn set_error_strategy(
294        &mut self,
295        strategy: Box<
296            dyn ErrorStrategy<'input, 'arena, TF, ParserInterpreterBase<'input, 'arena, Input, TF>>
297                + 'arena,
298        >,
299    ) {
300        self.err_handler = unsafe { ErrorStrategyDelegate::new(strategy) };
301    }
302
303    /// Begin parsing at `start_rule_index`
304    pub fn parse(
305        &mut self,
306        start_rule_index: usize,
307    ) -> Result<&'arena InterpreterNode<'input, 'arena, TF::Tok>, ANTLRError> {
308        let atn = self.base.atn;
309        let start_rule_start_state = atn.rule_to_start_state[start_rule_index];
310        let is_left_recursive = is_left_recursive_rule(start_rule_start_state.as_ref());
311
312        let root_context = self.create_interpreter_rule_context(
313            None,
314            ATNSTATE_INVALID_STATE_NUMBER,
315            start_rule_index,
316        )?;
317        // Keep a second reference to the root node; the arena allocation
318        // outlives the parser, and the raw pointer read does not lock the
319        // `&'arena mut` used below.
320        self.root_context = Some(unsafe { &*(root_context as *const _) });
321        if is_left_recursive {
322            self.enter_recursion_rule(
323                root_context,
324                start_rule_start_state.get_state_number(),
325                start_rule_index,
326                0,
327            )?;
328        } else {
329            self.base.enter_rule(
330                root_context,
331                start_rule_start_state.get_state_number(),
332                start_rule_index,
333            )?;
334        }
335
336        loop {
337            let p = atn.get_state(self.base.get_state());
338            match p.state_type() {
339                ATNStateType::RuleStop => {
340                    // pop; return from rule
341                    let ctx = self.base.ctx().expect("parser is inside a rule");
342                    if ctx.is_empty() {
343                        if is_left_recursive {
344                            let result = ctx;
345                            let (parent_ctx, _) = self
346                                .parent_context_stack
347                                .pop()
348                                .expect("left-recursive start rule has a parent context");
349                            self.base.unroll_recursion_context(parent_ctx)?;
350                            return Ok(result);
351                        } else {
352                            self.base.exit_rule()?;
353                            return Ok(self.root_context.expect("root context was created"));
354                        }
355                    }
356
357                    self.visit_rule_stop_state(p)?;
358                }
359                _ => {
360                    match self.visit_state(p) {
361                        Ok(()) => {}
362                        Err(e) if !e.is_recoverable() => return Err(e),
363                        Err(e) => {
364                            self.base.set_state(
365                                atn.rule_to_stop_state[p.get_rule_index() as usize]
366                                    .get_state_number(),
367                            );
368                            // `ctx.exception = e` is a no-op in this runtime
369                            self.err_handler.report_error(&mut self.base, &e);
370                            self.recover(&e)?;
371                        }
372                    }
373                }
374            }
375        }
376    }
377
378    /// Interpreting counterpart of [BaseParser::enter_recursion_rule]:
379    /// additionally tracks the `_parentctx`/`_parentState` pair on
380    /// [ParserInterpreter::parent_context_stack].
381    pub fn enter_recursion_rule(
382        &mut self,
383        localctx: &'arena mut InterpreterNode<'input, 'arena, TF::Tok>,
384        state: i32,
385        rule_index: usize,
386        precedence: i32,
387    ) -> Result<(), ANTLRError> {
388        let pair = (self.base.ctx(), localctx.get_invoking_state());
389        self.parent_context_stack.push(pair);
390        self.base
391            .enter_recursion_rule(localctx, state, rule_index, precedence)
392    }
393
394    fn visit_state(&mut self, p: &'static ATNState) -> Result<(), ANTLRError> {
395        let atn = self.base.atn;
396        let mut predicted_alt = 1;
397        if p.is_decision_state() {
398            predicted_alt = self.visit_decision_state(p)?;
399        }
400
401        let transition = &p.get_transitions()[(predicted_alt - 1) as usize];
402        match transition.transition_type() {
403            TransitionType::Epsilon => {
404                if p.state_type() == ATNStateType::StarLoopEntry
405                    && p.try_as::<StarLoopEntryState>()
406                        .is_some_and(|state| state.is_precedence)
407                    && transition.get_target().state_type() != ATNStateType::LoopEnd
408                {
409                    // We are at the start of a left recursive rule's (...)* loop
410                    // and we're not taking the exit branch of loop.
411                    let (parent_ctx, parent_state) = *self
412                        .parent_context_stack
413                        .last()
414                        .expect("left-recursive rule has a parent context");
415                    let rule_index = self
416                        .base
417                        .ctx()
418                        .expect("parser is inside a rule")
419                        .get_rule_index();
420                    let localctx =
421                        self.create_interpreter_rule_context(parent_ctx, parent_state, rule_index)?;
422                    self.base.push_new_recursion_context(
423                        localctx,
424                        atn.rule_to_start_state[p.get_rule_index() as usize].get_state_number(),
425                        rule_index,
426                    )?;
427                }
428            }
429            TransitionType::Atom => {
430                let label = transition
431                    .try_as::<AtomTransition>()
432                    .expect("atom transition")
433                    .label();
434                self.base.match_token(label, &mut self.err_handler)?;
435            }
436            TransitionType::Range | TransitionType::Set | TransitionType::NotSet => {
437                if !transition.matches(
438                    self.base.get_input_stream_mut().la(1),
439                    TOKEN_MIN_USER_TOKEN_TYPE,
440                    65535,
441                ) {
442                    self.recover_inline()?;
443                }
444                self.base.match_wildcard(&mut self.err_handler)?;
445            }
446            TransitionType::Wildcard => {
447                self.base.match_wildcard(&mut self.err_handler)?;
448            }
449            TransitionType::Rule => {
450                let rule_transition = transition
451                    .try_as::<RuleTransition>()
452                    .expect("rule transition");
453                let rule_start_state = transition.get_target();
454                let rule_index = rule_start_state.get_rule_index() as usize;
455                let newctx = self.create_interpreter_rule_context(
456                    self.base.ctx(),
457                    p.get_state_number(),
458                    rule_index,
459                )?;
460                if is_left_recursive_rule(&rule_start_state) {
461                    self.enter_recursion_rule(
462                        newctx,
463                        rule_start_state.get_state_number(),
464                        rule_index,
465                        rule_transition.precedence(),
466                    )?;
467                } else {
468                    self.base.enter_rule(
469                        newctx,
470                        rule_start_state.get_state_number(),
471                        rule_index,
472                    )?;
473                }
474            }
475            TransitionType::Predicate => {
476                let predicate_transition = transition
477                    .try_as::<PredicateTransition>()
478                    .expect("predicate transition");
479                let ctx = self.base.ctx();
480                if !self.base.sempred(
481                    ctx,
482                    predicate_transition.rule_index(),
483                    predicate_transition.pred_index(),
484                ) {
485                    return Err(ANTLRError::failed_predicate(&mut self.base, None, None));
486                }
487            }
488            TransitionType::Action => {
489                let action_transition = transition
490                    .try_as::<ActionTransition>()
491                    .expect("action transition");
492                let ctx = self.base.ctx();
493                self.base.action(
494                    ctx,
495                    action_transition.rule_index(),
496                    action_transition.action_index(),
497                );
498            }
499            TransitionType::PrecedencePredicate => {
500                let precedence = transition
501                    .try_as::<PrecedencePredicateTransition>()
502                    .expect("precedence predicate transition")
503                    .precedence();
504                let ctx = self.base.ctx();
505                if !self.base.precpred(ctx, precedence) {
506                    return Err(ANTLRError::failed_predicate(
507                        &mut self.base,
508                        Some(format!("precpred(_ctx, {})", precedence)),
509                        None,
510                    ));
511                }
512            }
513        }
514
515        self.base
516            .set_state(transition.get_target().get_state_number());
517        Ok(())
518    }
519
520    /// Called when the interpreter reaches a decision state.
521    ///
522    /// Mirrors Java's `ParserInterpreter.visitDecisionState`, including the
523    /// decision override check.
524    fn visit_decision_state(&mut self, p: &'static ATNState) -> Result<i32, ANTLRError> {
525        let mut predicted_alt = 1;
526        if p.get_transitions().len() > 1 {
527            self.err_handler.sync(&mut self.base)?;
528            let decision = p.get_decision().expect("decision state has a decision");
529            if decision == self.override_decision
530                && self.base.get_input_stream().index() == self.override_decision_input_index
531                && !self.override_decision_reached
532            {
533                predicted_alt = self.override_decision_alt;
534                self.override_decision_reached = true;
535            } else {
536                predicted_alt = self
537                    .base
538                    .get_interpreter()
539                    .adaptive_predict(decision, &mut self.base)?;
540            }
541        }
542        let track = self.track_alt_numbers
543            && self
544                .outer_alt_decision_states
545                .as_ref()
546                .is_some_and(|states| {
547                    states
548                        .get(p.get_state_number() as usize)
549                        .copied()
550                        .unwrap_or(false)
551                });
552        if track {
553            self.base
554                .with_mut_ctx(|ctx| ctx.set_alt_number(predicted_alt));
555        }
556        Ok(predicted_alt)
557    }
558
559    /// Provides a simple "factory" for [InterpreterRuleContext](crate::interpreter_rule_context::InterpreterRuleContext)s.
560    fn create_interpreter_rule_context(
561        &self,
562        parent: Option<&'arena InterpreterNode<'input, 'arena, TF::Tok>>,
563        invoking_state: i32,
564        rule_index: usize,
565    ) -> Result<&'arena mut InterpreterNode<'input, 'arena, TF::Tok>, ANTLRError> {
566        let node = BaseParserRuleContext::create(
567            self.base.arena,
568            parent,
569            invoking_state,
570            InterpreterRuleContextExt::new(rule_index),
571        )?;
572        // The ANTLR tool's `GrammarInterpreterRuleContext` initializes
573        // `outerAltNum` to 1; match that when alt-number tracking is on.
574        if self.track_alt_numbers {
575            node.set_alt_number(1);
576        }
577        Ok(node)
578    }
579
580    fn visit_rule_stop_state(&mut self, p: &'static ATNState) -> Result<(), ANTLRError> {
581        let atn = self.base.atn;
582        let rule_start_state = atn.rule_to_start_state[p.get_rule_index() as usize];
583        if is_left_recursive_rule(&rule_start_state) {
584            let (parent_ctx, parent_state) = self
585                .parent_context_stack
586                .pop()
587                .expect("left-recursive rule has a parent context");
588            self.base.unroll_recursion_context(parent_ctx)?;
589            self.base.set_state(parent_state);
590        } else {
591            self.base.exit_rule()?;
592        }
593
594        let state = atn.get_state(self.base.get_state());
595        let rule_transition = state
596            .get_transitions()
597            .first()
598            .and_then(|transition| transition.try_as::<RuleTransition>())
599            .expect("invoking state has a rule transition");
600        self.base
601            .set_state(rule_transition.follow_state.get_state_number());
602        Ok(())
603    }
604
605    /// Enables or disables outer alternative number tracking; see
606    /// [ParserInterpreter::track_alt_numbers].
607    pub fn set_track_alt_numbers(&mut self, track: bool) {
608        if track && self.outer_alt_decision_states.is_none() {
609            self.outer_alt_decision_states = Some(find_outer_most_decision_states(self.base.atn));
610        }
611        self.track_alt_numbers = track;
612    }
613
614    /// Override this parser interpreter's normal decision-making process at a
615    /// particular decision and input token index. Instead of allowing the
616    /// adaptive prediction mechanism to choose the first alternative within a
617    /// block that leads to a successful parse, force it to take the
618    /// alternative, 1..n for n alternatives.
619    ///
620    /// As an implementation limitation right now, you can only specify one
621    /// override. This is sufficient to allow construction of different parse
622    /// trees for ambiguous input. It means re-parsing the entire input in
623    /// general because you're never sure where an ambiguous sequence would
624    /// live in the various parse trees.
625    ///
626    /// Only parser interpreters can override decisions so as to avoid
627    /// inserting override checking code in the critical ALL(*) prediction
628    /// execution path.
629    pub fn add_decision_override(&mut self, decision: i32, token_index: isize, forced_alt: i32) {
630        self.override_decision = decision;
631        self.override_decision_input_index = token_index;
632        self.override_decision_alt = forced_alt;
633    }
634
635    /// Returns the root of the parse when a decision override was used.
636    pub fn get_override_decision_root(
637        &self,
638    ) -> Option<&'arena InterpreterNode<'input, 'arena, TF::Tok>> {
639        self.override_decision_root
640    }
641
642    /// Rely on the error handler for this parser but, if no tokens are
643    /// consumed to recover, add an error node. Otherwise, nothing is seen in
644    /// the parse tree.
645    fn recover(&mut self, e: &ANTLRError) -> Result<(), ANTLRError> {
646        let i = self.base.get_input_stream().index();
647        self.err_handler.recover(&mut self.base, e)?;
648        if self.base.get_input_stream().index() == i {
649            // no input consumed, better add an error node
650            let expected_token_type = match e.as_ref() {
651                ANTLRErrorKind::InputMismatchError(ime) => ime
652                    .base
653                    .get_expected_tokens(&self.base)
654                    .get_min()
655                    .unwrap_or(TOKEN_INVALID_TYPE),
656                // NoViableAlt
657                _ => TOKEN_INVALID_TYPE,
658            };
659            let offending_token = e
660                .get_offending_token()
661                .expect("recognition error has an offending token");
662            let text = offending_token.get_text().to_owned();
663            let line = offending_token.get_line();
664            let column = offending_token.get_char_position_in_line();
665            let err_token = self.base.get_token_factory().create(
666                None::<&mut dyn CharStream<'input>>,
667                expected_token_type,
668                Some(text),
669                TOKEN_DEFAULT_CHANNEL,
670                -1,
671                -1, // invalid start/stop
672                line,
673                column,
674            );
675            let node = TreeNode::create_error_node(self.base.arena, err_token);
676            if node.is_null() {
677                return Err(ANTLRError::dfa_cache_limit_exceeded(0, 0, 0));
678            }
679            let node = unsafe { &*node };
680            self.base.with_mut_ctx(|ctx| ctx.add_child(node));
681        }
682        Ok(())
683    }
684
685    fn recover_inline(&mut self) -> Result<&'arena TF::Tok, ANTLRError> {
686        self.err_handler.recover_inline(&mut self.base)
687    }
688
689    /// Return the root of the parse, which can be useful if the parser
690    /// bails out. You still can access the top node. Note that,
691    /// because of the way left recursive rules add children, it's possible
692    /// that the root will not have any children if the start rule immediately
693    /// called and left recursive rule that fails.
694    pub fn get_root_context(&self) -> Option<&'arena InterpreterNode<'input, 'arena, TF::Tok>> {
695        self.root_context
696    }
697}
698
699/// Port of the ANTLR tool's
700/// `GrammarParserInterpreter.findOuterMostDecisionStates`: identifies the ATN
701/// states where the outer alternative number of the current rule context is
702/// determined. For regular rules that is the block at the target of the rule
703/// start state; for left-recursive rules it is also the star block holding
704/// the recursive alternatives. Returns a set indexed by state number.
705fn find_outer_most_decision_states(atn: &ATN) -> Vec<bool> {
706    let mut track = vec![false; atn.states_count()];
707    for decision in 0..atn.decision_to_state.len() {
708        let decision_state = atn.get_decision_state(decision as i32);
709        let start_state = atn.rule_to_start_state[decision_state.get_rule_index() as usize];
710        if decision_state.state_type() == ATNStateType::StarLoopEntry {
711            if decision_state
712                .try_as::<StarLoopEntryState>()
713                .is_some_and(|state| state.is_precedence)
714            {
715                let block_start = decision_state.get_transitions()[0].get_target();
716                track[block_start.get_state_number() as usize] = true;
717            }
718        } else if start_state
719            .get_transitions()
720            .first()
721            .is_some_and(|transition| {
722                transition.get_target().get_state_number() == decision_state.get_state_number()
723            })
724        {
725            track[decision_state.get_state_number() as usize] = true;
726        }
727    }
728    track
729}
730
731fn is_left_recursive_rule(rule_start_state: &ATNState) -> bool {
732    rule_start_state
733        .try_as::<RuleStartState>()
734        .is_some_and(|state| state.is_left_recursive)
735}