path: root/bootstrap/ast.c

/*
 * Functions for constructing/accessing the Abstract Syntax Tree.
 *
 * Copyright © 2025-2026 Samuel Lidén Borell <samuel@kodafritt.se>
 *
 * SPDX-License-Identifier: EUPL-1.2+ OR LGPL-2.1-or-later
 */
#include <assert.h>
#include <string.h>
#include "compiler.h"


struct TreeNode *types = NULL;
struct TreeNode *toplevel_funcs = NULL;
/*struct TreeNode *toplevel_consts = NULL;*/
struct Type *types_list = NULL; /* including exported ones */
struct Func *toplevel_funcs_list = NULL;

struct Type *unbound_types_list = NULL;
struct Func *unbound_funcs_list = NULL;

struct Type *current_type = NULL;
struct Func *current_func = NULL;
static struct Type **type_nextptr;
static struct Func **func_nextptr;
static struct Func **type_func_nextptr;
static struct Func **type_ctor_nextptr;
/* TODO should constants in "utility files" be allowed? */
/*static struct Var **var_nextptr;*/
static struct Var **type_var_nextptr;

bool is_library = false;
bool interfaces_done = false;
bool in_exported_interface = false;
unsigned current_module_id = 0;


void ast_init(void)
{
    type_nextptr = &types_list;
    func_nextptr = &toplevel_funcs_list;
    /*var_nextptr = &toplevel_consts_list;*/
}

static void register_type(struct Type *t)
{
    assert(t->next == NULL);
    assert(t->prev == NULL);
    assert(current_type == NULL);
    *type_nextptr = t;
    type_nextptr = &t->next;
}

static void check_visibility(const struct Type *type)
{
    if (!interfaces_done && type->module_id != current_module_id &&
            type->module_id != CORE_MODULE_ID) {
        error_ident("Type has not been imported with `usetype` into the "
                    "interface", &type->ident);
    }
}

static void set_type_defaults(struct Type *t)
{
    t->module_id = current_module_id;
    t->funcs = NULL;
    t->funcs_list = NULL;
    t->funcs_exported = NULL;
    t->ctors = NULL;
    t->ctors_list = NULL;
    t->ctors_exported = NULL;
    t->ctor_default = NULL;
    t->vars = NULL;
    t->vars_list = NULL;
    t->vars_exported = NULL;
    t->svcspecs = NULL;
    t->svcspecs_list = NULL;
    t->enumvalues = NULL;
    t->enumvalues_list = NULL;
    t->is_export = false;
    t->is_implemented = false;
    t->has_initvals = false;
    t->is_enum = false;
    t->next = NULL;
    t->prev = NULL;
    t->sincever_next = NULL;
}

/* TODO Disallow identifiers that differ only in case
        (for example, `Int` and `int`, or `True` and `true`). */
static struct Type *map_named_type(const char *name, size_t len)
{
    struct Type *t;

    if (current_type &&
            len == current_type->ident.node.length &&
            !memcmp(name, current_type->ident.node.name, len)) {
        assert(current_type->ident.node.is_defined);
        return current_type;
    }

    t = (struct Type *)tree_insert_str(&types,
            name, len, NULL, sizeof(struct Type));
    if (!t->ident.node.is_new) {
        check_visibility(t);
        return t;
    }
    set_type_defaults(t);
    return t;
}

struct Type *reference_type(const char *name, size_t len)
{
    struct Type *t = map_named_type(name, len);
    if (t->ident.node.is_new && !t->ident.node.is_defined) {
        srcloc_init(&t->ident.srcloc); /* for "Undefined type" errors */
        assert(t->prev == NULL);
        assert(t->next == NULL);
        t->next = unbound_types_list;
        if (unbound_types_list) {
            unbound_types_list->prev = t;
        }
        unbound_types_list = t;
    }
    return t;
}

static void remove_type_from_unbound(struct Type *t)
{
    assert(t != NULL);
    if (t == unbound_types_list) {
        assert(t->prev == NULL);
        unbound_types_list = t->next;
    } else {
        assert(t->prev != NULL);
        t->prev->next = t->next;
    }
    if (t->next) {
        t->next->prev = t->prev;
    }
    t->next = NULL;
    t->prev = NULL;
}

void srcloc_init(struct SourceLocation *srcloc)
{
    assert(current_filename != NULL);
    srcloc->filename = current_filename;
    srcloc->line = current_line;
}

void type_start(const char *name, size_t len)
{
    struct Type *t;

    assert(current_type == NULL);
    t = map_named_type(name, len);
    if (t->ident.node.is_defined) {
        if (!interfaces_done || t->is_implemented) {
            error_len(t->module_id == current_module_id ?
                        "Duplicate type name" :
                        "The bootstrap compiler does not support types "
                        "with the same name in different modules",
                      name, len);
        }
    }
    srcloc_init(&t->ident.srcloc);
    t->is_implemented = !!interfaces_done;
    if (in_exported_interface) {
        t->is_export = true;
    }
    t->funcs_exported = t->funcs_list;
    t->ctors_exported = t->ctors_list;
    t->vars_exported = t->vars_list;
    t->funcs_list = NULL;
    t->ctors_list = NULL;
    t->vars_list = NULL;
    type_func_nextptr = &t->funcs_list;
    type_ctor_nextptr = &t->ctors_list;
    type_var_nextptr = &t->vars_list;
    if (!t->ident.node.is_defined) {
        if (!t->ident.node.is_new) {
            remove_type_from_unbound(t);
        }
        register_type(t);
        t->ident.node.is_defined = true;
    }
    current_type = t;
}

/** Assignment statement: `this.field = expr` */
struct FieldInit {
    struct Stmt stmt;   /* `=` */
    struct Expr obj;    /* `this` */
    struct Expr field;  /* `.field` */
};

static struct Stmt *add_field_init(struct Var *field,
                                   struct Expr *initexpr)
{
    struct FieldInit *fi;

    fi = malloc(sizeof(struct FieldInit));
    NO_NULL(fi);
    fi->stmt.next = NULL;
    fi->stmt.kind = S_ASSIGN;
    fi->stmt.line = 0;
    fi->stmt.has_break = false;
    fi->stmt.u.assign.first_dest.expr = &fi->field;
    fi->stmt.u.assign.first_dest.next = NULL;
    fi->stmt.u.assign.sourceexpr = initexpr;
    fi->obj.kind = E_THIS;
    fi->obj.id = 0;
    fi->obj.typeref = NULL; /* initialized in typechk.c */
    fi->obj.rpnnext = &fi->field;
    fi->field.kind = E_INSTVAR;
    fi->field.id = 1;
    fi->field.typeref = NULL;
    fi->field.u.ident.namelen = 0;
    fi->field.u.ident.u.var = field;
    fi->field.rpnnext = NULL;
    return &fi->stmt;
}

static struct Stmt *add_field_paraminit(struct Var *field,
                                        struct Var *param)
{
    struct Expr *e; /* the parameter, as an expression */

    e = malloc(sizeof(struct Expr));
    NO_NULL(e);
    e->kind = E_LOCALVAR;
    e->id = 2;
    e->typeref = NULL;
    e->u.ident.namelen = 0;
    e->u.ident.u.var = param;
    e->rpnnext = NULL;
    return add_field_init(field, e);
}

static void add_default_constructor(void)
{
    struct Var *field;
    struct Var **var_nextptr;
    struct Stmt **stmt_nextptr;
    int init_stmt_id = 0;
    size_t num_params = 0;

    func_start("new", 3, FK_CONSTRUCTOR);
    var_nextptr = &current_func->params;
    stmt_nextptr = &current_func->code;
    for (field = current_type->vars_list; field; field = field->next) {
        if (field->initval == NULL && !field->is_giveme &&
                current_type->svcspecs_list != NULL) {
            error_var("All fields must be explicitly initialised in "
                      "service-type implementation classes", field);
        }
        if (field->is_modifiable) {
            /* If the object contains any modifiable fields, then the
               default constructor should return a modifiable object
               (otherwise those fields would never be possible to modify) */
            current_func->is_constructed_modifiable = true;
        }
        if (field->initval == NULL && !field->is_giveme) {
            /* All unmodifiable and uninitialized fields become constructor
               parameters. But service-type implementations (like the
               CommandMain class). */
            struct Var *param;
            struct Stmt *stmt;

            if (num_params++ > FUNCPARAMS_MAX) {
                error_var("Too many fields for default constructor", field);
            }
            param = var_new(&current_funcparams,
                            field->ident.node.name, field->ident.node.length);
            param->typeref = field->typeref;
            param->ident.srcloc = field->ident.srcloc;
            *var_nextptr = param;
            var_nextptr = &param->next;
            param->is_funcparam = true;

            /* Add initialization in function body */
            stmt = add_field_paraminit(field, param);
            stmt->id = init_stmt_id++;
            *stmt_nextptr = stmt;
            stmt_nextptr = &stmt->next;
        }
    }
    current_func->num_params = num_params;
    func_end();
}

/** Returns true if the given type contains initial values.
    Does NOT look at both interface and implementation! */
static bool contains_initvals(const struct Var *fields_list)
{
    const struct Var *field;
    for (field = fields_list; field; field = field->next) {
        if (field->initval != NULL && !field->is_giveme) {
            return true;
        }
    }
    return false;
}

struct StmtAddState {
    struct Stmt **stmt_nextptr;
    int init_stmt_id;
};

static void add_field_inits(struct StmtAddState *state,
                            struct Var *fields_list)
{
    struct Stmt **nextptr = state->stmt_nextptr;
    int id = state->init_stmt_id;
    struct Var *field;

    for (field = fields_list; field; field = field->next) {
        if (field->initval != NULL && !field->is_giveme) {
            struct Stmt *stmt = add_field_init(field, field->initval);
            stmt->id = id++;
            *nextptr = stmt;
            nextptr = &stmt->next;
        }
    }
    state->stmt_nextptr = nextptr;
    state->init_stmt_id = id;
}

/**
 * Adds a function that initializes all fields with initial values.
 * A call to this function (if it is needed) gets emitted in each constructor.
 */
static void add_initvals_function(void)
{
    struct StmtAddState state;

    current_type->has_initvals =
            contains_initvals(current_type->vars_list) ||
            contains_initvals(current_type->vars_exported);
    if (!current_type->has_initvals) return;

    func_start("initvals__", 10, FK_FUNC);
    current_func->is_modifying = true;
    state.init_stmt_id = 0;
    state.stmt_nextptr = &current_func->code;
    add_field_inits(&state, current_type->vars_list);
    add_field_inits(&state, current_type->vars_exported);
    func_end();
}

void type_end(void)
{
    if (interfaces_done) {
        /* Don't add constructors in exported types, because:
            1. Sometimes it is desirable to have private constructors only.
            2. add_default_constructor() uses modifiable-ness of private fields
               to determine the modifiable-ness of the constructor return.
               But the constructor return is part of the public API, which
               must not change on internal changes.
           Also, don't add constructors for enums, because:
           1. Enums can only have compile-time constant objects,
              so there's no point in heap-allocating them
           2. Enum values are singletons, and trying to allocate them only
              once would lead to a lot of complexity. */
        if (!current_type->ctors && !current_type->is_enum) {
            add_default_constructor();
        }
        add_initvals_function();
    }
    current_type = NULL;
    type_func_nextptr = NULL;
    type_ctor_nextptr = NULL;
    type_var_nextptr = NULL;
}

static void set_func_defaults(struct Func *f)
{
    f->class_ = current_type;
    f->params = NULL;
    f->returns = NULL;
    f->vardecls = NULL;
    f->code = NULL;
    f->section_first = NULL;
    f->section_by_name = NULL;
    f->is_noreturn = false;
    f->is_modifying = false;
    f->is_constructed_modifiable = false;
    f->is_constructor = false;
    f->is_service_ctor = false;
    f->is_entry = false;
    f->is_external = false;
    f->is_export = false;
    f->is_implemented = false;
    f->num_params = 0;
    f->num_returns = 0;
    f->next = NULL;
    f->prev = NULL;
    f->sincever_next = NULL;
}

static void register_func(struct Func *f)
{
    assert(!f->is_constructor);
    assert(f->next == NULL);
    assert(f->prev == NULL);
    if (current_type) {
        *type_func_nextptr = f;
        type_func_nextptr = &f->next;
    } else {
        *func_nextptr = f;
        func_nextptr = &f->next;
    }
}

static void register_ctor(struct Func *f)
{
    assert(f->is_constructor);
    assert(f->next == NULL);
    assert(f->prev == NULL);
    *type_ctor_nextptr = f;
    type_ctor_nextptr = &f->next;
}

static struct Func *map_named_func(const char *name, size_t len,
                                   enum FuncKind kind)
{
    struct Func *f;
    struct TreeNode **root;

    if (kind == FK_CONSTRUCTOR) {
        assert(current_type != NULL);
        root = &current_type->ctors;
    } else {
        root = (current_type ?
            &current_type->funcs : &toplevel_funcs);
    }

    f = (struct Func *)tree_insert_str(root,
            name, len, NULL, sizeof(struct Func));
    if (!f->ident.node.is_new) {
        assert(kind != FK_ENTRY); /* not supported in bootstrap */
        if (f->is_entry) {
            error_len("Attempt to call an `entry` function", name, len);
        }
        return f;
    }
    set_func_defaults(f);
    if (kind == FK_CONSTRUCTOR) {
        f->is_constructor = true;
        f->is_modifying = true;
        if (current_type->svcspecs) {
            f->is_service_ctor = true;
        }
    } else {
        f->is_entry = (kind == FK_ENTRY);
    }
    return f;
}

struct Func *reference_func(const char *name, size_t len, enum FuncKind kind)
{
    struct Func *f = map_named_func(name, len, kind);
    if (f->ident.node.is_new && !f->ident.node.is_defined) {
        srcloc_init(&f->ident.srcloc); /* for "Undefined function" errors */
        assert(f->prev == NULL);
        assert(f->next == NULL);
        f->next = unbound_funcs_list;
        if (unbound_funcs_list) {
            unbound_funcs_list->prev = f;
        }
        unbound_funcs_list = f;
    }
    return f;
}

static void remove_func_from_unbound(struct Func *f)
{
    assert(f != NULL);
    if (f == unbound_funcs_list) {
        assert(f->prev == NULL);
        unbound_funcs_list = f->next;
    } else {
        assert(f->prev != NULL);
        f->prev->next = f->next;
    }
    if (f->next) {
        f->next->prev = f->prev;
    }
    f->next = NULL;
    f->prev = NULL;
}

void func_start(const char *name, size_t len, enum FuncKind kind)
{
    struct Func *f;

    assert(current_func == NULL);
    f = map_named_func(name, len, kind);
    if (f->ident.node.is_defined &&
            (!interfaces_done || f->is_implemented)) {
        error_len(kind != FK_CONSTRUCTOR ?
                "Duplicate function name" :
                "Duplicate constructor name",
              name, len);
    }
    srcloc_init(&f->ident.srcloc);
    f->is_external = !interfaces_done && !in_exported_interface;
    if (in_exported_interface) {
        f->is_export = true;
    }
    f->is_implemented = !!interfaces_done;
    if (!f->ident.node.is_defined) {
        if (!f->ident.node.is_new) {
            remove_func_from_unbound(f);
        }
        if (kind == FK_CONSTRUCTOR) {
            register_ctor(f);
        } else {
            register_func(f);
        }
        f->ident.node.is_defined = true;
    }
    current_func = f;
}

void func_end(void)
{
    current_func = NULL;
}

void toplevel_var_add(struct Var *var)
{
    var->next = NULL;
    if (current_type) {
        *type_var_nextptr = var;
        type_var_nextptr = &var->next;
    } else {
        /* TODO should constants in "utility files" be allowed? */
        /* *var_nextptr = var;
        var_nextptr = &var->next;*/
        assert(0);
    }
}

struct Var *lookup_instance_var(const char *name, size_t len)
{
    HashCode h;

    assert(current_type != NULL);
    assert(name != NULL);
    assert(len != 0);
    h = hash_str(name, len);
    return (struct Var *)tree_search(current_type->vars, h, len, name);
}

struct Var *var_new(struct TreeNode **root, const char *name, size_t namelen)
{
    struct Var *var;
    struct TreeNode *insresult;

    var = malloc(sizeof(struct Var));
    NO_NULL(var);
    var->is_modifiable = false;
    var->is_funcparam = false;
    var->is_giveme = false;
    var->declared_at_level = NOT_YET_DECLARED;
    var->assigned_at_level = NOT_YET_ASSIGNED;
    var->ifelse_assigned_level = NOT_IFELSE_ASSIGNED;
    var->typeref = NULL;
    var->next = NULL;
    var->initval = NULL;

    insresult = tree_insert_str(root, name, namelen, &var->ident.node,
                                sizeof(struct Var));
    if (!insresult->is_new) {
        error_len("Identifier of variable already in use", name, namelen);
    }
    assert(insresult == &var->ident.node);
    insresult->is_defined = true;
    return var;
}

struct EnumValue *enum_value_add(const char *name, size_t namelen)
{
    struct EnumValue *enu;
    struct TreeNode *insresult;

    assert(current_type != NULL);
    assert(current_type->is_enum);
    assert(name != NULL);
    assert(namelen != 0);

    enu = malloc(sizeof(struct EnumValue));
    NO_NULL(enu);
    enu->class_ = current_type;

    insresult = tree_insert_str(&current_type->enumvalues, name, namelen,
                                &enu->ident.node, sizeof(struct EnumValue));
    if (!insresult->is_new) {
        error_len("Identifier of enum value already in use", name, namelen);
    }
    assert(insresult == &enu->ident.node);
    insresult->is_defined = true;

    return enu;
}