Type that accepts generic closures which return owned or referenced values

help
1

I've been working on a small library as part of a larger project which lets you build "comparators" which compare things. Instead of using Ord, you can build and customize a comparator to change the way that two things are compared. The motivating use-case is in an application where the user may customize the sort behavior of a table of complex data.

One important combinator that I'm trying to write is called map, which lets you map a value to another value so the output is compared instead of the original. For example, given a list of structs, you might want to sort them based on a single field of that struct, so you would use a map combinator with a closure like |x: Foo| &x.sort. However I've been having a lot of trouble writing a single generic type for map that accepts both closures that return an owned value (such as a single number, or a tuple of numbers) and closures that return a referenced value (such as a reference to a non-Copy field of a struct), as well as combinations of the two (such as a tuple where the first field is a reference and the second field is a number).

This is my most basic attempt at this, which fails to compile for closures returning references, I think because the closure's output type has nothing that requires it lives as long as the argument.

I've tried a lot of other approaches with lifetime generics which resulted in even thornier compile errors like "one type is more general than the other". I feel like I must be missing something fundamental here. How do you write a closure type that's generic on the output but still requires that the output must live as long as the input? How would you fix the code I linked so that all three comparisons in main compile?

2

As soon as you write

    TMap: Fn(&TIn) -> TOut,

you've indicated that the output of the mapping function is a type that does not depend on the lifetime of the input. You need

    TMap: Fn(&TIn) -> TOut<'_>,

but then there's no way to define TOut without getting into generic associated types (GAT). I don’t know if there is a clean general solution, but that is why you are having trouble.

1 Like
3

Yes I've tried versions of this with GATs, like having the Comparator trait have a type Value<'a>; (instead of a generic argument) for the type of things it compares, and that got really messy fast and had a lot of other issues. Is this just not possible with Rust at the moment?

4

You can get a certain distance depending on the use case. Even when that's the case, the indirection involved often destroys inference, especially if the Fn traits are involved.

Here's an example for your playground.

Note how I had to do this:

// Identity function with `Fn` trait bound
fn coerce_closure_1<F>(f: F) -> F
where
    F: Fn(&Foo) -> &Vec<usize>
{
    f
}

// ...

    let cmp2 = Map {
        map: coerce_closure_1(|x: &Foo| &x.vals),
        inner: Nat {},
    };
    dbg!(cmp2.compare(&foo1, &foo2));

That's due to a related problem that exists outside just your use case: in the absence of an expected bound, closure inference can't deal with closures that take an input with any lifetime and return an output with the same lifetime. See here for an example.

But this ability of bounds to drive closure inference only works for the Fn traits directly. If we go back to the code with the MapFn indirection...

fn needs_bound<F: MapFn<str>>(_: F) {}
fn try_it() {
    needs_bound(|s: &str| s);
}

error: lifetime may not live long enough
  --> src/main.rs:86:27
   |
86 |     needs_bound(|s: &str| s);
   |                     -   - ^ returning this value requires that `'1` must outlive `'2`
   |                     |   |
   |                     |   return type of closure is &'2 str
   |                     let's call the lifetime of this reference `'1`

...you get the "default closure inference" that can't deal with taking any lifetime and returning it.

That's an example of what I meant when I said that the indirection destroys inference.

Depending on your mental model, it may help to not think of it as "lives long enough", but in terms of types. And types with different lifetimes are different types. This bound says:

TMap: Fn(&TIn) -> TOut
// Same thing:
Tmap: for<'a> Fn(&'a TIn) -> TOut

"All input types produce the same output type" (because TOut represents a single type).

There are no "generic type constructors" in Rust to specify a bound for returning a distinct but generic type per input lifetime...

// Imaginary feature
//              vvvvvvvv                                     vvvvvvvvvvvv
impl<TMap, Tin, TOut<..>> where Tmap: for<'a> Fn(&'a TIn) -> TOut<'a, ..>

...so we fall back to indirection through associated types and such.

5

Appreciate the detailed response. This is so close to working! Unfortunately as you say, inference is broken in a way I'm not sure I can easily resolve, giving me errors like this:

error[E0277]: the trait bound `for<'a> Then<Nat<_>, Nat<_>>: Cmp<<_ as MapFnLt<'a, _>>::Out>` is not satisfied
   --> lib/cmp/src/lib.rs:631:59
    |
631 |         v.sort_using(&map(|&(a, b): &(i32, i32)| (-b, a), then(nat(), nat())));
    |                       ---                                 ^^^^^^^^^^^^^^^^^^ the trait `for<'a> Cmp<<_ as MapFnLt<'a, _>>::Out>` is not implemented for `Then<Nat<_>, Nat<_>>`
    |                       |
    |                       required by a bound introduced by this call
    |
    = help: the trait `Cmp<<_ as MapFnLt<'a, _>>::Out>` is not implemented for `Then<Nat<_>, Nat<_>>`
            but trait `Cmp<(_, _)>` is implemented for it
    = help: for that trait implementation, expected `(_, _)`, found `<_ as MapFnLt<'a, _>>::Out`
note: this is a known limitation of the trait solver that will be lifted in the future
   --> lib/cmp/src/lib.rs:631:59
    |
631 |         v.sort_using(&map(|&(a, b): &(i32, i32)| (-b, a), then(nat(), nat())));
    |                       ------------------------------------^^^^^^^^^^^^^^^^^^-
    |                       |                                   |
    |                       |                                   the trait solver is unable to infer the generic types that should be inferred from this argument
    |                       add turbofish arguments to this call to specify the types manually, even if it's redundant
note: required by a bound in `map`
   --> lib/cmp/src/lib.rs:185:13
    |
182 | pub fn map<
    |        --- required by a bound in this function
...
185 |     TInner: for<'a> Cmp<<TMap as MapFnLt<'a, TIn>>::Out>,
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ required by this bound in `map`

It's asking me to manually name types that are too complex to name, and "this is a known limitation of the trait solver that will be lifted in the future" isn't encouraging. Oh well, I might try some other approach.

6

Some of those errors may have just been because I didn't use your coerce_closure helpers actually, but that seems way too verbose to make this useful.

7

Yeah, that's the rub. If the magical coercion powers of Fn bounds transferred to subtraits of Fn, like MapFn, things might be a lot better (it might only be as annoying as typical closure bounds). Or even if we had some notation like

// "use the input lifetime plz" vvvvvvvvv
let my_closure = |s: &str| -> _ + use<'_> { s }
// "infer the type too"       ^

(There's this RFC, but it's initial form is too limiting as you still have to write out the type. I want something that's not only more ergonomic, but works with unnameables like closures and most futures.)