I'd like to create a vector of TestStruct. TestStruct has an optional reference to another TestStruct instance. No TestStruct will ever reference itself, nor will there be circular references with the intended use. Multiple others can reference the same TestStruct. The TestStruct instances do not need to mutate.
Is it possible to express this using references, or do I need Rc and Weak?
struct TestStruct<'a>
{
other: Option<&'a TestStruct<'a>>
}
fn testFn()
{
let mut events = vec![TestStruct{other: None}];
events.push(TestStruct{other: Some(&events[0])});
}
yields:
error[E0502]: cannot borrow `events` as mutable because it is also borrowed as immutable
--> src\test.rs:9:5
|
9 | events.push(TestStruct{other: Some(&events[0])});
| ^^^^^^^----^^^^^^^^^^^^^^^^^^^^^^^^^------^^^^^^
| | | |
| | | immutable borrow occurs here
| | immutable borrow later used by call
| mutable borrow occurs here
Can I make it work for example by creating a vector of Box<TestStruct> instead? Or will a reference to a TestStruct whose box is in the vector implicitly borrow the vector as well?
If we accept some restrictions,
Vecthen this can be done with typed_arena::Arena:
// [dependencies]
// typed-arena = "2.0.1"
use typed_arena::Arena;
struct TestStruct<'a> {
other: Option<&'a TestStruct<'a>>,
}
pub fn test_fn() {
let events = Arena::new();
let first = &*events.alloc(TestStruct { other: None });
let second = &*events.alloc(TestStruct { other: Some(first) });
}
The key difference in what Arena offers is that Arena::alloc() takes &self — indicating that only a shared reference to the arena is required to allocate (add the element). Rust's mutability rules therefore tell us that we can keep using the returned reference even as we alloc() more, whereas Vec::push() invalidates all existing references (as it must, since the vector's items might be moved into reallocated memory to grow the vector).
However, all those references are still borrows of the arena. Thus, the arena is effectively pinned — you cannot, for example, take this whole data structure and return it from a function; you have to use it in the scope it was created, or a nested scope or function call. The restrictions are essentially the same as if you had implemented your algorithm via a tail-recursive function — that is, the function could put each TestStruct in a let variable and then call itself with the reference to it, to accumulate a set of values that can reference older values.
There are other ways to make a “self-referential” data structure in Rust, such as ouroboros, but as far as I know none of them support making an arbitrary-depth graph that is also movable. If you require the ability to return the structure after creating it, then you should use Rc or Arc, or an explicit graph data structure such as that provided by petgraph.
Adding indirection via Box does not help permit this sort of reference structure, for two reasons:
Box implies uniqueness of the pointer to its contents in exactly the same way direct ownership or &mut does. As far as the language rules are concerned, moving a Box<T> has exactly the same implications for an &T as moving the T itself does. (ouroboros works by creating something Box-like that does not assert uniqueness in this way.)
There's nothing in the borrow checker to perform analysis which proves that the box isn't dropped until after the references to it are. For example, suppose Vec<Box<TestStruct>> were allowed; this would imply that the TestStructs have to be dropped in reverse order of their position in the vector (otherwise an impl Drop for TestStruct could observe an invalid reference). But, there is nothing in Vec that says the items can't be reordered, so that would not be sufficient.
You would need a special data structure that allows only safe operations, and drops in the right order (basically a combination of the ideas from typed_arena and ouroboros). In principle, such a data structure could exist, but I don't know of one having been written.