Cannot find an error in the Visitor lifetime annotations

help
1

I wrote the following piece of code trying to implement universal Visitor trait parameterized by trait which is being visited. To me it looks like I placed all lifetime annotations correctly. My goal was to designate that visited item outlives the visitor. Compiler shows E0597 error for the final call. Could you please help me to understand where I made a mistake?

The code:

use std::fmt::Display;

trait Visitor<'a, 'b: 'a, T: 'b> {
    fn visit(&'a self, t: T);
}

struct Printer { }

impl<'a, 'b: 'a, T: Display + 'b> Visitor<'a, 'b, T> for Printer {
    fn visit(&'a self, t: T) {
        println!("{}", t);
    }
}

trait Visitable<'a, 'b: 'a, T: 'b> {
    fn accept(&'b self, visitor: &'a dyn Visitor<'a, 'b, T>);
}

#[derive(Debug)]
struct ItemA<T> {
    v: T,
}

impl<T: Display> Display for ItemA<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        write!(f, "ItemA.v = {}", self.v)
    }
}

impl<'a, 'b: 'a, T: Display> Visitable<'a, 'b, &'b dyn Display> for ItemA<T> {
    fn accept(&'b self, visitor: &'a dyn Visitor<'a, 'b, &'b dyn Display>) {
        visitor.visit(self as &dyn Display);
    }
}

fn print_items<'a, 'b: 'a, T: Display + 'b>(
        vec: &'b Vec<Box<dyn Visitable<'a, 'b, &'b dyn Display>>>,
        visitor: &'a dyn Visitor<'a, 'b, &'b dyn Display>) {
    for v in vec {
        v.accept(visitor);
    }
}

fn main() {
    let vec: Vec<Box<dyn Visitable<&dyn Display>>> = vec![Box::new(ItemA{ v: 3 })];
    let printer = Printer{};
    print_items::<&dyn Display>(&vec, &printer);
}

Compilation fails with E0597:

   Compiling a v0.1.0 (/home/vital/projects/trueagi/a)
error[E0597]: `vec` does not live long enough
  --> src/main.rs:47:33
   |
47 |     print_items::<&dyn Display>(&vec, &printer);
   |                                 ^^^^ borrowed value does not live long enough
48 | }
   | -
   | |
   | `vec` dropped here while still borrowed
   | borrow might be used here, when `vec` is dropped and runs the `Drop` code for type `Vec`

error[E0597]: `printer` does not live long enough
  --> src/main.rs:47:39
   |
47 |     print_items::<&dyn Display>(&vec, &printer);
   |                                       ^^^^^^^^ borrowed value does not live long enough
48 | }
   | -
   | |
   | `printer` dropped here while still borrowed
   | borrow might be used here, when `vec` is dropped and runs the `Drop` code for type `Vec`
   |
   = note: values in a scope are dropped in the opposite order they are defined

For more information about this error, try `rustc --explain E0597`.
error: could not compile `a` due to 2 previous errors
2

Well you are dealing with a type of the form &'a T<'a> where the same lifetime is repeated both on the reference and also annotated on the type itself. This usually doesn't work because:

  1. The lifetime on the reference is an upper bound on where the target can exist.
  2. The lifetime on annotated on the type is a lower bound on where the target can exist.

So basically you've introduced both constraints 'a ≥ 'vec and 'a ≤ 'vec, which forces them to be equal. But then, the lifetime 'a is the duration in which the call borrows the vector immutably, and if it is equal to the duration in which the vector exists, then the immutable borrow extends until after the vector's destructor. However, running the vector's destructor requires mutable access to it, and therefore can't overlap with the immutable borrow. Thus you get an error.

It is difficult to give specific advice on how to solve this besides the recommendation that you simplify your code. You don't need this many lifetimes — I don't know exactly what you're trying to do, but I suspect you can it without any lifetimes whatsoever.

2 Likes
3

Thank you very much for explanation. It makes a perfect sense. For sure I added too many lifetime annotations here, but without at least some of them code doesn't compile.

I started from the code without lifetimes:

impl<T: Display> Visitable<&dyn Display> for ItemA<T> {
    fn accept(&self, visitor: &dyn Visitor<&dyn Display>) {
        visitor.visit(self as &dyn Display);
    }
}

But compiler complains &self and <&dyn Display> type parameter have different (anonymous) lifetimes so it cannot infer lifetime of the self as &dyn Display reference in the Visitable implementation (which sounds reasonable).

If I designate self outlives &dyn Display (which is true because dyn Display is a casted self) through the impl lifetime parameter, then compiler says that accept method is not compatible with the trait. This is also true because in the trait lifetimes of the &self and Visitor are not linked. So I need adding at least single lifetime parameter to Visitable:

trait Visitable<'b, T> {
    fn accept(&'b self, visitor: &dyn Visitor<T>);
}

impl<'a, 'b: 'a, T: Display> Visitable<'b, &'a dyn Display> for ItemA<T> {
    fn accept(&'b self, visitor: &dyn Visitor<&'a dyn Display>) {
        visitor.visit(self as &dyn Display);
    }
}

Now print_items requires lifetime parameters because accept requires Visitable reference outlives Visitor reference:

fn print_items<'a, 'b: 'a, T: Display>(
        vec: &'b Vec<Box<dyn Visitable<'b, T>>>,
        visitor: &'a dyn Visitor<T>) {
    for v in vec {
        v.accept(visitor);
    }
}

This variant has lower number of lifetime annotations than previous version, but it doesn't compile with E0597:

   Compiling a v0.1.0 (/home/vital/projects/trueagi/a)
error[E0597]: `vec` does not live long enough
  --> src/main.rs:47:33
   |
47 |     print_items::<&dyn Display>(&vec, &printer);
   |                                 ^^^^ borrowed value does not live long enough
48 | }
   | -
   | |
   | `vec` dropped here while still borrowed
   | borrow might be used here, when `vec` is dropped and runs the `Drop` code for type `Vec`

For more information about this error, try `rustc --explain E0597`.

I added full code to the playground.

4

The original goal was to check whether it is possible in Rust to implement a visitor pattern using upcasting from a sum of traits to the specific trait which is known to Visitor. As far as I understand even if code I wrote can be compiled this solution doesn't work in stable Rust because trait upcasting is experimental. But now I would like to understand lifetimes better and find out why this code cannot be compiled.

For example there is some collection (Vec<T> for instance), traits A and B and structs C and D. Both C and D implement both A and B. Thus one could instantiate Vec<A + B> (in pseudo code) then put instances of C or D into the vector.

Is it is possible to implement generic traits Visitor<T> and Visitable<T> such as if C and D implement Visitable<A> and struct E implements Visitor<A> then we can write a function to visit vector items by instance of E.

5

Well, you definitely don't want the 'b lifetime here. Start by removing it.

My next comment would be that you're using dyn Trait too much. This looks wrong to me:

Like, &dyn Display is a single specific type separate from, say, i32 or &i32. If you wanted it to be able to visit anything that implements Display, then you should be using a generic parameter rather than a trait object.

And in general, having a dyn Trait inside a dyn Trait is also just a red flag.

1 Like
6

Another thing with this one is that dyn Visitor<T> is short-hand for dyn Visitor<T> + 'static, which I'm not sure is what you intended. Consider generics here too?

trait Visitable<T> {
    fn accept<V: Visitor<T>>(&self, visitor: &V);
}

The hidden 'static is likely why you had trouble with the self as &dyn Display stuff.

1 Like
7

I started by pulling out all of the lifetimes and squinting at the impl Visitable<&dyn Display> for ItemA<T> until I decided the core ideas are:

// I can visit Ts
trait Visitor<T> {
    fn visit(&self, t: T);
}

// I can make visitors of T visit myself
// Implication: I can become T
trait Visitable<T> {
    fn accept(&self, visitor: &dyn Visitor<T>);
}

And within that context, you may be able to intuit where a problem comes in: ItemA cannot become a &dyn anything. But &ItemA can. There's a disconnect here between the reference type in the header of the implementation, and the borrow of &self in the higher-ranked method accept. We need those types to be "at the same level", not split up like this; we need to know we can always turn the implementer of Visitable<T> into T, across the entire implementation.

One way to try to get them on the same level is to add a lifetime to the trait, and add that lifetime to the &self parameter, so that the method is no longer higher-ranked over the implementation. But as you've found, this often just leads to more suggestions to add more lifetimes so that the compiler can make a little more progress (i.e. one more function checks). And then the end result is often a Gordian knot that may not be satisfiable by any actual (or practical) program -- like a function you can't call with a borrow of a Vec because the borrow has to outlive the Vec.

Another way is to get them at the same level is to implement for &ItemA instead, as that can transform into a &dyn in the right circumstances. This would also have a minimal impact on your trait APIs. This is the result, which runs:

impl<'d, T: Display> Visitable<&'d dyn Display> for &'d ItemA<T> {
    fn accept(&self, visitor: &dyn Visitor<&'d dyn Display>) {
        visitor.visit(*self as &'d dyn Display)
    }
}

However, it's not ideal. For one, this means that accept is taking a &&ItemA, which is pretty awkward. For another, it means that in main, you're boxing up references, which probably isn't what you want. You seem to be aiming for an owned solution.

Instead, we can keep the implementation for ItemA if we allow the T in Visitable<T> to be dyn Display instead of &dyn Display, as ItemA can become a dyn Display. This means we need T: ?Sized in the traits, and that visit should take a &T and not a T. After those changes, the implementation becomes:

// n.b. U is Sized here as ItemA<U> stores a U
impl<'t, U: Display + 't> Visitable<dyn Display + 't> for ItemA<U> {
    fn accept(&self, visitor: &dyn Visitor<dyn Display + 't>) {
        visitor.visit(self as &dyn Display)
    }
}

This also runs, and is much cleaner. You don't need to box up references in your main any more, either.

So, the exploration can be made to work. Is it practical? I'm less sure about that; the nested dyns probably mean you have to decide to type erase everything pretty much as they're created. But maybe there's a use case.

3 Likes
8

Thank you @alice and @quinedot for your answers. Finally the second solution which were suggested by @quinedot is exactly what I was trying to achieve.

Ironically I started from the visit(&self, t: &T) declaration as it was intuitive :slight_smile: But after a while I looked at self as &dyn Display inside implementation of accept and thought I can just declare visit as visit(&self, t: T). Even after reading answer I still cannot completely explain why this doesn't work, but probably I need to think about it further.

The second hard step to me was assigning lifetimes in implementation of Visitable for ItemA properly. Without lifetimes:

impl<T: Display> Visitable<dyn Display> for ItemA<T> {
    fn accept(&self, visitor: &dyn Visitor<dyn Display>) {
        visitor.visit(self as &dyn Display);
    }
}

Compiler shows E0310:

error[E0310]: the parameter type `T` may not live long enough
  --> src/main.rs:38:23
   |
36 | impl<T: Display> Visitable<dyn Display> for ItemA<T> {
   |      -- help: consider adding an explicit lifetime bound...: `T: 'static +`
37 |     fn accept(&self, visitor: &dyn Visitor<dyn Display>) {
38 |         visitor.visit(self as &dyn Display);
   |                       ^^^^ ...so that the type `ItemA<T>` will meet its required lifetime bounds

For more information about this error, try `rustc --explain E0310`.

Which is probably because dyn Display contains &Self so the compiler should be sure the &Self lives long enough. The only possibly non-static thing here is T parameter of the ItemA<T> so it requires declaring 't to designate that dyn Display has the same lifetime as T.

9

Alice alluded to this before; basically

  • dyn Trait always has an attached "lifetime of trait applicability" (though it's often elided)
  • Outside of any lifetime context, the default is dyn Trait + 'static

So this

impl<T: Display> Visitable<dyn Display> for ItemA<T> {

is short for

impl<T: Display> Visitable<dyn Display + 'static> for ItemA<T> {

And as you said, the T may not be 'static if you don't constrain it to be so; if it's not 'static, Item<T>'s maximum lifetime of applicability would be shorter too, and the cast invalid. Hence the compiler hint. And as it happens, your implementation and main example will run fine with that bound; it might be good enough for your use case generally.

However, when the compiler suggests tightening bounds with "consider T: 'static", it can often be better to figure out where the 'static requirement is coming from and to loosen that bound instead.

And that's exactly what the T: 't and dyn Display + 't adjustments do.

10

I tried this but my understanding this requires where Self: Sized and my goal requires calling accept on a trait rather than on a type. So I believe dyn Trait<dyn Trait> is inevitable here.

11

Thanks, yes, it was not clear to me why dyn Trait is considered dyn Trait + 'static, but as trait object is a fat pointer it sounds like a safe default lifetime which can be overridden manually if needed.

12

What do you mean by that? You can't call a method "on a trait"; you can call a trait method on a known type (and that known, concrete type can be dyn Trait). So dyn Trait<dyn Trait> does in fact seem like an anti-pattern; I haven't ever seen a case where this kind of construct was required for implementing a visitor.

If you want to learn how to implement visitors idiomatically, I recommend you to read the definition of serde::de::Visitor.

13

Yes, I typed it incorrectly, I mean not a trait but a trait object. Thanks for the reference to the serde, I am definitely going to look at it.

14

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.