Pre-RFC: Downgradable mutable borrows

Some months ago I've read the following comment by steffahn and I think a generalized &mut T could be viable.

So here's my very first Pre-RFC based on that idea:

Summary

Generalize &mut with a second, optional lifetime to allow opt-in downgradeable borrows.

Motivation

Currently coercing or reborrowing a &mut as an immutable reference always extends the unique borrow to the lifetime of the resulting reference. When interior mutability is involved, this behavior is neccessary for correctness (e.g. for Cell::as_mut and Mutex::as_mut to be sound), but in other cases relaxing the borrow to a shared one might be perfectly safe.

This proposal allows get-or-insert functions and similar patterns that need an unique borrow for a short time inside the function body but want to return an immutable, shared reference.

Guide-level explanation

With this proposal, mutable references can have separately tracked "borrow" and "uniqueness" lifetimes.

If not further restricted, unique borrows created from mutable references can downgrade to shared borrows if they are only used immutably after some point:

fn main() {
	let mut x: i32 = 42;

	let a = &mut x; // type inferred as &'_ mut<'_> i32
	a += 1;
	 // `a` is only coerced/reborrowed immutably after this point, so
	 // it can be downgraded and only the uniqueness lifetime ends here.
	let b = &x;

	println!("{}", a == b);
}

The separate tracking is opt-in outside function bodies, e.g. in function signatures. The borrows from mutable references stay unique, even if the references are coerced to shared references. Only if a second lifetime parameter is added (e.g. &'ref mut<'uniq>) they can be downgraded.

E.g. the following code fails:

#[derive(Default)]
struct Cache(std::collections::HashMap<u64, String>);

impl Cache {
	fn get(&self, key: u64) -> Option<&str> {
		self.0.get(key)
	}

	fn get_or_insert(&mut self, key: u64, default: impl FnOnce() -> String) -> &str {
		self.0.entry(key).or_insert_with(default)
	}
}

fn main() {
	let mut cache = Cache::default();

	let a = cache.get_or_insert(1, || "foo".into());
	let b = cache.get(1);
	// ^ Error: cannot borrow `cache` as immutable because it is also borrowed as mutable

	println!("{a}, {b}");
}

With downgradeable borrows, the code can compile by adding the second lifetime parameter and specifying that the return value of get_or_insert only uses the borrow lifetime:

	fn get_or_insert<'a>(&'a mut<'_> self, key: u64, default: impl FnOnce() -> String) -> &'a str {
		self.0.entry(key).or_insert_with(default)
	}

Where it's neccessary for soundness, the borrows can't be downgraded, as the function signatures of e.g. Cell::get_mut() won't allow downgrading of the returned borrow:

fn main() {
	let mut x: Cell<Option<i32>> = Cell::new(Some(42));

	let a: &i32 = x.get_mut().as_ref().unwrap();
	x.replace(None);
	// ^ Error: cannot borrow `x` as immutable because it is also borrowed as mutable

	println!("{}", a);
}

Reference-level explanation

Mutable reference types &mut T have two associated lifetimes. One describing the total duration of the borrow and one describing the duration the borrow needs to be unique: &'ref mut<'uniq> T with the implicit constraint 'ref: 'uniq.

The uniqueness lifetime can be omitted and is then forced to be equal to the borrow lifetime. &'a mut T is thus short for &'a mut<'a> T. Such references with both lifetimes equal can be coerced to mutable references with shorter lifetime only if both lifetimes stay equal.

Besides this restriction, mutable references &'a_ref mut<'a_mut> T can be coerced to &'b_ref mut<'b_mut> T, as long as 'a_ref: 'b_ref, 'a_mut: 'b_mut holds, and all mutable references &'a_ref mut<'a_mut> T can be coerced to &'b T, as long as 'a_ref: 'b holds. Coercing to or reborrowing as a shared reference doesn't extend the uniqueness lifetime.

For backwards compatibility &mut T in function signatures desugars to &'_a mut<'_a> T. This ensures that functions like Cell::get_mut stay sound. This makes the feature opt-in for all interfaces.

Drawbacks

  • Introducing a built-in type with two lifetimes makes the language more complex and harder to learn.

Rationale and alternatives

  • Do nothing and continue to only allow such patterns with some kind of interior mutability.
  • An implementation of partial borrows could also include downgradeable borrows as a special case of the partial borrowing rules.

Prior art

TBD

Unresolved questions

  • Is there a better syntax than &'a mut<'b> T? Maybe &'a mut 'b T?
  • Type inference might need some tweaks to match e.g. &'a mut<'b> T to an impl<'a> Trait for &'a mut T.
  • Unless Entry, DerefMut, etc. are modified to allow the second lifetime, most code won't be able to take advantage of the feature. It's hard to say if this is even possible for all types and traits for which downgradeable borrows would be helpful without a breaking change.

Future possibilities

In a future edition, the desugaring of &mut T in function arguments might be relaxed to a downgradeable reference with two anonymous lifetimes. This would allow more code to compile, but could make functions with interior mutability through unsafe code unsound, if those that need it forget to constrain the argument to a single lifetime. So that would need a detailed transition plan. `

6 Likes

I don’t even think that this particular code example is of too much importance to make compile. In my opinion, it would be fine – especially as a minimal viable product – even if every direct usage (including creation of new immutable re-borrows) of the mutable reference still asserts that it’s currently still having mutable access, i.e. none of the two lifetimes would be allowed to be dead.[1]

The more minimal code example that I’d find particularly interesting is this:

fn main() {
	let mut x: i32 = 42;

	let a = &mut x; // type inferred as &'_ mut<'_> i32
	a += 1;
	let b = &*a;
    // a is no longer used beyond this point.
    // The mutable borrow of `x` can end while an immutable borrow remains,
    // and the re-borrow in `b` stays alive.
	let c = &x;

	println!("{}", b == c);
}

And then of course, this situation where everything is local is relatively boring, but the killer feature is that it works through function boundaries

fn increment_then_reborrow<'lt_immut>(a: &'lt_immut mut<'_> i32) -> &'lt_immut i32 {
    a += 1;
    &*a
}
fn main() {
	let mut x: i32 = 42;

	let b = increment_then_reborrow(&mut x);
    // The mutable borrow of `x` can end immediatly
    // after the `increment_then_reborrow` call,
    // while an immutable borrow remains,
    // and `b` stays alive.
	let c = &x;

	println!("{}", b == c);
}

  1. Across function boundaries, this restriction would always be necessary anyways. If you declare fn foo<'a, 'b>(x: &'a mut<'b> T), then the reference x is always allowing mutable access throughout the entire duration of the call. ↩︎

1 Like

No, even with downgradable borrows, a sequence of two get_or_insert calls should not compile.

At least in my interpretation. Maybe I’m misunderstanding your understanding of this feature.

This will always fail

	let a = cache.get_or_insert(1, || "foo".into());
	let b = cache.get_or_insert(2, || "bar".into());
	println!("{a}, {b}"); // ERROR

Because upon creation, the mutable borrow passed to the second get_or_insert call, even if downgradable, must be exclusive (ruling out coexisting immutable borrows) at least for the (short) duration of that call.

The thing that can be made to work though is something like

	let a = cache.get_or_insert(1, || "foo".into());
	let b = cache.get(2).unwrap();
	println!("{a}, {b}"); // ERROR

with get_or_insert<'a>(&'a mut<'_> self, …) -> &'a Something
and get<'a>(&'a self, …) -> Option<&'a Something>


Probably a typo, right? “can be coerced to &'b_ref mut<'b_mut> T” probably.

1 Like

Yes, you're right. Seems like I confused myself while rewriting my initial code examples. I'll fix that.

I have a minor concern that &'long mut<'short> T: Send implementation, which – if this transparently expands the existing &mut T type – just requires T: Send, no T: Sync might possibly be problematic, but I couldn’t come up with any scenario yet how this can turn into an actual soundness issue. Also I’m going to bed now, which is why I’m leaving only this note. (If it was an issue, it might kill the attempt to make existing &'a mut T just “desugar” to &'a mut<'a> T.)

For what it's worth, when I read &'a mut 'b T, my instinct is that 'a is the lifetime of the mutable portion of the borrow, and 'b is the lifetime of the borrow as a whole (so equivalent to &'b mut<'a> T). Maybe I'm the only one who thinks that way, but with the angle-brackets syntax there is no possibility of confusion (though at the cost of more ugly angle brackets).

1 Like

I think it should still be safe. To use a reference as a &'long mut<'short> argument 'short still must be valid, so this doesn't change in respect to the existing &mut T. Only if immutable and mutable references were unified e.g. with something like &'long mut<'!> T it would become problematic.

1 Like

The complexities if adding a new optional lifetime argument to &mut T seems really major and needs a very significant motivation, which I don't see here.

The problem of get or insert functions is intended to be solved with flow sensitive borrow checking (polonius), which doesn't expose anything new in the language.

2 Likes

Is that possible without introducing semver hazards?

E.g. if you've got a function with the signature

fn foo<'a>(&'a mut self) -> &'a T

it could be ok to downgrade the borrow, but if there's interior mutability in the implementation, it may not be sound for separate borrows to exist while 'a is live.

1 Like

I don't think this is possible/correct to do, and I would prefer explicitness anyway. One problem is that analysing the function signature might not be enough to determine when a downgrade happens.

For example, this is a valid code that could benefit from downgrading:

fn add_hello_and_put_into_vec<'a>(s: &'a mut String, v1: &mut Vec<&'a str>, _v2: &mut Vec<&'a mut str>) {
    s.push_str("hello");
    v1.push(&*s);
}

...but it doesn't return a reference, and it's not clear from the signature that a downgrade is happening (the code could just as well push the string into the other Vec, preventing the downgrade).

And if it's not possible to determine this from the signature alone, then that would undermine Rust's amazing function locality. (Remote code could break due to changing the implementation of a function without a change in the signature!)

While this version completely fixes the issue:

fn add_hello_and_put_into_vec<'a, 'm>(s: &'a mut<'m> String, v1: &mut Vec<&'a str>, _v2: &mut Vec<&'a mut str>) {
    s.push_str("hello");
    v1.push(&*s);
}

(without an extra constraint like 'a: 'm, Rust wouldn't allow me to push the reference into the second Vec, proving that the downgrade is sound)

2 Likes

Tree Borrows already has this for raw pointer permissions! [1]

This means that implementing this feature would only require compiler support but no changes to the memory model are necessary, assuming the final memory model will be Tree Borrows or something derived from it. Stacked Borrows doesn't support this even for raw pointers.

(I just read the Stacked Borrows and Tree Borrows papers. I don't know how many people reading this have read them, I felt like I should assert this for those do haven't.)


  1. pointers change from Active (mutable) to Frozen (shared) and not Disabled on foreign read (read through a pointer derived from the base pointer) ↩︎

1 Like

We haven't even written the Tree Borrows paper yet! Where did you get the time machine from? :wink:

2 Likes

I didn't know that! I read this thing. It is about Tree Borrows and it looks kinda like a paper, so...

2 Likes

Ah, fair. :slight_smile: That's Neven's internship report. It's a bit light on details for a paper in this field. For comparison, here's the Stacked Borrows paper.