Is this the idiomatic way to make self-referential structures?

Question

I am interested in knowing the idiomatic/canonical way of making self-referential structures in Rust. The related question Why can't I store a value and a reference to that value in the same struct explains the problem, but try as I might, I couldn't figure out the answer in the existing question (although there were some useful hints).

I have come up with a solution, but I am unsure of how safe it is, or if it is the idiomatic way to solve this problem; if it isn't, I would very much like to know what the usual solution is.

I have an existing structure in my program that holds a reference to a sequence. Sequences hold information about chromosomes so they can be rather long, and copying them isn't a viable idea.

// My real Foo is more complicated than this and is an existing
// type I'd rather not have to rewrite if I can avoid it...
struct Foo<'a> {
    x: &'a [usize],
    // more here...
}
impl<'a> Foo<'a> {
    pub fn new(x: &'a [usize]) -> Self {
        Foo {
            x, /* more here... */
        }
    }
}

I now need a new structure that reduces the sequence to something smaller and then builds a Foo structure over the reduced string, and since someone has to own both reduced string and Foo object, I would like to put both in a structure.

// My real Bar is slightly more complicated, but it boils down to having
// a vector it owns and a Foo over that vector.
struct Bar<'a> {
    x: Vec<usize>,
    y: Foo<'a>, // has a reference to &x
}


// This doesn't work because x is moved after y has borrowed it
impl<'a> Bar<'a> {
    pub fn new() -> Self {
        let x = vec![1, 2, 3];
        let y = Foo::new(&x);
        Bar { x, y }
    }
}

Now, this doesn't work because the Foo object in a Bar refers into the Bar object

and if the Bar object moves, the reference will point into memory that is no longer occupied by the Bar object

To avoid this problem, the x element in Bar must sit on the heap and not move around. (I think the data in a Vec already sits happily on the heap, but that doesn't seem to help me here).

A pinned box should do the trick, I belive.

struct Bar<'a> {
    x: Pin<Box<Vec<usize>>>,
    y: Foo<'a>, 
}

Now the structure looks like this

and when I move it, the references point to the same memory.

However, moving x to the heap isn't enough for the type-checker. It still thinks that moving the pinned box will move what it points to.

If I implement Bar's constructor like this:

impl<'a> Bar<'a> {
    pub fn new() -> Self {
        let v: Vec<usize> = vec![1, 2, 3];
        let x = Box::pin(v);
        let y = Foo::new(&x);
        Bar { x, y }
    }
}

I get the error

error[E0515]: cannot return value referencing local variable `x`
  --> src/main.rs:22:9
   |
21 |         let y = Foo::new(&x);
   |                          -- `x` is borrowed here
22 |         Bar { x, y }
   |         ^^^^^^^^^^^^ returns a value referencing data owned by the current function

error[E0505]: cannot move out of `x` because it is borrowed
  --> src/main.rs:22:15
   |
17 | impl<'a> Bar<'a> {
   |      -- lifetime `'a` defined here
...
21 |         let y = Foo::new(&x);
   |                          -- borrow of `x` occurs here
22 |         Bar { x, y }
   |         ------^-----
   |         |     |
   |         |     move out of `x` occurs here
   |         returning this value requires that `x` is borrowed for `'a`

Some errors have detailed explanations: E0505, E0515.
For more information about an error, try `rustc --explain E0505`.

(Playground)

Even though the object I take a reference of sits on the heap, and doesn't move, the checker still sees me borrowing from an object that moves, and that, of course, is a no-no.

Here, you might stop and notice that I am trying to make two pointers to the same object, so Rc or Arc is an obvious solution. And it is, but I would have to change the implementation of Foo to have an Rc member instead of a reference. While I do have control of the source code for Foo, and I could update it and all the code that uses it, I am reluctant to make such a major change if I can avoid it. And I could have been in a situation where I am not in control of the Foo, so I couldn't change its implementation, and I would love to know how I would solve that situation then.

The only solution I could get to work was to get a raw pointer to x, so the type-checker doesn't see that I borrow it, and then connect x and y though that.

impl<'a> Bar<'a> {
    pub fn new() -> Self {
        let v: Vec<usize> = vec![1, 2, 3];
        let x = Box::new(v);
        let (x, y) = unsafe {
            let ptr: *mut Vec<usize> = Box::into_raw(x);
            let w: &Vec<usize> = ptr.as_ref().unwrap();
            (Pin::new(Box::from_raw(ptr)), Foo::new(&w))
        };
        Bar { x, y }
    }
}

Playground code here

What I don't know is if this is the right way to do it. It seems rather complicated, but perhaps it is the only way to make a structure like this in Rust? That some sort of unsafe is needed to trick the compiler. So that is the first of my questions.

The second is, if this is safe to do? Of course it is unsafe in the technical sense, but am I risking creating a reference to memory that might not be valid later? It is my impression that Pin should guarantee that the object remains where it is supposed to sit, and that the lifetime of the Bar<'a> and Foo<'a> objects should ensure that the reference doesn't out-live the vector, but once I have gone unsafe, could that promise be broken?

Update

The owning_ref crate has functionality that looks like what I need. You can create owned objects that present their references as well.

There is an OwningRef type that wraps an object and a reference, and it would be wonderful if you could have the slice in that and getting the reference wasn't seen as borrowing from the object, but obviously that isn't the case. Code such as this

use owning_ref::OwningRef;
struct Bar<'a> {
    x: OwningRef<Vec<usize>, [usize]>,
    y: Foo<'a>, // has a reference to &x
}

// This doesn't work because x is moved after y has borrowed it
impl<'a> Bar<'a> {
    pub fn new() -> Self {
        let v: Vec<usize> = vec![1, 2, 3];
        let x = OwningRef::new(v);
        let y = Foo::new(x.as_ref());
        Bar { x, y }
    }
}

you get the error

error[E0515]: cannot return value referencing local variable `x`
  --> src/main.rs:22:9
   |
21 |         let y = Foo::new(x.as_ref());
   |                          ---------- `x` is borrowed here
22 |         Bar { x, y }
   |         ^^^^^^^^^^^^ returns a value referencing data owned by the current function

error[E0505]: cannot move out of `x` because it is borrowed
  --> src/main.rs:22:15
   |
17 | impl<'a> Bar<'a> {
   |      -- lifetime `'a` defined here
...
21 |         let y = Foo::new(x.as_ref());
   |                          ---------- borrow of `x` occurs here
22 |         Bar { x, y }
   |         ------^-----
   |         |     |
   |         |     move out of `x` occurs here
   |         returning this value requires that `x` is borrowed for `'a`

Some errors have detailed explanations: E0505, E0515.
For more information about an error, try `rustc --explain E0505`.
error: could not compile `foo` due to 2 previous errors

The reason is the same as before: I borrow a reference to x and then I move it.

There are different wrapper objects in the crate, and in various combinations they will let me get close to a solution and then snatch it away from me, because what I borrow I still cannot move later, e.g.:

use owning_ref::{BoxRef, OwningRef};
struct Bar<'a> {
    x: OwningRef<Box<Vec<usize>>, Vec<usize>>,
    y: Foo<'a>, // has a reference to &x
}

// This doesn't work because x is moved after y has borrowed it
impl<'a> Bar<'a> {
    pub fn new() -> Self {
        let v: Vec<usize> = vec![1, 2, 3];
        let v = Box::new(v); // Vector on the heap
        let x = BoxRef::new(v);
        let y = Foo::new(x.as_ref());
        Bar { x, y }
    }
}

error[E0515]: cannot return value referencing local variable `x`
  --> src/main.rs:23:9
   |
22 |         let y = Foo::new(x.as_ref());
   |                          ---------- `x` is borrowed here
23 |         Bar { x, y }
   |         ^^^^^^^^^^^^ returns a value referencing data owned by the current function

error[E0505]: cannot move out of `x` because it is borrowed
  --> src/main.rs:23:15
   |
17 | impl<'a> Bar<'a> {
   |      -- lifetime `'a` defined here
...
22 |         let y = Foo::new(x.as_ref());
   |                          ---------- borrow of `x` occurs here
23 |         Bar { x, y }
   |         ------^-----
   |         |     |
   |         |     move out of `x` occurs here
   |         returning this value requires that `x` is borrowed for `'a`

Some errors have detailed explanations: E0505, E0515.
For more information about an error, try `rustc --explain E0505`.

I can get around this by going unsafe and work with a pointer, of course, but then I am back to the solution I had with Pin and pointer hacking. I strongly feel that there is a solution here, (especially because having a Box<Vec<...>> and the corresponding Vec<...> isn't adding much to the table so there must be more to the crate), but what it is is eluding me.

Answer 1

I think I have finally grokked ouroboros and that is an elegant solution.

You use a macro, self_referencing when defining a structure, and inside the structure you can specify that one entry borrows others. For my application, I got it to work like this:

use ouroboros::self_referencing;

#[self_referencing]
struct _Bar {
    x: Vec<usize>,
    #[borrows(x)]
    #[covariant]
    y: Foo<'this>,
}
struct Bar(pub _Bar);

The y element references x, so I specify that. I'm sure why co-/contra-varianse is needed in this particular case where there is only one lifetime, but it specififes whether other references should live longer or can live shorter than the object. I've defined the struct as _Bar and then wrapped it in Bar. This is because macro will create a new method, and I don't want the default one. At the same time I wnat to call my constructor new to stick with tradition. So I wrap the type and write my own constructor:

impl Bar {
    pub fn new() -> Self {
        let x: Vec<usize> = vec![1, 2, 3];
        let _bar = _BarBuilder {
            x,
            y_builder: |x: &Vec<usize>| Foo::new(&x),
        }
        .build();
        Bar(_bar)
    }
}

I don't use the generated _Bar::new but a generated _BarBuilder object where I can specify how to get the y value from the x reference.

I have also written accessors to get the two values. There isn't anything special here.

impl Bar {
    pub fn x(&self) -> &Vec<usize> {
        self.0.borrow_x()
    }
    pub fn y(&self) -> &Foo {
        self.0.borrow_y()
    }
}

and with that my trivial little test case runs...

fn main() {
    let bar = Bar::new();
    let vec = bar.x();
    for &i in vec {
        println!("i == {}", i);
    }

    let vec = bar.y().x;
    for &i in vec {
        println!("i == {}", i);
    }
}

This is probably the best solution so far, assuming that there are no hidden costs that I am currently unaware of.

Answer 2

(I think the data in a Vec already sits happily on the heap, but that doesn't seem to help me here).

Indeed the data in a Vec does already sit on the heap, and the x: &'a [usize] in Foo is already a reference to that heap allocation; so your problem here is not (as shown in your graphics) that moving Bar would result in (the undefined behaviour of) a dangling reference.

However, what happens if the Vec were to outgrow its current allocation? It would reallocate and be moved from its present heap allocation to another—and this would result in a dangling reference. Hence the borrow checker must enforce that, so long as anything (e.g. a Foo) that borrows from the Vec exists, the Vec cannot be mutated. Yet here we already have an expressivity problem: the Rust language has no way to annotate Bar to indicate this relationship.

Your proposed unsafe solution uses <*mut _>::as_ref, whose safety documentation includes the following requirement (emphasis added):

• You must enforce Rust’s aliasing rules, since the returned lifetime 'a is arbitrarily chosen and does not necessarily reflect the actual lifetime of the data. In particular, for the duration of this lifetime, the memory the pointer points to must not get mutated (except inside UnsafeCell).

This is the key bit of the compiler's safety checks that you are trying to opt out of—but because accessing Bar now requires that one uphold this requirement, you do not have a completely safe abstraction. In my view, a raw pointer would be a tad safer here because it forces one to consider the safety of every access.

For example, one issue that immediately springs to mind is that x is declared before y in Bar and therefore, upon destruction, it will be dropped first: the Vec's heap allocation will be freed while Foo still holds references into it: undefined behaviour! Simply reordering the fields would avoid this particular problem, but there would have been no such problem with raw pointers (and any attempt to dereference them in Foo's drop handler would have forced one to consider whether they were still dereferenceable at that time).

Personally, I would try to avoid self-referencing here and probably use an arena.