Too strict orphan rules E0117

language design
1

Code:

use std::collections::VecDeque;

struct MyVec<T>(Vec<T>);

impl<T> From<Option<Vec<T>>> for Option<MyVec<T>> {
    fn from(value: Option<Vec<T>>) -> Self {
        Some(MyVec(value?))
    }
}

impl From<Option<Vec<i32>>> for Option<MyVec<i32>> {
    fn from(value: Option<Vec<i32>>) -> Self {
        Some(MyVec(value?))
    }
}

struct Node<T> {
    val: T,
    next: Option<Box<Node<T>>>,
}

impl<T> From<VecDeque<Box<Node<T>>>> for Option<Box<Node<T>>> {
    fn from(mut value: VecDeque<Box<Node<T>>>) -> Self {
        let mut head = value.pop_front()?;
        let mut current = &mut head;
        for node in value {
            current.next = Some(node);
            current = current.next.as_mut().unwrap()
        }
        Some(head)
    }
}

fn main() {}

And the result:

   Checking explore v0.1.0 (/home/PC-Killer/projects/explore)
error[E0119]: conflicting implementations of trait `From<Option<Vec<i32>>>` for type `Option<MyVec<i32>>`
 --> src/main.rs:11:1
  |
5 | impl<T> From<Option<Vec<T>>> for Option<MyVec<T>> {
  | ------------------------------------------------- first implementation here
...
11 | impl From<Option<Vec<i32>>> for Option<MyVec<i32>> {
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `Option<MyVec<i32>>`

error[E0117]: only traits defined in the current crate can be implemented for types defined outside of the crate
--> src/main.rs:5:1
 |
5 | impl<T> From<Option<Vec<T>>> for Option<MyVec<T>> {
 | ^^^^^^^^--------------------^^^^^----------------
 |         |                        |
 |         |                        `Option` is not defined in the current crate
 |         `Option` is not defined in the current crate
 |
 = note: impl doesn't have any local type before any uncovered type parameters
 = note: for more information see https://doc.rust-lang.org/reference/items/implementations.html#orphan-rules
 = note: define and implement a trait or new type instead

error[E0117]: only traits defined in the current crate can be implemented for types defined outside of the crate
 --> src/main.rs:11:1
  |
11 | impl From<Option<Vec<i32>>> for Option<MyVec<i32>> {
  | ^^^^^----------------------^^^^^------------------
  |      |                          |
  |      |                          `Option` is not defined in the current crate
  |      `Option` is not defined in the current crate
  |
  = note: impl doesn't have any local type before any uncovered type parameters
  = note: for more information see https://doc.rust-lang.org/reference/items/implementations.html#orphan-rules
  = note: define and implement a trait or new type instead

error[E0117]: only traits defined in the current crate can be implemented for types defined outside of the crate
 --> src/main.rs:22:1
  |
22 | impl<T> From<VecDeque<Box<Node<T>>>> for Option<Box<Node<T>>> {
  | ^^^^^^^^----------------------------^^^^^--------------------
  |         |                                |
  |         |                                `Option` is not defined in the current crate
  |         `VecDeque` is not defined in the current crate
  |
  = note: impl doesn't have any local type before any uncovered type parameters
  = note: for more information see https://doc.rust-lang.org/reference/items/implementations.html#orphan-rules
  = note: define and implement a trait or new type instead

Some errors have detailed explanations: E0117, E0119.
For more information about an error, try `rustc --explain E0117`.
error: could not compile `explore` (bin "explore") due to 4 previous errors

Divide this into three parts:

  1. struct MyVec<T>(Vec<T>);

impl<T> From<Option<Vec<T>>> for Option<MyVec<T>> {
    fn from(value: Option<Vec<T>>) -> Self {
        Some(MyVec(value?))
    }
}
    Here we implement From<Option<Vec<T>> for Option<MyVec<T>>, and the compiler reports that we voilate the orphan rule. However, MyVec is defined in the scope, so there's no chance that a more specialized overload will be defined in any other modules.
  2. impl From<Option<Vec<i32>>> for Option<MyVec<i32>> {
    fn from(value: Option<Vec<i32>>) -> Self {
        Some(MyVec(value?))
    }
}
    Since we all use concrete types like Option<MyVec<i32>>, which means it's impossible that there is a more specialized implementation than this. However the compiler just reports that Option<MyVec<i32>> is foreign, which is a little stupid.
  3. struct Node<T> {
    val: T,
    next: Option<Box<Node<T>>>,
}

impl<T> From<VecDeque<Box<Node<T>>>> for Option<Box<Node<T>>> {
    fn from(mut value: VecDeque<Box<Node<T>>>) -> Self {
        let mut head = value.pop_front()?;
        let mut current = &mut head;
        for node in value {
            current.next = Some(node);
            current = current.next.as_mut().unwrap()
        }
        Some(head)
    }
}
    This proves that similar case does make sense, while still being rejected by the compiler.

Is it possible to correct the behavior?

2

My immediate concern is that unsafe code may be making assumptions about the nonexistence of foreign impls; only a select few types (&T, &mut T, Box<T>, Pin<T>) allow foreign impls. (These types are called “fundamental” types.)

Those fundamental types have contributed to unsoundness in std in the past: Unsoundness in `Pin`

I can’t actually think of any soundness problems that would ensue from allowing arbitrary users to implement foreign traits for Option<LocalType>, but unless someone exhaustively proves that this is sound, I will remain suspicious.

3

There are also concerns related to backwards compatibility and semver. There are some things that Option<T> could do in a backwards-compatible way, thanks to the orphan rules, which a #[fundamental] type like Box<T> can’t. AFAIK the sole extra power for non-fundamental stuff — setting aside whatever reasoning goes into unsafe code — is the ability to add new blanket impls of existing non-#[fundamental] traits for existing non-#[fundamental] types in a nonbreaking change, but I could be forgetting something.

4

it is not possible to correct the behavior because the behavior is correct.

its really not ; Option<MyVec<i32>> is local to the crate that defined Option, the same way MyVec<i32> is local to your crate, and not core, that defined i32.

i am very confused as to what this is supposed to prove ?

this is the current orphan rule

if you think you can make a better one that is sound, feel free to do so, but very smart people have worked a long time on making it as relaxed as possible

2 Likes
5

Adding blanket implementations is a breaking change.

Blanket implementations are defined in terms of uncovered generic parameters. A type constructor TyCons<T> covers T if it is non-fundamental, and does not if it is fundamental.

Changing a non-fundamental type constructor to a fundamental one is a breaking change, as mentioned below. (And vice-versa, too.)

Under the current orphan rules, alloc (VecDeque's crate) has the "right" to add this implementation in a non-SemVer-breaking fashion:

impl<T> From<VecDeque<T>> for Option<T> { ... }

And that overlaps with your example.

Similarly, crates today can have their own implementations following the pattern:

// These can exist in the current ecosystem.
impl<T> From<MyTypeConstructor<T>> for Option<T> { ... }
impl<T> From<MyTypeConstructor<T>> for VecDeque<T> { ... }

Changing the orphan rules to take away the "right" generally would break those crates.

Making Option<T> or VecDeque<T> fundamental would make an implementing type in the example uncovered, which is not allowed on foreign traits -- and thus would also break those crates.

It's harder to construct conundrums for your other specific examples that don't involve Option making breaking changes of its own, but not impossible. If Vec somehow moved to core,[1] the following implementation would be allowed with todays orphan rules, so long as Vec<T> didn't meet the SomeHypotheticalTrait bound.

trait SomeHypotheticalTrait {}
impl<T> SomeHypotheticalTrait for T where /* ... */;

impl<T, U> From<Option<Vec<T>>> for Option<U>
where
    U: SomeHypotheticalTrait,
{ ... }

If MyVec<_> could meet the hypothetical bound, the above implementation would conflict with your first two examples.

Even if we discard such a possibility, you would need to formally define what set of circumstances allows downstream to use negative reasoning about Option's implementations. Like some argument that it's impossible for Option to write such an implementation that isn't itself a breaking change or otherwise not allowed.

(If the argument relies on coherence assuming types never change crates (like a type moving to a dependency and becoming an alias in the original crate), I doubt that would fly either.)

  1. like some attempts to move io::Error to core ↩︎

1 Like