iddqd/id_hash_map/

daft_impls.rs

//! `Diffable` implementation.

use super::{IdHashItem, IdHashMap};
use crate::{
    DefaultHashBuilder,
    support::{
        alloc::{Allocator, Global},
        daft_utils::IdLeaf,
    },
};
use core::{
    fmt,
    hash::{BuildHasher, Hash},
};
use daft::Diffable;
use equivalent::Equivalent;

impl<T: IdHashItem, S: Clone + BuildHasher, A: Clone + Allocator> Diffable
    for IdHashMap<T, S, A>
{
    type Diff<'a>
        = Diff<'a, T, S, A>
    where
        T: 'a,
        S: 'a,
        A: 'a;

    fn diff<'daft>(&'daft self, other: &'daft Self) -> Self::Diff<'daft> {
        let mut diff = Diff::with_hasher_in(
            self.hasher().clone(),
            self.allocator().clone(),
        );
        for item in self {
            if let Some(other_item) = other.get(&item.key()) {
                diff.common.insert_overwrite(IdLeaf::new(item, other_item));
            } else {
                diff.removed.insert_overwrite(item);
            }
        }
        for item in other {
            if !self.contains_key(&item.key()) {
                diff.added.insert_overwrite(item);
            }
        }
        diff
    }
}

/// A diff of two [`IdHashMap`]s.
///
/// Generated by the [`Diffable`] implementation for [`IdHashMap`].
///
/// # Examples
///
/// ```
/// # #[cfg(feature = "default-hasher")] {
/// use daft::Diffable;
/// use iddqd::{IdHashItem, IdHashMap, id_upcast};
///
/// #[derive(Eq, PartialEq)]
/// struct Item {
///     id: String,
///     value: u32,
/// }
///
/// impl IdHashItem for Item {
///     type Key<'a> = &'a str;
///     fn key(&self) -> Self::Key<'_> {
///         &self.id
///     }
///     id_upcast!();
/// }
///
/// // Create two IdHashMaps with overlapping items.
/// let mut map1 = IdHashMap::new();
/// map1.insert_unique(Item { id: "a".to_string(), value: 1 });
/// map1.insert_unique(Item { id: "b".to_string(), value: 2 });
///
/// let mut map2 = IdHashMap::new();
/// map2.insert_unique(Item { id: "b".to_string(), value: 3 });
/// map2.insert_unique(Item { id: "c".to_string(), value: 4 });
///
/// // Compute the diff between the two maps.
/// let diff = map1.diff(&map2);
///
/// // "a" is removed.
/// assert!(diff.removed.contains_key("a"));
/// // "b" is modified (value changed from 2 to 3).
/// assert!(diff.is_modified("b"));
/// // "c" is added.
/// assert!(diff.added.contains_key("c"));
/// # }
/// ```
///
/// [`Diffable`]: daft::Diffable
pub struct Diff<
    'daft,
    T: ?Sized + IdHashItem,
    S = DefaultHashBuilder,
    A: Allocator = Global,
> {
    /// Entries common to both maps.
    ///
    /// Items are stored as [`IdLeaf`]s to references.
    pub common: IdHashMap<IdLeaf<&'daft T>, S, A>,

    /// Added entries.
    pub added: IdHashMap<&'daft T, S, A>,

    /// Removed entries.
    pub removed: IdHashMap<&'daft T, S, A>,
}

impl<'a, 'daft, T, S: Clone + BuildHasher, A: Allocator> fmt::Debug
    for Diff<'daft, T, S, A>
where
    T: ?Sized + IdHashItem + fmt::Debug,
    T::Key<'a>: fmt::Debug,
    T: 'a,
    'daft: 'a,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Diff")
            .field("common", &self.common)
            .field("added", &self.added)
            .field("removed", &self.removed)
            .finish()
    }
}

impl<'daft, T: ?Sized + IdHashItem, S: Default, A: Allocator + Default> Default
    for Diff<'daft, T, S, A>
{
    fn default() -> Self {
        Self {
            common: IdHashMap::default(),
            added: IdHashMap::default(),
            removed: IdHashMap::default(),
        }
    }
}

#[cfg(all(feature = "default-hasher", feature = "allocator-api2"))]
impl<'daft, T: ?Sized + IdHashItem> Diff<'daft, T> {
    /// Creates a new, empty `Diff`.
    pub fn new() -> Self {
        Self {
            common: IdHashMap::new(),
            added: IdHashMap::new(),
            removed: IdHashMap::new(),
        }
    }
}

#[cfg(feature = "allocator-api2")]
impl<'daft, T: ?Sized + IdHashItem, S: Clone + BuildHasher> Diff<'daft, T, S> {
    /// Creates a new, empty `Diff` with the given hasher.
    pub fn with_hasher(hasher: S) -> Self {
        Self {
            common: IdHashMap::with_hasher(hasher.clone()),
            added: IdHashMap::with_hasher(hasher.clone()),
            removed: IdHashMap::with_hasher(hasher),
        }
    }
}

impl<
    'daft,
    T: ?Sized + IdHashItem,
    S: Clone + BuildHasher,
    A: Clone + Allocator,
> Diff<'daft, T, S, A>
{
    /// Creates a new, empty `Diff` with the given hasher and allocator.
    pub fn with_hasher_in(hasher: S, alloc: A) -> Self {
        Self {
            common: IdHashMap::with_hasher_in(hasher.clone(), alloc.clone()),
            added: IdHashMap::with_hasher_in(hasher.clone(), alloc.clone()),
            removed: IdHashMap::with_hasher_in(hasher, alloc),
        }
    }
}

impl<'daft, T: ?Sized + IdHashItem + Eq, S: Clone + BuildHasher, A: Allocator>
    Diff<'daft, T, S, A>
{
    /// Returns an iterator over unchanged keys and values.
    pub fn unchanged(&self) -> impl Iterator<Item = &'daft T> + '_ {
        self.common
            .iter()
            .filter_map(|leaf| leaf.is_unchanged().then_some(*leaf.before()))
    }

    /// Returns true if the item corresponding to the key is unchanged.
    pub fn is_unchanged<'a, Q>(&'a self, key: &Q) -> bool
    where
        Q: ?Sized + Hash + Equivalent<T::Key<'a>>,
    {
        self.common.get(key).is_some_and(|leaf| leaf.is_unchanged())
    }

    /// Returns the value associated with the key if it is unchanged,
    /// otherwise `None`.
    pub fn get_unchanged<'a, Q>(&'a self, key: &Q) -> Option<&'daft T>
    where
        Q: ?Sized + Hash + Equivalent<T::Key<'a>>,
    {
        self.common
            .get(key)
            .and_then(|leaf| leaf.is_unchanged().then_some(*leaf.before()))
    }

    /// Returns an iterator over modified keys and values.
    pub fn modified(&self) -> impl Iterator<Item = IdLeaf<&'daft T>> + '_ {
        self.common
            .iter()
            .filter_map(|leaf| leaf.is_modified().then_some(*leaf))
    }

    /// Returns true if the value corresponding to the key is
    /// modified.
    pub fn is_modified<'a, Q>(&'a self, key: &Q) -> bool
    where
        Q: ?Sized + Hash + Equivalent<T::Key<'a>>,
    {
        self.common.get(key).is_some_and(|leaf| leaf.is_modified())
    }

    /// Returns the [`IdLeaf`] associated with the key if it is modified,
    /// otherwise `None`.
    pub fn get_modified<'a, Q>(&'a self, key: &Q) -> Option<IdLeaf<&'daft T>>
    where
        Q: ?Sized + Hash + Equivalent<T::Key<'a>>,
    {
        self.common
            .get(key)
            .and_then(|leaf| leaf.is_modified().then_some(*leaf))
    }

    /// Returns an iterator over modified keys and values, performing
    /// a diff on the values.
    ///
    /// This is useful when `T::Diff` is a complex type, not just a
    /// [`daft::Leaf`].
    pub fn modified_diff(&self) -> impl Iterator<Item = T::Diff<'daft>> + '_
    where
        T: Diffable,
    {
        self.modified().map(|leaf| leaf.diff_pair())
    }
}

impl<T: IdHashItem> IdHashItem for IdLeaf<T> {
    type Key<'a>
        = T::Key<'a>
    where
        T: 'a;

    fn key(&self) -> Self::Key<'_> {
        let before_key = self.before().key();
        if before_key != self.after().key() {
            panic!("key is different between before and after");
        }
        before_key
    }

    #[inline]
    fn upcast_key<'short, 'long: 'short>(
        long: Self::Key<'long>,
    ) -> Self::Key<'short> {
        T::upcast_key(long)
    }
}