---
# System prepended metadata

title: '# t-types standing design meeting 2023-07-03: scopes in the polonius model'

---


### Goals and plan

- present some light background material on the borrow-checking code, NLL
- show the NLL scope computation (from a few weeks back), explain what needs to change to use the polonius model
- go over [PR #113218](https://github.com/rust-lang/rust/pull/113218) implementing that change

### Background

1. The root of borrowck, [`do_mir_borrowck`](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/lib.rs#L159): a bunch of sequential steps
2. Of interest today, some of the code path emitting errors:
    a. setting up some [dataflow computations](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/lib.rs#L288-L300) (we'll come back to `flow_borrows`)
    b. heavy lifting: done by [visiting dataflow results](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/lib.rs#L379-L385)
3. Most relevant path today: checking accesses to places [`access_place`](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/lib.rs#L974). In particular, ending up in [`check_access_for_conflict`]() to emit errors.
4. Key point: looking at the set of ["borrows in scopes"](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/lib.rs#L1043) to ensure there are no conflicting borrows that would prevent the access. `flow_borrows` from above.
5. [`Borrows` dataflow computation](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/dataflow.rs#L589-L690). gen/kill analysis to compute borrows in scope
    * [gen new borrows](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/dataflow.rs#L616-L630) on borrow expressions
    * [kill borrows on locals](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/dataflow.rs#L631-L641): going out of lexical scope, being overwritten
    * and, of interest today: [kill borrows going out of NLL scope](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/dataflow.rs#L510-L532)
6. The map of `BorrowIndex`es going out of scope at each location is [precomputed](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/dataflow.rs#L225-L240), by the NLL `OutOfScopePrecomputer`, currently [here](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/dataflow.rs#L129-L223).
7. It's been refactored in the last few weeks. However, my PR was started before that, and I haven't had time to look into the new one, so the PR matches the structure from the previous versions: [`precompute_borrows_out_of_scope`, as the basis of my changes](https://github.com/lqd/rust/blob/eaddc3707520988f8bc2d267cb192d2f0c63ee80/compiler/rustc_borrowck/src/dataflow.rs#L155-L231).
8. For each borrow, walk the CFG (with some subtletly about cycles, we don't need to worry about it) starting at the point where it was introduced: check if the CFG point [is contained within the region](https://github.com/lqd/rust/blob/eaddc3707520988f8bc2d267cb192d2f0c63ee80/compiler/rustc_borrowck/src/dataflow.rs#L186), if not, the borrow goes out of scope.
9. Key point: *regions as sets of points*. This is the thing we want to change.

### PR #113218 

(a bunch of `-Z` flag work that we can ignore to introduce `-Zpolonius=next`)

`-Zpolonius=next` [enables the new computation, and asserts that it computes the same results as before](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/dataflow.rs#L476-L501).

Switch from NLL `OutOfScopePrecomputer` to `PoloniusOutOfScopePrecomputer`: 
- from set-of-points: check whether the region contains a point.
- to set-of-loans: check whether the loan is live at that point. A loan is live if it's contained within a live region. In the location-insensitive analysis, a region contains a loan, if it's outlived by the region that issued it. The PR is about reachability.

We'll want:
- SCCs reachable from a given borrow region
- SCCs are live at a point

Some common data:
- [SCCs live at all points](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/dataflow.rs#L271-L290)
- liveness data in shape better suited to the computation, [live SCCs per point](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/dataflow.rs#L291-L305)

The dual function to NLL precomputer is `precompute_loans_out_of_scope`:
1. starts with precomputing the [reachability of the region](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/dataflow.rs#L330-L373) whose scope we're computing
    * SCCs live at all points
    * member constraints
        * these loans escape the current function, and can't go out of scope
    * regular outlives constraints 

2. CFG walk (exactly like the previous `precompute_borrows_out_of_scope`  we saw earlier)
    * [can the issuing region reach a live region at the point ?](https://github.com/lqd/rust/blob/c14a38cf7a76d20d87a967d6cf2a409b2c1d3414/compiler/rustc_borrowck/src/dataflow.rs#L398-L419)
    * if not, the loan goes out of scope here


---

### Thoughts, questions

#### How do I leave a question?

ferris: How do I leave a question?

Like this! Make a new section, summarize, and then give details