Anonymous lifetimes in a trait bound

help
1

Hi everyone, I'm not sure how to describe the issue I'm encountering, so I'll just show a simplified example to hopefully make it more clear (playground link):

This is my code:

trait Visit<'a> {
    fn visit(slice: &'a [u8]) -> Self;
    fn min_size() -> usize;
    fn consumed(&self) -> usize;
}

struct Num<'a>(&'a [u8]);

impl<'a> Visit<'a> for Num<'a> {
    fn visit(slice: &'a [u8]) -> Self {
        Num(&slice[..4])
    }
    fn min_size() -> usize {
        4
    }
    fn consumed(&self) -> usize {
        4
    }
}

struct Visitor {
    buffer: Vec<u8>,
    cursor: usize,
}

impl Visitor {
    fn advance<'a, 's: 'a, V: Visit<'a>>(&'s mut self) -> bool {
        if self.buffer.len() - self.cursor < V::min_size() {
            false
        } else {
            let value = V::visit(&self.buffer[self.cursor..]);
            self.cursor += value.consumed();

            true
        }
    }

    fn consume_all<'a, V: Visit<'a>>(&mut self) {
        while self.advance::<V>() {}
    }
}

And this is the error I'm getting:

error: lifetime may not live long enough
  --> src/main.rs:39:15
   |
38 |     fn consume_all<'a, V: Visit<'a>>(&mut self) {
   |                    --                - let's call the lifetime of this reference `'1`
   |                    |
   |                    lifetime `'a` defined here
39 |         while self.advance::<V>() {}
   |               ^^^^^^^^^^^^^^^^^^^ argument requires that `'1` must outlive `'a`

error[E0499]: cannot borrow `*self` as mutable more than once at a time
  --> src/main.rs:39:15
   |
38 |     fn consume_all<'a, V: Visit<'a>>(&mut self) {
   |                    -- lifetime `'a` defined here
39 |         while self.advance::<V>() {}
   |               ^^^^^^^^^^^^^^^^^^^
   |               |
   |               `*self` was mutably borrowed here in the previous iteration of the loop
   |               argument requires that `*self` is borrowed for `'a`

I think understand why this error happens, but my problem is that I can't figure out a way to remove/simplify the lifetimes. Since the value variable clearly doesn't outlive the advance function I thought about specifying an anonymous lifetime to the Visit trait bound, but the compiler doesn't allow me to do it. And since I can't do that I have to explicitly name that lifetime, but this is where it all spirals out of control.

I tried defining a separate lifetime 's to make it more clear that 'a doesn't live all that long, but that also didn't work. And as I understand it there's no way to define a lifetime which lives "shorter" than the function (which is what I'm interested into here I think).

From what I'm reading online I'm guessing HRTB might be helpful in this case, but again I can't figure out a way to use them here.

Sorry for the very vague question, I can't really explain this any better. If you have any tips or ideas I'd really appreciate them!

Thanks!
Alekos

2

You are super close.

Try this: Rust Playground

Here's an explanation of what's going on: Higher-Rank Trait Bounds - The Rustonomicon

3

The way that "shorter than the function body" is specified is generally by a HRTB, yes. There's no way for callers of a function to name a lifetime that short.

Tacking that onto your current trait is a bit messy, as Rust doesn't have generic type constructors. Instead you need something GAT-like to emulate them. A direct modification might look like:

// A way to indirectly name the trait implementer
trait VisitType<'a> { type Visitor: Visit<'a>; }

// A convenience trait for the HRTB, implemented whenever possible
trait VisitAny: for<'any> VisitType<'any> {}
impl<T: ?Sized> VisitAny for T where for<'any> T: VisitType<'any> {}

// A convience type alias
type VisitorOf<'a, V> = <V as VisitType<'a>>::Visitor;

// Then you need a single type that can represent all `Num<'_>`
struct NumRep;
impl<T: ?Sized> VisitAny for T where for<'any> T: VisitType<'any> {}

    fn advance<V: VisitAny>(&mut self) -> bool {
        if self.buffer.len() - self.cursor < VisitorOf::<'_, V>::min_size() {
            false
        } else {
            let value = VisitorOf::<'_, V>::visit(&self.buffer[self.cursor..]);
            self.cursor += value.consumed();

            true
        }
    }

    fn consume_all<V: VisitAny>(&mut self) {
        while self.advance::<V>() {}
    }

Playground.

Alternatively, you could modify your trait to take this type-constructor consideration into more direct account. You do lose the self receiver on the constructed type.

You can get it back with another trait.

Edit: Side note, it's too bad custom DSTs aren't more ergonomic, as you can leverage references to be your type constructor that way.

4

Num<'_> can't meet that HRTB because it only implements Visit<'_> for a single lifetime.

5

Thank you so much for the explanation!

I think I understand most of the code, but it's still not very clear to me why the extra VisitType trait is required: in particular, I don't understand how you can make a trait that's only implemented for a single lifetime (Visit) work with an HRTB just because it goes through the indirection of an associated type (?)

A follow-up question: is there an alternative way to define the Visit trait so that I can directly implement it "for any lifetime", in order to avoid the "it's not general enough" error?

Thanks again!

6

So, let's back up a minute to make sure we're on the same page. Types that differ only in lifetime are still different types (even though there's a lot that goes on which makes it seem like they might be the same type). And a lifetime-parameterized type without a lifetime isn't actually a type -- it's a type constructor (that needs to be supplied with a lifetime).

When being formal then, &MyType is not a type. It's a type constructor.

For your trait to be practical, you need to be able to construct instances of visitors from an arbitrary lifetime -- you need a type constructor for visitors. If Rust were designed differently and had generic type constructors, perhaps you could do something like

trait Visit<TC<*>> {
    fn visit(slice: &[u8]) -> TC<'_>;
}

// or maybe instead
fn advance<TC<*>>(...)
where
    for<'any> TC<'any>: Visit<'any>

But it doesn't have generic type constructors, so you need some otherway to express this bound.

If you were using just references, like in my DST example, the pattern of the construction trait you want looks like

impl Visit for Num {
    fn visit(slice: &[u8]) -> &Self {
    //                        ^

and everyone uses the same type constructor (&).

But you want people to be able to supply their own type constructor, like if you could do something like this:

impl Visit for Num {
    fn visit(slice: &[u8]) -> Self<'_> {

And there is a way to do this in one trait on beta -- it's Generic Associated Types (GATs), which will reach stable in November, barring any complications. [1] Another name for GATs is ATCs: Associated Type Constructors. Using GATs, you could write it like this:

trait Visit {
    // The `Consumed` bound is for methods on the visitor
    type Visitor<'a>: Consumed;
    fn visit(slice: &[u8]) -> Self::Visitor<'_>;

With this approach, a single type can define a type constructor that works for all lifetimes.

But without GATs, we need another approach. And as it turns out, you can emulate lifetime GATs with a lifetime-carrying trait that has a non-generic associated type:

// Replaces Visit::Visitor<'a>
trait VisitOnce<'a> {
    type Visitor: Consumed;
    fn visit(slice: &'a [u8]) -> Self::Visitor;
}

trait Visit: for<'any> VisitOnce<'any> {

Here, we've moved the lifetime off of the associated type and put it on a separate trait. I pulled the method along with it, but you could also spell it like so:[2]

trait VisitOnce<'a> {
    type Visitor: Consumed;
}

trait Visit: for<'any> VisitOnce<'any> {
    fn visit(slice: &[u8]) -> <Self as VisitOnce<'_>>::Visitor;

Now, the lifetime carrying trait is our type constructor. And we associate it with the main trait by means of a supertrait bound that requies it be implemented for all lifetimes.

So hopefully that's more clear -- the indirection is because without GATs, that's how you let implementors of a trait define a type constructor you can make use of. You need a type constructor that can be named in some way so you can have the HRTB.

  1. It's still a bit rough around the edges for some applications. ↩︎

  2. The main benefit of not doing this is if you have use cases for both the higher-ranked, need-all-lifetimes trait and the single-lifetime, might-be-a-one-off trait; this comes up with non-static closures sometimes for example. ↩︎

7

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.