diff options
author | Ori Bernstein <ori@eigenstate.org> | 2014-11-04 21:34:24 -0500 |
---|---|---|
committer | Ori Bernstein <ori@eigenstate.org> | 2014-11-04 21:34:24 -0500 |
commit | 09af6b8f6597c29208b8725b4f67bd7ed6d45e85 (patch) | |
tree | bde47d08349e5512f71c36c5f7d39e19ffd0f4b0 | |
parent | 3460240b3a7654af5a994d305d8ab440b7fdfd54 (diff) | |
download | mc-09af6b8f6597c29208b8725b4f67bd7ed6d45e85.tar.gz |
Check for exhaustiveness in patterns.
-rw-r--r-- | libstd/fltfmt.myr | 2 | ||||
-rw-r--r-- | libstd/fmt.myr | 1 | ||||
-rw-r--r-- | libstd/hashfuncs.myr | 3 | ||||
-rw-r--r-- | libstd/resolve.myr | 20 | ||||
-rw-r--r-- | mi/match.c | 175 |
5 files changed, 189 insertions, 12 deletions
diff --git a/libstd/fltfmt.myr b/libstd/fltfmt.myr index ce77e2c..9fe07cd 100644 --- a/libstd/fltfmt.myr +++ b/libstd/fltfmt.myr @@ -151,6 +151,7 @@ const dragon4 = {buf, isneg, f, e, p, mode, cutoff bigfree(t) bigfree(u) break + | _: ;; ;; @@ -173,6 +174,7 @@ const dragon4 = {buf, isneg, f, e, p, mode, cutoff bigshli(t, 1) match bigcmp(t, mm) | `Before: low = true + | _: ;; bigfree(t) diff --git a/libstd/fmt.myr b/libstd/fmt.myr index 486b08b..64cd043 100644 --- a/libstd/fmt.myr +++ b/libstd/fmt.myr @@ -196,6 +196,7 @@ const bfmtv = {buf, fmt, ap | '0': (c, fmt) = striter(fmt) padfill = '0' + | _: /* nothing */ ;; if isdigit(c) && padto == 0 /* diff --git a/libstd/hashfuncs.myr b/libstd/hashfuncs.myr index 49aa0e5..8edb439 100644 --- a/libstd/hashfuncs.myr +++ b/libstd/hashfuncs.myr @@ -1,3 +1,4 @@ +use "die.use" use "sleq.use" use "types.use" @@ -78,6 +79,8 @@ const murmurhash2 = {data, seed h ^= (data[0] castto(uint32)) | 1: h ^= (data[0] castto(uint32)) + | 0: /* nothing */ + | _: die("0 < len < 4 must be true") ;; h *= m diff --git a/libstd/resolve.myr b/libstd/resolve.myr index 5653338..3a4fc42 100644 --- a/libstd/resolve.myr +++ b/libstd/resolve.myr @@ -116,6 +116,7 @@ const loadhosts = { /* trim comment */ match strfind(l, "#") | `Some idx: l = l[:idx] + | `None: /* whole line */ ;; match word(l) @@ -123,6 +124,12 @@ const loadhosts = { match ipparse(ip) | `Some addr: addhosts(addr, ip, rest) + | `None: + /* + invalid addresses are ignored: we don't want to break stuff + with invalid or unsupported addresses + */ + ;; | `None: ;; @@ -175,10 +182,12 @@ const loadresolv = { ;; match word(l) - | `Some (cmd, rest): - if sleq(cmd, "nameserver") - addns(rest) - ;; + | `Some ("nameserver", srv): + addns(srv) + | `Some (_, rest): + /* invalid or unrecognized commands */ + | `None: + /* unrecognized lines */ ;; ;; slfree(lines) @@ -191,7 +200,10 @@ const addns = {rest | `Some addr: nameservers = slpush(nameservers, addr) | `None: + /* nothing */ ;; + | `None: + /* nothing */ ;; } @@ -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); +} |