Provide a witness pattern for non-exhaustive patterns

Fixed #4321

7 files changed, 486 insertions, 536 deletions

diff --git a/src/librustc/middle/check_match.rs b/src/librustc/middle/check_match.rs
index 8483ffaa438..44657147d05 100644
--- a/src/librustc/middle/check_match.rs
+++ b/src/librustc/middle/check_match.rs
@@ -10,23 +10,57 @@
 
 #![allow(non_camel_case_types)]
 
-use middle::const_eval::{compare_const_vals, lookup_const_by_id};
-use middle::const_eval::{eval_const_expr, const_val, const_bool, const_float};
+use middle::const_eval::{compare_const_vals, const_bool, const_float, const_val};
+use middle::const_eval::{eval_const_expr, lookup_const_by_id};
 use middle::def::*;
 use middle::pat_util::*;
 use middle::ty::*;
 use middle::ty;
-use util::ppaux::ty_to_str;
 
-use std::cmp;
 use std::gc::{Gc, GC};
 use std::iter;
 use syntax::ast::*;
 use syntax::ast_util::{is_unguarded, walk_pat};
-use syntax::codemap::{DUMMY_SP, Span};
-use syntax::parse::token;
+use syntax::codemap::{Span, Spanned, DUMMY_SP};
+use syntax::owned_slice::OwnedSlice;
+use syntax::print::pprust::pat_to_str;
 use syntax::visit;
 use syntax::visit::{Visitor, FnKind};
+use util::ppaux::ty_to_str;
+
+type Matrix = Vec<Vec<Gc<Pat>>>;
+
+#[deriving(Clone)]
+enum Usefulness {
+    Useful(Vec<Gc<Pat>>),
+    NotUseful
+}
+
+enum WitnessPreference {
+    ConstructWitness,
+    LeaveOutWitness
+}
+
+impl Usefulness {
+    fn useful(self) -> Option<Vec<Gc<Pat>>> {
+        match self {
+            Useful(pats) => Some(pats),
+            _ => None
+        }
+    }
+}
+
+fn def_to_path(tcx: &ty::ctxt, id: DefId) -> Path {
+    ty::with_path(tcx, id, |path| Path {
+        global: false,
+        segments: path.map(|elem| PathSegment {
+            identifier: Ident::new(elem.name()),
+            lifetimes: vec!(),
+            types: OwnedSlice::empty()
+        }).collect(),
+        span: DUMMY_SP,
+    })
+}
 
 struct MatchCheckCtxt<'a> {
     tcx: &'a ty::ctxt,
@@ -58,38 +92,38 @@ pub fn check_crate(tcx: &ty::ctxt,
 fn check_expr(cx: &mut MatchCheckCtxt, ex: &Expr) {
     visit::walk_expr(cx, ex, ());
     match ex.node {
-      ExprMatch(scrut, ref arms) => {
-        // First, check legality of move bindings.
-        for arm in arms.iter() {
-            check_legality_of_move_bindings(cx,
-                                            arm.guard.is_some(),
-                                            arm.pats.as_slice());
-        }
+        ExprMatch(scrut, ref arms) => {
+            // First, check legality of move bindings.
+            for arm in arms.iter() {
+                check_legality_of_move_bindings(cx,
+                                                arm.guard.is_some(),
+                                                arm.pats.as_slice());
+            }
 
-        check_arms(cx, arms.as_slice());
-        /* Check for exhaustiveness */
-         // Check for empty enum, because is_useful only works on inhabited
-         // types.
-       let pat_ty = node_id_to_type(cx.tcx, scrut.id);
-       if (*arms).is_empty() {
-           if !type_is_empty(cx.tcx, pat_ty) {
-               // We know the type is inhabited, so this must be wrong
-               cx.tcx.sess.span_err(ex.span, format!("non-exhaustive patterns: \
-                            type {} is non-empty",
-                            ty_to_str(cx.tcx, pat_ty)).as_slice());
-           }
-           // If the type *is* empty, it's vacuously exhaustive
-           return;
-       }
-       let m: matrix = arms
-          .iter()
-          .filter(|&arm| is_unguarded(arm))
-          .flat_map(|arm| arm.pats.iter())
-          .map(|pat| vec!(pat.clone()))
-          .collect();
-       check_exhaustive(cx, ex.span, &m);
-     }
-     _ => ()
+            check_arms(cx, arms.as_slice());
+            /* Check for exhaustiveness */
+             // Check for empty enum, because is_useful only works on inhabited
+             // types.
+            let pat_ty = node_id_to_type(cx.tcx, scrut.id);
+            if (*arms).is_empty() {
+               if !type_is_empty(cx.tcx, pat_ty) {
+                   // We know the type is inhabited, so this must be wrong
+                   cx.tcx.sess.span_err(ex.span, format!("non-exhaustive patterns: \
+                                type {} is non-empty",
+                                ty_to_str(cx.tcx, pat_ty)).as_slice());
+               }
+               // If the type *is* empty, it's vacuously exhaustive
+               return;
+            }
+            let m: Matrix = arms
+                .iter()
+                .filter(|&arm| is_unguarded(arm))
+                .flat_map(|arm| arm.pats.iter())
+                .map(|pat| vec!(pat.clone()))
+                .collect();
+            check_exhaustive(cx, ex.span, &m);
+        },
+        _ => ()
     }
 }
 
@@ -98,7 +132,6 @@ fn check_arms(cx: &MatchCheckCtxt, arms: &[Arm]) {
     let mut seen = Vec::new();
     for arm in arms.iter() {
         for pat in arm.pats.iter() {
-
             // Check that we do not match against a static NaN (#6804)
             let pat_matches_nan: |&Pat| -> bool = |p| {
                 let opt_def = cx.tcx.def_map.borrow().find_copy(&p.id);
@@ -123,11 +156,9 @@ fn check_arms(cx: &MatchCheckCtxt, arms: &[Arm]) {
             });
 
             let v = vec!(*pat);
-            match is_useful(cx, &seen, v.as_slice()) {
-              not_useful => {
-                cx.tcx.sess.span_err(pat.span, "unreachable pattern");
-              }
-              _ => ()
+            match is_useful(cx, &seen, v.as_slice(), LeaveOutWitness) {
+                NotUseful => cx.tcx.sess.span_err(pat.span, "unreachable pattern"),
+                _ => ()
             }
             if arm.guard.is_none() { seen.push(v); }
         }
@@ -136,71 +167,27 @@ fn check_arms(cx: &MatchCheckCtxt, arms: &[Arm]) {
 
 fn raw_pat(p: Gc<Pat>) -> Gc<Pat> {
     match p.node {
-      PatIdent(_, _, Some(s)) => { raw_pat(s) }
-      _ => { p }
+        PatIdent(_, _, Some(s)) => { raw_pat(s) }
+        _ => { p }
     }
 }
 
-fn check_exhaustive(cx: &MatchCheckCtxt, sp: Span, m: &matrix) {
-    let ext = match is_useful(cx, m, [wild()]) {
-        not_useful => {
+fn check_exhaustive(cx: &MatchCheckCtxt, sp: Span, m: &Matrix) {
+    match is_useful(cx, m, [wild()], ConstructWitness) {
+        NotUseful => {
             // This is good, wildcard pattern isn't reachable
             return;
         }
-        useful_ => None,
-        useful(ty, ref ctor) => {
-            match ty::get(ty).sty {
-                ty::ty_bool => {
-                    match *ctor {
-                        val(const_bool(true)) => Some("true".to_string()),
-                        val(const_bool(false)) => Some("false".to_string()),
-                        _ => None
-                    }
-                }
-                ty::ty_enum(id, _) => {
-                    let vid = match *ctor {
-                        variant(id) => id,
-                        _ => fail!("check_exhaustive: non-variant ctor"),
-                    };
-                    let variants = ty::enum_variants(cx.tcx, id);
-
-                    match variants.iter().find(|v| v.id == vid) {
-                        Some(v) => {
-                            Some(token::get_ident(v.name).get()
-                                                         .to_str()
-                                                         .into_string())
-                        }
-                        None => {
-                            fail!("check_exhaustive: bad variant in ctor")
-                        }
-                    }
-                }
-                ty::ty_vec(..) | ty::ty_rptr(..) => {
-                    match *ctor {
-                        vec(n) => {
-                            Some(format!("vectors of length {}", n))
-                        }
-                        _ => None
-                    }
-                }
-                _ => None
-            }
+        Useful(pats) => {
+            let witness = match pats.as_slice() {
+                [ref witness] => witness.clone(),
+                [] => wild(),
+                _ => unreachable!()
+            };
+            let msg = format!("non-exhaustive patterns: {0} not covered", pat_to_str(&*witness));
+            cx.tcx.sess.span_err(sp, msg.as_slice());
         }
-    };
-    let msg = format!("non-exhaustive patterns{}", match ext {
-        Some(ref s) => format!(": {} not covered", *s),
-        None => "".to_string()
-    });
-    cx.tcx.sess.span_err(sp, msg.as_slice());
-}
-
-type matrix = Vec<Vec<Gc<Pat>>>;
-
-#[deriving(Clone)]
-enum useful {
-    useful(ty::t, ctor),
-    useful_,
-    not_useful,
+    }
 }
 
 #[deriving(Clone, PartialEq)]
@@ -212,6 +199,129 @@ enum ctor {
     vec(uint)
 }
 
+fn const_val_to_expr(value: &const_val) -> Gc<Expr> {
+    let node = match value {
+        &const_bool(b) => LitBool(b),
+        _ => unreachable!()
+    };
+    box(GC) Expr {
+        id: 0,
+        node: ExprLit(box(GC) Spanned { node: node, span: DUMMY_SP }),
+        span: DUMMY_SP
+    }
+}
+
+fn construct_witness(cx: &MatchCheckCtxt, ctor: &ctor, pats: Vec<Gc<Pat>>, lty: ty::t) -> Gc<Pat> {
+    let pat = match ty::get(lty).sty {
+        ty::ty_tup(_) => PatTup(pats),
+
+        ty::ty_enum(_, _) => {
+            let vid = match ctor {
+                &variant(vid) => vid,
+                _ => unreachable!()
+            };
+            PatEnum(def_to_path(cx.tcx, vid), Some(pats))
+        },
+
+        ty::ty_struct(cid, _) => {
+            let fields = ty::lookup_struct_fields(cx.tcx, cid);
+            let field_pats = fields.move_iter()
+                .zip(pats.iter())
+                .map(|(field, pat)| FieldPat {
+                    ident: Ident::new(field.name),
+                    pat: pat.clone()
+                }).collect();
+            PatStruct(def_to_path(cx.tcx, cid), field_pats, false)
+        },
+
+        ty::ty_rptr(_, ty::mt { ty: ty, .. }) => {
+            match ty::get(ty).sty {
+                ty::ty_vec(_, None) => match ctor {
+                    &vec(_) => PatVec(pats, None, vec!()),
+                    _ => unreachable!()
+                },
+                _ => {
+                    assert_eq!(pats.len(), 1);
+                    PatRegion(pats.get(0).clone())
+                }
+            }
+        },
+
+        ty::ty_box(_) => {
+            assert_eq!(pats.len(), 1);
+            PatBox(pats.get(0).clone())
+        },
+
+        _ => {
+            match ctor {
+                &vec(_) => PatVec(pats, None, vec!()),
+                &val(ref v) => PatLit(const_val_to_expr(v)),
+                _ => PatWild
+            }
+        }
+    };
+
+    box(GC) Pat {
+        id: 0,
+        node: pat,
+        span: DUMMY_SP
+    }
+}
+
+fn missing_constructor(cx: &MatchCheckCtxt, m: &Matrix, left_ty: ty::t) -> Option<ctor> {
+    let used_constructors: Vec<ctor> = m.iter()
+        .filter_map(|r| pat_ctor_id(cx, left_ty, *r.get(0)))
+        .collect();
+
+    all_constructors(cx, m, left_ty)
+        .move_iter()
+        .find(|c| !used_constructors.contains(c))
+}
+
+fn all_constructors(cx: &MatchCheckCtxt, m: &Matrix, left_ty: ty::t) -> Vec<ctor> {
+    fn vec_constructors(m: &Matrix) -> Vec<ctor> {
+        let max_vec_len = m.iter().map(|r| match r.get(0).node {
+            PatVec(ref before, _, ref after) => before.len() + after.len(),
+            _ => 0u
+        }).max().unwrap_or(0u);
+        let contains_slice = m.iter().any(|r| match r.get(0).node {
+            PatVec(_, ref slice, _) => slice.is_some(),
+            _ => false
+        });
+        let lengths = iter::range_inclusive(0u, if contains_slice {
+            max_vec_len
+        } else {
+            max_vec_len + 1
+        });
+        lengths.map(|len| vec(len)).collect()
+    }
+
+    match ty::get(left_ty).sty {
+        ty::ty_bool =>
+            [true, false].iter().map(|b| val(const_bool(*b))).collect(),
+
+        ty::ty_rptr(_, ty::mt { ty: ty, .. }) => match ty::get(ty).sty {
+            ty::ty_vec(_, None) => vec_constructors(m),
+            _ => vec!(single)
+        },
+
+        ty::ty_enum(eid, _) =>
+            ty::enum_variants(cx.tcx, eid).iter().map(|va| variant(va.id)).collect(),
+
+        ty::ty_vec(_, None) =>
+            vec_constructors(m),
+
+        ty::ty_vec(_, Some(n)) =>
+            vec!(vec(n)),
+
+        ty::ty_nil if !m.iter().all(|r| is_wild(cx, *r.get(0))) =>
+            vec!(),
+
+        _ =>
+            vec!(single)
+    }
+}
+
 // Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html
 //
 // Whether a vector `v` of patterns is 'useful' in relation to a set of such
@@ -225,12 +335,13 @@ enum ctor {
 
 // Note: is_useful doesn't work on empty types, as the paper notes.
 // So it assumes that v is non-empty.
-fn is_useful(cx: &MatchCheckCtxt, m: &matrix, v: &[Gc<Pat>]) -> useful {
+fn is_useful(cx: &MatchCheckCtxt, m: &Matrix, v: &[Gc<Pat>],
+             witness: WitnessPreference) -> Usefulness {
     if m.len() == 0u {
-        return useful_;
+        return Useful(vec!());
     }
     if m.get(0).len() == 0u {
-        return not_useful
+        return NotUseful;
     }
     let real_pat = match m.iter().find(|r| r.get(0).id != 0) {
         Some(r) => {
@@ -241,310 +352,146 @@ fn is_useful(cx: &MatchCheckCtxt, m: &matrix, v: &[Gc<Pat>]) -> useful {
                 _ => *r.get(0)
             }
         }
-        None if v.len() == 0 => return not_useful,
+        None if v.len() == 0 => return NotUseful,
         None => v[0]
     };
-    let left_ty = if real_pat.id == 0 { ty::mk_nil() }
-                  else { ty::node_id_to_type(cx.tcx, real_pat.id) };
-
-    match pat_ctor_id(cx, v[0]) {
-      None => {
-        match missing_ctor(cx, m, left_ty) {
-          None => {
-            match ty::get(left_ty).sty {
-              ty::ty_bool => {
-                  match is_useful_specialized(cx, m, v,
-                                              val(const_bool(true)),
-                                              0u, left_ty){
-                      not_useful => {
-                          is_useful_specialized(cx, m, v,
-                                                val(const_bool(false)),
-                                                0u, left_ty)
-                      }
-                      u => u,
-                  }
-              }
-              ty::ty_enum(eid, _) => {
-                  for va in (*ty::enum_variants(cx.tcx, eid)).iter() {
-                      match is_useful_specialized(cx, m, v, variant(va.id),
-                                                  va.args.len(), left_ty) {
-                        not_useful => (),
-                        u => return u,
-                      }
-                  }
-                  not_useful
-              }
-              ty::ty_vec(_, Some(n)) => {
-                  is_useful_specialized(cx, m, v, vec(n), n, left_ty)
-              }
-              ty::ty_vec(..) => fail!("impossible case"),
-              ty::ty_rptr(_, ty::mt{ty: ty, ..}) | ty::ty_uniq(ty) => match ty::get(ty).sty {
-                  ty::ty_vec(_, None) => {
-                      let max_len = m.iter().rev().fold(0, |max_len, r| {
-                          match r.get(0).node {
-                              PatVec(ref before, _, ref after) => {
-                                  cmp::max(before.len() + after.len(), max_len)
-                              }
-                              _ => max_len
-                          }
-                      });
-                      for n in iter::range(0u, max_len + 1) {
-                          match is_useful_specialized(cx, m, v, vec(n), n, left_ty) {
-                              not_useful => (),
-                              u => return u,
-                          }
-                      }
-                      not_useful
-                  }
-                  _ => {
-                      let arity = ctor_arity(cx, &single, left_ty);
-                      is_useful_specialized(cx, m, v, single, arity, left_ty)
-                  }
-              },
-              _ => {
-                  let arity = ctor_arity(cx, &single, left_ty);
-                  is_useful_specialized(cx, m, v, single, arity, left_ty)
-              }
-            }
-          }
-          Some(ctor) => {
-            match is_useful(cx,
-                            &m.iter().filter_map(|r| {
-                                default(cx, r.as_slice())
-                            }).collect::<matrix>(),
-                            v.tail()) {
-              useful_ => useful(left_ty, ctor),
-              u => u,
+    let left_ty = if real_pat.id == 0 {
+        ty::mk_nil()
+    } else {
+        ty::pat_ty(cx.tcx, &*real_pat)
+    };
+
+    match pat_ctor_id(cx, left_ty, v[0]) {
+        None => match missing_constructor(cx, m, left_ty) {
+            None => {
+                all_constructors(cx, m, left_ty).move_iter().filter_map(|c| {
+                    is_useful_specialized(cx, m, v, c.clone(),
+                                          left_ty, witness).useful().map(|pats| {
+                        Useful(match witness {
+                            ConstructWitness => {
+                                let arity = constructor_arity(cx, &c, left_ty);
+                                let subpats = {
+                                    let pat_slice = pats.as_slice();
+                                    Vec::from_fn(arity, |i| {
+                                        pat_slice.get(i).map(|p| p.clone())
+                                            .unwrap_or_else(|| wild())
+                                    })
+                                };
+                                let mut result = vec!(construct_witness(cx, &c, subpats, left_ty));
+                                result.extend(pats.move_iter().skip(arity));
+                                result
+                            }
+                            LeaveOutWitness => vec!()
+                        })
+                    })
+                }).nth(0).unwrap_or(NotUseful)
+            },
+
+            Some(ctor) => {
+                let matrix = &m.iter().filter_map(|r| default(cx, r.as_slice())).collect();
+                match is_useful(cx, matrix, v.tail(), witness) {
+                    Useful(pats) => Useful(match witness {
+                        ConstructWitness => {
+                            let arity = constructor_arity(cx, &ctor, left_ty);
+                            let wild_pats = Vec::from_elem(arity, wild());
+                            let enum_pat = construct_witness(cx, &ctor, wild_pats, left_ty);
+                            (vec!(enum_pat)).append(pats.as_slice())
+                        }
+                        LeaveOutWitness => vec!()
+                    }),
+                    result => result
+                }
             }
-          }
-        }
-      }
-      Some(v0_ctor) => {
-        let arity = ctor_arity(cx, &v0_ctor, left_ty);
-        is_useful_specialized(cx, m, v, v0_ctor, arity, left_ty)
-      }
+        },
+
+        Some(v0_ctor) => is_useful_specialized(cx, m, v, v0_ctor, left_ty, witness)
     }
 }
 
-fn is_useful_specialized(cx: &MatchCheckCtxt,
-                             m: &matrix,
-                             v: &[Gc<Pat>],
-                             ctor: ctor,
-                             arity: uint,
-                             lty: ty::t)
-                             -> useful {
-    let ms = m.iter().filter_map(|r| {
-        specialize(cx, r.as_slice(), &ctor, arity, lty)
-    }).collect::<matrix>();
-    let could_be_useful = match specialize(cx, v, &ctor, arity, lty) {
-        Some(v) => is_useful(cx, &ms, v.as_slice()),
-        None => return not_useful,
-    };
-    match could_be_useful {
-      useful_ => useful(lty, ctor),
-      u => u,
+fn is_useful_specialized(cx: &MatchCheckCtxt, m: &Matrix, v: &[Gc<Pat>],
+                         ctor: ctor, lty: ty::t, witness: WitnessPreference) -> Usefulness {
+    let arity = constructor_arity(cx, &ctor, lty);
+    let matrix = m.iter().filter_map(|r| {
+        specialize(cx, r.as_slice(), &ctor, arity)
+    }).collect();
+    match specialize(cx, v, &ctor, arity) {
+        Some(v) => is_useful(cx, &matrix, v.as_slice(), witness),
+        None => NotUseful
     }
 }
 
-fn pat_ctor_id(cx: &MatchCheckCtxt, p: Gc<Pat>) -> Option<ctor> {
+fn pat_ctor_id(cx: &MatchCheckCtxt, left_ty: ty::t, p: Gc<Pat>) -> Option<ctor> {
     let pat = raw_pat(p);
     match pat.node {
-      PatWild | PatWildMulti => { None }
-      PatIdent(_, _, _) | PatEnum(_, _) => {
-        let opt_def = cx.tcx.def_map.borrow().find_copy(&pat.id);
-        match opt_def {
-          Some(DefVariant(_, id, _)) => Some(variant(id)),
-          Some(DefStatic(did, false)) => {
-            let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
-            Some(val(eval_const_expr(cx.tcx, &*const_expr)))
-          }
-          _ => None
-        }
-      }
-      PatLit(ref expr) => { Some(val(eval_const_expr(cx.tcx, &**expr))) }
-      PatRange(ref lo, ref hi) => {
-        Some(range(eval_const_expr(cx.tcx, &**lo), eval_const_expr(cx.tcx, &**hi)))
-      }
-      PatStruct(..) => {
-        match cx.tcx.def_map.borrow().find(&pat.id) {
-          Some(&DefVariant(_, id, _)) => Some(variant(id)),
-          _ => Some(single)
-        }
-      }
-      PatBox(_) | PatTup(_) | PatRegion(..) => {
-        Some(single)
-      }
-      PatVec(ref before, slice, ref after) => {
-        match slice {
-          Some(_) => None,
-          None => Some(vec(before.len() + after.len()))
-        }
-      }
-      PatMac(_) => cx.tcx.sess.bug("unexpanded macro"),
+        PatIdent(..) | PatEnum(..) | PatStruct(..) =>
+            match cx.tcx.def_map.borrow().find(&pat.id) {
+                Some(&DefStatic(did, false)) => {
+                    let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
+                    Some(val(eval_const_expr(cx.tcx, &*const_expr)))
+                },
+                Some(&DefVariant(_, id, _)) =>
+                    Some(variant(id)),
+                _ => match pat.node {
+                    PatEnum(..) | PatStruct(..) => Some(single),
+                    PatIdent(..) => None,
+                    _ => unreachable!()
+                }
+            },
+        PatLit(expr) =>
+            Some(val(eval_const_expr(cx.tcx, &*expr))),
+        PatRange(lo, hi) =>
+            Some(range(eval_const_expr(cx.tcx, &*lo), eval_const_expr(cx.tcx, &*hi))),
+        PatVec(ref before, _, ref after) => match ty::get(left_ty).sty {
+            ty::ty_vec(_, Some(n)) =>
+                Some(vec(n)),
+            _ =>
+                Some(vec(before.len() + after.len()))
+        },
+        PatBox(_) | PatTup(_) | PatRegion(..) =>
+            Some(single),
+        PatWild | PatWildMulti =>
+            None,
+        PatMac(_) =>
+            cx.tcx.sess.bug("unexpanded macro")
     }
 }
 
 fn is_wild(cx: &MatchCheckCtxt, p: Gc<Pat>) -> bool {
     let pat = raw_pat(p);
     match pat.node {
-      PatWild | PatWildMulti => { true }
-      PatIdent(_, _, _) => {
-        match cx.tcx.def_map.borrow().find(&pat.id) {
-          Some(&DefVariant(_, _, _)) | Some(&DefStatic(..)) => { false }
-          _ => { true }
-        }
-      }
-      _ => { false }
-    }
-}
-
-fn missing_ctor(cx: &MatchCheckCtxt,
-                m: &matrix,
-                left_ty: ty::t)
-                -> Option<ctor> {
-    return match ty::get(left_ty).sty {
-      ty::ty_box(_) | ty::ty_tup(_) |
-      ty::ty_struct(..) => check_matrix_for_wild(cx, m),
-      ty::ty_uniq(ty) | ty::ty_rptr(_, ty::mt{ty: ty, ..}) => match ty::get(ty).sty {
-          ty::ty_vec(_, None) => ctor_for_slice(m),
-          ty::ty_str => Some(single),
-          _ => check_matrix_for_wild(cx, m),
-      },
-      ty::ty_enum(eid, _) => {
-        let pat_ctors: Vec<ctor> = m
-          .iter()
-          .filter_map(|r| pat_ctor_id(cx, *r.get(0)))
-          .collect();
-        let variants = ty::enum_variants(cx.tcx, eid);
-        variants.iter().map(|v| variant(v.id)).find(|c| !pat_ctors.contains(c))
-      }
-      ty::ty_nil => None,
-      ty::ty_bool => {
-        let mut true_found = false;
-        let mut false_found = false;
-        for r in m.iter() {
-            match pat_ctor_id(cx, *r.get(0)) {
-              None => (),
-              Some(val(const_bool(true))) => true_found = true,
-              Some(val(const_bool(false))) => false_found = true,
-              _ => fail!("impossible case")
-            }
-        }
-        if true_found && false_found { None }
-        else if true_found { Some(val(const_bool(false))) }
-        else { Some(val(const_bool(true))) }
-      }
-      ty::ty_vec(_, Some(n)) => {
-        let mut missing = true;
-        let mut wrong = false;
-        for r in m.iter() {
-          match r.get(0).node {
-            PatVec(ref before, ref slice, ref after) => {
-              let count = before.len() + after.len();
-              if (count < n && slice.is_none()) || count > n {
-                wrong = true;
-              }
-              if count == n || (count < n && slice.is_some()) {
-                missing = false;
-              }
+        PatWild | PatWildMulti => true,
+        PatIdent(_, _, _) => {
+            match cx.tcx.def_map.borrow().find(&pat.id) {
+                Some(&DefVariant(_, _, _)) | Some(&DefStatic(..)) => false,
+                _ => true
             }
-            _ => {}
-          }
-        }
-        match (wrong, missing) {
-          (true, _) => Some(vec(n)), // should be compile-time error
-          (_, true) => Some(vec(n)),
-          _         => None
-        }
-      }
-      ty::ty_vec(..) => fail!("impossible case"),
-      _ => Some(single)
-    };
-
-    fn check_matrix_for_wild(cx: &MatchCheckCtxt, m: &matrix) -> Option<ctor> {
-        for r in m.iter() {
-            if !is_wild(cx, *r.get(0)) { return None; }
-        }
-        return Some(single);
-    }
-
-    // For slice and ~[T].
-    fn ctor_for_slice(m: &matrix) -> Option<ctor> {
-        // Find the lengths and slices of all vector patterns.
-        let mut vec_pat_lens = m.iter().filter_map(|r| {
-            match r.get(0).node {
-                PatVec(ref before, ref slice, ref after) => {
-                    Some((before.len() + after.len(), slice.is_some()))
-                }
-                _ => None
-            }
-        }).collect::<Vec<(uint, bool)> >();
-
-        // Sort them by length such that for patterns of the same length,
-        // those with a destructured slice come first.
-        vec_pat_lens.sort_by(|&(len1, slice1), &(len2, slice2)| {
-                    if len1 == len2 {
-                        slice2.cmp(&slice1)
-                    } else {
-                        len1.cmp(&len2)
-                    }
-                });
-        vec_pat_lens.dedup();
-
-        let mut found_slice = false;
-        let mut next = 0;
-        let mut missing = None;
-        for &(length, slice) in vec_pat_lens.iter() {
-            if length != next {
-                missing = Some(next);
-                break;
-            }
-            if slice {
-                found_slice = true;
-                break;
-            }
-            next += 1;
-        }
-
-        // We found patterns of all lengths within <0, next), yet there was no
-        // pattern with a slice - therefore, we report vec(next) as missing.
-        if !found_slice {
-            missing = Some(next);
-        }
-        match missing {
-          Some(k) => Some(vec(k)),
-          None => None
         }
+        _ => false
     }
 }
 
-fn ctor_arity(cx: &MatchCheckCtxt, ctor: &ctor, ty: ty::t) -> uint {
-    fn vec_ctor_arity(ctor: &ctor) -> uint {
-        match *ctor {
-            vec(n) => n,
-            _ => 0u
-        }
-    }
-
+fn constructor_arity(cx: &MatchCheckCtxt, ctor: &ctor, ty: ty::t) -> uint {
     match ty::get(ty).sty {
         ty::ty_tup(ref fs) => fs.len(),
-        ty::ty_box(_) => 1u,
-        ty::ty_uniq(ty) | ty::ty_rptr(_, ty::mt{ty: ty, ..}) => match ty::get(ty).sty {
-            ty::ty_vec(_, None) => vec_ctor_arity(ctor),
-            _ => 1u,
+        ty::ty_box(_) | ty::ty_uniq(_) => 1u,
+        ty::ty_rptr(_, ty::mt { ty: ty, .. }) => match ty::get(ty).sty {
+            ty::ty_vec(_, None) => match *ctor {
+                vec(n) => n,
+                _ => 0u
+            },
+            _ => 1u
         },
         ty::ty_enum(eid, _) => {
-            let id = match *ctor {
-                variant(id) => id,
-                _ => fail!("impossible case")
-            };
-            match ty::enum_variants(cx.tcx, eid).iter().find(|v| v.id == id ) {
-                Some(v) => v.args.len(),
-                None => fail!("impossible case")
+            match *ctor {
+                variant(id) => enum_variant_with_id(cx.tcx, eid, id).args.len(),
+                _ => unreachable!()
             }
         }
         ty::ty_struct(cid, _) => ty::lookup_struct_fields(cx.tcx, cid).len(),
-        ty::ty_vec(_, Some(_)) => vec_ctor_arity(ctor),
+        ty::ty_vec(_, _) => match *ctor {
+            vec(n) => n,
+            _ => 0u
+        },
         _ => 0u
     }
 }
@@ -553,10 +500,6 @@ fn wild() -> Gc<Pat> {
     box(GC) Pat {id: 0, node: PatWild, span: DUMMY_SP}
 }
 
-fn wild_multi() -> Gc<Pat> {
-    box(GC) Pat {id: 0, node: PatWildMulti, span: DUMMY_SP}
-}
-
 fn range_covered_by_constructor(ctor_id: &ctor, from: &const_val, to: &const_val) -> Option<bool> {
     let (c_from, c_to) = match *ctor_id {
         val(ref value)          => (value, value),
@@ -572,164 +515,153 @@ fn range_covered_by_constructor(ctor_id: &ctor, from: &const_val, to: &const_val
     }
 }
 
-fn specialize(cx: &MatchCheckCtxt,
-                  r: &[Gc<Pat>],
-                  ctor_id: &ctor,
-                  arity: uint,
-                  left_ty: ty::t)
-               -> Option<Vec<Gc<Pat>>> {
-    let &Pat{id: ref pat_id, node: ref n, span: ref pat_span} = &(*raw_pat(r[0]));
+fn specialize(cx: &MatchCheckCtxt, r: &[Gc<Pat>],
+              ctor_id: &ctor, arity: uint) -> Option<Vec<Gc<Pat>>> {
+    let &Pat {
+        id: ref pat_id, node: ref n, span: ref pat_span
+    } = &(*raw_pat(r[0]));
     let head: Option<Vec<Gc<Pat>>> = match n {
-            &PatWild => {
-                Some(Vec::from_elem(arity, wild()))
-            }
-            &PatWildMulti => {
-                Some(Vec::from_elem(arity, wild_multi()))
-            }
-            &PatIdent(_, _, _) => {
-                let opt_def = cx.tcx.def_map.borrow().find_copy(pat_id);
-                match opt_def {
-                    Some(DefVariant(_, id, _)) => {
-                        if variant(id) == *ctor_id {
-                            Some(vec!())
-                        } else {
-                            None
-                        }
+        &PatWild => {
+            Some(Vec::from_elem(arity, wild()))
+        }
+        &PatWildMulti => {
+            Some(Vec::from_elem(arity, wild()))
+        }
+        &PatIdent(_, _, _) => {
+            let opt_def = cx.tcx.def_map.borrow().find_copy(pat_id);
+            match opt_def {
+                Some(DefVariant(_, id, _)) => {
+                    if variant(id) == *ctor_id {
+                        Some(vec!())
+                    } else {
+                        None
                     }
-                    Some(DefStatic(did, _)) => {
-                        let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
-                        let e_v = eval_const_expr(cx.tcx, &*const_expr);
-                        match range_covered_by_constructor(ctor_id, &e_v, &e_v) {
-                           Some(true) => Some(vec!()),
-                           Some(false) => None,
-                           None => {
-                              cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
-                              None
-                           }
+                }
+                Some(DefStatic(did, _)) => {
+                    let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
+                    let e_v = eval_const_expr(cx.tcx, &*const_expr);
+                    match range_covered_by_constructor(ctor_id, &e_v, &e_v) {
+                        Some(true) => Some(vec!()),
+                        Some(false) => None,
+                        None => {
+                            cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
+                            None
                         }
                     }
-                    _ => {
-                        Some(Vec::from_elem(arity, wild()))
-                    }
+                }
+                _ => {
+                    Some(Vec::from_elem(arity, wild()))
                 }
             }
-            &PatEnum(_, ref args) => {
-                let def = cx.tcx.def_map.borrow().get_copy(pat_id);
-                match def {
-                    DefStatic(did, _) => {
-                        let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
-                        let e_v = eval_const_expr(cx.tcx, &*const_expr);
-                        match range_covered_by_constructor(ctor_id, &e_v, &e_v) {
-                           Some(true) => Some(vec!()),
-                           Some(false) => None,
-                           None => {
-                              cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
-                              None
-                           }
+        }
+        &PatEnum(_, ref args) => {
+            let def = cx.tcx.def_map.borrow().get_copy(pat_id);
+            match def {
+                DefStatic(did, _) => {
+                    let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
+                    let e_v = eval_const_expr(cx.tcx, &*const_expr);
+                    match range_covered_by_constructor(ctor_id, &e_v, &e_v) {
+                        Some(true) => Some(vec!()),
+                        Some(false) => None,
+                        None => {
+                            cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
+                            None
                         }
                     }
-                    DefVariant(_, id, _) if variant(id) != *ctor_id => None,
-                    DefVariant(..) | DefFn(..) | DefStruct(..) => {
-                        Some(match args {
-                            &Some(ref args) => args.clone(),
-                            &None => Vec::from_elem(arity, wild())
-                        })
-                    }
-                    _ => None
                 }
+                DefVariant(_, id, _) if variant(id) != *ctor_id => None,
+                DefVariant(..) | DefFn(..) | DefStruct(..) => {
+                    Some(match args {
+                        &Some(ref args) => args.clone(),
+                        &None => Vec::from_elem(arity, wild())
+                    })
+                }
+                _ => None
             }
-            &PatStruct(_, ref pattern_fields, _) => {
-                // Is this a struct or an enum variant?
-                let def = cx.tcx.def_map.borrow().get_copy(pat_id);
-                let class_id = match def {
-                    DefVariant(_, variant_id, _) => {
-                      if variant(variant_id) == *ctor_id {
-                        Some(variant_id)
-                      } else {
-                        None
-                      }
-                    }
-                    _ => {
-                        match ty::get(left_ty).sty {
-                            ty::ty_struct(cid, _) => Some(cid),
-                            _ => {
-                                cx.tcx.sess.span_bug(
-                                    *pat_span,
-                                    format!("struct pattern resolved to {}, \
-                                          not a struct",
-                                         ty_to_str(cx.tcx,
-                                                   left_ty)).as_slice());
-                            }
-                        }
+        }
+
+        &PatStruct(_, ref pattern_fields, _) => {
+            // Is this a struct or an enum variant?
+            let def = cx.tcx.def_map.borrow().get_copy(pat_id);
+            let class_id = match def {
+                DefVariant(_, variant_id, _) => if variant(variant_id) == *ctor_id {
+                    Some(variant_id)
+                } else {
+                    None
+                },
+                DefStruct(struct_id) => Some(struct_id),
+                _ => None
+            };
+            class_id.map(|variant_id| {
+                let struct_fields = ty::lookup_struct_fields(cx.tcx, variant_id);
+                let args = struct_fields.iter().map(|sf| {
+                    match pattern_fields.iter().find(|f| f.ident.name == sf.name) {
+                        Some(f) => f.pat,
+                        _ => wild()
                     }
-                };
-                class_id.map(|variant_id| {
-                  let struct_fields = ty::lookup_struct_fields(cx.tcx, variant_id);
-                  let args = struct_fields.iter().map(|sf| {
-                      match pattern_fields.iter().find(|f| f.ident.name == sf.name) {
-                          Some(f) => f.pat,
-                          _ => wild()
-                      }
-                  }).collect();
-                  args
-                })
+                }).collect();
+                args
+            })
+        }
 
-            }
-            &PatTup(ref args) => {
-                Some(args.clone())
-            }
-            &PatBox(ref inner) | &PatRegion(ref inner) => {
-                Some(vec!(inner.clone()))
-            }
-            &PatLit(ref expr) => {
-              let expr_value = eval_const_expr(cx.tcx, &**expr);
-              match range_covered_by_constructor(ctor_id, &expr_value, &expr_value) {
-                 Some(true) => Some(vec!()),
-                 Some(false) => None,
-                 None => {
+        &PatTup(ref args) =>
+            Some(args.clone()),
+
+        &PatBox(ref inner) | &PatRegion(ref inner) =>
+            Some(vec!(inner.clone())),
+
+        &PatLit(ref expr) => {
+            let expr_value = eval_const_expr(cx.tcx, &**expr);
+            match range_covered_by_constructor(ctor_id, &expr_value, &expr_value) {
+                Some(true) => Some(vec!()),
+                Some(false) => None,
+                None => {
                     cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
                     None
-                 }
-              }
+                }
             }
-            &PatRange(ref from, ref to) => {
-              let from_value = eval_const_expr(cx.tcx, &**from);
-              let to_value = eval_const_expr(cx.tcx, &**to);
-              match range_covered_by_constructor(ctor_id, &from_value, &to_value) {
-                 Some(true) => Some(vec!()),
-                 Some(false) => None,
-                 None => {
+        }
+
+        &PatRange(ref from, ref to) => {
+            let from_value = eval_const_expr(cx.tcx, &**from);
+            let to_value = eval_const_expr(cx.tcx, &**to);
+            match range_covered_by_constructor(ctor_id, &from_value, &to_value) {
+                Some(true) => Some(vec!()),
+                Some(false) => None,
+                None => {
                     cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
                     None
-                 }
-              }
+                }
             }
-            &PatVec(ref before, ref slice, ref after) => {
-                match *ctor_id {
-                    vec(_) => {
-                        let num_elements = before.len() + after.len();
-                        if num_elements < arity && slice.is_some() {
-                            let mut result = Vec::new();
-                            result.push_all(before.as_slice());
-                            result.grow_fn(arity - num_elements, |_| wild());
-                            result.push_all(after.as_slice());
-                            Some(result)
-                        } else if num_elements == arity {
-                            let mut result = Vec::new();
-                            result.push_all(before.as_slice());
-                            result.push_all(after.as_slice());
-                            Some(result)
-                        } else {
-                            None
-                        }
+        }
+
+        &PatVec(ref before, ref slice, ref after) => {
+            match *ctor_id {
+                vec(_) => {
+                    let num_elements = before.len() + after.len();
+                    if num_elements < arity && slice.is_some() {
+                        let mut result = Vec::new();
+                        result.push_all(before.as_slice());
+                        result.grow_fn(arity - num_elements, |_| wild());
+                        result.push_all(after.as_slice());
+                        Some(result)
+                    } else if num_elements == arity {
+                        let mut result = Vec::new();
+                        result.push_all(before.as_slice());
+                        result.push_all(after.as_slice());
+                        Some(result)
+                    } else {
+                        None
                     }
-                    _ => None
                 }
+                _ => None
             }
-            &PatMac(_) => {
-                cx.tcx.sess.span_err(*pat_span, "unexpanded macro");
-                None
-            }
+        }
+
+        &PatMac(_) => {
+            cx.tcx.sess.span_err(*pat_span, "unexpanded macro");
+            None
+        }
     };
     head.map(|head| head.append(r.tail()))
 }
@@ -787,7 +719,7 @@ fn check_fn(cx: &mut MatchCheckCtxt,
 
 fn is_refutable(cx: &MatchCheckCtxt, pat: Gc<Pat>) -> Option<Gc<Pat>> {
     let pats = vec!(vec!(pat));
-    is_useful(cx, &pats, [wild()])
+    is_useful(cx, &pats, [wild()], ConstructWitness)
         .useful()
         .map(|pats| {
             assert_eq!(pats.len(), 1);
diff --git a/src/test/compile-fail/issue-2111.rs b/src/test/compile-fail/issue-2111.rs
index 40010b203aa..98eb62fe392 100644
--- a/src/test/compile-fail/issue-2111.rs
+++ b/src/test/compile-fail/issue-2111.rs
@@ -9,7 +9,8 @@
 // except according to those terms.
 
 fn foo(a: Option<uint>, b: Option<uint>) {
-  match (a,b) { //~ ERROR: non-exhaustive patterns: None not covered
+  match (a,b) {
+  //~^ ERROR: non-exhaustive patterns: (core::option::None, core::option::None) not covered
     (Some(a), Some(b)) if a == b => { }
     (Some(_), None) |
     (None, Some(_)) => { }
diff --git a/src/test/compile-fail/issue-4321.rs b/src/test/compile-fail/issue-4321.rs
new file mode 100644
index 00000000000..660183366e8
--- /dev/null
+++ b/src/test/compile-fail/issue-4321.rs
@@ -0,0 +1,18 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+fn main() {
+    let tup = (true, true);
+    println!("foo {:}", match tup { //~ ERROR non-exhaustive patterns: (true, false) not covered
+        (false, false) => "foo",
+        (false, true) => "bar",
+        (true, true) => "baz"
+    });
+}
diff --git a/src/test/compile-fail/non-exhaustive-match-nested.rs b/src/test/compile-fail/non-exhaustive-match-nested.rs
index 102772f79d5..bb5b2e750d5 100644
--- a/src/test/compile-fail/non-exhaustive-match-nested.rs
+++ b/src/test/compile-fail/non-exhaustive-match-nested.rs
@@ -8,13 +8,12 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-// error-pattern: non-exhaustive patterns
 enum t { a(u), b }
 enum u { c, d }
 
 fn main() {
   let x = a(c);
-  match x {
+  match x { //~ ERROR non-exhaustive patterns: a(c) not covered
       a(d) => { fail!("hello"); }
       b => { fail!("goodbye"); }
     }
diff --git a/src/test/compile-fail/non-exhaustive-match.rs b/src/test/compile-fail/non-exhaustive-match.rs
index a07fec853fc..97b65a305e0 100644
--- a/src/test/compile-fail/non-exhaustive-match.rs
+++ b/src/test/compile-fail/non-exhaustive-match.rs
@@ -12,21 +12,21 @@ enum t { a, b, }
 
 fn main() {
     let x = a;
-    match x { b => { } } //~ ERROR non-exhaustive patterns
-    match true { //~ ERROR non-exhaustive patterns
+    match x { b => { } } //~ ERROR non-exhaustive patterns: a not covered
+    match true { //~ ERROR non-exhaustive patterns: false not covered
       true => {}
     }
-    match Some(10) { //~ ERROR non-exhaustive patterns
+    match Some(10) { //~ ERROR non-exhaustive patterns: core::option::Some(_) not covered
       None => {}
     }
-    match (2, 3, 4) { //~ ERROR non-exhaustive patterns
+    match (2, 3, 4) { //~ ERROR non-exhaustive patterns: (_, _, _) not covered
       (_, _, 4) => {}
     }
-    match (a, a) { //~ ERROR non-exhaustive patterns
+    match (a, a) { //~ ERROR non-exhaustive patterns: (a, a) not covered
       (a, b) => {}
       (b, a) => {}
     }
-    match a { //~ ERROR b not covered
+    match a { //~ ERROR non-exhaustive patterns: b not covered
       a => {}
     }
     // This is exhaustive, though the algorithm got it wrong at one point
@@ -37,8 +37,7 @@ fn main() {
     }
     let vec = vec!(Some(42), None, Some(21));
     let vec: &[Option<int>] = vec.as_slice();
-    match vec {
-        //~^ ERROR non-exhaustive patterns: vectors of length 0 not covered
+    match vec { //~ ERROR non-exhaustive patterns: [] not covered
         [Some(..), None, ..tail] => {}
         [Some(..), Some(..), ..tail] => {}
         [None] => {}
@@ -51,7 +50,7 @@ fn main() {
     }
     let vec = vec!(0.5);
     let vec: &[f32] = vec.as_slice();
-    match vec { //~ ERROR non-exhaustive patterns: vectors of length 4 not covered
+    match vec { //~ ERROR non-exhaustive patterns: [_, _, _, _] not covered
         [0.1, 0.2, 0.3] => (),
         [0.1, 0.2] => (),
         [0.1] => (),
diff --git a/src/test/compile-fail/refutable-pattern-errors.rs b/src/test/compile-fail/refutable-pattern-errors.rs
index 38b9b888e06..d664ea10b98 100644
--- a/src/test/compile-fail/refutable-pattern-errors.rs
+++ b/src/test/compile-fail/refutable-pattern-errors.rs
@@ -10,9 +10,9 @@
 
 
 fn func((1, (Some(1), 2..3)): (int, (Option<int>, int))) { }
-//~^ ERROR refutable pattern in function argument
+//~^ ERROR refutable pattern in function argument: (_, _) not covered
 
 fn main() {
     let (1, (Some(1), 2..3)) = (1, (None, 2));
-    //~^ ERROR refutable pattern in local binding
+    //~^ ERROR refutable pattern in local binding: (_, _) not covered
 }
diff --git a/src/test/compile-fail/refutable-pattern-in-fn-arg.rs b/src/test/compile-fail/refutable-pattern-in-fn-arg.rs
index d5489b6a852..064957979f7 100644
--- a/src/test/compile-fail/refutable-pattern-in-fn-arg.rs
+++ b/src/test/compile-fail/refutable-pattern-in-fn-arg.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 fn main() {
-    let f = |3: int| println!("hello");  //~ ERROR refutable pattern
+    let f = |3: int| println!("hello");
+    //~^ ERROR refutable pattern in function argument: _ not covered
     f(4);
 }