From 26baab5d2836eb5affd93d1991b3e96853f13869 Mon Sep 17 00:00:00 2001 From: Dawer <7803845+iDawer@users.noreply.github.com> Date: Wed, 28 Apr 2021 23:25:01 +0500 Subject: Enable generation of non-exhaustiveness witnesses --- crates/hir_ty/src/diagnostics/expr.rs | 3 +- .../src/diagnostics/pattern/deconstruct_pat.rs | 2 +- .../hir_ty/src/diagnostics/pattern/usefulness.rs | 84 +++++++++++++++++++--- 3 files changed, 76 insertions(+), 13 deletions(-) (limited to 'crates') 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> { } else { &infer.type_of_expr[match_expr] }; - eprintln!("ExprValidator::validate_match2({:?})", match_expr_ty.kind(&Interner)); + // eprintln!("ExprValidator::validate_match2({:?})", match_expr_ty.kind(&Interner)); let pattern_arena = usefulness::PatternArena::clone_from(&body.pats); let cx = usefulness::MatchCheckCtx { @@ -408,6 +408,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> { // } let witnesses = report.non_exhaustiveness_witnesses; + eprintln!("compute_match_usefulness(..) -> {:?}", &witnesses); if !witnesses.is_empty() { if let Ok(source_ptr) = source_map.expr_syntax(id) { 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 { } } + /// Determines the constructor that the given pattern can be specialized to. pub(super) fn from_pat(cx: &MatchCheckCtx<'_>, pat: PatId) -> Self { match &cx.pattern_arena.borrow()[pat] { Pat::Bind { .. } | Pat::Wild => Wildcard, @@ -312,7 +313,6 @@ impl SplitWildcard { // // The exception is: if we are at the top-level, for example in an empty match, we // sometimes prefer reporting the list of constructors instead of just `_`. - let report_when_all_missing = pcx.is_top_level && !IntRange::is_integral(&pcx.ty); let ctor = if !self.matrix_ctors.is_empty() || report_when_all_missing { 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 for PatStack { } } +/// A 2D matrix. #[derive(Clone)] pub(super) struct Matrix { patterns: Vec, @@ -321,6 +322,10 @@ impl SubPatSet { } _ => panic!("bug"), } + + if self.is_full() { + *self = Full; + } } /// Returns a list of the spans of the unreachable subpatterns. If `self` is empty (i.e. the @@ -449,14 +454,37 @@ impl Usefulness { ) -> Self { match self { WithWitnesses(witnesses) if witnesses.is_empty() => WithWitnesses(witnesses), - WithWitnesses(w) => { + WithWitnesses(witnesses) => { let new_witnesses = if matches!(ctor, Constructor::Missing) { let mut split_wildcard = SplitWildcard::new(pcx); split_wildcard.split(pcx, matrix.head_ctors(pcx.cx)); + // Construct for each missing constructor a "wild" version of this + // constructor, that matches everything that can be built with + // it. For example, if `ctor` is a `Constructor::Variant` for + // `Option::Some`, we get the pattern `Some(_)`. + let new_patterns: Vec<_> = split_wildcard + .iter_missing(pcx) + .map(|missing_ctor| { + Fields::wildcards(pcx, missing_ctor).apply(pcx, missing_ctor) + }) + .collect(); + witnesses + .into_iter() + .flat_map(|witness| { + new_patterns.iter().map(move |pat| { + let mut witness = witness.clone(); + witness.0.push(pat.clone()); + witness + }) + }) + .collect() } else { - todo!("Usefulness::apply_constructor({:?})", ctor) + witnesses + .into_iter() + .map(|witness| witness.apply_constructor(pcx, &ctor, ctor_wild_subpatterns)) + .collect() }; - todo!("Usefulness::apply_constructor({:?})", ctor) + WithWitnesses(new_witnesses) } NoWitnesses(subpats) => NoWitnesses(subpats.unspecialize(ctor_wild_subpatterns.len())), } @@ -469,6 +497,39 @@ enum WitnessPreference { LeaveOutWitness, } +/// A witness of non-exhaustiveness for error reporting, represented +/// as a list of patterns (in reverse order of construction) with +/// wildcards inside to represent elements that can take any inhabitant +/// of the type as a value. +/// +/// A witness against a list of patterns should have the same types +/// and length as the pattern matched against. Because Rust `match` +/// is always against a single pattern, at the end the witness will +/// have length 1, but in the middle of the algorithm, it can contain +/// multiple patterns. +/// +/// For example, if we are constructing a witness for the match against +/// +/// ``` +/// struct Pair(Option<(u32, u32)>, bool); +/// +/// match (p: Pair) { +/// Pair(None, _) => {} +/// Pair(_, false) => {} +/// } +/// ``` +/// +/// We'll perform the following steps: +/// 1. Start with an empty witness +/// `Witness(vec![])` +/// 2. Push a witness `true` against the `false` +/// `Witness(vec![true])` +/// 3. Push a witness `Some(_)` against the `None` +/// `Witness(vec![true, Some(_)])` +/// 4. Apply the `Pair` constructor to the witnesses +/// `Witness(vec![Pair(Some(_), true)])` +/// +/// The final `Pair(Some(_), true)` is then the resulting witness. #[derive(Clone, Debug)] pub(crate) struct Witness(Vec); @@ -560,7 +621,7 @@ fn is_useful( assert!(rows.iter().all(|r| r.len() == v.len())); // FIXME(Nadrieril): Hack to work around type normalization issues (see rust-lang/rust#72476). - // TODO(iDawer): ty.as_reference() + // TODO(iDawer): ty.strip_references() ? let ty = matrix.heads().next().map_or(cx.type_of(v.head()), |r| cx.type_of(r)); let pcx = PatCtxt { cx, ty, is_top_level }; @@ -643,6 +704,11 @@ pub(crate) struct UsefulnessReport { pub(crate) non_exhaustiveness_witnesses: Vec, } +/// The entrypoint for the usefulness algorithm. Computes whether a match is exhaustive and which +/// of its arms are reachable. +/// +/// Note: the input patterns must have been lowered through +/// `check_match::MatchVisitor::lower_pattern`. pub(crate) fn compute_match_usefulness( cx: &MatchCheckCtx<'_>, arms: &[MatchArm], @@ -670,14 +736,10 @@ pub(crate) fn compute_match_usefulness( let wild_pattern = cx.pattern_arena.borrow_mut().alloc(Pat::Wild, &cx.infer[cx.match_expr]); let v = PatStack::from_pattern(wild_pattern); - let usefulness = is_useful(cx, &matrix, &v, LeaveOutWitness, false, true); + let usefulness = is_useful(cx, &matrix, &v, ConstructWitness, false, true); let non_exhaustiveness_witnesses = match usefulness { - // TODO: ConstructWitness - // WithWitnesses(pats) => pats.into_iter().map(Witness::single_pattern).collect(), - // NoWitnesses(_) => panic!("bug"), - NoWitnesses(subpats) if subpats.is_empty() => Vec::new(), - NoWitnesses(subpats) => vec![Pat::Wild], - WithWitnesses(..) => panic!("bug"), + WithWitnesses(pats) => pats.into_iter().map(Witness::single_pattern).collect(), + NoWitnesses(_) => panic!("bug"), }; UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses } } -- cgit v1.2.3