rustc_mir_build/builder/matches/mod.rs
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
8use std::borrow::Borrow;
9use std::mem;
10use std::sync::Arc;
11
12use itertools::{Itertools, Position};
13use rustc_abi::VariantIdx;
14use rustc_data_structures::fx::FxIndexMap;
15use rustc_data_structures::stack::ensure_sufficient_stack;
16use rustc_hir::{BindingMode, ByRef, LetStmt, LocalSource, Node};
17use rustc_middle::bug;
18use rustc_middle::middle::region;
19use rustc_middle::mir::*;
20use rustc_middle::thir::{self, *};
21use rustc_middle::ty::{self, CanonicalUserTypeAnnotation, Ty, ValTree, ValTreeKind};
22use rustc_pattern_analysis::constructor::RangeEnd;
23use rustc_pattern_analysis::rustc::{DeconstructedPat, RustcPatCtxt};
24use rustc_span::{BytePos, Pos, Span, Symbol, sym};
25use tracing::{debug, instrument};
26
27use crate::builder::ForGuard::{self, OutsideGuard, RefWithinGuard};
28use crate::builder::expr::as_place::PlaceBuilder;
29use crate::builder::matches::user_ty::ProjectedUserTypesNode;
30use crate::builder::scope::DropKind;
31use crate::builder::{
32 BlockAnd, BlockAndExtension, Builder, GuardFrame, GuardFrameLocal, LocalsForNode,
33};
34
35// helper functions, broken out by category:
36mod match_pair;
37mod test;
38mod user_ty;
39mod util;
40
41/// Arguments to [`Builder::then_else_break_inner`] that are usually forwarded
42/// to recursive invocations.
43#[derive(Clone, Copy)]
44struct ThenElseArgs {
45 /// Used as the temp scope for lowering `expr`. If absent (for match guards),
46 /// `self.local_scope()` is used.
47 temp_scope_override: Option<region::Scope>,
48 variable_source_info: SourceInfo,
49 /// Determines how bindings should be handled when lowering `let` expressions.
50 ///
51 /// Forwarded to [`Builder::lower_let_expr`] when lowering [`ExprKind::Let`].
52 declare_let_bindings: DeclareLetBindings,
53}
54
55/// Should lowering a `let` expression also declare its bindings?
56///
57/// Used by [`Builder::lower_let_expr`] when lowering [`ExprKind::Let`].
58#[derive(Clone, Copy)]
59pub(crate) enum DeclareLetBindings {
60 /// Yes, declare `let` bindings as normal for `if` conditions.
61 Yes,
62 /// No, don't declare `let` bindings, because the caller declares them
63 /// separately due to special requirements.
64 ///
65 /// Used for match guards and let-else.
66 No,
67 /// Let expressions are not permitted in this context, so it is a bug to
68 /// try to lower one (e.g inside lazy-boolean-or or boolean-not).
69 LetNotPermitted,
70}
71
72/// Used by [`Builder::storage_live_binding`] and [`Builder::bind_matched_candidate_for_arm_body`]
73/// to decide whether to schedule drops.
74#[derive(Clone, Copy, Debug)]
75pub(crate) enum ScheduleDrops {
76 /// Yes, the relevant functions should also schedule drops as appropriate.
77 Yes,
78 /// No, don't schedule drops. The caller has taken responsibility for any
79 /// appropriate drops.
80 No,
81}
82
83impl<'a, 'tcx> Builder<'a, 'tcx> {
84 /// Lowers a condition in a way that ensures that variables bound in any let
85 /// expressions are definitely initialized in the if body.
86 ///
87 /// If `declare_let_bindings` is false then variables created in `let`
88 /// expressions will not be declared. This is for if let guards on arms with
89 /// an or pattern, where the guard is lowered multiple times.
90 pub(crate) fn then_else_break(
91 &mut self,
92 block: BasicBlock,
93 expr_id: ExprId,
94 temp_scope_override: Option<region::Scope>,
95 variable_source_info: SourceInfo,
96 declare_let_bindings: DeclareLetBindings,
97 ) -> BlockAnd<()> {
98 self.then_else_break_inner(
99 block,
100 expr_id,
101 ThenElseArgs { temp_scope_override, variable_source_info, declare_let_bindings },
102 )
103 }
104
105 fn then_else_break_inner(
106 &mut self,
107 block: BasicBlock, // Block that the condition and branch will be lowered into
108 expr_id: ExprId, // Condition expression to lower
109 args: ThenElseArgs,
110 ) -> BlockAnd<()> {
111 let this = self;
112 let expr = &this.thir[expr_id];
113 let expr_span = expr.span;
114
115 match expr.kind {
116 ExprKind::LogicalOp { op: LogicalOp::And, lhs, rhs } => {
117 let lhs_then_block = this.then_else_break_inner(block, lhs, args).into_block();
118 let rhs_then_block =
119 this.then_else_break_inner(lhs_then_block, rhs, args).into_block();
120 rhs_then_block.unit()
121 }
122 ExprKind::LogicalOp { op: LogicalOp::Or, lhs, rhs } => {
123 let local_scope = this.local_scope();
124 let (lhs_success_block, failure_block) =
125 this.in_if_then_scope(local_scope, expr_span, |this| {
126 this.then_else_break_inner(
127 block,
128 lhs,
129 ThenElseArgs {
130 declare_let_bindings: DeclareLetBindings::LetNotPermitted,
131 ..args
132 },
133 )
134 });
135 let rhs_success_block = this
136 .then_else_break_inner(
137 failure_block,
138 rhs,
139 ThenElseArgs {
140 declare_let_bindings: DeclareLetBindings::LetNotPermitted,
141 ..args
142 },
143 )
144 .into_block();
145
146 // Make the LHS and RHS success arms converge to a common block.
147 // (We can't just make LHS goto RHS, because `rhs_success_block`
148 // might contain statements that we don't want on the LHS path.)
149 let success_block = this.cfg.start_new_block();
150 this.cfg.goto(lhs_success_block, args.variable_source_info, success_block);
151 this.cfg.goto(rhs_success_block, args.variable_source_info, success_block);
152 success_block.unit()
153 }
154 ExprKind::Unary { op: UnOp::Not, arg } => {
155 // Improve branch coverage instrumentation by noting conditions
156 // nested within one or more `!` expressions.
157 // (Skipped if branch coverage is not enabled.)
158 if let Some(coverage_info) = this.coverage_info.as_mut() {
159 coverage_info.visit_unary_not(this.thir, expr_id);
160 }
161
162 let local_scope = this.local_scope();
163 let (success_block, failure_block) =
164 this.in_if_then_scope(local_scope, expr_span, |this| {
165 // Help out coverage instrumentation by injecting a dummy statement with
166 // the original condition's span (including `!`). This fixes #115468.
167 if this.tcx.sess.instrument_coverage() {
168 this.cfg.push_coverage_span_marker(block, this.source_info(expr_span));
169 }
170 this.then_else_break_inner(
171 block,
172 arg,
173 ThenElseArgs {
174 declare_let_bindings: DeclareLetBindings::LetNotPermitted,
175 ..args
176 },
177 )
178 });
179 this.break_for_else(success_block, args.variable_source_info);
180 failure_block.unit()
181 }
182 ExprKind::Scope { region_scope, lint_level, value } => {
183 let region_scope = (region_scope, this.source_info(expr_span));
184 this.in_scope(region_scope, lint_level, |this| {
185 this.then_else_break_inner(block, value, args)
186 })
187 }
188 ExprKind::Use { source } => this.then_else_break_inner(block, source, args),
189 ExprKind::Let { expr, ref pat } => this.lower_let_expr(
190 block,
191 expr,
192 pat,
193 Some(args.variable_source_info.scope),
194 args.variable_source_info.span,
195 args.declare_let_bindings,
196 ),
197 _ => {
198 let mut block = block;
199 let temp_scope = args.temp_scope_override.unwrap_or_else(|| this.local_scope());
200 let mutability = Mutability::Mut;
201
202 let place = unpack!(
203 block = this.as_temp(
204 block,
205 TempLifetime {
206 temp_lifetime: Some(temp_scope),
207 backwards_incompatible: None
208 },
209 expr_id,
210 mutability
211 )
212 );
213
214 let operand = Operand::Move(Place::from(place));
215
216 let then_block = this.cfg.start_new_block();
217 let else_block = this.cfg.start_new_block();
218 let term = TerminatorKind::if_(operand, then_block, else_block);
219
220 // Record branch coverage info for this condition.
221 // (Does nothing if branch coverage is not enabled.)
222 this.visit_coverage_branch_condition(expr_id, then_block, else_block);
223
224 let source_info = this.source_info(expr_span);
225 this.cfg.terminate(block, source_info, term);
226 this.break_for_else(else_block, source_info);
227
228 then_block.unit()
229 }
230 }
231 }
232
233 /// Generates MIR for a `match` expression.
234 ///
235 /// The MIR that we generate for a match looks like this.
236 ///
237 /// ```text
238 /// [ 0. Pre-match ]
239 /// |
240 /// [ 1. Evaluate Scrutinee (expression being matched on) ]
241 /// [ (PlaceMention of scrutinee) ]
242 /// |
243 /// [ 2. Decision tree -- check discriminants ] <--------+
244 /// | |
245 /// | (once a specific arm is chosen) |
246 /// | |
247 /// [pre_binding_block] [otherwise_block]
248 /// | |
249 /// [ 3. Create "guard bindings" for arm ] |
250 /// [ (create fake borrows) ] |
251 /// | |
252 /// [ 4. Execute guard code ] |
253 /// [ (read fake borrows) ] --(guard is false)-----------+
254 /// |
255 /// | (guard results in true)
256 /// |
257 /// [ 5. Create real bindings and execute arm ]
258 /// |
259 /// [ Exit match ]
260 /// ```
261 ///
262 /// All of the different arms have been stacked on top of each other to
263 /// simplify the diagram. For an arm with no guard the blocks marked 3 and
264 /// 4 and the fake borrows are omitted.
265 ///
266 /// We generate MIR in the following steps:
267 ///
268 /// 1. Evaluate the scrutinee and add the PlaceMention of it ([Builder::lower_scrutinee]).
269 /// 2. Create the decision tree ([Builder::lower_match_tree]).
270 /// 3. Determine the fake borrows that are needed from the places that were
271 /// matched against and create the required temporaries for them
272 /// ([util::collect_fake_borrows]).
273 /// 4. Create everything else: the guards and the arms ([Builder::lower_match_arms]).
274 ///
275 /// ## False edges
276 ///
277 /// We don't want to have the exact structure of the decision tree be visible through borrow
278 /// checking. Specifically we want borrowck to think that:
279 /// - at any point, any or none of the patterns and guards seen so far may have been tested;
280 /// - after the match, any of the patterns may have matched.
281 ///
282 /// For example, all of these would fail to error if borrowck could see the real CFG (examples
283 /// taken from `tests/ui/nll/match-cfg-fake-edges.rs`):
284 /// ```ignore (too many errors, this is already in the test suite)
285 /// let x = String::new();
286 /// let _ = match true {
287 /// _ => {},
288 /// _ => drop(x),
289 /// };
290 /// // Borrowck must not know the second arm is never run.
291 /// drop(x); //~ ERROR use of moved value
292 ///
293 /// let x;
294 /// # let y = true;
295 /// match y {
296 /// _ if { x = 2; true } => {},
297 /// // Borrowck must not know the guard is always run.
298 /// _ => drop(x), //~ ERROR used binding `x` is possibly-uninitialized
299 /// };
300 ///
301 /// let x = String::new();
302 /// # let y = true;
303 /// match y {
304 /// false if { drop(x); true } => {},
305 /// // Borrowck must not know the guard is not run in the `true` case.
306 /// true => drop(x), //~ ERROR use of moved value: `x`
307 /// false => {},
308 /// };
309 ///
310 /// # let mut y = (true, true);
311 /// let r = &mut y.1;
312 /// match y {
313 /// //~^ ERROR cannot use `y.1` because it was mutably borrowed
314 /// (false, true) => {}
315 /// // Borrowck must not know we don't test `y.1` when `y.0` is `true`.
316 /// (true, _) => drop(r),
317 /// (false, _) => {}
318 /// };
319 /// ```
320 ///
321 /// We add false edges to act as if we were naively matching each arm in order. What we need is
322 /// a (fake) path from each candidate to the next, specifically from candidate C's pre-binding
323 /// block to next candidate D's pre-binding block. For maximum precision (needed for deref
324 /// patterns), we choose the earliest node on D's success path that doesn't also lead to C (to
325 /// avoid loops).
326 ///
327 /// This turns out to be easy to compute: that block is the `start_block` of the first call to
328 /// `match_candidates` where D is the first candidate in the list.
329 ///
330 /// For example:
331 /// ```rust
332 /// # let (x, y) = (true, true);
333 /// match (x, y) {
334 /// (true, true) => 1,
335 /// (false, true) => 2,
336 /// (true, false) => 3,
337 /// _ => 4,
338 /// }
339 /// # ;
340 /// ```
341 /// In this example, the pre-binding block of arm 1 has a false edge to the block for result
342 /// `false` of the first test on `x`. The other arms have false edges to the pre-binding blocks
343 /// of the next arm.
344 ///
345 /// On top of this, we also add a false edge from the otherwise_block of each guard to the
346 /// aforementioned start block of the next candidate, to ensure borrock doesn't rely on which
347 /// guards may have run.
348 #[instrument(level = "debug", skip(self, arms))]
349 pub(crate) fn match_expr(
350 &mut self,
351 destination: Place<'tcx>,
352 mut block: BasicBlock,
353 scrutinee_id: ExprId,
354 arms: &[ArmId],
355 span: Span,
356 scrutinee_span: Span,
357 ) -> BlockAnd<()> {
358 let scrutinee_place =
359 unpack!(block = self.lower_scrutinee(block, scrutinee_id, scrutinee_span));
360
361 let match_start_span = span.shrink_to_lo().to(scrutinee_span);
362 let patterns = arms
363 .iter()
364 .map(|&arm| {
365 let arm = &self.thir[arm];
366 let has_match_guard =
367 if arm.guard.is_some() { HasMatchGuard::Yes } else { HasMatchGuard::No };
368 (&*arm.pattern, has_match_guard)
369 })
370 .collect();
371 let built_tree = self.lower_match_tree(
372 block,
373 scrutinee_span,
374 &scrutinee_place,
375 match_start_span,
376 patterns,
377 false,
378 );
379
380 self.lower_match_arms(
381 destination,
382 scrutinee_place,
383 scrutinee_span,
384 arms,
385 built_tree,
386 self.source_info(span),
387 )
388 }
389
390 /// Evaluate the scrutinee and add the PlaceMention for it.
391 pub(crate) fn lower_scrutinee(
392 &mut self,
393 mut block: BasicBlock,
394 scrutinee_id: ExprId,
395 scrutinee_span: Span,
396 ) -> BlockAnd<PlaceBuilder<'tcx>> {
397 let scrutinee_place_builder = unpack!(block = self.as_place_builder(block, scrutinee_id));
398 if let Some(scrutinee_place) = scrutinee_place_builder.try_to_place(self) {
399 let source_info = self.source_info(scrutinee_span);
400 self.cfg.push_place_mention(block, source_info, scrutinee_place);
401 }
402
403 block.and(scrutinee_place_builder)
404 }
405
406 /// Lower the bindings, guards and arm bodies of a `match` expression.
407 ///
408 /// The decision tree should have already been created
409 /// (by [Builder::lower_match_tree]).
410 ///
411 /// `outer_source_info` is the SourceInfo for the whole match.
412 pub(crate) fn lower_match_arms(
413 &mut self,
414 destination: Place<'tcx>,
415 scrutinee_place_builder: PlaceBuilder<'tcx>,
416 scrutinee_span: Span,
417 arms: &[ArmId],
418 built_match_tree: BuiltMatchTree<'tcx>,
419 outer_source_info: SourceInfo,
420 ) -> BlockAnd<()> {
421 let arm_end_blocks: Vec<BasicBlock> = arms
422 .iter()
423 .map(|&arm| &self.thir[arm])
424 .zip(built_match_tree.branches)
425 .map(|(arm, branch)| {
426 debug!("lowering arm {:?}\ncorresponding branch = {:?}", arm, branch);
427
428 let arm_source_info = self.source_info(arm.span);
429 let arm_scope = (arm.scope, arm_source_info);
430 let match_scope = self.local_scope();
431 let guard_scope = arm
432 .guard
433 .map(|_| region::Scope { data: region::ScopeData::MatchGuard, ..arm.scope });
434 self.in_scope(arm_scope, arm.lint_level, |this| {
435 this.opt_in_scope(guard_scope.map(|scope| (scope, arm_source_info)), |this| {
436 // `if let` guard temps needing deduplicating will be in the guard scope.
437 let old_dedup_scope =
438 mem::replace(&mut this.fixed_temps_scope, guard_scope);
439
440 // `try_to_place` may fail if it is unable to resolve the given
441 // `PlaceBuilder` inside a closure. In this case, we don't want to include
442 // a scrutinee place. `scrutinee_place_builder` will fail to be resolved
443 // if the only match arm is a wildcard (`_`).
444 // Example:
445 // ```
446 // let foo = (0, 1);
447 // let c = || {
448 // match foo { _ => () };
449 // };
450 // ```
451 let scrutinee_place = scrutinee_place_builder.try_to_place(this);
452 let opt_scrutinee_place =
453 scrutinee_place.as_ref().map(|place| (Some(place), scrutinee_span));
454 let scope = this.declare_bindings(
455 None,
456 arm.span,
457 &arm.pattern,
458 arm.guard,
459 opt_scrutinee_place,
460 );
461
462 let arm_block = this.bind_pattern(
463 outer_source_info,
464 branch,
465 &built_match_tree.fake_borrow_temps,
466 scrutinee_span,
467 Some((arm, match_scope)),
468 );
469
470 this.fixed_temps_scope = old_dedup_scope;
471
472 if let Some(source_scope) = scope {
473 this.source_scope = source_scope;
474 }
475
476 this.expr_into_dest(destination, arm_block, arm.body)
477 })
478 })
479 .into_block()
480 })
481 .collect();
482
483 // all the arm blocks will rejoin here
484 let end_block = self.cfg.start_new_block();
485
486 let end_brace = self.source_info(
487 outer_source_info.span.with_lo(outer_source_info.span.hi() - BytePos::from_usize(1)),
488 );
489 for arm_block in arm_end_blocks {
490 let block = &self.cfg.basic_blocks[arm_block];
491 let last_location = block.statements.last().map(|s| s.source_info);
492
493 self.cfg.goto(arm_block, last_location.unwrap_or(end_brace), end_block);
494 }
495
496 self.source_scope = outer_source_info.scope;
497
498 end_block.unit()
499 }
500
501 /// For a top-level `match` arm or a `let` binding, binds the variables and
502 /// ascribes types, and also checks the match arm guard (if present).
503 ///
504 /// `arm_scope` should be `Some` if and only if this is called for a
505 /// `match` arm.
506 ///
507 /// In the presence of or-patterns, a match arm might have multiple
508 /// sub-branches representing different ways to match, with each sub-branch
509 /// requiring its own bindings and its own copy of the guard. This method
510 /// handles those sub-branches individually, and then has them jump together
511 /// to a common block.
512 ///
513 /// Returns a single block that the match arm can be lowered into.
514 /// (For `let` bindings, this is the code that can use the bindings.)
515 fn bind_pattern(
516 &mut self,
517 outer_source_info: SourceInfo,
518 branch: MatchTreeBranch<'tcx>,
519 fake_borrow_temps: &[(Place<'tcx>, Local, FakeBorrowKind)],
520 scrutinee_span: Span,
521 arm_match_scope: Option<(&Arm<'tcx>, region::Scope)>,
522 ) -> BasicBlock {
523 if branch.sub_branches.len() == 1 {
524 let [sub_branch] = branch.sub_branches.try_into().unwrap();
525 // Avoid generating another `BasicBlock` when we only have one sub branch.
526 self.bind_and_guard_matched_candidate(
527 sub_branch,
528 fake_borrow_temps,
529 scrutinee_span,
530 arm_match_scope,
531 ScheduleDrops::Yes,
532 )
533 } else {
534 // It's helpful to avoid scheduling drops multiple times to save
535 // drop elaboration from having to clean up the extra drops.
536 //
537 // If we are in a `let` then we only schedule drops for the first
538 // candidate.
539 //
540 // If we're in a `match` arm then we could have a case like so:
541 //
542 // Ok(x) | Err(x) if return => { /* ... */ }
543 //
544 // In this case we don't want a drop of `x` scheduled when we
545 // return: it isn't bound by move until right before enter the arm.
546 // To handle this we instead unschedule it's drop after each time
547 // we lower the guard.
548 // As a result, we end up with the drop order of the last sub-branch we lower. To use
549 // the drop order for the first sub-branch, we lower sub-branches in reverse (#142163).
550 let target_block = self.cfg.start_new_block();
551 for (pos, sub_branch) in branch.sub_branches.into_iter().rev().with_position() {
552 debug_assert!(pos != Position::Only);
553 let schedule_drops =
554 if pos == Position::Last { ScheduleDrops::Yes } else { ScheduleDrops::No };
555 let binding_end = self.bind_and_guard_matched_candidate(
556 sub_branch,
557 fake_borrow_temps,
558 scrutinee_span,
559 arm_match_scope,
560 schedule_drops,
561 );
562 self.cfg.goto(binding_end, outer_source_info, target_block);
563 }
564
565 target_block
566 }
567 }
568
569 pub(super) fn expr_into_pattern(
570 &mut self,
571 mut block: BasicBlock,
572 irrefutable_pat: &Pat<'tcx>,
573 initializer_id: ExprId,
574 ) -> BlockAnd<()> {
575 match irrefutable_pat.kind {
576 // Optimize the case of `let x = ...` to write directly into `x`
577 PatKind::Binding { mode: BindingMode(ByRef::No, _), var, subpattern: None, .. } => {
578 let place = self.storage_live_binding(
579 block,
580 var,
581 irrefutable_pat.span,
582 false,
583 OutsideGuard,
584 ScheduleDrops::Yes,
585 );
586 block = self.expr_into_dest(place, block, initializer_id).into_block();
587
588 // Inject a fake read, see comments on `FakeReadCause::ForLet`.
589 let source_info = self.source_info(irrefutable_pat.span);
590 self.cfg.push_fake_read(block, source_info, FakeReadCause::ForLet(None), place);
591
592 self.schedule_drop_for_binding(var, irrefutable_pat.span, OutsideGuard);
593 block.unit()
594 }
595
596 // Optimize the case of `let x: T = ...` to write directly
597 // into `x` and then require that `T == typeof(x)`.
598 PatKind::AscribeUserType {
599 ref subpattern,
600 ascription: thir::Ascription { ref annotation, variance: _ },
601 } if let PatKind::Binding {
602 mode: BindingMode(ByRef::No, _),
603 var,
604 subpattern: None,
605 ..
606 } = subpattern.kind =>
607 {
608 let place = self.storage_live_binding(
609 block,
610 var,
611 irrefutable_pat.span,
612 false,
613 OutsideGuard,
614 ScheduleDrops::Yes,
615 );
616 block = self.expr_into_dest(place, block, initializer_id).into_block();
617
618 // Inject a fake read, see comments on `FakeReadCause::ForLet`.
619 let pattern_source_info = self.source_info(irrefutable_pat.span);
620 let cause_let = FakeReadCause::ForLet(None);
621 self.cfg.push_fake_read(block, pattern_source_info, cause_let, place);
622
623 let ty_source_info = self.source_info(annotation.span);
624
625 let base = self.canonical_user_type_annotations.push(annotation.clone());
626 self.cfg.push(
627 block,
628 Statement::new(
629 ty_source_info,
630 StatementKind::AscribeUserType(
631 Box::new((place, UserTypeProjection { base, projs: Vec::new() })),
632 // We always use invariant as the variance here. This is because the
633 // variance field from the ascription refers to the variance to use
634 // when applying the type to the value being matched, but this
635 // ascription applies rather to the type of the binding. e.g., in this
636 // example:
637 //
638 // ```
639 // let x: T = <expr>
640 // ```
641 //
642 // We are creating an ascription that defines the type of `x` to be
643 // exactly `T` (i.e., with invariance). The variance field, in
644 // contrast, is intended to be used to relate `T` to the type of
645 // `<expr>`.
646 ty::Invariant,
647 ),
648 ),
649 );
650
651 self.schedule_drop_for_binding(var, irrefutable_pat.span, OutsideGuard);
652 block.unit()
653 }
654
655 _ => {
656 let initializer = &self.thir[initializer_id];
657 let place_builder =
658 unpack!(block = self.lower_scrutinee(block, initializer_id, initializer.span));
659 self.place_into_pattern(block, irrefutable_pat, place_builder, true)
660 }
661 }
662 }
663
664 pub(crate) fn place_into_pattern(
665 &mut self,
666 block: BasicBlock,
667 irrefutable_pat: &Pat<'tcx>,
668 initializer: PlaceBuilder<'tcx>,
669 set_match_place: bool,
670 ) -> BlockAnd<()> {
671 let built_tree = self.lower_match_tree(
672 block,
673 irrefutable_pat.span,
674 &initializer,
675 irrefutable_pat.span,
676 vec![(irrefutable_pat, HasMatchGuard::No)],
677 false,
678 );
679 let [branch] = built_tree.branches.try_into().unwrap();
680
681 // For matches and function arguments, the place that is being matched
682 // can be set when creating the variables. But the place for
683 // let PATTERN = ... might not even exist until we do the assignment.
684 // so we set it here instead.
685 if set_match_place {
686 // `try_to_place` may fail if it is unable to resolve the given `PlaceBuilder` inside a
687 // closure. In this case, we don't want to include a scrutinee place.
688 // `scrutinee_place_builder` will fail for destructured assignments. This is because a
689 // closure only captures the precise places that it will read and as a result a closure
690 // may not capture the entire tuple/struct and rather have individual places that will
691 // be read in the final MIR.
692 // Example:
693 // ```
694 // let foo = (0, 1);
695 // let c = || {
696 // let (v1, v2) = foo;
697 // };
698 // ```
699 if let Some(place) = initializer.try_to_place(self) {
700 // Because or-alternatives bind the same variables, we only explore the first one.
701 let first_sub_branch = branch.sub_branches.first().unwrap();
702 for binding in &first_sub_branch.bindings {
703 let local = self.var_local_id(binding.var_id, OutsideGuard);
704 if let LocalInfo::User(BindingForm::Var(VarBindingForm {
705 opt_match_place: Some((ref mut match_place, _)),
706 ..
707 })) = **self.local_decls[local].local_info.as_mut().unwrap_crate_local()
708 {
709 *match_place = Some(place);
710 } else {
711 bug!("Let binding to non-user variable.")
712 };
713 }
714 }
715 }
716
717 self.bind_pattern(
718 self.source_info(irrefutable_pat.span),
719 branch,
720 &[],
721 irrefutable_pat.span,
722 None,
723 )
724 .unit()
725 }
726
727 /// Declares the bindings of the given patterns and returns the visibility
728 /// scope for the bindings in these patterns, if such a scope had to be
729 /// created. NOTE: Declaring the bindings should always be done in their
730 /// drop scope.
731 #[instrument(skip(self), level = "debug")]
732 pub(crate) fn declare_bindings(
733 &mut self,
734 mut visibility_scope: Option<SourceScope>,
735 scope_span: Span,
736 pattern: &Pat<'tcx>,
737 guard: Option<ExprId>,
738 opt_match_place: Option<(Option<&Place<'tcx>>, Span)>,
739 ) -> Option<SourceScope> {
740 self.visit_primary_bindings_special(
741 pattern,
742 &ProjectedUserTypesNode::None,
743 &mut |this, name, mode, var, span, ty, user_tys| {
744 let saved_scope = this.source_scope;
745 this.set_correct_source_scope_for_arg(var.0, saved_scope, span);
746 let vis_scope = *visibility_scope
747 .get_or_insert_with(|| this.new_source_scope(scope_span, LintLevel::Inherited));
748 let source_info = SourceInfo { span, scope: this.source_scope };
749 let user_tys = user_tys.build_user_type_projections();
750
751 this.declare_binding(
752 source_info,
753 vis_scope,
754 name,
755 mode,
756 var,
757 ty,
758 user_tys,
759 ArmHasGuard(guard.is_some()),
760 opt_match_place.map(|(x, y)| (x.cloned(), y)),
761 pattern.span,
762 );
763 this.source_scope = saved_scope;
764 },
765 );
766 if let Some(guard_expr) = guard {
767 self.declare_guard_bindings(guard_expr, scope_span, visibility_scope);
768 }
769 visibility_scope
770 }
771
772 /// Declare bindings in a guard. This has to be done when declaring bindings
773 /// for an arm to ensure that or patterns only have one version of each
774 /// variable.
775 pub(crate) fn declare_guard_bindings(
776 &mut self,
777 guard_expr: ExprId,
778 scope_span: Span,
779 visibility_scope: Option<SourceScope>,
780 ) {
781 match self.thir.exprs[guard_expr].kind {
782 ExprKind::Let { expr: _, pat: ref guard_pat } => {
783 // FIXME: pass a proper `opt_match_place`
784 self.declare_bindings(visibility_scope, scope_span, guard_pat, None, None);
785 }
786 ExprKind::Scope { value, .. } => {
787 self.declare_guard_bindings(value, scope_span, visibility_scope);
788 }
789 ExprKind::Use { source } => {
790 self.declare_guard_bindings(source, scope_span, visibility_scope);
791 }
792 ExprKind::LogicalOp { op: LogicalOp::And, lhs, rhs } => {
793 self.declare_guard_bindings(lhs, scope_span, visibility_scope);
794 self.declare_guard_bindings(rhs, scope_span, visibility_scope);
795 }
796 _ => {}
797 }
798 }
799
800 /// Emits a [`StatementKind::StorageLive`] for the given var, and also
801 /// schedules a drop if requested (and possible).
802 pub(crate) fn storage_live_binding(
803 &mut self,
804 block: BasicBlock,
805 var: LocalVarId,
806 span: Span,
807 is_shorthand: bool,
808 for_guard: ForGuard,
809 schedule_drop: ScheduleDrops,
810 ) -> Place<'tcx> {
811 let local_id = self.var_local_id(var, for_guard);
812 let source_info = self.source_info(span);
813 self.cfg.push(block, Statement::new(source_info, StatementKind::StorageLive(local_id)));
814 // Although there is almost always scope for given variable in corner cases
815 // like #92893 we might get variable with no scope.
816 if let Some(region_scope) = self.region_scope_tree.var_scope(var.0.local_id)
817 && matches!(schedule_drop, ScheduleDrops::Yes)
818 {
819 self.schedule_drop(span, region_scope, local_id, DropKind::Storage);
820 }
821 let local_info = self.local_decls[local_id].local_info.as_mut().unwrap_crate_local();
822 if let LocalInfo::User(BindingForm::Var(var_info)) = &mut **local_info {
823 var_info.introductions.push(VarBindingIntroduction { span, is_shorthand });
824 }
825 Place::from(local_id)
826 }
827
828 pub(crate) fn schedule_drop_for_binding(
829 &mut self,
830 var: LocalVarId,
831 span: Span,
832 for_guard: ForGuard,
833 ) {
834 let local_id = self.var_local_id(var, for_guard);
835 if let Some(region_scope) = self.region_scope_tree.var_scope(var.0.local_id) {
836 self.schedule_drop(span, region_scope, local_id, DropKind::Value);
837 }
838 }
839
840 /// Visits all of the "primary" bindings in a pattern, i.e. the leftmost
841 /// occurrence of each variable bound by the pattern.
842 /// See [`PatKind::Binding::is_primary`] for more context.
843 ///
844 /// This variant provides only the limited subset of binding data needed
845 /// by its callers, and should be a "pure" visit without side-effects.
846 pub(super) fn visit_primary_bindings(
847 &mut self,
848 pattern: &Pat<'tcx>,
849 f: &mut impl FnMut(&mut Self, LocalVarId, Span),
850 ) {
851 pattern.walk_always(|pat| {
852 if let PatKind::Binding { var, is_primary: true, .. } = pat.kind {
853 f(self, var, pat.span);
854 }
855 })
856 }
857
858 /// Visits all of the "primary" bindings in a pattern, while preparing
859 /// additional user-type-annotation data needed by `declare_bindings`.
860 ///
861 /// This also has the side-effect of pushing all user type annotations
862 /// onto `canonical_user_type_annotations`, so that they end up in MIR
863 /// even if they aren't associated with any bindings.
864 #[instrument(level = "debug", skip(self, f))]
865 fn visit_primary_bindings_special(
866 &mut self,
867 pattern: &Pat<'tcx>,
868 user_tys: &ProjectedUserTypesNode<'_>,
869 f: &mut impl FnMut(
870 &mut Self,
871 Symbol,
872 BindingMode,
873 LocalVarId,
874 Span,
875 Ty<'tcx>,
876 &ProjectedUserTypesNode<'_>,
877 ),
878 ) {
879 // Avoid having to write the full method name at each recursive call.
880 let visit_subpat = |this: &mut Self, subpat, user_tys: &_, f: &mut _| {
881 this.visit_primary_bindings_special(subpat, user_tys, f)
882 };
883
884 match pattern.kind {
885 PatKind::Binding { name, mode, var, ty, ref subpattern, is_primary, .. } => {
886 if is_primary {
887 f(self, name, mode, var, pattern.span, ty, user_tys);
888 }
889 if let Some(subpattern) = subpattern.as_ref() {
890 visit_subpat(self, subpattern, user_tys, f);
891 }
892 }
893
894 PatKind::Array { ref prefix, ref slice, ref suffix }
895 | PatKind::Slice { ref prefix, ref slice, ref suffix } => {
896 let from = u64::try_from(prefix.len()).unwrap();
897 let to = u64::try_from(suffix.len()).unwrap();
898 for subpattern in prefix.iter() {
899 visit_subpat(self, subpattern, &user_tys.index(), f);
900 }
901 if let Some(subpattern) = slice {
902 visit_subpat(self, subpattern, &user_tys.subslice(from, to), f);
903 }
904 for subpattern in suffix.iter() {
905 visit_subpat(self, subpattern, &user_tys.index(), f);
906 }
907 }
908
909 PatKind::Constant { .. }
910 | PatKind::Range { .. }
911 | PatKind::Missing
912 | PatKind::Wild
913 | PatKind::Never
914 | PatKind::Error(_) => {}
915
916 PatKind::Deref { ref subpattern } => {
917 visit_subpat(self, subpattern, &user_tys.deref(), f);
918 }
919
920 PatKind::DerefPattern { ref subpattern, .. } => {
921 visit_subpat(self, subpattern, &ProjectedUserTypesNode::None, f);
922 }
923
924 PatKind::AscribeUserType {
925 ref subpattern,
926 ascription: thir::Ascription { ref annotation, variance: _ },
927 } => {
928 // This corresponds to something like
929 //
930 // ```
931 // let A::<'a>(_): A<'static> = ...;
932 // ```
933 //
934 // Note that the variance doesn't apply here, as we are tracking the effect
935 // of `user_ty` on any bindings contained with subpattern.
936
937 // Caution: Pushing this user type here is load-bearing even for
938 // patterns containing no bindings, to ensure that the type ends
939 // up represented in MIR _somewhere_.
940 let base_user_ty = self.canonical_user_type_annotations.push(annotation.clone());
941 let subpattern_user_tys = user_tys.push_user_type(base_user_ty);
942 visit_subpat(self, subpattern, &subpattern_user_tys, f)
943 }
944
945 PatKind::ExpandedConstant { ref subpattern, .. } => {
946 visit_subpat(self, subpattern, user_tys, f)
947 }
948
949 PatKind::Leaf { ref subpatterns } => {
950 for subpattern in subpatterns {
951 let subpattern_user_tys = user_tys.leaf(subpattern.field);
952 debug!("visit_primary_bindings: subpattern_user_tys={subpattern_user_tys:?}");
953 visit_subpat(self, &subpattern.pattern, &subpattern_user_tys, f);
954 }
955 }
956
957 PatKind::Variant { adt_def, args: _, variant_index, ref subpatterns } => {
958 for subpattern in subpatterns {
959 let subpattern_user_tys =
960 user_tys.variant(adt_def, variant_index, subpattern.field);
961 visit_subpat(self, &subpattern.pattern, &subpattern_user_tys, f);
962 }
963 }
964 PatKind::Or { ref pats } => {
965 // In cases where we recover from errors the primary bindings
966 // may not all be in the leftmost subpattern. For example in
967 // `let (x | y) = ...`, the primary binding of `y` occurs in
968 // the right subpattern
969 for subpattern in pats.iter() {
970 visit_subpat(self, subpattern, user_tys, f);
971 }
972 }
973 }
974 }
975}
976
977/// Data extracted from a pattern that doesn't affect which branch is taken. Collected during
978/// pattern simplification and not mutated later.
979#[derive(Debug, Clone)]
980struct PatternExtraData<'tcx> {
981 /// [`Span`] of the original pattern.
982 span: Span,
983
984 /// Bindings that must be established.
985 bindings: Vec<SubpatternBindings<'tcx>>,
986
987 /// Types that must be asserted.
988 ascriptions: Vec<Ascription<'tcx>>,
989
990 /// Whether this corresponds to a never pattern.
991 is_never: bool,
992}
993
994impl<'tcx> PatternExtraData<'tcx> {
995 fn is_empty(&self) -> bool {
996 self.bindings.is_empty() && self.ascriptions.is_empty()
997 }
998}
999
1000#[derive(Debug, Clone)]
1001enum SubpatternBindings<'tcx> {
1002 /// A single binding.
1003 One(Binding<'tcx>),
1004 /// Holds the place for an or-pattern's bindings. This ensures their drops are scheduled in the
1005 /// order the primary bindings appear. See rust-lang/rust#142163 for more information.
1006 FromOrPattern,
1007}
1008
1009/// A pattern in a form suitable for lowering the match tree, with all irrefutable
1010/// patterns simplified away.
1011///
1012/// Here, "flat" indicates that irrefutable nodes in the pattern tree have been
1013/// recursively replaced with their refutable subpatterns. They are not
1014/// necessarily flat in an absolute sense.
1015///
1016/// Will typically be incorporated into a [`Candidate`].
1017#[derive(Debug, Clone)]
1018struct FlatPat<'tcx> {
1019 /// To match the pattern, all of these must be satisfied...
1020 match_pairs: Vec<MatchPairTree<'tcx>>,
1021
1022 extra_data: PatternExtraData<'tcx>,
1023}
1024
1025impl<'tcx> FlatPat<'tcx> {
1026 /// Creates a `FlatPat` containing a simplified [`MatchPairTree`] list/forest
1027 /// for the given pattern.
1028 fn new(place: PlaceBuilder<'tcx>, pattern: &Pat<'tcx>, cx: &mut Builder<'_, 'tcx>) -> Self {
1029 // Recursively build a tree of match pairs for the given pattern.
1030 let mut match_pairs = vec![];
1031 let mut extra_data = PatternExtraData {
1032 span: pattern.span,
1033 bindings: Vec::new(),
1034 ascriptions: Vec::new(),
1035 is_never: pattern.is_never_pattern(),
1036 };
1037 MatchPairTree::for_pattern(place, pattern, cx, &mut match_pairs, &mut extra_data);
1038
1039 Self { match_pairs, extra_data }
1040 }
1041}
1042
1043/// Candidates are a generalization of (a) top-level match arms, and
1044/// (b) sub-branches of or-patterns, allowing the match-lowering process to handle
1045/// them both in a mostly-uniform way. For example, the list of candidates passed
1046/// to [`Builder::match_candidates`] will often contain a mixture of top-level
1047/// candidates and or-pattern subcandidates.
1048///
1049/// At the start of match lowering, there is one candidate for each match arm.
1050/// During match lowering, arms with or-patterns will be expanded into a tree
1051/// of candidates, where each "leaf" candidate represents one of the ways for
1052/// the arm pattern to successfully match.
1053#[derive(Debug)]
1054struct Candidate<'tcx> {
1055 /// For the candidate to match, all of these must be satisfied...
1056 ///
1057 /// ---
1058 /// Initially contains a list of match pairs created by [`FlatPat`], but is
1059 /// subsequently mutated (in a queue-like way) while lowering the match tree.
1060 /// When this list becomes empty, the candidate is fully matched and becomes
1061 /// a leaf (see [`Builder::select_matched_candidate`]).
1062 ///
1063 /// Key mutations include:
1064 ///
1065 /// - When a match pair is fully satisfied by a test, it is removed from the
1066 /// list, and its subpairs are added instead (see [`Builder::sort_candidate`]).
1067 /// - During or-pattern expansion, any leading or-pattern is removed, and is
1068 /// converted into subcandidates (see [`Builder::expand_and_match_or_candidates`]).
1069 /// - After a candidate's subcandidates have been lowered, a copy of any remaining
1070 /// or-patterns is added to each leaf subcandidate
1071 /// (see [`Builder::test_remaining_match_pairs_after_or`]).
1072 ///
1073 /// Invariants:
1074 /// - All or-patterns ([`TestCase::Or`]) have been sorted to the end.
1075 match_pairs: Vec<MatchPairTree<'tcx>>,
1076
1077 /// ...and if this is non-empty, one of these subcandidates also has to match...
1078 ///
1079 /// ---
1080 /// Initially a candidate has no subcandidates; they are added (and then immediately
1081 /// lowered) during or-pattern expansion. Their main function is to serve as _output_
1082 /// of match tree lowering, allowing later steps to see the leaf candidates that
1083 /// represent a match of the entire match arm.
1084 ///
1085 /// A candidate no subcandidates is either incomplete (if it has match pairs left),
1086 /// or is a leaf in the match tree. A candidate with one or more subcandidates is
1087 /// an internal node in the match tree.
1088 ///
1089 /// Invariant: at the end of match tree lowering, this must not contain an
1090 /// `is_never` candidate, because that would break binding consistency.
1091 /// - See [`Builder::remove_never_subcandidates`].
1092 subcandidates: Vec<Candidate<'tcx>>,
1093
1094 /// ...and if there is a guard it must be evaluated; if it's `false` then branch to `otherwise_block`.
1095 ///
1096 /// ---
1097 /// For subcandidates, this is copied from the parent candidate, so it indicates
1098 /// whether the enclosing match arm has a guard.
1099 has_guard: bool,
1100
1101 /// Holds extra pattern data that was prepared by [`FlatPat`], including bindings and
1102 /// ascriptions that must be established if this candidate succeeds.
1103 extra_data: PatternExtraData<'tcx>,
1104
1105 /// When setting `self.subcandidates`, we store here the span of the or-pattern they came from.
1106 ///
1107 /// ---
1108 /// Invariant: it is `None` iff `subcandidates.is_empty()`.
1109 /// - FIXME: We sometimes don't unset this when clearing `subcandidates`.
1110 or_span: Option<Span>,
1111
1112 /// The block before the `bindings` have been established.
1113 ///
1114 /// After the match tree has been lowered, [`Builder::lower_match_arms`]
1115 /// will use this as the start point for lowering bindings and guards, and
1116 /// then jump to a shared block containing the arm body.
1117 pre_binding_block: Option<BasicBlock>,
1118
1119 /// The block to branch to if the guard or a nested candidate fails to match.
1120 otherwise_block: Option<BasicBlock>,
1121
1122 /// The earliest block that has only candidates >= this one as descendents. Used for false
1123 /// edges, see the doc for [`Builder::match_expr`].
1124 false_edge_start_block: Option<BasicBlock>,
1125}
1126
1127impl<'tcx> Candidate<'tcx> {
1128 fn new(
1129 place: PlaceBuilder<'tcx>,
1130 pattern: &Pat<'tcx>,
1131 has_guard: HasMatchGuard,
1132 cx: &mut Builder<'_, 'tcx>,
1133 ) -> Self {
1134 // Use `FlatPat` to build simplified match pairs, then immediately
1135 // incorporate them into a new candidate.
1136 Self::from_flat_pat(
1137 FlatPat::new(place, pattern, cx),
1138 matches!(has_guard, HasMatchGuard::Yes),
1139 )
1140 }
1141
1142 /// Incorporates an already-simplified [`FlatPat`] into a new candidate.
1143 fn from_flat_pat(flat_pat: FlatPat<'tcx>, has_guard: bool) -> Self {
1144 let mut this = Candidate {
1145 match_pairs: flat_pat.match_pairs,
1146 extra_data: flat_pat.extra_data,
1147 has_guard,
1148 subcandidates: Vec::new(),
1149 or_span: None,
1150 otherwise_block: None,
1151 pre_binding_block: None,
1152 false_edge_start_block: None,
1153 };
1154 this.sort_match_pairs();
1155 this
1156 }
1157
1158 /// Restores the invariant that or-patterns must be sorted to the end.
1159 fn sort_match_pairs(&mut self) {
1160 self.match_pairs.sort_by_key(|pair| matches!(pair.test_case, TestCase::Or { .. }));
1161 }
1162
1163 /// Returns whether the first match pair of this candidate is an or-pattern.
1164 fn starts_with_or_pattern(&self) -> bool {
1165 matches!(&*self.match_pairs, [MatchPairTree { test_case: TestCase::Or { .. }, .. }, ..])
1166 }
1167
1168 /// Visit the leaf candidates (those with no subcandidates) contained in
1169 /// this candidate.
1170 fn visit_leaves<'a>(&'a mut self, mut visit_leaf: impl FnMut(&'a mut Self)) {
1171 traverse_candidate(
1172 self,
1173 &mut (),
1174 &mut move |c, _| visit_leaf(c),
1175 move |c, _| c.subcandidates.iter_mut(),
1176 |_| {},
1177 );
1178 }
1179
1180 /// Visit the leaf candidates in reverse order.
1181 fn visit_leaves_rev<'a>(&'a mut self, mut visit_leaf: impl FnMut(&'a mut Self)) {
1182 traverse_candidate(
1183 self,
1184 &mut (),
1185 &mut move |c, _| visit_leaf(c),
1186 move |c, _| c.subcandidates.iter_mut().rev(),
1187 |_| {},
1188 );
1189 }
1190}
1191
1192/// A depth-first traversal of the `Candidate` and all of its recursive
1193/// subcandidates.
1194///
1195/// This signature is very generic, to support traversing candidate trees by
1196/// reference or by value, and to allow a mutable "context" to be shared by the
1197/// traversal callbacks. Most traversals can use the simpler
1198/// [`Candidate::visit_leaves`] wrapper instead.
1199fn traverse_candidate<'tcx, C, T, I>(
1200 candidate: C,
1201 context: &mut T,
1202 // Called when visiting a "leaf" candidate (with no subcandidates).
1203 visit_leaf: &mut impl FnMut(C, &mut T),
1204 // Called when visiting a "node" candidate (with one or more subcandidates).
1205 // Returns an iterator over the candidate's children (by value or reference).
1206 // Can perform setup before visiting the node's children.
1207 get_children: impl Copy + Fn(C, &mut T) -> I,
1208 // Called after visiting a "node" candidate's children.
1209 complete_children: impl Copy + Fn(&mut T),
1210) where
1211 C: Borrow<Candidate<'tcx>>, // Typically `Candidate` or `&mut Candidate`
1212 I: Iterator<Item = C>,
1213{
1214 if candidate.borrow().subcandidates.is_empty() {
1215 visit_leaf(candidate, context)
1216 } else {
1217 for child in get_children(candidate, context) {
1218 traverse_candidate(child, context, visit_leaf, get_children, complete_children);
1219 }
1220 complete_children(context)
1221 }
1222}
1223
1224#[derive(Clone, Copy, Debug)]
1225struct Binding<'tcx> {
1226 span: Span,
1227 source: Place<'tcx>,
1228 var_id: LocalVarId,
1229 binding_mode: BindingMode,
1230 is_shorthand: bool,
1231}
1232
1233/// Indicates that the type of `source` must be a subtype of the
1234/// user-given type `user_ty`; this is basically a no-op but can
1235/// influence region inference.
1236#[derive(Clone, Debug)]
1237struct Ascription<'tcx> {
1238 source: Place<'tcx>,
1239 annotation: CanonicalUserTypeAnnotation<'tcx>,
1240 variance: ty::Variance,
1241}
1242
1243/// Partial summary of a [`thir::Pat`], indicating what sort of test should be
1244/// performed to match/reject the pattern, and what the desired test outcome is.
1245/// This avoids having to perform a full match on [`thir::PatKind`] in some places,
1246/// and helps [`TestKind::Switch`] and [`TestKind::SwitchInt`] know what target
1247/// values to use.
1248///
1249/// Created by [`MatchPairTree::for_pattern`], and then inspected primarily by:
1250/// - [`Builder::pick_test_for_match_pair`] (to choose a test)
1251/// - [`Builder::sort_candidate`] (to see how the test interacts with a match pair)
1252///
1253/// Note that or-patterns are not tested directly like the other variants.
1254/// Instead they participate in or-pattern expansion, where they are transformed into
1255/// subcandidates. See [`Builder::expand_and_match_or_candidates`].
1256#[derive(Debug, Clone)]
1257enum TestCase<'tcx> {
1258 Variant { adt_def: ty::AdtDef<'tcx>, variant_index: VariantIdx },
1259 Constant { value: ty::Value<'tcx> },
1260 Range(Arc<PatRange<'tcx>>),
1261 Slice { len: usize, variable_length: bool },
1262 Deref { temp: Place<'tcx>, mutability: Mutability },
1263 Never,
1264 Or { pats: Box<[FlatPat<'tcx>]> },
1265}
1266
1267impl<'tcx> TestCase<'tcx> {
1268 fn as_range(&self) -> Option<&PatRange<'tcx>> {
1269 if let Self::Range(v) = self { Some(v.as_ref()) } else { None }
1270 }
1271}
1272
1273/// Node in a tree of "match pairs", where each pair consists of a place to be
1274/// tested, and a test to perform on that place.
1275///
1276/// Each node also has a list of subpairs (possibly empty) that must also match,
1277/// and a reference to the THIR pattern it represents.
1278#[derive(Debug, Clone)]
1279pub(crate) struct MatchPairTree<'tcx> {
1280 /// This place...
1281 ///
1282 /// ---
1283 /// This can be `None` if it referred to a non-captured place in a closure.
1284 ///
1285 /// Invariant: Can only be `None` when `test_case` is `Or`.
1286 /// Therefore this must be `Some(_)` after or-pattern expansion.
1287 place: Option<Place<'tcx>>,
1288
1289 /// ... must pass this test...
1290 test_case: TestCase<'tcx>,
1291
1292 /// ... and these subpairs must match.
1293 ///
1294 /// ---
1295 /// Subpairs typically represent tests that can only be performed after their
1296 /// parent has succeeded. For example, the pattern `Some(3)` might have an
1297 /// outer match pair that tests for the variant `Some`, and then a subpair
1298 /// that tests its field for the value `3`.
1299 subpairs: Vec<Self>,
1300
1301 /// Type field of the pattern this node was created from.
1302 pattern_ty: Ty<'tcx>,
1303 /// Span field of the pattern this node was created from.
1304 pattern_span: Span,
1305}
1306
1307/// See [`Test`] for more.
1308#[derive(Clone, Debug, PartialEq)]
1309enum TestKind<'tcx> {
1310 /// Test what enum variant a value is.
1311 ///
1312 /// The subset of expected variants is not stored here; instead they are
1313 /// extracted from the [`TestCase`]s of the candidates participating in the
1314 /// test.
1315 Switch {
1316 /// The enum type being tested.
1317 adt_def: ty::AdtDef<'tcx>,
1318 },
1319
1320 /// Test what value an integer or `char` has.
1321 ///
1322 /// The test's target values are not stored here; instead they are extracted
1323 /// from the [`TestCase`]s of the candidates participating in the test.
1324 SwitchInt,
1325
1326 /// Test whether a `bool` is `true` or `false`.
1327 If,
1328
1329 /// Test for equality with value, possibly after an unsizing coercion to
1330 /// `cast_ty`,
1331 Eq {
1332 value: ty::Value<'tcx>,
1333 // Integer types are handled by `SwitchInt`, and constants with ADT
1334 // types and `&[T]` types are converted back into patterns, so this can
1335 // only be `&str` or floats.
1336 cast_ty: Ty<'tcx>,
1337 },
1338
1339 /// Test whether the value falls within an inclusive or exclusive range.
1340 Range(Arc<PatRange<'tcx>>),
1341
1342 /// Test that the length of the slice is `== len` or `>= len`.
1343 Len { len: u64, op: BinOp },
1344
1345 /// Call `Deref::deref[_mut]` on the value.
1346 Deref {
1347 /// Temporary to store the result of `deref()`/`deref_mut()`.
1348 temp: Place<'tcx>,
1349 mutability: Mutability,
1350 },
1351
1352 /// Assert unreachability of never patterns.
1353 Never,
1354}
1355
1356/// A test to perform to determine which [`Candidate`] matches a value.
1357///
1358/// [`Test`] is just the test to perform; it does not include the value
1359/// to be tested.
1360#[derive(Debug)]
1361pub(crate) struct Test<'tcx> {
1362 span: Span,
1363 kind: TestKind<'tcx>,
1364}
1365
1366/// The branch to be taken after a test.
1367#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
1368enum TestBranch<'tcx> {
1369 /// Success branch, used for tests with two possible outcomes.
1370 Success,
1371 /// Branch corresponding to this constant. Must be a scalar.
1372 Constant(ty::Value<'tcx>),
1373 /// Branch corresponding to this variant.
1374 Variant(VariantIdx),
1375 /// Failure branch for tests with two possible outcomes, and "otherwise" branch for other tests.
1376 Failure,
1377}
1378
1379impl<'tcx> TestBranch<'tcx> {
1380 fn as_constant(&self) -> Option<ty::Value<'tcx>> {
1381 if let Self::Constant(v) = self { Some(*v) } else { None }
1382 }
1383}
1384
1385/// `ArmHasGuard` is a wrapper around a boolean flag. It indicates whether
1386/// a match arm has a guard expression attached to it.
1387#[derive(Copy, Clone, Debug)]
1388pub(crate) struct ArmHasGuard(pub(crate) bool);
1389
1390///////////////////////////////////////////////////////////////////////////
1391// Main matching algorithm
1392
1393/// A sub-branch in the output of match lowering. Match lowering has generated MIR code that will
1394/// branch to `success_block` when the matched value matches the corresponding pattern. If there is
1395/// a guard, its failure must continue to `otherwise_block`, which will resume testing patterns.
1396#[derive(Debug, Clone)]
1397struct MatchTreeSubBranch<'tcx> {
1398 span: Span,
1399 /// The block that is branched to if the corresponding subpattern matches.
1400 success_block: BasicBlock,
1401 /// The block to branch to if this arm had a guard and the guard fails.
1402 otherwise_block: BasicBlock,
1403 /// The bindings to set up in this sub-branch.
1404 bindings: Vec<Binding<'tcx>>,
1405 /// The ascriptions to set up in this sub-branch.
1406 ascriptions: Vec<Ascription<'tcx>>,
1407 /// Whether the sub-branch corresponds to a never pattern.
1408 is_never: bool,
1409}
1410
1411/// A branch in the output of match lowering.
1412#[derive(Debug, Clone)]
1413struct MatchTreeBranch<'tcx> {
1414 sub_branches: Vec<MatchTreeSubBranch<'tcx>>,
1415}
1416
1417/// The result of generating MIR for a pattern-matching expression. Each input branch/arm/pattern
1418/// gives rise to an output `MatchTreeBranch`. If one of the patterns matches, we branch to the
1419/// corresponding `success_block`. If none of the patterns matches, we branch to `otherwise_block`.
1420///
1421/// Each branch is made of one of more sub-branches, corresponding to or-patterns. E.g.
1422/// ```ignore(illustrative)
1423/// match foo {
1424/// (x, false) | (false, x) => {}
1425/// (true, true) => {}
1426/// }
1427/// ```
1428/// Here the first arm gives the first `MatchTreeBranch`, which has two sub-branches, one for each
1429/// alternative of the or-pattern. They are kept separate because each needs to bind `x` to a
1430/// different place.
1431#[derive(Debug, Clone)]
1432pub(crate) struct BuiltMatchTree<'tcx> {
1433 branches: Vec<MatchTreeBranch<'tcx>>,
1434 otherwise_block: BasicBlock,
1435 /// If any of the branches had a guard, we collect here the places and locals to fakely borrow
1436 /// to ensure match guards can't modify the values as we match them. For more details, see
1437 /// [`util::collect_fake_borrows`].
1438 fake_borrow_temps: Vec<(Place<'tcx>, Local, FakeBorrowKind)>,
1439}
1440
1441impl<'tcx> MatchTreeSubBranch<'tcx> {
1442 fn from_sub_candidate(
1443 candidate: Candidate<'tcx>,
1444 parent_data: &Vec<PatternExtraData<'tcx>>,
1445 ) -> Self {
1446 debug_assert!(candidate.match_pairs.is_empty());
1447 MatchTreeSubBranch {
1448 span: candidate.extra_data.span,
1449 success_block: candidate.pre_binding_block.unwrap(),
1450 otherwise_block: candidate.otherwise_block.unwrap(),
1451 bindings: sub_branch_bindings(parent_data, &candidate.extra_data.bindings),
1452 ascriptions: parent_data
1453 .iter()
1454 .flat_map(|d| &d.ascriptions)
1455 .cloned()
1456 .chain(candidate.extra_data.ascriptions)
1457 .collect(),
1458 is_never: candidate.extra_data.is_never,
1459 }
1460 }
1461}
1462
1463impl<'tcx> MatchTreeBranch<'tcx> {
1464 fn from_candidate(candidate: Candidate<'tcx>) -> Self {
1465 let mut sub_branches = Vec::new();
1466 traverse_candidate(
1467 candidate,
1468 &mut Vec::new(),
1469 &mut |candidate: Candidate<'_>, parent_data: &mut Vec<PatternExtraData<'_>>| {
1470 sub_branches.push(MatchTreeSubBranch::from_sub_candidate(candidate, parent_data));
1471 },
1472 |inner_candidate, parent_data| {
1473 parent_data.push(inner_candidate.extra_data);
1474 inner_candidate.subcandidates.into_iter()
1475 },
1476 |parent_data| {
1477 parent_data.pop();
1478 },
1479 );
1480 MatchTreeBranch { sub_branches }
1481 }
1482}
1483
1484/// Collects the bindings for a [`MatchTreeSubBranch`], preserving the order they appear in the
1485/// pattern, as though the or-alternatives chosen in this sub-branch were inlined.
1486fn sub_branch_bindings<'tcx>(
1487 parents: &[PatternExtraData<'tcx>],
1488 leaf_bindings: &[SubpatternBindings<'tcx>],
1489) -> Vec<Binding<'tcx>> {
1490 // In the common case, all bindings will be in leaves. Allocate to fit the leaf's bindings.
1491 let mut all_bindings = Vec::with_capacity(leaf_bindings.len());
1492 let mut remainder = parents
1493 .iter()
1494 .map(|parent| parent.bindings.as_slice())
1495 .chain([leaf_bindings])
1496 // Skip over unsimplified or-patterns without bindings.
1497 .filter(|bindings| !bindings.is_empty());
1498 if let Some(candidate_bindings) = remainder.next() {
1499 push_sub_branch_bindings(&mut all_bindings, candidate_bindings, &mut remainder);
1500 }
1501 // Make sure we've included all bindings. For ill-formed patterns like `(x, _ | y)`, we may not
1502 // have collected all bindings yet, since we only check the first alternative when determining
1503 // whether to inline subcandidates' bindings.
1504 // FIXME(@dianne): prevent ill-formed patterns from getting here
1505 while let Some(candidate_bindings) = remainder.next() {
1506 ty::tls::with(|tcx| {
1507 tcx.dcx().delayed_bug("mismatched or-pattern bindings but no error emitted")
1508 });
1509 // To recover, we collect the rest in an arbitrary order.
1510 push_sub_branch_bindings(&mut all_bindings, candidate_bindings, &mut remainder);
1511 }
1512 all_bindings
1513}
1514
1515/// Helper for [`sub_branch_bindings`]. Collects bindings from `candidate_bindings` into
1516/// `flattened`. Bindings in or-patterns are collected recursively from `remainder`.
1517fn push_sub_branch_bindings<'c, 'tcx: 'c>(
1518 flattened: &mut Vec<Binding<'tcx>>,
1519 candidate_bindings: &'c [SubpatternBindings<'tcx>],
1520 remainder: &mut impl Iterator<Item = &'c [SubpatternBindings<'tcx>]>,
1521) {
1522 for subpat_bindings in candidate_bindings {
1523 match subpat_bindings {
1524 SubpatternBindings::One(binding) => flattened.push(*binding),
1525 SubpatternBindings::FromOrPattern => {
1526 // Inline bindings from an or-pattern. By construction, this always
1527 // corresponds to a subcandidate and its closest descendants (i.e. those
1528 // from nested or-patterns, but not adjacent or-patterns). To handle
1529 // adjacent or-patterns, e.g. `(x | x, y | y)`, we update the `remainder` to
1530 // point to the first descendant candidate from outside this or-pattern.
1531 if let Some(subcandidate_bindings) = remainder.next() {
1532 push_sub_branch_bindings(flattened, subcandidate_bindings, remainder);
1533 } else {
1534 // For ill-formed patterns like `x | _`, we may not have any subcandidates left
1535 // to inline bindings from.
1536 // FIXME(@dianne): prevent ill-formed patterns from getting here
1537 ty::tls::with(|tcx| {
1538 tcx.dcx().delayed_bug("mismatched or-pattern bindings but no error emitted")
1539 });
1540 };
1541 }
1542 }
1543 }
1544}
1545
1546#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1547pub(crate) enum HasMatchGuard {
1548 Yes,
1549 No,
1550}
1551
1552impl<'a, 'tcx> Builder<'a, 'tcx> {
1553 /// The entrypoint of the matching algorithm. Create the decision tree for the match expression,
1554 /// starting from `block`.
1555 ///
1556 /// `patterns` is a list of patterns, one for each arm. The associated boolean indicates whether
1557 /// the arm has a guard.
1558 ///
1559 /// `refutable` indicates whether the candidate list is refutable (for `if let` and `let else`)
1560 /// or not (for `let` and `match`). In the refutable case we return the block to which we branch
1561 /// on failure.
1562 pub(crate) fn lower_match_tree(
1563 &mut self,
1564 block: BasicBlock,
1565 scrutinee_span: Span,
1566 scrutinee_place_builder: &PlaceBuilder<'tcx>,
1567 match_start_span: Span,
1568 patterns: Vec<(&Pat<'tcx>, HasMatchGuard)>,
1569 refutable: bool,
1570 ) -> BuiltMatchTree<'tcx> {
1571 // Assemble the initial list of candidates. These top-level candidates are 1:1 with the
1572 // input patterns, but other parts of match lowering also introduce subcandidates (for
1573 // sub-or-patterns). So inside the algorithm, the candidates list may not correspond to
1574 // match arms directly.
1575 let mut candidates: Vec<Candidate<'_>> = patterns
1576 .into_iter()
1577 .map(|(pat, has_guard)| {
1578 Candidate::new(scrutinee_place_builder.clone(), pat, has_guard, self)
1579 })
1580 .collect();
1581
1582 let fake_borrow_temps = util::collect_fake_borrows(
1583 self,
1584 &candidates,
1585 scrutinee_span,
1586 scrutinee_place_builder.base(),
1587 );
1588
1589 // This will generate code to test scrutinee_place and branch to the appropriate arm block.
1590 // If none of the arms match, we branch to `otherwise_block`. When lowering a `match`
1591 // expression, exhaustiveness checking ensures that this block is unreachable.
1592 let mut candidate_refs = candidates.iter_mut().collect::<Vec<_>>();
1593 let otherwise_block =
1594 self.match_candidates(match_start_span, scrutinee_span, block, &mut candidate_refs);
1595
1596 // Set up false edges so that the borrow-checker cannot make use of the specific CFG we
1597 // generated. We falsely branch from each candidate to the one below it to make it as if we
1598 // were testing match branches one by one in order. In the refutable case we also want a
1599 // false edge to the final failure block.
1600 let mut next_candidate_start_block = if refutable { Some(otherwise_block) } else { None };
1601 for candidate in candidates.iter_mut().rev() {
1602 let has_guard = candidate.has_guard;
1603 candidate.visit_leaves_rev(|leaf_candidate| {
1604 if let Some(next_candidate_start_block) = next_candidate_start_block {
1605 let source_info = self.source_info(leaf_candidate.extra_data.span);
1606 // Falsely branch to `next_candidate_start_block` before reaching pre_binding.
1607 let old_pre_binding = leaf_candidate.pre_binding_block.unwrap();
1608 let new_pre_binding = self.cfg.start_new_block();
1609 self.false_edges(
1610 old_pre_binding,
1611 new_pre_binding,
1612 next_candidate_start_block,
1613 source_info,
1614 );
1615 leaf_candidate.pre_binding_block = Some(new_pre_binding);
1616 if has_guard {
1617 // Falsely branch to `next_candidate_start_block` also if the guard fails.
1618 let new_otherwise = self.cfg.start_new_block();
1619 let old_otherwise = leaf_candidate.otherwise_block.unwrap();
1620 self.false_edges(
1621 new_otherwise,
1622 old_otherwise,
1623 next_candidate_start_block,
1624 source_info,
1625 );
1626 leaf_candidate.otherwise_block = Some(new_otherwise);
1627 }
1628 }
1629 assert!(leaf_candidate.false_edge_start_block.is_some());
1630 next_candidate_start_block = leaf_candidate.false_edge_start_block;
1631 });
1632 }
1633
1634 if !refutable {
1635 // Match checking ensures `otherwise_block` is actually unreachable in irrefutable
1636 // cases.
1637 let source_info = self.source_info(scrutinee_span);
1638
1639 // Matching on a scrutinee place of an uninhabited type doesn't generate any memory
1640 // reads by itself, and so if the place is uninitialized we wouldn't know. In order to
1641 // disallow the following:
1642 // ```rust
1643 // let x: !;
1644 // match x {}
1645 // ```
1646 // we add a dummy read on the place.
1647 //
1648 // NOTE: If we require never patterns for empty matches, those will check that the place
1649 // is initialized, and so this read would no longer be needed.
1650 let cause_matched_place = FakeReadCause::ForMatchedPlace(None);
1651
1652 if let Some(scrutinee_place) = scrutinee_place_builder.try_to_place(self) {
1653 self.cfg.push_fake_read(
1654 otherwise_block,
1655 source_info,
1656 cause_matched_place,
1657 scrutinee_place,
1658 );
1659 }
1660
1661 self.cfg.terminate(otherwise_block, source_info, TerminatorKind::Unreachable);
1662 }
1663
1664 BuiltMatchTree {
1665 branches: candidates.into_iter().map(MatchTreeBranch::from_candidate).collect(),
1666 otherwise_block,
1667 fake_borrow_temps,
1668 }
1669 }
1670
1671 /// The main match algorithm. It begins with a set of candidates `candidates` and has the job of
1672 /// generating code that branches to an appropriate block if the scrutinee matches one of these
1673 /// candidates. The
1674 /// candidates are ordered such that the first item in the list
1675 /// has the highest priority. When a candidate is found to match
1676 /// the value, we will set and generate a branch to the appropriate
1677 /// pre-binding block.
1678 ///
1679 /// If none of the candidates apply, we continue to the returned `otherwise_block`.
1680 ///
1681 /// Note that while `match` expressions in the Rust language are exhaustive,
1682 /// candidate lists passed to this method are often _non-exhaustive_.
1683 /// For example, the match lowering process will frequently divide up the
1684 /// list of candidates, and recursively call this method with a non-exhaustive
1685 /// subset of candidates.
1686 /// See [`Builder::test_candidates`] for more details on this
1687 /// "backtracking automata" approach.
1688 ///
1689 /// For an example of how we use `otherwise_block`, consider:
1690 /// ```
1691 /// # fn foo((x, y): (bool, bool)) -> u32 {
1692 /// match (x, y) {
1693 /// (true, true) => 1,
1694 /// (_, false) => 2,
1695 /// (false, true) => 3,
1696 /// }
1697 /// # }
1698 /// ```
1699 /// For this match, we generate something like:
1700 /// ```
1701 /// # fn foo((x, y): (bool, bool)) -> u32 {
1702 /// if x {
1703 /// if y {
1704 /// return 1
1705 /// } else {
1706 /// // continue
1707 /// }
1708 /// } else {
1709 /// // continue
1710 /// }
1711 /// if y {
1712 /// if x {
1713 /// // This is actually unreachable because the `(true, true)` case was handled above,
1714 /// // but we don't know that from within the lowering algorithm.
1715 /// // continue
1716 /// } else {
1717 /// return 3
1718 /// }
1719 /// } else {
1720 /// return 2
1721 /// }
1722 /// // this is the final `otherwise_block`, which is unreachable because the match was exhaustive.
1723 /// unreachable!()
1724 /// # }
1725 /// ```
1726 ///
1727 /// Every `continue` is an instance of branching to some `otherwise_block` somewhere deep within
1728 /// the algorithm. For more details on why we lower like this, see [`Builder::test_candidates`].
1729 ///
1730 /// Note how we test `x` twice. This is the tradeoff of backtracking automata: we prefer smaller
1731 /// code size so we accept non-optimal code paths.
1732 #[instrument(skip(self), level = "debug")]
1733 fn match_candidates(
1734 &mut self,
1735 span: Span,
1736 scrutinee_span: Span,
1737 start_block: BasicBlock,
1738 candidates: &mut [&mut Candidate<'tcx>],
1739 ) -> BasicBlock {
1740 ensure_sufficient_stack(|| {
1741 self.match_candidates_inner(span, scrutinee_span, start_block, candidates)
1742 })
1743 }
1744
1745 /// Construct the decision tree for `candidates`. Don't call this, call `match_candidates`
1746 /// instead to reserve sufficient stack space.
1747 fn match_candidates_inner(
1748 &mut self,
1749 span: Span,
1750 scrutinee_span: Span,
1751 mut start_block: BasicBlock,
1752 candidates: &mut [&mut Candidate<'tcx>],
1753 ) -> BasicBlock {
1754 if let [first, ..] = candidates {
1755 if first.false_edge_start_block.is_none() {
1756 first.false_edge_start_block = Some(start_block);
1757 }
1758 }
1759
1760 // Process a prefix of the candidates.
1761 let rest = match candidates {
1762 [] => {
1763 // If there are no candidates that still need testing, we're done.
1764 return start_block;
1765 }
1766 [first, remaining @ ..] if first.match_pairs.is_empty() => {
1767 // The first candidate has satisfied all its match pairs.
1768 // We record the blocks that will be needed by match arm lowering,
1769 // and then continue with the remaining candidates.
1770 let remainder_start = self.select_matched_candidate(first, start_block);
1771 remainder_start.and(remaining)
1772 }
1773 candidates if candidates.iter().any(|candidate| candidate.starts_with_or_pattern()) => {
1774 // If any candidate starts with an or-pattern, we want to expand or-patterns
1775 // before we do any more tests.
1776 //
1777 // The only candidate we strictly _need_ to expand here is the first one.
1778 // But by expanding other candidates as early as possible, we unlock more
1779 // opportunities to include them in test outcomes, making the match tree
1780 // smaller and simpler.
1781 self.expand_and_match_or_candidates(span, scrutinee_span, start_block, candidates)
1782 }
1783 candidates => {
1784 // The first candidate has some unsatisfied match pairs; we proceed to do more tests.
1785 self.test_candidates(span, scrutinee_span, candidates, start_block)
1786 }
1787 };
1788
1789 // Process any candidates that remain.
1790 let remaining_candidates = unpack!(start_block = rest);
1791 self.match_candidates(span, scrutinee_span, start_block, remaining_candidates)
1792 }
1793
1794 /// Link up matched candidates.
1795 ///
1796 /// For example, if we have something like this:
1797 ///
1798 /// ```ignore (illustrative)
1799 /// ...
1800 /// Some(x) if cond1 => ...
1801 /// Some(x) => ...
1802 /// Some(x) if cond2 => ...
1803 /// ...
1804 /// ```
1805 ///
1806 /// We generate real edges from:
1807 ///
1808 /// * `start_block` to the [pre-binding block] of the first pattern,
1809 /// * the [otherwise block] of the first pattern to the second pattern,
1810 /// * the [otherwise block] of the third pattern to a block with an
1811 /// [`Unreachable` terminator](TerminatorKind::Unreachable).
1812 ///
1813 /// In addition, we later add fake edges from the otherwise blocks to the
1814 /// pre-binding block of the next candidate in the original set of
1815 /// candidates.
1816 ///
1817 /// [pre-binding block]: Candidate::pre_binding_block
1818 /// [otherwise block]: Candidate::otherwise_block
1819 fn select_matched_candidate(
1820 &mut self,
1821 candidate: &mut Candidate<'tcx>,
1822 start_block: BasicBlock,
1823 ) -> BasicBlock {
1824 assert!(candidate.otherwise_block.is_none());
1825 assert!(candidate.pre_binding_block.is_none());
1826 assert!(candidate.subcandidates.is_empty());
1827
1828 candidate.pre_binding_block = Some(start_block);
1829 let otherwise_block = self.cfg.start_new_block();
1830 // Create the otherwise block for this candidate, which is the
1831 // pre-binding block for the next candidate.
1832 candidate.otherwise_block = Some(otherwise_block);
1833 otherwise_block
1834 }
1835
1836 /// Takes a list of candidates such that some of the candidates' first match pairs are
1837 /// or-patterns. This expands as many or-patterns as possible and processes the resulting
1838 /// candidates. Returns the unprocessed candidates if any.
1839 fn expand_and_match_or_candidates<'b, 'c>(
1840 &mut self,
1841 span: Span,
1842 scrutinee_span: Span,
1843 start_block: BasicBlock,
1844 candidates: &'b mut [&'c mut Candidate<'tcx>],
1845 ) -> BlockAnd<&'b mut [&'c mut Candidate<'tcx>]> {
1846 // We can't expand or-patterns freely. The rule is:
1847 // - If a candidate doesn't start with an or-pattern, we include it in
1848 // the expansion list as-is (i.e. it "expands" to itself).
1849 // - If a candidate has an or-pattern as its only remaining match pair,
1850 // we can expand it.
1851 // - If it starts with an or-pattern but also has other match pairs,
1852 // we can expand it, but we can't process more candidates after it.
1853 //
1854 // If we didn't stop, the `otherwise` cases could get mixed up. E.g. in the
1855 // following, or-pattern simplification (in `merge_trivial_subcandidates`) makes it
1856 // so the `1` and `2` cases branch to a same block (which then tests `false`). If we
1857 // took `(2, _)` in the same set of candidates, when we reach the block that tests
1858 // `false` we don't know whether we came from `1` or `2`, hence we can't know where
1859 // to branch on failure.
1860 //
1861 // ```ignore(illustrative)
1862 // match (1, true) {
1863 // (1 | 2, false) => {},
1864 // (2, _) => {},
1865 // _ => {}
1866 // }
1867 // ```
1868 //
1869 // We therefore split the `candidates` slice in two, expand or-patterns in the first part,
1870 // and process the rest separately.
1871 let expand_until = candidates
1872 .iter()
1873 .position(|candidate| {
1874 // If a candidate starts with an or-pattern and has more match pairs,
1875 // we can expand it, but we must stop expanding _after_ it.
1876 candidate.match_pairs.len() > 1 && candidate.starts_with_or_pattern()
1877 })
1878 .map(|pos| pos + 1) // Stop _after_ the found candidate
1879 .unwrap_or(candidates.len()); // Otherwise, include all candidates
1880 let (candidates_to_expand, remaining_candidates) = candidates.split_at_mut(expand_until);
1881
1882 // Expand one level of or-patterns for each candidate in `candidates_to_expand`.
1883 // We take care to preserve the relative ordering of candidates, so that
1884 // or-patterns are expanded in their parent's relative position.
1885 let mut expanded_candidates = Vec::new();
1886 for candidate in candidates_to_expand.iter_mut() {
1887 if candidate.starts_with_or_pattern() {
1888 let or_match_pair = candidate.match_pairs.remove(0);
1889 // Expand the or-pattern into subcandidates.
1890 self.create_or_subcandidates(candidate, or_match_pair);
1891 // Collect the newly created subcandidates.
1892 for subcandidate in candidate.subcandidates.iter_mut() {
1893 expanded_candidates.push(subcandidate);
1894 }
1895 // Note that the subcandidates have been added to `expanded_candidates`,
1896 // but `candidate` itself has not. If the last candidate has more match pairs,
1897 // they are handled separately by `test_remaining_match_pairs_after_or`.
1898 } else {
1899 // A candidate that doesn't start with an or-pattern has nothing to
1900 // expand, so it is included in the post-expansion list as-is.
1901 expanded_candidates.push(candidate);
1902 }
1903 }
1904
1905 // Recursively lower the part of the match tree represented by the
1906 // expanded candidates. This is where subcandidates actually get lowered!
1907 let remainder_start = self.match_candidates(
1908 span,
1909 scrutinee_span,
1910 start_block,
1911 expanded_candidates.as_mut_slice(),
1912 );
1913
1914 // Postprocess subcandidates, and process any leftover match pairs.
1915 // (Only the last candidate can possibly have more match pairs.)
1916 debug_assert!({
1917 let mut all_except_last = candidates_to_expand.iter().rev().skip(1);
1918 all_except_last.all(|candidate| candidate.match_pairs.is_empty())
1919 });
1920 for candidate in candidates_to_expand.iter_mut() {
1921 if !candidate.subcandidates.is_empty() {
1922 self.merge_trivial_subcandidates(candidate);
1923 self.remove_never_subcandidates(candidate);
1924 }
1925 }
1926 // It's important to perform the above simplifications _before_ dealing
1927 // with remaining match pairs, to avoid exponential blowup if possible
1928 // (for trivial or-patterns), and avoid useless work (for never patterns).
1929 if let Some(last_candidate) = candidates_to_expand.last_mut() {
1930 self.test_remaining_match_pairs_after_or(span, scrutinee_span, last_candidate);
1931 }
1932
1933 remainder_start.and(remaining_candidates)
1934 }
1935
1936 /// Given a match-pair that corresponds to an or-pattern, expand each subpattern into a new
1937 /// subcandidate. Any candidate that has been expanded this way should also be postprocessed
1938 /// at the end of [`Self::expand_and_match_or_candidates`].
1939 fn create_or_subcandidates(
1940 &mut self,
1941 candidate: &mut Candidate<'tcx>,
1942 match_pair: MatchPairTree<'tcx>,
1943 ) {
1944 let TestCase::Or { pats } = match_pair.test_case else { bug!() };
1945 debug!("expanding or-pattern: candidate={:#?}\npats={:#?}", candidate, pats);
1946 candidate.or_span = Some(match_pair.pattern_span);
1947 candidate.subcandidates = pats
1948 .into_iter()
1949 .map(|flat_pat| Candidate::from_flat_pat(flat_pat, candidate.has_guard))
1950 .collect();
1951 candidate.subcandidates[0].false_edge_start_block = candidate.false_edge_start_block;
1952 }
1953
1954 /// Try to merge all of the subcandidates of the given candidate into one. This avoids
1955 /// exponentially large CFGs in cases like `(1 | 2, 3 | 4, ...)`. The candidate should have been
1956 /// expanded with `create_or_subcandidates`.
1957 ///
1958 /// Given a pattern `(P | Q, R | S)` we (in principle) generate a CFG like
1959 /// so:
1960 ///
1961 /// ```text
1962 /// [ start ]
1963 /// |
1964 /// [ match P, Q ]
1965 /// |
1966 /// +----------------------------------------+------------------------------------+
1967 /// | | |
1968 /// V V V
1969 /// [ P matches ] [ Q matches ] [ otherwise ]
1970 /// | | |
1971 /// V V |
1972 /// [ match R, S ] [ match R, S ] |
1973 /// | | |
1974 /// +--------------+------------+ +--------------+------------+ |
1975 /// | | | | | | |
1976 /// V V V V V V |
1977 /// [ R matches ] [ S matches ] [otherwise ] [ R matches ] [ S matches ] [otherwise ] |
1978 /// | | | | | | |
1979 /// +--------------+------------|------------+--------------+ | |
1980 /// | | | |
1981 /// | +----------------------------------------+--------+
1982 /// | |
1983 /// V V
1984 /// [ Success ] [ Failure ]
1985 /// ```
1986 ///
1987 /// In practice there are some complications:
1988 ///
1989 /// * If there's a guard, then the otherwise branch of the first match on
1990 /// `R | S` goes to a test for whether `Q` matches, and the control flow
1991 /// doesn't merge into a single success block until after the guard is
1992 /// tested.
1993 /// * If neither `P` or `Q` has any bindings or type ascriptions and there
1994 /// isn't a match guard, then we create a smaller CFG like:
1995 ///
1996 /// ```text
1997 /// ...
1998 /// +---------------+------------+
1999 /// | | |
2000 /// [ P matches ] [ Q matches ] [ otherwise ]
2001 /// | | |
2002 /// +---------------+ |
2003 /// | ...
2004 /// [ match R, S ]
2005 /// |
2006 /// ...
2007 /// ```
2008 ///
2009 /// Note that this takes place _after_ the subcandidates have participated
2010 /// in match tree lowering.
2011 fn merge_trivial_subcandidates(&mut self, candidate: &mut Candidate<'tcx>) {
2012 assert!(!candidate.subcandidates.is_empty());
2013 if candidate.has_guard {
2014 // FIXME(or_patterns; matthewjasper) Don't give up if we have a guard.
2015 return;
2016 }
2017
2018 // FIXME(or_patterns; matthewjasper) Try to be more aggressive here.
2019 let can_merge = candidate.subcandidates.iter().all(|subcandidate| {
2020 subcandidate.subcandidates.is_empty() && subcandidate.extra_data.is_empty()
2021 });
2022 if !can_merge {
2023 return;
2024 }
2025
2026 let mut last_otherwise = None;
2027 let shared_pre_binding_block = self.cfg.start_new_block();
2028 // This candidate is about to become a leaf, so unset `or_span`.
2029 let or_span = candidate.or_span.take().unwrap();
2030 let source_info = self.source_info(or_span);
2031
2032 if candidate.false_edge_start_block.is_none() {
2033 candidate.false_edge_start_block = candidate.subcandidates[0].false_edge_start_block;
2034 }
2035
2036 // Remove the (known-trivial) subcandidates from the candidate tree,
2037 // so that they aren't visible after match tree lowering, and wire them
2038 // all to join up at a single shared pre-binding block.
2039 // (Note that the subcandidates have already had their part of the match
2040 // tree lowered by this point, which is why we can add a goto to them.)
2041 for subcandidate in mem::take(&mut candidate.subcandidates) {
2042 let subcandidate_block = subcandidate.pre_binding_block.unwrap();
2043 self.cfg.goto(subcandidate_block, source_info, shared_pre_binding_block);
2044 last_otherwise = subcandidate.otherwise_block;
2045 }
2046 candidate.pre_binding_block = Some(shared_pre_binding_block);
2047 assert!(last_otherwise.is_some());
2048 candidate.otherwise_block = last_otherwise;
2049 }
2050
2051 /// Never subcandidates may have a set of bindings inconsistent with their siblings,
2052 /// which would break later code. So we filter them out. Note that we can't filter out
2053 /// top-level candidates this way.
2054 fn remove_never_subcandidates(&mut self, candidate: &mut Candidate<'tcx>) {
2055 if candidate.subcandidates.is_empty() {
2056 return;
2057 }
2058
2059 let false_edge_start_block = candidate.subcandidates[0].false_edge_start_block;
2060 candidate.subcandidates.retain_mut(|candidate| {
2061 if candidate.extra_data.is_never {
2062 candidate.visit_leaves(|subcandidate| {
2063 let block = subcandidate.pre_binding_block.unwrap();
2064 // That block is already unreachable but needs a terminator to make the MIR well-formed.
2065 let source_info = self.source_info(subcandidate.extra_data.span);
2066 self.cfg.terminate(block, source_info, TerminatorKind::Unreachable);
2067 });
2068 false
2069 } else {
2070 true
2071 }
2072 });
2073 if candidate.subcandidates.is_empty() {
2074 // If `candidate` has become a leaf candidate, ensure it has a `pre_binding_block` and `otherwise_block`.
2075 let next_block = self.cfg.start_new_block();
2076 candidate.pre_binding_block = Some(next_block);
2077 candidate.otherwise_block = Some(next_block);
2078 // In addition, if `candidate` doesn't have `false_edge_start_block`, it should be assigned here.
2079 if candidate.false_edge_start_block.is_none() {
2080 candidate.false_edge_start_block = false_edge_start_block;
2081 }
2082 }
2083 }
2084
2085 /// If more match pairs remain, test them after each subcandidate.
2086 /// We could have added them to the or-candidates during or-pattern expansion, but that
2087 /// would make it impossible to detect simplifiable or-patterns. That would guarantee
2088 /// exponentially large CFGs for cases like `(1 | 2, 3 | 4, ...)`.
2089 fn test_remaining_match_pairs_after_or(
2090 &mut self,
2091 span: Span,
2092 scrutinee_span: Span,
2093 candidate: &mut Candidate<'tcx>,
2094 ) {
2095 if candidate.match_pairs.is_empty() {
2096 return;
2097 }
2098
2099 let or_span = candidate.or_span.unwrap_or(candidate.extra_data.span);
2100 let source_info = self.source_info(or_span);
2101 let mut last_otherwise = None;
2102 candidate.visit_leaves(|leaf_candidate| {
2103 last_otherwise = leaf_candidate.otherwise_block;
2104 });
2105
2106 let remaining_match_pairs = mem::take(&mut candidate.match_pairs);
2107 // We're testing match pairs that remained after an `Or`, so the remaining
2108 // pairs should all be `Or` too, due to the sorting invariant.
2109 debug_assert!(
2110 remaining_match_pairs
2111 .iter()
2112 .all(|match_pair| matches!(match_pair.test_case, TestCase::Or { .. }))
2113 );
2114
2115 // Visit each leaf candidate within this subtree, add a copy of the remaining
2116 // match pairs to it, and then recursively lower the rest of the match tree
2117 // from that point.
2118 candidate.visit_leaves(|leaf_candidate| {
2119 // At this point the leaf's own match pairs have all been lowered
2120 // and removed, so `extend` and assignment are equivalent,
2121 // but extending can also recycle any existing vector capacity.
2122 assert!(leaf_candidate.match_pairs.is_empty());
2123 leaf_candidate.match_pairs.extend(remaining_match_pairs.iter().cloned());
2124
2125 let or_start = leaf_candidate.pre_binding_block.unwrap();
2126 let otherwise =
2127 self.match_candidates(span, scrutinee_span, or_start, &mut [leaf_candidate]);
2128 // In a case like `(P | Q, R | S)`, if `P` succeeds and `R | S` fails, we know `(Q,
2129 // R | S)` will fail too. If there is no guard, we skip testing of `Q` by branching
2130 // directly to `last_otherwise`. If there is a guard,
2131 // `leaf_candidate.otherwise_block` can be reached by guard failure as well, so we
2132 // can't skip `Q`.
2133 let or_otherwise = if leaf_candidate.has_guard {
2134 leaf_candidate.otherwise_block.unwrap()
2135 } else {
2136 last_otherwise.unwrap()
2137 };
2138 self.cfg.goto(otherwise, source_info, or_otherwise);
2139 });
2140 }
2141
2142 /// Pick a test to run. Which test doesn't matter as long as it is guaranteed to fully match at
2143 /// least one match pair. We currently simply pick the test corresponding to the first match
2144 /// pair of the first candidate in the list.
2145 ///
2146 /// *Note:* taking the first match pair is somewhat arbitrary, and we might do better here by
2147 /// choosing more carefully what to test.
2148 ///
2149 /// For example, consider the following possible match-pairs:
2150 ///
2151 /// 1. `x @ Some(P)` -- we will do a [`Switch`] to decide what variant `x` has
2152 /// 2. `x @ 22` -- we will do a [`SwitchInt`] to decide what value `x` has
2153 /// 3. `x @ 3..5` -- we will do a [`Range`] test to decide what range `x` falls in
2154 /// 4. etc.
2155 ///
2156 /// [`Switch`]: TestKind::Switch
2157 /// [`SwitchInt`]: TestKind::SwitchInt
2158 /// [`Range`]: TestKind::Range
2159 fn pick_test(&mut self, candidates: &[&mut Candidate<'tcx>]) -> (Place<'tcx>, Test<'tcx>) {
2160 // Extract the match-pair from the highest priority candidate
2161 let match_pair = &candidates[0].match_pairs[0];
2162 let test = self.pick_test_for_match_pair(match_pair);
2163 // Unwrap is ok after simplification.
2164 let match_place = match_pair.place.unwrap();
2165 debug!(?test, ?match_pair);
2166
2167 (match_place, test)
2168 }
2169
2170 /// Given a test, we partition the input candidates into several buckets.
2171 /// If a candidate matches in exactly one of the branches of `test`
2172 /// (and no other branches), we put it into the corresponding bucket.
2173 /// If it could match in more than one of the branches of `test`, the test
2174 /// doesn't usefully apply to it, and we stop partitioning candidates.
2175 ///
2176 /// Importantly, we also **mutate** the branched candidates to remove match pairs
2177 /// that are entailed by the outcome of the test, and add any sub-pairs of the
2178 /// removed pairs.
2179 ///
2180 /// This returns a pair of
2181 /// - the candidates that weren't sorted;
2182 /// - for each possible outcome of the test, the candidates that match in that outcome.
2183 ///
2184 /// For example:
2185 /// ```
2186 /// # let (x, y, z) = (true, true, true);
2187 /// match (x, y, z) {
2188 /// (true , _ , true ) => true, // (0)
2189 /// (false, false, _ ) => false, // (1)
2190 /// (_ , true , _ ) => true, // (2)
2191 /// (true , _ , false) => false, // (3)
2192 /// }
2193 /// # ;
2194 /// ```
2195 ///
2196 /// Assume we are testing on `x`. Conceptually, there are 2 overlapping candidate sets:
2197 /// - If the outcome is that `x` is true, candidates {0, 2, 3} are possible
2198 /// - If the outcome is that `x` is false, candidates {1, 2} are possible
2199 ///
2200 /// Following our algorithm:
2201 /// - Candidate 0 is sorted into outcome `x == true`
2202 /// - Candidate 1 is sorted into outcome `x == false`
2203 /// - Candidate 2 remains unsorted, because testing `x` has no effect on it
2204 /// - Candidate 3 remains unsorted, because a previous candidate (2) was unsorted
2205 /// - This helps preserve the illusion that candidates are tested "in order"
2206 ///
2207 /// The sorted candidates are mutated to remove entailed match pairs:
2208 /// - candidate 0 becomes `[z @ true]` since we know that `x` was `true`;
2209 /// - candidate 1 becomes `[y @ false]` since we know that `x` was `false`.
2210 fn sort_candidates<'b, 'c>(
2211 &mut self,
2212 match_place: Place<'tcx>,
2213 test: &Test<'tcx>,
2214 mut candidates: &'b mut [&'c mut Candidate<'tcx>],
2215 ) -> (
2216 &'b mut [&'c mut Candidate<'tcx>],
2217 FxIndexMap<TestBranch<'tcx>, Vec<&'b mut Candidate<'tcx>>>,
2218 ) {
2219 // For each of the possible outcomes, collect vector of candidates that apply if the test
2220 // has that particular outcome.
2221 let mut target_candidates: FxIndexMap<_, Vec<&mut Candidate<'_>>> = Default::default();
2222
2223 let total_candidate_count = candidates.len();
2224
2225 // Sort the candidates into the appropriate vector in `target_candidates`. Note that at some
2226 // point we may encounter a candidate where the test is not relevant; at that point, we stop
2227 // sorting.
2228 while let Some(candidate) = candidates.first_mut() {
2229 let Some(branch) =
2230 self.sort_candidate(match_place, test, candidate, &target_candidates)
2231 else {
2232 break;
2233 };
2234 let (candidate, rest) = candidates.split_first_mut().unwrap();
2235 target_candidates.entry(branch).or_insert_with(Vec::new).push(candidate);
2236 candidates = rest;
2237 }
2238
2239 // At least the first candidate ought to be tested
2240 assert!(
2241 total_candidate_count > candidates.len(),
2242 "{total_candidate_count}, {candidates:#?}"
2243 );
2244 debug!("tested_candidates: {}", total_candidate_count - candidates.len());
2245 debug!("untested_candidates: {}", candidates.len());
2246
2247 (candidates, target_candidates)
2248 }
2249
2250 /// This is the most subtle part of the match lowering algorithm. At this point, there are
2251 /// no fully-satisfied candidates, and no or-patterns to expand, so we actually need to
2252 /// perform some sort of test to make progress.
2253 ///
2254 /// Once we pick what sort of test we are going to perform, this test will help us winnow down
2255 /// our candidates. So we walk over the candidates (from high to low priority) and check. We
2256 /// compute, for each outcome of the test, a list of (modified) candidates. If a candidate
2257 /// matches in exactly one branch of our test, we add it to the corresponding outcome. We also
2258 /// **mutate its list of match pairs** if appropriate, to reflect the fact that we know which
2259 /// outcome occurred.
2260 ///
2261 /// For example, if we are testing `x.0`'s variant, and we have a candidate `(x.0 @ Some(v), x.1
2262 /// @ 22)`, then we would have a resulting candidate of `((x.0 as Some).0 @ v, x.1 @ 22)` in the
2263 /// branch corresponding to `Some`. To ensure we make progress, we always pick a test that
2264 /// results in simplifying the first candidate.
2265 ///
2266 /// But there may also be candidates that the test doesn't
2267 /// apply to. The classical example is wildcards:
2268 ///
2269 /// ```
2270 /// # let (x, y, z) = (true, true, true);
2271 /// match (x, y, z) {
2272 /// (true , _ , true ) => true, // (0)
2273 /// (false, false, _ ) => false, // (1)
2274 /// (_ , true , _ ) => true, // (2)
2275 /// (true , _ , false) => false, // (3)
2276 /// }
2277 /// # ;
2278 /// ```
2279 ///
2280 /// Here, the traditional "decision tree" method would generate 2 separate code-paths for the 2
2281 /// possible values of `x`. This would however duplicate some candidates, which would need to be
2282 /// lowered several times.
2283 ///
2284 /// In some cases, this duplication can create an exponential amount of
2285 /// code. This is most easily seen by noticing that this method terminates
2286 /// with precisely the reachable arms being reachable - but that problem
2287 /// is trivially NP-complete:
2288 ///
2289 /// ```ignore (illustrative)
2290 /// match (var0, var1, var2, var3, ...) {
2291 /// (true , _ , _ , false, true, ...) => false,
2292 /// (_ , true, true , false, _ , ...) => false,
2293 /// (false, _ , false, false, _ , ...) => false,
2294 /// ...
2295 /// _ => true
2296 /// }
2297 /// ```
2298 ///
2299 /// Here the last arm is reachable only if there is an assignment to
2300 /// the variables that does not match any of the literals. Therefore,
2301 /// compilation would take an exponential amount of time in some cases.
2302 ///
2303 /// In rustc, we opt instead for the "backtracking automaton" approach. This guarantees we never
2304 /// duplicate a candidate (except in the presence of or-patterns). In fact this guarantee is
2305 /// ensured by the fact that we carry around `&mut Candidate`s which can't be duplicated.
2306 ///
2307 /// To make this work, whenever we decide to perform a test, if we encounter a candidate that
2308 /// could match in more than one branch of the test, we stop. We generate code for the test and
2309 /// for the candidates in its branches; the remaining candidates will be tested if the
2310 /// candidates in the branches fail to match.
2311 ///
2312 /// For example, if we test on `x` in the following:
2313 /// ```
2314 /// # fn foo((x, y, z): (bool, bool, bool)) -> u32 {
2315 /// match (x, y, z) {
2316 /// (true , _ , true ) => 0,
2317 /// (false, false, _ ) => 1,
2318 /// (_ , true , _ ) => 2,
2319 /// (true , _ , false) => 3,
2320 /// }
2321 /// # }
2322 /// ```
2323 /// this function generates code that looks more of less like:
2324 /// ```
2325 /// # fn foo((x, y, z): (bool, bool, bool)) -> u32 {
2326 /// if x {
2327 /// match (y, z) {
2328 /// (_, true) => return 0,
2329 /// _ => {} // continue matching
2330 /// }
2331 /// } else {
2332 /// match (y, z) {
2333 /// (false, _) => return 1,
2334 /// _ => {} // continue matching
2335 /// }
2336 /// }
2337 /// // the block here is `remainder_start`
2338 /// match (x, y, z) {
2339 /// (_ , true , _ ) => 2,
2340 /// (true , _ , false) => 3,
2341 /// _ => unreachable!(),
2342 /// }
2343 /// # }
2344 /// ```
2345 ///
2346 /// We return the unprocessed candidates.
2347 fn test_candidates<'b, 'c>(
2348 &mut self,
2349 span: Span,
2350 scrutinee_span: Span,
2351 candidates: &'b mut [&'c mut Candidate<'tcx>],
2352 start_block: BasicBlock,
2353 ) -> BlockAnd<&'b mut [&'c mut Candidate<'tcx>]> {
2354 // Choose a match pair from the first candidate, and use it to determine a
2355 // test to perform that will confirm or refute that match pair.
2356 let (match_place, test) = self.pick_test(candidates);
2357
2358 // For each of the N possible test outcomes, build the vector of candidates that applies if
2359 // the test has that particular outcome. This also mutates the candidates to remove match
2360 // pairs that are fully satisfied by the relevant outcome.
2361 let (remaining_candidates, target_candidates) =
2362 self.sort_candidates(match_place, &test, candidates);
2363
2364 // The block that we should branch to if none of the `target_candidates` match.
2365 let remainder_start = self.cfg.start_new_block();
2366
2367 // For each outcome of the test, recursively lower the rest of the match tree
2368 // from that point. (Note that we haven't lowered the actual test yet!)
2369 let target_blocks: FxIndexMap<_, _> = target_candidates
2370 .into_iter()
2371 .map(|(branch, mut candidates)| {
2372 let branch_start = self.cfg.start_new_block();
2373 // Recursively lower the rest of the match tree after the relevant outcome.
2374 let branch_otherwise =
2375 self.match_candidates(span, scrutinee_span, branch_start, &mut *candidates);
2376
2377 // Link up the `otherwise` block of the subtree to `remainder_start`.
2378 let source_info = self.source_info(span);
2379 self.cfg.goto(branch_otherwise, source_info, remainder_start);
2380 (branch, branch_start)
2381 })
2382 .collect();
2383
2384 // Perform the chosen test, branching to one of the N subtrees prepared above
2385 // (or to `remainder_start` if no outcome was satisfied).
2386 self.perform_test(
2387 span,
2388 scrutinee_span,
2389 start_block,
2390 remainder_start,
2391 match_place,
2392 &test,
2393 target_blocks,
2394 );
2395
2396 remainder_start.and(remaining_candidates)
2397 }
2398}
2399
2400///////////////////////////////////////////////////////////////////////////
2401// Pat binding - used for `let` and function parameters as well.
2402
2403impl<'a, 'tcx> Builder<'a, 'tcx> {
2404 /// Lowers a `let` expression that appears in a suitable context
2405 /// (e.g. an `if` condition or match guard).
2406 ///
2407 /// Also used for lowering let-else statements, since they have similar
2408 /// needs despite not actually using `let` expressions.
2409 ///
2410 /// Use [`DeclareLetBindings`] to control whether the `let` bindings are
2411 /// declared or not.
2412 pub(crate) fn lower_let_expr(
2413 &mut self,
2414 mut block: BasicBlock,
2415 expr_id: ExprId,
2416 pat: &Pat<'tcx>,
2417 source_scope: Option<SourceScope>,
2418 scope_span: Span,
2419 declare_let_bindings: DeclareLetBindings,
2420 ) -> BlockAnd<()> {
2421 let expr_span = self.thir[expr_id].span;
2422 let scrutinee = unpack!(block = self.lower_scrutinee(block, expr_id, expr_span));
2423 let built_tree = self.lower_match_tree(
2424 block,
2425 expr_span,
2426 &scrutinee,
2427 pat.span,
2428 vec![(pat, HasMatchGuard::No)],
2429 true,
2430 );
2431 let [branch] = built_tree.branches.try_into().unwrap();
2432
2433 self.break_for_else(built_tree.otherwise_block, self.source_info(expr_span));
2434
2435 match declare_let_bindings {
2436 DeclareLetBindings::Yes => {
2437 let expr_place = scrutinee.try_to_place(self);
2438 let opt_expr_place = expr_place.as_ref().map(|place| (Some(place), expr_span));
2439 self.declare_bindings(
2440 source_scope,
2441 pat.span.to(scope_span),
2442 pat,
2443 None,
2444 opt_expr_place,
2445 );
2446 }
2447 DeclareLetBindings::No => {} // Caller is responsible for bindings.
2448 DeclareLetBindings::LetNotPermitted => {
2449 self.tcx.dcx().span_bug(expr_span, "let expression not expected in this context")
2450 }
2451 }
2452
2453 let success = self.bind_pattern(self.source_info(pat.span), branch, &[], expr_span, None);
2454
2455 // If branch coverage is enabled, record this branch.
2456 self.visit_coverage_conditional_let(pat, success, built_tree.otherwise_block);
2457
2458 success.unit()
2459 }
2460
2461 /// Initializes each of the bindings from the candidate by
2462 /// moving/copying/ref'ing the source as appropriate. Tests the guard, if
2463 /// any, and then branches to the arm. Returns the block for the case where
2464 /// the guard succeeds.
2465 ///
2466 /// Note: we do not check earlier that if there is a guard,
2467 /// there cannot be move bindings. We avoid a use-after-move by only
2468 /// moving the binding once the guard has evaluated to true (see below).
2469 fn bind_and_guard_matched_candidate(
2470 &mut self,
2471 sub_branch: MatchTreeSubBranch<'tcx>,
2472 fake_borrows: &[(Place<'tcx>, Local, FakeBorrowKind)],
2473 scrutinee_span: Span,
2474 arm_match_scope: Option<(&Arm<'tcx>, region::Scope)>,
2475 schedule_drops: ScheduleDrops,
2476 ) -> BasicBlock {
2477 debug!("bind_and_guard_matched_candidate(subbranch={:?})", sub_branch);
2478
2479 let block = sub_branch.success_block;
2480
2481 if sub_branch.is_never {
2482 // This arm has a dummy body, we don't need to generate code for it. `block` is already
2483 // unreachable (except via false edge).
2484 let source_info = self.source_info(sub_branch.span);
2485 self.cfg.terminate(block, source_info, TerminatorKind::Unreachable);
2486 return self.cfg.start_new_block();
2487 }
2488
2489 self.ascribe_types(block, sub_branch.ascriptions);
2490
2491 // Lower an instance of the arm guard (if present) for this candidate,
2492 // and then perform bindings for the arm body.
2493 if let Some((arm, match_scope)) = arm_match_scope
2494 && let Some(guard) = arm.guard
2495 {
2496 let tcx = self.tcx;
2497
2498 // Bindings for guards require some extra handling to automatically
2499 // insert implicit references/dereferences.
2500 // This always schedules storage drops, so we may need to unschedule them below.
2501 self.bind_matched_candidate_for_guard(block, sub_branch.bindings.iter());
2502 let guard_frame = GuardFrame {
2503 locals: sub_branch
2504 .bindings
2505 .iter()
2506 .map(|b| GuardFrameLocal::new(b.var_id))
2507 .collect(),
2508 };
2509 debug!("entering guard building context: {:?}", guard_frame);
2510 self.guard_context.push(guard_frame);
2511
2512 let re_erased = tcx.lifetimes.re_erased;
2513 let scrutinee_source_info = self.source_info(scrutinee_span);
2514 for &(place, temp, kind) in fake_borrows {
2515 let borrow = Rvalue::Ref(re_erased, BorrowKind::Fake(kind), place);
2516 self.cfg.push_assign(block, scrutinee_source_info, Place::from(temp), borrow);
2517 }
2518
2519 let mut guard_span = rustc_span::DUMMY_SP;
2520
2521 let (post_guard_block, otherwise_post_guard_block) =
2522 self.in_if_then_scope(match_scope, guard_span, |this| {
2523 guard_span = this.thir[guard].span;
2524 this.then_else_break(
2525 block,
2526 guard,
2527 None, // Use `self.local_scope()` as the temp scope
2528 this.source_info(arm.span),
2529 DeclareLetBindings::No, // For guards, `let` bindings are declared separately
2530 )
2531 });
2532
2533 // If this isn't the final sub-branch being lowered, we need to unschedule drops of
2534 // bindings and temporaries created for and by the guard. As a result, the drop order
2535 // for the arm will correspond to the binding order of the final sub-branch lowered.
2536 if matches!(schedule_drops, ScheduleDrops::No) {
2537 self.clear_match_arm_and_guard_scopes(arm.scope);
2538 }
2539
2540 let source_info = self.source_info(guard_span);
2541 let guard_end = self.source_info(tcx.sess.source_map().end_point(guard_span));
2542 let guard_frame = self.guard_context.pop().unwrap();
2543 debug!("Exiting guard building context with locals: {:?}", guard_frame);
2544
2545 for &(_, temp, _) in fake_borrows {
2546 let cause = FakeReadCause::ForMatchGuard;
2547 self.cfg.push_fake_read(post_guard_block, guard_end, cause, Place::from(temp));
2548 }
2549
2550 self.cfg.goto(otherwise_post_guard_block, source_info, sub_branch.otherwise_block);
2551
2552 // We want to ensure that the matched candidates are bound
2553 // after we have confirmed this candidate *and* any
2554 // associated guard; Binding them on `block` is too soon,
2555 // because that would be before we've checked the result
2556 // from the guard.
2557 //
2558 // But binding them on the arm is *too late*, because
2559 // then all of the candidates for a single arm would be
2560 // bound in the same place, that would cause a case like:
2561 //
2562 // ```rust
2563 // match (30, 2) {
2564 // (mut x, 1) | (2, mut x) if { true } => { ... }
2565 // ... // ^^^^^^^ (this is `arm_block`)
2566 // }
2567 // ```
2568 //
2569 // would yield an `arm_block` something like:
2570 //
2571 // ```
2572 // StorageLive(_4); // _4 is `x`
2573 // _4 = &mut (_1.0: i32); // this is handling `(mut x, 1)` case
2574 // _4 = &mut (_1.1: i32); // this is handling `(2, mut x)` case
2575 // ```
2576 //
2577 // and that is clearly not correct.
2578 let by_value_bindings = sub_branch
2579 .bindings
2580 .iter()
2581 .filter(|binding| matches!(binding.binding_mode.0, ByRef::No));
2582 // Read all of the by reference bindings to ensure that the
2583 // place they refer to can't be modified by the guard.
2584 for binding in by_value_bindings.clone() {
2585 let local_id = self.var_local_id(binding.var_id, RefWithinGuard);
2586 let cause = FakeReadCause::ForGuardBinding;
2587 self.cfg.push_fake_read(post_guard_block, guard_end, cause, Place::from(local_id));
2588 }
2589 // Only schedule drops for the last sub-branch we lower.
2590 self.bind_matched_candidate_for_arm_body(
2591 post_guard_block,
2592 schedule_drops,
2593 by_value_bindings,
2594 );
2595
2596 post_guard_block
2597 } else {
2598 // (Here, it is not too early to bind the matched
2599 // candidate on `block`, because there is no guard result
2600 // that we have to inspect before we bind them.)
2601 self.bind_matched_candidate_for_arm_body(
2602 block,
2603 schedule_drops,
2604 sub_branch.bindings.iter(),
2605 );
2606 block
2607 }
2608 }
2609
2610 /// Append `AscribeUserType` statements onto the end of `block`
2611 /// for each ascription
2612 fn ascribe_types(
2613 &mut self,
2614 block: BasicBlock,
2615 ascriptions: impl IntoIterator<Item = Ascription<'tcx>>,
2616 ) {
2617 for ascription in ascriptions {
2618 let source_info = self.source_info(ascription.annotation.span);
2619
2620 let base = self.canonical_user_type_annotations.push(ascription.annotation);
2621 self.cfg.push(
2622 block,
2623 Statement::new(
2624 source_info,
2625 StatementKind::AscribeUserType(
2626 Box::new((
2627 ascription.source,
2628 UserTypeProjection { base, projs: Vec::new() },
2629 )),
2630 ascription.variance,
2631 ),
2632 ),
2633 );
2634 }
2635 }
2636
2637 /// Binding for guards is a bit different from binding for the arm body,
2638 /// because an extra layer of implicit reference/dereference is added.
2639 ///
2640 /// The idea is that any pattern bindings of type T will map to a `&T` within
2641 /// the context of the guard expression, but will continue to map to a `T`
2642 /// in the context of the arm body. To avoid surfacing this distinction in
2643 /// the user source code (which would be a severe change to the language and
2644 /// require far more revision to the compiler), any occurrence of the
2645 /// identifier in the guard expression will automatically get a deref op
2646 /// applied to it. (See the caller of [`Self::is_bound_var_in_guard`].)
2647 ///
2648 /// So an input like:
2649 ///
2650 /// ```ignore (illustrative)
2651 /// let place = Foo::new();
2652 /// match place { foo if inspect(foo)
2653 /// => feed(foo), ... }
2654 /// ```
2655 ///
2656 /// will be treated as if it were really something like:
2657 ///
2658 /// ```ignore (illustrative)
2659 /// let place = Foo::new();
2660 /// match place { Foo { .. } if { let tmp1 = &place; inspect(*tmp1) }
2661 /// => { let tmp2 = place; feed(tmp2) }, ... }
2662 /// ```
2663 ///
2664 /// And an input like:
2665 ///
2666 /// ```ignore (illustrative)
2667 /// let place = Foo::new();
2668 /// match place { ref mut foo if inspect(foo)
2669 /// => feed(foo), ... }
2670 /// ```
2671 ///
2672 /// will be treated as if it were really something like:
2673 ///
2674 /// ```ignore (illustrative)
2675 /// let place = Foo::new();
2676 /// match place { Foo { .. } if { let tmp1 = & &mut place; inspect(*tmp1) }
2677 /// => { let tmp2 = &mut place; feed(tmp2) }, ... }
2678 /// ```
2679 /// ---
2680 ///
2681 /// ## Implementation notes
2682 ///
2683 /// To encode the distinction above, we must inject the
2684 /// temporaries `tmp1` and `tmp2`.
2685 ///
2686 /// There are two cases of interest: binding by-value, and binding by-ref.
2687 ///
2688 /// 1. Binding by-value: Things are simple.
2689 ///
2690 /// * Establishing `tmp1` creates a reference into the
2691 /// matched place. This code is emitted by
2692 /// [`Self::bind_matched_candidate_for_guard`].
2693 ///
2694 /// * `tmp2` is only initialized "lazily", after we have
2695 /// checked the guard. Thus, the code that can trigger
2696 /// moves out of the candidate can only fire after the
2697 /// guard evaluated to true. This initialization code is
2698 /// emitted by [`Self::bind_matched_candidate_for_arm_body`].
2699 ///
2700 /// 2. Binding by-reference: Things are tricky.
2701 ///
2702 /// * Here, the guard expression wants a `&&` or `&&mut`
2703 /// into the original input. This means we need to borrow
2704 /// the reference that we create for the arm.
2705 /// * So we eagerly create the reference for the arm and then take a
2706 /// reference to that.
2707 ///
2708 /// ---
2709 ///
2710 /// See these PRs for some historical context:
2711 /// - <https://github.com/rust-lang/rust/pull/49870> (introduction of autoref)
2712 /// - <https://github.com/rust-lang/rust/pull/59114> (always use autoref)
2713 fn bind_matched_candidate_for_guard<'b>(
2714 &mut self,
2715 block: BasicBlock,
2716 bindings: impl IntoIterator<Item = &'b Binding<'tcx>>,
2717 ) where
2718 'tcx: 'b,
2719 {
2720 debug!("bind_matched_candidate_for_guard(block={:?})", block);
2721
2722 // Assign each of the bindings. Since we are binding for a
2723 // guard expression, this will never trigger moves out of the
2724 // candidate.
2725 let re_erased = self.tcx.lifetimes.re_erased;
2726 for binding in bindings {
2727 debug!("bind_matched_candidate_for_guard(binding={:?})", binding);
2728 let source_info = self.source_info(binding.span);
2729
2730 // For each pattern ident P of type T, `ref_for_guard` is
2731 // a reference R: &T pointing to the location matched by
2732 // the pattern, and every occurrence of P within a guard
2733 // denotes *R.
2734 // Drops must be scheduled to emit `StorageDead` on the guard's failure/break branches.
2735 let ref_for_guard = self.storage_live_binding(
2736 block,
2737 binding.var_id,
2738 binding.span,
2739 binding.is_shorthand,
2740 RefWithinGuard,
2741 ScheduleDrops::Yes,
2742 );
2743 match binding.binding_mode.0 {
2744 ByRef::No => {
2745 // The arm binding will be by value, so for the guard binding
2746 // just take a shared reference to the matched place.
2747 let rvalue = Rvalue::Ref(re_erased, BorrowKind::Shared, binding.source);
2748 self.cfg.push_assign(block, source_info, ref_for_guard, rvalue);
2749 }
2750 ByRef::Yes(mutbl) => {
2751 // The arm binding will be by reference, so eagerly create it now. Drops must
2752 // be scheduled to emit `StorageDead` on the guard's failure/break branches.
2753 let value_for_arm = self.storage_live_binding(
2754 block,
2755 binding.var_id,
2756 binding.span,
2757 binding.is_shorthand,
2758 OutsideGuard,
2759 ScheduleDrops::Yes,
2760 );
2761
2762 let rvalue =
2763 Rvalue::Ref(re_erased, util::ref_pat_borrow_kind(mutbl), binding.source);
2764 self.cfg.push_assign(block, source_info, value_for_arm, rvalue);
2765 // For the guard binding, take a shared reference to that reference.
2766 let rvalue = Rvalue::Ref(re_erased, BorrowKind::Shared, value_for_arm);
2767 self.cfg.push_assign(block, source_info, ref_for_guard, rvalue);
2768 }
2769 }
2770 }
2771 }
2772
2773 fn bind_matched_candidate_for_arm_body<'b>(
2774 &mut self,
2775 block: BasicBlock,
2776 schedule_drops: ScheduleDrops,
2777 bindings: impl IntoIterator<Item = &'b Binding<'tcx>>,
2778 ) where
2779 'tcx: 'b,
2780 {
2781 debug!("bind_matched_candidate_for_arm_body(block={:?})", block);
2782
2783 let re_erased = self.tcx.lifetimes.re_erased;
2784 // Assign each of the bindings. This may trigger moves out of the candidate.
2785 for binding in bindings {
2786 let source_info = self.source_info(binding.span);
2787 let local = self.storage_live_binding(
2788 block,
2789 binding.var_id,
2790 binding.span,
2791 binding.is_shorthand,
2792 OutsideGuard,
2793 schedule_drops,
2794 );
2795 if matches!(schedule_drops, ScheduleDrops::Yes) {
2796 self.schedule_drop_for_binding(binding.var_id, binding.span, OutsideGuard);
2797 }
2798 let rvalue = match binding.binding_mode.0 {
2799 ByRef::No => Rvalue::Use(self.consume_by_copy_or_move(binding.source)),
2800 ByRef::Yes(mutbl) => {
2801 Rvalue::Ref(re_erased, util::ref_pat_borrow_kind(mutbl), binding.source)
2802 }
2803 };
2804 self.cfg.push_assign(block, source_info, local, rvalue);
2805 }
2806 }
2807
2808 /// Each binding (`ref mut var`/`ref var`/`mut var`/`var`, where the bound
2809 /// `var` has type `T` in the arm body) in a pattern maps to 2 locals. The
2810 /// first local is a binding for occurrences of `var` in the guard, which
2811 /// will have type `&T`. The second local is a binding for occurrences of
2812 /// `var` in the arm body, which will have type `T`.
2813 #[instrument(skip(self), level = "debug")]
2814 fn declare_binding(
2815 &mut self,
2816 source_info: SourceInfo,
2817 visibility_scope: SourceScope,
2818 name: Symbol,
2819 mode: BindingMode,
2820 var_id: LocalVarId,
2821 var_ty: Ty<'tcx>,
2822 user_ty: Option<Box<UserTypeProjections>>,
2823 has_guard: ArmHasGuard,
2824 opt_match_place: Option<(Option<Place<'tcx>>, Span)>,
2825 pat_span: Span,
2826 ) {
2827 let tcx = self.tcx;
2828 let debug_source_info = SourceInfo { span: source_info.span, scope: visibility_scope };
2829 let local = LocalDecl {
2830 mutability: mode.1,
2831 ty: var_ty,
2832 user_ty,
2833 source_info,
2834 local_info: ClearCrossCrate::Set(Box::new(LocalInfo::User(BindingForm::Var(
2835 VarBindingForm {
2836 binding_mode: mode,
2837 // hypothetically, `visit_primary_bindings` could try to unzip
2838 // an outermost hir::Ty as we descend, matching up
2839 // idents in pat; but complex w/ unclear UI payoff.
2840 // Instead, just abandon providing diagnostic info.
2841 opt_ty_info: None,
2842 opt_match_place,
2843 pat_span,
2844 introductions: Vec::new(),
2845 },
2846 )))),
2847 };
2848 let for_arm_body = self.local_decls.push(local);
2849 if self.should_emit_debug_info_for_binding(name, var_id) {
2850 self.var_debug_info.push(VarDebugInfo {
2851 name,
2852 source_info: debug_source_info,
2853 value: VarDebugInfoContents::Place(for_arm_body.into()),
2854 composite: None,
2855 argument_index: None,
2856 });
2857 }
2858 let locals = if has_guard.0 {
2859 let ref_for_guard = self.local_decls.push(LocalDecl::<'tcx> {
2860 // This variable isn't mutated but has a name, so has to be
2861 // immutable to avoid the unused mut lint.
2862 mutability: Mutability::Not,
2863 ty: Ty::new_imm_ref(tcx, tcx.lifetimes.re_erased, var_ty),
2864 user_ty: None,
2865 source_info,
2866 local_info: ClearCrossCrate::Set(Box::new(LocalInfo::User(
2867 BindingForm::RefForGuard(for_arm_body),
2868 ))),
2869 });
2870 if self.should_emit_debug_info_for_binding(name, var_id) {
2871 self.var_debug_info.push(VarDebugInfo {
2872 name,
2873 source_info: debug_source_info,
2874 value: VarDebugInfoContents::Place(ref_for_guard.into()),
2875 composite: None,
2876 argument_index: None,
2877 });
2878 }
2879 LocalsForNode::ForGuard { ref_for_guard, for_arm_body }
2880 } else {
2881 LocalsForNode::One(for_arm_body)
2882 };
2883 debug!(?locals);
2884 self.var_indices.insert(var_id, locals);
2885 }
2886
2887 /// Some bindings are introduced when producing HIR from the AST and don't
2888 /// actually exist in the source. Skip producing debug info for those when
2889 /// we can recognize them.
2890 fn should_emit_debug_info_for_binding(&self, name: Symbol, var_id: LocalVarId) -> bool {
2891 // For now we only recognize the output of desugaring assigns.
2892 if name != sym::lhs {
2893 return true;
2894 }
2895
2896 let tcx = self.tcx;
2897 for (_, node) in tcx.hir_parent_iter(var_id.0) {
2898 // FIXME(khuey) at what point is it safe to bail on the iterator?
2899 // Can we stop at the first non-Pat node?
2900 if matches!(node, Node::LetStmt(&LetStmt { source: LocalSource::AssignDesugar(_), .. }))
2901 {
2902 return false;
2903 }
2904 }
2905
2906 true
2907 }
2908
2909 /// Attempt to statically pick the `BasicBlock` that a value would resolve to at runtime.
2910 pub(crate) fn static_pattern_match(
2911 &self,
2912 cx: &RustcPatCtxt<'_, 'tcx>,
2913 valtree: ValTree<'tcx>,
2914 arms: &[ArmId],
2915 built_match_tree: &BuiltMatchTree<'tcx>,
2916 ) -> Option<BasicBlock> {
2917 let it = arms.iter().zip(built_match_tree.branches.iter());
2918 for (&arm_id, branch) in it {
2919 let pat = cx.lower_pat(&*self.thir.arms[arm_id].pattern);
2920
2921 // Peel off or-patterns if they exist.
2922 if let rustc_pattern_analysis::rustc::Constructor::Or = pat.ctor() {
2923 for pat in pat.iter_fields() {
2924 // For top-level or-patterns (the only ones we accept right now), when the
2925 // bindings are the same (e.g. there are none), the sub_branch is stored just
2926 // once.
2927 let sub_branch = branch
2928 .sub_branches
2929 .get(pat.idx)
2930 .or_else(|| branch.sub_branches.last())
2931 .unwrap();
2932
2933 match self.static_pattern_match_inner(valtree, &pat.pat) {
2934 true => return Some(sub_branch.success_block),
2935 false => continue,
2936 }
2937 }
2938 } else if self.static_pattern_match_inner(valtree, &pat) {
2939 return Some(branch.sub_branches[0].success_block);
2940 }
2941 }
2942
2943 None
2944 }
2945
2946 /// Helper for [`Self::static_pattern_match`], checking whether the value represented by the
2947 /// `ValTree` matches the given pattern. This function does not recurse, meaning that it does
2948 /// not handle or-patterns, or patterns for types with fields.
2949 fn static_pattern_match_inner(
2950 &self,
2951 valtree: ty::ValTree<'tcx>,
2952 pat: &DeconstructedPat<'_, 'tcx>,
2953 ) -> bool {
2954 use rustc_pattern_analysis::constructor::{IntRange, MaybeInfiniteInt};
2955 use rustc_pattern_analysis::rustc::Constructor;
2956
2957 match pat.ctor() {
2958 Constructor::Variant(variant_index) => {
2959 let ValTreeKind::Branch(box [actual_variant_idx]) = *valtree else {
2960 bug!("malformed valtree for an enum")
2961 };
2962
2963 let ValTreeKind::Leaf(actual_variant_idx) = ***actual_variant_idx else {
2964 bug!("malformed valtree for an enum")
2965 };
2966
2967 *variant_index == VariantIdx::from_u32(actual_variant_idx.to_u32())
2968 }
2969 Constructor::IntRange(int_range) => {
2970 let size = pat.ty().primitive_size(self.tcx);
2971 let actual_int = valtree.unwrap_leaf().to_bits(size);
2972 let actual_int = if pat.ty().is_signed() {
2973 MaybeInfiniteInt::new_finite_int(actual_int, size.bits())
2974 } else {
2975 MaybeInfiniteInt::new_finite_uint(actual_int)
2976 };
2977 IntRange::from_singleton(actual_int).is_subrange(int_range)
2978 }
2979 Constructor::Bool(pattern_value) => match valtree.unwrap_leaf().try_to_bool() {
2980 Ok(actual_value) => *pattern_value == actual_value,
2981 Err(()) => bug!("bool value with invalid bits"),
2982 },
2983 Constructor::F16Range(l, h, end) => {
2984 let actual = valtree.unwrap_leaf().to_f16();
2985 match end {
2986 RangeEnd::Included => (*l..=*h).contains(&actual),
2987 RangeEnd::Excluded => (*l..*h).contains(&actual),
2988 }
2989 }
2990 Constructor::F32Range(l, h, end) => {
2991 let actual = valtree.unwrap_leaf().to_f32();
2992 match end {
2993 RangeEnd::Included => (*l..=*h).contains(&actual),
2994 RangeEnd::Excluded => (*l..*h).contains(&actual),
2995 }
2996 }
2997 Constructor::F64Range(l, h, end) => {
2998 let actual = valtree.unwrap_leaf().to_f64();
2999 match end {
3000 RangeEnd::Included => (*l..=*h).contains(&actual),
3001 RangeEnd::Excluded => (*l..*h).contains(&actual),
3002 }
3003 }
3004 Constructor::F128Range(l, h, end) => {
3005 let actual = valtree.unwrap_leaf().to_f128();
3006 match end {
3007 RangeEnd::Included => (*l..=*h).contains(&actual),
3008 RangeEnd::Excluded => (*l..*h).contains(&actual),
3009 }
3010 }
3011 Constructor::Wildcard => true,
3012
3013 // Opaque patterns must not be matched on structurally.
3014 Constructor::Opaque(_) => false,
3015
3016 // These we may eventually support:
3017 Constructor::Struct
3018 | Constructor::Ref
3019 | Constructor::DerefPattern(_)
3020 | Constructor::Slice(_)
3021 | Constructor::UnionField
3022 | Constructor::Or
3023 | Constructor::Str(_) => bug!("unsupported pattern constructor {:?}", pat.ctor()),
3024
3025 // These should never occur here:
3026 Constructor::Never
3027 | Constructor::NonExhaustive
3028 | Constructor::Hidden
3029 | Constructor::Missing
3030 | Constructor::PrivateUninhabited => {
3031 bug!("unsupported pattern constructor {:?}", pat.ctor())
3032 }
3033 }
3034 }
3035}