Planet Mozilla

So wait, how does the orphan rule protect composition?

You might be wondering how the orphan rule ensures you can compose crates from crates.io. Well, imagine that there is a crate widget that defines a struct Widget:

// crate widget
#[derive(PartialEq, Eq)]
pub struct Widget {
    pub name: String,
    pub code: u32,
}

As you can see, the crate has derived Eq, but neglected to derive Hash. Now, I am writing another crate, widget-factory that depends on widget. I’d like to store widgets in a hashset, but I can’t, because they don’t implement Hash! Today, if you want Widget to implement Hash, the only way is to open a PR against widget and wait for a new release.¹ But if we didn’t have the orphan rule, we could just define Hash ourselves:

// Crate widget-factory
impl Hash for Widget {
    fn hash(&self) {
        // PSA: Don’t really define your hash functions like this omg.
        self.name.hash() ^ self.code.hash()
    }
}

Now we can define our WidgetFactory using HashSet<Widget>…

pub struct WidgetFactory {
    produced: HashSet<Widget>,
}

impl WidgetFactory {
    fn take_produced(&mut self) -> HashSet<Widget> {
        self.produced.take()
    }
}

OK, so far so good, but what happens if somebody else defines a widget-delivery crate and they too wish to use a HashSet<Widget>? Well, they will also define Hash for Widget, but of course they might do it differently — maybe even very badly:

// Crate widget-factory
impl Hash for Widget {
    fn hash(&self) {
        // PSA: You REALLY shouldn’t define your hash functions this way omg
        0
    }
}

Now the problem comes when I try to develop my widget-app crate that depends on widget-delivery and widget-factory. I now have two different impls of Hash for Widget, so which should the compiler use?

There are a bunch of answers we might give here, but most of them are bad:

• We could have each crate use its own impl, in theory: but that wouldn’t work so well if the user tried to take a HashSet<Widget> from one crate and pass it to another crate.
• The compiler could pick one of the two impls arbitrarily, but how do we know which one to use? In this case, one of them would give very bad performance, but it’s also possible that some code is designed to expect the exact hash algorithm it specified.
  • This is even harder with associated types.
• Users could tell us which impl they want, which is maybe better, but it also means that the widget-delivery crates have to be prepared that any impl they are using might be switched to another one by some other crate later on. This makes it impossible for us to inline the hash function or do other optimizations except at the very last second.

Faced with these options, we decided to just rule out orphan impls altogether. Too much hassle!

But the orphan rules make it hard to establish a standard

The orphan rules work well at ensuring that we can link two crates together, but ironically they can also work to make actual interop much harder. Consider the async runtime situation. Right now, there are a number of async runtimes, but no convenient way to write code that works with any runtime. As a result, people writing async libraries often wind up writing directly against one specific runtime. The end result is that we cannot combine libraries that were written against different runtimes, or at least that doing so can result in surprising failures.

It would be nice if we could implement some traits that allowed for greater interop. But we don’t quite know what those traits should look like (we also lack support for async fn in traits, but that’s coming!), so it would be nice if we could introduce those traits in the crates.io ecosystem and iterate a bit there — this was indeed the original vision for the futures crate! But if we do that, in practice, then the same crate that defines the trait must also define an implementation for every runtime. The problem is that the runtimes won’t want to depend on the futures crate, as it is still unstable; and the futures crate doesn’t want to have to depend on every runtime. So we’re kind of stuck. And of course if the futures crate were to take a dependency on some specific runtime, then that runtime couldn’t later add futures as a dependency, since that would result in a cycle.

Distinguishing “I need an impl” from “I prove an impl”

At the end of the day, I think we’re going to have to lift the orphan rule, and just accept that it may be possible to create crates that cannot be linked together because they contain overlapping impls. However, we can still give people the tools to ensure that composition works smoothly.

I would like to see us distinguish (at least) two cases:

• I need this type to implement this trait (which maybe it doesn’t, yet).
• I am supplying an impl of a trait for a given type.

The idea would be that most crates can just declare that they need an impl without actually supplying a specific one. Any number of such crates can be combined together without a problem (assuming that they don’t put inconsistent conditions on associated types).

Then, separately, one can have a crate that actually supplies an impl of a foreign trait for a foreign type. These impls can be isolated as much as possible. The hope is that only the final binary would be responsible for actually supplying the impl itself.

Where clauses are how we express “I need an impl” today

If you think about it, expressing “I need an impl” is something that we do all the time, but we typically do it with generic types. For example, when I write a function like so…

fn clone_list<T: Clone>(v: &[T]) {
    …
}

I am saying “I need a type T and I need it to implement Clone”, but I’m not being specific about what those types are.

In fact, it’s also possible to use where-clauses to specify things about non-generic types…

fn example()
where 
    u32: Copy,
{
{

…but the compiler today is a bit inconsistent about how it treats those. The plan is to move to a model where we “trust” what the user wrote — e.g., if the user wrote where String: Copy, then the function would treat the String type as if it were Copy, even if we can’t find any Copy impl. It so happens that such a function could never be called, but that’s no reason you can’t define it².

Where clauses at the crate scope

What if we could put where clauses at the crate scope? We could use that to express impls that we need to exist without actually providing those impls. For example, the widget-factory crate from our earlier example might add a line like this into its lib.rs:

// Crate widget-factory
where Widget: Hash;

As a result, people would not be able to use that crate unless they either (a) supplied an impl of Hash for Widget or (b) repeated the where clause themselves, propagating the request up to the crates that depend on them. (Same as with any other where-clause.)

The intent would be to do the latter, propagating the dependencies up to the root crate, which could then either supply the impl itself or link in some other crate that does.

Allow crates to implement foreign traits for foreign impls

The next part of the idea would be to allow crates to implement foreign traits for foreign impls. I think I would convert the orphan check into a “deny by default” lint. The lint text would explain that these impls are not permitted because they may cause linker errors, but a crate could mark the impl with #[allow(orphan_impls]) to ignore that warning. Best practice would be to put orphan impls into their own crate that others can use.

Another idea: permit duplicate impls (especially those generated via derive)

Josh Triplett floated another interesting idea, which is that we could permit duplicate impls. One common example might be if the impl is defined via a derive (though we’d have to extend derive to permit one to derive on a struct definition that is not local somehow).

Conflicting where clauses

Even if you don’t supply an actual impl, it’s possible to create two crates that can’t be linked together if they contain contradictory where-clauses. For example, perhaps widget-factory defines Widget as an iterator over strings…

// Widget-factory
where Widget: Iterator<Item = String>;

…whilst widget-lib wants Widget to be an iterator over UUIDs:

// Widget-lib
where Widget: Iterator<Item = UUID>;

At the end of the day, at most one of these where-clauses can be satisfied, not both, so the two crates would not interoperate. That seems inevitable and ok.

Expressing target dependencies via where-clauses

Another idea that has been kicking around is the idea of expressing portability across target-architectures via traits and some kind of Platform type. As an example, one could imagine having code that says where Platform: NativeSimd to mean “this code requires native SIMD support”, or perhaps where Platform: Windows to mean “this msut support various windows APIs. This is just a “kernel” of an idea, I have no idea what the real trait hierarchy would look like, but it’s quite appealing and seems to fit well with the idea of crate-level where-clauses. Essentially the idea is to allow crates to “constrain the environment that they are used in” in an explicit way.

Module-level generics

In truth, the idea of crate-level where clauses is kind of a special case of having module-level generics, which I would very much like. The idea would be to allow modules (like types, functions, etc) to declare generic parameters and where-clauses.³ These would be nameable and usable from all code within the module, and when you referenced an item from outside the module, you would have to specify their value. This is very much like how a trait-level generic gets “inherited” by the methods in the trait.

I have wanted this for a long time because I often have modules where all the code is parameterized over some sort of “context parameter”. In the compiler, that is the lifetime ’tcx, but very often it’s some kind of generic type (e.g., Interner in salsa).

Conclusion

I discussed a few things in this post:

• How coherence helps composability by ensuring that crates can be linked together, but harms composability by making it much harder to establish and use interoperability traits.
• How crate-level where-clauses can allow us to express “I need someone to implement this trait” without actually providing an impl, providing for the ability to link things together.
• A sketch of how crate-level where-clauses might be generalized to capture other kinds of constraints on the environment, such as conditions on the target platform, or to module-level generics, which could potentially be an ergonomic win.

Overall, I feel pretty excited about this direction. I feel like more and more things are becoming possible if we think about generalizing the trait system and making it more uniform. All of this, in my mind, builds on the work we’ve been doing to create a more precise definition of the trait system in a-mir-formality and to build up a team with expertise in how it works (see the types team RFC). I’ll write more about those in upcoming posts though! =)

Both of these features fit nicely into the less rigamarole part of the lang team Rust 2024 roadmap. That is, they allow the compiler to be smarter and require less annotation from you to figure out what code should be legal. Interestingly, as a direct result of that, they both also carry the same downside: semver hazards.

What is a semver hazard?

A semver hazard occurs when you have a change which feels innocuous but which, in fact, can break clients of your library. Whenever you try to automatically figure out some part of a crate’s public interface, you risk some kind of semver hazard. This doesn’t necessarily mean that you shouldn’t do the auto-detection: the convenience may be worth it. But it’s usually worth asking yourself if there is some way to lessen the semver hazard while still getting similar or the same benefits.

Rust has a number of semver hazards today.¹ The most common example is around thread-safety. In Rust, a struct MyStruct is automatically deemed to implement the trait Send so long as all the fields of MyStruct are Send (this is why we call Send an auto trait: it is automatically implemented). This is very convenient, but an implication of it is that adding a private field to your struct whose type is not thread-safe (e.g., a Rc<T>) is potentially a breaking change: if someone was using your library and sending MyStruct to run in another thread, they would no longer be able to do so.

What is “perfect derive”?

So what is the perfect derive feature? Currently, when you derive a trait (e.g., Clone) on a generic type, the derive just assumes that all the generic parameters must be Clone. This is sometimes necessary, but not always; the idea of perfect derive is to change how derive works so that it instead figures out exactly the bounds that are needed.

Let’s see an example. Consider this List<T> type, which creates a linked list of T elements. Suppose that List<T> can be deref’d to yield its &T value. However, lists are immutable once created, and we also want them to be cheaply cloneable, so we use Rc<T> to store the data itself:

#[derive(Clone)]
struct List<T> {
    data: Rc<T>,
    next: Option<Rc<List<T>>>,
}

impl<T> Deref for List<T> {
    type Target = T;

    fn deref(&self) -> &T { &self.data }
}

Currently, derive is going to generate an impl that requires T: Clone, like this…

impl<T> Clone for List<T> 
where
    T: Clone,
{
    fn clone(&self) {
        List {
            value: self.value.clone(),
            next: self.next.clone(),
        }
    }
}

If you look closely at this impl, though, you will see that the T: Clone requirement is not actually necessary. This is because the only T in this struct is inside of an Rc, and hence is reference counted. Cloning the Rc only increments the reference count, it doesn’t actually create a new T.

With perfect derive, we would change the derive to generate an impl with one where clause per field, instead. The idea is that what we really need to know is that every field is cloneable (which may in turn require that T be cloneable):

impl<T> Clone for List<T> 
where
    Rc<T>: Clone, // type of the `value` field
    Option<Rc<List<T>>: Clone, // type of the `next` field
{
    fn clone(&self) { /* as before */ }
}

Making perfect derive sound was tricky, but we can do it now

This idea is quite old, but there were a few problems that have blocked us from doing it. First, it requires changing all trait matching to permit cycles (currently, cycles are only permitted for auto traits like Send). This is because checking whether List<T> is Send would not require checking whether Option<Rc<List<T>>> is Send. If you work that through, you’ll find that a cycle arises. I’m not going to talk much about this in this post, but it is not a trivial thing to do: if we are not careful, it would make Rust quite unsound indeed. For now, though, let’s just assume we can do it soundly.

The semver hazard with perfect derive

The other problem is that it introduces a new semver hazard: just as Rust currently commits you to being Send so long as you don’t have any non-Send types, derive would now commit List<T> to being cloneable even when T: Clone does not hold.

For example, perhaps we decide that storing a Rc<T> for each list wasn’t really necessary. Therefore, we might refactor List<T> to store T directly, like so:

#[derive(Clone)]
struct List<T> {
    data: T,
    next: Option<Rc<List<T>>>,
}

We might expect that, since we are only changing the type of a private field, this change could not cause any clients of the library to stop compiling. With perfect derive, we would be wrong.² This change means that we now own a T directly, and so List<T>: Clone is only true if T: Clone.

Expanded implied bounds

An implied bound is a where clause that you don’t have to write explicitly. For example, if you have a struct that declares T: Ord, like this one…

struct RedBlackTree<T: Ord> { … }

impl<T: Ord> RedBlackTree<T> {
    fn insert(&mut self, value: T) { … }
}

…it would be nice if functions that worked with a red-black tree didn’t have to redeclare those same bounds:

fn insert_smaller<T>(red_black_tree: &mut RedBlackTree<T>, item1: T, item2: T) {
    // Today, this function would require `where T: Ord`:
    if item1 < item2 {
        red_black_tree.insert(item);
    } else {
        red_black_tree.insert(item2);
    }   
}\

I am saying expanded implied bounds because Rust already has two notions of implied bounds: expanding supertraits (T: Ord implies T: PartialOrd, for example, which is why the fn above can contain item1 < item2) and outlives relations (an argument of type &’a T, for example, implies that T: ‘a). The most maximal version of this proposal would expand those implied bounds from supertraits and lifetimes to any where-clause at all.

Implied bounds and semver

Expanding the set of implied bounds will also introduce a new semver hazard — or perhaps it would be better to say that is expands an existing semver hazard. It’s already the case that removing a supertrait from a trait is a breaking change: if the stdlib were to change trait Ord so that it no longer extended Eq, then Rust programs that just wrote T: Ord would no longer be able to assume that T: Eq, for example.

Similarly, at least with a maximal version of expanded implied bounds, removing the T: Ord from BinaryTree<T> would potentially stop client code from compiling. Making changes like that is not that uncommon. For example, we might want to introduce new methods on BinaryTree that work even without ordering. To do that, we would remove the T: Ord bound from the struct and just keep it on the impl:

struct RedBlackTree<T> { … }

impl<T> RedBlackTree<T> {
    fn len(&self) -> usize { /* doesn’t need to compare `T` values, so no bound */ }
}

impl<T: Ord> RedBlackTree<T> {
    fn insert(&mut self, value: T) { … }
}

But, if we had a maximal expansion of implied bounds, this could cause crates that depend on your library to stop compiling, because they would no longer be able to assume that RedBlackTree<X> being valid implies X: Ord. As a general rule, I think we want it to be clear what parts of your interface you are committing to and which you are not.

PSA: Removing bounds not always semver compliant

Interestingly, while it is true that you can remove bounds from a struct (today, at least) and be at semver complaint³, this is not the case for impls. For example if I have

impl<T: Copy> MyTrait for Vec<T> { }

and I change it to impl<T> MyTrait for Vec<T>, this is effectively introducing a new blanket impl, and that is not a semver compliant change (see RFC 2451 for more details).

Summarize

So, to summarize:

• Perfect derive is great, but it reveals details about your fields—- sure, you can clone your List<T> for any type T now, but maybe you want the right to require T: Clone in the future?
• Expanded implied bounds are great, but they prevent you from “relaxing” your requirements in the future— sure, you only ever have a RedBlackTree<T> for T: Ord now, but maybe you want to support more types in the future?
• But also: the rules around semver compliance are rather subtle and quick to anger.

How can we fix these features?

I see a few options. The most obvious of course is to just accept the semver hazards. It’s not clear to me whether they will be a problem in practice, and Rust already has a number of similar hazards (e.g., adding a Box<dyn Write> makes your type no longer Send).

Another extreme alternative: crate-local implied bounds

Another option for implied bounds would be to expand implied bounds, but only on a crate-local basis. Imagine that the RedBlackTree type is declared in some crate rbtree, like so…

// The crate rbtree
struct RedBlackTree<T: Ord> { .. }
…
impl<T> RedBlackTree<T> {
    fn insert(&mut self, value: T) {
        …
    }
}

This impl, because it lives in the same crate as RedBlackTree, would be able to benefit from expanded implied bounds. Therefore, code inside the impl could assume that T: Ord. That’s nice. If I later remove the T: Ord bound from RedBlackTree, I can move it to the impl, and that’s fine.

But if I’m in some downstream crate, then I don’t benefit from implied bounds. If I were going to, say, implement some trait for RedBlackTree, I’d have to repeat T: Ord…

trait MyTrait { }

impl<T> MyTrait for rbtrait::RedBlackTree<T>
where
    T: Ord, // required
{ }

A middle ground: declaring “how public” your bounds are

Another variation would be to add a visibility to your bounds. The default would be that where clauses on structs are “private”, i.e., implied only within your module. But you could declare where clauses as “public”, in which case you would be committing to them as part of your semver guarantee:

struct RedBlackTree<T: pub Ord> { .. }

In principle, we could also support pub(crate) and other visibility modifiers.

Explicit perfect derive

I’ve been focused on implied bounds, but the same questions apply to perfect derive. In that case, I think the question is mildly simpler— we likely want some way to expand the perfect derive syntax to “opt in” to the perfect version (or “opt out” from it).

There have been some proposals that would allow you to be explicit about which parameters require which bounds. I’ve been a fan of those, but now that I’ve realized we can do perfect derive, I’m less sure. Maybe we should just want some way to say “add the bounds all the time” (the default today) or “use perfect derive” (the new option), and that’s good enough. We could even make there be a new attribute, e.g. #[perfect_derive(…)] or #[semver_derive]. Not sure.

Conclusion

In the past, we were blocked for technical reasons from expanding implied bounds and supporting perfect derive, but I believe we have resolved those issues. So now we have to think a bit about semver and decide how much explicit we want to be.

Side not that, no matter what we pick, I think it would be great to have easy tooling to help authors determine if something is a semver breaking change. This is a bit tricky because it requires reasoning about two versions of your code. I know there is rust-semverer but I’m not sure how well maintained it is. It’d be great to have a simple github action one could deploy that would warn you when reviewing PRs.