1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
use std::borrow::Cow;
use std::collections::HashMap;
use std::pin::Pin;
use crate::atn_state::ATNState;
use crate::atn_state::ATNStateRef;
use crate::atn_type::ATNType;
use crate::interval_set::IntervalSet;
use crate::interval_set::IntervalSetBuf;
use crate::lexer_action::LexerAction;
use crate::ll1_analyzer::LL1Analyzer;
use crate::token::Token;
use crate::token::{TOKEN_EOF, TOKEN_EPSILON};
use crate::transition::RuleTransition;
use crate::tree::NodeKindType;
use crate::tree::TreeNode;
use std::fmt::{Debug, Formatter};
pub const INVALID_ALT: i32 = 0;
/// Augmented Transition Network
///
/// Basically NFA(graph) of states and possible(maybe multiple) transitions on a
/// given particular symbol.
///
/// Public mostly because of implementations reasons. From user side is only
/// useful for advanced error handling.
///
/// An [`ATN`] is never deallocated: the simulators and DFAs hold
/// [`ATNStateRef`] pointers into it and share them dynamically, so they only
/// accept a `&'static ATN`. Build or deserialize an ATN once, then leak it with
/// [`ATN::into_static`].
pub struct ATN {
pub decision_to_state: Vec<ATNStateRef>,
pub grammar_type: ATNType,
pub lexer_actions: Vec<LexerAction<'static>>,
pub max_token_type: i32,
pub mode_name_to_start_state: HashMap<String, ATNStateRef>,
pub mode_to_start_state: Vec<ATNStateRef>,
pub rule_to_start_state: Vec<ATNStateRef>,
pub rule_to_stop_state: Vec<ATNStateRef>,
pub rule_to_token_type: Vec<i32>,
states: Vec<Pin<Box<ATNState>>>,
/// The static parser DFA tables decoded from the packed ATN's `SDFA` tail.
pub(crate) static_dfas: crate::dfa::static_parser_dfa::StaticParserTables,
}
impl Debug for ATN {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
f.debug_struct("ATN")
.field("grammar_type", &self.grammar_type)
.field("max_token_type", &self.max_token_type)
.field("states count", &self.states.len())
.field("..", &"..")
.finish()
}
}
impl ATN {
/// Creates an empty ATN.
///
/// Start here, both in the word-stream deserializers and in grammar
/// compilers that build an ATN directly. Fill the states with
/// [`Self::alloc_states`] and [`Self::add_state`], then fill the rule,
/// mode, decision, and lexer action tables.
pub fn new(grammar_type: ATNType, max_token_type: i32) -> ATN {
ATN {
decision_to_state: Vec::new(),
grammar_type,
lexer_actions: vec![],
max_token_type,
mode_name_to_start_state: HashMap::new(),
mode_to_start_state: Vec::new(),
rule_to_start_state: Vec::new(),
rule_to_stop_state: Vec::new(),
rule_to_token_type: Vec::new(),
states: Vec::new(),
static_dfas: crate::dfa::static_parser_dfa::StaticParserTables::empty(),
}
}
/// The static parser SLL DFA tables of this ATN, empty when the unit was
/// generated without `--static-parser-dfa`.
pub fn static_dfas(&self) -> &crate::dfa::static_parser_dfa::StaticParserTables {
&self.static_dfas
}
/// Leaks this ATN for the rest of the process and returns a `'static`
/// handle to it.
///
/// The ATN layer is built on the convention of one ATN per recognizer that
/// is never deallocated: DFAs and simulators store [`ATNStateRef`] pointers
/// into the ATN, and they share those pointers dynamically, so no shorter
/// lifetime can be expressed. Every consumer that builds an ATN at run
/// time calls this once, before handing the ATN to a simulator.
#[must_use]
pub fn into_static(self) -> &'static ATN {
Box::leak(Box::new(self))
}
///Compute the set of valid tokens that can occur starting in `s` and
///staying in same rule. `Token::EPSILON` is in set if we reach end of
///rule.
pub fn next_tokens<'a, Tok: Token>(&'a self, s: &ATNStateRef) -> &'a IntervalSet {
s.get_next_tokens_within_rule::<Tok>(self)
}
/// Compute the set of valid tokens that can occur starting in state `s`.
/// If `ctx` is null, the set of tokens will not include what can follow
/// the rule surrounding `s`. In other words, the set will be
/// restricted to tokens reachable staying within `s`'s rule.
pub fn next_tokens_in_ctx<'input, 'arena, Node, Tok>(
&self,
s: ATNStateRef,
ctx: Option<&'arena TreeNode<'input, 'arena, Node, Tok>>,
) -> IntervalSetBuf
where
'input: 'arena,
Node: NodeKindType<'arena, Tok>,
Tok: Token + 'input,
{
let analyzer = LL1Analyzer::new(self);
analyzer.look(s, None, ctx)
}
/// Installs `state` at the slot reserved by [`Self::alloc_states`] for its
/// state number.
///
/// This is the construction path shared by the word-stream deserializers
/// and by grammar compilers that build an [`ATN`] directly.
pub fn add_state(&mut self, state: ATNState) {
let state_number = state.get_state_number();
assert!(
usize::try_from(state_number).is_ok_and(|number| number < self.states.len()),
"state number {state_number} is not an allocated state slot"
);
*self.get_state_mut(state_number) = state;
}
/// Reserves `count` state slots after the existing states.
///
/// Reserved states are placeholders until [`Self::add_state`] installs a
/// real state for their number. State references stay valid across
/// installation because the states are boxed.
pub fn alloc_states(&mut self, count: usize) {
self.states
.resize_with(self.states.len() + count, || Box::pin(ATNState::default()));
}
pub fn get_decision_state(&self, decision: i32) -> ATNStateRef {
self.decision_to_state[decision as usize]
}
pub fn make_state_ref(&self, state_number: i32) -> ATNStateRef {
ATNStateRef::from(&self.states[state_number as usize])
}
pub fn get_state(&self, state_number: i32) -> &ATNState {
&self.states[state_number as usize]
}
pub fn get_state_mut(&mut self, state_number: i32) -> &mut ATNState {
&mut self.states[state_number as usize]
}
pub fn iter_states(&self) -> impl Iterator<Item = &ATNState> {
self.states.iter().map(|s| &**s)
}
pub fn states_count(&self) -> usize {
self.states.len()
}
/// Computes the set of input symbols which could follow ATN state number
/// {@code stateNumber} in the specified full {@code context}. This method
/// considers the complete parser context, but does not evaluate semantic
/// predicates (i.e. all predicates encountered during the calculation are
/// assumed true). If a path in the ATN exists from the starting state to the
/// {@link RuleStopState} of the outermost context without matching any
/// symbols, {@link Token#EOF} is added to the returned set.
///
/// <p>If {@code context} is {@code null}, it is treated as {@link ParserRuleContext#EMPTY}.</p>
///
/// Note that this does NOT give you the set of all tokens that could
/// appear at a given token position in the input phrase. In other words,
/// it does not answer:
///
/// "Given a specific partial input phrase, return the set of all tokens
/// that can follow the last token in the input phrase."
///
/// The big difference is that with just the input, the parser could
/// land right in the middle of a lookahead decision. Getting
/// all *possible* tokens given a partial input stream is a separate
/// computation. See https://github.com/antlr/antlr4/issues/1428
///
/// For this function, we are specifying an ATN state and call stack to compute
/// what token(s) can come next and specifically: outside of a lookahead decision.
/// That is what you want for error reporting and recovery upon parse error.
///
/// @param stateNumber the ATN state number
/// @param context the full parse context
/// @return The set of potentially valid input symbols which could follow the
/// specified state in the specified context.
/// Panics if the ATN does not contain a state with
/// number {@code stateNumber}
pub fn get_expected_tokens<'a, Tok: Token>(
&'a self,
state_number: i32,
states_stack: impl Iterator<Item = i32>, // _ctx: &Rc<Ctx::Type>,
) -> Cow<'a, IntervalSet> {
let s = self.make_state_ref(state_number);
let mut following = self.next_tokens::<Tok>(&s);
if !following.contains(TOKEN_EPSILON) {
return Cow::Borrowed(following);
}
let mut expected = IntervalSetBuf::new();
expected.add_set(following);
expected.remove_one(TOKEN_EPSILON);
// let mut ctx = Some(Rc::clone(_ctx));
for state in states_stack {
if !following.contains(TOKEN_EPSILON) {
break;
}
let invoking_state = &self.states[state as usize];
let tr = invoking_state.get_transitions().first().unwrap();
let tr = tr.try_as::<RuleTransition>().unwrap();
following = self.next_tokens::<Tok>(&tr.follow_state);
expected.add_set(following);
expected.remove_one(TOKEN_EPSILON);
// ctx = c.get_parent_ctx();
}
if following.contains(TOKEN_EPSILON) {
expected.add_one(TOKEN_EOF);
}
Cow::Owned(expected)
}
}