path: root/compiler/constexpr.c

/*

  constexpr.c -- Tries to evaluate expressions at compile-time

  Copyright © 2013-2016 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 <string.h>

#include "constexpr.h"
#include "misc.h"
#include "string.h"
#include "verify.h"
#include "context_private.h"

/* Do not evaluate broken or external data */
#define is_ident_ready(expr) ( \
    (expr)->typeref.type && \
    (expr)->kind.ident.identref.ident && \
    (expr)->kind.ident.identref.ident->def_node && \
    ((expr)->kind.ident.identref.ident->def_node->ast_type == LRL_AST_Def_Data || \
     (expr)->kind.ident.identref.ident->def_node->ast_type == LRL_AST_Stmt_Decl) && \
    (expr)->kind.ident.identref.ident->def_node->def.kind.data.value)
#define ident_has_initval(expr) ( \
    (expr)->kind.ident.identref.ident->def_node->def.kind.data.value->ast_type != LRL_AST_Value_Undefined)
#define normalize_asttype(asttype) ((asttype) == LRL_AST_Value_TypeIdent ? \
    LRL_AST_Value_Ident : (asttype))

static LRLASTExpr *constexpr_eval(LRLCtx *ctx, LRLASTExpr *expr);
static LRLASTExpr *eval_binary_op(LRLCtx *ctx, LRLASTExpr *expr);

/**
 * Returns 1 if the expr is compile-time constant, 0 if not, or -1 if
 * this can't be determined due to unbound identifiers.
 */
int lrl_constexpr_expr_is_evaluatable(LRLCtx *ctx, LRLASTExpr *expr)
{
    if (!expr) return 0;
    /* TODO which ops can be compile-time constant? */
    switch (expr->ast_type) {
        case LRL_AST_Expr_UnaryOp:
            switch (expr->kind.unary_op.token_type) {
                case LRL_Op_AddrOf:
                case LRL_Op_SizeOf:
                case LRL_Op_MinSizeOf:
                case LRL_Op_OffsetOf:
                case LRL_Op_AlignOf:
                    return 1;
                case LRL_Op_Plus:
                case LRL_Op_Minus:
                case LRL_Op_Deref:
                case LRL_Op_OptionalValue:
                case LRL_Op_EnumBase:
                case LRL_Op_MakeOpt:
                case LRL_Op_Compl:
                case LRL_Op_LNot:
                    return lrl_constexpr_expr_is_evaluatable(ctx, expr->kind.unary_op.operand);
                LRL_case_except_tt_unops default:
                    fail("constexpr_exprisconst_unop_switch");
            }
        case LRL_AST_Expr_BinaryOp: {
            int op1 = lrl_constexpr_expr_is_evaluatable(ctx, expr->kind.binary_op.operand1);
            int op2 = lrl_constexpr_expr_is_evaluatable(ctx, expr->kind.binary_op.operand2);
            if (op1 ==  0 || op2 ==  0) return  0;
            if (op1 == -1 || op2 == -1) return -1;
            return 1;
            }
        case LRL_AST_Expr_Conditional: {
            /* actually isn't it const if constexpr and the right true/false expr is const? */
            int cond = lrl_constexpr_expr_is_evaluatable(ctx, expr->kind.conditional.condexpr);
            int texpr = lrl_constexpr_expr_is_evaluatable(ctx, expr->kind.conditional.trueexpr);
            int fexpr = lrl_constexpr_expr_is_evaluatable(ctx, expr->kind.conditional.falseexpr);
            
            if (cond ==  0 || texpr ==  0 || fexpr ==  0) return  0;
            if (cond == -1 || texpr == -1 || fexpr == -1) return -1;
            return 1;
            }
        case LRL_AST_Expr_Call:
        case LRL_AST_Expr_FuncMember:
            return 0;
        case LRL_AST_Expr_Member:
            /* TODO check that the member in the struct is const also */
            return lrl_constexpr_expr_is_evaluatable(ctx, expr->kind.member.struc);
        case LRL_AST_Expr_As:
            return lrl_constexpr_expr_is_evaluatable(ctx, expr->kind.asexpr.expr);
        case LRL_AST_Expr_TypeAssert:
            return lrl_constexpr_expr_is_evaluatable(ctx, expr->kind.typeassert.expr);
        case LRL_AST_Expr_ArrayIndex: {
            int arrexpr = lrl_constexpr_expr_is_evaluatable(ctx, expr->kind.index.array);
            int indexpr = lrl_constexpr_expr_is_evaluatable(ctx, expr->kind.index.index);
            
            if (arrexpr ==  0 || indexpr ==  0) return  0;
            if (arrexpr == -1 || indexpr == -1) return -1;
            return 1;
            }
        case LRL_AST_Value_TypeIdent:
        case LRL_AST_Value_Ident: {
            const LRLIdent *ident;
            const LRLASTExpr *refexpr;
            if (lrl_identref_queue(ctx, &expr->kind.ident.identref)) return -1;
            if (!is_ident_ready(expr)) return -1;
            
            ident = expr->kind.ident.identref.ident;
            if (ident->flags & LRL_IdFl_EnumValue) return 1;
            if (!ident_has_initval(expr)) return 0;
            refexpr = ident->def_node->def.kind.data.value;
            return (refexpr->typeref.quals &
                        (LRL_Qual_Var|LRL_Qual_Shared)) == 0; }
        case LRL_AST_Value_None:
        case LRL_AST_Value_NaN:
        case LRL_AST_Value_Inf:
        case LRL_AST_Value_Undefined:
        case LRL_AST_Value_Scalar:
        case LRL_AST_Expr_Evaluated:
            return 1;
        case LRL_AST_Value_Array:
        case LRL_AST_Value_Struct: {
            /* compile-time constant if all elements are also compile-time constant */
            size_t i;
            for (i = 0; i < expr->kind.exprlist.num_args; i++) {
                LRLASTExpr *elem = expr->kind.exprlist.values[i];
                int status = lrl_constexpr_expr_is_evaluatable(ctx, elem);
                if (status <= 0) return status;
            }
            return 1; }
        LRL_case_except_ast_exprs_values default:
            fail("constexpr_exprisconst_switch");
            return -1;
    }
}

static int is_already_evaluated(LRLCtx *ctx, LRLASTExpr *expr)
{
    if (!expr) return -1;
    switch (expr->ast_type) {
        case LRL_AST_Expr_UnaryOp:
            switch (expr->kind.unary_op.token_type) {
                case LRL_Op_AddrOf:
                case LRL_Op_SizeOf:
                case LRL_Op_MinSizeOf:
                case LRL_Op_OffsetOf:
                case LRL_Op_AlignOf:
                    return 1;
                case LRL_Op_Minus:
                    if (!expr->kind.unary_op.operand) return -1;
                    return expr->kind.unary_op.operand->ast_type == LRL_AST_Value_Scalar;
                case LRL_Op_MakeOpt:
                    return is_already_evaluated(ctx, expr->kind.unary_op.operand);
                case LRL_Op_Plus:
                case LRL_Op_Deref:
                case LRL_Op_OptionalValue:
                case LRL_Op_EnumBase:
                case LRL_Op_Compl:
                case LRL_Op_LNot:
                    return 0;
                LRL_case_except_tt_unops default:
                    fail("constexpr_isalready_unop_switch");
            }
        case LRL_AST_Expr_BinaryOp:
        case LRL_AST_Expr_Conditional:
        case LRL_AST_Expr_Call:
        case LRL_AST_Expr_FuncMember:
        case LRL_AST_Expr_Member:
        case LRL_AST_Expr_As:
        case LRL_AST_Expr_TypeAssert:
        case LRL_AST_Expr_ArrayIndex:
            return 0;
        case LRL_AST_Value_TypeIdent:
        case LRL_AST_Value_Ident: {
            const LRLIdent *ident;
            if (lrl_identref_queue(ctx, &expr->kind.ident.identref)) return -1;
            if (!is_ident_ready(expr)) return -1;
            
            ident = expr->kind.ident.identref.ident;
            if (ident->flags & LRL_IdFl_EnumValue) return 1;
            
            if (!ident_has_initval(expr)) return 0;
            return 0; }
        case LRL_AST_Value_None:
        case LRL_AST_Value_NaN:
        case LRL_AST_Value_Inf:
        case LRL_AST_Value_Undefined:
        case LRL_AST_Value_Scalar:
        case LRL_AST_Expr_Evaluated:
            return 1;
        case LRL_AST_Value_Array:
        case LRL_AST_Value_Struct: {
            size_t i;
            for (i = 0; i < expr->kind.exprlist.num_args; i++) {
                LRLASTExpr *elem = expr->kind.exprlist.values[i];
                if (!is_already_evaluated(ctx, elem))
                    return 0;
            }
            return 1; }
        LRL_case_except_ast_exprs_values default:
            fail("constexpr_isalready_switch");
            return -1;
    }
}


typedef struct Number {
    LRLCodeLocation loc;
    int is_neg;
} Number;

static int get_number_expr(const LRLASTExpr *expr, Number *result)
{
    /* There's a negation flag in number exprs so we can
       remove any negation operation around it. */
    if (expr->ast_type == LRL_AST_Expr_UnaryOp &&
        expr->kind.unary_op.token_type == LRL_Op_Minus) {
        expr = expr->kind.unary_op.operand;
    }
    
    if (expr->ast_type != LRL_AST_Value_Scalar) return 0;
    
    if (expr->kind.scalar.token->type != LRL_TT_Integer &&
        expr->kind.scalar.token->type != LRL_TT_Real) return 0;
    
    if (result) {
        result->loc = expr->kind.scalar.token->loc;
        result->is_neg = expr->kind.scalar.is_negative;
    }
    return 1;
}

static LRLASTExpr *make_number_expr(const Number *value, const LRLASTExpr *template)
{
    LRLASTExpr *expr = malloc(sizeof(LRLASTExpr));
    LRLToken *token;
    expr->ast_type = LRL_AST_Value_Scalar;
    expr->typeref.quals = LRL_Qual_Const;
    expr->typeref.prm = template->typeref.prm;
    expr->typeref.type = template->typeref.type;
    expr->from = template->from;
    expr->to = template->to;
    
    token = malloc(sizeof(LRLToken));
    token->type = LRL_TT_Integer; /* TODO detect if integer or real value */
    token->loc = value->loc;
    
    expr->kind.scalar.token = token;
    expr->kind.scalar.is_negative = value->is_neg;

    if (value->is_neg) {
        LRLASTExpr *negation = malloc(sizeof(LRLASTExpr));
        negation->ast_type = LRL_AST_Expr_UnaryOp;
        negation->typeref.quals = LRL_Qual_Const;
        negation->typeref.prm = template->typeref.prm;
        negation->typeref.type = template->typeref.type;
        negation->from = template->from;
        negation->to = template->to;
        negation->kind.unary_op.token_type = LRL_Op_Minus;
        negation->kind.unary_op.operand = expr;
        return negation;
    } else {
        return expr;
    }
}

/**
 * Converts an integer to hexadecimal.
 * Returns 1 if successful.
 */
static int to_hex(const Number *num, Number *result)
{
    char *hexstr, *hsp;
    unsigned short hex[16]; /* short is => 16 bits, and we need 256 bits (to handle wrap around in wuint128 type) */
    unsigned short digit_one[16];
    unsigned short digit_n[16];
    short d, started;
    
    if (num->loc.length > 2 && !strncmp("0x", num->loc.start, 2)) {
        /* Already in hexadecimal */
        memcpy(result, num, sizeof(*result));
        return 1;
    }
    
    /* If we add support for binary numbers, we need to add a conversion
       here. For now we can assume it's decimal. */

    memset(hex, 0, sizeof(hex));
    memset(digit_one, 0, sizeof(digit_one));
    digit_one[15] = 1;
    for (d = num->loc.length-1; d >= 0; d--) {
        unsigned int digit = num->loc.start[d] - '0';
        short i, carry = 0;
        if (num->loc.start[d] == '_') continue;
        
        /* Convert the current digit to hex */
        for (i = 15; i >= 0; i--) {
            unsigned long dec = digit_one[i];
            unsigned long res = (digit*dec) + carry;
            digit_n[i] = res & 0xFFFF;
            carry = res >> 16;
        }
        if (carry) return 0;
        
        /* Add it */
        carry = 0;
        for (i = 15; i >= 0; i--) {
            unsigned long h = hex[i];
            unsigned long res = h + digit_n[i] + carry;
            hex[i] = res & 0xFFFF;
            carry = res >> 16;
        }
        if (carry) return 0;
        
        /* Next digit multiplier */
        if (d != 0) {
            carry = 0;
            for (i = 15; i >= 0; i--) {
                unsigned long dec = digit_one[i];
                unsigned long res = (10L*dec) + carry;
                digit_one[i] = res & 0xFFFF;
                carry = res >> 16;
            }
            if (carry) return 0;
        }
    }

    /* Build hex string */
    hsp = hexstr = malloc(num->loc.length+2);
    started = 0;
    for (d = 0; d < 16; d++) {
        int i;
        unsigned short h = hex[d];
        for (i = 0; i < 4; i++) {
            unsigned short digit = h >> 12;
            if (!started && digit) {
                *(hsp++) = '0';
                *(hsp++) = 'x';
                started = 1;
            }
            if (started) {
                char c = digit < 10 ? '0' + digit : 'a' + digit - 10;
                *(hsp++) = c;
            }
            h <<= 4;
        }
    }
    if (!started) {
        *(hsp++) = '0';
        *(hsp++) = 'x';
    }
    if (hsp[-1] == 'x') {
        *(hsp++) = '0';
    }
    
    result->loc.start = hexstr;
    result->loc.length = hsp - hexstr;
    result->is_neg = num->is_neg;
    return 1;
}

/**
 * Converts a number representing e.g. a bit count to an integer. If the
 * number is greater than max, then the result will be the max value instead.
 * Returns 1 if successful, 0 otherwise.
 */
static int to_int(const Number *a, unsigned *result, unsigned max)
{
    Number an;
    const char *ap;
    unsigned r = 0;
    short shift = 0;
    
    if (!to_hex(a, &an)) {
        return 0;
    }
    
    ap = an.loc.start + an.loc.length-1;
    while (ap > an.loc.start && *ap != 'x') {
        char c = *ap | 0x20;
        if (c >= '0' && c <= '9') {
            r |= (c - '0') << shift;
            shift += 4;
        } else if (c >= 'a' && c <= 'f') {
            r |= (c - 'a' + 0xa) << shift;
            shift += 4;
        } else if (c != '_') return 0;
        if (r > max) {
            r = max;
            break;
        }
        ap--;
    }
    
    *result = r;
    return 1;
}


static int get_bool_expr(const LRLASTExpr *expr)
{
    const LRLIdent *ident;
    if (expr->ast_type != LRL_AST_Value_Ident && expr->ast_type != LRL_AST_Value_TypeIdent)
        return -1;
    if (!is_ident_ready(expr)) return -1;
    if (!ident_has_initval(expr)) return 0;
    
    ident = expr->kind.ident.identref.ident;
    if (ident == lrl_builtin_get_bool_value(0)) return 0;
    if (ident == lrl_builtin_get_bool_value(1)) return 1;
    return -1;
}


static LRLASTExpr *make_bool_expr(int value, const LRLASTExpr *template)
{
    const LRLIdent *ident = lrl_builtin_get_bool_value(value);
    LRLASTExpr *expr = malloc(sizeof(LRLASTExpr));
    expr->ast_type = LRL_AST_Value_Ident;
    expr->typeref.quals = LRL_Qual_Const;
    expr->typeref.prm = NULL;
    expr->typeref.type = lrl_builtin_get_type(LRL_BT_bool);
    expr->from = template->from;
    expr->to = template->to;
    expr->kind.ident.identref.ident = ident;
    expr->kind.ident.identref.first_token = NULL;
    expr->kind.ident.identref.scope = NULL;
    expr->kind.ident.identref.next = NULL;
    expr->kind.ident.type_params = NULL;
    return expr;
}

/**
 * Returns
 *  -1 if a is less than b,
 *   0 if equal, or
 *   1 if a is greater than b.
 *   2 on error
 */
static int calc_compare(const Number *an, const Number *bn, int use_abs)
{
    size_t alen = an->loc.length, blen = bn->loc.length;
    const char *a = an->loc.start, *b = bn->loc.start;
    int aneg = an->is_neg;
    int bneg = bn->is_neg;
    int digit_diff = 0;
    int ahex, bhex;
    
    if (!use_abs && aneg != bneg) {
        return bneg - aneg;
    }
    
    /* TODO floating point is not yet supported */
    
    /* If any of the numbers is in hex, convert the other one to hex also */
    ahex = alen > 2 && !strncmp("0x", a, 2);
    bhex = blen > 2 && !strncmp("0x", b, 2);
    if (ahex != bhex) {
        Number hex;
        if (bhex) {
            if (!to_hex(an, &hex)) return 2;
            a = hex.loc.start;
            alen = hex.loc.length;
        } else {
            if (!to_hex(bn, &hex)) return 2;
            b = hex.loc.start;
            blen = hex.loc.length;
        }
    }
    if (ahex || bhex) { /* if so, then both are hex */
        a += 2; alen -= 2;
        b += 2; blen -= 2;
    }
    
    /* Skip leading zeros */
    while (alen && (*a == '_' || *a == '0')) { a++; alen--; }
    while (blen && (*b == '_' || *b == '0')) { b++; blen--; }
    
    for (;;) {
        /* Skip thousands separators */
        while (alen && *a == '_') { a++; alen--; }
        while (blen && *b == '_') { b++; blen--; }
        
        if (!alen || !blen) {
            /* Reached end */
            int diff;
            if (!alen && !blen) diff = digit_diff; /* Same length */
            else if (!alen) diff = -1;
            else if (!blen) diff = 1;
            else fail("impossible");
            
            return (use_abs || !aneg ? diff : -diff);
        }
        
        /* Compare digits */
        if (!digit_diff) {
            char ac = *a | 0x20;
            char bc = *b | 0x20;
            if (ac != bc) {
                digit_diff = ac < bc ? -1 : 1;
            }
        }
        
        a++; b++;
        alen--; blen--;
    }
}

#define get_hexdigit(ch, dig) do { \
        char c = (ch) | 0x20; \
        if (c >= '0' && c <= '9') { (dig) = c - '0'; } \
        else if (c >= 'a' && c <= 'f') { (dig) = c - 'a' + 10; } \
        else { (dig) = 0x10; } \
    } while (0)

/**
 * Adds or subtracts two numbers.
 */
static int calc_add(LRLTokenType op, const Number *anum, const Number *bnum,
                    Number *result)
{
    typedef struct Entry { unsigned int r_neg:1, swap:1, sub:1; } Entry;
    static const Entry optable[2][4][2] = {
        /* op == Plus */
        {
                      /* |b|<=|a|, |b|>|a| */
            /* +a, +b */ { {0,0,0}, {0,0,0} },
            /* +a, -b */ { {0,0,1}, {1,1,1} },
            /* -a, +b */ { {1,0,1}, {0,1,1} },
            /* -a, -b */ { {1,0,0}, {1,0,0} }
        },
        /* op == Minus */
        {
                      /* |b|<=|a|, |b|>|a| */
            /* +a, +b */ { {0,0,1}, {1,1,1} },
            /* +a, -b */ { {0,0,0}, {0,0,0} },
            /* -a, +b */ { {1,0,0}, {1,0,0} },
            /* -a, -b */ { {1,0,1}, {0,1,1} }
        }
    };
    Number an, bn;
    size_t r_len;
    char *r_start, *r;
    const char *a, *b, *a_start, *b_start;
    int a_neg, b_neg, b_greater, is_hex, base;
    Entry info;
    int carry;
    
    /* If either operand is hex, make sure both are hex */
    if ((anum->loc.length > 2 && !strncmp("0x", anum->loc.start, 2)) ||
        (bnum->loc.length > 2 && !strncmp("0x", bnum->loc.start, 2))) {
        if (!to_hex(anum, &an) || !to_hex(bnum, &bn)) return 0;
        is_hex = 1;
        base = 16;
    } else {
        memcpy(&an, anum, sizeof(an));
        memcpy(&bn, bnum, sizeof(bn));
        is_hex = 0;
        base = 10;
    }
    
    /* TODO floating point is not yet supported */
    
    /* Check if the numbers should be swapped */
    a_neg = an.is_neg;
    b_neg = bn.is_neg;
    b_greater = calc_compare(&an, &bn, 1) < 0; /* should compare abs values */
    info = optable[op==LRL_Op_Plus?0:1][(a_neg<<1)|b_neg][b_greater];
    
    /* Swap if needed */
    if (info.swap) {
        b_start = an.loc.start;
        a_start = bn.loc.start;
        b = an.loc.start + an.loc.length - 1;
        a = bn.loc.start + bn.loc.length - 1;
    } else {
        a_start = an.loc.start;
        b_start = bn.loc.start;
        a = an.loc.start + an.loc.length - 1;
        b = bn.loc.start + bn.loc.length - 1;
    }

        
    /* Allocate result with space for a rollover digit */
    r_len = (an.loc.length > bn.loc.length ?
             an.loc.length : bn.loc.length) + 1;
    r_start = malloc(r_len+1);
    r_start[r_len] = '\0';
    r = r_start + r_len - 1;
    
    /* Skip "0x" */
    if (is_hex) {
        a_start += 2;
        b_start += 2;
    }
    
    /* Perform operation */
    carry = 0;
    while (r >= r_start) {
        int dig1 = 0, dig2 = 0;
        int res;
        
        while (a >= a_start && *a == '_') a--;
        if (a >= a_start) {
            get_hexdigit(*(a--), dig1);
            if (dig1 > 0xf) {
                free(r_start);
                return 0;
            }
        }
        
        while (b >= b_start && *b == '_') b--;
        if (b >= b_start) {
            get_hexdigit(*(b--), dig2);
            if (dig1 > 0xf) {
                free(r_start);
                return 0;
            }
        }
        
        if (!info.sub) {
            /* Add digits */
            res = dig1 + dig2 + carry;
            if (res >= base) {
                res -= base;
                carry = 1;
            } else {
                carry = 0;
            }
        } else {
            /* Subtract digits */
            res = dig1 - dig2 + carry;
            if (res < 0) {
                res += base;
                carry = -1;
            } else {
                carry = 0;
            }
        }
        
        *(r--) = (res < 10 ? '0' + res : 'a' + res - 10);
    }
    
    /* Strip zeroes at the beginning */
    while (*r_start == '0' && r_len > 1) { r_start++; r_len--; }
    
    /* Add "0x" if hexadecimal */
    if (is_hex) {
        *(--r_start) = 'x';
        *(--r_start) = '0';
        r_len += 2;
    }
    
/*    fprintf(stderr, "result[a=%.*s, b=%.*s b_greater:%d] = (%d) %.*s\n", an->loc.length, an->loc.start, bn->loc.length, bn->loc.start, b_greater, info.r_neg, r_len, r_start);*/
    result->loc.length = r_len;
    result->loc.start = r_start;
    result->is_neg = info.r_neg;
    return 1;
}

/**
 * Multiplies two numbers.
 */
static int calc_mul(const Number *anum, const Number *bnum, Number *result)
{
    Number an, bn;
    size_t r_len;
    char *r_start, *r, *rnext;
    const char *a, *b;
    int is_hex, base, is_zero;
    int carry;

    /* If either operand is hex, make sure both are hex */
    if ((anum->loc.length > 2 && !strncmp("0x", anum->loc.start, 2)) ||
        (bnum->loc.length > 2 && !strncmp("0x", bnum->loc.start, 2))) {
        if (!to_hex(anum, &an) || !to_hex(bnum, &bn)) return 0;
        is_hex = 1;
        base = 16;
    } else {
        memcpy(&an, anum, sizeof(an));
        memcpy(&bn, bnum, sizeof(bn));
        is_hex = 0;
        base = 10;
    }

    /* TODO floating point is not yet supported */

    r_len = an.loc.length + bn.loc.length + 1;
    if (is_hex) r_len -= 2;
    r_start = malloc(r_len+1);
    memset(r_start, '0', r_len);
    r_start[r_len] = '\0';
    r = r_start + r_len - 1;

    a = an.loc.start + an.loc.length - 1;
    b = bn.loc.start + bn.loc.length - 1;

    /* Perform operation */
    carry = 0;
    rnext = r;
    for (a = an.loc.start + an.loc.length - 1; a >= an.loc.start; a--) {
        int dig1;
        if (*a == 'x') break;
        get_hexdigit(*a, dig1);
        if (dig1 > 0xf) continue;
        r = rnext;
        rnext = r-1;
        for (b = bn.loc.start + bn.loc.length - 1; b >= bn.loc.start; b--) {
            int dig2, exstdig, res;
            if (*b == 'x') break;
            get_hexdigit(*b, dig2);
            if (dig2 > 0xf) continue;
            get_hexdigit(*r, exstdig);
            res = dig1 * dig2 + exstdig + carry;
            if (res >= base) {
                /* TODO optimize */
                carry = res / base;
                res %= base;
            } else {
                carry = 0;
            }
            *(r--) = (res < 10 ? '0' + res : 'a' + res - 10);
        }
        if (carry) {
            *(r--) = (carry < 10 ? '0' + carry : 'a' + carry - 10);
            carry = 0;
        }
    }

    while (r[1] == '0') r++;
    if (*r == '0' && r[1] == '\0') {
        is_zero = 1;
        r--;
    } else {
        is_zero = 0;
    }
    if (is_hex) {
        *(r--) = 'x';
        *(r--) = '0';
    }
    r++;

/*fprintf(stderr, "res: %d<%.*s>\n", (int)((r_start+r_len) - r), (int)((r_start+r_len) - r), r);*/
    result->loc.start = r;
    result->loc.length = (r_start+r_len) - r;
    result->is_neg = !is_zero && (an.is_neg||bn.is_neg) && !(an.is_neg&&bn.is_neg);
    return 1;
}

/**
 * Performs bitwise complement on a number.
 */
static int calc_compl(const Number *a, Number *result)
{
    Number an;
    size_t i;
    char *rp;
    
    if (!to_hex(a, &an)) {
        return 0;
    }
    
    /* TODO need to know the target type and fill with 0xFFF...
            but we might not know the size of the target type here.
            have a "missing digits are complemented" flag?
            these could be translated into e.g. (-1L & x) */
    
    result->loc.start = rp = malloc(an.loc.length+1);
    *(rp++) = '0';
    *(rp++) = 'x';
    for (i = 2; i < an.loc.length; i++) {
        char dig = an.loc.start[i] | 0x20; /* convert A-F to lowercase */
        char rdig;
        if (dig >= '0' && dig <= '5') { rdig = 'a' + ('5' - dig); }
        else if (dig >= '6' && dig <= '9') { rdig = '6' + ('9' - dig); }
        else if (dig >= 'a' && dig <= 'f') { rdig = '0' + ('f' - dig); }
        else if (dig == ('_' | 0x20)) continue;
        else return 0;
        
        /*fprintf(stderr, "digit: %c=%c --> %c\n", an->loc.start[i], dig, rdig);*/
        *(rp++) = rdig;
    }
    *rp = '\0';
    result->loc.length = (rp - result->loc.start);
    return 1;
}

/**
 * Performs a left or right shift.
 */
static int calc_shift(const Number *a, const Number *bn,
                      Number *result, LRLTokenType optype)
{
    Number an;
    char *rp;
    unsigned bvalue;
    
    unsigned digitshift;
    unsigned bitshift;
    unsigned carry, carryshift;
    
    if (!to_hex(a, &an) || !to_int(bn, &bvalue, 128)) {
        return 0;
    } else if (bvalue == 0)  {
        /* Do nothing */
        memcpy(result, a, sizeof(*result));
        return 1;
    }
    
    digitshift = bvalue >> 2;
    bitshift = bvalue & 0x3;
    carry = 0;
    carryshift = 4 - bitshift;
    
    if (optype == LRL_Op_ShiftL) {
        /* Shift left */
        const char *ap = an.loc.start + an.loc.length - 1;
        size_t rlen = an.loc.length + digitshift + 1;
        char *rstart = malloc(rlen + 1);
        char *rend;
        rp = rend = (rstart + rlen);
        
        *(rp--) = '\0';
        if (digitshift) {
            /* fill with zeros at the end if we shift more than 4 bits */
            memset(rp-digitshift+1, '0', digitshift);
            rp -= digitshift;
        }
        for (;;) {
            unsigned dig, rdig;
            while (*ap == '_') { ap--; }
            if (*ap == 'x') break;
            get_hexdigit(*ap, dig);
            if (dig > 0xf) {
                free(rstart);
                return 0;
            }
            rdig = ((dig << bitshift) & 0xF) | carry;
            carry = dig >> carryshift;
            
            *(rp--) = (rdig < 10 ? '0' + rdig : 'a' + rdig - 10);
            ap--;
        }
        if (carry) {
            *(rp--) = (carry < 10 ? '0' + carry : 'a' + carry - 10);
        }
        *(rp--) = 'x';
        *rp = '0';
        result->loc.start = rp;
        result->loc.length = rend - rp;
    } else {
        /* Shift right */
        const char *ap = an.loc.start + 2;
        const char *aend = an.loc.start + an.loc.length;
        unsigned carrymask = 0xf >> carryshift;
        int started = 0;
        size_t allocsize;
        char *rstart;
        
        if ((uintptr_t)(aend - ap) > digitshift) {
            aend -= digitshift;
            allocsize = aend - ap + 3; /* 0x + \0 */
        } else {
            aend = ap;
            allocsize = 4; /* 0x0\0 */
        }
        
        rstart = rp = malloc(allocsize);
        *(rp++) = '0';
        *(rp++) = 'x';
        for (;;) {
            unsigned dig, rdig;
            while (ap != aend && *ap == '_') { ap++; }
            if (ap >= aend) break;
            get_hexdigit(*ap, dig);
            if (dig > 0xf) {
                free(rstart);
                return 0;
            }
            rdig = (dig >> bitshift) | carry;
            carry = (dig & carrymask) << carryshift;
            
            if (started || rdig) {
                *(rp++) = (rdig < 10 ? '0' + rdig : 'a' + rdig - 10);
                started = 1;
            }
            ap++;
        }
        if (!started) {
            /* shifted away all digits */
            *(rp++) = '0';
        }
        *rp = '\0';
        result->loc.start = rstart;
        result->loc.length = rp - result->loc.start;
    }

    result->is_neg = 0;
    return 1;
}

/**
 * Performs a bitwise AND, OR or XOR.
 */
static int calc_bitwise(const Number *a, const Number *b,
                        Number *result, LRLTokenType optype)
{
    Number an, bn;
    const char *ap, *bp, *tp;
    char *rp;
    size_t alen, blen, rlen, adigs = 0, bdigs = 0, askip = 0, bskip = 0;
    
    if (!to_hex(a, &an) || !to_hex(b, &bn)) {
        return 0;
    }
    
    ap = an.loc.start;
    alen = an.loc.length;
    bp = bn.loc.start;
    blen = bn.loc.length;
    
    ap += 2; alen -= 2;
    bp += 2; blen -= 2;
    
    /* Count number of digits, so we know how many
       digits to skip in the smallest number */
    for (tp = ap; tp < ap + alen; tp++) {
        if (*tp != '_') adigs++;
    }
    for (tp = bp; tp < bp + blen; tp++) {
        if (*tp != '_') bdigs++;
    }
    if (!adigs || !bdigs) return 0;
    
    rlen = adigs > bdigs ? adigs : bdigs;
    result->loc.start = rp = malloc(3+rlen);
    result->loc.length = 2+rlen;
    result->is_neg = 0;
    *(rp++) = '0';
    *(rp++) = 'x';
    
    if (adigs < bdigs)      { askip = bdigs - adigs; }
    else if (adigs > bdigs) { bskip = adigs - bdigs; }
    
    do {
        int adig, bdig, rdig;
        
        if (askip) {
            adig = 0;
            askip--;
        } else {
            while (alen && *ap == '_') { ap++; alen--; }
            get_hexdigit(*ap, adig);
            if (adig > 0xf) return 0;
            alen--; ap++;
        }
        
        if (bskip) {
            bdig = 0;
            bskip--;
        } else {
            while (blen && *bp == '_') { bp++; blen--; }
            get_hexdigit(*bp, bdig);
            if (bdig > 0xf) return 0;
            blen--; bp++;
        }
        
        switch ((int)optype) {
        case LRL_Op_BitAnd:  rdig = adig & bdig; break;
        case LRL_Op_BitOr:   rdig = adig | bdig; break;
        case LRL_Op_BitXor:  rdig = adig ^ bdig; break;
        default: fail("constexpr_bitwise_badoptype");
        }
        
        *(rp++) = (rdig > 9 ? 'a' + rdig - 10 : '0' + rdig);
        rlen--;
    } while (rlen && alen && blen);
    *rp = '\0';
    if (rlen) { fail("constexpr_bitwise_mismatch"); }
    
    return 1;
}

/**
 * Checks if the given integer can be assigned to the type of the given expr.
 */
static void integer_range_check(LRLCtx *ctx, const Number *num,
                                const LRLASTExpr *expr)
{
    LRLBuiltinType mintype = lrl_builtin_determine_int_type(&num->loc,
                                                            num->is_neg);
    LRLTypeRef realtr = lrl_vfy_find_real_typeref(&expr->typeref);
    if (realtr.type && realtr.type->ast_type == LRL_AST_Type_Builtin) {
        const LRLBuiltinType targetbt = realtr.type->kind.builtin;
        if (mintype == LRL_BT_INVALID || !lrl_builtin_target_is_superset(targetbt, mintype)) {
            lrl_err_set_expr(ctx, expr, 0);
            lrl_err_set_loc(ctx, &num->loc, 1);
            lrl_err_finish(ctx, LRL_Err_ComputedValueTooLarge);
        }
    }
}

/**
 * Performs wrap-around for wuint etc. types.
 * Returns 1 if wrapped around.
 */
static int wrap_around(LRLCtx *ctx, Number *num, const LRLASTExpr *expr)
{
    Number tmp;
    size_t hexdigits, numdigits, i, modified = 0;
    char *newnum = NULL, *newp;
    LRLTypeRef realtr = lrl_vfy_find_real_typeref(&expr->typeref);
    if (!realtr.type || realtr.type->ast_type != LRL_AST_Type_Builtin ||
        lrl_builtin_info[realtr.type->kind.builtin].btgroup != LRL_BTG_wrapping)
        return 0;

    switch (realtr.type->kind.builtin) {
        case LRL_BT_wcount:
        case LRL_BT_wuint:
        case LRL_BT_wushort:
        case LRL_BT_wulong:
        case LRL_BT_wulonglong:
            /* TODO need to query backend for size */
            return 0;
        case LRL_BT_wuint8:   hexdigits =  2; break;
        case LRL_BT_wuint16:  hexdigits =  4; break;
        case LRL_BT_wuint32:  hexdigits =  8; break;
        case LRL_BT_wuint64:  hexdigits = 16; break;
        case LRL_BT_wuint128: hexdigits = 32; break;
        LRL_case_bt_signedints
        LRL_case_bt_uints
        LRL_case_bt_eints
        LRL_case_bt_floats
        LRL_case_bt_bool
        LRL_case_bt_specials
        default: fail("constexpr_wraparound_bt_case");
    }
    /* Check number of digits */
    tmp = *num;
    if (!to_hex(&tmp, num)) return 0;
    if (num->loc.length <= 2+hexdigits) goto lengthok; /* "0x" + hexdigits */
    numdigits = 0;
    for (i = 2; i < num->loc.length; i++) {
        if (num->loc.start[i] != '_') numdigits++;
    }
    if (numdigits <= hexdigits) goto lengthok;
    /* Cut off excess high order digits */
    newnum = malloc(2+hexdigits+1);
    newnum[0] = '0';
    newnum[1] = 'x';
    newp = &newnum[2+hexdigits];
    *(newp--) = '\0';
    for (i = num->loc.length-1; newp >= newnum+2; i--, newp--) {
        if (num->loc.start[i] == '_') continue;
        *newp = num->loc.start[i];
    }
    num->loc.start = newnum;
    num->loc.length = 2+hexdigits;
    modified = 1;
  lengthok:
    if (num->is_neg) {
        Number maxnum;
        char maxvalue[2+1+32+1];
        maxvalue[0] = '0';
        maxvalue[1] = 'x';
        maxvalue[2] = '1';
        memset(maxvalue+3, '0', hexdigits);
        maxvalue[3+hexdigits] = '\0';
        maxnum.loc.start = maxvalue;
        maxnum.loc.length = 3+hexdigits;
        maxnum.is_neg = 0;
        calc_add(LRL_Op_Plus, &maxnum, num, &tmp);
        if (newnum) free(newnum);
        *num = tmp;
        modified = 1;
    }
    return modified;
}

static LRLASTExpr *eval_unary_op(LRLCtx *ctx, LRLASTExpr *expr)
{
    LRLASTExpr *op = constexpr_eval(ctx, expr->kind.unary_op.operand);
    if (!op) return NULL;
    
    switch (expr->kind.unary_op.token_type) {
        case LRL_Op_AddrOf:
        case LRL_Op_SizeOf:
        case LRL_Op_MinSizeOf:
        case LRL_Op_OffsetOf:
        case LRL_Op_AlignOf:
            return expr;
        case LRL_Op_Deref:
            return NULL;
        case LRL_Op_LNot: {
            /* Boolean Not operator */
            int val = get_bool_expr(op);
            if (val == -1) goto skip_op;
            return make_bool_expr(val ? 0 : 1, expr); }
        case LRL_Op_Plus:
            /* Do-noting operator */
            if (op->ast_type != LRL_AST_Value_Scalar) goto skip_op;
            else return op;
        case LRL_Op_Minus:
            /* Negation */
            if (op->ast_type == LRL_AST_Expr_UnaryOp &&
                op->kind.unary_op.token_type == LRL_Op_Minus) {
                /* Remove double negation */
                LRLASTExpr *operand = op->kind.unary_op.operand, *ret;
                /* TODO what about the is_neg on the operand? */
                /*if (op->kind.unary_op.operand->kind.scalar.is_negative) fail("notimpl");
                return op->kind.unary_op.operand;*/
                if (operand->ast_type != LRL_AST_Value_Scalar) goto skip_op;
                ret = malloc(sizeof(LRLASTExpr));
                memcpy(ret, operand, sizeof(LRLASTExpr));
                ret->kind.scalar.is_negative = 0;
                return ret;
            } else if (op->ast_type == LRL_AST_Value_Scalar) {
                /* Nothing to change, but rebuild the expr to
                   include any changes in the operand */
                LRLASTExpr *ret = malloc(sizeof(LRLASTExpr));
                LRLASTExpr *retop = malloc(sizeof(LRLASTExpr));
                memcpy(ret, expr, sizeof(LRLASTExpr));
                memcpy(retop, op, sizeof(LRLASTExpr));
                ret->kind.unary_op.operand = retop;
                retop->kind.scalar.is_negative = 1;
                return ret;
            } else {
                goto skip_op;
            }
        case LRL_Op_Compl: /*{
            Number a;
            Number result;
            if (!get_number_expr(op, &a) || a.is_neg)
                goto skip_op;
            
            TODO need to check the number of digits for the target type here
                 (or skip if unknown? or query the backend somehow?)
            TODO need to check that the target type doesn't have less digits
                 than the operand!
            
            calc_compl(&a, &result);
            return make_number_expr(&result, expr);
            }*/
            goto skip_op;
        case LRL_Op_OptionalValue:
            /* Take the value of an optional value. Undoes a makeopt */
            if (op->ast_type != LRL_AST_Expr_UnaryOp ||
                op->kind.unary_op.token_type != LRL_Op_MakeOpt) goto skip_op;
            return op->kind.unary_op.operand;
        case LRL_Op_EnumBase: {
            /* Return the value of the enum identifier */
            const LRLIdent *ident;
            LRLASTExpr *refexpr;
            if (op->ast_type != LRL_AST_Value_Ident && op->ast_type != LRL_AST_Value_TypeIdent) return NULL;
            if (lrl_identref_queue(ctx, &op->kind.ident.identref)) return NULL;
            if (!is_ident_ready(op) || !ident_has_initval(op)) return NULL;
            
            ident = op->kind.ident.identref.ident;
            if ((ident->flags & LRL_IdFl_EnumValue) == 0) return NULL;
            if (!ident->def_node) return NULL;
            refexpr = ident->def_node->def.kind.data.value;
            if (!refexpr) return NULL;
            
            return constexpr_eval(ctx, refexpr);
            }
        case LRL_Op_MakeOpt: {
            /* The operand might have been changed */
            LRLASTExpr *ret = malloc(sizeof(LRLASTExpr));
            memcpy(ret, expr, sizeof(LRLASTExpr));
            ret->kind.unary_op.operand = op;
            return ret; }
        LRL_case_except_tt_unops default:
            fail("constexpr_unaryop_switch");
    }
    
  skip_op: {
    /* We couldn't perform the operation (perhaps it contained e.g. a sizeof)
       but we can return an updated expr with the evaluated operand */
    LRLASTExpr *newexpr = malloc(sizeof(LRLASTExpr));
    memcpy(newexpr, expr, sizeof(LRLASTExpr));
    newexpr->kind.unary_op.operand = op;
    return newexpr;
    }
}

static LRLASTExpr *eval_equal_exprlist(LRLCtx *ctx, LRLASTExpr *eqexpr,
                                       LRLASTExpr *op1, LRLASTExpr *op2)
{
    int equal = eqexpr->kind.binary_op.token_type == LRL_Op_Equal;
    LRLASTExpr **aelem = op1->kind.exprlist.values;
    LRLASTExpr **belem = op2->kind.exprlist.values;
    LRLASTExpr compar;
    /* The verifier checks that the literal values have the correct number
       of elements. Here we only do a safety check that the number of items are
       the same */
    size_t num_args = op1->kind.exprlist.num_args;
    if (num_args != op2->kind.exprlist.num_args) return NULL;
    /* Do a comparison for each pair of elements */
    compar.ast_type = LRL_AST_Expr_BinaryOp;
    compar.kind.binary_op.token_type = LRL_Op_Equal;

    while (num_args--) {
        LRLASTExpr *resultexpr;
        int result;
        compar.kind.binary_op.operand1 = *aelem;
        compar.kind.binary_op.operand2 = *belem;
        resultexpr = eval_binary_op(ctx, &compar);
        if (!resultexpr) return NULL;
        result = get_bool_expr(resultexpr);
        free(resultexpr);
        if (result == -1) return NULL;
        else if (!result) return make_bool_expr(!equal, eqexpr);
        aelem++; belem++;
    }
    return make_bool_expr(equal, eqexpr);
}

/** Evalutes a binary operation. Returns a new expression, or NULL on error. */
static LRLASTExpr *eval_binary_op(LRLCtx *ctx, LRLASTExpr *expr)
{
    const LRLTokenType optype = expr->kind.binary_op.token_type;
    LRLASTExpr *op1 = constexpr_eval(ctx, expr->kind.binary_op.operand1);
    LRLASTExpr *op2 = constexpr_eval(ctx, expr->kind.binary_op.operand2);
    if (!op1 || !op2) return NULL;
    
    switch (optype) {
        case LRL_Op_Plus:
        case LRL_Op_Minus:
        case LRL_Op_Times:
        case LRL_Op_Divide:
        case LRL_Op_Modulo:
        case LRL_Op_ShiftL:
        case LRL_Op_ShiftR:
        case LRL_Op_BitAnd:
        case LRL_Op_BitOr:
        case LRL_Op_BitXor: {
            Number a;
            Number b;
            Number result;
            if (!get_number_expr(op1, &a) || !get_number_expr(op2, &b))
                goto skip_op;
            
            /* TODO check for floating point types, since working with them requires different code */
            
            switch ((int)optype) {
                case LRL_Op_Plus:
                case LRL_Op_Minus:
                    if (!calc_add(expr->kind.binary_op.token_type, &a, &b, &result))
                        goto skip_op;
                    break;
                case LRL_Op_Times:
                    if (!calc_mul(&a, &b, &result))
                        goto skip_op;
                    break;
                case LRL_Op_Divide:
                case LRL_Op_Modulo:
                    /* TODO */
                    goto skip_op;
                case LRL_Op_ShiftL:
                case LRL_Op_ShiftR:
                    if (!calc_shift(&a, &b, &result, optype))
                        goto skip_op;
                    break;
                case LRL_Op_BitAnd:
                case LRL_Op_BitOr:
                case LRL_Op_BitXor:
                    if (!calc_bitwise(&a, &b, &result, optype))
                        goto skip_op;
                    break;
                default:
                    fail("impossible");
            }

            wrap_around(ctx, &result, expr);

            /* Range check */
            integer_range_check(ctx, &result, expr);
            
            return make_number_expr(&result, expr); }
        case LRL_Op_LAnd:
        case LRL_Op_LOr:
        case LRL_Op_LXor: {
            int a = get_bool_expr(op1);
            int b = get_bool_expr(op2);
            int result;
            if (a == -1 || b == -1) goto skip_op;
            
            switch ((int)optype) {
                case LRL_Op_LAnd: result = a && b; break;
                case LRL_Op_LOr:  result = a || b; break;
                case LRL_Op_LXor: result = (a+b)==1; break;
                default: fail("impossible");
            }
            
            return make_bool_expr(result, expr); }
        case LRL_Op_Equal:
        case LRL_Op_NotEqual: {
            int equal = (optype == LRL_Op_Equal);
          deeper_equals:
            /* The expressions are evaluated literal values here, so if
               they are equal they should be exactly the same. */
            if (normalize_asttype(op1->ast_type) != normalize_asttype(op2->ast_type))
                return make_bool_expr(!equal, expr);
            
            if (get_number_expr(op1, NULL))
                goto compare_number;
            
            switch (op1->ast_type) {
                case LRL_AST_Value_None:
                    return make_bool_expr(equal, expr);
                case LRL_AST_Value_NaN:
                    return make_bool_expr(!equal, expr);
                case LRL_AST_Value_Undefined:
                case LRL_AST_Value_Inf:
                    goto skip_op;
                case LRL_AST_Value_Struct:
                case LRL_AST_Value_Array:
                    return eval_equal_exprlist(ctx, expr, op1, op2);
                case LRL_AST_Expr_UnaryOp:
                    /* Don't allow sizeof, addrof, etc. to be compared like
                       this (a==b doesn't imply that sizeof(a)==sizeof(b)) */
                    if (op1->kind.unary_op.token_type != LRL_Op_MakeOpt)
                        goto skip_op;
                    if (op1->kind.unary_op.token_type !=
                        op2->kind.unary_op.token_type)
                        return make_bool_expr(!equal, expr);
                    op1 = op1->kind.unary_op.operand;
                    op2 = op2->kind.unary_op.operand;
                    goto deeper_equals;
                case LRL_AST_Value_TypeIdent:
                case LRL_AST_Value_Ident: {
                    const LRLIdent *op1ident = op1->kind.ident.identref.ident;
                    const LRLIdent *op2ident = op2->kind.ident.identref.ident;

                    if (!op1ident || !op2ident) return NULL;

                    if ((op1ident->flags & LRL_IdFl_EnumValue) &&
                        op1ident->scope == op2ident->scope) {
                        /* Values from the same enum */
                        return make_bool_expr(op1ident == op2ident ? equal : !equal, expr);
                    }
                    goto skip_op;
                }
                case LRL_AST_Value_Scalar: /* handled by get_number_expr */
                case LRL_AST_Expr_Evaluated: /* handled by constexpr_eval */
                /* If we get any of the following expression types, then that
                   means that the expression could not be evaluated. */
                case LRL_AST_Expr_BinaryOp:
                case LRL_AST_Expr_Conditional:
                case LRL_AST_Expr_Call:
                case LRL_AST_Expr_FuncMember:
                case LRL_AST_Expr_Member:
                case LRL_AST_Expr_As:
                case LRL_AST_Expr_TypeAssert:
                case LRL_AST_Expr_ArrayIndex:
                LRL_case_except_ast_exprs_values default:
                    goto skip_op;
            }
            goto skip_op; }
        case LRL_Op_Less:
        case LRL_Op_LessEqual:
        case LRL_Op_Greater:
        case LRL_Op_GreaterEqual: {
            Number a;
            Number b;
            int diff, result;
          compare_number:
            if (!get_number_expr(op1, &a) || !get_number_expr(op2, &b))
                goto skip_op;
            
            diff = calc_compare(&a, &b, 0);
            if (diff == 2)
                goto skip_op;
            
            switch ((int)optype) {
                case LRL_Op_Less:         result = diff < 0; break;
                case LRL_Op_LessEqual:    result = diff <= 0; break;
                case LRL_Op_Greater:      result = diff > 0; break;
                case LRL_Op_GreaterEqual: result = diff >= 0; break;
                case LRL_Op_Equal:        result = diff == 0; break;
                case LRL_Op_NotEqual:     result = diff != 0; break;
                default: fail("impossible");
            }
            
            return make_bool_expr(result, expr); }
        case LRL_Op_PlusAssign:
        case LRL_Op_MinusAssign:
        case LRL_Op_TimesAssign:
        case LRL_Op_DivideAssign:
        case LRL_Op_ShiftLAssign:
        case LRL_Op_ShiftRAssign:
        case LRL_Op_Assign:
            /* Not allowed in const expressions */
            return NULL;
        LRL_case_except_tt_binops default:
            fail("constexpr_binaryop_switch");
    }

  skip_op: {
    /* We couldn't perform the operation (perhaps it contained e.g. a sizeof)
       but we can return an updated expr with the evaluated operands */
    LRLASTExpr *newexpr = malloc(sizeof(LRLASTExpr));
    memcpy(newexpr, expr, sizeof(LRLASTExpr));
    newexpr->kind.binary_op.operand1 = op1;
    newexpr->kind.binary_op.operand2 = op2;
    return newexpr;
    }
}

/**
 * Evaluates the given expression. Returns an expr constisting of only
 * literal values and pointers.
 *
 * The expression must be valid and must be evaluatable.
 */
LRLASTExpr *lrl_constexpr_eval(LRLCtx *ctx, LRLASTExpr *expr)
{
    if (!expr || expr->ast_type == LRL_AST_Expr_Evaluated) return NULL;
    ctx->constexpr_cyclestart = NULL;
    ctx->constexpr_iteration = 0;
    ctx->constexpr_nextstop = 2;
    ctx->constexpr_errorexpr = expr;
    return constexpr_eval(ctx, expr);
}

static LRLASTExpr *constexpr_eval(LRLCtx *ctx, LRLASTExpr *expr)
{
    int status;

    if (!expr) return NULL;
    if (expr->ast_type == LRL_AST_Expr_Evaluated) {
        return expr->kind.evaluated.evaluated;
    }

    /* Check if already evaluated or not possible to evaluate */
    status = is_already_evaluated(ctx, expr);
    if (status == 1) return expr;
    else if (status == -1) return NULL;
    
    if (!ctx->constexpr_errorexpr) return NULL; /* error reported already */
    
    /* Detect cycles */
    if (ctx->constexpr_cyclestart && expr == ctx->constexpr_cyclestart) {
        lrl_err_set_expr(ctx, ctx->constexpr_errorexpr, 0);
        lrl_err_set_expr(ctx, expr, 1);
        lrl_err_finish(ctx, LRL_Err_CyclicExprDetected);
        ctx->constexpr_errorexpr = NULL; /* = don't continue */
        return NULL;
    }
    if (++ctx->constexpr_iteration == ctx->constexpr_nextstop) {
        ctx->constexpr_cyclestart = expr;
        ctx->constexpr_nextstop *= 2;
        ctx->constexpr_iteration = 0;
    }
    
    switch (expr->ast_type) {
        case LRL_AST_Expr_UnaryOp:
            return eval_unary_op(ctx, expr);
        case LRL_AST_Expr_BinaryOp:
            return eval_binary_op(ctx, expr);
        case LRL_AST_Expr_Conditional: {
            LRLASTExpr *cond = constexpr_eval(ctx, expr->kind.conditional.condexpr);
            int cond_value;
            if (!cond) return NULL;
            
            cond_value = get_bool_expr(cond);
            if (cond_value == 1)
                return constexpr_eval(ctx, expr->kind.conditional.trueexpr);
            else if (cond_value == 0)
                return constexpr_eval(ctx, expr->kind.conditional.falseexpr);
            else
                return NULL; }
        case LRL_AST_Expr_Call:
        case LRL_AST_Expr_FuncMember:
            return NULL;
        case LRL_AST_Expr_Member: {
            LRLTypeRef structtr;
            LRLASTExpr *struc = constexpr_eval(ctx, expr->kind.member.struc);
            size_t i;
            const LRLASTDefList *member;
            const LRLToken *tok;
            
            if (!struc || struc->ast_type != LRL_AST_Value_Struct) return NULL;
            
            structtr = lrl_vfy_find_real_typeref(&struc->typeref);
            if (!structtr.type ||
                structtr.type->ast_type != LRL_AST_Type_Struct) return NULL;
            
            tok = expr->kind.member.token;
            if (!tok) return NULL;
            for (i = 0, member = structtr.type->kind.struc.members;
                 i < struc->kind.exprlist.num_args && member;
                 i++, member = member->next) {
                const LRLToken *name;
                const LRLIdent *ident = member->def.kind.ident;
                if (!ident) continue; /* ignore nameless members */
                name = ident->def_token;
                if (!name) fail("constexpr_eval_nomemberdeftok");
                
                if (name->loc.length == tok->loc.length &&
                   !strncmp(name->loc.start, tok->loc.start, tok->loc.length)) {
                    return struc->kind.exprlist.values[i];
                }
            }
            /* Not found */
            return NULL; }
        case LRL_AST_Expr_As:
            /* should work since the calculations are done with the right type */
            return constexpr_eval(ctx, expr->kind.asexpr.expr);
        case LRL_AST_Expr_TypeAssert: {
            LRLASTExpr *val = constexpr_eval(ctx, expr->kind.typeassert.expr);
            LRLASTExpr *copy;
            Number result;
            
            if (!get_number_expr(val, &result))
                return val;
            
            integer_range_check(ctx, &result, expr);
            
            copy = malloc(sizeof(LRLASTExpr));
            memcpy(copy, val, sizeof(LRLASTExpr));
            copy->typeref.type = expr->kind.typeassert.type;
            copy->typeref.quals = LRL_Qual_Var|LRL_Qual_Mine;
            return copy; }
        case LRL_AST_Expr_ArrayIndex: {
            LRLASTExpr *array = constexpr_eval(ctx, expr->kind.index.array);
            LRLASTExpr *index = constexpr_eval(ctx, expr->kind.index.index);
            char number[51];
            const char *p;
            char *n;
            unsigned long index_value;
            unsigned long length;
            char *parsed_str;
            if (!array || !index) return NULL;
            
            /* The array expr must be an array literal or string literal */
            if (array->ast_type != LRL_AST_Value_Array &&
                (array->ast_type != LRL_AST_Value_Scalar ||
                 array->kind.scalar.token->type != LRL_TT_String)) return NULL;
            
            /* The index expr must be an integer */
            if (index->ast_type != LRL_AST_Value_Scalar ||
                index->kind.scalar.token->type != LRL_TT_Integer) return NULL;
            
            /* Convert index token to integer */
            if (index->kind.scalar.token->loc.length >= 50 ||
                !index->kind.scalar.token->loc.length ||
                index->kind.scalar.is_negative) {
                lrl_err_set_expr(ctx, ctx->constexpr_errorexpr, 0);
                lrl_err_set_token(ctx, index->kind.scalar.token, 1);
                lrl_err_finish(ctx, LRL_Err_InvalidArrayIndex);
                return NULL;
            }
            
            /* Skip leading zeros (causes strtol to interpret as octal) */
            /* TODO can we use to_int here ? */
            p = index->kind.scalar.token->loc.start;
            while (*p == '0' && p[1] >= '0' && p[1] <= '9') p++;
            
            n = number;
            if (*p == '0' && p[1] == 'x') {
                *(n++) = '0';
                *(n++) = 'x';
                p += 2;
            }
            if (!*p) return NULL;
            for (;;) {
                char c = *(p++);
                if (c == '_') continue;
                if (n > number+49) break;
                if ((c < '0' || c > '9') && (c < 'a' || c > 'z') && (c < 'A' || c > 'Z')) break;
                *(n++) = c;
            }
            *n = '\0';
            index_value = strtoul(number, NULL, 0);
            
            if (array->ast_type == LRL_AST_Value_Array) {
                /* Array */
                if (index_value >= array->kind.exprlist.num_args) {
                    lrl_err_set_expr(ctx, ctx->constexpr_errorexpr, 0);
                    lrl_err_set_token(ctx, index->kind.scalar.token, 1);
                    lrl_err_finish(ctx, LRL_Err_InvalidArrayIndex);
                    return NULL;
                }
                return constexpr_eval(ctx, array->kind.exprlist.values[index_value]);
            } else {
                /* String */
                const LRLToken *strtoken = array->kind.scalar.token;
                const char *unparsed = strtoken->loc.start+1;
                char *sp = parsed_str = malloc(strtoken->loc.length);
                LRLASTExpr *elem;
                LRLToken *token;
                char *bytestr;
                unsigned char ch;
                
                if (!lrl_string_parse(ctx, &unparsed, &sp)) {
                    return NULL;
                }
                *sp = '\0';
                length = strlen(parsed_str);
                
                if (index_value >= length) {
                    lrl_err_set_expr(ctx, ctx->constexpr_errorexpr, 0);
                    lrl_err_set_token(ctx, index->kind.scalar.token, 1);
                    lrl_err_finish(ctx, LRL_Err_InvalidArrayIndex);
                    return NULL;
                }
                
                /* Extract char value and return as a number expr */
                elem = malloc(sizeof(LRLASTExpr));
                token = malloc(sizeof(LRLToken));
                bytestr = malloc(3+1); /* max is "255\0" */
                
                elem->ast_type = LRL_AST_Value_Scalar;
                elem->typeref.quals = LRL_Qual_Const;
                elem->typeref.prm = NULL;
                elem->typeref.type = lrl_builtin_get_type(LRL_BT_byte);
                elem->from = expr->from;
                elem->to = expr->to;
                
                ch = parsed_str[index_value];
                token->type = LRL_TT_Integer;
                token->loc.length = sprintf(bytestr, "%u",  (unsigned int)ch);
                token->loc.start = bytestr;
                
                elem->kind.scalar.token = token;
                elem->kind.scalar.is_negative = 0;
                return elem;
            }
            }
        case LRL_AST_Value_TypeIdent:
        case LRL_AST_Value_Ident: {
            const LRLIdent *ident;
            LRLASTExpr *refexpr;
            if (lrl_identref_queue(ctx, &expr->kind.ident.identref)) return NULL;
            if (!is_ident_ready(expr) || !ident_has_initval(expr)) return NULL;
            
            ident = expr->kind.ident.identref.ident;
            refexpr = ident->def_node->def.kind.data.value;
            if (ident->flags & LRL_IdFl_EnumValue) return expr;
            if (refexpr->typeref.quals & (LRL_Qual_Var|LRL_Qual_Shared))
                return NULL;
            
            if (!refexpr->typeref.type) {
                /* TODO: In the worst case this will lead to quadratic
                   compilation time if definitions come in reverse order.
                   Note that returning a **expr (i.e. that could be updated
                   when the definition has been parsed) won't work, because we
                   might need to evaluate it to get the result (e.g. a=b+123)*/
                return NULL;
            }

            return constexpr_eval(ctx, refexpr/*expr->kind.ident.identref.ident->def_node->def.kind.data.value*/); }
        case LRL_AST_Value_None:
        case LRL_AST_Value_NaN:
        case LRL_AST_Value_Inf:
        case LRL_AST_Value_Undefined:
        case LRL_AST_Value_Scalar:
            return expr;
        case LRL_AST_Value_Array:
        case LRL_AST_Value_Struct: {
            LRLASTExpr *evaluated = malloc(sizeof(LRLASTExpr));
            size_t i;
            
            memcpy(evaluated, expr, sizeof(LRLASTExpr));
            evaluated->kind.exprlist.values = malloc(expr->kind.exprlist.num_args*sizeof(LRLASTExpr*));
            for (i = 0; i < expr->kind.exprlist.num_args; i++) {
                LRLASTExpr *elemexpr = constexpr_eval(ctx, expr->kind.exprlist.values[i]);
                if (!elemexpr) {
                    free(evaluated);
                    return NULL;
                }
                evaluated->kind.exprlist.values[i] = elemexpr;
            }
            return evaluated; }
        case LRL_AST_Expr_Evaluated: /* handled at start of function */
        LRL_case_except_ast_exprs_values default:
            fail("constexpr_eval_switch");
            return NULL;
    }
}