xref: /third_party/ltp/tools/sparse/sparse-src/evaluate.c (revision f08c3bdf)

/*
 * sparse/evaluate.c
 *
 * Copyright (C) 2003 Transmeta Corp.
 *               2003-2004 Linus Torvalds
 *
 * 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.
 *
 * 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 "evaluate.h"
#include "lib.h"
#include "allocate.h"
#include "parse.h"
#include "token.h"
#include "symbol.h"
#include "target.h"
#include "expression.h"

struct symbol *current_fn;

struct ident bad_address_space = { .len = 6, .name = "bad AS", };

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

static inline int valid_expr_type(struct expression *expr)
{
	return expr && valid_type(expr->ctype);
}

static inline int valid_subexpr_type(struct expression *expr)
{
	return valid_expr_type(expr->left)
	    && valid_expr_type(expr->right);
}

static struct symbol *unqualify_type(struct symbol *ctype)
{
	if (!ctype)
		return ctype;
	if (ctype->type == SYM_NODE && (ctype->ctype.modifiers & MOD_QUALIFIER)) {
		struct symbol *unqual = alloc_symbol(ctype->pos, 0);

		*unqual = *ctype;
		unqual->ctype.modifiers &= ~MOD_QUALIFIER;
		return unqual;
	}
	return ctype;
}

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

	if (!sym) {
		expression_error(expr, "undefined identifier '%s'", show_ident(expr->symbol_name));
		return NULL;
	}

	examine_symbol_type(sym);

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

	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 */
	addr->flags = expr->flags;
	expr->type = EXPR_PREOP;
	expr->op = '*';
	expr->unop = addr;
	expr->flags = CEF_NONE;

	/* The type of a symbol is the symbol itself! */
	expr->ctype = sym;
	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;
	struct symbol *char_type = expr->wide ? wchar_ctype : &char_ctype;

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

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

	array->array_size = sym->array_size;
	array->bit_size = sym->bit_size;
	array->ctype.alignment = char_type->ctype.alignment;
	array->ctype.modifiers = MOD_STATIC;
	array->ctype.base_type = char_type;
	array->examined = 1;
	array->evaluated = 1;

	addr->symbol = sym;
	addr->ctype = &lazy_ptr_ctype;
	addr->flags = CEF_ADDR;

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

/* type has come from classify_type and is an integer type */
static inline struct symbol *integer_promotion(struct symbol *type)
{
	unsigned long mod =  type->ctype.modifiers;
	int width = type->bit_size;

	/*
	 * Bitfields always promote to the base type,
	 * even if the bitfield might be bigger than
	 * an "int".
	 */
	if (type->type == SYM_BITFIELD) {
		type = type->ctype.base_type;
	}
	mod = type->ctype.modifiers;
	if (width < bits_in_int)
		return &int_ctype;

	/* If char/short has as many bits as int, it still gets "promoted" */
	if (type->rank < 0) {
		if (mod & MOD_UNSIGNED)
			return &uint_ctype;
		return &int_ctype;
	}
	return type;
}

/*
 * After integer promotons:
 * If both types are the same
 *   -> no conversion needed
 * If the types have the same signedness (their rank must be different)
 *   -> convert to the type of the highest rank
 * If rank(unsigned type) >= rank(signed type)
 *   -> convert to the unsigned type
 * If size(signed type) > size(unsigned type)
 *   -> convert to the signed type
 * Otherwise
 *   -> convert to the unsigned type corresponding to the signed type.
 */
static struct symbol *bigger_int_type(struct symbol *left, struct symbol *right)
{
	static struct symbol *unsigned_types[] = {
		[0] = &uint_ctype,
		[1] = &ulong_ctype,
		[2] = &ullong_ctype,
		[3] = &uint128_ctype,
	};
	unsigned long lmod, rmod;
	struct symbol *stype, *utype;

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

	if (left == right)
		return left;

	lmod = left->ctype.modifiers;
	rmod = right->ctype.modifiers;
	if (((lmod ^ rmod) & MOD_UNSIGNED) == 0)
		return (left->rank > right->rank) ? left : right;
	if (lmod & MOD_UNSIGNED) {
		utype = left;
		stype = right;
	} else {
		stype = left;
		utype = right;
	}
	if (utype->rank >= stype->rank)
		return utype;
	if (stype->bit_size > utype->bit_size)
		return stype;
	utype = unsigned_types[stype->rank];
	return utype;
}

static struct symbol *base_type(struct symbol *node, unsigned long *modp, struct ident **asp)
{
	unsigned long mod = 0;
	struct ident *as = NULL;

	while (node) {
		mod |= node->ctype.modifiers;
		combine_address_space(node->pos, &as, node->ctype.as);
		if (node->type == SYM_NODE) {
			node = node->ctype.base_type;
			continue;
		}
		break;
	}
	*modp = mod & ~MOD_IGNORE;
	*asp = as;
	return node;
}

static int is_same_type(struct expression *expr, struct symbol *new)
{
	struct symbol *old = expr->ctype;
	unsigned long oldmod, newmod;
	struct ident *oldas, *newas;

	old = base_type(old, &oldmod, &oldas);
	new = base_type(new, &newmod, &newas);

	/* Same base type, same address space? */
	if (old == new && oldas == newas) {
		unsigned long difmod;

		/* Check the modifier bits. */
		difmod = (oldmod ^ newmod) & ~MOD_NOCAST;

		/* Exact same type? */
		if (!difmod)
			return 1;

		/*
		 * Not the same type, but differs only in "const".
		 * Don't warn about MOD_NOCAST.
		 */
		if (difmod == MOD_CONST)
			return 0;
	}
	if ((oldmod | newmod) & MOD_NOCAST) {
		const char *tofrom = "to/from";
		if (!(newmod & MOD_NOCAST))
			tofrom = "from";
		if (!(oldmod & MOD_NOCAST))
			tofrom = "to";
		warning(expr->pos, "implicit cast %s nocast type", tofrom);
	}
	return 0;
}

static void
warn_for_different_enum_types (struct position pos,
			       struct symbol *typea,
			       struct symbol *typeb)
{
	if (!Wenum_mismatch)
		return;
	if (typea->type == SYM_NODE)
		typea = typea->ctype.base_type;
	if (typeb->type == SYM_NODE)
		typeb = typeb->ctype.base_type;

	if (typea == typeb)
		return;

	if (typea->type == SYM_ENUM && typeb->type == SYM_ENUM) {
		warning(pos, "mixing different enum types:");
		info(pos, "   %s", show_typename(typea));
		info(pos, "   %s", show_typename(typeb));
	}
}

static int cast_flags(struct expression *expr, struct expression *target);
static struct symbol *cast_to_bool(struct expression *expr);

/*
 * This gets called for implicit casts in assignments and
 * integer promotion.
 */
static struct expression * cast_to(struct expression *old, struct symbol *type)
{
	struct expression *expr;

	warn_for_different_enum_types (old->pos, old->ctype, type);

	if (old->ctype != &null_ctype && is_same_type(old, type))
		return old;

	expr = alloc_expression(old->pos, EXPR_IMPLIED_CAST);
	expr->ctype = type;
	expr->cast_type = type;
	expr->cast_expression = old;
	expr->flags = cast_flags(expr, old);

	if (is_bool_type(type))
		cast_to_bool(expr);

	return expr;
}

enum {
	TYPE_NUM = 1,
	TYPE_BITFIELD = 2,
	TYPE_RESTRICT = 4,
	TYPE_FLOAT = 8,
	TYPE_PTR = 16,
	TYPE_COMPOUND = 32,
	TYPE_FOULED = 64,
	TYPE_FN = 128,
};

static inline int classify_type(struct symbol *type, struct symbol **base)
{
	static int type_class[SYM_BAD + 1] = {
		[SYM_PTR] = TYPE_PTR,
		[SYM_FN] = TYPE_PTR | TYPE_FN,
		[SYM_ARRAY] = TYPE_PTR | TYPE_COMPOUND,
		[SYM_STRUCT] = TYPE_COMPOUND,
		[SYM_UNION] = TYPE_COMPOUND,
		[SYM_BITFIELD] = TYPE_NUM | TYPE_BITFIELD,
		[SYM_RESTRICT] = TYPE_NUM | TYPE_RESTRICT,
		[SYM_FOULED] = TYPE_NUM | TYPE_RESTRICT | TYPE_FOULED,
	};
	if (type->type == SYM_NODE)
		type = type->ctype.base_type;
	if (type->type == SYM_TYPEOF) {
		type = examine_symbol_type(type);
		if (type->type == SYM_NODE)
			type = type->ctype.base_type;
	}
	if (type->type == SYM_ENUM)
		type = type->ctype.base_type;
	*base = type;
	if (type->type == SYM_BASETYPE) {
		if (type->ctype.base_type == &int_type)
			return TYPE_NUM;
		if (type->ctype.base_type == &fp_type)
			return TYPE_NUM | TYPE_FLOAT;
	}
	return type_class[type->type];
}

#define is_int(class) ((class & (TYPE_NUM | TYPE_FLOAT)) == TYPE_NUM)

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

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

	expr->flags = CEF_NONE;
	return expr->ctype = &bad_ctype;
}

static int restricted_value(struct expression *v, struct symbol *type)
{
	if (v->type != EXPR_VALUE)
		return 1;
	if (v->value != 0)
		return 1;
	return 0;
}

static int restricted_binop(int op, struct symbol *type)
{
	switch (op) {
		case '&':
		case '=':
		case SPECIAL_AND_ASSIGN:
		case SPECIAL_OR_ASSIGN:
		case SPECIAL_XOR_ASSIGN:
			return 1;	/* unfoul */
		case '|':
		case '^':
		case '?':
			return 2;	/* keep fouled */
		case SPECIAL_EQUAL:
		case SPECIAL_NOTEQUAL:
			return 3;	/* warn if fouled */
		default:
			return 0;	/* warn */
	}
}

static int restricted_unop(int op, struct symbol **type)
{
	if (op == '~') {
		if ((*type)->bit_size < bits_in_int)
			*type = befoul(*type);
		return 0;
	} if (op == '+')
		return 0;
	return 1;
}

/* type should be SYM_FOULED */
static inline struct symbol *unfoul(struct symbol *type)
{
	return type->ctype.base_type;
}

static struct symbol *restricted_binop_type(int op,
					struct expression *left,
					struct expression *right,
					int lclass, int rclass,
					struct symbol *ltype,
					struct symbol *rtype)
{
	struct symbol *ctype = NULL;
	if (lclass & TYPE_RESTRICT) {
		if (rclass & TYPE_RESTRICT) {
			if (ltype == rtype) {
				ctype = ltype;
			} else if (lclass & TYPE_FOULED) {
				if (unfoul(ltype) == rtype)
					ctype = ltype;
			} else if (rclass & TYPE_FOULED) {
				if (unfoul(rtype) == ltype)
					ctype = rtype;
			}
		} else {
			if (!restricted_value(right, ltype))
				ctype = ltype;
		}
	} else if (!restricted_value(left, rtype))
		ctype = rtype;

	if (ctype) {
		switch (restricted_binop(op, ctype)) {
		case 1:
			if ((lclass ^ rclass) & TYPE_FOULED)
				ctype = unfoul(ctype);
			break;
		case 3:
			if (!(lclass & rclass & TYPE_FOULED))
				break;
		case 0:
			ctype = NULL;
		default:
			break;
		}
	}

	return ctype;
}

static inline void unrestrict(struct expression *expr,
			      int class, struct symbol **ctype)
{
	if (class & TYPE_RESTRICT) {
		if (class & TYPE_FOULED)
			*ctype = unfoul(*ctype);
		warning(expr->pos, "%s degrades to integer",
			show_typename(*ctype));
		*ctype = (*ctype)->ctype.base_type; /* get to arithmetic type */
	}
}

static struct symbol *usual_conversions(int op,
					struct expression *left,
					struct expression *right,
					int lclass, int rclass,
					struct symbol *ltype,
					struct symbol *rtype)
{
	struct symbol *ctype;

	warn_for_different_enum_types(right->pos, left->ctype, right->ctype);

	if ((lclass | rclass) & TYPE_RESTRICT)
		goto Restr;

Normal:
	if (!(lclass & TYPE_FLOAT)) {
		if (!(rclass & TYPE_FLOAT))
			return bigger_int_type(ltype, rtype);
		else
			return rtype;
	} else if (rclass & TYPE_FLOAT) {
		if (rtype->rank > ltype->rank)
			return rtype;
		else
			return ltype;
	} else
		return ltype;

Restr:
	ctype = restricted_binop_type(op, left, right,
				      lclass, rclass, ltype, rtype);
	if (ctype)
		return ctype;

	unrestrict(left, lclass, &ltype);
	unrestrict(right, rclass, &rtype);

	goto Normal;
}

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

static struct symbol *evaluate_ptr_add(struct expression *expr, struct symbol *itype)
{
	struct expression *index = expr->right;
	struct symbol *ctype, *base;
	int multiply;

	classify_type(degenerate(expr->left), &ctype);
	base = examine_pointer_target(ctype);

	/*
	 * An address constant +/- an integer constant expression
	 * yields an address constant again [6.6(7)].
	 */
	if ((expr->left->flags & CEF_ADDR) && (expr->right->flags & CEF_ICE))
		expr->flags = CEF_ADDR;

	if (!base) {
		expression_error(expr, "missing type information");
		return NULL;
	}
	if (is_function(base)) {
		expression_error(expr, "arithmetics on pointers to functions");
		return NULL;
	}

	/* Get the size of whatever the pointer points to */
	multiply = is_void_type(base) ? 1 : bits_to_bytes(base->bit_size);

	if (ctype == &null_ctype)
		ctype = &ptr_ctype;
	expr->ctype = ctype;

	if (multiply == 1 && itype->bit_size == bits_in_pointer)
		return ctype;

	if (index->type == EXPR_VALUE) {
		struct expression *val = alloc_expression(expr->pos, EXPR_VALUE);
		unsigned long long v = index->value, mask;
		mask = 1ULL << (itype->bit_size - 1);
		if (v & mask)
			v |= -mask;
		else
			v &= mask - 1;
		v *= multiply;
		mask = 1ULL << (bits_in_pointer - 1);
		v &= mask | (mask - 1);
		val->value = v;
		val->ctype = ssize_t_ctype;
		expr->right = val;
		return ctype;
	}

	if (itype->bit_size != bits_in_pointer)
		index = cast_to(index, ssize_t_ctype);

	if (multiply > 1) {
		struct expression *val = alloc_expression(expr->pos, EXPR_VALUE);
		struct expression *mul = alloc_expression(expr->pos, EXPR_BINOP);

		val->ctype = ssize_t_ctype;
		val->value = multiply;

		mul->op = '*';
		mul->ctype = ssize_t_ctype;
		mul->left = index;
		mul->right = val;
		index = mul;
	}

	expr->right = index;
	return ctype;
}

static void examine_fn_arguments(struct symbol *fn);

#define MOD_IGN (MOD_QUALIFIER | MOD_FUN_ATTR)

const char *type_difference(struct ctype *c1, struct ctype *c2,
	unsigned long mod1, unsigned long mod2)
{
	struct ident *as1 = c1->as, *as2 = c2->as;
	struct symbol *t1 = c1->base_type;
	struct symbol *t2 = c2->base_type;
	int move1 = 1, move2 = 1;
	mod1 |= c1->modifiers;
	mod2 |= c2->modifiers;
	for (;;) {
		unsigned long diff;
		int type;
		struct symbol *base1 = t1->ctype.base_type;
		struct symbol *base2 = t2->ctype.base_type;

		/*
		 * FIXME! Collect alignment and context too here!
		 */
		if (move1) {
			if (t1 && t1->type != SYM_PTR) {
				mod1 |= t1->ctype.modifiers;
				combine_address_space(t1->pos, &as1, t1->ctype.as);
			}
			move1 = 0;
		}

		if (move2) {
			if (t2 && t2->type != SYM_PTR) {
				mod2 |= t2->ctype.modifiers;
				combine_address_space(t2->pos, &as2, t2->ctype.as);
			}
			move2 = 0;
		}

		if (t1 == t2)
			break;
		if (!t1 || !t2)
			return "different types";

		if (t1->type == SYM_NODE || t1->type == SYM_ENUM) {
			t1 = base1;
			move1 = 1;
			if (!t1)
				return "bad types";
			continue;
		}

		if (t2->type == SYM_NODE || t2->type == SYM_ENUM) {
			t2 = base2;
			move2 = 1;
			if (!t2)
				return "bad types";
			continue;
		}

		move1 = move2 = 1;
		type = t1->type;
		if (type != t2->type)
			return "different base types";

		switch (type) {
		default:
			sparse_error(t1->pos,
				     "internal error: bad type in derived(%d)",
				     type);
			return "bad types";
		case SYM_RESTRICT:
			return "different base types";
		case SYM_UNION:
		case SYM_STRUCT:
			/* allow definition of incomplete structs and unions */
			if (t1->ident == t2->ident)
			  return NULL;
			return "different base types";
		case SYM_ARRAY:
			/* XXX: we ought to compare sizes */
			break;
		case SYM_PTR:
			if (as1 != as2)
				return "different address spaces";
			/* MOD_SPECIFIER is due to idiocy in parse.c */
			if ((mod1 ^ mod2) & ~MOD_IGNORE & ~MOD_SPECIFIER)
				return "different modifiers";
			/* we could be lazier here */
			base1 = examine_pointer_target(t1);
			base2 = examine_pointer_target(t2);
			mod1 = t1->ctype.modifiers;
			as1 = t1->ctype.as;
			mod2 = t2->ctype.modifiers;
			as2 = t2->ctype.as;
			break;
		case SYM_FN: {
			struct symbol *arg1, *arg2;
			int i;

			if (as1 != as2)
				return "different address spaces";
			if ((mod1 ^ mod2) & ~MOD_IGNORE & ~MOD_SIGNEDNESS)
				return "different modifiers";
			mod1 = t1->ctype.modifiers;
			as1 = t1->ctype.as;
			mod2 = t2->ctype.modifiers;
			as2 = t2->ctype.as;

			if (t1->variadic != t2->variadic)
				return "incompatible variadic arguments";
			examine_fn_arguments(t1);
			examine_fn_arguments(t2);
			PREPARE_PTR_LIST(t1->arguments, arg1);
			PREPARE_PTR_LIST(t2->arguments, arg2);
			i = 1;
			for (;;) {
				const char *diffstr;
				if (!arg1 && !arg2)
					break;
				if (!arg1 || !arg2)
					return "different argument counts";
				diffstr = type_difference(&arg1->ctype,
							  &arg2->ctype,
							  MOD_IGN, MOD_IGN);
				if (diffstr) {
					static char argdiff[80];
					sprintf(argdiff, "incompatible argument %d (%s)", i, diffstr);
					return argdiff;
				}
				NEXT_PTR_LIST(arg1);
				NEXT_PTR_LIST(arg2);
				i++;
			}
			FINISH_PTR_LIST(arg2);
			FINISH_PTR_LIST(arg1);
			break;
		}
		case SYM_BASETYPE:
			if (as1 != as2)
				return "different address spaces";
			if (base1 != base2)
				return "different base types";
			if (t1->rank != t2->rank)
				return "different type sizes";
			diff = (mod1 ^ mod2) & ~MOD_IGNORE;
			if (!diff)
				return NULL;
			else if (diff & ~MOD_SIGNEDNESS)
				return "different modifiers";
			else
				return "different signedness";
		}
		t1 = base1;
		t2 = base2;
	}
	if (as1 != as2)
		return "different address spaces";
	if ((mod1 ^ mod2) & ~MOD_IGNORE & ~MOD_SIGNEDNESS)
		return "different modifiers";
	return NULL;
}

static void bad_null(struct expression *expr)
{
	if (Wnon_pointer_null)
		warning(expr->pos, "Using plain integer as NULL pointer");
}

static unsigned long target_qualifiers(struct symbol *type)
{
	unsigned long mod = type->ctype.modifiers & MOD_IGN;
	if (type->ctype.base_type && type->ctype.base_type->type == SYM_ARRAY)
		mod = 0;
	return mod;
}

static struct symbol *evaluate_ptr_sub(struct expression *expr)
{
	const char *typediff;
	struct symbol *ltype, *rtype;
	struct expression *l = expr->left;
	struct expression *r = expr->right;
	struct symbol *lbase;

	classify_type(degenerate(l), &ltype);
	classify_type(degenerate(r), &rtype);

	lbase = examine_pointer_target(ltype);
	examine_pointer_target(rtype);
	typediff = type_difference(&ltype->ctype, &rtype->ctype,
				   target_qualifiers(rtype),
				   target_qualifiers(ltype));
	if (typediff)
		expression_error(expr, "subtraction of different types can't work (%s)", typediff);

	if (is_function(lbase)) {
		expression_error(expr, "subtraction of functions? Share your drugs");
		return NULL;
	}

	expr->ctype = ssize_t_ctype;
	if (lbase->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);
		unsigned long value = bits_to_bytes(lbase->bit_size);

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

		if (value & (value-1)) {
			if (Wptr_subtraction_blows) {
				warning(expr->pos, "potentially expensive pointer subtraction");
				info(expr->pos, "    '%s' has a non-power-of-2 size: %lu", show_typename(lbase), value);
			}
		}

		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;
}

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

static struct symbol *evaluate_conditional(struct expression *expr, int iterator)
{
	struct symbol *ctype;

	if (!expr)
		return NULL;

	if (!iterator && expr->type == EXPR_ASSIGNMENT && expr->op == '=')
		warning(expr->pos, "assignment expression in conditional");

	ctype = evaluate_expression(expr);
	if (!valid_type(ctype))
		return NULL;
	if (is_safe_type(ctype))
		warning(expr->pos, "testing a 'safe expression'");
	if (is_func_type(ctype)) {
		if (Waddress)
			warning(expr->pos, "the address of %s will always evaluate as true", "a function");
	} else if (is_array_type(ctype)) {
		if (Waddress)
			warning(expr->pos, "the address of %s will always evaluate as true", "an array");
	} else if (!is_scalar_type(ctype)) {
		sparse_error(expr->pos, "non-scalar type in conditional:");
		info(expr->pos, "   %s", show_typename(ctype));
		return NULL;
	}

	ctype = degenerate(expr);
	return ctype;
}

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

	/* the result is int [6.5.13(3), 6.5.14(3)] */
	expr->ctype = &int_ctype;
	expr->flags = expr->left->flags & expr->right->flags;
	expr->flags &= ~(CEF_CONST_MASK | CEF_ADDR);
	return &int_ctype;
}

static struct symbol *evaluate_binop(struct expression *expr)
{
	struct symbol *ltype, *rtype, *ctype;
	int lclass = classify_type(expr->left->ctype, &ltype);
	int rclass = classify_type(expr->right->ctype, &rtype);
	int op = expr->op;

	/* number op number */
	if (lclass & rclass & TYPE_NUM) {
		expr->flags = expr->left->flags & expr->right->flags;
		expr->flags &= ~CEF_CONST_MASK;

		if ((lclass | rclass) & TYPE_FLOAT) {
			switch (op) {
			case '+': case '-': case '*': case '/':
				break;
			default:
				return bad_expr_type(expr);
			}
		}

		if (op == SPECIAL_LEFTSHIFT || op == SPECIAL_RIGHTSHIFT) {
			// shifts do integer promotions, but that's it.
			unrestrict(expr->left, lclass, &ltype);
			unrestrict(expr->right, rclass, &rtype);
			ctype = ltype = integer_promotion(ltype);
			rtype = integer_promotion(rtype);
		} else {
			// The rest do usual conversions
			const unsigned left_not  = expr->left->type == EXPR_PREOP
			                           && expr->left->op == '!';
			const unsigned right_not = expr->right->type == EXPR_PREOP
			                           && expr->right->op == '!';
			if ((op == '&' || op == '|') && (left_not || right_not))
				warning(expr->pos, "dubious: %sx %c %sy",
				        left_not ? "!" : "",
					op,
					right_not ? "!" : "");

			ltype = usual_conversions(op, expr->left, expr->right,
						  lclass, rclass, ltype, rtype);
			ctype = rtype = ltype;
		}

		expr->left = cast_to(expr->left, ltype);
		expr->right = cast_to(expr->right, rtype);
		expr->ctype = ctype;
		return ctype;
	}

	/* pointer (+|-) integer */
	if (lclass & TYPE_PTR && is_int(rclass) && (op == '+' || op == '-')) {
		unrestrict(expr->right, rclass, &rtype);
		return evaluate_ptr_add(expr, rtype);
	}

	/* integer + pointer */
	if (rclass & TYPE_PTR && is_int(lclass) && op == '+') {
		struct expression *index = expr->left;
		unrestrict(index, lclass, &ltype);
		expr->left = expr->right;
		expr->right = index;
		return evaluate_ptr_add(expr, ltype);
	}

	/* pointer - pointer */
	if (lclass & rclass & TYPE_PTR && expr->op == '-')
		return evaluate_ptr_sub(expr);

	return bad_expr_type(expr);
}

static struct symbol *evaluate_comma(struct expression *expr)
{
	expr->ctype = unqualify_type(degenerate(expr->right));
	if (expr->ctype == &null_ctype)
		expr->ctype = &ptr_ctype;
	expr->flags &= expr->left->flags & expr->right->flags;
	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;
}

enum null_constant_type {
	NON_NULL,
	NULL_PTR,
	NULL_ZERO,
};

static inline int is_null_pointer_constant(struct expression *e)
{
	if (e->ctype == &null_ctype)
		return NULL_PTR;
	if (!(e->flags & CEF_ICE))
		return NON_NULL;
	return is_zero_constant(e) ? NULL_ZERO : NON_NULL;
}

static struct symbol *evaluate_compare(struct expression *expr)
{
	struct expression *left = expr->left, *right = expr->right;
	struct symbol *ltype, *rtype, *lbase, *rbase;
	int lclass = classify_type(degenerate(left), &ltype);
	int rclass = classify_type(degenerate(right), &rtype);
	struct symbol *ctype;
	const char *typediff;

	/* Type types? */
	if (is_type_type(ltype) && is_type_type(rtype)) {
		/*
		 * __builtin_types_compatible_p() yields an integer
		 * constant expression
		 */
		expr->flags = CEF_SET_ICE;
		goto OK;
	}

	if (is_safe_type(left->ctype) || is_safe_type(right->ctype))
		warning(expr->pos, "testing a 'safe expression'");

	expr->flags = left->flags & right->flags & ~CEF_CONST_MASK & ~CEF_ADDR;

	/* number on number */
	if (lclass & rclass & TYPE_NUM) {
		ctype = usual_conversions(expr->op, expr->left, expr->right,
					  lclass, rclass, ltype, rtype);
		expr->left = cast_to(expr->left, ctype);
		expr->right = cast_to(expr->right, ctype);
		if (ctype->ctype.modifiers & MOD_UNSIGNED)
			expr->op = modify_for_unsigned(expr->op);
		goto OK;
	}

	/* at least one must be a pointer */
	if (!((lclass | rclass) & TYPE_PTR))
		return bad_expr_type(expr);

	/* equality comparisons can be with null pointer constants */
	if (expr->op == SPECIAL_EQUAL || expr->op == SPECIAL_NOTEQUAL) {
		int is_null1 = is_null_pointer_constant(left);
		int is_null2 = is_null_pointer_constant(right);
		if (is_null1 == NULL_ZERO)
			bad_null(left);
		if (is_null2 == NULL_ZERO)
			bad_null(right);
		if (is_null1 && is_null2) {
			int positive = expr->op == SPECIAL_EQUAL;
			expr->type = EXPR_VALUE;
			expr->value = positive;
			goto OK;
		}
		if (is_null1 && (rclass & TYPE_PTR)) {
			expr->left = cast_to(left, rtype);
			goto OK;
		}
		if (is_null2 && (lclass & TYPE_PTR)) {
			expr->right = cast_to(right, ltype);
			goto OK;
		}
	}
	/* both should be pointers */
	if (!(lclass & rclass & TYPE_PTR))
		return bad_expr_type(expr);
	expr->op = modify_for_unsigned(expr->op);

	lbase = examine_pointer_target(ltype);
	rbase = examine_pointer_target(rtype);

	/* they also have special treatment for pointers to void */
	if (expr->op == SPECIAL_EQUAL || expr->op == SPECIAL_NOTEQUAL) {
		if (ltype->ctype.as == rtype->ctype.as) {
			if (lbase == &void_ctype) {
				expr->right = cast_to(right, ltype);
				goto OK;
			}
			if (rbase == &void_ctype) {
				expr->left = cast_to(left, rtype);
				goto OK;
			}
		}
	}

	typediff = type_difference(&ltype->ctype, &rtype->ctype,
				   target_qualifiers(rtype),
				   target_qualifiers(ltype));
	if (!typediff)
		goto OK;

	expression_error(expr, "incompatible types in comparison expression (%s):", typediff);
	info(expr->pos, "   %s", show_typename(ltype));
	info(expr->pos, "   %s", show_typename(rtype));
	return NULL;

OK:
	/* the result is int [6.5.8(6), 6.5.9(3)]*/
	expr->ctype = &int_ctype;
	return &int_ctype;
}

/*
 * NOTE! The degenerate case of "x ? : y", where we don't
 * have a true case, this will possibly promote "x" to the
 * same type as "y", and thus _change_ the conditional
 * test in the expression. But since promotion is "safe"
 * for testing, that's OK.
 */
static struct symbol *evaluate_conditional_expression(struct expression *expr)
{
	struct expression **cond;
	struct symbol *ctype, *ltype, *rtype, *lbase, *rbase;
	int lclass, rclass;
	const char * typediff;
	int qual;

	if (!evaluate_conditional(expr->conditional, 0))
		return NULL;
	if (!evaluate_expression(expr->cond_false))
		return NULL;

	ctype = degenerate(expr->conditional);
	rtype = degenerate(expr->cond_false);

	cond = &expr->conditional;
	ltype = ctype;
	if (expr->cond_true) {
		if (!evaluate_expression(expr->cond_true))
			return NULL;
		ltype = degenerate(expr->cond_true);
		cond = &expr->cond_true;
	}

	expr->flags = (expr->conditional->flags & (*cond)->flags &
			expr->cond_false->flags & ~CEF_CONST_MASK);
	/*
	 * In the standard, it is defined that an integer constant expression
	 * shall only have operands that are themselves constant [6.6(6)].
	 * While this definition is very clear for expressions that need all
	 * their operands to be evaluated, for conditional expressions with a
	 * constant condition things are much less obvious.
	 * So, as an extension, do the same as GCC seems to do:
	 *	Consider a conditional expression with a constant condition
	 *	as having the same constantness as the argument corresponding
	 *	to the truth value (including in the case of address constants
	 *	which are defined more stricly [6.6(9)]).
	 */
	if (expr->conditional->flags & (CEF_ACE | CEF_ADDR)) {
		int is_true = expr_truth_value(expr->conditional);
		struct expression *arg = is_true ? *cond : expr->cond_false;
		expr->flags = arg->flags & ~CEF_CONST_MASK;
	}

	lclass = classify_type(ltype, &ltype);
	rclass = classify_type(rtype, &rtype);
	if (lclass & rclass & TYPE_NUM) {
		ctype = usual_conversions('?', *cond, expr->cond_false,
					  lclass, rclass, ltype, rtype);
		*cond = cast_to(*cond, ctype);
		expr->cond_false = cast_to(expr->cond_false, ctype);
		goto out;
	}

	if ((lclass | rclass) & TYPE_PTR) {
		int is_null1 = is_null_pointer_constant(*cond);
		int is_null2 = is_null_pointer_constant(expr->cond_false);

		if (is_null1 && is_null2) {
			*cond = cast_to(*cond, &ptr_ctype);
			expr->cond_false = cast_to(expr->cond_false, &ptr_ctype);
			ctype = &ptr_ctype;
			goto out;
		}
		if (is_null1 && (rclass & TYPE_PTR)) {
			if (is_null1 == NULL_ZERO)
				bad_null(*cond);
			*cond = cast_to(*cond, rtype);
			ctype = rtype;
			goto out;
		}
		if (is_null2 && (lclass & TYPE_PTR)) {
			if (is_null2 == NULL_ZERO)
				bad_null(expr->cond_false);
			expr->cond_false = cast_to(expr->cond_false, ltype);
			ctype = ltype;
			goto out;
		}
		if (!(lclass & rclass & TYPE_PTR)) {
			typediff = "different types";
			goto Err;
		}
		/* OK, it's pointer on pointer */
		if (ltype->ctype.as != rtype->ctype.as) {
			typediff = "different address spaces";
			goto Err;
		}

		/* need to be lazier here */
		lbase = examine_pointer_target(ltype);
		rbase = examine_pointer_target(rtype);
		qual = target_qualifiers(ltype) | target_qualifiers(rtype);

		if (lbase == &void_ctype) {
			/* XXX: pointers to function should warn here */
			ctype = ltype;
			goto Qual;

		}
		if (rbase == &void_ctype) {
			/* XXX: pointers to function should warn here */
			ctype = rtype;
			goto Qual;
		}
		/* XXX: that should be pointer to composite */
		ctype = ltype;
		typediff = type_difference(&ltype->ctype, &rtype->ctype,
					   qual, qual);
		if (!typediff)
			goto Qual;
		goto Err;
	}

	/* void on void, struct on same struct, union on same union */
	if (ltype == rtype) {
		ctype = ltype;
		goto out;
	}
	typediff = "different base types";

Err:
	expression_error(expr, "incompatible types in conditional expression (%s):", typediff);
	info(expr->pos, "   %s", show_typename(ltype));
	info(expr->pos, "   %s", show_typename(rtype));
	/*
	 * if the condition is constant, the type is in fact known
	 * so use it, as gcc & clang do.
	 */
	switch (expr_truth_value(expr->conditional)) {
	case 1:	expr->ctype = ltype;
		break;
	case 0: expr->ctype = rtype;
		break;
	default:
		break;
	}
	return NULL;

out:
	expr->ctype = ctype;
	return ctype;

Qual:
	if (qual & ~ctype->ctype.modifiers) {
		struct symbol *sym = alloc_symbol(ctype->pos, SYM_PTR);
		*sym = *ctype;
		sym->ctype.modifiers |= qual;
		ctype = sym;
	}
	*cond = cast_to(*cond, ctype);
	expr->cond_false = cast_to(expr->cond_false, ctype);
	goto out;
}

/* FP assignments can not do modulo or bit operations */
static int compatible_float_op(int op)
{
	return	op == SPECIAL_ADD_ASSIGN ||
		op == SPECIAL_SUB_ASSIGN ||
		op == SPECIAL_MUL_ASSIGN ||
		op == SPECIAL_DIV_ASSIGN;
}

static int evaluate_assign_op(struct expression *expr)
{
	struct symbol *target = expr->left->ctype;
	struct symbol *source = expr->right->ctype;
	struct symbol *t, *s;
	int tclass = classify_type(target, &t);
	int sclass = classify_type(source, &s);
	int op = expr->op;

	if (tclass & sclass & TYPE_NUM) {
		if (tclass & TYPE_FLOAT && !compatible_float_op(op)) {
			expression_error(expr, "invalid assignment");
			return 0;
		}
		if (tclass & TYPE_RESTRICT) {
			if (!restricted_binop(op, t)) {
				warning(expr->pos, "bad assignment (%s) to %s",
					show_special(op), show_typename(t));
				expr->right = cast_to(expr->right, target);
				return 0;
			}
			/* allowed assignments unfoul */
			if (sclass & TYPE_FOULED && unfoul(s) == t)
				goto Cast;
			if (!restricted_value(expr->right, t))
				return 1;
		} else if (op == SPECIAL_SHR_ASSIGN || op == SPECIAL_SHL_ASSIGN) {
			// shifts do integer promotions, but that's it.
			unrestrict(expr->left, tclass, &t);
			target = integer_promotion(t);

			unrestrict(expr->right, sclass, &s);
			source = integer_promotion(s);
			expr->right = cast_to(expr->right, source);

			// both gcc & clang seems to do this, so ...
			if (target->bit_size > source->bit_size)
				expr->right = cast_to(expr->right, &uint_ctype);

			goto Cast;
		} else if (!(sclass & TYPE_RESTRICT))
			goto usual;
		/* source and target would better be identical restricted */
		if (t == s)
			return 1;
		warning(expr->pos, "invalid assignment: %s", show_special(op));
		info(expr->pos, "   left side has type %s", show_typename(t));
		info(expr->pos, "   right side has type %s", show_typename(s));
		expr->right = cast_to(expr->right, target);
		return 0;
	}
	if (tclass == TYPE_PTR && is_int(sclass)) {
		if (op == SPECIAL_ADD_ASSIGN || op == SPECIAL_SUB_ASSIGN) {
			unrestrict(expr->right, sclass, &s);
			evaluate_ptr_add(expr, s);
			return 1;
		}
		expression_error(expr, "invalid pointer assignment");
		return 0;
	}

	expression_error(expr, "invalid assignment");
	return 0;

usual:
	target = usual_conversions(op, expr->left, expr->right,
				tclass, sclass, target, source);
Cast:
	expr->right = cast_to(expr->right, target);
	return 1;
}

static int whitelist_pointers(struct symbol *t1, struct symbol *t2)
{
	if (t1 == t2)
		return 0;	/* yes, 0 - we don't want a cast_to here */
	if (t1 == &void_ctype)
		return 1;
	if (t2 == &void_ctype)
		return 1;
	if (classify_type(t1, &t1) != TYPE_NUM)
		return 0;
	if (classify_type(t2, &t2) != TYPE_NUM)
		return 0;
	if (t1 == t2)
		return 1;
	if (t1->rank == -2 && t2->rank == -2)
		return 1;
	if (t1->rank != t2->rank)
		return 0;
	return !Wtypesign;
}

static int check_assignment_types(struct symbol *target, struct expression **rp,
	const char **typediff)
{
	struct symbol *source = degenerate(*rp);
	struct symbol *t, *s;
	int tclass = classify_type(target, &t);
	int sclass = classify_type(source, &s);

	if (tclass & sclass & TYPE_NUM) {
		if (tclass & TYPE_RESTRICT) {
			/* allowed assignments unfoul */
			if (sclass & TYPE_FOULED && unfoul(s) == t)
				goto Cast;
			if (!restricted_value(*rp, target))
				goto Cast;
			if (s == t)
				return 1;
		} else if (!(sclass & TYPE_RESTRICT))
			goto Cast;
                if (t == &bool_ctype) {
                        if (is_fouled_type(s))
                                warning((*rp)->pos, "%s degrades to integer",
                                        show_typename(s->ctype.base_type));
                        goto Cast;
                }
		*typediff = "different base types";
		return 0;
	}

	if (tclass == TYPE_PTR) {
		unsigned long mod1, mod2;
		unsigned long modl, modr;
		struct symbol *b1, *b2;
		// NULL pointer is always OK
		int is_null = is_null_pointer_constant(*rp);
		if (is_null) {
			if (is_null == NULL_ZERO)
				bad_null(*rp);
			goto Cast;
		}
		if (!(sclass & TYPE_PTR)) {
			*typediff = "different base types";
			return 0;
		}
		b1 = examine_pointer_target(t);
		b2 = examine_pointer_target(s);
		mod1 = t->ctype.modifiers & MOD_IGN;
		mod2 = s->ctype.modifiers & MOD_IGN;
		if (whitelist_pointers(b1, b2)) {
			/*
			 * assignments to/from void * are OK, provided that
			 * we do not remove qualifiers from pointed to [C]
			 * or mix address spaces [sparse].
			 */
			if (t->ctype.as != s->ctype.as) {
				*typediff = "different address spaces";
				return 0;
			}
			/*
			 * If this is a function pointer assignment, it is
			 * actually fine to assign a pointer to const data to
			 * it, as a function pointer points to const data
			 * implicitly, i.e., dereferencing it does not produce
			 * an lvalue.
			 */
			if (b1->type == SYM_FN)
				mod1 |= MOD_CONST;
			if (mod2 & ~mod1 & ~MOD_FUN_ATTR) {
				*typediff = "different modifiers";
				return 0;
			}
			goto Cast;
		}
		/* It's OK if the target is more volatile or const than the source */
		/* It's OK if the source is more pure/noreturn than the target */
		modr = mod1 & ~MOD_REV_QUAL;
		modl = mod2 &  MOD_REV_QUAL;
		*typediff = type_difference(&t->ctype, &s->ctype, modl, modr);
		if (*typediff)
			return 0;
		return 1;
	}

	if ((tclass & TYPE_COMPOUND) && s == t)
		return 1;

	if (tclass & TYPE_NUM) {
		/* XXX: need to turn into comparison with NULL */
		if (t == &bool_ctype && (sclass & TYPE_PTR))
			goto Cast;
		*typediff = "different base types";
		return 0;
	}
	*typediff = "invalid types";
	return 0;

Cast:
	*rp = cast_to(*rp, target);
	return 1;
}

static int compatible_assignment_types(struct expression *expr, struct symbol *target,
	struct expression **rp, const char *where)
{
	const char *typediff;

	if (!check_assignment_types(target, rp, &typediff)) {
		struct symbol *source = *rp ? (*rp)->ctype : NULL;
		warning(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;
	}

	return 1;
}

static int compatible_transparent_union(struct symbol *target,
	struct expression **rp)
{
	struct symbol *t, *member;
	classify_type(target, &t);
	if (t->type != SYM_UNION || !t->transparent_union)
		return 0;

	FOR_EACH_PTR(t->symbol_list, member) {
		const char *typediff;
		if (check_assignment_types(member, rp, &typediff))
			return 1;
	} END_FOR_EACH_PTR(member);

	return 0;
}

static int compatible_argument_type(struct expression *expr, struct symbol *target,
	struct expression **rp, const char *where)
{
	if (compatible_transparent_union(target, rp))
		return 1;

	return compatible_assignment_types(expr, target, rp, where);
}

static void mark_addressable(struct expression *expr)
{
	while (expr->type == EXPR_BINOP && expr->op == '+')
		expr = expr->left;
	if (expr->type == EXPR_SYMBOL) {
		struct symbol *sym = expr->symbol;
		sym->ctype.modifiers |= MOD_ADDRESSABLE;
	}
}

static void mark_assigned(struct expression *expr)
{
	struct symbol *sym;

	if (!expr)
		return;
	switch (expr->type) {
	case EXPR_SYMBOL:
		sym = expr->symbol;
		if (!sym)
			return;
		if (sym->type != SYM_NODE)
			return;
		sym->ctype.modifiers |= MOD_ASSIGNED;
		return;

	case EXPR_BINOP:
		mark_assigned(expr->left);
		mark_assigned(expr->right);
		return;
	case EXPR_CAST:
	case EXPR_FORCE_CAST:
		mark_assigned(expr->cast_expression);
		return;
	case EXPR_SLICE:
		mark_assigned(expr->base);
		return;
	default:
		/* Hmm? */
		return;
	}
}

static void evaluate_assign_to(struct expression *left, struct symbol *type)
{
	if (type->ctype.modifiers & MOD_CONST)
		expression_error(left, "assignment to const expression");

	/* We know left is an lvalue, so it's a "preop-*" */
	mark_assigned(left->unop);
}

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

	if (!lvalue_expression(left)) {
		expression_error(expr, "not an lvalue");
		return NULL;
	}

	ltype = left->ctype;

	if (expr->op != '=') {
		if (!evaluate_assign_op(expr))
			return NULL;
	} else {
		if (!compatible_assignment_types(expr, ltype, &expr->right, "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;
				combine_address_space(s->pos, &ptr->ctype.as, s->ctype.as);
				ptr->ctype.modifiers |= s->ctype.modifiers & MOD_PTRINHERIT;

				s->ctype.base_type = ptr;
				s->ctype.as = NULL;
				s->ctype.modifiers &= ~MOD_PTRINHERIT;
				s->bit_size = 0;
				s->examined = 0;
				examine_symbol_type(s);
				break;
			default:
				/* nothing */
				break;
			}
		}
	} END_FOR_EACH_PTR(s);
}

static struct symbol *convert_to_as_mod(struct symbol *sym, struct ident *as, int mod)
{
	/* Take the modifiers of the pointer, and apply them to the member */
	mod |= sym->ctype.modifiers;
	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);
	if (sym->ctype.modifiers & MOD_REGISTER) {
		warning(expr->pos, "taking address of 'register' variable '%s'", show_ident(sym->ident));
		sym->ctype.modifiers &= ~MOD_REGISTER;
	}
	if (sym->type == SYM_NODE) {
		combine_address_space(sym->pos, &ptr->ctype.as, sym->ctype.as);
		ptr->ctype.modifiers |= sym->ctype.modifiers & MOD_PTRINHERIT;
		sym = sym->ctype.base_type;
	}
	if (degenerate && sym->type == SYM_ARRAY) {
		combine_address_space(sym->pos, &ptr->ctype.as, sym->ctype.as);
		ptr->ctype.modifiers |= sym->ctype.modifiers & MOD_PTRINHERIT;
		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 = examine_symbol_type(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,
							bits_to_bytes(expr->r_bitpos));
				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) {
			expression_error(expr, "strange non-value function or array");
			return &bad_ctype;
		}
		if (ctype->builtin)
			sparse_error(expr->pos, "taking the address of built-in function '%s'", show_ident(ctype->ident));
		*expr = *expr->unop;
		ctype = create_pointer(expr, ctype, 1);
		expr->ctype = ctype;
		mark_addressable(expr);
	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) {
		expression_error(expr, "not addressable");
		return NULL;
	}
	ctype = op->ctype;
	if (ctype->builtin)
		sparse_error(expr->pos, "taking the address of built-in function '%s'", show_ident(ctype->ident));
	*expr = *op->unop;

	mark_addressable(expr);

	/*
	 * 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;
		expr->flags = CEF_NONE;
		return expr->ctype;
	}

	examine_symbol_type(ctype);

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

	target = ctype->ctype.base_type;

	switch (ctype->type) {
	default:
		expression_error(expr, "cannot dereference this type");
		return NULL;
	case SYM_FN:
		*expr = *op;
		return expr->ctype;
	case SYM_PTR:
		examine_symbol_type(target);
		node = alloc_symbol(expr->pos, SYM_NODE);
		node->ctype.modifiers = target->ctype.modifiers & MOD_SPECIFIER;
		merge_type(node, ctype);
		break;

	case SYM_ARRAY:
		if (!lvalue_expression(op)) {
			expression_error(op, "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..
		 */
		node = alloc_symbol(expr->pos, SYM_NODE);
		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;
	int class = classify_type(ctype, &ctype);
	int multiply = 0;

	if (!class || class & TYPE_COMPOUND) {
		expression_error(expr, "need scalar for ++/--");
		return NULL;
	}
	if (!lvalue_expression(expr->unop)) {
		expression_error(expr, "need lvalue expression for ++/--");
		return NULL;
	}

	unrestrict(expr, class, &ctype);

	if (class & TYPE_NUM) {
		multiply = 1;
	} else if (class == TYPE_PTR) {
		struct symbol *target = examine_pointer_target(ctype);
		if (!is_function(target))
			multiply = bits_to_bytes(target->bit_size);
	}

	if (multiply) {
		evaluate_assign_to(op, op->ctype);
		expr->op_value = multiply;
		expr->ctype = ctype;
		return ctype;
	}

	expression_error(expr, "bad argument type for ++/--");
	return NULL;
}

static struct symbol *evaluate_sign(struct expression *expr)
{
	struct symbol *ctype = expr->unop->ctype;
	int class = classify_type(ctype, &ctype);
	unsigned char flags = expr->unop->flags & ~CEF_CONST_MASK;

	/* should be an arithmetic type */
	if (!(class & TYPE_NUM))
		return bad_expr_type(expr);
	if (class & TYPE_RESTRICT)
		goto Restr;
Normal:
	if (!(class & TYPE_FLOAT)) {
		ctype = integer_promotion(ctype);
		expr->unop = cast_to(expr->unop, ctype);
	} else if (expr->op != '~') {
		/* no conversions needed */
	} else {
		return bad_expr_type(expr);
	}
	if (expr->op == '+')
		*expr = *expr->unop;
	expr->flags = flags;
	expr->ctype = ctype;
	return ctype;
Restr:
	if (restricted_unop(expr->op, &ctype))
		unrestrict(expr, class, &ctype);
	goto Normal;
}

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 preops are
		 * the same as the postops
		 */
		return evaluate_postop(expr);

	case '!':
		ctype = degenerate(expr->unop);
		expr->flags = expr->unop->flags & ~CEF_CONST_MASK;
		/*
		 * A logical negation never yields an address constant
		 * [6.6(9)].
		 */
		expr->flags &= ~CEF_ADDR;

		if (is_safe_type(ctype))
			warning(expr->pos, "testing a 'safe expression'");
		if (is_float_type(ctype)) {
			struct expression *arg = expr->unop;
			expr->type = EXPR_COMPARE;
			expr->op = SPECIAL_EQUAL;
			expr->left = arg;
			expr->right = alloc_expression(expr->pos, EXPR_FVALUE);
			expr->right->ctype = ctype;
			expr->right->fvalue = 0;
		} else if (is_fouled_type(ctype)) {
			warning(expr->pos, "%s degrades to integer",
				show_typename(ctype->ctype.base_type));
		}
		/* the result is int [6.5.3.3(5)]*/
		ctype = &int_ctype;
		break;

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

static 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;
	/*
	 * The resulting address of a member access through an address
	 * constant is an address constant again [6.6(9)].
	 */
	add->flags = expr->flags;

	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;
	struct ident *address_space;
	unsigned int mod;

	if (!evaluate_expression(deref))
		return NULL;
	if (!ident) {
		expression_error(expr, "bad member name");
		return NULL;
	}

	ctype = deref->ctype;
	examine_symbol_type(ctype);
	address_space = ctype->ctype.as;
	mod = ctype->ctype.modifiers;
	if (ctype->type == SYM_NODE) {
		ctype = ctype->ctype.base_type;
		combine_address_space(deref->pos, &address_space, ctype->ctype.as);
		mod |= ctype->ctype.modifiers;
	}
	if (!ctype || (ctype->type != SYM_STRUCT && ctype->type != SYM_UNION)) {
		expression_error(expr, "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;
		}
		if (ctype->symbol_list)
			expression_error(expr, "no member '%s' in %s %.*s",
				show_ident(ident), type, namelen, name);
		else
			expression_error(expr, "using member '%s' in "
				"incomplete %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 = get_base_type(member);

	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 += bytes_to_bits(offset);
		expr->type = EXPR_SLICE;
		expr->r_bitpos += member->bit_offset;
		expr->ctype = member;
		return member;
	}

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

	add = evaluate_offset(deref, offset);
	expr->type = EXPR_PREOP;
	expr->op = '*';
	expr->unop = add;

	expr->ctype = member;
	return member;
}

static int is_promoted(struct expression *expr)
{
	while (1) {
		switch (expr->type) {
		case EXPR_BINOP:
		case EXPR_SELECT:
		case EXPR_CONDITIONAL:
			return 1;
		case EXPR_COMMA:
			expr = expr->right;
			continue;
		case EXPR_PREOP:
			switch (expr->op) {
			case '(':
				expr = expr->unop;
				continue;
			case '+':
			case '-':
			case '~':
				return 1;
			default:
				return 0;
			}
		default:
			return 0;
		}
	}
}


static struct symbol *evaluate_type_information(struct expression *expr)
{
	struct symbol *sym = expr->cast_type;
	if (!sym) {
		sym = evaluate_expression(expr->cast_expression);
		if (!sym)
			return NULL;
		/*
		 * Expressions of restricted types will possibly get
		 * promoted - check that here
		 */
		if (is_restricted_type(sym)) {
			if (sym->bit_size < bits_in_int && is_promoted(expr))
				sym = &int_ctype;
		} else if (is_fouled_type(sym)) {
			sym = &int_ctype;
		}
	}
	examine_symbol_type(sym);
	if (is_bitfield_type(sym)) {
		expression_error(expr, "trying to examine bitfield type");
		return NULL;
	}
	return sym;
}

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

	type = evaluate_type_information(expr);
	if (!type)
		return NULL;

	size = type->bit_size;

	if (size < 0 && is_void_type(type)) {
		if (Wpointer_arith)
			warning(expr->pos, "expression using sizeof(void)");
		size = bits_in_char;
	}

	if (is_bool_type(type)) {
		if (Wsizeof_bool)
			warning(expr->pos, "expression using sizeof _Bool");
		size = bits_to_bytes(bits_in_bool) * bits_in_char;
	}

	if (is_function(type->ctype.base_type)) {
		if (Wpointer_arith)
			warning(expr->pos, "expression using sizeof on a function");
		size = bits_in_char;
	}

	if (has_flexible_array(type) && Wflexible_array_sizeof)
		warning(expr->pos, "using sizeof on a flexible structure");

	if (is_array_type(type) && size < 0) {	// VLA, 1-dimension only
		struct expression *base, *size;
		struct symbol *base_type;

		if (type->type == SYM_NODE)
			type = type->ctype.base_type;	// strip the SYM_NODE
		base_type = get_base_type(type);
		if (!base_type)
			goto error;
		if (base_type->bit_size <= 0) {
			base = alloc_expression(expr->pos, EXPR_SIZEOF);
			base->cast_type = base_type;
			if (!evaluate_sizeof(base))
				goto error;
		} else {
			base = alloc_expression(expr->pos, EXPR_VALUE);
			base->value = bits_to_bytes(base_type->bit_size);
			base->ctype = size_t_ctype;
		}
		size = alloc_expression(expr->pos, EXPR_CAST);
		size->cast_type = size_t_ctype;
		size->cast_expression = type->array_size;
		if (!evaluate_expression(size))
			goto error;
		expr->left = size;
		expr->right = base;
		expr->type = EXPR_BINOP;
		expr->op = '*';
		return expr->ctype = size_t_ctype;
	}

error:
	if ((size < 0) || (size & (bits_in_char - 1)))
		expression_error(expr, "cannot size expression");

	expr->type = EXPR_VALUE;
	expr->value = bits_to_bytes(size);
	expr->taint = 0;
	expr->ctype = size_t_ctype;
	return size_t_ctype;
}

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

	type = evaluate_type_information(expr);
	if (!type)
		return NULL;

	if (type->type == SYM_NODE)
		type = type->ctype.base_type;
	if (!type)
		return NULL;
	switch (type->type) {
	case SYM_ARRAY:
		break;
	case SYM_PTR:
		type = get_base_type(type);
		if (type)
			break;
	default:
		expression_error(expr, "expected pointer expression");
		return NULL;
	}
	size = type->bit_size;
	if (size & (bits_in_char-1))
		size = 0;
	expr->type = EXPR_VALUE;
	expr->value = bits_to_bytes(size);
	expr->taint = 0;
	expr->ctype = size_t_ctype;
	return size_t_ctype;
}

static struct symbol *evaluate_alignof(struct expression *expr)
{
	struct symbol *type;

	type = evaluate_type_information(expr);
	if (!type)
		return NULL;

	expr->type = EXPR_VALUE;
	expr->value = type->ctype.alignment;
	expr->taint = 0;
	expr->ctype = size_t_ctype;
	return size_t_ctype;
}

int evaluate_arguments(struct symbol_list *argtypes, struct expression_list *head)
{
	struct expression *expr;
	struct symbol *argtype;
	int i = 1;

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

		if (!ctype)
			return 0;

		target = argtype;
		if (!target) {
			struct symbol *type;
			int class = classify_type(ctype, &type);
			if (is_int(class)) {
				*p = cast_to(expr, integer_promotion(type));
			} else if (class & TYPE_FLOAT) {
				if (type->rank < 0)
					*p = cast_to(expr, &double_ctype);
			} else if (class & TYPE_PTR) {
				if (expr->ctype == &null_ctype)
					*p = cast_to(expr, &ptr_ctype);
				else
					degenerate(expr);
			}
		} else if (!target->forced_arg){
			static char where[30];
			examine_symbol_type(target);
			sprintf(where, "argument %d", i);
			compatible_argument_type(expr, target, p, where);
		}

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

static void convert_index(struct expression *e)
{
	struct expression *child = e->idx_expression;
	unsigned from = e->idx_from;
	unsigned to = e->idx_to + 1;
	e->type = EXPR_POS;
	e->init_offset = from * bits_to_bytes(e->ctype->bit_size);
	e->init_nr = to - from;
	e->init_expr = child;
}

static void convert_ident(struct expression *e)
{
	struct expression *child = e->ident_expression;
	int offset = e->offset;

	e->type = EXPR_POS;
	e->init_offset = offset;
	e->init_nr = 1;
	e->init_expr = child;
}

static void convert_designators(struct expression *e)
{
	while (e) {
		if (e->type == EXPR_INDEX)
			convert_index(e);
		else if (e->type == EXPR_IDENTIFIER)
			convert_ident(e);
		else
			break;
		e = e->init_expr;
	}
}

static void excess(struct expression *e, const char *s)
{
	warning(e->pos, "excessive elements in %s initializer", s);
}

/*
 * implicit designator for the first element
 */
static struct expression *first_subobject(struct symbol *ctype, int class,
					  struct expression **v)
{
	struct expression *e = *v, *new;

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

	if (class & TYPE_PTR) { /* array */
		if (!ctype->bit_size)
			return NULL;
		new = alloc_expression(e->pos, EXPR_INDEX);
		new->idx_expression = e;
		new->ctype = ctype->ctype.base_type;
	} else  {
		struct symbol *field, *p;
		PREPARE_PTR_LIST(ctype->symbol_list, p);
		while (p && !p->ident && is_bitfield_type(p))
			NEXT_PTR_LIST(p);
		field = p;
		FINISH_PTR_LIST(p);
		if (!field)
			return NULL;
		new = alloc_expression(e->pos, EXPR_IDENTIFIER);
		new->ident_expression = e;
		new->field = new->ctype = field;
		new->offset = field->offset;
	}
	*v = new;
	return new;
}

/*
 * sanity-check explicit designators; return the innermost one or NULL
 * in case of error.  Assign types.
 */
static struct expression *check_designators(struct expression *e,
					    struct symbol *ctype)
{
	struct expression *last = NULL;
	const char *err;
	while (1) {
		if (ctype->type == SYM_NODE)
			ctype = ctype->ctype.base_type;
		if (e->type == EXPR_INDEX) {
			struct symbol *type;
			if (ctype->type != SYM_ARRAY) {
				err = "array index in non-array";
				break;
			}
			type = ctype->ctype.base_type;
			if (ctype->bit_size >= 0 && type->bit_size >= 0) {
				unsigned offset = array_element_offset(type->bit_size, e->idx_to);
				if (offset >= ctype->bit_size) {
					err = "index out of bounds in";
					break;
				}
			}
			e->ctype = ctype = type;
			ctype = type;
			last = e;
			if (!e->idx_expression) {
				err = "invalid";
				break;
			}
			e = e->idx_expression;
		} else if (e->type == EXPR_IDENTIFIER) {
			int offset = 0;
			if (ctype->type != SYM_STRUCT && ctype->type != SYM_UNION) {
				err = "field name not in struct or union";
				break;
			}
			ctype = find_identifier(e->expr_ident, ctype->symbol_list, &offset);
			if (!ctype) {
				err = "unknown field name in";
				break;
			}
			e->offset = offset;
			e->field = e->ctype = ctype;
			last = e;
			if (!e->ident_expression) {
				err = "invalid";
				break;
			}
			e = e->ident_expression;
		} else if (e->type == EXPR_POS) {
			err = "internal front-end error: EXPR_POS in";
			break;
		} else
			return last;
	}
	expression_error(e, "%s initializer", err);
	return NULL;
}

/*
 * choose the next subobject to initialize.
 *
 * Get designators for next element, switch old ones to EXPR_POS.
 * Return the resulting expression or NULL if we'd run out of subobjects.
 * The innermost designator is returned in *v.  Designators in old
 * are assumed to be already sanity-checked.
 */
static struct expression *next_designators(struct expression *old,
			     struct symbol *ctype,
			     struct expression *e, struct expression **v)
{
	struct expression *new = NULL;

	if (!old)
		return NULL;
	if (old->type == EXPR_INDEX) {
		struct expression *copy;
		unsigned n;

		copy = next_designators(old->idx_expression,
					old->ctype, e, v);
		if (!copy) {
			n = old->idx_to + 1;
			if (array_element_offset(old->ctype->bit_size, n) == ctype->bit_size) {
				convert_index(old);
				return NULL;
			}
			copy = e;
			*v = new = alloc_expression(e->pos, EXPR_INDEX);
		} else {
			n = old->idx_to;
			new = alloc_expression(e->pos, EXPR_INDEX);
		}

		new->idx_from = new->idx_to = n;
		new->idx_expression = copy;
		new->ctype = old->ctype;
		convert_index(old);
	} else if (old->type == EXPR_IDENTIFIER) {
		struct expression *copy;
		struct symbol *field;
		int offset = 0;

		copy = next_designators(old->ident_expression,
					old->ctype, e, v);
		if (!copy) {
			field = old->field->next_subobject;
			if (!field) {
				convert_ident(old);
				return NULL;
			}
			copy = e;
			*v = new = alloc_expression(e->pos, EXPR_IDENTIFIER);
			/*
			 * We can't necessarily trust "field->offset",
			 * because the field might be in an anonymous
			 * union, and the field offset is then the offset
			 * within that union.
			 *
			 * The "old->offset - old->field->offset"
			 * would be the offset of such an anonymous
			 * union.
			 */
			offset = old->offset - old->field->offset;
		} else {
			field = old->field;
			new = alloc_expression(e->pos, EXPR_IDENTIFIER);
		}

		new->field = field;
		new->expr_ident = field->ident;
		new->ident_expression = copy;
		new->ctype = field;
		new->offset = field->offset + offset;
		convert_ident(old);
	}
	return new;
}

static int handle_initializer(struct expression **ep, int nested,
		int class, struct symbol *ctype, unsigned long mods);

/*
 * deal with traversing subobjects [6.7.8(17,18,20)]
 */
static void handle_list_initializer(struct expression *expr,
		int class, struct symbol *ctype, unsigned long mods)
{
	struct expression *e, *last = NULL, *top = NULL, *next;
	int jumped = 0;	// has the last designator multiple levels?

	if (expr->zero_init)
		free_ptr_list(&expr->expr_list);

	FOR_EACH_PTR(expr->expr_list, e) {
		struct expression **v;
		struct symbol *type;
		int lclass;

		if (e->type != EXPR_INDEX && e->type != EXPR_IDENTIFIER) {
			struct symbol *struct_sym;
			if (!top) {
				top = e;
				last = first_subobject(ctype, class, &top);
			} else {
				last = next_designators(last, ctype, e, &top);
			}
			if (!last) {
				excess(e, class & TYPE_PTR ? "array" :
							"struct or union");
				DELETE_CURRENT_PTR(e);
				continue;
			}
			struct_sym = ctype->type == SYM_NODE ? ctype->ctype.base_type : ctype;
			if (Wdesignated_init && struct_sym->designated_init)
				warning(e->pos, "%s%.*s%spositional init of field in %s %s, declared with attribute designated_init",
					ctype->ident ? "in initializer for " : "",
					ctype->ident ? ctype->ident->len : 0,
					ctype->ident ? ctype->ident->name : "",
					ctype->ident ? ": " : "",
					get_type_name(struct_sym->type),
					show_ident(struct_sym->ident));
			if (jumped && Wpast_deep_designator) {
				warning(e->pos, "advancing past deep designator");
				jumped = 0;
			}
			REPLACE_CURRENT_PTR(e, last);
		} else {
			next = check_designators(e, ctype);
			if (!next) {
				DELETE_CURRENT_PTR(e);
				continue;
			}
			top = next;
			/* deeper than one designator? */
			jumped = top != e;
			convert_designators(last);
			last = e;
		}

found:
		lclass = classify_type(top->ctype, &type);
		if (top->type == EXPR_INDEX)
			v = &top->idx_expression;
		else
			v = &top->ident_expression;

		mods |= ctype->ctype.modifiers & MOD_STORAGE;
		if (handle_initializer(v, 1, lclass, top->ctype, mods))
			continue;

		if (!(lclass & TYPE_COMPOUND)) {
			warning(e->pos, "bogus scalar initializer");
			DELETE_CURRENT_PTR(e);
			continue;
		}

		next = first_subobject(type, lclass, v);
		if (next) {
			warning(e->pos, "missing braces around initializer");
			top = next;
			goto found;
		}

		DELETE_CURRENT_PTR(e);
		excess(e, lclass & TYPE_PTR ? "array" : "struct or union");

	} END_FOR_EACH_PTR(e);

	convert_designators(last);
	expr->ctype = ctype;
}

static int is_string_literal(struct expression **v)
{
	struct expression *e = *v;
	while (e && e->type == EXPR_PREOP && e->op == '(')
		e = e->unop;
	if (!e || e->type != EXPR_STRING)
		return 0;
	if (e != *v && Wparen_string)
		warning(e->pos,
			"array initialized from parenthesized string constant");
	*v = e;
	return 1;
}

/*
 * We want a normal expression, possibly in one layer of braces.  Warn
 * if the latter happens inside a list (it's legal, but likely to be
 * an effect of screwup).  In case of anything not legal, we are definitely
 * having an effect of screwup, so just fail and let the caller warn.
 */
static struct expression *handle_scalar(struct expression *e, int nested)
{
	struct expression *v = NULL, *p;
	int count = 0;

	/* normal case */
	if (e->type != EXPR_INITIALIZER)
		return e;

	FOR_EACH_PTR(e->expr_list, p) {
		if (!v)
			v = p;
		count++;
	} END_FOR_EACH_PTR(p);
	if (count != 1)
		return NULL;
	switch(v->type) {
	case EXPR_INITIALIZER:
	case EXPR_INDEX:
	case EXPR_IDENTIFIER:
		return NULL;
	default:
		break;
	}
	if (nested)
		warning(e->pos, "braces around scalar initializer");
	return v;
}

/*
 * deal with the cases that don't care about subobjects:
 * scalar <- assignment expression, possibly in braces [6.7.8(11)]
 * character array <- string literal, possibly in braces [6.7.8(14)]
 * struct or union <- assignment expression of compatible type [6.7.8(13)]
 * compound type <- initializer list in braces [6.7.8(16)]
 * The last one punts to handle_list_initializer() which, in turn will call
 * us for individual elements of the list.
 *
 * We do not handle 6.7.8(15) (wide char array <- wide string literal) for
 * the lack of support of wide char stuff in general.
 *
 * One note: we need to take care not to evaluate a string literal until
 * we know that we *will* handle it right here.  Otherwise we would screw
 * the cases like struct { struct {char s[10]; ...} ...} initialized with
 * { "string", ...} - we need to preserve that string literal recognizable
 * until we dig into the inner struct.
 */
static int handle_initializer(struct expression **ep, int nested,
		int class, struct symbol *ctype, unsigned long mods)
{
	struct expression *e = *ep, *p;
	struct symbol *type;

	if (!e)
		return 0;

	/* scalar */
	if (!(class & TYPE_COMPOUND)) {
		e = handle_scalar(e, nested);
		if (!e)
			return 0;
		*ep = e;
		if (!evaluate_expression(e))
			return 1;
		compatible_assignment_types(e, ctype, ep, "initializer");
		/*
		 * Initializers for static storage duration objects
		 * shall be constant expressions or a string literal [6.7.8(4)].
		 */
		mods |= ctype->ctype.modifiers;
		mods &= (MOD_TOPLEVEL | MOD_STATIC);
		if (mods && !(e->flags & (CEF_ACE | CEF_ADDR)))
			if (Wconstexpr_not_const)
				warning(e->pos, "non-constant initializer for static object");

		return 1;
	}

	/*
	 * sublist; either a string, or we dig in; the latter will deal with
	 * pathologies, so we don't need anything fancy here.
	 */
	if (e->type == EXPR_INITIALIZER) {
		if (is_string_type(ctype)) {
			struct expression *v = NULL;
			int count = 0;

			FOR_EACH_PTR(e->expr_list, p) {
				if (!v)
					v = p;
				count++;
			} END_FOR_EACH_PTR(p);
			if (count == 1 && is_string_literal(&v)) {
				*ep = e = v;
				goto String;
			}
		}
		handle_list_initializer(e, class, ctype, mods);
		return 1;
	}

	/* string */
	if (is_string_literal(&e)) {
		/* either we are doing array of char, or we'll have to dig in */
		if (is_string_type(ctype)) {
			*ep = e;
			goto String;
		}
		return 0;
	}
	/* struct or union can be initialized by compatible */
	if (class != TYPE_COMPOUND)
		return 0;
	type = evaluate_expression(e);
	if (!type)
		return 0;
	if (ctype->type == SYM_NODE)
		ctype = ctype->ctype.base_type;
	if (type->type == SYM_NODE)
		type = type->ctype.base_type;
	if (ctype == type)
		return 1;
	return 0;

String:
	p = alloc_expression(e->pos, EXPR_STRING);
	*p = *e;
	type = evaluate_expression(p);
	if (ctype->bit_size != -1) {
		struct symbol *char_type = e->wide ? wchar_ctype : &char_ctype;
		unsigned int size_with_null = ctype->bit_size + char_type->bit_size;
		if (size_with_null < type->bit_size)
			warning(e->pos,
				"too long initializer-string for array of char");
		else if (Winit_cstring && size_with_null == type->bit_size) {
			warning(e->pos,
				"too long initializer-string for array of char(no space for nul char)");
		}
	}
	*ep = p;
	return 1;
}

static void evaluate_initializer(struct symbol *ctype, struct expression **ep)
{
	struct symbol *type;
	int class = classify_type(ctype, &type);
	if (!handle_initializer(ep, 0, class, ctype, 0))
		expression_error(*ep, "invalid initializer");
}

static struct symbol *cast_to_bool(struct expression *expr)
{
	struct expression *old = expr->cast_expression;
	struct expression *zero;
	struct symbol *otype;
	int oclass = classify_type(degenerate(old), &otype);
	struct symbol *ctype;

	if (oclass & TYPE_COMPOUND)
		return NULL;

	zero = alloc_const_expression(expr->pos, 0);
	if (oclass & TYPE_PTR)
		zero->ctype = otype;
	expr->op = SPECIAL_NOTEQUAL;
	ctype = usual_conversions(expr->op, old, zero,
			oclass, TYPE_NUM, otype, zero->ctype);
	expr->type = EXPR_COMPARE;
	expr->left = cast_to(old, ctype);
	expr->right = cast_to(zero, ctype);

	return expr->ctype;
}

static int cast_flags(struct expression *expr, struct expression *old)
{
	struct symbol *t;
	int class;
	int flags = CEF_NONE;

	class = classify_type(expr->ctype, &t);
	if (class & TYPE_NUM) {
		flags = old->flags & ~CEF_CONST_MASK;
		/*
		 * Casts to numeric types never result in address
		 * constants [6.6(9)].
		 */
		flags &= ~CEF_ADDR;

		/*
		 * As an extension, treat address constants cast to
		 * integer type as an arithmetic constant.
		 */
		if (old->flags & CEF_ADDR)
			flags = CEF_ACE;

		/*
		 * Cast to float type -> not an integer constant
		 * expression [6.6(6)].
		 */
		if (class & TYPE_FLOAT)
			flags &= ~CEF_CLR_ICE;
		/*
		 * Casts of float literals to integer type results in
		 * a constant integer expression [6.6(6)].
		 */
		else if (old->flags & CEF_FLOAT)
			flags = CEF_SET_ICE;
	} else if (class & TYPE_PTR) {
		/*
		 * Casts of integer literals to pointer type yield
		 * address constants [6.6(9)].
		 *
		 * As an extension, treat address constants cast to a
		 * different pointer type as address constants again.
		 *
		 * As another extension, treat integer constant
		 * expressions (in contrast to literals) cast to
		 * pointer type as address constants.
		 */
		if (old->flags & (CEF_ICE | CEF_ADDR))
			flags = CEF_ADDR;
	}

	return flags;
}

///
// check if a type matches one of the members of a union type
// @utype: the union type
// @type: to type to check
// @return: to identifier of the matching type in the union.
static struct symbol *find_member_type(struct symbol *utype, struct symbol *type)
{
	struct symbol *t, *member;

	if (utype->type != SYM_UNION)
		return NULL;

	FOR_EACH_PTR(utype->symbol_list, member) {
		classify_type(member, &t);
		if (type == t)
			return member;
	} END_FOR_EACH_PTR(member);
	return NULL;
}

static struct symbol *evaluate_compound_literal(struct expression *expr, struct expression *source)
{
	struct expression *addr = alloc_expression(expr->pos, EXPR_SYMBOL);
	struct symbol *sym = expr->cast_type;

	sym->initializer = source;
	evaluate_symbol(sym);

	addr->ctype = &lazy_ptr_ctype;	/* Lazy eval */
	addr->symbol = sym;
	if (sym->ctype.modifiers & MOD_TOPLEVEL)
		addr->flags |= CEF_ADDR;

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

static struct symbol *evaluate_cast(struct expression *expr)
{
	struct expression *source = expr->cast_expression;
	struct symbol *ctype;
	struct symbol *ttype, *stype;
	struct symbol *member;
	int tclass, sclass;
	struct ident *tas = NULL, *sas = NULL;

	if (!source)
		return NULL;

	/*
	 * 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
	 * (cfr. compound literals: C99 & C11 6.5.2.5).
	 *
	 * 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 (source->type == EXPR_INITIALIZER)
		return evaluate_compound_literal(expr, source);

	ctype = examine_symbol_type(expr->cast_type);
	ctype = unqualify_type(ctype);
	expr->ctype = ctype;
	expr->cast_type = ctype;

	evaluate_expression(source);
	degenerate(source);

	tclass = classify_type(ctype, &ttype);

	expr->flags = cast_flags(expr, source);

	/*
	 * 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 (ttype == &void_ctype)
		goto out;

	stype = source->ctype;
	if (!stype) {
		expression_error(expr, "cast from unknown type");
		goto out;
	}
	sclass = classify_type(stype, &stype);

	if (expr->type == EXPR_FORCE_CAST)
		goto out;

	if (tclass & (TYPE_COMPOUND | TYPE_FN)) {
		/*
		 * Special case: cast to union type (GCC extension)
		 * The effect is similar to a compound literal except
		 * that the result is a rvalue.
		 */
		if ((member = find_member_type(ttype, stype))) {
			struct expression *item, *init;

			if (Wunion_cast)
				warning(expr->pos, "cast to union type");

			item = alloc_expression(source->pos, EXPR_IDENTIFIER);
			item->expr_ident = member->ident;
			item->ident_expression = source;

			init = alloc_expression(source->pos, EXPR_INITIALIZER);
			add_expression(&init->expr_list, item);

			// FIXME: this should be a rvalue
			evaluate_compound_literal(expr, init);
			return ctype;
		}

		warning(expr->pos, "cast to non-scalar");
	}

	if (sclass & TYPE_COMPOUND)
		warning(expr->pos, "cast from non-scalar");

	/* allowed cast unfouls */
	if (sclass & TYPE_FOULED)
		stype = unfoul(stype);

	if (ttype != stype) {
		if ((tclass & TYPE_RESTRICT) && restricted_value(source, ttype))
			warning(expr->pos, "cast to %s",
				show_typename(ttype));
		if (sclass & TYPE_RESTRICT) {
			if (ttype == &bool_ctype) {
				if (sclass & TYPE_FOULED)
					warning(expr->pos, "%s degrades to integer",
						show_typename(stype));
			} else {
				warning(expr->pos, "cast from %s",
					show_typename(stype));
			}
		}
	}

	if ((ttype == &ulong_ctype || ttype == uintptr_ctype) && !Wcast_from_as)
		tas = &bad_address_space;
	else if (tclass == TYPE_PTR) {
		examine_pointer_target(ttype);
		tas = ttype->ctype.as;
	}

	if ((stype == &ulong_ctype || stype == uintptr_ctype))
		sas = &bad_address_space;
	else if (sclass == TYPE_PTR) {
		examine_pointer_target(stype);
		sas = stype->ctype.as;
	}

	if (!tas && valid_as(sas))
		warning(expr->pos, "cast removes address space '%s' of expression", show_as(sas));
	if (valid_as(tas) && valid_as(sas) && tas != sas)
		warning(expr->pos, "cast between address spaces (%s -> %s)", show_as(sas), show_as(tas));
	if (valid_as(tas) && !sas &&
	    !is_null_pointer_constant(source) && Wcast_to_as)
		warning(expr->pos,
			"cast adds address space '%s' to expression", show_as(tas));

	if (!(ttype->ctype.modifiers & MOD_PTRINHERIT) && tclass == TYPE_PTR &&
	    !tas && (source->flags & CEF_ICE)) {
		if (ttype->ctype.base_type == &void_ctype) {
			if (is_zero_constant(source)) {
				/* NULL */
				expr->type = EXPR_VALUE;
				expr->ctype = &null_ctype;
				expr->value = 0;
				return expr->ctype;
			}
		}
	}

	if (ttype == &bool_ctype)
		cast_to_bool(expr);

	// checks pointers to restricted
	while (Wbitwise_pointer && tclass == TYPE_PTR && sclass == TYPE_PTR) {
		tclass = classify_type(ttype->ctype.base_type, &ttype);
		sclass = classify_type(stype->ctype.base_type, &stype);
		if (ttype == stype)
			break;
		if (!ttype || !stype)
			break;
		if (ttype == &void_ctype || stype == &void_ctype)
			break;
		if (tclass & TYPE_RESTRICT) {
			warning(expr->pos, "cast to %s", show_typename(ctype));
			break;
		}
		if (sclass & TYPE_RESTRICT) {
			warning(expr->pos, "cast from %s", show_typename(source->ctype));
			break;
		}
	}
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);

	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 = get_base_type(ctype);

	if (ctype->type != SYM_FN) {
		struct expression *arg;

		if (fn->ctype == &bad_ctype)
			return NULL;

		expression_error(expr, "not a function %s",
			     show_ident(sym->ident));
		/* do typechecking in arguments */
		FOR_EACH_PTR (arglist, arg) {
			evaluate_expression(arg);
		} END_FOR_EACH_PTR(arg);
		return NULL;
	}

	examine_fn_arguments(ctype);
        if (sym->type == SYM_NODE && fn->type == EXPR_PREOP &&
	    sym->op && sym->op->args) {
		if (!sym->op->args(expr))
			return NULL;
	} else {
		if (!evaluate_arguments(ctype->arguments, arglist))
			return NULL;
		args = expression_list_size(expr->args);
		fnargs = symbol_list_size(ctype->arguments);
		if (args < fnargs) {
			expression_error(expr,
				     "not enough arguments for function %s",
				     show_ident(sym->ident));
			return NULL;
		}
		if (args > fnargs && !ctype->variadic)
			expression_error(expr,
				     "too many arguments for function %s",
				     show_ident(sym->ident));
	}
	expr->ctype = ctype->ctype.base_type;
	if (sym->type == SYM_NODE) {
		if (evaluate_symbol_call(expr))
			return expr->ctype;
	}
	return expr->ctype;
}

static struct symbol *evaluate_offsetof(struct expression *expr)
{
	struct expression *e = expr->down;
	struct symbol *ctype = expr->in;
	int class;

	if (expr->op == '.') {
		struct symbol *field;
		int offset = 0;
		if (!ctype) {
			expression_error(expr, "expected structure or union");
			return NULL;
		}
		examine_symbol_type(ctype);
		class = classify_type(ctype, &ctype);
		if (class != TYPE_COMPOUND) {
			expression_error(expr, "expected structure or union");
			return NULL;
		}

		field = find_identifier(expr->ident, ctype->symbol_list, &offset);
		if (!field) {
			expression_error(expr, "unknown member");
			return NULL;
		}
		ctype = field;
		expr->type = EXPR_VALUE;
		expr->flags = CEF_SET_ICE;
		expr->value = offset;
		expr->taint = 0;
		expr->ctype = size_t_ctype;
	} else {
		if (!ctype) {
			expression_error(expr, "expected structure or union");
			return NULL;
		}
		examine_symbol_type(ctype);
		class = classify_type(ctype, &ctype);
		if (class != (TYPE_COMPOUND | TYPE_PTR)) {
			expression_error(expr, "expected array");
			return NULL;
		}
		ctype = ctype->ctype.base_type;
		if (!expr->index) {
			expr->type = EXPR_VALUE;
			expr->flags = CEF_SET_ICE;
			expr->value = 0;
			expr->taint = 0;
			expr->ctype = size_t_ctype;
		} else {
			struct expression *idx = expr->index, *m;
			struct symbol *i_type = evaluate_expression(idx);
			unsigned old_idx_flags;
			int i_class = classify_type(i_type, &i_type);

			if (!is_int(i_class)) {
				expression_error(expr, "non-integer index");
				return NULL;
			}
			unrestrict(idx, i_class, &i_type);
			old_idx_flags = idx->flags;
			idx = cast_to(idx, size_t_ctype);
			idx->flags = old_idx_flags;
			m = alloc_const_expression(expr->pos,
						   bits_to_bytes(ctype->bit_size));
			m->ctype = size_t_ctype;
			m->flags = CEF_SET_INT;
			expr->type = EXPR_BINOP;
			expr->left = idx;
			expr->right = m;
			expr->op = '*';
			expr->ctype = size_t_ctype;
			expr->flags = m->flags & idx->flags & ~CEF_CONST_MASK;
		}
	}
	if (e) {
		struct expression *copy = __alloc_expression(0);
		*copy = *expr;
		if (e->type == EXPR_OFFSETOF)
			e->in = ctype;
		if (!evaluate_expression(e))
			return NULL;
		expr->type = EXPR_BINOP;
		expr->flags = e->flags & copy->flags & ~CEF_CONST_MASK;
		expr->op = '+';
		expr->ctype = size_t_ctype;
		expr->left = copy;
		expr->right = e;
	}
	return size_t_ctype;
}

static void check_label_declaration(struct position pos, struct symbol *label)
{
	switch (label->namespace) {
	case NS_LABEL:
		if (label->stmt)
			break;
		sparse_error(pos, "label '%s' was not declared", show_ident(label->ident));
		/* fallthrough */
	case NS_NONE:
		current_fn->bogus_linear = 1;
	default:
		break;
	}
}

static int type_selection(struct symbol *ctrl, struct symbol *type)
{
	struct ctype c = { .base_type = ctrl };
	struct ctype t = { .base_type = type };

	return !type_difference(&c, &t, 0, 0);
}

static struct symbol *evaluate_generic_selection(struct expression *expr)
{
	struct type_expression *map;
	struct expression *res;
	struct symbol source;
	struct symbol *ctrl;

	if (!evaluate_expression(expr->control))
		return NULL;
	if (!(ctrl = degenerate(expr->control)))
		return NULL;

	source = *ctrl;
	source.ctype.modifiers &= ~(MOD_QUALIFIER|MOD_ATOMIC);
	for (map = expr->map; map; map = map->next) {
		struct symbol *stype = map->type;
		struct symbol *base;

		if (!evaluate_symbol(stype))
			continue;

		base = stype->ctype.base_type;
		if (base->type == SYM_ARRAY && base->array_size) {
			get_expression_value_silent(base->array_size);
			if (base->array_size->type == EXPR_VALUE)
				continue;
			sparse_error(stype->pos, "variable length array type in generic selection");
			continue;
		}
		if (is_func_type(stype)) {
			sparse_error(stype->pos, "function type in generic selection");
			continue;
		}
		if (stype->bit_size <= 0 || is_void_type(stype)) {
			sparse_error(stype->pos, "incomplete type in generic selection");
			continue;
		}
		if (!type_selection(&source, stype))
			continue;

		res = map->expr;
		goto found;
	}
	res = expr->def;
	if (!res) {
		sparse_error(expr->pos, "no generic selection for '%s'", show_typename(ctrl));
		return NULL;
	}

found:
	*expr = *res;
	return evaluate_expression(expr);
}

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:
		expression_error(expr, "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:
		evaluate_expression(expr->left);
		evaluate_expression(expr->right);
		if (!valid_subexpr_type(expr))
			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:
		evaluate_expression(expr->left);
		evaluate_expression(expr->right);
		if (!valid_subexpr_type(expr))
			return NULL;
		return evaluate_compare(expr);
	case EXPR_ASSIGNMENT:
		evaluate_expression(expr->left);
		evaluate_expression(expr->right);
		if (!valid_subexpr_type(expr))
			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:
	case EXPR_FORCE_CAST:
	case EXPR_IMPLIED_CAST:
		return evaluate_cast(expr);
	case EXPR_SIZEOF:
		return evaluate_sizeof(expr);
	case EXPR_PTRSIZEOF:
		return evaluate_ptrsizeof(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_SELECT:
	case EXPR_CONDITIONAL:
		return evaluate_conditional_expression(expr);
	case EXPR_STATEMENT:
		expr->ctype = evaluate_statement(expr->statement);
		return expr->ctype;

	case EXPR_LABEL:
		expr->ctype = &ptr_ctype;
		check_label_declaration(expr->pos, expr->label_symbol);
		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;

	case EXPR_OFFSETOF:
		return evaluate_offsetof(expr);

	case EXPR_GENERIC:
		return evaluate_generic_selection(expr);

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

void check_duplicates(struct symbol *sym)
{
	int declared = 0;
	struct symbol *next = sym;
	int initialized = sym->initializer != NULL;

	while ((next = next->same_symbol) != NULL) {
		const char *typediff;
		evaluate_symbol(next);
		if (initialized && next->initializer) {
			sparse_error(sym->pos, "symbol '%s' has multiple initializers (originally initialized at %s:%d)",
				show_ident(sym->ident),
				stream_name(next->pos.stream), next->pos.line);
			/* Only warn once */
			initialized = 0;
		}
		declared++;
		typediff = type_difference(&sym->ctype, &next->ctype, 0, 0);
		if (typediff) {
			sparse_error(sym->pos, "symbol '%s' redeclared with different type (%s):",
				show_ident(sym->ident), typediff);
			info(sym->pos, "   %s", show_typename(sym));
			info(next->pos, "note: previously declared as:");
			info(next->pos, "   %s", show_typename(next));
			return;
		}
	}
	if (!declared) {
		unsigned long mod = sym->ctype.modifiers;
		if (mod & (MOD_STATIC | MOD_REGISTER | MOD_EXT_VISIBLE))
			return;
		if (!(mod & MOD_TOPLEVEL))
			return;
		if (!Wdecl)
			return;
		if (sym->ident == &main_ident)
			return;
		warning(sym->pos, "symbol '%s' was not declared. Should it be static?", show_ident(sym->ident));
	}
}

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

	if (!sym)
		return sym;
	if (sym->evaluated)
		return sym;
	sym->evaluated = 1;

	sym = examine_symbol_type(sym);
	base_type = get_base_type(sym);
	if (!base_type)
		return NULL;

	/* Evaluate the initializers */
	if (sym->initializer)
		evaluate_initializer(sym, &sym->initializer);

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

		if (sym->definition && sym->definition != sym)
			return evaluate_symbol(sym->definition);

		current_fn = sym;

		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;
	}

	return base_type;
}

void evaluate_symbol_list(struct symbol_list *list)
{
	struct symbol *sym;

	FOR_EACH_PTR(list, sym) {
		has_error &= ~ERROR_CURR_PHASE;
		evaluate_symbol(sym);
		check_duplicates(sym);
	} END_FOR_EACH_PTR(sym);
}

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

	evaluate_expression(expr);
	fntype = current_fn->ctype.base_type;
	rettype = fntype->ctype.base_type;
	if (!rettype || rettype == &void_ctype) {
		if (expr && expr->ctype && !is_void_type(expr->ctype))
			expression_error(expr, "return expression in %s function", rettype?"void":"typeless");
		if (expr && Wreturn_void)
			warning(stmt->pos, "returning void-valued expression");
		return NULL;
	}

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

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

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

static void evaluate_iterator(struct statement *stmt)
{
	evaluate_symbol_list(stmt->iterator_syms);
	evaluate_conditional(stmt->iterator_pre_condition, 1);
	evaluate_conditional(stmt->iterator_post_condition,1);
	evaluate_statement(stmt->iterator_pre_statement);
	evaluate_statement(stmt->iterator_statement);
	evaluate_statement(stmt->iterator_post_statement);
}


static void parse_asm_constraint(struct asm_operand *op)
{
	struct expression *constraint = op->constraint;
	const char *str = constraint->string->data;
	int c;

	switch (str[0]) {
	case '\0':
		sparse_error(constraint->pos, "invalid ASM constraint (\"\")");
		break;
	case '+':
		op->is_modify = true;
		/* fall-through */
	case '=':
		op->is_assign = true;
		str++;
		break;
	}

	while ((c = *str++)) {
		switch (c) {
		case '=':
		case '+':
			sparse_error(constraint->pos, "invalid ASM constraint '%c'", c);
			break;

		case '&':
			op->is_earlyclobber = true;
			break;
		case '%':
			op->is_commutative = true;
			break;
		case 'r':
			op->is_register = true;
			break;

		case 'm':
		case 'o':
		case 'V':
		case 'Q':
			op->is_memory = true;
			break;

		case '<':
		case '>':
			// FIXME: ignored for now
			break;

		case ',':
			// FIXME: multiple alternative constraints
			break;

		case '0' ... '9':
			// FIXME: numeric  matching constraint?
			break;
		case '[':
			// FIXME: symbolic matching constraint
			return;

		default:
			if (arch_target->asm_constraint)
				str = arch_target->asm_constraint(op, c, str);

			// FIXME: multi-letter constraints
			break;
		}
	}

	// FIXME: how to deal with multi-constraint?
	if (op->is_register)
		op->is_memory = 0;
}

static void verify_output_constraint(struct asm_operand *op)
{
	struct expression *expr = op->constraint;
	const char *constraint = expr->string->data;

	if (!op->is_assign)
		expression_error(expr, "output constraint is not an assignment constraint (\"%s\")", constraint);
}

static void verify_input_constraint(struct asm_operand *op)
{
	struct expression *expr = op->constraint;
	const char *constraint = expr->string->data;

	if (op->is_assign)
		expression_error(expr, "input constraint with assignment (\"%s\")", constraint);
}

static void evaluate_asm_memop(struct asm_operand *op)
{
	if (op->is_memory) {
		struct expression *expr = op->expr;
		struct expression *addr;

		// implicit addressof
		addr = alloc_expression(expr->pos, EXPR_PREOP);
		addr->op = '&';
		addr->unop = expr;

		evaluate_addressof(addr);
		op->expr = addr;
	} else {
		evaluate_expression(op->expr);
		degenerate(op->expr);
	}
}

static void evaluate_asm_statement(struct statement *stmt)
{
	struct expression *expr;
	struct asm_operand *op;
	struct symbol *sym;

	if (!stmt->asm_string)
		return;

	FOR_EACH_PTR(stmt->asm_outputs, op) {
		/* Identifier */

		/* Constraint */
		if (op->constraint) {
			parse_asm_constraint(op);
			verify_output_constraint(op);
		}

		/* Expression */
		expr = op->expr;
		if (!evaluate_expression(expr))
			return;
		if (!lvalue_expression(expr))
			warning(expr->pos, "asm output is not an lvalue");
		evaluate_assign_to(expr, expr->ctype);
		evaluate_asm_memop(op);
	} END_FOR_EACH_PTR(op);

	FOR_EACH_PTR(stmt->asm_inputs, op) {
		/* Identifier */

		/* Constraint */
		if (op->constraint) {
			parse_asm_constraint(op);
			verify_input_constraint(op);
		}

		/* Expression */
		if (!evaluate_expression(op->expr))
			return;
		evaluate_asm_memop(op);
	} END_FOR_EACH_PTR(op);

	FOR_EACH_PTR(stmt->asm_clobbers, expr) {
		if (!expr) {
			sparse_error(stmt->pos, "bad asm clobbers");
			return;
		}
		if (expr->type == EXPR_STRING)
			continue;
		expression_error(expr, "asm clobber is not a string");
	} END_FOR_EACH_PTR(expr);

	FOR_EACH_PTR(stmt->asm_labels, sym) {
		if (!sym || sym->type != SYM_LABEL) {
			sparse_error(stmt->pos, "bad asm label");
			return;
		}
	} END_FOR_EACH_PTR(sym);
}

static void evaluate_case_statement(struct statement *stmt)
{
	evaluate_expression(stmt->case_expression);
	evaluate_expression(stmt->case_to);
	evaluate_statement(stmt->case_statement);
}

static void check_case_type(struct expression *switch_expr,
			    struct expression *case_expr,
			    struct expression **enumcase)
{
	struct symbol *switch_type, *case_type;
	int sclass, cclass;

	if (!case_expr)
		return;

	switch_type = switch_expr->ctype;
	case_type = evaluate_expression(case_expr);

	if (!switch_type || !case_type)
		goto Bad;
	if (enumcase) {
		if (*enumcase)
			warn_for_different_enum_types(case_expr->pos, case_type, (*enumcase)->ctype);
		else if (is_enum_type(case_type))
			*enumcase = case_expr;
	}

	sclass = classify_type(switch_type, &switch_type);
	cclass = classify_type(case_type, &case_type);

	/* both should be arithmetic */
	if (!(sclass & cclass & TYPE_NUM))
		goto Bad;

	/* neither should be floating */
	if ((sclass | cclass) & TYPE_FLOAT)
		goto Bad;

	/* if neither is restricted, we are OK */
	if (!((sclass | cclass) & TYPE_RESTRICT))
		return;

	if (!restricted_binop_type(SPECIAL_EQUAL, case_expr, switch_expr,
				   cclass, sclass, case_type, switch_type)) {
		unrestrict(case_expr, cclass, &case_type);
		unrestrict(switch_expr, sclass, &switch_type);
	}
	return;

Bad:
	expression_error(case_expr, "incompatible types for 'case' statement");
}

static void evaluate_switch_statement(struct statement *stmt)
{
	struct symbol *sym;
	struct expression *enumcase = NULL;
	struct expression **enumcase_holder = &enumcase;
	struct expression *sel = stmt->switch_expression;

	evaluate_expression(sel);
	evaluate_statement(stmt->switch_statement);
	if (!sel)
		return;
	if (sel->ctype && is_enum_type(sel->ctype))
		enumcase_holder = NULL; /* Only check cases against switch */

	FOR_EACH_PTR(stmt->switch_case->symbol_list, sym) {
		struct statement *case_stmt = sym->stmt;
		check_case_type(sel, case_stmt->case_expression, enumcase_holder);
		check_case_type(sel, case_stmt->case_to, enumcase_holder);
	} END_FOR_EACH_PTR(sym);
}

static void evaluate_goto_statement(struct statement *stmt)
{
	struct symbol *label = stmt->goto_label;

	if (!label) {
		// no label associated, may be a computed goto
		evaluate_expression(stmt->goto_expression);
		return;
	}

	check_label_declaration(stmt->pos, label);
}

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

	switch (stmt->type) {
	case STMT_DECLARATION: {
		struct symbol *s;
		FOR_EACH_PTR(stmt->declaration, s) {
			evaluate_symbol(s);
		} END_FOR_EACH_PTR(s);
		return NULL;
	}

	case STMT_RETURN:
		return evaluate_return_expression(stmt);

	case STMT_EXPRESSION:
		if (!evaluate_expression(stmt->expression))
			return NULL;
		if (stmt->expression->ctype == &null_ctype)
			stmt->expression = cast_to(stmt->expression, &ptr_ctype);
		return unqualify_type(degenerate(stmt->expression));

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

		/* Evaluate the return symbol in the compound statement */
		evaluate_symbol(stmt->ret);

		/*
		 * Then, evaluate each statement, making the type of the
		 * compound statement be the type of the last statement
		 */
		type = evaluate_statement(stmt->args);
		FOR_EACH_PTR(stmt->stmts, s) {
			type = evaluate_statement(s);
		} END_FOR_EACH_PTR(s);
		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_switch_statement(stmt);
		return NULL;
	case STMT_CASE:
		evaluate_case_statement(stmt);
		return NULL;
	case STMT_LABEL:
		return evaluate_statement(stmt->label_statement);
	case STMT_GOTO:
		evaluate_goto_statement(stmt);
		return NULL;
	case STMT_NONE:
		break;
	case STMT_ASM:
		evaluate_asm_statement(stmt);
		return NULL;
	case STMT_CONTEXT:
		evaluate_expression(stmt->expression);
		return NULL;
	case STMT_RANGE:
		evaluate_expression(stmt->range_expression);
		evaluate_expression(stmt->range_low);
		evaluate_expression(stmt->range_high);
		return NULL;
	}
	return NULL;
}