Unconstrained lifetime parameter while propagating trait lifetimes

[lut_99]

Hello!

I'm trying to make a combinator parser library, very much inspired by nom. I want to add the notion of combinators being able to express what they expect from the input, ideally by returning some formatter that builds this string later (as combinators tend to do a lot of trial-and-error, so this error information needs to be very cheaply available until it is presented to the user). But I'm running into some lifetime issues.

In particular, I'm working with nom's tag() in the back of my mind, where the combinator itself depends on some external data (in this case a byte array) that influences what it expects. So I'd like my representation of a tag to return something like:

struct TagExpectsFormatter<'t> {
    tag: &'t [u8],
}

which can then implement something like Display to build the string later on.

However, this pattern gives me trouble when I try to write higher-order combinators, like pair(). I wrote something like the following:

use std::fmt::Display;

trait Expects<'t> {
    type Formatter: 't + Display;
    fn expects(&self) -> Self::Formatter;
}

struct PairExpects<F1, F2> {
    fmt1: F1,
    fmt2: F2,
}

struct Pair<C1, C2>(C1, C2);
impl<'t1, 't2: 't1, C1: Expects<'t1>, C2: Expects<'t2>> Expects<'t1> for Pair<C1, C2> {
    type Formatter = PairExpects<C1::Formatter, C2::Formatter>;
    fn expects(&self) -> Self::Formatter {
        PairExpects {
            fmt1: self.0.expects(),
            fmt2: self.1.expects(),
        }
    }
}

(playground, I took the lifetime bounds from this thread)

But this gives me the following error:

Compiling playground v0.0.1 (/playground)
error[E0207]: the lifetime parameter `'t2` is not constrained by the impl trait, self type, or predicates
  --> src/main.rs:19:11
   |
19 | impl<'t1, 't2: 't1, C1: Expects<'t1>, C2: Expects<'t2>> Expects<'t1> for Pair<C1, C2> {
   |           ^^^ unconstrained lifetime parameter

For more information about this error, try `rustc --explain E0207`.
error: could not compile `playground` (bin "playground") due to 1 previous error

Reading the rustc --explain E0207 that the compiler suggests, I guess that this has something do with unconstrained lifetimes being illegal if they occur in associated types of a trait, which seems to happen through the Expects::Formatter (also see the RFC that text suggests).

I'm not sure how to fix this problem, though. Can someone help me make this pattern work? Or else suggest me some other pattern with which I can propagate these lifetimes of nested, generic combinators through higher-order ones?

Thanks,
Tim

[kpreid]

Why not use a single lifetime parameter? This compiles:

impl<'t, C1: Expects<'t>, C2: Expects<'t>> Expects<'t> for Pair<C1, C2>

[lut_99]

Ah yes ~ sorry, I forgot to mention, I tried that initially. This indeed works for defining the Pair, but then later, when trying to use them with mixed lifetimes ('static and something local), it seems to resolve to the largest lifetime instead of the shortest.

For example:

use std::fmt::{Display, Formatter, Result as FResult};

trait Expects<'t> {
    type Formatter: 't + Display;

    fn expects(&self) -> Self::Formatter;
}

struct Tag<'t>(&'t str);
impl<'t> Expects<'t> for Tag<'t> {
    type Formatter = &'t str;
    fn expects(&self) -> Self::Formatter { self.0 }
}

struct PairExpects<F1, F2> {
    fmt1: F1,
    fmt2: F2,
}
impl<F1: Display, F2: Display> Display for PairExpects<F1, F2> {
    fn fmt(&self, f: &mut Formatter) -> FResult { write!(f, "{}, then {}", self.fmt1, self.fmt2) }
}

struct Pair<C1, C2>(C1, C2);
impl<'t, C1: Expects<'t>, C2: Expects<'t>> Expects<'t> for Pair<C1, C2> {
    type Formatter = PairExpects<C1::Formatter, C2::Formatter>;
    fn expects(&self) -> Self::Formatter {
        PairExpects {
            fmt1: self.0.expects(),
            fmt2: self.1.expects(),
        }
    }
}

fn expects_tags<'t>(tag1: &'t str) -> PairExpects<&'t str, &'static str> {
    Pair(Tag(tag1), Tag("Hello, world!")).expects()
}

(check the playground here)

Maybe it's a bit artificial example, but imagine that expects_tags is essentially a parse_tags combinator, just the parse-part left out.

Anyway - the error I get says that it requires that the lifetime 't in expects_tags() needs to live at least as long as 'static, whereas I'm looking for the reverse I think (it needs to notice that 'static only needs to live as long as 't).

Though maybe I'm doing something wrong with the bound on parse_tags?

EDIT: Oh and of course, thanks for looking at it

[kpreid]

You can weaken one of the constraints like this and that playground code will compile:

impl<'t: 'e, 'e> Expects<'e> for Tag<'t> {
    type Formatter = &'t str;
    fn expects(&self) -> Self::Formatter { self.0 }
}

The thing that you need to watch out for when using lifetime parameters on traits is that they are always invariant: having T: Foo<'static> does not imply T: Foo<'a> for any shorter 'a (because the particular trait impl might use the lifetime in a contravariant or invariant way). But the modified trait implementation above explicitly defines that, in the particular case of Tag, that property does hold. (There's no way to make it true in general for all Expects implementors.)

This is a little bit like what you were trying to do for Pair, but it's allowed because both 'e and 't are “ constrained by the impl trait, self type, or predicates” here. Pair still benefits indirectly because the single 't in the impl Expects<'t> for Pair is now less constrained by what the Tags in the Pair are. You can have Expects<'a> for any sufficiently short 'a and any composition of Tags and Pairs, because none of the Tags forces the 'a to be as long as its own reference lifetime.

[lut_99]

Wow, I see, that’s a really cool trick! I hadn’t realised that lifetime parameters in traits aren’t always covariant. That actually explains a lot about the struggle I always had with them. Thanks!!

I think maybe this also clears up something else about lifetime parameters. Just to check my intuition: you’re using the 'a in a truly generic way, right? I’ve grown to think about lifetime parameters as kind of ‘tags’ for other generics to communicate how long they live. And they are, but your version really seems to describe a template for multiple impls of Expects, one for every lifetime 'a for which it holds that the lifetime of Tag<'t> does not live shorter. It really seems to stand alone as a generic. That’s very useful to be reminded of

Anyway ~ thanks a lot! I’ll try it out in the real codebase tomorrow, but I’m confident that it’ll work. But as I know how these things go, I’ll just hold off with closing the topic until I’ve confirmed it

EDIT: Yep, that works. Awesome, thank you so much!

[kpreid]

@lut_99

Just to check my intuition: you’re using the 'a in a truly generic way, right? I’ve grown to think about lifetime parameters as kind of ‘tags’ for other generics to communicate how long they live.

I'm not sure what counts as "truly generic".

One thing that may be useful to think about is that every lifetime name, other than 'static, is a generic parameter of some sort; we cannot ever name a truly concrete lifetime except for 'static, because those are (in theory) run-time things that are unknown when the program is being compiled. In fn foo<'a>(), 'a is a parameter to the function, which can take on a new value every time the function is called. It just happens that this doesn't require any actual work at run time, because everything that is needed to be known about lifetimes was already calculated generically at compile time

[lut_99]

Alright, I see. I think the key insight for me is thinking about lifetime parameters as generics in the sense that they represent a set of possible lifetimes (albeit that we can only know the contents of the set at runtime) instead of a particular one which the compiler chooses based on subtyping. The latter model gets you some way as long as things are nice and covariant, but breaks down in the case of other variances where we need to assume the compiler can no longer do this, and we have to express constraints on the sets ourselves.

Thanks yet again, I think this has given me some important understanding about lifetimes

[kpreid]

Alright, I see. I think the key insight for me is thinking about lifetime parameters as generics in the sense that they represent a set of possible lifetimes (albeit that we can only know the contents of the set at runtime) instead of a particular one which the compiler chooses based on subtyping.

Yes, exactly!

Thanks yet again, I think this has given me some important understanding about lifetimes

And I learned something here too — I had never actually connected “trait lifetime parameters are invariant” (something I knew of as a hazard to keep in mind) to “sometimes it's useful to use two lifetime generics with one would seemingly do” (something I had seen done but didn't really understand) until I tried to explain and solve your problem.