Battling with Lifetimes for a Generic trait

1

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?

2

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())),
        }
    }
}
3

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

Thanks

4

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?

5

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))
}
6

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

1 Like
7

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!

8

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.