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_data_structures::bitvec::BitVector;
  19 use rustc::middle::const_val::ConstVal;
  20 use rustc::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, 'gcx, 'tcx> Builder<'a, 'gcx, '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         let mut arm_blocks = ArmBlocks {
  42             blocks: arms.iter()
  43                         .map(|_| self.cfg.start_new_block())
  44                         .collect(),
  45         };
  46
  47         // Get the arm bodies and their scopes, while declaring bindings.
  48         let arm_bodies: Vec<_> = arms.iter().map(|arm| {
  49             let body = self.hir.mirror(arm.body.clone());
  50             let scope = self.declare_bindings(None, body.span, &arm.patterns[0]);
  51             (body, scope.unwrap_or(self.visibility_scope))
  52         }).collect();
  53
  54         // assemble a list of candidates: there is one candidate per
  55         // pattern, which means there may be more than one candidate
  56         // *per arm*. These candidates are kept sorted such that the
  57         // highest priority candidate comes first in the list.
  58         // (i.e. same order as in source)
  59         let candidates: Vec<_> =
  60             arms.iter()
  61                 .enumerate()
  62                 .flat_map(|(arm_index, arm)| {
  63                     arm.patterns.iter()
  64                                 .map(move |pat| (arm_index, pat, arm.guard.clone()))
  65                 })
  66                 .map(|(arm_index, pattern, guard)| {
  67                     Candidate {
  68                         span: pattern.span,
  69                         match_pairs: vec![MatchPair::new(discriminant_lvalue.clone(), pattern)],
  70                         bindings: vec![],
  71                         guard: guard,
  72                         arm_index: arm_index,
  73                     }
  74                 })
  75                 .collect();
  76
  77         // this will generate code to test discriminant_lvalue and
  78         // branch to the appropriate arm block
  79         let otherwise = self.match_candidates(span, &mut arm_blocks, candidates, block);
  80
  81         if !otherwise.is_empty() {
  82             // All matches are exhaustive. However, because some matches
  83             // only have exponentially-large exhaustive decision trees, we
  84             // sometimes generate an inexhaustive decision tree.
  85             //
  86             // In that case, the inexhaustive tips of the decision tree
  87             // can't be reached - terminate them with an `unreachable`.
  88             let source_info = self.source_info(span);
  89
  90             let mut otherwise = otherwise;
  91             otherwise.sort();
  92             otherwise.dedup(); // variant switches can introduce duplicate target blocks
  93             for block in otherwise {
  94                 self.cfg.terminate(block, source_info, TerminatorKind::Unreachable);
  95             }
  96         }
  97
  98         // all the arm blocks will rejoin here
  99         let end_block = self.cfg.start_new_block();
 100
 101         let outer_source_info = self.source_info(span);
 102         for (arm_index, (body, visibility_scope)) in arm_bodies.into_iter().enumerate() {
 103             let mut arm_block = arm_blocks.blocks[arm_index];
 104             // Re-enter the visibility scope we created the bindings in.
 105             self.visibility_scope = visibility_scope;
 106             unpack!(arm_block = self.into(destination, arm_block, body));
 107             self.cfg.terminate(arm_block, outer_source_info,
 108                                TerminatorKind::Goto { target: end_block });
 109         }
 110         self.visibility_scope = outer_source_info.scope;
 111
 112         end_block.unit()
 113     }
 114
 115     pub fn expr_into_pattern(&mut self,
 116                              mut block: BasicBlock,
 117                              irrefutable_pat: Pattern<'tcx>,
 118                              initializer: ExprRef<'tcx>)
 119                              -> BlockAnd<()> {
 120         // optimize the case of `let x = ...`
 121         match *irrefutable_pat.kind {
 122             PatternKind::Binding { mode: BindingMode::ByValue,
 123                                    var,
 124                                    subpattern: None, .. } => {
 125                 let lvalue = Lvalue::Var(self.var_indices[&var]);
 126                 return self.into(&lvalue, block, initializer);
 127             }
 128             _ => {}
 129         }
 130         let lvalue = unpack!(block = self.as_lvalue(block, initializer));
 131         self.lvalue_into_pattern(block,
 132                                  irrefutable_pat,
 133                                  &lvalue)
 134     }
 135
 136     pub fn lvalue_into_pattern(&mut self,
 137                                mut block: BasicBlock,
 138                                irrefutable_pat: Pattern<'tcx>,
 139                                initializer: &Lvalue<'tcx>)
 140                                -> BlockAnd<()> {
 141         // create a dummy candidate
 142         let mut candidate = Candidate {
 143             span: irrefutable_pat.span,
 144             match_pairs: vec![MatchPair::new(initializer.clone(), &irrefutable_pat)],
 145             bindings: vec![],
 146             guard: None,
 147             arm_index: 0, // since we don't call `match_candidates`, this field is unused
 148         };
 149
 150         // Simplify the candidate. Since the pattern is irrefutable, this should
 151         // always convert all match-pairs into bindings.
 152         unpack!(block = self.simplify_candidate(block, &mut candidate));
 153
 154         if !candidate.match_pairs.is_empty() {
 155             span_bug!(candidate.match_pairs[0].pattern.span,
 156                       "match pairs {:?} remaining after simplifying \
 157                        irrefutable pattern",
 158                       candidate.match_pairs);
 159         }
 160
 161         // now apply the bindings, which will also declare the variables
 162         self.bind_matched_candidate(block, candidate.bindings);
 163
 164         block.unit()
 165     }
 166
 167     /// Declares the bindings of the given pattern and returns the visibility scope
 168     /// for the bindings in this patterns, if such a scope had to be created.
 169     /// NOTE: Declaring the bindings should always be done in their drop scope.
 170     pub fn declare_bindings(&mut self,
 171                             mut var_scope: Option<VisibilityScope>,
 172                             scope_span: Span,
 173                             pattern: &Pattern<'tcx>)
 174                             -> Option<VisibilityScope> {
 175         match *pattern.kind {
 176             PatternKind::Binding { mutability, name, mode: _, var, ty, ref subpattern } => {
 177                 if var_scope.is_none() {
 178                     var_scope = Some(self.new_visibility_scope(scope_span));
 179                 }
 180                 let source_info = SourceInfo {
 181                     span: pattern.span,
 182                     scope: var_scope.unwrap()
 183                 };
 184                 self.declare_binding(source_info, mutability, name, var, ty);
 185                 if let Some(subpattern) = subpattern.as_ref() {
 186                     var_scope = self.declare_bindings(var_scope, scope_span, subpattern);
 187                 }
 188             }
 189             PatternKind::Array { ref prefix, ref slice, ref suffix } |
 190             PatternKind::Slice { ref prefix, ref slice, ref suffix } => {
 191                 for subpattern in prefix.iter().chain(slice).chain(suffix) {
 192                     var_scope = self.declare_bindings(var_scope, scope_span, subpattern);
 193                 }
 194             }
 195             PatternKind::Constant { .. } | PatternKind::Range { .. } | PatternKind::Wild => {
 196             }
 197             PatternKind::Deref { ref subpattern } => {
 198                 var_scope = self.declare_bindings(var_scope, scope_span, subpattern);
 199             }
 200             PatternKind::Leaf { ref subpatterns } |
 201             PatternKind::Variant { ref subpatterns, .. } => {
 202                 for subpattern in subpatterns {
 203                     var_scope = self.declare_bindings(var_scope, scope_span, &subpattern.pattern);
 204                 }
 205             }
 206         }
 207         var_scope
 208     }
 209 }
 210
 211 /// List of blocks for each arm (and potentially other metadata in the
 212 /// future).
 213 struct ArmBlocks {
 214     blocks: Vec<BasicBlock>,
 215 }
 216
 217 #[derive(Clone, Debug)]
 218 pub struct Candidate<'pat, 'tcx:'pat> {
 219     // span of the original pattern that gave rise to this candidate
 220     span: Span,
 221
 222     // all of these must be satisfied...
 223     match_pairs: Vec<MatchPair<'pat, 'tcx>>,
 224
 225     // ...these bindings established...
 226     bindings: Vec<Binding<'tcx>>,
 227
 228     // ...and the guard must be evaluated...
 229     guard: Option<ExprRef<'tcx>>,
 230
 231     // ...and then we branch to arm with this index.
 232     arm_index: usize,
 233 }
 234
 235 #[derive(Clone, Debug)]
 236 struct Binding<'tcx> {
 237     span: Span,
 238     source: Lvalue<'tcx>,
 239     name: Name,
 240     var_id: NodeId,
 241     var_ty: Ty<'tcx>,
 242     mutability: Mutability,
 243     binding_mode: BindingMode,
 244 }
 245
 246 #[derive(Clone, Debug)]
 247 pub struct MatchPair<'pat, 'tcx:'pat> {
 248     // this lvalue...
 249     lvalue: Lvalue<'tcx>,
 250
 251     // ... must match this pattern.
 252     pattern: &'pat Pattern<'tcx>,
 253
 254     // HACK(eddyb) This is used to toggle whether a Slice pattern
 255     // has had its length checked. This is only necessary because
 256     // the "rest" part of the pattern right now has type &[T] and
 257     // as such, it requires an Rvalue::Slice to be generated.
 258     // See RFC 495 / issue #23121 for the eventual (proper) solution.
 259     slice_len_checked: bool
 260 }
 261
 262 #[derive(Clone, Debug, PartialEq)]
 263 enum TestKind<'tcx> {
 264     // test the branches of enum
 265     Switch {
 266         adt_def: AdtDef<'tcx>,
 267         variants: BitVector,
 268     },
 269
 270     // test the branches of enum
 271     SwitchInt {
 272         switch_ty: Ty<'tcx>,
 273         options: Vec<ConstVal>,
 274         indices: FnvHashMap<ConstVal, usize>,
 275     },
 276
 277     // test for equality
 278     Eq {
 279         value: ConstVal,
 280         ty: Ty<'tcx>,
 281     },
 282
 283     // test whether the value falls within an inclusive range
 284     Range {
 285         lo: Literal<'tcx>,
 286         hi: Literal<'tcx>,
 287         ty: Ty<'tcx>,
 288     },
 289
 290     // test length of the slice is equal to len
 291     Len {
 292         len: u64,
 293         op: BinOp,
 294     },
 295 }
 296
 297 #[derive(Debug)]
 298 pub struct Test<'tcx> {
 299     span: Span,
 300     kind: TestKind<'tcx>,
 301 }
 302
 303 ///////////////////////////////////////////////////////////////////////////
 304 // Main matching algorithm
 305
 306 impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> {
 307     /// The main match algorithm. It begins with a set of candidates
 308     /// `candidates` and has the job of generating code to determine
 309     /// which of these candidates, if any, is the correct one. The
 310     /// candidates are sorted such that the first item in the list
 311     /// has the highest priority. When a candidate is found to match
 312     /// the value, we will generate a branch to the appropriate
 313     /// block found in `arm_blocks`.
 314     ///
 315     /// The return value is a list of "otherwise" blocks. These are
 316     /// points in execution where we found that *NONE* of the
 317     /// candidates apply.  In principle, this means that the input
 318     /// list was not exhaustive, though at present we sometimes are
 319     /// not smart enough to recognize all exhaustive inputs.
 320     ///
 321     /// It might be surprising that the input can be inexhaustive.
 322     /// Indeed, initially, it is not, because all matches are
 323     /// exhaustive in Rust. But during processing we sometimes divide
 324     /// up the list of candidates and recurse with a non-exhaustive
 325     /// list. This is important to keep the size of the generated code
 326     /// under control. See `test_candidates` for more details.
 327     fn match_candidates<'pat>(&mut self,
 328                               span: Span,
 329                               arm_blocks: &mut ArmBlocks,
 330                               mut candidates: Vec<Candidate<'pat, 'tcx>>,
 331                               mut block: BasicBlock)
 332                               -> Vec<BasicBlock>
 333     {
 334         debug!("matched_candidate(span={:?}, block={:?}, candidates={:?})",
 335                span, block, candidates);
 336
 337         // Start by simplifying candidates. Once this process is
 338         // complete, all the match pairs which remain require some
 339         // form of test, whether it be a switch or pattern comparison.
 340         for candidate in &mut candidates {
 341             unpack!(block = self.simplify_candidate(block, candidate));
 342         }
 343
 344         // The candidates are sorted by priority. Check to see
 345         // whether the higher priority candidates (and hence at
 346         // the front of the vec) have satisfied all their match
 347         // pairs.
 348         let fully_matched =
 349             candidates.iter().take_while(|c| c.match_pairs.is_empty()).count();
 350         debug!("match_candidates: {:?} candidates fully matched", fully_matched);
 351         let mut unmatched_candidates = candidates.split_off(fully_matched);
 352         for candidate in candidates {
 353             // If so, apply any bindings, test the guard (if any), and
 354             // branch to the arm.
 355             if let Some(b) = self.bind_and_guard_matched_candidate(block, arm_blocks, candidate) {
 356                 block = b;
 357             } else {
 358                 // if None is returned, then any remaining candidates
 359                 // are unreachable (at least not through this path).
 360                 return vec![];
 361             }
 362         }
 363
 364         // If there are no candidates that still need testing, we're done.
 365         // Since all matches are exhaustive, execution should never reach this point.
 366         if unmatched_candidates.is_empty() {
 367             return vec![block];
 368         }
 369
 370         // Test candidates where possible.
 371         let (otherwise, tested_candidates) =
 372             self.test_candidates(span, arm_blocks, &unmatched_candidates, block);
 373
 374         // If the target candidates were exhaustive, then we are done.
 375         if otherwise.is_empty() {
 376             return vec![];
 377         }
 378
 379         // If all candidates were sorted into `target_candidates` somewhere, then
 380         // the initial set was inexhaustive.
 381         let untested_candidates = unmatched_candidates.split_off(tested_candidates);
 382         if untested_candidates.len() == 0 {
 383             return otherwise;
 384         }
 385
 386         // Otherwise, let's process those remaining candidates.
 387         let join_block = self.join_otherwise_blocks(span, otherwise);
 388         self.match_candidates(span, arm_blocks, untested_candidates, join_block)
 389     }
 390
 391     fn join_otherwise_blocks(&mut self,
 392                              span: Span,
 393                              mut otherwise: Vec<BasicBlock>)
 394                              -> BasicBlock
 395     {
 396         let source_info = self.source_info(span);
 397         otherwise.sort();
 398         otherwise.dedup(); // variant switches can introduce duplicate target blocks
 399         if otherwise.len() == 1 {
 400             otherwise[0]
 401         } else {
 402             let join_block = self.cfg.start_new_block();
 403             for block in otherwise {
 404                 self.cfg.terminate(block, source_info,
 405                                    TerminatorKind::Goto { target: join_block });
 406             }
 407             join_block
 408         }
 409     }
 410
 411     /// This is the most subtle part of the matching algorithm.  At
 412     /// this point, the input candidates have been fully simplified,
 413     /// and so we know that all remaining match-pairs require some
 414     /// sort of test. To decide what test to do, we take the highest
 415     /// priority candidate (last one in the list) and extract the
 416     /// first match-pair from the list. From this we decide what kind
 417     /// of test is needed using `test`, defined in the `test` module.
 418     ///
 419     /// *Note:* taking the first match pair is somewhat arbitrary, and
 420     /// we might do better here by choosing more carefully what to
 421     /// test.
 422     ///
 423     /// For example, consider the following possible match-pairs:
 424     ///
 425     /// 1. `x @ Some(P)` -- we will do a `Switch` to decide what variant `x` has
 426     /// 2. `x @ 22` -- we will do a `SwitchInt`
 427     /// 3. `x @ 3..5` -- we will do a range test
 428     /// 4. etc.
 429     ///
 430     /// Once we know what sort of test we are going to perform, this
 431     /// test may also help us with other candidates. So we walk over
 432     /// the candidates (from high to low priority) and check. This
 433     /// gives us, for each outcome of the test, a transformed list of
 434     /// candidates.  For example, if we are testing the current
 435     /// variant of `x.0`, and we have a candidate `{x.0 @ Some(v), x.1
 436     /// @ 22}`, then we would have a resulting candidate of `{(x.0 as
 437     /// Some).0 @ v, x.1 @ 22}`. Note that the first match-pair is now
 438     /// simpler (and, in fact, irrefutable).
 439     ///
 440     /// But there may also be candidates that the test just doesn't
 441     /// apply to. The classical example involves wildcards:
 442     ///
 443     /// ```rust,ignore
 444     /// match (x, y, z) {
 445     ///     (true, _, true) => true,    // (0)
 446     ///     (_, true, _) => true,       // (1)
 447     ///     (false, false, _) => false, // (2)
 448     ///     (true, _, false) => false,  // (3)
 449     /// }
 450     /// ```
 451     ///
 452     /// In that case, after we test on `x`, there are 2 overlapping candidate
 453     /// sets:
 454     ///
 455     /// - If the outcome is that `x` is true, candidates 0, 1, and 3
 456     /// - If the outcome is that `x` is false, candidates 1 and 2
 457     ///
 458     /// Here, the traditional "decision tree" method would generate 2
 459     /// separate code-paths for the 2 separate cases.
 460     ///
 461     /// In some cases, this duplication can create an exponential amount of
 462     /// code. This is most easily seen by noticing that this method terminates
 463     /// with precisely the reachable arms being reachable - but that problem
 464     /// is trivially NP-complete:
 465     ///
 466     /// ```rust
 467     ///     match (var0, var1, var2, var3, ..) {
 468     ///         (true, _, _, false, true, ...) => false,
 469     ///         (_, true, true, false, _, ...) => false,
 470     ///         (false, _, false, false, _, ...) => false,
 471     ///         ...
 472     ///         _ => true
 473     ///     }
 474     /// ```
 475     ///
 476     /// Here the last arm is reachable only if there is an assignment to
 477     /// the variables that does not match any of the literals. Therefore,
 478     /// compilation would take an exponential amount of time in some cases.
 479     ///
 480     /// That kind of exponential worst-case might not occur in practice, but
 481     /// our simplistic treatment of constants and guards would make it occur
 482     /// in very common situations - for example #29740:
 483     ///
 484     /// ```rust
 485     /// match x {
 486     ///     "foo" if foo_guard => ...,
 487     ///     "bar" if bar_guard => ...,
 488     ///     "baz" if baz_guard => ...,
 489     ///     ...
 490     /// }
 491     /// ```
 492     ///
 493     /// Here we first test the match-pair `x @ "foo"`, which is an `Eq` test.
 494     ///
 495     /// It might seem that we would end up with 2 disjoint candidate
 496     /// sets, consisting of the first candidate or the other 3, but our
 497     /// algorithm doesn't reason about "foo" being distinct from the other
 498     /// constants; it considers the latter arms to potentially match after
 499     /// both outcomes, which obviously leads to an exponential amount
 500     /// of tests.
 501     ///
 502     /// To avoid these kinds of problems, our algorithm tries to ensure
 503     /// the amount of generated tests is linear. When we do a k-way test,
 504     /// we return an additional "unmatched" set alongside the obvious `k`
 505     /// sets. When we encounter a candidate that would be present in more
 506     /// than one of the sets, we put it and all candidates below it into the
 507     /// "unmatched" set. This ensures these `k+1` sets are disjoint.
 508     ///
 509     /// After we perform our test, we branch into the appropriate candidate
 510     /// set and recurse with `match_candidates`. These sub-matches are
 511     /// obviously inexhaustive - as we discarded our otherwise set - so
 512     /// we set their continuation to do `match_candidates` on the
 513     /// "unmatched" set (which is again inexhaustive).
 514     ///
 515     /// If you apply this to the above test, you basically wind up
 516     /// with an if-else-if chain, testing each candidate in turn,
 517     /// which is precisely what we want.
 518     ///
 519     /// In addition to avoiding exponential-time blowups, this algorithm
 520     /// also has nice property that each guard and arm is only generated
 521     /// once.
 522     fn test_candidates<'pat>(&mut self,
 523                              span: Span,
 524                              arm_blocks: &mut ArmBlocks,
 525                              candidates: &[Candidate<'pat, 'tcx>],
 526                              block: BasicBlock)
 527                              -> (Vec<BasicBlock>, usize)
 528     {
 529         // extract the match-pair from the highest priority candidate
 530         let match_pair = &candidates.first().unwrap().match_pairs[0];
 531         let mut test = self.test(match_pair);
 532
 533         // most of the time, the test to perform is simply a function
 534         // of the main candidate; but for a test like SwitchInt, we
 535         // may want to add cases based on the candidates that are
 536         // available
 537         match test.kind {
 538             TestKind::SwitchInt { switch_ty, ref mut options, ref mut indices } => {
 539                 for candidate in candidates.iter() {
 540                     if !self.add_cases_to_switch(&match_pair.lvalue,
 541                                                  candidate,
 542                                                  switch_ty,
 543                                                  options,
 544                                                  indices) {
 545                         break;
 546                     }
 547                 }
 548             }
 549             TestKind::Switch { adt_def: _, ref mut variants} => {
 550                 for candidate in candidates.iter() {
 551                     if !self.add_variants_to_switch(&match_pair.lvalue,
 552                                                     candidate,
 553                                                     variants) {
 554                         break;
 555                     }
 556                 }
 557             }
 558             _ => { }
 559         }
 560
 561         // perform the test, branching to one of N blocks. For each of
 562         // those N possible outcomes, create a (initially empty)
 563         // vector of candidates. Those are the candidates that still
 564         // apply if the test has that particular outcome.
 565         debug!("match_candidates: test={:?} match_pair={:?}", test, match_pair);
 566         let target_blocks = self.perform_test(block, &match_pair.lvalue, &test);
 567         let mut target_candidates: Vec<_> = (0..target_blocks.len()).map(|_| vec![]).collect();
 568
 569         // Sort the candidates into the appropriate vector in
 570         // `target_candidates`. Note that at some point we may
 571         // encounter a candidate where the test is not relevant; at
 572         // that point, we stop sorting.
 573         let tested_candidates =
 574             candidates.iter()
 575                       .take_while(|c| self.sort_candidate(&match_pair.lvalue,
 576                                                           &test,
 577                                                           c,
 578                                                           &mut target_candidates))
 579                       .count();
 580         assert!(tested_candidates > 0); // at least the last candidate ought to be tested
 581         debug!("tested_candidates: {}", tested_candidates);
 582         debug!("untested_candidates: {}", candidates.len() - tested_candidates);
 583
 584         // For each outcome of test, process the candidates that still
 585         // apply. Collect a list of blocks where control flow will
 586         // branch if one of the `target_candidate` sets is not
 587         // exhaustive.
 588         let otherwise: Vec<_> =
 589             target_blocks.into_iter()
 590                          .zip(target_candidates)
 591                          .flat_map(|(target_block, target_candidates)| {
 592                              self.match_candidates(span,
 593                                                    arm_blocks,
 594                                                    target_candidates,
 595                                                    target_block)
 596                          })
 597                          .collect();
 598
 599         (otherwise, tested_candidates)
 600     }
 601
 602     /// Initializes each of the bindings from the candidate by
 603     /// moving/copying/ref'ing the source as appropriate. Tests the
 604     /// guard, if any, and then branches to the arm. Returns the block
 605     /// for the case where the guard fails.
 606     ///
 607     /// Note: we check earlier that if there is a guard, there cannot
 608     /// be move bindings.  This isn't really important for the
 609     /// self-consistency of this fn, but the reason for it should be
 610     /// clear: after we've done the assignments, if there were move
 611     /// bindings, further tests would be a use-after-move (which would
 612     /// in turn be detected by the borrowck code that runs on the
 613     /// MIR).
 614     fn bind_and_guard_matched_candidate<'pat>(&mut self,
 615                                               mut block: BasicBlock,
 616                                               arm_blocks: &mut ArmBlocks,
 617                                               candidate: Candidate<'pat, 'tcx>)
 618                                               -> Option<BasicBlock> {
 619         debug!("bind_and_guard_matched_candidate(block={:?}, candidate={:?})",
 620                block, candidate);
 621
 622         debug_assert!(candidate.match_pairs.is_empty());
 623
 624         self.bind_matched_candidate(block, candidate.bindings);
 625
 626         let arm_block = arm_blocks.blocks[candidate.arm_index];
 627
 628         if let Some(guard) = candidate.guard {
 629             // the block to branch to if the guard fails; if there is no
 630             // guard, this block is simply unreachable
 631             let guard = self.hir.mirror(guard);
 632             let source_info = self.source_info(guard.span);
 633             let cond = unpack!(block = self.as_operand(block, guard));
 634             let otherwise = self.cfg.start_new_block();
 635             self.cfg.terminate(block, source_info,
 636                                TerminatorKind::If { cond: cond,
 637                                                     targets: (arm_block, otherwise)});
 638             Some(otherwise)
 639         } else {
 640             let source_info = self.source_info(candidate.span);
 641             self.cfg.terminate(block, source_info,
 642                                TerminatorKind::Goto { target: arm_block });
 643             None
 644         }
 645     }
 646
 647     fn bind_matched_candidate(&mut self,
 648                               block: BasicBlock,
 649                               bindings: Vec<Binding<'tcx>>) {
 650         debug!("bind_matched_candidate(block={:?}, bindings={:?})",
 651                block, bindings);
 652
 653         // Assign each of the bindings. This may trigger moves out of the candidate.
 654         for binding in bindings {
 655             // Find the variable for the `var_id` being bound. It
 656             // should have been created by a previous call to
 657             // `declare_bindings`.
 658             let var_index = self.var_indices[&binding.var_id];
 659
 660             let rvalue = match binding.binding_mode {
 661                 BindingMode::ByValue =>
 662                     Rvalue::Use(Operand::Consume(binding.source)),
 663                 BindingMode::ByRef(region, borrow_kind) =>
 664                     Rvalue::Ref(region, borrow_kind, binding.source),
 665             };
 666
 667             let source_info = self.source_info(binding.span);
 668             self.cfg.push_assign(block, source_info,
 669                                  &Lvalue::Var(var_index), rvalue);
 670         }
 671     }
 672
 673     fn declare_binding(&mut self,
 674                        source_info: SourceInfo,
 675                        mutability: Mutability,
 676                        name: Name,
 677                        var_id: NodeId,
 678                        var_ty: Ty<'tcx>)
 679                        -> Var
 680     {
 681         debug!("declare_binding(var_id={:?}, name={:?}, var_ty={:?}, source_info={:?})",
 682                var_id, name, var_ty, source_info);
 683
 684         let var = self.var_decls.push(VarDecl::<'tcx> {
 685             source_info: source_info,
 686             mutability: mutability,
 687             name: name,
 688             ty: var_ty.clone(),
 689         });
 690         let extent = self.extent_of_innermost_scope();
 691         self.schedule_drop(source_info.span, extent, &Lvalue::Var(var), var_ty);
 692         self.var_indices.insert(var_id, var);
 693
 694         debug!("declare_binding: var={:?}", var);
 695
 696         var
 697     }
 698 }