tawasuyu/llimphi

1// =============================================================================
2//  grafo-nav — el contrato del DAG navegable, una sola vez (PLAN-GRAFO F1)
3// -----------------------------------------------------------------------------
4//  Un DAG cualquiera del repo (Mónadas, commits, celdas, mensajes) se vuelve
5//  navegable y gestionable implementando [`GrafoNavegable`]: dice sus nodos, sus
6//  aristas dirigidas `(padre → hijo)`, y qué [`Verbo`]s permite para la
7//  selección. Todo lo estructural — raíces, cabezas, cono, bifurcación — se
8//  deriva solo, puro, de las aristas.
9//
10//  El cockpit compartido (`llimphi-widget-navigator::cockpit_grafo_view`) toma
11//  cualquier `impl GrafoNavegable` y lo pinta con pan/zoom/selección y la paleta
12//  de verbos. Esta caja NO conoce la UI: sólo topología y vocabulario.
13//
14//  Convención de dirección de arista: `(from, to)` = `ancestro → descendiente`
15//  (padre → hijo). Así una **raíz** no tiene aristas entrantes (commit inicial)
16//  y una **cabeza** no tiene salientes (tip / mensaje sin respuesta) — coincide
17//  con `minga::GrafoCommits` y con el layout por rango del nodegraph.
18// =============================================================================
19
20#![no_std]
21#![forbid(unsafe_code)]
22
23extern crate alloc;
24
25use alloc::string::String;
26use alloc::vec::Vec;
27
28/// Identificador opaco de un nodo. Lo asigna el dominio (un índice a su propio
29/// mapa `id → CommitHash | MensajeId | MonadId`); el visor no lo interpreta.
30pub type NodoId = u64;
31
32/// Estado **de dominio** de un nodo — lo que la topología no puede deducir sola
33/// (a diferencia de raíz/cabeza, que sí se derivan de las aristas). Elige tinte
34/// y matiza los verbos.
35#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36pub enum Rol {
37    /// Nodo interior corriente.
38    Normal,
39    /// El nodo "activo": HEAD actual, celda en foco, último leído.
40    Activo,
41    /// Marcado como desactualizado por el dominio (hija stale de pluma, celda
42    /// con dependencia cambiada) — candidato a *restablecer*.
43    Stale,
44    /// Inalcanzable / colgante — candidato a *cercenar*.
45    Huerfano,
46}
47
48impl Default for Rol {
49    fn default() -> Self {
50        Rol::Normal
51    }
52}
53
54/// Un nodo del grafo: id opaco, etiqueta legible y su rol de dominio.
55#[derive(Debug, Clone, PartialEq, Eq)]
56pub struct Nodo {
57    pub id: NodoId,
58    pub etiqueta: String,
59    pub rol: Rol,
60}
61
62impl Nodo {
63    pub fn new(id: NodoId, etiqueta: impl Into<String>, rol: Rol) -> Self {
64        Self { id, etiqueta: etiqueta.into(), rol }
65    }
66}
67
68/// Los cuatro verbos compartidos. El mismo vocabulario para todos los dominios;
69/// cada uno los implementa a su manera (minga: checkout/gc/fusionar; ayni: merge
70/// de cabezas; notebook: run_from / borrar celda).
71#[derive(Debug, Clone, Copy, PartialEq, Eq)]
72pub enum Verbo {
73    /// Enfocar / ir al nodo (navegación pura, siempre disponible).
74    Saltar,
75    /// Mover el puntero/HEAD a este nodo (reset, checkout, re-ejecutar cono).
76    Restablecer,
77    /// Podar este nodo y su cono descendente (gc, borrar celda + dependientes).
78    Cercenar,
79    /// Unir cabezas divergentes (fusionar commits, merge de mensajes/CRDT).
80    Conciliar,
81}
82
83impl Verbo {
84    /// Rótulo para el menú contextual del cockpit.
85    pub fn etiqueta(self) -> &'static str {
86        match self {
87            Verbo::Saltar => "Saltar",
88            Verbo::Restablecer => "Restablecer",
89            Verbo::Cercenar => "Cercenar",
90            Verbo::Conciliar => "Conciliar",
91        }
92    }
93
94    /// Los cuatro, en orden canónico (de menos a más destructivo).
95    pub const TODOS: [Verbo; 4] = [
96        Verbo::Saltar,
97        Verbo::Restablecer,
98        Verbo::Cercenar,
99        Verbo::Conciliar,
100    ];
101}
102
103/// El contrato. Un dominio lo implementa sobre su modelo ya existente; las
104/// derivadas estructurales vienen gratis.
105pub trait GrafoNavegable {
106    /// Los nodos a mostrar.
107    fn nodos(&self) -> Vec<Nodo>;
108
109    /// Aristas dirigidas `(ancestro, descendiente)`.
110    fn aristas(&self) -> Vec<(NodoId, NodoId)>;
111
112    /// Verbos permitidos para la selección (o para el grafo entero si `None`).
113    /// El dominio decide la política: p.ej. `Conciliar` sólo si hay bifurcación,
114    /// `Restablecer` sólo sobre un nodo histórico, `Cercenar` sólo lo inalcanzable.
115    fn acciones(&self, seleccion: Option<NodoId>) -> Vec<Verbo>;
116
117    // ── derivadas puras (default; el dominio rara vez las sobreescribe) ──────
118
119    /// Raíces: nodos sin aristas entrantes (ancestros de todo).
120    fn raices(&self) -> Vec<NodoId> {
121        let edges = self.aristas();
122        self.nodos()
123            .into_iter()
124            .map(|n| n.id)
125            .filter(|id| !edges.iter().any(|(_, t)| t == id))
126            .collect()
127    }
128
129    /// Cabezas: nodos sin aristas salientes (los tips / lo más nuevo).
130    fn cabezas(&self) -> Vec<NodoId> {
131        let edges = self.aristas();
132        self.nodos()
133            .into_iter()
134            .map(|n| n.id)
135            .filter(|id| !edges.iter().any(|(f, _)| f == id))
136            .collect()
137    }
138
139    /// `true` si el grafo **bifurcó** (más de una cabeza) — condición para que
140    /// *conciliar* tenga sentido.
141    fn bifurcado(&self) -> bool {
142        self.cabezas().len() > 1
143    }
144
145    /// Cono **ascendente** de `id`: sus ancestros, incluido `id`.
146    fn cono_ascendente(&self, id: NodoId) -> Vec<NodoId> {
147        cono(&self.aristas(), id, Sentido::Arriba)
148    }
149
150    /// Cono **descendente** de `id`: sus descendientes, incluido `id` (lo que se
151    /// arrastra al *cercenar*).
152    fn cono_descendente(&self, id: NodoId) -> Vec<NodoId> {
153        cono(&self.aristas(), id, Sentido::Abajo)
154    }
155}
156
157#[derive(Clone, Copy)]
158enum Sentido {
159    Arriba,
160    Abajo,
161}
162
163/// BFS del cono en un sentido, con dedup por `Vec::contains` (sin `std`; apto
164/// para los grafos modestos que maneja un cockpit interactivo).
165fn cono(edges: &[(NodoId, NodoId)], id: NodoId, sentido: Sentido) -> Vec<NodoId> {
166    let mut visto: Vec<NodoId> = Vec::new();
167    visto.push(id);
168    let mut i = 0;
169    while i < visto.len() {
170        let cur = visto[i];
171        i += 1;
172        for &(f, t) in edges {
173            let vecino = match sentido {
174                Sentido::Arriba if t == cur => Some(f),
175                Sentido::Abajo if f == cur => Some(t),
176                _ => None,
177            };
178            if let Some(v) = vecino {
179                if !visto.contains(&v) {
180                    visto.push(v);
181                }
182            }
183        }
184    }
185    visto.sort_unstable();
186    visto
187}
188
189#[cfg(test)]
190mod tests {
191    use super::*;
192    use alloc::vec;
193
194    /// Grafo sintético en diamante con una segunda cabeza suelta:
195    ///   1 → 2, 1 → 3, 2 → 4, 3 → 4   (diamante),   1 → 5   (cabeza extra)
196    /// Raíz: 1.  Cabezas: 4 y 5  ⇒ bifurcado.
197    struct Diamante;
198    impl GrafoNavegable for Diamante {
199        fn nodos(&self) -> Vec<Nodo> {
200            vec![
201                Nodo::new(1, "raíz", Rol::Normal),
202                Nodo::new(2, "A", Rol::Normal),
203                Nodo::new(3, "B", Rol::Normal),
204                Nodo::new(4, "merge", Rol::Activo),
205                Nodo::new(5, "suelto", Rol::Huerfano),
206            ]
207        }
208        fn aristas(&self) -> Vec<(NodoId, NodoId)> {
209            vec![(1, 2), (1, 3), (2, 4), (3, 4), (1, 5)]
210        }
211        fn acciones(&self, seleccion: Option<NodoId>) -> Vec<Verbo> {
212            let mut v = vec![Verbo::Saltar];
213            if seleccion.is_some() {
214                v.push(Verbo::Cercenar);
215            }
216            if self.bifurcado() {
217                v.push(Verbo::Conciliar);
218            }
219            v
220        }
221    }
222
223    #[test]
224    fn raices_y_cabezas_derivadas() {
225        let g = Diamante;
226        assert_eq!(g.raices(), vec![1]);
227        let mut cab = g.cabezas();
228        cab.sort_unstable();
229        assert_eq!(cab, vec![4, 5]);
230        assert!(g.bifurcado(), "dos cabezas ⇒ bifurcado");
231    }
232
233    #[test]
234    fn conos_ascendente_y_descendente() {
235        let g = Diamante;
236        assert_eq!(g.cono_ascendente(4), vec![1, 2, 3, 4]);
237        assert_eq!(g.cono_descendente(1), vec![1, 2, 3, 4, 5]);
238        // una hoja sólo se contiene a sí misma hacia abajo.
239        assert_eq!(g.cono_descendente(4), vec![4]);
240        // una raíz sólo se contiene a sí misma hacia arriba.
241        assert_eq!(g.cono_ascendente(1), vec![1]);
242    }
243
244    #[test]
245    fn acciones_dependen_de_la_seleccion() {
246        let g = Diamante;
247        // Sin selección: no ofrece cercenar.
248        let sin = g.acciones(None);
249        assert!(sin.contains(&Verbo::Saltar));
250        assert!(!sin.contains(&Verbo::Cercenar));
251        assert!(sin.contains(&Verbo::Conciliar)); // bifurcado
252        // Con selección: aparece cercenar.
253        assert!(g.acciones(Some(4)).contains(&Verbo::Cercenar));
254    }
255
256    #[test]
257    fn verbo_etiquetas_y_orden() {
258        assert_eq!(Verbo::TODOS.len(), 4);
259        assert_eq!(Verbo::Saltar.etiqueta(), "Saltar");
260        assert_eq!(Verbo::Conciliar.etiqueta(), "Conciliar");
261    }
262}