#[derive(Clone)]
pub struct Dict<K, V, Seq> {
live: std::collections::HashMap<K, Value<V, Seq>>,
removed: std::collections::HashMap<Seq, Seq>,
}
pub struct DictDiff<K, V: crate::Mergable, Seq> {
updates: Vec<Update<K, V, Seq>>,
}
impl<
K,
V: crate::Mergable,
SF: crate::SequenceFactory,
> crate::Diff
for DictDiff<K, V, crate::Sequence<SF>> {
fn is_empty(&self) -> bool {
self.updates.is_empty()
}
fn revert(mut self) -> Result<Self, crate::RevertError> {
crate::map_in_place(&mut self.updates, |update| Ok(match update {
Update::Del(_what, Some((k, v)), when) => Update::Up(when.undo()?, k, UpdateValue::New(v)),
Update::Del(what, None, when) => Update::Del(what, None, when),
Update::Up(what, k, v) => match v {
UpdateValue::New(v) => {
Update::Del(what.clone(), Some((k, v)), what.undo()?)
}
UpdateValue::Diff(diff) => {
Update::Up(what, k, UpdateValue::Diff(crate::Diff::revert(diff)?))
},
}
}))?;
Ok(self)
}
}
impl<
K: Clone,
V: crate::Mergable + Clone,
Seq: Clone,
>
Clone for DictDiff<K, V, Seq>
where
V::Diff: Clone,
{
fn clone(&self) -> Self {
DictDiff {
updates: self.updates.clone(),
}
}
}
impl<
K: std::fmt::Debug,
V: crate::Mergable + std::fmt::Debug,
Seq: std::fmt::Debug
>
std::fmt::Debug for DictDiff<K, V, Seq>
where V::Diff: std::fmt::Debug
{
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "DictDiff(")?;
self.updates.fmt(f)?;
write!(f, ")")
}
}
#[derive(Clone,Debug)]
enum UpdateValue<N, D> {
New(N),
Diff(D),
}
#[derive(Clone,Debug)]
enum Update<K, V: crate::Mergable, Seq> {
Del(
Seq,
Option<(K, V)>,
Seq,
),
Up(
Seq,
K,
UpdateValue<V, V::Diff>,
),
}
impl<
K: Clone + Eq + std::hash::Hash,
V: crate::Mergable,
SF: crate::SequenceFactory,
>
Dict<K, V, crate::Sequence<SF>>
{
pub fn entry(&mut self, key: K) -> DictEntry<K, V, SF> {
match self.live.entry(key) {
std::collections::hash_map::Entry::Occupied(entry) => {
DictEntry::Occupied(DictOccupiedEntry {
entry,
removed: &mut self.removed,
})
}
std::collections::hash_map::Entry::Vacant(entry) => {
DictEntry::Vacant(DictVacantEntry {
entry,
})
}
}
}
pub fn get<
Q: std::hash::Hash + Eq>
(&self, k: &Q) -> Option<&V>
where K: std::borrow::Borrow<Q>
{
self.live.get(k).map(|v| &v.value)
}
pub fn get_mut<
Q: std::hash::Hash + Eq>
(&mut self, k: &Q) -> Option<&mut V>
where K: std::borrow::Borrow<Q>
{
self.live.get_mut(k).map(|v| &mut v.value)
}
pub fn insert(&mut self, ctx: &mut crate::Context<SF>, k: K, v: V) {
self.entry(k).insert(ctx, v);
}
pub fn remove<Q: ?Sized>(&mut self, ctx: &mut crate::Context<SF>, k: K) -> Option<V>
where
K: std::borrow::Borrow<Q>,
Q: std::hash::Hash + Eq
{
if let DictEntry::Occupied(entry) = self.entry(k) {
Some(entry.remove(ctx))
} else {
None
}
}
pub fn len(&self) -> usize {
self.live.len()
}
pub fn is_empty(&self) -> bool {
self.live.is_empty()
}
pub fn iter(&self) -> DictIter<K, V, crate::Sequence<SF>> {
return DictIter(self.live.iter());
}
fn apply(&mut self,
updates: impl IntoIterator<Item=Update<K, V, crate::Sequence<SF>>>,
) -> Result<(), crate::ApplyError> {
let mut unpurged_removals = std::collections::HashSet::new();
for update in updates {
match update {
Update::Del(what, value, when) => {
let removed_entry = match self.removed.entry(what) {
std::collections::hash_map::Entry::Occupied(mut entry) => {
if entry.get() < &when {
entry.insert(when.clone());
}
continue
}
std::collections::hash_map::Entry::Vacant(entry) => entry,
};
if let Some((k, _)) = value {
if let std::collections::hash_map::Entry::Occupied(entry) = self.live.entry(k) {
if entry.get().sequence == *removed_entry.key() {
eprintln!("remove");
entry.remove();
}
}
} else {
unpurged_removals.insert(removed_entry.key().clone());
}
removed_entry.insert(when.clone());
}
Update::Up(what, k, value) => {
match self.live.entry(k) {
std::collections::hash_map::Entry::Occupied(mut entry) => {
let slot = entry.get_mut();
if what > slot.sequence {
slot.sequence = what;
}
match value {
UpdateValue::Diff(d) => slot.value.apply(d)?,
UpdateValue::New(v) => slot.value.merge(v),
}
}
std::collections::hash_map::Entry::Vacant(entry) => {
if self.removed.contains_key(&what) {
continue
}
let UpdateValue::New(value) = value else {
return Err(crate::ApplyError::Missing(
"Target doesn't contain base value for diff.".into()))
};
entry.insert(Value{
sequence: what,
value,
});
}
}
}
}
}
if !unpurged_removals.is_empty() {
self.live.retain(|_, v| !unpurged_removals.contains(&v.sequence))
}
Ok(())
}
}
impl<
K: Clone + Eq + std::hash::Hash,
V: Clone + crate::Mergable<Seq=crate::Sequence<SF>>,
SF: crate::SequenceFactory,
>
crate::Mergable for Dict<K, V, crate::Sequence<SF>>
{
type Diff = DictDiff<K, V, crate::Sequence<SF>>;
type Seq = crate::Sequence<SF>;
fn merge(&mut self, that: Self) {
let removed = that.removed.into_iter()
.map(|(what, when)| Update::Del(what, None, when));
let live = that.live.into_iter()
.map(|(k, Value{sequence, value})| Update::Up(sequence, k, UpdateValue::New(value)));
self.apply(removed.chain(live)).unwrap()
}
fn diff(&self, that: &Self) -> Self::Diff {
let mut updates = Vec::<Update<K, V, crate::Sequence<SF>>>::new();
let mut deleted_seq = std::collections::HashMap::new();
for (what, when) in &self.removed {
if that.removed.get(what) >= Some(when) { continue }
let i = updates.len();
updates.push(Update::Del(what.clone(), None, when.clone()));
deleted_seq.insert(what, i);
}
if !deleted_seq.is_empty() {
for (k, v) in &that.live {
let Some(i) = deleted_seq.get(&v.sequence) else { continue };
let Update::Del(_, ref mut kv, _) = updates[*i] else { unreachable!() };
*kv = Some((k.clone(), v.value.clone()));
}
}
for (k, v) in &self.live {
if that.removed.contains_key(&v.sequence) { continue }
updates.push(
Update::Up(
v.sequence.clone(),
k.clone(),
match that.get(k) {
Some(known) => {
let diff = v.value.diff(known);
if crate::Diff::is_empty(&diff) { continue }
UpdateValue::Diff(diff)
}
None => UpdateValue::New(v.value.clone()),
}));
}
DictDiff { updates }
}
fn apply(&mut self, diff: Self::Diff) -> Result<(), crate::ApplyError> {
self.apply(diff.updates)
}
fn clean(&mut self, cutoff: &Self::Seq) {
for entry in self.live.values_mut() {
entry.value.clean(cutoff);
}
self.removed.retain(|_, seq| *seq >= *cutoff);
}
}
impl<
K,
V,
SF,
>
Default for Dict<K, V, SF>
{
fn default() -> Self {
Dict {
live: Default::default(),
removed: Default::default(),
}
}
}
impl<K: Eq + std::hash::Hash, V: PartialEq, Seq> PartialEq for Dict<K, V, Seq> {
fn eq(&self, that: &Self) -> bool {
self.live == that.live
}
}
impl<K: std::fmt::Debug, V: std::fmt::Debug, Seq> std::fmt::Debug for Dict<K, V, Seq> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
self.live.fmt(f)
}
}
#[derive(Clone)]
struct Value<V, Seq> {
sequence: Seq,
value: V,
}
impl<V: PartialEq, Seq> PartialEq for Value<V, Seq> {
fn eq(&self, that: &Self) -> bool {
self.value == that.value
}
}
impl<V: std::fmt::Debug, Seq> std::fmt::Debug for Value<V, Seq> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
self.value.fmt(f)
}
}
pub enum DictEntry<'a, K: 'a, V: 'a, SF: crate::SequenceFactory> {
Occupied(DictOccupiedEntry<'a, K, V, SF>),
Vacant(DictVacantEntry<'a, K, V, SF>),
}
impl<'a,
K: 'a + Eq + std::hash::Hash,
V: 'a + crate::Mergable,
SF: crate::SequenceFactory
>
DictEntry<'a, K, V, SF>
{
pub fn insert(self, ctx: &'a mut crate::Context<SF>, v: V) -> &'a mut V {
match self {
DictEntry::Occupied(mut entry) => {
entry.insert(ctx, v);
entry.into_mut()
}
DictEntry::Vacant(entry) => entry.insert(ctx, v),
}
}
pub fn or_insert(self, ctx: &'a mut crate::Context<SF>, v: V) -> &'a mut V {
match self {
DictEntry::Occupied(mut entry) => {
entry.insert(ctx, v);
entry.into_mut()
}
DictEntry::Vacant(entry) => entry.insert(ctx, v),
}
}
}
pub struct DictOccupiedEntry<'a, K: 'a, V: 'a, SF: crate::SequenceFactory> {
entry: std::collections::hash_map::OccupiedEntry<'a, K, Value<V, crate::Sequence<SF>>>,
removed: &'a mut std::collections::HashMap<crate::Sequence<SF>, crate::Sequence<SF>>,
}
impl<'a,
K: 'a + Eq + std::hash::Hash,
V: 'a + crate::Mergable,
SF: crate::SequenceFactory
>
DictOccupiedEntry<'a, K, V, SF>
{
pub fn into_mut(self) -> &'a mut V {
&mut self.entry.into_mut().value
}
pub fn insert(&mut self, ctx: &'a mut crate::Context<SF>, v: V) {
self.entry.get_mut().sequence = ctx.next_sequence();
self.entry.get_mut().value.merge(v);
}
pub fn remove(self, ctx: &'a mut crate::Context<SF>) -> V {
let (_, Value{sequence, value}) = self.entry.remove_entry();
self.removed.insert(sequence, ctx.next_sequence());
value
}
}
pub struct DictVacantEntry<'a, K: 'a, V: 'a, SF: crate::SequenceFactory> {
entry: std::collections::hash_map::VacantEntry<'a, K, Value<V, crate::Sequence<SF>>>,
}
impl<'a, K: 'a, V: 'a, SF: crate::SequenceFactory> DictVacantEntry<'a, K, V, SF> {
pub fn insert(self, ctx: &'a mut crate::Context<SF>, value: V) -> &'a mut V {
&mut self.entry.insert(
Value {
sequence: ctx.next_sequence(),
value,
})
.value
}
}
pub struct DictIter<'a, K, V, Seq>(std::collections::hash_map::Iter<'a, K, Value<V, Seq>>);
impl<'a, K, V, Seq> Iterator for DictIter<'a, K, V, Seq> {
type Item = (&'a K, &'a V);
fn next(&mut self) -> Option<Self::Item> {
self.0.next()
.map(|item| (item.0, &item.1.value))
}
}
impl<
'a,
K: Clone + Eq + std::hash::Hash,
V: crate::Mergable,
SF: crate::SequenceFactory,
> IntoIterator for &'a Dict<K, V, crate::Sequence<SF>> {
type IntoIter = DictIter<'a, K, V, crate::Sequence<SF>>;
type Item = (&'a K, &'a V);
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
pub struct DictIntoIter<K, V, Seq>(std::collections::hash_map::IntoIter<K, Value<V, Seq>>);
impl<K, V, Seq> Iterator for DictIntoIter<K, V, Seq> {
type Item = (K, V);
fn next(&mut self) -> Option<Self::Item> {
self.0.next()
.map(|item| (item.0, item.1.value))
}
}
impl<
K: Clone + Eq + std::hash::Hash,
V: crate::Mergable,
SF: crate::SequenceFactory,
> IntoIterator for Dict<K, V, crate::Sequence<SF>> {
type IntoIter = DictIntoIter<K, V, crate::Sequence<SF>>;
type Item = (K, V);
fn into_iter(self) -> Self::IntoIter {
DictIntoIter(self.live.into_iter())
}
}
#[test]
fn test_dict() {
let mut ctx = crate::Context::default();
let one = crate::Cell::new(&mut ctx, "one");
let two = crate::Cell::new(&mut ctx, "two");
let result = crate::test::test_merge(&mut [&one, &two]);
assert_eq!(*result, "two");
let mut parent_l = Dict::default();
parent_l.insert(&mut ctx, 0, two.clone());
let mut parent_r = Dict::default();
parent_r.insert(&mut ctx, 0, one.clone());
let merged = crate::test::test_merge(&mut [&parent_l, &parent_r]);
assert_eq!(merged, parent_l);
let mut child_l = merged.clone();
child_l.insert(&mut ctx, 1, one.clone());
let mut child_r = merged;
child_r.insert(&mut ctx, 2, two.clone());
let merged = crate::test::test_merge(&mut [&parent_l, &parent_r, &child_l, &child_r]);
let mut expected = Dict::default();
expected.insert(&mut ctx, 0, two.clone());
expected.insert(&mut ctx, 1, one.clone());
expected.insert(&mut ctx, 2, two.clone());
assert_eq!(merged, expected);
}
#[test]
fn test_dict_remove_old() {
let mut ctx = crate::Context::default();
let one = crate::Cell::new(&mut ctx, "one");
let two = crate::Cell::new(&mut ctx, "two");
let mut parent_l = Dict::default();
parent_l.insert(&mut ctx, 0, two.clone());
let mut parent_r = Dict::default();
parent_r.insert(&mut ctx, 0, one.clone());
parent_l.remove(&mut ctx, 0);
let merged = crate::test::test_merge(&mut [&parent_l, &parent_r]);
assert_eq!(merged, parent_r);
}
#[test]
fn test_dict_remove_new() {
let mut ctx = crate::Context::default();
let one = crate::Cell::new(&mut ctx, "one");
let two = crate::Cell::new(&mut ctx, "two");
let mut parent_l = Dict::default();
parent_l.insert(&mut ctx, 0, two.clone());
let mut parent_r = Dict::default();
parent_r.insert(&mut ctx, 0, one.clone());
parent_r.remove(&mut ctx, 0);
let merged = crate::test::test_merge(&mut [&parent_l, &parent_r]);
assert_eq!(merged, parent_l);
}
#[test]
fn test_dict_remove_merge_revive() {
let mut ctx = crate::Context::default();
let one = crate::Cell::new(&mut ctx, "one");
let two = crate::Cell::new(&mut ctx, "two");
let mut root = Dict::default();
root.insert(&mut ctx, 0, two.clone());
let mut child_insert = root.clone();
child_insert.insert(&mut ctx, 0, one.clone());
let mut child_remove = root.clone();
child_remove.remove(&mut ctx, 0);
let merged = crate::test::test_merge(&mut [&child_remove, &child_insert]);
assert_eq!(merged, child_insert);
}
#[test]
fn test_undo_insert() {
let mut ctx = crate::Context::default();
let mut base = Dict::default();
let v = crate::Cell::new(&mut ctx, "one");
base.insert(&mut ctx, 1, v);
let mut updated = base.clone();
let v = crate::Cell::new(&mut ctx, "two");
updated.insert(&mut ctx, 2, v);
let diff_two = crate::Mergable::diff(&updated, &base);
crate::Mergable::apply(&mut base, diff_two.clone()).unwrap();
let initial = updated.clone();
let v = crate::Cell::new(&mut ctx, "three");
updated.insert(&mut ctx, 3, v);
let diff_three = crate::Mergable::diff(&updated, &base);
let revert = crate::Diff::revert(diff_two).unwrap();
let result = crate::test::test_apply(initial, &mut [
diff_three,
revert,
]);
updated.remove(&mut ctx, 2);
assert_eq!(result, updated);
}
#[test]
fn test_undo_remove() {
let mut ctx = crate::Context::default();
let mut base = Dict::default();
let v = crate::Cell::new(&mut ctx, "one");
base.insert(&mut ctx, 1, v);
let v = crate::Cell::new(&mut ctx, "two");
base.insert(&mut ctx, 2, v);
let mut updated = base.clone();
updated.remove(&mut ctx, 2);
let diff_two_remove = crate::Mergable::diff(&updated, &base);
crate::Mergable::apply(&mut base, diff_two_remove.clone()).unwrap();
let initial = base.clone();
let v = crate::Cell::new(&mut ctx, "three");
updated.insert(&mut ctx, 3, v);
let diff_three = crate::Mergable::diff(&updated, &base);
let revert = crate::Diff::revert(diff_two_remove.clone()).unwrap();
let result = crate::test::test_apply(initial, &mut [
diff_three,
revert,
]);
let mut expected = Dict::default();
let v = crate::Cell::new(&mut ctx, "one");
expected.insert(&mut ctx, 1, v);
let v = crate::Cell::new(&mut ctx, "two");
expected.insert(&mut ctx, 2, v);
let v = crate::Cell::new(&mut ctx, "three");
expected.insert(&mut ctx, 3, v);
assert_eq!(result, expected);
}
#[test]
fn test_undo_update() {
let mut ctx = crate::Context::default();
let mut base = Dict::default();
let mut sub = Dict::default();
let v = crate::Cell::new(&mut ctx, "one");
sub.insert(&mut ctx, 1, v);
base.insert(&mut ctx, (), sub);
let mut updated = base.clone();
let v = crate::Cell::new(&mut ctx, "two");
updated.get_mut(&()).unwrap().insert(&mut ctx, 2, v);
let diff_two = crate::Mergable::diff(&updated, &base);
let revert_diff_two = crate::Diff::revert(diff_two.clone()).unwrap();
dbg!(&updated, &base, &diff_two, &revert_diff_two);
crate::Mergable::apply(&mut base, diff_two).unwrap();
let v = crate::Cell::new(&mut ctx, "three");
updated.get_mut(&()).unwrap().insert(&mut ctx, 3, v);
let diff_three = crate::Mergable::diff(&updated, &base);
let result = crate::test::test_apply(base, &mut [
diff_three,
revert_diff_two,
]);
let mut sub = Dict::default();
let v = crate::Cell::new(&mut ctx, "one");
sub.insert(&mut ctx, 1, v);
let v = crate::Cell::new(&mut ctx, "three");
sub.insert(&mut ctx, 3, v);
let mut expected = Dict::default();
expected.insert(&mut ctx, (), sub);
assert_eq!(result, expected);
}
#[test]
fn test_undo_old_update() {
let mut ctx = crate::Context::default();
let mut base = Dict::default();
let mut sub = Dict::default();
let v = crate::Cell::new(&mut ctx, "one");
sub.insert(&mut ctx, 1, v);
base.insert(&mut ctx, (), sub);
let mut updated = base.clone();
let v = crate::Cell::new(&mut ctx, "two");
updated.get_mut(&()).unwrap().insert(&mut ctx, 2, v);
let diff_two = crate::Mergable::diff(&updated, &base);
let revert_diff_two = crate::Diff::revert(diff_two.clone()).unwrap();
crate::Mergable::apply(&mut base, diff_two).unwrap();
let v = crate::Cell::new(&mut ctx, "three");
updated.get_mut(&()).unwrap().insert(&mut ctx, 3, v);
let diff_three = crate::Mergable::diff(&updated, &base);
let result = crate::test::test_apply(base, &mut [
diff_three,
revert_diff_two,
]);
let mut sub = Dict::default();
let v = crate::Cell::new(&mut ctx, "one");
sub.insert(&mut ctx, 1, v);
let v = crate::Cell::new(&mut ctx, "three");
sub.insert(&mut ctx, 3, v);
let mut expected = Dict::default();
expected.insert(&mut ctx, (), sub);
assert_eq!(result, expected);
}
#[test]
fn test_iter() {
let mut ctx = crate::Context::default();
let one = crate::Cell::new(&mut ctx, "one");
let two = crate::Cell::new(&mut ctx, "two");
let three = crate::Cell::new(&mut ctx, "three");
let mut dict = Dict::default();
dict.insert(&mut ctx, 1, one);
dict.insert(&mut ctx, 2, two);
dict.remove(&mut ctx, 2);
dict.insert(&mut ctx, 3, three);
let mut seen = Vec::with_capacity(2);
for (k, v) in &dict {
seen.push((*k, **v));
}
seen.sort_unstable();
assert_eq!(seen, &[(1, "one"), (3, "three")]);
}
#[test]
fn test_into_iter() {
let mut ctx = crate::Context::default();
let one = crate::Cell::new(&mut ctx, "one".to_string());
let two = crate::Cell::new(&mut ctx, "two".to_string());
let three = crate::Cell::new(&mut ctx, "three".to_string());
let mut dict = Dict::default();
dict.insert(&mut ctx, "1".to_string(), one);
dict.insert(&mut ctx, "2".to_string(), two);
dict.remove::<String>(&mut ctx, "2".to_string());
dict.insert(&mut ctx, "3".to_string(), three);
let mut seen = Vec::with_capacity(2);
for (k, v) in dict {
seen.push((k, v.into()));
}
seen.sort_unstable();
assert_eq!(seen, &[
("1".to_string(), "one".to_string()),
("3".to_string(), "three".to_string()),
]);
}
#[test]
fn test_clean() {
let mut ctx = crate::Context::default();
let mut d1 = Dict::default();
let one = crate::Cell::new(&mut ctx, "one");
d1.insert(&mut ctx, 1, one);
let d2 = d1.clone();
let seq_fork = ctx.next_sequence();
d1.remove(&mut ctx, 1);
let seq_remove = ctx.next_sequence();
assert_eq!(d1.removed.len(), 1);
crate::Mergable::clean(&mut d1, &seq_fork);
assert_eq!(d1.removed.len(), 1);
let result = crate::test::test_merge(&mut [&d1, &d2]);
assert_eq!(result.len(), 0);
crate::Mergable::clean(&mut d1, &seq_remove);
assert_eq!(d1.removed.len(), 0);
let result = crate::test::test_merge(&mut [&d1, &d2]);
assert_eq!(result.len(), 1);
}