harec

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

type_store.c (37900B)


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