aboutsummaryrefslogtreecommitdiff
path: root/crates/hir_ty/src
diff options
context:
space:
mode:
Diffstat (limited to 'crates/hir_ty/src')
-rw-r--r--crates/hir_ty/src/diagnostics/expr.rs1
-rw-r--r--crates/hir_ty/src/diagnostics/pattern.rs25
-rw-r--r--crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs145
-rw-r--r--crates/hir_ty/src/diagnostics/pattern/usefulness.rs313
4 files changed, 383 insertions, 101 deletions
diff --git a/crates/hir_ty/src/diagnostics/expr.rs b/crates/hir_ty/src/diagnostics/expr.rs
index e4e9ab5c0..b321004ac 100644
--- a/crates/hir_ty/src/diagnostics/expr.rs
+++ b/crates/hir_ty/src/diagnostics/expr.rs
@@ -437,7 +437,6 @@ impl<'a, 'b> ExprValidator<'a, 'b> {
437 let cx = usefulness::MatchCheckCtx { 437 let cx = usefulness::MatchCheckCtx {
438 module: self.owner.module(db.upcast()), 438 module: self.owner.module(db.upcast()),
439 match_expr, 439 match_expr,
440 body,
441 infer: &infer, 440 infer: &infer,
442 db, 441 db,
443 pattern_arena: &pattern_arena, 442 pattern_arena: &pattern_arena,
diff --git a/crates/hir_ty/src/diagnostics/pattern.rs b/crates/hir_ty/src/diagnostics/pattern.rs
index 38e4b53b7..85c01b178 100644
--- a/crates/hir_ty/src/diagnostics/pattern.rs
+++ b/crates/hir_ty/src/diagnostics/pattern.rs
@@ -1,15 +1,18 @@
1#![deny(elided_lifetimes_in_paths)] 1//! Validation of matches.
2#![allow(unused)] // todo remove 2//!
3//! This module provides lowering from [hir_def::expr::Pat] to [self::Pat] and match
4//! checking algorithm.
5//!
6//! It is a loose port of `rustc_mir_build::thir::pattern` module.
3 7
4mod deconstruct_pat; 8mod deconstruct_pat;
5// TODO: find a better place for this?
6mod pat_util; 9mod pat_util;
7pub(crate) mod usefulness; 10pub(crate) mod usefulness;
8 11
9use hir_def::{body::Body, EnumVariantId, LocalFieldId, VariantId}; 12use hir_def::{body::Body, EnumVariantId, LocalFieldId, VariantId};
10use la_arena::Idx; 13use la_arena::Idx;
11 14
12use crate::{db::HirDatabase, AdtId, InferenceResult, Interner, Substitution, Ty, TyKind}; 15use crate::{db::HirDatabase, InferenceResult, Interner, Substitution, Ty, TyKind};
13 16
14use self::pat_util::EnumerateAndAdjustIterator; 17use self::pat_util::EnumerateAndAdjustIterator;
15 18
@@ -38,6 +41,7 @@ impl Pat {
38 } 41 }
39} 42}
40 43
44/// Close relative to `rustc_mir_build::thir::pattern::PatKind`
41#[derive(Clone, Debug, PartialEq)] 45#[derive(Clone, Debug, PartialEq)]
42pub(crate) enum PatKind { 46pub(crate) enum PatKind {
43 Wild, 47 Wild,
@@ -66,7 +70,7 @@ pub(crate) enum PatKind {
66 subpattern: Pat, 70 subpattern: Pat,
67 }, 71 },
68 72
69 // only bool for now 73 // FIXME: for now, only bool literals are implemented
70 LiteralBool { 74 LiteralBool {
71 value: bool, 75 value: bool,
72 }, 76 },
@@ -91,7 +95,7 @@ impl<'a> PatCtxt<'a> {
91 } 95 }
92 96
93 pub(crate) fn lower_pattern(&mut self, pat: hir_def::expr::PatId) -> Pat { 97 pub(crate) fn lower_pattern(&mut self, pat: hir_def::expr::PatId) -> Pat {
94 // TODO: pattern adjustments (implicit dereference) 98 // FIXME: implement pattern adjustments (implicit pattern dereference; "RFC 2005-match-ergonomics")
95 // More info https://github.com/rust-lang/rust/issues/42640#issuecomment-313535089 99 // More info https://github.com/rust-lang/rust/issues/42640#issuecomment-313535089
96 let unadjusted_pat = self.lower_pattern_unadjusted(pat); 100 let unadjusted_pat = self.lower_pattern_unadjusted(pat);
97 unadjusted_pat 101 unadjusted_pat
@@ -141,7 +145,7 @@ impl<'a> PatCtxt<'a> {
141 .iter() 145 .iter()
142 .map(|field| FieldPat { 146 .map(|field| FieldPat {
143 // XXX(iDawer): field lookup is inefficient 147 // XXX(iDawer): field lookup is inefficient
144 field: variant_data.field(&field.name).unwrap_or_else(|| todo!()), 148 field: variant_data.field(&field.name).unwrap(),
145 pattern: self.lower_pattern(field.pat), 149 pattern: self.lower_pattern(field.pat),
146 }) 150 })
147 .collect(); 151 .collect();
@@ -208,11 +212,10 @@ impl<'a> PatCtxt<'a> {
208 PatKind::Wild 212 PatKind::Wild
209 } 213 }
210 }; 214 };
211 // TODO: do we need PatKind::AscribeUserType ?
212 kind 215 kind
213 } 216 }
214 217
215 fn lower_path(&mut self, pat: hir_def::expr::PatId, path: &hir_def::path::Path) -> Pat { 218 fn lower_path(&mut self, pat: hir_def::expr::PatId, _path: &hir_def::path::Path) -> Pat {
216 let ty = &self.infer[pat]; 219 let ty = &self.infer[pat];
217 220
218 let pat_from_kind = |kind| Pat { ty: ty.clone(), kind: Box::new(kind) }; 221 let pat_from_kind = |kind| Pat { ty: ty.clone(), kind: Box::new(kind) };
@@ -338,8 +341,6 @@ impl PatternFoldable for PatKind {
338mod tests { 341mod tests {
339 use crate::diagnostics::tests::check_diagnostics; 342 use crate::diagnostics::tests::check_diagnostics;
340 343
341 use super::*;
342
343 #[test] 344 #[test]
344 fn unit() { 345 fn unit() {
345 check_diagnostics( 346 check_diagnostics(
@@ -372,8 +373,6 @@ fn main() {
372 373
373 #[test] 374 #[test]
374 fn tuple_with_ellipsis() { 375 fn tuple_with_ellipsis() {
375 // TODO: test non-exhaustive match with ellipsis in the middle
376 // of a pattern, check reported witness
377 check_diagnostics( 376 check_diagnostics(
378 r#" 377 r#"
379struct A; struct B; 378struct A; struct B;
diff --git a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
index 1c86ed59b..9fa82a952 100644
--- a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
+++ b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs
@@ -1,14 +1,54 @@
1//! [`super::usefulness`] explains most of what is happening in this file. As explained there,
2//! values and patterns are made from constructors applied to fields. This file defines a
3//! `Constructor` enum, a `Fields` struct, and various operations to manipulate them and convert
4//! them from/to patterns.
5//!
6//! There's one idea that is not detailed in [`super::usefulness`] because the details are not
7//! needed there: _constructor splitting_.
8//!
9//! # Constructor splitting
10//!
11//! The idea is as follows: given a constructor `c` and a matrix, we want to specialize in turn
12//! with all the value constructors that are covered by `c`, and compute usefulness for each.
13//! Instead of listing all those constructors (which is intractable), we group those value
14//! constructors together as much as possible. Example:
15//!
16//! ```
17//! match (0, false) {
18//! (0 ..=100, true) => {} // `p_1`
19//! (50..=150, false) => {} // `p_2`
20//! (0 ..=200, _) => {} // `q`
21//! }
22//! ```
23//!
24//! The naive approach would try all numbers in the range `0..=200`. But we can be a lot more
25//! clever: `0` and `1` for example will match the exact same rows, and return equivalent
26//! witnesses. In fact all of `0..50` would. We can thus restrict our exploration to 4
27//! constructors: `0..50`, `50..=100`, `101..=150` and `151..=200`. That is enough and infinitely
28//! more tractable.
29//!
30//! We capture this idea in a function `split(p_1 ... p_n, c)` which returns a list of constructors
31//! `c'` covered by `c`. Given such a `c'`, we require that all value ctors `c''` covered by `c'`
32//! return an equivalent set of witnesses after specializing and computing usefulness.
33//! In the example above, witnesses for specializing by `c''` covered by `0..50` will only differ
34//! in their first element.
35//!
36//! We usually also ask that the `c'` together cover all of the original `c`. However we allow
37//! skipping some constructors as long as it doesn't change whether the resulting list of witnesses
38//! is empty of not. We use this in the wildcard `_` case.
39//!
40//! Splitting is implemented in the [`Constructor::split`] function. We don't do splitting for
41//! or-patterns; instead we just try the alternatives one-by-one. For details on splitting
42//! wildcards, see [`SplitWildcard`]; for integer ranges, see [`SplitIntRange`]; for slices, see
43//! [`SplitVarLenSlice`].
44
1use std::{ 45use std::{
2 cmp::{max, min}, 46 cmp::{max, min},
3 iter::once, 47 iter::once,
4 ops::RangeInclusive, 48 ops::RangeInclusive,
5}; 49};
6 50
7use hir_def::{ 51use hir_def::{EnumVariantId, HasModule, LocalFieldId, VariantId};
8 expr::{Expr, Literal, RecordFieldPat},
9 type_ref::Mutability,
10 AttrDefId, EnumVariantId, HasModule, LocalFieldId, VariantId,
11};
12use smallvec::{smallvec, SmallVec}; 52use smallvec::{smallvec, SmallVec};
13 53
14use crate::{AdtId, Interner, Scalar, Ty, TyExt, TyKind}; 54use crate::{AdtId, Interner, Scalar, Ty, TyExt, TyKind};
@@ -20,9 +60,21 @@ use super::{
20 60
21use self::Constructor::*; 61use self::Constructor::*;
22 62
63/// [Constructor] uses this in umimplemented variants.
64/// It allows porting match expressions from upstream algorithm without losing semantics.
23#[derive(Copy, Clone, Debug, PartialEq, Eq)] 65#[derive(Copy, Clone, Debug, PartialEq, Eq)]
24pub(super) enum ToDo {} 66pub(super) enum Void {}
25 67
68/// An inclusive interval, used for precise integer exhaustiveness checking.
69/// `IntRange`s always store a contiguous range. This means that values are
70/// encoded such that `0` encodes the minimum value for the integer,
71/// regardless of the signedness.
72/// For example, the pattern `-128..=127i8` is encoded as `0..=255`.
73/// This makes comparisons and arithmetic on interval endpoints much more
74/// straightforward. See `signed_bias` for details.
75///
76/// `IntRange` is never used to encode an empty range or a "range" that wraps
77/// around the (offset) space: i.e., `range.lo <= range.hi`.
26#[derive(Clone, Debug, PartialEq, Eq)] 78#[derive(Clone, Debug, PartialEq, Eq)]
27pub(super) struct IntRange { 79pub(super) struct IntRange {
28 range: RangeInclusive<u128>, 80 range: RangeInclusive<u128>,
@@ -55,11 +107,11 @@ impl IntRange {
55 } 107 }
56 108
57 #[inline] 109 #[inline]
58 fn from_range(cx: &MatchCheckCtx<'_>, lo: u128, hi: u128, scalar_ty: Scalar) -> IntRange { 110 fn from_range(lo: u128, hi: u128, scalar_ty: Scalar) -> IntRange {
59 if let Scalar::Bool = scalar_ty { 111 if let Scalar::Bool = scalar_ty {
60 IntRange { range: lo..=hi } 112 IntRange { range: lo..=hi }
61 } else { 113 } else {
62 todo!() 114 unimplemented!()
63 } 115 }
64 } 116 }
65 117
@@ -188,13 +240,13 @@ impl SplitIntRange {
188/// A constructor for array and slice patterns. 240/// A constructor for array and slice patterns.
189#[derive(Copy, Clone, Debug, PartialEq, Eq)] 241#[derive(Copy, Clone, Debug, PartialEq, Eq)]
190pub(super) struct Slice { 242pub(super) struct Slice {
191 todo: ToDo, 243 _unimplemented: Void,
192} 244}
193 245
194impl Slice { 246impl Slice {
195 /// See `Constructor::is_covered_by` 247 /// See `Constructor::is_covered_by`
196 fn is_covered_by(self, other: Self) -> bool { 248 fn is_covered_by(self, _other: Self) -> bool {
197 todo!() 249 unimplemented!() // never called as Slice contains Void
198 } 250 }
199} 251}
200 252
@@ -205,6 +257,7 @@ impl Slice {
205/// `specialize_constructor` returns the list of fields corresponding to a pattern, given a 257/// `specialize_constructor` returns the list of fields corresponding to a pattern, given a
206/// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and 258/// constructor. `Constructor::apply` reconstructs the pattern from a pair of `Constructor` and
207/// `Fields`. 259/// `Fields`.
260#[allow(dead_code)]
208#[derive(Clone, Debug, PartialEq)] 261#[derive(Clone, Debug, PartialEq)]
209pub(super) enum Constructor { 262pub(super) enum Constructor {
210 /// The constructor for patterns that have a single constructor, like tuples, struct patterns 263 /// The constructor for patterns that have a single constructor, like tuples, struct patterns
@@ -215,9 +268,9 @@ pub(super) enum Constructor {
215 /// Ranges of integer literal values (`2`, `2..=5` or `2..5`). 268 /// Ranges of integer literal values (`2`, `2..=5` or `2..5`).
216 IntRange(IntRange), 269 IntRange(IntRange),
217 /// Ranges of floating-point literal values (`2.0..=5.2`). 270 /// Ranges of floating-point literal values (`2.0..=5.2`).
218 FloatRange(ToDo), 271 FloatRange(Void),
219 /// String literals. Strings are not quite the same as `&[u8]` so we treat them separately. 272 /// String literals. Strings are not quite the same as `&[u8]` so we treat them separately.
220 Str(ToDo), 273 Str(Void),
221 /// Array and slice patterns. 274 /// Array and slice patterns.
222 Slice(Slice), 275 Slice(Slice),
223 /// Constants that must not be matched structurally. They are treated as black 276 /// Constants that must not be matched structurally. They are treated as black
@@ -253,7 +306,7 @@ impl Constructor {
253 } 306 }
254 } 307 }
255 308
256 fn variant_id_for_adt(&self, adt: hir_def::AdtId, cx: &MatchCheckCtx<'_>) -> VariantId { 309 fn variant_id_for_adt(&self, adt: hir_def::AdtId) -> VariantId {
257 match *self { 310 match *self {
258 Variant(id) => id.into(), 311 Variant(id) => id.into(),
259 Single => { 312 Single => {
@@ -270,7 +323,6 @@ impl Constructor {
270 323
271 /// Determines the constructor that the given pattern can be specialized to. 324 /// Determines the constructor that the given pattern can be specialized to.
272 pub(super) fn from_pat(cx: &MatchCheckCtx<'_>, pat: PatId) -> Self { 325 pub(super) fn from_pat(cx: &MatchCheckCtx<'_>, pat: PatId) -> Self {
273 let ty = cx.type_of(pat);
274 match cx.pattern_arena.borrow()[pat].kind.as_ref() { 326 match cx.pattern_arena.borrow()[pat].kind.as_ref() {
275 PatKind::Binding { .. } | PatKind::Wild => Wildcard, 327 PatKind::Binding { .. } | PatKind::Wild => Wildcard,
276 PatKind::Leaf { .. } | PatKind::Deref { .. } => Single, 328 PatKind::Leaf { .. } | PatKind::Deref { .. } => Single,
@@ -312,7 +364,7 @@ impl Constructor {
312 split_range.split(int_ranges.cloned()); 364 split_range.split(int_ranges.cloned());
313 split_range.iter().map(IntRange).collect() 365 split_range.iter().map(IntRange).collect()
314 } 366 }
315 Slice(_) => todo!("Constructor::split Slice"), 367 Slice(_) => unimplemented!(),
316 // Any other constructor can be used unchanged. 368 // Any other constructor can be used unchanged.
317 _ => smallvec![self.clone()], 369 _ => smallvec![self.clone()],
318 } 370 }
@@ -323,7 +375,7 @@ impl Constructor {
323 /// this checks for inclusion. 375 /// this checks for inclusion.
324 // We inline because this has a single call site in `Matrix::specialize_constructor`. 376 // We inline because this has a single call site in `Matrix::specialize_constructor`.
325 #[inline] 377 #[inline]
326 pub(super) fn is_covered_by(&self, pcx: PatCtxt<'_>, other: &Self) -> bool { 378 pub(super) fn is_covered_by(&self, _pcx: PatCtxt<'_>, other: &Self) -> bool {
327 // This must be kept in sync with `is_covered_by_any`. 379 // This must be kept in sync with `is_covered_by_any`.
328 match (self, other) { 380 match (self, other) {
329 // Wildcards cover anything 381 // Wildcards cover anything
@@ -336,10 +388,10 @@ impl Constructor {
336 388
337 (IntRange(self_range), IntRange(other_range)) => self_range.is_covered_by(other_range), 389 (IntRange(self_range), IntRange(other_range)) => self_range.is_covered_by(other_range),
338 (FloatRange(..), FloatRange(..)) => { 390 (FloatRange(..), FloatRange(..)) => {
339 todo!() 391 unimplemented!()
340 } 392 }
341 (Str(self_val), Str(other_val)) => { 393 (Str(..), Str(..)) => {
342 todo!() 394 unimplemented!()
343 } 395 }
344 (Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice), 396 (Slice(self_slice), Slice(other_slice)) => self_slice.is_covered_by(*other_slice),
345 397
@@ -358,7 +410,7 @@ impl Constructor {
358 /// Faster version of `is_covered_by` when applied to many constructors. `used_ctors` is 410 /// Faster version of `is_covered_by` when applied to many constructors. `used_ctors` is
359 /// assumed to be built from `matrix.head_ctors()` with wildcards filtered out, and `self` is 411 /// assumed to be built from `matrix.head_ctors()` with wildcards filtered out, and `self` is
360 /// assumed to have been split from a wildcard. 412 /// assumed to have been split from a wildcard.
361 fn is_covered_by_any(&self, pcx: PatCtxt<'_>, used_ctors: &[Constructor]) -> bool { 413 fn is_covered_by_any(&self, _pcx: PatCtxt<'_>, used_ctors: &[Constructor]) -> bool {
362 if used_ctors.is_empty() { 414 if used_ctors.is_empty() {
363 return false; 415 return false;
364 } 416 }
@@ -411,9 +463,10 @@ pub(super) struct SplitWildcard {
411impl SplitWildcard { 463impl SplitWildcard {
412 pub(super) fn new(pcx: PatCtxt<'_>) -> Self { 464 pub(super) fn new(pcx: PatCtxt<'_>) -> Self {
413 let cx = pcx.cx; 465 let cx = pcx.cx;
414 let make_range = 466 let make_range = |start, end, scalar| IntRange(IntRange::from_range(start, end, scalar));
415 |start, end, scalar| IntRange(IntRange::from_range(cx, start, end, scalar)); 467
416 // FIXME(iDawer) using NonExhaustive ctor for unhandled types 468 // Unhandled types are treated as non-exhaustive. Being explicit here instead of falling
469 // to catchall arm to ease further implementation.
417 let unhandled = || smallvec![NonExhaustive]; 470 let unhandled = || smallvec![NonExhaustive];
418 471
419 // This determines the set of all possible constructors for the type `pcx.ty`. For numbers, 472 // This determines the set of all possible constructors for the type `pcx.ty`. For numbers,
@@ -426,7 +479,7 @@ impl SplitWildcard {
426 // `cx.is_uninhabited()`). 479 // `cx.is_uninhabited()`).
427 let all_ctors = match pcx.ty.kind(&Interner) { 480 let all_ctors = match pcx.ty.kind(&Interner) {
428 TyKind::Scalar(Scalar::Bool) => smallvec![make_range(0, 1, Scalar::Bool)], 481 TyKind::Scalar(Scalar::Bool) => smallvec![make_range(0, 1, Scalar::Bool)],
429 // TyKind::Array(..) if ... => todo!(), 482 // TyKind::Array(..) if ... => unhandled(),
430 TyKind::Array(..) | TyKind::Slice(..) => unhandled(), 483 TyKind::Array(..) | TyKind::Slice(..) => unhandled(),
431 &TyKind::Adt(AdtId(hir_def::AdtId::EnumId(enum_id)), ref _substs) => { 484 &TyKind::Adt(AdtId(hir_def::AdtId::EnumId(enum_id)), ref _substs) => {
432 let enum_data = cx.db.enum_data(enum_id); 485 let enum_data = cx.db.enum_data(enum_id);
@@ -556,26 +609,6 @@ impl SplitWildcard {
556 } 609 }
557} 610}
558 611
559#[test]
560fn it_works2() {}
561
562/// Some fields need to be explicitly hidden away in certain cases; see the comment above the
563/// `Fields` struct. This struct represents such a potentially-hidden field.
564#[derive(Debug, Copy, Clone)]
565pub(super) enum FilteredField {
566 Kept(PatId),
567 Hidden,
568}
569
570impl FilteredField {
571 fn kept(self) -> Option<PatId> {
572 match self {
573 FilteredField::Kept(p) => Some(p),
574 FilteredField::Hidden => None,
575 }
576 }
577}
578
579/// A value can be decomposed into a constructor applied to some fields. This struct represents 612/// A value can be decomposed into a constructor applied to some fields. This struct represents
580/// those fields, generalized to allow patterns in each field. See also `Constructor`. 613/// those fields, generalized to allow patterns in each field. See also `Constructor`.
581/// This is constructed from a constructor using [`Fields::wildcards()`]. 614/// This is constructed from a constructor using [`Fields::wildcards()`].
@@ -623,14 +656,13 @@ impl Fields {
623 } 656 }
624 TyKind::Ref(.., rty) => Fields::from_single_pattern(wildcard_from_ty(rty)), 657 TyKind::Ref(.., rty) => Fields::from_single_pattern(wildcard_from_ty(rty)),
625 TyKind::Adt(AdtId(adt), substs) => { 658 TyKind::Adt(AdtId(adt), substs) => {
626 let adt_is_box = false; // TODO(iDawer): handle box patterns 659 let adt_is_box = false; // TODO(iDawer): implement this
627 if adt_is_box { 660 if adt_is_box {
628 // Use T as the sub pattern type of Box<T>. 661 // Use T as the sub pattern type of Box<T>.
629 let ty = substs.at(&Interner, 0).assert_ty_ref(&Interner); 662 let subst_ty = substs.at(&Interner, 0).assert_ty_ref(&Interner);
630 Fields::from_single_pattern(wildcard_from_ty(ty)) 663 Fields::from_single_pattern(wildcard_from_ty(subst_ty))
631 } else { 664 } else {
632 let variant_id = constructor.variant_id_for_adt(*adt, cx); 665 let variant_id = constructor.variant_id_for_adt(*adt);
633 let variant = variant_id.variant_data(cx.db.upcast());
634 let adt_is_local = 666 let adt_is_local =
635 variant_id.module(cx.db.upcast()).krate() == cx.module.krate(); 667 variant_id.module(cx.db.upcast()).krate() == cx.module.krate();
636 // Whether we must not match the fields of this variant exhaustively. 668 // Whether we must not match the fields of this variant exhaustively.
@@ -655,8 +687,8 @@ impl Fields {
655 } 687 }
656 _ => panic!("Unexpected type for `Single` constructor: {:?}", ty), 688 _ => panic!("Unexpected type for `Single` constructor: {:?}", ty),
657 }, 689 },
658 Slice(slice) => { 690 Slice(..) => {
659 todo!() 691 unimplemented!()
660 } 692 }
661 Str(..) | FloatRange(..) | IntRange(..) | NonExhaustive | Opaque | Missing 693 Str(..) | FloatRange(..) | IntRange(..) | NonExhaustive | Opaque | Missing
662 | Wildcard => Fields::Vec(Default::default()), 694 | Wildcard => Fields::Vec(Default::default()),
@@ -722,7 +754,7 @@ impl Fields {
722 } 754 }
723 _ => PatKind::Wild, 755 _ => PatKind::Wild,
724 }, 756 },
725 Constructor::Slice(slice) => UNHANDLED, 757 Constructor::Slice(_) => UNHANDLED,
726 Str(_) => UNHANDLED, 758 Str(_) => UNHANDLED,
727 FloatRange(..) => UNHANDLED, 759 FloatRange(..) => UNHANDLED,
728 Constructor::IntRange(_) => UNHANDLED, 760 Constructor::IntRange(_) => UNHANDLED,
@@ -828,7 +860,7 @@ impl Fields {
828 pat: PatId, 860 pat: PatId,
829 cx: &MatchCheckCtx<'_>, 861 cx: &MatchCheckCtx<'_>,
830 ) -> Self { 862 ) -> Self {
831 // TODO: these alocations and clones are so unfortunate (+1 for switching to references) 863 // FIXME(iDawer): these alocations and clones are so unfortunate (+1 for switching to references)
832 let mut arena = cx.pattern_arena.borrow_mut(); 864 let mut arena = cx.pattern_arena.borrow_mut();
833 match arena[pat].kind.as_ref() { 865 match arena[pat].kind.as_ref() {
834 PatKind::Deref { subpattern } => { 866 PatKind::Deref { subpattern } => {
@@ -860,6 +892,3 @@ fn is_field_list_non_exhaustive(variant_id: VariantId, cx: &MatchCheckCtx<'_>) -
860 }; 892 };
861 cx.db.attrs(attr_def_id).by_key("non_exhaustive").exists() 893 cx.db.attrs(attr_def_id).by_key("non_exhaustive").exists()
862} 894}
863
864#[test]
865fn it_works() {}
diff --git a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
index 01a7fb0d9..b01e3557c 100644
--- a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
+++ b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs
@@ -1,9 +1,279 @@
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// https://github.com/rust-lang/rust/blob/25c15cdbe/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//!
4use std::{cell::RefCell, iter::FromIterator, ops::Index, sync::Arc}; 4//! -----
5 5//!
6use hir_def::{body::Body, expr::ExprId, HasModule, ModuleId}; 6//! This file includes the logic for exhaustiveness and reachability checking for pattern-matching.
7//! Specifically, given a list of patterns for a type, we can tell whether:
8//! (a) each pattern is reachable (reachability)
9//! (b) the patterns cover every possible value for the type (exhaustiveness)
10//!
11//! The algorithm implemented here is a modified version of the one described in [this
12//! paper](http://moscova.inria.fr/~maranget/papers/warn/index.html). We have however generalized
13//! it to accommodate the variety of patterns that Rust supports. We thus explain our version here,
14//! without being as rigorous.
15//!
16//!
17//! # Summary
18//!
19//! The core of the algorithm is the notion of "usefulness". A pattern `q` is said to be *useful*
20//! relative to another pattern `p` of the same type if there is a value that is matched by `q` and
21//! not matched by `p`. This generalizes to many `p`s: `q` is useful w.r.t. a list of patterns
22//! `p_1 .. p_n` if there is a value that is matched by `q` and by none of the `p_i`. We write
23//! `usefulness(p_1 .. p_n, q)` for a function that returns a list of such values. The aim of this
24//! file is to compute it efficiently.
25//!
26//! This is enough to compute reachability: a pattern in a `match` expression is reachable iff it
27//! is useful w.r.t. the patterns above it:
28//! ```rust
29//! match x {
30//! Some(_) => ...,
31//! None => ..., // reachable: `None` is matched by this but not the branch above
32//! Some(0) => ..., // unreachable: all the values this matches are already matched by
33//! // `Some(_)` above
34//! }
35//! ```
36//!
37//! This is also enough to compute exhaustiveness: a match is exhaustive iff the wildcard `_`
38//! pattern is _not_ useful w.r.t. the patterns in the match. The values returned by `usefulness`
39//! are used to tell the user which values are missing.
40//! ```rust
41//! match x {
42//! Some(0) => ...,
43//! None => ...,
44//! // not exhaustive: `_` is useful because it matches `Some(1)`
45//! }
46//! ```
47//!
48//! The entrypoint of this file is the [`compute_match_usefulness`] function, which computes
49//! reachability for each match branch and exhaustiveness for the whole match.
50//!
51//!
52//! # Constructors and fields
53//!
54//! Note: we will often abbreviate "constructor" as "ctor".
55//!
56//! The idea that powers everything that is done in this file is the following: a (matcheable)
57//! value is made from a constructor applied to a number of subvalues. Examples of constructors are
58//! `Some`, `None`, `(,)` (the 2-tuple constructor), `Foo {..}` (the constructor for a struct
59//! `Foo`), and `2` (the constructor for the number `2`). This is natural when we think of
60//! pattern-matching, and this is the basis for what follows.
61//!
62//! Some of the ctors listed above might feel weird: `None` and `2` don't take any arguments.
63//! That's ok: those are ctors that take a list of 0 arguments; they are the simplest case of
64//! ctors. We treat `2` as a ctor because `u64` and other number types behave exactly like a huge
65//! `enum`, with one variant for each number. This allows us to see any matcheable value as made up
66//! from a tree of ctors, each having a set number of children. For example: `Foo { bar: None,
67//! baz: Ok(0) }` is made from 4 different ctors, namely `Foo{..}`, `None`, `Ok` and `0`.
68//!
69//! This idea can be extended to patterns: they are also made from constructors applied to fields.
70//! A pattern for a given type is allowed to use all the ctors for values of that type (which we
71//! call "value constructors"), but there are also pattern-only ctors. The most important one is
72//! the wildcard (`_`), and the others are integer ranges (`0..=10`), variable-length slices (`[x,
73//! ..]`), and or-patterns (`Ok(0) | Err(_)`). Examples of valid patterns are `42`, `Some(_)`, `Foo
74//! { bar: Some(0) | None, baz: _ }`. Note that a binder in a pattern (e.g. `Some(x)`) matches the
75//! same values as a wildcard (e.g. `Some(_)`), so we treat both as wildcards.
76//!
77//! From this deconstruction we can compute whether a given value matches a given pattern; we
78//! simply look at ctors one at a time. Given a pattern `p` and a value `v`, we want to compute
79//! `matches!(v, p)`. It's mostly straightforward: we compare the head ctors and when they match
80//! we compare their fields recursively. A few representative examples:
81//!
82//! - `matches!(v, _) := true`
83//! - `matches!((v0, v1), (p0, p1)) := matches!(v0, p0) && matches!(v1, p1)`
84//! - `matches!(Foo { bar: v0, baz: v1 }, Foo { bar: p0, baz: p1 }) := matches!(v0, p0) && matches!(v1, p1)`
85//! - `matches!(Ok(v0), Ok(p0)) := matches!(v0, p0)`
86//! - `matches!(Ok(v0), Err(p0)) := false` (incompatible variants)
87//! - `matches!(v, 1..=100) := matches!(v, 1) || ... || matches!(v, 100)`
88//! - `matches!([v0], [p0, .., p1]) := false` (incompatible lengths)
89//! - `matches!([v0, v1, v2], [p0, .., p1]) := matches!(v0, p0) && matches!(v2, p1)`
90//! - `matches!(v, p0 | p1) := matches!(v, p0) || matches!(v, p1)`
91//!
92//! Constructors, fields and relevant operations are defined in the [`super::deconstruct_pat`] module.
93//!
94//! Note: this constructors/fields distinction may not straightforwardly apply to every Rust type.
95//! For example a value of type `Rc<u64>` can't be deconstructed that way, and `&str` has an
96//! infinitude of constructors. There are also subtleties with visibility of fields and
97//! uninhabitedness and various other things. The constructors idea can be extended to handle most
98//! of these subtleties though; caveats are documented where relevant throughout the code.
99//!
100//! Whether constructors cover each other is computed by [`Constructor::is_covered_by`].
101//!
102//!
103//! # Specialization
104//!
105//! Recall that we wish to compute `usefulness(p_1 .. p_n, q)`: given a list of patterns `p_1 ..
106//! p_n` and a pattern `q`, all of the same type, we want to find a list of values (called
107//! "witnesses") that are matched by `q` and by none of the `p_i`. We obviously don't just
108//! enumerate all possible values. From the discussion above we see that we can proceed
109//! ctor-by-ctor: for each value ctor of the given type, we ask "is there a value that starts with
110//! this constructor and matches `q` and none of the `p_i`?". As we saw above, there's a lot we can
111//! say from knowing only the first constructor of our candidate value.
112//!
113//! Let's take the following example:
114//! ```
115//! match x {
116//! Enum::Variant1(_) => {} // `p1`
117//! Enum::Variant2(None, 0) => {} // `p2`
118//! Enum::Variant2(Some(_), 0) => {} // `q`
119//! }
120//! ```
121//!
122//! We can easily see that if our candidate value `v` starts with `Variant1` it will not match `q`.
123//! If `v = Variant2(v0, v1)` however, whether or not it matches `p2` and `q` will depend on `v0`
124//! and `v1`. In fact, such a `v` will be a witness of usefulness of `q` exactly when the tuple
125//! `(v0, v1)` is a witness of usefulness of `q'` in the following reduced match:
126//!
127//! ```
128//! match x {
129//! (None, 0) => {} // `p2'`
130//! (Some(_), 0) => {} // `q'`
131//! }
132//! ```
133//!
134//! This motivates a new step in computing usefulness, that we call _specialization_.
135//! Specialization consist of filtering a list of patterns for those that match a constructor, and
136//! then looking into the constructor's fields. This enables usefulness to be computed recursively.
137//!
138//! Instead of acting on a single pattern in each row, we will consider a list of patterns for each
139//! row, and we call such a list a _pattern-stack_. The idea is that we will specialize the
140//! leftmost pattern, which amounts to popping the constructor and pushing its fields, which feels
141//! like a stack. We note a pattern-stack simply with `[p_1 ... p_n]`.
142//! Here's a sequence of specializations of a list of pattern-stacks, to illustrate what's
143//! happening:
144//! ```
145//! [Enum::Variant1(_)]
146//! [Enum::Variant2(None, 0)]
147//! [Enum::Variant2(Some(_), 0)]
148//! //==>> specialize with `Variant2`
149//! [None, 0]
150//! [Some(_), 0]
151//! //==>> specialize with `Some`
152//! [_, 0]
153//! //==>> specialize with `true` (say the type was `bool`)
154//! [0]
155//! //==>> specialize with `0`
156//! []
157//! ```
158//!
159//! The function `specialize(c, p)` takes a value constructor `c` and a pattern `p`, and returns 0
160//! or more pattern-stacks. If `c` does not match the head constructor of `p`, it returns nothing;
161//! otherwise if returns the fields of the constructor. This only returns more than one
162//! pattern-stack if `p` has a pattern-only constructor.
163//!
164//! - Specializing for the wrong constructor returns nothing
165//!
166//! `specialize(None, Some(p0)) := []`
167//!
168//! - Specializing for the correct constructor returns a single row with the fields
169//!
170//! `specialize(Variant1, Variant1(p0, p1, p2)) := [[p0, p1, p2]]`
171//!
172//! `specialize(Foo{..}, Foo { bar: p0, baz: p1 }) := [[p0, p1]]`
173//!
174//! - For or-patterns, we specialize each branch and concatenate the results
175//!
176//! `specialize(c, p0 | p1) := specialize(c, p0) ++ specialize(c, p1)`
177//!
178//! - We treat the other pattern constructors as if they were a large or-pattern of all the
179//! possibilities:
180//!
181//! `specialize(c, _) := specialize(c, Variant1(_) | Variant2(_, _) | ...)`
182//!
183//! `specialize(c, 1..=100) := specialize(c, 1 | ... | 100)`
184//!
185//! `specialize(c, [p0, .., p1]) := specialize(c, [p0, p1] | [p0, _, p1] | [p0, _, _, p1] | ...)`
186//!
187//! - If `c` is a pattern-only constructor, `specialize` is defined on a case-by-case basis. See
188//! the discussion about constructor splitting in [`super::deconstruct_pat`].
189//!
190//!
191//! We then extend this function to work with pattern-stacks as input, by acting on the first
192//! column and keeping the other columns untouched.
193//!
194//! Specialization for the whole matrix is done in [`Matrix::specialize_constructor`]. Note that
195//! or-patterns in the first column are expanded before being stored in the matrix. Specialization
196//! for a single patstack is done from a combination of [`Constructor::is_covered_by`] and
197//! [`PatStack::pop_head_constructor`]. The internals of how it's done mostly live in the
198//! [`Fields`] struct.
199//!
200//!
201//! # Computing usefulness
202//!
203//! We now have all we need to compute usefulness. The inputs to usefulness are a list of
204//! pattern-stacks `p_1 ... p_n` (one per row), and a new pattern_stack `q`. The paper and this
205//! file calls the list of patstacks a _matrix_. They must all have the same number of columns and
206//! the patterns in a given column must all have the same type. `usefulness` returns a (possibly
207//! empty) list of witnesses of usefulness. These witnesses will also be pattern-stacks.
208//!
209//! - base case: `n_columns == 0`.
210//! Since a pattern-stack functions like a tuple of patterns, an empty one functions like the
211//! unit type. Thus `q` is useful iff there are no rows above it, i.e. if `n == 0`.
212//!
213//! - inductive case: `n_columns > 0`.
214//! We need a way to list the constructors we want to try. We will be more clever in the next
215//! section but for now assume we list all value constructors for the type of the first column.
216//!
217//! - for each such ctor `c`:
218//!
219//! - for each `q'` returned by `specialize(c, q)`:
220//!
221//! - we compute `usefulness(specialize(c, p_1) ... specialize(c, p_n), q')`
222//!
223//! - for each witness found, we revert specialization by pushing the constructor `c` on top.
224//!
225//! - We return the concatenation of all the witnesses found, if any.
226//!
227//! Example:
228//! ```
229//! [Some(true)] // p_1
230//! [None] // p_2
231//! [Some(_)] // q
232//! //==>> try `None`: `specialize(None, q)` returns nothing
233//! //==>> try `Some`: `specialize(Some, q)` returns a single row
234//! [true] // p_1'
235//! [_] // q'
236//! //==>> try `true`: `specialize(true, q')` returns a single row
237//! [] // p_1''
238//! [] // q''
239//! //==>> base case; `n != 0` so `q''` is not useful.
240//! //==>> go back up a step
241//! [true] // p_1'
242//! [_] // q'
243//! //==>> try `false`: `specialize(false, q')` returns a single row
244//! [] // q''
245//! //==>> base case; `n == 0` so `q''` is useful. We return the single witness `[]`
246//! witnesses:
247//! []
248//! //==>> undo the specialization with `false`
249//! witnesses:
250//! [false]
251//! //==>> undo the specialization with `Some`
252//! witnesses:
253//! [Some(false)]
254//! //==>> we have tried all the constructors. The output is the single witness `[Some(false)]`.
255//! ```
256//!
257//! This computation is done in [`is_useful`]. In practice we don't care about the list of
258//! witnesses when computing reachability; we only need to know whether any exist. We do keep the
259//! witnesses when computing exhaustiveness to report them to the user.
260//!
261//!
262//! # Making usefulness tractable: constructor splitting
263//!
264//! We're missing one last detail: which constructors do we list? Naively listing all value
265//! constructors cannot work for types like `u64` or `&str`, so we need to be more clever. The
266//! first obvious insight is that we only want to list constructors that are covered by the head
267//! constructor of `q`. If it's a value constructor, we only try that one. If it's a pattern-only
268//! constructor, we use the final clever idea for this algorithm: _constructor splitting_, where we
269//! group together constructors that behave the same.
270//!
271//! The details are not necessary to understand this file, so we explain them in
272//! [`super::deconstruct_pat`]. Splitting is done by the [`Constructor::split`] function.
273
274use std::{cell::RefCell, iter::FromIterator};
275
276use hir_def::{expr::ExprId, HasModule, ModuleId};
7use la_arena::Arena; 277use la_arena::Arena;
8use once_cell::unsync::OnceCell; 278use once_cell::unsync::OnceCell;
9use rustc_hash::FxHashMap; 279use rustc_hash::FxHashMap;
@@ -16,16 +286,11 @@ use super::{
16 Pat, PatId, PatKind, PatternFoldable, PatternFolder, 286 Pat, PatId, PatKind, PatternFoldable, PatternFolder,
17}; 287};
18 288
19use self::{ 289use self::{helper::PatIdExt, Usefulness::*, WitnessPreference::*};
20 helper::{Captures, PatIdExt},
21 Usefulness::*,
22 WitnessPreference::*,
23};
24 290
25pub(crate) struct MatchCheckCtx<'a> { 291pub(crate) struct MatchCheckCtx<'a> {
26 pub(crate) module: ModuleId, 292 pub(crate) module: ModuleId,
27 pub(crate) match_expr: ExprId, 293 pub(crate) match_expr: ExprId,
28 pub(crate) body: Arc<Body>,
29 pub(crate) infer: &'a InferenceResult, 294 pub(crate) infer: &'a InferenceResult,
30 pub(crate) db: &'a dyn HirDatabase, 295 pub(crate) db: &'a dyn HirDatabase,
31 /// Lowered patterns from self.body.pats plus generated by the check. 296 /// Lowered patterns from self.body.pats plus generated by the check.
@@ -33,7 +298,7 @@ pub(crate) struct MatchCheckCtx<'a> {
33} 298}
34 299
35impl<'a> MatchCheckCtx<'a> { 300impl<'a> MatchCheckCtx<'a> {
36 pub(super) fn is_uninhabited(&self, ty: &Ty) -> bool { 301 pub(super) fn is_uninhabited(&self, _ty: &Ty) -> bool {
37 // FIXME(iDawer) implement exhaustive_patterns feature. More info in: 302 // FIXME(iDawer) implement exhaustive_patterns feature. More info in:
38 // Tracking issue for RFC 1872: exhaustive_patterns feature https://github.com/rust-lang/rust/issues/51085 303 // Tracking issue for RFC 1872: exhaustive_patterns feature https://github.com/rust-lang/rust/issues/51085
39 false 304 false
@@ -90,7 +355,7 @@ impl PatternFolder for LiteralExpander {
90} 355}
91 356
92impl Pat { 357impl Pat {
93 fn is_wildcard(&self) -> bool { 358 fn _is_wildcard(&self) -> bool {
94 matches!(*self.kind, PatKind::Binding { subpattern: None, .. } | PatKind::Wild) 359 matches!(*self.kind, PatKind::Binding { subpattern: None, .. } | PatKind::Wild)
95 } 360 }
96} 361}
@@ -102,11 +367,11 @@ impl PatIdExt for PatId {
102 367
103 /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns. 368 /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns.
104 fn expand_or_pat(self, cx: &MatchCheckCtx<'_>) -> Vec<Self> { 369 fn expand_or_pat(self, cx: &MatchCheckCtx<'_>) -> Vec<Self> {
105 fn expand(pat: PatId, vec: &mut Vec<PatId>, mut pat_arena: &mut PatternArena) { 370 fn expand(pat: PatId, vec: &mut Vec<PatId>, pat_arena: &mut PatternArena) {
106 if let PatKind::Or { pats } = pat_arena[pat].kind.as_ref() { 371 if let PatKind::Or { pats } = pat_arena[pat].kind.as_ref() {
107 let pats = pats.clone(); 372 let pats = pats.clone();
108 for pat in pats { 373 for pat in pats {
109 // TODO(iDawer): Ugh, I want to go back to references (PatId -> &Pat) 374 // FIXME(iDawer): Ugh, I want to go back to references (PatId -> &Pat)
110 let pat = pat_arena.alloc(pat.clone()); 375 let pat = pat_arena.alloc(pat.clone());
111 expand(pat, vec, pat_arena); 376 expand(pat, vec, pat_arena);
112 } 377 }
@@ -157,10 +422,6 @@ impl PatStack {
157 self.head_ctor.get_or_init(|| Constructor::from_pat(cx, self.head())) 422 self.head_ctor.get_or_init(|| Constructor::from_pat(cx, self.head()))
158 } 423 }
159 424
160 fn iter(&self) -> impl Iterator<Item = PatId> + '_ {
161 self.pats.iter().copied()
162 }
163
164 // Recursively expand the first pattern into its subpatterns. Only useful if the pattern is an 425 // Recursively expand the first pattern into its subpatterns. Only useful if the pattern is an
165 // or-pattern. Panics if `self` is empty. 426 // or-pattern. Panics if `self` is empty.
166 fn expand_or_pat(&self, cx: &MatchCheckCtx<'_>) -> impl Iterator<Item = PatStack> + '_ { 427 fn expand_or_pat(&self, cx: &MatchCheckCtx<'_>) -> impl Iterator<Item = PatStack> + '_ {
@@ -224,7 +485,7 @@ impl Matrix {
224 } 485 }
225 486
226 /// Number of columns of this matrix. `None` is the matrix is empty. 487 /// Number of columns of this matrix. `None` is the matrix is empty.
227 pub(super) fn column_count(&self) -> Option<usize> { 488 pub(super) fn _column_count(&self) -> Option<usize> {
228 self.patterns.get(0).map(|r| r.len()) 489 self.patterns.get(0).map(|r| r.len())
229 } 490 }
230 491
@@ -770,7 +1031,6 @@ fn is_useful(
770 assert!(rows.iter().all(|r| r.len() == v.len())); 1031 assert!(rows.iter().all(|r| r.len() == v.len()));
771 1032
772 // FIXME(Nadrieril): Hack to work around type normalization issues (see rust-lang/rust#72476). 1033 // FIXME(Nadrieril): Hack to work around type normalization issues (see rust-lang/rust#72476).
773 // TODO(iDawer): ty.strip_references() ?
774 let ty = matrix.heads().next().map_or(cx.type_of(v.head()), |r| cx.type_of(r)); 1034 let ty = matrix.heads().next().map_or(cx.type_of(v.head()), |r| cx.type_of(r));
775 let pcx = PatCtxt { cx, ty: &ty, is_top_level }; 1035 let pcx = PatCtxt { cx, ty: &ty, is_top_level };
776 1036
@@ -848,7 +1108,7 @@ pub(crate) enum Reachability {
848/// The output of checking a match for exhaustiveness and arm reachability. 1108/// The output of checking a match for exhaustiveness and arm reachability.
849pub(crate) struct UsefulnessReport { 1109pub(crate) struct UsefulnessReport {
850 /// For each arm of the input, whether that arm is reachable after the arms above it. 1110 /// For each arm of the input, whether that arm is reachable after the arms above it.
851 pub(crate) arm_usefulness: Vec<(MatchArm, Reachability)>, 1111 pub(crate) _arm_usefulness: Vec<(MatchArm, Reachability)>,
852 /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of 1112 /// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of
853 /// exhaustiveness. 1113 /// exhaustiveness.
854 pub(crate) non_exhaustiveness_witnesses: Vec<Pat>, 1114 pub(crate) non_exhaustiveness_witnesses: Vec<Pat>,
@@ -892,14 +1152,12 @@ pub(crate) fn compute_match_usefulness(
892 WithWitnesses(pats) => pats.into_iter().map(Witness::single_pattern).collect(), 1152 WithWitnesses(pats) => pats.into_iter().map(Witness::single_pattern).collect(),
893 NoWitnesses(_) => panic!("bug"), 1153 NoWitnesses(_) => panic!("bug"),
894 }; 1154 };
895 UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses } 1155 UsefulnessReport { _arm_usefulness: arm_usefulness, non_exhaustiveness_witnesses }
896} 1156}
897 1157
898pub(crate) type PatternArena = Arena<Pat>; 1158pub(crate) type PatternArena = Arena<Pat>;
899 1159
900mod helper { 1160mod helper {
901 use hir_def::expr::{Pat, PatId};
902
903 use super::MatchCheckCtx; 1161 use super::MatchCheckCtx;
904 1162
905 pub(super) trait PatIdExt: Sized { 1163 pub(super) trait PatIdExt: Sized {
@@ -920,6 +1178,3 @@ mod helper {
920 1178
921 impl<'a, T: ?Sized> Captures<'a> for T {} 1179 impl<'a, T: ?Sized> Captures<'a> for T {}
922} 1180}
923
924#[test]
925fn it_works() {}