ref: a1774754e1da0397cc2cf567ca2ce6e79ae57bf7
parent: 43a9a671c7bf82d6de25ee6f0509a8c62cf23e6e
author: Ori Bernstein <[email protected]>
date: Fri Jul 20 12:46:05 EDT 2012
x
Add occurs check for types.
We don't want infinite types.
--- a/parse/infer.c
+++ b/parse/infer.c
@@ -100,6 +100,44 @@
return t;
}
+static int tyoccurs(Inferstate *st, Type *t, Type *sub)
+{+ size_t i;
+
+ assert(t != NULL);
+ if (t == sub) /* FIXME: is this actually right? */
+ 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;
+
+ switch (sub->type) {+ case Tystruct:
+ for (i = 0; i < sub->nmemb; i++)
+ if (tyoccurs(st, t, decltype(sub->sdecls[i])))
+ return 1;
+ break;
+ case Tyunion:
+ for (i = 0; i < t->nmemb; i++) {+ if (sub->udecls[i]->etype && tyoccurs(st, t, sub->udecls[i]->etype))
+ return 1;
+ }
+ break;
+
+ case Typtr:
+ case Tyslice:
+ return 0;
+ default:
+ for (i = 0; i < sub->nsub; i++)
+ if (tyoccurs(st, t, sub->sub[i]))
+ return 1;
+ break;
+ }
+ return 0;
+}
+
static void tyresolve(Inferstate *st, Type *t)
{size_t i;
@@ -132,6 +170,8 @@
bsunion(t->cstrs, base->cstrs);
else
t->cstrs = bsdup(base->cstrs);
+ if (tyoccurs(st, t, NULL))
+ fatal(t->line, "Type %s includes itself", tystr(t));
}
/* fixd the most accurate type mapping we have */
@@ -790,11 +830,12 @@
return tyint;
if (hascstr(t, cstrtab[Tcfloat]) && cstrcheck(t, tyflt))
return tyint;
- } else {+ } else if (!t->fixed) {+ t->fixed = 1;
if (t->type == Tyarray) {typesub(st, t->asize);
} else if (t->type == Tystruct) {- for (i = 0; i < t->nmemb && t->visits < st->subpass; i++)
+ for (i = 0; i < t->nmemb; i++)
typesub(st, t->sdecls[i]);
} else if (t->type == Tyunion) { for (i = 0; i < t->nmemb; i++) {--- a/parse/parse.h
+++ b/parse/parse.h
@@ -92,7 +92,8 @@
Ty type;
int tid;
int line;
- int resolved; /* Have we resolved the subtypes? Idempotent, but slow to repeat. */
+ int resolved; /* Have we resolved the subtypes? Prevents infinite recursion. */
+ int fixed; /* Have we fixed the subtypes? Prevents infinite recursion. */
Bitset *cstrs; /* the type constraints matched on this type */
Node **cstrlist; /* The names of the constraints on the type. Used to resolve/fill the bitset */
size_t ncstrlist; /* The length of the constraint list above */
--- a/parse/type.c
+++ b/parse/type.c
@@ -320,7 +320,7 @@
p = buf;
end = p + len;
- p += snprintf(p, end - p, "struct ");
+ p += snprintf(p, end - p, "union ");
for (i = 0; i < t->nmemb; i++) {name = namestr(t->udecls[i]->name);
ty = tystr(t->udecls[i]->etype);
--- a/test/tests
+++ b/test/tests
@@ -53,6 +53,7 @@
B arraylit-ni E 2
B structlit E 42
B tuple E 42
+B tyrec E 42
F declmismatch
F infermismatch
F flow
--- /dev/null
+++ b/test/tyrec.myr
@@ -1,0 +1,9 @@
+/* we just want to see if this file compiles */
+type foo = struct
+ v : foo*
+;;
+
+const main = {+ var v : foo
+ -> 42
+}