harec

[hare] Hare compiler, written in C11 for POSIX OSs
Log | Files | Refs | README | LICENSE

eval.c (29328B)


      1 #include <assert.h>
      2 #include <stdarg.h>
      3 #include <stdbool.h>
      4 #include <stdint.h>
      5 #include <stdlib.h>
      6 #include <string.h>
      7 #include "check.h"
      8 #include "eval.h"
      9 #include "expr.h"
     10 #include "scope.h"
     11 #include "type_store.h"
     12 #include "types.h"
     13 #include "util.h"
     14 
     15 static void
     16 error(struct context *ctx, const struct location loc, char *fmt, ...)
     17 {
     18 	va_list ap, copy;
     19 	va_start(ap, fmt);
     20 
     21 	va_copy(copy, ap);
     22 	size_t sz = vsnprintf(NULL, 0, fmt, copy);
     23 	va_end(copy);
     24 
     25 	char *msg = xcalloc(1, sz + 1);
     26 	vsnprintf(msg, sz + 1, fmt, ap);
     27 	va_end(ap);
     28 
     29 	struct errors *next = *ctx->next = xcalloc(1, sizeof(struct errors));
     30 	next->loc = loc;
     31 	next->msg = msg;
     32 	ctx->next = &next->next;
     33 }
     34 
     35 static enum eval_result
     36 eval_access(struct context *ctx, struct expression *in, struct expression *out)
     37 {
     38 	struct expression tmp = {0};
     39 	enum eval_result r;
     40 
     41 	switch (in->access.type) {
     42 	case ACCESS_IDENTIFIER:
     43 		return EVAL_INVALID; // &ident handled in eval_unarithm
     44 	case ACCESS_INDEX:
     45 		r = eval_expr(ctx, in->access.array, &tmp);
     46 		if (r != EVAL_OK) {
     47 			return r;
     48 		}
     49 		const struct array_constant *array = tmp.constant.array;
     50 		r = eval_expr(ctx, in->access.index, &tmp);
     51 		if (r != EVAL_OK) {
     52 			return r;
     53 		}
     54 		for (size_t i = tmp.constant.uval; i > 0; --i) {
     55 			if (array == NULL) {
     56 				error(ctx, in->loc, "slice or array access out of bounds");
     57 				return EVAL_INVALID;
     58 			}
     59 			array = array->next;
     60 		}
     61 		return eval_expr(ctx, array->value, out);
     62 	case ACCESS_FIELD:
     63 		r = eval_expr(ctx, in->access._struct, &tmp);
     64 		if (r != EVAL_OK) {
     65 			return r;
     66 		}
     67 		const struct struct_constant *fields = tmp.constant._struct;
     68 		for (; fields != NULL; fields = fields->next) {
     69 			if (!strcmp(fields->field->name, in->access.field->name)) {
     70 				break;
     71 			}
     72 		}
     73 		if (fields == NULL) {
     74 			return EVAL_INVALID;
     75 		}
     76 		return eval_expr(ctx, fields->value, out);
     77 	case ACCESS_TUPLE:
     78 		r = eval_expr(ctx, in->access.tuple, &tmp);
     79 		if (r != EVAL_OK) {
     80 			return r;
     81 		}
     82 		const struct tuple_constant *tuple = tmp.constant.tuple;
     83 		for (size_t i = in->access.tindex; i > 0; --i) {
     84 			if (tuple == NULL) {
     85 				// out of bounds
     86 				return EVAL_INVALID;
     87 			}
     88 			tuple = tuple->next;
     89 		}
     90 		return eval_expr(ctx, tuple->value, out);
     91 	}
     92 
     93 	return EVAL_OK;
     94 }
     95 
     96 static uintmax_t
     97 itrunc(const struct type *type, uintmax_t val)
     98 {
     99 	switch (type->storage) {
    100 	case STORAGE_CHAR:
    101 	case STORAGE_U8:
    102 		return (uint8_t)val;
    103 	case STORAGE_U16:
    104 		return (uint16_t)val;
    105 	case STORAGE_U32:
    106 	case STORAGE_RCONST:
    107 	case STORAGE_RUNE:
    108 		return (uint32_t)val;
    109 	case STORAGE_U64:
    110 		return (uint64_t)val;
    111 	case STORAGE_I8:
    112 		return (int8_t)val;
    113 	case STORAGE_I16:
    114 		return (int16_t)val;
    115 	case STORAGE_I32:
    116 		return (int32_t)val;
    117 	case STORAGE_I64:
    118 		return (int64_t)val;
    119 	case STORAGE_INT:
    120 		return (int)val;
    121 	case STORAGE_UINT:
    122 		return (unsigned int)val;
    123 	case STORAGE_ARRAY:
    124 	case STORAGE_ICONST:
    125 	case STORAGE_POINTER:
    126 	case STORAGE_SIZE:
    127 	case STORAGE_UINTPTR:
    128 		return val;
    129 	case STORAGE_BOOL:
    130 		return (bool)val;
    131 	case STORAGE_NULL:
    132 		return (uintptr_t)NULL;
    133 	case STORAGE_ALIAS:
    134 		return itrunc(type_dealias(type), val);
    135 	case STORAGE_ENUM:
    136 		return itrunc(type->alias.type, val);
    137 	case STORAGE_ERROR:
    138 		return val;
    139 	case STORAGE_F32:
    140 	case STORAGE_F64:
    141 	case STORAGE_FCONST:
    142 	case STORAGE_FUNCTION:
    143 	case STORAGE_SLICE:
    144 	case STORAGE_STRING:
    145 	case STORAGE_STRUCT:
    146 	case STORAGE_TAGGED:
    147 	case STORAGE_TUPLE:
    148 	case STORAGE_UNION:
    149 	case STORAGE_VALIST:
    150 	case STORAGE_VOID:
    151 		assert(0);
    152 	}
    153 	assert(0);
    154 }
    155 
    156 static double
    157 ftrunc(const struct type *type, double val)
    158 {
    159 	if (type->storage == STORAGE_F32) {
    160 		return (float)val;
    161 	}
    162 	assert(type_is_float(type));
    163 	return val;
    164 }
    165 
    166 static enum eval_result
    167 eval_binarithm(struct context *ctx, struct expression *in, struct expression *out)
    168 {
    169 	struct expression lvalue = {0}, rvalue = {0};
    170 	enum eval_result r = eval_expr(ctx, in->binarithm.lvalue, &lvalue);
    171 	if (r != EVAL_OK) {
    172 		return r;
    173 	}
    174 	r = eval_expr(ctx, in->binarithm.rvalue, &rvalue);
    175 	if (r != EVAL_OK) {
    176 		return r;
    177 	}
    178 
    179 	bool blval = false, brval = false, bval = false;
    180 	intmax_t ilval = 0, irval = 0, ival = 0;
    181 	uintmax_t ulval = 0, urval = 0, uval = 0;
    182 	double flval = 0, frval = 0, fval = 0;
    183 	if (type_is_float(lvalue.result)) {
    184 		flval = lvalue.constant.fval, frval = rvalue.constant.fval;
    185 	} else if (type_is_signed(lvalue.result)) {
    186 		ilval = lvalue.constant.ival, irval = rvalue.constant.ival;
    187 	} else if (type_is_integer(lvalue.result)) {
    188 		ulval = lvalue.constant.uval, urval = rvalue.constant.uval;
    189 	} else if (type_dealias(lvalue.result)->storage == STORAGE_BOOL) {
    190 		blval = lvalue.constant.bval, brval = rvalue.constant.bval;
    191 	}
    192 
    193 	// Type promotion is lowered in check
    194 	assert(lvalue.result->storage == rvalue.result->storage);
    195 	bool neg = false;
    196 	switch (in->binarithm.op) {
    197 	case BIN_BAND:
    198 		assert(type_is_integer(lvalue.result));
    199 		if (type_is_signed(lvalue.result)) {
    200 			ival = itrunc(lvalue.result, ilval) & itrunc(rvalue.result, irval);
    201 		} else {
    202 			uval = itrunc(lvalue.result, ulval) & itrunc(rvalue.result, urval);
    203 		}
    204 		break;
    205 	case BIN_BOR:
    206 		assert(type_is_integer(lvalue.result));
    207 		if (type_is_signed(lvalue.result)) {
    208 			ival = itrunc(lvalue.result, ilval) | itrunc(rvalue.result, irval);
    209 		} else {
    210 			uval = itrunc(lvalue.result, ulval) | itrunc(rvalue.result, urval);
    211 		}
    212 		break;
    213 	case BIN_DIV:
    214 		if (type_is_float(lvalue.result)) {
    215 			fval = ftrunc(lvalue.result, flval) / ftrunc(rvalue.result, frval);
    216 		} else if (type_is_signed(lvalue.result)) {
    217 			uintmax_t r = itrunc(rvalue.result, irval);
    218 			if (r == 0) {
    219 				error(ctx, in->loc, "division by zero");
    220 				return EVAL_INVALID;
    221 			}
    222 			ival = itrunc(lvalue.result, ilval) / r;
    223 		} else {
    224 			assert(type_is_integer(lvalue.result));
    225 			uintmax_t r = itrunc(rvalue.result, urval);
    226 			if (r == 0) {
    227 				error(ctx, in->loc, "division by zero");
    228 				return EVAL_INVALID;
    229 			}
    230 			uval = itrunc(lvalue.result, ulval) / r;
    231 		}
    232 		break;
    233 	case BIN_LSHIFT:
    234 		assert(type_is_integer(lvalue.result));
    235 		assert(type_is_integer(rvalue.result));
    236 		assert(!type_is_signed(rvalue.result));
    237 		uval = itrunc(lvalue.result, ulval) << itrunc(rvalue.result, urval);
    238 		break;
    239 	case BIN_MINUS:
    240 		if (type_is_float(lvalue.result)) {
    241 			fval = ftrunc(lvalue.result, flval) - ftrunc(rvalue.result, frval);
    242 		} else if (type_is_signed(lvalue.result)) {
    243 			ival = itrunc(lvalue.result, ilval) - itrunc(rvalue.result, irval);
    244 		} else {
    245 			assert(type_is_integer(lvalue.result));
    246 			uval = itrunc(lvalue.result, ulval) - itrunc(rvalue.result, urval);
    247 		}
    248 		break;
    249 	case BIN_MODULO:
    250 		assert(type_is_integer(lvalue.result));
    251 		if (type_is_signed(lvalue.result)) {
    252 			uintmax_t r = itrunc(rvalue.result, irval);
    253 			if (r == 0) {
    254 				error(ctx, in->loc, "division by zero");
    255 				return EVAL_INVALID;
    256 			}
    257 			ival = itrunc(lvalue.result, ilval) % itrunc(rvalue.result, irval);
    258 		} else {
    259 			uintmax_t r = itrunc(rvalue.result, urval);
    260 			if (r == 0) {
    261 				error(ctx, in->loc, "division by zero");
    262 				return EVAL_INVALID;
    263 			}
    264 			uval = itrunc(lvalue.result, ulval) % itrunc(rvalue.result, urval);
    265 		}
    266 		break;
    267 	case BIN_PLUS:
    268 		if (type_is_float(lvalue.result)) {
    269 			fval = ftrunc(lvalue.result, flval) + ftrunc(rvalue.result, frval);
    270 		} else if (type_is_signed(lvalue.result)) {
    271 			ival = itrunc(lvalue.result, ilval) + itrunc(rvalue.result, irval);
    272 		} else {
    273 			assert(type_is_integer(lvalue.result));
    274 			uval = itrunc(lvalue.result, ulval) + itrunc(rvalue.result, urval);
    275 		}
    276 		break;
    277 	case BIN_RSHIFT:
    278 		assert(type_is_integer(lvalue.result));
    279 		assert(type_is_integer(rvalue.result));
    280 		assert(!type_is_signed(rvalue.result));
    281 		uval = itrunc(lvalue.result, ulval) >> itrunc(rvalue.result, urval);
    282 		break;
    283 	case BIN_TIMES:
    284 		if (type_is_float(lvalue.result)) {
    285 			fval = ftrunc(lvalue.result, flval) * ftrunc(rvalue.result, frval);
    286 		} else if (type_is_signed(lvalue.result)) {
    287 			ival = itrunc(lvalue.result, ilval) * itrunc(rvalue.result, irval);
    288 		} else {
    289 			assert(type_is_integer(lvalue.result));
    290 			uval = itrunc(lvalue.result, ulval) * itrunc(rvalue.result, urval);
    291 		}
    292 		break;
    293 	case BIN_BXOR:
    294 		assert(type_is_integer(lvalue.result));
    295 		if (type_is_signed(lvalue.result)) {
    296 			ival = itrunc(lvalue.result, ilval) ^ itrunc(rvalue.result, irval);
    297 		} else {
    298 			uval = itrunc(lvalue.result, ulval) ^ itrunc(rvalue.result, urval);
    299 		}
    300 		break;
    301 	// Logical arithmetic
    302 	case BIN_GREATER:
    303 		if (type_is_float(lvalue.result)) {
    304 			bval = ftrunc(lvalue.result, flval) > ftrunc(rvalue.result, frval);
    305 		} else if (type_is_signed(lvalue.result)) {
    306 			bval = itrunc(lvalue.result, ilval) > itrunc(rvalue.result, irval);
    307 		} else {
    308 			assert(type_is_integer(lvalue.result));
    309 			bval = itrunc(lvalue.result, ulval) > itrunc(rvalue.result, urval);
    310 		}
    311 		break;
    312 	case BIN_GREATEREQ:
    313 		if (type_is_float(lvalue.result)) {
    314 			bval = ftrunc(lvalue.result, flval) >= ftrunc(rvalue.result, frval);
    315 		} else if (type_is_signed(lvalue.result)) {
    316 			bval = itrunc(lvalue.result, ilval) >= itrunc(rvalue.result, irval);
    317 		} else {
    318 			assert(type_is_integer(lvalue.result));
    319 			bval = itrunc(lvalue.result, ulval) >= itrunc(rvalue.result, urval);
    320 		}
    321 		break;
    322 	case BIN_LAND:
    323 		assert(type_dealias(lvalue.result)->storage == STORAGE_BOOL
    324 			&& type_dealias(rvalue.result)->storage == STORAGE_BOOL);
    325 		bval = blval && brval;
    326 		break;
    327 	case BIN_NEQUAL:
    328 		neg = true;
    329 		/* fallthrough */
    330 	case BIN_LEQUAL:
    331 		if (type_is_float(lvalue.result)) {
    332 			bval = ftrunc(lvalue.result, flval) == ftrunc(rvalue.result, frval);
    333 		} else if (type_is_signed(lvalue.result)) {
    334 			bval = itrunc(lvalue.result, ilval) == itrunc(rvalue.result, irval);
    335 		} else if (type_is_integer(lvalue.result)
    336 				|| type_dealias(lvalue.result)->storage == STORAGE_POINTER) {
    337 			bval = itrunc(lvalue.result, ulval) == itrunc(rvalue.result, urval);
    338 		} else if (lvalue.result->storage == STORAGE_BOOL) {
    339 			bval = lvalue.constant.bval == rvalue.constant.bval;
    340 		} else {
    341 			assert(type_dealias(lvalue.result)->storage == STORAGE_STRING);
    342 			if (lvalue.constant.string.len != rvalue.constant.string.len) {
    343 				bval = false;
    344 			} else {
    345 				bval = memcmp(lvalue.constant.string.value,
    346 					rvalue.constant.string.value,
    347 					lvalue.constant.string.len) == 0;
    348 			}
    349 		}
    350 		bval = bval != neg;
    351 		break;
    352 	case BIN_LESS:
    353 		if (type_is_float(lvalue.result)) {
    354 			bval = ftrunc(lvalue.result, flval) < ftrunc(rvalue.result, frval);
    355 		} else if (type_is_signed(lvalue.result)) {
    356 			bval = itrunc(lvalue.result, ilval) < itrunc(rvalue.result, irval);
    357 		} else {
    358 			assert(type_is_integer(lvalue.result));
    359 			bval = itrunc(lvalue.result, ulval) < itrunc(rvalue.result, urval);
    360 		}
    361 		break;
    362 	case BIN_LESSEQ:
    363 		if (type_is_float(lvalue.result)) {
    364 			bval = ftrunc(lvalue.result, flval) <= ftrunc(rvalue.result, frval);
    365 		} else if (type_is_signed(lvalue.result)) {
    366 			bval = itrunc(lvalue.result, ilval) <= itrunc(rvalue.result, irval);
    367 		} else {
    368 			assert(type_is_integer(lvalue.result));
    369 			bval = itrunc(lvalue.result, ulval) <= itrunc(rvalue.result, urval);
    370 		}
    371 		break;
    372 	case BIN_LOR:
    373 		assert(type_dealias(lvalue.result)->storage == STORAGE_BOOL
    374 			&& type_dealias(rvalue.result)->storage == STORAGE_BOOL);
    375 		bval = blval || brval;
    376 		break;
    377 	case BIN_LXOR:
    378 		assert(type_dealias(lvalue.result)->storage == STORAGE_BOOL
    379 			&& type_dealias(rvalue.result)->storage == STORAGE_BOOL);
    380 		bval = blval != brval;
    381 		break;
    382 	}
    383 	if (type_is_float(in->result)) {
    384 		out->constant.fval = ftrunc(in->result, fval);
    385 	} else if (type_is_signed(in->result)) {
    386 		out->constant.ival = itrunc(in->result, ival);
    387 	} else if (type_dealias(in->result)->storage == STORAGE_BOOL
    388 			|| type_dealias(in->result)->storage == STORAGE_STRING) {
    389 		out->constant.bval = bval;
    390 	} else {
    391 		assert(type_is_integer(in->result)
    392 			|| type_dealias(in->result)->storage == STORAGE_POINTER);
    393 		out->constant.uval = itrunc(in->result, uval);
    394 	}
    395 	return EVAL_OK;
    396 }
    397 
    398 static enum eval_result
    399 eval_const(struct context *ctx, struct expression *in, struct expression *out)
    400 {
    401 	enum type_storage storage = type_dealias(out->result)->storage;
    402 	if (storage == STORAGE_ENUM) {
    403 		storage = type_dealias(out->result)->alias.type->storage;
    404 	}
    405 	switch (storage) {
    406 	case STORAGE_ALIAS:
    407 	case STORAGE_ENUM:
    408 		assert(0); // Handled above
    409 	case STORAGE_ARRAY:;
    410 		struct array_constant **anext = &out->constant.array;
    411 		for (struct array_constant *arr = in->constant.array; arr;
    412 				arr = arr->next) {
    413 			struct array_constant *aconst = *anext =
    414 				xcalloc(sizeof(struct array_constant), 1);
    415 			aconst->value = xcalloc(sizeof(struct expression), 1);
    416 			enum eval_result r =
    417 				eval_expr(ctx, arr->value, aconst->value);
    418 			if (r != EVAL_OK) {
    419 				return r;
    420 			}
    421 			anext = &aconst->next;
    422 		}
    423 		break;
    424 	case STORAGE_FUNCTION:
    425 	case STORAGE_SLICE:
    426 		assert(0); // TODO
    427 	case STORAGE_STRING:
    428 		out->constant.string.len = in->constant.string.len;
    429 		out->constant.string.value = xcalloc(1, in->constant.string.len);
    430 		memcpy(out->constant.string.value,
    431 			in->constant.string.value,
    432 			in->constant.string.len);
    433 		break;
    434 	case STORAGE_TAGGED:
    435 		out->constant.tagged.tag = in->constant.tagged.tag;
    436 		out->constant.tagged.value = xcalloc(sizeof(struct expression), 1);
    437 		return eval_expr(ctx, in->constant.tagged.value,
    438 				out->constant.tagged.value);
    439 	case STORAGE_STRUCT:;
    440 		struct struct_constant **next = &out->constant._struct;
    441 		for (struct struct_constant *_struct = in->constant._struct;
    442 				_struct; _struct = _struct->next) {
    443 			struct struct_constant *cur = *next =
    444 				xcalloc(sizeof(struct struct_constant), 1);
    445 			cur->field = _struct->field;
    446 			cur->value = xcalloc(sizeof(struct expression), 1);
    447 			enum eval_result r =
    448 				eval_expr(ctx, _struct->value, cur->value);
    449 			if (r != EVAL_OK) {
    450 				return r;
    451 			}
    452 			next = &cur->next;
    453 		}
    454 		break;
    455 	case STORAGE_UNION:
    456 		assert(0); // TODO
    457 	case STORAGE_TUPLE:;
    458 		struct tuple_constant **tnext = &out->constant.tuple;
    459 		for (struct tuple_constant *tuple = in->constant.tuple; tuple;
    460 				tuple = tuple->next) {
    461 			struct tuple_constant *tconst = *tnext =
    462 				xcalloc(1, sizeof(struct tuple_constant));
    463 			tconst->field = tuple->field;
    464 			tconst->value = xcalloc(1, sizeof(struct expression));
    465 			enum eval_result r =
    466 				eval_expr(ctx, tuple->value, tconst->value);
    467 			if (r != EVAL_OK) {
    468 				return r;
    469 			}
    470 			tnext = &tconst->next;
    471 		}
    472 		break;
    473 	case STORAGE_BOOL:
    474 	case STORAGE_CHAR:
    475 	case STORAGE_ERROR:
    476 	case STORAGE_F32:
    477 	case STORAGE_F64:
    478 	case STORAGE_FCONST:
    479 	case STORAGE_I16:
    480 	case STORAGE_I32:
    481 	case STORAGE_I64:
    482 	case STORAGE_I8:
    483 	case STORAGE_ICONST:
    484 	case STORAGE_INT:
    485 	case STORAGE_NULL:
    486 	case STORAGE_POINTER:
    487 	case STORAGE_RCONST:
    488 	case STORAGE_RUNE:
    489 	case STORAGE_SIZE:
    490 	case STORAGE_U16:
    491 	case STORAGE_U32:
    492 	case STORAGE_U64:
    493 	case STORAGE_U8:
    494 	case STORAGE_UINT:
    495 	case STORAGE_UINTPTR:
    496 	case STORAGE_VOID:
    497 		out->constant = in->constant;
    498 		break;
    499 	case STORAGE_VALIST:
    500 		abort(); // Invariant
    501 	}
    502 	return EVAL_OK;
    503 }
    504 
    505 static void
    506 eval_expand_array(struct context *ctx,
    507 	const struct type *intype, const struct type *outtype,
    508 	struct expression *in, struct expression *out)
    509 {
    510 	assert(in->type == EXPR_CONSTANT);
    511 	assert(out->type == EXPR_CONSTANT);
    512 	assert(intype->storage == STORAGE_ARRAY);
    513 	assert(outtype->storage == STORAGE_ARRAY);
    514 	struct array_constant *array_in = in->constant.array;
    515 	struct array_constant **next = &out->constant.array;
    516 	for (size_t i = 0; i < outtype->array.length; i++) {
    517 		struct array_constant *item = *next =
    518 			xcalloc(1, sizeof(struct array_constant));
    519 		item->value = array_in->value;
    520 		next = &item->next;
    521 		if (array_in->next) {
    522 			array_in = array_in->next;
    523 		}
    524 	}
    525 }
    526 
    527 static enum eval_result
    528 eval_type_assertion(struct context *ctx, struct expression *in,
    529 		struct expression *out)
    530 {
    531 	struct expression val = {0};
    532 	enum eval_result r = eval_expr(ctx, in->cast.value, &val);
    533 	if (r != EVAL_OK) {
    534 		return r;
    535 	}
    536 
    537 	const struct type *from = type_dealias(in->cast.value->result);
    538 	assert(from->storage == STORAGE_TAGGED);
    539 	if (val.constant.tagged.tag == in->cast.secondary) {
    540 		out->constant = val.constant.tagged.value->constant;
    541 		return EVAL_OK;
    542 	} else {
    543 		error(ctx, in->loc, "type assertion failed");
    544 		return EVAL_INVALID;
    545 	}
    546 }
    547 
    548 static enum eval_result
    549 eval_type_test(struct context *ctx, struct expression *in,
    550 		struct expression *out)
    551 {
    552 	struct expression val = {0};
    553 	enum eval_result r = eval_expr(ctx, in->cast.value, &val);
    554 	if (r != EVAL_OK) {
    555 		return r;
    556 	}
    557 
    558 	const struct type *from = type_dealias(in->cast.value->result);
    559 	assert(from->storage == STORAGE_TAGGED);
    560 
    561 	out->constant.bval = val.constant.tagged.tag == in->cast.secondary;
    562 
    563 	return EVAL_OK;
    564 }
    565 
    566 static enum eval_result
    567 eval_cast(struct context *ctx, struct expression *in, struct expression *out)
    568 {
    569 	struct expression val = {0};
    570 	enum eval_result r = eval_expr(ctx, in->cast.value, &val);
    571 	if (r != EVAL_OK) {
    572 		return r;
    573 	}
    574 
    575 	const struct type *to = type_dealias(in->result),
    576 		*from = type_dealias(val.result);
    577 	// The STORAGE_ARRAY exception is to make sure we handle expandable
    578 	// arrays at this point.
    579 	if (to->storage == from->storage && to->storage != STORAGE_ARRAY) {
    580 		out->constant = val.constant;
    581 		return EVAL_OK;
    582 	}
    583 
    584 	if (from->storage == STORAGE_ERROR) {
    585 		return EVAL_OK;
    586 	}
    587 
    588 	// XXX: We should also be able to handle expressions which use
    589 	// symbols/identifiers
    590 
    591 	const struct type *subtype;
    592 	switch (to->storage) {
    593 	case STORAGE_POINTER:
    594 		if (from->storage == STORAGE_NULL) {
    595 			out->constant.uval = 0;
    596 			return EVAL_OK;
    597 		}
    598 		assert(from->storage == STORAGE_POINTER
    599 			|| from->storage == STORAGE_UINTPTR);
    600 		out->constant.uval = val.constant.uval;
    601 		return EVAL_OK;
    602 	case STORAGE_ENUM:
    603 	case STORAGE_I16:
    604 	case STORAGE_I32:
    605 	case STORAGE_I64:
    606 	case STORAGE_I8:
    607 	case STORAGE_ICONST:
    608 	case STORAGE_INT:
    609 	case STORAGE_U16:
    610 	case STORAGE_U32:
    611 	case STORAGE_U64:
    612 	case STORAGE_U8:
    613 	case STORAGE_UINT:
    614 	case STORAGE_UINTPTR:
    615 	case STORAGE_SIZE:
    616 	case STORAGE_RCONST:
    617 	case STORAGE_RUNE:
    618 		if (type_is_float(val.result)) {
    619 			out->constant.ival =
    620 				itrunc(to, (intmax_t)val.constant.fval);
    621 		} else if (type_is_signed(val.result)) {
    622 			out->constant.ival = itrunc(to, val.constant.ival);
    623 		} else {
    624 			out->constant.ival = itrunc(to, val.constant.uval);
    625 		}
    626 		return EVAL_OK;
    627 	case STORAGE_ARRAY:
    628 		assert(from->storage == STORAGE_ARRAY);
    629 		if (from->array.expandable) {
    630 			eval_expand_array(ctx, from, to, &val, out);
    631 		} else {
    632 			out->constant = val.constant;
    633 		}
    634 		return EVAL_OK;
    635 	case STORAGE_SLICE:
    636 		assert(val.result->storage == STORAGE_ARRAY);
    637 		out->constant = val.constant;
    638 		return EVAL_OK;
    639 	case STORAGE_F32:
    640 	case STORAGE_F64:
    641 	case STORAGE_FCONST:
    642 		if (type_is_float(val.result)) {
    643 			out->constant.fval = ftrunc(to, val.constant.fval);
    644 		} else if (type_is_signed(val.result)) {
    645 			out->constant.fval =
    646 				ftrunc(to, (double)val.constant.ival);
    647 		} else {
    648 			out->constant.fval =
    649 				ftrunc(to, (double)val.constant.uval);
    650 		}
    651 		return EVAL_OK;
    652 	case STORAGE_TAGGED:
    653 		subtype = tagged_select_subtype(to, val.result, true);
    654 		out->constant.tagged.value =
    655 			xcalloc(1, sizeof(struct expression));
    656 		if (subtype) {
    657 			out->constant.tagged.tag = subtype;
    658 			*out->constant.tagged.value = val;
    659 		} else {
    660 			out->constant.tagged.tag = from;
    661 			*out->constant.tagged.value = val;
    662 		}
    663 		return EVAL_OK;
    664 	case STORAGE_CHAR:
    665 	case STORAGE_NULL:
    666 	case STORAGE_ALIAS:
    667 		assert(0); // Handled above
    668 	case STORAGE_BOOL:
    669 	case STORAGE_FUNCTION:
    670 	case STORAGE_STRING:
    671 	case STORAGE_STRUCT:
    672 	case STORAGE_TUPLE:
    673 	case STORAGE_UNION:
    674 	case STORAGE_VALIST:
    675 		assert(0); // Invariant
    676 	case STORAGE_ERROR:
    677 	case STORAGE_VOID:
    678 		return EVAL_OK;
    679 	}
    680 
    681 	assert(0); // Unreachable
    682 }
    683 
    684 static enum eval_result
    685 eval_measurement(struct context *ctx, struct expression *in, struct expression *out)
    686 {
    687 	assert(in->type == EXPR_MEASURE);
    688 	struct expression obj = {0};
    689 	enum eval_result res;
    690 	switch (in->measure.op) {
    691 	case M_LEN:
    692 		res = eval_expr(ctx, in->measure.value, &obj);
    693 		if (res != EVAL_OK) {
    694 			return res;
    695 		}
    696 
    697 		switch (obj.result->storage) {
    698 		case STORAGE_ARRAY:
    699 		case STORAGE_SLICE:
    700 			break;
    701 		case STORAGE_STRING:
    702 			out->constant.uval = obj.constant.string.len;
    703 			return EVAL_OK;
    704 		default:
    705 			abort(); // Invariant
    706 		}
    707 
    708 		uintmax_t len = 0;
    709 		for (struct array_constant *c = obj.constant.array;
    710 				c != NULL; c = c->next) {
    711 			len++;
    712 		}
    713 		out->constant.uval = len;
    714 		return EVAL_OK;
    715 	case M_ALIGN:
    716 		out->constant.uval = in->measure.dimensions.align;
    717 		return EVAL_OK;
    718 	case M_SIZE:
    719 		out->constant.uval = in->measure.dimensions.size;
    720 		return EVAL_OK;
    721 	case M_OFFSET:
    722 		if (in->measure.value->access.type == ACCESS_FIELD) {
    723 			out->constant.uval =
    724 				in->measure.value->access.field->offset;
    725 		} else {
    726 			assert(in->measure.value->access.type == ACCESS_TUPLE);
    727 			out->constant.uval =
    728 				in->measure.value->access.tvalue->offset;
    729 		}
    730 		return EVAL_OK;
    731 	}
    732 	assert(0);
    733 }
    734 
    735 static enum eval_result
    736 constant_default(struct context *ctx, struct expression *v)
    737 {
    738 	struct expression b = {0};
    739 	switch (type_dealias(v->result)->storage) {
    740 	case STORAGE_ERROR:
    741 	case STORAGE_POINTER:
    742 	case STORAGE_I16:
    743 	case STORAGE_I32:
    744 	case STORAGE_I64:
    745 	case STORAGE_I8:
    746 	case STORAGE_ICONST:
    747 	case STORAGE_INT:
    748 	case STORAGE_U16:
    749 	case STORAGE_U32:
    750 	case STORAGE_U64:
    751 	case STORAGE_U8:
    752 	case STORAGE_UINT:
    753 	case STORAGE_UINTPTR:
    754 	case STORAGE_SIZE:
    755 	case STORAGE_F32:
    756 	case STORAGE_F64:
    757 	case STORAGE_FCONST:
    758 	case STORAGE_CHAR:
    759 	case STORAGE_ENUM:
    760 	case STORAGE_NULL:
    761 	case STORAGE_RCONST:
    762 	case STORAGE_RUNE:
    763 	case STORAGE_SLICE:
    764 	case STORAGE_BOOL:
    765 		break; // calloc does this for us
    766 	case STORAGE_STRUCT:
    767 	case STORAGE_UNION:
    768 		b.type = EXPR_STRUCT;
    769 		b.result = v->result;
    770 		b._struct.autofill = true;
    771 		enum eval_result r = eval_expr(ctx, &b, v);
    772 		assert(r == EVAL_OK);
    773 		break;
    774 	case STORAGE_STRING:
    775 		v->constant.string.value = NULL;
    776 		v->constant.string.len = 0;
    777 		break;
    778 	case STORAGE_ARRAY:
    779 		v->constant.array = xcalloc(1, sizeof(struct array_constant));
    780 		v->constant.array->value = xcalloc(1, sizeof(struct expression));
    781 		v->constant.array->value->type = EXPR_CONSTANT;
    782 		v->constant.array->value->result =
    783 			type_dealias(v->result)->array.members;
    784 		return constant_default(ctx, v->constant.array->value);
    785 		break;
    786 	case STORAGE_TAGGED:
    787 		return EVAL_INVALID;
    788 	case STORAGE_TUPLE:;
    789 		struct tuple_constant **c = &v->constant.tuple;
    790 		for (const struct type_tuple *t = &type_dealias(v->result)->tuple;
    791 				t != NULL; t = t->next) {
    792 			*c = xcalloc(1, sizeof(struct tuple_constant));
    793 			(*c)->field = t;
    794 			(*c)->value = xcalloc(1, sizeof(struct expression));
    795 			(*c)->value->type = EXPR_CONSTANT;
    796 			(*c)->value->result = t->type;
    797 			enum eval_result r = constant_default(ctx, (*c)->value);
    798 			if (r != EVAL_OK) {
    799 				return r;
    800 			}
    801 			c = &(*c)->next;
    802 		}
    803 		break;
    804 	case STORAGE_ALIAS:
    805 	case STORAGE_FUNCTION:
    806 	case STORAGE_VALIST:
    807 		assert(0); // Invariant
    808 	case STORAGE_VOID:
    809 		break; // no-op
    810 	}
    811 
    812 	return EVAL_OK;
    813 }
    814 
    815 static int
    816 field_compar(const void *_a, const void *_b)
    817 {
    818 	const struct struct_constant **a = (const struct struct_constant **)_a;
    819 	const struct struct_constant **b = (const struct struct_constant **)_b;
    820 	return (*a)->field->offset - (*b)->field->offset;
    821 }
    822 
    823 static size_t
    824 count_struct_fields(const struct type *type)
    825 {
    826 	size_t n = 0;
    827 	assert(type->storage == STORAGE_STRUCT || type->storage == STORAGE_UNION);
    828 	for (const struct struct_field *field = type->struct_union.fields;
    829 			field; field = field->next) {
    830 		if (!field->name) {
    831 			n += count_struct_fields(type_dealias(field->type));
    832 		} else {
    833 			++n;
    834 		}
    835 	}
    836 	return n;
    837 }
    838 
    839 static enum eval_result
    840 autofill_struct(struct context *ctx, const struct type *type, struct struct_constant **fields)
    841 {
    842 	enum eval_result r;
    843 	assert(type->storage == STORAGE_STRUCT || type->storage == STORAGE_UNION);
    844 	for (const struct struct_field *field = type->struct_union.fields;
    845 			field; field = field->next) {
    846 		if (!field->name) {
    847 			r = autofill_struct(ctx, type_dealias(field->type), fields);
    848 			if (r != EVAL_OK) {
    849 				return r;
    850 			}
    851 			continue;
    852 		}
    853 		size_t i = 0;
    854 		bool skip = false;
    855 		for (; fields[i]; ++i) {
    856 			if (!strcmp(field->name, fields[i]->field->name)) {
    857 				skip = true;
    858 				break;
    859 			}
    860 		}
    861 		if (!skip) {
    862 			fields[i] = xcalloc(1, sizeof(struct struct_constant));
    863 			fields[i]->field = field;
    864 			fields[i]->value = xcalloc(1, sizeof(struct expression));
    865 			fields[i]->value->type = EXPR_CONSTANT;
    866 			fields[i]->value->result = field->type;
    867 			// TODO: there should probably be a better error message
    868 			// when this happens
    869 			r = constant_default(ctx, fields[i]->value);
    870 			if (r != EVAL_OK) {
    871 				return r;
    872 			}
    873 		}
    874 	}
    875 
    876 	return EVAL_OK;
    877 }
    878 
    879 static enum eval_result
    880 eval_struct(struct context *ctx, struct expression *in, struct expression *out)
    881 {
    882 	assert(in->type == EXPR_STRUCT);
    883 	assert(type_dealias(in->result)->storage != STORAGE_UNION); // TODO
    884 	const struct type *type = type_dealias(in->result);
    885 
    886 	size_t n = count_struct_fields(type);
    887 	assert(n > 0);
    888 
    889 	size_t i = 0;
    890 	struct struct_constant **fields =
    891 		xcalloc(n, sizeof(struct struct_constant *));
    892 	for (const struct expr_struct_field *field_in = in->_struct.fields;
    893 			field_in; field_in = field_in->next, ++i) {
    894 		const struct struct_field *field =
    895 			type_get_field(type, field_in->field->name);
    896 		fields[i] = xcalloc(1, sizeof(struct struct_constant));
    897 		fields[i]->field = field;
    898 		fields[i]->value = xcalloc(1, sizeof(struct expression));
    899 
    900 		enum eval_result r = eval_expr(ctx,
    901 			field_in->value, fields[i]->value);
    902 		if (r != EVAL_OK) {
    903 			return r;
    904 		}
    905 	}
    906 	assert(in->_struct.autofill || i == n);
    907 
    908 	if (in->_struct.autofill) {
    909 		enum eval_result r = autofill_struct(ctx, type, fields);
    910 		if (r != EVAL_OK) {
    911 			return r;
    912 		}
    913 	}
    914 
    915 	qsort(fields, n, sizeof(struct struct_constant *), field_compar);
    916 
    917 	for (size_t i = 0; i < n - 1; ++i) {
    918 		fields[i]->next = fields[i + 1];
    919 	}
    920 
    921 	out->constant._struct = fields[0];
    922 	free(fields);
    923 	return EVAL_OK;
    924 }
    925 
    926 static enum eval_result
    927 eval_tuple(struct context *ctx, struct expression *in, struct expression *out)
    928 {
    929 	assert(in->type == EXPR_TUPLE);
    930 	const struct type *type = type_dealias(in->result);
    931 
    932 	struct tuple_constant *out_tuple_start, *out_tuple;
    933 	out_tuple_start = out_tuple = xcalloc(1, sizeof(struct tuple_constant));
    934 	const struct expression_tuple *in_tuple = &in->tuple;
    935 	for (const struct type_tuple *field_type = &type->tuple; field_type;
    936 			field_type = field_type->next) {
    937 		out_tuple->value = xcalloc(1, sizeof(struct expression));
    938 		enum eval_result r =
    939 			eval_expr(ctx, in_tuple->value, out_tuple->value);
    940 		if (r != EVAL_OK) {
    941 			return r;
    942 		}
    943 		out_tuple->field = field_type;
    944 		if (in_tuple->next) {
    945 			in_tuple = in_tuple->next;
    946 			out_tuple->next =
    947 				xcalloc(1, sizeof(struct tuple_constant));
    948 			out_tuple = out_tuple->next;
    949 		}
    950 	}
    951 
    952 	out->constant.tuple = out_tuple_start;
    953 	return EVAL_OK;
    954 }
    955 
    956 
    957 static enum eval_result
    958 eval_unarithm(struct context *ctx, struct expression *in, struct expression *out)
    959 {
    960 	if (in->unarithm.op == UN_ADDRESS) {
    961 		if (in->unarithm.operand->result == &builtin_type_error) {
    962 			out->type = EXPR_CONSTANT;
    963 			out->result = &builtin_type_error;
    964 			out->constant.uval = 0;
    965 			return EVAL_OK;
    966 		}
    967 		if (in->unarithm.operand->type != EXPR_ACCESS) {
    968 			return EVAL_INVALID;
    969 		};
    970 		// TODO other access types
    971 		assert(in->unarithm.operand->access.type == ACCESS_IDENTIFIER);
    972 		if (in->unarithm.operand->access.object->otype != O_DECL) {
    973 			return EVAL_INVALID;
    974 		}
    975 		out->constant.object = in->unarithm.operand->access.object;
    976 		out->constant.ival = 0;
    977 		return EVAL_OK;
    978 	}
    979 
    980 	struct expression lvalue = {0};
    981 	enum eval_result r = eval_expr(ctx, in->unarithm.operand, &lvalue);
    982 	if (r != EVAL_OK) {
    983 		return r;
    984 	}
    985 
    986 	switch (in->unarithm.op) {
    987 	case UN_ADDRESS:
    988 		assert(0); // handled above
    989 	case UN_BNOT:
    990 		out->constant.uval = ~lvalue.constant.uval;
    991 		break;
    992 	case UN_DEREF:
    993 		return EVAL_INVALID;
    994 	case UN_LNOT:
    995 		out->constant.bval = !lvalue.constant.bval;
    996 		break;
    997 	case UN_MINUS:
    998 		if (type_is_float(out->result)) {
    999 			out->constant.fval = -lvalue.constant.fval;
   1000 		} else {
   1001 			out->constant.ival = -(uintmax_t)lvalue.constant.ival;
   1002 		}
   1003 		break;
   1004 	case UN_PLUS:
   1005 		out->constant = lvalue.constant;
   1006 		break;
   1007 	}
   1008 
   1009 	return EVAL_OK;
   1010 }
   1011 
   1012 enum eval_result
   1013 eval_expr(struct context *ctx, struct expression *in, struct expression *out)
   1014 {
   1015 	out->result = in->result;
   1016 	out->type = EXPR_CONSTANT;
   1017 
   1018 	switch (in->type) {
   1019 	case EXPR_ACCESS:
   1020 		return eval_access(ctx, in, out);
   1021 	case EXPR_BINARITHM:
   1022 		return eval_binarithm(ctx, in, out);
   1023 	case EXPR_CAST:
   1024 		switch (in->cast.kind) {
   1025 		case C_CAST:
   1026 			return eval_cast(ctx, in, out);
   1027 		case C_ASSERTION:
   1028 			return eval_type_assertion(ctx, in, out);
   1029 		case C_TEST:
   1030 			return eval_type_test(ctx, in, out);
   1031 		default:
   1032 			assert(0); // Unreacheable
   1033 		}
   1034 	case EXPR_CONSTANT:
   1035 		return eval_const(ctx, in, out);
   1036 	case EXPR_MEASURE:
   1037 		return eval_measurement(ctx, in, out);
   1038 	case EXPR_STRUCT:
   1039 		return eval_struct(ctx, in, out);
   1040 	case EXPR_SLICE:
   1041 		assert(0); // TODO
   1042 	case EXPR_TUPLE:
   1043 		return eval_tuple(ctx, in, out);
   1044 	case EXPR_UNARITHM:
   1045 		return eval_unarithm(ctx, in, out);
   1046 	case EXPR_ALLOC:
   1047 	case EXPR_APPEND:
   1048 	case EXPR_ASSERT:
   1049 	case EXPR_ASSIGN:
   1050 	case EXPR_BINDING:
   1051 	case EXPR_BREAK:
   1052 	case EXPR_CALL:
   1053 	case EXPR_COMPOUND:
   1054 	case EXPR_CONTINUE:
   1055 	case EXPR_DEFER:
   1056 	case EXPR_DELETE:
   1057 	case EXPR_FOR:
   1058 	case EXPR_FREE:
   1059 	case EXPR_IF:
   1060 	case EXPR_INSERT:
   1061 	case EXPR_MATCH:
   1062 	case EXPR_PROPAGATE:
   1063 	case EXPR_RETURN:
   1064 	case EXPR_SWITCH:
   1065 	case EXPR_VAARG:
   1066 	case EXPR_VAEND:
   1067 	case EXPR_VASTART:
   1068 	case EXPR_YIELD:
   1069 		return EVAL_INVALID;
   1070 	}
   1071 	assert(0); // Unreachable
   1072 }