Passing in type information with lifetimes

help
1

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.

2

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).

3

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.

4

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.

5

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
6

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
7

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.

8

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.

9

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!