path: root/src-cslul/typecompat.c

/*

  typecompat.c -- Type compatibility checker

  Copyright © 2022-2023 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>
#include <string.h>
#define INTERR_TYPECOMPAT(errnum) MAKE_INTERR(errnum, INTERRBASE_TYPECOMPAT)
#define INTERR_BADTYPE          INTERR_TYPECOMPAT(0x01)
#define INTERR_ENUMREALTYPE     INTERR_TYPECOMPAT(0x02)
#define INTERR_IDENTREALTYPE    INTERR_TYPECOMPAT(0x03)
#define INTERR_METHODREALTYPE   INTERR_TYPECOMPAT(0x04)


#define RESTRICTING_QUALS (Q_WRONLY|Q_ALIASED|Q_THREADED)
#define ENTITLING_QUALS (Q_VAR)
static int compatible_quals(unsigned target_quals, unsigned source_quals)
{
    unsigned required_quals, allowed_quals;
    /* For example: "ref T a = ref_var_b" is allowed, but not vice versa */
    allowed_quals = (target_quals & ENTITLING_QUALS);
    if ((source_quals & target_quals & ENTITLING_QUALS) != allowed_quals)
        return 0;
    /* For example: "aliased T a = ref_b" is allowed, but not vice versa */
    required_quals = (source_quals & RESTRICTING_QUALS);
    if ((source_quals & target_quals & RESTRICTING_QUALS) != required_quals)
        return 0;
    return 1;
}

void get_array_info(const struct Type *arrtype,
                    struct ArrTypeInfo *out, enum ArrInfoState *state)
{
    /* TODO should the length expr itself and/or elemtype itself be checked here? */
    out->constant_len = 0;
    out->is_variable = 0;
    if (IS_SHORT_ARRAYLEN(arrtype)) {
        out->elemtype = arrtype->u.nested;
        out->constant_len = arrtype->misc;
        out->len_expr = NULL;
    } else if (arrtype->misc == M_ANY_LENGTH) {
        out->elemtype = arrtype->u.nested;
        *state = IGNORE_LENGTH;
    } else {
        struct ExprRoot *lenexpr;
        out->elemtype = &arrtype->u.arr->elemtype;
        out->len_expr = lenexpr = arrtype->u.arr->lengthexpr;
        if (UNLIKELY(!lenexpr || !lenexpr->root)) {
            *state = IGNORE_LENGTH;
        } else if (lenexpr->root->exprtype == E_INTEGER) {
            out->constant_len = lenexpr->root->a.intval;
        } else {
            out->is_variable = 1;
        }
    }
}

#define IS_STRICT(mode) \
    ((mode) == TC_EXACT || (mode) == TC_PTREXACT || (mode) == TC_PTRTARGET)

/**
 * Checks whether two types are compatible. The check depends on the mode,
 * see the TC_* constants.
 *
 * \param ctx         Compilation context
 * \param target_tr   Target type
 * \param subexpr_tr  Source/subexpression type
 * \param sourceexpr  Source expression. Will be used in error messages.
 * \param varstate    Source expression none-ness/range.
 * \param mode        TC_* constants
 * \return  1 if types are compatible, or 0 (and reports error) if not.
 */
int require_type_compat(struct CSlul *ctx,
                        const struct TypeRef *target_tr,
                        const struct TypeRef *subexpr_tr,
                        const struct ExprNode *sourceexpr,
                        const struct VarStateEntry *varstate,
                        enum TypeCompatCheck mode)
{
    const struct Type *target;
    const struct Type *subexpr;
    enum CSlulErrorCode errcode;
    struct TypeRef alloc1, alloc2;

/*  deeper:*/
    target = target_tr->type;
    subexpr = subexpr_tr->type;
  retry:
    if (UNLIKELY(!target || target->type == T_INVALID)) goto earlier_error;
    if (UNLIKELY(!subexpr || subexpr->type == T_INVALID)) goto earlier_error;
    if (target == subexpr && target_tr->prm == subexpr_tr->prm &&
        target_tr->quals == subexpr_tr->quals) return 1;

    if (substitute_type_params_tr(&subexpr_tr, &subexpr, &alloc1) | /* run both */
        substitute_type_params_tr(&target_tr, &target, &alloc2)) {
        /* Retry with modified args */
        goto retry;
    }

    /* Resolve imports */
    if (subexpr->type == T_IMPORTED) {
        struct TypeDecl *decl = subexpr_tr->type->u.ident;
        if (UNLIKELY(!decl)) goto earlier_error;
        subexpr = &decl->type;
        ctx->current_sourcetype_ident = &decl->ident;
        goto retry;
    }
    if (target->type == T_IMPORTED) {
        struct TypeDecl *decl = target_tr->type->u.ident;
        if (UNLIKELY(!decl)) goto earlier_error;
        target = &decl->type;
        ctx->current_targettype_ident = &decl->ident;
        goto retry;
    }

    if (mode == TC_EXACT || mode == TC_PTREXACT) {
        if (UNLIKELY(target->quals != subexpr->quals)) {
            errcode = CSLUL_E_QUALSNOTEQUAL;
            goto mismatch;
        }
    } else if (mode == TC_PTRTARGET) {
        if (UNLIKELY(!compatible_quals(target->quals, subexpr->quals))) {
            errcode = CSLUL_E_QUALSNOTCOMPATIBLE;
            goto mismatch;
        }
    }

    if (UNLIKELY(IS_STRICT(mode) && target->type != subexpr->type))
        goto incompatible;

    if (target->type == T_IDENT && subexpr->type == T_IDENT) {
        /* Named types are compared by place of definition
           (i.e. name compatibility) */
        struct TypeDecl *a = get_identtype_decl(target);
        struct TypeDecl *b = get_identtype_decl(subexpr);
        if (LIKELY(a == b)) return 1;
        else {
            errcode = CSLUL_E_NAMEDTYPESMUSTBESAME;
            goto mismatch;
        }
    }

    /* Else, check structural compatiblity */

    /* Dereference the identifier type */
    if (!IS_STRICT(mode)) {
        int modified = 0;
        if (target->type == T_IDENT) {
            struct TypeDecl *decl = get_identtype_decl(target);
            if (UNLIKELY(!decl)) goto earlier_error;
            ctx->current_targettype_ident = &decl->ident;
            target = &decl->type;
            modified = 1;
        }
        if (subexpr->type == T_IDENT) {
            struct TypeDecl *decl = get_identtype_decl(subexpr);
            if (UNLIKELY(!decl)) goto earlier_error;
            ctx->current_sourcetype_ident = &decl->ident;
            subexpr = &decl->type;
            modified = 1;
        }
        if (modified) goto retry;
    }

    /* Check equality of type parameters. This is only done if the base types
       are actually compatible (i.e. the same identifier, since the base type
       must be an identifier) */
    /* TODO */

    /* Bind type params in e.g. Map<int,int> */
    /* TODO */

    /* References can be assigned to optional types */
    /* TODO */

    /* Comparisons are symmetric, so any operation that is allowed from->to
       is also allowed to->from. */
    if (mode == TC_COMPARABLE) {
        /* TODO */
    }

    /* Comparisons can be done between any numeric types */
    {
        const struct Type *compared_side = NULL;
        if (subexpr->type == T_INTERNAL &&
                subexpr->u.internal == IT_UnsizedInt) {
            compared_side = target;
        }
        if (target->type == T_INTERNAL &&
                target->u.internal == IT_UnsizedInt) {
            compared_side = subexpr;
        }
        if (compared_side && compared_side->type == T_ELMNTRY &&
                BT_IS_NUMERIC(compared_side->u.builtin)) return 1;
    }

    /* Typeidentifiers always have the type of the target type.
       But enum definitions get evaluated to their integer type,
       which would not be considered compatible with the enum type.
       So for enum types, we need to return early. */
    if (mode == TC_ASSIGNABLE_TYPEIDENT) return 1;

    if (UNLIKELY(subexpr->type != target->type))
        goto incompatible;

    /* Many (if not most?) of these should require nominal compatbility?
        - but how about e.g. functions (taking reference of one)
          or literals?
        - should it be required to declare that a function is of a
          particular type?
            funcreftarget SomeFuncType somefunc
            func somefunc(int x, int y) -> int
      */
    switch (target->type) {
    case T_REF:
        if (IS_STRICT(mode)) {
            if (!IS_REF_ANYREF(*target) &&
                UNLIKELY(target->misc != subexpr->misc)) goto incompatible;
        } else {
            if (IS_REF_OPTIONAL(*subexpr) && !IS_REF_OPTIONAL(*target)) {
                /* If it's a variable, it might be known to be not 'none' */
                if (UNLIKELY(!varstate)) {
                    goto incompatible;
                } else if (UNLIKELY(!varstate->not_none)) {
                    errcode = CSLUL_E_VARMAYBENONE;
                    goto mismatch;
                }
            }
            if (!IS_REF_ANYREF(*target) && !IS_REF_NORMAL(*target) &&
                    REF_KIND(*target) != REF_KIND(*subexpr)) {
                goto incompatible; /* e.g. "arena a = normal_ref" */
            }
        }
        /* TODO check lifetime */
        if (!IS_REF_ANYREF(*target) &&
                mode != TC_EXACT && mode != TC_PTREXACT) {
            mode = (mode != TC_PTRTARGET ? TC_PTRTARGET : TC_PTREXACT);
        }
        target = target->u.nested;
        subexpr = subexpr->u.nested;
        goto retry;
    case T_SLOT:
        if (UNLIKELY(target->u.ident != subexpr->u.ident)) {
            goto incompatible;
        }
        break;
    case T_ARRAY: {
        struct ArrTypeInfo t, s;
        enum ArrInfoState state = NORMAL_ARRAYS;
        get_array_info(target, &t, &state);
        get_array_info(subexpr, &s, &state);
        if (!state) {
            if (UNLIKELY(t.is_variable != s.is_variable)) {
                errcode = CSLUL_E_ARRAYVARIABLENESSDIFFER;
                goto mismatch;
            }
            if (!t.is_variable) {
                if (UNLIKELY(t.constant_len != s.constant_len)) {
                    errcode = CSLUL_E_ARRAYLENGTHDIFFER;
                    goto mismatch;
                }
            } else {
                /* TODO */
                /*if (UNLIKELY(!compare_exprs(t.len_expr, s.len_expr))) {
                    errcode = CSLUL_E_ARRAYLENGTHDIFFER;
                    goto mismatch;
                }*/
            }
        } else if (UNLIKELY(state == UNKNOWN_LENGTH)) {
            errcode = CSLUL_E_ARRAYLENGTUNKNOWN;
            goto mismatch;
        }
        /* Now compare the element type. Conversions such as [3]byte to [3]int
           are forbidden, BUT the target type might be an inferred type from
           an array index operation. In that case, only the element is
           actually being converted. */
        if ((target->defflags & D_DEFINED) != 0) {
            mode = TC_EXACT;
        }
        target = t.elemtype;
        subexpr = s.elemtype;
        goto retry; }
    case T_STRUCT: {
        struct FieldOrParamEntry *tf, *sf;
        if (UNLIKELY(!target->u.fields)) goto earlier_error;
        if (UNLIKELY(!subexpr->u.fields)) goto earlier_error;
        if (UNLIKELY((target->misc & M_KNOWN_SIZE) == 0)) {
            errcode = (subexpr->misc & M_KNOWN_SIZE) == 0 ?
                 CSLUL_E_STRUCTSOPEN : CSLUL_E_STRUCTTARGETOPEN;
            goto mismatch;
        }
        if (UNLIKELY((subexpr->misc & M_KNOWN_SIZE) == 0)) {
            errcode = CSLUL_E_STRUCTSOURCEOPEN;
            goto mismatch;
        }
        if (UNLIKELY(target->u.fields->count != subexpr->u.fields->count)) {
            errcode = CSLUL_E_STRUCTSCOUNTDIFFER;
            goto mismatch;
        }
        if (UNLIKELY((target->quals & Q_CLOSED) == 0)) {
            errcode = CSLUL_E_TARGETTYPENOTCLOSED;
            goto mismatch;
        }
        if (UNLIKELY((subexpr->quals & Q_CLOSED) == 0)) {
            errcode = CSLUL_E_SUBEXPRTYPENOTCLOSED;
            goto mismatch;
        }
        tf = target->u.fields->first;
        sf = subexpr->u.fields->first;
        while (tf && sf) {
            const struct TypeRef
                ttr = nested_tr_const(&tf->f.vardef.decl.type, target_tr),
                str = nested_tr_const(&sf->f.vardef.decl.type, subexpr_tr);
            if (!require_type_compat(ctx, &ttr, &str,
                                     sourceexpr, NULL, TC_EXACT))
                return 0;
            tf = tf->next;
            sf = sf->next;
        }
        if (tf || sf) goto earlier_error;
        break; }
    case T_ENUM: /* Can only appear in typedefs (named types) */
        internal_error(ctx, INTERR_ENUMREALTYPE);
        break;
    case T_IDENT: /* Not a "real type" */
        internal_error(ctx, INTERR_IDENTREALTYPE);
        break;
    case T_ELMNTRY: {
        enum BuiltinType tb = target->u.builtin;
        enum BuiltinType sb = subexpr->u.builtin;
        if (UNLIKELY(IS_STRICT(mode) && tb != sb))
            goto incompatible;
        if (tb == BT_Bool || tb == BT_String ||
            sb == BT_Bool || sb == BT_String) {
            if (UNLIKELY(tb != sb))
                goto incompatible;
            break;
        } else { /* Numeric type */
            const struct BuiltinInfo *ti, *si;
            /* TODO range constraints. perhaps a new T_CONSTRAINED type? */
            if (tb == sb)
                break;
            ti = &builtin_infos[tb];
            si = &builtin_infos[sb];
            assert(ti->type != BI_OTHER && si->type != BI_OTHER);
            if (ti->type == BI_FLOAT) {
                /* Always possible (but might be lossy) */
            } else if (UNLIKELY(si->type == BI_FLOAT)) {
                errcode = CSLUL_E_FLOATTOINT;
                goto mismatch;
            } else if (UNLIKELY(!ti->negmin && si->negmin)) {
                errcode = CSLUL_E_SIGNEDTOUNSIGNED;
                goto mismatch;
            } else if (UNLIKELY(si->is_sysdependent)) {
                errcode = CSLUL_E_SYSDEPTOFIXED;
                goto mismatch;
            } else if (UNLIKELY(ti->negmin < si->negmin ||
                                ti->max < si->max)) {
                errcode = ti->is_sysdependent ?
                        CSLUL_E_FIXEDTOSYSDEP : CSLUL_E_NARROWERRANGE;
                goto mismatch;
            }
        }
        break; }
    case T_BITS:
        /* TODO */
        break;
    case T_FUNC:
        if (IS_FUNCREF_OPTIONAL(*subexpr) && !IS_FUNCREF_OPTIONAL(*target)) {
            /* If it's a variable, it might be known to be not 'none' */
            if (UNLIKELY(!varstate)) {
                goto incompatible;
            } else if (UNLIKELY(!varstate->not_none)) {
                errcode = CSLUL_E_VARMAYBENONE;
                goto mismatch;
            }
        }
        /* TODO */
        break;
    case T_METHOD:
        internal_error(ctx, INTERR_METHODREALTYPE);
        break;
    case T_GENERICSPEC: {
        struct TypeRef ttr, str;
        struct PrmEntry *tprm, *sprm;
        if (UNLIKELY(!target->u.gprm)) goto earlier_error;
        if (UNLIKELY(!subexpr->u.gprm)) goto earlier_error;
        if (UNLIKELY(!target->u.gprm->generictype)) goto earlier_error;
        if (UNLIKELY(!subexpr->u.gprm->generictype)) goto earlier_error;
        ttr = nested_tr_const(target->u.gprm->generictype, target_tr);
        str = nested_tr_const(subexpr->u.gprm->generictype, subexpr_tr);
        if (!require_type_compat(ctx, &ttr, &str, sourceexpr, NULL, mode))
            return 0;
        /* Number of type parameters */
        if (UNLIKELY(target->misc != subexpr->misc)) goto earlier_error;
        if (UNLIKELY(target->misc == 0)) goto earlier_error;
        tprm = &target->u.gprm->param;
        sprm = &subexpr->u.gprm->param;
        do {
            const struct TypeRef tprmtr =
                    nested_tr_const(&tprm->type, target_tr);
            const struct TypeRef sprmtr =
                    nested_tr_const(&sprm->type, subexpr_tr);
            if (!require_type_compat(ctx, &tprmtr, &sprmtr,
                                     sourceexpr, NULL, TC_EXACT)) {
                return 0;
            }
            tprm = tprm->next;
            sprm = sprm->next;
        } while (sprm && tprm);
        assert(!sprm && !tprm);
        break; }
    case T_LIFETIMED:
        /* TODO */
        break;
    case T_PRIVATE:
        errcode = CSLUL_E_ACCESSPRIVATETYPE;
        goto mismatch;
    case T_INTERNAL:
        if (UNLIKELY(target->u.internal != subexpr->u.internal))
            goto incompatible;
        break;
    case T_INVALID:
    case T_GENERICDEF: /* Always wrapped in a T_IDENT */
    case T_GENERICVAR:
    default:
        if (!ctx->has_errors) {
            internal_error(ctx, INTERR_BADTYPE);
        }
        return 0;
    }
    return 1;
  incompatible:
    if (mode == TC_PTREXACT) {
        errcode = CSLUL_E_REFREFTYPESNOTEQUAL;
    } else if (mode == TC_PTRTARGET) {
        errcode = CSLUL_E_REFTYPESNOTEQUAL;
    } else if (mode == TC_EXACT) {
        if (target->type == subexpr->type) {
            errcode = CSLUL_E_TYPESNOTEQUAL;
        } else {
            errcode = CSLUL_E_INCOMPATIBLENESTEDTYPES;
        }
    } else {
        errcode = CSLUL_E_INCOMPATIBLETYPES;
    }
  mismatch:
    {
        int loc_num = 1;
        message_set_expr(ctx, 0, CSLUL_LT_MAIN, ctx->current_exprroot, sourceexpr);
        if (ctx->current_sourcetype_ident) {
            message_set_type_ident(ctx, loc_num++, CSLUL_LT_TYPE_SOURCE,
                                   ctx->current_sourcetype_ident, subexpr);
        }
        if (ctx->current_targettype_ident) {
            message_set_type_ident(ctx, loc_num++, CSLUL_LT_TYPE_TARGET,
                                   ctx->current_targettype_ident, target);
        }
        message_final(ctx, errcode);
        return 0;
    }
  earlier_error:
    assert(ctx->has_errors);
    return 1;
}