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

antlr4_runtime/atn/
mod.rs
