Panic Safety and Invariants

title: “HashMap Panic Safety and Invariants in Rust” meta_description: “Learn how to maintain HashMap invariants through panics, implement drop guards, and ensure memory safety in unsafe code.” keywords: [“rust panic safety”, “hashmap invariants”, “drop guard”, “panic unwinding”, “memory safety rust”]

⚠️ Reinventing from Scratch: Building HashMap

Chapter 7 — “Panic Safety and Invariants”

“Your code will panic. The question is: will it leak memory when it does?”

🧭 7.1. The Panic Problem

Rust functions can panic (like exceptions in other languages):

map.insert(key, value);  // What if Hash::hash panics?
map.remove(&key);         // What if Eq::eq panics?

If a panic occurs mid-operation, will our HashMap be in a valid state?

💣 7.2. Invariants We Must Maintain

Our HashMap has critical invariants:

I1: Length Consistency

// len always equals number of occupied slots
self.len == self.entries.iter().filter(|e| e.is_occupied()).count()

I2: No Dangling Pointers

// All occupied entries have valid, initialized key/value

I3: No Double-Drops

// Each entry is dropped exactly once

I4: Valid State After Panic

// If any operation panics, HashMap remains usable

🎯 7.3. Where Panics Can Occur

During Hash Computation

impl Hash for BadKey {
    fn hash<H: Hasher>(&self, state: &mut H) {
        if self.value == "panic" {
            panic!("Hash panicked!");  // ❌
        }
        self.value.hash(state);
    }
}

map.insert(BadKey { value: "panic".into() }, 42);
// Panic! HashMap state???

During Equality Check

impl PartialEq for BadKey {
    fn eq(&self, other: &Self) -> bool {
        panic!("Eq panicked!");  // ❌
    }
}

map.get(&key);  // Panic during lookup!

During Drop

impl Drop for BadValue {
    fn drop(&mut self) {
        panic!("Drop panicked!");  // ❌❌❌
    }
}

🛡️ 7.4. Panic-Safe Insert

Let’s make insert panic-safe:

pub fn insert(&mut self, key: K, value: V) -> Option<V> {
    // Step 1: Hash the key (might panic)
    let hash = {
        let mut hasher = self.hasher_builder.build_hasher();
        key.hash(&mut hasher);  // Panic possible here!
        hasher.finish()
    };
    // If panic occurred, HashMap is unchanged ✓
    
    // Step 2: Check if we need to grow (might panic during allocation)
    if self.should_grow() {
        self.grow();  // Panic possible here!
    }
    // If panic during grow, old HashMap is dropped cleanly ✓
    
    // Step 3: Insert the entry
    self.insert_entry(hash, key, value)  // Panic possible in Eq!
}

Analysis

Panic during hash:

  • HashMap unchanged
  • key and value are dropped cleanly
  • ✅ Safe!

Panic during grow:

  • Old entries moved to new map
  • If panic during rehash, partially-built map is dropped
  • Original map already consumed
  • Might lose some entries, but no UB!
  • ⚠️ Not ideal, but safe

Panic during insert (in Eq check):

  • HashMap is partially modified
  • Need to be careful about len tracking

🔒 7.5. The Length Problem

Consider this insert:

fn insert_entry(&mut self, hash: u64, mut key: K, mut value: V) -> Option<V> {
    let index = self.find_slot(&key);  // Might panic in Eq!
    
    match &mut self.entries[index] {
        Empty => {
            self.entries[index] = Occupied(Entry { key, value, hash });
            self.len += 1;  // ← What if we panic before this?
            None
        }
        Occupied(old) if old.key == key => {  // ← Panic possible here!
            Some(std::mem::replace(&mut old.value, value))
        }
        // ...
    }
}

Problem: If we panic after inserting but before incrementing len, invariant I1 is broken!

Solution: Update len LAST

fn insert_entry(&mut self, hash: u64, key: K, value: V) -> Option<V> {
    // Track if we're adding a new entry
    let mut added_new = false;
    
    let index = self.find_slot(&key);  // Might panic
    
    let old_value = match &mut self.entries[index] {
        Empty => {
            self.entries[index] = Occupied(Entry { key, value, hash });
            added_new = true;
            None
        }
        Occupied(old) if old.key == key => {
            Some(std::mem::replace(&mut old.value, value))
        }
        // ...
    };
    
    if added_new {
        self.len += 1;  // Only increment if we actually added
    }
    
    old_value
}

🔥 7.6. Drop Guards

For complex operations, use guard objects:

struct LenGuard<'a> {
    len: &'a mut usize,
    increment: bool,
}

impl<'a> LenGuard<'a> {
    fn new(len: &'a mut usize) -> Self {
        Self { len, increment: false }
    }
    
    fn will_increment(&mut self) {
        self.increment = true;
    }
}

impl Drop for LenGuard<'_> {
    fn drop(&mut self) {
        if self.increment {
            *self.len += 1;
        }
    }
}

Usage:

fn insert_entry(&mut self, hash: u64, key: K, value: V) -> Option<V> {
    let mut guard = LenGuard::new(&mut self.len);
    
    let index = self.find_slot(&key);  // Might panic
    
    match &mut self.entries[index] {
        Empty => {
            self.entries[index] = Occupied(Entry { key, value, hash });
            guard.will_increment();  // Only increments if we reach here
            None
        }
        // ...
    }
    
    // Guard drops here, increments len if will_increment was called
}

🧹 7.7. Safe Resize

Resizing is the most dangerous operation:

fn grow(&mut self) {
    let new_capacity = self.capacity * 2;
    let mut new_entries = vec![Empty; new_capacity];
    
    // Danger zone: moving entries
    for old_entry in self.entries.drain(..) {
        if let Occupied(entry) = old_entry {
            // Reinsert into new_entries
            // What if Eq panics here?
        }
    }
    
    self.entries = new_entries;
}

Problem: If panic during rehash:

  • Old entries partially moved
  • New entries partially filled
  • Some entries might be lost!

Solution: Build Completely, Then Swap

fn grow(&mut self) {
    let new_capacity = self.capacity * 2;
    
    // Build new map completely
    let mut new_map = Self::with_capacity_and_hasher(
        new_capacity,
        self.hasher_builder.clone()
    );
    
    // Move entries (might panic, but new_map is separate)
    for entry in self.entries.drain(..) {
        if let Occupied(e) = entry {
            // If panic here, new_map is dropped, old entries still in self
            new_map.insert_hashed(e.hash, e.key, e.value);
        }
    }
    
    // Only swap if everything succeeded
    *self = new_map;
}

Better: All-or-nothing semantics.

🧪 7.8. Testing Panic Safety

#[test]
#[should_panic]
fn test_panic_during_insert() {
    struct PanicKey;
    
    impl Hash for PanicKey {
        fn hash<H: Hasher>(&self, state: &mut H) {
            panic!("Intentional panic!");
        }
    }
    
    impl PartialEq for PanicKey {
        fn eq(&self, _: &Self) -> bool { true }
    }
    impl Eq for PanicKey {}
    
    let mut map = MyHashMap::new();
    map.insert("safe", 1);
    
    // This will panic
    let _ = map.insert(PanicKey, 2);
    
    // If we could reach here (we can't, but in theory):
    // HashMap should still have "safe" entry and be valid
}

Using catch_unwind for Testing

use std::panic::catch_unwind;

#[test]
fn test_map_valid_after_panic() {
    let mut map = MyHashMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    
    // Try to insert panic-inducing key
    let result = catch_unwind(|| {
        map.insert(PanicKey, 3);
    });
    
    assert!(result.is_err());  // Panicked as expected
    
    // HashMap should still work!
    assert_eq!(map.len(), 2);
    assert_eq!(map.get("a"), Some(&1));
}

📋 7.9. Invariant Checklist

After every operation, verify:

#[cfg(debug_assertions)]
fn check_invariants(&self) {
    // I1: Length matches occupied count
    let actual_len = self.entries.iter()
        .filter(|e| matches!(e, Occupied(_)))
        .count();
    assert_eq!(self.len, actual_len, "Length invariant violated!");
    
    // I2: All entries have correct distances
    for (i, entry) in self.entries.iter().enumerate() {
        if let Occupied(e) = entry {
            let ideal = self.ideal_index(e.hash);
            let distance = self.probe_distance(e.hash, i);
            // Distance should be reasonable
            assert!(distance < self.capacity, "Invalid distance!");
        }
    }
    
    // I3: No duplicate keys
    let mut seen = std::collections::HashSet::new();
    for entry in &self.entries {
        if let Occupied(e) = entry {
            assert!(seen.insert(&e.key), "Duplicate key!");
        }
    }
}

🧠 7.10. Chapter Takeaways

Concept Purpose
Panic safety HashMap valid even after panic
Drop guards Ensure invariants via RAII
All-or-nothing Complete operation or rollback
Invariant checks Debug-mode validation
catch_unwind Test panic behavior

🚀 7.11. What’s Next

We now have a robust, panic-safe HashMap!

Next: Chapter 8 — Tests, Benchmarks, and Miri

Learn how to:

  • Write comprehensive test suites
  • Benchmark performance
  • Use Miri to catch undefined behavior

💡 Exercises

  1. Add check_invariants calls after each operation
  2. Implement drop guard for len tracking
  3. Test panic scenarios with catch_unwind
  4. Verify no memory leaks when panic occurs
  5. Measure panic overhead (should be zero in happy path)

Next: Chapter 8 — Tests, Benchmarks, and Miri 🧪