type_check.cpp

#include "type_check.h"
#include "ast.h"
#include "nc_log.h"
#include "nc_memory.h"
#include "nc_print.h"
#include "type.h"
#include "token.h"
#include "symbol_table.h"
#include "parser.h"
#include "nc_tls.h"

#define CHECK_EXPR_NONE 0

internal const u8 SCALAR_RANK[BUILTIN_b64 + 1] = {
    0,
    2, 
    5, 
    8, 
    11,
    3, 
    6, 
    9, 
    12,
    13, 
    14,
    1, 
    4,
    7,
    10
};

INTERNAL b32
IsScalar(TypeIndex T)
{
    return (T.V - 1u) < (u32) BUILTIN_b64;
}

INTERNAL b32
IsUntyped(TypeIndex T)
{
    return T.V == TYPE_INDEX_INVALID_TYPE;
}

INTERNAL b32
IsVoid(TypeIndex T)
{
    return T.V == BUILTIN_void;
}

INTERNAL b32
IsAggregate(TypeIndex T)
{
    b32 Result = FALSE;

    if (
        !IsUntyped(T) && 
        !IsVoid(T) && 
        !IsScalar(T)
    ) {
        TypeKind Kind = TypeAt(T)->Kind;

        Result = (
            Kind == TYPE_KIND_STRUCT ||
            Kind == TYPE_KIND_UNION ||
            Kind == TYPE_KIND_INSTANCE
        );
    }

    return Result;
}

INTERNAL u32
ResolvedHash(ExprIndex Expr)
{
    return (u32) Expr.V * 2654435761U;
}

BindIndex
ASTResolvedFind(AST *Tree, ExprIndex Expr)
{
    BindIndex Result = {
        BINDING_INVALID_VALUE
    };

    if (Tree->ResolvedMask) {
        u32 ExprHash = ResolvedHash(Expr);
        u32 SlotIndex = ExprHash & Tree->ResolvedMask;

        while (Tree->Resolved[SlotIndex].Expr.V) {
            if (Tree->Resolved[SlotIndex].Expr.V == Expr.V) {
                Result = Tree->Resolved[SlotIndex].Bind;
                break;
            }

            SlotIndex = (SlotIndex + 1) & Tree->ResolvedMask;
        }
    }

    return Result;
}

internal void
ResolvedInsert(AST* Tree, ExprIndex Expr, BindIndex Bind)
{
    ASSERT(Expr.V != CHECK_EXPR_NONE);

    if ((Tree->ResolvedCount + 1) * 2 > Tree->ResolvedMask + 1) {
        u32 OldMask = Tree->ResolvedMask;
        ASTResolved* Old = Tree->Resolved;
        u32 NewMask = OldMask ? (OldMask * 2 + 1) : 63;

        Tree->Resolved = ArenaPushArrayZero(
            Tree->MemPool,
            ASTResolved,
            NewMask + 1
        );
        Tree->ResolvedMask = NewMask;

        for (u32 Index = 0; Old && Index <= OldMask; ++Index) {
            if (!Old[Index].Expr.V)
                continue;

            u32 OldExprHash = ResolvedHash(Old[Index].Expr);
            u32 SlotIndex = OldExprHash & NewMask;

            while (Tree->Resolved[SlotIndex].Expr.V)
                SlotIndex = (SlotIndex + 1) & NewMask;

            Tree->Resolved[SlotIndex] = Old[Index];
        }
    }

    u32 ExprHash = ResolvedHash(Expr);
    u32 SlotIndex = ExprHash & Tree->ResolvedMask;

    while (
        Tree->Resolved[SlotIndex].Expr.V && 
        Tree->Resolved[SlotIndex].Expr.V != Expr.V
    ) {
        SlotIndex = (SlotIndex + 1) & Tree->ResolvedMask;
    }

    if (!Tree->Resolved[SlotIndex].Expr.V)
        ++Tree->ResolvedCount;

    Tree->Resolved[SlotIndex].Expr = Expr;
    Tree->Resolved[SlotIndex].Bind = Bind;
}

internal TypeIndex
ValueType(TypeIndex TIndex)
{
    TypeIndex Result = TIndex;

    if (
        IsUntyped(TIndex) ||
        IsVoid(TIndex) ||
        IsScalar(TIndex)
    ) {
        return Result;
    }

    Type* Info = TypeAt(TIndex);

    switch (Info->Kind) {
        default: {} break;

        case TYPE_KIND_ENUM: {
            if (Info->B == TYPE_INDEX_INVALID_TYPE)
                Result.V = CHECK_DEFAULT_INT_TYPE;
            else
                Result.V = Info->B;
        } break;

        case TYPE_KIND_ARR: {
            Result.V = Info->A;
            Result = TypePtrTo(Result);
        } break;
    }

    return Result;
}

API_INTERNAL b32
IsPtr(TypeIndex TIndex)
{
    b32 Result = (
        !IsUntyped(TIndex) &&
        !IsVoid(TIndex) &&
        TypeAt(TIndex)->Kind == TYPE_KIND_PTR
    );

    return Result;
}

INTERNAL ASTNodeExprAccel*
ExprAt(AST* Tree, ExprIndex Index)
{
    return (ASTNodeExprAccel*) (Tree->Exprs + Index.V);
}

INTERNAL ExprIndex
ImplicitChild(AST* Tree, void* Node, u32 NodeSize)
{
    ExprIndex Result = {
        (i32) (((u8*) Node + NodeSize) - Tree->Exprs)
    };

    return Result;
}

INTERNAL TypeIndex
TypeOf(AST* Tree, ExprIndex Index)
{
    ASTNodeExprAccel* Node = ExprAt(Tree, Index);
    TypeIndex Result = {
        BUILTIN_void
    };

    if (ASTExprIsTyped(Node->Header.Type))
        Result = Node->Type;

    return Result;
}

INTERNAL u32
OffsetOf(Token* Tokens, ASTNodeHeader* Header)
{
    return Tokens[Header->Tok.V].Offset;
}

INTERNAL AdoptFrame*
AdoptPush(Arena* MemPool, AdoptFrame* Head, ExprIndex Expr)
{
    AdoptFrame* Result = ArenaPushStruct(MemPool, AdoptFrame);

    Result->Prev = Head;
    Result->Expr = Expr;

    return Result;
}

internal void
Adopt(AST* Tree, ExprIndex Root, TypeIndex TIndex)
{
    TempArena Scratch = GetScratch(NULL, 0);
    AdoptFrame* Head = NULL;
    ExprIndex EIndex = Root;

    for (;;) {
        ASTNodeExprAccel* Node = ExprAt(Tree, EIndex);
        ExprIndex Next = {
            CHECK_EXPR_NONE
        };

        if (ASTExprIsTyped(Node->Header.Type) && IsUntyped(Node->Type)) {
            Node->Type = TIndex;

            switch (Node->Header.Type) {
                default: {} break;

                case AST_UNARY_EXPR:
                case AST_PRE_INCR:
                case AST_POST_INCR: {
                    Next = ((ASTNodeUnary*) Node)->Expr;
                } break;

                case AST_BINARY_EXPR: {
                    Head = AdoptPush(
                        Scratch.MemPool,
                        Head,
                        ((ASTNodeBinary*) Node)->Left
                    );
                    Next = ImplicitChild(Tree, Node, sizeof(ASTNodeBinary));
                } break;

                case AST_TERNARY_EXPR: {
                    Head = AdoptPush(
                        Scratch.MemPool,
                        Head,
                        ((ASTNodeTernary*) Node)->Then
                    );
                    Next = ImplicitChild(Tree, Node, sizeof(ASTNodeTernary));
                } break;
            }
        }

        if (Next.V != CHECK_EXPR_NONE) {
            EIndex = Next;
        } else if (Head) {
            EIndex = Head->Expr;
            Head = Head->Prev;
        } else {
            break;
        }
    }

    ReleaseScratch(Scratch);
}

INTERNAL TypeIndex
Defaulted(TypeIndex TIndex)
{
    TypeIndex Result = {
        CHECK_DEFAULT_INT_TYPE
    };

    if (!IsUntyped(TIndex))
        Result = TIndex;

    return Result;
}

INTERNAL b32
IsConvertible(TypeIndex From, TypeIndex To)
{
    if (
        From.V == To.V || 
        IsUntyped(From) || 
        IsVoid(From) || 
        IsVoid(To)
    ) {
        return TRUE;
    }

    From = ValueType(From);
    To = ValueType(To);

    if (From.V == To.V)
        return TRUE;

    if (IsScalar(From) && IsScalar(To))
        return TRUE;

    if (IsPtr(From) && IsPtr(To)) {
        return (
            TypeAt(From)->A == BUILTIN_void ||
            TypeAt(To)->A == BUILTIN_void
        );
    }

    return FALSE;
}

internal TypeIndex
Promote(TypeIndex LHS, TypeIndex RHS)
{
    TypeIndex Result = {
        BUILTIN_void
    };

    if (IsUntyped(LHS)) {
        Result = RHS;
    } else if (IsUntyped(RHS)) {
        Result = LHS;
    } else if (LHS.V == RHS.V) {
        Result = LHS;
    } else if (
        IsVoid(LHS) ||
        IsVoid(RHS)
    ) {
        Result.V = BUILTIN_void;
    } else if (IsScalar(LHS) && IsScalar(RHS)) {
        if (SCALAR_RANK[LHS.V] >= SCALAR_RANK[RHS.V])
            Result = LHS;
        else
            Result = RHS;
    }

    return Result;
}

internal BindIndex
ResolveCall(
    AST* Tree,
    BindIndex Head,
    ExprIndex const* Expressions,
    i32 Step,
    TypeIndex const* Types,
    u32 Count,
    OUT TypeIndex* Return
) {
    BindIndex Result = {
        BINDING_INVALID_VALUE
    };
    TypeIndex CandidateField = {
        TYPE_INDEX_INVALID_TYPE
    };
    TypeIndex CandidateBound[TYPE_GENERIC_MAX] = {};
    u32 CandidateScore = 0;
    b32 CandidateGeneric = FALSE;

    for (BindIndex Candidate = Head; Candidate.V != BINDING_INVALID_VALUE; ) {
        Binding* B = &GetTLS()->SYMBOL_TABLE->Bindings[Candidate.V];
        TypeIndex F = B->Type;
        BindIndex CurrentCandidate = Candidate;

        Candidate = B->Overload;

        if (
            IsUntyped(F) ||
            TypeAt(F)->Kind != TYPE_KIND_FUNC ||
            TypeAt(F)->Count != Count
        ) {
            continue;
        }

        TypeIndex const* Sig = TypeArgs(TypeAt(F));
        b32 IsGeneric = !!(TypeAt(F)->Flags & TYPE_FLAG_GENERIC);
        TypeIndex Bound[TYPE_GENERIC_MAX] = {};
        u32 Score = 0;
        b32 IsOkay = TRUE;

        if (IsGeneric) {
            for (u32 Index = 0; Index < TYPE_GENERIC_MAX; ++Index)
                Bound[Index].V = TYPE_INDEX_INVALID_TYPE;
        }

        for (u32 Index = 0; Index < Count && IsOkay; ++Index) {
            TypeIndex P = Sig[Index + 1];
            TypeIndex A = Types
                ? Types[Index]
                : TypeOf(Tree, Expressions[(i32) Index * Step]);

            if (TypeAt(P)->Flags & TYPE_FLAG_GENERIC) {
                IsOkay = TypeUnify(P, A, Bound, TYPE_GENERIC_MAX);
                Score += !IsUntyped(A);
            } else if (P.V == A.V) {
                ++Score;
            } else {
                IsOkay = IsConvertible(A, P);
            }
        }

        if (
            IsOkay && 
            (
                Result.V == BINDING_INVALID_VALUE || 
                Score >= CandidateScore
            )
        ) {
            Result = CurrentCandidate;
            CandidateField = F;
            CandidateScore = Score;
            CandidateGeneric = IsGeneric;

            if (IsGeneric)
                MemCpy(CandidateBound, Bound, sizeof(Bound));
        }
    }

    if (Result.V != BINDING_INVALID_VALUE) {
        TypeIndex const* Sig = TypeArgs(TypeAt(CandidateField));

        for (u32 Index = 0; Index < Count; ++Index) {
            TypeIndex P = Sig[Index + 1];
            ExprIndex EIndex = Expressions[(i32) Index * Step];

            if (CandidateGeneric)
                P = TypeSub(P, CandidateBound, TYPE_GENERIC_MAX);

            if (EIndex.V != CHECK_EXPR_NONE)
                Adopt(Tree, EIndex, P);
        }


        if (CandidateGeneric)
            *Return = TypeSub(Sig[0], CandidateBound, TYPE_GENERIC_MAX);
        else
            *Return = Sig[0];
    }

    return Result;
}

internal void
ResolveOperator(
    AST* Tree,
    Token* Tokens,
    ASTNodeExprAccel* Node,
    ExprIndex Self,
    NameIndex Name,
    ExprIndex const* Expressions,
    TypeIndex const* Types,
    u32 Count
) {
    BindIndex Head = FindBinding(Name);
    BindIndex Chosen = {
        BINDING_INVALID_VALUE
    };
    TypeIndex Return = {
        BUILTIN_void
    };

    if (
        Head.V != BINDING_INVALID_VALUE &&
        GetTLS()->SYMBOL_TABLE->Bindings[Head.V].Kind == BINDING_KIND_FUNC
    ) {
        Chosen = ResolveCall(Tree, Head, Expressions, 1, Types, Count, &Return);
    }

    if (Chosen.V == BINDING_INVALID_VALUE) {
        Str8 NameString = GetName(GetTLS()->SYMBOL_TABLE->Names, Name);

        LogError(
            "no matching operator %S for these operands at offset %u",
            PRINT_STR(NameString),
            OffsetOf(Tokens, &Node->Header)
        );
        Node->Type.V = BUILTIN_void;
    } else {
        Node->Header.Flags |= AST_EXPR_FLAG_OVERLOADED;
        ResolvedInsert(Tree, Self, Chosen);
        Node->Type = Return;
    }
}

internal void
CheckExpr(AST* Tree, ASTNodeExprAccel* Node, ExprIndex Self, Token* Tokens)
{
    switch (Node->Header.Type) {
        default: {} break;

        case AST_LITERAL: {} break;

        case AST_IDENT: {
            ASTNodeExprIdent* Ident = (ASTNodeExprIdent*) Node;

            if (Ident->Bind.V == BINDING_INVALID_VALUE) {
                Node->Type.V = BUILTIN_void;
                break;
            }

            Binding* B = &GetTLS()->SYMBOL_TABLE->Bindings[Ident->Bind.V];

            if (
                B->Kind != BINDING_KIND_VALUE &&
                B->Kind != BINDING_KIND_FUNC
            ) {
                LogError(
                    "type name used as a value at offset %u", 
                    OffsetOf(Tokens, &Node->Header)
                );
                Node->Type.V = BUILTIN_void;
                break;
            }

            if (IsUntyped(B->Type)) {
                LogError(
                    "type of identifier is not known at this point, at offset %u", 
                    OffsetOf(Tokens, &Node->Header)
                );
                Node->Type = {
                    BUILTIN_void
                };
                break;
            }

            Node->Type = B->Type;
        } break;

        case AST_PRE_INCR:
        case AST_POST_INCR: {
            Node->Type = TypeOf(Tree, ((ASTNodeUnary*) Node)->Expr);
        } break;

        case AST_UNARY_EXPR: {
            ExprIndex Operand = ((ASTNodeUnary*) Node)->Expr;
            TypeIndex T = TypeOf(Tree, Operand);

            if (
                IsAggregate(T) &&
                Node->Header.Variant != TOKEN_KIND_BIT_AND &&
                Node->Header.Variant != TOKEN_KIND_STAR
            ) {
                ResolveOperator(
                    Tree, 
                    Tokens, 
                    Node, 
                    Self,
                    OP_NAMES[Node->Header.Variant], 
                    &Operand,
                    &T,
                    1
                );
                break;
            }

            switch (Node->Header.Variant) {
                default: {
                    Node->Type = T;
                } break;

                case TOKEN_KIND_EXCLAIM: {
                    Adopt(Tree, Operand, Defaulted(T));
                    Node->Type.V = BUILTIN_b32;
                } break;

                case TOKEN_KIND_BIT_AND: {
                    if (IsUntyped(T)) {
                        LogError(
                            "cannot take the address of a literal at offset %u", 
                            OffsetOf(Tokens, &Node->Header)
                        );
                        Node->Type.V = BUILTIN_void;
                    } else if (IsVoid(T)) {
                        Node->Type = T;
                    } else {
                        Node->Type = TypePtrTo(T);
                    }
                } break;

                case TOKEN_KIND_STAR: {
                    if (IsVoid(T)) {
                        Node->Type = T;
                    } else if (
                        !IsUntyped(T) && 
                        TypeAt(T)->Kind == TYPE_KIND_PTR
                    ) {
                        Node->Type.V = TypeAt(T)->A;
                    } else {
                        LogError(
                            "cannot dereference a non-pointer at offset %u", 
                            OffsetOf(Tokens, &Node->Header)
                        );
                        Node->Type.V = BUILTIN_void;
                    }
                } break;
            }
        } break;

        case AST_BINARY_EXPR: {
            ExprIndex Left = ((ASTNodeBinary*) Node)->Left;
            ExprIndex Right = ImplicitChild(Tree, Node, sizeof(ASTNodeBinary));
            TypeIndex LHS = ValueType(TypeOf(Tree, Left));
            TypeIndex RHS = ValueType(TypeOf(Tree, Right));

            if (IsAggregate(LHS) || IsAggregate(RHS)) {
                ExprIndex OpExpressions[2] = {
                    Left,
                    Right
                };
                TypeIndex OpTypes[2] = {
                    LHS,
                    RHS
                };

                ResolveOperator(
                    Tree, 
                    Tokens, 
                    Node, 
                    Self, 
                    OP_NAMES[Node->Header.Variant], 
                    OpExpressions, 
                    OpTypes, 
                    2
                );
                break;
            }

            switch (Node->Header.Variant) {
                case TOKEN_KIND_LESS:
                case TOKEN_KIND_GREATER:
                case TOKEN_KIND_LESS_EQ:
                case TOKEN_KIND_GREATER_EQ:
                case TOKEN_KIND_EQ_EQ:
                case TOKEN_KIND_EXCLAIM_EQ: {
                    TypeIndex Common = Defaulted(Promote(LHS, RHS));

                    if (IsPtr(LHS) && IsPtr(RHS))
                        Common = LHS;

                    if (
                        IsVoid(Common) && 
                        !IsVoid(LHS) && 
                        !IsVoid(RHS)
                    ) {
                        LogError(
                            "cannot compare these types at offset %u", 
                            OffsetOf(Tokens, &Node->Header)
                        );
                    }

                    Adopt(Tree, Left, Common);
                    Adopt(Tree, Right, Common);
                    Node->Type.V = BUILTIN_b32;
                } break;

                case TOKEN_KIND_LOG_AND:
                case TOKEN_KIND_LOG_OR: {
                    Adopt(Tree, Left, Defaulted(LHS));
                    Adopt(Tree, Right, Defaulted(RHS));
                    Node->Type.V = BUILTIN_b32;
                } break;

                case TOKEN_KIND_L_SHIFT:
                case TOKEN_KIND_R_SHIFT: {
                    Adopt(Tree, Right, Defaulted(RHS));
                    Node->Type = LHS;
                } break;

                default: {
                    b32 LeftPtr = IsPtr(LHS);
                    b32 RightPtr = IsPtr(RHS);
                    b32 Additive = (
                        Node->Header.Variant == TOKEN_KIND_PLUS || 
                        Node->Header.Variant == TOKEN_KIND_MINUS
                    );

                    if (
                        LeftPtr && 
                        RightPtr && 
                        Node->Header.Variant == TOKEN_KIND_MINUS
                    ) {
                        Node->Type.V = BUILTIN_i64;
                    } else if (
                        LeftPtr && 
                        Additive && 
                        (
                            IsUntyped(RHS) || 
                            IsScalar(RHS)
                        )
                    ) {
                        Adopt(Tree, Right, Defaulted(RHS));
                        Node->Type = LHS;
                    } else if (
                        RightPtr && 
                        Node->Header.Variant == TOKEN_KIND_PLUS && 
                        (
                            IsUntyped(LHS) || 
                            IsScalar(LHS)
                        )
                    ) {
                        Adopt(Tree, Left, Defaulted(LHS));
                        Node->Type = RHS;
                    } else {
                        TypeIndex Common = Promote(LHS, RHS);

                        if (
                            IsVoid(Common) && 
                            !IsVoid(LHS) && 
                            !IsVoid(RHS)
                        ) {
                            LogError(
                                "operands have incompatible types at offset %u", 
                                OffsetOf(Tokens, &Node->Header)
                            );
                        }

                        if (!IsUntyped(Common)) {
                            Adopt(Tree, Left, Common);
                            Adopt(Tree, Right, Common);
                        }

                        Node->Type = Common;
                    }
                } break;
            }
        } break;

        case AST_BINARY_ASSIGNMENT: {
            ExprIndex Left = ((ASTNodeBinary*) Node)->Left;
            ExprIndex Right = ImplicitChild(Tree, Node, sizeof(ASTNodeBinary));
            TypeIndex LHS = TypeOf(Tree, Left);
            TypeIndex RHS = TypeOf(Tree, Right);

            if (Node->Header.Variant != TOKEN_KIND_EQUAL && IsAggregate(LHS)) {
                ExprIndex OpExpressions[2] = {
                    {
                        CHECK_EXPR_NONE
                    },
                    Right
                };
                TypeIndex OpTypes[2] = {
                    TypePtrTo(LHS),
                    RHS
                };

                ResolveOperator(
                    Tree,
                    Tokens,
                    Node,
                    Self,
                    OP_NAMES[Node->Header.Variant],
                    OpExpressions,
                    OpTypes,
                    2
                );
                break;
            }

            if (Node->Header.Variant == TOKEN_KIND_EQUAL) {
                ASTNodeExprAccel* LeftNode = ExprAt(Tree, Left);

                if (
                    LeftNode->Header.Type == AST_INDEX &&
                    (LeftNode->Header.Flags & AST_EXPR_FLAG_OVERLOADED)
                ) {
                    ExprIndex Base = ((ASTNodeBinary*) LeftNode)->Left;
                    ExprIndex Index = ImplicitChild(
                        Tree, 
                        LeftNode, 
                        sizeof(ASTNodeBinary)
                    );
                    ExprIndex OpExpressions[3] = {
                        {
                            CHECK_EXPR_NONE
                        },
                        Index,
                        Right
                    };
                    TypeIndex OpTypes[3] = {
                        TypePtrTo(TypeOf(Tree, Base)),
                        TypeOf(Tree, Index),
                        RHS
                    };

                    ResolveOperator(
                        Tree,
                        Tokens,
                        LeftNode,
                        Left,
                        OP_NAME_INDEX_ASSIGN,
                        OpExpressions,
                        OpTypes,
                        3
                    );
                    Node->Header.Flags |= AST_EXPR_FLAG_OVERLOADED;
                    Node->Type = TypeOf(Tree, Right);
                    break;
                }
            }

            if (IsUntyped(LHS)) {
                LogError(
                    "cannot assign to a literal at offset %u", 
                    OffsetOf(Tokens, &Node->Header)
                );
                LHS.V = BUILTIN_void;
            }

            Adopt(Tree, Right, LHS);

            if (!IsConvertible(RHS, LHS)) {
                LogError(
                    "cannot convert in assignment at offset %u", 
                    OffsetOf(Tokens, &Node->Header)
                );
            }

            Node->Type = LHS;
        } break;

        case AST_TERNARY_EXPR: {
            ASTNodeTernary* Ternary = (ASTNodeTernary*) Node;
            ExprIndex Else = ImplicitChild(Tree, Node, sizeof(ASTNodeTernary));
            TypeIndex Common = Promote(
                TypeOf(Tree, Ternary->Then), 
                TypeOf(Tree, Else)
            );

            Adopt(Tree, Ternary->Cond, Defaulted(TypeOf(Tree, Ternary->Cond)));

            if (!IsUntyped(Common)) {
                Adopt(Tree, Ternary->Then, Common);
                Adopt(Tree, Else, Common);
            }

            Node->Type = Common;
        } break;

        case AST_INDEX: {
            ExprIndex Base = ((ASTNodeBinary*) Node)->Left;
            ExprIndex Index = ImplicitChild(Tree, Node, sizeof(ASTNodeBinary));
            TypeIndex T = TypeOf(Tree, Base);

            if (IsAggregate(T)) {
                ExprIndex OpExpressions[2] = {
                    Base,
                    Index
                };
                TypeIndex OpTypes[2] = {
                    T,
                    TypeOf(Tree, Index)
                };

                ResolveOperator(
                    Tree,
                    Tokens,
                    Node,
                    Self,
                    OP_NAME_INDEX,
                    OpExpressions,
                    OpTypes,
                    2
                );
                break;
            }

            Adopt(Tree, Index, Defaulted(TypeOf(Tree, Index)));

            if (IsVoid(T)) {
                Node->Type = T;
            } else if (
                !IsUntyped(T) && 
                (
                    TypeAt(T)->Kind == TYPE_KIND_ARR || 
                    TypeAt(T)->Kind == TYPE_KIND_PTR
                )
            ) {
                Node->Type = {TypeAt(T)->A};
            } else {
                LogError(
                    "cannot index this type at offset %u", 
                    OffsetOf(Tokens, &Node->Header)
                );
                Node->Type.V = BUILTIN_void;
            }
        } break;

        case AST_FUNC_CALL: {
            ASTNodeFuncCall* Call = (ASTNodeFuncCall*) Node;
            TypeIndex F = TypeOf(Tree, Call->Func);
            u32 ArgCount = Call->Header.Count;
            ASTNodeExprAccel* FuncNode = ExprAt(Tree, Call->Func);

            if (IsVoid(F)) {
                Node->Type = F;
                break;
            }

            if (FuncNode->Header.Type == AST_IDENT) {
                BindIndex Head = ((ASTNodeExprIdent*) FuncNode)->Bind;

                if (
                    Head.V != BINDING_INVALID_VALUE &&
                    GetTLS()->SYMBOL_TABLE->Bindings[Head.V].Kind == BINDING_KIND_FUNC &&
                    (
                        GetTLS()->SYMBOL_TABLE->Bindings[Head.V].Overload.V != BINDING_INVALID_VALUE ||
                        (
                            !IsUntyped(F) && 
                            (TypeAt(F)->Flags & TYPE_FLAG_GENERIC)
                        )
                    )
                ) {
                    TypeIndex Return = {
                        BUILTIN_void
                    };
                    BindIndex Chosen = ResolveCall(
                        Tree,
                        Head,
                        Call->Arg + (ArgCount - 1),
                        -1,
                        NULL,
                        ArgCount,
                        &Return
                    );

                    if (Chosen.V == BINDING_INVALID_VALUE) {
                        LogError(
                            "no matching overload for call at offset %u",
                            OffsetOf(Tokens, &Node->Header)
                        );
                        Node->Type.V = BUILTIN_void;
                    } else {
                        if (IsUntyped(Return)) {
                            LogError(
                                "cannot infer generic type from the arguments at offset %u",
                                OffsetOf(Tokens, &Node->Header)
                            );
                            Return.V = BUILTIN_void;
                        }

                        if (Chosen.V != Head.V)
                            ResolvedInsert(Tree, Self, Chosen);

                        Node->Type = Return;
                    }

                    break;
                }
            }

            if (
                !IsUntyped(F) && 
                TypeAt(F)->Kind == TYPE_KIND_PTR
            ) {
                F.V = TypeAt(F)->A;
            }

            if (IsUntyped(F) || TypeAt(F)->Kind != TYPE_KIND_FUNC) {
                LogError(
                    "call of a non-function at offset %u", 
                    OffsetOf(Tokens, &Node->Header)
                );
                Node->Type.V = BUILTIN_void;
                break;
            }

            Type* Func = TypeAt(F);
            TypeIndex const* Sig = TypeArgs(Func);

            if (ArgCount != Func->Count) {
                LogError(
                    "expected %u arguments, got %u at offset %u",
                    Func->Count,
                    ArgCount,
                    OffsetOf(Tokens, &Node->Header)
                );
            }

            u32 Checked = MIN(ArgCount, (u32) Func->Count);

            for (u32 Index = 0; Index < Checked; ++Index) {
                u32 ParamIndex = ArgCount - 1 - Index;
                ExprIndex Arg = Call->Arg[Index];
                TypeIndex Param = Sig[1 + ParamIndex];

                Adopt(Tree, Arg, Param);

                if (!IsConvertible(TypeOf(Tree, Arg), Param)) {
                    LogError(
                        "cannot convert argument %u at offset %u", 
                        ParamIndex, 
                        OffsetOf(Tokens, &Node->Header)
                    );
                }
            }

            Node->Type = Sig[0];
        } break;

        case AST_FIELD_ACCESS: {
            ASTNodeFieldAccess* Access = (ASTNodeFieldAccess*) Node;
            ExprIndex Base = ImplicitChild(Tree, Node, sizeof(ASTNodeFieldAccess));
            TypeIndex T = TypeOf(Tree, Base);

            Access->Field.V = AST_NODE_INDEX_INVALID;

            if (IsVoid(T)) {
                Node->Type = T;
                break;
            }

            if (IsUntyped(T)) {
                LogError(
                    "field access on a literal at offset %u",
                    OffsetOf(Tokens, &Node->Header)
                );
                Node->Type.V = BUILTIN_void;
                break;
            }

            if (Node->Header.Variant == TOKEN_KIND_ARROW) {
                if (!IsPtr(T)) {
                    LogError(
                        "\"->\" on a non-pointer at offset %u",
                        OffsetOf(Tokens, &Node->Header)
                    );
                    Node->Type.V = BUILTIN_void;
                    break;
                }

                T.V = TypeAt(T)->A;
            }

            TypeIndex const* Args = NULL;
            u32 ArgsCount = 0;
            Type const* Info = TypeAt(T);

            if (Info->Kind == TYPE_KIND_INSTANCE) {
                ASTNodeDeclType* Generic = (ASTNodeDeclType*) (Tree->Decls + Info->A);

                Args = TypeArgs(Info);
                ArgsCount = Info->Count;
                T = Generic->Type;
                Info = TypeAt(T);
            }

            if (Info->Kind != TYPE_KIND_STRUCT && Info->Kind != TYPE_KIND_UNION) {
                LogError(
                    "field access on a non-aggregate at offset %u",
                    OffsetOf(Tokens, &Node->Header)
                );
                Node->Type.V = BUILTIN_void;
                break;
            }

            ASTNodeDeclEx* Aggregate = (ASTNodeDeclEx*) (Tree->Decls + Info->A);
            ASTField const* Members = (ASTField const*) (Tree->Decls + Aggregate->SubDeclList.V);
            u32 Found = Aggregate->Count;

            for (u32 Index = 0; Index < Aggregate->Count; ++Index) {
                if (Members[Index].Name.V == Access->Name.V) {
                    Found = Index;
                    break;
                }
            }

            if (Found == Aggregate->Count) {
                Str8 NameString = GetName(GetTLS()->SYMBOL_TABLE->Names, Access->Name);

                LogError(
                    "no member named \"%S\" at offset %u",
                    PRINT_STR(NameString),
                    OffsetOf(Tokens, &Node->Header)
                );
                Node->Type.V = BUILTIN_void;
                break;
            }

            DeclIndex FieldDecl = Members[Found].Decl;
            TypeIndex FieldType = ((ASTNodeDecl*) (Tree->Decls + FieldDecl.V))->Type;

            if (ArgsCount)
                FieldType = TypeSub(FieldType, Args, ArgsCount);

            Access->Field = FieldDecl;
            Node->Type = FieldType;
        } break;
    }
}

internal void
FinaliseBinding(AST* Tree, BindIndex Bind, Token* Tokens)
{
    Binding* B = &GetTLS()->SYMBOL_TABLE->Bindings[Bind.V];
    ASTNodeDecl* Decl = (ASTNodeDecl*) (Tree->Decls + B->Decl.V);
    ASTNodeHeader* Head = (ASTNodeHeader*) (Tree->Decls + Decl->FirstDecl.V);

    if (Head->Type != AST_DECLARATOR_VALUED) {
        if (IsUntyped(B->Type)) {
            LogError(
                "declaration has neither a type nor an initialiser at offset %u", 
                OffsetOf(Tokens, &Decl->Header)
            );
        }

        return;
    }

    ASTNodeHeader* Init = (ASTNodeHeader*) (
        Tree->Inits + ((ASTNodeDeclValued*) Head)->Init.V
    );

    if (Init->Type != AST_INITIALISER_EXPR)
        return;

    ExprIndex Root = ((ASTNodeInitialiserExpr*) Init)->Val;
    TypeIndex T = TypeOf(Tree, Root);

    if (!IsUntyped(B->Type)) {
        Adopt(Tree, Root, B->Type);

        if (!IsConvertible(T, B->Type)) {
            LogError(
                "cannot convert initialiser at offset %u", 
                OffsetOf(Tokens, &Decl->Header)
            );
        }

        return;
    }

    T = Defaulted(T);
    Adopt(Tree, Root, T);
    B->Type = T;
    Decl->Type = T;
}

internal void
CheckReturn(AST* Tree, ExprIndex Root, BindIndex FuncBind, Token* Tokens)
{
    if (FuncBind.V == BINDING_INVALID_VALUE)
        return;

    TypeIndex F = GetTLS()->SYMBOL_TABLE->Bindings[FuncBind.V].Type;

    if (IsUntyped(F) || TypeAt(F)->Kind != TYPE_KIND_FUNC)
        return;

    TypeIndex Return = TypeArgs(TypeAt(F))[0];
    TypeIndex T = TypeOf(Tree, Root);

    Adopt(Tree, Root, Return);

    if (!IsConvertible(T, Return)) {
        LogError(
            "cannot convert return value at offset %u", 
            OffsetOf(Tokens, &ExprAt(Tree, Root)->Header)
        );
    }
}

void
CheckAST(AST* Tree, TokenArray* Tokens)
{
    ExprIndex LastExpr = {};

    for (u32 Index = 0; Index < Tree->WorkCount; ++Index) {
        i32 Item = Tree->Work[Index];

        if (Item < 0) {
            LastExpr = {
                Item
            };
            CheckExpr(
                Tree, 
                ExprAt(Tree, LastExpr), 
                LastExpr, 
                Tokens->Tokens
            );
            continue;
        }

        u32 Kind = (u32) Item >> CHECK_WORK_KIND_OFFSET;
        u32 Arg = (u32) Item & CHECK_WORK_ARG_MASK;

        if (Kind == CHECK_WORK_KIND_BIND) {
            FinaliseBinding(
                Tree, 
                {
                    Arg
                }, 
                Tokens->Tokens
            );
        } else {
            CheckReturn(
                Tree, 
                LastExpr, 
                {
                    Arg
                }, 
                Tokens->Tokens
            );
        }
    }
}