harec

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs | README | LICENSE

commit 486a8e57b0532e507688e012bc33258e6edb4d40
parent 3fecfcfd18fb73fab06e8a2593085307e424ca15
Author: Drew DeVault <sir@cmpwn.com>
Date:   Mon, 23 Aug 2021 16:28:04 +0200

all: move labels to compound expressions

This patch does the following things:

- Renames expression list to compound expression
- Associates labels with compound expressions
- Updates loops accordingly

This is the first step towards yield.

Signed-off-by: Drew DeVault <sir@cmpwn.com>

Diffstat:
Minclude/ast.h | 10+++++++---
Minclude/expr.h | 27++++++++++++++-------------
Minclude/gen.h | 2++
Minclude/scope.h | 17+++++++++++++++--
Msrc/check.c | 152+++++++++++++++++++++++++++++++++----------------------------------------------
Msrc/eval.c | 4++--
Msrc/gen.c | 90+++++++++++++++++++++++++++++++++++++++++++------------------------------------
Msrc/parse.c | 39+++++++++++++++++++++------------------
Msrc/scope.c | 27++++++++++++++++++++++++++-
Msrc/type_store.c | 3++-
Mtests/12-loops.ha | 4++--
Mtests/16-defer.ha | 1+
Mtests/30-reduction.c | 2+-
13 files changed, 205 insertions(+), 173 deletions(-)

diff --git a/include/ast.h b/include/ast.h @@ -225,8 +225,6 @@ struct ast_expression_delete { }; struct ast_expression_for { - char *label; - struct location label_loc; struct ast_expression *bindings; struct ast_expression *cond; struct ast_expression *afterthought; @@ -254,6 +252,12 @@ struct ast_expression_list { struct ast_expression_list *next; }; +struct ast_expression_compound { + char *label; + struct location label_loc; + struct ast_expression_list list; +}; + struct ast_match_case { char *name; // May be null struct ast_type *type; @@ -349,6 +353,7 @@ struct ast_expression { struct ast_expression_binding binding; struct ast_expression_call call; struct ast_expression_cast cast; + struct ast_expression_compound compound; struct ast_expression_constant constant; struct ast_expression_control control; struct ast_expression_defer defer; @@ -357,7 +362,6 @@ struct ast_expression { struct ast_expression_free free; struct ast_expression_if _if; struct ast_expression_insert insert; - struct ast_expression_list list; struct ast_expression_match match; struct ast_expression_measure measure; struct ast_expression_propagate propagate; diff --git a/include/expr.h b/include/expr.h @@ -19,6 +19,7 @@ enum expr_type { EXPR_BREAK, EXPR_CALL, EXPR_CAST, + EXPR_COMPOUND, EXPR_CONSTANT, EXPR_CONTINUE, EXPR_DEFER, @@ -27,7 +28,6 @@ enum expr_type { EXPR_FREE, EXPR_IF, EXPR_INSERT, - EXPR_LIST, EXPR_MATCH, EXPR_MEASURE, EXPR_PROPAGATE, @@ -152,6 +152,17 @@ struct expression_call { struct call_argument *args; }; +struct expressions { + struct expression *expr; + struct expressions *next; +}; + +struct expression_compound { + char *label; + struct scope *scope; + struct expressions exprs; +}; + struct array_constant { struct expression *value; struct array_constant *next; @@ -198,6 +209,7 @@ struct expression_constant { struct expression_control { char *label; + const struct scope *scope; }; struct expression_defer { @@ -210,7 +222,6 @@ struct expression_delete { }; struct expression_for { - char *label; struct scope *scope; struct expression *bindings; struct expression *cond; @@ -235,16 +246,6 @@ struct expression_insert { bool is_static; }; -struct expressions { - struct expression *expr; - struct expressions *next; -}; - -struct expression_list { - struct scope *scope; - struct expressions exprs; -}; - struct match_case { const struct scope_object *object; // NULL if not bound const struct type *type; // NULL if default @@ -347,6 +348,7 @@ struct expression { struct expression_binding binding; struct expression_call call; struct expression_cast cast; + struct expression_compound compound; struct expression_constant constant; struct expression_defer defer; struct expression_delete delete; @@ -355,7 +357,6 @@ struct expression { struct expression_free free; struct expression_if _if; struct expression_insert insert; - struct expression_list list; struct expression_match match; struct expression_measure measure; struct expression_propagate propagate; diff --git a/include/gen.h b/include/gen.h @@ -5,6 +5,7 @@ #include "qbe.h" #include "type_store.h" #include "types.h" +#include "scope.h" enum fixed_aborts { ABORT_OOB = 0, @@ -50,6 +51,7 @@ struct gen_defer { struct gen_scope { const char *label; + const struct scope *scope; struct qbe_value *after; struct qbe_value *end; struct gen_defer *defers; diff --git a/include/scope.h b/include/scope.h @@ -25,8 +25,18 @@ struct scope_object { struct scope_object *mnext; // Hash map }; +enum scope_class { + SCOPE_COMPOUND, + SCOPE_ENUM, + SCOPE_FUNC, + SCOPE_LOOP, + SCOPE_MATCH, + SCOPE_SUBUNIT, + SCOPE_UNIT, +}; + struct scope { - enum expr_type type; + enum scope_class class; const char *label; struct scope *parent; @@ -45,9 +55,12 @@ struct scopes { struct scopes *next; }; -struct scope *scope_push(struct scope **stack); +struct scope *scope_push(struct scope **stack, enum scope_class class); struct scope *scope_pop(struct scope **stack); +struct scope *scope_lookup_ancestor(struct scope *scope, + enum scope_class class, const char *label); + void scope_free(struct scope *scope); void scope_free_all(struct scopes *scopes); diff --git a/src/check.c b/src/check.c @@ -1263,6 +1263,45 @@ lower_constant(const struct type *type, struct expression *expr) } static void +check_expr_compound(struct context *ctx, + const struct ast_expression *aexpr, + struct expression *expr, + const struct type *hint) +{ + expr->type = EXPR_COMPOUND; + + struct scope *scope = scope_push(&ctx->scope, SCOPE_COMPOUND); + expr->compound.scope = scope; + + if (aexpr->compound.label) { + expr->compound.label = strdup(aexpr->compound.label); + scope->label = strdup(aexpr->compound.label); + } + + struct expressions *list = &expr->compound.exprs; + struct expressions **next = &list->next; + + const struct ast_expression_list *alist = &aexpr->compound.list; + while (alist) { + struct expression *lexpr = xcalloc(1, sizeof(struct expression)); + check_expression(ctx, alist->expr, lexpr, alist->next ? &builtin_type_void : hint); + list->expr = lexpr; + + alist = alist->next; + if (alist) { + *next = xcalloc(1, sizeof(struct expressions)); + list = *next; + next = &list->next; + } else { + expr->result = lexpr->result; + expr->terminates = lexpr->terminates; + } + } + + scope_pop(&ctx->scope); +} + +static void check_expr_constant(struct context *ctx, const struct ast_expression *aexpr, struct expression *expr, @@ -1446,23 +1485,12 @@ check_expr_control(struct context *ctx, expr->type = aexpr->type; expr->result = &builtin_type_void; expr->terminates = true; - char *label = expr->control.label = aexpr->control.label; - - struct scope *scope = ctx->scope; - for (; scope != NULL; scope = scope->parent) { - if (scope->type != EXPR_FOR) { - continue; - } - if (label == NULL) { - break; - } - if (scope->label != NULL && strcmp(label, scope->label) == 0) { - break; - } - } - if (scope == NULL) { - error(ctx, aexpr->loc, expr, "Unknown label %s", - expr->control.label); + expr->control.label = aexpr->control.label; + expr->control.scope = scope_lookup_ancestor(ctx->scope, + SCOPE_LOOP, aexpr->control.label); + if (!expr->control.scope) { + // XXX: This error message is bad + error(ctx, aexpr->loc, expr, "No eligible loop for operation"); return; } } @@ -1476,26 +1504,8 @@ check_expr_for(struct context *ctx, expr->type = EXPR_FOR; expr->result = &builtin_type_void; - if (aexpr->_for.label) { - expr->_for.label = strdup(aexpr->_for.label); - } - - struct scope *scope = scope_push(&ctx->scope); + struct scope *scope = scope_push(&ctx->scope, SCOPE_LOOP); expr->_for.scope = scope; - scope->type = expr->type; - scope->label = expr->_for.label; - if (expr->_for.label) { - for (scope = scope->parent; scope; scope = scope->parent) { - if (scope->label == NULL) { - continue; - } - if (strcmp(scope->label, expr->_for.label) == 0){ - error(ctx, aexpr->_for.label_loc, expr, - "for loop label must be unique among its ancestors"); - return; - } - } - } struct expression *bindings = NULL, *cond = NULL, *afterthought = NULL, *body = NULL; @@ -1678,41 +1688,6 @@ check_expr_insert(struct context *ctx, } static void -check_expr_list(struct context *ctx, - const struct ast_expression *aexpr, - struct expression *expr, - const struct type *hint) -{ - expr->type = EXPR_LIST; - - struct scope *scope = scope_push(&ctx->scope); - expr->list.scope = scope; - scope->type = expr->type; - - struct expressions *list = &expr->list.exprs; - struct expressions **next = &list->next; - - const struct ast_expression_list *alist = &aexpr->list; - while (alist) { - struct expression *lexpr = xcalloc(1, sizeof(struct expression)); - check_expression(ctx, alist->expr, lexpr, alist->next ? &builtin_type_void : hint); - list->expr = lexpr; - - alist = alist->next; - if (alist) { - *next = xcalloc(1, sizeof(struct expressions)); - list = *next; - next = &list->next; - } else { - expr->result = lexpr->result; - expr->terminates = lexpr->terminates; - } - } - - scope_pop(&ctx->scope); -} - -static void check_expr_match(struct context *ctx, const struct ast_expression *aexpr, struct expression *expr, @@ -1777,8 +1752,8 @@ check_expr_match(struct context *ctx, struct identifier ident = { .name = acase->name, }; - struct scope *scope = scope_push(&ctx->scope); - scope->type = EXPR_MATCH; + struct scope *scope = scope_push( + &ctx->scope, SCOPE_MATCH); _case->object = scope_insert(scope, O_BIND, &ident, &ident, ctype, NULL); } @@ -1973,8 +1948,7 @@ check_expr_propagate(struct context *ctx, expr->type = EXPR_MATCH; expr->match.value = lvalue; - struct scope *scope = scope_push(&ctx->scope); - scope->type = EXPR_MATCH; + struct scope *scope = scope_push(&ctx->scope, SCOPE_MATCH); struct match_case *case_ok = xcalloc(1, sizeof(struct match_case)); struct match_case *case_err = xcalloc(1, sizeof(struct match_case)); struct identifier ok_name = {0}, err_name = {0}; @@ -2621,6 +2595,9 @@ check_expression(struct context *ctx, case EXPR_CAST: check_expr_cast(ctx, aexpr, expr, hint); break; + case EXPR_COMPOUND: + check_expr_compound(ctx, aexpr, expr, hint); + break; case EXPR_CONSTANT: check_expr_constant(ctx, aexpr, expr, hint); break; @@ -2642,9 +2619,6 @@ check_expression(struct context *ctx, case EXPR_INSERT: check_expr_insert(ctx, aexpr, expr, hint); break; - case EXPR_LIST: - check_expr_list(ctx, aexpr, expr, hint); - break; case EXPR_MATCH: check_expr_match(ctx, aexpr, expr, hint); break; @@ -2750,7 +2724,7 @@ check_function(struct context *ctx, return decl; // Prototype } - decl->func.scope = scope_push(&ctx->scope); + decl->func.scope = scope_push(&ctx->scope, SCOPE_FUNC); struct ast_function_parameters *params = afndecl->prototype.params; while (params) { expect(&params->loc, params->name, @@ -3077,6 +3051,14 @@ expr_is_specified(struct context *ctx, const struct ast_expression *aexpr) } } return true; + case EXPR_COMPOUND: + for (const struct ast_expression_list *list = &aexpr->compound.list; + list; list = list->next) { + if (!expr_is_specified(ctx, list->expr)) { + return false; + } + } + return true; case EXPR_BREAK: case EXPR_CONTINUE: return true; @@ -3119,14 +3101,6 @@ expr_is_specified(struct context *ctx, const struct ast_expression *aexpr) && expr_is_specified(ctx, aexpr->_if.false_branch); case EXPR_INSERT: assert(0); // TODO - case EXPR_LIST: - for (const struct ast_expression_list *list = &aexpr->list; - list; list = list->next) { - if (!expr_is_specified(ctx, list->expr)) { - return false; - } - } - return true; case EXPR_MATCH: for (struct ast_match_case *mcase = aexpr->match.cases; mcase; mcase = mcase->next) { @@ -3558,7 +3532,7 @@ check_internal(struct type_store *ts, // // Further down the call frame, subsequent functions will create // sub-scopes for each declaration, expression-list, etc. - ctx.unit = scope_push(&ctx.scope); + ctx.unit = scope_push(&ctx.scope, SCOPE_UNIT); // Install defines (-D on the command line) // XXX: This duplicates a lot of code with scan_const @@ -3600,7 +3574,7 @@ check_internal(struct type_store *ts, // First pass populates the imports for (const struct ast_subunit *su = &aunit->subunits; su; su = su->next) { - scope_push(&ctx.scope); + scope_push(&ctx.scope, SCOPE_SUBUNIT); for (struct ast_imports *imports = su->imports; imports; imports = imports->next) { diff --git a/src/eval.c b/src/eval.c @@ -718,15 +718,15 @@ eval_expr(struct context *ctx, struct expression *in, struct expression *out) case EXPR_ASSIGN: case EXPR_BINDING: case EXPR_BREAK: - case EXPR_CONTINUE: case EXPR_CALL: + case EXPR_COMPOUND: + case EXPR_CONTINUE: case EXPR_DEFER: case EXPR_DELETE: case EXPR_FOR: case EXPR_FREE: case EXPR_IF: case EXPR_INSERT: - case EXPR_LIST: case EXPR_MATCH: case EXPR_PROPAGATE: case EXPR_RETURN: diff --git a/src/gen.c b/src/gen.c @@ -42,12 +42,25 @@ gen_defers(struct gen_context *ctx, struct gen_scope *scope) } } +static struct gen_scope * +gen_scope_lookup(struct gen_context *ctx, const struct scope *which) +{ + for (struct gen_scope *scope = ctx->scope; + scope; scope = scope->parent) { + if (scope->scope == which) { + return scope; + } + } + abort(); +} + static void -push_scope(struct gen_context *ctx) +push_scope(struct gen_context *ctx, const struct scope *scope) { - struct gen_scope *scope = xcalloc(1, sizeof(struct gen_scope)); - scope->parent = ctx->scope; - ctx->scope = scope; + struct gen_scope *new = xcalloc(1, sizeof(struct gen_scope)); + new->parent = ctx->scope; + new->scope = scope; + ctx->scope = new; } static void @@ -66,7 +79,6 @@ pop_scope(struct gen_context *ctx, bool gendefers) free(scope); } - static void gen_copy_memcpy(struct gen_context *ctx, struct gen_value dest, struct gen_value src) @@ -863,19 +875,16 @@ gen_expr_binding(struct gen_context *ctx, const struct expression *expr) static struct gen_value gen_expr_control(struct gen_context *ctx, const struct expression *expr) { - struct gen_scope *scope = ctx->scope; - while (scope != NULL) { - gen_defers(ctx, scope); - if (expr->control.label && scope->label) { - if (strcmp(expr->control.label, scope->label) == 0) { - break; - } - } else if (!expr->control.label && scope->after) { + struct gen_scope *scope = gen_scope_lookup(ctx, expr->control.scope); + assert(scope->scope->class == SCOPE_LOOP); + struct gen_scope *deferred = ctx->scope; + while (deferred != NULL) { + gen_defers(ctx, deferred); + if (deferred == scope) { break; } - scope = scope->parent; + deferred = deferred->parent; } - assert(scope != NULL); if (expr->type == EXPR_BREAK) { pushi(ctx->current, NULL, Q_JMP, scope->end, NULL); } else { @@ -1315,6 +1324,25 @@ gen_expr_cast(struct gen_context *ctx, const struct expression *expr) return result; } +static struct gen_value +gen_expr_compound_with(struct gen_context *ctx, + const struct expression *expr, + struct gen_value *out) +{ + push_scope(ctx, expr->compound.scope); + for (const struct expressions *exprs = &expr->compound.exprs; + exprs; exprs = exprs->next) { + if (!exprs->next) { + struct gen_value gv = gen_expr_with( + ctx, exprs->expr, out); + pop_scope(ctx, !exprs->expr->terminates); + return gv; + } + gen_expr(ctx, exprs->expr); + } + abort(); // Unreachable +} + static void gen_const_array_at(struct gen_context *ctx, const struct expression *expr, struct gen_value out) @@ -1595,8 +1623,7 @@ gen_expr_for(struct gen_context *ctx, const struct expression *expr) gen_expr_binding(ctx, expr->_for.bindings); } - push_scope(ctx); - ctx->scope->label = expr->_for.label; + push_scope(ctx, expr->_for.scope); ctx->scope->after = &bafter; ctx->scope->end = &bend; @@ -1797,25 +1824,6 @@ gen_expr_insert(struct gen_context *ctx, const struct expression *expr) return gv_void; } -static struct gen_value -gen_expr_list_with(struct gen_context *ctx, - const struct expression *expr, - struct gen_value *out) -{ - push_scope(ctx); - for (const struct expressions *exprs = &expr->list.exprs; - exprs; exprs = exprs->next) { - if (!exprs->next) { - struct gen_value gv = gen_expr_with( - ctx, exprs->expr, out); - pop_scope(ctx, !exprs->expr->terminates); - return gv; - } - gen_expr(ctx, exprs->expr); - } - abort(); // Unreachable -} - enum match_compat { // The case type is a member of the match object type and can be used // directly from the match object's tagged union storage area. @@ -2520,6 +2528,8 @@ gen_expr(struct gen_context *ctx, const struct expression *expr) return gen_expr_call(ctx, expr); case EXPR_CAST: return gen_expr_cast(ctx, expr); + case EXPR_COMPOUND: + return gen_expr_compound_with(ctx, expr, NULL); case EXPR_CONSTANT: return gen_expr_const(ctx, expr); case EXPR_DEFER: @@ -2534,8 +2544,6 @@ gen_expr(struct gen_context *ctx, const struct expression *expr) return gen_expr_if_with(ctx, expr, NULL); case EXPR_INSERT: return gen_expr_insert(ctx, expr); - case EXPR_LIST: - return gen_expr_list_with(ctx, expr, NULL); case EXPR_MATCH: return gen_expr_match_with(ctx, expr, NULL); case EXPR_MEASURE: @@ -2580,15 +2588,15 @@ gen_expr_at(struct gen_context *ctx, case EXPR_CAST: gen_expr_cast_at(ctx, expr, out); return; + case EXPR_COMPOUND: + gen_expr_compound_with(ctx, expr, &out); + return; case EXPR_CONSTANT: gen_expr_const_at(ctx, expr, out); return; case EXPR_IF: gen_expr_if_with(ctx, expr, &out); return; - case EXPR_LIST: - gen_expr_list_with(ctx, expr, &out); - return; case EXPR_MATCH: gen_expr_match_with(ctx, expr, &out); return; diff --git a/src/parse.c b/src/parse.c @@ -1692,18 +1692,7 @@ parse_for_expression(struct lexer *lexer) exp->type = EXPR_FOR; struct token tok = {0}; - switch (lex(lexer, &tok)) { - case T_FOR: - break; - case T_LABEL: - exp->_for.label_loc = tok.loc; - exp->_for.label = tok.name; - want(lexer, T_FOR, NULL); - break; - default: - assert(0); - } - + want(lexer, T_FOR, &tok); want(lexer, T_LPAREN, &tok); switch (lex(lexer, &tok)) { case T_LET: @@ -2048,18 +2037,31 @@ parse_control_statement(struct lexer *lexer) } static struct ast_expression * -parse_expression_list(struct lexer *lexer) +parse_compound_expression(struct lexer *lexer) { struct ast_expression *exp = mkexpr(&lexer->loc); - struct ast_expression_list *cur = &exp->list; + exp->type = EXPR_COMPOUND; + + struct ast_expression_list *cur = &exp->compound.list; struct ast_expression_list **next = &cur->next; - exp->type = EXPR_LIST; + + struct token tok = {0}; + switch (lex(lexer, &tok)) { + case T_LABEL: + exp->compound.label = tok.name; + want(lexer, T_LBRACE, &tok); + break; + case T_LBRACE: + break; // no-op + default: + synassert(false, &tok, T_LBRACE, T_LABEL, T_EOF); + break; + }; bool more = true; while (more) { cur->expr = parse_expression(lexer); - struct token tok = {0}; want(lexer, T_SEMICOLON, &tok); if (more) { @@ -2140,7 +2142,6 @@ parse_expression(struct lexer *lexer) value = parse_deferred_expression(lexer); break; case T_FOR: - case T_LABEL: unlex(lexer, &tok); value = parse_for_expression(lexer); break; @@ -2148,7 +2149,9 @@ parse_expression(struct lexer *lexer) value = parse_if_expression(lexer); break; case T_LBRACE: - value = parse_expression_list(lexer); + case T_LABEL: + unlex(lexer, &tok); + value = parse_compound_expression(lexer); break; case T_MATCH: value = parse_match_expression(lexer); diff --git a/src/scope.c b/src/scope.c @@ -1,5 +1,6 @@ #include <assert.h> #include <stdlib.h> +#include <string.h> #include "expr.h" #include "identifier.h" #include "scope.h" @@ -12,9 +13,10 @@ name_hash(uint32_t init, const struct identifier *ident) } struct scope * -scope_push(struct scope **stack) +scope_push(struct scope **stack, enum scope_class class) { struct scope *new = xcalloc(1, sizeof(struct scope)); + new->class = class; new->next = &new->objects; if (*stack) { new->parent = *stack; @@ -32,6 +34,29 @@ scope_pop(struct scope **stack) return prev; } +struct scope * +scope_lookup_ancestor(struct scope *scope, + enum scope_class class, const char *label) +{ + // Implements the algorithm described by "Control statements" item 2, or + // 6.6.48.2 at the time of writing + while (scope) { + if (label && scope->label && strcmp(scope->label, label) == 0) { + break; + } else if (!label && scope->class == class) { + break; + } + scope = scope->parent; + } + + if (scope && class != scope->class) { + assert(scope->class == SCOPE_COMPOUND); + scope = scope->parent; + } + + return scope; +} + void scope_free(struct scope *scope) { diff --git a/src/type_store.c b/src/type_store.c @@ -598,7 +598,8 @@ type_init_from_atype(struct type_store *store, type->size = storage->size; type->align = storage->size; - struct scope *scope = scope_push(&store->check_context->scope); + struct scope *scope = scope_push( + &store->check_context->scope, SCOPE_ENUM); // TODO: Check for duplicates struct ast_enum_field *avalue = atype->_enum.values; struct type_enum_value **values = &type->_enum.values; diff --git a/tests/12-loops.ha b/tests/12-loops.ha @@ -73,8 +73,8 @@ fn _continue() void = { fn label() void = { let i = 0; - :outer for (i < 10) { - :inner for (let j = 0; j < 7; j += 1) { + for (i < 10) :outer { + for (let j = 0; j < 7; j += 1) :inner { i += 1; if (j == 6) { for (let k = 0; k < 5; k += 1) { diff --git a/tests/16-defer.ha b/tests/16-defer.ha @@ -45,6 +45,7 @@ fn control() void = { if (true) { break; }; + abort(); }; assert(x == 1); }; diff --git a/tests/30-reduction.c b/tests/30-reduction.c @@ -69,7 +69,7 @@ int main(void) { ctx.store = &ts; ctx.store->check_context = &ctx; ctx.modcache = modcache; - ctx.unit = scope_push(&ctx.scope); + ctx.unit = scope_push(&ctx.scope, SCOPE_UNIT); test(&ctx, "(int | void)", "if (true) 0: int else void: void"); test(&ctx, "(nullable *int | void)",