aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty
diff options
context:
space:
mode:
authorDawer <[email protected]>2021-04-22 16:17:27 +0100
committerDawer <[email protected]>2021-05-31 20:03:45 +0100
commitc3c2893f302d087ff3c1ddd3a1d4e88c03c4356b (patch)
treedc24743a4482f625b287c697f3ef17bfbfb9097f /crates/hir_ty
parent7c1d8ca63510bb719fd91bbf38692e45b19c04d6 (diff)
Update match checking.
fn is_useful , more skeletons Specify a lifetime on pattern references impl PatStack fill impl Matrix PatStack::pop_head_constructor Index-based approach struct PatCtxt fields construction fn Fields::wildcards split wildcard fn Constructor::is_covered_by_any(..) fn Matrix::specialize_constructor(..) impl Usefulness Initial work on witness construction Reorganize files Replace match checking diagnostic Handle types of expanded patterns unit match checking go brrr
Diffstat (limited to 'crates/hir_ty')
-rw-r--r--crates/hir_ty/Cargo.toml1
-rw-r--r--crates/hir_ty/src/diagnostics.rs2
-rw-r--r--crates/hir_ty/src/diagnostics/expr.rs70
-rw-r--r--crates/hir_ty/src/diagnostics/pattern.rs36
-rw-r--r--crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs627
-rw-r--r--crates/hir_ty/src/diagnostics/pattern/usefulness.rs736
6 files changed, 1471 insertions, 1 deletions
diff --git a/crates/hir_ty/Cargo.toml b/crates/hir_ty/Cargo.toml
index c3d02424d..4b714c6d8 100644
--- a/crates/hir_ty/Cargo.toml
+++ b/crates/hir_ty/Cargo.toml
@@ -22,6 +22,7 @@ chalk-solve = { version = "0.68", default-features = false }
22chalk-ir = "0.68" 22chalk-ir = "0.68"
23chalk-recursive = "0.68" 23chalk-recursive = "0.68"
24la-arena = { version = "0.2.0", path = "../../lib/arena" } 24la-arena = { version = "0.2.0", path = "../../lib/arena" }
25once_cell = { version = "1.5.0" }
25 26
26stdx = { path = "../stdx", version = "0.0.0" } 27stdx = { path = "../stdx", version = "0.0.0" }
27hir_def = { path = "../hir_def", version = "0.0.0" } 28hir_def = { path = "../hir_def", version = "0.0.0" }
diff --git a/crates/hir_ty/src/diagnostics.rs b/crates/hir_ty/src/diagnostics.rs
index 283894704..87a3594c5 100644
--- a/crates/hir_ty/src/diagnostics.rs
+++ b/crates/hir_ty/src/diagnostics.rs
@@ -1,6 +1,8 @@
1//! Type inference-based diagnostics. 1//! Type inference-based diagnostics.
2mod expr; 2mod expr;
3#[allow(unused)] //todo
3mod match_check; 4mod match_check;
5mod pattern;
4mod unsafe_check; 6mod unsafe_check;
5mod decl_check; 7mod decl_check;
6 8
diff --git a/crates/hir_ty/src/diagnostics/expr.rs b/crates/hir_ty/src/diagnostics/expr.rs
index 86f82e3fa..ea70a5f9f 100644
--- a/crates/hir_ty/src/diagnostics/expr.rs
+++ b/crates/hir_ty/src/diagnostics/expr.rs
@@ -62,7 +62,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
62 62
63 match expr { 63 match expr {
64 Expr::Match { expr, arms } => { 64 Expr::Match { expr, arms } => {
65 self.validate_match(id, *expr, arms, db, self.infer.clone()); 65 self.validate_match2(id, *expr, arms, db, self.infer.clone());
66 } 66 }
67 Expr::Call { .. } | Expr::MethodCall { .. } => { 67 Expr::Call { .. } | Expr::MethodCall { .. } => {
68 self.validate_call(db, id, expr); 68 self.validate_call(db, id, expr);
@@ -277,6 +277,7 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
277 } 277 }
278 } 278 }
279 279
280 #[allow(dead_code)]
280 fn validate_match( 281 fn validate_match(
281 &mut self, 282 &mut self,
282 id: ExprId, 283 id: ExprId,
@@ -358,6 +359,73 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
358 } 359 }
359 } 360 }
360 361
362 fn validate_match2(
363 &mut self,
364 id: ExprId,
365 match_expr: ExprId,
366 arms: &[MatchArm],
367 db: &dyn HirDatabase,
368 infer: Arc<InferenceResult>,
369 ) {
370 use crate::diagnostics::pattern::usefulness;
371 use hir_def::HasModule;
372
373 let (body, source_map): (Arc<Body>, Arc<BodySourceMap>) =
374 db.body_with_source_map(self.owner);
375
376 let match_expr_ty = if infer.type_of_expr[match_expr].is_unknown() {
377 return;
378 } else {
379 &infer.type_of_expr[match_expr]
380 };
381 eprintln!("ExprValidator::validate_match2({:?})", match_expr_ty.kind(&Interner));
382
383 let pattern_arena = usefulness::PatternArena::clone_from(&body.pats);
384 let cx = usefulness::MatchCheckCtx {
385 krate: self.owner.module(db.upcast()).krate(),
386 match_expr,
387 body,
388 infer: &infer,
389 db,
390 pattern_arena: &pattern_arena,
391 };
392
393 let m_arms: Vec<_> = arms
394 .iter()
395 .map(|arm| usefulness::MatchArm { pat: arm.pat, has_guard: arm.guard.is_some() })
396 .collect();
397
398 let report = usefulness::compute_match_usefulness(&cx, &m_arms);
399
400 // TODO Report unreacheble arms
401 // let mut catchall = None;
402 // for (arm_index, (arm, is_useful)) in report.arm_usefulness.iter().enumerate() {
403 // match is_useful{
404 // Unreachable => {
405 // }
406 // Reachable(_) => {}
407 // }
408 // }
409
410 let witnesses = report.non_exhaustiveness_witnesses;
411 if !witnesses.is_empty() {
412 if let Ok(source_ptr) = source_map.expr_syntax(id) {
413 let root = source_ptr.file_syntax(db.upcast());
414 if let ast::Expr::MatchExpr(match_expr) = &source_ptr.value.to_node(&root) {
415 if let (Some(match_expr), Some(arms)) =
416 (match_expr.expr(), match_expr.match_arm_list())
417 {
418 self.sink.push(MissingMatchArms {
419 file: source_ptr.file_id,
420 match_expr: AstPtr::new(&match_expr),
421 arms: AstPtr::new(&arms),
422 })
423 }
424 }
425 }
426 }
427 }
428
361 fn validate_results_in_tail_expr(&mut self, body_id: ExprId, id: ExprId, db: &dyn HirDatabase) { 429 fn validate_results_in_tail_expr(&mut self, body_id: ExprId, id: ExprId, db: &dyn HirDatabase) {
362 // the mismatch will be on the whole block currently 430 // the mismatch will be on the whole block currently
363 let mismatch = match self.infer.type_mismatch_for_expr(body_id) { 431 let mismatch = match self.infer.type_mismatch_for_expr(body_id) {
diff --git a/crates/hir_ty/src/diagnostics/pattern.rs b/crates/hir_ty/src/diagnostics/pattern.rs
new file mode 100644
index 000000000..28c7a244d
--- /dev/null
+++ b/crates/hir_ty/src/diagnostics/pattern.rs
@@ -0,0 +1,36 @@
1#![deny(elided_lifetimes_in_paths)]
2#![allow(unused)] // todo remove
3
4mod deconstruct_pat;
5pub mod usefulness;
6
7#[cfg(test)]
8mod tests {
9 use crate::diagnostics::tests::check_diagnostics;
10
11 use super::*;
12
13 #[test]
14 fn unit_exhaustive() {
15 check_diagnostics(
16 r#"
17fn main() {
18 match () { () => {} }
19 match () { _ => {} }
20}
21"#,
22 );
23 }
24
25 #[test]
26 fn unit_non_exhaustive() {
27 check_diagnostics(
28 r#"
29fn main() {
30 match () { }
31 //^^ Missing match arm
32}
33"#,
34 );
35 }
36}
diff --git a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
new file mode 100644
index 000000000..cde04409e
--- /dev/null
+++ b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
@@ -0,0 +1,627 @@
1use hir_def::{
2 expr::{Pat, PatId},
3 AttrDefId, EnumVariantId, HasModule, VariantId,
4};
5
6use smallvec::{smallvec, SmallVec};
7
8use crate::{AdtId, Interner, Scalar, Ty, TyExt, TyKind};
9
10use super::usefulness::{MatchCheckCtx, PatCtxt};
11
12use self::Constructor::*;
13
14#[derive(Copy, Clone, Debug, PartialEq, Eq)]
15pub(super) enum ToDo {}
16
17#[derive(Clone, Debug, PartialEq, Eq)]
18pub(super) struct IntRange {
19 range: ToDo,
20}
21
22impl IntRange {
23 #[inline]
24 fn is_integral(ty: &Ty) -> bool {
25 match ty.kind(&Interner) {
26 TyKind::Scalar(Scalar::Char)
27 | TyKind::Scalar(Scalar::Int(_))
28 | TyKind::Scalar(Scalar::Uint(_))
29 | TyKind::Scalar(Scalar::Bool) => true,
30 _ => false,
31 }
32 }
33
34 /// See `Constructor::is_covered_by`
35 fn is_covered_by(&self, other: &Self) -> bool {
36 todo!()
37 }
38}
39
40/// A constructor for array and slice patterns.
41#[derive(Copy, Clone, Debug, PartialEq, Eq)]
42pub(super) struct Slice {
43 todo: ToDo,
44}
45
46impl Slice {
47 /// See `Constructor::is_covered_by`
48 fn is_covered_by(self, other: Self) -> bool {
49 todo!()
50 }
51}
52
53/// A value can be decomposed into a constructor applied to some fields. This struct represents
54/// the constructor. See also `Fields`.
55///
56/// `pat_constructor` retrieves the constructor corresponding to a pattern.
57/// `specialize_constructor` returns the list of fields corresponding to a pattern, given a
58/// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and
59/// `Fields`.
60#[derive(Clone, Debug, PartialEq)]
61pub(super) enum Constructor {
62 /// The constructor for patterns that have a single constructor, like tuples, struct patterns
63 /// and fixed-length arrays.
64 Single,
65 /// Enum variants.
66 Variant(EnumVariantId),
67 /// Ranges of integer literal values (`2`, `2..=5` or `2..5`).
68 IntRange(IntRange),
69 /// Array and slice patterns.
70 Slice(Slice),
71 /// Stands for constructors that are not seen in the matrix, as explained in the documentation
72 /// for [`SplitWildcard`].
73 Missing,
74 /// Wildcard pattern.
75 Wildcard,
76}
77
78impl Constructor {
79 pub(super) fn is_wildcard(&self) -> bool {
80 matches!(self, Wildcard)
81 }
82
83 fn as_int_range(&self) -> Option<&IntRange> {
84 match self {
85 IntRange(range) => Some(range),
86 _ => None,
87 }
88 }
89
90 fn as_slice(&self) -> Option<Slice> {
91 match self {
92 Slice(slice) => Some(*slice),
93 _ => None,
94 }
95 }
96
97 fn variant_id_for_adt(&self, adt: hir_def::AdtId, cx: &MatchCheckCtx<'_>) -> VariantId {
98 match *self {
99 Variant(id) => id.into(),
100 Single => {
101 assert!(!matches!(adt, hir_def::AdtId::EnumId(_)));
102 match adt {
103 hir_def::AdtId::EnumId(_) => unreachable!(),
104 hir_def::AdtId::StructId(id) => id.into(),
105 hir_def::AdtId::UnionId(id) => id.into(),
106 }
107 }
108 _ => panic!("bad constructor {:?} for adt {:?}", self, adt),
109 }
110 }
111
112 pub(super) fn from_pat(cx: &MatchCheckCtx<'_>, pat: PatId) -> Self {
113 match &cx.pattern_arena.borrow()[pat] {
114 Pat::Bind { .. } | Pat::Wild => Wildcard,
115 Pat::Tuple { .. } | Pat::Ref { .. } | Pat::Box { .. } => Single,
116
117 pat => todo!("Constructor::from_pat {:?}", pat),
118 // Pat::Missing => {}
119 // Pat::Or(_) => {}
120 // Pat::Record { path, args, ellipsis } => {}
121 // Pat::Range { start, end } => {}
122 // Pat::Slice { prefix, slice, suffix } => {}
123 // Pat::Path(_) => {}
124 // Pat::Lit(_) => {}
125 // Pat::TupleStruct { path, args, ellipsis } => {}
126 // Pat::ConstBlock(_) => {}
127 }
128 }
129
130 /// Some constructors (namely `Wildcard`, `IntRange` and `Slice`) actually stand for a set of actual
131 /// constructors (like variants, integers or fixed-sized slices). When specializing for these
132 /// constructors, we want to be specialising for the actual underlying constructors.
133 /// Naively, we would simply return the list of constructors they correspond to. We instead are
134 /// more clever: if there are constructors that we know will behave the same wrt the current
135 /// matrix, we keep them grouped. For example, all slices of a sufficiently large length
136 /// will either be all useful or all non-useful with a given matrix.
137 ///
138 /// See the branches for details on how the splitting is done.
139 ///
140 /// This function may discard some irrelevant constructors if this preserves behavior and
141 /// diagnostics. Eg. for the `_` case, we ignore the constructors already present in the
142 /// matrix, unless all of them are.
143 pub(super) fn split<'a>(
144 &self,
145 pcx: &PatCtxt<'_>,
146 ctors: impl Iterator<Item = &'a Constructor> + Clone,
147 ) -> SmallVec<[Self; 1]> {
148 match self {
149 Wildcard => {
150 let mut split_wildcard = SplitWildcard::new(pcx);
151 split_wildcard.split(pcx, ctors);
152 split_wildcard.into_ctors(pcx)
153 }
154 // Fast-track if the range is trivial. In particular, we don't do the overlapping
155 // ranges check.
156 IntRange(_) => todo!("Constructor::split IntRange"),
157 Slice(_) => todo!("Constructor::split Slice"),
158 // Any other constructor can be used unchanged.
159 _ => smallvec![self.clone()],
160 }
161 }
162
163 /// Returns whether `self` is covered by `other`, i.e. whether `self` is a subset of `other`.
164 /// For the simple cases, this is simply checking for equality. For the "grouped" constructors,
165 /// this checks for inclusion.
166 // We inline because this has a single call site in `Matrix::specialize_constructor`.
167 #[inline]
168 pub(super) fn is_covered_by(&self, pcx: &PatCtxt<'_>, other: &Self) -> bool {
169 // This must be kept in sync with `is_covered_by_any`.
170 match (self, other) {
171 // Wildcards cover anything
172 (_, Wildcard) => true,
173 // The missing ctors are not covered by anything in the matrix except wildcards.
174 (Missing, _) | (Wildcard, _) => false,
175
176 (Single, Single) => true,
177 (Variant(self_id), Variant(other_id)) => self_id == other_id,
178
179 (Constructor::IntRange(_), Constructor::IntRange(_)) => todo!(),
180
181 (Constructor::Slice(_), Constructor::Slice(_)) => todo!(),
182
183 _ => panic!("bug"),
184 }
185 }
186
187 /// Faster version of `is_covered_by` when applied to many constructors. `used_ctors` is
188 /// assumed to be built from `matrix.head_ctors()` with wildcards filtered out, and `self` is
189 /// assumed to have been split from a wildcard.
190 fn is_covered_by_any(&self, pcx: &PatCtxt<'_>, used_ctors: &[Constructor]) -> bool {
191 if used_ctors.is_empty() {
192 return false;
193 }
194
195 // This must be kept in sync with `is_covered_by`.
196 match self {
197 // If `self` is `Single`, `used_ctors` cannot contain anything else than `Single`s.
198 Single => !used_ctors.is_empty(),
199 Variant(_) => used_ctors.iter().any(|c| c == self),
200 IntRange(range) => used_ctors
201 .iter()
202 .filter_map(|c| c.as_int_range())
203 .any(|other| range.is_covered_by(other)),
204 Slice(slice) => used_ctors
205 .iter()
206 .filter_map(|c| c.as_slice())
207 .any(|other| slice.is_covered_by(other)),
208
209 _ => todo!(),
210 }
211 }
212}
213
214/// A wildcard constructor that we split relative to the constructors in the matrix, as explained
215/// at the top of the file.
216///
217/// A constructor that is not present in the matrix rows will only be covered by the rows that have
218/// wildcards. Thus we can group all of those constructors together; we call them "missing
219/// constructors". Splitting a wildcard would therefore list all present constructors individually
220/// (or grouped if they are integers or slices), and then all missing constructors together as a
221/// group.
222///
223/// However we can go further: since any constructor will match the wildcard rows, and having more
224/// rows can only reduce the amount of usefulness witnesses, we can skip the present constructors
225/// and only try the missing ones.
226/// This will not preserve the whole list of witnesses, but will preserve whether the list is empty
227/// or not. In fact this is quite natural from the point of view of diagnostics too. This is done
228/// in `to_ctors`: in some cases we only return `Missing`.
229#[derive(Debug)]
230pub(super) struct SplitWildcard {
231 /// Constructors seen in the matrix.
232 matrix_ctors: Vec<Constructor>,
233 /// All the constructors for this type
234 all_ctors: SmallVec<[Constructor; 1]>,
235}
236
237impl SplitWildcard {
238 pub(super) fn new(pcx: &PatCtxt<'_>) -> Self {
239 // let cx = pcx.cx;
240 // let make_range = |start, end| IntRange(todo!());
241
242 // This determines the set of all possible constructors for the type `pcx.ty`. For numbers,
243 // arrays and slices we use ranges and variable-length slices when appropriate.
244 //
245 // If the `exhaustive_patterns` feature is enabled, we make sure to omit constructors that
246 // are statically impossible. E.g., for `Option<!>`, we do not include `Some(_)` in the
247 // returned list of constructors.
248 // Invariant: this is empty if and only if the type is uninhabited (as determined by
249 // `cx.is_uninhabited()`).
250 let all_ctors = match pcx.ty.kind(&Interner) {
251 TyKind::Adt(AdtId(hir_def::AdtId::EnumId(_)), _) => todo!(),
252 TyKind::Adt(..) | TyKind::Tuple(..) | TyKind::Ref(..) => smallvec![Single],
253 _ => todo!(),
254 };
255 SplitWildcard { matrix_ctors: Vec::new(), all_ctors }
256 }
257
258 /// Pass a set of constructors relative to which to split this one. Don't call twice, it won't
259 /// do what you want.
260 pub(super) fn split<'a>(
261 &mut self,
262 pcx: &PatCtxt<'_>,
263 ctors: impl Iterator<Item = &'a Constructor> + Clone,
264 ) {
265 // Since `all_ctors` never contains wildcards, this won't recurse further.
266 self.all_ctors =
267 self.all_ctors.iter().flat_map(|ctor| ctor.split(pcx, ctors.clone())).collect();
268 self.matrix_ctors = ctors.filter(|c| !c.is_wildcard()).cloned().collect();
269 }
270
271 /// Whether there are any value constructors for this type that are not present in the matrix.
272 fn any_missing(&self, pcx: &PatCtxt<'_>) -> bool {
273 self.iter_missing(pcx).next().is_some()
274 }
275
276 /// Iterate over the constructors for this type that are not present in the matrix.
277 pub(super) fn iter_missing<'a>(
278 &'a self,
279 pcx: &'a PatCtxt<'_>,
280 ) -> impl Iterator<Item = &'a Constructor> {
281 self.all_ctors.iter().filter(move |ctor| !ctor.is_covered_by_any(pcx, &self.matrix_ctors))
282 }
283
284 /// Return the set of constructors resulting from splitting the wildcard. As explained at the
285 /// top of the file, if any constructors are missing we can ignore the present ones.
286 fn into_ctors(self, pcx: &PatCtxt<'_>) -> SmallVec<[Constructor; 1]> {
287 if self.any_missing(pcx) {
288 // Some constructors are missing, thus we can specialize with the special `Missing`
289 // constructor, which stands for those constructors that are not seen in the matrix,
290 // and matches the same rows as any of them (namely the wildcard rows). See the top of
291 // the file for details.
292 // However, when all constructors are missing we can also specialize with the full
293 // `Wildcard` constructor. The difference will depend on what we want in diagnostics.
294
295 // If some constructors are missing, we typically want to report those constructors,
296 // e.g.:
297 // ```
298 // enum Direction { N, S, E, W }
299 // let Direction::N = ...;
300 // ```
301 // we can report 3 witnesses: `S`, `E`, and `W`.
302 //
303 // However, if the user didn't actually specify a constructor
304 // in this arm, e.g., in
305 // ```
306 // let x: (Direction, Direction, bool) = ...;
307 // let (_, _, false) = x;
308 // ```
309 // we don't want to show all 16 possible witnesses `(<direction-1>, <direction-2>,
310 // true)` - we are satisfied with `(_, _, true)`. So if all constructors are missing we
311 // prefer to report just a wildcard `_`.
312 //
313 // 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
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 {
318 Missing
319 } else {
320 Wildcard
321 };
322 return smallvec![ctor];
323 }
324
325 // All the constructors are present in the matrix, so we just go through them all.
326 self.all_ctors
327 }
328}
329
330#[test]
331fn it_works2() {}
332
333/// Some fields need to be explicitly hidden away in certain cases; see the comment above the
334/// `Fields` struct. This struct represents such a potentially-hidden field.
335#[derive(Debug, Copy, Clone)]
336pub(super) enum FilteredField {
337 Kept(PatId),
338 Hidden,
339}
340
341impl FilteredField {
342 fn kept(self) -> Option<PatId> {
343 match self {
344 FilteredField::Kept(p) => Some(p),
345 FilteredField::Hidden => None,
346 }
347 }
348}
349
350/// A value can be decomposed into a constructor applied to some fields. This struct represents
351/// those fields, generalized to allow patterns in each field. See also `Constructor`.
352/// This is constructed from a constructor using [`Fields::wildcards()`].
353///
354/// If a private or `non_exhaustive` field is uninhabited, the code mustn't observe that it is
355/// uninhabited. For that, we filter these fields out of the matrix. This is handled automatically
356/// in `Fields`. This filtering is uncommon in practice, because uninhabited fields are rarely used,
357/// so we avoid it when possible to preserve performance.
358#[derive(Debug, Clone)]
359pub(super) enum Fields {
360 /// Lists of patterns that don't contain any filtered fields.
361 /// `Slice` and `Vec` behave the same; the difference is only to avoid allocating and
362 /// triple-dereferences when possible. Frankly this is premature optimization, I (Nadrieril)
363 /// have not measured if it really made a difference.
364 Vec(SmallVec<[PatId; 2]>),
365}
366
367impl Fields {
368 /// Internal use. Use `Fields::wildcards()` instead.
369 /// Must not be used if the pattern is a field of a struct/tuple/variant.
370 fn from_single_pattern(pat: PatId) -> Self {
371 Fields::Vec(smallvec![pat])
372 }
373
374 /// Convenience; internal use.
375 fn wildcards_from_tys<'a>(
376 cx: &MatchCheckCtx<'_>,
377 tys: impl IntoIterator<Item = &'a Ty>,
378 ) -> Self {
379 let wilds = tys.into_iter().map(|ty| (Pat::Wild, ty));
380 let pats = wilds.map(|(pat, ty)| cx.alloc_pat(pat, ty)).collect();
381 Fields::Vec(pats)
382 }
383
384 pub(crate) fn wildcards(pcx: &PatCtxt<'_>, constructor: &Constructor) -> Self {
385 let ty = &pcx.ty;
386 let cx = pcx.cx;
387 let wildcard_from_ty = |ty| cx.alloc_pat(Pat::Wild, ty);
388
389 let ret = match constructor {
390 Single | Variant(_) => match ty.kind(&Interner) {
391 TyKind::Tuple(_, substs) => {
392 let tys = substs.iter(&Interner).map(|ty| ty.assert_ty_ref(&Interner));
393 Fields::wildcards_from_tys(cx, tys)
394 }
395 TyKind::Ref(.., rty) => Fields::from_single_pattern(wildcard_from_ty(rty)),
396 TyKind::Adt(AdtId(adt), substs) => {
397 let adt_is_box = false; // TODO(iDawer): handle box patterns
398 if adt_is_box {
399 // Use T as the sub pattern type of Box<T>.
400 let ty = substs.at(&Interner, 0).assert_ty_ref(&Interner);
401 Fields::from_single_pattern(wildcard_from_ty(ty))
402 } else {
403 let variant_id = constructor.variant_id_for_adt(*adt, cx);
404 let variant = variant_id.variant_data(cx.db.upcast());
405 let adt_is_local = variant_id.module(cx.db.upcast()).krate() == cx.krate;
406 // Whether we must not match the fields of this variant exhaustively.
407 let is_non_exhaustive =
408 is_field_list_non_exhaustive(variant_id, cx) && !adt_is_local;
409 let field_ty_arena = cx.db.field_types(variant_id);
410 let field_tys =
411 || field_ty_arena.iter().map(|(_, binders)| binders.skip_binders());
412 // In the following cases, we don't need to filter out any fields. This is
413 // the vast majority of real cases, since uninhabited fields are uncommon.
414 let has_no_hidden_fields = (matches!(adt, hir_def::AdtId::EnumId(_))
415 && !is_non_exhaustive)
416 || !field_tys().any(|ty| cx.is_uninhabited(ty));
417
418 if has_no_hidden_fields {
419 Fields::wildcards_from_tys(cx, field_tys())
420 } else {
421 //FIXME(iDawer): see MatchCheckCtx::is_uninhabited
422 unimplemented!("exhaustive_patterns feature")
423 }
424 }
425 }
426 _ => panic!("Unexpected type for `Single` constructor: {:?}", ty),
427 },
428 Missing | Wildcard => Fields::Vec(Default::default()),
429 _ => todo!(),
430 };
431 ret
432 }
433
434 /// Apply a constructor to a list of patterns, yielding a new pattern. `self`
435 /// must have as many elements as this constructor's arity.
436 ///
437 /// This is roughly the inverse of `specialize_constructor`.
438 ///
439 /// Examples:
440 /// `ctor`: `Constructor::Single`
441 /// `ty`: `Foo(u32, u32, u32)`
442 /// `self`: `[10, 20, _]`
443 /// returns `Foo(10, 20, _)`
444 ///
445 /// `ctor`: `Constructor::Variant(Option::Some)`
446 /// `ty`: `Option<bool>`
447 /// `self`: `[false]`
448 /// returns `Some(false)`
449 pub(super) fn apply(self, pcx: &PatCtxt<'_>, ctor: &Constructor) -> Pat {
450 let subpatterns_and_indices = self.patterns_and_indices();
451 let mut subpatterns = subpatterns_and_indices.iter().map(|&(_, p)| p);
452
453 match ctor {
454 Single | Variant(_) => match pcx.ty.kind(&Interner) {
455 TyKind::Adt(..) | TyKind::Tuple(..) => {
456 // We want the real indices here.
457 // TODO indices
458 let subpatterns = subpatterns_and_indices.iter().map(|&(_, pat)| pat).collect();
459
460 if let Some((adt, substs)) = pcx.ty.as_adt() {
461 if let hir_def::AdtId::EnumId(_) = adt {
462 todo!()
463 } else {
464 todo!()
465 }
466 } else {
467 // TODO ellipsis
468 Pat::Tuple { args: subpatterns, ellipsis: None }
469 }
470 }
471
472 _ => todo!(),
473 // TyKind::AssociatedType(_, _) => {}
474 // TyKind::Scalar(_) => {}
475 // TyKind::Array(_, _) => {}
476 // TyKind::Slice(_) => {}
477 // TyKind::Raw(_, _) => {}
478 // TyKind::Ref(_, _, _) => {}
479 // TyKind::OpaqueType(_, _) => {}
480 // TyKind::FnDef(_, _) => {}
481 // TyKind::Str => {}
482 // TyKind::Never => {}
483 // TyKind::Closure(_, _) => {}
484 // TyKind::Generator(_, _) => {}
485 // TyKind::GeneratorWitness(_, _) => {}
486 // TyKind::Foreign(_) => {}
487 // TyKind::Error => {}
488 // TyKind::Placeholder(_) => {}
489 // TyKind::Dyn(_) => {}
490 // TyKind::Alias(_) => {}
491 // TyKind::Function(_) => {}
492 // TyKind::BoundVar(_) => {}
493 // TyKind::InferenceVar(_, _) => {}
494 },
495
496 _ => todo!(),
497 // Constructor::IntRange(_) => {}
498 // Constructor::Slice(_) => {}
499 // Missing => {}
500 // Wildcard => {}
501 }
502 }
503
504 /// Returns the number of patterns. This is the same as the arity of the constructor used to
505 /// construct `self`.
506 pub(super) fn len(&self) -> usize {
507 match self {
508 Fields::Vec(pats) => pats.len(),
509 }
510 }
511
512 /// Returns the list of patterns along with the corresponding field indices.
513 fn patterns_and_indices(&self) -> SmallVec<[(usize, PatId); 2]> {
514 match self {
515 Fields::Vec(pats) => pats.iter().copied().enumerate().collect(),
516 }
517 }
518
519 pub(super) fn into_patterns(self) -> SmallVec<[PatId; 2]> {
520 match self {
521 Fields::Vec(pats) => pats,
522 }
523 }
524
525 /// Overrides some of the fields with the provided patterns. Exactly like
526 /// `replace_fields_indexed`, except that it takes `FieldPat`s as input.
527 fn replace_with_fieldpats(&self, new_pats: impl IntoIterator<Item = PatId>) -> Self {
528 self.replace_fields_indexed(new_pats.into_iter().enumerate())
529 }
530
531 /// Overrides some of the fields with the provided patterns. This is used when a pattern
532 /// defines some fields but not all, for example `Foo { field1: Some(_), .. }`: here we start
533 /// with a `Fields` that is just one wildcard per field of the `Foo` struct, and override the
534 /// entry corresponding to `field1` with the pattern `Some(_)`. This is also used for slice
535 /// patterns for the same reason.
536 fn replace_fields_indexed(&self, new_pats: impl IntoIterator<Item = (usize, PatId)>) -> Self {
537 let mut fields = self.clone();
538
539 match &mut fields {
540 Fields::Vec(pats) => {
541 for (i, pat) in new_pats {
542 if let Some(p) = pats.get_mut(i) {
543 *p = pat;
544 }
545 }
546 }
547 }
548 fields
549 }
550
551 /// Replaces contained fields with the given list of patterns. There must be `len()` patterns
552 /// in `pats`.
553 pub(super) fn replace_fields(
554 &self,
555 cx: &MatchCheckCtx<'_>,
556 pats: impl IntoIterator<Item = Pat>,
557 ) -> Self {
558 let pats = {
559 let mut arena = cx.pattern_arena.borrow_mut();
560 pats.into_iter().map(move |pat| /* arena.alloc(pat) */ todo!()).collect()
561 };
562
563 match self {
564 Fields::Vec(_) => Fields::Vec(pats),
565 }
566 }
567
568 /// Replaces contained fields with the arguments of the given pattern. Only use on a pattern
569 /// that is compatible with the constructor used to build `self`.
570 /// This is meant to be used on the result of `Fields::wildcards()`. The idea is that
571 /// `wildcards` constructs a list of fields where all entries are wildcards, and the pattern
572 /// provided to this function fills some of the fields with non-wildcards.
573 /// In the following example `Fields::wildcards` would return `[_, _, _, _]`. If we call
574 /// `replace_with_pattern_arguments` on it with the pattern, the result will be `[Some(0), _,
575 /// _, _]`.
576 /// ```rust
577 /// let x: [Option<u8>; 4] = foo();
578 /// match x {
579 /// [Some(0), ..] => {}
580 /// }
581 /// ```
582 /// This is guaranteed to preserve the number of patterns in `self`.
583 pub(super) fn replace_with_pattern_arguments(
584 &self,
585 pat: PatId,
586 cx: &MatchCheckCtx<'_>,
587 ) -> Self {
588 match &cx.pattern_arena.borrow()[pat] {
589 Pat::Ref { pat: subpattern, .. } => {
590 assert_eq!(self.len(), 1);
591 Fields::from_single_pattern(*subpattern)
592 }
593 Pat::Tuple { args: subpatterns, ellipsis } => {
594 // FIXME(iDawer) handle ellipsis.
595 // XXX(iDawer): in rustc, this is handled by HIR->TypedHIR lowering
596 // rustc_mir_build::thir::pattern::PatCtxt::lower_tuple_subpats(..)
597 self.replace_with_fieldpats(subpatterns.iter().copied())
598 }
599
600 Pat::Wild => self.clone(),
601 pat => todo!("Fields::replace_with_pattern_arguments({:?})", pat),
602 // Pat::Missing => {}
603 // Pat::Or(_) => {}
604 // Pat::Record { path, args, ellipsis } => {}
605 // Pat::Range { start, end } => {}
606 // Pat::Slice { prefix, slice, suffix } => {}
607 // Pat::Path(_) => {}
608 // Pat::Lit(_) => {}
609 // Pat::Bind { mode, name, subpat } => {}
610 // Pat::TupleStruct { path, args, ellipsis } => {}
611 // Pat::Box { inner } => {}
612 // Pat::ConstBlock(_) => {}
613 }
614 }
615}
616
617fn is_field_list_non_exhaustive(variant_id: VariantId, cx: &MatchCheckCtx<'_>) -> bool {
618 let attr_def_id = match variant_id {
619 VariantId::EnumVariantId(id) => id.into(),
620 VariantId::StructId(id) => id.into(),
621 VariantId::UnionId(id) => id.into(),
622 };
623 cx.db.attrs(attr_def_id).by_key("non_exhaustive").exists()
624}
625
626#[test]
627fn it_works() {}
diff --git a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
new file mode 100644
index 000000000..f5f6bf494
--- /dev/null
+++ b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
@@ -0,0 +1,736 @@
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
3
4use std::{cell::RefCell, iter::FromIterator, ops::Index, sync::Arc};
5
6use base_db::CrateId;
7use hir_def::{
8 body::Body,
9 expr::{ExprId, Pat, PatId},
10};
11use la_arena::Arena;
12use once_cell::unsync::OnceCell;
13use rustc_hash::FxHashMap;
14use smallvec::{smallvec, SmallVec};
15
16use crate::{db::HirDatabase, InferenceResult, Ty};
17
18use super::deconstruct_pat::{Constructor, Fields, SplitWildcard};
19
20use self::{
21 helper::{Captures, PatIdExt},
22 Usefulness::*,
23 WitnessPreference::*,
24};
25
26pub(crate) struct MatchCheckCtx<'a> {
27 pub(crate) krate: CrateId,
28 pub(crate) match_expr: ExprId,
29 pub(crate) body: Arc<Body>,
30 pub(crate) infer: &'a InferenceResult,
31 pub(crate) db: &'a dyn HirDatabase,
32 /// Patterns from self.body.pats plus generated by the check.
33 pub(crate) pattern_arena: &'a RefCell<PatternArena>,
34}
35
36impl<'a> MatchCheckCtx<'a> {
37 pub(super) fn is_uninhabited(&self, ty: &Ty) -> bool {
38 // FIXME(iDawer) implement exhaustive_patterns feature. More info in:
39 // Tracking issue for RFC 1872: exhaustive_patterns feature https://github.com/rust-lang/rust/issues/51085
40 false
41 }
42
43 pub(super) fn alloc_pat(&self, pat: Pat, ty: &Ty) -> PatId {
44 self.pattern_arena.borrow_mut().alloc(pat, ty)
45 }
46
47 /// Get type of a pattern. Handles expanded patterns.
48 pub(super) fn type_of(&self, pat: PatId) -> Ty {
49 let type_of_expanded_pat = self.pattern_arena.borrow().type_of_epat.get(&pat).cloned();
50 type_of_expanded_pat.unwrap_or_else(|| self.infer[pat].clone())
51 }
52}
53
54#[derive(Clone)]
55pub(super) struct PatCtxt<'a> {
56 pub(super) cx: &'a MatchCheckCtx<'a>,
57 /// Type of the current column under investigation.
58 pub(super) ty: Ty,
59 /// Whether the current pattern is the whole pattern as found in a match arm, or if it's a
60 /// subpattern.
61 pub(super) is_top_level: bool,
62}
63
64impl PatIdExt for PatId {
65 fn is_wildcard(self, cx: &MatchCheckCtx<'_>) -> bool {
66 matches!(cx.pattern_arena.borrow()[self], Pat::Bind { subpat: None, .. } | Pat::Wild)
67 }
68
69 fn is_or_pat(self, cx: &MatchCheckCtx<'_>) -> bool {
70 matches!(cx.pattern_arena.borrow()[self], Pat::Or(..))
71 }
72
73 /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns.
74 fn expand_or_pat(self, cx: &MatchCheckCtx<'_>) -> Vec<Self> {
75 fn expand(pat: PatId, vec: &mut Vec<PatId>, pat_arena: &PatternArena) {
76 if let Pat::Or(pats) = &pat_arena[pat] {
77 for &pat in pats {
78 expand(pat, vec, pat_arena);
79 }
80 } else {
81 vec.push(pat)
82 }
83 }
84
85 let pat_arena = cx.pattern_arena.borrow();
86 let mut pats = Vec::new();
87 expand(self, &mut pats, &pat_arena);
88 pats
89 }
90}
91
92/// A row of a matrix. Rows of len 1 are very common, which is why `SmallVec[_; 2]`
93/// works well.
94#[derive(Clone)]
95pub(super) struct PatStack {
96 pats: SmallVec<[PatId; 2]>,
97 /// Cache for the constructor of the head
98 head_ctor: OnceCell<Constructor>,
99}
100
101impl PatStack {
102 fn from_pattern(pat: PatId) -> Self {
103 Self::from_vec(smallvec![pat])
104 }
105
106 fn from_vec(vec: SmallVec<[PatId; 2]>) -> Self {
107 PatStack { pats: vec, head_ctor: OnceCell::new() }
108 }
109
110 fn is_empty(&self) -> bool {
111 self.pats.is_empty()
112 }
113
114 fn len(&self) -> usize {
115 self.pats.len()
116 }
117
118 fn head(&self) -> PatId {
119 self.pats[0]
120 }
121
122 #[inline]
123 fn head_ctor(&self, cx: &MatchCheckCtx<'_>) -> &Constructor {
124 self.head_ctor.get_or_init(|| Constructor::from_pat(cx, self.head()))
125 }
126
127 fn iter(&self) -> impl Iterator<Item = PatId> + '_ {
128 self.pats.iter().copied()
129 }
130
131 // Recursively expand the first pattern into its subpatterns. Only useful if the pattern is an
132 // or-pattern. Panics if `self` is empty.
133 fn expand_or_pat(&self, cx: &MatchCheckCtx<'_>) -> impl Iterator<Item = PatStack> + '_ {
134 self.head().expand_or_pat(cx).into_iter().map(move |pat| {
135 let mut new_patstack = PatStack::from_pattern(pat);
136 new_patstack.pats.extend_from_slice(&self.pats[1..]);
137 new_patstack
138 })
139 }
140
141 /// This computes `S(self.head_ctor(), self)`. See top of the file for explanations.
142 ///
143 /// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing
144 /// fields filled with wild patterns.
145 ///
146 /// This is roughly the inverse of `Constructor::apply`.
147 fn pop_head_constructor(
148 &self,
149 ctor_wild_subpatterns: &Fields,
150 cx: &MatchCheckCtx<'_>,
151 ) -> PatStack {
152 // We pop the head pattern and push the new fields extracted from the arguments of
153 // `self.head()`.
154 let mut new_fields =
155 ctor_wild_subpatterns.replace_with_pattern_arguments(self.head(), cx).into_patterns();
156 new_fields.extend_from_slice(&self.pats[1..]);
157 PatStack::from_vec(new_fields)
158 }
159}
160
161impl Default for PatStack {
162 fn default() -> Self {
163 Self::from_vec(smallvec![])
164 }
165}
166
167impl PartialEq for PatStack {
168 fn eq(&self, other: &Self) -> bool {
169 self.pats == other.pats
170 }
171}
172
173impl FromIterator<PatId> for PatStack {
174 fn from_iter<T>(iter: T) -> Self
175 where
176 T: IntoIterator<Item = PatId>,
177 {
178 Self::from_vec(iter.into_iter().collect())
179 }
180}
181
182#[derive(Clone)]
183pub(super) struct Matrix {
184 patterns: Vec<PatStack>,
185}
186
187impl Matrix {
188 fn empty() -> Self {
189 Matrix { patterns: vec![] }
190 }
191
192 /// Number of columns of this matrix. `None` is the matrix is empty.
193 pub(super) fn column_count(&self) -> Option<usize> {
194 self.patterns.get(0).map(|r| r.len())
195 }
196
197 /// Pushes a new row to the matrix. If the row starts with an or-pattern, this recursively
198 /// expands it.
199 fn push(&mut self, row: PatStack, cx: &MatchCheckCtx<'_>) {
200 if !row.is_empty() && row.head().is_or_pat(cx) {
201 for row in row.expand_or_pat(cx) {
202 self.patterns.push(row);
203 }
204 } else {
205 self.patterns.push(row);
206 }
207 }
208
209 /// Iterate over the first component of each row
210 fn heads(&self) -> impl Iterator<Item = PatId> + '_ {
211 self.patterns.iter().map(|r| r.head())
212 }
213
214 /// Iterate over the first constructor of each row.
215 fn head_ctors<'a>(
216 &'a self,
217 cx: &'a MatchCheckCtx<'_>,
218 ) -> impl Iterator<Item = &'a Constructor> + Clone {
219 self.patterns.iter().map(move |r| r.head_ctor(cx))
220 }
221
222 /// This computes `S(constructor, self)`. See top of the file for explanations.
223 fn specialize_constructor(
224 &self,
225 pcx: &PatCtxt<'_>,
226 ctor: &Constructor,
227 ctor_wild_subpatterns: &Fields,
228 ) -> Matrix {
229 let rows = self
230 .patterns
231 .iter()
232 .filter(|r| ctor.is_covered_by(pcx, r.head_ctor(pcx.cx)))
233 .map(|r| r.pop_head_constructor(ctor_wild_subpatterns, pcx.cx));
234 Matrix::from_iter(rows, pcx.cx)
235 }
236
237 fn from_iter(rows: impl IntoIterator<Item = PatStack>, cx: &MatchCheckCtx<'_>) -> Matrix {
238 let mut matrix = Matrix::empty();
239 for x in rows {
240 // Using `push` ensures we correctly expand or-patterns.
241 matrix.push(x, cx);
242 }
243 matrix
244 }
245}
246
247#[derive(Debug, Clone)]
248enum SubPatSet {
249 /// The empty set. This means the pattern is unreachable.
250 Empty,
251 /// The set containing the full pattern.
252 Full,
253 /// If the pattern is a pattern with a constructor or a pattern-stack, we store a set for each
254 /// of its subpatterns. Missing entries in the map are implicitly full, because that's the
255 /// common case.
256 Seq { subpats: FxHashMap<usize, SubPatSet> },
257 /// If the pattern is an or-pattern, we store a set for each of its alternatives. Missing
258 /// entries in the map are implicitly empty. Note: we always flatten nested or-patterns.
259 Alt {
260 subpats: FxHashMap<usize, SubPatSet>,
261 /// Counts the total number of alternatives in the pattern
262 alt_count: usize,
263 /// We keep the pattern around to retrieve spans.
264 pat: PatId,
265 },
266}
267
268impl SubPatSet {
269 fn full() -> Self {
270 SubPatSet::Full
271 }
272
273 fn empty() -> Self {
274 SubPatSet::Empty
275 }
276
277 fn is_empty(&self) -> bool {
278 match self {
279 SubPatSet::Empty => true,
280 SubPatSet::Full => false,
281 // If any subpattern in a sequence is unreachable, the whole pattern is unreachable.
282 SubPatSet::Seq { subpats } => subpats.values().any(|set| set.is_empty()),
283 // An or-pattern is reachable if any of its alternatives is.
284 SubPatSet::Alt { subpats, .. } => subpats.values().all(|set| set.is_empty()),
285 }
286 }
287
288 fn is_full(&self) -> bool {
289 match self {
290 SubPatSet::Empty => false,
291 SubPatSet::Full => true,
292 // The whole pattern is reachable only when all its alternatives are.
293 SubPatSet::Seq { subpats } => subpats.values().all(|sub_set| sub_set.is_full()),
294 // The whole or-pattern is reachable only when all its alternatives are.
295 SubPatSet::Alt { subpats, alt_count, .. } => {
296 subpats.len() == *alt_count && subpats.values().all(|set| set.is_full())
297 }
298 }
299 }
300
301 /// Union `self` with `other`, mutating `self`.
302 fn union(&mut self, other: Self) {
303 use SubPatSet::*;
304 // Union with full stays full; union with empty changes nothing.
305 if self.is_full() || other.is_empty() {
306 return;
307 } else if self.is_empty() {
308 *self = other;
309 return;
310 } else if other.is_full() {
311 *self = Full;
312 return;
313 }
314
315 match (&mut *self, other) {
316 (Seq { .. }, Seq { .. }) => {
317 todo!()
318 }
319 (Alt { .. }, Alt { .. }) => {
320 todo!()
321 }
322 _ => panic!("bug"),
323 }
324 }
325
326 /// Returns a list of the spans of the unreachable subpatterns. If `self` is empty (i.e. the
327 /// whole pattern is unreachable) we return `None`.
328 fn list_unreachable_spans(&self) -> Option<Vec<()>> {
329 if self.is_empty() {
330 return None;
331 }
332 if self.is_full() {
333 // No subpatterns are unreachable.
334 return Some(Vec::new());
335 }
336 todo!()
337 }
338
339 /// When `self` refers to a patstack that was obtained from specialization, after running
340 /// `unspecialize` it will refer to the original patstack before specialization.
341 fn unspecialize(self, arity: usize) -> Self {
342 use SubPatSet::*;
343 match self {
344 Full => Full,
345 Empty => Empty,
346 Seq { subpats } => {
347 todo!()
348 }
349 Alt { .. } => panic!("bug"),
350 }
351 }
352
353 /// When `self` refers to a patstack that was obtained from splitting an or-pattern, after
354 /// running `unspecialize` it will refer to the original patstack before splitting.
355 ///
356 /// For example:
357 /// ```
358 /// match Some(true) {
359 /// Some(true) => {}
360 /// None | Some(true | false) => {}
361 /// }
362 /// ```
363 /// Here `None` would return the full set and `Some(true | false)` would return the set
364 /// containing `false`. After `unsplit_or_pat`, we want the set to contain `None` and `false`.
365 /// This is what this function does.
366 fn unsplit_or_pat(mut self, alt_id: usize, alt_count: usize, pat: PatId) -> Self {
367 todo!()
368 }
369}
370
371/// This carries the results of computing usefulness, as described at the top of the file. When
372/// checking usefulness of a match branch, we use the `NoWitnesses` variant, which also keeps track
373/// of potential unreachable sub-patterns (in the presence of or-patterns). When checking
374/// exhaustiveness of a whole match, we use the `WithWitnesses` variant, which carries a list of
375/// witnesses of non-exhaustiveness when there are any.
376/// Which variant to use is dictated by `WitnessPreference`.
377#[derive(Clone, Debug)]
378enum Usefulness {
379 /// Carries a set of subpatterns that have been found to be reachable. If empty, this indicates
380 /// the whole pattern is unreachable. If not, this indicates that the pattern is reachable but
381 /// that some sub-patterns may be unreachable (due to or-patterns). In the absence of
382 /// or-patterns this will always be either `Empty` (the whole pattern is unreachable) or `Full`
383 /// (the whole pattern is reachable).
384 NoWitnesses(SubPatSet),
385 /// Carries a list of witnesses of non-exhaustiveness. If empty, indicates that the whole
386 /// pattern is unreachable.
387 WithWitnesses(Vec<Witness>),
388}
389
390impl Usefulness {
391 fn new_useful(preference: WitnessPreference) -> Self {
392 match preference {
393 ConstructWitness => WithWitnesses(vec![Witness(vec![])]),
394 LeaveOutWitness => NoWitnesses(SubPatSet::full()),
395 }
396 }
397 fn new_not_useful(preference: WitnessPreference) -> Self {
398 match preference {
399 ConstructWitness => WithWitnesses(vec![]),
400 LeaveOutWitness => NoWitnesses(SubPatSet::empty()),
401 }
402 }
403
404 /// Combine usefulnesses from two branches. This is an associative operation.
405 fn extend(&mut self, other: Self) {
406 match (&mut *self, other) {
407 (WithWitnesses(_), WithWitnesses(o)) if o.is_empty() => {}
408 (WithWitnesses(s), WithWitnesses(o)) if s.is_empty() => *self = WithWitnesses(o),
409 (WithWitnesses(s), WithWitnesses(o)) => s.extend(o),
410 (NoWitnesses(s), NoWitnesses(o)) => s.union(o),
411 _ => unreachable!(),
412 }
413 }
414
415 /// When trying several branches and each returns a `Usefulness`, we need to combine the
416 /// results together.
417 fn merge(pref: WitnessPreference, usefulnesses: impl Iterator<Item = Self>) -> Self {
418 let mut ret = Self::new_not_useful(pref);
419 for u in usefulnesses {
420 ret.extend(u);
421 if let NoWitnesses(subpats) = &ret {
422 if subpats.is_full() {
423 // Once we reach the full set, more unions won't change the result.
424 return ret;
425 }
426 }
427 }
428 ret
429 }
430
431 /// After calculating the usefulness for a branch of an or-pattern, call this to make this
432 /// usefulness mergeable with those from the other branches.
433 fn unsplit_or_pat(self, alt_id: usize, alt_count: usize, pat: PatId) -> Self {
434 match self {
435 NoWitnesses(subpats) => NoWitnesses(subpats.unsplit_or_pat(alt_id, alt_count, pat)),
436 WithWitnesses(_) => panic!("bug"),
437 }
438 }
439
440 /// After calculating usefulness after a specialization, call this to recontruct a usefulness
441 /// that makes sense for the matrix pre-specialization. This new usefulness can then be merged
442 /// with the results of specializing with the other constructors.
443 fn apply_constructor(
444 self,
445 pcx: &PatCtxt<'_>,
446 matrix: &Matrix,
447 ctor: &Constructor,
448 ctor_wild_subpatterns: &Fields,
449 ) -> Self {
450 match self {
451 WithWitnesses(witnesses) if witnesses.is_empty() => WithWitnesses(witnesses),
452 WithWitnesses(w) => {
453 let new_witnesses = if matches!(ctor, Constructor::Missing) {
454 let mut split_wildcard = SplitWildcard::new(pcx);
455 split_wildcard.split(pcx, matrix.head_ctors(pcx.cx));
456 } else {
457 todo!("Usefulness::apply_constructor({:?})", ctor)
458 };
459 todo!("Usefulness::apply_constructor({:?})", ctor)
460 }
461 NoWitnesses(subpats) => NoWitnesses(subpats.unspecialize(ctor_wild_subpatterns.len())),
462 }
463 }
464}
465
466#[derive(Copy, Clone, Debug)]
467enum WitnessPreference {
468 ConstructWitness,
469 LeaveOutWitness,
470}
471
472#[derive(Clone, Debug)]
473pub(crate) struct Witness(Vec<Pat>);
474
475impl Witness {
476 /// Asserts that the witness contains a single pattern, and returns it.
477 fn single_pattern(self) -> Pat {
478 assert_eq!(self.0.len(), 1);
479 self.0.into_iter().next().unwrap()
480 }
481
482 /// Constructs a partial witness for a pattern given a list of
483 /// patterns expanded by the specialization step.
484 ///
485 /// When a pattern P is discovered to be useful, this function is used bottom-up
486 /// to reconstruct a complete witness, e.g., a pattern P' that covers a subset
487 /// of values, V, where each value in that set is not covered by any previously
488 /// used patterns and is covered by the pattern P'. Examples:
489 ///
490 /// left_ty: tuple of 3 elements
491 /// pats: [10, 20, _] => (10, 20, _)
492 ///
493 /// left_ty: struct X { a: (bool, &'static str), b: usize}
494 /// pats: [(false, "foo"), 42] => X { a: (false, "foo"), b: 42 }
495 fn apply_constructor(
496 mut self,
497 pcx: &PatCtxt<'_>,
498 ctor: &Constructor,
499 ctor_wild_subpatterns: &Fields,
500 ) -> Self {
501 let pat = {
502 let len = self.0.len();
503 let arity = ctor_wild_subpatterns.len();
504 let pats = self.0.drain((len - arity)..).rev();
505 ctor_wild_subpatterns.replace_fields(pcx.cx, pats).apply(pcx, ctor)
506 };
507
508 self.0.push(pat);
509
510 self
511 }
512}
513
514/// Algorithm from <http://moscova.inria.fr/~maranget/papers/warn/index.html>.
515/// The algorithm from the paper has been modified to correctly handle empty
516/// types. The changes are:
517/// (0) We don't exit early if the pattern matrix has zero rows. We just
518/// continue to recurse over columns.
519/// (1) all_constructors will only return constructors that are statically
520/// possible. E.g., it will only return `Ok` for `Result<T, !>`.
521///
522/// This finds whether a (row) vector `v` of patterns is 'useful' in relation
523/// to a set of such vectors `m` - this is defined as there being a set of
524/// inputs that will match `v` but not any of the sets in `m`.
525///
526/// All the patterns at each column of the `matrix ++ v` matrix must have the same type.
527///
528/// This is used both for reachability checking (if a pattern isn't useful in
529/// relation to preceding patterns, it is not reachable) and exhaustiveness
530/// checking (if a wildcard pattern is useful in relation to a matrix, the
531/// matrix isn't exhaustive).
532///
533/// `is_under_guard` is used to inform if the pattern has a guard. If it
534/// has one it must not be inserted into the matrix. This shouldn't be
535/// relied on for soundness.
536fn is_useful(
537 cx: &MatchCheckCtx<'_>,
538 matrix: &Matrix,
539 v: &PatStack,
540 witness_preference: WitnessPreference,
541 is_under_guard: bool,
542 is_top_level: bool,
543) -> Usefulness {
544 let Matrix { patterns: rows, .. } = matrix;
545
546 // The base case. We are pattern-matching on () and the return value is
547 // based on whether our matrix has a row or not.
548 // NOTE: This could potentially be optimized by checking rows.is_empty()
549 // first and then, if v is non-empty, the return value is based on whether
550 // the type of the tuple we're checking is inhabited or not.
551 if v.is_empty() {
552 let ret = if rows.is_empty() {
553 Usefulness::new_useful(witness_preference)
554 } else {
555 Usefulness::new_not_useful(witness_preference)
556 };
557 return ret;
558 }
559
560 assert!(rows.iter().all(|r| r.len() == v.len()));
561
562 // FIXME(Nadrieril): Hack to work around type normalization issues (see rust-lang/rust#72476).
563 // TODO(iDawer): ty.as_reference()
564 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 };
566
567 // If the first pattern is an or-pattern, expand it.
568 let ret = if v.head().is_or_pat(cx) {
569 //expanding or-pattern
570 let v_head = v.head();
571 let vs: Vec<_> = v.expand_or_pat(cx).collect();
572 let alt_count = vs.len();
573 // We try each or-pattern branch in turn.
574 let mut matrix = matrix.clone();
575 let usefulnesses = vs.into_iter().enumerate().map(|(i, v)| {
576 let usefulness = is_useful(cx, &matrix, &v, witness_preference, is_under_guard, false);
577 // If pattern has a guard don't add it to the matrix.
578 if !is_under_guard {
579 // We push the already-seen patterns into the matrix in order to detect redundant
580 // branches like `Some(_) | Some(0)`.
581 matrix.push(v, cx);
582 }
583 usefulness.unsplit_or_pat(i, alt_count, v_head)
584 });
585 Usefulness::merge(witness_preference, usefulnesses)
586 } else {
587 let v_ctor = v.head_ctor(cx);
588 // if let Constructor::IntRange(ctor_range) = v_ctor {
589 // // Lint on likely incorrect range patterns (#63987)
590 // ctor_range.lint_overlapping_range_endpoints(
591 // pcx,
592 // matrix.head_ctors_and_spans(cx),
593 // matrix.column_count().unwrap_or(0),
594 // hir_id,
595 // )
596 // }
597
598 // We split the head constructor of `v`.
599 let split_ctors = v_ctor.split(&pcx, matrix.head_ctors(cx));
600 // For each constructor, we compute whether there's a value that starts with it that would
601 // witness the usefulness of `v`.
602 let start_matrix = matrix;
603 let usefulnesses = split_ctors.into_iter().map(|ctor| {
604 // debug!("specialize({:?})", ctor);
605 // We cache the result of `Fields::wildcards` because it is used a lot.
606 let ctor_wild_subpatterns = Fields::wildcards(&pcx, &ctor);
607 let spec_matrix =
608 start_matrix.specialize_constructor(&pcx, &ctor, &ctor_wild_subpatterns);
609 let v = v.pop_head_constructor(&ctor_wild_subpatterns, cx);
610 let usefulness =
611 is_useful(cx, &spec_matrix, &v, witness_preference, is_under_guard, false);
612 usefulness.apply_constructor(&pcx, start_matrix, &ctor, &ctor_wild_subpatterns)
613 });
614 Usefulness::merge(witness_preference, usefulnesses)
615 };
616
617 ret
618}
619
620/// The arm of a match expression.
621#[derive(Clone, Copy)]
622pub(crate) struct MatchArm {
623 pub(crate) pat: PatId,
624 pub(crate) has_guard: bool,
625}
626
627/// Indicates whether or not a given arm is reachable.
628#[derive(Clone, Debug)]
629pub(crate) enum Reachability {
630 /// The arm is reachable. This additionally carries a set of or-pattern branches that have been
631 /// found to be unreachable despite the overall arm being reachable. Used only in the presence
632 /// of or-patterns, otherwise it stays empty.
633 Reachable(Vec<()>),
634 /// The arm is unreachable.
635 Unreachable,
636}
637/// The output of checking a match for exhaustiveness and arm reachability.
638pub(crate) struct UsefulnessReport {
639 /// For each arm of the input, whether that arm is reachable after the arms above it.
640 pub(crate) arm_usefulness: Vec<(MatchArm, Reachability)>,
641 /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of
642 /// exhaustiveness.
643 pub(crate) non_exhaustiveness_witnesses: Vec<Pat>,
644}
645
646pub(crate) fn compute_match_usefulness(
647 cx: &MatchCheckCtx<'_>,
648 arms: &[MatchArm],
649) -> UsefulnessReport {
650 let mut matrix = Matrix::empty();
651 let arm_usefulness: Vec<_> = arms
652 .iter()
653 .copied()
654 .map(|arm| {
655 let v = PatStack::from_pattern(arm.pat);
656 let usefulness = is_useful(cx, &matrix, &v, LeaveOutWitness, arm.has_guard, true);
657 if !arm.has_guard {
658 matrix.push(v, cx);
659 }
660 let reachability = match usefulness {
661 NoWitnesses(subpats) if subpats.is_empty() => Reachability::Unreachable,
662 NoWitnesses(subpats) => {
663 Reachability::Reachable(subpats.list_unreachable_spans().unwrap())
664 }
665 WithWitnesses(..) => panic!("bug"),
666 };
667 (arm, reachability)
668 })
669 .collect();
670
671 let wild_pattern = cx.pattern_arena.borrow_mut().alloc(Pat::Wild, &cx.infer[cx.match_expr]);
672 let v = PatStack::from_pattern(wild_pattern);
673 let usefulness = is_useful(cx, &matrix, &v, LeaveOutWitness, false, true);
674 let non_exhaustiveness_witnesses = match usefulness {
675 // TODO: ConstructWitness
676 // WithWitnesses(pats) => pats.into_iter().map(Witness::single_pattern).collect(),
677 // NoWitnesses(_) => panic!("bug"),
678 NoWitnesses(subpats) if subpats.is_empty() => Vec::new(),
679 NoWitnesses(subpats) => vec![Pat::Wild],
680 WithWitnesses(..) => panic!("bug"),
681 };
682 UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }
683}
684
685pub(crate) struct PatternArena {
686 arena: Arena<Pat>,
687 /// Types of expanded patterns.
688 type_of_epat: FxHashMap<PatId, Ty>,
689}
690
691impl PatternArena {
692 pub(crate) fn clone_from(pats: &Arena<Pat>) -> RefCell<Self> {
693 PatternArena { arena: pats.clone(), type_of_epat: Default::default() }.into()
694 }
695
696 fn alloc(&mut self, pat: Pat, ty: &Ty) -> PatId {
697 let id = self.arena.alloc(pat);
698 self.type_of_epat.insert(id, ty.clone());
699 id
700 }
701}
702
703impl Index<PatId> for PatternArena {
704 type Output = Pat;
705
706 fn index(&self, pat: PatId) -> &Pat {
707 &self.arena[pat]
708 }
709}
710
711mod helper {
712 use hir_def::expr::{Pat, PatId};
713
714 use super::MatchCheckCtx;
715
716 pub(super) trait PatIdExt: Sized {
717 fn is_wildcard(self, cx: &MatchCheckCtx<'_>) -> bool;
718 fn is_or_pat(self, cx: &MatchCheckCtx<'_>) -> bool;
719 fn expand_or_pat(self, cx: &MatchCheckCtx<'_>) -> Vec<Self>;
720 }
721
722 // Copy-pasted from rust/compiler/rustc_data_structures/src/captures.rs
723 /// "Signaling" trait used in impl trait to tag lifetimes that you may
724 /// need to capture but don't really need for other reasons.
725 /// Basically a workaround; see [this comment] for details.
726 ///
727 /// [this comment]: https://github.com/rust-lang/rust/issues/34511#issuecomment-373423999
728 // FIXME(eddyb) false positive, the lifetime parameter is "phantom" but needed.
729 #[allow(unused_lifetimes)]
730 pub trait Captures<'a> {}
731
732 impl<'a, T: ?Sized> Captures<'a> for T {}
733}
734
735#[test]
736fn it_works() {}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 04:10:31 +0000