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::fx::FxHashMap;
18 use rustc_data_structures::bitvec::BitVector;
19 use rustc::middle::const_val::ConstVal;
20 use rustc::ty::{AdtDef, Ty};
24 use syntax::ast::{Name, NodeId};
27 // helper functions, broken out by category:
32 impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> {
33 pub fn match_expr(&mut self,
34 destination: &Lvalue<'tcx>,
36 mut block: BasicBlock,
37 discriminant: ExprRef<'tcx>,
40 let discriminant_lvalue = unpack!(block = self.as_lvalue(block, discriminant));
42 let mut arm_blocks = ArmBlocks {
44 .map(|_| self.cfg.start_new_block())
48 // Get the arm bodies and their scopes, while declaring bindings.
49 let arm_bodies: Vec<_> = arms.iter().map(|arm| {
50 let body = self.hir.mirror(arm.body.clone());
51 let scope = self.declare_bindings(None, body.span, &arm.patterns[0]);
52 (body, scope.unwrap_or(self.visibility_scope))
55 // assemble a list of candidates: there is one candidate per
56 // pattern, which means there may be more than one candidate
57 // *per arm*. These candidates are kept sorted such that the
58 // highest priority candidate comes first in the list.
59 // (i.e. same order as in source)
60 let candidates: Vec<_> =
63 .flat_map(|(arm_index, arm)| {
65 .map(move |pat| (arm_index, pat, arm.guard.clone()))
67 .map(|(arm_index, pattern, guard)| {
70 match_pairs: vec![MatchPair::new(discriminant_lvalue.clone(), pattern)],
78 // this will generate code to test discriminant_lvalue and
79 // branch to the appropriate arm block
80 let otherwise = self.match_candidates(span, &mut arm_blocks, candidates, block);
82 if !otherwise.is_empty() {
83 // All matches are exhaustive. However, because some matches
84 // only have exponentially-large exhaustive decision trees, we
85 // sometimes generate an inexhaustive decision tree.
87 // In that case, the inexhaustive tips of the decision tree
88 // can't be reached - terminate them with an `unreachable`.
89 let source_info = self.source_info(span);
91 let mut otherwise = otherwise;
93 otherwise.dedup(); // variant switches can introduce duplicate target blocks
94 for block in otherwise {
95 self.cfg.terminate(block, source_info, TerminatorKind::Unreachable);
99 // all the arm blocks will rejoin here
100 let end_block = self.cfg.start_new_block();
102 let outer_source_info = self.source_info(span);
103 for (arm_index, (body, visibility_scope)) in arm_bodies.into_iter().enumerate() {
104 let mut arm_block = arm_blocks.blocks[arm_index];
105 // Re-enter the visibility scope we created the bindings in.
106 self.visibility_scope = visibility_scope;
107 unpack!(arm_block = self.into(destination, arm_block, body));
108 self.cfg.terminate(arm_block, outer_source_info,
109 TerminatorKind::Goto { target: end_block });
111 self.visibility_scope = outer_source_info.scope;
116 pub fn expr_into_pattern(&mut self,
117 mut block: BasicBlock,
118 irrefutable_pat: Pattern<'tcx>,
119 initializer: ExprRef<'tcx>)
121 // optimize the case of `let x = ...`
122 match *irrefutable_pat.kind {
123 PatternKind::Binding { mode: BindingMode::ByValue,
125 subpattern: None, .. } => {
126 let lvalue = self.storage_live_binding(block, var, irrefutable_pat.span);
127 unpack!(block = self.into(&lvalue, block, initializer));
128 self.schedule_drop_for_binding(var, irrefutable_pat.span);
132 let lvalue = unpack!(block = self.as_lvalue(block, initializer));
133 self.lvalue_into_pattern(block, irrefutable_pat, &lvalue)
138 pub fn lvalue_into_pattern(&mut self,
139 mut block: BasicBlock,
140 irrefutable_pat: Pattern<'tcx>,
141 initializer: &Lvalue<'tcx>)
143 // create a dummy candidate
144 let mut candidate = Candidate {
145 span: irrefutable_pat.span,
146 match_pairs: vec![MatchPair::new(initializer.clone(), &irrefutable_pat)],
149 arm_index: 0, // since we don't call `match_candidates`, this field is unused
152 // Simplify the candidate. Since the pattern is irrefutable, this should
153 // always convert all match-pairs into bindings.
154 unpack!(block = self.simplify_candidate(block, &mut candidate));
156 if !candidate.match_pairs.is_empty() {
157 span_bug!(candidate.match_pairs[0].pattern.span,
158 "match pairs {:?} remaining after simplifying \
159 irrefutable pattern",
160 candidate.match_pairs);
163 // now apply the bindings, which will also declare the variables
164 self.bind_matched_candidate(block, candidate.bindings);
169 /// Declares the bindings of the given pattern and returns the visibility scope
170 /// for the bindings in this patterns, if such a scope had to be created.
171 /// NOTE: Declaring the bindings should always be done in their drop scope.
172 pub fn declare_bindings(&mut self,
173 mut var_scope: Option<VisibilityScope>,
175 pattern: &Pattern<'tcx>)
176 -> Option<VisibilityScope> {
177 self.visit_bindings(pattern, &mut |this, mutability, name, var, span, ty| {
178 if var_scope.is_none() {
179 var_scope = Some(this.new_visibility_scope(scope_span));
181 let source_info = SourceInfo {
183 scope: var_scope.unwrap()
185 this.declare_binding(source_info, mutability, name, var, ty);
190 pub fn storage_live_binding(&mut self, block: BasicBlock, var: NodeId, span: Span)
193 let local_id = self.var_indices[&var];
194 let source_info = self.source_info(span);
195 self.cfg.push(block, Statement {
196 source_info: source_info,
197 kind: StatementKind::StorageLive(Lvalue::Local(local_id))
199 Lvalue::Local(local_id)
202 pub fn schedule_drop_for_binding(&mut self, var: NodeId, span: Span) {
203 let local_id = self.var_indices[&var];
204 let var_ty = self.local_decls[local_id].ty;
205 let extent = self.hir.tcx().region_maps().var_scope(var);
206 self.schedule_drop(span, extent, &Lvalue::Local(local_id), var_ty);
209 pub fn visit_bindings<F>(&mut self, pattern: &Pattern<'tcx>, mut f: &mut F)
210 where F: FnMut(&mut Self, Mutability, Name, NodeId, Span, Ty<'tcx>)
212 match *pattern.kind {
213 PatternKind::Binding { mutability, name, var, ty, ref subpattern, .. } => {
214 f(self, mutability, name, var, pattern.span, ty);
215 if let Some(subpattern) = subpattern.as_ref() {
216 self.visit_bindings(subpattern, f);
219 PatternKind::Array { ref prefix, ref slice, ref suffix } |
220 PatternKind::Slice { ref prefix, ref slice, ref suffix } => {
221 for subpattern in prefix.iter().chain(slice).chain(suffix) {
222 self.visit_bindings(subpattern, f);
225 PatternKind::Constant { .. } | PatternKind::Range { .. } | PatternKind::Wild => {
227 PatternKind::Deref { ref subpattern } => {
228 self.visit_bindings(subpattern, f);
230 PatternKind::Leaf { ref subpatterns } |
231 PatternKind::Variant { ref subpatterns, .. } => {
232 for subpattern in subpatterns {
233 self.visit_bindings(&subpattern.pattern, f);
241 /// List of blocks for each arm (and potentially other metadata in the
244 blocks: Vec<BasicBlock>,
247 #[derive(Clone, Debug)]
248 pub struct Candidate<'pat, 'tcx:'pat> {
249 // span of the original pattern that gave rise to this candidate
252 // all of these must be satisfied...
253 match_pairs: Vec<MatchPair<'pat, 'tcx>>,
255 // ...these bindings established...
256 bindings: Vec<Binding<'tcx>>,
258 // ...and the guard must be evaluated...
259 guard: Option<ExprRef<'tcx>>,
261 // ...and then we branch to arm with this index.
265 #[derive(Clone, Debug)]
266 struct Binding<'tcx> {
268 source: Lvalue<'tcx>,
272 mutability: Mutability,
273 binding_mode: BindingMode<'tcx>,
276 #[derive(Clone, Debug)]
277 pub struct MatchPair<'pat, 'tcx:'pat> {
279 lvalue: Lvalue<'tcx>,
281 // ... must match this pattern.
282 pattern: &'pat Pattern<'tcx>,
284 // HACK(eddyb) This is used to toggle whether a Slice pattern
285 // has had its length checked. This is only necessary because
286 // the "rest" part of the pattern right now has type &[T] and
287 // as such, it requires an Rvalue::Slice to be generated.
288 // See RFC 495 / issue #23121 for the eventual (proper) solution.
289 slice_len_checked: bool
292 #[derive(Clone, Debug, PartialEq)]
293 enum TestKind<'tcx> {
294 // test the branches of enum
296 adt_def: &'tcx AdtDef,
300 // test the branches of enum
303 options: Vec<ConstVal<'tcx>>,
304 indices: FxHashMap<ConstVal<'tcx>, usize>,
309 value: ConstVal<'tcx>,
313 // test whether the value falls within an inclusive or exclusive range
321 // test length of the slice is equal to len
329 pub struct Test<'tcx> {
331 kind: TestKind<'tcx>,
334 ///////////////////////////////////////////////////////////////////////////
335 // Main matching algorithm
337 impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> {
338 /// The main match algorithm. It begins with a set of candidates
339 /// `candidates` and has the job of generating code to determine
340 /// which of these candidates, if any, is the correct one. The
341 /// candidates are sorted such that the first item in the list
342 /// has the highest priority. When a candidate is found to match
343 /// the value, we will generate a branch to the appropriate
344 /// block found in `arm_blocks`.
346 /// The return value is a list of "otherwise" blocks. These are
347 /// points in execution where we found that *NONE* of the
348 /// candidates apply. In principle, this means that the input
349 /// list was not exhaustive, though at present we sometimes are
350 /// not smart enough to recognize all exhaustive inputs.
352 /// It might be surprising that the input can be inexhaustive.
353 /// Indeed, initially, it is not, because all matches are
354 /// exhaustive in Rust. But during processing we sometimes divide
355 /// up the list of candidates and recurse with a non-exhaustive
356 /// list. This is important to keep the size of the generated code
357 /// under control. See `test_candidates` for more details.
358 fn match_candidates<'pat>(&mut self,
360 arm_blocks: &mut ArmBlocks,
361 mut candidates: Vec<Candidate<'pat, 'tcx>>,
362 mut block: BasicBlock)
365 debug!("matched_candidate(span={:?}, block={:?}, candidates={:?})",
366 span, block, candidates);
368 // Start by simplifying candidates. Once this process is
369 // complete, all the match pairs which remain require some
370 // form of test, whether it be a switch or pattern comparison.
371 for candidate in &mut candidates {
372 unpack!(block = self.simplify_candidate(block, candidate));
375 // The candidates are sorted by priority. Check to see
376 // whether the higher priority candidates (and hence at
377 // the front of the vec) have satisfied all their match
380 candidates.iter().take_while(|c| c.match_pairs.is_empty()).count();
381 debug!("match_candidates: {:?} candidates fully matched", fully_matched);
382 let mut unmatched_candidates = candidates.split_off(fully_matched);
383 for candidate in candidates {
384 // If so, apply any bindings, test the guard (if any), and
385 // branch to the arm.
386 if let Some(b) = self.bind_and_guard_matched_candidate(block, arm_blocks, candidate) {
389 // if None is returned, then any remaining candidates
390 // are unreachable (at least not through this path).
395 // If there are no candidates that still need testing, we're done.
396 // Since all matches are exhaustive, execution should never reach this point.
397 if unmatched_candidates.is_empty() {
401 // Test candidates where possible.
402 let (otherwise, tested_candidates) =
403 self.test_candidates(span, arm_blocks, &unmatched_candidates, block);
405 // If the target candidates were exhaustive, then we are done.
406 if otherwise.is_empty() {
410 // If all candidates were sorted into `target_candidates` somewhere, then
411 // the initial set was inexhaustive.
412 let untested_candidates = unmatched_candidates.split_off(tested_candidates);
413 if untested_candidates.len() == 0 {
417 // Otherwise, let's process those remaining candidates.
418 let join_block = self.join_otherwise_blocks(span, otherwise);
419 self.match_candidates(span, arm_blocks, untested_candidates, join_block)
422 fn join_otherwise_blocks(&mut self,
424 mut otherwise: Vec<BasicBlock>)
427 let source_info = self.source_info(span);
429 otherwise.dedup(); // variant switches can introduce duplicate target blocks
430 if otherwise.len() == 1 {
433 let join_block = self.cfg.start_new_block();
434 for block in otherwise {
435 self.cfg.terminate(block, source_info,
436 TerminatorKind::Goto { target: join_block });
442 /// This is the most subtle part of the matching algorithm. At
443 /// this point, the input candidates have been fully simplified,
444 /// and so we know that all remaining match-pairs require some
445 /// sort of test. To decide what test to do, we take the highest
446 /// priority candidate (last one in the list) and extract the
447 /// first match-pair from the list. From this we decide what kind
448 /// of test is needed using `test`, defined in the `test` module.
450 /// *Note:* taking the first match pair is somewhat arbitrary, and
451 /// we might do better here by choosing more carefully what to
454 /// For example, consider the following possible match-pairs:
456 /// 1. `x @ Some(P)` -- we will do a `Switch` to decide what variant `x` has
457 /// 2. `x @ 22` -- we will do a `SwitchInt`
458 /// 3. `x @ 3..5` -- we will do a range test
461 /// Once we know what sort of test we are going to perform, this
462 /// test may also help us with other candidates. So we walk over
463 /// the candidates (from high to low priority) and check. This
464 /// gives us, for each outcome of the test, a transformed list of
465 /// candidates. For example, if we are testing the current
466 /// variant of `x.0`, and we have a candidate `{x.0 @ Some(v), x.1
467 /// @ 22}`, then we would have a resulting candidate of `{(x.0 as
468 /// Some).0 @ v, x.1 @ 22}`. Note that the first match-pair is now
469 /// simpler (and, in fact, irrefutable).
471 /// But there may also be candidates that the test just doesn't
472 /// apply to. The classical example involves wildcards:
475 /// match (x, y, z) {
476 /// (true, _, true) => true, // (0)
477 /// (_, true, _) => true, // (1)
478 /// (false, false, _) => false, // (2)
479 /// (true, _, false) => false, // (3)
483 /// In that case, after we test on `x`, there are 2 overlapping candidate
486 /// - If the outcome is that `x` is true, candidates 0, 1, and 3
487 /// - If the outcome is that `x` is false, candidates 1 and 2
489 /// Here, the traditional "decision tree" method would generate 2
490 /// separate code-paths for the 2 separate cases.
492 /// In some cases, this duplication can create an exponential amount of
493 /// code. This is most easily seen by noticing that this method terminates
494 /// with precisely the reachable arms being reachable - but that problem
495 /// is trivially NP-complete:
498 /// match (var0, var1, var2, var3, ..) {
499 /// (true, _, _, false, true, ...) => false,
500 /// (_, true, true, false, _, ...) => false,
501 /// (false, _, false, false, _, ...) => false,
507 /// Here the last arm is reachable only if there is an assignment to
508 /// the variables that does not match any of the literals. Therefore,
509 /// compilation would take an exponential amount of time in some cases.
511 /// That kind of exponential worst-case might not occur in practice, but
512 /// our simplistic treatment of constants and guards would make it occur
513 /// in very common situations - for example #29740:
517 /// "foo" if foo_guard => ...,
518 /// "bar" if bar_guard => ...,
519 /// "baz" if baz_guard => ...,
524 /// Here we first test the match-pair `x @ "foo"`, which is an `Eq` test.
526 /// It might seem that we would end up with 2 disjoint candidate
527 /// sets, consisting of the first candidate or the other 3, but our
528 /// algorithm doesn't reason about "foo" being distinct from the other
529 /// constants; it considers the latter arms to potentially match after
530 /// both outcomes, which obviously leads to an exponential amount
533 /// To avoid these kinds of problems, our algorithm tries to ensure
534 /// the amount of generated tests is linear. When we do a k-way test,
535 /// we return an additional "unmatched" set alongside the obvious `k`
536 /// sets. When we encounter a candidate that would be present in more
537 /// than one of the sets, we put it and all candidates below it into the
538 /// "unmatched" set. This ensures these `k+1` sets are disjoint.
540 /// After we perform our test, we branch into the appropriate candidate
541 /// set and recurse with `match_candidates`. These sub-matches are
542 /// obviously inexhaustive - as we discarded our otherwise set - so
543 /// we set their continuation to do `match_candidates` on the
544 /// "unmatched" set (which is again inexhaustive).
546 /// If you apply this to the above test, you basically wind up
547 /// with an if-else-if chain, testing each candidate in turn,
548 /// which is precisely what we want.
550 /// In addition to avoiding exponential-time blowups, this algorithm
551 /// also has nice property that each guard and arm is only generated
553 fn test_candidates<'pat>(&mut self,
555 arm_blocks: &mut ArmBlocks,
556 candidates: &[Candidate<'pat, 'tcx>],
558 -> (Vec<BasicBlock>, usize)
560 // extract the match-pair from the highest priority candidate
561 let match_pair = &candidates.first().unwrap().match_pairs[0];
562 let mut test = self.test(match_pair);
564 // most of the time, the test to perform is simply a function
565 // of the main candidate; but for a test like SwitchInt, we
566 // may want to add cases based on the candidates that are
569 TestKind::SwitchInt { switch_ty, ref mut options, ref mut indices } => {
570 for candidate in candidates.iter() {
571 if !self.add_cases_to_switch(&match_pair.lvalue,
580 TestKind::Switch { adt_def: _, ref mut variants} => {
581 for candidate in candidates.iter() {
582 if !self.add_variants_to_switch(&match_pair.lvalue,
592 // perform the test, branching to one of N blocks. For each of
593 // those N possible outcomes, create a (initially empty)
594 // vector of candidates. Those are the candidates that still
595 // apply if the test has that particular outcome.
596 debug!("match_candidates: test={:?} match_pair={:?}", test, match_pair);
597 let target_blocks = self.perform_test(block, &match_pair.lvalue, &test);
598 let mut target_candidates: Vec<_> = (0..target_blocks.len()).map(|_| vec![]).collect();
600 // Sort the candidates into the appropriate vector in
601 // `target_candidates`. Note that at some point we may
602 // encounter a candidate where the test is not relevant; at
603 // that point, we stop sorting.
604 let tested_candidates =
606 .take_while(|c| self.sort_candidate(&match_pair.lvalue,
609 &mut target_candidates))
611 assert!(tested_candidates > 0); // at least the last candidate ought to be tested
612 debug!("tested_candidates: {}", tested_candidates);
613 debug!("untested_candidates: {}", candidates.len() - tested_candidates);
615 // For each outcome of test, process the candidates that still
616 // apply. Collect a list of blocks where control flow will
617 // branch if one of the `target_candidate` sets is not
619 let otherwise: Vec<_> =
620 target_blocks.into_iter()
621 .zip(target_candidates)
622 .flat_map(|(target_block, target_candidates)| {
623 self.match_candidates(span,
630 (otherwise, tested_candidates)
633 /// Initializes each of the bindings from the candidate by
634 /// moving/copying/ref'ing the source as appropriate. Tests the
635 /// guard, if any, and then branches to the arm. Returns the block
636 /// for the case where the guard fails.
638 /// Note: we check earlier that if there is a guard, there cannot
639 /// be move bindings. This isn't really important for the
640 /// self-consistency of this fn, but the reason for it should be
641 /// clear: after we've done the assignments, if there were move
642 /// bindings, further tests would be a use-after-move (which would
643 /// in turn be detected by the borrowck code that runs on the
645 fn bind_and_guard_matched_candidate<'pat>(&mut self,
646 mut block: BasicBlock,
647 arm_blocks: &mut ArmBlocks,
648 candidate: Candidate<'pat, 'tcx>)
649 -> Option<BasicBlock> {
650 debug!("bind_and_guard_matched_candidate(block={:?}, candidate={:?})",
653 debug_assert!(candidate.match_pairs.is_empty());
655 self.bind_matched_candidate(block, candidate.bindings);
657 let arm_block = arm_blocks.blocks[candidate.arm_index];
659 if let Some(guard) = candidate.guard {
660 // the block to branch to if the guard fails; if there is no
661 // guard, this block is simply unreachable
662 let guard = self.hir.mirror(guard);
663 let source_info = self.source_info(guard.span);
664 let cond = unpack!(block = self.as_local_operand(block, guard));
665 let otherwise = self.cfg.start_new_block();
666 self.cfg.terminate(block, source_info,
667 TerminatorKind::if_(self.hir.tcx(), cond, arm_block, otherwise));
670 let source_info = self.source_info(candidate.span);
671 self.cfg.terminate(block, source_info,
672 TerminatorKind::Goto { target: arm_block });
677 fn bind_matched_candidate(&mut self,
679 bindings: Vec<Binding<'tcx>>) {
680 debug!("bind_matched_candidate(block={:?}, bindings={:?})",
683 // Assign each of the bindings. This may trigger moves out of the candidate.
684 for binding in bindings {
685 let source_info = self.source_info(binding.span);
686 let local = self.storage_live_binding(block, binding.var_id, binding.span);
687 self.schedule_drop_for_binding(binding.var_id, binding.span);
688 let rvalue = match binding.binding_mode {
689 BindingMode::ByValue =>
690 Rvalue::Use(Operand::Consume(binding.source)),
691 BindingMode::ByRef(region, borrow_kind) =>
692 Rvalue::Ref(region, borrow_kind, binding.source),
694 self.cfg.push_assign(block, source_info, &local, rvalue);
698 fn declare_binding(&mut self,
699 source_info: SourceInfo,
700 mutability: Mutability,
706 debug!("declare_binding(var_id={:?}, name={:?}, var_ty={:?}, source_info={:?})",
707 var_id, name, var_ty, source_info);
709 let var = self.local_decls.push(LocalDecl::<'tcx> {
710 mutability: mutability,
713 source_info: source_info,
714 is_user_variable: true,
716 self.var_indices.insert(var_id, var);
718 debug!("declare_binding: var={:?}", var);