ratio_metadata/
interner.rs

1//! # Value interner module
2//!
3//! ## License
4//!
5//! This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0.
6//! If a copy of the MPL was not distributed with this file,
7//! You can obtain one at <https://mozilla.org/MPL/2.0/>.
8//!
9//! **Code examples both in the docstrings and rendered documentation are free to use.**
10
11use std::borrow::Cow;
12use std::collections::BTreeMap;
13use std::fmt::Debug;
14
15use slotmap::{DenseSlotMap, Key};
16use snafu::prelude::*;
17
18/// Interner error.
19#[derive(Clone, Debug, Snafu)]
20#[snafu(visibility(pub))]
21pub enum Error {
22    /// Value already exists under a different key.
23    ValueAlreadyExists,
24    /// Key is no longer valid.
25    InvalidKey,
26    /// Value does not exist in this interner.
27    ValueDoesNotExist,
28}
29
30/// Interner trait that interns values and returns keys for them.
31/// - K: Key type.
32/// - V: Value type.
33pub trait Interner<K: Copy + Debug, V: Clone + Debug> {
34    /// Intern (a reference to) a value. Returns the corresponding key.
35    fn intern(&mut self, value: Cow<'_, V>) -> K;
36
37    /// Try to intern a new value and raise an error if it already exists.
38    fn try_intern(&mut self, value: Cow<'_, V>) -> Result<K, Error>;
39
40    /// Intern an owned value.
41    fn intern_owned(&mut self, value: V) -> K {
42        self.intern(Cow::Owned(value))
43    }
44
45    /// Intern a borrowed value.
46    fn intern_borrowed(&mut self, value: &V) -> K {
47        self.intern(Cow::Borrowed(value))
48    }
49
50    /// Remove a key and return the removed value if it existed.
51    fn remove_key(&mut self, key: K) -> Option<V>;
52
53    /// Try to remove an entry by key.
54    fn try_remove_key(&mut self, key: K) -> Result<V, Error> {
55        match self.remove_key(key) {
56            Some(value) => Ok(value),
57            None => InvalidKeySnafu.fail(),
58        }
59    }
60
61    /// Try to update the value for an existing key and raise a value if the value already exists
62    /// for another key.
63    fn try_update(&mut self, key: K, value: Cow<'_, V>) -> Result<V, Error>;
64
65    /// Remove a value and returns the corresponding key if it existed.
66    fn remove_value(&mut self, value: &V) -> Option<K>;
67
68    /// Try to remove an entry by value and return the corresponding key if it existed.
69    fn try_remove_value(&mut self, value: &V) -> Result<K, Error> {
70        self.remove_value(value).context(ValueDoesNotExistSnafu)
71    }
72
73    /// Clear all entries in this map.
74    fn clear(&mut self);
75
76    /// The number of items interned.
77    fn len(&self) -> usize;
78
79    /// Whether the interner is empty.
80    fn is_empty(&self) -> bool;
81
82    /// Check whether the interner has some key.
83    fn contains_key(&self, key: K) -> bool;
84
85    /// Check whether the interner has some value.
86    fn contains_value(&self, value: &V) -> bool;
87
88    /// Get the key corresponding to a value.
89    fn get_key(&self, value: &V) -> Option<K>;
90
91    /// Try to get the key corresponding to a value and raise an error if the value isn't interned.
92    fn try_get_key(&self, value: &V) -> Result<K, Error> {
93        self.get_key(value).context(ValueDoesNotExistSnafu)
94    }
95
96    /// Get an interned value using its key.
97    fn get_value(&self, key: K) -> Option<&V>;
98
99    /// Try to get an interned value or throw an error.
100    fn try_get_value(&self, key: K) -> Result<&V, Error> {
101        self.get_value(key).context(InvalidKeySnafu)
102    }
103
104    /// Iterator over all keys.
105    fn keys(&self) -> impl Iterator<Item = K>;
106
107    /// Iterator over all values.
108    fn values<'a>(&'a self) -> impl Iterator<Item = &'a V>
109    where
110        V: 'a;
111
112    /// Iterator over all key-value pairs in this interner.
113    fn items<'a>(&'a self) -> impl Iterator<Item = (K, &'a V)>
114    where
115        V: 'a;
116}
117
118/// Value interner based on a DenseSlotMap and a BTreeMap.
119#[derive(Clone, Debug, bon::Builder)]
120#[cfg_attr(
121    feature = "serde",
122    derive(serde::Serialize, serde::Deserialize),
123    serde(default, rename_all = "camelCase")
124)]
125#[cfg_attr(feature = "reactive", derive(reactive_stores::Store))]
126pub struct DenseSlottedBTreeInterner<K, V>
127where
128    K: Key + Debug,
129    V: Clone + Debug + Ord,
130{
131    /// Orderable names by slot keys.
132    values_by_key: DenseSlotMap<K, V>,
133
134    /// Slotmap keys by orderable values.
135    keys_by_value: BTreeMap<V, K>,
136}
137
138impl<K, V> Default for DenseSlottedBTreeInterner<K, V>
139where
140    K: Key + Debug,
141    V: Clone + Debug + Ord,
142{
143    fn default() -> Self {
144        Self {
145            values_by_key: Default::default(),
146            keys_by_value: Default::default(),
147        }
148    }
149}
150
151impl<K, V> DenseSlottedBTreeInterner<K, V>
152where
153    K: Key + Debug,
154    V: Clone + Debug + Ord,
155{
156    /// Create a new interner.
157    pub fn new() -> Self {
158        Self::default()
159    }
160}
161
162impl<K, V> Interner<K, V> for DenseSlottedBTreeInterner<K, V>
163where
164    K: Key + Debug,
165    V: Clone + Debug + Ord,
166{
167    fn intern(&mut self, value: Cow<'_, V>) -> K {
168        if let Some(key) = self.keys_by_value.get(&value) {
169            *key
170        } else {
171            let value = value.into_owned();
172            let key = self.values_by_key.insert(value.clone());
173            self.keys_by_value.insert(value, key);
174            key
175        }
176    }
177
178    fn try_intern(&mut self, value: Cow<'_, V>) -> Result<K, Error> {
179        if self.contains_value(&value) {
180            ValueAlreadyExistsSnafu.fail()
181        } else {
182            let value = value.into_owned();
183            let key = self.values_by_key.insert(value.clone());
184            self.keys_by_value.insert(value, key);
185            Ok(key)
186        }
187    }
188
189    fn try_update(&mut self, key: K, value: Cow<'_, V>) -> Result<V, Error> {
190        if self.contains_value(&value) {
191            ValueAlreadyExistsSnafu.fail()
192        } else {
193            let value = value.into_owned();
194            let old = self
195                .values_by_key
196                .get_mut(key)
197                .map(|v| std::mem::replace(v, value.clone()))
198                .context(InvalidKeySnafu)?;
199            self.keys_by_value.remove(&old);
200            self.keys_by_value.insert(value, key);
201            Ok(old)
202        }
203    }
204
205    fn remove_key(&mut self, key: K) -> Option<V> {
206        let value = self.values_by_key.remove(key);
207        if let Some(value) = value.as_ref() {
208            self.keys_by_value.remove(value);
209        }
210        value
211    }
212
213    fn remove_value(&mut self, value: &V) -> Option<K> {
214        let key = self.keys_by_value.remove(value);
215        if let Some(key) = key {
216            self.values_by_key.remove(key);
217        }
218        key
219    }
220
221    fn clear(&mut self) {
222        self.keys_by_value.clear();
223        self.values_by_key.clear();
224    }
225
226    fn len(&self) -> usize {
227        self.keys_by_value.len()
228    }
229
230    fn is_empty(&self) -> bool {
231        self.keys_by_value.is_empty()
232    }
233
234    fn contains_key(&self, key: K) -> bool {
235        self.values_by_key.contains_key(key)
236    }
237
238    fn contains_value(&self, value: &V) -> bool {
239        self.keys_by_value.contains_key(value)
240    }
241
242    fn get_key(&self, value: &V) -> Option<K> {
243        self.keys_by_value.get(value).copied()
244    }
245
246    fn get_value(&self, key: K) -> Option<&V> {
247        self.values_by_key.get(key)
248    }
249
250    fn keys(&self) -> impl Iterator<Item = K> {
251        self.values_by_key.keys()
252    }
253
254    fn values<'a>(&'a self) -> impl Iterator<Item = &'a V>
255    where
256        V: 'a,
257    {
258        self.keys_by_value.keys()
259    }
260
261    fn items<'a>(&'a self) -> impl Iterator<Item = (K, &'a V)>
262    where
263        V: 'a,
264    {
265        self.keys_by_value.iter().map(|(v, &k)| (k, v))
266    }
267}
268
269#[cfg(test)]
270mod tests {
271    #[allow(unused_imports)]
272    use pretty_assertions::{assert_eq, assert_ne, assert_str_eq};
273    use slotmap::DefaultKey;
274
275    #[allow(unused_imports)]
276    use super::*;
277
278    #[test]
279    fn test_dense_slotted_btree_interner() {
280        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();
281
282        // Test interning owned values
283        let key1 = interner.intern_owned("foo".to_string());
284        let key2 = interner.intern_owned("bar".to_string());
285        assert_ne!(key1, key2);
286
287        // Test interning borrowed values
288        let key3 = interner.intern_borrowed(&"foo".to_string());
289        let key4 = interner.intern_borrowed(&"bar".to_string());
290        assert_eq!(key3, key1);
291        assert_eq!(key4, key2);
292
293        // Test that the interner only stores unique values
294        assert_eq!(interner.len(), 2);
295
296        // Test value ordering from btreemap.
297        assert_eq!(interner.values().collect::<Vec<_>>(), vec!["bar", "foo"]);
298    }
299
300    #[test]
301    fn test_dense_slotted_btree_interner_try_intern() {
302        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();
303
304        // Test successful try_intern
305        let key1 = interner.try_intern(Cow::Owned("foo".to_string())).unwrap();
306        assert_eq!(interner.len(), 1);
307
308        // Test try_intern with existing value
309        let result = interner.try_intern(Cow::Owned("foo".to_string()));
310        assert!(matches!(result, Err(Error::ValueAlreadyExists)));
311        assert_eq!(interner.len(), 1);
312
313        // Test try_intern with borrowed value
314        let key2 = interner
315            .try_intern(Cow::Borrowed(&"bar".to_string()))
316            .unwrap();
317        assert_eq!(interner.len(), 2);
318        assert_ne!(key1, key2);
319    }
320
321    #[test]
322    fn test_dense_slotted_btree_interner_try_update() {
323        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();
324
325        // Test try_update with non-existent key
326        let result = interner.try_update(DefaultKey::null(), Cow::Owned("foo".to_string()));
327        assert!(matches!(result, Err(Error::InvalidKey)));
328
329        // Test successful try_update
330        let key1 = interner.intern_owned("foo".to_string());
331        let old_value = interner
332            .try_update(key1, Cow::Owned("bar".to_string()))
333            .unwrap();
334        assert_eq!(old_value, "foo");
335        assert_eq!(interner.get_value(key1), Some(&"bar".to_string()));
336
337        // Test try_update with existing value
338        let key2 = interner.intern_owned("baz".to_string());
339        let result = interner.try_update(key2, Cow::Owned("baz".to_string()));
340        assert!(matches!(result, Err(Error::ValueAlreadyExists)));
341        assert_eq!(interner.get_value(key2), Some(&"baz".to_string()));
342    }
343
344    #[test]
345    fn test_dense_slotted_btree_interner_remove() {
346        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();
347
348        // Test remove_key with non-existent key
349        assert_eq!(interner.remove_key(DefaultKey::null()), None);
350
351        // Test remove_key with existing key
352        let key1 = interner.intern_owned("foo".to_string());
353        assert_eq!(interner.remove_key(key1), Some("foo".to_string()));
354        assert_eq!(interner.len(), 0);
355
356        // Test remove_value with non-existent value
357        assert_eq!(interner.remove_value(&"bar".to_string()), None);
358
359        // Test remove_value with existing value
360        let key2 = interner.intern_owned("bar".to_string());
361        assert_eq!(interner.remove_value(&"bar".to_string()), Some(key2));
362        assert_eq!(interner.len(), 0);
363    }
364
365    #[test]
366    fn test_dense_slotted_btree_interner_try_remove() {
367        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();
368
369        // Test try_remove_key with non-existent key
370        let result = interner.try_remove_key(DefaultKey::null());
371        assert!(matches!(result, Err(Error::InvalidKey)));
372
373        // Test try_remove_key with existing key
374        let key1 = interner.intern_owned("foo".to_string());
375        assert_eq!(interner.try_remove_key(key1).unwrap(), "foo".to_string());
376        assert_eq!(interner.len(), 0);
377
378        // Test try_remove_value with non-existent value
379        let result = interner.try_remove_value(&"bar".to_string());
380        assert!(matches!(result, Err(Error::ValueDoesNotExist)));
381
382        // Test try_remove_value with existing value
383        let key2 = interner.intern_owned("bar".to_string());
384        assert_eq!(interner.try_remove_value(&"bar".to_string()).unwrap(), key2);
385        assert_eq!(interner.len(), 0);
386    }
387
388    #[test]
389    fn test_dense_slotted_btree_interner_try_get() {
390        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();
391
392        // Test try_get_key with non-existent value
393        let result = interner.try_get_key(&"foo".to_string());
394        assert!(matches!(result, Err(Error::ValueDoesNotExist)));
395
396        // Test try_get_key with existing value
397        let key1 = interner.intern_owned("foo".to_string());
398        assert_eq!(interner.try_get_key(&"foo".to_string()).unwrap(), key1);
399
400        // Test try_get_value with non-existent key
401        let result = interner.try_get_value(DefaultKey::null());
402        assert!(matches!(result, Err(Error::InvalidKey)));
403
404        // Test try_get_value with existing key
405        assert_eq!(interner.try_get_value(key1).unwrap(), &"foo".to_string());
406    }
407
408    #[test]
409    fn test_dense_slotted_btree_interner_clear() {
410        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();
411
412        // Test clear on empty interner
413        interner.clear();
414        assert_eq!(interner.len(), 0);
415
416        // Test clear on non-empty interner
417        interner.intern_owned("foo".to_string());
418        interner.intern_owned("bar".to_string());
419        assert_eq!(interner.len(), 2);
420        interner.clear();
421        assert_eq!(interner.len(), 0);
422    }
423}
ratio_metadata/interner.rs

ratio_metadata/
interner.rs
