safemesh_crdt/crdt/gcounter.rs
1// SafeMesh — delta-state CRDT convergence, built on crdt-lean.
2// Copyright (C) 2026 Ben Cassie
3// SPDX-License-Identifier: Apache-2.0
4
5use crate::{ownership, Crdt, MergeError, Mergeable, RecordId, WireError};
6use alloc::vec::Vec;
7
8/// Delta for a grow-only counter: one replica coordinate and its asserted tally.
9#[derive(Clone, Debug, PartialEq, Eq)]
10pub struct GCounterDelta {
11 pub replica: usize,
12 pub tally: u64,
13}
14
15/// Rejection of an invalid counter domain or replica coordinate.
16#[derive(Clone, Copy, Debug, PartialEq, Eq)]
17pub enum CoordinateError {
18 /// The requested constructor domain exceeds [`GCounter::MAX_REPLICAS`].
19 ReplicaLimitExceeded { requested: usize, maximum: usize },
20 /// The index is outside `0..replica_count`; the counter is unchanged.
21 ReplicaOutOfRange {
22 replica: usize,
23 replica_count: usize,
24 },
25}
26
27impl core::fmt::Display for CoordinateError {
28 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
29 match self {
30 Self::ReplicaLimitExceeded { requested, maximum } => {
31 write!(f, "replica count {requested} exceeds maximum {maximum}")
32 }
33 Self::ReplicaOutOfRange {
34 replica,
35 replica_count,
36 } => write!(
37 f,
38 "replica coordinate {replica} is outside 0..{replica_count}"
39 ),
40 }
41 }
42}
43
44impl core::error::Error for CoordinateError {}
45
46/// A grow-only counter: one tally per replica, join = pointwise max.
47///
48/// Model: `Crdt.GCounter ι = ι → ℕ` with the Pi join-semilattice. Applying a
49/// delta is joining it in, so delivery order and redelivery are irrelevant —
50/// `SafeMesh.delta_dissemination_sec` — and a replica that received bumps `B`
51/// holds, per coordinate, the max over that coordinate's bumps —
52/// `SafeMesh.deltaGCounter_correct`.
53#[derive(Clone, Debug, PartialEq, Eq)]
54pub struct GCounter {
55 counts: Vec<u64>,
56}
57
58impl GCounter {
59 /// Maximum constructor domain: 4,096 replicas, matching the default wire
60 /// version-vector author limit. Storage is at most 32 KiB per G-counter
61 /// (64 KiB per PN-counter), below the WASM and Python numeric limits.
62 pub const MAX_REPLICAS: usize = 4_096;
63
64 /// Fresh counter for `n` replicas — the lattice bottom `⊥` (all zeros).
65 ///
66 /// # Panics
67 /// Panics above [`Self::MAX_REPLICAS`] or on allocator refusal. Use
68 /// [`Self::try_new`] to receive a named error instead.
69 pub fn new(n: usize) -> Self {
70 Self::try_new(n).expect("counter width cannot be allocated")
71 }
72
73 /// Fresh counter with a domain bounded by [`Self::MAX_REPLICAS`].
74 ///
75 /// The 4,096-replica maximum matches the default wire author limit and
76 /// bounds storage to 32 KiB. Larger counts return `ReplicaLimitExceeded`
77 /// before allocation. Admitted counts use the allocator's zeroed path,
78 /// like `vec![0; n]`, without an explicit page-touching initialization loop.
79 /// As on main, admitted allocations use `vec![0; n]`; an out-of-memory
80 /// allocator can abort. The cap bounds this request to 32 KiB.
81 pub fn try_new(n: usize) -> Result<Self, CoordinateError> {
82 if n > Self::MAX_REPLICAS {
83 return Err(CoordinateError::ReplicaLimitExceeded {
84 requested: n,
85 maximum: Self::MAX_REPLICAS,
86 });
87 }
88 let counts = alloc::vec![0; n];
89 Ok(GCounter { counts })
90 }
91
92 /// Number of replica coordinates.
93 pub fn len(&self) -> usize {
94 self.counts.len()
95 }
96
97 pub fn is_empty(&self) -> bool {
98 self.counts.is_empty()
99 }
100
101 /// Apply the delta `SafeMesh.deltaBump replica tally` — a single
102 /// coordinate on the wire. Joining the delta is `max` at that coordinate
103 /// (`Pi.single` joined into the state); applying the same bump again is a
104 /// no-op (idempotence, `SafeMesh.delta_dissemination_sec`).
105 ///
106 /// Out-of-range `replica` is ignored (a malformed delta must not corrupt
107 /// state; the Lean model has no such case — `Fin n` makes it unrepresentable).
108 /// Use [`Self::try_apply_bump`] to receive an error for an invalid index.
109 pub fn apply_bump(&mut self, replica: usize, tally: u64) {
110 if let Some(c) = self.counts.get_mut(replica) {
111 if tally > *c {
112 *c = tally;
113 }
114 }
115 }
116
117 /// Apply a single-coordinate delta, returning an error for an invalid index.
118 ///
119 /// Checks the coordinate before mutation. On error, the entire counter is
120 /// unchanged; on success, behaves exactly like [`Self::apply_bump`], including
121 /// accepting an equal or lower tally as a no-op.
122 pub fn try_apply_bump(&mut self, replica: usize, tally: u64) -> Result<(), CoordinateError> {
123 if replica >= self.counts.len() {
124 return Err(CoordinateError::ReplicaOutOfRange {
125 replica,
126 replica_count: self.counts.len(),
127 });
128 }
129 self.apply_bump(replica, tally);
130 Ok(())
131 }
132
133 /// Checked full-state merge: pointwise max, erroring on a replica-count
134 /// mismatch instead of silently truncating to the shorter vector (WS1).
135 /// This is the boundary-safe entry point for state received from an
136 /// untrusted peer.
137 pub fn try_merge(&mut self, other: &GCounter) -> Result<(), MergeError> {
138 if self.counts.len() != other.counts.len() {
139 return Err(MergeError::ReplicaCountMismatch {
140 own: self.counts.len(),
141 other: other.counts.len(),
142 });
143 }
144 for (c, o) in self.counts.iter_mut().zip(other.counts.iter()) {
145 if *o > *c {
146 *c = *o;
147 }
148 }
149 Ok(())
150 }
151
152 /// Full-state merge: pointwise max — `Crdt.gcounter_merge_apply`. A
153 /// delta replica and a full-state replica fed the same bumps agree:
154 /// `SafeMesh.deltaGCounter_matches_full`.
155 ///
156 /// Returns [`MergeError::ReplicaCountMismatch`] without changing state if
157 /// the replica counts differ, just like [`GCounter::try_merge`].
158 pub fn merge(&mut self, other: &GCounter) -> Result<(), MergeError> {
159 self.try_merge(other)
160 }
161
162 /// Per-coordinate state (the `ι → ℕ` vector).
163 pub fn state(&self) -> &[u64] {
164 &self.counts
165 }
166
167 /// The counter's read: sum of per-replica tallies — `Crdt.gcounterValue`,
168 /// a natural number with no upper bound in the model.
169 ///
170 /// The read is exact for every state this counter can hold: at most
171 /// `isize::MAX` coordinates, each at most `u64::MAX`, sum to strictly less
172 /// than `2^127`, so the `u128` total never wraps and is never clamped. A
173 /// total that no longer fits a narrower integer is still returned whole;
174 /// a caller that needs `u64` narrows it with `u64::try_from` and handles
175 /// the failure itself.
176 pub fn value(&self) -> u128 {
177 self.counts.iter().map(|&tally| u128::from(tally)).sum()
178 }
179}
180
181impl Mergeable for GCounter {
182 fn merge(&mut self, other: &Self) -> Result<(), MergeError> {
183 GCounter::merge(self, other)
184 }
185}
186
187impl Crdt for GCounter {
188 type Delta = GCounterDelta;
189
190 fn validate_record(&self, id: RecordId, delta: &Self::Delta) -> Result<(), WireError> {
191 ownership::check_counter_record(self.len(), id, delta)
192 .map_err(|_| WireError::OwnershipViolation)
193 }
194
195 fn replica_count(&self) -> Option<usize> {
196 Some(self.len())
197 }
198
199 fn apply_delta(&mut self, delta: Self::Delta) {
200 self.apply_bump(delta.replica, delta.tally);
201 }
202}
203
204#[cfg(test)]
205mod construction_tests {
206 use super::*;
207 use crate::WireEncode;
208
209 #[test]
210 fn unallocatable_counter_width_returns_error() {
211 for width in [
212 GCounter::MAX_REPLICAS + 1,
213 usize::MAX,
214 usize::try_from(1u64 << 40).unwrap_or(usize::MAX),
215 ] {
216 let expected = CoordinateError::ReplicaLimitExceeded {
217 requested: width,
218 maximum: GCounter::MAX_REPLICAS,
219 };
220 assert_eq!(GCounter::try_new(width), Err(expected));
221 assert_eq!(crate::PnCounter::try_new(width), Err(expected));
222 }
223 let max = GCounter::try_new(GCounter::MAX_REPLICAS).unwrap();
224 assert_eq!(max.len(), GCounter::MAX_REPLICAS);
225 assert!(max.counts.iter().all(|&x| x == 0));
226 let pn = crate::PnCounter::try_new(GCounter::MAX_REPLICAS).unwrap();
227 assert!(pn.p_state().iter().chain(pn.n_state()).all(|&x| x == 0));
228 assert!(crate::PnCounter::try_new(usize::MAX).is_err());
229 let largest = isize::MAX as usize / core::mem::size_of::<u64>();
230 assert!(GCounter::try_new(largest + 1).is_err());
231 for n in [0, 1, 2] {
232 assert_eq!(GCounter::try_new(n).unwrap(), GCounter::new(n));
233 assert_eq!(
234 crate::PnCounter::try_new(n).unwrap(),
235 crate::PnCounter::new(n)
236 );
237 }
238 let mut counter = GCounter::try_new(2).unwrap();
239 counter.try_apply_bump(0, 7).unwrap();
240 assert_eq!(counter.value(), 7);
241 assert!(!GCounterDelta {
242 replica: 0,
243 tally: 7
244 }
245 .to_wire_bytes()
246 .unwrap()
247 .is_empty());
248 }
249}