Pre-Pre-RFC: Noncontinuous Lifetime Parameters

Consider the following code:

struct VecWrapper<'a, T>(&'a mut Vec<T>);
impl<'a> VecWrapper<'a> {
  pub fn new(vec: &'a mut Vec<T>) -> Self { VecWrapper(vec) }
  pub fn something(&self){ ... }
}

let mut vec = vec![1];
let vec_wrap = VecWrapper::new(&mut vec);
vec_wrap.something();
vec.push(1);
vec_wrap.something();

This code does not compile, because push requires a mutable reference at the same time vec_wrap has one.

However, there is no inherent reason this wouldn't work; it should, in theory, be equivalent to

let mut vec = vec![1];
VecWrapper::new(&mut vec).something();
vec.push(1);
VecWrapper::new(&mut vec).something();

Which compiles and runs sucessfully.

Why, then, is this pattern not this allowed?

To answer this, consider this code:

struct VecWrapper2<'a, T>(&'a mut T);
impl<'a> VecWrapper2<'a> {
  pub fn new(vec: &'a mut Vec<T>) -> Self { VecWrapper2(&mut vec[0]) }
  pub fn something(&self){ ... }
}

let mut vec = vec![1];
let vec_wrap = VecWrapper2::new(&mut vec);
vec_wrap.something();
vec.push(1); // reallocates the array
vec_wrap.something(); // use after free

Here, this is clearly not ok -- and the compiler informs us of this with a compile error (in fact, the same error that blocked the first example).

However, it would be useful for a number of things if the original code compiled.

To address this, we'll consider a new language feature: 'noncontinuous lifetime parameters'. Noncontinuous lifetime parameters are defined with the following (placeholder) syntax:

//                 v non continuous lifetime parameter
struct VecWrapper<''a, T>(&''a mut Vec<T>);
//                          ^ usage

Noncontinuous lifetimes, as the name implies, do not have to be continuous -- they can have breaks in them.

Noncontinuous lifetime parameters must also obey these additional rules:

  1. Noncontinuous lifetime parameters are not assignable to continuous lifetime parameters (though continuous lifetime parameters are assignable to noncontinuous lifetime parameters)
  2. Noncontinuous lifetime parameters are not preserved in refutable patterns

We'll now edit the previous example to use noncontinuous lifetime parameters:

struct VecWrapper<''a, T>(&''a mut Vec<T>);
impl<''a> VecWrapper<''a> {
  pub fn new(vec: &''a mut Vec<T>) -> Self { VecWrapper(&mut vec) }
  pub fn something(&self){ ... }
}

let vec = vec![1];
let vec_wrap = VecWrapper::new(&mut vec);
vec_wrap.something();
vec.push(1);
vec_wrap.something();

Unlike before, there are never two simultaneous mutable references, because the lifetime parameter in VecWrapper only encompasses the two .something() calls -- there's a gap around the .push(). Thus, this code compiles successfully.

On the other hand, if we try to use noncontinuous lifetime parameters in VecWrapper2, we'll get a compile error:

struct VecWrapper2<''a, T>(&''a mut T); // ok
impl<''a> VecWrapper2<''a> {
  pub fn new(vec: &''a mut Vec<T>) { VecWrapper2(&mut vec[0]) } // compile error
  pub fn something(&self){ ... }
}

This errors because of rule #1 -- the noncontinuous lifetime parameter ''a isn't assignable to the continuous lifetime parameter defined in the IndexMut trait.

Rules #1 and #2 make this feature safe. There are 4 primitive operations to manipulate references:

  • Accessing struct properties or pattern matching on structs
  • Pattern matching on enums
  • Accessing union variants (unsafe)
  • Doing stuff with raw pointers (unsafe)

For the first one, it's ok to preserve a noncontinuous lifetime, as the struct field will always exist.

For the second, it is not ok to preserve a noncontinuous lifetime, as variant fields can be invalidated if the enum value is changed to a different variant. This is covered by rule #2.

The last two are already unsafe, so it's up to the implementor to determine if they can safely preserve noncontinuous lifetimes. These are thus covered by rule #1. If the implementor determines that it is safe to preserve a noncontinuous lifetime, they use a noncontinuous lifetime parameter. Otherwise, they should leave it as a continuous lifetime parameter, and the compiler knows to statically check that a noncontinuous lifetime is not assigned to it.

This feature would allow for many new patterns to compile. For example, consider the following code:

let mut val = 0;
let inc = || val += 1;
let dec = || val -= 1;
inc();
inc();
dec();
inc();

This is currently a compile error, as inc and dec need to share a mutable reference to val.

If noncontinuous lifetimes were added, closures could always borrow their captures noncontinuously, allowing the above code to compile. inc's capture's lifetime would span its definition and the three calls to it, with a gap around dec's definition and its singular call. dec's capture's lifetime would span its definition and its call, and have a gap around the first two inc calls.

5 Likes

This UB, but Miri currently doesn't catch it if something doesn't actually use the vec reference as miri currently only applies protectors for top level references amd not references inside structs. If I add self.0.len() to the body of something miri gives an UB error:

https://play.rust-lang.org/?version=stable&mode=release&edition=2021&gist=ca7e0b3330dd8860f785f53e83a88d05

error: Undefined Behavior: trying to reborrow for SharedReadOnly at alloc1161, but parent tag <2403> does not have an appropriate item in the borrow stack
  --> src/main.rs:6:28
   |
6  |   pub fn something(&self){ self.0.len(); }
   |                            ^^^^^^^^^^^^ trying to reborrow for SharedReadOnly at alloc1161, but parent tag <2403> does not have an appropriate item in the borrow stack
   |
   = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
   = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
           
   = note: inside `VecWrapper::<i32>::something` at src/main.rs:6:28
note: inside `main` at src/main.rs:14:5
  --> src/main.rs:14:5
   |
14 |     vec_wrap.something();
   |     ^^^^^^^^^^^^^^^^^^^^
[...]

Note that a program running correctly doesn't guarantee the absence of UB. UB is allowed to have any effect including the program running fine using a specific compiler version.

5 Likes

Citation needed. Miri diagnoses this as UB, because &'_ mut guarantees unique access from the time its created to the time of last use (LLVM noalias). Though I suppose &''_ mut wouldn't?

I believe this is the same root desire as the "resumable borrow" problem with async.

With async, though, at least the "parent" borrow which is being used while the "child" borrow is "sleeping" is only used to dispatch back to the "child" borrow, and doesn't touch the same memory that the "child" borrow is currently uniquely borrowing (except for the purpose of shadow state retagging), so it's theoretically less of a deviation than actually using the memory region and violating the noalias attribute.

Good point -- I've edited the original post to remove that statement.

Related thread: Local closures borrowing ergonomics

2 Likes

This is similar to the local closure problem except probably much less motivated, there is no reason not to write this code as

let mut vec = vec![1];
let mut vec_wrap = VecWrapper::new(&mut vec);
vec_wrap.something();
vec_wrap.0.push(1);
vec_wrap.something();

If you can't do the above, but really need to, VecWrapper's api can be easily improved. In the case of closures we have this same problem but we can't even name the wrapped captured items. There is no ergonomic way to improve the api.

Sidenote, I imagine implementing this less with "noncontinuous lifetime parameters" and more with the compiler realizing and substituting in the correct path, so vec.push(1) gets rewritten as vec_wrap.0.push(1) and that works fine. I don't think this is helpful, but it was one of the possible options forward for closures.

Yeah, at the end I show the primary use-case: closures (though there are others). The VecWrapper struct is just a more approachable example.