Lambda crabs (part 2): Region inference is (not) magic.
This post will cover region (lifetime) inference with a mathematical and type theoretical focus.
The problem
Inference is a very handy concept. We no longer have to annotate redundant types, which is a major pain point in languages, that lacks of type inference.
Now, we want such an inference scheme for regions as well.
We described the problem of region inference in last post as:
So, this is just a classical optimization problem:
minimize 'a
subject to A, B, C...
A, B, C… are outlives relations. ‘a may or may not be free in those.
Namely, we want to minimize some lifetimes, while holding some conditions.
“Adding” regions
One thing we will use throughout the region inference algorithm is the notion of “adding” regions.
You may have seen 'a + 'b
before. Intuitively, 'a: 'b + 'c
is equivalent to
'a: 'b, 'a: 'c
, but we can go further and use 'a + 'b
as a way to construct
new regions:
Define 'a + 'b
as the smallest region that outlives both 'a
and 'b
.
In a sense, you “widen” the region until it covers both regions:
'a: II
'b: II
'a + 'b: II
Funky but useless: Regions under addition as an abelian semigroup
A semigroup is an algebraic structure satisfying two properties:
 Closure, for any a, b in S, a + b is contained in S.
 Associativity, for any a, b, and c in S, (a + b) + c = a + (b + c).
But in contrary to monoids, there is no identity element.
“Abelian” means commutative. That is, a + b = b + a.
And, in fact, regions follows all these rules, making it an abelian semigroup.
We know two additional facts about our operator:
 It follows from the fact
'a: 'a
, that a + a = a  It follows from the fact
'static: 'a
for all'a
, that∃s∈L ∀a∈L s + a = s
.
Regions as a lattice
It makes much more sense to think of regions as a lattice. A lattice is a poset with two operators defined on it:
Join, an unique supremum (that is, least upperbound). This is our
+
operator.Meet, an unique infimum (that is, greatest lowerbound). This isn’t very useful for the matter of regions, but it is still defined on them.
which follows a set of laws:
The law of commutativity: Both meet and join are commutative operators.
The law of associativity: Both meet and join are associative operators.
The law of absorption: Meet(a, Meet(a, b)) = Meet(a, b) and Join(a, Join(a, b)) = Join(a, b).
In fact, this describes our structure perfectly. In particular, L is an
upperbounded lattice, i.e. we have a maximal element ('static
).
Lattice theory, which we will cover indepth in a later post is perfect for studying subtyping relations.
Directed Acyclic Graphs
A directed acyclic graph is a finite directed graph with no directed cycles. That is, any arbitrary directed walk in the graph will “end” at some point.
Let’s forget the 'a: 'a
case for a moment. As such, the regions under our
strict outlive relation, <, forms a directed acyclic graph (DAG).
In particular, if two node are connected, with a directed edge A → B, A represents a region, which outlives B.
Consider we take a reference &'b T
where T: 'a
'static

v
'a <\
 
 
 
v 
'b < 'a + 'b
Handling cycles
Every lifetime outlives itself, as explained in the last post. So our outlives relation doesn’t form a DAG, due to these cycles.
The solution is relatively simple, though.
Let {'a, 'b, 'c, ...}
be cycle such that 'a < 'b < 'c ... < 'a
. Due to
transitivity and antisymmetry, we can assume that 'a = 'b = 'c = ...
, thus we
can, without loss of generality, collapse the cycle into a single node.
This lets us interpret the graph, where edges represents outlives relations, as a DAG.
Recursively widening the regions
Say we want to infer the span of some node 'a
. Assume 'a
neighbors (outlives)
'b, 'c, 'd...
Since we know the bound, we can say 'a = 'b + 'c + 'd + ...
, since this is the
smallest ‘a subject to the outlives conditions.
Now, recursively do the same with 'b, 'c, 'd, ...
Since the graph is acyclic,
this will terminate at some point.
On an implementation note: you can optimize this process by 1. deduplicating
the regions, 2. collapsing sums containing 'static
into 'static
, 3. caching the
nodes to avoid redundant calculations.
Going further: liveness
Now that we have a closed form for inferring lifetimes, we can do lots of cool stuff.
Liveness of a value is the span starting where the value is declared and ending where the last access to it is made. This is in contrary to the classical lexical approach, where the initial lifetimes are assigned as the scopes of the variables.
Let’s start by defining empty(x)
as the region spanning from x to x (that is,
an empty region at x). Assign every value declared at x a region, empty(x)
.
Whenever a value of lifetime 'x
is used at some point y, we add a bound 'x:
empty(y)
.
So we essentially expand the region whenever used, effectively yielding the liveness of the value.
A happy ending
That’s it… The algorithm is really that simple. In fact, you can implement it in only a 100200 lines.
Questions and errata
Ping me at #rust in Mozilla IRC.
Follow me on Twitter or Github.