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.
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.
11 pub use self::Constructor
::*;
12 use self::Usefulness
::*;
13 use self::WitnessPreference
::*;
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
;
26 use rustc
::middle
::mem_categorization
::{cmt}
;
27 use rustc
::hir
::pat_util
::*;
28 use rustc
::traits
::ProjectionMode
;
31 use std
::cmp
::Ordering
;
33 use std
::iter
::{FromIterator, IntoIterator, repeat}
;
36 use rustc
::hir
::{Pat, PatKind}
;
37 use rustc
::hir
::intravisit
::{self, IdVisitor, IdVisitingOperation, Visitor, FnKind}
;
38 use rustc_back
::slice
;
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
;
45 use rustc
::util
::nodemap
::FnvHashMap
;
47 pub const DUMMY_WILD_PAT
: &'
static Pat
= &Pat
{
53 struct Matrix
<'a
>(Vec
<Vec
<&'a Pat
>>);
55 /// Pretty-printer for matrices of patterns, example:
56 /// ++++++++++++++++++++++++++
58 /// ++++++++++++++++++++++++++
59 /// + true + [First] +
60 /// ++++++++++++++++++++++++++
61 /// + true + [Second(true)] +
62 /// ++++++++++++++++++++++++++
64 /// ++++++++++++++++++++++++++
65 /// + _ + [_, _, ..tail] +
66 /// ++++++++++++++++++++++++++
67 impl<'a
> fmt
::Debug
for Matrix
<'a
> {
68 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
71 let &Matrix(ref m
) = self;
72 let pretty_printed_matrix
: Vec
<Vec
<String
>> = m
.iter().map(|row
| {
74 .map(|&pat
| pat_to_string(&pat
))
75 .collect
::<Vec
<String
>>()
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)
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
{
89 for (column
, pat_str
) in row
.into_iter().enumerate() {
91 write
!(f
, "{:1$}", pat_str
, column_widths
[column
])?
;
95 write
!(f
, "{}\n", br
)?
;
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())
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
>,
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.
121 ConstantValue(ConstVal
),
122 /// Ranges of literal values (2..5).
123 ConstantRange(ConstVal
, ConstVal
),
124 /// Array patterns of length n.
126 /// Array patterns with a subslice.
127 SliceWithSubslice(usize, usize)
130 #[derive(Clone, PartialEq)]
133 UsefulWithWitness(Vec
<P
<Pat
>>),
137 #[derive(Copy, Clone)]
138 enum WitnessPreference
{
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
);
147 fn visit_local(&mut self, l
: &hir
::Local
) {
148 check_local(self, l
);
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
);
156 pub fn check_crate(tcx
: &TyCtxt
) {
157 tcx
.visit_all_items_in_krate(DepNode
::MatchCheck
, &mut MatchCheckCtxt
{
159 param_env
: tcx
.empty_parameter_environment(),
161 tcx
.sess
.abort_if_errors();
164 fn check_expr(cx
: &mut MatchCheckCtxt
, ex
: &hir
::Expr
) {
165 intravisit
::walk_expr(cx
, ex
);
167 hir
::ExprMatch(ref scrut
, ref arms
, source
) => {
169 // First, check legality of move bindings.
170 check_legality_of_move_bindings(cx
,
174 // Second, if there is a guard on each arm, make sure it isn't
175 // assigning or borrowing anything mutably.
177 Some(ref guard
) => check_for_mutation_in_guard(cx
, &guard
),
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
>)>>();
189 // Bail out early if inlining failed.
190 if static_inliner
.failed
{
194 for pat
in inlined_arms
196 .flat_map(|&(ref pats
, _
)| pats
) {
197 // Third, check legality of move bindings.
198 check_legality_of_bindings_in_at_patterns(cx
, &pat
);
200 // Fourth, check if there are any references to NaN that we should warn about.
201 check_for_static_nan(cx
, &pat
);
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
);
208 // Fourth, check for unreachable arms.
209 check_arms(cx
, &inlined_arms
[..], source
);
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",
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.");
225 // If the type *is* empty, it's vacuously exhaustive
229 let matrix
: Matrix
= inlined_arms
231 .filter(|&&(_
, guard
)| guard
.is_none())
232 .flat_map(|arm
| &arm
.0)
233 .map(|pat
| vec
![&**pat
])
235 check_exhaustive(cx
, ex
.span
, &matrix
, source
);
241 fn check_for_bindings_named_the_same_as_variants(cx
: &MatchCheckCtxt
, pat
: &Pat
) {
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
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
);
273 // Check that we do not match against a static NaN (#6804)
274 fn check_for_static_nan(cx
: &MatchCheckCtxt
, pat
: &Pat
) {
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");
286 let mut diag
= struct_span_err
!(cx
.tcx
.sess
, err
.span
, E0471
,
287 "constant evaluation error: {}",
289 if !p
.span
.contains(err
.span
) {
290 diag
.span_note(p
.span
, "in pattern here");
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
{
308 let v
= vec
![&**pat
];
310 match is_useful(cx
, &seen
, &v
[..], LeaveOutWitness
) {
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.
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;
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");
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
339 // (see libsyntax/ext/expand.rs for the full expansion of a for loop)
340 span_bug
!(pat
.span
, "unreachable for-loop pattern")
343 hir
::MatchSource
::Normal
=> {
344 span_err
!(cx
.tcx
.sess
, pat
.span
, E0001
, "unreachable pattern")
347 hir
::MatchSource
::TryDesugar
=> {
348 span_bug
!(pat
.span
, "unreachable try pattern")
353 UsefulWithWitness(_
) => bug
!()
356 let Matrix(mut rows
) = seen
;
364 fn raw_pat
<'a
>(p
: &'a Pat
) -> &'a Pat
{
366 PatKind
::Ident(_
, _
, Some(ref s
)) => raw_pat(&s
),
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() {
377 pats
.iter().map(|w
| &**w
).collect()
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
[..] {
389 span_err
!(cx
.tcx
.sess
, sp
, E0297
,
390 "refutable pattern in `for` loop binding: \
392 pat_to_string(witness
));
395 let pattern_strings
: Vec
<_
> = witnesses
.iter().map(|w
| {
398 const LIMIT
: usize = 3;
399 let joined_patterns
= match pattern_strings
.len() {
401 1 => format
!("`{}`", pattern_strings
[0]),
403 let (tail
, head
) = pattern_strings
.split_last().unwrap();
404 format
!("`{}`", head
.join("`, `") + "` and `" + tail
)
407 let (head
, tail
) = pattern_strings
.split_at(LIMIT
);
408 format
!("`{}` and {} more", head
.join("`, `"), tail
.len())
411 span_err
!(cx
.tcx
.sess
, sp
, E0004
,
412 "non-exhaustive patterns: {} not covered",
419 // This is good, wildcard pattern isn't reachable
425 fn const_val_to_expr(value
: &ConstVal
) -> P
<hir
::Expr
> {
426 let node
= match value
{
427 &ConstVal
::Bool(b
) => ast
::LitKind
::Bool(b
),
432 node
: hir
::ExprLit(P(Spanned { node: node, span: DUMMY_SP }
)),
438 pub struct StaticInliner
<'a
, 'tcx
: 'a
> {
439 pub tcx
: &'a TyCtxt
<'tcx
>,
441 pub renaming_map
: Option
<&'a
mut FnvHashMap
<(NodeId
, Span
), NodeId
>>,
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
> {
451 renaming_map
: renaming_map
456 struct RenamingRecorder
<'map
> {
457 substituted_node_id
: NodeId
,
459 renaming_map
: &'map
mut FnvHashMap
<(NodeId
, Span
), NodeId
>
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
);
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());
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
) {
481 if let Some(ref mut map
) = self.renaming_map
{
482 // Record any renamings we do here
483 record_renamings(const_expr
, &pat
, map
);
489 self.tcx
.sess
.span_err(
491 &format
!("constants of the type `{}` \
492 cannot be used in patterns",
493 self.tcx
.item_path_str(def_id
)));
499 span_err
!(self.tcx
.sess
, pat
.span
, E0158
,
500 "statics cannot be referenced in patterns");
504 _
=> noop_fold_pat(pat
, self)
507 _
=> noop_fold_pat(pat
, self)
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
,
519 let mut id_visitor
= IdVisitor
::new(&mut renaming_recorder
);
521 id_visitor
.visit_expr(const_expr
);
526 /// Constructs a partial witness for a pattern given a list of
527 /// patterns expanded by the specialization step.
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:
534 /// left_ty: tuple of 3 elements
535 /// pats: [10, 20, _] => (10, 20, _)
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()),
546 ty
::TyEnum(adt
, _
) | ty
::TyStruct(adt
, _
) => {
547 let v
= ctor
.variant_for_adt(adt
);
549 VariantKind
::Struct
=> {
550 let field_pats
: hir
::HirVec
<_
> = v
.fields
.iter()
552 .filter(|&(_
, ref pat
)| pat
.node
!= PatKind
::Wild
)
553 .map(|(field
, pat
)| Spanned
{
555 node
: hir
::FieldPat
{
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
)
564 VariantKind
::Tuple
=> {
565 PatKind
::TupleStruct(def_to_path(cx
.tcx
, v
.did
), Some(pats
.collect()))
567 VariantKind
::Unit
=> {
568 PatKind
::Path(def_to_path(cx
.tcx
, v
.did
))
573 ty
::TyRef(_
, ty
::TypeAndMut { ty, mutbl }
) => {
575 ty
::TyArray(_
, n
) => match ctor
{
577 assert_eq
!(pats_len
, n
);
578 PatKind
::Vec(pats
.collect(), None
, hir
::HirVec
::new())
582 ty
::TySlice(_
) => match ctor
{
584 assert_eq
!(pats_len
, n
);
585 PatKind
::Vec(pats
.collect(), None
, hir
::HirVec
::new())
589 ty
::TyStr
=> PatKind
::Wild
,
592 assert_eq
!(pats_len
, 1);
593 PatKind
::Ref(pats
.nth(0).unwrap(), mutbl
)
598 ty
::TyArray(_
, len
) => {
599 assert_eq
!(pats_len
, len
);
600 PatKind
::Vec(pats
.collect(), None
, hir
::HirVec
::new())
605 ConstantValue(ref v
) => PatKind
::Lit(const_val_to_expr(v
)),
619 fn variant_for_adt
<'tcx
, 'container
, 'a
>(&self,
620 adt
: &'a ty
::AdtDefData
<'tcx
, 'container
>)
621 -> &'a VariantDefData
<'tcx
, 'container
> {
623 &Variant(vid
) => adt
.variant_with_id(vid
),
624 _
=> adt
.struct_variant()
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
))
634 all_constructors(cx
, left_ty
, max_slice_length
)
636 .filter(|c
| !used_constructors
.contains(c
))
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
> {
648 [true, false].iter().map(|b
| ConstantValue(ConstVal
::Bool(*b
))).collect(),
650 ty
::TyRef(_
, ty
::TypeAndMut { ty, .. }
) => match ty
.sty
{
652 (0..max_slice_length
+1).map(|length
| Slice(length
)).collect(),
656 ty
::TyEnum(def
, _
) => def
.variants
.iter().map(|v
| Variant(v
.did
)).collect(),
661 // Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html
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`.
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).
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
,
677 witness
: WitnessPreference
)
679 let &Matrix(ref rows
) = matrix
;
680 debug
!("{:?}", matrix
);
682 return match witness
{
683 ConstructWitness
=> UsefulWithWitness(vec
!()),
684 LeaveOutWitness
=> Useful
687 if rows
[0].is_empty() {
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
,
696 let left_ty
= if real_pat
.id
== DUMMY_NODE_ID
{
699 let left_ty
= cx
.tcx
.pat_ty(&real_pat
);
701 match real_pat
.node
{
702 PatKind
::Ident(hir
::BindByRef(..), _
, _
) => {
703 left_ty
.builtin_deref(false, NoPreference
).unwrap().ty
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()),
712 }).max().map_or(0, |v
| v
+ 1);
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
);
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
)
727 vec
![construct_witness(cx
, &c
, subpats
, left_ty
)]
729 result
.extend(pats
.into_iter().skip(arity
));
734 }).find(|result
| result
!= &NotUseful
).unwrap_or(NotUseful
)
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())
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
)
750 new_pats
.extend(pats
);
751 UsefulWithWitness(new_pats
)
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
)
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
)
770 match specialize(cx
, v
, &ctor
, 0, arity
) {
771 Some(v
) => is_useful(cx
, &matrix
, &v
[..], witness
),
776 /// Determines the constructors that the given pattern can be specialized to.
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.
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
);
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 \
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
),
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
) =>
808 ty
::TyArray(_
, _
) => vec
!(Single
),
809 _
=> if slice
.is_some() {
810 (before
.len() + after
.len()..max_slice_length
+1)
811 .map(|length
| Slice(length
))
814 vec
!(Slice(before
.len() + after
.len()))
817 PatKind
::Box(_
) | PatKind
::Tup(_
) | PatKind
::Ref(..) =>
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.
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 {
831 ty
::TyTuple(ref fs
) => fs
.len(),
833 ty
::TyRef(_
, ty
::TypeAndMut { ty, .. }
) => match ty
.sty
{
834 ty
::TySlice(_
) => match *ctor
{
835 Slice(length
) => length
,
836 ConstantValue(_
) => 0,
842 ty
::TyEnum(adt
, _
) | ty
::TyStruct(adt
, _
) => {
843 ctor
.variant_for_adt(adt
).fields
.len()
845 ty
::TyArray(_
, n
) => n
,
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),
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
)
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.
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
>> {
879 id
: pat_id
, ref node
, span
: pat_span
881 let head
: Option
<Vec
<&Pat
>> = match *node
{
883 Some(vec
![DUMMY_WILD_PAT
; arity
]),
885 PatKind
::Path(..) | PatKind
::Ident(..) => {
886 let def
= cx
.tcx
.def_map
.borrow().get(&pat_id
).unwrap().full_def();
888 Def
::Const(..) | Def
::AssociatedConst(..) =>
889 span_bug
!(pat_span
, "const pattern should've \
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
),
899 PatKind
::TupleStruct(_
, ref args
) => {
900 let def
= cx
.tcx
.def_map
.borrow().get(&pat_id
).unwrap().full_def();
902 Def
::Const(..) | Def
::AssociatedConst(..) =>
903 span_bug
!(pat_span
, "const pattern should've \
905 Def
::Variant(_
, id
) if *constructor
!= Variant(id
) => None
,
906 Def
::Variant(..) | Def
::Struct(..) => {
908 &Some(ref args
) => args
.iter().map(|p
| &**p
).collect(),
909 &None
=> vec
![DUMMY_WILD_PAT
; arity
],
916 PatKind
::QPath(_
, _
) => {
917 span_bug
!(pat_span
, "const pattern should've been rewritten")
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
,
937 PatKind
::Tup(ref args
) =>
938 Some(args
.iter().map(|p
| &**p
).collect()),
940 PatKind
::Box(ref inner
) | PatKind
::Ref(ref inner
, _
) =>
941 Some(vec
![&**inner
]),
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
![]),
949 span_err
!(cx
.tcx
.sess
, pat_span
, E0298
, "mismatched types between arms");
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
![]),
962 span_err
!(cx
.tcx
.sess
, pat_span
, E0299
, "mismatched types between arms");
968 PatKind
::Vec(ref before
, ref slice
, ref after
) => {
970 // Fixed-length vectors.
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
));
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
));
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
));
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
));
1000 head
.map(|mut head
| {
1001 head
.extend_from_slice(&r
[..col
]);
1002 head
.extend_from_slice(&r
[col
+ 1..]);
1007 fn check_local(cx
: &mut MatchCheckCtxt
, loc
: &hir
::Local
) {
1008 intravisit
::walk_local(cx
, loc
);
1010 let pat
= StaticInliner
::new(cx
.tcx
, None
).fold_pat(loc
.pat
.clone());
1011 check_irrefutable(cx
, &pat
, false);
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
);
1018 fn check_fn(cx
: &mut MatchCheckCtxt
,
1025 FnKind
::Closure(_
) => {}
1026 _
=> cx
.param_env
= ParameterEnvironment
::for_item(cx
.tcx
, fn_id
),
1029 intravisit
::walk_fn(cx
, kind
, decl
, body
, sp
);
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
);
1038 fn check_irrefutable(cx
: &MatchCheckCtxt
, pat
: &Pat
, is_fn_arg
: bool
) {
1039 let origin
= if is_fn_arg
{
1045 is_refutable(cx
, pat
, |uncovered_pat
| {
1046 span_err
!(cx
.tcx
.sess
, pat
.span
, E0005
,
1047 "refutable pattern in {}: `{}` not covered",
1049 pat_to_string(uncovered_pat
),
1054 fn is_refutable
<A
, F
>(cx
: &MatchCheckCtxt
, pat
: &Pat
, refutable
: F
) -> Option
<A
> where
1055 F
: FnOnce(&Pat
) -> A
,
1057 let pats
= Matrix(vec
!(vec
!(pat
)));
1058 match is_useful(cx
, &pats
, &[DUMMY_WILD_PAT
], ConstructWitness
) {
1059 UsefulWithWitness(pats
) => Some(refutable(&pats
[0])),
1065 // Legality of move bindings checking
1066 fn check_legality_of_move_bindings(cx
: &MatchCheckCtxt
,
1070 let def_map
= &tcx
.def_map
;
1071 let mut by_ref_span
= None
;
1073 pat_bindings(def_map
, &pat
, |bm
, _
, span
, _path
| {
1075 hir
::BindByRef(_
) => {
1076 by_ref_span
= Some(span
);
1078 hir
::BindByValue(_
) => {
1084 let check_move
= |p
: &Pat
, sub
: Option
<&Pat
>| {
1085 // check legality of moving out of the enum
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");
1102 if pat_is_binding(&def_map
.borrow(), &p
) {
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
,
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
));
1115 PatKind
::Ident(hir
::BindByRef(_
), _
, _
) => {
1120 "binding pattern {} is not an identifier: {:?}",
1131 /// Ensures that a pattern guard doesn't borrow by mutable reference or
1133 fn check_for_mutation_in_guard
<'a
, 'tcx
>(cx
: &'a MatchCheckCtxt
<'a
, 'tcx
>,
1134 guard
: &hir
::Expr
) {
1135 let mut checker
= MutationChecker
{
1139 let infcx
= infer
::new_infer_ctxt(cx
.tcx
,
1141 Some(checker
.cx
.param_env
.clone()),
1142 ProjectionMode
::AnyFinal
);
1144 let mut visitor
= ExprUseVisitor
::new(&mut checker
, &infcx
);
1145 visitor
.walk_expr(guard
);
1148 struct MutationChecker
<'a
, 'tcx
: 'a
> {
1149 cx
: &'a MatchCheckCtxt
<'a
, 'tcx
>,
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,
1165 span_err
!(self.cx
.tcx
.sess
, span
, E0301
,
1166 "cannot mutably borrow in a pattern guard")
1168 ImmBorrow
| UniqueImmBorrow
=> {}
1171 fn decl_without_init(&mut self, _
: NodeId
, _
: Span
) {}
1172 fn mutate(&mut self, _
: NodeId
, span
: Span
, _
: cmt
, mode
: MutateMode
) {
1174 MutateMode
::JustWrite
| MutateMode
::WriteAndRead
=> {
1175 span_err
!(self.cx
.tcx
.sess
, span
, E0302
, "cannot assign in a pattern guard")
1177 MutateMode
::Init
=> {}
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
1185 fn check_legality_of_bindings_in_at_patterns(cx
: &MatchCheckCtxt
, pat
: &Pat
) {
1186 AtBindingPatternVisitor { cx: cx, bindings_allowed: true }
.visit_pat(pat
);
1189 struct AtBindingPatternVisitor
<'a
, 'b
:'a
, 'tcx
:'b
> {
1190 cx
: &'a MatchCheckCtxt
<'b
, 'tcx
>,
1191 bindings_allowed
: bool
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 \
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
;
1209 _
=> intravisit
::walk_pat(self, pat
),