aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty/src
diff options
context:
space:
mode:
authorDawer <[email protected]>2021-05-11 13:18:16 +0100
committerDawer <[email protected]>2021-05-31 20:23:09 +0100
commite84efc4a4656e54a4f08b99592d5d98ac5726449 (patch)
tree7f21f05a7eb6cbef32ca9c081e19f9f0c2392567 /crates/hir_ty/src
parent894b4c64ffdb280a38c1ea2e9be145ca308965fd (diff)
Replace the old match checking algorithm
Diffstat (limited to 'crates/hir_ty/src')
-rw-r--r--crates/hir_ty/src/diagnostics.rs2
-rw-r--r--crates/hir_ty/src/diagnostics/expr.rs119
-rw-r--r--crates/hir_ty/src/diagnostics/match_check.rs1077
-rw-r--r--crates/hir_ty/src/diagnostics/match_check/deconstruct_pat.rs (renamed from crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs)0
-rw-r--r--crates/hir_ty/src/diagnostics/match_check/pat_util.rs (renamed from crates/hir_ty/src/diagnostics/pattern/pat_util.rs)0
-rw-r--r--crates/hir_ty/src/diagnostics/match_check/usefulness.rs (renamed from crates/hir_ty/src/diagnostics/pattern/usefulness.rs)0
-rw-r--r--crates/hir_ty/src/diagnostics/pattern.rs1040
7 files changed, 311 insertions, 1927 deletions
diff --git a/crates/hir_ty/src/diagnostics.rs b/crates/hir_ty/src/diagnostics.rs
index 87a3594c5..283894704 100644
--- a/crates/hir_ty/src/diagnostics.rs
+++ b/crates/hir_ty/src/diagnostics.rs
@@ -1,8 +1,6 @@
1//! Type inference-based diagnostics. 1//! Type inference-based diagnostics.
2mod expr; 2mod expr;
3#[allow(unused)] //todo
4mod match_check; 3mod match_check;
5mod pattern;
6mod unsafe_check; 4mod unsafe_check;
7mod decl_check; 5mod decl_check;
8 6
diff --git a/crates/hir_ty/src/diagnostics/expr.rs b/crates/hir_ty/src/diagnostics/expr.rs
index b321004ac..c6015d236 100644
--- a/crates/hir_ty/src/diagnostics/expr.rs
+++ b/crates/hir_ty/src/diagnostics/expr.rs
@@ -4,7 +4,9 @@
4 4
5use std::{cell::RefCell, sync::Arc}; 5use std::{cell::RefCell, sync::Arc};
6 6
7use hir_def::{expr::Statement, path::path, resolver::HasResolver, AssocItemId, DefWithBodyId}; 7use hir_def::{
8 expr::Statement, path::path, resolver::HasResolver, AssocItemId, DefWithBodyId, HasModule,
9};
8use hir_expand::name; 10use hir_expand::name;
9use rustc_hash::FxHashSet; 11use rustc_hash::FxHashSet;
10use syntax::{ast, AstPtr}; 12use syntax::{ast, AstPtr};
@@ -12,7 +14,10 @@ use syntax::{ast, AstPtr};
12use crate::{ 14use crate::{
13 db::HirDatabase, 15 db::HirDatabase,
14 diagnostics::{ 16 diagnostics::{
15 match_check::{is_useful, MatchCheckCtx, Matrix, PatStack, Usefulness}, 17 match_check::{
18 self,
19 usefulness::{compute_match_usefulness, expand_pattern, MatchCheckCtx, PatternArena},
20 },
16 MismatchedArgCount, MissingFields, MissingMatchArms, MissingOkOrSomeInTailExpr, 21 MismatchedArgCount, MissingFields, MissingMatchArms, MissingOkOrSomeInTailExpr,
17 MissingPatFields, RemoveThisSemicolon, 22 MissingPatFields, RemoveThisSemicolon,
18 }, 23 },
@@ -26,13 +31,7 @@ pub(crate) use hir_def::{
26 LocalFieldId, VariantId, 31 LocalFieldId, VariantId,
27}; 32};
28 33
29use super::{ 34use super::ReplaceFilterMapNextWithFindMap;
30 pattern::{
31 self,
32 usefulness::{expand_pattern, PatternArena},
33 },
34 ReplaceFilterMapNextWithFindMap,
35};
36 35
37pub(super) struct ExprValidator<'a, 'b: 'a> { 36pub(super) struct ExprValidator<'a, 'b: 'a> {
38 owner: DefWithBodyId, 37 owner: DefWithBodyId,
@@ -68,7 +67,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
68 67
69 match expr { 68 match expr {
70 Expr::Match { expr, arms } => { 69 Expr::Match { expr, arms } => {
71 self.validate_match2(id, *expr, arms, db, self.infer.clone()); 70 self.validate_match(id, *expr, arms, db, self.infer.clone());
72 } 71 }
73 Expr::Call { .. } | Expr::MethodCall { .. } => { 72 Expr::Call { .. } | Expr::MethodCall { .. } => {
74 self.validate_call(db, id, expr); 73 self.validate_call(db, id, expr);
@@ -283,7 +282,6 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
283 } 282 }
284 } 283 }
285 284
286 #[allow(dead_code)]
287 fn validate_match( 285 fn validate_match(
288 &mut self, 286 &mut self,
289 id: ExprId, 287 id: ExprId,
@@ -301,90 +299,6 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
301 &infer.type_of_expr[match_expr] 299 &infer.type_of_expr[match_expr]
302 }; 300 };
303 301
304 let cx = MatchCheckCtx { match_expr, body, infer: infer.clone(), db };
305 let pats = arms.iter().map(|arm| arm.pat);
306
307 let mut seen = Matrix::empty();
308 for pat in pats {
309 if let Some(pat_ty) = infer.type_of_pat.get(pat) {
310 // We only include patterns whose type matches the type
311 // of the match expression. If we had a InvalidMatchArmPattern
312 // diagnostic or similar we could raise that in an else
313 // block here.
314 //
315 // When comparing the types, we also have to consider that rustc
316 // will automatically de-reference the match expression type if
317 // necessary.
318 //
319 // FIXME we should use the type checker for this.
320 if (pat_ty == match_expr_ty
321 || match_expr_ty
322 .as_reference()
323 .map(|(match_expr_ty, ..)| match_expr_ty == pat_ty)
324 .unwrap_or(false))
325 && types_of_subpatterns_do_match(pat, &cx.body, &infer)
326 {
327 // If we had a NotUsefulMatchArm diagnostic, we could
328 // check the usefulness of each pattern as we added it
329 // to the matrix here.
330 let v = PatStack::from_pattern(pat);
331 seen.push(&cx, v);
332 continue;
333 }
334 }
335
336 // If we can't resolve the type of a pattern, or the pattern type doesn't
337 // fit the match expression, we skip this diagnostic. Skipping the entire
338 // diagnostic rather than just not including this match arm is preferred
339 // to avoid the chance of false positives.
340 return;
341 }
342
343 match is_useful(&cx, &seen, &PatStack::from_wild()) {
344 Ok(Usefulness::Useful) => (),
345 // if a wildcard pattern is not useful, then all patterns are covered
346 Ok(Usefulness::NotUseful) => return,
347 // this path is for unimplemented checks, so we err on the side of not
348 // reporting any errors
349 _ => return,
350 }
351
352 if let Ok(source_ptr) = source_map.expr_syntax(id) {
353 let root = source_ptr.file_syntax(db.upcast());
354 if let ast::Expr::MatchExpr(match_expr) = &source_ptr.value.to_node(&root) {
355 if let (Some(match_expr), Some(arms)) =
356 (match_expr.expr(), match_expr.match_arm_list())
357 {
358 self.sink.push(MissingMatchArms {
359 file: source_ptr.file_id,
360 match_expr: AstPtr::new(&match_expr),
361 arms: AstPtr::new(&arms),
362 })
363 }
364 }
365 }
366 }
367
368 fn validate_match2(
369 &mut self,
370 id: ExprId,
371 match_expr: ExprId,
372 arms: &[MatchArm],
373 db: &dyn HirDatabase,
374 infer: Arc<InferenceResult>,
375 ) {
376 use crate::diagnostics::pattern::usefulness;
377 use hir_def::HasModule;
378
379 let (body, source_map): (Arc<Body>, Arc<BodySourceMap>) =
380 db.body_with_source_map(self.owner);
381
382 let match_expr_ty = if infer.type_of_expr[match_expr].is_unknown() {
383 return;
384 } else {
385 &infer.type_of_expr[match_expr]
386 };
387
388 let pattern_arena = RefCell::new(PatternArena::new()); 302 let pattern_arena = RefCell::new(PatternArena::new());
389 303
390 let mut m_arms = Vec::new(); 304 let mut m_arms = Vec::new();
@@ -401,16 +315,17 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
401 // necessary. 315 // necessary.
402 // 316 //
403 // FIXME we should use the type checker for this. 317 // FIXME we should use the type checker for this.
404 if pat_ty == match_expr_ty 318 if (pat_ty == match_expr_ty
405 || match_expr_ty 319 || match_expr_ty
406 .as_reference() 320 .as_reference()
407 .map(|(match_expr_ty, ..)| match_expr_ty == pat_ty) 321 .map(|(match_expr_ty, ..)| match_expr_ty == pat_ty)
408 .unwrap_or(false) 322 .unwrap_or(false))
323 && types_of_subpatterns_do_match(arm.pat, &body, &infer)
409 { 324 {
410 // If we had a NotUsefulMatchArm diagnostic, we could 325 // If we had a NotUsefulMatchArm diagnostic, we could
411 // check the usefulness of each pattern as we added it 326 // check the usefulness of each pattern as we added it
412 // to the matrix here. 327 // to the matrix here.
413 let m_arm = usefulness::MatchArm { 328 let m_arm = match_check::MatchArm {
414 pat: self.lower_pattern( 329 pat: self.lower_pattern(
415 arm.pat, 330 arm.pat,
416 &mut pattern_arena.borrow_mut(), 331 &mut pattern_arena.borrow_mut(),
@@ -434,14 +349,14 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
434 return; 349 return;
435 } 350 }
436 351
437 let cx = usefulness::MatchCheckCtx { 352 let cx = MatchCheckCtx {
438 module: self.owner.module(db.upcast()), 353 module: self.owner.module(db.upcast()),
439 match_expr, 354 match_expr,
440 infer: &infer, 355 infer: &infer,
441 db, 356 db,
442 pattern_arena: &pattern_arena, 357 pattern_arena: &pattern_arena,
443 }; 358 };
444 let report = usefulness::compute_match_usefulness(&cx, &m_arms); 359 let report = compute_match_usefulness(&cx, &m_arms);
445 360
446 // FIXME Report unreacheble arms 361 // FIXME Report unreacheble arms
447 // https://github.com/rust-lang/rust/blob/25c15cdbe/compiler/rustc_mir_build/src/thir/pattern/check_match.rs#L200-L201 362 // https://github.com/rust-lang/rust/blob/25c15cdbe/compiler/rustc_mir_build/src/thir/pattern/check_match.rs#L200-L201
@@ -473,8 +388,8 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
473 db: &dyn HirDatabase, 388 db: &dyn HirDatabase,
474 body: &Body, 389 body: &Body,
475 have_errors: &mut bool, 390 have_errors: &mut bool,
476 ) -> pattern::PatId { 391 ) -> match_check::PatId {
477 let mut patcx = pattern::PatCtxt::new(db, &self.infer, body); 392 let mut patcx = match_check::PatCtxt::new(db, &self.infer, body);
478 let pattern = patcx.lower_pattern(pat); 393 let pattern = patcx.lower_pattern(pat);
479 let pattern = pattern_arena.alloc(expand_pattern(pattern)); 394 let pattern = pattern_arena.alloc(expand_pattern(pattern));
480 if !patcx.errors.is_empty() { 395 if !patcx.errors.is_empty() {
diff --git a/crates/hir_ty/src/diagnostics/match_check.rs b/crates/hir_ty/src/diagnostics/match_check.rs
index 52e9a5b1b..aebadd391 100644
--- a/crates/hir_ty/src/diagnostics/match_check.rs
+++ b/crates/hir_ty/src/diagnostics/match_check.rs
@@ -1,864 +1,340 @@
1//! This module implements match statement exhaustiveness checking and usefulness checking 1//! Validation of matches.
2//! for match arms.
3//! 2//!
4//! It is modeled on the rustc module `librustc_mir_build::hair::pattern::_match`, which 3//! This module provides lowering from [hir_def::expr::Pat] to [self::Pat] and match
5//! contains very detailed documentation about the algorithms used here. I've duplicated 4//! checking algorithm.
6//! most of that documentation below.
7//! 5//!
8//! This file includes the logic for exhaustiveness and usefulness checking for 6//! It is modeled on the rustc module `rustc_mir_build::thir::pattern`.
9//! pattern-matching. Specifically, given a list of patterns for a type, we can 7
10//! tell whether: 8mod deconstruct_pat;
11//! - (a) the patterns cover every possible constructor for the type (exhaustiveness). 9mod pat_util;
12//! - (b) each pattern is necessary (usefulness). 10pub(crate) mod usefulness;
13//! 11
14//! The algorithm implemented here is a modified version of the one described in 12use hir_def::{body::Body, EnumVariantId, LocalFieldId, VariantId};
15//! <http://moscova.inria.fr/~maranget/papers/warn/index.html>.
16//! However, to save future implementors from reading the original paper, we
17//! summarize 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//! ```ignore
42//! // x: (Option<bool>, Result<()>)
43//! match x {
44//! (Some(true), _) => (),
45//! (None, Err(())) => (),
46//! (None, Err(_)) => (),
47//! }
48//! ```
49//!
50//! Here, the matrix `P` starts as:
51//!
52//! ```text
53//! [
54//! [(Some(true), _)],
55//! [(None, Err(()))],
56//! [(None, Err(_))],
57//! ]
58//! ```
59//!
60//! We can tell it's not exhaustive, because `U(P, _)` is true (we're not covering
61//! `[(Some(false), _)]`, for instance). In addition, row 3 is not useful, because
62//! all the values it covers are already covered by row 2.
63//!
64//! A list of patterns can be thought of as a stack, because we are mainly interested in the top of
65//! the stack at any given point, and we can pop or apply constructors to get new pattern-stacks.
66//! To match the paper, the top of the stack is at the beginning / on the left.
67//!
68//! There are two important operations on pattern-stacks necessary to understand the algorithm:
69//!
70//! 1. We can pop a given constructor off the top of a stack. This operation is called
71//! `specialize`, and is denoted `S(c, p)` where `c` is a constructor (like `Some` or
72//! `None`) and `p` a pattern-stack.
73//! If the pattern on top of the stack can cover `c`, this removes the constructor and
74//! pushes its arguments onto the stack. It also expands OR-patterns into distinct patterns.
75//! Otherwise the pattern-stack is discarded.
76//! This essentially filters those pattern-stacks whose top covers the constructor `c` and
77//! discards the others.
78//!
79//! For example, the first pattern above initially gives a stack `[(Some(true), _)]`. If we
80//! pop the tuple constructor, we are left with `[Some(true), _]`, and if we then pop the
81//! `Some` constructor we get `[true, _]`. If we had popped `None` instead, we would get
82//! nothing back.
83//!
84//! This returns zero or more new pattern-stacks, as follows. We look at the pattern `p_1`
85//! on top of the stack, and we have four cases:
86//!
87//! * 1.1. `p_1 = c(r_1, .., r_a)`, i.e. the top of the stack has constructor `c`. We push onto
88//! the stack the arguments of this constructor, and return the result:
89//!
90//! r_1, .., r_a, p_2, .., p_n
91//!
92//! * 1.2. `p_1 = c'(r_1, .., r_a')` where `c ≠ c'`. We discard the current stack and return
93//! nothing.
94//! * 1.3. `p_1 = _`. We push onto the stack as many wildcards as the constructor `c` has
95//! arguments (its arity), and return the resulting stack:
96//!
97//! _, .., _, p_2, .., p_n
98//!
99//! * 1.4. `p_1 = r_1 | r_2`. We expand the OR-pattern and then recurse on each resulting stack:
100//!
101//! S(c, (r_1, p_2, .., p_n))
102//! S(c, (r_2, p_2, .., p_n))
103//!
104//! 2. We can pop a wildcard off the top of the stack. This is called `D(p)`, where `p` is
105//! a pattern-stack.
106//! This is used when we know there are missing constructor cases, but there might be
107//! existing wildcard patterns, so to check the usefulness of the matrix, we have to check
108//! all its *other* components.
109//!
110//! It is computed as follows. We look at the pattern `p_1` on top of the stack,
111//! and we have three cases:
112//! * 1.1. `p_1 = c(r_1, .., r_a)`. We discard the current stack and return nothing.
113//! * 1.2. `p_1 = _`. We return the rest of the stack:
114//!
115//! p_2, .., p_n
116//!
117//! * 1.3. `p_1 = r_1 | r_2`. We expand the OR-pattern and then recurse on each resulting stack:
118//!
119//! D((r_1, p_2, .., p_n))
120//! D((r_2, p_2, .., p_n))
121//!
122//! Note that the OR-patterns are not always used directly in Rust, but are used to derive the
123//! exhaustive integer matching rules, so they're written here for posterity.
124//!
125//! Both those operations extend straightforwardly to a list or pattern-stacks, i.e. a matrix, by
126//! working row-by-row. Popping a constructor ends up keeping only the matrix rows that start with
127//! the given constructor, and popping a wildcard keeps those rows that start with a wildcard.
128//!
129//!
130//! The algorithm for computing `U`
131//! -------------------------------
132//! The algorithm is inductive (on the number of columns: i.e., components of tuple patterns).
133//! That means we're going to check the components from left-to-right, so the algorithm
134//! operates principally on the first component of the matrix and new pattern-stack `p`.
135//! This algorithm is realized in the `is_useful` function.
136//!
137//! Base case (`n = 0`, i.e., an empty tuple pattern):
138//! - If `P` already contains an empty pattern (i.e., if the number of patterns `m > 0`), then
139//! `U(P, p)` is false.
140//! - Otherwise, `P` must be empty, so `U(P, p)` is true.
141//!
142//! Inductive step (`n > 0`, i.e., whether there's at least one column [which may then be expanded
143//! into further columns later]). We're going to match on the top of the new pattern-stack, `p_1`:
144//!
145//! - If `p_1 == c(r_1, .., r_a)`, i.e. we have a constructor pattern.
146//! Then, the usefulness of `p_1` can be reduced to whether it is useful when
147//! we ignore all the patterns in the first column of `P` that involve other constructors.
148//! This is where `S(c, P)` comes in:
149//!
150//! ```text
151//! U(P, p) := U(S(c, P), S(c, p))
152//! ```
153//!
154//! This special case is handled in `is_useful_specialized`.
155//!
156//! For example, if `P` is:
157//!
158//! ```text
159//! [
160//! [Some(true), _],
161//! [None, 0],
162//! ]
163//! ```
164//!
165//! and `p` is `[Some(false), 0]`, then we don't care about row 2 since we know `p` only
166//! matches values that row 2 doesn't. For row 1 however, we need to dig into the
167//! arguments of `Some` to know whether some new value is covered. So we compute
168//! `U([[true, _]], [false, 0])`.
169//!
170//! - If `p_1 == _`, then we look at the list of constructors that appear in the first component of
171//! the rows of `P`:
172//! - If there are some constructors that aren't present, then we might think that the
173//! wildcard `_` is useful, since it covers those constructors that weren't covered
174//! before.
175//! That's almost correct, but only works if there were no wildcards in those first
176//! components. So we need to check that `p` is useful with respect to the rows that
177//! start with a wildcard, if there are any. This is where `D` comes in:
178//! `U(P, p) := U(D(P), D(p))`
179//!
180//! For example, if `P` is:
181//! ```text
182//! [
183//! [_, true, _],
184//! [None, false, 1],
185//! ]
186//! ```
187//! and `p` is `[_, false, _]`, the `Some` constructor doesn't appear in `P`. So if we
188//! only had row 2, we'd know that `p` is useful. However row 1 starts with a
189//! wildcard, so we need to check whether `U([[true, _]], [false, 1])`.
190//!
191//! - Otherwise, all possible constructors (for the relevant type) are present. In this
192//! case we must check whether the wildcard pattern covers any unmatched value. For
193//! that, we can think of the `_` pattern as a big OR-pattern that covers all
194//! possible constructors. For `Option`, that would mean `_ = None | Some(_)` for
195//! example. The wildcard pattern is useful in this case if it is useful when
196//! specialized to one of the possible constructors. So we compute:
197//! `U(P, p) := ∃(k ϵ constructors) U(S(k, P), S(k, p))`
198//!
199//! For example, if `P` is:
200//! ```text
201//! [
202//! [Some(true), _],
203//! [None, false],
204//! ]
205//! ```
206//! and `p` is `[_, false]`, both `None` and `Some` constructors appear in the first
207//! components of `P`. We will therefore try popping both constructors in turn: we
208//! compute `U([[true, _]], [_, false])` for the `Some` constructor, and `U([[false]],
209//! [false])` for the `None` constructor. The first case returns true, so we know that
210//! `p` is useful for `P`. Indeed, it matches `[Some(false), _]` that wasn't matched
211//! before.
212//!
213//! - If `p_1 == r_1 | r_2`, then the usefulness depends on each `r_i` separately:
214//!
215//! ```text
216//! U(P, p) := U(P, (r_1, p_2, .., p_n))
217//! || U(P, (r_2, p_2, .., p_n))
218//! ```
219use std::{iter, sync::Arc};
220
221use hir_def::{
222 adt::VariantData,
223 body::Body,
224 expr::{Expr, Literal, Pat, PatId},
225 EnumVariantId, StructId, VariantId,
226};
227use la_arena::Idx; 13use la_arena::Idx;
228use smallvec::{smallvec, SmallVec};
229
230use crate::{db::HirDatabase, AdtId, InferenceResult, Interner, TyExt, TyKind};
231
232#[derive(Debug, Clone, Copy)]
233/// Either a pattern from the source code being analyzed, represented as
234/// as `PatId`, or a `Wild` pattern which is created as an intermediate
235/// step in the match checking algorithm and thus is not backed by a
236/// real `PatId`.
237///
238/// Note that it is totally valid for the `PatId` variant to contain
239/// a `PatId` which resolves to a `Wild` pattern, if that wild pattern
240/// exists in the source code being analyzed.
241enum PatIdOrWild {
242 PatId(PatId),
243 Wild,
244}
245 14
246impl PatIdOrWild { 15use crate::{db::HirDatabase, InferenceResult, Interner, Substitution, Ty, TyKind};
247 fn as_pat(self, cx: &MatchCheckCtx) -> Pat {
248 match self {
249 PatIdOrWild::PatId(id) => cx.body.pats[id].clone(),
250 PatIdOrWild::Wild => Pat::Wild,
251 }
252 }
253 16
254 fn as_id(self) -> Option<PatId> { 17use self::pat_util::EnumerateAndAdjustIterator;
255 match self {
256 PatIdOrWild::PatId(id) => Some(id),
257 PatIdOrWild::Wild => None,
258 }
259 }
260}
261 18
262impl From<PatId> for PatIdOrWild { 19pub(crate) use self::usefulness::MatchArm;
263 fn from(pat_id: PatId) -> Self {
264 Self::PatId(pat_id)
265 }
266}
267 20
268impl From<&PatId> for PatIdOrWild { 21pub(crate) type PatId = Idx<Pat>;
269 fn from(pat_id: &PatId) -> Self {
270 Self::PatId(*pat_id)
271 }
272}
273 22
274#[derive(Debug, Clone, Copy, PartialEq)] 23#[derive(Clone, Debug)]
275pub(super) enum MatchCheckErr { 24pub(crate) enum PatternError {
276 NotImplemented, 25 Unimplemented,
277 MalformedMatchArm, 26 UnresolvedVariant,
278 /// Used when type inference cannot resolve the type of
279 /// a pattern or expression.
280 Unknown,
281} 27}
282 28
283/// The return type of `is_useful` is either an indication of usefulness 29#[derive(Clone, Debug, PartialEq)]
284/// of the match arm, or an error in the case the match statement 30pub(crate) struct FieldPat {
285/// is made up of types for which exhaustiveness checking is currently 31 pub(crate) field: LocalFieldId,
286/// not completely implemented. 32 pub(crate) pattern: Pat,
287/// 33}
288/// The `std::result::Result` type is used here rather than a custom enum
289/// to allow the use of `?`.
290pub(super) type MatchCheckResult<T> = Result<T, MatchCheckErr>;
291
292#[derive(Debug)]
293/// A row in a Matrix.
294///
295/// This type is modeled from the struct of the same name in `rustc`.
296pub(super) struct PatStack(PatStackInner);
297type PatStackInner = SmallVec<[PatIdOrWild; 2]>;
298 34
299impl PatStack { 35#[derive(Clone, Debug, PartialEq)]
300 pub(super) fn from_pattern(pat_id: PatId) -> PatStack { 36pub(crate) struct Pat {
301 Self(smallvec!(pat_id.into())) 37 pub(crate) ty: Ty,
302 } 38 pub(crate) kind: Box<PatKind>,
39}
303 40
304 pub(super) fn from_wild() -> PatStack { 41impl Pat {
305 Self(smallvec!(PatIdOrWild::Wild)) 42 pub(crate) fn wildcard_from_ty(ty: &Ty) -> Self {
43 Pat { ty: ty.clone(), kind: Box::new(PatKind::Wild) }
306 } 44 }
45}
307 46
308 fn from_slice(slice: &[PatIdOrWild]) -> PatStack { 47/// Close relative to `rustc_mir_build::thir::pattern::PatKind`
309 Self(SmallVec::from_slice(slice)) 48#[derive(Clone, Debug, PartialEq)]
310 } 49pub(crate) enum PatKind {
50 Wild,
311 51
312 fn from_vec(v: PatStackInner) -> PatStack { 52 /// `x`, `ref x`, `x @ P`, etc.
313 Self(v) 53 Binding {
314 } 54 subpattern: Option<Pat>,
55 },
56
57 /// `Foo(...)` or `Foo{...}` or `Foo`, where `Foo` is a variant name from an ADT with
58 /// multiple variants.
59 Variant {
60 substs: Substitution,
61 enum_variant: EnumVariantId,
62 subpatterns: Vec<FieldPat>,
63 },
64
65 /// `(...)`, `Foo(...)`, `Foo{...}`, or `Foo`, where `Foo` is a variant name from an ADT with
66 /// a single variant.
67 Leaf {
68 subpatterns: Vec<FieldPat>,
69 },
70
71 /// `box P`, `&P`, `&mut P`, etc.
72 Deref {
73 subpattern: Pat,
74 },
75
76 // FIXME: for now, only bool literals are implemented
77 LiteralBool {
78 value: bool,
79 },
80
81 /// An or-pattern, e.g. `p | q`.
82 /// Invariant: `pats.len() >= 2`.
83 Or {
84 pats: Vec<Pat>,
85 },
86}
315 87
316 fn get_head(&self) -> Option<PatIdOrWild> { 88pub(crate) struct PatCtxt<'a> {
317 self.0.first().copied() 89 db: &'a dyn HirDatabase,
318 } 90 infer: &'a InferenceResult,
91 body: &'a Body,
92 pub(crate) errors: Vec<PatternError>,
93}
319 94
320 fn tail(&self) -> &[PatIdOrWild] { 95impl<'a> PatCtxt<'a> {
321 self.0.get(1..).unwrap_or(&[]) 96 pub(crate) fn new(db: &'a dyn HirDatabase, infer: &'a InferenceResult, body: &'a Body) -> Self {
97 Self { db, infer, body, errors: Vec::new() }
322 } 98 }
323 99
324 fn to_tail(&self) -> PatStack { 100 pub(crate) fn lower_pattern(&mut self, pat: hir_def::expr::PatId) -> Pat {
325 Self::from_slice(self.tail()) 101 // FIXME: implement pattern adjustments (implicit pattern dereference; "RFC 2005-match-ergonomics")
102 // More info https://github.com/rust-lang/rust/issues/42640#issuecomment-313535089
103 let unadjusted_pat = self.lower_pattern_unadjusted(pat);
104 unadjusted_pat
326 } 105 }
327 106
328 fn replace_head_with<I, T>(&self, pats: I) -> PatStack 107 fn lower_pattern_unadjusted(&mut self, pat: hir_def::expr::PatId) -> Pat {
329 where 108 let ty = &self.infer[pat];
330 I: Iterator<Item = T>, 109 let variant = self.infer.variant_resolution_for_pat(pat);
331 T: Into<PatIdOrWild>,
332 {
333 let mut patterns: PatStackInner = smallvec![];
334 for pat in pats {
335 patterns.push(pat.into());
336 }
337 for pat in &self.0[1..] {
338 patterns.push(*pat);
339 }
340 PatStack::from_vec(patterns)
341 }
342 110
343 /// Computes `D(self)`. 111 let kind = match self.body[pat] {
344 /// 112 hir_def::expr::Pat::Wild => PatKind::Wild,
345 /// See the module docs and the associated documentation in rustc for details.
346 fn specialize_wildcard(&self, cx: &MatchCheckCtx) -> Option<PatStack> {
347 if matches!(self.get_head()?.as_pat(cx), Pat::Wild) {
348 Some(self.to_tail())
349 } else {
350 None
351 }
352 }
353 113
354 /// Computes `S(constructor, self)`. 114 hir_def::expr::Pat::Lit(expr) => self.lower_lit(expr),
355 ///
356 /// See the module docs and the associated documentation in rustc for details.
357 fn specialize_constructor(
358 &self,
359 cx: &MatchCheckCtx,
360 constructor: &Constructor,
361 ) -> MatchCheckResult<Option<PatStack>> {
362 let head = match self.get_head() {
363 Some(head) => head,
364 None => return Ok(None),
365 };
366 115
367 let head_pat = head.as_pat(cx); 116 hir_def::expr::Pat::Path(ref path) => {
368 let result = match (head_pat, constructor) { 117 return self.lower_path(pat, path);
369 (Pat::Tuple { args: pat_ids, ellipsis }, &Constructor::Tuple { arity }) => {
370 if let Some(ellipsis) = ellipsis {
371 let (pre, post) = pat_ids.split_at(ellipsis);
372 let n_wild_pats = arity.saturating_sub(pat_ids.len());
373 let pre_iter = pre.iter().map(Into::into);
374 let wildcards = iter::repeat(PatIdOrWild::Wild).take(n_wild_pats);
375 let post_iter = post.iter().map(Into::into);
376 Some(self.replace_head_with(pre_iter.chain(wildcards).chain(post_iter)))
377 } else {
378 Some(self.replace_head_with(pat_ids.iter()))
379 }
380 }
381 (Pat::Lit(lit_expr), Constructor::Bool(constructor_val)) => {
382 match cx.body.exprs[lit_expr] {
383 Expr::Literal(Literal::Bool(pat_val)) if *constructor_val == pat_val => {
384 Some(self.to_tail())
385 }
386 // it was a bool but the value doesn't match
387 Expr::Literal(Literal::Bool(_)) => None,
388 // perhaps this is actually unreachable given we have
389 // already checked that these match arms have the appropriate type?
390 _ => return Err(MatchCheckErr::NotImplemented),
391 }
392 } 118 }
393 (Pat::Wild, constructor) => Some(self.expand_wildcard(cx, constructor)?), 119
394 (Pat::Path(_), constructor) => { 120 hir_def::expr::Pat::Tuple { ref args, ellipsis } => {
395 // unit enum variants become `Pat::Path` 121 let arity = match *ty.kind(&Interner) {
396 let pat_id = head.as_id().expect("we know this isn't a wild"); 122 TyKind::Tuple(arity, _) => arity,
397 let variant_id: VariantId = match constructor { 123 _ => panic!("unexpected type for tuple pattern: {:?}", ty),
398 &Constructor::Enum(e) => e.into(),
399 &Constructor::Struct(s) => s.into(),
400 _ => return Err(MatchCheckErr::NotImplemented),
401 }; 124 };
402 if Some(variant_id) != cx.infer.variant_resolution_for_pat(pat_id) { 125 let subpatterns = self.lower_tuple_subpats(args, arity, ellipsis);
403 None 126 PatKind::Leaf { subpatterns }
404 } else {
405 Some(self.to_tail())
406 }
407 } 127 }
408 (Pat::TupleStruct { args: ref pat_ids, ellipsis, .. }, constructor) => { 128
409 let pat_id = head.as_id().expect("we know this isn't a wild"); 129 hir_def::expr::Pat::Bind { subpat, .. } => {
410 let variant_id: VariantId = match constructor { 130 PatKind::Binding { subpattern: self.lower_opt_pattern(subpat) }
411 &Constructor::Enum(e) => e.into(),
412 &Constructor::Struct(s) => s.into(),
413 _ => return Err(MatchCheckErr::MalformedMatchArm),
414 };
415 if Some(variant_id) != cx.infer.variant_resolution_for_pat(pat_id) {
416 None
417 } else {
418 let constructor_arity = constructor.arity(cx)?;
419 if let Some(ellipsis_position) = ellipsis {
420 // If there are ellipsis in the pattern, the ellipsis must take the place
421 // of at least one sub-pattern, so `pat_ids` should be smaller than the
422 // constructor arity.
423 if pat_ids.len() < constructor_arity {
424 let mut new_patterns: Vec<PatIdOrWild> = vec![];
425
426 for pat_id in &pat_ids[0..ellipsis_position] {
427 new_patterns.push((*pat_id).into());
428 }
429
430 for _ in 0..(constructor_arity - pat_ids.len()) {
431 new_patterns.push(PatIdOrWild::Wild);
432 }
433
434 for pat_id in &pat_ids[ellipsis_position..pat_ids.len()] {
435 new_patterns.push((*pat_id).into());
436 }
437
438 Some(self.replace_head_with(new_patterns.into_iter()))
439 } else {
440 return Err(MatchCheckErr::MalformedMatchArm);
441 }
442 } else {
443 // If there is no ellipsis in the tuple pattern, the number
444 // of patterns must equal the constructor arity.
445 if pat_ids.len() == constructor_arity {
446 Some(self.replace_head_with(pat_ids.into_iter()))
447 } else {
448 return Err(MatchCheckErr::MalformedMatchArm);
449 }
450 }
451 }
452 }
453 (Pat::Record { args: ref arg_patterns, .. }, constructor) => {
454 let pat_id = head.as_id().expect("we know this isn't a wild");
455 let (variant_id, variant_data) = match constructor {
456 &Constructor::Enum(e) => (
457 e.into(),
458 cx.db.enum_data(e.parent).variants[e.local_id].variant_data.clone(),
459 ),
460 &Constructor::Struct(s) => {
461 (s.into(), cx.db.struct_data(s).variant_data.clone())
462 }
463 _ => return Err(MatchCheckErr::MalformedMatchArm),
464 };
465 if Some(variant_id) != cx.infer.variant_resolution_for_pat(pat_id) {
466 None
467 } else {
468 match variant_data.as_ref() {
469 VariantData::Record(struct_field_arena) => {
470 // Here we treat any missing fields in the record as the wild pattern, as
471 // if the record has ellipsis. We want to do this here even if the
472 // record does not contain ellipsis, because it allows us to continue
473 // enforcing exhaustiveness for the rest of the match statement.
474 //
475 // Creating the diagnostic for the missing field in the pattern
476 // should be done in a different diagnostic.
477 let patterns = struct_field_arena.iter().map(|(_, struct_field)| {
478 arg_patterns
479 .iter()
480 .find(|pat| pat.name == struct_field.name)
481 .map(|pat| PatIdOrWild::from(pat.pat))
482 .unwrap_or(PatIdOrWild::Wild)
483 });
484
485 Some(self.replace_head_with(patterns))
486 }
487 _ => return Err(MatchCheckErr::Unknown),
488 }
489 }
490 } 131 }
491 (Pat::Or(_), _) => return Err(MatchCheckErr::NotImplemented),
492 (_, _) => return Err(MatchCheckErr::NotImplemented),
493 };
494 132
495 Ok(result) 133 hir_def::expr::Pat::TupleStruct { ref args, ellipsis, .. } if variant.is_some() => {
496 } 134 let expected_len = variant.unwrap().variant_data(self.db.upcast()).fields().len();
497 135 let subpatterns = self.lower_tuple_subpats(args, expected_len, ellipsis);
498 /// A special case of `specialize_constructor` where the head of the pattern stack 136 self.lower_variant_or_leaf(pat, ty, subpatterns)
499 /// is a Wild pattern. 137 }
500 ///
501 /// Replaces the Wild pattern at the head of the pattern stack with N Wild patterns
502 /// (N >= 0), where N is the arity of the given constructor.
503 fn expand_wildcard(
504 &self,
505 cx: &MatchCheckCtx,
506 constructor: &Constructor,
507 ) -> MatchCheckResult<PatStack> {
508 assert_eq!(
509 Pat::Wild,
510 self.get_head().expect("expand_wildcard called on empty PatStack").as_pat(cx),
511 "expand_wildcard must only be called on PatStack with wild at head",
512 );
513 138
514 let mut patterns: PatStackInner = smallvec![]; 139 hir_def::expr::Pat::Record { ref args, .. } if variant.is_some() => {
140 let variant_data = variant.unwrap().variant_data(self.db.upcast());
141 let subpatterns = args
142 .iter()
143 .map(|field| FieldPat {
144 // XXX(iDawer): field lookup is inefficient
145 field: variant_data.field(&field.name).unwrap(),
146 pattern: self.lower_pattern(field.pat),
147 })
148 .collect();
149 self.lower_variant_or_leaf(pat, ty, subpatterns)
150 }
151 hir_def::expr::Pat::TupleStruct { .. } | hir_def::expr::Pat::Record { .. } => {
152 self.errors.push(PatternError::UnresolvedVariant);
153 PatKind::Wild
154 }
515 155
516 for _ in 0..constructor.arity(cx)? { 156 hir_def::expr::Pat::Or(ref pats) => PatKind::Or { pats: self.lower_patterns(pats) },
517 patterns.push(PatIdOrWild::Wild);
518 }
519 157
520 for pat in &self.0[1..] { 158 _ => {
521 patterns.push(*pat); 159 self.errors.push(PatternError::Unimplemented);
522 } 160 PatKind::Wild
161 }
162 };
523 163
524 Ok(PatStack::from_vec(patterns)) 164 Pat { ty: ty.clone(), kind: Box::new(kind) }
525 } 165 }
526}
527 166
528/// A collection of PatStack. 167 fn lower_tuple_subpats(
529/// 168 &mut self,
530/// This type is modeled from the struct of the same name in `rustc`. 169 pats: &[hir_def::expr::PatId],
531pub(super) struct Matrix(Vec<PatStack>); 170 expected_len: usize,
532 171 ellipsis: Option<usize>,
533impl Matrix { 172 ) -> Vec<FieldPat> {
534 pub(super) fn empty() -> Self { 173 pats.iter()
535 Self(vec![]) 174 .enumerate_and_adjust(expected_len, ellipsis)
175 .map(|(i, &subpattern)| FieldPat {
176 field: LocalFieldId::from_raw((i as u32).into()),
177 pattern: self.lower_pattern(subpattern),
178 })
179 .collect()
536 } 180 }
537 181
538 pub(super) fn push(&mut self, cx: &MatchCheckCtx, row: PatStack) { 182 fn lower_patterns(&mut self, pats: &[hir_def::expr::PatId]) -> Vec<Pat> {
539 if let Some(Pat::Or(pat_ids)) = row.get_head().map(|pat_id| pat_id.as_pat(cx)) { 183 pats.iter().map(|&p| self.lower_pattern(p)).collect()
540 // Or patterns are expanded here
541 for pat_id in pat_ids {
542 self.0.push(row.replace_head_with([pat_id].iter()));
543 }
544 } else {
545 self.0.push(row);
546 }
547 } 184 }
548 185
549 fn is_empty(&self) -> bool { 186 fn lower_opt_pattern(&mut self, pat: Option<hir_def::expr::PatId>) -> Option<Pat> {
550 self.0.is_empty() 187 pat.map(|p| self.lower_pattern(p))
551 } 188 }
552 189
553 fn heads(&self) -> Vec<PatIdOrWild> { 190 fn lower_variant_or_leaf(
554 self.0.iter().flat_map(|p| p.get_head()).collect() 191 &mut self,
192 pat: hir_def::expr::PatId,
193 ty: &Ty,
194 subpatterns: Vec<FieldPat>,
195 ) -> PatKind {
196 let kind = match self.infer.variant_resolution_for_pat(pat) {
197 Some(variant_id) => {
198 if let VariantId::EnumVariantId(enum_variant) = variant_id {
199 let substs = match ty.kind(&Interner) {
200 TyKind::Adt(_, substs) | TyKind::FnDef(_, substs) => substs.clone(),
201 TyKind::Error => {
202 return PatKind::Wild;
203 }
204 _ => panic!("inappropriate type for def: {:?}", ty),
205 };
206 PatKind::Variant { substs, enum_variant, subpatterns }
207 } else {
208 PatKind::Leaf { subpatterns }
209 }
210 }
211 None => {
212 self.errors.push(PatternError::UnresolvedVariant);
213 PatKind::Wild
214 }
215 };
216 kind
555 } 217 }
556 218
557 /// Computes `D(self)` for each contained PatStack. 219 fn lower_path(&mut self, pat: hir_def::expr::PatId, _path: &hir_def::path::Path) -> Pat {
558 /// 220 let ty = &self.infer[pat];
559 /// See the module docs and the associated documentation in rustc for details.
560 fn specialize_wildcard(&self, cx: &MatchCheckCtx) -> Self {
561 Self::collect(cx, self.0.iter().filter_map(|r| r.specialize_wildcard(cx)))
562 }
563 221
564 /// Computes `S(constructor, self)` for each contained PatStack. 222 let pat_from_kind = |kind| Pat { ty: ty.clone(), kind: Box::new(kind) };
565 /// 223
566 /// See the module docs and the associated documentation in rustc for details. 224 match self.infer.variant_resolution_for_pat(pat) {
567 fn specialize_constructor( 225 Some(_) => pat_from_kind(self.lower_variant_or_leaf(pat, ty, Vec::new())),
568 &self, 226 None => {
569 cx: &MatchCheckCtx, 227 self.errors.push(PatternError::UnresolvedVariant);
570 constructor: &Constructor, 228 pat_from_kind(PatKind::Wild)
571 ) -> MatchCheckResult<Self> {
572 let mut new_matrix = Matrix::empty();
573 for pat in &self.0 {
574 if let Some(pat) = pat.specialize_constructor(cx, constructor)? {
575 new_matrix.push(cx, pat);
576 } 229 }
577 } 230 }
578
579 Ok(new_matrix)
580 } 231 }
581 232
582 fn collect<T: IntoIterator<Item = PatStack>>(cx: &MatchCheckCtx, iter: T) -> Self { 233 fn lower_lit(&mut self, expr: hir_def::expr::ExprId) -> PatKind {
583 let mut matrix = Matrix::empty(); 234 use hir_def::expr::{Expr, Literal::Bool};
584 235
585 for pat in iter { 236 match self.body[expr] {
586 // using push ensures we expand or-patterns 237 Expr::Literal(Bool(value)) => PatKind::LiteralBool { value },
587 matrix.push(cx, pat); 238 _ => {
239 self.errors.push(PatternError::Unimplemented);
240 PatKind::Wild
241 }
588 } 242 }
589
590 matrix
591 } 243 }
592} 244}
593 245
594#[derive(Clone, Debug, PartialEq)] 246pub(crate) trait PatternFoldable: Sized {
595/// An indication of the usefulness of a given match arm, where 247 fn fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
596/// usefulness is defined as matching some patterns which were 248 self.super_fold_with(folder)
597/// not matched by an prior match arms. 249 }
598///
599/// We may eventually need an `Unknown` variant here.
600pub(super) enum Usefulness {
601 Useful,
602 NotUseful,
603}
604 250
605pub(super) struct MatchCheckCtx<'a> { 251 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self;
606 pub(super) match_expr: Idx<Expr>,
607 pub(super) body: Arc<Body>,
608 pub(super) infer: Arc<InferenceResult>,
609 pub(super) db: &'a dyn HirDatabase,
610} 252}
611 253
612/// Given a set of patterns `matrix`, and pattern to consider `v`, determines 254pub(crate) trait PatternFolder: Sized {
613/// whether `v` is useful. A pattern is useful if it covers cases which were 255 fn fold_pattern(&mut self, pattern: &Pat) -> Pat {
614/// not previously covered. 256 pattern.super_fold_with(self)
615///
616/// When calling this function externally (that is, not the recursive calls) it
617/// expected that you have already type checked the match arms. All patterns in
618/// matrix should be the same type as v, as well as they should all be the same
619/// type as the match expression.
620pub(super) fn is_useful(
621 cx: &MatchCheckCtx,
622 matrix: &Matrix,
623 v: &PatStack,
624) -> MatchCheckResult<Usefulness> {
625 // Handle two special cases:
626 // - enum with no variants
627 // - `!` type
628 // In those cases, no match arm is useful.
629 match cx.infer[cx.match_expr].strip_references().kind(&Interner) {
630 TyKind::Adt(AdtId(hir_def::AdtId::EnumId(enum_id)), ..) => {
631 if cx.db.enum_data(*enum_id).variants.is_empty() {
632 return Ok(Usefulness::NotUseful);
633 }
634 }
635 TyKind::Never => return Ok(Usefulness::NotUseful),
636 _ => (),
637 } 257 }
638 258
639 let head = match v.get_head() { 259 fn fold_pattern_kind(&mut self, kind: &PatKind) -> PatKind {
640 Some(head) => head, 260 kind.super_fold_with(self)
641 None => {
642 let result = if matrix.is_empty() { Usefulness::Useful } else { Usefulness::NotUseful };
643
644 return Ok(result);
645 }
646 };
647
648 if let Pat::Or(pat_ids) = head.as_pat(cx) {
649 let mut found_unimplemented = false;
650 let any_useful = pat_ids.iter().any(|&pat_id| {
651 let v = PatStack::from_pattern(pat_id);
652
653 match is_useful(cx, matrix, &v) {
654 Ok(Usefulness::Useful) => true,
655 Ok(Usefulness::NotUseful) => false,
656 _ => {
657 found_unimplemented = true;
658 false
659 }
660 }
661 });
662
663 return if any_useful {
664 Ok(Usefulness::Useful)
665 } else if found_unimplemented {
666 Err(MatchCheckErr::NotImplemented)
667 } else {
668 Ok(Usefulness::NotUseful)
669 };
670 } 261 }
262}
671 263
672 if let Some(constructor) = pat_constructor(cx, head)? { 264impl<T: PatternFoldable> PatternFoldable for Box<T> {
673 let matrix = matrix.specialize_constructor(&cx, &constructor)?; 265 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
674 let v = v 266 let content: T = (**self).fold_with(folder);
675 .specialize_constructor(&cx, &constructor)? 267 Box::new(content)
676 .expect("we know this can't fail because we get the constructor from `v.head()` above"); 268 }
677 269}
678 is_useful(&cx, &matrix, &v)
679 } else {
680 // expanding wildcard
681 let mut used_constructors: Vec<Constructor> = vec![];
682 for pat in matrix.heads() {
683 if let Some(constructor) = pat_constructor(cx, pat)? {
684 used_constructors.push(constructor);
685 }
686 }
687
688 // We assume here that the first constructor is the "correct" type. Since we
689 // only care about the "type" of the constructor (i.e. if it is a bool we
690 // don't care about the value), this assumption should be valid as long as
691 // the match statement is well formed. We currently uphold this invariant by
692 // filtering match arms before calling `is_useful`, only passing in match arms
693 // whose type matches the type of the match expression.
694 match &used_constructors.first() {
695 Some(constructor) if all_constructors_covered(&cx, constructor, &used_constructors) => {
696 // If all constructors are covered, then we need to consider whether
697 // any values are covered by this wildcard.
698 //
699 // For example, with matrix '[[Some(true)], [None]]', all
700 // constructors are covered (`Some`/`None`), so we need
701 // to perform specialization to see that our wildcard will cover
702 // the `Some(false)` case.
703 //
704 // Here we create a constructor for each variant and then check
705 // usefulness after specializing for that constructor.
706 let mut found_unimplemented = false;
707 for constructor in constructor.all_constructors(cx) {
708 let matrix = matrix.specialize_constructor(&cx, &constructor)?;
709 let v = v.expand_wildcard(&cx, &constructor)?;
710
711 match is_useful(&cx, &matrix, &v) {
712 Ok(Usefulness::Useful) => return Ok(Usefulness::Useful),
713 Ok(Usefulness::NotUseful) => continue,
714 _ => found_unimplemented = true,
715 };
716 }
717
718 if found_unimplemented {
719 Err(MatchCheckErr::NotImplemented)
720 } else {
721 Ok(Usefulness::NotUseful)
722 }
723 }
724 _ => {
725 // Either not all constructors are covered, or the only other arms
726 // are wildcards. Either way, this pattern is useful if it is useful
727 // when compared to those arms with wildcards.
728 let matrix = matrix.specialize_wildcard(&cx);
729 let v = v.to_tail();
730 270
731 is_useful(&cx, &matrix, &v) 271impl<T: PatternFoldable> PatternFoldable for Vec<T> {
732 } 272 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
733 } 273 self.iter().map(|t| t.fold_with(folder)).collect()
734 } 274 }
735} 275}
736 276
737#[derive(Debug, Clone, Copy)] 277impl<T: PatternFoldable> PatternFoldable for Option<T> {
738/// Similar to TypeCtor, but includes additional information about the specific 278 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
739/// value being instantiated. For example, TypeCtor::Bool doesn't contain the 279 self.as_ref().map(|t| t.fold_with(folder))
740/// boolean value. 280 }
741enum Constructor {
742 Bool(bool),
743 Tuple { arity: usize },
744 Enum(EnumVariantId),
745 Struct(StructId),
746} 281}
747 282
748impl Constructor { 283macro_rules! clone_impls {
749 fn arity(&self, cx: &MatchCheckCtx) -> MatchCheckResult<usize> { 284 ($($ty:ty),+) => {
750 let arity = match self { 285 $(
751 Constructor::Bool(_) => 0, 286 impl PatternFoldable for $ty {
752 Constructor::Tuple { arity } => *arity, 287 fn super_fold_with<F: PatternFolder>(&self, _: &mut F) -> Self {
753 Constructor::Enum(e) => { 288 Clone::clone(self)
754 match cx.db.enum_data(e.parent).variants[e.local_id].variant_data.as_ref() {
755 VariantData::Tuple(struct_field_data) => struct_field_data.len(),
756 VariantData::Record(struct_field_data) => struct_field_data.len(),
757 VariantData::Unit => 0,
758 } 289 }
759 } 290 }
760 &Constructor::Struct(s) => match cx.db.struct_data(s).variant_data.as_ref() { 291 )+
761 VariantData::Tuple(struct_field_data) => struct_field_data.len(),
762 VariantData::Record(struct_field_data) => struct_field_data.len(),
763 VariantData::Unit => 0,
764 },
765 };
766
767 Ok(arity)
768 } 292 }
293}
769 294
770 fn all_constructors(&self, cx: &MatchCheckCtx) -> Vec<Constructor> { 295clone_impls! { LocalFieldId, Ty, Substitution, EnumVariantId }
771 match self { 296
772 Constructor::Bool(_) => vec![Constructor::Bool(true), Constructor::Bool(false)], 297impl PatternFoldable for FieldPat {
773 Constructor::Tuple { .. } | Constructor::Struct(_) => vec![*self], 298 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
774 Constructor::Enum(e) => cx 299 FieldPat { field: self.field.fold_with(folder), pattern: self.pattern.fold_with(folder) }
775 .db
776 .enum_data(e.parent)
777 .variants
778 .iter()
779 .map(|(local_id, _)| {
780 Constructor::Enum(EnumVariantId { parent: e.parent, local_id })
781 })
782 .collect(),
783 }
784 } 300 }
785} 301}
786 302
787/// Returns the constructor for the given pattern. Should only return None 303impl PatternFoldable for Pat {
788/// in the case of a Wild pattern. 304 fn fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
789fn pat_constructor(cx: &MatchCheckCtx, pat: PatIdOrWild) -> MatchCheckResult<Option<Constructor>> { 305 folder.fold_pattern(self)
790 let res = match pat.as_pat(cx) { 306 }
791 Pat::Wild => None,
792 Pat::Tuple { .. } => {
793 let pat_id = pat.as_id().expect("we already know this pattern is not a wild");
794 Some(Constructor::Tuple {
795 arity: cx.infer.type_of_pat[pat_id]
796 .as_tuple()
797 .ok_or(MatchCheckErr::Unknown)?
798 .len(&Interner),
799 })
800 }
801 Pat::Lit(lit_expr) => match cx.body.exprs[lit_expr] {
802 Expr::Literal(Literal::Bool(val)) => Some(Constructor::Bool(val)),
803 _ => return Err(MatchCheckErr::NotImplemented),
804 },
805 Pat::TupleStruct { .. } | Pat::Path(_) | Pat::Record { .. } => {
806 let pat_id = pat.as_id().expect("we already know this pattern is not a wild");
807 let variant_id =
808 cx.infer.variant_resolution_for_pat(pat_id).ok_or(MatchCheckErr::Unknown)?;
809 match variant_id {
810 VariantId::EnumVariantId(enum_variant_id) => {
811 Some(Constructor::Enum(enum_variant_id))
812 }
813 VariantId::StructId(struct_id) => Some(Constructor::Struct(struct_id)),
814 _ => return Err(MatchCheckErr::NotImplemented),
815 }
816 }
817 _ => return Err(MatchCheckErr::NotImplemented),
818 };
819 307
820 Ok(res) 308 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
309 Pat { ty: self.ty.fold_with(folder), kind: self.kind.fold_with(folder) }
310 }
821} 311}
822 312
823fn all_constructors_covered( 313impl PatternFoldable for PatKind {
824 cx: &MatchCheckCtx, 314 fn fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
825 constructor: &Constructor, 315 folder.fold_pattern_kind(self)
826 used_constructors: &[Constructor], 316 }
827) -> bool {
828 match constructor {
829 Constructor::Tuple { arity } => {
830 used_constructors.iter().any(|constructor| match constructor {
831 Constructor::Tuple { arity: used_arity } => arity == used_arity,
832 _ => false,
833 })
834 }
835 Constructor::Bool(_) => {
836 if used_constructors.is_empty() {
837 return false;
838 }
839
840 let covers_true =
841 used_constructors.iter().any(|c| matches!(c, Constructor::Bool(true)));
842 let covers_false =
843 used_constructors.iter().any(|c| matches!(c, Constructor::Bool(false)));
844 317
845 covers_true && covers_false 318 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
846 } 319 match self {
847 Constructor::Enum(e) => cx.db.enum_data(e.parent).variants.iter().all(|(id, _)| { 320 PatKind::Wild => PatKind::Wild,
848 for constructor in used_constructors { 321 PatKind::Binding { subpattern } => {
849 if let Constructor::Enum(e) = constructor { 322 PatKind::Binding { subpattern: subpattern.fold_with(folder) }
850 if id == e.local_id {
851 return true;
852 }
853 }
854 } 323 }
855 324 PatKind::Variant { substs, enum_variant, subpatterns } => PatKind::Variant {
856 false 325 substs: substs.fold_with(folder),
857 }), 326 enum_variant: enum_variant.fold_with(folder),
858 &Constructor::Struct(s) => used_constructors.iter().any(|constructor| match constructor { 327 subpatterns: subpatterns.fold_with(folder),
859 &Constructor::Struct(sid) => sid == s, 328 },
860 _ => false, 329 PatKind::Leaf { subpatterns } => {
861 }), 330 PatKind::Leaf { subpatterns: subpatterns.fold_with(folder) }
331 }
332 PatKind::Deref { subpattern } => {
333 PatKind::Deref { subpattern: subpattern.fold_with(folder) }
334 }
335 &PatKind::LiteralBool { value } => PatKind::LiteralBool { value },
336 PatKind::Or { pats } => PatKind::Or { pats: pats.fold_with(folder) },
337 }
862 } 338 }
863} 339}
864 340
@@ -1514,6 +990,41 @@ fn main() {
1514"#, 990"#,
1515 ); 991 );
1516 } 992 }
993
994 #[test]
995 fn no_panic_at_unimplemented_subpattern_type() {
996 check_diagnostics(
997 r#"
998struct S { a: char}
999fn main(v: S) {
1000 match v { S{ a } => {} }
1001 match v { S{ a: _x } => {} }
1002 match v { S{ a: 'a' } => {} }
1003 match v { S{..} => {} }
1004 match v { _ => {} }
1005 match v { }
1006 //^ Missing match arm
1007}
1008"#,
1009 );
1010 }
1011
1012 #[test]
1013 fn binding() {
1014 check_diagnostics(
1015 r#"
1016fn main() {
1017 match true {
1018 _x @ true => {}
1019 false => {}
1020 }
1021 match true { _x @ true => {} }
1022 //^^^^ Missing match arm
1023}
1024"#,
1025 );
1026 }
1027
1517 mod false_negatives { 1028 mod false_negatives {
1518 //! The implementation of match checking here is a work in progress. As we roll this out, we 1029 //! The implementation of match checking here is a work in progress. As we roll this out, we
1519 //! prefer false negatives to false positives (ideally there would be no false positives). This 1030 //! prefer false negatives to false positives (ideally there would be no false positives). This
diff --git a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs b/crates/hir_ty/src/diagnostics/match_check/deconstruct_pat.rs
index 9fa82a952..9fa82a952 100644
--- a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
+++ b/crates/hir_ty/src/diagnostics/match_check/deconstruct_pat.rs
diff --git a/crates/hir_ty/src/diagnostics/pattern/pat_util.rs b/crates/hir_ty/src/diagnostics/match_check/pat_util.rs
index eb0b07a52..eb0b07a52 100644
--- a/crates/hir_ty/src/diagnostics/pattern/pat_util.rs
+++ b/crates/hir_ty/src/diagnostics/match_check/pat_util.rs
diff --git a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs b/crates/hir_ty/src/diagnostics/match_check/usefulness.rs
index b01e3557c..b01e3557c 100644
--- a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
+++ b/crates/hir_ty/src/diagnostics/match_check/usefulness.rs
diff --git a/crates/hir_ty/src/diagnostics/pattern.rs b/crates/hir_ty/src/diagnostics/pattern.rs
deleted file mode 100644
index f8d2e9baa..000000000
--- a/crates/hir_ty/src/diagnostics/pattern.rs
+++ /dev/null
@@ -1,1040 +0,0 @@
1//! Validation of matches.
2//!
3//! This module provides lowering from [hir_def::expr::Pat] to [self::Pat] and match
4//! checking algorithm.
5//!
6//! It is modeled on the rustc module `rustc_mir_build::thir::pattern`.
7
8mod deconstruct_pat;
9mod pat_util;
10pub(crate) mod usefulness;
11
12use hir_def::{body::Body, EnumVariantId, LocalFieldId, VariantId};
13use la_arena::Idx;
14
15use crate::{db::HirDatabase, InferenceResult, Interner, Substitution, Ty, TyKind};
16
17use self::pat_util::EnumerateAndAdjustIterator;
18
19pub(crate) type PatId = Idx<Pat>;
20
21#[derive(Clone, Debug)]
22pub(crate) enum PatternError {
23 Unimplemented,
24 UnresolvedVariant,
25}
26
27#[derive(Clone, Debug, PartialEq)]
28pub(crate) struct FieldPat {
29 pub(crate) field: LocalFieldId,
30 pub(crate) pattern: Pat,
31}
32
33#[derive(Clone, Debug, PartialEq)]
34pub(crate) struct Pat {
35 pub(crate) ty: Ty,
36 pub(crate) kind: Box<PatKind>,
37}
38
39impl Pat {
40 pub(crate) fn wildcard_from_ty(ty: &Ty) -> Self {
41 Pat { ty: ty.clone(), kind: Box::new(PatKind::Wild) }
42 }
43}
44
45/// Close relative to `rustc_mir_build::thir::pattern::PatKind`
46#[derive(Clone, Debug, PartialEq)]
47pub(crate) enum PatKind {
48 Wild,
49
50 /// `x`, `ref x`, `x @ P`, etc.
51 Binding {
52 subpattern: Option<Pat>,
53 },
54
55 /// `Foo(...)` or `Foo{...}` or `Foo`, where `Foo` is a variant name from an ADT with
56 /// multiple variants.
57 Variant {
58 substs: Substitution,
59 enum_variant: EnumVariantId,
60 subpatterns: Vec<FieldPat>,
61 },
62
63 /// `(...)`, `Foo(...)`, `Foo{...}`, or `Foo`, where `Foo` is a variant name from an ADT with
64 /// a single variant.
65 Leaf {
66 subpatterns: Vec<FieldPat>,
67 },
68
69 /// `box P`, `&P`, `&mut P`, etc.
70 Deref {
71 subpattern: Pat,
72 },
73
74 // FIXME: for now, only bool literals are implemented
75 LiteralBool {
76 value: bool,
77 },
78
79 /// An or-pattern, e.g. `p | q`.
80 /// Invariant: `pats.len() >= 2`.
81 Or {
82 pats: Vec<Pat>,
83 },
84}
85
86pub(crate) struct PatCtxt<'a> {
87 db: &'a dyn HirDatabase,
88 infer: &'a InferenceResult,
89 body: &'a Body,
90 pub(crate) errors: Vec<PatternError>,
91}
92
93impl<'a> PatCtxt<'a> {
94 pub(crate) fn new(db: &'a dyn HirDatabase, infer: &'a InferenceResult, body: &'a Body) -> Self {
95 Self { db, infer, body, errors: Vec::new() }
96 }
97
98 pub(crate) fn lower_pattern(&mut self, pat: hir_def::expr::PatId) -> Pat {
99 // FIXME: implement pattern adjustments (implicit pattern dereference; "RFC 2005-match-ergonomics")
100 // More info https://github.com/rust-lang/rust/issues/42640#issuecomment-313535089
101 let unadjusted_pat = self.lower_pattern_unadjusted(pat);
102 unadjusted_pat
103 }
104
105 fn lower_pattern_unadjusted(&mut self, pat: hir_def::expr::PatId) -> Pat {
106 let ty = &self.infer[pat];
107 let variant = self.infer.variant_resolution_for_pat(pat);
108
109 let kind = match self.body[pat] {
110 hir_def::expr::Pat::Wild => PatKind::Wild,
111
112 hir_def::expr::Pat::Lit(expr) => self.lower_lit(expr),
113
114 hir_def::expr::Pat::Path(ref path) => {
115 return self.lower_path(pat, path);
116 }
117
118 hir_def::expr::Pat::Tuple { ref args, ellipsis } => {
119 let arity = match *ty.kind(&Interner) {
120 TyKind::Tuple(arity, _) => arity,
121 _ => panic!("unexpected type for tuple pattern: {:?}", ty),
122 };
123 let subpatterns = self.lower_tuple_subpats(args, arity, ellipsis);
124 PatKind::Leaf { subpatterns }
125 }
126
127 hir_def::expr::Pat::Bind { subpat, .. } => {
128 PatKind::Binding { subpattern: self.lower_opt_pattern(subpat) }
129 }
130
131 hir_def::expr::Pat::TupleStruct { ref args, ellipsis, .. } if variant.is_some() => {
132 let expected_len = variant.unwrap().variant_data(self.db.upcast()).fields().len();
133 let subpatterns = self.lower_tuple_subpats(args, expected_len, ellipsis);
134 self.lower_variant_or_leaf(pat, ty, subpatterns)
135 }
136
137 hir_def::expr::Pat::Record { ref args, .. } if variant.is_some() => {
138 let variant_data = variant.unwrap().variant_data(self.db.upcast());
139 let subpatterns = args
140 .iter()
141 .map(|field| FieldPat {
142 // XXX(iDawer): field lookup is inefficient
143 field: variant_data.field(&field.name).unwrap(),
144 pattern: self.lower_pattern(field.pat),
145 })
146 .collect();
147 self.lower_variant_or_leaf(pat, ty, subpatterns)
148 }
149 hir_def::expr::Pat::TupleStruct { .. } | hir_def::expr::Pat::Record { .. } => {
150 self.errors.push(PatternError::UnresolvedVariant);
151 PatKind::Wild
152 }
153
154 hir_def::expr::Pat::Or(ref pats) => PatKind::Or { pats: self.lower_patterns(pats) },
155
156 _ => {
157 self.errors.push(PatternError::Unimplemented);
158 PatKind::Wild
159 }
160 };
161
162 Pat { ty: ty.clone(), kind: Box::new(kind) }
163 }
164
165 fn lower_tuple_subpats(
166 &mut self,
167 pats: &[hir_def::expr::PatId],
168 expected_len: usize,
169 ellipsis: Option<usize>,
170 ) -> Vec<FieldPat> {
171 pats.iter()
172 .enumerate_and_adjust(expected_len, ellipsis)
173 .map(|(i, &subpattern)| FieldPat {
174 field: LocalFieldId::from_raw((i as u32).into()),
175 pattern: self.lower_pattern(subpattern),
176 })
177 .collect()
178 }
179
180 fn lower_patterns(&mut self, pats: &[hir_def::expr::PatId]) -> Vec<Pat> {
181 pats.iter().map(|&p| self.lower_pattern(p)).collect()
182 }
183
184 fn lower_opt_pattern(&mut self, pat: Option<hir_def::expr::PatId>) -> Option<Pat> {
185 pat.map(|p| self.lower_pattern(p))
186 }
187
188 fn lower_variant_or_leaf(
189 &mut self,
190 pat: hir_def::expr::PatId,
191 ty: &Ty,
192 subpatterns: Vec<FieldPat>,
193 ) -> PatKind {
194 let kind = match self.infer.variant_resolution_for_pat(pat) {
195 Some(variant_id) => {
196 if let VariantId::EnumVariantId(enum_variant) = variant_id {
197 let substs = match ty.kind(&Interner) {
198 TyKind::Adt(_, substs) | TyKind::FnDef(_, substs) => substs.clone(),
199 TyKind::Error => {
200 return PatKind::Wild;
201 }
202 _ => panic!("inappropriate type for def: {:?}", ty),
203 };
204 PatKind::Variant { substs, enum_variant, subpatterns }
205 } else {
206 PatKind::Leaf { subpatterns }
207 }
208 }
209 None => {
210 self.errors.push(PatternError::UnresolvedVariant);
211 PatKind::Wild
212 }
213 };
214 kind
215 }
216
217 fn lower_path(&mut self, pat: hir_def::expr::PatId, _path: &hir_def::path::Path) -> Pat {
218 let ty = &self.infer[pat];
219
220 let pat_from_kind = |kind| Pat { ty: ty.clone(), kind: Box::new(kind) };
221
222 match self.infer.variant_resolution_for_pat(pat) {
223 Some(_) => pat_from_kind(self.lower_variant_or_leaf(pat, ty, Vec::new())),
224 None => {
225 self.errors.push(PatternError::UnresolvedVariant);
226 pat_from_kind(PatKind::Wild)
227 }
228 }
229 }
230
231 fn lower_lit(&mut self, expr: hir_def::expr::ExprId) -> PatKind {
232 use hir_def::expr::{Expr, Literal::Bool};
233
234 match self.body[expr] {
235 Expr::Literal(Bool(value)) => PatKind::LiteralBool { value },
236 _ => {
237 self.errors.push(PatternError::Unimplemented);
238 PatKind::Wild
239 }
240 }
241 }
242}
243
244pub(crate) trait PatternFoldable: Sized {
245 fn fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
246 self.super_fold_with(folder)
247 }
248
249 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self;
250}
251
252pub(crate) trait PatternFolder: Sized {
253 fn fold_pattern(&mut self, pattern: &Pat) -> Pat {
254 pattern.super_fold_with(self)
255 }
256
257 fn fold_pattern_kind(&mut self, kind: &PatKind) -> PatKind {
258 kind.super_fold_with(self)
259 }
260}
261
262impl<T: PatternFoldable> PatternFoldable for Box<T> {
263 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
264 let content: T = (**self).fold_with(folder);
265 Box::new(content)
266 }
267}
268
269impl<T: PatternFoldable> PatternFoldable for Vec<T> {
270 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
271 self.iter().map(|t| t.fold_with(folder)).collect()
272 }
273}
274
275impl<T: PatternFoldable> PatternFoldable for Option<T> {
276 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
277 self.as_ref().map(|t| t.fold_with(folder))
278 }
279}
280
281macro_rules! clone_impls {
282 ($($ty:ty),+) => {
283 $(
284 impl PatternFoldable for $ty {
285 fn super_fold_with<F: PatternFolder>(&self, _: &mut F) -> Self {
286 Clone::clone(self)
287 }
288 }
289 )+
290 }
291}
292
293clone_impls! { LocalFieldId, Ty, Substitution, EnumVariantId }
294
295impl PatternFoldable for FieldPat {
296 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
297 FieldPat { field: self.field.fold_with(folder), pattern: self.pattern.fold_with(folder) }
298 }
299}
300
301impl PatternFoldable for Pat {
302 fn fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
303 folder.fold_pattern(self)
304 }
305
306 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
307 Pat { ty: self.ty.fold_with(folder), kind: self.kind.fold_with(folder) }
308 }
309}
310
311impl PatternFoldable for PatKind {
312 fn fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
313 folder.fold_pattern_kind(self)
314 }
315
316 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
317 match self {
318 PatKind::Wild => PatKind::Wild,
319 PatKind::Binding { subpattern } => {
320 PatKind::Binding { subpattern: subpattern.fold_with(folder) }
321 }
322 PatKind::Variant { substs, enum_variant, subpatterns } => PatKind::Variant {
323 substs: substs.fold_with(folder),
324 enum_variant: enum_variant.fold_with(folder),
325 subpatterns: subpatterns.fold_with(folder),
326 },
327 PatKind::Leaf { subpatterns } => {
328 PatKind::Leaf { subpatterns: subpatterns.fold_with(folder) }
329 }
330 PatKind::Deref { subpattern } => {
331 PatKind::Deref { subpattern: subpattern.fold_with(folder) }
332 }
333 &PatKind::LiteralBool { value } => PatKind::LiteralBool { value },
334 PatKind::Or { pats } => PatKind::Or { pats: pats.fold_with(folder) },
335 }
336 }
337}
338
339#[cfg(test)]
340mod tests {
341 use crate::diagnostics::tests::check_diagnostics;
342
343 #[test]
344 fn empty_tuple() {
345 check_diagnostics(
346 r#"
347fn main() {
348 match () { }
349 //^^ Missing match arm
350 match (()) { }
351 //^^^^ Missing match arm
352
353 match () { _ => (), }
354 match () { () => (), }
355 match (()) { (()) => (), }
356}
357"#,
358 );
359 }
360
361 #[test]
362 fn tuple_of_two_empty_tuple() {
363 check_diagnostics(
364 r#"
365fn main() {
366 match ((), ()) { }
367 //^^^^^^^^ Missing match arm
368
369 match ((), ()) { ((), ()) => (), }
370}
371"#,
372 );
373 }
374
375 #[test]
376 fn boolean() {
377 check_diagnostics(
378 r#"
379fn test_main() {
380 match false { }
381 //^^^^^ Missing match arm
382 match false { true => (), }
383 //^^^^^ Missing match arm
384 match (false, true) {}
385 //^^^^^^^^^^^^^ Missing match arm
386 match (false, true) { (true, true) => (), }
387 //^^^^^^^^^^^^^ Missing match arm
388 match (false, true) {
389 //^^^^^^^^^^^^^ Missing match arm
390 (false, true) => (),
391 (false, false) => (),
392 (true, false) => (),
393 }
394 match (false, true) { (true, _x) => (), }
395 //^^^^^^^^^^^^^ Missing match arm
396
397 match false { true => (), false => (), }
398 match (false, true) {
399 (false, _) => (),
400 (true, false) => (),
401 (_, true) => (),
402 }
403 match (false, true) {
404 (true, true) => (),
405 (true, false) => (),
406 (false, true) => (),
407 (false, false) => (),
408 }
409 match (false, true) {
410 (true, _x) => (),
411 (false, true) => (),
412 (false, false) => (),
413 }
414 match (false, true, false) {
415 (false, ..) => (),
416 (true, ..) => (),
417 }
418 match (false, true, false) {
419 (.., false) => (),
420 (.., true) => (),
421 }
422 match (false, true, false) { (..) => (), }
423}
424"#,
425 );
426 }
427
428 #[test]
429 fn tuple_of_tuple_and_bools() {
430 check_diagnostics(
431 r#"
432fn main() {
433 match (false, ((), false)) {}
434 //^^^^^^^^^^^^^^^^^^^^ Missing match arm
435 match (false, ((), false)) { (true, ((), true)) => (), }
436 //^^^^^^^^^^^^^^^^^^^^ Missing match arm
437 match (false, ((), false)) { (true, _) => (), }
438 //^^^^^^^^^^^^^^^^^^^^ Missing match arm
439
440 match (false, ((), false)) {
441 (true, ((), true)) => (),
442 (true, ((), false)) => (),
443 (false, ((), true)) => (),
444 (false, ((), false)) => (),
445 }
446 match (false, ((), false)) {
447 (true, ((), true)) => (),
448 (true, ((), false)) => (),
449 (false, _) => (),
450 }
451}
452"#,
453 );
454 }
455
456 #[test]
457 fn enums() {
458 check_diagnostics(
459 r#"
460enum Either { A, B, }
461
462fn main() {
463 match Either::A { }
464 //^^^^^^^^^ Missing match arm
465 match Either::B { Either::A => (), }
466 //^^^^^^^^^ Missing match arm
467
468 match &Either::B {
469 //^^^^^^^^^^ Missing match arm
470 Either::A => (),
471 }
472
473 match Either::B {
474 Either::A => (), Either::B => (),
475 }
476 match &Either::B {
477 Either::A => (), Either::B => (),
478 }
479}
480"#,
481 );
482 }
483
484 #[test]
485 fn enum_containing_bool() {
486 check_diagnostics(
487 r#"
488enum Either { A(bool), B }
489
490fn main() {
491 match Either::B { }
492 //^^^^^^^^^ Missing match arm
493 match Either::B {
494 //^^^^^^^^^ Missing match arm
495 Either::A(true) => (), Either::B => ()
496 }
497
498 match Either::B {
499 Either::A(true) => (),
500 Either::A(false) => (),
501 Either::B => (),
502 }
503 match Either::B {
504 Either::B => (),
505 _ => (),
506 }
507 match Either::B {
508 Either::A(_) => (),
509 Either::B => (),
510 }
511
512}
513 "#,
514 );
515 }
516
517 #[test]
518 fn enum_different_sizes() {
519 check_diagnostics(
520 r#"
521enum Either { A(bool), B(bool, bool) }
522
523fn main() {
524 match Either::A(false) {
525 //^^^^^^^^^^^^^^^^ Missing match arm
526 Either::A(_) => (),
527 Either::B(false, _) => (),
528 }
529
530 match Either::A(false) {
531 Either::A(_) => (),
532 Either::B(true, _) => (),
533 Either::B(false, _) => (),
534 }
535 match Either::A(false) {
536 Either::A(true) | Either::A(false) => (),
537 Either::B(true, _) => (),
538 Either::B(false, _) => (),
539 }
540}
541"#,
542 );
543 }
544
545 #[test]
546 fn tuple_of_enum_no_diagnostic() {
547 check_diagnostics(
548 r#"
549enum Either { A(bool), B(bool, bool) }
550enum Either2 { C, D }
551
552fn main() {
553 match (Either::A(false), Either2::C) {
554 (Either::A(true), _) | (Either::A(false), _) => (),
555 (Either::B(true, _), Either2::C) => (),
556 (Either::B(false, _), Either2::C) => (),
557 (Either::B(_, _), Either2::D) => (),
558 }
559}
560"#,
561 );
562 }
563
564 #[test]
565 fn or_pattern_no_diagnostic() {
566 check_diagnostics(
567 r#"
568enum Either {A, B}
569
570fn main() {
571 match (Either::A, Either::B) {
572 (Either::A | Either::B, _) => (),
573 }
574}"#,
575 )
576 }
577
578 #[test]
579 fn mismatched_types() {
580 // Match statements with arms that don't match the
581 // expression pattern do not fire this diagnostic.
582 check_diagnostics(
583 r#"
584enum Either { A, B }
585enum Either2 { C, D }
586
587fn main() {
588 match Either::A {
589 Either2::C => (),
590 Either2::D => (),
591 }
592 match (true, false) {
593 (true, false, true) => (),
594 (true) => (),
595 }
596 match (0) { () => () }
597 match Unresolved::Bar { Unresolved::Baz => () }
598}
599 "#,
600 );
601 }
602
603 #[test]
604 fn malformed_match_arm_tuple_enum_missing_pattern() {
605 // We are testing to be sure we don't panic here when the match
606 // arm `Either::B` is missing its pattern.
607 check_diagnostics(
608 r#"
609enum Either { A, B(u32) }
610
611fn main() {
612 match Either::A {
613 Either::A => (),
614 Either::B() => (),
615 }
616}
617"#,
618 );
619 }
620
621 #[test]
622 fn expr_diverges() {
623 check_diagnostics(
624 r#"
625enum Either { A, B }
626
627fn main() {
628 match loop {} {
629 Either::A => (),
630 Either::B => (),
631 }
632 match loop {} {
633 Either::A => (),
634 }
635 match loop { break Foo::A } {
636 //^^^^^^^^^^^^^^^^^^^^^ Missing match arm
637 Either::A => (),
638 }
639 match loop { break Foo::A } {
640 Either::A => (),
641 Either::B => (),
642 }
643}
644"#,
645 );
646 }
647
648 #[test]
649 fn expr_partially_diverges() {
650 check_diagnostics(
651 r#"
652enum Either<T> { A(T), B }
653
654fn foo() -> Either<!> { Either::B }
655fn main() -> u32 {
656 match foo() {
657 Either::A(val) => val,
658 Either::B => 0,
659 }
660}
661"#,
662 );
663 }
664
665 #[test]
666 fn enum_record() {
667 check_diagnostics(
668 r#"
669enum Either { A { foo: bool }, B }
670
671fn main() {
672 let a = Either::A { foo: true };
673 match a { }
674 //^ Missing match arm
675 match a { Either::A { foo: true } => () }
676 //^ Missing match arm
677 match a {
678 Either::A { } => (),
679 //^^^^^^^^^ Missing structure fields:
680 // | - foo
681 Either::B => (),
682 }
683 match a {
684 //^ Missing match arm
685 Either::A { } => (),
686 } //^^^^^^^^^ Missing structure fields:
687 // | - foo
688
689 match a {
690 Either::A { foo: true } => (),
691 Either::A { foo: false } => (),
692 Either::B => (),
693 }
694 match a {
695 Either::A { foo: _ } => (),
696 Either::B => (),
697 }
698}
699"#,
700 );
701 }
702
703 #[test]
704 fn enum_record_fields_out_of_order() {
705 check_diagnostics(
706 r#"
707enum Either {
708 A { foo: bool, bar: () },
709 B,
710}
711
712fn main() {
713 let a = Either::A { foo: true, bar: () };
714 match a {
715 //^ Missing match arm
716 Either::A { bar: (), foo: false } => (),
717 Either::A { foo: true, bar: () } => (),
718 }
719
720 match a {
721 Either::A { bar: (), foo: false } => (),
722 Either::A { foo: true, bar: () } => (),
723 Either::B => (),
724 }
725}
726"#,
727 );
728 }
729
730 #[test]
731 fn enum_record_ellipsis() {
732 check_diagnostics(
733 r#"
734enum Either {
735 A { foo: bool, bar: bool },
736 B,
737}
738
739fn main() {
740 let a = Either::B;
741 match a {
742 //^ Missing match arm
743 Either::A { foo: true, .. } => (),
744 Either::B => (),
745 }
746 match a {
747 //^ Missing match arm
748 Either::A { .. } => (),
749 }
750
751 match a {
752 Either::A { foo: true, .. } => (),
753 Either::A { foo: false, .. } => (),
754 Either::B => (),
755 }
756
757 match a {
758 Either::A { .. } => (),
759 Either::B => (),
760 }
761}
762"#,
763 );
764 }
765
766 #[test]
767 fn enum_tuple_partial_ellipsis() {
768 check_diagnostics(
769 r#"
770enum Either {
771 A(bool, bool, bool, bool),
772 B,
773}
774
775fn main() {
776 match Either::B {
777 //^^^^^^^^^ Missing match arm
778 Either::A(true, .., true) => (),
779 Either::A(true, .., false) => (),
780 Either::A(false, .., false) => (),
781 Either::B => (),
782 }
783 match Either::B {
784 //^^^^^^^^^ Missing match arm
785 Either::A(true, .., true) => (),
786 Either::A(true, .., false) => (),
787 Either::A(.., true) => (),
788 Either::B => (),
789 }
790
791 match Either::B {
792 Either::A(true, .., true) => (),
793 Either::A(true, .., false) => (),
794 Either::A(false, .., true) => (),
795 Either::A(false, .., false) => (),
796 Either::B => (),
797 }
798 match Either::B {
799 Either::A(true, .., true) => (),
800 Either::A(true, .., false) => (),
801 Either::A(.., true) => (),
802 Either::A(.., false) => (),
803 Either::B => (),
804 }
805}
806"#,
807 );
808 }
809
810 #[test]
811 fn never() {
812 check_diagnostics(
813 r#"
814enum Never {}
815
816fn enum_(never: Never) {
817 match never {}
818}
819fn enum_ref(never: &Never) {
820 match never {}
821 //^^^^^ Missing match arm
822}
823fn bang(never: !) {
824 match never {}
825}
826"#,
827 );
828 }
829
830 #[test]
831 fn unknown_type() {
832 check_diagnostics(
833 r#"
834enum Option<T> { Some(T), None }
835
836fn main() {
837 // `Never` is deliberately not defined so that it's an uninferred type.
838 match Option::<Never>::None {
839 None => (),
840 Some(never) => match never {},
841 }
842}
843"#,
844 );
845 }
846
847 #[test]
848 fn tuple_of_bools_with_ellipsis_at_end_missing_arm() {
849 check_diagnostics(
850 r#"
851fn main() {
852 match (false, true, false) {
853 //^^^^^^^^^^^^^^^^^^^^ Missing match arm
854 (false, ..) => (),
855 }
856}"#,
857 );
858 }
859
860 #[test]
861 fn tuple_of_bools_with_ellipsis_at_beginning_missing_arm() {
862 check_diagnostics(
863 r#"
864fn main() {
865 match (false, true, false) {
866 //^^^^^^^^^^^^^^^^^^^^ Missing match arm
867 (.., false) => (),
868 }
869}"#,
870 );
871 }
872
873 #[test]
874 fn tuple_of_bools_with_ellipsis_in_middle_missing_arm() {
875 check_diagnostics(
876 r#"
877fn main() {
878 match (false, true, false) {
879 //^^^^^^^^^^^^^^^^^^^^ Missing match arm
880 (true, .., false) => (),
881 }
882}"#,
883 );
884 }
885
886 #[test]
887 fn record_struct() {
888 check_diagnostics(
889 r#"struct Foo { a: bool }
890fn main(f: Foo) {
891 match f {}
892 //^ Missing match arm
893 match f { Foo { a: true } => () }
894 //^ Missing match arm
895 match &f { Foo { a: true } => () }
896 //^^ Missing match arm
897 match f { Foo { a: _ } => () }
898 match f {
899 Foo { a: true } => (),
900 Foo { a: false } => (),
901 }
902 match &f {
903 Foo { a: true } => (),
904 Foo { a: false } => (),
905 }
906}
907"#,
908 );
909 }
910
911 #[test]
912 fn tuple_struct() {
913 check_diagnostics(
914 r#"struct Foo(bool);
915fn main(f: Foo) {
916 match f {}
917 //^ Missing match arm
918 match f { Foo(true) => () }
919 //^ Missing match arm
920 match f {
921 Foo(true) => (),
922 Foo(false) => (),
923 }
924}
925"#,
926 );
927 }
928
929 #[test]
930 fn unit_struct() {
931 check_diagnostics(
932 r#"struct Foo;
933fn main(f: Foo) {
934 match f {}
935 //^ Missing match arm
936 match f { Foo => () }
937}
938"#,
939 );
940 }
941
942 #[test]
943 fn record_struct_ellipsis() {
944 check_diagnostics(
945 r#"struct Foo { foo: bool, bar: bool }
946fn main(f: Foo) {
947 match f { Foo { foo: true, .. } => () }
948 //^ Missing match arm
949 match f {
950 //^ Missing match arm
951 Foo { foo: true, .. } => (),
952 Foo { bar: false, .. } => ()
953 }
954 match f { Foo { .. } => () }
955 match f {
956 Foo { foo: true, .. } => (),
957 Foo { foo: false, .. } => ()
958 }
959}
960"#,
961 );
962 }
963
964 #[test]
965 fn internal_or() {
966 check_diagnostics(
967 r#"
968fn main() {
969 enum Either { A(bool), B }
970 match Either::B {
971 //^^^^^^^^^ Missing match arm
972 Either::A(true | false) => (),
973 }
974}
975"#,
976 );
977 }
978
979 #[test]
980 fn no_panic_at_unimplemented_subpattern_type() {
981 check_diagnostics(
982 r#"
983struct S { a: char}
984fn main(v: S) {
985 match v { S{ a } => {} }
986 match v { S{ a: _x } => {} }
987 match v { S{ a: 'a' } => {} }
988 match v { S{..} => {} }
989 match v { _ => {} }
990 match v { }
991 //^ Missing match arm
992}
993"#,
994 );
995 }
996
997 #[test]
998 fn binding() {
999 check_diagnostics(
1000 r#"
1001fn main() {
1002 match true {
1003 _x @ true => {}
1004 false => {}
1005 }
1006 match true { _x @ true => {} }
1007 //^^^^ Missing match arm
1008}
1009"#,
1010 );
1011 }
1012
1013 mod false_negatives {
1014 //! The implementation of match checking here is a work in progress. As we roll this out, we
1015 //! prefer false negatives to false positives (ideally there would be no false positives). This
1016 //! test module should document known false negatives. Eventually we will have a complete
1017 //! implementation of match checking and this module will be empty.
1018 //!
1019 //! The reasons for documenting known false negatives:
1020 //!
1021 //! 1. It acts as a backlog of work that can be done to improve the behavior of the system.
1022 //! 2. It ensures the code doesn't panic when handling these cases.
1023 use super::*;
1024
1025 #[test]
1026 fn integers() {
1027 // We don't currently check integer exhaustiveness.
1028 check_diagnostics(
1029 r#"
1030fn main() {
1031 match 5 {
1032 10 => (),
1033 11..20 => (),
1034 }
1035}
1036"#,
1037 );
1038 }
1039 }
1040}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-04 21:16:22 +0000