Rc::Weak=Box::? , tree not DAG, Rc that can only be used once

1

TLDR, Rc::Weak = Box :: ???

Longer Version:

Here is a concrete class:

pub enum SExp {
  Num(i64),
  List(Vector<Container<SExp>>),  // What do we use for Container ?
}

I have the following weird requirement:

  1. I want the compiler to enforce that this particular data structure is a TREE, not merely a DAG. In particular, I want to statically enforce that nodes can NOT be shared. I.e. each node has at most 1 parent.

  2. I want to be able to refer to nodes and store aux data. For example, to have a HashMap that allows me to lookup the parent of a Node.

  3. I want to avoid memory leaks.

===

Now, let's work through the design space a bit:

Suppose all we care about is (1). Then the right choice is to use Box instead of Rc. This ensures that we are storing a TREE, not a DAG.

Now, ignore (1) for now. focus only on (2) and (3). One way to do this is to store everything via Rc. Then, for (2), we just use Weak's to store things like "Weak_X is parent of Weak_Y".

===

So now there is where I'm stuck. As far as I know, there isn't any "???" that satisfies "Rc::Weak = Box::???". Yet, on the other hand, I want a compiler enforced "this is a TREE, not a DAG" property that Box offers over Rc.

Suggestions ?

2

Tree or DAG is not important. If the allocation can be aliased, it should be Rc/Arc. Imagine if you've implemented it using Rc/Weak. Now each non-leaf nodes can be accessed in more than one path - one from the parent, and others from the children by upgrading Weak. Note that in children case, you need more than one Rc living at once, though temporarily.

General solution here would be to not alias the allocation at all. Instead of to store up-reference, you may maintain accessor stack at tree searcher like Iterator implementation.

1 Like
3

I'm not 100% sure, but you might be right on this. It is strange that I am (1) making distinction of Tree vs DAG yet (2) perfectly okay with Rc_child -> Weak_child -> Weak_parent -> Rc_parent

Perhaps I should be thinking about enforcing the "Tree" structure in another manner, say:

pub struct NoCloneRc<T>(Rc<T>);

impl <T> NoCloneRc<T> {
  pub fn new(t: T) -> NoCloneRc<T> {
    NoCloneRc(Rc::new(t))
  }
}
// just making this up on the spot, no idea of implications
4

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.