mod private {
// Allocator similar to bumpalo's Bump allocator which uses interior mutability style allocation methods and is also `Send` but not `Sync`.
pub struct Allocator {}
impl Allocator {
// Always returns non-aliasable/"unique" data reference that "lives" as long as 'a
pub fn raw<'a>(&'a self) -> &'a usize {
// Just an example.
Box::leak(Box::new(0usize)) as _
}
}
impl Allocator {
pub fn new() -> Self {
Self { }
}
}
}
use private::Allocator;
struct Arena<'s> {
alloc: &'s mut Allocator,
}
impl<'s> Arena<'s> {
// We must take a mutable reference, so others can't allocate while Arena uses it.
fn new(alloc: &'s mut Allocator) -> Self {
Self { alloc }
}
fn intern<'a>(&'a self) -> &'s usize
where
's: 'a,
{
// data has 'a, the shorter lifetime instead of the longer one 's (due to `alloc` being a mutable reference, I assume)
let data = self.alloc.raw();
return data;
// unsafe { std::mem::transmute::<&'_ usize, &'s usize>(data) }
}
}
fn main() {
let mut alloc = Allocator::new();
let arena = Arena::new(&mut alloc);
let a = arena.intern();
let b = arena.intern();
println!("{a:?}, {b:?}");
// Reuse alloc.
let arena = Arena::new(&mut alloc);
let c = arena.intern();
let d = arena.intern();
println!("{c:?}, {d:?}");
}
The arena struct mutably borrows the Allocator which should provide non-aliasing immutable data space for the arena (not shown in the code above for simplicity, but imagine something like bumpalo's Bump allocator).
The intern method should return a data reference with the lifetime of the allocator. However rustc errors with:
error: lifetime may not live long enough
--> src/main.rs:36:16
|
25 | impl<'s> Arena<'s> {
| -- lifetime `'s` defined here
...
30 | fn intern<'a>(&'a self) -> &'s usize
| -- lifetime `'a` defined here
...
36 | return data;
| ^^^^ associated function was supposed to return data with lifetime `'s` but it is returning data with lifetime `'a`
|
= help: consider adding the following bound: `'a: 's`
I understand the issue here, however I also think that this might be overly restrictive? Since, ideally, rustc could also pick the longer lifetime 's over the shorter 'a, but it doesn't because of the mutable allocator reference. Obviously, using unsafe code here to force the longer lifetime onto it, is possible, and might be sound? But I might be missing something here... Is there a way to do this in a purely safe and sound way?
(Based on what you've shared) store a &'s Allocator, not a &'s mut Allocator.
If you have a &'short &'long mut A, and you return a &'long ThingInA, then 'short expires and &'long mut A becomes exclusive again... but it's observable through &'long ThingInA. That's the soundness problem. As the rules stand now it's instant UB.
I am aware of that, however I've also mentioned why the Arena has to take a mutable reference to the Allocator (it's intentional/by design) in the code above: We must take a mutable reference, so others can't allocate while Arena uses it.. There are reasons the allocator shouldn't be used while the Arena has ownership of it.
If you have a &'short &'long mut A , and you return a &'long ThingInA , then 'short expires and &'long mut A becomes exclusive again... but it's observable through &'long ThingInA . That's the soundness problem. As the rules stand now it's instant UB.
I understand that. However the allocator always returns a newly allocated non-aliasable reference (That has the lifetime of the allocator). So we don't technically return a &'long ThingInA. I don't think this violates any aliasing issues here. Transmuting this, so it has the 's/'longer lifetime should be fine then? (Also sorry, the example code didn't reflect that part, I just briefly mentioned it behaving like bumpalo's Bump allocator). But I realize now, that this might be impossible to actually express in safe Rust code.
It's not possible to implement an allocator/arena in safe Rust, because there's no way to declare these constraints in a way that borrow checker will check. You will have to transmute the lifetimes.
Technically speaking, I am not doing that. I agree that the terminology used in the example code is somewhat confusing or wrong. The idea was to build a wrapper around an existing bump allocator (like bumpalo's Bump allocator). But it turns out that some of the "lifetime concepts leak out" and one has to resort to unsafe code
I did indeed miss that comment, sorry. But I think my suggestion still stands:
struct Arena<'s> {
alloc: &'s Allocator,
}
impl<'s> Arena<'s> {
// Assuming this is the only way to create the Arena, you still
// have to exclusively borrow the `Allocator` for `'s` in order
// to create it.
//
// This comes up when people wish they could do stuff like
// let shared_ref = hash_map.insert_fancy(new_value);
// do_stuff_with(&hash_map);
// println!("{shared_ref}");
//
// They can't, because the `hash_map` is still exclusively
// borrowed so long as `shared_ref` is around. But in this case
// it's working in your favor.
fn new(alloc: &'s mut Allocator) -> Self {
Self { alloc }
}
Alternatively I think you could also keep the &'s mut but have intern look like:
fn intern(&'s self) -> &'s usize
A &'x &'y mut Allocator is covariant in both 'x and 'y so you won't hit the kind of problems you get with &'z mut &'z [mut] Allocator locking up the inner struct forever.
Unless I'm not fully understanding some further need beyond the borrow checker in the code provided.
You are absolutely right. It does work (Somehow I could've sworn seeing compiler issues with that because I remembered trying that before. I guess I did not .)
To add to the other answers, the reason your original code can't work is that it allows this code:
let mut alloc = Allocator::new();
let arena = Arena::new(&mut alloc);
let a = arena.intern();
// This drops the arena from which `a` was taken.
drop(std::mem::replace(arena.alloc, Allocator::new()));
// This is now invalid because it prints from freed memory.
dbg!(a);
(Somehow I could've sworn seeing compiler issues with that because I remembered trying that before. I guess I did not 
.)