How to have struct reference its owning collection

1

Is there a way in Rust, without using Arc, or Rc, to have a structure hold a non-owning reference back to a collection that owns it?

Here's my example code:

struct Organization<'a> {
    name: String,
    people: Vec<Person<'a>>,
}

struct Person<'a> {
    org: &'a Organization<'a>,
    index: usize,
    name: String,
}

fn main() {
    let mut rust_101 =
        Organization { name: "Rust Beginners".to_string(), people: Vec::new(), };
    let index = rust_101.people.len();
    rust_101.people.push(
        Person { 
            org: &rust_101,
            name: "Me".to_string(),
            index,
        },
    );

    for (i,person) in rust_101.people.iter().enumerate() {
        println!("i={}, org={}", i, person.name);
    }
}

Here is the compiler error. I understand the error, and so I'm wondering what the best work around there is. Ultimately it would be nice if the reference could be mutable, but I cannot get past the immutable option. I wish to avoid using Arc or Rc because the reference I wish to store is not to be an owner so I don't want the overhead it brings.

error[E0502]: cannot borrow `rust_101.people` as mutable because it is also borrowed as immutable
  --> src/main.rs:16:5
   |
16 |       rust_101.people.push(
   |       ^               ---- immutable borrow later used by call
   |  _____|
   | |
17 | |         Person {
18 | |             org: &rust_101,
   | |                  --------- immutable borrow occurs here
19 | |             name: "Me".to_string(),
20 | |             index,
21 | |         },
22 | |     );
   | |_____^ mutable borrow occurs here
2

This is essentially a self-referential struct (albeit indirectly). It is usually said that these are impossible to build in safe Rust.

1 Like
3

This is not possible with ordinary references. You could do it with Rc and Weak, but honestly you would get a better design if you just don't have cyclic references.

6 Likes
4

The topic of self-referential structs resurfaces on this forum periodically, often with a reference to the article Introduction - Learning Rust With Entirely Too Many Linked Lists. Self-referential structs appear to be a common design pattern in other languages that does not translate well into Rust.

Is there a recommended (idiomatic) approach to employ instead of a self-referential struct that can address the majority of use cases? The kind of stuff that we find in Introduction - Rust Design Patterns?

5

In many cases there are idiomatic alternatives, but how that looks varies depending on what you are doing. The main exception is when you are dealing with libraries that force you to use callbacks (e.g. gtk), in which case Rc is nearly unavoidable.

In your case for example, I might create a struct with a Person and Organization vector or hash map, then replace the references with indexes or ids.

6

Thanks for the feedback. I'm curious about Weak and will look into that. I see Weak is described as Rc withhout the ownership part. Since I'm not interested in these references being owners, it seems to make sense to avoid related overhead there.

7

I know what you mean, but....

struct Node {
       name: String,
       children: Vec<Node>
}

Works great for me so far. Where I'm running into trouble is with specialized operations involving temporary collections of references into individual nodes.

I'm getting the feeling that there needs to be some API (probably using unsafe code properly) that will deliver what Arc and Rc deliver as a solution to this problem, but without the reference counting overhead because the ownership is all the tree itself.

8

That's a bit like saying you could have a Vec type without index checking. Rust strongly steers you towards safety ( it is POSSIBLE to make an unsafe Vec type, it's just not encouraged ).

9

It's actually nothing like saying that. I think you may be misunderstanding me. Vec, Rc, Arc and many other std APIs use plenty of unsafe rust. Are you aware of that? And that is the sense in which I meant to qualify unsafe with the word "properly".

I'm simply saying that the API I am hypothetically referring to would most likely have to similarly use unsafe code -- (unsafe rust may be the better term.)

10

You could certainly attempt to write another safe wrapper that allows something like this, but whether that is possible depends a lot on the exact shape of the API you actually want. The actual storing of the pointers would need to happen with raw pointers, and can't happen in user-defined types.

11

I completely agree. In fact I would not attempt such a thing until I having a really solid feel for the material here: Implementing Vec and here: Implementing Arc

And any other pointers you may have!

12

Correct, I see now you are thinking of a SAFE API. But I think such an API, if it allows individual elements of the tree to be identified, is inevitably going to incur some overhead when an element is accessed, that is, a when simple reference or simple mutable reference to the element is obtained, due to the alias rules on simple references. There is no such thing as a free lunch!

13

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.