How can I create an Rc<RefCell<_>> to something that already exists?

Question

So, in order to teach myself some Rust, I decided to create a simply hybrid datatype that I like, the ChainVec. It's a doubly linked list of vectors, useful if you need to resize vectors that could grow to vast scales. It uses linked list logic, but the lookup, search, and iterate characteristics are much faster because they grow O(n/alot). That's not really the point, though: The problem I ran into would occur in any doubly linked list.

Here's the problem... in C, when I make the new linked list node, I can just set its 'tail' to a pointer to the previous. I can toss pointers like candy in C, but in Rust, I don't know how to create new pointers yet. Here is what I tried... (look under fn push_head for the invalid line)

Note: In my implementation, the 'head' node to the chainvec is whichever you choose to point to, so there is no separate struct for the list head/tail.

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

#[allow(dead_code)]
struct ChainVec<T> {
    item: Option<Vec<T>>,
    head: Option<Rc<RefCell<ChainVec<T>>>>,
    tail: Option<Rc<RefCell<ChainVec<T>>>>,
}

impl<T> ChainVec<T> {
    fn new(prealloc: usize) -> Self {
        let vector: Vec<T> = Vec::with_capacity(prealloc);
        Self {
            item: Some(vector),
            head: None,
            tail: None,
        }
    }

    fn new_with_links(
        prealloc: usize,
        head: Option<Rc<RefCell<ChainVec<T>>>>,
        tail: Option<Rc<RefCell<ChainVec<T>>>>,
    ) -> Self {
        let vector: Vec<T> = Vec::with_capacity(prealloc);
        Self {
            item: Some(vector),
            head: head,
            tail: tail,
        }
    }
    fn push_head(&mut self, prealloc: usize) {
        self.head = Some(Rc::new(RefCell::new(ChainVec::new_with_links(
            prealloc,
            None,
            Some(Rc::new(RefCell::new(self))),
        ))));
    }
}

#[allow(unused_variables)]
fn main() {
    let alef: ChainVec<u32> = ChainVec::new(100);
    println!("Hello, world!");
}

Obviously I got lost when I tried to create a new pointer in push_head. I got:

error[E0308]: mismatched types
  --> src/main.rs:36:39
   |
36 |             Some(Rc::new(RefCell::new(self))),
   |                          ------------ ^^^^ expected struct `ChainVec`, found `&mut ChainVec<T>`
   |                          |
   |                          arguments to this function are incorrect
   |
   = note:         expected struct `ChainVec<T>`
           found mutable reference `&mut ChainVec<T>`

A dereference operator doesn't do anything here... and I'm not sure how to proceed.

How would I create an Rc<RefCell<_>> that references a struct that already exists?

Answer 1

Simple answer: You can't.

As soon as you are inside of a function that takes &self or &mut self as a parameter, the function has no knowledge about the fact that it is wrapped in an Rc. So you cannot create a new Rc from it.

If you could, how would the existing Rcs and the new Rc know how long to keep the object alive, and when to delete it?

You can only ever create a new Rc from an existing one. That means, if you want to achieve that, you need to take the existing Rc as a parameter instead of &self.

---

As an excurse on how other libraries deal with this:

tokio_util::sync::CancellationToken has a similar problem. Its solution is to hide the Rc in the .inner member, and then when operating on it, it passes the entire Arc to the handling method.

You can see this for example on the clone(), which does pretty much exactly what you are trying to do: it runs some code on it and creates a new Arc. You can see how it passes the entire Arc into the tree_node:: function; the tree_node mod is pretty much like the collection of member functions that operate on the Arc.

---

More details

There is only two ways to create an Rc object:

• By transferring ownership of an owned but not yet refcounted object into it. For example, if you have self (not &self), you can do Rc::new(self), which moves self into a new reference counted storage and returns an Rc to it.
• From an existing Rc: If you halready have an Rc object, meaning, the reference counted object already lives in a reference counted storage, you can do Rc::clone(&other_rc), which simply increases the reference count by one and returns a new Rc object.

You can not create an Rc object from &self or &mut self, because those are references, meaning the object the reference is already stored somewhere else. You cannot create a new Rc reference counter for a reference, because Rc has to own the object (makes sense, because it has to destroy the object if all Rc references to it are gone, and you can't destroy an object behind a reference). Even if the object referenced by &self already lives inside of a reference counted storage, the datatype &self has no way of finding that out. You need an actual Rc object to create a new Rc object.

Here is an example of how this could work. Note that I also made tail a Weak reference to avoid cyclic references.

#![allow(dead_code)]

use std::{
    cell::RefCell,
    fmt::Debug,
    rc::{Rc, Weak},
};

pub struct ChainVecNode<T> {
    item: Vec<T>,
    head: Option<ChainVec<T>>,
    tail: Option<ChainVecWeak<T>>,
}

pub struct ChainVec<T> {
    inner: Rc<RefCell<ChainVecNode<T>>>,
}

pub struct ChainVecWeak<T> {
    inner: Weak<RefCell<ChainVecNode<T>>>,
}

impl<T> ChainVecNode<T> {
    fn push_head(this: &Rc<RefCell<ChainVecNode<T>>>, prealloc: usize) {
        this.borrow_mut().head = Some(ChainVec::new_with_links(
            prealloc,
            None,
            Some(ChainVecWeak {
                inner: Rc::downgrade(this),
            }),
        ))
    }
}

impl<T> ChainVec<T> {
    fn new(prealloc: usize) -> Self {
        Self::new_with_links(prealloc, None, None)
    }

    fn new_with_links(
        prealloc: usize,
        head: Option<ChainVec<T>>,
        tail: Option<ChainVecWeak<T>>,
    ) -> Self {
        let item: Vec<T> = Vec::with_capacity(prealloc);
        Self {
            inner: Rc::new(RefCell::new(ChainVecNode { item, head, tail })),
        }
    }

    fn push_head(&mut self, prealloc: usize) {
        ChainVecNode::push_head(&self.inner, prealloc)
    }
}

impl<T: Debug> Debug for ChainVec<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        writeln!(f, "ChainVec {{")?;
        let mut current = Rc::clone(&self.inner);
        loop {
            let current_ref = current.borrow();
            writeln!(f, "    {:?}", current_ref.item)?;
            let next = if let Some(next) = &current_ref.head {
                Rc::clone(&next.inner)
            } else {
                break;
            };

            drop(current_ref);
            current = next;
        }
        write!(f, "}}")
    }
}

fn main() {
    let mut chain_vec: ChainVec<u32> = ChainVec::new(100);
    chain_vec
        .inner
        .borrow_mut()
        .item
        .extend_from_slice(&[1, 2, 3, 4, 5]);

    chain_vec.push_head(100);

    println!("{:?}", chain_vec)
}

ChainVec {
    [1, 2, 3, 4, 5]
    []
}

Note that I forward the call of push_head into ChainVecNode::push_head, but pass self (here called this) as an actual &Rc object. This is the trick that is necessary to deal with this problem.