Repository: Kuree/hgdb (language: python)

Issue:
Use custom parser and evaluate logic instead of exprtk
Exprtk is good but lack of the following features:
- good support for bit manipulation
- integers type, instead of floats
- fast compilation. We probably only need 1% of exprtk's functionality, yet it makes the compilation way longer than the rest of the system.

We probably just want some simple parser and can evaluate some simple expressions.


Discussion / hints:

Fix patch:
diff --git a/.gitmodules b/.gitmodules
index f4d97b6..ee811ca 100644
--- a/.gitmodules
+++ b/.gitmodules
@@ -22,9 +22,9 @@
 [submodule "extern/vlstd"]
 	path = extern/vlstd
 	url = https://github.com/Kuree/vlstd.git
-[submodule "extern/exprtk"]
-	path = extern/exprtk
-	url = https://github.com/Kuree/exprtk.git
 [submodule "bindings/python/pybind11"]
 	path = bindings/python/extern/pybind11
 	url = https://github.com/pybind/pybind11
+[submodule "extern/PEGTL"]
+	path = extern/PEGTL
+	url = https://github.com/taocpp/PEGTL
diff --git a/CMakeLists.txt b/CMakeLists.txt
index a725cd5..2557489 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -13,6 +13,7 @@ include(CheckCXXCompilerFlag)
 # extern dependencies
 add_subdirectory(extern/fmt)
 add_subdirectory(extern/sqlite)
+add_subdirectory(extern/PEGTL)
 
 # system dependencies
 set(THREADS_PREFER_PTHREAD_FLAG ON)
diff --git a/extern/PEGTL b/extern/PEGTL
new file mode 160000
index 0000000..b430a67
--- /dev/null
+++ b/extern/PEGTL
@@ -0,0 +1,1 @@
+Subproject commit b430a678b20dd2791b9696b9b42b15309f708543
diff --git a/extern/exprtk b/extern/exprtk
deleted file mode 160000
index 7c9b237..0000000
--- a/extern/exprtk
+++ /dev/null
@@ -1,1 +0,0 @@
-Subproject commit 7c9b2370f80f2145e91edfc481c916ff5d1260d7
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index bccb850..0db1aa0 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -12,7 +12,8 @@ target_include_directories(hgdb PUBLIC
         ../extern/asio/asio/include/
         ../extern/websocketpp
         ../extern/vlstd
-        ../extern/exprtk)
+        ../extern/exprtk
+        ../extern/PEGTL/include)
 
 # check if the compiler support static lib gcc
 # we need this because most
@@ -25,7 +26,7 @@ if (${COMPILER_STATIC_LIBCXX})
     set(STATIC_CXX_FLAG "-static-libstdc++")
 endif ()
 
-target_link_libraries(hgdb fmt sqlite3 Threads::Threads ${STATIC_GCC_FLAG} ${STATIC_CXX_FLAG})
+target_link_libraries(hgdb fmt sqlite3 Threads::Threads ${STATIC_GCC_FLAG} ${STATIC_CXX_FLAG} taocpp::pegtl)
 
 # check if the compiler support attributes like [[likely]]
 set(CMAKE_REQUIRED_FLAGS "-Wall -Werror")
diff --git a/src/debug.cc b/src/debug.cc
index cbc88ae..73d00d1 100644
--- a/src/debug.cc
+++ b/src/debug.cc
@@ -247,7 +247,7 @@ void Debugger::add_breakpoint(const BreakPoint &bp_info, const BreakPoint &db_bp
     // add them to the eval vector
     std::string cond = "1";
     if (!db_bp.condition.empty()) cond = db_bp.condition;
-    if (!bp_info.condition.empty()) cond.append(" and " + bp_info.condition);
+    if (!bp_info.condition.empty()) cond.append(" && " + bp_info.condition);
     log_info(fmt::format("Breakpoint inserted into {0}:{1}", db_bp.filename, db_bp.line_num));
     std::lock_guard guard(breakpoint_lock_);
     if (inserted_breakpoints_.find(db_bp.id) == inserted_breakpoints_.end()) {
diff --git a/src/eval.cc b/src/eval.cc
index abd322a..b36f4ed 100644
--- a/src/eval.cc
+++ b/src/eval.cc
@@ -1,68 +1,379 @@
 #include "eval.hh"
 
+#include <stack>
+#include <tao/pegtl.hpp>
+
 namespace hgdb {
 
-std::unique_ptr<exprtk::expression<ExpressionHelper::ExpressionType>>
-ExpressionHelper::get_expression(const std::string &expression,
-                                 exprtk::symbol_table<ExpressionHelper::ExpressionType> &table) {
-    exprtk::parser<ExpressionHelper::ExpressionType> parser;
-    auto expr = std::make_unique<exprtk::expression<ExpressionHelper::ExpressionType>>();
-    expr->register_symbol_table(table);
-    int r = parser.compile(expression, *expr);
-    if (r) {
-        return expr;
-    } else {
+// construct peg grammar
+
+namespace expr {
+
+using tao::pegtl::alpha;
+using tao::pegtl::digit;
+using tao::pegtl::eof;
+using tao::pegtl::if_must;
+using tao::pegtl::list;
+using tao::pegtl::one;
+using tao::pegtl::pad;
+using tao::pegtl::parse;
+using tao::pegtl::plus;
+using tao::pegtl::seq;
+using tao::pegtl::sor;
+using tao::pegtl::space;
+using tao::pegtl::star;
+using tao::pegtl::two;
+
+struct integer : plus<digit> {};
+struct variable_head1 : plus<sor<alpha, one<'_'>, one<'$'>>> {};
+struct variable_head2 : seq<variable_head1, star<sor<variable_head1, digit>>> {};
+struct variable_tail : if_must<one<'['>, plus<digit>, one<']'>> {};
+struct variable2 : seq<variable_head2, star<variable_tail>> {};
+struct variable : list<variable2, one<'.'>> {};
+
+struct plus_ : one<'+'> {};
+struct minus : one<'-'> {};
+struct multiply : one<'*'> {};
+struct divide : one<'/'> {};
+struct mod : one<'%'> {};
+struct eq : two<'='> {};
+struct neq : seq<one<'!'>, one<'='>> {};
+struct not_ : one<'!'> {};
+struct flip : one<'~'> {};
+struct b_and : one<'&'> {};
+struct b_or : one<'|'> {};
+struct xor_ : one<'^'> {};
+struct and_ : two<'&'> {};
+struct or_ : two<'|'> {};
+
+struct binary_op : sor<multiply, divide, xor_, and_, or_, plus_, minus, mod, eq, neq, b_and, b_or> {
+};
+struct binary_op_space : pad<binary_op, space> {};
+struct unary_op : sor<not_, flip> {};
+
+struct open_bracket : seq<one<'('>, star<space>> {};
+struct close_bracket : seq<star<space>, one<')'>> {};
+
+struct expression;
+struct bracketed : seq<open_bracket, expression, close_bracket> {};
+struct value : sor<integer, variable, bracketed> {};
+struct expression3 : seq<unary_op, expression> {};
+struct expression2 : sor<expression3, value> {};
+struct expression : list<expression2, binary_op_space> {};
+
+struct grammar : seq<expression, eof> {};
+
+// parser logic
+class ParserStack {
+public:
+    [[nodiscard]] bool push(const std::string& op_str) {
+        const static std::unordered_map<std::string, Operator> op_mapping = {
+            {"+", Operator::Add},    {"-", Operator::Minus}, {"*", Operator::Multiply},
+            {"/", Operator::Divide}, {"%", Operator::Mod},   {"==", Operator::Eq},
+            {"!=", Operator::Neq},   {"!", Operator::Not},   {"~", Operator::Invert},
+            {"&&", Operator::And},   {"^", Operator::Xor},   {"||", Operator::Or},
+            {"&", Operator::BAnd},   {"|", Operator::BOr}};
+        if (op_mapping.find(op_str) != op_mapping.end()) {
+            auto op = op_mapping.at(op_str);
+            ops_.emplace(op);
+            return true;
+        } else {
+            return false;
+        }
+    }
+    void push(Expr* expr) { exprs_.emplace(expr); }
+
+    Expr* reduce(DebugExpression& debug) {
+        // TODO implement expresion rotation to account for op priority
+        if (ops_.empty()) [[unlikely]] {
+            if (exprs_.empty()) {
+                return nullptr;
+            }
+        }
+        Expr* root = nullptr;
+        while (!ops_.empty()) {
+            auto op = ops_.top();
+            ops_.pop();
+            static const std::unordered_set<Operator> unary_ops = {Operator::Not, Operator::Invert};
+            if (unary_ops.find(op) != unary_ops.end()) {
+                // unary op
+                auto* exp = exprs_.top();
+                exprs_.pop();
+                auto* expr = debug.add_expression(op);
+                if (exp->left) {
+                    expr->unary = exp->left;
+                    exp->left = expr;
+                } else if (exp->unary) {
+                    expr->unary = exp->unary;
+                    exp->unary = expr;
+                } else {
+                    expr->unary = exp;
+                }
+                exprs_.emplace(expr);
+            } else {
+                auto* expr = debug.add_expression(op);
+                if (!root) {
+                    auto* right = exprs_.top();
+                    exprs_.pop();
+                    auto* left = exprs_.top();
+                    exprs_.pop();
+
+                    expr->left = left;
+                    expr->right = right;
+                } else {
+                    auto* top = exprs_.top();
+                    exprs_.pop();
+                    auto* leaf = top->left;
+                    auto* left = exprs_.top();
+                    exprs_.pop();
+
+                    top->left = expr;
+                    expr->right = leaf;
+                    expr->left = left;
+                }
+
+                // put it back in
+                exprs_.emplace(expr);
+
+                if (!root) {
+                    root = exprs_.top();
+                }
+            }
+        }
+        if (!root) root = exprs_.top();
+        fix_precedence(root);
+        return root;
+    }
+
+private:
+    std::stack<Operator> ops_;
+    std::stack<Expr*> exprs_;
+
+    static void fix_precedence(Expr* expr) {
+        // the map is from https://en.cppreference.com/w/c/language/operator_precedence
+        static const std::unordered_map<Operator, uint32_t> precedence{
+            {Operator::Multiply, 3}, {Operator::Divide, 3}, {Operator::Mod, 3},
+            {Operator::Add, 4},      {Operator::Minus, 4},  {Operator::Eq, 7},
+            {Operator::Neq, 7},      {Operator::BAnd, 8},   {Operator::Xor, 9},
+            {Operator::BOr, 10},     {Operator::And, 11},   {Operator::Or, 12}};
+        Expr* node = expr;
+        while (true) {
+            auto* next = node->left;
+            if (!next) break;
+            auto current_op = node->op;
+            auto next_op = next->op;
+            // if both ops exist in the map and we have low precedence before high precedence
+            // do a tree rotation
+            if (precedence.find(current_op) != precedence.end() &&
+                precedence.find(next_op) != precedence.end() &&
+                precedence.at(current_op) < precedence.at(next_op) && !next->bracketed) {
+                /*
+                 * before:                   after:
+                 *        /                             /
+                 *       A                             B
+                 *      / \                           / \
+                 *     B   C                         D   A
+                 *    / \                               / \
+                 *   D   E                             E   C
+                 *
+                 */
+                // We do everything in place
+                // first swap op
+                auto temp_op = next_op;
+                next->op = node->op;
+                node->op = temp_op;
+
+                auto* c = node->right;
+                auto* d = next->left;
+                auto* e = next->right;
+                // node is B now
+                // and next is A
+                node->left = d;
+                next->left = e;
+                next->right = c;
+                node->right = next;
+
+                next = d;
+            }
+
+            // scan the next expression node
+            node = next;
+        }
+    }
+};
+
+class ParserState {
+public:
+    explicit ParserState(DebugExpression& debug) : debug_(debug) { stacks.emplace(ParserStack{}); }
+    void push(const std::string& op) {
+        auto r = stacks.top().push(op);
+        if (!r) debug_.set_error();
+    }
+
+    void push(Expr* expr) { stacks.top().push(expr); }
+
+    void open() { stacks.emplace(ParserStack{}); }
+
+    void close() {
+        auto& stack = stacks.top();
+        auto* expr = stack.reduce(debug_);
+        expr->bracketed = true;
+        stacks.pop();
+        stacks.top().push(expr);
+    }
+
+    Expr* reduce() { return stacks.top().reduce(debug_); }
+
+    inline Symbol* add_symbol(const std::string& name) { return debug_.add_symbol(name); }
+    inline Expr* add_expression(expr::Operator op) { return debug_.add_expression(op); }
+
+private:
+    // stack of stacks
+    std::stack<ParserStack> stacks;
+
+    DebugExpression& debug_;
+};
+
+template <typename Rule>
+struct action {};
+
+template <>
+struct action<variable> {
+    template <typename ActionInput>
+    [[maybe_unused]] [[maybe_unused]] static void apply(const ActionInput& in, ParserState& state) {
+        auto name = in.string();
+        auto* symbol = state.add_symbol(name);
+        state.push(symbol);
+    }
+};
+
+template <>
+struct action<integer> {
+    template <typename ActionInput>
+    [[maybe_unused]] [[maybe_unused]] static void apply(const ActionInput& in, ParserState& state) {
+        auto* expr = state.add_expression(expr::Operator::None);
+        std::stringstream ss(in.string());
+        ExpressionType v;
+        ss >> v;
+        expr->set_value(v);
+        state.push(expr);
+    }
+};
+
+template <>
+struct action<binary_op> {
+    template <typename ActionInput>
+    [[maybe_unused]] [[maybe_unused]] static void apply(const ActionInput& in, ParserState& state) {
+        auto s = in.string();
+        state.push(s);
+    }
+};
+
+template <>
+struct action<unary_op> {
+    template <typename ActionInput>
+    [[maybe_unused]] [[maybe_unused]] static void apply(const ActionInput& in, ParserState& state) {
+        auto s = in.string();
+        state.push(s);
+    }
+};
+
+template <>
+struct action<open_bracket> {
+    template <typename ActionInput>
+    [[maybe_unused]] static void apply(const ActionInput&, ParserState& state) {
+        state.open();
+    }
+};
+
+template <>
+struct action<close_bracket> {
+    template <typename ActionInput>
+    [[maybe_unused]] static void apply(const ActionInput&, ParserState& state) {
+        state.close();
+    }
+};
+
+Expr* parse(const std::string& value, DebugExpression& debug_expression) {
+    tao::pegtl::memory_input in(value, "");
+    ParserState state(debug_expression);
+    auto r = tao::pegtl::parse<grammar, action>(in, state);
+    if (!r) {
+        debug_expression.set_error();
         return nullptr;
+    } else {
+        return state.reduce();
     }
 }
 
-std::unordered_set<std::string> ExpressionHelper::get_expr_symbols(const std::string &expression) {
-    std::unordered_set<std::string> result;
-    exprtk::lexer::generator generator;
-    generator.process(expression);
-    // copied from exprtk implementation
-    const static std::unordered_set<std::string> predefined_symbols = {
-        "and",  "nand",  "or", "nor", "xor", "xnor", "in",
-        "like", "ilike", "&",  "|",   "not", "~",    "!"};
-
-    auto size = generator.size();
-    for (auto i = 0u; i < size; i++) {
-        auto token = generator[i];
-        if (token.type == exprtk::lexer::token::token_type::e_symbol) {
-            auto val = token.value;
-            if (predefined_symbols.find(val) == predefined_symbols.end())
-                result.emplace(token.value);
-        }
+ExpressionType Expr::eval() const {
+    switch (op) {
+        case Operator::None:
+            return value_;
+        case Operator::Add:
+            return left->eval() + right->eval();
+        case Operator::Minus:
+            return left->eval() - right->eval();
+        case Operator::Multiply:
+            return left->eval() * right->eval();
+        case Operator::Divide:
+            return left->eval() / right->eval();
+        case Operator::Mod:
+            return left->eval() % right->eval();
+        case Operator::Eq:
+            return left->eval() == right->eval();
+        case Operator::Neq:
+            return left->eval() != right->eval();
+        case Operator::Not:
+            return !unary->eval();
+        case Operator::Invert:
+            return ~unary->eval();
+        case Operator::And:
+            return left->eval() && right->eval();
+        case Operator::Xor:
+            return left->eval() ^ right->eval();
+        case Operator::Or:
+            return left->eval() || right->eval();
+        case Operator::BAnd:
+            return left->eval() & right->eval();
+        case Operator::BOr:
+            return left->eval() | right->eval();
     }
-    return result;
+    return 0;
+}
+
+}  // namespace expr
+
+DebugExpression::DebugExpression(const std::string& expression) : expression_(expression) {
+    root_ = expr::parse(expression, *this);
+}
+
+expr::Expr* DebugExpression::add_expression(expr::Operator op) {
+    auto expr = std::make_unique<expr::Expr>(op);
+    expressions_.emplace_back(std::move(expr));
+    return expressions_.back().get();
 }
 
-DebugExpression::DebugExpression(const std::string &expression) : expression_(expression) {
-    symbols_ = ExpressionHelper::get_expr_symbols(expression_);
-    for (auto const &name : symbols_) {
-        symbol_table_.emplace(name, 0);
-        exprtk_table_.add_variable(name, symbol_table_.at(name));
+expr::Symbol* DebugExpression::add_symbol(const std::string& name) {
+    if (symbols_str_.find(name) == symbols_str_.end()) {
+        symbols_str_.emplace(name);
+        expressions_.emplace_back(std::make_unique<expr::Symbol>(name));
+        auto* ptr = reinterpret_cast<expr::Symbol*>(expressions_.back().get());
+        symbols_.emplace(name, ptr);
     }
-    // notice that we actually lex the expression twice here
-    expr_ = ExpressionHelper::get_expression(expression, exprtk_table_);
+
+    return symbols_.at(name);
 }
 
-int64_t DebugExpression::eval(const std::unordered_map<std::string, int64_t> &values) {
-    if (!correct()) return 0;
-    uint64_t hit = 0;
-    for (auto const &[name, value] : values) {
+int64_t DebugExpression::eval(const std::unordered_map<std::string, int64_t>& symbol_value) {
+    if (!root_) [[unlikely]]
+        return 0;
+    for (auto const& [name, value] : symbol_value) {
         if (symbols_.find(name) != symbols_.end()) [[likely]] {
-            hit++;
-            symbol_table_[name] = value;
+            symbols_.at(name)->set_value(value);
         }
     }
-    if (hit != symbols_.size()) {
-        // some values are missing
-        return 0;
-    } else {
-        auto result = expr_->value();
-        return static_cast<int64_t>(result);
-    }
+    return root_->eval();
 }
 
 }  // namespace hgdb
\ No newline at end of file
diff --git a/src/eval.hh b/src/eval.hh
index c35b310..9b10632 100644
--- a/src/eval.hh
+++ b/src/eval.hh
@@ -1,29 +1,75 @@
 #ifndef HGDB_EVAL_HH
 #define HGDB_EVAL_HH
 
-#include <exprtk.hpp>
 #include <memory>
 #include <unordered_map>
 #include <unordered_set>
+#include <vector>
 
 namespace hgdb {
 
-class ExpressionHelper {
+using ExpressionType = int64_t;
+
+namespace expr {
+enum class Operator {
+    None,
+    Add,
+    Minus,
+    Multiply,
+    Divide,
+    Mod,
+    Eq,
+    Neq,
+    Not,
+    Invert,
+    And,
+    Xor,
+    Or,
+    BAnd,
+    BOr
+};
+class Expr {
 public:
-    // exprtk requires to use floats
-    using ExpressionType = double;
-    static std::unique_ptr<exprtk::expression<ExpressionType>> get_expression(
-        const std::string &expression,
-        exprtk::symbol_table<ExpressionHelper::ExpressionType> &table);
-    static std::unordered_set<std::string> get_expr_symbols(const std::string &expression);
+    Expr(Operator op) : op(op), value_(0) {}
+    void set_value(ExpressionType value) { value_ = value; }
+
+    Expr *left = nullptr;
+    Expr *right = nullptr;
+    Expr *unary = nullptr;
+
+    Operator op = Operator::None;
+    bool bracketed = false;
+
+    [[nodiscard]] ExpressionType eval() const;
+
+private:
+    ExpressionType value_;
 };
 
+class Symbol : public Expr {
+public:
+    Symbol(std::string name) : Expr(Operator::None), name(std::move(name)) {}
+    std::string name;
+};
+}  // namespace expr
+
 class DebugExpression {
 public:
     explicit DebugExpression(const std::string &expression);
-    [[nodiscard]] const std::unordered_set<std::string> &symbols() const { return symbols_; }
-    int64_t eval(const std::unordered_map<std::string, int64_t> &values);
-    [[nodiscard]] bool correct() const { return expr_ != nullptr; }
+
+    // symbol table related functions
+    [[nodiscard]] const std::unordered_set<std::string> &symbols() const { return symbols_str_; }
+    [[nodiscard]] uint64_t size() const { return symbols_str_.size(); }
+    auto find(const std::string &value) const { return symbols_str_.find(value); }
+    auto end() const { return symbols_str_.end(); }
+    [[nodiscard]] bool empty() const { return symbols_str_.empty(); }
+    int64_t eval(const std::unordered_map<std::string, int64_t> &symbol_value);
+    [[nodiscard]] bool correct() const { return correct_ && root_ != nullptr; }
+    void set_error() { correct_ = false; }
+    [[nodiscard]] const expr::Expr *root() const { return root_; }
+
+    expr::Expr *add_expression(expr::Operator op);
+    expr::Symbol *add_symbol(const std::string &name);
 
     // no copy construction
     DebugExpression(const DebugExpression &) = delete;
@@ -32,11 +78,14 @@ public:
 
 private:
     std::string expression_;
-    std::unordered_set<std::string> symbols_;
-    std::unordered_map<std::string, ExpressionHelper::ExpressionType> symbol_table_;
+    // only for strings for fast access during evaluation
+    std::unordered_set<std::string> symbols_str_;
+    std::unordered_map<std::string, expr::Symbol *> symbols_;
+
+    std::vector<std::unique_ptr<expr::Expr>> expressions_;
 
-    std::unique_ptr<exprtk::expression<ExpressionHelper::ExpressionType>> expr_;
-    exprtk::symbol_table<ExpressionHelper::ExpressionType> exprtk_table_;
+    bool correct_ = true;
+    expr::Expr *root_ = nullptr;
 };
 
 }  // namespace hgdb


Test patch:
diff --git a/tests/generators/test_kratos.py b/tests/generators/test_kratos.py
index d05b74f..b44e663 100644
--- a/tests/generators/test_kratos.py
+++ b/tests/generators/test_kratos.py
@@ -95,7 +95,7 @@ async def client_logic():
                 await client.recv()
                 # remove the current breakpoint
                 await client.remove_breakpoint(py_filename, py_line_num)
-                await client.set_breakpoint(py_filename, py_line_num, cond="out == 6 and i == 3")
+                await client.set_breakpoint(py_filename, py_line_num, cond="out == 6 && i == 3")
                 await client.continue_()
                 bp = await client.recv()
                 assert bp["payload"]["instances"][0]["local"]["out"] == "6"
diff --git a/tests/test_debug_server.cc b/tests/test_debug_server.cc
index 0244ea8..e53ca19 100644
--- a/tests/test_debug_server.cc
+++ b/tests/test_debug_server.cc
@@ -105,7 +105,7 @@ auto setup_db_vpi(MockVPIProvider &vpi) {
         store_breakpoint(*db, 0 + base_id, dut_id, filename, 2, 0, "a");
         store_context_variable(*db, "a", 0 + base_id, variable_ids.at("a"));
         // assign c_1 = 0;  // a = a  en: ~a          -> c = 0
-        store_breakpoint(*db, 1 + base_id, dut_id, filename, 4, 0, "~a");
+        store_breakpoint(*db, 1 + base_id, dut_id, filename, 4, 0, "!a");
         store_context_variable(*db, "a", 1 + base_id, variable_ids.at("a"));
         // assign c_2 = a? c_0: c_1; // a = a en: 1   -> if (a)
         store_breakpoint(*db, 2 + base_id, dut_id, filename, 1, 0, "1");
diff --git a/tests/test_eval.cc b/tests/test_eval.cc
index b0c3298..64437c9 100644
--- a/tests/test_eval.cc
+++ b/tests/test_eval.cc
@@ -1,27 +1,106 @@
 #include "../src/eval.hh"
 #include "gtest/gtest.h"
 
-TEST(eval, get_tokens) {    // NOLINT
-    const auto *expr = "a + b - c";
-    auto tokens = hgdb::ExpressionHelper::get_expr_symbols(expr);
-    EXPECT_EQ(tokens.size(), 3);
-    for (auto const &s: {"a", "b", "c"}) {
-        EXPECT_NE(tokens.find(s), tokens.end());
+TEST(expr, symbol_parse) {  // NOLINT
+    auto legal_symbols = {"a[0]", "a[0][0]", "__a", "$a", "a.b", "a0", "a[0].b", "a.b[0]", "a0$b0"};
+    for (auto const *expr : legal_symbols) {
+        hgdb::DebugExpression debug_expr(expr);
+        EXPECT_TRUE(debug_expr.correct());
+        EXPECT_EQ(debug_expr.size(), 1);
+        EXPECT_NE(debug_expr.find(expr), debug_expr.end());
     }
+    // test illegal legal_symbols
+    auto illegal_symbols = {"0a", "="};
+    for (auto const *expr : illegal_symbols) {
+        hgdb::DebugExpression debug_expr(expr);
+        EXPECT_FALSE(debug_expr.correct());
+        EXPECT_TRUE(debug_expr.empty());
+    }
+
+    // test (symbol)
+    hgdb::DebugExpression debug_expr_("(a)");
+    EXPECT_TRUE(debug_expr_.correct());
+    EXPECT_EQ(debug_expr_.size(), 1);
+    EXPECT_NE(debug_expr_.find("a"), debug_expr_.end());
+}
+
+TEST(expr, expr_parse) {  // NOLINT
+    const hgdb::expr::Expr *expr;
+    auto const *expr1 = "1 + 2 * 3";
+    hgdb::DebugExpression debug_expr1(expr1);
+    EXPECT_TRUE(debug_expr1.correct());
+    expr = debug_expr1.root();
+    EXPECT_EQ(expr->op, hgdb::expr::Operator::Add);
+
+    auto const *expr2 = "a * (b + c)";
+    hgdb::DebugExpression debug_expr2(expr2);
+    EXPECT_TRUE(debug_expr2.correct());
+    expr = debug_expr2.root();
+    EXPECT_EQ(expr->op, hgdb::expr::Operator::Multiply);
+
+    auto const *expr3 = "!a";
+    hgdb::DebugExpression debug_expr3(expr3);
+    EXPECT_TRUE(debug_expr3.correct());
+    expr = debug_expr3.root();
+    EXPECT_EQ(expr->op, hgdb::expr::Operator::Not);
+
+    auto const *expr4 = "!a == 1";
+    hgdb::DebugExpression debug_expr4(expr4);
+    EXPECT_TRUE(debug_expr4.correct());
+    expr = debug_expr4.root();
+    EXPECT_EQ(expr->op, hgdb::expr::Operator::Eq);
 }
 
-TEST(eval, eval_expr) { // NOLINT
-    const auto *expr_str = "a == 5 and b == 6";
-    auto expr = hgdb::DebugExpression(expr_str);
-    EXPECT_EQ(expr.symbols().size(), 2);
-    std::unordered_map<std::string, int64_t> values{{"a", 5}, {"b", 6}};
-    auto v = expr.eval(values);
-    EXPECT_EQ(v, 1);
-    values["a"] = 4;
-    v = expr.eval(values);
-    EXPECT_EQ(v, 0);
-    // missing args
-    values.erase("a");
-    v = expr.eval(values);
-    EXPECT_EQ(v, 0);
+TEST(expr, expr_eval) {  // NOLINT
+    hgdb::ExpressionType result;
+
+    auto const *expr1 = "1";
+    hgdb::DebugExpression debug_expr1(expr1);
+    EXPECT_TRUE(debug_expr1.correct());
+    result = debug_expr1.eval({});
+    EXPECT_EQ(result, 1);
+
+    auto const *expr2 = "1 + a";
+    hgdb::DebugExpression debug_expr2(expr2);
+    EXPECT_TRUE(debug_expr2.correct());
+    result = debug_expr2.eval({{"a", 41}});
+    EXPECT_EQ(result, 42);
+
+    auto const *expr3 = "a == 42";
+    hgdb::DebugExpression debug_expr3(expr3);
+    EXPECT_TRUE(debug_expr3.correct());
+    result = debug_expr3.eval({{"a", 42}});
+    EXPECT_EQ(result, 1);
+
+    auto const *expr4 = "a==42&&b==1";  // no space
+    hgdb::DebugExpression debug_expr4(expr4);
+    EXPECT_TRUE(debug_expr4.correct());
+    result = debug_expr4.eval({{"a", 42}, {"b", 1}});
+    EXPECT_EQ(result, 1);
+    result = debug_expr4.eval({{"a", 42}, {"b", 2}});
+    EXPECT_EQ(result, 0);
+
+    auto const *expr5 = "a + b * c - d % e";  // test tree rotate
+    hgdb::DebugExpression debug_expr5(expr5);
+    EXPECT_TRUE(debug_expr5.correct());
+    result = debug_expr5.eval({{"a", 1}, {"b", 2}, {"c", 4}, {"d", 5}, {"e", 3}});
+    EXPECT_EQ(result, 1 + 2 * 4 - 5 % 3);
+
+    auto const *expr6 = "(a + b) * (c - d) % e";  // with brackets
+    hgdb::DebugExpression debug_expr6(expr6);
+    EXPECT_TRUE(debug_expr6.correct());
+    result = debug_expr6.eval({{"a", 1}, {"b", 2}, {"c", 4}, {"d", 5}, {"e", 3}});
+    EXPECT_EQ(result, (1 + 2) * (4 - 5) % 3);
+
+    auto const *expr7 = "!a && b && ~c";
+    hgdb::DebugExpression debug_expr7(expr7);
+    EXPECT_TRUE(debug_expr7.correct());
+    result = debug_expr7.eval({{"a", 0}, {"b", 1}, {"c", 0}});
+    EXPECT_EQ(result, 1);
+
+    auto const *expr8 = "!!a && (~~a)";
+    hgdb::DebugExpression debug_expr8(expr8);
+    EXPECT_TRUE(debug_expr8.correct());
+    result = debug_expr8.eval({{"a", 1}});
+    EXPECT_EQ(result, 1);
 }
\ No newline at end of file