Repair strategies

Tightest bounds first

This strategy checks the extracted function signature for any argument that has a reference type. Then we annotate each of those argument with the same lifetime 'lt0. Then we also annotate the output if it contains any reference type.

After that we compile and see if the program compiles, if there are any errors that the compiler can fix, we accept that fix (this include bounding the lifetimes down too) and if not--we try to loosen the bounds. This, however, can possibly create a loop as the compiler fixes tends to try to bound the loosened lifetime constraint so we incorporate a loop counter to detect this.

This loop counter also provides a guarantee that our refactoring terminates at some point and we can set the upper limit of the time our refactoring will run.

More formally,

Algorithm TightestBoundsFirstRepair
Input: Rust source file F, function name FN, max number of repairs MR
Output: successful repair predicate

AnnotateLifetimeToAllReference
Input: AST of type T TA, named lifetime to be annotated with 'LT
Output: new AST of type T TA'

LoosenBounds
Input: Rust source file F, extracted function AST FA
Output: predicate for successfully loosening bounds

By this version of loosening the bounds, we do not blindly loosen just any bounds which might put us in a loop or break what constraint we had before but we target the bounds that the borrow checker complains about.

NB: More room to experiment: What if we try to do an analysis to loosen the bounds or we loosen the next not loosened bound in the argument order?

Loosest bounds first

This strategy is the opposite. We check the extracted function signature for any argument that has a reference type. Then we annotate each of those argument with the a different lifetime 'lt0, 'lt1, etc. Then we also annotate the output with 'lt0 if it contains any reference type.

After that we compile and see if the program compiles, if there are any errors that the compiler can fix, we accept that fix (this include bounding the lifetimes down too). Since we are not expanding the bounds and the compiler feedback do not either, we do not run a risk of having a cycle but a loop counter provides us with a terminating guarantee under some time paramter.

More formally,

Algorithm LoosestBoundsFirstRepair
Input: Rust source file F, function name FN, max number of repairs MR
Output: successful repair predicate

Examples

Let's look closely at this toy example about lifetime bounds and this modified toy example about different in/out lifetimes.

Lifetime bounds

The original code before repair is:

pub fn new_foo(){
    let p : &mut &i32 = &mut &0;
    {
        let x = 1;
        bar_extracted(p, &x);
        println!("{}", **p);
    }
}

fn bar_extracted(p: &mut & i32, x: & i32) {
    *p = &x;
}

Simple repair

When we don't apply any strategy before compiling and keep using only what the compiler suggests, this repaired successfully:

fn bar_extracted<'a>(p: &mut &'a  i32, x: &'a  i32) {
    *p = &x;
}

Tightest bounds first

When we apply the tightest bound, we actually could not repair this example because the current approach is not fine-grained enough and ended up loosenning the lifetime of all references of p:

fn bar_extracted<'lt0, 'lt1, 'lt2>(p: &'lt2 mut &'lt2  i32, x: &'lt0  i32)  where 'lt0: 'lt1 {
    *p = &x;
}

We would need to figure out a way to loosen only some part of a reference liftime.

Loosest bounds first

We could repair this example:

fn bar_extracted<'lt0, 'lt1, 'lt2>(p: &'lt0 mut &'lt1  i32, x: &'lt2  i32)  where 'lt2: 'lt1 {
    *p = &x;
}

As the compiler helps us tighten the bound, we can safely use this.

Different In/out lifetimes

pub fn new_foo () {
    let x = 1;
    let x_ref = &x;
    let mut z : &i32;
    {
        let y = 2;
        z = &y;
        z = bar_extracted(x_ref, z, &y);
        println!("{}", *z);
    }
    z = x_ref;
    println!("{}", *z);
}

fn bar_extracted(x_ref: &i32, z: &i32, y: &i32) -> &i32 {
    if *z < *x_ref {
        &y
    } else {
        &W
    }
}

Simple repair

This is what the compiler suggested:

fn bar_extracted<'a>(x_ref: &'a i32, z: &'a i32, y: &'a i32) -> &'a i32 {
    if *z < *x_ref {
        &y
    } else {
        &W
    }
}

Tightest bounds first

Exactly the same as simple repair:

fn bar_extracted<'lt0>(x_ref: &'lt0 i32, z: &'lt0 i32, y: &'lt0 i32)  -> &'lt0 i32 {
    if *z < *x_ref {
        &y
    } else {
        &W
    }
}

Loosest bounds first

Here we first start with the biggest bounds, then the compiler suggests we tighten it:

fn bar_extracted<'lt0, 'lt1, 'lt2>(x_ref: &'lt0 i32, z: &'lt1 i32, y: &'lt2 i32)  -> &'lt0 i32 where 'lt2: 'lt0 {
    if *z < *x_ref {
        &y
    } else {
        &W
    }
}