Borrow checker scoping issue

help
1

The exclusive borrowing is done in a dedicated scope. Why is still affecting the for loop following it ?

#[derive(Clone, Default)]
struct Polygon {
    points: Vec<(i64, i64)>,
}

fn main() {
    let mut prev_crossing = None;
    let mut polygons: Vec<Polygon> = vec![Polygon::default(); 10];

    for i in 0..10 {
        {
            let polygon = &mut polygons[i];
            polygon.points.sort_by(|_, _| todo!());
            drop(polygon);

            // try using a function, still errors
            // sort(&mut polygons[i]);
        }

        for crossing in polygons[i].points.iter() {
            if prev_crossing.is_none() {
                prev_crossing = Some(crossing);
            } else {
                todo!();
            }
        }
    }
}

fn sort(polygon: &mut Polygon) {
    polygon.points.sort_by(|_, _| todo!());
}

error[E0502]: cannot borrow `polygons` as mutable because it is also borrowed as immutable
  --> src/main.rs:12:32
   |
12 |             let polygon = &mut polygons[i];
   |                                ^^^^^^^^ mutable borrow occurs here
...
19 |         for crossing in polygons[i].points.iter() {
   |                         -------- immutable borrow occurs here
20 |             if prev_crossing.is_none() {
   |                ------------- immutable borrow later used here
2

You're saving a reference to the polygon in prev_crossing. So on the next iteration of the loop you can't get a mut ref.

Instead of a &(i64, i64) you could store a (i64, i64) by dereferencing the point here:

                prev_crossing = Some(*crossing); // note * to deref
3

Thanks, it did solve the simplified code I provided. However, I belive I have a unfundmental misconception here, I just couldn't understand the compiler and it is pointing to locations I couldn't comprehend altogether.

I believe the sitatuion will be similiar to your answer. In previous case, I do see previous_crossing holds a ref to crossing in the first iteration and thus the borrowing in the second iterator will fail.

But in this case I just don't understand why find is causing trouble here as it is just borrowing crossing once. I don't see find is borrowing crossing after first iteration?

use std::collections::HashMap;
use std::hash::Hash;

pub(crate) struct UnionFind<E> {
    items: Vec<E>,
    element_to_position: HashMap<E, usize>,
}

impl<E> UnionFind<E>
where
    E: Clone + Eq + Hash + PartialEq,
{
    pub(crate) fn new() -> Self {
        Self {
            items: Vec::new(),
            element_to_position: HashMap::new(),
        }
    }

    pub(crate) fn find(&mut self, _item: &E) -> Option<usize> {
        todo!()
    }
}

#[derive(Clone, Default)]
struct Polygons(Vec<i64>);

#[derive(Eq, Hash, PartialEq)]
struct LineSegment;

struct Process {
    crossings: Vec<Vec<Vec<LineSegment>>>,
}

impl Process {
    fn connect_lines(&mut self, _result_lines: &mut Polygons) {
        let mut connected_lines = UnionFind::<&LineSegment>::new();

        for polygon_index in 0..10 {
            let mut previous_crossing = None;

            for vertex_index in 0..10 {
                {
                    let crossings_on_polygon = &mut self.crossings[polygon_index];
                    let segment = &mut crossings_on_polygon[vertex_index];
                    segment.sort_by(|_left_hand_side, _right_hand_side| todo!());
                }

                for crossing in &self.crossings[polygon_index][vertex_index] {
                    if previous_crossing.is_none() {
                        previous_crossing = Some(crossing.clone());
                    } else {
                        connected_lines.find(&crossing);
                    }
                }
            }
        }
    }
}

error[E0502]: cannot borrow `self.crossings` as mutable because it is also borrowed as immutable
  --> src/lib.rs:44:53
   |
44 |                     let crossings_on_polygon = &mut self.crossings[polygon_index];
   |                                                     ^^^^^^^^^^^^^^ mutable borrow occurs here
...
49 |                 for crossing in &self.crossings[polygon_index][vertex_index] {
   |                                  -------------- immutable borrow occurs here
...
53 |                         connected_lines.find(&crossing);
   |                         --------------- immutable borrow later used here
4

You're right, there is a similar problem, but actually two problems.

First note that crossing is a ref, its type is &LineSegment. This is probably not what you want, and I think the root of all these problems is that you probably didn't realize that you're iterating over references.

The first problem, where the error is related to find, is that you're passing crossing to find, which is a &mut self method. The compiler has to assume you might be storing the reference in the UnionFind, so that's why it is complaining. It doesn't look inside methods to determine whether calls to the methods are safe, it just looks at the method signature.

I fixed that by changing &mut self to &self. This may not be what you want, but at least now you know why it was complaining.

Then there is another problem:

error[E0502]: cannot borrow `self.crossings` as mutable because it is also borrowed as immutable
  --> src/lib.rs:44:53
   |
44 |                     let crossings_on_polygon = &mut self.crossings[polygon_index];
   |                                                     ^^^^^^^^^^^^^^ mutable borrow occurs here
...
49 |                 for crossing in &self.crossings[polygon_index][vertex_index] {
   |                                  -------------- immutable borrow occurs here
50 |                     if previous_crossing.is_none() {
   |                        ----------------- immutable borrow later used here

This is similar to your first problem. You may be thinking "but I clone it, so why does it think I'm storing a reference in previous_crossing"? The answer is that you're just cloning the &LineSegment reference, which does nothing since all refs are Copy. So the type of previous_crossing is Option<&LineSegment>. I fixed this just like the original problem:

                                previous_crossing = Some(*crossing);

I had to also add Copy, Clone to the derive for LineSegment.

With these derives, you could also leave the line above alone, since you can either copy or clone it:

                        previous_crossing = Some(crossing.clone());

So just adding the derive of Copy, Clone to LineSegment fixes the second problem. I think it is confusing that the compiler clones the reference when LineSegment does not implement Clone, but clones the LineSegment itself when Clone is implemented. I don't know exactly why it does that, but at least we know what is happening and how to fix it.

Here is the playground with the two fixes.

2 Likes
5

The bare inner block doesn't effect Rust lifetimes (those '_ things) in your playground. Unless a destructor is causing problems, adding inner scopes generally doesn't help with such problems in Rust.

If previous_crossing is not None, then it holds a borrow from &self.crossings when you enter the vertex_index for loop. That's one problem. In your playground you're not using the contents: this variable can be a bool. (Maybe this isn't the case in your real code.)

But there's a second problem. Let's expand your implementation of find to more closely reflect the types in use within connect_lines:

impl<'a, R> UnionFind<&'a R>
where
    R: Eq + Hash + PartialEq,
{
    //                         vvvv           vvvvv           vvvvv
    pub(crate) fn find_r(self: &mut UnionFind<&'a R>, _item: &&'a R) -> Option<usize> {
        todo!()
    }
}

By your signature, you have to pass in a reference to a &'a R in order to find things in the UnionFind<&'a R>. Moreover, the Union<&'a R> cannot coerce to some shorter lifetime, because it's behind a &mut _. For this call to work in connect_lines, crossing here...

for crossing in &self.crossings[polygon_index][vertex_index] {

...needs to have the same lifetime as connected_lines, every time through the loop.

If you loosen up the lifetimes:

impl<'a, R> UnionFind<&'a R>
where
    R: Eq + Hash + PartialEq,
{
    //                                                       vv
    pub(crate) fn find_r(self: &mut UnionFind<&'a R>, _item: &R) -> Option<usize> {
        todo!()
    }
}
// ...
                    } else {
                        connected_lines.find_r(crossing); // no &
                    }

This constraint goes away.

1 Like
6

Follow up: @jumpnbrownweasel's reply came while I was writing up mine. Their "you wanted to clone LineSegment" might be closer to your actual intention, I'm not sure.

7

This is a result of Rust’s method resolution order:

When looking up a method call, the receiver may be automatically dereferenced or borrowed in order to call a method. This requires a more complex lookup process than for other functions, since there may be a number of possible methods to call. The following procedure is used:

The first step is to build a list of candidate receiver types. Obtain these by repeatedly dereferencingthe receiver expression's type, adding each type encountered to the list, then finally attempting an unsized coercion at the end, and adding the result type if that is successful. Then, for each candidate T, add &T and &mut T to the list immediately after T.

If I understand this correctly, it means that in this case the compiler looks for clone methods with these receiver types in order:

  1. &LineSegment
  2. &&LineSegment
  3. &mut &LineSegment
  4. LineSegment
  5. &LineSegment (again)
  6. &mut LineSegment

When LineSegment implements Clone, option (1) is valid; otherwise it goes to the first alternate (2) which is provided by a blanket impl<T> Clone for &T.

2 Likes
8

Except that's almost never what you want. I think it's worth filing a bug to improve the diagnostic.

References are cloneable and should be cloneable for generic algorithms. But since they are also Copy you never want to clone them if you are dealing with concrete type.

Especially if this leads to problem with borrowing.

P.S. I'm not sure it's worth detecting and diagnosing it for other Copy + Clone types, but reference is especially problematic because of these auto-dereference rules.

1 Like
9

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.