src/librustc_mir_build/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::hair::{self, *};
  18 use rustc::mir::interpret::truncate;
  19 use rustc::ty;
  20 use rustc::ty::layout::{Integer, IntegerExt, Size};
  21 use rustc_hir::RangeEnd;
  22 use syntax::attr::{SignedInt, UnsignedInt};
  23
  24 use std::mem;
  25
  26 impl<'a, 'tcx> Builder<'a, 'tcx> {
  27     crate fn simplify_candidate<'pat>(&mut self, candidate: &mut Candidate<'pat, 'tcx>) {
  28         // repeatedly simplify match pairs until fixed point is reached
  29         loop {
  30             let match_pairs = mem::take(&mut candidate.match_pairs);
  31             let mut changed = false;
  32             for match_pair in match_pairs {
  33                 match self.simplify_match_pair(match_pair, candidate) {
  34                     Ok(()) => {
  35                         changed = true;
  36                     }
  37                     Err(match_pair) => {
  38                         candidate.match_pairs.push(match_pair);
  39                     }
  40                 }
  41             }
  42             if !changed {
  43                 return; // if we were not able to simplify any, done.
  44             }
  45         }
  46     }
  47
  48     /// Tries to simplify `match_pair`, returning `Ok(())` if
  49     /// successful. If successful, new match pairs and bindings will
  50     /// have been pushed into the candidate. If no simplification is
  51     /// possible, `Err` is returned and no changes are made to
  52     /// candidate.
  53     fn simplify_match_pair<'pat>(
  54         &mut self,
  55         match_pair: MatchPair<'pat, 'tcx>,
  56         candidate: &mut Candidate<'pat, 'tcx>,
  57     ) -> Result<(), MatchPair<'pat, 'tcx>> {
  58         let tcx = self.hir.tcx();
  59         match *match_pair.pattern.kind {
  60             PatKind::AscribeUserType {
  61                 ref subpattern,
  62                 ascription: hair::pattern::Ascription { variance, ref user_ty, user_ty_span },
  63             } => {
  64                 // Apply the type ascription to the value at `match_pair.place`, which is the
  65                 // value being matched, taking the variance field into account.
  66                 candidate.ascriptions.push(Ascription {
  67                     span: user_ty_span,
  68                     user_ty: user_ty.clone(),
  69                     source: match_pair.place.clone(),
  70                     variance,
  71                 });
  72
  73                 candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern));
  74
  75                 Ok(())
  76             }
  77
  78             PatKind::Wild => {
  79                 // nothing left to do
  80                 Ok(())
  81             }
  82
  83             PatKind::Binding { name, mutability, mode, var, ty, ref subpattern } => {
  84                 candidate.bindings.push(Binding {
  85                     name,
  86                     mutability,
  87                     span: match_pair.pattern.span,
  88                     source: match_pair.place.clone(),
  89                     var_id: var,
  90                     var_ty: ty,
  91                     binding_mode: mode,
  92                 });
  93
  94                 if let Some(subpattern) = subpattern.as_ref() {
  95                     // this is the `x @ P` case; have to keep matching against `P` now
  96                     candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern));
  97                 }
  98
  99                 Ok(())
 100             }
 101
 102             PatKind::Constant { .. } => {
 103                 // FIXME normalize patterns when possible
 104                 Err(match_pair)
 105             }
 106
 107             PatKind::Range(PatRange { lo, hi, end }) => {
 108                 let (range, bias) = match lo.ty.kind {
 109                     ty::Char => {
 110                         (Some(('\u{0000}' as u128, '\u{10FFFF}' as u128, Size::from_bits(32))), 0)
 111                     }
 112                     ty::Int(ity) => {
 113                         let size = Integer::from_attr(&tcx, SignedInt(ity)).size();
 114                         let max = truncate(u128::max_value(), size);
 115                         let bias = 1u128 << (size.bits() - 1);
 116                         (Some((0, max, size)), bias)
 117                     }
 118                     ty::Uint(uty) => {
 119                         let size = Integer::from_attr(&tcx, UnsignedInt(uty)).size();
 120                         let max = truncate(u128::max_value(), size);
 121                         (Some((0, max, size)), 0)
 122                     }
 123                     _ => (None, 0),
 124                 };
 125                 if let Some((min, max, sz)) = range {
 126                     if let (Some(lo), Some(hi)) = (lo.val.try_to_bits(sz), hi.val.try_to_bits(sz)) {
 127                         // We want to compare ranges numerically, but the order of the bitwise
 128                         // representation of signed integers does not match their numeric order.
 129                         // Thus, to correct the ordering, we need to shift the range of signed
 130                         // integers to correct the comparison. This is achieved by XORing with a
 131                         // bias (see pattern/_match.rs for another pertinent example of this
 132                         // pattern).
 133                         let (lo, hi) = (lo ^ bias, hi ^ bias);
 134                         if lo <= min && (hi > max || hi == max && end == RangeEnd::Included) {
 135                             // Irrefutable pattern match.
 136                             return Ok(());
 137                         }
 138                     }
 139                 }
 140                 Err(match_pair)
 141             }
 142
 143             PatKind::Slice { ref prefix, ref slice, ref suffix } => {
 144                 if prefix.is_empty() && slice.is_some() && suffix.is_empty() {
 145                     // irrefutable
 146                     self.prefix_slice_suffix(
 147                         &mut candidate.match_pairs,
 148                         &match_pair.place,
 149                         prefix,
 150                         slice.as_ref(),
 151                         suffix,
 152                     );
 153                     Ok(())
 154                 } else {
 155                     Err(match_pair)
 156                 }
 157             }
 158
 159             PatKind::Variant { adt_def, substs, variant_index, ref subpatterns } => {
 160                 let irrefutable = adt_def.variants.iter_enumerated().all(|(i, v)| {
 161                     i == variant_index || {
 162                         self.hir.tcx().features().exhaustive_patterns
 163                             && !v
 164                                 .uninhabited_from(self.hir.tcx(), substs, adt_def.adt_kind())
 165                                 .is_empty()
 166                     }
 167                 }) && (adt_def.did.is_local()
 168                     || !adt_def.is_variant_list_non_exhaustive());
 169                 if irrefutable {
 170                     let place = tcx.mk_place_downcast(match_pair.place, adt_def, variant_index);
 171                     candidate.match_pairs.extend(self.field_match_pairs(place, subpatterns));
 172                     Ok(())
 173                 } else {
 174                     Err(match_pair)
 175                 }
 176             }
 177
 178             PatKind::Array { ref prefix, ref slice, ref suffix } => {
 179                 self.prefix_slice_suffix(
 180                     &mut candidate.match_pairs,
 181                     &match_pair.place,
 182                     prefix,
 183                     slice.as_ref(),
 184                     suffix,
 185                 );
 186                 Ok(())
 187             }
 188
 189             PatKind::Leaf { ref subpatterns } => {
 190                 // tuple struct, match subpats (if any)
 191                 candidate.match_pairs.extend(self.field_match_pairs(match_pair.place, subpatterns));
 192                 Ok(())
 193             }
 194
 195             PatKind::Deref { ref subpattern } => {
 196                 let place = tcx.mk_place_deref(match_pair.place);
 197                 candidate.match_pairs.push(MatchPair::new(place, subpattern));
 198                 Ok(())
 199             }
 200
 201             PatKind::Or { .. } => Err(match_pair),
 202         }
 203     }
 204 }