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.
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 middle
::const_eval
::{compare_const_vals, ConstVal}
;
16 use middle
::const_eval
::{eval_const_expr, eval_const_expr_partial}
;
17 use middle
::const_eval
::{const_expr_to_pat, lookup_const_by_id}
;
18 use middle
::const_eval
::EvalHint
::ExprTypeChecked
;
20 use middle
::def_id
::{DefId}
;
21 use middle
::expr_use_visitor
::{ConsumeMode, Delegate, ExprUseVisitor, Init}
;
22 use middle
::expr_use_visitor
::{JustWrite, LoanCause, MutateMode}
;
23 use middle
::expr_use_visitor
::WriteAndRead
;
24 use middle
::expr_use_visitor
as euv
;
26 use middle
::mem_categorization
::{cmt}
;
27 use middle
::pat_util
::*;
30 use std
::cmp
::Ordering
;
32 use std
::iter
::{FromIterator, IntoIterator, repeat}
;
35 use rustc_front
::hir
::Pat
;
36 use rustc_front
::intravisit
::{self, Visitor, FnKind}
;
37 use rustc_front
::util
as front_util
;
38 use rustc_back
::slice
;
40 use syntax
::ast
::{self, DUMMY_NODE_ID, NodeId}
;
42 use syntax
::codemap
::{Span, Spanned, DUMMY_SP}
;
43 use rustc_front
::fold
::{Folder, noop_fold_pat}
;
44 use rustc_front
::print
::pprust
::pat_to_string
;
46 use util
::nodemap
::FnvHashMap
;
48 pub const DUMMY_WILD_PAT
: &'
static Pat
= &Pat
{
54 struct Matrix
<'a
>(Vec
<Vec
<&'a Pat
>>);
56 /// Pretty-printer for matrices of patterns, example:
57 /// ++++++++++++++++++++++++++
59 /// ++++++++++++++++++++++++++
60 /// + true + [First] +
61 /// ++++++++++++++++++++++++++
62 /// + true + [Second(true)] +
63 /// ++++++++++++++++++++++++++
65 /// ++++++++++++++++++++++++++
66 /// + _ + [_, _, ..tail] +
67 /// ++++++++++++++++++++++++++
68 impl<'a
> fmt
::Debug
for Matrix
<'a
> {
69 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
70 try
!(write
!(f
, "\n"));
72 let &Matrix(ref m
) = self;
73 let pretty_printed_matrix
: Vec
<Vec
<String
>> = m
.iter().map(|row
| {
75 .map(|&pat
| pat_to_string(&*pat
))
76 .collect
::<Vec
<String
>>()
79 let column_count
= m
.iter().map(|row
| row
.len()).max().unwrap_or(0);
80 assert
!(m
.iter().all(|row
| row
.len() == column_count
));
81 let column_widths
: Vec
<usize> = (0..column_count
).map(|col
| {
82 pretty_printed_matrix
.iter().map(|row
| row
[col
].len()).max().unwrap_or(0)
85 let total_width
= column_widths
.iter().cloned().sum
::<usize>() + column_count
* 3 + 1;
86 let br
= repeat('
+'
).take(total_width
).collect
::<String
>();
87 try
!(write
!(f
, "{}\n", br
));
88 for row
in pretty_printed_matrix
{
90 for (column
, pat_str
) in row
.into_iter().enumerate() {
92 try
!(write
!(f
, "{:1$}", pat_str
, column_widths
[column
]));
93 try
!(write
!(f
, " +"));
95 try
!(write
!(f
, "\n"));
96 try
!(write
!(f
, "{}\n", br
));
102 impl<'a
> FromIterator
<Vec
<&'a Pat
>> for Matrix
<'a
> {
103 fn from_iter
<T
: IntoIterator
<Item
=Vec
<&'a Pat
>>>(iter
: T
) -> Matrix
<'a
> {
104 Matrix(iter
.into_iter().collect())
108 //NOTE: appears to be the only place other then InferCtxt to contain a ParamEnv
109 pub struct MatchCheckCtxt
<'a
, 'tcx
: 'a
> {
110 pub tcx
: &'a ty
::ctxt
<'tcx
>,
111 pub param_env
: ParameterEnvironment
<'a
, 'tcx
>,
114 #[derive(Clone, PartialEq)]
115 pub enum Constructor
{
116 /// The constructor of all patterns that don't vary by constructor,
117 /// e.g. struct patterns and fixed-length arrays.
122 ConstantValue(ConstVal
),
123 /// Ranges of literal values (2..5).
124 ConstantRange(ConstVal
, ConstVal
),
125 /// Array patterns of length n.
127 /// Array patterns with a subslice.
128 SliceWithSubslice(usize, usize)
131 #[derive(Clone, PartialEq)]
134 UsefulWithWitness(Vec
<P
<Pat
>>),
138 #[derive(Copy, Clone)]
139 enum WitnessPreference
{
144 impl<'a
, 'tcx
, 'v
> Visitor
<'v
> for MatchCheckCtxt
<'a
, 'tcx
> {
145 fn visit_expr(&mut self, ex
: &hir
::Expr
) {
146 check_expr(self, ex
);
148 fn visit_local(&mut self, l
: &hir
::Local
) {
149 check_local(self, l
);
151 fn visit_fn(&mut self, fk
: FnKind
<'v
>, fd
: &'v hir
::FnDecl
,
152 b
: &'v hir
::Block
, s
: Span
, n
: NodeId
) {
153 check_fn(self, fk
, fd
, b
, s
, n
);
157 pub fn check_crate(tcx
: &ty
::ctxt
) {
158 tcx
.map
.krate().visit_all_items(&mut MatchCheckCtxt
{
160 param_env
: tcx
.empty_parameter_environment(),
162 tcx
.sess
.abort_if_errors();
165 fn check_expr(cx
: &mut MatchCheckCtxt
, ex
: &hir
::Expr
) {
166 intravisit
::walk_expr(cx
, ex
);
168 hir
::ExprMatch(ref scrut
, ref arms
, source
) => {
170 // First, check legality of move bindings.
171 check_legality_of_move_bindings(cx
,
175 // Second, if there is a guard on each arm, make sure it isn't
176 // assigning or borrowing anything mutably.
178 Some(ref guard
) => check_for_mutation_in_guard(cx
, &**guard
),
183 let mut static_inliner
= StaticInliner
::new(cx
.tcx
, None
);
184 let inlined_arms
= arms
.iter().map(|arm
| {
185 (arm
.pats
.iter().map(|pat
| {
186 static_inliner
.fold_pat((*pat
).clone())
187 }).collect(), arm
.guard
.as_ref().map(|e
| &**e
))
188 }).collect
::<Vec
<(Vec
<P
<Pat
>>, Option
<&hir
::Expr
>)>>();
190 // Bail out early if inlining failed.
191 if static_inliner
.failed
{
195 for pat
in inlined_arms
197 .flat_map(|&(ref pats
, _
)| pats
) {
198 // Third, check legality of move bindings.
199 check_legality_of_bindings_in_at_patterns(cx
, &**pat
);
201 // Fourth, check if there are any references to NaN that we should warn about.
202 check_for_static_nan(cx
, &**pat
);
204 // Fifth, check if for any of the patterns that match an enumerated type
205 // are bindings with the same name as one of the variants of said type.
206 check_for_bindings_named_the_same_as_variants(cx
, &**pat
);
209 // Fourth, check for unreachable arms.
210 check_arms(cx
, &inlined_arms
[..], source
);
212 // Finally, check if the whole match expression is exhaustive.
213 // Check for empty enum, because is_useful only works on inhabited types.
214 let pat_ty
= cx
.tcx
.node_id_to_type(scrut
.id
);
215 if inlined_arms
.is_empty() {
216 if !pat_ty
.is_empty(cx
.tcx
) {
217 // We know the type is inhabited, so this must be wrong
218 span_err
!(cx
.tcx
.sess
, ex
.span
, E0002
,
219 "non-exhaustive patterns: type {} is non-empty",
221 span_help
!(cx
.tcx
.sess
, ex
.span
,
222 "Please ensure that all possible cases are being handled; \
223 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
) {
242 front_util
::walk_pat(pat
, |p
| {
244 hir
::PatIdent(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(DefLocal(..)) = def
{
249 if edef
.variants
.iter().any(|variant
|
250 variant
.name
== ident
.node
.unhygienic_name
251 && variant
.kind() == VariantKind
::Unit
253 span_warn
!(cx
.tcx
.sess
, p
.span
, E0170
,
254 "pattern binding `{}` is named the same as one \
255 of the variants of the type `{}`",
257 fileline_help
!(cx
.tcx
.sess
, p
.span
,
258 "if you meant to match on a variant, \
259 consider making the path in the pattern qualified: `{}::{}`",
271 // Check that we do not match against a static NaN (#6804)
272 fn check_for_static_nan(cx
: &MatchCheckCtxt
, pat
: &Pat
) {
273 front_util
::walk_pat(pat
, |p
| {
274 if let hir
::PatLit(ref expr
) = p
.node
{
275 match eval_const_expr_partial(cx
.tcx
, &**expr
, ExprTypeChecked
, None
) {
276 Ok(ConstVal
::Float(f
)) if f
.is_nan() => {
277 span_warn
!(cx
.tcx
.sess
, p
.span
, E0003
,
278 "unmatchable NaN in pattern, \
279 use the is_nan method in a guard instead");
284 span_err
!(cx
.tcx
.sess
, err
.span
, E0471
,
285 "constant evaluation error: {}",
287 if !p
.span
.contains(err
.span
) {
288 cx
.tcx
.sess
.span_note(p
.span
,
298 // Check for unreachable patterns
299 fn check_arms(cx
: &MatchCheckCtxt
,
300 arms
: &[(Vec
<P
<Pat
>>, Option
<&hir
::Expr
>)],
301 source
: hir
::MatchSource
) {
302 let mut seen
= Matrix(vec
![]);
303 let mut printed_if_let_err
= false;
304 for &(ref pats
, guard
) in arms
{
306 let v
= vec
![&**pat
];
308 match is_useful(cx
, &seen
, &v
[..], LeaveOutWitness
) {
311 hir
::MatchSource
::IfLetDesugar { .. }
=> {
312 if printed_if_let_err
{
313 // we already printed an irrefutable if-let pattern error.
314 // We don't want two, that's just confusing.
316 // find the first arm pattern so we can use its span
317 let &(ref first_arm_pats
, _
) = &arms
[0];
318 let first_pat
= &first_arm_pats
[0];
319 let span
= first_pat
.span
;
320 span_err
!(cx
.tcx
.sess
, span
, E0162
, "irrefutable if-let pattern");
321 printed_if_let_err
= true;
325 hir
::MatchSource
::WhileLetDesugar
=> {
326 // find the first arm pattern so we can use its span
327 let &(ref first_arm_pats
, _
) = &arms
[0];
328 let first_pat
= &first_arm_pats
[0];
329 let span
= first_pat
.span
;
330 span_err
!(cx
.tcx
.sess
, span
, E0165
, "irrefutable while-let pattern");
333 hir
::MatchSource
::ForLoopDesugar
=> {
334 // this is a bug, because on `match iter.next()` we cover
335 // `Some(<head>)` and `None`. It's impossible to have an unreachable
337 // (see libsyntax/ext/expand.rs for the full expansion of a for loop)
338 cx
.tcx
.sess
.span_bug(pat
.span
, "unreachable for-loop pattern")
341 hir
::MatchSource
::Normal
=> {
342 span_err
!(cx
.tcx
.sess
, pat
.span
, E0001
, "unreachable pattern")
347 UsefulWithWitness(_
) => unreachable
!()
350 let Matrix(mut rows
) = seen
;
358 fn raw_pat
<'a
>(p
: &'a Pat
) -> &'a Pat
{
360 hir
::PatIdent(_
, _
, Some(ref s
)) => raw_pat(&**s
),
365 fn check_exhaustive(cx
: &MatchCheckCtxt
, sp
: Span
, matrix
: &Matrix
, source
: hir
::MatchSource
) {
366 match is_useful(cx
, matrix
, &[DUMMY_WILD_PAT
], ConstructWitness
) {
367 UsefulWithWitness(pats
) => {
368 let witness
= match &pats
[..] {
369 [ref witness
] => &**witness
,
370 [] => DUMMY_WILD_PAT
,
374 hir
::MatchSource
::ForLoopDesugar
=> {
375 // `witness` has the form `Some(<head>)`, peel off the `Some`
376 let witness
= match witness
.node
{
377 hir
::PatEnum(_
, Some(ref pats
)) => match &pats
[..] {
384 span_err
!(cx
.tcx
.sess
, sp
, E0297
,
385 "refutable pattern in `for` loop binding: \
387 pat_to_string(witness
));
390 span_err
!(cx
.tcx
.sess
, sp
, E0004
,
391 "non-exhaustive patterns: `{}` not covered",
392 pat_to_string(witness
)
398 // This is good, wildcard pattern isn't reachable
404 fn const_val_to_expr(value
: &ConstVal
) -> P
<hir
::Expr
> {
405 let node
= match value
{
406 &ConstVal
::Bool(b
) => ast
::LitBool(b
),
411 node
: hir
::ExprLit(P(Spanned { node: node, span: DUMMY_SP }
)),
417 pub struct StaticInliner
<'a
, 'tcx
: 'a
> {
418 pub tcx
: &'a ty
::ctxt
<'tcx
>,
420 pub renaming_map
: Option
<&'a
mut FnvHashMap
<(NodeId
, Span
), NodeId
>>,
423 impl<'a
, 'tcx
> StaticInliner
<'a
, 'tcx
> {
424 pub fn new
<'b
>(tcx
: &'b ty
::ctxt
<'tcx
>,
425 renaming_map
: Option
<&'b
mut FnvHashMap
<(NodeId
, Span
), NodeId
>>)
426 -> StaticInliner
<'b
, 'tcx
> {
430 renaming_map
: renaming_map
435 struct RenamingRecorder
<'map
> {
436 substituted_node_id
: NodeId
,
438 renaming_map
: &'map
mut FnvHashMap
<(NodeId
, Span
), NodeId
>
441 impl<'map
> ast_util
::IdVisitingOperation
for RenamingRecorder
<'map
> {
442 fn visit_id(&mut self, node_id
: NodeId
) {
443 let key
= (node_id
, self.origin_span
);
444 self.renaming_map
.insert(key
, self.substituted_node_id
);
448 impl<'a
, 'tcx
> Folder
for StaticInliner
<'a
, 'tcx
> {
449 fn fold_pat(&mut self, pat
: P
<Pat
>) -> P
<Pat
> {
450 return match pat
.node
{
451 hir
::PatIdent(..) | hir
::PatEnum(..) | hir
::PatQPath(..) => {
452 let def
= self.tcx
.def_map
.borrow().get(&pat
.id
).map(|d
| d
.full_def());
454 Some(DefAssociatedConst(did
)) |
455 Some(DefConst(did
)) => match lookup_const_by_id(self.tcx
, did
, Some(pat
.id
)) {
456 Some(const_expr
) => {
457 const_expr_to_pat(self.tcx
, const_expr
, pat
.span
).map(|new_pat
| {
459 if let Some(ref mut renaming_map
) = self.renaming_map
{
460 // Record any renamings we do here
461 record_renamings(const_expr
, &pat
, renaming_map
);
469 span_err
!(self.tcx
.sess
, pat
.span
, E0158
,
470 "statics cannot be referenced in patterns");
474 _
=> noop_fold_pat(pat
, self)
477 _
=> noop_fold_pat(pat
, self)
480 fn record_renamings(const_expr
: &hir
::Expr
,
481 substituted_pat
: &hir
::Pat
,
482 renaming_map
: &mut FnvHashMap
<(NodeId
, Span
), NodeId
>) {
483 let mut renaming_recorder
= RenamingRecorder
{
484 substituted_node_id
: substituted_pat
.id
,
485 origin_span
: substituted_pat
.span
,
486 renaming_map
: renaming_map
,
489 let mut id_visitor
= front_util
::IdVisitor
::new(&mut renaming_recorder
);
491 id_visitor
.visit_expr(const_expr
);
496 /// Constructs a partial witness for a pattern given a list of
497 /// patterns expanded by the specialization step.
499 /// When a pattern P is discovered to be useful, this function is used bottom-up
500 /// to reconstruct a complete witness, e.g. a pattern P' that covers a subset
501 /// of values, V, where each value in that set is not covered by any previously
502 /// used patterns and is covered by the pattern P'. Examples:
504 /// left_ty: tuple of 3 elements
505 /// pats: [10, 20, _] => (10, 20, _)
507 /// left_ty: struct X { a: (bool, &'static str), b: usize}
508 /// pats: [(false, "foo"), 42] => X { a: (false, "foo"), b: 42 }
509 fn construct_witness
<'a
,'tcx
>(cx
: &MatchCheckCtxt
<'a
,'tcx
>, ctor
: &Constructor
,
510 pats
: Vec
<&Pat
>, left_ty
: Ty
<'tcx
>) -> P
<Pat
> {
511 let pats_len
= pats
.len();
512 let mut pats
= pats
.into_iter().map(|p
| P((*p
).clone()));
513 let pat
= match left_ty
.sty
{
514 ty
::TyTuple(_
) => hir
::PatTup(pats
.collect()),
516 ty
::TyEnum(adt
, _
) | ty
::TyStruct(adt
, _
) => {
517 let v
= adt
.variant_of_ctor(ctor
);
518 if let VariantKind
::Struct
= v
.kind() {
519 let field_pats
: Vec
<_
> = v
.fields
.iter()
521 .filter(|&(_
, ref pat
)| pat
.node
!= hir
::PatWild
)
522 .map(|(field
, pat
)| Spanned
{
524 node
: hir
::FieldPat
{
530 let has_more_fields
= field_pats
.len() < pats_len
;
531 hir
::PatStruct(def_to_path(cx
.tcx
, v
.did
), field_pats
, has_more_fields
)
533 hir
::PatEnum(def_to_path(cx
.tcx
, v
.did
), Some(pats
.collect()))
537 ty
::TyRef(_
, ty
::TypeAndMut { ty, mutbl }
) => {
539 ty
::TyArray(_
, n
) => match ctor
{
541 assert_eq
!(pats_len
, n
);
542 hir
::PatVec(pats
.collect(), None
, vec
!())
546 ty
::TySlice(_
) => match ctor
{
548 assert_eq
!(pats_len
, n
);
549 hir
::PatVec(pats
.collect(), None
, vec
!())
553 ty
::TyStr
=> hir
::PatWild
,
556 assert_eq
!(pats_len
, 1);
557 hir
::PatRegion(pats
.nth(0).unwrap(), mutbl
)
562 ty
::TyArray(_
, len
) => {
563 assert_eq
!(pats_len
, len
);
564 hir
::PatVec(pats
.collect(), None
, vec
![])
569 ConstantValue(ref v
) => hir
::PatLit(const_val_to_expr(v
)),
582 impl<'tcx
, 'container
> ty
::AdtDefData
<'tcx
, 'container
> {
583 fn variant_of_ctor(&self,
585 -> &VariantDefData
<'tcx
, 'container
> {
587 &Variant(vid
) => self.variant_with_id(vid
),
588 _
=> self.struct_variant()
593 fn missing_constructor(cx
: &MatchCheckCtxt
, &Matrix(ref rows
): &Matrix
,
594 left_ty
: Ty
, max_slice_length
: usize) -> Option
<Constructor
> {
595 let used_constructors
: Vec
<Constructor
> = rows
.iter()
596 .flat_map(|row
| pat_constructors(cx
, row
[0], left_ty
, max_slice_length
))
598 all_constructors(cx
, left_ty
, max_slice_length
)
600 .find(|c
| !used_constructors
.contains(c
))
603 /// This determines the set of all possible constructors of a pattern matching
604 /// values of type `left_ty`. For vectors, this would normally be an infinite set
605 /// but is instead bounded by the maximum fixed length of slice patterns in
606 /// the column of patterns being analyzed.
607 fn all_constructors(_cx
: &MatchCheckCtxt
, left_ty
: Ty
,
608 max_slice_length
: usize) -> Vec
<Constructor
> {
611 [true, false].iter().map(|b
| ConstantValue(ConstVal
::Bool(*b
))).collect(),
613 ty
::TyRef(_
, ty
::TypeAndMut { ty, .. }
) => match ty
.sty
{
615 (0..max_slice_length
+1).map(|length
| Slice(length
)).collect(),
619 ty
::TyEnum(def
, _
) => def
.variants
.iter().map(|v
| Variant(v
.did
)).collect(),
624 // Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html
626 // Whether a vector `v` of patterns is 'useful' in relation to a set of such
627 // vectors `m` is defined as there being a set of inputs that will match `v`
628 // but not any of the sets in `m`.
630 // This is used both for reachability checking (if a pattern isn't useful in
631 // relation to preceding patterns, it is not reachable) and exhaustiveness
632 // checking (if a wildcard pattern is useful in relation to a matrix, the
633 // matrix isn't exhaustive).
635 // Note: is_useful doesn't work on empty types, as the paper notes.
636 // So it assumes that v is non-empty.
637 fn is_useful(cx
: &MatchCheckCtxt
,
640 witness
: WitnessPreference
)
642 let &Matrix(ref rows
) = matrix
;
643 debug
!("{:?}", matrix
);
645 return match witness
{
646 ConstructWitness
=> UsefulWithWitness(vec
!()),
647 LeaveOutWitness
=> Useful
650 if rows
[0].is_empty() {
653 assert
!(rows
.iter().all(|r
| r
.len() == v
.len()));
654 let real_pat
= match rows
.iter().find(|r
| (*r
)[0].id
!= DUMMY_NODE_ID
) {
655 Some(r
) => raw_pat(r
[0]),
656 None
if v
.is_empty() => return NotUseful
,
659 let left_ty
= if real_pat
.id
== DUMMY_NODE_ID
{
662 let left_ty
= cx
.tcx
.pat_ty(&*real_pat
);
664 match real_pat
.node
{
665 hir
::PatIdent(hir
::BindByRef(..), _
, _
) => {
666 left_ty
.builtin_deref(false, NoPreference
).unwrap().ty
672 let max_slice_length
= rows
.iter().filter_map(|row
| match row
[0].node
{
673 hir
::PatVec(ref before
, _
, ref after
) => Some(before
.len() + after
.len()),
675 }).max().map_or(0, |v
| v
+ 1);
677 let constructors
= pat_constructors(cx
, v
[0], left_ty
, max_slice_length
);
678 if constructors
.is_empty() {
679 match missing_constructor(cx
, matrix
, left_ty
, max_slice_length
) {
681 all_constructors(cx
, left_ty
, max_slice_length
).into_iter().map(|c
| {
682 match is_useful_specialized(cx
, matrix
, v
, c
.clone(), left_ty
, witness
) {
683 UsefulWithWitness(pats
) => UsefulWithWitness({
684 let arity
= constructor_arity(cx
, &c
, left_ty
);
686 let pat_slice
= &pats
[..];
687 let subpats
: Vec
<_
> = (0..arity
).map(|i
| {
688 pat_slice
.get(i
).map_or(DUMMY_WILD_PAT
, |p
| &**p
)
690 vec
![construct_witness(cx
, &c
, subpats
, left_ty
)]
692 result
.extend(pats
.into_iter().skip(arity
));
697 }).find(|result
| result
!= &NotUseful
).unwrap_or(NotUseful
)
700 Some(constructor
) => {
701 let matrix
= rows
.iter().filter_map(|r
| {
702 if pat_is_binding_or_wild(&cx
.tcx
.def_map
.borrow(), raw_pat(r
[0])) {
703 Some(r
[1..].to_vec())
708 match is_useful(cx
, &matrix
, &v
[1..], witness
) {
709 UsefulWithWitness(pats
) => {
710 let arity
= constructor_arity(cx
, &constructor
, left_ty
);
711 let wild_pats
= vec
![DUMMY_WILD_PAT
; arity
];
712 let enum_pat
= construct_witness(cx
, &constructor
, wild_pats
, left_ty
);
713 let mut new_pats
= vec
![enum_pat
];
714 new_pats
.extend(pats
);
715 UsefulWithWitness(new_pats
)
722 constructors
.into_iter().map(|c
|
723 is_useful_specialized(cx
, matrix
, v
, c
.clone(), left_ty
, witness
)
724 ).find(|result
| result
!= &NotUseful
).unwrap_or(NotUseful
)
728 fn is_useful_specialized(cx
: &MatchCheckCtxt
, &Matrix(ref m
): &Matrix
,
729 v
: &[&Pat
], ctor
: Constructor
, lty
: Ty
,
730 witness
: WitnessPreference
) -> Usefulness
{
731 let arity
= constructor_arity(cx
, &ctor
, lty
);
732 let matrix
= Matrix(m
.iter().filter_map(|r
| {
733 specialize(cx
, &r
[..], &ctor
, 0, arity
)
735 match specialize(cx
, v
, &ctor
, 0, arity
) {
736 Some(v
) => is_useful(cx
, &matrix
, &v
[..], witness
),
741 /// Determines the constructors that the given pattern can be specialized to.
743 /// In most cases, there's only one constructor that a specific pattern
744 /// represents, such as a specific enum variant or a specific literal value.
745 /// Slice patterns, however, can match slices of different lengths. For instance,
746 /// `[a, b, ..tail]` can match a slice of length 2, 3, 4 and so on.
748 /// On the other hand, a wild pattern and an identifier pattern cannot be
749 /// specialized in any way.
750 fn pat_constructors(cx
: &MatchCheckCtxt
, p
: &Pat
,
751 left_ty
: Ty
, max_slice_length
: usize) -> Vec
<Constructor
> {
752 let pat
= raw_pat(p
);
755 match cx
.tcx
.def_map
.borrow().get(&pat
.id
).map(|d
| d
.full_def()) {
756 Some(DefConst(..)) | Some(DefAssociatedConst(..)) =>
757 cx
.tcx
.sess
.span_bug(pat
.span
, "const pattern should've \
759 Some(DefStruct(_
)) => vec
!(Single
),
760 Some(DefVariant(_
, id
, _
)) => vec
!(Variant(id
)),
764 match cx
.tcx
.def_map
.borrow().get(&pat
.id
).map(|d
| d
.full_def()) {
765 Some(DefConst(..)) | Some(DefAssociatedConst(..)) =>
766 cx
.tcx
.sess
.span_bug(pat
.span
, "const pattern should've \
768 Some(DefVariant(_
, id
, _
)) => vec
!(Variant(id
)),
772 cx
.tcx
.sess
.span_bug(pat
.span
, "const pattern should've \
774 hir
::PatStruct(..) =>
775 match cx
.tcx
.def_map
.borrow().get(&pat
.id
).map(|d
| d
.full_def()) {
776 Some(DefConst(..)) | Some(DefAssociatedConst(..)) =>
777 cx
.tcx
.sess
.span_bug(pat
.span
, "const pattern should've \
779 Some(DefVariant(_
, id
, _
)) => vec
!(Variant(id
)),
782 hir
::PatLit(ref expr
) =>
783 vec
!(ConstantValue(eval_const_expr(cx
.tcx
, &**expr
))),
784 hir
::PatRange(ref lo
, ref hi
) =>
785 vec
!(ConstantRange(eval_const_expr(cx
.tcx
, &**lo
), eval_const_expr(cx
.tcx
, &**hi
))),
786 hir
::PatVec(ref before
, ref slice
, ref after
) =>
788 ty
::TyArray(_
, _
) => vec
!(Single
),
789 _
=> if slice
.is_some() {
790 (before
.len() + after
.len()..max_slice_length
+1)
791 .map(|length
| Slice(length
))
794 vec
!(Slice(before
.len() + after
.len()))
797 hir
::PatBox(_
) | hir
::PatTup(_
) | hir
::PatRegion(..) =>
804 /// This computes the arity of a constructor. The arity of a constructor
805 /// is how many subpattern patterns of that constructor should be expanded to.
807 /// For instance, a tuple pattern (_, 42, Some([])) has the arity of 3.
808 /// A struct pattern's arity is the number of fields it contains, etc.
809 pub fn constructor_arity(_cx
: &MatchCheckCtxt
, ctor
: &Constructor
, ty
: Ty
) -> usize {
811 ty
::TyTuple(ref fs
) => fs
.len(),
813 ty
::TyRef(_
, ty
::TypeAndMut { ty, .. }
) => match ty
.sty
{
814 ty
::TySlice(_
) => match *ctor
{
815 Slice(length
) => length
,
816 ConstantValue(_
) => 0,
822 ty
::TyEnum(adt
, _
) | ty
::TyStruct(adt
, _
) => {
823 adt
.variant_of_ctor(ctor
).fields
.len()
825 ty
::TyArray(_
, n
) => n
,
830 fn range_covered_by_constructor(ctor
: &Constructor
,
831 from
: &ConstVal
, to
: &ConstVal
) -> Option
<bool
> {
832 let (c_from
, c_to
) = match *ctor
{
833 ConstantValue(ref value
) => (value
, value
),
834 ConstantRange(ref from
, ref to
) => (from
, to
),
835 Single
=> return Some(true),
838 let cmp_from
= compare_const_vals(c_from
, from
);
839 let cmp_to
= compare_const_vals(c_to
, to
);
840 match (cmp_from
, cmp_to
) {
841 (Some(cmp_from
), Some(cmp_to
)) => {
842 Some(cmp_from
!= Ordering
::Less
&& cmp_to
!= Ordering
::Greater
)
848 /// This is the main specialization step. It expands the first pattern in the given row
849 /// into `arity` patterns based on the constructor. For most patterns, the step is trivial,
850 /// for instance tuple patterns are flattened and box patterns expand into their inner pattern.
852 /// OTOH, slice patterns with a subslice pattern (..tail) can be expanded into multiple
853 /// different patterns.
854 /// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing
855 /// fields filled with wild patterns.
856 pub fn specialize
<'a
>(cx
: &MatchCheckCtxt
, r
: &[&'a Pat
],
857 constructor
: &Constructor
, col
: usize, arity
: usize) -> Option
<Vec
<&'a Pat
>> {
859 id
: pat_id
, ref node
, span
: pat_span
861 let head
: Option
<Vec
<&Pat
>> = match *node
{
863 Some(vec
![DUMMY_WILD_PAT
; arity
]),
865 hir
::PatIdent(_
, _
, _
) => {
866 let opt_def
= cx
.tcx
.def_map
.borrow().get(&pat_id
).map(|d
| d
.full_def());
868 Some(DefConst(..)) | Some(DefAssociatedConst(..)) =>
869 cx
.tcx
.sess
.span_bug(pat_span
, "const pattern should've \
871 Some(DefVariant(_
, id
, _
)) => if *constructor
== Variant(id
) {
876 _
=> Some(vec
![DUMMY_WILD_PAT
; arity
])
880 hir
::PatEnum(_
, ref args
) => {
881 let def
= cx
.tcx
.def_map
.borrow().get(&pat_id
).unwrap().full_def();
883 DefConst(..) | DefAssociatedConst(..) =>
884 cx
.tcx
.sess
.span_bug(pat_span
, "const pattern should've \
886 DefVariant(_
, id
, _
) if *constructor
!= Variant(id
) => None
,
887 DefVariant(..) | DefStruct(..) => {
889 &Some(ref args
) => args
.iter().map(|p
| &**p
).collect(),
890 &None
=> vec
![DUMMY_WILD_PAT
; arity
],
897 hir
::PatQPath(_
, _
) => {
898 cx
.tcx
.sess
.span_bug(pat_span
, "const pattern should've \
902 hir
::PatStruct(_
, ref pattern_fields
, _
) => {
903 let def
= cx
.tcx
.def_map
.borrow().get(&pat_id
).unwrap().full_def();
904 let adt
= cx
.tcx
.node_id_to_type(pat_id
).ty_adt_def().unwrap();
905 let variant
= adt
.variant_of_ctor(constructor
);
906 let def_variant
= adt
.variant_of_def(def
);
907 if variant
.did
== def_variant
.did
{
908 Some(variant
.fields
.iter().map(|sf
| {
909 match pattern_fields
.iter().find(|f
| f
.node
.name
== sf
.name
) {
910 Some(ref f
) => &*f
.node
.pat
,
919 hir
::PatTup(ref args
) =>
920 Some(args
.iter().map(|p
| &**p
).collect()),
922 hir
::PatBox(ref inner
) | hir
::PatRegion(ref inner
, _
) =>
923 Some(vec
![&**inner
]),
925 hir
::PatLit(ref expr
) => {
926 let expr_value
= eval_const_expr(cx
.tcx
, &**expr
);
927 match range_covered_by_constructor(constructor
, &expr_value
, &expr_value
) {
928 Some(true) => Some(vec
![]),
931 span_err
!(cx
.tcx
.sess
, pat_span
, E0298
, "mismatched types between arms");
937 hir
::PatRange(ref from
, ref to
) => {
938 let from_value
= eval_const_expr(cx
.tcx
, &**from
);
939 let to_value
= eval_const_expr(cx
.tcx
, &**to
);
940 match range_covered_by_constructor(constructor
, &from_value
, &to_value
) {
941 Some(true) => Some(vec
![]),
944 span_err
!(cx
.tcx
.sess
, pat_span
, E0299
, "mismatched types between arms");
950 hir
::PatVec(ref before
, ref slice
, ref after
) => {
952 // Fixed-length vectors.
954 let mut pats
: Vec
<&Pat
> = before
.iter().map(|p
| &**p
).collect();
955 pats
.extend(repeat(DUMMY_WILD_PAT
).take(arity
- before
.len() - after
.len()));
956 pats
.extend(after
.iter().map(|p
| &**p
));
959 Slice(length
) if before
.len() + after
.len() <= length
&& slice
.is_some() => {
960 let mut pats
: Vec
<&Pat
> = before
.iter().map(|p
| &**p
).collect();
961 pats
.extend(repeat(DUMMY_WILD_PAT
).take(arity
- before
.len() - after
.len()));
962 pats
.extend(after
.iter().map(|p
| &**p
));
965 Slice(length
) if before
.len() + after
.len() == length
=> {
966 let mut pats
: Vec
<&Pat
> = before
.iter().map(|p
| &**p
).collect();
967 pats
.extend(after
.iter().map(|p
| &**p
));
970 SliceWithSubslice(prefix
, suffix
)
971 if before
.len() == prefix
972 && after
.len() == suffix
973 && slice
.is_some() => {
974 let mut pats
: Vec
<&Pat
> = before
.iter().map(|p
| &**p
).collect();
975 pats
.extend(after
.iter().map(|p
| &**p
));
982 head
.map(|mut head
| {
983 head
.extend_from_slice(&r
[..col
]);
984 head
.extend_from_slice(&r
[col
+ 1..]);
989 fn check_local(cx
: &mut MatchCheckCtxt
, loc
: &hir
::Local
) {
990 intravisit
::walk_local(cx
, loc
);
992 let pat
= StaticInliner
::new(cx
.tcx
, None
).fold_pat(loc
.pat
.clone());
993 check_irrefutable(cx
, &pat
, false);
995 // Check legality of move bindings and `@` patterns.
996 check_legality_of_move_bindings(cx
, false, slice
::ref_slice(&loc
.pat
));
997 check_legality_of_bindings_in_at_patterns(cx
, &*loc
.pat
);
1000 fn check_fn(cx
: &mut MatchCheckCtxt
,
1007 FnKind
::Closure
=> {}
1008 _
=> cx
.param_env
= ParameterEnvironment
::for_item(cx
.tcx
, fn_id
),
1011 intravisit
::walk_fn(cx
, kind
, decl
, body
, sp
);
1013 for input
in &decl
.inputs
{
1014 check_irrefutable(cx
, &input
.pat
, true);
1015 check_legality_of_move_bindings(cx
, false, slice
::ref_slice(&input
.pat
));
1016 check_legality_of_bindings_in_at_patterns(cx
, &*input
.pat
);
1020 fn check_irrefutable(cx
: &MatchCheckCtxt
, pat
: &Pat
, is_fn_arg
: bool
) {
1021 let origin
= if is_fn_arg
{
1027 is_refutable(cx
, pat
, |uncovered_pat
| {
1028 span_err
!(cx
.tcx
.sess
, pat
.span
, E0005
,
1029 "refutable pattern in {}: `{}` not covered",
1031 pat_to_string(uncovered_pat
),
1036 fn is_refutable
<A
, F
>(cx
: &MatchCheckCtxt
, pat
: &Pat
, refutable
: F
) -> Option
<A
> where
1037 F
: FnOnce(&Pat
) -> A
,
1039 let pats
= Matrix(vec
!(vec
!(pat
)));
1040 match is_useful(cx
, &pats
, &[DUMMY_WILD_PAT
], ConstructWitness
) {
1041 UsefulWithWitness(pats
) => {
1042 assert_eq
!(pats
.len(), 1);
1043 Some(refutable(&*pats
[0]))
1046 Useful
=> unreachable
!()
1050 // Legality of move bindings checking
1051 fn check_legality_of_move_bindings(cx
: &MatchCheckCtxt
,
1055 let def_map
= &tcx
.def_map
;
1056 let mut by_ref_span
= None
;
1058 pat_bindings(def_map
, &**pat
, |bm
, _
, span
, _path
| {
1060 hir
::BindByRef(_
) => {
1061 by_ref_span
= Some(span
);
1063 hir
::BindByValue(_
) => {
1069 let check_move
= |p
: &Pat
, sub
: Option
<&Pat
>| {
1070 // check legality of moving out of the enum
1072 // x @ Foo(..) is legal, but x @ Foo(y) isn't.
1073 if sub
.map_or(false, |p
| pat_contains_bindings(&def_map
.borrow(), &*p
)) {
1074 span_err
!(cx
.tcx
.sess
, p
.span
, E0007
, "cannot bind by-move with sub-bindings");
1075 } else if has_guard
{
1076 span_err
!(cx
.tcx
.sess
, p
.span
, E0008
, "cannot bind by-move into a pattern guard");
1077 } else if by_ref_span
.is_some() {
1078 span_err
!(cx
.tcx
.sess
, p
.span
, E0009
,
1079 "cannot bind by-move and by-ref in the same pattern");
1080 span_note
!(cx
.tcx
.sess
, by_ref_span
.unwrap(), "by-ref binding occurs here");
1085 front_util
::walk_pat(&**pat
, |p
| {
1086 if pat_is_binding(&def_map
.borrow(), &*p
) {
1088 hir
::PatIdent(hir
::BindByValue(_
), _
, ref sub
) => {
1089 let pat_ty
= tcx
.node_id_to_type(p
.id
);
1090 //FIXME: (@jroesch) this code should be floated up as well
1091 let infcx
= infer
::new_infer_ctxt(cx
.tcx
,
1093 Some(cx
.param_env
.clone()),
1095 if infcx
.type_moves_by_default(pat_ty
, pat
.span
) {
1096 check_move(p
, sub
.as_ref().map(|p
| &**p
));
1099 hir
::PatIdent(hir
::BindByRef(_
), _
, _
) => {
1102 cx
.tcx
.sess
.span_bug(
1104 &format
!("binding pattern {} is not an \
1116 /// Ensures that a pattern guard doesn't borrow by mutable reference or
1118 fn check_for_mutation_in_guard
<'a
, 'tcx
>(cx
: &'a MatchCheckCtxt
<'a
, 'tcx
>,
1119 guard
: &hir
::Expr
) {
1120 let mut checker
= MutationChecker
{
1124 let infcx
= infer
::new_infer_ctxt(cx
.tcx
,
1126 Some(checker
.cx
.param_env
.clone()),
1129 let mut visitor
= ExprUseVisitor
::new(&mut checker
, &infcx
);
1130 visitor
.walk_expr(guard
);
1133 struct MutationChecker
<'a
, 'tcx
: 'a
> {
1134 cx
: &'a MatchCheckCtxt
<'a
, 'tcx
>,
1137 impl<'a
, 'tcx
> Delegate
<'tcx
> for MutationChecker
<'a
, 'tcx
> {
1138 fn matched_pat(&mut self, _
: &Pat
, _
: cmt
, _
: euv
::MatchMode
) {}
1139 fn consume(&mut self, _
: NodeId
, _
: Span
, _
: cmt
, _
: ConsumeMode
) {}
1140 fn consume_pat(&mut self, _
: &Pat
, _
: cmt
, _
: ConsumeMode
) {}
1141 fn borrow(&mut self,
1150 span_err
!(self.cx
.tcx
.sess
, span
, E0301
,
1151 "cannot mutably borrow in a pattern guard")
1153 ImmBorrow
| UniqueImmBorrow
=> {}
1156 fn decl_without_init(&mut self, _
: NodeId
, _
: Span
) {}
1157 fn mutate(&mut self, _
: NodeId
, span
: Span
, _
: cmt
, mode
: MutateMode
) {
1159 JustWrite
| WriteAndRead
=> {
1160 span_err
!(self.cx
.tcx
.sess
, span
, E0302
, "cannot assign in a pattern guard")
1167 /// Forbids bindings in `@` patterns. This is necessary for memory safety,
1168 /// because of the way rvalues are handled in the borrow check. (See issue
1170 fn check_legality_of_bindings_in_at_patterns(cx
: &MatchCheckCtxt
, pat
: &Pat
) {
1171 AtBindingPatternVisitor { cx: cx, bindings_allowed: true }
.visit_pat(pat
);
1174 struct AtBindingPatternVisitor
<'a
, 'b
:'a
, 'tcx
:'b
> {
1175 cx
: &'a MatchCheckCtxt
<'b
, 'tcx
>,
1176 bindings_allowed
: bool
1179 impl<'a
, 'b
, 'tcx
, 'v
> Visitor
<'v
> for AtBindingPatternVisitor
<'a
, 'b
, 'tcx
> {
1180 fn visit_pat(&mut self, pat
: &Pat
) {
1181 if !self.bindings_allowed
&& pat_is_binding(&self.cx
.tcx
.def_map
.borrow(), pat
) {
1182 span_err
!(self.cx
.tcx
.sess
, pat
.span
, E0303
,
1183 "pattern bindings are not allowed \
1188 hir
::PatIdent(_
, _
, Some(_
)) => {
1189 let bindings_were_allowed
= self.bindings_allowed
;
1190 self.bindings_allowed
= false;
1191 intravisit
::walk_pat(self, pat
);
1192 self.bindings_allowed
= bindings_were_allowed
;
1194 _
=> intravisit
::walk_pat(self, pat
),