harec

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

commit a7fb6028b0234691d400749ffe5fa154d5b1635b
parent c790744abb4f02f31044fe11bd4b2eebf34bc81b
Author: Drew DeVault <sir@cmpwn.com>
Date:   Fri, 31 Dec 2021 15:02:47 +0100

all: overhaul append & insert semantics

This updates the compiler following the specification changes for append
and insert. In short, this removes heuristics from append and insert,
unifies some of their code paths (though there's room for more
improvement in this respect), and implements the new "append with
length" feature.

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

Diffstat:
Minclude/ast.h | 23+++++------------------
Minclude/expr.h | 25+++++--------------------
Mrt/ensure.ha | 59+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Msrc/check.c | 159++++++++++++++++++++++++++-----------------------------------------------------
Msrc/gen.c | 266+++++++++++++++++++++++++++++++++++++++++--------------------------------------
Msrc/parse.c | 115++++++++++++++++++++++++++++++++++++++-----------------------------------------
Mtests/19-append.ha | 105+++++++++++++++++++++++++++++++++++--------------------------------------------
Mtests/22-delete.ha | 2+-
Mtests/28-insert.ha | 91+++++++++++++++++++++++++++++++++++++++----------------------------------------
9 files changed, 406 insertions(+), 439 deletions(-)

diff --git a/include/ast.h b/include/ast.h @@ -130,16 +130,11 @@ struct ast_expression_alloc { struct ast_expression *cap; }; -struct ast_append_values { - struct ast_expression *expr; - struct ast_append_values *next; -}; - struct ast_expression_append { - struct ast_expression *expr; - struct ast_expression *variadic; - struct ast_append_values *values; - bool is_static; + struct ast_expression *object; + struct ast_expression *value; + struct ast_expression *length; + bool is_static, is_multi; }; struct ast_expression_assert { @@ -237,13 +232,6 @@ struct ast_expression_if { struct ast_expression *true_branch, *false_branch; }; -struct ast_expression_insert { - struct ast_expression *expr; - struct ast_expression *variadic; - struct ast_append_values *values; - bool is_static; -}; - struct ast_expression_compound { char *label; struct location label_loc; @@ -336,7 +324,7 @@ struct ast_expression { union { struct ast_expression_access access; struct ast_expression_alloc alloc; - struct ast_expression_append append; + struct ast_expression_append append; // also insert struct ast_expression_assert assert; struct ast_expression_assign assign; struct ast_expression_binarithm binarithm; @@ -351,7 +339,6 @@ struct ast_expression { struct ast_expression_for _for; struct ast_expression_free free; struct ast_expression_if _if; - struct ast_expression_insert insert; 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 @@ -88,17 +88,11 @@ struct expression_alloc { struct expression *cap; }; -struct append_values { - struct expression *expr; - struct append_values *next; -}; - struct expression_append { - struct expression *expr; - struct expression *variadic; - struct append_values *values; - struct location loc; - bool is_static; + struct expression *object; + struct expression *value; + struct expression *length; + bool is_static, is_multi; }; struct expression_assert { @@ -251,14 +245,6 @@ struct expression_if { struct expression *true_branch, *false_branch; }; -struct expression_insert { - struct expression *expr; - struct expression *variadic; - struct append_values *values; - struct location loc; - bool is_static; -}; - struct match_case { const struct scope_object *object; // NULL if not bound const struct type *type; // NULL if default @@ -358,7 +344,7 @@ struct expression { union { struct expression_access access; struct expression_alloc alloc; - struct expression_append append; + struct expression_append append; // and insert struct expression_assert assert; struct expression_assign assign; struct expression_binarithm binarithm; @@ -373,7 +359,6 @@ struct expression { struct expression_for _for; struct expression_free free; struct expression_if _if; - struct expression_insert insert; struct expression_match match; struct expression_measure measure; struct expression_propagate propagate; diff --git a/rt/ensure.ha b/rt/ensure.ha @@ -34,3 +34,62 @@ export fn unensure(s: *slice, membsz: size) void = { assert(data != null || s.capacity * membsz == 0); s.data = data; }; + +type base = enum uint { + BIN = 2, + OCT = 8, + DEC = 10, + HEX = 16, +}; + +// XXX: TEMP +fn u64tosb(u: u64, b: base) const str = { + static let buf: [64]u8 = [0...]; // 64 binary digits + + static const lut_upper = [ + '0', '1', '2', '3', '4', '5', '6', '7', + '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', + ]; + const lut = &lut_upper; + + let s = string { data = &buf, ... }; + if (u == 0) { + buf[s.length] = '0': u32: u8; + s.length += 1z; + }; + + for (u > 0u64) { + buf[s.length] = lut[u % b: u64]: u32: u8; + s.length += 1; + u /= b; + }; + + reverse(buf[..s.length]); + return *(&s: *str); +}; + +fn reverse(b: []u8) void = { + if (len(b) == 0) { + return; + }; + for (let s = 0z, e = len(b) - 1; s < e) { + let x = b[s]; + b[s] = b[e]; + b[e] = x; + s += 1; + e -= 1; + }; +}; + +fn println(msgs: str...) void = { + for (let i = 0z; i < len(msgs); i += 1) { + let msg = msgs[i]; + rt::write(1, *(&msg: **void): *const char, len(msg)): void; + if (i + 1 < len(msgs)) { + const sp = " "; + rt::write(1, *(&sp: **void): *const char, 1): void; + }; + }; + const linefeed = "\n"; + write(1, *(&linefeed: **void): *const char, 1): void; +}; diff --git a/src/check.c b/src/check.c @@ -393,61 +393,69 @@ check_expr_alloc(struct context *ctx, } static void -check_expr_append(struct context *ctx, +check_expr_append_insert(struct context *ctx, const struct ast_expression *aexpr, struct expression *expr, const struct type *hint) { - assert(aexpr->type == EXPR_APPEND); - expr->type = EXPR_APPEND; + assert(aexpr->type == EXPR_APPEND || aexpr->type == EXPR_INSERT); + expr->loc = aexpr->loc; + expr->type = aexpr->type; expr->result = &builtin_type_void; expr->append.is_static = aexpr->append.is_static; - expr->insert.loc = aexpr->loc; - expr->append.expr = xcalloc(sizeof(struct expression), 1); - check_expression(ctx, aexpr->append.expr, expr->append.expr, NULL); - const struct type *stype = type_dereference(expr->append.expr->result); - if (!stype) { - error(ctx, aexpr->access.array->loc, expr, - "Cannot dereference nullable pointer for append"); - return; + expr->append.is_multi = aexpr->append.is_multi; + expr->append.object = xcalloc(sizeof(struct expression), 1); + check_expression(ctx, aexpr->append.object, expr->append.object, NULL); + assert(expr->append.object->type == EXPR_ACCESS); + + const struct type *sltype; + switch (expr->type) { + case EXPR_APPEND: + sltype = type_dereference(expr->append.object->result); + sltype = type_dealias(sltype); + break; + case EXPR_INSERT: + assert(expr->append.object->access.type == ACCESS_INDEX); + sltype = expr->append.object->access.array->result; + sltype = type_dealias(sltype); + break; + default: + abort(); // Invariant } - stype = type_dealias(stype); - if (stype->storage != STORAGE_SLICE) { - error(ctx, aexpr->append.expr->loc, expr, - "append must operate on a slice"); + + if (sltype->storage != STORAGE_SLICE) { + error(ctx, aexpr->append.object->loc, expr, + "expression must operate on a slice"); return; } - if (stype->flags & TYPE_CONST) { - error(ctx, aexpr->append.expr->loc, expr, - "append must operate on a mutable slice"); + if (sltype->flags & TYPE_CONST) { + error(ctx, aexpr->append.object->loc, expr, + "expression must operate on a mutable slice"); return; } - assert(expr->append.expr->type == EXPR_ACCESS); - const struct type *memb = stype->array.members; - struct append_values **next = &expr->append.values; - for (struct ast_append_values *avalue = aexpr->append.values; avalue; - avalue = avalue->next) { - struct append_values *value = *next = - xcalloc(sizeof(struct append_values), 1); - value->expr = - xcalloc(sizeof(struct expression), 1); - check_expression(ctx, avalue->expr, value->expr, memb); - if (!type_is_assignable(memb, value->expr->result)) { - error(ctx, avalue->expr->loc, expr, - "appended value must be assignable to member type"); - return; - } - value->expr = lower_implicit_cast(memb, value->expr); - next = &value->next; + + const struct type *valuehint = sltype; + if (!expr->append.is_multi) { + valuehint = sltype->array.members; } - if (aexpr->append.variadic != NULL) { - expr->append.variadic = xcalloc(sizeof(struct expression), 1); - check_expression(ctx, aexpr->append.variadic, expr->append.variadic, stype); - if (!type_is_assignable(stype, expr->append.variadic->result)) { - error(ctx, aexpr->append.variadic->loc, expr, - "appended slice must be assignable to slice type"); + expr->append.value = xcalloc(sizeof(struct expression), 1); + check_expression(ctx, aexpr->append.value, expr->append.value, valuehint); + + if (aexpr->append.length) { + struct expression *len = xcalloc(sizeof(struct expression), 1); + check_expression(ctx, aexpr->append.length, len, &builtin_type_size); + if (!type_is_assignable(&builtin_type_size, len->result)) { + error(ctx, aexpr->loc, expr, + "Length parameter must be assignable to size"); return; } + len = lower_implicit_cast(&builtin_type_size, len); + expr->append.length = len; + } + + if (!expr->append.is_multi && !expr->append.length) { + expr->append.value = lower_implicit_cast( + sltype->array.members, expr->append.value); } } @@ -1782,71 +1790,6 @@ check_expr_if(struct context *ctx, } static void -check_expr_insert(struct context *ctx, - const struct ast_expression *aexpr, - struct expression *expr, - const struct type *hint) -{ - assert(aexpr->type == EXPR_INSERT); - expr->type = EXPR_INSERT; - expr->result = &builtin_type_void; - expr->insert.is_static = aexpr->insert.is_static; - expr->insert.loc = aexpr->loc; - expr->insert.expr = xcalloc(sizeof(struct expression), 1); - check_expression(ctx, aexpr->insert.expr, expr->insert.expr, NULL); - assert(expr->insert.expr->type == EXPR_ACCESS - && expr->insert.expr->access.type == ACCESS_INDEX); - const struct type *sltype = expr->insert.expr->access.array->result; - sltype = type_dereference(sltype); - if (!sltype) { - error(ctx, aexpr->access.array->loc, expr, - "Cannot dereference nullable pointer for insert"); - return; - } - sltype = type_dealias(sltype); - if (sltype->storage != STORAGE_SLICE) { - error(ctx, aexpr->insert.expr->loc, expr, - "cannot insert into non-slice type %s", - type_storage_unparse(type_dealias(sltype)->storage)); - return; - } - if (sltype->flags & TYPE_CONST) { - error(ctx, aexpr->insert.expr->loc, expr, - "insert must operate on a mutable slice"); - return; - } - const struct type *memb = type_dealias(sltype)->array.members; - struct append_values **next = &expr->insert.values; - for (struct ast_append_values *avalue = aexpr->insert.values; avalue; - avalue = avalue->next) { - struct append_values *value = *next = - xcalloc(sizeof(struct append_values), 1); - value->expr = - xcalloc(sizeof(struct expression), 1); - check_expression(ctx, avalue->expr, value->expr, memb); - if (!type_is_assignable(memb, value->expr->result)) { - error(ctx, avalue->expr->loc, expr, - "inserted value must be assignable to member type"); - return; - } - value->expr = lower_implicit_cast(memb, value->expr); - next = &value->next; - } - if (aexpr->insert.variadic != NULL) { - expr->insert.variadic = xcalloc(sizeof(struct expression), 1); - check_expression(ctx, aexpr->insert.variadic, expr->insert.variadic, sltype); - if (!type_is_assignable(sltype, expr->insert.variadic->result)) { - error(ctx, aexpr->insert.variadic->loc, expr, - "inserted slice type %s must be assignable to slice type", - type_storage_unparse(expr->insert.variadic->result->storage)); - return; - } - expr->insert.variadic = lower_implicit_cast( - sltype, expr->insert.variadic); - } -} - -static void check_expr_match(struct context *ctx, const struct ast_expression *aexpr, struct expression *expr, @@ -2817,7 +2760,7 @@ check_expression(struct context *ctx, check_expr_alloc(ctx, aexpr, expr, hint); break; case EXPR_APPEND: - check_expr_append(ctx, aexpr, expr, hint); + check_expr_append_insert(ctx, aexpr, expr, hint); break; case EXPR_ASSERT: check_expr_assert(ctx, aexpr, expr, hint); @@ -2864,7 +2807,7 @@ check_expression(struct context *ctx, check_expr_if(ctx, aexpr, expr, hint); break; case EXPR_INSERT: - check_expr_insert(ctx, aexpr, expr, hint); + check_expr_append_insert(ctx, aexpr, expr, hint); break; case EXPR_MATCH: check_expr_match(ctx, aexpr, expr, hint); diff --git a/src/gen.c b/src/gen.c @@ -631,67 +631,65 @@ gen_expr_alloc_with(struct gen_context *ctx, static struct gen_value gen_expr_append(struct gen_context *ctx, const struct expression *expr) { - struct gen_value slice = gen_expr(ctx, expr->append.expr); + struct gen_value slice = gen_expr(ctx, expr->append.object); slice = gen_autoderef(ctx, slice); struct qbe_value qslice = mkqval(ctx, &slice); - struct qbe_value ptr = mkqtmp(ctx, ctx->arch.ptr, ".%d"); + struct qbe_value lenptr = mkqtmp(ctx, ctx->arch.ptr, ".%d"); + struct qbe_value prevlen = mkqtmp(ctx, ctx->arch.sz, ".%d"); struct qbe_value offs = constl(builtin_type_size.size); - pushi(ctx->current, &ptr, Q_ADD, &qslice, &offs, NULL); - struct qbe_value len = mkqtmp(ctx, ctx->arch.sz, ".%d"); + pushi(ctx->current, &lenptr, Q_ADD, &qslice, &offs, NULL); enum qbe_instr load = load_for_type(ctx, &builtin_type_size); - pushi(ctx->current, &len, load, &ptr, NULL); - - size_t args = 0; - for (struct append_values *value = expr->append.values; value; - value = value->next) { - args++; - } - struct qbe_value qargs = constl(args); - struct qbe_value newlen = mkqtmp(ctx, ctx->arch.sz, ".%d"); - pushi(ctx->current, &newlen, Q_ADD, &len, &qargs, NULL); - - const struct type *vtype = NULL; - struct qbe_value vdata, vlen; - if (expr->append.variadic) { - // TODO: If it's an array object we might be able to make this - // more efficient by using gen_expr_at to populate the expanded - // slice storage area with the variadic data, like - // gen_alloc_slice_at does. - struct gen_value vobj = gen_expr(ctx, expr->append.variadic); - struct qbe_value qvobj = mkqval(ctx, &vobj); - struct qbe_value ptr = mkqtmp(ctx, ctx->arch.ptr, ".%d"); - vdata = mkqtmp(ctx, ctx->arch.ptr, ".%d"); - vtype = type_dealias(expr->append.variadic->result); - switch (vtype->storage) { - case STORAGE_ARRAY: - pushi(ctx->current, &vdata, Q_COPY, &qvobj, NULL); - vlen = constl(vtype->array.length); - break; - case STORAGE_SLICE: - vlen = mkqtmp(ctx, ctx->arch.sz, "vlen.%d"); - pushi(ctx->current, &vdata, Q_COPY, &qvobj, NULL); - pushi(ctx->current, &ptr, Q_ADD, &qvobj, &offs, NULL); - pushi(ctx->current, &vlen, load, &ptr, NULL); - break; - default: abort(); // Invariant + pushi(ctx->current, &prevlen, load, &lenptr, NULL); + + struct qbe_value appendlen; + const struct type *valtype = type_dealias(expr->append.value->result); + if (expr->append.length != NULL) { + struct gen_value length = gen_expr(ctx, expr->append.length); + appendlen = mkqval(ctx, &length); + assert(valtype->storage == STORAGE_ARRAY && valtype->array.expandable); + } else if (!expr->append.is_multi) { + appendlen = constl(1); + } + + struct gen_value value; + struct qbe_value qvalue; + if (!expr->append.is_multi || valtype->storage != STORAGE_ARRAY) { + // We use gen_expr_at for the array case to avoid a copy + value = gen_expr(ctx, expr->append.value); + qvalue = mkqval(ctx, &value); + } + + if (expr->append.is_multi) { + if (valtype->storage == STORAGE_ARRAY) { + assert(valtype->array.length != SIZE_UNDEFINED); + appendlen = constl(valtype->array.length); + } else { + value = gen_expr(ctx, expr->append.value); + qvalue = mkqval(ctx, &value); + appendlen = mkqtmp(ctx, ctx->arch.sz, ".%d"); + struct qbe_value ptr = mkqtmp(ctx, ctx->arch.ptr, ".%d"); + offs = constl(builtin_type_size.size); + pushi(ctx->current, &ptr, Q_ADD, &qvalue, &offs, NULL); + pushi(ctx->current, &appendlen, load, &ptr, NULL); } - - pushi(ctx->current, &newlen, Q_ADD, &newlen, &vlen, NULL); } + struct qbe_value newlen = mkqtmp(ctx, ctx->arch.sz, ".%d"); + pushi(ctx->current, &newlen, Q_ADD, &prevlen, &appendlen, NULL); enum qbe_instr store = store_for_type(ctx, &builtin_type_size); - pushi(ctx->current, NULL, store, &newlen, &ptr, NULL); + pushi(ctx->current, NULL, store, &newlen, &lenptr, NULL); + struct qbe_value ptr = mkqtmp(ctx, ctx->arch.ptr, ".%d"); const struct type *mtype = type_dealias(slice.type)->array.members; struct qbe_value membsz = constl(mtype->size); - if (!expr->append.is_static) { struct qbe_value rtfunc = mkrtfunc(ctx, "rt.ensure"); struct qbe_value lval = mklval(ctx, &slice); pushi(ctx->current, NULL, Q_CALL, &rtfunc, &lval, &membsz, NULL); } else { - pushi(ctx->current, &ptr, Q_ADD, &ptr, &offs, NULL); + offs = constl(builtin_type_size.size * 2); + pushi(ctx->current, &ptr, Q_ADD, &qslice, &offs, NULL); struct qbe_value cap = mkqtmp(ctx, ctx->arch.ptr, ".%d"); pushi(ctx->current, &cap, load, &ptr, NULL); @@ -701,17 +699,15 @@ gen_expr_append(struct gen_context *ctx, const struct expression *expr) struct qbe_value valid = mkqtmp(ctx, &qbe_word, ".%d"); pushi(ctx->current, &valid, Q_CULEL, &newlen, &cap, NULL); pushi(ctx->current, NULL, Q_JNZ, &valid, &bvalid, &binvalid, NULL); - push(&ctx->current->body, &linvalid); + push(&ctx->current->body, &linvalid); gen_fixed_abort(ctx, expr->loc, ABORT_OOB); - push(&ctx->current->body, &lvalid); } - offs = mkqtmp(ctx, ctx->arch.sz, ".%d"); - ptr = mkqtmp(ctx, ctx->arch.ptr, ".%d"); + offs = mkqtmp(ctx, ctx->arch.ptr, ".%d"); pushi(ctx->current, &ptr, load, &qslice, NULL); - pushi(ctx->current, &offs, Q_MUL, &len, &membsz, NULL); + pushi(ctx->current, &offs, Q_MUL, &prevlen, &membsz, NULL); pushi(ctx->current, &ptr, Q_ADD, &ptr, &offs, NULL); struct gen_value item = { @@ -719,20 +715,40 @@ gen_expr_append(struct gen_context *ctx, const struct expression *expr) .type = mtype, .name = ptr.name, }; - for (struct append_values *value = expr->append.values; value; - value = value->next) { - gen_expr_at(ctx, value->expr, item); - pushi(ctx->current, &ptr, Q_ADD, &ptr, &membsz, NULL); - } - - if (expr->append.variadic) { + if (expr->append.is_multi && valtype->storage == STORAGE_ARRAY) { + item.type = valtype; + gen_expr_at(ctx, expr->append.value, item); + } else if (expr->append.is_multi && valtype->storage == STORAGE_SLICE) { + struct qbe_value qsrc = mkqtmp(ctx, ctx->arch.ptr, ".%d"); struct qbe_value rtfunc = mkrtfunc(ctx, "rt.memmove"); struct qbe_value sz = mkqtmp(ctx, ctx->arch.sz, ".%d"); - pushi(ctx->current, &sz, Q_MUL, &vlen, &membsz, NULL); - if (vtype->storage == STORAGE_SLICE) { - pushi(ctx->current, &vdata, load, &vdata, NULL); - } - pushi(ctx->current, NULL, Q_CALL, &rtfunc, &ptr, &vdata, &sz, NULL); + pushi(ctx->current, &sz, Q_MUL, &appendlen, &membsz, NULL); + pushi(ctx->current, &qsrc, load, &qvalue, NULL); + pushi(ctx->current, NULL, Q_CALL, &rtfunc, &ptr, &qsrc, &sz, NULL); + } else if (expr->append.length != NULL) { + // XXX: This could be made more efficient for some cases if + // check could determine the length at compile time and lower it + // to a fixed-length array type + assert(valtype->storage == STORAGE_ARRAY); + item.type = valtype; + gen_expr_at(ctx, expr->append.value, item); + + assert(valtype->array.length != SIZE_UNDEFINED); + struct qbe_value next = mkqtmp(ctx, ctx->arch.ptr, "next.%d"); + struct qbe_value last = mkqtmp(ctx, ctx->arch.ptr, "last.%d"); + struct qbe_value arlen = constl(valtype->array.length * mtype->size); + pushi(ctx->current, &next, Q_ADD, &ptr, &arlen, NULL); + arlen = constl((valtype->array.length - 1) * mtype->size); + pushi(ctx->current, &last, Q_ADD, &ptr, &arlen, NULL); + + struct qbe_value rtfunc = mkrtfunc(ctx, "rt.memcpy"); + struct qbe_value remain = mkqtmp(ctx, ctx->arch.ptr, ".%d"); + struct qbe_value one = constl(1); + pushi(ctx->current, &remain, Q_SUB, &appendlen, &one, NULL); + pushi(ctx->current, &remain, Q_MUL, &remain, &membsz, NULL); + pushi(ctx->current, NULL, Q_CALL, &rtfunc, &next, &last, &remain, NULL); + } else { + gen_store(ctx, item, value); } return gv_void; @@ -1900,74 +1916,67 @@ gen_expr_if_with(struct gen_context *ctx, static struct gen_value gen_expr_insert(struct gen_context *ctx, const struct expression *expr) { - const struct expression *objexpr = expr->insert.expr; + // XXX: A lot of this code is identical to the corresponding append + // code, maybe we can/should deduplicate it + assert(expr->append.length == NULL); + const struct expression *objexpr = expr->append.object; assert(objexpr->type == EXPR_ACCESS && objexpr->access.type == ACCESS_INDEX); - - const struct expression *arrayexpr = objexpr->access.array; - struct gen_value slice = gen_expr(ctx, arrayexpr); + const struct expression *arexpr = objexpr->access.array; + struct gen_value slice = gen_expr(ctx, arexpr); slice = gen_autoderef(ctx, slice); + struct qbe_value qslice = mkqval(ctx, &slice); struct gen_value index = gen_expr(ctx, objexpr->access.index); struct qbe_value qindex = mkqval(ctx, &index); - const struct type *sltype = type_dereference(arrayexpr->result); - const struct type *mtype = type_dealias(sltype)->array.members; - - enum qbe_instr load = load_for_type(ctx, &builtin_type_size); - struct qbe_value qslice = mklval(ctx, &slice); - struct qbe_value offs = constl(builtin_type_size.size); struct qbe_value lenptr = mkqtmp(ctx, ctx->arch.ptr, ".%d"); + struct qbe_value prevlen = mkqtmp(ctx, ctx->arch.sz, ".%d"); + struct qbe_value offs = constl(builtin_type_size.size); pushi(ctx->current, &lenptr, Q_ADD, &qslice, &offs, NULL); - struct qbe_value len = mkqtmp(ctx, ctx->arch.sz, ".%d"); - pushi(ctx->current, &len, load, &lenptr, NULL); - - struct qbe_value valid = mkqtmp(ctx, &qbe_word, ".%d"); - pushi(ctx->current, &valid, Q_CULEL, &qindex, &len, NULL); + enum qbe_instr load = load_for_type(ctx, &builtin_type_size); + pushi(ctx->current, &prevlen, load, &lenptr, NULL); - struct qbe_statement linvalid, lvalid; - struct qbe_value binvalid = mklabel(ctx, &linvalid, ".%d"); - struct qbe_value bvalid = mklabel(ctx, &lvalid, ".%d"); + struct qbe_value appendlen = constl(1); + const struct type *valtype = type_dealias(expr->append.value->result); - pushi(ctx->current, NULL, Q_JNZ, &valid, &bvalid, &binvalid, NULL); - push(&ctx->current->body, &linvalid); - gen_fixed_abort(ctx, expr->loc, ABORT_OOB); - push(&ctx->current->body, &lvalid); - - size_t args = 0; - for (struct append_values *value = expr->insert.values; - value; value = value->next) { - args++; + struct gen_value value; + struct qbe_value qvalue; + if (!expr->append.is_multi || valtype->storage != STORAGE_ARRAY) { + // We use gen_expr_at for the array case to avoid a copy + value = gen_expr(ctx, expr->append.value); + qvalue = mkqval(ctx, &value); } - struct qbe_value nadd = constl(args); - struct qbe_value newlen = mkqtmp(ctx, ctx->arch.sz, ".%d"); - pushi(ctx->current, &newlen, Q_ADD, &len, &nadd, NULL); - struct gen_value vobj; - struct qbe_value vlen = constl(0), vdata; - if (expr->insert.variadic) { - vobj = gen_expr(ctx, expr->insert.variadic); - struct qbe_value lval = mklval(ctx, &vobj); - vdata = mkqtmp(ctx, ctx->arch.ptr, ".%d"); - pushi(ctx->current, &vdata, load, &lval, NULL); - - struct qbe_value vptr = mkqtmp(ctx, ctx->arch.ptr, ".%d"); - vlen = mkqtmp(ctx, ctx->arch.sz, ".%d"); - pushi(ctx->current, &vptr, Q_ADD, &lval, &offs, NULL); - pushi(ctx->current, &vlen, load, &vptr, NULL); - pushi(ctx->current, &newlen, Q_ADD, &newlen, &vlen, NULL); + if (expr->append.is_multi) { + if (valtype->storage == STORAGE_ARRAY) { + assert(valtype->array.length != SIZE_UNDEFINED); + appendlen = constl(valtype->array.length); + } else { + value = gen_expr(ctx, expr->append.value); + qvalue = mkqval(ctx, &value); + appendlen = mkqtmp(ctx, ctx->arch.sz, ".%d"); + struct qbe_value ptr = mkqtmp(ctx, ctx->arch.ptr, ".%d"); + offs = constl(builtin_type_size.size); + pushi(ctx->current, &ptr, Q_ADD, &qvalue, &offs, NULL); + pushi(ctx->current, &appendlen, load, &ptr, NULL); + } } + struct qbe_value newlen = mkqtmp(ctx, ctx->arch.sz, ".%d"); + pushi(ctx->current, &newlen, Q_ADD, &prevlen, &appendlen, NULL); enum qbe_instr store = store_for_type(ctx, &builtin_type_size); pushi(ctx->current, NULL, store, &newlen, &lenptr, NULL); - struct qbe_value membsz = constl(mtype->size); - if (!expr->insert.is_static) { + struct qbe_value ptr = mkqtmp(ctx, ctx->arch.ptr, ".%d"); + const struct type *mtype = type_dealias(slice.type)->array.members; + struct qbe_value membsz = constl(mtype->size); + if (!expr->append.is_static) { struct qbe_value rtfunc = mkrtfunc(ctx, "rt.ensure"); struct qbe_value lval = mklval(ctx, &slice); pushi(ctx->current, NULL, Q_CALL, &rtfunc, &lval, &membsz, NULL); } else { - struct qbe_value ptr = mkqtmp(ctx, ctx->arch.ptr, ".%d"); - pushi(ctx->current, &ptr, Q_ADD, &lenptr, &offs, NULL); + offs = constl(builtin_type_size.size * 2); + pushi(ctx->current, &ptr, Q_ADD, &qslice, &offs, NULL); struct qbe_value cap = mkqtmp(ctx, ctx->arch.ptr, ".%d"); pushi(ctx->current, &cap, load, &ptr, NULL); @@ -1977,45 +1986,44 @@ gen_expr_insert(struct gen_context *ctx, const struct expression *expr) struct qbe_value valid = mkqtmp(ctx, &qbe_word, ".%d"); pushi(ctx->current, &valid, Q_CULEL, &newlen, &cap, NULL); pushi(ctx->current, NULL, Q_JNZ, &valid, &bvalid, &binvalid, NULL); - push(&ctx->current->body, &linvalid); + push(&ctx->current->body, &linvalid); gen_fixed_abort(ctx, expr->loc, ABORT_OOB); - push(&ctx->current->body, &lvalid); } struct qbe_value base = mkqtmp(ctx, ctx->arch.ptr, ".%d"); pushi(ctx->current, &base, load, &qslice, NULL); - struct qbe_value src = mkqtmp(ctx, ctx->arch.ptr, ".%d"); - pushi(ctx->current, &src, Q_MUL, &qindex, &membsz, NULL); - pushi(ctx->current, &src, Q_ADD, &base, &src, NULL); + pushi(ctx->current, &ptr, Q_MUL, &qindex, &membsz, NULL); + pushi(ctx->current, &ptr, Q_ADD, &base, &ptr, NULL); + struct qbe_value nbyte = mkqtmp(ctx, ctx->arch.sz, ".%d"); struct qbe_value dest = mkqtmp(ctx, ctx->arch.ptr, ".%d"); - pushi(ctx->current, &nbyte, Q_ADD, &nadd, &vlen, NULL); struct qbe_value ncopy = mkqtmp(ctx, ctx->arch.sz, ".%d"); - pushi(ctx->current, &ncopy, Q_SUB, &len, &qindex, NULL); - pushi(ctx->current, &nbyte, Q_MUL, &nbyte, &membsz, NULL); + pushi(ctx->current, &nbyte, Q_MUL, &appendlen, &membsz, NULL); + pushi(ctx->current, &ncopy, Q_SUB, &prevlen, &qindex, NULL); pushi(ctx->current, &ncopy, Q_MUL, &ncopy, &membsz, NULL); - pushi(ctx->current, &dest, Q_ADD, &src, &nbyte, NULL); + pushi(ctx->current, &dest, Q_ADD, &ptr, &nbyte, NULL); struct qbe_value rtfunc = mkrtfunc(ctx, "rt.memmove"); - pushi(ctx->current, NULL, Q_CALL, &rtfunc, &dest, &src, &ncopy, NULL); + pushi(ctx->current, NULL, Q_CALL, &rtfunc, &dest, &ptr, &ncopy, NULL); - struct gen_value gv = { + struct gen_value item = { .kind = GV_TEMP, .type = mtype, - .name = src.name, + .name = ptr.name, }; - for (struct append_values *value = expr->insert.values; - value; value = value->next) { - gen_expr_at(ctx, value->expr, gv); - pushi(ctx->current, &src, Q_ADD, &src, &membsz, NULL); - } - if (expr->insert.variadic) { - rtfunc = mkrtfunc(ctx, "rt.memcpy"); - pushi(ctx->current, &nbyte, Q_MUL, &vlen, &membsz, NULL); - pushi(ctx->current, NULL, Q_CALL, &rtfunc, &src, &vdata, &nbyte, NULL); + if (expr->append.is_multi && valtype->storage == STORAGE_ARRAY) { + item.type = valtype; + gen_expr_at(ctx, expr->append.value, item); + } else if (expr->append.is_multi && valtype->storage == STORAGE_SLICE) { + struct qbe_value qsrc = mkqtmp(ctx, ctx->arch.ptr, ".%d"); + struct qbe_value rtfunc = mkrtfunc(ctx, "rt.memmove"); + pushi(ctx->current, &qsrc, load, &qvalue, NULL); + pushi(ctx->current, NULL, Q_CALL, &rtfunc, &ptr, &qsrc, &nbyte, NULL); + } else { + gen_store(ctx, item, value); } return gv_void; diff --git a/src/parse.c b/src/parse.c @@ -1273,79 +1273,76 @@ parse_allocation_expression(struct lexer *lexer) } static struct ast_expression * -parse_slice_mutation(struct lexer *lexer, bool is_static) +parse_append_insert(struct lexer *lexer, struct location *loc, + bool is_static, enum expr_type etype) { - struct ast_expression *exp = NULL; struct token tok = {0}; - switch (lex(lexer, &tok)) { - case T_APPEND: - case T_INSERT: - exp = mkexpr(&tok.loc); - exp->type = tok.token == T_APPEND ? EXPR_APPEND : EXPR_INSERT; - want(lexer, T_LPAREN, NULL); - - struct ast_append_values **next; - switch (exp->type) { - case EXPR_APPEND: - exp->append.expr = parse_object_selector(lexer); - exp->append.is_static = is_static; - next = &exp->append.values; - break; - case EXPR_INSERT: - exp->insert.expr = parse_object_selector(lexer); - exp->insert.is_static = is_static; - next = &exp->insert.values; - break; - default: - assert(0); - } - - want(lexer, T_COMMA, NULL); + struct ast_expression *expr = mkexpr(loc); + expr->type = etype; - while (tok.token != T_RPAREN) { - if (lex(lexer, &tok) == T_ELLIPSIS) { - exp->append.variadic = - parse_expression(lexer); - break; - } - *next = xcalloc(1, sizeof(struct ast_append_values)); - unlex(lexer, &tok); - (*next)->expr = parse_expression(lexer); + want(lexer, T_LPAREN, NULL); + expr->append.object = parse_object_selector(lexer); + if (etype == EXPR_INSERT) { + synassert_msg(expr->append.object->access.type == ACCESS_INDEX, + "expected indexing expression", &tok); + } + want(lexer, T_COMMA, NULL); + expr->append.value = parse_expression(lexer); + expr->append.is_static = is_static; - lex(lexer, &tok); - if (tok.token == T_ELLIPSIS) { - exp->append.variadic = (*next)->expr; - free(*next); - *next = NULL; - if (lex(lexer, &tok) != T_COMMA) { - unlex(lexer, &tok); - } - want(lexer, T_RPAREN, &tok); - break; - } else if (tok.token != T_COMMA) { - unlex(lexer, &tok); - want(lexer, T_RPAREN, &tok); - break; - } + switch (lex(lexer, &tok)) { + case T_ELLIPSIS: + expr->append.is_multi = true; + break; + default: + unlex(lexer, &tok); + break; + } - next = &(*next)->next; - } + switch (lex(lexer, &tok)) { + case T_RPAREN: + // This space deliberately left blank break; - case T_DELETE: - exp = mkexpr(&tok.loc); - exp->type = EXPR_DELETE; - want(lexer, T_LPAREN, NULL); - exp->delete.expr = parse_expression(lexer); - exp->delete.is_static = is_static; + case T_COMMA: + expr->append.length = parse_expression(lexer); want(lexer, T_RPAREN, NULL); break; default: - assert(0); + synassert(false, &tok, T_RPAREN, T_COMMA, T_EOF); } + + return expr; +} + +static struct ast_expression * +parse_delete(struct lexer *lexer, struct location *loc, bool is_static) +{ + struct ast_expression *exp = mkexpr(loc); + exp->type = EXPR_DELETE; + want(lexer, T_LPAREN, NULL); + exp->delete.expr = parse_expression(lexer); + exp->delete.is_static = is_static; + want(lexer, T_RPAREN, NULL); return exp; } static struct ast_expression * +parse_slice_mutation(struct lexer *lexer, bool is_static) +{ + struct token tok = {0}; + switch (lex(lexer, &tok)) { + case T_APPEND: + case T_INSERT: + return parse_append_insert(lexer, &tok.loc, is_static, + tok.token == T_APPEND ? EXPR_APPEND : EXPR_INSERT); + case T_DELETE: + return parse_delete(lexer, &tok.loc, is_static); + default: + abort(); // Invariant + } +} + +static struct ast_expression * parse_postfix_expression(struct lexer *lexer, struct ast_expression *lvalue) { if (lvalue == NULL) { diff --git a/tests/19-append.ha b/tests/19-append.ha @@ -1,72 +1,61 @@ -use rt; +fn basics() void = { + let x: []int = []; + append(x, 1); + append(x, 2); + append(x, 3); + assert(len(x) == 3); + assert(x[0] == 1 && x[1] == 2 && x[2] == 3); + free(x); +}; + +fn multi() void = { + let x: []int = []; + append(x, [1, 2, 3]...); + assert(len(x) == 3); -fn simple() void = { - let x: []int = alloc([1, 2, 3], 6); - append(x, 4, 5, 6); + let y: []int = [4, 5, 6]; + append(x, y...); assert(len(x) == 6); - assert(x[0] == 1 && x[1] == 2 && x[2] == 3 && x[3] == 4 && x[4] == 5); - assert(x[5] == 6); - let y = &x; - append(y, 7, 8); - let z = &y; - append(y, 9); - assert(x[0] == 1 && x[1] == 2 && x[2] == 3 && x[3] == 4 && x[4] == 5); - assert(x[5] == 6 && x[6] == 7 && x[7] == 8 && x[8] == 9); - let y: [][]int = alloc([[1]], 1z); - let z = [2, 3, 4]; - append(y, y...); - append(y, z); - assert(len(y) == 3); - assert(len(y[0]) == 1 && len(y[1]) == 1 && len(y[2]) == 3); - assert(y[0][0] == 1); - assert(y[1][0] == 1); - assert(y[2][0] == 2 && y[2][1] == 3 && y[2][2] == 4); + for (let i = 0z; i < len(x); i += 1) { + assert(x[i] == i: int + 1); + }; + free(x); - free(y); }; -fn variadic() void = { - let x: []int = alloc([1, 2], 2z); - append(x, 4, [8, 16, 32, 64]...); - assert(len(x) == 7); - assert(x[0] == 1 && x[1] == 2 && x[2] == 4 && x[3] == 8 && x[4] == 16); - assert(x[5] == 32 && x[6] == 64); +fn _static() void = { + let buf: [32]int = [0...]; + let x = buf[..0]; + static append(x, 1); + static append(x, 2); + static append(x, 3); + assert(len(x) == 3); - let y: []int = alloc([1, 2, 3], 3); - let z = [128, 256]; - append(y, x...); - let w = &y; - append(w, z...); - assert(len(y) == 12); - assert(y[0] == 1 && y[1] == 2 && y[2] == 3 && y[3] == 1 && y[4] == 2); - assert(y[5] == 4 && y[6] == 8 && y[7] == 16 && y[8] == 32); - assert(y[9] == 64 && y[10] == 128 && y[11] == 256); - free(x); - free(y); + static append(x, [4, 5, 6]...); + assert(len(x) == 6); + + for (let i = 0z; i < len(x); i += 1) { + assert(x[i] == i: int + 1); + assert(buf[i] == i: int + 1); + }; }; -fn static_append() void = { - let buf: [4]int = [0...]; - let x = buf[..0]; - static append(x, 1, 2); - let y = &x; - static append(y, [3, 4]...); - assert(x[0] == 1 && x[1] == 2 && x[2] == 3 && x[3] == 4); - assert(buf[0] == 1 && buf[1] == 2 && buf[2] == 3 && buf[3] == 4); +fn withlength() void = { + let x: []int = []; + append(x, [42...], 10); - let buf: [4]int = [1, 2, 0...]; - let x = buf[..2]; - static append(x, 3, 4); - assert(x[0] == 1 && x[1] == 2 && x[2] == 3 && x[3] == 4); - assert(buf[0] == 1 && buf[1] == 2 && buf[2] == 3 && buf[3] == 4); + assert(len(x) == 10); + for (let i = 0z; i < len(x); i += 1) { + assert(x[i] == 42); + }; + + free(x); }; export fn main() void = { - simple(); - variadic(); - static_append(); - - assert(rt::compile("fn test() void = append([1], 2);") != 0); - assert(rt::compile("fn test() void = { let x: []int = alloc([1], 1z); append(x[..], 2); };") != 0); + basics(); + multi(); + _static(); + withlength(); }; diff --git a/tests/22-delete.ha b/tests/22-delete.ha @@ -31,7 +31,7 @@ fn slice() void = { assert(len(x) == 0); assert(s.capacity < 5); - append(x, 6, 7, 8, 9); + append(x, [6, 7, 8, 9]...); delete(x[1..3]); assert(len(x) == 2); assert(x[0] == 6 && x[1] == 9); diff --git a/tests/28-insert.ha b/tests/28-insert.ha @@ -1,57 +1,56 @@ -fn sleq(a: []int, b: []int) bool = { - if (len(a) != len(b)) { - return false; - }; - for (let i = 0z; i < len(a); i += 1) { - if (a[i] != b[i]) { - return false; - }; - }; - return true; -}; - fn basics() void = { - let x: []int = []; - defer free(x); - append(x, 1, 2, 3, 4, 5, 6); - insert(x[2], 7, 8, 9); - assert(sleq(x, [1, 2, 7, 8, 9, 3, 4, 5, 6])); - - let x: []int = alloc([], 9); - defer free(x); - append(x, 1, 2, 3, 4, 5, 6); - let y = &x; - insert(y[2], 7, 8, 9); - assert(sleq(x, [1, 2, 7, 8, 9, 3, 4, 5, 6])); + let x: []int = alloc([1, 2, 5]); + insert(x[2], 4); + insert(x[2], 3); + assert(len(x) == 5); + for (let i = 0z; i < len(x); i += 1) { + assert(x[i] == i: int + 1); + }; + insert(x[0], 42); + assert(len(x) == 6 && x[0] == 42); + free(x); }; -fn variadic() void = { - let x: []int = []; - defer free(x); - append(x, 1, 2, 3, 4, 5, 6); - insert(x[2], [7, 8, 9]...); - assert(sleq(x, [1, 2, 7, 8, 9, 3, 4, 5, 6])); +fn multi() void = { + let x: []int = alloc([1, 2, 5]); + insert(x[2], [3, 4]...); + assert(len(x) == 5); + for (let i = 0z; i < len(x); i += 1) { + assert(x[i] == i: int + 1); + }; + free(x); - let x: []int = []; - defer free(x); - let y = &x; - let z = &y; - append(y, 1, 2, 3, 4, 5, 6); - insert(z[2], 7, 8, 9, [10, 11, 12]...); - assert(sleq(x, [1, 2, 7, 8, 9, 10, 11, 12, 3, 4, 5, 6])); + let x: []int = alloc([1, 2, 5]); + let y: []int = [3, 4]; + insert(x[2], y...); + assert(len(x) == 5); + for (let i = 0z; i < len(x); i += 1) { + assert(x[i] == i: int + 1); + }; + free(x); }; -fn static_insert() void = { - let buf: [4]int = [0...]; - let x = buf[..0]; - static insert(x[0], 1, 2); - static insert(x[1], [3, 4]...); - assert(x[0] == 1 && x[1] == 3 && x[2] == 4 && x[3] == 2); - assert(buf[0] == 1 && buf[1] == 3 && buf[2] == 4 && buf[3] == 2); +fn _static() void = { + let buf: [32]int = [1, 2, 5, 42...]; + let x = buf[..3]; + static insert(x[2], 4); + static insert(x[2], 3); + assert(len(x) == 5); + for (let i = 0z; i < len(x); i += 1) { + assert(x[i] == i: int + 1); + assert(buf[i] == i: int + 1); + }; + let z: []int = [1, 2, 3, 4]; + static insert(x[2], [1, 2, 3, 4]...); + static insert(x[2], z...); + for (let i = len(x); i < len(buf); i += 1) { + assert(buf[i] == 42); + }; }; export fn main() void = { basics(); - variadic(); - static_insert(); + multi(); + _static(); + return; };