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.

[sffc]

Note the error message:

error[E0599]: the method `mini_load_payload` exists for struct `MiniStructProvider<_>`, but its trait bounds were not satisfied

So, the compiler knows that the impl exists, and it wants to use it, but it can't because it thinks there are unsatisfied trait bounds.

[Manishearth]

Yeah the diagnostics are definitely wrong here (we should perhaps file separate bugs for them -- both the one in the initial issue and the one in your updated code), but from talking to @eddyb it seems unlikely that the inference here can be improved any time soon, it's coming from a pretty important assumption in the inference engine.

What's actually happening here is that the compiler is bailing on inference because it's not sure that it's solvable and is tripping a heuristic used to avoid infinite recursion in the inference engine. The wrapper hack works because this heuristic applies to cases where _: Trait is being determined, but not for Foo<_>: Trait where the recursion is somewhat limited.

[Manishearth]

Filed a diagnostic issue: #89418

[eddyb]

I think the reduction is not complete. What you want is this:

let payload: MiniDataPayload<SimpleStruct> = MiniDataProvider::<_>::mini_load_payload(&provider);

Basically the method call version tries this and fails it. If you actually call the method, but ask for the types to be inferred, you get more information:

error[E0277]: the trait bound `for<'a> <_ as MiniYokeable<'a>>::Output: Clone` is not satisfied

This is why the wrapper hack works, it avoids hitting the "_: Trait is always ambiguous" rule.

If the bound on the impl that contains mini_load_payload is changed to this, "everything" compiles (well, except clone isn't callable by mini_load_payload - so only the caller of mini_load_payload is unbroken):

<M::Yokeable as MiniYokeable<'static>>::Output: Clone

(check out on playground)

So I believe what happens is:

1. M::Yokeable cannot normalize because M isn't known (yet)
2. <M::Yokeable as MiniYokeable<'a>>::Output fails to normalize because 'a is bound
   • but with 'static it seems to normalize without knowing M::Yokeable? this must be where "only one impl of MiniYokeable exists" comes into its own
3. you're left with for<'a> <_ as MiniYokeable<'a>>::Output: Clone which is stuck because _: MiniYokeable<'a> itself is "always ambiguous"

What's interesting is that this can fail early even if M is provided later (through the return type).

For method calls, I can understand why (since M won't be known until after the method has been chosen). We may want to commit to a method call, if we have only one candidate, even if the bounds don't seem to apply, as long as it's because they're "still ambiguous".

But for MiniDataProvider::<_>::mini_load_payload, why wouldn't M::Yokeable be normalized, after M is inferred from the expected type? I feel like we're generating a $123 = M::Yokeable obligation and then replace the original bound with this obligation:

for<'a> <$123 as MiniYokeable<'a>>::Output: Clone

Somehow, this fails (presumably after inference is complete). Do we not try hard enough to resolve inference variables that came from replacing a not-yet-resolved projection, before giving up?

[eddyb]

Reconstructed the scenario I was guessing at (then further reduced it, because it turns out M::Yokeable is a red herring), and it reproduces (try on playground):

trait Trait<'a> {
    type Out;
}

impl<'a, T> Trait<'a> for T {
    type Out = T;
}

fn weird_bound<X>() -> X
    where
        for<'a> X: Trait<'a>,
        for<'a> <X as Trait<'a>>::Out: Copy
{ todo!() }

fn main() {
    let _: () = weird_bound();
}

@jackh726 ^^ hopefully this is more useful. Zero method calls, just failing to propagate X = () into the for<'a> <X as Trait<'a>>:Out: Copy bound after it was instantiated.

If I had to guess, it's failing to check if an inference variable was resolved before giving up somewhere.

[jackh726]

Yeah, I think this is falling into a class of bugs that I've been running into a lot recently.

Basically, the general idea is that when we make a method call, we assign new inference vars as generics. We then add the required obligations, and try to normalize them. At this point, normalization fails because we have an inference variable as a Self type. And we also have late-bound vars in the projection, so we can't return a new inference var + obligation. This basically causes us to topple.

The only thing that might work here as an "easy" solution is to try to delay normalization the required obligations until after we've done the expected type checking part (which means we'll have more into about the inference var, supposedly).

Other than that, I think we're just back at the limit of what we can handle with late-bound vars in projections. And this might just have to wait until lazy norm.

[fee1-dead]

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

I have an example where even if you specify an explicit type, it does not resolve correctly: (play)

Code

struct E<A, B> {
    a: A,
    b: B,
}

struct S;

impl S {
    fn e<A, B>(&self, a: A, b: B)
        where Self: R<E<A, B>>
    {}
}

trait R<A> {}

impl<A> R<A> for S where A: Tr {}

trait Tr {}
trait HasItem {
    type Item;
}
impl<T: IntoIterator> HasItem for T {
    type Item = T::Item;
}
impl<T> HasItem for [T] {
    type Item = T;
}

impl<A, B> Tr for E<A, B>
where
    A: AsRef<[u8]>,
    B: HasItem,
    <B as HasItem>::Item: AsRef<[u8]>,
    for<'a> &'a B: IntoIterator<Item = &'a <B as HasItem>::Item>,
    for<'a> <&'a B as IntoIterator>::IntoIter: Clone,
{
}

const ST: &str = "";
const V: Vec<u8> = Vec::new();

fn main() {
    let arr: [Vec<u8>; 1] = [V];
    S.e(ST, arr);
}

Failure:

error[E0277]: the trait bound `for<'a> <&'a _ as IntoIterator>::IntoIter: Clone` is not satisfied
  --> src/main.rs:44:7
   |
44 |     S.e(ST, arr);
   |       ^ the trait `for<'a> Clone` is not implemented for `<&'a _ as IntoIterator>::IntoIter`
   |
   = help: the following implementations were found:
             <&T as Clone>
note: required because of the requirements on the impl of `Tr` for `E<_, _>`
  --> src/main.rs:29:12
   |
29 | impl<A, B> Tr for E<A, B>
   |            ^^     ^^^^^^^
note: required because of the requirements on the impl of `R<E<_, _>>` for `S`
  --> src/main.rs:16:9
   |
16 | impl<A> R<A> for S where A: Tr {}
   |         ^^^^     ^

For more information about this error, try `rustc --explain E0277`.
error: could not compile `playground` due to previous error

[Manishearth]

More errors of this kind: #90638

[estebank]

Current output:

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>
   | ----------------------------
   | |      |
   | |      method `mini_load_payload` not found for this struct
   | 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: trait bound `<_ as MiniYokeable<'a>>::Output: Clone` was not satisfied
  --> src/main.rs:40:56
   |
37 | impl<M> MiniDataProvider<M> for MiniStructProvider<M>
   |         -------------------     ---------------------
...
40 |     for<'a> <M::Yokeable as MiniYokeable<'a>>::Output: Clone,
   |                                                        ^^^^^ unsatisfied trait bound introduced here