abyo_crdt/
version.rs

1//! Version vectors — a summary of "what ops a replica has seen".
2//!
3//! Used by every CRDT in this crate to drive idempotent op application
4//! and incremental sync via [`crate::List::ops_since`] et al.
5
6use crate::id::{OpId, ReplicaId};
7use std::collections::BTreeMap;
8
9#[cfg(feature = "serde")]
10use serde::{Deserialize, Serialize};
11
12/// Summary of "what ops a replica has seen", indexed by replica.
13///
14/// `vv[replica]` is the highest `counter` ever observed from that replica.
15/// Because `counter`s are Lamport timestamps that strictly increase along
16/// any causal chain, "seen `(replica, counter)`" implies "seen everything
17/// from that replica with counter ≤ that counter".
18#[derive(Clone, Default, Debug, Eq, PartialEq)]
19#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
20pub struct VersionVector {
21    /// `replica → highest seen counter`.
22    inner: BTreeMap<ReplicaId, u64>,
23}
24
25impl VersionVector {
26    /// Empty version vector.
27    #[must_use]
28    pub fn new() -> Self {
29        Self::default()
30    }
31
32    /// Has this version vector seen op `id`?
33    #[must_use]
34    pub fn contains(&self, id: OpId) -> bool {
35        self.inner
36            .get(&id.replica)
37            .is_some_and(|&v| v >= id.counter)
38    }
39
40    /// Number of distinct replicas seen.
41    #[must_use]
42    pub fn replica_count(&self) -> usize {
43        self.inner.len()
44    }
45
46    /// Highest counter observed from `replica`, or 0 if none.
47    #[must_use]
48    pub fn get(&self, replica: ReplicaId) -> u64 {
49        self.inner.get(&replica).copied().unwrap_or(0)
50    }
51
52    /// Record `id` as observed.
53    pub fn observe(&mut self, id: OpId) {
54        let entry = self.inner.entry(id.replica).or_insert(0);
55        *entry = (*entry).max(id.counter);
56    }
57
58    /// Iterate `(replica, highest_counter)` pairs in replica-id order.
59    pub fn iter_clocks(&self) -> impl Iterator<Item = (ReplicaId, u64)> + '_ {
60        self.inner.iter().map(|(&r, &c)| (r, c))
61    }
62}
abyo_crdt/version.rs

abyo_crdt/
version.rs
