]> git.proxmox.com Git - rustc.git/blob - src/librustc_const_eval/check_match.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc_const_eval / check_match.rs
1 // Copyright 2012-2016 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 pub use self::Constructor::*;
12 use self::Usefulness::*;
13 use self::WitnessPreference::*;
14
15 use rustc::dep_graph::DepNode;
16 use rustc::middle::const_val::ConstVal;
17 use ::{eval_const_expr, eval_const_expr_partial, compare_const_vals};
18 use ::{const_expr_to_pat, lookup_const_by_id};
19 use ::EvalHint::ExprTypeChecked;
20 use rustc::hir::def::*;
21 use rustc::hir::def_id::{DefId};
22 use rustc::middle::expr_use_visitor::{ConsumeMode, Delegate, ExprUseVisitor};
23 use rustc::middle::expr_use_visitor::{LoanCause, MutateMode};
24 use rustc::middle::expr_use_visitor as euv;
25 use rustc::infer;
26 use rustc::middle::mem_categorization::{cmt};
27 use rustc::hir::pat_util::*;
28 use rustc::traits::ProjectionMode;
29 use rustc::ty::*;
30 use rustc::ty;
31 use std::cmp::Ordering;
32 use std::fmt;
33 use std::iter::{FromIterator, IntoIterator, repeat};
34
35 use rustc::hir;
36 use rustc::hir::{Pat, PatKind};
37 use rustc::hir::intravisit::{self, IdVisitor, IdVisitingOperation, Visitor, FnKind};
38 use rustc_back::slice;
39
40 use syntax::ast::{self, DUMMY_NODE_ID, NodeId};
41 use syntax::codemap::{Span, Spanned, DUMMY_SP};
42 use rustc::hir::fold::{Folder, noop_fold_pat};
43 use rustc::hir::print::pat_to_string;
44 use syntax::ptr::P;
45 use rustc::util::nodemap::FnvHashMap;
46
47 pub const DUMMY_WILD_PAT: &'static Pat = &Pat {
48 id: DUMMY_NODE_ID,
49 node: PatKind::Wild,
50 span: DUMMY_SP
51 };
52
53 struct Matrix<'a>(Vec<Vec<&'a Pat>>);
54
55 /// Pretty-printer for matrices of patterns, example:
56 /// ++++++++++++++++++++++++++
57 /// + _ + [] +
58 /// ++++++++++++++++++++++++++
59 /// + true + [First] +
60 /// ++++++++++++++++++++++++++
61 /// + true + [Second(true)] +
62 /// ++++++++++++++++++++++++++
63 /// + false + [_] +
64 /// ++++++++++++++++++++++++++
65 /// + _ + [_, _, ..tail] +
66 /// ++++++++++++++++++++++++++
67 impl<'a> fmt::Debug for Matrix<'a> {
68 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
69 write!(f, "\n")?;
70
71 let &Matrix(ref m) = self;
72 let pretty_printed_matrix: Vec<Vec<String>> = m.iter().map(|row| {
73 row.iter()
74 .map(|&pat| pat_to_string(&pat))
75 .collect::<Vec<String>>()
76 }).collect();
77
78 let column_count = m.iter().map(|row| row.len()).max().unwrap_or(0);
79 assert!(m.iter().all(|row| row.len() == column_count));
80 let column_widths: Vec<usize> = (0..column_count).map(|col| {
81 pretty_printed_matrix.iter().map(|row| row[col].len()).max().unwrap_or(0)
82 }).collect();
83
84 let total_width = column_widths.iter().cloned().sum::<usize>() + column_count * 3 + 1;
85 let br = repeat('+').take(total_width).collect::<String>();
86 write!(f, "{}\n", br)?;
87 for row in pretty_printed_matrix {
88 write!(f, "+")?;
89 for (column, pat_str) in row.into_iter().enumerate() {
90 write!(f, " ")?;
91 write!(f, "{:1$}", pat_str, column_widths[column])?;
92 write!(f, " +")?;
93 }
94 write!(f, "\n")?;
95 write!(f, "{}\n", br)?;
96 }
97 Ok(())
98 }
99 }
100
101 impl<'a> FromIterator<Vec<&'a Pat>> for Matrix<'a> {
102 fn from_iter<T: IntoIterator<Item=Vec<&'a Pat>>>(iter: T) -> Matrix<'a> {
103 Matrix(iter.into_iter().collect())
104 }
105 }
106
107 //NOTE: appears to be the only place other then InferCtxt to contain a ParamEnv
108 pub struct MatchCheckCtxt<'a, 'tcx: 'a> {
109 pub tcx: &'a TyCtxt<'tcx>,
110 pub param_env: ParameterEnvironment<'a, 'tcx>,
111 }
112
113 #[derive(Clone, PartialEq)]
114 pub enum Constructor {
115 /// The constructor of all patterns that don't vary by constructor,
116 /// e.g. struct patterns and fixed-length arrays.
117 Single,
118 /// Enum variants.
119 Variant(DefId),
120 /// Literal values.
121 ConstantValue(ConstVal),
122 /// Ranges of literal values (2..5).
123 ConstantRange(ConstVal, ConstVal),
124 /// Array patterns of length n.
125 Slice(usize),
126 /// Array patterns with a subslice.
127 SliceWithSubslice(usize, usize)
128 }
129
130 #[derive(Clone, PartialEq)]
131 enum Usefulness {
132 Useful,
133 UsefulWithWitness(Vec<P<Pat>>),
134 NotUseful
135 }
136
137 #[derive(Copy, Clone)]
138 enum WitnessPreference {
139 ConstructWitness,
140 LeaveOutWitness
141 }
142
143 impl<'a, 'tcx, 'v> Visitor<'v> for MatchCheckCtxt<'a, 'tcx> {
144 fn visit_expr(&mut self, ex: &hir::Expr) {
145 check_expr(self, ex);
146 }
147 fn visit_local(&mut self, l: &hir::Local) {
148 check_local(self, l);
149 }
150 fn visit_fn(&mut self, fk: FnKind<'v>, fd: &'v hir::FnDecl,
151 b: &'v hir::Block, s: Span, n: NodeId) {
152 check_fn(self, fk, fd, b, s, n);
153 }
154 }
155
156 pub fn check_crate(tcx: &TyCtxt) {
157 tcx.visit_all_items_in_krate(DepNode::MatchCheck, &mut MatchCheckCtxt {
158 tcx: tcx,
159 param_env: tcx.empty_parameter_environment(),
160 });
161 tcx.sess.abort_if_errors();
162 }
163
164 fn check_expr(cx: &mut MatchCheckCtxt, ex: &hir::Expr) {
165 intravisit::walk_expr(cx, ex);
166 match ex.node {
167 hir::ExprMatch(ref scrut, ref arms, source) => {
168 for arm in arms {
169 // First, check legality of move bindings.
170 check_legality_of_move_bindings(cx,
171 arm.guard.is_some(),
172 &arm.pats);
173
174 // Second, if there is a guard on each arm, make sure it isn't
175 // assigning or borrowing anything mutably.
176 match arm.guard {
177 Some(ref guard) => check_for_mutation_in_guard(cx, &guard),
178 None => {}
179 }
180 }
181
182 let mut static_inliner = StaticInliner::new(cx.tcx, None);
183 let inlined_arms = arms.iter().map(|arm| {
184 (arm.pats.iter().map(|pat| {
185 static_inliner.fold_pat((*pat).clone())
186 }).collect(), arm.guard.as_ref().map(|e| &**e))
187 }).collect::<Vec<(Vec<P<Pat>>, Option<&hir::Expr>)>>();
188
189 // Bail out early if inlining failed.
190 if static_inliner.failed {
191 return;
192 }
193
194 for pat in inlined_arms
195 .iter()
196 .flat_map(|&(ref pats, _)| pats) {
197 // Third, check legality of move bindings.
198 check_legality_of_bindings_in_at_patterns(cx, &pat);
199
200 // Fourth, check if there are any references to NaN that we should warn about.
201 check_for_static_nan(cx, &pat);
202
203 // Fifth, check if for any of the patterns that match an enumerated type
204 // are bindings with the same name as one of the variants of said type.
205 check_for_bindings_named_the_same_as_variants(cx, &pat);
206 }
207
208 // Fourth, check for unreachable arms.
209 check_arms(cx, &inlined_arms[..], source);
210
211 // Finally, check if the whole match expression is exhaustive.
212 // Check for empty enum, because is_useful only works on inhabited types.
213 let pat_ty = cx.tcx.node_id_to_type(scrut.id);
214 if inlined_arms.is_empty() {
215 if !pat_ty.is_empty(cx.tcx) {
216 // We know the type is inhabited, so this must be wrong
217 let mut err = struct_span_err!(cx.tcx.sess, ex.span, E0002,
218 "non-exhaustive patterns: type {} is non-empty",
219 pat_ty);
220 span_help!(&mut err, ex.span,
221 "Please ensure that all possible cases are being handled; \
222 possibly adding wildcards or more match arms.");
223 err.emit();
224 }
225 // If the type *is* empty, it's vacuously exhaustive
226 return;
227 }
228
229 let matrix: Matrix = inlined_arms
230 .iter()
231 .filter(|&&(_, guard)| guard.is_none())
232 .flat_map(|arm| &arm.0)
233 .map(|pat| vec![&**pat])
234 .collect();
235 check_exhaustive(cx, ex.span, &matrix, source);
236 },
237 _ => ()
238 }
239 }
240
241 fn check_for_bindings_named_the_same_as_variants(cx: &MatchCheckCtxt, pat: &Pat) {
242 pat.walk(|p| {
243 match p.node {
244 PatKind::Ident(hir::BindByValue(hir::MutImmutable), ident, None) => {
245 let pat_ty = cx.tcx.pat_ty(p);
246 if let ty::TyEnum(edef, _) = pat_ty.sty {
247 let def = cx.tcx.def_map.borrow().get(&p.id).map(|d| d.full_def());
248 if let Some(Def::Local(..)) = def {
249 if edef.variants.iter().any(|variant|
250 variant.name == ident.node.unhygienic_name
251 && variant.kind() == VariantKind::Unit
252 ) {
253 let ty_path = cx.tcx.item_path_str(edef.did);
254 let mut err = struct_span_warn!(cx.tcx.sess, p.span, E0170,
255 "pattern binding `{}` is named the same as one \
256 of the variants of the type `{}`",
257 ident.node, ty_path);
258 fileline_help!(err, p.span,
259 "if you meant to match on a variant, \
260 consider making the path in the pattern qualified: `{}::{}`",
261 ty_path, ident.node);
262 err.emit();
263 }
264 }
265 }
266 }
267 _ => ()
268 }
269 true
270 });
271 }
272
273 // Check that we do not match against a static NaN (#6804)
274 fn check_for_static_nan(cx: &MatchCheckCtxt, pat: &Pat) {
275 pat.walk(|p| {
276 if let PatKind::Lit(ref expr) = p.node {
277 match eval_const_expr_partial(cx.tcx, &expr, ExprTypeChecked, None) {
278 Ok(ConstVal::Float(f)) if f.is_nan() => {
279 span_warn!(cx.tcx.sess, p.span, E0003,
280 "unmatchable NaN in pattern, \
281 use the is_nan method in a guard instead");
282 }
283 Ok(_) => {}
284
285 Err(err) => {
286 let mut diag = struct_span_err!(cx.tcx.sess, err.span, E0471,
287 "constant evaluation error: {}",
288 err.description());
289 if !p.span.contains(err.span) {
290 diag.span_note(p.span, "in pattern here");
291 }
292 diag.emit();
293 }
294 }
295 }
296 true
297 });
298 }
299
300 // Check for unreachable patterns
301 fn check_arms(cx: &MatchCheckCtxt,
302 arms: &[(Vec<P<Pat>>, Option<&hir::Expr>)],
303 source: hir::MatchSource) {
304 let mut seen = Matrix(vec![]);
305 let mut printed_if_let_err = false;
306 for &(ref pats, guard) in arms {
307 for pat in pats {
308 let v = vec![&**pat];
309
310 match is_useful(cx, &seen, &v[..], LeaveOutWitness) {
311 NotUseful => {
312 match source {
313 hir::MatchSource::IfLetDesugar { .. } => {
314 if printed_if_let_err {
315 // we already printed an irrefutable if-let pattern error.
316 // We don't want two, that's just confusing.
317 } else {
318 // find the first arm pattern so we can use its span
319 let &(ref first_arm_pats, _) = &arms[0];
320 let first_pat = &first_arm_pats[0];
321 let span = first_pat.span;
322 span_err!(cx.tcx.sess, span, E0162, "irrefutable if-let pattern");
323 printed_if_let_err = true;
324 }
325 },
326
327 hir::MatchSource::WhileLetDesugar => {
328 // find the first arm pattern so we can use its span
329 let &(ref first_arm_pats, _) = &arms[0];
330 let first_pat = &first_arm_pats[0];
331 let span = first_pat.span;
332 span_err!(cx.tcx.sess, span, E0165, "irrefutable while-let pattern");
333 },
334
335 hir::MatchSource::ForLoopDesugar => {
336 // this is a bug, because on `match iter.next()` we cover
337 // `Some(<head>)` and `None`. It's impossible to have an unreachable
338 // pattern
339 // (see libsyntax/ext/expand.rs for the full expansion of a for loop)
340 span_bug!(pat.span, "unreachable for-loop pattern")
341 },
342
343 hir::MatchSource::Normal => {
344 span_err!(cx.tcx.sess, pat.span, E0001, "unreachable pattern")
345 },
346
347 hir::MatchSource::TryDesugar => {
348 span_bug!(pat.span, "unreachable try pattern")
349 },
350 }
351 }
352 Useful => (),
353 UsefulWithWitness(_) => bug!()
354 }
355 if guard.is_none() {
356 let Matrix(mut rows) = seen;
357 rows.push(v);
358 seen = Matrix(rows);
359 }
360 }
361 }
362 }
363
364 fn raw_pat<'a>(p: &'a Pat) -> &'a Pat {
365 match p.node {
366 PatKind::Ident(_, _, Some(ref s)) => raw_pat(&s),
367 _ => p
368 }
369 }
370
371 fn check_exhaustive(cx: &MatchCheckCtxt, sp: Span, matrix: &Matrix, source: hir::MatchSource) {
372 match is_useful(cx, matrix, &[DUMMY_WILD_PAT], ConstructWitness) {
373 UsefulWithWitness(pats) => {
374 let witnesses = if pats.is_empty() {
375 vec![DUMMY_WILD_PAT]
376 } else {
377 pats.iter().map(|w| &**w ).collect()
378 };
379 match source {
380 hir::MatchSource::ForLoopDesugar => {
381 // `witnesses[0]` has the form `Some(<head>)`, peel off the `Some`
382 let witness = match witnesses[0].node {
383 PatKind::TupleStruct(_, Some(ref pats)) => match &pats[..] {
384 [ref pat] => &**pat,
385 _ => bug!(),
386 },
387 _ => bug!(),
388 };
389 span_err!(cx.tcx.sess, sp, E0297,
390 "refutable pattern in `for` loop binding: \
391 `{}` not covered",
392 pat_to_string(witness));
393 },
394 _ => {
395 let pattern_strings: Vec<_> = witnesses.iter().map(|w| {
396 pat_to_string(w)
397 }).collect();
398 const LIMIT: usize = 3;
399 let joined_patterns = match pattern_strings.len() {
400 0 => bug!(),
401 1 => format!("`{}`", pattern_strings[0]),
402 2...LIMIT => {
403 let (tail, head) = pattern_strings.split_last().unwrap();
404 format!("`{}`", head.join("`, `") + "` and `" + tail)
405 },
406 _ => {
407 let (head, tail) = pattern_strings.split_at(LIMIT);
408 format!("`{}` and {} more", head.join("`, `"), tail.len())
409 }
410 };
411 span_err!(cx.tcx.sess, sp, E0004,
412 "non-exhaustive patterns: {} not covered",
413 joined_patterns
414 );
415 },
416 }
417 }
418 NotUseful => {
419 // This is good, wildcard pattern isn't reachable
420 },
421 _ => bug!()
422 }
423 }
424
425 fn const_val_to_expr(value: &ConstVal) -> P<hir::Expr> {
426 let node = match value {
427 &ConstVal::Bool(b) => ast::LitKind::Bool(b),
428 _ => bug!()
429 };
430 P(hir::Expr {
431 id: 0,
432 node: hir::ExprLit(P(Spanned { node: node, span: DUMMY_SP })),
433 span: DUMMY_SP,
434 attrs: None,
435 })
436 }
437
438 pub struct StaticInliner<'a, 'tcx: 'a> {
439 pub tcx: &'a TyCtxt<'tcx>,
440 pub failed: bool,
441 pub renaming_map: Option<&'a mut FnvHashMap<(NodeId, Span), NodeId>>,
442 }
443
444 impl<'a, 'tcx> StaticInliner<'a, 'tcx> {
445 pub fn new<'b>(tcx: &'b TyCtxt<'tcx>,
446 renaming_map: Option<&'b mut FnvHashMap<(NodeId, Span), NodeId>>)
447 -> StaticInliner<'b, 'tcx> {
448 StaticInliner {
449 tcx: tcx,
450 failed: false,
451 renaming_map: renaming_map
452 }
453 }
454 }
455
456 struct RenamingRecorder<'map> {
457 substituted_node_id: NodeId,
458 origin_span: Span,
459 renaming_map: &'map mut FnvHashMap<(NodeId, Span), NodeId>
460 }
461
462 impl<'map> IdVisitingOperation for RenamingRecorder<'map> {
463 fn visit_id(&mut self, node_id: NodeId) {
464 let key = (node_id, self.origin_span);
465 self.renaming_map.insert(key, self.substituted_node_id);
466 }
467 }
468
469 impl<'a, 'tcx> Folder for StaticInliner<'a, 'tcx> {
470 fn fold_pat(&mut self, pat: P<Pat>) -> P<Pat> {
471 return match pat.node {
472 PatKind::Ident(..) | PatKind::Path(..) | PatKind::QPath(..) => {
473 let def = self.tcx.def_map.borrow().get(&pat.id).map(|d| d.full_def());
474 match def {
475 Some(Def::AssociatedConst(did)) |
476 Some(Def::Const(did)) => {
477 let substs = Some(self.tcx.node_id_item_substs(pat.id).substs);
478 if let Some((const_expr, _)) = lookup_const_by_id(self.tcx, did, substs) {
479 match const_expr_to_pat(self.tcx, const_expr, pat.id, pat.span) {
480 Ok(new_pat) => {
481 if let Some(ref mut map) = self.renaming_map {
482 // Record any renamings we do here
483 record_renamings(const_expr, &pat, map);
484 }
485 new_pat
486 }
487 Err(def_id) => {
488 self.failed = true;
489 self.tcx.sess.span_err(
490 pat.span,
491 &format!("constants of the type `{}` \
492 cannot be used in patterns",
493 self.tcx.item_path_str(def_id)));
494 pat
495 }
496 }
497 } else {
498 self.failed = true;
499 span_err!(self.tcx.sess, pat.span, E0158,
500 "statics cannot be referenced in patterns");
501 pat
502 }
503 }
504 _ => noop_fold_pat(pat, self)
505 }
506 }
507 _ => noop_fold_pat(pat, self)
508 };
509
510 fn record_renamings(const_expr: &hir::Expr,
511 substituted_pat: &hir::Pat,
512 renaming_map: &mut FnvHashMap<(NodeId, Span), NodeId>) {
513 let mut renaming_recorder = RenamingRecorder {
514 substituted_node_id: substituted_pat.id,
515 origin_span: substituted_pat.span,
516 renaming_map: renaming_map,
517 };
518
519 let mut id_visitor = IdVisitor::new(&mut renaming_recorder);
520
521 id_visitor.visit_expr(const_expr);
522 }
523 }
524 }
525
526 /// Constructs a partial witness for a pattern given a list of
527 /// patterns expanded by the specialization step.
528 ///
529 /// When a pattern P is discovered to be useful, this function is used bottom-up
530 /// to reconstruct a complete witness, e.g. a pattern P' that covers a subset
531 /// of values, V, where each value in that set is not covered by any previously
532 /// used patterns and is covered by the pattern P'. Examples:
533 ///
534 /// left_ty: tuple of 3 elements
535 /// pats: [10, 20, _] => (10, 20, _)
536 ///
537 /// left_ty: struct X { a: (bool, &'static str), b: usize}
538 /// pats: [(false, "foo"), 42] => X { a: (false, "foo"), b: 42 }
539 fn construct_witness<'a,'tcx>(cx: &MatchCheckCtxt<'a,'tcx>, ctor: &Constructor,
540 pats: Vec<&Pat>, left_ty: Ty<'tcx>) -> P<Pat> {
541 let pats_len = pats.len();
542 let mut pats = pats.into_iter().map(|p| P((*p).clone()));
543 let pat = match left_ty.sty {
544 ty::TyTuple(_) => PatKind::Tup(pats.collect()),
545
546 ty::TyEnum(adt, _) | ty::TyStruct(adt, _) => {
547 let v = ctor.variant_for_adt(adt);
548 match v.kind() {
549 VariantKind::Struct => {
550 let field_pats: hir::HirVec<_> = v.fields.iter()
551 .zip(pats)
552 .filter(|&(_, ref pat)| pat.node != PatKind::Wild)
553 .map(|(field, pat)| Spanned {
554 span: DUMMY_SP,
555 node: hir::FieldPat {
556 name: field.name,
557 pat: pat,
558 is_shorthand: false,
559 }
560 }).collect();
561 let has_more_fields = field_pats.len() < pats_len;
562 PatKind::Struct(def_to_path(cx.tcx, v.did), field_pats, has_more_fields)
563 }
564 VariantKind::Tuple => {
565 PatKind::TupleStruct(def_to_path(cx.tcx, v.did), Some(pats.collect()))
566 }
567 VariantKind::Unit => {
568 PatKind::Path(def_to_path(cx.tcx, v.did))
569 }
570 }
571 }
572
573 ty::TyRef(_, ty::TypeAndMut { ty, mutbl }) => {
574 match ty.sty {
575 ty::TyArray(_, n) => match ctor {
576 &Single => {
577 assert_eq!(pats_len, n);
578 PatKind::Vec(pats.collect(), None, hir::HirVec::new())
579 },
580 _ => bug!()
581 },
582 ty::TySlice(_) => match ctor {
583 &Slice(n) => {
584 assert_eq!(pats_len, n);
585 PatKind::Vec(pats.collect(), None, hir::HirVec::new())
586 },
587 _ => bug!()
588 },
589 ty::TyStr => PatKind::Wild,
590
591 _ => {
592 assert_eq!(pats_len, 1);
593 PatKind::Ref(pats.nth(0).unwrap(), mutbl)
594 }
595 }
596 }
597
598 ty::TyArray(_, len) => {
599 assert_eq!(pats_len, len);
600 PatKind::Vec(pats.collect(), None, hir::HirVec::new())
601 }
602
603 _ => {
604 match *ctor {
605 ConstantValue(ref v) => PatKind::Lit(const_val_to_expr(v)),
606 _ => PatKind::Wild,
607 }
608 }
609 };
610
611 P(hir::Pat {
612 id: 0,
613 node: pat,
614 span: DUMMY_SP
615 })
616 }
617
618 impl Constructor {
619 fn variant_for_adt<'tcx, 'container, 'a>(&self,
620 adt: &'a ty::AdtDefData<'tcx, 'container>)
621 -> &'a VariantDefData<'tcx, 'container> {
622 match self {
623 &Variant(vid) => adt.variant_with_id(vid),
624 _ => adt.struct_variant()
625 }
626 }
627 }
628
629 fn missing_constructors(cx: &MatchCheckCtxt, &Matrix(ref rows): &Matrix,
630 left_ty: Ty, max_slice_length: usize) -> Vec<Constructor> {
631 let used_constructors: Vec<Constructor> = rows.iter()
632 .flat_map(|row| pat_constructors(cx, row[0], left_ty, max_slice_length))
633 .collect();
634 all_constructors(cx, left_ty, max_slice_length)
635 .into_iter()
636 .filter(|c| !used_constructors.contains(c))
637 .collect()
638 }
639
640 /// This determines the set of all possible constructors of a pattern matching
641 /// values of type `left_ty`. For vectors, this would normally be an infinite set
642 /// but is instead bounded by the maximum fixed length of slice patterns in
643 /// the column of patterns being analyzed.
644 fn all_constructors(_cx: &MatchCheckCtxt, left_ty: Ty,
645 max_slice_length: usize) -> Vec<Constructor> {
646 match left_ty.sty {
647 ty::TyBool =>
648 [true, false].iter().map(|b| ConstantValue(ConstVal::Bool(*b))).collect(),
649
650 ty::TyRef(_, ty::TypeAndMut { ty, .. }) => match ty.sty {
651 ty::TySlice(_) =>
652 (0..max_slice_length+1).map(|length| Slice(length)).collect(),
653 _ => vec![Single]
654 },
655
656 ty::TyEnum(def, _) => def.variants.iter().map(|v| Variant(v.did)).collect(),
657 _ => vec![Single]
658 }
659 }
660
661 // Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html
662 //
663 // Whether a vector `v` of patterns is 'useful' in relation to a set of such
664 // vectors `m` is defined as there being a set of inputs that will match `v`
665 // but not any of the sets in `m`.
666 //
667 // This is used both for reachability checking (if a pattern isn't useful in
668 // relation to preceding patterns, it is not reachable) and exhaustiveness
669 // checking (if a wildcard pattern is useful in relation to a matrix, the
670 // matrix isn't exhaustive).
671
672 // Note: is_useful doesn't work on empty types, as the paper notes.
673 // So it assumes that v is non-empty.
674 fn is_useful(cx: &MatchCheckCtxt,
675 matrix: &Matrix,
676 v: &[&Pat],
677 witness: WitnessPreference)
678 -> Usefulness {
679 let &Matrix(ref rows) = matrix;
680 debug!("{:?}", matrix);
681 if rows.is_empty() {
682 return match witness {
683 ConstructWitness => UsefulWithWitness(vec!()),
684 LeaveOutWitness => Useful
685 };
686 }
687 if rows[0].is_empty() {
688 return NotUseful;
689 }
690 assert!(rows.iter().all(|r| r.len() == v.len()));
691 let real_pat = match rows.iter().find(|r| (*r)[0].id != DUMMY_NODE_ID) {
692 Some(r) => raw_pat(r[0]),
693 None if v.is_empty() => return NotUseful,
694 None => v[0]
695 };
696 let left_ty = if real_pat.id == DUMMY_NODE_ID {
697 cx.tcx.mk_nil()
698 } else {
699 let left_ty = cx.tcx.pat_ty(&real_pat);
700
701 match real_pat.node {
702 PatKind::Ident(hir::BindByRef(..), _, _) => {
703 left_ty.builtin_deref(false, NoPreference).unwrap().ty
704 }
705 _ => left_ty,
706 }
707 };
708
709 let max_slice_length = rows.iter().filter_map(|row| match row[0].node {
710 PatKind::Vec(ref before, _, ref after) => Some(before.len() + after.len()),
711 _ => None
712 }).max().map_or(0, |v| v + 1);
713
714 let constructors = pat_constructors(cx, v[0], left_ty, max_slice_length);
715 if constructors.is_empty() {
716 let constructors = missing_constructors(cx, matrix, left_ty, max_slice_length);
717 if constructors.is_empty() {
718 all_constructors(cx, left_ty, max_slice_length).into_iter().map(|c| {
719 match is_useful_specialized(cx, matrix, v, c.clone(), left_ty, witness) {
720 UsefulWithWitness(pats) => UsefulWithWitness({
721 let arity = constructor_arity(cx, &c, left_ty);
722 let mut result = {
723 let pat_slice = &pats[..];
724 let subpats: Vec<_> = (0..arity).map(|i| {
725 pat_slice.get(i).map_or(DUMMY_WILD_PAT, |p| &**p)
726 }).collect();
727 vec![construct_witness(cx, &c, subpats, left_ty)]
728 };
729 result.extend(pats.into_iter().skip(arity));
730 result
731 }),
732 result => result
733 }
734 }).find(|result| result != &NotUseful).unwrap_or(NotUseful)
735 } else {
736 let matrix = rows.iter().filter_map(|r| {
737 if pat_is_binding_or_wild(&cx.tcx.def_map.borrow(), raw_pat(r[0])) {
738 Some(r[1..].to_vec())
739 } else {
740 None
741 }
742 }).collect();
743 match is_useful(cx, &matrix, &v[1..], witness) {
744 UsefulWithWitness(pats) => {
745 let mut new_pats: Vec<_> = constructors.into_iter().map(|constructor| {
746 let arity = constructor_arity(cx, &constructor, left_ty);
747 let wild_pats = vec![DUMMY_WILD_PAT; arity];
748 construct_witness(cx, &constructor, wild_pats, left_ty)
749 }).collect();
750 new_pats.extend(pats);
751 UsefulWithWitness(new_pats)
752 },
753 result => result
754 }
755 }
756 } else {
757 constructors.into_iter().map(|c|
758 is_useful_specialized(cx, matrix, v, c.clone(), left_ty, witness)
759 ).find(|result| result != &NotUseful).unwrap_or(NotUseful)
760 }
761 }
762
763 fn is_useful_specialized(cx: &MatchCheckCtxt, &Matrix(ref m): &Matrix,
764 v: &[&Pat], ctor: Constructor, lty: Ty,
765 witness: WitnessPreference) -> Usefulness {
766 let arity = constructor_arity(cx, &ctor, lty);
767 let matrix = Matrix(m.iter().filter_map(|r| {
768 specialize(cx, &r[..], &ctor, 0, arity)
769 }).collect());
770 match specialize(cx, v, &ctor, 0, arity) {
771 Some(v) => is_useful(cx, &matrix, &v[..], witness),
772 None => NotUseful
773 }
774 }
775
776 /// Determines the constructors that the given pattern can be specialized to.
777 ///
778 /// In most cases, there's only one constructor that a specific pattern
779 /// represents, such as a specific enum variant or a specific literal value.
780 /// Slice patterns, however, can match slices of different lengths. For instance,
781 /// `[a, b, ..tail]` can match a slice of length 2, 3, 4 and so on.
782 ///
783 /// On the other hand, a wild pattern and an identifier pattern cannot be
784 /// specialized in any way.
785 fn pat_constructors(cx: &MatchCheckCtxt, p: &Pat,
786 left_ty: Ty, max_slice_length: usize) -> Vec<Constructor> {
787 let pat = raw_pat(p);
788 match pat.node {
789 PatKind::Struct(..) | PatKind::TupleStruct(..) | PatKind::Path(..) | PatKind::Ident(..) =>
790 match cx.tcx.def_map.borrow().get(&pat.id).unwrap().full_def() {
791 Def::Const(..) | Def::AssociatedConst(..) =>
792 span_bug!(pat.span, "const pattern should've \
793 been rewritten"),
794 Def::Struct(..) | Def::TyAlias(..) => vec![Single],
795 Def::Variant(_, id) => vec![Variant(id)],
796 Def::Local(..) => vec![],
797 def => span_bug!(pat.span, "pat_constructors: unexpected \
798 definition {:?}", def),
799 },
800 PatKind::QPath(..) =>
801 span_bug!(pat.span, "const pattern should've been rewritten"),
802 PatKind::Lit(ref expr) =>
803 vec!(ConstantValue(eval_const_expr(cx.tcx, &expr))),
804 PatKind::Range(ref lo, ref hi) =>
805 vec!(ConstantRange(eval_const_expr(cx.tcx, &lo), eval_const_expr(cx.tcx, &hi))),
806 PatKind::Vec(ref before, ref slice, ref after) =>
807 match left_ty.sty {
808 ty::TyArray(_, _) => vec!(Single),
809 _ => if slice.is_some() {
810 (before.len() + after.len()..max_slice_length+1)
811 .map(|length| Slice(length))
812 .collect()
813 } else {
814 vec!(Slice(before.len() + after.len()))
815 }
816 },
817 PatKind::Box(_) | PatKind::Tup(_) | PatKind::Ref(..) =>
818 vec!(Single),
819 PatKind::Wild =>
820 vec!(),
821 }
822 }
823
824 /// This computes the arity of a constructor. The arity of a constructor
825 /// is how many subpattern patterns of that constructor should be expanded to.
826 ///
827 /// For instance, a tuple pattern (_, 42, Some([])) has the arity of 3.
828 /// A struct pattern's arity is the number of fields it contains, etc.
829 pub fn constructor_arity(_cx: &MatchCheckCtxt, ctor: &Constructor, ty: Ty) -> usize {
830 match ty.sty {
831 ty::TyTuple(ref fs) => fs.len(),
832 ty::TyBox(_) => 1,
833 ty::TyRef(_, ty::TypeAndMut { ty, .. }) => match ty.sty {
834 ty::TySlice(_) => match *ctor {
835 Slice(length) => length,
836 ConstantValue(_) => 0,
837 _ => bug!()
838 },
839 ty::TyStr => 0,
840 _ => 1
841 },
842 ty::TyEnum(adt, _) | ty::TyStruct(adt, _) => {
843 ctor.variant_for_adt(adt).fields.len()
844 }
845 ty::TyArray(_, n) => n,
846 _ => 0
847 }
848 }
849
850 fn range_covered_by_constructor(ctor: &Constructor,
851 from: &ConstVal, to: &ConstVal) -> Option<bool> {
852 let (c_from, c_to) = match *ctor {
853 ConstantValue(ref value) => (value, value),
854 ConstantRange(ref from, ref to) => (from, to),
855 Single => return Some(true),
856 _ => bug!()
857 };
858 let cmp_from = compare_const_vals(c_from, from);
859 let cmp_to = compare_const_vals(c_to, to);
860 match (cmp_from, cmp_to) {
861 (Some(cmp_from), Some(cmp_to)) => {
862 Some(cmp_from != Ordering::Less && cmp_to != Ordering::Greater)
863 }
864 _ => None
865 }
866 }
867
868 /// This is the main specialization step. It expands the first pattern in the given row
869 /// into `arity` patterns based on the constructor. For most patterns, the step is trivial,
870 /// for instance tuple patterns are flattened and box patterns expand into their inner pattern.
871 ///
872 /// OTOH, slice patterns with a subslice pattern (..tail) can be expanded into multiple
873 /// different patterns.
874 /// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing
875 /// fields filled with wild patterns.
876 pub fn specialize<'a>(cx: &MatchCheckCtxt, r: &[&'a Pat],
877 constructor: &Constructor, col: usize, arity: usize) -> Option<Vec<&'a Pat>> {
878 let &Pat {
879 id: pat_id, ref node, span: pat_span
880 } = raw_pat(r[col]);
881 let head: Option<Vec<&Pat>> = match *node {
882 PatKind::Wild =>
883 Some(vec![DUMMY_WILD_PAT; arity]),
884
885 PatKind::Path(..) | PatKind::Ident(..) => {
886 let def = cx.tcx.def_map.borrow().get(&pat_id).unwrap().full_def();
887 match def {
888 Def::Const(..) | Def::AssociatedConst(..) =>
889 span_bug!(pat_span, "const pattern should've \
890 been rewritten"),
891 Def::Variant(_, id) if *constructor != Variant(id) => None,
892 Def::Variant(..) | Def::Struct(..) => Some(Vec::new()),
893 Def::Local(..) => Some(vec![DUMMY_WILD_PAT; arity]),
894 _ => span_bug!(pat_span, "specialize: unexpected \
895 definition {:?}", def),
896 }
897 }
898
899 PatKind::TupleStruct(_, ref args) => {
900 let def = cx.tcx.def_map.borrow().get(&pat_id).unwrap().full_def();
901 match def {
902 Def::Const(..) | Def::AssociatedConst(..) =>
903 span_bug!(pat_span, "const pattern should've \
904 been rewritten"),
905 Def::Variant(_, id) if *constructor != Variant(id) => None,
906 Def::Variant(..) | Def::Struct(..) => {
907 Some(match args {
908 &Some(ref args) => args.iter().map(|p| &**p).collect(),
909 &None => vec![DUMMY_WILD_PAT; arity],
910 })
911 }
912 _ => None
913 }
914 }
915
916 PatKind::QPath(_, _) => {
917 span_bug!(pat_span, "const pattern should've been rewritten")
918 }
919
920 PatKind::Struct(_, ref pattern_fields, _) => {
921 let def = cx.tcx.def_map.borrow().get(&pat_id).unwrap().full_def();
922 let adt = cx.tcx.node_id_to_type(pat_id).ty_adt_def().unwrap();
923 let variant = constructor.variant_for_adt(adt);
924 let def_variant = adt.variant_of_def(def);
925 if variant.did == def_variant.did {
926 Some(variant.fields.iter().map(|sf| {
927 match pattern_fields.iter().find(|f| f.node.name == sf.name) {
928 Some(ref f) => &*f.node.pat,
929 _ => DUMMY_WILD_PAT
930 }
931 }).collect())
932 } else {
933 None
934 }
935 }
936
937 PatKind::Tup(ref args) =>
938 Some(args.iter().map(|p| &**p).collect()),
939
940 PatKind::Box(ref inner) | PatKind::Ref(ref inner, _) =>
941 Some(vec![&**inner]),
942
943 PatKind::Lit(ref expr) => {
944 let expr_value = eval_const_expr(cx.tcx, &expr);
945 match range_covered_by_constructor(constructor, &expr_value, &expr_value) {
946 Some(true) => Some(vec![]),
947 Some(false) => None,
948 None => {
949 span_err!(cx.tcx.sess, pat_span, E0298, "mismatched types between arms");
950 None
951 }
952 }
953 }
954
955 PatKind::Range(ref from, ref to) => {
956 let from_value = eval_const_expr(cx.tcx, &from);
957 let to_value = eval_const_expr(cx.tcx, &to);
958 match range_covered_by_constructor(constructor, &from_value, &to_value) {
959 Some(true) => Some(vec![]),
960 Some(false) => None,
961 None => {
962 span_err!(cx.tcx.sess, pat_span, E0299, "mismatched types between arms");
963 None
964 }
965 }
966 }
967
968 PatKind::Vec(ref before, ref slice, ref after) => {
969 match *constructor {
970 // Fixed-length vectors.
971 Single => {
972 let mut pats: Vec<&Pat> = before.iter().map(|p| &**p).collect();
973 pats.extend(repeat(DUMMY_WILD_PAT).take(arity - before.len() - after.len()));
974 pats.extend(after.iter().map(|p| &**p));
975 Some(pats)
976 },
977 Slice(length) if before.len() + after.len() <= length && slice.is_some() => {
978 let mut pats: Vec<&Pat> = before.iter().map(|p| &**p).collect();
979 pats.extend(repeat(DUMMY_WILD_PAT).take(arity - before.len() - after.len()));
980 pats.extend(after.iter().map(|p| &**p));
981 Some(pats)
982 },
983 Slice(length) if before.len() + after.len() == length => {
984 let mut pats: Vec<&Pat> = before.iter().map(|p| &**p).collect();
985 pats.extend(after.iter().map(|p| &**p));
986 Some(pats)
987 },
988 SliceWithSubslice(prefix, suffix)
989 if before.len() == prefix
990 && after.len() == suffix
991 && slice.is_some() => {
992 let mut pats: Vec<&Pat> = before.iter().map(|p| &**p).collect();
993 pats.extend(after.iter().map(|p| &**p));
994 Some(pats)
995 }
996 _ => None
997 }
998 }
999 };
1000 head.map(|mut head| {
1001 head.extend_from_slice(&r[..col]);
1002 head.extend_from_slice(&r[col + 1..]);
1003 head
1004 })
1005 }
1006
1007 fn check_local(cx: &mut MatchCheckCtxt, loc: &hir::Local) {
1008 intravisit::walk_local(cx, loc);
1009
1010 let pat = StaticInliner::new(cx.tcx, None).fold_pat(loc.pat.clone());
1011 check_irrefutable(cx, &pat, false);
1012
1013 // Check legality of move bindings and `@` patterns.
1014 check_legality_of_move_bindings(cx, false, slice::ref_slice(&loc.pat));
1015 check_legality_of_bindings_in_at_patterns(cx, &loc.pat);
1016 }
1017
1018 fn check_fn(cx: &mut MatchCheckCtxt,
1019 kind: FnKind,
1020 decl: &hir::FnDecl,
1021 body: &hir::Block,
1022 sp: Span,
1023 fn_id: NodeId) {
1024 match kind {
1025 FnKind::Closure(_) => {}
1026 _ => cx.param_env = ParameterEnvironment::for_item(cx.tcx, fn_id),
1027 }
1028
1029 intravisit::walk_fn(cx, kind, decl, body, sp);
1030
1031 for input in &decl.inputs {
1032 check_irrefutable(cx, &input.pat, true);
1033 check_legality_of_move_bindings(cx, false, slice::ref_slice(&input.pat));
1034 check_legality_of_bindings_in_at_patterns(cx, &input.pat);
1035 }
1036 }
1037
1038 fn check_irrefutable(cx: &MatchCheckCtxt, pat: &Pat, is_fn_arg: bool) {
1039 let origin = if is_fn_arg {
1040 "function argument"
1041 } else {
1042 "local binding"
1043 };
1044
1045 is_refutable(cx, pat, |uncovered_pat| {
1046 span_err!(cx.tcx.sess, pat.span, E0005,
1047 "refutable pattern in {}: `{}` not covered",
1048 origin,
1049 pat_to_string(uncovered_pat),
1050 );
1051 });
1052 }
1053
1054 fn is_refutable<A, F>(cx: &MatchCheckCtxt, pat: &Pat, refutable: F) -> Option<A> where
1055 F: FnOnce(&Pat) -> A,
1056 {
1057 let pats = Matrix(vec!(vec!(pat)));
1058 match is_useful(cx, &pats, &[DUMMY_WILD_PAT], ConstructWitness) {
1059 UsefulWithWitness(pats) => Some(refutable(&pats[0])),
1060 NotUseful => None,
1061 Useful => bug!()
1062 }
1063 }
1064
1065 // Legality of move bindings checking
1066 fn check_legality_of_move_bindings(cx: &MatchCheckCtxt,
1067 has_guard: bool,
1068 pats: &[P<Pat>]) {
1069 let tcx = cx.tcx;
1070 let def_map = &tcx.def_map;
1071 let mut by_ref_span = None;
1072 for pat in pats {
1073 pat_bindings(def_map, &pat, |bm, _, span, _path| {
1074 match bm {
1075 hir::BindByRef(_) => {
1076 by_ref_span = Some(span);
1077 }
1078 hir::BindByValue(_) => {
1079 }
1080 }
1081 })
1082 }
1083
1084 let check_move = |p: &Pat, sub: Option<&Pat>| {
1085 // check legality of moving out of the enum
1086
1087 // x @ Foo(..) is legal, but x @ Foo(y) isn't.
1088 if sub.map_or(false, |p| pat_contains_bindings(&def_map.borrow(), &p)) {
1089 span_err!(cx.tcx.sess, p.span, E0007, "cannot bind by-move with sub-bindings");
1090 } else if has_guard {
1091 span_err!(cx.tcx.sess, p.span, E0008, "cannot bind by-move into a pattern guard");
1092 } else if by_ref_span.is_some() {
1093 let mut err = struct_span_err!(cx.tcx.sess, p.span, E0009,
1094 "cannot bind by-move and by-ref in the same pattern");
1095 span_note!(&mut err, by_ref_span.unwrap(), "by-ref binding occurs here");
1096 err.emit();
1097 }
1098 };
1099
1100 for pat in pats {
1101 pat.walk(|p| {
1102 if pat_is_binding(&def_map.borrow(), &p) {
1103 match p.node {
1104 PatKind::Ident(hir::BindByValue(_), _, ref sub) => {
1105 let pat_ty = tcx.node_id_to_type(p.id);
1106 //FIXME: (@jroesch) this code should be floated up as well
1107 let infcx = infer::new_infer_ctxt(cx.tcx,
1108 &cx.tcx.tables,
1109 Some(cx.param_env.clone()),
1110 ProjectionMode::AnyFinal);
1111 if infcx.type_moves_by_default(pat_ty, pat.span) {
1112 check_move(p, sub.as_ref().map(|p| &**p));
1113 }
1114 }
1115 PatKind::Ident(hir::BindByRef(_), _, _) => {
1116 }
1117 _ => {
1118 span_bug!(
1119 p.span,
1120 "binding pattern {} is not an identifier: {:?}",
1121 p.id,
1122 p.node);
1123 }
1124 }
1125 }
1126 true
1127 });
1128 }
1129 }
1130
1131 /// Ensures that a pattern guard doesn't borrow by mutable reference or
1132 /// assign.
1133 fn check_for_mutation_in_guard<'a, 'tcx>(cx: &'a MatchCheckCtxt<'a, 'tcx>,
1134 guard: &hir::Expr) {
1135 let mut checker = MutationChecker {
1136 cx: cx,
1137 };
1138
1139 let infcx = infer::new_infer_ctxt(cx.tcx,
1140 &cx.tcx.tables,
1141 Some(checker.cx.param_env.clone()),
1142 ProjectionMode::AnyFinal);
1143
1144 let mut visitor = ExprUseVisitor::new(&mut checker, &infcx);
1145 visitor.walk_expr(guard);
1146 }
1147
1148 struct MutationChecker<'a, 'tcx: 'a> {
1149 cx: &'a MatchCheckCtxt<'a, 'tcx>,
1150 }
1151
1152 impl<'a, 'tcx> Delegate<'tcx> for MutationChecker<'a, 'tcx> {
1153 fn matched_pat(&mut self, _: &Pat, _: cmt, _: euv::MatchMode) {}
1154 fn consume(&mut self, _: NodeId, _: Span, _: cmt, _: ConsumeMode) {}
1155 fn consume_pat(&mut self, _: &Pat, _: cmt, _: ConsumeMode) {}
1156 fn borrow(&mut self,
1157 _: NodeId,
1158 span: Span,
1159 _: cmt,
1160 _: Region,
1161 kind: BorrowKind,
1162 _: LoanCause) {
1163 match kind {
1164 MutBorrow => {
1165 span_err!(self.cx.tcx.sess, span, E0301,
1166 "cannot mutably borrow in a pattern guard")
1167 }
1168 ImmBorrow | UniqueImmBorrow => {}
1169 }
1170 }
1171 fn decl_without_init(&mut self, _: NodeId, _: Span) {}
1172 fn mutate(&mut self, _: NodeId, span: Span, _: cmt, mode: MutateMode) {
1173 match mode {
1174 MutateMode::JustWrite | MutateMode::WriteAndRead => {
1175 span_err!(self.cx.tcx.sess, span, E0302, "cannot assign in a pattern guard")
1176 }
1177 MutateMode::Init => {}
1178 }
1179 }
1180 }
1181
1182 /// Forbids bindings in `@` patterns. This is necessary for memory safety,
1183 /// because of the way rvalues are handled in the borrow check. (See issue
1184 /// #14587.)
1185 fn check_legality_of_bindings_in_at_patterns(cx: &MatchCheckCtxt, pat: &Pat) {
1186 AtBindingPatternVisitor { cx: cx, bindings_allowed: true }.visit_pat(pat);
1187 }
1188
1189 struct AtBindingPatternVisitor<'a, 'b:'a, 'tcx:'b> {
1190 cx: &'a MatchCheckCtxt<'b, 'tcx>,
1191 bindings_allowed: bool
1192 }
1193
1194 impl<'a, 'b, 'tcx, 'v> Visitor<'v> for AtBindingPatternVisitor<'a, 'b, 'tcx> {
1195 fn visit_pat(&mut self, pat: &Pat) {
1196 if !self.bindings_allowed && pat_is_binding(&self.cx.tcx.def_map.borrow(), pat) {
1197 span_err!(self.cx.tcx.sess, pat.span, E0303,
1198 "pattern bindings are not allowed \
1199 after an `@`");
1200 }
1201
1202 match pat.node {
1203 PatKind::Ident(_, _, Some(_)) => {
1204 let bindings_were_allowed = self.bindings_allowed;
1205 self.bindings_allowed = false;
1206 intravisit::walk_pat(self, pat);
1207 self.bindings_allowed = bindings_were_allowed;
1208 }
1209 _ => intravisit::walk_pat(self, pat),
1210 }
1211 }
1212 }