Keeping a struct implementation generic but calling specific implementations

help
1

I'm trying to be generic on C's implementation, but use individual implementations of div_array for its member T. For example, C::something(&self) should use the correct implementation for the array [T; 2]. Since T: A, only 2 possible T can exist: T=u32, T=u64, so I implemented DivArray for [u32;2] and [u64;2] only. While I could do a generic implementation, I really want it to be specific on each array implementation because it could use some hardware operations only available for some types, etc.

use core::marker::PhantomData;
use num_traits::Zero;

pub trait A: Zero + Copy {}

impl A for u32{}
impl A for u64{}

pub trait DivArray<'a, Rhs>: Sized + Copy {
    type Output;
    fn div_array(
        self,
        denominator: Rhs,
    ) -> Result<Self::Output, ()>;
}
    
impl<'a, Rhs: Into<Rhs>> DivArray<'a, Rhs> for [u32; 2] {
    type Output = [u32; 2];
    fn div_array(
        self,
        denominator: Rhs,
    ) -> Result<Self::Output, ()> {
        unimplemented!();
    }
}

impl<'a, Rhs: Into<Rhs>> DivArray<'a, Rhs> for [u64; 2] {
    type Output = [u64; 2];
    fn div_array(
        self,
        denominator: Rhs,
    ) -> Result<Self::Output, ()> {
        unimplemented!();
    }
}

pub struct C<T>{
    _phantom: PhantomData<T>
}

impl<T: A> C<T>{
    pub fn something(&self) {
        let arr = [T::zero(); 2];
        arr.div_array(1u64);
    }
}


error[E0599]: no method named `div_array` found for array `[T; 2]` in the current scope
  --> src/lib.rs:44:13
   |
44 |         arr.div_array(1u64);
   |             ^^^^^^^^^ method not found in `[T; 2]`
   |
   = help: items from traits can only be used if the trait is implemented and in scope
note: `DivArray` defines an item `div_array`, perhaps you need to implement it
  --> src/lib.rs:9:1
   |
9  | pub trait DivArray<'a, Rhs>: Sized + Copy {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

What is happening here? I clearly implemented DivArray for all T such that T:A

2

I don't quite get this. Could you please elaborate?
As far as I can see, you implemented DivArray for [u32; 2] and [u64; 2]. But you called div_array on an array of type [T; 2]. Hence, the Rust compiler complains.
The following works though (Rust Playground):

let arr = [1_u32; 2];
arr.div_array(2_u32);
3

I want C to be generic, and I did impl<T: A> C<T>, so the T in [T; 2] should be either u32 or u64, so that's why I made the implementations [u32; 2] and [u64; 2]

4

Well, in Rust that is not expressed in terms of generics.
Since you know that you will get either a u32 or u64, you can make an enum specifying that. Then you don't need a trait but can define array_div as an enum method.

5

If you want something to be defined for any C<T>, you have to provide a definition which works for every T.

Alternatives include an impl for each type (perhaps via macro), and constraining the impl with trait bounds.

impl<T: A> C<T> where [T; 2]: for<'a> DivArray<'a, u64> {
6

I can't do like this but I tried to see how it would look like and I can't do it because I'd define 2 fn somethings:

I changed the DivArray trait and tried implementing for u32 and u64 instead, but without success also: Rust Playground

I also can't use macros because otherwise there's no point in using generics. All of my code would be macros.

7

Well, let's back up. What's the complete trait that you're trying to use here? Or perhaps more to the point, what operations over which types do you need to support exactly?

The original looks like so:

pub trait DivArray<'a, Rhs>: Sized + Copy {
    type Output;
    fn div_array(self, denominator: Rhs,) -> Result<Self::Output, ()>;
}

But you're not making use of 'a and both of your implementations follow this pattern:

impl<'a, Rhs: Into<Rhs>> DivArray<'a, Rhs> for [u32; 2] {
    type Output = [u32; 2];

If this pattern is always followed,

  • There's no need for Output if it's always Self
  • Rhs can be any Sized type, because all Sized types T satisfy T: Into<T>
    • And dividing from anything whatsoever doesn't really make sense

And the rewritten version has similar redundancy and over-generality.

8

I was thinking about having a polynomial with coefficients over T where T: A, and thus I'd be able to do something like this:

impl<T: A> Polynomial<T> {
    //...
}

and my polynomial would be able to do lots of stuff on its coefficients, one of which would be DivArray. I just noticed I don't need the lifetime, I was using it so I could pass a mutable slice to put the result into, but now I remembered that I always return an array of size 2, but anyways for other types of operations it could be needed because I could not know the size of the slice to be returned.

Anyways, I wanted to be generic over T but also be able to implement DivArray (and other operations) for my types individually. Some hardware functions are only available for u64 for example.

I think a better example would be this:

pub trait ModAdd<Rhs = Self>: Sized + Copy {
    type Output;
    //addition modulo a number
    fn mod_add(
        self,
        rhs: Rhs,
        modulus: Self,
    ) -> Self::Output;
  }

the coefficients of the polynomial would have to implement this, but I also would be able to implement ModAdd individually for u64 and u32.

So, instead of

impl<T: A> ModAdd for T{}

I'd like to do

impl ModAdd for u64{
//...
}
impl ModAdd for u32{
//...
}

but somehow make sure the right implementation is called by the Polynomial. Example:

impl<T: A> Polynomial<T> {
    fn add_coefficients_by_x_mod_modulus(&mut self, x: T, modulus: T) {
        //*coefficient = (coefficient + x) mod modulus
        for coefficient in self.coefficients.iter_mut() {
               (*coefficient).mod_add(x, modulus);
        }
    }
}

I could implement Polynomial for u64 and u32 separately, but I don't want to, neither I want to use macros.

9

Alright, I took another crack at it. Here I just mirrored the Div trait from the standard library, as I got the impression you're wanting standard operations over your coefficients. You might even want to consider making a new type to hold your [T; 2] and implementing the standard ops on the newtype(s) instead, where applicable.

For the somethings I made use of num_traits::One.

You almost definitely don't want a lifetime in your trait. If you do end up with some sort of buffer system where you pass in the destination but don't know the resulting size, consider

  • A buffer type like Vec with distinct capacity and size you can modify
  • If you do take a slice, perhaps return the resulting length (or an error) instead
  • If you do take and return a slice (or error), just keep the lifetime on the specific method(s)

As an aside, in case you didn't know: when you write generics, the compiler monomorphizes every concrete type that uses the generic trait/method/whatever so that they all get their own functions that can be optimized independently. If you're not doing some pretty low-level tuning, this is often good enough.

10

I don't get it. How can I optimize them independently? This is what I was trying to do but I don't know how to optimize it myself, unless by implementing it differently for each type. For example, suppose I had the trait CarryAddition:


pub trait CarryAddition<Rhs = Self>: Sized {
    type Output;
    fn carry_addition(
        self,
        carry: bool,
        rhs: Rhs,
    ) -> (Self::Output, bool);
}

For u64, I'd implement it using the x64 carry addition builtin instruction (when available), and for u32, pure software (technically I can just .into() to u64 but anyways, just an example). This is what I'm doing right now. Are you saying that the compiler does the optimization for me? I really need to manually do the optimization, I'm gonna use lots of builtin instructions and also SIMD stuff, differently for each type.

Ok, so, for your example:

impl<T: A> C<T> where [T; 2]: DivArray<T>, T: One {
    pub fn something(&self) {
        let arr = [T::zero(); 2];
        arr.div_array(T::one());
    }
}

this is what I was trying to avoid since the begining. Unfortunately, I'd have lots of these operations, not just DivArray<T>, so I'd have to put lots of trait bounds on impl<T: A> C<T>, like where [T; 2]: DivArray<T> + CarryAdd<T> + .... Not only that, every struct that uses C<T> and is also generic on T, would have to put these bounds as well. In the begining, I was writing things like CarryAddition not as traits, but like this:

pub fn carry_addition<T: SomeTrait> {
    //
}

where SomeTrait would be implemented for u32, u64 etc. I quickly realized that I could not implement carry_addition separatedly for each type so I could use x64's carry add for u64 for example. Also, every struct that uses this function would have to have its trait bounds as well. So the idea of defining a trait for CarryAddition and implement for u64, u32 and possibly a user-defined type, seems like a really good idea. I just need to find a way of using these while also doing impl<T:A> C<T> so I don't have to implement a polynomial (a C struct) for every type.

11

I meant the compiler will optimize them independently. What it optimizes down to varies with circumstance and, it's true, is not guaranteed. Maybe you are working on a low enough level it matters -- you have to compile things and see what you get. Sometimes you can refactor to hint the compiler in the right direction. It does vectorize operations down to SIMD sometimes.

That's how generics work -- you can use the abilities described by your trait bounds, but nothing more. In numeric contexts, that does tend to be a lot of bounds. Sometimes mitigations are possible by making a custom trait with a bunch of supertraits, for example. You'll probably lose some expressiveness trying to maintain just a T: A bound, but if you can cram everything into A, maybe it will work for you.

If you don't need the generic infrastructure for anything else, macros are another common solution for avoiding trait bound explosion when you really just need a handful of concrete types like u32 and u64. (It sounds like possibly you want it for ease of user-defined types, but I'm not sure if that's your actual objection.)

12

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.