Regression in trait bounds that are redundant with associated type's HRTB

[rozbb]

The title is a mouthful, so let me explain and give some motivation. Say I have a trait MyTrait with an associated type MessageType. This message type must be deserializable (in the serde sense), i.e., MessageType: for<'a> Deserialize<'a>. Now suppose I have a generic struct GenericStruct<T> where T: MyTrait. I want the struct to contain a message, so I put a thing of type T::MessageType inside the struct. I would like GenericStruct to also be Deserializeable now, so I #[derive(Deserialize)].

Concretely, the code

use serde::Deserialize;

//trait DeserializeOwned: for<'a> Deserialize<'a> {}

trait MyTrait {
    type MessageType: Sized + for<'a> Deserialize<'a>;
    //type MessageType: Sized + DeserializeOwned;
}

#[derive(Deserialize)]
struct GenericStruct<T: MyTrait>(T::MessageType);

compiles in 1.31.1-stable and fails in 1.33.0-nightly with error message

error[E0308]: mismatched types
  |
  | #[derive(Deserialize)]
  |          ^^^^^^^^^^^ one type is more general than the other
  |
  = note: expected type `for<'a> _IMPL_DESERIALIZE_FOR_GenericStruct::_serde::Deserialize<'a>`
             found type `_IMPL_DESERIALIZE_FOR_GenericStruct::_serde::Deserialize<'de>`

Furthermore, if the commented lines are uncommented, and the first type line in MyTrait is commented out, the code now compiles in stable and nightly.

I don't believe this is version-specific behavior in serde. I would like to make a neater minimal testcase, but I don't know of any auto-derivable traits that only take a lifetime as a parameter.

[stephaneyfx]

I think this is a minimal reproduction example. It compiles on stable (1.31.1) but not on nightly. Playground

trait Foo<'a> {}

trait Bar {
    type Item: for<'a> Foo<'a>;
}

fn foo<'a, T>(_: T)
where
    T: Bar,
    T::Item: Foo<'a>
{}

[dtolnay]

Changed the title because this is not specific to custom derives. The characteristic behavior seems to be a trait bound T::Item: Foo<'a> that is redundant with a HRTB on the same associated type, Item: for<'a> Foo<'a>.

[dtolnay]

Mentioning @nikomatsakis and @scalexm because this seems likely to do with universes.

[pnkfelix]

triage: P-high,assigning to @nikomatsakis

[nikomatsakis]

OK, I did some digging into this. I'm not sure yet what I think is the correct fix.

The problem begins when we are asked to prove

for<'x> T::Item: Foo<'x>

I think we are asked to prove this because we are trying to prove that T::Item: Foo<'a> is well-formed, and the criteria for that include the where-clauses from the trait. I don't really think we should be proving that per se, but it's kind of an orthogonal question (maybe).

Here we have two choices. We can use the where clause T::Item: Foo<'a>, or we can use the rule we get from the trait for<'x> T::Item: Foo<'x>. In the older system, we would have rejected the where-clause earlier, because it's insufficiently general, but under the newer system we defer that, and we think we have two good choices. Next, we run up against one of the arbitrary preference that the trait solver has for where-clauses, so we wind up picking T::Item: Foo<'a>. This puts us in the position of trying to prove that for<'x> 'a = 'x, which of course isn't true.

Now, in the universe PR I kind of took a maximally simplistic view of higher-ranked unification errors, deferring detection as long as possible. This was in part to give us room to get smarter. It seems like that may have too strong. I think we could add some logic here that allows us to reject the where-clause, though I'd have to look to find the best spot.

@rozbb @dtolnay -- one question I have: how severe is this regression? it's hard for me to tell whether this affects one particular pattern, or something that is very common (I would've expected the latter to show up in the crater runs, but maybe not)

[dtolnay]

I don't know of this being a common pattern.

It is startling to me that in @rozbb's code if you replace for<'de> Deserialize<'de> with DeserializeOwned then it compiles. We have T: for<'de> Deserialize<'de> if and only if T: DeserializeOwned, so ideally both of those would compile or neither would compile, or there is some way for us to articulate how for<'de> Deserialize<'de> and DeserializeOwned are different so that users can work around this type of failure.

In the minimal repro:

trait Foo<'a> {}

trait FooAll: for<'a> Foo<'a> {}
impl<T: ?Sized> FooAll for T where T: for<'a> Foo<'a> {}

trait Bar {
    type Item: FooAll;
}

fn foo<'a, T>(_: T)
where
    T: Bar,
    T::Item: Foo<'a>
{}

[nikomatsakis]

I mean it's definitely a shortcoming of the trait solver, so it's hard to "explain" the behavior. I'm mostly trying to judge how quickly to try and hack up a fix, not whether to do so.

[nikomatsakis]

I've been thinking about to handle region solving in any case, and I think some of the changes I have in mind would help here.

[dtolnay]

Makes sense! If it didn't appear in crater, and there isn't an easy fix, it seems fine to postpone until the trait solver is better prepared to support this case.

[pnkfelix]

triage Q for @nikomatsakis : how should I interpret the recent comments between you and @dtolnay ? Is the idea that we do not need a fix tomorrow, but would instead aim for a deadline like ... well, I just noticed that the bug has already leaked out to beta. So we want to find a backportable fix before the train hits stable?

[nikomatsakis]

@pnkfelix I am not sure yet. I haven't really had time to try and tinker with a fix, though I have some strategies in mind. I guess it would be good to prevent this regression from leaking out though. So, yes, let's say that a goal is to get a fix before the Rust 1.33 release on Thu Feb 28 2019. On a shorter time frame, I aim to have some notes and/or experiments here before the next compiler meeting. =)

[pnkfelix]

Visiting for triage; @nikomatsakis How realistic is it to think that you might get around to this, with a beta-backportable fix, in the next two weeks (i.e. before the deadline you established in the previous comment)?

[nikomatsakis]

I'm working with @aturon and other members of @rust-lang/wg-traits on exploring this issue. We did our first call yesterday talking over the details (recording available here) and we have to schedule a follow-up call to keep working on it. Don't yet know the best fix but I think it's still plausible we can have one.

[nikomatsakis]

Assigning @aturon as well as myself.