happenstance_sync_testkit/convergence_suite.rs
1//! The convergence family: SY-20's check over a declared projection, SY-21's
2//! check that it cannot see the local position, and SY-22's proof that the
3//! check excludes what it must not fail.
4//!
5//! # How a check of convergence reorders without a second peer
6//!
7//! Convergence is a property of a fold, not of a peer, so no rule here holds
8//! a peer at all (SY-8). Two peers that ingested the same events differ only
9//! in the order they appended them, and that difference is reproduced exactly
10//! by two replica logs: each event keeps its origin's [`EventId`], and the
11//! local position is the arrival order. The rule writes both logs with
12//! [`MemoryEventStore::restore`], which keeps every store-assigned fact it is
13//! handed, and runs the fixture's projection over each through the shipped
14//! [`run_projection`]. Whether a real ingest store assigns those positions is
15//! the ingest family's question (SY-5), not this one's.
16//!
17//! The two interleavings are origin one's events then origin two's, and the
18//! reverse. They agree on each origin's order and reverse every pair across
19//! origins, and they are the only such pair: an interleaving that alternates
20//! has no partner that reverses all of its cross-origin pairs while keeping
21//! each origin's order. So the two are exactly what SY-20 quantifies over,
22//! "agree on per-origin order and disagree everywhere else", and a third,
23//! alternating interleaving would hold a fold to more than the clause says.
24//!
25//! SY-21's check holds the order still and moves the numbering instead. The
26//! same arrivals, origin one's first, are written to two replicas: one
27//! numbered densely from the first position, one from far past it with gaps
28//! between, which the event-store contract permits. `Delivered` hands a fold
29//! no position; the channel to the local position that the port a fold is
30//! given offers is the projection store's checkpoint. The rule compares read
31//! models, not channels, so a fold that lets the local numbering reach its
32//! read model by any route commits two, and the checkpoint is the route the
33//! wrong projection in `tests/` takes. SY-20's interleavings cannot see that
34//! fold: both are numbered densely over the same count of events, so the
35//! checkpoint runs through the same values in each.
36//!
37//! Every event carries one [`RecordedAt`]. `Delivered` does not hand a fold
38//! the time, and a fold that found it another way could order by it only
39//! with ties broken by arrival, which is arrival order again.
40
41use alloc::format;
42use alloc::string::String;
43use alloc::vec::Vec;
44use core::num::{NonZeroU64, NonZeroUsize};
45
46use happenstance::{Chunk, DomainEvent, run_projection};
47use happenstance_core::{
48 Event, EventId, MemoryEventStore, RecordedAt, SequencePosition, SequencedEvent, StoreId,
49};
50
51use crate::Violation;
52use crate::convergence_fixture::{ConvergenceFixture, EventOf};
53use crate::violation::ensure;
54
55/// The first origin's identity. Distinct from the second's and the replica's,
56/// so no identity coincides with a local position by construction.
57const ORIGIN_ONE: StoreId = StoreId::from_bytes([0x0a; 16]);
58/// The second origin's identity.
59const ORIGIN_TWO: StoreId = StoreId::from_bytes([0x0b; 16]);
60/// The replica both interleavings are ingested into.
61const REPLICA: StoreId = StoreId::from_bytes([0x0c; 16]);
62/// One instant for every event.
63const RECORDED: RecordedAt = RecordedAt::from_millis(0);
64/// Two events per commit, so a fold's state crosses a commit boundary in
65/// every case with more than two events.
66const CHUNK: NonZeroUsize = NonZeroUsize::MIN.saturating_add(1);
67/// One event per commit, for SY-21's runs: every event after the first is
68/// applied over a committed checkpoint, so a fold that reads it sees a local
69/// position in every case the fixture contract admits, which is two events
70/// at least.
71const ONE_AT_A_TIME: NonZeroUsize = NonZeroUsize::MIN;
72/// Where SY-21's second replica starts numbering: far from the first
73/// position, so every event's local position differs between the two
74/// replicas.
75const OFFSET_FROM: NonZeroU64 = NonZeroU64::MIN.saturating_add(999);
76/// The gap between its consecutive positions, so the numbering is not only
77/// shifted but gapped.
78const OFFSET_STRIDE: NonZeroU64 = NonZeroU64::MIN.saturating_add(2);
79
80/// One event as its origin wrote it: the identity every replica shares, and
81/// the encoded event.
82type Authored = (EventId, Event);
83
84/// Each origin's events, identified and encoded once, in authorship order.
85fn author<F: ConvergenceFixture>(
86 fixture: &F,
87 clause: &'static str,
88) -> Result<[Vec<Authored>; 2], Violation> {
89 let [one, two] = fixture.authored();
90 Ok([
91 identify(ORIGIN_ONE, one, fixture, clause)?,
92 identify(ORIGIN_TWO, two, fixture, clause)?,
93 ])
94}
95
96fn identify<F: ConvergenceFixture>(
97 origin: StoreId,
98 events: Vec<EventOf<F>>,
99 fixture: &F,
100 clause: &'static str,
101) -> Result<Vec<Authored>, Violation> {
102 ensure(!events.is_empty(), clause, || {
103 format!(
104 "the fixture authored no events at origin {origin}, so both interleavings are one \
105 log and the check would compare it with itself; hand the rule events from both \
106 origins"
107 )
108 })?;
109 let mut authored = Vec::with_capacity(events.len());
110 for (there, event) in (1..).zip(events) {
111 let position = SequencePosition::new(there).ok_or_else(|| {
112 Violation::new(clause, "an origin position counted from one was zero")
113 })?;
114 let data = event.encode(fixture.codec()).map_err(|error| {
115 Violation::new(
116 clause,
117 format!("the fixture's event did not encode: {error}"),
118 )
119 })?;
120 let encoded = Event::new(event.event_type(), data)
121 .map_err(|error| {
122 Violation::new(
123 clause,
124 format!("the fixture's event type is invalid: {error}"),
125 )
126 })?
127 .with_tags(event.tags());
128 authored.push((EventId::new(origin, position), encoded));
129 }
130 Ok(authored)
131}
132
133/// The replica that appended `arrivals` in that order, numbered densely from
134/// the first position.
135fn replica<'a>(
136 arrivals: impl Iterator<Item = &'a Authored>,
137 clause: &'static str,
138) -> Result<MemoryEventStore, Violation> {
139 replica_at(arrivals, NonZeroU64::MIN, NonZeroU64::MIN, clause)
140}
141
142/// The replica that appended `arrivals` in that order, numbering them from
143/// `first` with `stride` between consecutive positions.
144fn replica_at<'a>(
145 arrivals: impl Iterator<Item = &'a Authored>,
146 first: NonZeroU64,
147 stride: NonZeroU64,
148 clause: &'static str,
149) -> Result<MemoryEventStore, Violation> {
150 let mut log = Vec::new();
151 let mut here = Some(first.get());
152 for (id, event) in arrivals {
153 let position = here.and_then(SequencePosition::new).ok_or_else(|| {
154 Violation::new(clause, "a local position ran past the end of the key space")
155 })?;
156 here = position.get().checked_add(stride.get());
157 // Genuinely duplicated: the same event is appended to both replicas'
158 // logs, and each store keeps its own. The payload is a `Bytes`, so
159 // the copy is of the envelope, not the data.
160 log.push(SequencedEvent::new(position, *id, RECORDED, event.clone()));
161 }
162 Ok(MemoryEventStore::restore(REPLICA, log))
163}
164
165/// What a fresh projection commits over `log`, read back as bytes.
166async fn committed<F: ConvergenceFixture>(
167 fixture: &F,
168 log: &MemoryEventStore,
169 expected: usize,
170 order: &str,
171 chunk: NonZeroUsize,
172 clause: &'static str,
173) -> Result<Vec<u8>, Violation> {
174 let models = fixture.store().await?;
175 let mut projection = fixture.projection();
176 let progressed = run_projection(
177 log,
178 &models,
179 &mut projection,
180 fixture.codec(),
181 Chunk::of(chunk),
182 )
183 .await
184 .map_err(|error| {
185 Violation::new(
186 clause,
187 format!("the projection's run over {order} failed: {error}"),
188 )
189 })?;
190 ensure(progressed.applied == expected, clause, || {
191 format!(
192 "the projection applied {} of the {expected} events over {order}, so the check saw \
193 less than the case; every event the fixture authors must be in the projection's \
194 scope",
195 progressed.applied
196 )
197 })?;
198 fixture.read_model(&models).await
199}
200
201/// The read models a fresh projection commits under each interleaving:
202/// origin one first, then origin two first.
203///
204/// Not bounded on the declaration, so SY-22's rule can run the case the
205/// declaration excludes through exactly the machinery SY-20's rule uses.
206pub(crate) async fn read_models<F: ConvergenceFixture>(
207 fixture: &F,
208 clause: &'static str,
209) -> Result<[Vec<u8>; 2], Violation> {
210 let [one, two] = author(fixture, clause)?;
211 let expected = one.len().saturating_add(two.len());
212 let one_first = replica(one.iter().chain(&two), clause)?;
213 let two_first = replica(two.iter().chain(&one), clause)?;
214 Ok([
215 committed(
216 fixture,
217 &one_first,
218 expected,
219 "origin one first",
220 CHUNK,
221 clause,
222 )
223 .await?,
224 committed(
225 fixture,
226 &two_first,
227 expected,
228 "origin two first",
229 CHUNK,
230 clause,
231 )
232 .await?,
233 ])
234}
235
236/// The read models a fresh projection commits over one arrival order, origin
237/// one's events first, under two numberings of it: dense from the first
238/// position, then offset and gapped.
239async fn read_models_numbered_twice<F: ConvergenceFixture>(
240 fixture: &F,
241 clause: &'static str,
242) -> Result<[Vec<u8>; 2], Violation> {
243 let [one, two] = author(fixture, clause)?;
244 let expected = one.len().saturating_add(two.len());
245 let dense = replica(one.iter().chain(&two), clause)?;
246 let offset = replica_at(one.iter().chain(&two), OFFSET_FROM, OFFSET_STRIDE, clause)?;
247 Ok([
248 committed(
249 fixture,
250 &dense,
251 expected,
252 "dense local positions",
253 ONE_AT_A_TIME,
254 clause,
255 )
256 .await?,
257 committed(
258 fixture,
259 &offset,
260 expected,
261 "offset, gapped local positions",
262 ONE_AT_A_TIME,
263 clause,
264 )
265 .await?,
266 ])
267}
268
269/// A read model as a reader of a failure message wants it.
270pub(crate) fn shown(model: &[u8]) -> String {
271 format!("{:?}", String::from_utf8_lossy(model))
272}
273
274/// Hands the complete convergence rule set to `$callback`.
275///
276/// This family's single enumeration (CF-22), beside the rules it names. No
277/// mounting macro reads it, because the family has no adapter to mount it
278/// beside: a projection author calls the SY-20 and SY-21 rules over a fixture
279/// of their own, and the SY-22 rule takes nothing.
280///
281/// # Examples
282///
283/// ```
284/// macro_rules! rule_names {
285/// ($($name:ident),* $(,)?) => { [ $( stringify!($name) ),* ] };
286/// }
287///
288/// let names = happenstance_sync_testkit::for_each_convergence_rule!(rule_names);
289/// assert_eq!(
290/// names,
291/// [
292/// "convergent_projection_is_interleaving_independent",
293/// "convergent_projection_cannot_observe_local_position",
294/// "non_convergent_projections_are_excluded_not_failed",
295/// ]
296/// );
297/// ```
298#[macro_export]
299macro_rules! for_each_convergence_rule {
300 ($($callback:tt)+) => {
301 $($callback)+! {
302 // --- A declared projection converges (SY-20) ---------------------
303 convergent_projection_is_interleaving_independent,
304
305 // --- ... and cannot see the local position (SY-21) ---------------
306 convergent_projection_cannot_observe_local_position,
307
308 // --- An undeclared one is excluded, not failed (SY-22) -----------
309 non_convergent_projections_are_excluded_not_failed,
310 }
311 };
312}
313
314/// The convergence rules (SY-20, SY-21, SY-22).
315///
316/// Each returns `Result<RuleOutcome, Violation>`, as every rule in this crate
317/// does. None has a capability to decline, so none ever reports a skip.
318pub mod convergence_rules {
319 use happenstance::ConvergentProjection;
320 use happenstance_testkit::RuleOutcome;
321
322 use super::{read_models, read_models_numbered_twice, shown};
323 use crate::Violation;
324 use crate::convergence_fixture::{ConvergenceFixture, CostLayersFixture, StockOnHandFixture};
325 use crate::violation::ensure;
326
327 /// **SY-20.** A declared projection commits byte-identical read models
328 /// under two interleavings that agree on each origin's order and disagree
329 /// everywhere else.
330 ///
331 /// The fixture's projection is run twice, fresh each time, over the two
332 /// origins' events: origin one's first, then origin two's first. Its read
333 /// models are compared byte for byte. A fixture whose projection has not
334 /// declared [`ConvergentProjection`] cannot be handed to this rule; that
335 /// is SY-22's exclusion, and
336 /// [`non_convergent_projections_are_excluded_not_failed`] holds it.
337 ///
338 /// Rejects `unit-ledger`, a per-serial state machine that keeps whatever
339 /// arrived last, and with it the class: any fold whose answer depends on
340 /// arrival — a count of arrivals kept as an order, a first or last
341 /// writer by arrival, a queue consumed in arrival order.
342 /// `tests/wrong_projections.rs` holds each against this rule.
343 ///
344 /// # Errors
345 ///
346 /// A [`Violation`] of SY-20 if the two read models differ, if either
347 /// origin authored nothing, if a run applied fewer events than it was
348 /// handed or failed, or if the fixture could not open or read a store.
349 ///
350 /// # Examples
351 ///
352 /// ```
353 /// use happenstance_sync_testkit::{StockOnHandFixture, convergence_rules};
354 /// use happenstance_testkit::{RuleOutcome, block_on};
355 ///
356 /// let outcome = block_on(
357 /// convergence_rules::convergent_projection_is_interleaving_independent(async || {
358 /// StockOnHandFixture::new()
359 /// }),
360 /// )?;
361 /// assert_eq!(outcome, RuleOutcome::Ran);
362 /// # Ok::<(), happenstance_sync_testkit::Violation>(())
363 /// ```
364 pub async fn convergent_projection_is_interleaving_independent<F>(
365 open: impl AsyncFn() -> F,
366 ) -> Result<RuleOutcome, Violation>
367 where
368 F: ConvergenceFixture,
369 F::Projection: ConvergentProjection,
370 {
371 const CLAUSE: &str = "SY-20";
372 let fixture = open().await;
373 let [one_first, two_first] = read_models(&fixture, CLAUSE).await?;
374 ensure(one_first == two_first, CLAUSE, || {
375 format!(
376 "a projection declared convergent committed {} with origin one's events first \
377 and {} with origin two's first; its answer depends on arrival order",
378 shown(&one_first),
379 shown(&two_first)
380 )
381 })?;
382 Ok(RuleOutcome::Ran)
383 }
384
385 /// **SY-21.** A declared projection cannot observe the local position:
386 /// the same arrivals, numbered twice, commit byte-identical read models.
387 ///
388 /// The fixture's projection is run twice, fresh each time and one event
389 /// per commit, over one arrival order, origin one's events first. The
390 /// first replica numbers the events densely from the first position; the
391 /// second numbers them from far past it, with gaps between. `Delivered`
392 /// already withholds the position from the fold (SY-21's compile-fail
393 /// fences). The rule compares read models, so any channel that lets the
394 /// local numbering reach them fails it; the one the port a fold is given
395 /// offers is its store's checkpoint.
396 ///
397 /// That is a reading of SY-21, not its letter. The clause forbids handing
398 /// the arrival position "in the value it folds over", and its reopening
399 /// condition grants a fold the store's own checkpoint. This rule takes
400 /// the clause to mean that a fold may read its checkpoint but must not
401 /// let it reach the read model: SY-20's property, applied to positions.
402 ///
403 /// Rejects a projection that writes its checkpoint into its read model,
404 /// which SY-20's rule passes, since both of its interleavings number the
405 /// same count of events densely. `tests/wrong_projections.rs` holds it
406 /// against both rules.
407 ///
408 /// # Errors
409 ///
410 /// A [`Violation`] of SY-21 if the two read models differ, if either
411 /// origin authored nothing, if a run applied fewer events than it was
412 /// handed or failed, or if the fixture could not open or read a store.
413 ///
414 /// # Examples
415 ///
416 /// ```
417 /// use happenstance_sync_testkit::{StockOnHandFixture, convergence_rules};
418 /// use happenstance_testkit::{RuleOutcome, block_on};
419 ///
420 /// let outcome = block_on(
421 /// convergence_rules::convergent_projection_cannot_observe_local_position(async || {
422 /// StockOnHandFixture::new()
423 /// }),
424 /// )?;
425 /// assert_eq!(outcome, RuleOutcome::Ran);
426 /// # Ok::<(), happenstance_sync_testkit::Violation>(())
427 /// ```
428 pub async fn convergent_projection_cannot_observe_local_position<F>(
429 open: impl AsyncFn() -> F,
430 ) -> Result<RuleOutcome, Violation>
431 where
432 F: ConvergenceFixture,
433 F::Projection: ConvergentProjection,
434 {
435 const CLAUSE: &str = "SY-21";
436 let fixture = open().await;
437 let [dense, offset] = read_models_numbered_twice(&fixture, CLAUSE).await?;
438 ensure(dense == offset, CLAUSE, || {
439 format!(
440 "a projection declared convergent committed {} over the arrivals numbered \
441 densely and {} over the same arrivals numbered from elsewhere with gaps; its \
442 answer depends on where this replica numbered the events",
443 shown(&dense),
444 shown(&offset)
445 )
446 })?;
447 Ok(RuleOutcome::Ran)
448 }
449
450 /// **SY-22.** A non-convergent projection is left out of the convergence
451 /// check, not failed by it.
452 ///
453 /// Two halves. The exclusion is
454 /// [`convergent_projection_is_interleaving_independent`]'s where-clause:
455 /// a fixture over [`CostLayers`](crate::CostLayers), which makes no
456 /// declaration, does not compile into it. And the exclusion is needed:
457 /// this rule runs cost layers through the same machinery the check uses,
458 /// and requires the two read models to **differ**, beside
459 /// [`StockOnHand`](crate::StockOnHand) over the same events, which must
460 /// agree. Without the exclusion, an honest projection is failed.
461 ///
462 /// Rejects a convergence check with no exclusion, which fails cost layers;
463 /// and a check that does not really reorder — one interleaving replayed
464 /// twice — under which cost layers would agree with itself and every
465 /// projection would pass. If cost layers is ever expressed convergently,
466 /// this rule fails too, and that is SY-22's own falsifier firing.
467 ///
468 /// # Errors
469 ///
470 /// A [`Violation`] of SY-22 if stock on hand diverges, if cost layers
471 /// does not, or if either run fails.
472 ///
473 /// # The exclusion, compiled
474 ///
475 /// A fixture over an undeclared projection is a [`ConvergenceFixture`],
476 /// and every bound but the check's still takes it. This is the control:
477 ///
478 /// ```
479 /// use happenstance_sync_testkit::{ConvergenceFixture, CostLayersFixture};
480 ///
481 /// fn any_case<F: ConvergenceFixture>(_: &F) {}
482 /// any_case(&CostLayersFixture::new());
483 /// ```
484 ///
485 /// The check is not one of them. Rustdoc 1.97.1 does not check the error
486 /// code on a `compile_fail` fence (RS-62-1), so the `E0277` is a statement
487 /// of intent. Two controls keep the fence from passing on a typo: the
488 /// `any_case` control above, which names the same fixture, and the SY-20
489 /// rule's own example, which makes the same call in the same shape:
490 ///
491 /// ```compile_fail,E0277
492 /// use happenstance_sync_testkit::{CostLayersFixture, convergence_rules};
493 ///
494 /// let check = convergence_rules::convergent_projection_is_interleaving_independent(
495 /// async || CostLayersFixture::new(),
496 /// );
497 /// drop(check);
498 /// ```
499 pub async fn non_convergent_projections_are_excluded_not_failed()
500 -> Result<RuleOutcome, Violation> {
501 const CLAUSE: &str = "SY-22";
502 let [one_first, two_first] = read_models(&StockOnHandFixture::new(), CLAUSE).await?;
503 ensure(one_first == two_first, CLAUSE, || {
504 format!(
505 "stock on hand, two sums, committed {} and {} under the two interleavings; the \
506 check differs on something other than arrival order, so it cannot tell a \
507 convergent fold from one that is not",
508 shown(&one_first),
509 shown(&two_first)
510 )
511 })?;
512 let [one_first, two_first] = read_models(&CostLayersFixture::new(), CLAUSE).await?;
513 ensure(one_first != two_first, CLAUSE, || {
514 format!(
515 "cost layers committed {} under both interleavings. Either the check no longer \
516 reorders the origins, and SY-20's rule passes any fold, or FIFO cost layers \
517 has been expressed convergently, which is SY-22's falsifier",
518 shown(&one_first)
519 )
520 })?;
521 Ok(RuleOutcome::Ran)
522 }
523}