shithub: mc

Download patch

ref: a8a5638f3cd024f627ce3fd64aac94fd8fcf9e6f
parent: c57f6ab5442e2be1500b5e8e280de537eced19d7
author: Ori Bernstein <ori@eigenstate.org>
date: Sat Jun 24 08:25:08 EDT 2017 

Fix occurs check.

	If we had a cycle within a type, the occurs check would
	recurse infinitely:

		a -> b -> c -> b

	would never return, because `a` doesn't occur in that
	sequence.


--- a/parse/infer.c
+++ b/parse/infer.c
@@ -281,43 +281,63 @@
  * Recursive types that contain themselves through
  * pointers or slices are fine, but any other self-inclusion
  * would lead to a value of infinite size */
-static int occurs(Inferstate *st, Type *t, Type *sub)
+static int occurs_rec(Inferstate *st, Type *sub, Bitset *bs)
 {
 	size_t i;
 
-	assert(t != NULL);
-	if (t == sub) /* FIXME: is this actually right? */
+	if (bshas(bs, sub->tid))
 		return 1;
-	/* if we're on the first iteration, the subtype is the type
-	 * itself. The assignment must come after the equality check
-	 * for obvious reasons. */
-	if (!sub)
-		sub = t;
-
+	bsput(bs, sub->tid);
 	switch (sub->type) {
+	case Typtr:
+	case Tyslice: 
+		break;
 	case Tystruct:
 		for (i = 0; i < sub->nmemb; i++)
-			if (occurs(st, t, decltype(sub->sdecls[i])))
+			if (occurs_rec(st, decltype(sub->sdecls[i]), bs))
 				return 1;
 		break;
 	case Tyunion:
 		for (i = 0; i < sub->nmemb; i++) {
-			if (sub->udecls[i]->etype && occurs(st, t, sub->udecls[i]->etype))
+			if (!sub->udecls[i]->etype)
+				continue;
+			if (occurs_rec(st, sub->udecls[i]->etype, bs))
 				return 1;
 		}
 		break;
-	case Typtr:
-	case Tyslice: 
-		return 0;
 	default:
 		for (i = 0; i < sub->nsub; i++)
-			if (occurs(st, t, sub->sub[i]))
+			if (occurs_rec(st, sub->sub[i], bs))
 				return 1;
 		break;
 	}
+	bsdel(bs, sub->tid);
 	return 0;
 }
 
+static int occursin(Inferstate *st, Type *a, Type *b)
+{
+	Bitset *bs;
+	int r;
+
+	bs = mkbs();
+	bsput(bs, b->tid);
+	r = occurs_rec(st, a, bs);
+	bsfree(bs);
+	return r;
+}
+
+static int occurs(Inferstate *st, Type *t)
+{
+	Bitset *bs;
+	int r;
+
+	bs = mkbs();
+	r = occurs_rec(st, t, bs);
+	bsfree(bs);
+	return r;
+}
+
 static int needfreshenrec(Inferstate *st, Type *t, Bitset *visited)
 {
 	size_t i;
@@ -446,7 +466,7 @@
 		bsunion(t->traits, base->traits);
 	else if (base->traits)
 		t->traits = bsdup(base->traits);
-	if (occurs(st, t, NULL))
+	if (occurs(st, t))
 		lfatal(t->loc, "type %s includes itself", tystr(t));
 	st->ingeneric--;
 	if (t->type == Tyname || t->type == Tygeneric) {
@@ -973,7 +993,7 @@
 
 	/* Disallow recursive types */
 	if (a->type == Tyvar && b->type != Tyvar) {
-		if (occurs(st, a, b))
+		if (occursin(st, a, b))
 			fatal(ctx, "%s occurs within %s, leading to infinite type near %s\n",
 				tystr(a), tystr(b), ctxstr(st, ctx));
 	}