1 //! Simplifying Candidates
3 //! *Simplifying* a match pair `place @ pattern` means breaking it down
4 //! into bindings or other, simpler match pairs. For example:
6 //! - `place @ (P1, P2)` can be simplified to `[place.0 @ P1, place.1 @ P2]`
7 //! - `place @ x` can be simplified to `[]` by binding `x` to `place`
9 //! The `simplify_candidate` routine just repeatedly applies these
10 //! sort of simplifications until there is nothing left to
11 //! simplify. Match pairs cannot be simplified if they require some
12 //! sort of test: for example, testing which variant an enum is, or
13 //! testing a value against a constant.
15 use crate::build
::expr
::as_place
::PlaceBuilder
;
16 use crate::build
::matches
::{Ascription, Binding, Candidate, MatchPair}
;
17 use crate::build
::Builder
;
18 use rustc_hir
::RangeEnd
;
19 use rustc_middle
::thir
::{self, *}
;
21 use rustc_middle
::ty
::layout
::IntegerExt
;
22 use rustc_target
::abi
::{Integer, Size}
;
26 impl<'a
, 'tcx
> Builder
<'a
, 'tcx
> {
27 /// Simplify a candidate so that all match pairs require a test.
29 /// This method will also split a candidate, in which the only
30 /// match-pair is an or-pattern, into multiple candidates.
38 /// only generates a single switch. If this happens this method returns
40 pub(super) fn simplify_candidate
<'pat
>(
42 candidate
: &mut Candidate
<'pat
, 'tcx
>,
44 // repeatedly simplify match pairs until fixed point is reached
45 debug
!(?candidate
, "simplify_candidate");
47 // existing_bindings and new_bindings exists to keep the semantics in order.
48 // Reversing the binding order for bindings after `@` changes the binding order in places
49 // it shouldn't be changed, for example `let (Some(a), Some(b)) = (x, y)`
51 // To avoid this, the binding occurs in the following manner:
52 // * the bindings for one iteration of the following loop occurs in order (i.e. left to
54 // * the bindings from the previous iteration of the loop is prepended to the bindings from
55 // the current iteration (in the implementation this is done by mem::swap and extend)
56 // * after all iterations, these new bindings are then appended to the bindings that were
57 // preexisting (i.e. `candidate.binding` when the function was called).
60 // candidate.bindings = [1, 2, 3]
61 // binding in iter 1: [4, 5]
62 // binding in iter 2: [6, 7]
64 // final binding: [1, 2, 3, 6, 7, 4, 5]
65 let mut existing_bindings
= mem
::take(&mut candidate
.bindings
);
66 let mut new_bindings
= Vec
::new();
68 let match_pairs
= mem
::take(&mut candidate
.match_pairs
);
70 if let [MatchPair { pattern: Pat { kind: box PatKind::Or { pats }
, .. }, place
}] =
73 existing_bindings
.extend_from_slice(&new_bindings
);
74 mem
::swap(&mut candidate
.bindings
, &mut existing_bindings
);
75 candidate
.subcandidates
=
76 self.create_or_subcandidates(candidate
, place
.clone(), pats
);
80 let mut changed
= false;
81 for match_pair
in match_pairs
{
82 match self.simplify_match_pair(match_pair
, candidate
) {
87 candidate
.match_pairs
.push(match_pair
);
91 // Avoid issue #69971: the binding order should be right to left if there are more
92 // bindings after `@` to please the borrow checker
94 // struct NonCopyStruct {
98 // fn foo1(x: NonCopyStruct) {
99 // let y @ NonCopyStruct { copy_field: z } = x;
100 // // the above should turn into
101 // let z = x.copy_field;
104 candidate
.bindings
.extend_from_slice(&new_bindings
);
105 mem
::swap(&mut candidate
.bindings
, &mut new_bindings
);
106 candidate
.bindings
.clear();
109 existing_bindings
.extend_from_slice(&new_bindings
);
110 mem
::swap(&mut candidate
.bindings
, &mut existing_bindings
);
111 // Move or-patterns to the end, because they can result in us
112 // creating additional candidates, so we want to test them as
116 .sort_by_key(|pair
| matches
!(*pair
.pattern
.kind
, PatKind
::Or { .. }
));
117 debug
!(simplified
= ?candidate
, "simplify_candidate");
118 return false; // if we were not able to simplify any, done.
123 /// Given `candidate` that has a single or-pattern for its match-pairs,
124 /// creates a fresh candidate for each of its input subpatterns passed via
126 fn create_or_subcandidates
<'pat
>(
128 candidate
: &Candidate
<'pat
, 'tcx
>,
129 place
: PlaceBuilder
<'tcx
>,
130 pats
: &'pat
[Pat
<'tcx
>],
131 ) -> Vec
<Candidate
<'pat
, 'tcx
>> {
134 let mut candidate
= Candidate
::new(place
.clone(), pat
, candidate
.has_guard
);
135 self.simplify_candidate(&mut candidate
);
141 /// Tries to simplify `match_pair`, returning `Ok(())` if
142 /// successful. If successful, new match pairs and bindings will
143 /// have been pushed into the candidate. If no simplification is
144 /// possible, `Err` is returned and no changes are made to
146 fn simplify_match_pair
<'pat
>(
148 match_pair
: MatchPair
<'pat
, 'tcx
>,
149 candidate
: &mut Candidate
<'pat
, 'tcx
>,
150 ) -> Result
<(), MatchPair
<'pat
, 'tcx
>> {
152 match *match_pair
.pattern
.kind
{
153 PatKind
::AscribeUserType
{
155 ascription
: thir
::Ascription { ref annotation, variance }
,
157 // Apply the type ascription to the value at `match_pair.place`, which is the
158 if let Ok(place_resolved
) =
159 match_pair
.place
.clone().try_upvars_resolved(self.tcx
, self.typeck_results
)
161 candidate
.ascriptions
.push(Ascription
{
162 annotation
: annotation
.clone(),
163 source
: place_resolved
.into_place(self.tcx
, self.typeck_results
),
168 candidate
.match_pairs
.push(MatchPair
::new(match_pair
.place
, subpattern
));
174 // nothing left to do
187 if let Ok(place_resolved
) =
188 match_pair
.place
.clone().try_upvars_resolved(self.tcx
, self.typeck_results
)
190 candidate
.bindings
.push(Binding
{
191 span
: match_pair
.pattern
.span
,
192 source
: place_resolved
.into_place(self.tcx
, self.typeck_results
),
198 if let Some(subpattern
) = subpattern
.as_ref() {
199 // this is the `x @ P` case; have to keep matching against `P` now
200 candidate
.match_pairs
.push(MatchPair
::new(match_pair
.place
, subpattern
));
206 PatKind
::Constant { .. }
=> {
207 // FIXME normalize patterns when possible
211 PatKind
::Range(PatRange { lo, hi, end }
) => {
212 let (range
, bias
) = match *lo
.ty().kind() {
214 (Some(('
\u{0000}'
as u128
, '
\u{10FFFF}'
as u128
, Size
::from_bits(32))), 0)
217 let size
= Integer
::from_int_ty(&tcx
, ity
).size();
218 let max
= size
.truncate(u128
::MAX
);
219 let bias
= 1u128 << (size
.bits() - 1);
220 (Some((0, max
, size
)), bias
)
223 let size
= Integer
::from_uint_ty(&tcx
, uty
).size();
224 let max
= size
.truncate(u128
::MAX
);
225 (Some((0, max
, size
)), 0)
229 if let Some((min
, max
, sz
)) = range
{
230 // We want to compare ranges numerically, but the order of the bitwise
231 // representation of signed integers does not match their numeric order. Thus,
232 // to correct the ordering, we need to shift the range of signed integers to
233 // correct the comparison. This is achieved by XORing with a bias (see
234 // pattern/_match.rs for another pertinent example of this pattern).
236 // Also, for performance, it's important to only do the second `try_to_bits` if
238 let lo
= lo
.try_to_bits(sz
).unwrap() ^ bias
;
240 let hi
= hi
.try_to_bits(sz
).unwrap() ^ bias
;
241 if hi
> max
|| hi
== max
&& end
== RangeEnd
::Included
{
242 // Irrefutable pattern match.
250 PatKind
::Slice { ref prefix, ref slice, ref suffix }
=> {
251 if prefix
.is_empty() && slice
.is_some() && suffix
.is_empty() {
253 self.prefix_slice_suffix(
254 &mut candidate
.match_pairs
,
266 PatKind
::Variant { adt_def, substs, variant_index, ref subpatterns }
=> {
267 let irrefutable
= adt_def
.variants().iter_enumerated().all(|(i
, v
)| {
268 i
== variant_index
|| {
269 self.tcx
.features().exhaustive_patterns
279 }) && (adt_def
.did().is_local()
280 || !adt_def
.is_variant_list_non_exhaustive());
282 let place_builder
= match_pair
.place
.downcast(adt_def
, variant_index
);
285 .extend(self.field_match_pairs(place_builder
, subpatterns
));
292 PatKind
::Array { ref prefix, ref slice, ref suffix }
=> {
293 self.prefix_slice_suffix(
294 &mut candidate
.match_pairs
,
303 PatKind
::Leaf { ref subpatterns }
=> {
304 // tuple struct, match subpats (if any)
305 candidate
.match_pairs
.extend(self.field_match_pairs(match_pair
.place
, subpatterns
));
309 PatKind
::Deref { ref subpattern }
=> {
310 let place_builder
= match_pair
.place
.deref();
311 candidate
.match_pairs
.push(MatchPair
::new(place_builder
, subpattern
));
315 PatKind
::Or { .. }
=> Err(match_pair
),