src/librustc/infer/lexical_region_resolve/README.md

   1 # Region inference
   2
   3 > WARNING: This README is obsolete and will be removed soon! For
   4 > more info on how the current borrowck works, see the [rustc guide].
   5
   6 [rustc guide]: https://rust-lang.github.io/rustc-guide/mir/borrowck.html
   7
   8 ## Terminology
   9
  10 Note that we use the terms region and lifetime interchangeably.
  11
  12 ## Introduction
  13
  14 Region inference uses a somewhat more involved algorithm than type
  15 inference. It is not the most efficient thing ever written though it
  16 seems to work well enough in practice (famous last words).  The reason
  17 that we use a different algorithm is because, unlike with types, it is
  18 impractical to hand-annotate with regions (in some cases, there aren't
  19 even the requisite syntactic forms).  So we have to get it right, and
  20 it's worth spending more time on a more involved analysis.  Moreover,
  21 regions are a simpler case than types: they don't have aggregate
  22 structure, for example.
  23
  24 ## The problem
  25
  26 Basically our input is a directed graph where nodes can be divided
  27 into two categories: region variables and concrete regions.  Each edge
  28 `R -> S` in the graph represents a constraint that the region `R` is a
  29 subregion of the region `S`.
  30
  31 Region variable nodes can have arbitrary degree.  There is one region
  32 variable node per region variable.
  33
  34 Each concrete region node is associated with some, well, concrete
  35 region: e.g., a free lifetime, or the region for a particular scope.
  36 Note that there may be more than one concrete region node for a
  37 particular region value.  Moreover, because of how the graph is built,
  38 we know that all concrete region nodes have either in-degree 1 or
  39 out-degree 1.
  40
  41 Before resolution begins, we build up the constraints in a hashmap
  42 that maps `Constraint` keys to spans.  During resolution, we construct
  43 the actual `Graph` structure that we describe here.
  44
  45 ## Computing the values for region variables
  46
  47 The algorithm is a simple dataflow algorithm. Each region variable
  48 begins as empty. We iterate over the constraints, and for each constraint
  49 we grow the relevant region variable to be as big as it must be to meet all the
  50 constraints. This means the region variables can grow to be `'static` if
  51 necessary.
  52
  53 ## Verification
  54
  55 After all constraints are fully propoagated, we do a "verification"
  56 step where we walk over the verify bounds and check that they are
  57 satisfied. These bounds represent the "maximal" values that a region
  58 variable can take on, basically.
  59
  60 ## The Region Hierarchy
  61
  62 ### Without closures
  63
  64 Let's first consider the region hierarchy without thinking about
  65 closures, because they add a lot of complications. The region
  66 hierarchy *basically* mirrors the lexical structure of the code.
  67 There is a region for every piece of 'evaluation' that occurs, meaning
  68 every expression, block, and pattern (patterns are considered to
  69 "execute" by testing the value they are applied to and creating any
  70 relevant bindings).  So, for example:
  71
  72 ```rust
  73 fn foo(x: isize, y: isize) { // -+
  74 //  +------------+           //  |
  75 //  |      +-----+           //  |
  76 //  |  +-+ +-+ +-+           //  |
  77 //  |  | | | | | |           //  |
  78 //  v  v v v v v v           //  |
  79     let z = x + y;           //  |
  80     ...                      //  |
  81 }                            // -+
  82
  83 fn bar() { ... }
  84 ```
  85
  86 In this example, there is a region for the fn body block as a whole,
  87 and then a subregion for the declaration of the local variable.
  88 Within that, there are sublifetimes for the assignment pattern and
  89 also the expression `x + y`. The expression itself has sublifetimes
  90 for evaluating `x` and `y`.
  91
  92 #s## Function calls
  93
  94 Function calls are a bit tricky. I will describe how we handle them
  95 *now* and then a bit about how we can improve them (Issue #6268).
  96
  97 Consider a function call like `func(expr1, expr2)`, where `func`,
  98 `arg1`, and `arg2` are all arbitrary expressions. Currently,
  99 we construct a region hierarchy like:
 100
 101     +----------------+
 102     |                |
 103     +--+ +---+  +---+|
 104     v  v v   v  v   vv
 105     func(expr1, expr2)
 106
 107 Here you can see that the call as a whole has a region and the
 108 function plus arguments are subregions of that. As a side-effect of
 109 this, we get a lot of spurious errors around nested calls, in
 110 particular when combined with `&mut` functions. For example, a call
 111 like this one
 112
 113 ```rust
 114 self.foo(self.bar())
 115 ```
 116
 117 where both `foo` and `bar` are `&mut self` functions will always yield
 118 an error.
 119
 120 Here is a more involved example (which is safe) so we can see what's
 121 going on:
 122
 123 ```rust
 124 struct Foo { f: usize, g: usize }
 125 // ...
 126 fn add(p: &mut usize, v: usize) {
 127     *p += v;
 128 }
 129 // ...
 130 fn inc(p: &mut usize) -> usize {
 131     *p += 1; *p
 132 }
 133 fn weird() {
 134     let mut x: Box<Foo> = box Foo { /* ... */ };
 135     'a: add(&mut (*x).f,
 136             'b: inc(&mut (*x).f)) // (..)
 137 }
 138 ```
 139
 140 The important part is the line marked `(..)` which contains a call to
 141 `add()`. The first argument is a mutable borrow of the field `f`.  The
 142 second argument also borrows the field `f`. Now, in the current borrow
 143 checker, the first borrow is given the lifetime of the call to
 144 `add()`, `'a`.  The second borrow is given the lifetime of `'b` of the
 145 call to `inc()`. Because `'b` is considered to be a sublifetime of
 146 `'a`, an error is reported since there are two co-existing mutable
 147 borrows of the same data.
 148
 149 However, if we were to examine the lifetimes a bit more carefully, we
 150 can see that this error is unnecessary. Let's examine the lifetimes
 151 involved with `'a` in detail. We'll break apart all the steps involved
 152 in a call expression:
 153
 154 ```rust
 155 'a: {
 156     'a_arg1: let a_temp1: ... = add;
 157     'a_arg2: let a_temp2: &'a mut usize = &'a mut (*x).f;
 158     'a_arg3: let a_temp3: usize = {
 159         let b_temp1: ... = inc;
 160         let b_temp2: &'b = &'b mut (*x).f;
 161         'b_call: b_temp1(b_temp2)
 162     };
 163     'a_call: a_temp1(a_temp2, a_temp3) // (**)
 164 }
 165 ```
 166
 167 Here we see that the lifetime `'a` includes a number of substatements.
 168 In particular, there is this lifetime I've called `'a_call` that
 169 corresponds to the *actual execution of the function `add()`*, after
 170 all arguments have been evaluated. There is a corresponding lifetime
 171 `'b_call` for the execution of `inc()`. If we wanted to be precise
 172 about it, the lifetime of the two borrows should be `'a_call` and
 173 `'b_call` respectively, since the references that were created
 174 will not be dereferenced except during the execution itself.
 175
 176 However, this model by itself is not sound. The reason is that
 177 while the two references that are created will never be used
 178 simultaneously, it is still true that the first reference is
 179 *created* before the second argument is evaluated, and so even though
 180 it will not be *dereferenced* during the evaluation of the second
 181 argument, it can still be *invalidated* by that evaluation. Consider
 182 this similar but unsound example:
 183
 184 ```rust
 185 struct Foo { f: usize, g: usize }
 186 // ...
 187 fn add(p: &mut usize, v: usize) {
 188     *p += v;
 189 }
 190 // ...
 191 fn consume(x: Box<Foo>) -> usize {
 192     x.f + x.g
 193 }
 194 fn weird() {
 195     let mut x: Box<Foo> = box Foo { ... };
 196     'a: add(&mut (*x).f, consume(x)) // (..)
 197 }
 198 ```
 199
 200 In this case, the second argument to `add` actually consumes `x`, thus
 201 invalidating the first argument.
 202
 203 So, for now, we exclude the `call` lifetimes from our model.
 204 Eventually I would like to include them, but we will have to make the
 205 borrow checker handle this situation correctly. In particular, if
 206 there is a reference created whose lifetime does not enclose
 207 the borrow expression, we must issue sufficient restrictions to ensure
 208 that the pointee remains valid.
 209
 210 ### Modeling closures
 211
 212 Integrating closures properly into the model is a bit of
 213 work-in-progress. In an ideal world, we would model closures as
 214 closely as possible after their desugared equivalents. That is, a
 215 closure type would be modeled as a struct, and the region hierarchy of
 216 different closure bodies would be completely distinct from all other
 217 fns. We are generally moving in that direction but there are
 218 complications in terms of the implementation.
 219
 220 In practice what we currently do is somewhat different. The basis for
 221 the current approach is the observation that the only time that
 222 regions from distinct fn bodies interact with one another is through
 223 an upvar or the type of a fn parameter (since closures live in the fn
 224 body namespace, they can in fact have fn parameters whose types
 225 include regions from the surrounding fn body). For these cases, there
 226 are separate mechanisms which ensure that the regions that appear in
 227 upvars/parameters outlive the dynamic extent of each call to the
 228 closure:
 229
 230 1. Types must outlive the region of any expression where they are used.
 231    For a closure type `C` to outlive a region `'r`, that implies that the
 232    types of all its upvars must outlive `'r`.
 233 2. Parameters must outlive the region of any fn that they are passed to.
 234
 235 Therefore, we can -- sort of -- assume that any region from an
 236 enclosing fns is larger than any region from one of its enclosed
 237 fn. And that is precisely what we do: when building the region
 238 hierarchy, each region lives in its own distinct subtree, but if we
 239 are asked to compute the `LUB(r1, r2)` of two regions, and those
 240 regions are in disjoint subtrees, we compare the lexical nesting of
 241 the two regions.
 242
 243 *Ideas for improving the situation:* (FIXME #3696) The correctness
 244 argument here is subtle and a bit hand-wavy. The ideal, as stated
 245 earlier, would be to model things in such a way that it corresponds
 246 more closely to the desugared code. The best approach for doing this
 247 is a bit unclear: it may in fact be possible to *actually* desugar
 248 before we start, but I don't think so. The main option that I've been
 249 thinking through is imposing a "view shift" as we enter the fn body,
 250 so that regions appearing in the types of fn parameters and upvars are
 251 translated from being regions in the outer fn into free region
 252 parameters, just as they would be if we applied the desugaring. The
 253 challenge here is that type inference may not have fully run, so the
 254 types may not be fully known: we could probably do this translation
 255 lazilly, as type variables are instantiated. We would also have to
 256 apply a kind of inverse translation to the return value. This would be
 257 a good idea anyway, as right now it is possible for free regions
 258 instantiated within the closure to leak into the parent: this
 259 currently leads to type errors, since those regions cannot outlive any
 260 expressions within the parent hierarchy. Much like the current
 261 handling of closures, there are no known cases where this leads to a
 262 type-checking accepting incorrect code (though it sometimes rejects
 263 what might be considered correct code; see rust-lang/rust#22557), but
 264 it still doesn't feel like the right approach.