Associated types and lifetime variance problem

help
1

I have a trait, Relation (a relational algebra table) that is modeled a bit after how Iterator works, in that its methods generally consume self, and there are usually distinct implementations for T and &T.

Because the main operations are consuming, I need a way to let users run multiple queries against the same table. To do this, I'd like to provide access to the &T implementation (if it exists) via a method that doesn't consume the original. When trying to implement this, I could only manage to make a lifetime-invariant trait, which basically limits its usefulness to 'static types.

An alternative that I considered is to require both T and &T implementations, and then provide a blanket &&T one, but I ran into a similar issue: I can't require for<'a> &'a T: ... because it restricts T to be static-- as far as I can tell, there's no way to restrict the HRTB to only those lifetimes that T is valid for.

The goal here is to be able to call a function that returns impl Viewable<...>, and be able to generate views that access the data in that viewable without cloning the whole thing. Can anyone else see a way to make this happen?

pub trait Relation {}

// Doesn't need to preserve old data
impl<R> Relation for Vec<R> {}

// Same results as above, but may need to make copies
impl<'view, R:'view> Relation for &'view [R] {}

// ================================

// Semantically, can support a view with lifetime exactly 'view
// Would prefer any lifetime contained in 'view, is that possible?
pub trait Viewable<'view>: Relation {
    type View: Relation + 'view;
    fn view<'s:'view>(&'s self)->Self::View;
}

// Vec can provide references to its records without destroying them
impl<'view, R:'view> Viewable<'view> for Vec<R> {
    type View= &'view [R];
    fn view<'s:'view>(&'s self)->Self::View { &self[..] }
}

// TODO: Implement Viewable for &[R] where Self::View=Self

// This works, but I'd prefer to return impl Viewable<'static> if possible
pub fn f_static()->impl for<'a> Viewable<'a> {
    vec![42]
}

// This is a better proxy for my use case.  It compiles, but can't be used.
pub fn f_ref<'x>(x:&'x usize)->impl Viewable<'x> {
    vec![x]
}

pub fn f_view() {
    {
        let rel = f_static();
        rel.view();
    }
    
    {
        let x:usize = 42;
        let rel = f_ref(&x);
        rel.view();  // Commenting out this line clears the compile error
    }
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0597]: `rel` does not live long enough
  --> src/lib.rs:45:9
   |
45 |         rel.view();  // Commenting out this line clears the compile error
   |         ^^^ borrowed value does not live long enough
46 |     }
   |     -
   |     |
   |     `rel` dropped here while still borrowed
   |     borrow might be used here, when `rel` is dropped and runs the destructor for type `impl Viewable<'_>`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0597`.
error: could not compile `playground`.

To learn more, run the command again with --verbose.

Warnings

No main function was detected, so your code was compiled
but not run. If you’d like to execute your code, please
add a main function.
2

You're looking at more or less the same problem as why Rust can't have an Iterable trait. GATs (generic associated types) will fix this (read Associated type constructors, part 1: basic concepts and introduction for a much more detailed explanation; note that "ATC" has mostly disappeared from the lexicon in favor of "GAT" but they mean the same thing).

You do, however, have one advantage over Iterable in this respect: all your View types (in the example) are actually references. That means you can actually just remove the 'view lifetime from Viewable entirely and put the reference in the return type:

pub trait Viewable: Relation {
    type View: ?Sized + Relation;
    fn view<'s>(&'s self)->&'s Self::View;
}

Why did I put ?Sized there? Well, if calling .view() on a Vec<R> is going to return a &'something [R], obviously Vec<R>::View has to be [R] (and [R] is unsized):

impl<R> Viewable for Vec<R> {
    type View = [R];
    fn view<'s>(&'s self)->&'s [R] { &self }
}

That, of course, means we also have to implement Relation for [R] as well, which is easily done...

impl<R> Relation for [R] {}

Now when it comes to implementing Viewable for &'a [R], you can do it (and you may want to) but it's just as easy to (also) implement it for plain [R]:

impl<R> Viewable for [R] {
    type View = [R];
    fn view<'s>(&'s self)->&'s [R] { &self }
}

f_static and f_ref now basically just work once you remove the lifetime from Viewable (f_ref just requires + 'x instead of <'x>):

pub fn f_static()->impl Viewable {
    vec![42]
}

pub fn f_ref<'x>(x:&'x usize)->impl Viewable + 'x {
    vec![x]
}

f_view doesn't need any changes; it just works (playground).

This approach will not work if any of your View types are not plain & references, because there's no way to get the lifetime "into" the associated type (cf. the blog post I linked earlier). So if you need the View to be a non-reference, you might be out of luck. The other option I'm aware of, using HRTBs... well, I couldn't get it to work, but I'm not yet sure it's impossible.

1 Like
3

Thanks for the detailed explanation. As usual, details I thought weren’t important get in the way of your proposed solutions :confused:. I suspect this approach isn’t going to work without GATs; unfortunate, but I’ve been dancing on that boundary for this entire project.

I’ll probably get around the lifetime issue by leaning on clone, and requiring lightweight views to come from Arc/Rc.

The problem with ?Sized + Relation is that all of the useful Relation methods take an owned self parameter instead of a reference &self. There’s a couple of reasons for this:

  • It allows a Vec<R> implementation to make optimizations like in-place sorting and using into_iter, while the &[R] implementation needs to do a lot more cloning and heap allocation to preserve its referent.
  • The table header is stored as an associated type in the Relation trait (as an HList of field newtypes), so almost every operation produces a differently typed result than its input. I’m considering doing the same thing for the current sort order.

I am using a lot of thin adapter structs with PhantomData to do GAT-like things: it forces every implementation to use the same type constructor, but that can pull whatever associated information it needs to configure behavior from the Relation trait of whatever it’s adapting; maybe I can make that approach work here.

The limitation here is one that might be fixable in the compiler without breaking too many things (said having never looked at the internals). The clause for<'a> &'a T: SomeTrait fails to compile unless the compiler can prove that T: for<'a> 'a (aka. T: 'static).

This feels overly conservative to me, because &'a T can provably never be constructed when 'a: T. As they can never exist, it seems just as correct to say that they always implement SomeTrait as to say that they don’t, by analogy to the ! type.

4

That's not necessarily a showstopper for View: ?Sized. Iterator also has a bunch of self-taking methods but because they all have where Self: Sized bounds, things that implement Iterator don't have to be Sized themselves. Otherwise you wouldn't be able to use dyn Iterator at all.

I mocked up something that demonstrates some tricks you could use. Maybe you can think of some others, maybe it won't work for you at all. It's easier with Iterator because that trait exposes an interface that lets you implement it generically for all references to things that implement Iterator already -- if Relation is also like that, you can avoid specifying the View types for f_static and f_ref.

2 Likes
5

Thanks; there’s a lot of good examples in that gist. I think at this point, it’s primarily a matter of trying a bunch of these in the real codebase until I find something I can live with.

6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.