Repository: rust
Issue: Coherence and blanket impls interact in a suboptimal fashion with generic impls
Labels: A-type-system,C-enhancement,T-lang,T-types

There is a tricky scenario with coherence rules and blanket impls of traits. This manifested as #18835, which is an inability to implement `FnOnce` manually for generic types. It turns out to be a legitimate coherence violation, at least according to the current rules (in other words, the problem is not specific to `FnOnce`, but rather an undesired interaction between blanket impls (like those used in the fn trait inheritance hierarchy) and coherence. I am not sure of the best fix, though negative where clauses would provide one possible solution. Changing the `Fn` type parameters to associated types, which arguably they ought to be, would also solve the problem.

Let me explain what happens. There is a blanket impl of `FnOnce` for all things that implement `FnMut`:

```
impl<A,R,F:FnMut<A,R>> FnOnce<A,R> for F { ... }
```

Now imagine someone tries to implement `FnOnce` in a generic way:

```
struct Thunk<R> { value: R }
impl<R> FnOnce<(),R> for Thunk<R> {
    fn call_once(self) -> R { self.value }
}
```

If you try this, you wind up with a coherence violation. The coherence checker is concerned because it is possible that someone from another crate comes along implements `FnMut` for `Thunk` as well:

```
struct SomeSpecificType;
impl FnMut<(),SomeSpecificType> for Thunk<SomeSpecificType> { ... }
```

This impl passes the orphan check because `SomeSpecificType` is local to the current crate. Now there is a coherence problem with respect to `FnOnce` for `Thunk<SomeSpecificType>` -- do use the impl that delegates to `FnMut`, or the direct impl?

If the `A` and `R` arguments to the `Fn` traits were associated types, there would be no issue, because the second impl would be illegal -- the `Fn` traits could only be implemented within the same crate as the main type itself.

If we had negative where clauses, one could write the manual `FnOnce` impl using a negative where clause:

```
struct Thunk<R> { value: R }
impl<R> FnOnce<(),R> for Thunk<R>
    where Thunk<R> : !FnMut<(),R> // imaginary syntax
{
    fn call_once(self) -> R { self.value }
}
```

This is _basically_ specialization: we implement `FnOnce`, so long as nobody has implemented `FnMut`, in which case that version wins. This is not necessarily what the author wanted to write, it's just something that would be possible.

There is also the (somewhat weird) possibility that one could write a negative where clause on the original blanket impl, kind of trying to say "you can implement FnOnce in terms of FnMut, but only if FnOnce is not implemented already". But if you think about it for a bit this is (a) basically a weird ad-hoc kind of specialization and (b) sort of a logical contradiction. I think the current logic, if naively extended with negative where clauses, would essentially reject that sort of impl, because the negative where clause doesn't hold (FnOnce _is_ implemented, by that same impl).

Note that we don't have to solve this for 1.0 because direct impls of the `Fn` traits are going to be behind a feature gate (per #18875).

cc @aturon