Higher-Ranked Trait Bounds vs Borrow Abstractions

I have tried to simplify my problem now a few types without completely destroying the intention of what I'm trying to do but I'm really struggling to understand if there are any meaningful workarounds or what exactly the core issue is.

To set the stage, imagine I have a type that represents a runtime value:

#[derive(Debug)]
enum Value {
    String(String),
    Number(i64),
}

And this trait and family of implementations to convert or borrow out of the value:

trait TryConvertValue<'a>: Sized {
    fn try_convert_value(value: &'a Value) -> Option<Self>;
}

impl<'a> TryConvertValue<'a> for &'a str {
    fn try_convert_value(value: &'a Value) -> Option<Self> {
        match value {
            Value::String(string) => Some(string),
            Value::Number(_) => None,
        }
    }
}

impl<'a> TryConvertValue<'a> for String {
    fn try_convert_value(value: &'a Value) -> Option<Self> {
        match value {
            Value::String(string) => Some(string.clone()),
            Value::Number(number) => Some(number.to_string()),
        }
    }
}

impl<'a> TryConvertValue<'a> for i64 {
    fn try_convert_value(value: &'a Value) -> Option<Self> {
        match value {
            Value::String(_) => None,
            Value::Number(number) => Some(*number),
        }
    }
}

So far, so good. This sort of abstraction works well, so you can do this just fine:

let foo: &str = TryConvertValue::try_convert_value(&value).unwrap();
let foo: String = TryConvertValue::try_convert_value(&value).unwrap();

However, I absolutely cannot find a way to funnel this abstraction through functions. I wanted to box up a bunch of functions that are exposed to a user where the arguments are abstracted through the TryConvertValue trait. In this simplified example, imagine only a single argument is supported:

trait CallbackTrait<Arg>: Send + Sync + 'static {
    fn invoke(&self, args: Arg) -> Value;
}

impl<Func, Arg> CallbackTrait<Arg> for Func
where
    Func: Fn(Arg) -> Value + Send + Sync + 'static,
    Arg: for<'a> TryConvertValue<'a>,
{
    fn invoke(&self, arg: Arg) -> Value {
        (self)(arg)
    }
}

struct ArgCallback(Box<dyn Fn(&Value) -> Value + Sync + Send + 'static>);

impl ArgCallback {
    pub fn new<F, Arg>(f: F) -> ArgCallback
    where
        F: CallbackTrait<Arg>,
        Arg: for<'a> TryConvertValue<'a>,
    {
        ArgCallback(Box::new(move |arg| -> Value {
            f.invoke(TryConvertValue::try_convert_value(arg).unwrap())
        }))
    }

    pub fn invoke(&self, arg: &Value) -> Value {
        (self.0)(arg)
    }
}

It works for owned values:

let pow = ArgCallback::new(|a: i64| Value::Number(a * a));

But it does not compile for borrowed values:

let to_upper = ArgCallback::new(|a: &str| Value::String(a.to_uppercase()));
23 |     let to_upper = ArgCallback::new(|a: &str| Value::String(a.to_uppercase()));
   |                    ^^^^^^^^^^^^^^^^ implementation of `TryConvertValue` is not general enough
   |
   = note: `TryConvertValue<'0>` would have to be implemented for the type `&str`, for any lifetime `'0`...
   = note: ...but `TryConvertValue<'1>` is actually implemented for the type `&'1 str`, for some specific lifetime `'1`

I presume the issue is related to what was being discussed in this thread, however I'm not sure if there are reasonable workarounds for what I am trying to accomplish.

Your example doesn't actually appear to use the 'a on TryConvertValue. Does your actual code have a lifetime on Value?

The root of the problem in the example is that this bound

T: for<'a> TryConvertValue<'a>,

can never be satisfied for the non-static-argument case like &str, because you need something more like

for<'a> &'a str: TryConvertValue<'a>

Thus, I suspect you're going to need to generalize over static arguments and lifetime-carrying arguments:

// Gat like helper for potential lifetime type constructors
trait ArgRepr<'a> {
    type Arg: 'a + TryConvertValue<'a>;
}

// Static args implement the trait themselves: <T as ArgRepr<'_>>::Arg == T
impl<T: 'static + for<'any> TryConvertValue<'any>> ArgRepr<'_> for T {
    type Arg = T;
}

// Non-static args need a represenative.  Since we've only implemented the above
// for sized types, references to unsized types can be represented by the unsized
// type.
//
// You'll need one of these per reference arg, and if it's sized, you'll need
// a dummy type represenative.
impl<'a> ArgRepr<'a> for str {
    type Arg = &'a str;
}

So your bound can be

T: for<'a> ArgRepr<'a> // implies...
// for<'a> <T as ArgRepr<'a>>::Arg: TryConvert<'a>

Which works for both static sized args, and for representatives of lifetime carrying args like str.

Then build up from that, perhaps with a single lifetime version of CallbackTrait that you then use to build the higher-ranked actual CallbackTrait.


The next challenge may be that generic implementations that hit all cases with the ArgRepr abstraction will defeat inference. In that case you can perhaps restore some inference by implementing for the static arguments in a blanket fashion, and then for each lifetime-carrying arg via it's for<'a> ArgRepr<'a> represenative (str for &str, ...).

I don't think I have time to hash it out today, but see here for a walkthrough of what I believe is a related problem.

4 Likes

Playground. If you have more lifetime carrying types, you'll probably want to macro it up (assuming you want the inference-friendly approach).

I was afraid of that answer. I already toyed around with these but this breaks inference to the point where the API is impossible to use or you end up with generating arity * types implementations of the function types.

It's quite frustrating that an otherwise well working API ends up being heavily constrained by the limitations on HRTBs involving callbacks. The reason I did not want to go down that path was that in the real world I have, I already have 5 types that I want people to borrow and I was planning on supporting 4 arities. That's just a lot of code that would need to be generated.

But thank you very much for that explanation and also your example. This looks quite a bit cleaner than what I ended up creating as a result of the link you provided yesterday.

Yeah, multiple arguments or arities does result in a combinatorial explosion of code. I'm afraid I don't know any way around that (especially while preserving inference).

Thank you for your help. I ended up finding a solution for my problem afterall and wrote the summary down here for others: You Can't Do That: Abstracting over Ownership in Rust with Higher-Rank Type Bounds. Or Can You? | Armin Ronacher's Thoughts and Writings

This struct has the main bit that makes it work: minijinja/filters.rs at 1b0da4da6e9e199f4056d571f98217c641279c34 · mitsuhiko/minijinja · GitHub

6 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.