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_nil, 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         &const_nil => LitNil,
 207         _ => unreachable!()
 208     };
 209     box(GC) Expr {
 210         id: 0,
 211         node: ExprLit(box(GC) Spanned { node: node, span: DUMMY_SP }),
 212         span: DUMMY_SP
 213     }
 214 }
 215
 216 fn construct_witness(cx: &MatchCheckCtxt, ctor: &ctor, pats: Vec<Gc<Pat>>, lty: ty::t) -> Gc<Pat> {
 217     let pat = match ty::get(lty).sty {
 218         ty::ty_tup(_) => PatTup(pats),
 219
 220         ty::ty_enum(cid, _) | ty::ty_struct(cid, _)  => {
 221             let (vid, is_structure) = match ctor {
 222                 &variant(vid) => (vid,
 223                     ty::enum_variant_with_id(cx.tcx, cid, vid).arg_names.is_some()),
 224                 _ => (cid, true)
 225             };
 226             if is_structure {
 227                 let fields = ty::lookup_struct_fields(cx.tcx, vid);
 228                 let field_pats = fields.move_iter()
 229                     .zip(pats.iter())
 230                     .map(|(field, pat)| FieldPat {
 231                         ident: Ident::new(field.name),
 232                         pat: pat.clone()
 233                     }).collect();
 234                 PatStruct(def_to_path(cx.tcx, vid), field_pats, false)
 235             } else {
 236                 PatEnum(def_to_path(cx.tcx, vid), Some(pats))
 237             }
 238         },
 239
 240         ty::ty_rptr(_, ty::mt { ty: ty, .. }) => {
 241             match ty::get(ty).sty {
 242                 ty::ty_vec(_, None) => match ctor {
 243                     &vec(_) => PatVec(pats, None, vec!()),
 244                     _ => unreachable!()
 245                 },
 246                 ty::ty_str => PatWild,
 247                 _ => {
 248                     assert_eq!(pats.len(), 1);
 249                     PatRegion(pats.get(0).clone())
 250                 }
 251             }
 252         },
 253
 254         ty::ty_box(_) => {
 255             assert_eq!(pats.len(), 1);
 256             PatBox(pats.get(0).clone())
 257         },
 258
 259         _ => {
 260             match ctor {
 261                 &vec(_) => PatVec(pats, None, vec!()),
 262                 &val(ref v) => PatLit(const_val_to_expr(v)),
 263                 _ => PatWild
 264             }
 265         }
 266     };
 267
 268     box(GC) Pat {
 269         id: 0,
 270         node: pat,
 271         span: DUMMY_SP
 272     }
 273 }
 274
 275 fn missing_constructor(cx: &MatchCheckCtxt, m: &Matrix, left_ty: ty::t) -> Option<ctor> {
 276     let used_constructors: Vec<ctor> = m.iter()
 277         .filter_map(|r| pat_ctor_id(cx, left_ty, *r.get(0)))
 278         .collect();
 279
 280     all_constructors(cx, m, left_ty)
 281         .move_iter()
 282         .find(|c| !used_constructors.contains(c))
 283 }
 284
 285 fn all_constructors(cx: &MatchCheckCtxt, m: &Matrix, left_ty: ty::t) -> Vec<ctor> {
 286     // This produces a list of all vector constructors that we would expect to appear
 287     // in an exhaustive set of patterns. Because such a list would normally be infinite,
 288     // we narrow it down to only those constructors that actually appear in the inspected
 289     // column, plus, any that are missing and not covered by a pattern with a destructured slice.
 290     fn vec_constructors(m: &Matrix) -> Vec<ctor> {
 291         let max_vec_len = m.iter().map(|r| match r.get(0).node {
 292             PatVec(ref before, _, ref after) => before.len() + after.len(),
 293             _ => 0u
 294         }).max().unwrap_or(0u);
 295         let min_vec_len_with_slice = m.iter().map(|r| match r.get(0).node {
 296             PatVec(ref before, Some(_), ref after) => before.len() + after.len(),
 297             _ => max_vec_len + 1
 298         }).min().unwrap_or(max_vec_len + 1);
 299         let other_lengths = m.iter().map(|r| match r.get(0).node {
 300             PatVec(ref before, _, ref after) => before.len() + after.len(),
 301             _ => 0u
 302         }).filter(|&len| len > min_vec_len_with_slice);
 303         iter::range_inclusive(0u, min_vec_len_with_slice)
 304             .chain(other_lengths)
 305             .map(|len| vec(len))
 306             .collect()
 307     }
 308
 309     match ty::get(left_ty).sty {
 310         ty::ty_bool =>
 311             [true, false].iter().map(|b| val(const_bool(*b))).collect(),
 312
 313         ty::ty_nil =>
 314             vec!(val(const_nil)),
 315
 316         ty::ty_rptr(_, ty::mt { ty: ty, .. }) => match ty::get(ty).sty {
 317             ty::ty_vec(_, None) => vec_constructors(m),
 318             _ => vec!(single)
 319         },
 320
 321         ty::ty_enum(eid, _) =>
 322             ty::enum_variants(cx.tcx, eid)
 323                 .iter()
 324                 .map(|va| variant(va.id))
 325                 .collect(),
 326
 327         ty::ty_vec(_, None) =>
 328             vec_constructors(m),
 329
 330         ty::ty_vec(_, Some(n)) =>
 331             vec!(vec(n)),
 332
 333         _ =>
 334             vec!(single)
 335     }
 336 }
 337
 338 // Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html
 339 //
 340 // Whether a vector `v` of patterns is 'useful' in relation to a set of such
 341 // vectors `m` is defined as there being a set of inputs that will match `v`
 342 // but not any of the sets in `m`.
 343 //
 344 // This is used both for reachability checking (if a pattern isn't useful in
 345 // relation to preceding patterns, it is not reachable) and exhaustiveness
 346 // checking (if a wildcard pattern is useful in relation to a matrix, the
 347 // matrix isn't exhaustive).
 348
 349 // Note: is_useful doesn't work on empty types, as the paper notes.
 350 // So it assumes that v is non-empty.
 351 fn is_useful(cx: &MatchCheckCtxt, m: &Matrix, v: &[Gc<Pat>],
 352              witness: WitnessPreference) -> Usefulness {
 353     if m.len() == 0u {
 354         return Useful(vec!());
 355     }
 356     if m.get(0).len() == 0u {
 357         return NotUseful;
 358     }
 359     let real_pat = match m.iter().find(|r| r.get(0).id != 0) {
 360         Some(r) => {
 361             match r.get(0).node {
 362                 // An arm of the form `ref x @ sub_pat` has type
 363                 // `sub_pat`, not `&sub_pat` as `x` itself does.
 364                 PatIdent(BindByRef(_), _, Some(sub)) => sub,
 365                 _ => *r.get(0)
 366             }
 367         }
 368         None if v.len() == 0 => return NotUseful,
 369         None => v[0]
 370     };
 371     let left_ty = if real_pat.id == 0 {
 372         ty::mk_nil()
 373     } else {
 374         ty::pat_ty(cx.tcx, &*real_pat)
 375     };
 376
 377     match pat_ctor_id(cx, left_ty, v[0]) {
 378         None => match missing_constructor(cx, m, left_ty) {
 379             None => {
 380                 all_constructors(cx, m, left_ty).move_iter().filter_map(|c| {
 381                     is_useful_specialized(cx, m, v, c.clone(),
 382                                           left_ty, witness).useful().map(|pats| {
 383                         Useful(match witness {
 384                             ConstructWitness => {
 385                                 let arity = constructor_arity(cx, &c, left_ty);
 386                                 let subpats = {
 387                                     let pat_slice = pats.as_slice();
 388                                     Vec::from_fn(arity, |i| {
 389                                         pat_slice.get(i).map(|p| p.clone())
 390                                             .unwrap_or_else(|| wild())
 391                                     })
 392                                 };
 393                                 let mut result = vec!(construct_witness(cx, &c, subpats, left_ty));
 394                                 result.extend(pats.move_iter().skip(arity));
 395                                 result
 396                             }
 397                             LeaveOutWitness => vec!()
 398                         })
 399                     })
 400                 }).nth(0).unwrap_or(NotUseful)
 401             },
 402
 403             Some(ctor) => {
 404                 let matrix = m.iter().filter_map(|r| default(cx, r.as_slice())).collect();
 405                 match is_useful(cx, &matrix, v.tail(), witness) {
 406                     Useful(pats) => Useful(match witness {
 407                         ConstructWitness => {
 408                             let arity = constructor_arity(cx, &ctor, left_ty);
 409                             let wild_pats = Vec::from_elem(arity, wild());
 410                             let enum_pat = construct_witness(cx, &ctor, wild_pats, left_ty);
 411                             (vec!(enum_pat)).append(pats.as_slice())
 412                         }
 413                         LeaveOutWitness => vec!()
 414                     }),
 415                     result => result
 416                 }
 417             }
 418         },
 419
 420         Some(v0_ctor) => is_useful_specialized(cx, m, v, v0_ctor, left_ty, witness)
 421     }
 422 }
 423
 424 fn is_useful_specialized(cx: &MatchCheckCtxt, m: &Matrix, v: &[Gc<Pat>],
 425                          ctor: ctor, lty: ty::t, witness: WitnessPreference) -> Usefulness {
 426     let arity = constructor_arity(cx, &ctor, lty);
 427     let matrix = m.iter().filter_map(|r| {
 428         specialize(cx, r.as_slice(), &ctor, arity)
 429     }).collect();
 430     match specialize(cx, v, &ctor, arity) {
 431         Some(v) => is_useful(cx, &matrix, v.as_slice(), witness),
 432         None => NotUseful
 433     }
 434 }
 435
 436 fn pat_ctor_id(cx: &MatchCheckCtxt, left_ty: ty::t, p: Gc<Pat>) -> Option<ctor> {
 437     let pat = raw_pat(p);
 438     match pat.node {
 439         PatIdent(..) =>
 440             match cx.tcx.def_map.borrow().find(&pat.id) {
 441                 Some(&DefStatic(did, false)) => {
 442                     let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
 443                     Some(val(eval_const_expr(cx.tcx, &*const_expr)))
 444                 },
 445                 Some(&DefVariant(_, id, _)) => Some(variant(id)),
 446                 _ => None
 447             },
 448         PatEnum(..) =>
 449             match cx.tcx.def_map.borrow().find(&pat.id) {
 450                 Some(&DefStatic(did, false)) => {
 451                     let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
 452                     Some(val(eval_const_expr(cx.tcx, &*const_expr)))
 453                 },
 454                 Some(&DefVariant(_, id, _)) => Some(variant(id)),
 455                 _ => Some(single)
 456             },
 457         PatStruct(..) =>
 458             match cx.tcx.def_map.borrow().find(&pat.id) {
 459                 Some(&DefVariant(_, id, _)) => Some(variant(id)),
 460                 _ => Some(single)
 461             },
 462         PatLit(expr) =>
 463             Some(val(eval_const_expr(cx.tcx, &*expr))),
 464         PatRange(lo, hi) =>
 465             Some(range(eval_const_expr(cx.tcx, &*lo), eval_const_expr(cx.tcx, &*hi))),
 466         PatVec(ref before, _, ref after) => match ty::get(left_ty).sty {
 467             ty::ty_vec(_, Some(n)) =>
 468                 Some(vec(n)),
 469             _ =>
 470                 Some(vec(before.len() + after.len()))
 471         },
 472         PatBox(_) | PatTup(_) | PatRegion(..) =>
 473             Some(single),
 474         PatWild | PatWildMulti =>
 475             None,
 476         PatMac(_) =>
 477             cx.tcx.sess.bug("unexpanded macro")
 478     }
 479 }
 480
 481 fn is_wild(cx: &MatchCheckCtxt, p: Gc<Pat>) -> bool {
 482     let pat = raw_pat(p);
 483     match pat.node {
 484         PatWild | PatWildMulti => true,
 485         PatIdent(_, _, _) => {
 486             match cx.tcx.def_map.borrow().find(&pat.id) {
 487                 Some(&DefVariant(_, _, _)) | Some(&DefStatic(..)) => false,
 488                 _ => true
 489             }
 490         }
 491         _ => false
 492     }
 493 }
 494
 495 fn constructor_arity(cx: &MatchCheckCtxt, ctor: &ctor, ty: ty::t) -> uint {
 496     match ty::get(ty).sty {
 497         ty::ty_tup(ref fs) => fs.len(),
 498         ty::ty_box(_) | ty::ty_uniq(_) => 1u,
 499         ty::ty_rptr(_, ty::mt { ty: ty, .. }) => match ty::get(ty).sty {
 500             ty::ty_vec(_, None) => match *ctor {
 501                 vec(n) => n,
 502                 _ => 0u
 503             },
 504             ty::ty_str => 0u,
 505             _ => 1u
 506         },
 507         ty::ty_enum(eid, _) => {
 508             match *ctor {
 509                 variant(id) => enum_variant_with_id(cx.tcx, eid, id).args.len(),
 510                 _ => unreachable!()
 511             }
 512         }
 513         ty::ty_struct(cid, _) => ty::lookup_struct_fields(cx.tcx, cid).len(),
 514         ty::ty_vec(_, _) => match *ctor {
 515             vec(n) => n,
 516             _ => 0u
 517         },
 518         _ => 0u
 519     }
 520 }
 521
 522 fn wild() -> Gc<Pat> {
 523     box(GC) Pat {id: 0, node: PatWild, span: DUMMY_SP}
 524 }
 525
 526 fn range_covered_by_constructor(ctor_id: &ctor, from: &const_val, to: &const_val) -> Option<bool> {
 527     let (c_from, c_to) = match *ctor_id {
 528         val(ref value)          => (value, value),
 529         range(ref from, ref to) => (from, to),
 530         single                  => return Some(true),
 531         _                       => unreachable!()
 532     };
 533     let cmp_from = compare_const_vals(c_from, from);
 534     let cmp_to = compare_const_vals(c_to, to);
 535     match (cmp_from, cmp_to) {
 536         (Some(val1), Some(val2)) => Some(val1 >= 0 && val2 <= 0),
 537         _ => None
 538     }
 539 }
 540
 541 fn specialize(cx: &MatchCheckCtxt, r: &[Gc<Pat>],
 542               ctor_id: &ctor, arity: uint) -> Option<Vec<Gc<Pat>>> {
 543     let &Pat {
 544         id: ref pat_id, node: ref n, span: ref pat_span
 545     } = &(*raw_pat(r[0]));
 546     let head: Option<Vec<Gc<Pat>>> = match n {
 547         &PatWild => {
 548             Some(Vec::from_elem(arity, wild()))
 549         }
 550         &PatWildMulti => {
 551             Some(Vec::from_elem(arity, wild()))
 552         }
 553         &PatIdent(_, _, _) => {
 554             let opt_def = cx.tcx.def_map.borrow().find_copy(pat_id);
 555             match opt_def {
 556                 Some(DefVariant(_, id, _)) => if *ctor_id == variant(id) {
 557                     Some(vec!())
 558                 } else {
 559                     None
 560                 },
 561                 Some(DefStatic(did, _)) => {
 562                     let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
 563                     let e_v = eval_const_expr(cx.tcx, &*const_expr);
 564                     match range_covered_by_constructor(ctor_id, &e_v, &e_v) {
 565                         Some(true) => Some(vec!()),
 566                         Some(false) => None,
 567                         None => {
 568                             cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
 569                             None
 570                         }
 571                     }
 572                 }
 573                 _ => {
 574                     Some(Vec::from_elem(arity, wild()))
 575                 }
 576             }
 577         }
 578         &PatEnum(_, ref args) => {
 579             let def = cx.tcx.def_map.borrow().get_copy(pat_id);
 580             match def {
 581                 DefStatic(did, _) => {
 582                     let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
 583                     let e_v = eval_const_expr(cx.tcx, &*const_expr);
 584                     match range_covered_by_constructor(ctor_id, &e_v, &e_v) {
 585                         Some(true) => Some(vec!()),
 586                         Some(false) => None,
 587                         None => {
 588                             cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
 589                             None
 590                         }
 591                     }
 592                 }
 593                 DefVariant(_, id, _) if *ctor_id != variant(id) => None,
 594                 DefVariant(..) | DefFn(..) | DefStruct(..) => {
 595                     Some(match args {
 596                         &Some(ref args) => args.clone(),
 597                         &None => Vec::from_elem(arity, wild())
 598                     })
 599                 }
 600                 _ => None
 601             }
 602         }
 603
 604         &PatStruct(_, ref pattern_fields, _) => {
 605             // Is this a struct or an enum variant?
 606             let def = cx.tcx.def_map.borrow().get_copy(pat_id);
 607             let class_id = match def {
 608                 DefVariant(_, variant_id, _) => if *ctor_id == variant(variant_id) {
 609                     Some(variant_id)
 610                 } else {
 611                     None
 612                 },
 613                 DefStruct(struct_id) => Some(struct_id),
 614                 _ => None
 615             };
 616             class_id.map(|variant_id| {
 617                 let struct_fields = ty::lookup_struct_fields(cx.tcx, variant_id);
 618                 let args = struct_fields.iter().map(|sf| {
 619                     match pattern_fields.iter().find(|f| f.ident.name == sf.name) {
 620                         Some(f) => f.pat,
 621                         _ => wild()
 622                     }
 623                 }).collect();
 624                 args
 625             })
 626         }
 627
 628         &PatTup(ref args) =>
 629             Some(args.clone()),
 630
 631         &PatBox(ref inner) | &PatRegion(ref inner) =>
 632             Some(vec!(inner.clone())),
 633
 634         &PatLit(ref expr) => {
 635             let expr_value = eval_const_expr(cx.tcx, &**expr);
 636             match range_covered_by_constructor(ctor_id, &expr_value, &expr_value) {
 637                 Some(true) => Some(vec!()),
 638                 Some(false) => None,
 639                 None => {
 640                     cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
 641                     None
 642                 }
 643             }
 644         }
 645
 646         &PatRange(ref from, ref to) => {
 647             let from_value = eval_const_expr(cx.tcx, &**from);
 648             let to_value = eval_const_expr(cx.tcx, &**to);
 649             match range_covered_by_constructor(ctor_id, &from_value, &to_value) {
 650                 Some(true) => Some(vec!()),
 651                 Some(false) => None,
 652                 None => {
 653                     cx.tcx.sess.span_err(*pat_span, "mismatched types between arms");
 654                     None
 655                 }
 656             }
 657         }
 658
 659         &PatVec(ref before, ref slice, ref after) => {
 660             match *ctor_id {
 661                 vec(_) => {
 662                     let num_elements = before.len() + after.len();
 663                     if num_elements < arity && slice.is_some() {
 664                         let mut result = Vec::new();
 665                         result.push_all(before.as_slice());
 666                         result.grow_fn(arity - num_elements, |_| wild());
 667                         result.push_all(after.as_slice());
 668                         Some(result)
 669                     } else if num_elements == arity {
 670                         let mut result = Vec::new();
 671                         result.push_all(before.as_slice());
 672                         result.push_all(after.as_slice());
 673                         Some(result)
 674                     } else {
 675                         None
 676                     }
 677                 }
 678                 _ => None
 679             }
 680         }
 681
 682         &PatMac(_) => {
 683             cx.tcx.sess.span_err(*pat_span, "unexpanded macro");
 684             None
 685         }
 686     };
 687     head.map(|head| head.append(r.tail()))
 688 }
 689
 690 fn default(cx: &MatchCheckCtxt, r: &[Gc<Pat>]) -> Option<Vec<Gc<Pat>>> {
 691     if is_wild(cx, r[0]) {
 692         Some(Vec::from_slice(r.tail()))
 693     } else {
 694         None
 695     }
 696 }
 697
 698 fn check_local(cx: &mut MatchCheckCtxt, loc: &Local) {
 699     visit::walk_local(cx, loc, ());
 700
 701     let name = match loc.source {
 702         LocalLet => "local",
 703         LocalFor => "`for` loop"
 704     };
 705
 706     match is_refutable(cx, loc.pat) {
 707         Some(pat) => {
 708             let msg = format!(
 709                 "refutable pattern in {} binding: `{}` not covered",
 710                 name, pat_to_str(&*pat)
 711             );
 712             cx.tcx.sess.span_err(loc.pat.span, msg.as_slice());
 713         },
 714         None => ()
 715     }
 716
 717     // Check legality of move bindings.
 718     check_legality_of_move_bindings(cx, false, [ loc.pat ]);
 719 }
 720
 721 fn check_fn(cx: &mut MatchCheckCtxt,
 722             kind: &FnKind,
 723             decl: &FnDecl,
 724             body: &Block,
 725             sp: Span) {
 726     visit::walk_fn(cx, kind, decl, body, sp, ());
 727     for input in decl.inputs.iter() {
 728         match is_refutable(cx, input.pat) {
 729             Some(pat) => {
 730                 let msg = format!(
 731                     "refutable pattern in function argument: `{}` not covered",
 732                     pat_to_str(&*pat)
 733                 );
 734                 cx.tcx.sess.span_err(input.pat.span, msg.as_slice());
 735             },
 736             None => ()
 737         }
 738         check_legality_of_move_bindings(cx, false, [input.pat]);
 739     }
 740 }
 741
 742 fn is_refutable(cx: &MatchCheckCtxt, pat: Gc<Pat>) -> Option<Gc<Pat>> {
 743     let pats = vec!(vec!(pat));
 744     is_useful(cx, &pats, [wild()], ConstructWitness)
 745         .useful()
 746         .map(|pats| {
 747             assert_eq!(pats.len(), 1);
 748             pats.get(0).clone()
 749         })
 750 }
 751
 752 // Legality of move bindings checking
 753
 754 fn check_legality_of_move_bindings(cx: &MatchCheckCtxt,
 755                                    has_guard: bool,
 756                                    pats: &[Gc<Pat>]) {
 757     let tcx = cx.tcx;
 758     let def_map = &tcx.def_map;
 759     let mut by_ref_span = None;
 760     for pat in pats.iter() {
 761         pat_bindings(def_map, &**pat, |bm, _, span, _path| {
 762             match bm {
 763                 BindByRef(_) => {
 764                     by_ref_span = Some(span);
 765                 }
 766                 BindByValue(_) => {
 767                 }
 768             }
 769         })
 770     }
 771
 772     let check_move: |&Pat, Option<Gc<Pat>>| = |p, sub| {
 773         // check legality of moving out of the enum
 774
 775         // x @ Foo(..) is legal, but x @ Foo(y) isn't.
 776         if sub.map_or(false, |p| pat_contains_bindings(def_map, &*p)) {
 777             tcx.sess.span_err(
 778                 p.span,
 779                 "cannot bind by-move with sub-bindings");
 780         } else if has_guard {
 781             tcx.sess.span_err(
 782                 p.span,
 783                 "cannot bind by-move into a pattern guard");
 784         } else if by_ref_span.is_some() {
 785             tcx.sess.span_err(
 786                 p.span,
 787                 "cannot bind by-move and by-ref \
 788                  in the same pattern");
 789             tcx.sess.span_note(
 790                 by_ref_span.unwrap(),
 791                 "by-ref binding occurs here");
 792         }
 793     };
 794
 795     for pat in pats.iter() {
 796         walk_pat(&**pat, |p| {
 797             if pat_is_binding(def_map, &*p) {
 798                 match p.node {
 799                     PatIdent(BindByValue(_), _, sub) => {
 800                         let pat_ty = ty::node_id_to_type(tcx, p.id);
 801                         if ty::type_moves_by_default(tcx, pat_ty) {
 802                             check_move(p, sub);
 803                         }
 804                     }
 805                     PatIdent(BindByRef(_), _, _) => {
 806                     }
 807                     _ => {
 808                         cx.tcx.sess.span_bug(
 809                             p.span,
 810                             format!("binding pattern {} is not an \
 811                                      identifier: {:?}",
 812                                     p.id,
 813                                     p.node).as_slice());
 814                     }
 815                 }
 816             }
 817             true
 818         });
 819     }
 820 }