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.
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.
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
16 use build::{BlockAnd, BlockAndExtension, Builder};
17 use rustc_data_structures::fnv::FnvHashMap;
18 use rustc::middle::const_eval::ConstVal;
19 use rustc::middle::ty::{AdtDef, Ty};
20 use rustc::mir::repr::*;
22 use syntax::ast::{Name, NodeId};
23 use syntax::codemap::Span;
25 // helper functions, broken out by category:
30 impl<'a,'tcx> Builder<'a,'tcx> {
31 pub fn match_expr(&mut self,
32 destination: &Lvalue<'tcx>,
34 mut block: BasicBlock,
35 discriminant: ExprRef<'tcx>,
38 let discriminant_lvalue = unpack!(block = self.as_lvalue(block, discriminant));
40 // Before we do anything, create uninitialized variables with
41 // suitable extent for all of the bindings in this match. It's
42 // easiest to do this up front because some of these arms may
43 // be unreachable or reachable multiple times.
44 let var_scope_id = self.innermost_scope_id();
46 self.declare_bindings(var_scope_id, &arm.patterns[0]);
49 let mut arm_blocks = ArmBlocks {
51 .map(|_| self.cfg.start_new_block())
55 let arm_bodies: Vec<ExprRef<'tcx>> =
57 .map(|arm| arm.body.clone())
60 // assemble a list of candidates: there is one candidate per
61 // pattern, which means there may be more than one candidate
62 // *per arm*. These candidates are kept sorted such that the
63 // highest priority candidate comes first in the list.
64 // (i.e. same order as in source)
65 let candidates: Vec<_> =
68 .flat_map(|(arm_index, arm)| {
70 .map(move |pat| (arm_index, pat, arm.guard.clone()))
72 .map(|(arm_index, pattern, guard)| {
74 match_pairs: vec![MatchPair::new(discriminant_lvalue.clone(), pattern)],
82 // this will generate code to test discriminant_lvalue and
83 // branch to the appropriate arm block
84 let otherwise = self.match_candidates(span, &mut arm_blocks, candidates, block);
86 // because all matches are exhaustive, in principle we expect
87 // an empty vector to be returned here, but the algorithm is
88 // not entirely precise
89 if !otherwise.is_empty() {
90 let join_block = self.join_otherwise_blocks(otherwise);
91 self.panic(join_block, "something about matches algorithm not being precise", span);
94 // all the arm blocks will rejoin here
95 let end_block = self.cfg.start_new_block();
97 for (arm_index, arm_body) in arm_bodies.into_iter().enumerate() {
98 let mut arm_block = arm_blocks.blocks[arm_index];
99 unpack!(arm_block = self.into(destination, arm_block, arm_body));
100 self.cfg.terminate(arm_block, Terminator::Goto { target: end_block });
106 pub fn expr_into_pattern(&mut self,
107 mut block: BasicBlock,
108 var_scope_id: ScopeId, // lifetime of vars
109 irrefutable_pat: Pattern<'tcx>,
110 initializer: ExprRef<'tcx>)
112 // optimize the case of `let x = ...`
113 match *irrefutable_pat.kind {
114 PatternKind::Binding { mutability,
116 mode: BindingMode::ByValue,
119 subpattern: None } => {
120 let index = self.declare_binding(var_scope_id,
125 irrefutable_pat.span);
126 let lvalue = Lvalue::Var(index);
127 return self.into(&lvalue, block, initializer);
131 let lvalue = unpack!(block = self.as_lvalue(block, initializer));
132 self.lvalue_into_pattern(block,
138 pub fn lvalue_into_pattern(&mut self,
139 mut block: BasicBlock,
140 var_scope_id: ScopeId,
141 irrefutable_pat: Pattern<'tcx>,
142 initializer: &Lvalue<'tcx>)
144 // first, creating the bindings
145 self.declare_bindings(var_scope_id, &irrefutable_pat);
147 // create a dummy candidate
148 let mut candidate = Candidate {
149 match_pairs: vec![MatchPair::new(initializer.clone(), &irrefutable_pat)],
152 arm_index: 0, // since we don't call `match_candidates`, this field is unused
155 // Simplify the candidate. Since the pattern is irrefutable, this should
156 // always convert all match-pairs into bindings.
157 unpack!(block = self.simplify_candidate(block, &mut candidate));
159 if !candidate.match_pairs.is_empty() {
160 self.hir.span_bug(candidate.match_pairs[0].pattern.span,
161 &format!("match pairs {:?} remaining after simplifying \
162 irrefutable pattern",
163 candidate.match_pairs));
166 // now apply the bindings, which will also declare the variables
167 self.bind_matched_candidate(block, candidate.bindings);
172 pub fn declare_bindings(&mut self, var_scope_id: ScopeId, pattern: &Pattern<'tcx>) {
173 match *pattern.kind {
174 PatternKind::Binding { mutability, name, mode: _, var, ty, ref subpattern } => {
175 self.declare_binding(var_scope_id, mutability, name, var, ty, pattern.span);
176 if let Some(subpattern) = subpattern.as_ref() {
177 self.declare_bindings(var_scope_id, subpattern);
180 PatternKind::Array { ref prefix, ref slice, ref suffix } |
181 PatternKind::Slice { ref prefix, ref slice, ref suffix } => {
182 for subpattern in prefix.iter().chain(slice).chain(suffix) {
183 self.declare_bindings(var_scope_id, subpattern);
186 PatternKind::Constant { .. } | PatternKind::Range { .. } | PatternKind::Wild => {
188 PatternKind::Deref { ref subpattern } => {
189 self.declare_bindings(var_scope_id, subpattern);
191 PatternKind::Leaf { ref subpatterns } |
192 PatternKind::Variant { ref subpatterns, .. } => {
193 for subpattern in subpatterns {
194 self.declare_bindings(var_scope_id, &subpattern.pattern);
201 /// List of blocks for each arm (and potentially other metadata in the
204 blocks: Vec<BasicBlock>,
207 #[derive(Clone, Debug)]
208 pub struct Candidate<'pat, 'tcx:'pat> {
209 // all of these must be satisfied...
210 match_pairs: Vec<MatchPair<'pat, 'tcx>>,
212 // ...these bindings established...
213 bindings: Vec<Binding<'tcx>>,
215 // ...and the guard must be evaluated...
216 guard: Option<ExprRef<'tcx>>,
218 // ...and then we branch to arm with this index.
222 #[derive(Clone, Debug)]
223 struct Binding<'tcx> {
225 source: Lvalue<'tcx>,
229 mutability: Mutability,
230 binding_mode: BindingMode,
233 #[derive(Clone, Debug)]
234 pub struct MatchPair<'pat, 'tcx:'pat> {
236 lvalue: Lvalue<'tcx>,
238 // ... must match this pattern.
239 pattern: &'pat Pattern<'tcx>,
241 // HACK(eddyb) This is used to toggle whether a Slice pattern
242 // has had its length checked. This is only necessary because
243 // the "rest" part of the pattern right now has type &[T] and
244 // as such, it requires an Rvalue::Slice to be generated.
245 // See RFC 495 / issue #23121 for the eventual (proper) solution.
246 slice_len_checked: bool
249 #[derive(Clone, Debug, PartialEq)]
250 enum TestKind<'tcx> {
251 // test the branches of enum
253 adt_def: AdtDef<'tcx>,
256 // test the branches of enum
259 options: Vec<ConstVal>,
260 indices: FnvHashMap<ConstVal, usize>,
269 // test whether the value falls within an inclusive range
276 // test length of the slice is equal to len
284 pub struct Test<'tcx> {
286 kind: TestKind<'tcx>,
289 ///////////////////////////////////////////////////////////////////////////
290 // Main matching algorithm
292 impl<'a,'tcx> Builder<'a,'tcx> {
293 /// The main match algorithm. It begins with a set of candidates
294 /// `candidates` and has the job of generating code to determine
295 /// which of these candidates, if any, is the correct one. The
296 /// candidates are sorted such that the first item in the list
297 /// has the highest priority. When a candidate is found to match
298 /// the value, we will generate a branch to the appropriate
299 /// block found in `arm_blocks`.
301 /// The return value is a list of "otherwise" blocks. These are
302 /// points in execution where we found that *NONE* of the
303 /// candidates apply. In principle, this means that the input
304 /// list was not exhaustive, though at present we sometimes are
305 /// not smart enough to recognize all exhaustive inputs.
307 /// It might be surprising that the input can be inexhaustive.
308 /// Indeed, initially, it is not, because all matches are
309 /// exhaustive in Rust. But during processing we sometimes divide
310 /// up the list of candidates and recurse with a non-exhaustive
311 /// list. This is important to keep the size of the generated code
312 /// under control. See `test_candidates` for more details.
313 fn match_candidates<'pat>(&mut self,
315 arm_blocks: &mut ArmBlocks,
316 mut candidates: Vec<Candidate<'pat, 'tcx>>,
317 mut block: BasicBlock)
320 debug!("matched_candidate(span={:?}, block={:?}, candidates={:?})",
321 span, block, candidates);
323 // Start by simplifying candidates. Once this process is
324 // complete, all the match pairs which remain require some
325 // form of test, whether it be a switch or pattern comparison.
326 for candidate in &mut candidates {
327 unpack!(block = self.simplify_candidate(block, candidate));
330 // The candidates are sorted by priority. Check to see
331 // whether the higher priority candidates (and hence at
332 // the front of the vec) have satisfied all their match
335 candidates.iter().take_while(|c| c.match_pairs.is_empty()).count();
336 debug!("match_candidates: {:?} candidates fully matched", fully_matched);
337 let mut unmatched_candidates = candidates.split_off(fully_matched);
338 for candidate in candidates {
339 // If so, apply any bindings, test the guard (if any), and
340 // branch to the arm.
341 if let Some(b) = self.bind_and_guard_matched_candidate(block, arm_blocks, candidate) {
344 // if None is returned, then any remaining candidates
345 // are unreachable (at least not through this path).
350 // If there are no candidates that still need testing, we're done.
351 // Since all matches are exhaustive, execution should never reach this point.
352 if unmatched_candidates.is_empty() {
356 // Test candidates where possible.
357 let (otherwise, tested_candidates) =
358 self.test_candidates(span, arm_blocks, &unmatched_candidates, block);
360 // If the target candidates were exhaustive, then we are done.
361 if otherwise.is_empty() {
365 // If all candidates were sorted into `target_candidates` somewhere, then
366 // the initial set was inexhaustive.
367 let untested_candidates = unmatched_candidates.split_off(tested_candidates);
368 if untested_candidates.len() == 0 {
372 // Otherwise, let's process those remaining candidates.
373 let join_block = self.join_otherwise_blocks(otherwise);
374 self.match_candidates(span, arm_blocks, untested_candidates, join_block)
377 fn join_otherwise_blocks(&mut self,
378 otherwise: Vec<BasicBlock>)
381 if otherwise.len() == 1 {
384 let join_block = self.cfg.start_new_block();
385 for block in otherwise {
386 self.cfg.terminate(block, Terminator::Goto { target: join_block });
392 /// This is the most subtle part of the matching algorithm. At
393 /// this point, the input candidates have been fully simplified,
394 /// and so we know that all remaining match-pairs require some
395 /// sort of test. To decide what test to do, we take the highest
396 /// priority candidate (last one in the list) and extract the
397 /// first match-pair from the list. From this we decide what kind
398 /// of test is needed using `test`, defined in the `test` module.
400 /// *Note:* taking the first match pair is somewhat arbitrary, and
401 /// we might do better here by choosing more carefully what to
404 /// For example, consider the following possible match-pairs:
406 /// 1. `x @ Some(P)` -- we will do a `Switch` to decide what variant `x` has
407 /// 2. `x @ 22` -- we will do a `SwitchInt`
408 /// 3. `x @ 3..5` -- we will do a range test
411 /// Once we know what sort of test we are going to perform, this
412 /// test may also help us with other candidates. So we walk over
413 /// the candidates (from high to low priority) and check. This
414 /// gives us, for each outcome of the test, a transformed list of
415 /// candidates. For example, if we are testing the current
416 /// variant of `x.0`, and we have a candidate `{x.0 @ Some(v), x.1
417 /// @ 22}`, then we would have a resulting candidate of `{(x.0 as
418 /// Some).0 @ v, x.1 @ 22}`. Note that the first match-pair is now
419 /// simpler (and, in fact, irrefutable).
421 /// But there may also be candidates that the test just doesn't
422 /// apply to. For example, consider the case of #29740:
433 /// Here the match-pair we are testing will be `x @ "foo"`, and we
434 /// will generate an `Eq` test. Because `"bar"` and `"baz"` are different
435 /// constants, we will decide that these later candidates are just not
436 /// informed by the eq test. So we'll wind up with three candidate sets:
438 /// - If outcome is that `x == "foo"` (one candidate, derived from `x @ "foo"`)
439 /// - If outcome is that `x != "foo"` (empty list of candidates)
440 /// - Otherwise (three candidates, `x @ "bar"`, `x @ "baz"`, `x @
441 /// _`). Here we have the invariant that everything in the
442 /// otherwise list is of **lower priority** than the stuff in the
445 /// So we'll compile the test. For each outcome of the test, we
446 /// recursively call `match_candidates` with the corresponding set
447 /// of candidates. But note that this set is now inexhaustive: for
448 /// example, in the case where the test returns false, there are
449 /// NO candidates, even though there is stll a value to be
450 /// matched. So we'll collect the return values from
451 /// `match_candidates`, which are the blocks where control-flow
452 /// goes if none of the candidates matched. At this point, we can
453 /// continue with the "otherwise" list.
455 /// If you apply this to the above test, you basically wind up
456 /// with an if-else-if chain, testing each candidate in turn,
457 /// which is precisely what we want.
458 fn test_candidates<'pat>(&mut self,
460 arm_blocks: &mut ArmBlocks,
461 candidates: &[Candidate<'pat, 'tcx>],
463 -> (Vec<BasicBlock>, usize)
465 // extract the match-pair from the highest priority candidate
466 let match_pair = &candidates.first().unwrap().match_pairs[0];
467 let mut test = self.test(match_pair);
469 // most of the time, the test to perform is simply a function
470 // of the main candidate; but for a test like SwitchInt, we
471 // may want to add cases based on the candidates that are
474 TestKind::SwitchInt { switch_ty, ref mut options, ref mut indices } => {
475 for candidate in candidates.iter() {
476 if !self.add_cases_to_switch(&match_pair.lvalue,
488 // perform the test, branching to one of N blocks. For each of
489 // those N possible outcomes, create a (initially empty)
490 // vector of candidates. Those are the candidates that still
491 // apply if the test has that particular outcome.
492 debug!("match_candidates: test={:?} match_pair={:?}", test, match_pair);
493 let target_blocks = self.perform_test(block, &match_pair.lvalue, &test);
494 let mut target_candidates: Vec<_> = (0..target_blocks.len()).map(|_| vec![]).collect();
496 // Sort the candidates into the appropriate vector in
497 // `target_candidates`. Note that at some point we may
498 // encounter a candidate where the test is not relevant; at
499 // that point, we stop sorting.
500 let tested_candidates =
502 .take_while(|c| self.sort_candidate(&match_pair.lvalue,
505 &mut target_candidates))
507 assert!(tested_candidates > 0); // at least the last candidate ought to be tested
509 // For each outcome of test, process the candidates that still
510 // apply. Collect a list of blocks where control flow will
511 // branch if one of the `target_candidate` sets is not
513 let otherwise: Vec<_> =
514 target_blocks.into_iter()
515 .zip(target_candidates)
516 .flat_map(|(target_block, target_candidates)| {
517 self.match_candidates(span,
524 (otherwise, tested_candidates)
527 /// Initializes each of the bindings from the candidate by
528 /// moving/copying/ref'ing the source as appropriate. Tests the
529 /// guard, if any, and then branches to the arm. Returns the block
530 /// for the case where the guard fails.
532 /// Note: we check earlier that if there is a guard, there cannot
533 /// be move bindings. This isn't really important for the
534 /// self-consistency of this fn, but the reason for it should be
535 /// clear: after we've done the assignments, if there were move
536 /// bindings, further tests would be a use-after-move (which would
537 /// in turn be detected by the borrowck code that runs on the
539 fn bind_and_guard_matched_candidate<'pat>(&mut self,
540 mut block: BasicBlock,
541 arm_blocks: &mut ArmBlocks,
542 candidate: Candidate<'pat, 'tcx>)
543 -> Option<BasicBlock> {
544 debug!("bind_and_guard_matched_candidate(block={:?}, candidate={:?})",
547 debug_assert!(candidate.match_pairs.is_empty());
549 self.bind_matched_candidate(block, candidate.bindings);
551 let arm_block = arm_blocks.blocks[candidate.arm_index];
553 if let Some(guard) = candidate.guard {
554 // the block to branch to if the guard fails; if there is no
555 // guard, this block is simply unreachable
556 let cond = unpack!(block = self.as_operand(block, guard));
557 let otherwise = self.cfg.start_new_block();
558 self.cfg.terminate(block, Terminator::If { cond: cond,
559 targets: (arm_block, otherwise)});
562 self.cfg.terminate(block, Terminator::Goto { target: arm_block });
567 fn bind_matched_candidate(&mut self,
569 bindings: Vec<Binding<'tcx>>) {
570 debug!("bind_matched_candidate(block={:?}, bindings={:?})",
573 // Assign each of the bindings. This may trigger moves out of the candidate.
574 for binding in bindings {
575 // Find the variable for the `var_id` being bound. It
576 // should have been created by a previous call to
577 // `declare_bindings`.
578 let var_index = self.var_indices[&binding.var_id];
580 let rvalue = match binding.binding_mode {
581 BindingMode::ByValue =>
582 Rvalue::Use(Operand::Consume(binding.source)),
583 BindingMode::ByRef(region, borrow_kind) =>
584 Rvalue::Ref(region, borrow_kind, binding.source),
587 let scope_id = self.innermost_scope_id();
588 self.cfg.push_assign(block, scope_id, binding.span,
589 &Lvalue::Var(var_index), rvalue);
593 fn declare_binding(&mut self,
594 var_scope_id: ScopeId,
595 mutability: Mutability,
602 debug!("declare_binding(var_id={:?}, name={:?}, var_ty={:?}, var_scope_id={:?}, span={:?})",
603 var_id, name, var_ty, var_scope_id, span);
605 let index = self.var_decls.len();
606 self.var_decls.push(VarDecl::<'tcx> {
608 mutability: mutability,
613 let index = index as u32;
614 let extent = self.scope_auxiliary[var_scope_id.index()].extent;
615 self.schedule_drop(span, extent, &Lvalue::Var(index), var_ty);
616 self.var_indices.insert(var_id, index);
618 debug!("declare_binding: index={:?}", index);