src/librustc/infer/lexical_region_resolve/README.md

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