Implementing traits and types for multiple foreign crates (pre-RFC)


#1

It often leads to problems, when I want to implement a trait of one crate for a type of another crate. I’m thinking about ways how this problem could be solved in a not too complex way. Besides of const genercis, this seems like a pretty important feature to me.

The problem occurs, when I have at least two independant crates and want to define traits, that contain only types and traits, which are not defined in the current crate.

Here some examples with fictional crates:

use renderer::Draw; // a trait for drawing something
use shapes::Circle; // some shapes and common operations on them (intersection, volume, etc.)

impl Draw for Circle {…}

In this case it would probably be useful to have a wrapper type. But redefining every needed function for a wrapper type seems complicated in most cases.

use physics::Vector as VectorP; // a vector optimized for physics
use graphics::Vector as VectorG; // a vector optimized for graphics

impl From<VectorP> for VectorG {…}
impl From<VectorG> for VectorP {…}

Here a wrapper type would not be useful. Instead, it would be possible to use a new vector type and define From for all vector types or an exisiting type where both already can be converted into.

Instead it may be useful to use a common vector type, where multiple crates depend on, but that may also be a problematic solution, if one lib just uses vectors, one implements vectors generically as special case of matrices and one implements vectors generically as special case of multivectors.

It would be possible to change one of the crates yourself, for example by adding optional dependencies of the other crate, but if they really are independend, that also seems not like a good solution.

There were some approaches to solve this problem, but they allowed multiple implementations of the same trait, which seems too confusing and useless for most use cases.

So here are my some ideas, I had in mind, which aim to solve these problem. If one of my approaches seems interesting, I’ll write an RFC for it.

Approaches

Local impls

The most trivial solution to most problems is to allow local impls. This means, that an implementation is only used in the current crate but not exported to other crates.

In order to avoid breakage, local impls are also allowed, if there already exists an implementation. If one of the used crates implements it later, it won’t break anything. A local impl could look like this:

#[local_impl]
impl Draw for Circle {…}

// or using keywords
crate impl Draw for Circle {…}

// or using keywords
crate impl Draw for Circle {…}
priv impl Draw for Circle {…}

If the impl already exists in some extern crate, it will be warned by default.

This won’t solve more complicated use cases, where the new implementations are reexported.

Therefore I have some other ideas.

Extender crates

This will allow to extend foreign crates. This is similar to adding optional dependencies to a crate, but will be possible inside a new crate.

Everything in the new crate, called extender crate, acts as if it is defined in the extended crate and so can define traits on types, even if none of them is in the new crate. A crate can define at most one crate to be extended.

If crate uses multiple extender crates, only one is allowed per crate. Else multiple extender crates may define the same traits on the same types. Instead one is allowed to extend an extender crate further.

The rules for cyclic dependencies also have to be different for extender crates.

For example when crate X extends A and depends on B, and crate Y extends B and depends on A, they may both implement the same additional traits. So when some other crate depends on X and Y it may cause multiple implementations of the same traits on the same objects.

Therefore in order to compute cyclic dependencies. Since an extender crate is seen as if all were defined in the crate itself, every crate, that depends on a crate, implicitely depends on the extender crate. So X depends on B and implicitely depends on Y, which depends on A and implicitely depends on X, so this is a cyclic crate definition.

Optional additions

It may be a good addition to not allow implementations of combinations of traits and types, that could be implemented inside the extended crate. Else it may be possible to This will also allow multiple extender crates for the same crate, as long as they have different dependencies.

But in may be pretty common to have multiple dependencies, and if one of them is not used by the extended crate, it won’t be possible to use both extender crates, even if the implemented traits are the same.

Glue crates

In order to fix this, it would be useful to be able to specify, which other crates are used, to implement the new traits. So it doesn’t extend a single crate anymore, but a set of crates, and now has some restrictions. This won’t be called extender crate, but glue crate. Every glue crate specifies some sets of crates. Each of these sets has exactly two elements. Both crates in this set are then glued together. If a set has more than two elements it will be decomposed into all subsets, which have exactly two elements. A glue crate also won’t need a special check for cyclic dependencies. Instead two crates are not compatible, if one of its glue sets is equal.

Crate X, which glues A and B may implement the following:

use A::Trait;
use B::Type;
impl Trait for Type {…}

It may also implement more complicated traits, as long one type or trait is in crate A and one is in crate B:

use A::Type as TypeA;
use B::Type as TypeB;
impl From<TypeA> for Vec<TypeB> {…}

Even this should be possible:

use A::Trait;
use B::Type;
impl<T> Trait<Type> for T {…}

The rules for using of new types and traits inside a glue crate is as in other crates, so there are no problems. But it may be useful to forbid adding new types and traits in glue crates (at least public ones) so it is just there for gluing things together and will not export anything.

Adding dependencies later

A problem may occur, when adding dependencies between both crates later. For example if the crate for physics vectors implements a converter from and into graphics vectors. If it’s an optional dependency, then it’s not a problem to use the matching extender or glue crates, when the dependency isn’t used. Other extender or glue crates will break, when they glue it and one of the new dependencies.

This could be fixed by explicitely adding, which crates will be used for trait impl, to the configuration of the crate. This way new crates are not implictely allowed to use std. So if I define a vector math library, I probably would add std, so I can implement my traits for the types in std and implement the traits of std for my vector types. I also may implement num-traits. But some user of my crate may want to implement the alga traits for my vector math, which is possible, since I didn’t explicitely add it to my crate. I may even use alga later in my crate without breaking anything, but am not allowed to implement any traits (except using local_impl, if this also exists) It’s not required to depend on std, when I do this:

struct Vector<T>…;

impl<T,U> From<Vector<T>> for Vector<U> where U: From<T> {…}
// this is currently a problem anyway, because the default definition (From<T> for T) exists and cannot be specialized

The reason is, that at least two types of my own crate participate.

If only one trait takes part on the implementation, it’s also allowed without explicitely adding a crate:

trait Test {…}

impl<T> Test for T {…}

It will still be allowed, not to explicitely add the impls of each crate, but then adding glue crates may cause problems, when adding new dependencies. By default just all dependencies are allowed for implementing new traits on the new types.

New types

Another approach, based on the wrapper type stategy, is a way to copy types and all things implemented on them. This could look like this:

struct Vector = physics::Vector;

The new type Vector defined like this, may work as if it was defined using type, but it’s a new type as defined with a default structs. All public fields and function impls will be derived for this type. In order to derive the existing trait implementations, this has to be done explicitely, and may be complicated. This may also be implementable as a macro.

If too many types would have to be redefined this way, this won’t be a good approach.

instead they may even be implemented implicitely when using, like this:

use impl physics::Vector;

This will create a new type, that implements all public fields and functions.

It could also implement the traits by default, that are already implemented in physics. When using other crates, that implement something on physics::Vector, it won’t be implemented by default. In order to use a more specialized version of a struct, the crate, which uses Vector and implements new structs for it, will have to reexport it. If the vector is not reexported, a special crate can be used for that:

// crate reexport_physics_with_additional_traits;
extern crate physics;
extern crate additional_physics_traits;
pub use physics::Vector;

This is everythign the crate has to do. Now i have to use it in another crate:

use impl reexport_physics_with_additional_traits::Vector;
// this will create a new vector type, which implements all traits accessible inside the crate, it is used from

Now it’s seems already usable, even if a bit complicated with the need of additional crates in some cases.

Conclusion

I hope, some of these ideas sound interesing enough, so I can write an RFC for one of my approach.

At least local_impl should be trivial, but it’s also not that useful. It should be good enough to solve this problem for simple crates.

The extender and glue crate approach seems pretty complicated, but may solve the problem in a clean way.

The ability to declare new types seems not to suit well for this problem, but may at least have some other use cases.

What do you think is worth to get an own RFC in the RFCs section? Are there already other good approaches, I didn’t mention? Do you have other ideas in mind?


#2

If we’re going to try to discuss solutions to this limitation of rust, it should be done with the understanding of why these limitations are in place.

The existing orphan rules protect a property of the language known as coherence. This is the property where, given a type and a trait, all code in the compiled binary agrees on the same implementation for that trait. If incoherent impls are allowed to exist in the language, it can lead to dangerous situations like “the hashtable problem.”

This blog post by @nikomatsakis details some of the thought that went into the current design. I recall there also being some discussion about the interaction between coherence and specialization, though I haven’t been following this story much. There’s some more links to related discussion here.

I’m pretty sure it can be shown that this particular idea leads to incoherent impls, just based on its resemblance to previous ideas. (this comes up pretty frequently)

I haven’t thought much about the other ideas yet, but “extender crates” seems novel to me at least.


#3

In addition to Niko’s blog post, I gave a talk at a meetup a year ago that gets into the benefits of the orphan rules, its the middle talk in this video.

Here are two important constraints that the orphan rules guarantee:

  1. It is not a breaking change to add an impl that is not a blanket impl or an impl of an auto trait or a fundamental trait.
  2. Given any two valid crates, they can be compiled together.

These constraints are extremely important for reducing “dependency hell” that plagues many languages, enabling people to use the crates.io ecosystem with much less distraction & stress than they experience in other ecosystems. Each of your proposals seems to violate at least one of these guarantees.


#4

@withoutboats If I knew, this talk existed, I probably wouldn’t have written this. Most of what I wrote is, what you already talk about there :wink:

So local impls are a problem, because they violate coherency (it’s not wanted, that the same type has different impls in some contexts). I understand now the problem, but at least for testing purposes or maybe binary crates, this may be useful. But having a better way to handle this, would make it useless anyway. New types are already thought about (newtype_derive).

And the problem with extender/glue crates is, that they cannot be compiled together, when they conflict. But needing the author of a crate to implement the matching trait definitions using features (or use a copy of that crate to implement some types oneself) still seems not that good. The posibility to add such an extension as an additional crate would be useful, preferably as what I called glue crates, because you don’t have to specify the “main” crate, which it extends. I think, since they would be a special crate kind, it would be ok to have an exception to the rule. Maybe they would not be handled as new crates but just parts of the extended crate, that are hosted in different repos.