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