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"

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

    // text source of the unit in translation
    // used for attaching diagnostics to correct lines
    struct Source_File source;

    // monotonic counter of synthesized types
    uint synthetic_type_counter;

    // TODO: add function & block scope data
};

void
lower_emit_error(struct Unit* unit, struct Span span, struct String message)
{
    struct Diagnostic d = {
        .severity = DIAGNOSTIC_ERROR,
        .span = span,
        .message = message,
    };
    array_push(&unit->diagnostics, &d);
    unit->had_error = true;
}

void
lower_emit_error_c(struct Unit* unit, struct Span span, const ascii* message)
{
    lower_emit_error(unit, span, string_from_c_string(message));
}

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);
}

// 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_id = inner.type_id,
            .mods = array_new(enum Type_Modifier, 4),
        };
        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_id = ctx->unit->types.primitive_void_id,
        .mods = array_new(enum Type_Modifier, 4),
    };

    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_emit_error(
                ctx->unit, current->span,
                string_concatenate(
                    ARG_ASCII, "undefined type '", ARG_STRING, current->value.name.name, ARG_ASCII,
                    "'", ARG_END));
        }
        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_emit_error_c(ctx->unit, current->span, "unimplemented: map types");
        return ref;
    default:
        lower_emit_error_c(ctx->unit, current->span, "unimplemented: 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_emit_error(
            unit, span,
            string_concatenate(
                ARG_ASCII, "duplicate function '", ARG_STRING, name, ARG_ASCII, "'", ARG_END));
        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_emit_error(
            unit, span,
            string_concatenate(
                ARG_ASCII, "duplicate type '", ARG_STRING, name, ARG_ASCII, "'", ARG_END));
        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_body = &fn_expr->value.function.body;
    fn->body = nil;
}

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_emit_error(
                ctx->unit, tree_type->span,
                string_concatenate(
                    ARG_ASCII, "undefined type '", ARG_STRING, tree_type->value.name.name,
                    ARG_ASCII, "'", ARG_END));
        }
        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_emit_error_c(ctx->unit, tree_type->span, "unimplemented: 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;
            // TODO: actually go into the body, only the signature for now.
            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) {
            lower_emit_error_c(ctx->unit, stmt->span, "unimplemented: top-level pragmas");
            continue;
        }

        lower_emit_error_c(ctx->unit, stmt->span, "unsupported top-level statement");
    }
}

// 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);

// turns a source expression into the lowered form.
struct Expression*
lower_expression(struct Lower_Context* ctx, struct Tree_Expression* tree_expr)
{
    // TODO: implement all the expressions
    switch (tree_expr->kind) {
    case TREE_EXPRESSION_INTEGER_LITERAL: {
        union Expression_Value v = { 0 };
        v.integer_literal.value = tree_expr->value.integer_literal.value;
        return expression_new(EXPRESSION_INTEGER_LITERAL, v, tree_expr->span);
    }
    case TREE_EXPRESSION_FLOAT_LITERAL: {
        union Expression_Value v = { 0 };
        v.float_literal.value = tree_expr->value.float_literal.value;
        return expression_new(EXPRESSION_FLOAT_LITERAL, v, tree_expr->span);
    }
    case TREE_EXPRESSION_STRING_LITERAL: {
        union Expression_Value v = { 0 };
        v.string_literal.value = tree_expr->value.string_literal.value;
        return expression_new(EXPRESSION_STRING_LITERAL, v, tree_expr->span);
    }
    case TREE_EXPRESSION_BOOLEAN_LITERAL: {
        union Expression_Value v = { 0 };
        v.bool_literal.value = tree_expr->value.bool_literal.value;
        return expression_new(EXPRESSION_BOOLEAN_LITERAL, v, tree_expr->span);
    }
    case TREE_EXPRESSION_NAME: {
        union Expression_Value v = { 0 };
        v.name.name = tree_expr->value.name.name;
        return expression_new(EXPRESSION_NAME, v, tree_expr->span);
    }
    default:
        lower_emit_error_c(ctx->unit, tree_expr->span, "unimplemented: this expression kind");
        return nil;
    }
}

// turns a source statement into the lowered form.
struct Statement*
lower_statement(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt)
{
    // TODO: implement all the statements
    switch (tree_stmt->kind) {
    case TREE_STATEMENT_RETURN: {
        union Statement_Value v = { 0 };
        if (tree_stmt->value.return_value.value)
            v.return_value.value = lower_expression(ctx, tree_stmt->value.return_value.value);
        return statement_new(STATEMENT_RETURN, v, tree_stmt->span);
    }
    default:
        lower_emit_error_c(ctx->unit, tree_stmt->span, "unimplemented: this statement kind");
        return nil;
    }
}

// turns a source block of statements into the lowered form of a block.
struct Block*
lower_block(struct Lower_Context* ctx, struct Tree_Block* tree_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);
    }
    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) {
        if ((*fn)->ast_body) (*fn)->body = lower_block(ctx, (*fn)->ast_body);
    }
}

// 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 = 1;
    uint upto = span.start;
    if (upto > string_length(source)) upto = string_length(source);
    for (uint i = 0; i < upto; ++i) {
        if (string_at(source, i) == '\n') line++;
    }
    return line;
}

// builds a nice & friendly cycle detection message and emits it as a diagnostic.
// `chain` is the path we walked while looking for the cycle, and
// `cycle_start` is the chain index at which the cycle closes.
void
lower_report_type_cycle(
    struct Unit* unit, struct Source_File source, struct _Array* chain, uint cycle_start)
{
    struct String_Buffer buf = string_buffer_new(512);
    string_buffer_append_c_str(&buf, "type cycle detected:\n");

    uint chain_len = array_length(chain);
    for (uint k = cycle_start; k < chain_len; ++k) {
        Type_Id current_id = *array_at(Type_Id, chain, k);
        Type_Id next_id;
        if (k + 1 < chain_len)
            next_id = *array_at(Type_Id, chain, k + 1);
        else
            next_id = *array_at(Type_Id, chain, cycle_start);

        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 = lower_span_to_line(source.source, current->span);

        ascii line_buf[256];
        snprintf(
            line_buf, sizeof line_buf, "  %s (line %lu) depends on %s\n",
            string_c_str(current->name), line, string_c_str(next->name));
        string_buffer_append_c_str(&buf, line_buf);
    }
    string_buffer_append_c_str(
        &buf, "hint: break the cycle with a reference (use `&T` instead of `T`). :)");

    Type_Id origin_id = *array_at(Type_Id, chain, cycle_start);
    struct Type* origin = *array_at(struct Type*, &unit->types.entries, origin_id);
    lower_emit_error(unit, origin->span, string_buffer_to_string(&buf));
}

// 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, struct Source_File source)
{
    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, source, &chain, found_at);
            return;
        }

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

void
lower_tree(struct Tree* tree, struct Source_File source, 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->diagnostics = array_new(struct Diagnostic, 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,
        .source = source,
        .synthetic_type_counter = 0,
    };

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