15

I'm trying to navigate a recursive data structure iteratively in order to insert elements at a certain position. To my limited understanding, this means taking a mutable reference to the root of the structure and successively replacing it by a reference to its follower:

type Link = Option<Box<Node>>;

struct Node {
    next: Link
}

struct Recursive {
    root: Link
}

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;
        while let Some(ref mut node) = *anchor {
            anchor = &mut node.next;
        }
        anchor
    }
}

(Rust playground link)

However, this fails:

error[E0499]: cannot borrow `anchor.0` as mutable more than once at a time
  --> src/main.rs:14:24
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ^^^^^^^^^^^^
   |                        |
   |                        second mutable borrow occurs here
   |                        first mutable borrow occurs here
...
18 |     }
   |     - first borrow ends here

error[E0506]: cannot assign to `anchor` because it is borrowed
  --> src/main.rs:15:13
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ------------ borrow of `anchor` occurs here
15 |             anchor = &mut node.next;
   |             ^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `anchor` occurs here

error[E0499]: cannot borrow `*anchor` as mutable more than once at a time
  --> src/main.rs:17:9
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ------------ first mutable borrow occurs here
...
17 |         anchor
   |         ^^^^^^ second mutable borrow occurs here
18 |     }
   |     - first borrow ends here

This makes sense as both anchor and node refer to the same structure, but I actually don't care about anchor any more after destructuring it.

How could back() be implemented correctly using safe Rust?

18

It is possible... but I wish I had a more elegant solution.

The trick is NOT to borrow from anchor, and therefore to juggle between two accumulators:

  • one holding the reference to the current node
  • the other being assigned the reference to the next node

This leads me to:

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;

        loop {
            let tmp = anchor;
            if let Some(ref mut node) = *tmp {
                anchor = &mut node.next;
            } else {
                anchor = tmp;
                break;
            }
        }

        anchor
    }
}

Not exactly pretty, but this is something the borrow checker can get behind so ¯\_(ツ)_/¯.

@ker has improved on this by creating an unnamed temporary:

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;

        loop {
            match {anchor} {
                &mut Some(ref mut node) => anchor = &mut node.next,
                other => return other,
            }
        }
    }
}

The trick here is that using {anchor} moves the content of anchor into an unnamed temporary on which the match executes. Therefore, in the match block we are not borrowing from anchor but from the temporary, leaving us free to modify anchor. See the related blog post Stuff the Identity Function Does (in Rust).

  • Awesome! Just so that I understand what's happening here: 1) anchor has the initial reference 2) tmp is moved from anchor, which means that anchor ist not a reference any more 3) tmp can be safely borrowed from as it is dropped as soon as the loop iteration ends – Fabian Knorr Jun 23 '16 at 9:18
  • 1
    The most awesome, here, is that I initially forgot the anchor = tmp; in the else branch and rustc raised an error for it... anyway, yes the idea is that you cannot re-assign anchor while it is borrowed, so we transfer the reference to tmp and then borrow tmp to assign anchor. – Matthieu M. Jun 23 '16 at 9:23
  • This can actually be written pretty concisely because we can call is_some() on anchor before moving it. I've edited your post. – Fabian Knorr Jun 23 '16 at 9:35
  • Here's a version of your solution without temporaries or unwrap: play.rust-lang.org/… – oli_obk Jun 23 '16 at 10:01
  • 2
    @FabianKnorr: I don't like using unwrap where I can avoid it, because while it is safe, it's also a source of (potential) crash. – Matthieu M. Jun 23 '16 at 11:55
8

You can use recursion to satisfy the borrow checker. This has the disadvantage of creating a stack frame for every item in your list. If your list is long, this will definitely run into a stack overflow. LLVM will optimize the Node::back method into a loop (see the LLVM IR generated on the playground)

impl Node {
    fn back(&mut self) -> &mut Link {
        match self.next {
            Some(ref mut node) => node.back(),
            None => &mut self.next,
        }
    }
}

impl Recursive {
    fn back(&mut self) -> Option<&mut Link> {
        self.root.as_mut().map(|node| node.back())
    }
}
7

The original code works as-is once non-lexical lifetimes are enabled:

#![feature(nll)]

type Link = Option<Box<Node>>;

struct Node {
    next: Link
}

struct Recursive {
    root: Link
}

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;
        while let Some(node) = anchor {
            anchor = &mut node.next;
        }
        anchor
    }
}

fn main() {}

Non-lexical lifetimes increases the precision of the compiler's borrow checker, allowing it to see that the mutable borrow of anchor is no longer used. We can also simplify the keywords in the if let due to recent language changes.

2

It works:

fn back(&mut self) -> &mut Link {
    let mut anchor = &mut self.root;
    while anchor.is_some(){
        anchor = &mut {anchor}.as_mut().unwrap().next;
    }
    anchor
}

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.