ref: ad893b63f1fe71c628742a0e38ddae971bdf8231
parent: 61ba873d4db80af7b53b4e35b6d50b57d1f22e91
author: Ori Bernstein <[email protected]>
date: Tue Nov 4 16:34:24 EST 2014
Check for exhaustiveness in patterns.
--- a/libstd/fltfmt.myr
+++ b/libstd/fltfmt.myr
@@ -151,6 +151,7 @@
bigfree(t)
bigfree(u)
break
+ | _:
;;
;;
@@ -173,6 +174,7 @@
bigshli(t, 1)
match bigcmp(t, mm)
| `Before: low = true
+ | _:
;;
bigfree(t)
--- a/libstd/fmt.myr
+++ b/libstd/fmt.myr
@@ -196,6 +196,7 @@
| '0':
(c, fmt) = striter(fmt)
padfill = '0'
+ | _: /* nothing */
;;
if isdigit(c) && padto == 0
/*
--- 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 @@
h ^= (data[0] castto(uint32))
| 1:
h ^= (data[0] castto(uint32))
+ | 0: /* nothing */
+ | _: die("0 < len < 4 must be true");;
h *= m
--- a/libstd/resolve.myr
+++ b/libstd/resolve.myr
@@ -116,6 +116,7 @@
/* trim comment */
match strfind(l, "#")
| `Some idx: l = l[:idx]
+ | `None: /* whole line */
;;
match word(l)
@@ -123,6 +124,12 @@
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 @@
;;
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 @@
| `Some addr:
nameservers = slpush(nameservers, addr)
| `None:
+ /* nothing */
;;
+ | `None:
+ /* nothing */
;;
}
--- 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 @@
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 @@
}
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,14 +209,73 @@
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)
{return NULL;
@@ -173,11 +288,12 @@
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 @@
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);
}