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

yash_arith/
ast.rs
