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, lookup_const_by_id};
  14 use middle::const_eval::{eval_const_expr, const_val, const_bool, const_float};
  15 use middle::pat_util::*;
  16 use middle::ty::*;
  17 use middle::ty;
  18 use middle::typeck::MethodMap;
  19 use middle::moves;
  20 use util::ppaux::ty_to_str;
  21
  22 use std::cmp;
  23 use std::iter;
  24 use std::vec;
  25 use syntax::ast::*;
  26 use syntax::ast_util::{unguarded_pat, walk_pat};
  27 use syntax::codemap::{DUMMY_SP, Span};
  28 use syntax::parse::token;
  29 use syntax::visit;
  30 use syntax::visit::{Visitor, FnKind};
  31
  32 struct MatchCheckCtxt {
  33     tcx: ty::ctxt,
  34     method_map: MethodMap,
  35     moves_map: moves::MovesMap
  36 }
  37
  38 struct CheckMatchVisitor {
  39     cx: @MatchCheckCtxt
  40 }
  41
  42 impl Visitor<()> for CheckMatchVisitor {
  43     fn visit_expr(&mut self, ex: &Expr, _: ()) {
  44         check_expr(self, self.cx, ex, ());
  45     }
  46     fn visit_local(&mut self, l: &Local, _: ()) {
  47         check_local(self, self.cx, l, ());
  48     }
  49     fn visit_fn(&mut self, fk: &FnKind, fd: &FnDecl, b: &Block, s: Span, n: NodeId, _: ()) {
  50         check_fn(self, self.cx, fk, fd, b, s, n, ());
  51     }
  52 }
  53
  54 pub fn check_crate(tcx: ty::ctxt,
  55                    method_map: MethodMap,
  56                    moves_map: moves::MovesMap,
  57                    krate: &Crate) {
  58     let cx = @MatchCheckCtxt {tcx: tcx,
  59                               method_map: method_map,
  60                               moves_map: moves_map};
  61     let mut v = CheckMatchVisitor { cx: cx };
  62
  63     visit::walk_crate(&mut v, krate, ());
  64
  65     tcx.sess.abort_if_errors();
  66 }
  67
  68 fn check_expr(v: &mut CheckMatchVisitor,
  69                   cx: @MatchCheckCtxt,
  70                   ex: &Expr,
  71                   s: ()) {
  72     visit::walk_expr(v, ex, s);
  73     match ex.node {
  74       ExprMatch(scrut, ref arms) => {
  75         // First, check legality of move bindings.
  76         for arm in arms.iter() {
  77             check_legality_of_move_bindings(cx,
  78                                             arm.guard.is_some(),
  79                                             arm.pats);
  80         }
  81
  82         check_arms(cx, *arms);
  83         /* Check for exhaustiveness */
  84          // Check for empty enum, because is_useful only works on inhabited
  85          // types.
  86        let pat_ty = node_id_to_type(cx.tcx, scrut.id);
  87        if (*arms).is_empty() {
  88            if !type_is_empty(cx.tcx, pat_ty) {
  89                // We know the type is inhabited, so this must be wrong
  90                cx.tcx.sess.span_err(ex.span, format!("non-exhaustive patterns: \
  91                             type {} is non-empty",
  92                             ty_to_str(cx.tcx, pat_ty)));
  93            }
  94            // If the type *is* empty, it's vacuously exhaustive
  95            return;
  96        }
  97        match ty::get(pat_ty).sty {
  98           ty_enum(did, _) => {
  99               if (*enum_variants(cx.tcx, did)).is_empty() &&
 100                     (*arms).is_empty() {
 101
 102                return;
 103             }
 104           }
 105           _ => { /* We assume only enum types can be uninhabited */ }
 106        }
 107        let arms = arms.iter().filter_map(unguarded_pat).collect::<~[~[@Pat]]>().concat_vec();
 108        if arms.is_empty() {
 109            cx.tcx.sess.span_err(ex.span, "non-exhaustive patterns");
 110        } else {
 111            check_exhaustive(cx, ex.span, arms);
 112        }
 113      }
 114      _ => ()
 115     }
 116 }
 117
 118 // Check for unreachable patterns
 119 fn check_arms(cx: &MatchCheckCtxt, arms: &[Arm]) {
 120     let mut seen = ~[];
 121     for arm in arms.iter() {
 122         for pat in arm.pats.iter() {
 123
 124             // Check that we do not match against a static NaN (#6804)
 125             let pat_matches_nan: |&Pat| -> bool = |p| {
 126                 let opt_def = {
 127                     let def_map = cx.tcx.def_map.borrow();
 128                     def_map.get().find_copy(&p.id)
 129                 };
 130                 match opt_def {
 131                     Some(DefStatic(did, false)) => {
 132                         let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
 133                         match eval_const_expr(cx.tcx, const_expr) {
 134                             const_float(f) if f.is_nan() => true,
 135                             _ => false
 136                         }
 137                     }
 138                     _ => false
 139                 }
 140             };
 141
 142             walk_pat(*pat, |p| {
 143                 if pat_matches_nan(p) {
 144                     cx.tcx.sess.span_warn(p.span, "unmatchable NaN in pattern, \
 145                                                    use the is_nan method in a guard instead");
 146                 }
 147                 true
 148             });
 149
 150             let v = ~[*pat];
 151             match is_useful(cx, &seen, v) {
 152               not_useful => {
 153                 cx.tcx.sess.span_err(pat.span, "unreachable pattern");
 154               }
 155               _ => ()
 156             }
 157             if arm.guard.is_none() { seen.push(v); }
 158         }
 159     }
 160 }
 161
 162 fn raw_pat(p: @Pat) -> @Pat {
 163     match p.node {
 164       PatIdent(_, _, Some(s)) => { raw_pat(s) }
 165       _ => { p }
 166     }
 167 }
 168
 169 fn check_exhaustive(cx: &MatchCheckCtxt, sp: Span, pats: ~[@Pat]) {
 170     assert!((!pats.is_empty()));
 171     let ext = match is_useful(cx, &pats.map(|p| ~[*p]), [wild()]) {
 172         not_useful => {
 173             // This is good, wildcard pattern isn't reachable
 174             return;
 175         }
 176         useful_ => None,
 177         useful(ty, ref ctor) => {
 178             match ty::get(ty).sty {
 179                 ty::ty_bool => {
 180                     match *ctor {
 181                         val(const_bool(true)) => Some(~"true"),
 182                         val(const_bool(false)) => Some(~"false"),
 183                         _ => None
 184                     }
 185                 }
 186                 ty::ty_enum(id, _) => {
 187                     let vid = match *ctor {
 188                         variant(id) => id,
 189                         _ => fail!("check_exhaustive: non-variant ctor"),
 190                     };
 191                     let variants = ty::enum_variants(cx.tcx, id);
 192
 193                     match variants.iter().find(|v| v.id == vid) {
 194                         Some(v) => Some(token::get_ident(v.name).get().to_str()),
 195                         None => {
 196                             fail!("check_exhaustive: bad variant in ctor")
 197                         }
 198                     }
 199                 }
 200                 ty::ty_unboxed_vec(..) | ty::ty_vec(..) => {
 201                     match *ctor {
 202                         vec(n) => Some(format!("vectors of length {}", n)),
 203                         _ => None
 204                     }
 205                 }
 206                 _ => None
 207             }
 208         }
 209     };
 210     let msg = ~"non-exhaustive patterns" + match ext {
 211         Some(ref s) => format!(": {} not covered",  *s),
 212         None => ~""
 213     };
 214     cx.tcx.sess.span_err(sp, msg);
 215 }
 216
 217 type matrix = ~[~[@Pat]];
 218
 219 #[deriving(Clone)]
 220 enum useful {
 221     useful(ty::t, ctor),
 222     useful_,
 223     not_useful,
 224 }
 225
 226 #[deriving(Clone, Eq)]
 227 enum ctor {
 228     single,
 229     variant(DefId),
 230     val(const_val),
 231     range(const_val, const_val),
 232     vec(uint)
 233 }
 234
 235 // Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html
 236 //
 237 // Whether a vector `v` of patterns is 'useful' in relation to a set of such
 238 // vectors `m` is defined as there being a set of inputs that will match `v`
 239 // but not any of the sets in `m`.
 240 //
 241 // This is used both for reachability checking (if a pattern isn't useful in
 242 // relation to preceding patterns, it is not reachable) and exhaustiveness
 243 // checking (if a wildcard pattern is useful in relation to a matrix, the
 244 // matrix isn't exhaustive).
 245
 246 // Note: is_useful doesn't work on empty types, as the paper notes.
 247 // So it assumes that v is non-empty.
 248 fn is_useful(cx: &MatchCheckCtxt, m: &matrix, v: &[@Pat]) -> useful {
 249     if m.len() == 0u { return useful_; }
 250     if m[0].len() == 0u { return not_useful; }
 251     let real_pat = match m.iter().find(|r| r[0].id != 0) {
 252       Some(r) => r[0], None => v[0]
 253     };
 254     let left_ty = if real_pat.id == 0 { ty::mk_nil() }
 255                   else { ty::node_id_to_type(cx.tcx, real_pat.id) };
 256
 257     match pat_ctor_id(cx, v[0]) {
 258       None => {
 259         match missing_ctor(cx, m, left_ty) {
 260           None => {
 261             match ty::get(left_ty).sty {
 262               ty::ty_bool => {
 263                 match is_useful_specialized(cx, m, v,
 264                                             val(const_bool(true)),
 265                                             0u, left_ty){
 266                   not_useful => {
 267                     is_useful_specialized(cx, m, v,
 268                                           val(const_bool(false)),
 269                                           0u, left_ty)
 270                   }
 271                   ref u => (*u).clone(),
 272                 }
 273               }
 274               ty::ty_enum(eid, _) => {
 275                 for va in (*ty::enum_variants(cx.tcx, eid)).iter() {
 276                     match is_useful_specialized(cx, m, v, variant(va.id),
 277                                                 va.args.len(), left_ty) {
 278                       not_useful => (),
 279                       ref u => return (*u).clone(),
 280                     }
 281                 }
 282                 not_useful
 283               }
 284               ty::ty_vec(_, ty::vstore_fixed(n)) => {
 285                 is_useful_specialized(cx, m, v, vec(n), n, left_ty)
 286               }
 287               ty::ty_unboxed_vec(..) | ty::ty_vec(..) => {
 288                 let max_len = m.rev_iter().fold(0, |max_len, r| {
 289                   match r[0].node {
 290                     PatVec(ref before, _, ref after) => {
 291                       cmp::max(before.len() + after.len(), max_len)
 292                     }
 293                     _ => max_len
 294                   }
 295                 });
 296                 for n in iter::range(0u, max_len + 1) {
 297                   match is_useful_specialized(cx, m, v, vec(n), n, left_ty) {
 298                     not_useful => (),
 299                     ref u => return (*u).clone(),
 300                   }
 301                 }
 302                 not_useful
 303               }
 304               _ => {
 305                 let arity = ctor_arity(cx, &single, left_ty);
 306                 is_useful_specialized(cx, m, v, single, arity, left_ty)
 307               }
 308             }
 309           }
 310           Some(ref ctor) => {
 311             match is_useful(cx,
 312                             &m.iter().filter_map(|r| default(cx, *r)).collect::<matrix>(),
 313                             v.tail()) {
 314               useful_ => useful(left_ty, (*ctor).clone()),
 315               ref u => (*u).clone(),
 316             }
 317           }
 318         }
 319       }
 320       Some(ref v0_ctor) => {
 321         let arity = ctor_arity(cx, v0_ctor, left_ty);
 322         is_useful_specialized(cx, m, v, (*v0_ctor).clone(), arity, left_ty)
 323       }
 324     }
 325 }
 326
 327 fn is_useful_specialized(cx: &MatchCheckCtxt,
 328                              m: &matrix,
 329                              v: &[@Pat],
 330                              ctor: ctor,
 331                              arity: uint,
 332                              lty: ty::t)
 333                           -> useful {
 334     let ms = m.iter().filter_map(|r| specialize(cx, *r, &ctor, arity, lty)).collect::<matrix>();
 335     let could_be_useful = is_useful(
 336         cx, &ms, specialize(cx, v, &ctor, arity, lty).unwrap());
 337     match could_be_useful {
 338       useful_ => useful(lty, ctor),
 339       ref u => (*u).clone(),
 340     }
 341 }
 342
 343 fn pat_ctor_id(cx: &MatchCheckCtxt, p: @Pat) -> Option<ctor> {
 344     let pat = raw_pat(p);
 345     match pat.node {
 346       PatWild | PatWildMulti => { None }
 347       PatIdent(_, _, _) | PatEnum(_, _) => {
 348         let opt_def = {
 349             let def_map = cx.tcx.def_map.borrow();
 350             def_map.get().find_copy(&pat.id)
 351         };
 352         match opt_def {
 353           Some(DefVariant(_, id, _)) => Some(variant(id)),
 354           Some(DefStatic(did, false)) => {
 355             let const_expr = lookup_const_by_id(cx.tcx, did).unwrap();
 356             Some(val(eval_const_expr(cx.tcx, const_expr)))
 357           }
 358           _ => None
 359         }
 360       }
 361       PatLit(expr) => { Some(val(eval_const_expr(cx.tcx, expr))) }
 362       PatRange(lo, hi) => {
 363         Some(range(eval_const_expr(cx.tcx, lo), eval_const_expr(cx.tcx, hi)))
 364       }
 365       PatStruct(..) => {
 366         let def_map = cx.tcx.def_map.borrow();
 367         match def_map.get().find(&pat.id) {
 368           Some(&DefVariant(_, id, _)) => Some(variant(id)),
 369           _ => Some(single)
 370         }
 371       }
 372       PatUniq(_) | PatTup(_) | PatRegion(..) => {
 373         Some(single)
 374       }
 375       PatVec(ref before, slice, ref after) => {
 376         match slice {
 377           Some(_) => None,
 378           None => Some(vec(before.len() + after.len()))
 379         }
 380       }
 381     }
 382 }
 383
 384 fn is_wild(cx: &MatchCheckCtxt, p: @Pat) -> bool {
 385     let pat = raw_pat(p);
 386     match pat.node {
 387       PatWild | PatWildMulti => { true }
 388       PatIdent(_, _, _) => {
 389         let def_map = cx.tcx.def_map.borrow();
 390         match def_map.get().find(&pat.id) {
 391           Some(&DefVariant(_, _, _)) | Some(&DefStatic(..)) => { false }
 392           _ => { true }
 393         }
 394       }
 395       _ => { false }
 396     }
 397 }
 398
 399 fn missing_ctor(cx: &MatchCheckCtxt,
 400                     m: &matrix,
 401                     left_ty: ty::t)
 402                  -> Option<ctor> {
 403     match ty::get(left_ty).sty {
 404       ty::ty_box(_) | ty::ty_uniq(_) | ty::ty_rptr(..) | ty::ty_tup(_) |
 405       ty::ty_struct(..) => {
 406         for r in m.iter() {
 407             if !is_wild(cx, r[0]) { return None; }
 408         }
 409         return Some(single);
 410       }
 411       ty::ty_enum(eid, _) => {
 412         let mut found = ~[];
 413         for r in m.iter() {
 414             let r = pat_ctor_id(cx, r[0]);
 415             for id in r.iter() {
 416                 if !found.contains(id) {
 417                     found.push((*id).clone());
 418                 }
 419             }
 420         }
 421         let variants = ty::enum_variants(cx.tcx, eid);
 422         if found.len() != (*variants).len() {
 423             for v in (*variants).iter() {
 424                 if !found.iter().any(|x| x == &(variant(v.id))) {
 425                     return Some(variant(v.id));
 426                 }
 427             }
 428             fail!();
 429         } else { None }
 430       }
 431       ty::ty_nil => None,
 432       ty::ty_bool => {
 433         let mut true_found = false;
 434         let mut false_found = false;
 435         for r in m.iter() {
 436             match pat_ctor_id(cx, r[0]) {
 437               None => (),
 438               Some(val(const_bool(true))) => true_found = true,
 439               Some(val(const_bool(false))) => false_found = true,
 440               _ => fail!("impossible case")
 441             }
 442         }
 443         if true_found && false_found { None }
 444         else if true_found { Some(val(const_bool(false))) }
 445         else { Some(val(const_bool(true))) }
 446       }
 447       ty::ty_vec(_, ty::vstore_fixed(n)) => {
 448         let mut missing = true;
 449         let mut wrong = false;
 450         for r in m.iter() {
 451           match r[0].node {
 452             PatVec(ref before, ref slice, ref after) => {
 453               let count = before.len() + after.len();
 454               if (count < n && slice.is_none()) || count > n {
 455                 wrong = true;
 456               }
 457               if count == n || (count < n && slice.is_some()) {
 458                 missing = false;
 459               }
 460             }
 461             _ => {}
 462           }
 463         }
 464         match (wrong, missing) {
 465           (true, _) => Some(vec(n)), // should be compile-time error
 466           (_, true) => Some(vec(n)),
 467           _         => None
 468         }
 469       }
 470       ty::ty_unboxed_vec(..) | ty::ty_vec(..) => {
 471
 472         // Find the lengths and slices of all vector patterns.
 473         let mut vec_pat_lens = m.iter().filter_map(|r| {
 474             match r[0].node {
 475                 PatVec(ref before, ref slice, ref after) => {
 476                     Some((before.len() + after.len(), slice.is_some()))
 477                 }
 478                 _ => None
 479             }
 480         }).collect::<~[(uint, bool)]>();
 481
 482         // Sort them by length such that for patterns of the same length,
 483         // those with a destructured slice come first.
 484         vec_pat_lens.sort_by(|&(len1, slice1), &(len2, slice2)| {
 485                     if len1 == len2 {
 486                         slice2.cmp(&slice1)
 487                     } else {
 488                         len1.cmp(&len2)
 489                     }
 490                 });
 491         vec_pat_lens.dedup();
 492
 493         let mut found_slice = false;
 494         let mut next = 0;
 495         let mut missing = None;
 496         for &(length, slice) in vec_pat_lens.iter() {
 497             if length != next {
 498                 missing = Some(next);
 499                 break;
 500             }
 501             if slice {
 502                 found_slice = true;
 503                 break;
 504             }
 505             next += 1;
 506         }
 507
 508         // We found patterns of all lengths within <0, next), yet there was no
 509         // pattern with a slice - therefore, we report vec(next) as missing.
 510         if !found_slice {
 511             missing = Some(next);
 512         }
 513         match missing {
 514           Some(k) => Some(vec(k)),
 515           None => None
 516         }
 517       }
 518       _ => Some(single)
 519     }
 520 }
 521
 522 fn ctor_arity(cx: &MatchCheckCtxt, ctor: &ctor, ty: ty::t) -> uint {
 523     match ty::get(ty).sty {
 524       ty::ty_tup(ref fs) => fs.len(),
 525       ty::ty_box(_) | ty::ty_uniq(_) | ty::ty_rptr(..) => 1u,
 526       ty::ty_enum(eid, _) => {
 527           let id = match *ctor { variant(id) => id,
 528           _ => fail!("impossible case") };
 529         match ty::enum_variants(cx.tcx, eid).iter().find(|v| v.id == id ) {
 530             Some(v) => v.args.len(),
 531             None => fail!("impossible case")
 532         }
 533       }
 534       ty::ty_struct(cid, _) => ty::lookup_struct_fields(cx.tcx, cid).len(),
 535       ty::ty_unboxed_vec(..) | ty::ty_vec(..) => {
 536         match *ctor {
 537           vec(n) => n,
 538           _ => 0u
 539         }
 540       }
 541       _ => 0u
 542     }
 543 }
 544
 545 fn wild() -> @Pat {
 546     @Pat {id: 0, node: PatWild, span: DUMMY_SP}
 547 }
 548
 549 fn wild_multi() -> @Pat {
 550     @Pat {id: 0, node: PatWildMulti, span: DUMMY_SP}
 551 }
 552
 553 fn specialize(cx: &MatchCheckCtxt,
 554                   r: &[@Pat],
 555                   ctor_id: &ctor,
 556                   arity: uint,
 557                   left_ty: ty::t)
 558                -> Option<~[@Pat]> {
 559     // Sad, but I can't get rid of this easily
 560     let r0 = (*raw_pat(r[0])).clone();
 561     match r0 {
 562         Pat{id: pat_id, node: n, span: pat_span} =>
 563             match n {
 564             PatWild => {
 565                 Some(vec::append(vec::from_elem(arity, wild()), r.tail()))
 566             }
 567             PatWildMulti => {
 568                 Some(vec::append(vec::from_elem(arity, wild_multi()), r.tail()))
 569             }
 570             PatIdent(_, _, _) => {
 571                 let opt_def = {
 572                     let def_map = cx.tcx.def_map.borrow();
 573                     def_map.get().find_copy(&pat_id)
 574                 };
 575                 match opt_def {
 576                     Some(DefVariant(_, id, _)) => {
 577                         if variant(id) == *ctor_id {
 578                             Some(r.tail().to_owned())
 579                         } else {
 580                             None
 581                         }
 582                     }
 583                     Some(DefStatic(did, _)) => {
 584                         let const_expr =
 585                             lookup_const_by_id(cx.tcx, did).unwrap();
 586                         let e_v = eval_const_expr(cx.tcx, const_expr);
 587                         let match_ = match *ctor_id {
 588                             val(ref v) => {
 589                                 match compare_const_vals(&e_v, v) {
 590                                     Some(val1) => (val1 == 0),
 591                                     None => {
 592                                         cx.tcx.sess.span_err(pat_span,
 593                                             "mismatched types between arms");
 594                                         false
 595                                     }
 596                                 }
 597                             },
 598                             range(ref c_lo, ref c_hi) => {
 599                                 let m1 = compare_const_vals(c_lo, &e_v);
 600                                 let m2 = compare_const_vals(c_hi, &e_v);
 601                                 match (m1, m2) {
 602                                     (Some(val1), Some(val2)) => {
 603                                         (val1 >= 0 && val2 <= 0)
 604                                     }
 605                                     _ => {
 606                                         cx.tcx.sess.span_err(pat_span,
 607                                             "mismatched types between ranges");
 608                                         false
 609                                     }
 610                                 }
 611                             }
 612                             single => true,
 613                             _ => fail!("type error")
 614                         };
 615                         if match_ {
 616                             Some(r.tail().to_owned())
 617                         } else {
 618                             None
 619                         }
 620                     }
 621                     _ => {
 622                         Some(
 623                             vec::append(
 624                                 vec::from_elem(arity, wild()),
 625                                 r.tail()
 626                             )
 627                         )
 628                     }
 629                 }
 630             }
 631             PatEnum(_, args) => {
 632                 let opt_def = {
 633                     let def_map = cx.tcx.def_map.borrow();
 634                     def_map.get().get_copy(&pat_id)
 635                 };
 636                 match opt_def {
 637                     DefStatic(did, _) => {
 638                         let const_expr =
 639                             lookup_const_by_id(cx.tcx, did).unwrap();
 640                         let e_v = eval_const_expr(cx.tcx, const_expr);
 641                         let match_ = match *ctor_id {
 642                             val(ref v) =>
 643                                 match compare_const_vals(&e_v, v) {
 644                                     Some(val1) => (val1 == 0),
 645                                     None => {
 646                                         cx.tcx.sess.span_err(pat_span,
 647                                             "mismatched types between arms");
 648                                         false
 649                                     }
 650                                 },
 651                             range(ref c_lo, ref c_hi) => {
 652                                 let m1 = compare_const_vals(c_lo, &e_v);
 653                                 let m2 = compare_const_vals(c_hi, &e_v);
 654                                 match (m1, m2) {
 655                                     (Some(val1), Some(val2)) => (val1 >= 0 && val2 <= 0),
 656                                     _ => {
 657                                         cx.tcx.sess.span_err(pat_span,
 658                                             "mismatched types between ranges");
 659                                         false
 660                                     }
 661                                 }
 662                             }
 663                             single => true,
 664                             _ => fail!("type error")
 665                         };
 666                         if match_ {
 667                             Some(r.tail().to_owned())
 668                         } else {
 669                             None
 670                         }
 671                     }
 672                     DefVariant(_, id, _) if variant(id) == *ctor_id => {
 673                         let args = match args {
 674                             Some(args) => args,
 675                             None => vec::from_elem(arity, wild())
 676                         };
 677                         Some(vec::append(args, r.tail()))
 678                     }
 679                     DefVariant(_, _, _) => None,
 680
 681                     DefFn(..) |
 682                     DefStruct(..) => {
 683                         let new_args;
 684                         match args {
 685                             Some(args) => new_args = args,
 686                             None => new_args = vec::from_elem(arity, wild())
 687                         }
 688                         Some(vec::append(new_args, r.tail()))
 689                     }
 690                     _ => None
 691                 }
 692             }
 693             PatStruct(_, ref pattern_fields, _) => {
 694                 // Is this a struct or an enum variant?
 695                 let opt_def = {
 696                     let def_map = cx.tcx.def_map.borrow();
 697                     def_map.get().get_copy(&pat_id)
 698                 };
 699                 match opt_def {
 700                     DefVariant(_, variant_id, _) => {
 701                         if variant(variant_id) == *ctor_id {
 702                             let struct_fields = ty::lookup_struct_fields(cx.tcx, variant_id);
 703                             let args = struct_fields.map(|sf| {
 704                                 match pattern_fields.iter().find(|f| f.ident.name == sf.name) {
 705                                     Some(f) => f.pat,
 706                                     _ => wild()
 707                                 }
 708                             });
 709                             Some(vec::append(args, r.tail()))
 710                         } else {
 711                             None
 712                         }
 713                     }
 714                     _ => {
 715                         // Grab the class data that we care about.
 716                         let class_fields;
 717                         let class_id;
 718                         match ty::get(left_ty).sty {
 719                             ty::ty_struct(cid, _) => {
 720                                 class_id = cid;
 721                                 class_fields =
 722                                     ty::lookup_struct_fields(cx.tcx,
 723                                                              class_id);
 724                             }
 725                             _ => {
 726                                 cx.tcx.sess.span_bug(
 727                                     pat_span,
 728                                     format!("struct pattern resolved to {}, \
 729                                           not a struct",
 730                                          ty_to_str(cx.tcx, left_ty)));
 731                             }
 732                         }
 733                         let args = class_fields.iter().map(|class_field| {
 734                             match pattern_fields.iter().find(|f|
 735                                             f.ident.name == class_field.name) {
 736                                 Some(f) => f.pat,
 737                                 _ => wild()
 738                             }
 739                         }).collect();
 740                         Some(vec::append(args, r.tail()))
 741                     }
 742                 }
 743             }
 744             PatTup(args) => Some(vec::append(args, r.tail())),
 745             PatUniq(a) | PatRegion(a) => {
 746                 Some(vec::append(~[a], r.tail()))
 747             }
 748             PatLit(expr) => {
 749                 let e_v = eval_const_expr(cx.tcx, expr);
 750                 let match_ = match *ctor_id {
 751                     val(ref v) => {
 752                         match compare_const_vals(&e_v, v) {
 753                             Some(val1) => val1 == 0,
 754                             None => {
 755                                 cx.tcx.sess.span_err(pat_span,
 756                                     "mismatched types between arms");
 757                                 false
 758                             }
 759                         }
 760                     },
 761                     range(ref c_lo, ref c_hi) => {
 762                         let m1 = compare_const_vals(c_lo, &e_v);
 763                         let m2 = compare_const_vals(c_hi, &e_v);
 764                         match (m1, m2) {
 765                             (Some(val1), Some(val2)) => (val1 >= 0 && val2 <= 0),
 766                             _ => {
 767                                 cx.tcx.sess.span_err(pat_span,
 768                                     "mismatched types between ranges");
 769                                 false
 770                             }
 771                         }
 772                     }
 773                     single => true,
 774                     _ => fail!("type error")
 775                 };
 776                 if match_ { Some(r.tail().to_owned()) } else { None }
 777             }
 778             PatRange(lo, hi) => {
 779                 let (c_lo, c_hi) = match *ctor_id {
 780                     val(ref v) => ((*v).clone(), (*v).clone()),
 781                     range(ref lo, ref hi) => ((*lo).clone(), (*hi).clone()),
 782                     single => return Some(r.tail().to_owned()),
 783                     _ => fail!("type error")
 784                 };
 785                 let v_lo = eval_const_expr(cx.tcx, lo);
 786                 let v_hi = eval_const_expr(cx.tcx, hi);
 787
 788                 let m1 = compare_const_vals(&c_lo, &v_lo);
 789                 let m2 = compare_const_vals(&c_hi, &v_hi);
 790                 match (m1, m2) {
 791                     (Some(val1), Some(val2)) if val1 >= 0 && val2 <= 0 => {
 792                         Some(r.tail().to_owned())
 793                     },
 794                     (Some(_), Some(_)) => None,
 795                     _ => {
 796                         cx.tcx.sess.span_err(pat_span,
 797                             "mismatched types between ranges");
 798                         None
 799                     }
 800                 }
 801             }
 802             PatVec(before, slice, after) => {
 803                 match *ctor_id {
 804                     vec(_) => {
 805                         let num_elements = before.len() + after.len();
 806                         if num_elements < arity && slice.is_some() {
 807                             Some(vec::append(
 808                                 [
 809                                     before,
 810                                     vec::from_elem(
 811                                         arity - num_elements, wild()),
 812                                     after
 813                                 ].concat_vec(),
 814                                 r.tail()
 815                             ))
 816                         } else if num_elements == arity {
 817                             Some(vec::append(
 818                                 vec::append(before, after),
 819                                 r.tail()
 820                             ))
 821                         } else {
 822                             None
 823                         }
 824                     }
 825                     _ => None
 826                 }
 827             }
 828         }
 829     }
 830 }
 831
 832 fn default(cx: &MatchCheckCtxt, r: &[@Pat]) -> Option<~[@Pat]> {
 833     if is_wild(cx, r[0]) { Some(r.tail().to_owned()) }
 834     else { None }
 835 }
 836
 837 fn check_local(v: &mut CheckMatchVisitor,
 838                    cx: &MatchCheckCtxt,
 839                    loc: &Local,
 840                    s: ()) {
 841     visit::walk_local(v, loc, s);
 842     if is_refutable(cx, loc.pat) {
 843         cx.tcx.sess.span_err(loc.pat.span,
 844                              "refutable pattern in local binding");
 845     }
 846
 847     // Check legality of move bindings.
 848     check_legality_of_move_bindings(cx, false, [ loc.pat ]);
 849 }
 850
 851 fn check_fn(v: &mut CheckMatchVisitor,
 852                 cx: &MatchCheckCtxt,
 853                 kind: &FnKind,
 854                 decl: &FnDecl,
 855                 body: &Block,
 856                 sp: Span,
 857                 id: NodeId,
 858                 s: ()) {
 859     visit::walk_fn(v, kind, decl, body, sp, id, s);
 860     for input in decl.inputs.iter() {
 861         if is_refutable(cx, input.pat) {
 862             cx.tcx.sess.span_err(input.pat.span,
 863                                  "refutable pattern in function argument");
 864         }
 865     }
 866 }
 867
 868 fn is_refutable(cx: &MatchCheckCtxt, pat: &Pat) -> bool {
 869     let opt_def = {
 870         let def_map = cx.tcx.def_map.borrow();
 871         def_map.get().find_copy(&pat.id)
 872     };
 873     match opt_def {
 874       Some(DefVariant(enum_id, _, _)) => {
 875         if ty::enum_variants(cx.tcx, enum_id).len() != 1u {
 876             return true;
 877         }
 878       }
 879       Some(DefStatic(..)) => return true,
 880       _ => ()
 881     }
 882
 883     match pat.node {
 884       PatUniq(sub) | PatRegion(sub) | PatIdent(_, _, Some(sub)) => {
 885         is_refutable(cx, sub)
 886       }
 887       PatWild | PatWildMulti | PatIdent(_, _, None) => { false }
 888       PatLit(lit) => {
 889           match lit.node {
 890             ExprLit(lit) => {
 891                 match lit.node {
 892                     LitNil => false,    // `()`
 893                     _ => true,
 894                 }
 895             }
 896             _ => true,
 897           }
 898       }
 899       PatRange(_, _) => { true }
 900       PatStruct(_, ref fields, _) => {
 901         fields.iter().any(|f| is_refutable(cx, f.pat))
 902       }
 903       PatTup(ref elts) => {
 904         elts.iter().any(|elt| is_refutable(cx, *elt))
 905       }
 906       PatEnum(_, Some(ref args)) => {
 907         args.iter().any(|a| is_refutable(cx, *a))
 908       }
 909       PatEnum(_,_) => { false }
 910       PatVec(..) => { true }
 911     }
 912 }
 913
 914 // Legality of move bindings checking
 915
 916 fn check_legality_of_move_bindings(cx: &MatchCheckCtxt,
 917                                        has_guard: bool,
 918                                        pats: &[@Pat]) {
 919     let tcx = cx.tcx;
 920     let def_map = tcx.def_map;
 921     let mut by_ref_span = None;
 922     let mut any_by_move = false;
 923     for pat in pats.iter() {
 924         pat_bindings(def_map, *pat, |bm, id, span, _path| {
 925             match bm {
 926                 BindByRef(_) => {
 927                     by_ref_span = Some(span);
 928                 }
 929                 BindByValue(_) => {
 930                     let moves_map = cx.moves_map.borrow();
 931                     if moves_map.get().contains(&id) {
 932                         any_by_move = true;
 933                     }
 934                 }
 935             }
 936         })
 937     }
 938
 939     let check_move: |&Pat, Option<@Pat>| = |p, sub| {
 940         // check legality of moving out of the enum
 941
 942         // x @ Foo(..) is legal, but x @ Foo(y) isn't.
 943         if sub.map_or(false, |p| pat_contains_bindings(def_map, p)) {
 944             tcx.sess.span_err(
 945                 p.span,
 946                 "cannot bind by-move with sub-bindings");
 947         } else if has_guard {
 948             tcx.sess.span_err(
 949                 p.span,
 950                 "cannot bind by-move into a pattern guard");
 951         } else if by_ref_span.is_some() {
 952             tcx.sess.span_err(
 953                 p.span,
 954                 "cannot bind by-move and by-ref \
 955                  in the same pattern");
 956             tcx.sess.span_note(
 957                 by_ref_span.unwrap(),
 958                 "by-ref binding occurs here");
 959         }
 960     };
 961
 962     if !any_by_move { return; } // pointless micro-optimization
 963     for pat in pats.iter() {
 964         walk_pat(*pat, |p| {
 965             if pat_is_binding(def_map, p) {
 966                 match p.node {
 967                     PatIdent(_, _, sub) => {
 968                         let moves_map = cx.moves_map.borrow();
 969                         if moves_map.get().contains(&p.id) {
 970                             check_move(p, sub);
 971                         }
 972                     }
 973                     _ => {
 974                         cx.tcx.sess.span_bug(
 975                             p.span,
 976                             format!("binding pattern {} is \
 977                                   not an identifier: {:?}",
 978                                  p.id, p.node));
 979                     }
 980                 }
 981             }
 982             true
 983         });
 984     }
 985 }