Generic trait not implemented for a closure returned by a function

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.

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.