[Pre-RFC] Mutually exclusive traits

[td_]

Summary

Distinguish between !Trait and ?Trait to enable mutually exclusive traits within the constraint that implementing traits should be a backwards compatible change. With these two type-trait relations distinguished, allow negative impls of all traits as well as negative bounds, introducing mutual exclusion to the type system. This enables users to encode additional logic in the type system & to provide multiple coherent blanket implementations for parameterized types with mutually exclusive trait bounds, without the backwards compat problems that have hampered past proposals.

Motivation

Trait coherence rules ensure that the compiler will predictably associate a particular definition with any invocation of a method or item associated with that trait. Without coherence rules, the behavior of a Rust program could easily become disastrously non-deterministic.

However, coherence rules are currently very conservative in what they allow to be implemented. Other RFCs may allow for multiple overlapping implementations through developing an order of precedence for specialized implementations. This RFC addresses the limitation from another angle. By introducing a concept of mutually exclusive traits, it becomes possible to declare that two traits must not both be implemented by a single type, causing parameters bound by each of those traits to be non-overlapping.

This is concretely useful; imagine a system with the traits Edible, Poisonous and Consumable; though no trait should be both Edible and Poisonous, it is not currently possible to implement Consumable for T: Edible and T: Poisonous because it cannot be guaranteed that a type will not implement both. With mutual exclusivity, this becomes possible.

trait Edible: !Poisonous {
    ...
}

trait Poisonous: !Edible {
    ...
}

trait Consumable {
    ...
}

impl<T> Consumable for T where T: Edible {
    ...
}

impl<T> Consumable for T where T: Poisonous {
    ...
}

Though this example is fairly trivial, this has a big impact on the ability of clients to compose multiple libraries together. Bounded blanket implementations are almost never possible under the current trait rules. Currently, if two libraries share an upstream library, both can extend the behavior of types in that library by defining new traits for that type. With this proposal, if the upstream library provides mutually exclusive traits, downstream library A could implement a type for all T bounded by one of those traits, and downstream library B could implement that trait for a new type, a client of both libraries can now call methods of the trait in library A on the type in library B.

A second benefit somewhat less concrete, because it has to do with what you cannot do. By encoding mutual exclusivity in the type system, programmers can guarantee that they will never by some accident create a type which implements both traits. Essentially, a greater portion of program logic is implemented in a manner which is statically analyzable. For example, the num crate currently defines both Signed and Unsigned, but nothing prevents a type from implementing both traits. Clients of num cannot safely rely on an Unsigned bound to guarantee that a type is not Signed, even though that is the entire purpose of the trait (which is currently a marker trait).

Detailed design

Trait, !Trait, and ?Trait

An earlier RFC attempting to codify negative reasoning ran aground on the problem of backwards compatibility. If it is possible to bound a type parameter or trait by the non-implementation of another trait, then that non-implementation becomes a semantic expression, and it would be backwards incompatible to ‘eliminate’ the non-implementation by implementing that trait. This backwards incompatibility hazard is a serious one, and applied to the implicit negative reasoning of certain non-overlapping implementations.

The solution to this problem which would enable mutual exclusivity is to hold the relation between types and traits to be in three states, not two:

• T: Trait: The type T implements the trait Trait.
• T: !Trait: The type T does not implement the trait Trait.
• T: ?Trait: The type T may or may not implement the trait Trait.

By default, the relation between any T and any Trait is T: ?Trait. Only with an implementation of Trait or !Trait which matches T does this change. This table documents the three relations and how they are described:

|               | ?Trait            | Trait                | !Trait             |
|---------------|-------------------|----------------------|--------------------|
| Specific impl | by default        | impl Trait for T     | impl !Trait for T  |
|               | impl ?Trait for T |                      |                    |
|---------------|-------------------|----------------------|--------------------|
| Default impl  | by default        | impl Trait for ..    | impl !Trait for .. |
|---------------|-------------------|----------------------|--------------------|
| Bounds        | by default        | where T: Trait       | where T: !Trait    |
|               | where T: ?Sized   | by default for Sized |                    |

Implementing ?Trait and !Trait

?Trait and !Trait act as if they were marker traits implicitly defined with Trait. They define no methods and have no associated items. They are imported wherever Trait is imported.

However, ?Trait can only be implemented for types for which a default impl has been defined (e.g. Send and Sync), and cannot be default impl’d itself. Traits without default impls are implemented ?Trait by default anyway, and any such implementation would be a redundancy. In general, the ?Trait syntax will be very uncommon.

The purpose of implementing !Trait for T is to make a forwards compatible guarantee that T can not and will not implement Trait. This makes the negative reasoning explicit and no longer a hazard for backwards compatibility.

Bounding by !Trait

Bounding by !Trait under this RFC is different from in the prior negative bounds RFC; this bound is only met if the trait explicitly implements !Trait. As mentioned prior, this avoids the hazards that implicit negative reasoning introduces.

The primary purpose of bounding by !Trait is that allows two traits to be declared mutually exclusive.

An argument could be made in a later RFC for a sugar in which implementing a trait bound by !Trait implicitly implements !Trait as well. This RFC does not propose to introduce that sugar.

Clarification of default impl rules

If a default impl of Trait exists, these rules are used to determine the relation between T and Trait:

• If Trait, ?Trait, or !Trait is implemented for T itself, that impl defines its relation.
• If one of its members impls a trait which is different from the default impl, the relation is T: ?Trait.
• Otherwise, it implements whatever relation the default impl defined.

(As it happens this is true for the implicit impl ?Trait for .. of trait with no default impl.)

Drawbacks

This adds rules to Rust’s coherence system. Adding rules necessarily makes the language less accessible, and is always a drawback. There is a trade off at play here between easiness and expressiveness.

It may be difficult to grok the difference between !Trait and ?Trait. The reason for this difference only becomes clear with an understanding of the factors at play in the coherence system.

The impl !Trait for T syntax overlaps with the syntax of existing negative impls for types with default impls. For each existing negative impl, it will need to be determined whether that type should impl !Trait or ?Trait (that is, whether or not the non-implementation is intended to be a reliable guarantee). That said, it is a backwards compatible change that will not cause any regressions (existing code will only become a stronger statement about the relation).

Alternatives

Sibling proposal: !Trait by default

There is an alternative scheme which has some advantages and disadvantages compared to the one proposed in the main RFC. I am not completely certain that the main proposal is a better proposal than this one.

Under this alternative, types would impl !Trait by default, and a default impl of ?Trait would be necessary to make that not the case. The table for such a proposal would look like this:

|               | ?Trait             | Trait                | !Trait            |
|---------------|--------------------|----------------------|-------------------|
| Specific impl | impl ?Trait for T  | impl Trait for T     | by default        |
|               |                    |                      | impl !Trait for T |
|---------------|--------------------|----------------------|-------------------|
| Default impl  | impl ?Trait for .. | impl Trait for ..    | by default        |
|---------------|--------------------|----------------------|-------------------|
| Bounds        | by default         | where T: Trait       | where T: !Trait   |
|               | except: ?Sized     | by default for Sized |                   |

The trade off here is between these two desirable, incompabilte features:

• A: Adding new impls is backwards compatible.
• B: impl’s for T: Trait do not overlap with types that don’t impl Trait.

The primary proposal prefers A whereas the alternative proposal prefers B. Both, however, make the other possible for specific traits in which the alternative makes more sense. I have preferred the primary proposal because it seems to me that problems presented by not having A will only appear over time, whereas problems presented by not having B will appear rapidly.

That is, you will only discover it is important to you to be able to add new impls of traits for stable types after you have already stabilized your types, whereas you will discover that you want your trait to be exclusive from types that don’t explicitly implement that trait as you are building out its implementation. Thus, enabling A by default avoids the sadness of discovering too late that you want to be able to add impls later.

Other alternatives

Allowing negative bounds without distinguishing between !Trait and ?Trait remains an alternative, though it presents a backwards compatibility hazard.

And as always, doing nothing is an alternative.

Not an alternative: specialization

As a side-note, this RFC does not overlap with proposals for trait specialization. Mutual exclusion is not a situation that can be modeled with specialization, and does not model specialization. Put in terms of sets, types which implement mutually exclusive traits are disjoint sets, whereas specialization allows a distinct implementation for a subset of the types which implement the trait.

Conceptually, they are connected only in that they expand what is allowed by Rust’s coherence system compared to the present, but they have separate use cases.

Unresolved questions

How mutual exclusion will be applied to the types and traits provided by Rust’s std library and other related libraries is not covered by this RFC, and should be the subject of a separate RFC.

[llogiq]

Another alternative would be to implement a lint that catches types bound by both traits (where the trait combination is somehow marked up to be incompatible, either by a special comment / arg or by naming convention, e.g. Something vs. NotSomething, InSomething or UnSomething).

This would not burden the compiler with the analysis (and let’s face it, 90% of the code most of us will work on will run fine without it), and give a good part of the benefits. Indeed writing such a lint and observing where it is useful would be a good exercise to motivate a RFC.

Should you want to go that route, feel free to contact @Manishearth or myself if you need help – I think your lint could even become part of rust-clippy if you like (Manish will have the last word on this; it’s his project after all). Also note that parts of the rustc_typeck crate have recently been made publicly accessible (though they are of course unstable), so detecting trait bounds from a lint should definitely be possible.

[td_]

@llogiq

Another alternative would be to implement a lint that catches types bound by both traits (where the trait combination is somehow marked up to be incompatible, either by a special comment / arg or by naming convention, e.g. Something vs. NotSomething, InSomething or UnSomething).

This wouldn't cause blanket impls for these types not to overlap, which is where most of the gain of mutually exclusive traits comes in in my opinion. This would allow trait impls to be statically abstracted over a variety of other traits, so that (for example) if you implement a new kind of Integer and I implement a trait for T: Integer, your Integer implements my trait. This is currently only possible if I don't also implement my trait for any other type (because all types are either Integer or ?Integer from my perspective).

[Manishearth]

I don’t think lints would work here – lints are imperfect and would balk at complex situations.

Besides, a lint cannot relax the typechecking of the compiler. Most motivations behind Something/NotSomething are there to try and provide a partitioned impl; i.e have

impl<T> Foo for T where T: Something {
 ...
}

impl<T> Foo for T where T: NotSomething {
 ...
}

This is currently disallowed by the compiler and there’s nothing a lint can do it.

(Also, clippy should be for style and footgun lints – stuff like this belongs in seperate lints; e.g. rust-extensible)

[llogiq]

I stand corrected.

[jnicklas]

I really hope you submit this as a RFC. I think this is a great change that makes the language more powerful and more consistent. Even as a relative newcomer I’ve run into restrictions in the coherence rules multiple times already which would have been easily bypassed by the solution proposed in this RFC. I like this much better than previously suggested solutions to the problem.

I do not feel that the added complexity you mention as drawbacks is that much of an issue. When I ran into this problem, my intuitive thinking was “I really wish there was some way to tell Rust that this doesn’t implement a certain trait”. Certainly if one runs into this syntax without ever having faced that particular problem it might be unintuitive, but I think most people who experiment for a while with generic programming in Rust will run into this issue.

[td_]

I submitted this RFC earlier today, actually.

[jnicklas]

Awesome I both scanned the list manually and checked with the GH search and I still missed it. Weird.

[llogiq]

As atonement for my mistake above, I have read through the RFC and submitted my comments.