delta_struct/entry.rs
1//! Keyed membership diffing, behind the `unordered` field type when the field
2//! is a map.
3//!
4//! A map is a bag of entries, but a bag with a rule that the plain
5//! [`bag`](crate::bag) knows nothing about: no two entries share a key. That
6//! rule is what makes an [`EntryDelta`] the right shape for one — a bare key
7//! is enough to say an entry left, and a value is enough to say what a key
8//! holds now, because putting one back cannot leave the old one standing
9//! beside it.
10//!
11//! Values are compared with `==` and replaced wholesale, which is the whole of
12//! what separates this from [`map`](crate::map): reach for `unordered-delta`
13//! and a [`MapDelta`](crate::MapDelta) when the values are big enough to be
14//! worth diffing and implement [`Delta`](crate::Delta) so they can be.
15//!
16//! The derive emits calls to [`diff`] and [`apply`]; you only need this module
17//! directly to inspect or construct a delta by hand.
18
19use crate::{MapEntry, TryIndex};
20
21/// A membership diff between two collections of key/value entries.
22///
23/// The two parts are asymmetric, and the map's one-value-per-key rule is what
24/// makes them so: [`add`] carries whole entries because the receiver needs to
25/// be told the value, while [`remove`] carries bare keys because a key names
26/// an entry on its own.
27///
28/// A key that survived with a new value under it is an [`add`], not a removal
29/// followed by one. Applying an addition overwrites whatever the key held, so
30/// the removal would say nothing the addition does not already say.
31///
32/// Nothing here records position — see [`SeqDelta`](crate::SeqDelta) for that.
33///
34/// [`add`]: EntryDelta::add
35/// [`remove`]: EntryDelta::remove
36#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
37#[derive(Clone, Debug, PartialEq, Eq)]
38pub struct EntryDelta<K, V> {
39 /// What a key holds in the new collection that it did not hold in the old
40 /// one — both keys that arrived and keys whose value moved.
41 pub add: Vec<(K, V)>,
42 /// Keys that were in the old collection but are not in the new one.
43 pub remove: Vec<K>,
44}
45
46impl<K, V> EntryDelta<K, V> {
47 /// Whether the two collections held the same entries, and so nothing needs
48 /// sending.
49 pub fn is_empty(&self) -> bool {
50 self.add.is_empty() && self.remove.is_empty()
51 }
52}
53
54impl<K, V> Default for EntryDelta<K, V> {
55 fn default() -> Self {
56 EntryDelta {
57 add: Vec::new(),
58 remove: Vec::new(),
59 }
60 }
61}
62
63/// Pairs the entries of `old` and `new` by key and records what the keys that
64/// survived hold now.
65///
66/// Returns an empty [`EntryDelta`] when the two hold the same entries. Each
67/// key of `old` is looked up in `new` exactly once, through the collection's
68/// own [`TryIndex`] implementation, so the cost is that of n lookups: O(n) for
69/// a [`HashMap`](std::collections::HashMap), O(n log n) for a
70/// [`BTreeMap`](std::collections::BTreeMap).
71///
72/// ```
73/// use delta_struct::entry::diff;
74/// use std::collections::BTreeMap;
75///
76/// let labels = |tier: &'static str| {
77/// vec![("tier", tier)].into_iter().collect::<BTreeMap<&str, &str>>()
78/// };
79///
80/// let delta = diff(labels("web"), labels("edge"));
81/// // The key survived, so only what it holds now travels — the old value
82/// // stays where it is, on the receiver.
83/// assert_eq!(delta.add, vec![("tier", "edge")]);
84/// assert!(delta.remove.is_empty());
85/// ```
86pub fn diff<C, E>(old: C, mut new: C) -> EntryDelta<E::Key, E::Value>
87where
88 C: IntoIterator<Item = E> + TryIndex<E::Key, Output = E::Value>,
89 E: MapEntry,
90 E::Value: PartialEq,
91{
92 // Take each of `old`'s entries out of `new` as it is matched, so whatever
93 // is still standing at the end is exactly the keys that arrived — and can
94 // join the changed ones in `add`, since applying either means the same
95 // thing to the receiver.
96 let mut add = Vec::new();
97 let mut remove = Vec::new();
98 for entry in old {
99 let (key, old_value) = entry.into_parts();
100 match new.try_remove(&key) {
101 Some(new_value) => {
102 if new_value != old_value {
103 add.push((key, new_value));
104 }
105 }
106 None => remove.push(key),
107 }
108 }
109 add.extend(new.into_iter().map(MapEntry::into_parts));
110 EntryDelta { add, remove }
111}
112
113/// Applies a keyed membership diff to `target` in place.
114///
115/// Each removal is a single lookup rather than a scan, so this costs the same
116/// as [`diff`] does. Membership is preserved but position is not — additions
117/// land wherever the collection decides to put them. Use `ordered` where that
118/// matters.
119///
120/// A removal naming a key that `target` does not have is ignored, and an
121/// addition overwrites whatever the key held, which together make applying the
122/// same delta twice harmless.
123///
124/// ```
125/// use delta_struct::entry::{apply, diff};
126/// use std::collections::BTreeMap;
127///
128/// let labels = |entries: Vec<(&'static str, &'static str)>| {
129/// entries.into_iter().collect::<BTreeMap<&str, &str>>()
130/// };
131///
132/// let delta = diff(
133/// labels(vec![("tier", "web"), ("zone", "a")]),
134/// labels(vec![("tier", "edge")]),
135/// );
136/// let mut target = labels(vec![("tier", "web"), ("zone", "a")]);
137/// apply(&mut target, delta);
138/// assert_eq!(target, labels(vec![("tier", "edge")]));
139/// ```
140pub fn apply<C, E>(target: &mut C, delta: EntryDelta<E::Key, E::Value>)
141where
142 C: IntoIterator<Item = E> + Extend<E> + TryIndex<E::Key, Output = E::Value>,
143 E: MapEntry,
144{
145 for key in delta.remove {
146 target.try_remove(&key);
147 }
148 target.extend(
149 delta
150 .add
151 .into_iter()
152 .map(|(key, value)| E::from_parts(key, value)),
153 );
154}