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 #[instrument(skip(self, candidate), level = "debug")]
41 pub(super) fn simplify_candidate<'pat>(
43 candidate: &mut Candidate<'pat, 'tcx>,
45 // repeatedly simplify match pairs until fixed point is reached
46 debug!("{candidate:#?}");
48 // existing_bindings and new_bindings exists to keep the semantics in order.
49 // Reversing the binding order for bindings after `@` changes the binding order in places
50 // it shouldn't be changed, for example `let (Some(a), Some(b)) = (x, y)`
52 // To avoid this, the binding occurs in the following manner:
53 // * the bindings for one iteration of the following loop occurs in order (i.e. left to
55 // * the bindings from the previous iteration of the loop is prepended to the bindings from
56 // the current iteration (in the implementation this is done by mem::swap and extend)
57 // * after all iterations, these new bindings are then appended to the bindings that were
58 // preexisting (i.e. `candidate.binding` when the function was called).
61 // candidate.bindings = [1, 2, 3]
62 // binding in iter 1: [4, 5]
63 // binding in iter 2: [6, 7]
65 // final binding: [1, 2, 3, 6, 7, 4, 5]
66 let mut existing_bindings = mem::take(&mut candidate.bindings);
67 let mut new_bindings = Vec::new();
69 let match_pairs = mem::take(&mut candidate.match_pairs);
71 if let [MatchPair { pattern: Pat { kind: PatKind::Or { pats }, .. }, place }] =
74 existing_bindings.extend_from_slice(&new_bindings);
75 mem::swap(&mut candidate.bindings, &mut existing_bindings);
76 candidate.subcandidates =
77 self.create_or_subcandidates(candidate, place.clone(), pats);
81 let mut changed = false;
82 for match_pair in match_pairs {
83 match self.simplify_match_pair(match_pair, candidate) {
88 candidate.match_pairs.push(match_pair);
92 // Avoid issue #69971: the binding order should be right to left if there are more
93 // bindings after `@` to please the borrow checker
95 // struct NonCopyStruct {
99 // fn foo1(x: NonCopyStruct) {
100 // let y @ NonCopyStruct { copy_field: z } = x;
101 // // the above should turn into
102 // let z = x.copy_field;
105 candidate.bindings.extend_from_slice(&new_bindings);
106 mem::swap(&mut candidate.bindings, &mut new_bindings);
107 candidate.bindings.clear();
110 existing_bindings.extend_from_slice(&new_bindings);
111 mem::swap(&mut candidate.bindings, &mut existing_bindings);
112 // Move or-patterns to the end, because they can result in us
113 // creating additional candidates, so we want to test them as
117 .sort_by_key(|pair| matches!(pair.pattern.kind, PatKind::Or { .. }));
118 debug!(simplified = ?candidate, "simplify_candidate");
119 return false; // if we were not able to simplify any, done.
124 /// Given `candidate` that has a single or-pattern for its match-pairs,
125 /// creates a fresh candidate for each of its input subpatterns passed via
127 fn create_or_subcandidates<'pat>(
129 candidate: &Candidate<'pat, 'tcx>,
130 place: PlaceBuilder<'tcx>,
131 pats: &'pat [Box<Pat<'tcx>>],
132 ) -> Vec<Candidate<'pat, 'tcx>> {
135 let mut candidate = Candidate::new(place.clone(), pat, candidate.has_guard, self);
136 self.simplify_candidate(&mut candidate);
142 /// Tries to simplify `match_pair`, returning `Ok(())` if
143 /// successful. If successful, new match pairs and bindings will
144 /// have been pushed into the candidate. If no simplification is
145 /// possible, `Err` is returned and no changes are made to
147 fn simplify_match_pair<'pat>(
149 match_pair: MatchPair<'pat, 'tcx>,
150 candidate: &mut Candidate<'pat, 'tcx>,
151 ) -> Result<(), MatchPair<'pat, 'tcx>> {
153 match match_pair.pattern.kind {
154 PatKind::AscribeUserType {
156 ascription: thir::Ascription { ref annotation, variance },
158 // Apply the type ascription to the value at `match_pair.place`, which is the
159 if let Ok(place_resolved) = match_pair.place.clone().try_upvars_resolved(self) {
160 candidate.ascriptions.push(Ascription {
161 annotation: annotation.clone(),
162 source: place_resolved.into_place(self),
167 candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern, self));
173 // nothing left to do
186 if let Ok(place_resolved) = match_pair.place.clone().try_upvars_resolved(self) {
187 candidate.bindings.push(Binding {
188 span: match_pair.pattern.span,
189 source: place_resolved.into_place(self),
195 if let Some(subpattern) = subpattern.as_ref() {
196 // this is the `x @ P` case; have to keep matching against `P` now
197 candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern, self));
203 PatKind::Constant { .. } => {
204 // FIXME normalize patterns when possible
208 PatKind::Range(box PatRange { lo, hi, end }) => {
209 let (range, bias) = match *lo.ty().kind() {
211 (Some(('\u{0000}' as u128, '\u{10FFFF}' as u128, Size::from_bits(32))), 0)
214 let size = Integer::from_int_ty(&tcx, ity).size();
215 let max = size.truncate(u128::MAX);
216 let bias = 1u128 << (size.bits() - 1);
217 (Some((0, max, size)), bias)
220 let size = Integer::from_uint_ty(&tcx, uty).size();
221 let max = size.truncate(u128::MAX);
222 (Some((0, max, size)), 0)
226 if let Some((min, max, sz)) = range {
227 // We want to compare ranges numerically, but the order of the bitwise
228 // representation of signed integers does not match their numeric order. Thus,
229 // to correct the ordering, we need to shift the range of signed integers to
230 // correct the comparison. This is achieved by XORing with a bias (see
231 // pattern/_match.rs for another pertinent example of this pattern).
233 // Also, for performance, it's important to only do the second `try_to_bits` if
235 let lo = lo.try_to_bits(sz).unwrap() ^ bias;
237 let hi = hi.try_to_bits(sz).unwrap() ^ bias;
238 if hi > max || hi == max && end == RangeEnd::Included {
239 // Irrefutable pattern match.
247 PatKind::Slice { ref prefix, ref slice, ref suffix } => {
248 if prefix.is_empty() && slice.is_some() && suffix.is_empty() {
250 self.prefix_slice_suffix(
251 &mut candidate.match_pairs,
263 PatKind::Variant { adt_def, substs, variant_index, ref subpatterns } => {
264 let irrefutable = adt_def.variants().iter_enumerated().all(|(i, v)| {
265 i == variant_index || {
266 self.tcx.features().exhaustive_patterns
267 && v.inhabited_predicate(self.tcx, adt_def)
268 .subst(self.tcx, substs)
269 .apply_any_module(self.tcx, self.param_env)
272 }) && (adt_def.did().is_local()
273 || !adt_def.is_variant_list_non_exhaustive());
275 let place_builder = match_pair.place.downcast(adt_def, variant_index);
278 .extend(self.field_match_pairs(place_builder, subpatterns));
285 PatKind::Array { ref prefix, ref slice, ref suffix } => {
286 self.prefix_slice_suffix(
287 &mut candidate.match_pairs,
296 PatKind::Leaf { ref subpatterns } => {
297 // tuple struct, match subpats (if any)
298 candidate.match_pairs.extend(self.field_match_pairs(match_pair.place, subpatterns));
302 PatKind::Deref { ref subpattern } => {
303 let place_builder = match_pair.place.deref();
304 candidate.match_pairs.push(MatchPair::new(place_builder, subpattern, self));
308 PatKind::Or { .. } => Err(match_pair),