Is it possible to provide something like StaticRc<T, 0, DEN> for temporarily sharing?

[frank-king]

Sometimes, it needs to yield a temporarily shared pointer of StaticRc. In Rc, it is done by Clone::clone, and the reference counting in Rc can make sure the shared objects outlives all of its shared pointers.

But in StaticRc, in can only be achieved by StaticRc::split, which requires to consume the value first, and the splitted pointers must be joined back after usage.

I am thinking of such matters:

What if providing something like StaticRc<T, 0, DEN> or naming Weak<T> to allow temporarily sharing without consuming the pointer or borrowing from it?

impl<T, const NUM: usize, const DEN: usize> StaticRc<T, NUM, DEN> {
    pub fn split(&self) -> StaticRc<0, DEN>
    where
        AssertLeType!(NUM + 1, DEN): Sized, //  here `NUM` must be `< DEN` because owned objects might be mutated
    {
        let pointer = self.pointer;
        StaticRc { pointer }
    }
}

However, it will never be safe if the temporarily yielded pointers lives longer than the host pointer. So there need to be a mechanism to constrain the lifetime of StaticRc.

The only thing come up in my mind is the GhostCell with GhostToken. If we add a covariant lifetime tag 'id like StaticRc<'id, T, NUM, DEN>, then it is possible to require pub fn split(&self) -> StaticRc<'id, 0, DEN> where the yielded pointer lives no longer than the host pointer. Nevertheless, the implementation details can be much more complicated.

---

Actually, I have been encountering this problem where using StaticRc and GhostCell to develop a safe doubly-linked list.

The type of linked list is defined as following:

pub struct List<'id, T> {
    head: Option<NodePtr<'id, T>>,
    tail: Option<NodePtr<'id, T>>,
    len: usize,
}

struct Node<'id, T> {
    next: Option<NodePtr<'id, T>>,
    prev: Option<NodePtr<'id, T>>,
    elem: T,
}

type NodePtr<'id, T> = Half<GhostCell<'id, Node<'id, T>>>;

type Half<T> = StaticRc<T, 1, 2>;
type Full<T> = StaticRc<T, 2, 2>;

And I implemented a push_back and pop_back method:

    pub fn push_back(&mut self, side: usize, elem: T, token: &mut GhostToken<'id>) {
        // Create a new node and split up to two halves.
        let (left, right) = Full::split(Full::new(GhostCell::new(Node::new(elem))));
        match self.tail.take() {
            Some(tail) => {
                // Link the left pointer. If the list is empty, link `self.head`.
                tail.deref().borrow_mut(token).next = Some(left);
                // Transfer the ownership of `self.tail` before insertion to the new inserted node.
                right.deref().borrow_mut(token).prev = Some(tail);
            }
            None => self.head = Some(left),
        }
        // Link the right pointer to `self.tail`.
        self.tail = Some(right);
    }
    pub fn pop_back(&mut self, side: usize, token: &mut GhostToken<'id>) -> Option<T> {
        // Take the right pointer from `self.tail`. Or return `None` if the list is empty.
        let right = self.tail.take()?;
        let left = match right.deref().borrow_mut(token).prev.take() {
            Some(tail) => {
                // If the previous of `self.tail` is not empty, take the left pointer from its `next`,
                // or else take the left pointer from `self.head`.
                let left = tail.deref().borrow_mut(token).next.take().unwrap();
                // Relink `self.tail`.
                self.tail = Some(tail);
                left
            }
            None => self.head.take().unwrap(),
        };
        // Join the left and right pointers, and returns the  popped node.
        Some(Full::into_box(Full::join(left, right)).into_inner().elem)
    }

Everything worked fine until I tried to implement a mutable iterator for it. First I wrote:

pub struct IterMut<'id, 'iter, T> {
    head: Option<&'iter NodePtr<'id, T>>,
    tail: Option<&'iter NodePtr<'id, T>>,
    len: usize,
    token: &'iter mut GhostToken<'id>,
}

impl<'id, 'iter, T> Iterator for IterMut<'id, 'iter, T> {
    type Item = &'iter mut T;

    fn next(&mut self) -> Option<Self::Item> {
        let current = self.head?;
        self.head = current.deref().borrow(self.token).next;
        self.len -= 1;
        // Compiler error: `token` was borrowed immutable first then mutable.
        Some(&current.deref().borrow_mut(self.token).elem)
    }
}

In alternative, I tried another way to implement the mutable iterator via an embedded way (similar to Iterator::for_each).

    pub fn for_each_mut(&self, token: &mut GhostToken<'id>, mut f: impl FnMut(&mut T)) {
        let mut current = self.head.as_ref();
        while let Some(node) = current {
            let node = node.deref().borrow_mut(token);
            f(&mut node.elem);
            current = node.deref().next.as_ref();
        }
    }

And the compiler complained:

error[E0499]: cannot borrow `*token` as mutable more than once at a time
   --> src/experiments.rs:182:48
    |
182 |             let node = node.deref().borrow_mut(token);
    |                                                ^^^^^ `*token` was mutably borrowed here in the previous iteration of the loop

Actually, in this line, let node = node.deref().borrow_mut(token); I only needed to borrow the elem of the node inside the loop body. but current = node.deref().next.as_ref(); extended the lifetime of the borrowed node, so in the while loop, the token was multiply borrowed mutably, and yielded a compile error.

To solve this problem, I have already tried to temporarily take the ownership of the next pointer by Option::take, then split it up to two type Quarter<T, 1, 4>s. It then led to another problem. Since the next of the next pointer must borrow from the splitted pointer, it cannot be joined together again in the loop body. I have to store all of the splitted pointers during the loop, and joined back them after the end of the loop. It can bring extra time and memory cost, which is definitely unacceptable.

---

That's all the background where I opened this issue.

Anyway, StaticRc is a great and intelligent invention! And hope it becomes more powerful in the future! :)

[matthieu-m]

Unfortunately, as you noticed, a StaticRc<T, 0, DEN> is necessarily unsafe as it does not own any fraction of T and thus the T can be dropped at any time.

---

With regard to mutable iterators: it is not possible to provide mutable iterators safely, to the best of my knowledge. Remember that &mut T guarantees unique access to this particular value, and it's impossible in general to prove that the sequence of items yielded by an iterator will not contain the same element multiple times.

This leaves at least two avenues:

• The Cursor: similar to an Iterator, with the exception that the Cursor itself is borrowed for the duration during which the &T or &mut T is available. This prevents moving the Cursor and yielding a second reference, guaranteeing unicity in the case of &mut T.
• An Iterator<Item = &Cell<T>>, for some Cell, provided that you can navigate through your collection without losing the ability to mutably borrow the cells.

You may be interested in the ghost-collections repository which uses StaticRc and GhostCell and has 2 variations of Linked Lists.