Cannot have immutable borrow of self in one code branch and mutable in another

Question

I have a struct storing an iterator and a map of items previously produced by the iterator. This struct has a method that

1. checks whether any previously found items match a certain criteria and, if so, returns it, or
2. if nothing is found in the previous results, it turns to the iterator to look for new results which hopefully match the criteria.

This is a simplified example of my code (Playground):

use std::path::{Path, PathBuf};
use std::collections::HashMap;

struct MyStruct {
    pub iter: std::vec::IntoIter<PathBuf>,
    pub previous: HashMap<usize, PathBuf>
}

impl MyStruct {
    pub fn my_method(&mut self, minimum: usize) -> &Path {
        for (len, path) in self.previous.iter() {
            if *len >= minimum {
                return path;
            }
        }
        
        while let Some(path) = self.iter.next() {
            let len = path.to_string_lossy().len();
            self.previous.insert(len, path);
            
            if len >= minimum {
                return &self.previous.get(&len).unwrap();
            }
        }
        
        panic!("Nothing found")
    }
}

This fails to build with the error:

error[E0502]: cannot borrow `self.previous` as mutable because it is also borrowed as immutable
  --> src/lib.rs:19:13
   |
10 |     pub fn my_method(&mut self, minimum: usize) -> &Path {
   |                      - let's call the lifetime of this reference `'1`
11 |         for (len, path) in self.previous.iter() {
   |                            ------------- immutable borrow occurs here
12 |             if *len >= minimum {
13 |                 return path;
   |                        ---- returning this value requires that `self.previous` is borrowed for `'1`
...
19 |             self.previous.insert(len, path);
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

For more information about this error, try `rustc --explain E0502`.
error: could not compile `playground` (lib) due to previous error

I'm aware I can fix this error easily be simply cloning the returned PathBuf instead of returning a reference. In my case, the wasted memory and CPU cycles do not pose a problem. But I'd still like to understand why this fails and how I would ideally solve it.

Being a beginner in Rust, I understand in principle that I can't have mutable and immutable references to the same field at the same time.

The error message seems to indicate to me that the compiler assigns the immutable borrow of self.previous the same lifetime as self because I'm returning a reference into the HashMap and the return type implicitly has the same lifetime as self.
The lifetime of self is obviously the entire method invocation so that is why the second, mutable borrow of self.previous fails.

What I can't wrap my head around is that, logically, it should be impossible for both the immutable and the mutable borrow to exist at the same time. If the execution ever reaches the point where the mutable borrow occurs, the immutable reference is no longer needed.

Am I misinterpreting my code? Or is the borrow checker not capable of this kind of analysis? Is there then some language feature which allows me to make this clear to the compiler?

Answer 1

Thanks to gerwin for his answer. His link pointed me to RFC 4094 where I found an explanation of my problem and a potential solution.

With that I was able to modify my code in a way that compiles and would like to include this here as a second answer.

The core of the problem was that my first loop, which does an immutable borrow, returns conditionally.
As soon as we wrap the loop in an if and make it return unconditionally, it compiles.
As the RFC points out, this workaround is less efficient than the original code because it iterates over the the vector twice. Nevertheless, it is a solution that works with the current compiler version, before Polonius rolls out.

use std::path::{Path, PathBuf};

struct MyStruct {
    pub iter: std::vec::IntoIter<PathBuf>,
    pub previous: Vec<(usize, PathBuf)>
}

impl MyStruct {
    pub fn my_method(&mut self, minimum: usize) -> &Path {
        if self.previous.iter().any(|(l,_)| *l >= minimum) {
            let mut i = self.previous.iter();
            return loop {
                let (l,p) = i.next().unwrap();
                if *l >= minimum {
                    break p;
                }
            }
        }
        while let Some(path) = self.iter.next() {
            let len = path.to_string_lossy().len();
            self.previous.push((len, path));
            
            if len >= minimum {
                let (_, p) = self.previous.last().unwrap(); 
                return &p;
            }
        }
        
        panic!("Nothing found")
    }
}

Answer 2

The Rust compiler currently cannot solve for such cases.

There is actually a redesign on the way that is scheduled for Rust 2024, and will likely fix this issue. It is called Polonius. More info here: https://blog.rust-lang.org/inside-rust/2023/10/06/polonius-update.html.