Error with the Hashbrown library: "dropped here while still borrowed"

[madmann91]

So I've been trying to implement a simple hash-consing library. I am trying to match the speed of my C implementation, and as the current rust version using fxHashMap was still slower, I decided to give Hashbrown a go. Unfortunately, even though it should be a direct replacement for fxHashMap, I get these "dropped here while still borrowed" errors now. I have managed to reduce my problem to the short listing below (playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=bef6e35df318356a3880f37ef23a7b40):

use hashbrown::HashMap;
use std::cell::RefCell;

type BrokenTable<'a> = HashMap<&'a i32, &'a i32>;

struct NonSense<'a> {
    exps: RefCell<BrokenTable<'a>>,
    x: Box<i32>
}

impl<'a> NonSense<'a> {
    fn new() -> NonSense<'a> {
        NonSense {
            exps: RefCell::<BrokenTable::<'a>>::new(BrokenTable::<'a>::default()),
            x: Box::new(1)
        }
    }

    fn foo(&'a self) -> &'a i32 {
        &self.x
    }
}

fn test() {
    let n = NonSense::new();
    let i = n.foo();
    println!("{}", i);
}

Is this a bug? Am I doing something wrong? Any suggestions to replace fxHashMap? I'd be very happy to have someone's input on this.

[billyrieger]

I believe the error is with this function signature: fn foo(&'a self) -> &'a i32. Even though the struct itself is generic over the lifetime 'a, a reference to &self does not need to have that same lifetime. Changing the method to fn foo(&self) -> &i32 appears to work.

Rust Playground

[madmann91]

Unfortunately that does not work in my setting, because I need to have a 'a &T argument to foo:

fn foo(&self, _: &'a i32) -> &i32 {
    &self.x
}

So, with this, even if the the lifetimes on self and the return value have been removed, the error still shows up.

[SkiFire13]

The initial code doesn't work because:

1. &'a NonSense<'a> ask for a reference that must be valid for at least 'a, but points to something that is not guaranteed to live more than 'a.
2. Usually this is made more ergonomic by shortening the lifetime 'a, meaning the reference doesn't really have to live as long as the struct it is borrowing.
3. However NonSense<'a> is invariant with respect to 'a because it appear inside a RefCell (i.e. you can't get a NonSense<'b> from a NonSense<'a> if 'a: 'b, no lifetime shortening!)
4. There's still one way to satisfy the existance of &'a NonSense<'a>, which is by making the reference live exactly as long as the struct it is borrowing.
5. However NonSense<'a> needs to be dropped because it contains a field that needs to be dropped (HashMap), which in turn means the reference must be dropped before NonSense<'a> and they can't live exactly the same.

The "corrected" code doesn't work pretty much for the same reason, except now the lifetimes are hidden. Using the return value of foo where a &'a i32 is expected forces that &self to be a &'a self, which bring us back to the starting point.

In the end what you're trying to make is a self-referential struct which unfortunately is not possible in safe rust. You should probably look for crates like rental or ouroboros which encapsulate the unsafe code needed and expose a safe (although limited) interface.

[madmann91]

Thank you for the detailed answer. I am still struggling to understand why this works with fxHashMap (see https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=aca4844d494a5f1767b06f559bffbc30) and not with hashbrown::HashMap.

This NonSense structure should act like a factory and I want the objects that are created by this factory to share the same lifetime as the factory. That does not have to be a cycle, since I know it's safe to drop the created objects before the factory. Isn't there a way to model that without those libraries or unsafe code? Maybe by introducing another lifetime parameter?

[cuviper]

The standard HashMap is actually implemented around hashbrown too!

The difference is that when built as part of std, hashbrown enables unstable features like the #[may_dangle] here, which tells the compiler that the map's Drop doesn't access the type's borrowed lifetime (your 'a). This allows your method to take the &'a self for the rest of NonSense<'a>'s life.

The independent version of hashbrown in the playground is not built with that feature.