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