Mutable reference to tree descendent

[kalimba]

I have a tree structure, for which I've written a find_mut function.

#[derive(Debug)]
struct Tree<'a> {
    children: Vec<Tree<'a>>,
    data: &'a Data,
}

#[derive(Debug)]
struct Data {
    id: u32,
    parent_id: u32,
}

impl<'a> Tree<'a> {
    pub fn new(data: &'a Data) -> Self {
        Self {
            children: vec!(),
            data: data,
        }
    }

    fn find_mut(&mut self, find_id: u32) -> Option<&'a mut Tree> {
        match self.data.id {
            id if id == find_id => Some(self),
            _                   =>
                match self.children
                        .iter_mut()
                        .map(|c| c.find_mut(find_id))
                        .filter(|c| c.is_some())
                        .next()
                {
                    Some(child) => child,
                    None        => None,
                }
        }
    }
}

This appears to work, but renders the calling Tree unusable, so e.g. this is impossible:

let mut tree = ...;
let mut find = tree.find_mut(0x1);

println!("{:#?}", tree);
// > error[E0502]: cannot borrow `tree` as immutable because it is also borrowed as mutable

The above makes sense to me, but I'm curious if my general idea can even work. My intuition is to write code like this:

1. Grab a mutable reference indiscriminately to a Tree or one of its descendents
2. Do work on it
3. Resume using the original Tree

Is this feasible, or am I thinking in the wrong paradigm here?

Playground

[cuviper]

Just change the return value to Option<&mut Tree<'a>>, so the reference has a shorter borrowed lifetime than that of the Tree node itself.

[quinedot]

To explain what's going on in case it wasn't clear, taking lifetime elision into account here:

    fn find_mut(&mut self, find_id: u32) -> Option<&'a mut Tree> {

We get:

    //                      vvvv Tree<'a>
    fn find_mut<'s>(&'s mut self, find_id: u32) -> Option<&'a mut Tree<'s>> {

The argument of &'s mut Tree<'a> (as &mut self) implies 'a: 's, and the return of &'a mut Tree<'s> implies 's: 'a. Together, those imply the lifetimes are actually the same, so we can simplify this further:

    // `&'a mut self` has type `&'a mut Tree<'a>`
    fn find_mut(&'a mut self, find_id: u32) -> Option<&'a mut Tree<'a>> {

The type &'a mut Tree<'a> requires that the struct is mutably (exclusively) borrowed for the rest of its lifetime -- that's why the calling Tree is rendered unusable (beyond the returned value).

In contrast, applying the suggested change is equivalent to

    fn find_mut<'s>(&'s mut self, find_id: u32) -> Option<&'s mut Tree<'a>> {

---

Perhaps you added the 'a to the returned &mut because without any lifetimes specified, you can't compile:

    fn find_mut(&mut self, find_id: u32) -> Option<&mut Tree> {
    // Is short for...
    fn find_mut<'s>(&'s mut self, find_id: u32) -> Option<&'s mut Tree<'s>> {

error[E0308]: mismatched types
  --> src/main.rs:25:41
   |
25 |             id if id == find_id => Some(self),
   |                                         ^^^^ lifetime mismatch
   |
   = note: expected mutable reference `&mut Tree<'_>`
              found mutable reference `&mut Tree<'a>`

It might have been easier to spot if you had initially spelled this out as:

    fn find_mut(&mut self, find_id: u32) -> Option<&mut Tree<'_>> {

To highlight that Tree has a lifetime parameter; if forcing yourself to do this is appealing, you can enable a lint to do so:

#![forbid(elided_lifetimes_in_paths)]

(RFC 2115 aimed to make this required, but other parts of that RFC were dropped and the lint is still allow by default, so I'm not sure if that's going to go anywhere or not.)

Alternatively, you could:

    fn find_mut(&mut self, find_id: u32) -> Option<&mut Self> {

As Self is Tree<'a>, just like it is with &mut self.

CC @matklad Re: this topic.