From a5c12fd6f4438fc172f28b722e54908b575c6ce1 Mon Sep 17 00:00:00 2001 From: Carson Fleming Date: Fri, 17 Jul 2026 00:38:51 -0400 Subject: before I do something crazy --- README.md | 9 +++++ ast.c | 83 +++++++++++++++++++++++--------------- ast.h | 84 +++++++++++++++++++++++--------------- codegen.c | 124 ++++++++++++++++++++++++++++----------------------------- codegen.h | 2 +- main.c | 7 ++-- parser.c | 100 ++++++++++++++++++++++++++-------------------- parser.h | 2 +- scope.c | 21 ++++++++-- scope.h | 7 +++- type_checker.c | 74 ++++++++++++++++++++++++++++++++++ 11 files changed, 331 insertions(+), 182 deletions(-) create mode 100644 type_checker.c diff --git a/README.md b/README.md index c979324..4ff2649 100644 --- a/README.md +++ b/README.md @@ -1,3 +1,12 @@ # Carson's C Compiler fuck it, we ball + +TODO soon: +- [ ] type checking +- [ ] use evaluated types to make code gen around math better +- [ ] ideally we don't want to recompute the definitions that live in scopes + - [ ] add a `struct scope* scope` to expr_node + - [ ] make the root scope live on a `struct ast` that houses the root node as well + - [ ] handle scope deallocation in ast.c + - [ ] `group_node` and `fn_decl_node` can have a `struct scope* scope` that they own diff --git a/ast.c b/ast.c index 7f97948..44401cb 100644 --- a/ast.c +++ b/ast.c @@ -1,11 +1,17 @@ #include "ast.h" +#include "scope.h" #include static void expr_destroy(struct expr_node* node); static void stmt_destroy(struct stmt_node* node); +static void type_destroy(struct type_node* node) { + free(node->def); +} + static void var_decl_destroy(struct var_decl_node* node) { free(node->ident); + type_destroy(&node->type); } static void var_ref_destroy(struct var_ref_node* node) { @@ -15,10 +21,10 @@ static void var_ref_destroy(struct var_ref_node* node) { static void lval_destroy(struct lval_node* node) { switch (node->type) { case LVAL_VAR_DECL: - var_decl_destroy(&node->as._var_decl); + var_decl_destroy(&node->inner.var_decl); break; case LVAL_VAR_REF: - var_ref_destroy(&node->as._var_ref); + var_ref_destroy(&node->inner.var_ref); break; } } @@ -30,27 +36,37 @@ static void assign_destroy(struct assign_node* node) { } static void group_destroy(struct group_node* node) { - struct stmt_node* body_node = node->body_head; + struct stmt_node* body_node = node->head; while (body_node != NULL) { struct stmt_node* next = body_node->next; stmt_destroy(body_node); free(body_node); body_node = next; } + + scope_destroy(node->scope); + free(node->scope); +} + +static void args_decl_destroy(struct args_decl_node* node) { + if (node != NULL) { + var_decl_destroy(node->decl); + free(node->decl); + args_decl_destroy(node->next); + } } static void fn_decl_destroy(struct fn_decl_node* node) { + type_destroy(&node->return_type); free(node->name); - struct var_decl_node* args_node = node->args_head; - while (args_node != NULL) { - struct var_decl_node* next = args_node->next; - var_decl_destroy(args_node); - free(args_node); - args_node = next; - } + args_decl_destroy(node->args); + free(node->args); group_destroy(&node->body); + + scope_destroy(node->scope); + free(node->scope); } static void return_destroy(struct return_node* node) { @@ -64,17 +80,19 @@ static void str_lit_destroy(struct str_lit_node* node) { free(node->val); } -static void call_destroy(struct call_node* node) { - /* don't destroy node->called_fn, this is owned by its declaration */ - struct expr_node* args_node = node->args_head; - while (args_node != NULL) { - struct expr_node* next = args_node->next; - expr_destroy(args_node); - free(args_node); - args_node = next; +static void args_list_destroy(struct args_eval_node* node) { + if (node != NULL) { + expr_destroy(node->expr); + free(node->expr); + args_list_destroy(node->next); } } +static void call_destroy(struct call_node* node) { + args_list_destroy(node->args); + free(node->args); +} + static void unary_destroy(struct unary_node* node) { expr_destroy(node->expr); free(node->expr); @@ -95,22 +113,22 @@ static void expr_destroy(struct expr_node* node) { case EXPR_CHAR_LIT: break; case EXPR_STR_LIT: - str_lit_destroy(&node->as._str_lit); + str_lit_destroy(&node->inner.str_lit); break; case EXPR_VAR_REF: - var_ref_destroy(&node->as._var_ref); + var_ref_destroy(&node->inner.var_ref); break; case EXPR_ASSIGN: - assign_destroy(&node->as._assign); + assign_destroy(&node->inner.assign); break; case EXPR_CALL: - call_destroy(&node->as._call); + call_destroy(&node->inner.call); break; case EXPR_UNARY: - unary_destroy(&node->as._unary); + unary_destroy(&node->inner.unary); break; case EXPR_BINARY: - binary_destroy(&node->as._binary); + binary_destroy(&node->inner.binary); break; } } @@ -120,33 +138,36 @@ static void stmt_destroy(struct stmt_node* node) { case STMT_EMPTY: break; case STMT_EXPR: - expr_destroy(&node->as._expr); + expr_destroy(&node->inner.expr); break; case STMT_VAR_DECL: - var_decl_destroy(&node->as._var_decl); + var_decl_destroy(&node->inner.var_decl); break; case STMT_RETURN: - return_destroy(&node->as._return); + return_destroy(&node->inner.return_); break; case STMT_GROUP: - group_destroy(&node->as._group); + group_destroy(&node->inner.group); } } static void root_node_destroy(struct root_node* node) { switch (node->type) { case ROOT_FN_DECL: - fn_decl_destroy(&node->as._fn_decl); + fn_decl_destroy(&node->inner.fn_decl); break; } } -void ast_destroy(struct root_node* head) { - struct root_node* node = head; +void ast_destroy(struct ast* ast) { + struct root_node* node = ast->root_node; while (node != NULL) { struct root_node* next = node->next; root_node_destroy(node); free(node); node = next; } + + scope_destroy(ast->root_scope); + free(ast->root_scope); } diff --git a/ast.h b/ast.h index 4837c2b..4b8f0ee 100644 --- a/ast.h +++ b/ast.h @@ -7,11 +7,11 @@ struct stmt_node; struct expr_node; struct type_node { - bool _unsigned; - bool _short; - bool _long; - struct type_def def; + bool is_unsigned; + bool is_short; + bool is_long; unsigned char ptr_level; + struct type_def* def; }; struct int_lit_node { @@ -37,8 +37,6 @@ struct var_ref_node { struct var_decl_node { struct type_node type; char* ident; - - struct var_decl_node* next; }; struct lval_node { @@ -47,9 +45,9 @@ struct lval_node { LVAL_VAR_REF, } type; union { - struct var_ref_node _var_ref; - struct var_decl_node _var_decl; - } as; + struct var_ref_node var_ref; + struct var_decl_node var_decl; + } inner; }; struct assign_node { @@ -57,10 +55,15 @@ struct assign_node { struct expr_node* rval; }; +struct args_eval_node { + struct expr_node* expr; + struct args_eval_node* next; +}; + struct call_node { /* TODO: eventually this could also be a function pointer */ - struct fn_decl_node* called_fn; - struct expr_node* args_head; + struct fn_decl_node* called_fn_ref; /* borrowed */ + struct args_eval_node* args; }; struct unary_node { @@ -94,29 +97,39 @@ struct expr_node { EXPR_BINARY, } type; union { - struct int_lit_node _int_lit; - struct float_lit_node _float_lit; - struct char_lit_node _char_lit; - struct str_lit_node _str_lit; - struct var_ref_node _var_ref; - struct assign_node _assign; - struct call_node _call; - struct unary_node _unary; - struct binary_node _binary; - } as; - - struct expr_node* next; + struct int_lit_node int_lit; + struct float_lit_node float_lit; + struct char_lit_node char_lit; + struct str_lit_node str_lit; + struct var_ref_node var_ref; + struct assign_node assign; + struct call_node call; + struct unary_node unary; + struct binary_node binary; + } inner; + + struct { + bool is_signed; + unsigned long long sz; + } evaluated_type; }; struct group_node { - struct stmt_node* body_head; + struct stmt_node* head; + struct scope* scope; +}; + +struct args_decl_node { + struct var_decl_node* decl; + struct args_decl_node* next; }; struct fn_decl_node { struct type_node return_type; char* name; - struct var_decl_node* args_head; + struct args_decl_node* args; struct group_node body; + struct scope* scope; }; struct return_node { @@ -132,11 +145,11 @@ struct stmt_node { STMT_GROUP, } type; union { - struct expr_node _expr; - struct var_decl_node _var_decl; - struct return_node _return; - struct group_node _group; - } as; + struct expr_node expr; + struct var_decl_node var_decl; + struct return_node return_; + struct group_node group; + } inner; struct stmt_node* next; }; @@ -146,12 +159,17 @@ struct root_node { ROOT_FN_DECL, } type; union { - struct fn_decl_node _fn_decl; - } as; + struct fn_decl_node fn_decl; + } inner; struct root_node* next; }; -void ast_destroy(struct root_node* head); +struct ast { + struct root_node* root_node; + struct scope* root_scope; +}; + +void ast_destroy(struct ast* ast); #endif diff --git a/codegen.c b/codegen.c index 662097e..749c85d 100644 --- a/codegen.c +++ b/codegen.c @@ -180,9 +180,10 @@ static void emit_mov( fprintf(outfile, "\n"); } +/* TODO: move this utility to the type checker and use evaluated_type */ static unsigned long long get_type_size(const struct type_node* type) { if (type->ptr_level > 0) return PTR_SIZE; - return type->def.sz; + return type->def->sz; } static inline struct lval_def make_stack_lval( @@ -272,6 +273,7 @@ static struct var_def emit_var_decl( FILE* outfile, const struct var_decl_node* node ) { + /* TODO: type checker should define vars, we just set their loc */ struct lval_def var_dst = make_stack_lval(outfile, &node->type); struct var_def var_def = { .name = node->ident, @@ -289,10 +291,10 @@ static struct lval_def emit_lval( struct var_def var_def; switch (node->type) { case LVAL_VAR_DECL: - var_def = emit_var_decl(outfile, &node->as._var_decl); + var_def = emit_var_decl(outfile, &node->inner.var_decl); return (struct lval_def) {.loc = var_def.loc, .sz = var_def.sz}; case LVAL_VAR_REF: - var_def = get_var(node->as._var_ref.ident); + var_def = get_var(node->inner.var_ref.ident); return (struct lval_def) {.loc = var_def.loc, .sz = var_def.sz}; } CGEN_PANIC("unknown lval type: %d", node->type); @@ -316,25 +318,30 @@ static void emit_call( unsigned long long orig_bp_offset = scope->bp_offset; unsigned long long arg_bp_offset = orig_bp_offset; - struct var_decl_node* arg_decl = node->called_fn->args_head; - struct expr_node* arg_eval = node->args_head; + struct args_decl_node* arg_decl = node->called_fn_ref->args; + struct args_eval_node* arg_eval = node->args; while (arg_decl != NULL && arg_eval != NULL) { - struct lval_def arg_dst = make_stack_lval(outfile, &arg_decl->type); - emit_expr(outfile, arg_eval, &arg_dst); + struct lval_def arg_dst = + make_stack_lval(outfile, &arg_decl->decl->type); + emit_expr(outfile, arg_eval->expr, &arg_dst); arg_decl = arg_decl->next; arg_eval = arg_eval->next; } if (arg_decl != NULL) - CGEN_PANIC("too many arguments to function %s", node->called_fn->name); + CGEN_PANIC( + "too many arguments to function %s", + node->called_fn_ref->name); if (arg_eval != NULL) - CGEN_PANIC("missing arguments to function %s", node->called_fn->name); + CGEN_PANIC( + "missing arguments to function %s", + node->called_fn_ref->name); unsigned char arg_regnum = 0; - arg_decl = node->called_fn->args_head; + arg_decl = node->called_fn_ref->args; while (arg_decl != NULL) { - unsigned long long type_sz = get_type_size(&arg_decl->type); + unsigned long long type_sz = get_type_size(&arg_decl->decl->type); arg_bp_offset += type_sz; struct lval_def arg_dst; @@ -347,7 +354,7 @@ static void emit_call( .sz = type_sz, }; else - arg_dst = make_stack_lval(outfile, &arg_decl->type); + arg_dst = make_stack_lval(outfile, &arg_decl->decl->type); emit_mov(outfile, &arg_dst, &(struct storage_location) { .type = STO_STACK, @@ -356,9 +363,9 @@ static void emit_call( arg_decl = arg_decl->next; } - fprintf(outfile, "\tcall %s\n", node->called_fn->name); + fprintf(outfile, "\tcall %s\n", node->called_fn_ref->name); if (dst != NULL) { - if (node->called_fn->return_type.def.sz == 0) + if (get_type_size(&node->called_fn_ref->return_type) == 0) CGEN_PANIC("can't assign the result of a void function"); emit_mov(outfile, dst, &RV_LOC); @@ -458,31 +465,31 @@ static void emit_expr( ) { switch (node->type) { case EXPR_INT_LIT: - emit_int_lit(outfile, &node->as._int_lit, dst); + emit_int_lit(outfile, &node->inner.int_lit, dst); break; case EXPR_FLOAT_LIT: - emit_float_lit(outfile, &node->as._float_lit, dst); + emit_float_lit(outfile, &node->inner.float_lit, dst); break; case EXPR_CHAR_LIT: - emit_char_lit(outfile, &node->as._char_lit, dst); + emit_char_lit(outfile, &node->inner.char_lit, dst); break; case EXPR_STR_LIT: - emit_str_lit(outfile, &node->as._str_lit, dst); + emit_str_lit(outfile, &node->inner.str_lit, dst); break; case EXPR_VAR_REF: - emit_var_ref(outfile, &node->as._var_ref, dst); + emit_var_ref(outfile, &node->inner.var_ref, dst); break; case EXPR_ASSIGN: - emit_assignment(outfile, &node->as._assign, dst); + emit_assignment(outfile, &node->inner.assign, dst); break; case EXPR_CALL: - emit_call(outfile, &node->as._call, dst); + emit_call(outfile, &node->inner.call, dst); break; case EXPR_UNARY: - emit_unary(outfile, &node->as._unary, dst); + emit_unary(outfile, &node->inner.unary, dst); break; case EXPR_BINARY: - emit_binary(outfile, &node->as._binary, dst); + emit_binary(outfile, &node->inner.binary, dst); break; } } @@ -491,7 +498,7 @@ static void emit_return(FILE* outfile, const struct return_node* node) { if (active_fn == NULL) CGEN_PANIC("must be inside a function to return"); if (node->ret_val != NULL) { - if (active_fn->return_type.def.sz == 0) + if (active_fn->return_type.def->sz == 0) CGEN_PANIC( "returning a value from void function %s", active_fn->name); @@ -500,9 +507,9 @@ static void emit_return(FILE* outfile, const struct return_node* node) { node->ret_val, &(struct lval_def) { .loc = RV_LOC, - .sz = active_fn->return_type.def.sz, + .sz = active_fn->return_type.def->sz, }); - } else if (active_fn->return_type.def.sz > 0) { + } else if (active_fn->return_type.def->sz > 0) { CGEN_PANIC( "non-void function %s should return a value", active_fn->name); } @@ -511,7 +518,7 @@ static void emit_return(FILE* outfile, const struct return_node* node) { } static void emit_group(FILE* outfile, const struct group_node* node) { - const struct stmt_node* body_node = node->body_head; + const struct stmt_node* body_node = node->head; while (body_node != NULL) { emit_stmt(outfile, body_node); body_node = body_node->next; @@ -519,14 +526,16 @@ static void emit_group(FILE* outfile, const struct group_node* node) { } static void emit_stmt_group(FILE* outfile, const struct group_node* node) { - scope_push(&scope); + if (node->scope->next_out != scope) CGEN_PANIC("scopes are misaligned"); + + scope = node->scope; scope->bp_offset = scope->next_out->bp_offset; /* don't reset bp */ emit_group(outfile, node); /* don't reset sp because alloca needs to work */ scope->next_out->bp_offset = scope->bp_offset; - scope_pop(&scope); + scope = scope->next_out; } static void emit_stmt(FILE* outfile, const struct stmt_node* node) { @@ -534,16 +543,16 @@ static void emit_stmt(FILE* outfile, const struct stmt_node* node) { case STMT_EMPTY: break; case STMT_VAR_DECL: - emit_var_decl(outfile, &node->as._var_decl); + emit_var_decl(outfile, &node->inner.var_decl); break; case STMT_RETURN: - emit_return(outfile, &node->as._return); + emit_return(outfile, &node->inner.return_); break; case STMT_EXPR: - emit_expr(outfile, &node->as._expr, NULL); + emit_expr(outfile, &node->inner.expr, NULL); break; case STMT_GROUP: - emit_stmt_group(outfile, &node->as._group); + emit_stmt_group(outfile, &node->inner.group); break; } } @@ -560,18 +569,20 @@ static void emit_fn_decl(FILE* outfile, const struct fn_decl_node* node) { fprintf(outfile, "\tpush rbp\n"); fprintf(outfile, "\tmov rbp, rsp\n"); - scope_push(&scope); + if (node->scope->next_out != scope) CGEN_PANIC("scopes are misaligned"); + scope = node->scope; scope->bp_offset = 0; long long spilled_bp_ofs = -16; // return address + old bp unsigned char arg_regnum = 0; - struct var_decl_node* args_node = node->args_head; - while (args_node != NULL) { - struct lval_def arg_dst = make_stack_lval(outfile, &args_node->type); + struct args_decl_node* arg_decl = node->args; + while (arg_decl != NULL) { + struct lval_def arg_dst = + make_stack_lval(outfile, &arg_decl->decl->type); scope_define_var( scope, (struct var_def) { - .name = args_node->ident, + .name = arg_decl->decl->ident, .loc = arg_dst.loc, .sz = arg_dst.sz, }); @@ -591,12 +602,12 @@ static void emit_fn_decl(FILE* outfile, const struct fn_decl_node* node) { } emit_mov(outfile, &arg_dst, &arg_src); - args_node = args_node->next; + arg_decl = arg_decl->next; } emit_group(outfile, &node->body); - scope_pop(&scope); + scope = scope->next_out; fprintf(outfile, RETURN_LABEL_FMT ":\n", node->name); fprintf(outfile, "\tmov rsp, rbp\n"); @@ -608,48 +619,33 @@ static void emit_fn_decl(FILE* outfile, const struct fn_decl_node* node) { static void emit_root_node(FILE* outfile, const struct root_node* node) { switch (node->type) { case ROOT_FN_DECL: - emit_fn_decl(outfile, &node->as._fn_decl); + emit_fn_decl(outfile, &node->inner.fn_decl); break; } } -void emit_code(const struct root_node* ast, const char* path) { +void emit_code(struct ast* ast, const char* path) { FILE* outfile = fopen(path, "w"); if (outfile == NULL) CCC_PANIC; + scope = ast->root_scope; fprintf(outfile, "section .text\n"); - scope_push(&scope); - scope_install_default_types(scope); - - /* output all non-static function declarations as globals */ - const struct root_node* node = ast; - while (node != NULL) { - if (node->type == ROOT_FN_DECL) { - const char* fn_name = node->as._fn_decl.name; - scope_define_var(scope, (struct var_def) { - .name = fn_name, - .loc = { - .type = STO_LABEL, - .label = fn_name, - }, - /* sz ignored, not relevant to functions */ - }); - fprintf(outfile, "global %s\n", fn_name); - } - node = node->next; + /* output all function declarations in the root scope as globals */ + const struct root_node* node = ast->root_node; + for (; node != NULL; node = node->next) { + if (node->type != ROOT_FN_DECL) continue; + fprintf(outfile, "global %s\n", node->inner.fn_decl.name); } - fprintf(outfile, "\n"); /* actual code body */ - node = ast; + node = ast->root_node; while (node != NULL) { emit_root_node(outfile, node); if (node->next != NULL) fprintf(outfile, "\n"); node = node->next; } - scope_pop(&scope); fclose(outfile); } diff --git a/codegen.h b/codegen.h index 50bb105..7c8023c 100644 --- a/codegen.h +++ b/codegen.h @@ -3,6 +3,6 @@ #include "ast.h" -void emit_code(const struct root_node* ast, const char* path); +void emit_code(struct ast* ast, const char* path); #endif diff --git a/main.c b/main.c index 4cb0ba7..90d7460 100644 --- a/main.c +++ b/main.c @@ -39,15 +39,16 @@ void test_lexer(int argc, char** argv) { void test_parser(int argc, char** argv) { for (int i = 1; i < argc; i++) { - struct root_node* root = parse(argv[i]); + struct ast ast; + parse(argv[i], &ast); unsigned int fn_sz = strlen(argv[i]); char asm_file[fn_sz + 1]; strcpy(asm_file, argv[i]); asm_file[fn_sz - 1] = 's'; asm_file[fn_sz] = 0; - emit_code(root, asm_file); - ast_destroy(root); + emit_code(&ast, asm_file); + ast_destroy(&ast); char obj_file[fn_sz + 1]; strcpy(obj_file, argv[i]); diff --git a/parser.c b/parser.c index 6a8ad31..42a7f49 100644 --- a/parser.c +++ b/parser.c @@ -66,8 +66,8 @@ static void parse_type(struct type_node* p_node) { /* TODO: modifiers, void rules, arrays, etc. */ /* TODO: struct, union, enum */ expect(TK_IDENT); - struct type_def type_def; - if (!scope_get_type(scope, &type_def, tok.data.ident)) + struct type_def* type_def = protected_alloc(sizeof(struct type_def)); + if (!scope_get_type(scope, type_def, tok.data.ident)) PARSER_PANIC("unknown type name: %s", tok.data.ident); p_node->def = type_def; @@ -90,12 +90,12 @@ static void parse_literal(struct expr_node* p_node) { case TK_INT_LIT: expect(TK_INT_LIT); p_node->type = EXPR_INT_LIT; - p_node->as._int_lit.val = tok.data.int_lit; + p_node->inner.int_lit.val = tok.data.int_lit; break; case TK_CHAR_LIT: expect(TK_CHAR_LIT); p_node->type = EXPR_CHAR_LIT; - p_node->as._char_lit.val = tok.data.char_lit; + p_node->inner.char_lit.val = tok.data.char_lit; break; default: PARSER_PANIC("invalid literal type"); @@ -105,14 +105,16 @@ static void parse_literal(struct expr_node* p_node) { static void parse_var_ref(struct var_ref_node* p_node) { expect(TK_IDENT); p_node->ident = tok.data.ident; + if (!scope_get_var(scope, NULL, p_node->ident)) + PARSER_PANIC("use of undeclared identifier: '%s'", p_node->ident); } static void parse_expr_assign(struct expr_node* p_node) { switch (p_node->type) { case EXPR_VAR_REF: - p_node->as._assign.lval = (struct lval_node) { + p_node->inner.assign.lval = (struct lval_node) { .type = LVAL_VAR_REF, - .as._var_ref = p_node->as._var_ref, + .inner.var_ref = p_node->inner.var_ref, }; return; default: @@ -120,16 +122,17 @@ static void parse_expr_assign(struct expr_node* p_node) { } p_node->type = EXPR_ASSIGN; - p_node->as._assign.rval = protected_alloc(sizeof(struct expr_node)); + p_node->inner.assign.rval = protected_alloc(sizeof(struct expr_node)); expect(TK_ASSIGN); - parse_expr(p_node->as._assign.rval); + parse_expr(p_node->inner.assign.rval); } -static void parse_arg_evals(struct expr_node** pp_arg) { +static void parse_args_eval(struct args_eval_node** pp_arg) { for (;;) { - *pp_arg = protected_alloc(sizeof(struct expr_node)); - parse_expr(*pp_arg); + *pp_arg = protected_alloc(sizeof(struct args_eval_node)); + (*pp_arg)->expr = protected_alloc(sizeof(struct expr_node)); + parse_expr((*pp_arg)->expr); pp_arg = &((*pp_arg)->next); peek_or_panic(); @@ -142,25 +145,25 @@ static void parse_expr_call(struct expr_node* p_node) { switch (p_node->type) { case EXPR_VAR_REF: struct var_def var_def; - if (!scope_get_var(scope, &var_def, p_node->as._var_ref.ident)) + if (!scope_get_var(scope, &var_def, p_node->inner.var_ref.ident)) PARSER_PANIC( - "%s is not a known function", p_node->as._var_ref.ident); + "%s is not a known function", p_node->inner.var_ref.ident); if (var_def.loc.type != STO_FN) PARSER_PANIC("called object is not a function"); - p_node->as._call.called_fn = var_def.loc.decl; + p_node->inner.call.called_fn_ref = var_def.loc.decl; break; default: PARSER_PANIC("expression is not callable"); } p_node->type = EXPR_CALL; - p_node->as._call.args_head = NULL; + p_node->inner.call.args = NULL; expect(TK_LPAREN); peek_or_panic(); - if (tok.type != TK_RPAREN) parse_arg_evals(&p_node->as._call.args_head); + if (tok.type != TK_RPAREN) parse_args_eval(&p_node->inner.call.args); expect(TK_RPAREN); } @@ -186,7 +189,7 @@ static void parse_expr_binary(struct expr_node* p_node) { *lhs = *p_node; *p_node = (struct expr_node) { .type = EXPR_BINARY, - .as._binary = { + .inner.binary = { .lhs = lhs, .rhs = rhs, }, @@ -196,19 +199,19 @@ static void parse_expr_binary(struct expr_node* p_node) { switch (tok.type) { case TK_PLUS: expect(TK_PLUS); - p_node->as._binary.op = BINARY_ADD; + p_node->inner.binary.op = BINARY_ADD; break; case TK_NEG: expect(TK_NEG); - p_node->as._binary.op = BINARY_SUB; + p_node->inner.binary.op = BINARY_SUB; break; case TK_STAR: expect(TK_STAR); - p_node->as._binary.op = BINARY_MUL; + p_node->inner.binary.op = BINARY_MUL; break; case TK_DIV: expect(TK_DIV); - p_node->as._binary.op = BINARY_DIV; + p_node->inner.binary.op = BINARY_DIV; break; default: PARSER_PANIC("expected binary operator"); @@ -227,7 +230,7 @@ static void parse_expr(struct expr_node* p_node) { break; case TK_NEG: p_node->type = EXPR_UNARY; - parse_unary(&p_node->as._unary); + parse_unary(&p_node->inner.unary); break; case TK_INT_LIT: case TK_CHAR_LIT: @@ -237,7 +240,7 @@ static void parse_expr(struct expr_node* p_node) { break; case TK_IDENT: p_node->type = EXPR_VAR_REF; - parse_var_ref(&p_node->as._var_ref); + parse_var_ref(&p_node->inner.var_ref); break; default: PARSER_PANIC("expected expression"); @@ -265,6 +268,7 @@ static void parse_var_decl(struct var_decl_node* p_node) { parse_type(&p_node->type); expect(TK_IDENT); p_node->ident = tok.data.ident; + scope_define_var(scope, (struct var_def) { .name = p_node->ident }); } static void parse_stmt(struct stmt_node* p_node); @@ -285,7 +289,10 @@ static void parse_return(struct return_node* p_node) { static void parse_group(struct group_node* p_node) { expect(TK_LCURLY); - struct stmt_node** pp_node = &p_node->body_head; + scope_push(&scope); + p_node->scope = scope; + + struct stmt_node** pp_node = &p_node->head; for (;;) { peek_or_panic(); if (tok.type == TK_RCURLY) break; @@ -295,6 +302,8 @@ static void parse_group(struct group_node* p_node) { pp_node = &((*pp_node)->next); } + scope_pop(&scope); + expect(TK_RCURLY); } @@ -304,9 +313,9 @@ static void parse_stmt_assign(struct stmt_node* p_node) { switch (p_node->type) { case STMT_VAR_DECL: - p_node->as._expr.as._assign.lval = (struct lval_node) { + p_node->inner.expr.inner.assign.lval = (struct lval_node) { .type = LVAL_VAR_DECL, - .as._var_decl = p_node->as._var_decl, + .inner.var_decl = p_node->inner.var_decl, }; break; default: @@ -314,12 +323,12 @@ static void parse_stmt_assign(struct stmt_node* p_node) { } p_node->type = STMT_EXPR; - p_node->as._expr.type = EXPR_ASSIGN; - p_node->as._expr.as._assign.rval = + p_node->inner.expr.type = EXPR_ASSIGN; + p_node->inner.expr.inner.assign.rval = protected_alloc(sizeof(struct expr_node)); expect(TK_ASSIGN); - parse_expr(p_node->as._expr.as._assign.rval); + parse_expr(p_node->inner.expr.inner.assign.rval); } static void parse_stmt(struct stmt_node* p_node) { @@ -330,32 +339,33 @@ static void parse_stmt(struct stmt_node* p_node) { break; case TK_LCURLY: p_node->type = STMT_GROUP; - parse_group(&p_node->as._group); + parse_group(&p_node->inner.group); return; case TK_IDENT: if (strcmp(tok.data.ident, "return") == 0) { p_node->type = STMT_RETURN; - parse_return(&p_node->as._return); + parse_return(&p_node->inner.return_); break; } else if (scope_get_type(scope, NULL, tok.data.ident)) { p_node->type = STMT_VAR_DECL; - parse_var_decl(&p_node->as._var_decl); + parse_var_decl(&p_node->inner.var_decl); break; } default: p_node->type = STMT_EXPR; - parse_expr(&p_node->as._expr); + parse_expr(&p_node->inner.expr); } parse_stmt_assign(p_node); expect(TK_SEMI); } -static void parse_arg_decls(struct var_decl_node** pp_arg) { +static void parse_args_decl(struct args_decl_node** pp_decl) { for (;;) { - *pp_arg = protected_alloc(sizeof(struct var_decl_node)); - parse_var_decl(*pp_arg); - pp_arg = &((*pp_arg)->next); + *pp_decl = protected_alloc(sizeof(struct args_decl_node)); + (*pp_decl)->decl = protected_alloc(sizeof(struct var_decl_node)); + parse_var_decl((*pp_decl)->decl); + pp_decl = &((*pp_decl)->next); peek_or_panic(); if (tok.type == TK_RPAREN) break; @@ -371,13 +381,18 @@ static void parse_fn_decl(struct fn_decl_node* p_node) { expect(TK_LPAREN); + scope_push(&scope); + p_node->scope = scope; + peek_or_panic(); - if (tok.type != TK_RPAREN) parse_arg_decls(&p_node->args_head); + if (tok.type != TK_RPAREN) parse_args_decl(&p_node->args); expect(TK_RPAREN); parse_group(&p_node->body); + scope_pop(&scope); + scope_define_var(scope, (struct var_def) { .name = p_node->name, .loc = { @@ -391,17 +406,17 @@ static bool parse_root(struct root_node* p_node) { if (!lexer_peek(&tok)) return false; p_node->type = ROOT_FN_DECL; - parse_fn_decl(&p_node->as._fn_decl); + parse_fn_decl(&p_node->inner.fn_decl); return true; } -struct root_node* parse(const char* path) { +void parse(const char* path, struct ast* ast) { lexer_load(path); scope_push(&scope); scope_install_default_types(scope); - struct root_node* root; - struct root_node** p_node = &root; + ast->root_scope = scope; + struct root_node** p_node = &ast->root_node; for (;;) { *p_node = protected_alloc(sizeof(struct root_node)); @@ -415,5 +430,4 @@ struct root_node* parse(const char* path) { scope_pop(&scope); lexer_close(); - return root; } diff --git a/parser.h b/parser.h index 5449b4f..a883364 100644 --- a/parser.h +++ b/parser.h @@ -3,6 +3,6 @@ #include "ast.h" -struct root_node* parse(const char* path); +void parse(const char* path, struct ast* ast); #endif diff --git a/scope.c b/scope.c index a0d4477..2bb686a 100644 --- a/scope.c +++ b/scope.c @@ -11,7 +11,7 @@ static void scope_init(struct scope* scope) { scope->var_cap = DEFAULT_SIZE; } -static void scope_destroy(struct scope* scope) { +void scope_destroy(struct scope* scope) { for (unsigned long long i = 0; i < scope->type_cap; i++) { if (scope->types[i] != NULL) free(scope->types[i]); } @@ -113,44 +113,57 @@ void scope_push(struct scope** p_scope) { } void scope_pop(struct scope** p_scope) { - struct scope* discarded_scope = *p_scope; *p_scope = (*p_scope)->next_out; - scope_destroy(discarded_scope); - free(discarded_scope); } void scope_install_default_types(struct scope* scope) { scope_define_type(scope, (struct type_def) { .name = "void", .sz = 0, + .is_primitive = true, + .is_signed = false, }); scope_define_type(scope, (struct type_def) { .name = "bool", .sz = 1, + .is_primitive = true, + .is_signed = false, }); scope_define_type(scope, (struct type_def) { .name = "char", .sz = 1, + .is_primitive = true, + .is_signed = true, /* implementation defined babyyyyyy */ }); scope_define_type(scope, (struct type_def) { .name = "short", .sz = 2, + .is_primitive = true, + .is_signed = true, }); scope_define_type(scope, (struct type_def) { .name = "int", .sz = 4, + .is_primitive = true, + .is_signed = true, }); scope_define_type(scope, (struct type_def) { .name = "float", .sz = 4, + .is_primitive = true, + .is_signed = true, /* floats can't be unsigned but wtv */ }); scope_define_type(scope, (struct type_def) { .name = "long", .sz = 8, + .is_primitive = true, + .is_signed = true, }); scope_define_type(scope, (struct type_def) { .name = "double", .sz = 8, + .is_primitive = true, + .is_signed = true, /* doubles also can't be unsigned */ }); } diff --git a/scope.h b/scope.h index 4d6cc7f..2dfa110 100644 --- a/scope.h +++ b/scope.h @@ -1,5 +1,5 @@ -#ifndef VARS_H -#define VARS_H +#ifndef SCOPE_H +#define SCOPE_H struct storage_location { enum { @@ -21,6 +21,8 @@ struct storage_location { struct type_def { const char* name; unsigned long long sz; + bool is_primitive; + bool is_signed; }; struct var_def { @@ -44,6 +46,7 @@ struct scope { void scope_push(struct scope** p_scope); void scope_pop(struct scope** p_scope); +void scope_destroy(struct scope* scope); void scope_install_default_types(struct scope* scope); bool scope_get_type( const struct scope* scope, diff --git a/type_checker.c b/type_checker.c new file mode 100644 index 0000000..f914c34 --- /dev/null +++ b/type_checker.c @@ -0,0 +1,74 @@ +#include "ast.h" +#include "scope.h" +#include +#include + +#define TYPE_PANIC(format, ...) {\ + fprintf(\ + stderr,\ + "ccc: type error: " format "\n" __VA_OPT__(,)\ + __VA_ARGS__);\ + exit(1);\ +} + +static struct scope* scope; + +static void type_check_group(struct group_node* node); + +static void type_check_expr(struct expr_node* node) {} + +static void type_check_var_decl(struct var_decl_node* node) {} + +static void type_check_return(struct return_node* node) {} + +static void type_check_stmt(struct stmt_node* node) { + switch (node->type) { + case STMT_EMPTY: + break; + case STMT_EXPR: + type_check_expr(&node->inner.expr); + break; + case STMT_VAR_DECL: + type_check_var_decl(&node->inner.var_decl); + break; + case STMT_RETURN: + type_check_return(&node->inner.return_); + break; + case STMT_GROUP: + type_check_group(&node->inner.group); + break; + } +} + +static void type_check_group(struct group_node* node) { + if (node->scope->next_out != scope) TYPE_PANIC("scopes are borked"); + scope = node->scope; + struct stmt_node* stmt = node->head; + while (stmt != NULL) { + type_check_stmt(stmt); + stmt = stmt->next; + } +} + +static void type_check_fn_decl(struct fn_decl_node* node) { + scope = node->scope; + type_check_group(&node->body); +} + +static void type_check_root(struct root_node* node) { + switch (node->type) { + case ROOT_FN_DECL: + type_check_fn_decl(&node->inner.fn_decl); + break; + } +} + +void type_check(struct ast* ast) { + scope = ast->root_scope; + + struct root_node* node = ast->root_node; + while (node != NULL) { + type_check_root(node); + node = node->next; + } +} -- cgit v1.2.3