path: root/boot/lower.c

/*
 * lowering pass to create an ir from a catskill source tree.
 *
 * the idea is to fully de-sugar a catskill source file
 * into an ir that can be very easily re-expressed into
 * a low-level language, like our transpilation target, c.
 *
 * the lowering pass is itself split into two passes, one
 * initial pass, which collects all top-level type & function
 * declarations to build up a table of all available language objects,
 * and then a second pass going over each function body.
 * this de-couples usage of the functions and types from their ordering
 * allowing for more free-flowing files than c would allow.
 *
 * additionally, we handle type dependencies by collecting every
 * direct reference a type has to another, and topologically
 * sort the types to create the correct ordering of them,
 * pointing out any unbreakable cycles to the user as they come up.
 *
 * Copyright (c) 2026, Mel G. <mel@rnrd.eu>
 *
 * SPDX-License-Identifier: MPL-2.0
 */

#pragma once

#include "catboot.h"

// a single local variable visible in the current scope.
struct Local_Variable
{
    struct String name;
    struct Type_Ref type; // TODO: type-check & fill out empty
};

// result of looking up a local that may turn out to be a capture for
// the function we are currently inside.
struct Lower_Local_Lookup_Capture
{
    // was the local found in an enclosing function?
    bool captured;
    // the captured local's declared type
    struct Type_Ref type;
    // which function does this capture belong to?
    struct Function* captured_into;
};

// what kind of scope is this?
// declared on every lexical scope so we can make sure that the scopes are balanced.
enum Scope_Type
{
    SCOPE_TYPE_NONE,

    // the persistent top-level scope. never removed!
    SCOPE_TYPE_UNIT,

    // pushed for each function body, holds parameters.
    SCOPE_TYPE_FUNCTION,

    // any kind of nested block, can hold anything.
    SCOPE_TYPE_BLOCK,
};

// a single lexical scope, pushed onto the context's stack when entering
// a block and popped when leaving it.
// the scope controls the visibility of every single language
// object (functions, types and variables).
// all objects are present in the unit's global object tables, however
// just because an object is registered does not mean that the current code
// block is allowed to use it. the scope decides the actual visibility of
// the objects, every top-level declaration is listed in the bottom-most
// scope, while other scopes contain local variables, types and functions.
// NOTE: though all top-most declarations are order-independent, the local
// objects have to be declared in the correct order, just like any other
// statements.
struct Scope
{
    enum Scope_Type type;
    Array(struct Local_Variable) variables;

    // function this scope is lexically contained in.
    // for function scopes, references the function itself,
    // for block scopes, references the enclosing function.
    // used to check whether references cross function scope boundary,
    // signifying a closure capture.
    struct Function* containing_function;

    // TODO: add local closure functions & local types.
};

struct Lower_Context
{
    // the translation unit being created
    struct Unit* unit;

    // monotonic counter of synthesized types
    uint synthetic_type_counter;

    // monotonic counter for other synthetic objects (lambdas, temporaries).
    uint synthetic_counter;

    // stack of lexical scopes.
    // all top-level declarations are stored are stored in the first unit scope.
    Array(struct Scope) scope_stack;
};

void
lower_push_error(struct Unit* unit, struct Lower_Error err)
{
    array_push(&unit->lower_errors, &err);
    unit->had_error = true;
}

// render the cycle's chain to a nice human-y message.
void
lower_format_cycle_chain(
    struct String_Buffer* buf, struct Unit* unit, struct Source_File source, Array(Type_Id) * chain)
{
    uint n = array_length(chain);
    for (uint k = 0; k < n; ++k) {
        Type_Id current_id = *array_at(Type_Id, chain, k);
        Type_Id next_id = *array_at(Type_Id, chain, (k + 1) % n);
        struct Type* current = *array_at(struct Type*, &unit->types.entries, current_id);
        struct Type* next = *array_at(struct Type*, &unit->types.entries, next_id);
        uint line, column;
        source_position_from_span(source.source, current->span, &line, &column);

        if (k > 0) string_buffer_appendf(buf, "\n");
        string_buffer_appendf(
            buf, "  %S (line %lu) depends on %S", STR(current->name), line, STR(next->name));
    }
}

// turn a structured lower error into a displayable diagnostic.
struct Diagnostic
lower_error_to_diagnostic(struct Lower_Error* err, struct Unit* unit, struct Source_File source)
{
    struct Diagnostic d = { .severity = DIAGNOSTIC_ERROR, .span = err->span };
    switch (err->kind) {
    case LOWER_ERROR_UNDEFINED_TYPE:
        d.message = string_format("undefined type '%S'", STR(err->name));
        return d;
    case LOWER_ERROR_DUPLICATE_TYPE:
        d.message = string_format("duplicate type '%S'", STR(err->name));
        return d;
    case LOWER_ERROR_DUPLICATE_FUNCTION:
        d.message = string_format("duplicate function '%S'", STR(err->name));
        return d;
    case LOWER_ERROR_NAME_SHADOWS:
        d.message = string_format("name '%S' shadows an existing binding", STR(err->name));
        return d;
    case LOWER_ERROR_TYPE_CYCLE: {
        struct String_Buffer buf = string_buffer_new(512);
        string_buffer_appendf(&buf, "type cycle detected\n");
        lower_format_cycle_chain(&buf, unit, source, &err->cycle_chain);
        d.message = string_buffer_to_string(&buf);
        d.hint = string_from_static_c_string(
            "break the cycle with a reference (use `&T` instead of `T`)");
        return d;
    }
    case LOWER_ERROR_ASSIGNMENT_AS_EXPRESSION:
        d.message = string_from_static_c_string("assignment cannot appear as an expression");
        return d;
    case LOWER_ERROR_RANGE_OUTSIDE_LOOP:
        d.message =
            string_from_static_c_string("range expressions are only valid in loop initializers");
        return d;
    case LOWER_ERROR_CONSTRUCT_SUBJECT_NOT_NAME:
        d.message = string_from_static_c_string("construction subject must be a type name");
        return d;
    case LOWER_ERROR_TYPE_EXPRESSION_IN_BODY:
        d.message =
            string_from_static_c_string("type expression not allowed inside a function body");
        return d;
    case LOWER_ERROR_UNSUPPORTED_TOP_LEVEL:
        d.message = string_from_static_c_string("unsupported top-level statement");
        return d;
    case LOWER_ERROR_UNKNOWN_LOOP_STYLE:
        d.message = string_from_static_c_string("unknown loop style");
        return d;
    case LOWER_ERROR_UNKNOWN_COMPOUND_ASSIGN:
        d.message = string_from_static_c_string("unknown compound assignment operator");
        return d;
    case LOWER_ERROR_UNKNOWN_NAMED_ARGUMENT:
        d.message = string_format("no parameter named '%S'", STR(err->name));
        return d;
    case LOWER_ERROR_DUPLICATE_ARGUMENT:
        d.message = string_format("argument for '%S' supplied more than once", STR(err->name));
        return d;
    case LOWER_ERROR_TOO_MANY_ARGUMENTS:
        d.message = string_from_static_c_string("too many arguments");
        return d;
    case LOWER_ERROR_NAMED_ARGUMENT_ON_UNKNOWN_CALLEE:
        d.message =
            string_from_static_c_string("named arguments only work on functions we can see");
        return d;
    case LOWER_ERROR_UNIMPLEMENTED:
        d.message = string_format("unimplemented: %S", STR(err->detail));
        return d;
    default:
        d.message = string_from_static_c_string("unknown lower error");
        return d;
    }
}

bool
lower_type_lookup_by_name(struct Unit* unit, struct String name, Type_Id* out_id)
{
    FOR_EACH_ARRAY (struct Type_Name_To_Id, mapping, &unit->types.by_name) {
        if (string_equals(mapping->name, name)) {
            *out_id = mapping->id;
            return true;
        }
    }
    return false;
}

bool
lower_function_lookup_by_name(struct Unit* unit, struct String name, Function_Id* out_id)
{
    FOR_EACH_ARRAY (struct Function_Name_To_Id, mapping, &unit->functions.by_name) {
        if (string_equals(mapping->name, name)) {
            *out_id = mapping->id;
            return true;
        }
    }
    return false;
}

// registers a basic type object for a primitive, so other types
// can depend on it and reference it in the same manner as any other type.
Type_Id
lower_seed_primitive(struct Unit* unit, const ascii* name)
{
    Type_Id id = array_length(&unit->types.entries);
    struct String name_str = string_from_static_c_string(name);
    struct Type* type = type_new(id, TYPE_PRIMITIVE, name_str, span_empty());
    array_push(&unit->types.entries, &type);

    struct Type_Name_To_Id mapping = { .name = name_str, .id = id };
    array_push(&unit->types.by_name, &mapping);

    return id;
}

// structural fingerprint for a source type.
// two type objects describing the same type shape should always
// produce identical fingerprints.
struct String
lower_type_fingerprint(struct Tree_Type* tree_type)
{
    if (!tree_type || tree_type->type == TREE_TYPE_NONE) return string_from_static_c_string("void");

    switch (tree_type->type) {
    case TREE_TYPE_NAME:
        return tree_type->value.name.name;
    case TREE_TYPE_REFERENCE:
        return string_concatenate(
            ARG_ASCII, "ref(", ARG_STRING,
            lower_type_fingerprint(tree_type->value.reference.referenced_type), ARG_ASCII, ")",
            ARG_END);
    case TREE_TYPE_MAYBE:
        return string_concatenate(
            ARG_ASCII, "maybe(", ARG_STRING,
            lower_type_fingerprint(tree_type->value.maybe.inner_type), ARG_ASCII, ")", ARG_END);
    case TREE_TYPE_ARRAY:
        return string_concatenate(
            ARG_ASCII, "array(", ARG_STRING,
            lower_type_fingerprint(tree_type->value.array.element_type), ARG_ASCII, ")", ARG_END);
    case TREE_TYPE_TUPLE: {
        struct String_Buffer buf = string_buffer_new(256);
        string_buffer_append_c_str(&buf, "tuple(");
        bool first = true;
        FOR_EACH (struct Tree_Type*, current, tree_type->value.tuple.head) {
            if (!first) string_buffer_append_c_str(&buf, ",");
            string_buffer_append(&buf, lower_type_fingerprint(current));
            first = false;
        }
        string_buffer_append_c_str(&buf, ")");
        return string_buffer_to_string(&buf);
    }
    case TREE_TYPE_STRUCTURE: {
        struct String_Buffer buf = string_buffer_new(256);
        string_buffer_append_c_str(&buf, "struct(");
        bool first = true;
        FOR_EACH (struct Tree_Type*, field, tree_type->value.structure.fields) {
            if (!first) string_buffer_append_c_str(&buf, ",");
            string_buffer_append(&buf, field->value_name);
            string_buffer_append_c_str(&buf, ":");
            string_buffer_append(&buf, lower_type_fingerprint(field));
            first = false;
        }
        string_buffer_append_c_str(&buf, ")");
        return string_buffer_to_string(&buf);
    }
    case TREE_TYPE_FUNCTION: {
        struct String_Buffer buf = string_buffer_new(256);
        string_buffer_append_c_str(&buf, "fun(");
        string_buffer_append(
            &buf, lower_type_fingerprint(tree_type->value.function.header.return_type));
        string_buffer_append_c_str(&buf, ";");
        bool first = true;
        FOR_EACH (
            struct Tree_Type*, param, tree_type->value.function.header.parameters_type_and_name) {
            if (!first) string_buffer_append_c_str(&buf, ",");
            string_buffer_append(&buf, lower_type_fingerprint(param));
            first = false;
        }
        string_buffer_append_c_str(&buf, ")");
        return string_buffer_to_string(&buf);
    }
    default:
        return string_from_static_c_string("unknown");
    }
}

struct Type_Ref lower_intern_type_ref(struct Lower_Context* ctx, struct Tree_Type* tree_type);

// adds a hard dependency on a type to a type object.
// only by-value references count as hard dependencies,
// anything else makes this a no-op.
void
lower_add_dependency(struct Type* type, struct Type_Ref ref)
{
    if (array_length(&ref.mods) > 0) {
        enum Type_Modifier outer = *array_at(enum Type_Modifier, &ref.mods, 0);
        if (outer == TYPE_MOD_REFERENCE) return;
    }
    array_push(&type->depends_on, &ref.type_id);
}

// create a synthetic type name for a structural type.
struct String
lower_synthesize_type_name(struct Lower_Context* ctx)
{
    const ascii* synthetic_type_name_template = "__cat_type_%lu";

    ascii name_buf[64];
    snprintf(
        name_buf, sizeof name_buf, synthetic_type_name_template, ctx->synthetic_type_counter++);
    return string_from_c_string(name_buf);
}

// create a synthetic name for some non-type object, e.g. a lifted lambda.
// `kind` is a short tag baked into the name for easier observability.
struct String
lower_synthesize_name(struct Lower_Context* ctx, const ascii* kind)
{
    ascii name_buf[64];
    snprintf(name_buf, sizeof name_buf, "__cat_%s_%lu", kind, ctx->synthetic_counter++);
    return string_from_c_string(name_buf);
}

// look up an existing structural synthetic by hash, or build a fresh one.
// inner type references are interned, contributing to dependencies.
Type_Id
lower_synthesize_structural(struct Lower_Context* ctx, struct Tree_Type* tree_type, uint64 hash)
{
    FOR_EACH_ARRAY (struct Type_Hash_To_Id, mapping, &ctx->unit->types.by_hash) {
        if (mapping->hash == hash) return mapping->id;
    }

    Type_Id id = array_length(&ctx->unit->types.entries);
    struct String name = lower_synthesize_type_name(ctx);

    struct Type* type = type_new(id, TYPE_NONE, name, tree_type->span);
    type->synthetic = true;
    type->structural_hash = hash;
    type->depends_on = array_new(Type_Id, 16);
    array_push(&ctx->unit->types.entries, &type);

    struct Type_Hash_To_Id mapping = { .hash = hash, .id = id };
    array_push(&ctx->unit->types.by_hash, &mapping);

    switch (tree_type->type) {
    case TREE_TYPE_MAYBE: {
        // `T?` -> `struct { bool present; T value; }`
        type->kind = TYPE_STRUCTURE;

        type->value.structure.fields = array_new(struct Field, 4);

        struct Field present_f = {
            .name = string_from_static_c_string("present"),
            .type = {
                .type_id = ctx->unit->types.primitive_bool_id,
                .mods = array_new(enum Type_Modifier, 1),
            },
        };
        array_push(&type->value.structure.fields, &present_f);
        Type_Id bool_id = ctx->unit->types.primitive_bool_id;
        array_push(&type->depends_on, &bool_id);

        struct Field value_f = {
            .name = string_from_static_c_string("value"),
            .type = lower_intern_type_ref(ctx, tree_type->value.maybe.inner_type),
        };
        array_push(&type->value.structure.fields, &value_f);
        lower_add_dependency(type, value_f.type); // possibly hard dependency
        break;
    }
    case TREE_TYPE_ARRAY: {
        // `[T]` -> `struct { &T data; uint length; }`
        type->kind = TYPE_STRUCTURE;

        type->value.structure.fields = array_new(struct Field, 4);

        struct Type_Ref inner = lower_intern_type_ref(ctx, tree_type->value.array.element_type);
        struct Type_Ref data_ref = type_ref_bare(inner.type_id);
        FOR_EACH_ARRAY (enum Type_Modifier, m, &inner.mods) array_push(&data_ref.mods, m);
        enum Type_Modifier ptr = TYPE_MOD_REFERENCE;
        array_push(&data_ref.mods, &ptr);

        struct Field data_f = {
            .name = string_from_static_c_string("data"),
            .type = data_ref,
        };
        array_push(&type->value.structure.fields, &data_f);
        // no dependency

        struct Field length_f = {
            .name = string_from_static_c_string("length"),
            .type = {
                .type_id = ctx->unit->types.primitive_uint_id,
                .mods = array_new(enum Type_Modifier, 1),
            },
        };
        array_push(&type->value.structure.fields, &length_f);
        Type_Id uint_id = ctx->unit->types.primitive_uint_id;
        array_push(&type->depends_on, &uint_id);
        break;
    }
    case TREE_TYPE_TUPLE: {
        // `(T1, T2, ...)` -> `struct { T1 _0; T2 _1; ... }`
        type->kind = TYPE_STRUCTURE;

        type->value.structure.fields = array_new(struct Field, 16);
        uint idx = 0;
        FOR_EACH (struct Tree_Type*, current, tree_type->value.tuple.head) {
            ascii field_buf[16];
            snprintf(field_buf, sizeof field_buf, "_%lu", idx++);
            struct Field f = {
                .name = string_from_c_string(field_buf),
                .type = lower_intern_type_ref(ctx, current),
            };
            array_push(&type->value.structure.fields, &f);
            lower_add_dependency(type, f.type); // possibly hard dependency for each element
        }
        break;
    }
    case TREE_TYPE_STRUCTURE: {
        // `{ x, y T }` -> `struct { uint x; uint y; }`
        type->kind = TYPE_STRUCTURE;

        type->value.structure.fields = array_new(struct Field, 16);
        FOR_EACH (struct Tree_Type*, tree_field, tree_type->value.structure.fields) {
            struct Field f = {
                .name = tree_field->value_name,
                .type = lower_intern_type_ref(ctx, tree_field),
            };
            array_push(&type->value.structure.fields, &f);
            lower_add_dependency(type, f.type); // possibly hard dependency for each field
        }
        break;
    }
    case TREE_TYPE_FUNCTION: {
        // `fun x(n X) Y` -> `Y x(X n) {}`
        type->kind = TYPE_FUNCTION;

        struct Tree_Function_Header* header = &tree_type->value.function.header;

        type->value.function.return_type = lower_intern_type_ref(ctx, header->return_type);
        // possibly hard dependency on return type
        lower_add_dependency(type, type->value.function.return_type);

        type->value.function.params = array_new(struct Type_Ref, 16);
        bool variadic = false;
        FOR_EACH (struct Tree_Type*, param, header->parameters_type_and_name) {
            struct Type_Ref ref = lower_intern_type_ref(ctx, param);
            array_push(&type->value.function.params, &ref);
            lower_add_dependency(type, ref); // possibly hard dependency for parameter
            if (param->variadic) variadic = true;
        }
        type->value.function.variadic = variadic;
        break;
    }
    default:
        // unreachable!
        break;
    }

    return id;
}

// turns a source type expression into a concrete type reference object.
// resolves named types from the type table, peels out reference modifiers,
// and synthesizes new entries for structural type shapes.
struct Type_Ref
lower_intern_type_ref(struct Lower_Context* ctx, struct Tree_Type* tree_type)
{
    struct Type_Ref ref = type_ref_bare(ctx->unit->types.primitive_void_id);

    if (!tree_type || tree_type->type == TREE_TYPE_NONE) return ref;

    struct Tree_Type* current = tree_type;
    while (current && current->type == TREE_TYPE_REFERENCE) {
        enum Type_Modifier mod = TYPE_MOD_REFERENCE;
        array_push(&ref.mods, &mod);
        current = current->value.reference.referenced_type;
    }

    if (!current || current->type == TREE_TYPE_NONE) return ref;

    switch (current->type) {
    case TREE_TYPE_NAME: {
        Type_Id id;
        if (lower_type_lookup_by_name(ctx->unit, current->value.name.name, &id)) {
            ref.type_id = id;
        } else {
            lower_push_error(
                ctx->unit,
                (struct Lower_Error){
                    .kind = LOWER_ERROR_UNDEFINED_TYPE,
                    .span = current->span,
                    .name = current->value.name.name,
                });
        }
        return ref;
    }
    case TREE_TYPE_MAYBE:
    case TREE_TYPE_ARRAY:
    case TREE_TYPE_TUPLE:
    case TREE_TYPE_STRUCTURE:
    case TREE_TYPE_FUNCTION: {
        struct String fp = lower_type_fingerprint(current);
        uint64 hash = fnv1a_64(fp);
        ref.type_id = lower_synthesize_structural(ctx, current, hash);
        return ref;
    }
    case TREE_TYPE_MAP:
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_UNIMPLEMENTED,
                .span = current->span,
                .detail = string_from_static_c_string("map types"),
            });
        return ref;
    default:
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_UNIMPLEMENTED,
                .span = current->span,
                .detail = string_from_static_c_string("this type form"),
            });
        return ref;
    }
}

// is this source statement a function?
// if it is, unwrap it and return true, otherwise false.
bool
lower_match_function_decl(
    struct Tree_Statement* stmt, struct String* out_name, struct Tree_Expression** out_fn_expr)
{
    if (stmt->kind != TREE_STATEMENT_EXPRESSION) return false;
    struct Tree_Expression* expr = stmt->value.expression.inner;
    if (!expr || expr->kind != TREE_EXPRESSION_BINARY_OPERATION) return false;
    if (expr->value.binary_operator.operation != BINARY_ASSIGN) return false;

    struct Tree_Expression* lhs = expr->value.binary_operator.left_operand;
    struct Tree_Expression* rhs = expr->value.binary_operator.right_operand;
    if (!lhs || lhs->kind != TREE_EXPRESSION_NAME) return false;
    if (!rhs || rhs->kind != TREE_EXPRESSION_FUNCTION) return false;

    *out_name = lhs->value.name.name;
    *out_fn_expr = rhs;
    return true;
}

// is this source statement a type?
// if it is, unwrap it and return true, otherwise false.
bool
lower_match_type_decl(
    struct Tree_Statement* stmt, struct String* out_name, struct Tree_Type** out_tree_type)
{
    if (stmt->kind != TREE_STATEMENT_EXPRESSION) return false;
    struct Tree_Expression* expr = stmt->value.expression.inner;
    if (!expr || expr->kind != TREE_EXPRESSION_BINARY_OPERATION) return false;
    if (expr->value.binary_operator.operation != BINARY_ASSIGN) return false;

    struct Tree_Expression* lhs = expr->value.binary_operator.left_operand;
    struct Tree_Expression* rhs = expr->value.binary_operator.right_operand;
    if (!lhs || lhs->kind != TREE_EXPRESSION_NAME) return false;
    if (!rhs || rhs->kind != TREE_EXPRESSION_TYPE) return false;

    *out_name = lhs->value.name.name;
    *out_tree_type = rhs->value.type.type;
    return true;
}

// register a function shell object, only listing a name and assigning a unique identifier.
bool
lower_register_function_shell(struct Unit* unit, struct String name, struct Span span)
{
    Function_Id existing;
    if (lower_function_lookup_by_name(unit, name, &existing)) {
        lower_push_error(
            unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_DUPLICATE_FUNCTION, .span = span, .name = name });
        return false;
    }

    Function_Id id = array_length(&unit->functions.entries);
    struct Function* fn = function_new(id, name);
    array_push(&unit->functions.entries, &fn);

    struct Function_Name_To_Id mapping = { .name = name, .id = id };
    array_push(&unit->functions.by_name, &mapping);
    return true;
}

// register a type shell object, only listing a name and assigning a unique identifier.
// used to resolve references to types which are defined out-of-order in the source.
bool
lower_register_type_shell(struct Unit* unit, struct String name, struct Span span)
{
    Type_Id existing;
    if (lower_type_lookup_by_name(unit, name, &existing)) {
        lower_push_error(
            unit,
            (struct Lower_Error){ .kind = LOWER_ERROR_DUPLICATE_TYPE, .span = span, .name = name });
        return false;
    }

    Type_Id id = array_length(&unit->types.entries);
    struct Type* type = type_new(id, TYPE_NONE, name, span);
    type->depends_on = array_new(Type_Id, 16);
    array_push(&unit->types.entries, &type);

    struct Type_Name_To_Id mapping = { .name = name, .id = id };
    array_push(&unit->types.by_name, &mapping);
    return true;
}

void
lower_fill_function_signature(
    struct Lower_Context* ctx, struct Function* fn, struct Tree_Expression* fn_expr)
{
    fn->is_main = string_equals_c_str(fn->name, "main");
    fn->return_type = lower_intern_type_ref(ctx, fn_expr->value.function.header.return_type);
    fn->params = array_new(struct Param, 16);

    bool variadic = false;
    FOR_EACH (
        struct Tree_Type*, param_type, fn_expr->value.function.header.parameters_type_and_name) {
        struct Param p = {
            .name = param_type->value_name,
            .type = lower_intern_type_ref(ctx, param_type),
        };
        array_push(&fn->params, &p);
        if (param_type->variadic) variadic = true;
    }
    fn->variadic = variadic;
    fn->main_takes_args = fn->is_main && array_length(&fn->params) > 0;
    fn->ast_header = &fn_expr->value.function.header;
    fn->ast_body = &fn_expr->value.function.body;
    fn->body = nil;
}

// synthesize the function's signature as a structural closure type
// the first time the function is referenced in value context, or reuse already
// synthesized type.
Type_Id
lower_function_closure_type(struct Lower_Context* ctx, struct Function* fn)
{
    if (fn->closure_type_id != 0) return fn->closure_type_id;

    struct Tree_Type wrapper = {
        .type = TREE_TYPE_FUNCTION,
        .value = { .function = { .header = *fn->ast_header } },
        .span = fn->ast_header->span,
        .location = fn->ast_header->location,
    };
    struct Type_Ref ref = lower_intern_type_ref(ctx, &wrapper);
    fn->closure_type_id = ref.type_id;
    return ref.type_id;
}

// synthesize the per-lambda state struct that carries pointers to each
// captured local.
// each captured local is stored by reference.
// NOTE(mel): the transpiler pass will output this as a normal structure,
// does it make sense to distinguish these state types as something else?
// it muddles distinguishing a type that the user wrote, and a type we synthesized.
Type_Id
lower_function_capture_state_type(struct Lower_Context* ctx, struct Function* fn)
{
    if (fn->capture_state_type_id != 0) return fn->capture_state_type_id;
    if (array_length(&fn->captures) == 0) return 0;

    Type_Id id = array_length(&ctx->unit->types.entries);
    struct String name = lower_synthesize_type_name(ctx);
    struct Type* type = type_new(id, TYPE_STRUCTURE, name, fn->ast_header->span);
    type->synthetic = true;
    type->depends_on = array_new(Type_Id, 8);
    type->value.structure.fields = array_new(struct Field, 8);

    FOR_EACH_ARRAY (struct Capture, cap, &fn->captures) {
        // each field carries a pointer to the captured local. peel any
        // existing modifiers off the captured type and prepend a reference.
        // TODO: correctly nest all modifiers here!
        struct Type_Ref ptr = {
            .type_id = cap->type.type_id,
            .mods = array_new(enum Type_Modifier, 4),
        };
        enum Type_Modifier ref_mod = TYPE_MOD_REFERENCE;
        array_push(&ptr.mods, &ref_mod);
        FOR_EACH_ARRAY (enum Type_Modifier, mod, &cap->type.mods) array_push(&ptr.mods, mod);

        struct Field f = { .name = cap->name, .type = ptr };
        array_push(&type->value.structure.fields, &f);
    }

    array_push(&ctx->unit->types.entries, &type);
    fn->capture_state_type_id = id;
    return id;
}

void
lower_fill_type_body(struct Lower_Context* ctx, struct Type* type, struct Tree_Type* tree_type)
{
    switch (tree_type->type) {
    case TREE_TYPE_NAME: {
        type->kind = TYPE_ALIAS;
        Type_Id target_id;
        if (lower_type_lookup_by_name(ctx->unit, tree_type->value.name.name, &target_id)) {
            type->value.alias.target_id = target_id;
            // aliases always need their target's full definition.
            array_push(&type->depends_on, &target_id);
        } else {
            lower_push_error(
                ctx->unit,
                (struct Lower_Error){
                    .kind = LOWER_ERROR_UNDEFINED_TYPE,
                    .span = tree_type->span,
                    .name = tree_type->value.name.name,
                });
        }
        break;
    }
    case TREE_TYPE_STRUCTURE: {
        type->kind = TYPE_STRUCTURE;
        type->value.structure.fields = array_new(struct Field, 16);
        FOR_EACH (struct Tree_Type*, tree_field, tree_type->value.structure.fields) {
            struct Field f = {
                .name = tree_field->value_name,
                .type = lower_intern_type_ref(ctx, tree_field),
            };
            array_push(&type->value.structure.fields, &f);
            lower_add_dependency(type, f.type);
        }
        break;
    }
    case TREE_TYPE_VARIANT: {
        type->kind = TYPE_VARIANT;
        type->value.variant.cases = array_new(struct Variant_Case, 16);
        uint32 next_tag = 0;
        FOR_EACH (struct Tree_Type*, tree_case, tree_type->value.variant.variants) {
            struct Variant_Case c = {
                .name = tree_case->value_name,
                .tag = next_tag++,
                .has_payload = tree_case->type != TREE_TYPE_NONE,
                .payload = { 0 },
            };
            if (c.has_payload) {
                c.payload = lower_intern_type_ref(ctx, tree_case);
                lower_add_dependency(type, c.payload);
            }
            array_push(&type->value.variant.cases, &c);
        }
        break;
    }
    case TREE_TYPE_FUNCTION: {
        type->kind = TYPE_FUNCTION;
        struct Tree_Function_Header* header = &tree_type->value.function.header;
        type->value.function.return_type = lower_intern_type_ref(ctx, header->return_type);
        lower_add_dependency(type, type->value.function.return_type);
        type->value.function.params = array_new(struct Type_Ref, 16);

        bool variadic = false;
        FOR_EACH (struct Tree_Type*, param_type, header->parameters_type_and_name) {
            struct Type_Ref ref = lower_intern_type_ref(ctx, param_type);
            array_push(&type->value.function.params, &ref);
            lower_add_dependency(type, ref);
            if (param_type->variadic) variadic = true;
        }
        type->value.function.variadic = variadic;
        break;
    }
    case TREE_TYPE_CLASS:
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_UNIMPLEMENTED,
                .span = tree_type->span,
                .detail = string_from_static_c_string("class types"),
            });
        break;
    default: {
        // this is a type alias assigning a name to a structural type.
        // create a new synthetic type, and point our type as alias towards it.
        struct Type_Ref ref = lower_intern_type_ref(ctx, tree_type);
        type->kind = TYPE_ALIAS;
        type->value.alias.target_id = ref.type_id;
        array_push(&type->depends_on, &ref.type_id);
        break;
    }
    }
}

// lowering pass 1, sub-pass a
// collection of every single declaration of a type or function,
// alongside with initial registration of any referenced dependencies.
void
lower_pass_1_register_shells(struct Unit* unit, struct Tree* tree)
{
    FOR_EACH (struct Tree_Statement*, stmt, tree->top_level_statements) {
        struct String name;

        struct Tree_Expression* fn_expr;
        if (lower_match_function_decl(stmt, &name, &fn_expr)) {
            lower_register_function_shell(unit, name, stmt->span);
            continue;
        }

        struct Tree_Type* tree_type;
        if (lower_match_type_decl(stmt, &name, &tree_type)) {
            lower_register_type_shell(unit, name, stmt->span);
            continue;
        }
    }
}

// lowering pass 1, sub-pass b
// walking over all top-level functions and types, fully filling out
// their definitions.
// now that sub-pass a has registered all top-level definitions, we can
// finally build out the type reference dag within the translation unit.
void
lower_pass_1_fill_bodies(struct Lower_Context* ctx, struct Tree* tree)
{
    FOR_EACH (struct Tree_Statement*, stmt, tree->top_level_statements) {
        struct String name;

        struct Tree_Expression* fn_expr;
        if (lower_match_function_decl(stmt, &name, &fn_expr)) {
            Function_Id id;
            if (lower_function_lookup_by_name(ctx->unit, name, &id)) {
                struct Function* fn =
                    *array_at(struct Function*, &ctx->unit->functions.entries, id);
                if (!fn->ast_body) lower_fill_function_signature(ctx, fn, fn_expr);
            }
            continue;
        }

        struct Tree_Type* tree_type;
        if (lower_match_type_decl(stmt, &name, &tree_type)) {
            Type_Id id;
            if (lower_type_lookup_by_name(ctx->unit, name, &id)) {
                struct Type* type = *array_at(struct Type*, &ctx->unit->types.entries, id);
                if (type->kind == TYPE_NONE) lower_fill_type_body(ctx, type, tree_type);
            }
            continue;
        }

        if (stmt->kind == TREE_STATEMENT_PRAGMA) {
            for (struct Tree_Pragma* pragma = stmt->value.pragma.inner; pragma;
                 pragma = pragma->next) {
                if (pragma->type == TREE_PRAGMA_C_HEADER && pragma->argument_count >= 1
                    && pragma->arguments[0].type == TREE_PRAGMA_ARGUMENT_NAME_OR_STRING) {
                    struct Import import = {
                        .path = pragma->arguments[0].value.name_or_string,
                        .span = pragma->span,
                    };
                    array_push(&ctx->unit->imports, &import);
                } else {
                    lower_push_error(
                        ctx->unit,
                        (struct Lower_Error){
                            .kind = LOWER_ERROR_UNIMPLEMENTED,
                            .span = pragma->span,
                            .detail = string_from_static_c_string("this pragma kind"),
                        });
                }
            }
            continue;
        }

        lower_push_error(
            ctx->unit,
            (struct Lower_Error){ .kind = LOWER_ERROR_UNSUPPORTED_TOP_LEVEL, .span = stmt->span });
    }
}

// lowering pass 1
// collects all top-level definitions into the translation unit's
// tables and fully maps out the references between them.
void
lower_pass_1(struct Lower_Context* ctx, struct Tree* tree)
{
    lower_pass_1_register_shells(ctx->unit, tree);
    lower_pass_1_fill_bodies(ctx, tree);
}

struct Block* lower_block(struct Lower_Context* ctx, struct Tree_Block* tree_block);
struct Statement* lower_statement(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt);
struct Expression* lower_expression(struct Lower_Context* ctx, struct Tree_Expression* tree_expr);
bool lower_name_is_function_typed_local(struct Lower_Context* ctx, struct String name);
struct Lower_Local_Lookup_Capture
lower_local_lookup_capturing(struct Lower_Context* ctx, struct String name);
void lower_record_capture(struct Function* fn, struct String name, struct Type_Ref type);
void lower_push_scope_function(struct Lower_Context* ctx, struct Function* owner);
void lower_pop_scope(struct Lower_Context* ctx, enum Scope_Type expected);
void lower_declare_local(struct Lower_Context* ctx, struct String name, struct Type_Ref type);

struct Expression*
lower_expression_integer_literal(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    (void)ctx;
    return ir_make_integer(tree_expr->value.integer_literal.value, tree_expr->span);
}

struct Expression*
lower_expression_float_literal(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    (void)ctx;
    return ir_make_float(tree_expr->value.float_literal.value, tree_expr->span);
}

struct Expression*
lower_expression_string_literal(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    (void)ctx;
    return ir_make_string(tree_expr->value.string_literal.value, tree_expr->span);
}

struct Expression*
lower_expression_boolean_literal(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    (void)ctx;
    return ir_make_bool(tree_expr->value.bool_literal.value, tree_expr->span);
}

struct Expression*
lower_expression_name(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    struct String name = tree_expr->value.name.name;

    // names that resolve to a catskill function become a function reference.
    Function_Id fn_id;
    if (lower_function_lookup_by_name(ctx->unit, name, &fn_id)) {
        // since this path is only taken outside direct call-positions,
        // the function will need a closure type to wrap it as a value.
        struct Function* fn = *array_at(struct Function*, &ctx->unit->functions.entries, fn_id);
        Type_Id closure_type_id = lower_function_closure_type(ctx, fn);
        return ir_make_function_ref(fn_id, closure_type_id, tree_expr->span);
    }

    // locals that were defined in an upper function scope are captured.
    struct Lower_Local_Lookup_Capture lookup = lower_local_lookup_capturing(ctx, name);
    if (lookup.captured) {
        lower_record_capture(lookup.captured_into, name, lookup.type);
        return ir_make_capture_ref(name, tree_expr->span);
    }

    // unresolved names will continue being bare names.
    // this is required to account for all non-language objects that might
    // come from c, or the runtime, or some c-header include we can't see.
    // the backend will note any name reference which is still unresolved
    // after taking every source into account.
    return ir_make_name(name, tree_expr->span);
}

// any groups are discarded in the lowered representation, their presence
// just yields different expression constructions.
// if required by precedence the final transpiler will handle them by itself.
struct Expression*
lower_expression_group(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    return lower_expression(ctx, tree_expr->value.group.inner_expression);
}

struct Expression*
lower_expression_unary_operation(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    return ir_make_unary(
        tree_expr->value.unary_operator.operation,
        lower_expression(ctx, tree_expr->value.unary_operator.operand), tree_expr->span);
}

struct Expression*
lower_expression_binary_operation(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    enum Binary_Operation op = tree_expr->value.binary_operator.operation;
    // TODO: maybe we want to support assignment expressions some day. today they aren't.
    if (op >= BINARY_ASSIGN) {
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_ASSIGNMENT_AS_EXPRESSION,
                .span = tree_expr->span,
            });
        return nil;
    }
    if (op == BINARY_RANGE) {
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_RANGE_OUTSIDE_LOOP, .span = tree_expr->span });
        return nil;
    }
    return ir_make_binary(
        op, lower_expression(ctx, tree_expr->value.binary_operator.left_operand),
        lower_expression(ctx, tree_expr->value.binary_operator.right_operand), tree_expr->span);
}

// find the index of `name` in `names`, or `array_length(names)` if absent.
uint
lower_find_slot_by_name(Array(struct String) names, struct String name)
{
    uint count = array_length(&names);
    for (uint j = 0; j < count; ++j) {
        if (string_equals(*array_at(struct String, &names, j), name)) return j;
    }
    return count;
}

// find the index of the leftmost unclaimed slot in `claimed`,
// or its length if no slot is free.
uint
lower_find_leftmost_unclaimed(Array(bool) claimed)
{
    uint count = array_length(&claimed);
    for (uint j = 0; j < count; ++j) {
        if (!*array_at(bool, &claimed, j)) return j;
    }
    return count;
}

// resolve a call's argument list. named args claim their named slot,
// positional args fill the leftmost unclaimed slot. extras (positionals
// past the last slot) land in slots `>= param_count` only when the
// callee is variadic.
bool
lower_resolve_call_arguments(
    struct Lower_Context* ctx, struct Span call_span, struct Tree_Argument_Group* group,
    Array(struct String) param_names, bool variadic, Array(struct Call_Argument) * out_arguments)
{
    uint param_count = array_length(&param_names);
    *out_arguments = array_new(struct Call_Argument, 16);

    Array(bool) claimed = array_new(bool, param_count > 0 ? param_count : 1);
    for (uint i = 0; i < param_count; ++i) {
        bool f = false;
        array_push(&claimed, &f);
    }
    uint extra_slot = param_count;
    bool ok = true;

    uint i = 0;
    FOR_EACH (struct Tree_Expression*, arg, group->arguments) {
        struct String name = string_empty();
        if (i < array_length(&group->argument_names))
            name = *array_at(struct String, &group->argument_names, i);
        ++i;

        uint slot;
        if (name.length > 0) {
            uint match = lower_find_slot_by_name(param_names, name);
            if (match == param_count) {
                lower_push_error(
                    ctx->unit,
                    (struct Lower_Error){
                        .kind = LOWER_ERROR_UNKNOWN_NAMED_ARGUMENT,
                        .span = call_span,
                        .name = name });
                ok = false;
                continue;
            }
            if (*array_at(bool, &claimed, match)) {
                lower_push_error(
                    ctx->unit,
                    (struct Lower_Error){
                        .kind = LOWER_ERROR_DUPLICATE_ARGUMENT, .span = call_span, .name = name });
                ok = false;
                continue;
            }
            *array_at(bool, &claimed, match) = true;
            slot = match;
        } else {
            uint match = lower_find_leftmost_unclaimed(claimed);
            if (match == param_count) {
                if (!variadic) {
                    lower_push_error(
                        ctx->unit,
                        (struct Lower_Error){
                            .kind = LOWER_ERROR_TOO_MANY_ARGUMENTS, .span = call_span });
                    ok = false;
                    continue;
                }
                slot = extra_slot++;
            } else {
                *array_at(bool, &claimed, match) = true;
                slot = match;
            }
        }

        struct Call_Argument tagged = { .value = lower_expression(ctx, arg), .slot = slot };
        array_push(out_arguments, &tagged);
    }

    return ok;
}

// resolve a struct construction's field list. same rule as calls, but the
// slot here is the target field's name since the transpiler emits via c
// designated initializers and call-site order is fine.
bool
lower_resolve_construct_fields(
    struct Lower_Context* ctx, struct Span call_span, struct Tree_Argument_Group* group,
    Array(struct String) field_names, Array(struct Construct_Field) * out_fields)
{
    uint field_count = array_length(&field_names);
    *out_fields = array_new(struct Construct_Field, 16);

    Array(bool) claimed = array_new(bool, field_count > 0 ? field_count : 1);
    for (uint i = 0; i < field_count; ++i) {
        bool f = false;
        array_push(&claimed, &f);
    }
    bool ok = true;

    uint i = 0;
    FOR_EACH (struct Tree_Expression*, arg, group->arguments) {
        struct String name = string_empty();
        if (i < array_length(&group->argument_names))
            name = *array_at(struct String, &group->argument_names, i);
        ++i;

        struct String resolved;
        if (name.length > 0) {
            uint match = lower_find_slot_by_name(field_names, name);
            if (match == field_count) {
                lower_push_error(
                    ctx->unit,
                    (struct Lower_Error){
                        .kind = LOWER_ERROR_UNKNOWN_NAMED_ARGUMENT,
                        .span = call_span,
                        .name = name });
                ok = false;
                continue;
            }
            if (*array_at(bool, &claimed, match)) {
                lower_push_error(
                    ctx->unit,
                    (struct Lower_Error){
                        .kind = LOWER_ERROR_DUPLICATE_ARGUMENT, .span = call_span, .name = name });
                ok = false;
                continue;
            }
            *array_at(bool, &claimed, match) = true;
            resolved = name;
        } else {
            uint match = lower_find_leftmost_unclaimed(claimed);
            if (match == field_count) {
                lower_push_error(
                    ctx->unit,
                    (struct Lower_Error){
                        .kind = LOWER_ERROR_TOO_MANY_ARGUMENTS, .span = call_span });
                ok = false;
                continue;
            }
            *array_at(bool, &claimed, match) = true;
            resolved = *array_at(struct String, &field_names, match);
        }

        struct Construct_Field field = { .name = resolved, .value = lower_expression(ctx, arg) };
        array_push(out_fields, &field);
    }

    return ok;
}

struct Expression*
lower_expression_call(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    struct Tree_Argument_Group* group = &tree_expr->value.call.argument_group;
    struct Tree_Expression* subject_tree = tree_expr->value.call.subject;

    // only catskill-side functions are in the function table, calls to libc
    // and the like go through as positional with no named args allowed.
    struct Function* callee = nil;
    Function_Id callee_id = 0;
    bool is_indirect = false;
    if (subject_tree && subject_tree->kind == TREE_EXPRESSION_NAME) {
        if (lower_function_lookup_by_name(ctx->unit, subject_tree->value.name.name, &callee_id))
            callee = *array_at(struct Function*, &ctx->unit->functions.entries, callee_id);
        else if (lower_name_is_function_typed_local(ctx, subject_tree->value.name.name))
            is_indirect = true;
    } else if (subject_tree) {
        // any subject that isn't a bare name (member, subscript, call result, closure, anything
        // that's not literally just a name) yields a fat closure value at the call site by default.
        is_indirect = true;
    }

    // for direct calls to a known catskill function, build the reference
    // subject directly so we don't drag the function into value-context synthesis!
    struct Expression* subject =
        callee ? ir_make_function_ref(callee_id, 0, subject_tree->span)
               : lower_expression(ctx, subject_tree);
    Array(struct Call_Argument) arguments;

    if (callee) {
        Array(struct String) param_names = array_new(struct String, array_length(&callee->params));
        FOR_EACH_ARRAY (struct Param, p, &callee->params) array_push(&param_names, &p->name);

        lower_resolve_call_arguments(
            ctx, tree_expr->span, group, param_names, callee->variadic, &arguments);
    } else {
        FOR_EACH_ARRAY (struct String, name, &group->argument_names) {
            if (name->length > 0) {
                lower_push_error(
                    ctx->unit,
                    (struct Lower_Error){
                        .kind = LOWER_ERROR_NAMED_ARGUMENT_ON_UNKNOWN_CALLEE,
                        .span = tree_expr->span });
                return nil;
            }
        }
        arguments = array_new(struct Call_Argument, 16);
        uint slot = 0;
        FOR_EACH (struct Tree_Expression*, arg, group->arguments) {
            struct Call_Argument tagged = { .value = lower_expression(ctx, arg), .slot = slot++ };
            array_push(&arguments, &tagged);
        }
    }

    return ir_make_call(subject, arguments, is_indirect, tree_expr->span);
}

struct Expression*
lower_expression_construct(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    struct Tree_Expression* subject = tree_expr->value.construct.subject;
    if (!subject || subject->kind != TREE_EXPRESSION_NAME) {
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_CONSTRUCT_SUBJECT_NOT_NAME,
                .span = tree_expr->span,
            });
        return nil;
    }
    Type_Id type_id;
    if (!lower_type_lookup_by_name(ctx->unit, subject->value.name.name, &type_id)) {
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_UNDEFINED_TYPE,
                .span = subject->span,
                .name = subject->value.name.name,
            });
        return nil;
    }

    struct Type* type = *array_at(struct Type*, &ctx->unit->types.entries, type_id);
    Array(struct String) field_names = array_new(struct String, 16);
    if (type->kind == TYPE_STRUCTURE) {
        FOR_EACH_ARRAY (struct Field, f, &type->value.structure.fields)
            array_push(&field_names, &f->name);
    }

    Array(struct Construct_Field) fields;
    lower_resolve_construct_fields(
        ctx, tree_expr->span, &tree_expr->value.construct.argument_group, field_names, &fields);

    return ir_make_construct(type_id, fields, tree_expr->span);
}

// type-as-expression is only valid as the right-side of a top-level binding,
// anywhere else it is an error.
struct Expression*
lower_expression_type(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    lower_push_error(
        ctx->unit,
        (struct Lower_Error){
            .kind = LOWER_ERROR_TYPE_EXPRESSION_IN_BODY, .span = tree_expr->span });
    return nil;
}

// anonymous function: lift it up as a synthetic function table entry,
// and emit a function reference so the use site can wrap it as a fat
// closure value.
struct Expression*
lower_expression_function(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    struct String name = lower_synthesize_name(ctx, "lambda");

    // NOTE: we are allowed to register functions whenever we want,
    // even while iterating over them, the pass will eventually get to them.
    if (!lower_register_function_shell(ctx->unit, name, tree_expr->span)) return nil;

    Function_Id id;
    lower_function_lookup_by_name(ctx->unit, name, &id);

    struct Function* fn = *array_at(struct Function*, &ctx->unit->functions.entries, id);
    fn->synthetic = true;
    lower_fill_function_signature(ctx, fn, tree_expr);

    // lower the body inline so name lookups inside see the enclosing
    // function's scope and can detect captures.
    lower_push_scope_function(ctx, fn);
    FOR_EACH_ARRAY (struct Param, param, &fn->params)
        lower_declare_local(ctx, param->name, param->type);
    fn->body = lower_block(ctx, fn->ast_body);
    lower_pop_scope(ctx, SCOPE_TYPE_FUNCTION);

    fn->completed = true; // mark the function as fully lowered.

    // a function literal is always in value context, we can synthesize
    // the closure type eagerly right here.
    Type_Id closure_type_id = lower_function_closure_type(ctx, fn);
    // if the body captured anything, also synthesize the state type.
    lower_function_capture_state_type(ctx, fn);

    return ir_make_function_ref(id, closure_type_id, tree_expr->span);
}

struct Expression*
lower_expression_increment_decrement(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    struct Tree_Expression_Increment_Decrement* incdec = &tree_expr->value.increment_decrement;
    struct Tree_Expression* subject = incdec->subject;
    if (!subject || subject->kind != TREE_EXPRESSION_NAME) {
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_UNIMPLEMENTED,
                .span = tree_expr->span,
                .detail = string_from_static_c_string("increment/decrement on non-trivial lvalue"),
            });
        return nil;
    }
    return ir_make_increment_decrement(
        lower_expression(ctx, subject), incdec->operation, incdec->prefix, tree_expr->span);
}

// turns a source expression into the lowered form.
struct Expression*
lower_expression(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    switch (tree_expr->kind) {
    case TREE_EXPRESSION_INTEGER_LITERAL:
        return lower_expression_integer_literal(ctx, tree_expr);
    case TREE_EXPRESSION_FLOAT_LITERAL:
        return lower_expression_float_literal(ctx, tree_expr);
    case TREE_EXPRESSION_STRING_LITERAL:
        return lower_expression_string_literal(ctx, tree_expr);
    case TREE_EXPRESSION_BOOLEAN_LITERAL:
        return lower_expression_boolean_literal(ctx, tree_expr);
    case TREE_EXPRESSION_NAME:
        return lower_expression_name(ctx, tree_expr);
    case TREE_EXPRESSION_GROUP:
        return lower_expression_group(ctx, tree_expr);
    case TREE_EXPRESSION_UNARY_OPERATION:
        return lower_expression_unary_operation(ctx, tree_expr);
    case TREE_EXPRESSION_BINARY_OPERATION:
        return lower_expression_binary_operation(ctx, tree_expr);
    case TREE_EXPRESSION_CALL:
        return lower_expression_call(ctx, tree_expr);
    case TREE_EXPRESSION_CONSTRUCT:
        return lower_expression_construct(ctx, tree_expr);
    case TREE_EXPRESSION_TYPE:
        return lower_expression_type(ctx, tree_expr);
    case TREE_EXPRESSION_FUNCTION:
        return lower_expression_function(ctx, tree_expr);
    case TREE_EXPRESSION_INCREMENT_DECREMENT:
        return lower_expression_increment_decrement(ctx, tree_expr);
    case TREE_EXPRESSION_SUBSCRIPT:
    case TREE_EXPRESSION_MEMBER:
    case TREE_EXPRESSION_TRY:
    case TREE_EXPRESSION_MUST:
        // TODO: implement these
    default:
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_UNIMPLEMENTED,
                .span = tree_expr->span,
                .detail = string_from_static_c_string("this expression kind"),
            });
        return nil;
    }
}

// look up the function whose body we are currently inside. (if there is one)
struct Function*
lower_current_function(struct Lower_Context* ctx)
{
    if (ctx->scope_stack.length == 0) return nil;
    struct Scope* top = array_at(struct Scope, &ctx->scope_stack, ctx->scope_stack.length - 1);
    return top->containing_function;
}

// push a fresh lexical scope onto the lowering stack.
// do not forget to also pop this scope once we leave it!
void
lower_push_scope(struct Lower_Context* ctx, enum Scope_Type type)
{
    struct Scope s = {
        .type = type,
        .variables = array_new(struct Local_Variable, 16),
        // block scopes inherit the function from their upper scope
        .containing_function = lower_current_function(ctx),
    };
    array_push(&ctx->scope_stack, &s);
}

// push a function scope.
void
lower_push_scope_function(struct Lower_Context* ctx, struct Function* owner)
{
    struct Scope s = {
        .type = SCOPE_TYPE_FUNCTION,
        .variables = array_new(struct Local_Variable, 16),
        // the owner of this scope is the function that created it
        .containing_function = owner,
    };
    array_push(&ctx->scope_stack, &s);
}

// pop the latest (inner-most) scope off the stack.
// the expected type must match the popped scope!
void
lower_pop_scope(struct Lower_Context* ctx, enum Scope_Type expected)
{
    check(ctx->scope_stack.length > 1, "lowering pass tried popping top-level unit scope");

    struct Scope* top = array_at(struct Scope, &ctx->scope_stack, ctx->scope_stack.length - 1);

    check(top->type == expected, "scope type mismatch on pop: expected %d, got %d", (int)expected,
          (int)top->type);
    check(expected != SCOPE_TYPE_UNIT, "lowering pass tried popping top-level unit scope");

    --ctx->scope_stack.length;
}

// declare a local variable in the current (inner-most) scope.
void
lower_declare_local(struct Lower_Context* ctx, struct String name, struct Type_Ref type)
{
    check(ctx->scope_stack.length > 0, "no active scope");

    struct Local_Variable v = { .name = name, .type = type };

    struct Scope* top = array_at(struct Scope, &ctx->scope_stack, ctx->scope_stack.length - 1);
    array_push(&top->variables, &v);
}

// check whether `name` is already known within any active scope.
// all shadowing is disallowed in catskill/catboot.
bool
lower_is_shadowing(struct Lower_Context* ctx, struct String name)
{
    for (uint i = ctx->scope_stack.length; i > 0; --i) {
        struct Scope* scope = array_at(struct Scope, &ctx->scope_stack, i - 1);

        FOR_EACH_ARRAY (struct Local_Variable, var, &scope->variables) {
            if (string_equals(var->name, name)) return true;
        }
    }

    return false;
}

// look up a local by name across all active scopes, returning its type.
// returns false if no local with that name exists in scope.
bool
lower_local_lookup(struct Lower_Context* ctx, struct String name, struct Type_Ref* out_type)
{
    for (uint i = ctx->scope_stack.length; i > 0; --i) {
        struct Scope* scope = array_at(struct Scope, &ctx->scope_stack, i - 1);

        FOR_EACH_ARRAY (struct Local_Variable, var, &scope->variables) {
            if (string_equals(var->name, name)) {
                if (out_type) *out_type = var->type;
                return true;
            }
        }
    }

    return false;
}

// walk the scope stack looking for a local, which could be captured.
// if the local was declared in some enclosing function that's not us,
// the local becomes captured by our closure function.
struct Lower_Local_Lookup_Capture
lower_local_lookup_capturing(struct Lower_Context* ctx, struct String name)
{
    struct Function* current = lower_current_function(ctx);

    for (uint i = ctx->scope_stack.length; i > 0; --i) {
        struct Scope* scope = array_at(struct Scope, &ctx->scope_stack, i - 1);
        FOR_EACH_ARRAY (struct Local_Variable, var, &scope->variables) {
            if (!string_equals(var->name, name)) continue;

            bool from_enclosing = current != nil && scope->containing_function != current;
            return (struct Lower_Local_Lookup_Capture){
                .captured = from_enclosing,
                .type = var->type,
                .captured_into = from_enclosing ? current : nil,
            };
        }
    }

    // no capture.
    return (struct Lower_Local_Lookup_Capture){ 0 };
}

// add a captured name to a function's capture list.
void
lower_record_capture(struct Function* fn, struct String name, struct Type_Ref type)
{
    // prevent duplication, closed-over locals are often referenced multiple times.
    FOR_EACH_ARRAY (struct Capture, c, &fn->captures) {
        if (string_equals(c->name, name)) return;
    }
    struct Capture cap = { .name = name, .type = type };
    array_push(&fn->captures, &cap);
}

// is the named local a function-typed value?
// (used to decide direct vs. indirect call dispatch when the call subject is a bare name.)
bool
lower_name_is_function_typed_local(struct Lower_Context* ctx, struct String name)
{
    struct Type_Ref ref;
    if (!lower_local_lookup(ctx, name, &ref)) return false;
    if (array_length(&ref.mods) > 0) return false; // references are not callable!
    struct Type* type = *array_at(struct Type*, &ctx->unit->types.entries, ref.type_id);
    return type->kind == TYPE_FUNCTION;
}

struct Statement*
lower_statement_return(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt)
{
    struct Expression* value =
        tree_stmt->value.return_value.value
            ? lower_expression(ctx, tree_stmt->value.return_value.value)
            : nil;
    return ir_make_return(value, tree_stmt->span);
}

struct Statement*
lower_statement_declaration(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt)
{
    struct Tree_Bare_Declaration* decl = &tree_stmt->value.declaration.inner;

    // TODO: multi-name decls like `var a, b int = ...` need to split into
    // N sibling declarations or introduce a temporary for the initializer.
    if (array_length(&decl->names) != 1) {
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_UNIMPLEMENTED,
                .span = tree_stmt->span,
                .detail = string_from_static_c_string("multi-name declarations"),
            });
        return nil;
    }

    struct String name = *array_at(struct String, &decl->names, 0);
    if (lower_is_shadowing(ctx, name)) {
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_NAME_SHADOWS,
                .span = tree_stmt->span,
                .name = name,
            });
        return nil;
    }
    struct Type_Ref type = lower_intern_type_ref(ctx, decl->type);
    lower_declare_local(ctx, name, type);

    struct Expression* initializer =
        decl->initializer ? lower_expression(ctx, decl->initializer) : nil;
    return ir_make_declaration(name, type, initializer, tree_stmt->span);
}

struct Statement*
lower_statement_expression(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt)
{
    struct Tree_Expression* inner = tree_stmt->value.expression.inner;

    if (inner && inner->kind == TREE_EXPRESSION_BINARY_OPERATION) {
        enum Binary_Operation op = inner->value.binary_operator.operation;
        struct Tree_Expression* lhs_tree = inner->value.binary_operator.left_operand;
        struct Tree_Expression* rhs_tree = inner->value.binary_operator.right_operand;

        if (op == BINARY_ASSIGN) {
            struct Expression* lhs = lower_expression(ctx, lhs_tree);
            struct Expression* rhs = lower_expression(ctx, rhs_tree);
            return ir_make_assign(lhs, rhs, tree_stmt->span);
        }
        if (op > BINARY_ASSIGN) {
            // compound assigns always synthesize into a basic assignment
            // to a simple binary operation.
            if (!lhs_tree || lhs_tree->kind != TREE_EXPRESSION_NAME) {
                // TODO: implement non-trivial lhs assignments like function
                // calls for example. not too common but sometimes necessary.
                lower_push_error(
                    ctx->unit,
                    (struct Lower_Error){
                        .kind = LOWER_ERROR_UNIMPLEMENTED,
                        .span = tree_stmt->span,
                        .detail = string_from_static_c_string(
                            "compound assignment with "
                            "non-trivial lvalue"),
                    });
                return nil;
            }

            enum Binary_Operation simple_op = binary_operation_strip_assign(op);
            if (simple_op == BINARY_NONE) {
                lower_push_error(
                    ctx->unit,
                    (struct Lower_Error){
                        .kind = LOWER_ERROR_UNKNOWN_COMPOUND_ASSIGN,
                        .span = tree_stmt->span,
                    });
                return nil;
            }

            struct Expression* binary = ir_make_binary(
                simple_op, lower_expression(ctx, lhs_tree), lower_expression(ctx, rhs_tree),
                inner->span);
            return ir_make_assign(lower_expression(ctx, lhs_tree), binary, tree_stmt->span);
        }
    }
    return ir_make_expression_statement(lower_expression(ctx, inner), tree_stmt->span);
}

struct Statement*
lower_statement_block(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt)
{
    return ir_make_block_statement(
        lower_block(ctx, &tree_stmt->value.block.inner), tree_stmt->span);
}

struct Statement*
lower_statement_conditional(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt)
{
    struct Tree_Statement_Value_Conditional* cond = &tree_stmt->value.conditional;
    Array(struct If_Branch) branches = array_new(struct If_Branch, 8);

    for (uint i = 0; i < cond->condition_count; ++i) {
        struct If_Branch branch = {
            .condition =
                cond->conditions[i].when ? lower_expression(ctx, cond->conditions[i].when) : nil,
            .body = lower_block(ctx, &cond->conditions[i].then),
        };
        array_push(&branches, &branch);
    }

    return ir_make_conditional(branches, tree_stmt->span);
}

struct Statement*
lower_statement_loop(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt)
{
    struct Tree_Statement_Value_Loop* loop = &tree_stmt->value.loop;

    switch (loop->style) {
    case TREE_STATEMENT_LOOP_STYLE_WHILE: {
        struct Expression* cond = lower_expression(ctx, loop->condition);
        struct Block* body = lower_block(ctx, &loop->body);
        return ir_make_loop(cond, body, tree_stmt->span);
    }
    case TREE_STATEMENT_LOOP_STYLE_ENDLESS: {
        // synthesize a `true` literal so the ir always has a real
        // condition to emit.
        struct Expression* cond = ir_make_bool(true, tree_stmt->span);
        struct Block* body = lower_block(ctx, &loop->body);
        return ir_make_loop(cond, body, tree_stmt->span);
    }
    case TREE_STATEMENT_LOOP_STYLE_C:
    case TREE_STATEMENT_LOOP_STYLE_FOR_EACH: {
        // both styles become a basic while loop
        // TODO: right now we only support for-each for ranges,
        // we want to add iteration over real containers later.

        struct Tree_Bare_Declaration* decl = &loop->declaration;

        struct Tree_Expression* init = nil;
        struct Tree_Expression* cond_tree = loop->condition;
        struct Tree_Expression* iter_tree = loop->iteration;

        if (loop->style == TREE_STATEMENT_LOOP_STYLE_FOR_EACH) {
            if (!decl->initializer || decl->initializer->kind != TREE_EXPRESSION_BINARY_OPERATION
                || decl->initializer->value.binary_operator.operation != BINARY_RANGE) {
                lower_push_error(
                    ctx->unit,
                    (struct Lower_Error){
                        .kind = LOWER_ERROR_UNIMPLEMENTED,
                        .span = tree_stmt->span,
                        .detail = string_from_static_c_string(
                            "for-each over non-range "
                            "collections"),
                    });
                return nil;
            }
            init = decl->initializer->value.binary_operator.left_operand;
            // condition and iteration step are synthesized below
        } else {
            init = decl->initializer;
        }

        if (array_length(&decl->names) != 1) {
            lower_push_error(
                ctx->unit,
                (struct Lower_Error){
                    .kind = LOWER_ERROR_UNIMPLEMENTED,
                    .span = tree_stmt->span,
                    .detail = string_from_static_c_string("for-loop with multi-name declaration"),
                });
            return nil;
        }
        struct String name = *array_at(struct String, &decl->names, 0);

        // open outer block scope.
        // this stores the iterator variable.
        lower_push_scope(ctx, SCOPE_TYPE_BLOCK);

        if (lower_is_shadowing(ctx, name)) {
            lower_push_error(
                ctx->unit,
                (struct Lower_Error){
                    .kind = LOWER_ERROR_NAME_SHADOWS,
                    .span = tree_stmt->span,
                    .name = name,
                });
            lower_pop_scope(ctx, SCOPE_TYPE_BLOCK);
            return nil;
        }

        struct Type_Ref iter_type = lower_intern_type_ref(ctx, decl->type);
        lower_declare_local(ctx, name, iter_type);

        // build the iteration variable declaration
        struct Statement* decl_stmt = ir_make_declaration(
            name, iter_type, init ? lower_expression(ctx, init) : nil, decl->span);

        // condition and iteration step: for c-style we lower the source
        // ones, for for-each over a range we synthesize `i < hi` and
        // `i = i + 1`.
        struct Expression* cond_expr = nil;
        struct Statement* iter_stmt = nil;
        if (loop->style == TREE_STATEMENT_LOOP_STYLE_FOR_EACH) {
            struct Tree_Expression* hi = decl->initializer->value.binary_operator.right_operand;
            // condition: i < hi
            cond_expr = ir_make_binary(
                BINARY_LESS_THAN, ir_make_name(name, tree_stmt->span), lower_expression(ctx, hi),
                tree_stmt->span);
            // step: i = i + 1
            iter_stmt = ir_make_assign(
                ir_make_name(name, tree_stmt->span),
                ir_make_binary(
                    BINARY_PLUS, ir_make_name(name, tree_stmt->span),
                    ir_make_integer(1, tree_stmt->span), tree_stmt->span),
                tree_stmt->span);
        } else {
            cond_expr = cond_tree ? lower_expression(ctx, cond_tree) : nil;
            if (iter_tree) {
                struct Tree_Statement iter_node = {
                    .kind = TREE_STATEMENT_EXPRESSION,
                    .value = { .expression = { .inner = iter_tree } },
                    .span = iter_tree->span,
                };
                iter_stmt = lower_statement(ctx, &iter_node);
            }
        }

        // assemble the body, appending the iteration step at the end so
        // both for-styles share the same `{ decl; while { body; iter; } }`
        // shape.
        struct Block* body = lower_block(ctx, &loop->body);
        if (iter_stmt) array_push(&body->statements, &iter_stmt);

        struct Statement* while_stmt = ir_make_loop(cond_expr, body, tree_stmt->span);

        struct Block* outer = block_new();
        outer->statements = array_new(struct Statement*, 4);
        array_push(&outer->statements, &decl_stmt);
        array_push(&outer->statements, &while_stmt);

        lower_pop_scope(ctx, SCOPE_TYPE_BLOCK);
        return ir_make_block_statement(outer, tree_stmt->span);
    }
    default:
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_UNKNOWN_LOOP_STYLE, .span = tree_stmt->span });
        return nil;
    }
}

struct Statement*
lower_statement_break(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt)
{
    (void)ctx;
    return ir_make_break(tree_stmt->span);
}

struct Statement*
lower_statement_continue(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt)
{
    (void)ctx;
    return ir_make_continue(tree_stmt->span);
}

// turns a source statement into the lowered form.
struct Statement*
lower_statement(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt)
{
    switch (tree_stmt->kind) {
    case TREE_STATEMENT_RETURN:
        return lower_statement_return(ctx, tree_stmt);
    case TREE_STATEMENT_DECLARATION:
        return lower_statement_declaration(ctx, tree_stmt);
    case TREE_STATEMENT_EXPRESSION:
        return lower_statement_expression(ctx, tree_stmt);
    case TREE_STATEMENT_BLOCK:
        return lower_statement_block(ctx, tree_stmt);
    case TREE_STATEMENT_CONDITIONAL:
        return lower_statement_conditional(ctx, tree_stmt);
    case TREE_STATEMENT_LOOP:
        return lower_statement_loop(ctx, tree_stmt);
    case TREE_STATEMENT_BREAK:
        return lower_statement_break(ctx, tree_stmt);
    case TREE_STATEMENT_CONTINUE:
        return lower_statement_continue(ctx, tree_stmt);
    default:
        lower_push_error(
            ctx->unit,
            (struct Lower_Error){
                .kind = LOWER_ERROR_UNIMPLEMENTED,
                .span = tree_stmt->span,
                .detail = string_from_static_c_string("this statement kind"),
            });
        return nil;
    }
}

// turns a source block of statements into the lowered form of a block.
// pushes a fresh lexical scope for the duration of the block.
struct Block*
lower_block(struct Lower_Context* ctx, struct Tree_Block* tree_block)
{
    lower_push_scope(ctx, SCOPE_TYPE_BLOCK);

    struct Block* block = block_new();
    block->statements = array_new(struct Statement*, 16);
    FOR_EACH (struct Tree_Statement*, tree_stmt, tree_block->statements) {
        struct Statement* stmt = lower_statement(ctx, tree_stmt);
        if (stmt) array_push(&block->statements, &stmt);
    }

    lower_pop_scope(ctx, SCOPE_TYPE_BLOCK);
    return block;
}

// lowering pass 2
// walks every collected function's source body and produces a lowered statement block.
void
lower_pass_2(struct Lower_Context* ctx)
{
    FOR_EACH_ARRAY (struct Function*, fn, &ctx->unit->functions.entries) {
        // skip functions which have already been processed.
        // synthetic lambdas get lowered eagerly when encountered to gain
        // access to the local stack at their location.
        if ((*fn)->completed) continue;
        if (!(*fn)->ast_body) continue;

        // push a function-level scope on top of the persistent top-level unit
        // scope, holding the parameter names.
        lower_push_scope_function(ctx, *fn);
        FOR_EACH_ARRAY (struct Param, param, &(*fn)->params) {
            lower_declare_local(ctx, param->name, param->type);
        }

        (*fn)->body = lower_block(ctx, (*fn)->ast_body);
        (*fn)->completed = true;

        lower_pop_scope(ctx, SCOPE_TYPE_FUNCTION);
    }
}

// return line number for the given byte position in the source. (1-based)
uint
lower_span_to_line(struct String source, struct Span span)
{
    uint line, column;
    source_position_from_span(source, span, &line, &column);
    return line;
}

// `chain` is the walk we took while looking for the cycle, `cycle_start` is
// the index in it at which the cycle closes back on itself.
void
lower_report_type_cycle(struct Unit* unit, struct _Array* chain, uint cycle_start)
{
    uint chain_len = array_length(chain);
    Array(Type_Id) cycle_copy = array_new(Type_Id, chain_len - cycle_start);
    for (uint k = cycle_start; k < chain_len; ++k) {
        Type_Id id = *array_at(Type_Id, chain, k);
        array_push(&cycle_copy, &id);
    }

    Type_Id origin_id = *array_at(Type_Id, chain, cycle_start);
    struct Type* origin = *array_at(struct Type*, &unit->types.entries, origin_id);
    lower_push_error(
        unit,
        (struct Lower_Error){
            .kind = LOWER_ERROR_TYPE_CYCLE,
            .span = origin->span,
            .cycle_chain = cycle_copy,
        });
}

// topologically sorting the unit's type dependency graph.
// implemented through kahn's algorithm.
// see: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm
// final ordering for the type emission is stable, types declared earlier
// are always first to emit when their vertex in-degree is 0.
// cycles reported as diagnostic, partial emission order will still be completed.
void
lower_topological_sort_dependency_graph(struct Unit* unit)
{
    const uint done_sentinel = (uint)-1; // marks vertecies that have been processed

    uint n = array_length(&unit->types.entries);
    if (n == 0) return;

    // for i, holds in-degree for type i.
    Array(uint) in_degree = array_new(uint, n);
    for (uint i = 0; i < n; ++i) {
        struct Type* type = *array_at(struct Type*, &unit->types.entries, i);
        uint deg = array_length(&type->depends_on);
        array_push(&in_degree, &deg);
    }

    // for i, holds every index of types that depends on type i.
    Array(struct _Array) reverse_deps = array_new(struct _Array, n);
    for (uint i = 0; i < n; ++i) {
        struct _Array slot = _array_new(sizeof(Type_Id), 16);
        array_push(&reverse_deps, &slot);
    }
    for (uint i = 0; i < n; ++i) {
        struct Type* type = *array_at(struct Type*, &unit->types.entries, i);
        Type_Id me = (Type_Id)i;
        FOR_EACH_ARRAY (Type_Id, dep, &type->depends_on) {
            struct _Array* slot = array_at(struct _Array, &reverse_deps, *dep);
            _array_push(slot, &me);
        }
    }

    uint output_count = 0;
    while (output_count < n) {
        Type_Id chosen = (Type_Id)-1;
        for (uint i = 0; i < n; ++i) {
            if (*array_at(uint, &in_degree, i) == 0) {
                chosen = (Type_Id)i;
                break;
            }
        }
        if (chosen == (Type_Id)-1) break; // cycle

        array_push(&unit->type_emission_order, &chosen);
        output_count++;
        *array_at(uint, &in_degree, chosen) = done_sentinel;

        struct _Array* dependents = array_at(struct _Array, &reverse_deps, chosen);
        FOR_EACH_ARRAY (Type_Id, dependent, dependents) {
            uint* d = array_at(uint, &in_degree, *dependent);
            if (*d != done_sentinel) (*d)--;
        }
    }

    if (output_count == n) return;

    // we've got a cycle! walk starting from the lowest type that's
    // still pending, following edges until we find type we already saw.
    // we revisit an id.
    Type_Id start = (Type_Id)-1;
    for (uint i = 0; i < n; ++i) {
        if (*array_at(uint, &in_degree, i) != done_sentinel) {
            start = (Type_Id)i;
            break;
        }
    }
    if (start == (Type_Id)-1) return;

    Array(Type_Id) chain = array_new(Type_Id, 64);
    array_push(&chain, &start);
    Type_Id current = start;

    while (true) {
        struct Type* type = *array_at(struct Type*, &unit->types.entries, current);

        Type_Id next = (Type_Id)-1;
        FOR_EACH_ARRAY (Type_Id, dep, &type->depends_on) {
            if (*array_at(uint, &in_degree, *dep) != done_sentinel) {
                next = *dep;
                break;
            }
        }
        if (next == (Type_Id)-1) return; // not a real cycle

        uint chain_len = array_length(&chain);
        uint found_at = chain_len;
        for (uint k = 0; k < chain_len; ++k) {
            if (*array_at(Type_Id, &chain, k) == next) {
                found_at = k;
                break;
            }
        }
        if (found_at < chain_len) {
            lower_report_type_cycle(unit, &chain, found_at);
            return;
        }

        array_push(&chain, &next);
        current = next;
    }
}

void
lower_tree(struct Tree* tree, struct Unit* unit)
{
    unit->types.entries = array_new(struct Type*, 256);
    unit->types.by_hash = array_new(struct Type_Hash_To_Id, 256);
    unit->types.by_name = array_new(struct Type_Name_To_Id, 256);

    unit->functions.entries = array_new(struct Function*, 256);
    unit->functions.by_name = array_new(struct Function_Name_To_Id, 256);

    unit->imports = array_new(struct Import, 32);
    unit->type_emission_order = array_new(Type_Id, 256);
    unit->had_error = false;
    unit->lower_errors = array_new(struct Lower_Error, 64);

    unit->types.primitive_int_id = lower_seed_primitive(unit, "int");
    unit->types.primitive_uint_id = lower_seed_primitive(unit, "uint");
    unit->types.primitive_bool_id = lower_seed_primitive(unit, "bool");
    unit->types.primitive_string_id = lower_seed_primitive(unit, "string");
    unit->types.primitive_float_id = lower_seed_primitive(unit, "float");
    unit->types.primitive_byte_id = lower_seed_primitive(unit, "byte");
    unit->types.primitive_ascii_id = lower_seed_primitive(unit, "ascii");
    unit->types.primitive_void_id = lower_seed_primitive(unit, "void");

    struct Lower_Context ctx = {
        .unit = unit,
        .synthetic_type_counter = 0,
        .synthetic_counter = 0,
        .scope_stack = array_new(struct Scope, 32),
    };

    // push the persistent top-level scope, where all top-level
    // language object declarations of a translation unit live.
    lower_push_scope(&ctx, SCOPE_TYPE_UNIT);

    if (tree) {
        lower_pass_1(&ctx, tree);
        lower_pass_2(&ctx);
    }
    lower_topological_sort_dependency_graph(unit);
}