harec

commit a812b9f9a38b9e7c059bfdbd8f880cec239b2393
parent 316f8fafd95b469416ec394ee4fec2d91ed32ce0
Author: Eyal Sawady <ecs@d2evs.net>
Date:   Sat, 19 Jun 2021 18:41:04 +0000

Implement tagged union reduction

And use it for if/match/switch result types

Signed-off-by: Eyal Sawady <ecs@d2evs.net>

Diffstat:
M
include/type_store.h
 | 
4
++++
M
src/check.c
 | 
29
++++++++++++++++++++---------
M
src/type_store.c
 | 
86
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

3 files changed, 110 insertions(+), 9 deletions(-)
diff --git a/include/type_store.h b/include/type_store.h
@@ -17,6 +17,10 @@ struct type_store {
 	struct context *check_context;
 };
 
+// Applies the type reduction algorithm to the given tagged union.
+const struct type *type_store_reduce_tagged(struct type_store *store,
+		struct type_tagged_union *in);
+
 struct ast_type;
 
 const struct type *type_store_lookup_atype(
diff --git a/src/check.c b/src/check.c
@@ -1574,18 +1574,17 @@ check_expr_if(struct context *ctx,
 		errors = check_expression(ctx, aexpr->_if.false_branch,
 			false_branch, hint, errors);
 
-		if (true_branch->terminates && false_branch->terminates) {
+		bool tt = true_branch->terminates, ft = false_branch->terminates;
+		if (tt && ft) {
 			expr->terminates = true;
 			expr->result = &builtin_type_void;
-		} else if (true_branch->terminates) {
-			expr->result = false_branch->result;
-		} else if (false_branch->terminates) {
+		} else if (!tt && ft) {
 			expr->result = true_branch->result;
+		} else if (tt && !ft) {
+			expr->result = false_branch->result;
 		} else if (hint && type_is_assignable(hint, true_branch->result)
 				&& type_is_assignable(hint, false_branch->result)) {
 			expr->result = hint;
-		} else if (true_branch->result == false_branch->result) {
-			expr->result = true_branch->result;
 		} else {
 			struct type_tagged_union _tags = {
 				.type = false_branch->result,
@@ -1595,7 +1594,11 @@ check_expr_if(struct context *ctx,
 				.next = &_tags,
 			};
 			expr->result =
-				type_store_lookup_tagged(ctx->store, &tags);
+				type_store_reduce_tagged(ctx->store, &tags);
+			if (expr->result == NULL) {
+				return error(aexpr->loc, expr, errors,
+					"Invalid result type (dangling or ambiguous null)");
+			}
 		}
 		true_branch = lower_implicit_cast(expr->result, true_branch);
 		false_branch = lower_implicit_cast(expr->result, false_branch);
@@ -1815,8 +1818,12 @@ check_expr_match(struct context *ctx,
 		if (hint) {
 			expr->result = hint;
 		} else {
-			expr->result = type_store_lookup_tagged(
+			expr->result = type_store_reduce_tagged(
 				ctx->store, &result_type);
+			if (expr->result == NULL) {
+				return error(aexpr->loc, expr, errors,
+					"Invalid result type (dangling or ambiguous null)");
+			}
 		}
 
 		struct match_case *_case = expr->match.cases;
@@ -2354,8 +2361,12 @@ check_expr_switch(struct context *ctx,
 		if (hint) {
 			expr->result = hint;
 		} else {
-			expr->result = type_store_lookup_tagged(
+			expr->result = type_store_reduce_tagged(
 				ctx->store, &result_type);
+			if (expr->result == NULL) {
+				return error(aexpr->loc, expr, errors,
+					"Invalid result type (dangling or ambiguous null)");
+			}
 		}
 
 		struct switch_case *_case = expr->_switch.cases;
diff --git a/src/type_store.c b/src/type_store.c
@@ -862,3 +862,89 @@ type_store_lookup_tuple(struct type_store *store, struct type_tuple *values)
 	}
 	return type_store_lookup_type(store, &type);
 }
+
+// Algorithm:
+// - Deduplicate and collect nested unions
+// - Merge *type with nullable *type
+// - If one of the types is null:
+// 	- If there's more than one pointer type, error out
+// 	- If there's one pointer type, make it nullable and drop the null
+// 	- If there are no pointer types, keep the null
+// - If the resulting union only has one type, return that type
+// - Otherwise, return a tagged union of all the selected types
+const struct type *
+type_store_reduce_tagged(struct type_store *store, struct type_tagged_union *in)
+{
+	if (!in) {
+		return &builtin_type_void;
+	}
+
+	const struct type *type = type_store_lookup_tagged(store, in);
+	struct type_tagged_union _in = type->tagged;
+	in = &_in;
+
+	struct type_tagged_union **null = NULL;
+	struct type_tagged_union *ptr = NULL;
+	bool multiple_ptrs = false;
+	struct type_tagged_union **tu = ∈
+	while (*tu != NULL) {
+		struct type_tagged_union *i = *tu;
+		bool dropped = false;
+		const struct type *it = i->type;
+		for (struct type_tagged_union *j = in; j != i; j = j->next) {
+			const struct type *jt = j->type;
+			assert(it->id != jt->id);
+			if (it->storage != STORAGE_POINTER
+					|| jt->storage != STORAGE_POINTER) {
+				break;
+			}
+			if (it->pointer.referent->id != jt->pointer.referent->id) {
+				break;
+			}
+			if (it->flags != jt->flags) {
+				break;
+			}
+			if ((it->pointer.flags & PTR_NULLABLE)
+					|| (jt->pointer.flags & PTR_NULLABLE)) {
+				it = type_store_lookup_pointer(store,
+					it->pointer.referent, PTR_NULLABLE);
+				jt = type_store_lookup_pointer(store,
+					jt->pointer.referent, PTR_NULLABLE);
+				if (it == jt) {
+					dropped = true;
+					*tu = i->next;
+					j->type = jt;
+					break;
+				}
+			};
+		}
+
+		if (i->type->storage == STORAGE_NULL) {
+			null = tu;
+		}
+		if (!dropped) {
+			if (i->type->storage == STORAGE_POINTER) {
+				if (ptr != NULL) {
+					multiple_ptrs = true;
+				}
+				ptr = i;
+			}
+			tu = &i->next;
+		}
+	}
+
+	if (null != NULL && (multiple_ptrs || ptr == NULL)) {
+		return NULL;
+	}
+
+	if (null != NULL && ptr != NULL) {
+		*null = (*null)->next;
+		ptr->type = type_store_lookup_pointer(store,
+			ptr->type->pointer.referent, PTR_NULLABLE);
+	}
+
+	if (in->next == NULL) {
+		return in->type;
+	}
+	return type_store_lookup_tagged(store, in);
+}