negative impls initiative

What is this?

This page tracks the work of the negative-impls initiative! To learn more about what we are trying to do, and to find out the people who are doing it, take a look at the charter.

Current status

The following table lists of the stages of an initiative, along with links to the artifacts that will be produced during that stage.

Key:

• ✅ -- phase complete
• 🦀 -- phase in progress
• 💤 -- phase not started yet

How Can I Get Involved?

• Check for 'help wanted' issues on this repository!
• If you would like to help with development, please contact the owner to find out if there are things that need doing.
• If you would like to help with the design, check the list of active design questions first.
• If you have questions about the design, you can file an issue, but be sure to check the FAQ or the design-questions first to see if there is already something that covers your topic.
• If you are using the feature and would like to provide feedback about your experiences, please [open a "experience report" issue].
• If you are using the feature and would like to report a bug, please open a regular issue.

We also participate on {{CHAT_PLATFORM}}, feel free to introduce yourself over there and ask us any questions you have.

Building Documentation

This repository is also an mdbook project. You can view and build it using the following command.

mdbook serve

✏️ Updates

Lang-team initiatives give monthly updates. This section collects the updates from this initiative for posterity.

To add a new update:

• Create a new file updates/YYYY-mmm.md, e.g. updates/2021-nov.md
  • We recomend basing this on the update template
• Link it from the SUMMARY.md

📜 {{INITIATIVE_NAME}} Charter

Proposal

Membership

🔬 Evaluation

The evaluation surveys the various design approaches that are under consideration. It is not required for all initiatives, only those that begin with a problem statement but without a clear picture of the best solution. Often the evaluation will refer to topics in the design-discussions for more detailed consideration.

📚 Explainer

The "explainer" is "end-user readable" documentation that explains how to use the feature being deveoped by this initiative. If you want to experiment with the feature, you've come to the right place. Until the feature enters "feature complete" form, the explainer should be considered a work-in-progress.

Negative impls: a promise NOT to do something

By now you are probably familiar with trait impls in Rust:

#![allow(unused)]
fn main() {
// In version 1.0 of the crate `uint`:
trait UnsignedInt {
    fn increment(&mut self);
}

impl UnsignedInt for u16 { 
    fn increment(&mut self) {
        *self += 1;
    }
}

impl UnsignedInt for u32 { 
    fn increment(&mut self) {
        *self += 1;
    }
}

impl UnsignedInt for u64 { 
    fn increment(&mut self) {
        *self += 1;
    }
}
}

Impls are forever

Of course, a trait implementation provides the definition of a trait's methods, but it also provides a semver promise: future releases of the same crate cannot remove an implementation without a major version bump.

Minor versions can add new impls

It is, however, legal for crates to add a new implementation in a minor version (with some caveats¹). So, if we had the trait above, one could add an impl for u8:

#![allow(unused)]
fn main() {
// In version 1.1 of the crate `uint`:

impl UnsignedInt for u8 {
    fn increment(&mut self) {
        *self += 1;
    }
}
}

Implication: Downstream crates cannot rely on something not being implemented

A consequence of the fact that crates are permitted to add new impls is that Rust code cannot rely on impls not being implemented, since impls that don't exist today may come to exist in the future. The primary place that this comes up today is with coherence. Consider this example:

#![allow(unused)]
fn main() {
// In another crate `foo` that depends on `uint`:

trait FooTrait { }
impl<T: uint::UnsignedInt> FooTrait for T { }
impl FooTrait for u128 { }
}

At the moment, uint does not implement UnsignedInt for u128, so one could imagine that this code would compile. However, if we were to allow that, then the crate foo might be broken by some future release of uint which adds an impl for u128. In particular, that would cause there to be two overlapping impls for FooTrait, and this is not allowed. That is a problem, since adding a new impl is meant to be a non-breaking change. For this reason, Rust rejects the impls above, unless they appear within the crate uint itself (the idea is that, within the crate, if you were to add the new impl, you would get a compilation error locally).

In the foo example, Rust's restriction makes sense. It seems highly likely that adding not having u128 implement UnsignedInt was just an oversight. But other examples are less clear. Imagine this crate, bar:

#![allow(unused)]
fn main() {
// In yet another crate `bar` that depends on `uint`:

trait BarTrait { }
impl<T: uint::UnsignedInt> BarTrait for T { }
impl BarTrait for String { }
}

Again, the compiler rejects this code, this time because it is concerned that some future release of uint might add an impl of UnsignedInt for String -- but that seems very unlikely to happen, since string is not an integer of any kind. (Although not impossible -- maybe we'd like to be able to treat format!("123") as an integer?) How are we to distinguish these two cases?

Enter: Negative impls

The idea of negative impls is to make it possible for a crate to promise not to implement something. Given this extension, the uint crate could add an impl like the following:

#![allow(unused)]
fn main() {
// In uint v1.2:

impl !UnsignedInt for String { }
}

Once added, removing a negative impl is a breaking change, just as with a positive impl. Effectively, the negative impl is a promise by uint never to implement UnsignedInt for String. Given this negative impl, it is then fine for bar to add impls that rely on String not implementing UnsignedInt, so that example would compile.

Coherence check

Coherence works in two parts. The first is the orphan check, which is unaffected by this RFC: the orphan check is the one that ensures that you only implement foreign traits for types that are local to your crate.

The second part of the coherence check is the overlap check. The principle here is that if you have two impls Impl1 and Impl2 for some trait Trait, we wish to ensure that Impl1 and Impl2 cannot apply to the same set of inputs P0: Trait<P1...Pn>.

Negative of a where clause

We define the negative of a where clause Negative(WC) as a partial function that converts T: Trait to T: !Trait:

• Negative(P0: Trait<P1...Pn>) = Some(P0: !Trait<P1...Pn>)
• Negative(for<'a..'z> P0: Trait<P1...Pn>) = Some(for<'a..'z> P0: !Trait<P1...Pn>)
• Negative(WC) = None, otherwise

New disjointness rules

The coherence check is extended with a new rule for determining when Impl1 and Impl2 are disjoint (the rule is applied twice for any pair (A, B) of impl, once with A as Impl1 and once with B as Impl1). These rules are alternatives to the existing rule, which means that any program that compiles today continues to compile, but we will also consider new programs as passing the coherence check.

In plain English, the idea is that we can consider Impl1 and Impl2 to be disjoint if whenever Impl1 applies, some where clause in Impl2 cannot hold (i.e., we can prove the negative of it) (and vice versa).

• Disjoint(Impl1, Impl2) holds if, for some substitution S and some where clause WC on Impl2:
  • S(TraitRef(Impl2)) = TraitRef(Impl1) -- there is some instantiation S of the Impl2 generics such that Impl1 and Impl2 apply to the same types
  • Negative(S(WC)) is provable, given the environment of Impl1 -- we can prove the negative version of some where clase from Impl2

In operational terms:

• Disjoint(Impl1, Impl2) if...
  • Instantiate Impl1 with placeholders
  • Instantiate Impl2 with inference variables
  • Equate all type parameters from Impl1 and Impl2
  • There exists some where clause WC on Impl2 where negative(WC) holds.

Always applicable impls

Like the Drop trait, negative impls are currently limited to being "always applicable", which means that they must apply to all instances of a given type. As an example, consider the following type Foo:

#![allow(unused)]
fn main() {
struct Foo<T: Eq> { t: T }
}

It is legal to implement a negative trait for Foo, so long as it applies to all T: Eq:

#![allow(unused)]
fn main() {
impl<T: Eq> !Clone for Foo<T> { }
}

It is not legal to implement a negative trait that only applies to some T:

#![allow(unused)]
fn main() {
impl<T: Eq + Ord> !Clone for Foo<T> { }
}

Why require always applicable?

This rule is inspired by limitations of the current implementation, particularly when it comes to auto traits. In particular, the way that auto traits are currently implemented, negative impls always apply to all instances of the type. Therefore, this impl for example would actually mean that Foo<T> is never Send:

#![allow(unused)]
fn main() {
impl<T: Eq + Ord> !Send for Foo<T> { }
}

Under the "always applicable" rule, this impl is simply illegal. Once the implementation for auto traits has improved, we could lift this rule.

✨ RFC

The RFC exists here in draft form. It will be edited and amended over the course of this initiative. Note that some initiatives produce multiple RFCs.

Until there is an accepted RFC, any feature gates must be labeled as experimental.

When you're ready to start drafting, copy in the template text from the rfcs repository.

😕 Frequently asked questions

This page lists frequently asked questions about the design. It often redirects to the other pages on the site.

What is the goal of this initiative?

See the Charter.

Who is working on it!

See the Charter.