ref: 72eec560c90e738fd117abcdadd911803bfb32a5
parent: 4778a1f97154b7c829b459c004110ca80e74b43f
parent: 7d590b64d3ad57239c8835b2fd1a0d2db2b2981a
author: Ori Bernstein <[email protected]>
date: Tue Dec 2 11:40:20 EST 2014
Merge branch 'master' of git+ssh://git.eigenstate.org/git/ori/mc
--- a/6/isel.c
+++ b/6/isel.c
@@ -668,6 +668,9 @@
case Ocjmp:
selcjmp(s, n, args);
break;
+ case Ojtab:
+ die("jump tables not yet implemented\n");+ break;
case Olit: /* fall through */
r = loc(s, n);
break;
@@ -680,9 +683,6 @@
r = loc(s, n);
}
break;
- case Olbl:
- r = loclbl(args[0]);
- break;
case Oblit:
a = selexpr(s, args[0]);
r = selexpr(s, args[1]);
@@ -740,10 +740,11 @@
case Opostdec: case Olor: case Oland: case Oaddeq:
case Osubeq: case Omuleq: case Odiveq: case Omodeq: case Oboreq:
case Obandeq: case Obxoreq: case Obsleq: case Obsreq: case Omemb:
- case Oslice: case Oidx: case Osize: case Numops:
- case Oucon: case Ouget: case Otup: case Oarr: case Ostruct:
- case Oslbase: case Osllen: case Ocast:
- case Obreak: case Ocontinue:
+ case Oslbase: case Osllen: case Ocast: case Outag: case Oudata:
+ case Oucon: case Otup: case Oarr: case Ostruct:
+ case Oslice: case Oidx: case Osize:
+ case Obreak: case Ocontinue:
+ case Numops:
dump(n, stdout);
die("Should not see %s in isel", opstr(exprop(n)));break;
--- a/6/simp.c
+++ b/6/simp.c
@@ -1291,7 +1291,10 @@
case Oucon:
r = simpucon(s, n, dst);
break;
- case Ouget:
+ case Outag:
+ die("union tags not yet supported\n");+ break;
+ case Oudata:
r = simpuget(s, n, dst);
break;
case Otup:
--- a/bench/runner.c
+++ b/bench/runner.c
@@ -50,7 +50,7 @@
return sec + usec;
}
-void timed_run(char *prog)
+double timed_run(char *prog)
{double avg, m, d, x;
int i, n;
@@ -66,15 +66,19 @@
m = m + d*(x - avg);
}
printf("%s:\t%fs (σ^2: %f)\n", prog, avg, m/(n-1));+ return avg;
}
int main(int argc, char **argv)
{+ double tot;
int i;
printf("Running benchmarks: %d samples per binary\n", Nsamp);+ tot = 0;
for (i = 1; i < argc; i++)
- timed_run(argv[i]);
+ tot += timed_run(argv[i]);
+ printf("total:\t%fs\n", tot);return 0;
}
--- 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/libstd/search.myr
+++ b/libstd/search.myr
@@ -15,6 +15,8 @@
match cmp(sl[i], val)
| `Equal:
-> `Some i
+ | _:
+ /* nothing */
;;
;;
-> `None
--- a/libstd/sort.myr
+++ b/libstd/sort.myr
@@ -40,10 +40,12 @@
s = r
match cmp(sl[s], sl[c])
| `Before: s = c
+ | _: /* nothing */
;;
if c + 1 < sl.len
match cmp(sl[s], sl[c + 1])
| `Before: s = c + 1
+ | _: /* nothing */
;;
;;
if s != r
--- 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,26 +30,78 @@
size_t ncap;
Node *act;
+ int id;
};
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.
+ */
+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)
{- Node *dcl;
-
- dcl = decls[pat->expr.did];
- /* FIXME: Avoid duplicate constants */
- if (dcl->decl.isconst)
- return NULL;
if (t->any)
return t->any;
t->any = mkdtree();
+ t->any->patexpr = pat;
lappend(cap, ncap, pat);
return t->any;
}
@@ -58,6 +111,8 @@
Dtree *sub;
size_t i;
+ if (t->any)
+ return t->any;
/* if we have the value already... */
sub = NULL;
for (i = 0; i < t->nval; i++) {@@ -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)
@@ -78,6 +134,8 @@
Dtree *sub;
size_t i;
+ 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 addpat(t->sub[i], pat->expr.args[1], NULL, cap, ncap);
@@ -84,6 +142,7 @@
}
sub = mkdtree();
+ sub->patexpr = pat;
lappend(&t->val, &t->nval, pat);
lappend(&t->sub, &t->nsub, sub);
return sub;
@@ -93,6 +152,8 @@
{size_t i;
+ if (t->any)
+ return t->any;
for (i = 0; i < pat->expr.nargs; i++)
t = addpat(t, pat->expr.args[i], NULL, cap, ncap);
return t;
@@ -102,6 +163,8 @@
{size_t i;
+ if (t->any)
+ return t->any;
for (i = 0; i < pat->expr.nargs; i++)
t = addpat(t, pat->expr.args[i], NULL, cap, ncap);
return t;
@@ -112,6 +175,8 @@
Node *elt;
size_t i, j;
+ if (t->any)
+ return t->any;
for (i = 0; i < pat->expr.nargs; i++) {elt = pat->expr.args[i];
for (j = 0; j < t->nval; j++) {@@ -126,12 +191,17 @@
static Dtree *addpat(Dtree *t, Node *pat, Node *val, Node ***cap, size_t *ncap)
{Dtree *ret;
+ Node *dcl;
if (pat == NULL)
return t;
switch (exprop(pat)) {case Ovar:
- ret = addwild(t, pat, val, cap, ncap);
+ dcl = decls[pat->expr.did];
+ if (dcl->decl.isconst)
+ ret = addpat(t, dcl->decl.init, val, cap, ncap);
+ else
+ ret = addwild(t, pat, val, cap, ncap);
break;
case Oucon:
ret = addunion(t, pat, val, cap, ncap);
@@ -153,14 +223,72 @@
fatal(pat, "unsupported pattern %s of type %s", opstr(exprop(pat)), tystr(exprtype(pat)));
break;
}
-
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,22 +301,69 @@
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++) {+ cap = NULL;
+ ncap = 0;
leaf = addpat(t, pat[i]->match.pat, NULL, &cap, &ncap);
/* TODO: NULL is returned by unsupported patterns. */
if (!leaf)
return NULL;
if (leaf->act)
- fatal(pat[i], "pattern matched by earlier case");
+ 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;
}
- 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->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";
+ default:
+ die("Invalid pattern in exhaustivenes check. BUG.");+ break;
+ }
+ return "???";
+}
+
+void dtdumpnode(Dtree *dt, FILE *f, int depth, int iswild)
+{+ Node *e;
+ size_t i;
+ if (dt->patexpr) {+ e = dt->patexpr;
+ indentf(depth, "%s%s %s : %s\n", iswild ? "WILDCARD " : "", opstr(exprop(e)), dtnodestr(e), tystr(exprtype(e)));
+ }
+ 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);
+}
+
+void dtdump(Dtree *dt, FILE *f)
+{+ dtdumpnode(dt, f, 0, 0);
}
--- a/parse/infer.c
+++ b/parse/infer.c
@@ -1437,11 +1437,8 @@
}
settype(st, n, type(st, args[0]));
break;
- case Olbl: /* :lbl -> void* */
- infersub(st, n, ret, sawret, &isconst);
- settype(st, n, mktyptr(n->loc, mktype(Zloc, Tyvoid)));
- case Obad: case Ocjmp: case Oset:
- case Oslbase: case Osllen:
+ case Obad: case Ocjmp: case Ojtab: case Oset:
+ case Oslbase: case Osllen: case Outag:
case Oblit: case Numops:
case Otrunc: case Oswiden: case Ozwiden:
case Oint2flt: case Oflt2int: case Oflt2flt:
@@ -1448,7 +1445,7 @@
case Ofadd: case Ofsub: case Ofmul: case Ofdiv: case Ofneg:
case Ofeq: case Ofne: case Ofgt: case Ofge: case Oflt: case Ofle:
case Oueq: case Oune: case Ougt: case Ouge: case Oult: case Oule:
- case Ouget:
+ case Oudata:
die("Should not see %s in fe", opstr(exprop(n)));break;
}
@@ -1670,7 +1667,7 @@
for (i = 0; i < n->func.nargs; i++)
putbindings(st, st->tybindings[st->ntybindings - 1], n->func.args[i]->decl.type);
pushstab(n->func.scope);
- inferstab(st, n->block.scope);
+ inferstab(st, n->func.scope);
inferfunc(st, n);
popstab();
break;
--- a/parse/ops.def
+++ b/parse/ops.def
@@ -50,9 +50,7 @@
O(Ocontinue, 0)
O(Ovar, 1)
O(Olit, 1)
-O(Olbl, 1)
O(Oucon, 1)
-O(Ouget, 1)
O(Otup, 1)
O(Ostruct, 1)
O(Oarr, 1)
@@ -59,16 +57,25 @@
/* all below this point are backend-only */
O(Ocjmp, 1) /* conditional jump */
+O(Ojtab, 1) /* jump table */
O(Oset, 1) /* store to var */
O(Osllen, 1) /* size of slice */
O(Oslbase, 1) /* base of sice */
-O(Oblit, 1) /* block copy of memory */
+O(Outag, 1) /* tag of union */
+O(Oudata, 1) /* pointer to contents of union */
+O(Oblit, 1) /* blit memory */
+
+/* integer conversions */
O(Otrunc, 1) /* truncating cast */
O(Ozwiden, 1) /* zero-extending widening cast */
O(Oswiden, 1) /* sign-extending widening cast */
+
+/* float conversions */
O(Oflt2int, 1) /* float to int conversion */
O(Oint2flt, 1) /* int to float conversion */
O(Oflt2flt, 1) /* flt32<->flt64 conversion */
+
+/* floating arithmetic */
O(Ofadd, 1)
O(Ofsub, 1)
O(Ofmul, 1)
@@ -82,6 +89,7 @@
O(Ofge, 1)
O(Oflt, 1)
O(Ofle, 1)
+
/* unsigned comparisons */
O(Oueq, 1)
O(Oune, 1)
--- a/test/genericret.myr
+++ b/test/genericret.myr
@@ -12,6 +12,7 @@
const main = {match f()
| `None: std.exit(42)
+ | _: std.die("Impossible match failure\n");;;
std.exit(0)
}
--- a/test/generictype.myr
+++ b/test/generictype.myr
@@ -13,6 +13,7 @@
match v
| `None: std.exit(1)
| `Some 123: std.exit(0)
+ | `Some _: std.die("Impossible match failure\n");;
std.exit(60)
}
--- a/test/matchargstr.myr
+++ b/test/matchargstr.myr
@@ -17,6 +17,7 @@
| `Str "fsda": std.fatal(1, "Wrong match `Str \"fsda\"\n")
| `Str "asdf": std.put("Correct `Str \"asdf\"!\n")| `Nil: std.fatal(1, "Wrong match `Str \"fsda\"\n")
+ | _: std.fatal(1, "Impossible failed match\n")
;;
}
--- a/test/matchargunion.myr
+++ b/test/matchargunion.myr
@@ -12,10 +12,11 @@
v = `Int 123
match v
- | `Int 127: std.exit(42)
- | `Int 123: std.exit(69)
- | `Chr 'a': std.exit(4)
- | `Nil: std.exit(6)
+ | `Int 127: std.exit(42)
+ | `Int 123: std.exit(69)
+ | `Chr 'a': std.exit(4)
+ | `Nil: std.exit(6)
+ | _: std.die("Impossible failed match\n");;
}
--- a/test/matchbind.myr
+++ b/test/matchbind.myr
@@ -16,6 +16,7 @@
| `Int x: std.exit(x)
| `Chr 'a': std.exit(4)
| `Nil: std.exit(6)
+ | x: std.die("Impossible match failure\n");;
}
--- a/test/matchconst.myr
+++ b/test/matchconst.myr
@@ -14,5 +14,6 @@
| Ca: std.exit(123)
| Cb: std.exit(88)
| Cc: std.exit(42)
+ | _: std.die("Impossible match failure in pattern\n");;
}
--- /dev/null
+++ b/test/matchexhaust.myr
@@ -1,0 +1,37 @@
+use std
+
+type u = union
+ `Foo (bool, v, bool)
+ `Bar (bool, bool)
+ `Baz bool
+ `Quux
+;;
+
+type v = union
+ `A
+ `B
+;;
+
+const main = {+ match `Quux
+ | `Foo (true, `A, true):
+ | `Foo (true, `A, false):
+ | `Foo (true, `B, true):
+ | `Foo (true, `B, false):
+ | `Foo (false, `A, true):
+ | `Foo (false, `A, false):
+ | `Foo (false, `B, true):
+ | `Foo (false, `B, false):
+
+ | `Bar (false, false):
+ | `Bar (false, true):
+ | `Bar (true, false):
+ | `Bar (true, true):
+
+ | `Baz false:
+ | `Baz true:
+
+ | `Quux:
+ ;;
+ std.put("worked\n")+}
--- a/test/matchint.myr
+++ b/test/matchint.myr
@@ -11,5 +11,6 @@
| 4: std.exit(99)
| 12: std.exit(84)
| 6: std.exit(18)
+ | x: std.die("Got an unexpected int!\n");;
}
--- a/test/matchunion_sl.myr
+++ b/test/matchunion_sl.myr
@@ -15,6 +15,7 @@
| `Int 127: std.exit(42)
| `Str s: std.put("%s\n", s)| `Nil:
+ | _: std.die("Impossible match failure\n");;
}
--- a/test/nestucon.myr
+++ b/test/nestucon.myr
@@ -13,6 +13,7 @@
a = [.x = `Str "asdf"]
match a
| [.x=`Str s]: std.put("%s\n", s)+ | _: std.die("Impossible match failure\n");;
}
--- a/test/stdsearch.myr
+++ b/test/stdsearch.myr
@@ -20,6 +20,7 @@
| `std.None:
match b
| `std.Some x: std.fatal(1, "Expected `std.None, `std.None, got `std.None, `std.Some %i\n", x)
+ | `std.None: /* nothing */
;;
| `std.Some x:
match b
--- a/test/tests
+++ b/test/tests
@@ -104,6 +104,7 @@
B matchstruct E 42
B matcharray E 42
B matchargunion E 69
+B matchexhaust P worked
B matchargstr C
B matchunion_sl P foo
B matchbind E 8