Passing mutable borrow to immutably borrowed closure

help
1

Hi, I'm a complete beginner at Rust, coming from a Java / Go background. The code below helps memoize a recursive function func, and compiles / runs fine.

pub struct FnCache<'a, I, O> {
    cache: HashMap<I, O>,
    func: &'a dyn Fn(&I, &mut Self) -> O,
}

impl<'a, I: Eq + Hash, O: Clone> FnCache<'a, I, O> {
    pub fn get(&mut self, input: I) -> O {
        match self.cache.get(&input) {
            Some(val) => val.clone(),
            None => {
                let result = (self.func)(&input, self);
                self.cache.entry(input).or_insert(result).clone()
            }
        }
    }
}

I want to refactor it as below, so that I can return the built cache from another function. The above code won't work as it requires a reference to the closure created in the function, which goes away after the function goes out of scope. Makes sense to me.

pub struct FnCache<I, O> {
    cache: HashMap<I, O>,
    func: Box<dyn Fn(&I, &mut Self) -> O>,
}

impl<I: Eq + Hash, O: Clone> FnCache<I, O> {
    pub fn get(&mut self, input: I) -> O {
        match self.cache.get(&input) {
            Some(val) => val.clone(),
            None => {
                let result = (self.func)(&input, self); // cannot borrow `*self` as mutable because it is also borrowed as immutable
                self.cache.entry(input).or_insert(result).clone()
            }
        }
    }
}

Compile fails with error

                let result = (self.func)(&input, self);
   |                              -----------^^^^^^^^^^^^^^
   |                              |
   |                              mutable borrow occurs here
   |                              immutable borrow occurs here
   |                              immutable borrow later used by call

Logically speaking, the check can be ignored, since self.func cannot be modified. But I guess the compiler has no way of knowing that.

My question is, why does the first example compile, when I'm also immutably borrowing self.func and passing it a mutable reference to self? Any fix will also be greatly appreciated.

Thanks for your help!

2

In the first example, calling the closure makes a copy of the reference stored in self.func. This copy will remain valid even if the self.func field is modified, because it references something outside of self.

In the second example, there's no existing reference to copy, so the compiler has to create a reference to the self.func field. In this case, if the self.func field is modified, the closure it contains will be deallocated and that reference would become a dangling pointer.

1 Like
3

One fix is to take the function out of self, call it, and then put it back. For example:

pub struct FnCache<I, O> {
    cache: HashMap<I, O>,
    func: Option<Box<dyn Fn(&I, &mut Self) -> O>>,
}

impl<I: Eq + Hash, O: Clone> FnCache<I, O> {
    pub fn get(&mut self, input: I) -> O {
        match self.cache.get(&input) {
            Some(val) => val.clone(),
            None => {
                let func = self.func.take().unwrap();
                let result = func(&input, self);
                self.func = Some(func);
                
                self.cache.entry(input).or_insert(result).clone()
            }
        }
    }
}

(Playground)

Another option is to pass &self, and use interior mutability (e.g. RefCell or Mutex) around the fields of self that the closure is allowed to mutate.

Or, you could pass the closure individual fields instead of the entirety of self.

1 Like
4

In this situation I would use a RefCell. If you use Option and take(), A recursive closure would cause a panic, as the first call would remove the function. Although the RefCell route doesn't look as clean, as you would need to manually control the guards.

pub struct FnCache<I, O> {
    // Add the RefCell around the HashMap, which is the mutable state
    cache: RefCell<HashMap<I, O>>,
    // notice func now takes an immutable refrence to self
    func: Box<dyn Fn(&I, &Self) -> O>,
}

impl<I: Eq + Hash, O: Clone> FnCache<I, O> {
    pub fn get(&self, input: I) -> O {
        // check to see if value is in cache, we obtain a read guard here
        let cache = self.cache.borrow();
        if let Some(val) = cache.get(&input) {
            return val.clone();
        }
        // we need to drop the read guard in case func uses recursion
        drop(cache);
        // now call the function
        let result = (self.func)(&input, self);
        // then obtain a write guard to store the output
        self.cache.borrow_mut().entry(input).or_insert(result).clone()
    }
}

Using the RefCell I was able to create user code that looked like this

let mem = FnCache::new(Box::new(|i, c| {
        if *i == 0 {
            1
        } else {
            i * c.get(i - 1)
        }
}));
    
let one = mem.get(10usize);
let two = mem.get(20);
let three = mem.get(20);
    
println!("{} {} {}", one, two, three);

Playground

2 Likes
5

Thanks mbrubeck and Jon-Davis for the explanation on regarding copying references and solution.

6

One other potential solution (that I forgot to mention) that is a bit more limiting, is to use a fn pointer rather than a Fn trait object. On the upside you don't have to use a RefCell or even a Box<dyn Fn>. The downside to it would be that FnCache would only support closures that don't have an associated Context.

Playground The commented out code won't compile with fn but will compile with Fn. So if you don't care about closures ability to capture variables, you could go this route.

7

Might be a dumb question, but why does Rust not support final fields, and have the compiler just "skip" borrow checking on said fields? Interior mutability kind of does the same thing, just in reverse.

8

A "final field" would make the struct permanently immobile, which breaks the assumptions of a lot of generic code. You can kind of do this already with lifetimes and self-referencing structs, but you can't move the result (so you have to create it in two steps, because it can't be returned from a function) or even take a &mut reference to it (it can reference itself, so it can always be aliased).

Could we imagine a sort of inverse UnsafeCell, whose contents can always be aliased even if you have a &mut reference to the struct itself? Maybe... but such a type would be so disruptive to normal Rust programming it might not be worth it. There have been discussions before about adding immovable types to the language; here's one such proposal. final fields would have all the known problems of immovable types, plus probably several problems that haven't been nearly as thoroughly discussed yet. In the end we got a less disruptive system (Pin/Unpin) with weaker built-in guarantees; it's unlikely that a new proposal covering much of the same ground as the old rejected ones (even if sound, well-designed and more flexible) will be accepted at this point.

Since dyn Fn is unsized and has to be behind a pointer anyway, it's natural to use a reference that prevents mutation. You could use &'static if you're okay with Box::leaking the closure, but if you want runtime lifetime analysis, reference counting works fine too:

pub struct FnCache<I, O> {
    cache: HashMap<I, O>,
    func: Rc<dyn Fn(&I, &mut Self) -> O>,
}

impl<I: Eq + Hash, O: Clone> FnCache<I, O> {
    pub fn get(&mut self, input: I) -> O {
        match self.cache.get(&input) {
            Some(val) => val.clone(),
            None => {
                let f = Rc::clone(&self.func);
                let result = f(&input, self);
                self.cache.entry(input).or_insert(result).clone()
            }
        }
    }
}
2 Likes
9

I just learned this has been proposed for solving the unsound self-referential generator problem, so maybe the idea isn't quite as far-fetched as I thought!

However, the proposal is much narrower than what I was imagining: essentially it just turns off noalias for pointers to the inner value. Just including an UnsafeAliasedCell wouldn't make a struct immobile, so you'd still need to wrap a bunch of unsafe code in order to promise that it never gets moved... in FnCache<I, O>, which contains a Box already, maybe we could imagine something like func: Box<AliasedCell<dyn Fn(&I, &mut Self) -> O>>. Toss a Pin in there if you need to expose func to external code. And even then you couldn't extend it to FnMut, which RefCell supports trivially.

Of course this is all rhetorical at the moment, but it'll be interesting to find out if anybody comes up with a way to generalize this into a safe interface, if and when AliasedCell becomes a reality.

tl;dr Use RefCell

10

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.