commit aba6bcec52f191372537f40d10d4c12a5888bdc8
parent 556ae5103bc7a5ee0f11ee275c22ebba1dcc67df
Author: Drew DeVault <sir@cmpwn.com>
Date: Tue, 21 Dec 2021 12:56:07 +0100
Overhaul expandable arrays
This improves the design of expandable arrays somewhat so that we are
able to use them in a broader set of contexts, notably for the coming
allocation improvements.
Essentially, this adds the "expandable" tag to the array type itself, so
that an expression of [1, 2, 3...] becomes a [3]int with the expandable
tag set, rather than the previous behavior of looking into the type hint
to find a suitable length.
This is an ABI breaking change.
Signed-off-by: Drew DeVault <sir@cmpwn.com>
Diffstat:
8 files changed, 132 insertions(+), 67 deletions(-)
diff --git a/include/expr.h b/include/expr.h
@@ -168,7 +168,6 @@ struct expression_compound {
struct array_constant {
struct expression *value;
struct array_constant *next;
- bool expand;
};
// Invariant: these are sorted by field offset
diff --git a/include/type_store.h b/include/type_store.h
@@ -39,7 +39,7 @@ const struct type *type_store_lookup_pointer(struct type_store *store,
const struct type *referent, unsigned int ptrflags);
const struct type *type_store_lookup_array(struct type_store *store,
- const struct type *members, size_t len);
+ const struct type *members, size_t len, bool expandable);
const struct type *type_store_lookup_slice(struct type_store *store,
const struct type *members);
diff --git a/include/types.h b/include/types.h
@@ -56,6 +56,7 @@ struct type_alias {
struct type_array {
size_t length; // SIZE_UNDEFINED for [*] and slices
const struct type *members;
+ bool expandable;
};
struct type_enum_value {
diff --git a/src/check.c b/src/check.c
@@ -995,7 +995,7 @@ lower_vaargs(struct context *ctx,
// XXX: This error handling is minimum-effort and bad
const struct type *hint = type_store_lookup_array(
- ctx->store, type, SIZE_UNDEFINED);
+ ctx->store, type, SIZE_UNDEFINED, false);
check_expression(ctx, &val, vaargs, hint);
if (vaargs->result->storage != STORAGE_ARRAY
|| vaargs->result->array.members != type) {
@@ -1162,17 +1162,20 @@ check_expr_array(struct context *ctx,
const struct type *hint)
{
size_t len = 0;
- bool expandable = false;
+ bool expand = false;
struct ast_array_constant *item = aexpr->constant.array;
struct array_constant *cur, **next = &expr->constant.array;
const struct type *type = NULL;
if (hint) {
hint = type_dealias(hint);
- if (hint->storage == STORAGE_ARRAY
- || hint->storage == STORAGE_SLICE) {
+
+ size_t narray = 0;
+ switch (hint->storage) {
+ case STORAGE_ARRAY:
+ case STORAGE_SLICE:
type = hint->array.members;
- } else if (hint->storage == STORAGE_TAGGED) {
- size_t narray = 0;
+ break;
+ case STORAGE_TAGGED:
for (const struct type_tagged_union *tu = &hint->tagged;
tu; tu = tu->next) {
const struct type *t = type_dealias(tu->type);
@@ -1186,8 +1189,10 @@ check_expr_array(struct context *ctx,
if (narray != 1) {
type = hint = NULL;
}
- } else {
+ break;
+ default:
hint = NULL;
+ break;
}
}
@@ -1209,8 +1214,7 @@ check_expr_array(struct context *ctx,
}
if (item->expand) {
- expandable = true;
- expr->constant.array->expand = true;
+ expand = true;
assert(!item->next);
}
@@ -1219,29 +1223,11 @@ check_expr_array(struct context *ctx,
++len;
}
- if (expandable) {
- if (hint == NULL) {
- error(ctx, aexpr->loc, expr,
- "Cannot expand array for inferred type");
- return;
- }
- if (hint->storage != STORAGE_ARRAY
- || hint->array.length == SIZE_UNDEFINED
- || hint->array.length < len) {
- error(ctx, aexpr->loc, expr,
- "Cannot expand array into destination type");
- return;
- }
- expr->result = type_store_lookup_array(ctx->store,
- type, hint->array.length);
- } else {
- if (type == NULL) {
- error(ctx, aexpr->loc, expr,
- "Cannot infer array type from context, try casting it to the desired type");
- return;
- }
- expr->result = type_store_lookup_array(ctx->store, type, len);
+ if (type == NULL) {
+ error(ctx, aexpr->loc, expr, "Cannot infer array type from context, try casting it to the desired type");
+ return;
}
+ expr->result = type_store_lookup_array(ctx->store, type, len, expand);
}
static const struct type *
@@ -3012,6 +2998,15 @@ check_global(struct context *ctx,
expect(&adecl->init->loc,
type_is_assignable(type, initializer->result),
"Constant type is not assignable from initializer type");
+
+ bool context = adecl->type
+ && adecl->type->storage == STORAGE_ARRAY
+ && adecl->type->array.contextual;
+ if (context) {
+ // XXX: Do we need to do anything more here
+ type = initializer->result;
+ }
+
initializer = lower_implicit_cast(type, initializer);
struct expression *value =
diff --git a/src/eval.c b/src/eval.c
@@ -310,7 +310,6 @@ eval_const(struct context *ctx, struct expression *in, struct expression *out)
arr = arr->next) {
struct array_constant *aconst = *next =
xcalloc(sizeof(struct array_constant), 1);
- aconst->expand = arr->expand;
aconst->value = xcalloc(sizeof(struct expression), 1);
eval_expr(ctx, arr->value, aconst->value);
next = &aconst->next;
@@ -359,6 +358,28 @@ eval_const(struct context *ctx, struct expression *in, struct expression *out)
return EVAL_OK;
}
+static void
+eval_expand_array(struct context *ctx,
+ const struct type *intype, const struct type *outtype,
+ struct expression *in, struct expression *out)
+{
+ assert(in->type == EXPR_CONSTANT);
+ assert(out->type == EXPR_CONSTANT);
+ assert(intype->storage == STORAGE_ARRAY);
+ assert(outtype->storage == STORAGE_ARRAY);
+ struct array_constant *array_in = in->constant.array;
+ struct array_constant **next = &out->constant.array;
+ for (size_t i = 0; i < outtype->array.length; i++) {
+ struct array_constant *item = *next =
+ xcalloc(1, sizeof(struct array_constant));
+ item->value = array_in->value;
+ next = &item->next;
+ if (array_in->next) {
+ array_in = array_in->next;
+ }
+ }
+}
+
enum eval_result
eval_cast(struct context *ctx, struct expression *in, struct expression *out)
{
@@ -370,7 +391,9 @@ eval_cast(struct context *ctx, struct expression *in, struct expression *out)
const struct type *to = type_dealias(in->result),
*from = type_dealias(val.result);
- if (to->storage == from->storage) {
+ // The STORAGE_ARRAY exception is to make sure we handle expandable
+ // arrays at this point.
+ if (to->storage == from->storage && to->storage != STORAGE_ARRAY) {
*out = val;
return EVAL_OK;
}
@@ -416,6 +439,13 @@ eval_cast(struct context *ctx, struct expression *in, struct expression *out)
}
return EVAL_OK;
case STORAGE_ARRAY:
+ assert(from->storage == STORAGE_ARRAY);
+ if (from->array.expandable) {
+ eval_expand_array(ctx, from, to, &val, out);
+ } else {
+ out->constant = val.constant;
+ }
+ return EVAL_OK;
case STORAGE_SLICE:
assert(val.result->storage == STORAGE_ARRAY);
out->constant = val.constant;
@@ -532,7 +562,6 @@ constant_default(struct context *ctx, struct expression *v)
case STORAGE_ARRAY:
case STORAGE_SLICE:
v->constant.array = xcalloc(1, sizeof(struct array_constant));
- v->constant.array->expand = true;
v->constant.array->value = xcalloc(1, sizeof(struct expression));
v->constant.array->value->type = EXPR_CONSTANT;
v->constant.array->value->result =
diff --git a/src/gen.c b/src/gen.c
@@ -1141,6 +1141,11 @@ cast_prefers_at(const struct expression *expr)
if (type_dealias(to)->storage == STORAGE_TAGGED) {
return true;
}
+ // array => array
+ if (type_dealias(to)->storage == STORAGE_ARRAY
+ && type_dealias(from)->storage == STORAGE_ARRAY) {
+ return true;
+ }
// array => slice
if (type_dealias(from)->storage == STORAGE_ARRAY &&
type_dealias(to)->storage == STORAGE_SLICE) {
@@ -1150,6 +1155,52 @@ cast_prefers_at(const struct expression *expr)
}
static void
+gen_expr_cast_array_at(struct gen_context *ctx,
+ const struct expression *expr, struct gen_value out)
+{
+ const struct type *typeout = type_dealias(expr->result);
+ const struct type *typein = type_dealias(expr->cast.value->result);
+ gen_expr_at(ctx, expr->cast.value, out);
+ if (!typein->array.expandable) {
+ return;
+ }
+
+ assert(typein->array.length != SIZE_UNDEFINED
+ && typeout->array.length != SIZE_UNDEFINED);
+ assert(typeout->array.length >= typein->array.length);
+
+ const struct type *membtype = typein->array.members;
+ size_t remain = typeout->array.length - typein->array.length;
+
+ struct qbe_value base = mkqval(ctx, &out);
+ struct qbe_value offs = constl((typein->array.length - 1) * membtype->size);
+ struct gen_value next = mktemp(ctx, membtype, ".%d");
+ struct qbe_value ptr = mklval(ctx, &next);
+ struct gen_value item = mktemp(ctx, membtype, "item.%d");
+ struct qbe_value qitem = mklval(ctx, &item);
+ pushi(ctx->current, &qitem, Q_ADD, &base, &offs, NULL);
+
+ if (remain * membtype->size <= 128) {
+ struct gen_value last = gen_load(ctx, item);
+ for (size_t n = typein->array.length; n < typeout->array.length; ++n) {
+ struct qbe_value offs = constl(n * membtype->size);
+ pushi(ctx->current, &ptr, Q_ADD, &base, &offs, NULL);
+ gen_store(ctx, next, last);
+ }
+ return;
+ }
+
+ offs = constl(typein->array.length * membtype->size);
+ pushi(ctx->current, &ptr, Q_ADD, &base, &offs, NULL);
+
+ struct qbe_value rtfunc = mkrtfunc(ctx, "rt.memcpy");
+ struct qbe_value dtemp = mklval(ctx, &next);
+ struct qbe_value stemp = mklval(ctx, &item);
+ struct qbe_value sz = constl(remain * membtype->size);
+ pushi(ctx->current, NULL, Q_CALL, &rtfunc, &dtemp, &stemp, &sz, NULL);
+}
+
+static void
gen_expr_cast_at(struct gen_context *ctx,
const struct expression *expr, struct gen_value out)
{
@@ -1173,6 +1224,9 @@ gen_expr_cast_at(struct gen_context *ctx,
case STORAGE_TAGGED:
gen_expr_cast_tagged_at(ctx, expr, out);
break;
+ case STORAGE_ARRAY:
+ gen_expr_cast_array_at(ctx, expr, out);
+ break;
default: abort(); // Invariant
}
}
@@ -1386,7 +1440,8 @@ gen_expr_compound_with(struct gen_context *ctx,
static void
gen_const_array_at(struct gen_context *ctx,
- const struct expression *expr, struct gen_value out)
+ const struct expression *expr,
+ struct gen_value out)
{
struct array_constant *aexpr = expr->constant.array;
struct qbe_value base = mkqval(ctx, &out);
@@ -1402,32 +1457,7 @@ gen_const_array_at(struct gen_context *ctx,
++n;
}
- if (!aexpr || !aexpr->expand) {
- return;
- }
-
- struct gen_value next = mktemp(ctx, atype->array.members, ".%d");
- struct qbe_value ptr = mklval(ctx, &next);
-
- size_t remain = atype->array.length - n;
- if (remain * atype->array.members->size <= 128) {
- struct gen_value last = gen_load(ctx, item);
- for (; n < atype->array.length; ++n) {
- struct qbe_value offs = constl(n * atype->array.members->size);
- pushi(ctx->current, &ptr, Q_ADD, &base, &offs, NULL);
- gen_store(ctx, next, last);
- }
- return;
- }
-
- struct qbe_value offs = constl(n * atype->array.members->size);
- pushi(ctx->current, &ptr, Q_ADD, &base, &offs, NULL);
-
- struct qbe_value rtfunc = mkrtfunc(ctx, "rt.memcpy");
- struct qbe_value dtemp = mklval(ctx, &next);
- struct qbe_value stemp = mklval(ctx, &item);
- struct qbe_value sz = constl(remain * atype->array.members->size);
- pushi(ctx->current, NULL, Q_CALL, &rtfunc, &dtemp, &stemp, &sz, NULL);
+ assert(n == atype->array.length);
}
static void
diff --git a/src/type_store.c b/src/type_store.c
@@ -976,13 +976,15 @@ type_store_lookup_pointer(struct type_store *store,
const struct type *
type_store_lookup_array(struct type_store *store,
- const struct type *members, size_t len)
+ const struct type *members, size_t len, bool expandable)
{
struct type array = {
.storage = STORAGE_ARRAY,
.array = {
.members = members,
.length = len,
+ // TODO: Define expandable semantics better in spec
+ .expandable = expandable,
},
.size = len == SIZE_UNDEFINED
? SIZE_UNDEFINED : members->size * len,
diff --git a/src/types.c b/src/types.c
@@ -397,6 +397,7 @@ type_hash(const struct type *type)
case STORAGE_ARRAY:
hash = fnv1a_u32(hash, type_hash(type->array.members));
hash = fnv1a_size(hash, type->array.length);
+ hash = fnv1a_u32(hash, type->array.expandable);
break;
case STORAGE_FUNCTION:
hash = fnv1a_u32(hash, type_hash(type->func.result));
@@ -650,9 +651,17 @@ type_is_assignable(const struct type *to, const struct type *from)
}
return to_secondary->id == from_secondary->id;
case STORAGE_ARRAY:
- return from->storage == STORAGE_ARRAY
- && to->array.length == SIZE_UNDEFINED
- && from->array.length != SIZE_UNDEFINED;
+ if (from->storage != STORAGE_ARRAY) {
+ return false;
+ }
+ if (from->array.expandable) {
+ return to->array.length != SIZE_UNDEFINED
+ && to->array.length >= from->array.length
+ && to->array.members == from->array.members;
+ } else {
+ return to->array.length == SIZE_UNDEFINED
+ && from->array.length != SIZE_UNDEFINED;
+ }
case STORAGE_TAGGED:
return tagged_select_subtype(to, from_orig) != NULL
|| tagged_subset_compat(to, from);
