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