Day 4 · Traits & Generics

The Project 2 overview promised a store you can put behind a network and share across threads. None of that matters if the core engine isn’t reusable and honest about its contract first. So Day 4 builds the bottom of the stack: a trait that says what a store is, a generic struct that implements it over a HashMap, and a REPL to poke at it. Two big Rust ideas show up because the design needs them — traits to separate “what” from “how”, generics so one engine serves any key/value type — plus a first, gentle brush with lifetimes.

Scaffold the crate

kvlite is a library with a small binary on top (see the overview’s file map), so we scaffold it as a library crate and add the binary alongside:

   cd code            # the playbook's companion-code directory
   cargo new kvlite --lib
   cd kvlite
   cargo add thiserror       # our one dependency; used for errors on Day 6

We need both a library (src/lib.rs, where all the logic lives) and a binary (src/main.rs, the CLI). Spell that out in Cargo.toml:

   [package]
   name = "kvlite"
   version = "0.1.0"
   edition = "2021"

   [dependencies]
   thiserror = "2"

   [lib]
   name = "kvlite"
   path = "src/lib.rs"

   [[bin]]
   name = "kvlite"
   path = "src/main.rs"

Two commands you’ll lean on all day: cargo check (type-check only — your fast inner loop) and cargo test (which we’ll use as the Day 4 proof).

The project skeleton

Before any real logic, lay out the whole crate as compiling stubs so nothing you write later points at a file that doesn’t exist yet. Today touches four files:

   src/
     lib.rs      # declares the modules and re-exports the names users reach for
     error.rs    # KvError + the crate-wide Result<T> alias (starts tiny, grows Day 6)
     store.rs    # Store trait + MemStore  (SharedStore is added Day 5)
     main.rs     # the binary: an in-memory REPL for now (rewritten Day 7)

Three mechanics wire the modules together, exactly as in logwise: pub mod store; in lib.rs pulls in src/store.rs; pub on an item makes it visible outside its file; use crate::error::Result; brings a name into another file’s scope. The dependencies point one way — store uses error — so we define error first.

src/error.rs — the crate’s shared vocabulary. Today it needs just the Result alias and one variant; Day 6 grows it when real I/O arrives.

   /// The one error type the whole crate speaks. It starts small and grows: today
   /// a single variant; Day 6 adds the I/O, protocol, and bad-key cases.
   #[derive(Debug, thiserror::Error)]
   pub enum KvError {
       /// A lock was poisoned: a thread panicked while holding it. (Earns its keep
       /// once `SharedStore` arrives on Day 5.)
       #[error("lock poisoned: a thread panicked while holding the store lock")]
       Poisoned,
   }

   /// Crate-wide alias, so signatures read `Result<T>` not `Result<T, KvError>`.
   pub type Result<T> = std::result::Result<T, KvError>;

src/store.rs — the trait and the empty shell of the engine; the next sections fill in the bodies.

   use std::collections::HashMap;
   use std::hash::Hash;

   use crate::error::Result;

   pub trait Store<K, V> {
       fn set(&mut self, key: K, value: V) -> Result<Option<V>>;
       fn get(&self, key: &K) -> Option<V>;
       fn delete(&mut self, key: &K) -> Result<Option<V>>;
       fn len(&self) -> usize;
       fn is_empty(&self) -> bool {
           self.len() == 0
       }
   }

   #[derive(Debug, Default, Clone)]
   pub struct MemStore<K, V> {
       map: HashMap<K, V>,
   }

src/lib.rs — declare the module tree and re-export the names callers use most, so use kvlite::Store; just works:

   pub mod error;
   pub mod store;

   pub use error::{KvError, Result};
   pub use store::{MemStore, Store};

src/main.rs — a placeholder for now; the REPL lands at the end of the day.

   fn main() {
       // Day 4: an in-memory REPL. Day 7: serve & repl subcommands over TCP.
   }

Run cargo check — it’s green (with a Poisoned never-constructed warning; expected, since the lock that uses it arrives Day 5). You now have a compiling skeleton: a shared Result, a Store contract, an empty MemStore, and the module wiring. The rest of the day fills in the bodies.

A trait is a contract, not a class

In Rust you don’t start from a class hierarchy; you start by writing down the behaviour you require, as the trait you just stubbed:

   pub trait Store<K, V> {
       fn set(&mut self, key: K, value: V) -> Result<Option<V>>;
       fn get(&self, key: &K) -> Option<V>;
       fn delete(&mut self, key: &K) -> Result<Option<V>>;
       fn len(&self) -> usize;

       // A *default method*: implementors get it for free, in terms of len().
       fn is_empty(&self) -> bool {
           self.len() == 0
       }
   }

Read it as a promise: “anything that is a Store can set, get, delete, and report its size.” It says nothing about how — HashMap, B-tree, a file, a remote server; all are allowed. (Result<Option<V>> is the crate alias from error.rs, so it means Result<Option<V>, KvError>.) Code written against the trait (fn report<S: Store<K, V>>(s: &S)) works with every implementation, forever. That separation is the whole point: the Day 7 server will talk to a Store, never to a specific struct, so swapping the engine never touches the network code.

&self vs &mut self — the trait encodes the borrow rule

Notice get takes &self (a shared borrow — reads don’t change anything) but set/delete take &mut self (exclusive — they mutate). That isn’t decoration: it’s the “shared XOR mutable” rule from The Rust Mindset, written into the contract. The compiler will later use exactly these signatures to decide a read lock is enough for get but a write lock is needed for set. The trait is already telling the truth about concurrency.

Generics: one engine, any key and value

We don’t want a StringStore and an IntStore and a BytesStore. We want one engine, generic over the key type K and value type V. Fill in MemStore’s inherent methods and its Store impl in store.rs:

   impl<K, V> MemStore<K, V> {
       pub fn new() -> Self
       where
           K: Eq + Hash,
       {
           MemStore {
               map: HashMap::new(),
           }
       }
   }

   impl<K, V> Store<K, V> for MemStore<K, V>
   where
       K: Eq + Hash,   // a HashMap key must be hashable and comparable
       V: Clone,       // get() hands back an owned copy (see below)
   {
       fn set(&mut self, key: K, value: V) -> Result<Option<V>> {
           Ok(self.map.insert(key, value))   // insert returns the old value
       }
       fn get(&self, key: &K) -> Option<V> {
           self.map.get(key).cloned()
       }
       fn delete(&mut self, key: &K) -> Result<Option<V>> {
           Ok(self.map.remove(key))
       }
       fn len(&self) -> usize {
           self.map.len()
       }
   }

The where clause is the interesting part. K: Eq + Hash are trait bounds — they say “this code only makes sense for key types that can be hashed and compared for equality,” which is precisely what a hash table needs. The compiler enforces it: try to use a key type that isn’t Hash and you get a clear error at the call site, not a mystery at runtime. Bounds are how generics stay safe — a generic function can only do to a T what its bounds permit.

By the numbers — why a HashMap, not a Vec

The data model is a dictionary, so lookup cost is everything. Find a key among N entries:

   Vec<(K, V)> linear scan : compares ≈ N/2 on average
   HashMap<K, V>           : compares ≈ 1   (hash to a bucket, check it)

At N = 1,000,000 keys that’s ~500,000 comparisons per GET versus ~1. The HashMap’s O(1)-average lookup is the reason a KV store can answer in microseconds while holding millions of keys.

Under the hood — generics are zero-cost (monomorphization)

A generic in Rust is not a runtime trick. When you actually use MemStore<String, String> and MemStore<u64, Vec<i32>>, the compiler stamps out a separate, specialized copy of the code for each concrete pair — a process called monomorphization. The generated machine code is identical to what you’d write by hand for that exact type: no boxing, no vtable, no per-call type checks. You get the ergonomics of “write once, use for any type” with the speed of hand-specialized code. The cost is paid at compile time (more code to compile) and in binary size, never at runtime. This is what Rust means by zero-cost abstraction: the abstraction compiles away.

It actually happened — HashDoS, and why Rust seeds its hasher randomly

In December 2011 (28C3), Alexander Klink and Julian Wälde showed that many web platforms could be knocked over by hash-collision denial of service: an attacker sends keys engineered to land in the same hash bucket, collapsing the HashMap’s O(1) lookups into O(n) and pinning the CPU. Rust’s standard HashMap defends against this by default — it uses SipHash with a random per-instance seed, so an attacker can’t predict which keys collide. The trade-off: SipHash is slightly slower than a trivial hash, which is why performance-sensitive code sometimes opts into a faster hasher when the keys are trusted. The default protects you; you give it up deliberately, in code you can see.

Lifetimes, in context: get clones, but it didn’t have to

Why does get return an owned Option<V> (a clone) instead of a cheaper borrow, Option<&V>? Add the borrowing version as an inherent method on MemStore and the answer becomes visible:

   impl<K, V> MemStore<K, V> {
       pub fn get_ref(&self, key: &K) -> Option<&V>
       where
           K: Eq + Hash,
       {
           self.map.get(key)
       }
   }

There are no 'a annotations here, yet a lifetime is absolutely present — the compiler infers it by lifetime elision. The signature desugars to:

   fn get_ref<'a>(&'a self, key: &K) -> Option<&'a V>

The rule: when a method takes &self, the returned reference is tied to self’s lifetime. Plain English: the borrowed &V is only valid as long as the MemStore it came from is alive and unchanged. That’s exactly what you want single-threaded — it’s free and safe.

So why does the trait’s get clone instead? Foreshadowing Day 5: once the map lives inside a lock, a borrow into it would have to outlive the lock guard — and the compiler won’t allow that, because reading freed-or-changing data is the very bug it exists to stop. Returning an owned clone lets us release the lock before the caller touches the value. The clone isn’t waste; it’s the price of letting go of the lock early. The lifetime rules made a design decision for us, on purpose.

Closures: iterate without exposing the map

We keep map private, but callers still need to walk the contents. A method that takes a closure lets them, without handing out the HashMap. Add it (and a keys snapshot helper) to the inherent impl:

   pub fn for_each<F: FnMut(&K, &V)>(&self, mut f: F) {
       for (k, v) in &self.map {
           f(k, v);
       }
   }

   pub fn keys(&self) -> Vec<K>
   where
       K: Clone,
   {
       self.map.keys().cloned().collect()
   }
   // caller: let mut total = 0; store.for_each(|_k, v| total += *v);

F: FnMut(&K, &V) is a trait bound again — this time on a closure type. FnMut means “callable, and allowed to mutate what it captured” (here, total). Closures are just types that implement one of the Fn/FnMut/FnOnce traits, so everything you learned about generics applies to them too.

Prove it: unit tests

store.rs carries its own #[cfg(test)] module — tests live next to the code they cover and can see its private items. These four pin down the contract you just built:

   #[cfg(test)]
   mod tests {
       use super::*;

       #[test]
       fn set_get_delete_roundtrip() {
           let mut s: MemStore<String, String> = MemStore::new();
           assert!(s.is_empty());

           // set returns the previous value (None the first time).
           assert_eq!(s.set("a".into(), "1".into()).unwrap(), None);
           assert_eq!(s.set("a".into(), "2".into()).unwrap(), Some("1".into()));
           assert_eq!(s.len(), 1);

           assert_eq!(s.get(&"a".into()), Some("2".into()));
           assert_eq!(s.get(&"missing".into()), None);

           assert_eq!(s.delete(&"a".into()).unwrap(), Some("2".into()));
           assert_eq!(s.delete(&"a".into()).unwrap(), None);
           assert!(s.is_empty());
       }

       #[test]
       fn generic_over_other_types() {
           // The same trait/impl, instantiated with different K and V. This only
           // compiles because the code never assumed String anywhere.
           let mut s: MemStore<u64, Vec<i32>> = MemStore::new();
           s.set(7, vec![1, 2, 3]).unwrap();
           assert_eq!(s.get(&7), Some(vec![1, 2, 3]));
           assert_eq!(s.len(), 1);
       }

       #[test]
       fn get_ref_borrows_without_cloning() {
           let mut s: MemStore<String, String> = MemStore::new();
           s.set("k".into(), "v".into()).unwrap();
           // Borrow tied to `s`; valid only while `s` is in scope.
           let borrowed: Option<&String> = s.get_ref(&"k".into());
           assert_eq!(borrowed.map(String::as_str), Some("v"));
       }

       #[test]
       fn for_each_visits_all_pairs_via_closure() {
           let mut s: MemStore<String, i32> = MemStore::new();
           s.set("a".into(), 10).unwrap();
           s.set("b".into(), 20).unwrap();
           let mut total = 0;
           s.for_each(|_k, v| total += *v);
           assert_eq!(total, 30);
       }
   }

cargo test runs them green. generic_over_other_types is the one that proves the design: the same engine serves <String, String> and <u64, Vec<i32>> because the code never assumed a concrete type.

Build it: a single-threaded store + a REPL

That’s enough engine to do real work. Wire it to standard input as a tiny REPL (read-eval-print loop) so you can drive it by hand — the Day 4 deliverable. Replace the placeholder src/main.rs with:

   use std::io::{self, BufRead, Write};

   use kvlite::{MemStore, Store};

   fn main() -> io::Result<()> {
       let mut store: MemStore<String, String> = MemStore::new();
       let stdin = io::stdin();
       let mut stdout = io::stdout();
       println!("kvlite repl (in-memory) — SET k v | GET k | DEL k | QUIT");

       for line in stdin.lock().lines() {
           let line = line?;
           let trimmed = line.trim();
           if trimmed.is_empty() {
               continue;
           }
           if trimmed.eq_ignore_ascii_case("QUIT") {
               break;
           }

           let mut parts = trimmed.splitn(3, ' ');
           let reply = match parts.next().map(str::to_ascii_uppercase).as_deref() {
               Some("SET") => match (parts.next(), parts.next()) {
                   (Some(k), Some(v)) => {
                       store.set(k.to_string(), v.to_string()).unwrap();
                       "OK".to_string()
                   }
                   _ => "ERR usage: SET <key> <value>".to_string(),
               },
               Some("GET") => match parts.next() {
                   Some(k) => match store.get(&k.to_string()) {
                       Some(v) => format!("VALUE {v}"),
                       None => "NIL".to_string(),
                   },
                   None => "ERR usage: GET <key>".to_string(),
               },
               Some("DEL") => match parts.next() {
                   Some(k) => {
                       if store.delete(&k.to_string()).unwrap().is_some() {
                           "DELETED".to_string()
                       } else {
                           "NOT_FOUND".to_string()
                       }
                   }
                   None => "ERR usage: DEL <key>".to_string(),
               },
               _ => "ERR unknown command".to_string(),
           };
           writeln!(stdout, "{reply}")?;
           stdout.flush()?;
       }
       Ok(())
   }

The loop is ordinary: read a line, split the first word into a command, dispatch to set/get/delete, print the reply.

   stdin ──▶ read line ──▶ parse ──▶ MemStore::{set,get,delete} ──▶ print
              ▲                                                       │
              └───────────────────── loop ◀───────────────────────────┘

Run it and try to break it:

   $ cargo run --
   kvlite repl (in-memory) — SET k v | GET k | DEL k | QUIT
   SET name ada
   OK
   GET name
   VALUE ada
   GET nope
   NIL
   DEL name
   DELETED

Feed it SET with no value, a GET for a missing key, a blank line. Each edge is a Result or an Option you had to handle — and the compiler made you handle them, which is the recurring lesson: what does building this force you to understand, and what is the compiler protecting you from? Here it’s a forgotten case and a borrow that outlives its data — both turned into errors you fix in seconds.

This REPL is in-memory and single-threaded, and it hand-rolls its parsing. On Day 7 the binary is rewritten so the REPL and the network server route through the same parse → execute path, so the protocol is written exactly once. Next, we make the store safe to share.

→ Next: Day 5 · Concurrency · Back to the Project 2 overview

Check your understanding

1. A trait and a struct play different roles here. State, in one sentence each, what Store<K, V> is responsible for versus what MemStore<K, V> is responsible for.
2. The impl has where K: Eq + Hash, V: Clone. Why does the HashMap require K: Eq + Hash, and why does our get require V: Clone?
3. What is monomorphization, and why does it mean Rust generics have no runtime cost?
4. get_ref has no 'a written anywhere, yet returns a borrowed Option<&V>. What lifetime does elision give the result, and in plain English what does that lifetime guarantee?
5. The trait’s get returns an owned clone instead of a reference. Give the concrete reason this matters the moment the map is put behind a lock (Day 5).

Show answers

1. Store<K, V> is the contract — it names the behaviour (set/get/delete/len) any store must provide, with no commitment to how. MemStore<K, V> is one implementation of that contract, backed by a HashMap.
2. A HashMap finds keys by hashing them into buckets and comparing for equality on collision, so the key type must be Hash (to bucket) and Eq (to compare) — K: Eq + Hash. Our get returns an owned value by calling .cloned(), which requires the value type to be duplicable — V: Clone.
3. Monomorphization is the compiler generating a separate specialized copy of generic code for each concrete type it’s used with. Because each copy is hand-specialized machine code (no vtable, no boxing, no runtime type checks), the abstraction compiles away — the cost is paid at compile time and in binary size, not at runtime.
4. Elision reads it as fn get_ref<'a>(&'a self, key: &K) -> Option<&'a V>: the result borrows from self. It guarantees the returned &V is valid only as long as the MemStore it came from is alive and not mutated — you can’t keep using it after the store changes or drops.
5. Once the HashMap lives inside a lock, a returned &V would borrow data owned by the lock guard; the borrow would have to outlive the guard, which the compiler forbids (it would be reading data the lock no longer protects). Returning an owned clone lets the lock be released before the caller uses the value — so cloning is what makes early unlock possible.