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}