yash_arith/
ast.rs

1// This file is part of yash, an extended POSIX shell.
2// Copyright (C) 2022 WATANABE Yuki
3//
4// This program is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8//
9// This program is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12// GNU General Public License for more details.
13//
14// You should have received a copy of the GNU General Public License
15// along with this program.  If not, see <https://www.gnu.org/licenses/>.
16
17//! Abstract syntax tree parser
18
19use crate::token::Operator;
20use crate::token::PeekableTokens;
21use crate::token::Term;
22use crate::token::Token;
23use crate::token::TokenError;
24use crate::token::TokenValue;
25use std::ops::Range;
26use thiserror::Error;
27
28pub(crate) mod portability;
29
30pub use portability::PortabilityError;
31
32/// Prefix operator kind
33#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
34pub enum PrefixOperator {
35    /// `++`
36    Increment,
37    /// `--`
38    Decrement,
39    /// `+`
40    NumericCoercion,
41    /// `-`
42    NumericNegation,
43    /// `!`
44    LogicalNegation,
45    /// `~`
46    BitwiseNegation,
47}
48
49/// Postfix operator kind
50#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
51pub enum PostfixOperator {
52    /// `++`
53    Increment,
54    /// `--`
55    Decrement,
56}
57
58/// Postfix operator kind
59#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
60pub enum BinaryOperator {
61    /// `=`
62    Assign,
63    /// `||`
64    LogicalOr,
65    /// `&&`
66    LogicalAnd,
67    /// `|`
68    BitwiseOr,
69    /// `|=`
70    BitwiseOrAssign,
71    /// `^`
72    BitwiseXor,
73    /// `^=`
74    BitwiseXorAssign,
75    /// `&`
76    BitwiseAnd,
77    /// `&=`
78    BitwiseAndAssign,
79    /// `==`
80    EqualTo,
81    /// `!=`
82    NotEqualTo,
83    /// `<`
84    LessThan,
85    /// `>`
86    GreaterThan,
87    /// `<=`
88    LessThanOrEqualTo,
89    /// `>=`
90    GreaterThanOrEqualTo,
91    /// `<<`
92    ShiftLeft,
93    /// `<<=`
94    ShiftLeftAssign,
95    /// `>>`
96    ShiftRight,
97    /// `>>=`
98    ShiftRightAssign,
99    /// `+`
100    Add,
101    /// `+=`
102    AddAssign,
103    /// `-`
104    Subtract,
105    /// `-=`
106    SubtractAssign,
107    /// `*`
108    Multiply,
109    /// `*=`
110    MultiplyAssign,
111    /// `/`
112    Divide,
113    /// `/=`
114    DivideAssign,
115    /// `%`
116    Remainder,
117    /// `%=`
118    RemainderAssign,
119}
120
121/// Associativity kind of binary operators
122#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
123enum Associativity {
124    Left,
125    Right,
126}
127
128impl Operator {
129    fn as_prefix(self) -> Option<PrefixOperator> {
130        match self {
131            Operator::PlusPlus => Some(PrefixOperator::Increment),
132            Operator::MinusMinus => Some(PrefixOperator::Decrement),
133            Operator::Plus => Some(PrefixOperator::NumericCoercion),
134            Operator::Minus => Some(PrefixOperator::NumericNegation),
135            Operator::Bang => Some(PrefixOperator::LogicalNegation),
136            Operator::Tilde => Some(PrefixOperator::BitwiseNegation),
137            _ => None,
138        }
139    }
140
141    fn as_postfix(self) -> Option<PostfixOperator> {
142        match self {
143            Operator::PlusPlus => Some(PostfixOperator::Increment),
144            Operator::MinusMinus => Some(PostfixOperator::Decrement),
145            _ => None,
146        }
147    }
148
149    fn as_binary(self) -> Option<(BinaryOperator, Associativity)> {
150        use Associativity::*;
151        use BinaryOperator::*;
152        match self {
153            Operator::Equal => Some((Assign, Right)),
154            Operator::BarEqual => Some((BitwiseOrAssign, Right)),
155            Operator::CaretEqual => Some((BitwiseXorAssign, Right)),
156            Operator::AndEqual => Some((BitwiseAndAssign, Right)),
157            Operator::LessLessEqual => Some((ShiftLeftAssign, Right)),
158            Operator::GreaterGreaterEqual => Some((ShiftRightAssign, Right)),
159            Operator::PlusEqual => Some((AddAssign, Right)),
160            Operator::MinusEqual => Some((SubtractAssign, Right)),
161            Operator::AsteriskEqual => Some((MultiplyAssign, Right)),
162            Operator::SlashEqual => Some((DivideAssign, Right)),
163            Operator::PercentEqual => Some((RemainderAssign, Right)),
164            Operator::BarBar => Some((LogicalOr, Left)),
165            Operator::AndAnd => Some((LogicalAnd, Left)),
166            Operator::Bar => Some((BitwiseOr, Left)),
167            Operator::Caret => Some((BitwiseXor, Left)),
168            Operator::And => Some((BitwiseAnd, Left)),
169            Operator::EqualEqual => Some((EqualTo, Left)),
170            Operator::BangEqual => Some((NotEqualTo, Left)),
171            Operator::Less => Some((LessThan, Left)),
172            Operator::LessEqual => Some((LessThanOrEqualTo, Left)),
173            Operator::Greater => Some((GreaterThan, Left)),
174            Operator::GreaterEqual => Some((GreaterThanOrEqualTo, Left)),
175            Operator::LessLess => Some((ShiftLeft, Left)),
176            Operator::GreaterGreater => Some((ShiftRight, Left)),
177            Operator::Plus => Some((Add, Left)),
178            Operator::Minus => Some((Subtract, Left)),
179            Operator::Asterisk => Some((Multiply, Left)),
180            Operator::Slash => Some((Divide, Left)),
181            Operator::Percent => Some((Remainder, Left)),
182            _ => None,
183        }
184    }
185
186    /// Returns the precedence of the operator.
187    ///
188    /// If the operator acts as both a unary and binary operator, the result is
189    /// the precedence as a binary operator.
190    fn precedence(self) -> u8 {
191        use Operator::*;
192        match self {
193            CloseParen | Colon => 0,
194            Equal | BarEqual | CaretEqual | AndEqual | LessLessEqual | GreaterGreaterEqual
195            | PlusEqual | MinusEqual | AsteriskEqual | SlashEqual | PercentEqual => 1,
196            Question => 2,
197            BarBar => 3,
198            AndAnd => 4,
199            Bar => 5,
200            Caret => 6,
201            And => 7,
202            EqualEqual | BangEqual => 8,
203            Less | LessEqual | Greater | GreaterEqual => 9,
204            LessLess | GreaterGreater => 10,
205            Plus | Minus => 11,
206            Asterisk | Slash | Percent => 12,
207            Tilde | Bang | PlusPlus | MinusMinus | OpenParen => 13,
208        }
209    }
210}
211
212/// Node of an abstract syntax tree (AST)
213///
214/// A whole AST is meant to be constructed as a vector of `Ast` nodes. A
215/// non-leaf node immediately follows its operand node in the vector. If a node
216/// has more than one operand, the first operand immediately precedes the
217/// second. This scheme makes up the tree in reverse Polish notation.
218#[derive(Clone, Debug, Eq, Hash, PartialEq)]
219pub enum Ast<'a> {
220    /// Term: a constant value or variable
221    Term(Term<'a>),
222    /// Prefix operator
223    ///
224    /// This node immediately follows its operand node.
225    Prefix {
226        /// Operator
227        operator: PrefixOperator,
228        /// Range of the substring where the operator occurs in the parsed expression
229        location: Range<usize>,
230    },
231    /// Postfix operator
232    ///
233    /// This node immediately follows its operand node.
234    Postfix {
235        /// Operator
236        operator: PostfixOperator,
237        /// Range of the substring where the operator occurs in the parsed expression
238        location: Range<usize>,
239    },
240    /// Binary operator
241    ///
242    /// This node immediately follows its right-hand-side operand node. The
243    /// right-hand-side operand tree in turn follows the left-hand-side.
244    Binary {
245        /// Operator
246        operator: BinaryOperator,
247        /// Length (number of `Ast` nodes) of the right-hand-side operand tree
248        rhs_len: usize,
249        /// Range of the substring where the operator occurs in the parsed expression
250        location: Range<usize>,
251    },
252    /// Conditional ternary operator
253    ///
254    /// This node has three child nodes: the condition, the then value, and the
255    /// else value. They appear in the `Ast` vector in this order and are
256    /// immediately followed by this `Conditional` node.
257    Conditional {
258        /// Length (number of `Ast` nodes) of the then value tree
259        then_len: usize,
260        /// Length (number of `Ast` nodes) of the else value tree
261        else_len: usize,
262    },
263}
264
265/// Cause of a syntax error
266#[derive(Clone, Debug, Eq, Error, Hash, PartialEq)]
267#[non_exhaustive]
268pub enum SyntaxError {
269    /// Error in tokenization
270    #[error(transparent)]
271    TokenError(#[from] TokenError),
272    /// Expression with a missing value
273    #[error("incomplete expression")]
274    IncompleteExpression,
275    /// Operator missing
276    #[error("expected an operator")]
277    MissingOperator,
278    /// `(` without `)`
279    #[error("closing parenthesis missing")]
280    UnclosedParenthesis {
281        /// Range of the substring in the evaluated expression string where `(` appears
282        opening_location: Range<usize>,
283    },
284    /// `?` without `:`
285    #[error("expected `:`")]
286    QuestionWithoutColon {
287        /// Range of the substring in the evaluated expression string where `?` appears
288        question_location: Range<usize>,
289    },
290    /// `:` without `?`
291    #[error("`:` without matching `?`")]
292    ColonWithoutQuestion,
293    /// Other error in operator usage
294    #[error("invalid use of operator")]
295    InvalidOperator,
296}
297
298/// Description of an error that occurred during expansion
299#[derive(Clone, Debug, Eq, Hash, PartialEq)]
300pub struct Error {
301    /// Cause of the error
302    pub cause: SyntaxError,
303    /// Range of the substring in the evaluated expression string where the error occurred
304    pub location: Range<usize>,
305}
306
307impl From<crate::token::Error> for Error {
308    fn from(e: crate::token::Error) -> Self {
309        Error {
310            cause: e.cause.into(),
311            location: e.location,
312        }
313    }
314}
315
316/// Parses postfix operators
317fn parse_postfix<'a>(
318    tokens: &mut PeekableTokens<'a>,
319    result: &mut Vec<Ast<'a>>,
320) -> Result<(), Error> {
321    while let &Ok(Token {
322        value: TokenValue::Operator(operator),
323        ..
324    }) = tokens.peek()
325    {
326        let operator = match operator.as_postfix() {
327            Some(operator) => operator,
328            None => break,
329        };
330        let location = tokens.next().unwrap().location;
331        result.push(Ast::Postfix { operator, location });
332    }
333    Ok(())
334}
335
336/// Parses a closing parenthesis `")"`.
337///
338/// Returns an error if the next token is not a closing parenthesis.
339fn parse_close_paren(
340    tokens: &mut PeekableTokens,
341    opening_location: Range<usize>,
342) -> Result<(), Error> {
343    let token = tokens.next()?;
344    match token.value {
345        TokenValue::Operator(Operator::CloseParen) => Ok(()),
346
347        TokenValue::Operator(Operator::Colon) => Err(Error {
348            cause: SyntaxError::ColonWithoutQuestion,
349            location: token.location,
350        }),
351
352        _ => Err(Error {
353            cause: SyntaxError::UnclosedParenthesis { opening_location },
354            location: token.location,
355        }),
356    }
357}
358
359/// Parses a leaf expression.
360///
361/// A leaf expression is a term or parenthesized expression, optionally modified
362/// by unary operators.
363fn parse_leaf<'a>(tokens: &mut PeekableTokens<'a>, result: &mut Vec<Ast<'a>>) -> Result<(), Error> {
364    let token = tokens.next()?;
365    match token.value {
366        TokenValue::Term(term) => {
367            result.push(Ast::Term(term));
368            parse_postfix(tokens, result)
369        }
370
371        TokenValue::Operator(Operator::OpenParen) => {
372            parse_tree(tokens, 1, result)?;
373            parse_close_paren(tokens, token.location)?;
374            parse_postfix(tokens, result)
375        }
376
377        TokenValue::Operator(operator) => {
378            let operator = match operator.as_prefix() {
379                Some(operator) => operator,
380                None => {
381                    return Err(Error {
382                        cause: SyntaxError::InvalidOperator,
383                        location: token.location,
384                    });
385                }
386            };
387            parse_leaf(tokens, result)?;
388            result.push(Ast::Prefix {
389                operator,
390                location: token.location,
391            });
392            Ok(())
393        }
394
395        TokenValue::EndOfInput => Err(Error {
396            cause: SyntaxError::IncompleteExpression,
397            location: token.location,
398        }),
399    }
400}
401
402/// Parses the right-hand-side operand of a binary operation and pushes the
403/// operator to the result.
404fn parse_binary_rhs<'a>(
405    tokens: &mut PeekableTokens<'a>,
406    operator: BinaryOperator,
407    location: Range<usize>,
408    min_precedence: u8,
409    result: &mut Vec<Ast<'a>>,
410) -> Result<(), Error> {
411    let old_len = result.len();
412    parse_tree(tokens, min_precedence, result)?;
413    result.push(Ast::Binary {
414        operator,
415        rhs_len: result.len() - old_len,
416        location,
417    });
418    Ok(())
419}
420
421/// Parses a expression that may contain binary and ternary operators.
422///
423/// This function consumes binary operators with precedence equal to or greater
424/// than the given minimum precedence, which must be greater than 0.
425fn parse_tree<'a>(
426    tokens: &mut PeekableTokens<'a>,
427    min_precedence: u8,
428    result: &mut Vec<Ast<'a>>,
429) -> Result<(), Error> {
430    parse_leaf(tokens, result)?;
431
432    while let &Ok(Token {
433        value: TokenValue::Operator(operator),
434        ..
435    }) = tokens.peek()
436    {
437        let precedence = operator.precedence();
438        if precedence < min_precedence {
439            break;
440        }
441
442        let location = tokens.next().unwrap().location;
443
444        use Operator::*;
445        if operator == Question {
446            let then_index = result.len();
447            parse_tree(tokens, 1, result)?;
448
449            // Skip the colon operator
450            let token = tokens.next()?;
451            if token.value != TokenValue::Operator(Operator::Colon) {
452                return Err(Error {
453                    cause: SyntaxError::QuestionWithoutColon {
454                        question_location: location,
455                    },
456                    location: token.location,
457                });
458            }
459
460            let else_index = result.len();
461            parse_tree(tokens, precedence, result)?;
462
463            result.push(Ast::Conditional {
464                then_len: else_index - then_index,
465                else_len: result.len() - else_index,
466            });
467            continue;
468        }
469
470        let (operator, rhs_precedence) = match operator.as_binary() {
471            Some((operator, Associativity::Left)) => (operator, precedence + 1),
472            Some((operator, Associativity::Right)) => (operator, precedence),
473            None => {
474                return Err(Error {
475                    cause: SyntaxError::InvalidOperator,
476                    location,
477                });
478            }
479        };
480        parse_binary_rhs(tokens, operator, location, rhs_precedence, result)?
481    }
482    Ok(())
483}
484
485/// Ensures there is no more token.
486///
487/// Returns an error if there is a next token.
488fn parse_end_of_input(tokens: &mut PeekableTokens) -> Result<(), Error> {
489    let token = tokens.next()?;
490    match token.value {
491        TokenValue::EndOfInput => Ok(()),
492
493        TokenValue::Operator(Operator::Colon) => Err(Error {
494            cause: SyntaxError::ColonWithoutQuestion,
495            location: token.location,
496        }),
497
498        _ => Err(Error {
499            cause: SyntaxError::MissingOperator,
500            location: token.location,
501        }),
502    }
503}
504
505/// Parses the whole expression.
506///
507/// A successful parse is returned as a non-empty vector of `Ast` nodes, where
508/// the last node is the root.
509pub fn parse(mut tokens: PeekableTokens) -> Result<Vec<Ast>, Error> {
510    let mut result = Vec::new();
511    parse_tree(&mut tokens, 1, &mut result)?;
512    parse_end_of_input(&mut tokens)?;
513    Ok(result)
514}
515
516#[cfg(test)]
517mod tests {
518    use super::*;
519    use crate::token::Value;
520
521    fn parse_str(source: &str) -> Result<Vec<Ast<'_>>, Error> {
522        parse(PeekableTokens::from(source))
523    }
524
525    #[test]
526    fn term() {
527        assert_eq!(
528            parse_str("123").unwrap(),
529            [Ast::Term(Term::Value(Value::Integer(123)))]
530        );
531        assert_eq!(
532            parse_str("0x42").unwrap(),
533            [Ast::Term(Term::Value(Value::Integer(0x42)))]
534        );
535        assert_eq!(
536            parse_str(" foo ").unwrap(),
537            [Ast::Term(Term::Variable {
538                name: "foo",
539                location: 1..4
540            })]
541        );
542    }
543
544    #[test]
545    fn token_error_in_term() {
546        assert_eq!(
547            parse_str("08"),
548            Err(Error {
549                cause: SyntaxError::TokenError(TokenError::InvalidNumericConstant),
550                location: 0..2
551            })
552        );
553    }
554
555    #[test]
556    fn increment_postfix_operator() {
557        assert_eq!(
558            parse_str("a++").unwrap(),
559            [
560                Ast::Term(Term::Variable {
561                    name: "a",
562                    location: 0..1,
563                }),
564                Ast::Postfix {
565                    operator: PostfixOperator::Increment,
566                    location: 1..3,
567                },
568            ]
569        );
570    }
571
572    #[test]
573    fn decrement_postfix_operator() {
574        assert_eq!(
575            parse_str("a--").unwrap(),
576            [
577                Ast::Term(Term::Variable {
578                    name: "a",
579                    location: 0..1,
580                }),
581                Ast::Postfix {
582                    operator: PostfixOperator::Decrement,
583                    location: 1..3,
584                },
585            ]
586        );
587    }
588
589    #[test]
590    fn combination_of_postfix_operators() {
591        assert_eq!(
592            parse_str(" x ++  -- ++ ").unwrap(),
593            [
594                Ast::Term(Term::Variable {
595                    name: "x",
596                    location: 1..2,
597                }),
598                Ast::Postfix {
599                    operator: PostfixOperator::Increment,
600                    location: 3..5,
601                },
602                Ast::Postfix {
603                    operator: PostfixOperator::Decrement,
604                    location: 7..9,
605                },
606                Ast::Postfix {
607                    operator: PostfixOperator::Increment,
608                    location: 10..12,
609                },
610            ]
611        );
612    }
613
614    #[test]
615    fn increment_prefix_operator() {
616        assert_eq!(
617            parse_str("++a").unwrap(),
618            [
619                Ast::Term(Term::Variable {
620                    name: "a",
621                    location: 2..3,
622                }),
623                Ast::Prefix {
624                    operator: PrefixOperator::Increment,
625                    location: 0..2,
626                },
627            ]
628        );
629    }
630
631    #[test]
632    fn decrement_prefix_operator() {
633        assert_eq!(
634            parse_str("--a").unwrap(),
635            [
636                Ast::Term(Term::Variable {
637                    name: "a",
638                    location: 2..3,
639                }),
640                Ast::Prefix {
641                    operator: PrefixOperator::Decrement,
642                    location: 0..2,
643                },
644            ]
645        );
646    }
647
648    #[test]
649    fn numeric_coercion_prefix_operator() {
650        assert_eq!(
651            parse_str("+a").unwrap(),
652            [
653                Ast::Term(Term::Variable {
654                    name: "a",
655                    location: 1..2,
656                }),
657                Ast::Prefix {
658                    operator: PrefixOperator::NumericCoercion,
659                    location: 0..1,
660                },
661            ]
662        );
663    }
664
665    #[test]
666    fn numeric_negation_prefix_operator() {
667        assert_eq!(
668            parse_str("-a").unwrap(),
669            [
670                Ast::Term(Term::Variable {
671                    name: "a",
672                    location: 1..2,
673                }),
674                Ast::Prefix {
675                    operator: PrefixOperator::NumericNegation,
676                    location: 0..1,
677                },
678            ]
679        );
680    }
681
682    #[test]
683    fn logical_negation_prefix_operator() {
684        assert_eq!(
685            parse_str("!a").unwrap(),
686            [
687                Ast::Term(Term::Variable {
688                    name: "a",
689                    location: 1..2,
690                }),
691                Ast::Prefix {
692                    operator: PrefixOperator::LogicalNegation,
693                    location: 0..1,
694                },
695            ]
696        );
697    }
698
699    #[test]
700    fn bitwise_negation_prefix_operator() {
701        assert_eq!(
702            parse_str("~a").unwrap(),
703            [
704                Ast::Term(Term::Variable {
705                    name: "a",
706                    location: 1..2,
707                }),
708                Ast::Prefix {
709                    operator: PrefixOperator::BitwiseNegation,
710                    location: 0..1,
711                },
712            ]
713        );
714    }
715
716    #[test]
717    fn combination_of_prefix_operators() {
718        assert_eq!(
719            parse_str(" - + !  ~ ++ -- i ").unwrap(),
720            [
721                Ast::Term(Term::Variable {
722                    name: "i",
723                    location: 16..17,
724                }),
725                Ast::Prefix {
726                    operator: PrefixOperator::Decrement,
727                    location: 13..15,
728                },
729                Ast::Prefix {
730                    operator: PrefixOperator::Increment,
731                    location: 10..12,
732                },
733                Ast::Prefix {
734                    operator: PrefixOperator::BitwiseNegation,
735                    location: 8..9,
736                },
737                Ast::Prefix {
738                    operator: PrefixOperator::LogicalNegation,
739                    location: 5..6,
740                },
741                Ast::Prefix {
742                    operator: PrefixOperator::NumericCoercion,
743                    location: 3..4,
744                },
745                Ast::Prefix {
746                    operator: PrefixOperator::NumericNegation,
747                    location: 1..2,
748                },
749            ]
750        );
751    }
752
753    #[test]
754    fn combination_of_unary_and_binary_operators() {
755        assert_eq!(
756            parse_str("0 + + a ++ * !1").unwrap(),
757            [
758                Ast::Term(Term::Value(Value::Integer(0))),
759                Ast::Term(Term::Variable {
760                    name: "a",
761                    location: 6..7,
762                }),
763                Ast::Postfix {
764                    operator: PostfixOperator::Increment,
765                    location: 8..10,
766                },
767                Ast::Prefix {
768                    operator: PrefixOperator::NumericCoercion,
769                    location: 4..5,
770                },
771                Ast::Term(Term::Value(Value::Integer(1))),
772                Ast::Prefix {
773                    operator: PrefixOperator::LogicalNegation,
774                    location: 13..14,
775                },
776                Ast::Binary {
777                    operator: BinaryOperator::Multiply,
778                    rhs_len: 2,
779                    location: 11..12,
780                },
781                Ast::Binary {
782                    operator: BinaryOperator::Add,
783                    rhs_len: 6,
784                    location: 2..3,
785                },
786            ]
787        );
788    }
789
790    #[test]
791    fn simple_assignment_operator() {
792        assert_eq!(
793            parse_str("a=42").unwrap(),
794            [
795                Ast::Term(Term::Variable {
796                    name: "a",
797                    location: 0..1,
798                }),
799                Ast::Term(Term::Value(Value::Integer(42))),
800                Ast::Binary {
801                    operator: BinaryOperator::Assign,
802                    rhs_len: 1,
803                    location: 1..2,
804                },
805            ]
806        );
807    }
808
809    #[test]
810    fn bitwise_or_assign_operator() {
811        assert_eq!(
812            parse_str("b|=2").unwrap(),
813            [
814                Ast::Term(Term::Variable {
815                    name: "b",
816                    location: 0..1,
817                }),
818                Ast::Term(Term::Value(Value::Integer(2))),
819                Ast::Binary {
820                    operator: BinaryOperator::BitwiseOrAssign,
821                    rhs_len: 1,
822                    location: 1..3,
823                },
824            ]
825        );
826    }
827
828    #[test]
829    fn bitwise_xor_assign_operator() {
830        assert_eq!(
831            parse_str("c^=3").unwrap(),
832            [
833                Ast::Term(Term::Variable {
834                    name: "c",
835                    location: 0..1,
836                }),
837                Ast::Term(Term::Value(Value::Integer(3))),
838                Ast::Binary {
839                    operator: BinaryOperator::BitwiseXorAssign,
840                    rhs_len: 1,
841                    location: 1..3,
842                },
843            ]
844        );
845    }
846
847    #[test]
848    fn bitwise_and_assign_operator() {
849        assert_eq!(
850            parse_str("d&=5").unwrap(),
851            [
852                Ast::Term(Term::Variable {
853                    name: "d",
854                    location: 0..1,
855                }),
856                Ast::Term(Term::Value(Value::Integer(5))),
857                Ast::Binary {
858                    operator: BinaryOperator::BitwiseAndAssign,
859                    rhs_len: 1,
860                    location: 1..3,
861                },
862            ]
863        );
864    }
865
866    #[test]
867    fn shift_left_assign_operator() {
868        assert_eq!(
869            parse_str("e<<=7").unwrap(),
870            [
871                Ast::Term(Term::Variable {
872                    name: "e",
873                    location: 0..1,
874                }),
875                Ast::Term(Term::Value(Value::Integer(7))),
876                Ast::Binary {
877                    operator: BinaryOperator::ShiftLeftAssign,
878                    rhs_len: 1,
879                    location: 1..4,
880                },
881            ]
882        );
883    }
884
885    #[test]
886    fn shift_right_assign_operator() {
887        assert_eq!(
888            parse_str("f>>=11").unwrap(),
889            [
890                Ast::Term(Term::Variable {
891                    name: "f",
892                    location: 0..1,
893                }),
894                Ast::Term(Term::Value(Value::Integer(11))),
895                Ast::Binary {
896                    operator: BinaryOperator::ShiftRightAssign,
897                    rhs_len: 1,
898                    location: 1..4,
899                },
900            ]
901        );
902    }
903
904    #[test]
905    fn add_assign_operator() {
906        assert_eq!(
907            parse_str("g+=13").unwrap(),
908            [
909                Ast::Term(Term::Variable {
910                    name: "g",
911                    location: 0..1,
912                }),
913                Ast::Term(Term::Value(Value::Integer(13))),
914                Ast::Binary {
915                    operator: BinaryOperator::AddAssign,
916                    rhs_len: 1,
917                    location: 1..3,
918                },
919            ]
920        );
921    }
922
923    #[test]
924    fn subtract_assign_operator() {
925        assert_eq!(
926            parse_str("h-=17").unwrap(),
927            [
928                Ast::Term(Term::Variable {
929                    name: "h",
930                    location: 0..1,
931                }),
932                Ast::Term(Term::Value(Value::Integer(17))),
933                Ast::Binary {
934                    operator: BinaryOperator::SubtractAssign,
935                    rhs_len: 1,
936                    location: 1..3,
937                },
938            ]
939        );
940    }
941
942    #[test]
943    fn multiply_assign_operator() {
944        assert_eq!(
945            parse_str("i*=19").unwrap(),
946            [
947                Ast::Term(Term::Variable {
948                    name: "i",
949                    location: 0..1,
950                }),
951                Ast::Term(Term::Value(Value::Integer(19))),
952                Ast::Binary {
953                    operator: BinaryOperator::MultiplyAssign,
954                    rhs_len: 1,
955                    location: 1..3,
956                },
957            ]
958        );
959    }
960
961    #[test]
962    fn divide_assign_operator() {
963        assert_eq!(
964            parse_str("j/=23").unwrap(),
965            [
966                Ast::Term(Term::Variable {
967                    name: "j",
968                    location: 0..1,
969                }),
970                Ast::Term(Term::Value(Value::Integer(23))),
971                Ast::Binary {
972                    operator: BinaryOperator::DivideAssign,
973                    rhs_len: 1,
974                    location: 1..3,
975                },
976            ]
977        );
978    }
979
980    #[test]
981    fn remainder_assign_operator() {
982        assert_eq!(
983            parse_str("k%=29").unwrap(),
984            [
985                Ast::Term(Term::Variable {
986                    name: "k",
987                    location: 0..1,
988                }),
989                Ast::Term(Term::Value(Value::Integer(29))),
990                Ast::Binary {
991                    operator: BinaryOperator::RemainderAssign,
992                    rhs_len: 1,
993                    location: 1..3,
994                },
995            ]
996        );
997    }
998
999    #[test]
1000    fn assignment_operators_are_right_associative() {
1001        assert_eq!(
1002            parse_str(" a = b |= c ^= d &= e <<= f >>= g += h -= i *= j /= k %= m ").unwrap(),
1003            [
1004                Ast::Term(Term::Variable {
1005                    name: "a",
1006                    location: 1..2,
1007                }),
1008                Ast::Term(Term::Variable {
1009                    name: "b",
1010                    location: 5..6,
1011                }),
1012                Ast::Term(Term::Variable {
1013                    name: "c",
1014                    location: 10..11,
1015                }),
1016                Ast::Term(Term::Variable {
1017                    name: "d",
1018                    location: 15..16,
1019                }),
1020                Ast::Term(Term::Variable {
1021                    name: "e",
1022                    location: 20..21,
1023                }),
1024                Ast::Term(Term::Variable {
1025                    name: "f",
1026                    location: 26..27,
1027                }),
1028                Ast::Term(Term::Variable {
1029                    name: "g",
1030                    location: 32..33,
1031                }),
1032                Ast::Term(Term::Variable {
1033                    name: "h",
1034                    location: 37..38,
1035                }),
1036                Ast::Term(Term::Variable {
1037                    name: "i",
1038                    location: 42..43,
1039                }),
1040                Ast::Term(Term::Variable {
1041                    name: "j",
1042                    location: 47..48,
1043                }),
1044                Ast::Term(Term::Variable {
1045                    name: "k",
1046                    location: 52..53,
1047                }),
1048                Ast::Term(Term::Variable {
1049                    name: "m",
1050                    location: 57..58,
1051                }),
1052                Ast::Binary {
1053                    operator: BinaryOperator::RemainderAssign,
1054                    rhs_len: 1,
1055                    location: 54..56,
1056                },
1057                Ast::Binary {
1058                    operator: BinaryOperator::DivideAssign,
1059                    rhs_len: 3,
1060                    location: 49..51,
1061                },
1062                Ast::Binary {
1063                    operator: BinaryOperator::MultiplyAssign,
1064                    rhs_len: 5,
1065                    location: 44..46,
1066                },
1067                Ast::Binary {
1068                    operator: BinaryOperator::SubtractAssign,
1069                    rhs_len: 7,
1070                    location: 39..41,
1071                },
1072                Ast::Binary {
1073                    operator: BinaryOperator::AddAssign,
1074                    rhs_len: 9,
1075                    location: 34..36,
1076                },
1077                Ast::Binary {
1078                    operator: BinaryOperator::ShiftRightAssign,
1079                    rhs_len: 11,
1080                    location: 28..31,
1081                },
1082                Ast::Binary {
1083                    operator: BinaryOperator::ShiftLeftAssign,
1084                    rhs_len: 13,
1085                    location: 22..25,
1086                },
1087                Ast::Binary {
1088                    operator: BinaryOperator::BitwiseAndAssign,
1089                    rhs_len: 15,
1090                    location: 17..19,
1091                },
1092                Ast::Binary {
1093                    operator: BinaryOperator::BitwiseXorAssign,
1094                    rhs_len: 17,
1095                    location: 12..14,
1096                },
1097                Ast::Binary {
1098                    operator: BinaryOperator::BitwiseOrAssign,
1099                    rhs_len: 19,
1100                    location: 7..9,
1101                },
1102                Ast::Binary {
1103                    operator: BinaryOperator::Assign,
1104                    rhs_len: 21,
1105                    location: 3..4,
1106                },
1107            ]
1108        );
1109    }
1110
1111    #[test]
1112    fn logical_or_operator() {
1113        assert_eq!(
1114            parse_str("3||5").unwrap(),
1115            [
1116                Ast::Term(Term::Value(Value::Integer(3))),
1117                Ast::Term(Term::Value(Value::Integer(5))),
1118                Ast::Binary {
1119                    operator: BinaryOperator::LogicalOr,
1120                    rhs_len: 1,
1121                    location: 1..3,
1122                },
1123            ]
1124        );
1125    }
1126
1127    #[test]
1128    fn logical_or_operator_is_left_associative() {
1129        assert_eq!(
1130            parse_str("1||2||3").unwrap(),
1131            [
1132                Ast::Term(Term::Value(Value::Integer(1))),
1133                Ast::Term(Term::Value(Value::Integer(2))),
1134                Ast::Binary {
1135                    operator: BinaryOperator::LogicalOr,
1136                    rhs_len: 1,
1137                    location: 1..3,
1138                },
1139                Ast::Term(Term::Value(Value::Integer(3))),
1140                Ast::Binary {
1141                    operator: BinaryOperator::LogicalOr,
1142                    rhs_len: 1,
1143                    location: 4..6,
1144                },
1145            ]
1146        );
1147    }
1148
1149    #[test]
1150    fn logical_or_operator_in_conditional_operator() {
1151        assert_eq!(
1152            parse_str("1||2?3:4||5").unwrap(),
1153            [
1154                Ast::Term(Term::Value(Value::Integer(1))),
1155                Ast::Term(Term::Value(Value::Integer(2))),
1156                Ast::Binary {
1157                    operator: BinaryOperator::LogicalOr,
1158                    rhs_len: 1,
1159                    location: 1..3,
1160                },
1161                Ast::Term(Term::Value(Value::Integer(3))),
1162                Ast::Term(Term::Value(Value::Integer(4))),
1163                Ast::Term(Term::Value(Value::Integer(5))),
1164                Ast::Binary {
1165                    operator: BinaryOperator::LogicalOr,
1166                    rhs_len: 1,
1167                    location: 8..10,
1168                },
1169                Ast::Conditional {
1170                    then_len: 1,
1171                    else_len: 3,
1172                },
1173            ]
1174        );
1175    }
1176
1177    #[test]
1178    fn logical_and_operator() {
1179        assert_eq!(
1180            parse_str("3&&5").unwrap(),
1181            [
1182                Ast::Term(Term::Value(Value::Integer(3))),
1183                Ast::Term(Term::Value(Value::Integer(5))),
1184                Ast::Binary {
1185                    operator: BinaryOperator::LogicalAnd,
1186                    rhs_len: 1,
1187                    location: 1..3,
1188                },
1189            ]
1190        );
1191    }
1192
1193    #[test]
1194    fn logical_and_operator_is_left_associative() {
1195        assert_eq!(
1196            parse_str("1&&2&&3").unwrap(),
1197            [
1198                Ast::Term(Term::Value(Value::Integer(1))),
1199                Ast::Term(Term::Value(Value::Integer(2))),
1200                Ast::Binary {
1201                    operator: BinaryOperator::LogicalAnd,
1202                    rhs_len: 1,
1203                    location: 1..3,
1204                },
1205                Ast::Term(Term::Value(Value::Integer(3))),
1206                Ast::Binary {
1207                    operator: BinaryOperator::LogicalAnd,
1208                    rhs_len: 1,
1209                    location: 4..6,
1210                },
1211            ]
1212        );
1213    }
1214
1215    #[test]
1216    fn logical_and_operator_in_logical_or_operator() {
1217        assert_eq!(
1218            parse_str("1&&2||3&&4").unwrap(),
1219            [
1220                Ast::Term(Term::Value(Value::Integer(1))),
1221                Ast::Term(Term::Value(Value::Integer(2))),
1222                Ast::Binary {
1223                    operator: BinaryOperator::LogicalAnd,
1224                    rhs_len: 1,
1225                    location: 1..3,
1226                },
1227                Ast::Term(Term::Value(Value::Integer(3))),
1228                Ast::Term(Term::Value(Value::Integer(4))),
1229                Ast::Binary {
1230                    operator: BinaryOperator::LogicalAnd,
1231                    rhs_len: 1,
1232                    location: 7..9,
1233                },
1234                Ast::Binary {
1235                    operator: BinaryOperator::LogicalOr,
1236                    rhs_len: 3,
1237                    location: 4..6,
1238                },
1239            ]
1240        );
1241    }
1242
1243    #[test]
1244    fn multiplication_operator_in_addition_operator() {
1245        assert_eq!(
1246            parse_str("1*2+3*4").unwrap(),
1247            [
1248                Ast::Term(Term::Value(Value::Integer(1))),
1249                Ast::Term(Term::Value(Value::Integer(2))),
1250                Ast::Binary {
1251                    operator: BinaryOperator::Multiply,
1252                    rhs_len: 1,
1253                    location: 1..2,
1254                },
1255                Ast::Term(Term::Value(Value::Integer(3))),
1256                Ast::Term(Term::Value(Value::Integer(4))),
1257                Ast::Binary {
1258                    operator: BinaryOperator::Multiply,
1259                    rhs_len: 1,
1260                    location: 5..6,
1261                },
1262                Ast::Binary {
1263                    operator: BinaryOperator::Add,
1264                    rhs_len: 3,
1265                    location: 3..4,
1266                },
1267            ]
1268        );
1269    }
1270
1271    #[test]
1272    fn multiplication_division_remainder_operators_are_left_associative() {
1273        assert_eq!(
1274            parse_str("1*2/3%4").unwrap(),
1275            [
1276                Ast::Term(Term::Value(Value::Integer(1))),
1277                Ast::Term(Term::Value(Value::Integer(2))),
1278                Ast::Binary {
1279                    operator: BinaryOperator::Multiply,
1280                    rhs_len: 1,
1281                    location: 1..2,
1282                },
1283                Ast::Term(Term::Value(Value::Integer(3))),
1284                Ast::Binary {
1285                    operator: BinaryOperator::Divide,
1286                    rhs_len: 1,
1287                    location: 3..4,
1288                },
1289                Ast::Term(Term::Value(Value::Integer(4))),
1290                Ast::Binary {
1291                    operator: BinaryOperator::Remainder,
1292                    rhs_len: 1,
1293                    location: 5..6,
1294                },
1295            ]
1296        );
1297    }
1298
1299    #[test]
1300    fn conditional_operator() {
1301        assert_eq!(
1302            parse_str("1?2:3").unwrap(),
1303            [
1304                Ast::Term(Term::Value(Value::Integer(1))),
1305                Ast::Term(Term::Value(Value::Integer(2))),
1306                Ast::Term(Term::Value(Value::Integer(3))),
1307                Ast::Conditional {
1308                    then_len: 1,
1309                    else_len: 1,
1310                },
1311            ]
1312        );
1313    }
1314
1315    #[test]
1316    fn assignment_in_then_value() {
1317        assert_eq!(
1318            parse_str("a ? b = 0 : 1").unwrap(),
1319            [
1320                Ast::Term(Term::Variable {
1321                    name: "a",
1322                    location: 0..1,
1323                }),
1324                Ast::Term(Term::Variable {
1325                    name: "b",
1326                    location: 4..5,
1327                }),
1328                Ast::Term(Term::Value(Value::Integer(0))),
1329                Ast::Binary {
1330                    operator: BinaryOperator::Assign,
1331                    rhs_len: 1,
1332                    location: 6..7,
1333                },
1334                Ast::Term(Term::Value(Value::Integer(1))),
1335                Ast::Conditional {
1336                    then_len: 3,
1337                    else_len: 1,
1338                },
1339            ]
1340        );
1341    }
1342
1343    #[test]
1344    fn condition_in_assignment() {
1345        assert_eq!(
1346            parse_str("4 ? a : b = 5").unwrap(),
1347            [
1348                Ast::Term(Term::Value(Value::Integer(4))),
1349                Ast::Term(Term::Variable {
1350                    name: "a",
1351                    location: 4..5,
1352                }),
1353                Ast::Term(Term::Variable {
1354                    name: "b",
1355                    location: 8..9,
1356                }),
1357                Ast::Conditional {
1358                    then_len: 1,
1359                    else_len: 1,
1360                },
1361                Ast::Term(Term::Value(Value::Integer(5))),
1362                Ast::Binary {
1363                    operator: BinaryOperator::Assign,
1364                    rhs_len: 1,
1365                    location: 10..11,
1366                },
1367            ]
1368        );
1369    }
1370
1371    #[test]
1372    fn conditional_operator_is_right_associative() {
1373        assert_eq!(
1374            parse_str("5 ? 6 : 7 ? 8 : 9").unwrap(),
1375            [
1376                Ast::Term(Term::Value(Value::Integer(5))),
1377                Ast::Term(Term::Value(Value::Integer(6))),
1378                Ast::Term(Term::Value(Value::Integer(7))),
1379                Ast::Term(Term::Value(Value::Integer(8))),
1380                Ast::Term(Term::Value(Value::Integer(9))),
1381                Ast::Conditional {
1382                    then_len: 1,
1383                    else_len: 1,
1384                },
1385                Ast::Conditional {
1386                    then_len: 1,
1387                    else_len: 4,
1388                },
1389            ]
1390        );
1391    }
1392
1393    #[test]
1394    fn question_without_colon() {
1395        assert_eq!(
1396            parse_str(" 1 ? 2 + 3 "),
1397            Err(Error {
1398                cause: SyntaxError::QuestionWithoutColon {
1399                    question_location: 3..4,
1400                },
1401                location: 11..11,
1402            })
1403        );
1404        assert_eq!(
1405            parse_str("(9?8)"),
1406            Err(Error {
1407                cause: SyntaxError::QuestionWithoutColon {
1408                    question_location: 2..3,
1409                },
1410                location: 4..5,
1411            })
1412        );
1413    }
1414
1415    #[test]
1416    fn colon_without_question() {
1417        assert_eq!(
1418            parse_str(" 2 : 3 "),
1419            Err(Error {
1420                cause: SyntaxError::ColonWithoutQuestion,
1421                location: 3..4,
1422            })
1423        );
1424        assert_eq!(
1425            parse_str("(4+5-6:7)"),
1426            Err(Error {
1427                cause: SyntaxError::ColonWithoutQuestion,
1428                location: 6..7,
1429            })
1430        );
1431    }
1432
1433    #[test]
1434    fn parentheses() {
1435        assert_eq!(
1436            parse_str("(a = 0)--").unwrap(),
1437            [
1438                Ast::Term(Term::Variable {
1439                    name: "a",
1440                    location: 1..2,
1441                }),
1442                Ast::Term(Term::Value(Value::Integer(0))),
1443                Ast::Binary {
1444                    operator: BinaryOperator::Assign,
1445                    rhs_len: 1,
1446                    location: 3..4,
1447                },
1448                Ast::Postfix {
1449                    operator: PostfixOperator::Decrement,
1450                    location: 7..9,
1451                },
1452            ]
1453        );
1454    }
1455
1456    #[test]
1457    fn unmatched_parentheses() {
1458        assert_eq!(
1459            parse_str("(a + 0 "),
1460            Err(Error {
1461                cause: SyntaxError::UnclosedParenthesis {
1462                    opening_location: 0..1,
1463                },
1464                location: 7..7,
1465            })
1466        );
1467        assert_eq!(
1468            parse_str(" ((0)"),
1469            Err(Error {
1470                cause: SyntaxError::UnclosedParenthesis {
1471                    opening_location: 1..2,
1472                },
1473                location: 5..5,
1474            })
1475        );
1476    }
1477
1478    #[test]
1479    fn incomplete_expression() {
1480        assert_eq!(
1481            parse_str("   "),
1482            Err(Error {
1483                cause: SyntaxError::IncompleteExpression,
1484                location: 3..3,
1485            })
1486        );
1487        assert_eq!(
1488            parse_str("+"),
1489            Err(Error {
1490                cause: SyntaxError::IncompleteExpression,
1491                location: 1..1,
1492            })
1493        );
1494    }
1495
1496    #[test]
1497    fn invalid_operator() {
1498        assert_eq!(
1499            parse_str(" 3 ! 5"),
1500            Err(Error {
1501                cause: SyntaxError::InvalidOperator,
1502                location: 3..4,
1503            })
1504        );
1505        assert_eq!(
1506            parse_str(" 1 + 2 ~ 3 + 4 "),
1507            Err(Error {
1508                cause: SyntaxError::InvalidOperator,
1509                location: 7..8,
1510            })
1511        );
1512        assert_eq!(
1513            parse_str(" + * 3 "),
1514            Err(Error {
1515                cause: SyntaxError::InvalidOperator,
1516                location: 3..4,
1517            })
1518        );
1519    }
1520
1521    #[test]
1522    fn redundant_tokens() {
1523        assert_eq!(
1524            parse_str(" 1 22 "),
1525            Err(Error {
1526                cause: SyntaxError::MissingOperator,
1527                location: 3..5,
1528            })
1529        );
1530    }
1531}
yash_arith/ast.rs

yash_arith/
ast.rs
