Illegal recursive struct type; wrap the inner value in a box to make it representable

help
1 
use std::vec::Vec;
use std::boxed::Box;
use std::option::Option;

struct Graph {

    /// Graphs can be nested. For a simple graph G made of the nodes A and B,
    /// G being this Graph, the nodes A and B are stored in this list.
    containedNodes: Vec<Box<Graph>>,

    /// the parent graph which contains this node.
    parent: Option<Graph>,

    /// A list of edges. Classical graphs only have edges made of two nodes.
    /// Defining hyperedges is easy: just make an edge containing more than
    /// two nodes.
    ///
    /// When an edge made of nodes with different parents is about to be
    /// formed, the parent for all of them is set to the top-most common
    /// ancestor for all of the nodes making up the edge.
    edges: Vec<Vec<Box<Graph>>>,

    /// A list of edges which contain (go through) this node
    passThroughEdges: Vec<Box<Graph>>,
}

impl Graph {
    fn new() -> Graph {
        Graph {
            containedNodes: Vec::new(),
            parent: Option::None,
        }
    }
}
fn main() {
    println!("Hello, world!");
}

I do not understand what the compiler wants from me. For me, the Graph (the name might be misleading, it's going to be a hypergraph) looks quite wrapped in a box.

How to fix this issue?

2

The compiler doesn't know the size of the struct, because you're using it recursively. See, when you tell the compiler you want a Graph inside the Graph, it will try to calculate the size of it, and it will never end. It'll try to do sizeof(Graph) + sizeof(Graph) + sizeof(Graph) + ... forever. And because of this, you need to create a reference, so that the compiler knows the size of it and it finally compiles.

edit: Check the Option out: parent: Option<Graph>.

1 Like
3

What kind of reference? How would the code look like?

4

Try to use a parent: Option<Box<Graph>>.

edit: Here's the code: Rust Playground

1 Like
5

That can't possibly work for any actual graph because the parent owns the children. He'll need to use a Weak pointer (see std::rc::Weak).

1 Like
6

Not really. A simple reference is better for this situation.

7

No, stebalien is right. Simple references (especially not Box<Graph>) can't be used to point from children to parents while also pointing from parents to children. Not if you expect to be able to do anything useful with them. You can't move the parent into the child and a &Graph would render the pointed to value immutable and immovable.

1 Like
8

Oh, I see. Sorry, these concepts are still trying to find its place in my brain.

9

It's understandable. This is one of the weak points of the borrow checker. Hierarchical structures (trees and single linked lists) are all good, but cyclic structures (double liked lists and some graphs) are hard to get right without Rc<T>.

1 Like
10

You can also store your graph in a directed adjacency list.

11

How to create a weak reference? I am used to read all kind of API docs (javadoc, doxygen, etc), but I still have a hard time with the rust stdlib docs.

Obviously line 55 does not work

parent: Option::Some(Weak::new(parent)),
12

I know what can be done in terms of representations (it is, however, a more generic type of a hypergraph, not a simple graph), but for now, the focus is on the clarity of the code, not on optimizations - since it's an experimental prototype, what I need first and foremost is understanding myself how I could use this data structure.

That's why I won't do it that way (yet). Besides, it's a great oportunity to learn rust (by doing).

13

The std::rc module docs should help: std::rc - Rust

OT: You can read doxygen?

14

Thanks Rc::downgrade() worked.

I had to activate #![feature(alloc)], why is that?

I am running rustc 1.1.0-nightly (7bd71637c 2015-05-06) (built 2015-05-06)

15

Weak pointers are not stable in 1.0 apparently: Using unstable APIs? Tell us about it! - #96 by aepsil0n

1 Like