Remove the remaining uses of `old_orphan_rules`

[arielb1]

UPDATED ISSUE:

The original issue that was reported by @arielb1 has largely been resolved. However, there remain some traits that were added before the new rules were completed, and which do not conform. Those traits are currently distinguished with old_orphan_check markers. The remaining work is to fix these traits:

• BorrowFrom
• BorrowFromMut
• IntoCow
• ToOwned
• PartialEq

- @nikomatsakis

ORIGINAL ISSUE:

The current version of orphan checking does not prevent me from break coherence if impls from different crates are non-orphan because of different type parameters of the same type, for example:

base.rs:

pub trait Base { fn work(&self); }

foo.rs:

extern crate base;
pub struct Foo;

impl<T> base::Base for (Foo, T) {
  fn work(&self) { println!("foo!"); }
}

bar.rs:

extern crate base;
pub struct Bar;

impl<T> base::Base for (T, Bar) {
  fn work(&self) { println!("bar!"); }
}

foobar.rs:

extern crate foo;
extern crate bar;
extern crate base;
use base::Base;

fn main() { (foo::Foo, bar::Bar).work(); }

Which of course ICE-s with a trans ambiguity.

[arielb1]

cc @nikomatsakis

[nikomatsakis]

@arielb1 that is definitely a hole! Nominating. Interesting, have to think a bit about what the best way is to patch the rules for this case.

[arielb1]

By the way, the ambiguity can also occur between the receiver and one of the trait's type parameters:

base.rs:

pub trait Base<T> { /* ... */}

foo.rs:

extern crate base;
pub struct Foo;
impl<T> base::Base<Foo> for T {}

bar.rs:

extern crate base;
pub struct Bar;
impl base::Base<T> for Bar {}

With <Bar as base::Base<Foo>> being ambigious.

[nikomatsakis]

Some relevant comments from @arielb1 on IRC: https://botbot.me/mozilla/rust-internals/2014-12-03/?msg=26759795&page=7

[nikomatsakis]

I thought this through. I am mildly uncomfortable with @arielb1's proposed rules in that I do not expect the ordering of type parameters to be significant (which is not to say that those rules would not solve the problem). @aturon and I worked through some examples and we felt like these rules captured our intution reasonably well:

Local(Trait<T2...Tn> for T1) =
    Trait is local || (
       exists i. Local(Ti) &&
       forall i. Ti is not a type parameter
    )
Local(Type<T1...Tn>) =
    Type is local || (
       exists i. Local(Ti) &&
       forall i. Ti is not a type parameter
    )

This can be summarized as "type parameters can only appear as parameters of a local type/trait". This seems to cover the various cases I can think of. I have not tried to prove it sound but I believe it is. Of course I thought that before. :) Once I've had some more coffee, I might take a crack at that, seems like it should be a simple inductive exercise.

[arielb1]

@nikomatsakis

The version you wrote is broken:

// Crate a:
struct A;
impl<T> Base for Pair<Option<T>, Option<A>> {}
// Crate b:
struct B;
impl<T> Base for Pair<Option<B>, Option<T>> {}

Which follows the rules, as Option<T> isn't a type parameter (it just contains one).

A working variant is my second version of the rule: let ≺ be the partial order on nodes in a trait-ref generated by Trait ≺ Self ≺ Tᵢ in the trait-ref 〈Trait〈Tᵢ〉 for Self〉, Type ≺ Tᵢ in a type Type〈Tᵢ〉, then for every type parameter node Q in the trait-ref there exists a local node L such that L ≺ Q.

[nikomatsakis]

@arielb1 that does not follow the rules because of their recursion nature. Note that the Pair type is not local, and neither is Option, and hence the rules recurse in and ultimately reject both impls because of their use of a type parameter.

[nikomatsakis]

(Not to say the rules are perfect, as I said, I have to go back through the list of examples I had and make sure they accept/reject correctly, I'm a bit nervous about the exists vs forall)

[nikomatsakis]

(Or maybe that's the point, perhaps you are correct and I haven't quite formulated the rules the way I wanted them)

[arielb1]

By the way, the partial-order rules in sequent form:

Rule C0:
a crate
T type
T has-no-free-parameters
---------------------------------
a ⊢ T complete

Rule C1:
a crate
T type
a ⊢ T local
---------------------------------
a ⊢ T complete

Rule T0:
a crate
Q unsubstituted-type
Q defined-in a
∀i. Pᵢ type
---------------------------------
a ⊢ Q〈Pᵢ〉 local

Rule T1:
a crate
Q unsubstituted-type
∀i. Pᵢ type
∀i. a ⊢ Pᵢ complete
∃i. a ⊢ Pᵢ local
---------------------------------
a ⊢ Q〈Pᵢ〉 local


Rule R0:
a crate
Tr unsubstituted-trait
∀i. Pᵢ type
S type
Tr defined-in a
---------------------------------
〈Tr〈Pᵢ〉 for S〉 local

Rule R1:
a crate
Tr unsubstituted-trait
∀i. Pᵢ type
S type
a ⊢ S local
---------------------------------
〈Tr〈Pᵢ〉 for S〉 local

Rule R2:
a crate
Tr unsubstituted-trait
∀i. Pᵢ type
S type
a ⊢ S complete
∀i. a ⊢ Pᵢ complete
∃i. a ⊢ Pᵢ local
---------------------------------
〈Tr〈Pᵢ〉 for S〉 local

[nikomatsakis]

I created btw a repository for experimenting with rules and their effects on various scenarios:

https://github.com/nikomatsakis/orphan