Region Constraints and Resolution in Rust Type Inference

is to first "generalize" `&'a i32` into a type with a region variable: `&'?b i32`, and then unify `?T` with that (`?T = &'?b i32`). We then relate this new variable with the original bound: ```text &'?b i32 <: &'a i32 ``` This will result in a region constraint (see below) of `'?b: 'a`. One final interesting case is relating two unbound type variables, like `?T <: ?U`. In that case, we can't make progress, so we enqueue an obligation `Subtype(?T, ?U)` and return it via the `InferOk` mechanism. You'll have to try again when more details about `?T` or `?U` are known. ## Region constraints Regions are inferenced somewhat differently from types. Rather than eagerly unifying things, we simply collect constraints as we go, but make (almost) no attempt to solve regions. These constraints have the form of an "outlives" constraint: ```text 'a: 'b ``` Actually the code tends to view them as a subregion relation, but it's the same idea: ```text 'b <= 'a ``` (There are various other kinds of constraints, such as "verifys"; see the [`region_constraints`] module for details.) There is one case where we do some amount of eager unification. If you have an equality constraint between two regions ```text 'a = 'b ``` we will record that fact in a unification table. You can then use [`opportunistic_resolve_var`] to convert `'b` to `'a` (or vice versa). This is sometimes needed to ensure termination of fixed-point algorithms. ## Solving region constraints Region constraints are only solved at the very end of typechecking, once all other constraints are known and all other obligations have been proven. There are two ways to solve region constraints right now: lexical and non-lexical. Eventually there will only be one. An exception here is the leak-check which is used during trait solving and relies on region constraints containing higher-ranked regions. Region constraints in the root universe (i.e. not arising from a `for<'a>`) must not influence the trait system, as these regions are all erased during codegen. To solve **lexical** region constraints, you invoke [`resolve_regions_and_report_errors`]. This "closes" the region constraint process and invokes the [`lexical_region_resolve`] code. Once this is done, any further attempt to equate or create a subtyping relationship will yield an ICE. The NLL solver (actually, the MIR type-checker) does things slightly differently. It uses canonical queries for trait solving which use [`take_and_reset_region_constraints`] at the end. This extracts all of the outlives constraints added during the canonical query. This is required as the NLL solver must not only know *what* regions outlive each other, but also *where*. Finally, the NLL solver invokes [`take_region_var_origins`], providing all region variables to the solver. ## Lexical region resolution Lexical region resolution is done by initially assigning each region variable to an empty value. We then process each outlives constraint repeatedly, growing region variables until a fixed-point is reached. Region variables can be grown using a least-upper-bound relation on the region lattice in a fairly straightforward fashion.

This section details how region constraints are handled differently from types in Rust's type inference. It describes the process of collecting constraints without eager unification, focusing on 'outlives' relationships. It highlights an exception for equality constraints between regions, where unification tables are used to record the equivalence. The section further explains how region constraints are solved at the end of typechecking using either lexical or non-lexical methods. It touches on leak-check during trait solving. Finally, the section describes the process of Lexical region resolution: initially assigning each region variable to an empty value and then growing region variables until a fixed-point is reached.