3

I'm trying to look up the value of an element (B) in a BTreeMap, from an element (A) that comes from the same map and then mutate the value of A with the value of B.

I know I can use a RefCell to avoid the "cannot borrow X as immutable because X is also borrowed as mutable" error, but I wanted to know if there was a more idiomatic, safe way to do this.

I've thought of trying to store pointers to the other elements, but that doesn't work because the memory locations of elements change move as one adds elements to the BTreeMap, so it's unsafe and wrong.

Is there a better approach to this kind of pattern?

Initial try

use std::collections::BTreeMap;

struct Map(BTreeMap<String, Foo>);

impl Map {
    fn new() -> Self {
        Map(BTreeMap::new())
    }

    fn calc_node(&mut self, name: &str) {
        self.0.get_mut(name).unwrap().calc_value(self)
    }
}

struct Foo {
    name: String,
    v: i32,

    lookup: String,
}

impl Foo {
    fn new(name: String, value: i32, lookup: String) -> Self {
        Self {
            name,
            v: value,
            lookup,
        }
    }

    fn calc_value(&mut self, map: &Map) {
        self.v = map.0.get(&self.lookup).unwrap().v * 2 // really what I'm trying to do
    }
}

fn main() {
    let mut map = Map::new();

    map.0.insert(
        "a".to_string(),
        Foo::new("a".to_string(), 1, "b".to_string()),
    );
    map.0.insert(
        "b".to_string(),
        Foo::new("b".to_string(), 2, "a".to_string()),
    );

    println!("{:?}", map.0.get("a").unwrap().v);
    map.calc_node("a");
    println!("{:?}", map.0.get("a").unwrap().v);
}

error[E0502]: cannot borrow `*self` as immutable because it is also borrowed as mutable
  --> src/main.rs:11:50
   |
11 |         self.0.get_mut(name).unwrap().calc_value(self)
   |         ------                        ---------- ^^^^ immutable borrow occurs here
   |         |                             |
   |         |                             mutable borrow later used by call
   |         mutable borrow occurs here

Using RefCell

use std::cell::RefCell;
use std::collections::BTreeMap;

struct Map(BTreeMap<String, RefCell<Foo>>);

impl Map {
    fn new() -> Self {
        Map(BTreeMap::new())
    }

    fn calc_node(&self, name: &str) {
        self.0.get(name).unwrap().borrow_mut().calc_value(self)
    }
}

struct Foo {
    name: String,
    v: i32,

    lookup: String,
}

impl Foo {
    fn new(name: String, value: i32, lookup: String) -> Self {
        Self {
            name,
            v: value,
            lookup,
        }
    }

    fn calc_value(&mut self, map: &Map) {
        self.v = map.0.get(&self.lookup).unwrap().borrow().v * 2
    }
}

fn main() {
    let mut map = Map::new();

    map.0.insert(
        "a".to_string(),
        RefCell::new(Foo::new("a".to_string(), 1, "b".to_string())),
    );
    map.0.insert(
        "b".to_string(),
        RefCell::new(Foo::new("b".to_string(), 2, "a".to_string())),
    );

    println!("{:?}", map.0.get("a").unwrap().borrow().v);
    map.calc_node("a");
    println!("{:?}", map.0.get("a").unwrap().borrow().v);
}

I get the correct result:

1
4

RefCells have a run-time cost and I would like to ideally be able to access referenced elements as quickly as possible.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
Oliver Funk
  • 166
  • 1
  • 15
  • 3
    *`RefCell`s have a run-time cost* — have you benchmarked to see what the "cost" is? I'm 99.9% sure it's a single integer comparison. – Shepmaster Jan 08 '19 at 15:16
  • I believe your question is answered by one or more of the answers of [Borrow two mutable values from the same HashMap](https://stackoverflow.com/q/47773849/155423), just ignore one of the mutable borrows. If you disagree, please [edit] your question to explain the differences. Otherwise, we can mark this question as already answered. – Shepmaster Jan 08 '19 at 15:18
  • 9
    @Shepmaster: They also have a memory cost :) – Matthieu M. Jan 08 '19 at 15:21
  • 1
    You may also use `Cell` or `AtomicI32` for `v`, which have no memory overhead and only a small effect on codegen. But that may not work if your actual code is not based on `i32` but some other type. – trent Jan 08 '19 at 17:57
  • [The duplicate applied to your specific case](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=98f6396cf796f5488aa5c63a50287823) – Shepmaster Jan 08 '19 at 18:56
  • Ok I've over simplified my problem, but thank you for the suggestions, you answered the question I asked. @Shepmaster the suggestion you posed won't work in my case because the `fn calc_value` comes from a trait that structs like Foo implement, so the function signature can't change and each Foo could reference and use a different number of other nodes. I'm going to try think of a better way to ask my actual question. – Oliver Funk Jan 09 '19 at 09:13
  • @trentcl yah `v` isn't `i32` in my actual case. – Oliver Funk Jan 09 '19 at 09:14
  • 1
    Is it guaranteed that a `Foo` cannot contain its own `name` as `lookup`? I.e. the collection of `Foo`s represent a [DAG](https://en.wikipedia.org/wiki/Directed_acyclic_graph)? There might be a better way to store them rather than by `name`, for instance, as indices into a `Vec`, or perhaps using the `petgraph` crate. Repeated lookup into a `BTreeMap` is most likely going to dwarf the cost of using `RefCell`. – trent Jan 09 '19 at 12:27
  • 1
    Actually, scratch the DAG part. With the `calc_value` you describe, the graph doesn't have to be acyclic, it just has to have no nodes with edges to themselves. (But if `calc_value` can traverse the graph it may have to be acyclic, anyway.) – trent Jan 09 '19 at 13:11
  • @trentcl you're right about the graph. I'm trying to build a computational graph of sorts, where `Foo`'s define functions that operate on other nodes in the graph. – Oliver Funk Jan 09 '19 at 19:07

0 Answers0