1 //! Note: tests specific to this file can be found in:
3 //! - `ui/pattern/usefulness`
5 //! - `ui/consts/const_in_pattern`
6 //! - `ui/rfc-2008-non-exhaustive`
7 //! - `ui/half-open-range-patterns`
8 //! - probably many others
10 //! I (Nadrieril) prefer to put new tests in `ui/pattern/usefulness` unless there's a specific
11 //! reason not to, for example if they depend on a particular feature like `or_patterns`.
15 //! This file includes the logic for exhaustiveness and reachability checking for pattern-matching.
16 //! Specifically, given a list of patterns for a type, we can tell whether:
17 //! (a) each pattern is reachable (reachability)
18 //! (b) the patterns cover every possible value for the type (exhaustiveness)
20 //! The algorithm implemented here is a modified version of the one described in [this
21 //! paper](http://moscova.inria.fr/~maranget/papers/warn/index.html). We have however generalized
22 //! it to accommodate the variety of patterns that Rust supports. We thus explain our version here,
23 //! without being as rigorous.
28 //! The core of the algorithm is the notion of "usefulness". A pattern `q` is said to be *useful*
29 //! relative to another pattern `p` of the same type if there is a value that is matched by `q` and
30 //! not matched by `p`. This generalizes to many `p`s: `q` is useful w.r.t. a list of patterns
31 //! `p_1 .. p_n` if there is a value that is matched by `q` and by none of the `p_i`. We write
32 //! `usefulness(p_1 .. p_n, q)` for a function that returns a list of such values. The aim of this
33 //! file is to compute it efficiently.
35 //! This is enough to compute reachability: a pattern in a `match` expression is reachable iff it
36 //! is useful w.r.t. the patterns above it:
38 //! # fn foo(x: Option<i32>) {
41 //! None => {}, // reachable: `None` is matched by this but not the branch above
42 //! Some(0) => {}, // unreachable: all the values this matches are already matched by
43 //! // `Some(_)` above
48 //! This is also enough to compute exhaustiveness: a match is exhaustive iff the wildcard `_`
49 //! pattern is _not_ useful w.r.t. the patterns in the match. The values returned by `usefulness`
50 //! are used to tell the user which values are missing.
51 //! ```compile_fail,E0004
52 //! # fn foo(x: Option<i32>) {
56 //! // not exhaustive: `_` is useful because it matches `Some(1)`
61 //! The entrypoint of this file is the [`compute_match_usefulness`] function, which computes
62 //! reachability for each match branch and exhaustiveness for the whole match.
65 //! # Constructors and fields
67 //! Note: we will often abbreviate "constructor" as "ctor".
69 //! The idea that powers everything that is done in this file is the following: a (matchable)
70 //! value is made from a constructor applied to a number of subvalues. Examples of constructors are
71 //! `Some`, `None`, `(,)` (the 2-tuple constructor), `Foo {..}` (the constructor for a struct
72 //! `Foo`), and `2` (the constructor for the number `2`). This is natural when we think of
73 //! pattern-matching, and this is the basis for what follows.
75 //! Some of the ctors listed above might feel weird: `None` and `2` don't take any arguments.
76 //! That's ok: those are ctors that take a list of 0 arguments; they are the simplest case of
77 //! ctors. We treat `2` as a ctor because `u64` and other number types behave exactly like a huge
78 //! `enum`, with one variant for each number. This allows us to see any matchable value as made up
79 //! from a tree of ctors, each having a set number of children. For example: `Foo { bar: None,
80 //! baz: Ok(0) }` is made from 4 different ctors, namely `Foo{..}`, `None`, `Ok` and `0`.
82 //! This idea can be extended to patterns: they are also made from constructors applied to fields.
83 //! A pattern for a given type is allowed to use all the ctors for values of that type (which we
84 //! call "value constructors"), but there are also pattern-only ctors. The most important one is
85 //! the wildcard (`_`), and the others are integer ranges (`0..=10`), variable-length slices (`[x,
86 //! ..]`), and or-patterns (`Ok(0) | Err(_)`). Examples of valid patterns are `42`, `Some(_)`, `Foo
87 //! { bar: Some(0) | None, baz: _ }`. Note that a binder in a pattern (e.g. `Some(x)`) matches the
88 //! same values as a wildcard (e.g. `Some(_)`), so we treat both as wildcards.
90 //! From this deconstruction we can compute whether a given value matches a given pattern; we
91 //! simply look at ctors one at a time. Given a pattern `p` and a value `v`, we want to compute
92 //! `matches!(v, p)`. It's mostly straightforward: we compare the head ctors and when they match
93 //! we compare their fields recursively. A few representative examples:
95 //! - `matches!(v, _) := true`
96 //! - `matches!((v0, v1), (p0, p1)) := matches!(v0, p0) && matches!(v1, p1)`
97 //! - `matches!(Foo { bar: v0, baz: v1 }, Foo { bar: p0, baz: p1 }) := matches!(v0, p0) && matches!(v1, p1)`
98 //! - `matches!(Ok(v0), Ok(p0)) := matches!(v0, p0)`
99 //! - `matches!(Ok(v0), Err(p0)) := false` (incompatible variants)
100 //! - `matches!(v, 1..=100) := matches!(v, 1) || ... || matches!(v, 100)`
101 //! - `matches!([v0], [p0, .., p1]) := false` (incompatible lengths)
102 //! - `matches!([v0, v1, v2], [p0, .., p1]) := matches!(v0, p0) && matches!(v2, p1)`
103 //! - `matches!(v, p0 | p1) := matches!(v, p0) || matches!(v, p1)`
105 //! Constructors, fields and relevant operations are defined in the [`super::deconstruct_pat`] module.
107 //! Note: this constructors/fields distinction may not straightforwardly apply to every Rust type.
108 //! For example a value of type `Rc<u64>` can't be deconstructed that way, and `&str` has an
109 //! infinitude of constructors. There are also subtleties with visibility of fields and
110 //! uninhabitedness and various other things. The constructors idea can be extended to handle most
111 //! of these subtleties though; caveats are documented where relevant throughout the code.
113 //! Whether constructors cover each other is computed by [`Constructor::is_covered_by`].
118 //! Recall that we wish to compute `usefulness(p_1 .. p_n, q)`: given a list of patterns `p_1 ..
119 //! p_n` and a pattern `q`, all of the same type, we want to find a list of values (called
120 //! "witnesses") that are matched by `q` and by none of the `p_i`. We obviously don't just
121 //! enumerate all possible values. From the discussion above we see that we can proceed
122 //! ctor-by-ctor: for each value ctor of the given type, we ask "is there a value that starts with
123 //! this constructor and matches `q` and none of the `p_i`?". As we saw above, there's a lot we can
124 //! say from knowing only the first constructor of our candidate value.
126 //! Let's take the following example:
127 //! ```compile_fail,E0004
128 //! # enum Enum { Variant1(()), Variant2(Option<bool>, u32)}
129 //! # fn foo(x: Enum) {
131 //! Enum::Variant1(_) => {} // `p1`
132 //! Enum::Variant2(None, 0) => {} // `p2`
133 //! Enum::Variant2(Some(_), 0) => {} // `q`
138 //! We can easily see that if our candidate value `v` starts with `Variant1` it will not match `q`.
139 //! If `v = Variant2(v0, v1)` however, whether or not it matches `p2` and `q` will depend on `v0`
140 //! and `v1`. In fact, such a `v` will be a witness of usefulness of `q` exactly when the tuple
141 //! `(v0, v1)` is a witness of usefulness of `q'` in the following reduced match:
143 //! ```compile_fail,E0004
144 //! # fn foo(x: (Option<bool>, u32)) {
146 //! (None, 0) => {} // `p2'`
147 //! (Some(_), 0) => {} // `q'`
152 //! This motivates a new step in computing usefulness, that we call _specialization_.
153 //! Specialization consist of filtering a list of patterns for those that match a constructor, and
154 //! then looking into the constructor's fields. This enables usefulness to be computed recursively.
156 //! Instead of acting on a single pattern in each row, we will consider a list of patterns for each
157 //! row, and we call such a list a _pattern-stack_. The idea is that we will specialize the
158 //! leftmost pattern, which amounts to popping the constructor and pushing its fields, which feels
159 //! like a stack. We note a pattern-stack simply with `[p_1 ... p_n]`.
160 //! Here's a sequence of specializations of a list of pattern-stacks, to illustrate what's
162 //! ```ignore (illustrative)
163 //! [Enum::Variant1(_)]
164 //! [Enum::Variant2(None, 0)]
165 //! [Enum::Variant2(Some(_), 0)]
166 //! //==>> specialize with `Variant2`
169 //! //==>> specialize with `Some`
171 //! //==>> specialize with `true` (say the type was `bool`)
173 //! //==>> specialize with `0`
177 //! The function `specialize(c, p)` takes a value constructor `c` and a pattern `p`, and returns 0
178 //! or more pattern-stacks. If `c` does not match the head constructor of `p`, it returns nothing;
179 //! otherwise if returns the fields of the constructor. This only returns more than one
180 //! pattern-stack if `p` has a pattern-only constructor.
182 //! - Specializing for the wrong constructor returns nothing
184 //! `specialize(None, Some(p0)) := []`
186 //! - Specializing for the correct constructor returns a single row with the fields
188 //! `specialize(Variant1, Variant1(p0, p1, p2)) := [[p0, p1, p2]]`
190 //! `specialize(Foo{..}, Foo { bar: p0, baz: p1 }) := [[p0, p1]]`
192 //! - For or-patterns, we specialize each branch and concatenate the results
194 //! `specialize(c, p0 | p1) := specialize(c, p0) ++ specialize(c, p1)`
196 //! - We treat the other pattern constructors as if they were a large or-pattern of all the
199 //! `specialize(c, _) := specialize(c, Variant1(_) | Variant2(_, _) | ...)`
201 //! `specialize(c, 1..=100) := specialize(c, 1 | ... | 100)`
203 //! `specialize(c, [p0, .., p1]) := specialize(c, [p0, p1] | [p0, _, p1] | [p0, _, _, p1] | ...)`
205 //! - If `c` is a pattern-only constructor, `specialize` is defined on a case-by-case basis. See
206 //! the discussion about constructor splitting in [`super::deconstruct_pat`].
209 //! We then extend this function to work with pattern-stacks as input, by acting on the first
210 //! column and keeping the other columns untouched.
212 //! Specialization for the whole matrix is done in [`Matrix::specialize_constructor`]. Note that
213 //! or-patterns in the first column are expanded before being stored in the matrix. Specialization
214 //! for a single patstack is done from a combination of [`Constructor::is_covered_by`] and
215 //! [`PatStack::pop_head_constructor`]. The internals of how it's done mostly live in the
216 //! [`Fields`] struct.
219 //! # Computing usefulness
221 //! We now have all we need to compute usefulness. The inputs to usefulness are a list of
222 //! pattern-stacks `p_1 ... p_n` (one per row), and a new pattern_stack `q`. The paper and this
223 //! file calls the list of patstacks a _matrix_. They must all have the same number of columns and
224 //! the patterns in a given column must all have the same type. `usefulness` returns a (possibly
225 //! empty) list of witnesses of usefulness. These witnesses will also be pattern-stacks.
227 //! - base case: `n_columns == 0`.
228 //! Since a pattern-stack functions like a tuple of patterns, an empty one functions like the
229 //! unit type. Thus `q` is useful iff there are no rows above it, i.e. if `n == 0`.
231 //! - inductive case: `n_columns > 0`.
232 //! We need a way to list the constructors we want to try. We will be more clever in the next
233 //! section but for now assume we list all value constructors for the type of the first column.
235 //! - for each such ctor `c`:
237 //! - for each `q'` returned by `specialize(c, q)`:
239 //! - we compute `usefulness(specialize(c, p_1) ... specialize(c, p_n), q')`
241 //! - for each witness found, we revert specialization by pushing the constructor `c` on top.
243 //! - We return the concatenation of all the witnesses found, if any.
246 //! ```ignore (illustrative)
247 //! [Some(true)] // p_1
250 //! //==>> try `None`: `specialize(None, q)` returns nothing
251 //! //==>> try `Some`: `specialize(Some, q)` returns a single row
254 //! //==>> try `true`: `specialize(true, q')` returns a single row
257 //! //==>> base case; `n != 0` so `q''` is not useful.
258 //! //==>> go back up a step
261 //! //==>> try `false`: `specialize(false, q')` returns a single row
263 //! //==>> base case; `n == 0` so `q''` is useful. We return the single witness `[]`
266 //! //==>> undo the specialization with `false`
269 //! //==>> undo the specialization with `Some`
272 //! //==>> we have tried all the constructors. The output is the single witness `[Some(false)]`.
275 //! This computation is done in [`is_useful`]. In practice we don't care about the list of
276 //! witnesses when computing reachability; we only need to know whether any exist. We do keep the
277 //! witnesses when computing exhaustiveness to report them to the user.
280 //! # Making usefulness tractable: constructor splitting
282 //! We're missing one last detail: which constructors do we list? Naively listing all value
283 //! constructors cannot work for types like `u64` or `&str`, so we need to be more clever. The
284 //! first obvious insight is that we only want to list constructors that are covered by the head
285 //! constructor of `q`. If it's a value constructor, we only try that one. If it's a pattern-only
286 //! constructor, we use the final clever idea for this algorithm: _constructor splitting_, where we
287 //! group together constructors that behave the same.
289 //! The details are not necessary to understand this file, so we explain them in
290 //! [`super::deconstruct_pat`]. Splitting is done by the [`Constructor::split`] function.
292 use self::ArmType
::*;
293 use self::Usefulness
::*;
295 use super::check_match
::{joined_uncovered_patterns, pattern_not_covered_label}
;
296 use super::deconstruct_pat
::{Constructor, DeconstructedPat, Fields, SplitWildcard}
;
298 use rustc_data_structures
::captures
::Captures
;
300 use rustc_arena
::TypedArena
;
301 use rustc_data_structures
::stack
::ensure_sufficient_stack
;
302 use rustc_hir
::def_id
::DefId
;
303 use rustc_hir
::HirId
;
304 use rustc_middle
::ty
::{self, Ty, TyCtxt}
;
305 use rustc_session
::lint
::builtin
::NON_EXHAUSTIVE_OMITTED_PATTERNS
;
306 use rustc_span
::{Span, DUMMY_SP}
;
308 use smallvec
::{smallvec, SmallVec}
;
312 pub(crate) struct MatchCheckCtxt
<'p
, 'tcx
> {
313 pub(crate) tcx
: TyCtxt
<'tcx
>,
314 /// The module in which the match occurs. This is necessary for
315 /// checking inhabited-ness of types because whether a type is (visibly)
316 /// inhabited can depend on whether it was defined in the current module or
317 /// not. E.g., `struct Foo { _private: ! }` cannot be seen to be empty
318 /// outside its module and should not be matchable with an empty match statement.
319 pub(crate) module
: DefId
,
320 pub(crate) param_env
: ty
::ParamEnv
<'tcx
>,
321 pub(crate) pattern_arena
: &'p TypedArena
<DeconstructedPat
<'p
, 'tcx
>>,
324 impl<'a
, 'tcx
> MatchCheckCtxt
<'a
, 'tcx
> {
325 pub(super) fn is_uninhabited(&self, ty
: Ty
<'tcx
>) -> bool
{
326 if self.tcx
.features().exhaustive_patterns
{
327 self.tcx
.is_ty_uninhabited_from(self.module
, ty
, self.param_env
)
333 /// Returns whether the given type is an enum from another crate declared `#[non_exhaustive]`.
334 pub(super) fn is_foreign_non_exhaustive_enum(&self, ty
: Ty
<'tcx
>) -> bool
{
336 ty
::Adt(def
, ..) => {
337 def
.is_enum() && def
.is_variant_list_non_exhaustive() && !def
.did().is_local()
344 #[derive(Copy, Clone)]
345 pub(super) struct PatCtxt
<'a
, 'p
, 'tcx
> {
346 pub(super) cx
: &'a MatchCheckCtxt
<'p
, 'tcx
>,
347 /// Type of the current column under investigation.
348 pub(super) ty
: Ty
<'tcx
>,
349 /// Span of the current pattern under investigation.
350 pub(super) span
: Span
,
351 /// Whether the current pattern is the whole pattern as found in a match arm, or if it's a
353 pub(super) is_top_level
: bool
,
354 /// Whether the current pattern is from a `non_exhaustive` enum.
355 pub(super) is_non_exhaustive
: bool
,
358 impl<'a
, 'p
, 'tcx
> fmt
::Debug
for PatCtxt
<'a
, 'p
, 'tcx
> {
359 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
360 f
.debug_struct("PatCtxt").field("ty", &self.ty
).finish()
364 /// A row of a matrix. Rows of len 1 are very common, which is why `SmallVec[_; 2]`
367 struct PatStack
<'p
, 'tcx
> {
368 pats
: SmallVec
<[&'p DeconstructedPat
<'p
, 'tcx
>; 2]>,
371 impl<'p
, 'tcx
> PatStack
<'p
, 'tcx
> {
372 fn from_pattern(pat
: &'p DeconstructedPat
<'p
, 'tcx
>) -> Self {
373 Self::from_vec(smallvec
![pat
])
376 fn from_vec(vec
: SmallVec
<[&'p DeconstructedPat
<'p
, 'tcx
>; 2]>) -> Self {
377 PatStack { pats: vec }
380 fn is_empty(&self) -> bool
{
384 fn len(&self) -> usize {
388 fn head(&self) -> &'p DeconstructedPat
<'p
, 'tcx
> {
392 fn iter(&self) -> impl Iterator
<Item
= &DeconstructedPat
<'p
, 'tcx
>> {
393 self.pats
.iter().copied()
396 // Recursively expand the first pattern into its subpatterns. Only useful if the pattern is an
397 // or-pattern. Panics if `self` is empty.
398 fn expand_or_pat
<'a
>(&'a
self) -> impl Iterator
<Item
= PatStack
<'p
, 'tcx
>> + Captures
<'a
> {
399 self.head().iter_fields().map(move |pat
| {
400 let mut new_patstack
= PatStack
::from_pattern(pat
);
401 new_patstack
.pats
.extend_from_slice(&self.pats
[1..]);
406 /// This computes `S(self.head().ctor(), self)`. See top of the file for explanations.
408 /// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing
409 /// fields filled with wild patterns.
411 /// This is roughly the inverse of `Constructor::apply`.
412 fn pop_head_constructor(
414 cx
: &MatchCheckCtxt
<'p
, 'tcx
>,
415 ctor
: &Constructor
<'tcx
>,
416 ) -> PatStack
<'p
, 'tcx
> {
417 // We pop the head pattern and push the new fields extracted from the arguments of
419 let mut new_fields
: SmallVec
<[_
; 2]> = self.head().specialize(cx
, ctor
);
420 new_fields
.extend_from_slice(&self.pats
[1..]);
421 PatStack
::from_vec(new_fields
)
425 /// Pretty-printing for matrix row.
426 impl<'p
, 'tcx
> fmt
::Debug
for PatStack
<'p
, 'tcx
> {
427 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
429 for pat
in self.iter() {
430 write
!(f
, " {:?} +", pat
)?
;
438 pub(super) struct Matrix
<'p
, 'tcx
> {
439 patterns
: Vec
<PatStack
<'p
, 'tcx
>>,
442 impl<'p
, 'tcx
> Matrix
<'p
, 'tcx
> {
444 Matrix { patterns: vec![] }
447 /// Number of columns of this matrix. `None` is the matrix is empty.
448 pub(super) fn column_count(&self) -> Option
<usize> {
449 self.patterns
.get(0).map(|r
| r
.len())
452 /// Pushes a new row to the matrix. If the row starts with an or-pattern, this recursively
454 fn push(&mut self, row
: PatStack
<'p
, 'tcx
>) {
455 if !row
.is_empty() && row
.head().is_or_pat() {
456 self.patterns
.extend(row
.expand_or_pat());
458 self.patterns
.push(row
);
462 /// Iterate over the first component of each row
465 ) -> impl Iterator
<Item
= &'p DeconstructedPat
<'p
, 'tcx
>> + Clone
+ Captures
<'a
> {
466 self.patterns
.iter().map(|r
| r
.head())
469 /// This computes `S(constructor, self)`. See top of the file for explanations.
470 fn specialize_constructor(
472 pcx
: PatCtxt
<'_
, 'p
, 'tcx
>,
473 ctor
: &Constructor
<'tcx
>,
474 ) -> Matrix
<'p
, 'tcx
> {
475 let mut matrix
= Matrix
::empty();
476 for row
in &self.patterns
{
477 if ctor
.is_covered_by(pcx
, row
.head().ctor()) {
478 let new_row
= row
.pop_head_constructor(pcx
.cx
, ctor
);
479 matrix
.push(new_row
);
486 /// Pretty-printer for matrices of patterns, example:
490 /// + true + [First] +
491 /// + true + [Second(true)] +
493 /// + _ + [_, _, tail @ ..] +
495 impl<'p
, 'tcx
> fmt
::Debug
for Matrix
<'p
, 'tcx
> {
496 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
499 let Matrix { patterns: m, .. }
= self;
500 let pretty_printed_matrix
: Vec
<Vec
<String
>> =
501 m
.iter().map(|row
| row
.iter().map(|pat
| format
!("{:?}", pat
)).collect()).collect();
503 let column_count
= m
.iter().map(|row
| row
.len()).next().unwrap_or(0);
504 assert
!(m
.iter().all(|row
| row
.len() == column_count
));
505 let column_widths
: Vec
<usize> = (0..column_count
)
506 .map(|col
| pretty_printed_matrix
.iter().map(|row
| row
[col
].len()).max().unwrap_or(0))
509 for row
in pretty_printed_matrix
{
511 for (column
, pat_str
) in row
.into_iter().enumerate() {
513 write
!(f
, "{:1$}", pat_str
, column_widths
[column
])?
;
522 /// This carries the results of computing usefulness, as described at the top of the file. When
523 /// checking usefulness of a match branch, we use the `NoWitnesses` variant, which also keeps track
524 /// of potential unreachable sub-patterns (in the presence of or-patterns). When checking
525 /// exhaustiveness of a whole match, we use the `WithWitnesses` variant, which carries a list of
526 /// witnesses of non-exhaustiveness when there are any.
527 /// Which variant to use is dictated by `ArmType`.
529 enum Usefulness
<'p
, 'tcx
> {
530 /// If we don't care about witnesses, simply remember if the pattern was useful.
531 NoWitnesses { useful: bool }
,
532 /// Carries a list of witnesses of non-exhaustiveness. If empty, indicates that the whole
533 /// pattern is unreachable.
534 WithWitnesses(Vec
<Witness
<'p
, 'tcx
>>),
537 impl<'p
, 'tcx
> Usefulness
<'p
, 'tcx
> {
538 fn new_useful(preference
: ArmType
) -> Self {
540 // A single (empty) witness of reachability.
541 FakeExtraWildcard
=> WithWitnesses(vec
![Witness(vec
![])]),
542 RealArm
=> NoWitnesses { useful: true }
,
546 fn new_not_useful(preference
: ArmType
) -> Self {
548 FakeExtraWildcard
=> WithWitnesses(vec
![]),
549 RealArm
=> NoWitnesses { useful: false }
,
553 fn is_useful(&self) -> bool
{
555 Usefulness
::NoWitnesses { useful }
=> *useful
,
556 Usefulness
::WithWitnesses(witnesses
) => !witnesses
.is_empty(),
560 /// Combine usefulnesses from two branches. This is an associative operation.
561 fn extend(&mut self, other
: Self) {
562 match (&mut *self, other
) {
563 (WithWitnesses(_
), WithWitnesses(o
)) if o
.is_empty() => {}
564 (WithWitnesses(s
), WithWitnesses(o
)) if s
.is_empty() => *self = WithWitnesses(o
),
565 (WithWitnesses(s
), WithWitnesses(o
)) => s
.extend(o
),
566 (NoWitnesses { useful: s_useful }
, NoWitnesses { useful: o_useful }
) => {
567 *s_useful
= *s_useful
|| o_useful
573 /// After calculating usefulness after a specialization, call this to reconstruct a usefulness
574 /// that makes sense for the matrix pre-specialization. This new usefulness can then be merged
575 /// with the results of specializing with the other constructors.
576 fn apply_constructor(
578 pcx
: PatCtxt
<'_
, 'p
, 'tcx
>,
579 matrix
: &Matrix
<'p
, 'tcx
>, // used to compute missing ctors
580 ctor
: &Constructor
<'tcx
>,
583 NoWitnesses { .. }
=> self,
584 WithWitnesses(ref witnesses
) if witnesses
.is_empty() => self,
585 WithWitnesses(witnesses
) => {
586 let new_witnesses
= if let Constructor
::Missing { .. }
= ctor
{
587 // We got the special `Missing` constructor, so each of the missing constructors
588 // gives a new pattern that is not caught by the match. We list those patterns.
589 let new_patterns
= if pcx
.is_non_exhaustive
{
590 // Here we don't want the user to try to list all variants, we want them to add
591 // a wildcard, so we only suggest that.
592 vec
![DeconstructedPat
::wildcard(pcx
.ty
)]
594 let mut split_wildcard
= SplitWildcard
::new(pcx
);
595 split_wildcard
.split(pcx
, matrix
.heads().map(DeconstructedPat
::ctor
));
597 // This lets us know if we skipped any variants because they are marked
598 // `doc(hidden)` or they are unstable feature gate (only stdlib types).
599 let mut hide_variant_show_wild
= false;
600 // Construct for each missing constructor a "wild" version of this
601 // constructor, that matches everything that can be built with
602 // it. For example, if `ctor` is a `Constructor::Variant` for
603 // `Option::Some`, we get the pattern `Some(_)`.
604 let mut new
: Vec
<DeconstructedPat
<'_
, '_
>> = split_wildcard
606 .filter_map(|missing_ctor
| {
607 // Check if this variant is marked `doc(hidden)`
608 if missing_ctor
.is_doc_hidden_variant(pcx
)
609 || missing_ctor
.is_unstable_variant(pcx
)
611 hide_variant_show_wild
= true;
614 Some(DeconstructedPat
::wild_from_ctor(pcx
, missing_ctor
.clone()))
618 if hide_variant_show_wild
{
619 new
.push(DeconstructedPat
::wildcard(pcx
.ty
));
627 .flat_map(|witness
| {
628 new_patterns
.iter().map(move |pat
| {
634 .map(DeconstructedPat
::clone_and_forget_reachability
)
643 .map(|witness
| witness
.apply_constructor(pcx
, &ctor
))
646 WithWitnesses(new_witnesses
)
652 #[derive(Copy, Clone, Debug)]
658 /// A witness of non-exhaustiveness for error reporting, represented
659 /// as a list of patterns (in reverse order of construction) with
660 /// wildcards inside to represent elements that can take any inhabitant
661 /// of the type as a value.
663 /// A witness against a list of patterns should have the same types
664 /// and length as the pattern matched against. Because Rust `match`
665 /// is always against a single pattern, at the end the witness will
666 /// have length 1, but in the middle of the algorithm, it can contain
667 /// multiple patterns.
669 /// For example, if we are constructing a witness for the match against
671 /// ```compile_fail,E0004
672 /// # #![feature(type_ascription)]
673 /// struct Pair(Option<(u32, u32)>, bool);
674 /// # fn foo(p: Pair) {
675 /// match (p: Pair) {
676 /// Pair(None, _) => {}
677 /// Pair(_, false) => {}
682 /// We'll perform the following steps:
683 /// 1. Start with an empty witness
684 /// `Witness(vec![])`
685 /// 2. Push a witness `true` against the `false`
686 /// `Witness(vec![true])`
687 /// 3. Push a witness `Some(_)` against the `None`
688 /// `Witness(vec![true, Some(_)])`
689 /// 4. Apply the `Pair` constructor to the witnesses
690 /// `Witness(vec![Pair(Some(_), true)])`
692 /// The final `Pair(Some(_), true)` is then the resulting witness.
694 pub(crate) struct Witness
<'p
, 'tcx
>(Vec
<DeconstructedPat
<'p
, 'tcx
>>);
696 impl<'p
, 'tcx
> Witness
<'p
, 'tcx
> {
697 /// Asserts that the witness contains a single pattern, and returns it.
698 fn single_pattern(self) -> DeconstructedPat
<'p
, 'tcx
> {
699 assert_eq
!(self.0.len(), 1);
700 self.0.into_iter
().next().unwrap()
703 /// Constructs a partial witness for a pattern given a list of
704 /// patterns expanded by the specialization step.
706 /// When a pattern P is discovered to be useful, this function is used bottom-up
707 /// to reconstruct a complete witness, e.g., a pattern P' that covers a subset
708 /// of values, V, where each value in that set is not covered by any previously
709 /// used patterns and is covered by the pattern P'. Examples:
711 /// left_ty: tuple of 3 elements
712 /// pats: [10, 20, _] => (10, 20, _)
714 /// left_ty: struct X { a: (bool, &'static str), b: usize}
715 /// pats: [(false, "foo"), 42] => X { a: (false, "foo"), b: 42 }
716 fn apply_constructor(mut self, pcx
: PatCtxt
<'_
, 'p
, 'tcx
>, ctor
: &Constructor
<'tcx
>) -> Self {
718 let len
= self.0.len();
719 let arity
= ctor
.arity(pcx
);
720 let pats
= self.0.drain((len
- arity
)..).rev();
721 let fields
= Fields
::from_iter(pcx
.cx
, pats
);
722 DeconstructedPat
::new(ctor
.clone(), fields
, pcx
.ty
, DUMMY_SP
)
731 /// Report that a match of a `non_exhaustive` enum marked with `non_exhaustive_omitted_patterns`
732 /// is not exhaustive enough.
734 /// NB: The partner lint for structs lives in `compiler/rustc_typeck/src/check/pat.rs`.
735 fn lint_non_exhaustive_omitted_patterns
<'p
, 'tcx
>(
736 cx
: &MatchCheckCtxt
<'p
, 'tcx
>,
740 witnesses
: Vec
<DeconstructedPat
<'p
, 'tcx
>>,
742 let joined_patterns
= joined_uncovered_patterns(cx
, &witnesses
);
743 cx
.tcx
.struct_span_lint_hir(NON_EXHAUSTIVE_OMITTED_PATTERNS
, hir_id
, sp
, |build
| {
744 let mut lint
= build
.build("some variants are not matched explicitly");
745 lint
.span_label(sp
, pattern_not_covered_label(&witnesses
, &joined_patterns
));
747 "ensure that all variants are matched explicitly by adding the suggested match arms",
750 "the matched value is of type `{}` and the `non_exhaustive_omitted_patterns` attribute was found",
757 /// Algorithm from <http://moscova.inria.fr/~maranget/papers/warn/index.html>.
758 /// The algorithm from the paper has been modified to correctly handle empty
759 /// types. The changes are:
760 /// (0) We don't exit early if the pattern matrix has zero rows. We just
761 /// continue to recurse over columns.
762 /// (1) all_constructors will only return constructors that are statically
763 /// possible. E.g., it will only return `Ok` for `Result<T, !>`.
765 /// This finds whether a (row) vector `v` of patterns is 'useful' in relation
766 /// to a set of such vectors `m` - this is defined as there being a set of
767 /// inputs that will match `v` but not any of the sets in `m`.
769 /// All the patterns at each column of the `matrix ++ v` matrix must have the same type.
771 /// This is used both for reachability checking (if a pattern isn't useful in
772 /// relation to preceding patterns, it is not reachable) and exhaustiveness
773 /// checking (if a wildcard pattern is useful in relation to a matrix, the
774 /// matrix isn't exhaustive).
776 /// `is_under_guard` is used to inform if the pattern has a guard. If it
777 /// has one it must not be inserted into the matrix. This shouldn't be
778 /// relied on for soundness.
779 #[instrument(level = "debug", skip(cx, matrix, hir_id))]
780 fn is_useful
<'p
, 'tcx
>(
781 cx
: &MatchCheckCtxt
<'p
, 'tcx
>,
782 matrix
: &Matrix
<'p
, 'tcx
>,
783 v
: &PatStack
<'p
, 'tcx
>,
784 witness_preference
: ArmType
,
786 is_under_guard
: bool
,
788 ) -> Usefulness
<'p
, 'tcx
> {
789 debug
!("matrix,v={:?}{:?}", matrix
, v
);
790 let Matrix { patterns: rows, .. }
= matrix
;
792 // The base case. We are pattern-matching on () and the return value is
793 // based on whether our matrix has a row or not.
794 // NOTE: This could potentially be optimized by checking rows.is_empty()
795 // first and then, if v is non-empty, the return value is based on whether
796 // the type of the tuple we're checking is inhabited or not.
798 let ret
= if rows
.is_empty() {
799 Usefulness
::new_useful(witness_preference
)
801 Usefulness
::new_not_useful(witness_preference
)
807 debug_assert
!(rows
.iter().all(|r
| r
.len() == v
.len()));
809 let ty
= v
.head().ty();
810 let is_non_exhaustive
= cx
.is_foreign_non_exhaustive_enum(ty
);
811 debug
!("v.head: {:?}, v.span: {:?}", v
.head(), v
.head().span());
812 let pcx
= PatCtxt { cx, ty, span: v.head().span(), is_top_level, is_non_exhaustive }
;
814 // If the first pattern is an or-pattern, expand it.
815 let mut ret
= Usefulness
::new_not_useful(witness_preference
);
816 if v
.head().is_or_pat() {
817 debug
!("expanding or-pattern");
818 // We try each or-pattern branch in turn.
819 let mut matrix
= matrix
.clone();
820 for v
in v
.expand_or_pat() {
822 let usefulness
= ensure_sufficient_stack(|| {
823 is_useful(cx
, &matrix
, &v
, witness_preference
, hir_id
, is_under_guard
, false)
826 ret
.extend(usefulness
);
827 // If pattern has a guard don't add it to the matrix.
829 // We push the already-seen patterns into the matrix in order to detect redundant
830 // branches like `Some(_) | Some(0)`.
835 let v_ctor
= v
.head().ctor();
837 if let Constructor
::IntRange(ctor_range
) = &v_ctor
{
838 // Lint on likely incorrect range patterns (#63987)
839 ctor_range
.lint_overlapping_range_endpoints(
842 matrix
.column_count().unwrap_or(0),
846 // We split the head constructor of `v`.
847 let split_ctors
= v_ctor
.split(pcx
, matrix
.heads().map(DeconstructedPat
::ctor
));
848 let is_non_exhaustive_and_wild
= is_non_exhaustive
&& v_ctor
.is_wildcard();
849 // For each constructor, we compute whether there's a value that starts with it that would
850 // witness the usefulness of `v`.
851 let start_matrix
= &matrix
;
852 for ctor
in split_ctors
{
853 debug
!("specialize({:?})", ctor
);
854 // We cache the result of `Fields::wildcards` because it is used a lot.
855 let spec_matrix
= start_matrix
.specialize_constructor(pcx
, &ctor
);
856 let v
= v
.pop_head_constructor(cx
, &ctor
);
857 let usefulness
= ensure_sufficient_stack(|| {
858 is_useful(cx
, &spec_matrix
, &v
, witness_preference
, hir_id
, is_under_guard
, false)
860 let usefulness
= usefulness
.apply_constructor(pcx
, start_matrix
, &ctor
);
862 // When all the conditions are met we have a match with a `non_exhaustive` enum
863 // that has the potential to trigger the `non_exhaustive_omitted_patterns` lint.
864 // To understand the workings checkout `Constructor::split` and `SplitWildcard::new/into_ctors`
865 if is_non_exhaustive_and_wild
866 // We check that the match has a wildcard pattern and that that wildcard is useful,
867 // meaning there are variants that are covered by the wildcard. Without the check
868 // for `witness_preference` the lint would trigger on `if let NonExhaustiveEnum::A = foo {}`
869 && usefulness
.is_useful() && matches
!(witness_preference
, RealArm
)
872 Constructor
::Missing { nonexhaustive_enum_missing_real_variants: true }
876 let mut split_wildcard
= SplitWildcard
::new(pcx
);
877 split_wildcard
.split(pcx
, matrix
.heads().map(DeconstructedPat
::ctor
));
878 // Construct for each missing constructor a "wild" version of this
879 // constructor, that matches everything that can be built with
880 // it. For example, if `ctor` is a `Constructor::Variant` for
881 // `Option::Some`, we get the pattern `Some(_)`.
884 // Filter out the `NonExhaustive` because we want to list only real
885 // variants. Also remove any unstable feature gated variants.
886 // Because of how we computed `nonexhaustive_enum_missing_real_variants`,
887 // this will not return an empty `Vec`.
888 .filter(|c
| !(c
.is_non_exhaustive() || c
.is_unstable_variant(pcx
)))
890 .map(|missing_ctor
| DeconstructedPat
::wild_from_ctor(pcx
, missing_ctor
))
894 lint_non_exhaustive_omitted_patterns(pcx
.cx
, pcx
.ty
, pcx
.span
, hir_id
, patterns
);
897 ret
.extend(usefulness
);
902 v
.head().set_reachable();
909 /// The arm of a match expression.
910 #[derive(Clone, Copy, Debug)]
911 pub(crate) struct MatchArm
<'p
, 'tcx
> {
912 /// The pattern must have been lowered through `check_match::MatchVisitor::lower_pattern`.
913 pub(crate) pat
: &'p DeconstructedPat
<'p
, 'tcx
>,
914 pub(crate) hir_id
: HirId
,
915 pub(crate) has_guard
: bool
,
918 /// Indicates whether or not a given arm is reachable.
919 #[derive(Clone, Debug)]
920 pub(crate) enum Reachability
{
921 /// The arm is reachable. This additionally carries a set of or-pattern branches that have been
922 /// found to be unreachable despite the overall arm being reachable. Used only in the presence
923 /// of or-patterns, otherwise it stays empty.
924 Reachable(Vec
<Span
>),
925 /// The arm is unreachable.
929 /// The output of checking a match for exhaustiveness and arm reachability.
930 pub(crate) struct UsefulnessReport
<'p
, 'tcx
> {
931 /// For each arm of the input, whether that arm is reachable after the arms above it.
932 pub(crate) arm_usefulness
: Vec
<(MatchArm
<'p
, 'tcx
>, Reachability
)>,
933 /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of
935 pub(crate) non_exhaustiveness_witnesses
: Vec
<DeconstructedPat
<'p
, 'tcx
>>,
938 /// The entrypoint for the usefulness algorithm. Computes whether a match is exhaustive and which
939 /// of its arms are reachable.
941 /// Note: the input patterns must have been lowered through
942 /// `check_match::MatchVisitor::lower_pattern`.
943 #[instrument(skip(cx, arms), level = "debug")]
944 pub(crate) fn compute_match_usefulness
<'p
, 'tcx
>(
945 cx
: &MatchCheckCtxt
<'p
, 'tcx
>,
946 arms
: &[MatchArm
<'p
, 'tcx
>],
949 ) -> UsefulnessReport
<'p
, 'tcx
> {
950 let mut matrix
= Matrix
::empty();
951 let arm_usefulness
: Vec
<_
> = arms
956 let v
= PatStack
::from_pattern(arm
.pat
);
957 is_useful(cx
, &matrix
, &v
, RealArm
, arm
.hir_id
, arm
.has_guard
, true);
961 let reachability
= if arm
.pat
.is_reachable() {
962 Reachability
::Reachable(arm
.pat
.unreachable_spans())
964 Reachability
::Unreachable
970 let wild_pattern
= cx
.pattern_arena
.alloc(DeconstructedPat
::wildcard(scrut_ty
));
971 let v
= PatStack
::from_pattern(wild_pattern
);
972 let usefulness
= is_useful(cx
, &matrix
, &v
, FakeExtraWildcard
, scrut_hir_id
, false, true);
973 let non_exhaustiveness_witnesses
= match usefulness
{
974 WithWitnesses(pats
) => pats
.into_iter().map(|w
| w
.single_pattern()).collect(),
975 NoWitnesses { .. }
=> bug
!(),
977 UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }