]>
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; | |
54a0048b SL |
18 | use rustc::middle::const_val::ConstVal; |
19 | use rustc::ty::{AdtDef, Ty}; | |
92a42be0 | 20 | use rustc::mir::repr::*; |
e9174d1e | 21 | use hair::*; |
b039eaaf SL |
22 | use syntax::ast::{Name, NodeId}; |
23 | use syntax::codemap::Span; | |
e9174d1e SL |
24 | |
25 | // helper functions, broken out by category: | |
26 | mod simplify; | |
27 | mod test; | |
28 | mod util; | |
29 | ||
b039eaaf | 30 | impl<'a,'tcx> Builder<'a,'tcx> { |
e9174d1e | 31 | pub fn match_expr(&mut self, |
b039eaaf SL |
32 | destination: &Lvalue<'tcx>, |
33 | span: Span, | |
e9174d1e | 34 | mut block: BasicBlock, |
b039eaaf SL |
35 | discriminant: ExprRef<'tcx>, |
36 | arms: Vec<Arm<'tcx>>) | |
37 | -> BlockAnd<()> { | |
38 | let discriminant_lvalue = unpack!(block = self.as_lvalue(block, discriminant)); | |
39 | ||
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. | |
54a0048b | 44 | let var_scope_id = self.innermost_scope_id(); |
b039eaaf | 45 | for arm in &arms { |
54a0048b | 46 | self.declare_bindings(var_scope_id, &arm.patterns[0]); |
b039eaaf | 47 | } |
e9174d1e | 48 | |
b039eaaf SL |
49 | let mut arm_blocks = ArmBlocks { |
50 | blocks: arms.iter() | |
51 | .map(|_| self.cfg.start_new_block()) | |
52 | .collect(), | |
53 | }; | |
e9174d1e | 54 | |
b039eaaf | 55 | let arm_bodies: Vec<ExprRef<'tcx>> = |
e9174d1e SL |
56 | arms.iter() |
57 | .map(|arm| arm.body.clone()) | |
58 | .collect(); | |
59 | ||
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 | |
9cc50fc6 SL |
63 | // highest priority candidate comes first in the list. |
64 | // (i.e. same order as in source) | |
92a42be0 | 65 | let candidates: Vec<_> = |
b039eaaf SL |
66 | arms.iter() |
67 | .enumerate() | |
b039eaaf SL |
68 | .flat_map(|(arm_index, arm)| { |
69 | arm.patterns.iter() | |
92a42be0 | 70 | .map(move |pat| (arm_index, pat, arm.guard.clone())) |
e9174d1e | 71 | }) |
b039eaaf | 72 | .map(|(arm_index, pattern, guard)| { |
e9174d1e | 73 | Candidate { |
54a0048b | 74 | span: pattern.span, |
92a42be0 | 75 | match_pairs: vec![MatchPair::new(discriminant_lvalue.clone(), pattern)], |
e9174d1e SL |
76 | bindings: vec![], |
77 | guard: guard, | |
b039eaaf | 78 | arm_index: arm_index, |
e9174d1e SL |
79 | } |
80 | }) | |
81 | .collect(); | |
82 | ||
83 | // this will generate code to test discriminant_lvalue and | |
84 | // branch to the appropriate arm block | |
92a42be0 SL |
85 | let otherwise = self.match_candidates(span, &mut arm_blocks, candidates, block); |
86 | ||
87 | // because all matches are exhaustive, in principle we expect | |
88 | // an empty vector to be returned here, but the algorithm is | |
89 | // not entirely precise | |
90 | if !otherwise.is_empty() { | |
54a0048b | 91 | let join_block = self.join_otherwise_blocks(span, otherwise); |
9cc50fc6 | 92 | self.panic(join_block, "something about matches algorithm not being precise", span); |
92a42be0 | 93 | } |
e9174d1e SL |
94 | |
95 | // all the arm blocks will rejoin here | |
96 | let end_block = self.cfg.start_new_block(); | |
97 | ||
b039eaaf SL |
98 | for (arm_index, arm_body) in arm_bodies.into_iter().enumerate() { |
99 | let mut arm_block = arm_blocks.blocks[arm_index]; | |
e9174d1e | 100 | unpack!(arm_block = self.into(destination, arm_block, arm_body)); |
54a0048b SL |
101 | self.cfg.terminate(arm_block, |
102 | var_scope_id, | |
103 | span, | |
104 | TerminatorKind::Goto { target: end_block }); | |
e9174d1e SL |
105 | } |
106 | ||
107 | end_block.unit() | |
108 | } | |
109 | ||
110 | pub fn expr_into_pattern(&mut self, | |
111 | mut block: BasicBlock, | |
54a0048b | 112 | var_scope_id: ScopeId, // 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 } => { | |
54a0048b | 124 | let index = self.declare_binding(var_scope_id, |
b039eaaf SL |
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 | 136 | self.lvalue_into_pattern(block, |
54a0048b | 137 | var_scope_id, |
92a42be0 | 138 | irrefutable_pat, |
b039eaaf | 139 | &lvalue) |
e9174d1e SL |
140 | } |
141 | ||
142 | pub fn lvalue_into_pattern(&mut self, | |
143 | mut block: BasicBlock, | |
54a0048b | 144 | var_scope_id: ScopeId, |
92a42be0 | 145 | irrefutable_pat: Pattern<'tcx>, |
b039eaaf SL |
146 | initializer: &Lvalue<'tcx>) |
147 | -> BlockAnd<()> { | |
148 | // first, creating the bindings | |
54a0048b | 149 | self.declare_bindings(var_scope_id, &irrefutable_pat); |
b039eaaf | 150 | |
e9174d1e | 151 | // create a dummy candidate |
92a42be0 | 152 | let mut candidate = Candidate { |
54a0048b | 153 | span: irrefutable_pat.span, |
92a42be0 | 154 | match_pairs: vec![MatchPair::new(initializer.clone(), &irrefutable_pat)], |
e9174d1e SL |
155 | bindings: vec![], |
156 | guard: None, | |
b039eaaf | 157 | arm_index: 0, // since we don't call `match_candidates`, this field is unused |
e9174d1e SL |
158 | }; |
159 | ||
160 | // Simplify the candidate. Since the pattern is irrefutable, this should | |
161 | // always convert all match-pairs into bindings. | |
162 | unpack!(block = self.simplify_candidate(block, &mut candidate)); | |
163 | ||
164 | if !candidate.match_pairs.is_empty() { | |
54a0048b SL |
165 | span_bug!(candidate.match_pairs[0].pattern.span, |
166 | "match pairs {:?} remaining after simplifying \ | |
167 | irrefutable pattern", | |
168 | candidate.match_pairs); | |
e9174d1e SL |
169 | } |
170 | ||
171 | // now apply the bindings, which will also declare the variables | |
b039eaaf | 172 | self.bind_matched_candidate(block, candidate.bindings); |
e9174d1e SL |
173 | |
174 | block.unit() | |
175 | } | |
176 | ||
54a0048b | 177 | pub fn declare_bindings(&mut self, var_scope_id: ScopeId, pattern: &Pattern<'tcx>) { |
92a42be0 SL |
178 | match *pattern.kind { |
179 | PatternKind::Binding { mutability, name, mode: _, var, ty, ref subpattern } => { | |
54a0048b | 180 | self.declare_binding(var_scope_id, mutability, name, var, ty, pattern.span); |
92a42be0 | 181 | if let Some(subpattern) = subpattern.as_ref() { |
54a0048b | 182 | self.declare_bindings(var_scope_id, subpattern); |
e9174d1e SL |
183 | } |
184 | } | |
92a42be0 SL |
185 | PatternKind::Array { ref prefix, ref slice, ref suffix } | |
186 | PatternKind::Slice { ref prefix, ref slice, ref suffix } => { | |
187 | for subpattern in prefix.iter().chain(slice).chain(suffix) { | |
54a0048b | 188 | self.declare_bindings(var_scope_id, subpattern); |
e9174d1e SL |
189 | } |
190 | } | |
92a42be0 SL |
191 | PatternKind::Constant { .. } | PatternKind::Range { .. } | PatternKind::Wild => { |
192 | } | |
193 | PatternKind::Deref { ref subpattern } => { | |
54a0048b | 194 | self.declare_bindings(var_scope_id, subpattern); |
e9174d1e | 195 | } |
92a42be0 SL |
196 | PatternKind::Leaf { ref subpatterns } | |
197 | PatternKind::Variant { ref subpatterns, .. } => { | |
e9174d1e | 198 | for subpattern in subpatterns { |
54a0048b | 199 | self.declare_bindings(var_scope_id, &subpattern.pattern); |
e9174d1e SL |
200 | } |
201 | } | |
202 | } | |
203 | } | |
204 | } | |
205 | ||
b039eaaf SL |
206 | /// List of blocks for each arm (and potentially other metadata in the |
207 | /// future). | |
208 | struct ArmBlocks { | |
209 | blocks: Vec<BasicBlock>, | |
210 | } | |
211 | ||
e9174d1e | 212 | #[derive(Clone, Debug)] |
9cc50fc6 | 213 | pub struct Candidate<'pat, 'tcx:'pat> { |
54a0048b SL |
214 | // span of the original pattern that gave rise to this candidate |
215 | span: Span, | |
216 | ||
e9174d1e | 217 | // all of these must be satisfied... |
92a42be0 | 218 | match_pairs: Vec<MatchPair<'pat, 'tcx>>, |
e9174d1e SL |
219 | |
220 | // ...these bindings established... | |
b039eaaf | 221 | bindings: Vec<Binding<'tcx>>, |
e9174d1e SL |
222 | |
223 | // ...and the guard must be evaluated... | |
b039eaaf | 224 | guard: Option<ExprRef<'tcx>>, |
e9174d1e | 225 | |
b039eaaf SL |
226 | // ...and then we branch to arm with this index. |
227 | arm_index: usize, | |
e9174d1e SL |
228 | } |
229 | ||
230 | #[derive(Clone, Debug)] | |
b039eaaf SL |
231 | struct Binding<'tcx> { |
232 | span: Span, | |
233 | source: Lvalue<'tcx>, | |
234 | name: Name, | |
235 | var_id: NodeId, | |
236 | var_ty: Ty<'tcx>, | |
e9174d1e | 237 | mutability: Mutability, |
b039eaaf | 238 | binding_mode: BindingMode, |
e9174d1e SL |
239 | } |
240 | ||
241 | #[derive(Clone, Debug)] | |
9cc50fc6 | 242 | pub struct MatchPair<'pat, 'tcx:'pat> { |
e9174d1e | 243 | // this lvalue... |
b039eaaf | 244 | lvalue: Lvalue<'tcx>, |
e9174d1e SL |
245 | |
246 | // ... must match this pattern. | |
92a42be0 | 247 | pattern: &'pat Pattern<'tcx>, |
54a0048b SL |
248 | |
249 | // HACK(eddyb) This is used to toggle whether a Slice pattern | |
250 | // has had its length checked. This is only necessary because | |
251 | // the "rest" part of the pattern right now has type &[T] and | |
252 | // as such, it requires an Rvalue::Slice to be generated. | |
253 | // See RFC 495 / issue #23121 for the eventual (proper) solution. | |
254 | slice_len_checked: bool | |
e9174d1e SL |
255 | } |
256 | ||
257 | #[derive(Clone, Debug, PartialEq)] | |
b039eaaf | 258 | enum TestKind<'tcx> { |
e9174d1e | 259 | // test the branches of enum |
b039eaaf SL |
260 | Switch { |
261 | adt_def: AdtDef<'tcx>, | |
262 | }, | |
e9174d1e | 263 | |
92a42be0 SL |
264 | // test the branches of enum |
265 | SwitchInt { | |
266 | switch_ty: Ty<'tcx>, | |
267 | options: Vec<ConstVal>, | |
268 | indices: FnvHashMap<ConstVal, usize>, | |
269 | }, | |
270 | ||
e9174d1e | 271 | // test for equality |
b039eaaf | 272 | Eq { |
9cc50fc6 | 273 | value: ConstVal, |
b039eaaf SL |
274 | ty: Ty<'tcx>, |
275 | }, | |
e9174d1e SL |
276 | |
277 | // test whether the value falls within an inclusive range | |
b039eaaf SL |
278 | Range { |
279 | lo: Literal<'tcx>, | |
280 | hi: Literal<'tcx>, | |
281 | ty: Ty<'tcx>, | |
282 | }, | |
e9174d1e SL |
283 | |
284 | // test length of the slice is equal to len | |
b039eaaf | 285 | Len { |
54a0048b | 286 | len: u64, |
b039eaaf SL |
287 | op: BinOp, |
288 | }, | |
e9174d1e SL |
289 | } |
290 | ||
291 | #[derive(Debug)] | |
9cc50fc6 | 292 | pub struct Test<'tcx> { |
b039eaaf SL |
293 | span: Span, |
294 | kind: TestKind<'tcx>, | |
e9174d1e SL |
295 | } |
296 | ||
297 | /////////////////////////////////////////////////////////////////////////// | |
298 | // Main matching algorithm | |
299 | ||
b039eaaf | 300 | impl<'a,'tcx> Builder<'a,'tcx> { |
92a42be0 SL |
301 | /// The main match algorithm. It begins with a set of candidates |
302 | /// `candidates` and has the job of generating code to determine | |
303 | /// which of these candidates, if any, is the correct one. The | |
9cc50fc6 SL |
304 | /// candidates are sorted such that the first item in the list |
305 | /// has the highest priority. When a candidate is found to match | |
306 | /// the value, we will generate a branch to the appropriate | |
92a42be0 SL |
307 | /// block found in `arm_blocks`. |
308 | /// | |
309 | /// The return value is a list of "otherwise" blocks. These are | |
310 | /// points in execution where we found that *NONE* of the | |
311 | /// candidates apply. In principle, this means that the input | |
312 | /// list was not exhaustive, though at present we sometimes are | |
313 | /// not smart enough to recognize all exhaustive inputs. | |
314 | /// | |
315 | /// It might be surprising that the input can be inexhaustive. | |
316 | /// Indeed, initially, it is not, because all matches are | |
317 | /// exhaustive in Rust. But during processing we sometimes divide | |
318 | /// up the list of candidates and recurse with a non-exhaustive | |
319 | /// list. This is important to keep the size of the generated code | |
320 | /// under control. See `test_candidates` for more details. | |
321 | fn match_candidates<'pat>(&mut self, | |
322 | span: Span, | |
323 | arm_blocks: &mut ArmBlocks, | |
324 | mut candidates: Vec<Candidate<'pat, 'tcx>>, | |
325 | mut block: BasicBlock) | |
326 | -> Vec<BasicBlock> | |
e9174d1e | 327 | { |
b039eaaf SL |
328 | debug!("matched_candidate(span={:?}, block={:?}, candidates={:?})", |
329 | span, block, candidates); | |
e9174d1e SL |
330 | |
331 | // Start by simplifying candidates. Once this process is | |
332 | // complete, all the match pairs which remain require some | |
333 | // form of test, whether it be a switch or pattern comparison. | |
334 | for candidate in &mut candidates { | |
335 | unpack!(block = self.simplify_candidate(block, candidate)); | |
336 | } | |
337 | ||
9cc50fc6 SL |
338 | // The candidates are sorted by priority. Check to see |
339 | // whether the higher priority candidates (and hence at | |
340 | // the front of the vec) have satisfied all their match | |
e9174d1e SL |
341 | // pairs. |
342 | let fully_matched = | |
9cc50fc6 | 343 | candidates.iter().take_while(|c| c.match_pairs.is_empty()).count(); |
e9174d1e | 344 | debug!("match_candidates: {:?} candidates fully matched", fully_matched); |
9cc50fc6 SL |
345 | let mut unmatched_candidates = candidates.split_off(fully_matched); |
346 | for candidate in candidates { | |
e9174d1e SL |
347 | // If so, apply any bindings, test the guard (if any), and |
348 | // branch to the arm. | |
b039eaaf SL |
349 | if let Some(b) = self.bind_and_guard_matched_candidate(block, arm_blocks, candidate) { |
350 | block = b; | |
351 | } else { | |
352 | // if None is returned, then any remaining candidates | |
353 | // are unreachable (at least not through this path). | |
92a42be0 | 354 | return vec![]; |
e9174d1e SL |
355 | } |
356 | } | |
357 | ||
358 | // If there are no candidates that still need testing, we're done. | |
359 | // Since all matches are exhaustive, execution should never reach this point. | |
9cc50fc6 | 360 | if unmatched_candidates.is_empty() { |
92a42be0 SL |
361 | return vec![block]; |
362 | } | |
363 | ||
364 | // Test candidates where possible. | |
365 | let (otherwise, tested_candidates) = | |
9cc50fc6 | 366 | self.test_candidates(span, arm_blocks, &unmatched_candidates, block); |
92a42be0 SL |
367 | |
368 | // If the target candidates were exhaustive, then we are done. | |
369 | if otherwise.is_empty() { | |
370 | return vec![]; | |
371 | } | |
372 | ||
373 | // If all candidates were sorted into `target_candidates` somewhere, then | |
374 | // the initial set was inexhaustive. | |
9cc50fc6 SL |
375 | let untested_candidates = unmatched_candidates.split_off(tested_candidates); |
376 | if untested_candidates.len() == 0 { | |
92a42be0 SL |
377 | return otherwise; |
378 | } | |
379 | ||
380 | // Otherwise, let's process those remaining candidates. | |
54a0048b | 381 | let join_block = self.join_otherwise_blocks(span, otherwise); |
9cc50fc6 | 382 | self.match_candidates(span, arm_blocks, untested_candidates, join_block) |
92a42be0 SL |
383 | } |
384 | ||
385 | fn join_otherwise_blocks(&mut self, | |
54a0048b | 386 | span: Span, |
92a42be0 SL |
387 | otherwise: Vec<BasicBlock>) |
388 | -> BasicBlock | |
389 | { | |
54a0048b | 390 | let scope_id = self.innermost_scope_id(); |
92a42be0 SL |
391 | if otherwise.len() == 1 { |
392 | otherwise[0] | |
393 | } else { | |
394 | let join_block = self.cfg.start_new_block(); | |
395 | for block in otherwise { | |
54a0048b SL |
396 | self.cfg.terminate(block, |
397 | scope_id, | |
398 | span, | |
399 | TerminatorKind::Goto { target: join_block }); | |
92a42be0 SL |
400 | } |
401 | join_block | |
e9174d1e | 402 | } |
92a42be0 | 403 | } |
e9174d1e | 404 | |
92a42be0 SL |
405 | /// This is the most subtle part of the matching algorithm. At |
406 | /// this point, the input candidates have been fully simplified, | |
407 | /// and so we know that all remaining match-pairs require some | |
408 | /// sort of test. To decide what test to do, we take the highest | |
409 | /// priority candidate (last one in the list) and extract the | |
410 | /// first match-pair from the list. From this we decide what kind | |
411 | /// of test is needed using `test`, defined in the `test` module. | |
412 | /// | |
413 | /// *Note:* taking the first match pair is somewhat arbitrary, and | |
414 | /// we might do better here by choosing more carefully what to | |
415 | /// test. | |
416 | /// | |
417 | /// For example, consider the following possible match-pairs: | |
418 | /// | |
419 | /// 1. `x @ Some(P)` -- we will do a `Switch` to decide what variant `x` has | |
420 | /// 2. `x @ 22` -- we will do a `SwitchInt` | |
421 | /// 3. `x @ 3..5` -- we will do a range test | |
422 | /// 4. etc. | |
423 | /// | |
424 | /// Once we know what sort of test we are going to perform, this | |
425 | /// test may also help us with other candidates. So we walk over | |
426 | /// the candidates (from high to low priority) and check. This | |
427 | /// gives us, for each outcome of the test, a transformed list of | |
428 | /// candidates. For example, if we are testing the current | |
429 | /// variant of `x.0`, and we have a candidate `{x.0 @ Some(v), x.1 | |
430 | /// @ 22}`, then we would have a resulting candidate of `{(x.0 as | |
431 | /// Some).0 @ v, x.1 @ 22}`. Note that the first match-pair is now | |
432 | /// simpler (and, in fact, irrefutable). | |
433 | /// | |
434 | /// But there may also be candidates that the test just doesn't | |
435 | /// apply to. For example, consider the case of #29740: | |
436 | /// | |
437 | /// ```rust | |
438 | /// match x { | |
439 | /// "foo" => ..., | |
440 | /// "bar" => ..., | |
441 | /// "baz" => ..., | |
442 | /// _ => ..., | |
443 | /// } | |
444 | /// ``` | |
445 | /// | |
446 | /// Here the match-pair we are testing will be `x @ "foo"`, and we | |
447 | /// will generate an `Eq` test. Because `"bar"` and `"baz"` are different | |
448 | /// constants, we will decide that these later candidates are just not | |
449 | /// informed by the eq test. So we'll wind up with three candidate sets: | |
450 | /// | |
451 | /// - If outcome is that `x == "foo"` (one candidate, derived from `x @ "foo"`) | |
452 | /// - If outcome is that `x != "foo"` (empty list of candidates) | |
453 | /// - Otherwise (three candidates, `x @ "bar"`, `x @ "baz"`, `x @ | |
454 | /// _`). Here we have the invariant that everything in the | |
455 | /// otherwise list is of **lower priority** than the stuff in the | |
456 | /// other lists. | |
457 | /// | |
458 | /// So we'll compile the test. For each outcome of the test, we | |
459 | /// recursively call `match_candidates` with the corresponding set | |
460 | /// of candidates. But note that this set is now inexhaustive: for | |
461 | /// example, in the case where the test returns false, there are | |
462 | /// NO candidates, even though there is stll a value to be | |
463 | /// matched. So we'll collect the return values from | |
464 | /// `match_candidates`, which are the blocks where control-flow | |
465 | /// goes if none of the candidates matched. At this point, we can | |
466 | /// continue with the "otherwise" list. | |
467 | /// | |
468 | /// If you apply this to the above test, you basically wind up | |
469 | /// with an if-else-if chain, testing each candidate in turn, | |
470 | /// which is precisely what we want. | |
471 | fn test_candidates<'pat>(&mut self, | |
472 | span: Span, | |
473 | arm_blocks: &mut ArmBlocks, | |
474 | candidates: &[Candidate<'pat, 'tcx>], | |
475 | block: BasicBlock) | |
476 | -> (Vec<BasicBlock>, usize) | |
477 | { | |
478 | // extract the match-pair from the highest priority candidate | |
9cc50fc6 | 479 | let match_pair = &candidates.first().unwrap().match_pairs[0]; |
92a42be0 SL |
480 | let mut test = self.test(match_pair); |
481 | ||
482 | // most of the time, the test to perform is simply a function | |
483 | // of the main candidate; but for a test like SwitchInt, we | |
484 | // may want to add cases based on the candidates that are | |
485 | // available | |
486 | match test.kind { | |
487 | TestKind::SwitchInt { switch_ty, ref mut options, ref mut indices } => { | |
9cc50fc6 | 488 | for candidate in candidates.iter() { |
92a42be0 SL |
489 | if !self.add_cases_to_switch(&match_pair.lvalue, |
490 | candidate, | |
491 | switch_ty, | |
492 | options, | |
493 | indices) { | |
494 | break; | |
495 | } | |
496 | } | |
497 | } | |
498 | _ => { } | |
499 | } | |
500 | ||
501 | // perform the test, branching to one of N blocks. For each of | |
502 | // those N possible outcomes, create a (initially empty) | |
503 | // vector of candidates. Those are the candidates that still | |
504 | // apply if the test has that particular outcome. | |
e9174d1e SL |
505 | debug!("match_candidates: test={:?} match_pair={:?}", test, match_pair); |
506 | let target_blocks = self.perform_test(block, &match_pair.lvalue, &test); | |
92a42be0 SL |
507 | let mut target_candidates: Vec<_> = (0..target_blocks.len()).map(|_| vec![]).collect(); |
508 | ||
509 | // Sort the candidates into the appropriate vector in | |
510 | // `target_candidates`. Note that at some point we may | |
511 | // encounter a candidate where the test is not relevant; at | |
512 | // that point, we stop sorting. | |
513 | let tested_candidates = | |
514 | candidates.iter() | |
92a42be0 SL |
515 | .take_while(|c| self.sort_candidate(&match_pair.lvalue, |
516 | &test, | |
517 | c, | |
518 | &mut target_candidates)) | |
519 | .count(); | |
520 | assert!(tested_candidates > 0); // at least the last candidate ought to be tested | |
521 | ||
522 | // For each outcome of test, process the candidates that still | |
523 | // apply. Collect a list of blocks where control flow will | |
524 | // branch if one of the `target_candidate` sets is not | |
525 | // exhaustive. | |
526 | let otherwise: Vec<_> = | |
527 | target_blocks.into_iter() | |
528 | .zip(target_candidates) | |
529 | .flat_map(|(target_block, target_candidates)| { | |
530 | self.match_candidates(span, | |
531 | arm_blocks, | |
532 | target_candidates, | |
533 | target_block) | |
534 | }) | |
535 | .collect(); | |
536 | ||
537 | (otherwise, tested_candidates) | |
e9174d1e SL |
538 | } |
539 | ||
540 | /// Initializes each of the bindings from the candidate by | |
541 | /// moving/copying/ref'ing the source as appropriate. Tests the | |
542 | /// guard, if any, and then branches to the arm. Returns the block | |
543 | /// for the case where the guard fails. | |
544 | /// | |
545 | /// Note: we check earlier that if there is a guard, there cannot | |
546 | /// be move bindings. This isn't really important for the | |
547 | /// self-consistency of this fn, but the reason for it should be | |
548 | /// clear: after we've done the assignments, if there were move | |
549 | /// bindings, further tests would be a use-after-move (which would | |
550 | /// in turn be detected by the borrowck code that runs on the | |
551 | /// MIR). | |
92a42be0 SL |
552 | fn bind_and_guard_matched_candidate<'pat>(&mut self, |
553 | mut block: BasicBlock, | |
554 | arm_blocks: &mut ArmBlocks, | |
555 | candidate: Candidate<'pat, 'tcx>) | |
556 | -> Option<BasicBlock> { | |
b039eaaf SL |
557 | debug!("bind_and_guard_matched_candidate(block={:?}, candidate={:?})", |
558 | block, candidate); | |
e9174d1e SL |
559 | |
560 | debug_assert!(candidate.match_pairs.is_empty()); | |
561 | ||
b039eaaf SL |
562 | self.bind_matched_candidate(block, candidate.bindings); |
563 | ||
564 | let arm_block = arm_blocks.blocks[candidate.arm_index]; | |
e9174d1e | 565 | |
54a0048b | 566 | let scope_id = self.innermost_scope_id(); |
e9174d1e SL |
567 | if let Some(guard) = candidate.guard { |
568 | // the block to branch to if the guard fails; if there is no | |
569 | // guard, this block is simply unreachable | |
54a0048b SL |
570 | let guard = self.hir.mirror(guard); |
571 | let guard_span = guard.span; | |
e9174d1e SL |
572 | let cond = unpack!(block = self.as_operand(block, guard)); |
573 | let otherwise = self.cfg.start_new_block(); | |
54a0048b SL |
574 | self.cfg.terminate(block, |
575 | scope_id, | |
576 | guard_span, | |
577 | TerminatorKind::If { cond: cond, | |
578 | targets: (arm_block, otherwise)}); | |
e9174d1e SL |
579 | Some(otherwise) |
580 | } else { | |
54a0048b SL |
581 | self.cfg.terminate(block, |
582 | scope_id, | |
583 | candidate.span, | |
584 | TerminatorKind::Goto { target: arm_block }); | |
e9174d1e SL |
585 | None |
586 | } | |
587 | } | |
588 | ||
589 | fn bind_matched_candidate(&mut self, | |
590 | block: BasicBlock, | |
b039eaaf SL |
591 | bindings: Vec<Binding<'tcx>>) { |
592 | debug!("bind_matched_candidate(block={:?}, bindings={:?})", | |
593 | block, bindings); | |
e9174d1e SL |
594 | |
595 | // Assign each of the bindings. This may trigger moves out of the candidate. | |
596 | for binding in bindings { | |
b039eaaf SL |
597 | // Find the variable for the `var_id` being bound. It |
598 | // should have been created by a previous call to | |
599 | // `declare_bindings`. | |
600 | let var_index = self.var_indices[&binding.var_id]; | |
e9174d1e SL |
601 | |
602 | let rvalue = match binding.binding_mode { | |
603 | BindingMode::ByValue => | |
604 | Rvalue::Use(Operand::Consume(binding.source)), | |
605 | BindingMode::ByRef(region, borrow_kind) => | |
606 | Rvalue::Ref(region, borrow_kind, binding.source), | |
607 | }; | |
608 | ||
54a0048b SL |
609 | let scope_id = self.innermost_scope_id(); |
610 | self.cfg.push_assign(block, scope_id, binding.span, | |
611 | &Lvalue::Var(var_index), rvalue); | |
e9174d1e SL |
612 | } |
613 | } | |
614 | ||
615 | fn declare_binding(&mut self, | |
54a0048b | 616 | var_scope_id: ScopeId, |
e9174d1e | 617 | mutability: Mutability, |
b039eaaf SL |
618 | name: Name, |
619 | var_id: NodeId, | |
620 | var_ty: Ty<'tcx>, | |
621 | span: Span) | |
e9174d1e SL |
622 | -> u32 |
623 | { | |
54a0048b SL |
624 | debug!("declare_binding(var_id={:?}, name={:?}, var_ty={:?}, var_scope_id={:?}, span={:?})", |
625 | var_id, name, var_ty, var_scope_id, span); | |
e9174d1e SL |
626 | |
627 | let index = self.var_decls.len(); | |
b039eaaf | 628 | self.var_decls.push(VarDecl::<'tcx> { |
54a0048b | 629 | scope: var_scope_id, |
e9174d1e SL |
630 | mutability: mutability, |
631 | name: name, | |
632 | ty: var_ty.clone(), | |
54a0048b | 633 | span: span, |
e9174d1e SL |
634 | }); |
635 | let index = index as u32; | |
54a0048b SL |
636 | let extent = self.scope_auxiliary[var_scope_id].extent; |
637 | self.schedule_drop(span, extent, &Lvalue::Var(index), var_ty); | |
e9174d1e SL |
638 | self.var_indices.insert(var_id, index); |
639 | ||
640 | debug!("declare_binding: index={:?}", index); | |
641 | ||
642 | index | |
643 | } | |
644 | } |