Idiomatic rust: generic struct and a generic trait

help
1

Hi --

I am trying to experiment with the type system with a real world example. Suppose I want to define a key-value store package. I start out by defining the behavior:

use std::{collections::HashMap, hash::Hash};

pub trait Store<T: Eq + Hash + Clone> {
    fn new() -> Self;
    fn get(&self, key: &T) -> Option<&T>;
    fn set(&mut self, key: T, value: T) -> Option<T>;

}

My understand: I define an interface (or trait) with three methods over the type T which can be any type as long as it implements the Eq, Hash, and Clone traits.

With that done, I want to define a naive implementation of a key-value store that's just a wrapped HashMap (same file):


pub struct NaiveStore<T: Eq + Hash> {
    storage: std::collections::HashMap<T, T>
}

From that, I make it a Store<T> (same file):

impl<T: Eq + Hash + Clone> Store<T> for NaiveStore<T> {
    fn new() -> Self {
        Self {
            storage: std::collections::HashMap::new(),
        }
    }

    fn get(&self, key: &T) -> Option<&T> {
        return self.storage.get(&key)
    }

    fn set(&mut self, key: T, value: T) -> Option<T> {
        self.storage.insert(key, value)
    }
}

The compiler seems happy, I go in another directory and create an example that consumes this kv library:

use kvrust;

fn main() {
    println!("Hello, world!");
    let mut store = kvrust::NaiveStore::new();

    let k = String::from_str("testKey").unwrap();
    let v = String::from_str("testValue").unwrap();
    store.set(k.clone(), v.clone());
    println!("for key={} we have value={}", k, store.get(&k).unwrap());
}

But, I meet the following error:

error[E0599]: no function or associated item named `new` found for struct `NaiveStore` in the current scope
 --> src/main.rs:7:41
  |
7 |     let mut store = kvrust::NaiveStore::new();
  |                                         ^^^ function or associated item not found in `NaiveStore<_>

I assumed this was related to the fact that when I create a NaiveStore I do not specify the type and the new function doesn't specify it. But I am being told that this is somehow inferred by the compiler. Moreover, the error message says it cannot find a matching method new which tells me I might be mis-calling the method. Can I anyone point me to:

  • how to fix the error?
  • what's the idiomatic way to implement this pattern?

Thanks

2

Since new is a method of the Store trait, you have to import that trait in order to call the method:

- use kvrust;
+ use kvrust::Store;

Also, using String::from_str is not the best way to make a String from a string literal; you should use String::from("string literal") or "string literal".to_owned() instead. These are infallible, so you don't need a trailing unwrap.

5 Likes
3

@cole-miller provided the solution for your original problem (you need to import a trait to use its methods), so I'd like to provide some general feedback on your trait's design.

In general, you probably don't want your traits to have a new() method.

This will lock all implementors into providing a way to construct the Store without any extra state, which tends to be unnecessarily restrictive unless you have other generic code that relies on constructing a store in a particular way.

To see why this may be a problem, imagine you are creating a store that is backed by a file on disk. If you can't provide the file's path when constructing the store then your only choices will be

  1. always use a hard-coded path (e.g. ~/.cache/my-app/store.db), or
  2. let new() construct a store that requires people to call a set_path() method before they can use it

The first option is too rigid and would make things really hard to test, while the second option is a footgun... People will forget to call set_path() if it's not enforced by the type system, and it goes against the philosophy of "make invalid state unrepresentable".

Will people ever want to use a different type for the key and value? For example, if they want to create a store that maps a person's name to their age.

Does the T: Eq + Hash + Clone requirement need to live on the Store trait itself?

This will make it impossible to create a store backed by a std::collections::BTreeMap because BTreeMap has the requirement that its key is Ord.

One way you can work around this is to remove the T: Eq + Hash + Clone bound from the trait definition and have types only implement Store<T> when T satisfies their particular requirements.

use std::collections::{HashMap, BTreeMap};

trait Store<T> { ... }

impl<T: Eq + Hash> Store<T> for HashMap<T, T> { ... }

impl<T: Ord> Store<T> for BTreeMap<T, T> { ... }

I didn't see any clone() calls in your trait implementation, so it should be fine to drop the T: Clone requirement altogether.

Can you elaborate on where/how this trait may be used, and what benefit using a trait will give us over directly coding against a concrete implementation (e.g. HashMap)?

I don't know the full context so feel free to disregard me here, but one really good bit of advice I was given is to take a step back and ask whether you actually need to define a trait in the first place. Matklad's Code Smell: Concrete Abstraction article puts this into words a lot better than I could and provides some interesting case studies.

8 Likes
4

Thank you for the thoughtful answer. I understand the motivation behind not having a new method but then what would be an idiomatic way to instantiate a store without leaking details about the implementation in the interface? What's a nice API for Store if the trait is supposed to be a general purpose storage thingy. Maybe it uses a hash-table, maybe it's a BTree, maybe it's a universal hash-table etc.

Does the T: Eq + Hash + Clone requirement need to live on the Store trait itself?

No, you're right I was trying different things because even though it seemed correct to me I couldn't make that example work because of the import (gah...). I think the cleaner way is to have a generic trait with no bound and provide implementations that do, as you wrote.

I didn't see any clone() calls in your trait implementation, so it should be fine to drop the T: Clone requirement altogether.

+1 - will clean that up.

Can you elaborate on where/how this trait may be used, and what benefit using a trait will give us over directly coding against a concrete implementation (e.g. HashMap)?

I don't know the full context so feel free to disregard me here, but one really good bit of advice I was given is to take a step back and ask whether you actually need to define a trait in the first place. Matklad's Code Smell: Concrete Abstraction article puts this into words a lot better than I could and provides some interesting case studies.

Thanks for the link, this is a very interesting article for me. Right now I am just toying around with the type system. I started off with a concrete implementation of String, then made it generic, then added a trait etc.

I think the usecase I'm trying to simulate is: I am writing a KV library. My clients want to be able to swap one for the other with minimal hassle. They would be able to use the trait inplace of a concrete type and just instantiate a different store in their init to swap and try out different strategies etc. That's why I am looking to leak a little as possible about the underlying implementation.

Thanks again for your help

5

There's probably no idiomatic way to make creation implementation-agnostic. The code which creates the Store will know the type anyway, even if all other code is generic. However, if you're really sure that parameterless constructor will always make sense (i.e. it will create Store which can be used right away, without any mandatory additional configuration), an idiomatic way would be to require Default as a supertrait of Store.

4 Likes
6

Can you give me a code example where you would want to use a KV store but hide its actual instantiation?

If something has a sensible default value you'll normally implement the Default, but again, I'd recommend coming up with a couple different examples where you need to instantiate the store inside a generic function before putting constructors inside the trait. There's nothing stopping you from giving the store implementation its own constructor, but it only needs to be part of the trait when generic code wants to call S::new() (where S: Store).

You might also want to look into Dependency Injection (the programming technique, not frameworks). The idea is if your code needs access to something, you should pass in an instance as a parameter instead of constructing it inside the function so the caller has a chance to pick the implementation and configure/reuse it.

1 Like
7

Ah I think I understand. This is what I had in mind:

let mut db = kvstore::BTreeBased::new();
let b = benchmark_and_populate_db(&mut db); // accept a kvstore::Store and returns benchmark
println!("{}", b);

The ability to switch to a different implementation

let mut db = kvstore::HashTable::new();
let b = benchmark_and_populate_db(&mut db); // accept a kvstore::Store and returns benchmark
println!("{}", b);

I see how this breaks if say, I need a different way to initialize (like using a textfile) but in my imagined usecase, this is all in memory.

using dependency injection, I would get something like that right? see:

let mut db = kvstore::new(kvstore::backend::Hashtable);
...
1 Like
8

No, your first and second snippets are correctly using dependency injection because benchmark_and_populate_db() depends on a store and you are passing it in as a parameter ("injecting") instead of constructing the store inside the function.

The second snippet wouldn't be valid Rust because kvstore::backend::Hashtable is a type and functions can only accept values as parameters.

You probably wanted to use turbofish.

let mut db = kvstore::new::<kvstore::backend::Hashtable>();

But again, this is objectively inferior to the trait that doesn't require a constructor.

As a bonus, removing the constructor makes the Store trait object safe. That mean you can create a Box<dyn Store<String>> and choose which implementation to use at runtime.

1 Like
9

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.