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::matches::{Ascription, Binding, Candidate, MatchPair};
  16 use crate::build::Builder;
  17 use crate::thir::{self, *};
  18 use rustc_hir::RangeEnd;
  19 use rustc_middle::mir::Place;
  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     pub(super) fn simplify_candidate<'pat>(
  41         &mut self,
  42         candidate: &mut Candidate<'pat, 'tcx>,
  43     ) -> bool {
  44         // repeatedly simplify match pairs until fixed point is reached
  45         debug!(?candidate, "simplify_candidate");
  46
  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)`
  50         //
  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
  53         // right)
  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).
  58         //
  59         // example:
  60         // candidate.bindings = [1, 2, 3]
  61         // binding in iter 1: [4, 5]
  62         // binding in iter 2: [6, 7]
  63         //
  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();
  67         loop {
  68             let match_pairs = mem::take(&mut candidate.match_pairs);
  69
  70             if let [MatchPair { pattern: Pat { kind: box PatKind::Or { pats }, .. }, place }] =
  71                 *match_pairs
  72             {
  73                 existing_bindings.extend_from_slice(&new_bindings);
  74                 mem::swap(&mut candidate.bindings, &mut existing_bindings);
  75                 candidate.subcandidates = self.create_or_subcandidates(candidate, place, pats);
  76                 return true;
  77             }
  78
  79             let mut changed = false;
  80             for match_pair in match_pairs {
  81                 match self.simplify_match_pair(match_pair, candidate) {
  82                     Ok(()) => {
  83                         changed = true;
  84                     }
  85                     Err(match_pair) => {
  86                         candidate.match_pairs.push(match_pair);
  87                     }
  88                 }
  89             }
  90             // Avoid issue #69971: the binding order should be right to left if there are more
  91             // bindings after `@` to please the borrow checker
  92             // Ex
  93             // struct NonCopyStruct {
  94             //     copy_field: u32,
  95             // }
  96             //
  97             // fn foo1(x: NonCopyStruct) {
  98             //     let y @ NonCopyStruct { copy_field: z } = x;
  99             //     // the above should turn into
 100             //     let z = x.copy_field;
 101             //     let y = x;
 102             // }
 103             candidate.bindings.extend_from_slice(&new_bindings);
 104             mem::swap(&mut candidate.bindings, &mut new_bindings);
 105             candidate.bindings.clear();
 106
 107             if !changed {
 108                 existing_bindings.extend_from_slice(&new_bindings);
 109                 mem::swap(&mut candidate.bindings, &mut existing_bindings);
 110                 // Move or-patterns to the end, because they can result in us
 111                 // creating additional candidates, so we want to test them as
 112                 // late as possible.
 113                 candidate
 114                     .match_pairs
 115                     .sort_by_key(|pair| matches!(*pair.pattern.kind, PatKind::Or { .. }));
 116                 debug!(simplified = ?candidate, "simplify_candidate");
 117                 return false; // if we were not able to simplify any, done.
 118             }
 119         }
 120     }
 121
 122     /// Given `candidate` that has a single or-pattern for its match-pairs,
 123     /// creates a fresh candidate for each of its input subpatterns passed via
 124     /// `pats`.
 125     fn create_or_subcandidates<'pat>(
 126         &mut self,
 127         candidate: &Candidate<'pat, 'tcx>,
 128         place: Place<'tcx>,
 129         pats: &'pat [Pat<'tcx>],
 130     ) -> Vec<Candidate<'pat, 'tcx>> {
 131         pats.iter()
 132             .map(|pat| {
 133                 let mut candidate = Candidate::new(place, pat, candidate.has_guard);
 134                 self.simplify_candidate(&mut candidate);
 135                 candidate
 136             })
 137             .collect()
 138     }
 139
 140     /// Tries to simplify `match_pair`, returning `Ok(())` if
 141     /// successful. If successful, new match pairs and bindings will
 142     /// have been pushed into the candidate. If no simplification is
 143     /// possible, `Err` is returned and no changes are made to
 144     /// candidate.
 145     fn simplify_match_pair<'pat>(
 146         &mut self,
 147         match_pair: MatchPair<'pat, 'tcx>,
 148         candidate: &mut Candidate<'pat, 'tcx>,
 149     ) -> Result<(), MatchPair<'pat, 'tcx>> {
 150         let tcx = self.tcx;
 151         match *match_pair.pattern.kind {
 152             PatKind::AscribeUserType {
 153                 ref subpattern,
 154                 ascription: thir::pattern::Ascription { variance, user_ty, user_ty_span },
 155             } => {
 156                 // Apply the type ascription to the value at `match_pair.place`, which is the
 157                 // value being matched, taking the variance field into account.
 158                 candidate.ascriptions.push(Ascription {
 159                     span: user_ty_span,
 160                     user_ty,
 161                     source: match_pair.place,
 162                     variance,
 163                 });
 164
 165                 candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern));
 166
 167                 Ok(())
 168             }
 169
 170             PatKind::Wild => {
 171                 // nothing left to do
 172                 Ok(())
 173             }
 174
 175             PatKind::Binding { name, mutability, mode, var, ty, ref subpattern, is_primary: _ } => {
 176                 candidate.bindings.push(Binding {
 177                     name,
 178                     mutability,
 179                     span: match_pair.pattern.span,
 180                     source: match_pair.place,
 181                     var_id: var,
 182                     var_ty: ty,
 183                     binding_mode: mode,
 184                 });
 185
 186                 if let Some(subpattern) = subpattern.as_ref() {
 187                     // this is the `x @ P` case; have to keep matching against `P` now
 188                     candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern));
 189                 }
 190
 191                 Ok(())
 192             }
 193
 194             PatKind::Constant { .. } => {
 195                 // FIXME normalize patterns when possible
 196                 Err(match_pair)
 197             }
 198
 199             PatKind::Range(PatRange { lo, hi, end }) => {
 200                 let (range, bias) = match *lo.ty.kind() {
 201                     ty::Char => {
 202                         (Some(('\u{0000}' as u128, '\u{10FFFF}' as u128, Size::from_bits(32))), 0)
 203                     }
 204                     ty::Int(ity) => {
 205                         let size = Integer::from_int_ty(&tcx, ity).size();
 206                         let max = size.truncate(u128::MAX);
 207                         let bias = 1u128 << (size.bits() - 1);
 208                         (Some((0, max, size)), bias)
 209                     }
 210                     ty::Uint(uty) => {
 211                         let size = Integer::from_uint_ty(&tcx, uty).size();
 212                         let max = size.truncate(u128::MAX);
 213                         (Some((0, max, size)), 0)
 214                     }
 215                     _ => (None, 0),
 216                 };
 217                 if let Some((min, max, sz)) = range {
 218                     if let (Some(lo), Some(hi)) = (lo.val.try_to_bits(sz), hi.val.try_to_bits(sz)) {
 219                         // We want to compare ranges numerically, but the order of the bitwise
 220                         // representation of signed integers does not match their numeric order.
 221                         // Thus, to correct the ordering, we need to shift the range of signed
 222                         // integers to correct the comparison. This is achieved by XORing with a
 223                         // bias (see pattern/_match.rs for another pertinent example of this
 224                         // pattern).
 225                         let (lo, hi) = (lo ^ bias, hi ^ bias);
 226                         if lo <= min && (hi > max || hi == max && end == RangeEnd::Included) {
 227                             // Irrefutable pattern match.
 228                             return Ok(());
 229                         }
 230                     }
 231                 }
 232                 Err(match_pair)
 233             }
 234
 235             PatKind::Slice { ref prefix, ref slice, ref suffix } => {
 236                 if prefix.is_empty() && slice.is_some() && suffix.is_empty() {
 237                     // irrefutable
 238                     self.prefix_slice_suffix(
 239                         &mut candidate.match_pairs,
 240                         &match_pair.place,
 241                         prefix,
 242                         slice.as_ref(),
 243                         suffix,
 244                     );
 245                     Ok(())
 246                 } else {
 247                     Err(match_pair)
 248                 }
 249             }
 250
 251             PatKind::Variant { adt_def, substs, variant_index, ref subpatterns } => {
 252                 let irrefutable = adt_def.variants.iter_enumerated().all(|(i, v)| {
 253                     i == variant_index || {
 254                         self.tcx.features().exhaustive_patterns
 255                             && !v
 256                                 .uninhabited_from(
 257                                     self.tcx,
 258                                     substs,
 259                                     adt_def.adt_kind(),
 260                                     self.param_env,
 261                                 )
 262                                 .is_empty()
 263                     }
 264                 }) && (adt_def.did.is_local()
 265                     || !adt_def.is_variant_list_non_exhaustive());
 266                 if irrefutable {
 267                     let place = tcx.mk_place_downcast(match_pair.place, adt_def, variant_index);
 268                     candidate.match_pairs.extend(self.field_match_pairs(place, subpatterns));
 269                     Ok(())
 270                 } else {
 271                     Err(match_pair)
 272                 }
 273             }
 274
 275             PatKind::Array { ref prefix, ref slice, ref suffix } => {
 276                 self.prefix_slice_suffix(
 277                     &mut candidate.match_pairs,
 278                     &match_pair.place,
 279                     prefix,
 280                     slice.as_ref(),
 281                     suffix,
 282                 );
 283                 Ok(())
 284             }
 285
 286             PatKind::Leaf { ref subpatterns } => {
 287                 // tuple struct, match subpats (if any)
 288                 candidate.match_pairs.extend(self.field_match_pairs(match_pair.place, subpatterns));
 289                 Ok(())
 290             }
 291
 292             PatKind::Deref { ref subpattern } => {
 293                 let place = tcx.mk_place_deref(match_pair.place);
 294                 candidate.match_pairs.push(MatchPair::new(place, subpattern));
 295                 Ok(())
 296             }
 297
 298             PatKind::Or { .. } => Err(match_pair),
 299         }
 300     }
 301 }