diff options
Diffstat (limited to 'crates/ra_hir_ty/src')
-rw-r--r-- | crates/ra_hir_ty/src/_match.rs | 80 |
1 files changed, 64 insertions, 16 deletions
diff --git a/crates/ra_hir_ty/src/_match.rs b/crates/ra_hir_ty/src/_match.rs index 91206adc3..8b9bdb7cd 100644 --- a/crates/ra_hir_ty/src/_match.rs +++ b/crates/ra_hir_ty/src/_match.rs | |||
@@ -2,7 +2,7 @@ | |||
2 | //! for match arms. | 2 | //! for match arms. |
3 | //! | 3 | //! |
4 | //! It is modeled on the rustc module `librustc_mir_build::hair::pattern::_match`, which | 4 | //! It is modeled on the rustc module `librustc_mir_build::hair::pattern::_match`, which |
5 | //! contains very detailed documentation about the match checking algorithm. | 5 | //! contains very detailed documentation about the algorithms used here. |
6 | use std::sync::Arc; | 6 | use std::sync::Arc; |
7 | 7 | ||
8 | use smallvec::{smallvec, SmallVec}; | 8 | use smallvec::{smallvec, SmallVec}; |
@@ -15,6 +15,14 @@ use crate::{ | |||
15 | use hir_def::{adt::VariantData, EnumVariantId, VariantId}; | 15 | use hir_def::{adt::VariantData, EnumVariantId, VariantId}; |
16 | 16 | ||
17 | #[derive(Debug, Clone, Copy)] | 17 | #[derive(Debug, Clone, Copy)] |
18 | /// Either a pattern from the source code being analyzed, represented as | ||
19 | /// as `PatId`, or a `Wild` pattern which is created as an intermediate | ||
20 | /// step in the match checking algorithm and thus is not backed by a | ||
21 | /// real `PatId`. | ||
22 | /// | ||
23 | /// Note that it is totally valid for the `PatId` variant to contain | ||
24 | /// a `PatId` which resolves to a `Wild` pattern, if that wild pattern | ||
25 | /// exists in the source code being analyzed. | ||
18 | enum PatIdOrWild { | 26 | enum PatIdOrWild { |
19 | PatId(PatId), | 27 | PatId(PatId), |
20 | Wild, | 28 | Wild, |
@@ -44,11 +52,22 @@ impl From<PatId> for PatIdOrWild { | |||
44 | 52 | ||
45 | #[derive(Debug, Clone, Copy, PartialEq)] | 53 | #[derive(Debug, Clone, Copy, PartialEq)] |
46 | pub struct MatchCheckNotImplemented; | 54 | pub struct MatchCheckNotImplemented; |
55 | |||
56 | /// The return type of `is_useful` is either an indication of usefulness | ||
57 | /// of the match arm, or an error in the case the match statement | ||
58 | /// is made up of types for which exhaustiveness checking is currently | ||
59 | /// not completely implemented. | ||
60 | /// | ||
61 | /// The `std::result::Result` type is used here rather than a custom enum | ||
62 | /// to allow the use of `?`. | ||
47 | pub type MatchCheckResult<T> = Result<T, MatchCheckNotImplemented>; | 63 | pub type MatchCheckResult<T> = Result<T, MatchCheckNotImplemented>; |
48 | 64 | ||
49 | type PatStackInner = SmallVec<[PatIdOrWild; 2]>; | ||
50 | #[derive(Debug)] | 65 | #[derive(Debug)] |
66 | /// A row in a Matrix. | ||
67 | /// | ||
68 | /// This type is modeled from the struct of the same name in `rustc`. | ||
51 | pub(crate) struct PatStack(PatStackInner); | 69 | pub(crate) struct PatStack(PatStackInner); |
70 | type PatStackInner = SmallVec<[PatIdOrWild; 2]>; | ||
52 | 71 | ||
53 | impl PatStack { | 72 | impl PatStack { |
54 | pub(crate) fn from_pattern(pat_id: PatId) -> PatStack { | 73 | pub(crate) fn from_pattern(pat_id: PatId) -> PatStack { |
@@ -94,7 +113,9 @@ impl PatStack { | |||
94 | PatStack::from_vec(patterns) | 113 | PatStack::from_vec(patterns) |
95 | } | 114 | } |
96 | 115 | ||
97 | // Computes `D(self)`. | 116 | /// Computes `D(self)`. |
117 | /// | ||
118 | /// See the module docs and the associated documentation in rustc for details. | ||
98 | fn specialize_wildcard(&self, cx: &MatchCheckCtx) -> Option<PatStack> { | 119 | fn specialize_wildcard(&self, cx: &MatchCheckCtx) -> Option<PatStack> { |
99 | if matches!(self.head().as_pat(cx), Pat::Wild) { | 120 | if matches!(self.head().as_pat(cx), Pat::Wild) { |
100 | Some(self.to_tail()) | 121 | Some(self.to_tail()) |
@@ -103,7 +124,9 @@ impl PatStack { | |||
103 | } | 124 | } |
104 | } | 125 | } |
105 | 126 | ||
106 | // Computes `S(constructor, self)`. | 127 | /// Computes `S(constructor, self)`. |
128 | /// | ||
129 | /// See the module docs and the associated documentation in rustc for details. | ||
107 | fn specialize_constructor( | 130 | fn specialize_constructor( |
108 | &self, | 131 | &self, |
109 | cx: &MatchCheckCtx, | 132 | cx: &MatchCheckCtx, |
@@ -146,6 +169,11 @@ impl PatStack { | |||
146 | Ok(result) | 169 | Ok(result) |
147 | } | 170 | } |
148 | 171 | ||
172 | /// A special case of `specialize_constructor` where the head of the pattern stack | ||
173 | /// is a Wild pattern. | ||
174 | /// | ||
175 | /// Replaces the Wild pattern at the head of the pattern stack with N Wild patterns | ||
176 | /// (N >= 0), where N is the arity of the given constructor. | ||
149 | fn expand_wildcard( | 177 | fn expand_wildcard( |
150 | &self, | 178 | &self, |
151 | cx: &MatchCheckCtx, | 179 | cx: &MatchCheckCtx, |
@@ -183,6 +211,9 @@ impl PatStack { | |||
183 | } | 211 | } |
184 | 212 | ||
185 | #[derive(Debug)] | 213 | #[derive(Debug)] |
214 | /// A collection of PatStack. | ||
215 | /// | ||
216 | /// This type is modeled from the struct of the same name in `rustc`. | ||
186 | pub(crate) struct Matrix(Vec<PatStack>); | 217 | pub(crate) struct Matrix(Vec<PatStack>); |
187 | 218 | ||
188 | impl Matrix { | 219 | impl Matrix { |
@@ -191,8 +222,8 @@ impl Matrix { | |||
191 | } | 222 | } |
192 | 223 | ||
193 | pub(crate) fn push(&mut self, cx: &MatchCheckCtx, row: PatStack) { | 224 | pub(crate) fn push(&mut self, cx: &MatchCheckCtx, row: PatStack) { |
194 | // if the pattern is an or pattern it should be expanded | ||
195 | if let Some(Pat::Or(pat_ids)) = row.get_head().map(|pat_id| pat_id.as_pat(cx)) { | 225 | if let Some(Pat::Or(pat_ids)) = row.get_head().map(|pat_id| pat_id.as_pat(cx)) { |
226 | // Or patterns are expanded here | ||
196 | for pat_id in pat_ids { | 227 | for pat_id in pat_ids { |
197 | self.0.push(PatStack::from_pattern(pat_id)); | 228 | self.0.push(PatStack::from_pattern(pat_id)); |
198 | } | 229 | } |
@@ -209,12 +240,16 @@ impl Matrix { | |||
209 | self.0.iter().map(|p| p.head()).collect() | 240 | self.0.iter().map(|p| p.head()).collect() |
210 | } | 241 | } |
211 | 242 | ||
212 | // Computes `D(self)`. | 243 | /// Computes `D(self)` for each contained PatStack. |
244 | /// | ||
245 | /// See the module docs and the associated documentation in rustc for details. | ||
213 | fn specialize_wildcard(&self, cx: &MatchCheckCtx) -> Self { | 246 | fn specialize_wildcard(&self, cx: &MatchCheckCtx) -> Self { |
214 | Self::collect(cx, self.0.iter().filter_map(|r| r.specialize_wildcard(cx))) | 247 | Self::collect(cx, self.0.iter().filter_map(|r| r.specialize_wildcard(cx))) |
215 | } | 248 | } |
216 | 249 | ||
217 | // Computes `S(constructor, self)`. | 250 | /// Computes `S(constructor, self)` for each contained PatStack. |
251 | /// | ||
252 | /// See the module docs and the associated documentation in rustc for details. | ||
218 | fn specialize_constructor( | 253 | fn specialize_constructor( |
219 | &self, | 254 | &self, |
220 | cx: &MatchCheckCtx, | 255 | cx: &MatchCheckCtx, |
@@ -243,6 +278,11 @@ impl Matrix { | |||
243 | } | 278 | } |
244 | 279 | ||
245 | #[derive(Clone, Debug, PartialEq)] | 280 | #[derive(Clone, Debug, PartialEq)] |
281 | /// An indication of the usefulness of a given match arm, where | ||
282 | /// usefulness is defined as matching some patterns which were | ||
283 | /// not matched by an prior match arms. | ||
284 | /// | ||
285 | /// We may eventually need an `Unknown` variant here. | ||
246 | pub enum Usefulness { | 286 | pub enum Usefulness { |
247 | Useful, | 287 | Useful, |
248 | NotUseful, | 288 | NotUseful, |
@@ -257,6 +297,11 @@ pub struct MatchCheckCtx<'a> { | |||
257 | /// Given a set of patterns `matrix`, and pattern to consider `v`, determines | 297 | /// Given a set of patterns `matrix`, and pattern to consider `v`, determines |
258 | /// whether `v` is useful. A pattern is useful if it covers cases which were | 298 | /// whether `v` is useful. A pattern is useful if it covers cases which were |
259 | /// not previously covered. | 299 | /// not previously covered. |
300 | /// | ||
301 | /// When calling this function externally (that is, not the recursive calls) it | ||
302 | /// expected that you have already type checked the match arms. All patterns in | ||
303 | /// matrix should be the same type as v, as well as they should all be the same | ||
304 | /// type as the match expression. | ||
260 | pub(crate) fn is_useful( | 305 | pub(crate) fn is_useful( |
261 | cx: &MatchCheckCtx, | 306 | cx: &MatchCheckCtx, |
262 | matrix: &Matrix, | 307 | matrix: &Matrix, |
@@ -311,8 +356,9 @@ pub(crate) fn is_useful( | |||
311 | // We assume here that the first constructor is the "correct" type. Since we | 356 | // We assume here that the first constructor is the "correct" type. Since we |
312 | // only care about the "type" of the constructor (i.e. if it is a bool we | 357 | // only care about the "type" of the constructor (i.e. if it is a bool we |
313 | // don't care about the value), this assumption should be valid as long as | 358 | // don't care about the value), this assumption should be valid as long as |
314 | // the match statement is well formed. But potentially a better way to handle | 359 | // the match statement is well formed. We currently uphold this invariant by |
315 | // this is to use the match expressions type. | 360 | // filtering match arms before calling `is_useful`, only passing in match arms |
361 | // whose type matches the type of the match expression. | ||
316 | match &used_constructors.first() { | 362 | match &used_constructors.first() { |
317 | Some(constructor) if all_constructors_covered(&cx, constructor, &used_constructors) => { | 363 | Some(constructor) if all_constructors_covered(&cx, constructor, &used_constructors) => { |
318 | // If all constructors are covered, then we need to consider whether | 364 | // If all constructors are covered, then we need to consider whether |
@@ -380,23 +426,25 @@ pub(crate) fn is_useful( | |||
380 | } | 426 | } |
381 | 427 | ||
382 | #[derive(Debug)] | 428 | #[derive(Debug)] |
429 | /// Similar to TypeCtor, but includes additional information about the specific | ||
430 | /// value being instantiated. For example, TypeCtor::Bool doesn't contain the | ||
431 | /// boolean value. | ||
383 | enum Constructor { | 432 | enum Constructor { |
384 | Bool(bool), | 433 | Bool(bool), |
385 | Tuple { arity: usize }, | 434 | Tuple { arity: usize }, |
386 | Enum(EnumVariantId), | 435 | Enum(EnumVariantId), |
387 | } | 436 | } |
388 | 437 | ||
438 | /// Returns the constructor for the given pattern. Should only return None | ||
439 | /// in the case of a Wild pattern. | ||
389 | fn pat_constructor(cx: &MatchCheckCtx, pat: PatIdOrWild) -> MatchCheckResult<Option<Constructor>> { | 440 | fn pat_constructor(cx: &MatchCheckCtx, pat: PatIdOrWild) -> MatchCheckResult<Option<Constructor>> { |
390 | let res = match pat.as_pat(cx) { | 441 | let res = match pat.as_pat(cx) { |
391 | Pat::Wild => None, | 442 | Pat::Wild => None, |
392 | Pat::Tuple(pats) => Some(Constructor::Tuple { arity: pats.len() }), | 443 | Pat::Tuple(pats) => Some(Constructor::Tuple { arity: pats.len() }), |
393 | Pat::Lit(lit_expr) => { | 444 | Pat::Lit(lit_expr) => match cx.body.exprs[lit_expr] { |
394 | // for now we only support bool literals | 445 | Expr::Literal(Literal::Bool(val)) => Some(Constructor::Bool(val)), |
395 | match cx.body.exprs[lit_expr] { | 446 | _ => return Err(MatchCheckNotImplemented), |
396 | Expr::Literal(Literal::Bool(val)) => Some(Constructor::Bool(val)), | 447 | }, |
397 | _ => return Err(MatchCheckNotImplemented), | ||
398 | } | ||
399 | } | ||
400 | Pat::TupleStruct { .. } | Pat::Path(_) => { | 448 | Pat::TupleStruct { .. } | Pat::Path(_) => { |
401 | let pat_id = pat.as_id().expect("we already know this pattern is not a wild"); | 449 | let pat_id = pat.as_id().expect("we already know this pattern is not a wild"); |
402 | let variant_id = | 450 | let variant_id = |