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/// Deserialized lexer Abstract Transition Network.
19///
20/// The structure keeps the state graph plus ANTLR side tables such as
21/// rule-to-start, rule-to-token, mode-to-start, decisions, and actions. Parser
22/// ATNs never use this object-graph representation.
23#[derive(Clone, Debug, Eq, PartialEq)]
24pub struct LexerAtn {
25    max_token_type: i32,
26    states: Vec<LexerAtnState>,
27    rule_to_start_state: Vec<usize>,
28    rule_to_stop_state: Vec<usize>,
29    rule_to_token_type: Vec<i32>,
30    mode_to_start_state: Vec<usize>,
31    decision_to_state: Vec<usize>,
32    lexer_actions: Vec<LexerAction>,
33}
34
35impl LexerAtn {
36    /// Creates an empty lexer ATN with the maximum token type read from the
37    /// serialized header.
38    pub const fn new(max_token_type: i32) -> Self {
39        Self {
40            max_token_type,
41            states: Vec::new(),
42            rule_to_start_state: Vec::new(),
43            rule_to_stop_state: Vec::new(),
44            rule_to_token_type: Vec::new(),
45            mode_to_start_state: Vec::new(),
46            decision_to_state: Vec::new(),
47            lexer_actions: Vec::new(),
48        }
49    }
50
51    pub const fn max_token_type(&self) -> i32 {
52        self.max_token_type
53    }
54
55    pub fn states(&self) -> &[LexerAtnState] {
56        &self.states
57    }
58
59    pub fn state(&self, state_number: usize) -> Option<&LexerAtnState> {
60        self.states.get(state_number)
61    }
62
63    pub fn state_mut(&mut self, state_number: usize) -> Option<&mut LexerAtnState> {
64        self.states.get_mut(state_number)
65    }
66
67    /// Appends a state and returns the state number assigned by insertion
68    /// order.
69    pub fn add_state(&mut self, state: LexerAtnState) -> usize {
70        let index = self.states.len();
71        self.states.push(state);
72        index
73    }
74
75    pub fn decision_to_state(&self) -> &[usize] {
76        &self.decision_to_state
77    }
78
79    pub fn add_decision_state(&mut self, state_number: usize) {
80        self.decision_to_state.push(state_number);
81    }
82
83    pub fn rule_to_start_state(&self) -> &[usize] {
84        &self.rule_to_start_state
85    }
86
87    pub fn set_rule_to_start_state(&mut self, rule_to_start_state: Vec<usize>) {
88        self.rule_to_start_state = rule_to_start_state;
89    }
90
91    pub fn rule_to_stop_state(&self) -> &[usize] {
92        &self.rule_to_stop_state
93    }
94
95    pub fn set_rule_to_stop_state(&mut self, rule_to_stop_state: Vec<usize>) {
96        self.rule_to_stop_state = rule_to_stop_state;
97    }
98
99    pub fn rule_to_token_type(&self) -> &[i32] {
100        &self.rule_to_token_type
101    }
102
103    pub fn set_rule_to_token_type(&mut self, rule_to_token_type: Vec<i32>) {
104        self.rule_to_token_type = rule_to_token_type;
105    }
106
107    pub fn mode_to_start_state(&self) -> &[usize] {
108        &self.mode_to_start_state
109    }
110
111    pub fn add_mode_start_state(&mut self, state_number: usize) {
112        self.mode_to_start_state.push(state_number);
113    }
114
115    pub fn lexer_actions(&self) -> &[LexerAction] {
116        &self.lexer_actions
117    }
118
119    pub fn set_lexer_actions(&mut self, lexer_actions: Vec<LexerAction>) {
120        self.lexer_actions = lexer_actions;
121    }
122}
123
124/// A node in the ANTLR ATN graph.
125///
126/// Some ANTLR state subclasses carry references to paired states, such as a
127/// block-start state's end state or a loop-end state's loop-back state. This
128/// representation stores those links as state numbers so the graph remains easy
129/// to clone and serialize in tests.
130#[derive(Clone, Debug, Eq, PartialEq)]
131pub struct LexerAtnState {
132    pub state_number: usize,
133    pub rule_index: Option<usize>,
134    pub kind: AtnStateKind,
135    pub end_state: Option<usize>,
136    pub loop_back_state: Option<usize>,
137    pub non_greedy: bool,
138    pub precedence_rule_decision: bool,
139    pub left_recursive_rule: bool,
140    pub transitions: Vec<LexerTransition>,
141}
142
143impl LexerAtnState {
144    /// Creates an ATN state with no rule index and no outgoing transitions.
145    pub const fn new(state_number: usize, kind: AtnStateKind) -> Self {
146        Self {
147            state_number,
148            rule_index: None,
149            kind,
150            end_state: None,
151            loop_back_state: None,
152            non_greedy: false,
153            precedence_rule_decision: false,
154            left_recursive_rule: false,
155            transitions: Vec::new(),
156        }
157    }
158
159    #[must_use]
160    pub const fn with_rule_index(mut self, rule_index: usize) -> Self {
161        self.rule_index = Some(rule_index);
162        self
163    }
164
165    /// Adds an outgoing transition in serialized order.
166    ///
167    /// Transition order matters for alternatives and lexer priority, so the
168    /// runtime preserves the order emitted by ANTLR.
169    pub fn add_transition(&mut self, transition: LexerTransition) {
170        self.transitions.push(transition);
171    }
172
173    pub fn is_rule_stop(&self) -> bool {
174        self.kind == AtnStateKind::RuleStop
175    }
176}
177
178/// Serialized ANTLR state kind.
179#[derive(Clone, Copy, Debug, Eq, PartialEq)]
180pub enum AtnStateKind {
181    Invalid,
182    Basic,
183    RuleStart,
184    BlockStart,
185    PlusBlockStart,
186    StarBlockStart,
187    TokenStart,
188    RuleStop,
189    BlockEnd,
190    StarLoopBack,
191    StarLoopEntry,
192    PlusLoopBack,
193    LoopEnd,
194}
195
196/// Edge between two ATN states.
197///
198/// Epsilon-like transitions do not consume input. Matching transitions compare
199/// the current input symbol against an atom, range, set, negated set, or
200/// wildcard.
201#[derive(Clone, Debug, Eq, PartialEq)]
202pub enum LexerTransition {
203    Epsilon {
204        target: usize,
205    },
206    Atom {
207        target: usize,
208        label: i32,
209    },
210    Range {
211        target: usize,
212        start: i32,
213        stop: i32,
214    },
215    Set {
216        target: usize,
217        set: IntervalSet,
218    },
219    NotSet {
220        target: usize,
221        set: IntervalSet,
222    },
223    Wildcard {
224        target: usize,
225    },
226    Rule {
227        target: usize,
228        rule_index: usize,
229        follow_state: usize,
230        precedence: i32,
231    },
232    Predicate {
233        target: usize,
234        rule_index: usize,
235        pred_index: usize,
236        context_dependent: bool,
237    },
238    Action {
239        target: usize,
240        rule_index: usize,
241        action_index: Option<usize>,
242        context_dependent: bool,
243    },
244    Precedence {
245        target: usize,
246        precedence: i32,
247    },
248}
249
250impl LexerTransition {
251    /// Returns the target state number for this transition.
252    pub const fn target(&self) -> usize {
253        match self {
254            Self::Epsilon { target }
255            | Self::Atom { target, .. }
256            | Self::Range { target, .. }
257            | Self::Set { target, .. }
258            | Self::NotSet { target, .. }
259            | Self::Wildcard { target }
260            | Self::Rule { target, .. }
261            | Self::Predicate { target, .. }
262            | Self::Action { target, .. }
263            | Self::Precedence { target, .. } => *target,
264        }
265    }
266
267    /// Returns whether traversing this transition consumes no input.
268    pub const fn is_epsilon(&self) -> bool {
269        matches!(
270            self,
271            Self::Epsilon { .. }
272                | Self::Rule { .. }
273                | Self::Predicate { .. }
274                | Self::Action { .. }
275                | Self::Precedence { .. }
276        )
277    }
278
279    /// Tests whether this transition consumes `symbol`.
280    ///
281    /// `min_vocabulary` and `max_vocabulary` define the accepted symbol range
282    /// for wildcard and negated-set transitions.
283    pub fn matches(&self, symbol: i32, min_vocabulary: i32, max_vocabulary: i32) -> bool {
284        match self {
285            Self::Atom { label, .. } => *label == symbol,
286            Self::Range { start, stop, .. } => (*start..=*stop).contains(&symbol),
287            Self::Set { set, .. } => set.contains(symbol),
288            Self::NotSet { set, .. } => {
289                (min_vocabulary..=max_vocabulary).contains(&symbol) && !set.contains(symbol)
290            }
291            Self::Wildcard { .. } => (min_vocabulary..=max_vocabulary).contains(&symbol),
292            Self::Epsilon { .. }
293            | Self::Rule { .. }
294            | Self::Predicate { .. }
295            | Self::Action { .. }
296            | Self::Precedence { .. } => false,
297        }
298    }
299}
300
301/// Ordered set of integer intervals used by set and negated-set transitions.
302///
303/// Unicode grammars can contain very large ranges, so this stores normalized
304/// intervals rather than expanding every code point into a flat set.
305#[derive(Clone, Debug, Default, Eq, PartialEq)]
306pub struct IntervalSet {
307    ranges: Vec<(i32, i32)>,
308}
309
310impl IntervalSet {
311    pub fn new() -> Self {
312        Self::default()
313    }
314
315    pub fn from_range(start: i32, stop: i32) -> Self {
316        let mut set = Self::new();
317        set.add_range(start, stop);
318        set
319    }
320
321    pub fn add(&mut self, value: i32) {
322        self.add_range(value, value);
323    }
324
325    /// Adds an inclusive interval and merges it with adjacent or overlapping
326    /// intervals.
327    pub fn add_range(&mut self, start: i32, stop: i32) {
328        let (start, stop) = if start <= stop {
329            (start, stop)
330        } else {
331            (stop, start)
332        };
333        self.ranges.push((start, stop));
334        self.normalize();
335    }
336
337    /// Re-sorts and coalesces interval storage after insertion.
338    fn normalize(&mut self) {
339        self.ranges.sort_unstable();
340        let mut merged: Vec<(i32, i32)> = Vec::with_capacity(self.ranges.len());
341        for (start, stop) in self.ranges.drain(..) {
342            if let Some((_, last_stop)) = merged.last_mut() {
343                if start <= last_stop.saturating_add(1) {
344                    *last_stop = (*last_stop).max(stop);
345                    continue;
346                }
347            }
348            merged.push((start, stop));
349        }
350        self.ranges = merged;
351    }
352
353    /// Returns true when `value` falls inside any stored interval.
354    pub fn contains(&self, value: i32) -> bool {
355        // Ranges are kept sorted and coalesced by `normalize`, so the first
356        // range whose `start > value` cannot contain `value` and neither can
357        // any range after it. Binary searching for that boundary turns
358        // membership lookup from O(n) to O(log n), which matters because
359        // parser/lexer hot paths call this once per `Set`/`NotSet`/`Wildcard`
360        // transition probe.
361        match self.ranges.binary_search_by(|(start, _)| start.cmp(&value)) {
362            Ok(_) => true,
363            Err(pos) => pos > 0 && self.ranges[pos - 1].1 >= value,
364        }
365    }
366
367    pub fn ranges(&self) -> &[(i32, i32)] {
368        &self.ranges
369    }
370
371    pub const fn is_empty(&self) -> bool {
372        self.ranges.is_empty()
373    }
374}
375
376/// Serialized lexer action attached to an action transition.
377///
378/// These actions are grammar-independent operations generated by ANTLR's lexer
379/// commands (`skip`, `more`, `type`, `channel`, `pushMode`, `popMode`, and
380/// `mode`). Custom embedded actions are represented but intentionally inert
381/// until a generated semantic-action hook exists.
382#[derive(Clone, Debug, Eq, PartialEq)]
383pub enum LexerAction {
384    Channel(i32),
385    Custom { rule_index: i32, action_index: i32 },
386    Mode(i32),
387    More,
388    PopMode,
389    PushMode(i32),
390    Skip,
391    Type(i32),
392}
393
394#[cfg(test)]
395mod tests {
396    use super::*;
397
398    #[test]
399    fn interval_set_handles_ranges() {
400        let set = IntervalSet::from_range(2, 4);
401        assert!(set.contains(2));
402        assert!(set.contains(3));
403        assert!(set.contains(4));
404        assert!(!set.contains(5));
405        assert_eq!(set.ranges(), &[(2, 4)]);
406    }
407}
antlr4_runtime/atn/mod.rs

antlr4_runtime/atn/
mod.rs
