How to make a trait more specific & more general


#1

Here is some code from the difflib crate’s sequencematcher/lib.rs (https://github.com/DimaKudosh/difflib/tree/master/src):


pub trait Sequence: Debug {
    fn len(&self) -> usize;
    fn at_index(&self, index: usize) -> Option<&str>;
}

impl<'a> Sequence for Vec<&'a str> {
    fn len(&self) -> usize {
        self.len()
    }

    fn at_index(&self, index: usize) -> Option<&str> {
        if index < self.len() {
            return Some(self[index]);
        }
        None
    }
}

The sequence matcher works on strings or vectors or slices of strings.

I have two problems I’d like to solve:

  1. The “items” (i.e., strings or chars) that this works on must support the == operator; but the trait doesn’t seem to specify this. Can this be made specific?
  2. I would like to implement this trait for any “item” type that has len() & at_index() methods & that supports ==. At the moment I have to use a local modified copy to process my custom Item type; I’d rather use a shared version in its own crate.

Is this possible?

PS At the moment I’ve got a local copy of this (& which I’ve changed to use FnvHashMap for speed & have made slightly closer to the Python original from Python’s difflib module).


#2

The == is implemented by the Eq trait. You can require it in two places - either the trait itself, or just in the trait’s implementation.

In the trait itself:


pub trait Sequence {
    type Item: Eq;
    fn len(&self) -> usize;
    fn at_index(&self, index: usize) -> Option<&Self::Item>;
}

// or

pub trait Sequence<Item> where Item: Eq {
    fn len(&self) -> usize;
    fn at_index(&self, index: usize) -> Option<&Item>;
}

See associated types.

or the implementation:

impl<T> Sequence for Vec<T> where T: Eq {
…

The difference is mostly philosophical, i.e. whether trait doesn’t make sense without Eq, or whether it is only implemented for Eq currently and someone could make it work without Eq if they really wanted.

Note that you can’t create a blanket implementation for all types that have some method (like in Golang). Rust requires trait implementations to be an explicit opt-in (more like interfaces in Java), but you can implement a trait any type that implements some other trait (so “it has a trait” is an indirect way of saying “it has a method”).


#3

I tried them & read the associated types docs (but didn’t really understand).

I’ve now realised that the Eq bit is not needed because internally the sequencematcher at_index() must return a &str, not any type that implements ==.

I’ll give up on this for now & live with the local version.

Thanks!