[PATCH 49/73] c23: Support auto type inference

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

Add ISO C23 'auto' type inference when 'auto' appears without a type
specifier, while preserving 'auto' as a block-scope storage-class
specifier when combined with an explicit type:
- Infer the variable type from its assignment-expression initializer
  after array-to-pointer, function-to-pointer, and lvalue conversion so
  top-level qualifiers and _Atomic are stripped per C23 6.7.10p2.
- Bind C23 'auto' symbols before parsing their initializers and mark
  them underspecified during initializer parsing and evaluation so
  self-references are diagnosed per C23 6.2.1p7.
- Diagnose underspecified redeclarations in the same scope per C23
  6.7p12, braced initializers, typedefs, empty declarations, type names,
  parameters, struct/union members, and file-scope 'auto' specifiers.

Signed-off-by: Bart Van Assche <bvanassche@acm.org>
---
 evaluate.c                  |  14 +++-
 parse.c                     | 129 +++++++++++++++++++++++++++++++++---
 symbol.c                    |  59 ++++++++++++++++-
 symbol.h                    |   3 +
 validation/c23-auto-error.c |  68 +++++++++++++++++++
 validation/c23-auto.c       | 107 ++++++++++++++++++++++++++++++
 6 files changed, 365 insertions(+), 15 deletions(-)
 create mode 100644 validation/c23-auto-error.c
 create mode 100644 validation/c23-auto.c

diff --git a/evaluate.c b/evaluate.c
index c0d039105881..1b1a72577d18 100644
--- a/evaluate.c
+++ b/evaluate.c
@@ -87,6 +87,12 @@ static struct symbol *evaluate_symbol_expression(struct expression *expr)
 		expression_error(expr, "undefined identifier '%s'", show_ident(expr->symbol_name));
 		return NULL;
 	}
+	if (sym->underspecified) {
+		expression_error(expr,
+				 "underspecified symbol '%s' used in its own initializer",
+				 show_ident(sym->ident));
+		return NULL;
+	}
 
 	examine_symbol_type(sym);
 
@@ -3853,8 +3859,14 @@ static struct symbol *evaluate_symbol(struct symbol *sym)
 		return NULL;
 
 	/* Evaluate the initializers */
-	if (sym->initializer)
+	if (sym->initializer) {
+		bool mark_underspec = sym->c23_auto;
+		if (mark_underspec)
+			sym->underspecified = 1;
 		evaluate_initializer(sym, &sym->initializer);
+		if (mark_underspec)
+			sym->underspecified = 0;
+	}
 
 	/* And finally, evaluate the body of the symbol too */
 	if (base_type->type == SYM_FN) {
diff --git a/parse.c b/parse.c
index 1e91825f8d38..324da8e40423 100644
--- a/parse.c
+++ b/parse.c
@@ -57,7 +57,7 @@ static declarator_t
 	attribute_specifier, typeof_specifier, typeof_unqual_specifier,
 	storage_specifier, thread_specifier;
 static declarator_t generic_qualifier;
-static declarator_t autotype_specifier;
+static declarator_t autotype_specifier, auto_specifier;
 
 static struct token *parse_if_statement(struct token *token, struct statement *stmt);
 static struct token *parse_return_statement(struct token *token, struct statement *stmt);
@@ -143,7 +143,7 @@ static struct symbol_op alignas_op = {
 
 static struct symbol_op auto_op = {
 	.type = KW_MODIFIER,
-	.declarator = storage_specifier,
+	.declarator = auto_specifier,
 };
 
 static struct symbol_op register_op = {
@@ -472,7 +472,7 @@ static struct init_keyword {
 #define U(I, O,...)	N("__" I,O,##__VA_ARGS__),	\
 			N("__" I "__",O,##__VA_ARGS__)
 	/* Storage classes */
-	N("auto",		&auto_op,	.mods = MOD_AUTO),
+	N("auto",		&auto_op),
 	N("register",		&register_op,	.mods = MOD_REGISTER),
 	N("static",		&static_op,	.mods = MOD_STATIC),
 	N("extern",		&extern_op,	.mods = MOD_EXTERN),
@@ -1202,6 +1202,15 @@ static struct token *autotype_specifier(struct token *token, struct symbol *sym,
 	return token;
 }
 
+static struct token *auto_specifier(struct token *token, struct symbol *sym,
+				    struct decl_state *ctx)
+{
+	if (ctx->has_auto)
+		sparse_error(token->pos, "duplicate auto");
+	ctx->has_auto = 1;
+	return token;
+}
+
 static struct token *ignore_attribute(struct token *token, struct symbol *attr, struct decl_state *ctx)
 {
 	struct expression *expr = NULL;
@@ -1732,6 +1741,23 @@ static struct token *declaration_specifiers(struct token *token, struct decl_sta
 		}
 	}
 
+	if (ctx->has_auto) {
+		if (seen & (Set_S | Set_Any)) {
+			if (ctx->storage_class)
+				sparse_error(token->pos,
+					     "multiple storage classes");
+			else
+				ctx->storage_class = MOD_AUTO;
+		} else {
+			if (standard < STANDARD_C23 && Wpedantic)
+				warning(token->pos,
+					"'auto' type inference is a C23 feature");
+			ctx->ctype.base_type = &autotype_ctype;
+			ctx->autotype = 1;
+			seen |= Set_S;
+		}
+	}
+
 	if (!(seen & Set_S)) {	/* not set explicitly? */
 		struct symbol *base = &incomplete_ctype;
 		if (seen & Set_Any)
@@ -2085,6 +2111,14 @@ static struct token *declaration_list(struct token *token, struct symbol_list **
 		decl->ctype.modifiers |= mod;
 		decl->cleanup = ctx.cleanup;
 		decl->endpos = token->pos;
+		if (ctx.has_auto) {
+			sparse_error(
+				decl->pos,
+				"struct or union member '%s' cannot be declared auto",
+				show_ident(decl->ident));
+			if (ctx.autotype)
+				decl->ctype.base_type = &bad_ctype;
+		}
 		if (decl->ctype.modifiers & MOD_TLS)
 			sparse_error(
 				decl->pos,
@@ -2136,6 +2170,14 @@ static struct token *parameter_declaration(struct token *token, struct symbol *s
 		sparse_error(sym->pos,
 			     "alignment specified for parameter '%s'",
 			     show_ident(sym->ident));
+	if (ctx.has_auto || ctx.autotype) {
+		sparse_error(sym->pos,
+			     "parameter '%s' cannot be declared %s",
+			     show_ident(sym->ident),
+			     ctx.has_auto ? "auto" : "__auto_type");
+		if (ctx.autotype)
+			sym->ctype.base_type = &bad_ctype;
+	}
 	if (sym->ctype.modifiers & MOD_TLS)
 		sparse_error(sym->pos,
 			     "parameter '%s' cannot be thread-local",
@@ -2152,6 +2194,11 @@ struct token *typename(struct token *token, struct symbol **p, int *forced)
 	token = declaration_specifiers(token, &ctx);
 	if (ctx.has_alignas)
 		sparse_error(sym->pos, "alignment specified for type name");
+	if (ctx.autotype) {
+		sparse_error(sym->pos, "'%s' in type name",
+			     ctx.has_auto ? "auto" : "__auto_type");
+		ctx.ctype.base_type = &bad_ctype;
+	}
 	token = declarator(token, &ctx);
 	apply_modifiers(token->pos, &ctx);
 	sym->ctype = ctx.ctype;
@@ -3199,6 +3246,7 @@ struct token *external_declaration(struct token *token, struct symbol_list **lis
 	struct symbol *base_type;
 	unsigned long mod;
 	int is_typedef;
+	bool delay_bind = false;
 
 	/* Top-level inline asm or static assertion? */
 	if (token_type(token) == TOKEN_IDENT) {
@@ -3213,6 +3261,9 @@ struct token *external_declaration(struct token *token, struct symbol_list **lis
 	decl = alloc_symbol(token->pos, SYM_NODE);
 	/* Just a type declaration? */
 	if (match_op(token, ';')) {
+		if (ctx.autotype)
+			sparse_error(token->pos, "%s in empty declaration",
+				     ctx.has_auto ? "auto" : "__auto_type");
 		apply_modifiers(token->pos, &ctx);
 		return token->next;
 	}
@@ -3226,6 +3277,7 @@ struct token *external_declaration(struct token *token, struct symbol_list **lis
 	decl->ctype = ctx.ctype;
 	decl->ctype.modifiers |= mod;
 	decl->cleanup = ctx.cleanup;
+	decl->c23_auto = ctx.autotype && ctx.has_auto;
 	decl->endpos = token->pos;
 
 	/* Just a type declaration? */
@@ -3241,9 +3293,15 @@ struct token *external_declaration(struct token *token, struct symbol_list **lis
 	if (is_typedef)
 		decl->ctype.modifiers |= MOD_USERTYPE;
 
-	bind_symbol(decl, ident, is_typedef ? NS_TYPEDEF: NS_SYMBOL);
-
 	base_type = decl->ctype.base_type;
+	if (!is_typedef && ctx.autotype && !ctx.has_auto &&
+	    base_type == &autotype_ctype) {
+		struct symbol *prev = lookup_symbol(ident, NS_SYMBOL | NS_TYPEDEF);
+		if (prev && is_outer_scope(prev->scope))
+			delay_bind = true;
+	}
+	if (!delay_bind)
+		bind_symbol(decl, ident, is_typedef ? NS_TYPEDEF: NS_SYMBOL);
 
 	if (is_typedef) {
 		if (base_type && !base_type->ident) {
@@ -3260,8 +3318,9 @@ struct token *external_declaration(struct token *token, struct symbol_list **lis
 		}
 	} else if (base_type && base_type->type == SYM_FN) {
 		if (base_type->ctype.base_type == &autotype_ctype) {
-			sparse_error(decl->pos, "'%s()' has __auto_type return type",
-				show_ident(decl->ident));
+			sparse_error(decl->pos, "'%s()' has %s return type",
+				     show_ident(decl->ident),
+				     ctx.has_auto ? "auto" : "__auto_type");
 			base_type->ctype.base_type = &int_ctype;
 		}
 		if (base_type->ctype.base_type == &incomplete_ctype) {
@@ -3301,11 +3360,26 @@ struct token *external_declaration(struct token *token, struct symbol_list **lis
 	for (;;) {
 		if (!is_typedef && match_op(token, '=')) {
 			struct token *next = token->next;
+			bool mark_underspec = decl->c23_auto;
+			if (mark_underspec)
+				decl->underspecified = 1;
 			token = initializer(&decl->initializer, next);
+			if (mark_underspec)
+				decl->underspecified = 0;
 			if (token == next)
 				sparse_error(token->pos, "expression expected before '%s'", show_token(token));
 		}
+		if (delay_bind) {
+			bind_symbol(decl, ident, is_typedef ? NS_TYPEDEF : NS_SYMBOL);
+			delay_bind = false;
+		}
 		if (!is_typedef) {
+			if (!ctx.autotype && (ctx.storage_class & MOD_AUTO) &&
+			    toplevel(block_scope))
+				sparse_error(
+					decl->pos,
+					"file-scope declaration of '%s' specifies 'auto'",
+					show_ident(decl->ident));
 			if (validate_decl)
 				validate_decl(decl);
 
@@ -3329,19 +3403,51 @@ struct token *external_declaration(struct token *token, struct symbol_list **lis
 			}
 		}
 
+		if (!is_typedef && decl->c23_auto &&
+		    (!decl->ctype.base_type ||
+		     decl->ctype.base_type->type != SYM_FN)) {
+			struct symbol *prev;
+			for (prev = decl->next_id; prev; prev = prev->next_id) {
+				if (prev->namespace != decl->namespace ||
+				    prev->builtin)
+					continue;
+				if (prev->scope == decl->scope ||
+				    (toplevel(decl->scope) &&
+				     toplevel(prev->scope))) {
+					sparse_error(
+						decl->pos,
+						"underspecified declaration of '%s', which is already declared in this scope",
+						show_ident(decl->ident));
+					break;
+				}
+			}
+		}
+
 		if (ctx.autotype) {
 			const char *msg = NULL;
-			if (decl->ctype.base_type != &autotype_ctype)
+			struct expression *init = decl->initializer;
+			while (init && init->type == EXPR_PREOP && init->op == '(')
+				init = init->unop;
+			if (is_typedef)
+				msg = "cannot be used with typedef";
+			else if (decl->ctype.base_type != &autotype_ctype)
 				msg = "on non-identifier";
 			else if (match_op(token, ','))
 				msg = "on declaration list";
 			else if (!decl->initializer)
 				msg = "without initializer";
-			else if (decl->initializer->type == EXPR_SYMBOL &&
-				 decl->initializer->symbol == decl)
+			else if (decl->initializer->type == EXPR_INITIALIZER) {
+				msg = "requires a scalar initializer expression";
+				decl->initializer = NULL;
+			} else if (!ctx.has_auto && init &&
+				   init->type == EXPR_SYMBOL &&
+				   init->symbol == decl)
 				msg = "on self-init var";
 			if (msg) {
-				sparse_error(decl->pos, "__auto_type %s", msg);
+				sparse_error(decl->pos, "%s %s",
+					     ctx.has_auto ? "auto" :
+							    "__auto_type",
+					     msg);
 				decl->ctype.base_type = &bad_ctype;
 			}
 		}
@@ -3391,6 +3497,7 @@ struct token *external_declaration(struct token *token, struct symbol_list **lis
 		decl->ctype = ctx.ctype;
 		decl->ctype.modifiers |= mod;
 		decl->cleanup = ctx.cleanup;
+		decl->c23_auto = ctx.autotype && ctx.has_auto;
 		decl->endpos = token->pos;
 		if (!ident) {
 			sparse_error(token->pos, "expected identifier name in type definition");
diff --git a/symbol.c b/symbol.c
index a05e240cdfaa..b0bdf0b1122f 100644
--- a/symbol.c
+++ b/symbol.c
@@ -266,15 +266,68 @@ static struct symbol *examine_base_type(struct symbol *sym)
 	struct symbol *base_type;
 
 	if (sym->ctype.base_type == &autotype_ctype) {
-		struct symbol *type = evaluate_expression(sym->initializer);
-		if (!type)
+		struct symbol *type;
+		sym->ctype.base_type = &bad_ctype;
+		if (!sym->initializer || sym->initializer->type == EXPR_INITIALIZER) {
+			type = &bad_ctype;
+		} else {
+			if (sym->c23_auto)
+				sym->underspecified = 1;
+			type = evaluate_expression(sym->initializer);
+			if (sym->c23_auto)
+				sym->underspecified = 0;
+		}
+		if (!type || type == sym || type->ctype.base_type == &autotype_ctype)
 			type = &bad_ctype;
 		if (is_bitfield_type(type)) {
-			warning(sym->pos, "__auto_type on bitfield");
+			if (!sym->c23_auto)
+				warning(sym->pos, "__auto_type on bitfield");
 			if (type->type == SYM_NODE)
 				type = type->ctype.base_type;
 			type = type->ctype.base_type;
 		}
+		if (type->type == SYM_NODE &&
+		    type->ctype.base_type->type == SYM_ARRAY) {
+			struct symbol *array = type->ctype.base_type;
+			struct symbol *ptr = alloc_symbol(sym->pos, SYM_PTR);
+			ptr->ctype.base_type = array->ctype.base_type;
+			combine_address_space(sym->pos, &ptr->ctype.as, type->ctype.as);
+			combine_address_space(sym->pos, &ptr->ctype.as, array->ctype.as);
+			ptr->ctype.modifiers |= (type->ctype.modifiers | array->ctype.modifiers) & MOD_PTRINHERIT;
+			ptr->bit_size = bits_in_pointer;
+			ptr->ctype.alignment = pointer_alignment;
+			type = ptr;
+		} else if (type->type == SYM_ARRAY) {
+			struct symbol *ptr = alloc_symbol(sym->pos, SYM_PTR);
+			ptr->ctype.base_type = type->ctype.base_type;
+			combine_address_space(sym->pos, &ptr->ctype.as, type->ctype.as);
+			ptr->ctype.modifiers |= type->ctype.modifiers & MOD_PTRINHERIT;
+			ptr->bit_size = bits_in_pointer;
+			ptr->ctype.alignment = pointer_alignment;
+			type = ptr;
+		} else if (type->type == SYM_NODE &&
+			   type->ctype.base_type->type == SYM_FN) {
+			struct symbol *ptr = alloc_symbol(sym->pos, SYM_PTR);
+			ptr->ctype.base_type = type->ctype.base_type;
+			ptr->bit_size = bits_in_pointer;
+			ptr->ctype.alignment = pointer_alignment;
+			type = ptr;
+		} else if (type->type == SYM_FN) {
+			struct symbol *ptr = alloc_symbol(sym->pos, SYM_PTR);
+			ptr->ctype.base_type = type;
+			ptr->bit_size = bits_in_pointer;
+			ptr->ctype.alignment = pointer_alignment;
+			type = ptr;
+		} else if (sym->c23_auto) {
+			/*
+			 * C23 6.7.10p2: inferred type is the type of the
+			 * assignment expression after lvalue, array-to-pointer,
+			 * or function-to-pointer conversion (stripping top-level
+			 * qualifiers and atomic).
+			 */
+			while (type->type == SYM_NODE)
+				type = type->ctype.base_type;
+		}
 		sym->ctype.base_type = type;
 	}
 
diff --git a/symbol.h b/symbol.h
index acd381fe64fd..61ca70afe83b 100644
--- a/symbol.h
+++ b/symbol.h
@@ -115,6 +115,7 @@ struct decl_state {
 	unsigned char autotype;
 	unsigned char forced;
 	unsigned char packed;
+	unsigned char has_auto;
 	unsigned char has_alignas;
 	unsigned char designated_init;
 	unsigned char transparent_union;
@@ -201,6 +202,8 @@ struct symbol {
 					packed:1,
 					transparent_union:1;
 			unsigned int has_alignas : 1;
+			unsigned int underspecified : 1;
+			unsigned int c23_auto : 1;
 			int		rank:3;	// arithmetic's rank
 			struct expression *array_size;
 			struct ctype ctype;
diff --git a/validation/c23-auto-error.c b/validation/c23-auto-error.c
new file mode 100644
index 000000000000..b88ebd37d2d9
--- /dev/null
+++ b/validation/c23-auto-error.c
@@ -0,0 +1,68 @@
+auto no_init;
+auto arr[2] = { 0, 1 };
+auto foo(void)
+{
+}
+auto x = 1, y = 2;
+auto self = self;
+auto auto dup = 1;
+auto self_expr = self_expr + 1;
+auto self_sz = sizeof(self_sz);
+struct bad_s {
+	auto m;
+};
+void bad_param(auto p);
+typedef auto bad_td;
+auto;
+auto int bad_file_storage = 1;
+extern int already_in_scope;
+auto already_in_scope = 1;
+
+void block_errors(void)
+{
+	int shadow = 5;
+	{
+		auto shadow = shadow + 1;
+	}
+	int bad_sz = sizeof(auto);
+	int bad_cast = (auto)1;
+	_Atomic(auto) bad_atomic = 1;
+	auto braced = { 1 };
+	(void)bad_sz;
+	(void)bad_cast;
+	(void)bad_atomic;
+	(void)braced;
+}
+
+/*
+ * check-name: C23 auto error cases
+ * check-command: sparse -std=c23 $file
+ *
+ * check-error-start
+c23-auto-error.c:1:6: error: auto without initializer
+c23-auto-error.c:2:6: error: auto on non-identifier
+c23-auto-error.c:3:6: error: 'foo()' has auto return type
+c23-auto-error.c:6:6: error: auto on declaration list
+c23-auto-error.c:8:11: error: duplicate auto
+c23-auto-error.c:12:14: error: struct or union member 'm' cannot be declared auto
+c23-auto-error.c:14:16: error: parameter 'p' cannot be declared auto
+c23-auto-error.c:15:14: error: auto cannot be used with typedef
+c23-auto-error.c:16:5: error: auto in empty declaration
+c23-auto-error.c:17:10: error: file-scope declaration of 'bad_file_storage' specifies 'auto'
+c23-auto-error.c:19:6: error: underspecified declaration of 'already_in_scope', which is already declared in this scope
+c23-auto-error.c:27:29: error: 'auto' in type name
+c23-auto-error.c:28:25: error: 'auto' in type name
+c23-auto-error.c:29:16: error: Trying to use reserved word 'auto' as identifier
+c23-auto-error.c:29:23: error: Expected ; at end of declaration
+c23-auto-error.c:29:23: error: got bad_atomic
+c23-auto-error.c:30:14: error: auto requires a scalar initializer expression
+c23-auto-error.c:2:15: error: invalid initializer
+c23-auto-error.c:7:13: error: underspecified symbol 'self' used in its own initializer
+c23-auto-error.c:9:18: error: underspecified symbol 'self_expr' used in its own initializer
+c23-auto-error.c:10:23: error: underspecified symbol 'self_sz' used in its own initializer
+c23-auto-error.c:10:16: error: cannot size expression
+c23-auto-error.c:25:31: error: underspecified symbol 'shadow' used in its own initializer
+c23-auto-error.c:27:22: error: cannot size expression
+c23-auto-error.c:33:15: error: undefined identifier 'bad_atomic'
+ * check-error-end
+ */
diff --git a/validation/c23-auto.c b/validation/c23-auto.c
new file mode 100644
index 000000000000..f9c461d9bed7
--- /dev/null
+++ b/validation/c23-auto.c
@@ -0,0 +1,107 @@
+#ifdef __CHECKER__
+#define ASSERT_TYPE(expr, T) _Static_assert([typeof(expr)] == [T], "")
+#else
+#define ASSERT_TYPE(expr, T) \
+	_Static_assert(_Generic((typeof(expr) *)0, typeof(T) *: 1, default: 0), "")
+#endif
+
+struct s {
+	int a;
+};
+static void fn(void)
+{
+}
+
+static auto file_static = 42L;
+ASSERT_TYPE(file_static, long);
+
+static void test(void)
+{
+	auto i = 0;
+	ASSERT_TYPE(i, int);
+
+	auto l = 1L;
+	ASSERT_TYPE(l, long);
+
+	auto d = 1.0;
+	ASSERT_TYPE(d, double);
+
+	auto f = 1.0f;
+	ASSERT_TYPE(f, float);
+
+	auto p = &i;
+	ASSERT_TYPE(p, int *);
+
+	const auto ci = 42;
+	ASSERT_TYPE(ci, const int);
+
+	volatile auto vi = 1;
+	ASSERT_TYPE(vi, volatile int);
+
+	_Atomic auto ai = 2;
+	ASSERT_TYPE(ai, _Atomic int);
+
+	/* Top-level qualifiers and _Atomic are stripped by lvalue conversion */
+	auto stripped_c = ci;
+	ASSERT_TYPE(stripped_c, int);
+	stripped_c = 43;
+
+	auto stripped_v = vi;
+	ASSERT_TYPE(stripped_v, int);
+	stripped_v = 2;
+
+	auto stripped_a = ai;
+	ASSERT_TYPE(stripped_a, int);
+	stripped_a = 3;
+
+	/* Pointee qualifiers and decayed array element qualifiers are kept */
+	const int *cp = &ci;
+	auto p_to_const = cp;
+	ASSERT_TYPE(p_to_const, const int *);
+
+	int *const top_const_p = &i;
+	auto stripped_p = top_const_p;
+	ASSERT_TYPE(stripped_p, int *);
+	stripped_p = nullptr;
+
+	const int carr[2] = { 1, 2 };
+	auto decayed_carr = carr;
+	ASSERT_TYPE(decayed_carr, const int *);
+
+	static auto si = 100;
+	ASSERT_TYPE(si, int);
+
+	auto s = "hello";
+	ASSERT_TYPE(s, char *);
+
+	int arr[10];
+	auto a = arr;
+	ASSERT_TYPE(a, int *);
+
+	auto fp = fn;
+	ASSERT_TYPE(fp, void (*)(void));
+
+	struct s st = { 1 };
+	auto sv = st;
+	ASSERT_TYPE(sv, struct s);
+
+	const struct s cst = { 2 };
+	auto stripped_st = cst;
+	ASSERT_TYPE(stripped_st, struct s);
+	stripped_st.a = 3;
+
+	auto int normal = 1;
+	ASSERT_TYPE(normal, int);
+
+	int auto normal2 = 2;
+	ASSERT_TYPE(normal2, int);
+
+	for (auto idx = 0; idx < 1; idx++) {
+		ASSERT_TYPE(idx, int);
+	}
+}
+
+/*
+ * check-name: C23 auto type inference
+ * check-command: sparse -std=c23 $file
+ */