Skip to main content

drevo_core/
native.rs

1//! [`NativeGraph`] — the graph engine.
2//!
3//! # What this is
4//!
5//! An **in-memory** implementation of [`GraphEngine`]:
6//! nodes and edges are held directly in Rust maps.
7//! [`open_durable`](crate::native::NativeGraph::open_durable) adds a
8//! write-ahead log, so acknowledged writes survive a restart.
9//!
10//! Adjacency is **denormalized**: each entry carries the neighbour node id and
11//! the edge's kind (interned to a `u32`) inline alongside the edge id, so a
12//! fan-out reads neighbour ids and filters by kind straight from a node's
13//! adjacency vector — no second lookup into the edge map, no per-edge string
14//! compare.
15//!
16//! # Snapshot isolation
17//!
18//! The whole store lives behind `RwLock<Arc<Inner>>`. A
19//! [`GraphSnapshot`] is a cheap `Arc::clone` of
20//! the current state — an **O(1)**, frozen, consistent view. Writers use
21//! copy-on-write via [`Arc::make_mut`](std::sync::Arc::make_mut): they mutate the state
22//! in place while no snapshot is outstanding, and clone it once on the first
23//! write after a snapshot is taken. So a reader that holds a snapshot always
24//! sees one consistent version of the graph regardless of concurrent writes —
25//! the property a multi-hop retrieval needs (a traversal never observes half of
26//! another writer's in-flight mutation). Transactions
27//! ([`begin`](crate::native::NativeGraph::begin)) buffer their writes and
28//! commit them atomically on top of this.
29//!
30//! # Guarantees
31//!
32//! Monotonic ids from 1, title uniqueness
33//! ([`CoreError::DuplicateTitle`]),
34//! endpoint existence on edge create
35//! ([`CoreError::NodeNotFound`]), weight
36//! finiteness ([`CoreError::InvalidWeight`]),
37//! [`EdgeNotFound`](crate::error::CoreError::EdgeNotFound) on missing edge
38//! update/delete, cascade edge deletion when a node is removed, and the
39//! direction/kind-filtered adjacency contract. uuid and timestamp fields are
40//! filled in by [`NewNode::into_node`](crate::model::NewNode::into_node) /
41//! [`NewEdge::into_edge`](crate::model::NewEdge::into_edge).
42//!
43//! Secondary subsystems (full-text, labels, property values) are
44//! intentionally **not** part of this engine: they live in their own modules
45//! and follow the graph through its change-feed
46//! ([`changes_since`](crate::native::NativeGraph::changes_since)).
47
48use std::collections::{BTreeMap, BTreeSet, HashMap};
49use std::sync::{Arc, RwLock};
50
51use serde::{Deserialize, Serialize};
52
53use crate::csr::CsrAdjacency;
54use crate::delta::{ApplyStats, Delta, StampedChange, StampedEdge, VersionVector};
55use crate::dump::{Dump, DumpError, ImportReport, FORMAT_V1};
56use crate::engine::GraphEngine;
57use crate::error::{CoreError, Result};
58use crate::hlc::HlcClock;
59use crate::lww::{OriginId, Stamp};
60use crate::model::{now_ms, Direction, Edge, EdgePatch, NewEdge, NewNode, Node, NodePatch};
61
62/// A denormalized adjacency entry: the incident edge, the node at its other
63/// end, and that edge's kind interned to a `u32`. Storing the neighbour id and
64/// kind inline is what lets a fan-out avoid a second map lookup per edge.
65#[derive(Clone, Copy, Debug)]
66struct AdjEntry {
67    edge_id: u64,
68    neighbor_id: u64,
69    kind_id: u32,
70}
71
72/// The total order every adjacency list is kept in: interned kind first — so a
73/// relationship-type filter is one contiguous run — then neighbour id, then
74/// edge id as a stable tie-break. Maintaining this lets a kind-filtered fan-out
75/// binary-search its run instead of scanning every incident edge.
76fn adj_sort_key(e: &AdjEntry) -> (u32, u64, u64) {
77    (e.kind_id, e.neighbor_id, e.edge_id)
78}
79
80/// Insert `entry` into a kind-sorted adjacency list at the position that keeps
81/// [`adj_sort_key`] ordering. Degrees are small, so the `insert` shift is cheap.
82fn insert_adj_sorted(v: &mut Vec<AdjEntry>, entry: AdjEntry) {
83    let key = adj_sort_key(&entry);
84    let pos = v.partition_point(|e| adj_sort_key(e) < key);
85    v.insert(pos, entry);
86}
87
88/// The contiguous sub-slice of a kind-sorted adjacency list whose entries have
89/// `kind_id == kind`, located by two binary searches (`O(log n)` to the run).
90fn kind_run(v: &[AdjEntry], kind: u32) -> &[AdjEntry] {
91    let start = v.partition_point(|e| e.kind_id < kind);
92    let end = v.partition_point(|e| e.kind_id <= kind);
93    &v[start..end]
94}
95
96/// Interior state of a [`NativeGraph`]. Held behind `Arc` so a snapshot is a
97/// cheap clone and writers copy-on-write via [`Arc::make_mut`]. `Clone` is what
98/// makes that copy-on-write possible.
99#[derive(Default, Clone)]
100struct Inner {
101    // Nodes and edges are stored behind `Arc` so a read can hand back a cheap
102    // pointer-bump handle (`get_node_arc`/`neighbors_arc`) instead of deep-
103    // cloning the record, and so copy-on-write of `Inner` for a snapshot clones
104    // `Arc`s rather than every node body/property map.
105    nodes: HashMap<u64, Arc<Node>>,
106    edges: HashMap<u64, Arc<Edge>>,
107    /// `from_id → entries` (neighbour = the edge's `to_id`), insertion order.
108    out_adj: HashMap<u64, Vec<AdjEntry>>,
109    /// `to_id → entries` (neighbour = the edge's `from_id`), insertion order.
110    in_adj: HashMap<u64, Vec<AdjEntry>>,
111    /// `title → node id`: the title-uniqueness index.
112    titles: HashMap<String, u64>,
113    /// `node kind → ids of that kind`: the primary-kind index, so
114    /// `nodes_by_kind` is `O(matches · log)` instead of a full `O(n)` scan.
115    /// The `BTreeSet` keeps ids ascending, the order `nodes_by_kind` returns
116    /// (and what `offset`/`limit` pagination is defined against).
117    kind_index: HashMap<String, BTreeSet<u64>>,
118    /// Edge-kind string → interned `u32` id (adjacency stores the id).
119    kind_ids: HashMap<String, u32>,
120    /// `node id → embedding vector` — the durable, typed embedding store. Kept
121    /// separate from node `properties` (distinct lifecycle; the HNSW index is
122    /// rebuilt from it), but keyed by node id and **cascaded on node
123    /// deletion**.
124    embeddings: HashMap<u64, Vec<f32>>,
125    /// Declared schema constraints, validated at transaction commit.
126    constraints: Vec<Constraint>,
127    next_node_id: u64,
128    next_edge_id: u64,
129    /// High-water mark of every `updated_at` timestamp the graph has issued.
130    /// `update_node` draws a strictly-greater value from it so a touched node
131    /// always sorts ahead in `list_recent`, even when several in-memory writes
132    /// land in the same wall-clock millisecond.
133    last_updated_at: i64,
134    /// Two-phase commit: transactions prepared but not yet resolved,
135    /// keyed by global transaction id. Kept with the graph so that replay,
136    /// WAL-tailing replicas and compaction all carry it; non-empty means the
137    /// write fence is up.
138    prepared: BTreeMap<String, PreparedEntry>,
139    /// Global transaction ids rolled back heuristically: a late
140    /// `commit_prepared` for one of these reports the overridden outcome.
141    heuristic: BTreeSet<String>,
142}
143
144impl Inner {
145    /// Record that a timestamp has been observed, advancing the recency
146    /// high-water mark. Called on every create and every WAL-replayed upsert so
147    /// a later `update_node` is guaranteed to out-rank it.
148    fn observe_updated_at(&mut self, ts: i64) {
149        self.last_updated_at = self.last_updated_at.max(ts);
150    }
151
152    /// Issue the next `updated_at` for a mutation: the wall clock, but never
153    /// less than one past the high-water mark, so recency ordering stays strict
154    /// under sub-millisecond writes.
155    fn next_updated_at(&mut self) -> i64 {
156        let ts = now_ms().max(self.last_updated_at + 1);
157        self.last_updated_at = ts;
158        ts
159    }
160
161    /// Intern an edge kind, assigning a fresh id on first sight.
162    fn intern_kind(&mut self, kind: &str) -> u32 {
163        if let Some(&id) = self.kind_ids.get(kind) {
164            return id;
165        }
166        let id = self.kind_ids.len() as u32;
167        self.kind_ids.insert(kind.to_string(), id);
168        id
169    }
170
171    /// The interned id for `kind`, or `None` if no edge of that kind has ever
172    /// existed (so a kind-filtered scan can short-circuit to empty).
173    fn kind_id_of(&self, kind: &str) -> Option<u32> {
174        self.kind_ids.get(kind).copied()
175    }
176
177    /// Add `id` to the `kind` bucket of the node-kind index.
178    fn index_node_kind(&mut self, id: u64, kind: &str) {
179        self.kind_index
180            .entry(kind.to_string())
181            .or_default()
182            .insert(id);
183    }
184
185    /// Remove `id` from the `kind` bucket, dropping the bucket when it empties
186    /// so an absent kind is truly absent (no lingering empty set).
187    fn unindex_node_kind(&mut self, id: u64, kind: &str) {
188        if let Some(set) = self.kind_index.get_mut(kind) {
189            set.remove(&id);
190            if set.is_empty() {
191                self.kind_index.remove(kind);
192            }
193        }
194    }
195
196    /// Invoke `f` for each adjacency entry incident to `node_id` in `direction`,
197    /// in `edges_of` order (the outgoing pass, then the incoming pass) —
198    /// **without allocating**, so the hot fan-out paths spend no time on a
199    /// scratch `Vec`/`HashSet`.
200    ///
201    /// A **self-loop** under [`Direction::Both`] sits in both the out- and
202    /// in-lists; it is reported once, so the incoming pass skips it. That is
203    /// exact: a self-loop is the *only* way one edge lands in both a node's out-
204    /// and in-lists (a non-loop edge `x→y` is in `out[x]` and `in[y]` only), and
205    /// a self-loop's entry is exactly the one whose `neighbor_id == node_id`.
206    fn for_each_incident<F: FnMut(&AdjEntry)>(&self, node_id: u64, direction: Direction, mut f: F) {
207        if matches!(direction, Direction::Outgoing | Direction::Both) {
208            if let Some(v) = self.out_adj.get(&node_id) {
209                for e in v {
210                    f(e);
211                }
212            }
213        }
214        if matches!(direction, Direction::Incoming | Direction::Both) {
215            if let Some(v) = self.in_adj.get(&node_id) {
216                for e in v {
217                    // Under `Both`, the outgoing pass already emitted any
218                    // self-loop; skip its mirror here to keep `Drevo`'s count.
219                    if matches!(direction, Direction::Both) && e.neighbor_id == node_id {
220                        continue;
221                    }
222                    f(e);
223                }
224            }
225        }
226    }
227
228    /// Like [`for_each_incident`](Self::for_each_incident) but visits only the
229    /// entries whose interned kind is `kind_id`, using the kind-sorted invariant
230    /// to binary-search each direction's run instead of scanning the whole list.
231    /// The same self-loop-under-`Both` dedup as `for_each_incident` applies.
232    fn for_each_incident_of_kind<F: FnMut(&AdjEntry)>(
233        &self,
234        node_id: u64,
235        direction: Direction,
236        kind_id: u32,
237        mut f: F,
238    ) {
239        if matches!(direction, Direction::Outgoing | Direction::Both) {
240            if let Some(v) = self.out_adj.get(&node_id) {
241                for e in kind_run(v, kind_id) {
242                    f(e);
243                }
244            }
245        }
246        if matches!(direction, Direction::Incoming | Direction::Both) {
247            if let Some(v) = self.in_adj.get(&node_id) {
248                for e in kind_run(v, kind_id) {
249                    if matches!(direction, Direction::Both) && e.neighbor_id == node_id {
250                        continue;
251                    }
252                    f(e);
253                }
254            }
255        }
256    }
257
258    /// The adjacency entries incident to `node_id`, collected into a `Vec`. Used
259    /// by the **mutating** paths (`delete_node`), which need an owned list
260    /// because they borrow `self` mutably while iterating; read paths use the
261    /// allocation-free [`for_each_incident`](Self::for_each_incident).
262    fn incident_entries(&self, node_id: u64, direction: Direction) -> Vec<AdjEntry> {
263        let mut entries = Vec::new();
264        self.for_each_incident(node_id, direction, |e| entries.push(*e));
265        entries
266    }
267
268    // ----- read operations (shared by the engine and by GraphSnapshot) -------
269
270    fn get_node(&self, id: u64) -> Option<Node> {
271        self.nodes.get(&id).map(|a| (**a).clone())
272    }
273
274    fn get_edge(&self, id: u64) -> Option<Edge> {
275        self.edges.get(&id).map(|a| (**a).clone())
276    }
277
278    /// Zero-copy node fetch: clones the `Arc` (a refcount bump), not the record.
279    fn get_node_arc(&self, id: u64) -> Option<Arc<Node>> {
280        self.nodes.get(&id).cloned()
281    }
282
283    /// Zero-copy edge fetch: clones the `Arc`, not the record.
284    fn get_edge_arc(&self, id: u64) -> Option<Arc<Edge>> {
285        self.edges.get(&id).cloned()
286    }
287
288    fn neighbor_ids(&self, node_id: u64, direction: Direction, kind: Option<&str>) -> Vec<u64> {
289        // A kind that was never seen means no matching edges.
290        let want_kind = match kind {
291            Some(k) => match self.kind_id_of(k) {
292                Some(id) => Some(id),
293                None => return Vec::new(),
294            },
295            None => None,
296        };
297        let mut seen = std::collections::HashSet::new();
298        seen.insert(node_id);
299        let mut ids = Vec::new();
300        let push = |e: &AdjEntry| {
301            if seen.insert(e.neighbor_id) {
302                ids.push(e.neighbor_id);
303            }
304        };
305        // A relationship-type filter takes the binary-searched kind run; an
306        // unfiltered fan-out still walks every incident edge.
307        match want_kind {
308            Some(k) => self.for_each_incident_of_kind(node_id, direction, k, push),
309            None => self.for_each_incident(node_id, direction, push),
310        }
311        ids
312    }
313
314    fn neighbors(&self, node_id: u64, direction: Direction, kind: Option<&str>) -> Vec<Node> {
315        self.neighbor_ids(node_id, direction, kind)
316            .into_iter()
317            .filter_map(|id| self.nodes.get(&id).map(|a| (**a).clone()))
318            .collect()
319    }
320
321    /// Zero-copy neighbour fetch: each neighbour comes back as an `Arc<Node>`
322    /// handle (refcount bump), so a fan-out that reads many neighbours never
323    /// deep-clones their bodies/properties.
324    fn neighbors_arc(
325        &self,
326        node_id: u64,
327        direction: Direction,
328        kind: Option<&str>,
329    ) -> Vec<Arc<Node>> {
330        self.neighbor_ids(node_id, direction, kind)
331            .into_iter()
332            .filter_map(|id| self.nodes.get(&id).cloned())
333            .collect()
334    }
335
336    fn edges_of(&self, node_id: u64, direction: Direction) -> Vec<Edge> {
337        let mut out = Vec::new();
338        self.for_each_incident(node_id, direction, |e| {
339            if let Some(edge) = self.edges.get(&e.edge_id) {
340                out.push((**edge).clone());
341            }
342        });
343        out
344    }
345
346    fn all_nodes(&self) -> Vec<Node> {
347        // Id-ascending, not HashMap iteration order: full scans must
348        // enumerate deterministically (and identically to the KV engine's
349        // `collect_all_nodes`) so an unordered Cypher `MATCH` produces the
350        // same row order on both engines.
351        let mut nodes: Vec<Node> = self.nodes.values().map(|a| (**a).clone()).collect();
352        nodes.sort_unstable_by_key(|n| n.id);
353        nodes
354    }
355
356    /// Zero-copy full scan: id-ascending `Arc<Node>` handles (refcount bumps
357    /// only), so enumerating the whole graph never deep-clones node bodies.
358    fn all_nodes_arc(&self) -> Vec<Arc<Node>> {
359        let mut nodes: Vec<Arc<Node>> = self.nodes.values().cloned().collect();
360        nodes.sort_unstable_by_key(|n| n.id);
361        nodes
362    }
363
364    fn all_edges(&self) -> Vec<Edge> {
365        // Id-ascending, for the same determinism contract as `all_nodes`.
366        let mut edges: Vec<Edge> = self.edges.values().map(|a| (**a).clone()).collect();
367        edges.sort_unstable_by_key(|e| e.id);
368        edges
369    }
370
371    fn nodes_by_kind(&self, kind: &str, limit: usize, offset: usize) -> Vec<Node> {
372        // Index-driven: walk only this kind's ids (already ascending in the
373        // `BTreeSet`, matching Drevo's order) and materialise the page. An
374        // unknown kind has no bucket → empty, no scan.
375        let Some(ids) = self.kind_index.get(kind) else {
376            return Vec::new();
377        };
378        ids.iter()
379            .skip(offset)
380            .take(limit)
381            .filter_map(|id| self.nodes.get(id).map(|a| (**a).clone()))
382            .collect()
383    }
384
385    /// Look up a node by its unique title via the `titles` index (title
386    /// uniqueness is enforced on write, so at most one match).
387    fn get_node_by_title(&self, title: &str) -> Option<Node> {
388        self.titles
389            .get(title)
390            .and_then(|id| self.nodes.get(id))
391            .map(|a| (**a).clone())
392    }
393
394    /// Most-recently-updated nodes first, capped at `limit`: `updated_at`
395    /// descending, ties broken by node id
396    /// descending (a higher id was allocated later, so it is the newer insert).
397    fn list_recent(&self, limit: usize) -> Vec<Node> {
398        if limit == 0 {
399            return Vec::new();
400        }
401        let mut nodes: Vec<Node> = self.nodes.values().map(|a| (**a).clone()).collect();
402        nodes.sort_unstable_by(|a, b| {
403            b.updated_at
404                .cmp(&a.updated_at)
405                .then_with(|| b.id.cmp(&a.id))
406        });
407        nodes.truncate(limit);
408        nodes
409    }
410
411    /// Edges of a given `kind`, id-ascending, paginated — the edge counterpart
412    /// of [`Inner::nodes_by_kind`]. No edge-kind index exists yet, so this
413    /// scans; `all_edges` is already id-sorted for the pagination contract.
414    fn list_edges_by_kind(&self, kind: &str, limit: usize, offset: usize) -> Vec<Edge> {
415        let mut edges: Vec<Edge> = self
416            .edges
417            .values()
418            .filter(|e| e.kind == kind)
419            .map(|a| (**a).clone())
420            .collect();
421        edges.sort_unstable_by_key(|e| e.id);
422        edges.into_iter().skip(offset).take(limit).collect()
423    }
424
425    /// Zero-copy label scan (see [`Inner::all_nodes_arc`]): the page's nodes
426    /// come back as `Arc<Node>` handles instead of deep clones.
427    fn nodes_by_kind_arc(&self, kind: &str, limit: usize, offset: usize) -> Vec<Arc<Node>> {
428        let Some(ids) = self.kind_index.get(kind) else {
429            return Vec::new();
430        };
431        ids.iter()
432            .skip(offset)
433            .take(limit)
434            .filter_map(|id| self.nodes.get(id).cloned())
435            .collect()
436    }
437
438    // ----- write operations (mutate through Arc::make_mut) -------------------
439
440    fn create_node(&mut self, new_node: NewNode) -> Result<Node> {
441        if self.titles.contains_key(&new_node.title) {
442            return Err(CoreError::DuplicateTitle(new_node.title));
443        }
444        self.next_node_id += 1;
445        let id = self.next_node_id;
446        let node = new_node.into_node(id);
447        self.observe_updated_at(node.updated_at);
448        self.titles.insert(node.title.clone(), id);
449        self.index_node_kind(id, &node.kind);
450        self.nodes.insert(id, Arc::new(node.clone()));
451        Ok(node)
452    }
453
454    fn update_node(&mut self, id: u64, patch: NodePatch) -> Result<Node> {
455        let mut node = self
456            .nodes
457            .get(&id)
458            .map(|a| (**a).clone())
459            .ok_or(CoreError::NodeNotFound(id))?;
460        let old_kind = node.kind.clone();
461        if let Some(ref new_title) = patch.title {
462            // A rename collides only when a *different* node owns the title.
463            match self.titles.get(new_title) {
464                Some(&owner) if owner != id => {
465                    return Err(CoreError::DuplicateTitle(new_title.clone()));
466                }
467                _ => {}
468            }
469            self.titles.remove(&node.title);
470            self.titles.insert(new_title.clone(), id);
471            node.title = new_title.clone();
472        }
473        if let Some(kind) = patch.kind {
474            node.kind = kind;
475        }
476        if let Some(body) = patch.body {
477            node.body = body;
478        }
479        if let Some(body_html) = patch.body_html {
480            node.body_html = body_html;
481        }
482        if let Some(properties) = patch.properties {
483            node.properties = properties;
484        }
485        if old_kind != node.kind {
486            self.unindex_node_kind(id, &old_kind);
487            self.index_node_kind(id, &node.kind);
488        }
489        // Bump the recency timestamp so `list_recent` surfaces the touched node
490        // as most-recent — parity with the KV engine's `Node::apply_patch`
491        // (and the documented `updated_at > created_at`-after-update contract).
492        // A per-graph monotonic clock keeps the ordering strict even when two
493        // in-memory writes land in the same wall-clock millisecond.
494        node.updated_at = self.next_updated_at();
495        self.nodes.insert(id, Arc::new(node.clone()));
496        Ok(node)
497    }
498
499    fn delete_node(&mut self, id: u64) -> Result<()> {
500        let node = self
501            .nodes
502            .get(&id)
503            .map(|a| (**a).clone())
504            .ok_or(CoreError::NodeNotFound(id))?;
505        let edge_ids: Vec<u64> = self
506            .incident_entries(id, Direction::Both)
507            .into_iter()
508            .map(|e| e.edge_id)
509            .collect();
510        for eid in edge_ids {
511            self.remove_edge(eid);
512        }
513        self.titles.remove(&node.title);
514        self.unindex_node_kind(id, &node.kind);
515        self.nodes.remove(&id);
516        // Deleting a node cascades to its embedding (parity with the KV handle,
517        // issue #446): the durable `vec:` entry is keyed by node id and dropped
518        // with the node, so no orphan survives.
519        self.embeddings.remove(&id);
520        Ok(())
521    }
522
523    fn create_edge(&mut self, new_edge: NewEdge) -> Result<Edge> {
524        if !new_edge.weight.is_finite() {
525            return Err(CoreError::InvalidWeight(new_edge.weight));
526        }
527        if !self.nodes.contains_key(&new_edge.from_id) {
528            return Err(CoreError::NodeNotFound(new_edge.from_id));
529        }
530        if !self.nodes.contains_key(&new_edge.to_id) {
531            return Err(CoreError::NodeNotFound(new_edge.to_id));
532        }
533        self.next_edge_id += 1;
534        let id = self.next_edge_id;
535        let edge = new_edge.into_edge(id);
536        let kind_id = self.intern_kind(&edge.kind);
537        insert_adj_sorted(
538            self.out_adj.entry(edge.from_id).or_default(),
539            AdjEntry {
540                edge_id: id,
541                neighbor_id: edge.to_id,
542                kind_id,
543            },
544        );
545        insert_adj_sorted(
546            self.in_adj.entry(edge.to_id).or_default(),
547            AdjEntry {
548                edge_id: id,
549                neighbor_id: edge.from_id,
550                kind_id,
551            },
552        );
553        self.edges.insert(id, Arc::new(edge.clone()));
554        Ok(edge)
555    }
556
557    fn update_edge(&mut self, id: u64, patch: EdgePatch) -> Result<Edge> {
558        // Weight finiteness is validated before existence, matching Drevo.
559        if let Some(w) = patch.weight {
560            if !w.is_finite() {
561                return Err(CoreError::InvalidWeight(w));
562            }
563        }
564        let kind_changed = patch.kind.is_some();
565        let mut edge = self
566            .edges
567            .get(&id)
568            .map(|a| (**a).clone())
569            .ok_or(CoreError::EdgeNotFound(id))?;
570        if let Some(kind) = patch.kind {
571            edge.kind = kind;
572        }
573        if let Some(weight) = patch.weight {
574            edge.weight = weight;
575        }
576        if let Some(properties) = patch.properties {
577            edge.properties = properties;
578        }
579        if kind_changed {
580            let new_kind_id = self.intern_kind(&edge.kind);
581            // Changing an entry's kind moves it in the `(kind_id, …)` order, so
582            // re-sort the two affected lists to preserve the kind-run invariant.
583            if let Some(list) = self.out_adj.get_mut(&edge.from_id) {
584                for e in list.iter_mut().filter(|e| e.edge_id == id) {
585                    e.kind_id = new_kind_id;
586                }
587                list.sort_unstable_by_key(adj_sort_key);
588            }
589            if let Some(list) = self.in_adj.get_mut(&edge.to_id) {
590                for e in list.iter_mut().filter(|e| e.edge_id == id) {
591                    e.kind_id = new_kind_id;
592                }
593                list.sort_unstable_by_key(adj_sort_key);
594            }
595        }
596        self.edges.insert(id, Arc::new(edge.clone()));
597        Ok(edge)
598    }
599
600    fn delete_edge(&mut self, id: u64) -> Result<()> {
601        if !self.edges.contains_key(&id) {
602            return Err(CoreError::EdgeNotFound(id));
603        }
604        self.remove_edge(id);
605        Ok(())
606    }
607
608    /// The state as a compact op log: every node then every edge as an
609    /// `Upsert`, ascending id. Replaying it reproduces the graph, so it is the
610    /// snapshot form used by `dump_wal` and WAL compaction.
611    fn to_wal_ops(&self) -> Vec<WalOp> {
612        let mut ops = Vec::with_capacity(self.nodes.len() + self.edges.len());
613        let mut nodes: Vec<&Arc<Node>> = self.nodes.values().collect();
614        nodes.sort_by_key(|n| n.id);
615        for n in nodes {
616            ops.push(WalOp::UpsertNode((**n).clone()));
617        }
618        let mut edges: Vec<&Arc<Edge>> = self.edges.values().collect();
619        edges.sort_by_key(|e| e.id);
620        for e in edges {
621            ops.push(WalOp::UpsertEdge((**e).clone()));
622        }
623        // Embeddings last, id-ascending, so compaction/dump preserves the
624        // durable embedding store (issue #446).
625        let mut embs: Vec<(&u64, &Vec<f32>)> = self.embeddings.iter().collect();
626        embs.sort_by_key(|(id, _)| **id);
627        for (id, vec) in embs {
628            ops.push(WalOp::SetEmbedding(*id, vec.clone()));
629        }
630        // Unresolved prepared transactions last (#556), so a compaction or a
631        // dump never forgets an in-doubt transaction.
632        for (gid, entry) in &self.prepared {
633            ops.push(WalOp::Prepare {
634                gid: gid.clone(),
635                prepared_at_ms: entry.prepared_at_ms,
636                ops: entry.ops.clone(),
637            });
638        }
639        // Heuristic outcomes too, so a late commit is still told after a
640        // compaction.
641        for gid in &self.heuristic {
642            ops.push(WalOp::RollbackPrepared {
643                gid: gid.clone(),
644                heuristic: true,
645            });
646        }
647        ops
648    }
649
650    /// Apply one [`WalOp`] during replay. Upserts re-insert a stored record
651    /// verbatim (ids/uuids/timestamps preserved) and advance the id counters so
652    /// a post-recovery create never reuses an id; deletes mirror the live paths.
653    /// Derived structures (adjacency, title and kind indexes) are rebuilt from
654    /// the record.
655    fn apply_wal_op(&mut self, op: WalOp) {
656        match op {
657            WalOp::UpsertNode(node) => {
658                // A replacing upsert may change the record's title and/or kind;
659                // clone the previous record so the derived indexes can be moved
660                // off the old values before the new record lands.
661                let old = self.nodes.get(&node.id).map(|a| (**a).clone());
662                if let Some(ref old) = old {
663                    if old.title != node.title {
664                        self.titles.remove(&old.title);
665                    }
666                    self.unindex_node_kind(node.id, &old.kind);
667                }
668                self.titles.insert(node.title.clone(), node.id);
669                self.index_node_kind(node.id, &node.kind);
670                self.next_node_id = self.next_node_id.max(node.id);
671                self.observe_updated_at(node.updated_at);
672                self.nodes.insert(node.id, Arc::new(node));
673            }
674            WalOp::DeleteNode(id) => {
675                if let Some(node) = self.nodes.get(&id).map(|a| (**a).clone()) {
676                    let edge_ids: Vec<u64> = self
677                        .incident_entries(id, Direction::Both)
678                        .into_iter()
679                        .map(|e| e.edge_id)
680                        .collect();
681                    for eid in edge_ids {
682                        self.remove_edge(eid);
683                    }
684                    self.titles.remove(&node.title);
685                    self.unindex_node_kind(id, &node.kind);
686                    self.nodes.remove(&id);
687                    // Cascade the embedding, same as the live delete path.
688                    self.embeddings.remove(&id);
689                }
690            }
691            WalOp::UpsertEdge(edge) => {
692                // On update, drop the old adjacency entries before re-adding.
693                if self.edges.contains_key(&edge.id) {
694                    self.remove_edge(edge.id);
695                }
696                let kind_id = self.intern_kind(&edge.kind);
697                insert_adj_sorted(
698                    self.out_adj.entry(edge.from_id).or_default(),
699                    AdjEntry {
700                        edge_id: edge.id,
701                        neighbor_id: edge.to_id,
702                        kind_id,
703                    },
704                );
705                insert_adj_sorted(
706                    self.in_adj.entry(edge.to_id).or_default(),
707                    AdjEntry {
708                        edge_id: edge.id,
709                        neighbor_id: edge.from_id,
710                        kind_id,
711                    },
712                );
713                self.next_edge_id = self.next_edge_id.max(edge.id);
714                self.edges.insert(edge.id, Arc::new(edge));
715            }
716            WalOp::DeleteEdge(id) => self.remove_edge(id),
717            WalOp::SetEmbedding(id, vector) => {
718                self.embeddings.insert(id, vector);
719            }
720            WalOp::DeleteEmbedding(id) => {
721                self.embeddings.remove(&id);
722            }
723            WalOp::Prepare {
724                gid,
725                prepared_at_ms,
726                ops,
727            } => {
728                // A new prepare reusing a gid starts afresh.
729                self.heuristic.remove(&gid);
730                self.prepared.insert(
731                    gid,
732                    PreparedEntry {
733                        prepared_at_ms,
734                        ops,
735                    },
736                );
737            }
738            // Applied at the resolution point, not at `Prepare`: an in-place
739            // writer may log a change that became visible before the
740            // transaction began *after* the `Prepare` line, and applying the
741            // write set here keeps the runtime order (RFC §2.4a).
742            WalOp::CommitPrepared { gid } => {
743                if let Some(entry) = self.prepared.remove(&gid) {
744                    for op in entry.ops {
745                        self.apply_wal_op(op);
746                    }
747                }
748            }
749            WalOp::RollbackPrepared { gid, heuristic } => {
750                self.prepared.remove(&gid);
751                if heuristic {
752                    self.heuristic.insert(gid);
753                }
754            }
755        }
756    }
757
758    /// Remove an edge and its adjacency entries. A missing id is a no-op;
759    /// callers that must error (`delete_edge`) check existence first.
760    fn remove_edge(&mut self, id: u64) {
761        let Some(edge) = self.edges.remove(&id) else {
762            return;
763        };
764        if let Some(v) = self.out_adj.get_mut(&edge.from_id) {
765            v.retain(|e| e.edge_id != id);
766        }
767        if let Some(v) = self.in_adj.get_mut(&edge.to_id) {
768            v.retain(|e| e.edge_id != id);
769        }
770    }
771
772    /// Check every declared constraint against the current node set, returning
773    /// the first [`ConstraintViolation`] found. A `UNIQUE(kind, property)`
774    /// constraint ignores nodes of that kind that lack the property (matching
775    /// Neo4j), and flags the first pair that shares a value.
776    fn validate_constraints(&self) -> std::result::Result<(), ConstraintViolation> {
777        for c in &self.constraints {
778            match c {
779                Constraint::UniqueNodeProperty { kind, property } => {
780                    let mut seen: std::collections::HashSet<String> =
781                        std::collections::HashSet::new();
782                    for n in self.nodes.values().filter(|n| &n.kind == kind) {
783                        if let Some(v) = n.properties.0.get(property) {
784                            let value = v.to_string();
785                            if !seen.insert(value.clone()) {
786                                return Err(ConstraintViolation {
787                                    kind: kind.clone(),
788                                    message: format!(
789                                        "duplicate value {value} for unique property `{property}`"
790                                    ),
791                                });
792                            }
793                        }
794                    }
795                }
796                Constraint::PropertyExists { kind, property } => {
797                    for n in self.nodes.values().filter(|n| &n.kind == kind) {
798                        if !n.properties.0.contains_key(property) {
799                            return Err(ConstraintViolation {
800                                kind: kind.clone(),
801                                message: format!(
802                                    "node {} is missing required property `{property}`",
803                                    n.id
804                                ),
805                            });
806                        }
807                    }
808                }
809                Constraint::NodeKey { kind, properties } => {
810                    let mut seen: std::collections::HashSet<String> =
811                        std::collections::HashSet::new();
812                    for n in self.nodes.values().filter(|n| &n.kind == kind) {
813                        let mut parts = Vec::with_capacity(properties.len());
814                        for p in properties {
815                            match n.properties.0.get(p) {
816                                Some(v) => parts.push(v.to_string()),
817                                None => {
818                                    return Err(ConstraintViolation {
819                                        kind: kind.clone(),
820                                        message: format!(
821                                            "node {} is missing node-key property `{p}`",
822                                            n.id
823                                        ),
824                                    })
825                                }
826                            }
827                        }
828                        // Unit separator joins the tuple into one comparable key.
829                        let key = parts.join("\u{1f}");
830                        if !seen.insert(key) {
831                            return Err(ConstraintViolation {
832                                kind: kind.clone(),
833                                message: format!(
834                                    "duplicate node key {parts:?} on properties {properties:?}"
835                                ),
836                            });
837                        }
838                    }
839                }
840            }
841        }
842        Ok(())
843    }
844}
845
846/// A schema constraint a [`NativeGraph`] enforces at transaction commit
847/// — the Neo4j-parity set: UNIQUE, property EXISTS, and
848/// NODE KEY.
849#[derive(Debug, Clone, PartialEq, Eq)]
850pub enum Constraint {
851    /// Among nodes of `kind`, the value of `property` must be unique. Nodes of
852    /// that kind that do not carry the property are not constrained.
853    UniqueNodeProperty {
854        /// The node kind (label) the constraint applies to.
855        kind: String,
856        /// The property whose value must be unique within that kind.
857        property: String,
858    },
859    /// Every node of `kind` must carry `property` (Neo4j property-existence
860    /// constraint).
861    PropertyExists {
862        /// The node kind the constraint applies to.
863        kind: String,
864        /// The property every such node must have.
865        property: String,
866    },
867    /// The tuple of `properties` is unique among nodes of `kind`, **and** every
868    /// such node must carry all of them — Neo4j's NODE KEY (existence +
869    /// uniqueness of the combination).
870    NodeKey {
871        /// The node kind the constraint applies to.
872        kind: String,
873        /// The properties whose combination forms the key.
874        properties: Vec<String>,
875    },
876}
877
878/// The details of a [`Constraint`] that was violated: the node kind and a
879/// human-readable description.
880#[derive(Debug, Clone, PartialEq, Eq)]
881pub struct ConstraintViolation {
882    /// The node kind whose constraint was violated.
883    pub kind: String,
884    /// A human-readable description of the violation.
885    pub message: String,
886}
887
888impl std::fmt::Display for ConstraintViolation {
889    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
890        write!(
891            f,
892            "constraint on `{}` violated: {}",
893            self.kind, self.message
894        )
895    }
896}
897
898impl std::error::Error for ConstraintViolation {}
899
900/// Why a [`NativeTx::commit`] failed. Both cases leave the graph unchanged and
901/// the transaction's writes discarded. A local error type, so the crate-wide
902/// [`CoreError`] is not widened.
903#[derive(Debug, Clone, PartialEq, Eq)]
904pub enum CommitError {
905    /// The graph changed since the transaction began (optimistic conflict);
906    /// retry against the new state.
907    Conflict,
908    /// The transaction's writes would violate a declared [`Constraint`].
909    Constraint(ConstraintViolation),
910    /// Writing the transaction to the write-ahead log failed (durable engine
911    /// only). The transaction is not applied; the message is the I/O error.
912    Io(String),
913    /// Two-phase commit: a transaction is prepared, and every other
914    /// write is refused until it is resolved (the prepared fence). Retryable;
915    /// carries the pending global transaction ids.
916    PreparedPending(Vec<String>),
917}
918
919impl std::fmt::Display for CommitError {
920    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
921        match self {
922            CommitError::Conflict => write!(
923                f,
924                "transaction conflict: the graph changed since the transaction began; retry"
925            ),
926            CommitError::Constraint(v) => write!(f, "{v}"),
927            CommitError::Io(e) => write!(f, "write-ahead log write failed: {e}"),
928            CommitError::PreparedPending(gids) => write!(
929                f,
930                "writes are paused while prepared transaction(s) {} await resolution; retry",
931                gids.join(", ")
932            ),
933        }
934    }
935}
936
937impl std::error::Error for CommitError {}
938
939/// Why [`NativeGraph::tx_prepare`] failed. Every case closes the
940/// transaction and leaves nothing prepared.
941#[derive(Debug, Clone, PartialEq, Eq)]
942pub enum PrepareError {
943    /// The id names no open registered transaction (never begun, or already
944    /// committed, rolled back or prepared).
945    UnknownTransaction,
946    /// The graph changed since the transaction began (optimistic conflict).
947    Conflict,
948    /// The transaction's writes would violate a declared [`Constraint`].
949    Constraint(ConstraintViolation),
950    /// A transaction is already prepared under this `gid`.
951    DuplicateGid(String),
952    /// Another transaction is prepared; the fence refuses this one too.
953    PreparedPending(Vec<String>),
954    /// Writing the `Prepare` record failed; nothing was prepared.
955    Io(String),
956}
957
958impl std::fmt::Display for PrepareError {
959    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
960        match self {
961            PrepareError::UnknownTransaction => {
962                write!(f, "unknown or already-closed transaction")
963            }
964            PrepareError::Conflict => write!(
965                f,
966                "transaction conflict: the graph changed since the transaction began; retry"
967            ),
968            PrepareError::Constraint(v) => write!(f, "{v}"),
969            PrepareError::DuplicateGid(gid) => {
970                write!(f, "a transaction is already prepared as {gid:?}")
971            }
972            PrepareError::PreparedPending(gids) => write!(
973                f,
974                "writes are paused while prepared transaction(s) {} await resolution; retry",
975                gids.join(", ")
976            ),
977            PrepareError::Io(e) => write!(f, "write-ahead log write failed: {e}"),
978        }
979    }
980}
981
982impl std::error::Error for PrepareError {}
983
984/// Why [`NativeGraph::commit_prepared`] / [`NativeGraph::rollback_prepared`]
985/// failed.
986#[derive(Debug, Clone, PartialEq, Eq)]
987pub enum ResolveError {
988    /// No transaction is prepared under this `gid` (never prepared, or
989    /// already resolved).
990    UnknownGid(String),
991    /// The server rolled the transaction back heuristically (the opt-in
992    /// prepared-transaction timeout), so it cannot be committed: the
993    /// coordinator's decision was overridden and must be reconciled.
994    HeuristicRollback(String),
995    /// Writing the resolution record failed; the transaction stays prepared
996    /// and the call can be retried.
997    Io(String),
998}
999
1000impl std::fmt::Display for ResolveError {
1001    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1002        match self {
1003            ResolveError::UnknownGid(gid) => write!(f, "no transaction is prepared as {gid:?}"),
1004            ResolveError::HeuristicRollback(gid) => write!(
1005                f,
1006                "transaction {gid:?} was rolled back heuristically after the prepared-transaction \
1007                 timeout; it cannot be committed"
1008            ),
1009            ResolveError::Io(e) => write!(f, "write-ahead log write failed: {e}"),
1010        }
1011    }
1012}
1013
1014impl std::error::Error for ResolveError {}
1015
1016/// One prepared transaction, as reported by [`NativeGraph::list_prepared`].
1017#[derive(Debug, Clone, PartialEq, Eq)]
1018pub struct PreparedInfo {
1019    /// The coordinator's global transaction id.
1020    pub gid: String,
1021    /// When it was prepared (Unix ms).
1022    pub prepared_at_ms: i64,
1023    /// Number of write operations in its write set.
1024    pub op_count: usize,
1025}
1026
1027/// A prepared transaction's durable state inside [`Inner`].
1028#[derive(Debug, Clone)]
1029struct PreparedEntry {
1030    prepared_at_ms: i64,
1031    ops: Vec<WalOp>,
1032}
1033
1034/// One entry in the write-ahead log: the durable,
1035/// replayable record of a single graph mutation. Upserts carry the **applied**
1036/// record (id/uuid/timestamps already assigned) so replay is deterministic and
1037/// never regenerates them; deletes carry the id. Appended in commit order and
1038/// replayed in order by [`NativeGraph::replay`] to reconstruct the in-memory
1039/// graph after a restart.
1040#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
1041pub enum WalOp {
1042    /// Insert or replace a node (create and update both log this).
1043    UpsertNode(Node),
1044    /// Delete a node (and, on replay, cascade its incident edges).
1045    DeleteNode(u64),
1046    /// Insert or replace an edge (create and update both log this).
1047    UpsertEdge(Edge),
1048    /// Delete an edge.
1049    DeleteEdge(u64),
1050    /// Insert or replace a node's embedding vector. The durable,
1051    /// typed embedding store — independent of node `properties`, keyed by node
1052    /// id.
1053    SetEmbedding(u64, Vec<f32>),
1054    /// Delete a node's embedding (idempotent).
1055    DeleteEmbedding(u64),
1056    /// Two-phase commit: a transaction prepared under `gid`, with its
1057    /// write set. Applied to the graph only when a matching
1058    /// [`WalOp::CommitPrepared`] follows; unresolved at the end of the log, it
1059    /// is restored as prepared (and the write fence is raised).
1060    Prepare {
1061        /// The coordinator's global transaction id.
1062        gid: String,
1063        /// When it was prepared (Unix ms).
1064        prepared_at_ms: i64,
1065        /// The transaction's write set, in commit order.
1066        ops: Vec<WalOp>,
1067    },
1068    /// Two-phase commit: apply the write set prepared under `gid`.
1069    CommitPrepared {
1070        /// The global transaction id being committed.
1071        gid: String,
1072    },
1073    /// Two-phase commit: discard the write set prepared under `gid`.
1074    RollbackPrepared {
1075        /// The global transaction id being rolled back.
1076        gid: String,
1077        /// `true` for a heuristic rollback taken by the server after the
1078        /// prepared-transaction timeout, not decided by the coordinator. The
1079        /// outcome is remembered, so a late `commit_prepared` reports
1080        /// [`ResolveError::HeuristicRollback`]. Absent in older records.
1081        #[serde(default, skip_serializing_if = "std::ops::Not::not")]
1082        heuristic: bool,
1083    },
1084}
1085
1086/// The graph engine: an in-memory [`GraphEngine`], optionally durable through
1087/// a write-ahead log ([`open_durable`](Self::open_durable)). See the
1088/// [module docs](self) for the guarantees.
1089#[derive(Default)]
1090pub struct NativeGraph {
1091    inner: RwLock<Arc<Inner>>,
1092    /// The write-ahead log sink, when the engine was opened durable via
1093    /// [`open_durable`](Self::open_durable). `None` for an in-memory-only
1094    /// engine ([`new`](Self::new)). Each direct write appends and fsyncs before
1095    /// returning, so an acknowledged write survives a crash.
1096    #[cfg(not(target_arch = "wasm32"))]
1097    wal: Option<std::sync::Mutex<WalSink>>,
1098    /// Registered (session-owned) transactions, keyed by [`NativeTxId`] —
1099    /// the executor-facing form of [`Self::begin`]: a Bolt
1100    /// session keeps only the id between statements and re-derives an
1101    /// ephemeral [`NativeTxEngine`] per statement, so no borrow outlives a
1102    /// statement. Slots are removed by commit / rollback.
1103    reg_txs: std::sync::Mutex<HashMap<u64, TxSlot>>,
1104    /// Monotonic source of registered-transaction ids (starts at 1).
1105    next_reg_tx: std::sync::atomic::AtomicU64,
1106    /// The ordered change-feed: every committed write, in commit order, as a
1107    /// [`WalOp`]. Secondary
1108    /// indexes off the graph seam (FTS, vector) keep themselves current by
1109    /// **tailing** this feed — snapshot the graph once, then apply each change
1110    /// since a cursor — instead of coupling to the write path. See
1111    /// [`changes_since`](Self::changes_since).
1112    feed: std::sync::Mutex<ChangeFeed>,
1113    /// Group-commit coordinator for durable writes: one `fsync`
1114    /// amortized across every write concurrently enqueued, so autocommit write
1115    /// throughput under concurrency is not one-fsync-per-edge. Idle for an
1116    /// in-memory engine (nothing to flush).
1117    #[cfg(not(target_arch = "wasm32"))]
1118    group: GroupCommit,
1119    /// This replica's stable identity (the multi-writer/P2P substrate).
1120    /// Persisted next to the WAL as `origin.json` for a durable
1121    /// store ([`open_durable`](Self::open_durable)); a fresh random ephemeral
1122    /// id for an in-memory one. Paired with [`clock`] it stamps autocommit
1123    /// writes with a total, causally-ordered [`Stamp`].
1124    origin: OriginId,
1125    /// The Hybrid Logical Clock issuing causal timestamps for this replica.
1126    clock: std::sync::Mutex<HlcClock>,
1127    /// The causal [`Stamp`] of each **live** node/edge's last autocommit write
1128    ///. A create/update sets it, a delete moves it into
1129    /// [`tombstones`]; queried via [`stamp_of`]. In-memory only for now (rebuilt
1130    /// as writes happen after a restart); stamps are not written to the WAL.
1131    ///
1132    /// [`tombstones`]: Self::tombstones
1133    stamps: RwLock<HashMap<StampTarget, Stamp>>,
1134    /// The [`Tomb`] of each **deleted** node/edge — its causal [`Stamp`] plus the
1135    /// entity's `uuid`. Kept disjoint from [`stamps`]: a target is
1136    /// either live (in `stamps`) or deleted (here), and the greater stamp wins.
1137    /// Tombstones let a [`Delta`] carry deletes so a peer converges on removals,
1138    /// not just upserts; the stored `uuid` lets the receiver remap the deletion
1139    /// onto its own local id. In-memory only, like `stamps`.
1140    ///
1141    /// [`stamps`]: Self::stamps
1142    tombstones: RwLock<HashMap<StampTarget, Tomb>>,
1143    /// The held exclusive-open lock for a durable store: the open
1144    /// lock-sidecar file whose advisory `flock`/`LockFileEx` this handle owns.
1145    /// Kept for the engine's whole lifetime so a second `open_durable` on the
1146    /// same path fails with [`CoreError::Locked`](crate::error::CoreError::Locked)
1147    /// instead of interleaving WAL appends and corrupting the log. Dropping the
1148    /// handle (or the process dying) closes the fd and releases the lock, so a
1149    /// crash never leaves a stale lock that would block the restart flow.
1150    /// `None` for an in-memory engine — nothing on disk to guard.
1151    ///
1152    /// Held purely for its `Drop` side-effect (releasing the advisory lock), so
1153    /// it is intentionally never read — the leading underscore keeps the
1154    /// dead-code lint quiet without an `allow`.
1155    #[cfg(not(target_arch = "wasm32"))]
1156    _lock: Option<std::fs::File>,
1157}
1158
1159/// A tombstone: the causal [`Stamp`] of a delete plus the deleted entity's
1160/// `uuid`, so the deletion can be carried in a [`Delta`] and remapped by `uuid`
1161/// on the receiver. Serializable so the tombstone table can be
1162/// checkpointed to a sidecar and survive a restart.
1163#[derive(Debug, Clone, Copy, Serialize, Deserialize)]
1164struct Tomb {
1165    stamp: Stamp,
1166    uuid: [u8; 16],
1167}
1168
1169/// `uuid → receiver-local-id` resolution for a single [`NativeGraph::apply_delta`]
1170/// batch. Indexes the receiver's live nodes/edges and its
1171/// tombstones once, then stays current as new ids are minted, so every change in
1172/// the delta is remapped from the sender's id space into ours by `uuid`.
1173struct Remap {
1174    /// Live node `uuid → local id`.
1175    node: HashMap<[u8; 16], u64>,
1176    /// Live edge `uuid → local id`.
1177    edge: HashMap<[u8; 16], u64>,
1178    /// Deleted `uuid → its anchored [`StampTarget`]` (the local id the tombstone
1179    /// is keyed by), for LWW against a re-delivered or superseding write.
1180    tomb: HashMap<[u8; 16], StampTarget>,
1181}
1182
1183/// A node or edge addressed by id, for the per-entity causal stamp table
1184/// ([`NativeGraph::stamp_of`]). Serializable so the tombstone table can be
1185/// checkpointed to disk.
1186#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
1187pub enum StampTarget {
1188    /// The node with this id.
1189    Node(u64),
1190    /// The edge with this id.
1191    Edge(u64),
1192}
1193
1194/// Mint a fresh random replica [`OriginId`] from the random bits of a UUIDv7
1195/// (its last 8 bytes are host-random). Collision-safe enough to identify a
1196/// replica without coordination.
1197fn mint_origin() -> OriginId {
1198    let uuid = crate::model::new_uuid_v7();
1199    let mut tail = [0u8; 8];
1200    tail.copy_from_slice(&uuid[8..16]);
1201    OriginId(u64::from_be_bytes(tail))
1202}
1203
1204/// The replica-identity sidecar path, next to the WAL file.
1205#[cfg(not(target_arch = "wasm32"))]
1206fn origin_sidecar(wal_path: &std::path::Path) -> std::path::PathBuf {
1207    wal_path.with_file_name("origin.json")
1208}
1209
1210/// Load the persisted replica origin from `sidecar`, or mint and persist a new
1211/// one. A missing or unparseable file mints a fresh id (best-effort persist: a
1212/// write failure only means a new id on the next boot, never a hard error).
1213#[cfg(not(target_arch = "wasm32"))]
1214fn load_or_mint_origin(sidecar: &std::path::Path) -> OriginId {
1215    if let Ok(text) = std::fs::read_to_string(sidecar) {
1216        if let Ok(id) = serde_json::from_str::<OriginId>(text.trim()) {
1217            return id;
1218        }
1219    }
1220    let id = mint_origin();
1221    let _ = persist_origin(sidecar, id);
1222    id
1223}
1224
1225/// Persist `origin` to `sidecar` atomically (temp file, then rename). The origin
1226/// is not a secret, so no restrictive mode is applied.
1227#[cfg(not(target_arch = "wasm32"))]
1228fn persist_origin(sidecar: &std::path::Path, origin: OriginId) -> std::io::Result<()> {
1229    // `OriginId` is a transparent newtype: it serializes as the bare u64.
1230    let json = origin.0.to_string();
1231    let tmp = sidecar.with_extension("json.tmp");
1232    std::fs::write(&tmp, json.as_bytes())?;
1233    std::fs::rename(&tmp, sidecar)
1234}
1235
1236/// The tombstone-checkpoint sidecar path, next to the WAL file.
1237#[cfg(not(target_arch = "wasm32"))]
1238fn tombstone_sidecar(wal_path: &std::path::Path) -> std::path::PathBuf {
1239    wal_path.with_file_name("tombstones.json")
1240}
1241
1242/// The exclusive-open lock sidecar path: the WAL path with a `.lock` suffix
1243/// appended (`native.wal` → `native.wal.lock`). Derived from the *full*
1244/// WAL filename — not a fixed name in the directory — so two distinct stores
1245/// sharing one directory get distinct locks. A stable companion file that
1246/// `compact_wal` never renames, so the advisory lock held on it survives
1247/// compaction — unlike an flock on the WAL inode, which a compaction rename
1248/// would swap out from under the guard.
1249#[cfg(not(target_arch = "wasm32"))]
1250fn lock_sidecar(wal_path: &std::path::Path) -> std::path::PathBuf {
1251    let mut name = wal_path.as_os_str().to_os_string();
1252    name.push(".lock");
1253    std::path::PathBuf::from(name)
1254}
1255
1256/// Take an exclusive, non-blocking advisory lock on `lock_path`, creating the
1257/// sidecar if absent, and return the held file handle. The lock guards a
1258/// durable store against a second `open_durable` on the same path: a contended
1259/// acquisition returns [`CoreError::Locked`], any other failure
1260/// [`CoreError::Io`]. The lock is *advisory* and tied to the open file
1261/// description, so it is released automatically when the handle drops or the
1262/// process dies — a crash never strands a stale lock that would block a restart.
1263#[cfg(all(unix, not(target_arch = "wasm32")))]
1264fn acquire_exclusive_lock(lock_path: &std::path::Path) -> Result<std::fs::File> {
1265    use std::os::unix::io::AsRawFd;
1266    let file = std::fs::OpenOptions::new()
1267        .create(true)
1268        .read(true)
1269        .write(true)
1270        .truncate(false)
1271        .open(lock_path)?;
1272    // SAFETY: `flock` takes a valid open fd and the two documented flags; it
1273    // has no memory-safety preconditions. `file` keeps the fd alive.
1274    let rc = unsafe { libc::flock(file.as_raw_fd(), libc::LOCK_EX | libc::LOCK_NB) };
1275    if rc != 0 {
1276        let err = std::io::Error::last_os_error();
1277        // `EWOULDBLOCK` (== `EAGAIN` on Linux/macOS) means another handle holds
1278        // the lock — the double-open we exist to reject.
1279        if err.raw_os_error() == Some(libc::EWOULDBLOCK) {
1280            return Err(CoreError::Locked);
1281        }
1282        return Err(CoreError::Io(err));
1283    }
1284    Ok(file)
1285}
1286
1287/// Windows counterpart of [`acquire_exclusive_lock`] using `LockFileEx` with
1288/// `LOCKFILE_EXCLUSIVE_LOCK | LOCKFILE_FAIL_IMMEDIATELY`. Byte-range lock
1289/// over the whole file; released when the handle closes or the process exits.
1290#[cfg(all(windows, not(target_arch = "wasm32")))]
1291fn acquire_exclusive_lock(lock_path: &std::path::Path) -> Result<std::fs::File> {
1292    use std::os::windows::io::AsRawHandle;
1293    use windows_sys::Win32::Storage::FileSystem::{
1294        LockFileEx, LOCKFILE_EXCLUSIVE_LOCK, LOCKFILE_FAIL_IMMEDIATELY,
1295    };
1296    use windows_sys::Win32::System::IO::OVERLAPPED;
1297    let file = std::fs::OpenOptions::new()
1298        .create(true)
1299        .read(true)
1300        .write(true)
1301        .truncate(false)
1302        .open(lock_path)?;
1303    // SAFETY: zeroed `OVERLAPPED` is the documented way to lock from offset 0;
1304    // the handle is valid and kept alive by `file`.
1305    let mut overlapped: OVERLAPPED = unsafe { std::mem::zeroed() };
1306    let ok = unsafe {
1307        LockFileEx(
1308            file.as_raw_handle() as _,
1309            LOCKFILE_EXCLUSIVE_LOCK | LOCKFILE_FAIL_IMMEDIATELY,
1310            0,
1311            u32::MAX,
1312            u32::MAX,
1313            &mut overlapped,
1314        )
1315    };
1316    if ok == 0 {
1317        // Contention surfaces as `ERROR_LOCK_VIOLATION`; treat any immediate
1318        // failure to acquire as a locked store.
1319        return Err(CoreError::Locked);
1320    }
1321    Ok(file)
1322}
1323
1324/// Fallback for the rare non-unix, non-windows, non-wasm target: open the
1325/// sidecar without an OS lock (best-effort, no cross-handle guard) so the
1326/// durable engine still builds and runs there.
1327#[cfg(all(not(unix), not(windows), not(target_arch = "wasm32")))]
1328fn acquire_exclusive_lock(lock_path: &std::path::Path) -> Result<std::fs::File> {
1329    Ok(std::fs::OpenOptions::new()
1330        .create(true)
1331        .read(true)
1332        .write(true)
1333        .truncate(false)
1334        .open(lock_path)?)
1335}
1336
1337/// Load the checkpointed tombstone table from `sidecar`, or an empty map if it
1338/// is missing or unparseable (best-effort: a lost checkpoint only risks a
1339/// resurrection on the next sync, which a full re-sync heals). Stored as a flat
1340/// list of pairs because a JSON object cannot key on the [`StampTarget`] enum.
1341#[cfg(not(target_arch = "wasm32"))]
1342fn load_tombstones(sidecar: &std::path::Path) -> HashMap<StampTarget, Tomb> {
1343    let mut map = HashMap::new();
1344    if let Ok(bytes) = std::fs::read(sidecar) {
1345        if let Ok(entries) = serde_json::from_slice::<Vec<(StampTarget, Tomb)>>(&bytes) {
1346            for (target, tomb) in entries {
1347                map.insert(target, tomb);
1348            }
1349        }
1350    }
1351    map
1352}
1353
1354/// Persist the tombstone table to `sidecar` atomically (temp file, then rename),
1355/// **without** `fsync` — a best-effort checkpoint, not an acknowledged write.
1356#[cfg(not(target_arch = "wasm32"))]
1357fn persist_tombstones(
1358    sidecar: &std::path::Path,
1359    entries: &[(StampTarget, Tomb)],
1360) -> std::io::Result<()> {
1361    let json = serde_json::to_vec(entries).map_err(std::io::Error::other)?;
1362    let tmp = sidecar.with_extension("json.tmp");
1363    std::fs::write(&tmp, &json)?;
1364    std::fs::rename(&tmp, sidecar)
1365}
1366
1367/// The in-memory tail of committed [`WalOp`]s backing [`NativeGraph`]'s
1368/// change-feed. `start_seq` is the sequence number *before* `ops[0]`, so the
1369/// change at index `i` carries sequence `start_seq + i + 1` and the current
1370/// head is `start_seq + ops.len()`. [`NativeGraph::trim_before`] drops
1371/// consumed history by advancing `start_seq` and draining `ops`.
1372#[derive(Default)]
1373struct ChangeFeed {
1374    start_seq: u64,
1375    ops: Vec<WalOp>,
1376}
1377
1378/// A batch of change-feed entries plus the cursor to resume from.
1379///
1380/// Returned by [`NativeGraph::changes_since`]. `cursor` is the sequence number
1381/// of the last change in `ops` (or the caller's cursor when `ops` is empty), so
1382/// the next poll is `changes_since(batch.cursor)`.
1383#[derive(Debug, Clone)]
1384pub struct ChangeBatch {
1385    /// The resume cursor — pass to the next [`changes_since`](NativeGraph::changes_since).
1386    pub cursor: u64,
1387    /// The changes after the requested cursor, in commit order.
1388    pub ops: Vec<WalOp>,
1389    /// `true` when the requested cursor was older than the retained history, so
1390    /// some changes were skipped and the subscriber must re-snapshot the graph
1391    /// before applying `ops`. Always `false` until history trimming lands.
1392    pub lagged: bool,
1393}
1394
1395/// The write-ahead-log file plus its path (needed so [`compact_wal`] can
1396/// atomically rewrite the log in place).
1397///
1398/// [`compact_wal`]: NativeGraph::compact_wal
1399#[cfg(not(target_arch = "wasm32"))]
1400struct WalSink {
1401    path: std::path::PathBuf,
1402    file: std::fs::File,
1403}
1404
1405/// One writer's pending durable commit: its ops, the pre-serialized WAL line,
1406/// and the commit sequence that fixes its order in the log.
1407#[cfg(not(target_arch = "wasm32"))]
1408struct PendingCommit {
1409    seq: u64,
1410    ops: Vec<WalOp>,
1411    line: String,
1412}
1413
1414/// Group-commit queue. Concurrent durable writers enqueue here; one elected
1415/// leader flushes the whole pending batch with a **single** `fsync`, so N
1416/// concurrent acknowledged writes cost far fewer than N fsyncs. Ordering is by
1417/// `seq` (enqueue order), the same total order the WAL always had.
1418#[cfg(not(target_arch = "wasm32"))]
1419struct CommitQueue {
1420    pending: Vec<PendingCommit>,
1421    /// Next commit sequence to hand out. Sequences start at 1 so the initial
1422    /// `durable_seq = 0` means "nothing durable yet" — a writer with seq ≥ 1 is
1423    /// never mistaken for already-flushed before its group runs.
1424    next_seq: u64,
1425    /// Highest sequence whose WAL write + fsync has completed.
1426    durable_seq: u64,
1427    /// A leader is currently flushing; other writers wait.
1428    leader: bool,
1429    /// A flush failed: the WAL is unusable, so every in-flight and future
1430    /// write fails rather than silently dropping durability.
1431    broken: bool,
1432}
1433
1434#[cfg(not(target_arch = "wasm32"))]
1435impl Default for CommitQueue {
1436    fn default() -> Self {
1437        Self {
1438            pending: Vec::new(),
1439            next_seq: 1,
1440            durable_seq: 0,
1441            leader: false,
1442            broken: false,
1443        }
1444    }
1445}
1446
1447/// The group-commit coordinator. `std::sync::Condvar` has no `Default`, so this
1448/// wrapper carries the manual `Default` that keeps `NativeGraph`'s derive.
1449#[cfg(not(target_arch = "wasm32"))]
1450struct GroupCommit {
1451    queue: std::sync::Mutex<CommitQueue>,
1452    committed: std::sync::Condvar,
1453    /// Total fsyncs the WAL has performed since open — the coalescing metric
1454    /// ([`NativeGraph::wal_fsync_count`]). A whole group counts as one.
1455    fsyncs: std::sync::atomic::AtomicU64,
1456}
1457
1458#[cfg(not(target_arch = "wasm32"))]
1459impl Default for GroupCommit {
1460    fn default() -> Self {
1461        Self {
1462            queue: std::sync::Mutex::new(CommitQueue::default()),
1463            committed: std::sync::Condvar::new(),
1464            fsyncs: std::sync::atomic::AtomicU64::new(0),
1465        }
1466    }
1467}
1468
1469/// The error every in-flight and future durable write returns once a group
1470/// flush has failed — the WAL is unusable, so failing loudly beats silently
1471/// dropping durability.
1472#[cfg(not(target_arch = "wasm32"))]
1473fn wal_broken_err() -> CoreError {
1474    std::io::Error::other("durable WAL is broken: a prior group commit failed to persist").into()
1475}
1476
1477impl NativeGraph {
1478    /// Create an empty in-memory engine. Ids start at 1.
1479    pub fn new() -> Self {
1480        // `Default` leaves the origin at `0`; mint a fresh ephemeral identity so
1481        // two in-memory graphs stamp with distinct origins (issue #389).
1482        Self {
1483            origin: mint_origin(),
1484            ..Self::default()
1485        }
1486    }
1487
1488    /// This replica's stable [`OriginId`]. Persisted next to the
1489    /// WAL for a durable store, ephemeral for an in-memory one.
1490    pub fn origin_id(&self) -> OriginId {
1491        self.origin
1492    }
1493
1494    /// Issue the next causal [`Stamp`] `(hlc, origin)`: advance the Hybrid
1495    /// Logical Clock and pair it with this replica's origin. Strictly
1496    /// increasing — a sequence of local writes is totally ordered.
1497    pub fn next_stamp(&self) -> Stamp {
1498        let hlc = self.clock.lock().unwrap_or_else(|e| e.into_inner()).now();
1499        Stamp::new(hlc, self.origin)
1500    }
1501
1502    /// The causal [`Stamp`] of `target`'s last autocommit write, or `None` if it
1503    /// is absent (never written, or deleted). Stamps live in memory only, so
1504    /// this starts empty after a restart.
1505    pub fn stamp_of(&self, target: StampTarget) -> Option<Stamp> {
1506        self.stamps
1507            .read()
1508            .unwrap_or_else(|e| e.into_inner())
1509            .get(&target)
1510            .copied()
1511    }
1512
1513    /// Record `target`'s causal version after a create/update: it becomes live,
1514    /// clearing any tombstone (a fresh write resurrects a previously-deleted id).
1515    fn stamp_write(&self, target: StampTarget) {
1516        let stamp = self.next_stamp();
1517        self.stamps
1518            .write()
1519            .unwrap_or_else(|e| e.into_inner())
1520            .insert(target, stamp);
1521        self.tombstones
1522            .write()
1523            .unwrap_or_else(|e| e.into_inner())
1524            .remove(&target);
1525    }
1526
1527    /// Record `target`'s causal version after a delete: it moves from live into
1528    /// the tombstone table (tagged with the deleted entity's `uuid`), so a
1529    /// [`Delta`] can carry the deletion to a peer and the peer can remap it.
1530    fn stamp_tombstone(&self, target: StampTarget, uuid: [u8; 16]) {
1531        let stamp = self.next_stamp();
1532        self.stamps
1533            .write()
1534            .unwrap_or_else(|e| e.into_inner())
1535            .remove(&target);
1536        self.tombstones
1537            .write()
1538            .unwrap_or_else(|e| e.into_inner())
1539            .insert(target, Tomb { stamp, uuid });
1540    }
1541
1542    /// Mark `target` live at `stamp` (an applied upsert): set its live stamp and
1543    /// clear any tombstone, keeping the two tables disjoint.
1544    fn mark_live(&self, target: StampTarget, stamp: Stamp) {
1545        self.stamps
1546            .write()
1547            .unwrap_or_else(|e| e.into_inner())
1548            .insert(target, stamp);
1549        self.tombstones
1550            .write()
1551            .unwrap_or_else(|e| e.into_inner())
1552            .remove(&target);
1553    }
1554
1555    /// Mark `target` deleted at `stamp` (an applied tombstone): set its tombstone
1556    /// and clear any live stamp.
1557    fn mark_tombstoned(&self, target: StampTarget, stamp: Stamp, uuid: [u8; 16]) {
1558        self.tombstones
1559            .write()
1560            .unwrap_or_else(|e| e.into_inner())
1561            .insert(target, Tomb { stamp, uuid });
1562        self.stamps
1563            .write()
1564            .unwrap_or_else(|e| e.into_inner())
1565            .remove(&target);
1566    }
1567
1568    /// Advance the local HLC past `stamp` so a subsequent local write is causally
1569    /// after the merged change.
1570    fn observe(&self, stamp: Stamp) {
1571        self.clock
1572            .lock()
1573            .unwrap_or_else(|e| e.into_inner())
1574            .observe(stamp.hlc());
1575    }
1576
1577    /// Best-effort checkpoint of the tombstone table to a sidecar next to the WAL
1578    ///, so deletes converge across a restart: without it, a
1579    /// restarted replica has neither a deleted entity nor its tombstone, and a
1580    /// peer still holding the entity would **resurrect** it on the next sync.
1581    ///
1582    /// Durable stores only (an in-memory graph has nowhere to write). No
1583    /// `fsync` and every I/O error is swallowed — a lost checkpoint only widens
1584    /// the resurrection window, which a full re-sync heals, so it is not worth a
1585    /// flush on the write path. Live stamps and the version vector are **not**
1586    /// persisted (an accepted tradeoff: a restarted replica re-syncs upserts in
1587    /// full).
1588    #[cfg(not(target_arch = "wasm32"))]
1589    fn checkpoint_tombstones(&self) {
1590        let Some(path) = self
1591            .wal
1592            .as_ref()
1593            .map(|w| w.lock().unwrap_or_else(|e| e.into_inner()).path.clone())
1594        else {
1595            return;
1596        };
1597        let entries: Vec<(StampTarget, Tomb)> = self
1598            .tombstones
1599            .read()
1600            .unwrap_or_else(|e| e.into_inner())
1601            .iter()
1602            .map(|(target, tomb)| (*target, *tomb))
1603            .collect();
1604        let _ = persist_tombstones(&tombstone_sidecar(&path), &entries);
1605    }
1606
1607    /// No durable sidecar on wasm (no WAL); tombstones are in-memory only.
1608    #[cfg(target_arch = "wasm32")]
1609    fn checkpoint_tombstones(&self) {}
1610
1611    /// The stamp governing `target`'s current LWW state — its live stamp if the
1612    /// entity exists, otherwise its tombstone stamp if it was deleted, else
1613    /// `None`. The two tables are disjoint, so at most one is present.
1614    fn current_stamp(&self, target: StampTarget) -> Option<Stamp> {
1615        if let Some(s) = self.stamp_of(target) {
1616            return Some(s);
1617        }
1618        self.tombstones
1619            .read()
1620            .unwrap_or_else(|e| e.into_inner())
1621            .get(&target)
1622            .map(|t| t.stamp)
1623    }
1624
1625    /// This replica's [`VersionVector`] — the greatest causal
1626    /// [`Stamp`] seen per origin across every live entity
1627    ///. A peer hands this to [`delta_since`] to learn
1628    /// the minimal set of writes it is missing.
1629    ///
1630    /// Built from the in-memory stamp table, so (like the table itself) it
1631    /// reflects only writes seen since the process started.
1632    ///
1633    /// [`delta_since`]: Self::delta_since
1634    pub fn version_vector(&self) -> VersionVector {
1635        let mut vv = VersionVector::new();
1636        for stamp in self
1637            .stamps
1638            .read()
1639            .unwrap_or_else(|e| e.into_inner())
1640            .values()
1641        {
1642            vv.observe(*stamp);
1643        }
1644        // Tombstones are writes too: folding them in tells a peer we have already
1645        // seen the delete, so it never resends the upsert we have since removed.
1646        for tomb in self
1647            .tombstones
1648            .read()
1649            .unwrap_or_else(|e| e.into_inner())
1650            .values()
1651        {
1652            vv.observe(tomb.stamp);
1653        }
1654        vv
1655    }
1656
1657    /// The minimal [`Delta`] a holder of `remote` is missing: every live upsert
1658    /// and every tombstone whose stamp `remote` has not already observed
1659    ///. An empty `remote`
1660    /// ([`VersionVector::new`]) returns the entire state — a full bootstrap.
1661    ///
1662    /// Deletes are carried as [`StampedChange::DeleteNode`] /
1663    /// [`StampedChange::DeleteEdge`] tombstones, so a delta converges removals as
1664    /// well as upserts (see the [module docs]). The returned records are deep
1665    /// clones, safe to serialise and send.
1666    ///
1667    /// [module docs]: crate::delta
1668    pub fn delta_since(&self, remote: &VersionVector) -> Delta {
1669        // Snapshot the missing targets under the stamp locks, then resolve
1670        // records under the graph lock — never hold both at once (the write path
1671        // takes them separately, so this keeps a single, consistent lock order).
1672        let missing_live: Vec<(StampTarget, Stamp)> = {
1673            let stamps = self.stamps.read().unwrap_or_else(|e| e.into_inner());
1674            stamps
1675                .iter()
1676                .filter(|(_, stamp)| !remote.dominates(**stamp))
1677                .map(|(target, stamp)| (*target, *stamp))
1678                .collect()
1679        };
1680        // Tombstones carry the deleted entity's uuid so the receiver can remap.
1681        let missing_dead: Vec<(StampTarget, Tomb)> = {
1682            let tombstones = self.tombstones.read().unwrap_or_else(|e| e.into_inner());
1683            tombstones
1684                .iter()
1685                .filter(|(_, tomb)| !remote.dominates(tomb.stamp))
1686                .map(|(target, tomb)| (*target, *tomb))
1687                .collect()
1688        };
1689        let inner = read(&self.inner);
1690        let mut changes = Vec::with_capacity(missing_live.len() + missing_dead.len());
1691        for (target, stamp) in missing_live {
1692            match target {
1693                StampTarget::Node(id) => {
1694                    if let Some(node) = inner.get_node_arc(id) {
1695                        changes.push(StampedChange::Node((*node).clone(), stamp));
1696                    }
1697                }
1698                StampTarget::Edge(id) => {
1699                    // Resolve the endpoints to uuids so the receiver can remap
1700                    // them; skip an edge whose endpoints have gone missing.
1701                    if let Some(edge) = inner.get_edge_arc(id) {
1702                        let (from_uuid, to_uuid) = (
1703                            inner.get_node_arc(edge.from_id).map(|n| n.uuid),
1704                            inner.get_node_arc(edge.to_id).map(|n| n.uuid),
1705                        );
1706                        if let (Some(from_uuid), Some(to_uuid)) = (from_uuid, to_uuid) {
1707                            changes.push(StampedChange::Edge(StampedEdge {
1708                                edge: (*edge).clone(),
1709                                from_uuid,
1710                                to_uuid,
1711                                stamp,
1712                            }));
1713                        }
1714                    }
1715                }
1716            }
1717        }
1718        for (target, tomb) in missing_dead {
1719            changes.push(match target {
1720                StampTarget::Node(_) => StampedChange::DeleteNode(tomb.uuid, tomb.stamp),
1721                StampTarget::Edge(_) => StampedChange::DeleteEdge(tomb.uuid, tomb.stamp),
1722            });
1723        }
1724        Delta { changes }
1725    }
1726
1727    /// Fold a received [`Delta`] into this replica by Last-Writer-Wins on the
1728    /// stamp, remapping the sender's ids into our own id space by `uuid`
1729    ///. Each change is installed only if its stamp
1730    /// beats the local one for the *same `uuid`*, and the local HLC is advanced
1731    /// past every stamp seen. Idempotent — re-applying a delta changes nothing.
1732    ///
1733    /// Because node/edge ids are per-replica, identity is the `uuid` each record
1734    /// carries: a `uuid` we already hold is merged at our local id, a new `uuid`
1735    /// is minted a fresh one, and an edge's endpoints are resolved from their
1736    /// carried uuids ([`StampedEdge`]). This makes the exchange symmetric —
1737    /// independent concurrent writers converge — not just a fresh-replica
1738    /// bootstrap.
1739    ///
1740    /// Changes apply in phase order (upsert nodes, upsert edges, delete edges,
1741    /// delete nodes) so endpoints exist before an edge references them and a
1742    /// cascading node delete runs last. Each winning change is persisted to the
1743    /// WAL (durable stores only; in-memory graphs skip the durable step), so a
1744    /// merge survives a restart. See the [module docs] for the remaining
1745    /// limitations.
1746    ///
1747    /// [module docs]: crate::delta
1748    pub fn apply_delta(&self, delta: &Delta) -> Result<ApplyStats> {
1749        let mut stats = ApplyStats::default();
1750        let mut ordered: Vec<&StampedChange> = delta.changes.iter().collect();
1751        ordered.sort_by_key(|c| c.apply_phase());
1752
1753        // Index identity by uuid once: live records from the graph, deleted ones
1754        // from the tombstone table. The maps stay current as ids are minted.
1755        let mut remap = {
1756            let node;
1757            let edge;
1758            {
1759                let inner = read(&self.inner);
1760                node = inner.nodes.values().map(|n| (n.uuid, n.id)).collect();
1761                edge = inner.edges.values().map(|e| (e.uuid, e.id)).collect();
1762            }
1763            let tomb = self
1764                .tombstones
1765                .read()
1766                .unwrap_or_else(|e| e.into_inner())
1767                .iter()
1768                .map(|(target, t)| (t.uuid, *target))
1769                .collect();
1770            Remap { node, edge, tomb }
1771        };
1772
1773        // Whether any applied change mutated the tombstone table (a delete, or an
1774        // upsert that resurrected a tombstoned uuid) — gates the checkpoint below.
1775        let mut tombstones_touched = false;
1776        for change in ordered {
1777            let touches_tombstone = match change {
1778                StampedChange::DeleteNode(..) | StampedChange::DeleteEdge(..) => true,
1779                StampedChange::Node(node, _) => remap.tomb.contains_key(&node.uuid),
1780                StampedChange::Edge(se) => remap.tomb.contains_key(&se.edge.uuid),
1781            };
1782            let won = match change {
1783                StampedChange::Node(node, stamp) => {
1784                    self.apply_node_upsert(node, *stamp, &mut remap)?
1785                }
1786                StampedChange::Edge(se) => self.apply_edge_upsert(se, &mut remap)?,
1787                StampedChange::DeleteNode(uuid, stamp) => {
1788                    self.apply_delete(*uuid, *stamp, true, &mut remap)?
1789                }
1790                StampedChange::DeleteEdge(uuid, stamp) => {
1791                    self.apply_delete(*uuid, *stamp, false, &mut remap)?
1792                }
1793            };
1794            if won {
1795                stats.applied += 1;
1796                tombstones_touched |= touches_tombstone;
1797            } else {
1798                stats.skipped += 1;
1799            }
1800        }
1801        // One best-effort checkpoint per merge, only when a tombstone changed.
1802        if tombstones_touched {
1803            self.checkpoint_tombstones();
1804        }
1805        Ok(stats)
1806    }
1807
1808    /// Merge an incoming node upsert under LWW, remapping its `uuid` to a local
1809    /// id (a fresh mint if unseen). Returns whether it won.
1810    fn apply_node_upsert(&self, node: &Node, incoming: Stamp, remap: &mut Remap) -> Result<bool> {
1811        let uuid = node.uuid;
1812        let cur_target = remap
1813            .node
1814            .get(&uuid)
1815            .copied()
1816            .map(StampTarget::Node)
1817            .or_else(|| {
1818                remap
1819                    .tomb
1820                    .get(&uuid)
1821                    .copied()
1822                    .filter(|t| matches!(t, StampTarget::Node(_)))
1823            });
1824        if let Some(t) = cur_target {
1825            if self.current_stamp(t).is_some_and(|local| local >= incoming) {
1826                return Ok(false);
1827            }
1828        }
1829        // Reuse the resolved local id, else mint a fresh one; rewrite the record
1830        // to our id space before applying.
1831        let mut record = node.clone();
1832        let local_id = {
1833            let mut guard = self.write_for_commit()?;
1834            let inner = Arc::make_mut(&mut guard);
1835            let id = match cur_target {
1836                Some(StampTarget::Node(id)) => id,
1837                _ => {
1838                    inner.next_node_id += 1;
1839                    inner.next_node_id
1840                }
1841            };
1842            record.id = id;
1843            inner.apply_wal_op(WalOp::UpsertNode(record.clone()));
1844            id
1845        };
1846        self.record(&[WalOp::UpsertNode(record)])?;
1847        self.mark_live(StampTarget::Node(local_id), incoming);
1848        remap.node.insert(uuid, local_id);
1849        remap.tomb.remove(&uuid);
1850        self.observe(incoming);
1851        Ok(true)
1852    }
1853
1854    /// Merge an incoming edge upsert under LWW, remapping the edge and both
1855    /// endpoints by `uuid`. Skips (returns `false`) when an endpoint uuid is not
1856    /// yet known locally — the edge cannot be placed until its nodes arrive.
1857    fn apply_edge_upsert(&self, se: &StampedEdge, remap: &mut Remap) -> Result<bool> {
1858        let (Some(&from_local), Some(&to_local)) =
1859            (remap.node.get(&se.from_uuid), remap.node.get(&se.to_uuid))
1860        else {
1861            return Ok(false);
1862        };
1863        let uuid = se.edge.uuid;
1864        let cur_target = remap
1865            .edge
1866            .get(&uuid)
1867            .copied()
1868            .map(StampTarget::Edge)
1869            .or_else(|| {
1870                remap
1871                    .tomb
1872                    .get(&uuid)
1873                    .copied()
1874                    .filter(|t| matches!(t, StampTarget::Edge(_)))
1875            });
1876        if let Some(t) = cur_target {
1877            if self.current_stamp(t).is_some_and(|local| local >= se.stamp) {
1878                return Ok(false);
1879            }
1880        }
1881        let mut record = se.edge.clone();
1882        record.from_id = from_local;
1883        record.to_id = to_local;
1884        let local_id = {
1885            let mut guard = self.write_for_commit()?;
1886            let inner = Arc::make_mut(&mut guard);
1887            let id = match cur_target {
1888                Some(StampTarget::Edge(id)) => id,
1889                _ => {
1890                    inner.next_edge_id += 1;
1891                    inner.next_edge_id
1892                }
1893            };
1894            record.id = id;
1895            inner.apply_wal_op(WalOp::UpsertEdge(record.clone()));
1896            id
1897        };
1898        self.record(&[WalOp::UpsertEdge(record)])?;
1899        self.mark_live(StampTarget::Edge(local_id), se.stamp);
1900        remap.edge.insert(uuid, local_id);
1901        remap.tomb.remove(&uuid);
1902        self.observe(se.stamp);
1903        Ok(true)
1904    }
1905
1906    /// Merge an incoming tombstone under LWW, remapping by `uuid`. Removes the
1907    /// live record if we hold it (a node delete cascades to its incident edges);
1908    /// a delete of a `uuid` we have never seen still records a tombstone (anchored
1909    /// on a minted id) so a later, lesser upsert loses. Returns whether it won.
1910    fn apply_delete(
1911        &self,
1912        uuid: [u8; 16],
1913        incoming: Stamp,
1914        is_node: bool,
1915        remap: &mut Remap,
1916    ) -> Result<bool> {
1917        let live = if is_node {
1918            remap.node.get(&uuid).copied()
1919        } else {
1920            remap.edge.get(&uuid).copied()
1921        };
1922        let as_target = |id: u64| {
1923            if is_node {
1924                StampTarget::Node(id)
1925            } else {
1926                StampTarget::Edge(id)
1927            }
1928        };
1929        let tomb_target = remap.tomb.get(&uuid).copied().filter(|t| {
1930            if is_node {
1931                matches!(t, StampTarget::Node(_))
1932            } else {
1933                matches!(t, StampTarget::Edge(_))
1934            }
1935        });
1936        let cur_target = live.map(as_target).or(tomb_target);
1937        if let Some(t) = cur_target {
1938            if self.current_stamp(t).is_some_and(|local| local >= incoming) {
1939                return Ok(false);
1940            }
1941        }
1942        let target = match cur_target {
1943            Some(t) => {
1944                // A live entity is removed (nodes cascade to incident edges); a
1945                // known-but-already-tombstoned target only bumps its stamp.
1946                if let Some(id) = live {
1947                    let op = if is_node {
1948                        WalOp::DeleteNode(id)
1949                    } else {
1950                        WalOp::DeleteEdge(id)
1951                    };
1952                    Arc::make_mut(&mut *self.write_for_commit()?).apply_wal_op(op.clone());
1953                    self.record(&[op])?;
1954                }
1955                t
1956            }
1957            None => {
1958                // Never seen: mint an anchor id so a later upsert of this uuid
1959                // LWW-compares against the tombstone. Nothing to remove.
1960                let id = {
1961                    let mut guard = self.write_for_commit()?;
1962                    let inner = Arc::make_mut(&mut guard);
1963                    if is_node {
1964                        inner.next_node_id += 1;
1965                        inner.next_node_id
1966                    } else {
1967                        inner.next_edge_id += 1;
1968                        inner.next_edge_id
1969                    }
1970                };
1971                as_target(id)
1972            }
1973        };
1974        self.mark_tombstoned(target, incoming, uuid);
1975        if is_node {
1976            remap.node.remove(&uuid);
1977        } else {
1978            remap.edge.remove(&uuid);
1979        }
1980        remap.tomb.insert(uuid, target);
1981        self.observe(incoming);
1982        Ok(true)
1983    }
1984
1985    /// Zero-copy node fetch: returns an `Arc<Node>` handle (a refcount bump)
1986    /// rather than deep-cloning the record the way
1987    /// [`GraphEngine::get_node`] must to
1988    /// honour its owned-return contract. Prefer this on read-hot paths where the
1989    /// caller only needs to *read* the node — a node with a large body/property
1990    /// map costs the same here as a tiny one.
1991    pub fn get_node_arc(&self, id: u64) -> Option<Arc<Node>> {
1992        read(&self.inner).get_node_arc(id)
1993    }
1994
1995    /// Zero-copy edge fetch — the [`get_node_arc`](Self::get_node_arc) analogue
1996    /// for edges.
1997    pub fn get_edge_arc(&self, id: u64) -> Option<Arc<Edge>> {
1998        read(&self.inner).get_edge_arc(id)
1999    }
2000
2001    /// The local id of the node with this globally-unique `uuid`, or `None`.
2002    /// A linear scan today (the `uuid → id` map is built per merge in
2003    /// [`apply_delta`](Self::apply_delta), not kept persistently); use it to
2004    /// address an entity across replicas by its stable `uuid`.
2005    pub fn node_id_of_uuid(&self, uuid: [u8; 16]) -> Option<u64> {
2006        read(&self.inner)
2007            .nodes
2008            .values()
2009            .find(|n| n.uuid == uuid)
2010            .map(|n| n.id)
2011    }
2012
2013    /// The local id of the edge with this globally-unique `uuid`, or `None` — the
2014    /// edge counterpart to [`node_id_of_uuid`](Self::node_id_of_uuid).
2015    pub fn edge_id_of_uuid(&self, uuid: [u8; 16]) -> Option<u64> {
2016        read(&self.inner)
2017            .edges
2018            .values()
2019            .find(|e| e.uuid == uuid)
2020            .map(|e| e.id)
2021    }
2022
2023    /// Fetch a node by its globally-unique `uuid`.
2024    pub fn get_node_by_uuid(&self, uuid: [u8; 16]) -> Option<Node> {
2025        let inner = read(&self.inner);
2026        inner
2027            .nodes
2028            .values()
2029            .find(|n| n.uuid == uuid)
2030            .map(|a| (**a).clone())
2031    }
2032
2033    /// Fetch a node by its unique `title` via the title index.
2034    pub fn get_node_by_title(&self, title: &str) -> Option<Node> {
2035        read(&self.inner).get_node_by_title(title)
2036    }
2037
2038    /// Most-recently-updated nodes first, capped at `limit` (`updated_at`
2039    /// desc, then id desc).
2040    pub fn list_recent(&self, limit: usize) -> Vec<Node> {
2041        read(&self.inner).list_recent(limit)
2042    }
2043
2044    /// Edges of `kind`, id-ascending, paginated by `limit`/`offset`.
2045    pub fn list_edges_by_kind(&self, kind: &str, limit: usize, offset: usize) -> Vec<Edge> {
2046        read(&self.inner).list_edges_by_kind(kind, limit, offset)
2047    }
2048
2049    // ----- durable embedding store (issue #446, epic #444) -------------------
2050    //
2051    // The native counterpart of the KV `vec:` keyspace: a typed, durable
2052    // per-node embedding store, independent of node `properties`. Writes append
2053    // a `WalOp::SetEmbedding`/`DeleteEmbedding` (durable, replicated, compacted
2054    // like node/edge records); reads are lock-free clones.
2055
2056    /// Store (or replace) `node_id`'s embedding, durably. Errors with
2057    /// [`CoreError::NodeNotFound`] if the node does not exist.
2058    ///
2059    /// # Errors
2060    /// [`CoreError::NodeNotFound`] if `node_id` is absent; propagates a WAL
2061    /// append/fsync failure.
2062    pub fn set_embedding(&self, node_id: u64, vector: Vec<f32>) -> Result<()> {
2063        {
2064            let mut guard = self.write_for_commit()?;
2065            let inner = Arc::make_mut(&mut guard);
2066            if !inner.nodes.contains_key(&node_id) {
2067                return Err(CoreError::NodeNotFound(node_id));
2068            }
2069            inner.apply_wal_op(WalOp::SetEmbedding(node_id, vector.clone()));
2070        }
2071        self.record(&[WalOp::SetEmbedding(node_id, vector)])
2072    }
2073
2074    /// Store many embeddings in one durable batch (one fsync). Validates every
2075    /// node exists **before** applying any, so it is all-or-nothing.
2076    ///
2077    /// # Errors
2078    /// [`CoreError::NodeNotFound`] for the first absent node (nothing is
2079    /// written); propagates a WAL append/fsync failure.
2080    pub fn set_embeddings_batch(&self, embeddings: &[(u64, Vec<f32>)]) -> Result<()> {
2081        if embeddings.is_empty() {
2082            return Ok(());
2083        }
2084        let ops: Vec<WalOp> = {
2085            let mut guard = self.write_for_commit()?;
2086            let inner = Arc::make_mut(&mut guard);
2087            for (id, _) in embeddings {
2088                if !inner.nodes.contains_key(id) {
2089                    return Err(CoreError::NodeNotFound(*id));
2090                }
2091            }
2092            let mut ops = Vec::with_capacity(embeddings.len());
2093            for (id, vector) in embeddings {
2094                inner.apply_wal_op(WalOp::SetEmbedding(*id, vector.clone()));
2095                ops.push(WalOp::SetEmbedding(*id, vector.clone()));
2096            }
2097            ops
2098        };
2099        self.record(&ops)
2100    }
2101
2102    /// Fetch `node_id`'s embedding, or `None`.
2103    pub fn get_embedding(&self, node_id: u64) -> Option<Vec<f32>> {
2104        read(&self.inner).embeddings.get(&node_id).cloned()
2105    }
2106
2107    /// Delete `node_id`'s embedding, durably. Idempotent (a missing embedding
2108    /// is not an error).
2109    ///
2110    /// # Errors
2111    /// Propagates a WAL append/fsync failure.
2112    pub fn delete_embedding(&self, node_id: u64) -> Result<()> {
2113        {
2114            let mut guard = self.write_for_commit()?;
2115            Arc::make_mut(&mut guard).apply_wal_op(WalOp::DeleteEmbedding(node_id));
2116        }
2117        self.record(&[WalOp::DeleteEmbedding(node_id)])
2118    }
2119
2120    /// The number of stored embeddings.
2121    pub fn embedding_count(&self) -> usize {
2122        read(&self.inner).embeddings.len()
2123    }
2124
2125    /// Snapshot of all `(node_id, embedding)` pairs, id-ascending — e.g. to
2126    /// build a vector index. The order is deterministic.
2127    pub fn all_embeddings(&self) -> Vec<(u64, Vec<f32>)> {
2128        let inner = read(&self.inner);
2129        let mut out: Vec<(u64, Vec<f32>)> = inner
2130            .embeddings
2131            .iter()
2132            .map(|(id, v)| (*id, v.clone()))
2133            .collect();
2134        out.sort_by_key(|(id, _)| *id);
2135        out
2136    }
2137
2138    // ----- batch create (embedded parity, #446 S3 prerequisite) --------------
2139    //
2140    // One durable boundary (one fsync) for the whole batch, all-or-nothing:
2141    // built on a private working copy swapped in only after the WAL append is
2142    // durable — so an I/O failure or a mid-batch validation error leaves the
2143    // live graph, log and feed untouched, exactly like `delete_nodes` (#435).
2144
2145    /// Create many nodes in one durable batch.
2146    ///
2147    /// # Errors
2148    /// [`CoreError::DuplicateTitle`] if any title collides (within the batch or
2149    /// against an existing node) — the whole batch fails and nothing is written;
2150    /// propagates a WAL append/fsync failure.
2151    pub fn create_nodes(&self, new_nodes: Vec<NewNode>) -> Result<Vec<Node>> {
2152        if new_nodes.is_empty() {
2153            return Ok(Vec::new());
2154        }
2155        let mut live = self.write_for_commit()?;
2156        let mut working = Arc::clone(&live);
2157        let w = Arc::make_mut(&mut working);
2158        let mut nodes = Vec::with_capacity(new_nodes.len());
2159        let mut ops = Vec::with_capacity(new_nodes.len());
2160        for nn in new_nodes {
2161            let node = w.create_node(nn)?; // validates DuplicateTitle in the working copy
2162            ops.push(WalOp::UpsertNode(node.clone()));
2163            nodes.push(node);
2164        }
2165        self.record(&ops)?;
2166        *live = working;
2167        drop(live);
2168        for n in &nodes {
2169            self.stamp_write(StampTarget::Node(n.id));
2170        }
2171        Ok(nodes)
2172    }
2173
2174    /// Create many edges in one durable batch. Every edge's endpoints must
2175    /// already exist.
2176    ///
2177    /// # Errors
2178    /// [`CoreError::NodeNotFound`] if an endpoint is missing (the whole batch
2179    /// fails, nothing written); propagates a WAL append/fsync failure.
2180    pub fn create_edges(&self, new_edges: Vec<NewEdge>) -> Result<Vec<Edge>> {
2181        if new_edges.is_empty() {
2182            return Ok(Vec::new());
2183        }
2184        let mut live = self.write_for_commit()?;
2185        let mut working = Arc::clone(&live);
2186        let w = Arc::make_mut(&mut working);
2187        let mut edges = Vec::with_capacity(new_edges.len());
2188        let mut ops = Vec::with_capacity(new_edges.len());
2189        for ne in new_edges {
2190            let edge = w.create_edge(ne)?;
2191            ops.push(WalOp::UpsertEdge(edge.clone()));
2192            edges.push(edge);
2193        }
2194        self.record(&ops)?;
2195        *live = working;
2196        drop(live);
2197        for e in &edges {
2198            self.stamp_write(StampTarget::Edge(e.id));
2199        }
2200        Ok(edges)
2201    }
2202
2203    /// Distinct neighbours as zero-copy `Arc<Node>` handles — the fan-out
2204    /// counterpart to [`get_node_arc`](Self::get_node_arc), so expanding a
2205    /// high-degree node never deep-clones every neighbour's record.
2206    pub fn neighbors_arc(
2207        &self,
2208        node_id: u64,
2209        direction: Direction,
2210        kind: Option<&str>,
2211    ) -> Vec<Arc<Node>> {
2212        read(&self.inner).neighbors_arc(node_id, direction, kind)
2213    }
2214
2215    /// The current change-feed head — the sequence number of the most recent
2216    /// committed change. A caught-up subscriber holds this as its cursor;
2217    /// `changes_since(change_head())` returns an empty batch.
2218    pub fn change_head(&self) -> u64 {
2219        let feed = self.feed.lock().unwrap_or_else(|e| e.into_inner());
2220        feed.start_seq + feed.ops.len() as u64
2221    }
2222
2223    /// Read every committed change after `cursor`, in commit order (the
2224    /// change feed). The returned
2225    /// [`ChangeBatch`] carries the resume cursor and, if the cursor had fallen
2226    /// behind the retained history, a `lagged` flag telling the subscriber to
2227    /// re-snapshot first.
2228    ///
2229    /// Subscribers follow snapshot-then-tail: seed the index from a
2230    /// [`snapshot`](Self::snapshot), remember [`change_head`](Self::change_head)
2231    /// at that instant, then poll `changes_since(cursor)` and advance the cursor
2232    /// by each batch — so an FTS or vector index stays current without touching
2233    /// the write path.
2234    pub fn changes_since(&self, cursor: u64) -> ChangeBatch {
2235        let feed = self.feed.lock().unwrap_or_else(|e| e.into_inner());
2236        let head = feed.start_seq + feed.ops.len() as u64;
2237        if cursor < feed.start_seq {
2238            // The cursor predates the retained window — history was trimmed, so
2239            // the subscriber must re-snapshot before applying what remains.
2240            return ChangeBatch {
2241                cursor: head,
2242                ops: feed.ops.clone(),
2243                lagged: true,
2244            };
2245        }
2246        let from = (cursor - feed.start_seq).min(feed.ops.len() as u64) as usize;
2247        ChangeBatch {
2248            cursor: head,
2249            ops: feed.ops[from..].to_vec(),
2250            lagged: false,
2251        }
2252    }
2253
2254    /// Drop change-feed history at or before `cursor`, bounding the feed's
2255    /// memory.
2256    ///
2257    /// The caller passes the **minimum cursor across its live subscribers**, so
2258    /// no subscriber that is still catching up loses a change it has not seen.
2259    /// After trimming, a subscriber whose cursor is below the new floor gets
2260    /// `lagged = true` from [`changes_since`](Self::changes_since) and must
2261    /// re-snapshot. `cursor` is clamped to the current head (the feed never
2262    /// trims a change that has not been produced). Returns the new retained
2263    /// floor — the sequence number before the oldest retained change.
2264    pub fn trim_before(&self, cursor: u64) -> u64 {
2265        let mut feed = self.feed.lock().unwrap_or_else(|e| e.into_inner());
2266        let head = feed.start_seq + feed.ops.len() as u64;
2267        let target = cursor.min(head);
2268        if target <= feed.start_seq {
2269            return feed.start_seq;
2270        }
2271        let drop = (target - feed.start_seq) as usize;
2272        feed.ops.drain(..drop);
2273        feed.start_seq = target;
2274        feed.start_seq
2275    }
2276
2277    /// The oldest sequence number still retained on the change-feed — the floor
2278    /// below which [`changes_since`](Self::changes_since) reports `lagged`. `0`
2279    /// until [`trim_before`](Self::trim_before) advances it.
2280    pub fn change_floor(&self) -> u64 {
2281        self.feed
2282            .lock()
2283            .unwrap_or_else(|e| e.into_inner())
2284            .start_seq
2285    }
2286
2287    /// Record committed changes into the WAL (when the engine is durable) and
2288    /// the change-feed, in commit order. The single record point for every
2289    /// mutation path, so the change-feed sees exactly what the WAL persists.
2290    ///
2291    /// The WAL append happens **first**: if it fails the feed is left untouched,
2292    /// so the feed never advertises a change the WAL did not persist.
2293    fn record(&self, ops: &[WalOp]) -> Result<()> {
2294        self.record_split(ops, ops)
2295    }
2296
2297    /// Persist `wal_ops` as one WAL record and publish `feed_ops` on the
2298    /// change-feed, in commit order. Ordinary writes pass the same ops for
2299    /// both. Two-phase commit logs a compact `Prepare` /
2300    /// `CommitPrepared` / `RollbackPrepared` record while the feed carries
2301    /// nothing (prepared state is invisible) or, on commit, the expanded write
2302    /// set, so indexes and in-process replicas see ordinary upserts/deletes.
2303    fn record_split(&self, wal_ops: &[WalOp], feed_ops: &[WalOp]) -> Result<()> {
2304        if wal_ops.is_empty() && feed_ops.is_empty() {
2305            return Ok(());
2306        }
2307        // Durable: the WAL append + feed extend go through group commit, so
2308        // concurrent writers share a single fsync. The feed is extended by the
2309        // flushing leader *after* fsync (in `flush_group`), preserving the
2310        // invariant that the feed never advertises a change the WAL did not
2311        // persist.
2312        #[cfg(not(target_arch = "wasm32"))]
2313        if self.wal.is_some() {
2314            return self.group_commit(wal_ops, feed_ops);
2315        }
2316        // In-memory (or wasm): no WAL to flush, just the change-feed.
2317        #[cfg(target_arch = "wasm32")]
2318        let _ = wal_ops;
2319        let mut feed = self.feed.lock().unwrap_or_else(|e| e.into_inner());
2320        feed.ops.extend_from_slice(feed_ops);
2321        Ok(())
2322    }
2323
2324    /// Enqueue `ops` for durable commit and block until they are fsynced. One
2325    /// elected leader flushes the whole pending batch with a single fsync
2326    /// (see [`flush_group`](Self::flush_group)); everyone else waits and returns
2327    /// once the leader has made their sequence durable. This is what turns N
2328    /// concurrent autocommit writes into far fewer than N fsyncs.
2329    #[cfg(not(target_arch = "wasm32"))]
2330    fn group_commit(&self, wal_ops: &[WalOp], feed_ops: &[WalOp]) -> Result<()> {
2331        // Serialize the WAL line up front, off the queue lock. A single op is a
2332        // bare object; a multi-op batch (a transaction) is one JSON array line,
2333        // so it still recovers all-or-nothing.
2334        let mut line = match wal_ops {
2335            [] => String::new(),
2336            [op] => serde_json::to_string(op)?,
2337            many => serde_json::to_string(many)?,
2338        };
2339        if !line.is_empty() {
2340            line.push('\n');
2341        }
2342
2343        let my_seq = {
2344            let mut q = self.group.queue.lock().unwrap_or_else(|e| e.into_inner());
2345            if q.broken {
2346                return Err(wal_broken_err());
2347            }
2348            let seq = q.next_seq;
2349            q.next_seq += 1;
2350            q.pending.push(PendingCommit {
2351                seq,
2352                ops: feed_ops.to_vec(),
2353                line,
2354            });
2355            seq
2356        };
2357
2358        let mut q = self.group.queue.lock().unwrap_or_else(|e| e.into_inner());
2359        loop {
2360            if q.durable_seq >= my_seq {
2361                return Ok(());
2362            }
2363            if q.broken {
2364                return Err(wal_broken_err());
2365            }
2366            if !q.leader {
2367                q.leader = true;
2368                // Take every currently-pending write (in seq order) and flush it
2369                // as one group with a single fsync.
2370                let batch: Vec<PendingCommit> = std::mem::take(&mut q.pending);
2371                drop(q);
2372                let result = self.flush_group(&batch);
2373                let mut done = self.group.queue.lock().unwrap_or_else(|e| e.into_inner());
2374                done.leader = false;
2375                match &result {
2376                    Ok(()) => {
2377                        if let Some(last) = batch.last() {
2378                            done.durable_seq = done.durable_seq.max(last.seq);
2379                        }
2380                    }
2381                    Err(_) => done.broken = true,
2382                }
2383                drop(done);
2384                self.group.committed.notify_all();
2385                return result;
2386            }
2387            // Someone else is flushing; wait for them to make progress.
2388            q = self
2389                .group
2390                .committed
2391                .wait(q)
2392                .unwrap_or_else(|e| e.into_inner());
2393        }
2394    }
2395
2396    /// Flush one group: write every pending line, fsync **once**, then extend
2397    /// the change-feed with the whole batch in seq order. On any I/O failure the
2398    /// caller marks the WAL broken (the partial, unfsynced tail is a torn record
2399    /// recovery truncates — never an acknowledged write).
2400    #[cfg(not(target_arch = "wasm32"))]
2401    fn flush_group(&self, batch: &[PendingCommit]) -> Result<()> {
2402        use std::io::Write;
2403        if batch.is_empty() {
2404            return Ok(());
2405        }
2406        if let Some(wal) = &self.wal {
2407            let mut sink = wal.lock().unwrap_or_else(|e| e.into_inner());
2408            for pc in batch {
2409                sink.file.write_all(pc.line.as_bytes())?;
2410            }
2411            sink.file.sync_all()?;
2412            self.group
2413                .fsyncs
2414                .fetch_add(1, std::sync::atomic::Ordering::Relaxed);
2415        }
2416        let mut feed = self.feed.lock().unwrap_or_else(|e| e.into_inner());
2417        for pc in batch {
2418            feed.ops.extend_from_slice(&pc.ops);
2419        }
2420        Ok(())
2421    }
2422
2423    /// Total fsyncs the durable WAL has performed since open — the group-commit
2424    /// coalescing metric: a batch of N writes flushed together counts as one, so
2425    /// under concurrency this stays far below the write count. `0` for an
2426    /// in-memory engine.
2427    #[cfg(not(target_arch = "wasm32"))]
2428    pub fn wal_fsync_count(&self) -> u64 {
2429        self.group.fsyncs.load(std::sync::atomic::Ordering::Relaxed)
2430    }
2431
2432    /// Take a consistent, read-only [`GraphSnapshot`] of the current state.
2433    ///
2434    /// O(1): it is an `Arc::clone` of the live state. The returned view is
2435    /// **frozen** — subsequent writes to this engine copy-on-write and leave the
2436    /// snapshot untouched — giving snapshot isolation for reads.
2437    pub fn snapshot(&self) -> GraphSnapshot {
2438        GraphSnapshot {
2439            inner: Arc::clone(&read(&self.inner)),
2440        }
2441    }
2442
2443    /// Begin a [`NativeTx`] — a transaction that reads a consistent snapshot of
2444    /// the graph as of now, buffers its writes privately, and applies them all
2445    /// atomically on [`commit`](NativeTx::commit).
2446    ///
2447    /// Isolation is snapshot: the transaction never sees another writer's
2448    /// changes made after it began. Concurrency control is optimistic — the
2449    /// commit succeeds only if the graph has not changed since the transaction
2450    /// began, otherwise it returns [`CommitError::Conflict`] and the caller
2451    /// retries. Dropping the transaction without committing rolls it back.
2452    pub fn begin(&self) -> NativeTx<'_> {
2453        let base = Arc::clone(&read(&self.inner));
2454        NativeTx {
2455            engine: self,
2456            working: Arc::clone(&base),
2457            base,
2458            ops: Vec::new(),
2459        }
2460    }
2461
2462    /// Begin a **registered** transaction — the executor-facing form of
2463    /// [`Self::begin`] for callers (a Bolt session) that keep only an id
2464    /// between statements: run each statement on
2465    /// [`Self::tx_engine`]`(id)`, then [`Self::tx_commit`] /
2466    /// [`Self::tx_rollback`]. Same semantics as [`NativeTx`]: buffered
2467    /// writes, read-your-writes, snapshot isolation, first-committer-wins
2468    /// conflict detection, one fsynced WAL batch at commit.
2469    pub fn tx_begin(&self) -> NativeTxId {
2470        let base = Arc::clone(&read(&self.inner));
2471        let id = self
2472            .next_reg_tx
2473            .fetch_add(1, std::sync::atomic::Ordering::SeqCst)
2474            + 1;
2475        self.reg_txs
2476            .lock()
2477            .unwrap_or_else(|e| e.into_inner())
2478            .insert(
2479                id,
2480                TxSlot {
2481                    working: Arc::clone(&base),
2482                    base,
2483                    ops: Vec::new(),
2484                },
2485            );
2486        NativeTxId(id)
2487    }
2488
2489    /// The per-statement [`GraphEngine`] view of a registered transaction,
2490    /// or `None` once it has been committed / rolled back.
2491    pub fn tx_engine(&self, id: NativeTxId) -> Option<NativeTxEngine<'_>> {
2492        self.reg_txs
2493            .lock()
2494            .unwrap_or_else(|e| e.into_inner())
2495            .contains_key(&id.0)
2496            .then_some(NativeTxEngine {
2497                graph: self,
2498                id: id.0,
2499            })
2500    }
2501
2502    /// Commit a registered transaction: apply its buffered writes
2503    /// atomically (one fsynced WAL batch) if the graph has not changed
2504    /// since [`Self::tx_begin`] and the result satisfies every declared
2505    /// constraint. The slot is always closed — a failed commit discards
2506    /// the buffered writes, exactly like [`NativeTx::commit`].
2507    ///
2508    /// # Errors
2509    /// - [`CommitError::Conflict`] if another writer committed since begin.
2510    /// - [`CommitError::Constraint`] on a constraint violation.
2511    /// - [`CommitError::Io`] on a WAL failure, or for an unknown /
2512    ///   already-closed id.
2513    pub fn tx_commit(&self, id: NativeTxId) -> std::result::Result<(), CommitError> {
2514        let slot = self
2515            .reg_txs
2516            .lock()
2517            .unwrap_or_else(|e| e.into_inner())
2518            .remove(&id.0)
2519            .ok_or_else(|| CommitError::Io("unknown or already-closed transaction".to_string()))?;
2520        self.commit_parts(slot.base, slot.working, &slot.ops)
2521    }
2522
2523    /// Discard a registered transaction's buffered writes. Returns whether
2524    /// the slot was still open (a second call is a `false` no-op).
2525    pub fn tx_rollback(&self, id: NativeTxId) -> bool {
2526        self.reg_txs
2527            .lock()
2528            .unwrap_or_else(|e| e.into_inner())
2529            .remove(&id.0)
2530            .is_some()
2531    }
2532
2533    /// Two-phase commit, phase one: validate registered transaction
2534    /// `id` exactly as a commit would (no change since `begin`, constraints
2535    /// hold), durably log its write set as prepared under `gid`, and raise the
2536    /// write fence. The transaction is closed either way; on success it can
2537    /// only be finished by [`commit_prepared`](Self::commit_prepared) or
2538    /// [`rollback_prepared`](Self::rollback_prepared), from any handle and
2539    /// across restarts. While the fence is up every other write fails fast
2540    /// ([`CoreError::PreparedTransactionPending`] /
2541    /// [`CommitError::PreparedPending`]); reads are unaffected.
2542    ///
2543    /// # Errors
2544    ///
2545    /// [`PrepareError`]; nothing is prepared and no fence is raised.
2546    pub fn tx_prepare(&self, id: NativeTxId, gid: &str) -> std::result::Result<(), PrepareError> {
2547        let slot = self
2548            .reg_txs
2549            .lock()
2550            .unwrap_or_else(|e| e.into_inner())
2551            .remove(&id.0)
2552            .ok_or(PrepareError::UnknownTransaction)?;
2553        let mut live = write(&self.inner);
2554        if live.prepared.contains_key(gid) {
2555            return Err(PrepareError::DuplicateGid(gid.to_string()));
2556        }
2557        if !live.prepared.is_empty() {
2558            return Err(PrepareError::PreparedPending(
2559                live.prepared.keys().cloned().collect(),
2560            ));
2561        }
2562        if !Arc::ptr_eq(&live, &slot.base) {
2563            return Err(PrepareError::Conflict);
2564        }
2565        slot.working
2566            .validate_constraints()
2567            .map_err(PrepareError::Constraint)?;
2568        let TxSlot { base, working, ops } = slot;
2569        // Only the write set is kept: the fence guarantees live stays equal to
2570        // `base`, so applying `ops` at resolution reproduces `working`.
2571        drop(working);
2572        drop(base);
2573        let entry = PreparedEntry {
2574            prepared_at_ms: crate::model::now_ms(),
2575            ops,
2576        };
2577        let record = WalOp::Prepare {
2578            gid: gid.to_string(),
2579            prepared_at_ms: entry.prepared_at_ms,
2580            ops: entry.ops.clone(),
2581        };
2582        // Logged under the writer lock; the feed gets nothing (invisible).
2583        self.record_split(std::slice::from_ref(&record), &[])
2584            .map_err(|e| PrepareError::Io(e.to_string()))?;
2585        let inner = Arc::make_mut(&mut live);
2586        inner.heuristic.remove(gid);
2587        inner.prepared.insert(gid.to_string(), entry);
2588        Ok(())
2589    }
2590
2591    /// Two-phase commit, phase two: apply the write set prepared under
2592    /// `gid` and lower the fence once nothing else is prepared. Cannot
2593    /// conflict: the fence kept the graph unchanged since the prepare.
2594    ///
2595    /// # Errors
2596    ///
2597    /// [`ResolveError::UnknownGid`] if nothing is prepared under `gid`;
2598    /// [`ResolveError::Io`] if the commit record could not be written (the
2599    /// transaction stays prepared — retry).
2600    pub fn commit_prepared(&self, gid: &str) -> std::result::Result<(), ResolveError> {
2601        let mut live = write(&self.inner);
2602        let Some(ops) = live.prepared.get(gid).map(|entry| entry.ops.clone()) else {
2603            return Err(if live.heuristic.contains(gid) {
2604                ResolveError::HeuristicRollback(gid.to_string())
2605            } else {
2606                ResolveError::UnknownGid(gid.to_string())
2607            });
2608        };
2609        let record = WalOp::CommitPrepared {
2610            gid: gid.to_string(),
2611        };
2612        // The WAL gets the small record; the feed the expanded write set, so
2613        // indexes and in-process replicas see ordinary upserts and deletes.
2614        self.record_split(std::slice::from_ref(&record), &ops)
2615            .map_err(|e| ResolveError::Io(e.to_string()))?;
2616        Arc::make_mut(&mut live).apply_wal_op(record);
2617        Ok(())
2618    }
2619
2620    /// Two-phase commit: discard the write set prepared under `gid`
2621    /// and lower the fence once nothing else is prepared.
2622    ///
2623    /// # Errors
2624    ///
2625    /// [`ResolveError::UnknownGid`] or [`ResolveError::Io`], as for
2626    /// [`commit_prepared`](Self::commit_prepared).
2627    pub fn rollback_prepared(&self, gid: &str) -> std::result::Result<(), ResolveError> {
2628        self.rollback_prepared_as(gid, false)
2629    }
2630
2631    /// Two-phase commit: roll back the transaction prepared under
2632    /// `gid` **heuristically** — a server decision after the opt-in
2633    /// prepared-transaction timeout, not the coordinator's. The outcome is
2634    /// logged and remembered, so a later [`commit_prepared`](Self::commit_prepared)
2635    /// returns [`ResolveError::HeuristicRollback`] instead of pretending the
2636    /// transaction never existed (the XA heuristic-outcome model).
2637    ///
2638    /// # Errors
2639    ///
2640    /// As for [`rollback_prepared`](Self::rollback_prepared).
2641    pub fn heuristic_rollback_prepared(&self, gid: &str) -> std::result::Result<(), ResolveError> {
2642        self.rollback_prepared_as(gid, true)
2643    }
2644
2645    fn rollback_prepared_as(
2646        &self,
2647        gid: &str,
2648        heuristic: bool,
2649    ) -> std::result::Result<(), ResolveError> {
2650        let mut live = write(&self.inner);
2651        if !live.prepared.contains_key(gid) {
2652            // Rolling back what the server already rolled back heuristically
2653            // agrees with the outcome.
2654            if !heuristic && live.heuristic.contains(gid) {
2655                return Ok(());
2656            }
2657            return Err(ResolveError::UnknownGid(gid.to_string()));
2658        }
2659        let record = WalOp::RollbackPrepared {
2660            gid: gid.to_string(),
2661            heuristic,
2662        };
2663        self.record_split(std::slice::from_ref(&record), &[])
2664            .map_err(|e| ResolveError::Io(e.to_string()))?;
2665        Arc::make_mut(&mut live).apply_wal_op(record);
2666        Ok(())
2667    }
2668
2669    /// Every prepared, unresolved transaction, by ascending `gid` — for
2670    /// a coordinator resolving in-doubt transactions, and for operators.
2671    pub fn list_prepared(&self) -> Vec<PreparedInfo> {
2672        read(&self.inner)
2673            .prepared
2674            .iter()
2675            .map(|(gid, entry)| PreparedInfo {
2676                gid: gid.clone(),
2677                prepared_at_ms: entry.prepared_at_ms,
2678                op_count: entry.ops.len(),
2679            })
2680            .collect()
2681    }
2682
2683    /// The shared commit tail of [`NativeTx::commit`] and
2684    /// [`Self::tx_commit`]: conflict check, constraint validation, one
2685    /// recorded (WAL + feed) batch, then the atomic swap.
2686    fn commit_parts(
2687        &self,
2688        base: Arc<Inner>,
2689        working: Arc<Inner>,
2690        ops: &[WalOp],
2691    ) -> std::result::Result<(), CommitError> {
2692        let mut live = write(&self.inner);
2693        // The two-phase-commit fence (#556): nothing else commits while a
2694        // transaction is prepared.
2695        if !live.prepared.is_empty() {
2696            return Err(CommitError::PreparedPending(
2697                live.prepared.keys().cloned().collect(),
2698            ));
2699        }
2700        if !Arc::ptr_eq(&live, &base) {
2701            return Err(CommitError::Conflict);
2702        }
2703        working
2704            .validate_constraints()
2705            .map_err(CommitError::Constraint)?;
2706        self.record(ops)
2707            .map_err(|e| CommitError::Io(e.to_string()))?;
2708        *live = working;
2709        Ok(())
2710    }
2711
2712    /// Declare a schema [`Constraint`] the engine enforces at transaction
2713    /// commit.
2714    ///
2715    /// The constraint is validated against the current data first: if existing
2716    /// nodes already violate it, it is **not** stored and the
2717    /// [`ConstraintViolation`] is returned (matching Neo4j, which refuses to
2718    /// create a constraint the data does not already satisfy).
2719    ///
2720    /// # Errors
2721    /// [`ConstraintViolation`] if the current graph already violates the
2722    /// constraint.
2723    pub fn add_constraint(
2724        &self,
2725        constraint: Constraint,
2726    ) -> std::result::Result<(), ConstraintViolation> {
2727        let mut guard = write(&self.inner);
2728        let g = Arc::make_mut(&mut guard);
2729        g.constraints.push(constraint);
2730        if let Err(e) = g.validate_constraints() {
2731            g.constraints.pop();
2732            return Err(e);
2733        }
2734        Ok(())
2735    }
2736
2737    /// Dump the current state as a write-ahead-log op sequence: every node then
2738    /// every edge as an `Upsert`, in ascending id order. This is the "snapshot" form of the log — replaying it into a
2739    /// fresh engine via [`replay`](Self::replay) reproduces the graph exactly,
2740    /// which is what lets a periodic snapshot compact/truncate the incremental
2741    /// WAL. Constraints are schema, not data, and are not part of the dump.
2742    pub fn dump_wal(&self) -> Vec<WalOp> {
2743        read(&self.inner).to_wal_ops()
2744    }
2745
2746    /// Apply a batch of committed [`WalOp`]s to this engine **verbatim** —
2747    /// ids/uuids/timestamps preserved, in order — and thread them through this
2748    /// engine's own durability and change-feed (the read-replica apply path).
2749    /// Unlike [`apply_delta`](Self::apply_delta), which
2750    /// remaps ids for a peer-to-peer CRDT merge, this is faithful single-master
2751    /// replication: a follower applies its leader's log and becomes an exact
2752    /// mirror. Each op extends the change-feed (so the follower's own indexes can
2753    /// tail it) and, for a durable follower, is logged to its WAL.
2754    pub fn apply_wal_ops(&self, ops: &[WalOp]) -> Result<()> {
2755        if ops.is_empty() {
2756            return Ok(());
2757        }
2758        {
2759            let mut guard = write(&self.inner);
2760            let inner = Arc::make_mut(&mut guard);
2761            for op in ops {
2762                inner.apply_wal_op(op.clone());
2763            }
2764        }
2765        self.record(ops)?;
2766        Ok(())
2767    }
2768
2769    /// Rebuild an engine by replaying a [`WalOp`] sequence in order — the
2770    /// recovery path: load a snapshot then replay the WAL
2771    /// tail, or replay a full WAL from empty. Ids/uuids/timestamps come from the
2772    /// logged records; the id counters advance past every replayed id so a
2773    /// post-recovery create never collides with a recovered node/edge.
2774    pub fn replay(ops: impl IntoIterator<Item = WalOp>) -> Self {
2775        let mut inner = Inner::default();
2776        for op in ops {
2777            inner.apply_wal_op(op);
2778        }
2779        // Seed the change-feed with the recovered state (its snapshot form),
2780        // exactly as `apply_dump` records what it applies: subscribers that
2781        // build themselves by tailing the feed (the secondary indexes, the
2782        // value cache) must see recovered data too, not only post-recovery
2783        // writes.
2784        let seed = inner.to_wal_ops();
2785        NativeGraph {
2786            inner: RwLock::new(Arc::new(inner)),
2787            #[cfg(not(target_arch = "wasm32"))]
2788            wal: None,
2789            reg_txs: std::sync::Mutex::new(HashMap::new()),
2790            next_reg_tx: std::sync::atomic::AtomicU64::new(0),
2791            feed: std::sync::Mutex::new(ChangeFeed {
2792                start_seq: 0,
2793                ops: seed,
2794            }),
2795            #[cfg(not(target_arch = "wasm32"))]
2796            group: GroupCommit::default(),
2797            origin: mint_origin(),
2798            clock: std::sync::Mutex::new(HlcClock::new()),
2799            stamps: RwLock::new(HashMap::new()),
2800            tombstones: RwLock::new(HashMap::new()),
2801            #[cfg(not(target_arch = "wasm32"))]
2802            _lock: None,
2803        }
2804    }
2805
2806    /// Open a **durable** engine backed by a write-ahead log at `path`. If the
2807    /// file exists its records are replayed to
2808    /// reconstruct the graph; then the file is opened for append and every
2809    /// subsequent direct write is logged and fsynced before it returns, so a
2810    /// write that has returned survives a crash. Reopening the same path
2811    /// recovers the graph.
2812    ///
2813    /// Both direct writes and transactions ([`begin`](Self::begin)) are
2814    /// durable, and a committed transaction is logged as **one** record
2815    /// (a JSON array of its ops), so it recovers all-or-nothing: a crash
2816    /// that tears the batch mid-write loses the whole transaction — which
2817    /// was never acknowledged — never half of it.
2818    ///
2819    /// # Crash recovery
2820    ///
2821    /// An acknowledged write returns only after fsync, so a crash can only
2822    /// tear the **unacknowledged tail** of the log. Recovery therefore
2823    /// truncates a torn final record (invalid bytes with nothing after
2824    /// them) and opens successfully — losing only what was never
2825    /// acknowledged — while an invalid record that is *followed by valid
2826    /// data* is genuine corruption of acknowledged history and refuses to
2827    /// open rather than silently dropping writes.
2828    ///
2829    /// # Errors
2830    /// [`CoreError::Io`] on a filesystem failure or on corruption before
2831    /// the tail; [`CoreError::Json`] on an encode failure.
2832    #[cfg(not(target_arch = "wasm32"))]
2833    pub fn open_durable(path: impl AsRef<std::path::Path>) -> Result<Self> {
2834        use std::io::Read;
2835        let path = path.as_ref();
2836        // Take the exclusive-open lock BEFORE reading/replaying the WAL (#455):
2837        // a second handle on the same store must be turned away up front, so two
2838        // writers never interleave appends into one log. The lock lives on a
2839        // stable `.lock` sidecar rather than on the WAL fd itself, because
2840        // `compact_wal` renames a fresh file over the WAL path — an flock on the
2841        // WAL inode would be silently defeated when the inode is swapped, letting
2842        // a second opener lock the new inode and slip through. The sidecar is
2843        // never renamed, so the guard holds across compaction.
2844        let lock = acquire_exclusive_lock(&lock_sidecar(path))?;
2845        let mut inner = Inner::default();
2846        if path.exists() {
2847            let mut bytes = Vec::new();
2848            std::fs::File::open(path)?.read_to_end(&mut bytes)?;
2849            let mut valid_end = 0usize; // byte offset just past the last valid record
2850            let mut pos = 0usize;
2851            let mut torn = false;
2852            while pos < bytes.len() {
2853                let (line_end, next) = match bytes[pos..].iter().position(|b| *b == b'\n') {
2854                    Some(i) => (pos + i, pos + i + 1),
2855                    None => (bytes.len(), bytes.len()),
2856                };
2857                match Self::parse_wal_record(&bytes[pos..line_end]) {
2858                    Some(ops) => {
2859                        for op in ops {
2860                            inner.apply_wal_op(op);
2861                        }
2862                        valid_end = next;
2863                        pos = next;
2864                    }
2865                    None => {
2866                        // Invalid record: a torn tail only if nothing but
2867                        // whitespace follows it; otherwise acknowledged
2868                        // history is corrupt — refuse.
2869                        let rest_is_blank = bytes[next..].iter().all(|b| b.is_ascii_whitespace());
2870                        if rest_is_blank {
2871                            torn = true;
2872                            break;
2873                        }
2874                        return Err(std::io::Error::new(
2875                            std::io::ErrorKind::InvalidData,
2876                            format!(
2877                                "corrupt write-ahead-log record at byte {pos} of {} \
2878                                 (valid records follow it, so this is not a torn tail); \
2879                                 refusing to open rather than drop acknowledged writes",
2880                                path.display()
2881                            ),
2882                        )
2883                        .into());
2884                    }
2885                }
2886            }
2887            if torn {
2888                // Drop the unacknowledged tail so the log is clean for append.
2889                std::fs::OpenOptions::new()
2890                    .write(true)
2891                    .open(path)?
2892                    .set_len(valid_end as u64)?;
2893            }
2894        }
2895        let file = std::fs::OpenOptions::new()
2896            .create(true)
2897            .append(true)
2898            .open(path)?;
2899        // Seed the change-feed with the recovered state so feed-tailing
2900        // subscribers (indexes, value cache) see recovered data — see
2901        // [`Self::replay`].
2902        let seed = inner.to_wal_ops();
2903        Ok(NativeGraph {
2904            inner: RwLock::new(Arc::new(inner)),
2905            wal: Some(std::sync::Mutex::new(WalSink {
2906                path: path.to_path_buf(),
2907                file,
2908            })),
2909            reg_txs: std::sync::Mutex::new(HashMap::new()),
2910            next_reg_tx: std::sync::atomic::AtomicU64::new(0),
2911            feed: std::sync::Mutex::new(ChangeFeed {
2912                start_seq: 0,
2913                ops: seed,
2914            }),
2915            #[cfg(not(target_arch = "wasm32"))]
2916            group: GroupCommit::default(),
2917            // Stable replica identity persisted next to the WAL (issue #389),
2918            // reused across restarts so a peer's writes keep a stable provenance.
2919            origin: load_or_mint_origin(&origin_sidecar(path)),
2920            clock: std::sync::Mutex::new(HlcClock::new()),
2921            stamps: RwLock::new(HashMap::new()),
2922            // Restore the tombstone checkpoint so deletes survive a restart and a
2923            // peer cannot resurrect a deleted entity on the next sync (issue #389).
2924            // Live stamps are not persisted (upserts re-sync in full).
2925            tombstones: RwLock::new(load_tombstones(&tombstone_sidecar(path))),
2926            // Hold the exclusive-open lock for this handle's lifetime (#455).
2927            _lock: Some(lock),
2928        })
2929    }
2930
2931    /// Parse one write-ahead-log line: a bare [`WalOp`] object (direct
2932    /// writes, and every record of the pre-batch format) or a JSON array of
2933    /// ops (a transaction batch, all-or-nothing by construction). A blank
2934    /// line parses as zero ops. `None` means the bytes are not a complete
2935    /// valid record.
2936    #[cfg(not(target_arch = "wasm32"))]
2937    pub(crate) fn parse_wal_record(line: &[u8]) -> Option<Vec<WalOp>> {
2938        let text = std::str::from_utf8(line).ok()?.trim();
2939        if text.is_empty() {
2940            return Some(Vec::new());
2941        }
2942        if text.starts_with('[') {
2943            serde_json::from_str::<Vec<WalOp>>(text).ok()
2944        } else {
2945            serde_json::from_str::<WalOp>(text).ok().map(|op| vec![op])
2946        }
2947    }
2948
2949    /// Compact the write-ahead log: rewrite it as the current state's snapshot
2950    /// form (every node/edge as one `Upsert`), discarding the superseded
2951    /// incremental history that has accumulated from overwrites and deletes
2952    ///. Bounds the log's growth without changing the
2953    /// recovered graph.
2954    ///
2955    /// Atomic and crash-safe: the snapshot is written to a temp file and fsynced,
2956    /// then `rename`d over the live log (an atomic replace on the same
2957    /// filesystem), then the append handle is reopened on the new file. A crash
2958    /// at any point leaves either the old or the new complete log — never a torn
2959    /// one. Writes are quiesced for the duration (the inner write lock is held).
2960    /// A no-op for an in-memory-only engine.
2961    ///
2962    /// Returns the on-disk [`CompactWalStats`] (bytes before/after) so a caller
2963    /// — e.g. the storage-panel `shrink` endpoint — can report reclaimed bytes;
2964    /// an in-memory engine reports all-`None`.
2965    ///
2966    /// # Errors
2967    /// [`CoreError::Io`] / [`CoreError::Json`] on a filesystem or encode
2968    /// failure.
2969    #[cfg(not(target_arch = "wasm32"))]
2970    pub fn compact_wal(&self) -> Result<CompactWalStats> {
2971        use std::io::Write;
2972        let Some(wal) = &self.wal else {
2973            return Ok(CompactWalStats::default());
2974        };
2975        // Hold the write lock so no mutation appends to the log mid-compaction.
2976        let inner = write(&self.inner);
2977        let ops = inner.to_wal_ops();
2978        let mut sink = wal.lock().unwrap_or_else(|e| e.into_inner());
2979        let bytes_before = std::fs::metadata(&sink.path).ok().map(|m| m.len());
2980
2981        let tmp = sink.path.with_extension("wal.tmp");
2982        {
2983            let mut f = std::fs::File::create(&tmp)?;
2984            for op in &ops {
2985                let mut line = serde_json::to_string(op)?;
2986                line.push('\n');
2987                f.write_all(line.as_bytes())?;
2988            }
2989            f.sync_all()?;
2990        }
2991        std::fs::rename(&tmp, &sink.path)?;
2992        sink.file = std::fs::OpenOptions::new().append(true).open(&sink.path)?;
2993        let bytes_after = std::fs::metadata(&sink.path).ok().map(|m| m.len());
2994        Ok(CompactWalStats {
2995            bytes_before,
2996            bytes_after,
2997        })
2998    }
2999
3000    /// Physical on-disk size of the write-ahead log in bytes, or `None` for an
3001    /// in-memory engine (nothing on disk). The storage panel's "file bytes".
3002    #[cfg(not(target_arch = "wasm32"))]
3003    #[must_use]
3004    pub fn wal_bytes(&self) -> Option<u64> {
3005        let wal = self.wal.as_ref()?;
3006        let path = wal.lock().unwrap_or_else(|e| e.into_inner()).path.clone();
3007        std::fs::metadata(path).ok().map(|m| m.len())
3008    }
3009
3010    /// The byte size a freshly-compacted WAL would occupy — the serialized
3011    /// current state, one upsert per live node/edge (newline-terminated). The
3012    /// irreducible logical footprint; `wal_bytes / this` is the reclaimable-bloat
3013    /// ratio the append-only log accumulates from superseded upserts, tombstones
3014    /// and old versions.
3015    #[must_use]
3016    pub fn wal_compacted_bytes(&self) -> u64 {
3017        read(&self.inner)
3018            .to_wal_ops()
3019            .iter()
3020            .map(|op| {
3021                serde_json::to_string(op)
3022                    .map(|s| s.len() as u64 + 1)
3023                    .unwrap_or(0)
3024            })
3025            .sum()
3026    }
3027
3028    /// Per-structure breakdown of the live index stack for the storage panel's
3029    /// "Keyspaces" table. The durable WAL holds only records on disk
3030    /// (indexes are rebuilt on load), so this reports the in-memory structures:
3031    /// node/edge records plus the adjacency (`out`/`in`), `title` and `kind`
3032    /// indexes. Each tuple is `(label, rows, content_bytes)`, where
3033    /// `content_bytes` is the structural in-memory footprint, not an on-disk
3034    /// size. Full-text and vector indexes live outside the engine and are not
3035    /// reported here.
3036    #[must_use]
3037    pub fn keyspace_stats(&self) -> Vec<(&'static str, u64, u64)> {
3038        let inner = read(&self.inner);
3039        let adj_entry = std::mem::size_of::<AdjEntry>() as u64;
3040
3041        // Record footprint: the serialized upsert bytes, split node vs edge
3042        // (same accounting as `wal_compacted_bytes`, the logical denominator).
3043        let mut node_bytes = 0u64;
3044        let mut edge_bytes = 0u64;
3045        let mut embedding_bytes = 0u64;
3046        for op in inner.to_wal_ops() {
3047            let bytes = serde_json::to_string(&op)
3048                .map(|s| s.len() as u64 + 1)
3049                .unwrap_or(0);
3050            match op {
3051                WalOp::UpsertNode(_) => node_bytes += bytes,
3052                WalOp::UpsertEdge(_) => edge_bytes += bytes,
3053                WalOp::SetEmbedding(..) => embedding_bytes += bytes,
3054                // `to_wal_ops` snapshots only upserts (plus unresolved
3055                // prepares, which hold no live rows), never deletes.
3056                WalOp::DeleteNode(_)
3057                | WalOp::DeleteEdge(_)
3058                | WalOp::DeleteEmbedding(_)
3059                | WalOp::Prepare { .. }
3060                | WalOp::CommitPrepared { .. }
3061                | WalOp::RollbackPrepared { .. } => {}
3062            }
3063        }
3064
3065        let out_rows: u64 = inner.out_adj.values().map(|v| v.len() as u64).sum();
3066        let in_rows: u64 = inner.in_adj.values().map(|v| v.len() as u64).sum();
3067        let title_bytes: u64 = inner.titles.keys().map(|k| k.len() as u64 + 8).sum();
3068        let kind_rows: u64 = inner.kind_index.values().map(|s| s.len() as u64).sum();
3069        let kind_bytes: u64 = inner
3070            .kind_index
3071            .iter()
3072            .map(|(k, s)| k.len() as u64 + s.len() as u64 * 8)
3073            .sum();
3074
3075        vec![
3076            ("node", inner.nodes.len() as u64, node_bytes),
3077            ("edge", inner.edges.len() as u64, edge_bytes),
3078            ("out", out_rows, out_rows * adj_entry),
3079            ("in", in_rows, in_rows * adj_entry),
3080            ("title", inner.titles.len() as u64, title_bytes),
3081            ("kind", kind_rows, kind_bytes),
3082            ("embedding", inner.embeddings.len() as u64, embedding_bytes),
3083        ]
3084    }
3085
3086    /// Number of node records currently stored.
3087    #[must_use]
3088    pub fn node_count(&self) -> u64 {
3089        read(&self.inner).nodes.len() as u64
3090    }
3091
3092    /// Number of edge records currently stored.
3093    #[must_use]
3094    pub fn edge_count(&self) -> u64 {
3095        read(&self.inner).edges.len() as u64
3096    }
3097
3098    /// The next node id the allocator will hand out (monotonic; never reused).
3099    #[must_use]
3100    pub fn next_node_id(&self) -> u64 {
3101        read(&self.inner).next_node_id + 1
3102    }
3103
3104    /// The next edge id the allocator will hand out (monotonic; never reused).
3105    #[must_use]
3106    pub fn next_edge_id(&self) -> u64 {
3107        read(&self.inner).next_edge_id + 1
3108    }
3109}
3110
3111/// On-disk bytes before and after a [`NativeGraph::compact_wal`] — the storage
3112/// panel's reclaimed-bytes report. `None` fields for an in-memory engine.
3113#[cfg(not(target_arch = "wasm32"))]
3114#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
3115pub struct CompactWalStats {
3116    /// WAL size before compaction, or `None` for an in-memory engine.
3117    pub bytes_before: Option<u64>,
3118    /// WAL size after compaction, or `None` for an in-memory engine.
3119    pub bytes_after: Option<u64>,
3120}
3121
3122#[cfg(not(target_arch = "wasm32"))]
3123impl CompactWalStats {
3124    /// Bytes reclaimed (`before - after`, saturating), or `0` when unmeasurable.
3125    #[must_use]
3126    pub fn reclaimed(&self) -> u64 {
3127        match (self.bytes_before, self.bytes_after) {
3128            (Some(b), Some(a)) => b.saturating_sub(a),
3129            _ => 0,
3130        }
3131    }
3132}
3133
3134/// One registered transaction's private state — the same triple
3135/// [`NativeTx`] holds, parked inside the engine so a session can reference
3136/// it by id across statements.
3137struct TxSlot {
3138    /// The snapshot the transaction began from (commit-time conflict check).
3139    base: Arc<Inner>,
3140    /// The private working copy (copy-on-write on first mutation).
3141    working: Arc<Inner>,
3142    /// The WAL ops produced so far, in causal order.
3143    ops: Vec<WalOp>,
3144}
3145
3146/// Handle to a registered (session-owned) transaction — see
3147/// [`NativeGraph::tx_begin`].
3148#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
3149pub struct NativeTxId(u64);
3150
3151/// A per-statement [`GraphEngine`] view of one registered transaction:
3152/// reads serve the transaction's working copy (read-your-writes), writes
3153/// buffer onto it — nothing touches the live graph until
3154/// [`NativeGraph::tx_commit`]. Derived fresh for each statement via
3155/// [`NativeGraph::tx_engine`], so a session never holds a borrow across
3156/// statements. Every operation locks the slot table briefly; concurrent
3157/// statements in different transactions serialize per operation, not per
3158/// statement.
3159pub struct NativeTxEngine<'a> {
3160    graph: &'a NativeGraph,
3161    id: u64,
3162}
3163
3164impl NativeTxEngine<'_> {
3165    /// Run `f` on this transaction's slot; a closed slot (committed /
3166    /// rolled back) surfaces as a backend error rather than a panic.
3167    fn with_slot<R>(&self, f: impl FnOnce(&mut TxSlot) -> Result<R>) -> Result<R> {
3168        let mut slots = self.graph.reg_txs.lock().unwrap_or_else(|e| e.into_inner());
3169        let slot = slots.get_mut(&self.id).ok_or_else(|| {
3170            CoreError::Backend("the transaction has already been closed".to_string())
3171        })?;
3172        f(slot)
3173    }
3174}
3175
3176impl GraphEngine for NativeTxEngine<'_> {
3177    fn create_node(&self, new_node: NewNode) -> Result<Node> {
3178        self.with_slot(|slot| {
3179            let node = Arc::make_mut(&mut slot.working).create_node(new_node)?;
3180            slot.ops.push(WalOp::UpsertNode(node.clone()));
3181            Ok(node)
3182        })
3183    }
3184
3185    fn get_node(&self, id: u64) -> Result<Option<Arc<Node>>> {
3186        self.with_slot(|slot| Ok(slot.working.get_node_arc(id)))
3187    }
3188
3189    fn update_node(&self, id: u64, patch: NodePatch) -> Result<Node> {
3190        self.with_slot(|slot| {
3191            let node = Arc::make_mut(&mut slot.working).update_node(id, patch)?;
3192            slot.ops.push(WalOp::UpsertNode(node.clone()));
3193            Ok(node)
3194        })
3195    }
3196
3197    fn delete_node(&self, id: u64) -> Result<()> {
3198        self.with_slot(|slot| {
3199            Arc::make_mut(&mut slot.working).delete_node(id)?;
3200            slot.ops.push(WalOp::DeleteNode(id));
3201            Ok(())
3202        })
3203    }
3204
3205    fn create_edge(&self, new_edge: NewEdge) -> Result<Edge> {
3206        self.with_slot(|slot| {
3207            let edge = Arc::make_mut(&mut slot.working).create_edge(new_edge)?;
3208            slot.ops.push(WalOp::UpsertEdge(edge.clone()));
3209            Ok(edge)
3210        })
3211    }
3212
3213    fn get_edge(&self, id: u64) -> Result<Option<Edge>> {
3214        self.with_slot(|slot| Ok(slot.working.get_edge(id)))
3215    }
3216
3217    fn update_edge(&self, id: u64, patch: EdgePatch) -> Result<Edge> {
3218        self.with_slot(|slot| {
3219            let edge = Arc::make_mut(&mut slot.working).update_edge(id, patch)?;
3220            slot.ops.push(WalOp::UpsertEdge(edge.clone()));
3221            Ok(edge)
3222        })
3223    }
3224
3225    fn delete_edge(&self, id: u64) -> Result<()> {
3226        self.with_slot(|slot| {
3227            Arc::make_mut(&mut slot.working).delete_edge(id)?;
3228            slot.ops.push(WalOp::DeleteEdge(id));
3229            Ok(())
3230        })
3231    }
3232
3233    fn neighbor_ids(
3234        &self,
3235        node_id: u64,
3236        direction: Direction,
3237        kind: Option<&str>,
3238    ) -> Result<Vec<u64>> {
3239        self.with_slot(|slot| Ok(slot.working.neighbor_ids(node_id, direction, kind)))
3240    }
3241
3242    fn neighbors(
3243        &self,
3244        node_id: u64,
3245        direction: Direction,
3246        kind: Option<&str>,
3247    ) -> Result<Vec<Arc<Node>>> {
3248        self.with_slot(|slot| Ok(slot.working.neighbors_arc(node_id, direction, kind)))
3249    }
3250
3251    fn edges_of(&self, node_id: u64, direction: Direction) -> Result<Vec<Edge>> {
3252        self.with_slot(|slot| Ok(slot.working.edges_of(node_id, direction)))
3253    }
3254
3255    fn all_nodes(&self) -> Result<Vec<Arc<Node>>> {
3256        self.with_slot(|slot| Ok(slot.working.all_nodes_arc()))
3257    }
3258
3259    fn all_edges(&self) -> Result<Vec<Edge>> {
3260        self.with_slot(|slot| Ok(slot.working.all_edges()))
3261    }
3262
3263    fn nodes_by_kind(&self, kind: &str, limit: usize, offset: usize) -> Result<Vec<Arc<Node>>> {
3264        self.with_slot(|slot| Ok(slot.working.nodes_by_kind_arc(kind, limit, offset)))
3265    }
3266
3267    fn export_dump(&self) -> Result<Dump> {
3268        Err(CoreError::Backend(
3269            "export is not available inside a transaction".to_string(),
3270        ))
3271    }
3272
3273    fn apply_dump(&self, _dump: Dump) -> Result<ImportReport> {
3274        Err(CoreError::Backend(
3275            "bulk import is not available inside a transaction".to_string(),
3276        ))
3277    }
3278}
3279
3280/// A transaction over a [`NativeGraph`]: reads a consistent snapshot taken at
3281/// [`begin`](NativeGraph::begin), buffers writes on a private working copy, and
3282/// applies them atomically at [`commit`](Self::commit) (or discards them on
3283/// [`rollback`](Self::rollback) / drop). Reads reflect the transaction's own
3284/// buffered writes (read-your-writes). See [`NativeGraph::begin`].
3285pub struct NativeTx<'a> {
3286    engine: &'a NativeGraph,
3287    /// The snapshot the transaction began from — used to detect, at commit, a
3288    /// concurrent change (the live `Arc` pointer will differ).
3289    base: Arc<Inner>,
3290    /// The private working copy; starts shared with `base` and copy-on-writes
3291    /// on the first mutation.
3292    working: Arc<Inner>,
3293    /// The write-ahead-log ops this transaction produced, in causal order,
3294    /// flushed to the engine's WAL as one atomic batch at commit (durable
3295    /// engine only).
3296    ops: Vec<WalOp>,
3297}
3298
3299impl NativeTx<'_> {
3300    /// Commit the buffered writes atomically. Succeeds only if (a) the graph
3301    /// has not changed since [`begin`](NativeGraph::begin) and (b) the resulting
3302    /// state satisfies every declared [`Constraint`]; otherwise the writes are
3303    /// discarded and the reason is returned for the caller to handle.
3304    ///
3305    /// # Errors
3306    /// - [`CommitError::Conflict`] if another writer committed since this
3307    ///   transaction began.
3308    /// - [`CommitError::Constraint`] if the transaction's writes would violate a
3309    ///   declared constraint.
3310    pub fn commit(self) -> std::result::Result<(), CommitError> {
3311        // Durability + change-feed: the shared commit tail records the whole
3312        // transaction as one fsynced batch *before* the swap, so the commit
3313        // is all-or-nothing — an I/O failure leaves the graph, the log, and
3314        // the feed untouched. On a non-durable engine the WAL step is a
3315        // no-op and only the feed advances.
3316        self.engine.commit_parts(self.base, self.working, &self.ops)
3317    }
3318
3319    /// Discard the transaction's buffered writes. Equivalent to dropping it.
3320    pub fn rollback(self) {}
3321
3322    // ----- reads (reflect the transaction's own buffered writes) -------------
3323
3324    /// Fetch a node by id within the transaction.
3325    pub fn get_node(&self, id: u64) -> Option<Node> {
3326        self.working.get_node(id)
3327    }
3328
3329    /// Fetch an edge by id within the transaction.
3330    pub fn get_edge(&self, id: u64) -> Option<Edge> {
3331        self.working.get_edge(id)
3332    }
3333
3334    /// Distinct neighbour ids within the transaction.
3335    pub fn neighbor_ids(&self, node_id: u64, direction: Direction, kind: Option<&str>) -> Vec<u64> {
3336        self.working.neighbor_ids(node_id, direction, kind)
3337    }
3338
3339    /// Every node visible within the transaction.
3340    pub fn all_nodes(&self) -> Vec<Node> {
3341        self.working.all_nodes()
3342    }
3343
3344    /// Every edge visible within the transaction.
3345    pub fn all_edges(&self) -> Vec<Edge> {
3346        self.working.all_edges()
3347    }
3348
3349    // ----- writes (buffered on the private working copy) ---------------------
3350
3351    /// Create a node within the transaction. Mirrors
3352    /// [`GraphEngine::create_node`].
3353    ///
3354    /// # Errors
3355    /// [`CoreError::DuplicateTitle`]
3356    /// if the title is taken in the transaction's view.
3357    pub fn create_node(&mut self, new_node: NewNode) -> Result<Node> {
3358        let node = Arc::make_mut(&mut self.working).create_node(new_node)?;
3359        self.ops.push(WalOp::UpsertNode(node.clone()));
3360        Ok(node)
3361    }
3362
3363    /// Update a node within the transaction.
3364    ///
3365    /// # Errors
3366    /// Propagates any [`CoreError`] from the update.
3367    pub fn update_node(&mut self, id: u64, patch: NodePatch) -> Result<Node> {
3368        let node = Arc::make_mut(&mut self.working).update_node(id, patch)?;
3369        self.ops.push(WalOp::UpsertNode(node.clone()));
3370        Ok(node)
3371    }
3372
3373    /// Delete a node (and its incident edges) within the transaction.
3374    ///
3375    /// # Errors
3376    /// [`CoreError::NodeNotFound`] if
3377    /// absent in the transaction's view.
3378    pub fn delete_node(&mut self, id: u64) -> Result<()> {
3379        Arc::make_mut(&mut self.working).delete_node(id)?;
3380        self.ops.push(WalOp::DeleteNode(id));
3381        Ok(())
3382    }
3383
3384    /// Create an edge within the transaction.
3385    ///
3386    /// # Errors
3387    /// Propagates any [`CoreError`] from the create.
3388    pub fn create_edge(&mut self, new_edge: NewEdge) -> Result<Edge> {
3389        let edge = Arc::make_mut(&mut self.working).create_edge(new_edge)?;
3390        self.ops.push(WalOp::UpsertEdge(edge.clone()));
3391        Ok(edge)
3392    }
3393
3394    /// Update an edge within the transaction.
3395    ///
3396    /// # Errors
3397    /// Propagates any [`CoreError`] from the update.
3398    pub fn update_edge(&mut self, id: u64, patch: EdgePatch) -> Result<Edge> {
3399        let edge = Arc::make_mut(&mut self.working).update_edge(id, patch)?;
3400        self.ops.push(WalOp::UpsertEdge(edge.clone()));
3401        Ok(edge)
3402    }
3403
3404    /// Delete an edge within the transaction.
3405    ///
3406    /// # Errors
3407    /// [`CoreError::EdgeNotFound`] if
3408    /// absent in the transaction's view.
3409    pub fn delete_edge(&mut self, id: u64) -> Result<()> {
3410        Arc::make_mut(&mut self.working).delete_edge(id)?;
3411        self.ops.push(WalOp::DeleteEdge(id));
3412        Ok(())
3413    }
3414}
3415
3416/// Recover a poisoned lock rather than propagating the panic — matches the
3417/// library-wide policy (no `unwrap`/`expect` in non-test code; a poisoned
3418/// graph lock still holds valid data).
3419fn read(inner: &RwLock<Arc<Inner>>) -> std::sync::RwLockReadGuard<'_, Arc<Inner>> {
3420    inner.read().unwrap_or_else(|e| e.into_inner())
3421}
3422
3423fn write(inner: &RwLock<Arc<Inner>>) -> std::sync::RwLockWriteGuard<'_, Arc<Inner>> {
3424    inner.write().unwrap_or_else(|e| e.into_inner())
3425}
3426
3427impl NativeGraph {
3428    /// The writer lock for an ordinary write — refused while a transaction is
3429    /// prepared (the two-phase-commit fence). The check runs *after*
3430    /// taking the lock, and `tx_prepare` raises the fence under the same lock,
3431    /// so no write can slip in between a prepare and its resolution. Reads,
3432    /// replica application, constraint declaration, compaction and the 2PC
3433    /// resolvers take the plain lock.
3434    fn write_for_commit(&self) -> Result<std::sync::RwLockWriteGuard<'_, Arc<Inner>>> {
3435        let guard = write(&self.inner);
3436        if !guard.prepared.is_empty() {
3437            return Err(CoreError::PreparedTransactionPending(
3438                guard.prepared.keys().cloned().collect(),
3439            ));
3440        }
3441        Ok(guard)
3442    }
3443}
3444
3445impl GraphEngine for NativeGraph {
3446    fn create_node(&self, new_node: NewNode) -> Result<Node> {
3447        let node = Arc::make_mut(&mut *self.write_for_commit()?).create_node(new_node)?;
3448        self.record(&[WalOp::UpsertNode(node.clone())])?;
3449        self.stamp_write(StampTarget::Node(node.id));
3450        Ok(node)
3451    }
3452
3453    fn get_node(&self, id: u64) -> Result<Option<Arc<Node>>> {
3454        // Zero-copy: an `Arc` handle to the stored record (refcount bump).
3455        Ok(read(&self.inner).get_node_arc(id))
3456    }
3457
3458    fn update_node(&self, id: u64, patch: NodePatch) -> Result<Node> {
3459        let node = Arc::make_mut(&mut *self.write_for_commit()?).update_node(id, patch)?;
3460        self.record(&[WalOp::UpsertNode(node.clone())])?;
3461        self.stamp_write(StampTarget::Node(node.id));
3462        Ok(node)
3463    }
3464
3465    fn delete_node(&self, id: u64) -> Result<()> {
3466        // Capture the uuid before removal so the tombstone can be remapped by a
3467        // peer (issue #389).
3468        let uuid = read(&self.inner).get_node_arc(id).map(|n| n.uuid);
3469        Arc::make_mut(&mut *self.write_for_commit()?).delete_node(id)?;
3470        self.record(&[WalOp::DeleteNode(id)])?;
3471        if let Some(uuid) = uuid {
3472            self.stamp_tombstone(StampTarget::Node(id), uuid);
3473            self.checkpoint_tombstones();
3474        }
3475        Ok(())
3476    }
3477
3478    fn delete_nodes(&self, ids: &[u64]) -> Result<usize> {
3479        // Batched delete under a single durability boundary (issue #435):
3480        // deleting a subtree of `N` nodes costs one fsync, not `N`. Mirrors the
3481        // per-node effects of `delete_node` — incident edges + index entries
3482        // dropped (the `DeleteNode` op cascades on replay), a durable tombstone
3483        // stamped per node (issue #389) — and skips ids that are already absent.
3484        //
3485        // Built on a private working copy that is swapped in only *after* the
3486        // WAL append is durable, so an I/O failure leaves the live graph, the
3487        // log and the feed untouched (all-or-nothing), exactly like a committed
3488        // transaction. One `record` call flushes the whole batch via group
3489        // commit (one fsync).
3490        let mut live = self.write_for_commit()?;
3491        let mut working = Arc::clone(&live);
3492        let w = Arc::make_mut(&mut working);
3493        let mut ops: Vec<WalOp> = Vec::with_capacity(ids.len());
3494        let mut tombs: Vec<(StampTarget, [u8; 16])> = Vec::with_capacity(ids.len());
3495        for &id in ids {
3496            let Some(uuid) = w.get_node_arc(id).map(|n| n.uuid) else {
3497                continue; // already absent — skip, not an error
3498            };
3499            w.delete_node(id)?;
3500            ops.push(WalOp::DeleteNode(id));
3501            tombs.push((StampTarget::Node(id), uuid));
3502        }
3503        if ops.is_empty() {
3504            return Ok(0);
3505        }
3506        self.record(&ops)?;
3507        *live = working;
3508        drop(live);
3509        for (target, uuid) in &tombs {
3510            self.stamp_tombstone(*target, *uuid);
3511        }
3512        self.checkpoint_tombstones();
3513        Ok(ops.len())
3514    }
3515
3516    fn create_edge(&self, new_edge: NewEdge) -> Result<Edge> {
3517        let edge = Arc::make_mut(&mut *self.write_for_commit()?).create_edge(new_edge)?;
3518        self.record(&[WalOp::UpsertEdge(edge.clone())])?;
3519        self.stamp_write(StampTarget::Edge(edge.id));
3520        Ok(edge)
3521    }
3522
3523    fn get_edge(&self, id: u64) -> Result<Option<Edge>> {
3524        Ok(read(&self.inner).get_edge(id))
3525    }
3526
3527    fn update_edge(&self, id: u64, patch: EdgePatch) -> Result<Edge> {
3528        let edge = Arc::make_mut(&mut *self.write_for_commit()?).update_edge(id, patch)?;
3529        self.record(&[WalOp::UpsertEdge(edge.clone())])?;
3530        self.stamp_write(StampTarget::Edge(edge.id));
3531        Ok(edge)
3532    }
3533
3534    fn delete_edge(&self, id: u64) -> Result<()> {
3535        let uuid = read(&self.inner).get_edge_arc(id).map(|e| e.uuid);
3536        Arc::make_mut(&mut *self.write_for_commit()?).delete_edge(id)?;
3537        self.record(&[WalOp::DeleteEdge(id)])?;
3538        if let Some(uuid) = uuid {
3539            self.stamp_tombstone(StampTarget::Edge(id), uuid);
3540            self.checkpoint_tombstones();
3541        }
3542        Ok(())
3543    }
3544
3545    fn neighbor_ids(
3546        &self,
3547        node_id: u64,
3548        direction: Direction,
3549        kind: Option<&str>,
3550    ) -> Result<Vec<u64>> {
3551        Ok(read(&self.inner).neighbor_ids(node_id, direction, kind))
3552    }
3553
3554    fn neighbors(
3555        &self,
3556        node_id: u64,
3557        direction: Direction,
3558        kind: Option<&str>,
3559    ) -> Result<Vec<Arc<Node>>> {
3560        Ok(read(&self.inner).neighbors_arc(node_id, direction, kind))
3561    }
3562
3563    fn edges_of(&self, node_id: u64, direction: Direction) -> Result<Vec<Edge>> {
3564        Ok(read(&self.inner).edges_of(node_id, direction))
3565    }
3566
3567    fn all_nodes(&self) -> Result<Vec<Arc<Node>>> {
3568        Ok(read(&self.inner).all_nodes_arc())
3569    }
3570
3571    fn count_nodes(&self) -> Result<u64> {
3572        Ok(read(&self.inner).nodes.len() as u64)
3573    }
3574
3575    fn count_nodes_by_kind(&self, kind: &str) -> Result<u64> {
3576        Ok(read(&self.inner)
3577            .kind_index
3578            .get(kind)
3579            .map_or(0, |ids| ids.len()) as u64)
3580    }
3581
3582    fn all_edges(&self) -> Result<Vec<Edge>> {
3583        Ok(read(&self.inner).all_edges())
3584    }
3585
3586    fn nodes_by_kind(&self, kind: &str, limit: usize, offset: usize) -> Result<Vec<Arc<Node>>> {
3587        Ok(read(&self.inner).nodes_by_kind_arc(kind, limit, offset))
3588    }
3589
3590    fn export_dump(&self) -> Result<Dump> {
3591        let g = read(&self.inner);
3592        let nodes = g.all_nodes();
3593        let edges = g.all_edges();
3594        // Derive the counters from the live max id (`max + 1`), matching
3595        // `Drevo::build_dump` byte-for-byte so a dump is engine-independent.
3596        let next_node_id = nodes.iter().map(|n| n.id).max().map_or(1, |m| m + 1);
3597        let next_edge_id = edges.iter().map(|e| e.id).max().map_or(1, |m| m + 1);
3598        Ok(Dump {
3599            format: FORMAT_V1.to_string(),
3600            exported_at: now_ms(),
3601            next_node_id,
3602            next_edge_id,
3603            nodes,
3604            edges,
3605        })
3606    }
3607
3608    fn apply_dump(&self, dump: Dump) -> Result<ImportReport> {
3609        let mut report = ImportReport::default();
3610        // Buffer the ops that actually land so they can be journaled in one
3611        // fsync after the in-memory apply succeeds (durability parity with the
3612        // live write paths).
3613        let mut applied: Vec<WalOp> = Vec::with_capacity(dump.nodes.len() + dump.edges.len());
3614        {
3615            let mut guard = self.write_for_commit()?;
3616            let g = Arc::make_mut(&mut guard);
3617
3618            // --- Nodes: skip byte-equal, reject id-collision, else upsert ---
3619            for node in &dump.nodes {
3620                match g.get_node(node.id) {
3621                    Some(existing) if existing == *node => {
3622                        report.nodes_skipped += 1;
3623                        continue;
3624                    }
3625                    Some(_) => {
3626                        return Err(DumpError::IdCollision(format!(
3627                            "node id {} already exists with different content",
3628                            node.id
3629                        ))
3630                        .into());
3631                    }
3632                    None => {}
3633                }
3634                g.apply_wal_op(WalOp::UpsertNode(node.clone()));
3635                applied.push(WalOp::UpsertNode(node.clone()));
3636                report.nodes_imported += 1;
3637            }
3638
3639            // --- Edges: endpoints must resolve (nodes are already applied) ---
3640            for edge in &dump.edges {
3641                match g.get_edge(edge.id) {
3642                    Some(existing) if existing == *edge => {
3643                        report.edges_skipped += 1;
3644                        continue;
3645                    }
3646                    Some(_) => {
3647                        return Err(DumpError::IdCollision(format!(
3648                            "edge id {} already exists with different content",
3649                            edge.id
3650                        ))
3651                        .into());
3652                    }
3653                    None => {}
3654                }
3655                if g.get_node(edge.from_id).is_none() {
3656                    return Err(CoreError::NodeNotFound(edge.from_id));
3657                }
3658                if g.get_node(edge.to_id).is_none() {
3659                    return Err(CoreError::NodeNotFound(edge.to_id));
3660                }
3661                g.apply_wal_op(WalOp::UpsertEdge(edge.clone()));
3662                applied.push(WalOp::UpsertEdge(edge.clone()));
3663                report.edges_imported += 1;
3664            }
3665
3666            // Clamp id counters above every imported id so a post-migration
3667            // create never reuses one (`apply_wal_op` already raised them to
3668            // the max imported id; honour a higher producer counter too).
3669            g.next_node_id = g.next_node_id.max(dump.next_node_id.saturating_sub(1));
3670            g.next_edge_id = g.next_edge_id.max(dump.next_edge_id.saturating_sub(1));
3671        }
3672
3673        if !applied.is_empty() {
3674            self.record(&applied)?;
3675        }
3676
3677        Ok(report)
3678    }
3679}
3680
3681/// A frozen, read-only view of a [`NativeGraph`] at the instant
3682/// [`NativeGraph::snapshot`] was called. Reads are
3683/// served from the captured [`Arc`] and are unaffected by later writes to the
3684/// engine, so a whole traversal sees one consistent version of the graph.
3685#[derive(Clone)]
3686pub struct GraphSnapshot {
3687    inner: Arc<Inner>,
3688}
3689
3690impl GraphSnapshot {
3691    /// Fetch a node by id, or `None` if absent in this snapshot.
3692    pub fn get_node(&self, id: u64) -> Option<Node> {
3693        self.inner.get_node(id)
3694    }
3695
3696    /// Fetch an edge by id, or `None` if absent in this snapshot.
3697    pub fn get_edge(&self, id: u64) -> Option<Edge> {
3698        self.inner.get_edge(id)
3699    }
3700
3701    /// Zero-copy node fetch within the snapshot — an `Arc<Node>` handle instead
3702    /// of a deep clone (see [`NativeGraph::get_node_arc`]).
3703    pub fn get_node_arc(&self, id: u64) -> Option<Arc<Node>> {
3704        self.inner.get_node_arc(id)
3705    }
3706
3707    /// Zero-copy edge fetch within the snapshot (see
3708    /// [`NativeGraph::get_edge_arc`]).
3709    pub fn get_edge_arc(&self, id: u64) -> Option<Arc<Edge>> {
3710        self.inner.get_edge_arc(id)
3711    }
3712
3713    /// Distinct neighbour ids in `direction`, optionally kind-filtered.
3714    pub fn neighbor_ids(&self, node_id: u64, direction: Direction, kind: Option<&str>) -> Vec<u64> {
3715        self.inner.neighbor_ids(node_id, direction, kind)
3716    }
3717
3718    /// Distinct neighbours as zero-copy `Arc<Node>` handles (see
3719    /// [`NativeGraph::neighbors_arc`]).
3720    pub fn neighbors_arc(
3721        &self,
3722        node_id: u64,
3723        direction: Direction,
3724        kind: Option<&str>,
3725    ) -> Vec<Arc<Node>> {
3726        self.inner.neighbors_arc(node_id, direction, kind)
3727    }
3728
3729    /// Adjacent nodes in `direction`, optionally kind-filtered.
3730    pub fn neighbors(&self, node_id: u64, direction: Direction, kind: Option<&str>) -> Vec<Node> {
3731        self.inner.neighbors(node_id, direction, kind)
3732    }
3733
3734    /// Full edge records incident to `node_id` in `direction`.
3735    pub fn edges_of(&self, node_id: u64, direction: Direction) -> Vec<Edge> {
3736        self.inner.edges_of(node_id, direction)
3737    }
3738
3739    /// Every node in this snapshot.
3740    pub fn all_nodes(&self) -> Vec<Node> {
3741        self.inner.all_nodes()
3742    }
3743
3744    /// Every edge in this snapshot.
3745    pub fn all_edges(&self) -> Vec<Edge> {
3746        self.inner.all_edges()
3747    }
3748
3749    /// Nodes of `kind`, paginated by `limit`/`offset`.
3750    pub fn nodes_by_kind(&self, kind: &str, limit: usize, offset: usize) -> Vec<Node> {
3751        self.inner.nodes_by_kind(kind, limit, offset)
3752    }
3753
3754    /// A Compressed-Sparse-Row view of this snapshot's **out**-adjacency
3755    /// ([`CsrAdjacency`]) — the cache-friendly, lock-free substrate for
3756    /// whole-graph parallel scans and algorithms. Vertices are the
3757    /// snapshot's node ids in ascending order; each vertex's neighbours are its
3758    /// distinct out-neighbours (as in [`neighbor_ids`](Self::neighbor_ids) with
3759    /// no kind filter). Built by flattening the frozen snapshot, so it is a
3760    /// consistent one-version view with no locking.
3761    #[must_use]
3762    pub fn csr_out(&self) -> CsrAdjacency {
3763        let mut vertices: Vec<u64> = self.inner.nodes.keys().copied().collect();
3764        vertices.sort_unstable();
3765        CsrAdjacency::from_out_neighbors(vertices, |id| {
3766            self.inner.neighbor_ids(id, Direction::Outgoing, None)
3767        })
3768    }
3769
3770    /// A Compressed-Sparse-Row view of this snapshot's **in**-adjacency — the
3771    /// reverse of [`csr_out`](Self::csr_out): each vertex's "neighbours" are its
3772    /// distinct **predecessors** (nodes with an edge *into* it). Same
3773    /// [`CsrAdjacency`] type and dense-index layout, so reverse traversal and
3774    /// pull-style algorithms (reverse reachability, in-degree, reverse PageRank)
3775    /// run over it exactly as forward ones run over `csr_out`.
3776    #[must_use]
3777    pub fn csr_in(&self) -> CsrAdjacency {
3778        let mut vertices: Vec<u64> = self.inner.nodes.keys().copied().collect();
3779        vertices.sort_unstable();
3780        CsrAdjacency::from_out_neighbors(vertices, |id| {
3781            self.inner.neighbor_ids(id, Direction::Incoming, None)
3782        })
3783    }
3784}
3785
3786#[cfg(test)]
3787mod kind_index_tests {
3788    //! The private node-kind index must always equal the ground truth derived
3789    //! from the live node set — the definitive guard that every node-map
3790    //! mutation site (create / update / delete / WAL replay) keeps it in sync.
3791    use super::*;
3792    use std::collections::BTreeSet;
3793
3794    fn nn(kind: &str, title: &str) -> NewNode {
3795        NewNode {
3796            kind: kind.into(),
3797            title: title.into(),
3798            body: String::new(),
3799            body_html: String::new(),
3800            properties: Default::default(),
3801        }
3802    }
3803
3804    /// The kind index recomputed from scratch off `nodes` — what any correct
3805    /// incremental maintenance must converge to.
3806    fn ground_truth(inner: &Inner) -> HashMap<String, BTreeSet<u64>> {
3807        let mut truth: HashMap<String, BTreeSet<u64>> = HashMap::new();
3808        for node in inner.nodes.values() {
3809            truth.entry(node.kind.clone()).or_default().insert(node.id);
3810        }
3811        truth
3812    }
3813
3814    #[test]
3815    fn index_matches_ground_truth_after_mixed_workload() {
3816        let mut inner = Inner::default();
3817        let a = inner.create_node(nn("person", "a")).unwrap();
3818        let b = inner.create_node(nn("person", "b")).unwrap();
3819        let _c = inner.create_node(nn("city", "c")).unwrap();
3820        assert_eq!(inner.kind_index, ground_truth(&inner));
3821
3822        // Re-kind b (person -> city): must move buckets.
3823        inner
3824            .update_node(
3825                b.id,
3826                NodePatch {
3827                    kind: Some("city".into()),
3828                    ..Default::default()
3829                },
3830            )
3831            .unwrap();
3832        assert_eq!(inner.kind_index, ground_truth(&inner));
3833
3834        // Delete a: person bucket empties and is dropped (no empty bucket left).
3835        inner.delete_node(a.id).unwrap();
3836        assert_eq!(inner.kind_index, ground_truth(&inner));
3837        assert!(!inner.kind_index.contains_key("person"));
3838
3839        // A replacing WAL upsert that changes an existing node's kind must
3840        // unindex the old kind and index the new one.
3841        let mut c_rekind = inner.get_node(_c.id).unwrap();
3842        c_rekind.kind = "town".into();
3843        inner.apply_wal_op(WalOp::UpsertNode(c_rekind));
3844        assert_eq!(inner.kind_index, ground_truth(&inner));
3845        // c left `city` for `town`; b (re-kinded to city earlier) still holds it.
3846        assert_eq!(inner.kind_index["town"], BTreeSet::from([_c.id]));
3847        assert_eq!(inner.kind_index["city"], BTreeSet::from([b.id]));
3848
3849        // A WAL delete removes its id from the index.
3850        inner.apply_wal_op(WalOp::DeleteNode(_c.id));
3851        assert_eq!(inner.kind_index, ground_truth(&inner));
3852    }
3853}
3854
3855#[cfg(test)]
3856mod adjacency_kind_sort_tests {
3857    //! Adjacency lists are kept sorted by `(kind_id, neighbor_id, edge_id)` so a
3858    //! kind-filtered fan-out can binary-search the run for a relationship type
3859    //! instead of scanning the whole list.
3860    //! These pin the invariant at every mutation site and prove the kind-run
3861    //! fast path returns exactly what a full linear filter would.
3862    use super::*;
3863
3864    fn nn(kind: &str, title: &str) -> NewNode {
3865        NewNode {
3866            kind: kind.into(),
3867            title: title.into(),
3868            body: String::new(),
3869            body_html: String::new(),
3870            properties: Default::default(),
3871        }
3872    }
3873
3874    fn ne(from: u64, to: u64, kind: &str) -> NewEdge {
3875        NewEdge {
3876            from_id: from,
3877            to_id: to,
3878            kind: kind.into(),
3879            weight: 1.0,
3880            properties: Default::default(),
3881        }
3882    }
3883
3884    /// The invariant key an adjacency list must be ordered by.
3885    fn key(e: &AdjEntry) -> (u32, u64, u64) {
3886        (e.kind_id, e.neighbor_id, e.edge_id)
3887    }
3888
3889    fn is_sorted(v: &[AdjEntry]) -> bool {
3890        v.windows(2).all(|w| key(&w[0]) <= key(&w[1]))
3891    }
3892
3893    fn assert_all_adjacency_sorted(inner: &Inner) {
3894        for (n, v) in inner.out_adj.iter() {
3895            assert!(is_sorted(v), "out_adj[{n}] not kind-sorted: {v:?}");
3896        }
3897        for (n, v) in inner.in_adj.iter() {
3898            assert!(is_sorted(v), "in_adj[{n}] not kind-sorted: {v:?}");
3899        }
3900    }
3901
3902    /// Build a small hub whose out-edges are inserted in an order that is NOT
3903    /// already `(kind_id, neighbor_id)` sorted, across several kinds.
3904    fn hub_graph() -> (Inner, u64, Vec<u64>) {
3905        let mut inner = Inner::default();
3906        let hub = inner.create_node(nn("n", "hub")).unwrap().id;
3907        let mut leaves = Vec::new();
3908        for i in 0..6 {
3909            leaves.push(inner.create_node(nn("n", &format!("l{i}"))).unwrap().id);
3910        }
3911        // Interleave kinds and neighbours so insertion order != sorted order.
3912        // kinds get interned in first-seen order: b=0, a=1, c=2.
3913        inner.create_edge(ne(hub, leaves[3], "b")).unwrap();
3914        inner.create_edge(ne(hub, leaves[0], "a")).unwrap();
3915        inner.create_edge(ne(hub, leaves[5], "c")).unwrap();
3916        inner.create_edge(ne(hub, leaves[1], "a")).unwrap();
3917        inner.create_edge(ne(hub, leaves[2], "b")).unwrap();
3918        inner.create_edge(ne(hub, leaves[4], "a")).unwrap();
3919        (inner, hub, leaves)
3920    }
3921
3922    #[test]
3923    fn adjacency_is_kind_sorted_after_interleaved_inserts() {
3924        let (inner, _hub, _) = hub_graph();
3925        assert_all_adjacency_sorted(&inner);
3926    }
3927
3928    #[test]
3929    fn adjacency_stays_sorted_after_kind_update() {
3930        let (mut inner, hub, _) = hub_graph();
3931        // Re-kind the very first out-edge (edge id 1, kind "b") to "a": its slot
3932        // must migrate so the list stays `(kind_id, …)` ordered.
3933        inner
3934            .update_edge(
3935                1,
3936                EdgePatch {
3937                    kind: Some("a".into()),
3938                    ..Default::default()
3939                },
3940            )
3941            .unwrap();
3942        assert_all_adjacency_sorted(&inner);
3943        // And the incoming side of that edge's target too.
3944        let _ = hub;
3945    }
3946
3947    #[test]
3948    fn adjacency_stays_sorted_after_delete_and_wal_upsert() {
3949        let (mut inner, hub, leaves) = hub_graph();
3950        inner.delete_edge(2).unwrap(); // remove one "a" edge
3951        assert_all_adjacency_sorted(&inner);
3952        // A replacing WAL upsert (kind change) must re-land sorted too.
3953        inner.apply_wal_op(WalOp::UpsertEdge(Edge {
3954            id: 3,
3955            uuid: [0u8; 16],
3956            from_id: hub,
3957            to_id: leaves[5],
3958            kind: "a".into(),
3959            weight: 1.0,
3960            created_at: 0,
3961            properties: Default::default(),
3962        }));
3963        assert_all_adjacency_sorted(&inner);
3964    }
3965
3966    #[test]
3967    fn kind_run_fast_path_matches_full_linear_filter() {
3968        let (inner, hub, _) = hub_graph();
3969        for kind in ["a", "b", "c", "missing"] {
3970            let want = inner.kind_id_of(kind);
3971            // Brute-force reference: every incident out-entry whose kind matches.
3972            let mut expect: Vec<u64> = Vec::new();
3973            inner.for_each_incident(hub, Direction::Outgoing, |e| {
3974                if want.is_some_and(|k| k == e.kind_id) {
3975                    expect.push(e.neighbor_id);
3976                }
3977            });
3978            expect.sort_unstable();
3979            let mut got = inner.neighbor_ids(hub, Direction::Outgoing, Some(kind));
3980            got.sort_unstable();
3981            assert_eq!(got, expect, "kind={kind}");
3982        }
3983    }
3984
3985    // ── Causal write stamping (issue #389) ──────────────────────────────────
3986
3987    fn stamp_edge(from: u64, to: u64) -> NewEdge {
3988        NewEdge {
3989            from_id: from,
3990            to_id: to,
3991            kind: "links".into(),
3992            weight: 1.0,
3993            properties: Default::default(),
3994        }
3995    }
3996
3997    #[test]
3998    fn writes_are_stamped_and_strictly_increasing() {
3999        let g = NativeGraph::new();
4000        let a = g.create_node(nn("n", "a")).unwrap();
4001        let b = g.create_node(nn("n", "b")).unwrap();
4002        let sa = g.stamp_of(StampTarget::Node(a.id)).expect("a stamped");
4003        let sb = g.stamp_of(StampTarget::Node(b.id)).expect("b stamped");
4004        assert!(sb > sa, "later write must have a greater stamp");
4005        // Every stamp carries this replica's origin.
4006        assert_eq!(sa.origin(), g.origin_id());
4007
4008        // An update bumps the node's stamp past its previous one.
4009        g.update_node(
4010            a.id,
4011            NodePatch {
4012                title: Some("a2".into()),
4013                ..Default::default()
4014            },
4015        )
4016        .unwrap();
4017        let sa2 = g.stamp_of(StampTarget::Node(a.id)).unwrap();
4018        assert!(sa2 > sb, "update must advance past all prior stamps");
4019
4020        // Edges are stamped too.
4021        let e = g.create_edge(stamp_edge(a.id, b.id)).unwrap();
4022        let se = g.stamp_of(StampTarget::Edge(e.id)).expect("edge stamped");
4023        assert!(se > sa2);
4024    }
4025
4026    #[test]
4027    fn delete_tombstones_the_stamp() {
4028        let g = NativeGraph::new();
4029        let a = g.create_node(nn("n", "a")).unwrap();
4030        let live = g.stamp_of(StampTarget::Node(a.id)).expect("a stamped");
4031        g.delete_node(a.id).unwrap();
4032        // No live stamp — but the delete leaves a tombstone with a *later* stamp,
4033        // still folded into the version vector so a peer learns of the removal.
4034        assert!(
4035            g.stamp_of(StampTarget::Node(a.id)).is_none(),
4036            "a deleted entity has no live stamp"
4037        );
4038        let tomb = g
4039            .version_vector()
4040            .get(g.origin_id())
4041            .expect("tombstone kept in the version vector");
4042        assert!(tomb > live.hlc(), "the delete stamps later than the create");
4043    }
4044
4045    #[test]
4046    fn absent_entity_has_no_stamp() {
4047        let g = NativeGraph::new();
4048        assert!(g.stamp_of(StampTarget::Node(999)).is_none());
4049        assert!(g.stamp_of(StampTarget::Edge(999)).is_none());
4050    }
4051
4052    #[test]
4053    fn distinct_in_memory_graphs_get_distinct_origins() {
4054        assert_ne!(
4055            NativeGraph::new().origin_id(),
4056            NativeGraph::new().origin_id()
4057        );
4058    }
4059
4060    #[test]
4061    fn delta_bootstraps_a_fresh_replica() {
4062        let a = NativeGraph::new();
4063        let n1 = a.create_node(nn("n", "a")).unwrap();
4064        let n2 = a.create_node(nn("n", "b")).unwrap();
4065        let e = a.create_edge(stamp_edge(n1.id, n2.id)).unwrap();
4066
4067        // A fresh replica has observed nothing, so the delta is A's whole state.
4068        let c = NativeGraph::new();
4069        assert!(c.version_vector().is_empty());
4070        let delta = a.delta_since(&c.version_vector());
4071        assert_eq!(delta.len(), 3, "2 nodes + 1 edge");
4072
4073        let stats = c.apply_delta(&delta).unwrap();
4074        assert_eq!(stats.applied, 3);
4075        assert_eq!(stats.skipped, 0);
4076
4077        // C now mirrors A's live records and stamps. Identity is the uuid: C
4078        // remaps A's ids into its own space, so compare by uuid, not by id.
4079        let cn1 = c.node_id_of_uuid(n1.uuid).expect("n1 on c");
4080        let cn2 = c.node_id_of_uuid(n2.uuid).expect("n2 on c");
4081        assert_eq!(c.get_node(cn1).unwrap().unwrap().title, "a");
4082        assert_eq!(c.get_node(cn2).unwrap().unwrap().title, "b");
4083        assert_eq!(c.get_node(cn1).unwrap().unwrap().uuid, n1.uuid);
4084
4085        // The remapped edge connects the remapped endpoints.
4086        let ce = c.edge_id_of_uuid(e.uuid).expect("edge on c");
4087        let ce_rec = c.get_edge(ce).unwrap().unwrap();
4088        assert_eq!(ce_rec.from_id, cn1);
4089        assert_eq!(ce_rec.to_id, cn2);
4090
4091        // Stamps carry across (keyed by C's local id but the same value).
4092        assert_eq!(
4093            c.stamp_of(StampTarget::Node(cn1)),
4094            a.stamp_of(StampTarget::Node(n1.id))
4095        );
4096        assert_eq!(c.version_vector(), a.version_vector());
4097    }
4098
4099    #[test]
4100    fn delta_is_idempotent_and_incremental() {
4101        let a = NativeGraph::new();
4102        a.create_node(nn("n", "a")).unwrap();
4103        let c = NativeGraph::new();
4104
4105        let d1 = a.delta_since(&c.version_vector());
4106        assert_eq!(c.apply_delta(&d1).unwrap().applied, 1);
4107
4108        // Re-applying the same delta changes nothing (idempotent LWW).
4109        let again = c.apply_delta(&d1).unwrap();
4110        assert_eq!(again.applied, 0);
4111        assert_eq!(again.skipped, 1);
4112
4113        // C is now caught up on A: nothing left to send.
4114        assert!(a.delta_since(&c.version_vector()).is_empty());
4115
4116        // One more write on A reaches C incrementally — just that entity.
4117        a.create_node(nn("n", "b")).unwrap();
4118        let d2 = a.delta_since(&c.version_vector());
4119        assert_eq!(d2.len(), 1);
4120        assert_eq!(c.apply_delta(&d2).unwrap().applied, 1);
4121        assert_eq!(a.version_vector(), c.version_vector());
4122    }
4123
4124    #[test]
4125    fn later_stamp_wins_and_stale_change_is_skipped() {
4126        let a = NativeGraph::new();
4127        let n = a.create_node(nn("n", "v1")).unwrap();
4128        let c = NativeGraph::new();
4129
4130        // Capture the v1 delta, then update the node so A holds a higher stamp.
4131        let d_v1 = a.delta_since(&c.version_vector());
4132        a.update_node(
4133            n.id,
4134            NodePatch {
4135                title: Some("v2".into()),
4136                ..Default::default()
4137            },
4138        )
4139        .unwrap();
4140        let d_v2 = a.delta_since(&c.version_vector());
4141
4142        // The newer write wins on C (found by uuid — C remaps the id).
4143        assert_eq!(c.apply_delta(&d_v2).unwrap().applied, 1);
4144        let cn = c.node_id_of_uuid(n.uuid).expect("n on c");
4145        assert_eq!(c.get_node(cn).unwrap().unwrap().title, "v2");
4146
4147        // Replaying the stale v1 delta loses on stamp order — no regression.
4148        let stats = c.apply_delta(&d_v1).unwrap();
4149        assert_eq!(stats.applied, 0);
4150        assert_eq!(stats.skipped, 1);
4151        assert_eq!(c.get_node(cn).unwrap().unwrap().title, "v2");
4152    }
4153
4154    #[test]
4155    fn delete_converges_via_tombstone() {
4156        // A and C converge on a node, then A deletes it; the delta carries the
4157        // tombstone and C removes its copy.
4158        let a = NativeGraph::new();
4159        let n = a.create_node(nn("n", "gone")).unwrap();
4160        let c = NativeGraph::new();
4161        c.apply_delta(&a.delta_since(&c.version_vector())).unwrap();
4162        let cn = c.node_id_of_uuid(n.uuid).expect("C has the node first");
4163
4164        a.delete_node(n.id).unwrap();
4165        let delta = a.delta_since(&c.version_vector());
4166        assert_eq!(delta.len(), 1, "just the tombstone");
4167        let stats = c.apply_delta(&delta).unwrap();
4168        assert_eq!(stats.applied, 1);
4169
4170        assert!(c.get_node(cn).unwrap().is_none(), "C removed the node");
4171        assert!(c.node_id_of_uuid(n.uuid).is_none(), "no live node by uuid");
4172        // Both replicas agree, and the delete is idempotent.
4173        assert_eq!(a.version_vector(), c.version_vector());
4174        assert_eq!(c.apply_delta(&delta).unwrap().applied, 0);
4175    }
4176
4177    #[test]
4178    fn delete_cascades_to_incident_edges_on_the_receiver() {
4179        let a = NativeGraph::new();
4180        let x = a.create_node(nn("n", "x")).unwrap();
4181        let y = a.create_node(nn("n", "y")).unwrap();
4182        let e = a.create_edge(stamp_edge(x.id, y.id)).unwrap();
4183        let c = NativeGraph::new();
4184        c.apply_delta(&a.delta_since(&c.version_vector())).unwrap();
4185        assert!(c.edge_id_of_uuid(e.uuid).is_some());
4186
4187        // Deleting the endpoint on A drops its incident edge; the delta ships the
4188        // node tombstone (the edge delete rides A's own cascade) and applying it
4189        // on C — nodes-then-edges, node-delete last — removes both.
4190        a.delete_node(x.id).unwrap();
4191        c.apply_delta(&a.delta_since(&c.version_vector())).unwrap();
4192        assert!(c.node_id_of_uuid(x.uuid).is_none());
4193        assert!(
4194            c.edge_id_of_uuid(e.uuid).is_none(),
4195            "edge cascaded away on C"
4196        );
4197        // The surviving endpoint y is untouched.
4198        assert!(c.node_id_of_uuid(y.uuid).is_some(), "y survives");
4199        assert_eq!(a.version_vector(), c.version_vector());
4200    }
4201
4202    #[test]
4203    fn newer_upsert_resurrects_a_tombstoned_entity() {
4204        // An upsert of a tombstoned id at a strictly-later stamp wins over the
4205        // tombstone and brings the record back — LWW on one shared timeline.
4206        let a = NativeGraph::new();
4207        let n = a.create_node(nn("n", "v1")).unwrap();
4208        a.delete_node(n.id).unwrap();
4209        assert!(a.get_node(n.id).unwrap().is_none(), "tombstoned first");
4210
4211        // A fresh stamp is later than the delete's (the HLC only advances).
4212        let later = a.next_stamp();
4213        let resurrect = Delta {
4214            changes: vec![StampedChange::Node(n.clone(), later)],
4215        };
4216        assert_eq!(a.apply_delta(&resurrect).unwrap().applied, 1);
4217        assert_eq!(a.get_node(n.id).unwrap().expect("resurrected").title, "v1");
4218
4219        // It is genuinely live again: a fresh peer receives it as an upsert, and
4220        // the tombstone no longer shadows it.
4221        let peer = NativeGraph::new();
4222        let d = a.delta_since(&peer.version_vector());
4223        assert_eq!(d.len(), 1);
4224        assert!(matches!(d.changes[0], StampedChange::Node(..)));
4225    }
4226
4227    #[test]
4228    fn stale_delete_loses_to_a_newer_live_write() {
4229        // A tombstone whose stamp is dominated by the local live stamp must not
4230        // remove the record. Capture the create-era stamp, let a later update
4231        // raise the live stamp, then replay a delete carrying the *old* stamp:
4232        // built on one origin so the two stamps are totally ordered (no flaky
4233        // cross-origin tie).
4234        let a = NativeGraph::new();
4235        let n = a.create_node(nn("n", "v1")).unwrap();
4236        let s1 = a.stamp_of(StampTarget::Node(n.id)).expect("v1 stamped");
4237        a.update_node(
4238            n.id,
4239            NodePatch {
4240                title: Some("v2".into()),
4241                ..Default::default()
4242            },
4243        )
4244        .unwrap();
4245        let s2 = a.stamp_of(StampTarget::Node(n.id)).unwrap();
4246        assert!(s2 > s1, "update raised the live stamp");
4247
4248        // A delete carrying the stale s1 loses to the live s2 — skipped, v2 kept.
4249        let stale_delete = Delta {
4250            changes: vec![StampedChange::DeleteNode(n.uuid, s1)],
4251        };
4252        let stats = a.apply_delta(&stale_delete).unwrap();
4253        assert_eq!(stats.applied, 0);
4254        assert_eq!(stats.skipped, 1);
4255        assert_eq!(a.get_node(n.id).unwrap().unwrap().title, "v2");
4256    }
4257
4258    #[test]
4259    fn concurrent_writers_converge_without_id_collision() {
4260        // A and B each mint local id 1 for *different* entities. A merge by id
4261        // would clobber; a merge by uuid keeps both.
4262        let a = NativeGraph::new();
4263        let na = a.create_node(nn("n", "from_a")).unwrap();
4264        let b = NativeGraph::new();
4265        let nb = b.create_node(nn("n", "from_b")).unwrap();
4266        assert_eq!(na.id, nb.id, "both replicas minted the same local id");
4267
4268        // Exchange deltas in both directions.
4269        let a_to_b = a.delta_since(&b.version_vector());
4270        let b_to_a = b.delta_since(&a.version_vector());
4271        assert_eq!(b.apply_delta(&a_to_b).unwrap().applied, 1);
4272        assert_eq!(a.apply_delta(&b_to_a).unwrap().applied, 1);
4273
4274        // Both hold both nodes; on each replica the incoming node got a fresh id
4275        // rather than overwriting the local one.
4276        for g in [&a, &b] {
4277            let ida = g.node_id_of_uuid(na.uuid).expect("has A's node");
4278            let idb = g.node_id_of_uuid(nb.uuid).expect("has B's node");
4279            assert_ne!(ida, idb, "distinct local ids for distinct uuids");
4280            assert_eq!(g.get_node(ida).unwrap().unwrap().title, "from_a");
4281            assert_eq!(g.get_node(idb).unwrap().unwrap().title, "from_b");
4282        }
4283        // Fully converged: identical version vectors.
4284        assert_eq!(a.version_vector(), b.version_vector());
4285    }
4286
4287    #[test]
4288    fn edge_endpoints_are_remapped_by_uuid_across_id_spaces() {
4289        // A builds x-[e]->y. B holds a filler node occupying id 1, so A's ids do
4290        // not line up with B's. Merging must wire the edge to the *remapped*
4291        // endpoints, never to B's coincidentally-numbered filler.
4292        let a = NativeGraph::new();
4293        let x = a.create_node(nn("n", "x")).unwrap();
4294        let y = a.create_node(nn("n", "y")).unwrap();
4295        let e = a.create_edge(stamp_edge(x.id, y.id)).unwrap();
4296
4297        let b = NativeGraph::new();
4298        let filler = b.create_node(nn("n", "filler")).unwrap();
4299        assert_eq!(filler.id, x.id, "filler squats on A's x id");
4300
4301        assert_eq!(
4302            b.apply_delta(&a.delta_since(&b.version_vector()))
4303                .unwrap()
4304                .applied,
4305            3
4306        );
4307        let bx = b.node_id_of_uuid(x.uuid).unwrap();
4308        let by = b.node_id_of_uuid(y.uuid).unwrap();
4309        let bf = b.node_id_of_uuid(filler.uuid).unwrap();
4310        let be_rec = b
4311            .get_edge(b.edge_id_of_uuid(e.uuid).unwrap())
4312            .unwrap()
4313            .unwrap();
4314        assert_eq!(be_rec.from_id, bx);
4315        assert_eq!(be_rec.to_id, by);
4316        assert_ne!(be_rec.from_id, bf, "edge must not point at the filler");
4317    }
4318
4319    #[test]
4320    fn delete_converges_across_distinct_id_spaces() {
4321        // The deleted node lives under different local ids on the two replicas;
4322        // the tombstone is keyed by uuid, so it removes the right node on B.
4323        let a = NativeGraph::new();
4324        let n = a.create_node(nn("n", "doomed")).unwrap();
4325        let b = NativeGraph::new();
4326        let filler = b.create_node(nn("n", "filler")).unwrap();
4327        b.apply_delta(&a.delta_since(&b.version_vector())).unwrap();
4328        let bn = b.node_id_of_uuid(n.uuid).unwrap();
4329        assert_ne!(bn, filler.id, "n has a different id on B than on A");
4330
4331        a.delete_node(n.id).unwrap();
4332        let del = a.delta_since(&b.version_vector());
4333        assert_eq!(del.len(), 1);
4334        assert_eq!(b.apply_delta(&del).unwrap().applied, 1);
4335
4336        assert!(b.node_id_of_uuid(n.uuid).is_none(), "n removed on B");
4337        assert!(
4338            b.node_id_of_uuid(filler.uuid).is_some(),
4339            "filler untouched by the remapped delete"
4340        );
4341    }
4342
4343    #[test]
4344    fn csr_out_matches_neighbor_ids_oracle() {
4345        // Build a small multi-kind graph with a fan-out, a back-edge and an
4346        // isolated node, then check the CSR out-adjacency against the existing
4347        // neighbor_ids() on every vertex (the oracle).
4348        let g = NativeGraph::new();
4349        let a = g.create_node(nn("n", "a")).unwrap();
4350        let b = g.create_node(nn("n", "b")).unwrap();
4351        let c = g.create_node(nn("n", "c")).unwrap();
4352        let _iso = g.create_node(nn("n", "iso")).unwrap();
4353        g.create_edge(stamp_edge(a.id, b.id)).unwrap();
4354        g.create_edge(stamp_edge(a.id, c.id)).unwrap();
4355        g.create_edge(stamp_edge(b.id, c.id)).unwrap();
4356        g.create_edge(stamp_edge(c.id, a.id)).unwrap();
4357        // A parallel edge a->b must collapse to one distinct neighbour.
4358        g.create_edge(stamp_edge(a.id, b.id)).unwrap();
4359
4360        let snap = g.snapshot();
4361        let csr = snap.csr_out();
4362        assert_eq!(csr.vertex_count(), 4);
4363
4364        for i in 0..csr.vertex_count() {
4365            let node_id = csr.node_id(i).unwrap();
4366            // Map the CSR dense neighbour indices back to node ids.
4367            let mut got: Vec<u64> = csr
4368                .neighbors_of(i)
4369                .iter()
4370                .map(|&j| csr.node_id(j as usize).unwrap())
4371                .collect();
4372            got.sort_unstable();
4373            let mut want = snap.neighbor_ids(node_id, Direction::Outgoing, None);
4374            want.sort_unstable();
4375            assert_eq!(
4376                got, want,
4377                "csr neighbours of node {node_id} match the oracle"
4378            );
4379        }
4380        // 3 distinct fan-out edges (a->b once, a->c, b->c, c->a) = 4 total.
4381        assert_eq!(csr.edge_count(), 4);
4382        assert_eq!(csr.out_degree(csr.index_of(a.id).unwrap()), 2);
4383    }
4384
4385    #[test]
4386    fn csr_in_matches_incoming_neighbor_ids_oracle() {
4387        // Same graph as the out-adjacency oracle; check csr_in's predecessors
4388        // against neighbor_ids(.., Incoming, None) on every vertex.
4389        let g = NativeGraph::new();
4390        let a = g.create_node(nn("n", "a")).unwrap();
4391        let b = g.create_node(nn("n", "b")).unwrap();
4392        let c = g.create_node(nn("n", "c")).unwrap();
4393        let _iso = g.create_node(nn("n", "iso")).unwrap();
4394        g.create_edge(stamp_edge(a.id, b.id)).unwrap();
4395        g.create_edge(stamp_edge(a.id, c.id)).unwrap();
4396        g.create_edge(stamp_edge(b.id, c.id)).unwrap();
4397        g.create_edge(stamp_edge(c.id, a.id)).unwrap();
4398        g.create_edge(stamp_edge(a.id, b.id)).unwrap(); // parallel a->b collapses
4399
4400        let snap = g.snapshot();
4401        let csr = snap.csr_in();
4402        assert_eq!(csr.vertex_count(), 4);
4403        for i in 0..csr.vertex_count() {
4404            let node_id = csr.node_id(i).unwrap();
4405            let mut got: Vec<u64> = csr
4406                .neighbors_of(i)
4407                .iter()
4408                .map(|&j| csr.node_id(j as usize).unwrap())
4409                .collect();
4410            got.sort_unstable();
4411            let mut want = snap.neighbor_ids(node_id, Direction::Incoming, None);
4412            want.sort_unstable();
4413            assert_eq!(
4414                got, want,
4415                "csr_in predecessors of node {node_id} match oracle"
4416            );
4417        }
4418        // c has two predecessors (a, b); a has one (c); b has one (a); iso none.
4419        assert_eq!(csr.out_degree(csr.index_of(c.id).unwrap()), 2);
4420        assert_eq!(csr.edge_count(), 4);
4421    }
4422
4423    #[test]
4424    fn edge_with_unknown_endpoints_is_skipped() {
4425        // An edge whose endpoint uuids the receiver has never seen cannot be
4426        // placed, so apply skips it rather than dropping it onto wrong ids.
4427        let c = NativeGraph::new();
4428        let stamp = NativeGraph::new().next_stamp();
4429        let se = StampedEdge {
4430            edge: Edge {
4431                id: 1,
4432                uuid: [7u8; 16],
4433                from_id: 1,
4434                to_id: 2,
4435                kind: "links".into(),
4436                weight: 1.0,
4437                created_at: 0,
4438                properties: Default::default(),
4439            },
4440            from_uuid: [1u8; 16],
4441            to_uuid: [2u8; 16],
4442            stamp,
4443        };
4444        let d = Delta {
4445            changes: vec![StampedChange::Edge(se)],
4446        };
4447        let stats = c.apply_delta(&d).unwrap();
4448        assert_eq!(stats.applied, 0);
4449        assert_eq!(stats.skipped, 1);
4450        assert!(c.edge_id_of_uuid([7u8; 16]).is_none());
4451    }
4452}