Spurious (?) "trait bound not satisfied" with associated type constructors

[SimonSapin]

I’m using the technique mentioned at https://github.com/rust-lang/rfcs/pull/1598/files/8e922c0cede49b0b07ac6fcf29ea736aab29acb9#r68995241 and used at https://github.com/nikomatsakis/nll/blob/master/graph-algorithms/src/lib.rs to have in a trait an associated type constructor that takes a lifetime parameter.

rustc 1.12.0-nightly (7ad125c 2016-07-11)

pub trait TypeConstructor<'a> {
    type BorrowedNamespace;
}

pub trait SelectorImpl
where Self: for<'a> TypeConstructor<'a> {
    // These two definitions should be equivalent (for `ExampleImpl`), but only the latter compiles.
    type Namespace: PartialEq + for<'a> PartialEq<<Self as TypeConstructor<'a>>::BorrowedNamespace>;
//  type Namespace: PartialEq + for<'a> PartialEq<&'a str>;

    // For illustration:
    fn get_namespace<'a>(&'a self) -> <Self as TypeConstructor<'a>>::BorrowedNamespace;
}


pub struct ExampleImpl;

impl<'a> TypeConstructor<'a> for ExampleImpl {
    type BorrowedNamespace = &'a str;
}

impl SelectorImpl for ExampleImpl {
    type Namespace = String;

    fn get_namespace<'a>(&'a self) -> &'a str { unimplemented!() }
}

error: the trait bound `for<'a> std::string::String: std::cmp::PartialEq<<ExampleImpl as TypeConstructor<'a>>::BorrowedNamespace>` is not satisfied [--explain E0277]
  --> a.rs:22:6
   |>
22 |> impl SelectorImpl for ExampleImpl {
   |>      ^^^^^^^^^^^^
help: the following implementations were found:
help:   <std::string::String as std::cmp::PartialEq>
help:   <std::string::String as std::cmp::PartialEq<str>>
help:   <std::string::String as std::cmp::PartialEq<&'a str>>
help:   <std::string::String as std::cmp::PartialEq<std::borrow::Cow<'a, str>>>
note: required by `SelectorImpl`

error: aborting due to previous error

Since<ExampleImpl as TypeConstructor<'a>>::BorrowedNamespace is &'a str for any 'a, I believe the bound for<'a> std::string::String: std::cmp::PartialEq<<ExampleImpl as TypeConstructor<'a>>::BorrowedNamespace> is equivalent to for<'a> std::string::String: std::cmp::PartialEq<&'a str>, which is the third bound that was found.

[eddyb]

I believe this is #30472, although I'm not sure that is the canonical version, and that @soltanmm and @nikomatsakis have been pushing for "lazy normalization" to solve this.

[steveklabnik]

Triage: different error today

error[E0277]: can't compare `std::string::String` with `<ExampleImpl as TypeConstructor<'a>>::BorrowedNamespace`
  --> src/lib.rs:23:5
   |
8  |     type Namespace: PartialEq + for<'a> PartialEq<<Self as TypeConstructor<'a>>::BorrowedNamespace>;
   |          --------- associated type defined here
...
22 | impl SelectorImpl for ExampleImpl {
   | --------------------------------- in this `impl` item
23 |     type Namespace = String;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^ no implementation for `std::string::String == <ExampleImpl as TypeConstructor<'a>>::BorrowedNamespace`
   |
   = help: the trait `for<'a> std::cmp::PartialEq<<ExampleImpl as TypeConstructor<'a>>::BorrowedNamespace>` is not implemented for `std::string::String`

error: aborting due to previous error

[fmease]

Triage: It now compiles. We might want to add a test before closing it.