Relaxing the borrow checker for fn (&mut self) -> &T


#1

The lifetime issue described here should be trivially fixable in the borrow checker logic.

To summarize the issue, the following code doesn’t pass the borrow checker:

struct T {...}
impl T {
    pub fn mutate_and_return_immut_ref(&mut self) -> &Foo { ... }
    pub fn use_immutable(&self) { ... }
}

let mut t : T = T { ... };
let foo : &Foo = t.mutate_and_return_immut_ref();
t.use_immutable();

The checker complains that use_immutable() cannot take an immutable reference to t because the foo variable has already taken a mutref to t. This seems like an over-strict enforcement of borrow semantics. Yes, it’s true that the body of mutate_and_return_immut_ref requires a mutable ref to t, but I can’t see a reason for the borrow checker to extend the mutability constraint on the borrow to the lifetime of the returned immutable reference.

Conceptually, the above expression could be treated as if the programmer had written:

let foo : &Foo = { t.mutate(); t.return_immut_ref() }
t.use_immutable();

The borrow checker would be fine with the above logic. The mutable borrow on t is taken only for the lifetime of the call expression, and the borrow on t taken by the return value is immutable.

Is there something I’m missing where the borrow checker’s logic cannot be relaxed to allow this?


#2

This code is currently sound:

struct Foo(Vec<i32>);

impl Foo {
    fn push_and_get(&mut self) -> &i32 {
        self.0.push(42);
        &self.0[0]
    }
}

If the borrow checker were relaxed as you propose, this would easily allow creating dangling pointers:

let foo = Foo(Vec::with_capacity(1));
let dangling_ref = foo.push_and_get();
// force reallocation, making the reference from the first call dangling
foo.push_and_get();

#3

The second call to push_and_get in your example would still be disallowed, since dangling_ref would hold an immutable borrow on foo, and push_and_get needs a mutable reference to foo.

Methods on Foo that take &self, however, would still be callable.

To make a finer point of it, consider the implicit transform I suggested above applied to this example:

impl Foo {
    fn push(&mut self) { self.0.push(42); }
    fn get(&self) { &self.0[0] }
}

let foo = Foo(Vec::with_capacity(1));
// Transform of "push_and_get" to separate the mutation and immutable-ref-return {
foo.push();
let dangling_ref = foo.get();
// }

// Transform of second "push_and_get" {
foo.push();
foo.get();
// }

The borrow checker would correctly reject this code since dangling_ref would hold a live immutable borrow on foo. That behaviour would still be preserved.

The relaxation would simply make the return value (and by implication dangling_ref) an immutable borrow instead of a mutable borrow. This would allow for subsequent immutable-method calls on foo while the return value is live, but still prevent mutable-method calls on foo.


#4

D’oh! I was so eager to write a program relying on the one property of borrows that your proposal would remove that I forgot the other rules.

I still believe that this change is dangerous. The signature (&mut self) -> &T currently guarantees that no &self method can be called on the same object while the result is still in use. While it seems unlikely that this makes safe Rust code unsound, I could see unsafe code relying on it, and it would be fully within its rights to do so.


#5

You’ve overlooked one thing, though: the borrow isn’t kept alive by the reference, but the lifetime.

Which can be, for example, in an unsafe structure with complex mutability interactions.

What the borrow-checker records is how the borrow was created (mutably) and how long it lasts (the lifetime in the return value ends up as long as necessary, during inference).

The borrow-checker doesn’t actually understand the returned borrow.

Which means you can write e.g. a lifetime-based API for managing a global resource without a single pointer in the return value, and the borrow-checker will enforce the somewhat simple (but correct) rules.


#6

Another thing, inlining a method call and observing that the resulting code passes borrow checking can be misleading. Borrow checking works locally and this certainly won’t change. So whatever the rule winds up being, it needs to work only by looking at the signature. Even if one somehow privileges references (to sidestep @eddyb’s point) the rule must be sound even for very complicated methods that can’t be cleanly separated into a “mutate something” step and a “create an immutable borrow” step.


#7

I don’t think any semantic requirements would be broken by the borrow checker treating this as two separate borrows: one mutable borrow that applies to the lifetime of the call expression, and an immutable borrow that applies to the return value lifetime. Yes, the borrow checker is currently combining these, and extending the mutability property of the borrow to the lifetime of the returned reference, but I’m arguing that there is no correctness problem caused by relaxing that behaviour.

rkruppe:

I agree, and I don’t think that needs to change. This relaxation can be inferred correct simply from looking at the signature.

The claim I’m making about the correctness of this is actually pretty strong, and doesn’t pertain to this example in particular. The strong claim is this:

Any method with signature fn method(&'a mut self, ...) -> &'a T can be automatically treated by the compiler, while preserving the semantics of the program, as if it was written:

fn __MUTATOR_method__(&'a mut self);
fn __GETTER_method__(&'a self) -> &'a T;

And following on that, a call to method of the form let t = obj.method(), can be treated by the compiler as if it was written:

obj.__MUTATOR_method__();
let t = obj.__GETTER_method__();

This has to be the case because whatever method does, at the point of “returning”, the reference it returns is immutable. Any potential mutations of the object allowed by the &mut self reference MUST cease by the end of the method call. The immutable returned reference can’t be used to perform any mutations, so why is it being treated as a mutating borrower?

Unsafe code already has to guarantee that if an immutable borrow exists on an object, and a later immutable method is called, that immutable method call cannot cause any hidden mutations of any live immutable references into the object. This relaxation would not change that requirement.


#8

The only thing the borrow checker sees is a bunch of lifetimes.

There is no relationship between the types using those lifetimes and the original borrow.

Inference has produced minimally sufficient lifetimes, and borrow checking makes sure they’re not too long.


#9

Right. The lifetimes in play here are the following:

  {
  let x = obj.mutate_and_return_constref();
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
               call expression lifetime
  | ...
  | ... lifetime of returned reference.
  | ...
  }

Currently the borrow checker is taking the fact that the lifetime of the invocation of mutate_and_return_constref uses a mutref, and extending the mutable borrow associated with that to the lifetime of the returned reference.

The borrow checker is aware of both lifetimes, and it can infer, purely from the method signature, that the returned reference cannot be used to mutate obj. It can confidently choose to take a mutable borrow on obj for the lifetime of the call, and a const borrow on obj for the lifetime of the returned reference.


#10

@kvijayan You repeatedly refer to mutations as if mutating something is the only reason for &mut. That is an understandable confusion, and most people (including myself) think of it like that most of the time, but it’s not all there is to mutable borrows. A &mut is also a unique borrow, and as such ca be useful even if you don’t need to mutate anything. For example, consider a stack-like data structure that ensures only the top-most frame on the stack is usable at any point in time:

use std::marker::PhantomData;

struct Stack;
struct Frame<'a>(PhantomData<&'a ()>);

impl Stack {
    fn first_frame(&mut self) -> Frame {
        unimplemented!()
    }
}

impl<'a> Frame<'a> {
    fn sub_frame(&mut self) -> Frame {
        unimplemented!()
    }

    fn do_something(&self) {}
}

fn main() {
    let mut stack = Stack;
    let mut frame1 = stack.first_frame();
    frame1.do_something();
    {
        let frame2 = frame1.sub_frame();
        frame2.do_something();
        // frame1.do_something(); // doesn't compile
    }
    frame1.do_something();
}

There is no mutation in this program, but it still enforces an important semantic invariant through lifetimes. And virtually any semantic invariant can become vital for the memory safety of the whole program when it’s a semantic invariant that unsafe code relies on.

Now, the above example relies on lifetime parameters on structs. I’ve not given it enough thought to say for sure whether one can pull similar tricks using only references. But if this extension would require special pleading for references, then that would be a big mark against it in my mind.


#11

No, there is a single lifetime, and the borrow checker doesn’t understand how it is used other than to create the borrow.

The borrow checker doesn’t know what a reference is, effectively.
It only tracks moves, borrow creations and borrow durations (which are determined directly by their “local scope” lifetimes).


#12

The relaxation should work just as well using unique/non-unique terminology. I’m not relying on behaviour unique to mutability. It just seems the most appropriate way to talk about it since it’s right there in the keyword :slight_smile:

Rephrased, looking at the signature of a method fn foo(&mut self) -> &T, we have three lifetimes in play: the lifetime of the object the method is called on, the lifetime of the call to foo (which beings when foo is called, and ends when foo returns), and the lifetime of the returned reference (which begins when foo returns, and ends when the returned reference falls out of scope).

The borrow checker takes a unique borrow on the object for the purposes of passing the self argument into the call to foo. It needs to do this because foo's implementation needs unique access to self. The borrow checker also takes a unique borrow on the object for the returned &T reference. These are two separate lifetimes, but the borrow checker treats them both as unique borrows.

This is overly restrictive because &T doesn’t mandate unique access to the underlying value. If it did, we would have typed it &mut T instead. So why is the borrow checker treating &T as taking a unique reference on the object? It’s very clearly NOT a unique reference.

I agree that the borrow checker is treating it as a single lifetime, but very clearly the lifetime of the call and the lifetime of the returned value are different. The proposal is to make the borrow checker treat them as two distinct lifetimes instead of treating them as one and the same, and the claim is that this does not lead to any semantic violations of rust’s lifetime model.


#13

What I’m saying is that you can’t claim this is “trivial”.

You’re also making claims about semantic violations without formal proofs, which makes them pretty much irrelevant.

but very clearly the lifetime of the call and the lifetime of the returned value are different

On the contrary, the type system mandates that the lifetimes inside the arguments and the return value are identical.

This idea might be actionable, but it requires splitting the borrow before borrow-checking, into a mutable borrow that lasts for the duration of the call, followed by an immutable borrow created by the “materialization” of the return value.

Not only would the borrow have to be split before borrow-checking, it would have to be always split, that is, calling for<'a> fn(&'a mut T) -> Foo<'a> would have to use different lifetimes for inputs and outputs (alone this might be impossible to have with complex typesystem interactions), and you would have to track down all the borrows associated with the input lifetime, and borrow again with the output lifetime.

All of this is much more complex than the planned refactoring of region (i.e. lifetime) inference and borrow-checking, including the planned non-lexical lifetimes (which are a pre-requisite, otherwise splitting a borrow would result in overlapping borrows because the original one wouldn’t always stop at the call).

Alternatively, lifetimes could be inferred to have potentially two scopes, an outer immutable one and an inner mutable one each, and the mutability of an inferred lifetime would depend on how it is used deep within a type.

Then, a borrow based on such a strange lifetime would stop being mutable after a certain point, allowing other immutable references to appear.
It could also start being mutable later than its creation, e.g.:

let mut x = 0;
let r = &mut x;
// x is still borrowed immutably here
let y = x;
let s = mut_to_shared(r);
// both r and s behave like shared references now
assert_eq!([*r, *s, y], [x, x, x]);

#14

When I wrote the signature sub_frame(&mut self) -> Frame (i.e., sub_frame<'a>(&'a mut self) -> Frame<'a>) in the above code, I meant exactly that and nothing else. I wanted a unique borrow of the self object to persist for as long as the return value is live. Furthermore, this is not an abuse of the region system, the behavior I want falls out perfectly naturally from the fact that both types contain the same lifetime 'a. It’s essentially an implied equality constraint: The lifetime in this place is the same as the one over there. To assign separate lifetimes to the &mut self and the Frame return type would not be convenient in this case, it would blatantly violate the types I’ve written own and in fact break the semantic invariant the signature was intended to maintain.

(Aside: This was not an example I made up to prove a point. It’s a stripped down, slightly modified version of an allocator crate I’ve started designing months ago but never got around to implementing.)

Likewise, when one writes foo<'a>(&'a mut self) -> &'a T (which is what foo(&mut self) -> &T is short for) one explicitly states that both borrows should be associated with the same lifetime. One may not be aware of it, one may not even want it, but that is what it means. I understand you want to express “borrow the object mutably for the duration of the call and then borrow it immutably” and associate a lifetime in the return type with the latter borrow, but that is not what the existing (&mut self) -> &T signatures mean. It may be a useful pattern to support, though I really can’t see a simple and elegant way to add it, and as you can probably tell I am extremely skeptical about re-purposing existing syntax to do that. But I just gave an example where the lifetime of the unique self borrow should be as long as the result’s lifetime, so you can’t just declare the existing semantics needlessly restrictive.


#15

Fair enough. The trivial bit was more saying that the program transformation would be trivially correct. I didn’t mean to imply that the implementation of it would be trivial. I have no idea how the rust compiler’s internal representation of borrow relationships is and how hard it would be to implement.

I realize a fuller treatment of the proposal would require more formal arguments. Still reasonably confident that the semantics would be preserved, though.

These two comments (and the rest of the post they are embedded in) helped me understand your arguments a lot more clearly.

Thanks for the stack example rkruppe, I didn’t see what you were getting at until the second explanatory post about it. The fact that this behaviour is by design, and allows the programmer to communicate with the borrow checker in a predictable way to leverage the lifetime model for their own ends… was not something that I had considered. I understand the motivations there and can see how it would be beneficial.

Appreciate the feedback. I’ll think on this more and post follow-ups if I have thoughts or other questions.

To underscore my motivations, just as you want to explicitly tie the return value to the lifetime of the input argument, there are circumstances where I want to explicitly tell the borrow checker that I require the unique borrow purely for the method body, and don’t want the uniqueness constraint extended to the lifetime of the return value.

Also, your use case doesn’t have an easy workaround without the current behaviour, whereas mine does with the current behaviour (just split up the mutator and getter)… so I can understand the skepticism.

Thanks for the patient explanations :slight_smile:


#16

So this issue comes up repeatedly. My take is this: In the current model, @kvijayan’s claims are not quite correct, but the issue he identifies is annoying, and it’d be nice to have a better solution.

First let me explain the model as I see it. I think this is quite similar to what @eddyb has been saying, though there are a lot of comments here and I’ve not parsed them all with 100% care. I think it’s easiest to think of the current model in terms of permissions. So when you do the borrow you give up your permissions for the lifetime of the borrow and you effectively transfer them into the reference. When the borrow expires (that is, when we exit the lifetime), you get those permissions back.

The current system was designed to make minimal assumptions. In particular, we wanted to avoid all kinds of alias analysis or reasoning about types and just focus on lifetimes. This is for two reasons: first, we know that people (particularly in unsafe code) will play games with types and transmutes and so forth. Second, those kinds of analyses are really brittle in the face of generics, closures, objects, etc (aka, existentials) where the types are unknown.

Furthermore, the borrow checker does not (and, at least in general, it cannot) assume that just because a function returned, it is finished using some data. Consider this signature:

impl<'scope> Scope {
    fn process(&self, x: &'scope mut T) -> &'scope U { ... }
}

In this case, it would be perfectly legal for unsafe code to take the x pointer and send it off to another thread. Or perhaps they have selected one or two fields from x to ship to another thread for processing, and returned the rest to you. This is legal so long as they know this thread will terminate before 'scope exits.

Of course, if you read that code above carefully, you will see that it is not quite @kvijayan’s example. His example – or at least the usual – was more like this (for clarify, I’m “eliding” elision):

impl Container { 
    fn insert_and_lock<'a>(&'a mut self, key: K) -> &'a Value { ... }
}

Now, in this example, the 'a is bound on the function itself (rather than on the impl. It only appears on exactly one argument (self). In such a case, I don’t as yet see how any safe abstraction could still be using parts of self after it returns. So in short it does seem plausible to me that we could “downgrade” the borrow in such a case. But it would have to be a pretty narrowly tailored rule.

This seems pretty related to the “rust memory model” question. Basically, it makes sense that we could potentially downgrade the borrow in precisely those cases where it makes sense for us to add “nocapture” annotations in LLVM, I suspect.

In this whole discussion, though, I’ve been assuming safe code. When you get to unsafe code, the picture is a bit murkier. When it comes to the memory model, for example, I’ve been envisioning rules that are focused on “safety boundaries”. When you enter into a function that contains unsafe code, the compiler would assume a lot more potential aliasing than in purely safe functions. And when a function is declared as unsafe (unsafe fn), it is considered effectively an extension of that unsafe region, and hence it may well not have “nocapture” annotations added to it. In such cases, should the borrow checker’s behavior also change?

I think the TL;DR then is that there may be indeed be something here, but it’s not an open-and-shut case. This case probably belongs to a list of things we should consider addressing in the borrow checker:

  • nested method calls
  • non-lexical lifetimes
  • “downgrading” borrows

The first two I have pretty solid plans for, though I’ve not been as good about communicating those plans as I’d like. Non-lexical lifetimes in particular has a lot of subtle points. Downgrading borrows I confess I haven’t thought as much about. But I think that, unlike the other two, it is at least partly about conventions and unsafe code as much as anything else – that is, the correctness of such a transform hinges on what the callee is allowed to do – and hence it should probably be considered together with a proposal for a Rust memory model.


#17

Bah. This is what I get for writing posts without having drunk more coffee. Reading @rkruppe’s post reminded me that a part of my concern about this particular proposal (which, as I said, comes up from time to time) is that in fact the set of function signatures where you can apply is even more narrow than I proposed. You have to start introducing some “type-based” reasoning, because you need to be sure that no &'a mut references escaped into the return type. That is, the signature I gave is OK fn<'a>(&'a mut T) -> &'a U, but one like fn<'a>(&'a mut) -> U<'a> is not. Or at least whether it is ok or not would depend on the definition of U. That is precisely the kind of type-based analysis we’ve been trying to avoid.


#18

Ok I’m trying to reason through how it might be possible to enable this to work. To reduce the confusion around specific types, I’ll write my example code in terms of pure lifetime annotations. So here’s a rewritten example that exhibits the issue:

struct Foo { count: u32 }
struct Count<'a> { count: u32, dummy: PhantomData<&'a u32> }
impl Foo {
    pub fn incr<'a>(&'a mut self) -> Count<'a> {
        self.count += 1;
        Count { count: &self.count; dummy: PhantomData }
    }
}

// Caller code
{
    let mut foo = Foo { count: 0 };
    let c : Count<'a> = foo.incr::<'a>();
    ...
}

So the borrow checker analyses the caller code. It knows of the lifetime of foo, which extends from its declaration do the end of the scope. It needs to compute the lifetime of the mut borrow on foo, which is 'a. The inferrer unifies the usage of 'a by incr's signature, with the usage of 'a by the variable c, and concludes that the lifetime of 'a extends from the start of the call to the end of the scope.

Thus the mut borrow, which is taken for lifetime 'a, extends from the start of the call, to the end of the scope.

To take a stab at decoupling the lifetime of the method call from the lifetime of the returned var, I changed the signature of incr to the following:

pub fn incr<'a, 'b>(&'a mut self) -> Count<'b> where 'a: 'b {
    self.count += 1;
    Count { count: &self.count; dummy: PhantomData }
}

// Caller code
{
    let mut foo = Foo { count: 0 };
    let c : Count<'b> = foo.incr::<'a>();
    ...
}

This doesn’t quite get us what we want. The lifetimes used for the call and the return value are separated into different lifetime variables, but the unifier still ends up making the lifetime 'b contained within 'a, since that’s required by the signature of incr. That signature is required for the body of incr to properly type-check, since incr can’t hand out a lifetime-'b reference into a lifetime-'a object without being sure that 'a outlives 'b.

Conceptually, what we want to be able to specify in incr's signature is the following (I’m going to invent some syntax here):

pub fn incr<'x, 'a, 'b>('x &'a mut self) -> Count<(const 'b)>
    where 'x: 'a, 'x: 'b
{
    self.count += 1;
    Count { count: &self.count; dummy: PhantomData }
}

In our imaginary syntax, what incr expresses is that the incoming argument is implicitly associated with a lifetime 'x. For the purposes of executing the method, we take a mut borrow on self, with lifetime 'a, and that’s ok since 'x outlives 'a. Then, we return a const reference into self of lifetime 'b, which is ok since 'x outlives 'b.

This allows incr to compile without any cross-procedural analysis.

At the call site, the borrow checker has the following understanding of lifetimes:

// Caller code
{
    let mut foo = Foo { count: 0 };
    let c : Count<'b> = foo::<'x>.incr::<'a>();
    ...
}

The unifier analyses the signature of incr with the behaviour of the method, and comes to the following lifetime assignments:

  1. The lifetime 'x extends from the start of the call to the end of the scope.
  2. The lifetime 'a extends from the start of the call to the end of the scope, and takes a mut borrow on foo.
  3. The lifetime 'b extends from the end of the call to the end of the scope, and takes a const borrow on foo.

The “implicit lifetime annotation” behaviour would work something like the following:

fn F(&mut self) -> &T;
// would desugar to
fn F<'a>('a &'a mut self) -> &(mut 'a) T;

Note that the syntax &(mut 'a) T still implies that the reference cannot be used to perform mut operations, but the borrow associated with that reference is a unique borrow.

I don’t know if this counts as non-lexical lifetime behaviour, but it doesn’t seem to be. The requirements from the language seem to be:

  1. Allowing the disassociation of the lifetime of the incoming value, from the lifetime of the borrow taken from that value for the lifetime of the call itself.
  2. Allowing the specification of a lifetime with a const/mut modifier that lets the borrow checker reason about the programmer’s intent when she specified the lifetime.

#19

Someone on stackoverflow found a workaround: http://stackoverflow.com/a/38080934/1103681

It obscures the API somewhat, but it makes it obvious what’s going on.


#20

Sorry to bump a thread this old, but the recent Elision 2.0 thread brought this thread to mind, and I got an idea how to allow “downgrading” borrows.

What if mutable references had two lifetimes to begin with? A lifetime of mutability and a lifetime of the reference. After the mutable lifetime ends, a reference to the value can still exist, but can’t be mutated anymore – the mutable reference must have been “downgraded” to a shared reference.

This would allow the lifetime checker to reason about stuff without understanding references per se; let us think about function signature like this: (The reference type constructor &'ref mut 'muta T is a straw man syntax.)

fn modify_return_inner<'muta, 'ref: 'muta>(val: &'ref mut 'muta IntContainer) -> &'ref i32

When this function returns, there’s nothing that would need 'muta to be alive anymore, so just by looking at the signature, we can think of it as having ended. Only the lifetime 'ref is alive, and from the type of val, we see that it’s only a lifetime of reference, not a lifetime of mutability, which allows us use the original value immutably.

On the other hand, this function keeps 'muta alive as long as the return value lives and doesn’t allow us to use the original value even immutably:

fn return_inner_mut_ref<'muta, 'ref: 'muta>(val: &'ref mut 'muta IntContainer) -> &'muta mut i32

Of course, this would be just an fully explicit syntax, equivalent in semantics with the current:

fn return_inner_mut_ref(val: &mut IntContainer) -> &mut i32

The &mut constructor could backwards compatibly allow single lifetime like it currently does, which would mean that the mutable and the reference lifetimes are the same lifetime, but the syntax for a pair of lifetimes could be an additional, explicit one that allows downgrading.

I guess that this would look a bit better with some ergonomic improvements. Eliminating the “outlives” annotation is an obvious one.