ORing different trait bounds together, rather than ANDing

Hi, I am trying to feed an external type into my function, which has trait bounds to ensure the type has a len(). I am using the len-trait crate, which works great for most types (str, String, Vec, etc.). The issue is that I am trying to feed in another external type, which does not implement the len trait, and since I don't own either the external type or the len trait, I can't implement the len trait for it. My solution is to create another len trait that I do own, implement it for the type, and then pass it to my function. The issue I face is that my function only accepts types implementing the len-trait::len trait. Can I make this function accept types with the len-trait::len OR my len trait. I know how to AND traits together using '+', but I can't find the syntax for ORing traits together.

Here is my function header right now:

pub fn filter_by_length<T: len_trait::Len> (lists: &mut Vec<Vec<T>>, min_length: Option<usize>, max_length: Option<usize>)

No, you can't do this. But you could consider the alternate solution of writing a custom wrapper struct around the foreign type and implementing the trait for the wrapper.

That was the solution I came up with. The problem is that I don't just have one instance of the object, but a Vec of a Vec of objects, so I have to use ugly nested for loops to convert each object to the wrapper class, and than after the function is called, convert them back with two more loops. Is there any other way around this, or is a wrapper struct the only possible way?

What I would do is something along the lines of the following

trait MyLen {
    fn len(&self) -> usize; // or whatever signature you need
}

impl<T: len_trait::Len> MyLen for T {
    fn len(&self) -> usize {
        len_trait::Len(self)
    }
}

impl MyLen for YourType {
    // ...
}

There may be an extra borrow needed; I haven't checked the code.

This will allow you to avoid a wrapper type while still taking advantage of the external crate's implementations.

1 Like

One more possibility is to write a trait (implemented by some unit types) whose job is to select which trait is used. It's still not exactly the most ergonomic thing ever, but compared to the previous solution, it has the advantage that you don't need to reach into the vectors to change the type of the individual items.

(I can't recall any public APIs I've seen that have done this, so I'm not sure of the most idiomatic way to write this. The following is how I might write it if it were in private code where I wasn't too concerned about providing a well-crafted and obvious interface. IMO, "provider" sounds a bit enterprisey :sweat_smile:)

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=fe939f54c93c3559f8db34393bd2214e

pub trait LenProvider<T> {
    fn len_of(&self, obj: &T) -> usize;
}

pub struct LenProviderA;
pub struct LenProviderB;

impl<T: LenTraitA> LenProvider<T> for LenProviderA {
    fn len_of(&self, obj: &T) -> usize {
        obj.len()
    }
}

impl<T: LenTraitB> LenProvider<T> for LenProviderB {
    fn len_of(&self, obj: &T) -> usize {
        obj.len()
    }
}

Used like this:

pub fn total_len<T, P: LenProvider<T>>(data: &[Vec<T>], len_provider: &P) -> usize {
    data.iter().map(|inner|
        inner.iter().map(|x| len_provider.len_of(x)).sum::<usize>()
    ).sum()
}

fn main() {
    let vec_a = vec![vec![ThingA, ThingA], vec![ThingA]];
    let vec_b = vec![vec![ThingB, ThingB], vec![ThingB]];
    
    // the impls of the Len trait in this example just give constant integers
    // (see the playground link above)

    assert_eq!(total_len(&vec_a, &LenProviderA), 9);  // uses trait LenTraitA
    assert_eq!(total_len(&vec_b, &LenProviderB), 12);  // uses trait LenTraitB

    // we can even handle this type that implements both Len traits
    let vec_ab = vec![vec![ThingAB, ThingAB], vec![ThingAB]];
    assert_eq!(total_len(&vec_ab, &LenProviderA), 15);
    assert_eq!(total_len(&vec_ab, &LenProviderB), 18);
}
3 Likes

I like the look of this, but unfortunately it doesn't seem to work. When I impl MyLen for YourType, it gives me the error:

`upstream crates may add a new impl of trait `

So I think this is trying to prepare for the possibility that len_trait will someday be implemented on my type, at which point MyLen would be implemented twice for the same type.

Somebody with better knowledge of unsafe will probably come along and correct me, but I think something like this might be sound:

#[repr(transparent)]
struct WithLen(ForeignType);

impl Len for WithLen { ... }

fn wrap_len(unwrapped: &mut Vec<Vec<ForeignType>>)
-> &mut Vec<Vec<WithLen>> {
    //safety: WithLen has the same memory layout as ForeignType
    unsafe { &mut *(unwrapped
        as *mut Vec<Vec<ForeignType>>
        as *mut Vec<Vec<WithLen>>
    ) }
}

I believe that's UB because Vec is repr(Rust) see link

also this from a few days ago link

1 Like

Usually, when I do this sort of thing, I’ll define an additional trait with an associated type:

trait MyLen {
    type Provider: LenProvider<Self>;
    fn len(&self) -> usize { Self::Provider::len_of(self) }
}

Then, for each type I care about, I can choose which provider to use by implementing MyLen. It’s a local trait, so I can implement it for anything:

impl MyLen for ThingA { type Provider = LenProviderA; }

Hmmm, but then something seems strange. This would lead to a total of 3 different traits in one crate:

  1. The author's original own Len trait.
  2. The LenProvider trait. (to abstract over (1) and a trait in another crate)
  3. Another Len trait that automatically includes the LenProvider so the user doesn't have to see it.

I have to wonder, are we really not overthinking this? Is 3 whole traits really the minimum number we need to make this ergonomic? Or can two of these be somehow merged?

1 Like

Trait #1 could probably be replaced by a unit type that implements LenProvider, and then generic code uses trait #3 as its bound.

Swapping the roles of Provider and T lets the compiler do type inference on the parameter, if you don't anticipate needing data in your length-providers (which seems unlikely). Here's what I came up with:

pub trait Length<How> {
    fn length(&self) -> usize;
}

pub fn total_len<T: Length<How>, How>(data: &[Vec<T>]) -> usize {
    data.iter().map(|inner|
        inner.iter().map(|x| x.length()).sum::<usize>()
    ).sum()
}

// since this is used only to help type inference, and not as the parameter of any type,
// there's probably no harm in making it uninstantiable
pub enum ByLenA {}
pub enum ByLenB {}

impl<T: LenTraitA> Length<ByLenA> for T {
    fn length(&self) -> usize {
        self.len()
    }
}

impl<T: LenTraitB> Length<ByLenB> for T {
    fn length(&self) -> usize {
        self.len()
    }
}

Used in a similar way to yours, but perhaps more ergonomically:

    // no annotations needed when there is only one applicable `impl` 
    assert_eq!(total_len(&vec_a), 9);
    assert_eq!(total_len(&vec_b), 12);
    // when there's overlap, use turbofish
    assert_eq!(total_len::<_, ByLenA>(&vec_ab), 15);
    assert_eq!(total_len::<_, ByLenB>(&vec_ab), 18);

Full example.

I don't know if I've seen this exact thing in the wild, but marker types certainly aren't anything new, and the unused type parameter on Length is reminiscent of how std::slice::Concat also has an unused type parameter that disambiguates conflicting impls and can (almost?) always be found by type inference anyway.

1 Like

Ah, I initially misread the post. I thought you owned the type rather than were trying to implement it for an external type, and just didn't want to implement that specific trait for some reason.

With this "new" knowledge, the idiomatic thing is probably to create a newtype, as tedious as that may be.

Thanks for all the help! I went with a pretty rudimentary solution and just reimplemented the Len trait right into my own crate. Since it was only implemented on around 10 different types, I could reimplement it in a short amount of time. I also see myself needing to implement it on other types someday in the future, so this would have to be done sooner or later.

This isn't a great solution if it's a more complex trait implemented across many different types in many different crates though, so these suggestions still super useful and relevant. Hopefully one day the Rust team will consider loosening the constraints on the orphan rule, but until then we will have to use these janky hacks.