{"action":"created","issue":{"url":"https://api.github.com/repos/rust-lang/rfcs/issues/586","labels_url":"https://api.github.com/repos/rust-lang/rfcs/issues/586/labels{/name}","comments_url":"https://api.github.com/repos/rust-lang/rfcs/issues/586/comments","events_url":"https://api.github.com/repos/rust-lang/rfcs/issues/586/events","html_url":"https://github.com/rust-lang/rfcs/pull/586","id":54373812,"number":586,"title":"Negative bounds","user":{"login":"kennytm","id":103023,"avatar_url":"https://avatars.githubusercontent.com/u/103023?v=3","gravatar_id":"","url":"https://api.github.com/users/kennytm","html_url":"https://github.com/kennytm","followers_url":"https://api.github.com/users/kennytm/followers","following_url":"https://api.github.com/users/kennytm/following{/other_user}","gists_url":"https://api.github.com/users/kennytm/gists{/gist_id}","starred_url":"https://api.github.com/users/kennytm/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kennytm/subscriptions","organizations_url":"https://api.github.com/users/kennytm/orgs","repos_url":"https://api.github.com/users/kennytm/repos","events_url":"https://api.github.com/users/kennytm/events{/privacy}","received_events_url":"https://api.github.com/users/kennytm/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":{"login":"nikomatsakis","id":155238,"avatar_url":"https://avatars.githubusercontent.com/u/155238?v=3","gravatar_id":"","url":"https://api.github.com/users/nikomatsakis","html_url":"https://github.com/nikomatsakis","followers_url":"https://api.github.com/users/nikomatsakis/followers","following_url":"https://api.github.com/users/nikomatsakis/following{/other_user}","gists_url":"https://api.github.com/users/nikomatsakis/gists{/gist_id}","starred_url":"https://api.github.com/users/nikomatsakis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nikomatsakis/subscriptions","organizations_url":"https://api.github.com/users/nikomatsakis/orgs","repos_url":"https://api.github.com/users/nikomatsakis/repos","events_url":"https://api.github.com/users/nikomatsakis/events{/privacy}","received_events_url":"https://api.github.com/users/nikomatsakis/received_events","type":"User","site_admin":false},"milestone":null,"comments":16,"created_at":"2015-01-14T20:42:20Z","updated_at":"2015-02-04T00:50:52Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/rust-lang/rfcs/pulls/586","html_url":"https://github.com/rust-lang/rfcs/pull/586","diff_url":"https://github.com/rust-lang/rfcs/pull/586.diff","patch_url":"https://github.com/rust-lang/rfcs/pull/586.patch"},"body":"Executive summary:\r\n\r\n```rust\r\nimpl<T: Int + !Float> Average for T { ... }\r\nimpl<T: Float + !Int> Average for T { ... }\r\nimpl<T: Int + Float> Average for T { ... }\r\n```\r\n\r\n[Rendered](https://github.com/kennytm/rfcs/blob/neg-bounds/text/0000-negative-bounds.md)\r\n\r\ncc #442, #290, rust-lang/rust#19032."},"comment":{"url":"https://api.github.com/repos/rust-lang/rfcs/issues/comments/72769171","html_url":"https://github.com/rust-lang/rfcs/pull/586#issuecomment-72769171","issue_url":"https://api.github.com/repos/rust-lang/rfcs/issues/586","id":72769171,"user":{"login":"nikomatsakis","id":155238,"avatar_url":"https://avatars.githubusercontent.com/u/155238?v=3","gravatar_id":"","url":"https://api.github.com/users/nikomatsakis","html_url":"https://github.com/nikomatsakis","followers_url":"https://api.github.com/users/nikomatsakis/followers","following_url":"https://api.github.com/users/nikomatsakis/following{/other_user}","gists_url":"https://api.github.com/users/nikomatsakis/gists{/gist_id}","starred_url":"https://api.github.com/users/nikomatsakis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nikomatsakis/subscriptions","organizations_url":"https://api.github.com/users/nikomatsakis/orgs","repos_url":"https://api.github.com/users/nikomatsakis/repos","events_url":"https://api.github.com/users/nikomatsakis/events{/privacy}","received_events_url":"https://api.github.com/users/nikomatsakis/received_events","type":"User","site_admin":false},"created_at":"2015-02-04T00:50:52Z","updated_at":"2015-02-04T00:50:52Z","body":"So I spent some time reading the RFC yesterday and thinking about it. What is written makes a lot of sense, but there are a lot of issues that I think arise that must be thought through. Also, I had some interest in pursuing negative bounds as a solution to https://github.com/rust-lang/rust/issues/18835, but I am now not sure that they will help there (see below). All in all I feel like this is a fairly non-trivial extension to the trait system that I do not want to rush into. (I've thought otherwise in the past. After all, there are parts of the trait system -- in particular some aspects of coherence -- that rely on the ability to decide that a trait is definitively not implemented, so in some sense we have negative bounds already, but in thinking about it more I've decided that adding negative bounds as a first-class thing opens a lot of new questions.)\r\n\r\nHere are some (preliminary) thoughts:\r\n\r\n#### Negative bounds as the way to do specialization\r\n\r\nIt's clear that negative bounds potentially enable a certain amount of specialization. However, I don't consider them a full solution, because they leave a number of important use cases unaddressed. The RFC mentions some of these concerns. The biggest concern is cross-crate specialization: I'd like to be able to define blankets in one crate and specialize them in others. There are also ergonomic concerns. Finally, specialization might allow us to enforce additional interesting constraints, like saying that all specializations of a \"base impl\" have consistent values for associated types (this relates to the next section). \r\n\r\n#### Interactions with the current implementation\r\n\r\nCurrently when resolving a trait obligation in the type checker, we always ensure that we can pick a specific impl. This makes sense because the impl defines the output type parameter definitions. It also makes sense because, not infrequently, some of the *input* type parameters are also being inferred, so narrowing down to a particular impl lets us know the values of those type parameters as well (we infer this based on the set of impls that are in scope). After type-checking is done, the precise set of impl type parameters are known. Thanks to coherence, this is enough to guarantee that later, when generating code, we can replay that search and always end up with the same impl (even when inlined into downstream crates).\r\n\r\nUsing negative bounds will not necessarily interact smoothly with this kind of specialization. To adapt an example from the RFC, imagine that we have:\r\n\r\n```rust\r\ntrait Foo { type Output; fn foo(&self) -> Self::Output; }\r\nimpl<T:Int+!Float> Foo for T { type Output = i32; ... }\r\nimpl<T:Float> Foo for T { type Output = f32; ... }\r\n```\r\n\r\nNow imagine I have a function:\r\n\r\n```rust\r\nfn call_foo<T:Int>(t: T) { t.foo() }\r\n```\r\n\r\nIf we adapt the code in a kind of straight-forward way, the function `call_foo` will yield an ambiguity error, because the compiler won't be able to decide between those two impls. After all, it doesn't know that `Float` is implemented or not. You could work around this like so:\r\n\r\n```rust\r\nfn call_foo<T:Int+Foo>(t: T) { t.foo() }\r\n```\r\n\r\nAt least as currently implemented, this would cause `Foo` to be resolved to the where clause instead of a concrete impl. This may seem like a silly distinction, but it's important for associated type resolution. `T::Output` in this case would normalize to `T::Output` -- or one could write `T:Int+Foo<Output=i32>` to manually specify the result.\r\n\r\nAnother option would be to specify enough bounds to narrow down to one impl:\r\n\r\n```rust\r\nfn call_foo<T:Int+!Float>(t: T) { t.foo() }\r\n```\r\n\r\n#### Impact on `Fn` vs `FnMut` etc\r\n\r\nMy main motivation for pursuing something like negative trait bounds sooner rather than later is to attempt to resolve rust-lang/rust#18835. However, in working through this RFC, I came to the conclusion that negative trait bounds don't actually help there in particular. For reference, the problem is roughly that the bridging impls that interconvert from `Fn` to `FnMut` and so forth create coherence conflicts with many manual impls of the `Fn` traits. (As explained in rust-lang/rust#19032, the problem is not really specific to the `Fn` traits, but they happen to be a relatively urgent manifestation of it.)\r\n\r\n**The problem.** To simplify the situation, let's just consider `Fn` and `FnMut`. The story begins with the bridging impl from `Fn` to `FnMut`:\r\n\r\n```rust\r\nimpl<A,F> FnMut<A> for F\r\n    where F : Fn<A>\r\n{\r\n    type Output = F::Output;\r\n} // Impl 1.\r\n```\r\n\r\nNow, imagine I try to write an impl of `FnMut` for some custom type of my own:\r\n\r\n```rust\r\nstruct MyType<A> { ... }\r\nimpl<A> FnMut<A> for MyType<A> { ... } // Impl 2.\r\n```\r\n\r\nThis impl is considered to overlap with the bridge impl above. That may seem a bit surprising. But in fact it's not wrong. After all, according to the rules as currently written, it is possible for some other crate to come along extend `MyType` with another impl:\r\n\r\n```rust\r\nstruct TheirArgument;\r\nimpl Fn<(TheirArgument,)> for MyType<TheirArgument> { ... } // Impl 3.\r\n```\r\n\r\nNow the problem is that given these three impls, if we have the trait obligation `MyType<TheirArgument> : FnMut<(TheirArgument,)>`, it can be implemented in two ways. The bridge impl (Impl 1) combined with Impl 3, and the other Impl (Impl 2).\r\n\r\nAnother impl I would like to write is:\r\n\r\n```rust\r\ntrait FnBox<A> { ... }\r\nimpl<A,F> FnOnce<A> for Box<F>\r\n    where F : FnBox<A>\r\n{\r\n    ...\r\n}\r\n```\r\n\r\nThis falls afoul of coherence as well, for similar reasons.\r\n\r\n**The solutions.**  There are a couple of ways out of this problem. \r\n\r\n*A. Adjust the coherence rules.* It is certainly conceivable that we could adjust the current overlap check to permit Impl 2 but reject Impl 3. However, this is a mite tricky, because it requires that whenever a downstream crate adds *any* impl we must recheck (potentially) *all* impls for overlap. E.g. in this case, Impl 3 is an impl of the `Fn` trait, but the conflict that it induces is between Impls 1 and 3, both impls of the `FnMut` trait. (Incidentally, I'm told that this kind of check is precisely what Haskell does to ensure non-overlap for type families, though I couldn't find a good citation here.)\r\n\r\n*B. Negative trait bounds on Impl 2.* We could consider employing negative trait bounds in a variety of ways. One might be to attach a negative trait bound to Impl 2:\r\n\r\n```rust\r\nstruct MyType<A> { ... }\r\nimpl<A> FnMut<A> for MyType<A>\r\n    where MyType<A> : !Fn<A>\r\n{ ... } // Impl 2b.\r\n```\r\n\r\nThis would allow the coherence checker to accept Impl 2 (which is currently rejected). Interestingly, it does not *disallow* Impl 3, it merely gives it precedences over Impl 2. This is perhaps not the outcome we wanted. Another problem with this solution is that it interacts with the need for disambiguation in the type checker, so that if we were to write a generic function like:\r\n\r\n```rust\r\nfn foo<A>(m: MyType<A>, arg: A) { m(a); }\r\n```\r\n\r\nThis function would not type-check, because Impl 2 is not known to apply. We'd have to write:\r\n\r\n```rust\r\nfn foo<A>(m: MyType<A>, arg: A) where MyType<A> : !Fn<A> { m(a); }\r\n```\r\n\r\n(Incidentally, this makes sense because it's possible that the return type specified in impl 2 and the return type in some hypothetical impl 3 don't agree.)\r\n\r\nThis drawback effectively rules out this solution, at least in isolation.\r\n\r\n*C. Negative trait bounds on the `FnMut` trait.* The intention of the bridging impls, really, is that you will implement at most one of the various `Fn` traits for a given type. So it might be interesting to try and somehow declare `Fn` and `FnMut` disjoint. For example maybe like this:\r\n\r\n```rust\r\ntrait FnMut<A> : !Fn<A> { ... }\r\n```\r\n\r\nThis sort of makes sense, in that if you implement `FnMut`, you should not implement `Fn`. But of course it also doesn't make sense, because then the bridge impl that says \"here is an automatic impl of `FnMut` if you implement `Fn`\" seems to be a violation.\r\n\r\nMaybe the other way is good?\r\n\r\n```rust\r\ntrait Fn<A> : !FnMut<A> { ... }\r\n```\r\n\r\nBut this is also not right. After all, *every* type that implements `Fn` implements `FnMut`. All in all this idea is merely flawed. The idea is in fact not that every type will implement at most one of the `Fn` traits, but rather that they will implement at most one *directly*. \r\n\r\n> *An aside:* Negative trait bounds in supertypes are also interesting because they are semantically quite different from positive bounds. In particular, a *positive* supertrait bound is (today) verified at the impl site. But a *negative* supetrait bound cannot necessarily be verified purely at the impl site, it must also be verified in downstream crates. This seems to raise a very similar probelm to option A above, where every impl must be checked against all upstream impls to see whether it happens to invalidate them. This should perhaps not be surprising, since a negative supertrait is effectively making a more explicit form of the same sort of constraint that was implied in Option A.\r\n\r\n*D. Supertraits.* One way to sidestep this problem is to dump the bridging impls and use supertraits instead:\r\n\r\n```rust\r\ntrait Fn<A> : FnMut<A> { fn call(&self) -> Self::Output; }\r\ntrait FnMut<A> : FnOnce<A> { fn call_mut(&mut self) -> Self::Output; }\r\ntrait FnOnce<A> { type Output; fn call_once(self) -> Self::Output; }\r\n```\r\n\r\nThe fact that this makes sense should make it clear that the negative supertrait bound from Option C was wrong-headed. ;) There are however several downsides to Option D:\r\n\r\n- To implement `Fn`, you must write your own bridging impls of `FnMut` and `FnOnce`.\r\n- The semantics of `Fn`, `FnMut`, and `FnOnce` can diverge.\r\n\r\nAll in all supertraits don't feel as good. And of course it leaves the crucial problem of permitting convenient bridging impls unsolved; there are other cases where a \"partial bridge\" feels right, after all.\r\n\r\n#### Conclusions\r\n\r\nNot a lot of conclusions just now, except that I want to find a solution for the `Fn` traits but don't yet know what I think it ought to be.\r\n"}}