I'm writing my first Rust program, implementing a simple LruCache and processing some events.

The LruCache is used in a closure, to keep track of events that have been processed after polling them, and to skip them, if they have already been processed:

let mut evt_cache = LruSetCache::new(100_000);

// poll for events
loop {

    let unprocessed_events: Vec<Event> = unprocessed_events_serialized
        .into_iter()
        .filter_map(|evt| {
            let key = evt.as_bytes();

            if evt_cache.exists(&key) {
                None
            } else {
                evt_cache.put(key.clone());
                Some(Event::from_bytes(&evt.as_bytes()).unwrap())
            }
        })
        .collect();

    // ... process events

}

However, the compiler is not happy with the way I pass the [u8] key to the cache:

  --> src/main.rs:58:27
   |
51 |     let mut evt_cache = LruSetCache::new(100_000);
   |         ------------ lifetime `'1` appears in the type of `evt_cache`
...
58 |                 let key = evt.as_bytes();
   |                           ^^^^^^^^^^^^^ borrowed value does not live long enough
...
63 |                     evt_cache.put(key);
   |                     ----------------- argument requires that `evt` is borrowed for `'1`
...
66 |             })
   |             - `evt` dropped here while still borrowed

LruSetCache could be the culprit:

use std::collections::{HashSet, VecDeque};
use std::hash::Hash;

/// A LruCache that stores values (instead of (key, values) pairs).
///
/// You can
/// - insert elements,
/// - check for existence of an item.
/// It automatically frees memory after max_capacity is reached.
///
/// Basically, an LRUCache Backed by an `HashSet` instead of an `HashMap` that saves (little) memory and (very few) cpu cycles.
pub struct LruSetCache<T> {
    /// Elements will start to be evicted from the cache when this number of elements is reached.
    ///
    /// Note: In theory, we could avoid having this field here and keep track of the capacity by
    /// initializing the underlying `items` with `HashSet::with_capacity()` and by querying
    /// `HashSet::capacity()` when needed. However, if this inner detail implementation of `HashSet`
    /// that grows the capacity and starts re-allocating when the element is close to being full
    /// (rather than being full), then the LruCache would break.
    capacity: usize,

    /// Tracks which elements were added first, because they'll need to be removed when the
    /// maximum capacity is reached.
    /// Keeps track of the current capacity (`items.len()`).
    items: VecDeque<T>,

    /// Allows fast item existence check (O(1) as opposed to O(n) with the above VecDeque).
    items_set: HashSet<T>,
}

impl<T> LruCache<T> {
    pub fn new(capacity: usize) -> LruCache<T> {
        LruCache {
            capacity,
            items: VecDeque::with_capacity(capacity),
            items_set: HashSet::with_capacity(capacity),
        }
    }

    /// Checks whether an item exists.
    pub fn exists(&self, item: &T) -> bool {
        self.items_set.get(item).is_some()
    }

    /// Inserts an item.
    pub fn put(&mut self, item: T) {
        if self.items.len() >= self.capacity {
            // evict item that was inserted least recently
            self.items.pop_back();
            self.items_set.remove(&item);
        }

        self.items.push_front(&item);
        self.items_set.insert(&item);
    }
}

My debugging journey so far

I passed ownership to the LruCache::put function, by specifying a T parameter instead of a &T like in LruSetCache::set but that doesn't seem to be enough for Rust to make it survive after the closure ends. It's my understanding that the move only creates another pointer to the original value, so I understand why this is not enough.

So I've tried .clone()ing the string before passing it in. I understand the error is the [u8] key will get out of memory when the closure ends. However, cloning it anew, and passing that instead, doesn't help.

I'm guessing it's because it gets cloned in the stack, instead of the heap where it can escape the function cleanup.

So I've tried Boxing the key, so it would exist in the heap instead of the stack and not be cleaned up when the function returns. But I get basically the same error message:

    let key = Box::new(evt.as_bytes());

53 |     let mut evt_cache = LruSetCache::new(100_000);
   |         ------------- lifetime `'1` appears in the type of `evt_cache`
...
60 |                 let key = Box::new(evt.as_bytes());
   |                                    ^^^^^^^^^^^^^^ borrowed value does not live long enough
...
65 |                     evt_cache.put(key);
   |                     ------------------ argument requires that `eat` is borrowed for `'1`
...
68 |             })
   |             - `evt` dropped here while still borrowed

Rust wants the evt to outlive the closure for some reason, but I only need the key to do that.

What's going on here?

Solution 1:

Try replacing .clone() with either .to_owned() or .to_vec().

let unprocessed_events: Vec<Event> = unprocessed_events_serialized
    .into_iter()
    .filter_map(|evt| {
        let key = evt.as_bytes().to_owned(); // add `.to_vec()` or `.to_owned()`

        if evt_cache.exists(&key) {
            None
        } else {
            evt_cache.put(key); // Can remove .clone()
            Some(Event::from_bytes(&evt.as_bytes()).unwrap())
        }
    })
    .collect();

This will clone the entire key, so probably won't be desirable if your key is very big.

The version above will always clone the entire key, even if it already exists in evt_cache. This limitation can (probably) be lifted if the .exists() function is generic over Borrow<T> instead of just taking in a reference. (see how HashSet::contains is defined https://doc.rust-lang.org/std/collections/struct.HashSet.html#method.contains). This way you only need to call .to_owned() on evt_cache.put.

Shouldn't .clone() and .to_vec() do the same thing here?

The clone trait is defined in a way where we can't produce a different type from the one that is passed in. This causes problems for types like &[T], &str, Path etc. which is solved with the additional ToOwned trait.

From https://doc.rust-lang.org/std/borrow/trait.ToOwned.html

A generalization of Clone to borrowed data.

Some types make it possible to go from borrowed to owned, usually by implementing the Clone trait. But Clone works only for going from &T to T. The ToOwned trait generalizes Clone to construct owned data from any borrow of a given type.

So the .to_owned() for &[u8] does do what you expect, it just calls .to_vec()

https://doc.rust-lang.org/src/alloc/slice.rs.html#838-862