src/doc/rustc-dev-guide/src/borrow_check/region_inference/lifetime_parameters.md

   1 # Universal regions
   2
   3 "Universal regions" is the name that the code uses to refer to "named
   4 lifetimes" -- e.g., lifetime parameters and `'static`. The name
   5 derives from the fact that such lifetimes are "universally quantified"
   6 (i.e., we must make sure the code is true for all values of those
   7 lifetimes). It is worth spending a bit of discussing how lifetime
   8 parameters are handled during region inference. Consider this example:
   9
  10 ```rust,ignore
  11 fn foo<'a, 'b>(x: &'a u32, y: &'b u32) -> &'b u32 {
  12   x
  13 }
  14 ```
  15
  16 This example is intended not to compile, because we are returning `x`,
  17 which has type `&'a u32`, but our signature promises that we will
  18 return a `&'b u32` value. But how are lifetimes like `'a` and `'b`
  19 integrated into region inference, and how this error wind up being
  20 detected?
  21
  22 ## Universal regions and their relationships to one another
  23
  24 Early on in region inference, one of the first things we do is to
  25 construct a [`UniversalRegions`] struct. This struct tracks the
  26 various universal regions in scope on a particular function.  We also
  27 create a [`UniversalRegionRelations`] struct, which tracks their
  28 relationships to one another. So if you have e.g. `where 'a: 'b`, then
  29 the [`UniversalRegionRelations`] struct would track that `'a: 'b` is
  30 known to hold (which could be tested with the [`outlives`] function.
  31
  32 [`UniversalRegions`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/borrow_check/universal_regions/struct.UniversalRegions.html
  33 [`UniversalRegionRelations`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/borrow_check/type_check/free_region_relations/struct.UniversalRegionRelations.html
  34 [`outlives`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/borrow_check/type_check/free_region_relations/struct.UniversalRegionRelations.html#method.outlives
  35
  36 ## Everything is a region variable
  37
  38 One important aspect of how NLL region inference works is that **all
  39 lifetimes** are represented as numbered variables. This means that the
  40 only variant of [`ty::RegionKind`] that we use is the [`ReVar`]
  41 variant. These region variables are broken into two major categories,
  42 based on their index:
  43
  44 [`ty::RegionKind`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/enum.RegionKind.html
  45 [`ReVar`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/enum.RegionKind.html#variant.ReVar
  46
  47 - 0..N: universal regions -- the ones we are discussing here. In this
  48   case, the code must be correct with respect to any value of those
  49   variables that meets the declared relationships.
  50 - N..M: existential regions -- inference variables where the region
  51   inferencer is tasked with finding *some* suitable value.
  52
  53 In fact, the universal regions can be further subdivided based on
  54 where they were brought into scope (see the [`RegionClassification`]
  55 type). These subdivisions are not important for the topics discussed
  56 here, but become important when we consider [closure constraint
  57 propagation](./closure_constraints.html), so we discuss them there.
  58
  59 [`RegionClassification`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/borrow_check/universal_regions/enum.RegionClassification.html#variant.Local
  60
  61 ## Universal lifetimes as the elements of a region's value
  62
  63 As noted previously, the value that we infer for each region is a set
  64 `{E}`. The elements of this set can be points in the control-flow
  65 graph, but they can also be an element `end('a)` corresponding to each
  66 universal lifetime `'a`. If the value for some region `R0` includes
  67 `end('a`), then this implies that `R0` must extend until the end of `'a`
  68 in the caller.
  69
  70 ## The "value" of a universal region
  71
  72 During region inference, we compute a value for each universal region
  73 in the same way as we compute values for other regions. This value
  74 represents, effectively, the **lower bound** on that universal region
  75 -- the things that it must outlive. We now describe how we use this
  76 value to check for errors.
  77
  78 ## Liveness and universal regions
  79
  80 All universal regions have an initial liveness constraint that
  81 includes the entire function body. This is because lifetime parameters
  82 are defined in the caller and must include the entirety of the
  83 function call that invokes this particular function. In addition, each
  84 universal region `'a` includes itself (that is, `end('a)`) in its
  85 liveness constraint (i.e., `'a` must extend until the end of
  86 itself). In the code, these liveness constraints are setup in
  87 [`init_free_and_bound_regions`].
  88
  89 [`init_free_and_bound_regions`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/borrow_check/region_infer/struct.RegionInferenceContext.html#method.init_free_and_bound_regions
  90
  91 ## Propagating outlives constraints for universal regions
  92
  93 So, consider the first example of this section:
  94
  95 ```rust,ignore
  96 fn foo<'a, 'b>(x: &'a u32, y: &'b u32) -> &'b u32 {
  97   x
  98 }
  99 ```
 100
 101 Here, returning `x` requires that `&'a u32 <: &'b u32`, which gives
 102 rise to an outlives constraint `'a: 'b`. Combined with our default liveness
 103 constraints we get:
 104
 105 ```txt
 106 'a live at {B, end('a)} // B represents the "function body"
 107 'b live at {B, end('b)}
 108 'a: 'b
 109 ```
 110
 111 When we process the `'a: 'b` constraint, therefore, we will add
 112 `end('b)` into the value for `'a`, resulting in a final value of `{B,
 113 end('a), end('b)}`.
 114
 115 ## Detecting errors
 116
 117 Once we have finished constraint propagation, we then enforce a
 118 constraint that if some universal region `'a` includes an element
 119 `end('b)`, then `'a: 'b` must be declared in the function's bounds. If
 120 not, as in our example, that is an error. This check is done in the
 121 [`check_universal_regions`] function, which simply iterates over all
 122 universal regions, inspects their final value, and tests against the
 123 declared [`UniversalRegionRelations`].
 124
 125 [`check_universal_regions`]: https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/borrow_check/region_infer/struct.RegionInferenceContext.html#method.check_universal_regions