mergable/

dict.rs

/** A mergable dictionary.
 *
 * This dict must contain a `Mergable` value. This determines the semantics on conflict. For example if the value is a `Cell` then last-write-wins semantics will be used. However if the value is a `Bag` then multiple values inserted into the same key will be kept. If the value is a `Counter` than conflicting values will be summed.
 */
#[derive(Clone)]
pub struct Dict<K, V, Seq> {
	live: std::collections::HashMap<K, Value<V, Seq>>,

	/** Removed entries.
	 *
	 * Keys are sequences of entires that have been deleted and values are when they were deleted.
	 */
	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(
		/// What
		Seq,
		/// Value (for reverts)
		Option<(K, V)>,
		/// When
		Seq,
	),
	Up(
		/// What
		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)
	}

	/** Insert a value into the map.
	 *
	 * Note that if the value is already in the map the two values will be *merged*. If you do not want this to occur `delete` the value first.

	 * Also note that this updates the key's creation time meaning that deletes on the previous key will no longer be respected.

	 * TODO: Weird revival stuff.
	 */
	pub fn insert(&mut self, ctx: &mut crate::Context<SF>, k: K, v: V) {
		self.entry(k).insert(ctx, v);
	}

	/** Remove a value from the map.
	 *
	 * Note that the semantics of this operation can be confusing read the description carefully.
	 *
	 * This removes the *known* version of the element in the map and all older versions. Unknown modifications will not prevent deletion but if the element has been `insert`ed again after the version that we are aware of that insert will be preserved. Also note that due to merging semantics that may result in values from the known version "reappearing".
	 */
	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 {
		// write!(f, "{:?} @ {:?}", self.value, self.sequence)
		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());

	// We remove the left entry. However the right is created after this.
	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());

	// We remove the right entry. Since this was created later the removal wins.
	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());

	// Note that this "insert" actually merges the cells, resulting in "two" winning because it is newer (even though the insert happened earlier.
	let mut child_insert = root.clone();
	child_insert.insert(&mut ctx, 0, one.clone());

	// This removes the value. However since it doesn't know about child_insert's insertion that is preserved and the "two" value is "revived".
	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);
	// Nothing was removed at this point.
	assert_eq!(d1.removed.len(), 1);

	// The remove is remembered because it happened last.
	let result = crate::test::test_merge(&mut [&d1, &d2]);
	assert_eq!(result.len(), 0);

	crate::Mergable::clean(&mut d1, &seq_remove);
	// All deletions happened before the cutoff.
	assert_eq!(d1.removed.len(), 0);

	// Merging with d2 with values before the cutoff causes unintended revival.
	let result = crate::test::test_merge(&mut [&d1, &d2]);
	assert_eq!(result.len(), 1);
}