Revisit Orphan Rules

[mboratko]

The newtype workaround has lots of disadvantages which I mentioned in my original post aside from being inconvenient or tedious.

Specialization is orthogonal to what I propose here.

You can pass S into some other crate that invokes S’s impl of T, but the preference is not set globally.

[Ixrec]

Wait, did you say Vec<f64>:my::Hash is a type? Not the type Vec<f64> with some sort of annotation, but an actual separate type?

Making it a separate type appears to solve the immediate question posed by @ExpHP, but that also appears to introduce a brand new dimension of subtyping into Rust, which… I dunno if that’s gonna work. And if it’s not a separate type, then I think @ExpHP is right that this still requires a form of global reasoning to actually work.

Specialization is orthogonal to what I propose here.

Clearly we’d like them to be orthogonal, but just saying so is not an argument that it is so.

It seems clear that there’s a non-trivial interaction at least. If crate A has an impl Trait of T, and crate B specializes that with impl Trait of BType, and my create C does something with BType:A::Trait, what happens?

I have no idea what should happen or whether there’s an actual problem with “just use the specialized impl from B”, but it seems like something we clearly need to think about more before we can be sure it really does work.

[mboratko]

Yes, it would be a type I think, but since this is part of @nikomatsakis’s idea and he mentioned at the end of it that he had some thoughts about the implementation I will defer to him on that part of it.

[Ixrec]

Interesting. So are you imagining Vec<f64>:my::Hash to be a sort of sugar over the newtype pattern (in which case we’re back to @ExpHP’s post), or an actual subtype with all the complications that a new subtyping dimension brings to the table?

[mboratko]

The fact that it is orthogonal follows from the statement that there are two steps:

1. Without a impl annotation, some form of default impl is chosen. This is where any specialization rules would come into play.
2. If the compiler cannot disambiguate, manual impl annotation is required.

[ExpHP]

Wait, did you say Vec<f64>:my::Hash is a type? Not the type Vec<f64> with some sort of annotation, but an actual separate type?

This is, as I understand it, the core of the proposal.

Since opaque(a) moves a and then returns it, it would have type Vec<f64>:my::Hash . If you then try to do expecting_bob(opaque(a)) , this is where a type error would occur, no different than expecting_bob(a) .

Right. As I said, that is global analysis, which is highly uncharacteristic of Rust, a language that prides itself in having the signature of a function indicate all that is necessary to decide where it can be used. (which is a useful property that allows for decent error messages. Contrast with C++…)

fn func_1(vec: Vec<f64>) -> Vec<f64> { vec }
fn func_2(vec: Vec<f64>) -> Vec<f64> { vec.into_iter().collect() }

type VecFn = fn(Vec<f64>) -> Vec<f64>;

fn foo() {
    let funcs: Vec<VecFn> = vec![func_1 as _, func_2 as _];

    // hand off to some crate that accepts `&[fn(Vec<f64>) -> Vec<f64>]`
    some_crate::have_some_funcs(&funcs)
}

Now suppose some_crate::have_some_funcs does what I previously mentioned, supplying a Vec<f64>:my::Hash and expecting a Vec<f64>:bob::Hash. Where is the error message now?

[mboratko]

I think I presented this poorly. My intention was that the “simple solution” would be easier to swallow, and then bringing up @nikomatsakis’s more advanced solution would make sense. I will add additional details to my original post suggesting users read fully @nikomatsakis’s proposed solution, which has more details. In particular, he states:

Next, we say that the value for a type variable is not just a type, like uint, but rather a tuple type : impl* of a type and zero or more implementations, one for each interface bound.

So yes, it would be a type.

[Ixrec]

I think niko’s gist might be a bit too old to use as a reference here. If I’m reading it right, it predates the existence of things like trait bounds on type parameters and trait objects, both of which clearly exist today and thus a huge chunk of the gist actually is part of stable Rust already. In fact, it doesn’t mention anything about multiple crates or breaking changes or orphan rules, so I don’t think it was ever meant to apply to the problems we’re discussing here. What’s suggested there wouldn’t even solve the opaque() case, because @ExpHP’s opaque() function is not a generic function, so there’s no type parameters to carry the impl annotations.

More importantly, that gist seems to only be considering generic code, because it’s all about whether and how generic code should select its trait impls at compile time or runtime (which is basically set in stone nowadays). Since the problems we’re discussing are not specific to generic code, I think that gist simply doesn’t apply.

If the goal is just to extract the “what if types came with a ‘use this impl’ tag?” idea and turn it into a concrete proposal relevant to today’s orphan rules dilemma, then I’m pretty sure we end up with either global reasoning or a new form of subtyping, as discussed above.

[mboratko]

Unless I’ve totally misunderstood, it is precisely about overlapping impls:

This looks reasonable. Now we create two modules, Module1 and Module2, which both share a reference to the same hashtable, but which have different implementations of the hash interface in scope:

It is not only focused on generic code:

fn bar(h: @ht::t<uint: Module2::hash, str>) { ... }

Here we are specifying uint : Module2::hash.

[Ixrec]

it is precisely about overlapping impls:

That much is true, because “overlapping impls” is a much broader topic (involving specialization, generics, traits, etc) than the orphan rules dilemma I thought this thread was about.

It is not only focused on generic code:

Hm, yeah I overstated that part.

It does contain that example of a function bar with a concrete type-plus-impl-annotation parameter, but it also appears to say that any non-generic function lacking the same exact set of impl annotations would simply not compile if it called or was called by bar, which afaik basically makes it sugar for a newtype. Which I assumed wasn’t relevant because you appear to be proposing something more than newtype sugar, right?

[kornel]

I’d prefer this problem to be approached from the other side: allow traits to opt-in into being implemented without orphan rules restriction. Let Serde say that it doesn’t matter who implements Serialize.

[mboratko]

@kornel You’d still have to deal with issues of multiple implementations. That is a strict subset of the idea discussed here.

–

Edit: I’m out of replies for the day, so I’m posting a response to @Ixrec here as well:

it also appears to say that any non-generic function lacking the same exact set of impl annotations would simply not compile if it called or was called by bar

Yes, that’s not what I was suggesting, but I don’t see where the gist suggests this is the case.

–

I have to think more about @ExpHP’s earlier post. It is a good point, and definitely raises a property of Rust that should be preserved.

–

Edit2: (since I’m out of replies – sorry, this will make it hard to follow in the future so after this I’ll stop)

@Ixrec the problem is that Module2::bar is being called with a hash type whose first parametric type is a uint : Module1::hash when it explicitly required a type uint : Module2::hash. The non-genericity of Module1::foo nor it’s absent impl annotations has nothing to do with it, which is why I was confused by your statement. It could be made to compile as long as h had the proper type, for instance

    fn foo() -> str {
        let h : @ht::t<uint: Module2::hash, str> = ht::create();
        ht::put(ht, 3u, "hi"); // 3u.hash() == 3u here
        ret Module2::bar(h);
    }

should compile (using the notation from the gist). I think the confusion was on my part, I thought you were saying that foo had to be generic or specify the same type parameters as bar in order to get it to compile, which isn’t the case.

[Ixrec]

I think this has been rejected in the past because having no conflict resolution strategy at all means eventually someone’s going to pull in two crates that impl T for S, and then there’s simply nothing they can do to make that code compile. Then, at best, we’re back to crates doing “defensive newtyping” to avoid this problem.

Also, we should probably stop using Serialize as the example, since as stated above we’d never want serde to use such an opt-out even if it was added to the language for good reason. Unless serde added a separate NonPersistSerialize trait or something.

---

Edit:

it also appears to say that any non-generic function lacking the same exact set of impl annotations would simply not compile if it called or was called by bar

Yes, that’s not what I was suggesting, but I don’t see where the gist suggests this is the case.

That was my interpretation of:

As a result, the compiler will specify a type error at the call Module2::bar(h) in Module1::foo(), because the type of the parameter h in bar() does not match the type of the value being provided (the implementation modules do not match).

afaict, that’s the only sentence in the gist about the semantics of a non-generic function with impl annotations in the signature, so maybe there are other ways to interpret this.

[scottmcm]

I’d prefer this problem to be approached from the other side: allow traits to opt-in into being implemented without orphan rules restriction. Let Serde say that it doesn’t matter who implements Serialize .

A very small step towards that has actually been accepted, for traits with no methods: https://doc.rust-lang.org/unstable-book/language-features/overlapping-marker-traits.html

[mboratko]

It’s generally assumed that the serialized form of a type needs to be deserializable into any future version of that type .

How exactly is this being guaranteed now? I can make a crate wherein I create a type, implement serialize and deserialize on it, then change them in some backwards-incompatible way. No language features of Rust or semver will prevent or alert me to this, so it’s not part of the language to guarantee this, it’s left up to the responsibility of the impl author. This would be no different if we didn’t have the orphan rules.

[Ixrec]

It’s not being guaranteed, because there’s no way any language could actively enforce a guarantee like that. Even if serialization was part of the core language, there’s simply no way for the language to know with certainty what all past and future implementations of a type look like.

The point of that was not to argue the orphan rules are an ideal solution to the Serialize forward compatibility problem (they’re not even trying to be a solution to that), but that the Serialize problem is a special one that the obvious orphan rule dilemma doesn’t actually apply to, despite it being the most common reason why people complain about orphan rules.

[mboratko]

the Serialize problem is a special one that the obvious orphan rule dilemma doesn’t actually apply to, despite it being the most common reason why people complain about orphan rules.

Why not?

In my opinion, it does apply. For one thing, it applied in my case when I wanted to serialize some types which the author of the crate had not implemented Serialize, Deserialize on. The structs had a couple layers of nesting, and also depended on a struct from another crate which didn’t have Serialize, Deserialize implemented. In this case, doing away with the orphan rule would have allowed me to just derive the necessary traits in ~ 20 lines of code, rather than the various workarounds which have multiple issues. If the authors of those structs decided they did want to implement those traits themselves I would get a compiler error when I pulled the new version and have to either disambiguate (by specifying that I want to use my impl) or remove my impl (inspecting the new serialize implementation from the external crate to see if it was compatible with my own, if that was a concern).

[skysch]

If the authors of those structs decided they did want to implement those traits themselves I would get a compiler error

… which you probably wouldn’t be able to fix, because your other dependencies would likely get the same error. So if someone in a high use left-pad crate implements a trait, the whole world just stops compiling unless they all happen to be version-pinned.

[withoutboats]

I think there are a lot of reasons to be skeptical of this approach (or any other that would allow multiple conflicting impls to be compiled together), but I want to highlight one in particular that I’m surprised hasn’t been mentioned in this thread at all: this proposal would require a major overhaul to our compilation model.

Any time a crate needs to “prefer” one impl over another, it needs to recompile the entire section of the upstream crate graph that previously knew about either impl, in order to avoid incorrect monomorphizations in those crates. While this is certainly possible, it seems severely undesirable: it would require a complete restructuring of our division of work between rustc/cargo and tightly couple the compilation of upstream crates with their downstream crates in ways our existing system adeptly avoids.

The orphan rules (as distinct from the overlap rules) provide for precisely this property while maintaining coherence: the behavior of a crate depends only on its dependencies, not on its dependents.

[mboratko]

The point of what I’m suggesting here is that it would allow for this to be fixed.

It would be just as quick and easy to fix as a method overlap, which already isn’t prevented within Rust, presumably because the disambiguation is considered to be a simple and easy fix.

For example, currently if I do something like

trait MyTrait {
  fn something();
}

impl MyTrait for S {
  fn something() {
    \\--snip--
  }
}

and then some package I have a dependency on also has

impl SomeOtherTrait for S {
  fn something() {
    \\--snip--
  }
}

then

let x = S;
x.something();

results in an error, and I have to disambiguate by adding something like

let x = S;
MyTrait::something(x);

The proposal above would result in a similar way to disambiguate in the case of overlapping impls. It would take an equal amount of work to disambiguate overlapping impls as it does currently to disambiguate overlapping method names. In addition, the proposed prefer idea would be syntactic sugar for annotating all your variables with a specific impl, which would potentially be much less work than dealing with the overlapping methods.