path: root/src-cslul/tlverify.c

/*

  tlverify.c -- Verifies top-level symbols

  Copyright © 2021-2024 Samuel Lidén Borell <samuel@kodafritt.se>

  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:

  The above copyright notice and this permission notice shall be included in
  all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  THE SOFTWARE.

*/

#include "internal.h"
#include "ast.h"
#include <assert.h>
#define INTERR_TLVERIFY(errnum) MAKE_INTERR(errnum, INTERRBASE_TLVERIFY)

/* Values for "symtype" parameter of ensure_ident_impl() */
enum SymbolType {
    DATA,
    FUNC
};

/**
 * Checks that the implementation of a type matches the interface.
 * The following checks are made:
 *
 * 1. Private types must be defined in the implementation.
 * 2. Non-private types may not be defined in the implementation.
 * 3. Private types must be of struct type
 * 4. Versions, if present, must match.
 */
static int ensure_type_impl(struct CSlul *ctx,
                            struct TopLevelType *tiface,
                            int is_private)
{
    struct TopLevelType *timpl;
    /* Private types should be defined in the implementation.
       Otherwise, it should NOT be present there. */
    timpl = (struct TopLevelType *)tree_search_node(ctx, ctx->impl.types_root,
                                                    &tiface->decl.ident);
    if (timpl) {
        timpl->iface_decl = tiface;
    }
    if (timpl && IS_IDENT_IMPLEMENTED(&timpl->decl)) {
        if (is_private) {
            if (UNLIKELY(timpl->decl.type.type != T_STRUCT)) {
                message_set_ident(ctx, 0, CSLUL_LT_MAIN, &timpl->decl.ident);
                message_set_ident(ctx, 1, CSLUL_LT_DEFINITION,
                                  &tiface->decl.ident);
                message_final(ctx, CSLUL_E_PRIVATENONSTRUCT);
                return 0;
            }
        } else {
            message_set_ident(ctx, 0, CSLUL_LT_MAIN, &timpl->decl.ident);
            message_set_ident(ctx, 1, CSLUL_LT_DUPLICATE,
                              &tiface->decl.ident);
            message_final(ctx, CSLUL_E_IFACEIMPLDUPLICATE);
            return 0;
        }
    } else if (UNLIKELY(is_private)) {
        message_set_ident(ctx, 0, CSLUL_LT_DEFINITION, &tiface->decl.ident);
        message_final(ctx, CSLUL_E_MISSINGIMPLDEF);
        return 0;
    }
    return 1;
}

/**
 * Checks that the implementation of a data item or function matches the
 * interface. The following checks are made:
 *
 * 1. Functions without a body must be defined in the implementation.
 *    Functions with a body (inlineable) must be absent in the implementation.
 * 2. Data items without a value must be defined in the implementation.
 *    Data items with a value must be absent in the implementation.
 * 3. Symbols must be of the same kind (function or data).
 * 4. Versions, if present, must match.
 * 5. TODO: Check that function/data declarations match.
 */
static int ensure_ident_impl(struct CSlul *ctx,
                             struct TopLevelIdent *iiface,
                             enum SymbolType symtype,
                             int is_private)
{
    struct TopLevelIdent *iimpl;
    struct TreeNode *searchroot;
    if (iiface->class_) {
        /* Methods and typeidents */
        struct TreeNode *clident = &iiface->class_->ident;
        struct TopLevelType *climpl;
        climpl = (struct TopLevelType *)tree_search_node(ctx,
                                                     ctx->impl.types_root,
                                                     clident);
        if (UNLIKELY(!climpl)) {
            message_set_ident(ctx, 0, CSLUL_LT_MAIN, &iiface->decl.ident);
            message_set_ident(ctx, 1, CSLUL_LT_DEFINITION, clident);
            message_final(ctx, CSLUL_E_MISSINGIMPLCLASS);
            return 0;
        }
        searchroot = climpl->decl.typeidents;
    } else {
        /* Item in root namespace */
        searchroot = ctx->impl.idents_root;
    }
    iimpl = (struct TopLevelIdent *)tree_search_node(ctx, searchroot,
                                                     &iiface->decl.ident);
    if (iimpl) {
        iimpl->iface_decl = iiface;
    }
    if (iimpl && IS_IDENT_IMPLEMENTED(&iimpl->decl)) {
        enum CSlulErrorCode errcode;
        enum CSlulLocationType second_loc;
        if ((symtype == FUNC && !IS_FUNC_DECL(&iimpl->decl)) ||
            (symtype == DATA && IS_FUNC_DECL(&iimpl->decl))) {
            errcode = CSLUL_E_IFACEIMPLDUPLICATE;
            second_loc = CSLUL_LT_DUPLICATE;
        } else if (!is_private) {
            errcode = symtype == FUNC ?
                CSLUL_E_INLINEPLUSIMPL : CSLUL_E_CONSTANTWITHDATA;
            second_loc = CSLUL_LT_DUPLICATE;
        } else {
            /* TODO Check that function/data declarations match */
            return 1;
        }
        message_set_ident(ctx, 0, CSLUL_LT_MAIN, &iimpl->decl.ident);
        message_set_ident(ctx, 1, second_loc, &iiface->decl.ident);
        message_final(ctx, errcode);
        return 0;
    } else if (UNLIKELY(is_private)) {
        message_set_ident(ctx, 0, CSLUL_LT_DEFINITION, &iiface->decl.ident);
        message_final(ctx, CSLUL_E_MISSINGIMPLDEF);
        return 0;
    }
    return 1;
}

/**
 * Verifies a top-level type symbol.
 */
static int verify_tltype(struct CSlul *ctx, struct TypeDecl *decl)
{
    int ok = 1;
    if (!IS_IDENT_IMPLEMENTED(decl)) return 1;

    if (UNLIKELY(decl->ident.state == TNS_PROCESSING)) {
        message_set_ident(ctx, 0, CSLUL_LT_MAIN, &decl->ident);
        message_final(ctx, CSLUL_E_CYCLICDECL);
        return 0;
    }
    if (decl->ident.state != TNS_DONE) {
        decl->ident.state = TNS_PROCESSING;
        ctx->in_typedef_check = 1;
        ok &= check_type(ctx, decl, decl, &decl->type, LTTypedef);
        ctx->in_typedef_check = 0;
        decl->ident.state = TNS_DONE;
    }
    return ok;
}

int verify_tlident(struct CSlul *ctx, struct IdentDecl *decl)
{
    int ok = 1;
    if (!IS_IDENT_IMPLEMENTED(decl)) return 1;

    if (UNLIKELY(decl->ident.state == TNS_PROCESSING)) {
        message_set_ident(ctx, 0, CSLUL_LT_MAIN, &decl->ident);
        message_final(ctx, CSLUL_E_CYCLICDECL);
        return 0;
    }
    if (decl->ident.state != TNS_DONE) {
        int is_func = IS_FUNC_DECL(decl);
        decl->ident.state = TNS_PROCESSING;
        /* FIXME can these nasty casts be avoided? */
        ok &= check_type(ctx, (struct TypeDecl *)decl,
                   (struct TypeDecl *)decl, &decl->type,
                   is_func ? LTToplevelFunc : LTToplevelData);
        if (!is_func && decl->u.initval != NULL) { /* data def. */
            struct TypeRef expr_tr = root_tr(&decl->type);
            ok &= check_expr(ctx, &expr_tr, decl->u.initval,
                             LEDataInitval);
        }
        decl->ident.state = TNS_DONE;
    }
    /* TODO process typescopes */
    return ok;
}

static int verify_iface_typedecl(struct CSlul *ctx,
                                 struct TopLevelType *tltype)
{
    int ok = 1;
    ok &= verify_tltype(ctx, &tltype->decl);
    if (IS_IDENT_IMPLEMENTED(&tltype->decl)) {
        ok &= ensure_type_impl(ctx, tltype,
                               tltype->decl.type.type==T_PRIVATE);
    }
    return ok;
}

static int verify_iface_identdecl(struct CSlul *ctx,
                                  struct TopLevelIdent *tlident)
{
    int ok = 1;

    ok &= verify_tlident(ctx, &tlident->decl);
    if (IS_IDENT_IMPLEMENTED(&tlident->decl)) {
        enum SymbolType symtype;
        int is_private;
        if (IS_FUNC_DECL(&tlident->decl)) {
            symtype = FUNC;
            is_private = !tlident->decl.u.funcbody;
        } else {
            symtype = DATA;
            is_private = !tlident->decl.u.initval;
        }
        ok &= ensure_ident_impl(ctx, tlident, symtype, is_private);
    }
    return ok;
}

static int verify_iface_decls(struct CSlul *ctx, struct Module *mod,
                              int is_main_module)
{
    int ok = 1;
    struct TopLevelType *tltype;
    struct TopLevelIdent *tlident;
    /* Interface definitions - Types */
    for (tltype = mod->iface.types_list;
                tltype; tltype = tltype->next) {
        ok &= is_main_module ?
                verify_iface_typedecl(ctx, tltype) :
                verify_tltype(ctx, &tltype->decl);
    }
    /* Interface definitions - Functions and data */
    for (tlident = mod->iface.idents_list;
                tlident; tlident = tlident->next) {
        if (UNLIKELY(tlident->decl.type.type == T_INVALID)) {
            assert(ctx->has_errors);
            continue;
        }
        /* Functions without a body and data without a value are expected
           to have a full definition in the implementation */
        ok &= is_main_module ?
                verify_iface_identdecl(ctx, tlident) :
                verify_tlident(ctx, &tlident->decl);
    }
    return ok;
}

/** Verifies function/data declarations in the interfaces
    (also in other modules) */
int tlverify_iface_decls(struct CSlul *ctx)
{
    int ok = 1;
    struct CSlulDependency *dep;
    ok &= verify_iface_decls(ctx, &ctx->module, 1);
    for (dep = ctx->module.first_dep; dep; dep = dep->next) {
        ok &= verify_iface_decls(ctx, dep->module, 0);
    }
    return ok;
}

/** Verifies function/data declarations in the implementation sources */
int tlverify_impl_decls(struct CSlul *ctx)
{
    int ok = 1;
    struct TopLevelType *tltype;
    struct TopLevelIdent *tlident;

    for (tltype = ctx->impl.types_list; tltype; tltype = tltype->next) {
        ok &= verify_tltype(ctx, &tltype->decl);
    }
    for (tlident = ctx->impl.idents_list; tlident; tlident = tlident->next) {
        ok &= verify_tlident(ctx, &tlident->decl);
    }
    return ok;
}

/**
 * Verifies all function bodies (in both implementation files and in
 * interfaces)
 */
int tlverify_funcs(struct CSlul *ctx)
{
    int ok = 1;
    struct FuncBody *func = ctx->funcbody;
    for (; func; func = func->next) {
        assert(func->ident->ident.state == TNS_DONE);
        ok &= check_funcbody(ctx, func);
    }
    return ok;
}

enum RefKind {
    RK_TYPE,
    RK_IDENT
};

/**
 * Searches for a definition of an identifier in a module.
 *
 * \param ctx  Compilation context
 * \param mod  Module where reference is found
 * \param tltype  Top level type OR top level identifier
 * \param name  Name of top level type/identifier
 * \param refkind  Selects whether to process a type or identifier
 */
static struct TopLevelType *find_decl_in_module_of(
                                        struct CSlul *ctx,
                                        const struct Module *mod,
                                        const struct TopLevelType *tltype,
                                        const char *name,
                                        enum RefKind refkind)
{
    struct TreeNode *search_root;
    struct TopLevelType *match;

    search_root = (refkind == RK_TYPE ?
            mod->iface.types_root :
            mod->iface.idents_root);
    /* FIXME require that symbols in interfaces follow code conventions:
            Underscores (or digits) are not allowed as the first character. */
    match = (struct TopLevelType *)tree_search(ctx, search_root,
                        tltype->decl.ident.hashcode,
                        tltype->decl.ident.length, name);
    if (!match || !IS_IDENT_IMPLEMENTED(&match->decl)) return NULL;
    return match;
}

/**
 * Binds a symbol reference to a definition.
 */
static void found_import(struct CSlul *ctx,
                         struct TopLevelType *tlref,
                         struct TopLevelType *match)
{
    PROTECT_STRUCT(tlref->decl.type);
    (void)ctx; /* prevent warning if struct-type protection is disabled */
    tlref->decl.type.defflags = D_DEFINED | (match->decl.type.defflags & D_FUNC);
    tlref->decl.type.type = T_IMPORTED;
    tlref->decl.type.misc = 0;
    tlref->decl.type.quals = 0;
    tlref->decl.type.u.ident = &match->decl;
    tlref->id = match->id;
}

/**
 * Binds a type/identifier reference to an external module.
 *
 * \param ctx  Compilation context
 * \param mod  Module where reference is found
 * \param tltype  Top level type OR top level identifier
 * \param refkind  Selects whether to process a type or identifier
 */
static int bind_ref(struct CSlul *ctx, struct Module *mod,
                    struct TopLevelType *tltype,
                    enum RefKind refkind, int in_impl)
{
    struct CSlulDependency *dep;
    const char *name;
    const struct Module *def_module = NULL;
    struct ClosestSincever closest = { NULL,NULL,NULL,NULL }; /* for errors */
    int ok = 1;
    int ignore_impl_depends = !is_app(mod) && !in_impl;
    int in_library_impl = !is_app(mod) && in_impl;

    CHECK_STRUCT(*tltype);
    CHECK_STRUCT(tltype->decl);
    if (IS_IDENT_DEFINED(&tltype->decl)) return 1; /* TODO disallow identifier hiding */
    name = node_nameptr(&tltype->decl.ident);

    /* Check if the identifier is defined in the module's own interface */
    if (in_library_impl) {
        struct TopLevelType *match =
                find_decl_in_module_of(ctx, mod, tltype, name, refkind);
        if (match) {
            def_module = mod;
            found_import(ctx, tltype, match);
        }
    }
    /* Check if the identifier is defined in a dependency */
    for (dep = mod->first_dep; dep; dep = dep->next) {
        struct TopLevelType *match;
        const struct Module *depmod;
        if (!dep->first_ifacever && ignore_impl_depends) continue;
        if ((dep->flags & CSLUL_DF_NESTEDONLY) != 0 || (!in_impl &&
                (dep->iface_flags & CSLUL_DF_NESTEDONLY) != 0)) {
            continue;
        }

        depmod = dep->module;
        if (UNLIKELY(!depmod)) {
            assert(ctx->has_errors);
            continue;
        }
        match = find_decl_in_module_of(ctx, depmod, tltype, name, refkind);
        if (!match) continue;

        if (!check_decl_sinceversion(dep, depmod, match->sinceversions,
                                     &closest)) continue;
        /* Identifier exists */
        if (UNLIKELY(def_module)) {
            message_set_ident(ctx, 0, CSLUL_LT_MAIN, &tltype->decl.ident);
            message_set_module(ctx, 1, CSLUL_LT_DEFINED_IN, depmod);
            message_set_module(ctx, 2, CSLUL_LT_DEFINED_IN, def_module);
            message_final(ctx, CSLUL_E_AMBIGUOUSIDENT);
            ok = 0;
        }
        def_module = depmod;
        found_import(ctx, tltype, match);
    }
    if (UNLIKELY(!def_module)) {
        enum CSlulErrorCode e;
        int is_ty = (refkind == RK_TYPE);
        message_set_ident(ctx, 0, CSLUL_LT_MAIN, &tltype->decl.ident);
        if (closest.too_old_dep) {
            message_set_module(ctx, 1, CSLUL_LT_DEPENDENCY,
                               closest.too_old_module);
            message_set_textlen(ctx, 2, CSLUL_LT_DEPENDENCY,
                    closest.too_old_dep->min_version, /*requested version*/
                    closest.too_old_dep->minverlen);
            if (closest.best_sincever) {
                e = is_ty ? CSLUL_E_TLTYPETOONEW : CSLUL_E_TLIDENTTOONEW;
            } else {
                e = is_ty ? CSLUL_E_TLTYPELATERLOWER:CSLUL_E_TLIDENTLATERLOWER;
                closest.best_sincever = closest.first_sincever;
                assert(closest.first_sincever);
            }
            message_set_ident(ctx, 3, CSLUL_LT_MINIMUM,
                      &closest.best_sincever->verstr); /*required version*/
        } else { /* Not found at all */
            e = is_ty ? CSLUL_E_TLTYPENOTDEF : CSLUL_E_TLIDENTNOTDEF;
        }
        message_final(ctx, e);
        tltype->decl.ident.state = TNS_DONE;
        ok = 0;
    }
    return ok;
}

/**
 * Binds all toplevel identifier references (to types, functions and data
 * items) in the TopLevels structure, to the ones that are available in
 * the given module.
 *
 * \param ctx Compilation context
 * \param mod Module that contains the toplevels
 * \param tl TopLevels structure
 */
static int bind_toplevel_refs(struct CSlul *ctx, struct Module *mod, struct TopLevels *tl,
                              int in_impl)
{
    struct TreeIter identiter;
    struct TreeNode *ident;
    int ok = 1;
    /* Process all type refs */
    tree_iter_init(&identiter, tl->types_root);
    while (tree_iter_next(&identiter, &ident)) {
        ok &= bind_ref(ctx, mod, (struct TopLevelType *)ident,
                       RK_TYPE, in_impl);
    }
    /* Process all ident refs */
    /* XXX should interfaces be able to reference functions in other modules?
           (e.g. in inline functions)
       XXX also, should it be allowed to reference data in other modules?
           (e.g. compile-time constants)
       Without these, then "typesonly" would be what interfaces can depend on. */
    tree_iter_init(&identiter, tl->idents_root);
    while (tree_iter_next(&identiter, &ident)) {
        /* This is actually a TopLevelIdent */
        ok &= bind_ref(ctx, mod, (struct TopLevelType *)ident,
                       RK_IDENT, in_impl);
    }
    return ok;
}

/**
 * Binds any referenced but undefined identifiers, to the correct definitions
 * in the corresponding dependencies.
 *
 * Processes both interface, implementation and interfaces of dependencies.
 */
int tlverify_bind_iface_refs(struct CSlul *ctx)
{
    struct CSlulDepIter depiter;
    int ok = 1;
    depiter.module_name = NULL;
    while (cslul_ll_dependency_iter(ctx, &depiter)) {
        /* Note: Each dependency should only bind idents from it's iface-dependencies */
        ok &= bind_toplevel_refs(ctx, depiter.internal->module,
                            &depiter.internal->module->iface, 0);
    }
    ok &= bind_toplevel_refs(ctx, &ctx->module, &ctx->module.iface, 0);
    ok &= bind_toplevel_refs(ctx, &ctx->module, &ctx->impl, 1);
    return ok;
}

/**
 * Checks requirements that are specific to modules of application type.
 */
int tlverify_check_modspecific(struct CSlul *ctx)
{
    int ok = 1;
    if (UNLIKELY(!ctx->has_app_main && is_app(&ctx->module))) {
        message_set_module(ctx, 0, CSLUL_LT_MAIN, &ctx->module);
        message_final(ctx, CSLUL_E_APPWITHOUTMAIN);
        ok = 0;
    }
    return ok;
}