Skip to main content

memfork_core/
db.rs

1//! The engine: branches, commits and the operations over them (DESIGN §4.2, §4.3).
2
3use std::collections::{BTreeMap, BTreeSet, VecDeque};
4use std::sync::Arc;
5
6use parking_lot::{Mutex, RwLock};
7use smallvec::SmallVec;
8
9use crate::access::AccessLog;
10use crate::commit::{Commit, LogEntry};
11use crate::entry::{Entry, Op, Value};
12use crate::error::{Error, Result};
13use crate::evict::{self, EvictionConfig, OnEvict};
14use crate::id::CommitId;
15use crate::journal::{Journal, Record};
16use crate::search::SearchHit;
17use crate::store::{Root, Store};
18use crate::txn::Txn;
19use crate::view::{BranchInfo, Change, ChangeKind, ReadView};
20
21/// The default branch name.
22pub const DEFAULT_BRANCH: &str = "main";
23
24/// How many times an auto-commit retries after losing an optimistic race.
25///
26/// Auto-commits serialize on the branch's writer lock, so the only thing that
27/// can move the head underneath one is an explicit transaction. The bound is
28/// generous because losing this race means another writer made progress.
29const AUTO_COMMIT_RETRIES: usize = 1024;
30
31/// A branch: a mutable pointer into the immutable commit graph.
32///
33/// Each branch carries its own locks, so writers on different branches never
34/// wait on each other (DESIGN §4.3).
35#[derive(Debug)]
36pub(crate) struct BranchHandle {
37    /// The head pointer. Held only for the instant of a compare-and-swap, so a
38    /// reader never waits behind a writer that is still building a commit.
39    pub(crate) head: Mutex<CommitId>,
40    /// Serializes the engine's own read-modify-write operations — auto-commits
41    /// and merges — on this branch.
42    ///
43    /// DESIGN §4.3 puts one writer on a branch, and an explicit [`Txn`] stays
44    /// purely optimistic as the spec describes. But a caller that ignores that
45    /// and writes from several threads at once should get correct behaviour
46    /// rather than a retry budget that can run out, so the operations the
47    /// engine drives end to end take a turn here instead of spinning.
48    pub(crate) writer: Mutex<()>,
49}
50
51pub(crate) struct DbInner {
52    /// Every commit currently reachable from some branch.
53    pub(crate) commits: RwLock<BTreeMap<CommitId, Arc<Commit>>>,
54    /// Branch name to head pointer. Only creating and discarding branches
55    /// takes the write lock.
56    pub(crate) branches: RwLock<BTreeMap<String, Arc<BranchHandle>>>,
57    /// The embedding dimension, pinned on the first insert that carries one.
58    pub(crate) dim: RwLock<Option<usize>>,
59    pub(crate) default_branch: String,
60    /// Where changes are recorded before they become visible, if anywhere.
61    pub(crate) journal: RwLock<Option<Arc<dyn Journal>>>,
62    /// The memory budget, if one is set. `None` means never evict, which is
63    /// also what keeps reads free of any bookkeeping.
64    pub(crate) eviction: RwLock<Option<EvictionConfig>>,
65    /// Where evicted entries go first.
66    pub(crate) on_evict: RwLock<Option<OnEvict>>,
67    /// Reading history, outside the commit chain (DESIGN §4.4).
68    pub(crate) access: AccessLog,
69}
70
71impl core::fmt::Debug for DbInner {
72    /// Hand-written because the eviction hook is a closure, which cannot
73    /// derive `Debug`. Reports what it is rather than dumping the graph.
74    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
75        f.debug_struct("DbInner")
76            .field("default_branch", &self.default_branch)
77            .field("branches", &self.branches.read().len())
78            .field("commits", &self.commits.read().len())
79            .field("embedding_dim", &*self.dim.read())
80            .field("journalled", &self.journal.read().is_some())
81            .field("eviction", &*self.eviction.read())
82            .field("on_evict", &self.on_evict.read().is_some())
83            .finish()
84    }
85}
86
87/// An embedded, in-memory database with Git semantics.
88///
89/// `Db` is a handle: cloning it is cheap and every clone refers to the same
90/// database. It is `Send + Sync`, and readers never block writers.
91///
92/// ```
93/// use memfork_core::{Db, MergePolicy, Value};
94///
95/// let db = Db::new();
96/// db.put("main", "plan:1", Value::new("draft"))?;
97///
98/// // Fork before a risky step; the parent cannot see the attempt.
99/// db.fork("main", "try")?;
100/// db.put("try", "plan:1", Value::new("rewritten"))?;
101/// assert_eq!(db.get("main", "plan:1")?.map(|e| e.value.clone()), Some("draft".into()));
102///
103/// // It worked: fold it back in.
104/// db.merge("try", "main", MergePolicy::Fail)?;
105/// assert_eq!(db.get("main", "plan:1")?.map(|e| e.value.clone()), Some("rewritten".into()));
106/// # Ok::<(), memfork_core::Error>(())
107/// ```
108#[derive(Debug, Clone)]
109pub struct Db {
110    pub(crate) inner: Arc<DbInner>,
111}
112
113/// Everything needed to build a commit, gathered so that the transaction and
114/// the merge paths hand the engine one value rather than a row of positional
115/// arguments.
116#[derive(Debug)]
117pub(crate) struct CommitDraft {
118    pub(crate) parents: SmallVec<[CommitId; 2]>,
119    pub(crate) root: Root,
120    pub(crate) seq: u64,
121    pub(crate) message: Option<String>,
122    pub(crate) ops: Vec<Op>,
123}
124
125impl Default for Db {
126    fn default() -> Self {
127        Self::new()
128    }
129}
130
131impl Db {
132    /// Create a database with a single empty branch, `main`.
133    pub fn new() -> Self {
134        Self::build(DEFAULT_BRANCH)
135    }
136
137    /// Create a database whose default branch has a name other than `main`.
138    pub fn with_default_branch(name: &str) -> Result<Self> {
139        validate_branch_name(name)?;
140        Ok(Self::build(name))
141    }
142
143    fn build(name: &str) -> Self {
144        let genesis = Arc::new(Commit::genesis());
145        let mut commits = BTreeMap::new();
146        commits.insert(genesis.id, Arc::clone(&genesis));
147        let mut branches = BTreeMap::new();
148        branches.insert(
149            name.to_owned(),
150            Arc::new(BranchHandle {
151                head: Mutex::new(genesis.id),
152                writer: Mutex::new(()),
153            }),
154        );
155        Db {
156            inner: Arc::new(DbInner {
157                commits: RwLock::new(commits),
158                branches: RwLock::new(branches),
159                dim: RwLock::new(None),
160                default_branch: name.to_owned(),
161                journal: RwLock::new(None),
162                eviction: RwLock::new(None),
163                on_evict: RwLock::new(None),
164                access: AccessLog::new(),
165            }),
166        }
167    }
168
169    /// The name of the branch that cannot be discarded.
170    pub fn default_branch(&self) -> &str {
171        &self.inner.default_branch
172    }
173
174    // ---- durability (DESIGN §4.5) --------------------------------------------
175
176    /// Record every change to a journal before it becomes visible.
177    ///
178    /// The engine does no I/O of its own: the journal decides where the bytes
179    /// go and how durable they are. Attached after recovery rather than at
180    /// construction, because replay must not re-record what it is replaying.
181    ///
182    /// A library caller gets no journal unless they ask. The `memfork` binary
183    /// attaches one by default, because an agent's memory that forgets
184    /// everything on restart is not what anyone means by memory.
185    pub fn set_journal(&self, journal: Option<Arc<dyn Journal>>) {
186        *self.inner.journal.write() = journal;
187    }
188
189    /// Whether changes are being recorded.
190    pub fn is_journalled(&self) -> bool {
191        self.inner.journal.read().is_some()
192    }
193
194    fn record(&self, record: &Record) -> Result<()> {
195        match self.inner.journal.read().as_ref() {
196            None => Ok(()),
197            Some(journal) => journal.append(record).map_err(|e| Error::Journal(e.0)),
198        }
199    }
200
201    // ---- eviction (DESIGN §4.4) ----------------------------------------------
202
203    /// Set a memory budget, or remove one.
204    ///
205    /// With no budget nothing is ever evicted and reads record nothing, so
206    /// they stay lock-free. Setting one turns on the reading history that
207    /// scoring needs, which costs a brief per-branch lock per read.
208    pub fn set_eviction(&self, config: Option<EvictionConfig>) {
209        *self.inner.eviction.write() = config;
210    }
211
212    /// The memory budget, if one is set.
213    pub fn eviction(&self) -> Option<EvictionConfig> {
214        *self.inner.eviction.read()
215    }
216
217    /// Be told about entries before they are evicted, so they can be kept
218    /// somewhere else.
219    pub fn on_evict(&self, hook: Option<OnEvict>) {
220        *self.inner.on_evict.write() = hook;
221    }
222
223    /// Note that keys were read, if anything is scoring reads.
224    pub(crate) fn note_read(&self, branch: &str, seq: u64, keys: impl Iterator<Item = String>) {
225        if self.inner.eviction.read().is_some() {
226            self.inner.access.record(branch, seq, keys);
227        }
228    }
229
230    /// Evict from a branch until it is under budget, as its own commit.
231    ///
232    /// Called after a commit lands. Does nothing without a budget, and nothing
233    /// when the branch is already under it, so the common path costs one
234    /// lock-free read of the configuration.
235    pub fn enforce_budget(&self, branch: &str) -> Result<Option<CommitId>> {
236        let Some(config) = *self.inner.eviction.read() else {
237            return Ok(None);
238        };
239        // Retry for the same reason a transaction does: another writer may
240        // land a commit between choosing and committing.
241        for _ in 0..AUTO_COMMIT_RETRIES {
242            let head_id = self.head(branch)?;
243            let head = self.commit(head_id)?;
244            let access = self.inner.access.snapshot(branch);
245            let chosen = evict::choose(head.root.iter(), head.seq, &access, &config);
246            if chosen.is_empty() {
247                return Ok(None);
248            }
249
250            // The hook sees them before they go, so it can keep what matters.
251            if let Some(hook) = self.inner.on_evict.read().as_ref() {
252                hook(&chosen);
253            }
254
255            let ops: Vec<Op> = chosen
256                .iter()
257                .map(|e| Op::Evict { key: e.key.clone() })
258                .collect();
259            let seq = head.seq + 1;
260            let mut root = head.root.clone();
261            crate::txn::apply_ops(&mut root, &ops, seq);
262
263            let message = Some(format!("evict {} entr(ies) over budget", ops.len()));
264            match self.commit_onto(
265                branch,
266                head_id,
267                CommitDraft {
268                    parents: smallvec::smallvec![head_id],
269                    root,
270                    seq,
271                    message,
272                    ops,
273                },
274            ) {
275                Ok(id) => {
276                    let gone: BTreeSet<String> = chosen.into_iter().map(|e| e.key).collect();
277                    self.inner.access.retain(branch, |k| !gone.contains(k));
278                    return Ok(Some(id));
279                }
280                Err(Error::Conflict { .. }) => continue,
281                Err(e) => return Err(e),
282            }
283        }
284        Ok(None)
285    }
286
287    /// The embedding dimension this database is pinned to, if any entry has
288    /// carried an embedding yet (DESIGN §4.1).
289    pub fn embedding_dim(&self) -> Option<usize> {
290        *self.inner.dim.read()
291    }
292
293    // ---- branch and commit lookup ------------------------------------------
294
295    pub(crate) fn branch_handle(&self, branch: &str) -> Result<Arc<BranchHandle>> {
296        self.inner
297            .branches
298            .read()
299            .get(branch)
300            .map(Arc::clone)
301            .ok_or_else(|| Error::NoSuchBranch(branch.to_owned()))
302    }
303
304    /// The commit a branch currently points at.
305    pub fn head(&self, branch: &str) -> Result<CommitId> {
306        Ok(*self.branch_handle(branch)?.head.lock())
307    }
308
309    /// Look up a commit by id.
310    pub fn commit(&self, id: CommitId) -> Result<Arc<Commit>> {
311        self.inner
312            .commits
313            .read()
314            .get(&id)
315            .map(Arc::clone)
316            .ok_or(Error::NoSuchCommit(id))
317    }
318
319    /// Whether a branch exists.
320    pub fn has_branch(&self, branch: &str) -> bool {
321        self.inner.branches.read().contains_key(branch)
322    }
323
324    /// Every branch, in ascending name order.
325    pub fn branches(&self) -> Vec<BranchInfo> {
326        let names: Vec<(String, Arc<BranchHandle>)> = self
327            .inner
328            .branches
329            .read()
330            .iter()
331            .map(|(k, v)| (k.clone(), Arc::clone(v)))
332            .collect();
333        let commits = self.inner.commits.read();
334        names
335            .into_iter()
336            .filter_map(|(name, handle)| {
337                let head = *handle.head.lock();
338                let commit = commits.get(&head)?;
339                Some(BranchInfo {
340                    is_default: name == self.inner.default_branch,
341                    name,
342                    head,
343                    seq: commit.seq,
344                    key_count: commit.root.len(),
345                })
346            })
347            .collect()
348    }
349
350    /// A consistent view of a branch as it is right now (DESIGN §4.3).
351    pub fn read(&self, branch: &str) -> Result<ReadView> {
352        let head = self.head(branch)?;
353        Ok(ReadView::new(self.commit(head)?))
354    }
355
356    /// A view of a branch as it was after commit number `seq` (DESIGN §4.2).
357    ///
358    /// Sequence numbers are monotonic along a branch's first-parent chain, so
359    /// `seq` names exactly one commit: 0 is the empty genesis state and
360    /// `head.seq` is the present.
361    pub fn at(&self, branch: &str, seq: u64) -> Result<ReadView> {
362        let head = self.commit(self.head(branch)?)?;
363        if seq > head.seq {
364            return Err(Error::NoSuchSeq {
365                branch: branch.to_owned(),
366                seq,
367                head_seq: head.seq,
368            });
369        }
370        let mut cur = head;
371        while cur.seq > seq {
372            let parent = cur.first_parent().ok_or_else(|| Error::NoSuchSeq {
373                branch: branch.to_owned(),
374                seq,
375                head_seq: cur.seq,
376            })?;
377            cur = self.commit(parent)?;
378        }
379        Ok(ReadView::new(cur))
380    }
381
382    // ---- reads -------------------------------------------------------------
383
384    /// Read one key from a branch head.
385    pub fn get(&self, branch: &str, key: &str) -> Result<Option<Arc<Entry>>> {
386        let view = self.read(branch)?;
387        let found = view.get(key);
388        if found.is_some() {
389            self.note_read(branch, view.seq(), std::iter::once(key.to_owned()));
390        }
391        Ok(found)
392    }
393
394    /// List the keys of a branch that start with `prefix`, in ascending order.
395    pub fn list(
396        &self,
397        branch: &str,
398        prefix: &str,
399        limit: Option<usize>,
400    ) -> Result<Vec<(String, Arc<Entry>)>> {
401        let view = self.read(branch)?;
402        let found = view.list(prefix, limit);
403        self.note_read(branch, view.seq(), found.iter().map(|(k, _)| k.clone()));
404        Ok(found)
405    }
406
407    /// Exact brute-force cosine similarity search (DESIGN §4.2).
408    pub fn search(
409        &self,
410        branch: &str,
411        query: &[f32],
412        k: usize,
413        prefix: Option<&str>,
414    ) -> Result<Vec<SearchHit>> {
415        if let Some(expected) = self.embedding_dim() {
416            if !query.is_empty() && query.len() != expected {
417                return Err(Error::BadQueryDimension {
418                    expected,
419                    got: query.len(),
420                });
421            }
422        }
423        let view = self.read(branch)?;
424        let hits = crate::search::search(&view, query, k, prefix);
425        self.note_read(branch, view.seq(), hits.iter().map(|h| h.key.clone()));
426        Ok(hits)
427    }
428
429    /// The first-parent history of a branch, newest first.
430    pub fn log(&self, branch: &str, limit: Option<usize>) -> Result<Vec<LogEntry>> {
431        let mut out = Vec::new();
432        let mut cur = Some(self.head(branch)?);
433        while let Some(id) = cur {
434            if limit.is_some_and(|n| out.len() >= n) {
435                break;
436            }
437            let commit = self.commit(id)?;
438            out.push(LogEntry {
439                id: commit.id,
440                seq: commit.seq,
441                parents: commit.parents.to_vec(),
442                message: commit.message.clone(),
443                op_count: commit.ops.len(),
444                key_count: commit.root.len(),
445            });
446            cur = commit.first_parent();
447        }
448        Ok(out)
449    }
450
451    /// Resolve a branch name or a full hex commit id to a commit.
452    pub fn resolve(&self, reference: &str) -> Result<Arc<Commit>> {
453        if self.has_branch(reference) {
454            return self.commit(self.head(reference)?);
455        }
456        match CommitId::from_hex(reference) {
457            Ok(id) => self.commit(id),
458            Err(_) => Err(Error::NoSuchBranch(reference.to_owned())),
459        }
460    }
461
462    /// Key-level differences between two branches or commits, sorted by key.
463    pub fn diff(&self, a: &str, b: &str) -> Result<Vec<Change>> {
464        let ca = self.resolve(a)?;
465        let cb = self.resolve(b)?;
466        Ok(diff_roots(&ca.root, &cb.root))
467    }
468
469    // ---- writes ------------------------------------------------------------
470
471    /// Open a transaction on a branch (DESIGN §4.2).
472    ///
473    /// The transaction records the branch head it was based on. Dropping it
474    /// without committing is a rollback that leaves no trace.
475    pub fn begin(&self, branch: &str) -> Result<Txn> {
476        Txn::open(self.clone(), branch)
477    }
478
479    /// Write one key as a single-operation transaction.
480    pub fn put(&self, branch: &str, key: &str, value: Value) -> Result<CommitId> {
481        let id = self.auto_commit(branch, &format!("put {key}"), |txn| {
482            txn.put(key, value.clone())
483        })?;
484        self.enforce_budget(branch)?;
485        Ok(id)
486    }
487
488    /// Remove one key as a single-operation transaction.
489    pub fn delete(&self, branch: &str, key: &str) -> Result<CommitId> {
490        self.auto_commit(branch, &format!("delete {key}"), |txn| txn.delete(key))
491    }
492
493    /// Rebuild state from journal records, in the order they were written.
494    ///
495    /// Commit ids are recomputed, never read from the record, so a replay that
496    /// produces the original ids is evidence the engine is deterministic
497    /// rather than evidence that bytes were copied faithfully.
498    pub fn apply_record(&self, record: &Record) -> Result<()> {
499        match record {
500            Record::BranchCreated { name, at } => {
501                if self.has_branch(name) {
502                    // Replaying onto a database that already has the branch is
503                    // not an error: the default branch always exists.
504                    return Ok(());
505                }
506                let _ = self.commit(*at)?;
507                self.create_branch_unrecorded(name, *at)?;
508                Ok(())
509            }
510            Record::BranchDiscarded { name } => {
511                if !self.has_branch(name) {
512                    return Ok(());
513                }
514                self.discard(name)
515            }
516            Record::HeadMoved { branch, to } => {
517                let _ = self.commit(*to)?;
518                let handle = self.branch_handle(branch)?;
519                *handle.head.lock() = *to;
520                Ok(())
521            }
522            Record::Commit {
523                branch,
524                parents,
525                seq,
526                message,
527                ops,
528            } => {
529                let base = parents
530                    .first()
531                    .copied()
532                    .ok_or_else(|| Error::Journal("a commit record has no parent".to_owned()))?;
533                let base_commit = self.commit(base)?;
534                let mut root = base_commit.root.clone();
535                crate::txn::apply_ops(&mut root, ops, *seq);
536
537                let id = Commit::compute_id(parents, message.as_deref(), ops);
538                let commit = Arc::new(Commit {
539                    id,
540                    parents: parents.clone(),
541                    root,
542                    seq: *seq,
543                    message: message.clone(),
544                    ops: ops.clone(),
545                });
546                self.inner.commits.write().entry(id).or_insert(commit);
547                if !self.has_branch(branch) {
548                    self.create_branch_unrecorded(branch, id)?;
549                } else {
550                    let handle = self.branch_handle(branch)?;
551                    *handle.head.lock() = id;
552                }
553                Ok(())
554            }
555        }
556    }
557
558    /// Run a closure in a transaction, retrying if another writer wins the race.
559    ///
560    /// Takes the branch's writer lock, so concurrent auto-commits take turns
561    /// rather than racing each other; the retry loop is then only for a
562    /// concurrent explicit transaction.
563    fn auto_commit<F>(&self, branch: &str, message: &str, mut f: F) -> Result<CommitId>
564    where
565        F: FnMut(&mut Txn) -> Result<()>,
566    {
567        let handle = self.branch_handle(branch)?;
568        let _writing = handle.writer.lock();
569        let mut last = None;
570        for _ in 0..AUTO_COMMIT_RETRIES {
571            let mut txn = self.begin(branch)?;
572            f(&mut txn)?;
573            match txn.commit(Some(message.to_owned())) {
574                Ok(id) => return Ok(id),
575                Err(e @ Error::Conflict { .. }) => {
576                    last = Some(e);
577                    // The winner is mid-commit; give it the core rather than
578                    // burning the retry budget against it.
579                    std::thread::yield_now();
580                }
581                Err(e) => return Err(e),
582            }
583        }
584        Err(last.unwrap_or_else(|| Error::NoSuchBranch(branch.to_owned())))
585    }
586
587    // ---- branching ---------------------------------------------------------
588
589    /// Point a new branch at another branch's head (DESIGN §4.2).
590    ///
591    /// Constant time and constant space whatever the database holds: the new
592    /// branch is one pointer into the same immutable commit, and the two
593    /// branches go on sharing every node until one of them is written to.
594    pub fn fork(&self, from: &str, new_branch: &str) -> Result<CommitId> {
595        let head = self.head(from)?;
596        self.create_branch(new_branch, head)?;
597        // The new branch starts from what its parent had read (DESIGN §4.4):
598        // the entries the parent valued are the ones the fork inherits.
599        self.inner.access.fork(from, new_branch);
600        Ok(head)
601    }
602
603    /// Point a new branch at a past commit of another branch (DESIGN §4.2).
604    pub fn fork_at(&self, from: &str, seq: u64, new_branch: &str) -> Result<CommitId> {
605        let head = self.at(from, seq)?.commit_id();
606        self.create_branch(new_branch, head)?;
607        Ok(head)
608    }
609
610    /// Point a new branch at an arbitrary commit.
611    pub fn branch_from_commit(&self, new_branch: &str, at: CommitId) -> Result<CommitId> {
612        // Fail before mutating anything if the commit is unknown.
613        let _ = self.commit(at)?;
614        self.create_branch(new_branch, at)?;
615        Ok(at)
616    }
617
618    pub(crate) fn create_branch(&self, name: &str, head: CommitId) -> Result<()> {
619        validate_branch_name(name)?;
620        if self.has_branch(name) {
621            return Err(Error::BranchExists(name.to_owned()));
622        }
623        self.record(&Record::BranchCreated {
624            name: name.to_owned(),
625            at: head,
626        })?;
627        self.create_branch_unrecorded(name, head)
628    }
629
630    /// Create a branch without recording it, which is what replay needs: the
631    /// record being replayed is already on disk.
632    fn create_branch_unrecorded(&self, name: &str, head: CommitId) -> Result<()> {
633        validate_branch_name(name)?;
634        let mut branches = self.inner.branches.write();
635        if branches.contains_key(name) {
636            return Err(Error::BranchExists(name.to_owned()));
637        }
638        branches.insert(
639            name.to_owned(),
640            Arc::new(BranchHandle {
641                head: Mutex::new(head),
642                writer: Mutex::new(()),
643            }),
644        );
645        Ok(())
646    }
647
648    /// Delete a branch and free every commit only it could reach (DESIGN §4.2).
649    ///
650    /// The default branch cannot be discarded. Any [`ReadView`] already handed
651    /// out stays valid: it holds its commit alive by reference count.
652    pub fn discard(&self, branch: &str) -> Result<()> {
653        if branch == self.inner.default_branch {
654            return Err(Error::CannotDiscardDefaultBranch(branch.to_owned()));
655        }
656        let mut branches = self.inner.branches.write();
657        if !branches.contains_key(branch) {
658            return Err(Error::NoSuchBranch(branch.to_owned()));
659        }
660        self.record(&Record::BranchDiscarded {
661            name: branch.to_owned(),
662        })?;
663        branches.remove(branch);
664        self.inner.access.forget(branch);
665        let live_heads: Vec<CommitId> = branches.values().map(|h| *h.head.lock()).collect();
666        drop(branches);
667        self.collect_unreachable(&live_heads);
668        Ok(())
669    }
670
671    /// Drop every commit no surviving branch can reach.
672    fn collect_unreachable(&self, live_heads: &[CommitId]) {
673        let mut commits = self.inner.commits.write();
674        let mut reachable: BTreeSet<CommitId> = BTreeSet::new();
675        let mut queue: VecDeque<CommitId> = live_heads.iter().copied().collect();
676        while let Some(id) = queue.pop_front() {
677            if !reachable.insert(id) {
678                continue;
679            }
680            if let Some(commit) = commits.get(&id) {
681                for parent in &commit.parents {
682                    queue.push_back(*parent);
683                }
684            }
685        }
686        commits.retain(|id, _| reachable.contains(id));
687    }
688
689    /// How many commits the graph currently holds. Tests use this to show that
690    /// a rolled-back transaction and a discarded branch leave nothing behind.
691    pub fn commit_count(&self) -> usize {
692        self.inner.commits.read().len()
693    }
694
695    // ---- internals used by txn and merge -----------------------------------
696
697    /// Install a commit and move a branch head from `expected` to it, failing
698    /// if another writer moved the head first (DESIGN §4.3).
699    pub(crate) fn commit_onto(
700        &self,
701        branch: &str,
702        expected: CommitId,
703        draft: CommitDraft,
704    ) -> Result<CommitId> {
705        let CommitDraft {
706            parents,
707            root,
708            seq,
709            message,
710            ops,
711        } = draft;
712        let id = Commit::compute_id(&parents, message.as_deref(), &ops);
713        let commit = Arc::new(Commit {
714            id,
715            parents,
716            root,
717            seq,
718            message,
719            ops,
720        });
721        let handle = self.branch_handle(branch)?;
722        let mut head = handle.head.lock();
723        if *head != expected {
724            return Err(Error::Conflict {
725                branch: branch.to_owned(),
726                expected,
727                actual: *head,
728            });
729        }
730        // Write-ahead, and inside the head lock: the race is already won, so
731        // this records a commit that is certainly happening, and it happens
732        // before any reader can see it. A crash between the two replays to the
733        // same state. The cost is a flush while the branch is locked, which
734        // serializes writers on that branch — which is the model anyway.
735        self.record(&Record::Commit {
736            branch: branch.to_owned(),
737            parents: commit.parents.clone(),
738            seq: commit.seq,
739            message: commit.message.clone(),
740            ops: commit.ops.clone(),
741        })?;
742        // Take the commit-index lock only once the race is won, so a commit is
743        // never visible in the graph unless a branch actually points at it.
744        self.inner.commits.write().entry(id).or_insert(commit);
745        *head = id;
746        Ok(id)
747    }
748
749    /// Move a branch head without creating a commit, for fast-forward merges.
750    pub(crate) fn fast_forward(
751        &self,
752        branch: &str,
753        expected: CommitId,
754        to: CommitId,
755    ) -> Result<CommitId> {
756        let handle = self.branch_handle(branch)?;
757        let mut head = handle.head.lock();
758        if *head != expected {
759            return Err(Error::Conflict {
760                branch: branch.to_owned(),
761                expected,
762                actual: *head,
763            });
764        }
765        self.record(&Record::HeadMoved {
766            branch: branch.to_owned(),
767            to,
768        })?;
769        *head = to;
770        Ok(to)
771    }
772
773    /// Pin, or check, the database-wide embedding dimension (DESIGN §4.1).
774    pub(crate) fn check_dim(&self, embedding: Option<&Vec<f32>>) -> Result<()> {
775        let Some(e) = embedding else { return Ok(()) };
776        let mut dim = self.inner.dim.write();
777        match *dim {
778            None => {
779                *dim = Some(e.len());
780                Ok(())
781            }
782            Some(expected) if expected == e.len() => Ok(()),
783            Some(expected) => Err(Error::DimensionMismatch {
784                expected,
785                got: e.len(),
786            }),
787        }
788    }
789
790    /// The most recent commit that is an ancestor of both `a` and `b`.
791    ///
792    /// Breadth-first from `a`, taking parents in order, so the answer depends
793    /// only on the shape of the graph and never on iteration order.
794    pub(crate) fn common_ancestor(&self, a: CommitId, b: CommitId) -> Option<CommitId> {
795        let ancestors_of_b = self.ancestors(b);
796        let commits = self.inner.commits.read();
797        let mut seen: BTreeSet<CommitId> = BTreeSet::new();
798        let mut queue: VecDeque<CommitId> = VecDeque::new();
799        queue.push_back(a);
800        while let Some(id) = queue.pop_front() {
801            if !seen.insert(id) {
802                continue;
803            }
804            if ancestors_of_b.contains(&id) {
805                return Some(id);
806            }
807            if let Some(commit) = commits.get(&id) {
808                for parent in &commit.parents {
809                    queue.push_back(*parent);
810                }
811            }
812        }
813        None
814    }
815
816    fn ancestors(&self, id: CommitId) -> BTreeSet<CommitId> {
817        let commits = self.inner.commits.read();
818        let mut seen = BTreeSet::new();
819        let mut queue = VecDeque::from([id]);
820        while let Some(cur) = queue.pop_front() {
821            if !seen.insert(cur) {
822                continue;
823            }
824            if let Some(commit) = commits.get(&cur) {
825                for parent in &commit.parents {
826                    queue.push_back(*parent);
827                }
828            }
829        }
830        seen
831    }
832}
833
834/// Key-level difference between two roots, sorted ascending by key.
835pub(crate) fn diff_roots(a: &Root, b: &Root) -> Vec<Change> {
836    let mut out = Vec::new();
837    let mut ia = a.iter().peekable();
838    let mut ib = b.iter().peekable();
839    // Both sides iterate in ascending key order, so one merge pass is enough.
840    loop {
841        match (ia.peek(), ib.peek()) {
842            (None, None) => break,
843            (Some((ka, _)), None) => {
844                out.push(Change {
845                    key: (*ka).clone(),
846                    kind: ChangeKind::Removed,
847                });
848                ia.next();
849            }
850            (None, Some((kb, _))) => {
851                out.push(Change {
852                    key: (*kb).clone(),
853                    kind: ChangeKind::Added,
854                });
855                ib.next();
856            }
857            (Some((ka, va)), Some((kb, vb))) => match ka.cmp(kb) {
858                core::cmp::Ordering::Less => {
859                    out.push(Change {
860                        key: (*ka).clone(),
861                        kind: ChangeKind::Removed,
862                    });
863                    ia.next();
864                }
865                core::cmp::Ordering::Greater => {
866                    out.push(Change {
867                        key: (*kb).clone(),
868                        kind: ChangeKind::Added,
869                    });
870                    ib.next();
871                }
872                core::cmp::Ordering::Equal => {
873                    if !va.content_eq(vb) {
874                        out.push(Change {
875                            key: (*ka).clone(),
876                            kind: ChangeKind::Modified,
877                        });
878                    }
879                    ia.next();
880                    ib.next();
881                }
882            },
883        }
884    }
885    out
886}
887
888/// Branch names are 1-255 bytes of printable, non-whitespace UTF-8.
889pub fn validate_branch_name(name: &str) -> Result<()> {
890    let ok = !name.is_empty()
891        && name.len() <= 255
892        && !name.chars().any(|c| c.is_whitespace() || c.is_control());
893    if ok {
894        Ok(())
895    } else {
896        Err(Error::BadBranchName(name.to_owned()))
897    }
898}