[Solved] Same trait implementation for multiple types

Hi,

So I am implementing some network code to handle buffering of received data. Basically, I'll need to buffer either data packets or some chat messages. The details behind those don't really matter I suppose. I wrote a buffer_item(t: T) function with the hopes that it could handle either a Packet or a ChatMessage, which it actually does. Awesome. :smiley:

The only problem is I have two full implementations of the same code, the only difference is that they are two distinct impls. Stated differently, I have a full implementation of buffer_item(t: T) where T: Packet for an implementation of RXQueue<Packet> , and another one of buffer_item(t: T) where T: ChatMessage for an implementation of RXQueue<ChatMessage>. The bodies of the functions is essentially the exact same code. The only difference lies in the type.

Link to playground explaining (hopefully) what I mean. Note, this won't compile since I omitted quite a bit for readability.

What I am trying to do is to only have one single instance of that function buffer_item(t: T) in impl NetworkQueue<T> for RXQueue<T>. The type T handle the type-specific details via Sequencer, but other than that it's all the same. That's what you see the Sequencer trait in the link I pasted above.

Is this possible at all? Ideally I'd like to avoid two identical implementations because that's a headache to maintain and can leak bugs easily. I know this may have been asked before in this thread so forgive me if this is a duplicate.

Any help would be appreciated. Thanks.

Edit: Probably should mention I tried fiddling with impl<T> NetworkQueue<T> for RXQueue<T> but couldn't get it working. Wish I had saved the code but I never committed it anywhere.

Have you tried impl<T: Sequenced> NetworkQueue<T> for RXQueue<T>? It seems that both types impls Sequenced.

This seems to work (at least it compiles in the toy example):

impl<T> NetworkQueue<T> for RXQueue<T>
where
    T: Sequenced,
{
    fn as_packet_queue(&self) -> &PacketQueue<T> {
        &self.queue
    }

    fn as_packet_queue_mut(&mut self) -> &mut PacketQueue<T> {
        &mut self.queue
    }

    fn buffer_item(&mut self, sequenced: T) {
        let sequence = sequenced.sequence_number();
        // ...
    }
}

However, you said that this was not working in your case. Maybe there is something in your real implementation that is still causing some problem. If you can give us more information, we can try to help you more.

Macros are also useful when you have structurally similar code that can't quite be merged together at the type level.

1 Like

@cuviper Yeah that thought crossed my mind but I'm hoping to leave it as a last result.

@Hyeonu @dodomorandi I'll have to give impl<T: Sequenced> NetworkQueue<T> for RXQueue<T> another attempt and report back.

Thanks everyone.

So I got a little bit closer thanks to the suggestions above. Something I omitted from the original post (for simplicity) was that the buffer_item(item:T) method iterates over a Vec<T> to find where the item should be inserted within the buffer. Here's an example of what I mean.


pub trait Sequenced<T> {
    fn sequence_number(&self) -> u64;
    fn sequencer(sequence: u64) -> T;
}

impl Sequenced<Packet> for Packet {
    fn sequence_number(&self) -> u64 {
        self.sequence_number()
    }

    fn sequencer(&self, sequence: u64) -> Packet {
        Packet::Request{sequence}
    }
}

impl Sequenced<ChatMessage> for ChatMessage{
    fn sequence_number(&self) -> u64 {
        self.sequence_number()
    }

    fn sequencer(&self, sequence: u64) -> ChatMessage{
        // We only compare on sequence_number() so the Strings do not matter
        ChatMessage::new(sequence, "".to_owned(), "".to_owned())
    }
}
impl Sequenced<()> { // I know this is probably wrong
    fn sequence_number(&self) -> u64 {
        unimplemented!()
    }


impl<T> RXQueue<T> where T: Sequenced {

...

    fn buffer_item(&mut self, item: T) {
        ...
        let insertion_index = self.find_rx_insertion_index_in_subset(0, buffer_wrap_index, sequence);
        ...
    }

    fn find_rx_insertion_index_in_subset(&self, start: usize, end: usize, sequence: u64) -> Option<usize> {
        let search_space: Vec<&T> = self.queue.iter().skip(start).take(end).collect();
        let result = search_space.as_slice().binary_search(&&T::sequencer(sequence));
        match result {
            Err(loc) => Some(loc + start),
            Ok(_) => None,
        }
    }

...

}

I think the problem I encounter during compilation is because sequencer() doesn't take self which is why it complains about not being able to be made into an object. I'm not quite sure how to fix this one.

error[E0038]: the trait `net::Sequenced` cannot be made into an object
   --> src\net.rs:364:6
    |
364 | impl Sequenced<()> {
    |      ^^^^^^^^^^^^^ the trait `net::Sequenced` cannot be made into an object
    |
    = note: method `sequencer` has no receiver

error[E0038]: the trait `net::Sequenced` cannot be made into an object
   --> src\net.rs:365:5
    |
365 |     fn sequence_number(&self) -> u64 {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `net::Sequenced` cannot be made into an object
    |
    = note: method `sequencer` has no receiver

error[E0038]: the trait `net::Sequenced` cannot be made into an object
   --> src\net.rs:364:6
    |
364 | impl Sequenced<()> {
    |      ^^^^^^^^^^^^^ the trait `net::Sequenced` cannot be made into an object
    |
    = note: method `sequencer` has no receiver

error: aborting due to 2 previous errors

The idea I have is that sequencer should simply return a value of type T with the specified sequence number so that that value can be used for comparison during the binary search.

I tried moving sequencer into impl Packet and impl ChatMessage separately, but then the above find_rx_insertion_index_in_subset() complained that it couldn't find a type 'T::sequencer`, which makes sense. I think it's because the compiler wasn't interpreting it as a generic.

Any ideas? I feel that I'm pretty close to the final solution but the syntax isn't quite lining up as I (wrongfully) expect.

I don't quite understand why you've structured/defined the code as you have, so I'll make some suggestions that you can take or leave.

The Sequenced::sequencer() fn seems unnecessary. In your example, all impls return some instance of themselves with the given sequence number. AFAIUI, you need this to do the binary search lookup. Instead of this, can Sequenced just require that it also impls Ord? In other words:

pub trait Sequenced: Ord {
    fn sequence_number(&self) -> u64;
}

This would make find_rx_insertion_index_in_subset look like:

fn find_rx_insertion_index_in_subset(&self, start: usize, end: usize, item: &T) -> Option<usize> {
        let search_space = &self.queue[start..start+end];
        let result = search_space.as_slice().binary_search(item);
        match result {
            Err(loc) => Some(loc + start),
            Ok(_) => None,
        }
    }

So you receive the item you're trying to buffer, and then search for an existing one that matches (whichever way Ord is defined). Note also that I don't think you need to collect anything into a temp Vec - just grab the slice (range) you want and binary search that.

I also dropped the T generic type param on Sequenced - it doesn't look necessary because in your example it's always returning the Self type anyway (i.e. Packet or ChatMessage). This becomes moot if you drop the sequencer fn but thought I'd mention it.

So, what did I get wrong here?

If you actually do need the sequencer fn, then you'd use the following in your insertion point finding fn:

let result = search_space.binary_search(&&T::sequencer(sequence);

You don't need any trait objects here and I'm also unsure where you were trying to go with the impl Sequenced<()> {...} attempt.

I hadn't considered passing in the type T as the item to be searched in, but your suggestion works. My initial thought was that I'd need to create the type T out of the provided value, but this is a lot more elegant. This is my first venture into rust's trait system (though I'd argue that solution really has nothing to do with traits) so thank you for the guidance. You hit the nail on precisely on the head.

Oh, also, ops::Range isn't implemented for VecDeque which is what queue actually is, so I cannot index like you suggested (&self.queue[start..start+end]). That's why I use skip(x).take(y).collect() instead.