Struct rustc_mir_build::build::Builder

struct Builder<'a, 'tcx> {

    tcx: TyCtxt<'tcx>,
    infcx: InferCtxt<'tcx>,
    region_scope_tree: &'tcx ScopeTree,
    param_env: ParamEnv<'tcx>,
    thir: &'a Thir<'tcx>,
    cfg: CFG<'tcx>,
    def_id: LocalDefId,
    hir_id: HirId,
    parent_module: DefId,
    check_overflow: bool,
    fn_span: Span,
    arg_count: usize,
    coroutine: Option<Box<CoroutineInfo<'tcx>>>,
    scopes: Scopes<'tcx>,
    block_context: BlockContext,
    in_scope_unsafe: Safety,
    source_scopes: IndexVec<SourceScope, SourceScopeData<'tcx>>,
    source_scope: SourceScope,
    guard_context: Vec<GuardFrame>,
    fixed_temps: FxHashMap<ExprId, Local>,
    fixed_temps_scope: Option<Scope>,
    var_indices: FxHashMap<LocalVarId, LocalsForNode>,
    local_decls: IndexVec<Local, LocalDecl<'tcx>>,
    canonical_user_type_annotations: CanonicalUserTypeAnnotations<'tcx>,
    upvars: SortedIndexMultiMap<usize, HirId, Capture<'tcx>>,
    unit_temp: Option<Place<'tcx>>,
    var_debug_info: Vec<VarDebugInfo<'tcx>>,
    lint_level_roots_cache: GrowableBitSet<ItemLocalId>,
    coverage_branch_info: Option<BranchInfoBuilder>,
}

Fields

tcx: TyCtxt<'tcx>

infcx: InferCtxt<'tcx>

region_scope_tree: &'tcx ScopeTree

param_env: ParamEnv<'tcx>

thir: &'a Thir<'tcx>

cfg: CFG<'tcx>

def_id: LocalDefId

hir_id: HirId

parent_module: DefId

check_overflow: bool

fn_span: Span

arg_count: usize

coroutine: Option<Box<CoroutineInfo<'tcx>>>

scopes: Scopes<'tcx>

The current set of scopes, updated as we traverse; see the scope module for more details.

block_context: BlockContext

The block-context: each time we build the code within an thir::Block, we push a frame here tracking whether we are building a statement or if we are pushing the tail expression of the block. This is used to embed information in generated temps about whether they were created for a block tail expression or not.

It would be great if we could fold this into self.scopes somehow, but right now I think that is very tightly tied to the code generation in ways that we cannot (or should not) start just throwing new entries onto that vector in order to distinguish the context of EXPR1 from the context of EXPR2 in { STMTS; EXPR1 } + EXPR2.

in_scope_unsafe: Safety

The current unsafe block in scope

source_scopes: IndexVec<SourceScope, SourceScopeData<'tcx>>

The vector of all scopes that we have created thus far; we track this for debuginfo later.

source_scope: SourceScope

guard_context: Vec<GuardFrame>

The guard-context: each time we build the guard expression for a match arm, we push onto this stack, and then pop when we finish building it.

fixed_temps: FxHashMap<ExprId, Local>

Temporaries with fixed indexes. Used so that if-let guards on arms with an or-pattern are only created once.

fixed_temps_scope: Option<Scope>

Scope of temporaries that should be deduplicated using Self::fixed_temps.

var_indices: FxHashMap<LocalVarId, LocalsForNode>

Maps HirIds of variable bindings to the Locals created for them. (A match binding can have two locals; the 2nd is for the arm’s guard.)

local_decls: IndexVec<Local, LocalDecl<'tcx>>

canonical_user_type_annotations: CanonicalUserTypeAnnotations<'tcx>

upvars: SortedIndexMultiMap<usize, HirId, Capture<'tcx>>

unit_temp: Option<Place<'tcx>>

var_debug_info: Vec<VarDebugInfo<'tcx>>

lint_level_roots_cache: GrowableBitSet<ItemLocalId>

coverage_branch_info: Option<BranchInfoBuilder>

Collects additional coverage information during MIR building. Only present if branch coverage is enabled and this function is eligible.

Implementations

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn ast_block( &mut self, destination: Place<'tcx>, block: BasicBlock, ast_block: BlockId, source_info: SourceInfo ) -> BlockAnd<()>

fn ast_block_stmts( &mut self, destination: Place<'tcx>, block: BasicBlock, span: Span, stmts: &[StmtId], expr: Option<ExprId>, safety_mode: BlockSafety, region_scope: Scope ) -> BlockAnd<()>

fn update_source_scope_for_safety_mode( &mut self, span: Span, safety_mode: BlockSafety )

If we are entering an unsafe block, create a new source scope

impl Builder<'_, '_>

pub(crate) fn visit_coverage_branch_condition( &mut self, expr_id: ExprId, then_block: BasicBlock, else_block: BasicBlock )

If branch coverage is enabled, inject marker statements into then_block and else_block, and record their IDs in the table of branch spans.

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn as_constant(&mut self, expr: &Expr<'tcx>) -> ConstOperand<'tcx>

Compile expr, yielding a compile-time constant. Assumes that expr is a valid compile-time constant!

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn as_local_operand( &mut self, block: BasicBlock, expr_id: ExprId ) -> BlockAnd<Operand<'tcx>>

Returns an operand suitable for use until the end of the current scope expression.

The operand returned from this function will not be valid after the current enclosing ExprKind::Scope has ended, so please do not return it from functions to avoid bad miscompiles.

pub(crate) fn as_local_call_operand( &mut self, block: BasicBlock, expr: ExprId ) -> BlockAnd<Operand<'tcx>>

Returns an operand suitable for use until the end of the current scope expression and suitable also to be passed as function arguments.

The operand returned from this function will not be valid after an ExprKind::Scope is passed, so please do not return it from functions to avoid bad miscompiles. Returns an operand suitable for use as a call argument. This is almost always equivalent to as_operand, except for the particular case of passing values of (potentially) unsized types “by value” (see details below).

The operand returned from this function will not be valid after the current enclosing ExprKind::Scope has ended, so please do not return it from functions to avoid bad miscompiles.

Parameters of unsized types

We tweak the handling of parameters of unsized type slightly to avoid the need to create a local variable of unsized type. For example, consider this program:

#![feature(unsized_locals, unsized_fn_params)]
fn foo(p: dyn Debug) { dbg!(p); }

fn bar(box_p: Box<dyn Debug>) { foo(*box_p); }

Ordinarily, for sized types, we would compile the call foo(*p) like so:

let tmp0 = *box_p; // tmp0 would be the operand returned by this function call
foo(tmp0)

But because the parameter to foo is of the unsized type dyn Debug, and because it is being moved the deref of a box, we compile it slightly differently. The temporary tmp0 that we create stores the entire box, and the parameter to the call itself will be *tmp0:

let tmp0 = box_p; call foo(*tmp0)

This way, the temporary tmp0 that we create has type Box<dyn Debug>, which is sized. The value passed to the call (*tmp0) still has the dyn Debug type – but the way that calls are compiled means that this parameter will be passed “by reference”, meaning that we will actually provide a pointer to the interior of the box, and not move the dyn Debug value to the stack.

See #68304 for more details.

pub(crate) fn as_operand( &mut self, block: BasicBlock, scope: Option<Scope>, expr_id: ExprId, local_info: LocalInfo<'tcx>, needs_temporary: NeedsTemporary ) -> BlockAnd<Operand<'tcx>>

Compile expr into a value that can be used as an operand. If expr is a place like x, this will introduce a temporary tmp = x, so that we capture the value of x at this time.

If we end up needing to create a temporary, then we will use local_info as its LocalInfo, unless as_temporary has already assigned it a non-None LocalInfo. Normally, you should use None for local_info

The operand is known to be live until the end of scope.

Like as_local_call_operand, except that the argument will not be valid once scope ends.

pub(crate) fn as_call_operand( &mut self, block: BasicBlock, scope: Option<Scope>, expr_id: ExprId ) -> BlockAnd<Operand<'tcx>>

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn as_place( &mut self, block: BasicBlock, expr_id: ExprId ) -> BlockAnd<Place<'tcx>>

Compile expr, yielding a place that we can move from etc.

WARNING: Any user code might:

• Invalidate any slice bounds checks performed.
• Change the address that this Place refers to.
• Modify the memory that this place refers to.
• Invalidate the memory that this place refers to, this will be caught by borrow checking.

Extra care is needed if any user code is allowed to run between calling this method and using it, as is the case for match and index expressions.

pub(crate) fn as_place_builder( &mut self, block: BasicBlock, expr_id: ExprId ) -> BlockAnd<PlaceBuilder<'tcx>>

This is used when constructing a compound Place, so that we can avoid creating intermediate Place values until we know the full set of projections.

pub(crate) fn as_read_only_place( &mut self, block: BasicBlock, expr_id: ExprId ) -> BlockAnd<Place<'tcx>>

Compile expr, yielding a place that we can move from etc. Mutability note: The caller of this method promises only to read from the resulting place. The place itself may or may not be mutable:

• If this expr is a place expr like a.b, then we will return that place.
• Otherwise, a temporary is created: in that event, it will be an immutable temporary.

fn as_read_only_place_builder( &mut self, block: BasicBlock, expr_id: ExprId ) -> BlockAnd<PlaceBuilder<'tcx>>

This is used when constructing a compound Place, so that we can avoid creating intermediate Place values until we know the full set of projections. Mutability note: The caller of this method promises only to read from the resulting place. The place itself may or may not be mutable:

• If this expr is a place expr like a.b, then we will return that place.
• Otherwise, a temporary is created: in that event, it will be an immutable temporary.

fn expr_as_place( &mut self, block: BasicBlock, expr_id: ExprId, mutability: Mutability, fake_borrow_temps: Option<&mut Vec<Local>> ) -> BlockAnd<PlaceBuilder<'tcx>>

fn lower_captured_upvar( &mut self, block: BasicBlock, closure_def_id: LocalDefId, var_hir_id: LocalVarId ) -> BlockAnd<PlaceBuilder<'tcx>>

Lower a captured upvar. Note we might not know the actual capture index, so we create a place starting from PlaceBase::Upvar, which will be resolved once all projections that allow us to identify a capture have been applied.

fn lower_index_expression( &mut self, block: BasicBlock, base: ExprId, index: ExprId, mutability: Mutability, fake_borrow_temps: Option<&mut Vec<Local>>, temp_lifetime: Option<Scope>, expr_span: Span, source_info: SourceInfo ) -> BlockAnd<PlaceBuilder<'tcx>>

Lower an index expression

This has two complications;

• We need to do a bounds check.
• We need to ensure that the bounds check can’t be invalidated using an expression like x[1][{x = y; 2}]. We use fake borrows here to ensure that this is the case.

fn bounds_check( &mut self, block: BasicBlock, slice: &PlaceBuilder<'tcx>, index: Local, expr_span: Span, source_info: SourceInfo ) -> BasicBlock

fn add_fake_borrows_of_base( &mut self, base_place: Place<'tcx>, block: BasicBlock, fake_borrow_temps: &mut Vec<Local>, expr_span: Span, source_info: SourceInfo )

fn read_fake_borrows( &mut self, bb: BasicBlock, fake_borrow_temps: &mut Vec<Local>, source_info: SourceInfo )

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn as_local_rvalue( &mut self, block: BasicBlock, expr_id: ExprId ) -> BlockAnd<Rvalue<'tcx>>

Returns an rvalue suitable for use until the end of the current scope expression.

The operand returned from this function will not be valid after an ExprKind::Scope is passed, so please do not return it from functions to avoid bad miscompiles.

pub(crate) fn as_rvalue( &mut self, block: BasicBlock, scope: Option<Scope>, expr_id: ExprId ) -> BlockAnd<Rvalue<'tcx>>

Compile expr, yielding an rvalue.

pub(crate) fn build_binary_op( &mut self, block: BasicBlock, op: BinOp, span: Span, ty: Ty<'tcx>, lhs: Operand<'tcx>, rhs: Operand<'tcx> ) -> BlockAnd<Rvalue<'tcx>>

fn build_zero_repeat( &mut self, block: BasicBlock, value: ExprId, scope: Option<Scope>, outer_source_info: SourceInfo ) -> BlockAnd<Rvalue<'tcx>>

fn limit_capture_mutability( &mut self, upvar_span: Span, upvar_ty: Ty<'tcx>, temp_lifetime: Option<Scope>, block: BasicBlock, arg: ExprId ) -> BlockAnd<Operand<'tcx>>

fn neg_1_literal(&mut self, span: Span, ty: Ty<'tcx>) -> Operand<'tcx>

fn minval_literal(&mut self, span: Span, ty: Ty<'tcx>) -> Operand<'tcx>

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn as_temp( &mut self, block: BasicBlock, temp_lifetime: Option<Scope>, expr_id: ExprId, mutability: Mutability ) -> BlockAnd<Local>

Compile expr into a fresh temporary. This is used when building up rvalues so as to freeze the value that will be consumed.

fn as_temp_inner( &mut self, block: BasicBlock, temp_lifetime: Option<Scope>, expr_id: ExprId, mutability: Mutability ) -> BlockAnd<Local>

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn expr_into_dest( &mut self, destination: Place<'tcx>, block: BasicBlock, expr_id: ExprId ) -> BlockAnd<()>

Compile expr, storing the result into destination, which is assumed to be uninitialized.

fn is_let(&self, expr: ExprId) -> bool

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn stmt_expr( &mut self, block: BasicBlock, expr_id: ExprId, statement_scope: Option<Scope> ) -> BlockAnd<()>

Builds a block of MIR statements to evaluate the THIR expr.

The statement_scope is used if a statement temporary must be dropped.

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(super) fn simplify_match_pairs<'pat>( &mut self, match_pairs: &mut Vec<MatchPair<'pat, 'tcx>>, extra_data: &mut PatternExtraData<'tcx> )

Simplify a list of match pairs so they all require a test. Stores relevant bindings and ascriptions in extra_data.

pub(super) fn create_or_subcandidates<'pat>( &mut self, pats: &[FlatPat<'pat, 'tcx>], has_guard: bool ) -> Vec<Candidate<'pat, 'tcx>>

Create a new candidate for each pattern in pats, and recursively simplify tje single-or-pattern case.

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(super) fn test<'pat>( &mut self, match_pair: &MatchPair<'pat, 'tcx> ) -> Test<'tcx>

Identifies what test is needed to decide if match_pair is applicable.

It is a bug to call this with a not-fully-simplified pattern.

pub(super) fn perform_test( &mut self, match_start_span: Span, scrutinee_span: Span, block: BasicBlock, otherwise_block: BasicBlock, place_builder: &PlaceBuilder<'tcx>, test: &Test<'tcx>, target_blocks: FxIndexMap<TestBranch<'tcx>, BasicBlock> )

fn compare( &mut self, block: BasicBlock, success_block: BasicBlock, fail_block: BasicBlock, source_info: SourceInfo, op: BinOp, left: Operand<'tcx>, right: Operand<'tcx> )

Compare using the provided built-in comparison operator

fn non_scalar_compare( &mut self, block: BasicBlock, success_block: BasicBlock, fail_block: BasicBlock, source_info: SourceInfo, value: Const<'tcx>, val: Place<'tcx>, ty: Ty<'tcx> )

Compare two values using <T as std::compare::PartialEq>::eq. If the values are already references, just call it directly, otherwise take a reference to the values first and then call it.

pub(super) fn sort_candidate( &mut self, test_place: &PlaceBuilder<'tcx>, test: &Test<'tcx>, candidate: &mut Candidate<'_, 'tcx>, sorted_candidates: &FxIndexMap<TestBranch<'tcx>, Vec<&mut Candidate<'_, 'tcx>>> ) -> Option<TestBranch<'tcx>>

Given that we are performing test against test_place, this job sorts out what the status of candidate will be after the test. See test_candidates for the usage of this function. The candidate may be modified to update its match_pairs.

So, for example, if this candidate is x @ Some(P0) and the Test is a variant test, then we would modify the candidate to be (x as Option).0 @ P0 and return the index corresponding to the variant Some.

However, in some cases, the test may just not be relevant to candidate. For example, suppose we are testing whether foo.x == 22, but in one match arm we have Foo { x: _, ... }… in that case, the test for the value of x has no particular relevance to this candidate. In such cases, this function just returns None without doing anything. This is used by the overall match_candidates algorithm to structure the match as a whole. See match_candidates for more details.

FIXME(#29623). In some cases, we have some tricky choices to make. for example, if we are testing that x == 22, but the candidate is x @ 13..55, what should we do? In the event that the test is true, we know that the candidate applies, but in the event of false, we don’t know that it doesn’t apply. For now, we return false, indicate that the test does not apply to this candidate, but it might be we can get tighter match code if we do something a bit different.

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn field_match_pairs<'pat>( &mut self, place: PlaceBuilder<'tcx>, subpatterns: &'pat [FieldPat<'tcx>] ) -> Vec<MatchPair<'pat, 'tcx>>

pub(crate) fn prefix_slice_suffix<'pat>( &mut self, match_pairs: &mut Vec<MatchPair<'pat, 'tcx>>, place: &PlaceBuilder<'tcx>, prefix: &'pat [Box<Pat<'tcx>>], opt_slice: &'pat Option<Box<Pat<'tcx>>>, suffix: &'pat [Box<Pat<'tcx>>] )

pub(crate) fn false_edges( &mut self, from_block: BasicBlock, real_target: BasicBlock, imaginary_target: Option<BasicBlock>, source_info: SourceInfo )

Creates a false edge to imaginary_target and a real edge to real_target. If imaginary_target is none, or is the same as the real target, a Goto is generated instead to simplify the generated MIR.

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn then_else_break( &mut self, block: BasicBlock, expr_id: ExprId, temp_scope_override: Option<Scope>, variable_source_info: SourceInfo, declare_let_bindings: bool ) -> BlockAnd<()>

Lowers a condition in a way that ensures that variables bound in any let expressions are definitely initialized in the if body.

If declare_let_bindings is false then variables created in let expressions will not be declared. This is for if let guards on arms with an or pattern, where the guard is lowered multiple times.

fn then_else_break_inner( &mut self, block: BasicBlock, expr_id: ExprId, args: ThenElseArgs ) -> BlockAnd<()>

pub(crate) fn match_expr( &mut self, destination: Place<'tcx>, block: BasicBlock, scrutinee_id: ExprId, arms: &[ArmId], span: Span, scrutinee_span: Span ) -> BlockAnd<()>

Generates MIR for a match expression.

The MIR that we generate for a match looks like this.

[ 0. Pre-match ]
       |
[ 1. Evaluate Scrutinee (expression being matched on) ]
[ (PlaceMention of scrutinee) ]
       |
[ 2. Decision tree -- check discriminants ] <--------+
       |                                             |
       | (once a specific arm is chosen)             |
       |                                             |
[pre_binding_block]                           [otherwise_block]
       |                                             |
[ 3. Create "guard bindings" for arm ]               |
[ (create fake borrows) ]                            |
       |                                             |
[ 4. Execute guard code ]                            |
[ (read fake borrows) ] --(guard is false)-----------+
       |
       | (guard results in true)
       |
[ 5. Create real bindings and execute arm ]
       |
[ Exit match ]

All of the different arms have been stacked on top of each other to simplify the diagram. For an arm with no guard the blocks marked 3 and 4 and the fake borrows are omitted.

We generate MIR in the following steps:

1. Evaluate the scrutinee and add the PlaceMention of it (Builder::lower_scrutinee).
2. Create the decision tree (Builder::lower_match_tree).
3. Determine the fake borrows that are needed from the places that were matched against and create the required temporaries for them (Builder::calculate_fake_borrows).
4. Create everything else: the guards and the arms (Builder::lower_match_arms).

False edges

We don’t want to have the exact structure of the decision tree be visible through borrow checking. False edges ensure that the CFG as seen by borrow checking doesn’t encode this. False edges are added:

• From each pre-binding block to the next pre-binding block.
• From each otherwise block to the next pre-binding block.

fn lower_scrutinee( &mut self, block: BasicBlock, scrutinee_id: ExprId, scrutinee_span: Span ) -> BlockAnd<PlaceBuilder<'tcx>>

Evaluate the scrutinee and add the PlaceMention for it.

fn create_match_candidates<'pat>( &mut self, scrutinee: &PlaceBuilder<'tcx>, arms: &'pat [ArmId] ) -> Vec<(&'pat Arm<'tcx>, Candidate<'pat, 'tcx>)>

where 'a: 'pat,

Create the initial Candidates for a match expression.

fn lower_match_tree<'pat>( &mut self, block: BasicBlock, scrutinee_span: Span, scrutinee_place_builder: &PlaceBuilder<'tcx>, match_start_span: Span, match_has_guard: bool, candidates: &mut [&mut Candidate<'pat, 'tcx>] ) -> Vec<(Place<'tcx>, Local)>

Create the decision tree for the match expression, starting from block.

Modifies candidates to store the bindings and type ascriptions for that candidate.

Returns the places that need fake borrows because we bind or test them.

fn lower_match_arms( &mut self, destination: Place<'tcx>, scrutinee_place_builder: PlaceBuilder<'tcx>, scrutinee_span: Span, arm_candidates: Vec<(&Arm<'tcx>, Candidate<'_, 'tcx>)>, outer_source_info: SourceInfo, fake_borrow_temps: Vec<(Place<'tcx>, Local)> ) -> BlockAnd<()>

Lower the bindings, guards and arm bodies of a match expression.

The decision tree should have already been created (by Builder::lower_match_tree).

outer_source_info is the SourceInfo for the whole match.

fn bind_pattern( &mut self, outer_source_info: SourceInfo, candidate: Candidate<'_, 'tcx>, fake_borrow_temps: &[(Place<'tcx>, Local)], scrutinee_span: Span, arm_match_scope: Option<(&Arm<'tcx>, Scope)>, storages_alive: bool ) -> BasicBlock

Binds the variables and ascribes types for a given match arm or let binding.

Also check if the guard matches, if it’s provided. arm_scope should be Some if and only if this is called for a match arm.

pub(super) fn expr_into_pattern( &mut self, block: BasicBlock, irrefutable_pat: &Pat<'tcx>, initializer_id: ExprId ) -> BlockAnd<()>

pub(crate) fn place_into_pattern( &mut self, block: BasicBlock, irrefutable_pat: &Pat<'tcx>, initializer: PlaceBuilder<'tcx>, set_match_place: bool ) -> BlockAnd<()>

pub(crate) fn declare_bindings( &mut self, visibility_scope: Option<SourceScope>, scope_span: Span, pattern: &Pat<'tcx>, guard: Option<ExprId>, opt_match_place: Option<(Option<&Place<'tcx>>, Span)> ) -> Option<SourceScope>

Declares the bindings of the given patterns and returns the visibility scope for the bindings in these patterns, if such a scope had to be created. NOTE: Declaring the bindings should always be done in their drop scope.

pub(crate) fn declare_guard_bindings( &mut self, guard_expr: ExprId, scope_span: Span, visibility_scope: Option<SourceScope> )

Declare bindings in a guard. This has to be done when declaring bindings for an arm to ensure that or patterns only have one version of each variable.

pub(crate) fn storage_live_binding( &mut self, block: BasicBlock, var: LocalVarId, span: Span, for_guard: ForGuard, schedule_drop: bool ) -> Place<'tcx>

pub(crate) fn schedule_drop_for_binding( &mut self, var: LocalVarId, span: Span, for_guard: ForGuard )

pub(super) fn visit_primary_bindings( &mut self, pattern: &Pat<'tcx>, pattern_user_ty: UserTypeProjections, f: &mut impl FnMut(&mut Self, Mutability, Symbol, BindingMode, LocalVarId, Span, Ty<'tcx>, UserTypeProjections) )

Visit all of the primary bindings in a patterns, that is, visit the leftmost occurrence of each variable bound in a pattern. A variable will occur more than once in an or-pattern.

impl<'a, 'tcx> Builder<'a, 'tcx>

fn match_candidates<'pat>( &mut self, span: Span, scrutinee_span: Span, start_block: BasicBlock, otherwise_block: BasicBlock, candidates: &mut [&mut Candidate<'pat, 'tcx>] )

The main match algorithm. It begins with a set of candidates candidates and has the job of generating code to determine which of these candidates, if any, is the correct one. The candidates are sorted such that the first item in the list has the highest priority. When a candidate is found to match the value, we will set and generate a branch to the appropriate pre-binding block.

If we find that NONE of the candidates apply, we branch to otherwise_block.

It might be surprising that the input can be non-exhaustive. Indeed, initially, it is not, because all matches are exhaustive in Rust. But during processing we sometimes divide up the list of candidates and recurse with a non-exhaustive list. This is how our lowering approach (called “backtracking automaton” in the literature) works. See Builder::test_candidates for more details.

If fake_borrows is Some, then places which need fake borrows will be added to it.

For an example of how we use otherwise_block, consider:

match (x, y) {
    (true, true) => 1,
    (_, false) => 2,
    (false, true) => 3,
}

For this match, we generate something like:

if x {
    if y {
        return 1
    } else {
        // continue
    }
} else {
    // continue
}
if y {
    if x {
        // This is actually unreachable because the `(true, true)` case was handled above.
        // continue
    } else {
        return 3
    }
} else {
    return 2
}
// this is the final `otherwise_block`, which is unreachable because the match was exhaustive.
unreachable!()

Every continue is an instance of branching to some otherwise_block somewhere deep within the algorithm. For more details on why we lower like this, see Builder::test_candidates.

Note how we test x twice. This is the tradeoff of backtracking automata: we prefer smaller code size at the expense of non-optimal code paths.

fn match_simplified_candidates( &mut self, span: Span, scrutinee_span: Span, start_block: BasicBlock, otherwise_block: BasicBlock, candidates: &mut [&mut Candidate<'_, 'tcx>] )

fn select_matched_candidate( &mut self, candidate: &mut Candidate<'_, 'tcx>, start_block: BasicBlock ) -> BasicBlock

Link up matched candidates.

For example, if we have something like this:

...
Some(x) if cond1 => ...
Some(x) => ...
Some(x) if cond2 => ...
...

We generate real edges from:

• start_block to the pre-binding block of the first pattern,
• the otherwise block of the first pattern to the second pattern,
• the otherwise block of the third pattern to a block with an Unreachable terminator.

In addition, we later add fake edges from the otherwise blocks to the pre-binding block of the next candidate in the original set of candidates.

fn test_candidates_with_or( &mut self, span: Span, scrutinee_span: Span, candidates: &mut [&mut Candidate<'_, 'tcx>], start_block: BasicBlock, otherwise_block: BasicBlock )

Tests a candidate where there are only or-patterns left to test, or forwards to Builder::test_candidates.

Given a pattern (P | Q, R | S) we (in principle) generate a CFG like so:

[ start ]
     |
[ match P, Q ]
     |
     +----------------------------------------+------------------------------------+
     |                                        |                                    |
     V                                        V                                    V
[ P matches ]                           [ Q matches ]                        [ otherwise ]
     |                                        |                                    |
     V                                        V                                    |
[ match R, S ]                          [ match R, S ]                             |
     |                                        |                                    |
     +--------------+------------+            +--------------+------------+        |
     |              |            |            |              |            |        |
     V              V            V            V              V            V        |
[ R matches ] [ S matches ] [otherwise ] [ R matches ] [ S matches ] [otherwise ]  |
     |              |            |            |              |            |        |
     +--------------+------------|------------+--------------+            |        |
     |                           |                                        |        |
     |                           +----------------------------------------+--------+
     |                           |
     V                           V
[ Success ]                 [ Failure ]

In practice there are some complications:

• If there’s a guard, then the otherwise branch of the first match on R | S goes to a test for whether Q matches, and the control flow doesn’t merge into a single success block until after the guard is tested.
• If neither P or Q has any bindings or type ascriptions and there isn’t a match guard, then we create a smaller CFG like:

    ...
     +---------------+------------+
     |               |            |
[ P matches ] [ Q matches ] [ otherwise ]
     |               |            |
     +---------------+            |
     |                           ...
[ match R, S ]
     |
    ...

fn test_or_pattern<'pat>( &mut self, candidate: &mut Candidate<'pat, 'tcx>, start_block: BasicBlock, otherwise_block: BasicBlock, pats: &[FlatPat<'pat, 'tcx>], or_span: Span )

fn merge_trivial_subcandidates( &mut self, candidate: &mut Candidate<'_, 'tcx>, source_info: SourceInfo )

Try to merge all of the subcandidates of the given candidate into one. This avoids exponentially large CFGs in cases like (1 | 2, 3 | 4, ...).

fn pick_test( &mut self, candidates: &mut [&mut Candidate<'_, 'tcx>] ) -> (PlaceBuilder<'tcx>, Test<'tcx>)

Pick a test to run. Which test doesn’t matter as long as it is guaranteed to fully match at least one match pair. We currently simply pick the test corresponding to the first match pair of the first candidate in the list.

Note: taking the first match pair is somewhat arbitrary, and we might do better here by choosing more carefully what to test.

For example, consider the following possible match-pairs:

1. x @ Some(P) – we will do a Switch to decide what variant x has
2. x @ 22 – we will do a SwitchInt to decide what value x has
3. x @ 3..5 – we will do a Range test to decide what range x falls in
4. etc.

fn sort_candidates<'b, 'c, 'pat>( &mut self, match_place: &PlaceBuilder<'tcx>, test: &Test<'tcx>, candidates: &'b mut [&'c mut Candidate<'pat, 'tcx>] ) -> (&'b mut [&'c mut Candidate<'pat, 'tcx>], FxIndexMap<TestBranch<'tcx>, Vec<&'b mut Candidate<'pat, 'tcx>>>)

Given a test, we sort the input candidates into several buckets. If a candidate only matches in one of the branches of test, we move it there. If it could match in more than one of the branches of test, we stop sorting candidates.

This returns a pair of

• the candidates that weren’t sorted;
• for each possible outcome of the test, the candidates that match in that outcome.

Moreover, we transform the branched candidates to reflect the fact that we know which outcome of test occurred.

For example:

match (x, y, z) {
    (true , _    , true ) => true,  // (0)
    (false, false, _    ) => false, // (1)
    (_    , true , _    ) => true,  // (2)
    (true , _    , false) => false, // (3)
}

Assume we are testing on x. There are 2 overlapping candidate sets:

• If the outcome is that x is true, candidates 0, 2, and 3
• If the outcome is that x is false, candidates 1 and 2

Following our algorithm, candidate 0 is sorted into outcome x == true, candidate 1 goes into outcome x == false, and candidate 2 and 3 remain unsorted.

The sorted candidates are transformed:

• candidate 0 becomes [z @ true] since we know that x was true;
• candidate 1 becomes [y @ false] since we know that x was false.

fn test_candidates<'pat, 'b, 'c>( &mut self, span: Span, scrutinee_span: Span, candidates: &'b mut [&'c mut Candidate<'pat, 'tcx>], start_block: BasicBlock, otherwise_block: BasicBlock )

This is the most subtle part of the match lowering algorithm. At this point, the input candidates have been fully simplified, so all remaining match-pairs require some sort of test.

Once we pick what sort of test we are going to perform, this test will help us winnow down our candidates. So we walk over the candidates (from high to low priority) and check. We compute, for each outcome of the test, a transformed list of candidates. If a candidate matches in a single branch of our test, we add it to the corresponding outcome. We also transform it to record the fact that we know which outcome occurred.

For example, if we are testing x.0’s variant, and we have a candidate (x.0 @ Some(v), x.1 @ 22), then we would have a resulting candidate of ((x.0 as Some).0 @ v, x.1 @ 22) in the branch corresponding to Some. To ensure we make progress, we always pick a test that results in simplifying the first candidate.

But there may also be candidates that the test doesn’t apply to. The classical example is wildcards:

match (x, y, z) {
    (true , _    , true ) => true,  // (0)
    (false, false, _    ) => false, // (1)
    (_    , true , _    ) => true,  // (2)
    (true , _    , false) => false, // (3)
}

Here, the traditional “decision tree” method would generate 2 separate code-paths for the 2 possible values of x. This would however duplicate some candidates, which would need to be lowered several times.

In some cases, this duplication can create an exponential amount of code. This is most easily seen by noticing that this method terminates with precisely the reachable arms being reachable - but that problem is trivially NP-complete:

match (var0, var1, var2, var3, ...) {
    (true , _   , _    , false, true, ...) => false,
    (_    , true, true , false, _   , ...) => false,
    (false, _   , false, false, _   , ...) => false,
    ...
    _ => true
}

Here the last arm is reachable only if there is an assignment to the variables that does not match any of the literals. Therefore, compilation would take an exponential amount of time in some cases.

In rustc, we opt instead for the “backtracking automaton” approach. This guarantees we never duplicate a candidate (except in the presence of or-patterns). In fact this guarantee is ensured by the fact that we carry around &mut Candidates which can’t be duplicated.

To make this work, whenever we decide to perform a test, if we encounter a candidate that could match in more than one branch of the test, we stop. We generate code for the test and for the candidates in its branches; the remaining candidates will be tested if the candidates in the branches fail to match.

For example, if we test on x in the following:

match (x, y, z) {
    (true , _    , true ) => 0,
    (false, false, _    ) => 1,
    (_    , true , _    ) => 2,
    (true , _    , false) => 3,
}

this function generates code that looks more of less like:

if x {
    match (y, z) {
        (_, true) => return 0,
        _ => {} // continue matching
    }
} else {
    match (y, z) {
        (false, _) => return 1,
        _ => {} // continue matching
    }
}
// the block here is `remainder_start`
match (x, y, z) {
    (_    , true , _    ) => 2,
    (true , _    , false) => 3,
    _ => unreachable!(),
}

fn calculate_fake_borrows<'b>( &mut self, fake_borrows: &'b FxIndexSet<Place<'tcx>>, temp_span: Span ) -> Vec<(Place<'tcx>, Local)>

Determine the fake borrows that are needed from a set of places that have to be stable across match guards.

Returns a list of places that need a fake borrow and the temporary that’s used to store the fake borrow.

Match exhaustiveness checking is not able to handle the case where the place being matched on is mutated in the guards. We add “fake borrows” to the guards that prevent any mutation of the place being matched. There are a some subtleties:

1. Borrowing *x doesn’t prevent assigning to x. If x is a shared reference, the borrow isn’t even tracked. As such we have to add fake borrows of any prefixes of a place
2. We don’t want match x { _ => (), } to conflict with mutable borrows of x, so we only add fake borrows for places which are bound or tested by the match.
3. We don’t want the fake borrows to conflict with ref mut bindings, so we use a special BorrowKind for them.
4. The fake borrows may be of places in inactive variants, so it would be UB to generate code for them. They therefore have to be removed by a MIR pass run after borrow checking.

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn lower_let_expr( &mut self, block: BasicBlock, expr_id: ExprId, pat: &Pat<'tcx>, source_scope: Option<SourceScope>, span: Span, declare_bindings: bool ) -> BlockAnd<()>

If the bindings have already been declared, set declare_bindings to false to avoid duplicated bindings declaration. Used for if-let guards.

fn bind_and_guard_matched_candidate<'pat>( &mut self, candidate: Candidate<'pat, 'tcx>, parent_data: &[PatternExtraData<'tcx>], fake_borrows: &[(Place<'tcx>, Local)], scrutinee_span: Span, arm_match_scope: Option<(&Arm<'tcx>, Scope)>, schedule_drops: bool, storages_alive: bool ) -> BasicBlock

Initializes each of the bindings from the candidate by moving/copying/ref’ing the source as appropriate. Tests the guard, if any, and then branches to the arm. Returns the block for the case where the guard succeeds.

Note: we do not check earlier that if there is a guard, there cannot be move bindings. We avoid a use-after-move by only moving the binding once the guard has evaluated to true (see below).

fn ascribe_types( &mut self, block: BasicBlock, ascriptions: impl IntoIterator<Item = Ascription<'tcx>> )

Append AscribeUserType statements onto the end of block for each ascription

fn bind_matched_candidate_for_guard<'b>( &mut self, block: BasicBlock, schedule_drops: bool, bindings: impl IntoIterator<Item = &'b Binding<'tcx>> )

where 'tcx: 'b,

fn bind_matched_candidate_for_arm_body<'b>( &mut self, block: BasicBlock, schedule_drops: bool, bindings: impl IntoIterator<Item = &'b Binding<'tcx>>, storages_alive: bool )

where 'tcx: 'b,

fn declare_binding( &mut self, source_info: SourceInfo, visibility_scope: SourceScope, mutability: Mutability, name: Symbol, mode: BindingMode, var_id: LocalVarId, var_ty: Ty<'tcx>, user_ty: UserTypeProjections, has_guard: ArmHasGuard, opt_match_place: Option<(Option<Place<'tcx>>, Span)>, pat_span: Span )

Each binding (ref mut var/ref var/mut var/var, where the bound var has type T in the arm body) in a pattern maps to 2 locals. The first local is a binding for occurrences of var in the guard, which will have type &T. The second local is a binding for occurrences of var in the arm body, which will have type T.

pub(crate) fn ast_let_else( &mut self, block: BasicBlock, init_id: ExprId, initializer_span: Span, else_block: BlockId, let_else_scope: &Scope, pattern: &Pat<'tcx> ) -> BlockAnd<BasicBlock>

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn temp(&mut self, ty: Ty<'tcx>, span: Span) -> Place<'tcx>

Adds a new temporary value of type ty storing the result of evaluating expr.

N.B., No cleanup is scheduled for this temporary. You should call schedule_drop once the temporary is initialized.

pub(crate) fn literal_operand( &mut self, span: Span, const_: Const<'tcx> ) -> Operand<'tcx>

Convenience function for creating a literal operand, one without any user type annotation.

pub(crate) fn zero_literal(&mut self, span: Span, ty: Ty<'tcx>) -> Operand<'tcx>

Returns a zero literal operand for the appropriate type, works for bool, char and integers.

pub(crate) fn push_usize( &mut self, block: BasicBlock, source_info: SourceInfo, value: u64 ) -> Place<'tcx>

pub(crate) fn consume_by_copy_or_move( &self, place: Place<'tcx> ) -> Operand<'tcx>

impl<'a, 'tcx> Builder<'a, 'tcx>

pub(crate) fn in_breakable_scope<F>( &mut self, loop_block: Option<BasicBlock>, break_destination: Place<'tcx>, span: Span, f: F ) -> BlockAnd<()>

where F: FnOnce(&mut Builder<'a, 'tcx>) -> Option<BlockAnd<()>>,

Start a breakable scope, which tracks where continue, break and return should branch to.

pub(crate) fn in_if_then_scope<F>( &mut self, region_scope: Scope, span: Span, f: F ) -> (BasicBlock, BasicBlock)

where F: FnOnce(&mut Builder<'a, 'tcx>) -> BlockAnd<()>,

Start an if-then scope which tracks drop for if expressions and if guards.

For an if-let chain:

if let Some(x) = a && let Some(y) = b && let Some(z) = c { … }

There are three possible ways the condition can be false and we may have to drop x, x and y, or neither depending on which binding fails. To handle this correctly we use a DropTree in a similar way to a loop expression and ‘break’ out on all of the ‘else’ paths.

Notes:

• We don’t need to keep a stack of scopes in the Builder because the ‘else’ paths will only leave the innermost scope.
• This is also used for match guards.

pub(crate) fn in_scope<F, R>( &mut self, region_scope: (Scope, SourceInfo), lint_level: LintLevel, f: F ) -> BlockAnd<R>

where F: FnOnce(&mut Builder<'a, 'tcx>) -> BlockAnd<R>,

Convenience wrapper that pushes a scope and then executes f to build its contents, popping the scope afterwards.

pub(crate) fn push_scope(&mut self, region_scope: (Scope, SourceInfo))

Push a scope onto the stack. You can then build code in this scope and call pop_scope afterwards. Note that these two calls must be paired; using in_scope as a convenience wrapper maybe preferable.

pub(crate) fn pop_scope( &mut self, region_scope: (Scope, SourceInfo), block: BasicBlock ) -> BlockAnd<()>

Pops a scope, which should have region scope region_scope, adding any drops onto the end of block that are needed. This must match 1-to-1 with push_scope.

pub(crate) fn break_scope( &mut self, block: BasicBlock, value: Option<ExprId>, target: BreakableTarget, source_info: SourceInfo ) -> BlockAnd<()>

Sets up the drops for breaking from block to target.

pub(crate) fn break_for_else( &mut self, block: BasicBlock, source_info: SourceInfo )

Sets up the drops for breaking from block due to an if condition that turned out to be false.

Must be called in the context of Builder::in_if_then_scope, so that there is an if-then scope to tell us what the target scope is.

fn leave_top_scope(&mut self, block: BasicBlock) -> BasicBlock

pub(crate) fn maybe_new_source_scope( &mut self, span: Span, safety: Option<Safety>, current_id: HirId, parent_id: HirId )

Possibly creates a new source scope if current_root and parent_root are different, or if -Zmaximal-hir-to-mir-coverage is enabled.

fn maybe_lint_level_root_bounded(&mut self, orig_id: HirId) -> HirId

Walks upwards from orig_id to find a node which might change lint levels with attributes. It stops at self.hir_id and just returns it if reached.

pub(crate) fn new_source_scope( &mut self, span: Span, lint_level: LintLevel, safety: Option<Safety> ) -> SourceScope

Creates a new source scope, nested in the current one.

pub(crate) fn source_info(&self, span: Span) -> SourceInfo

Given a span and the current source scope, make a SourceInfo.

pub(crate) fn local_scope(&self) -> Scope

Returns the scope that we should use as the lifetime of an operand. Basically, an operand must live until it is consumed. This is similar to, but not quite the same as, the temporary scope (which can be larger or smaller).

Consider:

let x = foo(bar(X, Y));

We wish to pop the storage for X and Y after bar() is called, not after the whole let is completed.

As another example, if the second argument diverges:

foo(Box::new(2), panic!())

We would allocate the box but then free it on the unwinding path; we would also emit a free on the ‘success’ path from panic, but that will turn out to be removed as dead-code.

pub(crate) fn schedule_drop_storage_and_value( &mut self, span: Span, region_scope: Scope, local: Local )

pub(crate) fn schedule_drop( &mut self, span: Span, region_scope: Scope, local: Local, drop_kind: DropKind )

Indicates that place should be dropped on exit from region_scope.

When called with DropKind::Storage, place shouldn’t be the return place, or a function parameter.

pub(crate) fn record_operands_moved( &mut self, operands: &[Spanned<Operand<'tcx>>] )

Indicates that the “local operand” stored in local is moved at some point during execution (see local_scope for more information about what a “local operand” is – in short, it’s an intermediate operand created as part of preparing some MIR instruction). We use this information to suppress redundant drops on the non-unwind paths. This results in less MIR, but also avoids spurious borrow check errors (c.f. #64391).

Example: when compiling the call to foo here:

foo(bar(), ...)

we would evaluate bar() to an operand _X. We would also schedule _X to be dropped when the expression scope for foo(bar()) is exited. This is relevant, for example, if the later arguments should unwind (it would ensure that _X gets dropped). However, if no unwind occurs, then _X will be unconditionally consumed by the call:

bb {
  ...
  _R = CALL(foo, _X, ...)
}

However, _X is still registered to be dropped, and so if we do nothing else, we would generate a DROP(_X) that occurs after the call. This will later be optimized out by the drop-elaboration code, but in the meantime it can lead to spurious borrow-check errors – the problem, ironically, is not the DROP(_X) itself, but the (spurious) unwind pathways that it creates. See #64391 for an example.

fn diverge_cleanup(&mut self) -> DropIdx

Returns the DropIdx for the innermost drop if the function unwound at this point. The DropIdx will be created if it doesn’t already exist.

fn diverge_cleanup_target(&mut self, target_scope: Scope, span: Span) -> DropIdx

This is similar to diverge_cleanup except its target is set to some ancestor scope instead of the current scope. It is possible to unwind to some ancestor scope if some drop panics as the program breaks out of a if-then scope.

pub(crate) fn diverge_from(&mut self, start: BasicBlock)

Prepares to create a path that performs all required cleanup for a terminator that can unwind at the given basic block.

This path terminates in Resume. The path isn’t created until after all of the non-unwind paths in this item have been lowered.

pub(crate) fn coroutine_drop_cleanup(&mut self, yield_block: BasicBlock)

Sets up a path that performs all required cleanup for dropping a coroutine, starting from the given block that ends in TerminatorKind::Yield.

This path terminates in CoroutineDrop.

pub(crate) fn build_drop_and_replace( &mut self, block: BasicBlock, span: Span, place: Place<'tcx>, value: Rvalue<'tcx> ) -> BlockAnd<()>

Utility function for non-scope code to build their own drops Force a drop at this point in the MIR by creating a new block.

pub(crate) fn assert( &mut self, block: BasicBlock, cond: Operand<'tcx>, expected: bool, msg: AssertMessage<'tcx>, span: Span ) -> BasicBlock

Creates an Assert terminator and return the success block. If the boolean condition operand is not the expected value, a runtime panic will be caused with the given message.

pub(crate) fn clear_top_scope(&mut self, region_scope: Scope)

Unschedules any drops in the top scope.

This is only needed for match arm scopes, because they have one entrance per pattern, but only one exit.

impl<'a, 'tcx: 'a> Builder<'a, 'tcx>

fn build_exit_tree( &mut self, drops: DropTree, else_scope: Scope, span: Span, continue_block: Option<BasicBlock> ) -> Option<BlockAnd<()>>

Build a drop tree for a breakable scope.

If continue_block is Some, then the tree is for continue inside a loop. Otherwise this is for break or return.

pub(crate) fn build_drop_trees(&mut self)

Build the unwind and coroutine drop trees.

fn build_coroutine_drop_trees(&mut self)

fn build_unwind_tree( cfg: &mut CFG<'tcx>, drops: &mut DropTree, fn_span: Span, resume_block: &mut Option<BasicBlock> )

impl<'a, 'tcx> Builder<'a, 'tcx>

fn is_bound_var_in_guard(&self, id: LocalVarId) -> bool

fn var_local_id(&self, id: LocalVarId, for_guard: ForGuard) -> Local

impl<'a, 'tcx> Builder<'a, 'tcx>

fn new( thir: &'a Thir<'tcx>, infcx: InferCtxt<'tcx>, def: LocalDefId, hir_id: HirId, span: Span, arg_count: usize, safety: Safety, return_ty: Ty<'tcx>, return_span: Span, coroutine: Option<Box<CoroutineInfo<'tcx>>> ) -> Builder<'a, 'tcx>

fn finish(self) -> Body<'tcx>

fn insert_upvar_arg(&mut self)

fn args_and_body( &mut self, block: BasicBlock, arguments: &IndexSlice<ParamId, Param<'tcx>>, argument_scope: Scope, expr_id: ExprId ) -> BlockAnd<()>

fn set_correct_source_scope_for_arg( &mut self, arg_hir_id: HirId, original_source_scope: SourceScope, pattern_span: Span )

fn get_unit_temp(&mut self) -> Place<'tcx>

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 1544 bytes