sphinx/
parser.rs

1use std::collections::VecDeque;
2
3use log::debug;
4
5use crate::language::{InternSymbol, Access};
6use crate::lexer::{TokenMeta, Token, LexerError};
7use crate::runtime::strings::StringInterner;
8use crate::debug::{SourceError, TokenIndex};
9
10
11pub mod expr;
12pub mod stmt;
13pub mod primary;
14pub mod lvalue;
15pub mod operator;
16pub mod fundefs;
17pub mod errors;
18mod tests;
19
20pub use errors::{ParserError, ParseResult};
21
22use expr::{ExprMeta, Expr, ExprBlock, ConditionalBranch};
23use stmt::{StmtMeta, StmtList, Stmt, Label, ControlFlow};
24use primary::{Primary, Atom, AccessItem};
25use lvalue::{LValue, AssignType, Assignment};
26use operator::{UnaryOp, BinaryOp, Precedence, PRECEDENCE_START, PRECEDENCE_END};
27use fundefs::{FunctionDef, SignatureDef, ParamDef, DefaultDef};
28use errors::{ErrorKind, ErrorContext, ContextTag};
29
30
31// Recursive descent parser
32
33pub struct Parser<'h, T> where T: Iterator<Item=Result<TokenMeta, LexerError>> {
34    interner: &'h mut StringInterner,
35    tokens: T,
36    next: Option<Result<TokenMeta, LexerError>>,
37    errors: VecDeque<ParserError>,
38}
39
40impl<T> Iterator for Parser<'_, T> where T: Iterator<Item=Result<TokenMeta, LexerError>> {
41    type Item = Result<StmtMeta, ParserError>;
42    fn next(&mut self) -> Option<Self::Item> { self.next_stmt() }
43}
44
45impl<'h, I> Parser<'h, I> where I: Iterator<Item=Result<TokenMeta, LexerError>> {
46    
47    pub fn new(interner: &'h mut StringInterner, tokens: I) -> Self {
48        Parser {
49            tokens, interner,
50            next: None,
51            errors: VecDeque::new(),
52        }
53    }
54}
55    
56impl<I> Parser<'_, I> where I: Iterator<Item=Result<TokenMeta, LexerError>> {
57    /// for debugging
58    fn current_index(&mut self) -> TokenIndex { 
59        let token = self.peek().unwrap();
60        token.symbol.start()
61    }
62    
63    fn advance(&mut self) -> ParseResult<TokenMeta> {
64        let next = self.next.take()
65            .or_else(|| self.tokens.next());
66        
67        if let Some(result) = next {
68            Ok(result?)
69        } else {
70            Err(ErrorKind::EndofTokenStream.into())
71        }
72    }
73    
74    // peek() will consume any errors it encounters (i.e. peek() acts like advance() if the next token was a lexer error)
75    // this is so that we don't have to do a complex map_err() every single time we call self.peek()
76    fn peek(&mut self) -> ParseResult<&TokenMeta> {
77        if self.next.is_none() {
78            self.next = self.tokens.next();
79            if self.next.is_none() {
80                return Err(ErrorKind::EndofTokenStream.into());
81            }
82        }
83        
84        // This is needed to finagle a reference in one branch while advancing the 
85        // token iterator and taking ownership of the ParserError in the other
86        if self.next.as_ref().unwrap().is_ok() {
87            Ok(self.next.as_ref().unwrap().as_ref().unwrap()) // yes, the repetition is required
88        } else {
89            Err(self.advance().unwrap_err())
90        }
91    }
92    
93    fn intern_str(&mut self, string: impl AsRef<str>) -> InternSymbol {
94        self.interner.get_or_intern(string)
95    }
96
97    pub fn next_stmt(&mut self) -> Option<Result<StmtMeta, ParserError>> {
98        let mut ctx = ErrorContext::new(ContextTag::TopLevel);
99        
100        if let Some(error) = self.errors.pop_front() {
101            return Some(Err(Self::process_error(ctx, error)));
102        }
103        
104        // check stop conditions
105        loop {
106            match self.peek() {
107                Err(error) if matches!(error.kind(), ErrorKind::EndofTokenStream) => return None,
108                
109                Err(error) => return Some(Err(Self::process_error(ctx, error))),
110                
111                Ok(next) if matches!(next.token, Token::EOF) => return None,
112                
113                // skip statement separators
114                Ok(next) if matches!(next.token, Token::Semicolon) => {
115                    self.advance().unwrap();
116                    continue;
117                },
118                
119                Ok(..) => break,
120            }
121        }
122        
123        let result = match self.parse_stmt(&mut ctx) {
124            Ok(stmt) => {
125                debug!("parser: {:?}", stmt); 
126                Ok(stmt)
127            },
128            Err(error) => {
129                self.errors.push_back(error);
130                let error = self.errors.pop_front().unwrap();
131                let error = Self::process_error(ctx, error);
132                
133                self.synchronize_stmt(false);
134                
135                Err(error)
136            },
137        };
138        Some(result)
139    }
140    
141    fn process_error(ctx: ErrorContext, error: ParserError) -> ParserError {
142        debug!("{:#?}", ctx);
143        
144        let error = error.with_error_context(ctx);
145        
146        debug!("parser error: {:?}\ncontext: {:?}\nsymbol: {:?}", 
147            error.kind(), error.context(), 
148            error.debug_symbol(),
149        );
150        
151        error
152    }
153    
154    fn catch_error_and_sync<T>(&mut self, ctx: &ErrorContext, result: ParseResult<T>, inside_block: bool) -> Option<ParseResult<T>> {
155        match result {
156            Ok(..) => Some(result),
157            Err(error) => {
158                if matches!(error.kind(), ErrorKind::EndofTokenStream) {
159                    return Some(Err(error));
160                }
161                
162                self.errors.push_back(error.with_symbol_from_ctx(ctx));
163                self.synchronize_stmt(inside_block);
164                
165                // if the next token is EOF there is no point catching an error
166                // since there is no more source code to examine anyways
167                // (same applies if we can't even peek without hitting an error)
168                match self.peek() {
169                    Err(..) | Ok(TokenMeta { token: Token::EOF, .. }) 
170                      => Some(Err(self.errors.pop_front().unwrap())),
171                    
172                    _ => None,
173                }
174            }
175        }
176    }
177    
178    // If we hit an error we need to synchronize back to a likely-valid state before we continue parsing again
179    // To do this, just keep discarding tokens until we think we're at the start of a new statement
180    fn synchronize_stmt(&mut self, inside_block: bool) {
181        // Check for either: a token that only appears at the start of a new statement
182        // OR try to parse an expression. If we can do it without errors, assume we're in a good state. The expression can be discarded.
183        debug!("sync to next stmt...");
184        
185        let mut ctx = ErrorContext::new(ContextTag::Sync);
186        
187        loop {
188
189            let next = match self.peek() {
190                // no more tokens...
191                Err(error) if matches!(error.kind(), ErrorKind::EndofTokenStream) => break,
192                
193                // skip errors
194                Err(..) => continue,  // peek will consume errors
195                
196                Ok(token) => token,
197            };
198
199            match next.token {
200                Token::EOF | Token::Semicolon |
201                Token::While  | Token::Loop | Token::For |
202                Token::Continue | Token::Break | Token::Return | 
203                Token::Label(..) | Token::Assert
204                    => break,
205                
206                Token::End if inside_block => break,
207                
208                _ => if self.parse_expr_variant(&mut ctx).is_ok() {
209                    break;
210                },
211            }
212
213        }
214        
215        debug!("done.");
216    }
217
218    /* Statement Parsing */
219    
220    fn parse_stmt(&mut self, ctx: &mut ErrorContext) -> ParseResult<StmtMeta> {
221        // skip statement separators
222        while let Token::Semicolon = self.peek()?.token {
223            self.advance()?;
224        }
225        
226        debug!("parsing stmt at index {}...", self.current_index());
227        
228        ctx.push(ContextTag::StmtMeta);
229        
230        let stmt = self.parse_stmt_variant(ctx)?;
231        let symbol = ctx.frame().as_debug_symbol().unwrap();
232        
233        ctx.pop_extend();
234        Ok(StmtMeta::new(stmt, symbol))
235    }
236    
237    fn parse_stmt_variant(&mut self, ctx: &mut ErrorContext) -> ParseResult<Stmt> {
238        let stmt = match  self.peek()?.token {
239            
240            Token::Loop => self.parse_loop(ctx, None)?,
241            Token::While => self.parse_while_loop(ctx, None)?,
242            Token::For => self.parse_for_loop(ctx, None)?,
243            
244            Token::Label(..) => self.parse_stmt_label(ctx)?,
245            
246            Token::Assert => {
247                ctx.set_start(&self.advance().unwrap());
248                Stmt::Assert(self.parse_expr_variant(ctx)?)
249            }
250            
251            Token::Continue | Token::Break | Token::Return => {
252                let next = self.advance().unwrap();
253                
254                ctx.push(ContextTag::ControlFlow);
255                ctx.set_start(&next);
256                
257                let name = match next.token {
258                    Token::Continue => "continue",
259                    Token::Break => "break",
260                    Token::Return => "return",
261                    _ => unreachable!(),
262                };
263                
264                let message = format!("\"{}\" is not allowed here", name);
265                return Err(message.as_str().into());
266            }
267            
268            // expression statements
269            _ => match self.parse_expr_variant(ctx)? {
270                Expr::Unpack(None) =>
271                    return Err("\"...\" is not allowed here".into()),
272                expr => Stmt::Expression(expr)
273            }
274        };
275        Ok(stmt)
276    }
277    
278    fn parse_stmt_label(&mut self, ctx: &mut ErrorContext) -> ParseResult<Stmt> {
279        let label = self.try_parse_label(ctx)?.unwrap();
280        
281        match self.peek()?.token {
282            Token::Loop => self.parse_loop(ctx, Some(label)),
283            Token::While => self.parse_while_loop(ctx, Some(label)),
284            Token::For => self.parse_for_loop(ctx, Some(label)),
285            
286            _ => Err("labels must be followed by either a block or a loop".into()),
287        }
288    }
289    
290    fn parse_loop(&mut self, ctx: &mut ErrorContext, label: Option<Label>) -> ParseResult<Stmt> {
291        let next = self.advance()?;
292        
293        ctx.push(ContextTag::Loop);
294        ctx.set_start(&next);
295        debug_assert!(matches!(next.token, Token::Loop));
296        
297        let body = self.parse_stmt_list(ctx, |token| matches!(token, Token::End))?;
298        
299        let next = self.advance().unwrap(); 
300        ctx.set_end(&next);
301        
302        ctx.pop_extend();
303        Ok(Stmt::Loop { label, body })
304    }
305    
306    fn parse_while_loop(&mut self, ctx: &mut ErrorContext, label: Option<Label>) -> ParseResult<Stmt> {
307        let next = self.advance()?;
308        
309        ctx.push(ContextTag::WhileLoop);
310        ctx.set_start(&next);
311        debug_assert!(matches!(next.token, Token::While));
312        
313        let condition = self.parse_expr_variant(ctx)?;
314        
315        let next = self.advance()?;
316        ctx.set_end(&next);
317        
318        if !matches!(next.token, Token::Do) {
319            return Err("expected \"do\" after condition in while-loop".into());
320        }
321        
322        let body = self.parse_stmt_list(ctx, |token| matches!(token, Token::End))?;
323        
324        ctx.set_end(&self.advance().unwrap()); // consume "end"
325        
326        ctx.pop_extend();
327        Ok(Stmt::WhileLoop { label, condition, body })
328    }
329    
330    fn parse_for_loop(&mut self, ctx: &mut ErrorContext, label: Option<Label>) -> ParseResult<Stmt> {
331        let next = self.advance()?;
332        
333        ctx.push(ContextTag::ForLoop);
334        ctx.set_start(&next);
335        debug_assert!(matches!(next.token, Token::For));
336        
337        // parse lvalue list
338        let lvalue = self.parse_lvalue_list(ctx)?;
339        
340        let next = self.advance()?;
341        ctx.set_end(&next);
342        
343        if !matches!(next.token, Token::In) {
344            return Err("expected \"do\" after condition in while-loop".into());
345        }
346        
347        // parse iterator expression
348        let iter = self.parse_expr_variant(ctx)?;
349        
350        let next = self.advance()?;
351        ctx.set_end(&next);
352        
353        if !matches!(next.token, Token::Do) {
354            return Err("expected \"do\" after condition in while-loop".into());
355        }
356        
357        let body = self.parse_stmt_list(ctx, |token| matches!(token, Token::End))?;
358        
359        ctx.set_end(&self.advance().unwrap()); // consume "end"
360        
361        let for_loop = Stmt::ForLoop {
362            label,
363            lvalue,
364            iter,
365            body,
366        };
367        
368        ctx.pop_extend();
369        Ok(for_loop)
370    }
371    
372    fn parse_lvalue_list(&mut self, ctx: &mut ErrorContext) -> ParseResult<LValue> {
373        let modifier = self.try_parse_assign_keyword(ctx)?;
374        
375        let lvalue = self.parse_tuple_expr(ctx)?
376            .try_into()
377            .map_err(|_| ParserError::from("can't assign to this"))?;
378        
379        if let Some(modifier) = modifier {
380            Ok(LValue::Modifier { modifier, lvalue: Box::new(lvalue) })
381        } else {
382            Ok(lvalue)
383        }
384    }
385    
386    /// Parses a list of statements, stopping when the given closure returns true. The final token is not consumed.
387    fn parse_stmt_list(&mut self, ctx: &mut ErrorContext, end_list: impl Fn(&Token) -> bool) -> ParseResult<StmtList> {
388        ctx.push(ContextTag::StmtList);
389        
390        let mut suite = Vec::new();
391        let mut control = None;
392        
393        debug!("enter stmt list at index {}...", self.current_index());
394        
395        loop {
396            
397            // statement separators
398            while matches!(self.peek()?.token, Token::Semicolon) {
399                ctx.set_end(&self.advance().unwrap());
400            }
401            
402            let next = self.peek()?;
403            if end_list(&next.token) {
404                break;
405            }
406            
407            let parse_result = self.try_parse_control_flow(ctx);
408            control = match self.catch_error_and_sync(ctx, parse_result, true) {
409                Some(result) => result?,
410                None => continue,
411            };
412            
413            // if we found a control flow statement, it must be the last item in the statement list
414            if let Some(control) = control.as_ref() {
415                
416                let next = self.peek()?;
417                if !end_list(&next.token) {
418                    // consume the unexpected token so that it is included in the error message
419                    ctx.set_end(&self.advance().unwrap());
420                    
421                    let name = match control {
422                        ControlFlow::Continue {..} => "continue",
423                        ControlFlow::Break {..} => "break",
424                        ControlFlow::Return {..} => "return",
425                    };
426                    
427                    let message = format!("\"{}\" must be the last statement in a block", name);
428                    let error = ParserError::from(ErrorKind::SyntaxError(message))
429                        .with_symbol_from_ctx(ctx);
430                    
431                    self.errors.push_back(error);
432                }
433                
434                break;
435            }
436            
437            let parse_result = self.parse_stmt(ctx);
438            let stmt = match self.catch_error_and_sync(ctx, parse_result, true) {
439                Some(result) => result?,
440                None => continue,
441            };
442            
443            suite.push(stmt);
444        }
445        
446        debug!("exit stmt list at {}...", self.current_index());
447        
448        ctx.pop_extend();
449        
450        Ok(StmtList::new(suite, control))
451    }
452    
453    fn try_parse_label(&mut self, _ctx: &mut ErrorContext) -> ParseResult<Option<Label>> {
454        let next = self.peek()?;
455        
456        let label = if let Token::Label(..) = next.token {
457            let next = self.advance().unwrap();
458            
459            if let Token::Label(name) = next.token {
460                Some(Label::new(self.intern_str(name)))
461            } else { unreachable!() }
462            
463        } else { None };
464        Ok(label)
465    }
466    
467    fn try_parse_control_flow(&mut self, ctx: &mut ErrorContext) -> ParseResult<Option<ControlFlow>> {
468        let next = self.peek()?;
469        
470        let control_flow = match next.token {
471            Token::Continue => {
472                ctx.push(ContextTag::ControlFlow);
473                ctx.set_start(&self.advance().unwrap());
474                
475                let label = self.try_parse_label(ctx)?;
476                
477                ControlFlow::Continue {
478                    label, 
479                    symbol: ctx.frame().as_debug_symbol()
480                }
481            },
482            
483            Token::Break => {
484                ctx.push(ContextTag::ControlFlow);
485                ctx.set_start(&self.advance().unwrap());
486                
487                let label = self.try_parse_label(ctx)?;
488                
489                let expr = 
490                    if !matches!(self.peek()?.token, Token::End | Token::Elif | Token::Else | Token::Semicolon ) {
491                        Some(Box::new(self.parse_expr_variant(ctx)?))
492                    } else { None };
493                
494                ControlFlow::Break {
495                    label, expr, 
496                    symbol: ctx.frame().as_debug_symbol()
497                }
498            },
499            
500            Token::Return => {
501                ctx.push(ContextTag::ControlFlow);
502                ctx.set_start(&self.advance().unwrap());
503                
504                let expr = 
505                    if !matches!(self.peek()?.token, Token::End | Token::Elif | Token::Else | Token::Semicolon ) {
506                        Some(Box::new(self.parse_expr_variant(ctx)?))
507                    } else { None };
508                
509                ControlFlow::Return {
510                    expr, 
511                    symbol: ctx.frame().as_debug_symbol()
512                }
513            }
514            
515            _ => return Ok(None),
516        };
517        
518        ctx.pop_extend();
519        Ok(Some(control_flow))
520    }
521
522    /* Expression Parsing */
523    
524    fn parse_expr(&mut self, ctx: &mut ErrorContext) -> ParseResult<ExprMeta> {
525        ctx.push(ContextTag::ExprMeta);
526        
527        let variant = self.parse_expr_variant(ctx)?;
528        let symbol = ctx.frame().as_debug_symbol().unwrap();
529        
530        ctx.pop_extend();
531        Ok(ExprMeta::new(variant, symbol))
532    }
533    
534    // the top of the recursive descent stack for expressions
535    fn parse_expr_variant(&mut self, ctx: &mut ErrorContext) -> ParseResult<Expr> {
536        self.parse_assignment_expr(ctx)
537    }
538    
539    /*
540        Assignment Expression syntax:
541        
542        lvalue ::= identifier | primary index-access | primary member-access ;
543
544        lvalue-expression ::= lvalue | lvalue-list | "(" lvalue ")" ;   (* basically just lvalues, and tuples of lvalues *)
545        lvalue-list ::= lvalue-expression ( "," lvalue-expression )* ;
546
547        lvalue-annotated ::= lvalue-expression ( ":" type-expression )? ; 
548
549        assignment-op ::= "=" | "+=" | "-=" | "*=" | "/=" | "%=" | "&=" | "|=" | "^=" | "<<=" | ">>=" ;
550        assignment-expression ::= lvalue-annotated assignment-op expression ;
551    */
552    
553    fn parse_assignment_expr(&mut self, ctx: &mut ErrorContext) -> ParseResult<Expr> {
554        
555        // check for lvalue modifier
556        let assign = self.try_parse_assign_keyword(ctx)?;
557        
558        // parse LHS
559        let expr = self.parse_tuple_expr(ctx)?;
560        
561        let next = self.peek()?;
562        if let Some(op) = Self::which_assignment_op(&next.token) {
563            // consume assign_op token
564            ctx.push_continuation(ContextTag::AssignmentExpr, None);
565            ctx.set_end(&self.advance().unwrap());
566            
567            // LHS of assignment must be an lvalue
568            let lhs = LValue::try_from(expr)
569                .map_err(|_| ParserError::from("can't assign to this"))?;
570            
571            // Parse RHS
572            let rhs = self.parse_expr_variant(ctx)?;
573            
574            ctx.pop_extend();
575            
576            let assign = Assignment {
577                lhs, op, rhs,
578                modifier: assign.unwrap_or(AssignType::AssignLocal),
579            };
580            
581            Ok(Expr::Assignment(Box::new(assign)))
582            
583        } else if let Some(assign) = assign {
584            let assign = match assign {
585                AssignType::AssignLocal => "local",
586                AssignType::AssignNonLocal => "nonlocal",
587                AssignType::DeclImmutable => "let",
588                AssignType::DeclMutable => "var",
589            };
590            let message = format!("expected an assignment expression after \"{}\"", assign);
591            
592            Err(message.as_str().into())
593            
594        } else {
595            
596            Ok(expr)
597        }
598        
599    }
600    
601    fn parse_tuple_expr(&mut self, ctx: &mut ErrorContext) -> ParseResult<Expr> {
602        
603        // if this inner expression ends up being captured as the first
604        // element of a tuple, we will want to get its debug symbol.
605        ctx.push(ContextTag::ExprMeta);
606        
607        // descend recursively into binops
608        let mut first_expr = Some(self.parse_binop_expr(ctx)?); // might be taken into tuple later
609        
610        // check for tuple constructor
611        let mut tuple_exprs = Vec::new();
612        loop {
613            let next = self.peek()?;
614            
615            if !matches!(next.token, Token::Comma) {
616                break;
617            }
618            
619            if let Some(first_expr) = first_expr.take() {
620                // retroactivly get debug symbol
621                let frame = ctx.pop();
622                let symbol = frame.as_debug_symbol().unwrap();
623                tuple_exprs.push(ExprMeta::new(first_expr, symbol));
624                
625                ctx.push_continuation(ContextTag::TupleCtor, Some(frame)); // enter the tuple context
626            }
627            
628            ctx.set_end(&self.advance().unwrap()); // consume comma
629            
630            let next = self.peek()?;
631            if matches!(next.token, Token::CloseParen) {
632                break;
633            }
634            
635            ctx.push(ContextTag::ExprMeta);
636            let next_expr = self.parse_binop_expr(ctx)?;
637            let symbol = ctx.frame().as_debug_symbol().unwrap();
638            ctx.pop_extend();
639            
640            tuple_exprs.push(ExprMeta::new(next_expr, symbol));
641        }
642        
643        ctx.pop_extend();
644        
645        if let Some(expr) = first_expr {
646            Ok(expr)
647        } else {
648            Ok(Expr::Tuple(tuple_exprs.into_boxed_slice()))
649        }
650    }
651    
652
653
654    /*
655        Binary operator syntax:
656        
657        operand[1] ::= unary ;
658        operand[N] ::= operand[N-1] ( OPERATOR[N] operand[N-1] )* ;
659    */
660    fn parse_binop_expr(&mut self, ctx: &mut ErrorContext) -> ParseResult<Expr> {
661        self.parse_binop_expr_levels(ctx, PRECEDENCE_START)
662    }
663    
664    fn parse_binop_expr_levels(&mut self, ctx: &mut ErrorContext, level: Precedence) -> ParseResult<Expr> {
665        if level == PRECEDENCE_END {
666            return self.parse_unary_expr(ctx);  // exit binop precedence recursion
667        }
668        
669        let mut expr = self.parse_binop_expr_levels(ctx, level - 1)?;
670        
671        let mut push_ctx = false;
672        loop {
673            let next = self.peek()?;
674            let binary_op = Self::which_binary_op(&next.token);
675            
676            if binary_op.is_none() {
677                break;
678            }
679            
680            let binary_op = binary_op.unwrap();
681            if binary_op.precedence_level() != level {
682                break;
683            }
684            
685            push_ctx = true;
686            ctx.push_continuation(ContextTag::BinaryOpExpr, None);
687            ctx.set_end(&self.advance().unwrap()); // consume binary_op token
688            
689            let rhs_expr = self.parse_binop_expr_levels(ctx, level - 1)?;
690            
691            expr = Expr::BinaryOp(binary_op, Box::new((expr, rhs_expr)));
692        }
693        
694        if push_ctx {
695            ctx.pop_extend();
696        }
697        
698        Ok(expr)
699    }
700    
701    /*
702        Unary operator syntax:
703        
704        unary-expression ::= ( "-" | "+" | "not" ) unary | primary ;
705    */
706    fn parse_unary_expr(&mut self, ctx: &mut ErrorContext) -> ParseResult<Expr> {
707        let next = self.peek()?;
708        if let Some(unary_op) = Self::which_unary_op(&next.token) {
709            ctx.push(ContextTag::UnaryOpExpr);
710            ctx.set_start(&self.advance().unwrap()); // consume unary_op token
711            
712            let expr = self.parse_unary_expr(ctx)?;
713            
714            ctx.pop_extend();
715            return Ok(Expr::UnaryOp(unary_op, Box::new(expr)));
716        }
717        
718        self.parse_primary_expr(ctx)
719    }
720
721    fn which_unary_op(token: &Token) -> Option<UnaryOp> {
722        let op = match token {
723            Token::OpAdd => UnaryOp::Pos,
724            Token::OpSub => UnaryOp::Neg,
725            Token::OpInv => UnaryOp::Inv,
726            Token::Not   => UnaryOp::Not,
727            
728            _ => return None,
729        };
730        
731        Some(op)
732    }
733    
734    fn which_binary_op(token: &Token) -> Option<BinaryOp> {
735        let op = match token {
736            Token::OpMul => BinaryOp::Mul,
737            Token::OpDiv => BinaryOp::Div,
738            Token::OpMod => BinaryOp::Mod,
739            Token::OpAdd => BinaryOp::Add,
740            Token::OpSub => BinaryOp::Sub,
741            Token::OpLShift => BinaryOp::LShift,
742            Token::OpRShift => BinaryOp::RShift,
743            Token::OpAnd => BinaryOp::BitAnd,
744            Token::OpXor => BinaryOp::BitXor,
745            Token::OpOr => BinaryOp::BitOr,
746            Token::OpLT => BinaryOp::LT,
747            Token::OpGT => BinaryOp::GT,
748            Token::OpLE => BinaryOp::LE,
749            Token::OpGE => BinaryOp::GE,
750            Token::OpEQ => BinaryOp::EQ,
751            Token::OpNE => BinaryOp::NE,
752            Token::And => BinaryOp::And,
753            Token::Or => BinaryOp::Or,
754            
755            _ => return None,
756        };
757        
758        Some(op)
759    }
760    
761    // Helper to see if the a token is an assignment operator and if so, which one it is.
762    fn which_assignment_op(token: &Token) -> Option<Option<BinaryOp>> {
763        let op = match token {
764            Token::OpAssign    => None,
765            Token::OpAddAssign => Some(BinaryOp::Add),
766            Token::OpSubAssign => Some(BinaryOp::Sub),
767            Token::OpMulAssign => Some(BinaryOp::Mul),
768            Token::OpDivAssign => Some(BinaryOp::Div),
769            Token::OpModAssign => Some(BinaryOp::Mod),
770            Token::OpAndAssign => Some(BinaryOp::BitAnd),
771            Token::OpOrAssign  => Some(BinaryOp::BitOr),
772            Token::OpXorAssign => Some(BinaryOp::BitXor),
773            Token::OpLShiftAssign => Some(BinaryOp::LShift),
774            Token::OpRShiftAssign => Some(BinaryOp::RShift),
775            
776            _ => return None,
777        };
778        
779        Some(op)
780    }
781    
782    /*
783        Here we parse all the things that are tighter binding than either unary or binary operator expressions.
784        We look for anything that can be immediately identified from the next token, or else fall back to a primary expression.
785    */
786    fn parse_primary_expr(&mut self, ctx: &mut ErrorContext) -> ParseResult<Expr> {
787        let expr = match self.peek()?.token {
788            Token::Class => unimplemented!(),
789            Token::Fun => self.parse_function_decl_expr(ctx)?,
790            
791            Token::If => self.parse_if_expr(ctx)?,
792            Token::Begin => self.parse_block_expr(ctx, None)?,
793            
794            Token::Label(..) => self.parse_expr_label(ctx)?,
795            
796            // Token::OpenBrace => Ok(ExprMeta::ObjectCtor(self.parse_object_constructor(ctx)?)),
797            
798            _ => self.parse_unpack_expr(ctx)?,
799        };
800        Ok(expr)
801    }
802    
803    fn parse_unpack_expr(&mut self, ctx: &mut ErrorContext) -> ParseResult<Expr> {
804        // check for plain ellipsis
805        let next = self.peek()?;
806        if matches!(next.token, Token::Ellipsis) {
807            ctx.set_end(&self.advance().unwrap());
808            return Ok(Expr::Unpack(None));
809        }
810        
811        let expr = self.parse_primary(ctx)?;
812        
813        let next = self.peek()?;
814        if matches!(next.token, Token::Ellipsis) {
815            ctx.set_end(&self.advance().unwrap());
816            
817            // Having multiple "..."s next to each other is really bad for readability
818            // So require that they are separated by parens, e.g. (((foo...)...)...)
819            if matches!(expr, Expr::Unpack(..)) {
820                return Err("nested use of \"...\" must be enclosed in parentheses".into());
821            }
822            return Ok(Expr::Unpack(Some(Box::new(expr))));
823        }
824        
825        Ok(expr)
826    }
827    
828    fn parse_expr_label(&mut self, ctx: &mut ErrorContext) -> ParseResult<Expr> {
829        let label = self.try_parse_label(ctx)?.unwrap();
830        
831        let expr = match self.peek()?.token {
832            Token::Begin => self.parse_block_expr(ctx, Some(label))?,
833            _ => return Err("labels must be followed by either a block or a loop".into()),
834        };
835        
836        Ok(expr)
837    }
838    
839    /*
840        block-expression ::= ( label )? "begin" ( statement | control-flow | "break" ( label )? expression )* "end" ;  (* break can be supplied a value inside of begin-blocks *)
841    */
842    fn parse_block_expr(&mut self, ctx: &mut ErrorContext, label: Option<Label>) -> ParseResult<Expr> {
843        let next = self.advance()?;
844        
845        // consume "begin"
846        ctx.push(ContextTag::BlockExpr);
847        ctx.set_start(&next);
848        debug_assert!(matches!(next.token, Token::Begin));
849        
850        let suite = self.parse_stmt_list(ctx, |token| matches!(token, Token::End))?;
851        ctx.set_end(&self.advance().unwrap()); // consume "end"
852        
853        ctx.pop_extend();
854        
855        Ok(Expr::Block { label, suite: Box::new(ExprBlock::from(suite)), })
856    }
857    
858    fn parse_if_expr(&mut self, ctx: &mut ErrorContext) -> ParseResult<Expr> {
859        let next = self.advance()?;
860        
861        ctx.push(ContextTag::IfExpr);
862        ctx.set_start(&next);
863        
864        debug_assert!(matches!(next.token, Token::If));
865        
866        let mut branches = Vec::new();
867        let mut else_clause = None;
868        
869        loop {
870            
871            // parse condition
872            let cond_expr = self.parse_expr_variant(ctx)?;
873            
874            let next = self.advance()?;
875            ctx.set_end(&next);
876            
877            if !matches!(next.token, Token::Then) {
878                return Err("expected \"then\" after condition in if-expression".into());
879            }
880            
881            let stmt_list = self.parse_stmt_list(ctx, |token| matches!(token, Token::Elif | Token::Else | Token::End))?;
882            
883            branches.push(ConditionalBranch::new(cond_expr, stmt_list.into()));
884            
885            let next = self.advance().unwrap();
886            ctx.set_end(&next);
887            
888            match next.token {
889                Token::End => break,
890                Token::Else => {
891                    
892                    let stmt_list = self.parse_stmt_list(ctx, |token| matches!(token, Token::End))?;
893                    else_clause.replace(ExprBlock::from(stmt_list));
894                    
895                    ctx.set_end(&self.advance().unwrap()); // consume "end"
896                    
897                    break;
898                },
899                
900                _ => { }
901            }
902            
903        }
904        
905        ctx.pop_extend();
906        
907        let if_expr = Expr::IfExpr { 
908            branches: branches.into_boxed_slice(),
909            else_clause: else_clause.map(Box::new),
910        };
911        Ok(if_expr)
912    }
913    
914    fn parse_function_decl_expr(&mut self, ctx: &mut ErrorContext) -> ParseResult<Expr> {
915        let next = self.advance()?;
916        
917        ctx.push(ContextTag::FunDefExpr);
918        ctx.set_start(&next);
919        debug_assert!(matches!(next.token, Token::Fun));
920        
921        // if the next token isn't an open paren, it must be a function name
922        let next = self.peek()?;
923        let name_lvalue =
924            if !matches!(next.token, Token::OpenParen) {
925                Some(self.parse_function_assignment_target(ctx)?)
926            } else { None };
927        
928        
929        let mut function_def = self.parse_function_def(ctx)?;
930        
931        // SYNTACTIC SUGAR: fun name(..) => let name = fun(..)
932        if let Some(lvalue) = name_lvalue {
933            // record name in function signature
934            if let LValue::Identifier(name) = &lvalue {
935                function_def.signature.name.replace(*name);
936            }
937            
938            let fun_decl = Assignment {
939                modifier: AssignType::DeclImmutable,
940                op: None,
941                lhs: lvalue,
942                rhs: Expr::FunctionDef(function_def),
943            };
944            
945            Ok(Expr::Assignment(Box::new(fun_decl)))
946
947        } else {
948
949            Ok(Expr::FunctionDef(function_def))
950        }
951    }
952    
953    // similar to parse_primary(), except we only allow member access and index access, and convert to an LValue after
954    fn parse_function_assignment_target(&mut self, ctx: &mut ErrorContext) -> ParseResult<LValue> {
955        ctx.push(ContextTag::PrimaryExpr);
956        
957        let atom = self.parse_atom(ctx)?;
958        
959        let mut items = Vec::new();
960        loop {
961            let next = self.peek()?;
962            match next.token {
963                
964                // access ::= "." IDENTIFIER ;
965                Token::OpAccess => items.push(self.parse_member_access(ctx)?),
966                
967                // subscript ::= "[" expression "]" ;
968                Token::OpenSquare => items.push(self.parse_index_access(ctx)?),
969                
970                _ => break,
971            };
972        }
973        
974        ctx.pop_extend();
975        
976        let lvalue =
977            if items.is_empty() { LValue::try_from(atom) } 
978            else { LValue::try_from(Primary::new(atom, items)) }
979            .map_err(|_| ParserError::from("cannot assign a function to this"))?;
980        
981        Ok(lvalue)
982    }
983    
984    fn parse_function_def(&mut self, ctx: &mut ErrorContext) -> ParseResult<FunctionDef> {
985        // expect open paren now
986        let next = self.advance().unwrap();
987        ctx.set_end(&next);
988        
989        // function parameter list
990        
991        if !matches!(next.token, Token::OpenParen) {
992            return Err("expected opening \"(\" before parameter list".into());
993        }
994        
995        let signature = self.parse_function_param_list(ctx)?;
996        
997        let next = self.advance()?;
998        if !matches!(next.token, Token::CloseParen) {
999            return Err("expected closing \")\" after parameter list".into());
1000        }
1001        
1002        // function body
1003        
1004        let body = self.parse_stmt_list(ctx, |token| matches!(token, Token::End))?;
1005        ctx.set_end(&self.advance().unwrap()); // consume "end"
1006        
1007        let fundef = FunctionDef {
1008            signature,
1009            body: Box::new(ExprBlock::from(body)),
1010        };
1011        
1012        Ok(fundef)
1013    }
1014    
1015    fn parse_function_param_list(&mut self, ctx: &mut ErrorContext) -> ParseResult<SignatureDef> {
1016
1017        let mut required = Vec::new();
1018        let mut default = Vec::new();
1019        let mut variadic = None;
1020
1021        loop {
1022            let next = self.peek()?;
1023            
1024            if matches!(next.token, Token::CloseParen) {
1025                break;
1026            }
1027            
1028            ctx.push(ContextTag::FunParam);
1029            ctx.set_start(next);
1030            
1031            // mutability modifier
1032            
1033            let mode = match next.token {
1034                Token::Var => Some(Access::ReadWrite),
1035                Token::Let => Some(Access::ReadOnly),
1036                Token::Identifier(..) => None,
1037                _ => return Err("invalid parameter".into()),
1038            };
1039            
1040            if mode.is_some() {
1041                ctx.set_end(&self.advance().unwrap());
1042            }
1043                        
1044            // name
1045            
1046            let next = self.advance()?;
1047            ctx.set_end(&next);
1048            
1049            let name = 
1050                if let Token::Identifier(name) = next.token { name }
1051                else { return Err("invalid parameter".into()); };
1052            
1053            let name = self.intern_str(name);
1054            
1055            // possibly variadic
1056            
1057            let next = self.peek()?;
1058            let is_variadic = matches!(next.token, Token::Ellipsis);
1059            if is_variadic {
1060                ctx.set_end(&self.advance().unwrap());
1061            }
1062            
1063            // possible default value
1064            let next = self.peek()?;
1065            let default_value = match next.token {
1066                Token::OpAssign if is_variadic => {
1067                    return Err("variadic parameters can't have a default value".into())
1068                },
1069                
1070                Token::OpAssign => {
1071                    ctx.set_end(&self.advance().unwrap());
1072                    
1073                    Some(Box::new(self.parse_expr(ctx)?))
1074                },
1075                
1076                _ => None,
1077            };
1078            
1079            // expect either a comma "," or the closing ")"
1080            let next = self.peek()?;
1081
1082            let mode = mode.unwrap_or(Access::ReadOnly);
1083            match next.token {
1084                // variadic parameter
1085                Token::Comma if is_variadic => {
1086                    return Err("a variadic parameter must appear last in the parameter list".into());
1087                }
1088                
1089                Token::CloseParen if is_variadic => {
1090                    debug_assert!(default_value.is_none());
1091                    variadic.replace(ParamDef { name, mode });
1092                },
1093                
1094                // normal parameter
1095                Token::Comma | Token::CloseParen if !is_variadic => {
1096                    if let Some(default_expr) = default_value {
1097                        default.push(DefaultDef { name, mode, default: default_expr });
1098                    } else {
1099                        if !default.is_empty() {
1100                            return Err("cannot have a non-default parameter after a default parameter".into());
1101                        }
1102                        required.push(ParamDef { name, mode });
1103                    }
1104                },
1105                
1106                _ => return Err("invalid parameter".into()),
1107            }
1108            
1109            if matches!(next.token, Token::Comma) {
1110                ctx.set_end(&self.advance().unwrap());
1111            }
1112            
1113            ctx.pop_extend();
1114        }
1115        
1116        let signature = SignatureDef {
1117            name: None,
1118            required: required.into_boxed_slice(),
1119            default: default.into_boxed_slice(),
1120            variadic,
1121        };
1122        
1123        Ok(signature)
1124    }
1125    
1126    /*
1127        Object Constructor syntax:
1128        
1129        object-constructor ::= "{" member-initializer ( "," member-initializer )* "}" ;
1130        member-initializer ::= ( IDENTIFIER | "[" primary "]" ) ":" expression ;
1131    
1132    */
1133    /*
1134    fn parse_object_constructor(&mut self, ctx: &mut ErrorContext) -> ParseResult<ObjectConstructor> {
1135        ctx.push(ContextTag::ObjectCtor);
1136        
1137        let next = self.advance().unwrap();
1138        ctx.set_start(&self.advance().unwrap());
1139        debug_assert!(matches!(next.token, Token::OpenBrace));
1140        
1141        unimplemented!();
1142        
1143        // let next = self.advance()?;
1144        // ctx.set_end(&next);
1145        
1146        // if !matches!(next.token, Token::CloseParen) {
1147        //     return Err(ParserError::new(ErrorKind::ExpectedCloseBrace, ctx.context()));
1148        // }
1149        
1150        // ctx.pop_extend();
1151    }
1152    */
1153    
1154    /*
1155        Primary expression syntax:
1156        
1157        primary ::= atom ( access | subscript | invocation | object-constructor )* ;
1158        subscript ::= "[" expression "]" ;
1159        access ::= "." IDENTIFIER ;
1160        invocation ::= "(" ... ")" ;  (* WIP *)
1161        object-constructor ::= "{" member-initializer ( "," member-initializer )* "}" ;
1162    */
1163    fn parse_primary(&mut self, ctx: &mut ErrorContext) -> ParseResult<Expr> { 
1164        ctx.push(ContextTag::PrimaryExpr);
1165        
1166        let atom = self.parse_atom(ctx)?;
1167        
1168        let mut items = Vec::new();
1169        loop {
1170            let next = self.peek()?;
1171            match next.token {
1172                
1173                // access ::= "." IDENTIFIER ;
1174                Token::OpAccess => items.push(self.parse_member_access(ctx)?),
1175                
1176                // subscript ::= "[" expression "]" ;
1177                Token::OpenSquare => items.push(self.parse_index_access(ctx)?),
1178                                
1179                // invocation ::= "(" ")" | "(" argument ( "," argument )* ")" ; 
1180                // argument ::= expression ( "..." )? ;  (* "..." is for argument unpacking syntax *)
1181                // invocations are not allowed to be on a separate line from the invocation receiver
1182                Token::OpenParen if !next.newline => items.push(self.parse_invocation(ctx)?),
1183                
1184                // object-constructor ::= "{" ... "}"
1185                Token::OpenBrace => {
1186                    unimplemented!()
1187                    // ctx.push(ContextTag::ObjectCtor);
1188                    // ctx.set_start(&self.advance().unwrap());
1189                    
1190                    // let obj_ctor = self.parse_object_constructor(ctx)?;
1191                    
1192                    // let next = self.advance()?;
1193                    // ctx.set_end(&next);
1194                    
1195                    // if matches!(next.token, Token::CloseParen) {
1196                    //     primary.push_construct(obj_ctor);
1197                    // } else {
1198                    //     return Err(ErrorKind::ExpectedCloseBrace.into());
1199                    // }
1200                    
1201                    // ctx.pop_extend();
1202                }
1203                
1204                _ => break,
1205            };
1206        }
1207        
1208        ctx.pop_extend();
1209        
1210        if items.is_empty() {
1211            Ok(Expr::Atom(atom))
1212        } else {
1213            Ok(Expr::Primary(Primary::new(atom, items)))
1214        }
1215    }
1216    
1217    // access ::= "." IDENTIFIER ;
1218    fn parse_member_access(&mut self, ctx: &mut ErrorContext) -> ParseResult<AccessItem> {
1219        let next = self.advance().unwrap();
1220        
1221        ctx.push(ContextTag::MemberAccess);
1222        ctx.set_start(&next);
1223        debug_assert!(matches!(next.token, Token::OpAccess));
1224        
1225        let next = self.advance()?;
1226        ctx.set_end(&next);
1227        
1228        let item;
1229        if let Token::Identifier(name) = next.token {
1230            item = AccessItem::Attribute(self.intern_str(name));
1231        } else {
1232            return Err("invalid Identifier".into());
1233        }
1234        
1235        ctx.pop_extend();
1236        Ok(item)
1237    }
1238    
1239    // subscript ::= "[" expression "]" ;
1240    fn parse_index_access(&mut self, ctx: &mut ErrorContext) -> ParseResult<AccessItem> {
1241        let next = self.advance().unwrap();
1242        
1243        ctx.push(ContextTag::IndexAccess);
1244        ctx.set_start(&next);
1245        debug_assert!(matches!(next.token, Token::OpenSquare));
1246        
1247        let index_expr = self.parse_expr(ctx)?;
1248        
1249        let next = self.advance()?;
1250        ctx.set_end(&next);
1251        
1252        if !matches!(next.token, Token::CloseSquare) {
1253            return Err("expected closing \"]\"".into());
1254        }
1255        
1256        ctx.pop_extend();
1257        Ok(AccessItem::Index(index_expr))
1258    }
1259    
1260    fn parse_invocation(&mut self, ctx: &mut ErrorContext) -> ParseResult<AccessItem> {
1261        let next = self.advance().unwrap();
1262        
1263        ctx.push(ContextTag::Invocation);
1264        ctx.set_start(&next);
1265        debug_assert!(matches!(next.token, Token::OpenParen));
1266        
1267        let mut args = Vec::new();
1268        
1269        // check for empty argument list
1270        if matches!(self.peek()?.token, Token::CloseParen) {
1271            
1272            ctx.set_end(&self.advance().unwrap());
1273            
1274        } else {
1275        
1276            // we use the fact that argument lists parse very similarly to tuples
1277            // parse a single ExprMeta. If the variant is a Tuple (not a group containing a tuple!),
1278            // that tuple's contents becomes the argument list.
1279            
1280            let (expr, symbol) = self.parse_expr(ctx)?.take();
1281            
1282            if let Expr::Tuple(items) = expr {
1283                args.extend(items.into_vec().into_iter());
1284            } else {
1285                args.push(ExprMeta::new(expr, symbol));
1286            }
1287            
1288            // check for close paren
1289            let next = self.advance()?;
1290            ctx.set_end(&next);
1291            if !matches!(next.token, Token::CloseParen) {
1292                return Err("expected closing \")\" after argument list".into());
1293            }
1294        }
1295        
1296        let invocation = AccessItem::Invoke(args.into_boxed_slice());
1297        
1298        ctx.pop_extend();
1299        Ok(invocation)
1300    }
1301    
1302    // atom ::= LITERAL | IDENTIFIER | "(" expression ")" ;
1303    fn parse_atom(&mut self, ctx: &mut ErrorContext) -> ParseResult<Atom> { 
1304        
1305        if let Token::OpenParen = self.peek()?.token {
1306            Ok(self.parse_group_expr(ctx)?)  // Groups
1307            
1308        } else { 
1309            ctx.push(ContextTag::Atom);
1310            
1311            let next = self.advance().unwrap();
1312            ctx.set_start(&next);
1313            
1314            let atom = match next.token {
1315                // Identifiers
1316                Token::Identifier(name) => {
1317                    Atom::Identifier(self.intern_str(name))
1318                },
1319                
1320                // Literals
1321                Token::Nil   => Atom::Nil,
1322                Token::True  => Atom::BooleanLiteral(true),
1323                Token::False => Atom::BooleanLiteral(false),
1324                
1325                Token::IntegerLiteral(value) => Atom::IntegerLiteral(value),
1326                Token::FloatLiteral(value)   => Atom::FloatLiteral(value),
1327                Token::StringLiteral(value)   => {
1328                    Atom::StringLiteral(self.intern_str(value))
1329                },
1330                
1331                // Error productions
1332                Token::Class | Token::Fun | Token::If | Token::Var | Token::Let | Token::Begin | Token::Label(..) => {
1333                    let name = match next.token {
1334                        Token::Class => "class definitions",
1335                        Token::Fun => "function definitions",
1336                        Token::Let => "\"let\"",
1337                        Token::Var => "\"var\"",
1338                        Token::Local => "\"local\"",
1339                        Token::NonLocal => "\"nonlocal\"",
1340                        Token::Begin => "block expressions",
1341                        _ => "this expression",
1342                    };
1343                    let message = format!("{} must be enclosed in parentheses to be used here", name);
1344                    
1345                    return Err(ErrorKind::SyntaxError(message).into())
1346                },
1347                
1348                Token::CloseParen => return Err("unmatched \")\"".into()),
1349                Token::CloseSquare => return Err("unmatched \"]\"".into()),
1350                Token::CloseBrace => return Err("unmatched \"}\"".into()),
1351                
1352                _ => { return Err("expected an expression here".into()) },
1353            };
1354            
1355            ctx.pop_extend();
1356            Ok(atom)
1357        }
1358    }
1359
1360    fn parse_group_expr(&mut self, ctx: &mut ErrorContext) -> ParseResult<Atom> {
1361        ctx.push(ContextTag::Group);
1362        
1363        let next = self.advance().unwrap(); // consume the "("
1364        ctx.set_start(&next);
1365        debug_assert!(matches!(next.token, Token::OpenParen));
1366        
1367        // Check for the empty tuple
1368        let next = self.peek()?;
1369        if let Token::CloseParen = next.token {
1370            ctx.set_end(&self.advance().unwrap());
1371            ctx.pop_extend();
1372            return Ok(Atom::EmptyTuple);
1373        }
1374
1375        // Check for lvalue modifier
1376        let mut modifier = self.try_parse_assign_keyword(ctx)?;
1377
1378        // Parse inner expression
1379        let mut expr = self.parse_expr_variant(ctx)?;
1380        
1381        // if inner expression is an assignment, transfer our modifier to it
1382        if let Expr::Assignment(assign) = &mut expr {
1383            assign.modifier = modifier.take().unwrap_or(assign.modifier);
1384        }
1385        
1386        // Consume and check closing paren
1387        let next = self.advance()?;
1388        ctx.set_end(&next);
1389        if !matches!(next.token, Token::CloseParen) {
1390            return Err("expected closing \")\"".into());
1391        }
1392        
1393        ctx.pop_extend();
1394        Ok(Atom::Group {
1395            modifier, inner: Box::new(expr),
1396        })
1397    }
1398
1399    /* LValue Parsing */
1400    fn try_parse_assign_keyword(&mut self, ctx: &mut ErrorContext) -> ParseResult<Option<AssignType>> {
1401        let next = self.peek()?;
1402
1403        // if we see any of these, then this is definitely an LValue
1404        let modifier = match next.token {
1405            Token::Let => Some(AssignType::DeclImmutable),
1406            Token::Var => Some(AssignType::DeclMutable),
1407            Token::Local => Some(AssignType::AssignLocal),
1408            Token::NonLocal => Some(AssignType::AssignNonLocal),
1409            _ => None,
1410        };
1411
1412        if modifier.is_some() {
1413            ctx.push(ContextTag::LValue);
1414            ctx.set_start(&self.advance().unwrap());
1415            ctx.pop_extend();
1416            return Ok(modifier);
1417        }
1418        Ok(None)
1419    }
1420
1421}
sphinx/parser.rs

sphinx/
parser.rs
