[PATCH] parser.c cleanup

[smatch.git] / evaluate.c

/*
 * sparse/evaluate.c
 *
 * Copyright (C) 2003 Transmeta Corp.
 *               2003 Linus Torvalds
 *
 *  Licensed under the Open Software License version 1.1
 *
 * Evaluate constant expressions.
 */
#include <stdlib.h>
#include <stdarg.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <unistd.h>
#include <fcntl.h>
#include <limits.h>

#include "lib.h"
#include "parse.h"
#include "token.h"
#include "symbol.h"
#include "target.h"
#include "expression.h"

static struct symbol *current_fn;
static int current_context, current_contextmask;

static struct symbol *degenerate(struct expression *expr);

static struct symbol *evaluate_symbol_expression(struct expression *expr)
{
        struct symbol *sym = expr->symbol;
        struct symbol *base_type;

        if (!sym) {
                if (preprocessing) {
                        expr->ctype = &int_ctype;
                        return &int_ctype;
                }
                warn(expr->pos, "undefined identifier '%s'", show_ident(expr->symbol_name));
                return NULL;
        }

        examine_symbol_type(sym);
        if ((sym->ctype.context ^ current_context) & (sym->ctype.contextmask & current_contextmask))
                warn(expr->pos, "Using symbol '%s' in wrong context", show_ident(expr->symbol_name));

        base_type = sym->ctype.base_type;
        if (!base_type) {
                warn(expr->pos, "identifier '%s' has no type", show_ident(expr->symbol_name));
                return NULL;
        }

        /* The type of a symbol is the symbol itself! */
        expr->ctype = sym;

        /* enum's can be turned into plain values */
        if (sym->type != SYM_ENUM) {
                struct expression *addr = alloc_expression(expr->pos, EXPR_SYMBOL);
                addr->symbol = sym;
                addr->symbol_name = expr->symbol_name;
                addr->ctype = &lazy_ptr_ctype;  /* Lazy evaluation: we need to do a proper job if somebody does &sym */
                expr->type = EXPR_PREOP;
                expr->op = '*';
                expr->unop = addr;
                return sym;
        }
        expr->type = EXPR_VALUE;
        expr->value = sym->value;
        expr->ctype = base_type;
        return sym;
}

static struct symbol *evaluate_string(struct expression *expr)
{
        struct symbol *sym = alloc_symbol(expr->pos, SYM_NODE);
        struct symbol *array = alloc_symbol(expr->pos, SYM_ARRAY);
        struct expression *addr = alloc_expression(expr->pos, EXPR_SYMBOL);
        struct expression *initstr = alloc_expression(expr->pos, EXPR_STRING);
        unsigned int length = expr->string->length;

        sym->array_size = alloc_const_expression(expr->pos, length);
        sym->bit_size = bits_in_char * length;
        sym->ctype.alignment = 1;
        sym->ctype.modifiers = MOD_STATIC;
        sym->ctype.base_type = array;
        sym->initializer = initstr;

        initstr->ctype = sym;
        initstr->string = expr->string;

        array->array_size = sym->array_size;
        array->bit_size = bits_in_char * length;
        array->ctype.alignment = 1;
        array->ctype.modifiers = MOD_STATIC;
        array->ctype.base_type = &char_ctype;
        
        addr->symbol = sym;
        addr->ctype = &lazy_ptr_ctype;

        expr->type = EXPR_PREOP;
        expr->op = '*';
        expr->unop = addr;  
        expr->ctype = sym;
        return sym;
}

static inline struct symbol *integer_promotion(struct symbol *type)
{
        unsigned long mod =  type->ctype.modifiers;
        int width;

        if (type->type == SYM_ENUM)
                return &int_ctype;
        else if (type->type == SYM_BITFIELD) {
                mod = type->ctype.base_type->ctype.modifiers;
                width = type->fieldwidth;
        } else if (mod & (MOD_CHAR | MOD_SHORT))
                width = type->bit_size;
        else
                return type;
        if (mod & MOD_UNSIGNED && width == bits_in_int)
                return &uint_ctype;
        return &int_ctype;
}

/*
 * integer part of usual arithmetic conversions:
 *      integer promotions are applied
 *      if left and right are identical, we are done
 *      if signedness is the same, convert one with lower rank
 *      unless unsigned argument has rank lower than signed one, convert the
 *      signed one.
 *      if signed argument is bigger than unsigned one, convert the unsigned.
 *      otherwise, convert signed.
 *
 * Leaving aside the integer promotions, that is equivalent to
 *      if identical, don't convert
 *      if left is bigger than right, convert right
 *      if right is bigger than left, convert right
 *      otherwise, if signedness is the same, convert one with lower rank
 *      otherwise convert the signed one.
 */
static struct symbol *bigger_int_type(struct symbol *left, struct symbol *right)
{
        unsigned long lmod, rmod;

        left = integer_promotion(left);
        right = integer_promotion(right);

        if (left == right)
                goto left;

        if (left->bit_size > right->bit_size)
                goto left;

        if (right->bit_size > left->bit_size)
                goto right;

        lmod = left->ctype.modifiers;
        rmod = right->ctype.modifiers;
        if ((lmod ^ rmod) & MOD_UNSIGNED) {
                if (lmod & MOD_UNSIGNED)
                        goto left;
        } else if ((lmod & ~rmod) & (MOD_LONG | MOD_LONGLONG))
                goto left;
right:
        left = right;
left:
        return left;
}

static struct expression * cast_to(struct expression *old, struct symbol *type)
{
        struct expression *expr = alloc_expression(old->pos, EXPR_CAST);
        expr->ctype = type;
        expr->cast_type = type;
        expr->cast_expression = old;
        return expr;
}

static int is_type_type(struct symbol *type)
{
        return (type->ctype.modifiers & MOD_TYPE) != 0;
}

static int is_ptr_type(struct symbol *type)
{
        if (type->type == SYM_NODE)
                type = type->ctype.base_type;
        return type->type == SYM_PTR || type->type == SYM_ARRAY || type->type == SYM_FN;
}

static inline int is_float_type(struct symbol *type)
{
        if (type->type == SYM_NODE)
                type = type->ctype.base_type;
        return type->ctype.base_type == &fp_type;
}

static inline int is_byte_type(struct symbol *type)
{
        return type->bit_size == bits_in_char && type->type != SYM_BITFIELD;
}

static inline int is_string_type(struct symbol *type)
{
        if (type->type == SYM_NODE)
                type = type->ctype.base_type;
        return type->type == SYM_ARRAY && is_byte_type(type->ctype.base_type);
}

static struct symbol *bad_expr_type(struct expression *expr)
{
        warn(expr->pos, "incompatible types for operation (%s)", show_special(expr->op));
        switch (expr->type) {
        case EXPR_BINOP:
        case EXPR_COMPARE:
                info(expr->pos, "   left side has type %s", show_typename(expr->left->ctype));
                info(expr->pos, "   right side has type %s", show_typename(expr->right->ctype));
                break;
        case EXPR_PREOP:
        case EXPR_POSTOP:
                info(expr->pos, "   argument has type %s", show_typename(expr->unop->ctype));
                break;
        default:
                break;
        }

        return NULL;
}

static struct symbol *compatible_float_binop(struct expression **lp, struct expression **rp)
{
        struct expression *left = *lp, *right = *rp;
        struct symbol *ltype = left->ctype, *rtype = right->ctype;

        if (ltype->type == SYM_NODE)
                ltype = ltype->ctype.base_type;
        if (rtype->type == SYM_NODE)
                rtype = rtype->ctype.base_type;
        if (is_float_type(ltype)) {
                if (is_int_type(rtype))
                        goto Left;
                if (is_float_type(rtype)) {
                        unsigned long lmod = ltype->ctype.modifiers;
                        unsigned long rmod = rtype->ctype.modifiers;
                        lmod &= MOD_LONG | MOD_LONGLONG;
                        rmod &= MOD_LONG | MOD_LONGLONG;
                        if (lmod == rmod)
                                return ltype;
                        if (lmod & ~rmod)
                                goto Left;
                        else
                                goto Right;
                }
                return NULL;
        }
        if (!is_float_type(rtype) || !is_int_type(ltype))
                return NULL;
Right:
        *lp = cast_to(left, rtype);
        return rtype;
Left:
        *rp = cast_to(right, ltype);
        return ltype;
}

static struct symbol *compatible_integer_binop(struct expression **lp, struct expression **rp)
{
        struct expression *left = *lp, *right = *rp;
        struct symbol *ltype = left->ctype, *rtype = right->ctype;

        if (ltype->type == SYM_NODE)
                ltype = ltype->ctype.base_type;
        if (rtype->type == SYM_NODE)
                rtype = rtype->ctype.base_type;
        if (is_int_type(ltype) && is_int_type(rtype)) {
                struct symbol *ctype = bigger_int_type(ltype, rtype);

                /* Don't bother promoting same-size entities, it only adds clutter */
                if (ltype->bit_size != ctype->bit_size)
                        *lp = cast_to(left, ctype);
                if (rtype->bit_size != ctype->bit_size)
                        *rp = cast_to(right, ctype);
                return ctype;
        }
        return NULL;
}

static struct symbol *evaluate_arith(struct expression *expr, int float_ok)
{
        struct symbol *ctype = compatible_integer_binop(&expr->left, &expr->right);
        if (!ctype && float_ok)
                ctype = compatible_float_binop(&expr->left, &expr->right);
        if (ctype) {
                expr->ctype = ctype;
                return ctype;
        }
        return bad_expr_type(expr);
}

static inline int lvalue_expression(struct expression *expr)
{
        return (expr->type == EXPR_PREOP && expr->op == '*') || expr->type == EXPR_BITFIELD;
}

static struct symbol *evaluate_ptr_add(struct expression *expr, struct expression *ptr, struct expression *i)
{
        struct symbol *ctype;
        struct symbol *ptr_type = ptr->ctype;
        int bit_size;

        if (ptr_type->type == SYM_NODE)
                ptr_type = ptr_type->ctype.base_type;

        if (!is_int_type(i->ctype))
                return bad_expr_type(expr);

        ctype = ptr->ctype;
        examine_symbol_type(ctype);

        ctype = degenerate(ptr);
        if (!ctype->ctype.base_type) {
                warn(expr->pos, "missing type information");
                return NULL;
        }

        /* Get the size of whatever the pointer points to */
        ptr_type = ctype;
        if (ptr_type->type == SYM_NODE)
        ptr_type = ptr_type->ctype.base_type;
        if (ptr_type->type == SYM_PTR)
                ptr_type = ptr_type->ctype.base_type;
        bit_size = ptr_type->bit_size;

        /* Special case: adding zero commonly happens as a result of 'array[0]' */
        if (i->type == EXPR_VALUE && !i->value) {
                *expr = *ptr;
        } else if (bit_size > bits_in_char) {
                struct expression *add = expr;
                struct expression *mul = alloc_expression(expr->pos, EXPR_BINOP);
                struct expression *val = alloc_expression(expr->pos, EXPR_VALUE);

                val->ctype = size_t_ctype;
                val->value = bit_size >> 3;

                mul->op = '*';
                mul->ctype = size_t_ctype;
                mul->left = i;
                mul->right = val;

                /* Leave 'add->op' as 'expr->op' - either '+' or '-' */
                add->left = ptr;
                add->right = mul;
        }

        expr->ctype = ctype;    
        return ctype;
}

static struct symbol *evaluate_add(struct expression *expr)
{
        struct expression *left = expr->left, *right = expr->right;
        struct symbol *ltype = left->ctype, *rtype = right->ctype;

        if (is_ptr_type(ltype))
                return evaluate_ptr_add(expr, left, right);

        if (is_ptr_type(rtype))
                return evaluate_ptr_add(expr, right, left);
                
        return evaluate_arith(expr, 1);
}

#define MOD_SIZE (MOD_CHAR | MOD_SHORT | MOD_LONG | MOD_LONGLONG)
#define MOD_IGNORE (MOD_TOPLEVEL | MOD_STORAGE | MOD_ADDRESSABLE |      \
        MOD_SIGNED | MOD_UNSIGNED | MOD_EXPLICITLY_SIGNED |             \
        MOD_ASSIGNED | MOD_USERTYPE | MOD_FORCE | MOD_ACCESSED)

const char * type_difference(struct symbol *target, struct symbol *source,
        unsigned long target_mod_ignore, unsigned long source_mod_ignore)
{
        for (;;) {
                unsigned long mod1, mod2, diff;
                unsigned long as1, as2;
                int type1, type2;
                struct symbol *base1, *base2;

                if (target == source)
                        break;
                if (!target || !source)
                        return "different types";
                /*
                 * Peel of per-node information.
                 * FIXME! Check alignment and context too here!
                 */
                mod1 = target->ctype.modifiers;
                as1 = target->ctype.as;
                mod2 = source->ctype.modifiers;
                as2 = source->ctype.as; 
                if (target->type == SYM_NODE) {
                        target = target->ctype.base_type;
                        if (!target)
                                return "bad types";
                        if (target->type == SYM_PTR) {
                                mod1 = 0;
                                as1 = 0;
                        }       
                        mod1 |= target->ctype.modifiers;
                        as1 |= target->ctype.as;
                }
                if (source->type == SYM_NODE) {
                        source = source->ctype.base_type;
                        if (!source)
                                return "bad types";
                        if (source->type == SYM_PTR) {
                                mod2 = 0;
                                as2 = 0;
                        }
                        mod2 |= source->ctype.modifiers;
                        as2 |= source->ctype.as; 
                }

                if (target == source)
                        break;
                if (!target || !source)
                        return "different types";

                type1 = target->type;
                base1 = target->ctype.base_type;

                type2 = source->type;
                base2 = source->ctype.base_type;

                /*
                 * Pointers to functions compare as the function itself
                 */
                if (type1 == SYM_PTR && base1) {
                        switch (base1->type) {
                        case SYM_FN:
                                type1 = SYM_FN;
                                target = base1;
                                base1 = base1->ctype.base_type;
                        default:
                                /* nothing */;
                        }
                }
                if (type2 == SYM_PTR && base2) {
                        switch (base2->type) {
                        case SYM_FN:
                                type2 = SYM_FN;
                                source = base2;
                                base2 = base2->ctype.base_type;
                        default:
                                /* nothing */;
                        }
                }

                /* Arrays degenerate to pointers for type comparisons */
                type1 = (type1 == SYM_ARRAY) ? SYM_PTR : type1;
                type2 = (type2 == SYM_ARRAY) ? SYM_PTR : type2;

                if (type1 != type2)
                        return "different base types";

                /* Must be same address space to be comparable */
                if (as1 != as2)
                        return "different address spaces";

                /* Ignore differences in storage types, sign, or addressability */
                diff = (mod1 ^ mod2) & ~MOD_IGNORE;
                if (diff) {
                        mod1 &= diff & ~target_mod_ignore;
                        mod2 &= diff & ~source_mod_ignore;
                        if (mod1 | mod2) {
                                if ((mod1 | mod2) & MOD_SIZE)
                                        return "different type sizes";
                                return "different modifiers";
                        }
                }

                if (type1 == SYM_FN) {
                        int i;
                        struct symbol *arg1, *arg2;
                        if (base1->variadic != base2->variadic)
                                return "incompatible variadic arguments";
                        PREPARE_PTR_LIST(target->arguments, arg1);
                        PREPARE_PTR_LIST(source->arguments, arg2);
                        i = 1;
                        for (;;) {
                                const char *diff;
                                diff = type_difference(arg1, arg2, 0, 0);
                                if (diff) {
                                        static char argdiff[80];
                                        sprintf(argdiff, "incompatible argument %d (%s)", i, diff);
                                        return argdiff;
                                }
                                if (!arg1)
                                        break;
                                NEXT_PTR_LIST(arg1);
                                NEXT_PTR_LIST(arg2);
                                i++;
                        }
                        FINISH_PTR_LIST(arg2);
                        FINISH_PTR_LIST(arg1);
                }

                target = base1;
                source = base2;
        }
        return NULL;
}

static int is_null_ptr(struct expression *expr)
{
        if (expr->type != EXPR_VALUE || expr->value)
                return 0;
        if (!is_ptr_type(expr->ctype))
                warn(expr->pos, "Using plain integer as NULL pointer");
        return 1;
}

static struct symbol *common_ptr_type(struct expression *l, struct expression *r)
{
        /* NULL expression? Just return the type of the "other side" */
        if (is_null_ptr(r))
                return l->ctype;
        if (is_null_ptr(l))
                return r->ctype;
        return NULL;
}

/*
 * Ignore differences in "volatile" and "const"ness when
 * subtracting pointers
 */
#define MOD_IGN (MOD_VOLATILE | MOD_CONST)

static struct symbol *evaluate_ptr_sub(struct expression *expr, struct expression *l, struct expression *r)
{
        const char *typediff;
        struct symbol *ctype;
        struct symbol *ltype, *rtype;

        ltype = degenerate(l);
        rtype = degenerate(r);

        /*
         * If it is an integer subtract: the ptr add case will do the
         * right thing.
         */
        if (!is_ptr_type(rtype))
                return evaluate_ptr_add(expr, l, r);

        ctype = ltype;
        typediff = type_difference(ltype, rtype, ~MOD_SIZE, ~MOD_SIZE);
        if (typediff) {
                ctype = common_ptr_type(l, r);
                if (!ctype) {
                        warn(expr->pos, "subtraction of different types can't work (%s)", typediff);
                        return NULL;
                }
        }
        examine_symbol_type(ctype);

        /* Figure out the base type we point to */
        if (ctype->type == SYM_NODE)
                ctype = ctype->ctype.base_type;
        if (ctype->type != SYM_PTR && ctype->type != SYM_ARRAY) {
                warn(expr->pos, "subtraction of functions? Share your drugs");
                return NULL;
        }
        ctype = ctype->ctype.base_type;

        expr->ctype = ssize_t_ctype;
        if (ctype->bit_size > bits_in_char) {
                struct expression *sub = alloc_expression(expr->pos, EXPR_BINOP);
                struct expression *div = expr;
                struct expression *val = alloc_expression(expr->pos, EXPR_VALUE);

                val->ctype = size_t_ctype;
                val->value = ctype->bit_size >> 3;

                sub->op = '-';
                sub->ctype = ssize_t_ctype;
                sub->left = l;
                sub->right = r;

                div->op = '/';
                div->left = sub;
                div->right = val;
        }
                
        return ssize_t_ctype;
}

static struct symbol *evaluate_sub(struct expression *expr)
{
        struct expression *left = expr->left, *right = expr->right;
        struct symbol *ltype = left->ctype;

        if (is_ptr_type(ltype))
                return evaluate_ptr_sub(expr, left, right);

        return evaluate_arith(expr, 1);
}

#define is_safe_type(type) ((type)->ctype.modifiers & MOD_SAFE)

static struct symbol *evaluate_conditional(struct expression **p)
{
        struct symbol *ctype;
        struct expression *expr = *p;

        if (!expr)
                return NULL;

        if (expr->type == EXPR_ASSIGNMENT)
                warn(expr->pos, "assignment expression in conditional");

        ctype = evaluate_expression(expr);
        if (ctype) {
                if (is_safe_type(ctype))
                        warn(expr->pos, "testing a 'safe expression'");
                if (is_float_type(ctype)) {
                        struct expression *comp;
                        /*
                         * It's easier to handle here, rather than deal with
                         * FP all over the place.  Floating point in boolean
                         * context is rare enough (and very often wrong),
                         * so price of explicit comparison with appropriate
                         * FP zero is not too high.  And it simplifies things
                         * elsewhere.
                         */
                        comp = alloc_expression(expr->pos, EXPR_BINOP);
                        comp->op = SPECIAL_NOTEQUAL;
                        comp->left = expr;
                        comp->right = alloc_expression(expr->pos, EXPR_FVALUE);
                        comp->right->ctype = comp->left->ctype;
                        comp->right->fvalue = 0;
                        ctype = comp->ctype = &bool_ctype;
                        *p = comp;
                }
        }

        return ctype;
}

static struct symbol *evaluate_logical(struct expression *expr)
{
        if (!evaluate_conditional(&expr->left))
                return NULL;
        if (!evaluate_conditional(&expr->right))
                return NULL;

        expr->ctype = &bool_ctype;
        return &bool_ctype;
}

static struct symbol *evaluate_shift(struct expression *expr)
{
        struct expression *left = expr->left, *right = expr->right;
        struct symbol *ltype = left->ctype, *rtype = right->ctype;

        if (ltype->type == SYM_NODE)
                ltype = ltype->ctype.base_type;
        if (rtype->type == SYM_NODE)
                rtype = rtype->ctype.base_type;
        if (is_int_type(ltype) && is_int_type(rtype)) {
                struct symbol *ctype = integer_promotion(ltype);
                if (ltype->bit_size != ctype->bit_size)
                        expr->left = cast_to(expr->left, ctype);
                expr->ctype = ctype;
                ctype = integer_promotion(rtype);
                if (rtype->bit_size != ctype->bit_size)
                        expr->right = cast_to(expr->right, ctype);
                return expr->ctype;
        }
        return bad_expr_type(expr);
}

static struct symbol *evaluate_binop(struct expression *expr)
{
        switch (expr->op) {
        // addition can take ptr+int, fp and int
        case '+':
                return evaluate_add(expr);

        // subtraction can take ptr-ptr, fp and int
        case '-':
                return evaluate_sub(expr);

        // Arithmetic operations can take fp and int
        case '*': case '/':
                return evaluate_arith(expr, 1);

        // shifts do integer promotions, but that's it.
        case SPECIAL_LEFTSHIFT: case SPECIAL_RIGHTSHIFT:
                return evaluate_shift(expr);

        // The rest are integer operations
        // '%', '&', '^', '|'
        default:
                return evaluate_arith(expr, 0);
        }
}

static struct symbol *evaluate_comma(struct expression *expr)
{
        expr->ctype = expr->right->ctype;
        return expr->ctype;
}

static int modify_for_unsigned(int op)
{
        if (op == '<')
                op = SPECIAL_UNSIGNED_LT;
        else if (op == '>')
                op = SPECIAL_UNSIGNED_GT;
        else if (op == SPECIAL_LTE)
                op = SPECIAL_UNSIGNED_LTE;
        else if (op == SPECIAL_GTE)
                op = SPECIAL_UNSIGNED_GTE;
        return op;
}

static struct symbol *evaluate_compare(struct expression *expr)
{
        struct expression *left = expr->left, *right = expr->right;
        struct symbol *ltype = left->ctype, *rtype = right->ctype;
        struct symbol *ctype;

        /* Type types? */
        if (is_type_type(ltype) && is_type_type(rtype)) {
                expr->ctype = &bool_ctype;
                return &bool_ctype;
        }

        if (is_safe_type(ltype) || is_safe_type(rtype))
                warn(expr->pos, "testing a 'safe expression'");

        /* Pointer types? */
        if (is_ptr_type(ltype) || is_ptr_type(rtype)) {
                expr->ctype = &bool_ctype;
                // FIXME! Check the types for compatibility
                return &bool_ctype;
        }

        ctype = compatible_integer_binop(&expr->left, &expr->right);
        if (ctype) {
                if (ctype->ctype.modifiers & MOD_UNSIGNED)
                        expr->op = modify_for_unsigned(expr->op);
                expr->ctype = &bool_ctype;
                return &bool_ctype;
        }
        ctype = compatible_float_binop(&expr->left, &expr->right);
        if (ctype) {
                expr->ctype = &bool_ctype;
                return &bool_ctype;
        }

        return bad_expr_type(expr);
}

/*
 * FIXME!! This should do casts, array degeneration etc..
 */
static struct symbol *compatible_ptr_type(struct expression *left, struct expression *right)
{
        struct symbol *ltype = left->ctype, *rtype = right->ctype;

        if (ltype->type == SYM_NODE)
                ltype = ltype->ctype.base_type;

        if (rtype->type == SYM_NODE)
                rtype = rtype->ctype.base_type;

        if (ltype->type == SYM_PTR) {
                if (is_null_ptr(right) || rtype->ctype.base_type == &void_ctype)
                        return ltype;
        }

        if (rtype->type == SYM_PTR) {
                if (is_null_ptr(left) || ltype->ctype.base_type == &void_ctype)
                        return rtype;
        }
        return NULL;
}

static struct symbol * evaluate_conditional_expression(struct expression *expr)
{
        struct expression *cond, *true, *false;
        struct symbol *ctype, *ltype, *rtype;
        const char * typediff;

        ctype = degenerate(expr->conditional);
        cond = expr->conditional;

        ltype = ctype;
        true = cond;
        if (expr->cond_true) {
                ltype = degenerate(expr->cond_true);
                true = expr->cond_true;
        }

        rtype = degenerate(expr->cond_false);
        false = expr->cond_false;

        ctype = ltype;
        typediff = type_difference(ltype, rtype, MOD_IGN, MOD_IGN);
        if (!typediff)
                goto out;

        ctype = compatible_integer_binop(&true, &expr->cond_false);
        if (ctype)
                goto out;
        ctype = compatible_ptr_type(true, expr->cond_false);
        if (ctype)
                goto out;
        ctype = compatible_float_binop(&true, &expr->cond_false);
        if (ctype)
                goto out;
        warn(expr->pos, "incompatible types in conditional expression (%s)", typediff);
        return NULL;

out:
        expr->ctype = ctype;
        return ctype;
}
                
static int compatible_assignment_types(struct expression *expr, struct symbol *target,
        struct expression **rp, struct symbol *source, const char *where)
{
        const char *typediff;
        struct symbol *t;
        int target_as;

        /* It's ok if the target is more volatile or const than the source */
        typediff = type_difference(target, source, MOD_VOLATILE | MOD_CONST, 0);
        if (!typediff)
                return 1;

        if (is_int_type(target)) {
                if (is_int_type(source)) {
                        if (target->bit_size != source->bit_size)
                                goto Cast;
                        return 1;
                }
                if (is_float_type(source))
                        goto Cast;
        } else if (is_float_type(target)) {
                if (is_int_type(source))
                        goto Cast;
                if (is_float_type(source)) {
                        if (target->bit_size != source->bit_size)
                                goto Cast;
                        return 1;
                }
        }

        /* Pointer destination? */
        t = target;
        target_as = t->ctype.as;
        if (t->type == SYM_NODE) {
                t = t->ctype.base_type;
                target_as |= t->ctype.as;
        }
        if (t->type == SYM_PTR || t->type == SYM_FN || t->type == SYM_ARRAY) {
                struct expression *right = *rp;
                struct symbol *s = source;
                int source_as;

                // NULL pointer is always ok
                if (is_null_ptr(right))
                        return 1;

                /* "void *" matches anything as long as the address space is ok */
                source_as = s->ctype.as;
                if (s->type == SYM_NODE) {
                        s = s->ctype.base_type;
                        source_as |= s->ctype.as;
                }
                if (source_as == target_as && (s->type == SYM_PTR || s->type == SYM_ARRAY)) {
                        s = s->ctype.base_type;
                        t = t->ctype.base_type;
                        if (s == &void_ctype || t == &void_ctype)
                                return 1;
                }
        }

        warn(expr->pos, "incorrect type in %s (%s)", where, typediff);
        info(expr->pos, "   expected %s", show_typename(target));
        info(expr->pos, "   got %s", show_typename(source));
        *rp = cast_to(*rp, target);
        return 0;
Cast:
        *rp = cast_to(*rp, target);
        return 1;
}

/*
 * FIXME!! This is wrong from a double evaluation standpoint. We can't
 * just expand the expression twice, that would make any side effects
 * happen twice too.
 */
static struct symbol *evaluate_binop_assignment(struct expression *expr, struct expression *left, struct expression *right)
{
        int op = expr->op;
        struct expression *subexpr = alloc_expression(expr->pos, EXPR_BINOP);
        static const int op_trans[] = {
                [SPECIAL_ADD_ASSIGN - SPECIAL_BASE] = '+',
                [SPECIAL_SUB_ASSIGN - SPECIAL_BASE] = '-',
                [SPECIAL_MUL_ASSIGN - SPECIAL_BASE] = '*',
                [SPECIAL_DIV_ASSIGN - SPECIAL_BASE] = '/',
                [SPECIAL_MOD_ASSIGN - SPECIAL_BASE] = '%',
                [SPECIAL_SHL_ASSIGN - SPECIAL_BASE] = SPECIAL_LEFTSHIFT,
                [SPECIAL_SHR_ASSIGN - SPECIAL_BASE] = SPECIAL_RIGHTSHIFT,
                [SPECIAL_AND_ASSIGN - SPECIAL_BASE] = '&',
                [SPECIAL_OR_ASSIGN - SPECIAL_BASE] = '|',
                [SPECIAL_XOR_ASSIGN - SPECIAL_BASE] = '^'
        };
        struct expression *e0, *e1, *e2, *e3, *e4, *e5;
        struct symbol *a = alloc_symbol(expr->pos, SYM_NODE);
        struct symbol *ltype = left->ctype;
        struct expression *addr;
        struct symbol *lptype;

        if (left->type == EXPR_BITFIELD)
                addr = left->address;
        else
                addr = left->unop;

        lptype = addr->ctype;

        a->ctype.base_type = lptype;
        a->bit_size = lptype->bit_size;
        a->array_size = lptype->array_size;

        e0 = alloc_expression(expr->pos, EXPR_SYMBOL);
        e0->symbol = a;
        e0->ctype = &lazy_ptr_ctype;

        e1 = alloc_expression(expr->pos, EXPR_PREOP);
        e1->unop = e0;
        e1->op = '*';
        e1->ctype = lptype;

        e2 = alloc_expression(expr->pos, EXPR_ASSIGNMENT);
        e2->left = e1;
        e2->right = addr;
        e2->op = '=';
        e2->ctype = lptype;

        /* we can't cannibalize left, unfortunately */
        e3 = alloc_expression(expr->pos, left->type);
        *e3 = *left;
        if (e3->type == EXPR_BITFIELD)
                e3->address = e1;
        else
                e3->unop = e1;

        e4 = alloc_expression(expr->pos, EXPR_BINOP);
        e4->op = subexpr->op = op_trans[op - SPECIAL_BASE];
        e4->left = e3;
        e4->right = right;
        /* will calculate type later */

        e5 = alloc_expression(expr->pos, EXPR_ASSIGNMENT);
        e5->left = e3;  /* we can share that one */
        e5->right = e4;
        e5->op = '=';
        e5->ctype = ltype;

        expr->type = EXPR_COMMA;
        expr->left = e2;
        expr->right = e5;
        expr->ctype = ltype;

        return evaluate_binop(e4);
}

static void evaluate_assign_to(struct expression *left, struct symbol *type)
{
        if (type->ctype.modifiers & MOD_CONST)
                warn(left->pos, "assignment to const expression");
        if (type->type == SYM_NODE)
                type->ctype.modifiers |= MOD_ASSIGNED;
}

static struct symbol *evaluate_assignment(struct expression *expr)
{
        struct expression *left = expr->left, *right = expr->right;
        struct expression *where = expr;
        struct symbol *ltype, *rtype;

        if (!lvalue_expression(left)) {
                warn(expr->pos, "not an lvalue");
                return NULL;
        }

        ltype = left->ctype;

        if (expr->op != '=') {
                if (!evaluate_binop_assignment(expr, left, right))
                        return NULL;
                where = expr->right;    /* expr is EXPR_COMMA now */
                left = where->left;
                right = where->right;
        }

        rtype = degenerate(right);

        if (!compatible_assignment_types(where, ltype, &where->right, rtype, "assignment"))
                return NULL;

        evaluate_assign_to(left, ltype);

        expr->ctype = ltype;
        return ltype;
}

static void examine_fn_arguments(struct symbol *fn)
{
        struct symbol *s;

        FOR_EACH_PTR(fn->arguments, s) {
                struct symbol *arg = evaluate_symbol(s);
                /* Array/function arguments silently degenerate into pointers */
                if (arg) {
                        struct symbol *ptr;
                        switch(arg->type) {
                        case SYM_ARRAY:
                        case SYM_FN:
                                ptr = alloc_symbol(s->pos, SYM_PTR);
                                if (arg->type == SYM_ARRAY)
                                        ptr->ctype = arg->ctype;
                                else
                                        ptr->ctype.base_type = arg;
                                ptr->ctype.as |= s->ctype.as;
                                ptr->ctype.modifiers |= s->ctype.modifiers;

                                s->ctype.base_type = ptr;
                                s->ctype.as = 0;
                                s->ctype.modifiers = 0;
                                examine_symbol_type(s);
                                break;
                        default:
                                /* nothing */
                                break;
                        }
                }
        } END_FOR_EACH_PTR;
}

static struct symbol *convert_to_as_mod(struct symbol *sym, int as, int mod)
{
        if (sym->ctype.as != as || sym->ctype.modifiers != mod) {
                struct symbol *newsym = alloc_symbol(sym->pos, SYM_NODE);
                *newsym = *sym;
                newsym->ctype.as = as;
                newsym->ctype.modifiers = mod;
                sym = newsym;
        }
        return sym;
}

static struct symbol *create_pointer(struct expression *expr, struct symbol *sym, int degenerate)
{
        struct symbol *node = alloc_symbol(expr->pos, SYM_NODE);
        struct symbol *ptr = alloc_symbol(expr->pos, SYM_PTR);

        node->ctype.base_type = ptr;
        ptr->bit_size = bits_in_pointer;
        ptr->ctype.alignment = pointer_alignment;

        node->bit_size = bits_in_pointer;
        node->ctype.alignment = pointer_alignment;

        access_symbol(sym);
        sym->ctype.modifiers |= MOD_ADDRESSABLE;
        if (sym->ctype.modifiers & MOD_REGISTER) {
                warn(expr->pos, "taking address of 'register' variable '%s'", show_ident(sym->ident));
                sym->ctype.modifiers &= ~MOD_REGISTER;
        }
        if (sym->type == SYM_NODE) {
                ptr->ctype.as |= sym->ctype.as;
                ptr->ctype.modifiers |= sym->ctype.modifiers;
                sym = sym->ctype.base_type;
        }
        if (degenerate && sym->type == SYM_ARRAY) {
                ptr->ctype.as |= sym->ctype.as;
                ptr->ctype.modifiers |= sym->ctype.modifiers;
                sym = sym->ctype.base_type;
        }
        ptr->ctype.base_type = sym;

        return node;
}

/* Arrays degenerate into pointers on pointer arithmetic */
static struct symbol *degenerate(struct expression *expr)
{
        struct symbol *ctype, *base;

        if (!expr)
                return NULL;
        ctype = expr->ctype;
        if (!ctype)
                return NULL;
        base = ctype;
        if (ctype->type == SYM_NODE)
                base = ctype->ctype.base_type;
        /*
         * Arrays degenerate into pointers to the entries, while
         * functions degenerate into pointers to themselves.
         * If array was part of non-lvalue compound, we create a copy
         * of that compound first and then act as if we were dealing with
         * the corresponding field in there.
         */
        switch (base->type) {
        case SYM_ARRAY:
                if (expr->type == EXPR_SLICE) {
                        struct symbol *a = alloc_symbol(expr->pos, SYM_NODE);
                        struct expression *e0, *e1, *e2, *e3, *e4;

                        a->ctype.base_type = expr->base->ctype;
                        a->bit_size = expr->base->ctype->bit_size;
                        a->array_size = expr->base->ctype->array_size;

                        e0 = alloc_expression(expr->pos, EXPR_SYMBOL);
                        e0->symbol = a;
                        e0->ctype = &lazy_ptr_ctype;

                        e1 = alloc_expression(expr->pos, EXPR_PREOP);
                        e1->unop = e0;
                        e1->op = '*';
                        e1->ctype = expr->base->ctype;  /* XXX */

                        e2 = alloc_expression(expr->pos, EXPR_ASSIGNMENT);
                        e2->left = e1;
                        e2->right = expr->base;
                        e2->op = '=';
                        e2->ctype = expr->base->ctype;

                        if (expr->r_bitpos) {
                                e3 = alloc_expression(expr->pos, EXPR_BINOP);
                                e3->op = '+';
                                e3->left = e0;
                                e3->right = alloc_const_expression(expr->pos,
                                                        expr->r_bitpos >> 3);
                                e3->ctype = &lazy_ptr_ctype;
                        } else {
                                e3 = e0;
                        }

                        e4 = alloc_expression(expr->pos, EXPR_COMMA);
                        e4->left = e2;
                        e4->right = e3;
                        e4->ctype = &lazy_ptr_ctype;

                        expr->unop = e4;
                        expr->type = EXPR_PREOP;
                        expr->op = '*';
                }
        case SYM_FN:
                if (expr->op != '*' || expr->type != EXPR_PREOP) {
                        warn(expr->pos, "strange non-value function or array");
                        return NULL;
                }
                *expr = *expr->unop;
                ctype = create_pointer(expr, ctype, 1);
                expr->ctype = ctype;
        default:
                /* nothing */;
        }
        return ctype;
}

static struct symbol *evaluate_addressof(struct expression *expr)
{
        struct expression *op = expr->unop;
        struct symbol *ctype;

        if (op->op != '*' || op->type != EXPR_PREOP) {
                warn(expr->pos, "not addressable");
                return NULL;
        }
        ctype = op->ctype;
        *expr = *op->unop;

        /*
         * symbol expression evaluation is lazy about the type
         * of the sub-expression, so we may have to generate
         * the type here if so..
         */
        if (expr->ctype == &lazy_ptr_ctype) {
                ctype = create_pointer(expr, ctype, 0);
                expr->ctype = ctype;
        }
        return expr->ctype;
}


static struct symbol *evaluate_dereference(struct expression *expr)
{
        struct expression *op = expr->unop;
        struct symbol *ctype = op->ctype, *node, *target;

        /* Simplify: *&(expr) => (expr) */
        if (op->type == EXPR_PREOP && op->op == '&') {
                *expr = *op->unop;
                return expr->ctype;
        }

        /* Dereferencing a node drops all the node information. */
        if (ctype->type == SYM_NODE)
                ctype = ctype->ctype.base_type;

        node = alloc_symbol(expr->pos, SYM_NODE);
        target = ctype->ctype.base_type;

        switch (ctype->type) {
        default:
                warn(expr->pos, "cannot derefence this type");
                return NULL;
        case SYM_PTR:
                merge_type(node, ctype);
                if (ctype->type != SYM_ARRAY)
                        break;
                /*
                 * Dereferencing a pointer to an array results in a
                 * degenerate dereference: the expression becomes
                 * just a pointer to the entry, and the derefence
                 * goes away.
                 */
                *expr = *op;

                target = alloc_symbol(expr->pos, SYM_PTR);
                target->bit_size = bits_in_pointer;
                target->ctype.alignment = pointer_alignment;
                merge_type(target, ctype->ctype.base_type);
                break;

        case SYM_ARRAY:
                if (!lvalue_expression(op)) {
                        warn(op->pos, "non-lvalue array??");
                        return NULL;
                }

                /* Do the implied "addressof" on the array */
                *op = *op->unop;

                /*
                 * When an array is dereferenced, we need to pick
                 * up the attributes of the original node too..
                 */
                merge_type(node, op->ctype);
                merge_type(node, ctype);
                break;
        }

        node->bit_size = target->bit_size;
        node->array_size = target->array_size;

        expr->ctype = node;
        return node;
}

/*
 * Unary post-ops: x++ and x--
 */
static struct symbol *evaluate_postop(struct expression *expr)
{
        struct expression *op = expr->unop;
        struct symbol *ctype = op->ctype;

        if (!lvalue_expression(expr->unop)) {
                warn(expr->pos, "need lvalue expression for ++/--");
                return NULL;
        }

        evaluate_assign_to(op, ctype);

        expr->ctype = ctype;
        return ctype;
}

static struct symbol *evaluate_sign(struct expression *expr)
{
        struct symbol *ctype = expr->unop->ctype;
        if (is_int_type(ctype)) {
                struct symbol *rtype = rtype = integer_promotion(ctype);
                if (rtype->bit_size != ctype->bit_size)
                        expr->unop = cast_to(expr->unop, rtype);
                ctype = rtype;
        } else if (is_float_type(ctype) && expr->op != '~') {
                /* no conversions needed */
        } else {
                return bad_expr_type(expr);
        }
        if (expr->op == '+')
                *expr = *expr->unop;
        expr->ctype = ctype;
        return ctype;
}

static struct symbol *evaluate_preop(struct expression *expr)
{
        struct symbol *ctype = expr->unop->ctype;

        switch (expr->op) {
        case '(':
                *expr = *expr->unop;
                return ctype;

        case '+':
        case '-':
        case '~':
                return evaluate_sign(expr);

        case '*':
                return evaluate_dereference(expr);

        case '&':
                return evaluate_addressof(expr);

        case SPECIAL_INCREMENT:
        case SPECIAL_DECREMENT:
                /*
                 * From a type evaluation standpoint the pre-ops are
                 * the same as the postops
                 */
                return evaluate_postop(expr);

        case '!':
                if (is_safe_type(ctype))
                        warn(expr->pos, "testing a 'safe expression'");
                if (is_float_type(ctype)) {
                        struct expression *arg = expr->unop;
                        expr->type = EXPR_BINOP;
                        expr->op = SPECIAL_EQUAL;
                        expr->left = arg;
                        expr->right = alloc_expression(expr->pos, EXPR_FVALUE);
                        expr->right->ctype = ctype;
                        expr->right->fvalue = 0;
                }
                ctype = &bool_ctype;
                break;

        default:
                break;
        }
        expr->ctype = ctype;
        return &bool_ctype;
}

struct symbol *find_identifier(struct ident *ident, struct symbol_list *_list, int *offset)
{
        struct ptr_list *head = (struct ptr_list *)_list;
        struct ptr_list *list = head;

        if (!head)
                return NULL;
        do {
                int i;
                for (i = 0; i < list->nr; i++) {
                        struct symbol *sym = (struct symbol *) list->list[i];
                        if (sym->ident) {
                                if (sym->ident != ident)
                                        continue;
                                *offset = sym->offset;
                                return sym;
                        } else {
                                struct symbol *ctype = sym->ctype.base_type;
                                struct symbol *sub;
                                if (!ctype)
                                        continue;
                                if (ctype->type != SYM_UNION && ctype->type != SYM_STRUCT)
                                        continue;
                                sub = find_identifier(ident, ctype->symbol_list, offset);
                                if (!sub)
                                        continue;
                                *offset += sym->offset;
                                return sub;
                        }       
                }
        } while ((list = list->next) != head);
        return NULL;
}

static struct expression *evaluate_offset(struct expression *expr, unsigned long offset)
{
        struct expression *add;

        /*
         * Create a new add-expression
         *
         * NOTE! Even if we just add zero, we need a new node
         * for the member pointer, since it has a different
         * type than the original pointer. We could make that
         * be just a cast, but the fact is, a node is a node,
         * so we might as well just do the "add zero" here.
         */
        add = alloc_expression(expr->pos, EXPR_BINOP);
        add->op = '+';
        add->left = expr;
        add->right = alloc_expression(expr->pos, EXPR_VALUE);
        add->right->ctype = &int_ctype;
        add->right->value = offset;

        /*
         * The ctype of the pointer will be lazily evaluated if
         * we ever take the address of this member dereference..
         */
        add->ctype = &lazy_ptr_ctype;
        return add;
}

/* structure/union dereference */
static struct symbol *evaluate_member_dereference(struct expression *expr)
{
        int offset;
        struct symbol *ctype, *member;
        struct expression *deref = expr->deref, *add;
        struct ident *ident = expr->member;
        unsigned int mod;
        int address_space;

        if (!evaluate_expression(deref))
                return NULL;
        if (!ident) {
                warn(expr->pos, "bad member name");
                return NULL;
        }

        ctype = deref->ctype;
        address_space = ctype->ctype.as;
        mod = ctype->ctype.modifiers;
        if (ctype->type == SYM_NODE) {
                ctype = ctype->ctype.base_type;
                address_space |= ctype->ctype.as;
                mod |= ctype->ctype.modifiers;
        }
        if (!ctype || (ctype->type != SYM_STRUCT && ctype->type != SYM_UNION)) {
                warn(expr->pos, "expected structure or union");
                return NULL;
        }
        offset = 0;
        member = find_identifier(ident, ctype->symbol_list, &offset);
        if (!member) {
                const char *type = ctype->type == SYM_STRUCT ? "struct" : "union";
                const char *name = "<unnamed>";
                int namelen = 9;
                if (ctype->ident) {
                        name = ctype->ident->name;
                        namelen = ctype->ident->len;
                }
                warn(expr->pos, "no member '%s' in %s %.*s",
                        show_ident(ident), type, namelen, name);
                return NULL;
        }

        /*
         * The member needs to take on the address space and modifiers of
         * the "parent" type.
         */
        member = convert_to_as_mod(member, address_space, mod);
        ctype = member->ctype.base_type;

        if (!lvalue_expression(deref)) {
                if (deref->type != EXPR_SLICE) {
                        expr->base = deref;
                        expr->r_bitpos = 0;
                } else {
                        expr->base = deref->base;
                        expr->r_bitpos = deref->r_bitpos;
                }
                expr->r_bitpos += offset << 3;
                expr->type = EXPR_SLICE;
                if (ctype->type == SYM_BITFIELD) {
                        expr->r_bitpos += member->bit_offset;
                        expr->r_nrbits = member->fieldwidth;
                } else {
                        expr->r_nrbits = member->bit_size;
                }
                expr->ctype = member;
                return member;
        }

        deref = deref->unop;
        expr->deref = deref;

        add = evaluate_offset(deref, offset);
        if (ctype->type == SYM_BITFIELD) {
                expr->type = EXPR_BITFIELD;
                expr->bitpos = member->bit_offset;
                expr->nrbits = member->fieldwidth;
                expr->address = add;
        } else {
                expr->type = EXPR_PREOP;
                expr->op = '*';
                expr->unop = add;
        }

        expr->ctype = member;
        return member;
}

static struct symbol *evaluate_cast(struct expression *);

static struct symbol *evaluate_sizeof(struct expression *expr)
{
        int size;

        if (expr->cast_type) {
                if (expr->cast_expression) {
                        struct symbol *sym = evaluate_cast(expr);
                        size = sym->bit_size;
                } else {
                        examine_symbol_type(expr->cast_type);
                        size = expr->cast_type->bit_size;
                }
        } else {
                if (!evaluate_expression(expr->cast_expression))
                        return NULL;
                size = expr->cast_expression->ctype->bit_size;
                if (is_bitfield_type (expr->cast_expression->ctype))
                        warn(expr->pos, "sizeof applied to bitfield type");
        }
        if (size & 7)
                warn(expr->pos, "cannot size expression");
        expr->type = EXPR_VALUE;
        expr->value = size >> 3;
        expr->ctype = size_t_ctype;
        return size_t_ctype;
}

static struct symbol *evaluate_alignof(struct expression *expr)
{
        struct symbol *type = expr->cast_type;

        if (!type) {
                type = evaluate_expression(expr->cast_expression);
                if (!type)
                        return NULL;
        }
        if (is_bitfield_type(type))
                warn(expr->pos, "alignof applied to bitfield type");
        examine_symbol_type(type);
        expr->type = EXPR_VALUE;
        expr->value = type->ctype.alignment;
        expr->ctype = size_t_ctype;
        return size_t_ctype;
}

static int context_clash(struct symbol *sym1, struct symbol *sym2)
{
        unsigned long clash = (sym1->ctype.context ^ sym2->ctype.context);
        clash &= (sym1->ctype.contextmask & sym2->ctype.contextmask);
        return clash != 0;
}

static int evaluate_arguments(struct symbol *f, struct symbol *fn, struct expression_list *head)
{
        struct expression *expr;
        struct symbol_list *argument_types = fn->arguments;
        struct symbol *argtype;
        int i = 1;

        PREPARE_PTR_LIST(argument_types, argtype);
        FOR_EACH_PTR (head, expr) {
                struct expression **p = THIS_ADDRESS(expr);
                struct symbol *ctype, *target;
                ctype = evaluate_expression(expr);

                if (!ctype)
                        return 0;

                if (context_clash(f, ctype))
                        warn(expr->pos, "argument %d used in wrong context", i);

                ctype = degenerate(expr);

                target = argtype;
                if (!target && ctype->bit_size < bits_in_int)
                        target = &int_ctype;
                if (target) {
                        static char where[30];
                        examine_symbol_type(target);
                        sprintf(where, "argument %d", i);
                        compatible_assignment_types(expr, target, p, ctype, where);
                }

                i++;
                NEXT_PTR_LIST(argtype);
        } END_FOR_EACH_PTR;
        FINISH_PTR_LIST(argtype);
        return 1;
}

static int evaluate_initializer(struct symbol *ctype, struct expression **ep, unsigned long offset);
static int evaluate_array_initializer(struct symbol *ctype, struct expression *expr, unsigned long offset)
{
        struct expression *entry;
        int current = 0;
        int max = 0;
        int accept_string = is_byte_type(ctype);

        FOR_EACH_PTR(expr->expr_list, entry) {
                struct expression **p = THIS_ADDRESS(entry);
                struct symbol *sym;
                int entries;

                if (entry->type == EXPR_INDEX) {
                        current = entry->idx_to;
                        continue;
                }
                if (accept_string && entry->type == EXPR_STRING) {
                        sym = evaluate_expression(entry);
                        entries = get_expression_value(sym->array_size);
                } else {
                        evaluate_initializer(ctype, p, offset + current*(ctype->bit_size>>3));
                        entries = 1;
                }
                current += entries;
                if (current > max)
                        max = current;
        } END_FOR_EACH_PTR;
        return max;
}

/* A scalar initializer is allowed, and acts pretty much like an array of one */
static int evaluate_scalar_initializer(struct symbol *ctype, struct expression *expr, unsigned long offset)
{
        if (offset || expression_list_size(expr->expr_list) != 1) {
                warn(expr->pos, "unexpected compound initializer");
                return 0;
        }
        return evaluate_array_initializer(ctype, expr, 0);
}

static int evaluate_struct_or_union_initializer(struct symbol *ctype, struct expression *expr, int multiple, unsigned long offset)
{
        struct expression *entry;
        struct symbol *sym;

        PREPARE_PTR_LIST(ctype->symbol_list, sym);
        FOR_EACH_PTR(expr->expr_list, entry) {
                struct expression **p = THIS_ADDRESS(entry);

                if (entry->type == EXPR_IDENTIFIER) {
                        struct ident *ident = entry->expr_ident;
                        /* We special-case the "already right place" case */
                        if (sym && sym->ident == ident)
                                continue;
                        RESET_PTR_LIST(sym);
                        for (;;) {
                                if (!sym) {
                                        warn(entry->pos, "unknown named initializer '%s'", show_ident(ident));
                                        return 0;
                                }
                                if (sym->ident == ident)
                                        break;
                                NEXT_PTR_LIST(sym);
                        }
                        continue;
                }

                if (!sym) {
                        warn(expr->pos, "too many initializers for struct/union");
                        return 0;
                }

                evaluate_initializer(sym, p, offset + sym->offset);

                NEXT_PTR_LIST(sym);
        } END_FOR_EACH_PTR;
        FINISH_PTR_LIST(sym);

        return 0;
}

/*
 * Initializers are kind of like assignments. Except
 * they can be a hell of a lot more complex.
 */
static int evaluate_initializer(struct symbol *ctype, struct expression **ep, unsigned long offset)
{
        struct expression *expr = *ep;

        /*
         * Simple non-structure/array initializers are the simple 
         * case, and look (and parse) largely like assignments.
         */
        if (expr->type != EXPR_INITIALIZER) {
                int size = 0, is_string = expr->type == EXPR_STRING;
                struct symbol *rtype = evaluate_expression(expr);
                if (rtype) {
                        struct expression *pos;

                        /*
                         * Special case:
                         *      char array[] = "string"
                         * should _not_ degenerate.
                         */
                        if (is_string && is_string_type(ctype)) {
                                struct expression *array_size = ctype->array_size;
                                if (!array_size)
                                        array_size = ctype->array_size = rtype->array_size;
                                size = get_expression_value(array_size);
                        } else {
                                rtype = degenerate(expr);
                                size = 1;
                        }
                        compatible_assignment_types(expr, ctype, ep, rtype, "initializer");

                        /*
                         * Don't bother creating a position expression for
                         * the simple initializer cases that don't need it.
                         *
                         * We need a position if the initializer has a byte
                         * offset, _or_ if we're initializing a bitfield.
                         */
                        if (offset || ctype->fieldwidth) {
                                pos = alloc_expression(expr->pos, EXPR_POS);
                                pos->init_offset = offset;
                                pos->init_sym = ctype;
                                pos->init_expr = *ep;
                                pos->ctype = expr->ctype;
                                *ep = pos;
                        }
                }
                return size;
        }

        expr->ctype = ctype;
        if (ctype->type == SYM_NODE)
                ctype = ctype->ctype.base_type;

        switch (ctype->type) {
        case SYM_ARRAY:
        case SYM_PTR:
                return evaluate_array_initializer(ctype->ctype.base_type, expr, offset);
        case SYM_UNION:
                return evaluate_struct_or_union_initializer(ctype, expr, 0, offset);
        case SYM_STRUCT:
                return evaluate_struct_or_union_initializer(ctype, expr, 1, offset);
        default:
                return evaluate_scalar_initializer(ctype, expr, offset);
        }
}

static int get_as(struct symbol *sym)
{
        int as;
        unsigned long mod;

        if (!sym)
                return 0;
        as = sym->ctype.as;
        mod = sym->ctype.modifiers;
        if (sym->type == SYM_NODE) {
                sym = sym->ctype.base_type;
                as |= sym->ctype.as;
                mod |= sym->ctype.modifiers;
        }

        /*
         * At least for now, allow casting to a "unsigned long".
         * That's how we do things like pointer arithmetic and
         * store pointers to registers.
         */
        if (sym == &ulong_ctype)
                return -1;

        if (sym && sym->type == SYM_PTR) {
                sym = sym->ctype.base_type;
                as |= sym->ctype.as;
                mod |= sym->ctype.modifiers;
        }
        if (mod & MOD_FORCE)
                return -1;
        return as;
}

static struct symbol *evaluate_cast(struct expression *expr)
{
        struct expression *target = expr->cast_expression;
        struct symbol *ctype = examine_symbol_type(expr->cast_type);
        enum type type;

        expr->ctype = ctype;
        expr->cast_type = ctype;

        /*
         * Special case: a cast can be followed by an
         * initializer, in which case we need to pass
         * the type value down to that initializer rather
         * than trying to evaluate it as an expression
         *
         * A more complex case is when the initializer is
         * dereferenced as part of a post-fix expression.
         * We need to produce an expression that can be dereferenced.
         */
        if (target->type == EXPR_INITIALIZER) {
                struct symbol *sym = expr->cast_type;
                struct expression *addr = alloc_expression(expr->pos, EXPR_SYMBOL);

                sym->initializer = expr->cast_expression;
                evaluate_symbol(sym);

                addr->ctype = &lazy_ptr_ctype;  /* Lazy eval */
                addr->symbol = sym;

                expr->type = EXPR_PREOP;
                expr->op = '*';
                expr->unop = addr;
                expr->ctype = sym;

                return sym;
        }

        evaluate_expression(target);
        degenerate(target);

        /*
         * You can always throw a value away by casting to
         * "void" - that's an implicit "force". Note that
         * the same is _not_ true of "void *".
         */
        if (ctype == &void_ctype)
                goto out;

        type = ctype->type;
        if (type == SYM_NODE) {
                type = ctype->ctype.base_type->type;
                if (ctype->ctype.base_type == &void_ctype)
                        goto out;
        }
        if (type == SYM_ARRAY || type == SYM_UNION || type == SYM_STRUCT)
                warn(expr->pos, "cast to non-scalar");

        if (!target->ctype) {
                warn(expr->pos, "cast from unknown type");
                goto out;
        }

        type = target->ctype->type;
        if (type == SYM_NODE)
                type = target->ctype->ctype.base_type->type;
        if (type == SYM_ARRAY || type == SYM_UNION || type == SYM_STRUCT)
                warn(expr->pos, "cast from non-scalar");

        if (!get_as(ctype) && get_as(target->ctype) > 0)
                warn(expr->pos, "cast removes address space of expression");

        /*
         * Casts of constant values are special: they
         * can be NULL, and thus need to be simplified
         * early.
         */
        if (target->type == EXPR_VALUE)
                cast_value(expr, ctype, target, target->ctype);

out:
        return ctype;
}

/*
 * Evaluate a call expression with a symbol. This
 * should expand inline functions, and evaluate
 * builtins.
 */
static int evaluate_symbol_call(struct expression *expr)
{
        struct expression *fn = expr->fn;
        struct symbol *ctype = fn->ctype;

        if (fn->type != EXPR_PREOP)
                return 0;

        if (ctype->op && ctype->op->evaluate)
                return ctype->op->evaluate(expr);

        if (ctype->ctype.modifiers & MOD_INLINE) {
                int ret;
                struct symbol *curr = current_fn;
                unsigned long context = current_context;
                unsigned long mask = current_contextmask;

                current_context |= ctype->ctype.context;
                current_contextmask |= ctype->ctype.contextmask;
                current_fn = ctype->ctype.base_type;
                examine_fn_arguments(current_fn);

                ret = inline_function(expr, ctype);

                /* restore the old function context */
                current_fn = curr;
                current_context = context;
                current_contextmask = mask;
                return ret;
        }

        return 0;
}

static struct symbol *evaluate_call(struct expression *expr)
{
        int args, fnargs;
        struct symbol *ctype, *sym;
        struct expression *fn = expr->fn;
        struct expression_list *arglist = expr->args;

        if (!evaluate_expression(fn))
                return NULL;
        sym = ctype = fn->ctype;
        if (ctype->type == SYM_NODE)
                ctype = ctype->ctype.base_type;
        if (ctype->type == SYM_PTR || ctype->type == SYM_ARRAY)
                ctype = ctype->ctype.base_type;
        if (!evaluate_arguments(sym, ctype, arglist))
                return NULL;
        if (ctype->type != SYM_FN) {
                warn(expr->pos, "not a function %s", show_ident(sym->ident));
                return NULL;
        }
        args = expression_list_size(expr->args);
        fnargs = symbol_list_size(ctype->arguments);
        if (args < fnargs)
                warn(expr->pos, "not enough arguments for function %s", show_ident(sym->ident));
        if (args > fnargs && !ctype->variadic)
                warn(expr->pos, "too many arguments for function %s", show_ident(sym->ident));
        if (sym->type == SYM_NODE) {
                if (evaluate_symbol_call(expr))
                        return expr->ctype;
        }
        expr->ctype = ctype->ctype.base_type;
        return expr->ctype;
}

struct symbol *evaluate_expression(struct expression *expr)
{
        if (!expr)
                return NULL;
        if (expr->ctype)
                return expr->ctype;

        switch (expr->type) {
        case EXPR_VALUE:
        case EXPR_FVALUE:
                warn(expr->pos, "value expression without a type");
                return NULL;
        case EXPR_STRING:
                return evaluate_string(expr);
        case EXPR_SYMBOL:
                return evaluate_symbol_expression(expr);
        case EXPR_BINOP:
                if (!evaluate_expression(expr->left))
                        return NULL;
                if (!evaluate_expression(expr->right))
                        return NULL;
                return evaluate_binop(expr);
        case EXPR_LOGICAL:
                return evaluate_logical(expr);
        case EXPR_COMMA:
                evaluate_expression(expr->left);
                if (!evaluate_expression(expr->right))
                        return NULL;
                return evaluate_comma(expr);
        case EXPR_COMPARE:
                if (!evaluate_expression(expr->left))
                        return NULL;
                if (!evaluate_expression(expr->right))
                        return NULL;
                return evaluate_compare(expr);
        case EXPR_ASSIGNMENT:
                if (!evaluate_expression(expr->left))
                        return NULL;
                if (!evaluate_expression(expr->right))
                        return NULL;
                return evaluate_assignment(expr);
        case EXPR_PREOP:
                if (!evaluate_expression(expr->unop))
                        return NULL;
                return evaluate_preop(expr);
        case EXPR_POSTOP:
                if (!evaluate_expression(expr->unop))
                        return NULL;
                return evaluate_postop(expr);
        case EXPR_CAST:
                return evaluate_cast(expr);
        case EXPR_SIZEOF:
                return evaluate_sizeof(expr);
        case EXPR_ALIGNOF:
                return evaluate_alignof(expr);
        case EXPR_DEREF:
                return evaluate_member_dereference(expr);
        case EXPR_CALL:
                return evaluate_call(expr);
        case EXPR_BITFIELD:
                warn(expr->pos, "bitfield generated by parser");
                return NULL;
        case EXPR_SELECT:
        case EXPR_CONDITIONAL:
                if (!evaluate_conditional(&expr->conditional))
                        return NULL;
                if (!evaluate_expression(expr->cond_false))
                        return NULL;
                if (expr->cond_true && !evaluate_expression(expr->cond_true))
                        return NULL;
                return evaluate_conditional_expression(expr);
        case EXPR_STATEMENT:
                expr->ctype = evaluate_statement(expr->statement);
                return expr->ctype;

        case EXPR_LABEL:
                expr->ctype = &ptr_ctype;
                return &ptr_ctype;

        case EXPR_TYPE:
                /* Evaluate the type of the symbol .. */
                evaluate_symbol(expr->symbol);
                /* .. but the type of the _expression_ is a "type" */
                expr->ctype = &type_ctype;
                return &type_ctype;

        /* These can not exist as stand-alone expressions */
        case EXPR_INITIALIZER:
        case EXPR_IDENTIFIER:
        case EXPR_INDEX:
        case EXPR_POS:
                warn(expr->pos, "internal front-end error: initializer in expression");
                return NULL;
        case EXPR_SLICE:
                warn(expr->pos, "internal front-end error: SLICE re-evaluated");
                return NULL;
        }
        return NULL;
}

void check_duplicates(struct symbol *sym)
{
        struct symbol *next = sym;

        while ((next = next->same_symbol) != NULL) {
                const char *typediff;
                evaluate_symbol(next);
                typediff = type_difference(sym, next, 0, 0);
                if (typediff) {
                        warn(sym->pos, "symbol '%s' redeclared with different type (originally declared at %s:%d) - %s",
                                show_ident(sym->ident),
                                input_streams[next->pos.stream].name, next->pos.line, typediff);
                        return;
                }
        }
}

struct symbol *evaluate_symbol(struct symbol *sym)
{
        struct symbol *base_type;

        if (!sym)
                return sym;

        sym = examine_symbol_type(sym);
        base_type = sym->ctype.base_type;
        if (!base_type)
                return NULL;

        /* Evaluate the initializers */
        if (sym->initializer) {
                int count = evaluate_initializer(sym, &sym->initializer, 0);
                if (base_type->type == SYM_ARRAY && !base_type->array_size) {
                        int bit_size = count * base_type->ctype.base_type->bit_size;
                        base_type->array_size = alloc_const_expression(sym->pos, count);
                        base_type->bit_size = bit_size;
                        sym->array_size = base_type->array_size;
                        sym->bit_size = bit_size;
                }
        }

        /* And finally, evaluate the body of the symbol too */
        if (base_type->type == SYM_FN) {
                struct symbol *curr = current_fn;
                unsigned long context = current_context;
                unsigned long mask = current_contextmask;

                current_fn = base_type;
                current_contextmask = sym->ctype.contextmask;
                current_context = sym->ctype.context;

                examine_fn_arguments(base_type);
                if (!base_type->stmt && base_type->inline_stmt)
                        uninline(sym);
                if (base_type->stmt)
                        evaluate_statement(base_type->stmt);

                current_fn = curr;
                current_contextmask = mask;
                current_context = context;
        }

        return base_type;
}

struct symbol *evaluate_return_expression(struct statement *stmt)
{
        struct expression *expr = stmt->expression;
        struct symbol *ctype, *fntype;

        evaluate_expression(expr);
        ctype = degenerate(expr);
        fntype = current_fn->ctype.base_type;
        if (!fntype || fntype == &void_ctype) {
                if (expr && ctype != &void_ctype)
                        warn(expr->pos, "return expression in %s function", fntype?"void":"typeless");
                return NULL;
        }

        if (!expr) {
                warn(stmt->pos, "return with no return value");
                return NULL;
        }
        if (!ctype)
                return NULL;
        compatible_assignment_types(expr, fntype, &stmt->expression, ctype, "return expression");
        return NULL;
}

static void evaluate_if_statement(struct statement *stmt)
{
        if (!stmt->if_conditional)
                return;

        evaluate_conditional(&stmt->if_conditional);
        evaluate_statement(stmt->if_true);
        evaluate_statement(stmt->if_false);
}

static void evaluate_iterator(struct statement *stmt)
{
        struct expression **pre = &stmt->iterator_pre_condition;
        struct expression **post = &stmt->iterator_post_condition;
        if (*pre == *post) {
                evaluate_conditional(pre);
                *post = *pre;
        } else {
                evaluate_conditional(pre);
                evaluate_conditional(post);
        }
        evaluate_statement(stmt->iterator_pre_statement);
        evaluate_statement(stmt->iterator_statement);
        evaluate_statement(stmt->iterator_post_statement);
}

struct symbol *evaluate_statement(struct statement *stmt)
{
        if (!stmt)
                return NULL;

        switch (stmt->type) {
        case STMT_RETURN:
                return evaluate_return_expression(stmt);

        case STMT_EXPRESSION:
                if (!evaluate_expression(stmt->expression))
                        return NULL;
                return degenerate(stmt->expression);

        case STMT_COMPOUND: {
                struct statement *s;
                struct symbol *type = NULL;
                struct symbol *sym;

                /* Evaluate each symbol in the compound statement */
                FOR_EACH_PTR(stmt->syms, sym) {
                        evaluate_symbol(sym);
                } END_FOR_EACH_PTR;
                evaluate_symbol(stmt->ret);

                /*
                 * Then, evaluate each statement, making the type of the
                 * compound statement be the type of the last statement
                 */
                type = NULL;
                FOR_EACH_PTR(stmt->stmts, s) {
                        type = evaluate_statement(s);
                } END_FOR_EACH_PTR;
                if (!type)
                        type = &void_ctype;
                return type;
        }
        case STMT_IF:
                evaluate_if_statement(stmt);
                return NULL;
        case STMT_ITERATOR:
                evaluate_iterator(stmt);
                return NULL;
        case STMT_SWITCH:
                evaluate_expression(stmt->switch_expression);
                evaluate_statement(stmt->switch_statement);
                return NULL;
        case STMT_CASE:
                evaluate_expression(stmt->case_expression);
                evaluate_expression(stmt->case_to);
                evaluate_statement(stmt->case_statement);
                return NULL;
        case STMT_LABEL:
                return evaluate_statement(stmt->label_statement);
        case STMT_GOTO:
                evaluate_expression(stmt->goto_expression);
                return NULL;
        case STMT_NONE:
                break;
        case STMT_ASM:
                /* FIXME! Do the asm parameter evaluation! */
                break;
        }
        return NULL;
}