behavior_actors/persistence/
cache.rs

1//! Bounded least-recently-used value policy.
2
3#[cfg(test)]
4use behavior::MessageProtocol;
5use behavior::{
6    Actions, Address, Behavior, BehaviorActed, BehaviorBase, Never, NoBirths, Protocol, User,
7};
8use thiserror::Error;
9
10use crate::DeliveryRoute;
11
12/// One cache entry.
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct CacheEntry<K, V> {
15    /// Application-defined key.
16    pub key: K,
17    /// Owned cached value.
18    pub value: V,
19}
20
21/// Complete valid cache state ordered least- to most-recently used.
22#[derive(Debug, Clone, PartialEq, Eq)]
23pub struct CacheState<K, V> {
24    /// Positive maximum number of entries.
25    pub capacity: usize,
26    entries: Vec<CacheEntry<K, V>>,
27}
28
29impl<K, V> CacheState<K, V> {
30    /// Entries ordered from next eviction candidate to most recently used.
31    #[must_use]
32    pub fn entries(&self) -> &[CacheEntry<K, V>] {
33        &self.entries
34    }
35
36    /// Current retained entry count.
37    #[must_use]
38    pub fn len(&self) -> usize {
39        self.entries.len()
40    }
41
42    /// Whether the cache currently retains no entry.
43    #[must_use]
44    pub fn is_empty(&self) -> bool {
45        self.entries.is_empty()
46    }
47}
48
49/// Factual result of one [`Cache`] command.
50#[derive(Debug, Clone, PartialEq, Eq)]
51pub enum CacheResult<K, V> {
52    /// The value is stored as most recently used.
53    Stored {
54        /// Stored key.
55        key: K,
56        /// Previous value replaced at the same key, if any.
57        replaced: Option<V>,
58        /// Least-recently-used entry evicted for capacity, if any.
59        evicted: Option<CacheEntry<K, V>>,
60    },
61    /// Lookup found and refreshed one value.
62    Hit { key: K, value: V },
63    /// Lookup found no value.
64    Miss { key: K },
65    /// Explicit removal returned ownership.
66    Removed { key: K, value: V },
67    /// Explicit removal found no value.
68    Absent { key: K },
69}
70
71/// Commands accepted by [`Cache`].
72pub enum CacheMessage<K, V, Route> {
73    /// Insert or replace one value.
74    Put {
75        /// Key to store.
76        key: K,
77        /// Owned value to store.
78        value: V,
79        /// Typed result recipient.
80        reply_to: Route,
81    },
82    /// Lookup and refresh one key.
83    Get {
84        /// Key to lookup.
85        key: K,
86        /// Typed result recipient.
87        reply_to: Route,
88    },
89    /// Remove one key without refreshing another entry.
90    Remove {
91        /// Key to remove.
92        key: K,
93        /// Typed result recipient.
94        reply_to: Route,
95    },
96}
97
98/// Invalid cache definition.
99#[derive(Debug, Error, Clone, Copy, PartialEq, Eq)]
100pub enum CacheConfigError {
101    /// Zero capacity could never retain accepted ownership.
102    #[error("cache capacity must be positive")]
103    ZeroCapacity,
104}
105
106/// Validated, protocol-independent cache capacity.
107#[derive(Debug, Clone, Copy, PartialEq, Eq)]
108pub struct CacheConfiguration {
109    capacity: usize,
110}
111
112impl CacheConfiguration {
113    /// Validate capacity before binding it to key, value, or address types.
114    ///
115    /// # Errors
116    ///
117    /// Returns [`CacheConfigError::ZeroCapacity`] for zero capacity.
118    pub fn new(capacity: usize) -> Result<Self, CacheConfigError> {
119        if capacity == 0 {
120            return Err(CacheConfigError::ZeroCapacity);
121        }
122        Ok(Self { capacity })
123    }
124}
125
126/// Bounded deterministic recency cache behavior.
127///
128/// State is [`CacheState`] in least- to most-recent order. Put and successful
129/// get move the key to the most-recent position. Replacement returns the old
130/// value; capacity eviction returns the complete oldest entry. Miss and absent
131/// are factual results, not errors. Every command emits exactly one typed
132/// result after committing its state transition. Initialization is empty, no
133/// actors are created, and the cache never terminates itself. Recency and
134/// eviction are Bombay policy, not durability: Mnesis remains the durable
135/// authority. The standard-library vector is intentional for this initial
136/// deterministic policy; an `lru` dependency requires a demonstrated scale
137/// need and must remain private. No method has a semantic panic condition.
138pub struct Cache<A, K, V, Route>
139where
140    A: Address,
141    Route: DeliveryRoute,
142    Route::Protocol: Protocol<Addr = A, Msg = CacheResult<K, V>>,
143{
144    state: CacheState<K, V>,
145    address: core::marker::PhantomData<fn() -> (A, Route)>,
146}
147
148impl<A, K, V, Route> Cache<A, K, V, Route>
149where
150    A: Address,
151    Route: DeliveryRoute,
152    Route::Protocol: Protocol<Addr = A, Msg = CacheResult<K, V>>,
153{
154    /// Bind validated capacity to an empty cache actor.
155    #[must_use]
156    pub fn new(configuration: CacheConfiguration) -> Self {
157        Self {
158            state: CacheState {
159                capacity: configuration.capacity,
160                entries: Vec::with_capacity(configuration.capacity),
161            },
162            address: core::marker::PhantomData,
163        }
164    }
165
166    /// Borrow the complete current recency state.
167    #[must_use]
168    pub const fn state(&self) -> &CacheState<K, V> {
169        &self.state
170    }
171}
172
173impl<A, K, V, Route> BehaviorBase for Cache<A, K, V, Route>
174where
175    A: Address,
176    Route: DeliveryRoute,
177    Route::Protocol: Protocol<Addr = A, Msg = CacheResult<K, V>>,
178{
179    type Base = Self;
180
181    fn base(&self) -> &Self {
182        self
183    }
184}
185
186impl<A, K, V, Route> behavior::Protocol for Cache<A, K, V, Route>
187where
188    A: Address,
189    Route: DeliveryRoute,
190    Route::Protocol: Protocol<Addr = A, Msg = CacheResult<K, V>>,
191{
192    type Addr = A;
193    type Msg = CacheMessage<K, V, Route>;
194}
195
196impl<A, K, V, Route> Behavior for Cache<A, K, V, Route>
197where
198    A: Address,
199    K: Clone + Eq,
200    V: Clone,
201    Route: DeliveryRoute,
202    Route::Protocol: Protocol<Addr = A, Msg = CacheResult<K, V>>,
203    Route::Sends: behavior::SendsFor<User<A, CacheMessage<K, V, Route>>>,
204{
205    type Protocol = Self;
206    type Event = User<A, behavior::BehaviorMessage<Self>>;
207    type Sends = Route::Sends;
208    type Ph = Never;
209    type Error = Never;
210    type Birth = NoBirths;
211
212    fn transition(&mut self, _: behavior::ActiveTurn, event: Self::Event) -> BehaviorActed<Self> {
213        let (reply_to, result) = match event.message {
214            CacheMessage::Put {
215                key,
216                value,
217                reply_to,
218            } => {
219                let replaced = self
220                    .state
221                    .entries
222                    .iter()
223                    .position(|entry| entry.key == key)
224                    .map(|index| self.state.entries.remove(index).value);
225                let evicted =
226                    if replaced.is_none() && self.state.entries.len() == self.state.capacity {
227                        Some(self.state.entries.remove(0))
228                    } else {
229                        None
230                    };
231                self.state.entries.push(CacheEntry {
232                    key: key.clone(),
233                    value,
234                });
235                (
236                    reply_to,
237                    CacheResult::Stored {
238                        key,
239                        replaced,
240                        evicted,
241                    },
242                )
243            }
244            CacheMessage::Get { key, reply_to } => {
245                let result = self
246                    .state
247                    .entries
248                    .iter()
249                    .position(|entry| entry.key == key)
250                    .map_or_else(
251                        || CacheResult::Miss { key: key.clone() },
252                        |index| {
253                            let entry = self.state.entries.remove(index);
254                            let value = entry.value.clone();
255                            self.state.entries.push(entry);
256                            CacheResult::Hit {
257                                key: key.clone(),
258                                value,
259                            }
260                        },
261                    );
262                (reply_to, result)
263            }
264            CacheMessage::Remove { key, reply_to } => {
265                let result = self
266                    .state
267                    .entries
268                    .iter()
269                    .position(|entry| entry.key == key)
270                    .map_or_else(
271                        || CacheResult::Absent { key: key.clone() },
272                        |index| {
273                            let entry = self.state.entries.remove(index);
274                            CacheResult::Removed {
275                                key: key.clone(),
276                                value: entry.value,
277                            }
278                        },
279                    );
280                (reply_to, result)
281            }
282        };
283        Ok(Actions::send(reply_to.deliver(result)))
284    }
285}
286
287#[cfg(test)]
288mod tests {
289    use super::*;
290    use crate::Activate as _;
291    use behavior::{MailAddr, Recipient};
292
293    fn put(
294        cache: &mut crate::Active<
295            Cache<MailAddr, u8, u16, Recipient<MessageProtocol<MailAddr, CacheResult<u8, u16>>>>,
296        >,
297        reply: Recipient<MessageProtocol<MailAddr, CacheResult<u8, u16>>>,
298        key: u8,
299        value: u16,
300    ) -> CacheResult<u8, u16> {
301        cache
302            .receive(
303                MailAddr(9),
304                CacheMessage::Put {
305                    key,
306                    value,
307                    reply_to: reply,
308                },
309            )
310            .unwrap()
311            .sends
312            .pop()
313            .unwrap()
314            .message
315    }
316
317    #[test]
318    fn zero_capacity_is_rejected_before_values_can_be_owned() {
319        assert!(matches!(
320            CacheConfiguration::new(0),
321            Err(CacheConfigError::ZeroCapacity)
322        ));
323    }
324
325    #[test]
326    fn hits_refresh_recency_and_capacity_returns_eviction() {
327        let reply = Recipient::from(MailAddr(8));
328        let mut cache = Cache::new(CacheConfiguration::new(2).unwrap())
329            .initialize()
330            .unwrap()
331            .behavior;
332        let stored = put(&mut cache, reply, 1, 10);
333        assert!(matches!(
334            stored,
335            CacheResult::Stored {
336                replaced: None,
337                evicted: None,
338                ..
339            }
340        ));
341        put(&mut cache, reply, 2, 20);
342        let hit = cache
343            .receive(
344                MailAddr(9),
345                CacheMessage::Get {
346                    key: 1,
347                    reply_to: reply,
348                },
349            )
350            .unwrap();
351        assert!(matches!(
352            hit.sends.as_slice(),
353            [delivery] if delivery.message == (CacheResult::Hit { key: 1, value: 10 })
354        ));
355        assert!(
356            cache
357                .state()
358                .entries()
359                .iter()
360                .map(|entry| entry.key)
361                .eq([2, 1])
362        );
363
364        let stored = put(&mut cache, reply, 3, 30);
365        assert_eq!(
366            stored,
367            CacheResult::Stored {
368                key: 3,
369                replaced: None,
370                evicted: Some(CacheEntry { key: 2, value: 20 }),
371            }
372        );
373        assert!(
374            cache
375                .state()
376                .entries()
377                .iter()
378                .map(|entry| entry.key)
379                .eq([1, 3])
380        );
381    }
382
383    #[test]
384    fn replacement_and_remove_return_every_displaced_value() {
385        let reply = Recipient::from(MailAddr(8));
386        let mut cache = Cache::new(CacheConfiguration::new(2).unwrap())
387            .initialize()
388            .unwrap()
389            .behavior;
390        put(&mut cache, reply, 1, 10);
391        let stored = put(&mut cache, reply, 1, 11);
392        assert_eq!(
393            stored,
394            CacheResult::Stored {
395                key: 1,
396                replaced: Some(10),
397                evicted: None,
398            }
399        );
400        let removed = cache
401            .receive(
402                MailAddr(9),
403                CacheMessage::Remove {
404                    key: 1,
405                    reply_to: reply,
406                },
407            )
408            .unwrap();
409        assert!(matches!(
410            removed.sends.as_slice(),
411            [delivery] if delivery.message == (CacheResult::Removed { key: 1, value: 11 })
412        ));
413        assert!(cache.state().is_empty());
414    }
415}
behavior_actors/persistence/cache.rs

behavior_actors/persistence/
cache.rs
