expr_parser/
parser.rs

1use crate::{
2    error::{ParseError, ParseErrorKind, ParseErrors, ParseErrorsFor},
3    expression::{Expression, ExpressionKind},
4    operator::Fixity,
5    token::{Token, Tokenizer},
6    Span,
7};
8
9const EXPECT_TERM: &str = "literal, variable, unary operator, or delimiter";
10const EXPECT_OPERATOR: &str = "binary operator, delimiter, postfix operator, or end of input";
11
12pub fn parse<T, P>(
13    mut tokenizer: T,
14    parser: P,
15) -> Result<ExpressionQueueFor<P, T>, ParseErrorsFor<P, T>>
16where
17    P: Parser<T::Token>,
18    T: Tokenizer,
19{
20    let mut state = ParseState::new(parser);
21    while let Some(token) = tokenizer.next_token() {
22        state.parse_result(token);
23    }
24    state.finish()
25}
26
27/// Parses until a single term has been completed.
28///
29/// This means zero or more prefix operators followed by either a term token or a delimited
30/// group.
31pub fn parse_one_term<T, P>(
32    mut tokenizer: T,
33    parser: P,
34) -> Result<ExpressionQueueFor<P, T>, ParseErrorsFor<P, T>>
35where
36    P: Parser<T::Token>,
37    T: Tokenizer,
38{
39    let mut state = ParseState::new(parser);
40    while let Some(token) = tokenizer.next_token() {
41        state.parse_result(token);
42        if state.has_parsed_expression() {
43            break;
44        }
45    }
46    state.finish()
47}
48
49pub type ExpressionQueueFor<P, T> = Vec<
50    Expression<
51        <T as Tokenizer>::Position,
52        <P as Parser<<T as Tokenizer>::Token>>::BinaryOperator,
53        <P as Parser<<T as Tokenizer>::Token>>::UnaryOperator,
54        <P as Parser<<T as Tokenizer>::Token>>::Term,
55    >,
56>;
57
58pub type ExpressionQueue<T, Idx, P> = Vec<
59    Expression<
60        Idx,
61        <P as Parser<T>>::BinaryOperator,
62        <P as Parser<T>>::UnaryOperator,
63        <P as Parser<T>>::Term,
64    >,
65>;
66
67pub struct ParseState<T, TokErr, Idx, P: Parser<T>> {
68    parser: P,
69    end_of_input: Idx,
70    state: State,
71    stack: Stack<T, Idx, P>,
72    queue: ExpressionQueue<T, Idx, P>,
73    errors: Vec<ParseError<P::Error, TokErr, Idx>>,
74}
75
76impl<T, TokErr, Idx: Default + Clone, P: Parser<T>> ParseState<T, TokErr, Idx, P> {
77    pub fn new(parser: P) -> Self {
78        Self {
79            parser,
80            end_of_input: Default::default(),
81            state: State::PostOperator,
82            stack: Stack::new(),
83            queue: Vec::new(),
84            errors: Vec::new(),
85        }
86    }
87
88    pub fn parse_result(&mut self, result: Result<Token<T, Idx>, TokErr>) {
89        match result {
90            Err(e) => self.errors.push(ParseError {
91                span: Span {
92                    start: self.end_of_input.clone(),
93                    end: self.end_of_input.clone(),
94                },
95                kind: ParseErrorKind::Tokenizer(e),
96            }),
97            Ok(token) => {
98                self.parse_token(token);
99            }
100        }
101    }
102
103    pub fn parse_token(&mut self, token: Token<T, Idx>) {
104        self.end_of_input = token.span.end.clone();
105        match self.parser.parse_token(token.kind) {
106            Ok(element) => match self.state {
107                State::PostOperator => {
108                    if self.parse_term(token.span.clone(), element.prefix) {
109                        self.parse_operator(token.span, element.postfix);
110                    }
111                }
112                State::PostTerm => {
113                    if self.parse_operator(token.span.clone(), element.postfix) {
114                        self.parse_term(token.span, element.prefix);
115                    }
116                }
117            },
118            Err(error) => {
119                self.errors.push(ParseError {
120                    span: token.span,
121                    kind: ParseErrorKind::Parser(error),
122                });
123                // assume that the invalid token was the more expected kind, ideally producing the
124                // most useful errors.
125                match self.state {
126                    State::PostOperator => self.state = State::PostTerm,
127                    State::PostTerm => self.state = State::PostOperator,
128                }
129            }
130        }
131    }
132
133    /// Returns whether the parser has parsed a complete expression.
134    pub fn has_parsed_expression(&mut self) -> bool {
135        // no delimiters on the stack
136        !self.stack.has_delimiter()
137            && (
138                // in post-term state or the top of the stack can go without a right-hand-side
139                self.state == State::PostTerm
140                    || self
141                        .stack
142                        .peek_top()
143                        .is_some_and(|top| top.operator.can_have_no_rhs())
144            )
145    }
146
147    /// Returns whether the parser has encountered at least one error
148    pub fn has_error(&mut self) -> bool {
149        !self.errors.is_empty()
150    }
151
152    #[allow(clippy::type_complexity)]
153    pub fn finish(
154        mut self,
155    ) -> Result<ExpressionQueue<T, Idx, P>, ParseErrors<P::Error, TokErr, Idx>> {
156        if self.state != State::PostTerm {
157            if let Some(el) = self.stack.pop() {
158                if let Some(kind) = el.operator.expression_kind_no_rhs() {
159                    self.queue.push(Expression {
160                        kind,
161                        span: el.span.clone(),
162                    });
163                } else {
164                    self.errors.push(ParseError {
165                        kind: ParseErrorKind::EndOfInput {
166                            expected: EXPECT_TERM,
167                        },
168                        span: Span {
169                            start: self.end_of_input.clone(),
170                            end: self.end_of_input,
171                        },
172                    })
173                }
174                if el.order.is_delimiter() {
175                    self.errors.push(ParseError {
176                        kind: ParseErrorKind::UnmatchedLeftDelimiter,
177                        span: el.span,
178                    })
179                }
180            }
181        }
182        while let Some(el) = self.stack.pop() {
183            if let Some(kind) = el.operator.expression_kind_rhs() {
184                self.queue.push(Expression {
185                    kind,
186                    span: el.span.clone(),
187                });
188            }
189            if el.order.is_delimiter() {
190                self.errors.push(ParseError {
191                    kind: ParseErrorKind::UnmatchedLeftDelimiter,
192                    span: el.span,
193                })
194            }
195        }
196        if self.errors.is_empty() {
197            Ok(self.queue)
198        } else {
199            Err(self.errors.into())
200        }
201    }
202
203    fn parse_term(&mut self, span: Span<Idx>, prefix: ParserPrefix<P, T>) -> bool {
204        match prefix {
205            Prefix::LeftDelimiter {
206                delimiter,
207                operator,
208                empty,
209            } => {
210                self.stack.push(StackElement {
211                    span,
212                    order: StackOrder::Delimiter(delimiter),
213                    operator: StackOperator::unary_delimiter(operator, empty),
214                });
215                self.state = State::PostOperator;
216                false
217            }
218            Prefix::RightDelimiter { delimiter } => {
219                self.process_right_delimiter(span, delimiter);
220                false
221            }
222            Prefix::UnaryOperator {
223                precedence,
224                operator,
225                no_rhs,
226            } => {
227                self.stack.push(StackElement {
228                    span,
229                    order: StackOrder::Precedence(precedence),
230                    operator: StackOperator::Unary {
231                        unary: operator,
232                        term: no_rhs,
233                    },
234                });
235                self.state = State::PostOperator;
236                false
237            }
238            Prefix::Term { term } => {
239                self.state = State::PostTerm;
240                self.queue.push(Expression {
241                    span,
242                    kind: ExpressionKind::Term(term),
243                });
244                false
245            }
246            Prefix::None => {
247                self.state = State::PostTerm;
248                if let Some(el) = self.stack.pop() {
249                    if let Some(kind) = el.operator.expression_kind_no_rhs() {
250                        self.queue.push(Expression {
251                            kind,
252                            span: el.span,
253                        });
254                    } else {
255                        self.errors.push(ParseError {
256                            kind: ParseErrorKind::UnexpectedToken {
257                                expected: EXPECT_TERM,
258                            },
259                            span: span.clone(),
260                        });
261                    };
262                }
263                true
264            }
265        }
266    }
267
268    fn parse_operator(&mut self, span: Span<Idx>, postfix: ParserPostfix<P, T>) -> bool {
269        match postfix {
270            Postfix::RightDelimiter { delimiter } => {
271                self.process_right_delimiter(span, delimiter);
272                false
273            }
274            Postfix::BinaryOperator {
275                fixity,
276                operator,
277                no_rhs,
278            } => {
279                self.state = State::PostOperator;
280                self.process_binary_operator(span, fixity, operator, no_rhs);
281                false
282            }
283            Postfix::ImplicitOperator { fixity, operator } => {
284                self.process_binary_operator(span.clone(), fixity, operator, None);
285                true
286            }
287            Postfix::PostfixOperator {
288                precedence,
289                operator,
290            } => {
291                self.process_postfix_operator(span, precedence, operator);
292                false
293            }
294            Postfix::LeftDelimiter {
295                delimiter,
296                operator,
297                empty,
298            } => {
299                self.state = State::PostOperator;
300                // left delimiter in operator position indicates a function call or similar.
301                // this is indicated by adding a binary operator (with the same token as the
302                // delimiter) to the stack immediately after the delimiter itself. this
303                // operator will then function as the "function application" operator (or a
304                // related operator, such as "struct construction") when it is popped from the
305                // stack after the closing delimiter is matched
306                self.stack.push(StackElement {
307                    span,
308                    order: StackOrder::Delimiter(delimiter),
309                    operator: StackOperator::Binary {
310                        binary: operator,
311                        unary: empty,
312                    },
313                });
314                false
315            }
316            Postfix::None => {
317                self.state = State::PostOperator;
318                self.errors.push(ParseError {
319                    kind: ParseErrorKind::UnexpectedToken {
320                        expected: EXPECT_OPERATOR,
321                    },
322                    span,
323                });
324                true
325            }
326        }
327    }
328
329    fn process_right_delimiter(&mut self, span: Span<Idx>, right: P::Delimiter) {
330        // If we don't have a right-hand operand, demote the operator on the top of the stack
331        // (binary -> unary, unary -> term) if possible. If it is not possible (i.e. that operator
332        // requires a right-hand operand), then push an error. We don't early return though, since
333        // we still want to find the matching delimiter so that we can continue parsing.
334        if self.state != State::PostTerm {
335            if let Some(el) = self.stack.pop() {
336                if let Some(kind) = el.operator.expression_kind_no_rhs() {
337                    self.queue.push(Expression {
338                        kind,
339                        span: el.span.clone(),
340                    });
341                } else {
342                    self.errors.push(ParseError {
343                        kind: ParseErrorKind::UnexpectedToken {
344                            expected: EXPECT_TERM,
345                        },
346                        span: span.clone(),
347                    });
348                };
349                if let StackOrder::Delimiter(left) = el.order {
350                    self.state = State::PostTerm;
351                    self.check_delimiter_match(left, el.span, right, span);
352                    return;
353                }
354            }
355        };
356        self.state = State::PostTerm;
357        while let Some(el) = self.stack.pop() {
358            if let Some(kind) = el.operator.expression_kind_rhs() {
359                self.queue.push(Expression {
360                    kind,
361                    span: el.span.clone(),
362                });
363            }
364            if let StackOrder::Delimiter(left) = el.order {
365                self.check_delimiter_match(left, el.span, right, span);
366                return;
367            }
368        }
369        self.errors.push(ParseError {
370            kind: ParseErrorKind::UnmatchedRightDelimiter,
371            span,
372        })
373    }
374
375    fn check_delimiter_match(
376        &mut self,
377        left: P::Delimiter,
378        left_span: Span<Idx>,
379        right: P::Delimiter,
380        right_span: Span<Idx>,
381    ) {
382        if !left.matches(&right) {
383            self.errors.push(ParseError {
384                kind: ParseErrorKind::MismatchedDelimiter { opening: left_span },
385                span: right_span,
386            });
387        }
388    }
389
390    fn process_binary_operator(
391        &mut self,
392        span: Span<Idx>,
393        fixity: Fixity<P::Precedence>,
394        binary: P::BinaryOperator,
395        unary: Option<P::UnaryOperator>,
396    ) {
397        self.pop_while_lower_precedence(&fixity);
398        self.stack.push(StackElement {
399            span,
400            order: StackOrder::Precedence(fixity.into_precedence()),
401            operator: StackOperator::Binary { binary, unary },
402        });
403    }
404
405    fn process_postfix_operator(
406        &mut self,
407        span: Span<Idx>,
408        precedence: P::Precedence,
409        operator: P::UnaryOperator,
410    ) {
411        self.state = State::PostTerm;
412        let fixity = Fixity::Right(precedence);
413        self.pop_while_lower_precedence(&fixity);
414        self.queue.push(Expression {
415            span,
416            kind: ExpressionKind::UnaryOperator(operator),
417        });
418    }
419
420    fn pop_while_lower_precedence(&mut self, fixity: &Fixity<P::Precedence>) {
421        while let Some(el) = self.stack.pop_if_lower_precedence(fixity) {
422            if let Some(kind) = el.operator.expression_kind_rhs() {
423                self.queue.push(Expression {
424                    kind,
425                    span: el.span,
426                });
427            }
428        }
429    }
430}
431
432impl<T, TokErr, Idx: Default + Clone, P: Parser<T>> Extend<Token<T, Idx>>
433    for ParseState<T, TokErr, Idx, P>
434{
435    fn extend<I>(&mut self, iter: I)
436    where
437        I: IntoIterator<Item = Token<T, Idx>>,
438    {
439        iter.into_iter().for_each(|tok| self.parse_token(tok))
440    }
441}
442
443impl<T, TokErr, Idx: Default + Clone, P: Parser<T>> Extend<Result<Token<T, Idx>, TokErr>>
444    for ParseState<T, TokErr, Idx, P>
445{
446    fn extend<I>(&mut self, iter: I)
447    where
448        I: IntoIterator<Item = Result<Token<T, Idx>, TokErr>>,
449    {
450        iter.into_iter().for_each(|res| self.parse_result(res))
451    }
452}
453
454pub trait Parser<T> {
455    type Precedence: Ord;
456    type Delimiter: Delimiter;
457    type BinaryOperator;
458    type UnaryOperator;
459    type Term;
460    type Error;
461
462    fn parse_token(&self, kind: T) -> Result<ParserElement<Self, T>, Self::Error>;
463}
464
465impl<P, T> Parser<T> for &'_ P
466where
467    P: Parser<T> + ?Sized,
468{
469    type Precedence = P::Precedence;
470    type Delimiter = P::Delimiter;
471    type BinaryOperator = P::BinaryOperator;
472    type UnaryOperator = P::UnaryOperator;
473    type Term = P::Term;
474    type Error = P::Error;
475
476    fn parse_token(&self, kind: T) -> Result<ParserElement<Self, T>, Self::Error> {
477        P::parse_token(self, kind)
478    }
479}
480
481pub trait Delimiter {
482    fn matches(&self, other: &Self) -> bool;
483}
484
485pub struct Element<P, D, B, U, T> {
486    pub prefix: Prefix<P, D, U, T>,
487    pub postfix: Postfix<P, D, B, U>,
488}
489
490pub type ParserElement<P, T> = Element<
491    <P as Parser<T>>::Precedence,
492    <P as Parser<T>>::Delimiter,
493    <P as Parser<T>>::BinaryOperator,
494    <P as Parser<T>>::UnaryOperator,
495    <P as Parser<T>>::Term,
496>;
497
498pub enum Prefix<P, D, U, T> {
499    UnaryOperator {
500        precedence: P,
501        operator: U,
502        no_rhs: Option<T>,
503    },
504    LeftDelimiter {
505        delimiter: D,
506        operator: Option<U>,
507        empty: Option<T>,
508    },
509    RightDelimiter {
510        delimiter: D,
511    },
512    Term {
513        term: T,
514    },
515    None,
516}
517
518type ParserPrefix<P, T> = Prefix<
519    <P as Parser<T>>::Precedence,
520    <P as Parser<T>>::Delimiter,
521    <P as Parser<T>>::UnaryOperator,
522    <P as Parser<T>>::Term,
523>;
524
525pub enum Postfix<P, D, B, U> {
526    BinaryOperator {
527        fixity: Fixity<P>,
528        operator: B,
529        no_rhs: Option<U>,
530    },
531    PostfixOperator {
532        precedence: P,
533        operator: U,
534    },
535    LeftDelimiter {
536        delimiter: D,
537        operator: B,
538        empty: Option<U>,
539    },
540    RightDelimiter {
541        delimiter: D,
542    },
543    ImplicitOperator {
544        fixity: Fixity<P>,
545        operator: B,
546    },
547    None,
548}
549
550type ParserPostfix<P, T> = Postfix<
551    <P as Parser<T>>::Precedence,
552    <P as Parser<T>>::Delimiter,
553    <P as Parser<T>>::BinaryOperator,
554    <P as Parser<T>>::UnaryOperator,
555>;
556
557pub enum StackOrder<P, D> {
558    Precedence(P),
559    Delimiter(D),
560}
561
562impl<P, D> StackOrder<P, D> {
563    fn precedence(&self) -> Option<&P> {
564        match self {
565            Self::Precedence(p) => Some(p),
566            Self::Delimiter(_) => None,
567        }
568    }
569
570    fn is_delimiter(&self) -> bool {
571        matches!(self, Self::Delimiter(_))
572    }
573}
574
575#[derive(Clone, Copy, Debug, Eq, PartialEq)]
576enum State {
577    PostOperator,
578    PostTerm,
579}
580
581struct Stack<T, Idx, P: Parser<T>> {
582    stack: Vec<StackElement<T, Idx, P>>,
583    first_delimiter_idx: Option<usize>,
584}
585
586impl<T, Idx, P: Parser<T>> Default for Stack<T, Idx, P> {
587    fn default() -> Self {
588        Stack {
589            stack: Default::default(),
590            first_delimiter_idx: None,
591        }
592    }
593}
594
595impl<T, Idx, P: Parser<T>> Stack<T, Idx, P> {
596    fn new() -> Self {
597        Default::default()
598    }
599
600    fn push(&mut self, element: StackElement<T, Idx, P>) {
601        if element.order.is_delimiter() && self.first_delimiter_idx.is_none() {
602            self.first_delimiter_idx = Some(self.stack.len());
603        }
604        self.stack.push(element);
605    }
606
607    fn pop(&mut self) -> Option<StackElement<T, Idx, P>> {
608        let el = self.stack.pop();
609        if Some(self.stack.len()) == self.first_delimiter_idx {
610            self.first_delimiter_idx = None
611        }
612        el
613    }
614
615    fn peek_top(&self) -> Option<&StackElement<T, Idx, P>> {
616        self.stack.last()
617    }
618
619    fn has_delimiter(&self) -> bool {
620        self.first_delimiter_idx.is_some()
621    }
622
623    /// Pops the stack if the new operator has lower precedence than the top of the stack
624    fn pop_if_lower_precedence(
625        &mut self,
626        fixity: &Fixity<P::Precedence>,
627    ) -> Option<StackElement<T, Idx, P>> {
628        if match fixity {
629            Fixity::Left(prec) => Some(prec) <= self.precedence(),
630            Fixity::Right(prec) => Some(prec) < self.precedence(),
631        } {
632            self.pop()
633        } else {
634            None
635        }
636    }
637
638    fn precedence(&self) -> Option<&P::Precedence> {
639        self.peek_top().and_then(StackElement::precedence)
640    }
641}
642
643struct StackElement<T, Idx, P: Parser<T>> {
644    span: Span<Idx>,
645    order: StackOrder<P::Precedence, P::Delimiter>,
646    operator: StackOperator<P::BinaryOperator, P::UnaryOperator, P::Term>,
647}
648
649impl<T, Idx, P: Parser<T>> StackElement<T, Idx, P> {
650    fn precedence(&self) -> Option<&P::Precedence> {
651        self.order.precedence()
652    }
653}
654
655#[derive(Clone, Copy, Debug)]
656enum StackOperator<B, U, T> {
657    None { term: Option<T> },
658    Binary { binary: B, unary: Option<U> },
659    Unary { unary: U, term: Option<T> },
660}
661
662impl<B, U, T> StackOperator<B, U, T> {
663    fn unary_delimiter(unary: Option<U>, term: Option<T>) -> Self {
664        match unary {
665            None => Self::None { term },
666            Some(unary) => Self::Unary { unary, term },
667        }
668    }
669
670    fn expression_kind_rhs(self) -> Option<ExpressionKind<B, U, T>> {
671        match self {
672            Self::None { .. } => None,
673            Self::Binary { binary, .. } => Some(ExpressionKind::BinaryOperator(binary)),
674            Self::Unary { unary, .. } => Some(ExpressionKind::UnaryOperator(unary)),
675        }
676    }
677
678    fn expression_kind_no_rhs(self) -> Option<ExpressionKind<B, U, T>> {
679        match self {
680            Self::None { term } | Self::Unary { term, .. } => term.map(ExpressionKind::Term),
681            Self::Binary { unary, .. } => unary.map(ExpressionKind::UnaryOperator),
682        }
683    }
684    fn can_have_no_rhs(&self) -> bool {
685        match self {
686            Self::None { term } | Self::Unary { term, .. } => term.is_some(),
687            Self::Binary { unary, .. } => unary.is_some(),
688        }
689    }
690}
691
692#[cfg(test)]
693mod tests {
694    #![allow(clippy::type_complexity)]
695
696    use std::{convert::Infallible, ops::Range};
697
698    use test_case::test_case;
699
700    use super::{
701        parse, parse_one_term, Delimiter, Element, ParseState, Parser, Postfix, Prefix,
702        EXPECT_OPERATOR, EXPECT_TERM,
703    };
704    use crate::{
705        error::ParseErrorKind,
706        expression::{Expression, ExpressionKind},
707        operator::Fixity,
708        token::{
709            charset::{SimpleCharSetTokenKind, SimpleTokenizer, StrSource},
710            Tokenizer,
711        },
712    };
713
714    struct SimpleExprContext;
715
716    #[derive(Clone, Copy, Eq, PartialEq)]
717    enum SimpleDelimiter {
718        Paren,
719        SquareBracket,
720        Pipe,
721    }
722
723    #[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
724    enum SimplePrecedence {
725        /// Comma
726        Comma,
727        /// Additive operators, such as `+` and `-`
728        Additive,
729        /// Multiplicative operators, such as `*` and `/`, as well as unary minus.
730        Multiplicative,
731        /// Exponential operators, such as `^` and `!`
732        Exponential,
733    }
734
735    impl Delimiter for SimpleDelimiter {
736        fn matches(&self, other: &Self) -> bool {
737            self == other
738        }
739    }
740
741    impl<'s> Parser<(&'s str, SimpleCharSetTokenKind)> for SimpleExprContext {
742        type Error = Infallible;
743        type Precedence = SimplePrecedence;
744        type Delimiter = SimpleDelimiter;
745        type BinaryOperator = &'s str;
746        type UnaryOperator = &'s str;
747        type Term = &'s str;
748
749        fn parse_token(
750            &self,
751            (s, kind): (&'s str, SimpleCharSetTokenKind),
752        ) -> Result<
753            Element<
754                Self::Precedence,
755                Self::Delimiter,
756                Self::BinaryOperator,
757                Self::UnaryOperator,
758                Self::Term,
759            >,
760            Self::Error,
761        > {
762            Ok(match s {
763                "(" => Element {
764                    prefix: Prefix::LeftDelimiter {
765                        delimiter: SimpleDelimiter::Paren,
766                        operator: None,
767                        empty: None,
768                    },
769                    postfix: Postfix::LeftDelimiter {
770                        delimiter: SimpleDelimiter::Paren,
771                        operator: s,
772                        empty: Some("()"),
773                    },
774                },
775                ")" => Element {
776                    prefix: Prefix::RightDelimiter {
777                        delimiter: SimpleDelimiter::Paren,
778                    },
779                    postfix: Postfix::RightDelimiter {
780                        delimiter: SimpleDelimiter::Paren,
781                    },
782                },
783                "[" => Element {
784                    prefix: Prefix::LeftDelimiter {
785                        delimiter: SimpleDelimiter::SquareBracket,
786                        operator: Some(s),
787                        empty: Some("[]"),
788                    },
789                    postfix: Postfix::None,
790                },
791                "]" => Element {
792                    prefix: Prefix::RightDelimiter {
793                        delimiter: SimpleDelimiter::SquareBracket,
794                    },
795                    postfix: Postfix::RightDelimiter {
796                        delimiter: SimpleDelimiter::SquareBracket,
797                    },
798                },
799                "|" => Element {
800                    prefix: Prefix::LeftDelimiter {
801                        delimiter: SimpleDelimiter::Pipe,
802                        operator: Some(s),
803                        empty: None,
804                    },
805                    postfix: Postfix::RightDelimiter {
806                        delimiter: SimpleDelimiter::Pipe,
807                    },
808                },
809                "," => Element {
810                    prefix: Prefix::None,
811                    postfix: Postfix::BinaryOperator {
812                        fixity: Fixity::Left(SimplePrecedence::Comma),
813                        operator: s,
814                        no_rhs: Some("(,)"),
815                    },
816                },
817                "-" => Element {
818                    prefix: Prefix::UnaryOperator {
819                        precedence: SimplePrecedence::Multiplicative,
820                        operator: s,
821                        no_rhs: None,
822                    },
823                    postfix: Postfix::BinaryOperator {
824                        fixity: Fixity::Left(SimplePrecedence::Additive),
825                        operator: s,
826                        no_rhs: None,
827                    },
828                },
829                "+" => Element {
830                    prefix: Prefix::None,
831                    postfix: Postfix::BinaryOperator {
832                        fixity: Fixity::Left(SimplePrecedence::Additive),
833                        operator: s,
834                        no_rhs: None,
835                    },
836                },
837                "*" | "/" => Element {
838                    prefix: Prefix::None,
839                    postfix: Postfix::BinaryOperator {
840                        fixity: Fixity::Left(SimplePrecedence::Multiplicative),
841                        operator: s,
842                        no_rhs: None,
843                    },
844                },
845                "^" => Element {
846                    prefix: Prefix::None,
847                    postfix: Postfix::BinaryOperator {
848                        fixity: Fixity::Right(SimplePrecedence::Exponential),
849                        operator: s,
850                        no_rhs: None,
851                    },
852                },
853                "!" => Element {
854                    prefix: Prefix::None,
855                    postfix: Postfix::PostfixOperator {
856                        precedence: SimplePrecedence::Exponential,
857                        operator: s,
858                    },
859                },
860                _ => {
861                    // variables get implicit multiplication, other tokens don't (so that we can
862                    // test unexpected token errors)
863                    let postfix = if let SimpleCharSetTokenKind::Tag = kind {
864                        Postfix::ImplicitOperator {
865                            fixity: Fixity::Left(SimplePrecedence::Multiplicative),
866                            operator: "{*}",
867                        }
868                    } else {
869                        Postfix::None
870                    };
871                    Element {
872                        prefix: Prefix::Term { term: s },
873                        postfix,
874                    }
875                }
876            })
877        }
878    }
879
880    fn expr_to_str<'s, Idx>(expr: Expression<Idx, &'s str, &'s str, &'s str>) -> &'s str {
881        match expr.kind {
882            ExpressionKind::BinaryOperator(s) => s,
883            ExpressionKind::UnaryOperator(s) => s,
884            ExpressionKind::Term(s) => s,
885        }
886    }
887
888    #[test_case("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3", "3 4 2 * 1 5 - 2 3 ^ ^ / +" ; "simple arithmetic" )]
889    #[test_case("sin(max(5/2, 3)) / 3 * pi", "sin max 5 2 / 3 , ( ( 3 / pi *" ; "with functions" )]
890    #[test_case("2^3!", "2 3 ! ^" ; "postfix operators" )]
891    #[test_case("-2^3 + (-2)^3", "2 3 ^ - 2 - 3 ^ +" ; "prefix operators" )]
892    #[test_case("[1, 2, 3, 4]", "1 2 , 3 , 4 , [" ; "delimiter operators" )]
893    #[test_case("[1, (2, 3), 4]", "1 2 3 , , 4 , [" ; "nested delimiter operators" )]
894    #[test_case("[ ]", "[]" ; "empty list" )]
895    #[test_case("[ ] + [ ]", "[] [] +" ; "adding lists" )]
896    #[test_case("f()", "f ()" ; "empty function call" )]
897    #[test_case("[1, 2, 3, 4, ]", "1 2 , 3 , 4 , (,) [" ; "trailing comma" )]
898    #[test_case("a * |b|", "a b | *" ; "absolute value" )]
899    #[test_case("a, * b", "a (,) b *" ; "trailing comma with binary operator" )]
900    #[test_case("5x^2", "5 x 2 ^ {*}" ; "implicit operator" )]
901    fn parse_expression(input: &str, output: &str) -> anyhow::Result<()> {
902        let actual = parse(
903            SimpleTokenizer::new(StrSource::new(input)),
904            SimpleExprContext,
905        )?
906        .into_iter()
907        .map(expr_to_str)
908        .collect::<Vec<_>>();
909        let expected = output.split_whitespace().collect::<Vec<_>>();
910        assert_eq!(actual, expected);
911        Ok(())
912    }
913
914    #[test_case("3", "3", "" ; "single term" )]
915    #[test_case("-3!", "3 -", "!" ; "unary operators" )]
916    #[test_case("3!", "3", "!" ; "postfix operator" )]
917    #[test_case("-3 a", "3 -", "a" ; "unary operators with additional" )]
918    #[test_case("(5 + 4) * (3 - 2)", "5 4 +", "* (3 - 2)" ; "delimited group" )]
919    #[test_case("(3)!", "3", "!" ; "delimited with unary operators" )]
920    #[test_case("abc def)", "abc", "def)" ; "ignores invalid after first term" )]
921    fn parse_one(input: &str, output: &str, rest: &str) -> anyhow::Result<()> {
922        let mut tokens = SimpleTokenizer::new(StrSource::new(input));
923        let actual = parse_one_term(&mut tokens, SimpleExprContext)?
924            .into_iter()
925            .map(expr_to_str)
926            .collect::<Vec<_>>();
927        let expected = output.split_whitespace().collect::<Vec<_>>();
928        assert_eq!(actual, expected);
929        let actual_rest = tokens
930            .map(|res| res.map(|tok| tok.kind))
931            .collect::<Result<Vec<_>, _>>()?;
932        let expected_rest = SimpleTokenizer::new(StrSource::new(rest))
933            .map(|res| res.map(|tok| tok.kind))
934            .collect::<Result<Vec<_>, _>>()?;
935        assert_eq!(actual_rest, expected_rest);
936        Ok(())
937    }
938
939    #[test_case("-", false ; "unary")]
940    #[test_case("-3", true ; "unary with rhs")]
941    #[test_case("-3 *", false ; "binary")]
942    #[test_case("-3 * 3", true ; "binary with rhs")]
943    #[test_case("-(4 + (3 * 3)", false ; "incomplete delimiter")]
944    #[test_case("-(4 + (3 * 3))", true ; "complete delimiter")]
945    #[test_case("3,", true ; "binary with optional rhs")]
946    fn is_complete(input: &str, is_complete: bool) -> anyhow::Result<()> {
947        let mut tokens = SimpleTokenizer::new(StrSource::new(input));
948        let mut state = ParseState::new(SimpleExprContext);
949        while let Some(t) = tokens.next_token() {
950            state.parse_result(t);
951        }
952        assert_eq!(state.has_parsed_expression(), is_complete);
953        if is_complete {
954            state.finish()?;
955        } else {
956            state.finish().unwrap_err();
957        }
958        Ok(())
959    }
960
961    #[test_case("1 )", &[(ParseErrorKind::UnmatchedRightDelimiter, 2..3)] ; "unmatched right paren" )]
962    #[test_case("1 +", &[(ParseErrorKind::EndOfInput { expected: EXPECT_TERM }, 3..3)] ; "end of input" )]
963    #[test_case("(5 5 +", &[
964        (ParseErrorKind::UnexpectedToken { expected: EXPECT_OPERATOR }, 3..4),
965        (ParseErrorKind::EndOfInput { expected: EXPECT_TERM }, 6..6),
966        (ParseErrorKind::UnmatchedLeftDelimiter, 0..1),
967    ] ; "multiple errors")]
968    #[test_case("[ 1 )", &[
969        (ParseErrorKind::MismatchedDelimiter { opening: (0..1).into() }, 4..5),
970    ] ; "mismatched delimiters" )]
971    #[test_case("( [ 1 )", &[
972        (ParseErrorKind::MismatchedDelimiter { opening: (2..3).into() }, 6..7),
973        (ParseErrorKind::UnmatchedLeftDelimiter, 0..1),
974    ] ; "mismatched delimiters 2" )]
975    #[test_case("[ 1 + )", &[
976        (ParseErrorKind::UnexpectedToken { expected: EXPECT_TERM }, 6..7),
977        (ParseErrorKind::MismatchedDelimiter { opening: (0..1).into() }, 6..7),
978    ] ; "mismatched delimiters with missing rhs" )]
979    #[test_case("1 + * 2", &[
980        (ParseErrorKind::UnexpectedToken { expected: EXPECT_TERM }, 4..5),
981    ] ; "extra operator" )]
982    fn parse_expression_fail(
983        input: &str,
984        expected: &[(ParseErrorKind<Infallible, Infallible, usize>, Range<usize>)],
985    ) {
986        let actual = parse(
987            SimpleTokenizer::new(StrSource::new(input)),
988            SimpleExprContext,
989        )
990        .unwrap_err()
991        .errors
992        .into_iter()
993        .map(|err| {
994            (
995                err.kind.map_tokenizer_error(|_| unreachable!()),
996                err.span.into_range(),
997            )
998        })
999        .collect::<Vec<_>>();
1000        assert_eq!(actual, expected);
1001    }
1002}
expr_parser/parser.rs

expr_parser/
parser.rs
