7

I have a Graph data structure in Rust:

type NodeIndex = usize;

struct Graph {
    nodes: Vec<NodeIndex>,
    edges: Vec<(NodeIndex, NodeIndex)>,
}

I want to iterate over all the nodes inside a function and call a function which mutates the graph using each node as an element, say:

impl Graph {
    fn mutate_fn(&mut self) {
        for node in self.nodes {
            self.mutate_using_node(node);
        }
    }

    fn mutate_using_node(&mut self, node: NodeIndex) {
        // mutate self here
    }
}

Which doesn't work, since I would have more than one mutable reference. I also cannot pass &self, since then I would have a mutable and an immutable reference. How is this handled in Rust?

Kitsu
  • 3,166
  • 14
  • 28
eager2learn
  • 1,447
  • 4
  • 24
  • 47
  • 1
    Does this answer your question? [Why does refactoring by extracting a method trigger a borrow checker error?](https://stackoverflow.com/questions/57017747/why-does-refactoring-by-extracting-a-method-trigger-a-borrow-checker-error) – Stargateur Jul 15 '20 at 14:00
  • What parts of `self` does `mutate_using_node` read, and what does it mutate? – Solomon Ucko Jul 15 '20 at 14:50
  • 1
    @SolomonUcko It reads and mutates only the edges variable. Would it make sense to re-write 'mutate_using_node' as a static method that takes a mutable reference to edges and the node we currently iterate over? – eager2learn Jul 15 '20 at 14:57
  • 2
    I recommend reading [Niko's blog post on interprocedural conflicts](https://smallcultfollowing.com/babysteps/blog/2018/11/01/after-nll-interprocedural-conflicts/) – it covers several general solutions to this kind of problem. – Sven Marnach Jul 15 '20 at 15:51
  • @eager2learn Until [partial borrowing](https://github.com/rust-lang/rfcs/issues/1215) is implemented for methods, that might be the simplest and most efficient solution. You could also try [the `partial_ref` crate](https://crates.io/crates/partial_ref), but I don't know much about it. – Solomon Ucko Jul 15 '20 at 16:12

1 Answers1

1

Well, you indeed cannot do this. I may name two main approaches applicable in general and for you example in particularly

Split out borrowing

That way is probably the hardest and/or the slowest way among others. Just do what borrow-checker want: don't mix up mutable and immutable borrows. For your case that can be as simple as cloning the nodes in mutate_fn:

let nodes = self.nodes.clone();
for node in nodes {
    self.mutate_using_node(node);
}

It's hard to reason without much details, but I think that's the only way to do for that approach. If you're only changing the edges, for example like this:

fn mutate_using_node(&mut self, node: NodeIndex) {
    for e in &mut self.edges {
        if e.0 == node {
            std::mem::swap(&mut e.0, &mut e.1);
        }
    }
}

That you may handle it simply by uniting these functions:

for node in self.nodes.iter().copied() {
    for e in &mut self.edges {
        if e.0 == node {
            std::mem::swap(&mut e.0, &mut e.1);
        }
    }
}

So in general, there's no ultimate step-by-step guide (except maybe copying) for splitting out the code. It do depends on the code semantics.

Interior mutability

That is RefCell is about. It basically handle a borrow checking rules in runtime, if those are broken you get a panic. For the case that looks like this:

use std::cell::RefCell;

type NodeIndex = usize;

struct Graph {
    nodes: RefCell<Vec<NodeIndex>>,
    edges: RefCell<Vec<(NodeIndex, NodeIndex)>>,
}

fn mutate_fn(&self) {
    for &node in self.nodes.borrow().iter() {
        self.mutate_using_node(node);
    }
}

fn mutate_using_node(&self, node: NodeIndex) { // <- notice immutable ref
    for e in self.edges.borrow_mut().iter_mut() {
        if e.0 == node {
            std::mem::swap(&mut e.0, &mut e.1);
        }
    }
}

Keep in mind, that RefCell is not Sync, so it cannot be shared between threads. For case with threads Mutex or RwLock is an alternative.

Kitsu
  • 3,166
  • 14
  • 28