Blanket impl, HRTB, and "impl" abstract return type: "expected bound lifetime parameter"

Question

I started a very small program to play with parser combinators in Rust, and quickly encountered an error I found strange:

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

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

// why can't I write:
// fn byte(b: u8) -> impl Parser<u8, ()> {

// this works, and the blanket Parser impl picks it up correctly
fn byte(b: u8) -> impl for<'a> Fn(&'a [u8]) -> Result<(&'a [u8], u8), ()> {
    move |input: &[u8]| match input.first() {
        Some(x) if *x == b => Ok((&input[1..], *x)),
        _ => Err(()),
    }
}

fn main() {
    println!("{:?}", byte(b'c').parse(b"c123"));
}

The commented-out signature for byte (returning impl Parser<u8, ()>) fails to compile with:

error[E0271]: type mismatch resolving `for<'a> <[[email protected]:14:5: 19:6 b:_] as std::ops::FnOnce<(&'a [u8],)>>::Output == std::result::Result<(&'a [u8], u8), ()>`
  --> parser.rs:12:19
   |
12 | fn byte(b: u8) -> impl Parser<u8, ()> {
   |                   ^^^^^^^^^^^^^^^^^^^ expected bound lifetime parameter 'a, found concrete lifetime
   |
   = note: required because of the requirements on the impl of `Parser<u8, ()>` for `[[email protected]:14:5: 19:6 b:_]`
   = note: the return type of a function must have a statically known size

I understand neither why a bound lifetime parameter was expected, nor what concrete lifetime was found.

The way I see it, the closure returned has some ineffable type. This type implements for <'a> Fn(&'a [u8]) -> Result<(&'a [u8], u8), ()> (and the compiler recognizes this). As a consequence, it should also by the blanket impl implement Parser<u8, ()>, or so I thought.

It's the same as github.com/rust-lang/rust/issues/41078, isn't it? Dammit. I've been down the trillions-of-structs-masquerading as closures path before. Gives me C++98 "functor" flashbacks. See also: all the various stdlib iterator flavors. — Derrick Turk

Isaac van Bakel Isaac van Bakel · Accepted Answer · 2019-05-16T00:08:42

The way I see it, the closure returned has some ineffable type. This type implements for <'a> Fn(&'a [u8]) -> Result<(&'a [u8], u8), ()> (and the compiler recognizes this).

That's only if you specify it.

Consider the function signature without the lifetime information:

fn byte(b: u8) -> impl Fn(&[u8]) -> Result<(&[u8], u8), ()>

Which, if you write out the elided lifetimes, gives

fn byte<'a>(b: u8) -> impl Fn(&'a [u8]) -> Result<(&'a [u8], u8), ()>

This doesn't implement the higher-order for<'a> Fn ... - it only implements the Fn trait for some fixed 'a, decided by the caller to byte.

That is the concrete lifetime the compiler is complaining about - where it expects to find a lifetime which is bound by for<...>, it instead finds a lifetime which is already described.

Blanket impl, HRTB, and "impl" abstract return type: "expected bound lifetime parameter"

1 Answers