antlr4_runtime/atn/
mod.rs

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

antlr4_runtime/atn/
mod.rs
