From 372064af20a456989c2a9ea2fda6e535d74dbafd Mon Sep 17 00:00:00 2001
From: Egor Tensin <Egor.Tensin@gmail.com>
Date: Mon, 30 Dec 2019 13:06:13 +0300
Subject: support the power (^) operator

It doesn't work with the unary minus currently (as is reflected in the
tests), it should have a higher precedence.
---
 server/lexer/token_type.cpp |  1 +
 server/lexer/token_type.hpp |  1 +
 server/parser/operator.hpp  | 27 +++++++++++++++++++++++++++
 server/parser/parser.hpp    | 12 +++++++++++-
 test/unit_tests/lexer.cpp   | 10 ++++++++++
 test/unit_tests/parser.cpp  |  8 ++++++++
 6 files changed, 58 insertions(+), 1 deletion(-)

diff --git a/server/lexer/token_type.cpp b/server/lexer/token_type.cpp
index cafb403..6a42a3d 100644
--- a/server/lexer/token_type.cpp
+++ b/server/lexer/token_type.cpp
@@ -35,6 +35,7 @@ private:
             {Type::MINUS, "-"},
             {Type::ASTERISK, "*"},
             {Type::SLASH, "/"},
+            {Type::CARET, "^"},
             {Type::LEFT_PAREN, "("},
             {Type::RIGHT_PAREN, ")"},
             {Type::NUMBER, "number"},
diff --git a/server/lexer/token_type.hpp b/server/lexer/token_type.hpp
index fba2abb..2040d28 100644
--- a/server/lexer/token_type.hpp
+++ b/server/lexer/token_type.hpp
@@ -18,6 +18,7 @@ enum class Type {
     MINUS,
     ASTERISK,
     SLASH,
+    CARET,
     LEFT_PAREN,
     RIGHT_PAREN,
     NUMBER,
diff --git a/server/parser/operator.hpp b/server/parser/operator.hpp
index f1c24de..86b9eb1 100644
--- a/server/parser/operator.hpp
+++ b/server/parser/operator.hpp
@@ -10,6 +10,8 @@
 #include "../lexer/token.hpp"
 #include "../lexer/token_type.hpp"
 
+#include <cmath>
+
 namespace math::server::parser {
 
 class BinaryOp {
@@ -23,6 +25,7 @@ public:
             case Type::MINUS:
             case Type::ASTERISK:
             case Type::SLASH:
+            case Type::CARET:
                 return true;
 
             default:
@@ -49,25 +52,49 @@ public:
             case Type::SLASH:
                 return min_precedence() + 1;
 
+            case Type::CARET:
+                return min_precedence() + 2;
+
             default:
                 throw ParserError{"internal: undefined operator precedence"};
         }
     }
 
+    bool is_right_associative() const {
+        switch (m_type) {
+            case Type::CARET:
+                return true;
+
+            default:
+                return false;
+        }
+    }
+
+    bool is_left_associative() const {
+        return !is_right_associative();
+    }
+
     double exec(double lhs, double rhs) const {
         switch (m_type) {
             case Type::PLUS:
                 return lhs + rhs;
+
             case Type::MINUS:
                 return lhs - rhs;
+
             case Type::ASTERISK:
                 return lhs * rhs;
+
             case Type::SLASH:
                 // Trapping the CPU would be better?
                 if (rhs == 0.) {
                     throw ParserError{"division by zero"};
                 }
                 return lhs / rhs;
+
+            case Type::CARET:
+                return std::pow(lhs, rhs);
+
             default:
                 throw ParserError{"internal: unsupported operator"};
         }
diff --git a/server/parser/parser.hpp b/server/parser/parser.hpp
index ac87fbe..596f84f 100644
--- a/server/parser/parser.hpp
+++ b/server/parser/parser.hpp
@@ -45,7 +45,17 @@ private:
             m_lexer.drop_token();
             auto rhs = exec_primary();
 
-            for (op = peek_operator(); op.has_value() && op->get_precedence() > lhs_op.get_precedence(); op = peek_operator()) {
+            for (op = peek_operator(); op.has_value(); op = peek_operator()) {
+                const auto op_prec = op->get_precedence();
+                const auto lhs_prec = lhs_op.get_precedence();
+                const auto ok_left_assoc = op->is_left_associative() && op_prec > lhs_prec;
+                const auto ok_right_assoc = op->is_right_associative() && op_prec == lhs_prec;
+                const auto ok = ok_left_assoc || ok_right_assoc;
+
+                if (!ok) {
+                    break;
+                }
+
                 rhs = exec_expr(rhs, op->get_precedence());
             }
 
diff --git a/test/unit_tests/lexer.cpp b/test/unit_tests/lexer.cpp
index aa4011c..0f65979 100644
--- a/test/unit_tests/lexer.cpp
+++ b/test/unit_tests/lexer.cpp
@@ -53,6 +53,7 @@ BOOST_AUTO_TEST_CASE(test_parse_const_token) {
     // parse_* functions only consume a single token:
     BOOST_TEST(details::parse_const_token("+/*").value() == Type::PLUS);
     BOOST_TEST(details::parse_const_token("-").value() == Type::MINUS);
+    BOOST_TEST(details::parse_const_token("^^").value() == Type::CARET);
     BOOST_TEST(!details::parse_const_token("&+").has_value());
 }
 
@@ -63,6 +64,7 @@ const std::vector<std::string_view> input{
     "",
     " + - ",
     "1+2",
+    ".5^-1 ^ 4",
     "1+2 *  (3- 4e-2)",
     " 2 * (1 + 3 * (1 - -3)) ",
 };
@@ -92,6 +94,14 @@ const std::vector<Expected> expected{
         Token{Type::PLUS},
         Token{2},
     }},
+    {{
+        Token{.5},
+        Token{Type::CARET},
+        Token{Type::MINUS},
+        Token{1},
+        Token{Type::CARET},
+        Token{4},
+    }},
     {{
         Token{1},
         Token{Type::PLUS},
diff --git a/test/unit_tests/parser.cpp b/test/unit_tests/parser.cpp
index 562c6b7..37d9e0a 100644
--- a/test/unit_tests/parser.cpp
+++ b/test/unit_tests/parser.cpp
@@ -30,6 +30,10 @@ const std::vector<std::string_view> input{
     " 2 * (1 + 3) ",
     " 2 * (1 + 3 * (1 - -3)) ",
     " -2 * ---- (3 + -100e-1)  ", // Looks weird, but also works in e.g. Python
+    "2 ^ 3 ^ 3",
+    "(2 ^ 3) ^ 3", // Power operator is right-associative
+    "(.5 ^ -1) ^ 4",
+    ".5 ^ -1 ^ 4", // Power operator has higher precedence than the unary minus
 };
 
 const std::vector<double> expected{
@@ -39,6 +43,10 @@ const std::vector<double> expected{
     8,
     26,
     14,
+    134217728,
+    512,
+    16,
+    2,
 };
 
 }
-- 
cgit v1.2.3