User extensions problems with orphan-rule

help
1

To simplify i'll present a minimized version of my problem, for detail see here:

The detailed problem We are writing value-traits, a crate that aims to emulate slices, but for data that is not represented explicitly, our goal is to use in a uniform way for both normal vectors and compressed vectors.

Here's the simplified versions of our traits.
We have a trait analogous to core::ops::Index but that doesn't return references, but owned values:

pub trait SliceByValue {
    type Value;
    fn len(&self) -> size;
    fn get(&self, index: usize) -> Option<Self::Value>;
    fn index(&self, index: usize) -> Self::Value;
}

Moreover, we have a trait that emulates subslicing:

pub trait SubsliceByValue {
    type SubSlice<'a>: SubsliceByValue + SliceByValue;
    fn get_subslice(&self, range: Range<usize>) -> Option<Self::SubSlice<'_>>;
}

We provide a helper struct that implements SubsliceByValue on anything that implements SliceByValue:

pub struct SubsliceImpl<'a, T: SliceByValue>{
    slice: &'a, T,
    range: Range<usize>,
}

And it implements both SubsliceByValue and SliceByValue, and the idea is that a user can use it for its SubsliceByValue implementation, but can also write their version if they find a more efficient way.

Finally, we have another trait IterByValue which models structs that can return an iterator of owned values:

pub trait IterByValue {
    type Item;
    type Iter<'a>: Iterator<Self::Item> + 'a where Self: 'a;
    fn iter_by_value(&self) -> Self::Iter<'_>; 
}

Now I'm implementing these traits on another crate for a compressed vector that uses k bits per element, and I'm using SubsliceImpl to implement SubsliceByValue.
I want the subslice to also implement IterByValue, as by keeping a buffer of data in memory, we get much better performance compared to doing a random access at each next call.

So I'd like to write:

pub struct BitFieldVec; // the compressed vec impl
impl IterByValue for SubsliceImpl<'_, BitFieldVec> {
    // return my efficient iterator
}

What I want

I'm writing a crate that contains:

pub trait TraitA {}
pub struct StructA<T>(T);

And I would like the user to be able to write:

pub struct MyLocalType;
impl TraitA for StructA<MyLocalType> {}

Why I want it

In this case, StructA is a helper struct I provide to help implement another trait.
While we can write the following blanket implementation, I want the user to be able to specialise it.

impl<T> TraitA for StructA<T> {}

In our concrete example, the specialisation allows a x5 in performance.

The problem

The says that the orphan rule doesn't allow this:

error[E0117]: only traits defined in the current crate can be implemented for types defined outside of the crate
  --> test_orphan/src/lib.rs:2:1
   |
51 | impl<'a> TraitA for StructA<MyLocalType> {
   | ^^^^^^^^^^^^^^^^^^^-------------------------------
   |                              |
   |                              `StructA` 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

Why it happens

Looking at the rust reference I see the orphan rules defined as:

Given impl<P1..=Pn> Trait<T1..=Tn> for T0, an impl is valid only if at least one of the following is true:

  • All of
    • At least one of the types T0..=Tn must be a local type. Let Ti be the first such type.
    • No uncovered type parameters P1..=Pn may appear in T0..Ti (excluding Ti)

Here the problem is that T0, which in my case is StructA<MyLocalType>, is not a LocalType, as they are defined as:

LocalType

A struct, enum, or union which was defined in the current crate. This is not affected by applied type arguments. struct Foo is considered local, but Vec is not. LocalType is local. Type aliases do not affect locality.

Questions

1 - What's the reason why ForeignType<LocalType> is not local?
2 - What can I do to allow the user to write their specialised impl in an ergonomic way? I'd rather avoid having to write a new-type that wraps StructA<MyLocalType> and having to forward all traits

2

If it was, it would break back compat for your crate to add blanket trait implementations: impl<T> Foo for MyStruct<T>

1 Like
3

In your example, T is a generic parameter, not a local type. I'm not sure how it's related.

4

A generic parameter T matches any Sized type, including your local (sized) type. If such a generic blanket implementation is added to the crate defining TraitA, it would break your user's code, because now there are two implementations of TraitA for ForgeinType<LocalType>, the foreign generic one and the local specific one.

5

Add a second trait.

pub trait TraitForStructA {}

impl<T: TraitForStructA> TraitA for StructA<T> {
    // delegate all of TraitA to methods of TraitForStructA
}

Then the dependent crates can contain implementations of TraitForStructA.

3 Likes
6

A type can be local only in a single crate. If ForeignType<LocalType> was local in the crate defining LocalType then it would not be local in the crate defining ForeignType, which is much more unexpected and restricting.

2 Likes