dyn_cache/
namespace.rs

1use super::{
2    cache_cell::CacheCell,
3    dep_node::{DepNode, Dependent},
4    Storage,
5};
6use hashbrown::{
7    hash_map::{DefaultHashBuilder, RawEntryMut},
8    HashMap,
9};
10
11use std::{
12    any::type_name,
13    borrow::Borrow,
14    fmt::{Debug, Formatter, Result as FmtResult},
15    hash::{BuildHasher, Hash, Hasher},
16    marker::PhantomData,
17};
18
19/// The result of failing to find a `key` in a cache with matching input. Passed
20/// back to [`Namespace::store`] to initialize a value in the cache.
21#[derive(Clone, Eq, Hash, Ord, PartialEq, PartialOrd)]
22pub struct KeyMiss<'k, K: ?Sized, I, H> {
23    inner: Result<Hashed<&'k K, H>, &'k K>,
24    dependent: Dependent,
25    node: Option<DepNode>,
26    input: I,
27}
28
29impl<'k, K: ?Sized, I, H> KeyMiss<'k, K, I, H> {
30    fn hashed(h: Hashed<&'k K, H>, input: I, node: Option<DepNode>, dependent: Dependent) -> Self {
31        Self { inner: Ok(h), node, dependent, input }
32    }
33
34    pub(crate) fn just_key(k: &'k K, input: I, dependent: Dependent, revision: u64) -> Self {
35        let node = DepNode::new(dependent, revision);
36        let dependent = node.as_dependent();
37        Self { inner: Err(k), dependent, node: Some(node), input }
38    }
39
40    pub(crate) fn init<R>(&self, op: impl FnOnce(&I) -> R) -> R {
41        self.dependent.clone().init_dependency(|| op(&self.input))
42    }
43}
44
45impl<'k, K, I, H> Debug for KeyMiss<'k, K, I, H>
46where
47    K: Debug + ?Sized,
48    I: Debug,
49{
50    fn fmt(&self, f: &mut Formatter) -> FmtResult {
51        f.debug_struct("KeyMiss")
52            .field("inner", &self.inner)
53            .field("dependent", &self.dependent)
54            .field("node", &self.node)
55            .field("input", &self.input)
56            .finish()
57    }
58}
59
60/// A query key that was hashed as part of an initial lookup and which can be
61/// used to store fresh values back to the cache.
62#[derive(Clone, Copy, Eq, Hash, Ord, PartialEq, PartialOrd)]
63struct Hashed<K, H> {
64    key: K,
65    hash: u64,
66    hasher: PhantomData<H>,
67}
68
69impl<K, H> Debug for Hashed<K, H>
70where
71    K: Debug,
72{
73    fn fmt(&self, f: &mut Formatter) -> FmtResult {
74        f.debug_struct("Hashed")
75            .field("key", &self.key)
76            .field("hash", &self.hash)
77            .field("hasher", &std::any::type_name::<H>())
78            .finish()
79    }
80}
81
82/// A namespace stores all cached values for a particular query type.
83#[derive(Clone)]
84pub(crate) struct Namespace<Scope, Input, Output, H = DefaultHashBuilder> {
85    inner: HashMap<Scope, CacheCell<Input, Output>, H>,
86}
87
88impl<Scope, Input, Output, H> Default for Namespace<Scope, Input, Output, H>
89where
90    H: Default,
91{
92    fn default() -> Self {
93        Self { inner: Default::default() }
94    }
95}
96
97impl<Scope, Input, Output, H> Namespace<Scope, Input, Output, H>
98where
99    Scope: Eq + Hash + 'static,
100    Input: 'static,
101    Output: 'static,
102    H: BuildHasher,
103{
104    fn hashed<'k, Key>(&self, key: &'k Key) -> Hashed<&'k Key, H>
105    where
106        Key: Hash + ?Sized,
107    {
108        let mut hasher = self.inner.hasher().build_hasher();
109        key.hash(&mut hasher);
110        Hashed { key, hash: hasher.finish(), hasher: PhantomData }
111    }
112
113    fn entry<'k, Key>(
114        &self,
115        hashed: &Hashed<&'k Key, H>,
116    ) -> Option<(&Scope, &CacheCell<Input, Output>)>
117    where
118        Key: Eq + ?Sized,
119        Scope: Borrow<Key>,
120    {
121        self.inner.raw_entry().from_hash(hashed.hash, |q| q.borrow().eq(hashed.key))
122    }
123
124    fn entry_mut<'k, Key>(
125        &mut self,
126        hashed: &Hashed<&'k Key, H>,
127    ) -> RawEntryMut<Scope, CacheCell<Input, Output>, H>
128    where
129        Key: Eq + ?Sized,
130        Scope: Borrow<Key>,
131    {
132        self.inner.raw_entry_mut().from_hash(hashed.hash, |q| q.borrow().eq(hashed.key))
133    }
134
135    pub fn get<'k, Key, Arg>(
136        &self,
137        key: &'k Key,
138        arg: &Arg,
139        dependent: Dependent,
140        revision: u64,
141    ) -> Result<&Output, KeyMiss<'k, Key, Input, H>>
142    where
143        Key: Eq + Hash + ?Sized,
144        Scope: Borrow<Key>,
145        Arg: PartialEq<Input> + ToOwned<Owned = Input> + ?Sized,
146        Input: Borrow<Arg>,
147    {
148        let hashed = self.hashed(key);
149        if let Some((_, cell)) = self.entry(&hashed) {
150            cell.get(arg, dependent).map_err(|d| KeyMiss::hashed(hashed, arg.to_owned(), None, d))
151        } else {
152            let node = DepNode::new(dependent, revision);
153            let new_dep = node.as_dependent();
154            Err(KeyMiss::hashed(hashed, arg.to_owned(), Some(node), new_dep))
155        }
156    }
157
158    pub fn store<Key>(&mut self, miss: KeyMiss<'_, Key, Input, H>, output: Output, revision: u64)
159    where
160        Key: Eq + Hash + ToOwned<Owned = Scope> + ?Sized,
161        Scope: Borrow<Key>,
162    {
163        let dependent = miss.dependent;
164        let hashed = miss.inner.unwrap_or_else(|k| self.hashed(k));
165        match self.entry_mut(&hashed) {
166            RawEntryMut::Occupied(occ) => {
167                assert!(miss.node.is_none(), "mustn't create nodes that aren't used");
168                occ.into_mut().store(miss.input, output, dependent, revision);
169            }
170            RawEntryMut::Vacant(vac) => {
171                vac.insert(
172                    hashed.key.to_owned(),
173                    CacheCell::new(
174                        miss.input,
175                        output,
176                        miss.node.expect("if no cell present, we must have created a fresh node"),
177                    ),
178                );
179            }
180        }
181    }
182}
183
184impl<Scope, Input, Output, H> Storage for Namespace<Scope, Input, Output, H>
185where
186    Scope: 'static,
187    Input: 'static,
188    Output: 'static,
189    H: 'static,
190{
191    fn mark(&mut self, revision: u64) {
192        self.inner.values_mut().for_each(|c| c.update_liveness(revision));
193    }
194
195    fn sweep(&mut self) {
196        self.inner.retain(|_, c| {
197            let keep = c.is_live();
198            c.mark_dead();
199            keep
200        });
201    }
202}
203
204impl<Scope, Input, Output, H> Debug for Namespace<Scope, Input, Output, H> {
205    // someday specialization might save us from these lame debug impls?
206    fn fmt(&self, f: &mut Formatter) -> FmtResult {
207        // TODO(#176) better debug output somehow?
208        f.debug_map()
209            .entry(&"scope", &type_name::<Scope>())
210            .entry(&"input", &type_name::<Input>())
211            .entry(&"output", &type_name::<Output>())
212            .finish()
213    }
214}
215
216#[cfg(test)]
217mod tests {
218    use super::*;
219
220    #[test]
221    fn namespace_debug_output() {
222        let ns: Namespace<u8, u8, u8> = Default::default();
223        let output = format!("{:?}", ns);
224        assert_eq!(output, "{\"scope\": \"u8\", \"input\": \"u8\", \"output\": \"u8\"}");
225    }
226}
dyn_cache/namespace.rs

dyn_cache/
namespace.rs
