types.c - tomo

(848 lines)
   1 // Logic for handling type_t types
   2 
   3 #include <limits.h>
   4 #include <math.h>
   5 #include <signal.h>
   6 #include <stdint.h>
   7 #include <sys/param.h>
   8 
   9 #include "environment.h"
  10 #include "stdlib/integers.h"
  11 #include "stdlib/tables.h"
  12 #include "stdlib/text.h"
  13 #include "stdlib/util.h"
  14 #include "types.h"
  15 
  16 Text_t arg_types_to_text(arg_t *args, const char *separator) {
  17     Text_t text = EMPTY_TEXT;
  18     for (arg_t *arg = args; arg; arg = arg->next) {
  19         text = Texts(text, type_to_text(arg->type));
  20         if (arg->next) text = Texts(text, separator);
  21     }
  22     return text;
  23 }
  24 
  25 Text_t type_to_text(type_t *t) {
  26     if (!t) return Text("(Unknown type)");
  27 
  28     switch (t->tag) {
  29     case UnknownType: return Text("???");
  30     case AbortType: return Text("Abort");
  31     case ReturnType: {
  32         type_t *ret = Match(t, ReturnType)->ret;
  33         return Texts("Return(", ret ? type_to_text(ret) : Text("Void"), ")");
  34     }
  35     case VoidType: return Text("Void");
  36     case MemoryType: return Text("Memory");
  37     case BoolType: return Text("Bool");
  38     case ByteType: return Text("Byte");
  39     case CStringType: return Text("CString");
  40     case PathType: return Text("Path");
  41     case TextType: return Match(t, TextType)->lang ? Text$from_str(Match(t, TextType)->lang) : Text("Text");
  42     case BigIntType: return Text("Int");
  43     case IntType: return Texts("Int", (int32_t)Match(t, IntType)->bits);
  44     case NumType: return Match(t, NumType)->bits == TYPE_NBITS32 ? Text("Num32") : Text("Num");
  45     case ListType: {
  46         DeclareMatch(list, t, ListType);
  47         return Texts("[", type_to_text(list->item_type), "]");
  48     }
  49     case TableType: {
  50         DeclareMatch(table, t, TableType);
  51         return (table->value_type && table->value_type != PRESENT_TYPE)
  52                    ? Texts("{", type_to_text(table->key_type), ":", type_to_text(table->value_type), "}")
  53                    : Texts("{", type_to_text(table->key_type), "}");
  54     }
  55     case ClosureType: {
  56         return type_to_text(Match(t, ClosureType)->fn);
  57     }
  58     case FunctionType: {
  59         DeclareMatch(fn, t, FunctionType);
  60         Text_t text = Texts("func(", arg_types_to_text(fn->args, ","));
  61         if (fn->ret && fn->ret->tag != VoidType) text = Texts(text, fn->args ? " -> " : "-> ", type_to_text(fn->ret));
  62         text = Texts(text, ")");
  63         return text;
  64     }
  65     case StructType: {
  66         DeclareMatch(struct_, t, StructType);
  67         return Text$replace(Text$from_str(struct_->name), Text("$"), Text("."));
  68     }
  69     case PointerType: {
  70         DeclareMatch(ptr, t, PointerType);
  71         Text_t sigil = ptr->is_stack ? Text("&") : Text("@");
  72         return Texts(sigil, type_to_text(ptr->pointed));
  73     }
  74     case EnumType: {
  75         DeclareMatch(enum_, t, EnumType);
  76         if (enum_->name != NULL && strncmp(enum_->name, "enum$", strlen("enum$")) != 0)
  77             return Text$replace(Text$from_str(enum_->name), Text("$"), Text("."));
  78         Text_t text = Text("enum(");
  79         for (tag_t *tag = enum_->tags; tag; tag = tag->next) {
  80             text = Texts(text, Text$from_str(tag->name));
  81             if (tag->type && Match(tag->type, StructType)->fields) {
  82                 text = Texts(text, "(");
  83                 for (arg_t *field = Match(tag->type, StructType)->fields; field; field = field->next) {
  84                     text = Texts(text, Text$from_str(field->name), ":", type_to_text(field->type));
  85                     if (field->next) text = Texts(text, ", ");
  86                 }
  87                 text = Texts(text, ")");
  88             }
  89             if (tag->next) text = Texts(text, ", ");
  90         }
  91         return Texts(text, ")");
  92     }
  93     case OptionalType: {
  94         type_t *opt = Match(t, OptionalType)->type;
  95         if (opt) return Texts(type_to_text(opt), "?");
  96         else return Text("(Unknown optional type)");
  97     }
  98     case TypeInfoType: {
  99         return Texts("Type$info(", Match(t, TypeInfoType)->name, ")");
 100     }
 101     case ModuleType: {
 102         return Texts("Module(", Match(t, ModuleType)->name, ")");
 103     }
 104     default: {
 105         raise(SIGABRT);
 106         return Texts("Unknown type: ", (int32_t)t->tag);
 107     }
 108     }
 109 }
 110 
 111 PUREFUNC const char *get_type_name(type_t *t) {
 112     switch (t->tag) {
 113     case TextType: return Match(t, TextType)->lang;
 114     case StructType: return Match(t, StructType)->name;
 115     case EnumType: return Match(t, EnumType)->name;
 116     default: return NULL;
 117     }
 118 }
 119 
 120 bool type_eq(type_t *a, type_t *b) {
 121     if (a == b) return true;
 122     if (!a && !b) return true;
 123     if (!a || !b) return false;
 124     if (a->tag != b->tag) return false;
 125     return Text$equal_values(type_to_text(a), type_to_text(b));
 126 }
 127 
 128 bool type_is_a(type_t *t, type_t *req) {
 129     if (type_eq(t, req)) return true;
 130     if (req->tag == OptionalType && Match(req, OptionalType)->type) return type_is_a(t, Match(req, OptionalType)->type);
 131     if (t->tag == PointerType && req->tag == PointerType) {
 132         DeclareMatch(t_ptr, t, PointerType);
 133         DeclareMatch(req_ptr, req, PointerType);
 134         if (type_eq(t_ptr->pointed, req_ptr->pointed))
 135             return (!t_ptr->is_stack && req_ptr->is_stack) || (!t_ptr->is_stack);
 136     }
 137     return false;
 138 }
 139 
 140 type_t *non_optional(type_t *t) {
 141     return t->tag == OptionalType ? Match(t, OptionalType)->type : t;
 142 }
 143 
 144 PUREFUNC type_t *value_type(type_t *t) {
 145     while (t->tag == PointerType)
 146         t = Match(t, PointerType)->pointed;
 147     return t;
 148 }
 149 
 150 PUREFUNC bool is_discardable_type(type_t *t) {
 151     if (t->tag == StructType) {
 152         return (Match(t, StructType)->fields == NULL);
 153     }
 154     return (t->tag == VoidType || t->tag == AbortType || t->tag == ReturnType);
 155 }
 156 
 157 type_t *type_or_type(type_t *a, type_t *b) {
 158     if (!a) return b;
 159     if (!b) return a;
 160     if (a->tag == OptionalType && !Match(a, OptionalType)->type)
 161         return b->tag == OptionalType ? b : Type(OptionalType, b);
 162     if (b->tag == OptionalType && !Match(b, OptionalType)->type)
 163         return a->tag == OptionalType ? a : Type(OptionalType, a);
 164     if (a->tag == ReturnType && b->tag == ReturnType)
 165         return Type(ReturnType, .ret = type_or_type(Match(a, ReturnType)->ret, Match(b, ReturnType)->ret));
 166     if ((a->tag == VoidType && is_discardable_type(b)) || (is_discardable_type(a) && b->tag == VoidType))
 167         return Type(VoidType);
 168 
 169     if (is_incomplete_type(a) && type_eq(b, most_complete_type(a, b))) return b;
 170     if (is_incomplete_type(b) && type_eq(a, most_complete_type(a, b))) return a;
 171 
 172     if (type_is_a(b, a)) return a;
 173     if (type_is_a(a, b)) return b;
 174     if (a->tag == AbortType || a->tag == ReturnType) return non_optional(b);
 175     if (b->tag == AbortType || b->tag == ReturnType) return non_optional(a);
 176     if ((a->tag == IntType || a->tag == NumType) && (b->tag == IntType || b->tag == NumType)) {
 177         switch (compare_precision(a, b)) {
 178         case NUM_PRECISION_EQUAL:
 179         case NUM_PRECISION_MORE: return a;
 180         case NUM_PRECISION_LESS: return b;
 181         default: return NULL;
 182         }
 183         return NULL;
 184     }
 185     return NULL;
 186 }
 187 
 188 static PUREFUNC INLINE double type_min_magnitude(type_t *t) {
 189     switch (t->tag) {
 190     case BoolType: return (double)false;
 191     case ByteType: return 0;
 192     case BigIntType: return -1. / 0.;
 193     case IntType: {
 194         switch (Match(t, IntType)->bits) {
 195         case TYPE_IBITS8: return (double)INT8_MIN;
 196         case TYPE_IBITS16: return (double)INT16_MIN;
 197         case TYPE_IBITS32: return (double)INT32_MIN;
 198         case TYPE_IBITS64: return (double)INT64_MIN;
 199         default: errx(1, "Invalid integer bit size");
 200         }
 201     }
 202     case NumType: return -1. / 0.;
 203     default: return (double)NAN;
 204     }
 205 }
 206 
 207 static PUREFUNC INLINE double type_max_magnitude(type_t *t) {
 208     switch (t->tag) {
 209     case BoolType: return (double)true;
 210     case ByteType: return (double)UINT8_MAX;
 211     case BigIntType: return 1. / 0.;
 212     case IntType: {
 213         switch (Match(t, IntType)->bits) {
 214         case TYPE_IBITS8: return (double)INT8_MAX;
 215         case TYPE_IBITS16: return (double)INT16_MAX;
 216         case TYPE_IBITS32: return (double)INT32_MAX;
 217         case TYPE_IBITS64: return (double)INT64_MAX;
 218         default: errx(1, "Invalid integer bit size");
 219         }
 220     }
 221     case NumType: return 1. / 0.;
 222     default: return (double)NAN;
 223     }
 224 }
 225 
 226 PUREFUNC precision_cmp_e compare_precision(type_t *a, type_t *b) {
 227     if (a == NULL || b == NULL) return NUM_PRECISION_INCOMPARABLE;
 228 
 229     if (is_int_type(a) && b->tag == NumType) return NUM_PRECISION_LESS;
 230     else if (a->tag == NumType && is_int_type(b)) return NUM_PRECISION_MORE;
 231 
 232     double a_min = type_min_magnitude(a), b_min = type_min_magnitude(b), a_max = type_max_magnitude(a),
 233            b_max = type_max_magnitude(b);
 234 
 235     if (isnan(a_min) || isnan(b_min) || isnan(a_max) || isnan(b_max)) return NUM_PRECISION_INCOMPARABLE;
 236     else if (a_min == b_min && a_max == b_max) return NUM_PRECISION_EQUAL;
 237     else if (a_min <= b_min && b_max <= a_max) return NUM_PRECISION_MORE;
 238     else if (b_min <= a_min && a_max <= b_max) return NUM_PRECISION_LESS;
 239     else return NUM_PRECISION_INCOMPARABLE;
 240 }
 241 
 242 bool _has_heap_memory(type_t *t, Table_t *visited) {
 243     if (!t) return false;
 244     Text_t type_text = type_to_text(t);
 245     if (Table$get(*visited, &type_text, Set$info(&Text$info))) return false;
 246     Table$set(visited, &type_text, NULL, Set$info(&Text$info));
 247 
 248     switch (t->tag) {
 249     case ListType: return true;
 250     case TableType: return true;
 251     case PointerType: return true;
 252     case OptionalType: return _has_heap_memory(Match(t, OptionalType)->type, visited);
 253     case BigIntType: return true;
 254     case StructType: {
 255         for (arg_t *field = Match(t, StructType)->fields; field; field = field->next) {
 256             if (_has_heap_memory(field->type, visited)) return true;
 257         }
 258         return false;
 259     }
 260     case EnumType: {
 261         for (tag_t *tag = Match(t, EnumType)->tags; tag; tag = tag->next) {
 262             if (tag->type && _has_heap_memory(tag->type, visited)) return true;
 263         }
 264         return false;
 265     }
 266     default: return false;
 267     }
 268 }
 269 
 270 bool has_heap_memory(type_t *t) {
 271     Table_t visited = EMPTY_TABLE;
 272     return _has_heap_memory(t, &visited);
 273 }
 274 
 275 bool _has_refcounts(type_t *t, Table_t *visited) {
 276     if (!t) return false;
 277     Text_t type_text = type_to_text(t);
 278     if (Table$get(*visited, &type_text, Set$info(&Text$info))) return false;
 279     Table$set(visited, &type_text, NULL, Set$info(&Text$info));
 280 
 281     switch (t->tag) {
 282     case ListType: return true;
 283     case TableType: return true;
 284     case OptionalType: return _has_refcounts(Match(t, OptionalType)->type, visited);
 285     case StructType: {
 286         for (arg_t *field = Match(t, StructType)->fields; field; field = field->next) {
 287             if (_has_refcounts(field->type, visited)) return true;
 288         }
 289         return false;
 290     }
 291     case EnumType: {
 292         for (tag_t *tag = Match(t, EnumType)->tags; tag; tag = tag->next) {
 293             if (tag->type && _has_refcounts(tag->type, visited)) return true;
 294         }
 295         return false;
 296     }
 297     default: return false;
 298     }
 299 }
 300 
 301 bool has_refcounts(type_t *t) {
 302     Table_t visited = EMPTY_TABLE;
 303     return _has_refcounts(t, &visited);
 304 }
 305 
 306 bool _has_stack_memory(type_t *t, Table_t *visited) {
 307     if (!t) return false;
 308     Text_t type_text = type_to_text(t);
 309     if (Table$get(*visited, &type_text, Set$info(&Text$info))) return false;
 310     Table$set(visited, &type_text, NULL, Set$info(&Text$info));
 311 
 312     switch (t->tag) {
 313     case PointerType: return Match(t, PointerType)->is_stack;
 314     case OptionalType: return _has_stack_memory(Match(t, OptionalType)->type, visited);
 315     case ListType: return _has_stack_memory(Match(t, ListType)->item_type, visited);
 316     case TableType:
 317         return _has_stack_memory(Match(t, TableType)->key_type, visited)
 318                || _has_stack_memory(Match(t, TableType)->value_type, visited);
 319     case StructType: {
 320         for (arg_t *field = Match(t, StructType)->fields; field; field = field->next) {
 321             if (_has_stack_memory(field->type, visited)) return true;
 322         }
 323         return false;
 324     }
 325     case EnumType: {
 326         for (tag_t *tag = Match(t, EnumType)->tags; tag; tag = tag->next) {
 327             if (tag->type && _has_stack_memory(tag->type, visited)) return true;
 328         }
 329         return false;
 330     }
 331     default: return false;
 332     }
 333 }
 334 
 335 bool has_stack_memory(type_t *t) {
 336     Table_t visited = EMPTY_TABLE;
 337     return _has_stack_memory(t, &visited);
 338 }
 339 
 340 PUREFUNC const char *enum_single_value_tag(type_t *enum_type, type_t *t) {
 341     const char *found = NULL;
 342     for (tag_t *tag = Match(enum_type, EnumType)->tags; tag; tag = tag->next) {
 343         if (tag->type->tag != StructType) continue;
 344         DeclareMatch(s, tag->type, StructType);
 345         if (!s->fields || s->fields->next || !s->fields->type) continue;
 346 
 347         if (can_promote(t, s->fields->type)) {
 348             if (found) // Ambiguous case, multiple matches
 349                 return NULL;
 350             found = tag->name;
 351             // Continue searching to check for ambiguous cases
 352         }
 353     }
 354     return found;
 355 }
 356 
 357 PUREFUNC bool can_promote(type_t *actual, type_t *needed) {
 358     if (!actual || !needed) return false;
 359 
 360     // No promotion necessary:
 361     if (type_eq(actual, needed)) return true;
 362 
 363     // Serialization/deserialization
 364     if (type_eq(actual, Type(ListType, Type(ByteType))) || type_eq(needed, Type(ListType, Type(ByteType)))) return true;
 365 
 366     if (actual->tag == NumType && needed->tag == IntType) return false;
 367 
 368     if (actual->tag == IntType && (needed->tag == NumType || needed->tag == BigIntType)) return true;
 369 
 370     if (actual->tag == BigIntType && needed->tag == NumType) return true;
 371 
 372     if (actual->tag == IntType && needed->tag == IntType) {
 373         precision_cmp_e cmp = compare_precision(actual, needed);
 374         return cmp == NUM_PRECISION_EQUAL || cmp == NUM_PRECISION_LESS;
 375     }
 376 
 377     if (needed->tag == EnumType) return (enum_single_value_tag(needed, actual) != NULL);
 378 
 379     // Text to C String
 380     if (actual->tag == TextType && !Match(actual, TextType)->lang && needed->tag == CStringType) return true;
 381 
 382     // Automatic dereferencing:
 383     if (actual->tag == PointerType && can_promote(Match(actual, PointerType)->pointed, needed)) return true;
 384 
 385     if (actual->tag == OptionalType) {
 386         if (needed->tag == BoolType) return true;
 387 
 388         // Ambiguous `none` to concrete optional
 389         if (Match(actual, OptionalType)->type == NULL) return (needed->tag == OptionalType);
 390 
 391         // Optional num -> num
 392         if (needed->tag == NumType && actual->tag == OptionalType && Match(actual, OptionalType)->type->tag == NumType)
 393             return can_promote(Match(actual, OptionalType)->type, needed);
 394     }
 395 
 396     // Optional promotion:
 397     if (needed->tag == OptionalType && Match(needed, OptionalType)->type != NULL
 398         && can_promote(actual, Match(needed, OptionalType)->type))
 399         return true;
 400 
 401     if (needed->tag == PointerType && actual->tag == PointerType) {
 402         DeclareMatch(needed_ptr, needed, PointerType);
 403         DeclareMatch(actual_ptr, actual, PointerType);
 404 
 405         if (actual_ptr->is_stack && !needed_ptr->is_stack)
 406             // Can't use &x for a function that wants a @Foo or ?Foo
 407             return false;
 408 
 409         if (needed_ptr->pointed->tag == TableType && actual_ptr->pointed->tag == TableType)
 410             return can_promote(actual_ptr->pointed, needed_ptr->pointed);
 411         else if (needed_ptr->pointed->tag != MemoryType && !type_eq(needed_ptr->pointed, actual_ptr->pointed))
 412             // Can't use @Foo for a function that wants @Baz
 413             // But you *can* use @Foo for a function that wants @Memory
 414             return false;
 415         else return true;
 416     }
 417 
 418     // Empty literals:
 419     if (actual->tag == ListType && needed->tag == ListType && Match(actual, ListType)->item_type == NULL)
 420         return true; // [] -> [T]
 421     if (actual->tag == TableType && needed->tag == TableType && Match(actual, TableType)->key_type == NULL
 422         && Match(actual, TableType)->value_type == NULL)
 423         return true; // {} -> {K:V}
 424 
 425     // Cross-promotion between tables with default values and without
 426     if (needed->tag == TableType && actual->tag == TableType) {
 427         DeclareMatch(actual_table, actual, TableType);
 428         DeclareMatch(needed_table, needed, TableType);
 429         if (type_eq(needed_table->key_type, actual_table->key_type)
 430             && type_eq(needed_table->value_type, actual_table->value_type))
 431             return true;
 432     }
 433 
 434     if (actual->tag == FunctionType && needed->tag == ClosureType)
 435         return can_promote(actual, Match(needed, ClosureType)->fn);
 436 
 437     if (actual->tag == ClosureType && needed->tag == ClosureType)
 438         return can_promote(Match(actual, ClosureType)->fn, Match(needed, ClosureType)->fn);
 439 
 440     if (actual->tag == FunctionType && needed->tag == FunctionType) {
 441         for (arg_t *actual_arg = Match(actual, FunctionType)->args, *needed_arg = Match(needed, FunctionType)->args;
 442              actual_arg || needed_arg; actual_arg = actual_arg->next, needed_arg = needed_arg->next) {
 443             if (!actual_arg || !needed_arg) return false;
 444             if (type_eq(actual_arg->type, needed_arg->type)) continue;
 445             if (actual_arg->type->tag == PointerType && needed_arg->type->tag == PointerType
 446                 && can_promote(actual_arg->type, needed_arg->type))
 447                 continue;
 448             return false;
 449         }
 450         type_t *actual_ret = Match(actual, FunctionType)->ret;
 451         if (!actual_ret) actual_ret = Type(VoidType);
 452         type_t *needed_ret = Match(needed, FunctionType)->ret;
 453         if (!needed_ret) needed_ret = Type(VoidType);
 454 
 455         return ((type_eq(actual_ret, needed_ret))
 456                 || (actual_ret->tag == PointerType && needed_ret->tag == PointerType
 457                     && can_promote(actual_ret, needed_ret)));
 458     }
 459 
 460     return false;
 461 }
 462 
 463 PUREFUNC bool is_int_type(type_t *t) {
 464     return t->tag == IntType || t->tag == BigIntType || t->tag == ByteType;
 465 }
 466 
 467 PUREFUNC bool is_numeric_type(type_t *t) {
 468     return t->tag == IntType || t->tag == BigIntType || t->tag == NumType || t->tag == ByteType;
 469 }
 470 
 471 PUREFUNC bool is_packed_data(type_t *t) {
 472     if (t->tag == IntType || t->tag == NumType || t->tag == ByteType || t->tag == PointerType || t->tag == BoolType
 473         || t->tag == FunctionType) {
 474         return true;
 475     } else if (t->tag == StructType) {
 476         size_t offset = 0;
 477         for (arg_t *field = Match(t, StructType)->fields; field; field = field->next) {
 478             if (!is_packed_data(field->type)) return false;
 479             size_t align = type_align(field->type);
 480             if (align > 0 && offset % align != 0) return false;
 481             offset += type_size(field->type);
 482         }
 483         size_t overall_align = type_align(t);
 484         return overall_align == 0 || (offset % overall_align == 0);
 485     } else if (t->tag == EnumType) {
 486         size_t offset = sizeof(int32_t);
 487         for (tag_t *tag = Match(t, EnumType)->tags; tag; tag = tag->next) {
 488             if (!is_packed_data(tag->type)) return false;
 489             size_t align = type_align(tag->type);
 490             if (align > 0 && offset % align != 0) return false;
 491             offset += type_size(tag->type);
 492         }
 493         size_t overall_align = type_align(t);
 494         return overall_align == 0 || (offset % overall_align == 0);
 495     } else {
 496         return false;
 497     }
 498 }
 499 
 500 PUREFUNC size_t unpadded_struct_size(type_t *t) {
 501     if (Match(t, StructType)->opaque)
 502         compiler_err(NULL, NULL, NULL, "The struct type %s is opaque, so I can't get the size of it",
 503                      Match(t, StructType)->name);
 504     arg_t *fields = Match(t, StructType)->fields;
 505     size_t size = 0;
 506     size_t bit_offset = 0;
 507     for (arg_t *field = fields; field; field = field->next) {
 508         type_t *field_type = field->type;
 509         if (field_type->tag == BoolType) {
 510             bit_offset += 1;
 511             if (bit_offset >= 8) {
 512                 size += 1;
 513                 bit_offset = 0;
 514             }
 515         } else {
 516             if (bit_offset > 0) {
 517                 size += 1;
 518                 bit_offset = 0;
 519             }
 520             size_t align = type_align(field_type);
 521             if (align > 1 && size % align > 0) size += align - (size % align); // Padding
 522             size += type_size(field_type);
 523         }
 524     }
 525     if (bit_offset > 0) {
 526         size += 1;
 527     }
 528     return size;
 529 }
 530 
 531 PUREFUNC size_t type_size(type_t *t) {
 532 #ifdef __GNUC__
 533 #pragma GCC diagnostic push
 534 #pragma GCC diagnostic ignored "-Wswitch-default"
 535 #endif
 536     switch (t->tag) {
 537     case UnknownType:
 538     case AbortType:
 539     case ReturnType:
 540     case VoidType: return 0;
 541     case MemoryType: errx(1, "Memory has undefined type size");
 542     case BoolType: return sizeof(bool);
 543     case ByteType: return sizeof(uint8_t);
 544     case CStringType: return sizeof(char *);
 545     case PathType: return sizeof(Path_t);
 546     case BigIntType: return sizeof(Int_t);
 547     case IntType: {
 548         switch (Match(t, IntType)->bits) {
 549         case TYPE_IBITS64: return sizeof(int64_t);
 550         case TYPE_IBITS32: return sizeof(int32_t);
 551         case TYPE_IBITS16: return sizeof(int16_t);
 552         case TYPE_IBITS8: return sizeof(int8_t);
 553         default: errx(1, "Invalid integer bit size");
 554         }
 555     }
 556     case NumType: return Match(t, NumType)->bits == TYPE_NBITS64 ? sizeof(double) : sizeof(float);
 557     case TextType: return sizeof(Text_t);
 558     case ListType: return sizeof(List_t);
 559     case TableType: return sizeof(Table_t);
 560     case FunctionType: return sizeof(void *);
 561     case ClosureType: return sizeof(struct { void *fn, *userdata; });
 562     case PointerType: return sizeof(void *);
 563     case OptionalType: {
 564         type_t *nonnull = Match(t, OptionalType)->type;
 565         switch (nonnull->tag) {
 566         case IntType:
 567             switch (Match(nonnull, IntType)->bits) {
 568             case TYPE_IBITS64: return sizeof(OptionalInt64_t);
 569             case TYPE_IBITS32: return sizeof(OptionalInt32_t);
 570             case TYPE_IBITS16: return sizeof(OptionalInt16_t);
 571             case TYPE_IBITS8: return sizeof(OptionalInt8_t);
 572             default: errx(1, "Invalid integer bit size");
 573             }
 574         case StructType: {
 575             arg_t *fields = new (arg_t, .name = "value", .type = nonnull,
 576                                  .next = new (arg_t, .name = "has_value", .type = Type(BoolType)));
 577             return type_size(Type(StructType, .fields = fields));
 578         }
 579         default: return type_size(nonnull);
 580         }
 581     }
 582     case StructType: {
 583         if (Match(t, StructType)->opaque)
 584             compiler_err(NULL, NULL, NULL, "The struct type %s is opaque, so I can't get the size of it",
 585                          Match(t, StructType)->name);
 586         size_t size = unpadded_struct_size(t);
 587         size_t align = type_align(t);
 588         if (size > 0 && align > 0 && (size % align) > 0) size = (size + align) - (size % align);
 589         return size;
 590     }
 591     case EnumType: {
 592         size_t max_align = 0;
 593         size_t max_size = 0;
 594         for (tag_t *tag = Match(t, EnumType)->tags; tag; tag = tag->next) {
 595             size_t align = type_align(tag->type);
 596             if (align > max_align) max_align = align;
 597             size_t size = type_size(tag->type);
 598             if (size > max_size) max_size = size;
 599         }
 600         size_t size = sizeof(UnknownType); // generic enum
 601         if (max_align > 1 && size % max_align > 0) // Padding before first union field
 602             size += max_align - (size % max_align);
 603         size += max_size;
 604         size_t align = MAX(__alignof__(UnknownType), max_align);
 605         if (size % align > 0) // Padding after union
 606             size += align - (size % align);
 607         return size;
 608     }
 609     case TypeInfoType: return sizeof(TypeInfo_t);
 610     case ModuleType: return 0;
 611     }
 612 #ifdef __GNUC__
 613 #pragma GCC diagnostic pop
 614 #endif
 615     errx(1, "This should not be reachable");
 616     return 0;
 617 }
 618 
 619 PUREFUNC size_t type_align(type_t *t) {
 620 #ifdef __GNUC__
 621 #pragma GCC diagnostic push
 622 #pragma GCC diagnostic ignored "-Wswitch-default"
 623 #endif
 624     switch (t->tag) {
 625     case UnknownType:
 626     case AbortType:
 627     case ReturnType:
 628     case VoidType: return 0;
 629     case MemoryType: errx(1, "Memory has undefined type alignment");
 630     case BoolType: return __alignof__(bool);
 631     case ByteType: return __alignof__(uint8_t);
 632     case CStringType: return __alignof__(char *);
 633     case PathType: return __alignof__(Path_t);
 634     case BigIntType: return __alignof__(Int_t);
 635     case IntType: {
 636         switch (Match(t, IntType)->bits) {
 637         case TYPE_IBITS64: return __alignof__(int64_t);
 638         case TYPE_IBITS32: return __alignof__(int32_t);
 639         case TYPE_IBITS16: return __alignof__(int16_t);
 640         case TYPE_IBITS8: return __alignof__(int8_t);
 641         default: return 0;
 642         }
 643     }
 644     case NumType: return Match(t, NumType)->bits == TYPE_NBITS64 ? __alignof__(double) : __alignof__(float);
 645     case TextType: return __alignof__(Text_t);
 646     case ListType: return __alignof__(List_t);
 647     case TableType: return __alignof__(Table_t);
 648     case FunctionType: return __alignof__(void *);
 649     case ClosureType: return __alignof__(struct { void *fn, *userdata; });
 650     case PointerType: return __alignof__(void *);
 651     case OptionalType: {
 652         type_t *nonnull = Match(t, OptionalType)->type;
 653         switch (nonnull->tag) {
 654         case IntType:
 655             switch (Match(nonnull, IntType)->bits) {
 656             case TYPE_IBITS64: return __alignof__(OptionalInt64_t);
 657             case TYPE_IBITS32: return __alignof__(OptionalInt32_t);
 658             case TYPE_IBITS16: return __alignof__(OptionalInt16_t);
 659             case TYPE_IBITS8: return __alignof__(OptionalInt8_t);
 660             default: errx(1, "Invalid integer bit size");
 661             }
 662         case StructType: return MAX(1, type_align(nonnull));
 663         default: return type_align(nonnull);
 664         }
 665     }
 666     case StructType: {
 667         if (Match(t, StructType)->opaque)
 668             compiler_err(NULL, NULL, NULL, "The struct type %s is opaque, so I can't get the alignment of it",
 669                          Match(t, StructType)->name);
 670         arg_t *fields = Match(t, StructType)->fields;
 671         size_t align = t->tag == StructType ? 0 : sizeof(void *);
 672         for (arg_t *field = fields; field; field = field->next) {
 673             size_t field_align = type_align(field->type);
 674             if (field_align > align) align = field_align;
 675         }
 676         return align;
 677     }
 678     case EnumType: {
 679         size_t align = __alignof__(UnknownType);
 680         for (tag_t *tag = Match(t, EnumType)->tags; tag; tag = tag->next) {
 681             size_t tag_align = type_align(tag->type);
 682             if (tag_align > align) align = tag_align;
 683         }
 684         return align;
 685     }
 686     case TypeInfoType: return __alignof__(TypeInfo_t);
 687     case ModuleType: return 0;
 688     }
 689 #ifdef __GNUC__
 690 #pragma GCC diagnostic pop
 691 #endif
 692     errx(1, "This should not be reachable");
 693     return 0;
 694 }
 695 
 696 type_t *get_field_type(type_t *t, const char *field_name) {
 697     t = value_type(t);
 698     switch (t->tag) {
 699     case PointerType: return get_field_type(Match(t, PointerType)->pointed, field_name);
 700     case TextType: {
 701         if (Match(t, TextType)->lang && streq(field_name, "text")) return TEXT_TYPE;
 702         else if (streq(field_name, "length")) return INT_TYPE;
 703         return NULL;
 704     }
 705     case StructType: {
 706         DeclareMatch(struct_t, t, StructType);
 707         for (arg_t *field = struct_t->fields; field; field = field->next) {
 708             if (streq(field->name, field_name)) return field->type;
 709         }
 710         return NULL;
 711     }
 712     case EnumType: {
 713         DeclareMatch(e, t, EnumType);
 714         for (tag_t *tag = e->tags; tag; tag = tag->next) {
 715             if (!streq(field_name, tag->name)) continue;
 716             return Type(OptionalType, tag->type);
 717         }
 718         return NULL;
 719     }
 720     case TableType: {
 721         if (streq(field_name, "length")) return INT_TYPE;
 722         else if (streq(field_name, "keys")) return Type(ListType, Match(t, TableType)->key_type);
 723         else if (streq(field_name, "values")) return Type(ListType, Match(t, TableType)->value_type);
 724         else if (streq(field_name, "fallback")) return Type(OptionalType, .type = t);
 725         return NULL;
 726     }
 727     case ListType: {
 728         if (streq(field_name, "length")) return INT_TYPE;
 729         return NULL;
 730     }
 731     default: return NULL;
 732     }
 733 }
 734 
 735 PUREFUNC type_t *get_iterated_type(type_t *t) {
 736     type_t *iter_value_t = value_type(t);
 737     switch (iter_value_t->tag) {
 738     case BigIntType:
 739     case IntType: return iter_value_t; break;
 740     case ListType: return Match(iter_value_t, ListType)->item_type; break;
 741     case TableType: return NULL;
 742     case FunctionType:
 743     case ClosureType: {
 744         // Iterator function
 745         __typeof(iter_value_t->__data.FunctionType) *fn =
 746             iter_value_t->tag == ClosureType ? Match(Match(iter_value_t, ClosureType)->fn, FunctionType)
 747                                              : Match(iter_value_t, FunctionType);
 748         if (fn->args || fn->ret->tag != OptionalType) return NULL;
 749         return Match(fn->ret, OptionalType)->type;
 750     }
 751     default: return NULL;
 752     }
 753 }
 754 
 755 CONSTFUNC bool is_incomplete_type(type_t *t) {
 756     if (t == NULL) return true;
 757     switch (t->tag) {
 758     case ReturnType: return is_incomplete_type(Match(t, ReturnType)->ret);
 759     case OptionalType: return is_incomplete_type(Match(t, OptionalType)->type);
 760     case ListType: return is_incomplete_type(Match(t, ListType)->item_type);
 761     case TableType: {
 762         DeclareMatch(table, t, TableType);
 763         return is_incomplete_type(table->key_type) || is_incomplete_type(table->value_type);
 764     }
 765     case FunctionType: {
 766         DeclareMatch(fn, t, FunctionType);
 767         for (arg_t *arg = fn->args; arg; arg = arg->next) {
 768             if (arg->type == NULL || is_incomplete_type(arg->type)) return true;
 769         }
 770         return fn->ret ? is_incomplete_type(fn->ret) : false;
 771     }
 772     case ClosureType: return is_incomplete_type(Match(t, ClosureType)->fn);
 773     case PointerType: return is_incomplete_type(Match(t, PointerType)->pointed);
 774     default: return false;
 775     }
 776 }
 777 
 778 CONSTFUNC type_t *most_complete_type(type_t *t1, type_t *t2) {
 779     if (!t1) return t2;
 780     if (!t2) return t1;
 781 
 782     if (is_incomplete_type(t1) && is_incomplete_type(t2)) return NULL;
 783     else if (!is_incomplete_type(t1) && !is_incomplete_type(t2) && type_eq(t1, t2)) return t1;
 784 
 785     if (t1->tag != t2->tag) return NULL;
 786 
 787     switch (t1->tag) {
 788     case ReturnType: {
 789         type_t *ret = most_complete_type(Match(t1, ReturnType)->ret, Match(t1, ReturnType)->ret);
 790         return ret ? Type(ReturnType, ret) : NULL;
 791     }
 792     case OptionalType: {
 793         type_t *opt = most_complete_type(Match(t1, OptionalType)->type, Match(t2, OptionalType)->type);
 794         return opt ? Type(OptionalType, opt) : NULL;
 795     }
 796     case ListType: {
 797         type_t *item = most_complete_type(Match(t1, ListType)->item_type, Match(t2, ListType)->item_type);
 798         return item ? Type(ListType, item) : NULL;
 799     }
 800     case TableType: {
 801         DeclareMatch(table1, t1, TableType);
 802         DeclareMatch(table2, t2, TableType);
 803         ast_t *default_value = table1->default_value ? table1->default_value : table2->default_value;
 804         type_t *key = most_complete_type(table1->key_type, table2->key_type);
 805         type_t *value = most_complete_type(table1->value_type, table2->value_type);
 806         return (key && value) ? Type(TableType, key, value, table1->env, default_value) : NULL;
 807     }
 808     case FunctionType: {
 809         DeclareMatch(fn1, t1, FunctionType);
 810         DeclareMatch(fn2, t2, FunctionType);
 811         arg_t *args = NULL;
 812         for (arg_t *arg1 = fn1->args, *arg2 = fn2->args; arg1 || arg2; arg1 = arg1->next, arg2 = arg2->next) {
 813             if (!arg1 || !arg2) return NULL;
 814 
 815             type_t *arg_type = most_complete_type(arg1->type, arg2->type);
 816             if (!arg_type) return NULL;
 817             args = new (arg_t, .type = arg_type, .next = args);
 818         }
 819         REVERSE_LIST(args);
 820         type_t *ret = most_complete_type(fn1->ret, fn2->ret);
 821         return ret ? Type(FunctionType, .args = args, .ret = ret) : NULL;
 822     }
 823     case ClosureType: {
 824         type_t *fn = most_complete_type(Match(t1, ClosureType)->fn, Match(t1, ClosureType)->fn);
 825         return fn ? Type(ClosureType, fn) : NULL;
 826     }
 827     case PointerType: {
 828         DeclareMatch(ptr1, t1, PointerType);
 829         DeclareMatch(ptr2, t2, PointerType);
 830         if (ptr1->is_stack != ptr2->is_stack) return NULL;
 831         type_t *pointed = most_complete_type(ptr1->pointed, ptr2->pointed);
 832         return pointed ? Type(PointerType, .is_stack = ptr1->is_stack, .pointed = pointed) : NULL;
 833     }
 834     default: {
 835         if (is_incomplete_type(t1) || is_incomplete_type(t2)) return NULL;
 836         return type_eq(t1, t2) ? t1 : NULL;
 837     }
 838     }
 839 }
 840 
 841 type_t *_make_function_type(type_t *ret, int n, arg_t args[n]) {
 842     arg_t *arg_pointers = GC_MALLOC(sizeof(arg_t[n]));
 843     for (int i = 0; i < n; i++) {
 844         arg_pointers[i] = args[i];
 845         if (i + 1 < n) arg_pointers[i].next = &arg_pointers[i + 1];
 846     }
 847     return Type(FunctionType, .ret = ret, .args = &arg_pointers[0]);
 848 }