Trait objects, limetimes, and the expression problem: implementing a function predicate trait

[slightknack]

Background

I'm implementing a distributed consensus protocol, and a common operation is to use a back-track-able predicate to construct a set or the like. Below is the specific error I'm running into, however, I believe this class of problems is something more general than just this specific case.

The Issue

So I'm bumping into an interesting lifetimes issue. Let's see here...
First things first, I have a Value, which is a non-static trait that is not a trait object. Here's the definition:

pub trait Value: Eq + Ord + fmt::Debug {
    fn combine(this: Self, that: Self, slot_id: SlotId) -> Self;
}

Next up, I have another trait, Predicate, which has one member function. It takes a generic Message<T> (a struct that contains a Value, among other things), and optionally returns a new predicate:

pub trait Predicate<T: Value>: fmt::Debug {
    fn test(self, message: &Message<T>) -> Option<Box<dyn Predicate<T>>>;
}

Last but not least, I have FnPredicate, which applies a function as a predicate, and returns itself if that function returns true:

pub struct FnPredicate<T: Value>(Box<fn(&Message<T>) -> bool>);

impl<T: Value> Predicate<T> for FnPredicate<T> {
    fn test(self, message: &Message<T>) -> Option<Box<dyn Predicate<T>>> {
        return if (self.0)(message) {
            Some(Box::new(self))
        } else {
            None
        }
    }
}

Right now, I'm currently getting a lifetime error when I box self in Some(Box::new(self)):

the parameter type `T` may not live long enough
...so that the type `FnPredicate<T>` will meet its required lifetime bounds

Any tips? I'm getting a serious code-smell right off the bat, but I haven't honestly explored the solution space that much. One more quick thing - rustc gives me this help message:

help: consider adding an explicit lifetime bound...: `T: 'static +`

But value is non-static, so this would result in further issues down the road. Thoughts y'all? Thanks in advance!

Generalities

I believe these... class of problems are something more general than just this specific case.

Whenever I try to use traits to emulate 'open' enums - i.e. sets of related types that implement the same interface - I usually run into what seems like a wall of errors no matter which direction I go. In the past, I've resolved this issue by switching to 'closed' enums, turning traits and their implementations into enums.

This seems related to the expression problem. Ignoring the example above, what is the idiomatic way to resolve the expression problem in Rust and what general patterns exist when working with traits and trait objects?

I feel like I have a solid grasp on traits when creating basic interfaces, but anything self-referential or dyn-related quickly gets shuts down. I understand the why, just not what general solutions exist.

Thanks!

[alice]

Can you include a playground with all the code together?

[slightknack]

Sure thing! Rust Playground

[drewkett]

As far as the error is concerned, Box<dyn SomeTrait> has an implicit 'static lifetime. So it’s really Box<dyn SomeTrait + 'static> if you don’t specify a lifetime. In your case you need to change the method definition to give the trait object a lifetime, such as

fn test<'s>(self, message: &Message<T>) -> Option<Box<dyn Predicate<T> + 's>> where Self:'s

Note the extra constraint to constrain self to stay alive for the lifetime as well.

playground

[juggle-tux]

You beat me to the answer however i was coming up witch where T: 's and are a bit surprised that where Self: 's works too.

[slightknack]

Oh, I see! Thanks for the answer! That really helped

One more thing:

I'm implementing a distributed consensus protocol, and a common operation is to use a back-track-able predicate to construct a set or the like.

In the implementation of the back-tracking code, which calls Predicate::test, I get a similar lifetime bounds error. The compiler is assuming a 'static lifetime again. The implementation is a bit more involved, so I'll try to narrow it down to a MVP.

Edit: Never mind, fixed.

[Yandros]

Yeah, performing dyn-safe -> Self-like methods (be it when implementing a dyn-safe Clone, or in this instance, a dyn-safe "optional identity", using the <'slf> … -> Box<dyn 'slf + …> where Self : 'slf is actually the correct bound, most of the time.

---

Regarding that snippet, @slightknack, if you are gonna be passing along a Box<dyn Predicate> through multiple test calls, then your current implementation involves unnecessary Boxing; if you are to box the input, then you may as well require it be Boxed:

- fn test (self:     Self , …)
+ fn test (self: Box<Self>, …)
  {
    if …
-       Some(Box::new(self))
+       Some(         self )

• Also, Box<fn …> involves unnecessary Boxing too. You can think of fn(…) -> _, conceptually, as of a &'static dyn Sync + Fn(…) -> _ (in practice it is optimized to be a slim pointer and use one less level of indirection). And since you wouldn't write Box<&'static …, you shouldn't write Box<fn… either:

  • Either your use fn… directly (no Boxing), for when you don't need to capture any state),

  • Or you use Box<dyn Fn….

• Playground

---

Finally, the test / pipe pattern looks a bit original from the outside: rather than taking and yielding ownership, it is common to, instead, use borrowing (although your design may be answering constraints that did not appear on this thread, in which case feel free to disregard this comment):

fn test (self: &'_ mut Self, message: &'_ Message<T>)
  -> bool

[slightknack]

Thanks for the explanation about boxing - I've fixed that and now everything's working as intended .

About the test / pipe pattern: because the code may backtrack, I can't pass in a mutable reference, because I may need to discard any changes made to the predicate as I traverse the set.

[drewkett]

The difference between putting the bound on Self versus T is that putting it on Self will ensure the whole Self object is bound by the lifetime requirement where as the constraint on T only applies the bound to T. Where this could come into play is if you implement the trait on an object with other lifetimes that the trait doesn’t know about. In that case, all of self (including any other lifetime that is tied to self) still needs to meet the lifetime requirement. There’s probably a workaround in that case for where you can still make an implementation work with your trait definition but putting the lifetime constraint directly on Self is both simpler and more clear.