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