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, Builder};
18 use rustc_data_structures::fnv::FnvHashMap;
19 use rustc::middle::const_eval::ConstVal;
20 use rustc::middle::region::CodeExtent;
21 use rustc::middle::ty::{AdtDef, Ty};
23 use syntax::ast::{Name, NodeId};
24 use syntax::codemap::Span;
26 // helper functions, broken out by category:
31 impl<'a,'tcx> Builder<'a,'tcx> {
32 pub fn match_expr(&mut self,
33 destination: &Lvalue<'tcx>,
35 mut block: BasicBlock,
36 discriminant: ExprRef<'tcx>,
39 let discriminant_lvalue = unpack!(block = self.as_lvalue(block, discriminant));
41 // Before we do anything, create uninitialized variables with
42 // suitable extent for all of the bindings in this match. It's
43 // easiest to do this up front because some of these arms may
44 // be unreachable or reachable multiple times.
45 let var_extent = self.extent_of_innermost_scope().unwrap();
47 self.declare_bindings(var_extent, &arm.patterns[0]);
50 let mut arm_blocks = ArmBlocks {
52 .map(|_| self.cfg.start_new_block())
56 let arm_bodies: Vec<ExprRef<'tcx>> =
58 .map(|arm| arm.body.clone())
61 // assemble a list of candidates: there is one candidate per
62 // pattern, which means there may be more than one candidate
63 // *per arm*. These candidates are kept sorted such that the
64 // highest priority candidate comes last in the list. This the
65 // reverse of the order in which candidates are written in the
67 let candidates: Vec<_> =
70 .rev() // highest priority comes last
71 .flat_map(|(arm_index, arm)| {
74 .map(move |pat| (arm_index, pat, arm.guard.clone()))
76 .map(|(arm_index, pattern, guard)| {
78 match_pairs: vec![MatchPair::new(discriminant_lvalue.clone(), pattern)],
86 // this will generate code to test discriminant_lvalue and
87 // branch to the appropriate arm block
88 let otherwise = self.match_candidates(span, &mut arm_blocks, candidates, block);
90 // because all matches are exhaustive, in principle we expect
91 // an empty vector to be returned here, but the algorithm is
92 // not entirely precise
93 if !otherwise.is_empty() {
94 let join_block = self.join_otherwise_blocks(otherwise);
95 self.panic(join_block);
98 // all the arm blocks will rejoin here
99 let end_block = self.cfg.start_new_block();
101 for (arm_index, arm_body) in arm_bodies.into_iter().enumerate() {
102 let mut arm_block = arm_blocks.blocks[arm_index];
103 unpack!(arm_block = self.into(destination, arm_block, arm_body));
104 self.cfg.terminate(arm_block, Terminator::Goto { target: end_block });
110 pub fn expr_into_pattern(&mut self,
111 mut block: BasicBlock,
112 var_extent: CodeExtent, // lifetime of vars
113 irrefutable_pat: Pattern<'tcx>,
114 initializer: ExprRef<'tcx>)
116 // optimize the case of `let x = ...`
117 match *irrefutable_pat.kind {
118 PatternKind::Binding { mutability,
120 mode: BindingMode::ByValue,
123 subpattern: None } => {
124 let index = self.declare_binding(var_extent,
129 irrefutable_pat.span);
130 let lvalue = Lvalue::Var(index);
131 return self.into(&lvalue, block, initializer);
135 let lvalue = unpack!(block = self.as_lvalue(block, initializer));
136 self.lvalue_into_pattern(block,
142 pub fn lvalue_into_pattern(&mut self,
143 mut block: BasicBlock,
144 var_extent: CodeExtent,
145 irrefutable_pat: Pattern<'tcx>,
146 initializer: &Lvalue<'tcx>)
148 // first, creating the bindings
149 self.declare_bindings(var_extent, &irrefutable_pat);
151 // create a dummy candidate
152 let mut candidate = Candidate {
153 match_pairs: vec![MatchPair::new(initializer.clone(), &irrefutable_pat)],
156 arm_index: 0, // since we don't call `match_candidates`, this field is unused
159 // Simplify the candidate. Since the pattern is irrefutable, this should
160 // always convert all match-pairs into bindings.
161 unpack!(block = self.simplify_candidate(block, &mut candidate));
163 if !candidate.match_pairs.is_empty() {
164 self.hir.span_bug(candidate.match_pairs[0].pattern.span,
165 &format!("match pairs {:?} remaining after simplifying \
166 irrefutable pattern",
167 candidate.match_pairs));
170 // now apply the bindings, which will also declare the variables
171 self.bind_matched_candidate(block, candidate.bindings);
176 pub fn declare_bindings(&mut self, var_extent: CodeExtent, pattern: &Pattern<'tcx>) {
177 match *pattern.kind {
178 PatternKind::Binding { mutability, name, mode: _, var, ty, ref subpattern } => {
179 self.declare_binding(var_extent, mutability, name, var, ty, pattern.span);
180 if let Some(subpattern) = subpattern.as_ref() {
181 self.declare_bindings(var_extent, subpattern);
184 PatternKind::Array { ref prefix, ref slice, ref suffix } |
185 PatternKind::Slice { ref prefix, ref slice, ref suffix } => {
186 for subpattern in prefix.iter().chain(slice).chain(suffix) {
187 self.declare_bindings(var_extent, subpattern);
190 PatternKind::Constant { .. } | PatternKind::Range { .. } | PatternKind::Wild => {
192 PatternKind::Deref { ref subpattern } => {
193 self.declare_bindings(var_extent, subpattern);
195 PatternKind::Leaf { ref subpatterns } |
196 PatternKind::Variant { ref subpatterns, .. } => {
197 for subpattern in subpatterns {
198 self.declare_bindings(var_extent, &subpattern.pattern);
205 /// List of blocks for each arm (and potentially other metadata in the
208 blocks: Vec<BasicBlock>,
211 #[derive(Clone, Debug)]
212 struct Candidate<'pat, 'tcx:'pat> {
213 // all of these must be satisfied...
214 match_pairs: Vec<MatchPair<'pat, 'tcx>>,
216 // ...these bindings established...
217 bindings: Vec<Binding<'tcx>>,
219 // ...and the guard must be evaluated...
220 guard: Option<ExprRef<'tcx>>,
222 // ...and then we branch to arm with this index.
226 #[derive(Clone, Debug)]
227 struct Binding<'tcx> {
229 source: Lvalue<'tcx>,
233 mutability: Mutability,
234 binding_mode: BindingMode,
237 #[derive(Clone, Debug)]
238 struct MatchPair<'pat, 'tcx:'pat> {
240 lvalue: Lvalue<'tcx>,
242 // ... must match this pattern.
243 pattern: &'pat Pattern<'tcx>,
246 #[derive(Clone, Debug, PartialEq)]
247 enum TestKind<'tcx> {
248 // test the branches of enum
250 adt_def: AdtDef<'tcx>,
253 // test the branches of enum
256 options: Vec<ConstVal>,
257 indices: FnvHashMap<ConstVal, usize>,
262 value: Literal<'tcx>,
266 // test whether the value falls within an inclusive range
273 // test length of the slice is equal to len
283 kind: TestKind<'tcx>,
286 ///////////////////////////////////////////////////////////////////////////
287 // Main matching algorithm
289 impl<'a,'tcx> Builder<'a,'tcx> {
290 /// The main match algorithm. It begins with a set of candidates
291 /// `candidates` and has the job of generating code to determine
292 /// which of these candidates, if any, is the correct one. The
293 /// candidates are sorted in inverse priority -- so the last item
294 /// in the list has highest priority. When a candidate is found to
295 /// match the value, we will generate a branch to the appropriate
296 /// block found in `arm_blocks`.
298 /// The return value is a list of "otherwise" blocks. These are
299 /// points in execution where we found that *NONE* of the
300 /// candidates apply. In principle, this means that the input
301 /// list was not exhaustive, though at present we sometimes are
302 /// not smart enough to recognize all exhaustive inputs.
304 /// It might be surprising that the input can be inexhaustive.
305 /// Indeed, initially, it is not, because all matches are
306 /// exhaustive in Rust. But during processing we sometimes divide
307 /// up the list of candidates and recurse with a non-exhaustive
308 /// list. This is important to keep the size of the generated code
309 /// under control. See `test_candidates` for more details.
310 fn match_candidates<'pat>(&mut self,
312 arm_blocks: &mut ArmBlocks,
313 mut candidates: Vec<Candidate<'pat, 'tcx>>,
314 mut block: BasicBlock)
317 debug!("matched_candidate(span={:?}, block={:?}, candidates={:?})",
318 span, block, candidates);
320 // Start by simplifying candidates. Once this process is
321 // complete, all the match pairs which remain require some
322 // form of test, whether it be a switch or pattern comparison.
323 for candidate in &mut candidates {
324 unpack!(block = self.simplify_candidate(block, candidate));
327 // The candidates are inversely sorted by priority. Check to
328 // see whether the candidates in the front of the queue (and
329 // hence back of the vec) have satisfied all their match
332 candidates.iter().rev().take_while(|c| c.match_pairs.is_empty()).count();
333 debug!("match_candidates: {:?} candidates fully matched", fully_matched);
334 for _ in 0..fully_matched {
335 // If so, apply any bindings, test the guard (if any), and
336 // branch to the arm.
337 let candidate = candidates.pop().unwrap();
338 if let Some(b) = self.bind_and_guard_matched_candidate(block, arm_blocks, candidate) {
341 // if None is returned, then any remaining candidates
342 // are unreachable (at least not through this path).
347 // If there are no candidates that still need testing, we're done.
348 // Since all matches are exhaustive, execution should never reach this point.
349 if candidates.is_empty() {
353 // Test candidates where possible.
354 let (otherwise, tested_candidates) =
355 self.test_candidates(span, arm_blocks, &candidates, block);
357 // If the target candidates were exhaustive, then we are done.
358 if otherwise.is_empty() {
362 // If all candidates were sorted into `target_candidates` somewhere, then
363 // the initial set was inexhaustive.
364 let untested_candidates = candidates.len() - tested_candidates;
365 if untested_candidates == 0 {
369 // Otherwise, let's process those remaining candidates.
370 let join_block = self.join_otherwise_blocks(otherwise);
371 candidates.truncate(untested_candidates);
372 self.match_candidates(span, arm_blocks, candidates, join_block)
375 fn join_otherwise_blocks(&mut self,
376 otherwise: Vec<BasicBlock>)
379 if otherwise.len() == 1 {
382 let join_block = self.cfg.start_new_block();
383 for block in otherwise {
384 self.cfg.terminate(block, Terminator::Goto { target: join_block });
390 /// This is the most subtle part of the matching algorithm. At
391 /// this point, the input candidates have been fully simplified,
392 /// and so we know that all remaining match-pairs require some
393 /// sort of test. To decide what test to do, we take the highest
394 /// priority candidate (last one in the list) and extract the
395 /// first match-pair from the list. From this we decide what kind
396 /// of test is needed using `test`, defined in the `test` module.
398 /// *Note:* taking the first match pair is somewhat arbitrary, and
399 /// we might do better here by choosing more carefully what to
402 /// For example, consider the following possible match-pairs:
404 /// 1. `x @ Some(P)` -- we will do a `Switch` to decide what variant `x` has
405 /// 2. `x @ 22` -- we will do a `SwitchInt`
406 /// 3. `x @ 3..5` -- we will do a range test
409 /// Once we know what sort of test we are going to perform, this
410 /// test may also help us with other candidates. So we walk over
411 /// the candidates (from high to low priority) and check. This
412 /// gives us, for each outcome of the test, a transformed list of
413 /// candidates. For example, if we are testing the current
414 /// variant of `x.0`, and we have a candidate `{x.0 @ Some(v), x.1
415 /// @ 22}`, then we would have a resulting candidate of `{(x.0 as
416 /// Some).0 @ v, x.1 @ 22}`. Note that the first match-pair is now
417 /// simpler (and, in fact, irrefutable).
419 /// But there may also be candidates that the test just doesn't
420 /// apply to. For example, consider the case of #29740:
431 /// Here the match-pair we are testing will be `x @ "foo"`, and we
432 /// will generate an `Eq` test. Because `"bar"` and `"baz"` are different
433 /// constants, we will decide that these later candidates are just not
434 /// informed by the eq test. So we'll wind up with three candidate sets:
436 /// - If outcome is that `x == "foo"` (one candidate, derived from `x @ "foo"`)
437 /// - If outcome is that `x != "foo"` (empty list of candidates)
438 /// - Otherwise (three candidates, `x @ "bar"`, `x @ "baz"`, `x @
439 /// _`). Here we have the invariant that everything in the
440 /// otherwise list is of **lower priority** than the stuff in the
443 /// So we'll compile the test. For each outcome of the test, we
444 /// recursively call `match_candidates` with the corresponding set
445 /// of candidates. But note that this set is now inexhaustive: for
446 /// example, in the case where the test returns false, there are
447 /// NO candidates, even though there is stll a value to be
448 /// matched. So we'll collect the return values from
449 /// `match_candidates`, which are the blocks where control-flow
450 /// goes if none of the candidates matched. At this point, we can
451 /// continue with the "otherwise" list.
453 /// If you apply this to the above test, you basically wind up
454 /// with an if-else-if chain, testing each candidate in turn,
455 /// which is precisely what we want.
456 fn test_candidates<'pat>(&mut self,
458 arm_blocks: &mut ArmBlocks,
459 candidates: &[Candidate<'pat, 'tcx>],
461 -> (Vec<BasicBlock>, usize)
463 // extract the match-pair from the highest priority candidate
464 let match_pair = &candidates.last().unwrap().match_pairs[0];
465 let mut test = self.test(match_pair);
467 // most of the time, the test to perform is simply a function
468 // of the main candidate; but for a test like SwitchInt, we
469 // may want to add cases based on the candidates that are
472 TestKind::SwitchInt { switch_ty, ref mut options, ref mut indices } => {
473 for candidate in candidates.iter().rev() {
474 if !self.add_cases_to_switch(&match_pair.lvalue,
486 // perform the test, branching to one of N blocks. For each of
487 // those N possible outcomes, create a (initially empty)
488 // vector of candidates. Those are the candidates that still
489 // apply if the test has that particular outcome.
490 debug!("match_candidates: test={:?} match_pair={:?}", test, match_pair);
491 let target_blocks = self.perform_test(block, &match_pair.lvalue, &test);
492 let mut target_candidates: Vec<_> = (0..target_blocks.len()).map(|_| vec![]).collect();
494 // Sort the candidates into the appropriate vector in
495 // `target_candidates`. Note that at some point we may
496 // encounter a candidate where the test is not relevant; at
497 // that point, we stop sorting.
498 let tested_candidates =
501 .take_while(|c| self.sort_candidate(&match_pair.lvalue,
504 &mut target_candidates))
506 assert!(tested_candidates > 0); // at least the last candidate ought to be tested
508 // For each outcome of test, process the candidates that still
509 // apply. Collect a list of blocks where control flow will
510 // branch if one of the `target_candidate` sets is not
512 let otherwise: Vec<_> =
513 target_blocks.into_iter()
514 .zip(target_candidates)
515 .flat_map(|(target_block, target_candidates)| {
516 self.match_candidates(span,
523 (otherwise, tested_candidates)
526 /// Initializes each of the bindings from the candidate by
527 /// moving/copying/ref'ing the source as appropriate. Tests the
528 /// guard, if any, and then branches to the arm. Returns the block
529 /// for the case where the guard fails.
531 /// Note: we check earlier that if there is a guard, there cannot
532 /// be move bindings. This isn't really important for the
533 /// self-consistency of this fn, but the reason for it should be
534 /// clear: after we've done the assignments, if there were move
535 /// bindings, further tests would be a use-after-move (which would
536 /// in turn be detected by the borrowck code that runs on the
538 fn bind_and_guard_matched_candidate<'pat>(&mut self,
539 mut block: BasicBlock,
540 arm_blocks: &mut ArmBlocks,
541 candidate: Candidate<'pat, 'tcx>)
542 -> Option<BasicBlock> {
543 debug!("bind_and_guard_matched_candidate(block={:?}, candidate={:?})",
546 debug_assert!(candidate.match_pairs.is_empty());
548 self.bind_matched_candidate(block, candidate.bindings);
550 let arm_block = arm_blocks.blocks[candidate.arm_index];
552 if let Some(guard) = candidate.guard {
553 // the block to branch to if the guard fails; if there is no
554 // guard, this block is simply unreachable
555 let cond = unpack!(block = self.as_operand(block, guard));
556 let otherwise = self.cfg.start_new_block();
557 self.cfg.terminate(block, Terminator::If { cond: cond,
558 targets: [arm_block, otherwise]});
561 self.cfg.terminate(block, Terminator::Goto { target: arm_block });
566 fn bind_matched_candidate(&mut self,
568 bindings: Vec<Binding<'tcx>>) {
569 debug!("bind_matched_candidate(block={:?}, bindings={:?})",
572 // Assign each of the bindings. This may trigger moves out of the candidate.
573 for binding in bindings {
574 // Find the variable for the `var_id` being bound. It
575 // should have been created by a previous call to
576 // `declare_bindings`.
577 let var_index = self.var_indices[&binding.var_id];
579 let rvalue = match binding.binding_mode {
580 BindingMode::ByValue =>
581 Rvalue::Use(Operand::Consume(binding.source)),
582 BindingMode::ByRef(region, borrow_kind) =>
583 Rvalue::Ref(region, borrow_kind, binding.source),
586 self.cfg.push_assign(block, binding.span, &Lvalue::Var(var_index), rvalue);
590 fn declare_binding(&mut self,
591 var_extent: CodeExtent,
592 mutability: Mutability,
599 debug!("declare_binding(var_id={:?}, name={:?}, var_ty={:?}, var_extent={:?}, span={:?})",
600 var_id, name, var_ty, var_extent, span);
602 let index = self.var_decls.len();
603 self.var_decls.push(VarDecl::<'tcx> {
604 mutability: mutability,
608 let index = index as u32;
609 self.schedule_drop(span, var_extent, DropKind::Deep, &Lvalue::Var(index), var_ty);
610 self.var_indices.insert(var_id, index);
612 debug!("declare_binding: index={:?}", index);