"cannot borrow `graph` as immutable because it is also borrowed as mutable." How can I let Rust know that I'm done with that mutable borrow?

Question

I'm trying to make a graph-like structure in Rust. My first implementation compiled just fine:

fn main() {
    let mut graph: Graph = Graph::new(); // Contains a vector of all nodes added to the graph.  The graph owns the nodes.

    // Create a node
    let parent: usize = graph.add_node(ParentNode::new()); // Returns the ID of the node.
    let parent: &Node = graph.get_node_with_id(parent); // Returns a borrowed reference to the node with the given ID

    // Print the number of nodes
    println!("Num nodes: {}", graph.count_nodes());
}

I don't like how I have to call add_node followed by get_node_with_id, so I wrote another method that combines those two steps into one:

fn main() {
    let mut graph: Graph = Graph::new();

    // Create a node
    let parent: &Node = graph.add_node_and_borrow(ParentNode::new());

    // Print the number of nodes
    println!("Num nodes: {}", graph.count_nodes());
}

add_node_and_borrow is just a shorthand:

/// Like add_node, but returns a borrowed reference
/// instead of the id
pub fn add_node_and_borrow(&mut self, node: Box<Node>) -> &Node {
    let id = self.add_node(node);
    return self.get_node_with_id(id);
}

When I try to compile this, I get an error:

error[E0502]: cannot borrow `graph` as immutable because it is also borrowed as mutable
  --> src/main.rs:23:31
   |
20 |     let parent: &Node = graph.add_node_and_borrow(ParentNode::new());
   |                         ----- mutable borrow occurs here
...
23 |     println!("Num nodes: {}", graph.count_nodes());
   |                               ^^^^^ immutable borrow occurs here
24 | }
   | - mutable borrow ends here

Strange! In both examples, I'm doing the exact same thing...aren't I? Why does Rust think I never stopped borrowing graph mutably in the second example?

Here's the full source file minus unimportant bits so you can see the whole picture:

fn main() {
    does_not_compike();
}

fn compiles() {
    let mut graph: Graph = Graph::new();

    // Create a node
    let parent: usize = graph.add_node(ParentNode::new());
    let parent: &Node = graph.get_node_with_id(parent);

    // Print the number of nodes
    println!("Num nodes: {}", graph.count_nodes());
}

fn does_not_compike() {
    let mut graph: Graph = Graph::new();

    // Create a node
    let parent: &Node = graph.add_node_and_borrow(ParentNode::new());

    // Print the number of nodes
    println!("Num nodes: {}", graph.count_nodes());
}

struct Graph {
    nodes: Vec<Box<Node>>,
    next_node_id: usize,
}

impl Graph {
    pub fn new() -> Graph {
        // Construct a new graph with no nodes.
        let new_graph = Graph {
            nodes: Vec::new(),
            next_node_id: 0,
        };

        return new_graph;
    }

    /// Adds a newly-created node to graph.
    /// The graph becomes the new owner of the node.
    /// Returns the node id of the node.
    pub fn add_node(&mut self, node: Box<Node>) -> usize {
        // Add the node
        self.nodes.push(node);

        // Return the id
        let id = self.next_node_id;
        self.next_node_id += 1;

        return id;
    }

    /// Like add_node, but returns a borrowed reference
    /// instead of the id
    pub fn add_node_and_borrow(&mut self, node: Box<Node>) -> &Node {
        let id = self.add_node(node);
        return self.get_node_with_id(id);
    }

    /// Returns a borrowed reference to the node with the given id
    pub fn get_node_with_id(&self, id: usize) -> &Node {
        return &*self.nodes[id];
    }

    pub fn count_nodes(&self) -> usize {
        return self.nodes.len();
    }
}

trait Node {
    // Not important
}

struct ParentNode {
    // Not important
}

impl ParentNode {
    pub fn new() -> Box<Node> {
        Box::new(ParentNode {
            // lol empty struct
        })
    }
}

impl Node for ParentNode {
    // Not important
}

Answer 1

In your first example:

let parent: usize = graph.add_node(ParentNode::new());

borrows graph mutably for the call to add_node then releases the borrow.

let parent: &Node = graph.get_node_with_id(parent);

borrows graph immutably and keeps the borrow because parent is a reference to a node that belongs to the graph. At this point, like @kazemakase said, you would be unable to add a new node to the graph because the immutable borrow prevents you from creating a new mutable borrow. You can however re-borrow graph immutably to print it.

In your second example:

let parent: &Node = graph.add_node_and_borrow(ParentNode::new());

borrows graph mutably (because of the function signature) and keeps the borrow (because of the parent reference). After this you can no longer re-borrow the graph at all because you already have an active mutable borrow.