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 use self::Constructor
::*;
12 use self::Usefulness
::*;
13 use self::WitnessPreference
::*;
15 use rustc
::middle
::const_val
::ConstVal
;
16 use eval
::{compare_const_vals}
;
18 use rustc_const_math
::ConstInt
;
20 use rustc_data_structures
::fx
::FxHashMap
;
21 use rustc_data_structures
::indexed_vec
::Idx
;
23 use pattern
::{FieldPattern, Pattern, PatternKind}
;
24 use pattern
::{PatternFoldable, PatternFolder}
;
26 use rustc
::hir
::def_id
::DefId
;
27 use rustc
::hir
::RangeEnd
;
28 use rustc
::ty
::{self, AdtKind, Ty, TyCtxt, TypeFoldable}
;
30 use rustc
::mir
::Field
;
31 use rustc
::util
::common
::ErrorReported
;
33 use syntax_pos
::{Span, DUMMY_SP}
;
35 use arena
::TypedArena
;
37 use std
::cmp
::{self, Ordering}
;
39 use std
::iter
::{FromIterator, IntoIterator, repeat}
;
41 pub fn expand_pattern
<'a
, 'tcx
>(cx
: &MatchCheckCtxt
<'a
, 'tcx
>, pat
: Pattern
<'tcx
>)
44 cx
.pattern_arena
.alloc(LiteralExpander
.fold_pattern(&pat
))
47 struct LiteralExpander
;
48 impl<'tcx
> PatternFolder
<'tcx
> for LiteralExpander
{
49 fn fold_pattern(&mut self, pat
: &Pattern
<'tcx
>) -> Pattern
<'tcx
> {
50 match (&pat
.ty
.sty
, &*pat
.kind
) {
51 (&ty
::TyRef(_
, mt
), &PatternKind
::Constant { ref value }
) => {
55 kind
: box PatternKind
::Deref
{
59 kind
: box PatternKind
::Constant { value: value.clone() }
,
64 (_
, &PatternKind
::Binding { subpattern: Some(ref s), .. }
) => {
67 _
=> pat
.super_fold_with(self)
72 impl<'tcx
> Pattern
<'tcx
> {
73 fn is_wildcard(&self) -> bool
{
75 PatternKind
::Binding { subpattern: None, .. }
| PatternKind
::Wild
=>
82 pub struct Matrix
<'a
, 'tcx
: 'a
>(Vec
<Vec
<&'a Pattern
<'tcx
>>>);
84 impl<'a
, 'tcx
> Matrix
<'a
, 'tcx
> {
85 pub fn empty() -> Self {
89 pub fn push(&mut self, row
: Vec
<&'a Pattern
<'tcx
>>) {
94 /// Pretty-printer for matrices of patterns, example:
95 /// ++++++++++++++++++++++++++
97 /// ++++++++++++++++++++++++++
98 /// + true + [First] +
99 /// ++++++++++++++++++++++++++
100 /// + true + [Second(true)] +
101 /// ++++++++++++++++++++++++++
103 /// ++++++++++++++++++++++++++
104 /// + _ + [_, _, ..tail] +
105 /// ++++++++++++++++++++++++++
106 impl<'a
, 'tcx
> fmt
::Debug
for Matrix
<'a
, 'tcx
> {
107 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
110 let &Matrix(ref m
) = self;
111 let pretty_printed_matrix
: Vec
<Vec
<String
>> = m
.iter().map(|row
| {
112 row
.iter().map(|pat
| format
!("{:?}", pat
)).collect()
115 let column_count
= m
.iter().map(|row
| row
.len()).max().unwrap_or(0);
116 assert
!(m
.iter().all(|row
| row
.len() == column_count
));
117 let column_widths
: Vec
<usize> = (0..column_count
).map(|col
| {
118 pretty_printed_matrix
.iter().map(|row
| row
[col
].len()).max().unwrap_or(0)
121 let total_width
= column_widths
.iter().cloned().sum
::<usize>() + column_count
* 3 + 1;
122 let br
= repeat('
+'
).take(total_width
).collect
::<String
>();
123 write
!(f
, "{}\n", br
)?
;
124 for row
in pretty_printed_matrix
{
126 for (column
, pat_str
) in row
.into_iter().enumerate() {
128 write
!(f
, "{:1$}", pat_str
, column_widths
[column
])?
;
132 write
!(f
, "{}\n", br
)?
;
138 impl<'a
, 'tcx
> FromIterator
<Vec
<&'a Pattern
<'tcx
>>> for Matrix
<'a
, 'tcx
> {
139 fn from_iter
<T
: IntoIterator
<Item
=Vec
<&'a Pattern
<'tcx
>>>>(iter
: T
) -> Self
141 Matrix(iter
.into_iter().collect())
145 //NOTE: appears to be the only place other then InferCtxt to contain a ParamEnv
146 pub struct MatchCheckCtxt
<'a
, 'tcx
: 'a
> {
147 pub tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
148 /// The module in which the match occurs. This is necessary for
149 /// checking inhabited-ness of types because whether a type is (visibly)
150 /// inhabited can depend on whether it was defined in the current module or
151 /// not. eg. `struct Foo { _private: ! }` cannot be seen to be empty
152 /// outside it's module and should not be matchable with an empty match
155 pub pattern_arena
: &'a TypedArena
<Pattern
<'tcx
>>,
156 pub byte_array_map
: FxHashMap
<*const Pattern
<'tcx
>, Vec
<&'a Pattern
<'tcx
>>>,
159 impl<'a
, 'tcx
> MatchCheckCtxt
<'a
, 'tcx
> {
160 pub fn create_and_enter
<F
, R
>(
161 tcx
: TyCtxt
<'a
, 'tcx
, 'tcx
>,
164 where F
: for<'b
> FnOnce(MatchCheckCtxt
<'b
, 'tcx
>) -> R
166 let pattern_arena
= TypedArena
::new();
171 pattern_arena
: &pattern_arena
,
172 byte_array_map
: FxHashMap(),
176 // convert a byte-string pattern to a list of u8 patterns.
177 fn lower_byte_str_pattern
<'p
>(&mut self, pat
: &'p Pattern
<'tcx
>) -> Vec
<&'p Pattern
<'tcx
>>
180 let pattern_arena
= &*self.pattern_arena
;
182 self.byte_array_map
.entry(pat
).or_insert_with(|| {
184 box PatternKind
::Constant
{
185 value
: ConstVal
::ByteStr(ref data
)
187 data
.iter().map(|c
| &*pattern_arena
.alloc(Pattern
{
190 kind
: box PatternKind
::Constant
{
191 value
: ConstVal
::Integral(ConstInt
::U8(*c
))
195 _
=> span_bug
!(pat
.span
, "unexpected byte array pattern {:?}", pat
)
200 fn is_uninhabited(&self, ty
: Ty
<'tcx
>) -> bool
{
201 if self.tcx
.sess
.features
.borrow().never_type
{
202 ty
.is_uninhabited_from(self.module
, self.tcx
)
208 fn is_variant_uninhabited(&self,
209 variant
: &'tcx ty
::VariantDef
,
210 substs
: &'tcx ty
::subst
::Substs
<'tcx
>) -> bool
212 if self.tcx
.sess
.features
.borrow().never_type
{
213 let forest
= variant
.uninhabited_from(
214 &mut FxHashMap
::default(), self.tcx
, substs
, AdtKind
::Enum
216 forest
.contains(self.tcx
, self.module
)
223 #[derive(Clone, Debug, PartialEq)]
224 pub enum Constructor
<'tcx
> {
225 /// The constructor of all patterns that don't vary by constructor,
226 /// e.g. struct patterns and fixed-length arrays.
231 ConstantValue(ConstVal
<'tcx
>),
232 /// Ranges of literal values (`2...5` and `2..5`).
233 ConstantRange(ConstVal
<'tcx
>, ConstVal
<'tcx
>, RangeEnd
),
234 /// Array patterns of length n.
238 impl<'tcx
> Constructor
<'tcx
> {
239 fn variant_index_for_adt(&self, adt
: &'tcx ty
::AdtDef
) -> usize {
241 &Variant(vid
) => adt
.variant_index_with_id(vid
),
243 assert_eq
!(adt
.variants
.len(), 1);
246 _
=> bug
!("bad constructor {:?} for adt {:?}", self, adt
)
252 pub enum Usefulness
<'tcx
> {
254 UsefulWithWitness(Vec
<Witness
<'tcx
>>),
258 impl<'tcx
> Usefulness
<'tcx
> {
259 fn is_useful(&self) -> bool
{
267 #[derive(Copy, Clone)]
268 pub enum WitnessPreference
{
273 #[derive(Copy, Clone, Debug)]
274 struct PatternContext
<'tcx
> {
276 max_slice_length
: usize,
279 /// A stack of patterns in reverse order of construction
281 pub struct Witness
<'tcx
>(Vec
<Pattern
<'tcx
>>);
283 impl<'tcx
> Witness
<'tcx
> {
284 pub fn single_pattern(&self) -> &Pattern
<'tcx
> {
285 assert_eq
!(self.0.len(), 1);
289 fn push_wild_constructor
<'a
>(
291 cx
: &MatchCheckCtxt
<'a
, 'tcx
>,
292 ctor
: &Constructor
<'tcx
>,
296 let sub_pattern_tys
= constructor_sub_pattern_tys(cx
, ctor
, ty
);
297 self.0.extend(sub_pattern_tys
.into_iter().map(|ty
| {
301 kind
: box PatternKind
::Wild
,
304 self.apply_constructor(cx
, ctor
, ty
)
308 /// Constructs a partial witness for a pattern given a list of
309 /// patterns expanded by the specialization step.
311 /// When a pattern P is discovered to be useful, this function is used bottom-up
312 /// to reconstruct a complete witness, e.g. a pattern P' that covers a subset
313 /// of values, V, where each value in that set is not covered by any previously
314 /// used patterns and is covered by the pattern P'. Examples:
316 /// left_ty: tuple of 3 elements
317 /// pats: [10, 20, _] => (10, 20, _)
319 /// left_ty: struct X { a: (bool, &'static str), b: usize}
320 /// pats: [(false, "foo"), 42] => X { a: (false, "foo"), b: 42 }
321 fn apply_constructor
<'a
>(
323 cx
: &MatchCheckCtxt
<'a
,'tcx
>,
324 ctor
: &Constructor
<'tcx
>,
328 let arity
= constructor_arity(cx
, ctor
, ty
);
330 let len
= self.0.len();
331 let mut pats
= self.0.drain(len
-arity
..).rev();
336 let pats
= pats
.enumerate().map(|(i
, p
)| {
338 field
: Field
::new(i
),
343 if let ty
::TyAdt(adt
, substs
) = ty
.sty
{
344 if adt
.variants
.len() > 1 {
345 PatternKind
::Variant
{
348 variant_index
: ctor
.variant_index_for_adt(adt
),
352 PatternKind
::Leaf { subpatterns: pats }
355 PatternKind
::Leaf { subpatterns: pats }
360 PatternKind
::Deref { subpattern: pats.nth(0).unwrap() }
363 ty
::TySlice(_
) | ty
::TyArray(..) => {
365 prefix
: pats
.collect(),
373 ConstantValue(ref v
) => PatternKind
::Constant { value: v.clone() }
,
374 _
=> PatternKind
::Wild
,
380 self.0.push(Pattern
{
390 /// This determines the set of all possible constructors of a pattern matching
391 /// values of type `left_ty`. For vectors, this would normally be an infinite set
392 /// but is instead bounded by the maximum fixed length of slice patterns in
393 /// the column of patterns being analyzed.
395 /// This intentionally does not list ConstantValue specializations for
396 /// non-booleans, because we currently assume that there is always a
397 /// "non-standard constant" that matches. See issue #12483.
399 /// We make sure to omit constructors that are statically impossible. eg for
400 /// Option<!> we do not include Some(_) in the returned list of constructors.
401 fn all_constructors
<'a
, 'tcx
: 'a
>(cx
: &mut MatchCheckCtxt
<'a
, 'tcx
>,
402 pcx
: PatternContext
<'tcx
>)
403 -> Vec
<Constructor
<'tcx
>>
405 debug
!("all_constructors({:?})", pcx
.ty
);
408 [true, false].iter().map(|b
| ConstantValue(ConstVal
::Bool(*b
))).collect(),
409 ty
::TySlice(ref sub_ty
) => {
410 if cx
.is_uninhabited(sub_ty
) {
413 (0..pcx
.max_slice_length
+1).map(|length
| Slice(length
)).collect()
416 ty
::TyArray(ref sub_ty
, length
) => {
417 if length
> 0 && cx
.is_uninhabited(sub_ty
) {
423 ty
::TyAdt(def
, substs
) if def
.is_enum() && def
.variants
.len() != 1 => {
425 .filter(|v
| !cx
.is_variant_uninhabited(v
, substs
))
426 .map(|v
| Variant(v
.did
))
430 if cx
.is_uninhabited(pcx
.ty
) {
439 fn max_slice_length
<'p
, 'a
: 'p
, 'tcx
: 'a
, I
>(
440 _cx
: &mut MatchCheckCtxt
<'a
, 'tcx
>,
441 patterns
: I
) -> usize
442 where I
: Iterator
<Item
=&'p Pattern
<'tcx
>>
444 // The exhaustiveness-checking paper does not include any details on
445 // checking variable-length slice patterns. However, they are matched
446 // by an infinite collection of fixed-length array patterns.
448 // Checking the infinite set directly would take an infinite amount
449 // of time. However, it turns out that for each finite set of
450 // patterns `P`, all sufficiently large array lengths are equivalent:
452 // Each slice `s` with a "sufficiently-large" length `l ≥ L` that applies
453 // to exactly the subset `Pₜ` of `P` can be transformed to a slice
454 // `sₘ` for each sufficiently-large length `m` that applies to exactly
455 // the same subset of `P`.
457 // Because of that, each witness for reachability-checking from one
458 // of the sufficiently-large lengths can be transformed to an
459 // equally-valid witness from any other length, so we only have
460 // to check slice lengths from the "minimal sufficiently-large length"
463 // Note that the fact that there is a *single* `sₘ` for each `m`
464 // not depending on the specific pattern in `P` is important: if
465 // you look at the pair of patterns
468 // Then any slice of length ≥1 that matches one of these two
469 // patterns can be be trivially turned to a slice of any
470 // other length ≥1 that matches them and vice-versa - for
471 // but the slice from length 2 `[false, true]` that matches neither
472 // of these patterns can't be turned to a slice from length 1 that
473 // matches neither of these patterns, so we have to consider
474 // slices from length 2 there.
476 // Now, to see that that length exists and find it, observe that slice
477 // patterns are either "fixed-length" patterns (`[_, _, _]`) or
478 // "variable-length" patterns (`[_, .., _]`).
480 // For fixed-length patterns, all slices with lengths *longer* than
481 // the pattern's length have the same outcome (of not matching), so
482 // as long as `L` is greater than the pattern's length we can pick
483 // any `sₘ` from that length and get the same result.
485 // For variable-length patterns, the situation is more complicated,
486 // because as seen above the precise value of `sₘ` matters.
488 // However, for each variable-length pattern `p` with a prefix of length
489 // `plâ‚š` and suffix of length `slâ‚š`, only the first `plâ‚š` and the last
490 // `slâ‚š` elements are examined.
492 // Therefore, as long as `L` is positive (to avoid concerns about empty
493 // types), all elements after the maximum prefix length and before
494 // the maximum suffix length are not examined by any variable-length
495 // pattern, and therefore can be added/removed without affecting
496 // them - creating equivalent patterns from any sufficiently-large
499 // Of course, if fixed-length patterns exist, we must be sure
500 // that our length is large enough to miss them all, so
501 // we can pick `L = max(FIXED_LEN+1 ∪ {max(PREFIX_LEN) + max(SUFFIX_LEN)})`
503 // for example, with the above pair of patterns, all elements
504 // but the first and last can be added/removed, so any
505 // witness of length ≥2 (say, `[false, false, true]`) can be
506 // turned to a witness from any other length ≥2.
508 let mut max_prefix_len
= 0;
509 let mut max_suffix_len
= 0;
510 let mut max_fixed_len
= 0;
512 for row
in patterns
{
514 PatternKind
::Constant { value: ConstVal::ByteStr(ref data) }
=> {
515 max_fixed_len
= cmp
::max(max_fixed_len
, data
.len());
517 PatternKind
::Slice { ref prefix, slice: None, ref suffix }
=> {
518 let fixed_len
= prefix
.len() + suffix
.len();
519 max_fixed_len
= cmp
::max(max_fixed_len
, fixed_len
);
521 PatternKind
::Slice { ref prefix, slice: Some(_), ref suffix }
=> {
522 max_prefix_len
= cmp
::max(max_prefix_len
, prefix
.len());
523 max_suffix_len
= cmp
::max(max_suffix_len
, suffix
.len());
529 cmp
::max(max_fixed_len
+ 1, max_prefix_len
+ max_suffix_len
)
532 /// Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html
533 /// The algorithm from the paper has been modified to correctly handle empty
534 /// types. The changes are:
535 /// (0) We don't exit early if the pattern matrix has zero rows. We just
536 /// continue to recurse over columns.
537 /// (1) all_constructors will only return constructors that are statically
538 /// possible. eg. it will only return Ok for Result<T, !>
540 /// Whether a vector `v` of patterns is 'useful' in relation to a set of such
541 /// vectors `m` is defined as there being a set of inputs that will match `v`
542 /// but not any of the sets in `m`.
544 /// This is used both for reachability checking (if a pattern isn't useful in
545 /// relation to preceding patterns, it is not reachable) and exhaustiveness
546 /// checking (if a wildcard pattern is useful in relation to a matrix, the
547 /// matrix isn't exhaustive).
548 pub fn is_useful
<'p
, 'a
: 'p
, 'tcx
: 'a
>(cx
: &mut MatchCheckCtxt
<'a
, 'tcx
>,
549 matrix
: &Matrix
<'p
, 'tcx
>,
550 v
: &[&'p Pattern
<'tcx
>],
551 witness
: WitnessPreference
)
552 -> Usefulness
<'tcx
> {
553 let &Matrix(ref rows
) = matrix
;
554 debug
!("is_useful({:?}, {:?})", matrix
, v
);
556 // The base case. We are pattern-matching on () and the return value is
557 // based on whether our matrix has a row or not.
558 // NOTE: This could potentially be optimized by checking rows.is_empty()
559 // first and then, if v is non-empty, the return value is based on whether
560 // the type of the tuple we're checking is inhabited or not.
562 return if rows
.is_empty() {
564 ConstructWitness
=> UsefulWithWitness(vec
![Witness(vec
![])]),
565 LeaveOutWitness
=> Useful
,
572 assert
!(rows
.iter().all(|r
| r
.len() == v
.len()));
574 let pcx
= PatternContext
{
575 ty
: rows
.iter().map(|r
| r
[0].ty
).find(|ty
| !ty
.references_error())
577 max_slice_length
: max_slice_length(cx
, rows
.iter().map(|r
| r
[0]).chain(Some(v
[0])))
580 debug
!("is_useful_expand_first_col: pcx={:?}, expanding {:?}", pcx
, v
[0]);
582 if let Some(constructors
) = pat_constructors(cx
, v
[0], pcx
) {
583 debug
!("is_useful - expanding constructors: {:?}", constructors
);
584 constructors
.into_iter().map(|c
|
585 is_useful_specialized(cx
, matrix
, v
, c
.clone(), pcx
.ty
, witness
)
586 ).find(|result
| result
.is_useful()).unwrap_or(NotUseful
)
588 debug
!("is_useful - expanding wildcard");
590 let used_ctors
: Vec
<Constructor
> = rows
.iter().flat_map(|row
| {
591 pat_constructors(cx
, row
[0], pcx
).unwrap_or(vec
![])
593 debug
!("used_ctors = {:?}", used_ctors
);
594 let all_ctors
= all_constructors(cx
, pcx
);
595 debug
!("all_ctors = {:?}", all_ctors
);
596 let missing_ctors
: Vec
<Constructor
> = all_ctors
.iter().filter(|c
| {
597 !used_ctors
.contains(*c
)
598 }).cloned().collect();
600 // `missing_ctors` is the set of constructors from the same type as the
601 // first column of `matrix` that are matched only by wildcard patterns
602 // from the first column.
604 // Therefore, if there is some pattern that is unmatched by `matrix`,
605 // it will still be unmatched if the first constructor is replaced by
606 // any of the constructors in `missing_ctors`
608 // However, if our scrutinee is *privately* an empty enum, we
609 // must treat it as though it had an "unknown" constructor (in
610 // that case, all other patterns obviously can't be variants)
611 // to avoid exposing its emptyness. See the `match_privately_empty`
614 // FIXME: currently the only way I know of something can
615 // be a privately-empty enum is when the never_type
616 // feature flag is not present, so this is only
617 // needed for that case.
619 let is_privately_empty
=
620 all_ctors
.is_empty() && !cx
.is_uninhabited(pcx
.ty
);
621 debug
!("missing_ctors={:?} is_privately_empty={:?}", missing_ctors
,
623 if missing_ctors
.is_empty() && !is_privately_empty
{
624 all_ctors
.into_iter().map(|c
| {
625 is_useful_specialized(cx
, matrix
, v
, c
.clone(), pcx
.ty
, witness
)
626 }).find(|result
| result
.is_useful()).unwrap_or(NotUseful
)
628 let matrix
= rows
.iter().filter_map(|r
| {
629 if r
[0].is_wildcard() {
630 Some(r
[1..].to_vec())
635 match is_useful(cx
, &matrix
, &v
[1..], witness
) {
636 UsefulWithWitness(pats
) => {
638 let new_witnesses
= if used_ctors
.is_empty() {
639 // All constructors are unused. Add wild patterns
640 // rather than each individual constructor
641 pats
.into_iter().map(|mut witness
| {
642 witness
.0.push(Pattern
{
645 kind
: box PatternKind
::Wild
,
650 pats
.into_iter().flat_map(|witness
| {
651 missing_ctors
.iter().map(move |ctor
| {
652 witness
.clone().push_wild_constructor(cx
, ctor
, pcx
.ty
)
656 UsefulWithWitness(new_witnesses
)
664 fn is_useful_specialized
<'p
, 'a
:'p
, 'tcx
: 'a
>(
665 cx
: &mut MatchCheckCtxt
<'a
, 'tcx
>,
666 &Matrix(ref m
): &Matrix
<'p
, 'tcx
>,
667 v
: &[&'p Pattern
<'tcx
>],
668 ctor
: Constructor
<'tcx
>,
670 witness
: WitnessPreference
) -> Usefulness
<'tcx
>
672 debug
!("is_useful_specialized({:?}, {:?}, {:?})", v
, ctor
, lty
);
673 let sub_pat_tys
= constructor_sub_pattern_tys(cx
, &ctor
, lty
);
674 let wild_patterns_owned
: Vec
<_
> = sub_pat_tys
.iter().map(|ty
| {
678 kind
: box PatternKind
::Wild
,
681 let wild_patterns
: Vec
<_
> = wild_patterns_owned
.iter().collect();
682 let matrix
= Matrix(m
.iter().flat_map(|r
| {
683 specialize(cx
, &r
[..], &ctor
, &wild_patterns
)
685 match specialize(cx
, v
, &ctor
, &wild_patterns
) {
686 Some(v
) => match is_useful(cx
, &matrix
, &v
[..], witness
) {
687 UsefulWithWitness(witnesses
) => UsefulWithWitness(
688 witnesses
.into_iter()
689 .map(|witness
| witness
.apply_constructor(cx
, &ctor
, lty
))
698 /// Determines the constructors that the given pattern can be specialized to.
700 /// In most cases, there's only one constructor that a specific pattern
701 /// represents, such as a specific enum variant or a specific literal value.
702 /// Slice patterns, however, can match slices of different lengths. For instance,
703 /// `[a, b, ..tail]` can match a slice of length 2, 3, 4 and so on.
705 /// Returns None in case of a catch-all, which can't be specialized.
706 fn pat_constructors
<'tcx
>(_cx
: &mut MatchCheckCtxt
,
709 -> Option
<Vec
<Constructor
<'tcx
>>>
712 PatternKind
::Binding { .. }
| PatternKind
::Wild
=>
714 PatternKind
::Leaf { .. }
| PatternKind
::Deref { .. }
=>
716 PatternKind
::Variant { adt_def, variant_index, .. }
=>
717 Some(vec
![Variant(adt_def
.variants
[variant_index
].did
)]),
718 PatternKind
::Constant { ref value }
=>
719 Some(vec
![ConstantValue(value
.clone())]),
720 PatternKind
::Range { ref lo, ref hi, ref end }
=>
721 Some(vec
![ConstantRange(lo
.clone(), hi
.clone(), end
.clone())]),
722 PatternKind
::Array { .. }
=> match pcx
.ty
.sty
{
723 ty
::TyArray(_
, length
) => Some(vec
![Slice(length
)]),
724 _
=> span_bug
!(pat
.span
, "bad ty {:?} for array pattern", pcx
.ty
)
726 PatternKind
::Slice { ref prefix, ref slice, ref suffix }
=> {
727 let pat_len
= prefix
.len() + suffix
.len();
729 Some((pat_len
..pcx
.max_slice_length
+1).map(Slice
).collect())
731 Some(vec
![Slice(pat_len
)])
737 /// This computes the arity of a constructor. The arity of a constructor
738 /// is how many subpattern patterns of that constructor should be expanded to.
740 /// For instance, a tuple pattern (_, 42, Some([])) has the arity of 3.
741 /// A struct pattern's arity is the number of fields it contains, etc.
742 fn constructor_arity(_cx
: &MatchCheckCtxt
, ctor
: &Constructor
, ty
: Ty
) -> usize {
743 debug
!("constructor_arity({:?}, {:?})", ctor
, ty
);
745 ty
::TyTuple(ref fs
, _
) => fs
.len(),
746 ty
::TySlice(..) | ty
::TyArray(..) => match *ctor
{
747 Slice(length
) => length
,
748 ConstantValue(_
) => 0,
749 _
=> bug
!("bad slice pattern {:?} {:?}", ctor
, ty
)
752 ty
::TyAdt(adt
, _
) => {
753 adt
.variants
[ctor
.variant_index_for_adt(adt
)].fields
.len()
759 /// This computes the types of the sub patterns that a constructor should be
762 /// For instance, a tuple pattern (43u32, 'a') has sub pattern types [u32, char].
763 fn constructor_sub_pattern_tys
<'a
, 'tcx
: 'a
>(cx
: &MatchCheckCtxt
<'a
, 'tcx
>,
765 ty
: Ty
<'tcx
>) -> Vec
<Ty
<'tcx
>>
767 debug
!("constructor_sub_pattern_tys({:?}, {:?})", ctor
, ty
);
769 ty
::TyTuple(ref fs
, _
) => fs
.into_iter().map(|t
| *t
).collect(),
770 ty
::TySlice(ty
) | ty
::TyArray(ty
, _
) => match *ctor
{
771 Slice(length
) => repeat(ty
).take(length
).collect(),
772 ConstantValue(_
) => vec
![],
773 _
=> bug
!("bad slice pattern {:?} {:?}", ctor
, ty
)
775 ty
::TyRef(_
, ref ty_and_mut
) => vec
![ty_and_mut
.ty
],
776 ty
::TyAdt(adt
, substs
) => {
777 adt
.variants
[ctor
.variant_index_for_adt(adt
)].fields
.iter().map(|field
| {
778 let is_visible
= adt
.is_enum()
779 || field
.vis
.is_accessible_from(cx
.module
, cx
.tcx
);
781 field
.ty(cx
.tcx
, substs
)
783 // Treat all non-visible fields as nil. They
784 // can't appear in any other pattern from
785 // this match (because they are private),
786 // so their type does not matter - but
787 // we don't want to know they are
797 fn slice_pat_covered_by_constructor(_tcx
: TyCtxt
, _span
: Span
,
800 slice
: &Option
<Pattern
>,
802 -> Result
<bool
, ErrorReported
> {
803 let data
= match *ctor
{
804 ConstantValue(ConstVal
::ByteStr(ref data
)) => data
,
808 let pat_len
= prefix
.len() + suffix
.len();
809 if data
.len() < pat_len
|| (slice
.is_none() && data
.len() > pat_len
) {
814 data
[..prefix
.len()].iter().zip(prefix
).chain(
815 data
[data
.len()-suffix
.len()..].iter().zip(suffix
))
818 box PatternKind
::Constant { ref value }
=> match *value
{
819 ConstVal
::Integral(ConstInt
::U8(u
)) => {
824 _
=> span_bug
!(pat
.span
, "bad const u8 {:?}", value
)
833 fn range_covered_by_constructor(tcx
: TyCtxt
, span
: Span
,
835 from
: &ConstVal
, to
: &ConstVal
,
837 -> Result
<bool
, ErrorReported
> {
838 let cmp_from
= |c_from
| Ok(compare_const_vals(tcx
, span
, c_from
, from
)?
!= Ordering
::Less
);
839 let cmp_to
= |c_to
| compare_const_vals(tcx
, span
, c_to
, to
);
841 ConstantValue(ref value
) => {
842 let to
= cmp_to(value
)?
;
843 let end
= (to
!= Ordering
::Greater
) ||
844 (end
== RangeEnd
::Excluded
&& to
== Ordering
::Equal
);
845 Ok(cmp_from(value
)?
&& end
)
847 ConstantRange(ref from
, ref to
, RangeEnd
::Included
) => {
848 let to
= cmp_to(to
)?
;
849 let end
= (to
!= Ordering
::Greater
) ||
850 (end
== RangeEnd
::Excluded
&& to
== Ordering
::Equal
);
851 Ok(cmp_from(from
)?
&& end
)
853 ConstantRange(ref from
, ref to
, RangeEnd
::Excluded
) => {
854 let to
= cmp_to(to
)?
;
855 let end
= (to
== Ordering
::Less
) ||
856 (end
== RangeEnd
::Excluded
&& to
== Ordering
::Equal
);
857 Ok(cmp_from(from
)?
&& end
)
864 fn patterns_for_variant
<'p
, 'a
: 'p
, 'tcx
: 'a
>(
865 subpatterns
: &'p
[FieldPattern
<'tcx
>],
866 wild_patterns
: &[&'p Pattern
<'tcx
>])
867 -> Vec
<&'p Pattern
<'tcx
>>
869 let mut result
= wild_patterns
.to_owned();
871 for subpat
in subpatterns
{
872 result
[subpat
.field
.index()] = &subpat
.pattern
;
875 debug
!("patterns_for_variant({:?}, {:?}) = {:?}", subpatterns
, wild_patterns
, result
);
879 /// This is the main specialization step. It expands the first pattern in the given row
880 /// into `arity` patterns based on the constructor. For most patterns, the step is trivial,
881 /// for instance tuple patterns are flattened and box patterns expand into their inner pattern.
883 /// OTOH, slice patterns with a subslice pattern (..tail) can be expanded into multiple
884 /// different patterns.
885 /// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing
886 /// fields filled with wild patterns.
887 fn specialize
<'p
, 'a
: 'p
, 'tcx
: 'a
>(
888 cx
: &mut MatchCheckCtxt
<'a
, 'tcx
>,
889 r
: &[&'p Pattern
<'tcx
>],
890 constructor
: &Constructor
,
891 wild_patterns
: &[&'p Pattern
<'tcx
>])
892 -> Option
<Vec
<&'p Pattern
<'tcx
>>>
896 let head
: Option
<Vec
<&Pattern
>> = match *pat
.kind
{
897 PatternKind
::Binding { .. }
| PatternKind
::Wild
=> {
898 Some(wild_patterns
.to_owned())
901 PatternKind
::Variant { adt_def, variant_index, ref subpatterns, .. }
=> {
902 let ref variant
= adt_def
.variants
[variant_index
];
903 if *constructor
== Variant(variant
.did
) {
904 Some(patterns_for_variant(subpatterns
, wild_patterns
))
910 PatternKind
::Leaf { ref subpatterns }
=> {
911 Some(patterns_for_variant(subpatterns
, wild_patterns
))
913 PatternKind
::Deref { ref subpattern }
=> {
914 Some(vec
![subpattern
])
917 PatternKind
::Constant { ref value }
=> {
919 Slice(..) => match *value
{
920 ConstVal
::ByteStr(ref data
) => {
921 if wild_patterns
.len() == data
.len() {
922 Some(cx
.lower_byte_str_pattern(pat
))
927 _
=> span_bug
!(pat
.span
,
928 "unexpected const-val {:?} with ctor {:?}", value
, constructor
)
931 match range_covered_by_constructor(
932 cx
.tcx
, pat
.span
, constructor
, value
, value
, RangeEnd
::Included
934 Ok(true) => Some(vec
![]),
936 Err(ErrorReported
) => None
,
942 PatternKind
::Range { ref lo, ref hi, ref end }
=> {
943 match range_covered_by_constructor(
944 cx
.tcx
, pat
.span
, constructor
, lo
, hi
, end
.clone()
946 Ok(true) => Some(vec
![]),
948 Err(ErrorReported
) => None
,
952 PatternKind
::Array { ref prefix, ref slice, ref suffix }
|
953 PatternKind
::Slice { ref prefix, ref slice, ref suffix }
=> {
956 let pat_len
= prefix
.len() + suffix
.len();
957 if let Some(slice_count
) = wild_patterns
.len().checked_sub(pat_len
) {
958 if slice_count
== 0 || slice
.is_some() {
961 wild_patterns
.iter().map(|p
| *p
)
974 ConstantValue(..) => {
975 match slice_pat_covered_by_constructor(
976 cx
.tcx
, pat
.span
, constructor
, prefix
, slice
, suffix
978 Ok(true) => Some(vec
![]),
980 Err(ErrorReported
) => None
983 _
=> span_bug
!(pat
.span
,
984 "unexpected ctor {:?} for slice pat", constructor
)
988 debug
!("specialize({:?}, {:?}) = {:?}", r
[0], wild_patterns
, head
);
990 head
.map(|mut head
| {
991 head
.extend_from_slice(&r
[1 ..]);