Implementation is not general enough

[duarten]

Hi,

I'm trying to get the code below to compile (rust playground link). I'm expecting that the borrow checker could match the local lifetime 'de to the lifetime foo expects, but apparently I need to help it somehow.

use serde; // 1.0.124
use serde_json; // 1.0.64

use serde::Deserialize;

#[derive(Debug, Deserialize)]
struct Value<'a> {
    v: &'a str
}

trait Handler<A> {
    fn call(&self, a: A);
}

fn handler_fn<F>(f: F) -> HandlerFn<F> {
    HandlerFn { f }
}

struct HandlerFn<F> {
    f: F
}

impl<A, F> Handler<A> for HandlerFn<F> 
where
    F: Fn(A),
{
    fn call(&self, a: A) {
        (self.f)(a)
    }
}

fn foo<'a>(d: Value<'a>) { 
    println!("{:?}", d);
}

fn call_foo<A, F>(f: F) -> Result<(), serde_json::Error>
where
    A: for<'de> Deserialize<'de>,
    F: Handler<A> + 'static,
{
    {
        let b = "{\"v\": \"x\"}".to_owned();
        let x = serde_json::from_str(&b)?;
        f.call(x);
    }
    Ok(())
}

fn main() {
    let h = handler_fn(foo);
    call_foo(h).unwrap();
}

This produces the error "implementation of Deserialize is not general enough". I've tried to add some intermediary types, but was never able to get it to work and have Rust infer all the types. Could someone point me in the right direction?

[Kestrer]

The problem is can be solved by adding an intermediate trait that essentially provides a type-level function from a lifetime to a type that can be deserialized with that lifetime.

[duarten]

Ah-ha, thanks a lot! Is there some reading material about why this is needed? It's pretty far from intuitive for me.

[Kestrer]

The derived implementation of Deserialize generates:

impl<'de> Deserialize<'de> for Value<'de> { /* ... */ }

Or, in English:

For any lifetime 'de, a value with lifetime 'de be deserialized from data that has a lifetime of 'de.

for<'de> Deserialize<'de> in English means:

For any lifetime 'de, this type can be deserialized from data that has a lifetime of 'de.

Notice the difference here: Given some Value<'de>, it can only be deserialized from data with one lifetime - 'de. So it cannot satisfy for<'de> Deserialize<'de>, as that would require it to implement Deserialize<'a>, Deserialize<'b>, Deserialize<'c> et cetera which it doesn't.

So the type parameter on this function can't be any sort of Value, because that would require it to be bound to one specific lifetime when passed into the function, whereas your function needs to accept a Value<'a>, where 'a is chosen by the function itself.

Now, if Rust had a feature called "higher-kinded types" this would be easy:

fn call_foo<A<'_>, F>(f: F) -> Result<(), serde_json::Error>
where
    // Notice the similarity between this and:
    // impl<'de> Deserialize<'de> for Value<'de>
    for<'de> A<'de>: Deserialize<'de>,
    F: for<'de> Handler<A<'de>> + 'static,
{ /* ... */ }

// Can be called like this:
call_foo::<Value, _>
// Notice the lack of a lifetime parameter on `Value` - we're not passing
// `Value<'a>` for some lifetime `'a`, we're passing `Value` itself, which
// is a type that can accept any lifetime.

But unfortunately, Rust lacks this feature currently - so we have to use an auxiliary trait and type to emulate it. With a Rust feature called GATs, this approach can be made slightly better:

trait DeserializeBorrowed {
    type Deserialize<'de>: Deserialize<'de>;
}

fn call_foo<A, F>(f: F) -> Result<(), serde_json::Error>
where
    A: DeserializeBorrowed,
    F: for<'de> Handler<A::Deserialize<'de>> + 'static,
{ /* ... */ }

The key thing is that instead of taking in a type that can be deserialized into, we take a type that can be used to construct another type that can be deserialized into. That layer of indirection allows the function to choose the lifetime it wishes to instantiate Value with, instead of it being specified by the caller.

[duarten]

Got it! Thanks a lot for taking the time to write that clear explanation; it makes perfect sense