owned this note
owned this note
Published
Linked with GitHub
---
title: Negative impls RFC (draft)
---
- Feature Name: (fill me in with a unique ident, `my_awesome_feature`)
- Start Date: (fill me in with today's date, YYYY-MM-DD)
- RFC PR: [rust-lang/rfcs#0000](https://github.com/rust-lang/rfcs/pull/0000)
- Rust Issue: [rust-lang/rust#0000](https://github.com/rust-lang/rust/issues/0000)
# Summary
[summary]: #summary
* Permit users to write negative impls like `impl !Trait for Type` on stable.
* This is a semver-binding promise that `Type` will never implement `Trait`.
* It is an error to have `impl Trait for Type` and `impl !Trait for Type` at the same time.
* Negative impls must obey the coherence orphan rules.
* Negative impls do not have to obey the overlap rules with respect to other negative impls. (FIXME--what do we do now? needs tests.)
* Negative impls can be used to prove that two positive impls are disjoint.
* Two impls as follows...
* `impl<T: Bar> Foo for T`
* `impl Foo for MyType`
* ...would be allowed if either...
* `MyType` is local to this crate and does not have a `Bar` impl (pre-existing rule)
* or there is a `MyType: !Bar` impl (new rule).
* Negative impls, when applied to auto traits like `Send` or `Sync`, cannot be conditional (similar to the `Drop` trait).
# Motivation
[motivation]: #motivation
In stable Rust today, you can declare that you implement a trait for a type. This forms a semver-binding commitment to always have such an impl[^major]. For example, the [`Rc`] type implements `Deref`, which signals that a `Rc<T>` can always be dereferenced to construct a `&T`:
[^major]: Until a new major version is released, of course, at which point all bets are off.
[`Rc`]: https://doc.rust-lang.org/std/rc/struct.Rc.html
```rust
struct Rc<T> {
...
}
impl<T> Deref for Rc<T> {
type Target = T;
...
}
```
However, stable Rust does not have a way to make a **negative** assertion. For example, there is no explicit way to say "you will NEVER be able to `DerefMut` an `Rc`".
The closest you can come in Rust today is simply *not* implementing `DerefMut` at all. In reality, though, this doesn't mean that `Rc<T>` can never implement `DerefMut`, it only means that `Rc<T>` doesn't implement `DerefMut` *yet*. There are a few ways that this could change:
* You could release a new version of your library that adds a `DerefMut` impl; this might happen because new maintainers aren't aware of the invariants you were trying to maintain.
* In some cases, the coherence rules permit downstream impls to implement a trait for `Rc`, so long as they are implemented for a "sufficiently local" type. This was the cause of an [unsoundness in `Pin`][#66544], for example, which was corrected via the mechanism we are proposing to stabilize in this RFC.
[#66544]: https://github.com/rust-lang/rust/issues/66544
Why, you might ask, does it matter that you explicitly declare that an impl will never be added? When is that a useful thing to say?
## Reason #1: Auto traits and opt-out
In Rust today, we have certain builtin traits (called "auto traits") that are implemented automatically for every type unless that type "opts out". The [`Send`] and [`Sync`] types are the most prominent examples, but there are other traits like [`UnwindSafe`] and [`Unpin`].
[`UnwindSafe`]: https://doc.rust-lang.org/std/panic/trait.UnwindSafe.html
[`Unpin`]: https://doc.rust-lang.org/std/marker/trait.Unpin.html
[`Send`]: https://doc.rust-lang.org/std/marker/trait.Send.html
[`Sync`]: https://doc.rust-lang.org/std/marker/trait.Sync.html
The auto trait rules try to automatically determine when it is safe for a type to be `Send`, but there are some cases where these automatic rules don't work. The auto trait RFC proposed negative impl syntax as the means to "opt out" from being `Send`, but this was never stabilized:
```rust
/// Example: Imagine that instances of ThreadLocalMarker
/// implicitly reference thread-local state and ought not to
/// be sent to other threads.
struct ThreadLocalMarker { id: u32 }
impl !Send for ThreadLocalMarker { }
```
To achieve a similar effect today, you would have to include a dummy field in `ThreadLocalMarker` that is already not sendable, such as `*const u32`. Of course, that raises the question of why `*const u32` is `!Send` in the first place? The answer is that the stdlib makes use of negative impls (in unstable state) already, so we are simply stabilizing the mechanism that's already in use.
(A similar pattern arises for `Unpin`: to mark a type as pinned, you currently include a field with type [`PhantomPinned`](https://doc.rust-lang.org/std/marker/struct.PhantomPinned.html).)
## Reason #2: Documentation
Sometimes there are traits that should not be implemented for correctness reasons. For example, if we have a struct `Money`, we may wish to ensure that `Money` cannot be cloned, but only moved from place to place. Right now, the only way to do that is to simply not implement `Clone`, write a comment, and hope that nobody else implements it in the future. With negative impls, we can explicitly state that `Money` is not `Clone`, and we also have an obvious place to document the reasons why:
```rust
struct Money { }
/// We do not wish users to be able to clone money,
/// convenient as that may be, because society would
/// fall apart. (citation needed)
impl !Clone for Money { }
```
## Reason #3: Unsafe code
Sometimes we wish to write unsafe code that is only correct because an impl does *not* exist. For example, some of the pin impls and methods were assuming that `&T` did not implement `DerefMut`. Per the previous point, without negative impls, there was no clear place to document this, but what's worse, it was found in [#66544] that it was possible to implement `DerefMut` for `&`-references in downstream crates, if you were sufficiently devious. For example, this impl
```rust
struct MyType {}
impl DerefMut for &MyType { }
```
would have been accepted. This could be used to undermine the safety of the pin system. The fix was to add an explicit negative-impl in the standard library:
```rust
impl<T: ?Sized> !DerefMut for &T { }
```
which ensured that the desired property would be enforced. This change has already been made but the mechanism (negative impls) is unstable, this RFC is proposing to stabilize that mechanism.
More generally, this allows unsafe code to always reason about things that are "positively true". For example, instead of arguing that something is sound because no impl exists (yet), you instead argue that it is sound because a negative impl exists. This ensures your reasoning remains valid even as the crate evolves, as it a semver-breaking change to remove a negative impl.
## Reason #4: Coherence rules
Rust programmers know that `Vec<T>` will never be `Display` (because there is no one right way to show a vector to an end-user). The compiler, however, is not so clever, and considers the following impls to potentially overlap:
```rust
impl<T: Display> SomeTrait for T { }
impl<T> SomeTrait for Vec<T> { }
```
Under this RFC, if `Vec<T>` had a `!Display` impl, then these impls would be accepted.
This exact scenario arose when attempting to [move the `Error` trait to libcore](https://github.com/rust-lang/project-error-handling/issues/3). In that case, the compiler needed to know that `&str` would never implement `Error`, but it did not. Today, libcore includes an [unstable negative impl indicating the `&str: !Error`](https://github.com/rust-lang/rust/pull/99917).
NB, this RFC is not a "fully general" solution to the coherence problem. There are numerous other extensions we would like to permit overlapping impls. But it is a step in the right direction.
# Guide-level explanation
[guide-level-explanation]: #guide-level-explanation
You can make a promise that you will never implement a trait for a specific type.
You do so by writing a *negative impl*, in which the trait name is preceded by a `!` sign:
```rust
impl !Trait for Type {}
```
That means that `Type` does not and will never implement `Trait`.
It is an error if a positive and negative impl of the same trait exist for the same type, and thus the following program will not compile:
```rust
impl !Trait for Type { }
impl Trait for Type { ... }
```
Note that unlike positive impls, negative impls do not have any items in their body.
## Orphan rules for negative impls
Negative impls make a semver commitment not to implement something in the future and
therefore they must follow the same "orphan rules" as positive impls (see [RFC 2451] for an explanation of the orphan rules).
[RFC 2451]: https://rust-lang.github.io/rfcs/2451-re-rebalancing-coherence.html
Specifically:
* Your negative impl must be for a local trait or a local type (and impl type parameters must be "covered" as defined in [RFC 2451]).
* Adding a blanket negative impl (e.g., `impl<T> !SomeTrait for SomeType<T>`) for a pre-existing trait `SomeTrait` and type `SomeType` is a breaking change and requires a new major version.
## Conditional negative impls
Like other impls, negative impls can have where-clauses to narrow their scope. For example, the following impl only applies to `Vec<T>` if `T: Debug`:
```rust!
impl<T: Debug> !Foo for Vec<T> { }
```
### Conditional negative impls disallowed for auto traits
For auto traits specifically, negative impls cannot be conditional. For example, the following impl is disallowed because it would not apply to `Foo<Vec<u32>>`, since `Vec<u32>` does not implement `Display`.
```rust=
struct Foo<T> { }
impl<T> !Send for Foo<T>
where
T: Display,
{}
```
The meaning of the above program is unclear and depends on the specifics of how auto traits are defined; by disallowing it, we avoid an ambiguous situation. One interpretation of auto traits is that there is an "implicit impl" that is always added that makes `Foo` be `Send` unless (1) there is a negative impl that applies or (2) `Foo` contains a field of non-Send type. Under that interpretation, `Foo<T>` would be `Send` so long as `T` does not implement `Display`. This makes `Foo<T>: Send` equivalent to a negative where-clause `not { T: Display }`; as discussed in the "alternatives" section, we do not wish to permit such where-clauses as they give rise to paradoxical behavior.
## Overlapping negative impls
For positive impls, having multiple impls introduces ambiguity as to which definition of a method or associated type should be used;
for negative impls, no such ambiguity arises.
Therefore, the compiler permits overlapping negative impls without error.
For example, the following pair of impls is accepted:
```rust
impl<T: Debug> !Foo for T { }
impl !Foo for u32 { }
```
## Negative impls and coherence
When a negative impl exists, other crates can rely on this as part of the coherence check. For example, if crate A contains
```rust
// Crate A
struct Widget { }
impl !Display for Widget { }
```
then crate B could contain the following impls:
```rust
// Crate B
impl<T: Display> SomeTrait for T { }
impl SomeTrait for Widget { }
```
These two impls are not considered to overlap because we know that `Widget` does not implement `Display` (and never will).
## When to include a negative impl
It is good practice to include negative impls for traits that your type intentionally does not implement.
However, since removing a negative impl is a breaking change, you should only do so if you know that the type will *never* implement the trait.
If you think you may want to add an impl of the trait later, you should simply do nothing.
# Reference-level explanation
[reference-level-explanation]: #reference-level-explanation
The following changes are required in the compiler. They are discussed in more detail in the sections below.
1. For each negative impl, we enforce the coherence rules as normal.
2. For each positive impl `P0: Trait<P1..Pn>`, we prove `not { P0: !Trait<P1...Pn>` (or report an error, if that proof fails)
3. For each pair `A, B` of positive impls that would otherwise be considered overlapping, we try to prove the negative version of some where-clause on A or B. If that proof succeeds, the pair is considered non-overlapping.
## Change 1: Each negative impl checks orphan rules
TBD
## Change 2: Each positive impl proves "not the negative impl"
TBD
## Change 3: Each pair of positive impls can prove non-intersection by proving the negative version of a where-clause
TBD
# Drawbacks
[drawbacks]: #drawbacks
Why should we *not* do this?
# Rationale and alternatives
[rationale-and-alternatives]: #rationale-and-alternatives
## Why do we not permit negative where clauses?
This RFC permits negative impls, but doesn't permit you to write a negative where clause like `where T: !Debug`. While such where-clauses could be useful, they introduce logical quandries. Consider a trait like this one:
```rust!
trait Truth { }
impl<T> Truth for T
where
T: !Truth
{ }
```
Given this impl, does `u32` implement `Truth`? The answer is that it does -- so long as it doesn't. This is called the "liar's paradox". There are ways to make these kind of statements make sense, but they generally make everything more complicated, and so we would prefer to avoid them.
## Are there any uses for negative where clauses? Would we ever want them?
The main reason to permit negative where-clauses is to declare sets of mutually exclusive traits. For example, we might like to say that a type `T` can implement `Square` or `Circle` but not both. This could inform specialization, coherence, or other similar features in the future. Given negative where-clauses, this could be expressed like `trait Square: !Circle`. However, negative where-clauses also allow *other* things to be expressed that we don't want (see previous question). A more tractable alternative might be to introduce an explicit declaration e.g. `Disjoint(Square, Circle)` that can be enforced through coherence. The key to avoiding the liar's paradox is to ensure that deciding whether a given trait is implemented for a given type doesn't require proving a negation.
# Prior art
[prior-art]: #prior-art
Discuss prior art, both the good and the bad, in relation to this proposal.
A few examples of what this can include are:
- For language, library, cargo, tools, and compiler proposals: Does this feature exist in other programming languages and what experience have their community had?
- For community proposals: Is this done by some other community and what were their experiences with it?
- For other teams: What lessons can we learn from what other communities have done here?
- Papers: Are there any published papers or great posts that discuss this? If you have some relevant papers to refer to, this can serve as a more detailed theoretical background.
This section is intended to encourage you as an author to think about the lessons from other languages, provide readers of your RFC with a fuller picture.
If there is no prior art, that is fine - your ideas are interesting to us whether they are brand new or if it is an adaptation from other languages.
Note that while precedent set by other languages is some motivation, it does not on its own motivate an RFC.
Please also take into consideration that rust sometimes intentionally diverges from common language features.
# Unresolved questions
[unresolved-questions]: #unresolved-questions
- What parts of the design do you expect to resolve through the RFC process before this gets merged?
- What parts of the design do you expect to resolve through the implementation of this feature before stabilization?
- What related issues do you consider out of scope for this RFC that could be addressed in the future independently of the solution that comes out of this RFC?
# Future possibilities
[future-possibilities]: #future-possibilities
## `?Trait` and reservations
Under this proposal, given some non-auto-trait `Draw` and a type `MyCircle`, one can have three different possibilities:
* There is an `impl Draw for MyCircle`, and hence `MyCircle: Draw` holds now and in the future (up to a major semver release).
* There is an `impl !Draw for MyCircle`, and hence `MyCircle: Draw` does not hold now nor will it hold in the future (up to a major semver release).
* There is no declaration at all, in which case `MyCircle` does not implement `Draw` now, but it *may* in some future release.
The final point is more complex when generic type parameters are involved. Consider the trait `PartialEq<T>`. If there is no impl of `PartialEq<_>` for `MyCircle`, then a downstream crate `X` would do the following:
```rust
struct Ex;
impl PartialEq<Ex> for MyCircle { }
```
Now if the original crate were to add an impl like `impl<T> PartialEq<T> for MyCircle`, that would cause an overlap in the crate `X` and hence `X` would stop compiling. For this reason, we say that adding "blanket impls" (those with type parameters) is only permitted on a new major version.
It might be useful if we could add a `?Trait` impl that would *reserve the right* to add an impl but does not actually add one. Then the original crate could declare something like this:
```rust
struct MyCircle { }
impl<T> ?PartialEq<T> for MyCircle { }
```
This impl would prevent the `X` crate from implementing `PartialEq<Ex> for MyCircle`, and thus allow the original crate to add impls in the future.
The compiler has an internal mechanism like this ([`rustc_reservation_impl`][#64631]) which was added to help stabilize the `!` type (though that stabilization has been stalled for other reasons). The [tracking issue][#64631] for `rustc_reservation_impl` explains:
> The `#[rustc_reservation_impl]` attribute was added as part of the effort to stabilize `!`. Its goal is to make it possible to add a `impl<T> From<!> for T` impl in the future by disallowing downstream crates to do negative reasoning that might conflict with that.
[#64631]: https://github.com/rust-lang/rust/issues/64631
This feature is narrowly tailored to the `!` type use case, however, and it does not actually provide the guarantees an end-user might want in most cases, as is explained on [the tracking issue](#64631).
### `?` and auto-traits (e.g., `?Send`)
The `?Trait` impl feature might be particularly useful for auto-traits. As the main RFC text explains, currently, if one wishes to say that you are not `Send` *now* but may become `Send` in the future, one must use a marker type, which is awkward and non-obvious.
## Mutually exclusive traits or `T: !Trait` where-clauses
Some traits are mutually exclusive, meaning that at most one can be implemented. For example, a single shape cannot be both a rectangle and a circle:
```rust
trait Shape { }
trait Rectangle: Shape { }
trait Circle: Shape { }
```
Rust today cannot express this in a first-class way. You can create programs that *rely* on this invariant for specific types (and this RFC makes it easier to do across crates). This program, for example...
```rust
struct MyCircle { }
impl Circle for MyCircle { }
trait Draw { }
impl<T: Rectangle> Draw for T { }
impl Draw for MyCircle { }
```
...would not compile if you were to add `impl Rectangle for MyCircle`. However, this exclusivity condition is specific to `MyCircle`, I could add other types that implement both `Circle` and `Rectangle`[^math]:
```rust
struct Point { }
impl Rectangle for Point {
// a infinitisemally small rectangle
}
impl Circle for Point {
// a infinitisemally small circle
}
```
As a consequence, these two blanket impls for `Draw` would be considered to potentially overlap and hence you will get a compilation error:
```rust
trait Draw { }
impl<T: Rectangle> Draw for T { }
impl<T: Draw> Draw for T { }
```
It would be nice to have a way to declare `Rectangle` and `Circle` as exclusive and thus rule out the type `Point`. One way to do that would be to have `!Trait` as a where-clause, so that we could write:
```rust
trait Shape { }
trait Rectangle: Shape + !Circle { }
trait Circle: Shape + !Rectangle { }
```
There are some downsides with this proposal, however. For example, if we were to add more kinds of shapes, we would need a large number of `!` clauses, one per trait:
```rust
trait Shape { }
trait Rectangle: Shape + !Circle + !Triangle { }
trait Circle: Shape + !Rectangle + !Triangle { }
trait Triangle: Shape + !Rectangle + !Circle { }
```
This seems annoying! Therefore we might want to have some way to declare a set of mutually exclusive traits instead as a first-class concept, or at least syntactic sugar.
One additional wrinkle around `T: !Trait` is that, in order to keep the trait solver tractable, it would be better if `T: !Trait` is only consider true when there is an actual negative impl (and not just "no impl has been added *yet*"). This ensures that we are not being asked to prove (or assume) the absence of things, but only the presence of things (negative impls, in this case), which makes life easier.
[^math]: We're probably using the word "infinitesimally" wrong and probably violating various geometric axioms. Do we look like mathematicians to you?
##### APPENDIX WEIRD EXAMPLES
```rust
// Crate A
trait TraitA { }
impl<T: Debug> !TraitA for Vec<T> { }
struct StructA { }
// Crate B
trait TraitB { }
impl<T: TraitA> TraitB for Vec<T> { }
impl TraitB for Vec<StructA> { }
// ok if crate B can prove `StructA: !TraitA`
// -- but there is no `Debug` impl for `StructA` and the negative impl requires one
```
```rust
// Crate A
trait TraitA { }
impl<T: Debug> !TraitA for Vec<T> { }
struct StructA { }
trait TraitB { }
impl<T: TraitA> TraitB for Vec<T> { }
impl TraitB for Vec<StructA> { }
// OK if all in one crate:
// -- but there is no `Debug` impl for `StructA` and the negative impl requires one
```
## Questions
- Should we mention something related to specialization, that it could be achieve used negative bounds and things like that?.
- What about specialization of a negative impl with another negative impl. That's overlap and we do allow both things. Worth mentioning it?.