1

I have a struct Oid, which owns a vector of distinct objects. It also has a reverse map which maps an object to its index in the vector. Objects are never deleted from the struct. However, new objects can be added. The use case is simple: I need fast retrieval of an object by its index and of the index of a given object. Here's my attempt so far:

struct Oid<'a, T>
where
    T: Eq + Hash,
{
    objects: Vec<Box<T>>,
    rev_map: HashMap<&'a T, usize>,
}

impl<'a, T> Oid<'a, T>
where
    T: Eq + Hash,
{
    pub fn insert(&mut self, t: T) -> usize {
        match self.objects.get(&t) {
            Some(&i) => i,
            _ => {
                let i = self.objects.size();
                self.objects.push(Box::new(t));
                self.rev_map
                    .insert(unsafe { &*(&*self.objects[i] as *const T) }, i);
                i
            }
        }
    }
}

As the memory locations of objects can change as the vector grows, I put each object in a Box, which ensures address stability. The problem is in rev_map, I can't figure out how to tell Rust that the object reference will never outlive the struct. Is there a way to do this in idiomatic Rust?

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
sl0th
  • 113
  • 1
  • 5
  • Maybe the crate [bidir-map](https://crates.io/crates/bidir-map) could help you? – Lukas Kalbertodt Jan 20 '18 at 09:51
  • @LukasKalbertodt I disagree with marking this as duplicate. The question is not why the presented `struct` doesn't work, but how got get it working in a idiomatic way. The answers of the linked question don't answer this particular problem as far as I can tell. – Stefan Jan 20 '18 at 10:31
  • If `bidir_map` is not a solution I guess you could write your own abstraction (this will require `unsafe` code blocks; I'd probably use `&'static T` references internally). I would keep this abstraction separate from the remaining logic for this type so it is easier to check whether your `unsafe` code blocks are safe. – Stefan Jan 20 '18 at 10:33
  • @Stefan "*tell Rust that the object reference will never outlive the struct. Is there a way to do this in idiomatic Rust?*" -- No, there is not a way to do that in idiomatic, non-unsafe Rust. This is explained in the linked answers. At least that's how I understood this question. But if others also think this was wrong, I have no problem with reopening this via Reopen votes :) – Lukas Kalbertodt Jan 20 '18 at 12:31
  • @LukasKalbertodt I disagree with your implied statement that idiomatic code cannot use `unsafe` blocks (also I wouldn't read too much into the word "idiomatic" - users are usually just looking for a good/acceptable solution, and a good abstraction using `unsafe` blocks certainly fits). If I had the reputation to vote for reopening I certainly would. – Stefan Jan 20 '18 at 13:00
  • @Stefan Oh, no no, I didn't want to imply this (I meant it as in "I like reading nice, long books" ... which doesn't imply that only long books can be nice). But as you said: you would want to hide `unsafe` behind an abstraction and not scatter it around in your actual program logic. Let's wait for others to vote to reopen, then. – Lukas Kalbertodt Jan 20 '18 at 13:07
  • @Stefan I've updated my question with a detailed implementation. Can you explain why `'static` is preferable in this case? – sl0th Jan 20 '18 at 14:08
  • @LukasKalbertodt Thanks for the suggestion but bidir-map is O(n), which is not efficient enough for my case. I've also read the linked post but I wasn't satisfied with the solution. – sl0th Jan 20 '18 at 14:17
  • 1
    @sl0th Well, in your abstraction you need to use `unsafe`. That means you can either use `unsafe` to use raw pointers (but creating them is safe iirc), or use `unsafe` to transform normal lifetimes into `'static`. The `HashMap` is easier to use with `&'static T` than with raw pointers (you'd probably have to wrap them in a struct). – Stefan Jan 20 '18 at 14:20
  • @sl0th Also maybe try using `Rc` first. If you don't use threads this should just work. With threads and your described scenario you probably could mark the `Oid` [`Sync`](https://doc.rust-lang.org/std/marker/trait.Sync.html) and it would still be safe. – Stefan Jan 20 '18 at 14:32
  • 1
    @Stefan If you want to show how to implement a BiDir map using unsafe, the additional duplicate I've added would be a good place. – Shepmaster Jan 20 '18 at 14:52

0 Answers0