An append only structure and getting myself in a mess of lifetimes

1

I have a scene structure that I only add entities to of the (simplified form):

struct<'scene> Scene<'scene> {
  entities : Vec<Pin<Box<dyn Entity + 'scene>>>
}

Where add just pushes a boxed entity to the back of the vector. And the entities cant be mutated after adding but i can add entities that have references to previously created entities.

Ideally i would like to write an add method which constructs a new entity and returns a stable reference to it that others can use that lasts the lifetime of the Scene object

So something like:

impl<'scene> Scene<'scene> { 
  pub fn add_thing(&mut self, data : &Data) -> &'scene dyn Entity {
    self.entities.push(Box::pin(ThingEntity::new(data)))
    self.entities.last().unwrap().as_ref().get_ref()
  }
}

However this (rightly) complains that my output type needs to live as long as the mutable borrow of self. If i extend the mutable borrow of the self to be as long as the scene exists for (&'scene mut self) then this method works but i can only ever add one item to my scene.

Ideally i would want to make the output reference last as long as the scene however i understand why we can't (if some other theoretical holder of a mutable reference to entities could drop by pinned box early and invalidate my reference.

It is possible that I have just ended up confusing myself and there is a easy way to convince the compiler that as we only add to the vector I can extend the reference of the element to the parent type. Or it could be that i am just being dumb and the idea cant really work - is unsound.

There is a couple of ways around it (the most basic one being wrapping all references in ref counted pointers and move the checking to runtime)

2

That's a self-referencial struct. TL;DR, references (&, &mut) are the wrong tool for the job. Also, Pin doesn't magically make self-referencial things work without unsafe. And Box is probably also best avoided as your borrows are invalidated when the Vec resizes (moves the Boxes).

There's no solution using actual references without unsafe,[1] and with unsafe it's notoriously hard to get right. You're better off with raw pointers if you try to tackle it yourself.

There are also some self-referencial crates that try to be sound (with a history of failures and potentially outstanding unsoundness). ouroboros and yoke are the two I've seen most frequently. I can't vouch for them, but they exist.

  1. well, except the "borrow forever" approach which is pretty much never adequate ↩︎

2 Likes
3

Thank you, Well at least I know i wasn't missing an obvious solution.

I will have a look at those crates. As well as sitting down and having a bit more of a think about this.

4

Although (without unsafe) there is no way to have a self-referential struct using references, you can of course use indexes instead. This is a very common solution. In general, using indexes (or other types of keys) rather than references in data structures is something that quickly becomes a habit when using Rust. By design, Rust references are meant to be short lived.

1 Like
5

I had a version with indices however i was a bit worried that i was just using that to get around lifetime tracking. If i am storing indices there is still a lifetime is dependence (is this id still pointing at the object i thought it is and is that still valid) but it needs to be proved manually.

6

That is true. But at least we have bounds checking to catch errors before they cause a memory safety problem.

1 Like
7

Sure i will take panics over inscrutable memory corruption any day!

As I said the previous code was all pointer based from C++ so i am not loosing anything with the change - I was just checking to see if I could find a way of the compiler helping me more!

1 Like
8

There's also the elsa crate; its FrozenVec::push_get() looks a bit like your add_thing().

1 Like
9

By the way, despite the name, Rust lifetimes ('_ things) are generally about the duration of borrows and not value liveness.[1] There's also no direct connection with the lifetime of a borrow and the, how to say, identity of an object...[2] though I suppose you did account for that aspect with Pin and being append-only, consciously or not.

A Scene<'scene> doesn't have to exist for all of 'scene, for example, and a Box<dyn Trait + 'static> need not be leaked.

  1. It'd be less confusing if they had a different name, but here we are. ↩︎

  2. Lifetimes can be used as part of something that does that, it turns out, but that's not what they're intrinsically about. ↩︎

1 Like
10

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.