Passing in type information with lifetimes

Apologies if this has been discussed before. But I wasn't able to find an answer so far, and all the other stuff looks a bit different to what I am struggling with.

Assuming I do have a trait like this:

pub trait Search<'a>: Sized {
    fn parse(s: &'a str) -> Result<Self, ()>;
}

And a function like this:

fn use_example_1<S>()
where
    S: for<'s> Search<'s>,
{
    let _ok = match S::parse("") {
        Ok(_) => true,
        Err(_) => false,
    };
}

Using it like this:

struct Test<'a>(&'a str);

impl<'a> Search<'a> for Test<'a> {
    fn parse(s: &'a str) -> Result<Self, ()> {
        Ok(Test(s))
    }
}

#[test]
fn test_lifetimes() {
    use_example_1::<Test>();
}

I run into:

error: implementation of `Search` is not general enough
  --> tests/lifetime.rs:47:5
   |
47 |     use_example_2::<Test>();
   |     ^^^^^^^^^^^^^^^^^^^^^ implementation of `Search` is not general enough
   |
   = note: `Search<'0>` would have to be implemented for the type `Test<'_>`, for any lifetime `'0`...
   = note: ...but `Search<'1>` is actually implemented for the type `Test<'1>`, for some specific lifetime `'1`

Reading to a bunch of topics like this, I came up with a workaround of:

pub trait SearchBorrowed {
    type Search<'a>: Search<'a>;
}

fn use_example_2<S>()
where
    S: SearchBorrowed,
{
    let _ok = match S::Search::parse("") {
        Ok(_) => true,
        Err(_) => false,
    };
}

impl SearchBorrowed for Test<'_>
{
    type Search<'a> = Test<'a>;
}

That works. But the downside is that for every T I have, I also need to implement the SearchBorrowed trait. A blanket implementation seems to bring back the original error.

Here is a link to the playground: Rust Playground

I am wondering if there is a more elegant solution to this.

A concrete type always has a concrete lifetime, and generics can't be higher-ranked over types (only over lifetimes). Thus, this is not directly possible. You'll always nave to have an associated type that allows the calling code to concretize from a HRTB to a concrete Searcher with a specific lifetime.

The blanket impl doesn't work because it's exactly the same problem, just with a different trait (ie. you kicked the bucket down the road).

You can fix your example by replacing the for<'s> Search<'s> bound with Search<'static>. Don't know if this is applicable to your real world needs though. Playground.

It's probably not – that doesn't work with a local string (as opposed to a literal), which was likely the whole reason for the HRTB in the first place.

Accordingly, I think a sensible solution is to simply present the interface of the "borrowed searcher" workaround, but without any sort of supertrait. Thus, you won't need to impl 2 traits per type, only one: Playground

pub trait Search {
    type Searcher<'s>;

    fn parse(s: &str) -> Result<Self::Searcher<'_>, ()>;
}

impl Search for Test<'_> {
    type Searcher<'s> = Test<'s>;
    fn parse(s: &str) -> Result<Test<'_>, ()> {
        Ok(Test(s))
    }
}
2 Likes

Of course. I was thinking that this would extend from 'static to any lifetime 'a as long as the string slice is passed as an argument. But a local &str instance wouldn't work.

1 Like

Yes, that was exactly the problem. In real-life it's not a literal, but a local string as you said. Parsing is done on the (user) provided &str.

That's an interesting idea. IIRC I am using that pattern in another case also, but it didn't cross my mind!

I actually implement the trait with a derive macro, so the user wouldn't be bothered too much with that.

Thanks for the idea!

Just for reference, the actual code of this is here: GitHub - ctron/sikula: A simple query language … it uses chumsky to parse a search query without the need to allocate. Thus the references instead owned strings.

So I tried to implement the idea. Turns out, I recalled the pattern from exactly this crate :rofl: … the Parsed associated type in the trait was necessary due to the fact returning structures required the lifetime, but didn't use it themselves. And that was the workaround:

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Term<'a, S>
where
    S: Search,
{
    Match(S::Parsed),
    Not(Box<Term<'a, S>>),
    Or(Vec<Term<'a, S>>),
    And(Vec<Term<'a, S>>),
}

In the trait

pub trait Search<'a>: Sized {
    type Parsed;
// … 
}

Using the S::Parsed type seemed to have triggered a "usage" of the lifetime argument and it worked.

So I added the lifetime to that associated type:

pub trait Search: Sized {
    type Parsed<'a>: Search;
// …
}

Of course reality is a bit more complex, so it took a bit longer to get all the rest going, but it looks good now!

Many thanks for your help!

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.