Line data Source code
1 : //! The LALR(1) driver, the `parse()` loop of bison's lalr1.cc skeleton configured with
2 : //! `parse.lac full`, `parse.error verbose` plus an error hint, error recovery through the `error`
3 : //! token, and a custom default location for reductions.
4 :
5 : use super::actions::{ReduceError, ReduceStack};
6 : use super::context::ParseContext;
7 : use super::value::Value;
8 : use crate::scanner::SymbolValue;
9 : use crate::symbol_kind::*;
10 : use crate::tables::*;
11 : use crate::{symbol_name, SymbolKind};
12 : use dashql_buffers::parser::SymbolSpan;
13 :
14 : /// A parser state
15 : pub type StateId = i32;
16 :
17 : /// The state of `goto` after reducing to `lhs` in `state` (`yy_lr_goto_state_`)
18 17495038 : pub fn goto_state(state: StateId, lhs: SymbolKind) -> StateId {
19 17495038 : let nterm = lhs as usize - YYNTOKENS;
20 17495038 : let r = YYPGOTO[nterm] as i32 + state;
21 17495038 : if (0..=YYLAST).contains(&r) && YYCHECK[r as usize] as i32 == state {
22 9280473 : YYTABLE[r as usize] as i32
23 : } else {
24 8214565 : YYDEFGOTO[nterm] as i32
25 : }
26 17495038 : }
27 :
28 : /// The action of a state on a token: `Some(Shift(state))`, `Some(Reduce(rule))`, or `None` for the
29 : /// default action (or an error if the default is to fail).
30 : #[derive(Clone, Copy, Debug, PartialEq, Eq)]
31 : pub enum Action {
32 : Shift(StateId),
33 : Reduce(usize),
34 : Error,
35 : }
36 :
37 : /// The table action of `state` on `token`, `None` if the default action applies
38 20532611 : pub fn table_action(state: StateId, token: SymbolKind) -> Option<Action> {
39 20532611 : let pact = YYPACT[state as usize] as i32;
40 20532611 : if pact == YYPACT_NINF {
41 3028649 : return None;
42 17503962 : }
43 17503962 : let i = pact + token as i32;
44 17503962 : if !(0..=YYLAST).contains(&i) || YYCHECK[i as usize] as i32 != token as i32 {
45 15452360 : return None;
46 2051602 : }
47 2051602 : let action = YYTABLE[i as usize] as i32;
48 2051602 : Some(if action > 0 {
49 1931592 : Action::Shift(action)
50 120010 : } else if action == YYTABLE_NINF {
51 96 : Action::Error
52 : } else {
53 119914 : Action::Reduce(-action as usize)
54 : })
55 20532611 : }
56 :
57 : /// Would the parser eventually shift `token` from the given stack of states? (`yy_lac_check_`)
58 : ///
59 : /// Simulates the reductions on a scratch stack, the stack itself is not modified.
60 3300286 : pub fn lac_check(states: &[StateId], token: SymbolKind, scratch: &mut Vec<StateId>) -> bool {
61 3300286 : scratch.clear();
62 : // The number of states popped from `states`
63 3300286 : let mut lac_top = 0;
64 : loop {
65 19179743 : let top_state = *scratch.last().unwrap_or(&states[states.len() - 1 - lac_top]);
66 19179743 : let rule = match table_action(top_state, token) {
67 1440233 : Some(Action::Shift(_)) => return true,
68 96 : Some(Action::Error) => return false,
69 77293 : Some(Action::Reduce(rule)) => rule,
70 17662121 : None => match YYDEFACT[top_state as usize] as usize {
71 1859957 : 0 => return false,
72 15802164 : rule => rule,
73 : },
74 : };
75 : // Pop the right-hand side, first from the scratch stack
76 15879457 : let mut len = YYR2[rule] as usize;
77 15879457 : if len < scratch.len() {
78 6255103 : scratch.truncate(scratch.len() - len);
79 6255103 : len = 0;
80 9628549 : } else if !scratch.is_empty() {
81 7576848 : len -= scratch.len();
82 7576848 : scratch.clear();
83 7576848 : }
84 15879457 : lac_top += len;
85 15879457 : let top_state = *scratch.last().unwrap_or(&states[states.len() - 1 - lac_top]);
86 15879457 : scratch.push(goto_state(top_state, YYR1[rule] as SymbolKind));
87 : }
88 3300286 : }
89 :
90 : /// Feed a token to a stack of states: reduce until the token is shifted. Returns false (and leaves
91 : /// the stack in an unspecified state) if the token is a syntax error.
92 0 : pub fn feed(states: &mut Vec<StateId>, token: SymbolKind) -> bool {
93 : loop {
94 0 : let top = *states.last().unwrap();
95 0 : let rule = match table_action(top, token) {
96 0 : Some(Action::Shift(next)) => {
97 0 : states.push(next);
98 0 : return true;
99 : }
100 0 : Some(Action::Error) => return false,
101 0 : Some(Action::Reduce(rule)) => rule,
102 0 : None => match YYDEFACT[top as usize] as usize {
103 0 : 0 => return false,
104 0 : rule => rule,
105 : },
106 : };
107 0 : let len = YYR2[rule] as usize;
108 0 : states.truncate(states.len() - len);
109 0 : let next = goto_state(*states.last().unwrap(), YYR1[rule] as SymbolKind);
110 0 : states.push(next);
111 : }
112 0 : }
113 :
114 : /// The location of the left-hand side of a reduction (bison's `YYLLOC_DEFAULT`).
115 : /// Uses wrapping uint32 arithmetic.
116 943117 : fn default_location(rhs: &[SymbolSpan], below: SymbolSpan) -> SymbolSpan {
117 943117 : match (rhs.first(), rhs.last()) {
118 789561 : (Some(first), Some(last)) => SymbolSpan::new(
119 789561 : first.offset(),
120 789561 : last.offset().wrapping_add(last.length()).wrapping_sub(first.offset()),
121 : ),
122 153556 : _ => SymbolSpan::new(below.offset().wrapping_add(below.length()), 0),
123 : }
124 943117 : }
125 :
126 : /// A lookahead token
127 : #[derive(Clone, Copy, Debug)]
128 : struct Lookahead {
129 : /// The token kind
130 : kind: SymbolKind,
131 : /// The semantic value of the token
132 : value: Value,
133 : }
134 :
135 : /// The parser stack
136 : struct Stack {
137 : /// The automaton states
138 : states: Vec<StateId>,
139 : /// The semantic values, parallel to the states
140 : values: Vec<Value>,
141 : /// The symbol-index locations, parallel to the states
142 : locations: Vec<SymbolSpan>,
143 : }
144 :
145 : impl Stack {
146 1292348 : fn push(&mut self, state: StateId, value: Value, location: SymbolSpan) {
147 1292348 : self.states.push(state);
148 1292348 : self.values.push(value);
149 1292348 : self.locations.push(location);
150 1292348 : }
151 :
152 943464 : fn pop(&mut self, n: usize) {
153 943464 : let len = self.states.len() - n;
154 943464 : self.states.truncate(len);
155 943464 : self.values.truncate(len);
156 943464 : self.locations.truncate(len);
157 943464 : }
158 :
159 2222231 : fn top(&self) -> StateId {
160 2222231 : *self.states.last().unwrap()
161 2222231 : }
162 : }
163 :
164 : impl ReduceStack for Stack {
165 1070411 : fn value_at(&self, i: usize) -> Value {
166 1070411 : self.values[self.values.len() - 1 - i]
167 1070411 : }
168 273021 : fn location_at(&self, i: usize) -> SymbolSpan {
169 273021 : self.locations[self.locations.len() - 1 - i]
170 273021 : }
171 : }
172 :
173 : /// The token stream of the parser: scanned symbols located by their
174 : /// index, followed by EOF tokens of length 0 once the symbols are exhausted.
175 : pub struct TokenStream {
176 : /// The index of the next symbol to return
177 : pub next_index: u32,
178 : }
179 :
180 : impl TokenStream {
181 349971 : pub fn next(&mut self, ctx: &ParseContext) -> (SymbolKind, Value, SymbolSpan) {
182 349971 : let index = self.next_index;
183 349971 : match ctx.symbols().get(index as usize) {
184 349856 : Some(symbol) => {
185 349856 : self.next_index += 1;
186 349856 : let value = match symbol.value {
187 155357 : SymbolValue::None => Value::Empty,
188 102210 : SymbolValue::Name(id) => Value::Name(id),
189 92289 : SymbolValue::Text(text) => Value::Str(text),
190 : };
191 349856 : (symbol.kind, value, SymbolSpan::new(index, 1))
192 : }
193 115 : None => (S_YYEOF, Value::Empty, SymbolSpan::new(index, 0)),
194 : }
195 349971 : }
196 : }
197 :
198 : /// Where the parse loop continues
199 : enum Label {
200 : NewState,
201 : Default,
202 : Reduce(usize),
203 : ErrLab,
204 : ErrLab1,
205 : }
206 :
207 : /// Build the verbose syntax error message (`yysyntax_error_`) and its hint.
208 357 : fn syntax_error(states: &[StateId], lookahead: Option<SymbolKind>, scratch: &mut Vec<StateId>) -> (String, String) {
209 : const ARGS_MAX: usize = 5;
210 357 : let Some(token) = lookahead else {
211 0 : return ("syntax error".to_string(), String::new());
212 : };
213 357 : let mut args = vec![token];
214 357 : let mut overflow = false;
215 44581 : for t in 0..YYNTOKENS as SymbolKind {
216 44581 : if t == S_YYerror || t == S_YYUNDEF || !lac_check(states, t, scratch) {
217 42925 : continue;
218 1656 : }
219 1656 : if args.len() == ARGS_MAX {
220 317 : overflow = true;
221 317 : break;
222 1339 : }
223 1339 : args.push(t);
224 : }
225 357 : if overflow {
226 317 : args.truncate(1);
227 317 : }
228 428 : let names: Vec<_> = args.iter().map(|&a| symbol_name(a)).collect();
229 357 : let mut message = format!("syntax error, unexpected {}", names[0]);
230 357 : for (i, name) in names.iter().enumerate().skip(1) {
231 71 : message.push_str(if i == 1 { ", expecting " } else { " or " });
232 71 : message.push_str(name);
233 : }
234 : // Suggest a double-quoted identifier when a string literal is used where an identifier fits.
235 357 : let hint = if token == S_SCONST && lac_check(states, S_IDENT, scratch) {
236 5 : "string literals cannot be used as identifiers here; use a double-quoted identifier instead".to_string()
237 : } else {
238 352 : String::new()
239 : };
240 357 : (message, hint)
241 357 : }
242 :
243 : /// Run the parser with the grammar actions. Returns false if parsing was aborted.
244 7918 : pub fn parse(ctx: &mut ParseContext) -> bool {
245 7918 : let mut stack = Stack {
246 7918 : states: vec![0],
247 7918 : values: vec![Value::Empty],
248 7918 : locations: vec![SymbolSpan::default()],
249 7918 : };
250 7918 : let mut tokens = TokenStream { next_index: 0 };
251 7918 : let mut lookahead: Option<Lookahead> = None;
252 : // The location of the lookahead; it outlives the lookahead itself, like bison's yyla.location.
253 7918 : let mut lookahead_location = SymbolSpan::default();
254 7918 : let mut lac_established = false;
255 7918 : let mut scratch = Vec::new();
256 7918 : let mut errstatus = 0;
257 7918 : let mut error_range_begin = SymbolSpan::default();
258 7918 : let mut label = Label::NewState;
259 :
260 : loop {
261 3164308 : label = match label {
262 : Label::NewState => {
263 1300266 : let state = stack.top();
264 1300266 : if state == YYFINAL {
265 7891 : return true;
266 1292375 : }
267 1292375 : if YYPACT[state as usize] as i32 == YYPACT_NINF {
268 488999 : Label::Default
269 : } else {
270 803376 : let la = match lookahead {
271 453405 : Some(la) => la,
272 : None => {
273 349971 : let (kind, value, location) = tokens.next(ctx);
274 349971 : lookahead_location = location;
275 349971 : let la = Lookahead { kind, value };
276 349971 : lookahead = Some(la);
277 349971 : la
278 : }
279 : };
280 803376 : let mut establish = |stack: &Stack| {
281 454145 : if !lac_established {
282 159368 : lac_established = true;
283 159368 : return lac_check(&stack.states, la.kind, &mut scratch);
284 294777 : }
285 294777 : true
286 454145 : };
287 803376 : match table_action(state, la.kind) {
288 : None => {
289 431920 : if establish(&stack) {
290 431179 : Label::Default
291 : } else {
292 741 : Label::ErrLab
293 : }
294 : }
295 0 : Some(Action::Error) => Label::ErrLab,
296 22225 : Some(Action::Reduce(rule)) => {
297 22225 : if establish(&stack) {
298 22219 : Label::Reduce(rule)
299 : } else {
300 6 : Label::ErrLab
301 : }
302 : }
303 349231 : Some(Action::Shift(next)) => {
304 349231 : if errstatus > 0 {
305 486 : errstatus -= 1;
306 348745 : }
307 349231 : stack.push(next, la.value, lookahead_location);
308 349231 : lookahead = None;
309 349231 : lac_established = false;
310 349231 : Label::NewState
311 : }
312 : }
313 : }
314 : }
315 920178 : Label::Default => match YYDEFACT[stack.top() as usize] as usize {
316 0 : 0 => Label::ErrLab,
317 920178 : rule => Label::Reduce(rule),
318 : },
319 942397 : Label::Reduce(rule) => {
320 942397 : let len = YYR2[rule] as usize;
321 942397 : let n = stack.states.len();
322 942397 : let lhs_state = goto_state(stack.states[n - 1 - len], YYR1[rule] as SymbolKind);
323 942397 : let location = default_location(&stack.locations[n - len..], stack.locations[n - 1]);
324 942397 : error_range_begin = location;
325 942397 : match reduce(ctx, rule, &stack, location) {
326 942397 : Ok(value) => {
327 942397 : if std::mem::take(&mut ctx.state.borrow_mut().clear_lookahead) {
328 713 : lookahead = None;
329 941684 : }
330 942397 : stack.pop(len);
331 942397 : stack.push(lhs_state, value.unwrap_or(Value::Empty), location);
332 942397 : Label::NewState
333 : }
334 : Err(ReduceError::YyError) => {
335 0 : if std::mem::take(&mut ctx.state.borrow_mut().clear_lookahead) {
336 0 : lookahead = None;
337 0 : }
338 : // yyerrorlab: do not reclaim the symbols of the rule
339 0 : stack.pop(len);
340 0 : Label::ErrLab1
341 : }
342 : }
343 : }
344 : Label::ErrLab => {
345 747 : if errstatus == 0 {
346 357 : let (message, hint) = syntax_error(&stack.states, lookahead.map(|la| la.kind), &mut scratch);
347 357 : ctx.state.borrow_mut().pending_hint = hint;
348 357 : ctx.error(lookahead_location, &message);
349 390 : }
350 747 : error_range_begin = lookahead_location;
351 747 : if errstatus == 3 {
352 : // Discard the lookahead that failed to be reused after an error
353 359 : match lookahead {
354 359 : Some(la) if la.kind == S_YYEOF => return false,
355 332 : Some(_) => lookahead = None,
356 0 : None => {}
357 : }
358 388 : }
359 720 : Label::ErrLab1
360 : }
361 : Label::ErrLab1 => {
362 720 : errstatus = 3;
363 : // Pop states until one shifts the error token
364 720 : let next = loop {
365 1787 : if let Some(Action::Shift(next)) = table_action(stack.top(), S_YYerror) {
366 720 : break next;
367 1067 : }
368 1067 : if stack.states.len() == 1 {
369 0 : return false;
370 1067 : }
371 1067 : error_range_begin = *stack.locations.last().unwrap();
372 1067 : stack.pop(1);
373 : };
374 720 : let error_location = default_location(&[error_range_begin, lookahead_location], SymbolSpan::default());
375 720 : lac_established = false;
376 720 : stack.push(next, Value::Empty, error_location);
377 720 : Label::NewState
378 : }
379 : };
380 : }
381 7918 : }
382 :
383 : /// Run the action of a rule
384 942397 : fn reduce(ctx: &mut ParseContext, rule: usize, stack: &Stack, location: SymbolSpan) -> Result<Option<Value>, ReduceError> {
385 942397 : crate::tables::reduce(ctx, rule, stack, location)
386 942397 : }
387 :
388 : #[cfg(test)]
389 : mod tests {
390 : use super::*;
391 :
392 : #[test]
393 1 : fn rejects_unknown_tokens() {
394 1 : let mut scratch = Vec::new();
395 1 : assert!(lac_check(&[0], S_SELECT, &mut scratch));
396 1 : assert!(!lac_check(&[0], S_RRB, &mut scratch));
397 1 : }
398 : }
|
