* [PATCH olang v0] proposal: checker: set the eval type at the binary op expression
@ 2024-10-22 3:39 Carlos Maniero
2024-10-22 3:40 ` [olang/patches/.build.yml] build success builds.sr.ht
2024-11-13 0:10 ` [PATCH olang v0] proposal: checker: set the eval type at the binary op expression Johnny Richard
0 siblings, 2 replies; 5+ messages in thread
From: Carlos Maniero @ 2024-10-22 3:39 UTC (permalink / raw)
To: ~johnnyrichard/olang-devel; +Cc: 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
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2024-11-12 22:46 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-10-22 3:39 [PATCH olang v0] proposal: checker: set the eval type at the binary op expression Carlos Maniero
2024-10-22 3:40 ` [olang/patches/.build.yml] build success builds.sr.ht
2024-11-13 0:10 ` [PATCH olang v0] proposal: checker: set the eval type at the binary op expression Johnny Richard
2024-11-12 22:35 ` Carlos Maniero
2024-11-13 0:45 ` Johnny Richard
Code repositories for project(s) associated with this public inbox
https://git.johnnyrichard.com/olang.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox