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}