diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/analyze.c | 298 | ||||
| -rw-r--r-- | src/ast.c | 106 | ||||
| -rw-r--r-- | src/debug.c | 91 | ||||
| -rw-r--r-- | src/scope.c | 8 |
4 files changed, 490 insertions, 13 deletions
diff --git a/src/analyze.c b/src/analyze.c index 6efd60f..900e771 100644 --- a/src/analyze.c +++ b/src/analyze.c @@ -4,11 +4,307 @@ #include <fwd/analyze.h> #include <assert.h> +struct state { +}; + +static int analyze(struct state *state, struct scope *scope, struct ast *node); +static int analyze_list(struct state *state, struct scope *scope, struct ast *nodes); + +static int analyze_type(struct state *state, struct scope *scope, struct type *type); +static int analyze_type_list(struct state *state, struct scope *scope, struct type *types); + +static int analyze_proc(struct state *state, struct scope *scope, struct ast *node) +{ + (void)state; + (void)scope; + + struct scope *proc_scope = create_scope(); + if (!proc_scope) { + internal_error("failed allocating proc scope"); + return -1; + } + + scope_add_scope(scope, proc_scope); + + struct state proc_state = {}; + if (analyze_list(&proc_state, proc_scope, proc_params(node))) + return -1; + + struct type *callable = tgen_callable(NULL, node->loc); + if (!callable) { + internal_error("failed allocating proc type"); + return -1; + } + + foreach_node(param, proc_params(node)) { + type_append(&callable->t0, clone_type(param->t)); + } + + node->t = callable; + + return analyze(&proc_state, proc_scope, proc_body(node)); +} + +static int analyze_unop(struct state *state, struct scope *scope, struct ast *node) +{ + assert(false); + return 0; +} + +static int analyze_block(struct state *state, struct scope *scope, struct ast *node) +{ + struct scope *block_scope = create_scope(); + if (!block_scope) { + internal_error("failed to allocate block scope"); + return -1; + } + + scope_add_scope(scope, block_scope); + if (analyze_list(state, block_scope, block_body(node))) + return -1; + + node->t = ast_last(block_body(node))->t; + return 0; +} + +static int analyze_var(struct state *state, struct scope *scope, struct ast *node) +{ + if (analyze_type(state, scope, var_type(node))) + return -1; + + node->t = var_type(node); + return scope_add_var(scope, node); +} + +static int analyze_let(struct state *state, struct scope *scope, struct ast *node) +{ + if (analyze(state, scope, let_var(node))) + return -1; + + if (analyze(state, scope, let_expr(node))) + return -1; + + struct type *l = (let_var(node))->t; + struct type *r = (let_expr(node))->t; + if (!types_match(l, r)) { + type_mismatch(scope, node, l, r); + return -1; + } + + node->t = l; + return 0; +} + +static int analyze_init(struct state *state, struct scope *scope, struct ast *node) +{ + if (analyze_type_list(state, scope, init_args(node))) + return -1; + + if (analyze(state, scope, init_body(node))) + return -1; + + /** @todo check that all parameters match, though that requires that the + * type is defined in fwd and not in C++, so this might have to wait a + * bit */ + node->t = tgen_construct(init_id(node), init_args(node), node->loc); + if (!node->t) { + internal_error("failed allocating type for construct"); + return -1; + } + + return 0; +} + +static int analyze_call(struct state *state, struct scope *scope, struct ast *node) +{ + struct ast *expr = call_expr(node); + if (analyze(state, scope, expr)) + return -1; + + if (!is_callable(expr->t)) { + semantic_error(scope, node, "expected callable expression"); + return -1; + } + + struct type *types = callable_types(expr->t); + struct ast *args = call_args(node); + if (analyze_list(state, scope, args)) + return -1; + + size_t expected = type_list_len(types); + size_t got = ast_list_len(args); + if (expected != got) { + semantic_error(scope, node, "expected %d params, got %d", expected, got); + return -1; + } + + struct type *type = types; + foreach_node(arg, args) { + if (!types_match(type, arg->t)) { + type_mismatch(scope, node, type, arg->t); + return -1; + } + + type = type->n; + } + + node->t = tgen_void(node->loc); + if (!node->t) { + internal_error("failed allocating void type for call"); + return -1; + } + + return 0; +} + +static int analyze_id(struct state *state, struct scope *scope, struct ast *node) +{ + struct ast *found = file_scope_find_symbol(scope, id_str(node)); + if (!found) { + semantic_error(scope, node, "no symbol named \"%s\"", id_str(node)); + return -1; + } + + /* kind of hacky, functions are given their type before they've been + * analyzed fully, this enables recursion */ + if (!found->t && !ast_flags(found, AST_FLAG_ANALYZED)) { + assert(found->k == AST_PROC_DEF); + /* a proc def will use its own state and scope, but pass these + * on in case the analysis wants to print errors or something + */ + if (analyze(state, scope, found)) + return -1; + } + + node->t = found->t; + return 0; +} + +static int analyze_closure(struct state *state, struct scope *scope, struct ast *node) +{ + struct scope *closure_scope = create_scope(); + if (!closure_scope) { + internal_error("failed allocating closure scope"); + return -1; + } + + scope_add_scope(scope, closure_scope); + + if (analyze_list(state, closure_scope, closure_bindings(node))) + return -1; + + if (analyze(state, closure_scope, closure_body(node))) + return -1; + + struct type *callable = tgen_callable(NULL, node->loc); + if (!callable) { + internal_error("failed allocating closure type"); + return -1; + } + + /** @todo use analysis to figure out if this closure can be called + * multiple times or just once */ + + foreach_node(binding, closure_bindings(node)) { + type_append(&callable->t0, clone_type(binding->t)); + } + + node->t = callable; + return 0; +} + +static int analyze(struct state *state, struct scope *scope, struct ast *node) +{ + if (!node) + return 0; + + if (ast_flags(node, AST_FLAG_ANALYZED)) { + assert(node->t); + return 0; + } + + if (ast_flags(node, AST_FLAG_PREANALYZIS)) { + semantic_error(scope, node, "semantic loop detected"); + return -1; + } + + ast_set_flags(node, AST_FLAG_PREANALYZIS); + + if (!node->scope) + node->scope = scope; + + int ret = 0; + if (is_unop(node)) { + ret = analyze_unop(state, scope, node); + goto out; + } + + switch (node->k) { + case AST_PROC_DEF: ret = analyze_proc (state, scope, node); break; + case AST_VAR_DEF: ret = analyze_var (state, scope, node); break; + case AST_BLOCK: ret = analyze_block (state, scope, node); break; + case AST_LET: ret = analyze_let (state, scope, node); break; + case AST_INIT: ret = analyze_init (state, scope, node); break; + case AST_CALL: ret = analyze_call (state, scope, node); break; + case AST_ID: ret = analyze_id (state, scope, node); break; + case AST_CLOSURE: ret = analyze_closure (state, scope, node); break; + default: + internal_error("missing ast analysis"); + return -1; + } + +out: + if (ret) + return ret; + + assert(node->t); + assert(node->scope); + ast_set_flags(node, AST_FLAG_ANALYZED); + return 0; +} + +static int analyze_list(struct state *state, struct scope *scope, struct ast *nodes) +{ + foreach_node(node, nodes) { + if (analyze(state, scope, node)) + return -1; + } + + return 0; +} + +static int analyze_type(struct state *state, struct scope *scope, struct type *type) +{ + /* for now, let's just say all types are fine as they are, specified by + * the user. */ + (void)state; + (void)scope; + (void)type; + return 0; +} + +static int analyze_type_list(struct state *state, struct scope *scope, struct type *types) +{ + foreach_type(type, types) { + if (analyze_type(state, scope, type)) + return -1; + } + + return 0; +} + int analyze_root(struct scope *scope, struct ast *root) { foreach_node(node, root) { assert(node->k == AST_PROC_DEF); - scope_add_proc(scope, node); + if (scope_add_proc(scope, node)) + return -1; + } + + foreach_node(node, root) { + struct state state = {}; + if (analyze(&state, scope, node)) + return -1; } return 0; @@ -133,6 +133,9 @@ struct type *tgen_type(enum type_kind kind, void ast_append(struct ast **list, struct ast *elem) { + assert(list); + assert(elem); + struct ast *cur = *list; if (!cur) { *list = elem; @@ -145,6 +148,23 @@ void ast_append(struct ast **list, struct ast *elem) cur->n = elem; } +void type_append(struct type **list, struct type *elem) +{ + assert(list); + assert(elem); + + struct type *cur = *list; + if (!cur) { + *list = elem; + return; + } + + while (cur->n) + cur = cur->n; + + cur->n = elem; +} + struct ast *ast_prepend(struct ast *list, struct ast *elem) { elem->n = list; @@ -295,6 +315,41 @@ struct ast *clone_ast_list(struct ast *root) return new_root; } +struct type *clone_type(struct type *type) +{ + if (!type) + return NULL; + + struct type *new = create_empty_type(); + if (!new) + return NULL; + + new->k = type->k; + if (type->id && !(new->id = strdup(type->id))) + return NULL; + + if (type->t0 && !(new->t0 = clone_type_list(type->t0))) + return NULL; + + return new; +} + +struct type *clone_type_list(struct type *root) +{ + struct type *n = root, *new_root = NULL, *prev = NULL; + while (n) { + struct type *new = clone_type(n); + + if (prev) prev->n = new; + else new_root = new; + + prev = new; + n = n->n; + } + + return new_root; +} + int ast_visit(ast_callback_t before, ast_callback_t after, struct ast *n, void *d) { @@ -346,6 +401,17 @@ size_t ast_list_len(struct ast *node) return count; } +size_t type_list_len(struct type *node) +{ + size_t count = 0; + while (node) { + count++; + node = node->n; + } + + return count; +} + struct ast *ast_last(struct ast *list) { if (!list) @@ -482,3 +548,43 @@ void fix_closures(struct ast *root) root = next; } } + +bool types_match(struct type *a, struct type *b) +{ + if (!a && !b) + return true; + + if (a && !b) + return false; + + if (!a && b) + return false; + + if (a->k != b->k) + return false; + + if (a->id && b->id && strcmp(a->id, b->id) != 0) + return false; + + if (!type_lists_match(a->t0, b->t0)) + return false; + + return true; +} + +bool type_lists_match(struct type *al, struct type *bl) +{ + if (type_list_len(al) != type_list_len(bl)) + return false; + + struct type *a = al; + struct type *b = bl; + while (a && b) { + if (!types_match(a, b)) + return false; + + a = a->n; + b = b->n; + } + return true; +} diff --git a/src/debug.c b/src/debug.c index f47a022..f823442 100644 --- a/src/debug.c +++ b/src/debug.c @@ -15,6 +15,7 @@ #include <stdarg.h> #include <fwd/debug.h> +#include <fwd/scope.h> /** * Get string representation of issue_level. @@ -120,7 +121,7 @@ void src_issue(struct src_issue issue, const char *err_msg, ...) va_end(args); } -void semantic_error(struct file_ctx fctx, struct ast *node, +void semantic_error(struct scope *scope, struct ast *node, const char *fmt, ...) { va_list args; @@ -128,12 +129,86 @@ void semantic_error(struct file_ctx fctx, struct ast *node, struct src_issue issue; issue.level = SRC_ERROR; issue.loc = node->loc; - issue.fctx = fctx; + issue.fctx = scope->fctx; _issue(issue, fmt, args); va_end(args); } -void loc_error(struct file_ctx fctx, struct src_loc loc, +void type_mismatch(struct scope *scope, struct ast *node, + struct type *l, struct type *r) +{ + const char *ls = type_str(l); + const char *rs = type_str(r); + semantic_error(scope, node, "type mismatch: %s vs %s\n", ls, rs); + free((void *)ls); + free((void *)rs); +} + +static void _type_str(FILE *f, struct type *t); + +static void _type_list_str(FILE *f, struct type *types) +{ + _type_str(f, types); + + foreach_type(type, types->n) { + fprintf(f, ", "); + _type_str(f, type); + } +} + +static void _type_str(FILE *f, struct type *type) +{ + if (!type) + return; + + switch (type->k) { + case TYPE_VOID: + fprintf(f, "void"); + break; + + case TYPE_PTR: + fprintf(f, "*"); + break; + + case TYPE_REF: + fprintf(f, "&"); + break; + + case TYPE_ID: + fprintf(f, "%s", type->id); + break; + + case TYPE_CALLABLE: + fprintf(f, "("); + _type_list_str(f, type->t0); + fprintf(f, ")"); + break; + + case TYPE_CONSTRUCT: + fprintf(f, "%s![", type->id); + _type_list_str(f, type->t0); + fprintf(f, "]"); + break; + } +} + +const char *type_str(struct type *t) +{ + if (!t) + return strdup("NULL"); + + char *buf = NULL; size_t size = 0; + FILE *memstream = open_memstream(&buf, &size); + if (!memstream) + return NULL; + + _type_str(memstream, t); + + fclose(memstream); + return buf; +} + +void loc_error(struct scope *scope, struct src_loc loc, const char *fmt, ...) { va_list args; @@ -141,12 +216,12 @@ void loc_error(struct file_ctx fctx, struct src_loc loc, struct src_issue issue; issue.level = SRC_ERROR; issue.loc = loc; - issue.fctx = fctx; + issue.fctx = scope->fctx; _issue(issue, fmt, args); va_end(args); } -void semantic_warn(struct file_ctx fctx, struct ast *node, const char *fmt, +void semantic_warn(struct scope *scope, struct ast *node, const char *fmt, ...) { va_list args; @@ -154,12 +229,12 @@ void semantic_warn(struct file_ctx fctx, struct ast *node, const char *fmt, struct src_issue issue; issue.level = SRC_WARN; issue.loc = node->loc; - issue.fctx = fctx; + issue.fctx = scope->fctx; _issue(issue, fmt, args); va_end(args); } -void semantic_info(struct file_ctx fctx, struct ast *node, const char *fmt, +void semantic_info(struct scope *scope, struct ast *node, const char *fmt, ...) { va_list args; @@ -167,7 +242,7 @@ void semantic_info(struct file_ctx fctx, struct ast *node, const char *fmt, struct src_issue issue; issue.level = SRC_INFO; issue.loc = node->loc; - issue.fctx = fctx; + issue.fctx = scope->fctx; _issue(issue, fmt, args); va_end(args); } diff --git a/src/scope.c b/src/scope.c index 869e0d6..a7dfa69 100644 --- a/src/scope.c +++ b/src/scope.c @@ -102,8 +102,8 @@ int scope_add_var(struct scope *scope, struct ast *var) { struct ast *exists = scope_find_symbol(scope, var_id(var)); if (exists) { - semantic_error(scope->fctx, var, "var redefined"); - semantic_info(scope->fctx, exists, "previously here"); + semantic_error(scope, var, "var redefined"); + semantic_info(scope, exists, "previously here"); return -1; } @@ -116,8 +116,8 @@ int scope_add_proc(struct scope *scope, struct ast *proc) assert(proc->k == AST_PROC_DEF); struct ast *exists = file_scope_find_symbol(scope, proc_id(proc)); if (exists) { - semantic_error(scope->fctx, proc, "proc redefined"); - semantic_info(scope->fctx, exists, "previously here"); + semantic_error(scope, proc, "proc redefined"); + semantic_info(scope, exists, "previously here"); return -1; } |