tawasuyu/hifas

1//! `native` — retículo derivado del merge del CRDT (T8a, Addendum §B).
2//!
3//! Mata la circularidad de T5–T7: el orden **no** se pone a mano ni se lee de la
4//! etiqueta monótono/reset, se deriva mecánicamente de la propia fusión:
5//! ```text
6//!   join(a, b) := merge_del_CRDT(a, b)     // la fusión que el tipo YA implementa
7//!   a ≤ b      := ( merge(a, b) == b )     // orden inducido por el merge
8//! ```
9//! Con esta regla es imposible filtrar la respuesta de CALM. La difusión es una
10//! **propagación de joins** (gossip) al punto fijo: el merge de cada componente
11//! conexa. Sin invariante, un CRDT siempre reconcilia → corre libre (T8c añade
12//! el invariante que sí puede forzar coordinación).
13
14use crate::cell::{Cell, GCounter, ResettableRegister};
15
16/// Un estado con una fusión CRDT y el orden que ésta induce.
17pub trait Merge: Clone + PartialEq {
18    /// La fusión del CRDT (conmutativa, asociativa, idempotente).
19    fn merge(&self, other: &Self) -> Self;
20
21    /// Orden inducido por el merge: `a ≤ b ⟺ merge(a, b) == b`.
22    fn leq(&self, other: &Self) -> bool {
23        &self.merge(other) == other
24    }
25}
26
27// Los CRDT del MVP ya traen su merge en `Cell::join`; lo reutilizamos tal cual.
28// (Usamos SOLO la fusión, nunca `is_monotone`: ahí estaba la circularidad.)
29impl Merge for GCounter {
30    fn merge(&self, other: &Self) -> Self {
31        Cell::join(self, other)
32    }
33}
34
35impl Merge for ResettableRegister {
36    fn merge(&self, other: &Self) -> Self {
37        Cell::join(self, other)
38    }
39}
40
41/// Propaga joins por las aristas hasta el punto fijo (Kleene ascendente sobre el
42/// orden del merge). El resultado en cada vértice es el merge de su componente
43/// conexa. Converge para estados de altura finita.
44pub fn reconcile<M: Merge>(edges: &[(usize, usize)], seed: &[M]) -> Vec<M> {
45    let mut x = seed.to_vec();
46    let mut changed = true;
47    let mut guard = 0usize;
48    while changed {
49        changed = false;
50        for &(a, b) in edges {
51            let m = x[a].merge(&x[b]);
52            if x[a] != m {
53                x[a] = m.clone();
54                changed = true;
55            }
56            if x[b] != m {
57                x[b] = m;
58                changed = true;
59            }
60        }
61        guard += 1;
62        assert!(guard <= 100_000, "reconcile no convergió (¿merge no idempotente?)");
63    }
64    x
65}
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn orden_de_gcounter_es_componente_a_componente() {
73        let a = GCounter { slots: vec![3, 0] };
74        let b = GCounter { slots: vec![1, 5] };
75        assert!(!a.leq(&b) && !b.leq(&a), "incomparables por casillas cruzadas");
76        let c = GCounter { slots: vec![3, 5] };
77        assert!(a.leq(&c) && b.leq(&c), "el join domina a ambos");
78    }
79
80    #[test]
81    fn orden_de_lww_es_una_cadena() {
82        // El registro LWW (reset = mayor generación) es una CADENA: todo par
83        // es comparable. Por eso su difusión NUNCA colapsa → corre libre.
84        let viejo = ResettableRegister::new(10); // gen 0, value 10
85        let mut reset = viejo.clone();
86        reset.reset(0); // gen 1, value 0 (valor MENOR, pero generación mayor)
87        // Comparables pese a que el valor baja: viejo ≤ reset (gana la generación).
88        assert!(viejo.leq(&reset), "el reset domina en el orden del merge");
89        assert!(!reset.leq(&viejo));
90    }
91
92    #[test]
93    fn reconcile_lww_llega_al_maximo_de_la_cadena() {
94        // Tres réplicas en ciclo, una reseteó. Bajo el orden nativo reconcilian
95        // al elemento máximo de la cadena; sin invariante, no hay obstrucción.
96        let seed = vec![
97            ResettableRegister::new(10),
98            ResettableRegister::new(10),
99            {
100                let mut r = ResettableRegister::new(10);
101                r.reset(7);
102                r
103            },
104        ];
105        let fix = reconcile(&[(0, 1), (1, 2), (2, 0)], &seed);
106        // Todos convergen al mismo estado (el máximo): gen 1, value 7.
107        assert!(fix.iter().all(|s| *s == fix[0]), "reconcilia a un estado común");
108        assert_eq!(fix[0].generation, 1);
109    }
110}