]>
Commit | Line | Data |
---|---|---|
9fa01778 XL |
1 | //! Code related to match expressions. These are sufficiently complex to |
2 | //! warrant their own module and submodules. :) This main module includes the | |
3 | //! high-level algorithm, the submodules contain the details. | |
4 | //! | |
5 | //! This also includes code for pattern bindings in `let` statements and | |
6 | //! function parameters. | |
7 | ||
dc9dc135 | 8 | use crate::build::scope::DropKind; |
9fa01778 XL |
9 | use crate::build::ForGuard::{self, OutsideGuard, RefWithinGuard}; |
10 | use crate::build::{BlockAnd, BlockAndExtension, Builder}; | |
11 | use crate::build::{GuardFrame, GuardFrameLocal, LocalsForNode}; | |
3dfed10e XL |
12 | use crate::thir::{self, *}; |
13 | use rustc_data_structures::{ | |
14 | fx::{FxHashSet, FxIndexMap}, | |
15 | stack::ensure_sufficient_stack, | |
16 | }; | |
dfeec247 XL |
17 | use rustc_hir::HirId; |
18 | use rustc_index::bit_set::BitSet; | |
ba9703b0 XL |
19 | use rustc_middle::middle::region; |
20 | use rustc_middle::mir::*; | |
21 | use rustc_middle::ty::{self, CanonicalUserTypeAnnotation, Ty}; | |
f9f354fc | 22 | use rustc_span::symbol::Symbol; |
3dfed10e | 23 | use rustc_span::Span; |
ba9703b0 | 24 | use rustc_target::abi::VariantIdx; |
dfeec247 | 25 | use smallvec::{smallvec, SmallVec}; |
e9174d1e SL |
26 | |
27 | // helper functions, broken out by category: | |
28 | mod simplify; | |
29 | mod test; | |
30 | mod util; | |
31 | ||
74b04a01 | 32 | use std::borrow::Borrow; |
0bf4aa26 | 33 | use std::convert::TryFrom; |
74b04a01 | 34 | use std::mem; |
0bf4aa26 | 35 | |
dc9dc135 | 36 | impl<'a, 'tcx> Builder<'a, 'tcx> { |
9fa01778 XL |
37 | /// Generates MIR for a `match` expression. |
38 | /// | |
39 | /// The MIR that we generate for a match looks like this. | |
40 | /// | |
41 | /// ```text | |
42 | /// [ 0. Pre-match ] | |
43 | /// | | |
44 | /// [ 1. Evaluate Scrutinee (expression being matched on) ] | |
45 | /// [ (fake read of scrutinee) ] | |
46 | /// | | |
47 | /// [ 2. Decision tree -- check discriminants ] <--------+ | |
48 | /// | | | |
49 | /// | (once a specific arm is chosen) | | |
50 | /// | | | |
51 | /// [pre_binding_block] [otherwise_block] | |
52 | /// | | | |
53 | /// [ 3. Create "guard bindings" for arm ] | | |
54 | /// [ (create fake borrows) ] | | |
55 | /// | | | |
56 | /// [ 4. Execute guard code ] | | |
57 | /// [ (read fake borrows) ] --(guard is false)-----------+ | |
58 | /// | | |
59 | /// | (guard results in true) | |
60 | /// | | |
61 | /// [ 5. Create real bindings and execute arm ] | |
62 | /// | | |
63 | /// [ Exit match ] | |
64 | /// ``` | |
65 | /// | |
66 | /// All of the different arms have been stacked on top of each other to | |
67 | /// simplify the diagram. For an arm with no guard the blocks marked 3 and | |
68 | /// 4 and the fake borrows are omitted. | |
69 | /// | |
70 | /// We generate MIR in the following steps: | |
71 | /// | |
dfeec247 | 72 | /// 1. Evaluate the scrutinee and add the fake read of it ([Builder::lower_scrutinee]). |
74b04a01 XL |
73 | /// 2. Create the decision tree ([Builder::lower_match_tree]). |
74 | /// 3. Determine the fake borrows that are needed from the places that were | |
dfeec247 XL |
75 | /// matched against and create the required temporaries for them |
76 | /// ([Builder::calculate_fake_borrows]). | |
74b04a01 | 77 | /// 4. Create everything else: the guards and the arms ([Builder::lower_match_arms]). |
9fa01778 XL |
78 | /// |
79 | /// ## False edges | |
80 | /// | |
81 | /// We don't want to have the exact structure of the decision tree be | |
82 | /// visible through borrow checking. False edges ensure that the CFG as | |
83 | /// seen by borrow checking doesn't encode this. False edges are added: | |
84 | /// | |
85 | /// * From each prebinding block to the next prebinding block. | |
86 | /// * From each otherwise block to the next prebinding block. | |
dfeec247 | 87 | crate fn match_expr( |
b7449926 | 88 | &mut self, |
ba9703b0 | 89 | destination: Place<'tcx>, |
b7449926 XL |
90 | span: Span, |
91 | mut block: BasicBlock, | |
9fa01778 | 92 | scrutinee: ExprRef<'tcx>, |
b7449926 XL |
93 | arms: Vec<Arm<'tcx>>, |
94 | ) -> BlockAnd<()> { | |
dfeec247 XL |
95 | let scrutinee_span = scrutinee.span(); |
96 | let scrutinee_place = | |
97 | unpack!(block = self.lower_scrutinee(block, scrutinee, scrutinee_span,)); | |
ff7c6d11 | 98 | |
74b04a01 | 99 | let mut arm_candidates = self.create_match_candidates(scrutinee_place, &arms); |
9fa01778 | 100 | |
dfeec247 | 101 | let match_has_guard = arms.iter().any(|arm| arm.guard.is_some()); |
74b04a01 XL |
102 | let mut candidates = |
103 | arm_candidates.iter_mut().map(|(_, candidate)| candidate).collect::<Vec<_>>(); | |
dfeec247 XL |
104 | |
105 | let fake_borrow_temps = | |
74b04a01 | 106 | self.lower_match_tree(block, scrutinee_span, match_has_guard, &mut candidates); |
dfeec247 XL |
107 | |
108 | self.lower_match_arms( | |
74b04a01 | 109 | destination, |
dfeec247 XL |
110 | scrutinee_place, |
111 | scrutinee_span, | |
112 | arm_candidates, | |
113 | self.source_info(span), | |
114 | fake_borrow_temps, | |
115 | ) | |
116 | } | |
9fa01778 | 117 | |
dfeec247 XL |
118 | /// Evaluate the scrutinee and add the fake read of it. |
119 | fn lower_scrutinee( | |
120 | &mut self, | |
121 | mut block: BasicBlock, | |
122 | scrutinee: ExprRef<'tcx>, | |
123 | scrutinee_span: Span, | |
124 | ) -> BlockAnd<Place<'tcx>> { | |
125 | let scrutinee_place = unpack!(block = self.as_place(block, scrutinee)); | |
9fa01778 | 126 | // Matching on a `scrutinee_place` with an uninhabited type doesn't |
ff7c6d11 XL |
127 | // generate any memory reads by itself, and so if the place "expression" |
128 | // contains unsafe operations like raw pointer dereferences or union | |
129 | // field projections, we wouldn't know to require an `unsafe` block | |
130 | // around a `match` equivalent to `std::intrinsics::unreachable()`. | |
131 | // See issue #47412 for this hole being discovered in the wild. | |
132 | // | |
133 | // HACK(eddyb) Work around the above issue by adding a dummy inspection | |
9fa01778 | 134 | // of `scrutinee_place`, specifically by applying `ReadForMatch`. |
94b46f34 | 135 | // |
9fa01778 | 136 | // NOTE: ReadForMatch also checks that the scrutinee is initialized. |
0bf4aa26 XL |
137 | // This is currently needed to not allow matching on an uninitialized, |
138 | // uninhabited value. If we get never patterns, those will check that | |
139 | // the place is initialized, and so this read would only be used to | |
140 | // check safety. | |
60c5eb7d | 141 | let cause_matched_place = FakeReadCause::ForMatchedPlace; |
dfeec247 | 142 | let source_info = self.source_info(scrutinee_span); |
74b04a01 | 143 | self.cfg.push_fake_read(block, source_info, cause_matched_place, scrutinee_place); |
94b46f34 | 144 | |
dfeec247 XL |
145 | block.and(scrutinee_place) |
146 | } | |
e9174d1e | 147 | |
dfeec247 XL |
148 | /// Create the initial `Candidate`s for a `match` expression. |
149 | fn create_match_candidates<'pat>( | |
150 | &mut self, | |
74b04a01 | 151 | scrutinee: Place<'tcx>, |
dfeec247 | 152 | arms: &'pat [Arm<'tcx>], |
74b04a01 | 153 | ) -> Vec<(&'pat Arm<'tcx>, Candidate<'pat, 'tcx>)> { |
9fa01778 XL |
154 | // Assemble a list of candidates: there is one candidate per pattern, |
155 | // which means there may be more than one candidate *per arm*. | |
dfeec247 | 156 | arms.iter() |
9fa01778 XL |
157 | .map(|arm| { |
158 | let arm_has_guard = arm.guard.is_some(); | |
74b04a01 XL |
159 | let arm_candidate = Candidate::new(scrutinee, &arm.pattern, arm_has_guard); |
160 | (arm, arm_candidate) | |
9fa01778 | 161 | }) |
dfeec247 XL |
162 | .collect() |
163 | } | |
9fa01778 | 164 | |
dfeec247 XL |
165 | /// Create the decision tree for the match expression, starting from `block`. |
166 | /// | |
167 | /// Modifies `candidates` to store the bindings and type ascriptions for | |
168 | /// that candidate. | |
169 | /// | |
170 | /// Returns the places that need fake borrows because we bind or test them. | |
171 | fn lower_match_tree<'pat>( | |
172 | &mut self, | |
173 | block: BasicBlock, | |
174 | scrutinee_span: Span, | |
175 | match_has_guard: bool, | |
74b04a01 | 176 | candidates: &mut [&mut Candidate<'pat, 'tcx>], |
dfeec247 | 177 | ) -> Vec<(Place<'tcx>, Local)> { |
9fa01778 XL |
178 | // The set of places that we are creating fake borrows of. If there are |
179 | // no match guards then we don't need any fake borrows, so don't track | |
180 | // them. | |
dfeec247 | 181 | let mut fake_borrows = if match_has_guard { Some(FxHashSet::default()) } else { None }; |
0bf4aa26 | 182 | |
74b04a01 XL |
183 | let mut otherwise = None; |
184 | ||
dfeec247 | 185 | // This will generate code to test scrutinee_place and |
e9174d1e | 186 | // branch to the appropriate arm block |
74b04a01 XL |
187 | self.match_candidates(scrutinee_span, block, &mut otherwise, candidates, &mut fake_borrows); |
188 | ||
189 | if let Some(otherwise_block) = otherwise { | |
190 | // See the doc comment on `match_candidates` for why we may have an | |
191 | // otherwise block. Match checking will ensure this is actually | |
192 | // unreachable. | |
193 | let source_info = self.source_info(scrutinee_span); | |
194 | self.cfg.terminate(otherwise_block, source_info, TerminatorKind::Unreachable); | |
195 | } | |
196 | ||
197 | // Link each leaf candidate to the `pre_binding_block` of the next one. | |
198 | let mut previous_candidate: Option<&mut Candidate<'_, '_>> = None; | |
199 | ||
200 | for candidate in candidates { | |
201 | candidate.visit_leaves(|leaf_candidate| { | |
202 | if let Some(ref mut prev) = previous_candidate { | |
203 | prev.next_candidate_pre_binding_block = leaf_candidate.pre_binding_block; | |
204 | } | |
205 | previous_candidate = Some(leaf_candidate); | |
206 | }); | |
207 | } | |
92a42be0 | 208 | |
dfeec247 | 209 | if let Some(ref borrows) = fake_borrows { |
9fa01778 XL |
210 | self.calculate_fake_borrows(borrows, scrutinee_span) |
211 | } else { | |
212 | Vec::new() | |
dfeec247 XL |
213 | } |
214 | } | |
9fa01778 | 215 | |
dfeec247 XL |
216 | /// Lower the bindings, guards and arm bodies of a `match` expression. |
217 | /// | |
218 | /// The decision tree should have already been created | |
219 | /// (by [Builder::lower_match_tree]). | |
220 | /// | |
221 | /// `outer_source_info` is the SourceInfo for the whole match. | |
222 | fn lower_match_arms( | |
223 | &mut self, | |
ba9703b0 | 224 | destination: Place<'tcx>, |
dfeec247 XL |
225 | scrutinee_place: Place<'tcx>, |
226 | scrutinee_span: Span, | |
74b04a01 | 227 | arm_candidates: Vec<(&'_ Arm<'tcx>, Candidate<'_, 'tcx>)>, |
dfeec247 XL |
228 | outer_source_info: SourceInfo, |
229 | fake_borrow_temps: Vec<(Place<'tcx>, Local)>, | |
230 | ) -> BlockAnd<()> { | |
416331ca XL |
231 | let match_scope = self.scopes.topmost(); |
232 | ||
dfeec247 XL |
233 | let arm_end_blocks: Vec<_> = arm_candidates |
234 | .into_iter() | |
74b04a01 XL |
235 | .map(|(arm, candidate)| { |
236 | debug!("lowering arm {:?}\ncanidate = {:?}", arm, candidate); | |
dfeec247 XL |
237 | |
238 | let arm_source_info = self.source_info(arm.span); | |
239 | let arm_scope = (arm.scope, arm_source_info); | |
240 | self.in_scope(arm_scope, arm.lint_level, |this| { | |
241 | let body = this.hir.mirror(arm.body.clone()); | |
242 | let scope = this.declare_bindings( | |
243 | None, | |
244 | arm.span, | |
74b04a01 | 245 | &arm.pattern, |
dfeec247 XL |
246 | ArmHasGuard(arm.guard.is_some()), |
247 | Some((Some(&scrutinee_place), scrutinee_span)), | |
248 | ); | |
9fa01778 | 249 | |
dfeec247 XL |
250 | let arm_block = this.bind_pattern( |
251 | outer_source_info, | |
74b04a01 | 252 | candidate, |
dfeec247 | 253 | arm.guard.as_ref().map(|g| (g, match_scope)), |
dc9dc135 XL |
254 | &fake_borrow_temps, |
255 | scrutinee_span, | |
74b04a01 | 256 | Some(arm.scope), |
dc9dc135 | 257 | ); |
9fa01778 | 258 | |
dfeec247 XL |
259 | if let Some(source_scope) = scope { |
260 | this.source_scope = source_scope; | |
261 | } | |
9fa01778 | 262 | |
dfeec247 XL |
263 | this.into(destination, arm_block, body) |
264 | }) | |
dc9dc135 | 265 | }) |
dfeec247 | 266 | .collect(); |
9fa01778 XL |
267 | |
268 | // all the arm blocks will rejoin here | |
269 | let end_block = self.cfg.start_new_block(); | |
270 | ||
271 | for arm_block in arm_end_blocks { | |
dfeec247 | 272 | self.cfg.goto(unpack!(arm_block), outer_source_info, end_block); |
e9174d1e | 273 | } |
9fa01778 | 274 | |
94b46f34 | 275 | self.source_scope = outer_source_info.scope; |
e9174d1e SL |
276 | |
277 | end_block.unit() | |
278 | } | |
279 | ||
74b04a01 XL |
280 | /// Binds the variables and ascribes types for a given `match` arm or |
281 | /// `let` binding. | |
dfeec247 XL |
282 | /// |
283 | /// Also check if the guard matches, if it's provided. | |
74b04a01 XL |
284 | /// `arm_scope` should be `Some` if and only if this is called for a |
285 | /// `match` arm. | |
dfeec247 XL |
286 | fn bind_pattern( |
287 | &mut self, | |
288 | outer_source_info: SourceInfo, | |
74b04a01 | 289 | candidate: Candidate<'_, 'tcx>, |
dfeec247 XL |
290 | guard: Option<(&Guard<'tcx>, region::Scope)>, |
291 | fake_borrow_temps: &Vec<(Place<'tcx>, Local)>, | |
292 | scrutinee_span: Span, | |
74b04a01 | 293 | arm_scope: Option<region::Scope>, |
dfeec247 | 294 | ) -> BasicBlock { |
74b04a01 | 295 | if candidate.subcandidates.is_empty() { |
dfeec247 XL |
296 | // Avoid generating another `BasicBlock` when we only have one |
297 | // candidate. | |
298 | self.bind_and_guard_matched_candidate( | |
74b04a01 XL |
299 | candidate, |
300 | &[], | |
dfeec247 XL |
301 | guard, |
302 | fake_borrow_temps, | |
303 | scrutinee_span, | |
74b04a01 | 304 | true, |
dfeec247 XL |
305 | ) |
306 | } else { | |
74b04a01 XL |
307 | // It's helpful to avoid scheduling drops multiple times to save |
308 | // drop elaboration from having to clean up the extra drops. | |
309 | // | |
310 | // If we are in a `let` then we only schedule drops for the first | |
311 | // candidate. | |
312 | // | |
313 | // If we're in a `match` arm then we could have a case like so: | |
314 | // | |
315 | // Ok(x) | Err(x) if return => { /* ... */ } | |
316 | // | |
317 | // In this case we don't want a drop of `x` scheduled when we | |
318 | // return: it isn't bound by move until right before enter the arm. | |
319 | // To handle this we instead unschedule it's drop after each time | |
320 | // we lower the guard. | |
321 | let target_block = self.cfg.start_new_block(); | |
322 | let mut schedule_drops = true; | |
323 | // We keep a stack of all of the bindings and type asciptions | |
324 | // from the the parent candidates that we visit, that also need to | |
325 | // be bound for each candidate. | |
326 | traverse_candidate( | |
327 | candidate, | |
328 | &mut Vec::new(), | |
329 | &mut |leaf_candidate, parent_bindings| { | |
330 | if let Some(arm_scope) = arm_scope { | |
331 | self.clear_top_scope(arm_scope); | |
332 | } | |
333 | let binding_end = self.bind_and_guard_matched_candidate( | |
334 | leaf_candidate, | |
335 | parent_bindings, | |
336 | guard, | |
337 | &fake_borrow_temps, | |
338 | scrutinee_span, | |
339 | schedule_drops, | |
340 | ); | |
341 | if arm_scope.is_none() { | |
342 | schedule_drops = false; | |
343 | } | |
344 | self.cfg.goto(binding_end, outer_source_info, target_block); | |
345 | }, | |
346 | |inner_candidate, parent_bindings| { | |
347 | parent_bindings.push((inner_candidate.bindings, inner_candidate.ascriptions)); | |
348 | inner_candidate.subcandidates.into_iter() | |
349 | }, | |
350 | |parent_bindings| { | |
351 | parent_bindings.pop(); | |
352 | }, | |
353 | ); | |
354 | ||
355 | target_block | |
dfeec247 XL |
356 | } |
357 | } | |
358 | ||
0bf4aa26 | 359 | pub(super) fn expr_into_pattern( |
b7449926 XL |
360 | &mut self, |
361 | mut block: BasicBlock, | |
e74abb32 | 362 | irrefutable_pat: Pat<'tcx>, |
b7449926 XL |
363 | initializer: ExprRef<'tcx>, |
364 | ) -> BlockAnd<()> { | |
92a42be0 | 365 | match *irrefutable_pat.kind { |
b7449926 | 366 | // Optimize the case of `let x = ...` to write directly into `x` |
dfeec247 | 367 | PatKind::Binding { mode: BindingMode::ByValue, var, subpattern: None, .. } => { |
b7449926 | 368 | let place = |
74b04a01 | 369 | self.storage_live_binding(block, var, irrefutable_pat.span, OutsideGuard, true); |
ba9703b0 | 370 | unpack!(block = self.into(place, block, initializer)); |
0bf4aa26 | 371 | |
0bf4aa26 XL |
372 | // Inject a fake read, see comments on `FakeReadCause::ForLet`. |
373 | let source_info = self.source_info(irrefutable_pat.span); | |
60c5eb7d | 374 | self.cfg.push_fake_read(block, source_info, FakeReadCause::ForLet, place); |
0bf4aa26 | 375 | |
b7449926 XL |
376 | self.schedule_drop_for_binding(var, irrefutable_pat.span, OutsideGuard); |
377 | block.unit() | |
378 | } | |
0531ce1d | 379 | |
b7449926 XL |
380 | // Optimize the case of `let x: T = ...` to write directly |
381 | // into `x` and then require that `T == typeof(x)`. | |
382 | // | |
383 | // Weirdly, this is needed to prevent the | |
384 | // `intrinsic-move-val.rs` test case from crashing. That | |
385 | // test works with uninitialized values in a rather | |
386 | // dubious way, so it may be that the test is kind of | |
387 | // broken. | |
e74abb32 | 388 | PatKind::AscribeUserType { |
dfeec247 XL |
389 | subpattern: |
390 | Pat { | |
391 | kind: | |
392 | box PatKind::Binding { | |
393 | mode: BindingMode::ByValue, | |
394 | var, | |
395 | subpattern: None, | |
396 | .. | |
397 | }, | |
b7449926 XL |
398 | .. |
399 | }, | |
dfeec247 | 400 | ascription: |
3dfed10e | 401 | thir::pattern::Ascription { user_ty: pat_ascription_ty, variance: _, user_ty_span }, |
b7449926 XL |
402 | } => { |
403 | let place = | |
74b04a01 | 404 | self.storage_live_binding(block, var, irrefutable_pat.span, OutsideGuard, true); |
ba9703b0 | 405 | unpack!(block = self.into(place, block, initializer)); |
b7449926 | 406 | |
0bf4aa26 XL |
407 | // Inject a fake read, see comments on `FakeReadCause::ForLet`. |
408 | let pattern_source_info = self.source_info(irrefutable_pat.span); | |
60c5eb7d | 409 | let cause_let = FakeReadCause::ForLet; |
74b04a01 | 410 | self.cfg.push_fake_read(block, pattern_source_info, cause_let, place); |
0bf4aa26 XL |
411 | |
412 | let ty_source_info = self.source_info(user_ty_span); | |
e1599b0c | 413 | let user_ty = pat_ascription_ty.user_ty( |
9fa01778 | 414 | &mut self.canonical_user_type_annotations, |
532ac7d7 | 415 | place.ty(&self.local_decls, self.hir.tcx()).ty, |
9fa01778 | 416 | ty_source_info.span, |
0731742a | 417 | ); |
0bf4aa26 XL |
418 | self.cfg.push( |
419 | block, | |
420 | Statement { | |
421 | source_info: ty_source_info, | |
b7449926 | 422 | kind: StatementKind::AscribeUserType( |
dfeec247 | 423 | box (place, user_ty), |
0731742a XL |
424 | // We always use invariant as the variance here. This is because the |
425 | // variance field from the ascription refers to the variance to use | |
426 | // when applying the type to the value being matched, but this | |
427 | // ascription applies rather to the type of the binding. e.g., in this | |
428 | // example: | |
429 | // | |
430 | // ``` | |
431 | // let x: T = <expr> | |
432 | // ``` | |
433 | // | |
434 | // We are creating an ascription that defines the type of `x` to be | |
435 | // exactly `T` (i.e., with invariance). The variance field, in | |
436 | // contrast, is intended to be used to relate `T` to the type of | |
437 | // `<expr>`. | |
b7449926 | 438 | ty::Variance::Invariant, |
b7449926 XL |
439 | ), |
440 | }, | |
441 | ); | |
442 | ||
83c7162d | 443 | self.schedule_drop_for_binding(var, irrefutable_pat.span, OutsideGuard); |
8bb4bdeb XL |
444 | block.unit() |
445 | } | |
9fa01778 | 446 | |
8bb4bdeb | 447 | _ => { |
ff7c6d11 | 448 | let place = unpack!(block = self.as_place(block, initializer)); |
74b04a01 | 449 | self.place_into_pattern(block, irrefutable_pat, place, true) |
e9174d1e | 450 | } |
e9174d1e | 451 | } |
e9174d1e SL |
452 | } |
453 | ||
dfeec247 | 454 | crate fn place_into_pattern( |
b7449926 | 455 | &mut self, |
0731742a | 456 | block: BasicBlock, |
e74abb32 | 457 | irrefutable_pat: Pat<'tcx>, |
74b04a01 | 458 | initializer: Place<'tcx>, |
b7449926 XL |
459 | set_match_place: bool, |
460 | ) -> BlockAnd<()> { | |
74b04a01 | 461 | let mut candidate = Candidate::new(initializer, &irrefutable_pat, false); |
e9174d1e | 462 | |
74b04a01 XL |
463 | let fake_borrow_temps = |
464 | self.lower_match_tree(block, irrefutable_pat.span, false, &mut [&mut candidate]); | |
e9174d1e | 465 | |
74b04a01 | 466 | // For matches and function arguments, the place that is being matched |
8faf50e0 XL |
467 | // can be set when creating the variables. But the place for |
468 | // let PATTERN = ... might not even exist until we do the assignment. | |
74b04a01 | 469 | // so we set it here instead. |
8faf50e0 | 470 | if set_match_place { |
74b04a01 XL |
471 | let mut candidate_ref = &candidate; |
472 | while let Some(next) = { | |
473 | for binding in &candidate_ref.bindings { | |
474 | let local = self.var_local_id(binding.var_id, OutsideGuard); | |
475 | ||
f9f354fc | 476 | if let Some(box LocalInfo::User(ClearCrossCrate::Set(BindingForm::Var( |
74b04a01 | 477 | VarBindingForm { opt_match_place: Some((ref mut match_place, _)), .. }, |
f9f354fc | 478 | )))) = self.local_decls[local].local_info |
74b04a01 XL |
479 | { |
480 | *match_place = Some(initializer); | |
481 | } else { | |
482 | bug!("Let binding to non-user variable.") | |
483 | } | |
8faf50e0 | 484 | } |
74b04a01 XL |
485 | // All of the subcandidates should bind the same locals, so we |
486 | // only visit the first one. | |
487 | candidate_ref.subcandidates.get(0) | |
488 | } { | |
489 | candidate_ref = next; | |
8faf50e0 XL |
490 | } |
491 | } | |
492 | ||
74b04a01 XL |
493 | self.bind_pattern( |
494 | self.source_info(irrefutable_pat.span), | |
495 | candidate, | |
496 | None, | |
497 | &fake_borrow_temps, | |
498 | irrefutable_pat.span, | |
499 | None, | |
500 | ) | |
501 | .unit() | |
e9174d1e SL |
502 | } |
503 | ||
b7449926 XL |
504 | /// Declares the bindings of the given patterns and returns the visibility |
505 | /// scope for the bindings in these patterns, if such a scope had to be | |
506 | /// created. NOTE: Declaring the bindings should always be done in their | |
507 | /// drop scope. | |
dfeec247 | 508 | crate fn declare_bindings( |
b7449926 XL |
509 | &mut self, |
510 | mut visibility_scope: Option<SourceScope>, | |
511 | scope_span: Span, | |
e74abb32 | 512 | pattern: &Pat<'tcx>, |
b7449926 XL |
513 | has_guard: ArmHasGuard, |
514 | opt_match_place: Option<(Option<&Place<'tcx>>, Span)>, | |
515 | ) -> Option<SourceScope> { | |
9fa01778 | 516 | debug!("declare_bindings: pattern={:?}", pattern); |
f9f354fc | 517 | self.visit_primary_bindings( |
9fa01778 | 518 | &pattern, |
0731742a | 519 | UserTypeProjections::none(), |
b7449926 XL |
520 | &mut |this, mutability, name, mode, var, span, ty, user_ty| { |
521 | if visibility_scope.is_none() { | |
dc9dc135 XL |
522 | visibility_scope = |
523 | Some(this.new_source_scope(scope_span, LintLevel::Inherited, None)); | |
ea8adc8c | 524 | } |
dc9dc135 | 525 | let source_info = SourceInfo { span, scope: this.source_scope }; |
b7449926 XL |
526 | let visibility_scope = visibility_scope.unwrap(); |
527 | this.declare_binding( | |
528 | source_info, | |
529 | visibility_scope, | |
530 | mutability, | |
531 | name, | |
532 | mode, | |
b7449926 XL |
533 | var, |
534 | ty, | |
535 | user_ty, | |
536 | has_guard, | |
537 | opt_match_place.map(|(x, y)| (x.cloned(), y)), | |
9fa01778 | 538 | pattern.span, |
b7449926 XL |
539 | ); |
540 | }, | |
541 | ); | |
94b46f34 | 542 | visibility_scope |
e9174d1e | 543 | } |
5bcae85e | 544 | |
dfeec247 | 545 | crate fn storage_live_binding( |
b7449926 XL |
546 | &mut self, |
547 | block: BasicBlock, | |
532ac7d7 | 548 | var: HirId, |
b7449926 XL |
549 | span: Span, |
550 | for_guard: ForGuard, | |
74b04a01 | 551 | schedule_drop: bool, |
b7449926 | 552 | ) -> Place<'tcx> { |
83c7162d | 553 | let local_id = self.var_local_id(var, for_guard); |
8bb4bdeb | 554 | let source_info = self.source_info(span); |
dfeec247 | 555 | self.cfg.push(block, Statement { source_info, kind: StatementKind::StorageLive(local_id) }); |
532ac7d7 | 556 | let region_scope = self.hir.region_scope_tree.var_scope(var.local_id); |
74b04a01 XL |
557 | if schedule_drop { |
558 | self.schedule_drop(span, region_scope, local_id, DropKind::Storage); | |
559 | } | |
416331ca | 560 | Place::from(local_id) |
8bb4bdeb | 561 | } |
5bcae85e | 562 | |
dfeec247 | 563 | crate fn schedule_drop_for_binding(&mut self, var: HirId, span: Span, for_guard: ForGuard) { |
83c7162d | 564 | let local_id = self.var_local_id(var, for_guard); |
532ac7d7 | 565 | let region_scope = self.hir.region_scope_tree.var_scope(var.local_id); |
dfeec247 | 566 | self.schedule_drop(span, region_scope, local_id, DropKind::Value); |
8bb4bdeb XL |
567 | } |
568 | ||
f9f354fc XL |
569 | /// Visit all of the primary bindings in a patterns, that is, visit the |
570 | /// leftmost occurrence of each variable bound in a pattern. A variable | |
571 | /// will occur more than once in an or-pattern. | |
572 | pub(super) fn visit_primary_bindings( | |
b7449926 | 573 | &mut self, |
e74abb32 | 574 | pattern: &Pat<'tcx>, |
532ac7d7 | 575 | pattern_user_ty: UserTypeProjections, |
b7449926 XL |
576 | f: &mut impl FnMut( |
577 | &mut Self, | |
578 | Mutability, | |
f9f354fc | 579 | Symbol, |
b7449926 | 580 | BindingMode, |
532ac7d7 | 581 | HirId, |
b7449926 XL |
582 | Span, |
583 | Ty<'tcx>, | |
532ac7d7 | 584 | UserTypeProjections, |
b7449926 XL |
585 | ), |
586 | ) { | |
f9f354fc XL |
587 | debug!( |
588 | "visit_primary_bindings: pattern={:?} pattern_user_ty={:?}", | |
589 | pattern, pattern_user_ty | |
590 | ); | |
8bb4bdeb | 591 | match *pattern.kind { |
f9f354fc XL |
592 | PatKind::Binding { |
593 | mutability, | |
594 | name, | |
595 | mode, | |
596 | var, | |
597 | ty, | |
598 | ref subpattern, | |
599 | is_primary, | |
600 | .. | |
601 | } => { | |
602 | if is_primary { | |
603 | f(self, mutability, name, mode, var, pattern.span, ty, pattern_user_ty.clone()); | |
604 | } | |
5bcae85e | 605 | if let Some(subpattern) = subpattern.as_ref() { |
f9f354fc | 606 | self.visit_primary_bindings(subpattern, pattern_user_ty, f); |
5bcae85e SL |
607 | } |
608 | } | |
9fa01778 | 609 | |
dfeec247 XL |
610 | PatKind::Array { ref prefix, ref slice, ref suffix } |
611 | | PatKind::Slice { ref prefix, ref slice, ref suffix } => { | |
0bf4aa26 XL |
612 | let from = u32::try_from(prefix.len()).unwrap(); |
613 | let to = u32::try_from(suffix.len()).unwrap(); | |
614 | for subpattern in prefix { | |
f9f354fc | 615 | self.visit_primary_bindings(subpattern, pattern_user_ty.clone().index(), f); |
0bf4aa26 XL |
616 | } |
617 | for subpattern in slice { | |
f9f354fc XL |
618 | self.visit_primary_bindings( |
619 | subpattern, | |
620 | pattern_user_ty.clone().subslice(from, to), | |
621 | f, | |
622 | ); | |
0bf4aa26 XL |
623 | } |
624 | for subpattern in suffix { | |
f9f354fc | 625 | self.visit_primary_bindings(subpattern, pattern_user_ty.clone().index(), f); |
5bcae85e SL |
626 | } |
627 | } | |
9fa01778 | 628 | |
e74abb32 | 629 | PatKind::Constant { .. } | PatKind::Range { .. } | PatKind::Wild => {} |
9fa01778 | 630 | |
e74abb32 | 631 | PatKind::Deref { ref subpattern } => { |
f9f354fc | 632 | self.visit_primary_bindings(subpattern, pattern_user_ty.deref(), f); |
5bcae85e | 633 | } |
9fa01778 | 634 | |
e74abb32 | 635 | PatKind::AscribeUserType { |
0731742a | 636 | ref subpattern, |
3dfed10e | 637 | ascription: thir::pattern::Ascription { ref user_ty, user_ty_span, variance: _ }, |
0731742a | 638 | } => { |
b7449926 XL |
639 | // This corresponds to something like |
640 | // | |
641 | // ``` | |
0bf4aa26 | 642 | // let A::<'a>(_): A<'static> = ...; |
b7449926 | 643 | // ``` |
0731742a XL |
644 | // |
645 | // Note that the variance doesn't apply here, as we are tracking the effect | |
646 | // of `user_ty` on any bindings contained with subpattern. | |
9fa01778 XL |
647 | let annotation = CanonicalUserTypeAnnotation { |
648 | span: user_ty_span, | |
649 | user_ty: user_ty.user_ty, | |
650 | inferred_ty: subpattern.ty, | |
651 | }; | |
0731742a XL |
652 | let projection = UserTypeProjection { |
653 | base: self.canonical_user_type_annotations.push(annotation), | |
9fa01778 | 654 | projs: Vec::new(), |
0731742a XL |
655 | }; |
656 | let subpattern_user_ty = pattern_user_ty.push_projection(&projection, user_ty_span); | |
f9f354fc | 657 | self.visit_primary_bindings(subpattern, subpattern_user_ty, f) |
b7449926 | 658 | } |
0bf4aa26 | 659 | |
e74abb32 | 660 | PatKind::Leaf { ref subpatterns } => { |
5bcae85e | 661 | for subpattern in subpatterns { |
0731742a | 662 | let subpattern_user_ty = pattern_user_ty.clone().leaf(subpattern.field); |
f9f354fc XL |
663 | debug!("visit_primary_bindings: subpattern_user_ty={:?}", subpattern_user_ty); |
664 | self.visit_primary_bindings(&subpattern.pattern, subpattern_user_ty, f); | |
0bf4aa26 XL |
665 | } |
666 | } | |
667 | ||
e74abb32 | 668 | PatKind::Variant { adt_def, substs: _, variant_index, ref subpatterns } => { |
0bf4aa26 | 669 | for subpattern in subpatterns { |
dfeec247 XL |
670 | let subpattern_user_ty = |
671 | pattern_user_ty.clone().variant(adt_def, variant_index, subpattern.field); | |
f9f354fc | 672 | self.visit_primary_bindings(&subpattern.pattern, subpattern_user_ty, f); |
5bcae85e SL |
673 | } |
674 | } | |
e74abb32 | 675 | PatKind::Or { ref pats } => { |
f9f354fc XL |
676 | // In cases where we recover from errors the primary bindings |
677 | // may not all be in the leftmost subpattern. For example in | |
678 | // `let (x | y) = ...`, the primary binding of `y` occurs in | |
679 | // the right subpattern | |
680 | for subpattern in pats { | |
681 | self.visit_primary_bindings(subpattern, pattern_user_ty.clone(), f); | |
682 | } | |
e1599b0c | 683 | } |
5bcae85e SL |
684 | } |
685 | } | |
e9174d1e SL |
686 | } |
687 | ||
9fa01778 | 688 | #[derive(Debug)] |
74b04a01 XL |
689 | struct Candidate<'pat, 'tcx> { |
690 | /// `Span` of the original pattern that gave rise to this candidate | |
54a0048b SL |
691 | span: Span, |
692 | ||
74b04a01 XL |
693 | /// This `Candidate` has a guard. |
694 | has_guard: bool, | |
695 | ||
696 | /// All of these must be satisfied... | |
60c5eb7d | 697 | match_pairs: SmallVec<[MatchPair<'pat, 'tcx>; 1]>, |
e9174d1e | 698 | |
74b04a01 | 699 | /// ...these bindings established... |
b039eaaf | 700 | bindings: Vec<Binding<'tcx>>, |
e9174d1e | 701 | |
74b04a01 | 702 | /// ...and these types asserted... |
b7449926 XL |
703 | ascriptions: Vec<Ascription<'tcx>>, |
704 | ||
74b04a01 XL |
705 | /// ... and if this is non-empty, one of these subcandidates also has to match ... |
706 | subcandidates: Vec<Candidate<'pat, 'tcx>>, | |
707 | ||
708 | /// ...and the guard must be evaluated, if false branch to Block... | |
9fa01778 | 709 | otherwise_block: Option<BasicBlock>, |
abe05a73 | 710 | |
74b04a01 XL |
711 | /// ...and the blocks for add false edges between candidates |
712 | pre_binding_block: Option<BasicBlock>, | |
dc9dc135 | 713 | next_candidate_pre_binding_block: Option<BasicBlock>, |
e9174d1e SL |
714 | } |
715 | ||
74b04a01 XL |
716 | impl<'tcx, 'pat> Candidate<'pat, 'tcx> { |
717 | fn new(place: Place<'tcx>, pattern: &'pat Pat<'tcx>, has_guard: bool) -> Self { | |
718 | Candidate { | |
719 | span: pattern.span, | |
720 | has_guard, | |
721 | match_pairs: smallvec![MatchPair { place, pattern }], | |
722 | bindings: Vec::new(), | |
723 | ascriptions: Vec::new(), | |
724 | subcandidates: Vec::new(), | |
725 | otherwise_block: None, | |
726 | pre_binding_block: None, | |
727 | next_candidate_pre_binding_block: None, | |
728 | } | |
729 | } | |
730 | ||
731 | /// Visit the leaf candidates (those with no subcandidates) contained in | |
732 | /// this candidate. | |
733 | fn visit_leaves<'a>(&'a mut self, mut visit_leaf: impl FnMut(&'a mut Self)) { | |
734 | traverse_candidate( | |
735 | self, | |
736 | &mut (), | |
737 | &mut move |c, _| visit_leaf(c), | |
738 | move |c, _| c.subcandidates.iter_mut(), | |
739 | |_| {}, | |
740 | ); | |
741 | } | |
742 | } | |
743 | ||
744 | /// A depth-first traversal of the `Candidate` and all of its recursive | |
745 | /// subcandidates. | |
746 | fn traverse_candidate<'pat, 'tcx: 'pat, C, T, I>( | |
747 | candidate: C, | |
748 | context: &mut T, | |
749 | visit_leaf: &mut impl FnMut(C, &mut T), | |
750 | get_children: impl Copy + Fn(C, &mut T) -> I, | |
751 | complete_children: impl Copy + Fn(&mut T), | |
752 | ) where | |
753 | C: Borrow<Candidate<'pat, 'tcx>>, | |
754 | I: Iterator<Item = C>, | |
755 | { | |
756 | if candidate.borrow().subcandidates.is_empty() { | |
757 | visit_leaf(candidate, context) | |
758 | } else { | |
759 | for child in get_children(candidate, context) { | |
760 | traverse_candidate(child, context, visit_leaf, get_children, complete_children); | |
761 | } | |
762 | complete_children(context) | |
763 | } | |
764 | } | |
765 | ||
e9174d1e | 766 | #[derive(Clone, Debug)] |
b039eaaf SL |
767 | struct Binding<'tcx> { |
768 | span: Span, | |
ff7c6d11 | 769 | source: Place<'tcx>, |
f9f354fc | 770 | name: Symbol, |
532ac7d7 | 771 | var_id: HirId, |
b039eaaf | 772 | var_ty: Ty<'tcx>, |
e9174d1e | 773 | mutability: Mutability, |
0731742a | 774 | binding_mode: BindingMode, |
e9174d1e SL |
775 | } |
776 | ||
b7449926 XL |
777 | /// Indicates that the type of `source` must be a subtype of the |
778 | /// user-given type `user_ty`; this is basically a no-op but can | |
779 | /// influence region inference. | |
780 | #[derive(Clone, Debug)] | |
781 | struct Ascription<'tcx> { | |
782 | span: Span, | |
783 | source: Place<'tcx>, | |
e74abb32 | 784 | user_ty: PatTyProj<'tcx>, |
0731742a | 785 | variance: ty::Variance, |
b7449926 XL |
786 | } |
787 | ||
e9174d1e | 788 | #[derive(Clone, Debug)] |
dfeec247 | 789 | crate struct MatchPair<'pat, 'tcx> { |
ff7c6d11 XL |
790 | // this place... |
791 | place: Place<'tcx>, | |
e9174d1e SL |
792 | |
793 | // ... must match this pattern. | |
e74abb32 | 794 | pattern: &'pat Pat<'tcx>, |
e9174d1e SL |
795 | } |
796 | ||
797 | #[derive(Clone, Debug, PartialEq)] | |
b039eaaf | 798 | enum TestKind<'tcx> { |
dc9dc135 | 799 | /// Test the branches of enum. |
b039eaaf | 800 | Switch { |
dc9dc135 | 801 | /// The enum being tested |
ea8adc8c | 802 | adt_def: &'tcx ty::AdtDef, |
dc9dc135 XL |
803 | /// The set of variants that we should create a branch for. We also |
804 | /// create an additional "otherwise" case. | |
a1dfa0c6 | 805 | variants: BitSet<VariantIdx>, |
b039eaaf | 806 | }, |
e9174d1e | 807 | |
dc9dc135 | 808 | /// Test what value an `integer`, `bool` or `char` has. |
92a42be0 | 809 | SwitchInt { |
dc9dc135 | 810 | /// The type of the value that we're testing. |
92a42be0 | 811 | switch_ty: Ty<'tcx>, |
dc9dc135 XL |
812 | /// The (ordered) set of values that we test for. |
813 | /// | |
814 | /// For integers and `char`s we create a branch to each of the values in | |
815 | /// `options`, as well as an "otherwise" branch for all other values, even | |
816 | /// in the (rare) case that options is exhaustive. | |
817 | /// | |
818 | /// For `bool` we always generate two edges, one for `true` and one for | |
819 | /// `false`. | |
3dfed10e | 820 | options: FxIndexMap<&'tcx ty::Const<'tcx>, u128>, |
92a42be0 SL |
821 | }, |
822 | ||
dc9dc135 XL |
823 | /// Test for equality with value, possibly after an unsizing coercion to |
824 | /// `ty`, | |
b039eaaf | 825 | Eq { |
dc9dc135 XL |
826 | value: &'tcx ty::Const<'tcx>, |
827 | // Integer types are handled by `SwitchInt`, and constants with ADT | |
828 | // types are converted back into patterns, so this can only be `&str`, | |
829 | // `&[T]`, `f32` or `f64`. | |
b039eaaf SL |
830 | ty: Ty<'tcx>, |
831 | }, | |
e9174d1e | 832 | |
dc9dc135 | 833 | /// Test whether the value falls within an inclusive or exclusive range |
e74abb32 | 834 | Range(PatRange<'tcx>), |
e9174d1e | 835 | |
dc9dc135 | 836 | /// Test length of the slice is equal to len |
dfeec247 | 837 | Len { len: u64, op: BinOp }, |
e9174d1e SL |
838 | } |
839 | ||
840 | #[derive(Debug)] | |
dfeec247 | 841 | crate struct Test<'tcx> { |
b039eaaf SL |
842 | span: Span, |
843 | kind: TestKind<'tcx>, | |
e9174d1e SL |
844 | } |
845 | ||
9fa01778 XL |
846 | /// ArmHasGuard is isomorphic to a boolean flag. It indicates whether |
847 | /// a match arm has a guard expression attached to it. | |
848 | #[derive(Copy, Clone, Debug)] | |
dfeec247 | 849 | crate struct ArmHasGuard(crate bool); |
9fa01778 | 850 | |
e9174d1e SL |
851 | /////////////////////////////////////////////////////////////////////////// |
852 | // Main matching algorithm | |
853 | ||
dc9dc135 | 854 | impl<'a, 'tcx> Builder<'a, 'tcx> { |
92a42be0 SL |
855 | /// The main match algorithm. It begins with a set of candidates |
856 | /// `candidates` and has the job of generating code to determine | |
857 | /// which of these candidates, if any, is the correct one. The | |
9cc50fc6 SL |
858 | /// candidates are sorted such that the first item in the list |
859 | /// has the highest priority. When a candidate is found to match | |
74b04a01 | 860 | /// the value, we will set and generate a branch to the appropriate |
9fa01778 | 861 | /// prebinding block. |
92a42be0 | 862 | /// |
dc9dc135 | 863 | /// If we find that *NONE* of the candidates apply, we branch to the |
74b04a01 XL |
864 | /// `otherwise_block`, setting it to `Some` if required. In principle, this |
865 | /// means that the input list was not exhaustive, though at present we | |
866 | /// sometimes are not smart enough to recognize all exhaustive inputs. | |
92a42be0 SL |
867 | /// |
868 | /// It might be surprising that the input can be inexhaustive. | |
869 | /// Indeed, initially, it is not, because all matches are | |
870 | /// exhaustive in Rust. But during processing we sometimes divide | |
871 | /// up the list of candidates and recurse with a non-exhaustive | |
872 | /// list. This is important to keep the size of the generated code | |
873 | /// under control. See `test_candidates` for more details. | |
0bf4aa26 | 874 | /// |
9fa01778 | 875 | /// If `fake_borrows` is Some, then places which need fake borrows |
0bf4aa26 | 876 | /// will be added to it. |
74b04a01 XL |
877 | /// |
878 | /// For an example of a case where we set `otherwise_block`, even for an | |
879 | /// exhaustive match consider: | |
880 | /// | |
881 | /// match x { | |
882 | /// (true, true) => (), | |
883 | /// (_, false) => (), | |
884 | /// (false, true) => (), | |
885 | /// } | |
886 | /// | |
887 | /// For this match, we check if `x.0` matches `true` (for the first | |
888 | /// arm). If that's false, we check `x.1`. If it's `true` we check if | |
889 | /// `x.0` matches `false` (for the third arm). In the (impossible at | |
890 | /// runtime) case when `x.0` is now `true`, we branch to | |
891 | /// `otherwise_block`. | |
b7449926 XL |
892 | fn match_candidates<'pat>( |
893 | &mut self, | |
894 | span: Span, | |
74b04a01 XL |
895 | start_block: BasicBlock, |
896 | otherwise_block: &mut Option<BasicBlock>, | |
9fa01778 | 897 | candidates: &mut [&mut Candidate<'pat, 'tcx>], |
9fa01778 | 898 | fake_borrows: &mut Option<FxHashSet<Place<'tcx>>>, |
dc9dc135 | 899 | ) { |
b7449926 | 900 | debug!( |
dc9dc135 | 901 | "matched_candidate(span={:?}, candidates={:?}, start_block={:?}, otherwise_block={:?})", |
dfeec247 | 902 | span, candidates, start_block, otherwise_block, |
b7449926 | 903 | ); |
e9174d1e | 904 | |
9fa01778 XL |
905 | // Start by simplifying candidates. Once this process is complete, all |
906 | // the match pairs which remain require some form of test, whether it | |
907 | // be a switch or pattern comparison. | |
74b04a01 | 908 | let mut split_or_candidate = false; |
9fa01778 | 909 | for candidate in &mut *candidates { |
74b04a01 | 910 | split_or_candidate |= self.simplify_candidate(candidate); |
e9174d1e SL |
911 | } |
912 | ||
f9f354fc XL |
913 | ensure_sufficient_stack(|| { |
914 | if split_or_candidate { | |
915 | // At least one of the candidates has been split into subcandidates. | |
916 | // We need to change the candidate list to include those. | |
917 | let mut new_candidates = Vec::new(); | |
74b04a01 | 918 | |
f9f354fc XL |
919 | for candidate in candidates { |
920 | candidate.visit_leaves(|leaf_candidate| new_candidates.push(leaf_candidate)); | |
921 | } | |
922 | self.match_simplified_candidates( | |
923 | span, | |
924 | start_block, | |
925 | otherwise_block, | |
926 | &mut *new_candidates, | |
927 | fake_borrows, | |
928 | ); | |
929 | } else { | |
930 | self.match_simplified_candidates( | |
931 | span, | |
932 | start_block, | |
933 | otherwise_block, | |
934 | candidates, | |
935 | fake_borrows, | |
936 | ); | |
74b04a01 | 937 | } |
f9f354fc | 938 | }); |
74b04a01 XL |
939 | } |
940 | ||
941 | fn match_simplified_candidates( | |
942 | &mut self, | |
943 | span: Span, | |
944 | start_block: BasicBlock, | |
945 | otherwise_block: &mut Option<BasicBlock>, | |
946 | candidates: &mut [&mut Candidate<'_, 'tcx>], | |
947 | fake_borrows: &mut Option<FxHashSet<Place<'tcx>>>, | |
948 | ) { | |
9fa01778 XL |
949 | // The candidates are sorted by priority. Check to see whether the |
950 | // higher priority candidates (and hence at the front of the slice) | |
951 | // have satisfied all their match pairs. | |
dfeec247 XL |
952 | let fully_matched = candidates.iter().take_while(|c| c.match_pairs.is_empty()).count(); |
953 | debug!("match_candidates: {:?} candidates fully matched", fully_matched); | |
9fa01778 | 954 | let (matched_candidates, unmatched_candidates) = candidates.split_at_mut(fully_matched); |
abe05a73 | 955 | |
74b04a01 | 956 | let block = if !matched_candidates.is_empty() { |
dfeec247 XL |
957 | let otherwise_block = |
958 | self.select_matched_candidates(matched_candidates, start_block, fake_borrows); | |
dc9dc135 XL |
959 | |
960 | if let Some(last_otherwise_block) = otherwise_block { | |
dfeec247 | 961 | last_otherwise_block |
b039eaaf | 962 | } else { |
9fa01778 | 963 | // Any remaining candidates are unreachable. |
abe05a73 | 964 | if unmatched_candidates.is_empty() { |
dc9dc135 | 965 | return; |
abe05a73 | 966 | } |
dfeec247 XL |
967 | self.cfg.start_new_block() |
968 | } | |
dc9dc135 | 969 | } else { |
74b04a01 | 970 | start_block |
dfeec247 | 971 | }; |
e9174d1e | 972 | |
9fa01778 XL |
973 | // If there are no candidates that still need testing, we're |
974 | // done. Since all matches are exhaustive, execution should | |
975 | // never reach this point. | |
9cc50fc6 | 976 | if unmatched_candidates.is_empty() { |
dc9dc135 | 977 | let source_info = self.source_info(span); |
74b04a01 XL |
978 | if let Some(otherwise) = *otherwise_block { |
979 | self.cfg.goto(block, source_info, otherwise); | |
980 | } else { | |
981 | *otherwise_block = Some(block); | |
dc9dc135 XL |
982 | } |
983 | return; | |
92a42be0 SL |
984 | } |
985 | ||
dc9dc135 | 986 | // Test for the remaining candidates. |
74b04a01 XL |
987 | self.test_candidates_with_or( |
988 | span, | |
989 | unmatched_candidates, | |
990 | block, | |
991 | otherwise_block, | |
992 | fake_borrows, | |
993 | ); | |
9fa01778 XL |
994 | } |
995 | ||
996 | /// Link up matched candidates. For example, if we have something like | |
997 | /// this: | |
998 | /// | |
999 | /// ... | |
1000 | /// Some(x) if cond => ... | |
1001 | /// Some(x) => ... | |
1002 | /// Some(x) if cond => ... | |
1003 | /// ... | |
1004 | /// | |
1005 | /// We generate real edges from: | |
dfeec247 | 1006 | /// * `start_block` to the `prebinding_block` of the first pattern, |
9fa01778 XL |
1007 | /// * the otherwise block of the first pattern to the second pattern, |
1008 | /// * the otherwise block of the third pattern to the a block with an | |
1009 | /// Unreachable terminator. | |
1010 | /// | |
1011 | /// As well as that we add fake edges from the otherwise blocks to the | |
1012 | /// prebinding block of the next candidate in the original set of | |
1013 | /// candidates. | |
1014 | fn select_matched_candidates( | |
1015 | &mut self, | |
1016 | matched_candidates: &mut [&mut Candidate<'_, 'tcx>], | |
74b04a01 | 1017 | start_block: BasicBlock, |
9fa01778 XL |
1018 | fake_borrows: &mut Option<FxHashSet<Place<'tcx>>>, |
1019 | ) -> Option<BasicBlock> { | |
1020 | debug_assert!( | |
1021 | !matched_candidates.is_empty(), | |
1022 | "select_matched_candidates called with no candidates", | |
1023 | ); | |
74b04a01 XL |
1024 | debug_assert!( |
1025 | matched_candidates.iter().all(|c| c.subcandidates.is_empty()), | |
1026 | "subcandidates should be empty in select_matched_candidates", | |
1027 | ); | |
9fa01778 XL |
1028 | |
1029 | // Insert a borrows of prefixes of places that are bound and are | |
1030 | // behind a dereference projection. | |
1031 | // | |
1032 | // These borrows are taken to avoid situations like the following: | |
1033 | // | |
1034 | // match x[10] { | |
1035 | // _ if { x = &[0]; false } => (), | |
1036 | // y => (), // Out of bounds array access! | |
1037 | // } | |
1038 | // | |
1039 | // match *x { | |
1040 | // // y is bound by reference in the guard and then by copy in the | |
1041 | // // arm, so y is 2 in the arm! | |
1042 | // y if { y == 1 && (x = &2) == () } => y, | |
1043 | // _ => 3, | |
1044 | // } | |
1045 | if let Some(fake_borrows) = fake_borrows { | |
dfeec247 XL |
1046 | for Binding { source, .. } in |
1047 | matched_candidates.iter().flat_map(|candidate| &candidate.bindings) | |
9fa01778 | 1048 | { |
e1599b0c | 1049 | if let Some(i) = |
f9f354fc | 1050 | source.projection.iter().rposition(|elem| elem == ProjectionElem::Deref) |
e1599b0c XL |
1051 | { |
1052 | let proj_base = &source.projection[..i]; | |
1053 | ||
1054 | fake_borrows.insert(Place { | |
dfeec247 | 1055 | local: source.local, |
e74abb32 | 1056 | projection: self.hir.tcx().intern_place_elems(proj_base), |
e1599b0c | 1057 | }); |
9fa01778 XL |
1058 | } |
1059 | } | |
1060 | } | |
1061 | ||
1062 | let fully_matched_with_guard = matched_candidates | |
1063 | .iter() | |
74b04a01 | 1064 | .position(|c| !c.has_guard) |
9fa01778 XL |
1065 | .unwrap_or(matched_candidates.len() - 1); |
1066 | ||
dfeec247 XL |
1067 | let (reachable_candidates, unreachable_candidates) = |
1068 | matched_candidates.split_at_mut(fully_matched_with_guard + 1); | |
9fa01778 | 1069 | |
74b04a01 | 1070 | let mut next_prebinding = start_block; |
9fa01778 | 1071 | |
74b04a01 XL |
1072 | for candidate in reachable_candidates.iter_mut() { |
1073 | assert!(candidate.otherwise_block.is_none()); | |
1074 | assert!(candidate.pre_binding_block.is_none()); | |
1075 | candidate.pre_binding_block = Some(next_prebinding); | |
1076 | if candidate.has_guard { | |
1077 | // Create the otherwise block for this candidate, which is the | |
1078 | // pre-binding block for the next candidate. | |
1079 | next_prebinding = self.cfg.start_new_block(); | |
1080 | candidate.otherwise_block = Some(next_prebinding); | |
1081 | } | |
dc9dc135 | 1082 | } |
9fa01778 | 1083 | |
74b04a01 XL |
1084 | debug!( |
1085 | "match_candidates: add pre_binding_blocks for unreachable {:?}", | |
1086 | unreachable_candidates, | |
1087 | ); | |
1088 | for candidate in unreachable_candidates { | |
1089 | assert!(candidate.pre_binding_block.is_none()); | |
1090 | candidate.pre_binding_block = Some(self.cfg.start_new_block()); | |
1091 | } | |
1092 | ||
1093 | reachable_candidates.last_mut().unwrap().otherwise_block | |
1094 | } | |
1095 | ||
1096 | /// Tests a candidate where there are only or-patterns left to test, or | |
1097 | /// forwards to [Builder::test_candidates]. | |
1098 | /// | |
1099 | /// Given a pattern `(P | Q, R | S)` we (in principle) generate a CFG like | |
1100 | /// so | |
1101 | /// | |
1102 | /// ```text | |
1103 | /// [ start ] | |
1104 | /// | | |
1105 | /// [ match P, Q ] | |
1106 | /// | | |
1107 | /// +----------------------------------------+------------------------------------+ | |
1108 | /// | | | | |
1109 | /// V V V | |
1110 | /// [ P matches ] [ Q matches ] [ otherwise ] | |
1111 | /// | | | | |
1112 | /// V V | | |
1113 | /// [ match R, S ] [ match R, S ] | | |
1114 | /// | | | | |
1115 | /// +--------------+------------+ +--------------+------------+ | | |
1116 | /// | | | | | | | | |
1117 | /// V V V V V V | | |
1118 | /// [ R matches ] [ S matches ] [otherwise ] [ R matches ] [ S matches ] [otherwise ] | | |
1119 | /// | | | | | | | | |
1120 | /// +--------------+------------|------------+--------------+ | | | |
1121 | /// | | | | | |
1122 | /// | +----------------------------------------+--------+ | |
1123 | /// | | | |
1124 | /// V V | |
1125 | /// [ Success ] [ Failure ] | |
1126 | /// ``` | |
1127 | /// | |
1128 | /// In practice there are some complications: | |
1129 | /// | |
1130 | /// * If there's a guard, then the otherwise branch of the first match on | |
1131 | /// `R | S` goes to a test for whether `Q` matches, and the control flow | |
1132 | /// doesn't merge into a single success block until after the guard is | |
1133 | /// tested. | |
1134 | /// * If neither `P` or `Q` has any bindings or type ascriptions and there | |
1135 | /// isn't a match guard, then we create a smaller CFG like: | |
1136 | /// | |
1137 | /// ```text | |
1138 | /// ... | |
1139 | /// +---------------+------------+ | |
1140 | /// | | | | |
1141 | /// [ P matches ] [ Q matches ] [ otherwise ] | |
1142 | /// | | | | |
1143 | /// +---------------+ | | |
1144 | /// | ... | |
1145 | /// [ match R, S ] | |
1146 | /// | | |
1147 | /// ... | |
1148 | /// ``` | |
1149 | fn test_candidates_with_or( | |
1150 | &mut self, | |
1151 | span: Span, | |
1152 | candidates: &mut [&mut Candidate<'_, 'tcx>], | |
1153 | block: BasicBlock, | |
1154 | otherwise_block: &mut Option<BasicBlock>, | |
1155 | fake_borrows: &mut Option<FxHashSet<Place<'tcx>>>, | |
1156 | ) { | |
1157 | let (first_candidate, remaining_candidates) = candidates.split_first_mut().unwrap(); | |
1158 | ||
1159 | // All of the or-patterns have been sorted to the end, so if the first | |
1160 | // pattern is an or-pattern we only have or-patterns. | |
1161 | match *first_candidate.match_pairs[0].pattern.kind { | |
1162 | PatKind::Or { .. } => (), | |
1163 | _ => { | |
1164 | self.test_candidates(span, candidates, block, otherwise_block, fake_borrows); | |
1165 | return; | |
9fa01778 XL |
1166 | } |
1167 | } | |
1168 | ||
74b04a01 XL |
1169 | let match_pairs = mem::take(&mut first_candidate.match_pairs); |
1170 | first_candidate.pre_binding_block = Some(block); | |
1171 | ||
1172 | let mut otherwise = None; | |
1173 | for match_pair in match_pairs { | |
1174 | if let PatKind::Or { ref pats } = *match_pair.pattern.kind { | |
1175 | let or_span = match_pair.pattern.span; | |
1176 | let place = match_pair.place; | |
1177 | ||
1178 | first_candidate.visit_leaves(|leaf_candidate| { | |
1179 | self.test_or_pattern( | |
1180 | leaf_candidate, | |
1181 | &mut otherwise, | |
1182 | pats, | |
1183 | or_span, | |
1184 | place, | |
1185 | fake_borrows, | |
1186 | ); | |
1187 | }); | |
1188 | } else { | |
1189 | bug!("Or-patterns should have been sorted to the end"); | |
9fa01778 XL |
1190 | } |
1191 | } | |
1192 | ||
74b04a01 XL |
1193 | let remainder_start = otherwise.unwrap_or_else(|| self.cfg.start_new_block()); |
1194 | ||
1195 | self.match_candidates( | |
1196 | span, | |
1197 | remainder_start, | |
1198 | otherwise_block, | |
1199 | remaining_candidates, | |
1200 | fake_borrows, | |
1201 | ) | |
1202 | } | |
1203 | ||
1204 | fn test_or_pattern<'pat>( | |
1205 | &mut self, | |
1206 | candidate: &mut Candidate<'pat, 'tcx>, | |
1207 | otherwise: &mut Option<BasicBlock>, | |
1208 | pats: &'pat [Pat<'tcx>], | |
1209 | or_span: Span, | |
1210 | place: Place<'tcx>, | |
1211 | fake_borrows: &mut Option<FxHashSet<Place<'tcx>>>, | |
1212 | ) { | |
1213 | debug!("test_or_pattern:\ncandidate={:#?}\npats={:#?}", candidate, pats); | |
1214 | let mut or_candidates: Vec<_> = | |
1215 | pats.iter().map(|pat| Candidate::new(place, pat, candidate.has_guard)).collect(); | |
1216 | let mut or_candidate_refs: Vec<_> = or_candidates.iter_mut().collect(); | |
1217 | let otherwise = if candidate.otherwise_block.is_some() { | |
1218 | &mut candidate.otherwise_block | |
9fa01778 | 1219 | } else { |
74b04a01 XL |
1220 | otherwise |
1221 | }; | |
1222 | self.match_candidates( | |
1223 | or_span, | |
1224 | candidate.pre_binding_block.unwrap(), | |
1225 | otherwise, | |
1226 | &mut or_candidate_refs, | |
1227 | fake_borrows, | |
1228 | ); | |
1229 | candidate.subcandidates = or_candidates; | |
1230 | self.merge_trivial_subcandidates(candidate, self.source_info(or_span)); | |
1231 | } | |
1232 | ||
1233 | /// Try to merge all of the subcandidates of the given candidate into one. | |
1234 | /// This avoids exponentially large CFGs in cases like `(1 | 2, 3 | 4, ...)`. | |
1235 | fn merge_trivial_subcandidates( | |
1236 | &mut self, | |
1237 | candidate: &mut Candidate<'_, 'tcx>, | |
1238 | source_info: SourceInfo, | |
1239 | ) { | |
1240 | if candidate.subcandidates.is_empty() || candidate.has_guard { | |
1241 | // FIXME(or_patterns; matthewjasper) Don't give up if we have a guard. | |
1242 | return; | |
1243 | } | |
1244 | ||
1245 | let mut can_merge = true; | |
1246 | ||
1247 | // Not `Iterator::all` because we don't want to short-circuit. | |
1248 | for subcandidate in &mut candidate.subcandidates { | |
1249 | self.merge_trivial_subcandidates(subcandidate, source_info); | |
1250 | ||
1251 | // FIXME(or_patterns; matthewjasper) Try to be more aggressive here. | |
1252 | can_merge &= subcandidate.subcandidates.is_empty() | |
1253 | && subcandidate.bindings.is_empty() | |
1254 | && subcandidate.ascriptions.is_empty(); | |
1255 | } | |
1256 | ||
1257 | if can_merge { | |
1258 | let any_matches = self.cfg.start_new_block(); | |
1259 | for subcandidate in mem::take(&mut candidate.subcandidates) { | |
1260 | let or_block = subcandidate.pre_binding_block.unwrap(); | |
1261 | self.cfg.goto(or_block, source_info, any_matches); | |
1262 | } | |
1263 | candidate.pre_binding_block = Some(any_matches); | |
9fa01778 | 1264 | } |
92a42be0 SL |
1265 | } |
1266 | ||
9fa01778 | 1267 | /// This is the most subtle part of the matching algorithm. At |
92a42be0 SL |
1268 | /// this point, the input candidates have been fully simplified, |
1269 | /// and so we know that all remaining match-pairs require some | |
1270 | /// sort of test. To decide what test to do, we take the highest | |
1271 | /// priority candidate (last one in the list) and extract the | |
1272 | /// first match-pair from the list. From this we decide what kind | |
1273 | /// of test is needed using `test`, defined in the `test` module. | |
1274 | /// | |
1275 | /// *Note:* taking the first match pair is somewhat arbitrary, and | |
1276 | /// we might do better here by choosing more carefully what to | |
1277 | /// test. | |
1278 | /// | |
1279 | /// For example, consider the following possible match-pairs: | |
1280 | /// | |
1281 | /// 1. `x @ Some(P)` -- we will do a `Switch` to decide what variant `x` has | |
1282 | /// 2. `x @ 22` -- we will do a `SwitchInt` | |
1283 | /// 3. `x @ 3..5` -- we will do a range test | |
1284 | /// 4. etc. | |
1285 | /// | |
1286 | /// Once we know what sort of test we are going to perform, this | |
9fa01778 | 1287 | /// Tests may also help us with other candidates. So we walk over |
92a42be0 SL |
1288 | /// the candidates (from high to low priority) and check. This |
1289 | /// gives us, for each outcome of the test, a transformed list of | |
9fa01778 | 1290 | /// candidates. For example, if we are testing the current |
92a42be0 SL |
1291 | /// variant of `x.0`, and we have a candidate `{x.0 @ Some(v), x.1 |
1292 | /// @ 22}`, then we would have a resulting candidate of `{(x.0 as | |
1293 | /// Some).0 @ v, x.1 @ 22}`. Note that the first match-pair is now | |
1294 | /// simpler (and, in fact, irrefutable). | |
1295 | /// | |
1296 | /// But there may also be candidates that the test just doesn't | |
3157f602 | 1297 | /// apply to. The classical example involves wildcards: |
92a42be0 | 1298 | /// |
041b39d2 XL |
1299 | /// ``` |
1300 | /// # let (x, y, z) = (true, true, true); | |
3157f602 XL |
1301 | /// match (x, y, z) { |
1302 | /// (true, _, true) => true, // (0) | |
1303 | /// (_, true, _) => true, // (1) | |
1304 | /// (false, false, _) => false, // (2) | |
1305 | /// (true, _, false) => false, // (3) | |
1306 | /// } | |
1307 | /// ``` | |
1308 | /// | |
1309 | /// In that case, after we test on `x`, there are 2 overlapping candidate | |
1310 | /// sets: | |
1311 | /// | |
1312 | /// - If the outcome is that `x` is true, candidates 0, 1, and 3 | |
1313 | /// - If the outcome is that `x` is false, candidates 1 and 2 | |
1314 | /// | |
1315 | /// Here, the traditional "decision tree" method would generate 2 | |
1316 | /// separate code-paths for the 2 separate cases. | |
1317 | /// | |
1318 | /// In some cases, this duplication can create an exponential amount of | |
1319 | /// code. This is most easily seen by noticing that this method terminates | |
1320 | /// with precisely the reachable arms being reachable - but that problem | |
1321 | /// is trivially NP-complete: | |
1322 | /// | |
1323 | /// ```rust | |
1324 | /// match (var0, var1, var2, var3, ..) { | |
1325 | /// (true, _, _, false, true, ...) => false, | |
1326 | /// (_, true, true, false, _, ...) => false, | |
1327 | /// (false, _, false, false, _, ...) => false, | |
1328 | /// ... | |
1329 | /// _ => true | |
1330 | /// } | |
1331 | /// ``` | |
1332 | /// | |
1333 | /// Here the last arm is reachable only if there is an assignment to | |
1334 | /// the variables that does not match any of the literals. Therefore, | |
1335 | /// compilation would take an exponential amount of time in some cases. | |
1336 | /// | |
1337 | /// That kind of exponential worst-case might not occur in practice, but | |
1338 | /// our simplistic treatment of constants and guards would make it occur | |
1339 | /// in very common situations - for example #29740: | |
1340 | /// | |
1341 | /// ```rust | |
92a42be0 | 1342 | /// match x { |
3157f602 XL |
1343 | /// "foo" if foo_guard => ..., |
1344 | /// "bar" if bar_guard => ..., | |
1345 | /// "baz" if baz_guard => ..., | |
1346 | /// ... | |
92a42be0 SL |
1347 | /// } |
1348 | /// ``` | |
1349 | /// | |
3157f602 XL |
1350 | /// Here we first test the match-pair `x @ "foo"`, which is an `Eq` test. |
1351 | /// | |
1352 | /// It might seem that we would end up with 2 disjoint candidate | |
1353 | /// sets, consisting of the first candidate or the other 3, but our | |
1354 | /// algorithm doesn't reason about "foo" being distinct from the other | |
1355 | /// constants; it considers the latter arms to potentially match after | |
1356 | /// both outcomes, which obviously leads to an exponential amount | |
1357 | /// of tests. | |
92a42be0 | 1358 | /// |
3157f602 XL |
1359 | /// To avoid these kinds of problems, our algorithm tries to ensure |
1360 | /// the amount of generated tests is linear. When we do a k-way test, | |
1361 | /// we return an additional "unmatched" set alongside the obvious `k` | |
1362 | /// sets. When we encounter a candidate that would be present in more | |
1363 | /// than one of the sets, we put it and all candidates below it into the | |
1364 | /// "unmatched" set. This ensures these `k+1` sets are disjoint. | |
92a42be0 | 1365 | /// |
3157f602 XL |
1366 | /// After we perform our test, we branch into the appropriate candidate |
1367 | /// set and recurse with `match_candidates`. These sub-matches are | |
1368 | /// obviously inexhaustive - as we discarded our otherwise set - so | |
1369 | /// we set their continuation to do `match_candidates` on the | |
1370 | /// "unmatched" set (which is again inexhaustive). | |
92a42be0 SL |
1371 | /// |
1372 | /// If you apply this to the above test, you basically wind up | |
1373 | /// with an if-else-if chain, testing each candidate in turn, | |
1374 | /// which is precisely what we want. | |
3157f602 XL |
1375 | /// |
1376 | /// In addition to avoiding exponential-time blowups, this algorithm | |
1377 | /// also has nice property that each guard and arm is only generated | |
1378 | /// once. | |
9fa01778 | 1379 | fn test_candidates<'pat, 'b, 'c>( |
b7449926 XL |
1380 | &mut self, |
1381 | span: Span, | |
9fa01778 | 1382 | mut candidates: &'b mut [&'c mut Candidate<'pat, 'tcx>], |
b7449926 | 1383 | block: BasicBlock, |
74b04a01 | 1384 | otherwise_block: &mut Option<BasicBlock>, |
9fa01778 | 1385 | fake_borrows: &mut Option<FxHashSet<Place<'tcx>>>, |
dc9dc135 | 1386 | ) { |
92a42be0 | 1387 | // extract the match-pair from the highest priority candidate |
9cc50fc6 | 1388 | let match_pair = &candidates.first().unwrap().match_pairs[0]; |
92a42be0 | 1389 | let mut test = self.test(match_pair); |
dfeec247 | 1390 | let match_place = match_pair.place; |
92a42be0 SL |
1391 | |
1392 | // most of the time, the test to perform is simply a function | |
1393 | // of the main candidate; but for a test like SwitchInt, we | |
1394 | // may want to add cases based on the candidates that are | |
1395 | // available | |
1396 | match test.kind { | |
3dfed10e | 1397 | TestKind::SwitchInt { switch_ty, ref mut options } => { |
9cc50fc6 | 1398 | for candidate in candidates.iter() { |
b7449926 | 1399 | if !self.add_cases_to_switch( |
9fa01778 | 1400 | &match_place, |
b7449926 XL |
1401 | candidate, |
1402 | switch_ty, | |
1403 | options, | |
b7449926 | 1404 | ) { |
92a42be0 SL |
1405 | break; |
1406 | } | |
1407 | } | |
1408 | } | |
dfeec247 | 1409 | TestKind::Switch { adt_def: _, ref mut variants } => { |
3157f602 | 1410 | for candidate in candidates.iter() { |
9fa01778 | 1411 | if !self.add_variants_to_switch(&match_place, candidate, variants) { |
3157f602 XL |
1412 | break; |
1413 | } | |
1414 | } | |
1415 | } | |
b7449926 | 1416 | _ => {} |
92a42be0 SL |
1417 | } |
1418 | ||
0bf4aa26 | 1419 | // Insert a Shallow borrow of any places that is switched on. |
f9f354fc XL |
1420 | if let Some(fb) = fake_borrows { |
1421 | fb.insert(match_place); | |
1422 | } | |
0bf4aa26 | 1423 | |
92a42be0 SL |
1424 | // perform the test, branching to one of N blocks. For each of |
1425 | // those N possible outcomes, create a (initially empty) | |
1426 | // vector of candidates. Those are the candidates that still | |
1427 | // apply if the test has that particular outcome. | |
dfeec247 | 1428 | debug!("match_candidates: test={:?} match_pair={:?}", test, match_pair); |
9fa01778 | 1429 | let mut target_candidates: Vec<Vec<&mut Candidate<'pat, 'tcx>>> = vec![]; |
dc9dc135 | 1430 | target_candidates.resize_with(test.targets(), Default::default); |
9fa01778 XL |
1431 | |
1432 | let total_candidate_count = candidates.len(); | |
92a42be0 SL |
1433 | |
1434 | // Sort the candidates into the appropriate vector in | |
1435 | // `target_candidates`. Note that at some point we may | |
1436 | // encounter a candidate where the test is not relevant; at | |
1437 | // that point, we stop sorting. | |
9fa01778 XL |
1438 | while let Some(candidate) = candidates.first_mut() { |
1439 | if let Some(idx) = self.sort_candidate(&match_place, &test, candidate) { | |
1440 | let (candidate, rest) = candidates.split_first_mut().unwrap(); | |
1441 | target_candidates[idx].push(candidate); | |
1442 | candidates = rest; | |
1443 | } else { | |
1444 | break; | |
1445 | } | |
1446 | } | |
1447 | // at least the first candidate ought to be tested | |
1448 | assert!(total_candidate_count > candidates.len()); | |
1449 | debug!("tested_candidates: {}", total_candidate_count - candidates.len()); | |
1450 | debug!("untested_candidates: {}", candidates.len()); | |
92a42be0 | 1451 | |
dc9dc135 XL |
1452 | // HACK(matthewjasper) This is a closure so that we can let the test |
1453 | // create its blocks before the rest of the match. This currently | |
1454 | // improves the speed of llvm when optimizing long string literal | |
1455 | // matches | |
1456 | let make_target_blocks = move |this: &mut Self| -> Vec<BasicBlock> { | |
74b04a01 XL |
1457 | // The block that we should branch to if none of the |
1458 | // `target_candidates` match. This is either the block where we | |
1459 | // start matching the untested candidates if there are any, | |
1460 | // otherwise it's the `otherwise_block`. | |
1461 | let remainder_start = &mut None; | |
1462 | let remainder_start = | |
1463 | if candidates.is_empty() { &mut *otherwise_block } else { remainder_start }; | |
1464 | ||
dc9dc135 XL |
1465 | // For each outcome of test, process the candidates that still |
1466 | // apply. Collect a list of blocks where control flow will | |
1467 | // branch if one of the `target_candidate` sets is not | |
1468 | // exhaustive. | |
74b04a01 | 1469 | let target_blocks: Vec<_> = target_candidates |
dfeec247 XL |
1470 | .into_iter() |
1471 | .map(|mut candidates| { | |
74b04a01 XL |
1472 | if !candidates.is_empty() { |
1473 | let candidate_start = this.cfg.start_new_block(); | |
dfeec247 XL |
1474 | this.match_candidates( |
1475 | span, | |
1476 | candidate_start, | |
74b04a01 | 1477 | remainder_start, |
dfeec247 XL |
1478 | &mut *candidates, |
1479 | fake_borrows, | |
dc9dc135 | 1480 | ); |
74b04a01 | 1481 | candidate_start |
dfeec247 | 1482 | } else { |
74b04a01 | 1483 | *remainder_start.get_or_insert_with(|| this.cfg.start_new_block()) |
dfeec247 XL |
1484 | } |
1485 | }) | |
74b04a01 XL |
1486 | .collect(); |
1487 | ||
1488 | if !candidates.is_empty() { | |
1489 | let remainder_start = remainder_start.unwrap_or_else(|| this.cfg.start_new_block()); | |
1490 | this.match_candidates( | |
1491 | span, | |
1492 | remainder_start, | |
1493 | otherwise_block, | |
1494 | candidates, | |
1495 | fake_borrows, | |
1496 | ); | |
1497 | }; | |
1498 | ||
1499 | target_blocks | |
dc9dc135 | 1500 | }; |
92a42be0 | 1501 | |
74b04a01 | 1502 | self.perform_test(block, match_place, &test, make_target_blocks); |
9fa01778 XL |
1503 | } |
1504 | ||
dfeec247 XL |
1505 | /// Determine the fake borrows that are needed from a set of places that |
1506 | /// have to be stable across match guards. | |
1507 | /// | |
1508 | /// Returns a list of places that need a fake borrow and the temporary | |
1509 | /// that's used to store the fake borrow. | |
1510 | /// | |
1511 | /// Match exhaustiveness checking is not able to handle the case where the | |
1512 | /// place being matched on is mutated in the guards. We add "fake borrows" | |
1513 | /// to the guards that prevent any mutation of the place being matched. | |
1514 | /// There are a some subtleties: | |
1515 | /// | |
1516 | /// 1. Borrowing `*x` doesn't prevent assigning to `x`. If `x` is a shared | |
1517 | /// reference, the borrow isn't even tracked. As such we have to add fake | |
1518 | /// borrows of any prefixes of a place | |
1519 | /// 2. We don't want `match x { _ => (), }` to conflict with mutable | |
1520 | /// borrows of `x`, so we only add fake borrows for places which are | |
1521 | /// bound or tested by the match. | |
1522 | /// 3. We don't want the fake borrows to conflict with `ref mut` bindings, | |
1523 | /// so we use a special BorrowKind for them. | |
1524 | /// 4. The fake borrows may be of places in inactive variants, so it would | |
1525 | /// be UB to generate code for them. They therefore have to be removed | |
1526 | /// by a MIR pass run after borrow checking. | |
9fa01778 XL |
1527 | fn calculate_fake_borrows<'b>( |
1528 | &mut self, | |
1529 | fake_borrows: &'b FxHashSet<Place<'tcx>>, | |
1530 | temp_span: Span, | |
dfeec247 | 1531 | ) -> Vec<(Place<'tcx>, Local)> { |
9fa01778 XL |
1532 | let tcx = self.hir.tcx(); |
1533 | ||
1534 | debug!("add_fake_borrows fake_borrows = {:?}", fake_borrows); | |
1535 | ||
1536 | let mut all_fake_borrows = Vec::with_capacity(fake_borrows.len()); | |
1537 | ||
1538 | // Insert a Shallow borrow of the prefixes of any fake borrows. | |
dfeec247 | 1539 | for place in fake_borrows { |
e74abb32 | 1540 | let mut cursor = place.projection.as_ref(); |
e1599b0c XL |
1541 | while let [proj_base @ .., elem] = cursor { |
1542 | cursor = proj_base; | |
1543 | ||
9fa01778 XL |
1544 | if let ProjectionElem::Deref = elem { |
1545 | // Insert a shallow borrow after a deref. For other | |
1546 | // projections the borrow of prefix_cursor will | |
1547 | // conflict with any mutation of base. | |
74b04a01 | 1548 | all_fake_borrows.push(PlaceRef { local: place.local, projection: proj_base }); |
9fa01778 | 1549 | } |
9fa01778 XL |
1550 | } |
1551 | ||
416331ca | 1552 | all_fake_borrows.push(place.as_ref()); |
9fa01778 XL |
1553 | } |
1554 | ||
1555 | // Deduplicate and ensure a deterministic order. | |
1556 | all_fake_borrows.sort(); | |
1557 | all_fake_borrows.dedup(); | |
1558 | ||
1559 | debug!("add_fake_borrows all_fake_borrows = {:?}", all_fake_borrows); | |
1560 | ||
dfeec247 XL |
1561 | all_fake_borrows |
1562 | .into_iter() | |
1563 | .map(|matched_place_ref| { | |
1564 | let matched_place = Place { | |
74b04a01 | 1565 | local: matched_place_ref.local, |
dfeec247 XL |
1566 | projection: tcx.intern_place_elems(matched_place_ref.projection), |
1567 | }; | |
1568 | let fake_borrow_deref_ty = matched_place.ty(&self.local_decls, tcx).ty; | |
1569 | let fake_borrow_ty = tcx.mk_imm_ref(tcx.lifetimes.re_erased, fake_borrow_deref_ty); | |
1570 | let fake_borrow_temp = | |
f9f354fc | 1571 | self.local_decls.push(LocalDecl::new(fake_borrow_ty, temp_span)); |
9fa01778 | 1572 | |
dfeec247 XL |
1573 | (matched_place, fake_borrow_temp) |
1574 | }) | |
1575 | .collect() | |
e9174d1e | 1576 | } |
9fa01778 | 1577 | } |
e9174d1e | 1578 | |
9fa01778 | 1579 | /////////////////////////////////////////////////////////////////////////// |
e74abb32 | 1580 | // Pat binding - used for `let` and function parameters as well. |
9fa01778 | 1581 | |
dc9dc135 | 1582 | impl<'a, 'tcx> Builder<'a, 'tcx> { |
e9174d1e | 1583 | /// Initializes each of the bindings from the candidate by |
9fa01778 XL |
1584 | /// moving/copying/ref'ing the source as appropriate. Tests the guard, if |
1585 | /// any, and then branches to the arm. Returns the block for the case where | |
1586 | /// the guard fails. | |
e9174d1e | 1587 | /// |
e1599b0c XL |
1588 | /// Note: we do not check earlier that if there is a guard, |
1589 | /// there cannot be move bindings. We avoid a use-after-move by only | |
1590 | /// moving the binding once the guard has evaluated to true (see below). | |
b7449926 XL |
1591 | fn bind_and_guard_matched_candidate<'pat>( |
1592 | &mut self, | |
b7449926 | 1593 | candidate: Candidate<'pat, 'tcx>, |
74b04a01 | 1594 | parent_bindings: &[(Vec<Binding<'tcx>>, Vec<Ascription<'tcx>>)], |
dfeec247 XL |
1595 | guard: Option<(&Guard<'tcx>, region::Scope)>, |
1596 | fake_borrows: &Vec<(Place<'tcx>, Local)>, | |
9fa01778 | 1597 | scrutinee_span: Span, |
74b04a01 | 1598 | schedule_drops: bool, |
dc9dc135 | 1599 | ) -> BasicBlock { |
9fa01778 | 1600 | debug!("bind_and_guard_matched_candidate(candidate={:?})", candidate); |
e9174d1e SL |
1601 | |
1602 | debug_assert!(candidate.match_pairs.is_empty()); | |
1603 | ||
abe05a73 XL |
1604 | let candidate_source_info = self.source_info(candidate.span); |
1605 | ||
74b04a01 | 1606 | let mut block = candidate.pre_binding_block.unwrap(); |
dc9dc135 | 1607 | |
74b04a01 | 1608 | if candidate.next_candidate_pre_binding_block.is_some() { |
dc9dc135 XL |
1609 | let fresh_block = self.cfg.start_new_block(); |
1610 | self.false_edges( | |
1611 | block, | |
1612 | fresh_block, | |
1613 | candidate.next_candidate_pre_binding_block, | |
1614 | candidate_source_info, | |
1615 | ); | |
1616 | block = fresh_block; | |
dc9dc135 | 1617 | } |
e9174d1e | 1618 | |
74b04a01 XL |
1619 | self.ascribe_types( |
1620 | block, | |
1621 | parent_bindings | |
1622 | .iter() | |
1623 | .flat_map(|(_, ascriptions)| ascriptions) | |
1624 | .chain(&candidate.ascriptions), | |
1625 | ); | |
1626 | ||
83c7162d XL |
1627 | // rust-lang/rust#27282: The `autoref` business deserves some |
1628 | // explanation here. | |
1629 | // | |
1630 | // The intent of the `autoref` flag is that when it is true, | |
1631 | // then any pattern bindings of type T will map to a `&T` | |
1632 | // within the context of the guard expression, but will | |
1633 | // continue to map to a `T` in the context of the arm body. To | |
1634 | // avoid surfacing this distinction in the user source code | |
1635 | // (which would be a severe change to the language and require | |
1636 | // far more revision to the compiler), when `autoref` is true, | |
1637 | // then any occurrence of the identifier in the guard | |
1638 | // expression will automatically get a deref op applied to it. | |
1639 | // | |
1640 | // So an input like: | |
1641 | // | |
1642 | // ``` | |
1643 | // let place = Foo::new(); | |
1644 | // match place { foo if inspect(foo) | |
1645 | // => feed(foo), ... } | |
1646 | // ``` | |
1647 | // | |
1648 | // will be treated as if it were really something like: | |
1649 | // | |
1650 | // ``` | |
1651 | // let place = Foo::new(); | |
1652 | // match place { Foo { .. } if { let tmp1 = &place; inspect(*tmp1) } | |
1653 | // => { let tmp2 = place; feed(tmp2) }, ... } | |
1654 | // | |
1655 | // And an input like: | |
1656 | // | |
1657 | // ``` | |
1658 | // let place = Foo::new(); | |
1659 | // match place { ref mut foo if inspect(foo) | |
1660 | // => feed(foo), ... } | |
1661 | // ``` | |
1662 | // | |
1663 | // will be treated as if it were really something like: | |
1664 | // | |
1665 | // ``` | |
1666 | // let place = Foo::new(); | |
1667 | // match place { Foo { .. } if { let tmp1 = & &mut place; inspect(*tmp1) } | |
1668 | // => { let tmp2 = &mut place; feed(tmp2) }, ... } | |
1669 | // ``` | |
1670 | // | |
1671 | // In short, any pattern binding will always look like *some* | |
1672 | // kind of `&T` within the guard at least in terms of how the | |
1673 | // MIR-borrowck views it, and this will ensure that guard | |
1674 | // expressions cannot mutate their the match inputs via such | |
1675 | // bindings. (It also ensures that guard expressions can at | |
1676 | // most *copy* values from such bindings; non-Copy things | |
1677 | // cannot be moved via pattern bindings in guard expressions.) | |
1678 | // | |
1679 | // ---- | |
1680 | // | |
1681 | // Implementation notes (under assumption `autoref` is true). | |
1682 | // | |
1683 | // To encode the distinction above, we must inject the | |
1684 | // temporaries `tmp1` and `tmp2`. | |
1685 | // | |
1686 | // There are two cases of interest: binding by-value, and binding by-ref. | |
1687 | // | |
1688 | // 1. Binding by-value: Things are simple. | |
1689 | // | |
1690 | // * Establishing `tmp1` creates a reference into the | |
1691 | // matched place. This code is emitted by | |
1692 | // bind_matched_candidate_for_guard. | |
1693 | // | |
1694 | // * `tmp2` is only initialized "lazily", after we have | |
1695 | // checked the guard. Thus, the code that can trigger | |
1696 | // moves out of the candidate can only fire after the | |
1697 | // guard evaluated to true. This initialization code is | |
1698 | // emitted by bind_matched_candidate_for_arm. | |
1699 | // | |
1700 | // 2. Binding by-reference: Things are tricky. | |
1701 | // | |
1702 | // * Here, the guard expression wants a `&&` or `&&mut` | |
1703 | // into the original input. This means we need to borrow | |
9fa01778 XL |
1704 | // the reference that we create for the arm. |
1705 | // * So we eagerly create the reference for the arm and then take a | |
1706 | // reference to that. | |
dfeec247 | 1707 | if let Some((guard, region_scope)) = guard { |
48663c56 | 1708 | let tcx = self.hir.tcx(); |
74b04a01 XL |
1709 | let bindings = parent_bindings |
1710 | .iter() | |
1711 | .flat_map(|(bindings, _)| bindings) | |
1712 | .chain(&candidate.bindings); | |
48663c56 | 1713 | |
74b04a01 | 1714 | self.bind_matched_candidate_for_guard(block, schedule_drops, bindings.clone()); |
48663c56 | 1715 | let guard_frame = GuardFrame { |
74b04a01 | 1716 | locals: bindings.map(|b| GuardFrameLocal::new(b.var_id, b.binding_mode)).collect(), |
48663c56 | 1717 | }; |
416331ca | 1718 | debug!("entering guard building context: {:?}", guard_frame); |
48663c56 | 1719 | self.guard_context.push(guard_frame); |
83c7162d | 1720 | |
48663c56 | 1721 | let re_erased = tcx.lifetimes.re_erased; |
9fa01778 | 1722 | let scrutinee_source_info = self.source_info(scrutinee_span); |
74b04a01 XL |
1723 | for &(place, temp) in fake_borrows { |
1724 | let borrow = Rvalue::Ref(re_erased, BorrowKind::Shallow, place); | |
ba9703b0 | 1725 | self.cfg.push_assign(block, scrutinee_source_info, Place::from(temp), borrow); |
9fa01778 XL |
1726 | } |
1727 | ||
e9174d1e SL |
1728 | // the block to branch to if the guard fails; if there is no |
1729 | // guard, this block is simply unreachable | |
b7449926 | 1730 | let guard = match guard { |
dfeec247 | 1731 | Guard::If(e) => self.hir.mirror(e.clone()), |
b7449926 | 1732 | }; |
3157f602 | 1733 | let source_info = self.source_info(guard.span); |
9fa01778 | 1734 | let guard_end = self.source_info(tcx.sess.source_map().end_point(guard.span)); |
dfeec247 XL |
1735 | let (post_guard_block, otherwise_post_guard_block) = |
1736 | self.test_bool(block, guard, source_info); | |
48663c56 | 1737 | let guard_frame = self.guard_context.pop().unwrap(); |
dfeec247 | 1738 | debug!("Exiting guard building context with locals: {:?}", guard_frame); |
abe05a73 | 1739 | |
9fa01778 | 1740 | for &(_, temp) in fake_borrows { |
60c5eb7d XL |
1741 | let cause = FakeReadCause::ForMatchGuard; |
1742 | self.cfg.push_fake_read(post_guard_block, guard_end, cause, Place::from(temp)); | |
9fa01778 | 1743 | } |
94b46f34 | 1744 | |
74b04a01 XL |
1745 | let otherwise_block = candidate.otherwise_block.unwrap_or_else(|| { |
1746 | let unreachable = self.cfg.start_new_block(); | |
1747 | self.cfg.terminate(unreachable, source_info, TerminatorKind::Unreachable); | |
1748 | unreachable | |
1749 | }); | |
1750 | let outside_scope = self.cfg.start_new_block(); | |
dc9dc135 XL |
1751 | self.exit_scope( |
1752 | source_info.span, | |
1753 | region_scope, | |
1754 | otherwise_post_guard_block, | |
74b04a01 XL |
1755 | outside_scope, |
1756 | ); | |
1757 | self.false_edges( | |
1758 | outside_scope, | |
1759 | otherwise_block, | |
1760 | candidate.next_candidate_pre_binding_block, | |
1761 | source_info, | |
dc9dc135 XL |
1762 | ); |
1763 | ||
94b46f34 XL |
1764 | // We want to ensure that the matched candidates are bound |
1765 | // after we have confirmed this candidate *and* any | |
1766 | // associated guard; Binding them on `block` is too soon, | |
1767 | // because that would be before we've checked the result | |
1768 | // from the guard. | |
1769 | // | |
dc9dc135 | 1770 | // But binding them on the arm is *too late*, because |
94b46f34 XL |
1771 | // then all of the candidates for a single arm would be |
1772 | // bound in the same place, that would cause a case like: | |
1773 | // | |
1774 | // ```rust | |
1775 | // match (30, 2) { | |
1776 | // (mut x, 1) | (2, mut x) if { true } => { ... } | |
1777 | // ... // ^^^^^^^ (this is `arm_block`) | |
1778 | // } | |
1779 | // ``` | |
1780 | // | |
1781 | // would yield a `arm_block` something like: | |
1782 | // | |
1783 | // ``` | |
1784 | // StorageLive(_4); // _4 is `x` | |
1785 | // _4 = &mut (_1.0: i32); // this is handling `(mut x, 1)` case | |
1786 | // _4 = &mut (_1.1: i32); // this is handling `(2, mut x)` case | |
1787 | // ``` | |
1788 | // | |
1789 | // and that is clearly not correct. | |
74b04a01 XL |
1790 | let by_value_bindings = |
1791 | parent_bindings | |
1792 | .iter() | |
1793 | .flat_map(|(bindings, _)| bindings) | |
1794 | .chain(&candidate.bindings) | |
1795 | .filter(|binding| { | |
1796 | if let BindingMode::ByValue = binding.binding_mode { true } else { false } | |
1797 | }); | |
48663c56 XL |
1798 | // Read all of the by reference bindings to ensure that the |
1799 | // place they refer to can't be modified by the guard. | |
1800 | for binding in by_value_bindings.clone() { | |
1801 | let local_id = self.var_local_id(binding.var_id, RefWithinGuard); | |
60c5eb7d XL |
1802 | let cause = FakeReadCause::ForGuardBinding; |
1803 | self.cfg.push_fake_read(post_guard_block, guard_end, cause, Place::from(local_id)); | |
83c7162d | 1804 | } |
74b04a01 XL |
1805 | assert!(schedule_drops, "patterns with guards must schedule drops"); |
1806 | self.bind_matched_candidate_for_arm_body(post_guard_block, true, by_value_bindings); | |
94b46f34 | 1807 | |
dc9dc135 | 1808 | post_guard_block |
e9174d1e | 1809 | } else { |
94b46f34 XL |
1810 | // (Here, it is not too early to bind the matched |
1811 | // candidate on `block`, because there is no guard result | |
1812 | // that we have to inspect before we bind them.) | |
74b04a01 XL |
1813 | self.bind_matched_candidate_for_arm_body( |
1814 | block, | |
1815 | schedule_drops, | |
1816 | parent_bindings | |
1817 | .iter() | |
1818 | .flat_map(|(bindings, _)| bindings) | |
1819 | .chain(&candidate.bindings), | |
1820 | ); | |
dc9dc135 | 1821 | block |
e9174d1e SL |
1822 | } |
1823 | } | |
1824 | ||
b7449926 XL |
1825 | /// Append `AscribeUserType` statements onto the end of `block` |
1826 | /// for each ascription | |
74b04a01 XL |
1827 | fn ascribe_types<'b>( |
1828 | &mut self, | |
1829 | block: BasicBlock, | |
1830 | ascriptions: impl IntoIterator<Item = &'b Ascription<'tcx>>, | |
1831 | ) where | |
1832 | 'tcx: 'b, | |
1833 | { | |
b7449926 XL |
1834 | for ascription in ascriptions { |
1835 | let source_info = self.source_info(ascription.span); | |
0bf4aa26 XL |
1836 | |
1837 | debug!( | |
1838 | "adding user ascription at span {:?} of place {:?} and {:?}", | |
dfeec247 | 1839 | source_info.span, ascription.source, ascription.user_ty, |
0bf4aa26 XL |
1840 | ); |
1841 | ||
e1599b0c | 1842 | let user_ty = ascription.user_ty.clone().user_ty( |
9fa01778 | 1843 | &mut self.canonical_user_type_annotations, |
532ac7d7 | 1844 | ascription.source.ty(&self.local_decls, self.hir.tcx()).ty, |
dfeec247 | 1845 | source_info.span, |
0731742a | 1846 | ); |
b7449926 XL |
1847 | self.cfg.push( |
1848 | block, | |
1849 | Statement { | |
1850 | source_info, | |
1851 | kind: StatementKind::AscribeUserType( | |
dfeec247 | 1852 | box (ascription.source, user_ty), |
0731742a | 1853 | ascription.variance, |
b7449926 XL |
1854 | ), |
1855 | }, | |
1856 | ); | |
1857 | } | |
1858 | } | |
1859 | ||
74b04a01 XL |
1860 | fn bind_matched_candidate_for_guard<'b>( |
1861 | &mut self, | |
1862 | block: BasicBlock, | |
1863 | schedule_drops: bool, | |
1864 | bindings: impl IntoIterator<Item = &'b Binding<'tcx>>, | |
1865 | ) where | |
1866 | 'tcx: 'b, | |
1867 | { | |
1868 | debug!("bind_matched_candidate_for_guard(block={:?})", block); | |
e9174d1e | 1869 | |
83c7162d XL |
1870 | // Assign each of the bindings. Since we are binding for a |
1871 | // guard expression, this will never trigger moves out of the | |
1872 | // candidate. | |
48663c56 | 1873 | let re_erased = self.hir.tcx().lifetimes.re_erased; |
83c7162d | 1874 | for binding in bindings { |
74b04a01 | 1875 | debug!("bind_matched_candidate_for_guard(binding={:?})", binding); |
83c7162d | 1876 | let source_info = self.source_info(binding.span); |
94b46f34 XL |
1877 | |
1878 | // For each pattern ident P of type T, `ref_for_guard` is | |
1879 | // a reference R: &T pointing to the location matched by | |
1880 | // the pattern, and every occurrence of P within a guard | |
1881 | // denotes *R. | |
74b04a01 XL |
1882 | let ref_for_guard = self.storage_live_binding( |
1883 | block, | |
1884 | binding.var_id, | |
1885 | binding.span, | |
1886 | RefWithinGuard, | |
1887 | schedule_drops, | |
1888 | ); | |
83c7162d XL |
1889 | match binding.binding_mode { |
1890 | BindingMode::ByValue => { | |
dfeec247 | 1891 | let rvalue = Rvalue::Ref(re_erased, BorrowKind::Shared, binding.source); |
ba9703b0 | 1892 | self.cfg.push_assign(block, source_info, ref_for_guard, rvalue); |
83c7162d | 1893 | } |
0731742a | 1894 | BindingMode::ByRef(borrow_kind) => { |
9fa01778 | 1895 | let value_for_arm = self.storage_live_binding( |
b7449926 XL |
1896 | block, |
1897 | binding.var_id, | |
1898 | binding.span, | |
9fa01778 | 1899 | OutsideGuard, |
74b04a01 | 1900 | schedule_drops, |
b7449926 | 1901 | ); |
94b46f34 | 1902 | |
dfeec247 | 1903 | let rvalue = Rvalue::Ref(re_erased, borrow_kind, binding.source); |
ba9703b0 | 1904 | self.cfg.push_assign(block, source_info, value_for_arm, rvalue); |
9fa01778 | 1905 | let rvalue = Rvalue::Ref(re_erased, BorrowKind::Shared, value_for_arm); |
ba9703b0 | 1906 | self.cfg.push_assign(block, source_info, ref_for_guard, rvalue); |
83c7162d XL |
1907 | } |
1908 | } | |
1909 | } | |
1910 | } | |
1911 | ||
9fa01778 | 1912 | fn bind_matched_candidate_for_arm_body<'b>( |
b7449926 XL |
1913 | &mut self, |
1914 | block: BasicBlock, | |
74b04a01 | 1915 | schedule_drops: bool, |
9fa01778 | 1916 | bindings: impl IntoIterator<Item = &'b Binding<'tcx>>, |
dfeec247 XL |
1917 | ) where |
1918 | 'tcx: 'b, | |
1919 | { | |
9fa01778 | 1920 | debug!("bind_matched_candidate_for_arm_body(block={:?})", block); |
0731742a | 1921 | |
48663c56 | 1922 | let re_erased = self.hir.tcx().lifetimes.re_erased; |
e9174d1e SL |
1923 | // Assign each of the bindings. This may trigger moves out of the candidate. |
1924 | for binding in bindings { | |
8bb4bdeb | 1925 | let source_info = self.source_info(binding.span); |
74b04a01 XL |
1926 | let local = self.storage_live_binding( |
1927 | block, | |
1928 | binding.var_id, | |
1929 | binding.span, | |
1930 | OutsideGuard, | |
1931 | schedule_drops, | |
1932 | ); | |
1933 | if schedule_drops { | |
1934 | self.schedule_drop_for_binding(binding.var_id, binding.span, OutsideGuard); | |
1935 | } | |
e9174d1e | 1936 | let rvalue = match binding.binding_mode { |
ba9703b0 | 1937 | BindingMode::ByValue => Rvalue::Use(self.consume_by_copy_or_move(binding.source)), |
0731742a | 1938 | BindingMode::ByRef(borrow_kind) => { |
dfeec247 | 1939 | Rvalue::Ref(re_erased, borrow_kind, binding.source) |
83c7162d | 1940 | } |
e9174d1e | 1941 | }; |
ba9703b0 | 1942 | self.cfg.push_assign(block, source_info, local, rvalue); |
e9174d1e SL |
1943 | } |
1944 | } | |
1945 | ||
9fa01778 XL |
1946 | /// Each binding (`ref mut var`/`ref var`/`mut var`/`var`, where the bound |
1947 | /// `var` has type `T` in the arm body) in a pattern maps to 2 locals. The | |
1948 | /// first local is a binding for occurrences of `var` in the guard, which | |
1949 | /// will have type `&T`. The second local is a binding for occurrences of | |
1950 | /// `var` in the arm body, which will have type `T`. | |
b7449926 XL |
1951 | fn declare_binding( |
1952 | &mut self, | |
1953 | source_info: SourceInfo, | |
1954 | visibility_scope: SourceScope, | |
1955 | mutability: Mutability, | |
f9f354fc | 1956 | name: Symbol, |
b7449926 | 1957 | mode: BindingMode, |
532ac7d7 | 1958 | var_id: HirId, |
b7449926 | 1959 | var_ty: Ty<'tcx>, |
532ac7d7 | 1960 | user_ty: UserTypeProjections, |
b7449926 XL |
1961 | has_guard: ArmHasGuard, |
1962 | opt_match_place: Option<(Option<Place<'tcx>>, Span)>, | |
1963 | pat_span: Span, | |
1964 | ) { | |
1965 | debug!( | |
1966 | "declare_binding(var_id={:?}, name={:?}, mode={:?}, var_ty={:?}, \ | |
1967 | visibility_scope={:?}, source_info={:?})", | |
1968 | var_id, name, mode, var_ty, visibility_scope, source_info | |
1969 | ); | |
e9174d1e | 1970 | |
83c7162d | 1971 | let tcx = self.hir.tcx(); |
dfeec247 | 1972 | let debug_source_info = SourceInfo { span: source_info.span, scope: visibility_scope }; |
94b46f34 | 1973 | let binding_mode = match mode { |
74b04a01 XL |
1974 | BindingMode::ByValue => ty::BindingMode::BindByValue(mutability), |
1975 | BindingMode::ByRef(_) => ty::BindingMode::BindByReference(mutability), | |
94b46f34 | 1976 | }; |
0731742a | 1977 | debug!("declare_binding: user_ty={:?}", user_ty); |
94b46f34 | 1978 | let local = LocalDecl::<'tcx> { |
3b2f2976 | 1979 | mutability, |
b7449926 | 1980 | ty: var_ty, |
f9f354fc | 1981 | user_ty: if user_ty.is_empty() { None } else { Some(box user_ty) }, |
3b2f2976 | 1982 | source_info, |
ea8adc8c | 1983 | internal: false, |
0bf4aa26 | 1984 | is_block_tail: None, |
3dfed10e XL |
1985 | local_info: Some(box LocalInfo::User(ClearCrossCrate::Set(BindingForm::Var( |
1986 | VarBindingForm { | |
1987 | binding_mode, | |
1988 | // hypothetically, `visit_primary_bindings` could try to unzip | |
1989 | // an outermost hir::Ty as we descend, matching up | |
1990 | // idents in pat; but complex w/ unclear UI payoff. | |
1991 | // Instead, just abandon providing diagnostic info. | |
1992 | opt_ty_info: None, | |
1993 | opt_match_place, | |
1994 | pat_span, | |
1995 | }, | |
1996 | )))), | |
94b46f34 | 1997 | }; |
dc9dc135 | 1998 | let for_arm_body = self.local_decls.push(local); |
60c5eb7d XL |
1999 | self.var_debug_info.push(VarDebugInfo { |
2000 | name, | |
2001 | source_info: debug_source_info, | |
2002 | place: for_arm_body.into(), | |
2003 | }); | |
48663c56 | 2004 | let locals = if has_guard.0 { |
94b46f34 | 2005 | let ref_for_guard = self.local_decls.push(LocalDecl::<'tcx> { |
9fa01778 XL |
2006 | // This variable isn't mutated but has a name, so has to be |
2007 | // immutable to avoid the unused mut lint. | |
b7449926 | 2008 | mutability: Mutability::Not, |
48663c56 | 2009 | ty: tcx.mk_imm_ref(tcx.lifetimes.re_erased, var_ty), |
f9f354fc | 2010 | user_ty: None, |
83c7162d | 2011 | source_info, |
83c7162d | 2012 | internal: false, |
0bf4aa26 | 2013 | is_block_tail: None, |
3dfed10e XL |
2014 | local_info: Some(box LocalInfo::User(ClearCrossCrate::Set( |
2015 | BindingForm::RefForGuard, | |
2016 | ))), | |
60c5eb7d XL |
2017 | }); |
2018 | self.var_debug_info.push(VarDebugInfo { | |
2019 | name, | |
2020 | source_info: debug_source_info, | |
2021 | place: ref_for_guard.into(), | |
83c7162d | 2022 | }); |
dfeec247 | 2023 | LocalsForNode::ForGuard { ref_for_guard, for_arm_body } |
83c7162d XL |
2024 | } else { |
2025 | LocalsForNode::One(for_arm_body) | |
2026 | }; | |
2027 | debug!("declare_binding: vars={:?}", locals); | |
2028 | self.var_indices.insert(var_id, locals); | |
e9174d1e SL |
2029 | } |
2030 | } |