Region Elements, Constraints, and Inference Overview

For each region we maintain a set storing what elements are present in its value (to make this efficient, we give each kind of element an index, the `RegionElementIndex`, and use sparse bitsets). The kinds of region elements are as follows: - Each **[`location`]** in the MIR control-flow graph: a location is just the pair of a basic block and an index. This identifies the point **on entry** to the statement with that index (or the terminator, if the index is equal to `statements.len()`). - There is an element `end('a)` for each universal region `'a`, corresponding to some portion of the caller's (or caller's caller, etc) control-flow graph. - Similarly, there is an element denoted `end('static)` corresponding to the remainder of program execution after this function returns. - There is an element `!1` for each placeholder region `!1`. This corresponds (intuitively) to some unknown set of other elements – for details on placeholders, see the section [placeholders and universes](region_inference/placeholders_and_universes.md). ## Constraints Before we can infer the value of regions, we need to collect constraints on the regions. The full set of constraints is described in [the section on constraint propagation][cp], but the two most common sorts of constraints are: 1. Outlives constraints. These are constraints that one region outlives another (e.g. `'a: 'b`). Outlives constraints are generated by the [MIR type checker]. 2. Liveness constraints. Each region needs to be live at points where it can be used. ## Inference Overview So how do we compute the contents of a region? This process is called _region inference_. The high-level idea is pretty simple, but there are some details we need to take care of. Here is the high-level idea: we start off each region with the MIR locations we know must be in it from the liveness constraints. From there, we use all of the outlives constraints computed from the type checker to _propagate_ the constraints: for each region `'a`, if `'a: 'b`, then we add all elements of `'b` to `'a`, including `end('b)`. This all happens in [`propagate_constraints`]. Then, we will check for errors. We first check that type tests are satisfied by calling [`check_type_tests`]. This checks constraints like `T: 'a`. Second, we check that universal regions are not "too big". This is done by calling [`check_universal_regions`]. This checks that for each region `'a` if `'a` contains the element `end('b)`, then we must already know that `'a: 'b` holds (e.g. from a where clause). If we don't already know this, that is an error... well, almost. There is some special handling for closures that we will discuss

This section details the kinds of region elements, which include MIR locations, the end of universal regions, the end of 'static, and placeholder regions. It then describes constraints on regions, specifically outlives constraints (generated by the MIR type checker) and liveness constraints. Finally, it provides an overview of region inference, where regions start with locations from liveness constraints, and outlives constraints are used to propagate elements. Error checking involves type tests and ensuring universal regions aren't too large, with special handling for closures.