rain_lang/graph/
cons.rs

1/*!
2Hash-consing and associated utilities
3*/
4use dashmap::{DashMap, mapref::entry::Entry};
5use ahash::AHasher;
6use std::hash::{Hash, Hasher, BuildHasherDefault};
7use std::convert::Infallible;
8use either::Either;
9use super::node::{WeakNode, Node, Data};
10use crate::util::PassThroughHasher;
11use crate::value::{ValueDesc, ValueData, ValId};
12
13/// A node cache type
14pub trait CacheType<T> {
15    /// The underlying map type for a given node cache type
16    type UnderlyingMap;
17}
18
19/// A global node cache
20#[derive(Debug, Copy, Clone, Eq, PartialEq)]
21pub struct GlobalCache;
22
23impl<T> CacheType<T> for GlobalCache {
24    type UnderlyingMap = DashMap<u64, WeakNode<T>, BuildHasherDefault<PassThroughHasher>>;
25}
26
27/// A node cache
28#[derive(Debug, Clone)]
29pub struct NodeCache<T, C: CacheType<T> = GlobalCache> {
30    /// The underlying map of this
31    pub map: C::UnderlyingMap,
32    /// The keys of this node cache, for constructing `AHasher` instances
33    pub keys: (u64, u64)
34}
35
36/// An entry in a node cache
37pub type CacheEntry<'a, T> =
38    Entry<'a, u64, WeakNode<T>, BuildHasherDefault<PassThroughHasher>>;
39
40/// An object which can accept a cache entry pointer
41pub trait CacheAcceptor<T> {
42    /// Accept a cache entry pointer
43    fn accept(self, weak: WeakNode<T>);
44}
45
46impl<'a, T> CacheAcceptor<T> for CacheEntry<'a, T> {
47    fn accept(self, weak: WeakNode<T>) {
48        *(self.or_default()) = weak;
49    }
50}
51
52impl<T> CacheAcceptor<T> for () {
53    fn accept(self, _weak: WeakNode<T>) {}
54}
55
56impl<T> NodeCache<T, GlobalCache> {
57    /// Create a new, empty node cache with the given keys
58    pub fn with_keys(keys: (u64, u64)) -> NodeCache<T> {
59        NodeCache { map: DashMap::default(), keys }
60    }
61    /// Create a new, empty node cache
62    pub fn new() -> NodeCache<T> { Self::with_keys((0, 0)) }
63    /// Get either the cached value for a key (if it exists), or the entry for the key
64    /// (if it does not). Note that this locks the bucket for the key up until the handle
65    /// for the entry is destroyed, so be careful!
66    pub fn cached_entry<'a, K>(&'a self, key: &K) -> Either<Node<T>, CacheEntry<'a, T>>
67    where K: Hash {
68        let hash = {
69            let mut hasher = AHasher::new_with_keys(self.keys.0, self.keys.1);
70            key.hash(&mut hasher);
71            hasher.finish()
72        };
73        let entry = self.map.entry(hash);
74        if let Entry::Occupied(occupied) = &entry {
75            if let Some(node) = occupied.get().upgrade() {
76                return Either::Left(node)
77            }
78        }
79        Either::Right(entry)
80    }
81    /// Try to get the node cached for a given key, with a given node creation function.
82    /// If the node has been collected or otherwise does not exist,
83    /// try to create a new one and cache it. If this fails, return an error.
84    pub fn cached_constructor<D, E, F>(&self, data: D, constructor: F) -> Result<Node<T>, E>
85    where D: Hash, F: FnOnce(D) -> Result<Node<T>, E> {
86        let entry = match self.cached_entry(&data) {
87            Either::Left(node) => return Ok(node),
88            Either::Right(entry) => entry
89        };
90        let node = constructor(data)?;
91        *(entry.or_default()) = node.downgrade();
92        Ok(node)
93    }
94    /// Remove a given cached value
95    pub fn remove<K>(&self, key: &K) -> Option<(u64, WeakNode<T>)> where K: Hash {
96        let mut hasher = AHasher::new_with_keys(self.keys.0, self.keys.1);
97        key.hash(&mut hasher);
98        let cache_key = hasher.finish();
99        self.map.remove(&cache_key)
100    }
101    /// Try to get the node cached for a given descriptor.
102    /// If the node has been collected or otherwise does not exist,
103    /// try to create a new one and cache it. If this fails, return an error.
104    #[inline(always)] pub fn cached_desc<D>(&self, desc: D) -> Result<Node<T>, T::CacheError>
105    where D: Hash, T: CacheBy<D> {
106        self.cached_constructor(desc, T::node_to_cache)
107    }
108}
109
110/// A node data-type which can be cached by a given key type
111pub trait CacheBy<K: Hash> {
112    /// Potential error when trying to cache a key type
113    type CacheError;
114    /// Try to get the node to cache for a given key
115    fn node_to_cache(key: K) -> Result<Node<Self>, Self::CacheError>;
116}
117
118impl<V> CacheBy<V> for ValueData where V: ValueDesc + Hash {
119    type CacheError = V::Err;
120    #[inline(always)] fn node_to_cache(key: V) -> Result<ValId, V::Err> { key.to_node() }
121}
122
123impl<T: Hash> CacheBy<Data<T>> for Data<T> {
124    type CacheError = Infallible;
125    #[inline(always)] fn node_to_cache(key: Data<T>) -> Result<Node<Data<T>>, Infallible> {
126        Ok(Node::new(key))
127    }
128}
129
130#[cfg(test)]
131mod tests {
132    use crate::util::AlwaysOk;
133    use super::*;
134
135    #[test]
136    fn bools_cache_properly() {
137        let cache = NodeCache::<Data<bool>>::new();
138        let dt = Data(true);
139        let df = Data(false);
140        let nt = cache.cached_desc(dt).aok();
141        let pass = cache.cached_constructor(Data(true), |_| Err(()))
142            .expect("Valid key, should not generate");
143        assert_eq!(nt, pass);
144        cache.cached_constructor(Data(false), |_| Err(()))
145            .expect_err("Invalid key, generator always errors");
146        let nf = cache.cached_desc(df).aok();
147        let pass = cache.cached_constructor(Data(false), |_| Err(()))
148            .expect("Valid key, should not generate");
149        assert_eq!(nf, pass);
150        let nt2 = cache.cached_desc(dt).aok();
151        let nf2 = cache.cached_desc(df).aok();
152        assert_eq!(nt, nt2);
153        assert_eq!(nf, nf2);
154        assert_ne!(nt, nf);
155        let mnt = Node::new(dt);
156        let mnf = Node::new(df);
157        assert_ne!(nt, mnt);
158        assert_ne!(nf, mnt);
159        assert_ne!(nt, mnf);
160        assert_ne!(nf, mnf);
161        let (_hash, ntr) = cache.remove(&dt).expect("Data(true) was previously inserted");
162        assert_eq!(ntr.upgrade().expect("We hold a reference to Data(true)"), nt);
163        let nt3 = cache.cached_desc(dt).expect("Valid key");
164        let nf3 = cache.cached_desc(df).expect("Valid key");
165        assert_ne!(nt, nt3);
166        assert_eq!(nf, nf3);
167    }
168}
rain_lang/graph/cons.rs

rain_lang/graph/
cons.rs
