diff options
author | Dawer <[email protected]> | 2021-04-29 08:08:52 +0100 |
---|---|---|
committer | Dawer <[email protected]> | 2021-05-31 20:03:46 +0100 |
commit | 2880fd23206042cc3564d388d2f991cb91e76c39 (patch) | |
tree | 12af7479559d4255c3863bacf8811cc9d806e9e4 /crates/hir_ty/src | |
parent | f4c396036416eaa977876d8ff4afe7f58f93c09e (diff) |
Complete usefulness::SubPatSet impl
Diffstat (limited to 'crates/hir_ty/src')
-rw-r--r-- | crates/hir_ty/src/diagnostics/pattern/usefulness.rs | 74 |
1 files changed, 71 insertions, 3 deletions
diff --git a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs index 57a416bec..2e5d2fb6c 100644 --- a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs +++ b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs | |||
@@ -1,5 +1,5 @@ | |||
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 | // rust/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 | use std::{cell::RefCell, iter::FromIterator, ops::Index, sync::Arc}; |
5 | 5 | ||
@@ -245,6 +245,33 @@ impl Matrix { | |||
245 | } | 245 | } |
246 | } | 246 | } |
247 | 247 | ||
248 | /// Given a pattern or a pattern-stack, this struct captures a set of its subpatterns. We use that | ||
249 | /// to track reachable sub-patterns arising from or-patterns. In the absence of or-patterns this | ||
250 | /// will always be either `Empty` (the whole pattern is unreachable) or `Full` (the whole pattern | ||
251 | /// is reachable). When there are or-patterns, some subpatterns may be reachable while others | ||
252 | /// aren't. In this case the whole pattern still counts as reachable, but we will lint the | ||
253 | /// unreachable subpatterns. | ||
254 | /// | ||
255 | /// This supports a limited set of operations, so not all possible sets of subpatterns can be | ||
256 | /// represented. That's ok, we only want the ones that make sense for our usage. | ||
257 | /// | ||
258 | /// What we're doing is illustrated by this: | ||
259 | /// ``` | ||
260 | /// match (true, 0) { | ||
261 | /// (true, 0) => {} | ||
262 | /// (_, 1) => {} | ||
263 | /// (true | false, 0 | 1) => {} | ||
264 | /// } | ||
265 | /// ``` | ||
266 | /// When we try the alternatives of the `true | false` or-pattern, the last `0` is reachable in the | ||
267 | /// `false` alternative but not the `true`. So overall it is reachable. By contrast, the last `1` | ||
268 | /// is not reachable in either alternative, so we want to signal this to the user. | ||
269 | /// Therefore we take the union of sets of reachable patterns coming from different alternatives in | ||
270 | /// order to figure out which subpatterns are overall reachable. | ||
271 | /// | ||
272 | /// Invariant: we try to construct the smallest representation we can. In particular if | ||
273 | /// `self.is_empty()` we ensure that `self` is `Empty`, and same with `Full`. This is not important | ||
274 | /// for correctness currently. | ||
248 | #[derive(Debug, Clone)] | 275 | #[derive(Debug, Clone)] |
249 | enum SubPatSet { | 276 | enum SubPatSet { |
250 | /// The empty set. This means the pattern is unreachable. | 277 | /// The empty set. This means the pattern is unreachable. |
@@ -397,7 +424,24 @@ impl SubPatSet { | |||
397 | Full => Full, | 424 | Full => Full, |
398 | Empty => Empty, | 425 | Empty => Empty, |
399 | Seq { subpats } => { | 426 | Seq { subpats } => { |
400 | todo!() | 427 | // We gather the first `arity` subpatterns together and shift the remaining ones. |
428 | let mut new_subpats = FxHashMap::default(); | ||
429 | let mut new_subpats_first_col = FxHashMap::default(); | ||
430 | for (i, sub_set) in subpats { | ||
431 | if i < arity { | ||
432 | // The first `arity` indices are now part of the pattern in the first | ||
433 | // column. | ||
434 | new_subpats_first_col.insert(i, sub_set); | ||
435 | } else { | ||
436 | // Indices after `arity` are simply shifted | ||
437 | new_subpats.insert(i - arity + 1, sub_set); | ||
438 | } | ||
439 | } | ||
440 | // If `new_subpats_first_col` has no entries it counts as full, so we can omit it. | ||
441 | if !new_subpats_first_col.is_empty() { | ||
442 | new_subpats.insert(0, Seq { subpats: new_subpats_first_col }); | ||
443 | } | ||
444 | Seq { subpats: new_subpats } | ||
401 | } | 445 | } |
402 | Alt { .. } => panic!("bug"), | 446 | Alt { .. } => panic!("bug"), |
403 | } | 447 | } |
@@ -417,7 +461,31 @@ impl SubPatSet { | |||
417 | /// containing `false`. After `unsplit_or_pat`, we want the set to contain `None` and `false`. | 461 | /// containing `false`. After `unsplit_or_pat`, we want the set to contain `None` and `false`. |
418 | /// This is what this function does. | 462 | /// This is what this function does. |
419 | fn unsplit_or_pat(mut self, alt_id: usize, alt_count: usize, pat: PatId) -> Self { | 463 | fn unsplit_or_pat(mut self, alt_id: usize, alt_count: usize, pat: PatId) -> Self { |
420 | todo!() | 464 | use SubPatSet::*; |
465 | if self.is_empty() { | ||
466 | return Empty; | ||
467 | } | ||
468 | |||
469 | // Subpatterns coming from inside the or-pattern alternative itself, e.g. in `None | Some(0 | ||
470 | // | 1)`. | ||
471 | let set_first_col = match &mut self { | ||
472 | Full => Full, | ||
473 | Seq { subpats } => subpats.remove(&0).unwrap_or(Full), | ||
474 | Empty => unreachable!(), | ||
475 | Alt { .. } => panic!("bug"), // `self` is a patstack | ||
476 | }; | ||
477 | let mut subpats_first_col = FxHashMap::default(); | ||
478 | subpats_first_col.insert(alt_id, set_first_col); | ||
479 | let set_first_col = Alt { subpats: subpats_first_col, pat, alt_count }; | ||
480 | |||
481 | let mut subpats = match self { | ||
482 | Full => FxHashMap::default(), | ||
483 | Seq { subpats } => subpats, | ||
484 | Empty => unreachable!(), | ||
485 | Alt { .. } => panic!("bug"), // `self` is a patstack | ||
486 | }; | ||
487 | subpats.insert(0, set_first_col); | ||
488 | Seq { subpats } | ||
421 | } | 489 | } |
422 | } | 490 | } |
423 | 491 | ||