Orphan rules

internals ideas (deprecated)
1

It is clear that the coherence orphan rules as currently implemented are too conservative. At the same time, they used to be too liberal. This turns out to be a hard thing to get right. I wrote up a blog post diving into the various options that have been discussed:

http://smallcultfollowing.com/babysteps/blog/2015/01/14/little-orphan-impls/

This thread is a place to talk about the possible rules we could use etc. My current thoughts are more-or-less covered in the post, but I guess the TL;DR is that I currently favor the rule I call “covered first”, which can be summarized as:

  • For an impl like impl RemoteTrait<B..Z> for A to be legal:
    • One of the types A..Z supplied (let’s call it t) must be local to the crate. t can reference impl type parameters, but they must be “covered”.
    • The types that A..t that come before t must all be external types and cannot reference type parameters.
    • The types t+1..Z that come after t can be anything at all.

It’s somewhat unfortunate to have ordering as an inherent part of the rules, but (as I argue in the post) I think it is possibly inescapable.

But that’s only my current thought. I’d love to find some better alternative.

4 Likes
2

I’m probably quite ignorant of many of the issues surrounding this, so don’t take me too seriously here. But it strikes me that there are actually two separate problems that the orphan rules are trying to solve:

  1. Making it easy for programmers to find trait implementations, by enforcing that they exist in a module with at least one of the involved items.
  2. Enforcing a global constraint that there cannot be duplicate/conflicting trait implementations.

The orphan rules seems well suited to the first issue, because it’s a very localized problem. But the second issue seems… maybe ill-suited to being solved by the orphan rules. The orphan rules are very local, whereas the constraint that we really want to enforce is global.

So what if we go back to the old liberal orphan rules to solve the first problem, and take a more globally-aware approach to solving the second problem. The compiler could keep track of the trait implementations it encounters, and error if it later encounters a conflicting trait implementation, pointing out where the conflicting implementations are.

In other words, instead of trying to find local rules that result in the global constraint we want, why not just directly enforce the global constraint?

Unless there is another purpose to the orphan rules that I’m missing (which is highly possible).

3

A benefit of explicit rules that provably enforce coherence is that any crate author in the future who wanted to rely on two sub-crates simultaneously would be guaranteed to be able to do so. E.g., relying on this example from the blog,

impl<T> Show for (T, MyBigInt) { ... } // in crate A
impl<T> Show for (YourBigInt, T) { ... } // in crate B

by your suggestion, if I understand it correctly, both crate A and crate B would compile and run fine, until the point that they are both used by a crate C that tries to call show on (B::YourBigInt, A::MyBigInt). If all crates are defined in a single project, probably this is fine, but with programming-in-the-large via crates.io, and relying on moving interfaces of externally-defined crates, the likelihood of problems like this arising increases substantially, and the difficulty of coordinating fixes can be significant.

2 Likes
4

I honestly don’t think users would even realize that such rules are necessary or that they exist without finding out the hard way, much less bother to try learn them and even less manage to actually memorize them.

Plus they make it impossible to implement traits in “3rd party” crates.

So this whole approach of enforcing coherence doesn’t really seem viable.

Why not just allow any impl, allow multiple impls, and prioritize impls that are visible via “use” by specificity and then import order?

Regarding the issue in https://mail.mozilla.org/pipermail/rust-dev/2011-December/001036.html , the obvious solution seems to add the found impls to the type signature of generics, so that HashTable[u32] in file1.rs and HashTable[u32] in file2.rs are not the same types if they are using a different impl of Hash for u32 (assuming that HashTable requires that T : Hash).

Note that this requires to put the T: Hash trait bound on the HashTable struct itself rather than on an impl, but that seems the correct thing to do as the Hash implementation does indeed affect the HashTable data itself and it is indeed needed for the Hash impl to be the same for all impls of traits for HashTable.

Of course, putting the bound on the struct itself would need to be done by the user, since putting bounds on impls still needs to be possible and they must not be added to the type signature, so it’s possible to implement HashTable wrong by not doing so, but that’s an understandable error at least.

There’s the further problem that for the language to be fully expressive it would be necessary to be able to make impls a first class object so that a function can refer to multiple different impls of the same trait, but the language should still be usable without this.

As a simple use case of not enforcing coherence, you could have a basic unoptimized but complete implementation of bignums in the core library, and then have an external crate that implements the Add/Sub/… traits on the bignum struct in the std library using GMP.

6

Coherence is really important. Far from being “not viable”, it’s essential.

Having magic specificity rules is much worse than magic coherence rules: if you violate the coherence rules, you get a random compiler error that can usually be worked around with a newtype. But if you misunderstand the specificity rules, your code breaks in that it can call random methods you didn’t expect.

4 Likes
7

That's what Haskell does. The problem is that you can have crate A and crate B that were totally interdependent but provide a conflicting implementation for some random type in another crate, and then crate C can't link to both A and B. That's really annoying when it happens because there's no way to work around it short of rewriting one of the libraries, and it's why Haskell provides orphan instance warnings.

2 Likes
8

It’s always made me uncomfortable to have commutative traits like Add defined for a single receiving type. It seems more natural to define it over a tuple:

trait Add {
    type Output;
    fn add(self) -> Self::Output;
}

impl Add for (u32, u32) {
    type Output = u32;
    fn add(self) -> u32 { /* return self.0 + self.1; */ }
}

This approach is relevant here because it puts the “self-like” types in the actual Self type. Together with the rule that any impl type params appearing in Self must be covered by a local type, this would basically be the “explicit” option.

impl Add for (u32, MyInt) { ... } // legal
impl Add for (MyInt, u32) { ... } // legal
impl<T> Add for (MyNum<T>, u32) { ... } // legal
impl<T> Add for (T, u32) { ... } // error: no local type in Self
impl<T> Add for (MyInt, T) { ... } // error: uncovered "T" in Self

One clear downside is that you can’t express the intended binary-tuple structure of Self in the trait definition. Another is the awkward use of tuple fields like “self.0”. There may be (very likely are) other downsides that I am too ignorant to catch :P.

9

@aidancully I think that case is still prevented by my suggestion, because crate B would have to depend on crate A to have access to MyBigInt in the first place, so the compiler would catch the conflict when compiling crate B because it would be checking against the implementations in A as well.

However, now that I’m thinking about it, a case involving 3 crates does still cause problems:

struct CrateABigInt { ... } // in crate A
impl<T> Show for (T, CrateABigInt) { ... } // in crate B
impl<T> Show for (T, CrateABigInt) { ... } // in crate C

If I have a crate D and I want to use both B and C in it, I’m in trouble. (Though at least this doesn’t prevent me from using either of them–I just have to pick one. This is basically crate conflicts.)

However, looking at this I’m noticing some things which might be useful:

  1. We really only need orphan rules for inter-crate dependencies, because the compiler could handler intra-crate coherence directly.
  2. Even for inter-crate dependencies, if those dependencies form a strict tree then the compiler can still directly enforce inter-crate coherence when compiling the dependant crates without causing problems.
  3. The problematic case that the compiler cannot directly handle (at least, not without causing problems for downstream users of crates) is when there are diamonds in the inter-crate dependency DAG.

So if we can come up with orphan rules to specifically (and narrowly?) address that issue, then we’re golden. Easier said than done, off course.

One possibility that would solve the issue (I think?), but might well be too restrictive: a trait implementation must either involve a concrete reference to a locally defined type, or it must be implementing a locally defined trait.

That would make this illegal:

impl<T> Show for (T, YourBigInt) { ... }

Because T is not a concrete type, it’s a type parameter.

The main downside I can think of is that it would prevent people from effectively implementing traits for other traits, e.g.:

impl<T: MyTrait> Show for (T, YourBigInt) { ... }

Though I’m pretty sure that kind of thing has problems of its own anyway. E.g.:

trait TraitA { ... }
trait TraitB { ... }
trait TraitC { ... }

impl<T: TraitA> TraitC for T { ... }
impl<T: TraitB> TraitC for T { ... }

// Which TraitC impl to use for Foo?
struct Foo { ... }
impl TraitA for Foo { ... }
impl TraitB for Foo { ... }

And that can even be done inside a single module. So if we’re okay with that kind of situation, then the rule could instead be:

“A trait implementation must either involve a concrete reference to a locally defined type, or it must involve a reference to a locally defined trait, or both.”

As always, I may be wildly misunderstanding some things here, and also in all likelihood am missing something. So grain of salt and all that.

10

If I understand the original proposal correctly, what is meant by the statement that one type must be local is equivalent to your “concrete reference”. Also, your proposed rule at the end doesn’t work for reasons explained in Niko’s post.

11

I’m glad to see Rust community tackling the orphan instances problem before to much code accretes that uses one interpretation or another.

As you may be well aware, Haskell’s approach to the orphan problem is to allow conflicting instances to be defined in different compilation units, and complain when those units are linked together. This, of course, gives up the guarantee that linking will never fail, and can result in situations where two libraries simply cannot be used together (which has caused us no end of headache when trying to put type classes and a module system together), so I think Rust is pursuing an admirable goal in trying to guarantee linking will never fail.

I quite like Niko’s proposal (I came up with something similar last summer while thinking about this problem in Haskell’s context), but I do have one suggestion: if the syntax can be figured out, I think it is better if the “ordering” is something that can be specified independently of the actual ordering of type parameters on a per-trait basis. This will help solve many cases where there is a natural ordering, but you really want to dispatch on a specific type parameter, which may not be the first parameter.

As some folks on this thread have already pointed out, by always enforcing orphan rules, you do give up one piece of functionality: the ability to define orphans! Haskell has had orphans from the beginning, and a non-trivial portion of our userbase swears by them. The single most common situation is two third-party libraries have defined a trait and a type respectively, but they did not know each other existed at the time they were written. With any sort of orphan rule which guarantees linking will work, it is no longer possible to define the trait for that type. To make matters worse, this induces libraries to try to include as many traits (or as any types) as possible, so that useful traits can be defined: this bloats dependency lists and generally makes your users unhappy. Orphans can be useful!

4 Likes
12

@pcwalton

What about requiring the user to explicitly specify an impl where more than one is applicable, then? (possibly only if they have the same specificity).

In general, you have exactly the same issue with two crates possibly defining a type or function called “Foo”, and both of them being imported.

Aside from being highly surprising, the fundamental issue with “coherence” is that it cannot allow to implements traits for any type.

For instance, let’s say you want to have these impls: impl<T> TraitFromLibStd for (A, T) impl<T> TraitFromLibStd for (T, B)

Obviously, the first impl must be in the crate defining A (since there are no other crates related to the impl), and the second impl in the crate definining B, but they both have an impl for (A, B), and thus one must be disallowed.

With ordering, you can allow one of them, but it makes tuples and generics asymmetric in their types.

1 Like
13

Yes, I’ve considered advocating this in the past, and this is certainly relevant. One problem is that sometimes you wish to reference the individual types of the tuple in the method signature. For example, suppose we wanted to retain the trait definition of Add we have today. You could actually do it like so:

/// Add is conventionally bound to a tuple.
trait Add {
    type Left;
    type Right;
    type Output;

    fn add(self: Self::Left, right: Self::Right) -> Self::Output;
}

impl Add for (u32, u32) {
    type Left = u32;
    type Right = u32;
    type Output = u32;
    ...
}

but it adds a level of tedium and repetition.

However, it does show that the “orphan self” rule that I proposed and the “explicit” rule are actually one and the same. In particular, you can add additional “self-like” parameters by having the convention that they be packed into a tuple. This was something that aturon and I had in mind when we settled on implementing the “orphan self” rule. However, I confess I’ve shied away from recommending this approach to reem etc. It just feels like such a workaround. It also implies that you lose method syntax unless you are invoking on the tuple (which I personally think is kind of ok in many cases, but others may disagree).

14

@bill_myers, while I appreciate the points you are making, we litigated the issue of coherence vs multiple impls long ago, and I am not inclined to revisit this question right now, on the eve of the 1.0 release. Getting the design of such a feature right would be a major change to Rust’s philosophy. Introducing “incoherent traits” remains an option for the future, and I stand by the design I sketched out in that e-mail long ago, but the focus on impls and not traits cause some real ergonomic annoyances. Among them, the need to import numerous impls so that you could invoke methods was quite irritating (much more so than the need to import traits today – you only have to import the trait once, not for every type you are using it with!). Long story short, this is perhaps a good idea for a feature, but it’s one that will require some time and care put into it, and not something we can add at the drop of a hat.

15

Interesting. This seems similar to the variant I suggested where the user distinguishes explicit from auxiliary traits, but instead with a focus on ordering. It also seems like something we could add as a backwards compatible extension once people are clamoring for it (though no individual trait could adopt a distinct ordering with potentially breaking downstream impls). Can you give an example where there is a natural ordering but Self is not the type on which you would want to dispatch?

Yes. This is definitely a trade-off. You gain guaranteed linking but it can still happen that two libraries cannot (easily) be made to work together since one library defines a trait that the other does not implement. I guess one important point is that there do exist workarounds to the latter problem but not the former. I imagine that in the future we will try to find extensions that ameliorate this problem. Introducing incoherent traits is one possibility. In some cases, permitting specialization can help (because the root crate can provide a blanket impl that others can then specialize to their liking). Another option that has been tossed about is the idea that while a library crate may not provide orphans, it is plausible for an executable crate to do so. This seems to imply that one could combine libraries together where impls are missing and only provide those impls at the last step. However, that seems like it would ultimately lead to the same problems you are describing -- libraries might ship based on some assumption of what a trait means for a given type, assuming that this assumption will be fulfilled in the final crate, and that assumption may not be compatible with what another library expects.

1 Like
16

@nikomatsakis

Yes, they only possible way forward seems to figure out a coherence rule for now and possibly add non-coherent impls after 1.0.

Regarding, the “self-like” vs auxiiary type parameter issue, what if trait declarations were changed to explicitly spell out the self type and regarding parameters on the trait itself as auxiliary?

That is, current trait declarations would become (probably also keeping the current syntax as sugar for this):

trait<Self> Foo for Self { ... }

And then Add could be declared like this:

trait<A, B> Add for (A, B) { type Output; fn add(a: A, b: B) -> Output; }

This means that A and B would both be self-like since they are part of the self type pattern.

This would let users distinguish auxiliary and self-type parameters in a very intuitive way that doesn’t require to learn an extra modifier.

Inheritance between traits could then be expressed like this: trait<Self> DerivedTrait for Self where Self : BaseTrait {

}

This also makes the language more expressive overall beyond addressing the coherence issue and I think allows to eliminate special treatment of Self beyond syntax sugar.

17

@bill_myers yes, that is precisely what I was referring to in the “explicit” section. You can see the tradeoff there in terms of expressiveness. I did not spell out specific syntax but that is the idea I had in mind.

This can also be modeled today as I wrote here http://discuss.rust-lang.org/t/orphan-rules/1322/13?u=nikomatsakis

18

Interesting. This seems similar to the variant I suggested where the user distinguishes explicit from auxiliary traits, but instead with a focus on ordering. It also seems like something we could add as a backwards compatible extension once people are clamoring for it (though no individual trait could adopt a distinct ordering with potentially breaking downstream impls). Can you give an example where there is a natural ordering but Self is not the type on which you would want to dispatch?

Oops, it looks like you've already considered this case. I think your proposal already captures this possibility, since I was thinking specifically about dispatch on self type. I retract my suggestion!

I guess one important point is that there do exist workarounds to the latter problem but not the former.

Do you mean using newtypes? Well, it's not cost free, both efficiency-wise (consider a list of T, and you need to newtype T. Richard and company wrote a paper about how to implement coercions so newtypes would be cost-free in this circumstance) and usability-wise (great, now you have to reimplement every function you want to use on the newtype.) Yes, in principle you can work around it but it can be pretty painful.

it can still happen that two libraries cannot (easily) be made to work together since one library defines a trait that the other does not implement.

I actually think the situation is worse than that. Let me try to give a concrete example. Suppose that I'm a library writer, writing a BSON (like JSON but binary) library. An obvious thing to want to do is provide a ToBson trait.

It will be pretty normal for me to provide impls for any types which are in the standard library. But what about types that live outside: should I give an impl for mysql::value::Value in rust-mysql-simple? Well, maybe someone who uses BSON and that library would find this impl useful. But obviously the core BSON library shouldn't depend on rust-mysql-simple, that would just be silly. Nor should rust-mysql-simple depend on BSON: what does BSON serializing have anything to do with querying the database?

The obvious thing to do: put the bson/rust-mysql-simple adapter in its own crate, is disallowed under any permutation of the orphan rules. And it must be, because what do you do if two people write adapters? But it's the "common sense" way of how to solve the problem.

Introducing incoherent traits is one possibility.

There is a way to do this properly, although I suspect the ship may have already sailed for Rust. In Dreyer et al's Modular Type Classes, the possibility of multiple instances being available for one type is planned for the same type is accounted for from the start. You're not allowed to have incoherent resolution (i.e. the type checker should not have to make an arbitrary choice), but you can selectively expose/hide instances in scopes. This is the other logical conclusion after you axiomatize "linking should not fail." The further conclusion is that users must not assume traits are global when constructing data types; so the types you've given to, e.g. std::collections::BinaryHeap, are no good.

There is a way to support something like BinaryHeap however: the key is that a BinaryHeap type should be specialized to a specific trait. (In the standard ML module lingo, BinaryHeap is a functor, and the trait is passed in as a parameter module. Then Applicative Functor semantics specifies that IF the parameter modules are equal, then the instantiated functor--and its internal types--are equal as well.) Then when you use any of the operations, the specific trait you specialized is used; furthermore, a BinaryHeap with the same element type but a different trait is incompatible and you can't, e.g. merge them. Unfortunately, I suspect that the Rust team will not be so keen on (1) adding a whole new type system feature and (2) changing all of the core library definitions at this stage in the game. Plus, Scala tried to allow local type class instances, but completely failed on the type system front and ended up with something worse. But if I could go back in time, I'd figure out how to make this work for Haskell and fix our standard libraries to do this properly.

However, that seems like it would ultimately lead to the same problems you are describing -- libraries might ship based on some assumption of what a trait means for a given type, assuming that this assumption will be fulfilled in the final crate, and that assumption may not be compatible with what another library expects.

Well, I actually don't think this is too much of a problem: if you ship a library that leaves the trait unspecified except for some contract, it seems reasonable to expect the final crate to need to fulfill the contract but otherwise be given latitude in the implementation choice. There are lots of other cases where user code might not fulfill a contract, and Rust has no way of checking.

19

[quote=“nikomatsakis, post:13, topic:1322”] However, I confess I’ve shied away from recommending this approach to reem etc. It just feels like such a workaround. It also implies that you lose method syntax unless you are invoking on the tuple (which I personally think is kind of ok in many cases, but others may disagree). [/quote] Looking around, “self-like” parameters are not always treated symmetrically (e.g. in iron’s Modifier trait), so tuples-for-Self isn’t a panacea. I do wish it was easier to use tuples when appropriate, e.g. for Add, but it looks like a separate issue from impl coherence.

20

Dependence on the order of parameters sounds alarming and counterintuitive. There is no other place in the language where the order of homogenous items in a list (apart from self) is important, and it feels a good property to maintain.

It will be appalling if developers can “paint themselves into a corner” by stabilizing a generic trait to discover later on that people are prevented from making certain impls by mere choice of the order of trait’s parameters.

Overall, the need to come up with rules like that may be a sign that the language is getting close to a complexity explosion of C++'s magnitude. Could it be an opportunity to stand back, cut down to a simpler set of rules that can be understood to an operative level by a good share of the developers, and cover the remaining ground by other means?

As an example, I tried to come up with a transitively implemented trait for single inheritance based on manually defined parent-child relationship traits. I was unable to get this past the current orphan checker and I have doubts it will ever be possible. But what if the compiler could implicitly generate non-generic impls for a type implementing a trait with a certain attribute:

#[auto_derive(Base)]
pub trait Derived { /* ... */ }
21

What about “covered self || covered everything else”:

  • impl<T…> RemoteTrait<B…> for A is legal if:
    1. A is local, and covers all impl type parameters T…, or
    2. A is external and doesn’t contain T…, and B… is not empty, and B… are all local and covers T….
    3. It is illegal otherwise (e.g. if A is contains non-covered T….)

There, we have eliminated order dependency.

This is exactly the same as covered-first for ≤1 type parameters (most of the cases), and is stricter than covered-first for ≥2 type parameters.