Higher-kinded-lifetime bounds workaround?


#1

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.


#2

Alright let’s try and work this thing out. I’m guessing you’ve got a functional background so I’ll try keep up :smile:

Based on what you’ve shared so far, I think you could get away with not having HKT and rely on plain old generics for the result of the pruning.

So what I’ve got is a Prune trait and implementation for Maybe that looks a bit like this:

trait Prune<'pr, T> {
    fn prune(&'pr self) -> T;
}

impl<'p, 'pr, T> Prune<'pr, Maybe<'pr, T>> for Maybe<'p, T>
    where 'p: 'pr,
          T: for<'tpr> Prune<'tpr, T> + 'p
{
    fn prune(&'pr self) -> Maybe<'pr, T> {
        match *self {
            Maybe::Avail(ref t) => Maybe::Ref(&self, RefCell::new(t.prune())),
            _ => unimplemented!(), // Do prune stuff
        }
    }
}

Where p is the original lifetime of the Maybe, pr is the lifetime of the pruned reference and tpr is the lifetime of the data wrapped by Maybe. Here’s a playground where I’ve substituted some of those types in your OP.

I do use higher ranked trait bounds (that T: for<'tpr> bound) so we can bridge from T: 'p to T: 'pr when pruning.

I haven’t worked the Cons type into this, but am wondering what a complete structure might look like. Eventually that T is going to need to terminate. Are the leaf nodes all going to be either Maybe::Missing or Maybe::Avail(Cons::Nil)?

I guess one thing I don’t understand is why Maybe::Ref needs a cell back to the original data? Is that not captured by a ref back to Maybe::Avail?

Anyways, maybe there’s some inspiration in there, but any more details on what your data looks like would help :slight_smile:

EDIT: Actually if you’re not going to have lots of nested calls to prune you can simplify the implementation a lot:

impl<'p, 'pr, T> Prune<'pr, Maybe<'pr, T>> for Maybe<'p, T> 
    where T: Prune<'pr, T>
{
    fn prune(&'pr self) -> Maybe<'pr, T> {
        match *self {
            Maybe::Avail(ref t) => Maybe::Ref(&self, RefCell::new(t.prune())),
            _ => unimplemented!()
        }
    }
}

#3

Thanks!

Not only did your solution work… it made me realize I’d misunderstood the problem. The real cause of my problem was a misunderstanding of what lifetimes can guarantee. Simple example:

struct Foo {
    bar: Rc<(something)>,
}

If I have a function that takes a &Foo value, it obviously can’t return a reference to anything within that value unless the thing it returns has the same lifetime as Foo. My mistake was thinking that the solution was to try to have a second lifetime for the data within Foo, but that’s unreasonable: how can the borrow checker know the next lifetime recursively? Secondly, that defeats the other purpose of lifetimes for my application: I want to make it hard to accidentally mix up pruned and original data, so you should have to do something explicit to go from one to the other.

I’ll be able to publish the actual code in a few weeks, but long story short, the correct solution was to have both borrowed and owned methods for the prune trait:

pub trait Prune<'a> : Commit + Clone {
    /// Convert into a pruned instance
    ///
    /// The pruned data is owned by the instance, and can be unpruned.
    fn into_pruned(self) -> Self;

    /// Create an unprunable proxy that borrows self
    ///
    /// The proxy will contain references to the original, and thus has the same lifetime.
    fn prune(&'a self) -> Self;
}

…define Maybe as:

pub enum MaybePruned<'a, T: 'a + Prune<'a>> {
    Maybe(MaybeMissing<T>),

    /// Owned, lazily unprunable value
    Pruned(Unprunable<T, T>),

    /// Borrowed unprunable
    Ref {
        parent: &'a MaybePruned<'a, T>,
        cell: LazyCell<T>,
    }
}

…and then have the unprune() function simply make sure that the lifetime of the upstream reference was reflected in the value it returned:

impl<'a, T> Unprune for MaybePruned<'a, T>
    where T: Prune<'a>
{
    type Unpruned = T;
    fn unprune(&self) -> Avail<&T> {
        match *self {
            MaybePruned::Maybe(ref maybe)       => maybe.unprune(),
            MaybePruned::Pruned(ref unprunable) => unprunable.unprune(),
            MaybePruned::Ref{parent, ref cell} => {
                if let Some(pruned_orig) = cell.get() {
                    Ok(pruned_orig)
                } else {
                    // This is a bit tricky...
                    //  
                    // First of all, ask our parent for a reference to the unpruned value. Note the
                    // lifetime: it's the same as the reference to the parent.
                    let upstream_ref: &'a T = parent.unprune()?;

                    // Now take that reference and prune it _as a reference_. This separates our
                    // pruning state from the parent's pruning state, while still maintaining the
                    // connection to the parent so that subsequent unpruning also unprunes the
                    // parent.
                    let our_pruned_orig = Prune::prune(upstream_ref);

                    cell.set(our_pruned_orig).ok().is_some();
                    Ok(cell.get().unwrap())
                }   
            }   
        }   
    }   
}

You know, Rust is the RMS of programming languages: the borrow checker has highly unpopular opinions about your code that inevitably turn out to be 100% correct.


TWiR quote of the week
#4

Excellent :slight_smile: I’m glad to hear you worked it out, without too much boilerplate.