Trouble unifying function types involving HRTB

[Manishearth]

use std::borrow::{Cow,  ToOwned};

pub trait Yokeable<'a> : 'static {
    type Transformed: 'a + Sized;
}

impl<'a, T: ToOwned + ?Sized> Yokeable<'a> for Cow<'static, T> {
    type Transformed = Cow<'a, T>;
}

pub fn attach<Y: 'static, F>(f: F)
where
    F: for<'de> FnOnce(&'de [u8]) -> <Y as Yokeable<'de>>::Transformed,
{
    unimplemented!()
}
fn deserialize<'d>(data: &'d [u8]) -> <Cow<'static, [u8]> as Yokeable<'d>>::Transformed {
    unimplemented!()
}

fn deserialize2<'d>(data: &'d [u8]) -> Cow<'d, [u8]> {
    unimplemented!()
}

fn main() {
    attach::<Cow<'static, [u8]>, _>(deserialize);
}

(playpen)

throws up the following error, both when using deserialize and deserialize2 in `attach

error[E0271]: type mismatch resolving `for<'de> <for<'d> fn(&'d [u8]) -> <Cow<'static, [u8]> as Yokeable<'d>>::Transformed {deserialize} as FnOnce<(&'de [u8],)>>::Output == <Cow<'static, [u8]> as Yokeable<'de>>::Transformed`
  --> src/main.rs:26:5
   |
11 | pub fn attach<Y: 'static, F>(f: F)
   |        ------ required by a bound in this
12 | where
13 |     F: for<'de> FnOnce(&'de [u8]) -> <Y as Yokeable<'de>>::Transformed,
   |                                      --------------------------------- required by this bound in `attach`
...
26 |     attach::<Cow<'static, [u8]>, _>(deserialize);
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected associated type, found enum `Cow`
   |
   = note: expected associated type `<Cow<'static, [u8]> as Yokeable<'_>>::Transformed`
                         found enum `Cow<'_, [u8]>`
   = help: consider constraining the associated type `<Cow<'static, [u8]> as Yokeable<'_>>::Transformed` to `Cow<'_, _>` or calling a method that returns `<Cow<'static, [u8]> as Yokeable<'_>>::Transformed`

This is a reduced version of my full testcase here.

The types are indeed the same, in the case of deserialize() they've literally been written out to be exactly the same, yet the compiler seems to have trouble. If I write out an actual meaningful body for deserialize() the body compiles just fine -- rustc is able to unify it there, but not when comparing Fn types

Even more confusing, I get a similar error when I swap out deserialize with |data| { unimplemented!() }, which is mystifying since the closure passed does not have a known Output type and yet the error is talking about unifying Cow<'_, [u8]> with the associated type. I feel like there's a bug involved here somewhere.

cc @eddyb @tmandry

[Manishearth]

This might be related to #84937

[tmandry]

I was literally talking to @eddyb about this problem the other day, so your timing and cc's are perfect.

My understanding is that we need to be able to express FnDef types as higher-ranked in the same way we do for function pointers (like for<'a> fn(&'a i32) -> &'a i32). The rest of the details are a bit fuzzy at the moment, but as I recall it would likely require us to handle binders that bind types, not just lifetimes.

[eddyb]

You definitely want to cc @nikomatsakis on this btw - I remember discussing my ideas around Ty::FnDef "flexible late-binding" before (something along the lines of all lifetimes are generic parameters and then the Ty::FnDef contains a for<'a> the_function::<'a> kind of binder to re-introduced higher-ranking/late-binding.

For for<T>, that's "type HRTB" (tho really for<const N: usize> is no different), and I believe actively worked on as part of GATs. @rust-lang/wg-traits likely knows more about that and when they might become available.

[jackh726]

Type/const HRTB is not being worked on as part of GATs; I'm not sure if there's any implementation for them at all.

[nikomatsakis]

That said, the work we're doing @jackh726 on normalizing under binders is pretty relevant to this.

[guswynn]

I have been working on something in the impedance crate, and I think I have hit a problem like this? simplified its: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=bbb3de13b6ecfcdf428cc6bda77bf9e2

I am trying to apply the same workaround as @Manishearth, but with a slightly different trait setup (I need to use a trait to be able to bind the closure's input lifetime to a generic type that the caller can choose, but gets to borrow from the input) and its not working, @Manishearth do you know more about this fn pointer workaround?

[Manishearth]

No idea

[jackh726]

This is fixed now, presumably by #85499. attach needs a Y: for<'de> Yokeable<'de> bound, but otherwise, this works

[Manishearth]

@jackh726 do you think it would be productive to add a regression test, or should we just close this issue?

[jackh726]

Yeah, I think we can probably just close it. There are a bunch of tests added in/after #85499 that probably cover this case.

[sffc]

Not quite fixed. Slightly more complicated case (playground):

trait MiniYokeable<'a> {
    type Output;
}

struct MiniYoke<Y: for<'a> MiniYokeable<'a>> {
    pub yokeable: Y,
}

fn map_project_broken<Y, P>(
    source: MiniYoke<Y>,
    f: impl for<'a> FnOnce(
        <Y as MiniYokeable<'a>>::Output,
        core::marker::PhantomData<&'a ()>,
    ) -> <P as MiniYokeable<'a>>::Output,
) -> MiniYoke<P>
where
    Y: for<'a> MiniYokeable<'a>,
    P: for<'a> MiniYokeable<'a>
{
    unimplemented!()
}

struct Bar<'a> {
    string_1: &'a str,
    string_2: &'a str,
}

impl<'a> MiniYokeable<'a> for Bar<'static> {
    type Output = Bar<'a>;
}

impl<'a> MiniYokeable<'a> for &'static str {
    type Output = &'a str;
}

fn demo_broken(bar: MiniYoke<Bar<'static>>) -> MiniYoke<&'static str> {
    map_project_broken(bar, |bar, _| bar.string_1)
}

Error message:

51 |     map_project_broken(bar, |bar, _| bar.string_1)
   |     ^^^^^^^^^^^^^^^^^^      --------------------- found signature of `for<'r> fn(Bar<'r>, PhantomData<&'r ()>) -> _`
   |     |
   |     expected signature of `for<'a> fn(<Bar<'_> as MiniYokeable<'a>>::Output, PhantomData<&'a ()>) -> _`

Note that the error is incorrect because <Bar<'_> as MiniYokeable<'a>>::Output is the same thing as Bar<'a>.

CC @Manishearth

Should this be a new issue?

[Manishearth]

cc @jackh726 thoughts?

[jackh726]

Please file a new issue and tag me

[Manishearth]

#89436