Rewrite exhaustiveness checker

Issue #352
Closes #1720

The old checker would happily accept things like 'alt x { @some(a) { a } }'.
It now properly descends into patterns, checks exhaustiveness of booleans,
and complains when number/string patterns aren't exhaustive.

5 files changed, 129 insertions, 82 deletions

diff --git a/src/comp/metadata/decoder.rs b/src/comp/metadata/decoder.rs
index 2a089ad14ad..867497f37fd 100644
--- a/src/comp/metadata/decoder.rs
+++ b/src/comp/metadata/decoder.rs
@@ -218,7 +218,7 @@ fn lookup_def(cnum: ast::crate_num, data: @[u8], did_: ast::def_id) ->
     let fam_ch = item_family(item);
     let did = {crate: cnum, node: did_.node};
     // We treat references to enums as references to types.
-    alt fam_ch {
+    alt check fam_ch {
       'c' { ast::def_const(did) }
       'u' { ast::def_fn(did, ast::unsafe_fn) }
       'f' { ast::def_fn(did, ast::impure_fn) }
@@ -336,7 +336,7 @@ fn get_iface_methods(cdata: cmd, id: ast::node_id, tcx: ty::ctxt)
           _ { tcx.sess.bug("get_iface_methods: id has non-function type");
         } };
         result += [{ident: name, tps: bounds, fty: fty,
-                    purity: alt item_family(mth) {
+                    purity: alt check item_family(mth) {
                       'u' { ast::unsafe_fn }
                       'f' { ast::impure_fn }
                       'p' { ast::pure_fn }
@@ -346,7 +346,7 @@ fn get_iface_methods(cdata: cmd, id: ast::node_id, tcx: ty::ctxt)
 }
 
 fn family_has_type_params(fam_ch: char) -> bool {
-    alt fam_ch {
+    alt check fam_ch {
       'c' | 'T' | 'm' | 'n' { false }
       'f' | 'u' | 'p' | 'F' | 'U' | 'P' | 'y' | 't' | 'v' | 'i' | 'I' { true }
     }
@@ -370,7 +370,7 @@ fn describe_def(items: ebml::doc, id: ast::def_id) -> str {
 }
 
 fn item_family_to_str(fam: char) -> str {
-    alt fam {
+    alt check fam {
       'c' { ret "const"; }
       'f' { ret "fn"; }
       'u' { ret "unsafe fn"; }
diff --git a/src/comp/metadata/tydecode.rs b/src/comp/metadata/tydecode.rs
index be7afbe0437..c7d434b3c1c 100644
--- a/src/comp/metadata/tydecode.rs
+++ b/src/comp/metadata/tydecode.rs
@@ -177,7 +177,7 @@ fn parse_proto(c: char) -> ast::proto {
 }
 
 fn parse_ty(st: @pstate, conv: conv_did) -> ty::t {
-    alt next(st) {
+    alt check next(st) {
       'n' { ret ty::mk_nil(st.tcx); }
       'z' { ret ty::mk_bot(st.tcx); }
       'b' { ret ty::mk_bool(st.tcx); }
@@ -185,7 +185,7 @@ fn parse_ty(st: @pstate, conv: conv_did) -> ty::t {
       'u' { ret ty::mk_uint(st.tcx); }
       'l' { ret ty::mk_float(st.tcx); }
       'M' {
-        alt next(st) {
+        alt check next(st) {
           'b' { ret ty::mk_mach_uint(st.tcx, ast::ty_u8); }
           'w' { ret ty::mk_mach_uint(st.tcx, ast::ty_u16); }
           'l' { ret ty::mk_mach_uint(st.tcx, ast::ty_u32); }
@@ -269,7 +269,7 @@ fn parse_ty(st: @pstate, conv: conv_did) -> ty::t {
       'Y' { ret ty::mk_type(st.tcx); }
       'y' { ret ty::mk_send_type(st.tcx); }
       'C' {
-        let ck = alt next(st) {
+        let ck = alt check next(st) {
           '&' { ty::ck_block }
           '@' { ty::ck_box }
           '~' { ty::ck_uniq }
@@ -355,7 +355,7 @@ fn parse_ty_fn(st: @pstate, conv: conv_did) -> ty::fn_ty {
     assert (next(st) == '[');
     let inputs: [ty::arg] = [];
     while peek(st) != ']' {
-        let mode = alt peek(st) {
+        let mode = alt check peek(st) {
           '&' { ast::by_mut_ref }
           '-' { ast::by_move }
           '+' { ast::by_copy }
@@ -405,7 +405,7 @@ fn parse_bounds_data(data: @[u8], start: uint,
 fn parse_bounds(st: @pstate, conv: conv_did) -> @[ty::param_bound] {
     let bounds = [];
     while true {
-        bounds += [alt next(st) {
+        bounds += [alt check next(st) {
           'S' { ty::bound_send }
           'C' { ty::bound_copy }
           'I' { ty::bound_iface(parse_ty(st, conv)) }
diff --git a/src/comp/middle/check_alt.rs b/src/comp/middle/check_alt.rs
index 5e377e33226..e1bf34ce5e4 100644
--- a/src/comp/middle/check_alt.rs
+++ b/src/comp/middle/check_alt.rs
@@ -27,7 +27,7 @@ fn check_expr(tcx: ty::ctxt, ex: @expr, &&s: (), v: visit::vt<()>) {
         /* Check for exhaustiveness */
         if mode == alt_exhaustive {
             let arms = vec::concat(vec::filter_map(arms, unguarded_pat));
-            check_exhaustive(tcx, ex.span, expr_ty(tcx, scrut), arms);
+            check_exhaustive(tcx, ex.span, arms);
         }
       }
       _ { }
@@ -59,89 +59,136 @@ fn check_arms(tcx: ty::ctxt, arms: [arm]) {
     }
 }
 
+fn raw_pat(p: @pat) -> @pat {
+    alt p.node {
+      pat_ident(_, some(s)) { raw_pat(s) }
+      _ { p }
+    }
+}
+
 // Precondition: patterns have been normalized
 // (not checked statically yet)
-fn check_exhaustive(tcx: ty::ctxt, sp:span, scrut_ty:ty::t, pats:[@pat]) {
-    let represented : [def_id] = [];
-    /* Determine the type of the scrutinee */
-    /* If it's not an enum, exit (bailing out on checking non-enum alts
-       for now) */
-    /* Otherwise, get the list of variants and make sure each one is
-     represented. Then recurse on the columns. */
-
-    let ty_def_id = alt ty::get(scrut_ty).struct {
-            ty_enum(id, _) { id }
-            _ { ret; } };
+fn check_exhaustive(tcx: ty::ctxt, sp: span, pats: [@pat]) {
+    if pats.len() == 0u {
+        tcx.sess.span_err(sp, "non-exhaustive patterns");
+        ret;
+    }
+    // If there a non-refutable pattern in the set, we're okay.
+    for pat in pats { if !is_refutable(tcx, pat) { ret; } }
 
-    let variants = *enum_variants(tcx, ty_def_id);
-    for pat in pats {
-        if !is_refutable(tcx, pat) {
-                /* automatically makes this alt complete */ ret;
+    alt ty::get(ty::node_id_to_type(tcx, pats[0].id)).struct {
+      ty::ty_enum(id, _) {
+        check_exhaustive_enum(tcx, id, sp, pats);
+      }
+      ty::ty_box(_) {
+        check_exhaustive(tcx, sp, vec::filter_map(pats, {|p|
+            alt raw_pat(p).node { pat_box(sub) { some(sub) } _ { none } }
+        }));
+      }
+      ty::ty_uniq(_) {
+        check_exhaustive(tcx, sp, vec::filter_map(pats, {|p|
+            alt raw_pat(p).node { pat_uniq(sub) { some(sub) } _ { none } }
+        }));
+      }
+      ty::ty_tup(ts) {
+        let cols = vec::init_elt_mut(ts.len(), []);
+        for p in pats {
+            alt raw_pat(p).node {
+              pat_tup(sub) {
+                vec::iteri(sub) {|i, sp| cols[i] += [sp];}
+              }
+              _ {}
+            }
         }
-        alt pat.node {
-                // want the def_id for the constructor
-            pat_enum(id,_) {
-                alt tcx.def_map.find(pat.id) {
-                    some(def_variant(_, variant_def_id)) {
-                        represented += [variant_def_id];
+        vec::iter(cols) {|col| check_exhaustive(tcx, sp, col); }
+      }
+      ty::ty_rec(fs) {
+        let cols = vec::init_elt(fs.len(), {mutable wild: false,
+                                            mutable pats: []});
+        for p in pats {
+            alt raw_pat(p).node {
+              pat_rec(sub, _) {
+                vec::iteri(fs) {|i, field|
+                    alt vec::find(sub, {|pf| pf.ident == field.ident }) {
+                      some(pf) { cols[i].pats += [pf.pat]; }
+                      none { cols[i].wild = true; }
                     }
-                    _ { tcx.sess.span_bug(pat.span, "check_exhaustive:
-                          pat_tag not bound to a variant"); }
                 }
+              }
+              _ {}
+            }
+        }
+        vec::iter(cols) {|col|
+            if !col.wild { check_exhaustive(tcx, sp, copy col.pats); }
+        }
+      }
+      ty::ty_bool {
+        let saw_true = false, saw_false = false;
+        for p in pats {
+            alt raw_pat(p).node {
+              pat_lit(@{node: expr_lit(@{node: lit_bool(b), _}), _}) {
+                if b { saw_true = true; }
+                else { saw_false = true; }
+              }
+              _ {}
             }
-            _ { tcx.sess.span_bug(pat.span, "check_exhaustive: ill-typed \
-                  pattern");   // we know this has enum type,
-            }                  // so anything else should be impossible
-         }
-    }
-    fn not_represented(v: [def_id], &&vinfo: variant_info) -> bool {
-        !vec::contains(v, vinfo.id)
-    }
-    // Could be more efficient (bitvectors?)
-    alt vec::find(variants, bind not_represented(represented,_)) {
-        some(bad) {
-        // complain
-        // TODO: give examples of cases that aren't covered
-            tcx.sess.note("Patterns not covered include:");
-            tcx.sess.note(bad.name);
-            tcx.sess.span_err(sp, "Non-exhaustive pattern");
         }
-        _ {}
+        if !saw_true { tcx.sess.span_err(
+            sp, "non-exhaustive bool patterns: true not covered"); }
+        if !saw_false { tcx.sess.span_err(
+            sp, "non-exhaustive bool patterns: false not covered"); }
+      }
+      ty::ty_nil {
+        let seen = vec::any(pats, {|p|
+            alt raw_pat(p).node {
+              pat_lit(@{node: expr_lit(@{node: lit_nil, _}), _}) { true }
+              _ { false }
+            }
+        });
+        if !seen { tcx.sess.span_err(sp, "non-exhaustive patterns"); }
+      }
+      // Literal patterns are always considered non-exhaustive
+      _ {
+        tcx.sess.span_err(sp, "non-exhaustive literal patterns");
+      }
     }
-    // Otherwise, check subpatterns
-    // inefficient
-    for variant in variants {
-        // rows consists of the argument list for each pat that's an enum
-        let rows : [[@pat]] = [];
-        for pat in pats {
+}
+
+fn check_exhaustive_enum(tcx: ty::ctxt, enum_id: def_id, sp: span,
+                         pats: [@pat]) {
+    let variants = enum_variants(tcx, enum_id);
+    let columns_by_variant = vec::map(*variants, {|v|
+        {mutable seen: false,
+         cols: vec::init_elt_mut(v.args.len(), [])}
+    });
+
+    for pat in pats {
+        let pat = raw_pat(pat);
+        alt tcx.def_map.get(pat.id) {
+          def_variant(_, id) {
+            let variant_idx =
+                option::get(vec::position(*variants, {|v| v.id == id}));
+            columns_by_variant[variant_idx].seen = true;
             alt pat.node {
-               pat_enum(id, args) {
-                  alt tcx.def_map.find(pat.id) {
-                      some(def_variant(_,variant_id))
-                        if variant_id == variant.id { rows += [args]; }
-                      _ { }
-                  }
-               }
-               _ {}
+              pat_enum(_, args) {
+                vec::iteri(args) {|i, p|
+                    columns_by_variant[variant_idx].cols[i] += [p];
+                }
+              }
+              _ {}
             }
+          }
+          _ {}
         }
-        if check vec::is_not_empty(rows) {
-             let i = 0u;
-             for it in rows[0] {
-                let column = [it];
-                // Annoying -- see comment in
-                // tstate::states::find_pre_post_state_loop
-                check vec::is_not_empty(rows);
-                for row in vec::tail(rows) {
-                  column += [row[i]];
-                }
-                check_exhaustive(tcx, sp, pat_ty(tcx, it), column);
-                i += 1u;
-             }
+    }
+
+    vec::iteri(columns_by_variant) {|i, cv|
+        if !cv.seen {
+            tcx.sess.span_err(sp, "non-exhaustive patterns: variant `" +
+                              variants[i].name + "` not covered");
+        } else {
+            vec::iter(cv.cols) {|col| check_exhaustive(tcx, sp, col); }
         }
-        // This shouldn't actually happen, since there were no
-        // irrefutable patterns if we got here.
-        else { cont; }
     }
 }
 
diff --git a/src/comp/middle/lint.rs b/src/comp/middle/lint.rs
index ff1b97b9587..f46a50ea4a1 100644
--- a/src/comp/middle/lint.rs
+++ b/src/comp/middle/lint.rs
@@ -40,7 +40,7 @@ fn time(do_it: bool, what: str, thunk: fn()) {
 fn merge_opts(attrs: [ast::attribute], cmd_opts: [(option, bool)]) ->
     [(option, bool)] {
     fn str_to_option(name: str) -> (option, bool) {
-        ret alt name {
+        ret alt check name {
           "ctypes" { (ctypes, true) }
           "no_ctypes" { (ctypes, false) }
         }
diff --git a/src/comp/syntax/print/pprust.rs b/src/comp/syntax/print/pprust.rs
index 9cd9cd0503a..23cea66e8db 100644
--- a/src/comp/syntax/print/pprust.rs
+++ b/src/comp/syntax/print/pprust.rs
@@ -1023,7 +1023,7 @@ fn print_expr(s: ps, &&expr: @ast::expr) {
       }
       ast::expr_be(result) { word_nbsp(s, "be"); print_expr(s, result); }
       ast::expr_log(lvl, lexp, expr) {
-        alt lvl {
+        alt check lvl {
           1 { word_nbsp(s, "log"); print_expr(s, expr); }
           0 { word_nbsp(s, "log_err"); print_expr(s, expr); }
           2 {