Coherence and blanket impls interact in a suboptimal fashion with generic impls

[nikomatsakis]

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

[nikomatsakis]

Updated title to reflect @arielb1's point that this problem is not specific to cross-crate. Really, it has to do with the fact that current coherence rules are designed so that, when implementing Foo, we don't have to consider if this (indirectly) violates coherence for some other trait Bar. (In this case, Foo is FnMut and Bar is FnOnce).

[nikomatsakis]

Actually, that's not strictly true. This is somewhat specific to cross-crate, because within a crate, we can search through the existing impls, but in a cross-crate scenario, we want to avoid having to retest all of the downstream impls in light of the impls added in this new crate.

[glaebhoerl]

I think Fn arg/return types should be associated types, for what it's worth. Isn't this also important for inference? (In Haskell (lack of) inference can be rather painful with MPTCs...)

[reem]

I actually really like that Fn types take input parameters rather than having associated types. I think implementing Fn of different types for the same struct is actually very useful.

[glaebhoerl]

Why not move directly to unrestricted overloading then? Top-level fns of a given name can be thought of as Fn impls for a zero-sized struct with that name.

[aturon]

@glaebhoerl @reem

Why not move directly to unrestricted overloading then? Top-level fns of a given name can be thought of as Fn impls for a zero-sized struct with that name.

This is a pretty key point to me: while I recognize the power/utility of full-blown overloading, it would be very strange to have it only for closures.

But I also want to stress that the status of the types is explicitly not going to be nailed down at 1.0, and we should take our time deciding what kinds of additional overloading, if any, we want throughout Rust.

(@reem, it's worth keeping in mind that there are tradeoffs lurking here with type inference among other things, so it's not a straightforward question of "just" giving you extra power.)

[reem]

Well the thing is you already get full overloading since there isn't really anything special about the Fn family. It's just a matter of making it easy or making it require some perverse macro.

[aturon]

@reem

Well the thing is you already get full overloading since there isn't really anything special about the Fn family. It's just a matter of making it easy or making it require some perverse macro.

If you count what you can do with macros or weird encodings, the language already has a lot more features than advertised :-)

More seriously, there is something special about Fn: with the auto-tupling going on with Fn sugar, it looks like you're doing a perfectly normal invocation but behind the scenes could be overloading on the size/type of that tuple. The thing about macros is that they're marked, so you always know that you're working outside the normal confines of the language.

Again, I'm not saying this kind of overloading is bad or undesirable, just that the language design should be coherent.

[reem]

I agree with your concerns, but still lean on the side of enabling overloading. I think the most complex thing to deal with if we do enable overloading will be dealing with conflicting blanket implementations, for instance if I write this impl:

impl<F: Fn(X) -> Y> SomeTrait for F { ... }

I cannot also write this impl:

impl<F: Fn(X, Y) -> Z> SomeTrait for F { ... }

even though in practice they almost never conflict. As a result, we'd need negative trait bounds, and we'd need to put a lot of them (O(n^2) in the number of such impls).

[nikomatsakis]

I've been giving this a lot of thought. I no longer believe that the args/ret-types of the fn traits should be associated types. The reason is that having them as associated types is a problem in higher-ranked situations, since in that case the lifetime must be specified by the caller. Consider an example like Fn(&int) -> int:

impl<'a> Fn for SomeType {
    type Arg = (&'a int,);
    type Ret = int;
    ...
}

Here, the parameter 'a is in violation of the rules from rust-lang/rfcs#447. This is because, basically, it is not actually an output of the impl, but an input. Trying to make this work causes all manner of problems in the associated types impl (believe me, I know).

Note that we could make 'a an input by having it appear on the input type:

impl<'a> Fn for SomeType<'a> { .. }

But now, for any given instance of SomeType, it can only be called with some particular 'a. To do otherwise, we'd need higher-ranked references to structures. This is certainly thinkable but I don't want to think it right now.

I'm busy right now so I'll stop this here. Obviously we'll have to address this issue, I have some thoughts on how to do it but I want to work them out a bit (short version is to have coherence be more liberal).