aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty
diff options
context:
space:
mode:
authorDawer <[email protected]>2021-04-28 19:25:01 +0100
committerDawer <[email protected]>2021-05-31 20:03:45 +0100
commit26baab5d2836eb5affd93d1991b3e96853f13869 (patch)
tree58a34d9449743150e6e0e9d256742aa9d8cc0653 /crates/hir_ty
parentc3c2893f302d087ff3c1ddd3a1d4e88c03c4356b (diff)
Enable generation of non-exhaustiveness witnesses
Diffstat (limited to 'crates/hir_ty')
-rw-r--r--crates/hir_ty/src/diagnostics/expr.rs3
-rw-r--r--crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs2
-rw-r--r--crates/hir_ty/src/diagnostics/pattern/usefulness.rs84
3 files changed, 76 insertions, 13 deletions
diff --git a/crates/hir_ty/src/diagnostics/expr.rs b/crates/hir_ty/src/diagnostics/expr.rs
index ea70a5f9f..4d17e8c9a 100644
--- a/crates/hir_ty/src/diagnostics/expr.rs
+++ b/crates/hir_ty/src/diagnostics/expr.rs
@@ -378,7 +378,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
378 } else { 378 } else {
379 &infer.type_of_expr[match_expr] 379 &infer.type_of_expr[match_expr]
380 }; 380 };
381 eprintln!("ExprValidator::validate_match2({:?})", match_expr_ty.kind(&Interner)); 381 // eprintln!("ExprValidator::validate_match2({:?})", match_expr_ty.kind(&Interner));
382 382
383 let pattern_arena = usefulness::PatternArena::clone_from(&body.pats); 383 let pattern_arena = usefulness::PatternArena::clone_from(&body.pats);
384 let cx = usefulness::MatchCheckCtx { 384 let cx = usefulness::MatchCheckCtx {
@@ -408,6 +408,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
408 // } 408 // }
409 409
410 let witnesses = report.non_exhaustiveness_witnesses; 410 let witnesses = report.non_exhaustiveness_witnesses;
411 eprintln!("compute_match_usefulness(..) -> {:?}", &witnesses);
411 if !witnesses.is_empty() { 412 if !witnesses.is_empty() {
412 if let Ok(source_ptr) = source_map.expr_syntax(id) { 413 if let Ok(source_ptr) = source_map.expr_syntax(id) {
413 let root = source_ptr.file_syntax(db.upcast()); 414 let root = source_ptr.file_syntax(db.upcast());
diff --git a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
index cde04409e..2f3555205 100644
--- a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
+++ b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
@@ -109,6 +109,7 @@ impl Constructor {
109 } 109 }
110 } 110 }
111 111
112 /// Determines the constructor that the given pattern can be specialized to.
112 pub(super) fn from_pat(cx: &MatchCheckCtx<'_>, pat: PatId) -> Self { 113 pub(super) fn from_pat(cx: &MatchCheckCtx<'_>, pat: PatId) -> Self {
113 match &cx.pattern_arena.borrow()[pat] { 114 match &cx.pattern_arena.borrow()[pat] {
114 Pat::Bind { .. } | Pat::Wild => Wildcard, 115 Pat::Bind { .. } | Pat::Wild => Wildcard,
@@ -312,7 +313,6 @@ impl SplitWildcard {
312 // 313 //
313 // The exception is: if we are at the top-level, for example in an empty match, we 314 // The exception is: if we are at the top-level, for example in an empty match, we
314 // sometimes prefer reporting the list of constructors instead of just `_`. 315 // sometimes prefer reporting the list of constructors instead of just `_`.
315
316 let report_when_all_missing = pcx.is_top_level && !IntRange::is_integral(&pcx.ty); 316 let report_when_all_missing = pcx.is_top_level && !IntRange::is_integral(&pcx.ty);
317 let ctor = if !self.matrix_ctors.is_empty() || report_when_all_missing { 317 let ctor = if !self.matrix_ctors.is_empty() || report_when_all_missing {
318 Missing 318 Missing
diff --git a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
index f5f6bf494..89e6c6593 100644
--- a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
+++ b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
@@ -179,6 +179,7 @@ impl FromIterator<PatId> for PatStack {
179 } 179 }
180} 180}
181 181
182/// A 2D matrix.
182#[derive(Clone)] 183#[derive(Clone)]
183pub(super) struct Matrix { 184pub(super) struct Matrix {
184 patterns: Vec<PatStack>, 185 patterns: Vec<PatStack>,
@@ -321,6 +322,10 @@ impl SubPatSet {
321 } 322 }
322 _ => panic!("bug"), 323 _ => panic!("bug"),
323 } 324 }
325
326 if self.is_full() {
327 *self = Full;
328 }
324 } 329 }
325 330
326 /// Returns a list of the spans of the unreachable subpatterns. If `self` is empty (i.e. the 331 /// Returns a list of the spans of the unreachable subpatterns. If `self` is empty (i.e. the
@@ -449,14 +454,37 @@ impl Usefulness {
449 ) -> Self { 454 ) -> Self {
450 match self { 455 match self {
451 WithWitnesses(witnesses) if witnesses.is_empty() => WithWitnesses(witnesses), 456 WithWitnesses(witnesses) if witnesses.is_empty() => WithWitnesses(witnesses),
452 WithWitnesses(w) => { 457 WithWitnesses(witnesses) => {
453 let new_witnesses = if matches!(ctor, Constructor::Missing) { 458 let new_witnesses = if matches!(ctor, Constructor::Missing) {
454 let mut split_wildcard = SplitWildcard::new(pcx); 459 let mut split_wildcard = SplitWildcard::new(pcx);
455 split_wildcard.split(pcx, matrix.head_ctors(pcx.cx)); 460 split_wildcard.split(pcx, matrix.head_ctors(pcx.cx));
461 // Construct for each missing constructor a "wild" version of this
462 // constructor, that matches everything that can be built with
463 // it. For example, if `ctor` is a `Constructor::Variant` for
464 // `Option::Some`, we get the pattern `Some(_)`.
465 let new_patterns: Vec<_> = split_wildcard
466 .iter_missing(pcx)
467 .map(|missing_ctor| {
468 Fields::wildcards(pcx, missing_ctor).apply(pcx, missing_ctor)
469 })
470 .collect();
471 witnesses
472 .into_iter()
473 .flat_map(|witness| {
474 new_patterns.iter().map(move |pat| {
475 let mut witness = witness.clone();
476 witness.0.push(pat.clone());
477 witness
478 })
479 })
480 .collect()
456 } else { 481 } else {
457 todo!("Usefulness::apply_constructor({:?})", ctor) 482 witnesses
483 .into_iter()
484 .map(|witness| witness.apply_constructor(pcx, &ctor, ctor_wild_subpatterns))
485 .collect()
458 }; 486 };
459 todo!("Usefulness::apply_constructor({:?})", ctor) 487 WithWitnesses(new_witnesses)
460 } 488 }
461 NoWitnesses(subpats) => NoWitnesses(subpats.unspecialize(ctor_wild_subpatterns.len())), 489 NoWitnesses(subpats) => NoWitnesses(subpats.unspecialize(ctor_wild_subpatterns.len())),
462 } 490 }
@@ -469,6 +497,39 @@ enum WitnessPreference {
469 LeaveOutWitness, 497 LeaveOutWitness,
470} 498}
471 499
500/// A witness of non-exhaustiveness for error reporting, represented
501/// as a list of patterns (in reverse order of construction) with
502/// wildcards inside to represent elements that can take any inhabitant
503/// of the type as a value.
504///
505/// A witness against a list of patterns should have the same types
506/// and length as the pattern matched against. Because Rust `match`
507/// is always against a single pattern, at the end the witness will
508/// have length 1, but in the middle of the algorithm, it can contain
509/// multiple patterns.
510///
511/// For example, if we are constructing a witness for the match against
512///
513/// ```
514/// struct Pair(Option<(u32, u32)>, bool);
515///
516/// match (p: Pair) {
517/// Pair(None, _) => {}
518/// Pair(_, false) => {}
519/// }
520/// ```
521///
522/// We'll perform the following steps:
523/// 1. Start with an empty witness
524/// `Witness(vec![])`
525/// 2. Push a witness `true` against the `false`
526/// `Witness(vec![true])`
527/// 3. Push a witness `Some(_)` against the `None`
528/// `Witness(vec![true, Some(_)])`
529/// 4. Apply the `Pair` constructor to the witnesses
530/// `Witness(vec![Pair(Some(_), true)])`
531///
532/// The final `Pair(Some(_), true)` is then the resulting witness.
472#[derive(Clone, Debug)] 533#[derive(Clone, Debug)]
473pub(crate) struct Witness(Vec<Pat>); 534pub(crate) struct Witness(Vec<Pat>);
474 535
@@ -560,7 +621,7 @@ fn is_useful(
560 assert!(rows.iter().all(|r| r.len() == v.len())); 621 assert!(rows.iter().all(|r| r.len() == v.len()));
561 622
562 // FIXME(Nadrieril): Hack to work around type normalization issues (see rust-lang/rust#72476). 623 // FIXME(Nadrieril): Hack to work around type normalization issues (see rust-lang/rust#72476).
563 // TODO(iDawer): ty.as_reference() 624 // TODO(iDawer): ty.strip_references() ?
564 let ty = matrix.heads().next().map_or(cx.type_of(v.head()), |r| cx.type_of(r)); 625 let ty = matrix.heads().next().map_or(cx.type_of(v.head()), |r| cx.type_of(r));
565 let pcx = PatCtxt { cx, ty, is_top_level }; 626 let pcx = PatCtxt { cx, ty, is_top_level };
566 627
@@ -643,6 +704,11 @@ pub(crate) struct UsefulnessReport {
643 pub(crate) non_exhaustiveness_witnesses: Vec<Pat>, 704 pub(crate) non_exhaustiveness_witnesses: Vec<Pat>,
644} 705}
645 706
707/// The entrypoint for the usefulness algorithm. Computes whether a match is exhaustive and which
708/// of its arms are reachable.
709///
710/// Note: the input patterns must have been lowered through
711/// `check_match::MatchVisitor::lower_pattern`.
646pub(crate) fn compute_match_usefulness( 712pub(crate) fn compute_match_usefulness(
647 cx: &MatchCheckCtx<'_>, 713 cx: &MatchCheckCtx<'_>,
648 arms: &[MatchArm], 714 arms: &[MatchArm],
@@ -670,14 +736,10 @@ pub(crate) fn compute_match_usefulness(
670 736
671 let wild_pattern = cx.pattern_arena.borrow_mut().alloc(Pat::Wild, &cx.infer[cx.match_expr]); 737 let wild_pattern = cx.pattern_arena.borrow_mut().alloc(Pat::Wild, &cx.infer[cx.match_expr]);
672 let v = PatStack::from_pattern(wild_pattern); 738 let v = PatStack::from_pattern(wild_pattern);
673 let usefulness = is_useful(cx, &matrix, &v, LeaveOutWitness, false, true); 739 let usefulness = is_useful(cx, &matrix, &v, ConstructWitness, false, true);
674 let non_exhaustiveness_witnesses = match usefulness { 740 let non_exhaustiveness_witnesses = match usefulness {
675 // TODO: ConstructWitness 741 WithWitnesses(pats) => pats.into_iter().map(Witness::single_pattern).collect(),
676 // WithWitnesses(pats) => pats.into_iter().map(Witness::single_pattern).collect(), 742 NoWitnesses(_) => panic!("bug"),
677 // NoWitnesses(_) => panic!("bug"),
678 NoWitnesses(subpats) if subpats.is_empty() => Vec::new(),
679 NoWitnesses(subpats) => vec![Pat::Wild],
680 WithWitnesses(..) => panic!("bug"),
681 }; 743 };
682 UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses } 744 UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }
683} 745}