src/librustc_mir/build/matches/mod.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 //! Code related to match expresions. These are sufficiently complex
  12 //! to warrant their own module and submodules. :) This main module
  13 //! includes the high-level algorithm, the submodules contain the
  14 //! details.
  15
  16 use build::{BlockAnd, BlockAndExtension, Builder};
  17 use rustc_data_structures::fnv::FnvHashMap;
  18 use rustc::middle::const_eval::ConstVal;
  19 use rustc::middle::region::CodeExtent;
  20 use rustc::middle::ty::{AdtDef, Ty};
  21 use rustc::mir::repr::*;
  22 use hair::*;
  23 use syntax::ast::{Name, NodeId};
  24 use syntax::codemap::Span;
  25
  26 // helper functions, broken out by category:
  27 mod simplify;
  28 mod test;
  29 mod util;
  30
  31 impl<'a,'tcx> Builder<'a,'tcx> {
  32     pub fn match_expr(&mut self,
  33                       destination: &Lvalue<'tcx>,
  34                       span: Span,
  35                       mut block: BasicBlock,
  36                       discriminant: ExprRef<'tcx>,
  37                       arms: Vec<Arm<'tcx>>)
  38                       -> BlockAnd<()> {
  39         let discriminant_lvalue = unpack!(block = self.as_lvalue(block, discriminant));
  40
  41         // Before we do anything, create uninitialized variables with
  42         // suitable extent for all of the bindings in this match. It's
  43         // easiest to do this up front because some of these arms may
  44         // be unreachable or reachable multiple times.
  45         let var_extent = self.extent_of_innermost_scope();
  46         for arm in &arms {
  47             self.declare_bindings(var_extent, &arm.patterns[0]);
  48         }
  49
  50         let mut arm_blocks = ArmBlocks {
  51             blocks: arms.iter()
  52                         .map(|_| self.cfg.start_new_block())
  53                         .collect(),
  54         };
  55
  56         let arm_bodies: Vec<ExprRef<'tcx>> =
  57             arms.iter()
  58                 .map(|arm| arm.body.clone())
  59                 .collect();
  60
  61         // assemble a list of candidates: there is one candidate per
  62         // pattern, which means there may be more than one candidate
  63         // *per arm*. These candidates are kept sorted such that the
  64         // highest priority candidate comes last in the list. This the
  65         // reverse of the order in which candidates are written in the
  66         // source.
  67         let candidates: Vec<_> =
  68             arms.iter()
  69                 .enumerate()
  70                 .rev() // highest priority comes last
  71                 .flat_map(|(arm_index, arm)| {
  72                     arm.patterns.iter()
  73                                 .rev()
  74                                 .map(move |pat| (arm_index, pat, arm.guard.clone()))
  75                 })
  76                 .map(|(arm_index, pattern, guard)| {
  77                     Candidate {
  78                         match_pairs: vec![MatchPair::new(discriminant_lvalue.clone(), pattern)],
  79                         bindings: vec![],
  80                         guard: guard,
  81                         arm_index: arm_index,
  82                     }
  83                 })
  84                 .collect();
  85
  86         // this will generate code to test discriminant_lvalue and
  87         // branch to the appropriate arm block
  88         let otherwise = self.match_candidates(span, &mut arm_blocks, candidates, block);
  89
  90         // because all matches are exhaustive, in principle we expect
  91         // an empty vector to be returned here, but the algorithm is
  92         // not entirely precise
  93         if !otherwise.is_empty() {
  94             let join_block = self.join_otherwise_blocks(otherwise);
  95             self.panic(join_block);
  96         }
  97
  98         // all the arm blocks will rejoin here
  99         let end_block = self.cfg.start_new_block();
 100
 101         for (arm_index, arm_body) in arm_bodies.into_iter().enumerate() {
 102             let mut arm_block = arm_blocks.blocks[arm_index];
 103             unpack!(arm_block = self.into(destination, arm_block, arm_body));
 104             self.cfg.terminate(arm_block, Terminator::Goto { target: end_block });
 105         }
 106
 107         end_block.unit()
 108     }
 109
 110     pub fn expr_into_pattern(&mut self,
 111                              mut block: BasicBlock,
 112                              var_extent: CodeExtent, // lifetime of vars
 113                              irrefutable_pat: Pattern<'tcx>,
 114                              initializer: ExprRef<'tcx>)
 115                              -> BlockAnd<()> {
 116         // optimize the case of `let x = ...`
 117         match *irrefutable_pat.kind {
 118             PatternKind::Binding { mutability,
 119                                    name,
 120                                    mode: BindingMode::ByValue,
 121                                    var,
 122                                    ty,
 123                                    subpattern: None } => {
 124                 let index = self.declare_binding(var_extent,
 125                                                  mutability,
 126                                                  name,
 127                                                  var,
 128                                                  ty,
 129                                                  irrefutable_pat.span);
 130                 let lvalue = Lvalue::Var(index);
 131                 return self.into(&lvalue, block, initializer);
 132             }
 133             _ => {}
 134         }
 135         let lvalue = unpack!(block = self.as_lvalue(block, initializer));
 136         self.lvalue_into_pattern(block,
 137                                  var_extent,
 138                                  irrefutable_pat,
 139                                  &lvalue)
 140     }
 141
 142     pub fn lvalue_into_pattern(&mut self,
 143                                mut block: BasicBlock,
 144                                var_extent: CodeExtent,
 145                                irrefutable_pat: Pattern<'tcx>,
 146                                initializer: &Lvalue<'tcx>)
 147                                -> BlockAnd<()> {
 148         // first, creating the bindings
 149         self.declare_bindings(var_extent, &irrefutable_pat);
 150
 151         // create a dummy candidate
 152         let mut candidate = Candidate {
 153             match_pairs: vec![MatchPair::new(initializer.clone(), &irrefutable_pat)],
 154             bindings: vec![],
 155             guard: None,
 156             arm_index: 0, // since we don't call `match_candidates`, this field is unused
 157         };
 158
 159         // Simplify the candidate. Since the pattern is irrefutable, this should
 160         // always convert all match-pairs into bindings.
 161         unpack!(block = self.simplify_candidate(block, &mut candidate));
 162
 163         if !candidate.match_pairs.is_empty() {
 164             self.hir.span_bug(candidate.match_pairs[0].pattern.span,
 165                               &format!("match pairs {:?} remaining after simplifying \
 166                                         irrefutable pattern",
 167                                        candidate.match_pairs));
 168         }
 169
 170         // now apply the bindings, which will also declare the variables
 171         self.bind_matched_candidate(block, candidate.bindings);
 172
 173         block.unit()
 174     }
 175
 176     pub fn declare_bindings(&mut self, var_extent: CodeExtent, pattern: &Pattern<'tcx>) {
 177         match *pattern.kind {
 178             PatternKind::Binding { mutability, name, mode: _, var, ty, ref subpattern } => {
 179                 self.declare_binding(var_extent, mutability, name, var, ty, pattern.span);
 180                 if let Some(subpattern) = subpattern.as_ref() {
 181                     self.declare_bindings(var_extent, subpattern);
 182                 }
 183             }
 184             PatternKind::Array { ref prefix, ref slice, ref suffix } |
 185             PatternKind::Slice { ref prefix, ref slice, ref suffix } => {
 186                 for subpattern in prefix.iter().chain(slice).chain(suffix) {
 187                     self.declare_bindings(var_extent, subpattern);
 188                 }
 189             }
 190             PatternKind::Constant { .. } | PatternKind::Range { .. } | PatternKind::Wild => {
 191             }
 192             PatternKind::Deref { ref subpattern } => {
 193                 self.declare_bindings(var_extent, subpattern);
 194             }
 195             PatternKind::Leaf { ref subpatterns } |
 196             PatternKind::Variant { ref subpatterns, .. } => {
 197                 for subpattern in subpatterns {
 198                     self.declare_bindings(var_extent, &subpattern.pattern);
 199                 }
 200             }
 201         }
 202     }
 203 }
 204
 205 /// List of blocks for each arm (and potentially other metadata in the
 206 /// future).
 207 struct ArmBlocks {
 208     blocks: Vec<BasicBlock>,
 209 }
 210
 211 #[derive(Clone, Debug)]
 212 pub struct Candidate<'pat, 'tcx:'pat> {
 213     // all of these must be satisfied...
 214     match_pairs: Vec<MatchPair<'pat, 'tcx>>,
 215
 216     // ...these bindings established...
 217     bindings: Vec<Binding<'tcx>>,
 218
 219     // ...and the guard must be evaluated...
 220     guard: Option<ExprRef<'tcx>>,
 221
 222     // ...and then we branch to arm with this index.
 223     arm_index: usize,
 224 }
 225
 226 #[derive(Clone, Debug)]
 227 struct Binding<'tcx> {
 228     span: Span,
 229     source: Lvalue<'tcx>,
 230     name: Name,
 231     var_id: NodeId,
 232     var_ty: Ty<'tcx>,
 233     mutability: Mutability,
 234     binding_mode: BindingMode,
 235 }
 236
 237 #[derive(Clone, Debug)]
 238 pub struct MatchPair<'pat, 'tcx:'pat> {
 239     // this lvalue...
 240     lvalue: Lvalue<'tcx>,
 241
 242     // ... must match this pattern.
 243     pattern: &'pat Pattern<'tcx>,
 244 }
 245
 246 #[derive(Clone, Debug, PartialEq)]
 247 enum TestKind<'tcx> {
 248     // test the branches of enum
 249     Switch {
 250         adt_def: AdtDef<'tcx>,
 251     },
 252
 253     // test the branches of enum
 254     SwitchInt {
 255         switch_ty: Ty<'tcx>,
 256         options: Vec<ConstVal>,
 257         indices: FnvHashMap<ConstVal, usize>,
 258     },
 259
 260     // test for equality
 261     Eq {
 262         value: Literal<'tcx>,
 263         ty: Ty<'tcx>,
 264     },
 265
 266     // test whether the value falls within an inclusive range
 267     Range {
 268         lo: Literal<'tcx>,
 269         hi: Literal<'tcx>,
 270         ty: Ty<'tcx>,
 271     },
 272
 273     // test length of the slice is equal to len
 274     Len {
 275         len: usize,
 276         op: BinOp,
 277     },
 278 }
 279
 280 #[derive(Debug)]
 281 pub struct Test<'tcx> {
 282     span: Span,
 283     kind: TestKind<'tcx>,
 284 }
 285
 286 ///////////////////////////////////////////////////////////////////////////
 287 // Main matching algorithm
 288
 289 impl<'a,'tcx> Builder<'a,'tcx> {
 290     /// The main match algorithm. It begins with a set of candidates
 291     /// `candidates` and has the job of generating code to determine
 292     /// which of these candidates, if any, is the correct one. The
 293     /// candidates are sorted in inverse priority -- so the last item
 294     /// in the list has highest priority. When a candidate is found to
 295     /// match the value, we will generate a branch to the appropriate
 296     /// block found in `arm_blocks`.
 297     ///
 298     /// The return value is a list of "otherwise" blocks. These are
 299     /// points in execution where we found that *NONE* of the
 300     /// candidates apply.  In principle, this means that the input
 301     /// list was not exhaustive, though at present we sometimes are
 302     /// not smart enough to recognize all exhaustive inputs.
 303     ///
 304     /// It might be surprising that the input can be inexhaustive.
 305     /// Indeed, initially, it is not, because all matches are
 306     /// exhaustive in Rust. But during processing we sometimes divide
 307     /// up the list of candidates and recurse with a non-exhaustive
 308     /// list. This is important to keep the size of the generated code
 309     /// under control. See `test_candidates` for more details.
 310     fn match_candidates<'pat>(&mut self,
 311                               span: Span,
 312                               arm_blocks: &mut ArmBlocks,
 313                               mut candidates: Vec<Candidate<'pat, 'tcx>>,
 314                               mut block: BasicBlock)
 315                               -> Vec<BasicBlock>
 316     {
 317         debug!("matched_candidate(span={:?}, block={:?}, candidates={:?})",
 318                span, block, candidates);
 319
 320         // Start by simplifying candidates. Once this process is
 321         // complete, all the match pairs which remain require some
 322         // form of test, whether it be a switch or pattern comparison.
 323         for candidate in &mut candidates {
 324             unpack!(block = self.simplify_candidate(block, candidate));
 325         }
 326
 327         // The candidates are inversely sorted by priority. Check to
 328         // see whether the candidates in the front of the queue (and
 329         // hence back of the vec) have satisfied all their match
 330         // pairs.
 331         let fully_matched =
 332             candidates.iter().rev().take_while(|c| c.match_pairs.is_empty()).count();
 333         debug!("match_candidates: {:?} candidates fully matched", fully_matched);
 334         for _ in 0..fully_matched {
 335             // If so, apply any bindings, test the guard (if any), and
 336             // branch to the arm.
 337             let candidate = candidates.pop().unwrap();
 338             if let Some(b) = self.bind_and_guard_matched_candidate(block, arm_blocks, candidate) {
 339                 block = b;
 340             } else {
 341                 // if None is returned, then any remaining candidates
 342                 // are unreachable (at least not through this path).
 343                 return vec![];
 344             }
 345         }
 346
 347         // If there are no candidates that still need testing, we're done.
 348         // Since all matches are exhaustive, execution should never reach this point.
 349         if candidates.is_empty() {
 350             return vec![block];
 351         }
 352
 353         // Test candidates where possible.
 354         let (otherwise, tested_candidates) =
 355             self.test_candidates(span, arm_blocks, &candidates, block);
 356
 357         // If the target candidates were exhaustive, then we are done.
 358         if otherwise.is_empty() {
 359             return vec![];
 360         }
 361
 362         // If all candidates were sorted into `target_candidates` somewhere, then
 363         // the initial set was inexhaustive.
 364         let untested_candidates = candidates.len() - tested_candidates;
 365         if untested_candidates == 0 {
 366             return otherwise;
 367         }
 368
 369         // Otherwise, let's process those remaining candidates.
 370         let join_block = self.join_otherwise_blocks(otherwise);
 371         candidates.truncate(untested_candidates);
 372         self.match_candidates(span, arm_blocks, candidates, join_block)
 373     }
 374
 375     fn join_otherwise_blocks(&mut self,
 376                              otherwise: Vec<BasicBlock>)
 377                              -> BasicBlock
 378     {
 379         if otherwise.len() == 1 {
 380             otherwise[0]
 381         } else {
 382             let join_block = self.cfg.start_new_block();
 383             for block in otherwise {
 384                 self.cfg.terminate(block, Terminator::Goto { target: join_block });
 385             }
 386             join_block
 387         }
 388     }
 389
 390     /// This is the most subtle part of the matching algorithm.  At
 391     /// this point, the input candidates have been fully simplified,
 392     /// and so we know that all remaining match-pairs require some
 393     /// sort of test. To decide what test to do, we take the highest
 394     /// priority candidate (last one in the list) and extract the
 395     /// first match-pair from the list. From this we decide what kind
 396     /// of test is needed using `test`, defined in the `test` module.
 397     ///
 398     /// *Note:* taking the first match pair is somewhat arbitrary, and
 399     /// we might do better here by choosing more carefully what to
 400     /// test.
 401     ///
 402     /// For example, consider the following possible match-pairs:
 403     ///
 404     /// 1. `x @ Some(P)` -- we will do a `Switch` to decide what variant `x` has
 405     /// 2. `x @ 22` -- we will do a `SwitchInt`
 406     /// 3. `x @ 3..5` -- we will do a range test
 407     /// 4. etc.
 408     ///
 409     /// Once we know what sort of test we are going to perform, this
 410     /// test may also help us with other candidates. So we walk over
 411     /// the candidates (from high to low priority) and check. This
 412     /// gives us, for each outcome of the test, a transformed list of
 413     /// candidates.  For example, if we are testing the current
 414     /// variant of `x.0`, and we have a candidate `{x.0 @ Some(v), x.1
 415     /// @ 22}`, then we would have a resulting candidate of `{(x.0 as
 416     /// Some).0 @ v, x.1 @ 22}`. Note that the first match-pair is now
 417     /// simpler (and, in fact, irrefutable).
 418     ///
 419     /// But there may also be candidates that the test just doesn't
 420     /// apply to. For example, consider the case of #29740:
 421     ///
 422     /// ```rust
 423     /// match x {
 424     ///     "foo" => ...,
 425     ///     "bar" => ...,
 426     ///     "baz" => ...,
 427     ///     _ => ...,
 428     /// }
 429     /// ```
 430     ///
 431     /// Here the match-pair we are testing will be `x @ "foo"`, and we
 432     /// will generate an `Eq` test. Because `"bar"` and `"baz"` are different
 433     /// constants, we will decide that these later candidates are just not
 434     /// informed by the eq test. So we'll wind up with three candidate sets:
 435     ///
 436     /// - If outcome is that `x == "foo"` (one candidate, derived from `x @ "foo"`)
 437     /// - If outcome is that `x != "foo"` (empty list of candidates)
 438     /// - Otherwise (three candidates, `x @ "bar"`, `x @ "baz"`, `x @
 439     ///   _`). Here we have the invariant that everything in the
 440     ///   otherwise list is of **lower priority** than the stuff in the
 441     ///   other lists.
 442     ///
 443     /// So we'll compile the test. For each outcome of the test, we
 444     /// recursively call `match_candidates` with the corresponding set
 445     /// of candidates. But note that this set is now inexhaustive: for
 446     /// example, in the case where the test returns false, there are
 447     /// NO candidates, even though there is stll a value to be
 448     /// matched. So we'll collect the return values from
 449     /// `match_candidates`, which are the blocks where control-flow
 450     /// goes if none of the candidates matched. At this point, we can
 451     /// continue with the "otherwise" list.
 452     ///
 453     /// If you apply this to the above test, you basically wind up
 454     /// with an if-else-if chain, testing each candidate in turn,
 455     /// which is precisely what we want.
 456     fn test_candidates<'pat>(&mut self,
 457                              span: Span,
 458                              arm_blocks: &mut ArmBlocks,
 459                              candidates: &[Candidate<'pat, 'tcx>],
 460                              block: BasicBlock)
 461                              -> (Vec<BasicBlock>, usize)
 462     {
 463         // extract the match-pair from the highest priority candidate
 464         let match_pair = &candidates.last().unwrap().match_pairs[0];
 465         let mut test = self.test(match_pair);
 466
 467         // most of the time, the test to perform is simply a function
 468         // of the main candidate; but for a test like SwitchInt, we
 469         // may want to add cases based on the candidates that are
 470         // available
 471         match test.kind {
 472             TestKind::SwitchInt { switch_ty, ref mut options, ref mut indices } => {
 473                 for candidate in candidates.iter().rev() {
 474                     if !self.add_cases_to_switch(&match_pair.lvalue,
 475                                                  candidate,
 476                                                  switch_ty,
 477                                                  options,
 478                                                  indices) {
 479                         break;
 480                     }
 481                 }
 482             }
 483             _ => { }
 484         }
 485
 486         // perform the test, branching to one of N blocks. For each of
 487         // those N possible outcomes, create a (initially empty)
 488         // vector of candidates. Those are the candidates that still
 489         // apply if the test has that particular outcome.
 490         debug!("match_candidates: test={:?} match_pair={:?}", test, match_pair);
 491         let target_blocks = self.perform_test(block, &match_pair.lvalue, &test);
 492         let mut target_candidates: Vec<_> = (0..target_blocks.len()).map(|_| vec![]).collect();
 493
 494         // Sort the candidates into the appropriate vector in
 495         // `target_candidates`. Note that at some point we may
 496         // encounter a candidate where the test is not relevant; at
 497         // that point, we stop sorting.
 498         let tested_candidates =
 499             candidates.iter()
 500                       .rev()
 501                       .take_while(|c| self.sort_candidate(&match_pair.lvalue,
 502                                                           &test,
 503                                                           c,
 504                                                           &mut target_candidates))
 505                       .count();
 506         assert!(tested_candidates > 0); // at least the last candidate ought to be tested
 507
 508         // For each outcome of test, process the candidates that still
 509         // apply. Collect a list of blocks where control flow will
 510         // branch if one of the `target_candidate` sets is not
 511         // exhaustive.
 512         let otherwise: Vec<_> =
 513             target_blocks.into_iter()
 514                          .zip(target_candidates)
 515                          .flat_map(|(target_block, target_candidates)| {
 516                              self.match_candidates(span,
 517                                                    arm_blocks,
 518                                                    target_candidates,
 519                                                    target_block)
 520                          })
 521                          .collect();
 522
 523         (otherwise, tested_candidates)
 524     }
 525
 526     /// Initializes each of the bindings from the candidate by
 527     /// moving/copying/ref'ing the source as appropriate. Tests the
 528     /// guard, if any, and then branches to the arm. Returns the block
 529     /// for the case where the guard fails.
 530     ///
 531     /// Note: we check earlier that if there is a guard, there cannot
 532     /// be move bindings.  This isn't really important for the
 533     /// self-consistency of this fn, but the reason for it should be
 534     /// clear: after we've done the assignments, if there were move
 535     /// bindings, further tests would be a use-after-move (which would
 536     /// in turn be detected by the borrowck code that runs on the
 537     /// MIR).
 538     fn bind_and_guard_matched_candidate<'pat>(&mut self,
 539                                               mut block: BasicBlock,
 540                                               arm_blocks: &mut ArmBlocks,
 541                                               candidate: Candidate<'pat, 'tcx>)
 542                                               -> Option<BasicBlock> {
 543         debug!("bind_and_guard_matched_candidate(block={:?}, candidate={:?})",
 544                block, candidate);
 545
 546         debug_assert!(candidate.match_pairs.is_empty());
 547
 548         self.bind_matched_candidate(block, candidate.bindings);
 549
 550         let arm_block = arm_blocks.blocks[candidate.arm_index];
 551
 552         if let Some(guard) = candidate.guard {
 553             // the block to branch to if the guard fails; if there is no
 554             // guard, this block is simply unreachable
 555             let cond = unpack!(block = self.as_operand(block, guard));
 556             let otherwise = self.cfg.start_new_block();
 557             self.cfg.terminate(block, Terminator::If { cond: cond,
 558                                                        targets: (arm_block, otherwise)});
 559             Some(otherwise)
 560         } else {
 561             self.cfg.terminate(block, Terminator::Goto { target: arm_block });
 562             None
 563         }
 564     }
 565
 566     fn bind_matched_candidate(&mut self,
 567                               block: BasicBlock,
 568                               bindings: Vec<Binding<'tcx>>) {
 569         debug!("bind_matched_candidate(block={:?}, bindings={:?})",
 570                block, bindings);
 571
 572         // Assign each of the bindings. This may trigger moves out of the candidate.
 573         for binding in bindings {
 574             // Find the variable for the `var_id` being bound. It
 575             // should have been created by a previous call to
 576             // `declare_bindings`.
 577             let var_index = self.var_indices[&binding.var_id];
 578
 579             let rvalue = match binding.binding_mode {
 580                 BindingMode::ByValue =>
 581                     Rvalue::Use(Operand::Consume(binding.source)),
 582                 BindingMode::ByRef(region, borrow_kind) =>
 583                     Rvalue::Ref(region, borrow_kind, binding.source),
 584             };
 585
 586             self.cfg.push_assign(block, binding.span, &Lvalue::Var(var_index), rvalue);
 587         }
 588     }
 589
 590     fn declare_binding(&mut self,
 591                        var_extent: CodeExtent,
 592                        mutability: Mutability,
 593                        name: Name,
 594                        var_id: NodeId,
 595                        var_ty: Ty<'tcx>,
 596                        span: Span)
 597                        -> u32
 598     {
 599         debug!("declare_binding(var_id={:?}, name={:?}, var_ty={:?}, var_extent={:?}, span={:?})",
 600                var_id, name, var_ty, var_extent, span);
 601
 602         let index = self.var_decls.len();
 603         self.var_decls.push(VarDecl::<'tcx> {
 604             mutability: mutability,
 605             name: name,
 606             ty: var_ty.clone(),
 607         });
 608         let index = index as u32;
 609         self.schedule_drop(span, var_extent, DropKind::Deep, &Lvalue::Var(index), var_ty);
 610         self.var_indices.insert(var_id, index);
 611
 612         debug!("declare_binding: index={:?}", index);
 613
 614         index
 615     }
 616 }