I have a lifetime compiler error that has broken my mental model of how I thought lifetimes are used.
The intent of the code is to prevent at compile time, by use of a lifetime parameter and PhantomData, a Ptr instance from outliving the Allocator instance that manages the memory that Ptr points to. I borrowed and mangled the pattern from https://github.com/rphmeier/allocators/
I've broken down my code to both represent the overall picture of what I want to do but to also be as minimal as I can make it to reproduce the error.
When the compiler says that syms does not live long enough, I simply do not understand the error in this context. The concept of a lifetime parameter and what it means has become too abstract for my brain to process
There may well be other eyebrow-raising features of my code, I'd be glad of any feedback.
I think the problem is that the lifetimes say what you wish was true, not what actually happens.
Keep in mind that lifetimes don't do anything, and they don't affect generated code in any way whatsoever. They're only like test assertions.
fn lookup(&'a self)
says that self, which is syms lives as long or longer than the Allocator. However, in:
fn setup(allocator: A) -> SymbolMap<'a, A> {
let syms = SymbolMap::new(allocator);
I think what compiler means here is that syms is created after the Allocator, and its actual lifetime is limited to that function, so the actual lifetime 'a becomes limited to life of that function, not as long as the allocator.
It might also be a case of self-referential struct, which just isn't going to pass borrow checker by design. Have you seen rental - Rust?
There are a few issues here, most of which @kornel already identified.
You almost never want to write &'a self when 'a is the struct's lifetime parameter. At best, this will borrow your struct for its entire lifetime, rendering it essentially unusable afterwards. In this case, it doesn't even work because it's impossible to borrow it for at least as long as 'a because the concrete lifetime that will be used is caller supplied (since 'a is a lifetime parameter on setup), and your struct is created within setup itself. So, you're asking for the impossible . The fix for this portion alone would be to change &'a self to just &self in lookup.
The other big issue, again as pointed out by @kornel, is self referential structs. As written, SymbolMap owns the allocator given to it. In lookup, the code tries to insert the Ptr into the internal HashMap but that Ptr is created by the owned allocator - that effectively creates a self-reference.
You probably want your SymbolMap to take a reference to an allocator, rather than own it. You should then be able to insert values it returns into a map inside SymbolMap, which will be safe because those values outlive your SymbolMap (since the allocator outlives the SymbolMap, as it's coming in as a reference externally).
Also, why do you need the Ptr type at all? If you just want to indicate that the allocator return value is tied to the allocator, I would think something like fn alloc<T>(&self) -> &mut T would work, no? The lifetime of the returned mutable reference would automatically be tied to the allocator.
The reason I want Ptr instead of simply &T is that this I'm playing with an interpreter in Rust where the internal memory management semantics need pointers to be copied around. Maybe that's possible with &T (certainly not &mut T) but then every T type would need to have interior mutability for each of it's members and that seems more... verbose and more overhead (Cell requires it's contents to be Copy and RefCell has runtime borrow checking overhead.) Honestly I don't really know the most idiomatic way to do this in Rust and maybe my approach is inherently unsafe?
Anyway, in the code snippet, Ptr is Copy + Clone so I don't follow the referential structs argument. self.syms.alloc() returns a Ptr, a copy of which is passed to the HashMap. Surely that avoids the self-reference problem? I guess I thought that if syms is within the SymbolMap instance, their lifetimes would all be the same and therefore interchangeable.
Now if I remove the 'a from lookup(&'a self, ...) the lifetime problem moves to self.syms.alloc(...) in lookup(). If I change SymbolMap to hold a &'a Allocator instead of owning the instance, the compiler succeeds. I'm going to go with that.
How do you intend to prevent aliasing if you're essentially allowing copying a mutable pointer? It seems like you're trying to present a safe API so just curious.
I think self-referential was the wrong way to describe the issue. The problem is really because you own the allocator but it returns something with a lifetime beyond the SymbolMap itself. RefCell is invariant over lifetimes because it allows interior mutability. As such you cannot "shrink" the lifetime of Ptr<'a, ...> to the lifetime of self (SymbolMap itself). Once you take an allocator reference, you can do that because the lifetime isn't conflicting between SymbolMap and the allocator. At least that's my thinking.
I'm exploring interpreters and memory management in Rust: typical interpreted languages aren't concerned about preventing aliasing and some runtimes have copying or moving collectors. How to bridge the gap between that kind of unsafety and Rust's type system isn't obvious to me. I'm neither any kind of expert in interpreters or mm and also not particularly adept at wielding Rust's type system yet so my results may be less than useful
To be clear, you mean you'd like to use the Rust language to implement an interpreter for some arbitrary language? Or are you implementing a Rust interpreter in Rust? I'm guessing it's the former, but wanted to clarify.
If it's the latter indeed, then the aliasing I'm referring to would be aliasing in your implementation, not the aliasing semantics of your language. Sort of similar to, eg, hitting C++ UB while implementing a JVM in it.
I guess that's your question about how to bridge the two worlds? That's an interesting question. How does one model unsafe (by Rust's definition) concepts that are safe in the target language/interpreter. Perhaps the Miri project, GitHub - rust-lang/miri: An interpreter for Rust's mid-level intermediate representation, could be interesting. AFAIK, it attempts to build an abstract machine for Rust in Rust. Although it's targeting Rust, it wants to model unsafety as well, and that could be considered an analog. But, I don't know much about it beyond that so can't comment much more on it.
. The fix for this portion alone would be to change