src/librustc_mir/build/matches/simplify.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Simplifying Candidates
  12 //!
  13 //! *Simplifying* a match pair `place @ pattern` means breaking it down
  14 //! into bindings or other, simpler match pairs. For example:
  15 //!
  16 //! - `place @ (P1, P2)` can be simplified to `[place.0 @ P1, place.1 @ P2]`
  17 //! - `place @ x` can be simplified to `[]` by binding `x` to `place`
  18 //!
  19 //! The `simplify_candidate` routine just repeatedly applies these
  20 //! sort of simplifications until there is nothing left to
  21 //! simplify. Match pairs cannot be simplified if they require some
  22 //! sort of test: for example, testing which variant an enum is, or
  23 //! testing a value against a constant.
  24
  25 use build::{BlockAnd, BlockAndExtension, Builder};
  26 use build::matches::{Ascription, Binding, MatchPair, Candidate};
  27 use hair::*;
  28 use rustc::mir::*;
  29 use rustc::ty;
  30 use rustc::ty::layout::{Integer, IntegerExt, Size};
  31 use syntax::attr::{SignedInt, UnsignedInt};
  32 use rustc::hir::RangeEnd;
  33
  34 use std::mem;
  35
  36 impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> {
  37     pub fn simplify_candidate<'pat>(&mut self,
  38                                     block: BasicBlock,
  39                                     candidate: &mut Candidate<'pat, 'tcx>)
  40                                     -> BlockAnd<()> {
  41         // repeatedly simplify match pairs until fixed point is reached
  42         loop {
  43             let match_pairs = mem::replace(&mut candidate.match_pairs, vec![]);
  44             let mut progress = match_pairs.len(); // count how many were simplified
  45             for match_pair in match_pairs {
  46                 match self.simplify_match_pair(match_pair, candidate) {
  47                     Ok(()) => {}
  48                     Err(match_pair) => {
  49                         candidate.match_pairs.push(match_pair);
  50                         progress -= 1; // this one was not simplified
  51                     }
  52                 }
  53             }
  54             if progress == 0 {
  55                 return block.unit(); // if we were not able to simplify any, done.
  56             }
  57         }
  58     }
  59
  60     /// Tries to simplify `match_pair`, returning true if
  61     /// successful. If successful, new match pairs and bindings will
  62     /// have been pushed into the candidate. If no simplification is
  63     /// possible, Err is returned and no changes are made to
  64     /// candidate.
  65     fn simplify_match_pair<'pat>(&mut self,
  66                                  match_pair: MatchPair<'pat, 'tcx>,
  67                                  candidate: &mut Candidate<'pat, 'tcx>)
  68                                  -> Result<(), MatchPair<'pat, 'tcx>> {
  69         let tcx = self.hir.tcx();
  70         match *match_pair.pattern.kind {
  71             PatternKind::AscribeUserType { ref subpattern, ref user_ty, user_ty_span } => {
  72                 candidate.ascriptions.push(Ascription {
  73                     span: user_ty_span,
  74                     user_ty: user_ty.clone(),
  75                     source: match_pair.place.clone(),
  76                 });
  77
  78                 candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern));
  79
  80                 Ok(())
  81             }
  82
  83             PatternKind::Wild => {
  84                 // nothing left to do
  85                 Ok(())
  86             }
  87
  88             PatternKind::Binding { name, mutability, mode, var, ty, ref subpattern } => {
  89                 candidate.bindings.push(Binding {
  90                     name,
  91                     mutability,
  92                     span: match_pair.pattern.span,
  93                     source: match_pair.place.clone(),
  94                     var_id: var,
  95                     var_ty: ty,
  96                     binding_mode: mode,
  97                 });
  98
  99                 if let Some(subpattern) = subpattern.as_ref() {
 100                     // this is the `x @ P` case; have to keep matching against `P` now
 101                     candidate.match_pairs.push(MatchPair::new(match_pair.place, subpattern));
 102                 }
 103
 104                 Ok(())
 105             }
 106
 107             PatternKind::Constant { .. } => {
 108                 // FIXME normalize patterns when possible
 109                 Err(match_pair)
 110             }
 111
 112             PatternKind::Range { lo, hi, ty, end } => {
 113                 let range = match ty.sty {
 114                     ty::Char => {
 115                         Some(('\u{0000}' as u128, '\u{10FFFF}' as u128, Size::from_bits(32)))
 116                     }
 117                     ty::Int(ity) => {
 118                         // FIXME(49937): refactor these bit manipulations into interpret.
 119                         let size = Integer::from_attr(&tcx, SignedInt(ity)).size();
 120                         let min = 1u128 << (size.bits() - 1);
 121                         let max = (1u128 << (size.bits() - 1)) - 1;
 122                         Some((min, max, size))
 123                     }
 124                     ty::Uint(uty) => {
 125                         // FIXME(49937): refactor these bit manipulations into interpret.
 126                         let size = Integer::from_attr(&tcx, UnsignedInt(uty)).size();
 127                         let max = !0u128 >> (128 - size.bits());
 128                         Some((0, max, size))
 129                     }
 130                     _ => None,
 131                 };
 132                 if let Some((min, max, sz)) = range {
 133                     if let (Some(lo), Some(hi)) = (lo.val.try_to_bits(sz), hi.val.try_to_bits(sz)) {
 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             PatternKind::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(&mut candidate.match_pairs,
 147                                              &match_pair.place,
 148                                              prefix,
 149                                              slice.as_ref(),
 150                                              suffix);
 151                     Ok(())
 152                 } else {
 153                     Err(match_pair)
 154                 }
 155             }
 156
 157             PatternKind::Variant { adt_def, substs, variant_index, ref subpatterns } => {
 158                 let irrefutable = adt_def.variants.iter_enumerated().all(|(i, v)| {
 159                     i == variant_index || {
 160                         self.hir.tcx().features().never_type &&
 161                         self.hir.tcx().features().exhaustive_patterns &&
 162                         self.hir.tcx().is_variant_uninhabited_from_all_modules(v, substs)
 163                     }
 164                 });
 165                 if irrefutable {
 166                     let place = match_pair.place.downcast(adt_def, variant_index);
 167                     candidate.match_pairs.extend(self.field_match_pairs(place, subpatterns));
 168                     Ok(())
 169                 } else {
 170                     Err(match_pair)
 171                 }
 172             },
 173
 174             PatternKind::Array { ref prefix, ref slice, ref suffix } => {
 175                 self.prefix_slice_suffix(&mut candidate.match_pairs,
 176                                          &match_pair.place,
 177                                          prefix,
 178                                          slice.as_ref(),
 179                                          suffix);
 180                 Ok(())
 181             }
 182
 183             PatternKind::Leaf { ref subpatterns } => {
 184                 // tuple struct, match subpats (if any)
 185                 candidate.match_pairs
 186                          .extend(self.field_match_pairs(match_pair.place, subpatterns));
 187                 Ok(())
 188             }
 189
 190             PatternKind::Deref { ref subpattern } => {
 191                 let place = match_pair.place.deref();
 192                 candidate.match_pairs.push(MatchPair::new(place, subpattern));
 193                 Ok(())
 194             }
 195         }
 196     }
 197 }