[PATCH olang v0] proposal: checker: set the eval type at the binary op expression

[PATCH olang v0] proposal: checker: set the eval type at the binary op expression

[Carlos Maniero]

I'm sending this patch to discuss how we can prepare our AST to handle
typing errors and to improve our codegen.

NOTICE: This is not a patch that should be applied; this is a proposal
so that we can understand what works or not and which path we will
follow.

ISSUE STATEMENT
===============

In my previous patchset, I had to identify what was the return type of a
deref operator (*), the main issue is, if I have a pointer of type
(u8**), if it is dereferenced one, it returns the type "u8*" if it is
dereferenced twice, it returns (u8).

But our AST does not provide this information, meaning that the codegen
needs to handle this logic.

MY PROPOSAL
===========

To add an new attribute on all the <expression> called *eval_type*, this
attribute will hold the type that the expression will produce.

Why?
----

- It simplifies the codegen
- There is a need to know the expressions result anyway for type
  checking.

HOW CLANG HANDLES IT?
=====================

I wrote the follow program in c:

int main() {
  return 1 + 2;
}

The AST was the following:

  `-FunctionDecl 0x55fb061d90f8 </tmp/a.c:1:1, line:3:1> line:1:5 main 'int ()'
    `-CompoundStmt 0x55fb061d9258 <col:12, line:3:1>
      `-ReturnStmt 0x55fb061d9248 <line:2:3, col:14>
        `-BinaryOperator 0x55fb061d9228 <col:10, col:14> 'int' '+'
          |-IntegerLiteral 0x55fb061d91e8 <col:10> 'int' 1
          `-IntegerLiteral 0x55fb061d9208 <col:14> 'int' 2

If you take a closer look at the BinaryyOperator, you will see it
specifies the operation result 'int'

        `-BinaryOperator 0x55fb061d9228 <col:10, col:14> 'int' '+'

ALTERNATIVES:
=============

- Make all ast_node_t to have an eval type.
  - This will require nodes like fn_def, translation_unit, if, while to
    have void eval_type, since they do not result anything. But this is
    confusing to have a function that has a "return_type" but doesn't
    have an "eval_type".

CONSIDERATIONS:
===============

1) I don't like the term eval_type, alternatives: result_type,
   expr_type.
2) We can use the populate_scope to make this as per my commit does,
   I like it because it does not require traversing the AST twice,
   although the name populate_scope no longer makes sense.

Signed-off-by: Carlos Maniero <carlos@maniero.me>
---
 src/ast.h                                  |  1 +
 src/checker.c                              | 53 ++++++++++++++--------
 src/codegen_x86_64.c                       |  3 ++
 src/main.c                                 |  3 ++
 src/pretty_print_ast.c                     |  8 +++-
 src/type.c                                 | 14 ++++++
 src/type.h                                 |  4 ++
 tests/olc/0002_binary_operator_addition.ol | 11 +++++
 tests/olc/0028_function_call.ol            |  2 +-
 tests/olc/0030_while_statement.ol          |  2 +-
 10 files changed, 80 insertions(+), 21 deletions(-)

diff --git a/src/ast.h b/src/ast.h
index e7d8ed8..7992045 100644
--- a/src/ast.h
+++ b/src/ast.h
@@ -146,6 +146,7 @@ typedef struct ast_binary_op
 {
     ast_node_meta_t meta;
     ast_binary_op_kind_t kind;
+    type_t *eval_type;
     ast_node_t *lhs;
     ast_node_t *rhs;
 } ast_binary_op_t;
diff --git a/src/checker.c b/src/checker.c
index 02341cc..90117d0 100644
--- a/src/checker.c
+++ b/src/checker.c
@@ -21,7 +21,10 @@
 #include <stdio.h>
 
 static void
-populate_scope(checker_t *checker, scope_t *scope, ast_node_t *ast);
+populate_scope(checker_t *checker,
+               scope_t *scope,
+               ast_node_t *ast,
+               type_t *eval_type);
 
 checker_t *
 checker_new(arena_t *arena)
@@ -86,6 +89,7 @@ type_resolve(type_t *type)
         case TYPE_PTR:
             type_resolve(type->as_ptr.type);
         case TYPE_PRIMITIVE:
+        case TYPE_VOID:
             break;
     }
 }
@@ -97,13 +101,16 @@ checker_check(checker_t *checker, ast_node_t *ast)
     assert(ast);
 
     scope_t *scope = scope_new(checker->arena);
-    populate_scope(checker, scope, ast);
+    populate_scope(checker, scope, ast, type_void());
 
     // TODO: traverse the ast tree to verify semantics
 }
 
 static void
-populate_scope(checker_t *checker, scope_t *scope, ast_node_t *ast)
+populate_scope(checker_t *checker,
+               scope_t *scope,
+               ast_node_t *ast,
+               type_t *eval_type)
 {
     assert(checker);
     assert(scope);
@@ -113,7 +120,8 @@ populate_scope(checker_t *checker, scope_t *scope, ast_node_t *ast)
             list_item_t *item = list_head(ast->as_translation_unit.decls);
 
             while (item != NULL) {
-                populate_scope(checker, scope, (ast_node_t *)item->value);
+                populate_scope(
+                    checker, scope, (ast_node_t *)item->value, eval_type);
                 item = list_next(item);
             }
             return;
@@ -124,8 +132,10 @@ populate_scope(checker_t *checker, scope_t *scope, ast_node_t *ast)
             fn_def->scope = scope_push(scope);
 
             type_resolve(fn_def->return_type);
+
             symbol_t *symbol =
                 symbol_new(checker->arena, fn_def->id, fn_def->return_type);
+
             scope_insert(scope, symbol);
 
             list_item_t *item = list_head(fn_def->params);
@@ -142,7 +152,10 @@ populate_scope(checker_t *checker, scope_t *scope, ast_node_t *ast)
             }
 
             if (ast->as_fn_def.block != NULL) {
-                populate_scope(checker, fn_def->scope, ast->as_fn_def.block);
+                populate_scope(checker,
+                               fn_def->scope,
+                               ast->as_fn_def.block,
+                               fn_def->return_type);
             }
             return;
         }
@@ -153,7 +166,8 @@ populate_scope(checker_t *checker, scope_t *scope, ast_node_t *ast)
             list_item_t *item = list_head(ast->as_fn_call.args);
 
             while (item != NULL) {
-                populate_scope(checker, scope, (ast_node_t *)item->value);
+                populate_scope(
+                    checker, scope, (ast_node_t *)item->value, eval_type);
                 item = list_next(item);
             }
 
@@ -161,42 +175,44 @@ populate_scope(checker_t *checker, scope_t *scope, ast_node_t *ast)
         }
 
         case AST_NODE_IF_STMT: {
-            populate_scope(checker, scope, ast->as_if_stmt.cond);
-            populate_scope(checker, scope, ast->as_if_stmt.then);
+            populate_scope(checker, scope, ast->as_if_stmt.cond, eval_type);
+            populate_scope(checker, scope, ast->as_if_stmt.then, eval_type);
 
             if (ast->as_if_stmt._else) {
-                populate_scope(checker, scope, ast->as_if_stmt._else);
+                populate_scope(
+                    checker, scope, ast->as_if_stmt._else, eval_type);
             }
 
             return;
         }
 
         case AST_NODE_WHILE_STMT: {
-            populate_scope(checker, scope, ast->as_while_stmt.cond);
-            populate_scope(checker, scope, ast->as_while_stmt.then);
+            populate_scope(checker, scope, ast->as_while_stmt.cond, eval_type);
+            populate_scope(checker, scope, ast->as_while_stmt.then, eval_type);
 
             return;
         }
 
         case AST_NODE_BINARY_OP: {
-            ast_binary_op_t bin_op = ast->as_bin_op;
+            ast->as_bin_op.eval_type = eval_type;
+            assert(eval_type);
 
-            populate_scope(checker, scope, bin_op.lhs);
-            populate_scope(checker, scope, bin_op.rhs);
+            populate_scope(checker, scope, ast->as_bin_op.lhs, eval_type);
+            populate_scope(checker, scope, ast->as_bin_op.rhs, eval_type);
             return;
         }
 
         case AST_NODE_UNARY_OP: {
             ast_unary_op_t unary_op = ast->as_unary_op;
 
-            populate_scope(checker, scope, unary_op.expr);
+            populate_scope(checker, scope, unary_op.expr, eval_type);
             return;
         }
 
         case AST_NODE_RETURN_STMT: {
             ast_return_stmt_t return_stmt = ast->as_return_stmt;
 
-            populate_scope(checker, scope, return_stmt.expr);
+            populate_scope(checker, scope, return_stmt.expr, eval_type);
             return;
         }
 
@@ -207,7 +223,8 @@ populate_scope(checker_t *checker, scope_t *scope, ast_node_t *ast)
             list_item_t *item = list_head(block.nodes);
 
             while (item != NULL) {
-                populate_scope(checker, scope, (ast_node_t *)item->value);
+                populate_scope(
+                    checker, scope, (ast_node_t *)item->value, eval_type);
                 item = list_next(item);
             }
 
@@ -225,7 +242,7 @@ populate_scope(checker_t *checker, scope_t *scope, ast_node_t *ast)
             scope_insert(scope, symbol);
             ast->as_var_def.scope = scope;
 
-            populate_scope(checker, scope, ast->as_var_def.value);
+            populate_scope(checker, scope, ast->as_var_def.value, eval_type);
             return;
         }
 
diff --git a/src/codegen_x86_64.c b/src/codegen_x86_64.c
index 4213571..3361510 100644
--- a/src/codegen_x86_64.c
+++ b/src/codegen_x86_64.c
@@ -913,6 +913,9 @@ type_to_bytes(type_t *type)
             assert(0 && "cannot calculate size of an unknown type: probably a "
                         "parser issue.");
         }
+        case TYPE_VOID: {
+            return 0;
+        }
     }
 
     assert(0 && "unreachable");
diff --git a/src/main.c b/src/main.c
index 685d8ce..08a0918 100644
--- a/src/main.c
+++ b/src/main.c
@@ -116,6 +116,9 @@ handle_dump_ast(cli_opts_t *opts)
 
     ast_node_t *ast = parser_parse_translation_unit(&parser);
 
+    checker_t *checker = checker_new(&arena);
+    checker_check(checker, ast);
+
     pretty_print_ast(ast);
 }
 
diff --git a/src/pretty_print_ast.c b/src/pretty_print_ast.c
index d476370..258e040 100644
--- a/src/pretty_print_ast.c
+++ b/src/pretty_print_ast.c
@@ -318,7 +318,13 @@ ast_node_to_pretty_print_node(ast_node_t *ast, arena_t *arena)
 
             switch (binop.kind) {
                 case AST_BINOP_ADDITION: {
-                    node->name = "Binary_Operation (+)";
+                    char name[256];
+                    sprintf(name,
+                            "Binary_Operation (+) <type:" SV_FMT ">",
+                            SV_ARG(ast->as_bin_op.eval_type->id));
+                    node->name = (char *)arena_alloc(
+                        arena, sizeof(char) * (strlen(name) + 1));
+                    strcpy(node->name, name);
                     break;
                 }
                 case AST_BINOP_SUBTRACTION: {
diff --git a/src/type.c b/src/type.c
index 4a8d6f4..241e57c 100644
--- a/src/type.c
+++ b/src/type.c
@@ -17,6 +17,9 @@
 #include "type.h"
 #include "assert.h"
 
+char *void_str = "void";
+type_t global_void_type;
+
 type_t *
 type_new_unknown(arena_t *arena, string_view_t id)
 {
@@ -39,3 +42,14 @@ type_new_ptr(arena_t *arena, string_view_t id, type_t *ref_type)
     type->as_ptr.type = ref_type;
     return type;
 }
+
+type_t *
+type_void()
+{
+    if (global_void_type.id.chars != void_str) {
+        global_void_type.id.chars = void_str;
+        global_void_type.id.size = 4;
+        global_void_type.kind = TYPE_VOID;
+    }
+    return &global_void_type;
+}
diff --git a/src/type.h b/src/type.h
index d930a88..e4bf078 100644
--- a/src/type.h
+++ b/src/type.h
@@ -24,6 +24,7 @@ typedef union type type_t;
 typedef enum
 {
     TYPE_UNKNOWN,
+    TYPE_VOID,
     TYPE_PRIMITIVE,
     TYPE_PTR
 } type_kind_t;
@@ -72,6 +73,9 @@ typedef union type
 type_t *
 type_new_unknown(arena_t *arena, string_view_t id);
 
+type_t *
+type_void();
+
 type_t *
 type_new_ptr(arena_t *arena, string_view_t id, type_t *type);
 #endif
diff --git a/tests/olc/0002_binary_operator_addition.ol b/tests/olc/0002_binary_operator_addition.ol
index e408b47..c66f2e8 100644
--- a/tests/olc/0002_binary_operator_addition.ol
+++ b/tests/olc/0002_binary_operator_addition.ol
@@ -19,4 +19,15 @@ fn main(): u32 {
 }
 
 # TEST test_compile(exit_code=0)
+
 # TEST test_run_binary(exit_code=21)
+
+# TEST test_ast WITH
+# Translation_Unit
+# `-Function_Definition <name:main> <return:u32>
+#   `-Block
+#     `-Return_Statement
+#       `-Binary_Operation (+) <type:u32>
+#         |-Literal <kind:u32> <value:10>
+#         `-Literal <kind:u32> <value:11>
+# END
diff --git a/tests/olc/0028_function_call.ol b/tests/olc/0028_function_call.ol
index b32fbbf..1bd6ad9 100644
--- a/tests/olc/0028_function_call.ol
+++ b/tests/olc/0028_function_call.ol
@@ -38,7 +38,7 @@ fn add(a: u32, b: u64): u8 {
 #   |-Param_Definition <name:b> <type:u64>
 #   `-Block
 #     `-Return_Statement
-#       `-Binary_Operation (+)
+#       `-Binary_Operation (+) <type:u8>
 #         |-Reference <name:a>
 #         `-Reference <name:b>
 # END
diff --git a/tests/olc/0030_while_statement.ol b/tests/olc/0030_while_statement.ol
index 0ce0185..09ba7bd 100644
--- a/tests/olc/0030_while_statement.ol
+++ b/tests/olc/0030_while_statement.ol
@@ -40,7 +40,7 @@ fn main(): u32 {
 #     | `-Block
 #     |   `-Binary_Operation (=)
 #     |     |-Reference <name:i>
-#     |     `-Binary_Operation (+)
+#     |     `-Binary_Operation (+) <type:u32>
 #     |       |-Reference <name:i>
 #     |       `-Literal <kind:u32> <value:1>
 #     `-Return_Statement
-- 
2.46.1

[olang/patches/.build.yml] build success

[builds.sr.ht]

olang/patches/.build.yml: SUCCESS in 31s

[proposal: checker: set the eval type at the binary op expression][0] v0 from [Carlos Maniero][1]

[0]: https://lists.sr.ht/~johnnyrichard/olang-devel/patches/55578
[1]: mailto:carlos@maniero.me

✓ #1354857 SUCCESS olang/patches/.build.yml https://builds.sr.ht/~johnnyrichard/job/1354857

Re: [PATCH olang v0] proposal: checker: set the eval type at the binary op expression

[Carlos Maniero]

We follow a different approach at the end. Adding the type to every
single node would be too expensive.

Re: [PATCH olang v0] proposal: checker: set the eval type at the binary op expression

[Johnny Richard]

I don't recall if this is still on progress.  Could you please refresh
my mind?

Re: [PATCH olang v0] proposal: checker: set the eval type at the binary op expression

[Johnny Richard]

On Tue, Nov 12, 2024 at 10:35:12PM GMT, Carlos Maniero wrote:
> We follow a different approach at the end. Adding the type to every
> single node would be too expensive.

Thanks for replying, I will reject it.