HRTB bounds not resolving correctly (take 2)

[Manishearth]

This is similar to the resolved issue #85636 , but details a newer iteration of that problem that has not yet been fixed.

Code example

trait MiniYokeable<'a> {
    type Output;
}

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

impl<Y> Clone for MiniYoke<Y>
where
    Y: for<'a> MiniYokeable<'a>,
    for<'a> <Y as MiniYokeable<'a>>::Output: Clone
{
    fn clone(&self) -> Self {
        todo!()
    }
}

trait MiniDataMarker {
    type Yokeable: for<'a> MiniYokeable<'a>;
}

trait MiniDataProvider<M>
where
    M: MiniDataMarker
{
    fn mini_load_payload(&self) -> MiniYoke<M::Yokeable>;
}

struct MiniStructProvider<M>
where
    M: MiniDataMarker,
{
    pub yoke: MiniYoke<M::Yokeable>,
}

impl<M> MiniDataProvider<M> for MiniStructProvider<M>
where
    M: MiniDataMarker,
    for<'a> <M::Yokeable as MiniYokeable<'a>>::Output: Clone,
{
    fn mini_load_payload(&self) -> MiniYoke<M::Yokeable> {
        self.yoke.clone()
    }
}

#[derive(Clone)]
struct SimpleStruct(pub u32);

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

impl MiniDataMarker for SimpleStruct {
    type Yokeable = SimpleStruct;
}

fn main() {
    let provider = MiniStructProvider {
        yoke: MiniYoke {
            yokeable: SimpleStruct(42)
        }
    };

    let yoke: MiniYoke<SimpleStruct> = provider.mini_load_payload();
    assert_eq!(yoke.yokeable.0, 42);
}

(playpen)

This fails to compile on beta/nightly (stable does not have #85499 so we cannot expect this to compile) with:

error[E0599]: the method `mini_load_payload` exists for struct `MiniStructProvider<_>`, but its trait bounds were not satisfied
  --> src/main.rs:65:49
   |
30 | / struct MiniStructProvider<M>
31 | | where
32 | |     M: MiniDataMarker,
33 | | {
34 | |     pub yoke: MiniYoke<M::Yokeable>,
35 | | }
   | | -
   | | |
   | |_method `mini_load_payload` not found for this
   |   doesn't satisfy `MiniStructProvider<_>: MiniDataProvider<_>`
...
65 |       let yoke: MiniYoke<SimpleStruct> = provider.mini_load_payload();
   |                                                   ^^^^^^^^^^^^^^^^^ method cannot be called on `MiniStructProvider<_>` due to unsatisfied trait bounds
   |
   = note: the following trait bounds were not satisfied:
           `<_ as MiniYokeable<'a>>::Output: Clone`
           which is required by `MiniStructProvider<_>: MiniDataProvider<_>`

The trait is implemented here: for<'a> <SimpleStruct as MiniYokeable>::Output is just SimpleStruct, which implements Clone.

cc @jackh726 @sffc

[jackh726]

Interestingly, if you change this to let provider: MiniStructProvider<SimpleStruct>, it works fine.

I think the problem here is we're unable to resolve what M on MiniStructProvider is for provider.

Theoretically, we can choose any M, as long as M::Yokeable == SimpleStruct. This might just be a diagnostics issue...

[jackh726]

I don't think we can make this code compile as-is. We need to pick a trait impl, and we can only do that if we know M. Technically, I suppose that we have an impl that applies to all M, but we still need to verify that M: MiniDataMarker (and you have to take into account specialization, for example).

[Manishearth]

Ah, so specifying the type as MiniStructProvider<SomeM> would work? @sffc, does this fix the original (unminimized) compilation issue?

[jackh726]

Yeah, that should work.

[Manishearth]

let provider = MiniStructProvider::<SimpleStruct> { does indeed fix the issue in the minimized thing.

I think we've tripped up against "diagnostics are terrible when you're relying on the inference of M::Foo not fully specifying M" before

[sffc]

Okay, so the suggest fix gets me further, but:

https://play.rust-lang.org/?version=beta&mode=debug&edition=2018&gist=ebbda5b15a398d648bdff9e439b27dc0

Snippet:

trait MiniDataProvider<M>
where
    M: MiniDataMarker
{
    fn mini_load_payload(&self) -> MiniDataPayload<M>;
}

impl<M> MiniDataProvider<M> for MiniStructProvider<M>
where
    M: MiniDataMarker,
    for<'a> <M::Yokeable as MiniYokeable<'a>>::Output: Clone,
{ ... }

let provider = MiniStructProvider { ... };
let payload: MiniDataPayload<SimpleStruct> = provider.mini_load_payload();

The compiler should figure out based on the type of payload that mini_load_payload() is the one from impl<M> MiniDataProvider<M> for MiniStructProvider<M>. However, I get the same error from the OP with this code (see updated playground link above).

However, it does work if I fully specify the trait:

// Works!
let payload = MiniDataProvider::<SimpleStruct>::mini_load_payload(&provider);

But, I cannot expect all the call sites to migrate to the fully-qualified trait function syntax. So, this is still a bug.

[Manishearth]

@sffc That seems somewhat expected: There could potentially be multiple impls of MiniDataProvider<T> on the same type -- in this case there is only one, but the types are complicated enough that it seems likely that inference will not be able to figure that out immediately.

[sffc]

@sffc That seems somewhat expected: There could potentially be multiple impls of MiniDataProvider<T> on the same type -- in this case there is only one, but the types are complicated enough that it seems likely that inference will not be able to figure that out immediately.

There is exactly one impl<T> MiniDataProvider<T> for a specific T, and the T is directly inferrable from the return type.

[Manishearth]

There is exactly one impl<T> MiniDataProvider<T> for a specific T,

That's not how inference sees this, though; it sees a complicated impl that it can't resolve without already knowing the concrete trait being dealt with.

To be clear, there are two issues here:

• A class of diagnostics enhancements around this kind of ambiguity (cc @estebank)
• A potential improvement to the inference engine around this kind of thing. This seems pretty challenging and I'd guess that it's unlikely to happen soon, though perhaps @jackh726 or @eddyb have a different idea since HRTB-heavy code will likely be hitting these same issues

Neither is an actual typesystem bug as originally reported.

[sffc]

I agree with everything you said.

To be clear, the bug in the inference engine really is a problem, as it blocks us (and others) from removing the "Wrap" workaround for #85636 as suggested in #85636 (comment) (see unicode-org/icu4x#1090).

I would like this ticket to focus on the inference bug.