How to return an *optional* reference into RefCell contents

1k views Asked by At

I have a type that stores its data in a container behind a Rc<RefCell<>>, which is for the most part hidden from the public API. For example:

struct Value;

struct Container {
    storage: Rc<RefCell<HashMap<u32, Value>>>,
}

impl Container {
    fn insert(&mut self, key: u32, value: Value) {
        self.storage.borrow_mut().insert(key, value);
    }

    fn remove(&mut self, key: u32) -> Option<Value> {
        self.storage.borrow_mut().remove(&key)
    }

    // ...
}

However, peeking inside the container requires returning a Ref. That can be achieved using Ref::map() - for example:

// peek value under key, panicking if not present
fn peek_assert(&self, key: u32) -> Ref<'_, Value> {
    Ref::map(self.storage.borrow(), |storage| storage.get(&key).unwrap())
}

However, I'd like to have a non-panicking version of peek, that would return Option<Ref<'_, Value>>. This is a problem because Ref::map requires that you return a reference to something that exists inside the RefCell, so even if I wanted to return Ref<'_, Option<Value>>, it wouldn't work because the option returned by storage.get() is ephemeral.

Trying to use Ref::map to create a Ref from a previously looked up key doesn't compile either:

// doesn't compile apparently the borrow checker doesn't understand that `v`
// won't outlive `_storage`.
fn peek(&self, key: u32) -> Option<Ref<'_, Value>> {
    let storage = self.storage.borrow();
    if let Some(v) = storage.get(&key) {
        Some(Ref::map(storage, |_storage| v))
    } else {
        None
    }
}

The approach that does work is to perform the lookup twice, but that's something I'd really like to avoid:

// works, but does lookup 2x
fn peek(&self, key: u32) -> Option<Ref<'_, Value>> {
    if self.storage.borrow().get(&key).is_some() {
        Some(Ref::map(self.storage.borrow(), |storage| {
            storage.get(&key).unwrap()
        }))
    } else {
        None
    }
}

Compilable example in the playground.

Related questions like this one assume that the inner reference is always available, so they don't have that issue.

I found Ref::filter_map() which would solve this, but it's not yet available on stable, and it's unclear how far it is from stabilization. Barring other options, I would accept a solution that uses unsafe provided it is sound and relies on documented guarantees.

4

There are 4 answers

1
Kevin Reid On BEST ANSWER

You could use a side effect to communicate whether the lookup succeeded, then return an arbitrary value from Ref::map if you don't have a successful value.

impl Container {
    // ...

    fn peek(&self, key: u32) -> Option<Ref<'_, Value>> {
        let storage = self.storage.borrow();
        if storage.is_empty() {
            // The trick below requires the map to be nonempty, but if it's
            // empty, then we don't need to do a lookup.
            return None;
        }

        // Find either the correct value or an arbitrary one, and use a mutable
        // side channel to remember which one it is.
        let mut failed = false;
        let ref_maybe_bogus: Ref<'_, Value> = Ref::map(storage, |storage| {
            storage.get(&key).unwrap_or_else(|| {
                // Report that the lookup failed.
                failed = true;
                // Return an arbitrary Value which will be ignored.
                // The is_empty() check above ensured that one will exist.
                storage.values().next().unwrap()
            })
        });
        
        // Return the ref only if it's due to a successful lookup.
        if failed {
            None
        } else {
            Some(ref_maybe_bogus)
        }
    }
}

Refinements:

  • If the Value type can have constant instances, then you can return one of those instead of requiring the map to be nonempty; the method above is just the most general one that works for any definition of Value, and not the simplest. (This is possible since a &'static Value satisfies Ref's requirements — the reference just needs to live long enough, not to actually point into the RefCell's contents.)

  • If the Value type can have a constant instance that is distinct from any meaningful instance that would be found in the map (a "sentinel value"), then you can check for that value in the final if instead of checking a separate boolean variable. However, this doesn't especially simplify the code; it's mostly useful if you have a sentinel you're using for other purposes anyway, or if you like a “pure functional” coding style which avoids side effects.

And of course, this is all moot if Ref::filter_map becomes stable.

0
user4815162342 On

Here is the solution I ended up using until Ref::filter_map() is stabilized. It changes the signature of peek() from that specified in the question, so I won't be accepting this answer, but it might be useful for others who stumble upon this issue.

While peek() is a powerful primitive, its usage at call sites boils down to inspecting certain properties of the value and making decisions based on that. For that kind of usage, the caller doesn't need to retain the reference, it only needs temporary access to it to extract the properties it cares about. So we can let peek accept a closure that examines the value, and return its result:

fn peek<F: FnOnce(&Value) -> R, R>(&self, key: u32, examine: F) -> Option<R> {
    self.storage.borrow().get(&key).map(examine)
}

Where with peek() as originally specified one would write:

if let Some(event) = container.peek() {
    if event.time() >= deadline {
        container.remove_next();
    }
}

...with the peek() from this answer, one would instead write:

if let Some(event_time) = container.peek(|e| e.time()) {
    if event_time >= deadline {
        container.remove_next();
    }
}
2
user3840170 On

I managed to come up with this:

fn peek<'a>(&'a self, key: u32) -> Option<Ref<'a, Value>> {
    // Safety: we perform a guarded borrow, then an unguarded one.
    // If the former is successful, so must be the latter.
    // Conceptually, they are the same borrow: we just take the pointer
    // from one and the dynamic lifetime guard from the other.
    unsafe {
        let s = self.storage.borrow();
        let u = self.storage.try_borrow_unguarded().unwrap();
        u.get(&key).map(|v| Ref::map(s, |_| &*(v as *const _)))
    }
}

I simply borrow the hashmap twice, then cast the lifetime away (by converting the reference into a pointer), then bring it back by re-borrowing the pointer’s referent. I un-elided the lifetime parameter just to be sure it doesn’t become too long.

I think it’s correct. I’d nevertheless keep looking forward to filter_map just to be sure.


Asker later came up with this variant, which I include here for the sake of avoiding link rot:

fn peek<'a>(&'a self, key: u32) -> Option<Ref<'a, Value>> {
    // Safety: we convert the reference obtained from the guarded borrow
    // into a pointer. Dropping the reference allows us to consume the
    // original borrow guard and turn it into a new one (with the same
    // lifetime) that refers to the value inside the hashmap.
    let s = self.storage.borrow();
    s.get(&key)
        .map(|v| v as *const _)
        .map(|v| Ref::map(s, |_| unsafe { &*v }))
}
0
user4815162342 On

As of Rust 1.63, released on Aug 11 2022, Ref::filter_map() is stable, so this simple solution is available:

pub fn peek(&self, key: u32) -> Option<Ref<'_, Value>> {
    Ref::filter_map(self.storage.borrow(), |storage| storage.get(&key)).ok()
}

Playground