Cannot use mutable referene as a (generic) return type?

[kajacx]

I was having some problems with the borrow checker and I managed to distill the issue into just a few lines of code: (Rust Playground)

trait MyMutGetter<T> {
    fn gimme_mut(&mut self) -> T;
}

// not ok
impl<'a> MyMutGetter<&'a mut i32> for Vec<&'a mut i32> {
    fn gimme_mut(&mut self) -> &'a mut i32 {
        *(self.get_mut(0).unwrap())
    }
}

So, why is this not ok? The immutable variant works fine. Notice that I am not returning a reference to the vector, but a value from the vector, which is a reference to somewhere else, explained by this drawing (edited):

You can even drop the vector after you get the reference and it would still be ok, no? And if the compiler cannot check that even the "target" i32 doesn't go out of scope, why is immutable ref ok?

Finally, changing the trait signature to fn gimme_mut(&mut self) -> &mut T; isn't really and option, because some implementators will return computed values (like String for example), so referencing them would be impossible.

[kornel]

It's not about dangling references. It's about &mut references being exclusive. The program must guarantee it's impossible to get two exclusive references to the same data.

However, the &mut self isn't declared to be related to the lifetime of the returned value, so it isn't "locked" for duration of use of the returned value. It could be a completely unrelated object, and therefore it could be used multiple times, which would result in violation of exclusivity of the returned value (this lifetime setup is used for vec.iter_mut(), but the iterator returns a different item each time).

This code works with shared references, because in that case the compiler doesn't have to ensure exclusivity and can implicitly and automagically relax the lifetimes. &mut is much more inflexible.

Generally Rust can't abstract over mutability, has limited ability to abstract over ownership, and the generics syntax lacks ability to express all of the lifetime edge cases, so you will have to make a less abstract trait:

trait MyMutGetter<T> {
    fn gimme_mut(&mut self) -> &mut T;
}

impl<'a> MyMutGetter<i32> for Vec<&'a mut i32> {
    // This means: fn gimme_mut<'temp>(&'temp mut self) -> &'temp mut i32,
    // so gimme_mut can't be called again as long as the returned value is accessible
    fn gimme_mut(&mut self) -> &mut i32 { 
        *(self.get_mut(0).unwrap())
    }
}

[quinedot]

It may help to dive into some rules around exclusive references to understand what the problem was.

I think this will be easier to talk about if we look at a version without the trait. The MyVec<&i32> and MyVec<&mut i32> implementations work the same, except for the last step, where you dereference. ^[1]

That is,

• You can go from &'outer [mut] &'inner i32 to &'inner i32, but
• You can't go from &'outer [mut] &'inner mut i32 to &'inner [mut] i32
  • You can only get a &'outer [mut] i32

If you change the MyVec<&mut i32> implementations to return &'outer mut i32, they work.

---

So, why is that? It's a combination of a few things:

• &'outer [mut] only grants access to the underlying object within the 'outer lifetime. So as long as you're going through &'outer, you only use any objects you reach for 'outer, no longer.

• Shared references &Whatever implement Copy, so you can copy a &'inner i32 out from behind a wrapping &'outer [mut] &'inner i32. Once you do this, you're no longer going through the &'outer [mut] reference, so you're free to use / return the &'inner i32. This happens automatically when it needs to, like in the example.

• Exclusive references &mut Whatever never implement Copy, so you always have to go through the outer wrapping reference. There's no way to get a &'inner mut i32 while it's still behind the &'outer reference.

  • You can't get an &'inner i32 either, because first you would need to get the &'inner mut i32 to reborrow from.
  • If you could get an &'inner mut i32, this would be a way to extend a borrow, which is unsound!

To demonstrate that last point, let's say I had something like...

fn foo(mut my_vec: MyVec<&mut i32>) {
    let middle: & /* 'middle */ mut MyVec<&mut i32> = &mut my_vec;
    // We call the method with a short `'outer` lifetime and get back
    // an `&'inner mut i32` to something still in the `MyVec`
    let inner: & /* 'inner */ mut i32 = middle.gimme_mut();

    // 'outer has now ended, so `middle` can be used again and is
    // supposed to have exclusive access

    let value = *middle.0[0];
    *inner = value + 1; // But it doesn't actually have mutable access!
    assert_eq!(value, *middle.0[0]);
}

By the rules of the language, there's no way value could have changed from *middle.0[0] by manipulating inner. ^[2] Other Rust code and the compiler itself is allowed to rely on these rules for soundness, and they do.

More generally, anything that violates the "&mut are exclusive" aliasing rules is considered instant UB by definition of the language.

---

Is there ever a way to get a &'inner mut out from behind a &'outer mut, say? Yes, but you have to move it out, you can't just copy it out.

For example, this works because you've removed the &'inner mut i32 from the Vec entirely. So there's no way to examine the reachable value through middle in this case, for example.

    // The type of `self` is `&'outer mut MyVec<&'inner mut i32>`
    fn gimme_mut<'outer>(&'outer mut self) -> &'inner mut i32 {
        self.0
            .pop()      // Option<&'inner mut i32>
            .unwrap()   // &'inner mut i32
    }

A similar situation arises if you try to implement a mutable iterator over slices yourself.

---

There are other ways your trait could be modified if @kornel's suggestion doesn't work for you, but it's not clear what your actual goals are (and the other ways tend to be more complicated), so I'll leave it here for now.

---

1. And gimme_mut for the former still returns a shared &'inner i32, because you can't turn that into a &'inner mut i32. The point of including it was that whether the outer reference is mutable or not doesn't matter here. ↩︎

2. In case someone jumps in with a self-modifying deref, etc, I mean given the types used here. ↩︎

[kajacx]

Yes, I was thinking about it some more yesterday, and I came up with a counter-example as well: Rust Playground

Thank you for the thorough explanation, it made things clearer. The problem is that you cannot "copy" the inner mutable reference from behind an outer (mutable) reference, you can only re-borrow it as an outer reference.

Also, if I understand correctly, the inner lifetime is a superlifetime of the outer lifetime in this case.

So, what to do?

Fist, let's explain what I was trying to do in the first place. I was trying to make a variant of retain, that would give you ownership of the items that you are filtering out. This is what I came up with:

pub enum Retain<F> {
    Keep,
    Take(F),
}

trait RetainWith<T> {
    fn retain_with<F: FnOnce(T)>(&mut self, f: impl FnMut(&T) -> Retain<F>);
}

Instead of returning a boolean (keep/discard), you return an enum and if you want to remove the item, you take it by the means of the function what will receive the item. Rust Playground

First I used lambdas, and that didn't work, so then I tried implementing them manually, and that still didn't work (that's when I discovered this issue), so I just gave up and put the value behind Rc<RefCell> and now it works, but it kind of sucks.

Needless to say, you would be better of using drain filter for this, but still, I wanted to see if it could be done.

Any solutions?

@kornel 's solution doesn't really work for me, because as I said, I want the implementators to be able to return a computed value. Moreover, some implementations need to return a computed value that contains the (inner) reference in it's data!

As you explained, this is possible when not using the trait, with an annotation like this:
fn gimme_mut<'outer>(&'outer mut self) -> &'outer mut i32
or even
fn gimme_mut<'outer>(&'outer mut self) -> SomeStruct<&'outer mut i32>
for a computed value that contains the inner reference.

To be cleared, I want to return the inner reference, but with the outer lifetime, which is possible in both of these 2 examples above.

But it is not possible when the return type is generic and it's not aware that one of the implementators might want to return SomeStruct for example. That is currently impossible in Rust if I understand correctly.

But does it have to be? What about a syntax like this:

fn gimme_mut<'a>(&'a mut self) -> T + 'a;

It would tell the compiler that the returned value might contain a reference to self and therefore the object must not be used until the returned value is dropped. It would work the same as &mut T in that way, except it would not force the return type to be &mut T; it could be anything that contains &mut T, or something that has no reference at all!

There probably are more practical / idiomatic solutions to problems where this would be useful, but still, it's important to think about these problems and how they could be solved.

[quinedot]

@kajacx

First I used lambdas, and that didn't work, so then I tried implementing them manually, and that still didn't work (that's when I discovered this issue), so I just gave up and put the value behind Rc<RefCell> and now it works, but it kind of sucks.

Can you give an example of something that didn't work as it relates to the OP? And one that returns a computed value that contains the inner reference?

(I don't see the direct connection as if you returned a closure that captured a reference to the data, there's no way you could give up ownership of the referenced data back to that same closure. Moving or otherwise using something borrowed invalidates all borrows, which would invalidate the closure.)

But does it have to be? What about a syntax like this:

fn gimme_mut<'a>(&'a mut self) -> T + 'a;

It would tell the compiler that the returned value might contain a reference to self and therefore the object must not be used until the returned value is dropped. It would work the same as &mut T in that way, except it would not force the return type to be &mut T; it could be anything that contains &mut T, or something that has no reference at all!

That's one of the alternatives I was refering to, and it's called GATs (Generic Associated Types). It might work like so with your OP. But note here that you're still only getting the outer lifetime (both in the playground and in your suggested syntax, where the outer lifetime is 'a).

GATs are in the pipeline to stabilize later this year. (But you can emulate lifetime GATs on stable today.)

Generalizing over ownership or borrowing types means you need some sort of generic type constructor (something where you input a lifetime and get out a concrete type, which might be borrowed ^[1] or might be owned ^[2]). Rust's generic type parameters are never type constructors; instead, the way you get a generic type constructor is to use GATs, or to emulate GATs with helper traits.

---

1. use the lifetime ↩︎

2. independent of the lifetime ↩︎

[kajacx]

Ok, so I have been able to make some progress with a somewhat realistic example: mutable iterators. Image a function that needs to take a "mutably iterable" thing and mutably iterate over it multiple times. Something like this: Rust Playground

trait MutIterable<'a, T: 'a> {
    fn get_iter_mut(&'a mut self) -> T;
}

fn add_numbers<'a, I>(collection: &'a mut impl MutIterable<'a, I>)
where I: Iterator<Item = &'a mut i32> + 'a {
    collection.get_iter_mut().for_each(|value| *value += 2);
    collection.get_iter_mut().for_each(|value| *value += 3);
}

But it only works if you iterate over the collection once (you need to comment the second line). The iterator is dropped after the first for_each finishes, so why is it still blocking the collection? I have tried wrapping each line in a {} block to try and force a new scope with with no success.

I also tried splitting the lifetimes in the annotation like this:

fn add_numbers<'a, 'b: 'a, I>(collection: &'b mut impl MutIterable<'a, I>)
where I: Iterator<Item = &'a mut i32> + 'b {
    collection.get_iter_mut().for_each(|value| *value += 2);
    //collection.get_iter_mut().for_each(|value| *value += 3); // still an error when uncommented
}

but with no success. TBH the "trait + lifetime" bound is still a bit new to me. I get the problem it is trying to solved (it is saying "this data may not live longer than 'lifetime), but I still do not understand it fully.

[H2CO3]

@kajacx

But it only works if you iterate over the collection once (you need to comment the second line). The iterator is dropped after the first for_each finishes, so why is it still blocking the collection?

Because you told it to do so Here:

&'a mut impl MutIterable<'a, I>

You say that the lifetime of the reference must be the same as the lifetime of some other reference in the inner type, i.e. the referent must be borrowed for its whole lifetime. This is a well-recognized antipattern. You must never require such an equality. (Incidentally, if you ever find yourself writing &'a mut self, that's also 99% sure to be wrong.)

Accordingly, if you remove the erroneous lifetime constraint, it works:

trait MutIterable<T> {
    fn get_iter_mut(&mut self) -> T;
}

fn add_numbers<'a, T, I>(collection: &mut T)
where
    T: MutIterable<I>,
    I: Iterator<Item = &'a mut i32>
{
    collection.get_iter_mut().for_each(|value| *value += 2);
    collection.get_iter_mut().for_each(|value| *value += 3);
}

but at this point this is really just a very convoluted way of writing &mut T: IntoIterator<Item = &'a mut i32>.

[kajacx]

Can you give an example of something that didn't work as it relates to the OP?

Sure, here is the original version that used lambdas (closures to be exact): Rust Playground I added RefCell and it actually works, but doesn't work without it.

And one that returns a computed value that contains the inner reference?

Yes, that would be the "manually implemented Fn trait" one, here: Rust Playground

The important bit is here:

impl<'a> FnOnce<(&String,)> for Collector<'a> {
    type Output = Retain<CollectorPush<'a>>;

Collector implements FnOnce (and FnMut), whose output type has no knowledge of lifetimes. But the output needs to contain a reference to the data that Collector has, namely to the same &'a mut Vec<String> string. The output is Retain<CollectorPush<'a>>, a computed value that needs the reference to the underlying data.

Example code:

 impl<'inner, 'arg> FnMut<(&'arg String,)> for Collector<'inner> {
     type Output = Retain<CollectorPush<'inner>>; // forced to use 'inner, even it should really be 'outer
   //type Output = Retain<CollectorPush<'outer>>; // syntax error, obviously
     fn call_mut<'outer>(&'outer mut self, args: (&'arg String,)) -> Self::Output { ... }
 }

However, signature of FnMut makes it impossible to return data with the outer lifetime, and because the inner reference is mutable, I cannot move (copy) it out of self, I could only re-borrow it. But then it would have the outer lifetime, which the compiler prohibits, because of the users of FnMut don't expect it.

I will now try the option with Generic Associated Types and see if it gets me anywhere.

[H2CO3]

The closure example is actually the purest form of your problem, and it exposes the essence of why what you want doesn't work.

The problem is that the inner closure tries to reference something that is outside even the outer closure, i.e. the outer one has to "inherit" the lifetimes of the inner one. That doesn't work because the outer one is the predicate that gets called upon every iteration, but in the previous iteration, the inner one had mutable access, with the same lifetime, to the same variable. Therefore this code would lead to mutable aliasing, and the problem is not really about stuff not living long enough. This is further corroborated by the fact that you can make the compiler happy by using RefCell only without Rc.

So if you want to keep the API as-is, you'll need some form of interior mutability, I suspect. But you might be better off redesigning the API so you don't really need this. I'm trying to think of a better way to express the same capabilities.

[kajacx]

You say that the lifetime of the reference must be the same as the lifetime of some other reference in the inner type, i.e. the referent must be borrowed for its whole lifetime. This is a well-recognized antipattern. You must never require such an equality. (Incidentally, if you ever find yourself writing &'a mut self , that's also 99% sure to be wrong.)

Yes, having everything be 'a looks is really silly, and that's what I wanted to fix by separating it into 2 different lifetimes 'a and 'b, but I will have to look at it in more depth to get it right.

In the mean time, i tried both of your code snippets, and I couldn't get either of them to work. The first one gives me the same error as always and the second one says that it cannot figure out the generic types (and it I specify them, it complains anyway).

Can you please provide a full example with executable main so that I know how to use these functions? Thanks.

[H2CO3]

The type parameter <'a> is superfluous. (I guess it was a remnant of your original signature that I failed to remove, because the compiler didn't complain without me actually having called the function.) The whole point of an iterator over a collection is that it returns items with the same lifetime as the lifetime of the collection (and I should have caught this). Those can't possibly be independent if you want references to items in the collection (because the collection has to outlive references to its elements so that no dangling reference is created).

Accordingly, this fixed version compiles and runs:

fn add_numbers<T>(collection: &mut T)
where
    for<'b> &'b mut T: IntoIterator<Item = &'b mut i32>,
{
    collection.into_iter().for_each(|value| *value += 2);
    collection.into_iter().for_each(|value| *value += 3);
}

fn main() {
    let mut numbers = vec![5, 7, 2];
    add_numbers(&mut numbers);
    println!("{:?}", numbers);
}

---

In the meantime, I figured you could just split up the two closures in your example instead of nesting them?

trait RetainWith<T> {
    fn retain_with<P, F>(&mut self, predicate: P, callback: F)
    where
        P: FnMut(&mut T) -> bool,
        F: FnMut(T);
}

impl<T> RetainWith<T> for Vec<T> {
    fn retain_with<P, F>(&mut self, mut predicate: P, mut callback: F)
    where
        P: FnMut(&mut T) -> bool,
        F: FnMut(T),
    {
        let mut index = 0;
        while index < self.len() {
            if predicate(&mut self[index]) {
                index += 1;
            } else {
                callback(self.remove(index));
            }
        }
    }
}

fn main() {
    let mut texts = vec!["Hello".to_string(), "world".to_string(), "foo".to_string()];
    let mut collected = Vec::new();

    texts.retain_with(
        |item| item.len() < 5,
        |item| collected.push(item)
    );

    println!("{:?}", texts);
    println!("{:?}", collected);
}

[kajacx]

The whole point of an iterator over a collection is that it returns items with the same lifetime as the lifetime of the collection [...]. Those can't possibly be independent if you want references to items in the collection (because the collection has to outlive references to its elements so that no dangling reference is created).

Yes, I'm not trying to return a reference with independent lifetime to the collection, I'm looking at way to put references to a computed type in a trait implementation. I managed to create a working example ( Rust Playground ) with this pattern:

trait Processor<'a, T: 'a> {
    fn process(&'a self) -> T;
}

It seems that this time, I can call the process function twice. However, I will have to try and see how it would work if thigs were mutable.

Accordingly, this fixed version compiles and runs:

Thank you for the example. I have never used the for<'b> syntax before, I will have to look more into it. Do you think the first example can be fixed as well?

In the meantime, I figured you could just split up the two closures in your example instead of nesting them?

Yes, I thought of that. While possible, I wanted to see if the original way could work, just to understand Rust better. Moreover, I think it's slightly more idiomatic to tie how the item will be taken directly to the decision of whether to take item or not, instead of having those 2 things as 2 separate parameters.

And in an extremely niche scenario, there might be some computation going both into the decision, and into the storing of the taken item, which you would have to do only once with the "retain enum" option, since the FnOnce can just take the owership of the already computed value.

[H2CO3]

@kajacx

And in an extremely niche scenario, there might be some computation going both into the decision, and into the storing of the taken item, which you would have to do only once with the "retain enum" option, since the FnOnce can just take the owership of the already computed value.

In my code, although both functions are FnMut, the storing callback still gets ownership of the removed value. You can just as easily make a decision in that callback about e.g. where to store it. (Do note that whether a closure has a by-value or by-ref parameter is orthogonal to whether it is FnOnce or FnMove. Which trait it implements only depends on its captures, not in its explicit arguments, and in this case, it simply can't be merely a FnOnce, because it is called in a loop.)

@kajacx

Do you think the first example can be fixed as well?

Possibly; I haven't looked into it since it feels superfluous in the presence of an IntoIter impl for &mut Collection.

[quinedot]

@kajacx

Sure, here is the original version that used lambdas (closures to be exact): Rust Playground I added RefCell and it actually works, but doesn't work without it.

With the closure version, without RefCell, you could call the outer function multiple times without calling the returned value, and they would simultaneously hold captured &mut references. So yes, you would need something like a GAT to flag that the Retain is capturing the borrow of &mut self in the FnMut trait... which is not how those traits were designed. The return type of a FnMut implementer is independent of the borrow of self. This is what the error is indirectly getting at -- FnMut closures can't hand out references to things they've captured that are tied to the lifetime of the call (the &mut self borrow of the FnMut implementor). ^[1]

Playground with a GAT sketch. Or, as you found, you can use RefCell as that lets you return something independent of the capture lifetime.

---

I understand now that by "calculating something", you meant within self's fields, not within the &T argument. The problem with the "manually implemented Fn trait" is the same -- there's no issue with FnOnce really, since you're consuming self. But Fn and FnMut use the same, singular return type, despite being higher-ranked over their &self/&mut self argument. So you can't implement the GAT-like, higher-ranked pattern to return something with a &mut in it having the same lifetime as the outer borrow of self (since you can't preserve the inner lifetime through the outer lifetime).

I think you basically wish we had FnMutGat or something / more powerful closures.

---

1. So usually &mut references. You can hand out shared & references by creating a copy -- with an inner lifetime, not the outer &mut self lifetime. ↩︎

[kajacx]

@kajacx

And in an extremely niche scenario, there might be some computation going both into the decision, and into the storing of the taken item, which you would have to do only once with the "retain enum" option, since the FnOnce can just take the ownership of the already computed value.

In my code, although both functions are FnMut, the storing callback still gets ownership of the removed value. You can just as easily make a decision in that callback about e.g. where to store it.

Yes, you can recompute the value again, but that may be inefficient. Example here. Now I can't honestly imagine a scenario where this wouldn't be a bad design, but this would be impossible with 2 separate FnMut parameters.

Also looking at this code:

fn add_numbers<T>(collection: &mut T)
where
    for<'b> &'b mut T: IntoIterator<Item = &'b mut i32>,
{
    collection.into_iter().for_each(|value| *value += 2);
    collection.into_iter().for_each(|value| *value += 3);
}

I was a bit surprised, because I have looked at IntoIterator before, and saw that it is taking ownership of self, so I though it is just going to eat my &mut reference since it doesn't implement copy, but it does actually get borrowed (not moved) into the method, even thought the signature is self and not &mut self.

I guess you learn something new every day.