diff options
author | Dawer <[email protected]> | 2021-05-10 12:55:00 +0100 |
---|---|---|
committer | Dawer <[email protected]> | 2021-05-31 20:08:27 +0100 |
commit | 466345ca81c9f8a17347671ca27856eb963858f4 (patch) | |
tree | 8327771c3d67f7c4509b373e8ad7075f5cfd5ac6 /crates/hir_ty | |
parent | 49e016169fc8413e2734a655cbd55ebba2907b76 (diff) |
Clean up, more docs.
Diffstat (limited to 'crates/hir_ty')
-rw-r--r-- | crates/hir_ty/src/diagnostics/expr.rs | 1 | ||||
-rw-r--r-- | crates/hir_ty/src/diagnostics/pattern.rs | 25 | ||||
-rw-r--r-- | crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs | 145 | ||||
-rw-r--r-- | crates/hir_ty/src/diagnostics/pattern/usefulness.rs | 313 |
4 files changed, 383 insertions, 101 deletions
diff --git a/crates/hir_ty/src/diagnostics/expr.rs b/crates/hir_ty/src/diagnostics/expr.rs index e4e9ab5c0..b321004ac 100644 --- a/crates/hir_ty/src/diagnostics/expr.rs +++ b/crates/hir_ty/src/diagnostics/expr.rs | |||
@@ -437,7 +437,6 @@ impl<'a, 'b> ExprValidator<'a, 'b> { | |||
437 | let cx = usefulness::MatchCheckCtx { | 437 | let cx = usefulness::MatchCheckCtx { |
438 | module: self.owner.module(db.upcast()), | 438 | module: self.owner.module(db.upcast()), |
439 | match_expr, | 439 | match_expr, |
440 | body, | ||
441 | infer: &infer, | 440 | infer: &infer, |
442 | db, | 441 | db, |
443 | pattern_arena: &pattern_arena, | 442 | pattern_arena: &pattern_arena, |
diff --git a/crates/hir_ty/src/diagnostics/pattern.rs b/crates/hir_ty/src/diagnostics/pattern.rs index 38e4b53b7..85c01b178 100644 --- a/crates/hir_ty/src/diagnostics/pattern.rs +++ b/crates/hir_ty/src/diagnostics/pattern.rs | |||
@@ -1,15 +1,18 @@ | |||
1 | #![deny(elided_lifetimes_in_paths)] | 1 | //! Validation of matches. |
2 | #![allow(unused)] // todo remove | 2 | //! |
3 | //! This module provides lowering from [hir_def::expr::Pat] to [self::Pat] and match | ||
4 | //! checking algorithm. | ||
5 | //! | ||
6 | //! It is a loose port of `rustc_mir_build::thir::pattern` module. | ||
3 | 7 | ||
4 | mod deconstruct_pat; | 8 | mod deconstruct_pat; |
5 | // TODO: find a better place for this? | ||
6 | mod pat_util; | 9 | mod pat_util; |
7 | pub(crate) mod usefulness; | 10 | pub(crate) mod usefulness; |
8 | 11 | ||
9 | use hir_def::{body::Body, EnumVariantId, LocalFieldId, VariantId}; | 12 | use hir_def::{body::Body, EnumVariantId, LocalFieldId, VariantId}; |
10 | use la_arena::Idx; | 13 | use la_arena::Idx; |
11 | 14 | ||
12 | use crate::{db::HirDatabase, AdtId, InferenceResult, Interner, Substitution, Ty, TyKind}; | 15 | use crate::{db::HirDatabase, InferenceResult, Interner, Substitution, Ty, TyKind}; |
13 | 16 | ||
14 | use self::pat_util::EnumerateAndAdjustIterator; | 17 | use self::pat_util::EnumerateAndAdjustIterator; |
15 | 18 | ||
@@ -38,6 +41,7 @@ impl Pat { | |||
38 | } | 41 | } |
39 | } | 42 | } |
40 | 43 | ||
44 | /// Close relative to `rustc_mir_build::thir::pattern::PatKind` | ||
41 | #[derive(Clone, Debug, PartialEq)] | 45 | #[derive(Clone, Debug, PartialEq)] |
42 | pub(crate) enum PatKind { | 46 | pub(crate) enum PatKind { |
43 | Wild, | 47 | Wild, |
@@ -66,7 +70,7 @@ pub(crate) enum PatKind { | |||
66 | subpattern: Pat, | 70 | subpattern: Pat, |
67 | }, | 71 | }, |
68 | 72 | ||
69 | // only bool for now | 73 | // FIXME: for now, only bool literals are implemented |
70 | LiteralBool { | 74 | LiteralBool { |
71 | value: bool, | 75 | value: bool, |
72 | }, | 76 | }, |
@@ -91,7 +95,7 @@ impl<'a> PatCtxt<'a> { | |||
91 | } | 95 | } |
92 | 96 | ||
93 | pub(crate) fn lower_pattern(&mut self, pat: hir_def::expr::PatId) -> Pat { | 97 | pub(crate) fn lower_pattern(&mut self, pat: hir_def::expr::PatId) -> Pat { |
94 | // TODO: pattern adjustments (implicit dereference) | 98 | // FIXME: implement pattern adjustments (implicit pattern dereference; "RFC 2005-match-ergonomics") |
95 | // More info https://github.com/rust-lang/rust/issues/42640#issuecomment-313535089 | 99 | // More info https://github.com/rust-lang/rust/issues/42640#issuecomment-313535089 |
96 | let unadjusted_pat = self.lower_pattern_unadjusted(pat); | 100 | let unadjusted_pat = self.lower_pattern_unadjusted(pat); |
97 | unadjusted_pat | 101 | unadjusted_pat |
@@ -141,7 +145,7 @@ impl<'a> PatCtxt<'a> { | |||
141 | .iter() | 145 | .iter() |
142 | .map(|field| FieldPat { | 146 | .map(|field| FieldPat { |
143 | // XXX(iDawer): field lookup is inefficient | 147 | // XXX(iDawer): field lookup is inefficient |
144 | field: variant_data.field(&field.name).unwrap_or_else(|| todo!()), | 148 | field: variant_data.field(&field.name).unwrap(), |
145 | pattern: self.lower_pattern(field.pat), | 149 | pattern: self.lower_pattern(field.pat), |
146 | }) | 150 | }) |
147 | .collect(); | 151 | .collect(); |
@@ -208,11 +212,10 @@ impl<'a> PatCtxt<'a> { | |||
208 | PatKind::Wild | 212 | PatKind::Wild |
209 | } | 213 | } |
210 | }; | 214 | }; |
211 | // TODO: do we need PatKind::AscribeUserType ? | ||
212 | kind | 215 | kind |
213 | } | 216 | } |
214 | 217 | ||
215 | fn lower_path(&mut self, pat: hir_def::expr::PatId, path: &hir_def::path::Path) -> Pat { | 218 | fn lower_path(&mut self, pat: hir_def::expr::PatId, _path: &hir_def::path::Path) -> Pat { |
216 | let ty = &self.infer[pat]; | 219 | let ty = &self.infer[pat]; |
217 | 220 | ||
218 | let pat_from_kind = |kind| Pat { ty: ty.clone(), kind: Box::new(kind) }; | 221 | let pat_from_kind = |kind| Pat { ty: ty.clone(), kind: Box::new(kind) }; |
@@ -338,8 +341,6 @@ impl PatternFoldable for PatKind { | |||
338 | mod tests { | 341 | mod tests { |
339 | use crate::diagnostics::tests::check_diagnostics; | 342 | use crate::diagnostics::tests::check_diagnostics; |
340 | 343 | ||
341 | use super::*; | ||
342 | |||
343 | #[test] | 344 | #[test] |
344 | fn unit() { | 345 | fn unit() { |
345 | check_diagnostics( | 346 | check_diagnostics( |
@@ -372,8 +373,6 @@ fn main() { | |||
372 | 373 | ||
373 | #[test] | 374 | #[test] |
374 | fn tuple_with_ellipsis() { | 375 | fn tuple_with_ellipsis() { |
375 | // TODO: test non-exhaustive match with ellipsis in the middle | ||
376 | // of a pattern, check reported witness | ||
377 | check_diagnostics( | 376 | check_diagnostics( |
378 | r#" | 377 | r#" |
379 | struct A; struct B; | 378 | struct A; struct B; |
diff --git a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs index 1c86ed59b..9fa82a952 100644 --- a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs +++ b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs | |||
@@ -1,14 +1,54 @@ | |||
1 | //! [`super::usefulness`] explains most of what is happening in this file. As explained there, | ||
2 | //! values and patterns are made from constructors applied to fields. This file defines a | ||
3 | //! `Constructor` enum, a `Fields` struct, and various operations to manipulate them and convert | ||
4 | //! them from/to patterns. | ||
5 | //! | ||
6 | //! There's one idea that is not detailed in [`super::usefulness`] because the details are not | ||
7 | //! needed there: _constructor splitting_. | ||
8 | //! | ||
9 | //! # Constructor splitting | ||
10 | //! | ||
11 | //! The idea is as follows: given a constructor `c` and a matrix, we want to specialize in turn | ||
12 | //! with all the value constructors that are covered by `c`, and compute usefulness for each. | ||
13 | //! Instead of listing all those constructors (which is intractable), we group those value | ||
14 | //! constructors together as much as possible. Example: | ||
15 | //! | ||
16 | //! ``` | ||
17 | //! match (0, false) { | ||
18 | //! (0 ..=100, true) => {} // `p_1` | ||
19 | //! (50..=150, false) => {} // `p_2` | ||
20 | //! (0 ..=200, _) => {} // `q` | ||
21 | //! } | ||
22 | //! ``` | ||
23 | //! | ||
24 | //! The naive approach would try all numbers in the range `0..=200`. But we can be a lot more | ||
25 | //! clever: `0` and `1` for example will match the exact same rows, and return equivalent | ||
26 | //! witnesses. In fact all of `0..50` would. We can thus restrict our exploration to 4 | ||
27 | //! constructors: `0..50`, `50..=100`, `101..=150` and `151..=200`. That is enough and infinitely | ||
28 | //! more tractable. | ||
29 | //! | ||
30 | //! We capture this idea in a function `split(p_1 ... p_n, c)` which returns a list of constructors | ||
31 | //! `c'` covered by `c`. Given such a `c'`, we require that all value ctors `c''` covered by `c'` | ||
32 | //! return an equivalent set of witnesses after specializing and computing usefulness. | ||
33 | //! In the example above, witnesses for specializing by `c''` covered by `0..50` will only differ | ||
34 | //! in their first element. | ||
35 | //! | ||
36 | //! We usually also ask that the `c'` together cover all of the original `c`. However we allow | ||
37 | //! skipping some constructors as long as it doesn't change whether the resulting list of witnesses | ||
38 | //! is empty of not. We use this in the wildcard `_` case. | ||
39 | //! | ||
40 | //! Splitting is implemented in the [`Constructor::split`] function. We don't do splitting for | ||
41 | //! or-patterns; instead we just try the alternatives one-by-one. For details on splitting | ||
42 | //! wildcards, see [`SplitWildcard`]; for integer ranges, see [`SplitIntRange`]; for slices, see | ||
43 | //! [`SplitVarLenSlice`]. | ||
44 | |||
1 | use std::{ | 45 | use std::{ |
2 | cmp::{max, min}, | 46 | cmp::{max, min}, |
3 | iter::once, | 47 | iter::once, |
4 | ops::RangeInclusive, | 48 | ops::RangeInclusive, |
5 | }; | 49 | }; |
6 | 50 | ||
7 | use hir_def::{ | 51 | use hir_def::{EnumVariantId, HasModule, LocalFieldId, VariantId}; |
8 | expr::{Expr, Literal, RecordFieldPat}, | ||
9 | type_ref::Mutability, | ||
10 | AttrDefId, EnumVariantId, HasModule, LocalFieldId, VariantId, | ||
11 | }; | ||
12 | use smallvec::{smallvec, SmallVec}; | 52 | use smallvec::{smallvec, SmallVec}; |
13 | 53 | ||
14 | use crate::{AdtId, Interner, Scalar, Ty, TyExt, TyKind}; | 54 | use crate::{AdtId, Interner, Scalar, Ty, TyExt, TyKind}; |
@@ -20,9 +60,21 @@ use super::{ | |||
20 | 60 | ||
21 | use self::Constructor::*; | 61 | use self::Constructor::*; |
22 | 62 | ||
63 | /// [Constructor] uses this in umimplemented variants. | ||
64 | /// It allows porting match expressions from upstream algorithm without losing semantics. | ||
23 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | 65 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] |
24 | pub(super) enum ToDo {} | 66 | pub(super) enum Void {} |
25 | 67 | ||
68 | /// An inclusive interval, used for precise integer exhaustiveness checking. | ||
69 | /// `IntRange`s always store a contiguous range. This means that values are | ||
70 | /// encoded such that `0` encodes the minimum value for the integer, | ||
71 | /// regardless of the signedness. | ||
72 | /// For example, the pattern `-128..=127i8` is encoded as `0..=255`. | ||
73 | /// This makes comparisons and arithmetic on interval endpoints much more | ||
74 | /// straightforward. See `signed_bias` for details. | ||
75 | /// | ||
76 | /// `IntRange` is never used to encode an empty range or a "range" that wraps | ||
77 | /// around the (offset) space: i.e., `range.lo <= range.hi`. | ||
26 | #[derive(Clone, Debug, PartialEq, Eq)] | 78 | #[derive(Clone, Debug, PartialEq, Eq)] |
27 | pub(super) struct IntRange { | 79 | pub(super) struct IntRange { |
28 | range: RangeInclusive<u128>, | 80 | range: RangeInclusive<u128>, |
@@ -55,11 +107,11 @@ impl IntRange { | |||
55 | } | 107 | } |
56 | 108 | ||
57 | #[inline] | 109 | #[inline] |
58 | fn from_range(cx: &MatchCheckCtx<'_>, lo: u128, hi: u128, scalar_ty: Scalar) -> IntRange { | 110 | fn from_range(lo: u128, hi: u128, scalar_ty: Scalar) -> IntRange { |
59 | if let Scalar::Bool = scalar_ty { | 111 | if let Scalar::Bool = scalar_ty { |
60 | IntRange { range: lo..=hi } | 112 | IntRange { range: lo..=hi } |
61 | } else { | 113 | } else { |
62 | todo!() | 114 | unimplemented!() |
63 | } | 115 | } |
64 | } | 116 | } |
65 | 117 | ||
@@ -188,13 +240,13 @@ impl SplitIntRange { | |||
188 | /// A constructor for array and slice patterns. | 240 | /// A constructor for array and slice patterns. |
189 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | 241 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] |
190 | pub(super) struct Slice { | 242 | pub(super) struct Slice { |
191 | todo: ToDo, | 243 | _unimplemented: Void, |
192 | } | 244 | } |
193 | 245 | ||
194 | impl Slice { | 246 | impl Slice { |
195 | /// See `Constructor::is_covered_by` | 247 | /// See `Constructor::is_covered_by` |
196 | fn is_covered_by(self, other: Self) -> bool { | 248 | fn is_covered_by(self, _other: Self) -> bool { |
197 | todo!() | 249 | unimplemented!() // never called as Slice contains Void |
198 | } | 250 | } |
199 | } | 251 | } |
200 | 252 | ||
@@ -205,6 +257,7 @@ impl Slice { | |||
205 | /// `specialize_constructor` returns the list of fields corresponding to a pattern, given a | 257 | /// `specialize_constructor` returns the list of fields corresponding to a pattern, given a |
206 | /// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and | 258 | /// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and |
207 | /// `Fields`. | 259 | /// `Fields`. |
260 | #[allow(dead_code)] | ||
208 | #[derive(Clone, Debug, PartialEq)] | 261 | #[derive(Clone, Debug, PartialEq)] |
209 | pub(super) enum Constructor { | 262 | pub(super) enum Constructor { |
210 | /// The constructor for patterns that have a single constructor, like tuples, struct patterns | 263 | /// The constructor for patterns that have a single constructor, like tuples, struct patterns |
@@ -215,9 +268,9 @@ pub(super) enum Constructor { | |||
215 | /// Ranges of integer literal values (`2`, `2..=5` or `2..5`). | 268 | /// Ranges of integer literal values (`2`, `2..=5` or `2..5`). |
216 | IntRange(IntRange), | 269 | IntRange(IntRange), |
217 | /// Ranges of floating-point literal values (`2.0..=5.2`). | 270 | /// Ranges of floating-point literal values (`2.0..=5.2`). |
218 | FloatRange(ToDo), | 271 | FloatRange(Void), |
219 | /// String literals. Strings are not quite the same as `&[u8]` so we treat them separately. | 272 | /// String literals. Strings are not quite the same as `&[u8]` so we treat them separately. |
220 | Str(ToDo), | 273 | Str(Void), |
221 | /// Array and slice patterns. | 274 | /// Array and slice patterns. |
222 | Slice(Slice), | 275 | Slice(Slice), |
223 | /// Constants that must not be matched structurally. They are treated as black | 276 | /// Constants that must not be matched structurally. They are treated as black |
@@ -253,7 +306,7 @@ impl Constructor { | |||
253 | } | 306 | } |
254 | } | 307 | } |
255 | 308 | ||
256 | fn variant_id_for_adt(&self, adt: hir_def::AdtId, cx: &MatchCheckCtx<'_>) -> VariantId { | 309 | fn variant_id_for_adt(&self, adt: hir_def::AdtId) -> VariantId { |
257 | match *self { | 310 | match *self { |
258 | Variant(id) => id.into(), | 311 | Variant(id) => id.into(), |
259 | Single => { | 312 | Single => { |
@@ -270,7 +323,6 @@ impl Constructor { | |||
270 | 323 | ||
271 | /// Determines the constructor that the given pattern can be specialized to. | 324 | /// Determines the constructor that the given pattern can be specialized to. |
272 | pub(super) fn from_pat(cx: &MatchCheckCtx<'_>, pat: PatId) -> Self { | 325 | pub(super) fn from_pat(cx: &MatchCheckCtx<'_>, pat: PatId) -> Self { |
273 | let ty = cx.type_of(pat); | ||
274 | match cx.pattern_arena.borrow()[pat].kind.as_ref() { | 326 | match cx.pattern_arena.borrow()[pat].kind.as_ref() { |
275 | PatKind::Binding { .. } | PatKind::Wild => Wildcard, | 327 | PatKind::Binding { .. } | PatKind::Wild => Wildcard, |
276 | PatKind::Leaf { .. } | PatKind::Deref { .. } => Single, | 328 | PatKind::Leaf { .. } | PatKind::Deref { .. } => Single, |
@@ -312,7 +364,7 @@ impl Constructor { | |||
312 | split_range.split(int_ranges.cloned()); | 364 | split_range.split(int_ranges.cloned()); |
313 | split_range.iter().map(IntRange).collect() | 365 | split_range.iter().map(IntRange).collect() |
314 | } | 366 | } |
315 | Slice(_) => todo!("Constructor::split Slice"), | 367 | Slice(_) => unimplemented!(), |
316 | // Any other constructor can be used unchanged. | 368 | // Any other constructor can be used unchanged. |
317 | _ => smallvec![self.clone()], | 369 | _ => smallvec![self.clone()], |
318 | } | 370 | } |
@@ -323,7 +375,7 @@ impl Constructor { | |||
323 | /// this checks for inclusion. | 375 | /// this checks for inclusion. |
324 | // We inline because this has a single call site in `Matrix::specialize_constructor`. | 376 | // We inline because this has a single call site in `Matrix::specialize_constructor`. |
325 | #[inline] | 377 | #[inline] |
326 | pub(super) fn is_covered_by(&self, pcx: PatCtxt<'_>, other: &Self) -> bool { | 378 | pub(super) fn is_covered_by(&self, _pcx: PatCtxt<'_>, other: &Self) -> bool { |
327 | // This must be kept in sync with `is_covered_by_any`. | 379 | // This must be kept in sync with `is_covered_by_any`. |
328 | match (self, other) { | 380 | match (self, other) { |
329 | // Wildcards cover anything | 381 | // Wildcards cover anything |
@@ -336,10 +388,10 @@ impl Constructor { | |||
336 | 388 | ||
337 | (IntRange(self_range), IntRange(other_range)) => self_range.is_covered_by(other_range), | 389 | (IntRange(self_range), IntRange(other_range)) => self_range.is_covered_by(other_range), |
338 | (FloatRange(..), FloatRange(..)) => { | 390 | (FloatRange(..), FloatRange(..)) => { |
339 | todo!() | 391 | unimplemented!() |
340 | } | 392 | } |
341 | (Str(self_val), Str(other_val)) => { | 393 | (Str(..), Str(..)) => { |
342 | todo!() | 394 | unimplemented!() |
343 | } | 395 | } |
344 | (Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice), | 396 | (Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice), |
345 | 397 | ||
@@ -358,7 +410,7 @@ impl Constructor { | |||
358 | /// Faster version of `is_covered_by` when applied to many constructors. `used_ctors` is | 410 | /// Faster version of `is_covered_by` when applied to many constructors. `used_ctors` is |
359 | /// assumed to be built from `matrix.head_ctors()` with wildcards filtered out, and `self` is | 411 | /// assumed to be built from `matrix.head_ctors()` with wildcards filtered out, and `self` is |
360 | /// assumed to have been split from a wildcard. | 412 | /// assumed to have been split from a wildcard. |
361 | fn is_covered_by_any(&self, pcx: PatCtxt<'_>, used_ctors: &[Constructor]) -> bool { | 413 | fn is_covered_by_any(&self, _pcx: PatCtxt<'_>, used_ctors: &[Constructor]) -> bool { |
362 | if used_ctors.is_empty() { | 414 | if used_ctors.is_empty() { |
363 | return false; | 415 | return false; |
364 | } | 416 | } |
@@ -411,9 +463,10 @@ pub(super) struct SplitWildcard { | |||
411 | impl SplitWildcard { | 463 | impl SplitWildcard { |
412 | pub(super) fn new(pcx: PatCtxt<'_>) -> Self { | 464 | pub(super) fn new(pcx: PatCtxt<'_>) -> Self { |
413 | let cx = pcx.cx; | 465 | let cx = pcx.cx; |
414 | let make_range = | 466 | let make_range = |start, end, scalar| IntRange(IntRange::from_range(start, end, scalar)); |
415 | |start, end, scalar| IntRange(IntRange::from_range(cx, start, end, scalar)); | 467 | |
416 | // FIXME(iDawer) using NonExhaustive ctor for unhandled types | 468 | // Unhandled types are treated as non-exhaustive. Being explicit here instead of falling |
469 | // to catchall arm to ease further implementation. | ||
417 | let unhandled = || smallvec![NonExhaustive]; | 470 | let unhandled = || smallvec![NonExhaustive]; |
418 | 471 | ||
419 | // This determines the set of all possible constructors for the type `pcx.ty`. For numbers, | 472 | // This determines the set of all possible constructors for the type `pcx.ty`. For numbers, |
@@ -426,7 +479,7 @@ impl SplitWildcard { | |||
426 | // `cx.is_uninhabited()`). | 479 | // `cx.is_uninhabited()`). |
427 | let all_ctors = match pcx.ty.kind(&Interner) { | 480 | let all_ctors = match pcx.ty.kind(&Interner) { |
428 | TyKind::Scalar(Scalar::Bool) => smallvec![make_range(0, 1, Scalar::Bool)], | 481 | TyKind::Scalar(Scalar::Bool) => smallvec![make_range(0, 1, Scalar::Bool)], |
429 | // TyKind::Array(..) if ... => todo!(), | 482 | // TyKind::Array(..) if ... => unhandled(), |
430 | TyKind::Array(..) | TyKind::Slice(..) => unhandled(), | 483 | TyKind::Array(..) | TyKind::Slice(..) => unhandled(), |
431 | &TyKind::Adt(AdtId(hir_def::AdtId::EnumId(enum_id)), ref _substs) => { | 484 | &TyKind::Adt(AdtId(hir_def::AdtId::EnumId(enum_id)), ref _substs) => { |
432 | let enum_data = cx.db.enum_data(enum_id); | 485 | let enum_data = cx.db.enum_data(enum_id); |
@@ -556,26 +609,6 @@ impl SplitWildcard { | |||
556 | } | 609 | } |
557 | } | 610 | } |
558 | 611 | ||
559 | #[test] | ||
560 | fn it_works2() {} | ||
561 | |||
562 | /// Some fields need to be explicitly hidden away in certain cases; see the comment above the | ||
563 | /// `Fields` struct. This struct represents such a potentially-hidden field. | ||
564 | #[derive(Debug, Copy, Clone)] | ||
565 | pub(super) enum FilteredField { | ||
566 | Kept(PatId), | ||
567 | Hidden, | ||
568 | } | ||
569 | |||
570 | impl FilteredField { | ||
571 | fn kept(self) -> Option<PatId> { | ||
572 | match self { | ||
573 | FilteredField::Kept(p) => Some(p), | ||
574 | FilteredField::Hidden => None, | ||
575 | } | ||
576 | } | ||
577 | } | ||
578 | |||
579 | /// A value can be decomposed into a constructor applied to some fields. This struct represents | 612 | /// A value can be decomposed into a constructor applied to some fields. This struct represents |
580 | /// those fields, generalized to allow patterns in each field. See also `Constructor`. | 613 | /// those fields, generalized to allow patterns in each field. See also `Constructor`. |
581 | /// This is constructed from a constructor using [`Fields::wildcards()`]. | 614 | /// This is constructed from a constructor using [`Fields::wildcards()`]. |
@@ -623,14 +656,13 @@ impl Fields { | |||
623 | } | 656 | } |
624 | TyKind::Ref(.., rty) => Fields::from_single_pattern(wildcard_from_ty(rty)), | 657 | TyKind::Ref(.., rty) => Fields::from_single_pattern(wildcard_from_ty(rty)), |
625 | TyKind::Adt(AdtId(adt), substs) => { | 658 | TyKind::Adt(AdtId(adt), substs) => { |
626 | let adt_is_box = false; // TODO(iDawer): handle box patterns | 659 | let adt_is_box = false; // TODO(iDawer): implement this |
627 | if adt_is_box { | 660 | if adt_is_box { |
628 | // Use T as the sub pattern type of Box<T>. | 661 | // Use T as the sub pattern type of Box<T>. |
629 | let ty = substs.at(&Interner, 0).assert_ty_ref(&Interner); | 662 | let subst_ty = substs.at(&Interner, 0).assert_ty_ref(&Interner); |
630 | Fields::from_single_pattern(wildcard_from_ty(ty)) | 663 | Fields::from_single_pattern(wildcard_from_ty(subst_ty)) |
631 | } else { | 664 | } else { |
632 | let variant_id = constructor.variant_id_for_adt(*adt, cx); | 665 | let variant_id = constructor.variant_id_for_adt(*adt); |
633 | let variant = variant_id.variant_data(cx.db.upcast()); | ||
634 | let adt_is_local = | 666 | let adt_is_local = |
635 | variant_id.module(cx.db.upcast()).krate() == cx.module.krate(); | 667 | variant_id.module(cx.db.upcast()).krate() == cx.module.krate(); |
636 | // Whether we must not match the fields of this variant exhaustively. | 668 | // Whether we must not match the fields of this variant exhaustively. |
@@ -655,8 +687,8 @@ impl Fields { | |||
655 | } | 687 | } |
656 | _ => panic!("Unexpected type for `Single` constructor: {:?}", ty), | 688 | _ => panic!("Unexpected type for `Single` constructor: {:?}", ty), |
657 | }, | 689 | }, |
658 | Slice(slice) => { | 690 | Slice(..) => { |
659 | todo!() | 691 | unimplemented!() |
660 | } | 692 | } |
661 | Str(..) | FloatRange(..) | IntRange(..) | NonExhaustive | Opaque | Missing | 693 | Str(..) | FloatRange(..) | IntRange(..) | NonExhaustive | Opaque | Missing |
662 | | Wildcard => Fields::Vec(Default::default()), | 694 | | Wildcard => Fields::Vec(Default::default()), |
@@ -722,7 +754,7 @@ impl Fields { | |||
722 | } | 754 | } |
723 | _ => PatKind::Wild, | 755 | _ => PatKind::Wild, |
724 | }, | 756 | }, |
725 | Constructor::Slice(slice) => UNHANDLED, | 757 | Constructor::Slice(_) => UNHANDLED, |
726 | Str(_) => UNHANDLED, | 758 | Str(_) => UNHANDLED, |
727 | FloatRange(..) => UNHANDLED, | 759 | FloatRange(..) => UNHANDLED, |
728 | Constructor::IntRange(_) => UNHANDLED, | 760 | Constructor::IntRange(_) => UNHANDLED, |
@@ -828,7 +860,7 @@ impl Fields { | |||
828 | pat: PatId, | 860 | pat: PatId, |
829 | cx: &MatchCheckCtx<'_>, | 861 | cx: &MatchCheckCtx<'_>, |
830 | ) -> Self { | 862 | ) -> Self { |
831 | // TODO: these alocations and clones are so unfortunate (+1 for switching to references) | 863 | // FIXME(iDawer): these alocations and clones are so unfortunate (+1 for switching to references) |
832 | let mut arena = cx.pattern_arena.borrow_mut(); | 864 | let mut arena = cx.pattern_arena.borrow_mut(); |
833 | match arena[pat].kind.as_ref() { | 865 | match arena[pat].kind.as_ref() { |
834 | PatKind::Deref { subpattern } => { | 866 | PatKind::Deref { subpattern } => { |
@@ -860,6 +892,3 @@ fn is_field_list_non_exhaustive(variant_id: VariantId, cx: &MatchCheckCtx<'_>) - | |||
860 | }; | 892 | }; |
861 | cx.db.attrs(attr_def_id).by_key("non_exhaustive").exists() | 893 | cx.db.attrs(attr_def_id).by_key("non_exhaustive").exists() |
862 | } | 894 | } |
863 | |||
864 | #[test] | ||
865 | fn it_works() {} | ||
diff --git a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs index 01a7fb0d9..b01e3557c 100644 --- a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs +++ b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs | |||
@@ -1,9 +1,279 @@ | |||
1 | // Based on rust-lang/rust 1.52.0-nightly (25c15cdbe 2021-04-22) | 1 | //! Based on rust-lang/rust 1.52.0-nightly (25c15cdbe 2021-04-22) |
2 | // https://github.com/rust-lang/rust/blob/25c15cdbe/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs | 2 | //! https://github.com/rust-lang/rust/blob/25c15cdbe/compiler/rustc_mir_build/src/thir/pattern/usefulness.rs |
3 | 3 | //! | |
4 | use std::{cell::RefCell, iter::FromIterator, ops::Index, sync::Arc}; | 4 | //! ----- |
5 | 5 | //! | |
6 | use hir_def::{body::Body, expr::ExprId, HasModule, ModuleId}; | 6 | //! This file includes the logic for exhaustiveness and reachability checking for pattern-matching. |
7 | //! Specifically, given a list of patterns for a type, we can tell whether: | ||
8 | //! (a) each pattern is reachable (reachability) | ||
9 | //! (b) the patterns cover every possible value for the type (exhaustiveness) | ||
10 | //! | ||
11 | //! The algorithm implemented here is a modified version of the one described in [this | ||
12 | //! paper](http://moscova.inria.fr/~maranget/papers/warn/index.html). We have however generalized | ||
13 | //! it to accommodate the variety of patterns that Rust supports. We thus explain our version here, | ||
14 | //! without being as rigorous. | ||
15 | //! | ||
16 | //! | ||
17 | //! # Summary | ||
18 | //! | ||
19 | //! The core of the algorithm is the notion of "usefulness". A pattern `q` is said to be *useful* | ||
20 | //! relative to another pattern `p` of the same type if there is a value that is matched by `q` and | ||
21 | //! not matched by `p`. This generalizes to many `p`s: `q` is useful w.r.t. a list of patterns | ||
22 | //! `p_1 .. p_n` if there is a value that is matched by `q` and by none of the `p_i`. We write | ||
23 | //! `usefulness(p_1 .. p_n, q)` for a function that returns a list of such values. The aim of this | ||
24 | //! file is to compute it efficiently. | ||
25 | //! | ||
26 | //! This is enough to compute reachability: a pattern in a `match` expression is reachable iff it | ||
27 | //! is useful w.r.t. the patterns above it: | ||
28 | //! ```rust | ||
29 | //! match x { | ||
30 | //! Some(_) => ..., | ||
31 | //! None => ..., // reachable: `None` is matched by this but not the branch above | ||
32 | //! Some(0) => ..., // unreachable: all the values this matches are already matched by | ||
33 | //! // `Some(_)` above | ||
34 | //! } | ||
35 | //! ``` | ||
36 | //! | ||
37 | //! This is also enough to compute exhaustiveness: a match is exhaustive iff the wildcard `_` | ||
38 | //! pattern is _not_ useful w.r.t. the patterns in the match. The values returned by `usefulness` | ||
39 | //! are used to tell the user which values are missing. | ||
40 | //! ```rust | ||
41 | //! match x { | ||
42 | //! Some(0) => ..., | ||
43 | //! None => ..., | ||
44 | //! // not exhaustive: `_` is useful because it matches `Some(1)` | ||
45 | //! } | ||
46 | //! ``` | ||
47 | //! | ||
48 | //! The entrypoint of this file is the [`compute_match_usefulness`] function, which computes | ||
49 | //! reachability for each match branch and exhaustiveness for the whole match. | ||
50 | //! | ||
51 | //! | ||
52 | //! # Constructors and fields | ||
53 | //! | ||
54 | //! Note: we will often abbreviate "constructor" as "ctor". | ||
55 | //! | ||
56 | //! The idea that powers everything that is done in this file is the following: a (matcheable) | ||
57 | //! value is made from a constructor applied to a number of subvalues. Examples of constructors are | ||
58 | //! `Some`, `None`, `(,)` (the 2-tuple constructor), `Foo {..}` (the constructor for a struct | ||
59 | //! `Foo`), and `2` (the constructor for the number `2`). This is natural when we think of | ||
60 | //! pattern-matching, and this is the basis for what follows. | ||
61 | //! | ||
62 | //! Some of the ctors listed above might feel weird: `None` and `2` don't take any arguments. | ||
63 | //! That's ok: those are ctors that take a list of 0 arguments; they are the simplest case of | ||
64 | //! ctors. We treat `2` as a ctor because `u64` and other number types behave exactly like a huge | ||
65 | //! `enum`, with one variant for each number. This allows us to see any matcheable value as made up | ||
66 | //! from a tree of ctors, each having a set number of children. For example: `Foo { bar: None, | ||
67 | //! baz: Ok(0) }` is made from 4 different ctors, namely `Foo{..}`, `None`, `Ok` and `0`. | ||
68 | //! | ||
69 | //! This idea can be extended to patterns: they are also made from constructors applied to fields. | ||
70 | //! A pattern for a given type is allowed to use all the ctors for values of that type (which we | ||
71 | //! call "value constructors"), but there are also pattern-only ctors. The most important one is | ||
72 | //! the wildcard (`_`), and the others are integer ranges (`0..=10`), variable-length slices (`[x, | ||
73 | //! ..]`), and or-patterns (`Ok(0) | Err(_)`). Examples of valid patterns are `42`, `Some(_)`, `Foo | ||
74 | //! { bar: Some(0) | None, baz: _ }`. Note that a binder in a pattern (e.g. `Some(x)`) matches the | ||
75 | //! same values as a wildcard (e.g. `Some(_)`), so we treat both as wildcards. | ||
76 | //! | ||
77 | //! From this deconstruction we can compute whether a given value matches a given pattern; we | ||
78 | //! simply look at ctors one at a time. Given a pattern `p` and a value `v`, we want to compute | ||
79 | //! `matches!(v, p)`. It's mostly straightforward: we compare the head ctors and when they match | ||
80 | //! we compare their fields recursively. A few representative examples: | ||
81 | //! | ||
82 | //! - `matches!(v, _) := true` | ||
83 | //! - `matches!((v0, v1), (p0, p1)) := matches!(v0, p0) && matches!(v1, p1)` | ||
84 | //! - `matches!(Foo { bar: v0, baz: v1 }, Foo { bar: p0, baz: p1 }) := matches!(v0, p0) && matches!(v1, p1)` | ||
85 | //! - `matches!(Ok(v0), Ok(p0)) := matches!(v0, p0)` | ||
86 | //! - `matches!(Ok(v0), Err(p0)) := false` (incompatible variants) | ||
87 | //! - `matches!(v, 1..=100) := matches!(v, 1) || ... || matches!(v, 100)` | ||
88 | //! - `matches!([v0], [p0, .., p1]) := false` (incompatible lengths) | ||
89 | //! - `matches!([v0, v1, v2], [p0, .., p1]) := matches!(v0, p0) && matches!(v2, p1)` | ||
90 | //! - `matches!(v, p0 | p1) := matches!(v, p0) || matches!(v, p1)` | ||
91 | //! | ||
92 | //! Constructors, fields and relevant operations are defined in the [`super::deconstruct_pat`] module. | ||
93 | //! | ||
94 | //! Note: this constructors/fields distinction may not straightforwardly apply to every Rust type. | ||
95 | //! For example a value of type `Rc<u64>` can't be deconstructed that way, and `&str` has an | ||
96 | //! infinitude of constructors. There are also subtleties with visibility of fields and | ||
97 | //! uninhabitedness and various other things. The constructors idea can be extended to handle most | ||
98 | //! of these subtleties though; caveats are documented where relevant throughout the code. | ||
99 | //! | ||
100 | //! Whether constructors cover each other is computed by [`Constructor::is_covered_by`]. | ||
101 | //! | ||
102 | //! | ||
103 | //! # Specialization | ||
104 | //! | ||
105 | //! Recall that we wish to compute `usefulness(p_1 .. p_n, q)`: given a list of patterns `p_1 .. | ||
106 | //! p_n` and a pattern `q`, all of the same type, we want to find a list of values (called | ||
107 | //! "witnesses") that are matched by `q` and by none of the `p_i`. We obviously don't just | ||
108 | //! enumerate all possible values. From the discussion above we see that we can proceed | ||
109 | //! ctor-by-ctor: for each value ctor of the given type, we ask "is there a value that starts with | ||
110 | //! this constructor and matches `q` and none of the `p_i`?". As we saw above, there's a lot we can | ||
111 | //! say from knowing only the first constructor of our candidate value. | ||
112 | //! | ||
113 | //! Let's take the following example: | ||
114 | //! ``` | ||
115 | //! match x { | ||
116 | //! Enum::Variant1(_) => {} // `p1` | ||
117 | //! Enum::Variant2(None, 0) => {} // `p2` | ||
118 | //! Enum::Variant2(Some(_), 0) => {} // `q` | ||
119 | //! } | ||
120 | //! ``` | ||
121 | //! | ||
122 | //! We can easily see that if our candidate value `v` starts with `Variant1` it will not match `q`. | ||
123 | //! If `v = Variant2(v0, v1)` however, whether or not it matches `p2` and `q` will depend on `v0` | ||
124 | //! and `v1`. In fact, such a `v` will be a witness of usefulness of `q` exactly when the tuple | ||
125 | //! `(v0, v1)` is a witness of usefulness of `q'` in the following reduced match: | ||
126 | //! | ||
127 | //! ``` | ||
128 | //! match x { | ||
129 | //! (None, 0) => {} // `p2'` | ||
130 | //! (Some(_), 0) => {} // `q'` | ||
131 | //! } | ||
132 | //! ``` | ||
133 | //! | ||
134 | //! This motivates a new step in computing usefulness, that we call _specialization_. | ||
135 | //! Specialization consist of filtering a list of patterns for those that match a constructor, and | ||
136 | //! then looking into the constructor's fields. This enables usefulness to be computed recursively. | ||
137 | //! | ||
138 | //! Instead of acting on a single pattern in each row, we will consider a list of patterns for each | ||
139 | //! row, and we call such a list a _pattern-stack_. The idea is that we will specialize the | ||
140 | //! leftmost pattern, which amounts to popping the constructor and pushing its fields, which feels | ||
141 | //! like a stack. We note a pattern-stack simply with `[p_1 ... p_n]`. | ||
142 | //! Here's a sequence of specializations of a list of pattern-stacks, to illustrate what's | ||
143 | //! happening: | ||
144 | //! ``` | ||
145 | //! [Enum::Variant1(_)] | ||
146 | //! [Enum::Variant2(None, 0)] | ||
147 | //! [Enum::Variant2(Some(_), 0)] | ||
148 | //! //==>> specialize with `Variant2` | ||
149 | //! [None, 0] | ||
150 | //! [Some(_), 0] | ||
151 | //! //==>> specialize with `Some` | ||
152 | //! [_, 0] | ||
153 | //! //==>> specialize with `true` (say the type was `bool`) | ||
154 | //! [0] | ||
155 | //! //==>> specialize with `0` | ||
156 | //! [] | ||
157 | //! ``` | ||
158 | //! | ||
159 | //! The function `specialize(c, p)` takes a value constructor `c` and a pattern `p`, and returns 0 | ||
160 | //! or more pattern-stacks. If `c` does not match the head constructor of `p`, it returns nothing; | ||
161 | //! otherwise if returns the fields of the constructor. This only returns more than one | ||
162 | //! pattern-stack if `p` has a pattern-only constructor. | ||
163 | //! | ||
164 | //! - Specializing for the wrong constructor returns nothing | ||
165 | //! | ||
166 | //! `specialize(None, Some(p0)) := []` | ||
167 | //! | ||
168 | //! - Specializing for the correct constructor returns a single row with the fields | ||
169 | //! | ||
170 | //! `specialize(Variant1, Variant1(p0, p1, p2)) := [[p0, p1, p2]]` | ||
171 | //! | ||
172 | //! `specialize(Foo{..}, Foo { bar: p0, baz: p1 }) := [[p0, p1]]` | ||
173 | //! | ||
174 | //! - For or-patterns, we specialize each branch and concatenate the results | ||
175 | //! | ||
176 | //! `specialize(c, p0 | p1) := specialize(c, p0) ++ specialize(c, p1)` | ||
177 | //! | ||
178 | //! - We treat the other pattern constructors as if they were a large or-pattern of all the | ||
179 | //! possibilities: | ||
180 | //! | ||
181 | //! `specialize(c, _) := specialize(c, Variant1(_) | Variant2(_, _) | ...)` | ||
182 | //! | ||
183 | //! `specialize(c, 1..=100) := specialize(c, 1 | ... | 100)` | ||
184 | //! | ||
185 | //! `specialize(c, [p0, .., p1]) := specialize(c, [p0, p1] | [p0, _, p1] | [p0, _, _, p1] | ...)` | ||
186 | //! | ||
187 | //! - If `c` is a pattern-only constructor, `specialize` is defined on a case-by-case basis. See | ||
188 | //! the discussion about constructor splitting in [`super::deconstruct_pat`]. | ||
189 | //! | ||
190 | //! | ||
191 | //! We then extend this function to work with pattern-stacks as input, by acting on the first | ||
192 | //! column and keeping the other columns untouched. | ||
193 | //! | ||
194 | //! Specialization for the whole matrix is done in [`Matrix::specialize_constructor`]. Note that | ||
195 | //! or-patterns in the first column are expanded before being stored in the matrix. Specialization | ||
196 | //! for a single patstack is done from a combination of [`Constructor::is_covered_by`] and | ||
197 | //! [`PatStack::pop_head_constructor`]. The internals of how it's done mostly live in the | ||
198 | //! [`Fields`] struct. | ||
199 | //! | ||
200 | //! | ||
201 | //! # Computing usefulness | ||
202 | //! | ||
203 | //! We now have all we need to compute usefulness. The inputs to usefulness are a list of | ||
204 | //! pattern-stacks `p_1 ... p_n` (one per row), and a new pattern_stack `q`. The paper and this | ||
205 | //! file calls the list of patstacks a _matrix_. They must all have the same number of columns and | ||
206 | //! the patterns in a given column must all have the same type. `usefulness` returns a (possibly | ||
207 | //! empty) list of witnesses of usefulness. These witnesses will also be pattern-stacks. | ||
208 | //! | ||
209 | //! - base case: `n_columns == 0`. | ||
210 | //! Since a pattern-stack functions like a tuple of patterns, an empty one functions like the | ||
211 | //! unit type. Thus `q` is useful iff there are no rows above it, i.e. if `n == 0`. | ||
212 | //! | ||
213 | //! - inductive case: `n_columns > 0`. | ||
214 | //! We need a way to list the constructors we want to try. We will be more clever in the next | ||
215 | //! section but for now assume we list all value constructors for the type of the first column. | ||
216 | //! | ||
217 | //! - for each such ctor `c`: | ||
218 | //! | ||
219 | //! - for each `q'` returned by `specialize(c, q)`: | ||
220 | //! | ||
221 | //! - we compute `usefulness(specialize(c, p_1) ... specialize(c, p_n), q')` | ||
222 | //! | ||
223 | //! - for each witness found, we revert specialization by pushing the constructor `c` on top. | ||
224 | //! | ||
225 | //! - We return the concatenation of all the witnesses found, if any. | ||
226 | //! | ||
227 | //! Example: | ||
228 | //! ``` | ||
229 | //! [Some(true)] // p_1 | ||
230 | //! [None] // p_2 | ||
231 | //! [Some(_)] // q | ||
232 | //! //==>> try `None`: `specialize(None, q)` returns nothing | ||
233 | //! //==>> try `Some`: `specialize(Some, q)` returns a single row | ||
234 | //! [true] // p_1' | ||
235 | //! [_] // q' | ||
236 | //! //==>> try `true`: `specialize(true, q')` returns a single row | ||
237 | //! [] // p_1'' | ||
238 | //! [] // q'' | ||
239 | //! //==>> base case; `n != 0` so `q''` is not useful. | ||
240 | //! //==>> go back up a step | ||
241 | //! [true] // p_1' | ||
242 | //! [_] // q' | ||
243 | //! //==>> try `false`: `specialize(false, q')` returns a single row | ||
244 | //! [] // q'' | ||
245 | //! //==>> base case; `n == 0` so `q''` is useful. We return the single witness `[]` | ||
246 | //! witnesses: | ||
247 | //! [] | ||
248 | //! //==>> undo the specialization with `false` | ||
249 | //! witnesses: | ||
250 | //! [false] | ||
251 | //! //==>> undo the specialization with `Some` | ||
252 | //! witnesses: | ||
253 | //! [Some(false)] | ||
254 | //! //==>> we have tried all the constructors. The output is the single witness `[Some(false)]`. | ||
255 | //! ``` | ||
256 | //! | ||
257 | //! This computation is done in [`is_useful`]. In practice we don't care about the list of | ||
258 | //! witnesses when computing reachability; we only need to know whether any exist. We do keep the | ||
259 | //! witnesses when computing exhaustiveness to report them to the user. | ||
260 | //! | ||
261 | //! | ||
262 | //! # Making usefulness tractable: constructor splitting | ||
263 | //! | ||
264 | //! We're missing one last detail: which constructors do we list? Naively listing all value | ||
265 | //! constructors cannot work for types like `u64` or `&str`, so we need to be more clever. The | ||
266 | //! first obvious insight is that we only want to list constructors that are covered by the head | ||
267 | //! constructor of `q`. If it's a value constructor, we only try that one. If it's a pattern-only | ||
268 | //! constructor, we use the final clever idea for this algorithm: _constructor splitting_, where we | ||
269 | //! group together constructors that behave the same. | ||
270 | //! | ||
271 | //! The details are not necessary to understand this file, so we explain them in | ||
272 | //! [`super::deconstruct_pat`]. Splitting is done by the [`Constructor::split`] function. | ||
273 | |||
274 | use std::{cell::RefCell, iter::FromIterator}; | ||
275 | |||
276 | use hir_def::{expr::ExprId, HasModule, ModuleId}; | ||
7 | use la_arena::Arena; | 277 | use la_arena::Arena; |
8 | use once_cell::unsync::OnceCell; | 278 | use once_cell::unsync::OnceCell; |
9 | use rustc_hash::FxHashMap; | 279 | use rustc_hash::FxHashMap; |
@@ -16,16 +286,11 @@ use super::{ | |||
16 | Pat, PatId, PatKind, PatternFoldable, PatternFolder, | 286 | Pat, PatId, PatKind, PatternFoldable, PatternFolder, |
17 | }; | 287 | }; |
18 | 288 | ||
19 | use self::{ | 289 | use self::{helper::PatIdExt, Usefulness::*, WitnessPreference::*}; |
20 | helper::{Captures, PatIdExt}, | ||
21 | Usefulness::*, | ||
22 | WitnessPreference::*, | ||
23 | }; | ||
24 | 290 | ||
25 | pub(crate) struct MatchCheckCtx<'a> { | 291 | pub(crate) struct MatchCheckCtx<'a> { |
26 | pub(crate) module: ModuleId, | 292 | pub(crate) module: ModuleId, |
27 | pub(crate) match_expr: ExprId, | 293 | pub(crate) match_expr: ExprId, |
28 | pub(crate) body: Arc<Body>, | ||
29 | pub(crate) infer: &'a InferenceResult, | 294 | pub(crate) infer: &'a InferenceResult, |
30 | pub(crate) db: &'a dyn HirDatabase, | 295 | pub(crate) db: &'a dyn HirDatabase, |
31 | /// Lowered patterns from self.body.pats plus generated by the check. | 296 | /// Lowered patterns from self.body.pats plus generated by the check. |
@@ -33,7 +298,7 @@ pub(crate) struct MatchCheckCtx<'a> { | |||
33 | } | 298 | } |
34 | 299 | ||
35 | impl<'a> MatchCheckCtx<'a> { | 300 | impl<'a> MatchCheckCtx<'a> { |
36 | pub(super) fn is_uninhabited(&self, ty: &Ty) -> bool { | 301 | pub(super) fn is_uninhabited(&self, _ty: &Ty) -> bool { |
37 | // FIXME(iDawer) implement exhaustive_patterns feature. More info in: | 302 | // FIXME(iDawer) implement exhaustive_patterns feature. More info in: |
38 | // Tracking issue for RFC 1872: exhaustive_patterns feature https://github.com/rust-lang/rust/issues/51085 | 303 | // Tracking issue for RFC 1872: exhaustive_patterns feature https://github.com/rust-lang/rust/issues/51085 |
39 | false | 304 | false |
@@ -90,7 +355,7 @@ impl PatternFolder for LiteralExpander { | |||
90 | } | 355 | } |
91 | 356 | ||
92 | impl Pat { | 357 | impl Pat { |
93 | fn is_wildcard(&self) -> bool { | 358 | fn _is_wildcard(&self) -> bool { |
94 | matches!(*self.kind, PatKind::Binding { subpattern: None, .. } | PatKind::Wild) | 359 | matches!(*self.kind, PatKind::Binding { subpattern: None, .. } | PatKind::Wild) |
95 | } | 360 | } |
96 | } | 361 | } |
@@ -102,11 +367,11 @@ impl PatIdExt for PatId { | |||
102 | 367 | ||
103 | /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns. | 368 | /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns. |
104 | fn expand_or_pat(self, cx: &MatchCheckCtx<'_>) -> Vec<Self> { | 369 | fn expand_or_pat(self, cx: &MatchCheckCtx<'_>) -> Vec<Self> { |
105 | fn expand(pat: PatId, vec: &mut Vec<PatId>, mut pat_arena: &mut PatternArena) { | 370 | fn expand(pat: PatId, vec: &mut Vec<PatId>, pat_arena: &mut PatternArena) { |
106 | if let PatKind::Or { pats } = pat_arena[pat].kind.as_ref() { | 371 | if let PatKind::Or { pats } = pat_arena[pat].kind.as_ref() { |
107 | let pats = pats.clone(); | 372 | let pats = pats.clone(); |
108 | for pat in pats { | 373 | for pat in pats { |
109 | // TODO(iDawer): Ugh, I want to go back to references (PatId -> &Pat) | 374 | // FIXME(iDawer): Ugh, I want to go back to references (PatId -> &Pat) |
110 | let pat = pat_arena.alloc(pat.clone()); | 375 | let pat = pat_arena.alloc(pat.clone()); |
111 | expand(pat, vec, pat_arena); | 376 | expand(pat, vec, pat_arena); |
112 | } | 377 | } |
@@ -157,10 +422,6 @@ impl PatStack { | |||
157 | self.head_ctor.get_or_init(|| Constructor::from_pat(cx, self.head())) | 422 | self.head_ctor.get_or_init(|| Constructor::from_pat(cx, self.head())) |
158 | } | 423 | } |
159 | 424 | ||
160 | fn iter(&self) -> impl Iterator<Item = PatId> + '_ { | ||
161 | self.pats.iter().copied() | ||
162 | } | ||
163 | |||
164 | // Recursively expand the first pattern into its subpatterns. Only useful if the pattern is an | 425 | // Recursively expand the first pattern into its subpatterns. Only useful if the pattern is an |
165 | // or-pattern. Panics if `self` is empty. | 426 | // or-pattern. Panics if `self` is empty. |
166 | fn expand_or_pat(&self, cx: &MatchCheckCtx<'_>) -> impl Iterator<Item = PatStack> + '_ { | 427 | fn expand_or_pat(&self, cx: &MatchCheckCtx<'_>) -> impl Iterator<Item = PatStack> + '_ { |
@@ -224,7 +485,7 @@ impl Matrix { | |||
224 | } | 485 | } |
225 | 486 | ||
226 | /// Number of columns of this matrix. `None` is the matrix is empty. | 487 | /// Number of columns of this matrix. `None` is the matrix is empty. |
227 | pub(super) fn column_count(&self) -> Option<usize> { | 488 | pub(super) fn _column_count(&self) -> Option<usize> { |
228 | self.patterns.get(0).map(|r| r.len()) | 489 | self.patterns.get(0).map(|r| r.len()) |
229 | } | 490 | } |
230 | 491 | ||
@@ -770,7 +1031,6 @@ fn is_useful( | |||
770 | assert!(rows.iter().all(|r| r.len() == v.len())); | 1031 | assert!(rows.iter().all(|r| r.len() == v.len())); |
771 | 1032 | ||
772 | // FIXME(Nadrieril): Hack to work around type normalization issues (see rust-lang/rust#72476). | 1033 | // FIXME(Nadrieril): Hack to work around type normalization issues (see rust-lang/rust#72476). |
773 | // TODO(iDawer): ty.strip_references() ? | ||
774 | let ty = matrix.heads().next().map_or(cx.type_of(v.head()), |r| cx.type_of(r)); | 1034 | let ty = matrix.heads().next().map_or(cx.type_of(v.head()), |r| cx.type_of(r)); |
775 | let pcx = PatCtxt { cx, ty: &ty, is_top_level }; | 1035 | let pcx = PatCtxt { cx, ty: &ty, is_top_level }; |
776 | 1036 | ||
@@ -848,7 +1108,7 @@ pub(crate) enum Reachability { | |||
848 | /// The output of checking a match for exhaustiveness and arm reachability. | 1108 | /// The output of checking a match for exhaustiveness and arm reachability. |
849 | pub(crate) struct UsefulnessReport { | 1109 | pub(crate) struct UsefulnessReport { |
850 | /// For each arm of the input, whether that arm is reachable after the arms above it. | 1110 | /// For each arm of the input, whether that arm is reachable after the arms above it. |
851 | pub(crate) arm_usefulness: Vec<(MatchArm, Reachability)>, | 1111 | pub(crate) _arm_usefulness: Vec<(MatchArm, Reachability)>, |
852 | /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of | 1112 | /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of |
853 | /// exhaustiveness. | 1113 | /// exhaustiveness. |
854 | pub(crate) non_exhaustiveness_witnesses: Vec<Pat>, | 1114 | pub(crate) non_exhaustiveness_witnesses: Vec<Pat>, |
@@ -892,14 +1152,12 @@ pub(crate) fn compute_match_usefulness( | |||
892 | WithWitnesses(pats) => pats.into_iter().map(Witness::single_pattern).collect(), | 1152 | WithWitnesses(pats) => pats.into_iter().map(Witness::single_pattern).collect(), |
893 | NoWitnesses(_) => panic!("bug"), | 1153 | NoWitnesses(_) => panic!("bug"), |
894 | }; | 1154 | }; |
895 | UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses } | 1155 | UsefulnessReport { _arm_usefulness: arm_usefulness, non_exhaustiveness_witnesses } |
896 | } | 1156 | } |
897 | 1157 | ||
898 | pub(crate) type PatternArena = Arena<Pat>; | 1158 | pub(crate) type PatternArena = Arena<Pat>; |
899 | 1159 | ||
900 | mod helper { | 1160 | mod helper { |
901 | use hir_def::expr::{Pat, PatId}; | ||
902 | |||
903 | use super::MatchCheckCtx; | 1161 | use super::MatchCheckCtx; |
904 | 1162 | ||
905 | pub(super) trait PatIdExt: Sized { | 1163 | pub(super) trait PatIdExt: Sized { |
@@ -920,6 +1178,3 @@ mod helper { | |||
920 | 1178 | ||
921 | impl<'a, T: ?Sized> Captures<'a> for T {} | 1179 | impl<'a, T: ?Sized> Captures<'a> for T {} |
922 | } | 1180 | } |
923 | |||
924 | #[test] | ||
925 | fn it_works() {} | ||