I have a series of (cryptographic) data structures for which some data can be missing. Secondly, I need to be able to determine what data is required to perform a given operation, and "prune" the parts that aren't needed. For this I'm using the following generic enum:
enum Maybe<'p, T: 'p> {
Missing(Hash),
Avail(T),
Ref(&'p Maybe<'p, T>, LazyCell<T>),
}
Basically, either a given value is missing, available, or we have a reference to it, and a RefCell variant that may or may not have a pruned version of the original. Now by pruning, suppose I have the following:
enum Cons<'p, T: 'p> {
Nil,
Cell(T, Rc<Maybe<'p, Cons<'p, T>>>),
}
I can create a linked-list with a few entries in it, and then create a pruned version referencing the original:
let orig = Maybe::Avail(Cons::from_iter(0..15));
let pruned = Maybe::Ref(&orig);
Now the idea is that as data is accessed in pruned via an unprune() method implemented by Maybe, Cons cell instances are created via interior mutation. So I have the following trait:
trait Prune<'p> for T {
fn prune(&'p self) -> Self;
fn fully_prune(self) -> Self;
}
prune() is supposed to produce an object whose prunable fields are in turn Maybe instances referencing the original; once you've done whatever operations you need to do, fully_prune() then replaces any unpruned references with Missing.
The problem is lifetimes. For instance, a working implementation of Prune<'p> for Maybe has these lifetimes:
fn prune<'p, 'a: 'p>(self: &'p Maybe<'a>) -> Maybe<'p>
The only way to represent that in a trait is with an associated type:
trait Prune<'p> for T {
type Pruned;
fn prune(&'p self) -> Self::Pruned;
}
...but that means I can't implement Maybe (and many other things) generically, as it can contain either T or T::Pruned instances, which quickly runs into the problem that T::Pruned also needs to implement Prune, giving you T::Pruned::Pruned... You can't even use mem::transmute() for this, as there's no way to say two types are identical modulo lifetimes - mem::transmute() can't even tell that they're the same size! Equally, I can't simply cheat and assume that T: 'static - as the cons cell example shows I'd like to be able to write container types and the like for types of any lifetime.
I did some research, and it sounds like this is an example of where higher-kinded-types are useful: Parameterizing over data structures (HKT?)
But of course, they aren't in Rust yet. So what's a reasonable alternative? I'm happy to use a small amount of unsafe code if needed.
Though I'd rather not drop the lifetimes from the design - not only are they efficient, but I think having pruned versions of original objects be tied by lifetime rules will help reduce errors in actually using these data-structures.