summaryrefslogtreecommitdiff
path: root/mi/match.c
diff options
context:
space:
mode:
Diffstat (limited to 'mi/match.c')
-rw-r--r--mi/match.c175
1 files changed, 167 insertions, 8 deletions
diff --git a/mi/match.c b/mi/match.c
index bdc4c02..756bd4b 100644
--- a/mi/match.c
+++ b/mi/match.c
@@ -16,11 +16,12 @@
typedef struct Dtree Dtree;
struct Dtree {
/* If the values are equal, go to 'sub'. If 'val' is null, anything matches. */
- Node **val; /* values to compare against */
+ Node *patexpr; /* the full pattern for this node */
+ Node **val; /* pattern values to compare against */
size_t nval;
- Node **load; /* values being loaded */
+ Node **load; /* expression value being compared */
size_t nload;
- Dtree **sub; /* submatches for an equal comparison */
+ Dtree **sub; /* submatche to use if if equal */
size_t nsub;
Dtree *any; /* tree for a wildcard match. */
@@ -29,13 +30,67 @@ struct Dtree {
size_t ncap;
Node *act;
+ int id;
};
static Dtree *addpat(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap);
+static size_t nconstructors(Type *t)
+{
+ if (!t)
+ return 0;
+ t = tybase(t);
+ switch (t->type) {
+ case Tyvoid: return 0; break;
+
+ case Tybool: return 2; break;
+ case Tychar: return 0x10ffff; break;
+
+ /* signed ints */
+ case Tyint8: return 0x100; break;
+ case Tyint16: return 0x10000; break;
+ case Tyint32: return 0x100000000; break;
+ case Tyint: return 0x100000000; break;
+ case Tylong: return ~0ull; break;
+ case Tyint64: return ~0ull; break;
+
+ /* unsigned ints */
+ case Tybyte: return 0x100; break;
+ case Tyuint8: return 0x100; break;
+ case Tyuint16: return 0x10000; break;
+ case Tyuint32: return 0x100000000; break;
+ case Tyuint: return 0x100000000; break;
+ case Tyulong: return ~0ull; break;
+ case Tyuint64: return ~0ull; break;
+
+ /* floats */
+ case Tyflt32: return ~0ull; break;
+ case Tyflt64: return ~0ull; break;
+
+ /* complex types */
+ case Typtr: return 1; break;
+ case Tyfunc: return 0; break;
+ case Tyarray: return 1; break;
+ case Tytuple: return 1; break;
+ case Tystruct: return 1;
+ case Tyunion: return t->nmemb; break;
+ case Tyslice: return ~0ULL; break;
+ case Tyvar: case Typaram: case Tyunres: case Tyname:
+ case Tybad: case Tyvalist: case Ntypes:
+ die("Invalid constructor type %s in match", tystr(t));
+ break;
+ }
+ return 0;
+}
+
+static int ndt;
static Dtree *mkdtree()
{
- return zalloc(sizeof(Dtree));
+ Dtree *t;
+
+ t = zalloc(sizeof(Dtree));
+ t->id = ndt++;
+ return t;
}
static Dtree *addwild(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
@@ -66,6 +121,7 @@ static Dtree *addunion(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap
}
sub = mkdtree();
+ sub->patexpr = pat;
lappend(&t->val, &t->nval, pat->expr.args[0]);
lappend(&t->sub, &t->nsub, sub);
if (pat->expr.nargs == 2)
@@ -153,12 +209,71 @@ static Dtree *addpat(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
fatal(pat, "unsupported pattern %s of type %s", opstr(exprop(pat)), tystr(exprtype(pat)));
break;
}
-
+ ret->patexpr = pat;
return ret;
}
-static void checkcomprehensive(Dtree *dt)
+static int isexhaustive(Dtree *dt)
+{
+ Type *subt;
+ size_t i;
+
+ if (dt->any)
+ return 1;
+
+ if (dt->nsub > 0) {
+ subt = tybase(exprtype(dt->sub[0]->patexpr));
+ if (dt->nsub != nconstructors(subt))
+ return 0;
+ }
+ switch (exprop(dt->patexpr)) {
+ case Ovar:
+ return 1;
+ case Olit:
+ return 1;
+ case Oucon:
+ for (i = 0; i < dt->nsub; i++)
+ if (!isexhaustive(dt->sub[i]))
+ return 0;
+ return 1;
+ break;
+ case Otup:
+ for (i = 0; i < dt->nsub; i++)
+ if (!isexhaustive(dt->sub[i]))
+ return 0;
+ return 1;
+ break;
+ case Oarr:
+ for (i = 0; i < dt->nsub; i++)
+ if (!isexhaustive(dt->sub[i]))
+ return 0;
+ return 1;
+ break;
+ case Ostruct:
+ for (i = 0; i < dt->nsub; i++)
+ if (!isexhaustive(dt->sub[i]))
+ return 0;
+ return 1;
+ break;
+ default:
+ die("Invalid pattern in exhaustivenes check. BUG.");
+ break;
+ }
+ return 0;
+}
+
+static int exhaustivematch(Node *m, Dtree *t, Type *tt)
{
+ size_t i;
+
+ if (t->any)
+ return 1;
+ if (t->nsub != nconstructors(tt))
+ return 0;
+ for (i = 0; i < t->nsub; i++)
+ if (!isexhaustive(t->sub[i]))
+ return 0;
+ return 1;
}
static Node *genmatch(Dtree *dt)
@@ -173,11 +288,12 @@ Node *gensimpmatch(Node *m)
size_t npat, ncap;
size_t i;
- t = mkdtree();
pat = m->matchstmt.matches;
npat = m->matchstmt.nmatches;
cap = NULL;
ncap = 0;
+
+ t = mkdtree();
for (i = 0; i < npat; i++) {
leaf = addpat(t, pat[i]->match.pat, NULL, &cap, &ncap);
/* TODO: NULL is returned by unsupported patterns. */
@@ -189,6 +305,49 @@ Node *gensimpmatch(Node *m)
leaf->cap = cap;
leaf->ncap = ncap;
}
- checkcomprehensive(t);
+ if (!exhaustivematch(m, t, exprtype(m->matchstmt.val)))
+ fatal(m, "nonexhaustive pattern set in match statement");
return genmatch(t);
}
+
+char *dtnodestr(Node *n)
+{
+ switch (exprop(n)) {
+ case Ovar:
+ return namestr(n);
+ case Olit:
+ return litstr(n->expr.args[0]->lit.littype);
+ case Oucon:
+ return namestr(n->expr.args[0]);
+ case Otup:
+ return "tuple";
+ case Oarr:
+ return "array";
+ case Ostruct:
+ return "struct";
+ default:
+ die("Invalid pattern in exhaustivenes check. BUG.");
+ break;
+ }
+ return "???";
+}
+
+void dtdumpnode(Dtree *dt, FILE *f, int depth)
+{
+ Node *e;
+ size_t i;
+
+ if (dt->patexpr) {
+ e = dt->patexpr;
+ indentf(depth, "%s %s : %s\n", opstr(exprop(e)), dtnodestr(e), tystr(exprtype(e)));
+ } else {
+ printf("ROOT:\n");
+ }
+ for (i = 0; i < dt->nsub; i++)
+ dtdumpnode(dt->sub[i], f, depth + 1);
+}
+
+void dtdump(Dtree *dt, FILE *f)
+{
+ dtdumpnode(dt, f, 0);
+}