How does Region Inference work?


#1

Hi,

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

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:

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?


#2

I think this question might be best asked on internals.rust-lang.org .


#3

Ok, thanks. I uploaded it there now


#4

You might find the readme (and/or code) in https://github.com/rust-lang/rust/tree/master/src/librustc_borrowck/borrowck useful.