// Logic for getting a type from an AST node
#include <ctype.h>
#include <gc.h>
#include <glob.h>
#include <stdarg.h>
#include <string.h>

#include "ast.h"
#include "config.h"
#include "environment.h"
#include "naming.h"
#include "packages.h"
#include "parse/files.h"
#include "parse/types.h"
#include "stdlib/c_string.h"
#include "stdlib/list.h"
#include "stdlib/number.h"
#include "stdlib/path.h"
#include "stdlib/table.h"
#include "stdlib/text.h"
#include "typecheck.h"
#include "types.h"
#include "util.h"

type_t *parse_type_ast(env_t *env, type_ast_t *ast) {
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wswitch-default"
    switch (ast->tag) {
    case VarTypeAST: {
        const char *name = Match(ast, VarTypeAST)->name;
        type_t *t = Table$str_get(*env->types, name);
        if (t) return t;
        while (strchr(name, '.')) {
            char *module_name = GC_strndup(name, strcspn(name, "."));
            binding_t *b = get_binding(env, module_name);
            if (!b || b->type->tag != ModuleType)
                code_err(ast, "I don't know a module with the name '", module_name, "'");

            env_t *imported = Table$str_get(*env->imports, Match(b->type, ModuleType)->name);
            assert(imported);
            env = imported;
            name = strchr(name, '.') + 1;
            t = Table$str_get(*env->types, name);
            if (t) return t;
        }
        code_err(ast, "I don't know a type with the name '", name, "'");
    }
    case PointerTypeAST: {
        DeclareMatch(ptr, ast, PointerTypeAST);
        type_t *pointed_t = parse_type_ast(env, ptr->pointed);
        if (pointed_t->tag == VoidType)
            code_err(ast, "Void pointers are not supported. You probably meant 'Memory' instead of 'Void'");
        return Type(PointerType, .pointed = pointed_t, .is_stack = ptr->is_stack);
    }
    case ListTypeAST: {
        type_ast_t *item_type = Match(ast, ListTypeAST)->item;
        type_t *item_t = parse_type_ast(env, item_type);
        if (!item_t) code_err(item_type, "I can't figure out what this type is.");
        if (has_stack_memory(item_t))
            code_err(item_type, "Lists can't have stack references because the list may outlive the stack frame.");
        if (type_size(item_t) > LIST_MAX_STRIDE)
            code_err(ast, "This list holds items that take up ", (uint64_t)type_size(item_t),
                     " bytes, but the maximum supported size is ", (int64_t)LIST_MAX_STRIDE,
                     " bytes. Consider using a list of pointers instead.");
        return Type(ListType, .item_type = item_t);
    }
    case TableTypeAST: {
        DeclareMatch(table_type, ast, TableTypeAST);
        type_ast_t *key_type_ast = table_type->key;
        type_t *key_type = parse_type_ast(env, key_type_ast);
        if (!key_type) code_err(key_type_ast, "I can't figure out what type this is.");
        if (has_stack_memory(key_type))
            code_err(key_type_ast, "Tables can't have stack references because the list may outlive the stack frame.");

        type_t *val_type = table_type->value ? parse_type_ast(env, table_type->value) : PRESENT_TYPE;
        if (!val_type) code_err(ast, "I can't figure out what the value type for this entry is.");

        if (table_type->value && has_stack_memory(val_type))
            code_err(table_type->value,
                     "Tables can't have stack references because the list may outlive the stack frame.");
        else if (table_type->value && val_type->tag == OptionalType)
            code_err(ast, "Tables with optional-typed values are not currently supported");

        return Type(TableType, .key_type = key_type, .value_type = val_type, .env = env,
                    .default_value = table_type->default_value);
    }
    case FunctionTypeAST: {
        DeclareMatch(fn, ast, FunctionTypeAST);
        type_t *ret_t = fn->ret ? parse_type_ast(env, fn->ret) : Type(VoidType);
        if (fn->ret && has_stack_memory(ret_t))
            code_err(fn->ret, "Functions are not allowed to return stack references, because the reference may no "
                              "longer exist on the stack.");
        arg_t *type_args = NULL;
        for (arg_ast_t *arg = fn->args; arg; arg = arg->next) {
            type_args = new (arg_t, .name = arg->name, .alias = arg->alias, .comment = arg->comment, .next = type_args);
            if (arg->type) type_args->type = parse_type_ast(env, arg->type);
            else if (arg->value) type_args->type = get_type(env, arg->value);

            if (arg->value) type_args->default_val = arg->value;
        }
        REVERSE_LIST(type_args);
        return Type(ClosureType, Type(FunctionType, .args = type_args, .ret = ret_t));
    }
    case OptionalTypeAST: {
        DeclareMatch(opt, ast, OptionalTypeAST);
        type_t *t = parse_type_ast(env, opt->type);
        if (t->tag == VoidType || t->tag == AbortType || t->tag == ReturnType)
            code_err(ast, "Optional ", type_to_text(t), " types are not supported.");
        else if (t->tag == OptionalType) code_err(ast, "Nested optional types are not currently supported");
        return Type(OptionalType, .type = t);
    }
    case EnumTypeAST: {
        const char *enum_name = Text$as_c_string(Match(ast, EnumTypeAST)->name);
        type_t *cached = Table$str_get(*env->types, enum_name);
        if (cached) return cached;

        tag_ast_t *tag_asts = Match(ast, EnumTypeAST)->tags;
        tag_t *tags = NULL;
        int64_t tag_value = 1;
        env_t *ns_env = namespace_env(env, enum_name);

        type_t *enum_type = Type(EnumType, .name = enum_name, .env = ns_env, .tags = NULL);

        Table$str_set(env->types, enum_name, enum_type);

        for (tag_ast_t *tag_ast = tag_asts; tag_ast; tag_ast = tag_ast->next) {
            arg_t *fields = NULL;
            for (arg_ast_t *field_ast = tag_ast->fields; field_ast; field_ast = field_ast->next) {
                type_t *field_type =
                    field_ast->type ? parse_type_ast(env, field_ast->type) : get_type(env, field_ast->value);
                fields = new (arg_t, .name = field_ast->name, .type = field_type, .default_val = field_ast->value,
                              .alias = field_ast->alias, .comment = field_ast->comment, .next = fields);
            }
            REVERSE_LIST(fields);
            const char *struct_name = String(enum_name, "$", tag_ast->name);
            env_t *struct_env = namespace_env(env, struct_name);
            type_t *tag_type = Type(StructType, .name = tag_ast->name, .fields = fields,
                                    .packed_bools = tag_ast->packed_bools, .env = struct_env);
            tags = new (tag_t, .name = tag_ast->name, .tag_value = tag_value, .type = tag_type, .next = tags);

            if (Match(tag_type, StructType)->fields) { // Constructor:
                type_t *constructor_t =
                    Type(FunctionType, .args = Match(tag_type, StructType)->fields, .ret = enum_type);
                Text_t tagged_name = namespace_name(env, env->namespace, Texts(enum_name, "$tagged$", tag_ast->name));
                set_variant_constructor_binding(ns_env, tag_ast->name, constructor_t, tagged_name);
                binding_t binding = {.type = constructor_t, .code = tagged_name};
                List$insert(&ns_env->namespace->constructors, &binding, I(1), sizeof(binding));
            } else { // Empty singleton value:
                Text_t code =
                    Texts("((", namespace_name(env, env->namespace, Texts(enum_name, "$$type")), "){",
                          namespace_name(env, env->namespace, Texts(enum_name, "$tag$", tag_ast->name)), "})");
                set_binding(ns_env, tag_ast->name, enum_type, code);
            }
            Table$str_set(env->types, String(enum_name, "$", tag_ast->name), tag_type);

            tag_value += 1;
        }
        REVERSE_LIST(tags);
        enum_type->__data.EnumType.tags = tags;
        return enum_type;
    }
    case UnknownTypeAST: code_err(ast, "I don't know how to get this type");
    }
#pragma clang diagnostic pop
    errx(1, "Unreachable");
    return NULL;
}

PUREFUNC type_t *get_math_type(env_t *env, ast_t *ast, type_t *lhs_t, type_t *rhs_t) {
    (void)env;
    switch (compare_precision(lhs_t, rhs_t)) {
    case NUM_PRECISION_EQUAL:
    case NUM_PRECISION_MORE: return lhs_t;
    case NUM_PRECISION_LESS: return rhs_t;
    default:
        code_err(ast, "Math operations between ", type_to_text(lhs_t), " and ", type_to_text(rhs_t),
                 " are not supported");
    }
    return NULL;
}

static env_t *load_module(env_t *env, ast_t *use_ast) {
    DeclareMatch(use, use_ast, Use);
    switch (use->what) {
    case USE_LOCAL: {
        Path_t source_path = Path$from_str(use_ast->file->filename);
        OptionalPath_t source_dir = Path$parent(source_path);
        assert(source_dir); // A source file always has a directory
        Path_t used_path = Path$resolved(Path$from_str(use->path), source_dir);

        if (!Path$exists(used_path)) code_err(use_ast, "No such file exists: ", quoted(use->path));

        env_t *module_env = Table$str_get(*env->imports, String(used_path));
        if (module_env) return module_env;

        ast_t *ast = parse_file(String(used_path), NULL);
        if (!ast) print_err("Could not compile file ", used_path);
        return load_module_env(env, ast);
    }
    case USE_PACKAGE: {
        OptionalPath_t installed = find_installed_package(env->build_info, use_ast);
        assert(installed);
        // Register under the name the `use` statement refers to it by, the
        // same name FieldAccess looks up (ModuleType->name). The install
        // directory's basename doesn't work as a key: digest-pinned packages
        // install into a directory named after their digest.
        const char *name = Match(use_ast, Use)->path;
        env_t *module_env = fresh_scope(env);
        Table$str_set(env->imports, name, module_env);
        OptionalList_t children = Path$glob(installed, Text("[!._0-9]*.tm"));
        if (children.data == NULL) print_err("Could not read the installed package directory: ", installed);
        for (int64_t i = 0; i < (int64_t)children.length; i++) {
            Path_t child = *(Path_t *)(children.data + i * children.stride);
            ast_t *ast = parse_file(child, NULL);
            if (!ast) print_err("Could not compile file ", child);
            env_t *module_file_env = fresh_scope(module_env);
            module_file_env->namespace = NULL;
            env_t *subenv = load_module_env(module_file_env, ast);
            for (int64_t j = 0; j < (int64_t)subenv->locals->entries.length; j++) {
                struct {
                    const char *name;
                    binding_t *binding;
                } *entry = subenv->locals->entries.data + j * subenv->locals->entries.stride;
                Table$str_set(module_env->locals, entry->name, entry->binding);
            }
            for (int64_t j = 0; j < (int64_t)subenv->types->entries.length; j++) {
                struct {
                    const char *name;
                    type_t *type;
                } *entry = subenv->types->entries.data + j * subenv->types->entries.stride;
                Table$str_set(module_env->types, entry->name, entry->type);
            }
        }
        return module_env;
    }
    default: return NULL;
    }
}

void prebind_statement(env_t *env, ast_t *statement) {
    switch (statement->tag) {
    case DebugLog: {
        for (ast_list_t *value = Match(statement, DebugLog)->values; value; value = value->next)
            prebind_statement(env, value->ast);
        break;
    }
    case Assert: {
        prebind_statement(env, Match(statement, Assert)->expr);
        break;
    }
    case StructDef: {
        DeclareMatch(def, statement, StructDef);
        if (get_binding(env, def->name))
            code_err(statement, "A ", type_to_text(get_binding(env, def->name)->type), " called ", quoted(def->name),
                     " has already been defined");

        if (def->packed_bools && def->external)
            code_err(statement, "This struct is `external`, so its layout comes from C and I can't pack its "
                                "booleans");

        env_t *ns_env = namespace_env(env, def->name);
        type_t *type = Type(StructType, .name = def->name, .opaque = true, .external = def->external,
                            .packed_bools = def->packed_bools, .env = ns_env); // placeholder
        Table$str_set(env->types, def->name, type);
        set_binding(env, def->name, Type(TypeInfoType, .name = def->name, .type = type, .env = ns_env),
                    namespace_name(env, env->namespace, Texts(def->name, "$$info")));
        for (ast_list_t *stmt = def->namespace ? Match(def->namespace, Block)->statements : NULL; stmt;
             stmt = stmt->next)
            prebind_statement(ns_env, stmt->ast);
        break;
    }
    case EnumDef: {
        DeclareMatch(def, statement, EnumDef);
        if (get_binding(env, def->name))
            code_err(statement, "A ", type_to_text(get_binding(env, def->name)->type), " called ", quoted(def->name),
                     " has already been defined");

        env_t *ns_env = namespace_env(env, def->name);
        type_t *type = Type(EnumType, .name = def->name, .opaque = true, .env = ns_env); // placeholder
        Table$str_set(env->types, def->name, type);
        set_binding(env, def->name, Type(TypeInfoType, .name = def->name, .type = type, .env = ns_env),
                    namespace_name(env, env->namespace, Texts(def->name, "$$info")));
        for (ast_list_t *stmt = def->namespace ? Match(def->namespace, Block)->statements : NULL; stmt;
             stmt = stmt->next)
            prebind_statement(ns_env, stmt->ast);
        break;
    }
    case LangDef: {
        DeclareMatch(def, statement, LangDef);
        if (get_binding(env, def->name))
            code_err(statement, "A ", type_to_text(get_binding(env, def->name)->type), " called ", quoted(def->name),
                     " has already been defined");

        env_t *ns_env = namespace_env(env, def->name);
        type_t *type = Type(TextType, .lang = def->name, .env = ns_env);
        Table$str_set(env->types, def->name, type);
        set_binding(env, def->name, Type(TypeInfoType, .name = def->name, .type = type, .env = ns_env),
                    namespace_name(env, env->namespace, Texts(def->name, "$$info")));
        for (ast_list_t *stmt = def->namespace ? Match(def->namespace, Block)->statements : NULL; stmt;
             stmt = stmt->next)
            prebind_statement(ns_env, stmt->ast);
        break;
    }
    default: break;
    }
}

void bind_statement(env_t *env, ast_t *statement) {
    switch (statement->tag) {
    case DebugLog: {
        for (ast_list_t *value = Match(statement, DebugLog)->values; value; value = value->next)
            bind_statement(env, value->ast);
        break;
    }
    case Assert: {
        bind_statement(env, Match(statement, Assert)->expr);
        break;
    }
    case Declare: {
        DeclareMatch(decl, statement, Declare);
        const char *name = Match(decl->var, Var)->name;
        if (streq(name, "_")) // Explicit discard
            return;
        if (get_binding(env, name))
            code_err(decl->var, "A ", type_to_text(get_binding(env, name)->type), " called ", quoted(name),
                     " has already been defined");
        if (decl->value) bind_statement(env, decl->value);
        type_t *type = decl->type ? parse_type_ast(env, decl->type) : get_type(env, decl->value);
        if (!type) code_err(statement, "I couldn't figure out the type of this value");
        // A table literal with a default whose declared type has none would
        // silently drop the default (making indexing optional). Reject it and
        // point at the type-annotation form instead. Unwrap any `&`/`@` around
        // the value, and the pointer around the declared type.
        if (decl->type && decl->value) {
            ast_t *tbl_val = decl->value;
            if (tbl_val->tag == HeapAllocate) tbl_val = Match(tbl_val, HeapAllocate)->value;
            else if (tbl_val->tag == StackReference) tbl_val = Match(tbl_val, StackReference)->value;
            type_t *tbl_type = value_type(type);
            if (tbl_val->tag == Table && Match(tbl_val, Table)->default_value && tbl_type->tag == TableType
                && Match(tbl_type, TableType)->default_value == NULL)
                code_err(tbl_val, "This table has a default value, but the type it's declared as (", type_to_text(type),
                         ") doesn't. Move the default into the type annotation instead, like `{K:V; default=...}`.");
        }
        if (type->tag == FunctionType) type = Type(ClosureType, type);
        // For top-level variables, some can only be initialized at runtime, so we need to ensure that the
        // initialization has actually happened using the check_initialized() macro.
        Text_t code;
        if (env->namespace || decl->top_level) {
            code = namespace_name(env, env->namespace, Text$from_str(name));
            if (needs_runtime_initialization(env, statement, NULL)) {
                Text_t initialized = namespace_name(env, env->namespace, Texts(name, "$$initialized"));
                code = Texts("check_initialized(", code, ", ", initialized, ", \"", name, "\")");
            }
        } else {
            code = Texts("_$", name);
        }
        set_binding(env, name, type, code);
        break;
    }
    case FunctionDef: {
        DeclareMatch(def, statement, FunctionDef);
        const char *name = Match(def->name, Var)->name;
        if (strchr(name, '.') && env->namespace)
            code_err(statement, "Subcommand functions like `func ", name,
                     "(...)` can only be defined at the top level of a file");

        if (get_binding(env, name))
            code_err(def->name, "A ", type_to_text(get_binding(env, name)->type), " called ", quoted(name),
                     " has already been defined");

        type_t *type = get_function_type(env, statement);
        // Dots in subcommand names (`main.add`) become `$`s in the C name:
        Text_t c_name = Text$replace(Text$from_str(name), Text("."), Text("$"));
        Table$str_set(
            env->locals, name,
            new (binding_t, .type = type, .code = namespace_name(env, env->namespace, c_name), .fn_def = statement));
        break;
    }
    case ConvertDef: {
        type_t *type = get_function_type(env, statement);
        type_t *ret_t = Match(type, FunctionType)->ret;
        const char *name = get_type_name(ret_t);
        if (!name)
            code_err(statement, "Conversions are only supported for text, struct, and enum types, not ",
                     type_to_text(ret_t));

        Text_t code =
            namespace_name(env, env->namespace, Texts(name, "$", get_line_number(statement->file, statement->start)));
        binding_t binding = {.type = type, .code = code};
        env_t *type_ns = get_namespace_by_type(env, ret_t);
        List$insert(&type_ns->namespace->constructors, &binding, I(0), sizeof(binding));
        break;
    }
    case StructDef: {
        DeclareMatch(def, statement, StructDef);
        env_t *ns_env = namespace_env(env, def->name);
        type_t *type = Table$str_get(*env->types, def->name);
        if (!type) code_err(statement, "Couldn't find type!");
        assert(type);
        ns_env->current_type = type;
        if (!def->opaque) {
            arg_t *fields = NULL;
            for (arg_ast_t *field_ast = def->fields; field_ast; field_ast = field_ast->next) {
                type_t *field_t = get_arg_ast_type(env, field_ast);
                type_t *non_opt_field_t = field_t->tag == OptionalType ? Match(field_t, OptionalType)->type : field_t;
                if ((non_opt_field_t->tag == StructType && Match(non_opt_field_t, StructType)->opaque)
                    || (non_opt_field_t->tag == EnumType && Match(non_opt_field_t, EnumType)->opaque)) {

                    file_t *file = NULL;
                    const char *start = NULL, *end = NULL;
                    if (field_ast->type) {
                        file = field_ast->type->file, start = field_ast->type->start, end = field_ast->type->end;
                    } else if (field_ast->value) {
                        file = field_ast->value->file, start = field_ast->value->start, end = field_ast->value->end;
                    }
                    if (non_opt_field_t == type)
                        compiler_err(file, start, end,
                                     "This is a recursive struct that would be infinitely large. Maybe you meant to "
                                     "use an optional '@",
                                     type_to_text(type), "?' pointer instead?");
                    else if (non_opt_field_t->tag == StructType && Match(non_opt_field_t, StructType)->external)
                        compiler_err(
                            file, start, end,
                            "This is an opaque externally defined struct.\n"
                            "I can't use it as a member without knowing what its fields are.\n"
                            "Either specify its fields and remove the `opaque` qualifier, or use something like a @",
                            type_to_text(non_opt_field_t), " pointer.");
                    else
                        compiler_err(file, start, end, "I'm still in the process of defining the fields of ",
                                     type_to_text(field_t),
                                     ", so I don't know how to use it as a member."
                                     "\nTry using a @",
                                     type_to_text(field_t), " pointer for this field.");
                }
                fields = new (arg_t, .name = field_ast->name, .alias = field_ast->alias, .type = field_t,
                              .comment = field_ast->comment, .default_val = field_ast->value, .next = fields);
            }
            REVERSE_LIST(fields);
            type->__data.StructType.fields = fields; // populate placeholder
            type->__data.StructType.opaque = false;
        }

        for (ast_list_t *stmt = def->namespace ? Match(def->namespace, Block)->statements : NULL; stmt;
             stmt = stmt->next)
            bind_statement(ns_env, stmt->ast);
        break;
    }
    case EnumDef: {
        DeclareMatch(def, statement, EnumDef);
        env_t *ns_env = namespace_env(env, def->name);
        type_t *type = Table$str_get(*env->types, def->name);
        assert(type);
        ns_env->current_type = type;
        tag_t *tags = NULL;
        int64_t next_tag = 1;
        for (tag_ast_t *tag_ast = def->tags; tag_ast; tag_ast = tag_ast->next) {
            arg_t *fields = NULL;
            for (arg_ast_t *field_ast = tag_ast->fields; field_ast; field_ast = field_ast->next) {
                type_t *field_t = get_arg_ast_type(env, field_ast);
                type_t *non_opt_field_t = field_t->tag == OptionalType ? Match(field_t, OptionalType)->type : field_t;
                if ((non_opt_field_t->tag == StructType && Match(non_opt_field_t, StructType)->opaque)
                    || (non_opt_field_t->tag == EnumType && Match(non_opt_field_t, EnumType)->opaque)) {
                    file_t *file = NULL;
                    const char *start = NULL, *end = NULL;
                    if (field_ast->type) {
                        file = field_ast->type->file, start = field_ast->type->start, end = field_ast->type->end;
                    } else if (field_ast->value) {
                        file = field_ast->value->file, start = field_ast->value->start, end = field_ast->value->end;
                    }
                    if (non_opt_field_t == type)
                        compiler_err(file, start, end,
                                     "This is a recursive enum that would be infinitely large. Maybe you meant to use "
                                     "an optional '@",
                                     type_to_text(type), "?' pointer instead?");
                    else if (non_opt_field_t->tag == StructType && Match(non_opt_field_t, StructType)->external)
                        compiler_err(
                            file, start, end,
                            "This is an opaque externally defined struct.\n"
                            "I can't use it as a member without knowing what its fields are.\n"
                            "Either specify its fields and remove the `opaque` qualifier, or use something like a @",
                            type_to_text(non_opt_field_t), " pointer.");
                    else
                        compiler_err(file, start, end, "I'm still in the process of defining the fields of ",
                                     type_to_text(field_t),
                                     ", so I don't know how to use it as a member."
                                     "\nTry using a @",
                                     type_to_text(field_t), " pointer for this field.");
                }
                fields = new (arg_t, .name = field_ast->name, .alias = field_ast->alias, .type = field_t,
                              .comment = field_ast->comment, .default_val = field_ast->value, .next = fields);
            }
            REVERSE_LIST(fields);
            env_t *member_ns = namespace_env(env, String(def->name, "$", tag_ast->name));
            type_t *tag_type = Type(StructType, .name = String(def->name, "$", tag_ast->name), .fields = fields,
                                    .packed_bools = tag_ast->packed_bools, .env = member_ns);
            tags = new (tag_t, .name = tag_ast->name, .tag_value = (next_tag++), .type = tag_type, .next = tags);
        }
        REVERSE_LIST(tags);
        type->__data.EnumType.tags = tags;
        type->__data.EnumType.opaque = false;

        for (tag_t *tag = tags; tag; tag = tag->next) {
            if (Match(tag->type, StructType)->fields) { // Constructor:
                type_t *constructor_t = Type(FunctionType, .args = Match(tag->type, StructType)->fields, .ret = type);
                Text_t tagged_name = namespace_name(env, env->namespace, Texts(def->name, "$tagged$", tag->name));
                set_variant_constructor_binding(ns_env, tag->name, constructor_t, tagged_name);
                binding_t binding = {.type = constructor_t, .code = tagged_name};
                List$insert(&ns_env->namespace->constructors, &binding, I(1), sizeof(binding));
            } else { // Empty singleton value:
                Text_t code = Texts("((", namespace_name(env, env->namespace, Texts(def->name, "$$type")), "){",
                                    namespace_name(env, env->namespace, Texts(def->name, "$tag$", tag->name)), "})");
                set_binding(ns_env, tag->name, type, code);
            }
            Table$str_set(env->types, String(def->name, "$", tag->name), tag->type);
        }

        for (ast_list_t *stmt = def->namespace ? Match(def->namespace, Block)->statements : NULL; stmt;
             stmt = stmt->next) {
            bind_statement(ns_env, stmt->ast);
        }
        break;
    }
    case LangDef: {
        DeclareMatch(def, statement, LangDef);
        env_t *ns_env = namespace_env(env, def->name);
        type_t *type = Type(TextType, .lang = def->name, .env = ns_env);
        ns_env->current_type = type;
        Table$str_set(env->types, def->name, type);

        set_binding(ns_env, "from_text", NewFunctionType(type, {.name = "text", .type = TEXT_TYPE}),
                    Texts("(", namespace_name(env, env->namespace, Texts(def->name, "$$type")), ")"));

        for (ast_list_t *stmt = def->namespace ? Match(def->namespace, Block)->statements : NULL; stmt;
             stmt = stmt->next)
            bind_statement(ns_env, stmt->ast);
        break;
    }
    case Use: {
        env_t *module_env = load_module(env, statement);
        if (!module_env) break;
        ast_t *var = Match(statement, Use)->var;
        if (var) {
            type_t *type = get_type(env, statement);
            assert(type);
            set_binding(env, Match(var, Var)->name, type, EMPTY_TEXT);
        } else {
            for (Table_t *bindings = module_env->locals; bindings != module_env->globals;
                 bindings = bindings->fallback) {
                List_t entries = bindings->entries;
                for (int64_t i = 0; i < (int64_t)entries.length; i++) {
                    struct {
                        const char *name;
                        binding_t *binding;
                    } *entry = entries.data + entries.stride * i;
                    if (entry->name[0] == '_' || streq(entry->name, "main")) continue;
                    binding_t *b = Table$str_get(*env->locals, entry->name);
                    if (!b) Table$str_set(env->locals, entry->name, entry->binding);
                    else if (b != entry->binding)
                        code_err(statement, "This module imports a symbol called '", entry->name,
                                 "', which would clobber another variable");
                }
            }
            for (int64_t i = 0; i < (int64_t)module_env->types->entries.length; i++) {
                struct {
                    const char *name;
                    type_t *type;
                } *entry = module_env->types->entries.data + module_env->types->entries.stride * i;
                if (entry->name[0] == '_') continue;
                if (Table$str_get(*env->types, entry->name)) continue;

                Table$str_set(env->types, entry->name, entry->type);
            }
        }
        break;
    }
    default: break;
    }
}

type_t *get_function_type(env_t *env, ast_t *ast) {
    arg_ast_t *arg_asts;
    type_ast_t *ret_ast;
    switch (ast->tag) {
    case FunctionDef:
        arg_asts = Match(ast, FunctionDef)->args;
        ret_ast = Match(ast, FunctionDef)->ret_type;
        break;
    case ConvertDef:
        arg_asts = Match(ast, ConvertDef)->args;
        ret_ast = Match(ast, ConvertDef)->ret_type;
        break;
    case Lambda:
        arg_asts = Match(ast, Lambda)->args;
        ret_ast = Match(ast, Lambda)->ret_type;
        break;
    default: code_err(ast, "This was expected to be a function definition of some sort");
    }
    arg_t *args = NULL;
    env_t *scope = fresh_scope(env);
    for (arg_ast_t *arg = arg_asts; arg; arg = arg->next) {
        type_t *t = arg->type ? parse_type_ast(env, arg->type) : get_type(env, arg->value);
        args = new (arg_t, .name = arg->name, .alias = arg->alias, .comment = arg->comment, .type = t,
                    .default_val = arg->value, .next = args);
        set_binding(scope, arg->name, t, EMPTY_TEXT);
    }
    REVERSE_LIST(args);

    if (ast->tag == Lambda) {
        ast_t *body = Match(ast, Lambda)->body;

        scope->fn = NULL;
        type_t *ret_t = get_type(scope, body);
        if (ret_t->tag == ReturnType) ret_t = Match(ret_t, ReturnType)->ret;
        if (ret_t->tag == AbortType) ret_t = Type(VoidType);

        if (ret_t->tag == OptionalType && !Match(ret_t, OptionalType)->type)
            code_err(body, "This function doesn't return a specific optional type");

        if (ret_ast) {
            type_t *declared = parse_type_ast(env, ret_ast);
            if (can_promote(ret_t, declared)) ret_t = declared;
            else
                code_err(ast, "This function was declared to return a value of type ", type_to_text(declared),
                         ", but actually returns a value of type ", type_to_text(ret_t));
        }

        if (has_stack_memory(ret_t))
            code_err(ast, "Functions can't return stack references because the reference may outlive its stack frame.");
        return Type(ClosureType, Type(FunctionType, .args = args, .ret = ret_t));
    } else {
        type_t *ret_t = ret_ast ? parse_type_ast(scope, ret_ast) : Type(VoidType);
        if (has_stack_memory(ret_t))
            code_err(ast, "Functions can't return stack references because the reference may outlive its stack frame.");
        return Type(FunctionType, .args = args, .ret = ret_t);
    }
}

type_t *get_function_return_type(env_t *env, ast_t *ast) {
    type_t *fn_t = get_function_type(env, ast);
    if (fn_t->tag == ClosureType) fn_t = Match(fn_t, ClosureType)->fn;
    return Match(fn_t, FunctionType)->ret;
}

type_t *get_method_type(env_t *env, ast_t *self, const char *name) {
    binding_t *b = get_namespace_binding(env, self, name);
    if (!b || !b->type) {
        OptionalText_t suggestion = suggest_best_name(name, get_method_names(env, get_type(env, self)));
        code_err(self, "No such method: ", type_to_text(get_type(env, self)), ".", name, "(...)", suggestion);
    }
    return b->type;
}

// The name a record literal's type expression refers to: `Foo{...}` -> "Foo",
// `Baz.A{...}` -> "A".
PUREFUNC public const char *record_literal_name(ast_t *type_expr) {
    if (type_expr->tag == Var) return Match(type_expr, Var)->name;
    else if (type_expr->tag == FieldAccess) return Match(type_expr, FieldAccess)->field;
    else return NULL;
}

// Enum variants aren't type infos: each one is bound in the enum's namespace as
// a generated constructor function returning the enum. `type_expr` (a Var like
// `A` or a FieldAccess like `Baz.A`) names a variant iff it resolves to a
// binding explicitly marked as one. Matching by name and return type alone
// would also catch an unrelated user function that happens to share a tag's
// name and return type (e.g. a smart constructor `func A(x:Int -> Baz)`).
PUREFUNC public binding_t *get_variant_constructor(env_t *env, ast_t *type_expr) {
    binding_t *b;
    if (type_expr->tag == Var) b = get_binding(env, Match(type_expr, Var)->name);
    else if (type_expr->tag == FieldAccess) {
        if (get_subcommand_binding(env, type_expr)) return NULL; // `main.add` is a subcommand, not a variant
        b = get_namespace_binding(env, Match(type_expr, FieldAccess)->fielded, Match(type_expr, FieldAccess)->field);
    } else return NULL;
    return (b && b->is_variant_constructor) ? b : NULL;
}

env_t *match_clause_scope(env_t *env, type_t *subject_t, match_clause_t *clause) {
    if (clause->pattern->tag == Var || subject_t->tag != EnumType) return env;

    if (clause->pattern->tag != RecordLiteral || Match(clause->pattern, RecordLiteral)->type->tag != Var)
        code_err(clause->pattern,
                 "I only support variables and variant patterns like 'case Tag{x, y}' for pattern "
                 "matching ",
                 type_to_text(subject_t), " types in a 'match' block");

    DeclareMatch(fn, clause->pattern, RecordLiteral);
    const char *tag_name = Match(fn->type, Var)->name;
    type_t *tag_type = NULL;
    tag_t *const tags = Match(subject_t, EnumType)->tags;
    for (tag_t *tag = tags; tag; tag = tag->next) {
        if (streq(tag->name, tag_name)) {
            tag_type = tag->type;
            break;
        }
    }

    if (!tag_type)
        code_err(clause->pattern, "There is no tag ", quoted(tag_name), " for the type ", type_to_text(subject_t));

    if (!fn->args) return env;

    env_t *scope = fresh_scope(env);
    DeclareMatch(tag_struct, tag_type, StructType);
    if (fn->args && !fn->args->next && tag_struct->fields && tag_struct->fields->next) {
        if (fn->args->value->tag != Var) code_err(fn->args->value, "I expected a variable here");
        set_binding(scope, Match(fn->args->value, Var)->name, tag_type, EMPTY_TEXT);
        return scope;
    }

    arg_t *field = tag_struct->fields;
    for (arg_ast_t *var = fn->args; var || field; var = var ? var->next : var) {
        if (!var)
            code_err(clause->pattern, "The field ", type_to_text(subject_t), ".", tag_name, ".", field->name,
                     " wasn't accounted for");
        if (!field) code_err(var->value, "This is one more field than ", type_to_text(subject_t), " has");
        if (var->value->tag != Var)
            code_err(var->value, "I expected this to be a plain variable so I could bind it to a value");
        if (!streq(Match(var->value, Var)->name, "_"))
            set_binding(scope, Match(var->value, Var)->name, field->type, EMPTY_TEXT);
        field = field->next;
    }
    return scope;
}

type_t *get_clause_type(env_t *env, type_t *subject_t, match_clause_t *clause) {
    env_t *scope = match_clause_scope(env, subject_t, clause);
    return get_type(scope, clause->body);
}

// A FieldAccess chain like `main.add` or `mymod.main.submodule.init` may name
// a subcommand function, which is bound under its full dotted name:
public
binding_t *get_subcommand_binding(env_t *env, ast_t *ast) {
    // Walk to the root of the chain first, without allocating: this runs for
    // every field access and method call, and nearly all of them bail out here.
    int n = 0;
    const char *outermost_field = NULL; // The field applied to the root Var
    ast_t *node = ast;
    for (; node->tag == FieldAccess; node = Match(node, FieldAccess)->fielded) {
        outermost_field = Match(node, FieldAccess)->field;
        n += 1;
    }
    if (node->tag != Var || n == 0) return NULL;
    const char *root = Match(node, Var)->name;
    env_t *lookup_env = env;
    int skip = 0; // Fields consumed by the `main` prefix itself
    if (!streq(root, "main")) {
        // Module-qualified subcommands: `mymod.main.add`
        if (n < 2 || !streq(outermost_field, "main")) return NULL;
        binding_t *rb = get_binding(env, root);
        if (!rb || rb->type->tag != ModuleType) return NULL;
        lookup_env = Table$str_get(*env->imports, Match(rb->type, ModuleType)->name);
        if (!lookup_env) return NULL;
        skip = 1;
    }
    const char **fields = GC_MALLOC(sizeof(const char *) * (size_t)n);
    int f = 0;
    for (node = ast; node->tag == FieldAccess; node = Match(node, FieldAccess)->fielded)
        fields[f++] = Match(node, FieldAccess)->field;
    const char *name = "main";
    for (f = n - 1 - skip; f >= 0; f--)
        name = String(name, ".", fields[f]);
    binding_t *b = get_binding(lookup_env, name);
    if (!b) {
        // `main.submodule` isn't a value when only `main.submodule.init` etc.
        // exist, so give a pointed error instead of a generic name-resolution one:
        const char *prefix = String(name, ".");
        for (Table_t *scope = lookup_env->locals; scope; scope = scope->fallback) {
            for (int64_t i = 0; i < (int64_t)scope->entries.length; i++) {
                struct {
                    const char *key;
                    binding_t *value;
                } *entry = (scope->entries.data + i * scope->entries.stride);
                if (strncmp(entry->key, prefix, strlen(prefix)) == 0)
                    code_err(ast, quoted(name), " is a group of subcommands, not a value. Did you mean ",
                             quoted(entry->key), "?");
            }
        }
    }
    return b;
}

// A comprehension inside a list or table literal stands in for the items it
// produces, not for a single item: its own type is the list/table type. Peel
// off any comprehension layers to reach the expression that actually yields an
// item, and advance `*scope` to the scope that expression is evaluated in (the
// one holding the loop variables). Returns `ast` unchanged if it isn't one.
static ast_t *unwrap_comprehension(env_t **scope, ast_t *ast) {
    while (ast->tag == Comprehension) {
        DeclareMatch(comp, ast, Comprehension);
        *scope = for_scope(*scope, FakeAST(For, .iters = comp->iters, .vars = comp->vars, .at = comp->at));
        ast = comp->expr;
    }
    return ast;
}

type_t *get_type(env_t *env, ast_t *ast) {
    if (!ast) return NULL;
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wswitch-default"
    switch (ast->tag) {
    case None: {
        return Type(OptionalType, .type = NULL);
    }
    case Bool: {
        return Type(BoolType);
    }
    case Int: {
        return Type(BigIntType);
    }
    case Num: {
        return Type(NumType);
    }
    case HeapAllocate: {
        type_t *pointed = get_type(env, Match(ast, HeapAllocate)->value);
        if (has_stack_memory(pointed))
            code_err(ast, "Stack references cannot be moved to the heap because they may outlive the stack frame they "
                          "were created in.");
        return Type(PointerType, .pointed = pointed);
    }
    case StackReference: {
        // Supported:
        //   &variable
        //   &struct_variable.field.(...)
        //   &struct_ptr.field.(...)
        //   &[10, 20, 30]; &{key:value}; &{10, 20, 30}
        //   &Foo(...)
        //   &(expression)
        // Not supported:
        //   &ptr[]
        //   &list[index]
        //   &table[key]
        //   &(expression).field
        //   &optional_struct_ptr.field
        ast_t *value = Match(ast, StackReference)->value;
        switch (value->tag) {
        case FieldAccess: {
            ast_t *base = value;
            while (base->tag == FieldAccess)
                base = Match(base, FieldAccess)->fielded;

            type_t *ref_type = get_type(env, value);
            type_t *base_type = get_type(env, base);
            if (base_type->tag == OptionalType) {
                code_err(base, "This value might be none, so it can't be safely dereferenced");
            } else if (base_type->tag == PointerType) {
                DeclareMatch(ptr, base_type, PointerType);
                return Type(PointerType, .pointed = ref_type, .is_stack = ptr->is_stack);
            } else if (base->tag == Var) {
                return Type(PointerType, .pointed = ref_type, .is_stack = true);
            }
            code_err(ast, "'&' stack references can only be used on the fields of pointers and local variables");
        }
        case Index: code_err(ast, "'&' stack references are not supported for list or table indexing");
        default: return Type(PointerType, .pointed = get_type(env, value), .is_stack = true);
        }
    }
    case NonOptional: {
        ast_t *value = Match(ast, NonOptional)->value;
        type_t *t = value_type(get_type(env, value));
        if (t->tag == EnumType) {
            tag_t *first_tag = Match(t, EnumType)->tags;
            if (!first_tag) code_err(ast, "'!' cannot be used on an empty enum");
            return first_tag->type;
        }
        if (t->tag != OptionalType)
            code_err(value, "This value is not optional. Only optional values can use the '!' operator.");
        return Match(t, OptionalType)->type;
    }
    case TextLiteral: return TEXT_TYPE;
    case Path: return PATH_TYPE;
    case Embed: {
        // Embedding a directory gives a table of each contained file's bytes,
        // keyed by its path relative to the embedded directory (coercible to
        // a {Path:Text} or {Path:CString} table):
        if (Path$is_directory(get_embed_path(ast), true))
            return Type(TableType, .key_type = PATH_TYPE, .value_type = Type(ListType, Type(ByteType)));
        return Type(ListType, Type(ByteType));
    }
    case TextJoin: {
        type_ast_t *lang = Match(ast, TextJoin)->lang;
        if (lang) {
            type_t *t = parse_type_ast(env, lang);
            if (!t || t->tag != TextType) {
                code_err(ast, "This is not a text type");
            }
            return t;
        } else {
            return TEXT_TYPE;
        }
    }
    case Var: {
        DeclareMatch(var, ast, Var);
        binding_t *b = get_binding(env, var->name);
        if (b) return b->type;
        List_t candidates = EMPTY_LIST;
        for (Table_t *scope = env->locals; scope; scope = scope->fallback) {
            for (int64_t i = 0; i < (int64_t)scope->entries.length; i++) {
                struct {
                    const char *key;
                    binding_t *value;
                } *entry = (scope->entries.data + i * scope->entries.stride);
                Text_t name = Text$from_str(entry->key);
                List$insert(&candidates, &name, I(0), sizeof(Text_t));
            }
        }
        OptionalText_t suggestion = suggest_best_name(var->name, candidates);
        code_err(ast, "I don't know what ", quoted(var->name), " refers to", suggestion);
    }
    case List: {
        DeclareMatch(list, ast, List);
        type_t *item_type = NULL;
        for (ast_list_t *item = list->items; item; item = item->next) {
            env_t *scope = env;
            ast_t *item_ast = unwrap_comprehension(&scope, item->ast);
            type_t *t2 = get_type(scope, item_ast);
            type_t *merged = item_type ? type_or_type(item_type, t2) : t2;
            if (!merged)
                code_err(item_ast, "This list has items of incompatible types: I can't reconcile ",
                         type_to_text(item_type), " with ", type_to_text(t2));
            item_type = merged;
        }

        if (item_type && has_stack_memory(item_type))
            code_err(ast, "Lists cannot hold stack references, because the list may outlive the stack frame the "
                          "reference was created in.");

        return Type(ListType, .item_type = item_type);
    }
    case Table: {
        DeclareMatch(table, ast, Table);
        type_t *key_type = NULL, *value_type = NULL;
        bool ambiguous_key_type = false, ambiguous_value_type = false;
        for (ast_list_t *entry = table->entries; entry; entry = entry->next) {
            env_t *scope = env;
            ast_t *entry_ast = unwrap_comprehension(&scope, entry->ast);
            DeclareMatch(e, entry_ast, TableEntry);
            type_t *key_t = get_type(scope, e->key);
            type_t *value_t = e->value ? get_type(scope, e->value) : PRESENT_TYPE;

            type_t *key_merged = key_type ? type_or_type(key_type, key_t) : key_t;
            if (!key_merged) ambiguous_key_type = true;
            key_type = key_merged;

            type_t *val_merged = value_type ? type_or_type(value_type, value_t) : value_t;
            if (!val_merged) ambiguous_value_type = true;
            value_type = val_merged;
        }

        if (ambiguous_key_type) key_type = NULL;

        if (ambiguous_value_type) value_type = NULL;

        if ((key_type && has_stack_memory(key_type)) || (value_type && has_stack_memory(value_type)))
            code_err(ast,
                     "Tables cannot hold stack references because the table may outlive the reference's stack frame.");

        return Type(TableType, .key_type = key_type, .value_type = value_type, .default_value = table->default_value,
                    .env = env);
    }
    case TableEntry: {
        code_err(ast, "Table entries should not be typechecked directly");
    }
    case Comprehension: {
        DeclareMatch(comp, ast, Comprehension);
        env_t *scope = for_scope(env, FakeAST(For, .iters = comp->iters, .vars = comp->vars, .at = comp->at));
        if (comp->expr->tag == Comprehension) {
            return get_type(scope, comp->expr);
        } else if (comp->expr->tag == TableEntry) {
            DeclareMatch(e, comp->expr, TableEntry);
            return Type(TableType, .key_type = get_type(scope, e->key),
                        .value_type = e->value ? get_type(scope, e->value) : PRESENT_TYPE);
        } else {
            return Type(ListType, .item_type = get_type(scope, comp->expr));
        }
    }
    case FieldAccess: {
        DeclareMatch(access, ast, FieldAccess);
        binding_t *subcommand = get_subcommand_binding(env, ast);
        if (subcommand) return subcommand->type;
        type_t *fielded_t = get_type(env, access->fielded);
        if (fielded_t->tag == ModuleType) {
            const char *name = Match(fielded_t, ModuleType)->name;
            env_t *module_env = Table$str_get(*env->imports, name);
            if (!module_env) code_err(access->fielded, "I couldn't find the environment for the module ", name);
            return get_type(module_env, WrapAST(ast, Var, access->field));
        } else if (fielded_t->tag == TypeInfoType) {
            DeclareMatch(info, fielded_t, TypeInfoType);
            assert(info->env);
            binding_t *b = get_binding(info->env, access->field);
            if (!b) code_err(ast, "I couldn't find the field '", access->field, "' on this type");
            return b->type;
        }
        type_t *field_t = get_field_type(fielded_t, access->field);
        if (!field_t) {
            fail_if_optional_field_access(ast, fielded_t, access->field);
            OptionalText_t suggestion = suggest_best_name(access->field, get_field_names(env, fielded_t));
            code_err(ast, type_to_text(fielded_t), " objects don't have a field called '", access->field, "'",
                     suggestion);
        }
        return field_t;
    }
    case Index: {
        DeclareMatch(indexing, ast, Index);
        type_t *indexed_t = get_type(env, indexing->indexed);
        if (indexed_t->tag == OptionalType && !indexing->index)
            code_err(ast, "You're attempting to dereference a value whose type indicates it could be none");

        if (indexed_t->tag == PointerType && !indexing->index) return Match(indexed_t, PointerType)->pointed;

        type_t *value_t = value_type(indexed_t);
        if (value_t->tag == ListType) {
            if (!indexing->index) return indexed_t;
            type_t *index_t = get_type(env, indexing->index);
            if (index_t->tag == IntType || index_t->tag == BigIntType || index_t->tag == ByteType) {
                type_t *item_type = Match(value_t, ListType)->item_type;
                return item_type->tag == OptionalType ? item_type : Type(OptionalType, item_type);
            }
            code_err(indexing->index, "I only know how to index lists using integers, not ", type_to_text(index_t));
        } else if (value_t->tag == TableType) {
            DeclareMatch(table_type, value_t, TableType);
            if (table_type->default_value) return table_type->value_type;
            return Type(OptionalType, table_type->value_type);
        } else if (value_t->tag == TextType) {
            return Type(OptionalType, value_t);
        } else {
            code_err(ast, "I don't know how to index ", type_to_text(indexed_t), " values");
        }
    }
    case FunctionCall: {
        DeclareMatch(call, ast, FunctionCall);
        type_t *fn_type_t = get_type(env, call->fn);
        if (!fn_type_t) code_err(call->fn, "I couldn't find this function");

        if (fn_type_t->tag == TypeInfoType) {
            type_t *t = Match(fn_type_t, TypeInfoType)->type;

            binding_t *constructor = get_constructor(env, t, call->args);
            // Not always `t`: a fallible constructor like Text(path) returns `t?`
            if (constructor) return Match(constructor->type, FunctionType)->ret;
            else if (t->tag == StructType)
                // Parens on a type name mean "call a constructor function"; building a
                // struct from its fields is a record literal instead.
                code_err(ast, "There's no constructor for ", type_to_text(t),
                         " that takes these arguments. If you meant to build one from its fields, use curly braces: ",
                         Match(t, StructType)->name, "{...}");
            else if (t->tag == IntType || t->tag == BigIntType || t->tag == NumType || t->tag == FloatType
                     || t->tag == ByteType || t->tag == TextType || t->tag == CStringType)
                return t; // Constructor
            arg_t *arg_types = NULL;
            for (arg_ast_t *arg = call->args; arg; arg = arg->next)
                arg_types = new (arg_t, .type = get_type(env, arg->value), .name = arg->name, .alias = arg->alias,
                                 .comment = arg->comment, .next = arg_types);
            REVERSE_LIST(arg_types);
            code_err(call->fn, "I couldn't find a type constructor for ",
                     type_to_text(Type(FunctionType, .args = arg_types, .ret = t)));
        }
        if (get_variant_constructor(env, call->fn))
            code_err(ast, "Enum variants are built with curly braces, not parentheses. Use ",
                     record_literal_name(call->fn), "{...} instead");
        if (fn_type_t->tag == ClosureType) fn_type_t = Match(fn_type_t, ClosureType)->fn;
        if (fn_type_t->tag != FunctionType)
            code_err(call->fn, "This isn't a function, it's a ", type_to_text(fn_type_t));
        DeclareMatch(fn_type, fn_type_t, FunctionType);
        return fn_type->ret;
    }
    case RecordLiteral: {
        DeclareMatch(record, ast, RecordLiteral);
        type_t *type_t_ = get_type(env, record->type);
        if (!type_t_) code_err(record->type, "I couldn't figure out what this refers to");

        binding_t *variant = get_variant_constructor(env, record->type);
        if (type_t_->tag == TypeInfoType) {
            type_t *t = Match(type_t_, TypeInfoType)->type;
            if (t->tag != StructType)
                code_err(record->type, "Curly braces build structs and enum variants, but ", type_to_text(t),
                         " is neither");
            return t;
        } else if (variant) {
            return Match(variant->type, FunctionType)->ret;
        } else if (type_t_->tag == EnumType) {
            // A variant with no fields is bound to the enum value itself:
            code_err(ast, "The variant ", record_literal_name(record->type),
                     " doesn't have any fields, so write it without curly braces");
        }
        code_err(record->type, "This isn't a struct or an enum variant, it's a ", type_to_text(type_t_));
    }
    case MethodCall: {
        DeclareMatch(call, ast, MethodCall);
        ast_t *as_field = WrapAST(call->self, FieldAccess, .fielded = call->self, .field = call->name);
        if (get_subcommand_binding(env, as_field)) // Subcommand calls: `main.add(...)`
            return get_type(env, WrapAST(ast, FunctionCall, .fn = as_field, .args = call->args));
        type_t *self_value_t = get_type(env, call->self);
        if (!self_value_t) code_err(call->self, "Couldn't get the type of this value");
        self_value_t = value_type(self_value_t);

        if (self_value_t->tag == TypeInfoType || self_value_t->tag == ModuleType) {
            return get_type(env,
                            WrapAST(ast, FunctionCall,
                                    .fn = WrapAST(call->self, FieldAccess, .fielded = call->self, .field = call->name),
                                    .args = call->args));
        }

        switch (self_value_t->tag) {
        case ListType: {
            type_t *item_type = Match(self_value_t, ListType)->item_type;
            if (streq(call->name, "binary_search")) return Type(OptionalType, INT_TYPE);
            else if (streq(call->name, "by")) return self_value_t;
            else if (streq(call->name, "clear")) return Type(VoidType);
            else if (streq(call->name, "counts")) return Type(TableType, .key_type = item_type, .value_type = INT_TYPE);
            else if (streq(call->name, "find")) return Type(OptionalType, .type = INT_TYPE);
            else if (streq(call->name, "where")) return Type(OptionalType, .type = INT_TYPE);
            else if (streq(call->name, "from")) return self_value_t;
            else if (streq(call->name, "has")) return Type(BoolType);
            else if (streq(call->name, "heap_pop")) return Type(OptionalType, .type = item_type);
            else if (streq(call->name, "heap_push")) return Type(VoidType);
            else if (streq(call->name, "heapify")) return Type(VoidType);
            else if (streq(call->name, "insert")) return Type(VoidType);
            else if (streq(call->name, "insert_all")) return Type(VoidType);
            else if (streq(call->name, "pairs"))
                // A multi-value iterator (see iterator_yield_args()) yielding
                // each unordered pair of distinct elements once (i < j):
                return Type(ClosureType,
                            .fn = Type(FunctionType,
                                       .args = new (arg_t, .name = "a",
                                                    .type = Type(PointerType, .pointed = item_type, .is_stack = true),
                                                    .next = new (arg_t, .name = "b",
                                                                 .type = Type(PointerType, .pointed = item_type,
                                                                              .is_stack = true))),
                                       .ret = Type(BoolType)));
            else if (streq(call->name, "pop")) return Type(OptionalType, .type = item_type);
            else if (streq(call->name, "random")) return Type(OptionalType, .type = item_type);
            else if (streq(call->name, "remove_at")) return Type(VoidType);
            else if (streq(call->name, "remove_item")) return Type(VoidType);
            else if (streq(call->name, "reversed")) return self_value_t;
            else if (streq(call->name, "sample")) return self_value_t;
            else if (streq(call->name, "shuffle")) return Type(VoidType);
            else if (streq(call->name, "shuffled")) return self_value_t;
            else if (streq(call->name, "slice")) return self_value_t;
            else if (streq(call->name, "sort")) return Type(VoidType);
            else if (streq(call->name, "sorted")) return self_value_t;
            else if (streq(call->name, "swap")) return Type(VoidType);
            else if (streq(call->name, "to")) return self_value_t;
            else if (streq(call->name, "unique"))
                return Type(TableType, .key_type = item_type, .value_type = PRESENT_TYPE);

            OptionalText_t suggestion = suggest_best_name(call->name, get_method_names(env, self_value_t));
            code_err(ast, "There is no '", call->name, "' method for lists", suggestion);
        }
        case TableType: {
            DeclareMatch(table, self_value_t, TableType);
            if (streq(call->name, "clear")) return Type(VoidType);
            else if (streq(call->name, "entries"))
                // A multi-value iterator (see iterator_yield_args()) yielding
                // each (key, value) pair of the table:
                return Type(
                    ClosureType,
                    .fn = Type(FunctionType,
                               .args = new (arg_t, .name = "key",
                                            .type = Type(PointerType, .pointed = table->key_type, .is_stack = true),
                                            .next = new (arg_t, .name = "value",
                                                         .type = Type(PointerType, .pointed = table->value_type,
                                                                      .is_stack = true))),
                               .ret = Type(BoolType)));
            else if (streq(call->name, "get")) return Type(OptionalType, .type = table->value_type);
            else if (streq(call->name, "get_or_set")) return table->value_type;
            else if (streq(call->name, "has")) return Type(BoolType);
            else if (streq(call->name, "remove")) return Type(VoidType);
            else if (streq(call->name, "set")) return Type(VoidType);
            else if (streq(call->name, "sorted")) return self_value_t;
            else if (streq(call->name, "with_fallback")) return self_value_t;
            else if (streq(call->name, "without")) return self_value_t;
            else if (streq(call->name, "intersection")) return self_value_t;
            else if (streq(call->name, "difference")) return self_value_t;
            else if (streq(call->name, "with")) return self_value_t;

            OptionalText_t suggestion = suggest_best_name(call->name, get_method_names(env, self_value_t));
            code_err(ast, "There is no '", call->name, "' method for ", type_to_text(self_value_t), " tables",
                     suggestion);
        }
        default: {
            if (call->name[0] == '_') {
                if (env->current_type == NULL || !type_eq(env->current_type, self_value_t))
                    code_err(ast, "You can't call private methods starting with underscore (like '", call->name,
                             "') outside of the place where the type (", type_to_text(self_value_t), ") is defined.");
            }
            type_t *field_type = get_field_type(self_value_t, call->name);
            if (field_type && field_type->tag == ClosureType) field_type = Match(field_type, ClosureType)->fn;
            if (field_type && field_type->tag == FunctionType) return Match(field_type, FunctionType)->ret;
            type_t *fn_type_t = get_method_type(env, call->self, call->name);
            if (!fn_type_t) {
                OptionalText_t suggestion = suggest_best_name(call->name, get_method_names(env, self_value_t));
                code_err(ast, "No such method!", suggestion);
            }
            if (fn_type_t->tag != FunctionType) code_err(ast, "This isn't a method, it's a ", type_to_text(fn_type_t));
            DeclareMatch(fn_type, fn_type_t, FunctionType);
            return fn_type->ret;
        }
        }
    }
    case Block: {
        DeclareMatch(block, ast, Block);
        ast_list_t *last = block->statements;
        if (!last) return Type(VoidType);
        while (last->next)
            last = last->next;

        // Early out if the type is knowable without any context from the block:
        switch (last->ast->tag) {
        case UPDATE_CASES:
        case Assign:
        case Declare:
        case FunctionDef:
        case ConvertDef:
        case StructDef:
        case EnumDef:
        case LangDef: return Type(VoidType);
        default: break;
        }

        env_t *block_env = fresh_scope(env);
        for (ast_list_t *stmt = block->statements; stmt; stmt = stmt->next) {
            prebind_statement(block_env, stmt->ast);
        }
        for (ast_list_t *stmt = block->statements; stmt; stmt = stmt->next) {
            bind_statement(block_env, stmt->ast);
            if (stmt->next) { // Check for unreachable code:
                if (stmt->ast->tag == Return)
                    code_err(
                        stmt->ast,
                        "This statement will always return, so the rest of the code in this block is unreachable!");
                type_t *statement_type = get_type(block_env, stmt->ast);
                if (statement_type && statement_type->tag == AbortType && stmt->next)
                    code_err(stmt->ast,
                             "This statement will always abort, so the rest of the code in this block is unreachable!");
            }
        }
        return get_type(block_env, last->ast);
    }
    case Declare:
    case Assign:
    case UPDATE_CASES:
    case DebugLog:
    case Test:
    case Assert: {
        return Type(VoidType);
    }
    case Use: {
        switch (Match(ast, Use)->what) {
        case USE_LOCAL: {
            Path_t source_path = Path$from_str(ast->file->filename);
            OptionalPath_t source_dir = Path$parent(source_path);
            assert(source_dir); // A source file always has a directory
            Path_t used_path = Path$resolved(Path$from_str(Match(ast, Use)->path), source_dir);
            return Type(ModuleType, Path$as_c_string(used_path));
        }
        default: return Type(ModuleType, Match(ast, Use)->path);
        }
    }
    case Return: {
        ast_t *val = Match(ast, Return)->value;
        if (env->fn) {
            // Inside a lambda, the return value is coerced into the function's explicit
            // return type if it has one, otherwise the return value's type is determined
            // from the return value.
            type_t *ret_type = NULL;
            if (env->fn->tag == Lambda) {
                type_ast_t *ret_type_ast = Match(env->fn, Lambda)->ret_type;
                if (ret_type_ast) ret_type = parse_type_ast(env, ret_type_ast);
            } else {
                ret_type = get_function_return_type(env, env->fn);
            }
            if (ret_type) env = with_enum_scope(env, ret_type);
        }
        return Type(ReturnType, .ret = (val ? get_type(env, val) : Type(VoidType)));
    }
    case Break:
    case Continue: {
        return Type(AbortType);
    }
    case Pass:
    case Defer: return Type(VoidType);
    case Negative: {
        ast_t *value = Match(ast, Negative)->value;
        type_t *t = get_type(env, value);
        if (t->tag == IntType || t->tag == FloatType) return t;

        binding_t *b = get_namespace_binding(env, value, "negative");
        if (b && b->type->tag == FunctionType) {
            DeclareMatch(fn, b->type, FunctionType);
            if (fn->args && type_eq(t, get_arg_type(env, fn->args)) && type_eq(t, fn->ret)) return t;
        }

        code_err(ast, "I don't know how to get the negative value of type ", type_to_text(t));
    }
    case Not: {
        type_t *t = get_type(env, Match(ast, Not)->value);
        if (t->tag == IntType || t->tag == ByteType || t->tag == FloatType || t->tag == BoolType) return t;
        if (t->tag == OptionalType) return Type(BoolType);

        ast_t *value = Match(ast, Not)->value;
        binding_t *b = get_namespace_binding(env, value, "negated");
        if (b && b->type->tag == FunctionType) {
            DeclareMatch(fn, b->type, FunctionType);
            if (fn->args && type_eq(t, get_arg_type(env, fn->args)) && type_eq(t, fn->ret)) return t;
        }
        code_err(ast, "I only know how to get 'not' of boolean, numeric, and optional pointer types, not ",
                 type_to_text(t));
    }
    case Or: {
        binary_operands_t binop = BINARY_OPERANDS(ast);
        type_t *lhs_t = get_type(env, binop.lhs);
        type_t *rhs_t = get_type(env, binop.rhs);

        if (is_int_literal(binop.lhs, NULL) && is_int_type(rhs_t)) return rhs_t;
        else if (is_int_literal(binop.rhs, NULL) && is_int_type(lhs_t)) return lhs_t;

        // `opt? or (x == y)` / `(x == y) or opt?` is a boolean conditional:
        if ((lhs_t->tag == OptionalType && rhs_t->tag == BoolType)
            || (lhs_t->tag == BoolType && rhs_t->tag == OptionalType)) {
            return Type(BoolType);
        }

        if (type_eq(lhs_t, rhs_t)) {
            binding_t *b = get_metamethod_binding(env, ast->tag, binop.lhs, binop.rhs, lhs_t);
            if (b) return lhs_t;
        }

        if (lhs_t->tag == OptionalType) {
            if (rhs_t->tag == OptionalType) {
                type_t *result = most_complete_type(lhs_t, rhs_t);
                if (result == NULL)
                    code_err(ast, "I could not determine the type of ", type_to_text(lhs_t), " `or` ",
                             type_to_text(rhs_t));
                return result;
            } else if (rhs_t->tag == AbortType || rhs_t->tag == ReturnType) {
                return Match(lhs_t, OptionalType)->type;
            }
            type_t *inner = Match(lhs_t, OptionalType)->type;
            type_t *non_opt = most_complete_type(inner, rhs_t);
            if (non_opt != NULL) return non_opt;
            // An untyped literal fallback takes the optional's own type, so
            // `x or 0` works for any numeric `x` (an `Int64?` and the bignum
            // `Int` literal `0` have no type in common otherwise).
            if (can_compile_to_type(env, binop.rhs, inner)) return inner;
        } else if ((is_numeric_type(lhs_t) || lhs_t->tag == BoolType)
                   && (is_numeric_type(rhs_t) || rhs_t->tag == BoolType) && lhs_t->tag != FloatType
                   && rhs_t->tag != FloatType) {
            if (can_compile_to_type(env, binop.rhs, lhs_t)) return lhs_t;
            else if (can_compile_to_type(env, binop.lhs, rhs_t)) return rhs_t;
        } else if (lhs_t->tag == TableType && rhs_t->tag == TableType && type_eq(lhs_t, rhs_t)) {
            return lhs_t;
        }
        code_err(ast, "I couldn't figure out how to do `or` between ", type_to_text(lhs_t), " and ",
                 type_to_text(rhs_t));
    }
    case And: {
        binary_operands_t binop = BINARY_OPERANDS(ast);
        type_t *lhs_t = get_type(env, binop.lhs);
        type_t *rhs_t = get_type(env, binop.rhs);

        if (is_int_literal(binop.lhs, NULL) && is_int_type(rhs_t)) return rhs_t;
        else if (is_int_literal(binop.rhs, NULL) && is_int_type(lhs_t)) return lhs_t;

        // `and` between optionals/bools is a boolean expression like `if opt? and opt?:` or `if x > 0 and opt?:`
        if ((lhs_t->tag == OptionalType || lhs_t->tag == BoolType)
            && (rhs_t->tag == OptionalType || rhs_t->tag == BoolType)) {
            return Type(BoolType);
        }

        if (type_eq(lhs_t, rhs_t)) {
            binding_t *b = get_metamethod_binding(env, ast->tag, binop.lhs, binop.rhs, lhs_t);
            if (b) return lhs_t;
        }

        // Bitwise AND:
        if ((is_numeric_type(lhs_t) || lhs_t->tag == BoolType) && (is_numeric_type(rhs_t) || rhs_t->tag == BoolType)
            && lhs_t->tag != FloatType && rhs_t->tag != FloatType) {
            if (can_compile_to_type(env, binop.rhs, lhs_t)) return lhs_t;
            else if (can_compile_to_type(env, binop.lhs, rhs_t)) return rhs_t;
        } else if (lhs_t->tag == TableType && rhs_t->tag == TableType && type_eq(lhs_t, rhs_t)) {
            return lhs_t;
        }
        code_err(ast, "I couldn't figure out how to do `and` between ", type_to_text(lhs_t), " and ",
                 type_to_text(rhs_t));
    }
    case Xor: {
        binary_operands_t binop = BINARY_OPERANDS(ast);
        type_t *lhs_t = get_type(env, binop.lhs);
        type_t *rhs_t = get_type(env, binop.rhs);

        if (is_int_literal(binop.lhs, NULL) && is_int_type(rhs_t)) return rhs_t;
        else if (is_int_literal(binop.rhs, NULL) && is_int_type(lhs_t)) return lhs_t;

        // `xor` between optionals/bools is a boolean expression like `if opt? xor opt?:` or `if x > 0 xor opt?:`
        if ((lhs_t->tag == OptionalType || lhs_t->tag == BoolType)
            && (rhs_t->tag == OptionalType || rhs_t->tag == BoolType)) {
            return Type(BoolType);
        }

        if (type_eq(lhs_t, rhs_t)) {
            binding_t *b = get_metamethod_binding(env, ast->tag, binop.lhs, binop.rhs, lhs_t);
            if (b) return lhs_t;
        }

        // Bitwise XOR:
        if ((is_numeric_type(lhs_t) || lhs_t->tag == BoolType) && (is_numeric_type(rhs_t) || rhs_t->tag == BoolType)
            && lhs_t->tag != FloatType && rhs_t->tag != FloatType) {
            if (can_compile_to_type(env, binop.rhs, lhs_t)) return lhs_t;
            else if (can_compile_to_type(env, binop.lhs, rhs_t)) return rhs_t;
        } else if (lhs_t->tag == TableType && rhs_t->tag == TableType && type_eq(lhs_t, rhs_t)) {
            return lhs_t;
        }
        code_err(ast, "I couldn't figure out how to do `xor` between ", type_to_text(lhs_t), " and ",
                 type_to_text(rhs_t));
    }
    case Compare:
    case Equals:
    case NotEquals:
    case LessThan:
    case LessThanOrEquals:
    case GreaterThan:
    case GreaterThanOrEquals: {
        binary_operands_t binop = BINARY_OPERANDS(ast);
        type_t *lhs_t = get_type(env, binop.lhs);
        type_t *rhs_t = get_type(env, binop.rhs);
        if (type_eq(lhs_t, rhs_t)) return ast->tag == Compare ? Type(IntType, .bits = TYPE_IBITS32) : Type(BoolType);

        // A bare numeric literal is untyped: it takes the other side's type,
        // even through an optional (`x : Float64? = none; x == 0.0`).
        if ((is_int_literal(binop.lhs, NULL) && is_numeric_type(rhs_t))
            || (is_int_literal(binop.rhs, NULL) && is_numeric_type(lhs_t))
            || (binop.lhs->tag == Num && is_numeric_type(non_optional(rhs_t)))
            || (binop.rhs->tag == Num && is_numeric_type(non_optional(lhs_t)))
            || can_compile_to_type(env, binop.rhs, lhs_t) || can_compile_to_type(env, binop.lhs, rhs_t))
            return ast->tag == Compare ? Type(IntType, .bits = TYPE_IBITS32) : Type(BoolType);

        code_err(ast, "I don't know how to compare ", type_to_text(lhs_t), " and ", type_to_text(rhs_t));
    }
    case Power:
    case Multiply:
    case Divide:
    case FloorDivide:
    case Mod:
    case Mod1:
    case Plus:
    case Minus:
    case LeftShift:
    case UnsignedLeftShift:
    case RightShift:
    case UnsignedRightShift: {
        binary_operands_t binop = BINARY_OPERANDS(ast);
        type_t *lhs_t = get_type(env, binop.lhs);
        type_t *rhs_t = get_type(env, binop.rhs);

        if (ast->tag == LeftShift || ast->tag == UnsignedLeftShift || ast->tag == RightShift
            || ast->tag == UnsignedRightShift) {
            if (!is_int_type(rhs_t))
                code_err(binop.rhs, "I only know how to do bit shifting by integer amounts, not ", type_to_text(rhs_t));
        }

        // `/` is exact division: dividing two integers gives the exact answer
        // (a Num), not a rounded-down integer. The integer quotient uses
        // `//` (Euclidean division), which keeps its operands' type.
        if (ast->tag == Divide && is_int_type(lhs_t) && is_int_type(rhs_t)) return Type(NumType);

        // A bare float literal is untyped, the same way a bare int literal is:
        // next to a `Float32`/`Float64` it takes that type instead of dragging
        // the whole operation into the exact-real `Num`, so `0.5 * x` is
        // Float64 math when `x` is a Float64. This mirrors what comparisons do
        // above. Only literals qualify: a `Num` *value* never promotes to a
        // float (see can_promote), so `can_compile_to_type` only says yes for
        // an expression built entirely out of literals.
        if (lhs_t->tag == FloatType && rhs_t->tag == NumType && can_compile_to_type(env, binop.rhs, lhs_t)) {
            return lhs_t;
        } else if (rhs_t->tag == FloatType && lhs_t->tag == NumType && can_compile_to_type(env, binop.lhs, rhs_t)) {
            return rhs_t;
        } else if (is_numeric_type(lhs_t) && is_int_literal(binop.rhs, NULL)) {
            return lhs_t;
        } else if (is_numeric_type(rhs_t) && is_int_literal(binop.lhs, NULL)) {
            return rhs_t;
        } else {
            switch (compare_precision(lhs_t, rhs_t)) {
            case NUM_PRECISION_LESS: return rhs_t;
            case NUM_PRECISION_MORE: return lhs_t;
            case NUM_PRECISION_EQUAL: return lhs_t;
            default: {
                if (can_compile_to_type(env, binop.rhs, lhs_t)) {
                    return lhs_t;
                } else if (can_compile_to_type(env, binop.lhs, rhs_t)) {
                    return rhs_t;
                }
                break;
            }
            }
        }

        if (ast->tag == Multiply && is_numeric_type(lhs_t)) {
            binding_t *b = get_namespace_binding(env, binop.rhs, "scaled_by");
            if (b && b->type->tag == FunctionType) {
                DeclareMatch(fn, b->type, FunctionType);
                if (type_eq(fn->ret, rhs_t)) {
                    arg_ast_t *args = new (arg_ast_t, .value = binop.rhs, .next = new (arg_ast_t, .value = binop.lhs));
                    if (is_valid_call(env, fn->args, args, (call_opts_t){.promotion = true})) return rhs_t;
                }
            }
        } else if (ast->tag == Multiply && is_numeric_type(rhs_t)) {
            binding_t *b = get_namespace_binding(env, binop.lhs, "scaled_by");
            if (b && b->type->tag == FunctionType) {
                DeclareMatch(fn, b->type, FunctionType);
                if (type_eq(fn->ret, lhs_t)) {
                    arg_ast_t *args = new (arg_ast_t, .value = binop.lhs, .next = new (arg_ast_t, .value = binop.rhs));
                    if (is_valid_call(env, fn->args, args, (call_opts_t){.promotion = true})) return lhs_t;
                }
            }
        } else if ((ast->tag == Divide || ast->tag == FloorDivide || ast->tag == Mod || ast->tag == Mod1)
                   && is_numeric_type(rhs_t)) {
            binding_t *b = get_namespace_binding(env, binop.lhs, binop_info[ast->tag].method_name);
            if (b && b->type->tag == FunctionType) {
                DeclareMatch(fn, b->type, FunctionType);
                if (type_eq(fn->ret, lhs_t)) {
                    arg_ast_t *args = new (arg_ast_t, .value = binop.lhs, .next = new (arg_ast_t, .value = binop.rhs));
                    if (is_valid_call(env, fn->args, args, (call_opts_t){.promotion = true})) return lhs_t;
                }
            }
        }

        type_t *overall_t =
            (can_compile_to_type(env, binop.rhs, lhs_t) ? lhs_t
                                                        : (can_compile_to_type(env, binop.lhs, rhs_t) ? rhs_t : NULL));
        if (overall_t == NULL)
            code_err(ast, "I don't know how to do math operations between ", type_to_text(lhs_t), " and ",
                     type_to_text(rhs_t));

        binding_t *b = get_metamethod_binding(env, ast->tag, binop.lhs, binop.rhs, overall_t);
        if (b) return overall_t;

        if (is_numeric_type(lhs_t) && is_numeric_type(rhs_t)) return overall_t;

        code_err(ast, "I don't know how to do math operations between ", type_to_text(lhs_t), " and ",
                 type_to_text(rhs_t));
    }
    case Concat: {
        binary_operands_t binop = BINARY_OPERANDS(ast);
        type_t *lhs_t = get_type(env, binop.lhs);
        type_t *rhs_t = get_type(env, binop.rhs);

        type_t *overall_t =
            (can_compile_to_type(env, binop.rhs, lhs_t) ? lhs_t
                                                        : (can_compile_to_type(env, binop.lhs, rhs_t) ? rhs_t : NULL));
        if (overall_t == NULL)
            code_err(ast, "I don't know how to do operations between ", type_to_text(lhs_t), " and ",
                     type_to_text(rhs_t));

        binding_t *b = get_metamethod_binding(env, ast->tag, binop.lhs, binop.rhs, overall_t);
        if (b) return overall_t;

        if (overall_t->tag == ListType || overall_t->tag == TableType || overall_t->tag == TextType) return overall_t;

        code_err(ast, "I don't know how to do concatenation between ", type_to_text(lhs_t), " and ",
                 type_to_text(rhs_t));
    }

    case Reduction: {
        DeclareMatch(reduction, ast, Reduction);
        type_t *iter_t = get_type(env, reduction->iter);

        if (reduction->op == Equals || reduction->op == NotEquals || reduction->op == LessThan
            || reduction->op == LessThanOrEquals || reduction->op == GreaterThan
            || reduction->op == GreaterThanOrEquals)
            return Type(OptionalType, .type = Type(BoolType));

        type_t *iterated = get_iterated_type(iter_t);
        if (!iterated)
            code_err(reduction->iter, "I don't know how to do a reduction over ", type_to_text(iter_t), " values");
        if (reduction->key && !(reduction->op == Min || reduction->op == Max)) {
            env_t *item_scope = fresh_scope(env);
            const char *op_str = binop_info[reduction->op].operator;
            set_binding(item_scope, op_str, iterated, EMPTY_TEXT);
            iterated = get_type(item_scope, reduction->key);
        }
        return iterated->tag == OptionalType ? iterated : Type(OptionalType, .type = iterated);
    }

    case Min:
    case Max: {
        // Unsafe! These types *should* have the same fields and this saves a lot of duplicate code:
        ast_t *lhs = ast->__data.Min.lhs, *rhs = ast->__data.Min.rhs;
        // Okay safe again

        type_t *lhs_t = get_type(env, lhs), *rhs_t = get_type(env, rhs);
        type_t *t = type_or_type(lhs_t, rhs_t);
        if (!t)
            code_err(ast, "The two sides of this operation are not compatible: ", type_to_text(lhs_t), " vs ",
                     type_to_text(rhs_t));
        return t;
    }

    case Lambda: return get_function_type(env, ast);

    case FunctionDef:
    case ConvertDef:
    case StructDef:
    case EnumDef:
    case LangDef: return Type(VoidType);

    case If: {
        DeclareMatch(if_, ast, If);

        env_t *truthy_scope = env;
        env_t *falsey_scope = env;
        if (if_->condition->tag == Declare) {
            DeclareMatch(decl, if_->condition, Declare);
            type_t *condition_type = decl->type ? parse_type_ast(env, decl->type) : get_type(env, decl->value);
            const char *varname = Match(decl->var, Var)->name;
            if (streq(varname, "_"))
                code_err(if_->condition, "To use `if var := ...:`, you must choose a real variable name, not `_`");

            truthy_scope = fresh_scope(env);
            if (condition_type->tag == OptionalType)
                set_binding(truthy_scope, varname, Match(condition_type, OptionalType)->type, EMPTY_TEXT);
            else set_binding(truthy_scope, varname, condition_type, EMPTY_TEXT);
        } else if (if_->condition->tag == Var) {
            type_t *condition_type = get_type(env, if_->condition);
            if (condition_type->tag == OptionalType) {
                truthy_scope = fresh_scope(env);
                const char *varname = Match(if_->condition, Var)->name;
                set_binding(truthy_scope, varname, Match(condition_type, OptionalType)->type, EMPTY_TEXT);
            }
        }

        type_t *true_t = get_type(truthy_scope, if_->body);
        ast_t *else_body = if_->else_body;
        if (!else_body) {
            if (true_t->tag == AbortType) return Type(VoidType);
            else_body = WrapAST(ast, None, .type = true_t);
        }
        type_t *false_t = get_type(falsey_scope, if_->else_body);
        type_t *t_either = type_or_type(true_t, false_t);
        if (!t_either)
            code_err(if_->else_body, "I was expecting this block to have a ", type_to_text(true_t),
                     " value (based on earlier clauses), but it actually has a ", type_to_text(false_t), " value.");
        return t_either;
    }

    case Match: {
        DeclareMatch(match, ast, Match);
        type_t *subject_t = get_type(env, match->subject);
        if (subject_t->tag != EnumType) {
            type_t *t = NULL;
            for (match_clause_t *clause = match->clauses; clause; clause = clause->next) {
                t = type_or_type(t, get_type(env, clause->body));
            }
            if (match->else_body) t = type_or_type(t, get_type(env, match->else_body));
            else if (t && t->tag != OptionalType) t = Type(OptionalType, .type = t);
            return t;
        }

        type_t *overall_t = NULL;
        tag_t *const tags = Match(subject_t, EnumType)->tags;

        typedef struct tag_coverage_s {
            tag_t *tag;
            bool handled;
            struct tag_coverage_s *next;
        } tag_coverage_t;
        tag_coverage_t *tag_coverage = NULL;
        for (tag_t *tag = tags; tag; tag = tag->next)
            tag_coverage = new (tag_coverage_t, .tag = tag, .handled = false, .next = tag_coverage);

        for (match_clause_t *clause = match->clauses; clause; clause = clause->next) {
            const char *tag_name;
            if (clause->pattern->tag == Var) tag_name = Match(clause->pattern, Var)->name;
            else if (clause->pattern->tag == RecordLiteral && Match(clause->pattern, RecordLiteral)->type->tag == Var)
                tag_name = Match(Match(clause->pattern, RecordLiteral)->type, Var)->name;
            else code_err(clause->pattern, "This is not a valid pattern for a ", type_to_text(subject_t), " enum");

            Text_t valid_tags = EMPTY_TEXT;
            for (tag_coverage_t *c = tag_coverage; c; c = c->next) {
                if (streq(c->tag->name, tag_name)) {
                    if (c->handled) code_err(clause->pattern, "This tag was already handled earlier");
                    c->handled = true;
                    goto found_matching_tag;
                }
                if (valid_tags.length > 0) valid_tags = Texts(valid_tags, ", ");
                valid_tags = Texts(valid_tags, c->tag->name);
            }

            code_err(clause->pattern, "There is no tag '", tag_name, "' for the type ", type_to_text(subject_t),
                     " (valid tags: ", valid_tags, ")");
        found_matching_tag:;
        }

        for (match_clause_t *clause = match->clauses; clause; clause = clause->next) {
            env_t *clause_scope = match_clause_scope(env, subject_t, clause);
            type_t *clause_type = get_type(clause_scope, clause->body);
            type_t *merged = type_or_type(overall_t, clause_type);
            if (!merged)
                code_err(clause->body, "The type of this branch is ", type_to_text(clause_type),
                         ", which conflicts with the earlier branch type of ", type_to_text(overall_t));
            overall_t = merged;
        }

        if (match->else_body) {
            bool any_unhandled = false;
            for (tag_coverage_t *c = tag_coverage; c; c = c->next) {
                if (!c->handled) {
                    any_unhandled = true;
                    break;
                }
            }
            // HACK: `while match ...` is handled by the parser adding an implicit
            // `else: break`, which has an empty source code span.
            if (!any_unhandled && match->else_body->end > match->else_body->start)
                code_err(match->else_body, "This 'else' block will never run because every tag is handled");

            type_t *else_t = get_type(env, match->else_body);
            type_t *merged = type_or_type(overall_t, else_t);
            if (!merged)
                code_err(match->else_body, "I was expecting this block to have a ", type_to_text(overall_t),
                         " value (based on earlier clauses), but it actually has a ", type_to_text(else_t), " value.");
            return merged;
        } else {
            Text_t unhandled = EMPTY_TEXT;
            for (tag_coverage_t *c = tag_coverage; c; c = c->next) {
                if (!c->handled)
                    unhandled =
                        unhandled.length > 0 ? Texts(unhandled, ", ", c->tag->name) : Text$from_str(c->tag->name);
            }
            if (unhandled.length > 0) code_err(ast, "This 'match' statement doesn't handle the tags: ", unhandled);
            return overall_t;
        }
    }

    case While:
    case Repeat:
    case For: return Type(VoidType);
    case InlineCCode: {
        DeclareMatch(inline_code, ast, InlineCCode);
        if (inline_code->type) return inline_code->type;
        type_ast_t *type_ast = inline_code->type_ast;
        return type_ast ? parse_type_ast(env, type_ast) : Type(VoidType);
    }
    case Serialize: {
        fail_if_serialize_shadowed(env, ast);
        type_t *t = get_type(env, Match(ast, Serialize)->value);
        type_t *bad = unserializable_part(t);
        if (bad)
            code_err(Match(ast, Serialize)->value, "I can't serialize this ", type_to_text(t),
                     " value, because values of type ", type_to_text(bad), " have no byte representation");
        return Type(ListType, .item_type = Type(ByteType));
    }
    case Deserialize: {
        type_t *t = parse_type_ast(env, Match(ast, Deserialize)->type_ast);
        type_t *bad = unserializable_part(t);
        if (bad)
            code_err(ast, "I can't deserialize a ", type_to_text(t), " value, because values of type ",
                     type_to_text(bad), " have no byte representation");
        // Note: if `t` is already optional, the result stays a single optional
        // (Tomo has no nested optionals), so `none` means either "the bytes
        // didn't decode" or "the bytes encoded a `none`".
        return t->tag == OptionalType ? t : Type(OptionalType, .type = t);
    }
    case Unknown: code_err(ast, "I can't figure out the type of: ", ast_to_sexp_str(ast));
    case ExplicitlyTyped: return Match(ast, ExplicitlyTyped)->type;
    case Metadata: return Type(VoidType);
    }
#pragma clang diagnostic pop
    code_err(ast, "I can't figure out the type of: ", ast_to_sexp_str(ast));
    return NULL;
}

PUREFUNC bool is_discardable(env_t *env, ast_t *ast) {
    switch (ast->tag) {
    case UPDATE_CASES:
    case Assign:
    case Declare:
    case FunctionDef:
    case ConvertDef:
    case StructDef:
    case EnumDef:
    case LangDef:
    case Use:
    case Metadata: return true;
    default: break;
    }
    return is_discardable_type(get_type(env, ast));
}

type_t *get_arg_ast_type(env_t *env, arg_ast_t *arg) {
    assert(arg->type || arg->value);
    if (arg->type) return parse_type_ast(env, arg->type);
    return get_type(env, arg->value);
}

type_t *get_arg_type(env_t *env, arg_t *arg) {
    assert(arg->type || arg->default_val);
    if (arg->type) return arg->type;
    return get_type(env, arg->default_val);
}

bool is_valid_call(env_t *env, arg_t *spec_args, arg_ast_t *call_args, call_opts_t options) {
    Table_t used_args = EMPTY_TABLE;

    // Populate keyword args:
    for (arg_ast_t *call_arg = call_args; call_arg; call_arg = call_arg->next) {
        if (!call_arg->name) continue;

        for (arg_t *spec_arg = spec_args; spec_arg; spec_arg = spec_arg->next) {
            if (!(streq(call_arg->name, spec_arg->name) || (spec_arg->alias && streq(call_arg->name, spec_arg->alias))))
                continue;
            type_t *spec_type = get_arg_type(env, spec_arg);
            env_t *arg_scope = with_enum_scope(env, spec_type);
            type_t *call_type = get_arg_ast_type(arg_scope, call_arg);
            if (options.promotion) {
                if (!can_compile_to_type(arg_scope, call_arg->value, spec_type))
                    return false; // Positional arg trying to fill in
            } else {
                type_t *complete_call_type =
                    is_incomplete_type(call_type) ? most_complete_type(call_type, spec_type) : call_type;
                if (!complete_call_type) return false;
                if (!type_eq(complete_call_type, spec_type)) return false;
            }
            Table$str_set(&used_args, call_arg->name, call_arg);
            goto next_call_arg;
        }
        return false;
    next_call_arg:;
    }

    arg_ast_t *unused_args = call_args;
    for (arg_t *spec_arg = spec_args; spec_arg; spec_arg = spec_arg->next) {
        arg_ast_t *keyworded = Table$str_get(used_args, spec_arg->name);
        if (keyworded) continue;

        {
            type_t *spec_type = get_arg_type(env, spec_arg);
            env_t *arg_scope = with_enum_scope(env, spec_type);
            for (; unused_args; unused_args = unused_args->next) {
                if (unused_args->name) continue; // Already handled the keyword args
                if (options.promotion) {
                    if (!can_compile_to_type(arg_scope, unused_args->value, spec_type)) {
                        return false; // Positional arg trying to fill in
                    }
                } else {
                    type_t *call_type = get_arg_ast_type(arg_scope, unused_args);
                    type_t *complete_call_type =
                        is_incomplete_type(call_type) ? most_complete_type(call_type, spec_type) : call_type;
                    if (!complete_call_type) return false;
                    if (!type_eq(complete_call_type, spec_type)) return false; // Positional arg trying to fill in
                }
                Table$str_set(&used_args, spec_arg->name, unused_args);
                unused_args = unused_args->next;
                goto found_it;
            }
        }

        if (spec_arg->default_val) goto found_it;

        return false;
    found_it:
        continue;
    }

    while (unused_args && unused_args->name)
        unused_args = unused_args->next;

    return (unused_args == NULL);
}

PUREFUNC bool is_bit_packed_field(env_t *env, ast_t *ast) {
    if (ast->tag != FieldAccess) return false;
    DeclareMatch(access, ast, FieldAccess);
    type_t *fielded_t = value_type(get_type(env, access->fielded));
    if (fielded_t->tag != StructType || !Match(fielded_t, StructType)->packed_bools) return false;
    type_t *field_t = get_field_type(fielded_t, access->field);
    return field_t != NULL && packed_bit_width(field_t) > 0;
}

PUREFUNC bool can_be_mutated(env_t *env, ast_t *ast) {
    switch (ast->tag) {
    case Var: return true;
    case InlineCCode: return true;
    case FieldAccess: {
        DeclareMatch(access, ast, FieldAccess);
        if (get_subcommand_binding(env, ast)) return false; // Subcommand functions can't be reassigned
        type_t *fielded_type = get_type(env, access->fielded);
        if (fielded_type->tag == PointerType) {
            type_t *val = value_type(fielded_type);
            return val->tag == StructType;
        } else if (fielded_type->tag == StructType) {
            return can_be_mutated(env, access->fielded);
        } else {
            return false;
        }
    }
    case Index: {
        DeclareMatch(index, ast, Index);
        type_t *indexed_type = get_type(env, index->indexed);
        return (indexed_type->tag == PointerType);
    }
    default: return false;
    }
}

type_t *parse_type_string(env_t *env, const char *str) {
    type_ast_t *ast = parse_type_str(str);
    return ast ? parse_type_ast(env, ast) : NULL;
}

// Compiled to a native fixed-width int / Num / Byte target, any int literal
// that fits is a plain cast to a C constant (codegen errors if it doesn't fit).
// Compiled to a bignum `Int`, only a small-enough literal is constant (the
// I_small() compound literal); a larger one compiles to a runtime
// Int$from_str/from_int64 call. Magnitude, not signed order: compile_int
// compares the same way (mpz_cmpabs_ui), so a big *negative* literal is no more
// constant than a big positive one.
static bool int_literal_is_constant(Int_t i, type_t *t) {
    if (t->tag == IntType || t->tag == FloatType || t->tag == ByteType) return true;
    return Int$compare_value(i, I(BIGGEST_SMALL_INT)) <= 0 && Int$compare_value(i, I(-BIGGEST_SMALL_INT)) >= 0;
}

bool is_constant(env_t *env, ast_t *ast, type_t *expected_type) {
    // For numeric cases, the type this value will be compiled to: when the
    // caller knows it (a declared type or a list's item type), an untyped-int
    // expression compiles in that type, so `1 + 2` in an Int64 context is
    // native `(I64(1)+I64(2))`, a C constant, rather than
    // bignum-then-converted.
    // `NULL` means "use the value's own inferred type".
#define EXPECTED_OR_INFERRED (expected_type ? expected_type : get_type(env, ast))
    switch (ast->tag) {
    case Bool:
    case None: return true;
    case Num: {
        // Compiled to a Float64/Float32 target, a numeric literal is a hex
        // float constant. Compiled to a `Num`, only a value that fits the
        // immediate tier is a C constant (a NUMBER_SMALL compound literal);
        // anything else, whether a big numerator/denominator or an irrational
        // like `90deg`, needs a runtime constructor call (see compile_num).
        type_t *t = EXPECTED_OR_INFERRED;
        if (t->tag == FloatType) return true;
        if (t->tag != NumType) return false;
        return (Match(ast, Num)->n.bits & 0x3) == 0x1;
    }
    case Int: return int_literal_is_constant(Match(ast, Int)->i, EXPECTED_OR_INFERRED);
    case TextJoin: {
        DeclareMatch(text, ast, TextJoin);
        if (!text->children) return true; // Empty string, OK
        if (text->children->next) return false; // Concatenation, not constant
        return is_constant(env, text->children->ast, NULL);
    }
    case List: {
        // A list literal is a compile-time constant when it has no comprehension
        // and every element is constant: it compiles to a `(List_t){...}` backed
        // by a hoisted `static const` array, itself a constant expression (see
        // ConstList / compile_typed_list). An empty literal is the constant
        // EMPTY_LIST.
        DeclareMatch(list, ast, List);
        if (!list->items) return true;
        type_t *lt = EXPECTED_OR_INFERRED;
        if (lt->tag != ListType) return false;
        type_t *item_type = Match(lt, ListType)->item_type;
        if (item_type == NULL || is_incomplete_type(item_type)) return false;
        for (ast_list_t *item = list->items; item; item = item->next) {
            if (item->ast->tag == Comprehension) return false;
            if (!is_constant(env, item->ast, item_type)) return false;
        }
        return true;
    }
    case TextLiteral: {
        Text_t literal = Match(ast, TextLiteral)->text;
        TextIter_t state = NEW_TEXT_ITER_STATE(literal);
        for (int64_t i = 0; i < (int64_t)literal.length; i++) {
            int32_t g = Text$get_grapheme_fast(&state, i);
            if (g < 0 || g > 127 || !isascii(g)) return false;
        }
        return true; // Literal ASCII string, OK
    }
    case Not: {
        // `not` is a native C `!`/`~` (constant) for Bool and fixed-width int /
        // Byte, but a function call (`Int$negated`) for bignum `Int`. Codegen
        // doesn't push a target type through `not`, so gate on the value's own
        // type, not the expected type.
        type_t *nt = get_type(env, ast);
        if (nt->tag == BigIntType) return false;
        return is_constant(env, Match(ast, Not)->value, NULL);
    }
    case Negative: {
        // A `-` written apart from its digits is a literal like any other (see
        // is_int_literal), and is constant on the same terms:
        Int_t literal;
        if (is_int_literal(ast, &literal)) return int_literal_is_constant(literal, EXPECTED_OR_INFERRED);

        // A constant Num folds to a single value at compile time, just as the
        // arithmetic in BINOP_CASES below does, but only when it is compiled
        // *as* a Num. Promoting one to a float is a runtime call, and codegen
        // doesn't push a target type through `-` to avoid it.
        if (EXPECTED_OR_INFERRED->tag == NumType) {
            Num_t folded;
            return fold_num_constant(ast, &folded) && (folded.bits & 0x3) == 0x1;
        }

        // Negation otherwise compiles to a native C `-` (a constant expression)
        // only for fixed-width int / Num / Byte, not bignum `Int`
        // (`Int$negative` call). Same reason as above: gate on the value's own
        // type, since no target type is pushed through the `-`.
        type_t *nt = get_type(env, ast);
        if (nt->tag != IntType && nt->tag != FloatType && nt->tag != ByteType) return false;
        return is_constant(env, Match(ast, Negative)->value, NULL);
    }
    case BINOP_CASES: {
        binary_operands_t binop = BINARY_OPERANDS(ast);
        type_t *t = EXPECTED_OR_INFERRED;
        // An operation is a compile-time constant only when it has a native C
        // operator form for `t` (so `compile_to_type`, which pushes `t` into
        // the operands, renders it as a constant expression). The op set is
        // type-dependent: fixed-width int `/`,`%` compile to *checked* blocks
        // (division-by-zero), and `**` and bignum arithmetic to function
        // calls, none of which are constants. Operands are checked against
        // the same target `t`.
        // Constant Num arithmetic folds to a single value at compile time
        // (see fold_num_constant); it's a C constant when that value fits the
        // immediate tier.
        if (t->tag == NumType) {
            Num_t folded;
            return fold_num_constant(ast, &folded) && (folded.bits & 0x3) == 0x1;
        }
        bool native;
        switch (ast->tag) {
        case Plus:
        case Minus:
        case Multiply: native = (t->tag == IntType || t->tag == ByteType || t->tag == FloatType); break;
        case Divide: native = (t->tag == FloatType); break; // fixed-width int '/' is a checked block
        case LeftShift:
        case RightShift:
        case UnsignedLeftShift:
        case UnsignedRightShift: native = (t->tag == IntType || t->tag == ByteType); break;
        case And:
        case Or:
        case Xor: native = (t->tag == IntType || t->tag == ByteType || t->tag == BoolType); break;
        default: native = false; break; // Power, Mod, Mod1, Concat, comparisons, Min, Max, Compare
        }
        if (!native) return false;
        return is_constant(env, binop.lhs, t) && is_constant(env, binop.rhs, t);
    }
    case Use:
    case Metadata: return true;
    case FunctionCall: {
        // A numeric type "constructor" applied to a constant literal (e.g.
        // `Int64(123)`, `Byte(10)`, `Num(1.5)`) is not a real call: it compiles
        // to a plain cast (see the pure-cast path in compile_typed_call()), so
        // it's a compile-time constant just like the literal it wraps.
        DeclareMatch(call, ast, FunctionCall);
        type_t *fn_t = get_type(env, call->fn);
        if (fn_t && fn_t->tag == TypeInfoType && call->args && !call->args->next) {
            type_t *ctor_t = Match(fn_t, TypeInfoType)->type;
            ast_t *arg = call->args->value;
            if (is_numeric_type(ctor_t) && is_int_literal(arg, NULL) && is_constant(env, arg, ctor_t)) return true;
            if (ctor_t->tag == FloatType && arg->tag == Num) return true;
        }
        return false;
    }
    case InlineCCode: return true;
    // Whether an `Embed` is a compile-time constant depends on what type it's being
    // compiled to, which `is_constant()` doesn't have access to, so conservatively say no
    // here and let callers that do know the target type use `embed_is_constant()` instead:
    case Embed: return false;
    default: return false;
    }
#undef EXPECTED_OR_INFERRED
}

public
Path_t get_embed_path(ast_t *ast) {
    DeclareMatch(embed, ast, Embed);
    const char *path = Match(embed->path, Path)->path;
    OptionalPath_t source_dir = Path$parent(Path$from_str(ast->file->filename));
    assert(source_dir); // A source file always has a directory
    return Path$resolved(Path$from_str(path), source_dir);
}

public
List_t get_embed_bytes(ast_t *ast) {
    Path_t resolved = get_embed_path(ast);
    if (Path$is_directory(resolved, true))
        code_err(ast,
                 "This is a directory, so it can only be embedded as a table ({Path:[Byte]}, {Path:Text}, or "
                 "{Path:CString}), not a single value: ",
                 resolved);
    OptionalList_t bytes = Path$read_bytes(resolved, NONE_INT);
    if (bytes.data == NULL) code_err(ast, "I couldn't read this file: ", resolved);
    return bytes;
}

static void collect_dir_embed_files(ast_t *ast, Path_t dir, List_t *files, List_t *subdirs) {
    OptionalList_t children = Path$glob(dir, Text("[!.]*"));
    if (children.data == NULL) code_err(ast, "I couldn't read this directory: ", dir);
    for (int64_t i = 0; i < (int64_t)children.length; i++) {
        Path_t child = *(Path_t *)(children.data + i * children.stride);
        if (Path$is_symlink(child)) continue;
        if (Path$is_directory(child, false)) {
            if (subdirs) List$insert(subdirs, &child, I(0), sizeof(Path_t));
            collect_dir_embed_files(ast, child, files, subdirs);
        } else if (Path$is_file(child, false)) {
            List$insert(files, &child, I(0), sizeof(Path_t));
        }
    }
}

// The files a directory embed includes: every file under the directory,
// recursively, excluding dotfiles (embed one by naming it explicitly) and
// symlinks (which could point outside the directory or form a cycle). Sorting
// the absolute paths also orders the table's relative keys, since they share
// the embedded directory as a prefix. `subdirs`, if non-NULL, receives every
// traversed subdirectory: a directory's mtime is what a staleness check has
// to watch to catch an added, removed, or renamed file.
public
List_t get_dir_embed_files(ast_t *ast, List_t *subdirs) {
    Path_t dir = get_embed_path(ast);
    List_t files = EMPTY_LIST;
    collect_dir_embed_files(ast, dir, &files, subdirs);
    if (files.length == 0)
        code_err(ast, "This directory has no files to embed in it (dotfiles and symlinks are not embedded): ", dir);
    Closure_t comparison = {.fn = (void *)CString$compare, .userdata = (void *)&Path$info};
    List$sort(&files, comparison, sizeof(Path_t));
    return files;
}

// Like `is_constant()`, but for `Embed` expressions, where const-ness depends on the target type:
// - `[Byte]`: always a constant (a raw bytes literal)
// - `Text`: a constant only if the file's contents are ASCII (no NUL bytes, no high-bit bytes)
// - `CString`: a constant only if the file has no embedded NUL bytes
// - anything else (including any directory embed, which compiles to a table): not a constant
bool embed_is_constant(ast_t *ast, type_t *t) {
    assert(ast->tag == Embed);
    if (t->tag == ListType && Match(t, ListType)->item_type->tag == ByteType) return true;

    if (t->tag != TextType && t->tag != CStringType) return false;

    List_t bytes = get_embed_bytes(ast);

    const uint8_t *data = (const uint8_t *)bytes.data;
    for (int64_t i = 0; i < (int64_t)bytes.length; i++) {
        uint8_t byte = data[i * bytes.stride];
        if (byte == 0) return false;
        if (t->tag == TextType && byte >= 0x80) return false;
    }
    return true;
}

// File-scope variables and variables inside of type namespaces are initialized
// using static initializers like `int x = 1;` when possible, but in cases where
// heap allocation or function calls are needed, C does not permit that, so we
// have to do a dance: `int x; bool x$initialized = false;` and then inside the
// init function, we put `x$initialized = true; x = doop();`
// The `out_type` param lets callers receive the declaration's type if they want it.
bool needs_runtime_initialization(env_t *env, ast_t *declare, type_t **out_type) {
    DeclareMatch(decl, declare, Declare);
    type_t *t = decl->type ? parse_type_ast(env, decl->type) : get_type(env, decl->value);
    if (t->tag == FunctionType) t = Type(ClosureType, t);
    if (out_type) *out_type = t;
    if (!decl->value) return has_heap_memory(t);
    return !(decl->value->tag == Embed ? embed_is_constant(decl->value, t) : is_constant(env, decl->value, t));
}

// Arithmetic/bitwise binary ops whose result type can be pushed down into the
// operands, so untyped-int-literal arithmetic like `1 + 2` can compile natively
// in a target numeric type (e.g. `(I64(1)+I64(2))`) instead of in
// bignum-then-converted. Excludes comparisons and Concat, which don't produce a
// numeric result of the operands' type. Used by can_compile_to_type (to accept
// such an expression for a numeric type) and compile_to_type (to emit the native
// form).
//
// The op set is `target`-dependent, because the native C form only exists for
// some (op, type) pairs (mirroring the native table in is_constant): bit shifts
// and bitwise and/or/xor have no float form, so they can't push into a
// `Float64`/`Float32` target (`(3.0 << 1.0)` is invalid C); exponentiation
// compiles to `pow()` and only supports floats. `Num` (the exact real) has no
// native C operator form for *any* op, since its arithmetic goes through the
// Num$plus/... metamethods, which compile_binary_op_to_type only finds when
// the operands are already Nums, so nothing pushes down into it; an int-literal
// expression bound for a `Num` is computed as an `Int` and promoted.
// `target == NULL` means "no target constraint".
PUREFUNC bool is_pushdown_arithmetic(ast_t *ast, type_t *target) {
    if (target != NULL && target->tag == NumType) return false;
    switch (ast->tag) {
    case Power: return target == NULL || target->tag == FloatType;
    case Multiply:
    case Divide:
    case FloorDivide:
    case Mod:
    case Mod1:
    case Plus:
    case Minus: return true;
    case LeftShift:
    case RightShift:
    case UnsignedLeftShift:
    case UnsignedRightShift:
    case And:
    case Or:
    case Xor: return target == NULL || target->tag != FloatType;
    default: return false;
    }
}

PUREFUNC bool can_compile_to_type(env_t *env, ast_t *ast, type_t *needed) {
    if (is_incomplete_type(needed)) return false;

    if (needed->tag == OptionalType && ast->tag == None) return true;

    // Whether an embed's path names a file or a directory is the filesystem's
    // business, checked when the embed is compiled, so the target type alone
    // settles this:
    if (ast->tag == Embed) {
        if (needed->tag == TextType || needed->tag == CStringType) return true;
        if (needed->tag == ListType && Match(needed, ListType)->item_type->tag == ByteType) return true;
        if (needed->tag == TableType) {
            type_t *key = Match(needed, TableType)->key_type, *value = Match(needed, TableType)->value_type;
            if (key->tag == PathType
                && (value->tag == TextType || value->tag == CStringType
                    || (value->tag == ListType && Match(value, ListType)->item_type->tag == ByteType)))
                return true;
        }
    }

    env = with_enum_scope(env, needed);
    type_t *non_optional_needed = non_optional(needed);
    // Untyped int literals can compile to a numeric type even when it's
    // wrapped in an Optional (e.g. comparing a `(+.length: ...)` reduction's
    // `Int64?` result against the literal `6`).
    if (is_numeric_type(non_optional_needed) && is_int_literal(ast, NULL)) return true;
    if (needed->tag == FloatType && ast->tag == Num) return true;
    // Untyped-int-literal arithmetic (inferred as bignum `Int`) can compile to
    // any numeric type its operands can, by pushing the type into them.
    if (is_numeric_type(non_optional_needed) && is_pushdown_arithmetic(ast, non_optional_needed)
        && get_type(env, ast)->tag == BigIntType) {
        // Only an opportunity, not a requirement: if the operands can't take
        // the target type (e.g. `x or 0`, whose `or` is an optional fallback
        // and not arithmetic at all), fall through to the ordinary checks
        // below, where the expression's own type may already fit.
        binary_operands_t binop = BINARY_OPERANDS(ast);
        if (can_compile_to_type(env, binop.lhs, non_optional_needed)
            && can_compile_to_type(env, binop.rhs, non_optional_needed))
            return true;
    }
    // ...and so can literal float arithmetic (inferred as the exact `Num`),
    // when the target is a float: `0.5*x`, `1.0/3.0*x`. A `Num` value never
    // promotes to a float, so this recursion only succeeds when every leaf is
    // itself a literal (or already float-compatible).
    if (non_optional_needed->tag == FloatType && is_pushdown_arithmetic(ast, non_optional_needed)
        && get_type(env, ast)->tag == NumType) {
        binary_operands_t binop = BINARY_OPERANDS(ast);
        if (can_compile_to_type(env, binop.lhs, non_optional_needed)
            && can_compile_to_type(env, binop.rhs, non_optional_needed))
            return true;
    }

    if (non_optional_needed->tag == ListType && ast->tag == List) {
        type_t *item_type = Match(non_optional_needed, ListType)->item_type;
        for (ast_list_t *item = Match(ast, List)->items; item; item = item->next) {
            env_t *scope = env;
            ast_t *item_ast = unwrap_comprehension(&scope, item->ast);
            if (!can_compile_to_type(scope, item_ast, item_type)) return false;
        }
        return true;
    } else if (non_optional_needed->tag == TableType && ast->tag == Table) {
        type_t *key_type = Match(non_optional_needed, TableType)->key_type;
        type_t *value_type = Match(non_optional_needed, TableType)->value_type;
        for (ast_list_t *entry = Match(ast, Table)->entries; entry; entry = entry->next) {
            env_t *scope = env;
            ast_t *entry_ast = unwrap_comprehension(&scope, entry->ast);
            if (entry_ast->tag != TableEntry) return false;
            DeclareMatch(e, entry_ast, TableEntry);
            if (!can_compile_to_type(scope, e->key, key_type)
                || !(e->value ? can_compile_to_type(scope, e->value, value_type) : type_eq(value_type, PRESENT_TYPE)))
                return false;
        }
        return true;
    }

    type_t *actual = get_type(env, ast);
    if (type_eq(actual, needed)) return true;
    if (actual->tag == OptionalType && needed->tag == OptionalType) return can_promote(actual, needed);

    if (non_optional_needed->tag == PointerType) {
        DeclareMatch(ptr, non_optional_needed, PointerType);
        if (ast->tag == HeapAllocate)
            return !ptr->is_stack && can_compile_to_type(env, Match(ast, HeapAllocate)->value, ptr->pointed);
        else if (ast->tag == StackReference)
            return ptr->is_stack && can_compile_to_type(env, Match(ast, StackReference)->value, ptr->pointed);
        else return can_promote(actual, non_optional_needed);
    } else if (actual->tag == OptionalType && non_optional_needed->tag != OptionalType) {
        return false;
    } else {
        return can_promote(actual, non_optional_needed);
    }
}

// "Did you mean 'x'?" for an unrecognized name, or nothing when no candidate
// is close enough to be worth suggesting:
OptionalText_t suggest_best_name(const char *wrong, List_t names) {
    Text_t target = Text$from_str(wrong);
    OptionalText_t nearest = Text$nearest(target, names, NUMBER_SMALL(3, 5) /* 0.6 */);
    if (nearest.tag == TEXT_NONE) return NONE_TEXT;
    // The per-grapheme ratio alone isn't enough at the long end: 0.6 of a
    // 20-character identifier is 12 edits, which is a different name, not a
    // typo. Cap the absolute distance too.
    if (number_compare(Text$distance(target, nearest), number_from_int(6)) > 0) return NONE_TEXT;
    return Texts("\nDid you mean '", nearest, "'?");
}

// `serialize(...)` always parses as the built-in construct, so a callable
// binding by that name is unreachable through it. Reject that rather than
// quietly ignoring the function.
void fail_if_serialize_shadowed(env_t *env, ast_t *ast) {
    binding_t *shadowed = get_binding(env, "serialize");
    if (shadowed && shadowed->type && (shadowed->type->tag == FunctionType || shadowed->type->tag == ClosureType))
        code_err(ast, "This is the built-in `serialize(...)` construct, so it shadows the `serialize` function "
                      "defined here. Please rename that function");
}

// A field access on an optional value is almost always a missing `!` rather
// than a misspelled field, so say that instead of "no such field". Does nothing
// if `fielded_t` isn't an optional whose underlying type has this field.
void fail_if_optional_field_access(ast_t *ast, type_t *fielded_t, const char *field) {
    if (fielded_t->tag != OptionalType) return;
    if (get_field_type(non_optional(fielded_t), field) == NULL) return;
    code_err(ast, "This value is optional (", type_to_text(fielded_t), "), so it might be none and I can't read its '",
             field, "' field. Use '!' to assert that it has a value, or check it with an 'if' first");
}

List_t get_field_names(env_t *env, type_t *t) {
    t = value_type(t);
    switch (t->tag) {
    case PointerType: return get_field_names(env, Match(t, PointerType)->pointed);
    case OptionalType: return get_field_names(env, Match(t, OptionalType)->type);
    case TextType: return List(Text("text"), Text("length"));
    case StructType: {
        DeclareMatch(struct_t, t, StructType);
        List_t fields = EMPTY_LIST;
        for (arg_t *field = struct_t->fields; field; field = field->next) {
            Text_t field_text = Text$from_str(field->name);
            List$insert(&fields, &field_text, I(0), sizeof(Text_t));
        }
        return fields;
    }
    case EnumType: {
        DeclareMatch(e, t, EnumType);
        List_t tags = EMPTY_LIST;
        for (tag_t *tag = e->tags; tag; tag = tag->next) {
            Text_t tag_text = Text$from_str(tag->name);
            List$insert(&tags, &tag_text, I(0), sizeof(Text_t));
        }
        return tags;
    }
    case TableType: return List(Text("length"), Text("keys"), Text("values"), Text("fallback"));
    case ListType: return List(Text("length"));
    default: {
        env_t *ns_env = get_namespace_by_type(env, t);
        List_t fields = EMPTY_LIST;
        if (ns_env == NULL) return fields; // No namespace to draw suggestions from
        for (int64_t i = 0; i < (int64_t)ns_env->locals->entries.length; i++) {
            struct {
                const char *key;
                binding_t *value;
            } *entry = (ns_env->locals->entries.data + i * ns_env->locals->entries.stride);
            if (entry->value->type->tag == FunctionType || entry->value->type->tag == ClosureType) continue;
            Text_t name = Text$from_str(entry->key);
            List$insert(&fields, &name, I(0), sizeof(Text_t));
        }
        return fields;
    }
    }
}

List_t get_method_names(env_t *env, type_t *t) {
    t = value_type(t);
    switch (t->tag) {
    case PointerType: return get_method_names(env, Match(t, PointerType)->pointed);
    case OptionalType: return get_method_names(env, Match(t, OptionalType)->type);
    case ListType: {
        return List(Text("binary_search"), Text("by"), Text("clear"), Text("counts"), Text("find"), Text("where"),
                    Text("from"), Text("has"), Text("heap_pop"), Text("heap_push"), Text("heapify"), Text("insert"),
                    Text("insert_all"), Text("pairs"), Text("pop"), Text("random"), Text("remove_at"),
                    Text("remove_item"), Text("reversed"), Text("sample"), Text("shuffle"), Text("shuffled"),
                    Text("slice"), Text("sort"), Text("sorted"), Text("swap"), Text("to"), Text("unique"));
    }
    case TableType: {
        return List(Text("clear"), Text("entries"), Text("get"), Text("get_or_set"), Text("has"), Text("remove"),
                    Text("set"), Text("sorted"), Text("with_fallback"), Text("without"), Text("intersection"),
                    Text("difference"), Text("with"));
    }
    default: {
        env_t *ns_env = get_namespace_by_type(env, t);
        List_t methods = EMPTY_LIST;
        if (ns_env == NULL) return methods; // No namespace to draw suggestions from
        for (int64_t i = 0; i < (int64_t)ns_env->locals->entries.length; i++) {
            struct {
                const char *key;
                binding_t *value;
            } *entry = (ns_env->locals->entries.data + i * ns_env->locals->entries.stride);
            if (entry->value->type->tag != FunctionType && entry->value->type->tag != ClosureType) continue;
            Text_t name = Text$from_str(entry->key);
            List$insert(&methods, &name, I(0), sizeof(Text_t));
        }
        return methods;
    }
    }
}