antlr4_runtime/atn/
mod.rs

1// SPDX-License-Identifier: BSD-3-Clause
2// Copyright (c) 2026 Konstantin Vyatkin
3//! Abstract Transition Network structures used by generated lexers and
4//! parsers.
5//!
6//! Lexers deserialize ANTLR metadata into a graph because lexer simulation
7//! still mutates and inspects that shape. Parsers use the packed,
8//! index-addressed [`parser_atn::ParserAtn`] representation instead.
9
10pub(crate) mod ascii_range;
11mod bypass;
12pub mod lexer;
13pub mod lexer_dfa;
14pub mod parser;
15pub mod parser_atn;
16pub mod serialized;
17
18#[derive(Clone, Copy)]
19struct TailCallSite {
20    start: usize,
21    stop: usize,
22    rule_index: usize,
23    state_count: usize,
24}
25
26#[derive(Default)]
27struct TailCallScratch {
28    marks: Vec<u8>,
29    work: Vec<(usize, bool)>,
30    successors: Vec<usize>,
31}
32
33fn plain_epsilon_tail_call<StateKind, StateRule, PushSuccessors>(
34    site: TailCallSite,
35    scratch: &mut TailCallScratch,
36    state_kind: StateKind,
37    state_rule_index: StateRule,
38    push_successors: PushSuccessors,
39) -> bool
40where
41    StateKind: Fn(usize) -> AtnStateKind,
42    StateRule: Fn(usize) -> Option<usize>,
43    PushSuccessors: Fn(usize, &mut Vec<usize>) -> bool,
44{
45    let TailCallSite {
46        start,
47        stop,
48        rule_index,
49        state_count,
50    } = site;
51    if start >= state_count
52        || stop >= state_count
53        || state_kind(stop) != AtnStateKind::RuleStop
54        || state_rule_index(stop) != Some(rule_index)
55    {
56        return false;
57    }
58
59    // Reject cycles as well as semantic, consuming, nested-rule, and dead-end
60    // paths. Every continuation must finish the enclosing rule without
61    // observable work.
62    let TailCallScratch {
63        marks,
64        work,
65        successors,
66    } = scratch;
67    marks.clear();
68    marks.resize(state_count, 0);
69    work.clear();
70    work.push((start, false));
71    successors.clear();
72    while let Some((state, exiting)) = work.pop() {
73        if state == stop {
74            continue;
75        }
76        if state >= state_count {
77            return false;
78        }
79        if exiting {
80            marks[state] = 2;
81            continue;
82        }
83        match marks[state] {
84            1 => return false,
85            2 => continue,
86            _ => {}
87        }
88        if state_kind(state) == AtnStateKind::RuleStop
89            || state_rule_index(state) != Some(rule_index)
90        {
91            return false;
92        }
93        successors.clear();
94        if !push_successors(state, successors) || successors.is_empty() {
95            return false;
96        }
97        marks[state] = 1;
98        work.push((state, true));
99        work.extend(successors.iter().copied().map(|target| (target, false)));
100    }
101    true
102}
103
104/// Deserialized lexer Abstract Transition Network.
105///
106/// The structure keeps the state graph plus ANTLR side tables such as
107/// rule-to-start, rule-to-token, mode-to-start, decisions, and actions. Parser
108/// ATNs never use this object-graph representation.
109#[derive(Clone, Debug, Eq, PartialEq)]
110pub struct LexerAtn {
111    max_token_type: i32,
112    states: Vec<LexerAtnState>,
113    rule_to_start_state: Vec<usize>,
114    rule_to_stop_state: Vec<usize>,
115    rule_to_token_type: Vec<i32>,
116    mode_to_start_state: Vec<usize>,
117    decision_to_state: Vec<usize>,
118    lexer_actions: Vec<LexerAction>,
119}
120
121impl LexerAtn {
122    /// Creates an empty lexer ATN with the maximum token type read from the
123    /// serialized header.
124    pub const fn new(max_token_type: i32) -> Self {
125        Self {
126            max_token_type,
127            states: Vec::new(),
128            rule_to_start_state: Vec::new(),
129            rule_to_stop_state: Vec::new(),
130            rule_to_token_type: Vec::new(),
131            mode_to_start_state: Vec::new(),
132            decision_to_state: Vec::new(),
133            lexer_actions: Vec::new(),
134        }
135    }
136
137    pub const fn max_token_type(&self) -> i32 {
138        self.max_token_type
139    }
140
141    pub fn states(&self) -> &[LexerAtnState] {
142        &self.states
143    }
144
145    pub fn state(&self, state_number: usize) -> Option<&LexerAtnState> {
146        self.states.get(state_number)
147    }
148
149    pub fn state_mut(&mut self, state_number: usize) -> Option<&mut LexerAtnState> {
150        self.states.get_mut(state_number)
151    }
152
153    /// Appends a state and returns the state number assigned by insertion
154    /// order.
155    pub fn add_state(&mut self, state: LexerAtnState) -> usize {
156        let index = self.states.len();
157        self.states.push(state);
158        index
159    }
160
161    pub fn decision_to_state(&self) -> &[usize] {
162        &self.decision_to_state
163    }
164
165    pub fn add_decision_state(&mut self, state_number: usize) {
166        self.decision_to_state.push(state_number);
167    }
168
169    pub fn rule_to_start_state(&self) -> &[usize] {
170        &self.rule_to_start_state
171    }
172
173    pub fn set_rule_to_start_state(&mut self, rule_to_start_state: Vec<usize>) {
174        self.rule_to_start_state = rule_to_start_state;
175    }
176
177    pub fn rule_to_stop_state(&self) -> &[usize] {
178        &self.rule_to_stop_state
179    }
180
181    pub fn set_rule_to_stop_state(&mut self, rule_to_stop_state: Vec<usize>) {
182        self.rule_to_stop_state = rule_to_stop_state;
183    }
184
185    pub fn rule_to_token_type(&self) -> &[i32] {
186        &self.rule_to_token_type
187    }
188
189    pub fn set_rule_to_token_type(&mut self, rule_to_token_type: Vec<i32>) {
190        self.rule_to_token_type = rule_to_token_type;
191    }
192
193    pub fn mode_to_start_state(&self) -> &[usize] {
194        &self.mode_to_start_state
195    }
196
197    pub fn add_mode_start_state(&mut self, state_number: usize) {
198        self.mode_to_start_state.push(state_number);
199    }
200
201    pub fn lexer_actions(&self) -> &[LexerAction] {
202        &self.lexer_actions
203    }
204
205    pub fn set_lexer_actions(&mut self, lexer_actions: Vec<LexerAction>) {
206        self.lexer_actions = lexer_actions;
207    }
208
209    /// Recomputes conservative tail-call markers after the graph is complete.
210    ///
211    /// Call this after every transition and derived rule-return edge has been
212    /// added. Any later mutation through [`Self::add_state`],
213    /// [`Self::state_mut`], or [`LexerAtnState::add_transition`] invalidates the
214    /// stored markers, so callers must run this analysis again before prediction.
215    #[doc(hidden)]
216    pub fn identify_tail_calls(&mut self) {
217        let mut tail_calls = Vec::new();
218        let mut scratch = TailCallScratch::default();
219        for source in 0..self.states.len() {
220            for index in 0..self.states[source].transitions.len() {
221                let follow_state = match &self.states[source].transitions[index] {
222                    LexerTransition::Rule { follow_state, .. } => *follow_state,
223                    _ => continue,
224                };
225                tail_calls.push((
226                    source,
227                    index,
228                    self.tail_call_follow_is_safe(source, follow_state, &mut scratch),
229                ));
230            }
231        }
232        for (source, index, tail_call) in tail_calls {
233            if let Some(LexerTransition::Rule {
234                tail_call: marker, ..
235            }) = self
236                .states
237                .get_mut(source)
238                .and_then(|state| state.transitions.get_mut(index))
239            {
240                *marker = tail_call;
241            }
242        }
243    }
244
245    fn tail_call_follow_is_safe(
246        &self,
247        source: usize,
248        start: usize,
249        scratch: &mut TailCallScratch,
250    ) -> bool {
251        let Some(rule_index) = self.states.get(source).and_then(|state| state.rule_index) else {
252            return false;
253        };
254        let Some(&stop) = self.rule_to_stop_state.get(rule_index) else {
255            return false;
256        };
257        plain_epsilon_tail_call(
258            TailCallSite {
259                start,
260                stop,
261                rule_index,
262                state_count: self.states.len(),
263            },
264            scratch,
265            |state| self.states[state].kind,
266            |state| self.states[state].rule_index,
267            |state, successors| {
268                for transition in &self.states[state].transitions {
269                    let LexerTransition::Epsilon { target } = transition else {
270                        return false;
271                    };
272                    successors.push(*target);
273                }
274                true
275            },
276        )
277    }
278}
279
280/// A node in the ANTLR ATN graph.
281///
282/// Some ANTLR state subclasses carry references to paired states, such as a
283/// block-start state's end state or a loop-end state's loop-back state. This
284/// representation stores those links as state numbers so the graph remains easy
285/// to clone and serialize in tests.
286#[derive(Clone, Debug, Eq, PartialEq)]
287pub struct LexerAtnState {
288    pub state_number: usize,
289    pub rule_index: Option<usize>,
290    pub kind: AtnStateKind,
291    pub end_state: Option<usize>,
292    pub loop_back_state: Option<usize>,
293    pub non_greedy: bool,
294    pub precedence_rule_decision: bool,
295    pub left_recursive_rule: bool,
296    pub transitions: Vec<LexerTransition>,
297}
298
299impl LexerAtnState {
300    /// Creates an ATN state with no rule index and no outgoing transitions.
301    pub const fn new(state_number: usize, kind: AtnStateKind) -> Self {
302        Self {
303            state_number,
304            rule_index: None,
305            kind,
306            end_state: None,
307            loop_back_state: None,
308            non_greedy: false,
309            precedence_rule_decision: false,
310            left_recursive_rule: false,
311            transitions: Vec::new(),
312        }
313    }
314
315    #[must_use]
316    pub const fn with_rule_index(mut self, rule_index: usize) -> Self {
317        self.rule_index = Some(rule_index);
318        self
319    }
320
321    /// Adds an outgoing transition in serialized order.
322    ///
323    /// Transition order matters for alternatives and lexer priority, so the
324    /// runtime preserves the order emitted by ANTLR.
325    pub fn add_transition(&mut self, transition: LexerTransition) {
326        self.transitions.push(transition);
327    }
328
329    pub fn is_rule_stop(&self) -> bool {
330        self.kind == AtnStateKind::RuleStop
331    }
332}
333
334/// Serialized ANTLR state kind.
335#[derive(Clone, Copy, Debug, Eq, PartialEq)]
336pub enum AtnStateKind {
337    Invalid,
338    Basic,
339    RuleStart,
340    BlockStart,
341    PlusBlockStart,
342    StarBlockStart,
343    TokenStart,
344    RuleStop,
345    BlockEnd,
346    StarLoopBack,
347    StarLoopEntry,
348    PlusLoopBack,
349    LoopEnd,
350}
351
352/// Edge between two ATN states.
353///
354/// Epsilon-like transitions do not consume input. Matching transitions compare
355/// the current input symbol against an atom, range, set, negated set, or
356/// wildcard.
357#[derive(Clone, Debug, Eq, PartialEq)]
358pub enum LexerTransition {
359    Epsilon {
360        target: usize,
361    },
362    Atom {
363        target: usize,
364        label: i32,
365    },
366    Range {
367        target: usize,
368        start: i32,
369        stop: i32,
370    },
371    Set {
372        target: usize,
373        set: IntervalSet,
374    },
375    NotSet {
376        target: usize,
377        set: IntervalSet,
378    },
379    Wildcard {
380        target: usize,
381    },
382    Rule {
383        target: usize,
384        rule_index: usize,
385        follow_state: usize,
386        precedence: i32,
387        tail_call: bool,
388    },
389    Predicate {
390        target: usize,
391        rule_index: usize,
392        pred_index: usize,
393        context_dependent: bool,
394    },
395    Action {
396        target: usize,
397        rule_index: usize,
398        action_index: Option<usize>,
399        context_dependent: bool,
400    },
401    Precedence {
402        target: usize,
403        precedence: i32,
404    },
405}
406
407impl LexerTransition {
408    /// Returns the target state number for this transition.
409    pub const fn target(&self) -> usize {
410        match self {
411            Self::Epsilon { target }
412            | Self::Atom { target, .. }
413            | Self::Range { target, .. }
414            | Self::Set { target, .. }
415            | Self::NotSet { target, .. }
416            | Self::Wildcard { target }
417            | Self::Rule { target, .. }
418            | Self::Predicate { target, .. }
419            | Self::Action { target, .. }
420            | Self::Precedence { target, .. } => *target,
421        }
422    }
423
424    /// Returns whether traversing this transition consumes no input.
425    pub const fn is_epsilon(&self) -> bool {
426        matches!(
427            self,
428            Self::Epsilon { .. }
429                | Self::Rule { .. }
430                | Self::Predicate { .. }
431                | Self::Action { .. }
432                | Self::Precedence { .. }
433        )
434    }
435
436    /// Returns whether this rule call's follow state is a provably redundant
437    /// prediction-context frame.
438    pub const fn is_tail_call(&self) -> bool {
439        matches!(
440            self,
441            Self::Rule {
442                tail_call: true,
443                ..
444            }
445        )
446    }
447
448    /// Tests whether this transition consumes `symbol`.
449    ///
450    /// `min_vocabulary` and `max_vocabulary` define the accepted symbol range
451    /// for wildcard and negated-set transitions.
452    pub fn matches(&self, symbol: i32, min_vocabulary: i32, max_vocabulary: i32) -> bool {
453        match self {
454            Self::Atom { label, .. } => *label == symbol,
455            Self::Range { start, stop, .. } => (*start..=*stop).contains(&symbol),
456            Self::Set { set, .. } => set.contains(symbol),
457            Self::NotSet { set, .. } => {
458                (min_vocabulary..=max_vocabulary).contains(&symbol) && !set.contains(symbol)
459            }
460            Self::Wildcard { .. } => (min_vocabulary..=max_vocabulary).contains(&symbol),
461            Self::Epsilon { .. }
462            | Self::Rule { .. }
463            | Self::Predicate { .. }
464            | Self::Action { .. }
465            | Self::Precedence { .. } => false,
466        }
467    }
468}
469
470/// Ordered set of integer intervals used by set and negated-set transitions.
471///
472/// Unicode grammars can contain very large ranges, so this stores normalized
473/// intervals rather than expanding every code point into a flat set.
474#[derive(Clone, Debug, Default, Eq, PartialEq)]
475pub struct IntervalSet {
476    ranges: Vec<(i32, i32)>,
477}
478
479impl IntervalSet {
480    pub fn new() -> Self {
481        Self::default()
482    }
483
484    pub fn from_range(start: i32, stop: i32) -> Self {
485        let mut set = Self::new();
486        set.add_range(start, stop);
487        set
488    }
489
490    pub fn add(&mut self, value: i32) {
491        self.add_range(value, value);
492    }
493
494    /// Adds an inclusive interval and merges it with adjacent or overlapping
495    /// intervals.
496    pub fn add_range(&mut self, start: i32, stop: i32) {
497        let (start, stop) = if start <= stop {
498            (start, stop)
499        } else {
500            (stop, start)
501        };
502        self.ranges.push((start, stop));
503        self.normalize();
504    }
505
506    /// Re-sorts and coalesces interval storage after insertion.
507    fn normalize(&mut self) {
508        self.ranges.sort_unstable();
509        let mut merged: Vec<(i32, i32)> = Vec::with_capacity(self.ranges.len());
510        for (start, stop) in self.ranges.drain(..) {
511            if let Some((_, last_stop)) = merged.last_mut() {
512                if start <= last_stop.saturating_add(1) {
513                    *last_stop = (*last_stop).max(stop);
514                    continue;
515                }
516            }
517            merged.push((start, stop));
518        }
519        self.ranges = merged;
520    }
521
522    /// Returns true when `value` falls inside any stored interval.
523    pub fn contains(&self, value: i32) -> bool {
524        // Ranges are kept sorted and coalesced by `normalize`, so the first
525        // range whose `start > value` cannot contain `value` and neither can
526        // any range after it. Binary searching for that boundary turns
527        // membership lookup from O(n) to O(log n), which matters because
528        // parser/lexer hot paths call this once per `Set`/`NotSet`/`Wildcard`
529        // transition probe.
530        match self.ranges.binary_search_by(|(start, _)| start.cmp(&value)) {
531            Ok(_) => true,
532            Err(pos) => pos > 0 && self.ranges[pos - 1].1 >= value,
533        }
534    }
535
536    pub fn ranges(&self) -> &[(i32, i32)] {
537        &self.ranges
538    }
539
540    pub const fn is_empty(&self) -> bool {
541        self.ranges.is_empty()
542    }
543}
544
545/// Serialized lexer action attached to an action transition.
546///
547/// These actions are grammar-independent operations generated by ANTLR's lexer
548/// commands (`skip`, `more`, `type`, `channel`, `pushMode`, `popMode`, and
549/// `mode`). Custom embedded actions are represented but intentionally inert
550/// until a generated semantic-action hook exists.
551#[derive(Clone, Debug, Eq, PartialEq)]
552pub enum LexerAction {
553    Channel(i32),
554    Custom { rule_index: i32, action_index: i32 },
555    Mode(i32),
556    More,
557    PopMode,
558    PushMode(i32),
559    Skip,
560    Type(i32),
561}
562
563#[cfg(test)]
564mod tests {
565    use super::*;
566
567    fn classified_lexer_rule(continuations: Vec<(usize, LexerTransition)>) -> LexerAtn {
568        let mut atn = LexerAtn::new(4);
569        for (kind, rule_index) in [
570            (AtnStateKind::RuleStart, 0),
571            (AtnStateKind::Basic, 0),
572            (AtnStateKind::Basic, 0),
573            (AtnStateKind::RuleStop, 0),
574            (AtnStateKind::RuleStart, 1),
575            (AtnStateKind::RuleStop, 1),
576            (AtnStateKind::RuleStart, 2),
577            (AtnStateKind::RuleStop, 2),
578            (AtnStateKind::Basic, 0),
579            (AtnStateKind::Basic, 0),
580        ] {
581            let state_number = atn.states.len();
582            atn.add_state(LexerAtnState::new(state_number, kind).with_rule_index(rule_index));
583        }
584        atn.set_rule_to_start_state(vec![0, 4, 6]);
585        atn.set_rule_to_stop_state(vec![3, 5, 7]);
586        atn.state_mut(0)
587            .expect("caller start")
588            .add_transition(LexerTransition::Epsilon { target: 1 });
589        atn.state_mut(1)
590            .expect("call source")
591            .add_transition(LexerTransition::Rule {
592                target: 4,
593                rule_index: 1,
594                follow_state: 2,
595                precedence: 0,
596                tail_call: false,
597            });
598        atn.state_mut(4)
599            .expect("callee start")
600            .add_transition(LexerTransition::Epsilon { target: 5 });
601        atn.state_mut(6)
602            .expect("other rule start")
603            .add_transition(LexerTransition::Epsilon { target: 7 });
604        for (source, transition) in continuations {
605            atn.state_mut(source)
606                .expect("continuation source")
607                .add_transition(transition);
608        }
609        atn.identify_tail_calls();
610        atn
611    }
612
613    fn classified_lexer_call(atn: &LexerAtn) -> &LexerTransition {
614        &atn.state(1).expect("call source").transitions[0]
615    }
616
617    #[test]
618    fn lexer_tail_call_classifier_is_conservative() {
619        let positive = classified_lexer_rule(vec![
620            (2, LexerTransition::Epsilon { target: 8 }),
621            (8, LexerTransition::Epsilon { target: 3 }),
622        ]);
623        assert!(classified_lexer_call(&positive).is_tail_call());
624
625        let rejected = [
626            ("dead end", Vec::new()),
627            (
628                "consuming edge",
629                vec![(
630                    2,
631                    LexerTransition::Atom {
632                        target: 3,
633                        label: 1,
634                    },
635                )],
636            ),
637            (
638                "predicate",
639                vec![(
640                    2,
641                    LexerTransition::Predicate {
642                        target: 3,
643                        rule_index: 0,
644                        pred_index: 0,
645                        context_dependent: false,
646                    },
647                )],
648            ),
649            (
650                "action",
651                vec![(
652                    2,
653                    LexerTransition::Action {
654                        target: 3,
655                        rule_index: 0,
656                        action_index: Some(0),
657                        context_dependent: false,
658                    },
659                )],
660            ),
661            (
662                "nested rule",
663                vec![(
664                    2,
665                    LexerTransition::Rule {
666                        target: 4,
667                        rule_index: 1,
668                        follow_state: 3,
669                        precedence: 0,
670                        tail_call: false,
671                    },
672                )],
673            ),
674            (
675                "epsilon cycle",
676                vec![(2, LexerTransition::Epsilon { target: 2 })],
677            ),
678            (
679                "other rule stop",
680                vec![(2, LexerTransition::Epsilon { target: 7 })],
681            ),
682        ];
683        for (label, continuations) in rejected {
684            let atn = classified_lexer_rule(continuations);
685            assert!(
686                !classified_lexer_call(&atn).is_tail_call(),
687                "{label} must not be classified as a lexer tail call"
688            );
689        }
690    }
691
692    #[test]
693    fn interval_set_handles_ranges() {
694        let set = IntervalSet::from_range(2, 4);
695        assert!(set.contains(2));
696        assert!(set.contains(3));
697        assert!(set.contains(4));
698        assert!(!set.contains(5));
699        assert_eq!(set.ranges(), &[(2, 4)]);
700    }
701}
antlr4_runtime/atn/mod.rs

antlr4_runtime/atn/
mod.rs
