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