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