Feedback on an isomorphic data structure

help
1

Would someone like to give me feedback on an isomorphic data structure in rust? (my first real code in rust beyond a few lines of code).

What I don't like is the use of unsafe.

Speed and memory usage are not a priority; having idiomatic, clean, easy to reason about and safe code, is.

2

Nice. What's an "isomorphic" data stucture? I'm curious.

I'll address the unsafe block since you asked. It looks unproblematic if you can guarantee that the parent pointer always is valid, however a closer look at how you get this parent pointer is needed.

You get it from &mut self in fn new_contained_node of course. But what this means is if self, the graph, moves, that invalidates the raw pointer!

If you take a graph g from your testcase and move that g value (for example push it to a vector), now the parent pointer is invalid.

We can only get a stable parent pointer if we know it's inside a box or an Rc. If you can make sure fn new_contained_node or similar is only called on an Rc-graph, then it's stable. And then you can use a Weak instead too.

3

How would I do that, in concrete code?

4

I would probably use a free function (something like: fn foo(graph: Rc<RefCell<Graph>>)) or a new trait to add a method to the Rc<RefCell<Graph>> type.

5

I'll have to underline here that this is a typical case (the validity of the parent pointer) where the safety becomes a non-local property. It's not enough to look at only the unsafe blocks but the whole lifecycle of that raw pointer. How it's created, changed, cloned(?) etc, all spread out over the module.

6

What is the syntax to add a method to such a nested type?

7

Will have to use a trait for now. Define the methods in a new trait, then implement it: impl CustomTrait for Rc<RefCell<Graph>> { ...

8

Thanks for your feedback, I have updated the code.

Would you or someone else like to offer feedback on the current version?

It's at the same address: hypergraph.rs · GitHub

One particular aspect disturbs me a lot: the ergonomy of the code. For instance, the last assertion assert!(g == new_node.as_ref().unwrap().borrow().parent().as_ref().unwrap().upgrade().unwrap());.

9

I have two ideas, they can be considered, not sure if they pay off:

  • Change from using Rc<RefCell<Graph>> to Rc<Graph> and use RefCell internally instead. This would make it easier for both implementation and for external users I believe.

  • Returning Rc instead of Weak from new_contained_node — it's more useful for the caller, and they can still choose either way to keep a weak or strong reference.

10

Thanks bluss.

With your help, I got to realize that rust is always forcing me to do the right thing.

For instance, I wanted to keep new() unparameterized and at the same time, to reuse it in another factory method, which is a no go in terms of OOP: "the object must at all times be in a valid state".

And although I know this and I would apply this principle in bigger projects, in higher-level abstractions, the rust compiler forces me to do it also on the smaller scale.

Maybe this code will help someone learn from my mistakes: hypergraph.rs · GitHub

As always, I am welcoming any feedback.

There is one thing bothering me: the clone on line 126, it doesn't feel right.