OK AST fully working!!!!

4 files changed, 79 insertions, 4 deletions

diff --git a/.gitignore b/.gitignore
index f73c4f0..4c3173c 100644
--- a/.gitignore
+++ b/.gitignore
@@ -72,3 +72,4 @@ include/test.h
 src/test.cc
 test/
 .vscode/
+third_party/
diff --git a/Makefile b/Makefile
index e9c5cc0..a58f7fb 100644
--- a/Makefile
+++ b/Makefile
@@ -5,10 +5,15 @@ INCLUDE_DIR = include
 BUILD = build
 TARGET = $(BUILD)/ccshell
 
+DEPS_DIR = third_party
+MAGIC_ENUM_DIR = $(DEPS_DIR)/magic_enum
+
 MAKEFLAGS += -j8
 
 CPPFLAGS = -I$(INCLUDE_DIR) -MMD -MP -flto
 CXXFLAGS = -std=c++23 -Wall -Wextra -O3 -flto
+CPPFLAGS += -I$(MAGIC_ENUM_DIR)/include
+
 
 TARGET_OS ?= $(shell uname -s)
 
@@ -42,3 +47,13 @@ fresh:
 	make
 
 .PHONY: clean
+
+.PHONY: magic-enum
+
+magic-enum:
+	@mkdir -p $(DEPS_DIR)
+	@if [ -d "$(MAGIC_ENUM_DIR)/.git" ]; then \
+		git -C "$(MAGIC_ENUM_DIR)" pull --ff-only; \
+	else \
+		git clone --depth 1 https://github.com/Neargye/magic_enum.git "$(MAGIC_ENUM_DIR)" -b master --single-branch; \
+	fi
diff --git a/ast.cc b/ast.cc
index 4bd9e6b..b7387e4 100644
--- a/ast.cc
+++ b/ast.cc
@@ -6,6 +6,8 @@
 #include <vector>
 #include <print>
 
+#include "magic_enum/magic_enum.hpp"
+
 #include "parser/shared.h"
 #include "parser/ast.h"
 #include "parser/enum_type.h"
@@ -21,7 +23,7 @@ constexpr int MAXLINE = 1024;
 
 int main()
 {
-    int test_case = 4;
+    int test_case = 5;
     string s;
 
     switch (test_case)
@@ -39,7 +41,10 @@ int main()
             s = "hi (hello || foo)";
             break;
         case 4:
-            s = "alpha || beta (gamma && (delta || epsilon & ) )";
+            s = "alpha || beta (gamma argument && (delta || epsilon second_argument & ) )";
+            break;
+        case 5:
+            s = "alpha || beta && (gamma || epsilon)";
             break;
         default:
             return 0;
@@ -69,6 +74,15 @@ int main()
 
     cout << "---------- parse ----------" << endl;
 
-    //parse(0, token.size(), alloc_ast());
+    parse(0, token.size(), alloc_ast());
+
+    cout << "---------- AST ----------" << endl; 
+    for (size_t i = 0; i < ast.size(); i++)
+    {
+        print("{}: type: {} left: {} right: {}", i, magic_enum::enum_name(ast[i].token_type), ast[i].left, ast[i].right);
+        if (ast[i].token_type == TEXT)
+            print(" command: {}", ast[i].command_text);
+        println();
+    }
     return 0;
 }
diff --git a/include/parser/ast.h b/include/parser/ast.h
index 75c4004..05ba553 100644
--- a/include/parser/ast.h
+++ b/include/parser/ast.h
@@ -24,6 +24,19 @@ public:
     size_t right = string::npos;
 };
 
+string final_trim(size_t _begin, size_t _end)
+{
+    string s;
+    for (size_t i = _begin; i < _end; i++)
+    {
+        if (token[i].token_type != TEXT)
+            continue;
+        s += token[i].text + " ";
+    }
+    s = s.substr(0, s.size()-1); // eat final space
+    return s;
+}
+
 size_t alloc_ast()
 {
     ast.emplace_back();
@@ -65,16 +78,25 @@ bool is_operator(enum_token_type x)
     }
 }
 
+// region [begin, end)
 void parse(size_t cmd_begin, size_t cmd_end, size_t ast_vec)
 {
     int current_depth = 0;
     int current_order = -1;
+    int max_depth = -1;
     size_t found_pos = string::npos;
 
+    for (size_t i = cmd_begin; i < cmd_end; i++)
+    {
+        if (token[i].bracket_depth > max_depth)
+            max_depth = token[i].bracket_depth;
+    }
+
+
     while (found_pos == string::npos)
     {
         // scan from right to left
-        for (size_t i = cmd_end - 1; i < cmd_end; i--)
+        for (size_t i = cmd_end - 1; i >= cmd_begin && i < cmd_end; i--)
         {
             // if same depth
             // and higher order number
@@ -88,7 +110,30 @@ void parse(size_t cmd_begin, size_t cmd_end, size_t ast_vec)
             }
         }
         current_depth++;
+        if (current_depth > max_depth)
+        {
+            break;
+        }
+    }
+
+    if (found_pos == string::npos)
+    {
+        println("Smallest unit");
+        ast[ast_vec].token_type = TEXT;
+        ast[ast_vec].command_text = final_trim(cmd_begin, cmd_end);
+        return;
     }
+
+    size_t l = alloc_ast();
+    size_t r = alloc_ast();
+    ast[ast_vec].left = l;
+    ast[ast_vec].right = r;
+    ast[ast_vec].token_type = token[found_pos].token_type;
+
+    println("Parse sub: {}, {}, {}", cmd_begin, found_pos, cmd_end);
+
+    parse(cmd_begin, found_pos, l);
+    parse(found_pos+1, cmd_end, r);
 }
 
 }