Borrow / BorrowMut

Level 14 — Advanced Traits & Type System Standard library conversion traits (std::borrow::Borrow and std::borrow::BorrowMut) that perform reference conversions with strict semantic guarantees that Hash, Eq, and Ord behavior remain identical between the owned and borrowed forms.

1. Prerequisites

• AsRef / AsMut — Reference conversion traits (contrasted with Borrow's hashing/equality equivalence guarantees).
• HashMap and HashSet — Standard collections that rely on Borrow for key lookups.
• Trait — Trait implementation mechanics (impl Trait for Type).

2. Term Category

Rust Standard Traits (borrowed reference abstraction traits): Borrow (std::borrow::Borrow<Borrowed>) and BorrowMut (std::borrow::BorrowMut<Borrowed>) are reference borrowing traits in Rust. While superficially similar to AsRef, Borrow carries a mandatory semantic invariant contract: an implementation impl Borrow<B> for A guarantees that the borrowed form B produces the exact same Hash, Eq, and Ord results as the owned form A. This property allows associative collections like HashMap<K, V> to look up entries using a borrowed key &Q (e.g. searching a HashMap<String, V> using a string slice &str) without allocating a new owned key.

3. Explanation

(1) Design Motivation — "Why did we design this?"

Consider a key-value hash map storing owned strings as keys: HashMap<String, UserData>.

To retrieve an entry from the map using map.get(...):

• If get required an exact owned key reference &String, you would be forced to allocate a new String or pass &String every time you queried the map.
• If get used AsRef<str>, any type that yields a &str could be passed. But what if a custom type implemented AsRef<str> by returning a lowercase version of a string, while its Hash and Eq implementation operated on uppercase characters?
  • Searching the HashMap with that type would compute a different hash value than the key stored in the map! The hash map lookup would fail or find the wrong entry, breaking container invariants.

Rust introduced Borrow<Borrowed> to solve key lookup ergonomics with mathematical hashing/equality guarantees:

1. Semantic Invariant: Borrow<B> requires that a.borrow() == b.borrow() is TRUE if and only if a == b, and hash(a.borrow()) is identical to hash(a).
2. HashMap<K, V>::get<Q> declares its parameter as Q: Borrow<K> + Hash + Eq.
3. Because String implements Borrow<str> and guarantees hash/equality equivalence with &str, you can look up entries in a HashMap<String, V> passing a temporary string slice &str directly without allocating a new String!

(2) Reality Metaphor

Imagine a Notary-Certified Biometric ID Copy:

• AsRef<T> is like a photo of your ID on a smartphone: it visually shows your name (converts to &T for display/processing), but a bank teller cannot use it to verify an official legal signature or open a vault because the phone photo lacks security notary seals (no Hash/Eq equivalence guarantee).
• Borrow<T> is a Notary-Certified Biometric Copy:
  • The notary seal guarantees that the fingerprint, signature, and legal identity on the copy (Hash and Eq values) match the original passport (owned type K) 100% identically.
  • The bank teller (HashMap lookup) accepts the certified copy (&str) to unlock the vault (find entry K) with complete legal confidence that the signature will never mismatch.

(3) Code Examples

Short Snippet (Zero-Allocation HashMap Lookups via Borrow)

use std::collections::HashMap;

fn main() {
    let mut user_scores: HashMap<String, u32> = HashMap::new();
    user_scores.insert(String::from("Alice"), 95);
    user_scores.insert(String::from("Bob"), 88);

    // Look up entry using string slice `&str` (borrowed form of `String`)
    let lookup_key: &str = "Alice";

    // `HashMap::get` takes `&Q where String: Borrow<Q>`.
    // Because `String` implements `Borrow<str>`, no `String` allocation occurs!
    if let Some(score) = user_scores.get(lookup_key) {
        println!("Alice's score: {}", score); // 95
    }
}

Fuller Example (Custom Type Implementing Borrow with Hash/Eq Invariant)

use std::borrow::Borrow;
use std::collections::HashSet;
use std::hash::{Hash, Hasher};

#[derive(Debug)]
pub struct CaseInsensitiveString(String);

impl CaseInsensitiveString {
    pub fn new(s: impl Into<String>) -> Self {
        CaseInsensitiveString(s.into().to_lowercase())
    }
}

// Ensure Hash operates on the lowercase string
impl Hash for CaseInsensitiveString {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.hash(state);
    }
}

impl PartialEq for CaseInsensitiveString {
    fn eq(&self, other: &Self) -> bool {
        self.0 == other.0
    }
}

impl Eq for CaseInsensitiveString {}

// 1. Implement `Borrow<str>`
// SAFETY INVARIANT: `str` hashing and equality must match `CaseInsensitiveString`.
// Since we stored the inner string as lowercase, `str` passed to `borrow()` must be lowercase.
impl Borrow<str> for CaseInsensitiveString {
    fn borrow(&self) -> &str {
        &self.0
    }
}

fn main() {
    let mut set = HashSet::new();
    set.insert(CaseInsensitiveString::new("Admin"));

    // Look up in HashSet using plain `&str` slice:
    // Searching for "admin" matches because `CaseInsensitiveString` stores "admin"
    // and implements `Borrow<str>` with identical Hash/Eq behavior.
    assert!(set.contains("admin"));
    println!("HashSet lookup via `Borrow<str>` succeeded!");
}

4. Borrow vs AsRef vs Deref Comparison

4. Common Mistakes & Pitfalls

Mistake 1: Violating the Hash/Eq Invariant in Custom Borrow Implementations

The mistake: Implementing Borrow<str> for a type whose Hash or Eq implementation yields different results than str::hash / str::eq.

Why it's wrong: Breaking the Borrow invariant causes HashMap and HashSet lookups to fail silently. The map will compute the wrong bucket hash or fail equality comparisons, leading to missing entries or corrupted map operations.

Incorrect:

struct UserKey { name: String, id: u64 }

impl Hash for UserKey {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.name.hash(state);
        self.id.hash(state); // Hashes both name AND id
    }
}

// ❌ VIOLATES BORROW INVARIANT!
// Borrowing `&str` hashes ONLY `name`, which produces a different hash than `UserKey`!
impl Borrow<str> for UserKey {
    fn borrow(&self) -> &str {
        &self.name
    }
}

Fix:

// Only implement `Borrow<B>` if `A` and `B` have identical `Hash` and `Eq` results.

Mistake 2: Using AsRef instead of Borrow in Generic Map Lookup Algorithms

The mistake: Writing a custom hash map lookup function fn find_key<K: AsRef<Q>, Q>(map: &HashMap<K, V>, query: &Q) thinking AsRef is sufficient.

Why it's wrong: AsRef does not require a.as_ref() == b.as_ref() to match a == b. Using AsRef for lookups risks silent logic bugs when types perform non-equivalent reference conversions.

Mistake 3: Confusing Blanket Borrow<T> for T

The mistake: Writing an explicit impl Borrow<MyType> for MyType in your crate.

Why it's wrong: Rust includes a standard library blanket implementation impl<T> Borrow<T> for T. Attempting to implement Borrow<T> for T manually causes a duplicate implementation coherence compiler error E0119.

5. Practice Exercises

Exercise 1: Zero-Allocation Threat Signature Lookup in Network Packets (Borrow<[u8]>)

Scenario: In an embedded network firewall, incoming network packets are stored in owned heap-allocated PacketBuffer structures (struct PacketBuffer { payload: Vec<u8> }). To detect malicious traffic in real time, known threat signatures are maintained inside a HashSet<PacketBuffer>. Searching the hash set using raw borrowed byte slices (&[u8]) must occur with zero heap allocation on the hot path. Implement Hash, PartialEq, Eq, and Borrow<[u8]> for PacketBuffer such that HashSet::contains can accept raw &[u8] query slices. Include complete unit tests with assertions (assert!, assert_eq!) proving lookup correctness and demonstrating hash equality between PacketBuffer and &[u8].

use std::borrow::Borrow;
use std::collections::HashSet;
use std::hash::{Hash, Hasher, DefaultHasher};

#[derive(Debug, Clone)]
pub struct PacketBuffer {
    pub payload: Vec<u8>,
}

impl PacketBuffer {
    pub fn new(payload: Vec<u8>) -> Self {
        Self { payload }
    }
}

// Delegate Hash directly to the inner payload slice
impl Hash for PacketBuffer {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.payload.hash(state);
    }
}

// Delegate equality comparison to slice equality
impl PartialEq for PacketBuffer {
    fn eq(&self, other: &Self) -> bool {
        self.payload == other.payload
    }
}

impl Eq for PacketBuffer {}

// Implement Borrow<[u8]> returning a reference to the inner slice
impl Borrow<[u8]> for PacketBuffer {
    fn borrow(&self) -> &[u8] {
        &self.payload
    }
}

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

    fn compute_hash<T: Hash + ?Sized>(val: &T) -> u64 {
        let mut hasher = DefaultHasher::new();
        val.hash(&mut hasher);
        hasher.finish()
    }

    #[test]
    fn test_zero_allocation_hashset_lookup() {
        let mut signature_db = HashSet::new();
        let mal_packet = PacketBuffer::new(vec![0xDE, 0xAD, 0xBE, 0xEF]);
        signature_db.insert(mal_packet.clone());

        let raw_query_slice: &[u8] = &[0xDE, 0xAD, 0xBE, 0xEF];

        // 1. Verify that HashSet can be queried directly with &[u8]
        assert!(signature_db.contains(raw_query_slice));

        // 2. Verify that non-matching slices are rejected
        let clean_slice: &[u8] = &[0x00, 0x01, 0x02, 0x03];
        assert!(!signature_db.contains(clean_slice));

        // 3. Mathematical proof: owned type and borrowed slice produce identical hashes
        assert_eq!(
            compute_hash(&mal_packet),
            compute_hash(raw_query_slice),
            "Borrow invariant failure: PacketBuffer and &[u8] hashes must be identical"
        );
    }
}

Exercise 2: Strict Hash and Eq Equivalence Verification for Case-Normalized Keys (Borrow<str>)

Scenario: An API gateway normalizes header routing keys by storing strings in uppercase inside struct CanonicalKey(String). To allow routing lookups in a HashMap<CanonicalKey, String> using standard string slices (&str), CanonicalKey implements Borrow<str>. Implement CanonicalKey, implement Borrow<str>, and write a generic lookup function is_authorized<Q>(map: &HashMap<CanonicalKey, String>, key: &Q) -> bool. Write unit tests with assertions validating that hash(&key) and hash(key.borrow()) yield identical hash values, demonstrating strict compliance with the mandatory Borrow semantic invariant contract.

use std::borrow::Borrow;
use std::collections::HashMap;
use std::hash::{Hash, Hasher, DefaultHasher};

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CanonicalKey(String);

impl CanonicalKey {
    pub fn new(s: &str) -> Self {
        CanonicalKey(s.to_uppercase())
    }

    pub fn as_str(&self) -> &str {
        &self.0
    }
}

// Delegate Hash to inner uppercase string
impl Hash for CanonicalKey {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.hash(state);
    }
}

// Implement Borrow<str>
impl Borrow<str> for CanonicalKey {
    fn borrow(&self) -> &str {
        &self.0
    }
}

// Generic lookup function accepting any borrowed query key Q
pub fn is_authorized<Q>(map: &HashMap<CanonicalKey, String>, key: &Q) -> bool
where
    CanonicalKey: Borrow<Q>,
    Q: Hash + Eq + ?Sized,
{
    map.contains_key(key)
}

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

    fn compute_hash<T: Hash + ?Sized>(val: &T) -> u64 {
        let mut hasher = DefaultHasher::new();
        val.hash(&mut hasher);
        hasher.finish()
    }

    #[test]
    fn test_canonical_key_borrow_contract() {
        let mut auth_map = HashMap::new();
        let key = CanonicalKey::new("admin_token"); // Normalizes to "ADMIN_TOKEN"
        auth_map.insert(key.clone(), "Role_SuperAdmin".to_string());

        // 1. Zero-allocation lookup with upper-case &str slice
        let query_uppercase: &str = "ADMIN_TOKEN";
        assert!(is_authorized(&auth_map, query_uppercase));

        // 2. Hash equivalence assertion
        let owned_hash = compute_hash(&key);
        let borrowed_hash = compute_hash(key.borrow());
        let str_hash = compute_hash(query_uppercase);

        assert_eq!(owned_hash, borrowed_hash);
        assert_eq!(owned_hash, str_hash);

        // 3. Demonstrating query preparation requirement:
        // Since CanonicalKey stores "ADMIN_TOKEN", querying raw "admin_token" produces a different hash!
        let raw_lowercase: &str = "admin_token";
        assert_ne!(compute_hash(raw_lowercase), str_hash);
        assert!(!is_authorized(&auth_map, raw_lowercase));
    }
}

Exercise 3: In-Place Embedded Sensor Payload Sanitization via BorrowMut<[u8]>

Scenario: In an embedded no_std telemetry driver, incoming sensor frames are buffered inside struct SensorFrame { buffer: [u8; 32], len: usize }. Encryption functions and checksum calculators must operate on active payload bytes (&buffer[..len]) without transferring ownership or reallocating memory. Implement Borrow<[u8]> and BorrowMut<[u8]> for SensorFrame. Write generic functions sanitize_payload<B: BorrowMut<[u8]>>(buf: &mut B, xor_mask: u8) and calculate_checksum<B: Borrow<[u8]>>(buf: &B) -> u8. Write unit tests with assertions verifying in-place byte mutation and checksum computation.

use std::borrow::{Borrow, BorrowMut};

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SensorFrame {
    buffer: [u8; 32],
    len: usize,
}

impl SensorFrame {
    pub fn new(data: &[u8]) -> Self {
        assert!(data.len() <= 32, "Payload length exceeds fixed buffer capacity of 32 bytes");
        let mut buffer = [0u8; 32];
        buffer[..data.len()].copy_from_slice(data);
        Self {
            buffer,
            len: data.len(),
        }
    }

    pub fn active_payload(&self) -> &[u8] {
        &self.buffer[..self.len]
    }
}

// Implement Borrow<[u8]> for active payload slice
impl Borrow<[u8]> for SensorFrame {
    fn borrow(&self) -> &[u8] {
        &self.buffer[..self.len]
    }
}

// Implement BorrowMut<[u8]> for mutable active payload slice
impl BorrowMut<[u8]> for SensorFrame {
    fn borrow_mut(&mut self) -> &mut [u8] {
        &mut self.buffer[..self.len]
    }
}

// Generic function accepting any mutable borrower of [u8]
pub fn sanitize_payload<B: BorrowMut<[u8]>>(buf: &mut B, xor_mask: u8) {
    let slice: &mut [u8] = buf.borrow_mut();
    for byte in slice.iter_mut() {
        *byte ^= xor_mask;
    }
}

// Generic function accepting any immutable borrower of [u8]
pub fn calculate_checksum<B: Borrow<[u8]>>(buf: &B) -> u8 {
    let slice: &[u8] = buf.borrow();
    slice.iter().fold(0u8, |acc, &b| acc.wrapping_add(b))
}

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

    #[test]
    fn test_sensor_frame_borrow_mut_sanitization() {
        let raw_data = &[0x10, 0x20, 0x30, 0x40];
        let mut frame = SensorFrame::new(raw_data);

        // 1. Verify initial checksum calculation via Borrow<[u8]>
        let initial_checksum = calculate_checksum(&frame);
        assert_eq!(initial_checksum, 0x10 + 0x20 + 0x30 + 0x40); // 0xA0

        // 2. Perform in-place mutation using BorrowMut<[u8]>
        sanitize_payload(&mut frame, 0xFF);

        // 3. Assert that payload bytes inside SensorFrame were modified in-place
        let expected_mutated = &[0xEF, 0xDF, 0xCF, 0xBF];
        assert_eq!(frame.borrow(), expected_mutated);

        // 4. Re-sanitize to restore original data
        sanitize_payload(&mut frame, 0xFF);
        assert_eq!(frame.borrow(), raw_data);
    }
}

6. Related Terms

• AsRef / AsMut — Reference conversion traits without Hash/Eq equivalence requirements.
• Deref / DerefMut Traits — Implicit smart pointer dereferencing traits.
• HashMap and HashSet — Collections that rely on Borrow for key lookups.
• Trait — Trait abstraction mechanism.
• Borrow<T> Trait — Related concept: Borrow<T> Trait.

7. Key Takeaways

• Borrow<Borrowed> (fn borrow(&self) -> &Borrowed) and BorrowMut perform reference borrowing conversions.
• Mandatory Semantic Contract: Borrow requires that the owned type and borrowed type produce identical Hash, Eq, and Ord results.
• It powers zero-allocation key lookups in HashMap and HashSet (e.g. looking up HashMap<String, V> using &str).
• Unlike AsRef (which only provides cheap reference conversion), Borrow guarantees mathematical equivalence between owned and borrowed keys.
• Every type T automatically implements Borrow<T> via a standard library blanket implementation.