Skip to main content

aria_engine_core/
graph.rs

1//! Experience/thought graph `G = (V, E, ℳ)` — 𝔸3, and the atomic mutation
2//! alphabet ℙ3/𝕃6 that is the only sanctioned way to change it.
3//!
4//! # v2 (plan WS3)
5//!
6//! - **Typed** nodes and edges (spec §5.3) instead of optional strings, with
7//!   `Custom` escapes so no ingestion format is locked out.
8//! - **`u64` ids** from a monotone counter instead of formatted strings: an
9//!   arena identity that a vector index can key on directly.
10//! - **Deterministic containers.** `BTreeMap`/`BTreeSet` rather than
11//!   `HashMap`/`HashSet`. This is not a taste choice: std's hashers are
12//!   randomly seeded *per process*, so any policy that indexed
13//!   `nodes.keys()` — as `SimGraphBackend`'s `one_edit` did — selected a
14//!   different node in different processes. Ordered containers make iteration
15//!   order, and therefore every trace, reproducible by construction.
16//! - **[`GraphOp`] + [`UndoOp`]**: mutations are atomic ops that record a
17//!   snapshot-based undo entry, so a failed invariant check rolls the graph
18//!   back exactly (𝕃6) without cloning the whole graph per step, and without
19//!   unwinding — `panic = "abort"` is set in release, so rollback must be
20//!   explicit data, never `catch_unwind`.
21//!
22//! Inv3's meaning is unchanged: every edge connects existing nodes and every
23//! node carries a finite `d`-dimensional embedding in 𝒵.
24
25use serde::de::{self, Deserializer, Visitor};
26use serde::{Deserialize, Serialize, Serializer};
27use std::collections::{BTreeMap, BTreeSet};
28use std::fmt;
29
30/// Arena identity of a node. Monotone, never reused within a graph.
31pub type NodeId = u64;
32
33/// Node types of the typed experience graph (spec §5.3).
34#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
35pub enum NodeType {
36    /// Something observed — the default for latents absorbed by Match.
37    #[default]
38    Observation,
39    /// A proposed explanation.
40    Hypothesis,
41    /// An action taken or planned.
42    Action,
43    /// A goal or target state.
44    Goal,
45    /// A checkpoint recording that invariants held.
46    InvariantCheckpoint,
47    /// Any type an ingestion format needs that the spec does not name.
48    Custom(String),
49}
50
51impl NodeType {
52    /// Wire name, and the key of the legacy alias table.
53    pub fn as_str(&self) -> &str {
54        match self {
55            NodeType::Observation => "observation",
56            NodeType::Hypothesis => "hypothesis",
57            NodeType::Action => "action",
58            NodeType::Goal => "goal",
59            NodeType::InvariantCheckpoint => "invariant_checkpoint",
60            NodeType::Custom(s) => s,
61        }
62    }
63
64    /// Parse a wire or legacy name.
65    ///
66    /// # Legacy alias table (plan WS3)
67    ///
68    /// | stored value | v2 type |
69    /// |---|---|
70    /// | `"latent"` (v0.1.0 Match) | [`NodeType::Observation`] |
71    /// | `"observation"` … `"invariant_checkpoint"` | the named variant |
72    /// | anything else | [`NodeType::Custom`] |
73    ///
74    /// Unknown strings become `Custom` rather than an error: a graph that
75    /// round-trips through an older or newer writer must still load, because
76    /// refusing to load is a worse failure than carrying an opaque label.
77    pub fn from_wire(s: &str) -> Self {
78        match s {
79            // v0.1.0 wrote every Match-absorbed latent as "latent".
80            "latent" | "observation" => NodeType::Observation,
81            "hypothesis" => NodeType::Hypothesis,
82            "action" => NodeType::Action,
83            "goal" => NodeType::Goal,
84            "invariant_checkpoint" => NodeType::InvariantCheckpoint,
85            other => NodeType::Custom(other.to_string()),
86        }
87    }
88}
89
90/// Edge types of the typed experience graph (spec §5.3).
91#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
92pub enum EdgeType {
93    /// Temporal-causal precedence — the default morphism Match lays down.
94    #[default]
95    CausallyPrecedes,
96    /// The endpoints disagree.
97    Contradicts,
98    /// The target refines the source.
99    Refines,
100    /// Plain temporal succession.
101    TemporalNext,
102    /// Any relation an ingestion format needs that the spec does not name.
103    Custom(String),
104}
105
106impl EdgeType {
107    /// Wire name, and the key of the legacy alias table.
108    pub fn as_str(&self) -> &str {
109        match self {
110            EdgeType::CausallyPrecedes => "causally_precedes",
111            EdgeType::Contradicts => "contradicts",
112            EdgeType::Refines => "refines",
113            EdgeType::TemporalNext => "temporal_next",
114            EdgeType::Custom(s) => s,
115        }
116    }
117
118    /// Parse a wire or legacy name. `"morph"` is v0.1.0's only edge label and
119    /// maps to [`EdgeType::CausallyPrecedes`]; unknown strings become `Custom`.
120    pub fn from_wire(s: &str) -> Self {
121        match s {
122            "morph" | "causally_precedes" => EdgeType::CausallyPrecedes,
123            "contradicts" => EdgeType::Contradicts,
124            "refines" => EdgeType::Refines,
125            "temporal_next" => EdgeType::TemporalNext,
126            other => EdgeType::Custom(other.to_string()),
127        }
128    }
129}
130
131/// Serialize both type enums as plain strings so the wire format stays
132/// human-readable and the legacy alias table above is all that a reader needs.
133macro_rules! string_serde {
134    ($t:ty, $expecting:literal) => {
135        impl Serialize for $t {
136            fn serialize<S: Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
137                s.serialize_str(self.as_str())
138            }
139        }
140
141        impl<'de> Deserialize<'de> for $t {
142            fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
143                struct V;
144                impl Visitor<'_> for V {
145                    type Value = $t;
146                    fn expecting(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
147                        f.write_str($expecting)
148                    }
149                    fn visit_str<E: de::Error>(self, v: &str) -> Result<$t, E> {
150                        Ok(<$t>::from_wire(v))
151                    }
152                }
153                d.deserialize_str(V)
154            }
155        }
156    };
157}
158
159string_serde!(NodeType, "a node type name");
160string_serde!(EdgeType, "an edge type name");
161
162/// A node of the experience graph: a typed, timestamped point of 𝒵.
163#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
164pub struct GraphNode {
165    /// Arena identity.
166    pub id: NodeId,
167    /// Embedding ℳ(v) ∈ 𝒵. Inv3 requires `len == latent_dim`, all finite.
168    pub embedding: Vec<f64>,
169    /// Typed role (spec §5.3).
170    #[serde(default)]
171    pub node_type: NodeType,
172    /// Discrete clock value `t` when this node was last written.
173    #[serde(default)]
174    pub timestamp: u64,
175}
176
177/// A typed directed edge — a morphism of the experience graph.
178#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
179pub struct GraphEdge {
180    /// Source node.
181    pub from: NodeId,
182    /// Target node.
183    pub to: NodeId,
184    /// Typed relation.
185    pub edge_type: EdgeType,
186}
187
188/// Experience/thought graph `G` — 𝔸3. Only Match mutates it (FORMAL_SPEC §6.3).
189#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
190pub struct Graph {
191    /// Nodes by id. Ordered for reproducible iteration.
192    ///
193    /// Direct mutation bypasses the [`GraphOp`] journal: use it in tests (to
194    /// build corrupt states that Inv3 must reject) and in deserialization,
195    /// never in the engine.
196    pub nodes: BTreeMap<NodeId, GraphNode>,
197    /// Typed edges. Ordered for reproducible iteration; a set, so `AddEdge` is
198    /// idempotent by construction (ℙ3).
199    pub edges: BTreeSet<GraphEdge>,
200    /// Next id to hand out. Monotone: ids are never reused, so a stale index
201    /// entry can never be confused with a fresh node.
202    #[serde(default)]
203    next_id: NodeId,
204}
205
206/// Why an atomic graph op was refused *before* any mutation happened (𝕃6).
207#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
208pub enum GraphOpError {
209    /// An op referenced a node that is not in `V`.
210    #[error("graph op references missing node {0}")]
211    MissingNode(NodeId),
212    /// `AddNode` collided with a different existing node.
213    #[error("node {0} already exists with different content")]
214    DuplicateNode(NodeId),
215    /// Embedding dimension violates Inv3.
216    #[error("node {id}: embedding has dim {got}, expected {want}")]
217    Dim {
218        /// Offending node.
219        id: NodeId,
220        /// Dimension supplied.
221        got: usize,
222        /// Dimension required (`latent_dim`).
223        want: usize,
224    },
225    /// Embedding contains NaN/±∞ — not a point of 𝒵.
226    #[error("node {0}: embedding contains a non-finite component")]
227    NonFinite(NodeId),
228    /// `MergeNodes` needs two distinct nodes.
229    #[error("MergeNodes requires distinct nodes, got {0} twice")]
230    SelfMerge(NodeId),
231}
232
233/// The atomic mutation alphabet — exactly ℙ3's elementary edits plus the
234/// 𝕃3 merge. Every op is idempotent and integrity-checked before commit.
235#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
236pub enum GraphOp {
237    /// Insert a typed node.
238    AddNode {
239        /// Arena identity (allocate with [`Graph::next_id`]).
240        id: NodeId,
241        /// Typed role.
242        ntype: NodeType,
243        /// Embedding ℳ(v).
244        emb: Vec<f64>,
245        /// Clock value.
246        ts: u64,
247    },
248    /// Remove a node and every incident edge (no dangling edges — 𝕃6).
249    DeleteNode {
250        /// Node to remove.
251        id: NodeId,
252    },
253    /// Insert a typed edge between existing nodes.
254    AddEdge {
255        /// Source.
256        from: NodeId,
257        /// Target.
258        to: NodeId,
259        /// Relation.
260        etype: EdgeType,
261    },
262    /// Remove a typed edge.
263    DeleteEdge {
264        /// Source.
265        from: NodeId,
266        /// Target.
267        to: NodeId,
268        /// Relation.
269        etype: EdgeType,
270    },
271    /// Replace a node's embedding (ℙ3 relabel).
272    RelabelNode {
273        /// Node to relabel.
274        id: NodeId,
275        /// New embedding.
276        emb: Vec<f64>,
277    },
278    /// Absorb `merged` into `keep`: re-point `merged`'s edges onto `keep`,
279    /// EMA-update `keep`'s embedding, then delete `merged` (𝕃3, spec §5.3).
280    MergeNodes {
281        /// Surviving node.
282        keep: NodeId,
283        /// Absorbed node.
284        merged: NodeId,
285    },
286}
287
288/// The exact pre-image needed to reverse one [`GraphOp`].
289///
290/// Snapshots, not inverse op names: a delete or a merge cannot be reconstructed
291/// from its arguments, so the journal carries the removed node, its incident
292/// edges, and the surviving node's overwritten embedding.
293#[derive(Debug, Clone, PartialEq)]
294pub enum UndoOp {
295    /// Reverse of `AddNode`.
296    DropNode(NodeId),
297    /// Reverse of `DeleteNode`.
298    RestoreNode {
299        /// The removed node, verbatim.
300        node: GraphNode,
301        /// Its incident edges, verbatim.
302        edges: Vec<GraphEdge>,
303    },
304    /// Reverse of `AddEdge`.
305    DropEdge(GraphEdge),
306    /// Reverse of `DeleteEdge`.
307    RestoreEdge(GraphEdge),
308    /// Reverse of `RelabelNode`.
309    RestoreEmbedding {
310        /// Node relabelled.
311        id: NodeId,
312        /// Its previous embedding.
313        emb: Vec<f64>,
314    },
315    /// Reverse of `MergeNodes`.
316    Unmerge {
317        /// The absorbed node, verbatim.
318        merged: GraphNode,
319        /// The absorbed node's incident edges, verbatim.
320        merged_edges: Vec<GraphEdge>,
321        /// The surviving node.
322        keep: NodeId,
323        /// The surviving node's embedding before the EMA update.
324        keep_emb: Vec<f64>,
325        /// The surviving node's timestamp before the merge.
326        keep_ts: u64,
327        /// Edges newly created by re-pointing (only these get removed).
328        rewired: Vec<GraphEdge>,
329    },
330    /// The op was already satisfied; nothing to reverse (idempotency).
331    Noop,
332}
333
334/// EMA weights for the merge embedding update — spec §5.3's normative Rust
335/// uses `*e = 0.9 * (*e) + 0.1 * (*c)`.
336const MERGE_EMA_KEEP: f64 = 0.9;
337const MERGE_EMA_NEW: f64 = 0.1;
338
339impl Graph {
340    /// An empty graph.
341    pub fn empty() -> Self {
342        Graph {
343            nodes: BTreeMap::new(),
344            edges: BTreeSet::new(),
345            next_id: 0,
346        }
347    }
348
349    /// A graph holding a single seed node.
350    pub fn seed(node: GraphNode) -> Self {
351        let mut g = Graph::empty();
352        g.next_id = node.id + 1;
353        g.nodes.insert(node.id, node);
354        g
355    }
356
357    /// `|V|`.
358    pub fn node_count(&self) -> usize {
359        self.nodes.len()
360    }
361
362    /// `|E|`.
363    pub fn edge_count(&self) -> usize {
364        self.edges.len()
365    }
366
367    /// `|G| = |V| + |E|`.
368    pub fn size(&self) -> usize {
369        self.node_count() + self.edge_count()
370    }
371
372    /// The next id this graph will hand out. Policies allocate from here so ids
373    /// stay monotone no matter who proposes the op.
374    pub fn next_id(&self) -> NodeId {
375        self.next_id
376    }
377
378    /// A node by id.
379    pub fn node(&self, id: NodeId) -> Option<&GraphNode> {
380        self.nodes.get(&id)
381    }
382
383    /// A node's embedding ℳ(v).
384    pub fn get_embedding(&self, id: NodeId) -> Option<&Vec<f64>> {
385        self.nodes.get(&id).map(|n| &n.embedding)
386    }
387
388    /// Edges incident to `id` in either direction.
389    pub fn incident(&self, id: NodeId) -> Vec<GraphEdge> {
390        self.edges
391            .iter()
392            .filter(|e| e.from == id || e.to == id)
393            .cloned()
394            .collect()
395    }
396
397    /// `GraphOK(G)` — Inv3.
398    ///
399    /// Every edge connects existing nodes, and every node carries a finite
400    /// `latent_dim`-dimensional embedding. Also checks the map key against the
401    /// node's own id, which direct field access could desync.
402    pub fn ok(&self, latent_dim: usize) -> bool {
403        for edge in &self.edges {
404            if !self.nodes.contains_key(&edge.from) || !self.nodes.contains_key(&edge.to) {
405                return false;
406            }
407        }
408        for (id, node) in &self.nodes {
409            if *id != node.id
410                || node.embedding.len() != latent_dim
411                || !node.embedding.iter().all(|v| v.is_finite())
412            {
413                return false;
414            }
415        }
416        true
417    }
418
419    /// Whether the directed structure is acyclic (Inv7 candidate gate).
420    ///
421    /// Kahn's algorithm: a DAG admits a topological order covering every node.
422    pub fn is_acyclic(&self) -> bool {
423        let mut indegree: BTreeMap<NodeId, usize> = self.nodes.keys().map(|&k| (k, 0)).collect();
424        let mut out: BTreeMap<NodeId, Vec<NodeId>> = BTreeMap::new();
425
426        for e in &self.edges {
427            // Dangling edges are Inv3's failure mode, not this one.
428            if !self.nodes.contains_key(&e.from) {
429                continue;
430            }
431            if let Some(d) = indegree.get_mut(&e.to) {
432                *d += 1;
433                out.entry(e.from).or_default().push(e.to);
434            }
435        }
436
437        let mut queue: Vec<NodeId> = indegree
438            .iter()
439            .filter(|(_, &d)| d == 0)
440            .map(|(&k, _)| k)
441            .collect();
442
443        let mut visited = 0usize;
444        while let Some(n) = queue.pop() {
445            visited += 1;
446            for &m in out.get(&n).into_iter().flatten() {
447                if let Some(d) = indegree.get_mut(&m) {
448                    *d -= 1;
449                    if *d == 0 {
450                        queue.push(m);
451                    }
452                }
453            }
454        }
455
456        visited == self.nodes.len()
457    }
458
459    /// Validate an embedding against Inv3 before it can enter `G`.
460    fn check_embedding(id: NodeId, emb: &[f64], latent_dim: usize) -> Result<(), GraphOpError> {
461        if emb.len() != latent_dim {
462            return Err(GraphOpError::Dim {
463                id,
464                got: emb.len(),
465                want: latent_dim,
466            });
467        }
468        if !emb.iter().all(|v| v.is_finite()) {
469            return Err(GraphOpError::NonFinite(id));
470        }
471        Ok(())
472    }
473
474    /// Apply one atomic op, returning the entry that reverses it.
475    ///
476    /// Integrity is checked *before* any mutation, so an `Err` leaves `G`
477    /// byte-identical and the returned journal stays a faithful pre-image (𝕃6).
478    pub fn apply(&mut self, op: &GraphOp, latent_dim: usize) -> Result<UndoOp, GraphOpError> {
479        match op {
480            GraphOp::AddNode { id, ntype, emb, ts } => {
481                self.apply_add_node(*id, ntype.clone(), emb, *ts, latent_dim)
482            }
483            GraphOp::DeleteNode { id } => Ok(self.apply_delete_node(*id)),
484            GraphOp::AddEdge { from, to, etype } => self.apply_add_edge(*from, *to, etype.clone()),
485            GraphOp::DeleteEdge { from, to, etype } => {
486                Ok(self.apply_delete_edge(*from, *to, etype.clone()))
487            }
488            GraphOp::RelabelNode { id, emb } => self.apply_relabel_node(*id, emb, latent_dim),
489            GraphOp::MergeNodes { keep, merged } => self.apply_merge_nodes(*keep, *merged),
490        }
491    }
492
493    fn apply_add_node(
494        &mut self,
495        id: NodeId,
496        ntype: NodeType,
497        emb: &[f64],
498        ts: u64,
499        latent_dim: usize,
500    ) -> Result<UndoOp, GraphOpError> {
501        Self::check_embedding(id, emb, latent_dim)?;
502        let candidate = GraphNode {
503            id,
504            embedding: emb.to_vec(),
505            node_type: ntype,
506            timestamp: ts,
507        };
508        if let Some(existing) = self.nodes.get(&id) {
509            // Idempotent when identical; a real collision is an error rather
510            // than a silent overwrite.
511            return if *existing == candidate {
512                Ok(UndoOp::Noop)
513            } else {
514                Err(GraphOpError::DuplicateNode(id))
515            };
516        }
517        self.nodes.insert(id, candidate);
518        self.next_id = self.next_id.max(id.saturating_add(1));
519        Ok(UndoOp::DropNode(id))
520    }
521
522    fn apply_delete_node(&mut self, id: NodeId) -> UndoOp {
523        let Some(node) = self.nodes.remove(&id) else {
524            return UndoOp::Noop;
525        };
526        let edges = self.incident(id);
527        for e in &edges {
528            self.edges.remove(e);
529        }
530        UndoOp::RestoreNode { node, edges }
531    }
532
533    fn apply_add_edge(
534        &mut self,
535        from: NodeId,
536        to: NodeId,
537        etype: EdgeType,
538    ) -> Result<UndoOp, GraphOpError> {
539        if !self.nodes.contains_key(&from) {
540            return Err(GraphOpError::MissingNode(from));
541        }
542        if !self.nodes.contains_key(&to) {
543            return Err(GraphOpError::MissingNode(to));
544        }
545        let edge = GraphEdge {
546            from,
547            to,
548            edge_type: etype,
549        };
550        if self.edges.contains(&edge) {
551            return Ok(UndoOp::Noop);
552        }
553        self.edges.insert(edge.clone());
554        Ok(UndoOp::DropEdge(edge))
555    }
556
557    fn apply_delete_edge(&mut self, from: NodeId, to: NodeId, etype: EdgeType) -> UndoOp {
558        let edge = GraphEdge {
559            from,
560            to,
561            edge_type: etype,
562        };
563        if self.edges.remove(&edge) {
564            UndoOp::RestoreEdge(edge)
565        } else {
566            UndoOp::Noop
567        }
568    }
569
570    fn apply_relabel_node(
571        &mut self,
572        id: NodeId,
573        emb: &[f64],
574        latent_dim: usize,
575    ) -> Result<UndoOp, GraphOpError> {
576        Self::check_embedding(id, emb, latent_dim)?;
577        let Some(node) = self.nodes.get_mut(&id) else {
578            return Err(GraphOpError::MissingNode(id));
579        };
580        if node.embedding == emb {
581            return Ok(UndoOp::Noop);
582        }
583        let previous = std::mem::replace(&mut node.embedding, emb.to_vec());
584        Ok(UndoOp::RestoreEmbedding { id, emb: previous })
585    }
586
587    fn apply_merge_nodes(&mut self, keep: NodeId, merged: NodeId) -> Result<UndoOp, GraphOpError> {
588        if keep == merged {
589            return Err(GraphOpError::SelfMerge(keep));
590        }
591        if !self.nodes.contains_key(&keep) {
592            return Err(GraphOpError::MissingNode(keep));
593        }
594        let Some(merged_node) = self.nodes.get(&merged).cloned() else {
595            return Err(GraphOpError::MissingNode(merged));
596        };
597
598        let merged_edges = self.incident(merged);
599        let keep_node = &self.nodes[&keep];
600        let keep_emb = keep_node.embedding.clone();
601        let keep_ts = keep_node.timestamp;
602
603        // Re-point every edge of `merged` onto `keep`, dropping the self-loops
604        // that re-pointing would create, and recording only the edges that did
605        // not already exist so undo removes exactly what the merge added.
606        let mut rewired = Vec::new();
607        for e in &merged_edges {
608            self.edges.remove(e);
609            let moved = GraphEdge {
610                from: if e.from == merged { keep } else { e.from },
611                to: if e.to == merged { keep } else { e.to },
612                edge_type: e.edge_type.clone(),
613            };
614            if moved.from == moved.to {
615                continue;
616            }
617            if self.edges.insert(moved.clone()) {
618                rewired.push(moved);
619            }
620        }
621
622        // EMA embedding update + timestamp refresh (spec §5.3).
623        let keep_node = self.nodes.get_mut(&keep).expect("checked above");
624        for (e, c) in keep_node
625            .embedding
626            .iter_mut()
627            .zip(merged_node.embedding.iter())
628        {
629            *e = MERGE_EMA_KEEP * *e + MERGE_EMA_NEW * *c;
630        }
631        keep_node.timestamp = merged_node.timestamp;
632        self.nodes.remove(&merged);
633
634        Ok(UndoOp::Unmerge {
635            merged: merged_node,
636            merged_edges,
637            keep,
638            keep_emb,
639            keep_ts,
640            rewired,
641        })
642    }
643
644    /// Whether two graphs hold the same `(V, E, ℳ)`, ignoring the id counter.
645    ///
646    /// This is the equality that 𝕃6 transactionality is about: [`Self::undo`]
647    /// restores the *graph*, while [`Self::next_id`] stays monotone on purpose
648    /// (see [`Self::undo`]), so `==` — which compares the counter too — is the
649    /// wrong predicate for "the rollback worked".
650    pub fn same_content(&self, other: &Graph) -> bool {
651        self.nodes == other.nodes && self.edges == other.edges
652    }
653
654    /// Reverse one journal entry.
655    ///
656    /// Restores `(V, E, ℳ)` exactly. It deliberately does **not** rewind
657    /// [`Self::next_id`]: recycling the id of a rolled-back node would let a
658    /// stale auxiliary entry (a vector-index tombstone that a revert missed)
659    /// alias a genuinely new node. Monotone allocation makes that class of bug
660    /// unrepresentable, and an unused id costs nothing.
661    pub fn undo(&mut self, entry: &UndoOp) {
662        match entry {
663            UndoOp::Noop => {}
664            UndoOp::DropNode(id) => {
665                self.nodes.remove(id);
666                self.edges.retain(|e| e.from != *id && e.to != *id);
667            }
668            UndoOp::RestoreNode { node, edges } => {
669                self.nodes.insert(node.id, node.clone());
670                for e in edges {
671                    self.edges.insert(e.clone());
672                }
673            }
674            UndoOp::DropEdge(edge) => {
675                self.edges.remove(edge);
676            }
677            UndoOp::RestoreEdge(edge) => {
678                self.edges.insert(edge.clone());
679            }
680            UndoOp::RestoreEmbedding { id, emb } => {
681                if let Some(node) = self.nodes.get_mut(id) {
682                    node.embedding.clone_from(emb);
683                }
684            }
685            UndoOp::Unmerge {
686                merged,
687                merged_edges,
688                keep,
689                keep_emb,
690                keep_ts,
691                rewired,
692            } => {
693                for e in rewired {
694                    self.edges.remove(e);
695                }
696                if let Some(node) = self.nodes.get_mut(keep) {
697                    node.embedding.clone_from(keep_emb);
698                    node.timestamp = *keep_ts;
699                }
700                self.nodes.insert(merged.id, merged.clone());
701                for e in merged_edges {
702                    self.edges.insert(e.clone());
703                }
704            }
705        }
706    }
707
708    /// Apply a batch atomically: on the first failure every applied op is
709    /// reversed and `G` is left byte-identical to its pre-state (𝕃6).
710    pub fn apply_ops(
711        &mut self,
712        ops: &[GraphOp],
713        latent_dim: usize,
714    ) -> Result<Vec<UndoOp>, GraphOpError> {
715        let mut journal = Vec::with_capacity(ops.len());
716        for op in ops {
717            match self.apply(op, latent_dim) {
718                Ok(entry) => journal.push(entry),
719                Err(e) => {
720                    self.undo_ops(&journal);
721                    return Err(e);
722                }
723            }
724        }
725        Ok(journal)
726    }
727
728    /// Reverse a journal, newest entry first.
729    pub fn undo_ops(&mut self, journal: &[UndoOp]) {
730        for entry in journal.iter().rev() {
731            self.undo(entry);
732        }
733    }
734}
735
736impl Default for Graph {
737    fn default() -> Self {
738        Graph::empty()
739    }
740}
741
742#[cfg(test)]
743mod tests {
744    use super::*;
745
746    const DIM: usize = 2;
747
748    fn node(id: NodeId, emb: [f64; DIM]) -> GraphNode {
749        GraphNode {
750            id,
751            embedding: emb.to_vec(),
752            node_type: NodeType::Observation,
753            timestamp: id,
754        }
755    }
756
757    fn two_node_graph() -> Graph {
758        let mut g = Graph::empty();
759        g.apply(
760            &GraphOp::AddNode {
761                id: 1,
762                ntype: NodeType::Observation,
763                emb: vec![1.0, 0.0],
764                ts: 1,
765            },
766            DIM,
767        )
768        .unwrap();
769        g.apply(
770            &GraphOp::AddNode {
771                id: 2,
772                ntype: NodeType::Hypothesis,
773                emb: vec![0.0, 1.0],
774                ts: 2,
775            },
776            DIM,
777        )
778        .unwrap();
779        g.apply(
780            &GraphOp::AddEdge {
781                from: 1,
782                to: 2,
783                etype: EdgeType::CausallyPrecedes,
784            },
785            DIM,
786        )
787        .unwrap();
788        g
789    }
790
791    #[test]
792    fn graph_ok_accepts_a_well_formed_graph() {
793        let g = two_node_graph();
794        assert!(g.ok(DIM));
795        assert_eq!(g.node_count(), 2);
796        assert_eq!(g.edge_count(), 1);
797        assert_eq!(g.size(), 3);
798    }
799
800    #[test]
801    fn graph_ok_rejects_wrong_dimension_and_dangling_edges() {
802        let g = two_node_graph();
803        assert!(!g.ok(DIM + 1), "wrong latent_dim must fail Inv3");
804
805        let mut dangling = two_node_graph();
806        dangling.edges.insert(GraphEdge {
807            from: 1,
808            to: 999,
809            edge_type: EdgeType::Refines,
810        });
811        assert!(!dangling.ok(DIM), "dangling edge must fail Inv3");
812
813        let mut desynced = two_node_graph();
814        desynced.nodes.insert(7, node(8, [0.0, 0.0]));
815        assert!(!desynced.ok(DIM), "key/id desync must fail Inv3");
816
817        let mut nonfinite = two_node_graph();
818        nonfinite.nodes.get_mut(&1).unwrap().embedding[0] = f64::NAN;
819        assert!(!nonfinite.ok(DIM), "NaN embedding must fail Inv3");
820    }
821
822    #[test]
823    fn ops_are_integrity_checked_before_mutating() {
824        let mut g = two_node_graph();
825        let before = g.clone();
826
827        // Wrong dimension.
828        assert!(matches!(
829            g.apply(
830                &GraphOp::AddNode {
831                    id: 3,
832                    ntype: NodeType::Action,
833                    emb: vec![1.0, 2.0, 3.0],
834                    ts: 3
835                },
836                DIM
837            ),
838            Err(GraphOpError::Dim {
839                id: 3,
840                got: 3,
841                want: 2
842            })
843        ));
844        // Non-finite embedding.
845        assert!(matches!(
846            g.apply(
847                &GraphOp::AddNode {
848                    id: 4,
849                    ntype: NodeType::Action,
850                    emb: vec![f64::INFINITY, 0.0],
851                    ts: 4
852                },
853                DIM
854            ),
855            Err(GraphOpError::NonFinite(4))
856        ));
857        // Edge to a missing endpoint.
858        assert!(matches!(
859            g.apply(
860                &GraphOp::AddEdge {
861                    from: 1,
862                    to: 42,
863                    etype: EdgeType::Refines
864                },
865                DIM
866            ),
867            Err(GraphOpError::MissingNode(42))
868        ));
869        // Relabel of a missing node.
870        assert!(matches!(
871            g.apply(
872                &GraphOp::RelabelNode {
873                    id: 42,
874                    emb: vec![0.0, 0.0]
875                },
876                DIM
877            ),
878            Err(GraphOpError::MissingNode(42))
879        ));
880        // Self-merge.
881        assert!(matches!(
882            g.apply(&GraphOp::MergeNodes { keep: 1, merged: 1 }, DIM),
883            Err(GraphOpError::SelfMerge(1))
884        ));
885
886        assert_eq!(g, before, "a refused op must not mutate the graph");
887    }
888
889    #[test]
890    fn every_op_round_trips_through_its_undo_entry() {
891        let dim = DIM;
892        let ops = vec![
893            GraphOp::AddNode {
894                id: 3,
895                ntype: NodeType::Goal,
896                emb: vec![0.5, 0.5],
897                ts: 3,
898            },
899            GraphOp::DeleteNode { id: 2 },
900            // Endpoints must exist in the fresh two-node fixture each
901            // iteration starts from, so this is 1→2 with a *new* type (the
902            // existing 1→2 edge is CausallyPrecedes, so this really inserts).
903            GraphOp::AddEdge {
904                from: 1,
905                to: 2,
906                etype: EdgeType::TemporalNext,
907            },
908            GraphOp::DeleteEdge {
909                from: 1,
910                to: 2,
911                etype: EdgeType::CausallyPrecedes,
912            },
913            GraphOp::RelabelNode {
914                id: 1,
915                emb: vec![9.0, 9.0],
916            },
917            GraphOp::MergeNodes { keep: 1, merged: 2 },
918        ];
919
920        for op in ops {
921            let mut g = two_node_graph();
922            let before = g.clone();
923            let entry = g.apply(&op, dim).expect("op should apply");
924            g.undo(&entry);
925            assert!(
926                g.same_content(&before),
927                "undo of {op:?} did not restore (V, E, ℳ):\n  got  {:?}\n  want {:?}",
928                g.nodes,
929                before.nodes
930            );
931            assert!(
932                g.next_id() >= before.next_id(),
933                "undo must never rewind the id counter"
934            );
935        }
936    }
937
938    #[test]
939    fn rollback_does_not_recycle_node_ids() {
940        // A rolled-back AddNode must not hand its id to the next node: a stale
941        // index tombstone could otherwise alias a genuinely new node.
942        let mut g = two_node_graph();
943        let id = g.next_id();
944        let entry = g
945            .apply(
946                &GraphOp::AddNode {
947                    id,
948                    ntype: NodeType::Observation,
949                    emb: vec![0.0, 0.0],
950                    ts: 0,
951                },
952                DIM,
953            )
954            .unwrap();
955        g.undo(&entry);
956        assert!(!g.nodes.contains_key(&id), "node must be gone after undo");
957        assert!(
958            g.next_id() > id,
959            "id {id} was recycled after rollback (next_id = {})",
960            g.next_id()
961        );
962    }
963
964    #[test]
965    fn merge_rewires_edges_and_ema_updates_the_survivor() {
966        let mut g = two_node_graph();
967        // 3 --Refines--> 2, so the merge must re-point it to 1.
968        g.apply(
969            &GraphOp::AddNode {
970                id: 3,
971                ntype: NodeType::Action,
972                emb: vec![0.0, 0.0],
973                ts: 3,
974            },
975            DIM,
976        )
977        .unwrap();
978        g.apply(
979            &GraphOp::AddEdge {
980                from: 3,
981                to: 2,
982                etype: EdgeType::Refines,
983            },
984            DIM,
985        )
986        .unwrap();
987        let before = g.clone();
988
989        let entry = g
990            .apply(&GraphOp::MergeNodes { keep: 1, merged: 2 }, DIM)
991            .unwrap();
992
993        assert!(!g.nodes.contains_key(&2), "merged node must be gone");
994        assert!(
995            g.edges.contains(&GraphEdge {
996                from: 3,
997                to: 1,
998                edge_type: EdgeType::Refines
999            }),
1000            "edge 3→2 must be re-pointed to 3→1, got {:?}",
1001            g.edges
1002        );
1003        assert!(
1004            !g.edges.iter().any(|e| e.from == 2 || e.to == 2),
1005            "no edge may reference the merged node"
1006        );
1007        assert!(
1008            !g.edges.iter().any(|e| e.from == e.to),
1009            "re-pointing must not create a self-loop"
1010        );
1011        // EMA: 0.9·[1,0] + 0.1·[0,1] = [0.9, 0.1]; timestamp takes the merged one.
1012        let keep = &g.nodes[&1];
1013        assert!((keep.embedding[0] - 0.9).abs() < 1e-15);
1014        assert!((keep.embedding[1] - 0.1).abs() < 1e-15);
1015        assert_eq!(keep.timestamp, 2);
1016        assert!(g.ok(DIM), "merge must preserve Inv3");
1017
1018        g.undo(&entry);
1019        assert!(
1020            g.same_content(&before),
1021            "unmerge must restore both pre-images exactly"
1022        );
1023    }
1024
1025    #[test]
1026    fn ops_are_idempotent() {
1027        let mut g = two_node_graph();
1028        let add = GraphOp::AddNode {
1029            id: 1,
1030            ntype: NodeType::Observation,
1031            emb: vec![1.0, 0.0],
1032            ts: 1,
1033        };
1034        assert_eq!(g.apply(&add, DIM).unwrap(), UndoOp::Noop);
1035        let edge = GraphOp::AddEdge {
1036            from: 1,
1037            to: 2,
1038            etype: EdgeType::CausallyPrecedes,
1039        };
1040        assert_eq!(g.apply(&edge, DIM).unwrap(), UndoOp::Noop);
1041        assert_eq!(
1042            g.apply(&GraphOp::DeleteNode { id: 77 }, DIM).unwrap(),
1043            UndoOp::Noop
1044        );
1045        assert_eq!(
1046            g.apply(
1047                &GraphOp::DeleteEdge {
1048                    from: 1,
1049                    to: 2,
1050                    etype: EdgeType::Refines
1051                },
1052                DIM
1053            )
1054            .unwrap(),
1055            UndoOp::Noop
1056        );
1057        assert_eq!(g.node_count(), 2);
1058        assert_eq!(g.edge_count(), 1);
1059    }
1060
1061    #[test]
1062    fn duplicate_id_with_different_content_is_refused() {
1063        let mut g = two_node_graph();
1064        assert!(matches!(
1065            g.apply(
1066                &GraphOp::AddNode {
1067                    id: 1,
1068                    ntype: NodeType::Goal,
1069                    emb: vec![7.0, 7.0],
1070                    ts: 9
1071                },
1072                DIM
1073            ),
1074            Err(GraphOpError::DuplicateNode(1))
1075        ));
1076    }
1077
1078    #[test]
1079    fn delete_node_takes_its_edges_and_restore_brings_them_back() {
1080        let mut g = two_node_graph();
1081        let before = g.clone();
1082        let entry = g.apply(&GraphOp::DeleteNode { id: 2 }, DIM).unwrap();
1083        assert_eq!(g.edge_count(), 0, "incident edges must go with the node");
1084        assert!(g.ok(DIM), "no dangling edge may survive a delete");
1085        g.undo(&entry);
1086        assert!(g.same_content(&before));
1087    }
1088
1089    #[test]
1090    fn batch_apply_is_all_or_nothing() {
1091        let mut g = two_node_graph();
1092        let before = g.clone();
1093        let err = g
1094            .apply_ops(
1095                &[
1096                    GraphOp::AddNode {
1097                        id: 5,
1098                        ntype: NodeType::Action,
1099                        emb: vec![0.1, 0.2],
1100                        ts: 5,
1101                    },
1102                    GraphOp::AddEdge {
1103                        from: 5,
1104                        to: 1,
1105                        etype: EdgeType::Refines,
1106                    },
1107                    // Fails: dimension violation, after two successful ops.
1108                    GraphOp::AddNode {
1109                        id: 6,
1110                        ntype: NodeType::Action,
1111                        emb: vec![0.0],
1112                        ts: 6,
1113                    },
1114                ],
1115                DIM,
1116            )
1117            .expect_err("batch must fail");
1118        assert!(matches!(err, GraphOpError::Dim { id: 6, .. }));
1119        assert!(
1120            g.same_content(&before),
1121            "a failed batch must roll back completely"
1122        );
1123
1124        let journal = g
1125            .apply_ops(
1126                &[
1127                    GraphOp::AddNode {
1128                        id: 5,
1129                        ntype: NodeType::Action,
1130                        emb: vec![0.1, 0.2],
1131                        ts: 5,
1132                    },
1133                    GraphOp::AddEdge {
1134                        from: 5,
1135                        to: 1,
1136                        etype: EdgeType::Refines,
1137                    },
1138                ],
1139                DIM,
1140            )
1141            .expect("batch must apply");
1142        assert_eq!(g.size(), before.size() + 2);
1143        g.undo_ops(&journal);
1144        assert!(
1145            g.same_content(&before),
1146            "undo_ops must restore the pre-state"
1147        );
1148    }
1149
1150    #[test]
1151    fn ids_stay_monotone_and_are_never_reused() {
1152        let mut g = Graph::empty();
1153        assert_eq!(g.next_id(), 0);
1154        let id = g.next_id();
1155        g.apply(
1156            &GraphOp::AddNode {
1157                id,
1158                ntype: NodeType::Observation,
1159                emb: vec![0.0, 0.0],
1160                ts: 0,
1161            },
1162            DIM,
1163        )
1164        .unwrap();
1165        assert_eq!(g.next_id(), 1);
1166        g.apply(&GraphOp::DeleteNode { id }, DIM).unwrap();
1167        assert_eq!(g.next_id(), 1, "deleting must not recycle the id");
1168    }
1169
1170    #[test]
1171    fn acyclicity_detects_cycles_and_self_loops() {
1172        let g = two_node_graph();
1173        assert!(g.is_acyclic());
1174
1175        let mut cyclic = two_node_graph();
1176        cyclic
1177            .apply(
1178                &GraphOp::AddEdge {
1179                    from: 2,
1180                    to: 1,
1181                    etype: EdgeType::CausallyPrecedes,
1182                },
1183                DIM,
1184            )
1185            .unwrap();
1186        assert!(!cyclic.is_acyclic());
1187
1188        let mut loopy = two_node_graph();
1189        loopy
1190            .apply(
1191                &GraphOp::AddEdge {
1192                    from: 1,
1193                    to: 1,
1194                    etype: EdgeType::CausallyPrecedes,
1195                },
1196                DIM,
1197            )
1198            .unwrap();
1199        assert!(!loopy.is_acyclic());
1200    }
1201
1202    #[test]
1203    fn legacy_type_names_load_through_the_alias_table() {
1204        // v0.1.0 wrote node_type "latent" and edge_type "morph".
1205        assert_eq!(NodeType::from_wire("latent"), NodeType::Observation);
1206        assert_eq!(EdgeType::from_wire("morph"), EdgeType::CausallyPrecedes);
1207        // Unknown labels survive as Custom rather than failing the load.
1208        assert_eq!(
1209            NodeType::from_wire("market_segment"),
1210            NodeType::Custom("market_segment".into())
1211        );
1212
1213        let legacy = r#"{
1214            "nodes": { "0": { "id": 0, "embedding": [1.0, 0.0], "node_type": "latent", "timestamp": 3 } },
1215            "edges": [ { "from": 0, "to": 0, "edge_type": "morph" } ]
1216        }"#;
1217        let g: Graph = serde_json::from_str(legacy).expect("legacy graph must deserialize");
1218        assert_eq!(g.nodes[&0].node_type, NodeType::Observation);
1219        assert_eq!(
1220            g.edges.iter().next().unwrap().edge_type,
1221            EdgeType::CausallyPrecedes
1222        );
1223    }
1224
1225    #[test]
1226    fn serde_round_trips_and_is_stable() {
1227        let g = two_node_graph();
1228        let json = serde_json::to_string(&g).unwrap();
1229        let back: Graph = serde_json::from_str(&json).unwrap();
1230        assert_eq!(g, back);
1231        // Ordered containers ⇒ byte-stable serialization across runs.
1232        assert_eq!(json, serde_json::to_string(&back).unwrap());
1233        assert!(
1234            json.contains("\"observation\"") && json.contains("\"causally_precedes\""),
1235            "types must serialize as readable names: {json}"
1236        );
1237    }
1238
1239    #[test]
1240    fn iteration_order_is_deterministic_regardless_of_insertion_order() {
1241        // The v0.1.0 HashMap/HashSet graph iterated in a per-process random
1242        // order, which made `one_edit` pick different nodes in different
1243        // processes. Ordered containers remove that degree of freedom.
1244        let mut ascending = Graph::empty();
1245        for id in 0..32u64 {
1246            ascending
1247                .apply(
1248                    &GraphOp::AddNode {
1249                        id,
1250                        ntype: NodeType::Observation,
1251                        emb: vec![id as f64, 0.0],
1252                        ts: id,
1253                    },
1254                    DIM,
1255                )
1256                .unwrap();
1257        }
1258        let mut descending = Graph::empty();
1259        for id in (0..32u64).rev() {
1260            descending
1261                .apply(
1262                    &GraphOp::AddNode {
1263                        id,
1264                        ntype: NodeType::Observation,
1265                        emb: vec![id as f64, 0.0],
1266                        ts: id,
1267                    },
1268                    DIM,
1269                )
1270                .unwrap();
1271        }
1272        let a: Vec<NodeId> = ascending.nodes.keys().copied().collect();
1273        let d: Vec<NodeId> = descending.nodes.keys().copied().collect();
1274        assert_eq!(a, d, "iteration order must not depend on insertion order");
1275        assert_eq!(a, (0..32u64).collect::<Vec<_>>());
1276    }
1277}