ratio-metadata 0.2.2

//! # Value interner module
//!
//! ## License
//!
//! This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0.
//! If a copy of the MPL was not distributed with this file,
//! You can obtain one at <https://mozilla.org/MPL/2.0/>.
//!
//! **Code examples both in the docstrings and rendered documentation are free to use.**

use std::borrow::Cow;
use std::collections::BTreeMap;
use std::fmt::Debug;

use slotmap::{DenseSlotMap, Key};
use snafu::prelude::*;

/// Interner error.
#[derive(Clone, Debug, Snafu)]
#[snafu(visibility(pub))]
pub enum Error {
    /// Value already exists under a different key.
    ValueAlreadyExists,
    /// Key is no longer valid.
    InvalidKey,
    /// Value does not exist in this interner.
    ValueDoesNotExist,
}

/// Interner trait that interns values and returns keys for them.
/// - K: Key type.
/// - V: Value type.
pub trait Interner<K: Copy + Debug, V: Clone + Debug> {
    /// Intern (a reference to) a value. Returns the corresponding key.
    fn intern(&mut self, value: Cow<'_, V>) -> K;

    /// Try to intern a new value and raise an error if it already exists.
    fn try_intern(&mut self, value: Cow<'_, V>) -> Result<K, Error>;

    /// Intern an owned value.
    fn intern_owned(&mut self, value: V) -> K {
        self.intern(Cow::Owned(value))
    }

    /// Intern a borrowed value.
    fn intern_borrowed(&mut self, value: &V) -> K {
        self.intern(Cow::Borrowed(value))
    }

    /// Remove a key and return the removed value if it existed.
    fn remove_key(&mut self, key: K) -> Option<V>;

    /// Try to remove an entry by key.
    fn try_remove_key(&mut self, key: K) -> Result<V, Error> {
        match self.remove_key(key) {
            Some(value) => Ok(value),
            None => InvalidKeySnafu.fail(),
        }
    }

    /// Try to update the value for an existing key and raise a value if the value already exists
    /// for another key.
    fn try_update(&mut self, key: K, value: Cow<'_, V>) -> Result<V, Error>;

    /// Remove a value and returns the corresponding key if it existed.
    fn remove_value(&mut self, value: &V) -> Option<K>;

    /// Try to remove an entry by value and return the corresponding key if it existed.
    fn try_remove_value(&mut self, value: &V) -> Result<K, Error> {
        self.remove_value(value).context(ValueDoesNotExistSnafu)
    }

    /// Clear all entries in this map.
    fn clear(&mut self);

    /// The number of items interned.
    fn len(&self) -> usize;

    /// Whether the interner is empty.
    fn is_empty(&self) -> bool;

    /// Check whether the interner has some key.
    fn contains_key(&self, key: K) -> bool;

    /// Check whether the interner has some value.
    fn contains_value(&self, value: &V) -> bool;

    /// Get the key corresponding to a value.
    fn get_key(&self, value: &V) -> Option<K>;

    /// Try to get the key corresponding to a value and raise an error if the value isn't interned.
    fn try_get_key(&self, value: &V) -> Result<K, Error> {
        self.get_key(value).context(ValueDoesNotExistSnafu)
    }

    /// Get an interned value using its key.
    fn get_value(&self, key: K) -> Option<&V>;

    /// Try to get an interned value or throw an error.
    fn try_get_value(&self, key: K) -> Result<&V, Error> {
        self.get_value(key).context(InvalidKeySnafu)
    }

    /// Iterator over all keys.
    fn keys(&self) -> impl Iterator<Item = K>;

    /// Iterator over all values.
    fn values<'a>(&'a self) -> impl Iterator<Item = &'a V>
    where
        V: 'a;

    /// Iterator over all key-value pairs in this interner.
    fn items<'a>(&'a self) -> impl Iterator<Item = (K, &'a V)>
    where
        V: 'a;
}

/// Value interner based on a DenseSlotMap and a BTreeMap.
#[derive(Clone, Debug, bon::Builder)]
#[cfg_attr(
    feature = "serde",
    derive(serde::Serialize, serde::Deserialize),
    serde(default, rename_all = "camelCase")
)]
#[cfg_attr(feature = "reactive", derive(reactive_stores::Store))]
pub struct DenseSlottedBTreeInterner<K, V>
where
    K: Key + Debug,
    V: Clone + Debug + Ord,
{
    /// Orderable names by slot keys.
    values_by_key: DenseSlotMap<K, V>,

    /// Slotmap keys by orderable values.
    keys_by_value: BTreeMap<V, K>,
}

impl<K, V> Default for DenseSlottedBTreeInterner<K, V>
where
    K: Key + Debug,
    V: Clone + Debug + Ord,
{
    fn default() -> Self {
        Self {
            values_by_key: Default::default(),
            keys_by_value: Default::default(),
        }
    }
}

impl<K, V> DenseSlottedBTreeInterner<K, V>
where
    K: Key + Debug,
    V: Clone + Debug + Ord,
{
    /// Create a new interner.
    pub fn new() -> Self {
        Self::default()
    }
}

impl<K, V> Interner<K, V> for DenseSlottedBTreeInterner<K, V>
where
    K: Key + Debug,
    V: Clone + Debug + Ord,
{
    fn intern(&mut self, value: Cow<'_, V>) -> K {
        if let Some(key) = self.keys_by_value.get(&value) {
            *key
        } else {
            let value = value.into_owned();
            let key = self.values_by_key.insert(value.clone());
            self.keys_by_value.insert(value, key);
            key
        }
    }

    fn try_intern(&mut self, value: Cow<'_, V>) -> Result<K, Error> {
        if self.contains_value(&value) {
            ValueAlreadyExistsSnafu.fail()
        } else {
            let value = value.into_owned();
            let key = self.values_by_key.insert(value.clone());
            self.keys_by_value.insert(value, key);
            Ok(key)
        }
    }

    fn try_update(&mut self, key: K, value: Cow<'_, V>) -> Result<V, Error> {
        if self.contains_value(&value) {
            ValueAlreadyExistsSnafu.fail()
        } else {
            let value = value.into_owned();
            let old = self
                .values_by_key
                .get_mut(key)
                .map(|v| std::mem::replace(v, value.clone()))
                .context(InvalidKeySnafu)?;
            self.keys_by_value.remove(&old);
            self.keys_by_value.insert(value, key);
            Ok(old)
        }
    }

    fn remove_key(&mut self, key: K) -> Option<V> {
        let value = self.values_by_key.remove(key);
        if let Some(value) = value.as_ref() {
            self.keys_by_value.remove(value);
        }
        value
    }

    fn remove_value(&mut self, value: &V) -> Option<K> {
        let key = self.keys_by_value.remove(value);
        if let Some(key) = key {
            self.values_by_key.remove(key);
        }
        key
    }

    fn clear(&mut self) {
        self.keys_by_value.clear();
        self.values_by_key.clear();
    }

    fn len(&self) -> usize {
        self.keys_by_value.len()
    }

    fn is_empty(&self) -> bool {
        self.keys_by_value.is_empty()
    }

    fn contains_key(&self, key: K) -> bool {
        self.values_by_key.contains_key(key)
    }

    fn contains_value(&self, value: &V) -> bool {
        self.keys_by_value.contains_key(value)
    }

    fn get_key(&self, value: &V) -> Option<K> {
        self.keys_by_value.get(value).copied()
    }

    fn get_value(&self, key: K) -> Option<&V> {
        self.values_by_key.get(key)
    }

    fn keys(&self) -> impl Iterator<Item = K> {
        self.values_by_key.keys()
    }

    fn values<'a>(&'a self) -> impl Iterator<Item = &'a V>
    where
        V: 'a,
    {
        self.keys_by_value.keys()
    }

    fn items<'a>(&'a self) -> impl Iterator<Item = (K, &'a V)>
    where
        V: 'a,
    {
        self.keys_by_value.iter().map(|(v, &k)| (k, v))
    }
}

#[cfg(test)]
mod tests {
    #[allow(unused_imports)]
    use pretty_assertions::{assert_eq, assert_ne, assert_str_eq};
    use slotmap::DefaultKey;

    #[allow(unused_imports)]
    use super::*;

    #[test]
    fn test_dense_slotted_btree_interner() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test interning owned values
        let key1 = interner.intern_owned("foo".to_string());
        let key2 = interner.intern_owned("bar".to_string());
        assert_ne!(key1, key2);

        // Test interning borrowed values
        let key3 = interner.intern_borrowed(&"foo".to_string());
        let key4 = interner.intern_borrowed(&"bar".to_string());
        assert_eq!(key3, key1);
        assert_eq!(key4, key2);

        // Test that the interner only stores unique values
        assert_eq!(interner.len(), 2);

        // Test value ordering from btreemap.
        assert_eq!(interner.values().collect::<Vec<_>>(), vec!["bar", "foo"]);
    }

    #[test]
    fn test_dense_slotted_btree_interner_try_intern() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test successful try_intern
        let key1 = interner.try_intern(Cow::Owned("foo".to_string())).unwrap();
        assert_eq!(interner.len(), 1);

        // Test try_intern with existing value
        let result = interner.try_intern(Cow::Owned("foo".to_string()));
        assert!(matches!(result, Err(Error::ValueAlreadyExists)));
        assert_eq!(interner.len(), 1);

        // Test try_intern with borrowed value
        let key2 = interner
            .try_intern(Cow::Borrowed(&"bar".to_string()))
            .unwrap();
        assert_eq!(interner.len(), 2);
        assert_ne!(key1, key2);
    }

    #[test]
    fn test_dense_slotted_btree_interner_try_update() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test try_update with non-existent key
        let result = interner.try_update(DefaultKey::null(), Cow::Owned("foo".to_string()));
        assert!(matches!(result, Err(Error::InvalidKey)));

        // Test successful try_update
        let key1 = interner.intern_owned("foo".to_string());
        let old_value = interner
            .try_update(key1, Cow::Owned("bar".to_string()))
            .unwrap();
        assert_eq!(old_value, "foo");
        assert_eq!(interner.get_value(key1), Some(&"bar".to_string()));

        // Test try_update with existing value
        let key2 = interner.intern_owned("baz".to_string());
        let result = interner.try_update(key2, Cow::Owned("baz".to_string()));
        assert!(matches!(result, Err(Error::ValueAlreadyExists)));
        assert_eq!(interner.get_value(key2), Some(&"baz".to_string()));
    }

    #[test]
    fn test_dense_slotted_btree_interner_remove() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test remove_key with non-existent key
        assert_eq!(interner.remove_key(DefaultKey::null()), None);

        // Test remove_key with existing key
        let key1 = interner.intern_owned("foo".to_string());
        assert_eq!(interner.remove_key(key1), Some("foo".to_string()));
        assert_eq!(interner.len(), 0);

        // Test remove_value with non-existent value
        assert_eq!(interner.remove_value(&"bar".to_string()), None);

        // Test remove_value with existing value
        let key2 = interner.intern_owned("bar".to_string());
        assert_eq!(interner.remove_value(&"bar".to_string()), Some(key2));
        assert_eq!(interner.len(), 0);
    }

    #[test]
    fn test_dense_slotted_btree_interner_try_remove() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test try_remove_key with non-existent key
        let result = interner.try_remove_key(DefaultKey::null());
        assert!(matches!(result, Err(Error::InvalidKey)));

        // Test try_remove_key with existing key
        let key1 = interner.intern_owned("foo".to_string());
        assert_eq!(interner.try_remove_key(key1).unwrap(), "foo".to_string());
        assert_eq!(interner.len(), 0);

        // Test try_remove_value with non-existent value
        let result = interner.try_remove_value(&"bar".to_string());
        assert!(matches!(result, Err(Error::ValueDoesNotExist)));

        // Test try_remove_value with existing value
        let key2 = interner.intern_owned("bar".to_string());
        assert_eq!(interner.try_remove_value(&"bar".to_string()).unwrap(), key2);
        assert_eq!(interner.len(), 0);
    }

    #[test]
    fn test_dense_slotted_btree_interner_try_get() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test try_get_key with non-existent value
        let result = interner.try_get_key(&"foo".to_string());
        assert!(matches!(result, Err(Error::ValueDoesNotExist)));

        // Test try_get_key with existing value
        let key1 = interner.intern_owned("foo".to_string());
        assert_eq!(interner.try_get_key(&"foo".to_string()).unwrap(), key1);

        // Test try_get_value with non-existent key
        let result = interner.try_get_value(DefaultKey::null());
        assert!(matches!(result, Err(Error::InvalidKey)));

        // Test try_get_value with existing key
        assert_eq!(interner.try_get_value(key1).unwrap(), &"foo".to_string());
    }

    #[test]
    fn test_dense_slotted_btree_interner_clear() {
        let mut interner = DenseSlottedBTreeInterner::<DefaultKey, String>::default();

        // Test clear on empty interner
        interner.clear();
        assert_eq!(interner.len(), 0);

        // Test clear on non-empty interner
        interner.intern_owned("foo".to_string());
        interner.intern_owned("bar".to_string());
        assert_eq!(interner.len(), 2);
        interner.clear();
        assert_eq!(interner.len(), 0);
    }
}