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