/*

  verify.c -- Checks that the source is semantically valid.

  Copyright © 2012-2017 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 "verify.h"
#include "constexpr.h"
#include "interop.h"
#include "misc.h"
#include "display.h"
#include "context_private.h"

#include <string.h>

typedef enum {
    StatementLevel = 0x1, /* allows assignment operation */
    NestedAssign   = 0x2  /* inside a multiassignment */
} ExprFlags;

static void verify_deflist(LRLCtx *ctx, LRLASTDefList *list);
static void verify_def_type(LRLCtx *ctx, LRLASTDefType *def);
static void verify_def_data(LRLCtx *ctx, LRLASTDefData *def);
static void verify_def_function(LRLCtx *ctx, LRLASTDefFunction *def);
static void verify_expr(LRLCtx *ctx, LRLASTExpr *expr,
                        const LRLTypeRef *targettr, ExprFlags flags);
static void verify_type(LRLCtx *ctx, LRLASTType *type,
                        LRLASTType *usedby, LRLASTType *storedby);
static void verify_statement(LRLCtx *ctx, LRLASTStmt *stmt);
static LRLTypeRef determine_expr_type(LRLCtx *ctx, LRLASTExpr *expr,
                                      const LRLTypeRef *typescope,
                                      int show_error);
static int is_unsigned(const LRLTypeRef *typeref);
static LRLASTExpr *get_count_expr(size_t n);
static int exprs_equal(LRLCtx *ctx, LRLASTExpr *a, LRLASTExpr *b);
static void check_cyclic_ident_types(LRLCtx *ctx, const LRLASTType *type);

#define is_private_type lrl_vfy_is_private_type
#define is_optional_pointer(t) ((t)->ast_type == LRL_AST_Type_Optional && (t)->kind.optional.type && (t)->kind.optional.type->ast_type == LRL_AST_Type_Pointer)
#define is_flexi_pointer(t) ((t)->ast_type == LRL_AST_Type_Pointer && ((t)->kind.pointer.flags & LRL_PF_Flexible) != 0)
#define is_raw_pointer(t)   ((t)->ast_type == LRL_AST_Type_Pointer && ((t)->kind.pointer.flags & LRL_PF_Raw) != 0)
#define is_typedef(def)     ((def)->ast_type == LRL_AST_Def_Type || (def)->ast_type == LRL_AST_Stmt_DefType)

/**
 * Returns the defining node of an identifier,
 * de-referencing "uses" statements as needed.
 */
static LRLASTDefOrStmt *get_def_node(const LRLIdent *ident)
{
    LRLASTDefOrStmt *defref;
    
    if (!lrl_ident_valid(ident)) return NULL;
    
    defref = ident->def_node;
    if (!defref) return NULL;
    
    if (defref->ast_type == LRL_AST_Uses) {
        const LRLIdent *imported = defref->def.kind.uses.identref.ident;
        if (!imported) return NULL;
        defref = imported->def_node;
        if (defref && defref->ast_type == LRL_AST_Uses) {
            fail("vfygetdef_gotrecursiveuses");
        }
    }
    
    return defref;
}

static LRLTypeRef make_typeref(LRLTypeQualifiers quals, LRLBoundParams *prm,
                               const LRLASTType *type)
{
    LRLTypeRef typeref;
    typeref.quals = quals;
    typeref.prm = prm;
    typeref.type = type;
    return typeref;
}

static LRLTypeQualifiers override_quals(LRLTypeQualifiers old,
                                        LRLTypeQualifiers new)
{
    LRLTypeQualifiers ret = old | new;
    if (new & LRL_VarConst_Quals) {
        ret = (ret & ~LRL_VarConst_Quals) | (new & LRL_VarConst_Quals);
    }
    if (new & LRL_SharedMine_Quals) {
        ret = (ret & ~LRL_SharedMine_Quals) | (new & LRL_SharedMine_Quals);
    }
    return ret;
}

LRLTypeRef typeref_root(const LRLASTType *type,
                        LRLTypeQualifiers default_quals)
{
    LRLTypeRef typeref;
    typeref.quals = type ?
        override_quals(default_quals, type->quals) : default_quals;
    typeref.prm = NULL;
    typeref.type = type;
    return typeref;
}

LRLTypeRef typeref_nested(const LRLASTType *type,
                          const LRLTypeRef *subtyperef)
{
    LRLTypeRef typeref;
    if (!subtyperef->type) fail("vfytyperefnested_nosubtyperef");
    typeref.quals = override_quals(subtyperef->quals,
                                   type ? type->quals : 0);
    typeref.prm = subtyperef->prm;
    typeref.type = type;
    return typeref;
}

/**
 * Evaluates and replaces the given expression, or reports an
 * error if the expression is not compile-time constant.
 */
static void eval_constexpr(LRLCtx *ctx, LRLASTExpr **expr)
{
    LRLASTExpr *value = *expr;
    if (value) {
        int status = lrl_constexpr_expr_is_evaluatable(ctx, value);
        if (status == 1) {
            LRLASTExpr *evaluated = lrl_constexpr_eval(ctx, value);
            if (evaluated && evaluated != value) {
                /* Use a wrapper so we report errors on the correct line.
                   Evaluated values may not have source information, or may
                   come from a different line, which would lead to confusing
                   error messages. */
                LRLASTExpr *wrapper = malloc(sizeof(LRLASTExpr));
                wrapper->ast_type = LRL_AST_Expr_Evaluated;
                wrapper->from = value->from;
                wrapper->to = value->to;
                wrapper->typeref = value->typeref;
                wrapper->kind.evaluated.evaluated = evaluated;
                wrapper->kind.evaluated.original = value;
                verify_expr(ctx, wrapper, &value->typeref, 0);

                lrl_ctx_set_has_completed_constexpr(ctx);
                *expr = wrapper;
            }
        } else if (status == 0) {
            lrl_err_expr(ctx, LRL_Err_ConstantTooComplex, value);
        }
    }
}

/**
 * Verifies and evaluates an expression
 */
static void verifyeval_expr(LRLCtx *ctx, LRLASTExpr **expr,
                            const LRLTypeRef *targettr)
{
    verify_expr(ctx, *expr, targettr, 0);
    eval_constexpr(ctx, expr);
}

void lrl_vfy_namespace(LRLCtx *ctx, LRLASTNamespace *root)
{
    verify_deflist(ctx, root->list);
}

static void verify_deflist(LRLCtx *ctx, LRLASTDefList *list)
{
    for (; list; list = list->next) {
        switch (list->def.ast_type) {
            case LRL_AST_Def_Type:
                ctx->allow_local_type_params++;
                verify_def_type(ctx, &list->def.kind.type);
                ctx->allow_local_type_params--;
                break;
            case LRL_AST_Def_Data: {
                verify_def_data(ctx, &list->def.kind.data);
                eval_constexpr(ctx, &list->def.kind.data.value);
                break; }
            case LRL_AST_Def_Function:
                ctx->allow_local_type_params++;
                verify_def_function(ctx, &list->def.kind.function);
                ctx->allow_local_type_params--;
                break;
            case LRL_AST_Uses:
                /* is it needed? */
                /*lrl_vfy_uses(ctx, &list->def.kind.uses);*/
                break;
            case LRL_AST_Namespace:
                lrl_vfy_namespace(ctx, list->def.kind.namespac);
                break;
            case LRL_AST_Interop: {
                LRLASTInterop *interop = &list->def.kind.interop;
                if (interop->options_type) {
                    const LRLInteropImpl *impl = interop->impl;
                    LRLTypeRef options_typeref;
                    int status;
                    
                    options_typeref = typeref_root(interop->options_type, 0);
                    verify_expr(ctx, interop->options_expr,
                                &options_typeref, 0);
                    
                    /* Perform the translation */
                    interop->ident->flags &= ~LRL_IdFl_Uninitialized;
                    status = impl->translate(ctx, interop);
                    if (status != 0) {
                        interop->ident->flags |= LRL_IdFl_Uninitialized;
                        if (status == 1) {
                            /* an error should have been reported by the
                               interop, don't report any errors for this
                               identifier */
                            interop->ident->flags |= LRL_IdFl_Broken;
                        } else if (status == 2) {
                            /* options_expr wasn't ready yet */
                            break;
                        }
                    }
                    
                    /* Mark as done */
                    interop->options_type = NULL;
                    lrl_ctx_set_has_deferred(ctx);
                    ctx->has_parsed = 1; /* more identifiers available */
                }
                
                /* Verify the contents */
                verify_deflist(ctx, interop->translated);
                break; }
            LRL_case_except_ast_namespaces_defs default:
                fail("vfydeflist_switch"); /* shouldn't happen */
        }
    }
}

static void verify_def_type(LRLCtx *ctx, LRLASTDefType *def)
{
    /* Type */
    verify_type(ctx, def->type, NULL, NULL);
    check_cyclic_ident_types(ctx, def->type);
    
    /* TODO check typenames */
    
    if (def->type && (def->flags & LRL_DeFl_Internal_MaybeIncomplete) == 0) {
        /* Check that the "incomplete" keyword is used correctly */
        LRLTypeRef deftr = typeref_root(def->type, 0);
        if (is_private_type(ctx, &deftr) &&
            def->type->ast_type != LRL_AST_Type_Private) {
            /* It might not be obvious that the type is incomplete, so it
               should be marked with the "incomplete" keyword */
            if ((def->flags & LRL_DeFl_Incomplete) == 0) {
                lrl_err_type(ctx, LRL_Err_MissingIncompleteKeyword, def->type);
            }
        } else {
            /* Non-private and obviously private types (i.e. only "private")
               should not have the keyword. */
            if (def->flags & LRL_DeFl_Incomplete) {
                lrl_err_type(ctx, LRL_Err_UselessIncompleteKeyword, def->type);
            }
        }
    }
}

static void verify_def_data(LRLCtx *ctx, LRLASTDefData *def)
{
    /* Type */
    const LRLASTType *realtype;
    verify_type(ctx, def->type, NULL, NULL);
    
    realtype = lrl_vfy_find_real_type(def->type);
    if (realtype && realtype->ast_type == LRL_AST_Type_Function) {
        lrl_err_set_type(ctx, def->type, 0);
        if (realtype != def->type) {
            lrl_err_set_type(ctx, realtype, 1);
        }
        lrl_err_finish(ctx, LRL_Err_FunctionNotInPointer);
    }
    
    if (realtype && realtype->ast_type == LRL_AST_Type_Any) {
        lrl_err_set_type(ctx, def->type, 0);
        if (realtype != def->type) {
            lrl_err_set_type(ctx, realtype, 1);
        }
        lrl_err_finish(ctx, LRL_Err_AnyTypeNotInPointer);
    }
    
    if (realtype && realtype->ast_type == LRL_AST_Type_Array &&
        realtype->kind.array.length &&
        realtype->kind.array.length->ast_type == LRL_AST_Value_Undefined &&
        (def->flags & (LRL_DeFl_Import|LRL_DeFl_DeclOnly)) == 0) {
        lrl_err_set_type(ctx, def->type, 0);
        if (realtype != def->type) {
            lrl_err_set_type(ctx, realtype, 1);
        }
        lrl_err_finish(ctx, LRL_Err_UnknownLengthArrayNotInPointer);
    }
    
    /* Value */
    if ((def->flags & (LRL_DeFl_Import|LRL_DeFl_DeclOnly)) == 0) {
        LRLTypeRef typeref = typeref_root(def->type, LRL_Qual_Const);
        verify_expr(ctx, def->value, &typeref, 0);
    }
}

static void verify_def_function(LRLCtx *ctx, LRLASTDefFunction *def)
{
    /* Type */
    verify_type(ctx, &def->type, NULL, NULL);
    
    /* Typenames */
    /* TODO check typenames */
    
    /* Code */
    if (def->code) {
        verify_statement(ctx, def->code);
    }
}

/**
 * Adds 1 to an integer scalar value.
 */
static LRLToken *next_scalar(const LRLToken *term)
{
    char *num;
    LRLToken *result;
    
    /* Check if we get one extra digit due to rollover (e.g. 99 to 100) */
    size_t i, len = term->loc.length+1;
    for (i = term->loc.length; i-- > 0;) {
        if (term->loc.start[i] != '9') { len--; break; }
    }
    num = (char*)malloc(len+1) + len; /* cast is needed for arithmetic */
    *num = '\0';
    
    /* Add (run backwards) */
    for (i = term->loc.length; i-- > 0;) {
        if (term->loc.start[i] != '9') {
            *--num = term->loc.start[i] + 1;
            break;
        }
        *--num = '0';
    }
    
    if (i+1 == 0) {
        /* Rollover */
        *--num = '1';
    } else {
        /* Copy remaining numbers */
        num -= i;
        memcpy(num, term->loc.start, i);
    }
    
    result = malloc(sizeof(LRLToken));
    result->type = LRL_TT_Integer;
    result->loc.start = num;
    result->loc.length = len;
    return result;
}

static int is_integer_scalar(const LRLASTExpr *expr)
{
    return (expr->ast_type == LRL_AST_Value_Scalar &&
            expr->kind.scalar.token->type == LRL_TT_Integer);
}

/**
 * Returns the given expression + 1.
 *
 * "defdata" is used to initialize the from/to pointers to tokens in
 * the source.
 */
static LRLASTExpr *get_next_number_expr(const LRLASTExpr *last_expr,
                                        const LRLASTType *type,
                                        const LRLASTDefData *defdata)
{
    LRLASTExpr *expr = malloc(sizeof(LRLASTExpr));
    expr->ast_type = LRL_AST_Value_Scalar;
    expr->typeref.quals = LRL_Qual_Const|LRL_Qual_Mine;
    expr->typeref.prm = NULL;
    expr->typeref.type = type;
    expr->from = defdata->ident->def_token;
    expr->to = expr->from; /* TODO include whole enum item */
    expr->kind.scalar.is_negative = 0;
    
    if (!last_expr) {
        /* Start from zero */
        expr->kind.scalar.token = &lrl_builtin_token_zero;
        return expr;
    } else if (is_integer_scalar(last_expr)) {
        /* Increase scalar */
        expr->kind.scalar.token = next_scalar(last_expr->kind.scalar.token);
        return expr;
    } else {
        /* Non-scalar expression. We need to create an addition operation */
        LRLASTExpr *add = malloc(sizeof(LRLASTExpr));
        add->ast_type = LRL_AST_Expr_BinaryOp;
        add->typeref.quals = LRL_Qual_Const|LRL_Qual_Mine;
        add->typeref.prm = NULL;
        add->typeref.type = type;
        add->from = expr->from;
        add->to = expr->to;
        add->kind.binary_op.token_type = LRL_Op_Plus;
        
        if (last_expr->ast_type == LRL_AST_Expr_BinaryOp &&
            last_expr->kind.binary_op.token_type == LRL_Op_Plus &&
            is_integer_scalar(last_expr->kind.binary_op.operand2)) {
            /* Increase (... + scalar) */
            LRLToken *tok = next_scalar(
                    last_expr->kind.binary_op.operand2->kind.scalar.token);
            
            expr->kind.scalar.token = tok;
            add->kind.binary_op.operand1 = last_expr->kind.binary_op.operand1;
            add->kind.binary_op.operand2 = expr;
        } else {
            /* Increment last by one */
            expr->kind.scalar.token = &lrl_builtin_token_one;
            add->kind.binary_op.operand1 = (LRLASTExpr*)last_expr;
            add->kind.binary_op.operand2 = expr;
        }
        return add;
    }
}

/**
 * Verifies a type. The "usedby" and "storedby" are the types which the
 * type is referenced by and stored by, respecively. The "usedby" parameter
 * is used for checking correctness of the "var" qualifier and that type
 * parameters are only used on identifiers that reference parametric types.
 *
 * The "storedby" parameter is used for checking that storage is possible.
 * For instance, it is not possible to store private/incomplete data or
 * functions (only pointers to them can be stored).
 */
static void verify_type(LRLCtx *ctx, LRLASTType *type,
                        LRLASTType *usedby, LRLASTType *storedby)
{
    if (!type) return;
    if (type->quals & LRL_InternQual_Processing) return; /* avoid recursion */
    
    if ((type->quals & LRL_InternQual_ConstMemory) == 0)
        type->quals |= LRL_InternQual_Processing;
    
    switch (type->ast_type) {
        case LRL_AST_Type_Array: {
            LRLASTType *length_type = lrl_builtin_get_type(LRL_BT_count);
            
            /* Element type */
            verify_type(ctx, type->kind.array.type, type, type);
            
            /* Verify length */
            if (type->kind.array.length) {
                LRLASTExpr *lengthexpr = type->kind.array.length;
                LRLTypeRef typescopetr = typeref_root(type->kind.array.type,0);
                int status;
                LRLTypeRef lenref = determine_expr_type(ctx, lengthexpr,
                                                        &typescopetr, 0);
                if (!lenref.type) {
                    lenref.quals = LRL_Qual_Const|LRL_Qual_Mine;
                    lenref.prm = NULL;
                    lenref.type = length_type;
                } else {
                    LRLTypeRef countref;
                    countref.quals = LRL_Qual_Const|LRL_Qual_Mine;
                    countref.prm = NULL;
                    countref.type = length_type;
                    
                    lrl_vfy_type_compat(ctx, &countref, &lenref, lengthexpr, 0);
                }
                verify_expr(ctx, lengthexpr, &lenref, 0);
                
                status = lrl_constexpr_expr_is_evaluatable(ctx, lengthexpr);
                if (status == 1) {
                    /* Try to evaluate expression */
                    LRLASTExpr *constexpr = lrl_constexpr_eval(ctx, lengthexpr);
                    if (constexpr) {
                        lengthexpr = type->kind.array.length = constexpr;
                    }
                } else if (status == 0) {
                    /* Not a constant expression */
                    lrl_err_expr(ctx, LRL_Err_ArrayLengthTooComplex, lengthexpr);
                }
                
                if (storedby && lengthexpr->ast_type == LRL_AST_Value_Undefined) {
                    lrl_err_set_type(ctx, type, 0);
                    lrl_err_set_type(ctx, storedby, 1);
                    lrl_err_finish(ctx, LRL_Err_UnknownLengthArrayNotInPointer);
                }
            }
            
            break; }
        case LRL_AST_Type_Function:
            if (storedby) {
                lrl_err_set_type(ctx, storedby, 0);
                lrl_err_set_type(ctx, type, 1);
                lrl_err_finish(ctx, LRL_Err_FunctionNotInPointer);
            }
            
            verify_type(ctx, type->kind.function.args, NULL, type);
            verify_type(ctx, type->kind.function.ret, NULL, type);
            break;
        case LRL_AST_Type_Ident:
            if (!lrl_identref_queue(ctx, &type->kind.identref)) {
                LRLASTDefOrStmt *defref = get_def_node(type->kind.identref.ident);
                if (defref && is_typedef(defref)) {
                    
                    /* Check if it needs type parameters */
                    if (defref->def.kind.type.typenames) {
                        if (!usedby ||
                            usedby->ast_type != LRL_AST_Type_Parametric) {
                            lrl_err_type(ctx, LRL_Err_MissingTypeParameters, type);
                        }
                    }
                    
                    /* TODO Optimize this. Do we really need to verify
                       the referenced type each time? */
                    ctx->allow_local_type_params++;
                    verify_type(ctx, defref->def.kind.type.type,
                                type, storedby);
                    ctx->allow_local_type_params--;

                    if ((type->kind.identref.ident->flags & LRL_IdFl_TypedefParam) &&
                            !ctx->allow_local_type_params) {
                        lrl_err_set_ident(ctx, type->kind.identref.first_token, 0);
                        lrl_err_finish(ctx, LRL_Err_LocalTypeParamNotBoundHere);
                    }
                } else {
                    lrl_err_set_ident(ctx, type->kind.identref.first_token, 0);
                    lrl_err_finish(ctx, LRL_Err_IdentIsNotType);
                }
            }
            break;
        case LRL_AST_Type_Optional:
            verify_type(ctx, type->kind.optional.type, type, type);
            break;
        case LRL_AST_Type_Parametric: {
            LRLASTType *basetype = type->kind.parametric.type;
            const LRLASTTypeList *param;
            const LRLASTDefList *name;
            const LRLASTDefType *deftype;
            const LRLASTDefOrStmt *defnode;
            const LRLIdent *baseident;
            
            /* Base type */
            verify_type(ctx, basetype, type, storedby);
        
            if (basetype->ast_type != LRL_AST_Type_Ident) {
                lrl_err_type(ctx, LRL_Err_ParamsOnNonParamType, type);
                goto end;
            }
            
            baseident = basetype->kind.identref.ident;
            if (!lrl_ident_valid(baseident)) goto end;
            
            defnode = get_def_node(baseident);
            if (!defnode || !is_typedef(defnode)) {
                lrl_err_set_type(ctx, type, 0);
                lrl_err_set_type(ctx, basetype, 1);
                lrl_err_finish(ctx, LRL_Err_ExpectedType);
                goto end;
            }
            
            /* Type parameters */
            deftype = &defnode->def.kind.type;
            name = deftype->typenames;
            
            if (!name) {
                lrl_err_type(ctx, LRL_Err_ParamsOnNonParamType, type);
                goto end;
            }
            
            for (param = type->kind.parametric.params;
                param; param = param->next) {
                
                if (!name) {
                    lrl_err_type(ctx, LRL_Err_TooManyTypeArgs, type);
                    goto end;
                }
                
                verify_type(ctx, param->type, NULL, NULL);
                
                name = name->next;
            }
            
            if (name) {
                lrl_err_type(ctx, LRL_Err_TooFewTypeArgs, type);
                goto end;
            }
            break; }
        case LRL_AST_Type_Pointer:
            if (storedby && storedby->ast_type == LRL_AST_Type_Optional &&
                    is_raw_pointer(type)) {
                lrl_err_type(ctx, LRL_Err_OptionalRawPointer, type);
            }
            /* Pointers aren't containers, hence the NULLs */
            verify_type(ctx, type->kind.pointer.type, NULL, NULL);
            break;
        case LRL_AST_Type_Enum: {
            LRLASTDefList *value;
            const LRLASTExpr *last_expr = NULL;
            LRLTypeRef basetyperef;
            basetyperef.quals = LRL_Qual_Const|LRL_Qual_Mine;
            basetyperef.prm = NULL;
            basetyperef.type = type->kind.enu.base_type;
            
            verify_type(ctx, type->kind.enu.base_type, NULL, type);
            
            /* Check values */
            value = type->kind.enu.values;
            for (; value; value = value->next) {
                LRLASTExpr *expr;
                int status;
                
                if (value->def.ast_type != LRL_AST_Def_Data)
                    fail("vfytype_enum_notdata");
                
                expr = value->def.kind.data.value;
                if (!expr) {
                    /* Omitted value. Increment the previous value or
                       start from zero if it's the first value. */
                    value->def.kind.data.value = expr =
                        get_next_number_expr(
                                last_expr, type->kind.enu.base_type,
                                &value->def.kind.data);
                } else if (type != lrl_builtin_get_type(LRL_BT_bool)) {
                    /* Use constexpr to evaluate the expression */
                    status = lrl_constexpr_expr_is_evaluatable(ctx, expr);
                    if (status == 1) {
                        /* Try to evaluate expression */
                        LRLASTExpr *constexpr = lrl_constexpr_eval(ctx, expr);
                        if (constexpr) {
                            value->def.kind.data.value = expr = constexpr;
                        }
                    } else if (status == 0) {
                        lrl_err_expr(ctx, LRL_Err_ConstantTooComplex, expr);
                    }
                }
                
                verify_expr(ctx, expr, &basetyperef, 0);
                
                last_expr = expr;
            }
            
            break; }
        case LRL_AST_Type_Struct:
        case LRL_AST_Type_Union: {
            LRLASTDefList *entry = type->kind.struc.members;
            type->quals &= ~LRL_InternQual_Private;
            for (; entry; entry = entry->next) {
                if (entry->def.ast_type != LRL_AST_Def_Data)
                    fail("vfytype_struct_notdata");
                
                if (type->quals & LRL_InternQual_Private) {
                    entry->def.kind.data.flags |=
                        LRL_DeFl_Internal_PrivateOffset;
                }
                
                verify_type(ctx, entry->def.kind.data.type, type, type);
                
                /* this type might have became private now! */
            }
            break; }
        case LRL_AST_Type_Bitfield: {
            LRLASTDefList *entry;
            LRLTypeRef counttyperef;
            counttyperef.quals = LRL_Qual_Const|LRL_Qual_Mine;
            counttyperef.prm = NULL;
            counttyperef.type = lrl_builtin_get_type(LRL_BT_count);
            
            /* Check base type */
            if (type->kind.bitfield.base_type) {
                LRLTypeRef basetr;
                verify_type(ctx, type->kind.bitfield.base_type, NULL, type);
                
                basetr = typeref_root(type->kind.bitfield.base_type, 0);
                if (!is_unsigned(&basetr)) {
                    lrl_err_set_type(ctx, type, 0);
                    lrl_err_set_type(ctx, lrl_vfy_find_real_type(
                                        type->kind.bitfield.base_type), 1);
                    lrl_err_finish(ctx, LRL_Err_InvalidBitfieldType);
                }
            }
            
            /* Verify members */
            type->quals &= ~LRL_InternQual_Private;
            for (entry=type->kind.bitfield.members; entry; entry=entry->next) {
                if (entry->def.ast_type != LRL_AST_Def_Data)
                    fail("vfytype_bitfield_notdata");
                
                if (type->quals & LRL_InternQual_Private) {
                    entry->def.kind.data.flags |=
                        LRL_DeFl_Internal_PrivateOffset;
                }
                
                /* Check number of bits */
                verifyeval_expr(ctx, &entry->def.kind.data.value, &counttyperef);
                
                /* Check type override */
                if (entry->def.kind.data.type) {
                    verify_type(ctx, entry->def.kind.data.type, type, type);
                    /* TODO check that it's no larger than the base type */
                }
            }
            break; }
        case LRL_AST_Type_Private:
            type->quals |= LRL_InternQual_Private;
            break;
        case LRL_AST_Type_Any:
            if (storedby) {
                lrl_err_set_type(ctx, type, 0);
                lrl_err_set_type(ctx, storedby, 1);
                lrl_err_finish(ctx, LRL_Err_AnyTypeNotInPointer);
            }
            break;
        case LRL_AST_Type_Builtin:
            /* Nothing need to be checked */
            break;
        LRL_case_except_ast_types default:
            fail("vfytype_switch");
    }
    
  end:
    if ((type->quals & LRL_InternQual_ConstMemory) == 0)
        type->quals &= ~LRL_InternQual_Processing;
    
    /* Containers inherit privateness */
    if (type->quals & LRL_InternQual_Private) {
        if (type->quals & LRL_InternQual_TypeParam) {
            /* Privateness of container depends on its type parameters */
            if (storedby) storedby->quals |= LRL_InternQual_ParametricStorage;
            if (usedby) usedby->quals |= LRL_InternQual_ParametricStorage;
        } else {
            if (storedby) storedby->quals |= LRL_InternQual_Private;
            if (usedby) usedby->quals |= LRL_InternQual_Private;
        }
    } else if (type->quals & LRL_InternQual_ParametricStorage) {
        if (storedby) storedby->quals |= LRL_InternQual_ParametricStorage;
        if (usedby) usedby->quals |= LRL_InternQual_ParametricStorage;
    }
}

/**
 * Binds each type parameter of deftype with the types in prmtypes. The
 * resulting list is stored in *params.
 */
static void bind_type_params_list(const LRLASTDefList *typenames,
                                  const LRLASTTypeList *prmtypes,
                                  LRLBoundParams **params)
{
    const LRLASTDefList *name;
    for (name = typenames; name; name = name->next) {
        LRLBoundParams *prm;
        
        if (!prmtypes) break;
        
        prm = malloc(sizeof(LRLBoundParams));
        prm->name = &name->def.kind.type;
        prm->bound_type = prmtypes->type;
        prm->next = *params;
        *params = prm;
        
        prmtypes = prmtypes->next;
    }
}

/**
 * Extracts type parameters from the given type. Outputs the base type
 * and adds the bound type parameters to *params.
 */
int lrl_vfy_bind_type_params(const LRLASTType **typeptr,
                             LRLBoundParams **params)
{
    const LRLASTType *type = (*typeptr);
    if (type->ast_type == LRL_AST_Type_Parametric) {
        const LRLASTType *basetype = type->kind.parametric.type;
        const LRLASTDefOrStmt *defnode;
        *typeptr = basetype;
        
        if (basetype->ast_type != LRL_AST_Type_Ident)
            fail("vfybindparams_notidenttype");
        
        defnode = get_def_node(basetype->kind.identref.ident);
        if (!defnode || !is_typedef(defnode)) return 0;
        
        bind_type_params_list(defnode->def.kind.type.typenames,
            type->kind.parametric.params, params);
        
        return 1;
    }
    
    return 0;
}

/**
 * Substitutes parameter types with any matching bound parameter.
 */
int lrl_vfy_substitute_type_params(const LRLASTType **type,
                                   LRLBoundParams *params)
{
    /* Parameter types are always identifiers */
    if ((*type)->ast_type == LRL_AST_Type_Ident) {
        const LRLASTType *paramtype;
        const LRLASTDefOrStmt *defnode;
        
        defnode = get_def_node((*type)->kind.identref.ident);
        if (!defnode || !is_typedef(defnode)) return 0;
        
        paramtype = defnode->def.kind.type.type;
        
        for (; params; params = params->next) {
            if (params->name->type == paramtype &&
                *type != params->bound_type) {
                /* Substitute */
                *type = params->bound_type;
                return 1;
            }
        }
    }
    
    return 0;
}

/**
 * Looks up the identifier references in types.
 */
LRLTypeRef lrl_vfy_find_real_typeref(const LRLTypeRef *typeref)
{
    LRLTypeRef ret;
    /* for cycle detection */
    const LRLASTType *cyclestart = NULL;
    int iteration = 0;
    int nextstop = 2;
    
    ret = *typeref;
    while (ret.type) {
        ret.quals = override_quals(ret.quals, typeref->quals);
        
        if (ret.prm && lrl_vfy_substitute_type_params(&ret.type, ret.prm))
            continue;
        
        switch (ret.type->ast_type) {
            case LRL_AST_Type_Ident: {
                /* Dereference identifier */
                const LRLIdent* ident = ret.type->kind.identref.ident;
                const LRLASTDefOrStmt *defnode = get_def_node(ident);
                ret.type = (defnode && is_typedef(defnode) ?
                            defnode->def.kind.type.type : NULL);
                break; }
            case LRL_AST_Type_Parametric:
                /* Move type parameters to prm */
                if (!lrl_vfy_bind_type_params(&ret.type, &ret.prm)) {
                    goto failure;
                }
                break;
            case LRL_AST_Type_Enum:
            case LRL_AST_Type_Bitfield:
            case LRL_AST_Type_Struct:
            case LRL_AST_Type_Union:
            case LRL_AST_Type_Function:
            case LRL_AST_Type_Array:
            case LRL_AST_Type_Pointer:
            case LRL_AST_Type_Optional:
            case LRL_AST_Type_Builtin:
            case LRL_AST_Type_Private:
            case LRL_AST_Type_Any:
                /* "Real" type. Stop */
                return ret;
            LRL_case_except_ast_types default:
                fail("vfyfindrealtype_switch");
        }
        
        /* Cycle detection */
        if (cyclestart && ret.type == cyclestart) goto failure;
        if (++iteration == nextstop) {
            cyclestart = ret.type;
            nextstop *= 2;
            iteration = 0;
        }
    }
    
  failure:
    return make_typeref(0, NULL, NULL);
}

/**
 * Looks for identifier cycles in a type, and reports an error if found.
 * This function is more or less a copy of lrl_vfy_find_real_typeref. The
 * reason why this is not implemented in that function is that 1) that
 * function shouldn't report any errors (it can be called many many times
 * with the same typeref) and 2) it's used in places where you don't have
 * any ctx parameter.
 *
 * Cycles involving non-identifiers (e.g. structs) are allowed, but won't
 * be possible to allocate (TODO add a check for this) and are NOT supported
 * by the C backend. Cycles involving pointers, however, can be allocated
 * and are supported by the C backend.
 */
static void check_cyclic_ident_types(LRLCtx *ctx, const LRLASTType *type)
{
    LRLTypeRef tr;
    /* for cycle detection */
    const LRLASTType *cyclestart = NULL;
    int iteration = 0;
    int nextstop = 2;
    
    tr = typeref_root(type, 0);
    while (tr.type) {
        if (tr.prm && lrl_vfy_substitute_type_params(&tr.type, tr.prm))
            continue;
        
        switch (tr.type->ast_type) {
            case LRL_AST_Type_Ident: {
                /* Dereference identifier */
                const LRLIdent *ident = tr.type->kind.identref.ident;
                const LRLASTDefOrStmt *defnode = get_def_node(ident);
                tr.type = (defnode && is_typedef(defnode) ?
                           defnode->def.kind.type.type : NULL);
                break; }
            case LRL_AST_Type_Parametric:
                /* Move type parameters to prm */
                if (!lrl_vfy_bind_type_params(&tr.type, &tr.prm)) return;
                break;
            case LRL_AST_Type_Array:
                tr.type = tr.type->kind.array.type;
                break;
            case LRL_AST_Type_Enum:
                tr.type = tr.type->kind.enu.base_type;
                break;
            case LRL_AST_Type_Bitfield:
                tr.type = tr.type->kind.bitfield.base_type;
                break;
            case LRL_AST_Type_Optional:
                tr.type = tr.type->kind.optional.type;
                break;
            case LRL_AST_Type_Struct:
            case LRL_AST_Type_Union:
            case LRL_AST_Type_Function:
                /* TODO add checks for the above */
            case LRL_AST_Type_Pointer:
            case LRL_AST_Type_Builtin:
            case LRL_AST_Type_Private:
            case LRL_AST_Type_Any:
                /* "Real" type. Stop */
                return;
            LRL_case_except_ast_types default:
                fail("vfycyclictypes_switch");
        }
        
        /* Cycle detection */
        if (cyclestart && tr.type == cyclestart) {
            /* Report an error. Note that this function is most likely
               called for all types in the cycle. */
            lrl_err_type(ctx, LRL_Err_CyclicTypeDetected, type);
            return;
        }
        if (++iteration == nextstop) {
            cyclestart = tr.type;
            nextstop *= 2;
            iteration = 0;
        }
    }
}

const LRLASTType *lrl_vfy_find_real_type(const LRLASTType *type)
{
    LRLTypeRef typeref = make_typeref(0, NULL, type);
    return lrl_vfy_find_real_typeref(&typeref).type;
}

/**
 * Looks up the type of a member of a struct type in an expression.
 */
static LRLTypeRef get_member_type(LRLCtx *ctx, LRLASTExpr *expr,
                                  const LRLTypeRef *typescope)
{
    const LRLIdent *memberident;
    LRLTypeRef typeref, realtyperef;
    LRLASTType *membertype;
    
    if (!expr->kind.member.token || !expr->kind.member.struc) goto failed;
    
    /* Determine struct type and bind type parameters */
    typeref = determine_expr_type(ctx, expr->kind.member.struc, typescope, 1);
    if (!typeref.type) goto failed;
    
    realtyperef = lrl_vfy_find_real_typeref(&typeref);
    if (!realtyperef.type) goto failed;
    
    if (realtyperef.type->ast_type != LRL_AST_Type_Struct &&
        realtyperef.type->ast_type != LRL_AST_Type_Union &&
        realtyperef.type->ast_type != LRL_AST_Type_Bitfield) {
        lrl_err_set_expr(ctx, expr, 0);
        lrl_err_set_typeref(ctx, &realtyperef, 1);
        lrl_err_finish(ctx, LRL_Err_MemberOfNonStruct);
        goto failed;
    }
    
    /* Look up member in struct namespace */
    if (!expr->kind.member.ident) {
        /* Not already looked up */
        memberident = lrl_ident_get(ctx,
            (LRLIdent*)realtyperef.type->kind.struc.scope,
            expr->kind.member.token, LRL_Ident_FindMember, NULL);
        
        expr->kind.member.ident = memberident;
        
    } else {
        memberident = expr->kind.member.ident;
    }
        
    /* Check that it is a valid member */
    if (!memberident) {
        lrl_err_set_token(ctx, expr->kind.member.token, 0);
        if (expr->kind.member.struc && expr->kind.member.struc->typeref.type) {
            lrl_err_set_typeref(ctx, &expr->kind.member.struc->typeref, 1);
        }
        lrl_err_finish(ctx, LRL_Err_MemberDoesntExist);
        goto failed;
    }
    
    if (memberident == LRL_IDENT_MISSING) goto failed;
    if (!memberident->def_node) fail("vfygetmember_nodef");
    
    if (memberident->def_node->ast_type != LRL_AST_Def_Data) {
        lrl_err_set_token(ctx, expr->kind.member.token, 0);
        if (expr->kind.member.struc && expr->kind.member.struc->typeref.type) {
            lrl_err_set_typeref(ctx, &expr->kind.member.struc->typeref, 1);
        }
        lrl_err_finish(ctx, LRL_Err_NotAMember);
        goto failed;
    }
    
    /* Return type of member */
    if (!memberident->def_node->def.kind.data.type &&
         realtyperef.type->ast_type == LRL_AST_Type_Bitfield) {
        /* Default type for bitfields */
        if (memberident->def_node->def.kind.data.value) {
            /* TODO should depend on the number of bits */
            membertype = lrl_builtin_get_type(LRL_BT_uint);
        } else {
            /* 1-bit member */
            membertype = lrl_builtin_get_type(LRL_BT_bool);
        }
    } else {
        membertype = memberident->def_node->def.kind.data.type;
    }
    return typeref_nested(membertype, &realtyperef);
    
  failed:
    return make_typeref(0, NULL, NULL);
}

/**
 * Looks up a "member function", i.e. "y" in "x->y()". The "this" parameter
 * is checked and removed from the function type.
 */
static LRLTypeRef get_funcmember_type(LRLCtx *ctx, LRLASTExpr *expr,
                                       const LRLTypeRef *typescope)
{
    LRLASTType *ret;
    LRLTypeRef optyperef; /* type of x in x->y(); */
    LRLTypeRef structtyperef; /* struct type - x or x^ */
    LRLTypeRef thistyperef; /* type of x the member function expects */
    const LRLASTType *functype, *thistype;
    LRLASTExprMember *memberexpr;
    const LRLIdent *memberident;
    const LRLASTDef *thisparam;
    
    if (expr->ast_type != LRL_AST_Expr_Call)
        fail("vfyfuncmember_notacallexpr");
    
    if (expr->kind.call.function->ast_type != LRL_AST_Expr_FuncMember)
        fail("vfyfuncmember_notafunctionmemberexpr");
    
    /* Determine type of object ("this" parameter) */
    memberexpr = &expr->kind.call.function->kind.member;
    if (!memberexpr->token || !memberexpr->struc) goto failed;
    optyperef = determine_expr_type(ctx, memberexpr->struc, typescope, 1);
    if (!optyperef.type) goto failed;
    
    /* Determine type of struct */
    structtyperef = optyperef;
    for (;;) {
        if (structtyperef.type->ast_type == LRL_AST_Type_Pointer) {
            const LRLASTType *type = structtyperef.type->kind.pointer.type;
            if (!type) goto failed;
            structtyperef = typeref_root(type, 0);
        } else if (structtyperef.type->ast_type == LRL_AST_Type_Parametric) {
            if (!lrl_vfy_bind_type_params(&structtyperef.type,
                                          &structtyperef.prm)) {
                goto failed;
            }
        } else break;
    }
    verify_expr(ctx, memberexpr->struc, &optyperef, 0);
    
    /* Look up function in namespace of type */
    if (!memberexpr->ident) {
        /* Not already looked up */
        if (structtyperef.type->ast_type != LRL_AST_Type_Ident) {
            lrl_err_set_expr(ctx, expr, 0);
            lrl_err_set_typeref(ctx, &structtyperef, 1);
            lrl_err_finish(ctx, LRL_Err_FunctionMemberOfTypeWithoutNamespace);
            goto failed;
        }
        
        if (!lrl_ident_valid(structtyperef.type->kind.identref.ident))
            goto failed;
        
        memberident = lrl_ident_get(ctx,
            (LRLIdent*)structtyperef.type->kind.identref.ident,
            memberexpr->token, LRL_Ident_FindMember, NULL);
        
        memberexpr->ident = memberident;
        
    } else {
        memberident = memberexpr->ident;
    }
    
    /* Check that it is a valid member */
    if (!memberident) {
        lrl_err_set_token(ctx, memberexpr->token, 0);
        lrl_err_set_typeref(ctx, &structtyperef, 1);
        lrl_err_finish(ctx, LRL_Err_MemberDoesntExist);
        goto failed;
    }
    
    if (memberident == LRL_IDENT_MISSING || !memberident->def_node)
        goto failed;
    
    /* Check that it is a function */
    if (memberident->def_node->ast_type != LRL_AST_Def_Function) {
        lrl_err_set_token(ctx, memberexpr->token, 0);
        lrl_err_set_typeref(ctx, &structtyperef, 1);
        lrl_err_finish(ctx, LRL_Err_ExpressionIsNotCallable);
        goto failed;
    }
    functype = &memberident->def_node->def.kind.function.type;
    
    /* Check compatibility of this argument */
    if (!functype->kind.function.args->kind.struc.members) {
        lrl_err_set_token(ctx, memberexpr->token, 0);
        lrl_err_set_type(ctx, functype, 1);
        lrl_err_finish(ctx, LRL_Err_FunctionHasNoThisParam);
        goto failed;
    }
    
    thisparam = &functype->kind.function.args->kind.struc.members->def;
    thistype = thisparam->kind.data.type;
    thistyperef = typeref_root(thistype, 0);
    thistyperef.prm = structtyperef.prm;
    lrl_vfy_type_compat(ctx, &thistyperef, &optyperef,
                        expr->kind.call.function, 0);
    
    /* Remove "this" function parameter */
    ret = malloc(sizeof(LRLASTType));
    *ret = *functype;
    
    ret->kind.function.args = malloc(sizeof(LRLASTType));
    *ret->kind.function.args = *functype->kind.function.args;
    ret->kind.function.args->kind.struc.members =
        ret->kind.function.args->kind.struc.members->next;
    
    return make_typeref(0, optyperef.prm, ret);
    
  failed:
    return make_typeref(0, NULL, NULL);
}

static void type_mismatch(LRLCtx *ctx,
                          const LRLASTExpr *expr, const LRLTypeRef *typeref,
                          LRLErrorType error)
{
    lrl_err_set_expr(ctx, expr, 0);
    lrl_err_set_typeref(ctx, typeref, 1);
    lrl_err_finish(ctx, error);
}

static int require_type(LRLCtx *ctx, const LRLASTExpr *expr,
                        const LRLTypeRef *typeref,
                        LRLASTNodeType required_type,
                        LRLErrorType error)
{
    LRLTypeRef realtr = lrl_vfy_find_real_typeref(typeref);
    if (!realtr.type) return 0;
    if (realtr.type->ast_type != required_type) {
        type_mismatch(ctx, expr, typeref, error);
        return 0;
    }
    return 1;
}

static int is_bool(const LRLTypeRef *typeref)
{
    LRLTypeRef realtr = lrl_vfy_find_real_typeref(typeref);
    if (!realtr.type) return 1;
    return realtr.type == lrl_builtin_get_type(LRL_BT_bool);
}

static int is_signed(const LRLTypeRef *typeref)
{
    LRLTypeRef realtr = lrl_vfy_find_real_typeref(typeref);
    if (!realtr.type) return 0;
    if (realtr.type->ast_type != LRL_AST_Type_Builtin) return 0;
    
    return lrl_builtin_info[realtr.type->kind.builtin].is_signed;
}

static int is_unsigned(const LRLTypeRef *typeref)
{
    LRLBuiltinGroup btgroup;
    LRLTypeRef realtr = lrl_vfy_find_real_typeref(typeref);
    if (!realtr.type) return 1;
    if (realtr.type->ast_type != LRL_AST_Type_Builtin) return 0;
    
    btgroup = lrl_builtin_info[realtr.type->kind.builtin].btgroup;
    return btgroup == LRL_BTG_unsigned || btgroup == LRL_BTG_eint ||
           btgroup == LRL_BTG_wrapping;
}

static int is_eint(const LRLTypeRef *typeref)
{
    LRLBuiltinGroup btgroup;
    LRLTypeRef realtr = lrl_vfy_find_real_typeref(typeref);
    if (!realtr.type) return 1;
    if (realtr.type->ast_type != LRL_AST_Type_Builtin) return 0;
    
    btgroup = lrl_builtin_info[realtr.type->kind.builtin].btgroup;
    return btgroup == LRL_BTG_eint;
}

static int is_number(const LRLTypeRef *typeref)
{
    LRLTypeRef realtr = lrl_vfy_find_real_typeref(typeref);
    if (!realtr.type) return 1;
    return is_signed(&realtr) || is_unsigned(&realtr);
}

static int is_float(const LRLTypeRef *typeref)
{
    LRLTypeRef realtr = lrl_vfy_find_real_typeref(typeref);
    if (!realtr.type) return 0;
    if (realtr.type->ast_type != LRL_AST_Type_Builtin) return 0;
    
    return lrl_builtin_info[realtr.type->kind.builtin].btgroup ==
                                                            LRL_BTG_float;
}

static int require_bool(LRLCtx *ctx, const LRLASTExpr *expr,
                        const LRLTypeRef *typeref)
{
    if (!typeref->type) return 1;
    if (!is_bool(typeref)) {
        if (expr) type_mismatch(ctx, expr, typeref,
                                LRL_Err_TargetIsNotBooleanType);
        return 0;
    }
    return 1;
}

static int require_unsigned(LRLCtx *ctx, const LRLASTExpr *expr,
                          const LRLTypeRef *typeref)
{
    if (!typeref->type) return 1;
    if (!is_unsigned(typeref)) {
        if (expr) type_mismatch(ctx, expr, typeref,
                                LRL_Err_TargetIsNotUnsignedType);
        return 0;
    }
    return 1;
}

static int require_signed(LRLCtx *ctx, const LRLASTExpr *expr,
                          const LRLTypeRef *typeref)
{
    if (!typeref->type) return 1;
    if (!is_signed(typeref)) {
        if (expr) type_mismatch(ctx, expr, typeref,
                                LRL_Err_TargetIsNotSignedType);
        return 0;
    }
    return 1;
}

static int require_non_eint(LRLCtx *ctx, const LRLASTExpr *expr,
                            const LRLTypeRef *typeref)
{
    if (!typeref->type) return 1;
    if (is_eint(typeref)) {
        if (expr) type_mismatch(ctx, expr, typeref,
                                LRL_Err_TargetMayNotBeEint);
        return 0;
    }
    return 1;
}

static int require_number(LRLCtx *ctx, const LRLASTExpr *expr,
                          const LRLTypeRef *typeref)
{
    if (!typeref->type) return 1;
    if (!is_number(typeref)) {
        if (expr) type_mismatch(ctx, expr, typeref,
                                LRL_Err_TargetIsNotNumberType);
        return 0;
    }
    return 1;
}

static int require_number_expr(LRLCtx *ctx, const LRLASTExpr *expr)
{
    if (!expr) return 1;
    if (!is_number(&expr->typeref)) {
        if (expr) type_mismatch(ctx, expr, &expr->typeref,
                                LRL_Err_ExpectedNumberExpr);
        return 0;
    }
    return 1;
}

static int require_float(LRLCtx *ctx, const LRLASTExpr *expr,
                         const LRLTypeRef *typeref)
{
    if (!typeref->type) return 1;
    if (!is_float(typeref)) {
        if (expr) type_mismatch(ctx, expr, typeref,
                                LRL_Err_TargetIsNotFloatType);
        return 0;
    }
    return 1;
}

static int require_lvalue(LRLCtx *ctx, const LRLASTExpr *expr)
{
    switch (expr->ast_type) {
        case LRL_AST_Value_Ident:
        case LRL_AST_Value_TypeIdent:
            return 1;
        case LRL_AST_Expr_ArrayIndex:
            return require_lvalue(ctx, expr->kind.index.array);
        case LRL_AST_Expr_Member:
            return require_lvalue(ctx, expr->kind.member.struc);
        case LRL_AST_Expr_As:
            /* TODO lvalue could perhaps do a "reverse" cast in this case */
            goto not_lvalue;
        case LRL_AST_Expr_UnaryOp:
            switch (expr->kind.unary_op.token_type) {
                case LRL_Op_EnumBase:
                case LRL_Op_Deref:
                    return 1;
                case LRL_Op_Plus:
                case LRL_Op_Minus:
                case LRL_Op_AddrOf:
                case LRL_Op_MakeOpt:
                case LRL_Op_Compl:
                case LRL_Op_LNot:
                case LRL_Op_SizeOf:
                case LRL_Op_MinSizeOf:
                case LRL_Op_OffsetOf:
                case LRL_Op_AlignOf:
                case LRL_Op_OptionalValue:
                    goto not_lvalue;
                LRL_case_except_tt_unops default:
                    fail("vfyreqlvalue_unop_switch");
            }
        case LRL_AST_Expr_BinaryOp:
            /* Assignment ops always return an lvalue, and the nested lvalue
               is verified in another require_lvalue call */
            if (expr->kind.binary_op.token_type == LRL_Op_Assign) return 1;
            else goto not_lvalue;
        case LRL_AST_Expr_Conditional:
            return require_lvalue(ctx, expr->kind.conditional.trueexpr) &&
                   require_lvalue(ctx, expr->kind.conditional.falseexpr);
        case LRL_AST_Expr_Evaluated:
            return require_lvalue(ctx, expr->kind.evaluated.evaluated);
        case LRL_AST_Value_Undefined:
        case LRL_AST_Value_None:
        case LRL_AST_Value_NaN:
        case LRL_AST_Value_Inf:
        case LRL_AST_Value_Scalar:
        case LRL_AST_Value_Struct:
        case LRL_AST_Value_Array:
        case LRL_AST_Expr_FuncMember:
        case LRL_AST_Expr_Call:
        case LRL_AST_Expr_TypeAssert:
        LRL_case_except_ast_exprs_values default:
          not_lvalue:
            lrl_err_expr(ctx, LRL_Err_MustBeLValue, expr);
            return 0;
    }
}

/** Requires an expression that has a value (i.e. is not a function
    reference) */
static int require_value_expr(LRLCtx *ctx, const LRLASTExpr *expr)
{
    const LRLTypeRef realtr = lrl_vfy_find_real_typeref(&expr->typeref);
    if (!realtr.type) return 0;
    if (realtr.type->ast_type == LRL_AST_Type_Function) {
        if (expr) type_mismatch(ctx, expr, &expr->typeref,
                                LRL_Err_FunctionsAreNotValues);
        return 0;
    }
    return 1;
}

/**
 * Determines the best type of a literal expression.
 */
static const LRLASTType *determine_literal_expr_type(LRLCtx *ctx,
                                                     const LRLASTExpr *expr,
                                                     const LRLASTType *target_type,
                                                     int show_error)
{
    if (!expr) return NULL;
    if (expr->ast_type == LRL_AST_Value_Scalar) {
        /* Literal scalar value */
        const LRLToken *token = expr->kind.scalar.token;
        switch (token->type) {
            case LRL_TT_Integer: {
                LRLBuiltinType bt = lrl_builtin_determine_int_type(&token->loc,
                                                expr->kind.scalar.is_negative);
                if (bt != LRL_BT_INVALID) {
                    return lrl_builtin_get_type(bt);
                }
                /* Error */
                if (show_error) {
                    lrl_err_token(ctx, LRL_Err_IntegerLargerThanLargestType,
                                  token);
                }
                return NULL; }
            case LRL_TT_Real: {
                LRLTypeRef targettr = typeref_root(target_type, 0);
                if (is_float(&targettr)) {
                    /* TODO check size and precision */
                    /* Type is valid */
                    return target_type;
                } else if (show_error) {
                    /* Not a float type */
                    if (target_type) {
                        lrl_err_set_expr(ctx, expr, 0);
                        lrl_err_set_type(ctx, target_type, 1);
                        lrl_err_finish(ctx, LRL_Err_TargetIsNotFloatType);
                        return lrl_builtin_get_type(LRL_BT_float);
                    } else {
                        lrl_err_set_expr(ctx, expr, 0);
                        lrl_err_finish(ctx, LRL_Err_AmbiguousStmtType);
                        return lrl_builtin_get_type(LRL_BT_float);
                    }
                } else {
                    return NULL;
                } }
            case LRL_TT_String: {
                /* FIXME and perhaps this should return an array instead
                   of a pointer to an array? if you want the pointer, you
                   can write @"Hello" instead. but using arrays for strings
                   can be confusing when it comes to non-ASCII characters,
                   since they use multiple bytes or "chars". */
                LRLASTType *t = malloc(sizeof(LRLASTType));
                t->ast_type = LRL_AST_Type_Pointer;
                t->kind.pointer.type = lrl_builtin_get_type(LRL_BT_char);
                t->kind.pointer.flags = LRL_PF_Flexible; /* we can do "hello"#[i] */
                t->from = expr->from;
                t->to = expr->to;
                t->quals = 0;
                t->unique_id = 0;
                return t; }
            case LRL_TT_Ident:
            case LRL_TT_Undefined:
            case LRL_TT_None:
            case LRL_TT_NaN:
            case LRL_TT_Inf:
            case LRL_KW_Here:
            LRL_case_except_tt_values default:
                fail("vfyliteralexprtype_scalar_switch");
        }
    }
    return NULL;
}

/**
 * Determines the type of an array literal.
 */
static LRLTypeRef determine_array_type(LRLCtx *ctx, const LRLASTExpr *expr,
                                       const LRLTypeRef *elem_tr)
{
    LRLASTType *arrtype;
    size_t length;
    
    (void)(ctx);
    if (expr->ast_type != LRL_AST_Value_Array)
        fail("vfy_determarrtype_notarray");
    if (!elem_tr) fail("vfy_determarrtype_noelemtype");
    
    length = expr->kind.array.values.num_args;
    
    arrtype = malloc(sizeof(LRLASTType));
    arrtype->ast_type = LRL_AST_Type_Array;
    arrtype->from = expr->from;
    arrtype->to = expr->to;
    arrtype->quals = 0;
    arrtype->unique_id = LRL_UNIQUEID_UNSET;
    arrtype->kind.array.type = (LRLASTType*)elem_tr->type;
    arrtype->kind.array.length = get_count_expr(length);
    
    return typeref_nested(arrtype, elem_tr);
}

static void must_use_result(LRLCtx *ctx, LRLASTExpr *expr, ExprFlags flags)
{
     if ((flags & (StatementLevel|NestedAssign)) == StatementLevel) {
         lrl_err_expr(ctx, LRL_Err_ExprResultNotUsed, expr);
     }
}

static void verify_unary_op(LRLCtx *ctx, LRLASTExpr *expr,
                            const LRLTypeRef *typeref,
                            ExprFlags flags)
{
    /* TODO shouldn't qualifiers be checked too (in pointers at least)? */
    LRLTypeRef realtyperef = lrl_vfy_find_real_typeref(typeref);
    LRLASTExpr *operand = expr->kind.unary_op.operand;
    switch (expr->kind.unary_op.token_type) {
        case LRL_Op_AddrOf: {
            /* type = type(operand)^ */
            LRLTypeRef ptrtyperef;
            must_use_result(ctx, expr, flags);
            if (realtyperef.type->ast_type == LRL_AST_Type_Optional) {
                LRLTypeRef tr = typeref_nested(realtyperef.type->kind.optional.type, &realtyperef);
                ptrtyperef = lrl_vfy_find_real_typeref(&tr);
            } else {
                ptrtyperef = realtyperef;
            }
            
            if (require_type(ctx, expr, &ptrtyperef, LRL_AST_Type_Pointer,
                             LRL_Err_TargetIsNotPointerType) &&
                    ptrtyperef.type->kind.pointer.type) {
                LRLTypeRef tr;
                tr.quals = ptrtyperef.type->kind.pointer.type->quals;
                tr.prm = ptrtyperef.prm;
                tr.type = ptrtyperef.type->kind.pointer.type;
                verify_expr(ctx, operand, &tr, 0);
            }
            break; }
        case LRL_Op_Deref: {
            /* type^ = type(operand) */
            LRLTypeRef tr;
            
            LRLASTType *t = malloc(sizeof(LRLASTType));
            t->ast_type = LRL_AST_Type_Pointer;
            t->kind.pointer.type = (LRLASTType*)typeref->type;
            t->kind.pointer.flags = LRL_InternPF_Dereferenced;
            t->from = typeref->type->from;
            t->to = typeref->type->to;
            t->quals = 0;
            t->unique_id = 0;
            
            tr.quals = LRL_Qual_Const|LRL_Qual_Mine;
            tr.prm = realtyperef.prm;
            tr.type = t;
            verify_expr(ctx, operand, &tr, 0);
            break; }
        case LRL_Op_EnumBase:
            /* type = base_type of operand */
            must_use_result(ctx, expr, flags);
            if (!operand) return;
            operand->typeref = determine_expr_type(ctx, operand, NULL, 1);
            verify_expr(ctx, operand, &operand->typeref, 0);
            
            /* Check that the enum base type is compatible */
            if (require_type(ctx, operand, &operand->typeref,
                             LRL_AST_Type_Enum, LRL_Err_ExpectedEnumExpr)) {
                LRLTypeRef realtr = lrl_vfy_find_real_typeref(&operand->typeref);
                LRLASTType *basetype = realtr.type->kind.enu.base_type;
                if (basetype) {
                    LRLTypeRef basetr = typeref_nested(basetype, &realtr);
                    lrl_vfy_type_compat(ctx, typeref, &basetr, expr, 0);
                }
            }
            break;
        case LRL_Op_MakeOpt:
            /* type = type(operand)? */
            must_use_result(ctx, expr, flags);
            if (require_type(ctx, expr, typeref, LRL_AST_Type_Optional,
                             LRL_Err_TargetIsNotOptionalType) &&
                     realtyperef.type->kind.optional.type) {
                LRLTypeRef tr;
                tr.quals = realtyperef.type->kind.optional.type->quals;
                tr.prm = realtyperef.prm;
                tr.type = realtyperef.type->kind.optional.type;
                verify_expr(ctx, operand, &tr, 0);
            }
            break;
        case LRL_Op_SizeOf:
        case LRL_Op_MinSizeOf:
        case LRL_Op_AlignOf: {
            LRLTypeRef optr;
            
            /* This type might be to small but if the size value doesn't fit
               in this size then the backend can report an error. */
            require_number(ctx, expr, typeref);
            must_use_result(ctx, expr, flags);
            
            optr = determine_expr_type(ctx, operand, NULL, 1);
            if (optr.type) {
                LRLTypeRef tr = lrl_vfy_find_real_typeref(&optr);
                const LRLASTType *t = tr.type;
                if (t) {
                    if (t->ast_type == LRL_AST_Type_Private) {
                        lrl_err_set_expr(ctx, expr, 0);
                        lrl_err_set_type(ctx, optr.type, 1);
                        lrl_err_finish(ctx, LRL_Err_SizeOfWithPrivateType);
                    } else if (is_private_type(ctx, &tr) &&
                           expr->kind.unary_op.token_type != LRL_Op_MinSizeOf) {
                        lrl_err_set_expr(ctx, expr, 0);
                        lrl_err_set_type(ctx, optr.type, 1);
                        lrl_err_finish(ctx, LRL_Err_SizeOfWithSemiPrivateType);
                    /* TODO this code is copy-pasted from verify_def_data */
                    } else if (t->ast_type == LRL_AST_Type_Function) {
                        lrl_err_set_expr(ctx, expr, 0);
                        lrl_err_set_type(ctx, optr.type, 1);
                        lrl_err_finish(ctx, LRL_Err_SizeOfFunction);
                    } else if (t->ast_type == LRL_AST_Type_Any) {
                        lrl_err_set_expr(ctx, expr, 0);
                        lrl_err_set_type(ctx, optr.type, 1);
                        lrl_err_finish(ctx, LRL_Err_SizeOfAny);
                    } else if (t->ast_type == LRL_AST_Type_Array &&
                        t->kind.array.length &&
                        t->kind.array.length->ast_type == LRL_AST_Value_Undefined) {
                        lrl_err_set_expr(ctx, expr, 0);
                        lrl_err_set_type(ctx, optr.type, 1);
                        lrl_err_finish(ctx, LRL_Err_SizeOfUnknownLengthArray);
                    }
                }
                verify_expr(ctx, operand, &optr, 0);
            }
            break; }
        case LRL_Op_OffsetOf:
            /* TODO */
            must_use_result(ctx, expr, flags);
            break;
        case LRL_Op_LNot:
            must_use_result(ctx, expr, flags);
            /* Check that the type is bool */
            require_bool(ctx, expr, typeref);
            
            verify_expr(ctx, operand, &ctx->bool_tr, 0);
            break;
        case LRL_Op_Plus:
        case LRL_Op_Minus:
            must_use_result(ctx, expr, flags);
            /* Check that the type is a signed number (float, int, intN...).
               Note that unsigned numbers can't possibly work because there
               are no implicit type conversions! */
            require_signed(ctx, expr, typeref);
            
            /* Expression type is not changed */
            verify_expr(ctx, operand, typeref, 0);
            break;
        case LRL_Op_Compl:
            must_use_result(ctx, expr, flags);
            /* Can't do bitwise complement reliably if we might have a
               sign bit */
            require_non_eint(ctx, expr, typeref); /* and */
            require_unsigned(ctx, expr, typeref);
            
            /* Expression type is not changed */
            verify_expr(ctx, operand, typeref, 0);
            break;
        case LRL_Op_OptionalValue: {
            /* type? = type(operand) */
            LRLTypeRef tr;
            
            LRLASTType *t = malloc(sizeof(LRLASTType));
            t->ast_type = LRL_AST_Type_Optional;
            t->kind.optional.type = (LRLASTType*)typeref->type;
            t->from = typeref->type->from;
            t->to = typeref->type->to;
            t->quals = typeref->type->quals;
            t->unique_id = 0;
            
            tr = typeref_nested(t, typeref);
            must_use_result(ctx, expr, flags);
            verify_expr(ctx, operand, &tr, 0);
            break; }
        LRL_case_tt_binops
        LRL_case_tt_otherops
        LRL_case_except_tt_ops default:
            fail("vfyunop_switch");
    }
}

static void verify_binary_op(LRLCtx *ctx, LRLASTExpr *expr,
                             const LRLTypeRef *typeref,
                             ExprFlags flags)
{
    /* TODO shouldn't qualifiers be checked too (in pointers at least)? */
    const LRLTokenType optype = expr->kind.binary_op.token_type;
    LRLASTExpr *operand1 = expr->kind.binary_op.operand1;
    LRLASTExpr *operand2 = expr->kind.binary_op.operand2;
    switch (optype) {
        case LRL_Op_Plus:
        case LRL_Op_Minus:
        case LRL_Op_Times:
        case LRL_Op_Divide:
        case LRL_Op_Modulo:
            must_use_result(ctx, expr, flags);
            require_number(ctx, expr, typeref);
            
            /* Expression type is not changed */
            verify_expr(ctx, operand1, typeref, 0);
            verify_expr(ctx, operand2, typeref, 0);
            break;
        case LRL_Op_ShiftL:
            /* Can't do left shift reliably if we might have a sign bit */
            require_non_eint(ctx, expr, typeref);
            /* Fall through */
        case LRL_Op_ShiftR:
        case LRL_Op_BitAnd:
        case LRL_Op_BitOr:
        case LRL_Op_BitXor:
            require_unsigned(ctx, expr, typeref);
            must_use_result(ctx, expr, flags);
            
            /* Expression type is not changed */
            verify_expr(ctx, operand1, typeref, 0);
            verify_expr(ctx, operand2, typeref, 0);
            break;
        case LRL_Op_LXor:
            must_use_result(ctx, expr, flags);
        case LRL_Op_LAnd:
        case LRL_Op_LOr:
            require_bool(ctx, expr, typeref);
            
            verify_expr(ctx, operand1, &ctx->bool_tr, 0);
            verify_expr(ctx, operand2, &ctx->bool_tr, 0);
            break;
        case LRL_Op_Equal:
        case LRL_Op_NotEqual:
        case LRL_Op_Less:
        case LRL_Op_LessEqual:
        case LRL_Op_Greater:
        case LRL_Op_GreaterEqual:
            must_use_result(ctx, expr, flags);
            require_bool(ctx, expr, typeref);
            
            if (!operand1 || !operand2) break;
            
            /* First, try to detect the type of at least one operand */
            if (!operand1->typeref.type) {
                operand1->typeref = determine_expr_type(ctx, operand1,
                                                        NULL, 0);
            }
            if (!operand2->typeref.type) {
                operand2->typeref = determine_expr_type(ctx, operand2,
                                                &operand1->typeref, 0);
            }

            if (!operand1->typeref.type && !operand2->typeref.type) {
                lrl_err_expr(ctx, LRL_Err_CantDetermineExprType, operand1);
            } else if (operand1->typeref.type && !operand2->typeref.type) {
                operand2->typeref = operand1->typeref;
            } else if (!operand1->typeref.type && operand2->typeref.type) {
                operand1->typeref = operand2->typeref;
            } else {
                /* Check that the types are compatible */
                /* TODO */
            }

            verify_expr(ctx, operand1, &operand1->typeref, 0);
            verify_expr(ctx, operand2, &operand2->typeref, 0);

            if (optype != LRL_Op_Equal && optype != LRL_Op_NotEqual) {
                require_number_expr(ctx, operand1);
                require_number_expr(ctx, operand2);
            } else {
                require_value_expr(ctx, operand1);
                require_value_expr(ctx, operand2);
                lrl_vfy_type_compat(ctx, &operand1->typeref, &operand2->typeref,
                                    expr, LRL_TCF_Symmetric);
            }
            break;
        case LRL_Op_PlusAssign:
        case LRL_Op_MinusAssign:
        case LRL_Op_TimesAssign:
        case LRL_Op_DivideAssign:
        case LRL_Op_ShiftLAssign:
        case LRL_Op_ShiftRAssign:
            require_number(ctx, expr, typeref);
            if ((flags & NestedAssign) != 0) {
                lrl_err_expr(ctx, LRL_Err_AssignmentInExpression, expr);
            }
            /* Fall through */
        case LRL_Op_Assign: {
            const ExprFlags newflags = (optype == LRL_Op_Assign ?
                    (StatementLevel | NestedAssign) : 0);
            const LRLTypeRef *optr;
            LRLTypeRef lvaluetr = determine_expr_type(ctx, operand1,
                                                      typeref, 1);
            if ((flags & StatementLevel) == 0) {
                lrl_err_expr(ctx, LRL_Err_AssignmentInExpression, expr);
                /* Continue anyway */
            }
            /* If the type is not given by the target type, use the left op.
               We prefer the target type because that allows expressions like
               d1=d2=s where d2 is an int and s and d1 are bytes. */
            optr = (typeref->type && !is_private_type(ctx, typeref) ?
                    typeref : &lvaluetr);
            if (optr->type && lvaluetr.type) {
                /* The left operand does not need to have any specific type,
                   (as long as it can be assigned to), so we use its
                   determined type, which in effect skips the type check. */
                verify_expr(ctx, operand1, &lvaluetr, 0);
                verify_expr(ctx, operand2, optr, newflags);
            }
            
            /* Left hand side must be assignable */
            if (operand1 && operand1->typeref.type &&
                (operand1->typeref.quals & LRL_Qual_Var) == 0) {
                lrl_err_expr(ctx, LRL_Err_CannotAssignToConstant, operand1);
            }
            require_lvalue(ctx, operand1);
            break; }
        /* LRL_Op_Member and LRL_Op_FunctionMember are not real operators,
           they are just used during parsing */
        LRL_case_tt_unops
        LRL_case_tt_otherops
        LRL_case_except_tt_ops default:
            fail("vfybinop_switch");
    }
}

static int require_function(LRLCtx *ctx, const LRLASTExpr *expr,
                            const LRLTypeRef *typeref)
{
    const LRLTypeRef realtr = lrl_vfy_find_real_typeref(typeref);
    if (!realtr.type) return 0;
    if (realtr.type->ast_type != LRL_AST_Type_Function) {
        lrl_err_set_expr(ctx, expr, 0);
        lrl_err_set_typeref(ctx, typeref, 1);
        lrl_err_finish(ctx, LRL_Err_ExpressionIsNotCallable);
        return 0;
    }
    return 1;
}



static void verify_call(LRLCtx *ctx, LRLASTExpr *expr,
                        const LRLTypeRef *typeref)
{
    LRLASTExprCall *call = &expr->kind.call;
    LRLTypeRef funtr, realfuntr, rettr;
    const LRLASTDefList *argdef;
    LRLASTExpr **argvals;
    size_t valsleft;
    LRLStructFlags argflags;
    
    /* Must have an expression to call */
    if (!call->function) return;
    
    /* Determine type of the expression */
    if (call->function->ast_type == LRL_AST_Expr_FuncMember) {
        /* Member function call (with implicit "this" pointer).
           get_funcmember_type performs verification also. */
        funtr = get_funcmember_type(ctx, expr, typeref);
        if (!funtr.type) return;
    } else {
        /* Regular function call */
        funtr = determine_expr_type(ctx, call->function, typeref, 1);
        if (!funtr.type) return;
        verify_expr(ctx, call->function, &funtr, 0);
    }
    
    /* Check that the expression is callable */
    realfuntr = lrl_vfy_find_real_typeref(&funtr);
    if (!require_function(ctx, expr, &realfuntr)) return;
    
    if (!realfuntr.type->kind.function.args ||
        realfuntr.type->kind.function.args->ast_type != LRL_AST_Type_Struct)
        fail("vfycall_strangeargs");
    
    /* Check arguments */
    argvals = call->args.values;
    valsleft = call->args.num_args;
    argdef = realfuntr.type->kind.function.args->kind.struc.members;
    argflags = realfuntr.type->kind.function.args->kind.struc.flags;
    while (argdef && valsleft > 0) {
        
        if (argdef->def.ast_type == LRL_AST_Def_Data) {
            LRLTypeRef argtyperef;
            argtyperef.quals = argdef->def.kind.data.type->quals;
            argtyperef.prm = realfuntr.prm;
            argtyperef.type = argdef->def.kind.data.type;
            verify_expr(ctx, *argvals, &argtyperef, 0);
        }
        
        argvals++;
        valsleft--;
        argdef = argdef->next;
    }
    
    if (argdef || valsleft) {
        if (valsleft && (argflags & LRL_SF_CVarArg)) {
            /* Variadic function */
            while (valsleft) {
                /* Types of arguments needs to be possible to determine
                   from the argument expressions */
                /* FIXME for numeric expressions we should require an "as"
                   expression to prevent mistakes. Currently 1 becomes
                   eint8, etc, which is usually undesirable. */
                LRLTypeRef argtyperef = determine_expr_type(ctx, *argvals,
                                                            NULL, 1);
                if (argtyperef.type) {
                    verify_expr(ctx, *argvals, &argtyperef, 0);
                }
                
                argvals++;
                valsleft--;
            }
        } else {
            lrl_err_set_expr(ctx, expr, 0);
            lrl_err_set_typeref(ctx, &funtr, 1);
            lrl_err_finish(ctx, LRL_Err_WrongNumberOfArguments);
        }
    }
    
    /* Check return type */
    rettr.quals = LRL_Qual_Const|LRL_Qual_Mine;
    rettr.prm = realfuntr.prm;
    rettr.type = realfuntr.type->kind.function.ret;
    lrl_vfy_type_compat(ctx, typeref, &rettr, call->function, 0);
}

static LRLToken *get_count_token(size_t n)
{
    LRLToken *token = malloc(sizeof(LRLToken));
    char *number = malloc(21); /* at most 64-bit number */
    sprintf(number, "%d", size2int(n));
    
    token->type = LRL_TT_Integer;
    token->loc.start = number;
    token->loc.length = strlen(number);
    return token;
}

static LRLASTExpr *get_count_expr(size_t n)
{
    LRLASTExpr *expr = malloc(sizeof(LRLASTExpr));
    expr->ast_type = LRL_AST_Value_Scalar;
    expr->typeref.quals = LRL_Qual_Const|LRL_Qual_Mine;
    expr->typeref.prm = NULL;
    expr->typeref.type = lrl_builtin_get_type(LRL_BT_count);
    expr->from = expr->to = NULL;
    expr->kind.scalar.is_negative = 0;
    expr->kind.scalar.token = get_count_token(n);
    return expr;
}

static void verify_arrayindex(LRLCtx *ctx, LRLASTExpr *expr,
                              const LRLTypeRef *typeref)
{
    LRLASTExprArrayIndex *arrind = &expr->kind.index;
    LRLTypeRef arrtyperef, indtyperef;
    
    /* Check array */
    arrtyperef = determine_expr_type(ctx, arrind->array, typeref, 0);
    if (!arrtyperef.type) {
        LRLASTExpr *curexpr;
        size_t levels;
        
        /* Either a literal type or an error occurred.
           For literal types we can determine the array type from the
           target/element type, and the length from the array literal.
           This allows doing stuff like "int j = [1,2,3]#[i];" */
        LRLASTType *arrtype = malloc(sizeof(LRLASTType));
        arrtype->ast_type = LRL_AST_Type_Array;
        arrtype->from = expr->from;
        arrtype->to = expr->to;
        arrtype->quals = 0;
        arrtype->unique_id = 0;
        arrtype->kind.array.type = (LRLASTType*)typeref->type;
        
        /* Skip array index access of shallower array dimensions */
        curexpr = arrind->array;
        if (!curexpr) goto arrtype_error;
        levels = 0;
        while (curexpr->ast_type == LRL_AST_Expr_ArrayIndex) {
            curexpr = curexpr->kind.index.array;
            if (!curexpr) goto arrtype_error;
            levels++;
        }
        
        /* Get the array */
        while (levels--) {
            if (curexpr->ast_type != LRL_AST_Value_Array) goto not_literal;
            if (!curexpr->kind.array.values.num_args) {
                /* TODO report error about zero-length array */
                goto not_literal;
            }
            /* In multi-dimensional arrays we use the first element at each
               dimension to determine the array length. lrl_verify_expr will
               check all elements, and report an error if they have a
               different type */
            curexpr = curexpr->kind.array.values.values[0];
        }
        
        if (curexpr->ast_type == LRL_AST_Value_Array) {
            size_t numelems = curexpr->kind.array.values.num_args;
            arrtype->kind.array.length = get_count_expr(numelems);
            goto determined_type;
        }
        
      not_literal:
        /* Show error if any */
        determine_expr_type(ctx, arrind->array, typeref, 1);
        goto arrtype_error;

      determined_type:
        arrtyperef.type = arrtype;
        arrtyperef.prm = typeref->prm;
        arrtyperef.quals = 0;
        
        verify_expr(ctx, arrind->array, &arrtyperef, 0);
    } else {
        /* Check that it's the correct array type */
        LRLTypeRef realtr = lrl_vfy_find_real_typeref(&arrtyperef);
        if (realtr.type) {
            if (realtr.type->ast_type == LRL_AST_Type_Array) {
                LRLTypeRef elemtr = typeref_nested(realtr.type->kind.array.type, &realtr);
                lrl_vfy_type_compat(ctx, typeref, &elemtr, expr, 0);
            } else if (is_flexi_pointer(realtr.type)) {
                LRLTypeRef elemtr = typeref_nested(realtr.type->kind.pointer.type, &realtr);
                lrl_vfy_type_compat(ctx, typeref, &elemtr, expr, 0);
            } else {
                lrl_err_set_expr(ctx, arrind->array, 0);
                lrl_err_set_type(ctx, realtr.type, 1);
                lrl_err_finish(ctx, LRL_Err_ExpectedArrayExpr);
            }
        }
    }
    
    /* Verify array type */
    if (arrtyperef.type) {
        verify_expr(ctx, arrind->array, &arrtyperef, 0);
    }
  arrtype_error:
    
    /* Check index */
    /* TODO enum index types */
    indtyperef.quals = LRL_Qual_Const|LRL_Qual_Mine;
    indtyperef.prm = typeref->prm;
    indtyperef.type = lrl_builtin_get_type(LRL_BT_count);
    verify_expr(ctx, arrind->index, &indtyperef, 0);
    /* TODO check that the index is within the range of the array type */
}

/**
 * Determines the scope to use for type-context scoping, i.e. :xx syntax.
 *
 * If error_expr is none, this function will not report any errors.
 */
static const LRLIdent *get_type_scope(LRLCtx *ctx, const LRLTypeRef *typeref,
                                      LRLASTExpr *error_expr)
{
    const LRLASTType *type;
    if (!typeref) return NULL;
    type = typeref->type;
    if (!type) return NULL;
    
    lrl_vfy_substitute_type_params(&type, typeref->prm);
    
    switch (type->ast_type) {
        case LRL_AST_Type_Enum:
            return type->kind.enu.scope;
        case LRL_AST_Type_Pointer: {
            LRLTypeRef tr = typeref_nested(type->kind.pointer.type, typeref);
            return get_type_scope(ctx, &tr, error_expr); }
        case LRL_AST_Type_Optional: {
            LRLTypeRef tr = typeref_nested(type->kind.optional.type, typeref);
            return get_type_scope(ctx, &tr, error_expr); }
        case LRL_AST_Type_Array: {
            /* Usually doesn't make much sense, but since a flexible pointer
               has a type scope, then an array should have one too. */
            LRLTypeRef tr = typeref_nested(type->kind.array.type, typeref);
            return get_type_scope(ctx, &tr, error_expr); }
        case LRL_AST_Type_Parametric: {
            LRLTypeRef tr = *typeref;
            lrl_vfy_bind_type_params(&tr.type, &tr.prm);
            return get_type_scope(ctx, &tr, error_expr); }
        case LRL_AST_Type_Ident:
            /* Use namespace of target directly */
            /* TODO should it work differently with aliases? */
            return (!lrl_identref_queue(ctx, (LRLIdentRef*)&type->kind.identref) ?
                    type->kind.identref.ident : NULL);
        case LRL_AST_Type_Bitfield:
        case LRL_AST_Type_Struct:
        case LRL_AST_Type_Union:
        case LRL_AST_Type_Function:
        case LRL_AST_Type_Builtin:
        case LRL_AST_Type_Private:
        case LRL_AST_Type_Any: {
            if (error_expr) {
                lrl_err_set_expr(ctx, error_expr, 0);
                lrl_err_set_type(ctx, type, 1);
                lrl_err_finish(ctx, LRL_Err_TypeHasNoTypeScope);
            }
            return NULL; }
        LRL_case_except_ast_types default:
            fail("vfygettypescope_switch");
            return NULL;
    }
}

static int is_private_given_params(LRLCtx *ctx, const LRLTypeRef *typeref)
{
    LRLTypeRef realtr = lrl_vfy_find_real_typeref(typeref);
    LRLASTType *type = (LRLASTType*)realtr.type;
    if (!type) return 0;
    
    switch (type->ast_type) {
        case LRL_AST_Type_Array: {
            LRLTypeRef arrtr = typeref_nested(type->kind.array.type, &realtr);
            return is_private_given_params(ctx, &arrtr); }
        case LRL_AST_Type_Ident:
            if (!lrl_identref_queue(ctx, &type->kind.identref)) {
                LRLASTDefOrStmt *defref = get_def_node(type->kind.identref.ident);
                if (defref && is_typedef(defref)) {
                    
                    LRLTypeRef deftr = typeref_nested(defref->def.kind.type.type, &realtr);
                    return is_private_given_params(ctx, &deftr);
                }
            }
            return 0;
        case LRL_AST_Type_Bitfield:
        case LRL_AST_Type_Enum: {
            LRLTypeRef basetr = typeref_nested(type->kind.enu.base_type, &realtr);
            return is_private_given_params(ctx, &basetr); }
        case LRL_AST_Type_Optional: {
            LRLTypeRef basetr = typeref_nested(type->kind.optional.type, &realtr);
            return is_private_given_params(ctx, &basetr); }
        case LRL_AST_Type_Struct:
        case LRL_AST_Type_Union: {
            LRLASTDefList *entry = type->kind.struc.members;
            for (; entry; entry = entry->next) {
                LRLTypeRef entrytr;
                if (entry->def.ast_type != LRL_AST_Def_Data)
                    fail("vfyispriv_struct_notdata");
                
                entrytr = typeref_nested(entry->def.kind.data.type, &realtr);
                if (is_private_given_params(ctx, &entrytr)) {
                    return 1;
                }
            }
            return 0; }
        case LRL_AST_Type_Function:
        case LRL_AST_Type_Pointer:
        case LRL_AST_Type_Builtin:
            return 0;
        case LRL_AST_Type_Private:
        case LRL_AST_Type_Any:
            return 1;
        case LRL_AST_Type_Parametric:
            /* TODO can we get here? what to do in that case? */
            fail("vfyispriv_parametric_whattodohere");
        LRL_case_except_ast_types default:
            fail("vfyispriv_switch");
    }
}

int lrl_vfy_is_private_type(LRLCtx *ctx, const LRLTypeRef *typeref)
{
    LRLTypeRef realtr = lrl_vfy_find_real_typeref(typeref);
    if (!realtr.type) return 0;
    
    return (realtr.type->quals & LRL_InternQual_Private) ||
        ((realtr.type->quals & LRL_InternQual_ParametricStorage) &&
          is_private_given_params(ctx, typeref));
}

/**
 * Checks that an expression is correct (most importantly it checks the
 * types). The expected type of the expression must be passed in the "target"
 * parameter. For root expressions this should be determined by the
 * determine_expr_type() function.
 */
static void verify_expr(LRLCtx *ctx, LRLASTExpr *expr,
                        const LRLTypeRef *targettr, ExprFlags flags)
{
    LRLTypeRef realtarget = lrl_vfy_find_real_typeref(targettr);
    LRLTypeRef target = *targettr;
    ExprFlags newflags = (flags & ~StatementLevel);
    if (!expr || !realtarget.type) {
        return; /* Can't verify due to previous errors */
    }
    
    /* Type names are always substituted with their parameters */
    lrl_vfy_substitute_type_params(&target.type, target.prm);
    
    if (!expr->typeref.type) {
        expr->typeref = target; /* Must be */
    }
    
    if (is_private_type(ctx, &realtarget)) {
        lrl_err_set_expr(ctx, expr, 0);
        lrl_err_set_type(ctx, realtarget.type, 1);
        lrl_err_finish(ctx, LRL_Err_TakingValueOfPrivateType);
    }
    
    /* TODO check qualifiers (if this can be done here) */
    
    switch (expr->ast_type) {
        case LRL_AST_Expr_UnaryOp:
            verify_unary_op(ctx, expr, &target, flags);
            break;
        case LRL_AST_Expr_BinaryOp:
            verify_binary_op(ctx, expr, &target, flags);
            break;
        case LRL_AST_Expr_Conditional: {
            /* "then-else" operator */
            LRLASTExpr *condexpr = expr->kind.conditional.condexpr;
            LRLASTExpr *trueexpr = expr->kind.conditional.trueexpr;
            LRLASTExpr *falseexpr = expr->kind.conditional.falseexpr;
            verify_expr(ctx, condexpr, &ctx->bool_tr, newflags);
            
            verify_expr(ctx, trueexpr, &target, newflags);
            verify_expr(ctx, falseexpr, &target, newflags);
            break; }
        case LRL_AST_Expr_Call:
            verify_call(ctx, expr, &target);
            break;
        case LRL_AST_Expr_Member: {
            LRLTypeRef structtr;
            LRLTypeRef membertr = get_member_type(ctx, expr, &target);
            
            structtr = determine_expr_type(ctx, expr->kind.member.struc, &target, 1);
            verify_expr(ctx, expr->kind.member.struc, &structtr, newflags);
            
            if (membertr.type)
            {
                lrl_vfy_type_compat(ctx, &target, &membertr, expr, 0);
            }
            break; }
        case LRL_AST_Expr_FuncMember:
            lrl_err_expr(ctx, LRL_Err_FunctionMembersAreNotValues, expr);
            break;
        case LRL_AST_Expr_As: {
            LRLTypeRef astyperef;
            astyperef.quals = expr->kind.asexpr.type->quals;
            astyperef.prm = expr->typeref.prm;
            astyperef.type = expr->kind.asexpr.type;
            verify_type(ctx, expr->kind.asexpr.type, NULL, NULL);
            verify_expr(ctx, expr->kind.asexpr.expr, &astyperef, newflags);
            break; }
        case LRL_AST_Expr_Evaluated: {
            const LRLASTExpr *origexpr = expr->kind.evaluated.original;
            LRLASTExpr *evaluatedexpr = expr->kind.evaluated.evaluated;
            LRLErrorCtx errctx;
            lrl_errctx_start_loc(ctx, &errctx, origexpr->from, origexpr->to);
            if (evaluatedexpr->typeref.type) {
                verify_expr(ctx, evaluatedexpr, &evaluatedexpr->typeref, flags);
            }
            lrl_errctx_end(ctx, &errctx);
            break; }
        case LRL_AST_Expr_TypeAssert: {
            LRLTypeRef fromtr, tatr;
            
            if (!expr->kind.typeassert.type) break; /* earlier error */
            tatr.quals = expr->kind.typeassert.type->quals;
            tatr.prm = expr->typeref.prm;
            tatr.type = expr->kind.typeassert.type;
            verify_type(ctx, expr->kind.typeassert.type, NULL, NULL);
            
            fromtr = determine_expr_type(ctx, expr->kind.typeassert.expr, &tatr, 1);
            verify_expr(ctx, expr->kind.typeassert.expr, &fromtr, newflags);
            
            if (tatr.type) {
                if (fromtr.type) {
                    lrl_vfy_type_compat(ctx, &tatr, &fromtr, expr,
                                        LRL_TCF_IsTypeAssert);
                }
                lrl_vfy_type_compat(ctx, &target, &tatr, expr, 0);
            }
            break; }
        case LRL_AST_Expr_ArrayIndex:
            verify_arrayindex(ctx, expr, &target);
            break;
        case LRL_AST_Value_TypeIdent:
            if (!expr->kind.ident.identref.scope) {
                expr->kind.ident.identref.scope = get_type_scope(ctx,
                                                        targettr, expr);
                if (!expr->kind.ident.identref.scope) break;
            }
            /* Fall through */
        case LRL_AST_Value_Ident: {
            LRLIdentRef *identref = &expr->kind.ident.identref;
            LRLASTTypeList *param;
            if (!lrl_identref_queue(ctx, identref)) {
                LRLASTDefOrStmt *defref = get_def_node(identref->ident);
                
                /* Check that the type of the data/function match */
                if (!defref) {
                    goto valident_nodef;
                } else if (defref->ast_type == LRL_AST_Def_Data) {
                    LRLTypeRef tr;
                    tr.quals = LRL_Qual_Const;
                    tr.prm = realtarget.prm;
                    tr.type = defref->def.kind.data.type;
                    lrl_vfy_type_compat(ctx, &target, &tr, expr, 0);
                    
                } else if (defref->ast_type == LRL_AST_Def_Function) {
                    LRLASTTypeList *typeparams = expr->kind.ident.type_params;
                    LRLTypeRef tr;
                    tr.quals = LRL_Qual_Const;
                    tr.prm = realtarget.prm;
                    tr.type = &defref->def.kind.function.type;
                    bind_type_params_list(defref->def.kind.function.typenames,
                                          typeparams, &tr.prm);
                    
                    lrl_vfy_type_compat(ctx, &target, &tr, expr, 0);
                    
                } else if (defref->ast_type == LRL_AST_Stmt_Decl) {
                    LRLTypeRef tr;
                    tr.quals = LRL_Qual_Const;
                    tr.prm = realtarget.prm;
                    tr.type = defref->def.kind.data.type;
                    lrl_vfy_type_compat(ctx, &target, &tr, expr, 0);
                    
                } else {
                  valident_nodef:
                    lrl_err_set_ident(ctx, identref->first_token, 0);
                    lrl_err_finish(ctx, LRL_Err_IdentIsNotValue);
                }
            }
            /* Verify type params, if any */
            for (param = expr->kind.ident.type_params; param;
                 param = param->next) {
                verify_type(ctx, param->type, NULL, NULL);
            }
            break; }
        case LRL_AST_Value_None:
            if (!is_raw_pointer(realtarget.type)) {
                /* Not a raw pointer (these implicitly accept optional types) */
                require_type(ctx, expr, &target, LRL_AST_Type_Optional,
                             LRL_Err_TargetIsNotOptionalType);
            }
            break;
        case LRL_AST_Value_NaN:
        case LRL_AST_Value_Inf:
            require_float(ctx, expr, &target);
            break;
        case LRL_AST_Value_Undefined:
            /* Is compatible with any non-private type */
            break;
        case LRL_AST_Value_Scalar: {
            LRLTypeRef tr;
            tr.quals = LRL_Qual_Const|LRL_Qual_Mine;
            tr.prm = realtarget.prm;
            tr.type = determine_literal_expr_type(ctx, expr, target.type, 1);
            if (tr.type) {
                lrl_vfy_type_compat(ctx, &target, &tr, expr, 0);
            }
            break; }
        case LRL_AST_Value_Array: {
            size_t i;
            LRLASTExpr *lengthexpr;
            if (realtarget.type->ast_type != LRL_AST_Type_Array) {
                lrl_err_set_expr(ctx, expr, 0);
                lrl_err_set_type(ctx, target.type, 1);
                lrl_err_finish(ctx, LRL_Err_TargetIsNotArrayType);
                break;
            }
            
            lengthexpr = realtarget.type->kind.array.length;
            if (lengthexpr && lengthexpr->ast_type != LRL_AST_Value_Undefined) {
                /* Compare lengths */
                size_t numargs = expr->kind.exprlist.num_args;
                LRLASTExpr *elemcount = get_count_expr(numargs);
                if (!exprs_equal(ctx, lengthexpr, elemcount)) {
                    lrl_err_set_expr(ctx, expr, 0);
                    lrl_err_set_typeref(ctx, &realtarget, 1);
                    lrl_err_finish(ctx, LRL_Err_ArrayLengthsDiffer);
                }
                free((LRLToken*)elemcount->kind.scalar.token);
                free(elemcount);
            }
            
            for (i = 0; i < expr->kind.exprlist.num_args; i++) {
                LRLTypeRef tr;
                tr.quals = LRL_Qual_Const|LRL_Qual_Mine;
                tr.prm = realtarget.prm;
                tr.type = realtarget.type->kind.array.type;
                verify_expr(ctx, expr->kind.exprlist.values[i], &tr, newflags);
            }
            break; }
        case LRL_AST_Value_Struct: {
            size_t i;
            LRLASTDefList *defentry;
            
            if (realtarget.type->ast_type != LRL_AST_Type_Struct) {
                lrl_err_set_expr(ctx, expr, 0);
                lrl_err_set_type(ctx, target.type, 1);
                lrl_err_finish(ctx, LRL_Err_TargetIsNotStructType);
                break;
            }
            
            /* TODO implement union values also, e.g. with this syntax:
                       union(.a=x)
                    this syntax is mainly useful in e.g. function arguments */
            
            defentry = realtarget.type->kind.struc.members;
            for (i = 0; i < expr->kind.exprlist.num_args; i++) {
                LRLASTExpr *valueexpr = expr->kind.exprlist.values[i];
                
                /* TODO named members (.x=0, .y=1) */
                
                if (!defentry) {
                    lrl_err_expr(ctx, LRL_Err_TooManyStructElems,
                                 valueexpr ? valueexpr : expr);
                    break;
                }
                
                if (valueexpr) {
                    LRLTypeRef tr;
                    tr.quals = LRL_Qual_Const|LRL_Qual_Mine;
                    tr.prm = realtarget.prm;
                    tr.type = defentry->def.kind.data.type;
                    verify_expr(ctx, valueexpr, &tr, newflags);
                }
                
                defentry = defentry->next;
            }
            
            if (defentry) {
                lrl_err_expr(ctx, LRL_Err_TooFewStructElems, expr);
                break;
            }
            
            break; }
        LRL_case_except_ast_exprs_values default:
            fail("vfyexpr_switch");
            break;
    }
}

static int is_alias_typedef(const LRLASTDefOrStmt *defnode)
{
    return defnode->def.kind.type.flags & LRL_DeFl_Alias;
}

/**
 * Static equality check of two expressions. Returns 1 if equal.
 *
 * TODO perhaps this should use the constexpr system?
 */
static int exprs_equal(LRLCtx *ctx, LRLASTExpr *a, LRLASTExpr *b)
{
    if (lrl_constexpr_expr_is_evaluatable(ctx, a) == -1 ||
        lrl_constexpr_expr_is_evaluatable(ctx, b) == -1) {
        /* Assume yes for now due to unbound identifiers */
        return 1;
    }

    while (a->ast_type == LRL_AST_Expr_Evaluated) {
        a = a->kind.evaluated.evaluated;
    }
    while (b->ast_type == LRL_AST_Expr_Evaluated) {
        b = b->kind.evaluated.evaluated;
    }

    if (a->ast_type != b->ast_type) return 0;
    
    switch (a->ast_type) {
        case LRL_AST_Value_TypeIdent:
            /* TODO implement type idents */
            fail("vfyexprsequal_typeidentnotimpl");
        case LRL_AST_Value_Ident: {
            LRLIdentRef *aref = &a->kind.ident.identref;
            LRLIdentRef *bref = &b->kind.ident.identref;
            
            if (a->kind.ident.type_params ||
                b->kind.ident.type_params)
                break; /* must be an unparametricized identifier */
            
            /* Ensure idents are dereferenced */
            if (lrl_identref_queue(ctx, aref) || lrl_identref_queue(ctx, bref))
                return 1; /* can't check without idents */
            
            return aref->ident == bref->ident; }
        case LRL_AST_Value_Scalar: {
            const LRLToken *atok = a->kind.scalar.token;
            const LRLToken *btok = b->kind.scalar.token;
            if (atok->type != btok->type) return 0;
            if (atok->type == LRL_TT_Integer) {
                /* TODO integers can have leading zeros */
                if (atok->loc.length != btok->loc.length) return 0;
                return memcmp(atok->loc.start, btok->loc.start, atok->loc.length) == 0;
            }
            break; }
        case LRL_AST_Value_None:
        case LRL_AST_Value_NaN:
        case LRL_AST_Value_Inf:
            return 1;
        case LRL_AST_Expr_ArrayIndex:
            return exprs_equal(ctx, a->kind.index.array, b->kind.index.array) &&
                   exprs_equal(ctx, a->kind.index.index, b->kind.index.index);
        case LRL_AST_Expr_Member:
            break; /* TODO */
            /*return exprs_equal(ctx, a->struc, b->struc);*/
        case LRL_AST_Expr_As:
            break; /* TODO */
            /*return exprs_equal(ctx, a->expr, b->expr); */
        case LRL_AST_Expr_TypeAssert:
            break; /* TODO */
            /*return exprs_equal(ctx, a->expr, b->expr); */
        case LRL_AST_Expr_UnaryOp:
            return exprs_equal(ctx, a->kind.unary_op.operand, b->kind.unary_op.operand);
        case LRL_AST_Expr_BinaryOp:
            return exprs_equal(ctx, a->kind.binary_op.operand1, b->kind.binary_op.operand1) &&
                   exprs_equal(ctx, a->kind.binary_op.operand2, b->kind.binary_op.operand2);
        case LRL_AST_Expr_Conditional:
            return exprs_equal(ctx, a->kind.conditional.condexpr, b->kind.conditional.condexpr) &&
                   exprs_equal(ctx, a->kind.conditional.trueexpr, b->kind.conditional.trueexpr) &&
                   exprs_equal(ctx, a->kind.conditional.falseexpr, b->kind.conditional.falseexpr);
        case LRL_AST_Value_Struct:
        case LRL_AST_Value_Array:
            /* TODO implement */
            break;
        case LRL_AST_Value_Undefined:
        case LRL_AST_Expr_FuncMember:
        case LRL_AST_Expr_Call:
            /* These cannot be compared */
            break;
        case LRL_AST_Expr_Evaluated: /* Handled above */
        LRL_case_except_ast_exprs_values default:
            fail("vfyexprequal_switch");
    }
    
    lrl_err_set_expr(ctx, a, 0);
    lrl_err_set_expr(ctx, b, 1);
    lrl_err_finish(ctx, LRL_Err_CantCompareExprsStatically);
    return 0;
}

/**
 * Returns 1 if the type parameter lists are equal.
 * The base type should have been checked before calling this function.
 */
static int compare_type_params(LRLCtx *ctx,
                       const LRLASTTypeList *a, LRLBoundParams *a_prm,
                       const LRLASTTypeList *b, LRLBoundParams *b_prm,
                       const LRLASTExpr *error_expr)
{
    while (a && b) {
        LRLTypeRef atr = typeref_root(a->type, 0);
        LRLTypeRef btr = typeref_root(b->type, 0);
        if (!a->type || !b->type) return 0;
        lrl_vfy_substitute_type_params(&atr.type, a_prm);
        lrl_vfy_substitute_type_params(&btr.type, b_prm);
        
        if (!lrl_vfy_type_compat(ctx, &atr, &btr, error_expr,
                                 LRL_TCF_RequireEqual)) {
            lrl_err_set_expr(ctx, error_expr, 0);
            lrl_err_set_type(ctx, atr.type, 1);
            lrl_err_set_type(ctx, btr.type, 2);
            lrl_err_finish(ctx, LRL_Err_TypeParametersDiffer);
            return 0;
        }
        a = a->next;
        b = b->next;
    }
    
    if (!a || !b) {
        /* One of the types must have the wrong number of parameters.
           An error should have been reported earler. */
        return 0;
    }
    
    return 1;
}

/**
 * Recursively checks whether <from_ref> can be assigned to <to_ref>.
 *
 * If flags include LRL_TCF_RequireEqual then the types must be equal,
 * otherwise it's enough if from_ref can be assigned to to_ref. Equal
 * comparisons are used for pointer types etc.
 *
 * FIXME assignment of pointers should be made more strict, to allow for
 * strict-aliasing optimizations (and also to prevent bugs)
 */
int lrl_vfy_type_compat(LRLCtx *ctx,
                        const LRLTypeRef *to_ref, const LRLTypeRef *from_ref,
                        const LRLASTExpr *error_expr, LRLTypeCompatFlags flags)
{
    LRLTypeRef to = *to_ref;
    LRLTypeRef from = *from_ref;
    LRLErrorType err;
    if (!error_expr) fail("vfytypecompat_errexpr_null");

  retry:
    if (!from.type || !to.type) return 1;
    
    /* Check identity */
    if (from.type == to.type &&
        from.type->ast_type != LRL_AST_Type_Parametric) return 1;
    
    /* Compare types with types params */
    if (lrl_vfy_substitute_type_params(&from.type, from.prm) | /* run both */
        lrl_vfy_substitute_type_params(&to.type, to.prm)) {
        /* Retry with modified args */
        goto retry;
    }
    
    /* TODO check qualifiers */
    
    if (to.type->ast_type == LRL_AST_Type_Ident &&
        from.type->ast_type == LRL_AST_Type_Ident &&
        (flags & LRL_TCF_IsTypeAssert) == 0) {
        /* Named types are compared by place of definition
           (i.e. name compatibility) */
        const LRLASTDefOrStmt *fromdef, *todef;
        
        fromdef = get_def_node(from.type->kind.identref.ident);
        todef = get_def_node(to.type->kind.identref.ident);
        
        if (!fromdef || !is_typedef(fromdef) ||
            !todef || !is_typedef(todef)) {
            return 1; /* earlier error */
        }
        
        if (fromdef == todef) return 1;
        
        /* Dereference aliases */
        if (is_alias_typedef(fromdef)) {
            from = typeref_nested(fromdef->def.kind.type.type, &from);
            goto retry;
        }
        if (is_alias_typedef(todef)) {
            to = typeref_nested(todef->def.kind.type.type, &to);
            goto retry;
        }
        
        err = LRL_Err_NamedTypesMustBeSame;
        goto mismatch;
    }
    
    /* Else, check structural compatiblity */
    
    /* Dereference the identifier type */
    while (from.type->ast_type == LRL_AST_Type_Ident) {
        const LRLASTDefOrStmt *defnode = get_def_node(from.type->kind.identref.ident);
        if (!defnode || !is_typedef(defnode)) return 1;
        from = typeref_nested(defnode->def.kind.type.type, &from);
        if (!from.type) return 1;
        lrl_vfy_substitute_type_params(&from.type, from.prm);
    }
    
    while (to.type->ast_type == LRL_AST_Type_Ident) {
        const LRLASTDefOrStmt *defnode = get_def_node(to.type->kind.identref.ident);
        if (!defnode || !is_typedef(defnode)) return 1;
        to = typeref_nested(defnode->def.kind.type.type, &to);
        if (!to.type) return 1;
        lrl_vfy_substitute_type_params(&to.type, to.prm);
    }
    
    /* 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) */
    if (from.type->ast_type == LRL_AST_Type_Parametric &&
        to.type->ast_type == LRL_AST_Type_Parametric &&
        (flags & LRL_TCF_IsTypeAssert) == 0) {
        const LRLTypeRef frombase = typeref_nested(from.type->kind.parametric.type, &from);
        const LRLTypeRef tobase = typeref_nested(to.type->kind.parametric.type, &to);
        if (lrl_vfy_type_compat(ctx, &frombase, &tobase, error_expr, 0)) {
            /* Require type parameters to be of equal types */
            return compare_type_params(ctx,
                        from.type->kind.parametric.params, from.prm,
                        to.type->kind.parametric.params, to.prm, error_expr);
        }
    }
    
    /* Bind type params in e.g. map[int,int] */
    if (lrl_vfy_bind_type_params(&from.type, &from.prm) | /* run both */
        lrl_vfy_bind_type_params(&to.type, &to.prm)) {
        /* Retry with modified args */
        goto retry;
    }
    
    /* "any" type is compatible with all other types */
    if (from.type->ast_type == LRL_AST_Type_Any ||
        to.type->ast_type == LRL_AST_Type_Any) return 1;
    
    /* Pointers can be assigned to optional pointers */
    if (from.type->ast_type == LRL_AST_Type_Pointer && is_optional_pointer(to.type)) {
        to = typeref_nested(to.type->kind.optional.type, &to);
        goto retry;
    }
    
    /* Optional pointers can be assigned to raw pointers also */
    if (is_optional_pointer(from.type) && is_raw_pointer(to.type)) {
        from = typeref_nested(from.type->kind.optional.type, &from);
        goto retry;
    }
    
    /* Comparisons are symmetric, so any operation that is allowed from->to
       is also allowed to->from. */
    if (flags & LRL_TCF_Symmetric) {
        if (to.type->ast_type == LRL_AST_Type_Pointer && is_optional_pointer(from.type)) {
            from = typeref_nested(from.type->kind.optional.type, &from);
            goto retry;
        }
        if (is_optional_pointer(to.type) && is_raw_pointer(from.type)) {
            to = typeref_nested(to.type->kind.optional.type, &to);
            goto retry;
        }
    }

    if (from.type->ast_type != to.type->ast_type) {
        err = LRL_Err_NotStructurallyCompatibleTypes;
        goto mismatch;
    }
    
    /* TODO check qualifiers of nested types */
    switch (from.type->ast_type) {
        case LRL_AST_Type_Array: {
            LRLTypeRef to_arr, from_arr;
            LRLASTExpr *to_length, *from_length;
            
            to_arr.quals = to.quals;
            to_arr.prm = to.prm;
            to_arr.type = to.type->kind.array.type;
            from_arr.quals = from.quals;
            from_arr.prm = from.prm;
            from_arr.type = from.type->kind.array.type;
            if (!lrl_vfy_type_compat(ctx, &to_arr, &from_arr, error_expr,
                                     LRL_TCF_RequireEqual)) {
                return 0;
            }
            
            /* TODO need expr parameters */
            
            to_length = to.type->kind.array.length;
            from_length = from.type->kind.array.length;
            if (!to_length || !from_length) return 1;
            
            if (to_length->ast_type == LRL_AST_Value_Undefined ||
                from_length->ast_type == LRL_AST_Value_Undefined) {
                /* TODO optionally generate runtime check here? */
                break;
            }
            
            if (!exprs_equal(ctx, from_length, to_length)) {
                err = LRL_Err_ArrayLengthsDiffer;
                goto mismatch;
            }
            break; }
        case LRL_AST_Type_Builtin: {
            LRLBuiltinType to_bt = to.type->kind.builtin;
            LRLBuiltinType from_bt = from.type->kind.builtin;
            
            /* byte/char <--> int8/uint8 is allowed, even though the ranges differ.
               This is also allowed in pointers. While this is very useful,
               it adds a small hole in the type system, since it's possible to
               make an int8^ point to a uint8 and vice versa.
               Casts between byte and char require an explicit "as"
               expression via int8/uint8. */
            /* TODO or add a string[] / string[5] type  */
            int to_byte = (to_bt == LRL_BT_byte || to_bt == LRL_BT_char);
            int from_byte = (from_bt == LRL_BT_byte || from_bt == LRL_BT_char);
            if ((to_byte && (
                 from_bt == LRL_BT_int8 || from_bt == LRL_BT_uint8)) ||
                (from_byte && (
                 to_bt == LRL_BT_int8 || to_bt == LRL_BT_uint8))) break;
            
            if (flags & LRL_TCF_RequireEqual) {
                if (to_bt != from_bt) {
                    err = LRL_Err_TargetTypeIsNotEqual;
                    goto mismatch;
                }
            } else if (flags & (LRL_TCF_IsTypeAssert|LRL_TCF_Symmetric)) {
                /* Any numeric type may be converted into any
                   other numeric type */
                if (to_bt != from_bt &&
                    (to_bt == LRL_BT_bool || from_bt == LRL_BT_bool)) {
                    err = LRL_Err_NotStructurallyCompatibleTypes;
                    goto mismatch;
                }
            } else {
                if (!lrl_builtin_target_is_superset(to_bt, from_bt)) {
                    err = LRL_Err_TargetTypeIsNotSuperset;
                    goto mismatch;
                }
            }
            break; }
        case LRL_AST_Type_Enum:
        case LRL_AST_Type_Bitfield: {
            LRLTypeRef frombase, tobase;
            /* Check values */
            LRLASTDefList *toentry = to.type->kind.enu.values;
            LRLASTDefList *fromentry = from.type->kind.enu.values;
            while (toentry && fromentry) {
                LRLASTExpr *to_value, *from_value;
                
                /* Check names */
                const LRLIdent *toident = toentry->def.kind.data.ident;
                const LRLIdent *fromident = fromentry->def.kind.data.ident;
                if (toident && fromident) {
                    if (!lrl_ident_names_equal(toident, fromident)) {
                        err = LRL_Err_EnumTypeNamesDiffer;
                        goto mismatch;
                    }
                }
                
                /* Check values */
                to_value = toentry->def.kind.data.value;
                from_value = fromentry->def.kind.data.value;
                if (!exprs_equal(ctx, from_value, to_value)) {
                    err = LRL_Err_EnumTypeValuesDiffer;
                    goto mismatch;
                }
                
                toentry = toentry->next;
                fromentry = fromentry->next;
            }
            
            if (fromentry) {
                err = LRL_Err_EnumTypeWithFewerValues;
                goto mismatch;
            }
            if (toentry && (flags & LRL_TCF_RequireEqual)) {
                err = LRL_Err_EnumTypesNotEqual;
                goto mismatch;
            }
            
            /* Check base type */
            frombase = typeref_nested(from.type->kind.enu.base_type, &from);
            tobase = typeref_nested(to.type->kind.enu.base_type, &to);
            if (!lrl_vfy_type_compat(ctx, &tobase, &frombase,
                                     error_expr, flags)) {
                return 0;
            }
            break; }
        case LRL_AST_Type_Function: {
            LRLTypeRef to_args = make_typeref(0, to.prm, to.type->kind.function.args),
                       from_args = make_typeref(0, from.prm, from.type->kind.function.args),
                       to_ret = make_typeref(0, to.prm, to.type->kind.function.ret),
                       from_ret = make_typeref(0, from.prm, from.type->kind.function.ret);
            
            if (!lrl_vfy_type_compat(ctx, &to_args, &from_args, error_expr, 0) ||
                !lrl_vfy_type_compat(ctx, &from_ret, &to_ret, error_expr, 0)) {
                return 0;
            }
            break; }
        case LRL_AST_Type_Optional: {
            LRLTypeRef to_opt = typeref_nested(to.type->kind.optional.type, &to),
                       from_opt = typeref_nested(from.type->kind.optional.type, &from);
            
            if (!lrl_vfy_type_compat(ctx, &to_opt, &from_opt, error_expr,
                                     flags)) {
                return 0;
            }
            break; }
        case LRL_AST_Type_Pointer: {
            const LRLASTTypePointer *to_ptr = &to.type->kind.pointer,
                                    *from_ptr = &from.type->kind.pointer;
            LRLTypeRef to_target = make_typeref(0, to.prm, to_ptr->type),
                       from_target = make_typeref(0, from.prm, from_ptr->type);
            /* Pointers must match exactly, except when being dereferenced */
            LRLPointerFlags either = to_ptr->flags | from_ptr->flags;
            LRLTypeCompatFlags compatflags = (
                (either & LRL_InternPF_Dereferenced) == 0 ?
                LRL_TCF_RequireEqual : 0);

            if (!lrl_vfy_type_compat(ctx, &to_target, &from_target, error_expr,
                                     compatflags)) {
                return 0;
            }
            break; }
        case LRL_AST_Type_Private:
            /* Nothing is known about private types => Not allowed */
            err = LRL_Err_PrivateTypesAreNotCompatible;
            goto mismatch;
        case LRL_AST_Type_Any:
            /* Compatible with everything */
            return 1;
        case LRL_AST_Type_Struct:
        case LRL_AST_Type_Union: {
            LRLASTDefList *toentry = to.type->kind.struc.members;
            LRLASTDefList *fromentry = from.type->kind.struc.members;
            while (toentry && fromentry) {
                const LRLIdent *toident, *fromident;
                
                /* Check member types */
                LRLTypeRef to_mbr = typeref_nested(toentry->def.kind.data.type, &to),
                           from_mbr = typeref_nested(fromentry->def.kind.data.type, &from);
                
                if (!lrl_vfy_type_compat(ctx, &to_mbr, &from_mbr,
                                         error_expr, LRL_TCF_RequireEqual)) {
                    return 0;
                }
                
                /* Check names */
                toident = toentry->def.kind.data.ident;
                fromident = fromentry->def.kind.data.ident;
                if (toident && fromident) {
                    if (!lrl_ident_names_equal(toident, fromident)) {
                        err = LRL_Err_MembersNamesDiffer;
                        goto mismatch;
                    }
                }
                
                toentry = toentry->next;
                fromentry = fromentry->next;
            }
            if (toentry || fromentry) {
                err = LRL_Err_MemberCountDiffers;
                goto mismatch;
            }
            break; }
        /* These types are handled specially above */
        case LRL_AST_Type_Ident:
        case LRL_AST_Type_Parametric:
            /* TODO what to do in this case? */
            break;
        LRL_case_except_ast_types default:
            fail("vfytypecompat_switch");
    }
    
    return 1;
    
  mismatch:
    lrl_err_set_expr(ctx, error_expr, 0);
    lrl_err_set_type(ctx, from.type, 1);
    lrl_err_set_type(ctx, to.type, 2);
    lrl_err_finish(ctx, err);
    return 0;
}

/**
 * Determines the type of an expression, if possible, and assigns it
 * to the type of the expression. Type determination is only possible with
 * expressions that do not depend on the type of the containing expression.
 *
 * The type determined by this function takes precedence over the type
 * determined by verify_expr().
 */
static LRLTypeRef determine_expr_type(LRLCtx *ctx, LRLASTExpr *expr,
                                      const LRLTypeRef *typescope,
                                      int show_error)
{
    LRLErrorType err;
    if (!expr) goto returnnull;
    
    switch (expr->ast_type) {
        case LRL_AST_Expr_Call: {
            /* Use function return type */
            LRLTypeRef functyperef;
            if (!expr->kind.call.function) goto returnnull;
            if (expr->kind.call.function->ast_type == LRL_AST_Expr_FuncMember) {
                /* Call to a member function (with implicit "this" pointer) */
                functyperef = get_funcmember_type(ctx, expr, typescope);
            } else {
                /* Call to a regular function */
                functyperef = determine_expr_type(ctx,
                                                  expr->kind.call.function,
                                                  typescope, show_error);
                if (functyperef.type) {
                    expr->kind.call.function->typeref = functyperef;
                }
            }
            functyperef = lrl_vfy_find_real_typeref(&functyperef);
            if (!functyperef.type) goto returnnull;
            if (functyperef.type->ast_type != LRL_AST_Type_Function) {
                err = LRL_Err_ExpressionIsNotCallable;
                goto error;
            }
            
            return typeref_nested(functyperef.type->kind.function.ret, &functyperef); }
        case LRL_AST_Expr_UnaryOp: {
            LRLASTExpr *operand = expr->kind.unary_op.operand;
            switch (expr->kind.unary_op.token_type) {
                case LRL_Op_AddrOf: {
                    LRLASTType *type;
                    LRLTypeRef ptrtarget;
                    
                    ptrtarget = determine_expr_type(ctx, operand, typescope,
                                                    show_error);
                    if (!ptrtarget.type) goto returnnull;
                    
                    /* Wrap inner type in a pointer type */
                    type = malloc(sizeof(LRLASTType)); /* memleak */
                    type->ast_type = LRL_AST_Type_Pointer;
                    type->kind.pointer.type = (LRLASTType*)ptrtarget.type;
                    type->kind.pointer.flags = 0;
                    type->from = expr->from;
                    type->to = expr->to;
                    type->quals = LRL_Qual_Const|LRL_Qual_Mine;
                    type->unique_id = 0;
                    
                    return make_typeref(LRL_Qual_Const, ptrtarget.prm, type); }
                case LRL_Op_Deref: {
                    /* Return what the pointer type points to */
                    LRLTypeRef typeref = determine_expr_type(ctx, operand,
                                                  typescope, show_error);
                    typeref = lrl_vfy_find_real_typeref(&typeref);
                    if (!typeref.type) goto returnnull;
                    if (typeref.type->ast_type != LRL_AST_Type_Pointer) {
                        err = LRL_Err_ExpectedPointerExpr;
                        goto error;
                    }
                    
                    return typeref_nested(typeref.type->kind.pointer.type,
                                          &typeref); }
                case LRL_Op_EnumBase: {
                    LRLTypeRef typeref = determine_expr_type(ctx, operand,
                                                    typescope, show_error);
                    if (!typeref.type) goto returnnull;
                    if (typeref.type->ast_type != LRL_AST_Type_Enum) {
                        err = LRL_Err_ExpectedEnumExpr;
                        goto error;
                    }
                    
                    return make_typeref(LRL_Qual_Const, typeref.prm,
                                        typeref.type->kind.enu.base_type); }
                case LRL_Op_MakeOpt: {
                    LRLASTType *type;
                    LRLTypeRef valuetype;
                    
                    valuetype = determine_expr_type(ctx, operand,
                                                    typescope, show_error);
                    if (!valuetype.type) goto returnnull;
                    
                    /* Wrap inner type in an optional type */
                    type = malloc(sizeof(LRLASTType)); /* memleak */
                    type->ast_type = LRL_AST_Type_Optional;
                    type->kind.optional.type = (LRLASTType*)valuetype.type;
                    type->from = expr->from;
                    type->to = expr->to;
                    type->quals = LRL_Qual_Const|LRL_Qual_Mine;
                    type->unique_id = 0;
                    
                    return make_typeref(LRL_Qual_Const, valuetype.prm, type); }
                case LRL_Op_OptionalValue: {
                    /* Return the value */
                    LRLTypeRef typeref = determine_expr_type(ctx, operand,
                                                  typescope, show_error);
                    typeref = lrl_vfy_find_real_typeref(&typeref);
                    if (!typeref.type) goto returnnull;
                    if (typeref.type->ast_type != LRL_AST_Type_Optional) {
                        err = LRL_Err_ExpectedOptionalExpr;
                        goto error;
                    }
                    
                    return typeref_nested(typeref.type->kind.optional.type,
                                          &typeref); }
                case LRL_Op_LNot:
                    return ctx->bool_tr;
                case LRL_Op_Plus:
                case LRL_Op_Minus:
                    if (!operand) goto returnnull;
                    if (operand->ast_type == LRL_AST_Value_Scalar) {
                        /* Special handling of literals such as -9 or +5 */
                        return determine_expr_type(ctx, operand,
                                                   typescope, show_error);
                    }
                    /* Fall through */
                case LRL_Op_Compl: /* TODO could be the same type */
                case LRL_Op_SizeOf: /* TODO all these could be <count> */
                case LRL_Op_MinSizeOf:
                case LRL_Op_OffsetOf:
                case LRL_Op_AlignOf:
                    goto ambiguous;
                LRL_case_except_tt_unops default:
                    fail("vfydetexpr_unop_switch");
            }
            break; }
        case LRL_AST_Expr_BinaryOp:
            switch (expr->kind.binary_op.token_type) {
                /* The type of a=b is that of the left operand */
                case LRL_Op_Assign:
                case LRL_Op_PlusAssign:
                case LRL_Op_MinusAssign:
                case LRL_Op_TimesAssign:
                case LRL_Op_DivideAssign:
                case LRL_Op_ShiftLAssign:
                case LRL_Op_ShiftRAssign:
                /* The type of "x mod y" is also that of the left operand.
                   There's never any loss of precision in the y value; if y
                   is larger than the maximum value of the type of x, then
                   the expression simply yields the value of x. */
                case LRL_Op_Modulo:
                    return determine_expr_type(ctx,
                                               expr->kind.binary_op.operand1,
                                               typescope, show_error);
                case LRL_Op_LAnd:
                case LRL_Op_LOr:
                case LRL_Op_LXor:
                case LRL_Op_Equal:
                case LRL_Op_NotEqual:
                case LRL_Op_Less:
                case LRL_Op_LessEqual:
                case LRL_Op_Greater:
                case LRL_Op_GreaterEqual:
                    return ctx->bool_tr;
                case LRL_Op_Plus:
                case LRL_Op_Minus:
                case LRL_Op_Times:
                case LRL_Op_Divide:
                case LRL_Op_ShiftL:
                case LRL_Op_ShiftR:
                case LRL_Op_BitAnd:
                case LRL_Op_BitXor:
                case LRL_Op_BitOr:
                    goto ambiguous;
                LRL_case_except_tt_binops default:
                    fail("vfydetexpr_binop_switch");
            }
            break;
        case LRL_AST_Expr_ArrayIndex: {
            /* Return element type */
            LRLTypeRef typeref = determine_expr_type(ctx,
                                                expr->kind.index.array,
                                                typescope, show_error);
            typeref = lrl_vfy_find_real_typeref(&typeref);
            if (!typeref.type) goto returnnull;
            if (typeref.type->ast_type != LRL_AST_Type_Array) {
                err = LRL_Err_ExpectedArrayExpr;
                goto error;
            }
            
            return typeref_nested(typeref.type->kind.array.type, &typeref); }
        case LRL_AST_Expr_Member:
            /* Return type from member declaration in struct */
            return get_member_type(ctx, expr, typescope);
        case LRL_AST_Expr_FuncMember:
            err = LRL_Err_FunctionMembersAreNotValues;
            goto error;
        case LRL_AST_Expr_As:
            verify_type(ctx, expr->kind.asexpr.type, NULL, NULL);
            return typeref_root(expr->kind.asexpr.type, LRL_Qual_Var|LRL_Qual_Mine);
        case LRL_AST_Expr_TypeAssert:
            verify_type(ctx, expr->kind.typeassert.type, NULL, NULL);
            return typeref_root(expr->kind.typeassert.type, LRL_Qual_Var|LRL_Qual_Mine);
        case LRL_AST_Expr_Evaluated:
            determine_expr_type(ctx, expr->kind.evaluated.original, typescope,
                                show_error);
            break;
        case LRL_AST_Value_TypeIdent:
            if (!typescope) {
                if (show_error) {
                    lrl_err_expr(ctx, LRL_Err_TypeIdentMakesNoSense, expr);
                }
                goto returnnull;
            }
            if (!expr->kind.ident.identref.scope) {
                /* Not already deferred */
                expr->kind.ident.identref.scope = get_type_scope(ctx,
                                       typescope, show_error ? expr : NULL);
                if (!expr->kind.ident.identref.scope) goto returnnull;
            }
            /* Fall through */
        case LRL_AST_Value_Ident: {
            LRLIdentRef *identref = &expr->kind.ident.identref;
            if (!lrl_identref_queue(ctx, identref)) {
                LRLASTDefOrStmt *defref = get_def_node(identref->ident);
                
                if (!defref) {
                    err = LRL_Err_IdentIsNotValue;
                    goto error;
                } else if (defref->ast_type == LRL_AST_Def_Data) {
                    return typeref_root(defref->def.kind.data.type, LRL_Qual_Const);
                } else if (defref->ast_type == LRL_AST_Def_Function) {
                    LRLBoundParams *prm = NULL;
                    bind_type_params_list(defref->def.kind.function.typenames,
                                          expr->kind.ident.type_params, &prm);
                    
                    return make_typeref(0, prm, &defref->def.kind.function.type);
                } else if (defref->ast_type == LRL_AST_Stmt_Decl) {
                    return typeref_root(defref->def.kind.data.type, LRL_Qual_Const);
                } else {
                    err = LRL_Err_IdentIsNotValue;
                    goto error;
                }
            }
            break; }
        case LRL_AST_Value_Undefined:
            /* A statement that should never be reached */
            break;
        case LRL_AST_Value_Scalar:
            return typeref_root(
                determine_literal_expr_type(ctx, expr, NULL, show_error),
                LRL_Qual_Const|LRL_Qual_Mine);
        /* TODO type parameter expressions */
        case LRL_AST_Expr_Conditional:
        case LRL_AST_Value_None:
        case LRL_AST_Value_NaN:
        case LRL_AST_Value_Inf:
        case LRL_AST_Value_Struct:
        case LRL_AST_Value_Array:
            goto ambiguous;
        LRL_case_except_ast_exprs_values default:
            fail("vfydetexpr_switch");
    }
    goto returnnull;
    
  ambiguous:
    err = LRL_Err_AmbiguousStmtType;
  error:
    if (show_error) {
        lrl_err_expr(ctx, err, expr);
    }
  returnnull:
    return make_typeref(0, NULL, NULL);
}

static const LRLToken tok_get_iterator[2] = {
    { LRL_TT_Ident, { "get_iterator", 12 } },
    { LRL_TT_EOF, LRL_NULL_LOCATION }
};
static const LRLToken tok_next_element[2] = {
    { LRL_TT_Ident, { "next_element", 12 } },
    { LRL_TT_EOF, LRL_NULL_LOCATION }
};

static void verify_statement(LRLCtx *ctx, LRLASTStmt *stmt)
{
    if (!stmt) return;
    
    switch (stmt->ast_type) {
        case LRL_AST_Stmt_Compound: {
            LRLASTStmtList *entry;
            for (entry = stmt->kind.compound; entry; entry = entry->next) {
                verify_statement(ctx, entry->statement);
            }
            break; }
        case LRL_AST_Stmt_Decl:
            /* Check type and initialization expression */
            verify_def_data(ctx, &stmt->kind.data);
            /* TODO check for "suspicious" identifier hiding?
                    or check for all kinds of identifiers? */
            break;
        case LRL_AST_Stmt_Expr: {
            LRLTypeRef root_tr;
            if (!stmt->kind.expr) break;
            
            root_tr = determine_expr_type(ctx, stmt->kind.expr, NULL, 1);
            if (root_tr.type) {
                verify_expr(ctx, stmt->kind.expr, &root_tr, StatementLevel);
            }
            break; }
        case LRL_AST_Stmt_DefType:
            /* Check type definition */
            verify_def_type(ctx, &stmt->kind.deftype);
            /* TODO check for "suspicious" identifier hiding? */
            break;
        case LRL_AST_Stmt_Break:
        case LRL_AST_Stmt_Continue:
            /* Verified in parser. Nothing to check here. */
            break;
        case LRL_AST_Stmt_Goto:
        case LRL_AST_Stmt_SkipTo:
        case LRL_AST_Stmt_RepeatFrom: {
            LRLASTDefOrStmt *defref;
            LRLIdentRef *identref = &stmt->kind.gotostm.identref;
            
            if (lrl_identref_queue(ctx, identref))
                break;
            
            defref = get_def_node(identref->ident);
            if (defref && defref->ast_type != LRL_AST_Stmt_Label)  {
                lrl_err_set_ident(ctx, identref->first_token, 0);
                if (identref->ident->def_token) {
                    lrl_err_set_ident(ctx, identref->ident->def_token, 1);
                }
                lrl_err_finish(ctx, LRL_Err_IdentIsNotGotoLabel);
                break;
            }
            
            /* TODO Check that the right keyword is used and that a "for" loop block or "typeassert" is not jumped into */
            break; }
        case LRL_AST_Stmt_Label:
            /* TODO Warn about variable definitions before the label if the variables are used. The check can be done somewhere else */
            break;
        case LRL_AST_Stmt_If:
            verify_expr(ctx, stmt->kind.ifstm.boolexpr, &ctx->bool_tr, 0);
            
            verify_statement(ctx, stmt->kind.ifstm.body_true);
            if (stmt->kind.ifstm.body_false) {
                verify_statement(ctx, stmt->kind.ifstm.body_false);
            }
            break;
        case LRL_AST_Stmt_Switch: {
            /* Check switch expression */
            LRLASTExpr *switchexpr = stmt->kind.switchstm.switchexpr;
            LRLTypeRef tr;
            size_t ci;
            
            tr = determine_expr_type(ctx, switchexpr, NULL, 1);
            if (tr.type) {
                verify_expr(ctx, switchexpr, &tr, 0);
            }
            
            /* TODO check for invalid types (private, incomplete types etc.) */
            /*real_tr = lrl_vfy_find_real_typeref(&switch_tr);*/
            
            /* Check cases */
            /* TODO we should check for duplicate expressions here! */
            for (ci = 0; ci < stmt->kind.switchstm.num_cases; ci++) {
                const LRLASTCase *casenode = &stmt->kind.switchstm.cases[ci];
                
                if (tr.type) {
                    size_t ei;
                    for (ei = 0; ei < casenode->num_matchvalues; ei++) {
                        LRLASTCaseMatch *match = &casenode->matchvalues[ei];
                        verifyeval_expr(ctx, &match->expr, &tr);
                        verify_statement(ctx, match->withstm);
                    }
                }
                
                verify_statement(ctx, casenode->stmt);
            }
            
            /* Default case */
            if (stmt->kind.switchstm.defaultstm) {
                verify_statement(ctx, stmt->kind.switchstm.defaultstm);
            }
            break; }
        case LRL_AST_Stmt_While:
        case LRL_AST_Stmt_DoWhile:
            verify_expr(ctx, stmt->kind.whilestm.boolexpr, &ctx->bool_tr, 0);
            
            verify_statement(ctx, stmt->kind.whilestm.body);
            break;
        case LRL_AST_Stmt_For: {
            LRLASTExpr *iterexpr;
            LRLTypeRef iter_tr, real_tr;
            
            /* Check element type */
            LRLTypeRef elem_tr;
            verify_def_data(ctx, &stmt->kind.forstm.valuedef.kind.data);
            elem_tr = typeref_root(stmt->kind.forstm.valuedef.kind.data.type,0);
            if (elem_tr.type) {
                if (elem_tr.type->quals & (LRL_Qual_Var | LRL_Qual_Shared)) {
                    lrl_err_type(ctx, LRL_Err_QualOnLoopVariable, elem_tr.type);
                }
            }
            
            /* Check iteration expression */
            iterexpr = stmt->kind.forstm.iterexpr;
            if (!iterexpr || !elem_tr.type) {
                /* Set type to NULL due to previous errors */
                memset(&iter_tr, 0, sizeof(iter_tr));
                memset(&real_tr, 0, sizeof(real_tr));
            } else if (iterexpr->ast_type == LRL_AST_Value_Array) {
                /* TODO support e.g. [[1,2], [2,3]]#[x] also */
                iter_tr = determine_array_type(ctx, iterexpr, &elem_tr);
                real_tr = iter_tr;
            } else {
                iter_tr = determine_expr_type(ctx, iterexpr, &elem_tr, 1);
                real_tr = lrl_vfy_find_real_typeref(&iter_tr);
            }
            if (real_tr.type) {
                const LRLASTType *iter_type = iter_tr.type;
                const LRLASTType *real_type = real_tr.type;
                LRLASTCtlForTemp *temp;

                verify_expr(ctx, iterexpr, &iter_tr, 0);
                
                /* Set up temporary data. Also used by the backend */
                if (stmt->kind.forstm.temp) {
                    temp = stmt->kind.forstm.temp;
                } else {
                    temp = calloc(1, sizeof(LRLASTCtlForTemp));
                    stmt->kind.forstm.temp = temp;
                }
                
                /*
                if the element type is T, then the iter expr type can be either:
                    - an array T#[]
                    - a type that has this function in it's namespace:
                        bool next_element(T this, var E^ result_element);
                    - a type that has an "get_iterator()" function that returns
                      a type that has the above function in it's namespace.
                      
                */
                if (iter_type->ast_type == LRL_AST_Type_Ident &&
                    real_type->ast_type == LRL_AST_Type_Struct) {
                    
                    LRLIdent *scope = (LRLIdent*)real_type->kind.struc.scope->scope;
                    
                    if (lrl_ident_valid(scope) && !temp->next_element_ident) {
                        temp->next_element_ident = lrl_ident_get(ctx, scope,
                            &tok_next_element[0], LRL_Ident_Find, NULL);
                    }
                    if (lrl_ident_valid(scope) && !temp->get_iterator_ident) {
                        temp->get_iterator_ident = lrl_ident_get(ctx, scope,
                            &tok_get_iterator[0], LRL_Ident_Find, NULL);
                    }
                }
                
                if (iter_type->ast_type == LRL_AST_Type_Ident &&
                   lrl_ident_valid(temp->next_element_ident)) {
                    /* Direct iteration with an iterator type */
                    temp->loop_type = LRL_AST_LT_DirectIter;
                    /* TODO check that get_iterator matches the interface */
                } else if (iter_type->ast_type == LRL_AST_Type_Ident &&
                      lrl_ident_valid(temp->get_iterator_ident)) {
                    /* Indirect iteration by first obtaining an iterator */
                    temp->loop_type = LRL_AST_LT_IndirectIter;
                    /* TODO check that get_iterator matches the interface */
                } else if (real_type->ast_type == LRL_AST_Type_Array) {
                    /* Iteration over an array */
                    LRLTypeRef array_tr = typeref_root(real_type->kind.array.type, 0);
                    lrl_vfy_type_compat(ctx, &elem_tr, &array_tr, iterexpr, 0);
                    
                    temp->loop_type = LRL_AST_LT_ArrayIter;
                    temp->length_expr = real_type->kind.array.length;
                } else {
                    /* Error */
                    lrl_err_set_expr(ctx, iterexpr, 0);
                    lrl_err_set_type(ctx, iter_type, 1);
                    lrl_err_finish(ctx, LRL_Err_TypeIsNotIterable);
                }
                
            }
            
            /* Check loop and end/empty body */
            verify_statement(ctx, stmt->kind.forstm.body);
            if (stmt->kind.forstm.body_end) {
                verify_statement(ctx, stmt->kind.forstm.body_end);
            }
            if (stmt->kind.forstm.body_empty) {
                verify_statement(ctx, stmt->kind.forstm.body_empty);
            }
            break; }
        case LRL_AST_Stmt_Return: {
            const LRLASTDefFunction *funcdef;
            const LRLASTType *rettype;
            LRLASTExpr *retexpr;
            LRLTypeRef ret_tr;
            
            /* Find current function */
            /* TODO optimize this */
            const LRLIdent *scope = &stmt->scope;
            for (;;) {
                if (!scope) fail("vfystmt_returnnoscope");
                if (scope->def_node &&
                    scope->def_node->ast_type == LRL_AST_Def_Function) break;
                
                scope = scope->scope;
            }
            
            /* Determine return type */
            funcdef = &scope->def_node->def.kind.function;
            rettype = funcdef->type.kind.function.ret;
            
            /* Check expr with return type */
            retexpr = stmt->kind.retstm.retexpr;
            if (!retexpr) {
                if (rettype && (rettype->ast_type != LRL_AST_Type_Struct ||
                        rettype->kind.struc.members)) {
                    lrl_err_set_token(ctx, stmt->token, 0);
                    lrl_err_set_token(ctx, scope->def_token, 1);
                    lrl_err_finish(ctx, LRL_Err_MustReturnAValue);
                    /* TODO do the same check at the end
                            of non-void functions */
                }
            } else {
                ret_tr = typeref_root(rettype, LRL_Qual_Var|LRL_Qual_Mine);
                verify_expr(ctx, retexpr, &ret_tr, 0);
            }
            break; }
        case LRL_AST_Stmt_Unreachable:
            /* TODO could check that there are no statements after this one */
            break;
        case LRL_AST_Stmt_TypeAssert: {
            /* Check assert statements */
            LRLTypeAssert *ta = stmt->kind.typeassertstm.asserts;
            for (; ta; ta = ta->next) {
                /* Source variable */
                LRLASTType *sourcetype = NULL;
                LRLIdentRef *identref = &ta->refexpr.kind.ident.identref;
                if (!lrl_identref_queue(ctx, identref)) {
                    LRLASTDefOrStmt *defref = get_def_node(identref->ident);
                    if (!defref) {
                        /* Ignore */
                    } else if (defref->ast_type == LRL_AST_Def_Data) {
                        sourcetype = defref->def.kind.data.type;
                    } else if (defref->ast_type == LRL_AST_Stmt_Decl) {
                        sourcetype = defref->stmt.kind.data.type;
                    } else {
                        lrl_err_set_ident(ctx, identref->first_token, 0);
                        lrl_err_finish(ctx, LRL_Err_IdentIsNotValue);
                    }
                }
                
                /* Target type */
                if (ta->def.ast_type != LRL_AST_Def_Data) {
                    fail("vfystmt_typeassert_notdefdata");
                }
                verify_type(ctx, ta->def.kind.data.type, NULL, NULL);
                
                if (sourcetype && ta->def.kind.data.type) {
                    LRLTypeRef fromtr, tatr;
                    fromtr = typeref_root(sourcetype,
                                          LRL_Qual_Var|LRL_Qual_Mine);
                    tatr = typeref_root(ta->def.kind.data.type,
                                        LRL_Qual_Var|LRL_Qual_Mine);
                    lrl_vfy_type_compat(ctx, &tatr, &fromtr, &ta->refexpr,
                                        LRL_TCF_IsTypeAssert);
                }
            }
            
            /* Check do and/or else bodies */
            if (stmt->kind.typeassertstm.body_do) {
                verify_statement(ctx, stmt->kind.typeassertstm.body_do);
            }
            if (stmt->kind.typeassertstm.body_else) {
                verify_statement(ctx, stmt->kind.typeassertstm.body_else);
            }
            break;
        }
        case LRL_AST_Stmt_Assert:
            verify_expr(ctx, stmt->kind.assertstm.boolexpr, &ctx->bool_tr, 0);
            /* TODO try to evaluate with constexpr and check if false?
               if we want to have something like "assert false;"
               then we could instead write "undefined;" */
            break;
        LRL_case_except_ast_stmts default:
            fail("vfystmt_switch");
    }
}