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 17242035 : pub fn goto_state(state: StateId, lhs: SymbolKind) -> StateId {
19 17242035 : let nterm = lhs as usize - YYNTOKENS;
20 17242035 : let r = YYPGOTO[nterm] as i32 + state;
21 17242035 : if (0..=YYLAST).contains(&r) && YYCHECK[r as usize] as i32 == state {
22 9164770 : YYTABLE[r as usize] as i32
23 : } else {
24 8077265 : YYDEFGOTO[nterm] as i32
25 : }
26 17242035 : }
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 20265967 : pub fn table_action(state: StateId, token: SymbolKind) -> Option<Action> {
39 20265967 : let pact = YYPACT[state as usize] as i32;
40 20265967 : if pact == YYPACT_NINF {
41 2904099 : return None;
42 17361868 : }
43 17361868 : let i = pact + token as i32;
44 17361868 : if !(0..=YYLAST).contains(&i) || YYCHECK[i as usize] as i32 != token as i32 {
45 15284053 : return None;
46 2077815 : }
47 2077815 : let action = YYTABLE[i as usize] as i32;
48 2077815 : Some(if action > 0 {
49 1960737 : Action::Shift(action)
50 117078 : } else if action == YYTABLE_NINF {
51 96 : Action::Error
52 : } else {
53 116982 : Action::Reduce(-action as usize)
54 : })
55 20265967 : }
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 3275339 : pub fn lac_check(states: &[StateId], token: SymbolKind, scratch: &mut Vec<StateId>) -> bool {
61 3275339 : scratch.clear();
62 : // The number of states popped from `states`
63 3275339 : let mut lac_top = 0;
64 : loop {
65 18962649 : let top_state = *scratch.last().unwrap_or(&states[states.len() - 1 - lac_top]);
66 18962649 : let rule = match table_action(top_state, token) {
67 1486009 : Some(Action::Shift(_)) => return true,
68 96 : Some(Action::Error) => return false,
69 75999 : Some(Action::Reduce(rule)) => rule,
70 17400545 : None => match YYDEFACT[top_state as usize] as usize {
71 1789234 : 0 => return false,
72 15611311 : rule => rule,
73 : },
74 : };
75 : // Pop the right-hand side, first from the scratch stack
76 15687310 : let mut len = YYR2[rule] as usize;
77 15687310 : if len < scratch.len() {
78 6143049 : scratch.truncate(scratch.len() - len);
79 6143049 : len = 0;
80 9548471 : } else if !scratch.is_empty() {
81 7479834 : len -= scratch.len();
82 7479834 : scratch.clear();
83 7479834 : }
84 15687310 : lac_top += len;
85 15687310 : let top_state = *scratch.last().unwrap_or(&states[states.len() - 1 - lac_top]);
86 15687310 : scratch.push(goto_state(top_state, YYR1[rule] as SymbolKind));
87 : }
88 3275339 : }
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 924270 : fn default_location(rhs: &[SymbolSpan], below: SymbolSpan) -> SymbolSpan {
117 924270 : match (rhs.first(), rhs.last()) {
118 773809 : (Some(first), Some(last)) => SymbolSpan::new(
119 773809 : first.offset(),
120 773809 : last.offset().wrapping_add(last.length()).wrapping_sub(first.offset()),
121 : ),
122 150461 : _ => SymbolSpan::new(below.offset().wrapping_add(below.length()), 0),
123 : }
124 924270 : }
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 1264383 : fn push(&mut self, state: StateId, value: Value, location: SymbolSpan) {
147 1264383 : self.states.push(state);
148 1264383 : self.values.push(value);
149 1264383 : self.locations.push(location);
150 1264383 : }
151 :
152 924434 : fn pop(&mut self, n: usize) {
153 924434 : let len = self.states.len() - n;
154 924434 : self.states.truncate(len);
155 924434 : self.values.truncate(len);
156 924434 : self.locations.truncate(len);
157 924434 : }
158 :
159 2175107 : fn top(&self) -> StateId {
160 2175107 : *self.states.last().unwrap()
161 2175107 : }
162 : }
163 :
164 : impl ReduceStack for Stack {
165 1050027 : fn value_at(&self, i: usize) -> Value {
166 1050027 : self.values[self.values.len() - 1 - i]
167 1050027 : }
168 266753 : fn location_at(&self, i: usize) -> SymbolSpan {
169 266753 : self.locations[self.locations.len() - 1 - i]
170 266753 : }
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 340741 : pub fn next(&mut self, ctx: &ParseContext) -> (SymbolKind, Value, SymbolSpan) {
182 340741 : let index = self.next_index;
183 340741 : match ctx.symbols().get(index as usize) {
184 340666 : Some(symbol) => {
185 340666 : self.next_index += 1;
186 340666 : let value = match symbol.value {
187 150728 : SymbolValue::None => Value::Empty,
188 99997 : SymbolValue::Name(id) => Value::Name(id),
189 89941 : SymbolValue::Text(text) => Value::Str(text),
190 : };
191 340666 : (symbol.kind, value, SymbolSpan::new(index, 1))
192 : }
193 75 : None => (S_YYEOF, Value::Empty, SymbolSpan::new(index, 0)),
194 : }
195 340741 : }
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 293 : fn syntax_error(states: &[StateId], lookahead: Option<SymbolKind>, scratch: &mut Vec<StateId>) -> (String, String) {
209 : const ARGS_MAX: usize = 5;
210 293 : let Some(token) = lookahead else {
211 0 : return ("syntax error".to_string(), String::new());
212 : };
213 293 : let mut args = vec![token];
214 293 : let mut overflow = false;
215 32100 : for t in 0..YYNTOKENS as SymbolKind {
216 32100 : if t == S_YYerror || t == S_YYUNDEF || !lac_check(states, t, scratch) {
217 30724 : continue;
218 1376 : }
219 1376 : if args.len() == ARGS_MAX {
220 268 : overflow = true;
221 268 : break;
222 1108 : }
223 1108 : args.push(t);
224 : }
225 293 : if overflow {
226 268 : args.truncate(1);
227 268 : }
228 329 : let names: Vec<_> = args.iter().map(|&a| symbol_name(a)).collect();
229 293 : let mut message = format!("syntax error, unexpected {}", names[0]);
230 293 : for (i, name) in names.iter().enumerate().skip(1) {
231 36 : message.push_str(if i == 1 { ", expecting " } else { " or " });
232 36 : message.push_str(name);
233 : }
234 : // Suggest a double-quoted identifier when a string literal is used where an identifier fits.
235 293 : 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 288 : String::new()
239 : };
240 293 : (message, hint)
241 293 : }
242 :
243 : /// Run the parser with the grammar actions. Returns false if parsing was aborted.
244 7386 : pub fn parse(ctx: &mut ParseContext) -> bool {
245 7386 : let mut stack = Stack {
246 7386 : states: vec![0],
247 7386 : values: vec![Value::Empty],
248 7386 : locations: vec![SymbolSpan::default()],
249 7386 : };
250 7386 : let mut tokens = TokenStream { next_index: 0 };
251 7386 : let mut lookahead: Option<Lookahead> = None;
252 : // The location of the lookahead; it outlives the lookahead itself, like bison's yyla.location.
253 7386 : let mut lookahead_location = SymbolSpan::default();
254 7386 : let mut lac_established = false;
255 7386 : let mut scratch = Vec::new();
256 7386 : let mut errstatus = 0;
257 7386 : let mut error_range_begin = SymbolSpan::default();
258 7386 : let mut label = Label::NewState;
259 :
260 : loop {
261 3098630 : label = match label {
262 : Label::NewState => {
263 1271769 : let state = stack.top();
264 1271769 : if state == YYFINAL {
265 7360 : return true;
266 1264409 : }
267 1264409 : if YYPACT[state as usize] as i32 == YYPACT_NINF {
268 476154 : Label::Default
269 : } else {
270 788255 : let la = match lookahead {
271 447514 : Some(la) => la,
272 : None => {
273 340741 : let (kind, value, location) = tokens.next(ctx);
274 340741 : lookahead_location = location;
275 340741 : let la = Lookahead { kind, value };
276 340741 : lookahead = Some(la);
277 340741 : la
278 : }
279 : };
280 788255 : let mut establish = |stack: &Stack| {
281 448142 : if !lac_established {
282 157179 : lac_established = true;
283 157179 : return lac_check(&stack.states, la.kind, &mut scratch);
284 290963 : }
285 290963 : true
286 448142 : };
287 788255 : match table_action(state, la.kind) {
288 : None => {
289 426431 : if establish(&stack) {
290 425802 : Label::Default
291 : } else {
292 629 : Label::ErrLab
293 : }
294 : }
295 0 : Some(Action::Error) => Label::ErrLab,
296 21711 : Some(Action::Reduce(rule)) => {
297 21711 : if establish(&stack) {
298 21705 : Label::Reduce(rule)
299 : } else {
300 6 : Label::ErrLab
301 : }
302 : }
303 340113 : Some(Action::Shift(next)) => {
304 340113 : if errstatus > 0 {
305 411 : errstatus -= 1;
306 339702 : }
307 340113 : stack.push(next, la.value, lookahead_location);
308 340113 : lookahead = None;
309 340113 : lac_established = false;
310 340113 : Label::NewState
311 : }
312 : }
313 : }
314 : }
315 901956 : Label::Default => match YYDEFACT[stack.top() as usize] as usize {
316 0 : 0 => Label::ErrLab,
317 901956 : rule => Label::Reduce(rule),
318 : },
319 923661 : Label::Reduce(rule) => {
320 923661 : let len = YYR2[rule] as usize;
321 923661 : let n = stack.states.len();
322 923661 : let lhs_state = goto_state(stack.states[n - 1 - len], YYR1[rule] as SymbolKind);
323 923661 : let location = default_location(&stack.locations[n - len..], stack.locations[n - 1]);
324 923661 : error_range_begin = location;
325 923661 : match reduce(ctx, rule, &stack, location) {
326 923661 : Ok(value) => {
327 923661 : if std::mem::take(&mut ctx.state.borrow_mut().clear_lookahead) {
328 602 : lookahead = None;
329 923059 : }
330 923661 : stack.pop(len);
331 923661 : stack.push(lhs_state, value.unwrap_or(Value::Empty), location);
332 923661 : 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 635 : if errstatus == 0 {
346 293 : let (message, hint) = syntax_error(&stack.states, lookahead.map(|la| la.kind), &mut scratch);
347 293 : ctx.state.borrow_mut().pending_hint = hint;
348 293 : ctx.error(lookahead_location, &message);
349 342 : }
350 635 : error_range_begin = lookahead_location;
351 635 : if errstatus == 3 {
352 : // Discard the lookahead that failed to be reused after an error
353 311 : match lookahead {
354 311 : Some(la) if la.kind == S_YYEOF => return false,
355 285 : Some(_) => lookahead = None,
356 0 : None => {}
357 : }
358 324 : }
359 609 : Label::ErrLab1
360 : }
361 : Label::ErrLab1 => {
362 609 : errstatus = 3;
363 : // Pop states until one shifts the error token
364 609 : let next = loop {
365 1382 : if let Some(Action::Shift(next)) = table_action(stack.top(), S_YYerror) {
366 609 : break next;
367 773 : }
368 773 : if stack.states.len() == 1 {
369 0 : return false;
370 773 : }
371 773 : error_range_begin = *stack.locations.last().unwrap();
372 773 : stack.pop(1);
373 : };
374 609 : let error_location = default_location(&[error_range_begin, lookahead_location], SymbolSpan::default());
375 609 : lac_established = false;
376 609 : stack.push(next, Value::Empty, error_location);
377 609 : Label::NewState
378 : }
379 : };
380 : }
381 7386 : }
382 :
383 : /// Run the action of a rule
384 923661 : fn reduce(ctx: &mut ParseContext, rule: usize, stack: &Stack, location: SymbolSpan) -> Result<Option<Value>, ReduceError> {
385 923661 : crate::tables::reduce(ctx, rule, stack, location)
386 923661 : }
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 : }
|
