# How does Region Inference work?

**URL:** <https://internals.rust-lang.org/t/how-does-region-inference-work/7511>\
**Category:** Uncategorized\
**Created:** [May 11, 2018, 1:23pm UTC](https://internals.rust-lang.org/t/how-does-region-inference-work/7511 "2018-05-11T13:23:14Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![klassegeljakt](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/klassegeljakt/32/4129_2.png) [@klassegeljakt](https://internals.rust-lang.org/u/klassegeljakt)\
**Post date:** [May 11, 2018, 1:23pm UTC](https://internals.rust-lang.org/t/how-does-region-inference-work/7511/1 "2018-05-11T13:23:14Z")

</div>

Hi,

I am trying to understand how Rust's region inference algorithm works. I have went through the docs

- [https://rust-lang-nursery.github.io/rustc-guide/type-inference.html](https://rust-lang-nursery.github.io/rustc-guide/type-inference.html)
- [Rust Borrow and Lifetimes](http://arthurtw.github.io/2014/11/30/rust-borrow-lifetimes.html)

My understanding of region inference is that 'region' and 'lifetime' is equivalent, thus the purpose is to infer the lifetimes of borrows. The inference algorithm collects lifetime constraints over the course of a function, e.g., for:

```Rust
fn foo<'a: 'b,'b>(a: &'a str, b: &'b str) -> &'a str {
  let c = &123; // 'c
  a
}

```

There are two types of lifetimes: _bounded_ and _free_. Bounded lifetimes originate from the function body (`'c`). Free lifetimes are unbound as they originate from some arbitrary outer scope (`'a` and `'b`).

> > Regions are inferred somewhat differently from types. Rather than eagerly unifying things, we simply collect constraints as we go, but make (almost) no attempt to solve regions.

First question: How are the constraints collected? I understand that constraints for the _free_ lifetimes are specified in the signature, e.g., `'a: 'b`, but I'm not sure about the `bounded` lifetimes? I suppose one constraint is that `'c` does not not outlive the lifetime of `123`.

> > Lexical region resolution is done by initially assigning each region variable to an empty value. We then process each outlives constraint repeatedly, growing region variables until a fixed-point is reached. Region variables can be grown using a least-upper-bound relation on the region lattice in a fairly straightforward fashion.

Second question: How does the inference algorithm work at a high-level? I'm not sure why the region variables are _grown_ here or what the _region lattice_ refers to.

Third question: What is the output of the inference algorithm? Is it a concrete lifetime for each borrow, corresponding to a particular scope?

---

<div class="post-metadata">

**Author:** ![Ixrec](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ixrec/32/6754_2.png) [@Ixrec](https://internals.rust-lang.org/u/Ixrec)\
**Post date:** [May 11, 2018, 1:53pm UTC](https://internals.rust-lang.org/t/how-does-region-inference-work/7511/2 "2018-05-11T13:53:34Z")

</div>

Just to check, are you interested in what stable Rust does today, or the brand new algorithms that are still under the “NLL” feature? I think the new logic is mostly documented at [https://github.com/rust-lang/rfcs/blob/master/text/2094-nll.md](https://github.com/rust-lang/rfcs/blob/master/text/2094-nll.md), though the details may change again: [Blog post: An alias-based formulation of the borrow checker](https://internals.rust-lang.org/t/blog-post-an-alias-based-formulation-of-the-borrow-checker/7411)

---

<div class="post-metadata">

**Author:** ![klassegeljakt](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/klassegeljakt/32/4129_2.png) [@klassegeljakt](https://internals.rust-lang.org/u/klassegeljakt)\
**Post date:** [May 11, 2018, 2:40pm UTC](https://internals.rust-lang.org/t/how-does-region-inference-work/7511/3 "2018-05-11T14:40:26Z")

</div>

I would like to gain an understanding of the stable first, but I’ll check out the NLL after

---

<div class="post-metadata">

**Author:** ![klassegeljakt](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/klassegeljakt/32/4129_2.png) [@klassegeljakt](https://internals.rust-lang.org/u/klassegeljakt)\
**Post date:** [May 11, 2018, 3:50pm UTC](https://internals.rust-lang.org/t/how-does-region-inference-work/7511/4 "2018-05-11T15:50:59Z")

</div>

I am trying to visualize it. If I have these constraints, should I get this ordering and this region lattice?

```rust
Constraints | Ordering | Region-lattice 
------------|----------|--------------
  'a:'b+'c | 'a <= 'b | 'd Join, LUB (Most Specific Supertype)
  'b:'d | 'a <= 'c | / \     
  'c:'d | 'b <= 'd | 'b 'c    
  'd | 'c <= 'd | \ /     
            | | 'a Meet, GLB (Most Common Subtype)

```

I’m not sure how this example would look in code though.

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [March 25, 2019, 8:30am UTC](https://internals.rust-lang.org/t/how-does-region-inference-work/7511/5 "2019-03-25T08:30:12Z")

</div>

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.