Mutable/Immutable borrows: completely stuck trying to define my own custom collection type


#1

I have a struct Buffer. What is in it doesn’t matter at the moment. My program is going to maintain a single set of these, so I am trying to write a struct BufferCollection which will own these objects and hand out mutable references to them when a client wants them, plus contain some collection-level functions. Eventually the BufferCollection will be a field inside another struct. At the moment I don’t care about threading, I am just trying to get a simple example working. So far it looks like this

pub struct BufferCollection {
    buffers: Vec<Buffer>
}

impl BufferCollection {
    pub fn add(&mut self, buffer: Buffer) {
        self.buffers.push(buffer)
    }

    pub fn find_by_filename<P: AsRef<Path>>(&self, _filename: P) -> Option<&mut Buffer> {
        None // TODO: Write me.
    }
}

The problem comes when I try to use it - see comment below

    // With this mut, rust complains on buffers.add() below: "cannot borrow as mutable because it
    // is already borrowed as immutable", which occurs in the call to find_by_filename. If I remove
    // the mut, rust complains "cannot borrow immutable local variable buffers as mutable", again
    // on the call to add().
    let mut buffers = BufferCollection::new();
    let filename = String::from("~/foo.txt");

    match buffers.find_by_filename(&filename) {
        Some(buffer) => { info!("Buffer for {} already exists.", &filename); },
        None => {
            info!("Buffer for {} does not exist, creating new buffer.", &filename);
            let mut b = Buffer::new();
            b.filename = Some(PathBuf::from(&filename));
            buffers.add(b);
        }
    }

How to square the circle? Looking at that code above and evaluating it in my head I don’t see a problem.

I am coming from a C# background where I would have written this in about 5 minutes. I have been stuck on this for 3 days now and am getting really frustrated. Any help is appreciated. It may be that this approach is completely wrong and that there is a good solution to the initial problem as stated - I half expect that - but the problem is that if I don’t know what the perfect solution is and I can’t even get a simple version to compile then I have no way of evolving my simple code to good code. I have to jump straight to the perfect code - which is pretty hard when you don’t know what it is.

Edit: should add that I have read numerous articles and the standard lib documentation on Rc, Cell and RefCell.


#2

You’re bumping up against non-lexical lifetimes- http://smallcultfollowing.com/babysteps/blog/2016/04/27/non-lexical-lifetimes-introduction/

The immutable borrow is active for the entire match statement, and so you get a conflict. The blog above may help you and if not ping back here.


#3

In addition to that, when you go to implement find_by_filename you will find that it cannot take &self and return &mut Buffer. The &self is a shared borrow so other code may be borrowing self at the same time. The &mut Buffer is an exclusive borrow so while it is in alive it must be the only way that any code can refer to that Buffer. These are in contradiction.


#4

Reason why you can’t do this is that you want to have valid reference to Buffer until end of your match block, but on None case you are pushing something to vector, so you may invalidate this reference. However there is a way to do that, something like:

buffers.find_by_filename(&filename)
    .map_or_else(|| {
        // None case goes here
    }, |buffer| {
        // Some case goes here
    })

In general you almost never want to match on Option nor Result cause they have bunch of really handy functions to deal with them without lifetimes pain/unnecessary clones.


#5

Closures in functions like these are free, more or less.


#6

Thanks @vitalyd and everyone else. I got something working, though it is not elegant. I had actually heard the term non-lexical lifetimes before on Reddit, and understood what was meant by it, but did not recognise it as applying in this case. My example was an exact analog for Problem case #2: checking/inserting into hashmaps. Once I refactored in line with the suggestion it compiled first time. Whew!

I also managed to implement find_by_filename, but it is something of a monstrosity to my eye:

pub fn find_by_filename<P : AsRef<Path>>(&mut self, filename: P) -> Option<&mut Buffer> {
    let pb = Some(filename.as_ref().to_path_buf());

    for b in self.buffers.iter_mut() {
        if b.filename == pb {
            return Some(b);
        }
    }

    None
}

I was trying to get rid of the explicit loop by using filter to check the filenames of all the buffers (which are Option<PathBuf>) and return the first one but haven’t found the right magic incantation yet…I was also annoyed at having to allocate a PathBuf to do the comparison, which seems unnecessary. Any suggestions gratefully received.

Edit: just found the docs for find, that should work…

Still, at least the program runs now. It’s a lot easier to make incremental improvements to a running program than to hack on something that doesn’t.


#7

Heh. Body changed to

pub fn find_by_filename<P : AsRef<Path>>(&mut self, filename: P) -> Option<&mut Buffer> {
    let pb = Some(filename.as_ref().to_path_buf());
    self.buffers.iter_mut().find(|&ref x| x.filename == pb)
}

#8

In this case, you can get around the lifetime issue by using an if let instead of a match:

    if let Some(_) = buffers.find_by_filename(&filename) {
        info!("Buffer for {} already exists.", &filename);
    } else {
        info!("Buffer for {} does not exist, creating new buffer.", &filename);
        let mut b = Buffer::new();
        b.filename = Some(PathBuf::from(&filename));
        buffers.add(b);
    }

Here’s a playground link.


#9

@Ophirr33 That’s essentially what I did, though with an early return rather than an else clause.


#10

To avoid needless PathBuf allocation, change that to:

self.buffers.iter_mut().find(|b| b.filename.as_ref().map_or(false, |f| f == _filename.as_ref()))

#11

Thank you @vitalyd I never would have got that. I appreciate the time you have taken to answer my questions. Let me try and break your last answer down to see if I understand it.

We do b.filename.as_ref() so that we can look inside the Option without moving the value out (or making a new Option and using == like I was originally).

The map_or then basically says “if b.filename is None, return false, else return f == filename”. The first match will return true and terminate the find().

That seems fairly straightforward.

The part I don’t get is the as_ref() on the filename, or indeed the AsRef<Path> signature. The standard documentation for AsRef is incomprehensible to me. What actually is the type of filename?


#12

Yup

Yup

So _filename is some generic type P that implements AsRef<Path>. What this means here is that you can call as_ref() on it (that’s part of the AsRef trait) and get a &Path back (i.e. AsRef<T>::as_ref(&self) returns &T, and we have T=Path in this particular case.).

AsRef is basically a trait that allows one to abstract over getting a reference to some type Y from some type X. In other words, if you have a struct Foo (the X in my previous sentence) from which you can get a &Path (Path is the Y), say because Foo internally contains an owned PathBuf(which itself can be dereferenced to a &Path), then you could impl AsRef<Path> for Foo. All that’s saying is you can get a &Path from a &Foo (that’s the &self part in the as_ref(&self) signature).

So back to the |f| f == _filename.as_ref() portion. f here is the &PathBuf reference we got from the Option<&PathBuf> and _filename.as_ref() is a &Path. So we have &PathBuf == &Path, for all intents and purposes. f == _filename.as_ref() is desugared into f.eq(_filename.as_ref()). This then bottoms out in this impl in the stdlib:

impl<'a, 'b> PartialEq<Path> for PathBuf {
      fn eq(&self, other: &Path) -> bool
}

Does that help? If not, let me know and I’ll try to explain further. My response here is perhaps a tad bit verbose, hopefully that doesn’t have a net negative effect :slight_smile:.


#13

It helps hugely, thank you very much. I think I understand now, it actually seems quite simple suddenly :slight_smile: I was getting stuck on “why do I need to call this as_ref() function to get a reference, why don’t I just put a & in front of it.” It’s the conversion aspect that the as_ref() supplies.

Hopefully this will become second nature soon!


#14

Right, that’s exactly it. Now that you know AsRef, the next thing to understand (or not) is the difference between it and Borrow - that’s virtually a rite of passage when learning Rust :slight_smile:.

By the way, your thought of “why not just put a & in front of it” reminds me - you can also make that method non-generic and make the caller pass a &Path argument directly, rather than getting it via AsRef<Path>. Clearly if the caller is giving you an AsRef<Path> type then they themselves can get the reference and pass it in (at a slight ergonomics hit to them). AsRef is useful in more generic contexts, such as storing it in a field (rather than as a pure &Path since that will require the struct/enum to gain a lifetime parameter). The other benefit in not using the generic function here is you’ll avoid code bloat that would ensue if callers of your function pass different P types, and the compiler monomorphizes the calls.