tawasuyu/brahman

1//! `fana-graph` — el grafo narrativo (DAG de `NarrativeAtom`s).
2//!
3//! Mantiene los átomos + una adjacency list `dependencia → dependientes`.
4//! Cuando un átomo muta, [`NarrativeGraph::propagate_mutation`] marca en
5//! cascada a todo descendiente como `PendingEvaluation` — la "onda de
6//! choque lógica" de la spec. Agnóstico de UI: devuelve los ids
7//! afectados; el front-end decide cuándo re-renderizar.
8
9#![forbid(unsafe_code)]
10
11use fana_core::{CoherenceState, NarrativeAtom};
12use std::collections::{HashMap, HashSet, VecDeque};
13use uuid::Uuid;
14
15/// El documento como grafo dirigido acíclico de átomos narrativos.
16#[derive(Debug, Default)]
17pub struct NarrativeGraph {
18    nodes: HashMap<Uuid, NarrativeAtom>,
19    /// `dependencia → [átomos que dependen de ella]`.
20    adjacency: HashMap<Uuid, Vec<Uuid>>,
21}
22
23impl NarrativeGraph {
24    pub fn new() -> Self {
25        Self::default()
26    }
27
28    pub fn len(&self) -> usize {
29        self.nodes.len()
30    }
31
32    pub fn is_empty(&self) -> bool {
33        self.nodes.is_empty()
34    }
35
36    pub fn contains(&self, id: Uuid) -> bool {
37        self.nodes.contains_key(&id)
38    }
39
40    pub fn get(&self, id: Uuid) -> Option<&NarrativeAtom> {
41        self.nodes.get(&id)
42    }
43
44    pub fn get_mut(&mut self, id: Uuid) -> Option<&mut NarrativeAtom> {
45        self.nodes.get_mut(&id)
46    }
47
48    /// Itera todos los átomos del grafo (orden no determinista).
49    pub fn atoms(&self) -> impl Iterator<Item = &NarrativeAtom> {
50        self.nodes.values()
51    }
52
53    /// Construye un grafo desde una colección de átomos.
54    pub fn from_atoms(atoms: impl IntoIterator<Item = NarrativeAtom>) -> Self {
55        let mut g = Self::new();
56        for a in atoms {
57            g.insert(a);
58        }
59        g
60    }
61
62    /// Inserta un átomo y conecta las aristas desde sus dependencias.
63    pub fn insert(&mut self, atom: NarrativeAtom) {
64        let id = atom.id;
65        for &dep in &atom.dependencies {
66            let children = self.adjacency.entry(dep).or_default();
67            if !children.contains(&id) {
68                children.push(id);
69            }
70        }
71        self.nodes.insert(id, atom);
72    }
73
74    /// Dependientes directos de `id`.
75    pub fn dependents(&self, id: Uuid) -> &[Uuid] {
76        self.adjacency.get(&id).map(|v| v.as_slice()).unwrap_or(&[])
77    }
78
79    /// Propaga una mutación: marca `PendingEvaluation` en TODO descendiente
80    /// transitivo de `origin` (BFS sobre la adjacency). Devuelve los ids
81    /// afectados — el caller (front-end) decide cuándo re-renderizar.
82    ///
83    /// `origin` mismo no se marca (es la fuente; ya se sabe que cambió).
84    pub fn propagate_mutation(&mut self, origin: Uuid) -> Vec<Uuid> {
85        let mut affected = Vec::new();
86        let mut seen: HashSet<Uuid> = HashSet::new();
87        let mut queue: VecDeque<Uuid> = VecDeque::new();
88        queue.push_back(origin);
89        seen.insert(origin);
90
91        while let Some(current) = queue.pop_front() {
92            let children: Vec<Uuid> = self
93                .adjacency
94                .get(&current)
95                .cloned()
96                .unwrap_or_default();
97            for child in children {
98                if seen.insert(child) {
99                    if let Some(node) = self.nodes.get_mut(&child) {
100                        node.coherence = CoherenceState::PendingEvaluation;
101                    }
102                    affected.push(child);
103                    queue.push_back(child);
104                }
105            }
106        }
107        affected
108    }
109
110    /// Orden topológico de los átomos (dependencias antes que dependientes).
111    /// `None` si el grafo tiene un ciclo (no es un DAG válido).
112    pub fn topological_order(&self) -> Option<Vec<Uuid>> {
113        let mut indeg: HashMap<Uuid, usize> = self.nodes.keys().map(|&k| (k, 0)).collect();
114        for atom in self.nodes.values() {
115            for &dep in &atom.dependencies {
116                if self.nodes.contains_key(&dep) {
117                    *indeg.entry(atom.id).or_insert(0) += 1;
118                }
119            }
120        }
121        let mut queue: VecDeque<Uuid> =
122            indeg.iter().filter(|(_, &d)| d == 0).map(|(&k, _)| k).collect();
123        let mut order = Vec::with_capacity(self.nodes.len());
124        while let Some(u) = queue.pop_front() {
125            order.push(u);
126            for &child in self.dependents(u) {
127                if let Some(d) = indeg.get_mut(&child) {
128                    *d -= 1;
129                    if *d == 0 {
130                        queue.push_back(child);
131                    }
132                }
133            }
134        }
135        if order.len() == self.nodes.len() {
136            Some(order)
137        } else {
138            None // quedó un ciclo
139        }
140    }
141}
142
143#[cfg(test)]
144mod tests {
145    use super::*;
146
147    /// Construye una cadena a → b → c y devuelve sus ids.
148    fn chain() -> (NarrativeGraph, Uuid, Uuid, Uuid) {
149        let mut g = NarrativeGraph::new();
150        let a = NarrativeAtom::new("a", "main");
151        let ( a_id,) = (a.id,);
152        let b = NarrativeAtom::new("b", "main").depends_on(a_id);
153        let b_id = b.id;
154        let c = NarrativeAtom::new("c", "main").depends_on(b_id);
155        let c_id = c.id;
156        g.insert(a);
157        g.insert(b);
158        g.insert(c);
159        (g, a_id, b_id, c_id)
160    }
161
162    #[test]
163    fn insert_wires_adjacency() {
164        let (g, a, b, c) = chain();
165        assert_eq!(g.len(), 3);
166        assert_eq!(g.dependents(a), &[b]);
167        assert_eq!(g.dependents(b), &[c]);
168        assert!(g.dependents(c).is_empty());
169    }
170
171    #[test]
172    fn propagate_marks_all_descendants_pending() {
173        let (mut g, a, b, c) = chain();
174        let affected = g.propagate_mutation(a);
175        assert_eq!(affected.len(), 2);
176        assert!(affected.contains(&b) && affected.contains(&c));
177        assert_eq!(g.get(b).unwrap().coherence, CoherenceState::PendingEvaluation);
178        assert_eq!(g.get(c).unwrap().coherence, CoherenceState::PendingEvaluation);
179        // El origen NO se marca.
180        assert_eq!(g.get(a).unwrap().coherence, CoherenceState::Valid);
181    }
182
183    #[test]
184    fn propagate_from_leaf_affects_nothing() {
185        let (mut g, _a, _b, c) = chain();
186        assert!(g.propagate_mutation(c).is_empty());
187    }
188
189    #[test]
190    fn topological_order_respects_dependencies() {
191        let (g, a, b, c) = chain();
192        let order = g.topological_order().expect("es un DAG");
193        let pos = |id: Uuid| order.iter().position(|&x| x == id).unwrap();
194        assert!(pos(a) < pos(b));
195        assert!(pos(b) < pos(c));
196    }
197
198    #[test]
199    fn cycle_has_no_topological_order() {
200        // a depende de b, b depende de a.
201        let mut g = NarrativeGraph::new();
202        let a = NarrativeAtom::new("a", "main");
203        let b = NarrativeAtom::new("b", "main");
204        let (a_id, b_id) = (a.id, b.id);
205        let a = a.depends_on(b_id);
206        let b = b.depends_on(a_id);
207        g.insert(a);
208        g.insert(b);
209        assert!(g.topological_order().is_none());
210    }
211}