cas_parser/parser/
mod.rs

1pub mod ast;
2pub mod error;
3pub mod fmt;
4pub mod garbage;
5pub mod iter;
6pub mod keyword;
7pub mod token;
8
9use cas_error::ErrorKind;
10use error::{Error, kind};
11use super::tokenizer::{tokenize_complete, Token};
12use std::{ops::Range, sync::Arc};
13
14/// State that can be used to determine if certain parse trees are valid (e.g. if a checking if a
15/// `break` expression is inside a loop).
16///
17/// The state cannot be mutated directly; it can only be changed when parsing using the [`Parser::try_parse_with_state`] method.
18#[derive(Debug, Clone, Default)]
19pub struct ParserState {
20    /// Whether loop control expressions are allowed in the current context. This is used to
21    /// determine if a `break` or `continue` expression is valid.
22    pub allow_loop_control: bool,
23}
24
25/// A high-level parser for the language. This is the type to use to parse an arbitrary piece of
26/// code into an abstract syntax tree.
27///
28/// The parser contains an [`Arc`] to the tokens representing the source code to be parsed, and
29/// thus is relatively cheap to clone.
30#[derive(Debug, Clone)]
31pub struct Parser<'source> {
32    /// The tokens that this parser is currently parsing.
33    tokens: Arc<[Token<'source>]>,
34
35    /// The index of the **next** token to be parsed.
36    cursor: usize,
37
38    /// Holds state that can be used to determine if certain parse trees are valid (e.g. if a
39    /// checking if a `break` expression is inside a loop).
40    ///
41    /// The state cannot be mutated directly; it can only be changed when parsing using the [`Parser::try_parse_with_state`] method.
42    state: ParserState,
43}
44
45impl<'source> Parser<'source> {
46    /// Create a new parser for the given source.
47    pub fn new(source: &'source str) -> Self {
48        Self {
49            tokens: tokenize_complete(source).into(),
50            cursor: 0,
51            state: ParserState::default(),
52        }
53    }
54
55    /// Returns an immutable reference to the parser's state.
56    pub fn state(&self) -> &ParserState {
57        &self.state
58    }
59
60    /// Sets the parser to point to the same token as the given parser. It is assumed that both
61    /// parsers point to the same source code.
62    pub fn set_cursor(&mut self, other: &Self) {
63        self.cursor = other.cursor;
64    }
65
66    /// Creates an error that points at the current token, or the end of the source code if the
67    /// cursor is at the end of the stream.
68    pub fn error(&self, kind: impl ErrorKind + 'static) -> Error {
69        Error::new(vec![self.span()], kind)
70    }
71
72    /// Returns a span pointing at the end of the source code.
73    pub fn eof_span(&self) -> Range<usize> {
74        self.tokens.last().map_or(0..0, |token| token.span.end..token.span.end)
75    }
76
77    /// Returns the span of the current token, or the end of the source code if the cursor is at
78    /// the end of the stream.
79    pub fn span(&self) -> Range<usize> {
80        self.tokens
81            .get(self.cursor)
82            .map_or(self.eof_span(), |token| token.span.clone())
83    }
84
85    /// Move the cursor to the previous token. This function is a no-op if the cursor is at the
86    /// beginning of the stream.
87    pub fn prev(&mut self) {
88        if self.cursor > 0 {
89            self.cursor -= 1;
90        }
91    }
92
93    /// Returns the previous token. The cursor is not moved. Returns [`None`] if the cursor is at
94    /// the beginning of the stream.
95    pub fn prev_token(&self) -> Option<&Token<'source>> {
96        self.tokens.get(self.cursor.checked_sub(1)?)
97    }
98
99    /// Returns the current token. The cursor is not moved. Returns [`None`] if the cursor is at
100    /// the end of the stream.
101    pub fn current_token(&self) -> Option<&Token<'source>> {
102        self.tokens.get(self.cursor)
103    }
104
105    /// Advances the cursor past whitespace tokens to the next non-whitespace token. The cursor is
106    /// not guaranteed to point to a valid token (might be out of bounds), but if the token is
107    /// valid, it is guaranteed to be non-whitespace.
108    pub fn advance_past_whitespace(&mut self) {
109        while let Some(token) = self.tokens.get(self.cursor) {
110            if token.is_ignore() {
111                self.cursor += 1;
112                continue;
113            } else {
114                break;
115            }
116        }
117    }
118
119    /// Advances the cursor past non-significant whitespace tokens to the next token. **This next
120    /// token can be a newline.**
121    ///
122    /// The cursor is not guaranteed to point to a valid token (might be out of bounds), but if the
123    /// token is valid, it is guaranteed to be a newline, or otherwise, non-whitespace.
124    ///
125    /// Newlines are significant in the context of implicit multiplication. Allowing implicit
126    /// multiplication to span multiple lines has shown to be confusing and error-prone; for
127    /// example, consider how this reasonably-looking file would be parsed (before implicit
128    /// multiplication was restricted to the same line):
129    ///
130    /// ```text
131    /// fact(n) = {
132    ///     out = n;
133    ///     while n > 1 then {
134    ///         n -= 1;
135    ///         out *= n;
136    ///     };
137    ///     out
138    /// }
139    ///
140    /// fact(14) == 14!
141    /// ```
142    ///
143    /// You would expect this code to behave like so:
144    ///
145    /// 1. Define the `fact` function.
146    /// 2. Call the `fact` function with the argument `14` and compare the result to `14!`.
147    ///
148    /// It certainly seems that way. However, in this example, implicit multiplication is actually
149    /// inserted between the "end" of the function definition `}`, and `fact(14)`, resulting in:
150    ///
151    /// ```text
152    /// fact(n) = {
153    ///     out = n;
154    ///     while n > 1 then {
155    ///         n -= 1;
156    ///         out *= n;
157    ///     };
158    ///     out
159    /// }
160    /// * // <-- implicit multiplication!!
161    /// fact(14) == 14!
162    /// ```
163    ///
164    /// The comparison `fact(14) == 14!` actually ends up being a part of the `fact` function
165    /// definition, and no comparison is made! This function is used to prevent such confusion
166    /// during parsing.
167    pub fn advance_past_non_significant_whitespace(&mut self) {
168        while let Some(token) = self.tokens.get(self.cursor) {
169            if token.is_ignore() && !token.is_significant_whitespace() {
170                self.cursor += 1;
171                continue;
172            } else {
173                break;
174            }
175        }
176    }
177
178    /// Returns the current token, then advances the cursor. Whitespace tokens are skipped.
179    ///
180    /// Returns an EOF error if there are no more tokens.
181    pub fn next_token(&mut self) -> Result<Token<'source>, Error> {
182        self.advance_past_whitespace();
183        self.next_token_raw()
184    }
185
186    /// Returns the current token, then advances the cursor. Whitespace tokens **are not** skipped.
187    ///
188    /// Returns an EOF error if there are no more tokens.
189    pub fn next_token_raw(&mut self) -> Result<Token<'source>, Error> {
190        let result = self.current_token()
191            .cloned() // cloning is cheap; only Range<_> is cloned
192            .ok_or_else(|| self.error(kind::UnexpectedEof));
193        self.cursor += 1;
194        result
195    }
196
197    /// Speculatively parses a value from the given stream of tokens. This function can be used
198    /// in the [`Parse::parse`] implementation of a type with the given [`Parser`], as it will
199    /// automatically backtrack the cursor position if parsing fails.
200    ///
201    /// If parsing is successful, the stream is advanced past the consumed tokens and the parsed
202    /// value is returned. Otherwise, the stream is left unchanged and an error is returned.
203    pub fn try_parse<T: Parse<'source>>(&mut self) -> ParseResult<T> {
204        self.try_parse_with_fn(T::parse)
205    }
206
207    /// Speculatively parses a value from the given stream of tokens. Before parsing, a copy of the
208    /// parser is created with the state mutated using the given function. The original parser's
209    /// state will not change, but the cursor position can be advanced if the new parser was
210    /// successful.
211    ///
212    /// This function can be used in the [`Parse::parse`] implementation of a type with the given
213    /// [`Parser`], as it will automatically backtrack the cursor position if parsing fails.
214    ///
215    /// If parsing is successful, the stream is advanced past the consumed tokens and the parsed
216    /// value is returned. Otherwise, the stream is left unchanged and an error is returned.
217    pub fn try_parse_with_state<F, T>(&mut self, modify_state: F) -> ParseResult<T>
218    where
219        F: FnOnce(&mut ParserState),
220        T: Parse<'source>,
221    {
222        let mut state = self.state.clone();
223        modify_state(&mut state);
224
225        let mut new_parser = Self {
226            tokens: self.tokens.clone(),
227            cursor: self.cursor,
228            state,
229        };
230
231        let t = new_parser.try_parse();
232        self.set_cursor(&new_parser);
233        t
234    }
235
236    /// Speculatively parses a value from the given stream of tokens, using a custom parsing
237    /// function to parse the value. This function can be used in the [`Parse::parse`]
238    /// implementation of a type with the given [`Parser`], as it will automatically backtrack the
239    /// cursor position if parsing fails.
240    ///
241    /// If parsing is successful, the stream is advanced past the consumed tokens and the parsed
242    /// value is returned. Otherwise, the stream is left unchanged and an error is returned.
243    pub fn try_parse_with_fn<T, F>(&mut self, f: F) -> ParseResult<T>
244    where
245        F: FnOnce(&mut Parser<'source>) -> ParseResult<T>,
246    {
247        let start = self.cursor;
248        f(self).inspect_unrecoverable(|_| self.cursor = start)
249    }
250
251    /// Speculatively parses a value from the given stream of tokens, with a validation predicate.
252    /// The value must parse successfully, **and** the predicate must return [`Ok`] for this
253    /// function to return successfully.
254    ///
255    /// If parsing is successful, the stream is advanced past the consumed tokens and the parsed
256    /// value is returned. Otherwise, the stream is left unchanged and an error is returned.
257    pub fn try_parse_then<T: Parse<'source>, F>(&mut self, predicate: F) -> ParseResult<T>
258    where
259        F: FnOnce(&T, &Parser) -> ParseResult<()>,
260    {
261        let start = self.cursor;
262        let mut errors = Vec::new();
263
264        let inner = || {
265            let value = T::parse(self).forward_errors(&mut errors)?;
266            predicate(&value, self).forward_errors(&mut errors)?;
267            Ok(value)
268        };
269
270        inner()
271            .map(|value| (value, errors))
272            .map_err(|unrecoverable: Vec<Error>| {
273                self.cursor = start;
274                unrecoverable
275            })
276            .into()
277    }
278
279    /// Attempts to parse a value from the given stream of tokens. All the tokens must be consumed
280    /// by the parser; if not, an error is returned.
281    pub fn try_parse_full<T: Parse<'source>>(&mut self) -> Result<T, Vec<Error>> {
282        let mut errors = Vec::new();
283        let value = T::parse(self).forward_errors(&mut errors)?;
284
285        // consume whitespace
286        self.advance_past_whitespace();
287
288        if self.cursor < self.tokens.len() {
289            errors.push(self.error(kind::ExpectedEof));
290        }
291
292        if errors.is_empty() {
293            Ok(value)
294        } else {
295            Err(errors)
296        }
297    }
298
299    /// Attempts to parse multiple values from the given stream of tokens. All the tokens must be
300    /// consumed by the parser; if not, an error is returned.
301    pub fn try_parse_full_many<T: std::fmt::Debug + Parse<'source>>(&mut self) -> Result<Vec<T>, Vec<Error>> {
302        let mut errors = Vec::new();
303        let mut values = Vec::new();
304
305        while self.cursor < self.tokens.len() {
306            let Ok(value) = T::parse(self).forward_errors(&mut errors) else {
307                break;
308            };
309            values.push(value);
310        }
311
312        // consume whitespace
313        self.advance_past_whitespace();
314
315        if self.cursor < self.tokens.len() {
316            errors.push(self.error(kind::ExpectedEof));
317        }
318
319        if errors.is_empty() {
320            Ok(values)
321        } else {
322            Err(errors)
323        }
324    }
325}
326
327/// Any type that can be parsed from a source of tokens.
328pub trait Parse<'source>: Sized {
329    /// Parses a value from the given stream of tokens, advancing the stream past the consumed
330    /// tokens if parsing is successful.
331    ///
332    /// If any recoverable errors are encountered, they should be appended to the given [`Vec`],
333    /// and parsing should continue as normal. If an unrecoverable error is encountered, parsing
334    /// should abort with said error.
335    ///
336    /// This function should be used by private functions in the library.
337    fn std_parse(
338        input: &mut Parser<'source>,
339        recoverable_errors: &mut Vec<Error>
340    ) -> Result<Self, Vec<Error>>;
341
342    /// Parses a value from the given stream of tokens, advancing the stream past the consumed
343    /// tokens if parsing is successful.
344    ///
345    /// This function should be used by users of this parser.
346    fn parse(input: &mut Parser<'source>) -> ParseResult<Self> {
347        let mut recoverable_errors = Vec::new();
348        Self::std_parse(input, &mut recoverable_errors)
349            .map(|value| (value, recoverable_errors))
350            .into()
351    }
352}
353
354/// The result of a parsing operation.
355#[derive(Debug)]
356pub enum ParseResult<T> {
357    /// Parsing was successful.
358    Ok(T),
359
360    /// An error occurred while parsing, however the parser attempted to recover and has tried to
361    /// continue parsing in order to find more errors. The recovered value is returned in addition
362    /// to all the errors that were found.
363    ///
364    /// There are **no** guarantees on whether the recovered value is valid or not. Thus, it should
365    /// only be used to allow the parser to continue parsing, and should not be shown to the user.
366    Recoverable(T, Vec<Error>),
367
368    /// An error occurred while parsing, and the parser was unable to recover. Parsing is aborted
369    /// and the error are returned.
370    Unrecoverable(Vec<Error>),
371}
372
373impl<T> From<Result<(T, Vec<Error>), Vec<Error>>> for ParseResult<T> {
374    fn from(result: Result<(T, Vec<Error>), Vec<Error>>) -> Self {
375        match result {
376            Ok((value, errors)) => (value, errors).into(),
377            Err(unrecoverable_errors) => Self::Unrecoverable(unrecoverable_errors),
378        }
379    }
380}
381
382impl<T> From<(T, Vec<Error>)> for ParseResult<T> {
383    fn from((value, errors): (T, Vec<Error>)) -> Self {
384        if errors.is_empty() {
385            Self::Ok(value)
386        } else {
387            Self::Recoverable(value, errors)
388        }
389    }
390}
391
392impl<T> From<Vec<Error>> for ParseResult<T> {
393    fn from(errors: Vec<Error>) -> Self {
394        Self::Unrecoverable(errors)
395    }
396}
397
398impl<T> ParseResult<T> {
399    /// Converts the [`ParseResult<T>`] to a [`Result<T, Vec<Error>>`], using these rules:
400    ///
401    /// - [`ParseResult::Ok`] is converted to [`Ok`].
402    /// - [`ParseResult::Recoverable`] is converted to [`Ok`]. The errors are appended to the given
403    /// mutable [`Vec`].
404    /// - [`ParseResult::Unrecoverable`] is converted to [`Err`].
405    ///
406    /// This can be a convenient way to allow utilizing the [`?`] operator in a parsing function,
407    /// while still holding onto errors that were found for later reporting.
408    pub fn forward_errors(self, errors: &mut Vec<Error>) -> Result<T, Vec<Error>> {
409        match self {
410            Self::Ok(value) => Ok(value),
411            Self::Recoverable(value, mut errs) => {
412                errors.append(&mut errs);
413                Ok(value)
414            },
415            Self::Unrecoverable(errs) => Err(errs),
416        }
417    }
418
419    /// Returns `true` if the result is [`ParseResult::Ok`].
420    pub fn is_ok(&self) -> bool {
421        matches!(self, ParseResult::Ok(_))
422    }
423
424    /// Calls the provided closure with a reference to the contained unrecoverable error.
425    ///
426    /// This is equivalent to [`Result::inspect_err`].
427    pub fn inspect_unrecoverable<F>(self, f: F) -> Self
428    where
429        F: FnOnce(&Vec<Error>),
430    {
431        if let Self::Unrecoverable(errs) = &self {
432            f(errs);
433        }
434
435        self
436    }
437
438    /// Maps a `ParseResult<T>` to `ParseResult<U>` by applying a function to a contained
439    /// [`ParseResult::Ok`] or [`ParseResult::Recoverable`] value, leaving an
440    /// [`ParseResult::Unrecoverable`] value untouched.
441    ///
442    /// This is equivalent to [`Result::map`].
443    pub fn map<U, F>(self, f: F) -> ParseResult<U>
444    where
445        F: FnOnce(T) -> U,
446    {
447        match self {
448            ParseResult::Ok(value) => ParseResult::Ok(f(value)),
449            ParseResult::Recoverable(value, errors) => ParseResult::Recoverable(f(value), errors),
450
451            // this line cannot be simplified to `err => err`, because then both the left hand side
452            // and right hand side are type `ParseResult<T>`!
453            ParseResult::Unrecoverable(errors) => ParseResult::Unrecoverable(errors),
454        }
455    }
456
457    /// Calls `op` if the result is an error, otherwise returns the `Ok` value of `self`.
458    ///
459    /// This is similar to [`Result::or_else`], but no error value is given to the closure.
460    pub fn or_else<F>(self, op: F) -> Self
461    where
462        F: FnOnce() -> Self,
463    {
464        match self {
465            ParseResult::Recoverable(..) | ParseResult::Unrecoverable(_) => op(),
466            ok => ok,
467        }
468    }
469}
470
471/// Convenience macro to short-circuit from a parsing function if the given [`Result`] is [`Ok`],
472/// or return the contained error if the result is [`Err`].
473///
474/// This is essentially the opposite of the [`try!`] macro.
475#[macro_export]
476macro_rules! return_if_ok {
477    ($result:expr) => {
478        match $result {
479            Ok(value) => return Ok(value),
480            Err(errors) => errors,
481        }
482    };
483}
484
485#[cfg(test)]
486mod tests {
487    use pretty_assertions::assert_eq;
488    use super::*;
489
490    use ast::*;
491    use token::op::{AssignOp, AssignOpKind, BinOp, BinOpKind, UnaryOp, UnaryOpKind};
492
493    #[test]
494    fn literal_int() {
495        let mut parser = Parser::new("16");
496        let expr = parser.try_parse_full::<Expr>().unwrap();
497
498        assert_eq!(expr, Expr::Literal(Literal::Integer(LitInt {
499            value: "16".to_string(),
500            span: 0..2,
501        })));
502    }
503
504    #[test]
505    fn literal_float() {
506        let mut parser = Parser::new("3.14");
507        let expr = parser.try_parse_full::<Expr>().unwrap();
508
509        assert_eq!(expr, Expr::Literal(Literal::Float(LitFloat {
510            value: "3.14".to_string(),
511            span: 0..4,
512        })));
513    }
514
515    #[test]
516    fn literal_float_2() {
517        let mut parser = Parser::new(".75");
518        let expr = parser.try_parse_full::<Expr>().unwrap();
519
520        assert_eq!(expr, Expr::Literal(Literal::Float(LitFloat {
521            value: ".75".to_string(),
522            span: 0..3,
523        })));
524    }
525
526    #[test]
527    fn literal_radix_base_2() {
528        let mut parser = Parser::new("2'10000110000");
529        let expr = parser.try_parse_full::<Expr>().unwrap();
530
531        assert_eq!(expr, Expr::Literal(Literal::Radix(LitRadix {
532            base: 2,
533            value: "10000110000".to_string(),
534            span: 0..13,
535        })));
536    }
537
538    #[test]
539    fn literal_radix_base_8() {
540        let mut parser = Parser::new("8'2060");
541        let expr = parser.try_parse_full::<Expr>().unwrap();
542
543        assert_eq!(expr, Expr::Literal(Literal::Radix(LitRadix {
544            base: 8,
545            value: "2060".to_string(),
546            span: 0..6,
547        })));
548    }
549
550    #[test]
551    fn literal_radix_base_25() {
552        let mut parser = Parser::new("25'1hm");
553        let expr = parser.try_parse_full::<Expr>().unwrap();
554
555        assert_eq!(expr, Expr::Literal(Literal::Radix(LitRadix {
556            base: 25,
557            value: "1hm".to_string(),
558            span: 0..6,
559        })));
560    }
561
562    #[test]
563    fn literal_radix_base_32() {
564        let mut parser = Parser::new("32'11g");
565        let expr = parser.try_parse_full::<Expr>().unwrap();
566
567        assert_eq!(expr, Expr::Literal(Literal::Radix(LitRadix {
568            base: 32,
569            value: "11g".to_string(),
570            span: 0..6,
571        })));
572    }
573
574    #[test]
575    fn literal_radix_base_47() {
576        let mut parser = Parser::new("47'mC");
577        let expr = parser.try_parse_full::<Expr>().unwrap();
578
579        assert_eq!(expr, Expr::Literal(Literal::Radix(LitRadix {
580            base: 47,
581            value: "mC".to_string(),
582            span: 0..5,
583        })));
584    }
585
586    #[test]
587    fn literal_radix_with_nonword_tokens() {
588        let mut parser = Parser::new("64'++/+//");
589        let expr = parser.try_parse_full::<Expr>().unwrap();
590
591        assert_eq!(expr, Expr::Literal(Literal::Radix(LitRadix {
592            base: 64,
593            value: "++/+//".to_string(),
594            span: 0..9,
595        })));
596    }
597
598    #[test]
599    fn literal_symbol() {
600        let mut parser = Parser::new("pi");
601        let expr = parser.try_parse_full::<Expr>().unwrap();
602
603        assert_eq!(expr, Expr::Literal(Literal::Symbol(LitSym {
604            name: "pi".to_string(),
605            span: 0..2,
606        })));
607    }
608
609    #[test]
610    fn unary_left_associativity() {
611        let mut parser = Parser::new("3!!");
612        let expr = parser.try_parse_full::<Expr>().unwrap();
613
614        assert_eq!(expr, Expr::Unary(Unary {
615            operand: Box::new(Expr::Unary(Unary {
616                operand: Box::new(Expr::Literal(Literal::Integer(LitInt {
617                    value: "3".to_string(),
618                    span: 0..1,
619                }))),
620                op: UnaryOp {
621                    kind: UnaryOpKind::Factorial,
622                    span: 1..2,
623                },
624                span: 0..2,
625            })),
626            op: UnaryOp {
627                kind: UnaryOpKind::Factorial,
628                span: 2..3,
629            },
630            span: 0..3,
631        }));
632    }
633
634    #[test]
635    fn unary_right_associativity() {
636        let mut parser = Parser::new("not not --3");
637        let expr = parser.try_parse_full::<Expr>().unwrap();
638
639        assert_eq!(expr, Expr::Unary(Unary {
640            operand: Box::new(Expr::Unary(Unary {
641                operand: Box::new(Expr::Unary(Unary {
642                    operand: Box::new(Expr::Unary(Unary {
643                        operand: Box::new(Expr::Literal(Literal::Integer(LitInt {
644                            value: "3".to_string(),
645                            span: 10..11,
646                        }))),
647                        op: UnaryOp {
648                            kind: UnaryOpKind::Neg,
649                            span: 9..10,
650                        },
651                        span: 9..11,
652                    })),
653                    op: UnaryOp {
654                        kind: UnaryOpKind::Neg,
655                        span: 8..9,
656                    },
657                    span: 8..11,
658                })),
659                op: UnaryOp {
660                    kind: UnaryOpKind::Not,
661                    span: 4..7,
662                },
663                span: 4..11,
664            })),
665            op: UnaryOp {
666                kind: UnaryOpKind::Not,
667                span: 0..3,
668            },
669            span: 0..11,
670        }));
671    }
672
673    #[test]
674    fn wrong_unary() {
675        let mut parser = Parser::new("!3");
676        assert!(parser.try_parse_full::<Expr>().is_err());
677    }
678
679    #[test]
680    fn unary_complicated() {
681        let mut parser = Parser::new("not 3!! + -4");
682        let expr = parser.try_parse_full::<Expr>().unwrap();
683
684        assert_eq!(expr, Expr::Binary(Binary {
685            lhs: Box::new(Expr::Unary(Unary {
686                operand: Box::new(Expr::Unary(Unary {
687                    operand: Box::new(Expr::Unary(Unary {
688                        operand: Box::new(Expr::Literal(Literal::Integer(LitInt {
689                            value: "3".to_string(),
690                            span: 4..5,
691                        }))),
692                        op: UnaryOp {
693                            kind: UnaryOpKind::Factorial,
694                            span: 5..6,
695                        },
696                        span: 4..6,
697                    })),
698                    op: UnaryOp {
699                        kind: UnaryOpKind::Factorial,
700                        span: 6..7,
701                    },
702                    span: 4..7,
703                })),
704                op: UnaryOp {
705                    kind: UnaryOpKind::Not,
706                    span: 0..3,
707                },
708                span: 0..7,
709            })),
710            op: BinOp {
711                kind: BinOpKind::Add,
712                implicit: false,
713                span: 8..9,
714            },
715            rhs: Box::new(Expr::Unary(Unary {
716                operand: Box::new(Expr::Literal(Literal::Integer(LitInt {
717                    value: "4".to_string(),
718                    span: 11..12,
719                }))),
720                op: UnaryOp {
721                    kind: UnaryOpKind::Neg,
722                    span: 10..11,
723                },
724                span: 10..12,
725            })),
726            span: 0..12,
727        }));
728    }
729
730    #[test]
731    fn binary_left_associativity() {
732        let mut parser = Parser::new("3 * x * 5");
733        let expr = parser.try_parse_full::<Expr>().unwrap();
734
735        assert_eq!(expr, Expr::Binary(Binary {
736            lhs: Box::new(Expr::Binary(Binary {
737                lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
738                    value: "3".to_string(),
739                    span: 0..1,
740                }))),
741                op: BinOp {
742                    kind: BinOpKind::Mul,
743                    implicit: false,
744                    span: 2..3,
745                },
746                rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
747                    name: "x".to_string(),
748                    span: 4..5,
749                }))),
750                span: 0..5,
751            })),
752            op: BinOp {
753                kind: BinOpKind::Mul,
754                implicit: false,
755                span: 6..7,
756            },
757            rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
758                value: "5".to_string(),
759                span: 8..9,
760            }))),
761            span: 0..9,
762        }));
763    }
764
765    #[test]
766    fn binary_left_associativity_mix_precedence() {
767        let mut parser = Parser::new("3 + 4 * a + b");
768        let expr = parser.try_parse_full::<Expr>().unwrap();
769
770        assert_eq!(expr, Expr::Binary(Binary {
771            lhs: Box::new(Expr::Binary(Binary {
772                lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
773                    value: "3".to_string(),
774                    span: 0..1,
775                }))),
776                op: BinOp {
777                    kind: BinOpKind::Add,
778                    implicit: false,
779                    span: 2..3,
780                },
781                rhs: Box::new(Expr::Binary(Binary {
782                    lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
783                        value: "4".to_string(),
784                        span: 4..5,
785                    }))),
786                    op: BinOp {
787                        kind: BinOpKind::Mul,
788                        implicit: false,
789                        span: 6..7,
790                    },
791                    rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
792                        name: "a".to_string(),
793                        span: 8..9,
794                    }))),
795                    span: 4..9,
796                })),
797                span: 0..9,
798            })),
799            op: BinOp {
800                kind: BinOpKind::Add,
801                implicit: false,
802                span: 10..11,
803            },
804            rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
805                name: "b".to_string(),
806                span: 12..13,
807            }))),
808            span: 0..13,
809        }));
810    }
811
812    #[test]
813    fn binary_right_associativity() {
814        let mut parser = Parser::new("1 ^ 2 ^ 3");
815        let expr = parser.try_parse_full::<Expr>().unwrap();
816
817        assert_eq!(expr, Expr::Binary(Binary {
818            lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
819                value: "1".to_string(),
820                span: 0..1,
821            }))),
822            op: BinOp {
823                kind: BinOpKind::Exp,
824                implicit: false,
825                span: 2..3,
826            },
827            rhs: Box::new(Expr::Binary(Binary {
828                lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
829                    value: "2".to_string(),
830                    span: 4..5,
831                }))),
832                op: BinOp {
833                    kind: BinOpKind::Exp,
834                    implicit: false,
835                    span: 6..7,
836                },
837                rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
838                    value: "3".to_string(),
839                    span: 8..9,
840                }))),
841                span: 4..9,
842            })),
843            span: 0..9,
844        }));
845    }
846
847    #[test]
848    fn binary_complicated() {
849        let mut parser = Parser::new("1 + 2 * 3 - 4 / 5 ^ 6");
850        let expr = parser.try_parse_full::<Expr>().unwrap();
851
852        // 2 * 3
853        let mul = Expr::Binary(Binary {
854            lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
855                value: "2".to_string(),
856                span: 4..5,
857            }))),
858            op: BinOp {
859                kind: BinOpKind::Mul,
860                implicit: false,
861                span: 6..7,
862            },
863            rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
864                value: "3".to_string(),
865                span: 8..9,
866            }))),
867            span: 4..9,
868        });
869
870        // 1 + 2 * 3
871        let add = Expr::Binary(Binary {
872            lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
873                value: "1".to_string(),
874                span: 0..1,
875            }))),
876            op: BinOp {
877                kind: BinOpKind::Add,
878                implicit: false,
879                span: 2..3,
880            },
881            rhs: Box::new(mul),
882            span: 0..9,
883        });
884
885        // 5 ^ 6
886        let exp = Expr::Binary(Binary {
887            lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
888                value: "5".to_string(),
889                span: 16..17,
890            }))),
891            op: BinOp {
892                kind: BinOpKind::Exp,
893                implicit: false,
894                span: 18..19,
895            },
896            rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
897                value: "6".to_string(),
898                span: 20..21,
899            }))),
900            span: 16..21,
901        });
902
903        // 4 / 5 ^ 6
904        let div = Expr::Binary(Binary {
905            lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
906                value: "4".to_string(),
907                span: 12..13,
908            }))),
909            op: BinOp {
910                kind: BinOpKind::Div,
911                implicit: false,
912                span: 14..15,
913            },
914            rhs: Box::new(exp),
915            span: 12..21,
916        });
917
918        // 1 + 2 * 3 - 4 / 5 ^ 6
919        let sub = Expr::Binary(Binary {
920            lhs: Box::new(add),
921            op: BinOp {
922                kind: BinOpKind::Sub,
923                implicit: false,
924                span: 10..11,
925            },
926            rhs: Box::new(div),
927            span: 0..21,
928        });
929
930        assert_eq!(expr, sub);
931    }
932
933    #[test]
934    fn binary_and_unary() {
935        let mut parser = Parser::new("-1 ^ -2 * 3");
936        let expr = parser.try_parse_full::<Expr>().unwrap();
937
938        assert_eq!(expr, Expr::Binary(Binary {
939            lhs: Box::new(Expr::Unary(Unary {
940                operand: Box::new(Expr::Binary(Binary {
941                    lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
942                        value: "1".to_string(),
943                        span: 1..2,
944                    }))),
945                    op: BinOp {
946                        kind: BinOpKind::Exp,
947                        implicit: false,
948                        span: 3..4,
949                    },
950                    rhs: Box::new(Expr::Unary(Unary {
951                        operand: Box::new(Expr::Literal(Literal::Integer(LitInt {
952                            value: "2".to_string(),
953                            span: 6..7,
954                        }))),
955                        op: UnaryOp {
956                            kind: UnaryOpKind::Neg,
957                            span: 5..6,
958                        },
959                        span: 5..7,
960                    })),
961                    span: 1..7,
962                })),
963                op: UnaryOp {
964                    kind: UnaryOpKind::Neg,
965                    span: 0..1,
966                },
967                span: 0..7,
968            })),
969            op: BinOp {
970                kind: BinOpKind::Mul,
971                implicit: false,
972                span: 8..9,
973            },
974            rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
975                value: "3".to_string(),
976                span: 10..11,
977            }))),
978            span: 0..11,
979        }));
980    }
981
982    #[test]
983    fn complicated_binary_and_unary() {
984        let mut parser = Parser::new("pi^2 * 17! / -4.9 + e");
985        let expr = parser.try_parse_full::<Expr>().unwrap();
986
987        assert_eq!(expr, Expr::Binary(Binary {
988            lhs: Box::new(Expr::Binary(Binary {
989                lhs: Box::new(Expr::Binary(Binary {
990                    lhs: Box::new(Expr::Binary(Binary {
991                        lhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
992                            name: "pi".to_string(),
993                            span: 0..2,
994                        }))),
995                        op: BinOp {
996                            kind: BinOpKind::Exp,
997                            implicit: false,
998                            span: 2..3,
999                        },
1000                        rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1001                            value: "2".to_string(),
1002                            span: 3..4,
1003                        }))),
1004                        span: 0..4,
1005                    })),
1006                    op: BinOp {
1007                        kind: BinOpKind::Mul,
1008                        implicit: false,
1009                        span: 5..6,
1010                    },
1011                    rhs: Box::new(Expr::Unary(Unary {
1012                        operand: Box::new(Expr::Literal(Literal::Integer(LitInt {
1013                            value: "17".to_string(),
1014                            span: 7..9,
1015                        }))),
1016                        op: UnaryOp {
1017                            kind: UnaryOpKind::Factorial,
1018                            span: 9..10,
1019                        },
1020                        span: 7..10,
1021                    })),
1022                    span: 0..10,
1023                })),
1024                op: BinOp {
1025                    kind: BinOpKind::Div,
1026                    implicit: false,
1027                    span: 11..12,
1028                },
1029                rhs: Box::new(Expr::Unary(Unary {
1030                    operand: Box::new(Expr::Literal(Literal::Float(LitFloat {
1031                        value: "4.9".to_string(),
1032                        span: 14..17,
1033                    }))),
1034                    op: UnaryOp {
1035                        kind: UnaryOpKind::Neg,
1036                        span: 13..14,
1037                    },
1038                    span: 13..17,
1039                })),
1040                span: 0..17,
1041            })),
1042            op: BinOp {
1043                kind: BinOpKind::Add,
1044                implicit: false,
1045                span: 18..19,
1046            },
1047            rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1048                name: "e".to_string(),
1049                span: 20..21,
1050            }))),
1051            span: 0..21,
1052        }));
1053    }
1054
1055    #[test]
1056    fn implicit_multiplication() {
1057        let mut parser = Parser::new("2(3 + 4)");
1058        let expr = parser.try_parse_full::<Expr>().unwrap();
1059
1060        assert_eq!(expr, Expr::Binary(Binary {
1061            lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1062                value: "2".to_string(),
1063                span: 0..1,
1064            }))),
1065            op: BinOp {
1066                kind: BinOpKind::Mul,
1067                implicit: true,
1068                span: 1..1,
1069            },
1070            rhs: Box::new(Expr::Paren(Paren {
1071                expr: Box::new(Expr::Binary(Binary {
1072                    lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1073                        value: "3".to_string(),
1074                        span: 2..3,
1075                    }))),
1076                    op: BinOp {
1077                        kind: BinOpKind::Add,
1078                        implicit: false,
1079                        span: 4..5,
1080                    },
1081                    rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1082                        value: "4".to_string(),
1083                        span: 6..7,
1084                    }))),
1085                    span: 2..7,
1086                })),
1087                span: 1..8,
1088            })),
1089            span: 0..8,
1090        }));
1091    }
1092
1093    #[test]
1094    fn implicit_multiplication_2() {
1095        let mut parser = Parser::new("1 + 2x");
1096        let expr = parser.try_parse_full::<Expr>().unwrap();
1097
1098        assert_eq!(expr, Expr::Binary(Binary {
1099            lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1100                value: "1".to_string(),
1101                span: 0..1,
1102            }))),
1103            op: BinOp {
1104                kind: BinOpKind::Add,
1105                implicit: false,
1106                span: 2..3,
1107            },
1108            rhs: Box::new(Expr::Binary(Binary {
1109                lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1110                    value: "2".to_string(),
1111                    span: 4..5,
1112                }))),
1113                op: BinOp {
1114                    kind: BinOpKind::Mul,
1115                    implicit: true,
1116                    span: 5..5,
1117                },
1118                rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1119                    name: "x".to_string(),
1120                    span: 5..6,
1121                }))),
1122                span: 4..6,
1123            })),
1124            span: 0..6,
1125        }));
1126    }
1127
1128    #[test]
1129    fn implicit_multiplication_3() {
1130        let mut parser = Parser::new("(1 - x)(1 + x)");
1131        let expr = parser.try_parse_full::<Expr>().unwrap();
1132
1133        assert_eq!(expr, Expr::Binary(Binary {
1134            lhs: Box::new(Expr::Paren(Paren {
1135                expr: Box::new(Expr::Binary(Binary {
1136                    lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1137                        value: "1".to_string(),
1138                        span: 1..2,
1139                    }))),
1140                    op: BinOp {
1141                        kind: BinOpKind::Sub,
1142                        implicit: false,
1143                        span: 3..4,
1144                    },
1145                    rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1146                        name: "x".to_string(),
1147                        span: 5..6,
1148                    }))),
1149                    span: 1..6,
1150                })),
1151                span: 0..7,
1152            })),
1153            op: BinOp {
1154                kind: BinOpKind::Mul,
1155                implicit: true,
1156                span: 7..7,
1157            },
1158            rhs: Box::new(Expr::Paren(Paren {
1159                expr: Box::new(Expr::Binary(Binary {
1160                    lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1161                        value: "1".to_string(),
1162                        span: 8..9,
1163                    }))),
1164                    op: BinOp {
1165                        kind: BinOpKind::Add,
1166                        implicit: false,
1167                        span: 10..11,
1168                    },
1169                    rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1170                        name: "x".to_string(),
1171                        span: 12..13,
1172                    }))),
1173                    span: 8..13,
1174                })),
1175                span: 7..14,
1176            })),
1177            span: 0..14,
1178        }));
1179    }
1180
1181    #[test]
1182    fn implicit_multiplication_extra() {
1183        let mut parser = Parser::new("4x^2 + 5x + 1");
1184        let expr = parser.try_parse_full::<Expr>().unwrap();
1185
1186        assert_eq!(expr, Expr::Binary(Binary {
1187            lhs: Box::new(Expr::Binary(Binary {
1188                lhs: Box::new(Expr::Binary(Binary {
1189                    lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1190                        value: "4".to_string(),
1191                        span: 0..1,
1192                    }))),
1193                    op: BinOp {
1194                        kind: BinOpKind::Mul,
1195                        implicit: true,
1196                        span: 1..1,
1197                    },
1198                    rhs: Box::new(Expr::Binary(Binary {
1199                        lhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1200                            name: "x".to_string(),
1201                            span: 1..2,
1202                        }))),
1203                        op: BinOp {
1204                            kind: BinOpKind::Exp,
1205                            implicit: false,
1206                            span: 2..3,
1207                        },
1208                        rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1209                            value: "2".to_string(),
1210                            span: 3..4,
1211                        }))),
1212                        span: 1..4,
1213                    })),
1214                    span: 0..4,
1215                })),
1216                op: BinOp {
1217                    kind: BinOpKind::Add,
1218                    implicit: false,
1219                    span: 5..6,
1220                },
1221                rhs: Box::new(Expr::Binary(Binary {
1222                    lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1223                        value: "5".to_string(),
1224                        span: 7..8,
1225                    }))),
1226                    op: BinOp {
1227                        kind: BinOpKind::Mul,
1228                        implicit: true,
1229                        span: 8..8,
1230                    },
1231                    rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1232                        name: "x".to_string(),
1233                        span: 8..9,
1234                    }))),
1235                    span: 7..9,
1236                })),
1237                span: 0..9,
1238            })),
1239            op: BinOp {
1240                kind: BinOpKind::Add,
1241                implicit: false,
1242                span: 10..11,
1243            },
1244            rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1245                value: "1".to_string(),
1246                span: 12..13,
1247            }))),
1248            span: 0..13,
1249        }));
1250    }
1251
1252    #[test]
1253    fn implicit_multiplication_extra_2() {
1254        let mut parser = Parser::new("3^42.9i");
1255        let expr = parser.try_parse_full::<Expr>().unwrap();
1256
1257        assert_eq!(expr, Expr::Binary(Binary {
1258            lhs: Box::new(Expr::Binary(Binary {
1259                lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1260                    value: "3".to_string(),
1261                    span: 0..1,
1262                }))),
1263                op: BinOp {
1264                    kind: BinOpKind::Exp,
1265                    implicit: false,
1266                    span: 1..2,
1267                },
1268                rhs: Box::new(Expr::Literal(Literal::Float(LitFloat {
1269                    value: "42.9".to_string(),
1270                    span: 2..6,
1271                }))),
1272                span: 0..6,
1273            })),
1274            op: BinOp {
1275                kind: BinOpKind::Mul,
1276                implicit: true,
1277                span: 6..6,
1278            },
1279            rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1280                name: "i".to_string(),
1281                span: 6..7,
1282            }))),
1283            span: 0..7,
1284        }));
1285    }
1286
1287    #[test]
1288    fn implicit_multiplication_nonsensical() {
1289        let mut parser = Parser::new("2!! 3!!");
1290        let expr = parser.try_parse_full::<Expr>().unwrap();
1291
1292        assert_eq!(expr, Expr::Binary(Binary {
1293            lhs: Box::new(Expr::Unary(Unary {
1294                operand: Box::new(Expr::Unary(Unary {
1295                    operand: Box::new(Expr::Literal(Literal::Integer(LitInt {
1296                        value: "2".to_string(),
1297                        span: 0..1,
1298                    }))),
1299                    op: UnaryOp {
1300                        kind: UnaryOpKind::Factorial,
1301                        span: 1..2,
1302                    },
1303                    span: 0..2,
1304                })),
1305                op: UnaryOp {
1306                    kind: UnaryOpKind::Factorial,
1307                    span: 2..3,
1308                },
1309                span: 0..3,
1310            })),
1311            op: BinOp {
1312                kind: BinOpKind::Mul,
1313                implicit: true,
1314                span: 3..4,
1315            },
1316            rhs: Box::new(Expr::Unary(Unary {
1317                operand: Box::new(Expr::Unary(Unary {
1318                    operand: Box::new(Expr::Literal(Literal::Integer(LitInt {
1319                        value: "3".to_string(),
1320                        span: 4..5,
1321                    }))),
1322                    op: UnaryOp {
1323                        kind: UnaryOpKind::Factorial,
1324                        span: 5..6,
1325                    },
1326                    span: 4..6,
1327                })),
1328                op: UnaryOp {
1329                    kind: UnaryOpKind::Factorial,
1330                    span: 6..7,
1331                },
1332                span: 4..7,
1333            })),
1334            span: 0..7,
1335        }));
1336    }
1337
1338    #[test]
1339    fn implicit_multiplication_ambiguous() {
1340        let mut parser = Parser::new("1 / 2a");
1341        let expr = parser.try_parse_full::<Expr>().unwrap();
1342
1343        assert_eq!(expr, Expr::Binary(Binary {
1344            lhs: Box::new(Expr::Binary(Binary {
1345                lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1346                    value: "1".to_string(),
1347                    span: 0..1,
1348                }))),
1349                op: BinOp {
1350                    kind: BinOpKind::Div,
1351                    implicit: false,
1352                    span: 2..3,
1353                },
1354                rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1355                    value: "2".to_string(),
1356                    span: 4..5,
1357                }))),
1358                span: 0..5,
1359            })),
1360            op: BinOp {
1361                kind: BinOpKind::Mul,
1362                implicit: true,
1363                span: 5..5,
1364            },
1365            rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1366                name: "a".to_string(),
1367                span: 5..6,
1368            }))),
1369            span: 0..6,
1370        }));
1371    }
1372
1373    #[test]
1374    fn implicit_multiplication_terms_with_power() {
1375        let mut parser = Parser::new("-16x y + 2x^2y");
1376        let expr = parser.try_parse_full::<Expr>().unwrap();
1377
1378        // -16xy
1379        let lhs = Expr::Binary(Binary {
1380            lhs: Box::new(Expr::Binary(Binary {
1381                lhs: Box::new(Expr::Unary(Unary {
1382                    operand: Box::new(Expr::Literal(Literal::Integer(LitInt {
1383                        value: "16".to_string(),
1384                        span: 1..3,
1385                    }))),
1386                    op: UnaryOp {
1387                        kind: UnaryOpKind::Neg,
1388                        span: 0..1,
1389                    },
1390                    span: 0..3,
1391                })),
1392                op: BinOp {
1393                    kind: BinOpKind::Mul,
1394                    implicit: true,
1395                    span: 3..3,
1396                },
1397                rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1398                    name: "x".to_string(),
1399                    span: 3..4,
1400                }))),
1401                span: 0..4,
1402            })),
1403            op: BinOp {
1404                kind: BinOpKind::Mul,
1405                implicit: true,
1406                span: 4..5,
1407            },
1408            rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1409                name: "y".to_string(),
1410                span: 5..6,
1411            }))),
1412            span: 0..6,
1413        });
1414
1415        // 2x^2y
1416        let rhs = Expr::Binary(Binary {
1417            lhs: Box::new(Expr::Binary(Binary {
1418                lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1419                    value: "2".to_string(),
1420                    span: 9..10,
1421                }))),
1422                op: BinOp {
1423                    kind: BinOpKind::Mul,
1424                    implicit: true,
1425                    span: 10..10,
1426                },
1427                rhs: Box::new(Expr::Binary(Binary {
1428                    lhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1429                        name: "x".to_string(),
1430                        span: 10..11,
1431                    }))),
1432                    op: BinOp {
1433                        kind: BinOpKind::Exp,
1434                        implicit: false,
1435                        span: 11..12,
1436                    },
1437                    rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1438                        value: "2".to_string(),
1439                        span: 12..13,
1440                    }))),
1441                    span: 10..13,
1442                })),
1443                span: 9..13,
1444            })),
1445            op: BinOp {
1446                kind: BinOpKind::Mul,
1447                implicit: true,
1448                span: 13..13,
1449            },
1450            rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1451                name: "y".to_string(),
1452                span: 13..14,
1453            }))),
1454            span: 9..14,
1455        });
1456
1457        // -16xy + 2x^2y
1458        let add = Expr::Binary(Binary {
1459            lhs: Box::new(lhs),
1460            op: BinOp {
1461                kind: BinOpKind::Add,
1462                implicit: false,
1463                span: 7..8,
1464            },
1465            rhs: Box::new(rhs),
1466            span: 0..14,
1467        });
1468
1469        assert_eq!(expr, add);
1470    }
1471
1472    #[test]
1473    fn parenthesized() {
1474        let mut parser = Parser::new("(1 + 2) * __");
1475        let expr = parser.try_parse_full::<Expr>().unwrap();
1476
1477        assert_eq!(expr, Expr::Binary(Binary {
1478            lhs: Box::new(Expr::Paren(Paren {
1479                expr: Box::new(Expr::Binary(Binary {
1480                    lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1481                        value: "1".to_string(),
1482                        span: 1..2,
1483                    }))),
1484                    op: BinOp {
1485                        kind: BinOpKind::Add,
1486                        implicit: false,
1487                        span: 3..4,
1488                    },
1489                    rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1490                        value: "2".to_string(),
1491                        span: 5..6,
1492                    }))),
1493                    span: 1..6,
1494                })),
1495                span: 0..7,
1496            })),
1497            op: BinOp {
1498                kind: BinOpKind::Mul,
1499                implicit: false,
1500                span: 8..9,
1501            },
1502            rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1503                name: "__".to_string(),
1504                span: 10..12,
1505            }))),
1506            span: 0..12,
1507        }));
1508    }
1509
1510    #[test]
1511    fn parenthesized_complicated() {
1512        let mut parser = Parser::new("(3 * 9 + 4.0 / 11.9 % (6 - 3))");
1513        let expr = parser.try_parse_full::<Expr>().unwrap();
1514
1515        assert_eq!(expr, Expr::Paren(Paren {
1516            expr: Box::new(Expr::Binary(Binary {
1517                lhs: Box::new(Expr::Binary(Binary {
1518                    lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1519                        value: "3".to_string(),
1520                        span: 1..2,
1521                    }))),
1522                    op: BinOp {
1523                        kind: BinOpKind::Mul,
1524                        implicit: false,
1525                        span: 3..4,
1526                    },
1527                    rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1528                        value: "9".to_string(),
1529                        span: 5..6,
1530                    }))),
1531                    span: 1..6,
1532                })),
1533                op: BinOp {
1534                    kind: BinOpKind::Add,
1535                    implicit: false,
1536                    span: 7..8,
1537                },
1538                rhs: Box::new(Expr::Binary(Binary {
1539                    lhs: Box::new(Expr::Binary(Binary {
1540                        lhs: Box::new(Expr::Literal(Literal::Float(LitFloat {
1541                            value: "4.0".to_string(),
1542                            span: 9..12,
1543                        }))),
1544                        op: BinOp {
1545                            kind: BinOpKind::Div,
1546                            implicit: false,
1547                            span: 13..14,
1548                        },
1549                        rhs: Box::new(Expr::Literal(Literal::Float(LitFloat {
1550                            value: "11.9".to_string(),
1551                            span: 15..19,
1552                        }))),
1553                        span: 9..19,
1554                    })),
1555                    op: BinOp {
1556                        kind: BinOpKind::Mod,
1557                        implicit: false,
1558                        span: 20..21,
1559                    },
1560                    rhs: Box::new(Expr::Paren(Paren {
1561                        expr: Box::new(Expr::Binary(Binary {
1562                            lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1563                                value: "6".to_string(),
1564                                span: 23..24,
1565                            }))),
1566                            op: BinOp {
1567                                kind: BinOpKind::Sub,
1568                                implicit: false,
1569                                span: 25..26,
1570                            },
1571                            rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1572                                value: "3".to_string(),
1573                                span: 27..28,
1574                            }))),
1575                            span: 23..28,
1576                        })),
1577                        span: 22..29,
1578                    })),
1579                    span: 9..29,
1580                })),
1581                span: 1..29,
1582            })),
1583            span: 0..30,
1584        }));
1585    }
1586
1587    #[test]
1588    fn block_code() {
1589        let mut parser = Parser::new("{ x = 5; y = 6; x + y }");
1590        let expr = parser.try_parse_full::<Expr>().unwrap();
1591
1592        assert_eq!(expr, Expr::Block(Block {
1593            stmts: vec![
1594                Stmt {
1595                    expr: Expr::Assign(Assign {
1596                        target: AssignTarget::Symbol(LitSym {
1597                            name: "x".to_string(),
1598                            span: 2..3,
1599                        }),
1600                        op: AssignOp {
1601                            kind: AssignOpKind::Assign,
1602                            span: 4..5,
1603                        },
1604                        value: Box::new(Expr::Literal(Literal::Integer(LitInt {
1605                            value: "5".to_string(),
1606                            span: 6..7,
1607                        }))),
1608                        span: 2..7,
1609                    }),
1610                    semicolon: Some(7..8),
1611                    span: 2..8,
1612                },
1613                Stmt {
1614                    expr: Expr::Assign(Assign {
1615                        target: AssignTarget::Symbol(LitSym {
1616                            name: "y".to_string(),
1617                            span: 9..10,
1618                        }),
1619                        op: AssignOp {
1620                            kind: AssignOpKind::Assign,
1621                            span: 11..12,
1622                        },
1623                        value: Box::new(Expr::Literal(Literal::Integer(LitInt {
1624                            value: "6".to_string(),
1625                            span: 13..14,
1626                        }))),
1627                        span: 9..14,
1628                    }),
1629                    semicolon: Some(14..15),
1630                    span: 9..15,
1631                },
1632                Stmt {
1633                    expr: Expr::Binary(Binary {
1634                        lhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1635                            name: "x".to_string(),
1636                            span: 16..17,
1637                        }))),
1638                        op: BinOp {
1639                            kind: BinOpKind::Add,
1640                            implicit: false,
1641                            span: 18..19,
1642                        },
1643                        rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1644                            name: "y".to_string(),
1645                            span: 20..21,
1646                        }))),
1647                        span: 16..21,
1648                    }),
1649                    semicolon: None,
1650                    span: 16..21,
1651                },
1652            ],
1653            span: 0..23,
1654        }));
1655    }
1656
1657    #[test]
1658    fn if_block() {
1659        let mut parser = Parser::new("if d then { abs''(d) } else { f = 1; f }");
1660        let expr = parser.try_parse_full::<Expr>().unwrap();
1661
1662        assert_eq!(expr, Expr::If(If {
1663            condition: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1664                name: "d".to_string(),
1665                span: 3..4,
1666            }))),
1667            then_expr: Box::new(Expr::Block(Block {
1668                stmts: vec![
1669                    Stmt {
1670                        expr: Expr::Call(Call {
1671                            name: LitSym {
1672                                name: "abs".to_string(),
1673                                span: 12..15,
1674                            },
1675                            derivatives: 2,
1676                            args: vec![
1677                                Expr::Literal(Literal::Symbol(LitSym {
1678                                    name: "d".to_string(),
1679                                    span: 18..19,
1680                                })),
1681                            ],
1682                            span: 12..20,
1683                            paren_span: 17..20,
1684                        }),
1685                        semicolon: None,
1686                        span: 12..20,
1687                    },
1688                ],
1689                span: 10..22,
1690            })),
1691            else_expr: Some(Box::new(Expr::Block(Block {
1692                stmts: vec![
1693                    Stmt {
1694                        expr: Expr::Assign(Assign {
1695                            target: AssignTarget::Symbol(LitSym {
1696                                name: "f".to_string(),
1697                                span: 30..31,
1698                            }),
1699                            op: AssignOp {
1700                                kind: AssignOpKind::Assign,
1701                                span: 32..33,
1702                            },
1703                            value: Box::new(Expr::Literal(Literal::Integer(LitInt {
1704                                value: "1".to_string(),
1705                                span: 34..35,
1706                            }))),
1707                            span: 30..35,
1708                        }),
1709                        semicolon: Some(35..36),
1710                        span: 30..36,
1711                    },
1712                    Stmt {
1713                        expr: Expr::Literal(Literal::Symbol(LitSym {
1714                            name: "f".to_string(),
1715                            span: 37..38,
1716                        })),
1717                        semicolon: None,
1718                        span: 37..38,
1719                    },
1720                ],
1721                span: 28..40,
1722            }))),
1723            span: 0..40,
1724            if_span: 0..2,
1725            then_span: 5..9,
1726            else_span: Some(23..27),
1727        }));
1728    }
1729
1730    #[test]
1731    fn assign_to_var() {
1732        let mut parser = Parser::new("fx += 1 / pi");
1733        let expr = parser.try_parse_full::<Expr>().unwrap();
1734
1735        assert_eq!(expr, Expr::Assign(Assign {
1736            target: AssignTarget::Symbol(LitSym {
1737                name: "fx".to_string(),
1738                span: 0..2,
1739            }),
1740            op: AssignOp {
1741                kind: AssignOpKind::Add,
1742                span: 3..5,
1743            },
1744            value: Box::new(Expr::Binary(Binary {
1745                lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1746                    value: "1".to_string(),
1747                    span: 6..7,
1748                }))),
1749                op: BinOp {
1750                    kind: BinOpKind::Div,
1751                    implicit: false,
1752                    span: 8..9,
1753                },
1754                rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1755                    name: "pi".to_string(),
1756                    span: 10..12,
1757                }))),
1758                span: 6..12,
1759            })),
1760            span: 0..12,
1761        }));
1762    }
1763
1764    #[test]
1765    fn assign_to_function() {
1766        let mut parser = Parser::new("f(x) = x^2 + 5x");
1767        let expr = parser.try_parse_full::<Expr>().unwrap();
1768
1769        assert_eq!(expr, Expr::Assign(Assign {
1770            target: AssignTarget::Func(FuncHeader {
1771                name: LitSym {
1772                    name: "f".to_string(),
1773                    span: 0..1,
1774                },
1775                params: vec![
1776                    Param::Symbol(LitSym {
1777                        name: "x".to_string(),
1778                        span: 2..3,
1779                    }),
1780                ],
1781                span: 0..4,
1782            }),
1783            op: AssignOp {
1784                kind: AssignOpKind::Assign,
1785                span: 5..6,
1786            },
1787            value: Box::new(Expr::Binary(Binary {
1788                lhs: Box::new(Expr::Binary(Binary {
1789                    lhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1790                        name: "x".to_string(),
1791                        span: 7..8,
1792                    }))),
1793                    op: BinOp {
1794                        kind: BinOpKind::Exp,
1795                        implicit: false,
1796                        span: 8..9,
1797                    },
1798                    rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1799                        value: "2".to_string(),
1800                        span: 9..10,
1801                    }))),
1802                    span: 7..10,
1803                })),
1804                op: BinOp {
1805                    kind: BinOpKind::Add,
1806                    implicit: false,
1807                    span: 11..12,
1808                },
1809                rhs: Box::new(Expr::Binary(Binary {
1810                    lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1811                        value: "5".to_string(),
1812                        span: 13..14,
1813                    }))),
1814                    op: BinOp {
1815                        kind: BinOpKind::Mul,
1816                        implicit: true,
1817                        span: 14..14,
1818                    },
1819                    rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1820                        name: "x".to_string(),
1821                        span: 14..15,
1822                    }))),
1823                    span: 13..15,
1824                })),
1825                span: 7..15,
1826            })),
1827            span: 0..15,
1828        }));
1829    }
1830
1831    #[test]
1832    fn assign_to_complicated_function() {
1833        let mut parser = Parser::new("discrim(a = 1, b = 5, c) = b^2 - 4a * c");
1834        let expr = parser.try_parse_full::<Expr>().unwrap();
1835
1836        assert_eq!(expr, Expr::Assign(Assign {
1837            target: AssignTarget::Func(FuncHeader {
1838                name: LitSym {
1839                    name: "discrim".to_string(),
1840                    span: 0..7,
1841                },
1842                params: vec![
1843                    Param::Default(
1844                        LitSym {
1845                            name: "a".to_string(),
1846                            span: 8..9,
1847                        },
1848                        Expr::Literal(Literal::Integer(LitInt {
1849                            value: "1".to_string(),
1850                            span: 12..13,
1851                        })),
1852                    ),
1853                    Param::Default(
1854                        LitSym {
1855                            name: "b".to_string(),
1856                            span: 15..16,
1857                        },
1858                        Expr::Literal(Literal::Integer(LitInt {
1859                            value: "5".to_string(),
1860                            span: 19..20,
1861                        })),
1862                    ),
1863                    Param::Symbol(
1864                        LitSym {
1865                            name: "c".to_string(),
1866                            span: 22..23,
1867                        },
1868                    ),
1869                ],
1870                span: 0..24,
1871            }),
1872            op: AssignOp {
1873                kind: AssignOpKind::Assign,
1874                span: 25..26,
1875            },
1876            value: Box::new(Expr::Binary(Binary {
1877                lhs: Box::new(Expr::Binary(Binary {
1878                    lhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1879                        name: "b".to_string(),
1880                        span: 27..28,
1881                    }))),
1882                    op: BinOp {
1883                        kind: BinOpKind::Exp,
1884                        implicit: false,
1885                        span: 28..29,
1886                    },
1887                    rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1888                        value: "2".to_string(),
1889                        span: 29..30,
1890                    }))),
1891                    span: 27..30,
1892                })),
1893                op: BinOp {
1894                    kind: BinOpKind::Sub,
1895                    implicit: false,
1896                    span: 31..32,
1897                },
1898                rhs: Box::new(Expr::Binary(Binary {
1899                    lhs: Box::new(Expr::Binary(Binary {
1900                        lhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
1901                            value: "4".to_string(),
1902                            span: 33..34,
1903                        }))),
1904                        op: BinOp {
1905                            kind: BinOpKind::Mul,
1906                            implicit: true,
1907                            span: 34..34,
1908                        },
1909                        rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1910                            name: "a".to_string(),
1911                            span: 34..35,
1912                        }))),
1913                        span: 33..35,
1914                    })),
1915                    op: BinOp {
1916                        kind: BinOpKind::Mul,
1917                        implicit: false,
1918                        span: 36..37,
1919                    },
1920                    rhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
1921                        name: "c".to_string(),
1922                        span: 38..39,
1923                    }))),
1924                    span: 33..39,
1925                })),
1926                span: 27..39,
1927            })),
1928            span: 0..39,
1929        }));
1930    }
1931
1932    #[test]
1933    fn function_call() {
1934        let mut parser = Parser::new("f(x)");
1935        let expr = parser.try_parse_full::<Expr>().unwrap();
1936
1937        assert_eq!(expr, Expr::Call(Call {
1938            name: LitSym {
1939                name: "f".to_string(),
1940                span: 0..1,
1941            },
1942            derivatives: 0,
1943            args: vec![
1944                Expr::Literal(Literal::Symbol(LitSym {
1945                    name: "x".to_string(),
1946                    span: 2..3,
1947                })),
1948            ],
1949            span: 0..4,
1950            paren_span: 1..4,
1951        }));
1952    }
1953
1954    #[test]
1955    fn function_call_whitespace() {
1956        let mut parser = Parser::new("ncr  ' ' ' '' ' ( 8 , 5 )");
1957        let expr = parser.try_parse_full::<Expr>().unwrap();
1958
1959        assert_eq!(expr, Expr::Call(Call {
1960            name: LitSym {
1961                name: "ncr".to_string(),
1962                span: 0..3,
1963            },
1964            derivatives: 6,
1965            args: vec![
1966                Expr::Literal(Literal::Integer(LitInt {
1967                    value: "8".to_string(),
1968                    span: 18..19,
1969                })),
1970                Expr::Literal(Literal::Integer(LitInt {
1971                    value: "5".to_string(),
1972                    span: 22..23,
1973                })),
1974            ],
1975            span: 0..25,
1976            paren_span: 16..25,
1977        }));
1978    }
1979
1980    #[test]
1981    fn blank_function_header() {
1982        let mut parser = Parser::new("f() = 5");
1983        let expr = parser.try_parse_full::<Expr>().unwrap();
1984
1985        assert_eq!(expr, Expr::Assign(Assign {
1986            target: AssignTarget::Func(FuncHeader {
1987                name: LitSym {
1988                    name: "f".to_string(),
1989                    span: 0..1,
1990                },
1991                params: vec![],
1992                span: 0..3,
1993            }),
1994            op: AssignOp {
1995                kind: AssignOpKind::Assign,
1996                span: 4..5,
1997            },
1998            value: Box::new(Expr::Literal(Literal::Integer(LitInt {
1999                value: "5".to_string(),
2000                span: 6..7,
2001            }))),
2002            span: 0..7,
2003        }));
2004    }
2005
2006    #[test]
2007    fn catastrophic_backtracking() {
2008        // parsing nested function calls like this used to take exponential time! :sweat:
2009        let mut parser = Parser::new("a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a(a()");
2010        assert!(parser.try_parse_full::<Expr>().is_err());
2011    }
2012
2013    #[test]
2014    fn oneline_while_loop() {
2015        let mut parser = Parser::new("while x < 5 then x += 1");
2016        let expr = parser.try_parse_full::<Expr>().unwrap();
2017
2018        assert_eq!(expr, Expr::While(While {
2019            condition: Box::new(Expr::Binary(Binary {
2020                lhs: Box::new(Expr::Literal(Literal::Symbol(LitSym {
2021                    name: "x".to_string(),
2022                    span: 6..7,
2023                }))),
2024                op: BinOp {
2025                    kind: BinOpKind::Less,
2026                    implicit: false,
2027                    span: 8..9,
2028                },
2029                rhs: Box::new(Expr::Literal(Literal::Integer(LitInt {
2030                    value: "5".to_string(),
2031                    span: 10..11,
2032                }))),
2033                span: 6..11,
2034            })),
2035            body: Box::new(Expr::Assign(Assign {
2036                target: AssignTarget::Symbol(LitSym {
2037                    name: "x".to_string(),
2038                    span: 17..18,
2039                }),
2040                op: AssignOp {
2041                    kind: AssignOpKind::Add,
2042                    span: 19..21,
2043                },
2044                value: Box::new(Expr::Literal(Literal::Integer(LitInt {
2045                    value: "1".to_string(),
2046                    span: 22..23,
2047                }))),
2048                span: 17..23,
2049            })),
2050            span: 0..23,
2051            while_span: 0..5,
2052            then_span: 12..16,
2053        }));
2054    }
2055
2056    #[test]
2057    fn source_code() {
2058        let mut parser = Parser::new("x = 5;
2059iseven(n) = n % 2 == 0;
2060if iseven(x) then {
2061    x^2 + 5x + 6
2062} else if (bool(x) && false) then {
2063    exp(x)
2064} else {
2065    log(x, 2)
2066}");
2067        assert!(parser.try_parse_full_many::<Stmt>().is_ok());
2068    }
2069}
cas_parser/parser/mod.rs

cas_parser/parser/
mod.rs
