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_middle::thir::{self, *};
  19
  20 use std::mem;
  21
  22 impl<'a, 'tcx> Builder<'a, 'tcx> {
  23     /// Simplify a candidate so that all match pairs require a test.
  24     ///
  25     /// This method will also split a candidate, in which the only
  26     /// match-pair is an or-pattern, into multiple candidates.
  27     /// This is so that
  28     ///
  29     /// match x {
  30     ///     0 | 1 => { ... },
  31     ///     2 | 3 => { ... },
  32     /// }
  33     ///
  34     /// only generates a single switch. If this happens this method returns
  35     /// `true`.
  36     #[instrument(skip(self, candidate), level = "debug")]
  37     pub(super) fn simplify_candidate<'pat>(
  38         &mut self,
  39         candidate: &mut Candidate<'pat, 'tcx>,
  40     ) -> bool {
  41         // repeatedly simplify match pairs until fixed point is reached
  42         debug!("{candidate:#?}");
  43
  44         // existing_bindings and new_bindings exists to keep the semantics in order.
  45         // Reversing the binding order for bindings after `@` changes the binding order in places
  46         // it shouldn't be changed, for example `let (Some(a), Some(b)) = (x, y)`
  47         //
  48         // To avoid this, the binding occurs in the following manner:
  49         // * the bindings for one iteration of the following loop occurs in order (i.e. left to
  50         // right)
  51         // * the bindings from the previous iteration of the loop is prepended to the bindings from
  52         // the current iteration (in the implementation this is done by mem::swap and extend)
  53         // * after all iterations, these new bindings are then appended to the bindings that were
  54         // preexisting (i.e. `candidate.binding` when the function was called).
  55         //
  56         // example:
  57         // candidate.bindings = [1, 2, 3]
  58         // binding in iter 1: [4, 5]
  59         // binding in iter 2: [6, 7]
  60         //
  61         // final binding: [1, 2, 3, 6, 7, 4, 5]
  62         let mut existing_bindings = mem::take(&mut candidate.bindings);
  63         let mut new_bindings = Vec::new();
  64         loop {
  65             let match_pairs = mem::take(&mut candidate.match_pairs);
  66
  67             if let [MatchPair { pattern: Pat { kind: PatKind::Or { pats }, .. }, place }] =
  68                 &*match_pairs
  69             {
  70                 existing_bindings.extend_from_slice(&new_bindings);
  71                 mem::swap(&mut candidate.bindings, &mut existing_bindings);
  72                 candidate.subcandidates = self.create_or_subcandidates(candidate, &place, pats);
  73                 return true;
  74             }
  75
  76             let mut changed = false;
  77             for match_pair in match_pairs {
  78                 match self.simplify_match_pair(match_pair, candidate) {
  79                     Ok(()) => {
  80                         changed = true;
  81                     }
  82                     Err(match_pair) => {
  83                         candidate.match_pairs.push(match_pair);
  84                     }
  85                 }
  86             }
  87             // Avoid issue #69971: the binding order should be right to left if there are more
  88             // bindings after `@` to please the borrow checker
  89             // Ex
  90             // struct NonCopyStruct {
  91             //     copy_field: u32,
  92             // }
  93             //
  94             // fn foo1(x: NonCopyStruct) {
  95             //     let y @ NonCopyStruct { copy_field: z } = x;
  96             //     // the above should turn into
  97             //     let z = x.copy_field;
  98             //     let y = x;
  99             // }
 100             candidate.bindings.extend_from_slice(&new_bindings);
 101             mem::swap(&mut candidate.bindings, &mut new_bindings);
 102             candidate.bindings.clear();
 103
 104             if !changed {
 105                 existing_bindings.extend_from_slice(&new_bindings);
 106                 mem::swap(&mut candidate.bindings, &mut existing_bindings);
 107                 // Move or-patterns to the end, because they can result in us
 108                 // creating additional candidates, so we want to test them as
 109                 // late as possible.
 110                 candidate
 111                     .match_pairs
 112                     .sort_by_key(|pair| matches!(pair.pattern.kind, PatKind::Or { .. }));
 113                 debug!(simplified = ?candidate, "simplify_candidate");
 114                 return false; // if we were not able to simplify any, done.
 115             }
 116         }
 117     }
 118
 119     /// Given `candidate` that has a single or-pattern for its match-pairs,
 120     /// creates a fresh candidate for each of its input subpatterns passed via
 121     /// `pats`.
 122     fn create_or_subcandidates<'pat>(
 123         &mut self,
 124         candidate: &Candidate<'pat, 'tcx>,
 125         place: &PlaceBuilder<'tcx>,
 126         pats: &'pat [Box<Pat<'tcx>>],
 127     ) -> Vec<Candidate<'pat, 'tcx>> {
 128         pats.iter()
 129             .map(|box pat| {
 130                 let mut candidate = Candidate::new(place.clone(), pat, candidate.has_guard, self);
 131                 self.simplify_candidate(&mut candidate);
 132                 candidate
 133             })
 134             .collect()
 135     }
 136
 137     /// Tries to simplify `match_pair`, returning `Ok(())` if
 138     /// successful. If successful, new match pairs and bindings will
 139     /// have been pushed into the candidate. If no simplification is
 140     /// possible, `Err` is returned and no changes are made to
 141     /// candidate.
 142     fn simplify_match_pair<'pat>(
 143         &mut self,
 144         match_pair: MatchPair<'pat, 'tcx>,
 145         candidate: &mut Candidate<'pat, 'tcx>,
 146     ) -> Result<(), MatchPair<'pat, 'tcx>> {
 147         match match_pair.pattern.kind {
 148             PatKind::AscribeUserType {
 149                 ref subpattern,
 150                 ascription: thir::Ascription { ref annotation, variance },
 151             } => {
 152                 // Apply the type ascription to the value at `match_pair.place`, which is the
 153                 if let Some(source) = match_pair.place.try_to_place(self) {
 154                     candidate.ascriptions.push(Ascription {
 155                         annotation: annotation.clone(),
 156                         source,
 157                         variance,
 158                     });
 159                 }
 160
 161                 candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern, self));
 162
 163                 Ok(())
 164             }
 165
 166             PatKind::Wild | PatKind::Error(_) => {
 167                 // nothing left to do
 168                 Ok(())
 169             }
 170
 171             PatKind::Binding {
 172                 name: _,
 173                 mutability: _,
 174                 mode,
 175                 var,
 176                 ty: _,
 177                 ref subpattern,
 178                 is_primary: _,
 179             } => {
 180                 if let Some(source) = match_pair.place.try_to_place(self) {
 181                     candidate.bindings.push(Binding {
 182                         span: match_pair.pattern.span,
 183                         source,
 184                         var_id: var,
 185                         binding_mode: mode,
 186                     });
 187                 }
 188
 189                 if let Some(subpattern) = subpattern.as_ref() {
 190                     // this is the `x @ P` case; have to keep matching against `P` now
 191                     candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern, self));
 192                 }
 193
 194                 Ok(())
 195             }
 196
 197             PatKind::Constant { .. } => {
 198                 // FIXME normalize patterns when possible
 199                 Err(match_pair)
 200             }
 201
 202             PatKind::InlineConstant { subpattern: ref pattern, def: _ } => {
 203                 candidate.match_pairs.push(MatchPair::new(match_pair.place, pattern, self));
 204
 205                 Ok(())
 206             }
 207
 208             PatKind::Range(ref range) => {
 209                 if let Some(true) = range.is_full_range(self.tcx) {
 210                     // Irrefutable pattern match.
 211                     return Ok(());
 212                 }
 213                 Err(match_pair)
 214             }
 215
 216             PatKind::Slice { ref prefix, ref slice, ref suffix } => {
 217                 if prefix.is_empty() && slice.is_some() && suffix.is_empty() {
 218                     // irrefutable
 219                     self.prefix_slice_suffix(
 220                         &mut candidate.match_pairs,
 221                         &match_pair.place,
 222                         prefix,
 223                         slice,
 224                         suffix,
 225                     );
 226                     Ok(())
 227                 } else {
 228                     Err(match_pair)
 229                 }
 230             }
 231
 232             PatKind::Variant { adt_def, args, variant_index, ref subpatterns } => {
 233                 let irrefutable = adt_def.variants().iter_enumerated().all(|(i, v)| {
 234                     i == variant_index || {
 235                         self.tcx.features().exhaustive_patterns
 236                             && !v
 237                                 .inhabited_predicate(self.tcx, adt_def)
 238                                 .instantiate(self.tcx, args)
 239                                 .apply_ignore_module(self.tcx, self.param_env)
 240                     }
 241                 }) && (adt_def.did().is_local()
 242                     || !adt_def.is_variant_list_non_exhaustive());
 243                 if irrefutable {
 244                     let place_builder = match_pair.place.downcast(adt_def, variant_index);
 245                     candidate
 246                         .match_pairs
 247                         .extend(self.field_match_pairs(place_builder, subpatterns));
 248                     Ok(())
 249                 } else {
 250                     Err(match_pair)
 251                 }
 252             }
 253
 254             PatKind::Array { ref prefix, ref slice, ref suffix } => {
 255                 self.prefix_slice_suffix(
 256                     &mut candidate.match_pairs,
 257                     &match_pair.place,
 258                     prefix,
 259                     slice,
 260                     suffix,
 261                 );
 262                 Ok(())
 263             }
 264
 265             PatKind::Leaf { ref subpatterns } => {
 266                 // tuple struct, match subpats (if any)
 267                 candidate.match_pairs.extend(self.field_match_pairs(match_pair.place, subpatterns));
 268                 Ok(())
 269             }
 270
 271             PatKind::Deref { ref subpattern } => {
 272                 let place_builder = match_pair.place.deref();
 273                 candidate.match_pairs.push(MatchPair::new(place_builder, subpattern, self));
 274                 Ok(())
 275             }
 276
 277             PatKind::Or { .. } => Err(match_pair),
 278         }
 279     }
 280 }