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 = ¶m->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 = ∈ 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 = ∈ 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 }