sim_lib_class/
cache.rs

1//! Managed, revision-checked caches for derived class views.
2
3use std::{collections::BTreeMap, error::Error, fmt};
4
5use sim_lib_gc_tracing::{CollectionError, CollectionLimits, CollectionReceipt, collect};
6use sim_lib_mutation::{
7    ArenaError, EdgeId, EdgeVisitor, EphemeronMutationError, HardCappedRetainPolicy, ManagedArena,
8    ManagedHandle, ManagedId, ManagedNode, ManagedObject, RootedHandle, StrongEdgeMutationError,
9};
10
11use crate::{LineageBudget, LineageError, LineageGraph, LineagePolicy};
12
13/// Parent and member revisions observed for one class.
14#[derive(Clone, Copy, Debug, Eq, PartialEq)]
15pub struct CacheRevisions {
16    /// Revision of the declared-parent list.
17    pub parents: u64,
18    /// Revision of the declared-member list.
19    pub members: u64,
20}
21
22/// A cached class linearization and its root-first derived member view.
23#[derive(Clone, Debug, Eq, PartialEq)]
24pub struct DerivedClassView<M> {
25    /// The class followed by its ancestors in policy order.
26    pub linearization: Vec<ManagedId>,
27    /// Members concatenated in the same order as `linearization`.
28    pub members: Vec<M>,
29}
30
31/// Whether an access reused or recomputed a derived value.
32#[derive(Clone, Copy, Debug, Eq, PartialEq)]
33pub enum CacheAccessKind {
34    /// All lineage revision stamps still matched.
35    Hit,
36    /// No value existed, or at least one lineage revision changed.
37    Recomputed,
38}
39
40/// Inspectable evidence for one cache access.
41#[derive(Clone, Debug, Eq, PartialEq)]
42pub struct CacheAccess<M> {
43    /// Access disposition.
44    pub kind: CacheAccessKind,
45    /// The observed derived value.
46    pub view: DerivedClassView<M>,
47}
48
49/// A strong root for a managed class.
50#[derive(Clone, Copy, Debug, Eq, PartialEq)]
51pub struct ClassRoot(RootedHandle);
52
53impl ClassRoot {
54    /// Returns the managed class identity.
55    pub const fn id(self) -> ManagedId {
56        self.0.handle().id()
57    }
58}
59
60#[derive(Clone, Debug)]
61enum Object<M> {
62    Manager(ManagedNode<()>),
63    Class {
64        edges: ManagedNode<()>,
65        parents: Vec<ManagedHandle>,
66        members: Vec<M>,
67        revisions: CacheRevisions,
68        cached: Option<CachedRef>,
69    },
70    Derived {
71        edges: ManagedNode<()>,
72        stamps: Vec<(ManagedId, CacheRevisions)>,
73        view: DerivedClassView<M>,
74    },
75}
76
77#[derive(Clone, Copy, Debug)]
78struct CachedRef {
79    edge: EdgeId,
80    value: ManagedHandle,
81}
82
83impl<M> Object<M> {
84    fn edges(&self) -> &ManagedNode<()> {
85        match self {
86            Self::Manager(edges) | Self::Class { edges, .. } | Self::Derived { edges, .. } => edges,
87        }
88    }
89    fn edges_mut(&mut self) -> &mut ManagedNode<()> {
90        match self {
91            Self::Manager(edges) | Self::Class { edges, .. } | Self::Derived { edges, .. } => edges,
92        }
93    }
94}
95
96impl<M> ManagedObject for Object<M> {
97    fn trace_edges(&self, visitor: &mut dyn EdgeVisitor) {
98        self.edges().trace_edges(visitor);
99    }
100    fn clear_weak_edge(&mut self, edge: EdgeId, expected: ManagedId) -> bool {
101        self.edges_mut().clear_weak_edge(edge, expected)
102    }
103    fn clear_ephemeron_edge(&mut self, edge: EdgeId, key: ManagedId, value: ManagedId) -> bool {
104        self.edges_mut().clear_ephemeron_edge(edge, key, value)
105    }
106}
107
108/// Failure from checked class-cache mutation or computation.
109#[derive(Debug)]
110pub enum CacheError {
111    /// A managed-arena operation failed.
112    Arena(ArenaError),
113    /// A parent edge mutation failed.
114    Strong(StrongEdgeMutationError),
115    /// An ephemeron mutation failed.
116    Ephemeron(EphemeronMutationError),
117    /// The lineage policy rejected the graph.
118    Lineage(LineageError<ManagedId>),
119    /// Collection failed before completing atomically.
120    Collection(CollectionError),
121    /// A handle named a managed object of the wrong role.
122    WrongObject(ManagedId),
123    /// A revision counter exhausted its identity space.
124    RevisionExhausted(ManagedId),
125}
126
127impl fmt::Display for CacheError {
128    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
129        write!(f, "{self:?}")
130    }
131}
132impl Error for CacheError {}
133impl From<ArenaError> for CacheError {
134    fn from(value: ArenaError) -> Self {
135        Self::Arena(value)
136    }
137}
138impl From<StrongEdgeMutationError> for CacheError {
139    fn from(value: StrongEdgeMutationError) -> Self {
140        Self::Strong(value)
141    }
142}
143impl From<EphemeronMutationError> for CacheError {
144    fn from(value: EphemeronMutationError) -> Self {
145        Self::Ephemeron(value)
146    }
147}
148impl From<CollectionError> for CacheError {
149    fn from(value: CollectionError) -> Self {
150        Self::Collection(value)
151    }
152}
153
154/// A bounded managed class universe with non-retaining derived caches.
155pub struct ClassCache<M> {
156    arena: ManagedArena<Object<M>>,
157    manager: RootedHandle,
158}
159
160impl<M: Clone> ClassCache<M> {
161    /// Creates a cache with a hard cap shared by classes and derived values.
162    pub fn new(max_objects: usize) -> Result<Self, CacheError> {
163        let mut arena = ManagedArena::new(HardCappedRetainPolicy::new(max_objects)?);
164        let manager = arena.allocate(Object::Manager(ManagedNode::new(())))?;
165        let manager = arena.root(manager)?;
166        Ok(Self { arena, manager })
167    }
168
169    /// Allocates and roots a class with its declared parents and members.
170    pub fn allocate_class(
171        &mut self,
172        parents: &[ClassRoot],
173        members: Vec<M>,
174    ) -> Result<ClassRoot, CacheError> {
175        let mut edges = ManagedNode::new(());
176        let parent_handles = parents
177            .iter()
178            .map(|parent| parent.0.handle())
179            .collect::<Vec<_>>();
180        for parent in &parent_handles {
181            edges.insert_strong(parent.id())?;
182        }
183        let handle = self.arena.allocate(Object::Class {
184            edges,
185            parents: parent_handles,
186            members,
187            revisions: CacheRevisions {
188                parents: 0,
189                members: 0,
190            },
191            cached: None,
192        })?;
193        Ok(ClassRoot(self.arena.root(handle)?))
194    }
195
196    /// Replaces declared parents and bumps the parent revision.
197    pub fn replace_parents(
198        &mut self,
199        class: ClassRoot,
200        parents: &[ClassRoot],
201    ) -> Result<(), CacheError> {
202        self.discard_cached(class.0.handle())?;
203        let object = self.arena.get_mut(class.0.handle())?;
204        let Object::Class {
205            edges,
206            parents: stored,
207            revisions,
208            ..
209        } = object
210        else {
211            return Err(CacheError::WrongObject(class.id()));
212        };
213        *edges = ManagedNode::new(());
214        stored.clear();
215        for parent in parents {
216            edges.insert_strong(parent.id())?;
217            stored.push(parent.0.handle());
218        }
219        revisions.parents = revisions
220            .parents
221            .checked_add(1)
222            .ok_or(CacheError::RevisionExhausted(class.id()))?;
223        Ok(())
224    }
225
226    /// Replaces declared members and bumps the member revision.
227    pub fn replace_members(&mut self, class: ClassRoot, members: Vec<M>) -> Result<(), CacheError> {
228        self.discard_cached(class.0.handle())?;
229        let object = self.arena.get_mut(class.0.handle())?;
230        let Object::Class {
231            members: stored,
232            revisions,
233            ..
234        } = object
235        else {
236            return Err(CacheError::WrongObject(class.id()));
237        };
238        *stored = members;
239        revisions.members = revisions
240            .members
241            .checked_add(1)
242            .ok_or(CacheError::RevisionExhausted(class.id()))?;
243        Ok(())
244    }
245
246    /// Returns a revision-validated cached view or computes and installs one.
247    pub fn derived<P>(
248        &mut self,
249        class: ClassRoot,
250        policy: &P,
251        budget: LineageBudget,
252    ) -> Result<CacheAccess<M>, CacheError>
253    where
254        P: LineagePolicy<SnapshotGraph<M>>,
255    {
256        let graph = self.snapshot_graph()?;
257        if let Some(cached) = self.cached(class.0.handle())? {
258            let Object::Derived { stamps, view, .. } = self.arena.get(cached.value)? else {
259                return Err(CacheError::WrongObject(cached.value.id()));
260            };
261            if stamps
262                .iter()
263                .all(|(id, expected)| graph.revisions.get(id) == Some(expected))
264            {
265                return Ok(CacheAccess {
266                    kind: CacheAccessKind::Hit,
267                    view: view.clone(),
268                });
269            }
270        }
271        self.discard_cached(class.0.handle())?;
272        let linearization = policy
273            .linearize(&graph, &class.id(), budget)
274            .map_err(CacheError::Lineage)?;
275        let stamps = linearization
276            .iter()
277            .map(|id| (*id, graph.revisions[id]))
278            .collect::<Vec<_>>();
279        let members = linearization
280            .iter()
281            .flat_map(|id| graph.members[id].clone())
282            .collect();
283        let view = DerivedClassView {
284            linearization,
285            members,
286        };
287        let value = self.arena.allocate(Object::Derived {
288            edges: ManagedNode::new(()),
289            stamps,
290            view: view.clone(),
291        })?;
292        let edge = match self.arena.get_mut(self.manager.handle())? {
293            Object::Manager(edges) => edges.insert_ephemeron(class.id(), value.id())?,
294            _ => return Err(CacheError::WrongObject(self.manager.handle().id())),
295        };
296        let Object::Class { cached, .. } = self.arena.get_mut(class.0.handle())? else {
297            return Err(CacheError::WrongObject(class.id()));
298        };
299        *cached = Some(CachedRef { edge, value });
300        Ok(CacheAccess {
301            kind: CacheAccessKind::Recomputed,
302            view,
303        })
304    }
305
306    /// Releases the caller's strong root. Collection can then reclaim the class and cache value.
307    pub fn release(&mut self, class: ClassRoot) -> Result<(), CacheError> {
308        self.arena.release_root(class.0)?;
309        Ok(())
310    }
311
312    /// Runs bounded MANAGED_2 tracing collection and returns its exact receipt.
313    pub fn collect(&mut self, limits: CollectionLimits) -> Result<CollectionReceipt, CacheError> {
314        Ok(collect(&mut self.arena, limits)?)
315    }
316
317    /// Returns the current number of managed manager, class, and derived objects.
318    pub fn managed_len(&self) -> usize {
319        self.arena.len()
320    }
321
322    fn cached(&self, class: ManagedHandle) -> Result<Option<CachedRef>, CacheError> {
323        match self.arena.get(class)? {
324            Object::Class { cached, .. } => Ok(*cached),
325            _ => Err(CacheError::WrongObject(class.id())),
326        }
327    }
328
329    fn discard_cached(&mut self, class: ManagedHandle) -> Result<(), CacheError> {
330        let Some(cached) = self.cached(class)? else {
331            return Ok(());
332        };
333        match self.arena.get_mut(self.manager.handle())? {
334            Object::Manager(edges) => {
335                edges.remove_ephemeron(cached.edge, (class.id(), cached.value.id()))?;
336            }
337            _ => return Err(CacheError::WrongObject(self.manager.handle().id())),
338        }
339        self.arena.remove(cached.value)?;
340        let Object::Class { cached, .. } = self.arena.get_mut(class)? else {
341            return Err(CacheError::WrongObject(class.id()));
342        };
343        *cached = None;
344        Ok(())
345    }
346
347    fn snapshot_graph(&mut self) -> Result<SnapshotGraph<M>, CacheError> {
348        let mut graph = SnapshotGraph::default();
349        let (ids, _) = self
350            .arena
351            .safepoint(|snapshot| snapshot.objects().collect::<Vec<_>>())?;
352        for id in ids {
353            let handle = self.arena.handle(id)?;
354            if let Object::Class {
355                parents,
356                members,
357                revisions,
358                ..
359            } = self.arena.get(handle)?
360            {
361                graph
362                    .parents
363                    .insert(id, parents.iter().map(|parent| parent.id()).collect());
364                graph.members.insert(id, members.clone());
365                graph.revisions.insert(id, *revisions);
366            }
367        }
368        Ok(graph)
369    }
370}
371
372/// Immutable computation snapshot; public only as the policy trait's graph parameter.
373pub struct SnapshotGraph<M = ()> {
374    parents: BTreeMap<ManagedId, Vec<ManagedId>>,
375    members: BTreeMap<ManagedId, Vec<M>>,
376    revisions: BTreeMap<ManagedId, CacheRevisions>,
377}
378impl<M> Default for SnapshotGraph<M> {
379    fn default() -> Self {
380        Self {
381            parents: BTreeMap::new(),
382            members: BTreeMap::new(),
383            revisions: BTreeMap::new(),
384        }
385    }
386}
387impl<M> LineageGraph for SnapshotGraph<M> {
388    type Node = ManagedId;
389    fn declared_parents(&self, node: &ManagedId) -> Vec<ManagedId> {
390        self.parents.get(node).cloned().unwrap_or_default()
391    }
392}
393
394#[cfg(test)]
395mod tests {
396    use super::*;
397    use crate::C3Policy;
398
399    fn budget() -> LineageBudget {
400        LineageBudget {
401            nodes: 32,
402            work: 512,
403        }
404    }
405    fn limits() -> CollectionLimits {
406        CollectionLimits {
407            objects: 32,
408            edges: 32,
409            stack: 32,
410            work: 512,
411            clears: 32,
412            finalizers: 0,
413        }
414    }
415
416    #[test]
417    fn hit_matches_recomputation_and_lineage_revisions_invalidate_descendants() {
418        let mut cache = ClassCache::new(16).unwrap();
419        let parent = cache.allocate_class(&[], vec!["parent-v1"]).unwrap();
420        let child = cache.allocate_class(&[parent], vec!["child"]).unwrap();
421
422        let first = cache.derived(child, &C3Policy, budget()).unwrap();
423        let hit = cache.derived(child, &C3Policy, budget()).unwrap();
424        assert_eq!(first.kind, CacheAccessKind::Recomputed);
425        assert_eq!(hit.kind, CacheAccessKind::Hit);
426        assert_eq!(hit.view, first.view);
427
428        cache.replace_members(parent, vec!["parent-v2"]).unwrap();
429        let recomputed = cache.derived(child, &C3Policy, budget()).unwrap();
430        assert_eq!(recomputed.kind, CacheAccessKind::Recomputed);
431        assert_eq!(recomputed.view.linearization, first.view.linearization);
432        assert_eq!(recomputed.view.members, ["child", "parent-v2"]);
433
434        cache.replace_parents(child, &[]).unwrap();
435        let without_parent = cache.derived(child, &C3Policy, budget()).unwrap();
436        assert_eq!(without_parent.kind, CacheAccessKind::Recomputed);
437        assert_eq!(without_parent.view.linearization, [child.id()]);
438        assert_eq!(without_parent.view.members, ["child"]);
439    }
440
441    #[test]
442    fn dropping_last_class_roots_clears_ephemeron_and_reclaims_cached_value() {
443        let mut cache = ClassCache::new(16).unwrap();
444        let parent = cache.allocate_class(&[], vec!["parent"]).unwrap();
445        let child = cache.allocate_class(&[parent], vec!["child"]).unwrap();
446        cache.derived(child, &C3Policy, budget()).unwrap();
447        assert_eq!(cache.managed_len(), 4);
448
449        cache.release(parent).unwrap();
450        cache.release(child).unwrap();
451        let receipt = cache.collect(limits()).unwrap();
452        assert_eq!(receipt.cleared_ephemerons.len(), 1);
453        assert_eq!(receipt.swept.len(), 3);
454        assert_eq!(cache.managed_len(), 1);
455    }
456}
sim_lib_class/cache.rs

sim_lib_class/
cache.rs
