Check for exhaustiveness in patterns.

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 */
 	;;
 }
 
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);
+}