compiler/rustc_mir_build/src/build/matches/simplify.rs

   1 //! Simplifying Candidates
   2 //!
   3 //! *Simplifying* a match pair `place @ pattern` means breaking it down
   4 //! into bindings or other, simpler match pairs. For example:
   5 //!
   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`
   8 //!
   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.
  14
  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, *};
  20 use rustc_middle::ty;
  21 use rustc_middle::ty::layout::IntegerExt;
  22 use rustc_target::abi::{Integer, Size};
  23
  24 use std::mem;
  25
  26 impl<'a, 'tcx> Builder<'a, 'tcx> {
  27     /// Simplify a candidate so that all match pairs require a test.
  28     ///
  29     /// This method will also split a candidate, in which the only
  30     /// match-pair is an or-pattern, into multiple candidates.
  31     /// This is so that
  32     ///
  33     /// match x {
  34     ///     0 | 1 => { ... },
  35     ///     2 | 3 => { ... },
  36     /// }
  37     ///
  38     /// only generates a single switch. If this happens this method returns
  39     /// `true`.
  40     #[instrument(skip(self, candidate), level = "debug")]
  41     pub(super) fn simplify_candidate<'pat>(
  42         &mut self,
  43         candidate: &mut Candidate<'pat, 'tcx>,
  44     ) -> bool {
  45         // repeatedly simplify match pairs until fixed point is reached
  46         debug!("{candidate:#?}");
  47
  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)`
  51         //
  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
  54         // right)
  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).
  59         //
  60         // example:
  61         // candidate.bindings = [1, 2, 3]
  62         // binding in iter 1: [4, 5]
  63         // binding in iter 2: [6, 7]
  64         //
  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();
  68         loop {
  69             let match_pairs = mem::take(&mut candidate.match_pairs);
  70
  71             if let [MatchPair { pattern: Pat { kind: PatKind::Or { pats }, .. }, place }] =
  72                 &*match_pairs
  73             {
  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);
  78                 return true;
  79             }
  80
  81             let mut changed = false;
  82             for match_pair in match_pairs {
  83                 match self.simplify_match_pair(match_pair, candidate) {
  84                     Ok(()) => {
  85                         changed = true;
  86                     }
  87                     Err(match_pair) => {
  88                         candidate.match_pairs.push(match_pair);
  89                     }
  90                 }
  91             }
  92             // Avoid issue #69971: the binding order should be right to left if there are more
  93             // bindings after `@` to please the borrow checker
  94             // Ex
  95             // struct NonCopyStruct {
  96             //     copy_field: u32,
  97             // }
  98             //
  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;
 103             //     let y = x;
 104             // }
 105             candidate.bindings.extend_from_slice(&new_bindings);
 106             mem::swap(&mut candidate.bindings, &mut new_bindings);
 107             candidate.bindings.clear();
 108
 109             if !changed {
 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
 114                 // late as possible.
 115                 candidate
 116                     .match_pairs
 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.
 120             }
 121         }
 122     }
 123
 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
 126     /// `pats`.
 127     fn create_or_subcandidates<'pat>(
 128         &mut self,
 129         candidate: &Candidate<'pat, 'tcx>,
 130         place: PlaceBuilder<'tcx>,
 131         pats: &'pat [Box<Pat<'tcx>>],
 132     ) -> Vec<Candidate<'pat, 'tcx>> {
 133         pats.iter()
 134             .map(|box pat| {
 135                 let mut candidate = Candidate::new(place.clone(), pat, candidate.has_guard, self);
 136                 self.simplify_candidate(&mut candidate);
 137                 candidate
 138             })
 139             .collect()
 140     }
 141
 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
 146     /// candidate.
 147     fn simplify_match_pair<'pat>(
 148         &mut self,
 149         match_pair: MatchPair<'pat, 'tcx>,
 150         candidate: &mut Candidate<'pat, 'tcx>,
 151     ) -> Result<(), MatchPair<'pat, 'tcx>> {
 152         let tcx = self.tcx;
 153         match match_pair.pattern.kind {
 154             PatKind::AscribeUserType {
 155                 ref subpattern,
 156                 ascription: thir::Ascription { ref annotation, variance },
 157             } => {
 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),
 163                         variance,
 164                     });
 165                 }
 166
 167                 candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern, self));
 168
 169                 Ok(())
 170             }
 171
 172             PatKind::Wild => {
 173                 // nothing left to do
 174                 Ok(())
 175             }
 176
 177             PatKind::Binding {
 178                 name: _,
 179                 mutability: _,
 180                 mode,
 181                 var,
 182                 ty: _,
 183                 ref subpattern,
 184                 is_primary: _,
 185             } => {
 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),
 190                         var_id: var,
 191                         binding_mode: mode,
 192                     });
 193                 }
 194
 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));
 198                 }
 199
 200                 Ok(())
 201             }
 202
 203             PatKind::Constant { .. } => {
 204                 // FIXME normalize patterns when possible
 205                 Err(match_pair)
 206             }
 207
 208             PatKind::Range(box PatRange { lo, hi, end }) => {
 209                 let (range, bias) = match *lo.ty().kind() {
 210                     ty::Char => {
 211                         (Some(('\u{0000}' as u128, '\u{10FFFF}' as u128, Size::from_bits(32))), 0)
 212                     }
 213                     ty::Int(ity) => {
 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)
 218                     }
 219                     ty::Uint(uty) => {
 220                         let size = Integer::from_uint_ty(&tcx, uty).size();
 221                         let max = size.truncate(u128::MAX);
 222                         (Some((0, max, size)), 0)
 223                     }
 224                     _ => (None, 0),
 225                 };
 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).
 232                     //
 233                     // Also, for performance, it's important to only do the second `try_to_bits` if
 234                     // necessary.
 235                     let lo = lo.try_to_bits(sz).unwrap() ^ bias;
 236                     if lo <= min {
 237                         let hi = hi.try_to_bits(sz).unwrap() ^ bias;
 238                         if hi > max || hi == max && end == RangeEnd::Included {
 239                             // Irrefutable pattern match.
 240                             return Ok(());
 241                         }
 242                     }
 243                 }
 244                 Err(match_pair)
 245             }
 246
 247             PatKind::Slice { ref prefix, ref slice, ref suffix } => {
 248                 if prefix.is_empty() && slice.is_some() && suffix.is_empty() {
 249                     // irrefutable
 250                     self.prefix_slice_suffix(
 251                         &mut candidate.match_pairs,
 252                         &match_pair.place,
 253                         prefix,
 254                         slice,
 255                         suffix,
 256                     );
 257                     Ok(())
 258                 } else {
 259                     Err(match_pair)
 260                 }
 261             }
 262
 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
 268                                 .inhabited_predicate(self.tcx, adt_def)
 269                                 .subst(self.tcx, substs)
 270                                 .apply_ignore_module(self.tcx, self.param_env)
 271                     }
 272                 }) && (adt_def.did().is_local()
 273                     || !adt_def.is_variant_list_non_exhaustive());
 274                 if irrefutable {
 275                     let place_builder = match_pair.place.downcast(adt_def, variant_index);
 276                     candidate
 277                         .match_pairs
 278                         .extend(self.field_match_pairs(place_builder, subpatterns));
 279                     Ok(())
 280                 } else {
 281                     Err(match_pair)
 282                 }
 283             }
 284
 285             PatKind::Array { ref prefix, ref slice, ref suffix } => {
 286                 self.prefix_slice_suffix(
 287                     &mut candidate.match_pairs,
 288                     &match_pair.place,
 289                     prefix,
 290                     slice,
 291                     suffix,
 292                 );
 293                 Ok(())
 294             }
 295
 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));
 299                 Ok(())
 300             }
 301
 302             PatKind::Deref { ref subpattern } => {
 303                 let place_builder = match_pair.place.deref();
 304                 candidate.match_pairs.push(MatchPair::new(place_builder, subpattern, self));
 305                 Ok(())
 306             }
 307
 308             PatKind::Or { .. } => Err(match_pair),
 309         }
 310     }
 311 }