Error message not helping me at all

help
1

Hello,

I am implementing a small parser for fun, I have the following error message

error[E0308]: mismatched types
  --> src/parse.rs:17:31
   |
17 | pub fn parse_char(c: char) -> impl Parser<char> {
   |                               ^^^^^^^^^^^^^^^^^ one type is more general than the other
   |
   = note: expected enum `Result<(&str, _), (&str, ParserError)>`
              found enum `Result<(&str, _), (&str, ParserError)>`

As you can see, the compiler is complaining that it found what it expected. I figure out I can be more explicit and return something more specific, but I would still like to understand the problem here.

That is most of the important code

type ParserResult<'a, T> = Result<(&'a str, T), (&'a str, ParserError)>;

#[derive(Debug, PartialEq, Eq)]
struct ParserError(&'static str);

trait Parser<T> {
    fn parse<'s>(&self, input: &'s str) -> ParserResult<'s, T>;
}

impl<F, T> Parser<T> for F where F: Fn(&str) -> ParserResult<T> {
    fn parse<'s>(&self, input: &'s str) -> ParserResult<'s, T> {
        self(input)
    }
}

// Can't compile this function.
fn parse_char(c: char) -> impl Parser<char> {
    move |input: &str| {
        if input.starts_with(c) {
            Ok((&input[1..], c))
        } else {
            Err((input, ParserError("character not found")))
        }
    }
}

I also made a playground with a minimal reproduction of the error and a little more details.

4

Closures with types that are generic (over lifetimes) are a bit tricky with type inference, apparently. It seems to me as if the impl Fn return type does help the closure find its correct type while the impl Parser doesn’t. It seems like you can’t really annotate how the lifetimes are supposed to interact in the closure signature either, even with an explicit return type. For the record, this seems to work in your playground:

fn parse_char(c: char) -> impl Parser<char> {
    parse_char2(c)
}

The error message certainly is not very helpful. Looks like the two types that look the same actually differ in lifetimes that the compiler doesn’t show you. Or something like that.

5

Perhaps an ergonomic way to help type inference out here is with a helper function. Something like

fn parser_fn<T, F>(f: F) -> impl Parser<T>
where
    F: Fn(&str) -> ParserResult<'_, T>,
{
    f
}

fn parse_char(c: char) -> impl Parser<char> {
    parser_fn(move |input: &str| {
        if input.starts_with(c) {
            Ok((&input[1..], c))
        } else {
            Err((input, ParserError("character not found")))
        }
    })
}

Actually even

fn parser_fn<T, F>(f: F) -> F
where
    F: Fn(&str) -> ParserResult<'_, T>,
{
    f
}

does the trick, helping out the compiler to figure out the right shape of Fn trait implementation.

Either of these helper functions also removes the need for providing the type of input explicitly.

parser_fn(move |input| {
    if input.starts_with(c) {
        Ok((&input[1..], c))
    } else {
        Err((input, ParserError("character not found")))
    }
})
6

This is a nice solution. I also found a solution, but it involves a lot of lifetime annotations to make sure that the lifetime of the input and output are linked are not the other ones.

type ParserResult<'a, T> = Result<(&'a str, T), (&'a str, ParserError)>;

pub struct ParserError(&'static str);

pub trait Parser<'a, T> {
    fn parse(&self, input: &'a str) -> ParserResult<'a, T>;
}

impl<'a, F, T> Parser<'a, T> for F where F: Fn(&'a str) -> ParserResult<'a, T> {
    fn parse(&self, input: &'a str) -> ParserResult<'a, T> {
        self(input)
    }
}

pub fn parse_char<'a>(c: char) -> impl Parser<'a, char> {
    move |input: &'a str| {
        if input.starts_with(c) {
            Ok((&input[1..], c))
        } else {
            Err((input, ParserError("character not found")))
        }
    }
}
7

This kind of trait would also allow for the type T to depend on the lifetime 'a. So that the parser could parse some &'a str slices from the original input without needing to copy them (but with the restriction that such a type T can only live as long as the original string you parsed from is kept alive). Whether having the trait like this makes sense depends on your use-cases, e.g. on if something like this is actually needed; the trait with the lifetime parameter is a bit more flexible in this regard, but as you noticed already it’s also a bit more verbose to work with. This would be similar to what serde allows as well with its lifetime on Deserialize.

8

In fact, this make a lot of sense to me to have this feature. I will try to combine this idea with your parser_fn solution. Thanks for the help.

Now, I wonder what would have been a good error message. I guess something like this would have help me

= note: expected enum `Result<(&'a str, _), (&'a str, ParserError)>`
            found enum `Result<(&'a str, _), (&'b str, ParserError)>`

with a mention that exact lifetimes can't be inferred in this case.

That is, if I understand well the source of the error.

9

Note that what you provided above doesn’t give you the full power possible yet, i.e.:

your function

pub fn parse_char<'a>(c: char) -> impl Parser<'a, char> {
    move |input: &'a str| {
        if input.starts_with(c) {
            Ok((&input[1..], c))
        } else {
            Err((input, ParserError("character not found")))
        }
    }
}

doesn’t provide a way to satisfy a higher-ranked bound, so this doesn’t work:

pub fn parse_char2(c: char) -> impl for<'a> Parser<'a, char> {
    parse_char(c)
}

Going the other way would work. If you use

fn parser_fn<T, F>(f: F) -> F
where
    F: Fn(&str) -> ParserResult<'_, T>,
{
    f
}

pub fn parse_char2(c: char) -> impl for<'a> Parser<'a, char> {
    parser_fn(move |input| {
        if input.starts_with(c) {
            Ok((&input[1..], c))
        } else {
            Err((input, ParserError("character not found")))
        }
    })
}

it also allows for using it like

pub fn parse_char<'a>(c: char) -> impl Parser<'a, char> {
    parse_char2(c)
}

In fact, for this Parser<'a, T> trait it might be useful to introduce a “synonym” similar to serde’s DeserializeOwned, i.e.

pub trait OwnedParser<T>: for<'a> Parser<'a, T> {}
impl<T, P: ?Sized> OwnedParser<T> for P where for<'a> P: Parser<'a, T> {}

then you can do

pub fn parse_char2(c: char) -> impl OwnedParser<char> {
    parser_fn(move |input| {
        if input.starts_with(c) {
            Ok((&input[1..], c))
        } else {
            Err((input, ParserError("character not found")))
        }
    })
}

The name subject to debate. You might also like something like Parser_<'a, T> and Parser<T>. This would stay “compatible” with your original Parser trait pretty much.

10

That is cool. I am not familiar with Higher-Rank bounds, but after a quick read, I think what you propose make sense. I will try to play with that and see what I can achieve. :slight_smile: