Backlinks, another approach

Playground: Rust Playground

Here's a way to create weak backlinks. I want this because the struct needs some kind of handle to itself to be called by some future event. This works a lot like a future, but it's for stateful objects.

This seems workable but clunky. Is there a better way?

Not stable yet, but: new_cyclic. (Playground.) (Tracking issue.)

2 Likes

That's a nice convenience feature. With new_cyclic, you can eliminate the Option<> from my code. Right now, you can have a struct field of Weak, but there's no good way to initialize it, because you need the value before it is available.

Knowing that's coming, I can use the code I have, then replace "new" and "get" later without affecting callers. So, good answer.

You don't need to wrap with Option even without new_cyclic, since you can create a weak reference that doesn't point at anything with Weak::new(). new_cyclic does make it a lot less clunky though.

2 Likes

Yes, that's a better solution. Don't need to wrap Weak in an Option because Weak has its very own null value.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=1ba2000be207d239a566ff54ecbf231c

The use case I keep needing is single ownership with weak references. I'd like to have something like Rc<RefCell<foo>> for weak borrow-only references. That is, I should be able to do borrow, borrow_mut, try_borrow, and try_borrow_mut, but not upgrade to full ownership.

Rc<RefCell<foo>> will do this, but it's overpowered for the job and you lose all compile time borrow checking. It would be nice to retain borrow checking on the ownership side and only have run time checks on the borrow side.

This is problematic because you need to make sure that foo doesn’t get dropped while one of these borrows is active. If, for example, you use the backlink to tell your parent to drop all of its children, you’re left with a dangling pointer inside the local stack frame; the borrow won’t be released until sometime after drop_children() returns.

Since these things usually run in a runtime, you can use the runtime to give you a unique identifier that can be used in further events.

Right. that would have to be a panic condition, caught in drop.

So here's how I'm doing backlinks now.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=323f36e2891be0a538597de22c080390

type FooLink = Rc::<RefCell<Foo>>;

#[derive(Default)]
struct Foo {
    pub self_link: Weak<RefCell<Foo>>, // we can give this out and clone it
    child: Option<Bar>, // parent to child single ownership
    name: String,
}
struct Bar {
    owner: FooLink,
}

This works, but it seems way too complicated and ugly. Is there an easier way?

I would tend to write something like this:

struct Tree<T> {
    parent: Cell<Weak<Self>>,
    children: RefCell<Vec<Rc<Self>>>,
    pub data: T
}

/* impls removed; see playground for details */

fn main() {
    let parent = Tree::new("The parent".to_string());
    let child = Tree::new("The child".to_string());
    
    parent.append(&child);
    
    for c in parent.children() {
        match c.parent() {
            Some(p) => println!("Parent is: {}", p.data),
            None => println!("Root node")
        }
    }
}

NB: This has immutable data in each node, but that can be a RefCell if mutability is needed.

That's cleaner than what I was doing. A step forward.

What I'd really like is something Rust doesn't support:

  • Single ownership, enforced. (So lists and trees are possible.)
  • Weak references available. (So references to the owner work)
  • Weak references can be borrowed and used to access data, but never take ownership. (Differs from Rc)
  • Dropping a strong pointer while the struct is borrowed causes a panic. (Essential for soundness).

This is a lot like Rc and Arc, but retains single-ownership semantics. Static analysis could, at least in theory, examine the scope of all borrows and determine whether the borrow count and drop-time check are necessary. It's not as dynamic as Rc, but handles many common cases, such as trees and doubly linked lists.

This is a use case I keep hitting in game work, where I have a tree-like structure with weak backlinks. Doing this with Rc works, but it's verbose.

Comments?

My instincts say that the internal mechanism for this would essentially be the same as Rc: You need to keep track of how many borrowed Weaks exist in order to panic at appropriate times, which is isomorphic to a reference count.

You might want to look at GhostCell. I haven't read farther than the abstract, but my first impression is that it combines all of the interconnected nodes of a data structure into a single virtual object that gets borrowed as a unit.

Since you could build it on top of Rc and RefCell, yes.

The real breakthrough would be an expansion of the borrow checker to check it statically. There's some work going on in that area. That would be a big win, because backlinks are normal in C++ but hard in Rust, which makes conversion to Rust harder.

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.