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

antlr4_runtime/atn/
mod.rs
