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).

[glaebhoerl]

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.

By this do you mean for<'a> &SomeType<'a>? (Or maybe for<'b, 'a: 'b> &'b SomeType<'a>?) But why do references enter into it - even for<'a> SomeType<'a> seems like it should be possible? Why are higher-ranked lifetimes with structs significantly harder than with fns and traits? (Superficially, it feels to me like higher-ranked traits, which we already have, should be the trickier case - but of course I didn't write the typechecker.)

[ghost]

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.

@reem I believe you could emulate this pattern by having a phantom parameter to the struct (just abstract over it when you don't care). You'd retain the flexibility while having the better type inference characteristics of associated types.

[bombless]

Glad I found this issue...seems that problem still exists.

#![feature(unboxed_closures)]
struct Foo<Ret> (Ret);
impl<T> FnMut()->T for Foo<T> {
    extern "rust-call" fn call_mut(&mut self, _: ())->T { self.0 }
}
fn main() {}

error: conflicting implementations for trait core::ops::FnMut [E0119]

[bombless]

How about fix this coherence problem by unifying Fn/FnOnce/FnMut using associated types?
Here's basic idea:

struct Counter(u64);
impl Counter { fn new()->Counter { Counter(0) } }
impl Callbale<(), u64> for Counter {
    type SelfType = &mut Counter;
    fn call(this: &mut Counter, _: ())->u64{
        this.0 = this.0 + 1;
        this.0
    }
}

That said, we use static method of Fn/FnOnce/FnMut to implement them, passing self as normal parameter.

The downside of this idea is that now you can only choose to impl one of them for one type when parameter type is the same.

[steveklabnik]

Triage: still seems relevant, even though a lot of details have changed since the original discussion was happening, as those were more details about the Fn traits than the underlying type system issue.

I agree with @nikomatsakis that this feels like an older #30191 (comment)

[nikomatsakis]

I closed #30191 as a dup of this issue. I wanted to reproduce a lightly edited version of the salient comments for posterity:

---

@arielb1 wrote this example, which was intended to demonstrate where the overlap rules were being too strict:

struct Row;

pub trait FromSql<A> {}

pub trait FromSqlRow<A> {
    fn foo(&self);
}

impl<ST, T> FromSqlRow<ST> for T where
    T: FromSql<ST>,
{
    fn foo(&self) {}
}

struct User;

impl<ST> FromSqlRow<ST> for User where
    (i32, String): FromSqlRow<ST>
{
    fn foo(&self) {}
}

fn main() {}

but as he and I later concluded, the orphan check is doing the right thing here. The danger is that a downstream crate might do something like:

struct Foo;
impl FromSql<Foo> for User { }

which they are legally able to do, for better or worse.

One solution here would be to adopt one of the negative impl proposals (such as what I describe in this gist]) that would permit impl<T> !FromSql<T> for User, which presumably coherence could then make use of.

[Rufflewind]

The danger is that a downstream crate might do something like:

struct Foo;
impl FromSql<Foo> for User { }

Maybe it's the downstream crate that should be blamed by the coherence checker? At that point both the blanket and the generic impls should be visible.

[cramertj]

Any update on this?

Basic pattern:

trait A<P> {}
trait B<P> {}

impl<P> B<P> for i32 {}

impl<P, T: A<P>> B<P> for T {}

Seems like it could be resolved by just banning simultaneous impls of A<P> and B<P> in the downstream crate, no?

[nikomatsakis]

No update, other than the fact that we've been slowly making progress towards a more canonical way of representing coherence and the Rust trait system, and it may help us feel comfortable with selecting a solution.

Seems like it could be resolved by just banning simultaneous impls of A

and B

in the downstream crate, no?

Potentially yes but this is not such a minor thing. Among other things, it implies a much more complex coherence check, since now an impl of A can directly interfere with an impl of B. It's also a subtle case of negative logic: by adding these impls, we are effectively declaring that A and B are mutually exclusive. I'd prefer to surface that logic more explicitly.

[cramertj]

@nikomatsakis Why is this so different from the non-parametric versions of the traits (which are allowed)? This compiles:

trait A {}
trait B {}
impl B for i32 {}
impl<T: A> B for T {}

W.R.T. the original example: you said "an impl of A can directly interfere with an impl of B." How is this not also true for the non-parametric versions above?

[nikomatsakis]

@cramertj because the only crate that could implement A for i32 is the crate that defined the trait, and it did not do so. This limited use of negative reasoning is described in RFC 1023.

[cramertj]

Edit: Disregard what this comment used to say.

So if I understand correctly, it's just that this particular instance of negative reasoning was allowed, but the relevant RFC didn't allow negative reasoning to be extended to traits that are parametric in this way.

[nikomatsakis]

@cramertj one might view it that way. The difference is that in the simpler, non-generic case, the local crate can verify that no impls of A exist for i32 -- and in particular, for such an impl to exist, it would have to be added in this crate.

In the generic case, we can validate that no impls exist that the crate can see, but there may be other impls added in downstream crates. This implies that downstream crates would have to do their own checking as well on our behalf, and this is what we wanted to avoid.

[cramertj]

@nikomatsakis That makes sense. Thank you for the explanation.

[Marwes]

Ran into the exact case in #19032 (comment) . Got some unparameterised traits which rely on blanket impls like that but would like to generalize them to take a parameter which is not possible as it is currently :(.

[dhardy]

Related: #22865, #48869.

Note also that we already have a case where coherence checks using blanket impls are pushed downstream, e.g.

struct S; impl From<S> for S {}

fails downstream while impl<T> From<T> for T { .. } is allowed upstream (special case?).