[PATCH 12/73] evaluate: Fix pointer arithmetic, incomplete types, and qualifiers

[Bart Van Assche <bvanassche@acm.org>]

Fix type checking and qualifier handling across evaluate.c, parse.c,
symbol.c, and symbol.h:
- Distinguish forward-declared incomplete structs and unions
  (bit_size = -1) from complete GNU empty structs (bit_size = 0) via
  sym->defined, and preserve bit_size = -1 on arrays of incomplete types.
- Preserve unsigned integer index offsets in evaluate_ptr_add() and
  diagnose pointer addition and subtraction on incomplete types.
- Diagnose incomplete types in evaluate_alignof() and incomplete array or
  multi-dimensional VLA types in evaluate_generic_selection().
- Guard null index types in evaluate_offsetof(), null current_fn in
  check_label_declaration(), and symbolic '[...]' asm constraints.
- Preserve noderef and nocast qualifiers across conditional pointer
  targets and check pointee MOD_NOCAST on pointer casts.

Signed-off-by: Bart Van Assche <bvanassche@acm.org>
---
 evaluate.c                    | 104 ++++++++++++++++++++++++++++------
 parse.c                       |   2 +
 symbol.c                      |  12 +++-
 symbol.h                      |   2 +-
 validation/eval-type-checks.c |  89 +++++++++++++++++++++++++++++
 5 files changed, 187 insertions(+), 22 deletions(-)
 create mode 100644 validation/eval-type-checks.c

diff --git a/evaluate.c b/evaluate.c
index 40778f4e8a63..0e4e64d33192 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -246,6 +246,8 @@ static struct symbol *base_type(struct symbol *node, unsigned long *modp, struct
 	return node;
 }
 
+#define MOD_IGN (MOD_QUALIFIER | MOD_FUN_ATTR)
+
 static int is_same_type(struct expression *expr, struct symbol *new)
 {
 	struct symbol *old = expr->ctype;
@@ -273,6 +275,13 @@ static int is_same_type(struct expression *expr, struct symbol *new)
 		if (difmod == MOD_CONST)
 			return 0;
 	}
+	if (old->type == SYM_PTR && new->type == SYM_PTR && oldas == newas &&
+	    (oldmod & MOD_NOCAST) == (newmod & MOD_NOCAST)) {
+		if (!type_difference(&old->ctype, &new->ctype,
+				     MOD_IGN | MOD_NODEREF, MOD_IGN | MOD_NODEREF) ||
+		    ((oldmod & MOD_NOCAST) && is_void_type(new->ctype.base_type)))
+			return 0;
+	}
 	if ((oldmod | newmod) & MOD_NOCAST) {
 		const char *tofrom = "to/from";
 		if (!(newmod & MOD_NOCAST))
@@ -588,6 +597,10 @@ static struct symbol *evaluate_ptr_add(struct expression *expr, struct symbol *i
 		expression_error(expr, "arithmetics on pointers to functions");
 		return NULL;
 	}
+	if (!is_void_type(base) && base->bit_size < 0) {
+		expression_error(expr, "arithmetics on pointers to incomplete type");
+		return NULL;
+	}
 
 	/* Get the size of whatever the pointer points to */
 	multiply = is_void_type(base) ? 1 : bits_to_bytes(base->bit_size);
@@ -603,10 +616,10 @@ static struct symbol *evaluate_ptr_add(struct expression *expr, struct symbol *i
 		struct expression *val = alloc_expression(expr->pos, EXPR_VALUE);
 		unsigned long long v = index->value, mask;
 		mask = sign_bit(itype->bit_size);
-		if (v & mask)
+		if (!(itype->ctype.modifiers & MOD_UNSIGNED) && (v & mask))
 			v |= -mask;
 		else
-			v &= mask - 1;
+			v &= mask | (mask - 1);
 		v *= multiply;
 		v &= bits_mask(bits_in_pointer);
 		val->value = v;
@@ -638,8 +651,6 @@ static struct symbol *evaluate_ptr_add(struct expression *expr, struct symbol *i
 
 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)
 {
@@ -812,6 +823,14 @@ static unsigned long target_qualifiers(struct symbol *type)
 	return mod;
 }
 
+static unsigned long cond_target_qualifiers(struct symbol *type)
+{
+	unsigned long mod = type->ctype.modifiers & (MOD_IGN | MOD_NODEREF | MOD_NOCAST);
+	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;
@@ -835,6 +854,10 @@ static struct symbol *evaluate_ptr_sub(struct expression *expr)
 		expression_error(expr, "subtraction of functions? Share your drugs");
 		return NULL;
 	}
+	if (!is_void_type(lbase) && lbase->bit_size < 0) {
+		expression_error(expr, "subtraction of pointers to incomplete type");
+		return NULL;
+	}
 
 	expr->ctype = ssize_t_ctype;
 	if (lbase->bit_size > bits_in_char) {
@@ -1222,7 +1245,7 @@ static struct symbol *evaluate_conditional_expression(struct expression *expr)
 		/* need to be lazier here */
 		lbase = examine_pointer_target(ltype);
 		rbase = examine_pointer_target(rtype);
-		qual = target_qualifiers(ltype) | target_qualifiers(rtype);
+		qual = cond_target_qualifiers(ltype) | cond_target_qualifiers(rtype);
 
 		if (lbase == &void_ctype) {
 			/* XXX: pointers to function should warn here */
@@ -1433,8 +1456,8 @@ static int check_assignment_types(struct symbol *target, struct expression **rp,
 		}
 		b1 = examine_pointer_target(t);
 		b2 = examine_pointer_target(s);
-		mod1 = t->ctype.modifiers & MOD_IGN;
-		mod2 = s->ctype.modifiers & MOD_IGN;
+		mod1 = t->ctype.modifiers & (MOD_IGN | MOD_NODEREF);
+		mod2 = s->ctype.modifiers & (MOD_IGN | MOD_NODEREF);
 		if (whitelist_pointers(b1, b2)) {
 			/*
 			 * assignments to/from void * are OK, provided that
@@ -2310,14 +2333,32 @@ static struct symbol *evaluate_ptrsizeof(struct expression *expr)
 	return size_t_ctype;
 }
 
+static bool is_incomplete_alignof_type(struct symbol *type, bool is_type)
+{
+	while (type && type->type == SYM_NODE)
+		type = type->ctype.base_type;
+	while (type && type->type == SYM_ARRAY) {
+		if (is_type && !type->array_size)
+			return true;
+		type = type->ctype.base_type;
+		while (type && type->type == SYM_NODE)
+			type = type->ctype.base_type;
+	}
+	return !type || (type->bit_size < 0 && type->type != SYM_FN);
+}
+
 static struct symbol *evaluate_alignof(struct expression *expr)
 {
 	struct symbol *type;
+	bool is_type = expr->cast_type != NULL;
 
 	type = evaluate_type_information(expr);
 	if (!type)
 		return NULL;
 
+	if (is_incomplete_alignof_type(type, is_type))
+		expression_error(expr, "cannot size alignment of incomplete type");
+
 	expr->type = EXPR_VALUE;
 	expr->value = type->ctype.alignment;
 	expr->taint = 0;
@@ -3268,7 +3309,11 @@ static struct symbol *evaluate_offsetof(struct expression *expr)
 			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);
+			int i_class;
+
+			if (!i_type)
+				return NULL;
+			i_class = classify_type(i_type, &i_type);
 
 			if (!is_int(i_class)) {
 				expression_error(expr, "non-integer index");
@@ -3316,7 +3361,8 @@ static void check_label_declaration(struct position pos, struct symbol *label)
 		sparse_error(pos, "label '%s' was not declared", show_ident(label->ident));
 		/* fallthrough */
 	case NS_NONE:
-		current_fn->bogus_linear = 1;
+		if (current_fn)
+			current_fn->bogus_linear = 1;
 	default:
 		break;
 	}
@@ -3337,10 +3383,14 @@ static struct symbol *evaluate_generic_selection(struct expression *expr)
 	struct symbol source;
 	struct symbol *ctrl;
 
-	if (!evaluate_expression(expr->control))
+	if (!evaluate_expression(expr->control)) {
+		expr->ctype = &bad_ctype;
 		return NULL;
-	if (!(ctrl = degenerate(expr->control)))
+	}
+	if (!(ctrl = degenerate(expr->control))) {
+		expr->ctype = &bad_ctype;
 		return NULL;
+	}
 
 	source = *ctrl;
 	source.ctype.modifiers &= ~(MOD_QUALIFIER|MOD_ATOMIC);
@@ -3352,18 +3402,31 @@ static struct symbol *evaluate_generic_selection(struct expression *expr)
 			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)
+		if (base && base->type == SYM_ARRAY) {
+			bool is_vla = false;
+			struct symbol *arr = base;
+			while (arr && arr->type == SYM_ARRAY) {
+				if (arr->array_size) {
+					get_expression_value_silent(arr->array_size);
+					if (arr->array_size->type != EXPR_VALUE) {
+						is_vla = true;
+						break;
+					}
+				}
+				arr = arr->ctype.base_type;
+				while (arr && arr->type == SYM_NODE)
+					arr = arr->ctype.base_type;
+			}
+			if (is_vla) {
+				sparse_error(stype->pos, "variable length array type in generic selection");
 				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)) {
+		if (stype->bit_size < 0 || is_void_type(stype)) {
 			sparse_error(stype->pos, "incomplete type in generic selection");
 			continue;
 		}
@@ -3376,6 +3439,7 @@ static struct symbol *evaluate_generic_selection(struct expression *expr)
 	res = expr->def;
 	if (!res) {
 		sparse_error(expr->pos, "no generic selection for '%s'", show_typename(ctrl));
+		expr->ctype = &bad_ctype;
 		return NULL;
 	}
 
@@ -3682,7 +3746,11 @@ static void parse_asm_constraint(struct asm_operand *op)
 			break;
 		case '[':
 			// FIXME: symbolic matching constraint
-			return;
+			while (*str && *str != ']')
+				str++;
+			if (*str == ']')
+				str++;
+			break;
 
 		default:
 			if (arch_target->asm_constraint)
diff --git a/parse.c b/parse.c
index ea90d088a244..2675a3976099 100644
--- a/parse.c
+++ b/parse.c
@@ -791,6 +791,8 @@ static struct token *struct_union_enum_specifier(enum type type,
 
 	token = parse(token->next, sym);
 	token = expect(token, '}', "at end of specifier");
+	sym->defined = 1;
+	sym->examined = 0;
 	attr.ctype.base_type = sym;
 	token = handle_attributes(token, &attr);
 	apply_ctype(token->pos, &sym->ctype, &attr.ctype);
diff --git a/symbol.c b/symbol.c
index abf3a198acc8..06cd8ca2ede7 100644
--- a/symbol.c
+++ b/symbol.c
@@ -215,6 +215,11 @@ static struct symbol * examine_struct_union_type(struct symbol *sym, int advance
 	void (*fn)(struct symbol *, struct struct_union_info *);
 	struct symbol *member;
 
+	if (!sym->defined) {
+		sym->bit_size = -1;
+		return sym;
+	}
+
 	fn = advance ? lay_out_struct : lay_out_union;
 	FOR_EACH_PTR(sym->symbol_list, member) {
 		if (member->ctype.base_type == &autotype_ctype) {
@@ -298,9 +303,10 @@ static struct symbol * examine_array_type(struct symbol *sym)
 	if (!base_type)
 		return sym;
 
-	if (array_size) {	
-		bit_size = array_element_offset(base_type->bit_size,
-						get_expression_value_silent(array_size));
+	if (array_size) {
+		unsigned long count = get_expression_value_silent(array_size);
+		if (base_type->bit_size >= 0)
+			bit_size = array_element_offset(base_type->bit_size, count);
 		if (array_size->type != EXPR_VALUE) {
 			if (Wvla)
 				warning(array_size->pos, "Variable length array is used.");
diff --git a/symbol.h b/symbol.h
index 9a8e58d5da28..a14686fe863b 100644
--- a/symbol.h
+++ b/symbol.h
@@ -149,7 +149,7 @@ struct symbol_op {
 struct symbol {
 	enum type type:8;
 	enum namespace namespace:9;
-	unsigned char used:1, attr:2, enum_member:1, bound:1;
+	unsigned char used:1, attr:2, enum_member:1, bound:1, defined:1;
 	struct position pos;		/* Where this symbol was declared */
 	struct position endpos;		/* Where this symbol ends*/
 	struct ident *ident;		/* What identifier this symbol is associated with */
diff --git a/validation/eval-type-checks.c b/validation/eval-type-checks.c
new file mode 100644
index 000000000000..13b3ff22210d
--- /dev/null
+++ b/validation/eval-type-checks.c
@@ -0,0 +1,89 @@
+#define __noderef __attribute__((noderef))
+#define __nocast __attribute__((nocast))
+
+struct empty {};
+struct inc;
+struct __attribute__((aligned(16))) inc_aligned;
+
+extern struct empty es;
+extern int ext_arr[];
+
+_Static_assert(_Generic(es, struct empty: 1, default: 0) == 1, "empty struct generic");
+_Static_assert(_Generic(0, int[4]: 1, default: 2) == 2, "fixed array assoc");
+_Static_assert(_Alignof(struct empty) == 1, "empty struct alignof");
+
+static unsigned long valid_alignof(int n)
+{
+	return _Alignof(int[n]) + _Alignof(void(void)) + __alignof__(ext_arr);
+}
+
+static void *valid_void_ptr_add(void *p)
+{
+	return p + 1;
+}
+
+static void test_incomplete_errors(struct inc *pi, int (*pa)[], int n)
+{
+	(void)(pi + 1);
+	(void)(pa + 1);
+	(void)_Alignof(void);
+	(void)_Alignof(int[]);
+	(void)_Alignof(struct inc);
+	(void)_Alignof(struct inc_aligned);
+	(void)_Alignof(struct inc[2]);
+	(void)_Generic(0, int[2][n]: 1, default: 0);
+	(void)_Generic(0, struct inc[2]: 1, default: 0);
+}
+
+static long test_qualifiers(int c, void *vp, void __nocast *vp_nc, int *p,
+			    int __noderef *p_nd, int __nocast *p_nc)
+{
+	void __nocast *ok_both_nc = c ? vp_nc : p_nc;
+	void __nocast *ok_one_nc = c ? vp : p_nc;
+	void __noderef *ok_nd = c ? vp : p_nd;
+	int *bad_nc = c ? vp_nc : p_nc;
+	int *bad_nd = c ? vp : p_nd;
+	long r = 0;
+
+	(void)ok_both_nc;
+	(void)ok_one_nc;
+	(void)ok_nd;
+	(void)bad_nc;
+	(void)bad_nd;
+
+	r += (p_nd == p);
+	r += (p_nd - p);
+	r += (p_nc == p);
+	r += (p_nc - p);
+	return r;
+}
+
+/*
+ * check-name: eval-type-checks
+ * check-command: sparse -Wno-vla $file
+ *
+ * check-error-start
+eval-type-checks.c:27:19: error: arithmetics on pointers to incomplete type
+eval-type-checks.c:28:19: error: arithmetics on pointers to incomplete type
+eval-type-checks.c:29:15: error: cannot size alignment of incomplete type
+eval-type-checks.c:30:15: error: cannot size alignment of incomplete type
+eval-type-checks.c:31:15: error: cannot size alignment of incomplete type
+eval-type-checks.c:32:15: error: cannot size alignment of incomplete type
+eval-type-checks.c:33:15: error: cannot size alignment of incomplete type
+eval-type-checks.c:34:27: error: variable length array type in generic selection
+eval-type-checks.c:35:27: error: incomplete type in generic selection
+eval-type-checks.c:42:40: warning: implicit cast to nocast type
+eval-type-checks.c:44:25: warning: implicit cast from nocast type
+eval-type-checks.c:45:25: warning: incorrect type in initializer (different modifiers)
+eval-type-checks.c:45:25:    expected int *bad_nd
+eval-type-checks.c:45:25:    got void [noderef] *
+eval-type-checks.c:54:20: error: incompatible types in comparison expression (different modifiers):
+eval-type-checks.c:54:20:    int [noderef] *
+eval-type-checks.c:54:20:    int *
+eval-type-checks.c:55:20: error: subtraction of different types can't work (different modifiers)
+eval-type-checks.c:56:20: error: incompatible types in comparison expression (different modifiers):
+eval-type-checks.c:56:20:    int [nocast] *
+eval-type-checks.c:56:20:    int *
+eval-type-checks.c:57:20: error: subtraction of different types can't work (different modifiers)
+ * check-error-end
+ */