Generic trait not implemented for a closure returned by a function

Question

I've been trying to reimplement the nom crate (for learning about parsing) and I cannot figure out how to implement a trait for a closure returned by a function.

The trait

The trait is meant to be implemented for functions which take some bytes as input, returning the new input (without the consumed tokens) and some output:

trait Parser<O, E> {
    fn parse<'a>(&self, data: &'a [u8]) -> Result<(&'a [u8], O), E>;
}

The implementation

The blanket implementation looks like this:

impl<O, E, F> Parser<O, E> for F
where
    F: Fn(&[u8]) -> Result<(&[u8], O), E>,
{
    fn parse<'a>(&self, data: &'a [u8]) -> Result<(&'a [u8], O), E> {
        self(data)
    }
}

This works well enough for functions on their own, for example

fn be_u32(data: &[u8]) -> Result<(&[u8], u32), ParseError> {
    let value = u32::from_be_bytes([data[0], data[1], data[2], data[3]]);
    Ok((&data[size_of::<u32>()..], value))
}
...
let (data, _) = be_u32.parse(data)?;  // This works as expected

Now, when trying to implement the trait for a higher order function returning a closure, I get an error:

fn tag<'a>(
    _tag: &'a str,
) -> impl Fn(&'a [u8]) -> Result<(&'a [u8], String), ParseError> {
    move |data: &'a [u8]| {
        // Parsing logic
    }
}
...
let t = tag("tag");
let (data, _) = t.parse(data)?;

This gives me the error:

error[E0599]: the method `parse` exists for opaque type `impl Fn(&[u8]) -> Result<(&[u8], String), ParseError>`, but its trait bounds were not satisfied
   --> src/qoi_vanilla.rs:180:33
    |
180 |         let (data, _) = qoi_tag.parse(data)?;
    |                                 ^^^^^ method cannot be called due to unsatisfied trait bounds
    |
note: the following trait bounds were not satisfied:
      `<impl Fn(&[u8]) -> Result<(&[u8], std::string::String), ParseError> as FnOnce<(&[u8],)>>::Output = Result<(&[u8], _), _>`
      `impl Fn(&[u8]) -> Result<(&[u8], std::string::String), ParseError>: Fn<(&[u8],)>`
   --> src/byteparser.rs:44:8
    |
42  | impl<O, E, F> Parser<O, E> for F
    |               ------------     -
43  | where
44  |     F: Fn(&[u8]) -> Result<(&[u8], O), E>,
    |        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |        |            |
    |        |            unsatisfied trait bound introduced here
    |        unsatisfied trait bound introduced here

What are the trait bounds I'm not satisfying?

I've tried adding lifetime variables and different combinations of dyn and impl.

kmdreko · Accepted Answer · 2025-02-23 15:12:21Z

0

Your Parser trait needs to work for all lifetimes passed to parse so your implementation on function objects is correctly un-restricted. However your tag implementation takes in a lifetime and the returned function object is only defined to accept and return that lifetime.

The fix is to not bind lifetimes in to the impl Fn returned by tag:

fn tag<'a>(
    _tag: &'a str,
) -> impl Fn(&[u8]) -> Result<(&[u8], String), ParseError> + 'a {
    move |data: &[u8]| {
        // Parsing logic
    }
}

It will actually work the same with all lifetimes elided, but I've left the outer one explicit for your benefit. The _tag is captured in the returned impl Fn, but its parameters and return type are not bound to its lifetime.

answered Feb 23 at 15:12

kmdreko

65.4k6 gold badges106 silver badges178 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Hannes Ryberg Feb 24 at 7:39

It works, so thank you very much! I still don't really understand why it works though. What does the + 'a (which gets elided to only + '_) mean exactly? That the returned closure has the lifetime of _tag?

kmdreko Feb 24 at 7:52

@HannesRyberg yes

Collectives™ on Stack Overflow

Generic trait not implemented for a closure returned by a function

The trait

The implementation

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

The trait

The implementation

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related