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