From a47e5ceb6eefdac9c5f5473e1fee0d33a5f4646e Mon Sep 17 00:00:00 2001 From: Carlos Maniero Date: Thu, 20 Apr 2023 11:05:54 -0300 Subject: ast: Allows recursive nodes Previously, the abstract syntax tree (AST) used static types, meaning that an ast_function_t would always have a ast_return_stmt_t as its body. However, this assumption is not always true, as we may have void functions that do not have a return statement. Additionally, the ast_return_stmt_t always had a number associated with it, but this too is not always the case. To make this possible, I need to perform a few changes in the whole project. One of the main changes is that there is no longer the inheritance hack. That mechanism was replaced by composition and pointers where required for recursive type reference. It is important to mention that I decided to use union type to implement the composition. There is two main advantages in this approach: 1. There is only one function to allocate memory for all kind of nodes. 2. There is no need to cast the data. In summary, this commit introduces changes to support dynamic typing in the AST, by replacing the inheritance hack with composition and using union types to simplify memory allocation and type casting. Signed-off-by: Carlos Maniero Reviewed-by: Johnny Richard --- src/ast.c | 73 ++++++++++++++++++++++++++++++++------------ src/ast.h | 41 +++++++++++++++++-------- src/gas_assembly_generator.c | 6 ++-- src/parser.c | 20 +++++++----- src/parser.h | 2 +- src/pipac.c | 10 ++++-- test/parser_test.c | 14 +++++++-- 7 files changed, 115 insertions(+), 51 deletions(-) diff --git a/src/ast.c b/src/ast.c index f8c2713..50f6a2e 100644 --- a/src/ast.c +++ b/src/ast.c @@ -15,6 +15,8 @@ * along with this program. If not, see . */ #include +#include +#include #include "ast.h" void @@ -26,38 +28,69 @@ ast_node_accept_visitor(ast_node_t *node, ast_visitor_t *visitor) } static void -ast_function_accept_visitor(ast_node_t *node, ast_visitor_t *visitor) +ast_node_function_accept_visitor(ast_node_t *node, ast_visitor_t *visitor) { - visitor->visit_function(visitor, (ast_function_t *) node); + visitor->visit_function(visitor, &node->data.function); } static void -ast_return_stmt_accept_visitor(ast_node_t *node, ast_visitor_t *visitor) +ast_node_return_stmt_accept_visitor(ast_node_t *node, ast_visitor_t *visitor) { - visitor->visit_return_stmt(visitor, (ast_return_stmt_t *) node); + visitor->visit_return_stmt(visitor, &node->data.return_stmt); } -ast_return_stmt_t -ast_return_stmt_create(uint32_t number) +ast_node_t* +ast_node_new() { - return (ast_return_stmt_t) { - .super = (ast_node_t) { - .accept_visitor = &ast_return_stmt_accept_visitor - }, - .number = number + ast_node_t *node = (ast_node_t*) malloc(sizeof(ast_node_t)); + if (node == NULL) { + printf("OOO: could no allocate a node"); + exit(EXIT_FAILURE); + } + node->kind = AST_UNKOWN_NODE; + return node; +} + +void +ast_node_destroy(ast_node_t *node) +{ + switch (node->kind) { + case AST_FUNCTION_DECLARATION: + ast_node_destroy(node->data.function.body); + break; + case AST_RETURN_STMT: + break; + case AST_UNKOWN_NODE: + break; + default: + assert(false && "unmapped free strategy"); + } + free(node); +} + +void +ast_node_init_return_stmt(ast_node_t *node, uint32_t number) +{ + node->accept_visitor = &ast_node_return_stmt_accept_visitor, + node->kind = AST_RETURN_STMT; + node->data = (ast_node_data_t) { + .return_stmt = { + .number = number + } }; } -ast_function_t -ast_function_create(string_view_t name, type_t return_type, ast_return_stmt_t body) +void +ast_node_init_function_declaration(ast_node_t *node, string_view_t name, type_t return_type, ast_node_t* body) { - return (ast_function_t) { - .super = (ast_node_t) { - .accept_visitor = &ast_function_accept_visitor - }, - .name = name, - .return_type = return_type, - .body = body + node->accept_visitor = &ast_node_function_accept_visitor, + node->kind = AST_FUNCTION_DECLARATION; + node->data = (ast_node_data_t) { + .function = { + .name = name, + .return_type = return_type, + .body = body + } }; } diff --git a/src/ast.h b/src/ast.h index 7f5a198..fab90c1 100644 --- a/src/ast.h +++ b/src/ast.h @@ -19,39 +19,54 @@ #include #include "string_view.h" -#define ast_visitor_visit(visitor, node) ast_node_accept_visitor((ast_node_t *) node, (ast_visitor_t *) visitor); +#define ast_visitor_visit(visitor, node) ast_node_accept_visitor(node, (ast_visitor_t *) visitor); typedef enum { TYPE_I32 } type_t; typedef struct ast_visitor_t ast_visitor_t; - -typedef struct ast_node_t { - void (*accept_visitor)(struct ast_node_t *, ast_visitor_t *); -} ast_node_t; +typedef struct ast_node_t ast_node_t; typedef struct ast_return_stmt_t { - struct ast_node_t super; uint32_t number; } ast_return_stmt_t; -typedef struct ast_function_t { - struct ast_node_t super; +typedef struct ast_function_declaration_t { string_view_t name; type_t return_type; - ast_return_stmt_t body; -} ast_function_t; + ast_node_t* body; +} ast_function_declaration_t; typedef struct ast_visitor_t { - void (*visit_function)(struct ast_visitor_t *, ast_function_t *); + void (*visit_function)(struct ast_visitor_t *, ast_function_declaration_t *); void (*visit_return_stmt)(struct ast_visitor_t *, ast_return_stmt_t *); } ast_visitor_t; +typedef enum { + AST_UNKOWN_NODE, + AST_FUNCTION_DECLARATION, + AST_RETURN_STMT +} ast_node_kind_t; + +typedef union { + ast_function_declaration_t function; + ast_return_stmt_t return_stmt; +} ast_node_data_t; + +typedef struct ast_node_t { + void (*accept_visitor)(ast_node_t *, ast_visitor_t *); + ast_node_kind_t kind; + ast_node_data_t data; +} ast_node_t; + void ast_node_accept_visitor(ast_node_t *node, ast_visitor_t *visitor); -ast_function_t ast_function_create(string_view_t name, type_t return_type, ast_return_stmt_t body); -ast_return_stmt_t ast_return_stmt_create(uint32_t number); +ast_node_t* ast_node_new(); +void ast_node_destroy(ast_node_t *node); + +void ast_node_init_function_declaration(ast_node_t* node, string_view_t name, type_t return_type, ast_node_t *body); +void ast_node_init_return_stmt(ast_node_t* node, uint32_t number); #endif /* AST_H */ diff --git a/src/gas_assembly_generator.c b/src/gas_assembly_generator.c index d164b7d..afbfebd 100644 --- a/src/gas_assembly_generator.c +++ b/src/gas_assembly_generator.c @@ -20,7 +20,7 @@ #include #include -static void gas_assembly_generator_visit_function(ast_visitor_t *visitor, ast_function_t *func); +static void gas_assembly_generator_visit_function(ast_visitor_t *visitor, ast_function_declaration_t *func); static void gas_assembly_generator_visit_return_stmt(ast_visitor_t *visitor, ast_return_stmt_t *return_stmt); void @@ -35,7 +35,7 @@ gas_assembly_generator_init(gas_assembly_generator_t *gen, FILE *out) } static void -gas_assembly_generator_visit_function(ast_visitor_t *visitor, ast_function_t *func) +gas_assembly_generator_visit_function(ast_visitor_t *visitor, ast_function_declaration_t *func) { assert(visitor && func); @@ -50,7 +50,7 @@ gas_assembly_generator_visit_function(ast_visitor_t *visitor, ast_function_t *fu fprintf(gen->out,".text\n"); fprintf(gen->out,"_start:\n"); - ast_visitor_visit(visitor, &func->body); + ast_visitor_visit(visitor, func->body); } static void diff --git a/src/parser.c b/src/parser.c index b956c4e..b1e6a1f 100644 --- a/src/parser.c +++ b/src/parser.c @@ -70,12 +70,12 @@ parser_parse_type(parser_t *parser) return TYPE_I32; } - fprintf(stderr, "[ERROR]: expected type 'i32' but got '"SVFMT"'\n", SVARG(&token.value)); + fprintf(stderr, "[ERROR]: expected type 'i32' but got '"SVFMT"'\n", SVARG(&token.value)); exit(EXIT_FAILURE); } -static ast_return_stmt_t -parser_parse_return_stmt(parser_t *parser) +void +parser_parse_return_stmt(parser_t *parser, ast_node_t *node) { expected_token(parser, TOKEN_OCURLY); token_t return_keyword_token = expected_token(parser, TOKEN_NAME); @@ -93,11 +93,11 @@ parser_parse_return_stmt(parser_t *parser) char number_as_str[number_token.value.size]; string_view_to_str(&number_token.value, number_as_str); - return ast_return_stmt_create(atoi(number_as_str)); + ast_node_init_return_stmt(node, atoi(number_as_str)); } -ast_function_t -parser_parse_function(parser_t *parser) +void +parser_parse_function_declaration(parser_t *parser, ast_node_t *node) { token_t func_name_token = expected_token(parser, TOKEN_NAME); expected_token(parser, TOKEN_OPAREN); @@ -105,9 +105,13 @@ parser_parse_function(parser_t *parser) expected_token(parser, TOKEN_COLON); type_t return_type = parser_parse_type(parser); - return ast_function_create( + ast_node_t *return_node = ast_node_new(); + parser_parse_return_stmt(parser, return_node); + + ast_node_init_function_declaration( + node, func_name_token.value, return_type, - parser_parse_return_stmt(parser) + return_node ); } diff --git a/src/parser.h b/src/parser.h index b846ae1..988006e 100644 --- a/src/parser.h +++ b/src/parser.h @@ -27,7 +27,7 @@ typedef struct parser_t { void parser_init(parser_t *parser, lexer_t *lexer); -ast_function_t parser_parse_function(parser_t *parser); +void parser_parse_function_declaration(parser_t *parser, ast_node_t *node); #endif /* PARSER_H */ diff --git a/src/pipac.c b/src/pipac.c index e56d8a1..41294c4 100644 --- a/src/pipac.c +++ b/src/pipac.c @@ -19,12 +19,13 @@ #include #include "lexer.h" +#include "ast.h" #include "parser.h" #include "string_view.h" #include "gas_assembly_generator.h" void -generate_gas_x86_64_linux(ast_function_t *func) +generate_gas_x86_64_linux(ast_node_t *func) { gas_assembly_generator_t gen; gas_assembly_generator_init(&gen, stdout); @@ -61,9 +62,12 @@ main(int argc, char **argv) parser_t parser; parser_init(&parser, &lexer); - ast_function_t func = parser_parse_function(&parser); - generate_gas_x86_64_linux(&func); + ast_node_t* func = ast_node_new(); + parser_parse_function_declaration(&parser, func); + generate_gas_x86_64_linux(func); + + ast_node_destroy(func); return EXIT_SUCCESS; } diff --git a/test/parser_test.c b/test/parser_test.c index b75f69f..30aa285 100644 --- a/test/parser_test.c +++ b/test/parser_test.c @@ -40,13 +40,21 @@ test_parse_function(const MunitParameter params[], make_lexer_from_static_src(&lexer, "main(): i32 { return 42; }"); parser_init(&parser, &lexer); - ast_function_t ast_function = parser_parse_function(&parser); + ast_node_t *ast_function = ast_node_new(); + parser_parse_function_declaration(&parser, ast_function); char actual[5]; - string_view_to_str(&ast_function.name, actual); + string_view_to_str(&ast_function->data.function.name, actual); assert_string_equal("main", actual); - assert_int(42, ==, ast_function.body.number); + assert_int(AST_FUNCTION_DECLARATION, ==, ast_function->kind); + + ast_node_t *ast_return = ast_function->data.function.body; + + assert_int(AST_RETURN_STMT, ==, ast_return->kind); + assert_int(42, ==, ast_return->data.return_stmt.number); + + ast_node_destroy(ast_function); return MUNIT_OK; } -- cgit v1.2.3