Struggling with higher-ranked-lifetimes

1

Hi everyone,

I'm struggling a little with higher-kinded lifetimes. I'm also struggling to reduce the problem to < 40 lines.

So, first of all: Gist and Playground link:
https://gist.github.com/skade/c61dfcf5ca7f0ab43865db289c0b349c

Here's the issue: I'm trying to write a trait that abstracts a query. It takes X + 'a and returns Y + 'b, where 'b: 'a. This is simple and the definition looks as follows:

trait Query<'a, 'b: 'a, X: 'b, Y: 'a> {
    fn execute(&self, f: X) -> Y;
}

As an example, such an implementation could look as follows:

#[derive(Default)]
struct ToBeQueried {
    inner: String
}

struct GetInner;

impl<'a, 'b: 'a> Query<'a, 'b, &'b ToBeQueried, &'a str> for GetInner {
    fn execute(&self, f: &'b ToBeQueried) -> &'a str {
        f.inner.as_ref()
    }
}

Now comes the catch: I want to wrap those queries in other structures, but these have no direct relationship to these lifetimes. Again, the definition is possible, using HRL:

struct QueryWrapper<X, Y, Q: for<'a,'b> Query<'a, 'b, X, Y>> {
    query: Q,
    phantom_x: PhantomData<X>,
    phantom_y: PhantomData<Y>
}

Implementations, too, especially of the query process:

impl<X, Y, Q: for<'a, 'b> Query<'a, 'b, X, Y>> QueryWrapper<X, Y, Q> {
    fn new(query: Q) -> Self {
        QueryWrapper { query: query, phantom_x: PhantomData, phantom_y: PhantomData }
    }
    
    fn query(&self, o: X) -> Y {
        self.query.execute(o)
    }
}

Now comes the catch: I can't find a way to construct it:

    let wrapper = QueryWrapper::new(GetInnerSlice);

error[E0277]: the trait bound `for<'a, 'b> GetInnerSlice: Query<'a, 'b, _, _>` is not satisfied
  --> <anon>:37:19
   |
37 |     let wrapper = QueryWrapper::new(GetInnerSlice);
   |                   ^^^^^^^^^^^^^^^^^ trait `for<'a, 'b> GetInnerSlice: Query<'a, 'b, _, _>` not satisfied
   |
   = help: the following implementations were found:
   = help:   <GetInnerSlice as Query<'a, 'b, &'b ToBeQueried, &'a str>>
   = note: required by `<QueryWrapper<X, Y, Q>>::new`

I would have either thought that implementing Query for <'a, 'b> would implement it for any <'a, 'b> (and thus fulfilling for <'a, 'b> or that impl for<'a, 'b: 'a> would be possible (which it isn't).

I'm, on the other hand, not very experienced in working in that corner of lifetimes and not sure if

a) what I'm doing is even sound and possible
b) there's just something I've overlooked.

FWIW: the problem came up when I tried to eliminate the need for the Wrapper to carry the lifetime bounds, so this would be the solution I'd have to settle for otherwise.

2

Here's the subtle unsoundness:

struct QueryWrapper<X, Y, Q: for<'a,'b> Query<'a, 'b, X, Y>>

This requires the same X (and Y) to work across all pairs of lifetimes. But this isn't possible if X or Y are tied to specific 'aor 'b lifetimes.

You might be able to relax the Query impl further to have separate lifetime parameters (with relations between them) and maybe it will work then.

1 Like
3

Thanks, that was a good dance. I played around a little and came up with this:

struct GetInnerSlice;

impl<'a, 'b: 'a> Query<'a, 'b, &'b ToBeQueried, &'a str> for GetInnerSlice {
    fn execute(&self, f: &'b ToBeQueried) -> &'a str {
        f.inner.as_ref()
    }
}

struct QueryWrapper<Q> {
    query: Q
}

impl<Q> QueryWrapper<Q> {
    fn new(query: Q) -> Self {
        QueryWrapper { query: query }
    }
}

trait ExecuteQuery<'a, 'b: 'a, X: 'b, Y: 'a, Q: Query<'a, 'b, X, Y>> {
    fn query(&self) -> &Q;

    fn execute_query(&self, o: X) -> Y {
        self.query().execute(o)
    }
}

impl<'a, 'b: 'a, X: 'b, Y: 'a, Q: Query<'a, 'b, X, Y>> ExecuteQuery<'a, 'b, X, Y, Q> for QueryWrapper<Q> {
    fn query(&self) -> &Q {
        &self.query
    }
}

I'm not sure I can integrate that back into the project I came from, but let's see :D.

Updated the gist.