Upgrading mutability based on exclusivity inference

I propose to allow upgrading immutable borrows to mutable ones, as long as the borrow checker can prove the immutable borrow is the only borrow standing. Language does not need to change, but it will accept more safe programs and reduce code duplication of implementing immutable getters and mutable getters separately.

Motivating Example

When a function returns a reference, it has to be fixed to be either immutable or mutable.

struct Example {
    // This example struct is simple, but imagine a complex data structure.
    data1: i32,
    data2: i32,
}

impl Example {
    pub fn get_some_ref_mutable( &mut self, key: i32 ) -> & mut i32 {
        // This code is simple, but imagine a complex algorithm retreiving a reference.
        if key == 42 {
            &mut self.data1
        } else {
            &mut self.data2
        }
    }
}

The function get_some_ref_mutable does NOT mutate self, but self has to be declared as &mut. It just needs to return a mutable subdata reference.

Now, suppose we want the same functionality, but want to work with immutable references. One has to implement a clone of the same function like below:

    // immutable version
    pub fn get_some_ref( &self, key: i32 ) -> &i32 {
        if key == 42 {
            & self.data1
        } else {
            & self.data2
        }
    }

Moreover, the implementations can't share the other function's code, even if they are practically the same code:

    pub fn get_some_ref( &self, key: i32 ) -> &i32 {
        // You can't re-use `get_some_ref_mutable`.
        return self.get_some_ref_mutable( key ); // error: `self` is not mutable.
    }

The fundamental issue in Rust is that the mutability of returned reference is not really a concern of the function returning it. We better let the caller to resolve the mutability of returned value based on the context.

Proposal: Inferred Mutability

Here's simpler example with a reasoning behind this idea.

fn not_working() {
    let mut v = Example { data1: 1, data2: 2 };
    let x1 = &v;
    let x2 = &x1.data1;
    *x2 = 4; // currently, not allowed
}

We can work around it by executing an identical mutable access:

fn workaround() {
    let mut v = Example { data1: 1, data2: 2 };
    let x1 = &v;
    let x2 = &x1.data1;
    // *x2 = 4; // currently, not allowed
    let x3 = &mut v.data1; // Note: x2 and x3 are the same reference.
    *x3 = 4; // ok
}

That works. But, that's silly since we are recalculating the same reference for no good reasons.

Logically, I think we need two new lifetime/mutability rules.

Rule 1: Upgrading to Mutable Borrow

When an immutable borrow is the only borrow of a mutable value, the borrow checker shall allow upgrading it to a mutable borrow.

Example:

fn rule1() {
    let mut v = Example { data1: 1, data2: 2 };
    let w1 = &v.data1; // immutable borrow
    // two possibilities
    if ... {
        // 1) implicit upgrade
        // `w1` is no longer live.
        *w1 = 4; // currently, not allowed
    }
    else {
        // 2) explicit upgrade via a new variable declaration
        let w2 = &mut w1; // currently, now allowed.
        // `w1` is no longer live.
        *w2 = 4;
    }
}

Among those two possibilities, considering the benefit of let mut / &mut declarations, I think the explicit upgrade is more desirable.

Rule 2: Flattening Nested Borrows

The Rule 1 alone won't resolve the issue in the not_working example. That's because x2 is not the only borrow of v.

fn rule2() {
    let mut v = Example { data1: 1, data2: 2 };
    let x1 = &v;
    let x2 = &x1.data1;
    // `x1` is no longer live.
    let x3 = &mut x2; // currently, not allowed
    // `x2` is no longer live.
    *x3 = 4;
}

The problem is that, becausex2 is borrowing from x1.data1, that keeps x1 live. What we need is to allow both x1 and x2 die at the time of x3's declaration.

The borrow structure before let x3 = ... is v --> x1 and x1.data1 --> x2. At that time, the rule 2 allows x1.data1 --> x2 to be flattened as v.data1 --> x2 by replacing (or instantiating) x1 with v.data1. This restructuing eliminates the lifetime constraint between x1 and x2, allowing x1 to die before x2, which inverts their usual lifetime schedules. The intuition is that x1 and x2 are both borrowing from v. As long as v is live, both of them are safe.

The lifetime inversion allows x2 to be the only borrow at the time of x3 declaration, thus allowing mutability upgrade (the rule 1).

Borrow flattening only makes sense between immutable borrows, thus this rule won't apply to mutable borrows.

This is just the logical reasoning of the process. The actual implementation can be simpler.

Conclusion

I propose to take mutability as something proved by compiler, instead of something prescribed syntactically. It effectively provides a way to implement accessor methods and search functions in a mutability-generic fashion.

Related Posts

Side Note

What I'm suggesting is actually inferred exclusivity (or uniqueness). (See Niko's blog post on this) But, to avoid any more confusion, let's just call it "inferred mutability" for now.

Your motivating example features API duplication for &T and &mut T access. The remaining proposal text then does not address function boundaries at all. The two “rules” both come with an example where “upgrading” of references seems entirely redundant, as there’s nothing limiting the references to have been mutable from the beginning, just add the missing “mut” in the right places.


I could go on and now assume that the whole point of your proposal might be e.g. that allowing

fn rule2() {
    let mut v = Example { data1: 1, data2: 2 };
    let x1 = &v;
    let x2 = &x1.data1;
    // `x1` is no longer live.
    let x3 = &mut *x2; // currently, not allowed
    // `x2` is no longer live.
    *x3 = 4;
}

should imply also allowing

impl Example {
    pub fn get_some_ref(&self, key: i32 ) -> &i32 {
        if key == 42 {
            & self.data1
        } else {
            & self.data2
        }
    }
}

fn rule2() {
    let mut v = Example { data1: 1, data2: 2 };
    let x1 = &v;
    let x2 = x1.get_some_ref(42);
    // `x1` is no longer live.
    let x3 = &mut *x2; // currently, not allowed
    // `x2` is no longer live.
    *x3 = 4;
}

However that now runs into one core principle of borrow checking: Local reasoning. The signature of get_some_ref alone does not tell the story whether or not upgrading the returned borrow can be permissable. Whether or not that’d be sound would depend on the implementation. A fn (&Example ,i32 ) -> &i32 function could also return a reference to immutable static memory, for instance:

impl Example {
    pub fn get_some_ref(&self, key: i32 ) -> &i32 {
        static LEET: i32 = 1337;
        if key == 42 {
            & LEET
        } else {
            & self.data2
        }
    }
}
5 Likes

I feel like what you're looking for is generic mutability.

With that, you could write this code (syntax to be bikeshedded):

    pub fn get_some_ref<M: Mutability>( &gen<M> self, key: i32 ) -> &gen<M> i32 {
        if key == 42 {
            &gen self.data1
        } else {
            &gen self.data2
        }
    }

I personally would love to have this in the language (I'm currently working on a generic mutability crate, not released yet), although many say it's not worth the price and using macros for this is fine.

The recent proposal to allow downgradable mut references seems like it would extend naturally to this:

    pub fn get_some_ref<'a, 'm>( &'a mut<'m> self, key: i32 ) -> &'a mut<'m> i32 {
        if key == 42 {
            &mut self.data1
        } else {
            &mut self.data2
        }
    }

…if we can say that &'a T is equivalent to &'a mut<'!> T or something.

Thanks for the feedback. Right, it depends on the lifetime tracking. But, I think it will work most of cases, especially when lifetime can be elided.

Putting together:

pub fn<'a> get_some_ref(&'a self, key: i32 ) -> &'a i32 {...} // after de-sugaring
// The return value borrows from the `&self`.

fn putting_together() {
    let mut v = Example { data1: 1, data2: 2 };
    let x2 = v.get_some_ref( nondet() ); // x2 borrows from &v.
    use( &x2 );
    // borrow structure: v --> &'1 v --> x2
    // flatten borrows: v --> &'1 v and v --> x2 (allowing `&'1 v` to die)
    let x3 = &mut *x2; // currently, not allowed
    *x3 = 4;
}

Even though lifetime couldn't be elided, it could still work (but more complicated). This second example below is out of scope, but nice to have:

fn longest<'a>(x: &'a str, y: &'a str) -> &'a str {...}

fn putting_together2() {
   let mut a : str = ...
   let mut b : str = ...
   let x: &str = longest( &a, &b );
   // borrows: a --> &a and b --> &b and `&a --> x` and `&b --> x`
   // both `&a` and `&b` above are no longer live.
   // after flattening: `a --> x` and `b --> x`
   let x2: &mut str = x; // `x2` borrows from both `a` and `b`.
   *x2 = ...;
}

@FZs Yes, it's a genetic mutability in a sense, except that generic cases can simply use immutable references. It doesn't require any no new language features to signal mutability-generic arguments/returns.

@jrose Downgrading mutability is a type of mutability generics, as well. But, I think upgrading will be applicable in more cases than downgrading.

I think you're missing the point. The fact that the return value borrows from self/x2 borrows from &v doesn't mean they are references pointing into it. Returning a static reference is an obvious example where the returned value doesn't point.

In other words, borrowing is an overapproximation of the program behaviour and you can't use it to infer what the program behaviour is, only what the program behaviour is not.


Another situation where your proposal breaks is when a type provides shared access to some data, but doesn't provide exclusive access, in which case your proposal would break that type invariant. For a concrete example consider Rc<T>. You can have exclusive access to an Rc<T> and get a &T, but you can't get a &mut T out of it because there might be other Rcs that point to the same allocation.

6 Likes

It doesn't have to be strictly subdata relationship for this to work. Mere "dependency" relationship (as "borrowing" currently means), or the lack thereof, is enough to establish exclusivity/uniqueness. If a 'static reference is passed as argument and returned, my rule 1 won't allow it to upgrade, since the 'static argument is still live.

The existing lifetime/borrow rules can already prove exclusivity of reference in many cases. I argue that mutability upgrade be allowed when the borrow checker can prove its exclusivity.

As to Rc<T>, my rules won't break any existing code and they won't allow any unsafe access to Rc<T> or anything else. If you have an exclusive access to Rc<T>, what you can get is &mut Rc<T>, not &mut T. That won't be changed.

The following code is legal:

static VAL: i32 = 0;

fn foo<'a>(bar: &'a i32) -> &'a i32 {
    &VAL
}

The return value of foo cannot be safely upgraded to a mutable reference because it is a pointer to static memory. However, by signature alone foo cannot be distinguished from the identity function on &i32, for which the return value could be upgraded. So the variance of the mutability of a returned reference cannot be correctly identified without either adding new non-lifetime annotations to function declarations or violating the rule that a function's signature depends only on its declaration and not its body.

5 Likes

Thanks for the counterexample. I missed that the lifetime relationship is just "lives as long as", not "dependency".

Counterexample 1:

static staticVal: i32 = 0;

fn foo<'a>(bar: &'a i32) -> &'a i32 {
    if *bar > 0 {
        bar
    }
    else {
        &staticVal
    }
}

fn counter_example1() {
    let mut v = 0;
    let w = foo(&v);
    // not safe to upgrade `w` to a mutable borrow.
}

So, my idea won't work without adding a new language feature after all. The necessary feature would be annotation that establish dependency relationship between args and return value. For example,

fn foo(bar: &i32) -> &'bar i32 { // explicit dependency on `bar`
    bar // &staticVar is not eligible here.
}

Also, I found explicitly immutable fields are problematic.

struct U<'a> {
    data: i32,
    mut_ref: &'a mut i32,
    immut_ref: &'a i32,
}

fn foo2<'a>(x: &'a U<'a>) -> &'a i32 {
    if x.data > 0 {
        x.mut_ref
    }
    else {
        x.immut_ref
    }
}

fn counter_example2() {
    let mut i = 0;
    let mut v = U{ data: 0, mut_ref: &mut i, immut_ref: &staticVal};
    let w = foo2(&v);
    // upgrading mutability of `w` may violate U.immut_ref's immutaiblity.
}

Accessing to such structs should be prohibited from upgrading, even if the first issue above was somehow resolved.