aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty/src/diagnostics/match_check.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/hir_ty/src/diagnostics/match_check.rs')
-rw-r--r--crates/hir_ty/src/diagnostics/match_check.rs1304
1 files changed, 530 insertions, 774 deletions
diff --git a/crates/hir_ty/src/diagnostics/match_check.rs b/crates/hir_ty/src/diagnostics/match_check.rs
index e8dd669bf..a9a99f57a 100644
--- a/crates/hir_ty/src/diagnostics/match_check.rs
+++ b/crates/hir_ty/src/diagnostics/match_check.rs
@@ -1,871 +1,416 @@
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 27 MissingField,
279 /// a pattern or expression. 28 ExtraFields,
280 Unknown,
281} 29}
282 30
283/// The return type of `is_useful` is either an indication of usefulness 31#[derive(Clone, Debug, PartialEq)]
284/// of the match arm, or an error in the case the match statement 32pub(crate) struct FieldPat {
285/// is made up of types for which exhaustiveness checking is currently 33 pub(crate) field: LocalFieldId,
286/// not completely implemented. 34 pub(crate) pattern: Pat,
287/// 35}
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 36
292#[derive(Debug)] 37#[derive(Clone, Debug, PartialEq)]
293/// A row in a Matrix. 38pub(crate) struct Pat {
294/// 39 pub(crate) ty: Ty,
295/// This type is modeled from the struct of the same name in `rustc`. 40 pub(crate) kind: Box<PatKind>,
296pub(super) struct PatStack(PatStackInner); 41}
297type PatStackInner = SmallVec<[PatIdOrWild; 2]>;
298 42
299impl PatStack { 43impl Pat {
300 pub(super) fn from_pattern(pat_id: PatId) -> PatStack { 44 pub(crate) fn wildcard_from_ty(ty: Ty) -> Self {
301 Self(smallvec!(pat_id.into())) 45 Pat { ty, kind: Box::new(PatKind::Wild) }
302 } 46 }
47}
303 48
304 pub(super) fn from_wild() -> PatStack { 49/// Close relative to `rustc_mir_build::thir::pattern::PatKind`
305 Self(smallvec!(PatIdOrWild::Wild)) 50#[derive(Clone, Debug, PartialEq)]
306 } 51pub(crate) enum PatKind {
52 Wild,
307 53
308 fn from_slice(slice: &[PatIdOrWild]) -> PatStack { 54 /// `x`, `ref x`, `x @ P`, etc.
309 Self(SmallVec::from_slice(slice)) 55 Binding {
310 } 56 subpattern: Option<Pat>,
57 },
58
59 /// `Foo(...)` or `Foo{...}` or `Foo`, where `Foo` is a variant name from an ADT with
60 /// multiple variants.
61 Variant {
62 substs: Substitution,
63 enum_variant: EnumVariantId,
64 subpatterns: Vec<FieldPat>,
65 },
66
67 /// `(...)`, `Foo(...)`, `Foo{...}`, or `Foo`, where `Foo` is a variant name from an ADT with
68 /// a single variant.
69 Leaf {
70 subpatterns: Vec<FieldPat>,
71 },
72
73 /// `box P`, `&P`, `&mut P`, etc.
74 Deref {
75 subpattern: Pat,
76 },
77
78 // FIXME: for now, only bool literals are implemented
79 LiteralBool {
80 value: bool,
81 },
82
83 /// An or-pattern, e.g. `p | q`.
84 /// Invariant: `pats.len() >= 2`.
85 Or {
86 pats: Vec<Pat>,
87 },
88}
311 89
312 fn from_vec(v: PatStackInner) -> PatStack { 90pub(crate) struct PatCtxt<'a> {
313 Self(v) 91 db: &'a dyn HirDatabase,
314 } 92 infer: &'a InferenceResult,
93 body: &'a Body,
94 pub(crate) errors: Vec<PatternError>,
95}
315 96
316 fn get_head(&self) -> Option<PatIdOrWild> { 97impl<'a> PatCtxt<'a> {
317 self.0.first().copied() 98 pub(crate) fn new(db: &'a dyn HirDatabase, infer: &'a InferenceResult, body: &'a Body) -> Self {
99 Self { db, infer, body, errors: Vec::new() }
318 } 100 }
319 101
320 fn tail(&self) -> &[PatIdOrWild] { 102 pub(crate) fn lower_pattern(&mut self, pat: hir_def::expr::PatId) -> Pat {
321 self.0.get(1..).unwrap_or(&[]) 103 // FIXME: implement pattern adjustments (implicit pattern dereference; "RFC 2005-match-ergonomics")
104 // More info https://github.com/rust-lang/rust/issues/42640#issuecomment-313535089
105 let unadjusted_pat = self.lower_pattern_unadjusted(pat);
106 unadjusted_pat
322 } 107 }
323 108
324 fn to_tail(&self) -> PatStack { 109 fn lower_pattern_unadjusted(&mut self, pat: hir_def::expr::PatId) -> Pat {
325 Self::from_slice(self.tail()) 110 let mut ty = &self.infer[pat];
326 } 111 let variant = self.infer.variant_resolution_for_pat(pat);
327 112
328 fn replace_head_with<I, T>(&self, pats: I) -> PatStack 113 let kind = match self.body[pat] {
329 where 114 hir_def::expr::Pat::Wild => PatKind::Wild,
330 I: Iterator<Item = T>,
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 115
343 /// Computes `D(self)`. 116 hir_def::expr::Pat::Lit(expr) => self.lower_lit(expr),
344 ///
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 117
354 /// Computes `S(constructor, self)`. 118 hir_def::expr::Pat::Path(ref path) => {
355 /// 119 return self.lower_path(pat, path);
356 /// See the module docs and the associated documentation in rustc for details. 120 }
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 121
367 let head_pat = head.as_pat(cx); 122 hir_def::expr::Pat::Tuple { ref args, ellipsis } => {
368 let result = match (head_pat, constructor) { 123 let arity = match *ty.kind(&Interner) {
369 (Pat::Tuple { args: pat_ids, ellipsis }, &Constructor::Tuple { arity }) => { 124 TyKind::Tuple(arity, _) => arity,
370 if let Some(ellipsis) = ellipsis { 125 _ => panic!("unexpected type for tuple pattern: {:?}", ty),
371 let (pre, post) = pat_ids.split_at(ellipsis); 126 };
372 let n_wild_pats = arity.saturating_sub(pat_ids.len()); 127 let subpatterns = self.lower_tuple_subpats(args, arity, ellipsis);
373 let pre_iter = pre.iter().map(Into::into); 128 PatKind::Leaf { subpatterns }
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 } 129 }
381 (Pat::Lit(lit_expr), Constructor::Bool(constructor_val)) => { 130
382 match cx.body.exprs[lit_expr] { 131 hir_def::expr::Pat::Bind { subpat, .. } => {
383 Expr::Literal(Literal::Bool(pat_val)) if *constructor_val == pat_val => { 132 if let TyKind::Ref(.., rty) = ty.kind(&Interner) {
384 Some(self.to_tail()) 133 ty = rty;
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 } 134 }
135 PatKind::Binding { subpattern: self.lower_opt_pattern(subpat) }
392 } 136 }
393 (Pat::Wild, constructor) => Some(self.expand_wildcard(cx, constructor)?), 137
394 (Pat::Path(_), constructor) => { 138 hir_def::expr::Pat::TupleStruct { ref args, ellipsis, .. } if variant.is_some() => {
395 // unit enum variants become `Pat::Path` 139 let expected_len = variant.unwrap().variant_data(self.db.upcast()).fields().len();
396 let pat_id = head.as_id().expect("we know this isn't a wild"); 140 let subpatterns = self.lower_tuple_subpats(args, expected_len, ellipsis);
397 let variant_id: VariantId = match constructor { 141 self.lower_variant_or_leaf(pat, ty, subpatterns)
398 &Constructor::Enum(e) => e.into(),
399 &Constructor::Struct(s) => s.into(),
400 _ => return Err(MatchCheckErr::NotImplemented),
401 };
402 if Some(variant_id) != cx.infer.variant_resolution_for_pat(pat_id) {
403 None
404 } else {
405 Some(self.to_tail())
406 }
407 } 142 }
408 (Pat::TupleStruct { args: ref pat_ids, ellipsis, .. }, constructor) => { 143
409 let pat_id = head.as_id().expect("we know this isn't a wild"); 144 hir_def::expr::Pat::Record { ref args, .. } if variant.is_some() => {
410 let variant_id: VariantId = match constructor { 145 let variant_data = variant.unwrap().variant_data(self.db.upcast());
411 &Constructor::Enum(e) => e.into(), 146 let subpatterns = args
412 &Constructor::Struct(s) => s.into(), 147 .iter()
413 _ => return Err(MatchCheckErr::MalformedMatchArm), 148 .map(|field| {
414 }; 149 // XXX(iDawer): field lookup is inefficient
415 if Some(variant_id) != cx.infer.variant_resolution_for_pat(pat_id) { 150 variant_data.field(&field.name).map(|lfield_id| FieldPat {
416 None 151 field: lfield_id,
417 } else { 152 pattern: self.lower_pattern(field.pat),
418 let constructor_arity = constructor.arity(cx)?; 153 })
419 if let Some(ellipsis_position) = ellipsis { 154 })
420 // If there are ellipsis in the pattern, the ellipsis must take the place 155 .collect();
421 // of at least one sub-pattern, so `pat_ids` should be smaller than the 156 match subpatterns {
422 // constructor arity. 157 Some(subpatterns) => self.lower_variant_or_leaf(pat, ty, subpatterns),
423 if pat_ids.len() < constructor_arity { 158 None => {
424 let mut new_patterns: Vec<PatIdOrWild> = vec![]; 159 self.errors.push(PatternError::MissingField);
425 160 PatKind::Wild
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 } 161 }
451 } 162 }
452 } 163 }
453 (Pat::Record { args: ref arg_patterns, .. }, constructor) => { 164 hir_def::expr::Pat::TupleStruct { .. } | hir_def::expr::Pat::Record { .. } => {
454 let pat_id = head.as_id().expect("we know this isn't a wild"); 165 self.errors.push(PatternError::UnresolvedVariant);
455 let (variant_id, variant_data) = match constructor { 166 PatKind::Wild
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 } 167 }
491 (Pat::Or(_), _) => return Err(MatchCheckErr::NotImplemented),
492 (_, _) => return Err(MatchCheckErr::NotImplemented),
493 };
494 168
495 Ok(result) 169 hir_def::expr::Pat::Or(ref pats) => PatKind::Or { pats: self.lower_patterns(pats) },
496 }
497
498 /// A special case of `specialize_constructor` where the head of the pattern stack
499 /// is a Wild pattern.
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 170
514 let mut patterns: PatStackInner = smallvec![]; 171 _ => {
172 self.errors.push(PatternError::Unimplemented);
173 PatKind::Wild
174 }
175 };
515 176
516 for _ in 0..constructor.arity(cx)? { 177 Pat { ty: ty.clone(), kind: Box::new(kind) }
517 patterns.push(PatIdOrWild::Wild); 178 }
518 }
519 179
520 for pat in &self.0[1..] { 180 fn lower_tuple_subpats(
521 patterns.push(*pat); 181 &mut self,
182 pats: &[hir_def::expr::PatId],
183 expected_len: usize,
184 ellipsis: Option<usize>,
185 ) -> Vec<FieldPat> {
186 if pats.len() > expected_len {
187 self.errors.push(PatternError::ExtraFields);
188 return Vec::new();
522 } 189 }
523 190
524 Ok(PatStack::from_vec(patterns)) 191 pats.iter()
192 .enumerate_and_adjust(expected_len, ellipsis)
193 .map(|(i, &subpattern)| FieldPat {
194 field: LocalFieldId::from_raw((i as u32).into()),
195 pattern: self.lower_pattern(subpattern),
196 })
197 .collect()
525 } 198 }
526}
527 199
528/// A collection of PatStack. 200 fn lower_patterns(&mut self, pats: &[hir_def::expr::PatId]) -> Vec<Pat> {
529/// 201 pats.iter().map(|&p| self.lower_pattern(p)).collect()
530/// This type is modeled from the struct of the same name in `rustc`. 202 }
531pub(super) struct Matrix(Vec<PatStack>);
532 203
533impl Matrix { 204 fn lower_opt_pattern(&mut self, pat: Option<hir_def::expr::PatId>) -> Option<Pat> {
534 pub(super) fn empty() -> Self { 205 pat.map(|p| self.lower_pattern(p))
535 Self(vec![])
536 } 206 }
537 207
538 pub(super) fn push(&mut self, cx: &MatchCheckCtx, row: PatStack) { 208 fn lower_variant_or_leaf(
539 if let Some(Pat::Or(pat_ids)) = row.get_head().map(|pat_id| pat_id.as_pat(cx)) { 209 &mut self,
540 // Or patterns are expanded here 210 pat: hir_def::expr::PatId,
541 for pat_id in pat_ids { 211 ty: &Ty,
542 self.0.push(row.replace_head_with([pat_id].iter())); 212 subpatterns: Vec<FieldPat>,
213 ) -> PatKind {
214 let kind = match self.infer.variant_resolution_for_pat(pat) {
215 Some(variant_id) => {
216 if let VariantId::EnumVariantId(enum_variant) = variant_id {
217 let substs = match ty.kind(&Interner) {
218 TyKind::Adt(_, substs) | TyKind::FnDef(_, substs) => substs.clone(),
219 TyKind::Error => {
220 return PatKind::Wild;
221 }
222 _ => panic!("inappropriate type for def: {:?}", ty),
223 };
224 PatKind::Variant { substs, enum_variant, subpatterns }
225 } else {
226 PatKind::Leaf { subpatterns }
227 }
543 } 228 }
544 } else { 229 None => {
545 self.0.push(row); 230 self.errors.push(PatternError::UnresolvedVariant);
546 } 231 PatKind::Wild
232 }
233 };
234 kind
547 } 235 }
548 236
549 fn is_empty(&self) -> bool { 237 fn lower_path(&mut self, pat: hir_def::expr::PatId, _path: &hir_def::path::Path) -> Pat {
550 self.0.is_empty() 238 let ty = &self.infer[pat];
551 }
552 239
553 fn heads(&self) -> Vec<PatIdOrWild> { 240 let pat_from_kind = |kind| Pat { ty: ty.clone(), kind: Box::new(kind) };
554 self.0.iter().flat_map(|p| p.get_head()).collect()
555 }
556 241
557 /// Computes `D(self)` for each contained PatStack. 242 match self.infer.variant_resolution_for_pat(pat) {
558 /// 243 Some(_) => pat_from_kind(self.lower_variant_or_leaf(pat, ty, Vec::new())),
559 /// See the module docs and the associated documentation in rustc for details. 244 None => {
560 fn specialize_wildcard(&self, cx: &MatchCheckCtx) -> Self { 245 self.errors.push(PatternError::UnresolvedVariant);
561 Self::collect(cx, self.0.iter().filter_map(|r| r.specialize_wildcard(cx))) 246 pat_from_kind(PatKind::Wild)
247 }
248 }
562 } 249 }
563 250
564 /// Computes `S(constructor, self)` for each contained PatStack. 251 fn lower_lit(&mut self, expr: hir_def::expr::ExprId) -> PatKind {
565 /// 252 use hir_def::expr::{Expr, Literal::Bool};
566 /// See the module docs and the associated documentation in rustc for details. 253
567 fn specialize_constructor( 254 match self.body[expr] {
568 &self, 255 Expr::Literal(Bool(value)) => PatKind::LiteralBool { value },
569 cx: &MatchCheckCtx, 256 _ => {
570 constructor: &Constructor, 257 self.errors.push(PatternError::Unimplemented);
571 ) -> MatchCheckResult<Self> { 258 PatKind::Wild
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 } 259 }
577 } 260 }
261 }
262}
578 263
579 Ok(new_matrix) 264pub(crate) trait PatternFoldable: Sized {
265 fn fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
266 self.super_fold_with(folder)
580 } 267 }
581 268
582 fn collect<T: IntoIterator<Item = PatStack>>(cx: &MatchCheckCtx, iter: T) -> Self { 269 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self;
583 let mut matrix = Matrix::empty(); 270}
584 271
585 for pat in iter { 272pub(crate) trait PatternFolder: Sized {
586 // using push ensures we expand or-patterns 273 fn fold_pattern(&mut self, pattern: &Pat) -> Pat {
587 matrix.push(cx, pat); 274 pattern.super_fold_with(self)
588 } 275 }
589 276
590 matrix 277 fn fold_pattern_kind(&mut self, kind: &PatKind) -> PatKind {
278 kind.super_fold_with(self)
591 } 279 }
592} 280}
593 281
594#[derive(Clone, Debug, PartialEq)] 282impl<T: PatternFoldable> PatternFoldable for Box<T> {
595/// An indication of the usefulness of a given match arm, where 283 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
596/// usefulness is defined as matching some patterns which were 284 let content: T = (**self).fold_with(folder);
597/// not matched by an prior match arms. 285 Box::new(content)
598/// 286 }
599/// We may eventually need an `Unknown` variant here.
600pub(super) enum Usefulness {
601 Useful,
602 NotUseful,
603} 287}
604 288
605pub(super) struct MatchCheckCtx<'a> { 289impl<T: PatternFoldable> PatternFoldable for Vec<T> {
606 pub(super) match_expr: Idx<Expr>, 290 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
607 pub(super) body: Arc<Body>, 291 self.iter().map(|t| t.fold_with(folder)).collect()
608 pub(super) infer: Arc<InferenceResult>, 292 }
609 pub(super) db: &'a dyn HirDatabase,
610} 293}
611 294
612/// Given a set of patterns `matrix`, and pattern to consider `v`, determines 295impl<T: PatternFoldable> PatternFoldable for Option<T> {
613/// whether `v` is useful. A pattern is useful if it covers cases which were 296 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
614/// not previously covered. 297 self.as_ref().map(|t| t.fold_with(folder))
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 } 298 }
299}
638 300
639 let head = match v.get_head() { 301macro_rules! clone_impls {
640 Some(head) => head, 302 ($($ty:ty),+) => {
641 None => { 303 $(
642 let result = if matrix.is_empty() { Usefulness::Useful } else { Usefulness::NotUseful }; 304 impl PatternFoldable for $ty {
643 305 fn super_fold_with<F: PatternFolder>(&self, _: &mut F) -> Self {
644 return Ok(result); 306 Clone::clone(self)
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 } 307 }
660 } 308 }
661 }); 309 )+
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 } 310 }
311}
671 312
672 if let Some(constructor) = pat_constructor(cx, head)? { 313clone_impls! { LocalFieldId, Ty, Substitution, EnumVariantId }
673 let matrix = matrix.specialize_constructor(&cx, &constructor)?;
674 let v = v
675 .specialize_constructor(&cx, &constructor)?
676 .expect("we know this can't fail because we get the constructor from `v.head()` above");
677
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 314
718 if found_unimplemented { 315impl PatternFoldable for FieldPat {
719 Err(MatchCheckErr::NotImplemented) 316 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
720 } else { 317 FieldPat { field: self.field.fold_with(folder), pattern: self.pattern.fold_with(folder) }
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
731 is_useful(&cx, &matrix, &v)
732 }
733 }
734 } 318 }
735} 319}
736 320
737#[derive(Debug, Clone, Copy)] 321impl PatternFoldable for Pat {
738/// Similar to TypeCtor, but includes additional information about the specific 322 fn fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
739/// value being instantiated. For example, TypeCtor::Bool doesn't contain the 323 folder.fold_pattern(self)
740/// boolean value. 324 }
741enum Constructor {
742 Bool(bool),
743 Tuple { arity: usize },
744 Enum(EnumVariantId),
745 Struct(StructId),
746}
747 325
748impl Constructor { 326 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
749 fn arity(&self, cx: &MatchCheckCtx) -> MatchCheckResult<usize> { 327 Pat { ty: self.ty.fold_with(folder), kind: self.kind.fold_with(folder) }
750 let arity = match self { 328 }
751 Constructor::Bool(_) => 0, 329}
752 Constructor::Tuple { arity } => *arity,
753 Constructor::Enum(e) => {
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 }
759 }
760 &Constructor::Struct(s) => match cx.db.struct_data(s).variant_data.as_ref() {
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 330
767 Ok(arity) 331impl PatternFoldable for PatKind {
332 fn fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
333 folder.fold_pattern_kind(self)
768 } 334 }
769 335
770 fn all_constructors(&self, cx: &MatchCheckCtx) -> Vec<Constructor> { 336 fn super_fold_with<F: PatternFolder>(&self, folder: &mut F) -> Self {
771 match self { 337 match self {
772 Constructor::Bool(_) => vec![Constructor::Bool(true), Constructor::Bool(false)], 338 PatKind::Wild => PatKind::Wild,
773 Constructor::Tuple { .. } | Constructor::Struct(_) => vec![*self], 339 PatKind::Binding { subpattern } => {
774 Constructor::Enum(e) => cx 340 PatKind::Binding { subpattern: subpattern.fold_with(folder) }
775 .db 341 }
776 .enum_data(e.parent) 342 PatKind::Variant { substs, enum_variant, subpatterns } => PatKind::Variant {
777 .variants 343 substs: substs.fold_with(folder),
778 .iter() 344 enum_variant: enum_variant.fold_with(folder),
779 .map(|(local_id, _)| { 345 subpatterns: subpatterns.fold_with(folder),
780 Constructor::Enum(EnumVariantId { parent: e.parent, local_id }) 346 },
781 }) 347 PatKind::Leaf { subpatterns } => {
782 .collect(), 348 PatKind::Leaf { subpatterns: subpatterns.fold_with(folder) }
349 }
350 PatKind::Deref { subpattern } => {
351 PatKind::Deref { subpattern: subpattern.fold_with(folder) }
352 }
353 &PatKind::LiteralBool { value } => PatKind::LiteralBool { value },
354 PatKind::Or { pats } => PatKind::Or { pats: pats.fold_with(folder) },
783 } 355 }
784 } 356 }
785} 357}
786 358
787/// Returns the constructor for the given pattern. Should only return None 359#[cfg(test)]
788/// in the case of a Wild pattern. 360pub(super) mod tests {
789fn pat_constructor(cx: &MatchCheckCtx, pat: PatIdOrWild) -> MatchCheckResult<Option<Constructor>> { 361 mod report {
790 let res = match pat.as_pat(cx) { 362 use std::any::Any;
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 363
820 Ok(res) 364 use hir_def::{expr::PatId, DefWithBodyId};
821} 365 use hir_expand::{HirFileId, InFile};
366 use syntax::SyntaxNodePtr;
822 367
823fn all_constructors_covered( 368 use crate::{
824 cx: &MatchCheckCtx, 369 db::HirDatabase,
825 constructor: &Constructor, 370 diagnostics_sink::{Diagnostic, DiagnosticCode, DiagnosticSink},
826 used_constructors: &[Constructor], 371 };
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 372
840 let covers_true = 373 /// In tests, match check bails out loudly.
841 used_constructors.iter().any(|c| matches!(c, Constructor::Bool(true))); 374 /// This helps to catch incorrect tests that pass due to false negatives.
842 let covers_false = 375 pub(crate) fn report_bail_out(
843 used_constructors.iter().any(|c| matches!(c, Constructor::Bool(false))); 376 db: &dyn HirDatabase,
377 def: DefWithBodyId,
378 pat: PatId,
379 sink: &mut DiagnosticSink,
380 ) {
381 let (_, source_map) = db.body_with_source_map(def);
382 if let Ok(source_ptr) = source_map.pat_syntax(pat) {
383 let pat_syntax_ptr = source_ptr.value.either(Into::into, Into::into);
384 sink.push(BailedOut { file: source_ptr.file_id, pat_syntax_ptr });
385 }
386 }
844 387
845 covers_true && covers_false 388 #[derive(Debug)]
389 struct BailedOut {
390 file: HirFileId,
391 pat_syntax_ptr: SyntaxNodePtr,
846 } 392 }
847 Constructor::Enum(e) => cx.db.enum_data(e.parent).variants.iter().all(|(id, _)| {
848 for constructor in used_constructors {
849 if let Constructor::Enum(e) = constructor {
850 if id == e.local_id {
851 return true;
852 }
853 }
854 }
855 393
856 false 394 impl Diagnostic for BailedOut {
857 }), 395 fn code(&self) -> DiagnosticCode {
858 &Constructor::Struct(s) => used_constructors.iter().any(|constructor| match constructor { 396 DiagnosticCode("internal:match-check-bailed-out")
859 &Constructor::Struct(sid) => sid == s, 397 }
860 _ => false, 398 fn message(&self) -> String {
861 }), 399 format!("Internal: match check bailed out")
400 }
401 fn display_source(&self) -> InFile<SyntaxNodePtr> {
402 InFile { file_id: self.file, value: self.pat_syntax_ptr.clone() }
403 }
404 fn as_any(&self) -> &(dyn Any + Send + 'static) {
405 self
406 }
407 }
862 } 408 }
863}
864 409
865#[cfg(test)]
866mod tests {
867 use crate::diagnostics::tests::check_diagnostics; 410 use crate::diagnostics::tests::check_diagnostics;
868 411
412 pub(crate) use self::report::report_bail_out;
413
869 #[test] 414 #[test]
870 fn empty_tuple() { 415 fn empty_tuple() {
871 check_diagnostics( 416 check_diagnostics(
@@ -1113,14 +658,18 @@ enum Either2 { C, D }
1113fn main() { 658fn main() {
1114 match Either::A { 659 match Either::A {
1115 Either2::C => (), 660 Either2::C => (),
661 // ^^^^^^^^^^ Internal: match check bailed out
1116 Either2::D => (), 662 Either2::D => (),
1117 } 663 }
1118 match (true, false) { 664 match (true, false) {
1119 (true, false, true) => (), 665 (true, false, true) => (),
666 // ^^^^^^^^^^^^^^^^^^^ Internal: match check bailed out
1120 (true) => (), 667 (true) => (),
1121 } 668 }
1122 match (true, false) { (true,) => {} } 669 match (true, false) { (true,) => {} }
670 // ^^^^^^^ Internal: match check bailed out
1123 match (0) { () => () } 671 match (0) { () => () }
672 // ^^ Internal: match check bailed out
1124 match Unresolved::Bar { Unresolved::Baz => () } 673 match Unresolved::Bar { Unresolved::Baz => () }
1125} 674}
1126 "#, 675 "#,
@@ -1133,7 +682,9 @@ fn main() {
1133 r#" 682 r#"
1134fn main() { 683fn main() {
1135 match false { true | () => {} } 684 match false { true | () => {} }
685 // ^^^^^^^^^ Internal: match check bailed out
1136 match (false,) { (true | (),) => {} } 686 match (false,) { (true | (),) => {} }
687 // ^^^^^^^^^^^^ Internal: match check bailed out
1137} 688}
1138"#, 689"#,
1139 ); 690 );
@@ -1158,6 +709,25 @@ fn main() {
1158 } 709 }
1159 710
1160 #[test] 711 #[test]
712 fn malformed_match_arm_extra_fields() {
713 check_diagnostics(
714 r#"
715enum A { B(isize, isize), C }
716fn main() {
717 match A::B(1, 2) {
718 A::B(_, _, _) => (),
719 // ^^^^^^^^^^^^^ Internal: match check bailed out
720 }
721 match A::B(1, 2) {
722 A::C(_) => (),
723 // ^^^^^^^ Internal: match check bailed out
724 }
725}
726"#,
727 );
728 }
729
730 #[test]
1161 fn expr_diverges() { 731 fn expr_diverges() {
1162 check_diagnostics( 732 check_diagnostics(
1163 r#" 733 r#"
@@ -1166,10 +736,12 @@ enum Either { A, B }
1166fn main() { 736fn main() {
1167 match loop {} { 737 match loop {} {
1168 Either::A => (), 738 Either::A => (),
739 // ^^^^^^^^^ Internal: match check bailed out
1169 Either::B => (), 740 Either::B => (),
1170 } 741 }
1171 match loop {} { 742 match loop {} {
1172 Either::A => (), 743 Either::A => (),
744 // ^^^^^^^^^ Internal: match check bailed out
1173 } 745 }
1174 match loop { break Foo::A } { 746 match loop { break Foo::A } {
1175 //^^^^^^^^^^^^^^^^^^^^^ Missing match arm 747 //^^^^^^^^^^^^^^^^^^^^^ Missing match arm
@@ -1357,6 +929,7 @@ fn enum_(never: Never) {
1357} 929}
1358fn enum_ref(never: &Never) { 930fn enum_ref(never: &Never) {
1359 match never {} 931 match never {}
932 //^^^^^ Missing match arm
1360} 933}
1361fn bang(never: !) { 934fn bang(never: !) {
1362 match never {} 935 match never {}
@@ -1376,6 +949,11 @@ fn main() {
1376 match Option::<Never>::None { 949 match Option::<Never>::None {
1377 None => (), 950 None => (),
1378 Some(never) => match never {}, 951 Some(never) => match never {},
952 // ^^^^^^^^^^^ Internal: match check bailed out
953 }
954 match Option::<Never>::None {
955 //^^^^^^^^^^^^^^^^^^^^^ Missing match arm
956 Option::Some(_never) => {},
1379 } 957 }
1380} 958}
1381"#, 959"#,
@@ -1513,6 +1091,151 @@ fn main() {
1513"#, 1091"#,
1514 ); 1092 );
1515 } 1093 }
1094
1095 #[test]
1096 fn no_panic_at_unimplemented_subpattern_type() {
1097 check_diagnostics(
1098 r#"
1099struct S { a: char}
1100fn main(v: S) {
1101 match v { S{ a } => {} }
1102 match v { S{ a: _x } => {} }
1103 match v { S{ a: 'a' } => {} }
1104 //^^^^^^^^^^^ Internal: match check bailed out
1105 match v { S{..} => {} }
1106 match v { _ => {} }
1107 match v { }
1108 //^ Missing match arm
1109}
1110"#,
1111 );
1112 }
1113
1114 #[test]
1115 fn binding() {
1116 check_diagnostics(
1117 r#"
1118fn main() {
1119 match true {
1120 _x @ true => {}
1121 false => {}
1122 }
1123 match true { _x @ true => {} }
1124 //^^^^ Missing match arm
1125}
1126"#,
1127 );
1128 }
1129
1130 #[test]
1131 fn binding_ref_has_correct_type() {
1132 // Asserts `PatKind::Binding(ref _x): bool`, not &bool.
1133 // If that's not true match checking will panic with "incompatible constructors"
1134 // FIXME: make facilities to test this directly like `tests::check_infer(..)`
1135 check_diagnostics(
1136 r#"
1137enum Foo { A }
1138fn main() {
1139 // FIXME: this should not bail out but current behavior is such as the old algorithm.
1140 // ExprValidator::validate_match(..) checks types of top level patterns incorrecly.
1141 match Foo::A {
1142 ref _x => {}
1143 // ^^^^^^ Internal: match check bailed out
1144 Foo::A => {}
1145 }
1146 match (true,) {
1147 (ref _x,) => {}
1148 (true,) => {}
1149 }
1150}
1151"#,
1152 );
1153 }
1154
1155 #[test]
1156 fn enum_non_exhaustive() {
1157 check_diagnostics(
1158 r#"
1159//- /lib.rs crate:lib
1160#[non_exhaustive]
1161pub enum E { A, B }
1162fn _local() {
1163 match E::A { _ => {} }
1164 match E::A {
1165 E::A => {}
1166 E::B => {}
1167 }
1168 match E::A {
1169 E::A | E::B => {}
1170 }
1171}
1172
1173//- /main.rs crate:main deps:lib
1174use lib::E;
1175fn main() {
1176 match E::A { _ => {} }
1177 match E::A {
1178 //^^^^ Missing match arm
1179 E::A => {}
1180 E::B => {}
1181 }
1182 match E::A {
1183 //^^^^ Missing match arm
1184 E::A | E::B => {}
1185 }
1186}
1187"#,
1188 );
1189 }
1190
1191 #[test]
1192 fn match_guard() {
1193 check_diagnostics(
1194 r#"
1195fn main() {
1196 match true {
1197 true if false => {}
1198 true => {}
1199 false => {}
1200 }
1201 match true {
1202 //^^^^ Missing match arm
1203 true if false => {}
1204 false => {}
1205}
1206"#,
1207 );
1208 }
1209
1210 #[test]
1211 fn pattern_type_is_of_substitution() {
1212 cov_mark::check!(match_check_wildcard_expanded_to_substitutions);
1213 check_diagnostics(
1214 r#"
1215struct Foo<T>(T);
1216struct Bar;
1217fn main() {
1218 match Foo(Bar) {
1219 _ | Foo(Bar) => {}
1220 }
1221}
1222"#,
1223 );
1224 }
1225
1226 #[test]
1227 fn record_struct_no_such_field() {
1228 check_diagnostics(
1229 r#"
1230struct Foo { }
1231fn main(f: Foo) {
1232 match f { Foo { bar } => () }
1233 // ^^^^^^^^^^^ Internal: match check bailed out
1234}
1235"#,
1236 );
1237 }
1238
1516 mod false_negatives { 1239 mod false_negatives {
1517 //! The implementation of match checking here is a work in progress. As we roll this out, we 1240 //! The implementation of match checking here is a work in progress. As we roll this out, we
1518 //! prefer false negatives to false positives (ideally there would be no false positives). This 1241 //! prefer false negatives to false positives (ideally there would be no false positives). This
@@ -1533,11 +1256,44 @@ fn main() {
1533fn main() { 1256fn main() {
1534 match 5 { 1257 match 5 {
1535 10 => (), 1258 10 => (),
1259 // ^^ Internal: match check bailed out
1536 11..20 => (), 1260 11..20 => (),
1537 } 1261 }
1538} 1262}
1539"#, 1263"#,
1540 ); 1264 );
1541 } 1265 }
1266
1267 #[test]
1268 fn reference_patterns_at_top_level() {
1269 check_diagnostics(
1270 r#"
1271fn main() {
1272 match &false {
1273 &true => {}
1274 // ^^^^^ Internal: match check bailed out
1275 }
1276}
1277 "#,
1278 );
1279 }
1280
1281 #[test]
1282 fn reference_patterns_in_fields() {
1283 check_diagnostics(
1284 r#"
1285fn main() {
1286 match (&false,) {
1287 (true,) => {}
1288 // ^^^^^^^ Internal: match check bailed out
1289 }
1290 match (&false,) {
1291 (&true,) => {}
1292 // ^^^^^^^^ Internal: match check bailed out
1293 }
1294}
1295 "#,
1296 );
1297 }
1542 } 1298 }
1543} 1299}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-02 22:07:56 +0100