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