Node trait for tree structure

help
1

Hi there I'm new here so just let me know if I'm doing this the wrong way.

I'm trying to create a Node trait that allows types with the Node trait to connect.
This is how I do it in javascript

class Node {
  this.connections = []
  connect(node){
    node.set(this)
    return node
  }
  set(input){
    this.connections.push(input)
  }
}

Then I extend from that class to all subclasses and that allows me to do trees like this.

let float = new Float()
let math = new Math()
let rect = new Rectangle()

float
  .connect(math)
  .connect(rect)

Now I'm trying to do something similar in Rust and I realized that it was a bit harder than I thought.

I've tried to do it with RefCells but here I have the problem because of the &self connect which makes
Rc::new(RefCell::new(self) to not work because it doesn't expect a reference.

trait MyNode {
    fn connect(&self, node: Rc<RefCell<dyn MyNode>>) -> Rc<RefCell<dyn MyNode>> where Self: Sized {
        node.borrow_mut().set(Rc::new(RefCell::new(self)));
        node
    }
    fn set(&mut self, node: Rc<RefCell<dyn MyNode>>);
}

struct Float{
    connections: Vec<Rc<RefCell<dyn MyNode>>>
}

impl MyNode for Float{
    fn set(&mut self, node: Rc<RefCell<dyn MyNode>>){
        self.connections.push()
    }
}

I also tried to do it without cells but this is as far as I got and when I tried to introduce the mutation part there where so many lifetime issues I didn't know where to start.

trait Node<'a>{
    fn connect<T: Node<'a>>(&'a self, node: &'a T) -> &T where Self: Sized{
        node.set(self);
        node
    }
    fn set<T: Node<'a>>(&self, node: &T);
}

Does anyone have a tip for me to implement this, or a library where I can have a look at the implementation?

2 
Rc::new(RefCell::new(self))

This can never work because self is a reference. You can only get an Rc/RefCell if you have ownership.

Node<'a>

If you have a lifetime on your trait or types, it will never compile.

To get something like this to compile, you would need self to already be wrapped in Rc/RefCell before the connect calls are made.

Regardless, the design you're going for seems very unidiomatic. What's your actual goal?

1 Like
3

Don't try to program javascript in rust, you are in for a rough time if you do. I'd give this blog a read, it's short and informative, and you are making mistakes 3 and 6.a on it.

To implement a node graph like this you need to use an Rc<RefCell<dyn Node>> combo. It's extremely difficult and awkward, as you have found out, and even if you do succeed, you will likely run into reference cycles. Since rust doesn't have a gc, that means you will likely leak large chunks of memory.

If you would like a graph, use a proper graph type. It'll be much easier than whatever you're trying to do here. If you need a tree, you can get away with fairly simple struct/enum combo:

enum NodeType{
    Rect, //any variant associated data can go here
    Triangle,
}
struct Node{
    variant: NodeType,
    children: Vec<Node>, //any data shared between all nodes goes here
}
2 Likes
4

Thanks for your replies!

What I’m going for is a node tree for graphics, skia in this case.

I’ve built it with javascript with canvas and modeled the api the same way the web audio api works.

So basically when the canvas node requests a draw it triggers get through the tree to evaluate math nodes and animation timelines and stuff like that.

So every node will do different things before it returns a float.

From your answers I take it I need to do it in a different way for Rust then.

I thought the principle was quite simple though, a node can have other nodes in it and be part of other and a get() in the node will trigger get() in the nodes it holds

5

You should consider having one large collection of all of the nodes, then using indexes or ids to look up their neighbours. This usually works pretty well.

This results in a cyclic ownership structure, which is incompatible with the single-owner principle of Rust.

1 Like
6

Thank you! I will try that out!

I saw in the rust web audio api crate that it’s done that way, but I was determined that it could be done! :nerd_face:

I was wrong (again) :joy:

7

If you only want a tree, then you don't need any reference counting. You can just have Boxes or a Vec tor of children, which you can then borrow mutably as needed. Trees lend themselves quite naturally to Rust's single ownership model.

struct Node {
    data: u64, // or whatever
    children: Vec<Node>,
}

impl Node {
    fn do_stuff(&mut self) {
        self.data += 1;
        for child in &mut self.children {
            child.do_stuff();
        }
    }
}
8

Yeah but if I want several types that “are” Nodes?
Like float, math, rectangle, circle and so on..

9

Still having problem storing the types of the trait

10 
struct Graph{
    current: i16,
    nodes: Vec<& dyn Node>
}

impl Graph{
    fn float(&mut self) -> Float{
        self.current += 1;
        let f = Float{id: self.current, connections: vec![]};
        self.nodes.push(&f);
        f
    }
}

trait Node{
    fn get_id(&self)->i16;
    fn connect<'a>(&'a self, node: &'a mut dyn Node) -> &mut dyn Node{
        node.set(self.get_id());
        node
    }
    fn set(&mut self, node: i16);
}

struct Float{
    id: i16,
    connections: Vec<i16>
}

impl Node for Float {
    fn get_id(&self) -> i16{
        self.id
    }
    fn set(&mut self, node: i16){
        self.connections.push(node);
    }
}


fn main() {
   let mut graph =  Graph{current: 0, nodes: vec![]};
   let mut float = graph.float();
   let mut float1 = graph.float();
   let mut float2 = graph.float();
   
   float
     .connect(&mut float1)
     .connect(&mut float2);

}

I guess I just need a different way to store the nodes in the graph and still return it from connect()

11

Sorry I meant from the create method on Graph

12

Then you replace the concrete type with Box<dyn Node> – which you already seem to be doing anyway. Example.

1 Like
13

That’s nice! Thanks!

And if I wanted to add a method on Node that sets a child and also returns the child?

Like root.set(child).set(child1)

14

Well, what then?

15

I mean that now the methods return &[Box<dyn Node>]

Which I don’t really understand in the first place to be honest, but I take it I can’t just chain method calls on that return?

16

You are free to return whatever you want from each method, and you can also add new ones. My code above was just an example.

17

Yeah, but that was the thing the question was about.
I wasn’t able to set it up so that I was able to mutate the node passed to connect, in this case passing the self into connections of this node.
Then returning that node so I can chain it.

And have that as a trait that all nodes can implement.

Also when the lowest node runs get it will run get recursively and when get is runned inside a node the return from its parent should be stored inside the node so the get is mutating as well

18

Are you looking for something like this?

19

Not exactly I made a boilerplate example here with a lot of problems, but I think it shows the idea.
Example

20

As already pointed out by others, you can't have simultaneous, mutual mutable references between objects.