Return a reference to a value inside an object that is itself in Rc<RefCell>>

help
1

Hello,

probably this question was already asked, but I could not find the answer.

I have a linked list of Maps and I want to return to the caller a reference to the value, which is
stored in the Map. However, after many tries I still could not achieve this.

Of course the caller can extract it itself, but this makes the api very ugly.

If it is not possible to achieve with the current approach what other options do I have?
Use a similar implementation from the std lib of the linked list?

Because I need to store the Map in two places and I can guarantee that it cannot be borrowed mutably
twice.

The following code illustrate the problem of

error[E0515]: cannot return reference to temporary value
  --> src/main.rs:44:26
   |
44 |             .map(|entry| entry.get_entry().get(key))
   |                          -----------------^^^^^^^^^
   |                          |
   |                          returns a reference to data owned by the current function
   |                          temporary value created here

and the playground list is here. I also guess that the commented get cannot work as well.

use std::cell::{Ref, RefCell, RefMut};
use std::collections::BTreeMap;
use std::ops::DerefMut;
use std::rc::Rc;

#[derive(Debug, PartialEq)]
pub struct Env<K, V> {
    curr: Option<Rc<RefCell<Node<K, V>>>>,
}

#[derive(Debug, PartialEq)]
pub struct Node<K, V> {
    prev: Option<Rc<RefCell<Node<K, V>>>>,
    table: BTreeMap<K, V>,
}

pub struct TableRef<K, V> {
    entry: Rc<RefCell<Node<K, V>>>,
}

impl<K: std::cmp::Ord, V> TableRef<K, V> {
    pub fn get_entry(&self) -> Ref<'_, BTreeMap<K, V>> {
        Ref::map((*self.entry).borrow(), |node| &node.table)
    }

    pub fn get_mut_entry(&self) -> impl DerefMut<Target = BTreeMap<K, V>> + '_ {
        RefMut::map((*self.entry).borrow_mut(), |node| &mut node.table)
    }

    // pub fn get(&self, key: &K) -> Ref<Option<&V>> {
    //     let table = self.get_entry();
    //     Ref::map(table, |table| &table.get(key))
    // }
}

impl<K: Ord, V> Env<K, V> {
    pub fn new() -> Env<K, V> {
        Env { curr: None }
    }

    pub fn get(&self, key: &K) -> Option<&V> {
        self.iter()
            .find(|env| env.get_entry().contains_key(key))
            .map(|entry| entry.get_entry().get(key))
            .flatten()
    }

    pub fn iter(&self) -> Iter<K, V> {
        Iter {
            curr: self.curr.as_ref().map(|node| node.clone()),
        }
    }
}

pub struct Iter<K, V> {
    curr: Option<Rc<RefCell<Node<K, V>>>>,
}

impl<K, V> Iterator for Iter<K, V> {
    type Item = TableRef<K, V>;

    fn next(&mut self) -> Option<Self::Item> {
        self.curr.take().map(|node| {
            self.curr = (*node).borrow().prev.clone();
            TableRef { entry: node }
        })
    }
}


fn main() {
    println!("Hello, world!");
}
2

Implementation of Linked List in Rust is quite tricky.
Since we cannot access to item of linked list directly, items are usually temporary and reference of it cannot live longer than item itself in Rust.
Hence function which returns reference of item is invalid.

I think there is no way to implement such function without re-define whole structs using different data structure (like Vec<BTreeMap<K, V>)

pub struct ListTable<K, V> {
    tables : Vec<BTreeMap<K, V>>
}

impl<K : Ord, V> ListTable<K, V>{
    pub fn new() -> Self{
        Self{ tables : Vec::new() }
    }

    pub fn get(&self, key : &K) -> Option<&V>{
        self.tables.iter()
            .find(|env| env.contains_key(key))
            .map(|entry| entry.get(key))
            .flatten()
    }
}

------ Add -----
I'm not sure, it works or not.
If we use unsafe rust then compilation of following codes succeed.

pub fn get(&self, key: &K) -> Option<&V>{
    unsafe{
        self.iter()
            .find(|env| env.get_entry().contains_key(key))
            .map(|entry| Some(&*(entry.get_entry().get(key).unwrap() as *const V)))
            .flatten()
    }
}
3

You can't – how would the RefCell track how long it is borrowed for, then? You should really just return the Ref that you got from borrow().

Another option is writing a callback-based API, whereby you borrow the cell yourself, pass the temporary reference to the callback, and then drop the Ref. But this would actually be more cumbersome to use, because Ref<T> is already Deref<Target = T>, so users won't have any problems using it for extracting a reference.

6 Likes
4

First of all thanks for the answers.

The problem with this approach is that I cannot save a reference to the map in the other place.

This I did not try yet but I will try.

After playing with the code a bit I was able to narrow down the problem to the following code

use std::cell::{Ref, RefCell};
use std::rc::Rc;

struct Inner2 {
    z: u32,
}

impl Inner2 {
    fn get(&self) -> &u32 {
        &self.z
    }
}

struct Inner {
    y: Inner2,
}

struct Foo {
    x: Rc<RefCell<Inner>>,
}

impl Foo {
    fn get<'b>(&'b self) -> Ref<'b, &u32> {
        let x: &'b RefCell<Inner> = &*self.x;
        let y: Ref<Inner2> = Ref::map(x.borrow(), |t| &t.y);
        Ref::map(y, |t| &t.get())
    }
}

and the problem is the get function. Now the compiler complains

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/main.rs:26:28
   |
26 |         Ref::map(y, |t| &t.get())
   |                            ^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined here...
  --> src/main.rs:26:21
   |
26 |         Ref::map(y, |t| &t.get())
   |                     ^^^^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:26:26
   |
26 |         Ref::map(y, |t| &t.get())
   |                          ^
note: but, the lifetime must be valid for the lifetime `'b` as defined here...
  --> src/main.rs:23:12
   |
23 |     fn get<'b>(&'b self) -> Ref<'b, &u32> {
   |            ^^
note: ...so that the types are compatible
  --> src/main.rs:26:9
   |
26 |         Ref::map(y, |t| &t.get())
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: expected `Ref<'b, &'b u32>`
              found `Ref<'_, &u32>`

For more information about this error, try `rustc --explain E0495`.

Is it really not possible to use the get function? Because to me as soon as the lifetime of the reference is smaller than the lifetime of the self the code should be fine or I miss something?

5

You don't have to use Ref<&u32>. The reference is redundant – Ref<T> already gives out &T. You could have deduced this by reading its documentation, which you should do instead of shooting in the dark.

The implementation of the get() function should be as simple as:

impl Foo {
    fn get(&self) -> Ref<u32> {
        Ref::map(self.x.borrow(), |t| t.y.get())
    }
}
2 Likes
6

I'm not sure if my understanding is correct, but you seem to be in the following situation.

  1. You have list of maps.
  2. Items in map won't be borrowed mutably twice.

Therefore, you think that even if you borrow each item mutably to another place, it does not violate Rust's borrowing rule. However, it does violate borrowing rule in Rust. A count of mutably borrow restricts 'list of maps' not each 'items'.

fn main(){
    let mut a = vec![[1, 2], [3, 4]];
    let x1 = &mut a[0][0];
    let x2 = &mut a[1][1];
    *x2 = -3;

    println!("{} {}", x1, x2);
}

For example, codes above occurs error.

error[E0499]: cannot borrow `a` as mutable more than once at a time
  --> src/main.rs:49:19
   |
48 |     let x1 = &mut a[0][0];
   |                   - first mutable borrow occurs here
49 |     let x2 = &mut a[1][1];
   |                   ^ second mutable borrow occurs here
...
52 |     println!("{} {}", x1, x2);
   |                       -- first borrow later used here

For more information about this error, try `rustc --explain E0499`.
error: could not compile `ch8-macgen` due to previous error

In this code, each item in list a is borrowed only a single time, but rust compiler thinks that there are two mutable borrow of a. It is because, rust compiler don't know which items in list are actually borrowed, so it can not guarantee that there is no items mutably borrowed twice in such manner.

In conclusion, if you want to borrow reference of items, then you should wrap it by Reference counter in every place. Then your simplified code should be as follows.

use std::cell::RefCell;
use std::rc::Rc;

struct Inner2 {
    z: Rc<RefCell<u32>>,
}

impl Inner2 {
    fn get(&self) -> Rc<RefCell<u32>> {
        self.z.clone()
    }
}

struct Inner {
    y: Inner2,
}

struct Foo {
    x: Rc<RefCell<Inner>>,
}

impl Foo {
    fn get(&self) -> Rc<RefCell<u32>> {
        self.x.clone().borrow().y.get()
    }
}

===== Add ====
and back to storing references problem, you can write as below

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
struct Map{
    key : u32,
    value : Rc<RefCell<u32>>
}

impl Map{
    fn new(key : u32, value : u32) -> Self{
        Map{
            key,
            value : Rc::new(RefCell::new(value)),
        }
    }
}

#[derive(Debug)]
struct Node{
    prev : Option<Rc<RefCell<Node>>>,
    map : Map
}

impl Node{
    fn new(map : Map) -> Self{
        Self{
            prev : None,
            map,
        }
    }

    fn attach_to(node : Rc<RefCell<Node>>, map : Map) -> Self{
        Self{
            prev : Some(node),
            map,
        }
    }
}

#[derive(Debug)]
struct List{
    tail : Option<Rc<RefCell<Node>>>,
}

impl List{
    fn new() -> Self{
        Self{
            tail : None,
        }
    }

    fn append(&mut self, map : Map){
        match &self.tail{
            Some(node) => {
                let new_node = Node::attach_to(node.clone(), map);
                self.tail = Some(Rc::new(RefCell::new(new_node)));
            },
            None => {
                self.tail = Some(Rc::new(RefCell::new(Node::new(map))));
            }
        }
    }

    fn iter(&self) -> IterList{
        IterList{
            curr : self.tail.clone(),
        }
    }

    fn get(&self, key : u32) -> Option<Rc<RefCell<u32>>>{
        for node in self.iter(){
            if node.borrow().map.key == key{
                return Some(node.borrow().map.value.clone());
            }
        }
        return None;
    }
}

struct IterList{
    curr : Option<Rc<RefCell<Node>>>,
}

impl Iterator for IterList{
    type Item = Rc<RefCell<Node>>;

    fn next(&mut self) -> Option<Self::Item> {
        self.curr.take().map(|node| {
            self.curr = (*node).borrow().prev.clone();
            node.clone()
        })
    }
}

fn main(){
    let mut list = List::new();

    let map1 = Map::new(1, 10);
    list.append(map1);

    let map2 = Map::new(2, 5);
    list.append(map2);

    let value1 = list.get(1).unwrap();  // Rc<RefCell<10>>
    let value2 = list.get(2).unwrap();  // Rc<RefCell<5>>

    println!("{} {}", value1.borrow(), value2.borrow());  // 10 5

    *value1.borrow_mut() = 12;
    println!("{} {}", value1.borrow(), value2.borrow());  // 12 5
}

I think, if you want to store reference of item at other place, you should change your BTreeMap<K, V> to BTreeMap<K, Rc<RefCell<V>>>

7

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.