1 use crate::queue_stack::QueueStack;
2 use crate::simulator::Simulator;
3 use ast::arena;
4 use ast::SourceLocation;
5 use generated_parser::{
6     full_actions, AstBuilder, AstBuilderDelegate, ErrorCode, ParseError, ParserTrait, Result,
7     StackValue, TermValue, TerminalId, Token, TABLES,
8 };
9 use json_log::json_trace;
10 
11 pub struct Parser<'alloc> {
12     /// Vector of states visited in the LR parse table.
13     state_stack: Vec<usize>,
14     /// Stack and Queue of terms and their associated values. The Queue
15     /// corresponds to terms which are added as lookahead as well as terms which
16     /// are replayed, and the stack matches the state_stack.
17     node_stack: QueueStack<TermValue<StackValue<'alloc>>>,
18     /// Build the AST stored in the TermValue vectors.
19     handler: AstBuilder<'alloc>,
20 }
21 
22 impl<'alloc> AstBuilderDelegate<'alloc> for Parser<'alloc> {
ast_builder_refmut(&mut self) -> &mut AstBuilder<'alloc>23     fn ast_builder_refmut(&mut self) -> &mut AstBuilder<'alloc> {
24         &mut self.handler
25     }
26 }
27 
28 impl<'alloc> ParserTrait<'alloc, StackValue<'alloc>> for Parser<'alloc> {
shift(&mut self, tv: TermValue<StackValue<'alloc>>) -> Result<'alloc, bool>29     fn shift(&mut self, tv: TermValue<StackValue<'alloc>>) -> Result<'alloc, bool> {
30         // The shift function should exit either by accepting the input or
31         // emptying its queue of lookahead.
32         debug_assert!(self.node_stack.queue_empty());
33         self.node_stack.enqueue(tv);
34         // Shift the new terminal/nonterminal and its associated value.
35         json_trace!({ "enter": "shift" });
36         let mut state = self.state();
37         debug_assert!(state < TABLES.shift_count);
38         while !self.node_stack.queue_empty() {
39             let term_index: usize = self.node_stack.next().unwrap().term.into();
40             debug_assert!(term_index < TABLES.shift_width);
41             let index = state * TABLES.shift_width + term_index;
42             let goto = TABLES.shift_table[index];
43             json_trace!({
44                 "from": state,
45                 "to": goto,
46                 "term": format!("{:?}", { let s: &'static str = tv.term.into(); s }),
47             });
48             if goto < 0 {
49                 self.node_stack.shift();
50                 let tv = self.node_stack.pop().unwrap();
51                 // Error handling is in charge of shifting an ErrorSymbol from the
52                 // current state.
53                 self.try_error_handling(tv)?;
54                 continue;
55             }
56             state = goto as usize;
57             self.shift_replayed(state);
58             // Execute any actions, such as reduce actions ast builder actions.
59             if state >= TABLES.shift_count {
60                 assert!(state < TABLES.action_count + TABLES.shift_count);
61                 json_trace!({ "action": state });
62                 if full_actions(self, state)? {
63                     return Ok(true);
64                 }
65                 state = self.state();
66             }
67             debug_assert!(state < TABLES.shift_count);
68         }
69         Ok(false)
70     }
71     #[inline(always)]
shift_replayed(&mut self, state: usize)72     fn shift_replayed(&mut self, state: usize) {
73         // let term_index: usize = self.node_stack.next().unwrap().term.into();
74         // assert!(term_index < TABLES.shift_width);
75         // let from_state = self.state();
76         // let index = from_state * TABLES.shift_width + term_index;
77         // let goto = TABLES.shift_table[index];
78         // assert!((goto as usize) == state);
79         self.state_stack.push(state);
80         self.node_stack.shift();
81     }
unshift(&mut self)82     fn unshift(&mut self) {
83         self.state_stack.pop().unwrap();
84         self.node_stack.unshift()
85     }
pop(&mut self) -> TermValue<StackValue<'alloc>>86     fn pop(&mut self) -> TermValue<StackValue<'alloc>> {
87         self.state_stack.pop().unwrap();
88         self.node_stack.pop().unwrap()
89     }
replay(&mut self, tv: TermValue<StackValue<'alloc>>)90     fn replay(&mut self, tv: TermValue<StackValue<'alloc>>) {
91         self.node_stack.push_next(tv)
92     }
epsilon(&mut self, state: usize)93     fn epsilon(&mut self, state: usize) {
94         *self.state_stack.last_mut().unwrap() = state;
95     }
top_state(&self) -> usize96     fn top_state(&self) -> usize {
97         self.state()
98     }
check_not_on_new_line(&mut self, peek: usize) -> Result<'alloc, bool>99     fn check_not_on_new_line(&mut self, peek: usize) -> Result<'alloc, bool> {
100         let sv = {
101             let stack = self.node_stack.stack_slice();
102             &stack[stack.len() - peek].value
103         };
104         if let StackValue::Token(ref token) = sv {
105             if !token.is_on_new_line {
106                 return Ok(true);
107             }
108             self.rewind(peek - 1);
109             let tv = self.pop();
110             self.try_error_handling(tv)?;
111             return Ok(false);
112         }
113         Err(ParseError::NoLineTerminatorHereExpectedToken.into())
114     }
115 }
116 
117 impl<'alloc> Parser<'alloc> {
new(handler: AstBuilder<'alloc>, entry_state: usize) -> Self118     pub fn new(handler: AstBuilder<'alloc>, entry_state: usize) -> Self {
119         TABLES.check();
120         assert!(entry_state < TABLES.shift_count);
121         let mut state_stack = Vec::with_capacity(128);
122         state_stack.push(entry_state);
123 
124         Self {
125             state_stack,
126             node_stack: QueueStack::with_capacity(128),
127             handler,
128         }
129     }
130 
state(&self) -> usize131     fn state(&self) -> usize {
132         *self.state_stack.last().unwrap()
133     }
134 
write_token(&mut self, token: arena::Box<'alloc, Token>) -> Result<'alloc, ()>135     pub fn write_token(&mut self, token: arena::Box<'alloc, Token>) -> Result<'alloc, ()> {
136         json_trace!({
137             "method": "write_token",
138             "is_on_new_line": token.is_on_new_line,
139             "start": token.loc.start,
140             "end": token.loc.end,
141         });
142         // Shift the token with the associated StackValue.
143         let term = token.terminal_id.into();
144         let accept = self.shift(TermValue {
145             term,
146             value: StackValue::Token(token),
147         })?;
148         // JavaScript grammar accepts empty inputs, therefore we can never
149         // accept any program before receiving a TerminalId::End.
150         assert!(!accept);
151         Ok(())
152     }
153 
close(&mut self, position: usize) -> Result<'alloc, StackValue<'alloc>>154     pub fn close(&mut self, position: usize) -> Result<'alloc, StackValue<'alloc>> {
155         // Shift the End terminal with the associated StackValue.
156         json_trace!({
157             "method": "close",
158             "position": position,
159         });
160         let loc = SourceLocation::new(position, position);
161         let token = Token::basic_token(TerminalId::End, loc);
162         let accept = self.shift(TermValue {
163             term: TerminalId::End.into(),
164             value: StackValue::Token(self.handler.alloc(token)),
165         })?;
166         // Adding a TerminalId::End would either lead to a parse error, or to
167         // accepting the current input. In which case we return matching node
168         // value.
169         assert!(accept);
170 
171         // We can either reduce a Script/Module, or a Script/Module followed by
172         // an <End> terminal.
173         assert!(self.node_stack.stack_len() >= 1);
174         assert!(self.node_stack.stack_len() <= 2);
175         if self.node_stack.stack_len() > 1 {
176             self.node_stack.pop();
177         }
178         Ok(self.node_stack.pop().unwrap().value)
179     }
180 
parse_error(t: &Token) -> ParseError<'alloc>181     pub(crate) fn parse_error(t: &Token) -> ParseError<'alloc> {
182         if t.terminal_id == TerminalId::End {
183             ParseError::UnexpectedEnd
184         } else {
185             ParseError::SyntaxError(t.clone())
186         }
187     }
188 
try_error_handling(&mut self, t: TermValue<StackValue<'alloc>>) -> Result<'alloc, bool>189     fn try_error_handling(&mut self, t: TermValue<StackValue<'alloc>>) -> Result<'alloc, bool> {
190         json_trace!({
191             "try_error_handling_term": format!("{}", {
192                 let s: &'static str = t.term.into();
193                 s
194             }),
195         });
196         if let StackValue::Token(ref token) = t.value {
197             // Error tokens might them-self cause more errors to be reported.
198             // This happens due to the fact that the ErrorToken can be replayed,
199             // and while the ErrorToken might be in the lookahead rules, it
200             // might not be in the shifted terms coming after the reduced
201             // nonterminal.
202             if t.term == TerminalId::ErrorToken.into() {
203                 return Err(Self::parse_error(token).into());
204             }
205 
206             // Otherwise, check if the current rule accept an Automatic
207             // Semi-Colon insertion (ASI).
208             let state = self.state();
209             assert!(state < TABLES.shift_count);
210             let error_code = TABLES.error_codes[state];
211             if let Some(error_code) = error_code {
212                 let err_token = (*token).clone();
213                 Self::recover(token, error_code)?;
214                 self.replay(t);
215                 let err_token = self.handler.alloc(err_token);
216                 self.replay(TermValue {
217                     term: TerminalId::ErrorToken.into(),
218                     value: StackValue::Token(err_token),
219                 });
220                 return Ok(false);
221             }
222             // On error, don't attempt error handling again.
223             return Err(Self::parse_error(token).into());
224         }
225         Err(ParseError::ParserCannotUnpackToken.into())
226     }
227 
recover(t: &Token, error_code: ErrorCode) -> Result<'alloc, ()>228     pub(crate) fn recover(t: &Token, error_code: ErrorCode) -> Result<'alloc, ()> {
229         match error_code {
230             ErrorCode::Asi => {
231                 if t.is_on_new_line
232                     || t.terminal_id == TerminalId::End
233                     || t.terminal_id == TerminalId::CloseBrace
234                 {
235                     Ok(())
236                 } else {
237                     Err(Self::parse_error(t).into())
238                 }
239             }
240             ErrorCode::DoWhileAsi => Ok(()),
241         }
242     }
243 
simulator<'a>(&'a self) -> Simulator<'alloc, 'a>244     fn simulator<'a>(&'a self) -> Simulator<'alloc, 'a> {
245         assert_eq!(self.node_stack.queue_len(), 0);
246         Simulator::new(&self.state_stack, self.node_stack.stack_slice())
247     }
248 
can_accept_terminal(&self, t: TerminalId) -> bool249     pub fn can_accept_terminal(&self, t: TerminalId) -> bool {
250         let result = self.simulator().write_token(t).is_ok();
251         json_trace!({
252             "can_accept": result,
253             "terminal": format!("{:?}", t),
254         });
255         result
256     }
257 
258     /// Return true if self.close() would succeed.
can_close(&self) -> bool259     pub fn can_close(&self) -> bool {
260         self.simulator().close(0).is_ok()
261     }
262 }
263