aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_hir_ty/src/_match.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/ra_hir_ty/src/_match.rs')
-rw-r--r--crates/ra_hir_ty/src/_match.rs1411
1 files changed, 1411 insertions, 0 deletions
diff --git a/crates/ra_hir_ty/src/_match.rs b/crates/ra_hir_ty/src/_match.rs
new file mode 100644
index 000000000..f29a25505
--- /dev/null
+++ b/crates/ra_hir_ty/src/_match.rs
@@ -0,0 +1,1411 @@
1//! This module implements match statement exhaustiveness checking and usefulness checking
2//! for match arms.
3//!
4//! It is modeled on the rustc module `librustc_mir_build::hair::pattern::_match`, which
5//! contains very detailed documentation about the algorithms used here. I've duplicated
6//! most of that documentation below.
7//!
8//! This file includes the logic for exhaustiveness and usefulness checking for
9//! pattern-matching. Specifically, given a list of patterns for a type, we can
10//! tell whether:
11//! (a) the patterns cover every possible constructor for the type [exhaustiveness]
12//! (b) each pattern is necessary [usefulness]
13//!
14//! The algorithm implemented here is a modified version of the one described in:
15//! http://moscova.inria.fr/~maranget/papers/warn/index.html
16//! However, to save future implementors from reading the original paper, we
17//! summarise the algorithm here to hopefully save time and be a little clearer
18//! (without being so rigorous).
19//!
20//! The core of the algorithm revolves about a "usefulness" check. In particular, we
21//! are trying to compute a predicate `U(P, p)` where `P` is a list of patterns (we refer to this as
22//! a matrix). `U(P, p)` represents whether, given an existing list of patterns
23//! `P_1 ..= P_m`, adding a new pattern `p` will be "useful" (that is, cover previously-
24//! uncovered values of the type).
25//!
26//! If we have this predicate, then we can easily compute both exhaustiveness of an
27//! entire set of patterns and the individual usefulness of each one.
28//! (a) the set of patterns is exhaustive iff `U(P, _)` is false (i.e., adding a wildcard
29//! match doesn't increase the number of values we're matching)
30//! (b) a pattern `P_i` is not useful if `U(P[0..=(i-1), P_i)` is false (i.e., adding a
31//! pattern to those that have come before it doesn't increase the number of values
32//! we're matching).
33//!
34//! During the course of the algorithm, the rows of the matrix won't just be individual patterns,
35//! but rather partially-deconstructed patterns in the form of a list of patterns. The paper
36//! calls those pattern-vectors, and we will call them pattern-stacks. The same holds for the
37//! new pattern `p`.
38//!
39//! For example, say we have the following:
40//! ```
41//! // x: (Option<bool>, Result<()>)
42//! match x {
43//! (Some(true), _) => {}
44//! (None, Err(())) => {}
45//! (None, Err(_)) => {}
46//! }
47//! ```
48//! Here, the matrix `P` starts as:
49//! [
50//! [(Some(true), _)],
51//! [(None, Err(()))],
52//! [(None, Err(_))],
53//! ]
54//! We can tell it's not exhaustive, because `U(P, _)` is true (we're not covering
55//! `[(Some(false), _)]`, for instance). In addition, row 3 is not useful, because
56//! all the values it covers are already covered by row 2.
57//!
58//! A list of patterns can be thought of as a stack, because we are mainly interested in the top of
59//! the stack at any given point, and we can pop or apply constructors to get new pattern-stacks.
60//! To match the paper, the top of the stack is at the beginning / on the left.
61//!
62//! There are two important operations on pattern-stacks necessary to understand the algorithm:
63//! 1. We can pop a given constructor off the top of a stack. This operation is called
64//! `specialize`, and is denoted `S(c, p)` where `c` is a constructor (like `Some` or
65//! `None`) and `p` a pattern-stack.
66//! If the pattern on top of the stack can cover `c`, this removes the constructor and
67//! pushes its arguments onto the stack. It also expands OR-patterns into distinct patterns.
68//! Otherwise the pattern-stack is discarded.
69//! This essentially filters those pattern-stacks whose top covers the constructor `c` and
70//! discards the others.
71//!
72//! For example, the first pattern above initially gives a stack `[(Some(true), _)]`. If we
73//! pop the tuple constructor, we are left with `[Some(true), _]`, and if we then pop the
74//! `Some` constructor we get `[true, _]`. If we had popped `None` instead, we would get
75//! nothing back.
76//!
77//! This returns zero or more new pattern-stacks, as follows. We look at the pattern `p_1`
78//! on top of the stack, and we have four cases:
79//! 1.1. `p_1 = c(r_1, .., r_a)`, i.e. the top of the stack has constructor `c`. We
80//! push onto the stack the arguments of this constructor, and return the result:
81//! r_1, .., r_a, p_2, .., p_n
82//! 1.2. `p_1 = c'(r_1, .., r_a')` where `c ≠ c'`. We discard the current stack and
83//! return nothing.
84//! 1.3. `p_1 = _`. We push onto the stack as many wildcards as the constructor `c` has
85//! arguments (its arity), and return the resulting stack:
86//! _, .., _, p_2, .., p_n
87//! 1.4. `p_1 = r_1 | r_2`. We expand the OR-pattern and then recurse on each resulting
88//! stack:
89//! S(c, (r_1, p_2, .., p_n))
90//! S(c, (r_2, p_2, .., p_n))
91//!
92//! 2. We can pop a wildcard off the top of the stack. This is called `D(p)`, where `p` is
93//! a pattern-stack.
94//! This is used when we know there are missing constructor cases, but there might be
95//! existing wildcard patterns, so to check the usefulness of the matrix, we have to check
96//! all its *other* components.
97//!
98//! It is computed as follows. We look at the pattern `p_1` on top of the stack,
99//! and we have three cases:
100//! 1.1. `p_1 = c(r_1, .., r_a)`. We discard the current stack and return nothing.
101//! 1.2. `p_1 = _`. We return the rest of the stack:
102//! p_2, .., p_n
103//! 1.3. `p_1 = r_1 | r_2`. We expand the OR-pattern and then recurse on each resulting
104//! stack.
105//! D((r_1, p_2, .., p_n))
106//! D((r_2, p_2, .., p_n))
107//!
108//! Note that the OR-patterns are not always used directly in Rust, but are used to derive the
109//! exhaustive integer matching rules, so they're written here for posterity.
110//!
111//! Both those operations extend straightforwardly to a list or pattern-stacks, i.e. a matrix, by
112//! working row-by-row. Popping a constructor ends up keeping only the matrix rows that start with
113//! the given constructor, and popping a wildcard keeps those rows that start with a wildcard.
114//!
115//!
116//! The algorithm for computing `U`
117//! -------------------------------
118//! The algorithm is inductive (on the number of columns: i.e., components of tuple patterns).
119//! That means we're going to check the components from left-to-right, so the algorithm
120//! operates principally on the first component of the matrix and new pattern-stack `p`.
121//! This algorithm is realised in the `is_useful` function.
122//!
123//! Base case. (`n = 0`, i.e., an empty tuple pattern)
124//! - If `P` already contains an empty pattern (i.e., if the number of patterns `m > 0`),
125//! then `U(P, p)` is false.
126//! - Otherwise, `P` must be empty, so `U(P, p)` is true.
127//!
128//! Inductive step. (`n > 0`, i.e., whether there's at least one column
129//! [which may then be expanded into further columns later])
130//! We're going to match on the top of the new pattern-stack, `p_1`.
131//! - If `p_1 == c(r_1, .., r_a)`, i.e. we have a constructor pattern.
132//! Then, the usefulness of `p_1` can be reduced to whether it is useful when
133//! we ignore all the patterns in the first column of `P` that involve other constructors.
134//! This is where `S(c, P)` comes in:
135//! `U(P, p) := U(S(c, P), S(c, p))`
136//! This special case is handled in `is_useful_specialized`.
137//!
138//! For example, if `P` is:
139//! [
140//! [Some(true), _],
141//! [None, 0],
142//! ]
143//! and `p` is [Some(false), 0], then we don't care about row 2 since we know `p` only
144//! matches values that row 2 doesn't. For row 1 however, we need to dig into the
145//! arguments of `Some` to know whether some new value is covered. So we compute
146//! `U([[true, _]], [false, 0])`.
147//!
148//! - If `p_1 == _`, then we look at the list of constructors that appear in the first
149//! component of the rows of `P`:
150//! + If there are some constructors that aren't present, then we might think that the
151//! wildcard `_` is useful, since it covers those constructors that weren't covered
152//! before.
153//! That's almost correct, but only works if there were no wildcards in those first
154//! components. So we need to check that `p` is useful with respect to the rows that
155//! start with a wildcard, if there are any. This is where `D` comes in:
156//! `U(P, p) := U(D(P), D(p))`
157//!
158//! For example, if `P` is:
159//! [
160//! [_, true, _],
161//! [None, false, 1],
162//! ]
163//! and `p` is [_, false, _], the `Some` constructor doesn't appear in `P`. So if we
164//! only had row 2, we'd know that `p` is useful. However row 1 starts with a
165//! wildcard, so we need to check whether `U([[true, _]], [false, 1])`.
166//!
167//! + Otherwise, all possible constructors (for the relevant type) are present. In this
168//! case we must check whether the wildcard pattern covers any unmatched value. For
169//! that, we can think of the `_` pattern as a big OR-pattern that covers all
170//! possible constructors. For `Option`, that would mean `_ = None | Some(_)` for
171//! example. The wildcard pattern is useful in this case if it is useful when
172//! specialized to one of the possible constructors. So we compute:
173//! `U(P, p) := ∃(k ϵ constructors) U(S(k, P), S(k, p))`
174//!
175//! For example, if `P` is:
176//! [
177//! [Some(true), _],
178//! [None, false],
179//! ]
180//! and `p` is [_, false], both `None` and `Some` constructors appear in the first
181//! components of `P`. We will therefore try popping both constructors in turn: we
182//! compute U([[true, _]], [_, false]) for the `Some` constructor, and U([[false]],
183//! [false]) for the `None` constructor. The first case returns true, so we know that
184//! `p` is useful for `P`. Indeed, it matches `[Some(false), _]` that wasn't matched
185//! before.
186//!
187//! - If `p_1 == r_1 | r_2`, then the usefulness depends on each `r_i` separately:
188//! `U(P, p) := U(P, (r_1, p_2, .., p_n))
189//! || U(P, (r_2, p_2, .., p_n))`
190use std::sync::Arc;
191
192use smallvec::{smallvec, SmallVec};
193
194use crate::{
195 db::HirDatabase,
196 expr::{Body, Expr, Literal, Pat, PatId},
197 InferenceResult,
198};
199use hir_def::{adt::VariantData, EnumVariantId, VariantId};
200
201#[derive(Debug, Clone, Copy)]
202/// Either a pattern from the source code being analyzed, represented as
203/// as `PatId`, or a `Wild` pattern which is created as an intermediate
204/// step in the match checking algorithm and thus is not backed by a
205/// real `PatId`.
206///
207/// Note that it is totally valid for the `PatId` variant to contain
208/// a `PatId` which resolves to a `Wild` pattern, if that wild pattern
209/// exists in the source code being analyzed.
210enum PatIdOrWild {
211 PatId(PatId),
212 Wild,
213}
214
215impl PatIdOrWild {
216 fn as_pat(self, cx: &MatchCheckCtx) -> Pat {
217 match self {
218 PatIdOrWild::PatId(id) => cx.body.pats[id].clone(),
219 PatIdOrWild::Wild => Pat::Wild,
220 }
221 }
222
223 fn as_id(self) -> Option<PatId> {
224 match self {
225 PatIdOrWild::PatId(id) => Some(id),
226 PatIdOrWild::Wild => None,
227 }
228 }
229}
230
231impl From<PatId> for PatIdOrWild {
232 fn from(pat_id: PatId) -> Self {
233 Self::PatId(pat_id)
234 }
235}
236
237#[derive(Debug, Clone, Copy, PartialEq)]
238pub struct MatchCheckNotImplemented;
239
240/// The return type of `is_useful` is either an indication of usefulness
241/// of the match arm, or an error in the case the match statement
242/// is made up of types for which exhaustiveness checking is currently
243/// not completely implemented.
244///
245/// The `std::result::Result` type is used here rather than a custom enum
246/// to allow the use of `?`.
247pub type MatchCheckResult<T> = Result<T, MatchCheckNotImplemented>;
248
249#[derive(Debug)]
250/// A row in a Matrix.
251///
252/// This type is modeled from the struct of the same name in `rustc`.
253pub(crate) struct PatStack(PatStackInner);
254type PatStackInner = SmallVec<[PatIdOrWild; 2]>;
255
256impl PatStack {
257 pub(crate) fn from_pattern(pat_id: PatId) -> PatStack {
258 Self(smallvec!(pat_id.into()))
259 }
260
261 pub(crate) fn from_wild() -> PatStack {
262 Self(smallvec!(PatIdOrWild::Wild))
263 }
264
265 fn from_slice(slice: &[PatIdOrWild]) -> PatStack {
266 Self(SmallVec::from_slice(slice))
267 }
268
269 fn from_vec(v: PatStackInner) -> PatStack {
270 Self(v)
271 }
272
273 fn is_empty(&self) -> bool {
274 self.0.is_empty()
275 }
276
277 fn head(&self) -> PatIdOrWild {
278 self.0[0]
279 }
280
281 fn get_head(&self) -> Option<PatIdOrWild> {
282 self.0.first().copied()
283 }
284
285 fn to_tail(&self) -> PatStack {
286 Self::from_slice(&self.0[1..])
287 }
288
289 fn replace_head_with(&self, pat_ids: &[PatId]) -> PatStack {
290 let mut patterns: PatStackInner = smallvec![];
291 for pat in pat_ids {
292 patterns.push((*pat).into());
293 }
294 for pat in &self.0[1..] {
295 patterns.push(*pat);
296 }
297 PatStack::from_vec(patterns)
298 }
299
300 /// Computes `D(self)`.
301 ///
302 /// See the module docs and the associated documentation in rustc for details.
303 fn specialize_wildcard(&self, cx: &MatchCheckCtx) -> Option<PatStack> {
304 if matches!(self.head().as_pat(cx), Pat::Wild) {
305 Some(self.to_tail())
306 } else {
307 None
308 }
309 }
310
311 /// Computes `S(constructor, self)`.
312 ///
313 /// See the module docs and the associated documentation in rustc for details.
314 fn specialize_constructor(
315 &self,
316 cx: &MatchCheckCtx,
317 constructor: &Constructor,
318 ) -> MatchCheckResult<Option<PatStack>> {
319 let result = match (self.head().as_pat(cx), constructor) {
320 (Pat::Tuple(ref pat_ids), Constructor::Tuple { arity }) => {
321 debug_assert_eq!(
322 pat_ids.len(),
323 *arity,
324 "we type check before calling this code, so we should never hit this case",
325 );
326
327 Some(self.replace_head_with(pat_ids))
328 }
329 (Pat::Lit(lit_expr), Constructor::Bool(constructor_val)) => {
330 match cx.body.exprs[lit_expr] {
331 Expr::Literal(Literal::Bool(pat_val)) if *constructor_val == pat_val => {
332 Some(self.to_tail())
333 }
334 // it was a bool but the value doesn't match
335 Expr::Literal(Literal::Bool(_)) => None,
336 // perhaps this is actually unreachable given we have
337 // already checked that these match arms have the appropriate type?
338 _ => return Err(MatchCheckNotImplemented),
339 }
340 }
341 (Pat::Wild, constructor) => Some(self.expand_wildcard(cx, constructor)?),
342 (Pat::Path(_), Constructor::Enum(constructor)) => {
343 // enums with no associated data become `Pat::Path`
344 let pat_id = self.head().as_id().expect("we know this isn't a wild");
345 if !enum_variant_matches(cx, pat_id, *constructor) {
346 None
347 } else {
348 Some(self.to_tail())
349 }
350 }
351 (Pat::TupleStruct { args: ref pat_ids, .. }, Constructor::Enum(constructor)) => {
352 let pat_id = self.head().as_id().expect("we know this isn't a wild");
353 if !enum_variant_matches(cx, pat_id, *constructor) {
354 None
355 } else {
356 Some(self.replace_head_with(pat_ids))
357 }
358 }
359 (Pat::Or(_), _) => return Err(MatchCheckNotImplemented),
360 (_, _) => return Err(MatchCheckNotImplemented),
361 };
362
363 Ok(result)
364 }
365
366 /// A special case of `specialize_constructor` where the head of the pattern stack
367 /// is a Wild pattern.
368 ///
369 /// Replaces the Wild pattern at the head of the pattern stack with N Wild patterns
370 /// (N >= 0), where N is the arity of the given constructor.
371 fn expand_wildcard(
372 &self,
373 cx: &MatchCheckCtx,
374 constructor: &Constructor,
375 ) -> MatchCheckResult<PatStack> {
376 assert_eq!(
377 Pat::Wild,
378 self.head().as_pat(cx),
379 "expand_wildcard must only be called on PatStack with wild at head",
380 );
381
382 let mut patterns: PatStackInner = smallvec![];
383
384 for _ in 0..constructor.arity(cx)? {
385 patterns.push(PatIdOrWild::Wild);
386 }
387
388 for pat in &self.0[1..] {
389 patterns.push(*pat);
390 }
391
392 Ok(PatStack::from_vec(patterns))
393 }
394}
395
396#[derive(Debug)]
397/// A collection of PatStack.
398///
399/// This type is modeled from the struct of the same name in `rustc`.
400pub(crate) struct Matrix(Vec<PatStack>);
401
402impl Matrix {
403 pub(crate) fn empty() -> Self {
404 Self(vec![])
405 }
406
407 pub(crate) fn push(&mut self, cx: &MatchCheckCtx, row: PatStack) {
408 if let Some(Pat::Or(pat_ids)) = row.get_head().map(|pat_id| pat_id.as_pat(cx)) {
409 // Or patterns are expanded here
410 for pat_id in pat_ids {
411 self.0.push(PatStack::from_pattern(pat_id));
412 }
413 } else {
414 self.0.push(row);
415 }
416 }
417
418 fn is_empty(&self) -> bool {
419 self.0.is_empty()
420 }
421
422 fn heads(&self) -> Vec<PatIdOrWild> {
423 self.0.iter().map(|p| p.head()).collect()
424 }
425
426 /// Computes `D(self)` for each contained PatStack.
427 ///
428 /// See the module docs and the associated documentation in rustc for details.
429 fn specialize_wildcard(&self, cx: &MatchCheckCtx) -> Self {
430 Self::collect(cx, self.0.iter().filter_map(|r| r.specialize_wildcard(cx)))
431 }
432
433 /// Computes `S(constructor, self)` for each contained PatStack.
434 ///
435 /// See the module docs and the associated documentation in rustc for details.
436 fn specialize_constructor(
437 &self,
438 cx: &MatchCheckCtx,
439 constructor: &Constructor,
440 ) -> MatchCheckResult<Self> {
441 let mut new_matrix = Matrix::empty();
442 for pat in &self.0 {
443 if let Some(pat) = pat.specialize_constructor(cx, constructor)? {
444 new_matrix.push(cx, pat);
445 }
446 }
447
448 Ok(new_matrix)
449 }
450
451 fn collect<T: IntoIterator<Item = PatStack>>(cx: &MatchCheckCtx, iter: T) -> Self {
452 let mut matrix = Matrix::empty();
453
454 for pat in iter {
455 // using push ensures we expand or-patterns
456 matrix.push(cx, pat);
457 }
458
459 matrix
460 }
461}
462
463#[derive(Clone, Debug, PartialEq)]
464/// An indication of the usefulness of a given match arm, where
465/// usefulness is defined as matching some patterns which were
466/// not matched by an prior match arms.
467///
468/// We may eventually need an `Unknown` variant here.
469pub enum Usefulness {
470 Useful,
471 NotUseful,
472}
473
474pub struct MatchCheckCtx<'a> {
475 pub body: Arc<Body>,
476 pub infer: Arc<InferenceResult>,
477 pub db: &'a dyn HirDatabase,
478}
479
480/// Given a set of patterns `matrix`, and pattern to consider `v`, determines
481/// whether `v` is useful. A pattern is useful if it covers cases which were
482/// not previously covered.
483///
484/// When calling this function externally (that is, not the recursive calls) it
485/// expected that you have already type checked the match arms. All patterns in
486/// matrix should be the same type as v, as well as they should all be the same
487/// type as the match expression.
488pub(crate) fn is_useful(
489 cx: &MatchCheckCtx,
490 matrix: &Matrix,
491 v: &PatStack,
492) -> MatchCheckResult<Usefulness> {
493 if v.is_empty() {
494 let result = if matrix.is_empty() { Usefulness::Useful } else { Usefulness::NotUseful };
495
496 return Ok(result);
497 }
498
499 if let Pat::Or(pat_ids) = v.head().as_pat(cx) {
500 let mut found_unimplemented = false;
501 let any_useful = pat_ids.iter().any(|&pat_id| {
502 let v = PatStack::from_pattern(pat_id);
503
504 match is_useful(cx, matrix, &v) {
505 Ok(Usefulness::Useful) => true,
506 Ok(Usefulness::NotUseful) => false,
507 _ => {
508 found_unimplemented = true;
509 false
510 }
511 }
512 });
513
514 return if any_useful {
515 Ok(Usefulness::Useful)
516 } else if found_unimplemented {
517 Err(MatchCheckNotImplemented)
518 } else {
519 Ok(Usefulness::NotUseful)
520 };
521 }
522
523 if let Some(constructor) = pat_constructor(cx, v.head())? {
524 let matrix = matrix.specialize_constructor(&cx, &constructor)?;
525 let v = v
526 .specialize_constructor(&cx, &constructor)?
527 .expect("we know this can't fail because we get the constructor from `v.head()` above");
528
529 is_useful(&cx, &matrix, &v)
530 } else {
531 // expanding wildcard
532 let mut used_constructors: Vec<Constructor> = vec![];
533 for pat in matrix.heads() {
534 if let Some(constructor) = pat_constructor(cx, pat)? {
535 used_constructors.push(constructor);
536 }
537 }
538
539 // We assume here that the first constructor is the "correct" type. Since we
540 // only care about the "type" of the constructor (i.e. if it is a bool we
541 // don't care about the value), this assumption should be valid as long as
542 // the match statement is well formed. We currently uphold this invariant by
543 // filtering match arms before calling `is_useful`, only passing in match arms
544 // whose type matches the type of the match expression.
545 match &used_constructors.first() {
546 Some(constructor) if all_constructors_covered(&cx, constructor, &used_constructors) => {
547 // If all constructors are covered, then we need to consider whether
548 // any values are covered by this wildcard.
549 //
550 // For example, with matrix '[[Some(true)], [None]]', all
551 // constructors are covered (`Some`/`None`), so we need
552 // to perform specialization to see that our wildcard will cover
553 // the `Some(false)` case.
554 //
555 // Here we create a constructor for each variant and then check
556 // usefulness after specializing for that constructor.
557 let mut found_unimplemented = false;
558 for constructor in constructor.all_constructors(cx) {
559 let matrix = matrix.specialize_constructor(&cx, &constructor)?;
560 let v = v.expand_wildcard(&cx, &constructor)?;
561
562 match is_useful(&cx, &matrix, &v) {
563 Ok(Usefulness::Useful) => return Ok(Usefulness::Useful),
564 Ok(Usefulness::NotUseful) => continue,
565 _ => found_unimplemented = true,
566 };
567 }
568
569 if found_unimplemented {
570 Err(MatchCheckNotImplemented)
571 } else {
572 Ok(Usefulness::NotUseful)
573 }
574 }
575 _ => {
576 // Either not all constructors are covered, or the only other arms
577 // are wildcards. Either way, this pattern is useful if it is useful
578 // when compared to those arms with wildcards.
579 let matrix = matrix.specialize_wildcard(&cx);
580 let v = v.to_tail();
581
582 is_useful(&cx, &matrix, &v)
583 }
584 }
585 }
586}
587
588#[derive(Debug, Clone, Copy)]
589/// Similar to TypeCtor, but includes additional information about the specific
590/// value being instantiated. For example, TypeCtor::Bool doesn't contain the
591/// boolean value.
592enum Constructor {
593 Bool(bool),
594 Tuple { arity: usize },
595 Enum(EnumVariantId),
596}
597
598impl Constructor {
599 fn arity(&self, cx: &MatchCheckCtx) -> MatchCheckResult<usize> {
600 let arity = match self {
601 Constructor::Bool(_) => 0,
602 Constructor::Tuple { arity } => *arity,
603 Constructor::Enum(e) => {
604 match cx.db.enum_data(e.parent).variants[e.local_id].variant_data.as_ref() {
605 VariantData::Tuple(struct_field_data) => struct_field_data.len(),
606 VariantData::Unit => 0,
607 _ => return Err(MatchCheckNotImplemented),
608 }
609 }
610 };
611
612 Ok(arity)
613 }
614
615 fn all_constructors(&self, cx: &MatchCheckCtx) -> Vec<Constructor> {
616 match self {
617 Constructor::Bool(_) => vec![Constructor::Bool(true), Constructor::Bool(false)],
618 Constructor::Tuple { .. } => vec![*self],
619 Constructor::Enum(e) => cx
620 .db
621 .enum_data(e.parent)
622 .variants
623 .iter()
624 .map(|(local_id, _)| {
625 Constructor::Enum(EnumVariantId { parent: e.parent, local_id })
626 })
627 .collect(),
628 }
629 }
630}
631
632/// Returns the constructor for the given pattern. Should only return None
633/// in the case of a Wild pattern.
634fn pat_constructor(cx: &MatchCheckCtx, pat: PatIdOrWild) -> MatchCheckResult<Option<Constructor>> {
635 let res = match pat.as_pat(cx) {
636 Pat::Wild => None,
637 Pat::Tuple(pats) => Some(Constructor::Tuple { arity: pats.len() }),
638 Pat::Lit(lit_expr) => match cx.body.exprs[lit_expr] {
639 Expr::Literal(Literal::Bool(val)) => Some(Constructor::Bool(val)),
640 _ => return Err(MatchCheckNotImplemented),
641 },
642 Pat::TupleStruct { .. } | Pat::Path(_) => {
643 let pat_id = pat.as_id().expect("we already know this pattern is not a wild");
644 let variant_id =
645 cx.infer.variant_resolution_for_pat(pat_id).ok_or(MatchCheckNotImplemented)?;
646 match variant_id {
647 VariantId::EnumVariantId(enum_variant_id) => {
648 Some(Constructor::Enum(enum_variant_id))
649 }
650 _ => return Err(MatchCheckNotImplemented),
651 }
652 }
653 _ => return Err(MatchCheckNotImplemented),
654 };
655
656 Ok(res)
657}
658
659fn all_constructors_covered(
660 cx: &MatchCheckCtx,
661 constructor: &Constructor,
662 used_constructors: &[Constructor],
663) -> bool {
664 match constructor {
665 Constructor::Tuple { arity } => {
666 used_constructors.iter().any(|constructor| match constructor {
667 Constructor::Tuple { arity: used_arity } => arity == used_arity,
668 _ => false,
669 })
670 }
671 Constructor::Bool(_) => {
672 if used_constructors.is_empty() {
673 return false;
674 }
675
676 let covers_true =
677 used_constructors.iter().any(|c| matches!(c, Constructor::Bool(true)));
678 let covers_false =
679 used_constructors.iter().any(|c| matches!(c, Constructor::Bool(false)));
680
681 covers_true && covers_false
682 }
683 Constructor::Enum(e) => cx.db.enum_data(e.parent).variants.iter().all(|(id, _)| {
684 for constructor in used_constructors {
685 if let Constructor::Enum(e) = constructor {
686 if id == e.local_id {
687 return true;
688 }
689 }
690 }
691
692 false
693 }),
694 }
695}
696
697fn enum_variant_matches(cx: &MatchCheckCtx, pat_id: PatId, enum_variant_id: EnumVariantId) -> bool {
698 Some(enum_variant_id.into()) == cx.infer.variant_resolution_for_pat(pat_id)
699}
700
701#[cfg(test)]
702mod tests {
703 pub(super) use insta::assert_snapshot;
704 pub(super) use ra_db::fixture::WithFixture;
705
706 pub(super) use crate::test_db::TestDB;
707
708 pub(super) fn check_diagnostic_message(content: &str) -> String {
709 TestDB::with_single_file(content).0.diagnostics().0
710 }
711
712 pub(super) fn check_diagnostic(content: &str) {
713 let diagnostic_count = TestDB::with_single_file(content).0.diagnostics().1;
714
715 assert_eq!(1, diagnostic_count, "no diagnostic reported");
716 }
717
718 pub(super) fn check_no_diagnostic(content: &str) {
719 let diagnostic_count = TestDB::with_single_file(content).0.diagnostics().1;
720
721 assert_eq!(0, diagnostic_count, "expected no diagnostic, found one");
722 }
723
724 #[test]
725 fn empty_tuple_no_arms_diagnostic_message() {
726 let content = r"
727 fn test_fn() {
728 match () {
729 }
730 }
731 ";
732
733 assert_snapshot!(
734 check_diagnostic_message(content),
735 @"\"()\": Missing match arm\n"
736 );
737 }
738
739 #[test]
740 fn empty_tuple_no_arms() {
741 let content = r"
742 fn test_fn() {
743 match () {
744 }
745 }
746 ";
747
748 check_diagnostic(content);
749 }
750
751 #[test]
752 fn empty_tuple_wild() {
753 let content = r"
754 fn test_fn() {
755 match () {
756 _ => {}
757 }
758 }
759 ";
760
761 check_no_diagnostic(content);
762 }
763
764 #[test]
765 fn empty_tuple_no_diagnostic() {
766 let content = r"
767 fn test_fn() {
768 match () {
769 () => {}
770 }
771 }
772 ";
773
774 check_no_diagnostic(content);
775 }
776
777 #[test]
778 fn tuple_of_empty_tuple_no_arms() {
779 let content = r"
780 fn test_fn() {
781 match (()) {
782 }
783 }
784 ";
785
786 check_diagnostic(content);
787 }
788
789 #[test]
790 fn tuple_of_empty_tuple_no_diagnostic() {
791 let content = r"
792 fn test_fn() {
793 match (()) {
794 (()) => {}
795 }
796 }
797 ";
798
799 check_no_diagnostic(content);
800 }
801
802 #[test]
803 fn tuple_of_two_empty_tuple_no_arms() {
804 let content = r"
805 fn test_fn() {
806 match ((), ()) {
807 }
808 }
809 ";
810
811 check_diagnostic(content);
812 }
813
814 #[test]
815 fn tuple_of_two_empty_tuple_no_diagnostic() {
816 let content = r"
817 fn test_fn() {
818 match ((), ()) {
819 ((), ()) => {}
820 }
821 }
822 ";
823
824 check_no_diagnostic(content);
825 }
826
827 #[test]
828 fn bool_no_arms() {
829 let content = r"
830 fn test_fn() {
831 match false {
832 }
833 }
834 ";
835
836 check_diagnostic(content);
837 }
838
839 #[test]
840 fn bool_missing_arm() {
841 let content = r"
842 fn test_fn() {
843 match false {
844 true => {}
845 }
846 }
847 ";
848
849 check_diagnostic(content);
850 }
851
852 #[test]
853 fn bool_no_diagnostic() {
854 let content = r"
855 fn test_fn() {
856 match false {
857 true => {}
858 false => {}
859 }
860 }
861 ";
862
863 check_no_diagnostic(content);
864 }
865
866 #[test]
867 fn tuple_of_bools_no_arms() {
868 let content = r"
869 fn test_fn() {
870 match (false, true) {
871 }
872 }
873 ";
874
875 check_diagnostic(content);
876 }
877
878 #[test]
879 fn tuple_of_bools_missing_arms() {
880 let content = r"
881 fn test_fn() {
882 match (false, true) {
883 (true, true) => {},
884 }
885 }
886 ";
887
888 check_diagnostic(content);
889 }
890
891 #[test]
892 fn tuple_of_bools_missing_arm() {
893 let content = r"
894 fn test_fn() {
895 match (false, true) {
896 (false, true) => {},
897 (false, false) => {},
898 (true, false) => {},
899 }
900 }
901 ";
902
903 check_diagnostic(content);
904 }
905
906 #[test]
907 fn tuple_of_bools_with_wilds() {
908 let content = r"
909 fn test_fn() {
910 match (false, true) {
911 (false, _) => {},
912 (true, false) => {},
913 (_, true) => {},
914 }
915 }
916 ";
917
918 check_no_diagnostic(content);
919 }
920
921 #[test]
922 fn tuple_of_bools_no_diagnostic() {
923 let content = r"
924 fn test_fn() {
925 match (false, true) {
926 (true, true) => {},
927 (true, false) => {},
928 (false, true) => {},
929 (false, false) => {},
930 }
931 }
932 ";
933
934 check_no_diagnostic(content);
935 }
936
937 #[test]
938 fn tuple_of_bools_binding_missing_arms() {
939 let content = r"
940 fn test_fn() {
941 match (false, true) {
942 (true, _x) => {},
943 }
944 }
945 ";
946
947 check_diagnostic(content);
948 }
949
950 #[test]
951 fn tuple_of_bools_binding_no_diagnostic() {
952 let content = r"
953 fn test_fn() {
954 match (false, true) {
955 (true, _x) => {},
956 (false, true) => {},
957 (false, false) => {},
958 }
959 }
960 ";
961
962 check_no_diagnostic(content);
963 }
964
965 #[test]
966 fn tuple_of_tuple_and_bools_no_arms() {
967 let content = r"
968 fn test_fn() {
969 match (false, ((), false)) {
970 }
971 }
972 ";
973
974 check_diagnostic(content);
975 }
976
977 #[test]
978 fn tuple_of_tuple_and_bools_missing_arms() {
979 let content = r"
980 fn test_fn() {
981 match (false, ((), false)) {
982 (true, ((), true)) => {},
983 }
984 }
985 ";
986
987 check_diagnostic(content);
988 }
989
990 #[test]
991 fn tuple_of_tuple_and_bools_no_diagnostic() {
992 let content = r"
993 fn test_fn() {
994 match (false, ((), false)) {
995 (true, ((), true)) => {},
996 (true, ((), false)) => {},
997 (false, ((), true)) => {},
998 (false, ((), false)) => {},
999 }
1000 }
1001 ";
1002
1003 check_no_diagnostic(content);
1004 }
1005
1006 #[test]
1007 fn tuple_of_tuple_and_bools_wildcard_missing_arms() {
1008 let content = r"
1009 fn test_fn() {
1010 match (false, ((), false)) {
1011 (true, _) => {},
1012 }
1013 }
1014 ";
1015
1016 check_diagnostic(content);
1017 }
1018
1019 #[test]
1020 fn tuple_of_tuple_and_bools_wildcard_no_diagnostic() {
1021 let content = r"
1022 fn test_fn() {
1023 match (false, ((), false)) {
1024 (true, ((), true)) => {},
1025 (true, ((), false)) => {},
1026 (false, _) => {},
1027 }
1028 }
1029 ";
1030
1031 check_no_diagnostic(content);
1032 }
1033
1034 #[test]
1035 fn enum_no_arms() {
1036 let content = r"
1037 enum Either {
1038 A,
1039 B,
1040 }
1041 fn test_fn() {
1042 match Either::A {
1043 }
1044 }
1045 ";
1046
1047 check_diagnostic(content);
1048 }
1049
1050 #[test]
1051 fn enum_missing_arms() {
1052 let content = r"
1053 enum Either {
1054 A,
1055 B,
1056 }
1057 fn test_fn() {
1058 match Either::B {
1059 Either::A => {},
1060 }
1061 }
1062 ";
1063
1064 check_diagnostic(content);
1065 }
1066
1067 #[test]
1068 fn enum_no_diagnostic() {
1069 let content = r"
1070 enum Either {
1071 A,
1072 B,
1073 }
1074 fn test_fn() {
1075 match Either::B {
1076 Either::A => {},
1077 Either::B => {},
1078 }
1079 }
1080 ";
1081
1082 check_no_diagnostic(content);
1083 }
1084
1085 #[test]
1086 fn enum_ref_missing_arms() {
1087 let content = r"
1088 enum Either {
1089 A,
1090 B,
1091 }
1092 fn test_fn() {
1093 match &Either::B {
1094 Either::A => {},
1095 }
1096 }
1097 ";
1098
1099 check_diagnostic(content);
1100 }
1101
1102 #[test]
1103 fn enum_ref_no_diagnostic() {
1104 let content = r"
1105 enum Either {
1106 A,
1107 B,
1108 }
1109 fn test_fn() {
1110 match &Either::B {
1111 Either::A => {},
1112 Either::B => {},
1113 }
1114 }
1115 ";
1116
1117 check_no_diagnostic(content);
1118 }
1119
1120 #[test]
1121 fn enum_containing_bool_no_arms() {
1122 let content = r"
1123 enum Either {
1124 A(bool),
1125 B,
1126 }
1127 fn test_fn() {
1128 match Either::B {
1129 }
1130 }
1131 ";
1132
1133 check_diagnostic(content);
1134 }
1135
1136 #[test]
1137 fn enum_containing_bool_missing_arms() {
1138 let content = r"
1139 enum Either {
1140 A(bool),
1141 B,
1142 }
1143 fn test_fn() {
1144 match Either::B {
1145 Either::A(true) => (),
1146 Either::B => (),
1147 }
1148 }
1149 ";
1150
1151 check_diagnostic(content);
1152 }
1153
1154 #[test]
1155 fn enum_containing_bool_no_diagnostic() {
1156 let content = r"
1157 enum Either {
1158 A(bool),
1159 B,
1160 }
1161 fn test_fn() {
1162 match Either::B {
1163 Either::A(true) => (),
1164 Either::A(false) => (),
1165 Either::B => (),
1166 }
1167 }
1168 ";
1169
1170 check_no_diagnostic(content);
1171 }
1172
1173 #[test]
1174 fn enum_containing_bool_with_wild_no_diagnostic() {
1175 let content = r"
1176 enum Either {
1177 A(bool),
1178 B,
1179 }
1180 fn test_fn() {
1181 match Either::B {
1182 Either::B => (),
1183 _ => (),
1184 }
1185 }
1186 ";
1187
1188 check_no_diagnostic(content);
1189 }
1190
1191 #[test]
1192 fn enum_containing_bool_with_wild_2_no_diagnostic() {
1193 let content = r"
1194 enum Either {
1195 A(bool),
1196 B,
1197 }
1198 fn test_fn() {
1199 match Either::B {
1200 Either::A(_) => (),
1201 Either::B => (),
1202 }
1203 }
1204 ";
1205
1206 check_no_diagnostic(content);
1207 }
1208
1209 #[test]
1210 fn enum_different_sizes_missing_arms() {
1211 let content = r"
1212 enum Either {
1213 A(bool),
1214 B(bool, bool),
1215 }
1216 fn test_fn() {
1217 match Either::A(false) {
1218 Either::A(_) => (),
1219 Either::B(false, _) => (),
1220 }
1221 }
1222 ";
1223
1224 check_diagnostic(content);
1225 }
1226
1227 #[test]
1228 fn enum_different_sizes_no_diagnostic() {
1229 let content = r"
1230 enum Either {
1231 A(bool),
1232 B(bool, bool),
1233 }
1234 fn test_fn() {
1235 match Either::A(false) {
1236 Either::A(_) => (),
1237 Either::B(true, _) => (),
1238 Either::B(false, _) => (),
1239 }
1240 }
1241 ";
1242
1243 check_no_diagnostic(content);
1244 }
1245
1246 #[test]
1247 fn or_no_diagnostic() {
1248 let content = r"
1249 enum Either {
1250 A(bool),
1251 B(bool, bool),
1252 }
1253 fn test_fn() {
1254 match Either::A(false) {
1255 Either::A(true) | Either::A(false) => (),
1256 Either::B(true, _) => (),
1257 Either::B(false, _) => (),
1258 }
1259 }
1260 ";
1261
1262 check_no_diagnostic(content);
1263 }
1264
1265 #[test]
1266 fn tuple_of_enum_no_diagnostic() {
1267 let content = r"
1268 enum Either {
1269 A(bool),
1270 B(bool, bool),
1271 }
1272 enum Either2 {
1273 C,
1274 D,
1275 }
1276 fn test_fn() {
1277 match (Either::A(false), Either2::C) {
1278 (Either::A(true), _) | (Either::A(false), _) => (),
1279 (Either::B(true, _), Either2::C) => (),
1280 (Either::B(false, _), Either2::C) => (),
1281 (Either::B(_, _), Either2::D) => (),
1282 }
1283 }
1284 ";
1285
1286 check_no_diagnostic(content);
1287 }
1288
1289 #[test]
1290 fn mismatched_types() {
1291 let content = r"
1292 enum Either {
1293 A,
1294 B,
1295 }
1296 enum Either2 {
1297 C,
1298 D,
1299 }
1300 fn test_fn() {
1301 match Either::A {
1302 Either2::C => (),
1303 Either2::D => (),
1304 }
1305 }
1306 ";
1307
1308 // Match arms with the incorrect type are filtered out.
1309 check_diagnostic(content);
1310 }
1311
1312 #[test]
1313 fn mismatched_types_with_different_arity() {
1314 let content = r"
1315 fn test_fn() {
1316 match (true, false) {
1317 (true, false, true) => (),
1318 (true) => (),
1319 }
1320 }
1321 ";
1322
1323 // Match arms with the incorrect type are filtered out.
1324 check_diagnostic(content);
1325 }
1326
1327 #[test]
1328 fn enum_not_in_scope() {
1329 let content = r"
1330 fn test_fn() {
1331 match Foo::Bar {
1332 Foo::Baz => (),
1333 }
1334 }
1335 ";
1336
1337 // The enum is not in scope so we don't perform exhaustiveness
1338 // checking, but we want to be sure we don't panic here (and
1339 // we don't create a diagnostic).
1340 check_no_diagnostic(content);
1341 }
1342}
1343
1344#[cfg(test)]
1345mod false_negatives {
1346 //! The implementation of match checking here is a work in progress. As we roll this out, we
1347 //! prefer false negatives to false positives (ideally there would be no false positives). This
1348 //! test module should document known false negatives. Eventually we will have a complete
1349 //! implementation of match checking and this module will be empty.
1350 //!
1351 //! The reasons for documenting known false negatives:
1352 //!
1353 //! 1. It acts as a backlog of work that can be done to improve the behavior of the system.
1354 //! 2. It ensures the code doesn't panic when handling these cases.
1355
1356 use super::tests::*;
1357
1358 #[test]
1359 fn integers() {
1360 let content = r"
1361 fn test_fn() {
1362 match 5 {
1363 10 => (),
1364 11..20 => (),
1365 }
1366 }
1367 ";
1368
1369 // This is a false negative.
1370 // We don't currently check integer exhaustiveness.
1371 check_no_diagnostic(content);
1372 }
1373
1374 #[test]
1375 fn enum_record() {
1376 let content = r"
1377 enum Either {
1378 A { foo: u32 },
1379 B,
1380 }
1381 fn test_fn() {
1382 match Either::B {
1383 Either::A { foo: 5 } => (),
1384 }
1385 }
1386 ";
1387
1388 // This is a false negative.
1389 // We don't currently handle enum record types.
1390 check_no_diagnostic(content);
1391 }
1392
1393 #[test]
1394 fn internal_or() {
1395 let content = r"
1396 fn test_fn() {
1397 enum Either {
1398 A(bool),
1399 B,
1400 }
1401 match Either::B {
1402 Either::A(true | false) => (),
1403 }
1404 }
1405 ";
1406
1407 // This is a false negative.
1408 // We do not currently handle patterns with internal `or`s.
1409 check_no_diagnostic(content);
1410 }
1411}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-13 08:11:28 +0100