From c87f5a8871edf6880b894a00b180c554ffd46d0a Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sun, 23 Mar 2025 22:29:11 +0200 Subject: start sketching out type system --- include/fwd/ast.h | 42 +++++++++++++++- include/fwd/scope.h | 82 +++++-------------------------- src/analyze.c | 31 ++++++++++-- src/ast.c | 10 ++++ src/lexer.l | 4 ++ src/parser.y | 88 +++++++++++++++++++++++++++++++-- src/scope.c | 139 ++++++++++++++++++++++++++++++++++------------------ 7 files changed, 268 insertions(+), 128 deletions(-) diff --git a/include/fwd/ast.h b/include/fwd/ast.h index a253901..36aa8c8 100644 --- a/include/fwd/ast.h +++ b/include/fwd/ast.h @@ -56,8 +56,18 @@ struct type { /** Possible AST node types. We reserve node 0 as an illegal value. */ enum ast_kind { - /** Creating new variable. */ - AST_LET = 1, + /** Trait definition */ + AST_TRAIT_DEF = 1, + /** Trait application */ + AST_TRAIT_APPLY, + /** Structure definition */ + AST_STRUCT_DEF, + /** Structure continuation */ + AST_STRUCT_CONT, + /** Import */ + AST_IMPORT, + /** Creating new variable */ + AST_LET, /** If statement */ AST_IF, /** Nil check */ @@ -141,6 +151,7 @@ enum ast_flag { AST_FLAG_ANALYZED = (1 << 0), AST_FLAG_PREANALYZIS = (1 << 1), AST_FLAG_NOMOVES = (1 << 2), + AST_FLAG_PUBLIC = (1 << 3), }; struct ast { @@ -161,6 +172,8 @@ struct ast { struct type *t; enum ast_flag flags; + struct ast *chain; + /* optional group */ struct ast *ol; struct ast *or; @@ -412,6 +425,31 @@ static inline bool is_trivially_copyable(struct type *type) #define gen_block(body, err, loc) \ gen2(AST_BLOCK, body, err, loc) +#define trait_id(x) return_s(x, AST_TRAIT_DEF) +#define trait_body(x) return_a1(x, AST_TRAIT_DEF) +#define gen_trait(id, body, loc) \ + gen_str1(AST_TRAIT_DEF, id, body, loc) + +#define trait_apply_id(x) return_s(x, AST_TRAIT_APPLY) +#define gen_trait_apply(id, loc) \ + gen_str(AST_TRAIT_DEF, id, loc) + +#define struct_id(x) return_s(x, AST_STRUCT_DEF) +#define struct_params(x) return_a0(x, AST_STRUCT_DEF) +#define struct_body(x) return_a1(x, AST_STRUCT_DEF) +#define gen_struct(id, params, body, loc) \ + gen_str2(AST_STRUCT_DEF, id, params, body, loc) + +#define import_file(x) return_s(x, AST_IMPORT) +#define gen_import(file, loc) \ + gen_str(AST_IMPORT, file, loc) + +#define struct_cont_id(x) return_s(x, AST_STRUCT_CONT) +#define struct_cont_params(x) return_a0(x, AST_STRUCT_CONT) +#define struct_cont_body(x) return_a1(x, AST_STRUCT_CONT) +#define gen_struct_cont(id, params, body, loc) \ + gen_str2(AST_STRUCT_CONT, id, params, body, loc) + #define str_val(x) return_s(x, AST_CONST_STR) #define gen_const_str(s, loc) \ gen_ast(AST_CONST_STR, NULL, NULL, NULL, NULL, NULL, s, 0, 0., loc) diff --git a/include/fwd/scope.h b/include/fwd/scope.h index e49eb0a..ebe0261 100644 --- a/include/fwd/scope.h +++ b/include/fwd/scope.h @@ -52,6 +52,8 @@ struct scope { struct scope *children; struct visible symbols; + struct visible traits; + struct visible types; enum scope_flags flags; }; @@ -106,80 +108,18 @@ int scope_add_scratch(struct scope *scope, struct ast *scratch); */ void scope_add_scope(struct scope *parent, struct scope *child); -/** - * Add variable to scope. - * Propagates public variables up the file scope chain as references. - * - * @param scope Scope to add variable to. - * @param var Variable to add to scope. - * @return \c 0 when succesful, non-zero otherwise. - */ -int scope_add_var(struct scope *scope, struct ast *var); - -/** - * Add type to scope. - * Propagates public types up the file scope chain as references. - * - * @param scope Scope to add type to. - * @param type Type to add to scope. - * @return \c 0 when succesful, non-zero otherwise. - */ -int scope_add_type(struct scope *scope, char *id, struct ast *type); -/** - * Add procedure to scope. - * Propagates public procedures up the file scope chain as references. - * - * @param scope Scope to add procedure to. - * @param proc Procedure to add to scope. - * @return \c 0 when succesful, non-zero otherwise. - */ -int scope_add_proc(struct scope *scope, struct ast *proc); - -/** - * Find a variable with ID in \p scope. - * @note Only looks in the current scope, so doesn't see anything outside - * of it. See file_scope_find_var(). - * - * @param scope Scope to look in. - * @param id ID of variable to find. - * @return Pointer to the AST node corresponding to \p id if found, - * otherwise \c NULL. - */ -struct ast *scope_find_var(struct scope *scope, char *id); +int scope_add_symbol(struct scope *scope, struct ast *symbol); struct ast *scope_find_symbol(struct scope *scope, char *id); - -/** - * Find a procedure with ID in \p scope. - * @note Only looks in the current scope, so doesn't see anything outside - * of it. See file_scope_find_proc(). - * - * @param scope Scope to look in. - * @param id ID of procedure to find. - * @return Pointer to the AST node corresponding to \p id if found, - * otherwise \c NULL. - */ -struct ast *scope_find_proc(struct scope *scope, char *id); - -/** - * Find a variable with ID visible to \p scope. - * - * @param scope Scope to look in. - * @param id ID of variable to find. - * @return Pointer to the AST node corresponding to \p id if found, - * otherwise \c NULL. - */ -struct ast *file_scope_find_var(struct scope *scope, char *id); struct ast *file_scope_find_symbol(struct scope *scope, char *id); -/** - * Find a procedure with ID visible to \p scope. - * - * @param scope Scope to look in. - * @param id ID of procedure to find. - * @return Pointer to the AST node corresponding to \p id if found, - * otherwise \c NULL. - */ -struct ast *file_scope_find_proc(struct scope *scope, char *id); +int scope_add_type(struct scope *scope, struct ast *type); +int scope_add_chain(struct scope *scope, struct ast *type); +struct ast *scope_find_type(struct scope *scope, char *id); +struct ast *file_scope_find_type(struct scope *scope, char *id); + +int scope_add_trait(struct scope *scope, struct ast *trait); +struct ast *scope_find_trait(struct scope *scope, char *id); +struct ast *file_scope_find_trait(struct scope *scope, char *id); #endif /* SCOPE_H */ diff --git a/src/analyze.c b/src/analyze.c index c33a901..0c06096 100644 --- a/src/analyze.c +++ b/src/analyze.c @@ -189,7 +189,7 @@ static int analyze_var(struct state *state, struct scope *scope, return -1; node->t = var_type(node); - return scope_add_var(scope, node); + return scope_add_symbol(scope, node); } static int analyze_let(struct state *state, struct scope *scope, @@ -478,7 +478,7 @@ static int analyze_err_branch(struct state *state, struct scope *scope, struct a struct ast *var = gen_var(strdup(err_branch_id(node)), NULL, node->loc); struct type *err_type = tgen_err(node->loc); var->t = err_type; - scope_add_var(branch_scope, var); + scope_add_symbol(branch_scope, var); return analyze(state, branch_scope, err_branch_body(node)); } @@ -607,9 +607,30 @@ static int analyze_type_list(struct state *state, struct scope *scope, int analyze_root(struct scope *scope, struct ast *root) { foreach_node(node, root) { - assert(node->k == AST_PROC_DEF); - if (scope_add_proc(scope, node)) - return -1; + switch (node->k) { + case AST_PROC_DEF: + if (scope_add_symbol(scope, node)) + return -1; + break; + + case AST_STRUCT_DEF: + if (scope_add_type(scope, node)) + return -1; + break; + + case AST_STRUCT_CONT: + if (scope_add_chain(scope, node)) + return -1; + break; + + case AST_TRAIT_DEF: + if (scope_add_trait(scope, node)) + return -1; + break; + + default: + abort(); + } } foreach_node(node, root) { diff --git a/src/ast.c b/src/ast.c index c236445..427c4c4 100644 --- a/src/ast.c +++ b/src/ast.c @@ -206,6 +206,11 @@ void ast_dump(int depth, struct ast *n) #define DUMP(x) case x: dump(depth, #x); break; switch (n->k) { + DUMP(AST_IMPORT); + DUMP(AST_TRAIT_DEF); + DUMP(AST_TRAIT_APPLY); + DUMP(AST_STRUCT_DEF); + DUMP(AST_STRUCT_CONT); DUMP(AST_CLOSURE); DUMP(AST_IF); DUMP(AST_NIL); @@ -636,6 +641,11 @@ const char *ast_str(enum ast_kind k) { #define CASE(x) case x: return #x; switch (k) { + CASE(AST_IMPORT); + CASE(AST_TRAIT_DEF); + CASE(AST_TRAIT_APPLY); + CASE(AST_STRUCT_DEF); + CASE(AST_STRUCT_CONT); CASE(AST_CLOSURE); CASE(AST_IF); CASE(AST_NIL); diff --git a/src/lexer.l b/src/lexer.l index e11b51e..e6a3f22 100644 --- a/src/lexer.l +++ b/src/lexer.l @@ -131,6 +131,10 @@ STRING \"(\\.|[^"\\])*\" "else" {return ELSE;} "nil" {return NIL;} "own" {return OWN;} +"pub" {return PUB;} + +"import" {return IMPORT;} +"continue" {return CONTINUE;} "error" {return ERROR;} diff --git a/src/parser.y b/src/parser.y index 68725a8..7b2c651 100644 --- a/src/parser.y +++ b/src/parser.y @@ -74,7 +74,10 @@ %token ELSE "else" %token NIL "nil" %token OWN "own" +%token PUB "pub" %token MUT "mut" +%token CONTINUE "continue" +%token IMPORT "import" %token ERROR "error" %token DOT "." %token SCOPE "::" @@ -97,11 +100,16 @@ %left "." "=>" "(" ")" %left "::" -%nterm top unit proc call closure var expr statement body +%nterm top unit proc proc_decl call closure var expr statement body %nterm vars exprs statements closures err trailing_closure %nterm opt_vars opt_exprs opt_statements opt_trailing_closure opt_err opt_error %nterm rev_vars rev_exprs rev_closures rev_statements -%nterm let if nil own unop binop construct +%nterm let if nil own unop binop construct import + +%nterm struct struct_cont trait +%nterm type_param type_params opt_type_params +%nterm behaviour behaviours opt_behaviours +%nterm member members opt_members %nterm type rev_types types opt_types @@ -203,7 +211,9 @@ proc : ID "(" opt_vars ")" body { $$ = gen_proc($[ID], $[opt_vars], NULL, $[body], src_loc(@$)); } - | ID "(" opt_vars ")" ";" { + +proc_decl + : ID "(" opt_vars ")" ";" { $$ = gen_proc($[ID], $[opt_vars], NULL, NULL, src_loc(@$)); } @@ -413,8 +423,80 @@ body $$ = gen_block($2, $3, src_loc(@$)); } +behaviour + : APPLY ";" { $$ = gen_trait_apply($1, src_loc(@$)); } + | proc_decl ";" + | proc + +behaviours + : behaviours behaviour { $$ = $1; $1->n = $2; } + | behaviour + +opt_behaviours + : behaviours + | { $$ = NULL; } + +member + : var ";" + | behaviour + +members + : members member { $$ = $1; $1->n = $2; } + | member + +opt_members + : members + | { $$ = NULL; } + +type_param + : ID ID { + struct type *t = tgen_id($1, src_loc(@1)); + $$ = gen_var($2, t, src_loc(@$)); + } + +type_params + : type_param "," type_params { + $$ = $1; $1->n = $3; + } + | type_param + +opt_type_params + : type_params + | { $$ = NULL; } + +struct + : ID "[" opt_type_params "]" "{" opt_members "}" { + $$ = gen_struct($1, $3, $6, src_loc(@$)); + } + +struct_cont + : "continue" ID "[" opt_type_params "]" "{" opt_behaviours "}" { + $$ = gen_struct_cont($2, $4, $7, src_loc(@$)); + } + +trait + : ID "{" opt_behaviours "}" { + $$ = gen_trait($1, $3, src_loc(@$)); + } + +import + : "import" STRING { + $$ = gen_import($2, src_loc(@$)); + } + top : proc + | proc_decl + | struct + | struct_cont + | import + | trait + | "pub" proc { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); } + | "pub" proc_decl { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); } + | "pub" struct { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); } + | "pub" struct_cont { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); } + | "pub" import { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); } + | "pub" trait { $$ = $2; ast_set_flags($$, AST_FLAG_PUBLIC); } | error { $$ = gen_empty(src_loc(@$)); parser->failed = true; diff --git a/src/scope.c b/src/scope.c index 367384a..fe35d58 100644 --- a/src/scope.c +++ b/src/scope.c @@ -29,6 +29,8 @@ struct scope *create_scope() scope->number = counter++; scope->symbols = visible_create(16); /* arbitrary number */ + scope->traits = visible_create(1); + scope->types = visible_create(1); return scope; } @@ -43,6 +45,8 @@ void destroy_scope(struct scope *scope) } visible_destroy(&scope->symbols); + visible_destroy(&scope->traits); + visible_destroy(&scope->types); struct scope *prev = scope->children, *cur; if (prev) @@ -54,17 +58,17 @@ void destroy_scope(struct scope *scope) free(scope); } -int scope_add_var(struct scope *scope, struct ast *var) +int scope_add_symbol(struct scope *scope, struct ast *symbol) { - assert(var->k == AST_VAR_DEF); - struct ast **exists = visible_insert(&scope->symbols, var_id(var), var); + assert(symbol->k == AST_VAR_DEF || symbol->k == AST_PROC_DEF); + struct ast **exists = visible_insert(&scope->symbols, symbol->s, symbol); if (!exists) { - internal_error("failed inserting var into scope"); + internal_error("failed inserting symbol into scope"); return -1; } - if (*exists != var) { - semantic_error(scope, var, "var redefined"); + if (*exists != symbol) { + semantic_error(scope, symbol, "symbol redefined"); semantic_info(scope, *exists, "previously here"); return -1; } @@ -72,17 +76,38 @@ int scope_add_var(struct scope *scope, struct ast *var) return 0; } -int scope_add_proc(struct scope *scope, struct ast *proc) +struct ast *scope_find_symbol(struct scope *scope, char *id) +{ + struct ast **v = visible_find(&scope->symbols, id); + if (!v) + return NULL; + + return *v; +} + +struct ast *file_scope_find_symbol(struct scope *scope, char *id) +{ + if (!scope) + return NULL; + + struct ast *found = scope_find_symbol(scope, id); + if (found) + return found; + + return file_scope_find_symbol(scope->parent, id); +} + +int scope_add_type(struct scope *scope, struct ast *type) { - assert(proc->k == AST_PROC_DEF); - struct ast **exists = visible_insert(&scope->symbols, proc_id(proc), proc); + assert(type->k == AST_STRUCT_DEF); + struct ast **exists = visible_insert(&scope->symbols, type->s, type); if (!exists) { - internal_error("failed inserting proc into scope"); + internal_error("failed inserting type into scope"); return -1; } - if (*exists != proc) { - semantic_error(scope, proc, "proc redefined"); + if (*exists != type) { + semantic_error(scope, type, "type redefined"); semantic_info(scope, *exists, "previously here"); return -1; } @@ -90,79 +115,99 @@ int scope_add_proc(struct scope *scope, struct ast *proc) return 0; } -struct ast *scope_find_proc(struct scope *scope, char *id) +int scope_add_chain(struct scope *scope, struct ast *type) { - struct ast **v = visible_find(&scope->symbols, id); - if (!v) - return NULL; + assert(type->k == AST_STRUCT_CONT); + struct ast *exists = file_scope_find_type(scope, type->s); + if (!exists) { + semantic_error(scope, type, "no previous definition"); + return -1; + } - struct ast *n = *v; - assert(n); + assert(exists->k == AST_STRUCT_DEF || exists->k == AST_STRUCT_CONT); + if (ast_flags(exists, AST_FLAG_PUBLIC) || !ast_flags(type, AST_FLAG_PUBLIC)) { + type->chain = exists; + struct ast **v = visible_insert(&scope->types, type->s, type); + if (!v) { + internal_error("failed inserting type into chain"); + return -1; + } - if (n->k != AST_PROC_DEF) - return NULL; + /* overwrite root */ + if (*v != type) + *v = type; - return n; -} - -struct ast *file_scope_find_proc(struct scope *scope, char *id) -{ - struct ast *n = file_scope_find_symbol(scope, id); - if (!n) - return NULL; + return 0; + } - if (n->k != AST_PROC_DEF) - return NULL; + struct ast *next = exists->chain; + while (next->k == AST_STRUCT_CONT && !ast_flags(next, AST_FLAG_PUBLIC)) { + exists = next; + next = next->chain; + } - return n; + exists->chain = type; + type->chain = exists; + return 0; } -struct ast *scope_find_symbol(struct scope *scope, char *id) +struct ast *scope_find_type(struct scope *scope, char *id) { - struct ast **v = visible_find(&scope->symbols, id); + struct ast **v = visible_find(&scope->types, id); if (!v) return NULL; return *v; } -struct ast *file_scope_find_symbol(struct scope *scope, char *id) +struct ast *file_scope_find_type(struct scope *scope, char *id) { if (!scope) return NULL; - struct ast *found = scope_find_symbol(scope, id); + struct ast *found = scope_find_type(scope, id); if (found) return found; - return file_scope_find_symbol(scope->parent, id); + return file_scope_find_type(scope->parent, id); } -struct ast *scope_find_var(struct scope *scope, char *id) +int scope_add_trait(struct scope *scope, struct ast *trait) { - struct ast **v = visible_find(&scope->symbols, id); - if (!v) - return NULL; + assert(trait->k == AST_TRAIT_DEF); + struct ast **exists = visible_insert(&scope->symbols, trait->s, trait); + if (!exists) { + internal_error("failed inserting trait into scope"); + return -1; + } - struct ast *n = *v; - assert(n); + if (*exists != trait) { + semantic_error(scope, trait, "trait redefined"); + semantic_info(scope, *exists, "previously here"); + return -1; + } - if (n->k != AST_VAR_DEF) + return 0; +} +struct ast *scope_find_trait(struct scope *scope, char *id) +{ + struct ast **v = visible_find(&scope->traits, id); + if (!v) return NULL; - return n; + return *v; } -struct ast *file_scope_find_var(struct scope *scope, char *id) +struct ast *file_scope_find_trait(struct scope *scope, char *id) { if (!scope) return NULL; - struct ast *found = scope_find_var(scope, id); + struct ast *found = scope_find_trait(scope, id); if (found) return found; - return file_scope_find_var(scope->parent, id); + return file_scope_find_trait(scope->parent, id); } void scope_add_scope(struct scope *parent, struct scope *child) -- cgit v1.2.3