Finding the Minimal Choice: Upper Bounds and the Reverse SCC Graph

i.e., that `'0` must be larger than. In fact, when it comes time to apply member constraints, we've already *computed* the lower bounds of `'0` because we computed its minimal value (or at least, the lower bounds considering everything but member constraints). Let `LB` be the current value of `'0`. We know then that `'0: LB` must hold, whatever the final value of `'0` is. Therefore, we can rule out any choice `'choice` where `'choice: LB` does not hold. Unfortunately, in our example, this is not very helpful. The lower bound for `'0` will just be the liveness set `{L}`, and we know that all the lifetime parameters outlive that set. So we are left with the same set of choices here. (But in other examples, particularly those with different variance, lower bound constraints may be relevant.) ### Upper bounds The *upper bounds* are those lifetimes that *must outlive* `'0` -- i.e., that `'0` must be *smaller* than. In our example, this would be `'a`, because we have the constraint that `'a: '0`. In more complex examples, the chain may be more indirect. We can use upper bounds to rule out members in a very similar way to lower bounds. If UB is some upper bound, then we know that `UB: '0` must hold, so we can rule out any choice `'choice` where `UB: 'choice` does not hold. In our example, we would be able to reduce our choice set from `['a, 'b, 'static]` to just `['a]`. This is because `'0` has an upper bound of `'a`, and neither `'a: 'b` nor `'a: 'static` is known to hold. (For notes on how we collect upper bounds in the implementation, see [the section below](#collecting).) ### Minimal choice After applying lower and upper bounds, we can still sometimes have multiple possibilities. For example, imagine a variant of our example using types with the opposite variance. In that case, we would have the constraint `'0: 'a` instead of `'a: '0`. Hence the current value of `'0` would be `{L, 'a}`. Using this as a lower bound, we would be able to narrow down the member choices to `['a, 'static]` because `'b: 'a` is not known to hold (but `'a: 'a` and `'static: 'a` do hold). We would not have any upper bounds, so that would be our final set of choices. In that case, we apply the **minimal choice** rule -- basically, if one of our choices if smaller than the others, we can use that. In this case, we would opt for `'a` (and not `'static`). This choice is consistent with the general 'flow' of region propagation, which always aims to compute a minimal value for the region being inferred. However, it is somewhat arbitrary. <a id="collecting"></a> ### Collecting upper bounds in the implementation In practice, computing upper bounds is a bit inconvenient, because our data structures are setup for the opposite. What we do is to compute the **reverse SCC graph** (we do this lazily and cache the result) -- that is, a graph where `'a: 'b` induces an edge `SCC('b) -> SCC('a)`. Like the normal SCC graph, this is a DAG. We can then do a depth-first search starting from `SCC('0)` in this graph. This will take us to all the SCCs that must outlive `'0`. One wrinkle is that, as we walk the "upper bound" SCCs, their values will not yet have been fully computed. However, we **have** already applied their liveness constraints, so we have some information about their value. In particular, for any regions representing lifetime parameters, their value will contain themselves (i.e., the initial value for `'a` includes `'a` and the value for `'b` contains `'b`). So we can collect all of the lifetime parameters that are reachable, which is precisely what we are interested in.

Upper bounds are used to further narrow down the choices in a member constraint by ruling out any choice that doesn't outlive the upper bound. After applying both lower and upper bounds, the algorithm selects the minimal choice, preferring smaller lifetimes when multiple possibilities remain. Collecting upper bounds involves computing a reverse SCC graph and performing a depth-first search to find all SCCs that must outlive the region in question. The algorithm accounts for partially computed values during the search, leveraging the liveness constraints already applied.