aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty/src/diagnostics/match_check.rs
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/diagnostics/match_check.rs
parent894b4c64ffdb280a38c1ea2e9be145ca308965fd (diff)
Replace the old match checking algorithm
Diffstat (limited to 'crates/hir_ty/src/diagnostics/match_check.rs')
-rw-r--r--crates/hir_ty/src/diagnostics/match_check.rs1077
1 files changed, 294 insertions, 783 deletions
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
generated by cgit v1.2.3 (git 2.25.1) at 2024-10-03 09:17:09 +0100