]>
Commit | Line | Data |
---|---|---|
e9174d1e SL |
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 | ||
92a42be0 SL |
16 | use build::{BlockAnd, BlockAndExtension, Builder}; |
17 | use rustc_data_structures::fnv::FnvHashMap; | |
18 | use rustc::middle::const_eval::ConstVal; | |
b039eaaf SL |
19 | use rustc::middle::region::CodeExtent; |
20 | use rustc::middle::ty::{AdtDef, Ty}; | |
92a42be0 | 21 | use rustc::mir::repr::*; |
e9174d1e | 22 | use hair::*; |
b039eaaf SL |
23 | use syntax::ast::{Name, NodeId}; |
24 | use syntax::codemap::Span; | |
e9174d1e SL |
25 | |
26 | // helper functions, broken out by category: | |
27 | mod simplify; | |
28 | mod test; | |
29 | mod util; | |
30 | ||
b039eaaf | 31 | impl<'a,'tcx> Builder<'a,'tcx> { |
e9174d1e | 32 | pub fn match_expr(&mut self, |
b039eaaf SL |
33 | destination: &Lvalue<'tcx>, |
34 | span: Span, | |
e9174d1e | 35 | mut block: BasicBlock, |
b039eaaf SL |
36 | discriminant: ExprRef<'tcx>, |
37 | arms: Vec<Arm<'tcx>>) | |
38 | -> BlockAnd<()> { | |
39 | let discriminant_lvalue = unpack!(block = self.as_lvalue(block, discriminant)); | |
40 | ||
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. | |
92a42be0 | 45 | let var_extent = self.extent_of_innermost_scope(); |
b039eaaf | 46 | for arm in &arms { |
92a42be0 | 47 | self.declare_bindings(var_extent, &arm.patterns[0]); |
b039eaaf | 48 | } |
e9174d1e | 49 | |
b039eaaf SL |
50 | let mut arm_blocks = ArmBlocks { |
51 | blocks: arms.iter() | |
52 | .map(|_| self.cfg.start_new_block()) | |
53 | .collect(), | |
54 | }; | |
e9174d1e | 55 | |
b039eaaf | 56 | let arm_bodies: Vec<ExprRef<'tcx>> = |
e9174d1e SL |
57 | arms.iter() |
58 | .map(|arm| arm.body.clone()) | |
59 | .collect(); | |
60 | ||
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 | |
66 | // source. | |
92a42be0 | 67 | let candidates: Vec<_> = |
b039eaaf SL |
68 | arms.iter() |
69 | .enumerate() | |
e9174d1e | 70 | .rev() // highest priority comes last |
b039eaaf SL |
71 | .flat_map(|(arm_index, arm)| { |
72 | arm.patterns.iter() | |
e9174d1e | 73 | .rev() |
92a42be0 | 74 | .map(move |pat| (arm_index, pat, arm.guard.clone())) |
e9174d1e | 75 | }) |
b039eaaf | 76 | .map(|(arm_index, pattern, guard)| { |
e9174d1e | 77 | Candidate { |
92a42be0 | 78 | match_pairs: vec![MatchPair::new(discriminant_lvalue.clone(), pattern)], |
e9174d1e SL |
79 | bindings: vec![], |
80 | guard: guard, | |
b039eaaf | 81 | arm_index: arm_index, |
e9174d1e SL |
82 | } |
83 | }) | |
84 | .collect(); | |
85 | ||
86 | // this will generate code to test discriminant_lvalue and | |
87 | // branch to the appropriate arm block | |
92a42be0 SL |
88 | let otherwise = self.match_candidates(span, &mut arm_blocks, candidates, block); |
89 | ||
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); | |
96 | } | |
e9174d1e SL |
97 | |
98 | // all the arm blocks will rejoin here | |
99 | let end_block = self.cfg.start_new_block(); | |
100 | ||
b039eaaf SL |
101 | for (arm_index, arm_body) in arm_bodies.into_iter().enumerate() { |
102 | let mut arm_block = arm_blocks.blocks[arm_index]; | |
e9174d1e SL |
103 | unpack!(arm_block = self.into(destination, arm_block, arm_body)); |
104 | self.cfg.terminate(arm_block, Terminator::Goto { target: end_block }); | |
105 | } | |
106 | ||
107 | end_block.unit() | |
108 | } | |
109 | ||
110 | pub fn expr_into_pattern(&mut self, | |
111 | mut block: BasicBlock, | |
b039eaaf | 112 | var_extent: CodeExtent, // lifetime of vars |
92a42be0 | 113 | irrefutable_pat: Pattern<'tcx>, |
b039eaaf SL |
114 | initializer: ExprRef<'tcx>) |
115 | -> BlockAnd<()> { | |
e9174d1e | 116 | // optimize the case of `let x = ...` |
92a42be0 | 117 | match *irrefutable_pat.kind { |
e9174d1e SL |
118 | PatternKind::Binding { mutability, |
119 | name, | |
120 | mode: BindingMode::ByValue, | |
121 | var, | |
122 | ty, | |
123 | subpattern: None } => { | |
b039eaaf SL |
124 | let index = self.declare_binding(var_extent, |
125 | mutability, | |
126 | name, | |
127 | var, | |
128 | ty, | |
129 | irrefutable_pat.span); | |
e9174d1e SL |
130 | let lvalue = Lvalue::Var(index); |
131 | return self.into(&lvalue, block, initializer); | |
132 | } | |
b039eaaf | 133 | _ => {} |
e9174d1e SL |
134 | } |
135 | let lvalue = unpack!(block = self.as_lvalue(block, initializer)); | |
b039eaaf SL |
136 | self.lvalue_into_pattern(block, |
137 | var_extent, | |
92a42be0 | 138 | irrefutable_pat, |
b039eaaf | 139 | &lvalue) |
e9174d1e SL |
140 | } |
141 | ||
142 | pub fn lvalue_into_pattern(&mut self, | |
143 | mut block: BasicBlock, | |
b039eaaf | 144 | var_extent: CodeExtent, |
92a42be0 | 145 | irrefutable_pat: Pattern<'tcx>, |
b039eaaf SL |
146 | initializer: &Lvalue<'tcx>) |
147 | -> BlockAnd<()> { | |
148 | // first, creating the bindings | |
92a42be0 | 149 | self.declare_bindings(var_extent, &irrefutable_pat); |
b039eaaf | 150 | |
e9174d1e | 151 | // create a dummy candidate |
92a42be0 SL |
152 | let mut candidate = Candidate { |
153 | match_pairs: vec![MatchPair::new(initializer.clone(), &irrefutable_pat)], | |
e9174d1e SL |
154 | bindings: vec![], |
155 | guard: None, | |
b039eaaf | 156 | arm_index: 0, // since we don't call `match_candidates`, this field is unused |
e9174d1e SL |
157 | }; |
158 | ||
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)); | |
162 | ||
163 | if !candidate.match_pairs.is_empty() { | |
b039eaaf SL |
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)); | |
e9174d1e SL |
168 | } |
169 | ||
170 | // now apply the bindings, which will also declare the variables | |
b039eaaf | 171 | self.bind_matched_candidate(block, candidate.bindings); |
e9174d1e SL |
172 | |
173 | block.unit() | |
174 | } | |
175 | ||
92a42be0 SL |
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 } => { | |
e9174d1e | 179 | self.declare_binding(var_extent, mutability, name, var, ty, pattern.span); |
92a42be0 | 180 | if let Some(subpattern) = subpattern.as_ref() { |
b039eaaf | 181 | self.declare_bindings(var_extent, subpattern); |
e9174d1e SL |
182 | } |
183 | } | |
92a42be0 SL |
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) { | |
b039eaaf | 187 | self.declare_bindings(var_extent, subpattern); |
e9174d1e SL |
188 | } |
189 | } | |
92a42be0 SL |
190 | PatternKind::Constant { .. } | PatternKind::Range { .. } | PatternKind::Wild => { |
191 | } | |
192 | PatternKind::Deref { ref subpattern } => { | |
b039eaaf | 193 | self.declare_bindings(var_extent, subpattern); |
e9174d1e | 194 | } |
92a42be0 SL |
195 | PatternKind::Leaf { ref subpatterns } | |
196 | PatternKind::Variant { ref subpatterns, .. } => { | |
e9174d1e | 197 | for subpattern in subpatterns { |
92a42be0 | 198 | self.declare_bindings(var_extent, &subpattern.pattern); |
e9174d1e SL |
199 | } |
200 | } | |
201 | } | |
202 | } | |
203 | } | |
204 | ||
b039eaaf SL |
205 | /// List of blocks for each arm (and potentially other metadata in the |
206 | /// future). | |
207 | struct ArmBlocks { | |
208 | blocks: Vec<BasicBlock>, | |
209 | } | |
210 | ||
e9174d1e | 211 | #[derive(Clone, Debug)] |
92a42be0 | 212 | struct Candidate<'pat, 'tcx:'pat> { |
e9174d1e | 213 | // all of these must be satisfied... |
92a42be0 | 214 | match_pairs: Vec<MatchPair<'pat, 'tcx>>, |
e9174d1e SL |
215 | |
216 | // ...these bindings established... | |
b039eaaf | 217 | bindings: Vec<Binding<'tcx>>, |
e9174d1e SL |
218 | |
219 | // ...and the guard must be evaluated... | |
b039eaaf | 220 | guard: Option<ExprRef<'tcx>>, |
e9174d1e | 221 | |
b039eaaf SL |
222 | // ...and then we branch to arm with this index. |
223 | arm_index: usize, | |
e9174d1e SL |
224 | } |
225 | ||
226 | #[derive(Clone, Debug)] | |
b039eaaf SL |
227 | struct Binding<'tcx> { |
228 | span: Span, | |
229 | source: Lvalue<'tcx>, | |
230 | name: Name, | |
231 | var_id: NodeId, | |
232 | var_ty: Ty<'tcx>, | |
e9174d1e | 233 | mutability: Mutability, |
b039eaaf | 234 | binding_mode: BindingMode, |
e9174d1e SL |
235 | } |
236 | ||
237 | #[derive(Clone, Debug)] | |
92a42be0 | 238 | struct MatchPair<'pat, 'tcx:'pat> { |
e9174d1e | 239 | // this lvalue... |
b039eaaf | 240 | lvalue: Lvalue<'tcx>, |
e9174d1e SL |
241 | |
242 | // ... must match this pattern. | |
92a42be0 | 243 | pattern: &'pat Pattern<'tcx>, |
e9174d1e SL |
244 | } |
245 | ||
246 | #[derive(Clone, Debug, PartialEq)] | |
b039eaaf | 247 | enum TestKind<'tcx> { |
e9174d1e | 248 | // test the branches of enum |
b039eaaf SL |
249 | Switch { |
250 | adt_def: AdtDef<'tcx>, | |
251 | }, | |
e9174d1e | 252 | |
92a42be0 SL |
253 | // test the branches of enum |
254 | SwitchInt { | |
255 | switch_ty: Ty<'tcx>, | |
256 | options: Vec<ConstVal>, | |
257 | indices: FnvHashMap<ConstVal, usize>, | |
258 | }, | |
259 | ||
e9174d1e | 260 | // test for equality |
b039eaaf SL |
261 | Eq { |
262 | value: Literal<'tcx>, | |
263 | ty: Ty<'tcx>, | |
264 | }, | |
e9174d1e SL |
265 | |
266 | // test whether the value falls within an inclusive range | |
b039eaaf SL |
267 | Range { |
268 | lo: Literal<'tcx>, | |
269 | hi: Literal<'tcx>, | |
270 | ty: Ty<'tcx>, | |
271 | }, | |
e9174d1e SL |
272 | |
273 | // test length of the slice is equal to len | |
b039eaaf SL |
274 | Len { |
275 | len: usize, | |
276 | op: BinOp, | |
277 | }, | |
e9174d1e SL |
278 | } |
279 | ||
280 | #[derive(Debug)] | |
b039eaaf SL |
281 | struct Test<'tcx> { |
282 | span: Span, | |
283 | kind: TestKind<'tcx>, | |
e9174d1e SL |
284 | } |
285 | ||
286 | /////////////////////////////////////////////////////////////////////////// | |
287 | // Main matching algorithm | |
288 | ||
b039eaaf | 289 | impl<'a,'tcx> Builder<'a,'tcx> { |
92a42be0 SL |
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`. | |
297 | /// | |
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. | |
303 | /// | |
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, | |
311 | span: Span, | |
312 | arm_blocks: &mut ArmBlocks, | |
313 | mut candidates: Vec<Candidate<'pat, 'tcx>>, | |
314 | mut block: BasicBlock) | |
315 | -> Vec<BasicBlock> | |
e9174d1e | 316 | { |
b039eaaf SL |
317 | debug!("matched_candidate(span={:?}, block={:?}, candidates={:?})", |
318 | span, block, candidates); | |
e9174d1e SL |
319 | |
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)); | |
325 | } | |
326 | ||
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 | |
330 | // pairs. | |
331 | let fully_matched = | |
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(); | |
b039eaaf SL |
338 | if let Some(b) = self.bind_and_guard_matched_candidate(block, arm_blocks, candidate) { |
339 | block = b; | |
340 | } else { | |
341 | // if None is returned, then any remaining candidates | |
342 | // are unreachable (at least not through this path). | |
92a42be0 | 343 | return vec![]; |
e9174d1e SL |
344 | } |
345 | } | |
346 | ||
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() { | |
92a42be0 SL |
350 | return vec![block]; |
351 | } | |
352 | ||
353 | // Test candidates where possible. | |
354 | let (otherwise, tested_candidates) = | |
355 | self.test_candidates(span, arm_blocks, &candidates, block); | |
356 | ||
357 | // If the target candidates were exhaustive, then we are done. | |
358 | if otherwise.is_empty() { | |
359 | return vec![]; | |
360 | } | |
361 | ||
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 { | |
366 | return otherwise; | |
367 | } | |
368 | ||
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) | |
373 | } | |
374 | ||
375 | fn join_otherwise_blocks(&mut self, | |
376 | otherwise: Vec<BasicBlock>) | |
377 | -> BasicBlock | |
378 | { | |
379 | if otherwise.len() == 1 { | |
380 | otherwise[0] | |
381 | } else { | |
382 | let join_block = self.cfg.start_new_block(); | |
383 | for block in otherwise { | |
384 | self.cfg.terminate(block, Terminator::Goto { target: join_block }); | |
385 | } | |
386 | join_block | |
e9174d1e | 387 | } |
92a42be0 | 388 | } |
e9174d1e | 389 | |
92a42be0 SL |
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. | |
397 | /// | |
398 | /// *Note:* taking the first match pair is somewhat arbitrary, and | |
399 | /// we might do better here by choosing more carefully what to | |
400 | /// test. | |
401 | /// | |
402 | /// For example, consider the following possible match-pairs: | |
403 | /// | |
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 | |
407 | /// 4. etc. | |
408 | /// | |
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). | |
418 | /// | |
419 | /// But there may also be candidates that the test just doesn't | |
420 | /// apply to. For example, consider the case of #29740: | |
421 | /// | |
422 | /// ```rust | |
423 | /// match x { | |
424 | /// "foo" => ..., | |
425 | /// "bar" => ..., | |
426 | /// "baz" => ..., | |
427 | /// _ => ..., | |
428 | /// } | |
429 | /// ``` | |
430 | /// | |
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: | |
435 | /// | |
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 | |
441 | /// other lists. | |
442 | /// | |
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. | |
452 | /// | |
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, | |
457 | span: Span, | |
458 | arm_blocks: &mut ArmBlocks, | |
459 | candidates: &[Candidate<'pat, 'tcx>], | |
460 | block: BasicBlock) | |
461 | -> (Vec<BasicBlock>, usize) | |
462 | { | |
463 | // extract the match-pair from the highest priority candidate | |
e9174d1e | 464 | let match_pair = &candidates.last().unwrap().match_pairs[0]; |
92a42be0 SL |
465 | let mut test = self.test(match_pair); |
466 | ||
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 | |
470 | // available | |
471 | match test.kind { | |
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, | |
475 | candidate, | |
476 | switch_ty, | |
477 | options, | |
478 | indices) { | |
479 | break; | |
480 | } | |
481 | } | |
482 | } | |
483 | _ => { } | |
484 | } | |
485 | ||
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. | |
e9174d1e SL |
490 | debug!("match_candidates: test={:?} match_pair={:?}", test, match_pair); |
491 | let target_blocks = self.perform_test(block, &match_pair.lvalue, &test); | |
92a42be0 SL |
492 | let mut target_candidates: Vec<_> = (0..target_blocks.len()).map(|_| vec![]).collect(); |
493 | ||
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 = | |
499 | candidates.iter() | |
500 | .rev() | |
501 | .take_while(|c| self.sort_candidate(&match_pair.lvalue, | |
502 | &test, | |
503 | c, | |
504 | &mut target_candidates)) | |
505 | .count(); | |
506 | assert!(tested_candidates > 0); // at least the last candidate ought to be tested | |
507 | ||
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 | |
511 | // exhaustive. | |
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, | |
517 | arm_blocks, | |
518 | target_candidates, | |
519 | target_block) | |
520 | }) | |
521 | .collect(); | |
522 | ||
523 | (otherwise, tested_candidates) | |
e9174d1e SL |
524 | } |
525 | ||
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. | |
530 | /// | |
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 | |
537 | /// MIR). | |
92a42be0 SL |
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> { | |
b039eaaf SL |
543 | debug!("bind_and_guard_matched_candidate(block={:?}, candidate={:?})", |
544 | block, candidate); | |
e9174d1e SL |
545 | |
546 | debug_assert!(candidate.match_pairs.is_empty()); | |
547 | ||
b039eaaf SL |
548 | self.bind_matched_candidate(block, candidate.bindings); |
549 | ||
550 | let arm_block = arm_blocks.blocks[candidate.arm_index]; | |
e9174d1e SL |
551 | |
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, | |
b039eaaf | 558 | targets: [arm_block, otherwise]}); |
e9174d1e SL |
559 | Some(otherwise) |
560 | } else { | |
b039eaaf | 561 | self.cfg.terminate(block, Terminator::Goto { target: arm_block }); |
e9174d1e SL |
562 | None |
563 | } | |
564 | } | |
565 | ||
566 | fn bind_matched_candidate(&mut self, | |
567 | block: BasicBlock, | |
b039eaaf SL |
568 | bindings: Vec<Binding<'tcx>>) { |
569 | debug!("bind_matched_candidate(block={:?}, bindings={:?})", | |
570 | block, bindings); | |
e9174d1e SL |
571 | |
572 | // Assign each of the bindings. This may trigger moves out of the candidate. | |
573 | for binding in bindings { | |
b039eaaf SL |
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]; | |
e9174d1e SL |
578 | |
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), | |
584 | }; | |
585 | ||
586 | self.cfg.push_assign(block, binding.span, &Lvalue::Var(var_index), rvalue); | |
587 | } | |
588 | } | |
589 | ||
590 | fn declare_binding(&mut self, | |
b039eaaf | 591 | var_extent: CodeExtent, |
e9174d1e | 592 | mutability: Mutability, |
b039eaaf SL |
593 | name: Name, |
594 | var_id: NodeId, | |
595 | var_ty: Ty<'tcx>, | |
596 | span: Span) | |
e9174d1e SL |
597 | -> u32 |
598 | { | |
599 | debug!("declare_binding(var_id={:?}, name={:?}, var_ty={:?}, var_extent={:?}, span={:?})", | |
600 | var_id, name, var_ty, var_extent, span); | |
601 | ||
602 | let index = self.var_decls.len(); | |
b039eaaf | 603 | self.var_decls.push(VarDecl::<'tcx> { |
e9174d1e SL |
604 | mutability: mutability, |
605 | name: name, | |
606 | ty: var_ty.clone(), | |
607 | }); | |
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); | |
611 | ||
612 | debug!("declare_binding: index={:?}", index); | |
613 | ||
614 | index | |
615 | } | |
616 | } |