struct Builder<'a, 'tcx> {
Show 26 fields tcx: TyCtxt<'tcx>, infcx: InferCtxt<'a, 'tcx>, typeck_results: &'tcx TypeckResults<'tcx>, region_scope_tree: &'tcx ScopeTree, param_env: ParamEnv<'tcx>, thir: &'a Thir<'tcx>, cfg: CFG<'tcx>, def_id: DefId, hir_id: HirId, parent_module: DefId, check_overflow: bool, fn_span: Span, arg_count: usize, generator_kind: Option<GeneratorKind>, scopes: Scopes<'tcx>, block_context: BlockContext, in_scope_unsafe: Safety, source_scopes: IndexVec<SourceScope, SourceScopeData<'tcx>>, source_scope: SourceScope, guard_context: Vec<GuardFrame>, 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>>,
}

Fields

tcx: TyCtxt<'tcx>infcx: InferCtxt<'a, 'tcx>typeck_results: &'tcx TypeckResults<'tcx>region_scope_tree: &'tcx ScopeTreeparam_env: ParamEnv<'tcx>thir: &'a Thir<'tcx>cfg: CFG<'tcx>def_id: DefIdhir_id: HirIdparent_module: DefIdcheck_overflow: boolfn_span: Spanarg_count: usizegenerator_kind: Option<GeneratorKind>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: SourceScopeguard_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.

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>>

Implementations

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

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

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.

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 #68034 for more details.

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.

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.

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.

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.

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.

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.

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.

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.

Compile expr, yielding an rvalue.

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

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

Builds a block of MIR statements to evaluate the THIR expr. If the original expression was an AST statement, (e.g., some().code(&here());) then opt_stmt_span is the span of that statement (including its semicolon, if any). The scope is used if a statement temporary must be dropped.

Simplify a candidate so that all match pairs require a test.

This method will also split a candidate, in which the only match-pair is an or-pattern, into multiple candidates. This is so that

match x { 0 | 1 => { … }, 2 | 3 => { … }, }

only generates a single switch. If this happens this method returns true.

Given candidate that has a single or-pattern for its match-pairs, creates a fresh candidate for each of its input subpatterns passed via pats.

Tries to simplify match_pair, returning Ok(()) if successful. If successful, new match pairs and bindings will have been pushed into the candidate. If no simplification is possible, Err is returned and no changes are made to candidate.

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.

Compare using the provided built-in comparison operator

Compare two &T values using <T as std::compare::PartialEq>::eq

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 returned index is the index that this candidate should be placed in the target_candidates vec. 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 what value x has 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.

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.

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) ]
[ (fake read 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 fake read 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.

Evaluate the scrutinee and add the fake read of it.

Create the initial Candidates for a match expression.

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.

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.

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.

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.

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.

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 the otherwise_block, setting it to Some if required. In principle, this means that the input list was not exhaustive, though at present we sometimes are not smart enough to recognize all exhaustive inputs.

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 important to keep the size of the generated code under control. 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 a case where we set otherwise_block, even for an exhaustive match, consider:

match x {
    (true, true) => (),
    (_, false) => (),
    (false, true) => (),
}

For this match, we check if x.0 matches true (for the first arm). If it doesn’t match, we check x.1. If x.1 is true we check if x.0 matches false (for the third arm). In the (impossible at runtime) case when x.0 is now true, we branch to otherwise_block.

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:

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

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 ]
     |
    ...

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, ...).

This is the most subtle part of the matching algorithm. At this point, the input candidates have been fully simplified, and so we know that all remaining match-pairs require some sort of test. To decide what test to perform, we take the highest priority candidate (the first one in the list, as of January 2021) and extract the first match-pair from the list. From this we decide what kind of test is needed using Builder::test, defined in the test module.

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.

Once we know what sort of test we are going to perform, this test may also help us winnow down our candidates. So we walk over the candidates (from high to low priority) and check. This gives us, for each outcome of the test, a transformed list of candidates. 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). Note that the first match-pair is now simpler (and, in fact, irrefutable).

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

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

In that case, after we test on x, there are 2 overlapping candidate sets:

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

Here, the traditional “decision tree” method would generate 2 separate code-paths for the 2 separate cases.

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.

That kind of exponential worst-case might not occur in practice, but our simplistic treatment of constants and guards would make it occur in very common situations - for example #29740:

match x {
    "foo" if foo_guard => ...,
    "bar" if bar_guard => ...,
    "baz" if baz_guard => ...,
    ...
}

Here we first test the match-pair x @ "foo", which is an Eq test.

It might seem that we would end up with 2 disjoint candidate sets, consisting of the first candidate or the other two, but our algorithm doesn’t reason about "foo" being distinct from the other constants; it considers the latter arms to potentially match after both outcomes, which obviously leads to an exponential number of tests.

To avoid these kinds of problems, our algorithm tries to ensure the amount of generated tests is linear. When we do a k-way test, we return an additional “unmatched” set alongside the obvious k sets. When we encounter a candidate that would be present in more than one of the sets, we put it and all candidates below it into the “unmatched” set. This ensures these k+1 sets are disjoint.

After we perform our test, we branch into the appropriate candidate set and recurse with match_candidates. These sub-matches are obviously non-exhaustive - as we discarded our otherwise set - so we set their continuation to do match_candidates on the “unmatched” set (which is again non-exhaustive).

If you apply this to the above test, you basically wind up with an if-else-if chain, testing each candidate in turn, which is precisely what we want.

In addition to avoiding exponential-time blowups, this algorithm also has the nice property that each guard and arm is only generated once.

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.

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).

Append AscribeUserType statements onto the end of block for each ascription

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.

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.

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

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.

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

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.

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.

Sets up the drops for breaking from block to target.

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

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

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.

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.

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.

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.

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.

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

This path terminates in GeneratorDrop.

Utility function for non-scope code to build their own drops

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.

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.

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.

Build the unwind and generator drop trees.

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion.

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: 1392 bytes