diff options
| -rw-r--r-- | ast.c | 2 | ||||
| -rw-r--r-- | ast.h | 22 | ||||
| -rw-r--r-- | ccc.c | 12 | ||||
| -rw-r--r-- | ccc.h | 3 | ||||
| -rw-r--r-- | codegen.c | 110 | ||||
| -rw-r--r-- | parser.c | 165 | ||||
| -rw-r--r-- | scope.c | 139 | ||||
| -rw-r--r-- | scope.h | 37 | ||||
| -rw-r--r-- | type.c | 52 | ||||
| -rw-r--r-- | type.h | 43 | ||||
| -rw-r--r-- | type_checker.c | 110 |
11 files changed, 362 insertions, 333 deletions
@@ -119,6 +119,8 @@ static void expr_destroy(struct expr_node* node) { binary_destroy(&node->inner.binary); break; } + + if (node->resolved_type != NULL) free(node->resolved_type); } static void if_destroy(struct if_node* node) { @@ -1,15 +1,12 @@ #ifndef AST_H #define AST_H +#include "type.h" #include "scope.h" struct stmt_node; struct expr_node; -struct type_ref_node { - struct type_ref type; -}; - struct int_lit_node { integral_t val; }; @@ -31,7 +28,7 @@ struct var_ref_node { }; struct var_decl_node { - struct type_ref_node type; + struct type type; struct var_def* def_ref; struct expr_node* initial_value; }; @@ -94,7 +91,7 @@ struct expr_node { struct binary_node binary; } inner; - const struct type_def* resolved_type; + struct type* resolved_type; }; struct group_node { @@ -108,13 +105,11 @@ struct decl_list_node { }; struct fn_decl_node { - struct type_ref_node return_type; - char* name; + struct type return_type; + const char* name; struct decl_list_node* args; struct group_node body; struct scope* scope; - - const struct type_def* resolved_return_type; }; struct return_node { @@ -183,13 +178,6 @@ struct root_node { struct ast { struct root_node* root_node; struct scope* root_scope; - - /* nice shortcuts to have */ - const struct type_def* void_type; - const struct type_def* char_type; - const struct type_def* integral_type; - const struct type_def* decimal_type; - const struct type_def* pointer_type; }; void ast_destroy(struct ast* ast); @@ -0,0 +1,12 @@ +#include "ccc.h" +#include <stdlib.h> +#include <stdio.h> + +void* ccc_alloc(integral_t sz) { + void* ptr = calloc(1, sz); + if (ptr == NULL) { + fprintf(stderr, "ccc: out of memory\n"); + exit(1); + } + return ptr; +} @@ -2,8 +2,11 @@ #define CCC_H #define CCC_PANIC { perror("ccc"); exit(1); } +#define ARRAY_SZ(x) (sizeof(x) / sizeof(x[0])) typedef unsigned long long integral_t; typedef double floating_t; +void* ccc_alloc(integral_t sz); + #endif @@ -15,7 +15,7 @@ } struct lval_def { - const struct type_def* type; + const struct type* type; struct storage_location loc; }; @@ -57,7 +57,7 @@ static void exit_scope(struct scope* child_scope, bool save_bp_offset) { if (save_bp_offset) scope->bp_offset = child_scope->bp_offset; } -static struct lval_def allocate_register(const struct type_def* type) { +static struct lval_def allocate_register(const struct type* type) { return (struct lval_def) { .loc = { .type = STO_REG, @@ -67,12 +67,25 @@ static struct lval_def allocate_register(const struct type_def* type) { }; } +static const struct data_type* get_effective_data_type( + const struct type* type +) { + switch (type->type) { + case TP_DATA: + return type->data.data_type; + case TP_PTR: + return &long_long_type; + } + CGEN_PANIC("unhandled type of type case"); +} + static struct lval_def allocate_stack( FILE* outfile, - const struct type_def* type + const struct type* type ) { - fprintf(outfile, "\tsub rsp, %llu\n", type->sz); - scope->bp_offset += type->sz; + integral_t type_sz = get_effective_data_type(type)->sz; + fprintf(outfile, "\tsub rsp, %llu\n", type_sz); + scope->bp_offset += type_sz; return (struct lval_def) { .loc = { .type = STO_STACK, @@ -84,15 +97,18 @@ static struct lval_def allocate_stack( static struct lval_def allocate_temporary( FILE* outfile, - const struct type_def* type + const struct type* type ) { return allocate_stack(outfile, type); } static void deallocate_temporary(FILE* outfile, const struct lval_def* tmp) { if (tmp->loc.type == STO_STACK) { - fprintf(outfile, "\tadd rsp, %llu\n", tmp->type->sz); - scope->bp_offset -= tmp->type->sz; + integral_t type_sz = get_effective_data_type(tmp->type)->sz; + fprintf(outfile, "\tadd rsp, %llu\n", type_sz); + scope->bp_offset -= type_sz; + } else if (tmp->loc.type == STO_REG) { + /* TOOD: release the register back to the algo */ } } @@ -168,18 +184,19 @@ static void emit_mov( /* first optimization: if dst == src, emit nothing */ if (locs_equal(&dst->loc, src)) return; + integral_t dst_sz = get_effective_data_type(dst->type)->sz; switch (dst->loc.type) { case STO_REG: - if (src->type == STO_REG && dst->type->sz < 4) { + if (src->type == STO_REG && dst_sz < 4) { fprintf(outfile, "\tmovzx "); emit_storage_loc(outfile, &dst->loc, FULL_REG_SZ); } else { fprintf(outfile, "\tmov "); - emit_storage_loc(outfile, &dst->loc, dst->type->sz); + emit_storage_loc(outfile, &dst->loc, dst_sz); } fprintf(outfile, ", "); - emit_storage_loc(outfile, src, dst->type->sz); + emit_storage_loc(outfile, src, dst_sz); break; case STO_STACK: if (src->type == STO_STACK) { @@ -191,11 +208,11 @@ static void emit_mov( } fprintf(outfile, "\tmov "); - if (src->type == STO_IMM) emit_size_const(outfile, dst->type->sz); + if (src->type == STO_IMM) emit_size_const(outfile, dst_sz); - emit_storage_loc(outfile, &dst->loc, dst->type->sz); + emit_storage_loc(outfile, &dst->loc, dst_sz); fprintf(outfile, ", "); - emit_storage_loc(outfile, src, dst->type->sz); + emit_storage_loc(outfile, src, dst_sz); break; case STO_LABEL: case STO_IMM: @@ -208,13 +225,14 @@ static void emit_mov( static void emit_cmp_zero(FILE* outfile, const struct lval_def* lval) { fprintf(outfile, "\tcmp "); + integral_t type_sz = get_effective_data_type(lval->type)->sz; switch (lval->loc.type) { case STO_REG: - emit_storage_loc(outfile, &lval->loc, lval->type->sz); + emit_storage_loc(outfile, &lval->loc, type_sz); break; case STO_STACK: - emit_size_const(outfile, lval->type->sz); - emit_storage_loc(outfile, &lval->loc, lval->type->sz); + emit_size_const(outfile, type_sz); + emit_storage_loc(outfile, &lval->loc, type_sz); break; case STO_LABEL: case STO_IMM: @@ -225,13 +243,6 @@ static void emit_cmp_zero(FILE* outfile, const struct lval_def* lval) { fprintf(outfile, ", 0\n"); } -static inline struct lval_def make_stack_lval( - FILE* outfile, - const struct type_def* type -) { - return allocate_stack(outfile, type); -} - static void emit_expr( FILE* outfile, const struct expr_node* node, @@ -305,11 +316,12 @@ static void emit_var_decl( const struct var_decl_node* node ) { struct lval_def var_dst = - make_stack_lval(outfile, node->def_ref->resolved_type); + allocate_stack(outfile, node->def_ref->type); node->def_ref->loc = var_dst.loc; fprintf(outfile, "\t; '%s' lives in: ", node->def_ref->name); - emit_storage_loc(outfile, &var_dst.loc, var_dst.type->sz); + integral_t dst_sz = get_effective_data_type(var_dst.type)->sz; + emit_storage_loc(outfile, &var_dst.loc, dst_sz); fprintf(outfile, "\n"); if (node->initial_value != NULL) @@ -326,7 +338,7 @@ static void emit_assignment( case EXPR_VAR_REF: struct var_ref_node* var_ref = &node->lval->inner.var_ref; lval_def = (struct lval_def) { - .type = var_ref->def_ref->resolved_type, + .type = var_ref->def_ref->type, .loc = var_ref->def_ref->loc, }; break; @@ -349,7 +361,7 @@ static void emit_call( struct expr_list_node* arg_eval = node->args; while (arg_decl != NULL && arg_eval != NULL) { struct lval_def arg_dst = - make_stack_lval(outfile, arg_decl->decl->def_ref->resolved_type); + allocate_stack(outfile, arg_decl->decl->def_ref->type); emit_expr(outfile, arg_eval->expr, &arg_dst); arg_decl = arg_decl->next; @@ -368,11 +380,13 @@ static void emit_call( unsigned char arg_regnum = 0; arg_decl = node->called_fn_ref->args; while (arg_decl != NULL) { - const struct type_def* arg_type = - arg_decl->decl->def_ref->resolved_type; - arg_bp_offset += arg_type->sz; + const struct type* arg_type = + arg_decl->decl->def_ref->type; + arg_bp_offset += get_effective_data_type(arg_type)->sz; struct lval_def arg_dst; + /* TODO: if the convention register is used, + * will need to spill the current value */ if (arg_regnum < CC_N_REGS) arg_dst = (struct lval_def) { .type = arg_type, @@ -382,7 +396,7 @@ static void emit_call( }, }; else - arg_dst = make_stack_lval(outfile, arg_type); + arg_dst = allocate_stack(outfile, arg_type); emit_mov(outfile, &arg_dst, &(struct storage_location) { .type = STO_STACK, @@ -393,7 +407,8 @@ static void emit_call( fprintf(outfile, "\tcall %s\n", node->called_fn_ref->name); if (dst != NULL) { - if (node->called_fn_ref->resolved_return_type->sz == 0) + if (get_effective_data_type( + &node->called_fn_ref->return_type) == &void_type) CGEN_PANIC("can't assign the result of a void function"); emit_mov(outfile, dst, &RV_LOC); @@ -415,14 +430,15 @@ static void emit_unary( emit_expr(outfile, node->expr, dst); if (dst == NULL) return; + integral_t dst_sz = get_effective_data_type(dst->type)->sz; switch (node->op) { case UNARY_NEG: fprintf(outfile, "\tneg "); if (dst->loc.type == STO_STACK) - emit_size_const(outfile, dst->type->sz); + emit_size_const(outfile, dst_sz); - emit_storage_loc(outfile, &dst->loc, dst->type->sz); + emit_storage_loc(outfile, &dst->loc, dst_sz); fprintf(outfile, "\n"); break; } @@ -449,21 +465,22 @@ static void emit_binary( }; emit_expr(outfile, node->lhs, &lhs_dst); + integral_t dst_sz = get_effective_data_type(dst->type)->sz; switch (node->op) { case BINARY_ADD: fprintf(outfile, "\tadd "); - emit_storage_loc(outfile, &lhs_dst.loc, dst->type->sz); + emit_storage_loc(outfile, &lhs_dst.loc, dst_sz); fprintf(outfile, ", "); break; case BINARY_SUB: fprintf(outfile, "\tsub "); - emit_storage_loc(outfile, &lhs_dst.loc, dst->type->sz); + emit_storage_loc(outfile, &lhs_dst.loc, dst_sz); fprintf(outfile, ", "); break; case BINARY_MUL: fprintf(outfile, "\timul "); if (rhs_dst.loc.type == STO_STACK) - emit_size_const(outfile, dst->type->sz); + emit_size_const(outfile, dst_sz); break; case BINARY_DIV: /* nothing in the top half reg */ @@ -475,11 +492,11 @@ static void emit_binary( fprintf(outfile, "\tidiv "); if (rhs_dst.loc.type == STO_STACK) - emit_size_const(outfile, dst->type->sz); + emit_size_const(outfile, dst_sz); break; } - emit_storage_loc(outfile, &rhs_dst.loc, dst->type->sz); + emit_storage_loc(outfile, &rhs_dst.loc, dst_sz); fprintf(outfile, "\n"); /* TODO: deal with RDX overflow shit for imul and idiv */ @@ -527,9 +544,11 @@ static void emit_expr( static void emit_return(FILE* outfile, const struct return_node* node) { if (active_fn == NULL) CGEN_PANIC("must be inside a function to return"); + bool is_void_fn = + get_effective_data_type(&active_fn->return_type) == &void_type; if (node->ret_val != NULL) { - if (active_fn->resolved_return_type->sz == 0) + if (is_void_fn) CGEN_PANIC( "returning a value from void function %s", active_fn->name); @@ -538,9 +557,9 @@ static void emit_return(FILE* outfile, const struct return_node* node) { node->ret_val, &(struct lval_def) { .loc = RV_LOC, - .type = active_fn->resolved_return_type, + .type = &active_fn->return_type, }); - } else if (active_fn->resolved_return_type > 0) { + } else if (!is_void_fn) { CGEN_PANIC( "non-void function %s should return a value", active_fn->name); } @@ -680,7 +699,7 @@ static void emit_fn_decl(FILE* outfile, const struct fn_decl_node* node) { for (; arg_decl != NULL; arg_decl = arg_decl->next) { struct var_def* arg_def = arg_decl->decl->def_ref; struct lval_def arg_dst = - make_stack_lval(outfile, arg_def->resolved_type); + allocate_stack(outfile, arg_def->type); arg_def->loc = arg_dst.loc; struct storage_location arg_src; @@ -694,7 +713,8 @@ static void emit_fn_decl(FILE* outfile, const struct fn_decl_node* node) { .type = STO_STACK, .bp_offset = spilled_bp_ofs, }; - spilled_bp_ofs -= arg_def->resolved_type->sz; + integral_t arg_sz = get_effective_data_type(arg_def->type)->sz; + spilled_bp_ofs -= arg_sz; } emit_mov(outfile, &arg_dst, &arg_src); } @@ -1,6 +1,7 @@ -#include "parser.h" -#include "lexer.h" +#include "type.h" #include "scope.h" +#include "lexer.h" +#include "parser.h" #include <stdlib.h> #include <stdio.h> #include <string.h> @@ -19,15 +20,6 @@ static struct token tok; static struct scope* scope; -static void* protected_alloc(size_t sz) { - void* ptr = calloc(1, sz); - if (ptr == NULL) { - fprintf(stderr, "ccc: out of memory\n"); - exit(1); - } - return ptr; -} - static void unexpected_token(enum token_type expected) { /* TODO: print what token was expected */ PARSER_PANIC("unexpected token; expected %d", expected); @@ -61,33 +53,61 @@ static void expect_kw(const char* kw) { tok.data.ident = NULL; } -static void parse_type_ref(struct type_ref_node* p_node) { +static struct type pointer_type_from_alias( + const struct type_alias* type_alias +) { + switch (type_alias->type.type) { + case TP_DATA: + return (struct type) { + .type = TP_PTR, + .pointer.data_type = type_alias->type.data.data_type, + .pointer.ptr_level = 0, + }; + case TP_PTR: + return type_alias->type; + } + PARSER_PANIC("unhandled type of type case"); +} + +static void parse_type_ref(struct type* p_type) { /* TODO: modifiers, void rules, arrays, etc. */ /* TODO: struct, union, enum */ expect(TK_IDENT); - const struct type_def* type_def; - if (!scope_get_type( - scope, - &type_def, - &(struct type_key) { - .name = tok.data.ident, - /* TODO: parse modifiers */ - .how_long = 0, - .marked_signed = 0, - .marked_unsigned = 0, - })) - PARSER_PANIC("unknown type name: %s", tok.data.ident); + const struct data_type* primitive_type = NULL; + const struct type_alias* type_alias = NULL; - free(tok.data.ident); - p_node->type = (struct type_ref) { - .raw_type = type_def, - .ptr_level = 0, - }; + for (integral_t i = 0; primitive_types[i] != NULL; i++) { + if (strcmp(tok.data.ident, primitive_types[i]->name) == 0) { + primitive_type = primitive_types[i]; + break; + } + } + scope_get_type(scope, &type_alias, tok.data.ident); + if (primitive_type == NULL && type_alias == NULL) + PARSER_PANIC("unknown type name: '%s'", tok.data.ident); + + free(tok.data.ident); peek_or_panic(); + + if (tok.type == TK_STAR) { + if (type_alias != NULL) *p_type = pointer_type_from_alias(type_alias); + else *p_type = (struct type) { + .type = TP_PTR, + .pointer.data_type = primitive_type, + .pointer.ptr_level = 0, + }; + } else { + if (type_alias != NULL) *p_type = type_alias->type; + else *p_type = (struct type) { + .type = TP_DATA, + .data.data_type = primitive_type, + }; + } + while (tok.type == TK_STAR) { expect(TK_STAR); - p_node->type.ptr_level++; + p_type->pointer.ptr_level++; peek_or_panic(); } } @@ -124,7 +144,7 @@ static void parse_var_ref(struct var_ref_node* p_node) { } static void parse_expr_assign(struct expr_node* p_node) { - struct expr_node* lval = protected_alloc(sizeof(struct expr_node)); + struct expr_node* lval = ccc_alloc(sizeof(struct expr_node)); *lval = *p_node; p_node->type = EXPR_ASSIGN; @@ -132,20 +152,20 @@ static void parse_expr_assign(struct expr_node* p_node) { a_node->lval = lval; expect(TK_ASSIGN); - a_node->rval = protected_alloc(sizeof(struct expr_node)); + a_node->rval = ccc_alloc(sizeof(struct expr_node)); parse_expr(a_node->rval); } static void parse_expr_list(struct expr_list_node* p_node) { for (;;) { - p_node->expr = protected_alloc(sizeof(struct expr_node)); + p_node->expr = ccc_alloc(sizeof(struct expr_node)); parse_expr(p_node->expr); peek_or_panic(); if (tok.type != TK_COMMA) break; expect(TK_COMMA); - p_node->next = protected_alloc(sizeof(struct expr_list_node)); + p_node->next = ccc_alloc(sizeof(struct expr_list_node)); p_node = p_node->next; } } @@ -171,7 +191,7 @@ static void parse_expr_call(struct expr_node* p_node) { peek_or_panic(); if (tok.type != TK_RPAREN) { p_node->inner.call.args = - protected_alloc(sizeof(struct expr_list_node)); + ccc_alloc(sizeof(struct expr_list_node)); parse_expr_list(p_node->inner.call.args); } expect(TK_RPAREN); @@ -188,13 +208,13 @@ static void parse_unary(struct unary_node* p_node) { PARSER_PANIC("expected unary operator"); } - p_node->expr = protected_alloc(sizeof(struct expr_node)); + p_node->expr = ccc_alloc(sizeof(struct expr_node)); parse_expr(p_node->expr); } static void parse_expr_binary(struct expr_node* p_node) { - struct expr_node* lhs = protected_alloc(sizeof(struct expr_node)); - struct expr_node* rhs = protected_alloc(sizeof(struct expr_node)); + struct expr_node* lhs = ccc_alloc(sizeof(struct expr_node)); + struct expr_node* rhs = ccc_alloc(sizeof(struct expr_node)); *lhs = *p_node; *p_node = (struct expr_node) { @@ -279,7 +299,7 @@ static void parse_var_decl(struct var_decl_node* p_node) { expect(TK_IDENT); p_node->def_ref = scope_define_var(scope, (struct var_def) { - .type = &p_node->type.type, + .type = &p_node->type, .name = tok.data.ident, .loc.type = STO_UNRESOLVED, }); @@ -289,7 +309,7 @@ static void parse_var_decl(struct var_decl_node* p_node) { peek_or_panic(); if (tok.type == TK_ASSIGN) { expect(TK_ASSIGN); - p_node->initial_value = protected_alloc(sizeof(struct expr_node)); + p_node->initial_value = ccc_alloc(sizeof(struct expr_node)); parse_expr(p_node->initial_value); } } @@ -305,7 +325,7 @@ static void parse_return(struct return_node* p_node) { return; } - p_node->ret_val = protected_alloc(sizeof(struct expr_node)); + p_node->ret_val = ccc_alloc(sizeof(struct expr_node)); parse_expr(p_node->ret_val); } @@ -320,7 +340,7 @@ static void parse_group(struct group_node* p_node) { peek_or_panic(); if (tok.type == TK_RCURLY) break; - *pp_node = protected_alloc(sizeof(struct stmt_node)); + *pp_node = ccc_alloc(sizeof(struct stmt_node)); parse_stmt(*pp_node); pp_node = &((*pp_node)->next); } @@ -337,18 +357,18 @@ static void parse_if(struct if_node* p_node) { p_node->scope = scope; expect(TK_LPAREN); - p_node->cond = protected_alloc(sizeof(struct expr_node)); + p_node->cond = ccc_alloc(sizeof(struct expr_node)); parse_expr(p_node->cond); expect(TK_RPAREN); - p_node->true_branch = protected_alloc(sizeof(struct stmt_node)); + p_node->true_branch = ccc_alloc(sizeof(struct stmt_node)); parse_stmt(p_node->true_branch); peek_or_panic(); if (tok.type == TK_IDENT && strcmp(tok.data.ident, "else") == 0) { expect_kw("else"); - p_node->false_branch = protected_alloc(sizeof(struct stmt_node)); + p_node->false_branch = ccc_alloc(sizeof(struct stmt_node)); parse_stmt(p_node->false_branch); } @@ -362,31 +382,37 @@ static void parse_while(struct loop_node* p_node) { p_node->scope = scope; expect(TK_LPAREN); - p_node->cond = protected_alloc(sizeof(struct expr_node)); + p_node->cond = ccc_alloc(sizeof(struct expr_node)); parse_expr(p_node->cond); expect(TK_RPAREN); - p_node->body = protected_alloc(sizeof(struct stmt_node)); + p_node->body = ccc_alloc(sizeof(struct stmt_node)); parse_stmt(p_node->body); scope_pop(&scope); } +static bool is_type_token() { + if (tok.type != TK_IDENT) return false; + + /* check primitive types */ + for (integral_t i = 0; primitive_types[i] != NULL; i++) { + if (strcmp(tok.data.ident, primitive_types[i]->name) == 0) return true; + } + + /* check type aliases */ + return scope_get_type(scope, NULL, tok.data.ident); +} + static void parse_loop_init(struct loop_init_node* p_node) { peek_or_panic(); - if (tok.type != TK_IDENT - || !scope_get_type(scope, NULL, &(struct type_key) { - .name = tok.data.ident, - .how_long = 0, - .marked_signed = false, - .marked_unsigned = false, - })) { + if (!is_type_token()) { p_node->type = INIT_EXPR_LIST; - p_node->expr_list = protected_alloc(sizeof(struct expr_list_node)); + p_node->expr_list = ccc_alloc(sizeof(struct expr_list_node)); parse_expr_list(p_node->expr_list); } else { p_node->type = INIT_DECL; - p_node->decl = protected_alloc(sizeof(struct var_decl_node)); + p_node->decl = ccc_alloc(sizeof(struct var_decl_node)); parse_var_decl(p_node->decl); } } @@ -400,24 +426,24 @@ static void parse_for(struct loop_node* p_node) { expect(TK_LPAREN); peek_or_panic(); if (tok.type != TK_SEMI) { - p_node->init = protected_alloc(sizeof(struct loop_init_node)); + p_node->init = ccc_alloc(sizeof(struct loop_init_node)); parse_loop_init(p_node->init); } expect(TK_SEMI); peek_or_panic(); if (tok.type != TK_SEMI) { - p_node->cond = protected_alloc(sizeof(struct expr_node)); + p_node->cond = ccc_alloc(sizeof(struct expr_node)); parse_expr(p_node->cond); } expect(TK_SEMI); peek_or_panic(); if (tok.type != TK_RPAREN) { - p_node->incr = protected_alloc(sizeof(struct expr_node)); + p_node->incr = ccc_alloc(sizeof(struct expr_node)); parse_expr(p_node->incr); } expect(TK_RPAREN); - p_node->body = protected_alloc(sizeof(struct stmt_node)); + p_node->body = ccc_alloc(sizeof(struct stmt_node)); parse_stmt(p_node->body); scope_pop(&scope); @@ -450,15 +476,7 @@ static void parse_stmt(struct stmt_node* p_node) { p_node->type = STMT_RETURN; parse_return(&p_node->inner.return_); break; - } else if (scope_get_type( - scope, - NULL, - &(struct type_key) { - .name = tok.data.ident, - .how_long = 0, - .marked_signed = false, - .marked_unsigned = false, - })) { + } else if (is_type_token()) { p_node->type = STMT_VAR_DECL; parse_var_decl(&p_node->inner.var_decl); break; @@ -473,14 +491,14 @@ static void parse_stmt(struct stmt_node* p_node) { static void parse_decl_list(struct decl_list_node* p_node) { for (;;) { - p_node->decl = protected_alloc(sizeof(struct var_decl_node)); + p_node->decl = ccc_alloc(sizeof(struct var_decl_node)); parse_var_decl(p_node->decl); peek_or_panic(); if (tok.type != TK_COMMA) break; expect(TK_COMMA); - p_node->next = protected_alloc(sizeof(struct decl_list_node)); + p_node->next = ccc_alloc(sizeof(struct decl_list_node)); p_node = p_node->next; } } @@ -511,7 +529,7 @@ static void parse_fn_decl(struct fn_decl_node* p_node) { peek_or_panic(); if (tok.type != TK_RPAREN) { - p_node->args = protected_alloc(sizeof(struct decl_list_node)); + p_node->args = ccc_alloc(sizeof(struct decl_list_node)); parse_decl_list(p_node->args); } @@ -534,12 +552,11 @@ void parse(const char* path, struct ast* ast) { lexer_load(path); scope_push(&scope); ast->root_scope = scope; - scope_install_default_types(ast); struct root_node** p_node = &ast->root_node; for (;;) { - *p_node = protected_alloc(sizeof(struct root_node)); + *p_node = ccc_alloc(sizeof(struct root_node)); if (!parse_root(*p_node)) { free(*p_node); *p_node = NULL; @@ -1,14 +1,13 @@ #include "scope.h" -#include "ast.h" #include <stdlib.h> #include <stdio.h> #include <string.h> #define DEFAULT_SIZE 16 static void scope_init(struct scope* scope) { - scope->types = calloc(DEFAULT_SIZE, sizeof(struct type_def*)); + scope->types = ccc_alloc(DEFAULT_SIZE * sizeof(struct type_def*)); scope->type_cap = DEFAULT_SIZE; - scope->vars = calloc(DEFAULT_SIZE, sizeof(struct var_def*)); + scope->vars = ccc_alloc(DEFAULT_SIZE * sizeof(struct var_def*)); scope->var_cap = DEFAULT_SIZE; } @@ -47,41 +46,23 @@ static integral_t hash_name(const char* name, integral_t cap) { return hash; } -integral_t hash_type_key(const struct type_key* key, integral_t cap) { - integral_t hash = hash_name(key->name, cap); - hash = advance_hash(hash, key->how_long, cap); - hash = advance_hash(hash, key->marked_signed, cap); - hash = advance_hash(hash, key->marked_unsigned, cap); - return hash; -} - -static bool type_keys_equal( - const struct type_key* a, - const struct type_key* b -) { - return a->how_long == b->how_long - && a->marked_signed == b->marked_signed - && a->marked_unsigned == b->marked_unsigned - && strcmp(a->name, b->name) == 0; -} - -static struct type_def** type_cell( +static struct type_alias** type_cell( const struct scope* scope, - const struct type_key* key + const char* name ) { - integral_t orig_idx = hash_type_key(key, scope->type_cap); + integral_t orig_idx = hash_name(name, scope->type_cap); integral_t idx = orig_idx; do { if (scope->types[idx] == NULL - || type_keys_equal(key, &scope->types[idx]->key)) + || strcmp(name, scope->types[idx]->name) == 0) return &scope->types[idx]; } while ((idx = (idx + 1) % scope->type_cap) != orig_idx); return NULL; } static void rehash_types(struct scope* scope) { - struct type_def** old_types = scope->types; + struct type_alias** old_types = scope->types; integral_t old_cap = scope->type_cap; scope->type_cap *= 2; scope->types = calloc(scope->type_cap, sizeof(struct type_def*)); @@ -93,7 +74,7 @@ static void rehash_types(struct scope* scope) { for (integral_t i = 0; i < old_cap; i++) { if (old_types[i] == NULL) continue; - struct type_def** cell = type_cell(scope, &old_types[i]->key); + struct type_alias** cell = type_cell(scope, old_types[i]->name); if (cell == NULL) { fprintf(stderr, "ccc: types rehash failed, likely a bug\n"); exit(1); @@ -152,101 +133,13 @@ void scope_pop(struct scope** p_scope) { *p_scope = (*p_scope)->next_out; } -void scope_install_default_types(struct ast* ast) { - /* TODO: don't let people make void variables */ - ast->void_type = scope_define_type(ast->root_scope, (struct type_def) { - .key = { - .name = "void", - .how_long = 0, - .marked_signed = false, - .marked_unsigned = false, - }, - .is_signed = false, - .is_floating = false, - .sz = 0, - }); - - ast->char_type = scope_define_type(ast->root_scope, (struct type_def) { - .key = { - .name = "char", - .how_long = 0, - .marked_signed = false, - .marked_unsigned = false, - }, - .sz = 1, - .is_signed = true, /* implementation defined babyyyyyy */ - .is_floating = false, - }); - - scope_define_type(ast->root_scope, (struct type_def) { - .key = { - .name = "short", - .how_long = 0, - .marked_signed = false, - .marked_unsigned = false, - }, - .sz = 2, - .is_signed = true, - .is_floating = false, - }); - - scope_define_type(ast->root_scope, (struct type_def) { - .key = { - .name = "int", - .how_long = 0, - .marked_signed = false, - .marked_unsigned = false, - }, - .sz = 4, - .is_signed = true, - .is_floating = false, - }); - - ast->integral_type = scope_define_type(ast->root_scope, (struct type_def) { - .key = { - .name = "int", - .how_long = 1, - .marked_signed = false, - .marked_unsigned = false, - }, - .sz = 8, - .is_signed = true, - .is_floating = false, - }); - ast->pointer_type = ast->integral_type; /* TODO: support pointers */ - - scope_define_type(ast->root_scope, (struct type_def) { - .key = { - .name = "float", - .how_long = 0, - .marked_signed = false, - .marked_unsigned = false, - }, - .sz = 4, - .is_signed = true, - .is_floating = true, - }); - - ast->decimal_type = scope_define_type(ast->root_scope, (struct type_def) { - .key = { - .name = "double", - .how_long = 0, - .marked_signed = false, - .marked_unsigned = false, - }, - .sz = 8, - .is_signed = true, - .is_floating = true, - }); -} - bool scope_get_type( const struct scope* scope, - const struct type_def** p_entry, - const struct type_key* key + const struct type_alias** p_entry, + const char* name ) { for (; scope != NULL; scope = scope->next_out) { - struct type_def** cell = type_cell(scope, key); + struct type_alias** cell = type_cell(scope, name); if (cell == NULL || *cell == NULL) continue; if (p_entry != NULL) *p_entry = *cell; return true; @@ -254,20 +147,20 @@ bool scope_get_type( return false; } -const struct type_def* scope_define_type( +const struct type_alias* scope_define_type( struct scope* scope, - struct type_def type + struct type_alias type ) { - struct type_def** cell = type_cell(scope, &type.key); + struct type_alias** cell = type_cell(scope, type.name); while (cell == NULL) { rehash_types(scope); - cell = type_cell(scope, &type.key); + cell = type_cell(scope, type.name); } /* redefinition leaks memory, so refuse */ if (*cell != NULL) return NULL; - *cell = calloc(1, sizeof(struct type_def)); + *cell = calloc(1, sizeof(struct type_alias)); if (*cell == NULL) { fprintf(stderr, "ccc: out of memory\n"); exit(1); @@ -2,6 +2,7 @@ #define SCOPE_H #include "ccc.h" +#include "type.h" struct storage_location { enum { @@ -23,34 +24,19 @@ struct storage_location { }; }; -struct type_ref { - const struct type_def* raw_type; - unsigned char ptr_level; -}; - -struct type_key { - char* name; - unsigned char how_long; - bool marked_unsigned; - bool marked_signed; -}; - -struct type_def { - struct type_key key; - bool is_signed; - bool is_floating; - integral_t sz; +struct type_alias { + const char* name; + struct type type; }; struct var_def { - const struct type_ref* type; + const struct type* type; char* name; struct storage_location loc; - const struct type_def* resolved_type; }; struct scope { - struct type_def** types; + struct type_alias** types; integral_t type_sz; integral_t type_cap; @@ -62,19 +48,16 @@ struct scope { integral_t bp_offset; }; -struct ast; - 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 ast* ast); bool scope_get_type( const struct scope* scope, - const struct type_def** p_entry, - const struct type_key* key); -const struct type_def* scope_define_type( + const struct type_alias** p_entry, + const char* name); +const struct type_alias* scope_define_type( struct scope* scope, - struct type_def type); + struct type_alias type); bool scope_get_var( const struct scope* scope, struct var_def** p_entry, @@ -0,0 +1,52 @@ +#include "type.h" +#include <stddef.h> + +const struct data_type void_type = { + .name = "void", + .sz = 0, + .is_floating = false, +}; +const struct data_type char_type = { + .name = "char", + .sz = 1, + .is_floating = false, +}; +const struct data_type short_type = { + .name = "short", + .sz = 2, + .is_floating = false, +}; +const struct data_type int_type = { + .name = "int", + .sz = 4, + .is_floating = false, +}; +const struct data_type long_type = { + .name = "long", + .sz = 8, + .is_floating = false, +}; +const struct data_type long_long_type = { + .name = "long long", + .sz = 8, + .is_floating = false, +}; +const struct data_type float_type = { + .name = "float", + .sz = 4, + .is_floating = true, +}; +const struct data_type double_type = { + .name = "double", + .sz = 8, + .is_floating = true, +}; + +const struct data_type* integral_type = &long_type; +const struct data_type* floating_type = &double_type; +const struct data_type* character_type = &char_type; +const struct data_type* primitive_types[] = { + &void_type, &char_type, &short_type, &int_type, &long_type, &long_long_type, + &float_type, &double_type, + NULL +}; @@ -0,0 +1,43 @@ +#ifndef TYPE_H +#define TYPE_H + +#include "ccc.h" + +struct data_type { + const char* name; + integral_t sz; + bool is_floating; +}; + +struct type { + enum { + TP_DATA, + TP_PTR, + } type; + union { + struct { + const struct data_type* data_type; + bool is_signed; + } data; + struct { + const struct data_type* data_type; + integral_t ptr_level; + } pointer; + }; +}; + +extern const struct data_type void_type; +extern const struct data_type char_type; +extern const struct data_type short_type; +extern const struct data_type int_type; +extern const struct data_type long_type; +extern const struct data_type long_long_type; +extern const struct data_type float_type; +extern const struct data_type double_type; + +extern const struct data_type* integral_type; +extern const struct data_type* floating_type; +extern const struct data_type* character_type; +extern const struct data_type* primitive_types[]; + +#endif diff --git a/type_checker.c b/type_checker.c index 5905c83..ccd816f 100644 --- a/type_checker.c +++ b/type_checker.c @@ -18,17 +18,28 @@ 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) { + switch (type->type) { + case TP_DATA: + return type->data.data_type->name; + case TP_PTR: + /* TODO: this is a stub */ + return type->pointer.data_type->name; + } + TYPE_PANIC("unhandled type of type case"); +} + static void assert_cast_compatible( - const struct type_def* lval_type, - const struct type_def* rval_type + const struct type* lval_type, + const struct type* rval_type ) { /* TODO: impl */ /* TODO: we should also insert cast nodes eventually */ if (false) { TYPE_PANIC( "cannot assign value of type '%s' to '%s'", - lval_type->key.name, - rval_type->key.name); + get_type_name(lval_type), + get_type_name(rval_type)); } } @@ -47,45 +58,52 @@ static void exit_scope(struct scope* child_scope) { scope = child_scope->next_out; } -static const struct type_def* resolve_type_ref(struct type_ref_node* node) { - /* TODO: support pointers and such */ - if (node->type.raw_type == NULL) TYPE_PANIC("use of unresolved type"); - if (node->type.ptr_level > 0) return ast_ref->pointer_type; - return node->type.raw_type; -} - -static const struct type_def* resolve_int_lit(struct int_lit_node* node) { - return ast_ref->integral_type; -} - -static const struct type_def* resolve_float_lit(struct float_lit_node* node) { - return ast_ref->decimal_type; +static struct type* allocate_data_type( + const struct data_type* data_type, + bool is_unsigned +) { + if (is_unsigned && data_type->is_floating) + TYPE_PANIC("floating type '%s' cannot be unsigned", data_type->name); + + struct type* type = ccc_alloc(sizeof(struct type)); + type->type = TP_DATA; + type->data.data_type = data_type; + type->data.is_signed = !is_unsigned; + return type; } -static const struct type_def* resolve_char_lit(struct char_lit_node* node) { - return ast_ref->char_type; +static struct type* allocate_pointer_type( + const struct data_type* data_type, + integral_t ptr_level +) { + struct type* type = ccc_alloc(sizeof(struct type)); + type->type = TP_PTR; + type->pointer.data_type = data_type; + type->pointer.ptr_level = ptr_level; + return type; } -static const struct type_def* resolve_str_lit(struct str_lit_node* node) { - return ast_ref->pointer_type; +static struct type* copy_type(const struct type* source_type) { + struct type* type = ccc_alloc(sizeof(struct type)); + *type = *source_type; + return type; } -static const struct type_def* resolve_var_ref(struct var_ref_node* node) { - if (node->def_ref->resolved_type == NULL) - TYPE_PANIC("variable '%s' has unresolved type.", node->def_ref->name); - return node->def_ref->resolved_type; +static struct type* resolve_var_ref(struct var_ref_node* node) { + if (node->def_ref->type == NULL) + TYPE_PANIC("variable '%s' has undefined type.", node->def_ref->name); + return copy_type(node->def_ref->type); } static void type_check_var_decl(struct var_decl_node* node) { - const struct type_def* lval_type = resolve_type_ref(&node->type); - node->def_ref->resolved_type = lval_type; + node->def_ref->type = &node->type; if (node->initial_value != NULL) { type_check_expr(node->initial_value); - assert_cast_compatible(lval_type, node->initial_value->resolved_type); + assert_cast_compatible(&node->type, node->initial_value->resolved_type); } } -static const struct type_def* resolve_assign(struct assign_node* node) { +static struct type* resolve_assign(struct assign_node* node) { switch (node->lval->type) { case EXPR_VAR_REF: break; @@ -95,14 +113,14 @@ static const struct type_def* resolve_assign(struct assign_node* node) { type_check_expr(node->lval); type_check_expr(node->rval); - const struct type_def* lval_type = node->lval->resolved_type; - const struct type_def* rval_type = node->rval->resolved_type; + const struct type* lval_type = node->lval->resolved_type; + const struct type* rval_type = node->rval->resolved_type; assert_cast_compatible(lval_type, rval_type); - return lval_type; + return copy_type(lval_type); } -static const struct type_def* resolve_call(struct call_node* node) { +static struct type* resolve_call(struct call_node* node) { struct decl_list_node* arg_decl = node->called_fn_ref->args; struct expr_list_node* arg_eval = node->args; while (arg_decl != NULL && arg_eval != NULL) { @@ -110,10 +128,10 @@ static const struct type_def* resolve_call(struct call_node* node) { TYPE_PANIC("C does not support default arguments"); type_check_var_decl(arg_decl->decl); - const struct type_def* decl_type = - arg_decl->decl->def_ref->resolved_type; + const struct type* decl_type = + arg_decl->decl->def_ref->type; type_check_expr(arg_eval->expr); - const struct type_def* eval_type = arg_eval->expr->resolved_type; + const struct type* eval_type = arg_eval->expr->resolved_type; assert_cast_compatible(decl_type, eval_type); arg_decl = arg_decl->next; @@ -124,36 +142,36 @@ static const struct type_def* resolve_call(struct call_node* node) { "mismatched argument count in call to '%s'", node->called_fn_ref->name); - return resolve_type_ref(&node->called_fn_ref->return_type); + return copy_type(&node->called_fn_ref->return_type); } -static const struct type_def* resolve_unary(struct unary_node* node) { +static struct type* resolve_unary(struct unary_node* node) { type_check_expr(node->expr); /* TODO: delegate by individual operation to prohibit shit like -"yes" */ - return node->expr->resolved_type; + return copy_type(node->expr->resolved_type); } -static const struct type_def* resolve_binary(struct binary_node* node) { +static struct type* resolve_binary(struct binary_node* node) { /* TODO: math rules and such lol */ type_check_expr(node->lhs); type_check_expr(node->rhs); assert_cast_compatible(node->lhs->resolved_type, node->rhs->resolved_type); - return node->lhs->resolved_type; + return copy_type(node->lhs->resolved_type); } static void type_check_expr(struct expr_node* node) { switch (node->type) { case EXPR_INT_LIT: - node->resolved_type = resolve_int_lit(&node->inner.int_lit); + node->resolved_type = allocate_data_type(integral_type, false); break; case EXPR_FLOAT_LIT: - node->resolved_type = resolve_float_lit(&node->inner.float_lit); + node->resolved_type = allocate_data_type(floating_type, false); break; case EXPR_CHAR_LIT: - node->resolved_type = resolve_char_lit(&node->inner.char_lit); + node->resolved_type = allocate_data_type(character_type, false); break; case EXPR_STR_LIT: - node->resolved_type = resolve_str_lit(&node->inner.str_lit); + node->resolved_type = allocate_pointer_type(character_type, 1); break; case EXPR_VAR_REF: node->resolved_type = resolve_var_ref(&node->inner.var_ref); @@ -253,8 +271,6 @@ static void type_check_group(struct group_node* node) { static void type_check_fn_decl(struct fn_decl_node* node) { enter_scope(node->scope); - node->resolved_return_type = resolve_type_ref(&node->return_type); - for (struct decl_list_node* arg_decl = node->args; arg_decl != NULL; arg_decl = arg_decl->next) |