`rustc` fails to see a bound that is present, but also requires that the bound not be present

[Twey]

In certain cases, rustc will emit an error message on what appears to be valid code, claiming that

• a bound that is present is not present, and must be present
• but the bound is present and must not be present

Here is a MWE (or playground):

trait Foo<T> { type Quux; }
trait Bar<B> {
    type Baz;
    fn arthur() where B: Foo<Self::Baz>, B::Quux: Send;
}
impl<B> Bar<B> for () {
    type Baz = ();
    fn arthur() where B: Foo<()>, B::Quux: Send { }
}

This produces the pair of errors:

rustc 1.16.0 (30cf806ef 2017-03-10)
error[E0277]: the trait bound `B: Foo<()>` is not satisfied
 --> <anon>:8:5
  |
8 |     fn arthur() where B: Foo<()>, B::Quux: Send { }
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `Foo<()>` is not implemented for `B`
  |
  = help: consider adding a `where B: Foo<()>` bound

error[E0276]: impl has stricter requirements than trait
 --> <anon>:8:5
  |
4 |     fn arthur() where B: Foo<Self::Baz>, B::Quux: Send;
  |     --------------------------------------------------- definition of `arthur` from trait
...
8 |     fn arthur() where B: Foo<()>, B::Quux: Send { }
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ impl has extra requirement `B: Foo<()>`

error: aborting due to 2 previous errors

[Twey]

It's interesting to note that the bound B::Quux: Send is an integral part of this MWE: removing it bypasses the error.

[lcnr]

afaict this is caused by our current approach to param env normalization, see

rust/compiler/rustc_trait_selection/src/traits/mod.rs

Lines 328 to 345 in c225c45

	// HACK: we are trying to normalize the param-env inside *itself*. The problem is that
	// normalization expects its param-env to be already normalized, which means we have
	// a circularity.
	//
	// The way we handle this is by normalizing the param-env inside an unnormalized version
	// of the param-env, which means that if the param-env contains unnormalized projections,
	// we'll have some normalization failures. This is unfortunate.
	//
	// Lazy normalization would basically handle this by treating just the
	// normalizing-a-trait-ref-requires-itself cycles as evaluation failures.
	//
	// Inferred outlives bounds can create a lot of `TypeOutlives` predicates for associated
	// types, so to make the situation less bad, we normalize all the predicates *but*
	// the `TypeOutlives` predicates first inside the unnormalized parameter environment, and
	// then we normalize the `TypeOutlives` bounds inside the normalized parameter environment.
	//
	// This works fairly well because trait matching does not actually care about param-env
	// TypeOutlives predicates - these are normally used by regionck.

fixed in the new solver because we defer projection equality there, so the unnormalized B: Foo<Self::Baz> candidate now applies to the B: Foo<()> goal.