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

antlr4_runtime/atn/
mod.rs
