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
.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 /// # let (x, y, z) = (true, true, true);
476 /// match (x, y, z) {
477 /// (true, _, true) => true, // (0)
478 /// (_, true, _) => true, // (1)
479 /// (false, false, _) => false, // (2)
480 /// (true, _, false) => false, // (3)
484 /// In that case, after we test on `x`, there are 2 overlapping candidate
487 /// - If the outcome is that `x` is true, candidates 0, 1, and 3
488 /// - If the outcome is that `x` is false, candidates 1 and 2
490 /// Here, the traditional "decision tree" method would generate 2
491 /// separate code-paths for the 2 separate cases.
493 /// In some cases, this duplication can create an exponential amount of
494 /// code. This is most easily seen by noticing that this method terminates
495 /// with precisely the reachable arms being reachable - but that problem
496 /// is trivially NP-complete:
499 /// match (var0, var1, var2, var3, ..) {
500 /// (true, _, _, false, true, ...) => false,
501 /// (_, true, true, false, _, ...) => false,
502 /// (false, _, false, false, _, ...) => false,
508 /// Here the last arm is reachable only if there is an assignment to
509 /// the variables that does not match any of the literals. Therefore,
510 /// compilation would take an exponential amount of time in some cases.
512 /// That kind of exponential worst-case might not occur in practice, but
513 /// our simplistic treatment of constants and guards would make it occur
514 /// in very common situations - for example #29740:
518 /// "foo" if foo_guard => ...,
519 /// "bar" if bar_guard => ...,
520 /// "baz" if baz_guard => ...,
525 /// Here we first test the match-pair `x @ "foo"`, which is an `Eq` test.
527 /// It might seem that we would end up with 2 disjoint candidate
528 /// sets, consisting of the first candidate or the other 3, but our
529 /// algorithm doesn't reason about "foo" being distinct from the other
530 /// constants; it considers the latter arms to potentially match after
531 /// both outcomes, which obviously leads to an exponential amount
534 /// To avoid these kinds of problems, our algorithm tries to ensure
535 /// the amount of generated tests is linear. When we do a k-way test,
536 /// we return an additional "unmatched" set alongside the obvious `k`
537 /// sets. When we encounter a candidate that would be present in more
538 /// than one of the sets, we put it and all candidates below it into the
539 /// "unmatched" set. This ensures these `k+1` sets are disjoint.
541 /// After we perform our test, we branch into the appropriate candidate
542 /// set and recurse with `match_candidates`. These sub-matches are
543 /// obviously inexhaustive - as we discarded our otherwise set - so
544 /// we set their continuation to do `match_candidates` on the
545 /// "unmatched" set (which is again inexhaustive).
547 /// If you apply this to the above test, you basically wind up
548 /// with an if-else-if chain, testing each candidate in turn,
549 /// which is precisely what we want.
551 /// In addition to avoiding exponential-time blowups, this algorithm
552 /// also has nice property that each guard and arm is only generated
554 fn test_candidates
<'pat
>(&mut self,
556 arm_blocks
: &mut ArmBlocks
,
557 candidates
: &[Candidate
<'pat
, 'tcx
>],
559 -> (Vec
<BasicBlock
>, usize)
561 // extract the match-pair from the highest priority candidate
562 let match_pair
= &candidates
.first().unwrap().match_pairs
[0];
563 let mut test
= self.test(match_pair
);
565 // most of the time, the test to perform is simply a function
566 // of the main candidate; but for a test like SwitchInt, we
567 // may want to add cases based on the candidates that are
570 TestKind
::SwitchInt { switch_ty, ref mut options, ref mut indices }
=> {
571 for candidate
in candidates
.iter() {
572 if !self.add_cases_to_switch(&match_pair
.lvalue
,
581 TestKind
::Switch { adt_def: _, ref mut variants}
=> {
582 for candidate
in candidates
.iter() {
583 if !self.add_variants_to_switch(&match_pair
.lvalue
,
593 // perform the test, branching to one of N blocks. For each of
594 // those N possible outcomes, create a (initially empty)
595 // vector of candidates. Those are the candidates that still
596 // apply if the test has that particular outcome.
597 debug
!("match_candidates: test={:?} match_pair={:?}", test
, match_pair
);
598 let target_blocks
= self.perform_test(block
, &match_pair
.lvalue
, &test
);
599 let mut target_candidates
: Vec
<_
> = (0..target_blocks
.len()).map(|_
| vec
![]).collect();
601 // Sort the candidates into the appropriate vector in
602 // `target_candidates`. Note that at some point we may
603 // encounter a candidate where the test is not relevant; at
604 // that point, we stop sorting.
605 let tested_candidates
=
607 .take_while(|c
| self.sort_candidate(&match_pair
.lvalue
,
610 &mut target_candidates
))
612 assert
!(tested_candidates
> 0); // at least the last candidate ought to be tested
613 debug
!("tested_candidates: {}", tested_candidates
);
614 debug
!("untested_candidates: {}", candidates
.len() - tested_candidates
);
616 // For each outcome of test, process the candidates that still
617 // apply. Collect a list of blocks where control flow will
618 // branch if one of the `target_candidate` sets is not
620 let otherwise
: Vec
<_
> =
621 target_blocks
.into_iter()
622 .zip(target_candidates
)
623 .flat_map(|(target_block
, target_candidates
)| {
624 self.match_candidates(span
,
631 (otherwise
, tested_candidates
)
634 /// Initializes each of the bindings from the candidate by
635 /// moving/copying/ref'ing the source as appropriate. Tests the
636 /// guard, if any, and then branches to the arm. Returns the block
637 /// for the case where the guard fails.
639 /// Note: we check earlier that if there is a guard, there cannot
640 /// be move bindings. This isn't really important for the
641 /// self-consistency of this fn, but the reason for it should be
642 /// clear: after we've done the assignments, if there were move
643 /// bindings, further tests would be a use-after-move (which would
644 /// in turn be detected by the borrowck code that runs on the
646 fn bind_and_guard_matched_candidate
<'pat
>(&mut self,
647 mut block
: BasicBlock
,
648 arm_blocks
: &mut ArmBlocks
,
649 candidate
: Candidate
<'pat
, 'tcx
>)
650 -> Option
<BasicBlock
> {
651 debug
!("bind_and_guard_matched_candidate(block={:?}, candidate={:?})",
654 debug_assert
!(candidate
.match_pairs
.is_empty());
656 self.bind_matched_candidate(block
, candidate
.bindings
);
658 let arm_block
= arm_blocks
.blocks
[candidate
.arm_index
];
660 if let Some(guard
) = candidate
.guard
{
661 // the block to branch to if the guard fails; if there is no
662 // guard, this block is simply unreachable
663 let guard
= self.hir
.mirror(guard
);
664 let source_info
= self.source_info(guard
.span
);
665 let cond
= unpack
!(block
= self.as_local_operand(block
, guard
));
666 let otherwise
= self.cfg
.start_new_block();
667 self.cfg
.terminate(block
, source_info
,
668 TerminatorKind
::if_(self.hir
.tcx(), cond
, arm_block
, otherwise
));
671 let source_info
= self.source_info(candidate
.span
);
672 self.cfg
.terminate(block
, source_info
,
673 TerminatorKind
::Goto { target: arm_block }
);
678 fn bind_matched_candidate(&mut self,
680 bindings
: Vec
<Binding
<'tcx
>>) {
681 debug
!("bind_matched_candidate(block={:?}, bindings={:?})",
684 // Assign each of the bindings. This may trigger moves out of the candidate.
685 for binding
in bindings
{
686 let source_info
= self.source_info(binding
.span
);
687 let local
= self.storage_live_binding(block
, binding
.var_id
, binding
.span
);
688 self.schedule_drop_for_binding(binding
.var_id
, binding
.span
);
689 let rvalue
= match binding
.binding_mode
{
690 BindingMode
::ByValue
=>
691 Rvalue
::Use(Operand
::Consume(binding
.source
)),
692 BindingMode
::ByRef(region
, borrow_kind
) =>
693 Rvalue
::Ref(region
, borrow_kind
, binding
.source
),
695 self.cfg
.push_assign(block
, source_info
, &local
, rvalue
);
699 fn declare_binding(&mut self,
700 source_info
: SourceInfo
,
701 mutability
: Mutability
,
707 debug
!("declare_binding(var_id={:?}, name={:?}, var_ty={:?}, source_info={:?})",
708 var_id
, name
, var_ty
, source_info
);
710 let var
= self.local_decls
.push(LocalDecl
::<'tcx
> {
711 mutability
: mutability
,
714 source_info
: source_info
,
715 is_user_variable
: true,
717 self.var_indices
.insert(var_id
, var
);
719 debug
!("declare_binding: var={:?}", var
);