Lifetime of a borrow gets extended by trait

help
1

I am writing an API for sparse arrays for my project. It looks like this:

// An non-contiguous array. E.g., an array with indices [0-99] and [200-299] valid, but not [100-199].
trait SparseArray<'a> {
    type Item: 'a;
    
    /* Using Borrow here so that I can return either an owned type or a borrowed type.
     * For example, if I implement this using a HashMap, I will need to return a vector
     * of references into the HashMap which are not contiguous. But if I implement this
     * using a vector, I can just return a slice of the vector.
     */
    type Slice: Borrow<[&'a Self::Item]>;
    
    // get a contiguous block of the array, if the range is contiguous within the array
    fn get_block(&'a self, range: Range<usize>) -> Option<Self::Slice>;
    
    // set a contiguous block of the array, if start..start+values.len() is contiguous within the array
    fn set_block<I, E>(&mut self, start: usize, values: I) -> Result<(), ()>
    where
        I: IntoIterator<IntoIter = E>,
        E: ExactSizeIterator<Item = Self::Item>;
    
    // check if the given range of indices is contiguous within the array
    fn contains(&'a self, range: Range<usize>) -> bool;
}

I also wrote a module-level function which writes to a sparse array:

fn write_array<'a, A>(from: &[u8], to: &'a mut A, start: usize) -> Result<(), ()>
where
    A: SparseArray<'a, Item = u8>
{
    if !to.contains(start..start+from.len()) {return Err(());}
    to.set_block(start, Vec::from(from))
}

When I tried to compile this, I got the following error:

error[E0502]: cannot borrow `*to` as mutable because it is also borrowed as immutable
  --> src/lib.rs:35:5
   |
29 | fn write_array<'a, A>(from: &[u8], to: &'a mut A, start: usize) -> Result<(), ()>
   |                -- lifetime `'a` defined here
...
34 |     if !to.contains(start..start+from.len()) {return Err(());}
   |         ------------------------------------
   |         |
   |         immutable borrow occurs here
   |         argument requires that `*to` is borrowed for `'a`
35 |     to.set_block(start, Vec::from(from))
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

For more information about this error, try `rustc --explain E0502`.
error: could not compile `playground` (lib) due to previous error

I stared at this for a little bit and noted the message argument requires that *to is borrowed for 'a. Which argument? Maybe the &'a self argument to contains():

fn contains(&'a self, range: Range<usize>) -> bool;

Sure enough, when I removed the lifetime from this signature, the error disappeared:

fn contains(&self, range: Range<usize>) -> bool;

First, what is happening here? In the documentation of E0502, the immutable borrow let y = &a is still in scope for the call to bar(a) clearly because of its use in the following println!("{}", y). However in my case, I don't see why the immutable borrow of to needs to remain in scope for the call to to.set_block() if we can just drop the immutable borrow and create a new mutable one. I even tried to be explicit about this:

fn write_array<'a, A>(from: &[u8], to: &'a mut A, start: usize) -> Result<(), ()>
where
    A: SparseArray<'a, Item = u8>
{
    {
        if !to.contains(start..start+from.len()) {return Err(());}
    }
    to.set_block(start, Vec::from(from))
}

But got the same error. So the error seems to be related to the lifetime on &'a self in contains(), but I'm not sure how.

Second, if the error is related to the signature of contains(), then I think the compiler should have pointed me to the definition of contains.

2 
fn write_array<'a, A>(from: &[u8], to: &'a mut A, start: usize) -> Result<(), ()>
where
    A: SparseArray<'a, Item = u8>

to is a &'a mut SparseArray<'a, Item = u8> and contains takes a &'a Self, so in order to call contains you have to reborrow *to as immutable for all of 'a.

This particular error will go away if you don't require &'a Self:

-    fn contains(&'a self, range: Range<usize>) -> bool;
+    fn contains(&self, range: Range<usize>) -> bool;

You may run into other problems as lifetime-carrying traits can be a bit tricky, as can abstracting over owned and borrowed data structures.

(Note that parameters of traits are always invariant.)

Looking at this comment:

    /* Using Borrow here so that I can return either an owned type or a borrowed type.
     * For example, if I implement this using a HashMap, I will need to return a vector
     * of references into the HashMap which are not contiguous. But if I implement this
     * using a vector, I can just return a slice of the vector.
     */

I guess you mean you have a hashmap of owned u8 and you're going to collect a bunch of references in a Vec to return. Which implies to me you would want a Vec<u8> for the vector implementation. But you can't return a slice of references from a Vec of owned u8. You would need a Vec<&'a u8> for that.

1 Like
3

I'm still not confident in the overall design here (as per my note on your comment block), but you may avoid some unpleasantness if this is a viable design for you:

// No lifetime on the trait
trait SparseArray {
    type Item;
    // This is now a GAT
    type Slice<'a>: Borrow<[&'a Self::Item]> where Self: 'a;

    // Utilizes GAT    
    fn get_block(&self, range: Range<usize>) -> Option<Self::Slice<'_>>;

    fn set_block<I, E>(&mut self, start: usize, values: I) -> Result<(), ()>
    where
        I: IntoIterator<IntoIter = E>,
        E: ExactSizeIterator<Item = Self::Item>;
   
    fn contains(&self, range: Range<usize>) -> bool;
}

// No lifetime bounds needed
fn write_array<A>(from: &[u8], to: &mut A, start: usize) -> Result<(), ()>
where
    A: SparseArray<Item = u8>
1 Like
4

This did indeed make the badness go away! What is the difference between my trait and yours?

5

I see what you mean. I chose the bound Borrow under the assumption that I would be able to return a slice of references. Since that's not the case I do need to rethink the design of this now. Perhaps return an Iterator instead.

6

T: MyTrait is roughly the same as T: for<'any> YourTrait<'any>, as the GAT and signature of get_block requires the implementor to handle any possible lifetime where Self is valid. If all your implementations look like impl<'a> YourTrait<'a> for Something, a GAT may be what you want.

More generally, I think there are also some inferred bounds differences/issues around for<'any>, but those wouldn't have been a problem for your use case as I understand it (where Self: 'static probably). The GAT isn't object safe, but the trait already wasn't object safe due to the type generic set_block method. GATs and higher-ranked bounds like

T: MyTrait, for<'any> <T as MyTrait>::Slice<'any>: ExtraBound

still have some rough edges, depending on how complicated your usage the trait ends up being.

The GAT avoids the need to make the lifetime a parameter of the trait, which is nicer to work with generally, makes it less likely for you to mention it unnecessarily elsewhere. With your trait, if you do mention a specific lifetime like 'a instead of using for<'any>, the lifetime will be invariant (due to being a trait parameter) which is less flexible from a borrow checker perspective.

1 Like
7

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.