harec

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

types.c (28419B)


      1 #include <assert.h>
      2 #include <stdbool.h>
      3 #include <stdio.h>
      4 #include <string.h>
      5 #include "expr.h"
      6 #include "scope.h"
      7 #include "types.h"
      8 #include "util.h"
      9 
     10 const struct type *
     11 type_dereference(const struct type *type)
     12 {
     13 	switch (type->storage) {
     14 	case STORAGE_ALIAS:
     15 		if (type_dealias(type)->storage != STORAGE_POINTER) {
     16 			return type;
     17 		}
     18 		return type_dereference(type_dealias(type));
     19 	case STORAGE_POINTER:
     20 		if (type->pointer.flags & PTR_NULLABLE) {
     21 			return NULL;
     22 		}
     23 		return type_dereference(type->pointer.referent);
     24 	default:
     25 		return type;
     26 	}
     27 }
     28 
     29 const struct type *
     30 type_dealias(const struct type *type)
     31 {
     32 	while (type->storage == STORAGE_ALIAS) {
     33 		if (type->alias.type == NULL) {
     34 			fprintf(stderr, "Cannot dealias incomplete type %s\n",
     35 				identifier_unparse(&type->alias.ident));
     36 			assert(0);
     37 		}
     38 		type = type->alias.type;
     39 	}
     40 	return type;
     41 }
     42 
     43 const struct struct_field *
     44 type_get_field(const struct type *type, const char *name)
     45 {
     46 	// TODO: We should consider lowering unions into structs with explicit
     47 	// offsets
     48 	assert(type->storage == STORAGE_STRUCT
     49 			|| type->storage == STORAGE_UNION);
     50 	struct struct_field *field = type->struct_union.fields;
     51 	while (field) {
     52 		if (field->name) {
     53 			if (strcmp(field->name, name) == 0) {
     54 				return field;
     55 			}
     56 		} else {
     57 			const struct struct_field *f =
     58 				type_get_field(type_dealias(field->type), name);
     59 			if (f != NULL) {
     60 				return f;
     61 			}
     62 		}
     63 		field = field->next;
     64 	}
     65 	return NULL;
     66 }
     67 
     68 const struct type_tuple *
     69 type_get_value(const struct type *type, uintmax_t index)
     70 {
     71 	assert(type->storage == STORAGE_TUPLE);
     72 	const struct type_tuple *tuple = &type->tuple;
     73 	while (tuple) {
     74 		if (index == 0) {
     75 			return tuple;
     76 		}
     77 		tuple = tuple->next;
     78 		--index;
     79 	}
     80 	return NULL;
     81 }
     82 
     83 // Returns true if this type is or contains an error type
     84 bool
     85 type_has_error(const struct type *type)
     86 {
     87 	if (type->flags & TYPE_ERROR) {
     88 		return true;
     89 	}
     90 	type = type_dealias(type);
     91 	if (type->storage != STORAGE_TAGGED) {
     92 		return false;
     93 	}
     94 	const struct type_tagged_union *tu = &type->tagged;
     95 	for (; tu; tu = tu->next) {
     96 		if (tu->type->flags & TYPE_ERROR) {
     97 			return true;
     98 		}
     99 	}
    100 	return false;
    101 }
    102 
    103 const char *
    104 type_storage_unparse(enum type_storage storage)
    105 {
    106 	switch (storage) {
    107 	case STORAGE_ALIAS:
    108 		return "alias";
    109 	case STORAGE_ARRAY:
    110 		return "array";
    111 	case STORAGE_BOOL:
    112 		return "bool";
    113 	case STORAGE_CHAR:
    114 		return "char";
    115 	case STORAGE_ENUM:
    116 		return "enum";
    117 	case STORAGE_F32:
    118 		return "f32";
    119 	case STORAGE_F64:
    120 		return "f64";
    121 	case STORAGE_FCONST:
    122 		return "fconst";
    123 	case STORAGE_FUNCTION:
    124 		return "function";
    125 	case STORAGE_I16:
    126 		return "i16";
    127 	case STORAGE_I32:
    128 		return "i32";
    129 	case STORAGE_I64:
    130 		return "i64";
    131 	case STORAGE_I8:
    132 		return "i8";
    133 	case STORAGE_ICONST:
    134 		return "iconst";
    135 	case STORAGE_INT:
    136 		return "int";
    137 	case STORAGE_POINTER:
    138 		return "pointer";
    139 	case STORAGE_NULL:
    140 		return "null";
    141 	case STORAGE_RCONST:
    142 		return "rconst";
    143 	case STORAGE_RUNE:
    144 		return "rune";
    145 	case STORAGE_SIZE:
    146 		return "size";
    147 	case STORAGE_SLICE:
    148 		return "slice";
    149 	case STORAGE_STRING:
    150 		return "str";
    151 	case STORAGE_STRUCT:
    152 		return "struct";
    153 	case STORAGE_TAGGED:
    154 		return "tagged union";
    155 	case STORAGE_TUPLE:
    156 		return "tuple";
    157 	case STORAGE_U16:
    158 		return "u16";
    159 	case STORAGE_U32:
    160 		return "u32";
    161 	case STORAGE_U64:
    162 		return "u64";
    163 	case STORAGE_U8:
    164 		return "u8";
    165 	case STORAGE_UINT:
    166 		return "uint";
    167 	case STORAGE_UINTPTR:
    168 		return "uintptr";
    169 	case STORAGE_UNION:
    170 		return "union";
    171 	case STORAGE_VALIST:
    172 		return "valist";
    173 	case STORAGE_VOID:
    174 		return "void";
    175 	}
    176 	assert(0);
    177 }
    178 
    179 bool
    180 type_is_integer(const struct type *type)
    181 {
    182 	switch (type->storage) {
    183 	case STORAGE_VOID:
    184 	case STORAGE_ARRAY:
    185 	case STORAGE_FUNCTION:
    186 	case STORAGE_POINTER:
    187 	case STORAGE_SLICE:
    188 	case STORAGE_STRING:
    189 	case STORAGE_STRUCT:
    190 	case STORAGE_TAGGED:
    191 	case STORAGE_TUPLE:
    192 	case STORAGE_UNION:
    193 	case STORAGE_BOOL:
    194 	case STORAGE_NULL:
    195 	case STORAGE_RCONST:
    196 	case STORAGE_RUNE:
    197 	case STORAGE_F32:
    198 	case STORAGE_F64:
    199 	case STORAGE_FCONST:
    200 	case STORAGE_VALIST:
    201 		return false;
    202 	case STORAGE_CHAR:
    203 	case STORAGE_ENUM:
    204 	case STORAGE_I8:
    205 	case STORAGE_I16:
    206 	case STORAGE_I32:
    207 	case STORAGE_I64:
    208 	case STORAGE_ICONST:
    209 	case STORAGE_INT:
    210 	case STORAGE_SIZE:
    211 	case STORAGE_U8:
    212 	case STORAGE_U16:
    213 	case STORAGE_U32:
    214 	case STORAGE_U64:
    215 	case STORAGE_UINT:
    216 	case STORAGE_UINTPTR:
    217 		return true;
    218 	case STORAGE_ALIAS:
    219 		return type_is_integer(type_dealias(type));
    220 	}
    221 	assert(0); // Unreachable
    222 }
    223 
    224 bool
    225 type_is_numeric(const struct type *type)
    226 {
    227 	switch (type->storage) {
    228 	case STORAGE_VOID:
    229 	case STORAGE_ARRAY:
    230 	case STORAGE_FUNCTION:
    231 	case STORAGE_POINTER:
    232 	case STORAGE_SLICE:
    233 	case STORAGE_STRING:
    234 	case STORAGE_STRUCT:
    235 	case STORAGE_TAGGED:
    236 	case STORAGE_TUPLE:
    237 	case STORAGE_UNION:
    238 	case STORAGE_BOOL:
    239 	case STORAGE_CHAR:
    240 	case STORAGE_RCONST:
    241 	case STORAGE_RUNE:
    242 	case STORAGE_NULL:
    243 	case STORAGE_VALIST:
    244 		return false;
    245 	case STORAGE_ENUM:
    246 	case STORAGE_I8:
    247 	case STORAGE_I16:
    248 	case STORAGE_I32:
    249 	case STORAGE_I64:
    250 	case STORAGE_ICONST:
    251 	case STORAGE_INT:
    252 	case STORAGE_F32:
    253 	case STORAGE_F64:
    254 	case STORAGE_FCONST:
    255 	case STORAGE_SIZE:
    256 	case STORAGE_U8:
    257 	case STORAGE_U16:
    258 	case STORAGE_U32:
    259 	case STORAGE_U64:
    260 	case STORAGE_UINT:
    261 	case STORAGE_UINTPTR:
    262 		return true;
    263 	case STORAGE_ALIAS:
    264 		return type_is_numeric(type_dealias(type));
    265 	}
    266 	assert(0); // Unreachable
    267 }
    268 
    269 bool
    270 type_is_float(const struct type *type)
    271 {
    272 	type = type_dealias(type);
    273 	return type->storage == STORAGE_F32 || type->storage == STORAGE_F64
    274 		|| type->storage == STORAGE_FCONST;
    275 }
    276 
    277 bool
    278 type_is_signed(const struct type *type)
    279 {
    280 	enum type_storage storage = type_dealias(type)->storage;
    281 	if (storage == STORAGE_ENUM) {
    282 		storage = type_dealias(type)->alias.type->storage;
    283 	}
    284 	switch (storage) {
    285 	case STORAGE_VOID:
    286 	case STORAGE_ARRAY:
    287 	case STORAGE_ENUM:
    288 	case STORAGE_FUNCTION:
    289 	case STORAGE_POINTER:
    290 	case STORAGE_SLICE:
    291 	case STORAGE_STRING:
    292 	case STORAGE_STRUCT:
    293 	case STORAGE_TAGGED:
    294 	case STORAGE_TUPLE:
    295 	case STORAGE_UNION:
    296 	case STORAGE_BOOL:
    297 	case STORAGE_CHAR:
    298 	case STORAGE_RCONST:
    299 	case STORAGE_RUNE:
    300 	case STORAGE_NULL:
    301 	case STORAGE_SIZE:
    302 	case STORAGE_U8:
    303 	case STORAGE_U16:
    304 	case STORAGE_U32:
    305 	case STORAGE_U64:
    306 	case STORAGE_UINT:
    307 	case STORAGE_UINTPTR:
    308 	case STORAGE_VALIST:
    309 		return false;
    310 	case STORAGE_I8:
    311 	case STORAGE_I16:
    312 	case STORAGE_I32:
    313 	case STORAGE_I64:
    314 	case STORAGE_INT:
    315 	case STORAGE_F32:
    316 	case STORAGE_F64:
    317 	case STORAGE_FCONST:
    318 		return true;
    319 	case STORAGE_ICONST:
    320 		return type->_const.min < 0;
    321 	case STORAGE_ALIAS:
    322 		assert(0); // Handled above
    323 	}
    324 	assert(0); // Unreachable
    325 }
    326 
    327 bool
    328 type_is_constant(const struct type *type)
    329 {
    330 	return type->storage == STORAGE_FCONST
    331 		|| type->storage == STORAGE_ICONST
    332 		|| type->storage == STORAGE_RCONST;
    333 }
    334 
    335 uint32_t
    336 type_hash(const struct type *type)
    337 {
    338 	// XXX: ARCH
    339 	uint32_t hash = FNV1A_INIT;
    340 	hash = fnv1a(hash, type->storage);
    341 	hash = fnv1a(hash, type->flags);
    342 	switch (type->storage) {
    343 	case STORAGE_BOOL:
    344 	case STORAGE_CHAR:
    345 	case STORAGE_F32:
    346 	case STORAGE_F64:
    347 	case STORAGE_I8:
    348 	case STORAGE_I16:
    349 	case STORAGE_I32:
    350 	case STORAGE_I64:
    351 	case STORAGE_INT:
    352 	case STORAGE_NULL:
    353 	case STORAGE_RUNE:
    354 	case STORAGE_SIZE:
    355 	case STORAGE_U8:
    356 	case STORAGE_U16:
    357 	case STORAGE_U32:
    358 	case STORAGE_U64:
    359 	case STORAGE_UINT:
    360 	case STORAGE_UINTPTR:
    361 	case STORAGE_VALIST:
    362 	case STORAGE_VOID:
    363 	case STORAGE_STRING:
    364 		break; // built-ins
    365 	case STORAGE_ENUM:
    366 		hash = fnv1a(hash, type->alias.type->storage);
    367 		/* fallthrough */
    368 	case STORAGE_ALIAS:
    369 		for (const struct identifier *ident = &type->alias.ident; ident;
    370 				ident = ident->ns) {
    371 			hash = fnv1a_s(hash, ident->name);
    372 			hash = fnv1a(hash, 0);
    373 		}
    374 		break;
    375 	case STORAGE_ARRAY:
    376 		hash = fnv1a_u32(hash, type_hash(type->array.members));
    377 		hash = fnv1a_size(hash, type->array.length);
    378 		hash = fnv1a_u32(hash, type->array.expandable);
    379 		break;
    380 	case STORAGE_FUNCTION:
    381 		hash = fnv1a_u32(hash, type_hash(type->func.result));
    382 		hash = fnv1a(hash, type->func.variadism);
    383 		hash = fnv1a(hash, type->func.flags);
    384 		for (struct type_func_param *param = type->func.params;
    385 				param; param = param->next) {
    386 			hash = fnv1a_u32(hash, type_hash(param->type));
    387 		}
    388 		break;
    389 	case STORAGE_FCONST:
    390 	case STORAGE_ICONST:
    391 	case STORAGE_RCONST:
    392 		hash = fnv1a(hash, type->_const.id);
    393 		break;
    394 	case STORAGE_POINTER:
    395 		hash = fnv1a(hash, type->pointer.flags);
    396 		hash = fnv1a_u32(hash, type_hash(type->pointer.referent));
    397 		break;
    398 	case STORAGE_SLICE:
    399 		hash = fnv1a_u32(hash, type_hash(type->array.members));
    400 		break;
    401 	case STORAGE_STRUCT:
    402 	case STORAGE_UNION:
    403 		for (const struct struct_field *field = type->struct_union.fields;
    404 				field; field = field->next) {
    405 			if (field->name) {
    406 				hash = fnv1a_s(hash, field->name);
    407 			}
    408 			hash = fnv1a_u32(hash, type_hash(field->type));
    409 			hash = fnv1a_size(hash, field->offset);
    410 		}
    411 		break;
    412 	case STORAGE_TAGGED:
    413 		// Invariant: subtypes must be sorted by ID and must not include
    414 		// any other tagged union types, nor any duplicates.
    415 		for (const struct type_tagged_union *tu = &type->tagged;
    416 				tu; tu = tu->next) {
    417 			hash = fnv1a_u32(hash, type_hash(tu->type));
    418 		}
    419 		break;
    420 	case STORAGE_TUPLE:
    421 		for (const struct type_tuple *tuple = &type->tuple;
    422 				tuple; tuple = tuple->next) {
    423 			hash = fnv1a_u32(hash, type_hash(tuple->type));
    424 		}
    425 		break;
    426 	}
    427 	return hash;
    428 }
    429 
    430 // Note that the type this returns is NOT a type singleton and cannot be treated
    431 // as such.
    432 static const struct type *
    433 strip_flags(const struct type *t, struct type *secondary)
    434 {
    435 	if (!t->flags) {
    436 		return t;
    437 	}
    438 	*secondary = *t;
    439 	secondary->flags = 0;
    440 	secondary->id = type_hash(secondary);
    441 	return secondary;
    442 }
    443 
    444 const struct type *
    445 tagged_select_subtype(const struct type *tagged, const struct type *subtype)
    446 {
    447 	tagged = type_dealias(tagged);
    448 	assert(tagged->storage == STORAGE_TAGGED);
    449 
    450 	struct type _stripped;
    451 	const struct type *stripped = strip_flags(subtype, &_stripped);
    452 
    453 	size_t nassign = 0;
    454 	const struct type *selected = NULL;
    455 	for (const struct type_tagged_union *tu = &tagged->tagged;
    456 			tu; tu = tu->next) {
    457 		struct type _tustripped;
    458 		const struct type *tustripped =
    459 			strip_flags(tu->type, &_tustripped);
    460 		// XXX: Kind of stupid
    461 		if (tu->type->id == subtype->id
    462 				|| tu->type->id == stripped->id
    463 				|| tustripped->id == subtype->id
    464 				|| tustripped->id == stripped->id) {
    465 			return tu->type;
    466 		}
    467 
    468 		if (type_dealias(tu->type)->storage == STORAGE_VOID) {
    469 			continue;
    470 		}
    471 		if (type_is_assignable(tu->type, subtype)) {
    472 			selected = tu->type;
    473 			++nassign;
    474 		}
    475 	}
    476 
    477 	if (nassign == 1) {
    478 		return selected;
    479 	}
    480 
    481 	return NULL;
    482 }
    483 
    484 static intmax_t
    485 min_value(const struct type *t)
    486 {
    487 	assert(type_is_integer(t));
    488 	if (!type_is_signed(t)) {
    489 		return 0;
    490 	}
    491 	if (t->size == sizeof(intmax_t)) {
    492 		return INTMAX_MIN;
    493 	}
    494 	return -(1 << (t->size * 8 - 1));
    495 }
    496 
    497 static uintmax_t
    498 max_value(const struct type *t)
    499 {
    500 	assert(type_is_integer(t));
    501 	size_t bits = t->size * 8;
    502 	if (type_is_signed(t)) {
    503 		bits--;
    504 	}
    505 	if (bits == sizeof(uintmax_t) * 8) {
    506 		return UINTMAX_MAX;
    507 	}
    508 	return ((uintmax_t)1 << bits) - 1;
    509 }
    510 
    511 const struct type *
    512 type_create_const(enum type_storage storage, intmax_t min, intmax_t max)
    513 {
    514 	// XXX: This'll be impossible to free. The right solution would be to
    515 	// store iconsts in the type store, but that'd require passing the store
    516 	// into type_is_assignable et al. An easier solution would be to keep
    517 	// our own list of iconsts and free them separately. Whatever, it
    518 	// doesn't really matter that much.
    519 	static uint32_t id = 0;
    520 	struct type *type = xcalloc(sizeof(struct type), 1);
    521 	type->storage = storage;
    522 	type->size = SIZE_UNDEFINED;
    523 	type->align = ALIGN_UNDEFINED;
    524 	type->_const.min = min;
    525 	type->_const.max = max;
    526 	type->_const.id = id++;
    527 	type->id = type_hash(type);
    528 	assert(type_is_constant(type));
    529 	return type;
    530 }
    531 
    532 // Register a reference to a flexible constant type. When `type` is lowered in
    533 // [[lower_const]], *ref will be updated to point to the new type.
    534 void
    535 const_refer(const struct type *type, const struct type **ref)
    536 {
    537 	if (type == NULL || !type_is_constant(type)) {
    538 		return;
    539 	}
    540 	struct type_const *constant = (struct type_const *)&type->_const;
    541 
    542 	if (constant->nrefs >= constant->zrefs) {
    543 		constant->zrefs *= 2;
    544 		if (constant->zrefs == 0) {
    545 			constant->zrefs++;
    546 		}
    547 		constant->refs = xrealloc(constant->refs,
    548 			constant->zrefs * sizeof(const struct type **));
    549 	}
    550 	constant->refs[constant->nrefs] = ref;
    551 	constant->nrefs++;
    552 }
    553 
    554 // Lower a flexible constant type. If new == NULL, lower it to its default type.
    555 const struct type *
    556 lower_const(const struct type *old, const struct type *new) {
    557 	if (!type_is_constant(old)) {
    558 		// If new != NULL, we're expected to always do something, and we
    559 		// can't if it's not a constant
    560 		assert(new == NULL);
    561 		return old;
    562 	}
    563 	if (new == NULL) {
    564 		switch (old->storage) {
    565 		case STORAGE_FCONST:
    566 			new = &builtin_type_f64;
    567 			break;
    568 		case STORAGE_ICONST:
    569 			if (old->_const.max <= (intmax_t)max_value(&builtin_type_int)
    570 					&& old->_const.min >= min_value(&builtin_type_int)) {
    571 				new = &builtin_type_int;
    572 			} else {
    573 				new = &builtin_type_i64;
    574 			}
    575 			break;
    576 		case STORAGE_RCONST:
    577 			new = &builtin_type_rune;
    578 			break;
    579 		default:
    580 			assert(0);
    581 		}
    582 	}
    583 	for (size_t i = 0; i < old->_const.nrefs; i++) {
    584 		const_refer(new, old->_const.refs[i]);
    585 		*old->_const.refs[i] = new;
    586 	}
    587 	// XXX: Can we free old?
    588 	return new;
    589 }
    590 
    591 // Implements the flexible constant promotion algorithm
    592 const struct type *
    593 promote_const(const struct type *a, const struct type *b) {
    594 	if (a->storage == STORAGE_ICONST && b->storage == STORAGE_ICONST) {
    595 		intmax_t min = a->_const.min < b->_const.min
    596 			? a->_const.min : b->_const.min;
    597 		intmax_t max = a->_const.max > b->_const.max
    598 			? a->_const.max : b->_const.max;
    599 		const struct type *l =
    600 			type_create_const(STORAGE_ICONST, min, max);
    601 		lower_const(a, l);
    602 		lower_const(b, l);
    603 		return l;
    604 	}
    605 	if (type_is_constant(a)) {
    606 		if (a->storage == b->storage) {
    607 			const struct type *l =
    608 				type_create_const(a->storage, 0, 0);
    609 			lower_const(a, l);
    610 			lower_const(b, l);
    611 			return l;
    612 		}
    613 		if (type_is_constant(b)) {
    614 			return NULL;
    615 		}
    616 		return promote_const(b, a);
    617 	}
    618 	assert(!type_is_constant(a) && type_is_constant(b));
    619 	if (type_dealias(a)->storage == STORAGE_TAGGED) {
    620 		const struct type *tag = NULL;
    621 		for (const struct type_tagged_union *tu =
    622 				&type_dealias(a)->tagged; tu; tu = tu->next) {
    623 			const struct type *p = promote_const(tu->type, b);
    624 			if (!p) {
    625 				continue;
    626 			}
    627 			if (tag) {
    628 				// Ambiguous
    629 				b = lower_const(b, NULL);
    630 				if (type_is_assignable(a, b)) {
    631 					return b;
    632 				}
    633 				return NULL;
    634 			}
    635 			tag = p;
    636 		}
    637 		return tag;
    638 	}
    639 	switch (b->storage) {
    640 	case STORAGE_FCONST:
    641 		if (!type_is_float(a)) {
    642 			return NULL;
    643 		}
    644 		lower_const(b, a);
    645 		return a;
    646 	case STORAGE_ICONST:
    647 		if (!type_is_integer(a)) {
    648 			return NULL;
    649 		}
    650 		if (type_is_signed(a) && min_value(a) > b->_const.min) {
    651 			return NULL;
    652 		}
    653 		if (b->_const.max > 0 && max_value(a) < (uintmax_t)b->_const.max) {
    654 			return NULL;
    655 		}
    656 		lower_const(b, a);
    657 		return a;
    658 	case STORAGE_RCONST:
    659 		if (type_dealias(a)->storage == STORAGE_RUNE) {
    660 			lower_const(b, a);
    661 			return a;
    662 		}
    663 		// XXX: This is probably a bit too lenient but I can't think of
    664 		// a better way to do this
    665 		if (!type_is_integer(a)) {
    666 			return NULL;
    667 		}
    668 		lower_const(b, a);
    669 		return a;
    670 	default:
    671 		assert(0); // Invariant
    672 	}
    673 }
    674 
    675 bool
    676 tagged_subset_compat(const struct type *superset, const struct type *subset)
    677 {
    678 	// Note: this implementation depends on the invariant that tagged union
    679 	// member types are sorted by their type ID.
    680 	superset = type_dealias(superset), subset = type_dealias(subset);
    681 	if (superset->storage != STORAGE_TAGGED || subset->storage != STORAGE_TAGGED) {
    682 		return false;
    683 	}
    684 	const struct type_tagged_union *superset_tu = &superset->tagged,
    685 		*subset_tu = &subset->tagged;
    686 	while (subset_tu && superset_tu) {
    687 		while (superset_tu) {
    688 			if (superset_tu->type->id == subset_tu->type->id) {
    689 				subset_tu = subset_tu->next;
    690 				superset_tu = superset_tu->next;
    691 				break;
    692 			}
    693 			superset_tu = superset_tu->next;
    694 		}
    695 	}
    696 
    697 	return !subset_tu;
    698 }
    699 
    700 static bool
    701 struct_subtype(const struct type *to, const struct type *from) {
    702 	if (from->storage != STORAGE_STRUCT) {
    703 		return false;
    704 	}
    705 	for (struct struct_field *f = from->struct_union.fields; f;
    706 			f = f->next) {
    707 		if (f->offset == 0) {
    708 			return f->type == to
    709 				|| struct_subtype(to, type_dealias(f->type));
    710 		}
    711 	}
    712 	return false;
    713 }
    714 
    715 bool
    716 type_is_assignable(const struct type *to, const struct type *from)
    717 {
    718 	const struct type *to_orig = to, *from_orig = from;
    719 	if (type_dealias(to)->storage != STORAGE_TAGGED) {
    720 		to = type_dealias(to);
    721 		from = type_dealias(from);
    722 	}
    723 
    724 	// const and non-const types are mutually assignable
    725 	struct type _to, _from;
    726 	to = strip_flags(to, &_to), from = strip_flags(from, &_from);
    727 	if (to->id == from->id && to->storage != STORAGE_VOID) {
    728 		return true;
    729 	}
    730 
    731 	if (type_is_constant(from)) {
    732 		return promote_const(to_orig, from_orig);
    733 	}
    734 
    735 	struct type _to_secondary, _from_secondary;
    736 	const struct type *to_secondary, *from_secondary;
    737 	switch (to->storage) {
    738 	case STORAGE_FCONST:
    739 	case STORAGE_ICONST:
    740 	case STORAGE_RCONST:
    741 		return promote_const(to_orig, from_orig);
    742 	case STORAGE_I8:
    743 	case STORAGE_I16:
    744 	case STORAGE_I32:
    745 	case STORAGE_I64:
    746 	case STORAGE_INT:
    747 		return type_is_integer(from)
    748 			&& type_is_signed(from)
    749 			&& to->size >= from->size;
    750 	case STORAGE_SIZE:
    751 	case STORAGE_U8:
    752 	case STORAGE_U16:
    753 	case STORAGE_U32:
    754 	case STORAGE_U64:
    755 	case STORAGE_UINT:
    756 		return type_is_integer(from)
    757 			&& !type_is_signed(from)
    758 			&& to->size >= from->size;
    759 	case STORAGE_F32:
    760 	case STORAGE_F64:
    761 		return type_is_float(from);
    762 	case STORAGE_POINTER:
    763 		to_secondary = type_dealias(to->pointer.referent);
    764 		to_secondary = strip_flags(to_secondary, &_to_secondary);
    765 		switch (from->storage) {
    766 		case STORAGE_UINTPTR:
    767 			return true;
    768 		case STORAGE_NULL:
    769 			return to->pointer.flags & PTR_NULLABLE;
    770 		case STORAGE_POINTER:
    771 			from_secondary = type_dealias(from->pointer.referent);
    772 			from_secondary = strip_flags(from_secondary, &_from_secondary);
    773 			if (struct_subtype(to->pointer.referent, from_secondary)) {
    774 				return true;
    775 			}
    776 			switch (to_secondary->storage) {
    777 			case STORAGE_VOID:
    778 				break;
    779 			case STORAGE_ARRAY:
    780 				if (!type_is_assignable(to_secondary, from_secondary)) {
    781 					return false;
    782 				}
    783 				break;
    784 			default:
    785 				if (to_secondary->id != from_secondary->id) {
    786 					return false;
    787 				}
    788 				break;
    789 			}
    790 			if (from->pointer.flags & PTR_NULLABLE) {
    791 				return to->pointer.flags & PTR_NULLABLE;
    792 			}
    793 			return true;
    794 		case STORAGE_STRING:
    795 			return to->pointer.referent->storage == STORAGE_CHAR
    796 				&& to->pointer.referent->flags & TYPE_CONST;
    797 		default:
    798 			return false;
    799 		}
    800 		assert(0); // Unreachable
    801 	case STORAGE_ALIAS:
    802 		assert(to->alias.type);
    803 		return type_is_assignable(to->alias.type, from);
    804 	case STORAGE_STRING:
    805 		return to->id == builtin_type_ptr_const_char.id;
    806 	case STORAGE_VOID:
    807 		return to_orig->id == from_orig->id &&
    808 			(from_orig->flags & TYPE_ERROR)	== (to_orig->flags & TYPE_ERROR);
    809 	case STORAGE_SLICE:
    810 		if (from->storage == STORAGE_POINTER) {
    811 			from = type_dealias(from->pointer.referent);
    812 			if (from->storage != STORAGE_ARRAY) {
    813 				return false;
    814 			}
    815 		}
    816 		if (from->storage != STORAGE_ARRAY
    817 				&& from->storage != STORAGE_SLICE) {
    818 			return false;
    819 		}
    820 		to_secondary = strip_flags(
    821 			type_dealias(to->array.members),
    822 			&_to_secondary);
    823 		from_secondary = strip_flags(
    824 			type_dealias(from->array.members),
    825 			&_from_secondary);
    826 		if (to->storage == STORAGE_SLICE
    827 				&& to_secondary->storage == STORAGE_VOID) {
    828 			return true;
    829 		}
    830 		return to_secondary->id == from_secondary->id;
    831 	case STORAGE_ARRAY:
    832 		if (from->storage != STORAGE_ARRAY) {
    833 			return false;
    834 		}
    835 		if (from->array.expandable) {
    836 			return to->array.length != SIZE_UNDEFINED
    837 				&& to->array.length >= from->array.length
    838 				&& to->array.members == from->array.members;
    839 		} else {
    840 			return to->array.length == SIZE_UNDEFINED
    841 				&& from->array.length != SIZE_UNDEFINED
    842 				&& to->array.members == from->array.members;
    843 		}
    844 	case STORAGE_TAGGED:
    845 		return tagged_select_subtype(to, from_orig) != NULL
    846 			|| tagged_subset_compat(to, from);
    847 	// The following types are only assignable from themselves, and are
    848 	// handled above:
    849 	case STORAGE_BOOL:
    850 	case STORAGE_CHAR:
    851 	case STORAGE_ENUM:
    852 	case STORAGE_FUNCTION:
    853 	case STORAGE_NULL:
    854 	case STORAGE_RUNE:
    855 	case STORAGE_STRUCT:
    856 	case STORAGE_TUPLE:
    857 	case STORAGE_UINTPTR:
    858 	case STORAGE_UNION:
    859 	case STORAGE_VALIST:
    860 		return false;
    861 	}
    862 
    863 	assert(0); // Unreachable
    864 }
    865 
    866 static bool
    867 is_castable_with_tagged(const struct type *to, const struct type *from)
    868 {
    869 	if (type_dealias(from)->storage == STORAGE_TAGGED
    870 			&& type_dealias(to)->storage == STORAGE_TAGGED) {
    871 		if (tagged_subset_compat(to, from) || tagged_subset_compat(from, to)) {
    872 			return true;
    873 		}
    874 	}
    875 	if (type_dealias(to)->storage == STORAGE_TAGGED) {
    876 		if (tagged_select_subtype(to, from) != NULL) {
    877 			return true;
    878 		}
    879 	}
    880 	if (type_dealias(from)->storage == STORAGE_TAGGED) {
    881 		if (tagged_select_subtype(from, to) != NULL) {
    882 			return true;
    883 		}
    884 	}
    885 	return false;
    886 }
    887 
    888 bool
    889 type_is_castable(const struct type *to, const struct type *from)
    890 {
    891 	if (to->storage == STORAGE_VOID) {
    892 		return true;
    893 	}
    894 
    895 	if (type_dealias(from)->storage == STORAGE_TAGGED
    896 			|| type_dealias(to)->storage == STORAGE_TAGGED) {
    897 		return is_castable_with_tagged(to, from);
    898 	}
    899 
    900 	const struct type *to_orig = to, *from_orig = from;
    901 	to = type_dealias(to), from = type_dealias(from);
    902 	if (to == from) {
    903 		return true;
    904 	}
    905 
    906 	struct type _to, _from;
    907 	to = strip_flags(to, &_to), from = strip_flags(from, &_from);
    908 	if (to->id == from->id) {
    909 		return true;
    910 	}
    911 
    912 	switch (from->storage) {
    913 	case STORAGE_FCONST:
    914 	case STORAGE_ICONST:
    915 	case STORAGE_RCONST:
    916 		return promote_const(from_orig, to_orig);
    917 	case STORAGE_I8:
    918 	case STORAGE_I16:
    919 	case STORAGE_I32:
    920 	case STORAGE_I64:
    921 	case STORAGE_INT:
    922 	case STORAGE_SIZE:
    923 	case STORAGE_U16:
    924 	case STORAGE_U64:
    925 	case STORAGE_UINT:
    926 		return to->storage == STORAGE_ENUM || type_is_numeric(to);
    927 	case STORAGE_U8:
    928 		return to->storage == STORAGE_ENUM
    929 			|| type_is_numeric(to)
    930 			|| to->storage == STORAGE_CHAR;
    931 	case STORAGE_U32:
    932 		return to->storage == STORAGE_ENUM
    933 			|| type_is_numeric(to)
    934 			|| to->storage == STORAGE_RUNE;
    935 	case STORAGE_CHAR:
    936 		return to->storage == STORAGE_U8;
    937 	case STORAGE_RUNE:
    938 		return to->storage == STORAGE_U32;
    939 	case STORAGE_ENUM:
    940 		return to->storage == STORAGE_ENUM || type_is_integer(from);
    941 	case STORAGE_F32:
    942 	case STORAGE_F64:
    943 		return type_is_numeric(to);
    944 	case STORAGE_UINTPTR:
    945 		return to->storage == STORAGE_POINTER
    946 			|| to->storage == STORAGE_NULL
    947 			|| type_is_numeric(to)
    948 			|| to->storage == STORAGE_ENUM;
    949 	case STORAGE_POINTER:
    950 		return to->storage == STORAGE_POINTER
    951 			|| to->storage == STORAGE_NULL
    952 			|| to->storage == STORAGE_UINTPTR;
    953 	case STORAGE_NULL:
    954 		return to->storage == STORAGE_POINTER
    955 			|| to->storage == STORAGE_UINTPTR;
    956 	case STORAGE_SLICE:
    957 	case STORAGE_ARRAY:
    958 		return to->storage == STORAGE_SLICE
    959 			|| to->storage == STORAGE_ARRAY
    960 			|| (to->storage == STORAGE_POINTER
    961 					&& to->pointer.referent->storage == STORAGE_ARRAY
    962 					&& from->storage == STORAGE_SLICE);
    963 	// Cannot be cast:
    964 	case STORAGE_STRING:
    965 	case STORAGE_BOOL:
    966 	case STORAGE_VOID:
    967 	case STORAGE_FUNCTION:
    968 	case STORAGE_TUPLE:
    969 	case STORAGE_STRUCT:
    970 	case STORAGE_UNION:
    971 	case STORAGE_VALIST:
    972 		return false;
    973 	case STORAGE_TAGGED:
    974 	case STORAGE_ALIAS:
    975 		assert(0); // Handled above
    976 	}
    977 
    978 	assert(0); // Unreachable
    979 }
    980 
    981 void
    982 builtin_types_init()
    983 {
    984 	struct type *builtins[] = {
    985 		&builtin_type_bool, &builtin_type_char, &builtin_type_f32,
    986 		&builtin_type_f64, &builtin_type_i8, &builtin_type_i16,
    987 		&builtin_type_i32, &builtin_type_i64, &builtin_type_int,
    988 		&builtin_type_u8, &builtin_type_u16, &builtin_type_u32,
    989 		&builtin_type_u64, &builtin_type_uint, &builtin_type_uintptr,
    990 		&builtin_type_null, &builtin_type_rune, &builtin_type_size,
    991 		&builtin_type_void, &builtin_type_const_bool,
    992 		&builtin_type_const_char, &builtin_type_const_f32,
    993 		&builtin_type_const_f64, &builtin_type_const_i8,
    994 		&builtin_type_const_i16, &builtin_type_const_i32,
    995 		&builtin_type_const_i64, &builtin_type_const_int,
    996 		&builtin_type_const_u8, &builtin_type_const_u16,
    997 		&builtin_type_const_u32, &builtin_type_const_u64,
    998 		&builtin_type_const_uint, &builtin_type_const_uintptr,
    999 		&builtin_type_const_rune, &builtin_type_const_size,
   1000 		&builtin_type_const_void, &builtin_type_ptr_const_char,
   1001 		&builtin_type_str, &builtin_type_const_str,
   1002 		&builtin_type_valist,
   1003 	};
   1004 	for (size_t i = 0; i < sizeof(builtins) / sizeof(builtins[0]); ++i) {
   1005 		builtins[i]->id = type_hash(builtins[i]);
   1006 	}
   1007 }
   1008 
   1009 // Built-in type singletons
   1010 struct type builtin_type_bool = {
   1011 	.storage = STORAGE_BOOL,
   1012 	.size = 4, // XXX: ARCH
   1013 	.align = 4,
   1014 },
   1015 builtin_type_char = {
   1016 	.storage = STORAGE_CHAR,
   1017 	.size = 1,
   1018 	.align = 1,
   1019 },
   1020 builtin_type_f32 = {
   1021 	.storage = STORAGE_F32,
   1022 	.size = 4,
   1023 	.align = 4,
   1024 },
   1025 builtin_type_f64 = {
   1026 	.storage = STORAGE_F64,
   1027 	.size = 8,
   1028 	.align = 8,
   1029 },
   1030 builtin_type_i8 = {
   1031 	.storage = STORAGE_I8,
   1032 	.size = 1,
   1033 	.align = 1,
   1034 },
   1035 builtin_type_i16 = {
   1036 	.storage = STORAGE_I16,
   1037 	.size = 2,
   1038 	.align = 2,
   1039 },
   1040 builtin_type_i32 = {
   1041 	.storage = STORAGE_I32,
   1042 	.size = 4,
   1043 	.align = 4,
   1044 },
   1045 builtin_type_i64 = {
   1046 	.storage = STORAGE_I64,
   1047 	.size = 8,
   1048 	.align = 8,
   1049 },
   1050 builtin_type_int = {
   1051 	.storage = STORAGE_INT,
   1052 	.size = 4, // XXX: ARCH
   1053 	.align = 4,
   1054 },
   1055 builtin_type_u8 = {
   1056 	.storage = STORAGE_U8,
   1057 	.size = 1,
   1058 	.align = 1,
   1059 },
   1060 builtin_type_u16 = {
   1061 	.storage = STORAGE_U16,
   1062 	.size = 2,
   1063 	.align = 2,
   1064 },
   1065 builtin_type_u32 = {
   1066 	.storage = STORAGE_U32,
   1067 	.size = 4,
   1068 	.align = 4,
   1069 },
   1070 builtin_type_u64 = {
   1071 	.storage = STORAGE_U64,
   1072 	.size = 8,
   1073 	.align = 8,
   1074 },
   1075 builtin_type_uint = {
   1076 	.storage = STORAGE_UINT,
   1077 	.size = 4,
   1078 	.align = 4,
   1079 },
   1080 builtin_type_uintptr = {
   1081 	.storage = STORAGE_UINTPTR,
   1082 	.size = 8, // XXX: ARCH
   1083 	.align = 8,
   1084 },
   1085 builtin_type_null = {
   1086 	.storage = STORAGE_NULL,
   1087 	.size = 8, // XXX: ARCH
   1088 	.align = 8,
   1089 },
   1090 builtin_type_rune = {
   1091 	.storage = STORAGE_RUNE,
   1092 	.size = 4,
   1093 	.align = 4,
   1094 },
   1095 builtin_type_size = {
   1096 	.storage = STORAGE_SIZE,
   1097 	.size = 8, // XXX: ARCH
   1098 	.align = 8,
   1099 },
   1100 builtin_type_void = {
   1101 	.storage = STORAGE_VOID,
   1102 	.size = 0,
   1103 	.align = 0,
   1104 },
   1105 builtin_type_const_bool = {
   1106 	.storage = STORAGE_BOOL,
   1107 	.flags = TYPE_CONST,
   1108 	.size = 4, // XXX: ARCH
   1109 	.align = 4,
   1110 },
   1111 builtin_type_const_char = {
   1112 	.storage = STORAGE_CHAR,
   1113 	.flags = TYPE_CONST,
   1114 	.size = 1,
   1115 	.align = 1,
   1116 },
   1117 builtin_type_const_f32 = {
   1118 	.storage = STORAGE_F32,
   1119 	.flags = TYPE_CONST,
   1120 	.size = 4,
   1121 	.align = 4,
   1122 },
   1123 builtin_type_const_f64 = {
   1124 	.storage = STORAGE_F64,
   1125 	.flags = TYPE_CONST,
   1126 	.size = 8,
   1127 	.align = 8,
   1128 },
   1129 builtin_type_const_i8 = {
   1130 	.storage = STORAGE_I8,
   1131 	.flags = TYPE_CONST,
   1132 	.size = 1,
   1133 	.align = 1,
   1134 },
   1135 builtin_type_const_i16 = {
   1136 	.storage = STORAGE_I16,
   1137 	.flags = TYPE_CONST,
   1138 	.size = 2,
   1139 	.align = 2,
   1140 },
   1141 builtin_type_const_i32 = {
   1142 	.storage = STORAGE_I32,
   1143 	.flags = TYPE_CONST,
   1144 	.size = 4,
   1145 	.align = 4,
   1146 },
   1147 builtin_type_const_i64 = {
   1148 	.storage = STORAGE_I64,
   1149 	.flags = TYPE_CONST,
   1150 	.size = 8,
   1151 	.align = 8,
   1152 },
   1153 builtin_type_const_int = {
   1154 	.storage = STORAGE_INT,
   1155 	.flags = TYPE_CONST,
   1156 	.size = 4, // XXX: ARCH
   1157 	.align = 4,
   1158 },
   1159 builtin_type_const_u8 = {
   1160 	.storage = STORAGE_U8,
   1161 	.flags = TYPE_CONST,
   1162 	.size = 1,
   1163 	.align = 1,
   1164 },
   1165 builtin_type_const_u16 = {
   1166 	.storage = STORAGE_U16,
   1167 	.flags = TYPE_CONST,
   1168 	.size = 2,
   1169 	.align = 2,
   1170 },
   1171 builtin_type_const_u32 = {
   1172 	.storage = STORAGE_U32,
   1173 	.flags = TYPE_CONST,
   1174 	.size = 4,
   1175 	.align = 4,
   1176 },
   1177 builtin_type_const_u64 = {
   1178 	.storage = STORAGE_U64,
   1179 	.flags = TYPE_CONST,
   1180 	.size = 8,
   1181 	.align = 8,
   1182 },
   1183 builtin_type_const_uint = {
   1184 	.storage = STORAGE_UINT,
   1185 	.flags = TYPE_CONST,
   1186 	.size = 4,
   1187 	.align = 4,
   1188 },
   1189 builtin_type_const_uintptr = {
   1190 	.storage = STORAGE_UINTPTR,
   1191 	.flags = TYPE_CONST,
   1192 	.size = 8, // XXX: ARCH
   1193 	.align = 8,
   1194 },
   1195 builtin_type_const_rune = {
   1196 	.storage = STORAGE_RUNE,
   1197 	.flags = TYPE_CONST,
   1198 	.size = 4,
   1199 	.align = 4,
   1200 },
   1201 builtin_type_const_size = {
   1202 	.storage = STORAGE_SIZE,
   1203 	.flags = TYPE_CONST,
   1204 	.size = 8, // XXX: ARCH
   1205 	.align = 8,
   1206 },
   1207 builtin_type_const_void = {
   1208 	.storage = STORAGE_VOID,
   1209 	.flags = TYPE_CONST,
   1210 	.size = 0,
   1211 	.align = 0,
   1212 };
   1213 
   1214 // Others
   1215 struct type builtin_type_ptr_const_char = {
   1216 	.storage = STORAGE_POINTER,
   1217 	.size = 8, // XXX: ARCH
   1218 	.align = 8,
   1219 	.pointer = {
   1220 		.referent = &builtin_type_const_char,
   1221 	},
   1222 },
   1223 builtin_type_str = {
   1224 	.storage = STORAGE_STRING,
   1225 	.size = 24, // XXX: ARCH
   1226 	.align = 8,
   1227 },
   1228 builtin_type_const_str = {
   1229 	.storage = STORAGE_STRING,
   1230 	.flags = TYPE_CONST,
   1231 	.size = 24, // XXX: ARCH
   1232 	.align = 8,
   1233 },
   1234 builtin_type_valist = {
   1235 	.storage = STORAGE_VALIST,
   1236 	.size = 32, // XXX: ARCH
   1237 	.align = 8,
   1238 };