src/librustc/middle/check_match.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 #![allow(non_camel_case_types)]
  12
  13 use middle::const_eval::{compare_const_vals, const_bool, const_float, const_val};
  14 use middle::const_eval::{eval_const_expr, lookup_const_by_id};
  15 use middle::def::*;
  16 use middle::pat_util::*;
  17 use middle::ty::*;
  18 use middle::ty;
  19
  20 use std::gc::{Gc, GC};
  21 use std::iter;
  22 use syntax::ast::*;
  23 use syntax::ast_util::{is_unguarded, walk_pat};
  24 use syntax::codemap::{Span, Spanned, DUMMY_SP};
  25 use syntax::owned_slice::OwnedSlice;
  26 use syntax::print::pprust::pat_to_str;
  27 use syntax::visit;
  28 use syntax::visit::{Visitor, FnKind};
  29 use util::ppaux::ty_to_str;
  30
  31 type Matrix = Vec<Vec<Gc<Pat>>>;
  32
  33 #[deriving(Clone)]
  34 enum Usefulness {
  35     Useful(Vec<Gc<Pat>>),
  36     NotUseful
  37 }
  38
  39 enum WitnessPreference {
  40     ConstructWitness,
  41     LeaveOutWitness
  42 }
  43
  44 impl Usefulness {
  45     fn useful(self) -> Option<Vec<Gc<Pat>>> {
  46         match self {
  47             Useful(pats) => Some(pats),
  48             _ => None
  49         }
  50     }
  51 }
  52
  53 fn def_to_path(tcx: &ty::ctxt, id: DefId) -> Path {
  54     ty::with_path(tcx, id, |mut path| Path {
  55         global: false,
  56         segments: path.last().map(|elem| PathSegment {
  57             identifier: Ident::new(elem.name()),
  58             lifetimes: vec!(),
  59             types: OwnedSlice::empty()
  60         }).move_iter().collect(),
  61         span: DUMMY_SP,
  62     })
  63 }
  64
  65 struct MatchCheckCtxt<'a> {
  66     tcx: &'a ty::ctxt,
  67 }
  68
  69 impl<'a> Visitor<()> for MatchCheckCtxt<'a> {
  70     fn visit_expr(&mut self, ex: &Expr, _: ()) {
  71         check_expr(self, ex);
  72     }
  73     fn visit_local(&mut self, l: &Local, _: ()) {
  74         check_local(self, l);
  75     }
  76     fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl, b: &Block, s: Span, _: NodeId, _: ()) {
  77         check_fn(self, fk, fd, b, s);
  78     }
  79 }
  80
  81 pub fn check_crate(tcx: &ty::ctxt,
  82                    krate: &Crate) {
  83     let mut cx = MatchCheckCtxt {
  84         tcx: tcx,
  85     };
  86
  87     visit::walk_crate(&mut cx, krate, ());
  88
  89     tcx.sess.abort_if_errors();
  90 }
  91
  92 fn check_expr(cx: &mut MatchCheckCtxt, ex: &Expr) {
  93     visit::walk_expr(cx, ex, ());
  94     match ex.node {
  95         ExprMatch(scrut, ref arms) => {
  96             // First, check legality of move bindings.
  97             for arm in arms.iter() {
  98                 check_legality_of_move_bindings(cx,
  99                                                 arm.guard.is_some(),
 100                                                 arm.pats.as_slice());
 101             }
 102
 103             // Second, check for unreachable arms.
 104             check_arms(cx, arms.as_slice());
 105
 106             // Finally, check if the whole match expression is exhaustive.
 107             // Check for empty enum, because is_useful only works on inhabited types.
 108             let pat_ty = node_id_to_type(cx.tcx, scrut.id);
 109             if (*arms).is_empty() {
 110                if !type_is_empty(cx.tcx, pat_ty) {
 111                    // We know the type is inhabited, so this must be wrong
 112                    cx.tcx.sess.span_err(ex.span, format!("non-exhaustive patterns: \
 113                                 type {} is non-empty",
 114                                 ty_to_str(cx.tcx, pat_ty)).as_slice());
 115                }
 116                // If the type *is* empty, it's vacuously exhaustive
 117                return;
 118             }
 119             let m: Matrix = arms
 120                 .iter()
 121                 .filter(|&arm| is_unguarded(arm))
 122                 .flat_map(|arm| arm.pats.iter())
 123                 .map(|pat| vec!(pat.clone()))
 124                 .collect();
 125             check_exhaustive(cx, ex.span, &m);
 126         },
 127         _ => ()
 128     }
 129 }
 130
 131 // Check for unreachable patterns
 132 fn check_arms(cx: &MatchCheckCtxt, arms: &[Arm]) {
 133     let mut seen = Vec::new();
 134     for arm in arms.iter() {
 135         for pat in arm.pats.iter() {
 136             // Check that we do not match against a static NaN (#6804)
 137             let pat_matches_nan: |&Pat| -> bool = |p| {
 138                 let opt_def = cx.tcx.def_map.borrow().find_copy(&p.id);
 139                 match opt_def {
 140                     Some(DefStatic(did, false)) => {
 141                         let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
 142                         match eval_const_expr(cx.tcx, &*const_expr) {
 143                             const_float(f) if f.is_nan() => true,
 144                             _ => false
 145                         }
 146                     }
 147                     _ => false
 148                 }
 149             };
 150
 151             walk_pat(&**pat, |p| {
 152                 if pat_matches_nan(p) {
 153                     cx.tcx.sess.span_warn(p.span, "unmatchable NaN in pattern, \
 154                                                    use the is_nan method in a guard instead");
 155                 }
 156                 true
 157             });
 158
 159             let v = vec!(*pat);
 160             match is_useful(cx, &seen, v.as_slice(), LeaveOutWitness) {
 161                 NotUseful => cx.tcx.sess.span_err(pat.span, "unreachable pattern"),
 162                 _ => ()
 163             }
 164             if arm.guard.is_none() { seen.push(v); }
 165         }
 166     }
 167 }
 168
 169 fn raw_pat(p: Gc<Pat>) -> Gc<Pat> {
 170     match p.node {
 171         PatIdent(_, _, Some(s)) => { raw_pat(s) }
 172         _ => { p }
 173     }
 174 }
 175
 176 fn check_exhaustive(cx: &MatchCheckCtxt, sp: Span, m: &Matrix) {
 177     match is_useful(cx, m, [wild()], ConstructWitness) {
 178         NotUseful => {
 179             // This is good, wildcard pattern isn't reachable
 180             return;
 181         }
 182         Useful(pats) => {
 183             let witness = match pats.as_slice() {
 184                 [witness] => witness,
 185                 [] => wild(),
 186                 _ => unreachable!()
 187             };
 188             let msg = format!("non-exhaustive patterns: `{0}` not covered", pat_to_str(&*witness));
 189             cx.tcx.sess.span_err(sp, msg.as_slice());
 190         }
 191     }
 192 }
 193
 194 #[deriving(Clone, PartialEq)]
 195 enum ctor {
 196     single,
 197     variant(DefId),
 198     val(const_val),
 199     range(const_val, const_val),
 200     vec(uint)
 201 }
 202
 203 fn const_val_to_expr(value: &const_val) -> Gc<Expr> {
 204     let node = match value {
 205         &const_bool(b) => LitBool(b),
 206         _ => unreachable!()
 207     };
 208     box(GC) Expr {
 209         id: 0,
 210         node: ExprLit(box(GC) Spanned { node: node, span: DUMMY_SP }),
 211         span: DUMMY_SP
 212     }
 213 }
 214
 215 fn construct_witness(cx: &MatchCheckCtxt, ctor: &ctor, pats: Vec<Gc<Pat>>, lty: ty::t) -> Gc<Pat> {
 216     let pat = match ty::get(lty).sty {
 217         ty::ty_tup(_) => PatTup(pats),
 218
 219         ty::ty_enum(cid, _) | ty::ty_struct(cid, _)  => {
 220             let (vid, is_structure) = match ctor {
 221                 &variant(vid) => (vid,
 222                     ty::enum_variant_with_id(cx.tcx, cid, vid).arg_names.is_some()),
 223                 _ => (cid, true)
 224             };
 225             if is_structure {
 226                 let fields = ty::lookup_struct_fields(cx.tcx, vid);
 227                 let field_pats = fields.move_iter()
 228                     .zip(pats.iter())
 229                     .map(|(field, pat)| FieldPat {
 230                         ident: Ident::new(field.name),
 231                         pat: pat.clone()
 232                     }).collect();
 233                 PatStruct(def_to_path(cx.tcx, vid), field_pats, false)
 234             } else {
 235                 PatEnum(def_to_path(cx.tcx, vid), Some(pats))
 236             }
 237         },
 238
 239         ty::ty_rptr(_, ty::mt { ty: ty, .. }) => {
 240             match ty::get(ty).sty {
 241                 ty::ty_vec(_, None) => match ctor {
 242                     &vec(_) => PatVec(pats, None, vec!()),
 243                     _ => unreachable!()
 244                 },
 245                 ty::ty_str => PatWild,
 246                 _ => {
 247                     assert_eq!(pats.len(), 1);
 248                     PatRegion(pats.get(0).clone())
 249                 }
 250             }
 251         },
 252
 253         ty::ty_box(_) => {
 254             assert_eq!(pats.len(), 1);
 255             PatBox(pats.get(0).clone())
 256         },
 257
 258         _ => {
 259             match ctor {
 260                 &vec(_) => PatVec(pats, None, vec!()),
 261                 &val(ref v) => PatLit(const_val_to_expr(v)),
 262                 _ => PatWild
 263             }
 264         }
 265     };
 266
 267     box(GC) Pat {
 268         id: 0,
 269         node: pat,
 270         span: DUMMY_SP
 271     }
 272 }
 273
 274 fn missing_constructor(cx: &MatchCheckCtxt, m: &Matrix, left_ty: ty::t) -> Option<ctor> {
 275     let used_constructors: Vec<ctor> = m.iter()
 276         .filter_map(|r| pat_ctor_id(cx, left_ty, *r.get(0)))
 277         .collect();
 278
 279     all_constructors(cx, m, left_ty)
 280         .move_iter()
 281         .find(|c| !used_constructors.contains(c))
 282 }
 283
 284 fn all_constructors(cx: &MatchCheckCtxt, m: &Matrix, left_ty: ty::t) -> Vec<ctor> {
 285     // This produces a list of all vector constructors that we would expect to appear
 286     // in an exhaustive set of patterns. Because such a list would normally be infinite,
 287     // we narrow it down to only those constructors that actually appear in the inspected
 288     // column, plus, any that are missing and not covered by a pattern with a destructured slice.
 289     fn vec_constructors(m: &Matrix) -> Vec<ctor> {
 290         let max_vec_len = m.iter().map(|r| match r.get(0).node {
 291             PatVec(ref before, _, ref after) => before.len() + after.len(),
 292             _ => 0u
 293         }).max().unwrap_or(0u);
 294         let min_vec_len_with_slice = m.iter().map(|r| match r.get(0).node {
 295             PatVec(ref before, Some(_), ref after) => before.len() + after.len(),
 296             _ => max_vec_len + 1
 297         }).min().unwrap_or(max_vec_len + 1);
 298         let other_lengths = m.iter().map(|r| match r.get(0).node {
 299             PatVec(ref before, _, ref after) => before.len() + after.len(),
 300             _ => 0u
 301         }).filter(|&len| len > min_vec_len_with_slice);
 302         iter::range_inclusive(0u, min_vec_len_with_slice)
 303             .chain(other_lengths)
 304             .map(|len| vec(len))
 305             .collect()
 306     }
 307
 308     match ty::get(left_ty).sty {
 309         ty::ty_bool =>
 310             [true, false].iter().map(|b| val(const_bool(*b))).collect(),
 311
 312         ty::ty_rptr(_, ty::mt { ty: ty, .. }) => match ty::get(ty).sty {
 313             ty::ty_vec(_, None) => vec_constructors(m),
 314             _ => vec!(single)
 315         },
 316
 317         ty::ty_enum(eid, _) =>
 318             ty::enum_variants(cx.tcx, eid)
 319                 .iter()
 320                 .map(|va| variant(va.id))
 321                 .collect(),
 322
 323         ty::ty_vec(_, None) =>
 324             vec_constructors(m),
 325
 326         ty::ty_vec(_, Some(n)) =>
 327             vec!(vec(n)),
 328
 329         ty::ty_nil if !m.iter().all(|r| is_wild(cx, *r.get(0))) =>
 330             vec!(),
 331
 332         _ =>
 333             vec!(single)
 334     }
 335 }
 336
 337 // Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html
 338 //
 339 // Whether a vector `v` of patterns is 'useful' in relation to a set of such
 340 // vectors `m` is defined as there being a set of inputs that will match `v`
 341 // but not any of the sets in `m`.
 342 //
 343 // This is used both for reachability checking (if a pattern isn't useful in
 344 // relation to preceding patterns, it is not reachable) and exhaustiveness
 345 // checking (if a wildcard pattern is useful in relation to a matrix, the
 346 // matrix isn't exhaustive).
 347
 348 // Note: is_useful doesn't work on empty types, as the paper notes.
 349 // So it assumes that v is non-empty.
 350 fn is_useful(cx: &MatchCheckCtxt, m: &Matrix, v: &[Gc<Pat>],
 351              witness: WitnessPreference) -> Usefulness {
 352     if m.len() == 0u {
 353         return Useful(vec!());
 354     }
 355     if m.get(0).len() == 0u {
 356         return NotUseful;
 357     }
 358     let real_pat = match m.iter().find(|r| r.get(0).id != 0) {
 359         Some(r) => {
 360             match r.get(0).node {
 361                 // An arm of the form `ref x @ sub_pat` has type
 362                 // `sub_pat`, not `&sub_pat` as `x` itself does.
 363                 PatIdent(BindByRef(_), _, Some(sub)) => sub,
 364                 _ => *r.get(0)
 365             }
 366         }
 367         None if v.len() == 0 => return NotUseful,
 368         None => v[0]
 369     };
 370     let left_ty = if real_pat.id == 0 {
 371         ty::mk_nil()
 372     } else {
 373         ty::pat_ty(cx.tcx, &*real_pat)
 374     };
 375
 376     match pat_ctor_id(cx, left_ty, v[0]) {
 377         None => match missing_constructor(cx, m, left_ty) {
 378             None => {
 379                 all_constructors(cx, m, left_ty).move_iter().filter_map(|c| {
 380                     is_useful_specialized(cx, m, v, c.clone(),
 381                                           left_ty, witness).useful().map(|pats| {
 382                         Useful(match witness {
 383                             ConstructWitness => {
 384                                 let arity = constructor_arity(cx, &c, left_ty);
 385                                 let subpats = {
 386                                     let pat_slice = pats.as_slice();
 387                                     Vec::from_fn(arity, |i| {
 388                                         pat_slice.get(i).map(|p| p.clone())
 389                                             .unwrap_or_else(|| wild())
 390                                     })
 391                                 };
 392                                 let mut result = vec!(construct_witness(cx, &c, subpats, left_ty));
 393                                 result.extend(pats.move_iter().skip(arity));
 394                                 result
 395                             }
 396                             LeaveOutWitness => vec!()
 397                         })
 398                     })
 399                 }).nth(0).unwrap_or(NotUseful)
 400             },
 401
 402             Some(ctor) => {
 403                 let matrix = m.iter().filter_map(|r| default(cx, r.as_slice())).collect();
 404                 match is_useful(cx, &matrix, v.tail(), witness) {
 405                     Useful(pats) => Useful(match witness {
 406                         ConstructWitness => {
 407                             let arity = constructor_arity(cx, &ctor, left_ty);
 408                             let wild_pats = Vec::from_elem(arity, wild());
 409                             let enum_pat = construct_witness(cx, &ctor, wild_pats, left_ty);
 410                             (vec!(enum_pat)).append(pats.as_slice())
 411                         }
 412                         LeaveOutWitness => vec!()
 413                     }),
 414                     result => result
 415                 }
 416             }
 417         },
 418
 419         Some(v0_ctor) => is_useful_specialized(cx, m, v, v0_ctor, left_ty, witness)
 420     }
 421 }
 422
 423 fn is_useful_specialized(cx: &MatchCheckCtxt, m: &Matrix, v: &[Gc<Pat>],
 424                          ctor: ctor, lty: ty::t, witness: WitnessPreference) -> Usefulness {
 425     let arity = constructor_arity(cx, &ctor, lty);
 426     let matrix = m.iter().filter_map(|r| {
 427         specialize(cx, r.as_slice(), &ctor, arity)
 428     }).collect();
 429     match specialize(cx, v, &ctor, arity) {
 430         Some(v) => is_useful(cx, &matrix, v.as_slice(), witness),
 431         None => NotUseful
 432     }
 433 }
 434
 435 fn pat_ctor_id(cx: &MatchCheckCtxt, left_ty: ty::t, p: Gc<Pat>) -> Option<ctor> {
 436     let pat = raw_pat(p);
 437     match pat.node {
 438         PatIdent(..) =>
 439             match cx.tcx.def_map.borrow().find(&pat.id) {
 440                 Some(&DefStatic(did, false)) => {
 441                     let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
 442                     Some(val(eval_const_expr(cx.tcx, &*const_expr)))
 443                 },
 444                 Some(&DefVariant(_, id, _)) => Some(variant(id)),
 445                 _ => None
 446             },
 447         PatEnum(..) =>
 448             match cx.tcx.def_map.borrow().find(&pat.id) {
 449                 Some(&DefStatic(did, false)) => {
 450                     let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
 451                     Some(val(eval_const_expr(cx.tcx, &*const_expr)))
 452                 },
 453                 Some(&DefVariant(_, id, _)) => Some(variant(id)),
 454                 _ => Some(single)
 455             },
 456         PatStruct(..) =>
 457             match cx.tcx.def_map.borrow().find(&pat.id) {
 458                 Some(&DefVariant(_, id, _)) => Some(variant(id)),
 459                 _ => Some(single)
 460             },
 461         PatLit(expr) =>
 462             Some(val(eval_const_expr(cx.tcx, &*expr))),
 463         PatRange(lo, hi) =>
 464             Some(range(eval_const_expr(cx.tcx, &*lo), eval_const_expr(cx.tcx, &*hi))),
 465         PatVec(ref before, _, ref after) => match ty::get(left_ty).sty {
 466             ty::ty_vec(_, Some(n)) =>
 467                 Some(vec(n)),
 468             _ =>
 469                 Some(vec(before.len() + after.len()))
 470         },
 471         PatBox(_) | PatTup(_) | PatRegion(..) =>
 472             Some(single),
 473         PatWild | PatWildMulti =>
 474             None,
 475         PatMac(_) =>
 476             cx.tcx.sess.bug("unexpanded macro")
 477     }
 478 }
 479
 480 fn is_wild(cx: &MatchCheckCtxt, p: Gc<Pat>) -> bool {
 481     let pat = raw_pat(p);
 482     match pat.node {
 483         PatWild | PatWildMulti => true,
 484         PatIdent(_, _, _) => {
 485             match cx.tcx.def_map.borrow().find(&pat.id) {
 486                 Some(&DefVariant(_, _, _)) | Some(&DefStatic(..)) => false,
 487                 _ => true
 488             }
 489         }
 490         _ => false
 491     }
 492 }
 493
 494 fn constructor_arity(cx: &MatchCheckCtxt, ctor: &ctor, ty: ty::t) -> uint {
 495     match ty::get(ty).sty {
 496         ty::ty_tup(ref fs) => fs.len(),
 497         ty::ty_box(_) | ty::ty_uniq(_) => 1u,
 498         ty::ty_rptr(_, ty::mt { ty: ty, .. }) => match ty::get(ty).sty {
 499             ty::ty_vec(_, None) => match *ctor {
 500                 vec(n) => n,
 501                 _ => 0u
 502             },
 503             ty::ty_str => 0u,
 504             _ => 1u
 505         },
 506         ty::ty_enum(eid, _) => {
 507             match *ctor {
 508                 variant(id) => enum_variant_with_id(cx.tcx, eid, id).args.len(),
 509                 _ => unreachable!()
 510             }
 511         }
 512         ty::ty_struct(cid, _) => ty::lookup_struct_fields(cx.tcx, cid).len(),
 513         ty::ty_vec(_, _) => match *ctor {
 514             vec(n) => n,
 515             _ => 0u
 516         },
 517         _ => 0u
 518     }
 519 }
 520
 521 fn wild() -> Gc<Pat> {
 522     box(GC) Pat {id: 0, node: PatWild, span: DUMMY_SP}
 523 }
 524
 525 fn range_covered_by_constructor(ctor_id: &ctor, from: &const_val, to: &const_val) -> Option<bool> {
 526     let (c_from, c_to) = match *ctor_id {
 527         val(ref value)          => (value, value),
 528         range(ref from, ref to) => (from, to),
 529         single                  => return Some(true),
 530         _                       => unreachable!()
 531     };
 532     let cmp_from = compare_const_vals(c_from, from);
 533     let cmp_to = compare_const_vals(c_to, to);
 534     match (cmp_from, cmp_to) {
 535         (Some(val1), Some(val2)) => Some(val1 >= 0 && val2 <= 0),
 536         _ => None
 537     }
 538 }
 539
 540 fn specialize(cx: &MatchCheckCtxt, r: &[Gc<Pat>],
 541               ctor_id: &ctor, arity: uint) -> Option<Vec<Gc<Pat>>> {
 542     let &Pat {
 543         id: ref pat_id, node: ref n, span: ref pat_span
 544     } = &(*raw_pat(r[0]));
 545     let head: Option<Vec<Gc<Pat>>> = match n {
 546         &PatWild => {
 547             Some(Vec::from_elem(arity, wild()))
 548         }
 549         &PatWildMulti => {
 550             Some(Vec::from_elem(arity, wild()))
 551         }
 552         &PatIdent(_, _, _) => {
 553             let opt_def = cx.tcx.def_map.borrow().find_copy(pat_id);
 554             match opt_def {
 555                 Some(DefVariant(_, id, _)) => if *ctor_id == variant(id) {
 556                     Some(vec!())
 557                 } else {
 558                     None
 559                 },
 560                 Some(DefStatic(did, _)) => {
 561                     let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
 562                     let e_v = eval_const_expr(cx.tcx, &*const_expr);
 563                     match range_covered_by_constructor(ctor_id, &e_v, &e_v) {
 564                         Some(true) => Some(vec!()),
 565                         Some(false) => None,
 566                         None => {
 567                             cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
 568                             None
 569                         }
 570                     }
 571                 }
 572                 _ => {
 573                     Some(Vec::from_elem(arity, wild()))
 574                 }
 575             }
 576         }
 577         &PatEnum(_, ref args) => {
 578             let def = cx.tcx.def_map.borrow().get_copy(pat_id);
 579             match def {
 580                 DefStatic(did, _) => {
 581                     let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
 582                     let e_v = eval_const_expr(cx.tcx, &*const_expr);
 583                     match range_covered_by_constructor(ctor_id, &e_v, &e_v) {
 584                         Some(true) => Some(vec!()),
 585                         Some(false) => None,
 586                         None => {
 587                             cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
 588                             None
 589                         }
 590                     }
 591                 }
 592                 DefVariant(_, id, _) if *ctor_id != variant(id) => None,
 593                 DefVariant(..) | DefFn(..) | DefStruct(..) => {
 594                     Some(match args {
 595                         &Some(ref args) => args.clone(),
 596                         &None => Vec::from_elem(arity, wild())
 597                     })
 598                 }
 599                 _ => None
 600             }
 601         }
 602
 603         &PatStruct(_, ref pattern_fields, _) => {
 604             // Is this a struct or an enum variant?
 605             let def = cx.tcx.def_map.borrow().get_copy(pat_id);
 606             let class_id = match def {
 607                 DefVariant(_, variant_id, _) => if *ctor_id == variant(variant_id) {
 608                     Some(variant_id)
 609                 } else {
 610                     None
 611                 },
 612                 DefStruct(struct_id) => Some(struct_id),
 613                 _ => None
 614             };
 615             class_id.map(|variant_id| {
 616                 let struct_fields = ty::lookup_struct_fields(cx.tcx, variant_id);
 617                 let args = struct_fields.iter().map(|sf| {
 618                     match pattern_fields.iter().find(|f| f.ident.name == sf.name) {
 619                         Some(f) => f.pat,
 620                         _ => wild()
 621                     }
 622                 }).collect();
 623                 args
 624             })
 625         }
 626
 627         &PatTup(ref args) =>
 628             Some(args.clone()),
 629
 630         &PatBox(ref inner) | &PatRegion(ref inner) =>
 631             Some(vec!(inner.clone())),
 632
 633         &PatLit(ref expr) => {
 634             let expr_value = eval_const_expr(cx.tcx, &**expr);
 635             match range_covered_by_constructor(ctor_id, &expr_value, &expr_value) {
 636                 Some(true) => Some(vec!()),
 637                 Some(false) => None,
 638                 None => {
 639                     cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
 640                     None
 641                 }
 642             }
 643         }
 644
 645         &PatRange(ref from, ref to) => {
 646             let from_value = eval_const_expr(cx.tcx, &**from);
 647             let to_value = eval_const_expr(cx.tcx, &**to);
 648             match range_covered_by_constructor(ctor_id, &from_value, &to_value) {
 649                 Some(true) => Some(vec!()),
 650                 Some(false) => None,
 651                 None => {
 652                     cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
 653                     None
 654                 }
 655             }
 656         }
 657
 658         &PatVec(ref before, ref slice, ref after) => {
 659             match *ctor_id {
 660                 vec(_) => {
 661                     let num_elements = before.len() + after.len();
 662                     if num_elements < arity && slice.is_some() {
 663                         let mut result = Vec::new();
 664                         result.push_all(before.as_slice());
 665                         result.grow_fn(arity - num_elements, |_| wild());
 666                         result.push_all(after.as_slice());
 667                         Some(result)
 668                     } else if num_elements == arity {
 669                         let mut result = Vec::new();
 670                         result.push_all(before.as_slice());
 671                         result.push_all(after.as_slice());
 672                         Some(result)
 673                     } else {
 674                         None
 675                     }
 676                 }
 677                 _ => None
 678             }
 679         }
 680
 681         &PatMac(_) => {
 682             cx.tcx.sess.span_err(*pat_span, "unexpanded macro");
 683             None
 684         }
 685     };
 686     head.map(|head| head.append(r.tail()))
 687 }
 688
 689 fn default(cx: &MatchCheckCtxt, r: &[Gc<Pat>]) -> Option<Vec<Gc<Pat>>> {
 690     if is_wild(cx, r[0]) {
 691         Some(Vec::from_slice(r.tail()))
 692     } else {
 693         None
 694     }
 695 }
 696
 697 fn check_local(cx: &mut MatchCheckCtxt, loc: &Local) {
 698     visit::walk_local(cx, loc, ());
 699
 700     let name = match loc.source {
 701         LocalLet => "local",
 702         LocalFor => "`for` loop"
 703     };
 704
 705     match is_refutable(cx, loc.pat) {
 706         Some(pat) => {
 707             let msg = format!(
 708                 "refutable pattern in {} binding: `{}` not covered",
 709                 name, pat_to_str(&*pat)
 710             );
 711             cx.tcx.sess.span_err(loc.pat.span, msg.as_slice());
 712         },
 713         None => ()
 714     }
 715
 716     // Check legality of move bindings.
 717     check_legality_of_move_bindings(cx, false, [ loc.pat ]);
 718 }
 719
 720 fn check_fn(cx: &mut MatchCheckCtxt,
 721             kind: &FnKind,
 722             decl: &FnDecl,
 723             body: &Block,
 724             sp: Span) {
 725     visit::walk_fn(cx, kind, decl, body, sp, ());
 726     for input in decl.inputs.iter() {
 727         match is_refutable(cx, input.pat) {
 728             Some(pat) => {
 729                 let msg = format!(
 730                     "refutable pattern in function argument: `{}` not covered",
 731                     pat_to_str(&*pat)
 732                 );
 733                 cx.tcx.sess.span_err(input.pat.span, msg.as_slice());
 734             },
 735             None => ()
 736         }
 737     }
 738 }
 739
 740 fn is_refutable(cx: &MatchCheckCtxt, pat: Gc<Pat>) -> Option<Gc<Pat>> {
 741     let pats = vec!(vec!(pat));
 742     is_useful(cx, &pats, [wild()], ConstructWitness)
 743         .useful()
 744         .map(|pats| {
 745             assert_eq!(pats.len(), 1);
 746             pats.get(0).clone()
 747         })
 748 }
 749
 750 // Legality of move bindings checking
 751
 752 fn check_legality_of_move_bindings(cx: &MatchCheckCtxt,
 753                                    has_guard: bool,
 754                                    pats: &[Gc<Pat>]) {
 755     let tcx = cx.tcx;
 756     let def_map = &tcx.def_map;
 757     let mut by_ref_span = None;
 758     for pat in pats.iter() {
 759         pat_bindings(def_map, &**pat, |bm, _, span, _path| {
 760             match bm {
 761                 BindByRef(_) => {
 762                     by_ref_span = Some(span);
 763                 }
 764                 BindByValue(_) => {
 765                 }
 766             }
 767         })
 768     }
 769
 770     let check_move: |&Pat, Option<Gc<Pat>>| = |p, sub| {
 771         // check legality of moving out of the enum
 772
 773         // x @ Foo(..) is legal, but x @ Foo(y) isn't.
 774         if sub.map_or(false, |p| pat_contains_bindings(def_map, &*p)) {
 775             tcx.sess.span_err(
 776                 p.span,
 777                 "cannot bind by-move with sub-bindings");
 778         } else if has_guard {
 779             tcx.sess.span_err(
 780                 p.span,
 781                 "cannot bind by-move into a pattern guard");
 782         } else if by_ref_span.is_some() {
 783             tcx.sess.span_err(
 784                 p.span,
 785                 "cannot bind by-move and by-ref \
 786                  in the same pattern");
 787             tcx.sess.span_note(
 788                 by_ref_span.unwrap(),
 789                 "by-ref binding occurs here");
 790         }
 791     };
 792
 793     for pat in pats.iter() {
 794         walk_pat(&**pat, |p| {
 795             if pat_is_binding(def_map, &*p) {
 796                 match p.node {
 797                     PatIdent(BindByValue(_), _, sub) => {
 798                         let pat_ty = ty::node_id_to_type(tcx, p.id);
 799                         if ty::type_moves_by_default(tcx, pat_ty) {
 800                             check_move(p, sub);
 801                         }
 802                     }
 803                     PatIdent(BindByRef(_), _, _) => {
 804                     }
 805                     _ => {
 806                         cx.tcx.sess.span_bug(
 807                             p.span,
 808                             format!("binding pattern {} is not an \
 809                                      identifier: {:?}",
 810                                     p.id,
 811                                     p.node).as_slice());
 812                     }
 813                 }
 814             }
 815             true
 816         });
 817     }
 818 }