Named and scoped trait implementations as a solution to orphan rules [ok, it wont' work]

[kornel]

I’m often running into a problem that I can’t make two crates work together:

extern crate duck;
extern crate quack;

/// E0117 Not allowed :(
impl Quack for Duck {}

Traits in general have a solution for being implemented on other types — they have to be in scope. I’m proposing similar scoping for trait implementations.

An implementation can be named, and it’s visible and usable only where it is in scope. Two conflicting implementations can’t be used in the same scope.

mod my {
    impl Quack as MyQuack for Duck {}  
    duck.quack(); // implemented! it works as an implementation of Quack, but only in places where MyQuack is visible
}

duck.quack(); // error, not implemented, because MyQuack is not in this scope

{
    use my::MyQuack;
    duck.quack();  // ok
}

{
    use my::MyQuack;
    use other::SomeoneElsesQuack; // error: conflicting trait implementations
}

[sinkuu]

Not sure if it works with trait bounds.

struct Foo<T: Quack>(T);

impl<T: Quack> Foo<T> {
    fn action(&self) { self.0.quack() }
}

let foo = {
    use my::MyQuack;
    Foo(Duck::new())
};

foo.action(); // `Duck` doesn't implement `Quack` here? But `Foo` must always contain a `Quack` implementor.

{
    use other::SomeoneElsesQuack;
    foo.action(); // now `Duck` has `Quack` impl by `other`?
}

[kornel]

Ah, I suspected it was too good to be true I don’t know how to solve that one.

[gabomgp]

In my opinion, that is very similar to implicits in Scala. So, foo.action call the quack method of impl MyQuack. So, when i call a trait method, the call may be dispatched to a global impl or to a named impl, depending on the scope where the original code stay. So, the compiler will have to “save” not only the type of foo, but the impls applyed to the object, a la scala, but more implicitly. So, the type of foo will be as "struct Foo<Duck with impl MyQuack>".

Edit: error in the last sentence.

[gabomgp]

And the programmer don’t need to know that the type is Foo<Duck with impl MyQuack>, only that is Foo<Duck with Quack>, wihtout knowing the exact impl involved. Impl Trait only say that the type implement the Trait, is similar, I think.

[kornel]

OK, so currently something close is possible in Rust if the trait opts in:

quack crate:

trait Quack<Impl=()> {}

duck crate:

struct Duck;
impl Quack for Duck {}

other crate:

struct MyQuack;
impl Quack<MyQuack> for Duck {}

The downside is that struct Foo<T: Quack>(T); becomes struct Foo<Impl, T: Quack<Impl>>(T); and the Impl spreads everywhere and causes type noise.

So maybe the solution could be that every trait has a special associated type for tracking of its impl, which is then inserted by the compiler, so it doesn’t pollute type signatures.

[withoutboats]

This idea has been brought up several times. I’m not very excited about it for several reasons.

@sinkuu’s example is a good example of how its confusing. We’d have to validate that every T you pass to Foo could implement Quack if an impl is in scope, without resolving it to a specific impl. Then, it would work, but you couldn’t call any methods on Foo without importing that impl.

What’s especially concerning, then, is that these two blocks could do totally different things:

{
    use my::QuackForDuck;
    foo.action();
}
{
    use another::QuackForDuck;
    foo.action();
}

This is especially concerning because you might import your quack impl to make a duck variable quack, without realizing you’re changing how foo behaves in that scope.

Additionally, you now have to check the imports to figure out what’s going on in every scope. You can’t just assume because you’ve seen the impl of this trait for this type before, you know what it does in this context. That seems quite bad.

We also haven’t considered how this interacts with the unnamed impls that non-orphan crates are still allowed to provide; this would have to shadow them, otherwise adding an impl to your crate is always a breaking change. But that just makes it even harder to track what’s going on.

This is all especially concerning with glob imports, which now might include an impl for types and traits that aren’t even from the same crate the glob’d module is from.

None of this is impossible - that is, we could define semantics that would still guarantee that in a given context, a single impl is found for every trait/type pair - but to me it seems much more confounding than the current behavior.

It just doesn’t seem better than the alternative - a newtype struct:

pub struct MyDuck(pub Duck);

impl Quack for MyDuck { }

fn foo() {
    let my_duck = MyDuck(duck);
    my_duck.quack();
    let duck = my_duck.0;
}

And we could provide some ‘newtype deriving’ solution so that MyDuck would delegate a lot of impls to Duck without you writing it all out.

[bbatha]

Edward Kmett makes some pretty compelling arguments against implicits in this talk. The short of it is, trying to guess which which version of a type class is in scope is not just difficult for humans to reason about, its actually pretty complex for the compiler too.

[withoutboats]

That’s a great talk!

It’s interesting that he says Haskell’s way of handling orphan instances (blowing up when you combine two modules) is an implementation detail of GHC; I would consider Rust’s handling of orphan impls a part of the language spec.

[nikomatsakis]

We initially had scoped impls in Rust. We removed them because of what we called “the hashtable problem”. This e-mail of mine from 2011 kind of goes into some of the details, I think. We called it the hashtable problem because – imagine you had a hashtable with keys to type K that is built up using one impl of Hash, but then you pass that hashtable to another module, where a distinct Hash impl is in scope. It’s going to be pandemonium. What that e-mail proposed was to solve this by making the impl “part of the type”, in a sense. At the end of the day it seemed like a lot of complexity and we opted against it – but there are real costs. I’m not sure of the best fix here.

[kristoffer]

Didn’t someone propose a kind of non exportable orphan implementation? Binaries can implement traits for unowned types and traits but libraries cannot. Solves the consumption problem without someone inadvertently ruining the soundness of someone else’s hashtable.

Anyway I have not actually come across a situation where I couldn’t wrap a type and just work with the wrapper itself (with the help of Deref) so I’d love to see some cases where that is really unergonomic.

[withoutboats]

That actually doesn’t prevent coherence issues. Consider this example:

You are and your parent are like this:

// parent
trait Foo { }

//you

// non-exported orphan impl
impl<T> Foo for T { }

You go to add another dependency which also depends on your current parent dependency, and it looks like this:

// second dependency, also depends on parent

struct Bar;

// conflicts with your orphan blanket impl
impl Foo for Bar { }

[kristoffer]

Seems like that only happens for blanket impls. Should be fine otherwise, right?

[withoutboats]

No. It would make adding any impl at all to your code a breaking change, something we have worked very hard to avoid, because any of your binary dependencies could contain any impl you might want to write.

For example, you could write impl<T: ToString> ToString for Vec<T>. Then we decide to add such an impl to std, now your code is broken when you go to update Rust.

[kristoffer]

Ah, never mind then.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.