harec

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

type_store.c (32832B)


      1 #include <assert.h>
      2 #include <stdarg.h>
      3 #include <stdlib.h>
      4 #include <string.h>
      5 #include <stdio.h>
      6 #include "check.h"
      7 #include "eval.h"
      8 #include "scope.h"
      9 #include "typedef.h"
     10 #include "type_store.h"
     11 #include "util.h"
     12 
     13 // XXX: This needs to be updated on updates to type_flags (types.h)
     14 const unsigned int typeflags[] = {
     15 	0,
     16 	TYPE_CONST,
     17 	TYPE_ERROR,
     18 	TYPE_ERROR | TYPE_CONST,
     19 };
     20 
     21 static struct dimensions lookup_atype_with_dimensions(struct type_store *store,
     22 		const struct type **type, const struct ast_type *atype);
     23 
     24 static const struct type *
     25 lookup_atype(struct type_store *store, const struct ast_type *atype);
     26 
     27 static void
     28 error(struct context *ctx, const struct location loc, char *fmt, ...)
     29 {
     30 	va_list ap;
     31 	va_start(ap, fmt);
     32 	size_t sz = vsnprintf(NULL, 0, fmt, ap);
     33 	va_end(ap);
     34 	char *msg = xcalloc(1, sz + 1);
     35 	va_start(ap, fmt);
     36 	vsnprintf(msg, sz + 1, fmt, ap);
     37 	va_end(ap);
     38 
     39 	struct errors *next = *ctx->next = xcalloc(1, sizeof(struct errors));
     40 	next->loc = loc;
     41 	next->msg = msg;
     42 	ctx->next = &next->next;
     43 }
     44 
     45 static size_t
     46 ast_array_len(struct type_store *store, const struct ast_type *atype)
     47 {
     48 	// TODO: Maybe we should cache these
     49 	struct expression in, out;
     50 	if (atype->array.length == NULL) {
     51 		return SIZE_UNDEFINED;
     52 	}
     53 	check_expression(store->check_context, atype->array.length, &in, NULL);
     54 	enum eval_result r = eval_expr(store->check_context, &in, &out);
     55 	if (r != EVAL_OK) {
     56 		error(store->check_context, atype->loc,
     57 			"Cannot evaluate array length at compile time");
     58 		return SIZE_UNDEFINED;
     59 	}
     60 	if (!type_is_integer(out.result)) {
     61 		error(store->check_context, atype->loc,
     62 			"Array length must be an integer");
     63 		return SIZE_UNDEFINED;
     64 	}
     65 	if (type_is_signed(out.result) && out.constant.ival <= 0) {
     66 		error(store->check_context, atype->loc,
     67 			"Array length must be greater than 0");
     68 		return SIZE_UNDEFINED;
     69 	}
     70 	return (size_t)out.constant.uval;
     71 }
     72 
     73 const struct type *
     74 builtin_type_for_storage(enum type_storage storage, bool is_const)
     75 {
     76 	switch (storage) {
     77 	case STORAGE_BOOL:
     78 		return is_const ? &builtin_type_const_bool : &builtin_type_bool;
     79 	case STORAGE_CHAR:
     80 		return is_const ? &builtin_type_const_char : &builtin_type_char;
     81 	case STORAGE_F32:
     82 		return is_const ? &builtin_type_const_f32 : &builtin_type_f32;
     83 	case STORAGE_F64:
     84 		return is_const ? &builtin_type_const_f64 : &builtin_type_f64;
     85 	case STORAGE_I8:
     86 		return is_const ? &builtin_type_const_i8 : &builtin_type_i8;
     87 	case STORAGE_I16:
     88 		return is_const ? &builtin_type_const_i16 : &builtin_type_i16;
     89 	case STORAGE_I32:
     90 		return is_const ? &builtin_type_const_i32 : &builtin_type_i32;
     91 	case STORAGE_I64:
     92 		return is_const ? &builtin_type_const_i64 : &builtin_type_i64;
     93 	case STORAGE_INT:
     94 		return is_const ? &builtin_type_const_int : &builtin_type_int;
     95 	case STORAGE_RUNE:
     96 		return is_const ? &builtin_type_const_rune : &builtin_type_rune;
     97 	case STORAGE_SIZE:
     98 		return is_const ? &builtin_type_const_size : &builtin_type_size;
     99 	case STORAGE_U8:
    100 		return is_const ? &builtin_type_const_u8 : &builtin_type_u8;
    101 	case STORAGE_U16:
    102 		return is_const ? &builtin_type_const_u16 : &builtin_type_u16;
    103 	case STORAGE_U32:
    104 		return is_const ? &builtin_type_const_u32 : &builtin_type_u32;
    105 	case STORAGE_U64:
    106 		return is_const ? &builtin_type_const_u64 : &builtin_type_u64;
    107 	case STORAGE_UINT:
    108 		return is_const ? &builtin_type_const_uint : &builtin_type_uint;
    109 	case STORAGE_UINTPTR:
    110 		return is_const ? &builtin_type_const_uintptr : &builtin_type_uintptr;
    111 	case STORAGE_VALIST:
    112 		return &builtin_type_valist;
    113 	case STORAGE_VOID:
    114 		return is_const ? &builtin_type_const_void : &builtin_type_void;
    115 	case STORAGE_NULL:
    116 		return &builtin_type_null; // const null and null are the same type
    117 	case STORAGE_STRING:
    118 		return is_const ? &builtin_type_const_str : &builtin_type_str;
    119 	case STORAGE_ALIAS:
    120 	case STORAGE_ARRAY:
    121 	case STORAGE_FUNCTION:
    122 	case STORAGE_FCONST:
    123 	case STORAGE_ICONST:
    124 	case STORAGE_RCONST:
    125 	case STORAGE_POINTER:
    126 	case STORAGE_SLICE:
    127 	case STORAGE_STRUCT:
    128 	case STORAGE_TAGGED:
    129 	case STORAGE_TUPLE:
    130 	case STORAGE_UNION:
    131 	case STORAGE_ENUM:
    132 		return NULL;
    133 	}
    134 	assert(0); // Unreachable
    135 }
    136 
    137 static const struct type *
    138 builtin_for_type(const struct type *type)
    139 {
    140 	if (type->flags & TYPE_ERROR) {
    141 		return NULL;
    142 	}
    143 	bool is_const = (type->flags & TYPE_CONST) != 0;
    144 	return builtin_type_for_storage(type->storage, is_const);
    145 }
    146 
    147 static struct struct_field *
    148 struct_insert_field(struct type_store *store, struct struct_field **fields,
    149 	enum type_storage storage, size_t *size, size_t *usize, size_t *align,
    150 	const struct ast_struct_union_type *atype, bool *ccompat, bool size_only)
    151 {
    152 	while (*fields && (!atype->name || !(*fields)->name || strcmp((*fields)->name, atype->name) < 0)) {
    153 		fields = &(*fields)->next;
    154 	}
    155 	struct struct_field *field = *fields;
    156 	if (field != NULL && atype->name && field->name && strcmp(field->name, atype->name) == 0) {
    157 		error(store->check_context, atype->type->loc,
    158 			"Duplicate struct/union member '%s'", atype->name);
    159 		return NULL;
    160 	}
    161 	// XXX: leaks if size_only
    162 	*fields = xcalloc(1, sizeof(struct struct_field));
    163 	(*fields)->next = field;
    164 	field = *fields;
    165 
    166 	if (atype->name) {
    167 		field->name = strdup(atype->name);
    168 	}
    169 	struct dimensions dim = {0};
    170 	if (size_only) {
    171 		dim = lookup_atype_with_dimensions(store, NULL, atype->type);
    172 	} else {
    173 		dim = lookup_atype_with_dimensions(store, &field->type, atype->type);
    174 	}
    175 	if (dim.size == 0) {
    176 		error(store->check_context, atype->type->loc,
    177 			"Struct field size cannot be zero");
    178 		return NULL;
    179 	} else if (dim.align == 0) {
    180 		error(store->check_context, atype->type->loc,
    181 			"Struct field alignment cannot be zero");
    182 		return NULL;
    183 	}
    184 
    185 	if (atype->offset) {
    186 		*ccompat = false;
    187 		struct expression in, out;
    188 		check_expression(store->check_context, atype->offset, &in, NULL);
    189 		field->offset = 0;
    190 		enum eval_result r = eval_expr(store->check_context, &in, &out);
    191 		if (r != EVAL_OK) {
    192 			error(store->check_context, in.loc,
    193 				"Cannot evaluate field offset at compile time");
    194 		} else if (!type_is_integer(out.result)) {
    195 			error(store->check_context, in.loc,
    196 				"Field offset must be an integer");
    197 		} else if (type_is_signed(out.result) && out.constant.ival < 0) {
    198 			error(store->check_context, in.loc,
    199 				"Field offset must not be less than 0");
    200 		} else {
    201 			field->offset = (size_t)out.constant.uval;
    202 		}
    203 	} else {
    204 		size_t offs = *size;
    205 		if (offs % dim.align) {
    206 			offs += dim.align - (offs % dim.align);
    207 		}
    208 		field->offset = offs;
    209 		assert(field->offset % dim.align == 0);
    210 	}
    211 
    212 	if (dim.size == SIZE_UNDEFINED || *size == SIZE_UNDEFINED) {
    213 		*size = SIZE_UNDEFINED;
    214 	} else if (storage == STORAGE_STRUCT) {
    215 		*size = field->offset + dim.size;
    216 	} else {
    217 		*usize = dim.size > *usize ? dim.size : *usize;
    218 	}
    219 	*align = dim.align > *align ? dim.align : *align;
    220 	field->size = dim.size;
    221 	return field;
    222 }
    223 
    224 static const struct type *type_store_lookup_type(struct type_store *store, const struct type *type);
    225 
    226 void
    227 shift_fields(struct type_store *store,
    228 	const struct ast_struct_union_type *atype, struct struct_field *parent)
    229 {
    230 	if (parent->type->storage == STORAGE_ALIAS
    231 			&& type_dealias(parent->type)->storage != STORAGE_STRUCT
    232 			&& type_dealias(parent->type)->storage != STORAGE_UNION) {
    233 		assert(atype);
    234 		error(store->check_context, atype->type->loc,
    235 			"Cannot embed non-struct non-union alias");
    236 		return;
    237 	}
    238 	if (parent->offset == 0) {
    239 		// We need to return early here in order to avoid dealiasing an
    240 		// embedded alias. This is acceptable at nonzero offsets, but we
    241 		// need to keep the alias if it's at offset 0 because of
    242 		// subtyping.
    243 		return;
    244 	}
    245 	const struct type *type = type_dealias(parent->type);
    246 	assert(type->storage == STORAGE_STRUCT
    247 		|| type->storage == STORAGE_UNION);
    248 	struct type new = {
    249 		.storage = type->storage,
    250 		.flags = type->flags,
    251 		.size = type->size,
    252 		.align = type->align,
    253 		.struct_union.c_compat = type->struct_union.c_compat,
    254 	};
    255 	struct struct_field **next = &new.struct_union.fields;
    256 	for (struct struct_field *field = type->struct_union.fields; field;
    257 			field = field->next) {
    258 		struct struct_field *new = *next =
    259 			xcalloc(1, sizeof(struct struct_field));
    260 		next = &new->next;
    261 		new->type = field->type;
    262 		new->offset = parent->offset;
    263 		if (field->name) {
    264 			new->name = strdup(field->name);
    265 		} else {
    266 			shift_fields(store, NULL, new);
    267 		}
    268 		// Sub-subfields are shifted by field->offset in the recursive
    269 		// shift_fields call, delay adding it to new->offset to avoid
    270 		// shifting by field->offset twice
    271 		new->offset += field->offset;
    272 	}
    273 
    274 	parent->type = type_store_lookup_type(store, &new);
    275 }
    276 
    277 static void
    278 struct_init_from_atype(struct type_store *store, enum type_storage storage,
    279 	size_t *size, size_t *align, struct struct_field **fields,
    280 	const struct ast_struct_union_type *atype, bool *ccompat, bool size_only)
    281 {
    282 	// TODO: fields with size SIZE_UNDEFINED
    283 	size_t usize = 0;
    284 	assert(storage == STORAGE_STRUCT || storage == STORAGE_UNION);
    285 	while (atype) {
    286 		struct struct_field *field = struct_insert_field(store, fields,
    287 			storage, size, &usize, align, atype, ccompat, size_only);
    288 		if (field == NULL) {
    289 			return;
    290 		}
    291 		if (!field->name && !size_only) {
    292 			// We need to shift the embedded struct/union's fields
    293 			// so that their offsets are from the start of the
    294 			// parent type. This is a bit of a hack, but it makes
    295 			// type_get_field far easier to implement and doesn't
    296 			// cause any trouble in gen since offsets are only used
    297 			// there for sorting fields.
    298 			shift_fields(store, atype, field);
    299 		}
    300 		atype = atype->next;
    301 	}
    302 
    303 	if (storage == STORAGE_UNION) {
    304 		*size = usize;
    305 	}
    306 }
    307 
    308 static size_t
    309 sum_tagged_memb(struct type_store *store,
    310 		const struct type_tagged_union *u)
    311 {
    312 	size_t nmemb = 0;
    313 	for (; u; u = u->next) {
    314 		const struct type *type = u->type;
    315 		if (type->storage == STORAGE_TAGGED) {
    316 			nmemb += sum_tagged_memb(store, &type->tagged);
    317 		} else {
    318 			++nmemb;
    319 		}
    320 	}
    321 	return nmemb;
    322 }
    323 
    324 // get next member of an incomplete tagged union without completing it
    325 static void
    326 tagged_or_atagged_member(struct type_store *store,
    327 		const struct ast_type **atype, const struct type **type)
    328 {
    329 	const struct ast_type *_atype = *atype;
    330 	while (_atype->storage == STORAGE_ALIAS && _atype->unwrap) {
    331 		const struct scope_object *obj = scope_lookup(
    332 			store->check_context->scope, &_atype->alias);
    333 		if (obj->otype != O_SCAN) {
    334 			if (obj->otype == O_TYPE) {
    335 				*type = type_dealias(obj->type);
    336 				return;
    337 			} else {
    338 				error(store->check_context, _atype->loc,
    339 					"Object '%s' is not a type",
    340 					identifier_unparse(&obj->ident));
    341 				*type = &builtin_type_void;
    342 				return;
    343 			}
    344 		}
    345 		struct incomplete_declaration *idecl =
    346 			(struct incomplete_declaration *)obj;
    347 		if (idecl->type != IDECL_DECL
    348 				|| idecl->decl.decl_type != AST_DECL_TYPE) {
    349 			error(store->check_context, _atype->loc,
    350 				"Object '%s' is not a type",
    351 				identifier_unparse(&obj->ident));
    352 			*type = &builtin_type_void;
    353 			return;
    354 		}
    355 		_atype = idecl->decl.type.type;
    356 	}
    357 	*type = NULL;
    358 	*atype = _atype;
    359 }
    360 
    361 static size_t
    362 sum_atagged_memb(struct type_store *store,
    363 		const struct ast_tagged_union_type *u)
    364 {
    365 	size_t nmemb = 0;
    366 	for (; u; u = u->next) {
    367 		const struct type *type = NULL;
    368 		const struct ast_type *atype = u->type;
    369 		tagged_or_atagged_member(store, &atype, &type);
    370 		if (type != NULL && type->storage == STORAGE_TAGGED) {
    371 			nmemb += sum_tagged_memb(store, &type->tagged);
    372 		} else if (atype->storage == STORAGE_TAGGED) {
    373 			nmemb += sum_atagged_memb(store, &atype->tagged_union);
    374 		} else {
    375 			++nmemb;
    376 		}
    377 	}
    378 	return nmemb;
    379 }
    380 
    381 static void
    382 collect_tagged_memb(struct type_store *store,
    383 		struct type_tagged_union **ta,
    384 		const struct type_tagged_union *src,
    385 		size_t *i)
    386 {
    387 	for (; src; src = src->next) {
    388 		const struct type *type = src->type;
    389 		if (type->storage == STORAGE_TAGGED) {
    390 			collect_tagged_memb(store, ta, &type->tagged, i);
    391 			continue;
    392 		}
    393 		struct type_tagged_union *tu;
    394 		ta[*i] = tu = xcalloc(1, sizeof(struct type_tagged_union));
    395 		tu->type = lower_const(type, NULL);
    396 		*i += 1;
    397 	}
    398 }
    399 
    400 static void
    401 collect_atagged_memb(struct type_store *store,
    402 		struct type_tagged_union **ta,
    403 		const struct ast_tagged_union_type *atu,
    404 		size_t *i)
    405 {
    406 	for (; atu; atu = atu->next) {
    407 		const struct type *type =
    408 			lookup_atype(store, atu->type);
    409 		if (type->storage == STORAGE_TAGGED) {
    410 			collect_tagged_memb(store, ta, &type->tagged, i);
    411 			continue;
    412 		}
    413 		struct type_tagged_union *tu;
    414 		ta[*i] = tu = xcalloc(1, sizeof(struct type_tagged_union));
    415 		tu->type = lower_const(type, NULL);
    416 		*i += 1;
    417 	}
    418 }
    419 
    420 static int
    421 tagged_cmp(const void *ptr_a, const void *ptr_b)
    422 {
    423 	const struct type_tagged_union **a =
    424 		(const struct type_tagged_union **)ptr_a;
    425 	const struct type_tagged_union **b =
    426 		(const struct type_tagged_union **)ptr_b;
    427 	return (*a)->type->id < (*b)->type->id ? -1
    428 		: (*a)->type->id > (*b)->type->id ? 1 : 0;
    429 }
    430 
    431 static size_t
    432 tagged_init(struct type_store *store, struct type *type,
    433 		struct type_tagged_union **tu, size_t nmemb)
    434 {
    435 	// Sort by ID
    436 	qsort(tu, nmemb, sizeof(tu[0]), tagged_cmp);
    437 
    438 	// Prune duplicates
    439 	size_t nmemb_dedup = 1;
    440 	for (size_t i = 1; i < nmemb; ++i) {
    441 		if (tu[i]->type->id != tu[nmemb_dedup - 1]->type->id) {
    442 			tu[nmemb_dedup++] = tu[i];
    443 		}
    444 	}
    445 	nmemb = nmemb_dedup;
    446 
    447 	// First one free
    448 	type->tagged = *tu[0];
    449 	free(tu[0]);
    450 
    451 	type->size = type->tagged.type->size;
    452 	type->align = type->tagged.type->align;
    453 
    454 	struct type_tagged_union **next = &type->tagged.next;
    455 	for (size_t i = 1; i < nmemb; ++i) {
    456 		if (tu[i]->type->size > type->size) {
    457 			type->size = tu[i]->type->size;
    458 		}
    459 		if (tu[i]->type->align > type->align) {
    460 			type->align = tu[i]->type->align;
    461 		}
    462 		*next = tu[i];
    463 		next = &tu[i]->next;
    464 	}
    465 
    466 	if (type->align < builtin_type_uint.align) {
    467 		type->align = builtin_type_uint.align;
    468 	}
    469 	type->size += builtin_type_uint.size % type->align
    470 		+ builtin_type_uint.align;
    471 	return nmemb;
    472 }
    473 
    474 static void
    475 tagged_init_from_atype(struct type_store *store,
    476 	struct type *type, const struct ast_type *atype)
    477 {
    478 	size_t nmemb = sum_atagged_memb(store, &atype->tagged_union);
    479 	struct type_tagged_union **tu =
    480 		xcalloc(nmemb, sizeof(struct type_tagged_union *));
    481 	size_t i = 0;
    482 	collect_atagged_memb(store, tu, &atype->tagged_union, &i);
    483 	nmemb = tagged_init(store, type, tu, nmemb);
    484 
    485 	if (nmemb <= 1) {
    486 		error(store->check_context, atype->loc,
    487 			"Cannot create tagged union with a single member");
    488 	}
    489 }
    490 
    491 static struct dimensions
    492 _tagged_size(struct type_store *store, const struct ast_tagged_union_type *u)
    493 {
    494 	struct dimensions dim = {0};
    495 	for (; u; u = u->next) {
    496 		struct dimensions memb = {0};
    497 		const struct type *type = NULL;
    498 		const struct ast_type *atype = u->type;
    499 		tagged_or_atagged_member(store, &atype, &type);
    500 		if (type != NULL && type->storage == STORAGE_TAGGED) {
    501 			for (const struct type_tagged_union *u = &type->tagged;
    502 					u; u = u->next) {
    503 				if (memb.size < u->type->size) {
    504 					memb.size = u->type->size;
    505 				}
    506 				if (memb.align < u->type->align) {
    507 					memb.align = u->type->align;
    508 				}
    509 			}
    510 		} else if (atype->storage == STORAGE_TAGGED) {
    511 			memb = _tagged_size(store, &atype->tagged_union);
    512 		} else {
    513 			memb = lookup_atype_with_dimensions(store, NULL, atype);
    514 		}
    515 		if (dim.size < memb.size) {
    516 			dim.size = memb.size;
    517 		}
    518 		if (dim.align < memb.align) {
    519 			dim.align = memb.align;
    520 		}
    521 	}
    522 	return dim;
    523 }
    524 
    525 // compute the dimensions of an incomplete tagged union without completing it
    526 static struct dimensions
    527 tagged_size(struct type_store *store, const struct ast_type *atype)
    528 {
    529 	struct dimensions dim = _tagged_size(store, &atype->tagged_union);
    530 	if (dim.align < builtin_type_uint.align) {
    531 		dim.align = builtin_type_uint.align;
    532 	}
    533 	dim.size += builtin_type_uint.size % dim.align
    534 		+ builtin_type_uint.align;
    535 	return dim;
    536 }
    537 
    538 
    539 static struct dimensions
    540 tuple_init_from_atype(struct type_store *store,
    541 	struct type *type, const struct ast_type *atype)
    542 {
    543 	const struct ast_tuple_type *atuple = &atype->tuple;
    544 	struct type_tuple *cur = NULL;
    545 	if (type) {
    546 		type->size = 0, type->align = 0;
    547 		cur = &type->tuple;
    548 	}
    549 	struct dimensions dim = {0};
    550 	while (atuple) {
    551 		struct dimensions memb = {0};
    552 		if (type) {
    553 			memb = lookup_atype_with_dimensions(store, &cur->type, atuple->type);
    554 			if (memb.size == 0 || memb.align == 0) {
    555 				error(store->check_context, atuple->type->loc,
    556 					"Tuple member types must have nonzero size and alignment");
    557 				return dim;
    558 			}
    559 			cur->offset = dim.size % memb.align + dim.size;
    560 		} else {
    561 			memb = lookup_atype_with_dimensions(store, NULL, atuple->type);
    562 			if (memb.size == 0 || memb.align == 0) {
    563 				error(store->check_context, atuple->type->loc,
    564 					"Tuple member types must have nonzero size and alignment");
    565 				return dim;
    566 			}
    567 		}
    568 		dim.size += dim.size % memb.align + memb.size;
    569 		if (dim.align < memb.align) {
    570 			dim.align = memb.align;
    571 		}
    572 
    573 		atuple = atuple->next;
    574 		if (atuple && type) {
    575 			cur->next = xcalloc(1, sizeof(struct type_tuple));
    576 			cur = cur->next;
    577 		}
    578 	}
    579 	if (type) {
    580 		type->size = dim.size;
    581 		type->align = dim.align;
    582 	}
    583 	return dim;
    584 }
    585 
    586 static const struct type *
    587 type_store_lookup_type(struct type_store *store, const struct type *type);
    588 
    589 static struct dimensions
    590 type_init_from_atype(struct type_store *store,
    591 	struct type *type,
    592 	const struct ast_type *atype)
    593 {
    594 	struct type tmp = {0};
    595 	bool size_only = false;
    596 	if (type == NULL) {
    597 		type = &tmp;
    598 		size_only = true;
    599 	}
    600 
    601 	type->storage = atype->storage;
    602 	type->flags = atype->flags;
    603 
    604 	// TODO: Use a dedicated error type instead of void for errors
    605 	const struct scope_object *obj = NULL;
    606 	const struct type *builtin;
    607 	switch (type->storage) {
    608 	case STORAGE_FCONST:
    609 	case STORAGE_ICONST:
    610 	case STORAGE_RCONST:
    611 	case STORAGE_ENUM:
    612 		assert(0); // Invariant
    613 	case STORAGE_BOOL:
    614 	case STORAGE_CHAR:
    615 	case STORAGE_F32:
    616 	case STORAGE_F64:
    617 	case STORAGE_I8:
    618 	case STORAGE_I16:
    619 	case STORAGE_I32:
    620 	case STORAGE_I64:
    621 	case STORAGE_INT:
    622 	case STORAGE_RUNE:
    623 	case STORAGE_SIZE:
    624 	case STORAGE_STRING:
    625 	case STORAGE_U8:
    626 	case STORAGE_U16:
    627 	case STORAGE_U32:
    628 	case STORAGE_U64:
    629 	case STORAGE_UINT:
    630 	case STORAGE_UINTPTR:
    631 	case STORAGE_VALIST:
    632 	case STORAGE_VOID:
    633 		builtin = builtin_type_for_storage(type->storage, false);
    634 		type->size = builtin->size;
    635 		type->align = builtin->align;
    636 		break;
    637 	case STORAGE_ALIAS:
    638 		obj = scope_lookup(store->check_context->scope, &atype->alias);
    639 		if (!obj) {
    640 			error(store->check_context, atype->loc,
    641 				"Unresolvable identifier '%s'",
    642 				identifier_unparse(&atype->alias));
    643 			*type = builtin_type_void;
    644 			return (struct dimensions){0};
    645 		}
    646 
    647 		if (obj->otype == O_SCAN) {
    648 			// an incomplete declaration was encountered
    649 			struct incomplete_declaration *idecl =
    650 				(struct incomplete_declaration *)obj;
    651 			if (size_only && idecl->type == IDECL_DECL) {
    652 				obj = wrap_resolver(store->check_context, obj,
    653 						resolve_dimensions);
    654 				type->size = obj->type->size;
    655 				type->align = obj->type->align;
    656 				break;
    657 			}
    658 			// complete it first and then proceed normally
    659 			obj = wrap_resolver(store->check_context,
    660 					obj, resolve_type);
    661 		}
    662 
    663 		if (obj->otype != O_TYPE) {
    664 			error(store->check_context, atype->loc,
    665 				"Object '%s' is not a type",
    666 				identifier_unparse(&obj->ident));
    667 			*type = builtin_type_void;
    668 			return (struct dimensions){0};
    669 		}
    670 
    671 		type->storage = obj->type->storage;
    672 		if (obj->type->storage == STORAGE_ENUM) {
    673 			type->_enum = obj->type->_enum;
    674 		} else if (atype->unwrap) {
    675 			*type = *type_dealias(obj->type);
    676 			break;
    677 		}
    678 		identifier_dup(&type->alias.ident, &obj->ident);
    679 		identifier_dup(&type->alias.name, &obj->name);
    680 		type->alias.type = obj->type->alias.type;
    681 		type->size = obj->type->size;
    682 		type->align = obj->type->align;
    683 		break;
    684 	case STORAGE_ARRAY:
    685 		type->array.length = ast_array_len(store, atype);
    686 		struct dimensions memb = {0};
    687 		if (size_only) {
    688 			memb = lookup_atype_with_dimensions(store,
    689 				NULL, atype->array.members);
    690 		} else {
    691 			memb = lookup_atype_with_dimensions(store,
    692 				&type->array.members, atype->array.members);
    693 		}
    694 		if (memb.size == SIZE_UNDEFINED) {
    695 			error(store->check_context, atype->loc,
    696 				"Array member must have defined size");
    697 			*type = builtin_type_void;
    698 			return (struct dimensions){0};
    699 		}
    700 
    701 		type->align = memb.align;
    702 		if (type->array.length == SIZE_UNDEFINED) {
    703 			type->size = SIZE_UNDEFINED;
    704 		} else {
    705 			type->size = memb.size * type->array.length;
    706 		}
    707 		break;
    708 	case STORAGE_FUNCTION:
    709 		type->size = SIZE_UNDEFINED;
    710 		type->align = ALIGN_UNDEFINED;
    711 		if (size_only) {
    712 			break;
    713 		}
    714 		type->func.result = lookup_atype(store,
    715 				atype->func.result);
    716 		type->func.variadism = atype->func.variadism;
    717 		type->func.flags = atype->func.flags;
    718 		struct type_func_param *param, **next = &type->func.params;
    719 		for (struct ast_function_parameters *aparam = atype->func.params;
    720 				aparam; aparam = aparam->next) {
    721 			param = *next = xcalloc(1, sizeof(struct type_func_param));
    722 			param->type = lookup_atype(store, aparam->type);
    723 			if (atype->func.variadism == VARIADISM_HARE
    724 					&& !aparam->next) {
    725 				param->type = type_store_lookup_slice(
    726 					store, param->type);
    727 			}
    728 			next = &param->next;
    729 		}
    730 		break;
    731 	case STORAGE_POINTER:
    732 		type->size = 8; // XXX: ARCH
    733 		type->align = 8;
    734 		if (size_only) {
    735 			break;
    736 		}
    737 		type->pointer.flags = atype->pointer.flags;
    738 		type->pointer.referent = lookup_atype(
    739 			store, atype->pointer.referent);
    740 		break;
    741 	case STORAGE_SLICE:
    742 		type->size = 24; // XXX: ARCH
    743 		type->align = 8;
    744 		if (size_only) {
    745 			break;
    746 		}
    747 		type->array.members = lookup_atype(
    748 			store, atype->array.members);
    749 		type->array.length = SIZE_UNDEFINED;
    750 		break;
    751 	case STORAGE_STRUCT:
    752 	case STORAGE_UNION:
    753 		type->struct_union.c_compat = true;
    754 		struct_init_from_atype(store, type->storage, &type->size,
    755 			&type->align, &type->struct_union.fields,
    756 			&atype->struct_union, &type->struct_union.c_compat,
    757 			size_only);
    758 		if (!type->struct_union.c_compat) {
    759 			// Recompute size
    760 			type->size = 0;
    761 			for (struct struct_field *f = type->struct_union.fields;
    762 					f; f = f->next) {
    763 				if (f->type) assert(f->type->size == f->size);
    764 				if (f->offset + f->size > type->size) {
    765 					type->size = f->offset + f->size;
    766 				}
    767 			}
    768 		}
    769 		break;
    770 	case STORAGE_TAGGED:
    771 		if (size_only) {
    772 			struct dimensions tagged = tagged_size(store, atype);
    773 			type->size = tagged.size;
    774 			type->align = tagged.align;
    775 		} else {
    776 			tagged_init_from_atype(store, type, atype);
    777 		}
    778 		break;
    779 	case STORAGE_TUPLE:
    780 		if (size_only) {
    781 			struct dimensions tup;
    782 			tup = tuple_init_from_atype(store, NULL, atype);
    783 			type->size = tup.size;
    784 			type->align = tup.align;
    785 		} else {
    786 			tuple_init_from_atype(store, type, atype);
    787 		}
    788 		break;
    789 	case STORAGE_NULL:
    790 		error(store->check_context, atype->loc,
    791 			"Type null used in invalid context");
    792 		*type = builtin_type_void;
    793 		return (struct dimensions){0};
    794 	}
    795 	return (struct dimensions){ .size = type->size, .align = type->align };
    796 }
    797 
    798 static void add_padding(size_t *size, size_t align) {
    799 	if (*size != SIZE_UNDEFINED && *size != 0 && *size % align != 0) {
    800 		*size += align - (*size - align) % align;
    801 	}
    802 }
    803 
    804 static const struct type *
    805 _type_store_lookup_type(
    806 	struct type_store *store,
    807 	const struct type *type)
    808 {
    809 	const struct type *builtin = builtin_for_type(type);
    810 	if (builtin) {
    811 		return builtin;
    812 	}
    813 
    814 	uint32_t hash = type_hash(type);
    815 	struct type_bucket **next = &store->buckets[hash % TYPE_STORE_BUCKETS],
    816 		*bucket = NULL;
    817 
    818 	while (*next) {
    819 		bucket = *next;
    820 		if (bucket->type.id == hash) {
    821 			if (bucket->type.storage == STORAGE_ALIAS) {
    822 				bucket->type.alias.type = type->alias.type;
    823 			}
    824 			return &bucket->type;
    825 		}
    826 		next = &bucket->next;
    827 	}
    828 
    829 	bucket = *next = xcalloc(1, sizeof(struct type_bucket));
    830 	bucket->type = *type;
    831 	bucket->type.id = hash;
    832 	add_padding(&bucket->type.size, type->align);
    833 	return &bucket->type;
    834 }
    835 
    836 static const struct type *
    837 type_store_lookup_type(struct type_store *store, const struct type *type)
    838 {
    839 	if (type->storage != STORAGE_ALIAS) {
    840 		return _type_store_lookup_type(store, type);
    841 	}
    842 	// References to type aliases always inherit the flags that the
    843 	// alias was defined with
    844 	struct type psuedotype = *type;
    845 	const struct scope_object *obj = scope_lookup(
    846 		store->check_context->scope, &type->alias.name);
    847 	psuedotype.flags |= obj->type->flags;
    848 	return type_store_lookup_alias(store, &psuedotype);
    849 }
    850 
    851 static struct dimensions
    852 lookup_atype_with_dimensions(struct type_store *store, const struct type **type, const struct ast_type *atype)
    853 {
    854 	struct type temp = {0};
    855 	struct dimensions dim = {0};
    856 	if (type) {
    857 		dim = type_init_from_atype(store, &temp, atype);
    858 		*type = type_store_lookup_type(store, &temp);
    859 	} else {
    860 		dim = type_init_from_atype(store, NULL, atype);
    861 	}
    862 	add_padding(&dim.size, dim.align);
    863 	return dim;
    864 }
    865 
    866 static const struct type *
    867 lookup_atype(struct type_store *store, const struct ast_type *atype)
    868 {
    869 	struct type temp = {0};
    870 	const struct type *type = &temp;
    871 	lookup_atype_with_dimensions(store, &type, atype);
    872 	return type;
    873 }
    874 
    875 const struct type *
    876 type_store_lookup_atype(struct type_store *store, const struct ast_type *atype)
    877 {
    878 	if (atype->storage == STORAGE_NULL) {
    879 		return &builtin_type_null;
    880 	};
    881 	return lookup_atype(store, atype);
    882 }
    883 
    884 // Compute dimensions of an incomplete type without completing it
    885 struct dimensions
    886 type_store_lookup_dimensions(struct type_store *store, const struct ast_type *atype)
    887 {
    888 	struct dimensions dim = type_init_from_atype(store, NULL, atype);
    889 	add_padding(&dim.size, dim.align);
    890 	return dim;
    891 }
    892 
    893 const struct type *
    894 type_store_lookup_with_flags(struct type_store *store,
    895 	const struct type *type, unsigned int flags)
    896 {
    897 	if (type->flags == flags) {
    898 		return type;
    899 	}
    900 	struct type new = *type;
    901 	new.flags = flags;
    902 	return _type_store_lookup_type(store, &new);
    903 }
    904 
    905 const struct type *
    906 type_store_lookup_pointer(struct type_store *store,
    907 	const struct type *referent, unsigned int ptrflags)
    908 {
    909 	referent = lower_const(referent, NULL);
    910 	struct type ptr = {
    911 		.storage = STORAGE_POINTER,
    912 		.pointer = {
    913 			.referent = referent,
    914 			.flags = ptrflags,
    915 		},
    916 		.size = 8, // XXX: ARCH
    917 		.align = 8,
    918 	};
    919 	return type_store_lookup_type(store, &ptr);
    920 }
    921 
    922 const struct type *
    923 type_store_lookup_array(struct type_store *store,
    924 	const struct type *members, size_t len, bool expandable)
    925 {
    926 	members = lower_const(members, NULL);
    927 	struct type array = {
    928 		.storage = STORAGE_ARRAY,
    929 		.array = {
    930 			.members = members,
    931 			.length = len,
    932 			// TODO: Define expandable semantics better in spec
    933 			.expandable = expandable,
    934 		},
    935 		.size = len == SIZE_UNDEFINED
    936 			? SIZE_UNDEFINED : members->size * len,
    937 		.align = members->align,
    938 	};
    939 	return type_store_lookup_type(store, &array);
    940 }
    941 
    942 const struct type *
    943 type_store_lookup_slice(struct type_store *store, const struct type *members)
    944 {
    945 	members = lower_const(members, NULL);
    946 	struct type slice = {
    947 		.storage = STORAGE_SLICE,
    948 		.array = {
    949 			.members = members,
    950 			.length = SIZE_UNDEFINED,
    951 		},
    952 		.size = 24, // XXX: ARCH
    953 		.align = 8,
    954 	};
    955 	return type_store_lookup_type(store, &slice);
    956 }
    957 
    958 const struct type *
    959 type_store_lookup_alias(struct type_store *store, const struct type *type)
    960 {
    961 	struct type tmp = *type;
    962 	const struct type *ret = NULL;
    963 	for (size_t i = 0; i < sizeof(typeflags) / sizeof(typeflags[0]); i++) {
    964 		if ((typeflags[i] & type->flags) != type->flags) {
    965 			continue;
    966 		}
    967 		if (type->alias.type) {
    968 			tmp.alias.type = type_store_lookup_with_flags(
    969 				store, type->alias.type, typeflags[i]);
    970 		}
    971 		tmp.flags = typeflags[i];
    972 		const struct type *alias = _type_store_lookup_type(store, &tmp);
    973 		if (typeflags[i] == type->flags) {
    974 			ret = alias;
    975 		}
    976 	}
    977 	return ret;
    978 }
    979 
    980 
    981 const struct type *
    982 type_store_lookup_tagged(struct type_store *store,
    983 		struct type_tagged_union *tags)
    984 {
    985 	struct type type = {
    986 		.storage = STORAGE_TAGGED,
    987 	};
    988 	size_t nmemb = sum_tagged_memb(store, tags);
    989 	struct type_tagged_union **tu =
    990 		xcalloc(nmemb, sizeof(struct type_tagged_union *));
    991 	size_t i = 0;
    992 	collect_tagged_memb(store, tu, tags, &i);
    993 	tagged_init(store, &type, tu, nmemb);
    994 	return type_store_lookup_type(store, &type);
    995 }
    996 
    997 const struct type *
    998 type_store_tagged_to_union(struct type_store *store, const struct type *tagged)
    999 {
   1000 	assert(tagged->storage == STORAGE_TAGGED);
   1001 	struct type type = {
   1002 		.storage = STORAGE_UNION,
   1003 		.flags = tagged->flags,
   1004 	};
   1005 	struct struct_field **next = &type.struct_union.fields;
   1006 	for (const struct type_tagged_union *tu = &tagged->tagged;
   1007 			tu; tu = tu->next) {
   1008 		if (tu->type->size == 0) {
   1009 			continue;
   1010 		}
   1011 		assert(tu->type->size != SIZE_UNDEFINED);
   1012 
   1013 		if (tu->type->size > type.size) {
   1014 			type.size = tu->type->size;
   1015 		}
   1016 		if (tu->type->align > type.align) {
   1017 			type.align = tu->type->align;
   1018 		}
   1019 
   1020 		struct struct_field *sf =
   1021 			xcalloc(1, sizeof(struct struct_field));
   1022 		sf->name = "unnamed";
   1023 		sf->type = tu->type;
   1024 		sf->next = *next, *next = sf;
   1025 		next = &sf->next;
   1026 	}
   1027 	type.struct_union.c_compat = true; // XXX: Unsure about this
   1028 	return type_store_lookup_type(store, &type);
   1029 }
   1030 
   1031 const struct type *
   1032 type_store_lookup_tuple(struct type_store *store, struct type_tuple *values,
   1033 		struct location loc)
   1034 {
   1035 	struct type type = {
   1036 		.storage = STORAGE_TUPLE,
   1037 	};
   1038 	for (struct type_tuple *t = values; t; t = t->next) {
   1039 		t->type = lower_const(t->type, NULL);
   1040 		if (t->type->align > type.align) {
   1041 			type.align = t->type->align;
   1042 		}
   1043 		if (t->type->size == 0 || t->type->align == 0) {
   1044 			error(store->check_context, loc,
   1045 				"Tuple values must have nonzero size and alignment");
   1046 			break;
   1047 		}
   1048 		t->offset = type.size % t->type->align + type.size;
   1049 		type.size += type.size % t->type->align + t->type->size;
   1050 	}
   1051 	type.tuple = *values;
   1052 	return type_store_lookup_type(store, &type);
   1053 }
   1054 
   1055 const struct type *
   1056 type_store_lookup_enum(struct type_store *store, const struct ast_type *atype,
   1057 	bool exported)
   1058 {
   1059 	struct type type = {0};
   1060 	type.storage = STORAGE_ENUM;
   1061 	type.flags = atype->flags;
   1062 	mkident(store->check_context, &type.alias.ident, &atype->alias);
   1063 	identifier_dup(&type.alias.name, &atype->alias);
   1064 	type.alias.exported = exported;
   1065 	type.alias.type =
   1066 		builtin_type_for_storage(atype->_enum.storage, false);
   1067 	if (!type_is_integer(type.alias.type)
   1068 			&& type.alias.type->storage != STORAGE_RUNE) {
   1069 		error(store->check_context, atype->loc,
   1070 			"Enum storage must be an integer or rune");
   1071 		return &builtin_type_void;
   1072 	}
   1073 	type.size = type.alias.type->size;
   1074 	type.align = type.alias.type->size;
   1075 	return type_store_lookup_type(store, &type);
   1076 }
   1077 
   1078 // Algorithm:
   1079 // - Deduplicate and collect nested unions
   1080 // - Merge *type with nullable *type
   1081 // - If one of the types is null:
   1082 // 	- If there's more than one pointer type, error out
   1083 // 	- If there's one pointer type, make it nullable and drop the null
   1084 // 	- If there are no pointer types, keep the null
   1085 // - If the resulting union only has one type, return that type
   1086 // - Otherwise, return a tagged union of all the selected types
   1087 const struct type *
   1088 type_store_reduce_result(struct type_store *store, struct type_tagged_union *in)
   1089 {
   1090 	if (!in) {
   1091 		return &builtin_type_void;
   1092 	} else if (!in->next) {
   1093 		return in->type;
   1094 	}
   1095 
   1096 	const struct type *type = type_store_lookup_tagged(store, in);
   1097 	struct type_tagged_union _in = type->tagged;
   1098 	in = &_in;
   1099 
   1100 	struct type_tagged_union **null = NULL;
   1101 	struct type_tagged_union *ptr = NULL;
   1102 	bool multiple_ptrs = false;
   1103 	struct type_tagged_union **tu = &in;
   1104 	while (*tu != NULL) {
   1105 		struct type_tagged_union *i = *tu;
   1106 		bool dropped = false;
   1107 		const struct type *it = i->type;
   1108 
   1109 		if (it->flags & TYPE_CONST) {
   1110 			struct type_tagged_union **j = &in;
   1111 			while (*j) {
   1112 				const struct type *jt = (*j)->type;
   1113 				if (jt == it) {
   1114 					j = &(*j)->next;
   1115 					continue;
   1116 				}
   1117 				jt = type_store_lookup_with_flags(store, jt,
   1118 					jt->flags | TYPE_CONST);
   1119 				if (jt == it) {
   1120 					*j = (*j)->next;
   1121 				} else {
   1122 					j = &(*j)->next;
   1123 				}
   1124 			}
   1125 		}
   1126 
   1127 		for (struct type_tagged_union *j = in; j != i; j = j->next) {
   1128 			const struct type *jt = j->type;
   1129 			assert(it->id != jt->id);
   1130 			if (it->storage != STORAGE_POINTER
   1131 					|| jt->storage != STORAGE_POINTER) {
   1132 				continue;
   1133 			}
   1134 			if (it->pointer.referent->id != jt->pointer.referent->id) {
   1135 				continue;
   1136 			}
   1137 			if (it->flags != jt->flags) {
   1138 				continue;
   1139 			}
   1140 			if ((it->pointer.flags & PTR_NULLABLE)
   1141 					|| (jt->pointer.flags & PTR_NULLABLE)) {
   1142 				it = type_store_lookup_pointer(store,
   1143 					it->pointer.referent, PTR_NULLABLE);
   1144 				jt = type_store_lookup_pointer(store,
   1145 					jt->pointer.referent, PTR_NULLABLE);
   1146 				if (it == jt) {
   1147 					dropped = true;
   1148 					*tu = i->next;
   1149 					j->type = jt;
   1150 					break;
   1151 				}
   1152 			};
   1153 		}
   1154 
   1155 		if (i->type->storage == STORAGE_NULL) {
   1156 			null = tu;
   1157 		}
   1158 		if (!dropped) {
   1159 			if (i->type->storage == STORAGE_POINTER) {
   1160 				if (ptr != NULL) {
   1161 					multiple_ptrs = true;
   1162 				}
   1163 				ptr = i;
   1164 			}
   1165 			tu = &i->next;
   1166 		}
   1167 	}
   1168 
   1169 	if (null != NULL && (multiple_ptrs || ptr == NULL)) {
   1170 		return NULL;
   1171 	}
   1172 
   1173 	if (null != NULL && ptr != NULL) {
   1174 		*null = (*null)->next;
   1175 		ptr->type = type_store_lookup_pointer(store,
   1176 			ptr->type->pointer.referent, PTR_NULLABLE);
   1177 	}
   1178 
   1179 	if (in->next == NULL) {
   1180 		return in->type;
   1181 	}
   1182 	return type_store_lookup_tagged(store, in);
   1183 }