Intermediate representation taxonomy

Signed-off-by: Mel <mel@rnrd.eu>

2 files changed, 544 insertions, 0 deletions

diff --git a/boot/catboot.h b/boot/catboot.h
index 00764f0..e5ffe5e 100644
--- a/boot/catboot.h
+++ b/boot/catboot.h
@@ -18,5 +18,6 @@
 #include "tree.c"
 #include "parse.c"
 #include "visit/tree.c"
+#include "ir.c"
 #include "transpile.c"
 #include "build.c"
diff --git a/boot/ir.c b/boot/ir.c
new file mode 100644
index 0000000..54ee2b3
--- /dev/null
+++ b/boot/ir.c
@@ -0,0 +1,543 @@
+/*
+ * 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;
+};
+
+struct Expression_Call
+{
+    struct Expression* subject;
+    // call arguments are positional, named and out-of-order
+    // arguments get re-ordered until they are correct.
+    Array(struct Expression*) 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 Diagnostic_Severity
+{
+    DIAGNOSTIC_NOTE,
+    DIAGNOSTIC_WARNING,
+    DIAGNOSTIC_ERROR,
+};
+
+// TODO: we might want to take this out to be used for other passes.
+struct Diagnostic
+{
+    enum Diagnostic_Severity severity;
+    struct Span span;
+    struct String message;
+};
+
+// 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 Diagnostic) diagnostics;
+};
+
+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;
+}