Battling with Lifetimes for a Generic trait

I have a trait:


pub trait Parser<V>: Sized {
    fn parse<'a>(&self, i: &LCChars<'a>) -> ParseRes<'a, V>;
}

It's implement for several things such a strings and chars and functions that fit a pattern:

impl<V, F: for<'a> Fn(&LCChars<'a>) -> ParseRes<'a, V>> Parser<V> for F {
    fn parse<'b>(&self, i: &LCChars<'b>) -> ParseRes<'b, V> {
        self(i)
    }
}

I really want to make the parser able to return a borrowwed str with the lifetime associated to the lifetime of the LCCHars (a wrapper around std::str::CharIndices).

Here is one attempl


pub struct AsStr<P: Parser<V>, V> {
    p: P,
    phv: PhantomData<V>,
}


impl<P: Parser<V>, V> Parser<&str> for AsStr<P, V> {
    // the lifetime of     ^^^ needs to match LCChars<'a>
    fn parse<'a>(&self, it: &LCChars<'a>) -> ParseRes<'a, &'a str> {
        //run the parser ignore the result
        let (it2, _) = self.p.parse(it)?;
        //match against the index before and the index after
        match (it.index(), it2.index()) {
            (Some(s), Some(f)) => Ok((it2, &it.as_str()[0..(f - s)])),
            _ => Ok((it2, &it.as_str())),
        }
    }
}

Currently the error is that the inner function does not match the trait.
If I remove the 'a from the ParseRes : eg ParseRes<'a,&str> then there is alifetime missmatch with the function.

The str result should have a lifetime tied to the str that LCChars holds a reference to. And is only a parameter of the function call, This function could be caled many times with different LCChars, so it makes little sense to tie the lifetime to the actual parser.

Any ideas?

Lift the lifetime parameter to the trait, and make the output type an associated type.

pub trait Parser<'text>: Sized {
    type Output;
    fn parse(&self, i: &LCChars<'text>) -> ParseRes<'text, Self::Output>;
}

impl<'text, V, F: Fn(&LCChars<'text>) -> ParseRes<'text, V>> Parser<'text> for F {
    type Output= V;
    fn parse(&self, i: &LCChars<'text>) -> ParseRes<'text, V> {
        self(i)
    }
}

pub struct AsStr<P> {
    p: P,
}

impl<'text, P: Parser<'text>> Parser<'text> for AsStr<P> {
    type Output = &'text str;
    fn parse(&self, it: &LCChars<'text>) -> ParseRes<'text, &'text str> {
        //run the parser ignore the result
        let (it2, _) = self.p.parse(it)?;
        //match against the index before and the index after
        match (it.index(), it2.index()) {
            (Some(s), Some(f)) => Ok((it2, &it.as_str()[0..(f - s)])),
            _ => Ok((it2, &it.as_str())),
        }
    }
}

that makes sense, I'll give it a try. might take some time to apply it across the whole library mind.

Thanks

OK, It took some time, but I have now applied this to the library, unfortunately this has led to a new problem:

The plan, and design of this project is to use combinators, which each have a specific return type:

Before this update:

struct Ob{
    a:String,
    b:String,
}
fn ob()->impl Parser<Ob>{
    a_parser.then(b_parser).map(|(a,b)| Ob{a,b})
}

Now it looks like:

fn ob()->impl Parser<'_>{
    a_parser.then(b_parser).map(|(a,b)| Ob(a,b))
}

This loses the documentation on the Parser type which is mildly annoying but OK, except, that now,
the return type is Associated::Object, and not of type Ob. Even though they match.

The compiler is telling me to constrain it somehow, but I can't work out how:

fn ob()->impl Parser<'_,Output=Ob>{
    a_parser.then(b_parser).map(|(a,b)| Ob(a,b))
}

creates a lifetime issue.

How do I make this work?

What I would add a trait alias:

pub trait Parser<'text> {
    type Output;
    fn parse(&self, i: &LCChars<'text>) -> ParseRes<'text, Self::Output>;
}

pub trait OwnedParser<Out>: for<'text> Parser<'text, Output = Out> {}
impl<Out, P: ?Sized> OwnedParser<Out> for P
where
    P: for<'text> Parser<'text, Output = Out>
{}

Then you can return OwnedParser most of the time,

fn ob() -> impl OwnedParser<Ob>{
    a_parser.then(b_parser).map(|(a,b)| Ob(a,b))
}

When you can't (when you directly borrow from the input) you will need to provide a lifetime paramter

fn ob<'text>() -> impl Parser<'text, Output = Ob>{
    a_parser.then(b_parser).map(|(a,b)| Ob(a,b))
}

Thanks again. My head is fried right now. I'll have to look at this tomorrow. But I really appreciate your help

1 Like

No-copy parsing is a hard problem, largely because they have a lot of lifetimes to track, so it helps a lot to name the lifetimes as I've been doing, or by removing them entirely as with OwnedParser. You'll get through it!