antlr4_runtime/atn/
mod.rs

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

antlr4_runtime/atn/
mod.rs
