What algorithms does the Rust compiler use to infer lifetime variables?

Question

fn foo<'a>(x: &'a i32, y: &'a i32) {}

fn main() { 
    let a = 123;
    {
        let b = 234;
        foo(&a, &b);
    }
}

In the code above &a and &b should hopefully be references with different lifetimes.

How does the compiler infer the lifetime var 'a for foo? As far as I can tell, it's not using a standard Hindley-Milner unification algorithm. The lifetime must be the inner scope or some intersection of the two lifetimes.

Is lifetime inference a completely separate process to the standard type inference?

Does the compiler use intersection types or use some sub-type relationship between lifetimes to choose the most restricted lifetime?

Matthieu M. Matthieu M. · Accepted Answer · 2017-04-21T19:18:05

Rust uses a modified Hindley-Milner unification algorithm because it has sub-typing relationships.

For example, &'static T is a sub-type of &'a T for any 'a.

Your case is relatively easy, when the compiler sees the call foo(&a, &b) it just unifies 'a as the most restrictive of both lifetimes (which is the intersection, since lifetimes are lexical for now).

What algorithms does the Rust compiler use to infer lifetime variables?

1 Answers