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