types.c (31841B)
1 #include <assert.h> 2 #include <stdbool.h> 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <string.h> 6 #include "expr.h" 7 #include "scope.h" 8 #include "types.h" 9 #include "util.h" 10 11 const struct type * 12 type_dereference(const struct type *type) 13 { 14 switch (type->storage) { 15 case STORAGE_ALIAS: 16 if (type_dealias(type)->storage != STORAGE_POINTER) { 17 return type; 18 } 19 return type_dereference(type_dealias(type)); 20 case STORAGE_POINTER: 21 if (type->pointer.flags & PTR_NULLABLE) { 22 return NULL; 23 } 24 return type_dereference(type->pointer.referent); 25 default: 26 return type; 27 } 28 } 29 30 const struct type * 31 type_dealias(const struct type *type) 32 { 33 while (type->storage == STORAGE_ALIAS) { 34 if (type->alias.type == NULL) { 35 fprintf(stderr, "Cannot dealias incomplete type %s\n", 36 identifier_unparse(&type->alias.ident)); 37 assert(0); 38 } 39 type = type->alias.type; 40 } 41 return type; 42 } 43 44 bool 45 type_is_complete(const struct type *type) 46 { 47 while (type->storage == STORAGE_ALIAS) { 48 if (type->alias.type == NULL) { 49 return false; 50 } 51 type = type->alias.type; 52 } 53 return true; 54 } 55 56 const struct struct_field * 57 type_get_field(const struct type *type, const char *name) 58 { 59 // TODO: We should consider lowering unions into structs with explicit 60 // offsets 61 if (type->storage == STORAGE_ERROR) { 62 return NULL; 63 }; 64 assert(type->storage == STORAGE_STRUCT 65 || type->storage == STORAGE_UNION); 66 struct struct_field *field = type->struct_union.fields; 67 while (field) { 68 if (field->name) { 69 if (strcmp(field->name, name) == 0) { 70 return field; 71 } 72 } else { 73 const struct struct_field *f = 74 type_get_field(type_dealias(field->type), name); 75 if (f != NULL) { 76 return f; 77 } 78 } 79 field = field->next; 80 } 81 return NULL; 82 } 83 84 const struct type_tuple * 85 type_get_value(const struct type *type, uintmax_t index) 86 { 87 assert(type->storage == STORAGE_TUPLE); 88 const struct type_tuple *tuple = &type->tuple; 89 while (tuple) { 90 if (index == 0) { 91 return tuple; 92 } 93 tuple = tuple->next; 94 --index; 95 } 96 return NULL; 97 } 98 99 // Returns true if this type is or contains an error type 100 bool 101 type_has_error(const struct type *type) 102 { 103 if (type->flags & TYPE_ERROR) { 104 return true; 105 } 106 type = type_dealias(type); 107 if (type->storage != STORAGE_TAGGED) { 108 return false; 109 } 110 const struct type_tagged_union *tu = &type->tagged; 111 for (; tu; tu = tu->next) { 112 if (tu->type->flags & TYPE_ERROR) { 113 return true; 114 } 115 } 116 return false; 117 } 118 119 const char * 120 type_storage_unparse(enum type_storage storage) 121 { 122 switch (storage) { 123 case STORAGE_ALIAS: 124 return "alias"; 125 case STORAGE_ARRAY: 126 return "array"; 127 case STORAGE_BOOL: 128 return "bool"; 129 case STORAGE_CHAR: 130 return "char"; 131 case STORAGE_ENUM: 132 return "enum"; 133 case STORAGE_F32: 134 return "f32"; 135 case STORAGE_F64: 136 return "f64"; 137 case STORAGE_ERROR: 138 return "invalid"; 139 case STORAGE_FCONST: 140 return "fconst"; 141 case STORAGE_FUNCTION: 142 return "function"; 143 case STORAGE_I16: 144 return "i16"; 145 case STORAGE_I32: 146 return "i32"; 147 case STORAGE_I64: 148 return "i64"; 149 case STORAGE_I8: 150 return "i8"; 151 case STORAGE_ICONST: 152 return "iconst"; 153 case STORAGE_INT: 154 return "int"; 155 case STORAGE_POINTER: 156 return "pointer"; 157 case STORAGE_NULL: 158 return "null"; 159 case STORAGE_RCONST: 160 return "rconst"; 161 case STORAGE_RUNE: 162 return "rune"; 163 case STORAGE_SIZE: 164 return "size"; 165 case STORAGE_SLICE: 166 return "slice"; 167 case STORAGE_STRING: 168 return "str"; 169 case STORAGE_STRUCT: 170 return "struct"; 171 case STORAGE_TAGGED: 172 return "tagged union"; 173 case STORAGE_TUPLE: 174 return "tuple"; 175 case STORAGE_U16: 176 return "u16"; 177 case STORAGE_U32: 178 return "u32"; 179 case STORAGE_U64: 180 return "u64"; 181 case STORAGE_U8: 182 return "u8"; 183 case STORAGE_UINT: 184 return "uint"; 185 case STORAGE_UINTPTR: 186 return "uintptr"; 187 case STORAGE_UNION: 188 return "union"; 189 case STORAGE_VALIST: 190 return "valist"; 191 case STORAGE_VOID: 192 return "void"; 193 } 194 assert(0); 195 } 196 197 bool 198 type_is_integer(const struct type *type) 199 { 200 switch (type->storage) { 201 case STORAGE_VOID: 202 case STORAGE_ARRAY: 203 case STORAGE_FUNCTION: 204 case STORAGE_POINTER: 205 case STORAGE_SLICE: 206 case STORAGE_STRING: 207 case STORAGE_STRUCT: 208 case STORAGE_TAGGED: 209 case STORAGE_TUPLE: 210 case STORAGE_UNION: 211 case STORAGE_BOOL: 212 case STORAGE_NULL: 213 case STORAGE_RCONST: 214 case STORAGE_RUNE: 215 case STORAGE_F32: 216 case STORAGE_F64: 217 case STORAGE_FCONST: 218 case STORAGE_VALIST: 219 return false; 220 case STORAGE_CHAR: 221 case STORAGE_ENUM: 222 case STORAGE_ERROR: 223 case STORAGE_I8: 224 case STORAGE_I16: 225 case STORAGE_I32: 226 case STORAGE_I64: 227 case STORAGE_ICONST: 228 case STORAGE_INT: 229 case STORAGE_SIZE: 230 case STORAGE_U8: 231 case STORAGE_U16: 232 case STORAGE_U32: 233 case STORAGE_U64: 234 case STORAGE_UINT: 235 case STORAGE_UINTPTR: 236 return true; 237 case STORAGE_ALIAS: 238 return type_is_integer(type_dealias(type)); 239 } 240 assert(0); // Unreachable 241 } 242 243 bool 244 type_is_numeric(const struct type *type) 245 { 246 switch (type->storage) { 247 case STORAGE_VOID: 248 case STORAGE_ARRAY: 249 case STORAGE_FUNCTION: 250 case STORAGE_POINTER: 251 case STORAGE_SLICE: 252 case STORAGE_STRING: 253 case STORAGE_STRUCT: 254 case STORAGE_TAGGED: 255 case STORAGE_TUPLE: 256 case STORAGE_UNION: 257 case STORAGE_BOOL: 258 case STORAGE_CHAR: 259 case STORAGE_RCONST: 260 case STORAGE_RUNE: 261 case STORAGE_NULL: 262 case STORAGE_VALIST: 263 return false; 264 case STORAGE_ERROR: 265 case STORAGE_ENUM: 266 case STORAGE_I8: 267 case STORAGE_I16: 268 case STORAGE_I32: 269 case STORAGE_I64: 270 case STORAGE_ICONST: 271 case STORAGE_INT: 272 case STORAGE_F32: 273 case STORAGE_F64: 274 case STORAGE_FCONST: 275 case STORAGE_SIZE: 276 case STORAGE_U8: 277 case STORAGE_U16: 278 case STORAGE_U32: 279 case STORAGE_U64: 280 case STORAGE_UINT: 281 case STORAGE_UINTPTR: 282 return true; 283 case STORAGE_ALIAS: 284 return type_is_numeric(type_dealias(type)); 285 } 286 assert(0); // Unreachable 287 } 288 289 bool 290 type_is_float(const struct type *type) 291 { 292 type = type_dealias(type); 293 return type->storage == STORAGE_F32 || type->storage == STORAGE_F64 294 || type->storage == STORAGE_FCONST 295 || type->storage == STORAGE_ERROR; 296 } 297 298 bool 299 type_is_signed(const struct type *type) 300 { 301 enum type_storage storage = type_dealias(type)->storage; 302 if (storage == STORAGE_ENUM) { 303 storage = type_dealias(type)->alias.type->storage; 304 } 305 switch (storage) { 306 case STORAGE_VOID: 307 case STORAGE_ARRAY: 308 case STORAGE_ENUM: 309 case STORAGE_ERROR: // XXX? 310 case STORAGE_FUNCTION: 311 case STORAGE_POINTER: 312 case STORAGE_SLICE: 313 case STORAGE_STRING: 314 case STORAGE_STRUCT: 315 case STORAGE_TAGGED: 316 case STORAGE_TUPLE: 317 case STORAGE_UNION: 318 case STORAGE_BOOL: 319 case STORAGE_CHAR: 320 case STORAGE_RCONST: 321 case STORAGE_RUNE: 322 case STORAGE_NULL: 323 case STORAGE_SIZE: 324 case STORAGE_U8: 325 case STORAGE_U16: 326 case STORAGE_U32: 327 case STORAGE_U64: 328 case STORAGE_UINT: 329 case STORAGE_UINTPTR: 330 case STORAGE_VALIST: 331 return false; 332 case STORAGE_I8: 333 case STORAGE_I16: 334 case STORAGE_I32: 335 case STORAGE_I64: 336 case STORAGE_INT: 337 case STORAGE_F32: 338 case STORAGE_F64: 339 case STORAGE_FCONST: 340 return true; 341 case STORAGE_ICONST: 342 return type->_const.min < 0; 343 case STORAGE_ALIAS: 344 assert(0); // Handled above 345 } 346 assert(0); // Unreachable 347 } 348 349 bool 350 type_is_constant(const struct type *type) 351 { 352 return type->storage == STORAGE_FCONST 353 || type->storage == STORAGE_ICONST 354 || type->storage == STORAGE_RCONST; 355 } 356 357 uint32_t 358 type_hash(const struct type *type) 359 { 360 // XXX: ARCH 361 uint32_t hash = FNV1A_INIT; 362 hash = fnv1a(hash, type->storage); 363 hash = fnv1a(hash, type->flags); 364 switch (type->storage) { 365 case STORAGE_BOOL: 366 case STORAGE_CHAR: 367 case STORAGE_ERROR: 368 case STORAGE_F32: 369 case STORAGE_F64: 370 case STORAGE_I8: 371 case STORAGE_I16: 372 case STORAGE_I32: 373 case STORAGE_I64: 374 case STORAGE_INT: 375 case STORAGE_NULL: 376 case STORAGE_RUNE: 377 case STORAGE_SIZE: 378 case STORAGE_U8: 379 case STORAGE_U16: 380 case STORAGE_U32: 381 case STORAGE_U64: 382 case STORAGE_UINT: 383 case STORAGE_UINTPTR: 384 case STORAGE_VALIST: 385 case STORAGE_VOID: 386 case STORAGE_STRING: 387 break; // built-ins 388 case STORAGE_ENUM: 389 hash = fnv1a(hash, type->alias.type->storage); 390 /* fallthrough */ 391 case STORAGE_ALIAS: 392 for (const struct identifier *ident = &type->alias.ident; ident; 393 ident = ident->ns) { 394 hash = fnv1a_s(hash, ident->name); 395 hash = fnv1a(hash, 0); 396 } 397 break; 398 case STORAGE_ARRAY: 399 hash = fnv1a_u32(hash, type_hash(type->array.members)); 400 hash = fnv1a_size(hash, type->array.length); 401 hash = fnv1a_u32(hash, type->array.expandable); 402 break; 403 case STORAGE_FUNCTION: 404 hash = fnv1a_u32(hash, type_hash(type->func.result)); 405 hash = fnv1a(hash, type->func.variadism); 406 hash = fnv1a(hash, type->func.flags); 407 for (struct type_func_param *param = type->func.params; 408 param; param = param->next) { 409 hash = fnv1a_u32(hash, type_hash(param->type)); 410 } 411 break; 412 case STORAGE_FCONST: 413 case STORAGE_ICONST: 414 case STORAGE_RCONST: 415 hash = fnv1a(hash, type->_const.id); 416 break; 417 case STORAGE_POINTER: 418 hash = fnv1a(hash, type->pointer.flags); 419 hash = fnv1a_u32(hash, type_hash(type->pointer.referent)); 420 break; 421 case STORAGE_SLICE: 422 hash = fnv1a_u32(hash, type_hash(type->array.members)); 423 break; 424 case STORAGE_STRUCT: 425 case STORAGE_UNION: 426 for (const struct struct_field *field = type->struct_union.fields; 427 field; field = field->next) { 428 if (field->name) { 429 hash = fnv1a_s(hash, field->name); 430 } 431 hash = fnv1a_u32(hash, type_hash(field->type)); 432 hash = fnv1a_size(hash, field->offset); 433 } 434 break; 435 case STORAGE_TAGGED: 436 // Invariant: subtypes must be sorted by ID and must not include 437 // any other tagged union types, nor any duplicates. 438 for (const struct type_tagged_union *tu = &type->tagged; 439 tu; tu = tu->next) { 440 hash = fnv1a_u32(hash, type_hash(tu->type)); 441 } 442 break; 443 case STORAGE_TUPLE: 444 for (const struct type_tuple *tuple = &type->tuple; 445 tuple; tuple = tuple->next) { 446 hash = fnv1a_u32(hash, type_hash(tuple->type)); 447 } 448 break; 449 } 450 return hash; 451 } 452 453 // Note that the type this returns is NOT a type singleton and cannot be treated 454 // as such. 455 static const struct type * 456 strip_flags(const struct type *t, struct type *secondary) 457 { 458 if (!t->flags) { 459 return t; 460 } 461 *secondary = *t; 462 secondary->flags = 0; 463 secondary->id = type_hash(secondary); 464 return secondary; 465 } 466 467 const struct type * 468 tagged_select_subtype(const struct type *tagged, const struct type *subtype, 469 bool strip) 470 { 471 tagged = type_dealias(tagged); 472 assert(tagged->storage == STORAGE_TAGGED); 473 474 struct type _stripped; 475 const struct type *stripped = strip_flags(subtype, &_stripped); 476 477 size_t nassign = 0; 478 const struct type *selected = NULL; 479 for (const struct type_tagged_union *tu = &tagged->tagged; 480 tu; tu = tu->next) { 481 if (tu->type->id == subtype->id) { 482 return tu->type; 483 } 484 485 if (type_dealias(tu->type)->storage == STORAGE_VOID) { 486 continue; 487 } 488 if (type_is_assignable(tu->type, subtype)) { 489 selected = tu->type; 490 ++nassign; 491 } 492 } 493 494 if (strip) { 495 for (const struct type_tagged_union *tu = &tagged->tagged; 496 tu; tu = tu->next) { 497 struct type _tustripped; 498 const struct type *tustripped = 499 strip_flags(tu->type, &_tustripped); 500 if (tustripped->id == stripped->id) { 501 return tu->type; 502 } 503 } 504 } 505 506 if (nassign == 1) { 507 return selected; 508 } 509 510 return NULL; 511 } 512 513 static intmax_t 514 min_value(const struct type *t) 515 { 516 assert(type_is_integer(t)); 517 if (!type_is_signed(t)) { 518 return 0; 519 } 520 if (t->size == sizeof(intmax_t)) { 521 return INTMAX_MIN; 522 } 523 return -((intmax_t)1 << (t->size * 8 - 1)); 524 } 525 526 static uintmax_t 527 max_value(const struct type *t) 528 { 529 assert(type_is_integer(t)); 530 size_t bits = t->size * 8; 531 if (type_is_signed(t)) { 532 bits--; 533 } 534 if (bits == sizeof(uintmax_t) * 8) { 535 return UINTMAX_MAX; 536 } 537 return ((uintmax_t)1 << bits) - 1; 538 } 539 540 const struct type * 541 type_create_const(enum type_storage storage, intmax_t min, intmax_t max) 542 { 543 // XXX: This'll be impossible to free. The right solution would be to 544 // store iconsts in the type store, but that'd require passing the store 545 // into type_is_assignable et al. An easier solution would be to keep 546 // our own list of iconsts and free them separately. Whatever, it 547 // doesn't really matter that much. 548 static uint32_t id = 0; 549 struct type *type = xcalloc(sizeof(struct type), 1); 550 type->storage = storage; 551 type->size = SIZE_UNDEFINED; 552 type->align = ALIGN_UNDEFINED; 553 type->_const.min = min; 554 type->_const.max = max; 555 type->_const.id = id++; 556 type->id = type_hash(type); 557 assert(type_is_constant(type)); 558 return type; 559 } 560 561 // Register a reference to a flexible constant type. When `type` is lowered in 562 // [[lower_const]], *ref will be updated to point to the new type. 563 void 564 const_refer(const struct type *type, const struct type **ref) 565 { 566 if (type == NULL || !type_is_constant(type)) { 567 return; 568 } 569 struct type_const *constant = (struct type_const *)&type->_const; 570 571 if (constant->nrefs >= constant->zrefs) { 572 constant->zrefs *= 2; 573 if (constant->zrefs == 0) { 574 constant->zrefs++; 575 } 576 constant->refs = xrealloc(constant->refs, 577 constant->zrefs * sizeof(const struct type **)); 578 } 579 constant->refs[constant->nrefs] = ref; 580 constant->nrefs++; 581 } 582 583 // Lower a flexible constant type. If new == NULL, lower it to its default type. 584 const struct type * 585 lower_const(const struct type *old, const struct type *new) { 586 if (!type_is_constant(old)) { 587 // If new != NULL, we're expected to always do something, and we 588 // can't if it's not a constant 589 assert(new == NULL); 590 return old; 591 } 592 if (new == NULL) { 593 switch (old->storage) { 594 case STORAGE_FCONST: 595 new = &builtin_type_f64; 596 break; 597 case STORAGE_ICONST: 598 if (old->_const.max <= (intmax_t)max_value(&builtin_type_int) 599 && old->_const.min >= min_value(&builtin_type_int)) { 600 new = &builtin_type_int; 601 } else { 602 new = &builtin_type_i64; 603 } 604 break; 605 case STORAGE_RCONST: 606 new = &builtin_type_rune; 607 break; 608 default: 609 assert(0); 610 } 611 } 612 for (size_t i = 0; i < old->_const.nrefs; i++) { 613 const_refer(new, old->_const.refs[i]); 614 *old->_const.refs[i] = new; 615 } 616 // XXX: Can we free old? 617 return new; 618 } 619 620 // Implements the flexible constant promotion algorithm 621 const struct type * 622 promote_const(const struct type *a, const struct type *b) { 623 if (a->storage == STORAGE_ICONST && b->storage == STORAGE_ICONST) { 624 intmax_t min = a->_const.min < b->_const.min 625 ? a->_const.min : b->_const.min; 626 intmax_t max = a->_const.max > b->_const.max 627 ? a->_const.max : b->_const.max; 628 const struct type *l = 629 type_create_const(STORAGE_ICONST, min, max); 630 lower_const(a, l); 631 lower_const(b, l); 632 return l; 633 } 634 if (type_is_constant(a)) { 635 if (a->storage == b->storage) { 636 const struct type *l = 637 type_create_const(a->storage, 0, 0); 638 lower_const(a, l); 639 lower_const(b, l); 640 return l; 641 } 642 if (type_is_constant(b)) { 643 return NULL; 644 } 645 return promote_const(b, a); 646 } 647 assert(!type_is_constant(a) && type_is_constant(b)); 648 if (type_dealias(a)->storage == STORAGE_TAGGED) { 649 const struct type *tag = NULL; 650 for (const struct type_tagged_union *tu = 651 &type_dealias(a)->tagged; tu; tu = tu->next) { 652 const struct type *p = promote_const(tu->type, b); 653 if (!p) { 654 lower_const(b, tag); 655 continue; 656 } 657 if (tag) { 658 // Ambiguous 659 b = lower_const(b, NULL); 660 if (type_is_assignable(a, b)) { 661 return b; 662 } 663 return NULL; 664 } 665 tag = p; 666 } 667 return tag; 668 } 669 switch (b->storage) { 670 case STORAGE_FCONST: 671 if (!type_is_float(a)) { 672 return NULL; 673 } 674 lower_const(b, a); 675 return a; 676 case STORAGE_ICONST: 677 if (!type_is_integer(a)) { 678 return NULL; 679 } 680 if (type_is_signed(a) && min_value(a) > b->_const.min) { 681 return NULL; 682 } 683 if (b->_const.max > 0 && max_value(a) < (uintmax_t)b->_const.max) { 684 return NULL; 685 } 686 lower_const(b, a); 687 return a; 688 case STORAGE_RCONST: 689 if (type_dealias(a)->storage == STORAGE_RUNE) { 690 lower_const(b, a); 691 return a; 692 } 693 // XXX: This is probably a bit too lenient but I can't think of 694 // a better way to do this 695 if (!type_is_integer(a)) { 696 return NULL; 697 } 698 lower_const(b, a); 699 return a; 700 default: 701 assert(0); // Invariant 702 } 703 } 704 705 bool 706 tagged_subset_compat(const struct type *superset, const struct type *subset) 707 { 708 // Note: this implementation depends on the invariant that tagged union 709 // member types are sorted by their type ID. 710 superset = type_dealias(superset), subset = type_dealias(subset); 711 if (superset->storage != STORAGE_TAGGED || subset->storage != STORAGE_TAGGED) { 712 return false; 713 } 714 const struct type_tagged_union *superset_tu = &superset->tagged, 715 *subset_tu = &subset->tagged; 716 while (subset_tu && superset_tu) { 717 while (superset_tu) { 718 if (superset_tu->type->id == subset_tu->type->id) { 719 subset_tu = subset_tu->next; 720 superset_tu = superset_tu->next; 721 break; 722 } 723 superset_tu = superset_tu->next; 724 } 725 } 726 727 return !subset_tu; 728 } 729 730 static bool 731 struct_subtype(const struct type *to, const struct type *from) { 732 if (from->storage != STORAGE_STRUCT) { 733 return false; 734 } 735 for (struct struct_field *f = from->struct_union.fields; f; 736 f = f->next) { 737 if (f->offset == 0) { 738 return f->type == to 739 || struct_subtype(to, type_dealias(f->type)); 740 } 741 } 742 return false; 743 } 744 745 bool 746 type_is_assignable(const struct type *to, const struct type *from) 747 { 748 const struct type *to_orig = to, *from_orig = from; 749 if (type_dealias(to)->storage != STORAGE_TAGGED) { 750 to = type_dealias(to); 751 from = type_dealias(from); 752 } 753 754 // const and non-const types are mutually assignable 755 struct type _to, _from; 756 to = strip_flags(to, &_to), from = strip_flags(from, &_from); 757 if (to->id == from->id && to->storage != STORAGE_VOID) { 758 return true; 759 } 760 761 if (type_is_constant(from)) { 762 return promote_const(to_orig, from_orig); 763 } 764 765 struct type _to_secondary, _from_secondary; 766 const struct type *to_secondary, *from_secondary; 767 switch (to->storage) { 768 case STORAGE_FCONST: 769 case STORAGE_ICONST: 770 case STORAGE_RCONST: 771 return promote_const(to_orig, from_orig); 772 case STORAGE_I8: 773 case STORAGE_I16: 774 case STORAGE_I32: 775 case STORAGE_I64: 776 case STORAGE_INT: 777 return type_is_integer(from) 778 && type_is_signed(from) 779 && to->size >= from->size; 780 case STORAGE_SIZE: 781 case STORAGE_U8: 782 case STORAGE_U16: 783 case STORAGE_U32: 784 case STORAGE_U64: 785 case STORAGE_UINT: 786 return type_is_integer(from) 787 && !type_is_signed(from) 788 && to->size >= from->size; 789 case STORAGE_F32: 790 case STORAGE_F64: 791 return type_is_float(from); 792 case STORAGE_POINTER: 793 to_secondary = type_dealias(to->pointer.referent); 794 to_secondary = strip_flags(to_secondary, &_to_secondary); 795 switch (from->storage) { 796 case STORAGE_UINTPTR: 797 return true; 798 case STORAGE_NULL: 799 return to->pointer.flags & PTR_NULLABLE; 800 case STORAGE_POINTER: 801 from_secondary = type_dealias(from->pointer.referent); 802 from_secondary = strip_flags(from_secondary, &_from_secondary); 803 if (struct_subtype(to->pointer.referent, from_secondary)) { 804 return true; 805 } 806 switch (to_secondary->storage) { 807 case STORAGE_VOID: 808 break; 809 case STORAGE_ARRAY: 810 if (!type_is_assignable(to_secondary, from_secondary)) { 811 return false; 812 } 813 break; 814 default: 815 if (to_secondary->id != from_secondary->id) { 816 return false; 817 } 818 break; 819 } 820 if (from->pointer.flags & PTR_NULLABLE) { 821 return to->pointer.flags & PTR_NULLABLE; 822 } 823 return true; 824 default: 825 return false; 826 } 827 assert(0); // Unreachable 828 case STORAGE_ALIAS: 829 assert(to->alias.type); 830 return type_is_assignable(to->alias.type, from); 831 case STORAGE_STRING: 832 return to->id == builtin_type_ptr_const_char.id; 833 case STORAGE_VOID: 834 return to_orig->id == from_orig->id && 835 (from_orig->flags & TYPE_ERROR) == (to_orig->flags & TYPE_ERROR); 836 case STORAGE_SLICE: 837 if (from->storage == STORAGE_POINTER) { 838 from = type_dealias(from->pointer.referent); 839 if (from->storage != STORAGE_ARRAY) { 840 return false; 841 } 842 } 843 if (from->storage != STORAGE_ARRAY 844 && from->storage != STORAGE_SLICE) { 845 return false; 846 } 847 to_secondary = strip_flags( 848 type_dealias(to->array.members), 849 &_to_secondary); 850 from_secondary = strip_flags( 851 type_dealias(from->array.members), 852 &_from_secondary); 853 if (to->storage == STORAGE_SLICE 854 && to_secondary->storage == STORAGE_VOID) { 855 return true; 856 } 857 return to_secondary->id == from_secondary->id; 858 case STORAGE_ARRAY: 859 if (from->storage != STORAGE_ARRAY) { 860 return false; 861 } 862 if (from->array.expandable) { 863 return to->array.length != SIZE_UNDEFINED 864 && to->array.length >= from->array.length 865 && to->array.members == from->array.members; 866 } else { 867 return to->array.length == SIZE_UNDEFINED 868 && from->array.length != SIZE_UNDEFINED 869 && to->array.members == from->array.members; 870 } 871 case STORAGE_TAGGED: 872 return tagged_select_subtype(to, from_orig, true) != NULL 873 || tagged_subset_compat(to, from); 874 // The following types are only assignable from themselves, and are 875 // handled above: 876 case STORAGE_BOOL: 877 case STORAGE_CHAR: 878 case STORAGE_ENUM: 879 case STORAGE_FUNCTION: 880 case STORAGE_NULL: 881 case STORAGE_RUNE: 882 case STORAGE_STRUCT: 883 case STORAGE_TUPLE: 884 case STORAGE_UINTPTR: 885 case STORAGE_UNION: 886 case STORAGE_VALIST: 887 return false; 888 case STORAGE_ERROR: 889 return true; 890 } 891 892 assert(0); // Unreachable 893 } 894 895 static const struct type * 896 is_castable_with_tagged(const struct type *to, const struct type *from) 897 { 898 if (type_dealias(from)->storage == STORAGE_TAGGED 899 && type_dealias(to)->storage == STORAGE_TAGGED) { 900 if (tagged_subset_compat(to, from) || tagged_subset_compat(from, to)) { 901 return to; 902 } 903 } 904 if (type_dealias(to)->storage == STORAGE_TAGGED) { 905 const struct type *subtype = tagged_select_subtype(to, from, true); 906 if (subtype != NULL) { 907 return subtype; 908 } 909 } 910 if (type_dealias(from)->storage == STORAGE_TAGGED) { 911 const struct type *subtype = tagged_select_subtype(from, to, true); 912 if (subtype != NULL) { 913 return subtype; 914 } 915 } 916 return NULL; 917 } 918 919 const struct type * 920 type_is_castable(const struct type *to, const struct type *from) 921 { 922 if (to->storage == STORAGE_VOID) { 923 if (type_is_constant(from)) { 924 lower_const(from, NULL); 925 }; 926 return to; 927 } 928 929 if (type_dealias(from)->storage == STORAGE_TAGGED 930 || type_dealias(to)->storage == STORAGE_TAGGED) { 931 return is_castable_with_tagged(to, from); 932 } 933 934 const struct type *to_orig = to, *from_orig = from; 935 to = type_dealias(to), from = type_dealias(from); 936 if (to == from) { 937 return to_orig; 938 } 939 940 struct type _to, _from; 941 to = strip_flags(to, &_to), from = strip_flags(from, &_from); 942 if (to->id == from->id) { 943 return to_orig; 944 } 945 946 switch (from->storage) { 947 case STORAGE_FCONST: 948 case STORAGE_ICONST: 949 case STORAGE_RCONST: 950 return promote_const(from_orig, to_orig); 951 case STORAGE_I8: 952 case STORAGE_I16: 953 case STORAGE_I32: 954 case STORAGE_I64: 955 case STORAGE_INT: 956 case STORAGE_SIZE: 957 case STORAGE_U16: 958 case STORAGE_U64: 959 case STORAGE_UINT: 960 return to->storage == STORAGE_ENUM || type_is_numeric(to) 961 ? to_orig : NULL; 962 case STORAGE_U8: 963 return to->storage == STORAGE_ENUM 964 || type_is_numeric(to) 965 || to->storage == STORAGE_CHAR 966 ? to_orig : NULL; 967 case STORAGE_U32: 968 return to->storage == STORAGE_ENUM 969 || type_is_numeric(to) 970 || to->storage == STORAGE_RUNE 971 ? to_orig : NULL; 972 case STORAGE_CHAR: 973 return to->storage == STORAGE_U8 974 ? to_orig : NULL; 975 case STORAGE_RUNE: 976 return to->storage == STORAGE_U32 977 ? to_orig : NULL; 978 case STORAGE_ENUM: 979 return to->storage == STORAGE_ENUM || type_is_integer(from) 980 ? to_orig : NULL; 981 case STORAGE_F32: 982 case STORAGE_F64: 983 return type_is_numeric(to) 984 ? to_orig : NULL; 985 case STORAGE_UINTPTR: 986 return to->storage == STORAGE_POINTER 987 || to->storage == STORAGE_NULL 988 || type_is_numeric(to) 989 || to->storage == STORAGE_ENUM 990 ? to_orig : NULL; 991 case STORAGE_POINTER: 992 return to->storage == STORAGE_POINTER 993 || to->storage == STORAGE_NULL 994 || to->storage == STORAGE_UINTPTR 995 ? to_orig : NULL; 996 case STORAGE_NULL: 997 return to->storage == STORAGE_POINTER 998 || to->storage == STORAGE_UINTPTR 999 ? to_orig : NULL; 1000 case STORAGE_SLICE: 1001 return to->storage == STORAGE_SLICE 1002 || (to->storage == STORAGE_POINTER 1003 && to->pointer.referent->storage == STORAGE_ARRAY) 1004 ? to_orig : NULL; 1005 case STORAGE_ARRAY: 1006 return to->storage == STORAGE_ARRAY 1007 || to->storage == STORAGE_SLICE 1008 ? to_orig : NULL; 1009 // Cannot be cast: 1010 case STORAGE_STRING: 1011 case STORAGE_BOOL: 1012 case STORAGE_VOID: 1013 case STORAGE_FUNCTION: 1014 case STORAGE_TUPLE: 1015 case STORAGE_STRUCT: 1016 case STORAGE_UNION: 1017 case STORAGE_VALIST: 1018 return NULL; 1019 case STORAGE_ERROR: 1020 return to_orig; 1021 case STORAGE_TAGGED: 1022 case STORAGE_ALIAS: 1023 assert(0); // Handled above 1024 } 1025 1026 assert(0); // Unreachable 1027 } 1028 1029 void 1030 builtin_types_init(const char *target) 1031 { 1032 if (strcmp(target, "aarch64") == 0) { 1033 builtin_type_int.size = 4; 1034 builtin_type_int.align = 4; 1035 builtin_type_uint.size = 4; 1036 builtin_type_uint.align = 4; 1037 builtin_type_uintptr.size = 8; 1038 builtin_type_uintptr.align = 8; 1039 builtin_type_null.size = 8; 1040 builtin_type_null.align = 8; 1041 builtin_type_size.size = 8; 1042 builtin_type_size.align = 8; 1043 builtin_type_const_int.size = 4; 1044 builtin_type_const_int.align = 4; 1045 builtin_type_const_uint.size = 4; 1046 builtin_type_const_uint.align = 4; 1047 builtin_type_const_uintptr.size = 8; 1048 builtin_type_const_uintptr.align = 8; 1049 builtin_type_const_size.size = 8; 1050 builtin_type_const_size.align = 8; 1051 builtin_type_ptr_const_char.size = 8; 1052 builtin_type_ptr_const_char.align = 8; 1053 builtin_type_str.size = 24; 1054 builtin_type_str.align = 8; 1055 builtin_type_const_str.size = 24; 1056 builtin_type_const_str.align = 8; 1057 builtin_type_valist.size = 32; 1058 builtin_type_valist.align = 8; 1059 } else if (strcmp(target, "riscv64") == 0) { 1060 builtin_type_int.size = 4; 1061 builtin_type_int.align = 4; 1062 builtin_type_uint.size = 4; 1063 builtin_type_uint.align = 4; 1064 builtin_type_uintptr.size = 8; 1065 builtin_type_uintptr.align = 8; 1066 builtin_type_null.size = 8; 1067 builtin_type_null.align = 8; 1068 builtin_type_size.size = 8; 1069 builtin_type_size.align = 8; 1070 builtin_type_const_int.size = 4; 1071 builtin_type_const_int.align = 4; 1072 builtin_type_const_uint.size = 4; 1073 builtin_type_const_uint.align = 4; 1074 builtin_type_const_uintptr.size = 8; 1075 builtin_type_const_uintptr.align = 8; 1076 builtin_type_const_size.size = 8; 1077 builtin_type_const_size.align = 8; 1078 builtin_type_ptr_const_char.size = 8; 1079 builtin_type_ptr_const_char.align = 8; 1080 builtin_type_str.size = 24; 1081 builtin_type_str.align = 8; 1082 builtin_type_const_str.size = 24; 1083 builtin_type_const_str.align = 8; 1084 builtin_type_valist.size = 8; 1085 builtin_type_valist.align = 8; 1086 } else if (strcmp(target, "x86_64") == 0) { 1087 builtin_type_int.size = 4; 1088 builtin_type_int.align = 4; 1089 builtin_type_uint.size = 4; 1090 builtin_type_uint.align = 4; 1091 builtin_type_uintptr.size = 8; 1092 builtin_type_uintptr.align = 8; 1093 builtin_type_null.size = 8; 1094 builtin_type_null.align = 8; 1095 builtin_type_size.size = 8; 1096 builtin_type_size.align = 8; 1097 builtin_type_const_int.size = 4; 1098 builtin_type_const_int.align = 4; 1099 builtin_type_const_uint.size = 4; 1100 builtin_type_const_uint.align = 4; 1101 builtin_type_const_uintptr.size = 8; 1102 builtin_type_const_uintptr.align = 8; 1103 builtin_type_const_size.size = 8; 1104 builtin_type_const_size.align = 8; 1105 builtin_type_ptr_const_char.size = 8; 1106 builtin_type_ptr_const_char.align = 8; 1107 builtin_type_str.size = 24; 1108 builtin_type_str.align = 8; 1109 builtin_type_const_str.size = 24; 1110 builtin_type_const_str.align = 8; 1111 builtin_type_valist.size = 24; 1112 builtin_type_valist.align = 8; 1113 } else { 1114 fprintf(stderr, "Unsupported or unrecognized target: %s", target); 1115 exit(EXIT_FAILURE); 1116 } 1117 struct type *builtins[] = { 1118 &builtin_type_bool, &builtin_type_char, &builtin_type_error, 1119 &builtin_type_f32, &builtin_type_f64, &builtin_type_i8, 1120 &builtin_type_i16, &builtin_type_i32, &builtin_type_i64, 1121 &builtin_type_int, &builtin_type_u8, &builtin_type_u16, 1122 &builtin_type_u32, &builtin_type_u64, &builtin_type_uint, 1123 &builtin_type_uintptr, &builtin_type_null, &builtin_type_rune, 1124 &builtin_type_size, &builtin_type_void, 1125 &builtin_type_const_bool, &builtin_type_const_char, 1126 &builtin_type_const_f32, &builtin_type_const_f64, 1127 &builtin_type_const_i8, &builtin_type_const_i16, 1128 &builtin_type_const_i32, &builtin_type_const_i64, 1129 &builtin_type_const_int, &builtin_type_const_u8, 1130 &builtin_type_const_u16, &builtin_type_const_u32, 1131 &builtin_type_const_u64, &builtin_type_const_uint, 1132 &builtin_type_const_uintptr, &builtin_type_const_rune, 1133 &builtin_type_const_size, &builtin_type_const_void, 1134 &builtin_type_ptr_const_char, &builtin_type_str, 1135 &builtin_type_const_str, &builtin_type_valist, 1136 }; 1137 for (size_t i = 0; i < sizeof(builtins) / sizeof(builtins[0]); ++i) { 1138 builtins[i]->id = type_hash(builtins[i]); 1139 } 1140 } 1141 1142 // Built-in type singletons 1143 struct type builtin_type_bool = { 1144 .storage = STORAGE_BOOL, 1145 .size = 1, 1146 .align = 1, 1147 }, 1148 builtin_type_char = { 1149 .storage = STORAGE_CHAR, 1150 .size = 1, 1151 .align = 1, 1152 }, 1153 builtin_type_error = { 1154 .storage = STORAGE_ERROR, 1155 .size = 1, 1156 .align = 1, 1157 }, 1158 builtin_type_f32 = { 1159 .storage = STORAGE_F32, 1160 .size = 4, 1161 .align = 4, 1162 }, 1163 builtin_type_f64 = { 1164 .storage = STORAGE_F64, 1165 .size = 8, 1166 .align = 8, 1167 }, 1168 builtin_type_i8 = { 1169 .storage = STORAGE_I8, 1170 .size = 1, 1171 .align = 1, 1172 }, 1173 builtin_type_i16 = { 1174 .storage = STORAGE_I16, 1175 .size = 2, 1176 .align = 2, 1177 }, 1178 builtin_type_i32 = { 1179 .storage = STORAGE_I32, 1180 .size = 4, 1181 .align = 4, 1182 }, 1183 builtin_type_i64 = { 1184 .storage = STORAGE_I64, 1185 .size = 8, 1186 .align = 8, 1187 }, 1188 builtin_type_int = { 1189 .storage = STORAGE_INT, 1190 }, 1191 builtin_type_u8 = { 1192 .storage = STORAGE_U8, 1193 .size = 1, 1194 .align = 1, 1195 }, 1196 builtin_type_u16 = { 1197 .storage = STORAGE_U16, 1198 .size = 2, 1199 .align = 2, 1200 }, 1201 builtin_type_u32 = { 1202 .storage = STORAGE_U32, 1203 .size = 4, 1204 .align = 4, 1205 }, 1206 builtin_type_u64 = { 1207 .storage = STORAGE_U64, 1208 .size = 8, 1209 .align = 8, 1210 }, 1211 builtin_type_uint = { 1212 .storage = STORAGE_UINT, 1213 }, 1214 builtin_type_uintptr = { 1215 .storage = STORAGE_UINTPTR, 1216 }, 1217 builtin_type_null = { 1218 .storage = STORAGE_NULL, 1219 }, 1220 builtin_type_rune = { 1221 .storage = STORAGE_RUNE, 1222 .size = 4, 1223 .align = 4, 1224 }, 1225 builtin_type_size = { 1226 .storage = STORAGE_SIZE, 1227 }, 1228 builtin_type_void = { 1229 .storage = STORAGE_VOID, 1230 .size = 0, 1231 .align = 0, 1232 }, 1233 builtin_type_const_bool = { 1234 .storage = STORAGE_BOOL, 1235 .flags = TYPE_CONST, 1236 .size = 1, 1237 .align = 1, 1238 }, 1239 builtin_type_const_char = { 1240 .storage = STORAGE_CHAR, 1241 .flags = TYPE_CONST, 1242 .size = 1, 1243 .align = 1, 1244 }, 1245 builtin_type_const_f32 = { 1246 .storage = STORAGE_F32, 1247 .flags = TYPE_CONST, 1248 .size = 4, 1249 .align = 4, 1250 }, 1251 builtin_type_const_f64 = { 1252 .storage = STORAGE_F64, 1253 .flags = TYPE_CONST, 1254 .size = 8, 1255 .align = 8, 1256 }, 1257 builtin_type_const_i8 = { 1258 .storage = STORAGE_I8, 1259 .flags = TYPE_CONST, 1260 .size = 1, 1261 .align = 1, 1262 }, 1263 builtin_type_const_i16 = { 1264 .storage = STORAGE_I16, 1265 .flags = TYPE_CONST, 1266 .size = 2, 1267 .align = 2, 1268 }, 1269 builtin_type_const_i32 = { 1270 .storage = STORAGE_I32, 1271 .flags = TYPE_CONST, 1272 .size = 4, 1273 .align = 4, 1274 }, 1275 builtin_type_const_i64 = { 1276 .storage = STORAGE_I64, 1277 .flags = TYPE_CONST, 1278 .size = 8, 1279 .align = 8, 1280 }, 1281 builtin_type_const_int = { 1282 .storage = STORAGE_INT, 1283 .flags = TYPE_CONST, 1284 }, 1285 builtin_type_const_u8 = { 1286 .storage = STORAGE_U8, 1287 .flags = TYPE_CONST, 1288 .size = 1, 1289 .align = 1, 1290 }, 1291 builtin_type_const_u16 = { 1292 .storage = STORAGE_U16, 1293 .flags = TYPE_CONST, 1294 .size = 2, 1295 .align = 2, 1296 }, 1297 builtin_type_const_u32 = { 1298 .storage = STORAGE_U32, 1299 .flags = TYPE_CONST, 1300 .size = 4, 1301 .align = 4, 1302 }, 1303 builtin_type_const_u64 = { 1304 .storage = STORAGE_U64, 1305 .flags = TYPE_CONST, 1306 .size = 8, 1307 .align = 8, 1308 }, 1309 builtin_type_const_uint = { 1310 .storage = STORAGE_UINT, 1311 .flags = TYPE_CONST, 1312 }, 1313 builtin_type_const_uintptr = { 1314 .storage = STORAGE_UINTPTR, 1315 .flags = TYPE_CONST, 1316 }, 1317 builtin_type_const_rune = { 1318 .storage = STORAGE_RUNE, 1319 .flags = TYPE_CONST, 1320 .size = 4, 1321 .align = 4, 1322 }, 1323 builtin_type_const_size = { 1324 .storage = STORAGE_SIZE, 1325 .flags = TYPE_CONST, 1326 }, 1327 builtin_type_const_void = { 1328 .storage = STORAGE_VOID, 1329 .flags = TYPE_CONST, 1330 .size = 0, 1331 .align = 0, 1332 }; 1333 1334 // Others 1335 struct type builtin_type_ptr_const_char = { 1336 .storage = STORAGE_POINTER, 1337 .pointer = { 1338 .referent = &builtin_type_const_char, 1339 }, 1340 }, 1341 builtin_type_str = { 1342 .storage = STORAGE_STRING, 1343 }, 1344 builtin_type_const_str = { 1345 .storage = STORAGE_STRING, 1346 .flags = TYPE_CONST, 1347 }, 1348 builtin_type_valist = { 1349 .storage = STORAGE_VALIST, 1350 };