Borrow checker errors in my graph implementation

Hello. I recently started learning Rust and I am comming from C++ and the borrow checker so far has been incredibly difficult for me to adjust to.

I decided to write a Graph based library to get some Rust experience and build a mental model about how things work (As graphs generally contain a lot of programming pitfalls).

This is my implementation

It basically fails at

    let mut e1_view = get_connections(&mut graph, e1);
    // let mut entry_view = get_connections(&mut graph, entry);
    {
        let immutabe_graph = &graph;

It considers get_connections as an mutable borrow. I would expect that it would understand that the mutable reference is dropped inside the get_connections. It is only used to initialize the EdgeView object which takes a mutable split from the Graphs vector.

It doesn't hold a reference to the Graph itself so I don't know why this error is happening.

Can anyone explain to me what is going on?

e1_view borrows from graph. As such you can't borrow graph a second time until after the last use of e1_view.

But why is that a problem?

It borrows from its field and as far as I understand it is legitimate to have multiple mutable borrows from the same struct to different fields?

pub fn new<T>(graph: &'a mut Graph<T>, vertex: usize) -> Self {

here you are saying that you are mutably borrowing from Graph - not one of its fields. The function declaration is decisive, not what's in the function body.

3 Likes

Good I understand that.

Now I slightly edited to code to basically this:

pub struct EdgeView<'a>{
    pub edges: &'a mut [usize],
}

impl <'a> EdgeView<'a> {
    #[inline(always)]
    pub fn len(&mut self) -> &mut usize {
        return &mut self.edges[0];
    }
    #[inline(always)]
    pub fn push(&mut self, vertex: usize){
        self.edges[*self.len() + 1] = vertex; // First element is size
        *self.len() += 1;
    }

    pub fn iter(&mut self) -> EdgeViewIter {
        return EdgeViewIter(1, *self.len(), self.edges);
    }
}

and then

#[inline(always)]
pub fn get_connections<T>(graph: &mut Graph<T>, vertex: usize) -> EdgeView {
    let data_start = graph.indices[vertex];
    let edges = graph.edges.split_at_mut(data_start).1;
    return EdgeView{edges};
}

now called like this:

    // Value check
    let mut e1_view = get_connections(&mut graph, e1);
    // let mut entry_view = get_connections(&mut graph, entry);
    {
        //
        for i in e1_view.iter(){
            print!("{} ", *get(&graph, i));

        }
    }

Giving still the error:

error[E0502]: cannot borrow `graph` as immutable because it is also borrowed as mutable
  --> src\tests\tree_test.rs:45:32
   |
40 |     let mut e1_view = get_connections(&mut graph, e1);
   |                                       ---------- mutable borrow occurs here
...
44 |         for i in e1_view.iter(){
   |                  -------------- mutable borrow later used here
45 |             print!("{} ", *get(&graph, i));
   |                                ^^^^^^ immutable borrow occurs here



I am uterrly confused now because, yes I understand that previously, with the lifetime parameter of 'a I basically told the borrow checker that the graph shall last as long as EdgeView (Which was a mistake), but now there is nothing like it and the graph is used only within the create_connection function and the borrow, as I understand it now, should end when the function returns.

Yes, the graph will stay alive until the function ends. But in Rust you cannot have an immutable borrow and a mutable borrow to the same object. The error message is saying this, take another look at it and be sure to read about this topic in the Rust book.

Why does get_connections have a &mut self param, does it need to mutate the graph? If not, change it to &self. Then you will have two immutable borrows at the same time in this function, which is allowed.

If you sometimes need a mutable view and other times you need an immutable view, create two functions: get_connections and get_connections_mut. This is common in Rust.

Oooohh.

Thanks a lot this is super helpful. As I am new I am still not sure what patterns are considered good in rust :grin:

I was thinking about get_connections and get_connections_mut before but I basically eliminated this line of thought when I realized that:

pub struct EdgeView<'a>{
    pub edges: &'a mut [usize],
}

the EdgeView needs to hold a reference to the slice.
Is there some rust mechanism that allows me to specify whether EdgeView should the internal reference as mutable or immutable:

pub struct EdgeView<'a>{
    pub edges: &'a <mut or not> [usize],
}

so I don't have to make two views?

No, there isn't.

So what is the recommended way of hanlind that?

Actually, I keep thinking---While what you propose would fix the issue, I still don't understand why it is happening.

You are saying that You can't have mutable as well as immutable borrow at the same time.
That is clear to me, but I don't understand why does the mutable borrow still exist after:

let mut e1_view = get_connections(&mut graph, e1);

The borrow should end at function return as it is closed within that scope... After hours of googling I can't seem to find an answer anywhere, and in the rust docs, there are trivial oversimplified cases where the errors are obvious...They don't really give me an insight into this issue here

I'm out of time to explain more, but the error is telling you:

The function signature with elided lifetimes expanded is:

pub fn get_connections<'a, T>(graph: &'a mut Graph<T>, vertex: usize) -> EdgeView<'a> {

The Graph is borrowed until the lifetime 'a ends, and it cannot end until the EdgeView<'a> is dropped.

Elided lifetimes in named types are often confusing because there's no syntactic cue that a lifetime is involved, like the & symbol usually provides. You can add #![deny(elided_lifetimes_in_paths)] to require yourself to always write EdgeView<'a> or EdgeView<'_> to remind yourself that a lifetime exists at that point.

3 Likes

e1_view is holding a reference to data of graph, hence the borrow can't be ended.

What do you want to achieve with EdgeView? Changing the graphs data behind its back? Rust prevents designs like this.

It is generally a bad design I agree.

I am using this to mostly learn and it is an inaccurate outline of what I want. I use the View internally in the graph functions to access to edges and write to them.

Outside it should be read only. As mentioned previously, I will change this and it should erase the error.

But right now I am more focused on the fact that the error is comming up, because currently with my mental model and the understanding, it shouldn't happen

Okay this seems to have almost completely cleared it up. I understand why it is happening now.

I will try to redesign this so it avoids these problems.

This hasn't been updated for some time I think. But is still a very good resource if you want to learn how Rust does graph data structures.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.