1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
extern crate alloc;
use alloc::collections::BTreeMap;
use super::DotSet;
impl DotSet {
/// Returns the restriction of this have-set to `roster`: the same dots on
/// the stations the roster names, nothing anywhere else.
///
/// The base-change read (PRD 0013), the have-set instance of
/// [`VersionVector::restrict`](crate::metis::VersionVector::restrict).
/// Restriction selects whole per-station fibers and never looks inside one,
/// so it commutes *exactly* with every read and fold on the type: the
/// restriction of a [`merge`](Self::merge) is the merge of the restrictions,
/// the [`floor`](Self::floor) of the restriction is the restriction of the
/// floor, likewise
/// [`high_water`](Self::high_water), [`holes`](Self::holes) (the holes at
/// roster stations, in the same order), and [`from_witnessed`](Self::from_witnessed)
/// (embed then restrict equals restrict then embed). Contrast the floor
/// under `merge`, which is only lax: that law crosses a station's interior,
/// where union fills holes; base change never crosses one.
///
/// Roster stations with no received dots contribute nothing, duplicates
/// are harmless, and canonical form is preserved.
#[must_use]
pub fn restrict(&self, roster: impl IntoIterator<Item = u32>) -> Self {
let mut stations = BTreeMap::new();
for station in roster {
if let Some(dots) = self.stations.get(&station) {
let _ = stations.insert(station, dots.clone());
}
}
Self { stations }
}
/// The union of two have-sets: the join of the have-set lattice.
///
/// Commutative, associative, idempotent, total; a dot is in the union iff
/// it is in either side. Models one replica learning everything another
/// holds (an anti-entropy exchange of exact have-sets); see
/// [`floor`](Self::floor) for why the union's floor can exceed the join of
/// the floors.
#[must_use]
pub fn merge(&self, other: &Self) -> Self {
let mut stations = self.stations.clone();
for (&station, slot) in &other.stations {
let merged = stations
.get(&station)
.map_or_else(|| slot.clone(), |mine| mine.merge(slot));
let _ = stations.insert(station, merged);
}
Self { stations }
}
/// The union in place: observationally identical to
/// `*self = self.merge(other)`, touching only the stations `other` names
/// (the [`clone_from`](Clone::clone_from) shape, S182).
///
/// The knowledge-fold half of the in-place causal merge: the pair's
/// context coordinate grows by exactly `other`'s stations, so a
/// delta-sized fold costs the delta, not the document. Grow-only like
/// [`merge`](Self::merge); `pub(crate)` because no consumer has asked for
/// the in-place form (each half of a symmetry faces its license alone).
pub(crate) fn merge_from(&mut self, other: &Self) {
for (&station, slot) in &other.stations {
match self.stations.entry(station) {
alloc::collections::btree_map::Entry::Vacant(vacant) => {
let _ = vacant.insert(slot.clone());
}
alloc::collections::btree_map::Entry::Occupied(mut occupied) => {
let merged = occupied.get().merge(slot);
let _ = occupied.insert(merged);
}
}
}
}
/// The intersection of two have-sets: the meet of the have-set lattice.
///
/// Commutative, associative, idempotent, total; a dot is in the
/// intersection iff it is in both sides. The audit read ("what did *both*
/// replicas receive") and, since S96, the first leg of the causal store
/// merge (a dot both stores carry survives it unconditionally).
///
/// The bracketing reads obey the mirror image of the union's asymmetric
/// pair, exactly as the adjoint ledger predicted before this method
/// existed: the *floor* is exact on intersections
/// (`a.intersect(&b).floor() == a.floor().meet(&b.floor())`, the interior
/// is a meet homomorphism) while the *high water* is only lax
/// (`a.intersect(&b).high_water() <= a.high_water().meet(&b.high_water())`,
/// strictly below when the two sides' maxima at a station are different
/// dots, so the intersection loses both). Canonical form is preserved: a
/// station with no common dots is absent, and the compact form is
/// re-absorbed.
#[must_use]
pub fn intersect(&self, other: &Self) -> Self {
let mut stations = BTreeMap::new();
for (&station, slot) in &self.stations {
let Some(peer) = other.stations.get(&station) else {
continue;
};
let common = slot.intersect(peer);
if common.floor > 0 || !common.above.is_empty() {
let _ = stations.insert(station, common);
}
}
Self { stations }
}
}