path: root/boot/ir.c

/*
 * intermediate representation produced by the lowering pass.
 *
 * the ir is the canonical form every later phase operates on.
 * it is 100% sugar-free (healthy!) and shaped (vaguely) like c, as the
 * primary target of our bootstrapping transpiler.
 *
 * Copyright (c) 2026, Mel G. <mel@rnrd.eu>
 *
 * SPDX-License-Identifier: MPL-2.0
 */

#pragma once

#include "catboot.h"

// per-unit stable identifier for a type, never becomes invalid.
typedef uint Type_Id;
// per-unit stable identifier for a function, never becomes invalid.
typedef uint Function_Id;

struct Type;
struct Type_Ref;
struct Function;
struct Statement;
struct Expression;
struct Block;

// modifier applied to a type reference.
enum Type_Modifier
{
    TYPE_MOD_REFERENCE, // &T
    // TODO: arrays, optionals, everything else...
};

// a use of a type.
struct Type_Ref
{
    Type_Id type_id;

    // modifiers are sorted outer-to-inner, for example:
    // `&[Thing?]`: reference -> array -> maybe -> Thing
    Array(enum Type_Modifier) mods;
};

// what kind of declaration is this type?
// represents both the declaration and the type itself.
enum Type_Kind
{
    TYPE_NONE,
    TYPE_PRIMITIVE,
    TYPE_ALIAS,
    TYPE_STRUCTURE,
    TYPE_VARIANT,
    TYPE_FUNCTION,
    // TODO: add rest of possible types
};

// a member of a structure.
struct Field
{
    struct String name;
    struct Type_Ref type;
};

// one case of a tagged union.
struct Variant_Case
{
    struct String name;
    // tag to distinguish each case at runtime
    uint32 tag;

    // if no payload, the case is just a tag
    bool has_payload;
    struct Type_Ref payload;
};

struct Type_Alias
{
    Type_Id target_id;
};

struct Type_Structure
{
    Array(struct Field) fields;
};

struct Type_Variant
{
    Array(struct Variant_Case) cases;
};

struct Type_Function
{
    struct Type_Ref return_type;
    Array(struct Type_Ref) params;
    bool variadic;
};

union Type_Value
{
    struct Type_Alias alias;
    struct Type_Structure structure;
    struct Type_Variant variant;
    struct Type_Function function;
};

// every type the compiler ever talks about lives in the type table and has a
// stable identifier which other types refer to.
// unnamed, structural types get synthesized into full types.
struct Type
{
    Type_Id id;
    struct String name;

    enum Type_Kind kind;
    union Type_Value value;

    // if a user names a type it is non-synthetic, if they just refer to a type
    // without a name, like `var x (A, B) = ...`, it is synthetic.
    bool synthetic;
    // for synthethic types this is a hash of the contents of the type,
    // used for de-duplication. otherwise we can't cast between the same type.
    // 0 for all named types.
    uint64 structural_hash;

    // all types which this type has a hard dependency on
    Array(Type_Id) depends_on;

    struct Span span;
};

// one parameter of a function.
struct Param
{
    struct String name;
    struct Type_Ref type;
};

// minimal lowered statement set.
enum Statement_Kind
{
    STATEMENT_NONE,
    STATEMENT_DECLARATION,
    STATEMENT_ASSIGN,
    STATEMENT_EXPRESSION,
    STATEMENT_CONDITIONAL,
    STATEMENT_LOOP,
    STATEMENT_RETURN,
    STATEMENT_BREAK,
    STATEMENT_CONTINUE,
    STATEMENT_BLOCK,
    STATEMENT_LABEL,
    STATEMENT_GOTO,
};

struct Statement_Declaration
{
    struct String name;
    struct Type_Ref type;
    struct Expression* initializer; // nil if no initializer
};

// only pure `x = y` assignments, no compounds like `+=`.
struct Statement_Assign
{
    struct Expression* lhs;
    struct Expression* rhs;
};

struct Statement_Expression
{
    struct Expression* inner;
};

// one branch of an if/else-if/else chain.
struct If_Branch
{
    struct Expression* condition; // nil if else branch
    struct Block* body;
};

struct Statement_Conditional
{
    Array(struct If_Branch) branches;
};

struct Statement_Loop
{
    struct Expression* condition;
    struct Block* body;
};

struct Statement_Return
{
    struct Expression* value; // nil if empty return
};

struct Statement_Block
{
    struct Block* inner;
};

struct Statement_Label
{
    struct String name;
};

struct Statement_Goto
{
    struct String target;
};

union Statement_Value
{
    struct Statement_Declaration declaration;
    struct Statement_Assign assign;
    struct Statement_Expression expression;
    struct Statement_Conditional conditional;
    struct Statement_Loop loop;
    struct Statement_Return return_value;
    struct Statement_Block block;
    struct Statement_Label label;
    struct Statement_Goto goto_target;
};

struct Statement
{
    enum Statement_Kind kind;
    union Statement_Value value;
    struct Span span;
};

// minimal lowered expression set.
enum Expression_Kind
{
    EXPRESSION_NONE,
    EXPRESSION_INTEGER_LITERAL,
    EXPRESSION_FLOAT_LITERAL,
    EXPRESSION_STRING_LITERAL,
    EXPRESSION_BOOLEAN_LITERAL,
    EXPRESSION_NAME,
    EXPRESSION_UNARY_OPERATION,
    EXPRESSION_BINARY_OPERATION,
    EXPRESSION_SIZEOF_OPERATION,
    EXPRESSION_CALL,
    EXPRESSION_MEMBER,
    EXPRESSION_SUBSCRIPT,
    EXPRESSION_CAST,
    EXPRESSION_CONSTRUCT,
};

struct Expression_Integer_Literal
{
    int64 value;
};

struct Expression_Float_Literal
{
    float64 value;
};

struct Expression_String_Literal
{
    struct String value;
};

struct Expression_Bool_Literal
{
    bool value;
};

struct Expression_Name
{
    struct String name;
};

struct Expression_Unary_Operator
{
    enum Unary_Operation operation;
    struct Expression* operand;
};

struct Expression_Binary_Operator
{
    // assignment is excluded
    enum Binary_Operation operation;
    struct Expression* left_operand;
    struct Expression* right_operand;
};

struct Expression_Sizeof_Operator
{
    struct Type_Ref target;
};

// one argument of a call, tagged with the parameter slot it fills.
struct Call_Argument
{
    struct Expression* value;
    // slot decides the final emission order.
    // slots that are higher than the parameter count of a function
    // are always counted as variadic extras, and an error for non-variadics.
    uint slot;
};

struct Expression_Call
{
    struct Expression* subject;
    // arguments of call in written order, the inner slot decides final ordering.
    Array(struct Call_Argument) arguments;
};

struct Expression_Member
{
    struct Expression* subject;
    struct String name;
};

struct Expression_Subscript
{
    struct Expression* subject;
    struct Expression* index;
};

struct Expression_Cast
{
    struct Type_Ref target;
    struct Expression* operand;
};

// one named field in a construction literal.
struct Construct_Field
{
    // empty for positional initialization.
    struct String name;
    struct Expression* value;
};

struct Expression_Construct
{
    Type_Id type_id;
    Array(struct Construct_Field) fields;
};

union Expression_Value
{
    struct Expression_Integer_Literal integer_literal;
    struct Expression_Float_Literal float_literal;
    struct Expression_String_Literal string_literal;
    struct Expression_Bool_Literal bool_literal;
    struct Expression_Name name;
    struct Expression_Unary_Operator unary_operator;
    struct Expression_Binary_Operator binary_operator;
    struct Expression_Sizeof_Operator sizeof_operator;
    struct Expression_Call call;
    struct Expression_Member member;
    struct Expression_Subscript subscript;
    struct Expression_Cast cast;
    struct Expression_Construct construct;
};

struct Expression
{
    enum Expression_Kind kind;
    union Expression_Value value;

    // TODO: fill this out with a basic type-checker
    struct Type_Ref result_type;

    struct Span span;
};

// a sequence of statements.
struct Block
{
    Array(struct Statement*) statements;
};

// a function declaration.
struct Function
{
    Function_Id id;
    struct String name;

    bool is_main;
    bool main_takes_args;

    // synthetic functions are unnamed closures.
    bool synthetic;

    struct Type_Ref return_type;
    Array(struct Param) params;
    bool variadic; // is last parameter variadic?

    // first lowering pass only fills out the ast body and not the lowered body,
    // to collect all top-declarations.
    struct Tree_Block* ast_body;
    struct Block* body;
};

struct Type_Hash_To_Id
{
    uint64 hash;
    Type_Id id;
};

struct Type_Name_To_Id
{
    struct String name;
    Type_Id id;
};

struct Type_Table
{
    // list of all types. index in this array is a type's unique identifier.
    Array(struct Type*) entries;
    // hash mapping of all synthetic types for de-duplication.
    Array(struct Type_Hash_To_Id) by_hash;
    // name mapping of all types.
    Array(struct Type_Name_To_Id) by_name;

    // seed table of all current primitive types, we fill it out
    // one-by-one whenever we find one.
    Type_Id primitive_int_id;
    Type_Id primitive_uint_id;
    Type_Id primitive_bool_id;
    Type_Id primitive_string_id;
    Type_Id primitive_float_id;
    Type_Id primitive_byte_id;
    Type_Id primitive_ascii_id;
    Type_Id primitive_void_id;
};

struct Function_Name_To_Id
{
    struct String name;
    Function_Id id;
};

struct Function_Table
{
    // list of all functions. index in this array is a functions's unique identifier.
    Array(struct Function*) entries;
    // name mapping of all functions
    Array(struct Function_Name_To_Id) by_name;
};

// c import via pragma.
struct Import
{
    struct String path;
    struct Span span;
};

enum Lower_Error_Kind
{
    LOWER_ERROR_NONE,
    LOWER_ERROR_UNDEFINED_TYPE,
    LOWER_ERROR_DUPLICATE_TYPE,
    LOWER_ERROR_DUPLICATE_FUNCTION,
    LOWER_ERROR_NAME_SHADOWS,
    LOWER_ERROR_TYPE_CYCLE,
    LOWER_ERROR_ASSIGNMENT_AS_EXPRESSION,
    LOWER_ERROR_RANGE_OUTSIDE_LOOP,
    LOWER_ERROR_CONSTRUCT_SUBJECT_NOT_NAME,
    LOWER_ERROR_TYPE_EXPRESSION_IN_BODY,
    LOWER_ERROR_UNSUPPORTED_TOP_LEVEL,
    LOWER_ERROR_UNKNOWN_LOOP_STYLE,
    LOWER_ERROR_UNKNOWN_COMPOUND_ASSIGN,
    LOWER_ERROR_UNKNOWN_NAMED_ARGUMENT,
    LOWER_ERROR_DUPLICATE_ARGUMENT,
    LOWER_ERROR_TOO_MANY_ARGUMENTS,
    LOWER_ERROR_NAMED_ARGUMENT_ON_UNKNOWN_CALLEE,
    LOWER_ERROR_UNIMPLEMENTED,
};

struct Lower_Error
{
    enum Lower_Error_Kind kind;
    struct Span span;

    // per-error details, meaning depends on each error kind!
    struct String name;
    struct String detail;
    Array(Type_Id) cycle_chain;
};

// a single translation unit.
struct Unit
{
    struct Type_Table types;
    struct Function_Table functions;
    Array(struct Import) imports;

    // types require a specific ordering taking into account
    // their interconnected dependencies.
    // this holds the final order necessary for correct compilation.
    Array(Type_Id) type_emission_order;

    bool had_error;
    Array(struct Lower_Error) lower_errors;
};

REGION(struct Type, type)
REGION(struct Function, function)
REGION(struct Statement, statement)
REGION(struct Expression, expression)
REGION(struct Block, block)

struct Type*
type_new(Type_Id id, enum Type_Kind kind, struct String name, struct Span span)
{
    check(region_type_cursor < REGION_SIZE, "out of type memory");
    struct Type* type = &region_type[region_type_cursor++];
    *type = (struct Type){
        .id = id,
        .kind = kind,
        .name = name,
        .span = span,
    };
    return type;
}

struct Function*
function_new(Function_Id id, struct String name)
{
    check(region_function_cursor < REGION_SIZE, "out of function memory");
    struct Function* function = &region_function[region_function_cursor++];
    *function = (struct Function){
        .id = id,
        .name = name,
    };
    return function;
}

struct Statement*
statement_new(enum Statement_Kind kind, union Statement_Value value, struct Span span)
{
    check(region_statement_cursor < REGION_SIZE, "out of statement memory");
    struct Statement* statement = &region_statement[region_statement_cursor++];
    *statement = (struct Statement){
        .kind = kind,
        .value = value,
        .span = span,
    };
    return statement;
}

struct Expression*
expression_new(enum Expression_Kind kind, union Expression_Value value, struct Span span)
{
    check(region_expression_cursor < REGION_SIZE, "out of expression memory");
    struct Expression* expression = &region_expression[region_expression_cursor++];
    *expression = (struct Expression){
        .kind = kind,
        .value = value,
        .span = span,
    };
    return expression;
}

struct Block*
block_new(void)
{
    check(region_block_cursor < REGION_SIZE, "out of block memory");
    struct Block* block = &region_block[region_block_cursor++];
    *block = (struct Block){ 0 };
    return block;
}

struct Expression*
ir_make_integer(int64 value, struct Span span)
{
    union Expression_Value v = { 0 };
    v.integer_literal.value = value;
    return expression_new(EXPRESSION_INTEGER_LITERAL, v, span);
}

struct Expression*
ir_make_float(float64 value, struct Span span)
{
    union Expression_Value v = { 0 };
    v.float_literal.value = value;
    return expression_new(EXPRESSION_FLOAT_LITERAL, v, span);
}

struct Expression*
ir_make_string(struct String value, struct Span span)
{
    union Expression_Value v = { 0 };
    v.string_literal.value = value;
    return expression_new(EXPRESSION_STRING_LITERAL, v, span);
}

struct Expression*
ir_make_bool(bool value, struct Span span)
{
    union Expression_Value v = { 0 };
    v.bool_literal.value = value;
    return expression_new(EXPRESSION_BOOLEAN_LITERAL, v, span);
}

struct Expression*
ir_make_name(struct String name, struct Span span)
{
    union Expression_Value v = { 0 };
    v.name.name = name;
    return expression_new(EXPRESSION_NAME, v, span);
}

struct Expression*
ir_make_unary(enum Unary_Operation op, struct Expression* operand, struct Span span)
{
    union Expression_Value v = { 0 };
    v.unary_operator.operation = op;
    v.unary_operator.operand = operand;
    return expression_new(EXPRESSION_UNARY_OPERATION, v, span);
}

struct Expression*
ir_make_binary(
    enum Binary_Operation op, struct Expression* left, struct Expression* right, struct Span span)
{
    union Expression_Value v = { 0 };
    v.binary_operator.operation = op;
    v.binary_operator.left_operand = left;
    v.binary_operator.right_operand = right;
    return expression_new(EXPRESSION_BINARY_OPERATION, v, span);
}

struct Expression*
ir_make_sizeof(struct Type_Ref target, struct Span span)
{
    union Expression_Value v = { 0 };
    v.sizeof_operator.target = target;
    return expression_new(EXPRESSION_SIZEOF_OPERATION, v, span);
}

struct Expression*
ir_make_call(struct Expression* subject, Array(struct Call_Argument) arguments, struct Span span)
{
    union Expression_Value v = { 0 };
    v.call.subject = subject;
    v.call.arguments = arguments;
    return expression_new(EXPRESSION_CALL, v, span);
}

struct Expression*
ir_make_member(struct Expression* subject, struct String name, struct Span span)
{
    union Expression_Value v = { 0 };
    v.member.subject = subject;
    v.member.name = name;
    return expression_new(EXPRESSION_MEMBER, v, span);
}

struct Expression*
ir_make_subscript(struct Expression* subject, struct Expression* index, struct Span span)
{
    union Expression_Value v = { 0 };
    v.subscript.subject = subject;
    v.subscript.index = index;
    return expression_new(EXPRESSION_SUBSCRIPT, v, span);
}

struct Expression*
ir_make_cast(struct Type_Ref target, struct Expression* operand, struct Span span)
{
    union Expression_Value v = { 0 };
    v.cast.target = target;
    v.cast.operand = operand;
    return expression_new(EXPRESSION_CAST, v, span);
}

struct Expression*
ir_make_construct(Type_Id type_id, Array(struct Construct_Field) fields, struct Span span)
{
    union Expression_Value v = { 0 };
    v.construct.type_id = type_id;
    v.construct.fields = fields;
    return expression_new(EXPRESSION_CONSTRUCT, v, span);
}

struct Type_Ref
type_ref_bare(Type_Id type_id)
{
    return (struct Type_Ref){
        .type_id = type_id,
        .mods = array_new(enum Type_Modifier, 4),
    };
}

struct Type_Ref
type_ref_pointer(Type_Id type_id)
{
    struct Type_Ref ref = type_ref_bare(type_id);
    enum Type_Modifier mod = TYPE_MOD_REFERENCE;
    array_push(&ref.mods, &mod);
    return ref;
}

struct Type_Ref
type_ref_with_mods(Type_Id type_id, Array(enum Type_Modifier) mods)
{
    return (struct Type_Ref){
        .type_id = type_id,
        .mods = mods,
    };
}

// statement builder family.
// same shape as the expression builders: wrap the union-init around
// `statement_new` so call sites stay readable.

struct Statement*
ir_make_declaration(
    struct String name, struct Type_Ref type, struct Expression* initializer, struct Span span)
{
    union Statement_Value v = { 0 };
    v.declaration.name = name;
    v.declaration.type = type;
    v.declaration.initializer = initializer;
    return statement_new(STATEMENT_DECLARATION, v, span);
}

struct Statement*
ir_make_assign(struct Expression* lhs, struct Expression* rhs, struct Span span)
{
    union Statement_Value v = { 0 };
    v.assign.lhs = lhs;
    v.assign.rhs = rhs;
    return statement_new(STATEMENT_ASSIGN, v, span);
}

struct Statement*
ir_make_expression_statement(struct Expression* inner, struct Span span)
{
    union Statement_Value v = { 0 };
    v.expression.inner = inner;
    return statement_new(STATEMENT_EXPRESSION, v, span);
}

struct Statement*
ir_make_conditional(Array(struct If_Branch) branches, struct Span span)
{
    union Statement_Value v = { 0 };
    v.conditional.branches = branches;
    return statement_new(STATEMENT_CONDITIONAL, v, span);
}

struct Statement*
ir_make_loop(struct Expression* condition, struct Block* body, struct Span span)
{
    union Statement_Value v = { 0 };
    v.loop.condition = condition;
    v.loop.body = body;
    return statement_new(STATEMENT_LOOP, v, span);
}

struct Statement*
ir_make_return(struct Expression* value, struct Span span)
{
    union Statement_Value v = { 0 };
    v.return_value.value = value;
    return statement_new(STATEMENT_RETURN, v, span);
}

struct Statement*
ir_make_break(struct Span span)
{
    union Statement_Value v = { 0 };
    return statement_new(STATEMENT_BREAK, v, span);
}

struct Statement*
ir_make_continue(struct Span span)
{
    union Statement_Value v = { 0 };
    return statement_new(STATEMENT_CONTINUE, v, span);
}

struct Statement*
ir_make_block_statement(struct Block* inner, struct Span span)
{
    union Statement_Value v = { 0 };
    v.block.inner = inner;
    return statement_new(STATEMENT_BLOCK, v, span);
}

struct Statement*
ir_make_label(struct String name, struct Span span)
{
    union Statement_Value v = { 0 };
    v.label.name = name;
    return statement_new(STATEMENT_LABEL, v, span);
}

struct Statement*
ir_make_goto(struct String target, struct Span span)
{
    union Statement_Value v = { 0 };
    v.goto_target.target = target;
    return statement_new(STATEMENT_GOTO, v, span);
}