diff options
| -rw-r--r-- | ast.c | 41 | ||||
| -rw-r--r-- | ast.h | 11 | ||||
| -rw-r--r-- | ccc.c | 22 | ||||
| -rw-r--r-- | ccc.h | 1 | ||||
| -rw-r--r-- | codegen.c | 87 | ||||
| -rw-r--r-- | dseg.c | 6 | ||||
| -rw-r--r-- | main.c | 10 | ||||
| -rw-r--r-- | parser.c | 56 | ||||
| -rw-r--r-- | scope.h | 19 | ||||
| -rw-r--r-- | type.h | 12 | ||||
| -rw-r--r-- | type_checker.c | 87 |
11 files changed, 224 insertions, 128 deletions
@@ -47,21 +47,52 @@ static void group_destroy(struct group_node* node) { free(node->scope); } +static void type_list_destroy(struct type_list* node) { + if (node->next != NULL) { + type_list_destroy(node->next); + free(node->next); + } +} + +static void type_destroy(struct type* node) { + switch (node->type) { + case TP_FN: + type_destroy(node->fn.return_type); + free(node->fn.return_type); + + if (node->fn.arg_types != NULL) { + type_list_destroy(node->fn.arg_types); + free(node->fn.arg_types); + } + break; + case TP_DATA: + case TP_PTR: + break; + } +} + static void decl_list_destroy(struct decl_list_node* node) { + type_destroy(&node->type); decl_destroy(node->head); free(node->head); } -static void fn_arg_destroy(struct arg_decl_node* node) { +static void arg_decl_destroy(struct arg_decl_node* node) { + type_destroy(&node->type); + if (node->next != NULL) { - fn_arg_destroy(node->next); + arg_decl_destroy(node->next); free(node->next); } } static void fn_decl_destroy(struct fn_decl_node* node) { + type_destroy(&node->type); + + free(node->name); + if (node->args != NULL) { - fn_arg_destroy(node->args); + arg_decl_destroy(node->args); free(node->args); } @@ -86,6 +117,9 @@ static void str_lit_destroy(struct str_lit_node* node) { } static void call_destroy(struct call_node* node) { + expr_destroy(node->expr); + free(node->expr); + if (node->args != NULL) { expr_list_destroy(node->args); free(node->args); @@ -111,6 +145,7 @@ static void paren_destroy(struct paren_node* node) { } static void cast_destroy(struct cast_node* node) { + type_destroy(&node->type); expr_destroy(node->expr); free(node->expr); } @@ -31,7 +31,7 @@ struct str_lit_node { }; struct var_ref_node { - struct var_def* def_ref; + const struct var_def* def_ref; }; struct decl_node { @@ -51,8 +51,7 @@ struct assign_node { }; struct call_node { - /* TODO: function pointers */ - struct fn_decl_node* fn_ref; /* borrowed */ + struct expr_node* expr; struct expr_list_node* args; }; @@ -126,15 +125,15 @@ struct arg_decl_node { }; struct fn_decl_node { - struct type return_type; - const char* name; + struct type type; + char* name; /* TODO: why is this borrowed? who owns it? */ struct arg_decl_node* args; struct group_node* body; struct scope* scope; }; struct return_node { - struct fn_decl_node* fn_ref; + struct var_def* fn_def; struct expr_list_node* ret_val; /* null to return void */ }; @@ -1,6 +1,7 @@ #include "ccc.h" #include <stdlib.h> #include <stdio.h> +#include <stdarg.h> void* ccc_alloc(integral_t sz) { void* ptr = calloc(1, sz); @@ -10,3 +11,24 @@ void* ccc_alloc(integral_t sz) { } return ptr; } + +char* ccc_sprintf(const char* format, ...) { + va_list args; + + va_start(args, format); + int req_sz = vsnprintf(NULL, 0, format, args); + va_end(args); + + if (req_sz < 0) { + fprintf(stderr, "ccc: formatting error\n"); + exit(1); + } + req_sz += 1; /* null terminated */ + char* buffer = ccc_alloc(req_sz); + + va_start(args, format); + vsnprintf(buffer, req_sz, format, args); + va_end(args); + + return buffer; +} @@ -9,5 +9,6 @@ typedef long long sintegral_t; typedef double floating_t; void* ccc_alloc(integral_t sz); +char* ccc_sprintf(const char* format, ...); #endif @@ -7,6 +7,7 @@ #include <stdlib.h> #include <stdio.h> #include <string.h> +#include <stddef.h> #define CGEN_PANIC(format, ...) {\ fprintf(\ @@ -32,7 +33,7 @@ static struct reg* MULDIV_OVERFLOW_REG = &RDX; static struct hash_map dseg; static struct scope* scope; -static const struct fn_decl_node* active_fn; +struct var_def* active_fn; static integral_t branch_counter = 0; static integral_t loop_counter = 0; @@ -90,8 +91,11 @@ static const struct data_type* get_effective_data_type( return type->data.data_type; case TP_PTR: return &long_long_type; + case TP_FN: + /* functions have size 1 I guess */ + return &char_type; } - CGEN_PANIC("unhandled type of type case"); + unreachable(); } static struct lval_def allocate_stack( @@ -132,11 +136,8 @@ static void release_temporary(FILE* outfile, const struct lval_def* tmp) { break; case STO_STACK: case STO_IMM: - case STO_FN: case STO_LABEL: break; - case STO_UNRESOLVED: - CGEN_PANIC("can't release unresolved storage"); } } @@ -149,9 +150,6 @@ static void emit_storage_loc( case STO_LABEL: fprintf(outfile, "%s", loc->label); break; - case STO_FN: - fprintf(outfile, "%s", loc->decl->name); - break; case STO_REG: if (sz > 4) fprintf(outfile, "%s", loc->reg->qword); else if (sz > 2) fprintf(outfile, "%s", loc->reg->dword); @@ -169,8 +167,6 @@ static void emit_storage_loc( case STO_IMM: fprintf(outfile, "0x%llx", loc->value); break; - case STO_UNRESOLVED: - CGEN_PANIC("can't emit unresolved storage location"); } } @@ -189,12 +185,8 @@ static bool locs_equal( return a->bp_offset == b->bp_offset; case STO_LABEL: return strcmp(a->label, b->label) == 0; - case STO_FN: - return a->decl == b->decl; - case STO_UNRESOLVED: - return false; } - CGEN_PANIC("unhandled storage type case"); + unreachable(); } static void emit_size_const(FILE* outfile, integral_t sz) { @@ -253,10 +245,8 @@ static void emit_label_lea( if (spill_reg) unspill_register(outfile, tmp_reg); else release_register(tmp_reg); return; - case STO_FN: case STO_IMM: case STO_LABEL: - case STO_UNRESOLVED: CGEN_PANIC("can't load label address into non-value storage"); } } @@ -331,9 +321,7 @@ static void emit_mov( break; case STO_LABEL: case STO_IMM: - case STO_FN: - case STO_UNRESOLVED: - CGEN_PANIC("can't move value into storage type"); + CGEN_PANIC("can't move value into non-storage type"); } fprintf(outfile, "\n"); } @@ -351,9 +339,7 @@ static void emit_cmp_zero(FILE* outfile, const struct lval_def* lval) { break; case STO_LABEL: case STO_IMM: - case STO_FN: - case STO_UNRESOLVED: - CGEN_PANIC("can't compare this storage type") + CGEN_PANIC("can't compare this non-storage type") } fprintf(outfile, ", 0\n"); } @@ -427,7 +413,7 @@ static void emit_var_ref( const struct lval_def* dst ) { if (dst != NULL) { - emit_mov(outfile, dst, &node->def_ref->loc); + emit_mov(outfile, dst, &node->def_ref->storage); } } @@ -439,7 +425,7 @@ static void emit_decl( ) { struct lval_def var_dst = allocate_stack(outfile, node->def_ref->type); - node->def_ref->loc = var_dst.loc; + node->def_ref->storage = var_dst.loc; fprintf(outfile, "\t; %s\n", node->def_ref->name); @@ -468,7 +454,7 @@ static void emit_assignment( struct var_ref_node* var_ref = &node->lval->inner.var_ref; lval_def = (struct lval_def) { .type = var_ref->def_ref->type, - .loc = var_ref->def_ref->loc, + .loc = var_ref->def_ref->storage, }; break; default: @@ -532,10 +518,14 @@ static void emit_call( } /* 3. `call <label>` */ - fprintf(outfile, "\tcall %s", node->fn_ref->name); - // TODO: this is kinda fukt we should probably keep an - // internal/external flag in the storage loc instead - if (node->fn_ref->body == NULL) fprintf(outfile, " WRT ..plt"); + /* TODO: support function pointers */ + if (node->expr->type != EXPR_VAR_REF) + CGEN_PANIC("function pointers are not supported"); + const struct var_def* fn_def = node->expr->inner.var_ref.def_ref; + fprintf(outfile, "\tcall "); + emit_storage_loc(outfile, &fn_def->storage, 0); + /* TODO: this could be a part of emit_storage_loc for labels */ + if (!fn_def->fn.resolved) fprintf(outfile, " WRT ..plt"); fprintf(outfile, "\n"); /* 4. `mov dst, rax` */ @@ -732,7 +722,7 @@ static void emit_return(FILE* outfile, const struct return_node* node) { outfile, node->ret_val, &(struct lval_def) { - .type = &active_fn->return_type, + .type = active_fn->type->fn.return_type, .loc = { .type = STO_REG, .reg = RV_REG, @@ -849,21 +839,24 @@ static void emit_stmt(FILE* outfile, const struct stmt_node* node) { } static void emit_fn_decl(FILE* outfile, const struct fn_decl_node* node) { - if (node->body == NULL) return; + if (!scope_get_var(scope, &active_fn, node->name)) + CGEN_PANIC("scopes are borked, missing symbol: '%s'", node->name); - if (active_fn != NULL) - CGEN_PANIC( - "can't define function %s inside function %s", - node->name, - active_fn->name); - active_fn = node; + const char* label = node->name; + active_fn->storage = (struct storage_location) { + .type = STO_LABEL, + .label = label, + }; - /* TODO: we need to account for the base pointer moving in var locs */ - fprintf(outfile, "%s:\n", node->name); - fprintf(outfile, "\tpush rbp\n"); - fprintf(outfile, "\tmov rbp, rsp\n"); + if (node->body == NULL) { + active_fn = NULL; + return; + } enter_scope(node->scope, 0); + fprintf(outfile, "%s:\n", label); + fprintf(outfile, "\tpush rbp\n"); + fprintf(outfile, "\tmov rbp, rsp\n"); sintegral_t spilled_bp_ofs = -16; // return address + spilled rbp struct arg_decl_node* arg_decl = node->args; @@ -872,7 +865,7 @@ static void emit_fn_decl(FILE* outfile, const struct fn_decl_node* node) { fprintf(outfile, "\t; %s\n", arg_def->name); struct lval_def arg_dst = allocate_stack(outfile, arg_def->type); - arg_def->loc = arg_dst.loc; + arg_def->storage = arg_dst.loc; struct storage_location arg_src; if (CALLING_CONV[i] != NULL) { @@ -900,8 +893,8 @@ static void emit_fn_decl(FILE* outfile, const struct fn_decl_node* node) { fprintf(outfile, "\tpop rbp\n"); fprintf(outfile, "\tret\n"); - active_fn = NULL; exit_scope(node->scope, false); + active_fn = NULL; } static void emit_root_node(FILE* outfile, const struct root_node* node) { @@ -924,7 +917,11 @@ void emit_code(struct ast* ast, const char* path) { for (; node != NULL; node = node->next) { if (node->type != ROOT_FN_DECL) continue; const struct fn_decl_node* fn = &node->inner.fn_decl; - if (fn->body != NULL) + struct var_def* fn_def; + if (!scope_get_var(scope, &fn_def, fn->name)) + CGEN_PANIC("use of undeclared function '%s'", fn->name); + + if (fn_def->fn.resolved) fprintf(outfile, "global %s\n", fn->name); else fprintf(outfile, "extern %s\n", fn->name); @@ -50,11 +50,7 @@ static void ent_assign_key(struct dseg_entry* ent) { switch (ent->type) { case ENT_STRING: integral_t strnum = string_counter++; - int req_sz = snprintf(NULL, 0, STRING_PATTERN, strnum); - if (req_sz < 0) CCC_PANIC; - req_sz += 1; // null terminator - ent->symbol = ccc_alloc(req_sz); - snprintf(ent->symbol, req_sz, STRING_PATTERN, strnum); + ent->symbol = ccc_sprintf(STRING_PATTERN, strnum); break; } } @@ -58,14 +58,10 @@ void test_parser(int argc, char** argv) { obj_file[fn_sz - 1] = 'o'; obj_file[fn_sz] = 0; - char cmd_buffer[2*fn_sz + 20]; - snprintf( - cmd_buffer, - sizeof(cmd_buffer), - "nasm -f elf64 %s -o %s", - asm_file, - obj_file); + char* cmd_buffer = + ccc_sprintf("nasm -f elf64 %s -o %s", asm_file, obj_file); int status = system(cmd_buffer); + free(cmd_buffer); if (status != 0) exit(status); } } @@ -5,6 +5,7 @@ #include <stdlib.h> #include <stdio.h> #include <string.h> +#include <stddef.h> #define PARSER_PANIC(format, ...) {\ fprintf(\ @@ -71,8 +72,10 @@ static struct type pointer_type_from_alias( }; case TP_PTR: return type_alias->type; + case TP_FN: + PARSER_PANIC("function pointers are not currently supported"); } - PARSER_PANIC("unhandled type of type case"); + unreachable(); } static void parse_type_ref(struct type* p_type) { @@ -196,20 +199,10 @@ static void parse_expr_list(struct expr_list_node* p_node) { } static void parse_expr_call(struct expr_node* p_node) { - switch (p_node->type) { - case EXPR_VAR_REF: - struct var_def* var_def = p_node->inner.var_ref.def_ref; - /* TODO: I would like to include functions in the type model rather than checking storage */ - if (var_def->loc.type != STO_FN) - PARSER_PANIC("called object is not a function"); - - p_node->inner.call.fn_ref = var_def->loc.decl; - break; - default: - PARSER_PANIC("expression is not callable"); - } - + struct expr_node* expr = ccc_alloc(sizeof(struct expr_node)); + *expr = *p_node; p_node->type = EXPR_CALL; + p_node->inner.call.expr = expr; p_node->inner.call.args = NULL; expect(TK_LPAREN); @@ -354,7 +347,6 @@ static void parse_decl(const struct type* type, struct decl_node* p_node) { p_node->def_ref = scope_define_var(scope, (struct var_def) { .type = type, .name = tok.data.ident, - .loc.type = STO_UNRESOLVED, }); if (p_node->def_ref == NULL) PARSER_PANIC("redefinition of '%s' in same scope", tok.data.ident); @@ -547,14 +539,17 @@ static void parse_stmt(struct stmt_node* p_node) { expect(TK_SEMI); } -static void parse_fn_arg(struct arg_decl_node* p_node) { +static void parse_arg_decl( + struct type_list* p_type, + struct arg_decl_node* p_node +) { parse_type_ref(&p_node->type); + p_type->type = &p_node->type; expect(TK_IDENT); p_node->def_ref = scope_define_var(scope, (struct var_def) { .type = &p_node->type, .name = tok.data.ident, - .loc.type = STO_UNRESOLVED, }); if (p_node->def_ref == NULL) PARSER_PANIC("redefinition of parameter '%s'", tok.data.ident); @@ -564,7 +559,8 @@ static void parse_fn_arg(struct arg_decl_node* p_node) { expect(TK_COMMA); p_node->next = ccc_alloc(sizeof(struct arg_decl_node)); - parse_fn_arg(p_node->next); + p_type->next = ccc_alloc(sizeof(struct type_list)); + parse_arg_decl(p_type->next, p_node->next); } } @@ -572,20 +568,21 @@ static void parse_fn_decl(struct fn_decl_node* p_node) { if (scope->next_out != NULL) PARSER_PANIC("functions can only be define in the root scope"); - parse_type_ref(&p_node->return_type); + p_node->type.type = TP_FN; + p_node->type.fn.return_type = ccc_alloc(sizeof(struct type)); + parse_type_ref(p_node->type.fn.return_type); expect(TK_IDENT); + p_node->name = tok.data.ident; /* redefinition is allowed */ - scope_define_var(scope, (struct var_def) { - .name = tok.data.ident, - .loc = { - .type = STO_FN, - .decl = p_node, - }, - }); - - p_node->name = tok.data.ident; + if (!scope_get_var(scope, NULL, p_node->name)) + scope_define_var(scope, (struct var_def) { + .type = &p_node->type, + /* name is owned by the var table */ + .name = strdup(p_node->name), + .fn = {.decl = p_node}, + }); expect(TK_LPAREN); @@ -595,7 +592,8 @@ static void parse_fn_decl(struct fn_decl_node* p_node) { peek_or_panic(); if (tok.type != TK_RPAREN) { p_node->args = ccc_alloc(sizeof(struct arg_decl_node)); - parse_fn_arg(p_node->args); + p_node->type.fn.arg_types = ccc_alloc(sizeof(struct type_list)); + parse_arg_decl(p_node->type.fn.arg_types, p_node->args); } expect(TK_RPAREN); @@ -5,35 +5,36 @@ #include "type.h" #include "hashmap.h" +struct type_alias { + const char* name; + struct type type; +}; + struct storage_location { enum { STO_REG, STO_LABEL, STO_STACK, STO_IMM, - /* I would like to solve functions using the type system - * and kill STO_FN and STO_UNRESOLVED in favor of STO_LABEL. */ - STO_FN, - STO_UNRESOLVED, } type; union { struct reg* reg; const char* label; sintegral_t bp_offset; integral_t value; - struct fn_decl_node* decl; }; }; -struct type_alias { - const char* name; - struct type type; +struct fn_def { + const struct fn_decl_node* decl; + bool resolved; }; struct var_def { const struct type* type; char* name; - struct storage_location loc; + struct fn_def fn; + struct storage_location storage; }; struct scope { @@ -9,10 +9,16 @@ struct data_type { bool is_floating; }; +struct fn_type { + struct type_list* arg_types; + struct type* return_type; +}; + struct type { enum { TP_DATA, TP_PTR, + TP_FN, } type; union { struct { @@ -23,9 +29,15 @@ struct type { const struct data_type* data_type; integral_t ptr_level; } pointer; + struct fn_type fn; }; }; +struct type_list { + const struct type* type; + struct type_list* next; +}; + extern const struct data_type void_type; extern const struct data_type char_type; extern const struct data_type short_type; diff --git a/type_checker.c b/type_checker.c index 00f57d0..f689a46 100644 --- a/type_checker.c +++ b/type_checker.c @@ -2,6 +2,8 @@ #include "scope.h" #include <stdio.h> #include <stdlib.h> +#include <string.h> +#include <stddef.h> #define TYPE_PANIC(format, ...) {\ fprintf(\ @@ -11,22 +13,42 @@ exit(1);\ } -static struct ast* ast_ref; +static const struct ast* ast_ref; static struct scope* scope; +static struct var_def* active_fn; static void type_check_expr(struct expr_node* node); static void type_check_stmt(struct stmt_node* node); static void type_check_group(struct group_node* node); -static const char* get_type_name(const struct type* type) { +static char* get_type_name(const struct type* type) { switch (type->type) { case TP_DATA: - return type->data.data_type->name; + return strdup(type->data.data_type->name); case TP_PTR: - /* TODO: this is a stub */ - return type->pointer.data_type->name; + char* stars = malloc((type->pointer.ptr_level + 1) * sizeof(char)); + memset(stars, '*', type->pointer.ptr_level); + stars[type->pointer.ptr_level] = 0; + char* name = + ccc_sprintf("%s%s", type->pointer.data_type->name, stars); + free(stars); + return name; + case TP_FN: + /* TODO: un-stub :'( */ + return "function"; } - TYPE_PANIC("unhandled type of type case"); + unreachable(); +} + +static bool is_callable(const struct type* type) { + switch (type->type) { + case TP_DATA: + case TP_PTR: + return false; + case TP_FN: + return true; + } + unreachable(); } static void assert_cast_compatible( @@ -116,25 +138,31 @@ static void type_check_expr_list(struct expr_list_node* node) { } static const struct type* resolve_call(struct call_node* node) { + type_check_expr(node->expr); + const struct fn_type* fn_type = &node->expr->resolved_type->fn; + if (!is_callable(node->expr->resolved_type)) + TYPE_PANIC( + "called object '%s' is not a function", + get_type_name(node->expr->resolved_type)); + type_check_expr_list(node->args); - /* TODO: enforce that the function has been type checked prior to this */ - struct arg_decl_node* arg_decl = node->fn_ref->args; + struct type_list* arg_type = fn_type->arg_types; struct expr_list_node* arg_eval = node->args; - while (arg_decl != NULL && arg_eval != NULL) { - const struct type* decl_type = &arg_decl->type; + while (arg_type != NULL && arg_eval != NULL) { + const struct type* decl_type = arg_type->type; const struct type* eval_type = arg_eval->expr->resolved_type; assert_cast_compatible(decl_type, eval_type); - arg_decl = arg_decl->next; + arg_type = arg_type->next; arg_eval = arg_eval->next; } - if (arg_decl != NULL) - TYPE_PANIC("missing arguments to function '%s'", node->fn_ref->name); + if (arg_type != NULL) + TYPE_PANIC("missing arguments to function"); if (arg_eval != NULL) - TYPE_PANIC("too many arguments to function '%s'", node->fn_ref->name); + TYPE_PANIC("too many arguments to function"); - return &node->fn_ref->return_type; + return fn_type->return_type; } static const struct type* resolve_unary(struct unary_node* node) { @@ -201,7 +229,8 @@ static void type_check_expr(struct expr_node* node) { } static void type_check_return(struct return_node* node) { - const struct type* return_type = &node->fn_ref->return_type; + if (active_fn == NULL) TYPE_PANIC("must be inside a function to return"); + const struct type* return_type = active_fn->type->fn.return_type; if (node->ret_val != NULL) { type_check_expr_list(node->ret_val); assert_cast_compatible(return_type, node->ret_val->resolved_type); @@ -209,7 +238,7 @@ static void type_check_return(struct return_node* node) { || return_type->data.data_type != &void_type) TYPE_PANIC( "void function '%s' should not return a value", - node->fn_ref->name); + active_fn->name); } static void type_check_if(struct if_node* node) { @@ -284,16 +313,26 @@ static void type_check_group(struct group_node* node) { /* TODO: type check redefinition arguments against each other */ /* TODO: wire the body to the definition either here or in the parser */ static void type_check_fn_decl(struct fn_decl_node* node) { - enter_scope(node->scope); - - for (struct arg_decl_node* arg_decl = node->args; - arg_decl != NULL; - arg_decl = arg_decl->next) - arg_decl->def_ref->type = &arg_decl->type; + if (!is_callable(&node->type)) + TYPE_PANIC("function definition does not have function type"); + if (active_fn != NULL) + TYPE_PANIC( + "can't define function '%s' inside function '%s'", + node->name, + active_fn->name); + if (!scope_get_var(scope, &active_fn, node->name)) + TYPE_PANIC("scopes are borked, missing symbol: '%s'", node->name); - if (node->body != NULL) type_check_group(node->body); + assert_cast_compatible(active_fn->type, &node->type); + enter_scope(node->scope); + if (node->body != NULL) { + type_check_group(node->body); + active_fn->fn.resolved = true; + } exit_scope(node->scope); + + active_fn = NULL; } static void type_check_root(struct root_node* node) { |
