Rewrite pattern matching code.

    Much cleaner, and more efficient.

3 files changed, 568 insertions, 357 deletions

diff --git a/mi/cfg.c b/mi/cfg.c
index de6ddb1..39b59fe 100644
--- a/mi/cfg.c
+++ b/mi/cfg.c
@@ -26,13 +26,6 @@ static Bb *mkbb(Cfg *cfg)
     return bb;
 }
 
-static char *lblstr(Node *n)
-{
-    assert(exprop(n) == Olit);
-    assert(n->expr.args[0]->type == Nlit);
-    assert(n->expr.args[0]->lit.littype == Llbl);
-    return n->expr.args[0]->lit.lblval;
-}
 
 static void strlabel(Cfg *cfg, char *lbl, Bb *bb)
 {
diff --git a/mi/match.c b/mi/match.c
index a2bb271..878a30a 100644
--- a/mi/match.c
+++ b/mi/match.c
@@ -1,4 +1,3 @@
-#include <stdlib.h>
 #include <stdio.h>
 #include <inttypes.h>
 #include <stdarg.h>
@@ -15,34 +14,150 @@
 
 typedef struct Dtree Dtree;
 struct Dtree {
-    /* If the values are equal, go to 'sub'. If 'val' is null, anything matches. */
-    Node *patexpr;      /* the full pattern for this node */
-    Node **val;         /* pattern values to compare against */
-    size_t nval;
-    Node *load;         /* expression value being compared */
-    Dtree **sub;        /* submatch to use if if equal */
-    size_t nsub;
-    Dtree *any;         /* tree for a wildcard match. */
+    int id;
+    Srcloc loc;
+
+    /* values for matching */
+    Node *lbl;
+    Node *load;
+    size_t nconstructors;
+    int accept;
+    int emitted;
+
+    /* the decision tree step */
+    Node **pat;
+    size_t npat;
+    Dtree **next;
+    size_t nnext;
+    Dtree *any;
 
     /* captured variables and action */
     Node **cap;
     size_t ncap;
-    Node *act;
 
-    int id;
 };
 
-void dtdumpnode(Dtree *dt, FILE *f, int depth, int iswild);
-static Dtree *addpat(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap);
-void dtdump(Dtree *dt, FILE *f);
-
-/* We treat all integer types, boolean types, etc, as having 2^n constructors.
- *
- * since, of course, we can't represent all of the constructors for 64 bit
- * integers using 64 bit values, we just approximate it. We'd have failed (run
- * out of memory, etc) long before getting to this code if we actually had that
- * many branches of the switch statements anyways.
- */
+Dtree *gendtree(Node *m, Node *val, Node **lbl, size_t nlbl);
+static int addpat(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend);
+void dtreedump(FILE *fd, Dtree *dt);
+
+
+static Node *utag(Node *n)
+{
+    Node *tag;
+
+    tag = mkexpr(n->loc, Outag, n, NULL);
+    tag->expr.type = mktype(n->loc, Tyint32);
+    return tag;
+}
+
+static Node *uvalue(Node *n, Type *ty)
+{
+    Node *elt;
+
+    elt = mkexpr(n->loc, Oudata, n, NULL);
+    elt->expr.type = ty;
+    return elt;
+}
+
+static Node *tupelt(Node *n, size_t i)
+{
+    Node *idx, *elt;
+
+    idx = mkintlit(n->loc, i);
+    idx->expr.type = mktype(n->loc, Tyuint64);
+    elt = mkexpr(n->loc, Otupget, n, idx, NULL);
+    elt->expr.type = tybase(exprtype(n))->sub[i];
+    return elt;
+}
+
+static Node *arrayelt(Node *n, size_t i)
+{
+    Node *idx, *elt;
+
+    idx = mkintlit(n->loc, i);
+    idx->expr.type = mktype(n->loc, Tyuint64);
+    elt = mkexpr(n->loc, Oidx, n, idx, NULL);
+    elt->expr.type = tybase(exprtype(n))->sub[0];
+    return elt;
+}
+
+static Node *findmemb(Node *pat, Node *name)
+{
+    Node *n;
+    size_t i;
+
+    for (i = 0; i < pat->expr.nargs; i++) {
+        n = pat->expr.args[i];
+        if (nameeq(n->expr.idx, name))
+            return n;
+    }
+    return NULL;
+}
+
+static Dtree *dtbytag(Dtree *t, Ucon *uc)
+{
+    uint32_t tagval;
+    Node *taglit;
+    size_t i;
+
+    for (i = 0; i < t->npat; i++) {
+        taglit = t->pat[i]->expr.args[0];
+        tagval = taglit->lit.intval;
+        if (tagval == uc->id) {
+            return t->next[i];
+        }
+    }
+    return NULL;
+}
+
+static Node *structmemb(Node *n, Node *name, Type *ty)
+{
+    Node *elt;
+
+    elt = mkexpr(n->loc, Omemb, n, name, NULL);
+    elt->expr.type = ty;
+    return elt;
+}
+
+static Node *addcapture(Node *n, Node **cap, size_t ncap)
+{
+    Node **blk;
+    size_t nblk, i;
+
+    nblk = 0;
+    blk = NULL;
+
+    for (i = 0; i < ncap; i++)
+        lappend(&blk, &nblk, cap[i]);
+    for (i = 0; i < n->block.nstmts; i++)
+        lappend(&blk, &nblk, n->block.stmts[i]);
+    lfree(&n->block.stmts, &n->block.nstmts);
+    n->block.stmts = blk;
+    n->block.nstmts = nblk;
+    return n;
+}
+
+static Dtree *mkdtree(Srcloc loc, Node *lbl)
+{
+    static int ndtree;
+    Dtree *t;
+
+    t = zalloc(sizeof(Dtree));
+    t->lbl = lbl;
+    t->loc = loc;
+    t->id = ndtree++;
+    return t;
+}
+
+static Dtree *nextnode(Srcloc loc, size_t idx, size_t count, Dtree *accept)
+{
+    if (idx == count - 1)
+        return accept;
+    else
+        return mkdtree(loc, genlbl(loc));
+}
+
 static size_t nconstructors(Type *t)
 {
     if (!t)
@@ -90,137 +205,211 @@ static size_t nconstructors(Type *t)
     return 0;
 }
 
-static int ndt;
-static Dtree *mkdtree()
+static int verifymatch(Dtree *t)
 {
-    Dtree *t;
-
-    t = zalloc(sizeof(Dtree));
-    t->id = ndt++;
-    return t;
-}
-
-static Node *tupelt(Node *n, size_t i)
-{
-    Node *idx, *elt;
-
-    idx = mkintlit(n->loc, i);
-    idx->expr.type = mktype(n->loc, Tyuint64);
-    elt = mkexpr(n->loc, Otupget, n, idx, NULL);
-    elt->expr.type = tybase(exprtype(n))->sub[i];
-    return elt;
-}
+    size_t i;
+    int ret;
 
-static Node *arrayelt(Node *n, size_t i)
-{
-    Node *idx, *elt;
+    if (t->accept)
+        return 1;
 
-    idx = mkintlit(n->loc, i);
-    idx->expr.type = mktype(n->loc, Tyuint64);
-    elt = mkexpr(n->loc, Oidx, n, idx, NULL);
-    elt->expr.type = tybase(exprtype(n))->sub[0];
-    return elt;
+    ret = 0;
+    if (t->nnext == t->nconstructors || t->any)
+        ret = 1;
+    for (i = 0; i < t->nnext; i++)
+        if (!verifymatch(t->next[i]))
+            ret = 0;
+    return ret;
 }
 
-static Node *structmemb(Node *n, Node *name, Type *ty)
+static int acceptall(Dtree *t, Dtree *accept)
 {
-    Node *elt;
+    size_t i;
+    int ret;
 
-    elt = mkexpr(n->loc, Omemb, n, name, NULL);
-    elt->expr.type = ty;
-    return elt;
-}
+    if (t->any == accept)
+        return 0;
 
-static Node *uvalue(Node *n, Type *ty)
-{
-    Node *elt;
+    ret = 0;
+    if (t->any) {
+        if (acceptall(t->any, accept))
+            ret = 1;
+    } else {
+        t->any = accept;
+        ret = 1;
+    }
 
-    elt = mkexpr(n->loc, Oudata, n, NULL);
-    elt->expr.type = ty;
-    return elt;
+    for (i = 0; i < t->nnext; i++)
+        if (acceptall(t->next[i], accept))
+            ret = 1;
+    return ret;
 }
 
-static Node *deadblock()
+static int addwildrec(Srcloc loc, Type *ty, Dtree *start, Dtree *accept, Dtree ***end, size_t *nend)
 {
-    Node *blk, *dead;
-
-    blk = mkblock(Zloc, mkstab(0));
-    dead = mkexpr(Zloc, Odead, NULL);
-    dead->expr.type = mktype(Zloc, Tyvoid);
-    lappend(&blk->block.stmts, &blk->block.nstmts, dead);
-    return blk;
+    Dtree *next, **last, **tail;
+    size_t i, j, nelt, nlast, ntail;
+    Node *asize;
+    Ucon *uc;
+    int ret;
+
+    tail = NULL;
+    ntail = 0;
+    ty = tybase(ty);
+    if (istyprimitive(ty)) {
+        for (i = 0; i < start->nnext; i++)
+            lappend(end, nend, start->next[i]);
+        if (start->any) {
+            lappend(end, nend, start->any);
+            return 0;
+        } else {
+            start->any = accept;
+            lappend(end, nend, accept);
+            return 1;
+        }
+    }
+    
+    ret = 0;
+    last = NULL;
+    nlast = 0;
+    lappend(&last, &nlast, start);
+    switch (ty->type) {
+        case Tytuple:
+            for (i = 0; i < ty->nsub; i++) {
+                next = nextnode(loc, i, ty->nsub, accept);
+                tail = NULL;
+                ntail = 0;
+                for (j = 0; j < nlast; j++)
+                    if (addwildrec(loc, ty->sub[i], last[j], next, &tail, &ntail))
+                        ret = 1;
+                lfree(&last, &nlast);
+                last = tail;
+                nlast = ntail;
+            }
+            break;
+        case Tyarray:
+            asize = fold(ty->asize, 1);
+            nelt = asize->expr.args[0]->lit.intval;
+            for (i = 0; i < nelt; i++) {
+                next = nextnode(loc, i, nelt, accept);
+                tail = NULL;
+                ntail = 0;
+                for (j = 0; j < nlast; j++)
+                    if (addwildrec(loc, ty->sub[0], last[j], next, &tail, &ntail))
+                        ret = 1;
+                lfree(&last, &nlast);
+                last = tail;
+                nlast = ntail;
+            }
+            break;
+        case Tystruct:
+            for (i = 0; i < ty->nmemb; i++) {
+                next = nextnode(loc, i, ty->nmemb, accept);
+                tail = NULL;
+                ntail = 0;
+                for (j = 0; j < nlast; j++)
+                    if (addwildrec(loc, decltype(ty->sdecls[i]), last[j], next, &tail, &ntail))
+                        ret = 1;
+                lfree(&last, &nlast);
+                last = tail;
+                nlast = ntail;
+            }
+            break;
+        case Tyunion:
+            for (i = 0; i < ty->nmemb; i++) {
+                uc = ty->udecls[i];
+                next = dtbytag(start, uc);
+                if (next) {
+                    if (uc->etype) {
+                        if (addwildrec(loc, uc->etype, next, accept, end, nend))
+                            ret = 1;
+                    } else {
+                        lappend(end, nend, next);
+                    }
+                }
+            }
+            if (!start->any) {
+                start->any = accept;
+                ret = 1;
+            }
+            lappend(end, nend, start->any);
+            break;
+        case Tyslice:
+            ret = acceptall(start, accept);
+            lappend(&last, &nlast, accept);
+            break;
+        default:
+            lappend(&last, &nlast, accept);
+            break;
+    }
+    lcat(end, nend, last, nlast);
+    lfree(&last, &nlast);
+    return ret;
 }
 
-static Dtree *addwild(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
+static int addwild(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
 {
     Node *asn;
 
-    if (t->any)
-        return t->any;
-    t->any = mkdtree();
-    t->any->patexpr = pat;
+    asn = mkexpr(pat->loc, Oasn, pat, val, NULL);
+    asn->expr.type = exprtype(pat);
     if (cap && ncap) {
         asn = mkexpr(pat->loc, Oasn, pat, val, NULL);
         asn->expr.type = exprtype(pat);
         lappend(cap, ncap, asn);
     }
-    return t->any;
+    return addwildrec(pat->loc, exprtype(pat), start, accept, end, nend);
 }
 
-static Dtree *addunion(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
+static int addunion(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
 {
-    Node *elt, *tag, *id;
-    int32_t t1, t2;
-    Dtree *sub;
+    Node *tagid;
+    Dtree *next;
     Ucon *uc;
-    size_t i;
 
-    if (t->any)
-        return t->any;
+    if (start->any) {
+        lappend(end, nend, start->any);
+        return 0;
+    }
+
     uc = finducon(tybase(exprtype(pat)), pat->expr.args[0]);
-    t2 = uc->id;
-    /* if we have the value already... */
-    sub = NULL;
-    for (i = 0; i < t->nval; i++) {
-        tag = t->val[i]->expr.args[0];
-        t1 = tag->lit.intval;
-        if (t1 == t2) {
-            if (pat->expr.nargs > 1) {
-                elt = uvalue(val, exprtype(pat->expr.args[1])); 
-                return addpat(t->sub[i], pat->expr.args[1], elt, cap, ncap);
-            } else {
-                return t->sub[i];
-            }
+    next = dtbytag(start, uc);
+    if (next) {
+        if (!uc->etype) {
+            lappend(end, nend, next);
+            return 0;
+        } else {
+            return addpat(pat->expr.args[1], uvalue(val, uc->etype), next, accept, cap, ncap, end, nend);
         }
     }
 
-    /* otherwise create a new match */
-    sub = mkdtree();
-    sub->patexpr = pat;
-    if (!t->load) {
-        tag = mkexpr(pat->loc, Outag, val, NULL);
-        tag->expr.type = mktype(pat->loc, Tyint32);
-        t->load = tag;
+    if (!start->load) {
+        start->load = utag(val);
+        start->nconstructors = nconstructors(tybase(exprtype(pat)));
     }
 
-    id = mkintlit(pat->loc, uc->id);
-    id->expr.type = mktype(pat->loc, Tyint32);
-
-    lappend(&t->val, &t->nval, id);
-    lappend(&t->sub, &t->nsub, sub);
-    if (pat->expr.nargs == 2) {
-        elt = uvalue(val, exprtype(pat->expr.args[1])); 
-        sub = addpat(sub, pat->expr.args[1], elt, cap, ncap);
+    tagid = mkintlit(pat->loc, uc->id);
+    tagid->expr.type = mktype(pat->loc, Tyint32);
+    lappend(&start->pat, &start->npat, tagid);
+    if (uc->etype) {
+        next = mkdtree(pat->loc, genlbl(pat->loc));
+        lappend(&start->next, &start->nnext, next);
+        addpat(pat->expr.args[1], uvalue(val, uc->etype), next, accept, cap, ncap, end, nend);
+    } else {
+        lappend(&start->next, &start->nnext, accept);
+        lappend(end, nend, accept);
     }
-    return sub;
+    return 1;
 }
 
-static Dtree *addstr(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
+static int addstr(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
 {
+    Dtree **tail, **last, *next;
+    size_t i, j, n, ntail, nlast;
     Node *p, *v, *lit;
-    size_t i, n;
     Type *ty;
     char *s;
+    int ret;
 
     lit = pat->expr.args[0];
     n = lit->lit.strval.len;
@@ -231,342 +420,370 @@ static Dtree *addstr(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
     v = structmemb(val, mkname(pat->loc, "len"), ty);
     p->expr.type = ty;
 
-    t = addpat(t, p, v, cap, ncap);
+    if (n == 0)
+        next = accept;
+    else
+        next = mkdtree(pat->loc, genlbl(pat->loc));
+
+    last = NULL;
+    nlast = 0;
+    if (addpat(p, v, start, next, cap, ncap, &last, &nlast))
+        ret = 1;
 
     ty = mktype(pat->loc, Tybyte);
     for (i = 0; i < n; i++) {
         p = mkintlit(lit->loc, s[i]);
         p->expr.type = ty;
         v = arrayelt(val, i);
-        t = addpat(t, p, v, cap, ncap);
+
+        tail = NULL;
+        ntail = 0;
+        next = nextnode(pat->loc, i, n, accept);
+        for (j = 0; j < nlast; j++) 
+            if (addpat(p, v, last[j], next, NULL, NULL, &tail, &ntail))
+                ret = 1;
+        lfree(&last, &nlast);
+        last = tail;
+        nlast = ntail;
     }
-    return t;
+    lcat(end, nend, last, nlast);
+    lfree(&last, &nlast);
+    return ret;
 }
 
-static Dtree *addlit(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
+static int addlit(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
 {
-    Dtree *sub;
     size_t i;
 
     if (pat->expr.args[0]->lit.littype == Lstr) {
-        sub = addstr(t, pat, val, cap, ncap);
+        return addstr(pat, val, start, accept, cap, ncap, end, nend);
     } else {
-        if (t->any)
-            return t->any;
-        for (i = 0; i < t->nval; i++) {
-            if (liteq(t->val[i]->expr.args[0], pat->expr.args[0]))
-                return t->sub[i];
+        /* if we already have a match, we're not adding a new node */
+        if (start->any) {
+            lappend(end, nend, start->any);
+            return 0;
         }
 
-        sub = mkdtree();
-        sub->patexpr = pat;
-        lappend(&t->val, &t->nval, pat);
-        if (!t->load)
-            t->load = val;
-        lappend(&t->sub, &t->nsub, sub);
+        for (i = 0; i < start->npat; i++) {
+            if (liteq(start->pat[i]->expr.args[0], pat->expr.args[0])) {
+                lappend(end, nend, start->next[i]);
+                return 0;
+            }
+        }
+
+        /* wire up an edge from start to 'accept' */
+        if (!start->load) {
+            start->load = val;
+            start->nconstructors = nconstructors(exprtype(pat));
+        }
+        lappend(&start->pat, &start->npat, pat);
+        lappend(&start->next, &start->nnext, accept);
+        lappend(end, nend, accept);
+        return 1;
     }
-    return sub;
 }
 
-static Dtree *addtup(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
+static int addtup(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
 {
-    size_t i;
-    Node *elt;
-
-    if (t->any)
-        return t->any;
-    for (i = 0; i < pat->expr.nargs; i++) {
-        elt = tupelt(val, i);
-        t = addpat(t, pat->expr.args[i], elt, cap, ncap);
+    size_t nargs, nlast, ntail, i, j;
+    Dtree *next, **last, **tail;
+    Node **args;
+    int ret;
+
+    args = pat->expr.args;
+    nargs = pat->expr.nargs;
+    last = NULL;
+    nlast = 0;
+    lappend(&last, &nlast, start);
+    ret = 0;
+
+    for (i = 0; i < nargs; i++) {
+        next = nextnode(args[i]->loc, i, nargs, accept);
+        tail = NULL;
+        ntail = 0;
+        for (j = 0; j < nlast; j++) 
+            if (addpat(pat->expr.args[i], tupelt(val, i), last[j], next, cap, ncap, &tail, &ntail))
+                ret = 1;
+        lfree(&last, &nlast);
+        last = tail;
+        nlast = ntail;
     }
-    return t;
+    lcat(end, nend, last, nlast);
+    lfree(&last, &nlast);
+    return ret;
 }
 
-static Dtree *addarr(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
+static int addarr(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
 {
-    size_t i;
-    Node *elt;
-
-    if (t->any)
-        return t->any;
-    for (i = 0; i < pat->expr.nargs; i++) {
-        elt = arrayelt(val, i);
-        t = addpat(t, pat->expr.args[i], elt, cap, ncap);
+    size_t nargs, nlast, ntail, i, j;
+    Dtree *next, **last, **tail;
+    Node **args;
+    int ret;
+
+    args = pat->expr.args;
+    nargs = pat->expr.nargs;
+    last = NULL;
+    nlast = 0;
+    lappend(&last, &nlast, start);
+    ret = 0;
+
+    for (i = 0; i < nargs; i++) {
+        next = nextnode(args[i]->loc, i, nargs, accept);
+        tail = NULL;
+        ntail = 0;
+        for (j = 0; j < nlast; j++) 
+            if (addpat(pat->expr.args[i], arrayelt(val, i), last[j], next, cap, ncap, &tail, &ntail))
+                ret = 1;
+        lfree(&last, &nlast);
+        last = tail;
+        nlast = ntail;
     }
-    return t;
+    lcat(end, nend, last, nlast);
+    lfree(&last, &nlast);
+    return ret;
 }
 
-static Dtree *addstruct(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
+static int addstruct(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
 {
-    Node *membpat, *membval, *name;
-    char *patname, *membname;
-    size_t i, j;
-    int found;
-    Type *ty;
-
-    if (t->any)
-        return t->any;
+    Dtree *next, **last, **tail;
+    Node *memb, *name;
+    Type *ty, *mty;
+    size_t i, j, ntail, nlast;
+    int ret;
+
+    ret = 0;
+    last = NULL;
+    nlast = 0;
+    lappend(&last, &nlast, start);
     ty = tybase(exprtype(pat));
+
     for (i = 0; i < ty->nmemb; i++) {
-        found = 0;
+        mty = decltype(ty->sdecls[i]);
         name = ty->sdecls[i]->decl.name;
-        membval = structmemb(val, name, decltype(ty->sdecls[i]));
-        for (j = 0; j < pat->expr.nargs; j++) {
-            membpat = pat->expr.args[j];
-            patname = namestr(membpat->expr.idx);
-            membname = namestr(ty->sdecls[i]->decl.name);
-            if (strcmp(patname, membname) != 0)
-                continue;
-            found = 1;
-            t = addpat(t, membpat, membval, cap, ncap);
-        }
-        if (!found) {
-            membpat = mkexpr(pat->loc, Ogap, NULL);
-            membpat->expr.type = decltype(ty->sdecls[i]);
-            t = addpat(t, membpat, membval, cap, ncap);
+        memb = findmemb(pat, name);
+        next = nextnode(pat->loc, i, ty->nmemb, accept);
+        tail = NULL;
+        ntail = 0;
+
+        for (j = 0; j < nlast; j++) {
+            /* add a _ capture if we don't specify the value */
+            if (!memb) {
+                if (addwild(memb, NULL, last[j], next, NULL, NULL, &tail, &ntail))
+                    ret = 1;
+            } else {
+                if (addpat(memb, structmemb(val, name, mty), last[j], next, cap, ncap, &tail, &ntail))
+                    ret = 1;
+            }
         }
+        lfree(&last, &nlast);
+        last = tail;
+        nlast = ntail;
     }
-    return t;
+    lcat(end, nend, last, nlast);
+    lfree(&last, &nlast);
+    return ret;
 }
 
-static Dtree *addpat(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
+static int addpat(Node *pat, Node *val, Dtree *start, Dtree *accept, Node ***cap, size_t *ncap, Dtree ***end, size_t *nend)
 {
-    Dtree *ret;
+    int ret;
     Node *dcl;
 
-    if (pat == NULL)
-        return t;
     pat = fold(pat, 1);
+    ret = 0;
     switch (exprop(pat)) {
         case Ovar:
             dcl = decls[pat->expr.did];
             if (dcl->decl.isconst)
-                ret = addpat(t, dcl->decl.init, val, cap, ncap);
+                ret = addpat(dcl->decl.init, val, start, accept, cap, ncap, end, nend);
             else
-                ret = addwild(t, pat, val, cap, ncap);
+                ret = addwild(pat, val, start, accept, cap, ncap, end, nend);
             break;
         case Oucon:
-            ret = addunion(t, pat, val, cap, ncap);
+            ret = addunion(pat, val, start, accept, cap, ncap, end, nend);
             break;
         case Olit:
-            ret = addlit(t, pat, val, cap, ncap);
+            ret = addlit(pat, val, start, accept, cap, ncap, end, nend);
             break;
         case Otup:
-            ret = addtup(t, pat, val, cap, ncap);
+            ret = addtup(pat, val, start, accept, cap, ncap, end, nend);
             break;
         case Oarr:
-            ret = addarr(t, pat, val, cap, ncap);
+            ret = addarr(pat, val, start, accept, cap, ncap, end, nend);
             break;
         case Ostruct:
-            ret = addstruct(t, pat, val, cap, ncap);
+            ret = addstruct(pat, val, start, accept, cap, ncap, end, nend);
             break;
         case Ogap:
-            ret = addwild(t, pat, val, NULL, NULL);
+            ret = addwild(pat, NULL, start, accept, NULL, NULL, end, nend);
             break;
         default:
-            ret = NULL;
             fatal(pat, "unsupported pattern %s of type %s", opstr[exprop(pat)], tystr(exprtype(pat)));
             break;
     }
     return ret;
 }
 
-static int isexhaustive(Dtree *dt)
+
+/* val must be a pure, fully evaluated value */
+Dtree *gendtree(Node *m, Node *val, Node **lbl, size_t nlbl)
 {
-    Type *subt;
+    Dtree *start, *accept, **end;
+    Node **pat, **cap;
+    size_t npat, ncap, nend;
     size_t i;
 
-    if (dt->any)
-        return 1;
+    pat = m->matchstmt.matches;
+    npat = m->matchstmt.nmatches;
 
-    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;
+    end = NULL;
+    nend = 0;
+    start = mkdtree(m->loc, genlbl(m->loc));
+    for (i = 0; i < npat; i++) {
+        cap = NULL;
+        ncap = 0;
+        accept = mkdtree(lbl[i]->loc, lbl[i]);
+        accept->accept = 1;
+
+        if (!addpat(pat[i]->match.pat, val, start, accept, &cap, &ncap, &end, &nend))
+            fatal(pat[i], "pattern matched by earlier case");
+        addcapture(pat[i]->match.block, cap, ncap);
     }
-    return 0;
+    if (!verifymatch(start))
+        fatal(m, "nonexhaustive pattern set in match statement");
+    return start;
 }
 
-static int exhaustivematch(Node *m, Dtree *t, Type *tt)
+void genmatchcode(Dtree *dt, Node ***out, size_t *nout)
 {
+    Node *jmp, *eq, *fail;
+    int emit;
     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;
-}
+    if (dt->emitted)
+        return;
+    dt->emitted = 1;
 
-Node *addcapture(Dtree *dt, Node *n)
-{
-    Node **blk;
-    size_t nblk, i;
+    /* the we jump to the accept label when generating the parent */
+    if (dt->accept) {
+        jmp = mkexpr(dt->loc, Ojmp, dt->lbl, NULL);
+        jmp->expr.type = mktype(dt->loc, Tyvoid);
+        lappend(out, nout, jmp);
+        return;
+    }
 
-    nblk = 0;
-    blk = NULL;
+    lappend(out, nout, dt->lbl);
+    for (i = 0; i < dt->nnext; i++) {
+        if (i == dt->nnext - 1 && dt->any) {
+            fail = dt->any->lbl;
+            emit = 0;
+        } else {
+            fail = genlbl(dt->loc);
+            emit = 1;
+        }
 
-    for (i = 0; i < dt->ncap; i++)
-        lappend(&blk, &nblk, dt->cap[i]);
-    for (i = 0; i < n->block.nstmts; i++)
-        lappend(&blk, &nblk, n->block.stmts[i]);
-    lfree(&n->block.stmts, &n->block.nstmts);
-    n->block.stmts = blk;
-    n->block.nstmts = nblk;
-    return n;
+        eq = mkexpr(dt->loc, Oeq, dt->load, dt->pat[i], NULL);
+        eq->expr.type = mktype(dt->loc, Tybool);
+        jmp = mkexpr(dt->loc, Ocjmp, eq, dt->next[i]->lbl, fail, NULL);
+        jmp->expr.type = mktype(dt->loc, Tyvoid);
+        lappend(out, nout, jmp);
+
+        genmatchcode(dt->next[i], out, nout);
+        if (emit)
+            lappend(out, nout, fail);
+    }
+    if (dt->any)
+        genmatchcode(dt->any, out, nout);
 }
 
-static Node *genmatch(Srcloc loc, Dtree *dt, Node *lastany)
+void genonematch(Node *pat, Node *val, Node *iftrue, Node *iffalse, Node ***out, size_t *nout, Node ***cap, size_t *ncap)
 {
-    Node *lastcmp, *cmp, *eq, *pat, *any;
-    size_t i;
+    Dtree *start, *accept, *reject, **end;
+    size_t nend;
 
-    lastcmp = NULL;
-    cmp = NULL;
-    pat = NULL;
-    /* we must have an action if this is a terminal leaf */
-    if (dt->any && dt->any->act)
-        lastany = dt->any->act;
-    if (dt->nsub == 0 && !dt->any)
-        return addcapture(dt, dt->act);
-    for (i = 0; i < dt->nsub; i++) {
-        eq = mkexpr(loc, Oeq, dt->load, dt->val[i], NULL);
-        cmp = mkifstmt(loc, eq, genmatch(loc, dt->sub[i], lastany), NULL);
-        if (!pat)
-            pat = cmp;
-        if (!lastcmp)
-            lastcmp = cmp;
-        else
-            lastcmp->ifstmt.iffalse = cmp;
-        lastcmp = cmp;
-    }
-    if (dt->any) {
-        any = genmatch(loc, dt->any, lastany);
-        if (lastcmp)
-            lastcmp->ifstmt.iffalse = any;
-        else
-            pat = any;
-    } else if (lastcmp) {
-        lastcmp->ifstmt.iffalse = lastany;
-    }
+    end = NULL;
+    nend = 0;
+
+    start = mkdtree(pat->loc, genlbl(pat->loc));
+    accept = mkdtree(iftrue->loc, iftrue);
+    accept->accept = 1;
+    reject = mkdtree(iffalse->loc, iffalse);
+    reject->accept = 1;
 
-    return pat;
+    assert(addpat(pat, val, start, accept, cap, ncap, &end, &nend));
+    acceptall(start, reject);
+    genmatchcode(start, out, nout);
 }
 
-/* val must be a pure, fully evaluated value */
-void gensimpmatch(Node *m, Node *val, Node ***out, size_t *nout)
+void genmatch(Node *m, Node *val, Node ***out, size_t *nout)
 {
-    Node **pat, **cap;
-    size_t npat, ncap;
-    Dtree *t, *leaf;
-    size_t i;
-    Node *n;
+    Node **pat, **lbl, *end, *endlbl;
+    size_t npat, nlbl, i;
+    Dtree *dt;
+
+    lbl = NULL;
+    nlbl = 0;
 
     pat = m->matchstmt.matches;
     npat = m->matchstmt.nmatches;
-    t = mkdtree();
+    for (i = 0; i < npat; i++)
+        lappend(&lbl, &nlbl, genlbl(pat[i]->match.block->loc));
+
+
+    endlbl = genlbl(m->loc);
+    dt = gendtree(m, val, lbl, nlbl);
+    genmatchcode(dt, out, nout);
+
     for (i = 0; i < npat; i++) {
-        cap = NULL;
-        ncap = 0;
-        leaf = addpat(t, pat[i]->match.pat, val, &cap, &ncap);
-        if (leaf->act)
-            fatal(pat[i], "pattern matched by earlier case on line %d", leaf->act->loc.line);
-        leaf->act = pat[i]->match.block;
-        leaf->cap = cap;
-        leaf->ncap = ncap;
+        end = mkexpr(pat[i]->loc, Ojmp, endlbl, NULL);
+        end->expr.type = mktype(end->loc, Tyvoid);
+        lappend(out, nout, lbl[i]);
+        lappend(out, nout, pat[i]->match.block);
+        lappend(out, nout, end);
     }
-    if (!exhaustivematch(m, t, exprtype(m->matchstmt.val)))
-        fatal(m, "nonexhaustive pattern set in match statement");
-    n = genmatch(m->loc, t, deadblock());
-    lappend(out, nout, n);
+    lappend(out, nout, endlbl);
+    
+    //dtreedump(stdout, dt);
+    //for (i = 0; i < *nout; i++)
+    //    dump((*out)[i], stdout);
 }
 
-char *dtnodestr(Node *n)
+
+void dtreedumplit(FILE *fd, Dtree *dt, Node *n, size_t depth)
 {
-    switch (exprop(n)) {
-        case Ovar:
-            return namestr(n->expr.args[0]);
-        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";
-        case Ogap:
-            return "_";
-        case Oasn:
-            return dtnodestr(n->expr.args[0]);
-        default:
-            die("Invalid pattern in exhaustivenes check. BUG.");
-            break;
+    char *s;
+
+    s = lblstr(dt->lbl);
+    switch (n->lit.littype) {
+        case Lchr:      findentf(fd, depth, "%s: Lchr %c\n", s, n->lit.chrval); break;
+        case Lbool:     findentf(fd, depth, "%s: Lbool %s\n", s, n->lit.boolval ? "true" : "false"); break;
+        case Lint:      findentf(fd, depth, "%s: Lint %llu\n", s, n->lit.intval); break;
+        case Lflt:      findentf(fd, depth, "%s: Lflt %lf\n", s, n->lit.fltval); break;
+        case Lstr:      findentf(fd, depth, "%s: Lstr %.*s\n", s, (int)n->lit.strval.len, n->lit.strval.buf); break;
+        case Llbl:      findentf(fd, depth, "%s: Llbl %s\n", s, n->lit.lblval); break;
+        case Lfunc:     findentf(fd, depth, "%s: Lfunc\n"); break;
     }
-    return "???";
 }
 
-void dtdumpnode(Dtree *dt, FILE *f, int depth, int iswild)
+void dtreedumpnode(FILE *fd, Dtree *dt, size_t depth)
 {
-    Node *e;
     size_t i;
-    char *s;
 
-    if (dt->patexpr) {
-        e = dt->patexpr;
-        s = tystr(exprtype(e));
-        indentf(depth, "%s%s %s : %s\n", iswild ? "WILDCARD " : "", opstr[exprop(e)], dtnodestr(e), s);
-        free(s);
-    } 
-    if (dt->cap)
-        for (i = 0; i < dt->ncap; i++)
-            indentf(depth + 1, "capture %s\n", dtnodestr(dt->cap[i]));
-    if (dt->act)
-        indentf(depth + 1, "action\n");
-    for (i = 0; i < dt->nsub; i++)
-        dtdumpnode(dt->sub[i], f, depth + 1, 0);
-    if (dt->any)
-        dtdumpnode(dt->any, f, depth + 1, 1);
+    if (dt->accept)
+        findentf(fd, depth, "%s: accept\n", lblstr(dt->lbl));
+
+    for (i = 0; i < dt->nnext; i++) {
+        dtreedumplit(fd, dt, dt->pat[i]->expr.args[0], depth);
+        dtreedumpnode(fd, dt->next[i], depth + 1);
+    }
+    if (dt->any) {
+        findentf(fd, depth, "%s: wildcard\n", lblstr(dt->lbl));
+        dtreedumpnode(fd, dt->any, depth + 1);
+    }
 }
 
-void dtdump(Dtree *dt, FILE *f)
+void dtreedump(FILE *fd, Dtree *dt)
 {
-    dtdumpnode(dt, f, 0, 0);
+    dtreedumpnode(fd, dt, 0);
 }
+
diff --git a/mi/mi.h b/mi/mi.h
index a29619a..0b9c8a8 100644
--- a/mi/mi.h
+++ b/mi/mi.h
@@ -48,4 +48,5 @@ void dumpcfg(Cfg *c, FILE *fd);
 void check(Cfg *cfg);
 
 /* pattern matching */
-void gensimpmatch(Node *m, Node *val, Node ***out, size_t *nout);
+void genmatch(Node *m, Node *val, Node ***out, size_t *nout);
+void genonematch(Node *pat, Node *val, Node *iftrue, Node *iffalse, Node ***out, size_t *nout, Node ***cap, size_t *ncap);