use std::collections::{BTreeMap, BTreeSet, VecDeque};
use std::sync::Arc;
use parking_lot::{Mutex, RwLock};
use smallvec::SmallVec;
use crate::access::AccessLog;
use crate::commit::{Commit, LogEntry};
use crate::entry::{Entry, Op, Value};
use crate::error::{Error, Result};
use crate::evict::{self, EvictionConfig, OnEvict};
use crate::id::CommitId;
use crate::journal::{Journal, Record};
use crate::search::SearchHit;
use crate::store::{Root, Store};
use crate::txn::Txn;
use crate::view::{BranchInfo, Change, ChangeKind, ReadView};
pub const DEFAULT_BRANCH: &str = "main";
const AUTO_COMMIT_RETRIES: usize = 1024;
pub const DISCARDS_REMEMBERED: usize = 100;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Discarded {
pub name: String,
pub forked_at: CommitId,
pub commits: u64,
}
#[derive(Debug)]
pub(crate) struct BranchHandle {
pub(crate) head: Mutex<CommitId>,
pub(crate) writer: Mutex<()>,
pub(crate) forked_at: CommitId,
}
pub(crate) struct DbInner {
pub(crate) commits: RwLock<BTreeMap<CommitId, Arc<Commit>>>,
pub(crate) branches: RwLock<BTreeMap<String, Arc<BranchHandle>>>,
pub(crate) dim: RwLock<Option<usize>>,
pub(crate) default_branch: String,
pub(crate) journal: RwLock<Option<Arc<dyn Journal>>>,
pub(crate) eviction: RwLock<Option<EvictionConfig>>,
pub(crate) on_evict: RwLock<Option<OnEvict>>,
pub(crate) access: AccessLog,
pub(crate) discarded: Mutex<VecDeque<Discarded>>,
}
impl core::fmt::Debug for DbInner {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.debug_struct("DbInner")
.field("default_branch", &self.default_branch)
.field("branches", &self.branches.read().len())
.field("commits", &self.commits.read().len())
.field("embedding_dim", &*self.dim.read())
.field("journalled", &self.journal.read().is_some())
.field("eviction", &*self.eviction.read())
.field("on_evict", &self.on_evict.read().is_some())
.finish()
}
}
#[derive(Debug, Clone)]
pub struct Db {
pub(crate) inner: Arc<DbInner>,
}
#[derive(Debug)]
pub(crate) struct CommitDraft {
pub(crate) parents: SmallVec<[CommitId; 2]>,
pub(crate) root: Root,
pub(crate) seq: u64,
pub(crate) message: Option<String>,
pub(crate) ops: Vec<Op>,
}
impl Default for Db {
fn default() -> Self {
Self::new()
}
}
impl Db {
pub fn new() -> Self {
Self::build(DEFAULT_BRANCH)
}
pub fn with_default_branch(name: &str) -> Result<Self> {
validate_branch_name(name)?;
Ok(Self::build(name))
}
fn build(name: &str) -> Self {
let genesis = Arc::new(Commit::genesis());
let mut commits = BTreeMap::new();
commits.insert(genesis.id, Arc::clone(&genesis));
let mut branches = BTreeMap::new();
branches.insert(
name.to_owned(),
Arc::new(BranchHandle {
head: Mutex::new(genesis.id),
writer: Mutex::new(()),
forked_at: genesis.id,
}),
);
Db {
inner: Arc::new(DbInner {
commits: RwLock::new(commits),
branches: RwLock::new(branches),
dim: RwLock::new(None),
default_branch: name.to_owned(),
journal: RwLock::new(None),
eviction: RwLock::new(None),
on_evict: RwLock::new(None),
access: AccessLog::new(),
discarded: Mutex::new(VecDeque::new()),
}),
}
}
pub fn default_branch(&self) -> &str {
&self.inner.default_branch
}
pub fn set_journal(&self, journal: Option<Arc<dyn Journal>>) {
*self.inner.journal.write() = journal;
}
pub fn is_journalled(&self) -> bool {
self.inner.journal.read().is_some()
}
fn record(&self, record: &Record) -> Result<()> {
match self.inner.journal.read().as_ref() {
None => Ok(()),
Some(journal) => journal.append(record).map_err(|e| Error::Journal(e.0)),
}
}
pub fn set_eviction(&self, config: Option<EvictionConfig>) {
*self.inner.eviction.write() = config;
}
pub fn eviction(&self) -> Option<EvictionConfig> {
*self.inner.eviction.read()
}
pub fn on_evict(&self, hook: Option<OnEvict>) {
*self.inner.on_evict.write() = hook;
}
pub(crate) fn note_read(&self, branch: &str, seq: u64, keys: impl Iterator<Item = String>) {
if self.inner.eviction.read().is_some() {
self.inner.access.record(branch, seq, keys);
}
}
pub fn enforce_budget(&self, branch: &str) -> Result<Option<CommitId>> {
let Some(config) = *self.inner.eviction.read() else {
return Ok(None);
};
for _ in 0..AUTO_COMMIT_RETRIES {
let head_id = self.head(branch)?;
let head = self.commit(head_id)?;
let access = self.inner.access.snapshot(branch);
let chosen = evict::choose(head.root.iter(), head.seq, &access, &config);
if chosen.is_empty() {
return Ok(None);
}
if let Some(hook) = self.inner.on_evict.read().as_ref() {
hook(&chosen);
}
let ops: Vec<Op> = chosen
.iter()
.map(|e| Op::Evict { key: e.key.clone() })
.collect();
let seq = head.seq + 1;
let mut root = head.root.clone();
crate::txn::apply_ops(&mut root, &ops, seq);
let message = Some(format!("evict {} entr(ies) over budget", ops.len()));
match self.commit_onto(
branch,
head_id,
CommitDraft {
parents: smallvec::smallvec![head_id],
root,
seq,
message,
ops,
},
) {
Ok(id) => {
let gone: BTreeSet<String> = chosen.into_iter().map(|e| e.key).collect();
self.inner.access.retain(branch, |k| !gone.contains(k));
return Ok(Some(id));
}
Err(Error::Conflict { .. }) => continue,
Err(e) => return Err(e),
}
}
Ok(None)
}
pub fn embedding_dim(&self) -> Option<usize> {
*self.inner.dim.read()
}
pub(crate) fn branch_handle(&self, branch: &str) -> Result<Arc<BranchHandle>> {
self.inner
.branches
.read()
.get(branch)
.map(Arc::clone)
.ok_or_else(|| Error::NoSuchBranch(branch.to_owned()))
}
pub fn head(&self, branch: &str) -> Result<CommitId> {
Ok(*self.branch_handle(branch)?.head.lock())
}
pub fn commit(&self, id: CommitId) -> Result<Arc<Commit>> {
self.inner
.commits
.read()
.get(&id)
.map(Arc::clone)
.ok_or(Error::NoSuchCommit(id))
}
pub fn has_branch(&self, branch: &str) -> bool {
self.inner.branches.read().contains_key(branch)
}
pub fn branches(&self) -> Vec<BranchInfo> {
let names: Vec<(String, Arc<BranchHandle>)> = self
.inner
.branches
.read()
.iter()
.map(|(k, v)| (k.clone(), Arc::clone(v)))
.collect();
let commits = self.inner.commits.read();
names
.into_iter()
.filter_map(|(name, handle)| {
let head = *handle.head.lock();
let commit = commits.get(&head)?;
Some(BranchInfo {
is_default: name == self.inner.default_branch,
name,
head,
seq: commit.seq,
key_count: commit.root.len(),
forked_at: handle.forked_at,
})
})
.collect()
}
pub fn read(&self, branch: &str) -> Result<ReadView> {
let head = self.head(branch)?;
Ok(ReadView::new(self.commit(head)?))
}
pub fn at(&self, branch: &str, seq: u64) -> Result<ReadView> {
let head = self.commit(self.head(branch)?)?;
if seq > head.seq {
return Err(Error::NoSuchSeq {
branch: branch.to_owned(),
seq,
head_seq: head.seq,
});
}
let mut cur = head;
while cur.seq > seq {
let parent = cur.first_parent().ok_or_else(|| Error::NoSuchSeq {
branch: branch.to_owned(),
seq,
head_seq: cur.seq,
})?;
cur = self.commit(parent)?;
}
Ok(ReadView::new(cur))
}
pub fn get(&self, branch: &str, key: &str) -> Result<Option<Arc<Entry>>> {
let view = self.read(branch)?;
let found = view.get(key);
if found.is_some() {
self.note_read(branch, view.seq(), std::iter::once(key.to_owned()));
}
Ok(found)
}
pub fn list(
&self,
branch: &str,
prefix: &str,
limit: Option<usize>,
) -> Result<Vec<(String, Arc<Entry>)>> {
let view = self.read(branch)?;
let found = view.list(prefix, limit);
self.note_read(branch, view.seq(), found.iter().map(|(k, _)| k.clone()));
Ok(found)
}
pub fn search(
&self,
branch: &str,
query: &[f32],
k: usize,
prefix: Option<&str>,
) -> Result<Vec<SearchHit>> {
if let Some(expected) = self.embedding_dim() {
if !query.is_empty() && query.len() != expected {
return Err(Error::BadQueryDimension {
expected,
got: query.len(),
});
}
}
let view = self.read(branch)?;
let hits = crate::search::search(&view, query, k, prefix);
self.note_read(branch, view.seq(), hits.iter().map(|h| h.key.clone()));
Ok(hits)
}
pub fn log(&self, branch: &str, limit: Option<usize>) -> Result<Vec<LogEntry>> {
let mut out = Vec::new();
let mut cur = Some(self.head(branch)?);
while let Some(id) = cur {
if limit.is_some_and(|n| out.len() >= n) {
break;
}
let commit = self.commit(id)?;
out.push(LogEntry {
id: commit.id,
seq: commit.seq,
parents: commit.parents.to_vec(),
message: commit.message.clone(),
op_count: commit.ops.len(),
key_count: commit.root.len(),
});
cur = commit.first_parent();
}
Ok(out)
}
pub fn resolve(&self, reference: &str) -> Result<Arc<Commit>> {
if self.has_branch(reference) {
return self.commit(self.head(reference)?);
}
match CommitId::from_hex(reference) {
Ok(id) => self.commit(id),
Err(_) => Err(Error::NoSuchBranch(reference.to_owned())),
}
}
pub fn diff(&self, a: &str, b: &str) -> Result<Vec<Change>> {
let ca = self.resolve(a)?;
let cb = self.resolve(b)?;
Ok(diff_roots(&ca.root, &cb.root))
}
pub fn begin(&self, branch: &str) -> Result<Txn> {
Txn::open(self.clone(), branch)
}
pub fn put(&self, branch: &str, key: &str, value: Value) -> Result<CommitId> {
let id = self.auto_commit(branch, &format!("put {key}"), |txn| {
txn.put(key, value.clone())
})?;
self.enforce_budget(branch)?;
Ok(id)
}
pub fn delete(&self, branch: &str, key: &str) -> Result<CommitId> {
self.auto_commit(branch, &format!("delete {key}"), |txn| txn.delete(key))
}
pub fn apply_record(&self, record: &Record) -> Result<()> {
match record {
Record::BranchCreated { name, at } => {
if self.has_branch(name) {
return Ok(());
}
let _ = self.commit(*at)?;
self.create_branch_unrecorded(name, *at)?;
Ok(())
}
Record::BranchDiscarded { name } => {
if !self.has_branch(name) {
return Ok(());
}
self.discard(name)
}
Record::HeadMoved { branch, to } => {
let _ = self.commit(*to)?;
let handle = self.branch_handle(branch)?;
*handle.head.lock() = *to;
Ok(())
}
Record::Commit {
branch,
parents,
seq,
message,
ops,
} => {
let base = parents
.first()
.copied()
.ok_or_else(|| Error::Journal("a commit record has no parent".to_owned()))?;
let base_commit = self.commit(base)?;
let mut root = base_commit.root.clone();
crate::txn::apply_ops(&mut root, ops, *seq);
let id = Commit::compute_id(parents, message.as_deref(), ops);
let commit = Arc::new(Commit {
id,
parents: parents.clone(),
root,
seq: *seq,
message: message.clone(),
ops: ops.clone(),
});
self.inner.commits.write().entry(id).or_insert(commit);
if !self.has_branch(branch) {
self.create_branch_unrecorded(branch, id)?;
} else {
let handle = self.branch_handle(branch)?;
*handle.head.lock() = id;
}
Ok(())
}
}
}
fn auto_commit<F>(&self, branch: &str, message: &str, mut f: F) -> Result<CommitId>
where
F: FnMut(&mut Txn) -> Result<()>,
{
let handle = self.branch_handle(branch)?;
let _writing = handle.writer.lock();
let mut last = None;
for _ in 0..AUTO_COMMIT_RETRIES {
let mut txn = self.begin(branch)?;
f(&mut txn)?;
match txn.commit(Some(message.to_owned())) {
Ok(id) => return Ok(id),
Err(e @ Error::Conflict { .. }) => {
last = Some(e);
std::thread::yield_now();
}
Err(e) => return Err(e),
}
}
Err(last.unwrap_or_else(|| Error::NoSuchBranch(branch.to_owned())))
}
pub fn fork(&self, from: &str, new_branch: &str) -> Result<CommitId> {
let head = self.head(from)?;
self.create_branch(new_branch, head)?;
self.inner.access.fork(from, new_branch);
Ok(head)
}
pub fn fork_at(&self, from: &str, seq: u64, new_branch: &str) -> Result<CommitId> {
let head = self.at(from, seq)?.commit_id();
self.create_branch(new_branch, head)?;
Ok(head)
}
pub fn branch_from_commit(&self, new_branch: &str, at: CommitId) -> Result<CommitId> {
let _ = self.commit(at)?;
self.create_branch(new_branch, at)?;
Ok(at)
}
pub(crate) fn create_branch(&self, name: &str, head: CommitId) -> Result<()> {
validate_branch_name(name)?;
if self.has_branch(name) {
return Err(Error::BranchExists(name.to_owned()));
}
self.record(&Record::BranchCreated {
name: name.to_owned(),
at: head,
})?;
self.create_branch_unrecorded(name, head)
}
fn create_branch_unrecorded(&self, name: &str, head: CommitId) -> Result<()> {
validate_branch_name(name)?;
let mut branches = self.inner.branches.write();
if branches.contains_key(name) {
return Err(Error::BranchExists(name.to_owned()));
}
branches.insert(
name.to_owned(),
Arc::new(BranchHandle {
head: Mutex::new(head),
writer: Mutex::new(()),
forked_at: head,
}),
);
Ok(())
}
pub fn discard(&self, branch: &str) -> Result<()> {
if branch == self.inner.default_branch {
return Err(Error::CannotDiscardDefaultBranch(branch.to_owned()));
}
let mut branches = self.inner.branches.write();
if !branches.contains_key(branch) {
return Err(Error::NoSuchBranch(branch.to_owned()));
}
self.record(&Record::BranchDiscarded {
name: branch.to_owned(),
})?;
if let Some(handle) = branches.remove(branch) {
let commits = self.inner.commits.read();
let seq_of = |id: &CommitId| commits.get(id).map_or(0, |c| c.seq);
let made = seq_of(&handle.head.lock()).saturating_sub(seq_of(&handle.forked_at));
drop(commits);
let mut discarded = self.inner.discarded.lock();
if discarded.len() == DISCARDS_REMEMBERED {
discarded.pop_front();
}
discarded.push_back(Discarded {
name: branch.to_owned(),
forked_at: handle.forked_at,
commits: made,
});
}
self.inner.access.forget(branch);
let surviving_heads: Vec<CommitId> = branches.values().map(|h| *h.head.lock()).collect();
drop(branches);
self.collect_unreachable(&surviving_heads);
Ok(())
}
fn collect_unreachable(&self, surviving_heads: &[CommitId]) {
let mut commits = self.inner.commits.write();
let mut reachable: BTreeSet<CommitId> = BTreeSet::new();
let mut queue: VecDeque<CommitId> = surviving_heads.iter().copied().collect();
while let Some(id) = queue.pop_front() {
if !reachable.insert(id) {
continue;
}
if let Some(commit) = commits.get(&id) {
for parent in &commit.parents {
queue.push_back(*parent);
}
}
}
commits.retain(|id, _| reachable.contains(id));
}
pub fn discarded(&self) -> Vec<Discarded> {
self.inner.discarded.lock().iter().cloned().collect()
}
pub fn all_commits(&self) -> Vec<Arc<Commit>> {
self.inner.commits.read().values().map(Arc::clone).collect()
}
pub fn commit_count(&self) -> usize {
self.inner.commits.read().len()
}
pub(crate) fn commit_onto(
&self,
branch: &str,
expected: CommitId,
draft: CommitDraft,
) -> Result<CommitId> {
let CommitDraft {
parents,
root,
seq,
message,
ops,
} = draft;
let id = Commit::compute_id(&parents, message.as_deref(), &ops);
let commit = Arc::new(Commit {
id,
parents,
root,
seq,
message,
ops,
});
let handle = self.branch_handle(branch)?;
let mut head = handle.head.lock();
if *head != expected {
return Err(Error::Conflict {
branch: branch.to_owned(),
expected,
actual: *head,
});
}
self.record(&Record::Commit {
branch: branch.to_owned(),
parents: commit.parents.clone(),
seq: commit.seq,
message: commit.message.clone(),
ops: commit.ops.clone(),
})?;
self.inner.commits.write().entry(id).or_insert(commit);
*head = id;
Ok(id)
}
pub(crate) fn fast_forward(
&self,
branch: &str,
expected: CommitId,
to: CommitId,
) -> Result<CommitId> {
let handle = self.branch_handle(branch)?;
let mut head = handle.head.lock();
if *head != expected {
return Err(Error::Conflict {
branch: branch.to_owned(),
expected,
actual: *head,
});
}
self.record(&Record::HeadMoved {
branch: branch.to_owned(),
to,
})?;
*head = to;
Ok(to)
}
pub(crate) fn check_dim(&self, embedding: Option<&Vec<f32>>) -> Result<()> {
let Some(e) = embedding else { return Ok(()) };
let mut dim = self.inner.dim.write();
match *dim {
None => {
*dim = Some(e.len());
Ok(())
}
Some(expected) if expected == e.len() => Ok(()),
Some(expected) => Err(Error::DimensionMismatch {
expected,
got: e.len(),
}),
}
}
pub(crate) fn common_ancestor(&self, a: CommitId, b: CommitId) -> Option<CommitId> {
let ancestors_of_b = self.ancestors(b);
let commits = self.inner.commits.read();
let mut seen: BTreeSet<CommitId> = BTreeSet::new();
let mut queue: VecDeque<CommitId> = VecDeque::new();
queue.push_back(a);
while let Some(id) = queue.pop_front() {
if !seen.insert(id) {
continue;
}
if ancestors_of_b.contains(&id) {
return Some(id);
}
if let Some(commit) = commits.get(&id) {
for parent in &commit.parents {
queue.push_back(*parent);
}
}
}
None
}
fn ancestors(&self, id: CommitId) -> BTreeSet<CommitId> {
let commits = self.inner.commits.read();
let mut seen = BTreeSet::new();
let mut queue = VecDeque::from([id]);
while let Some(cur) = queue.pop_front() {
if !seen.insert(cur) {
continue;
}
if let Some(commit) = commits.get(&cur) {
for parent in &commit.parents {
queue.push_back(*parent);
}
}
}
seen
}
}
pub(crate) fn diff_roots(a: &Root, b: &Root) -> Vec<Change> {
let mut out = Vec::new();
let mut ia = a.iter().peekable();
let mut ib = b.iter().peekable();
loop {
match (ia.peek(), ib.peek()) {
(None, None) => break,
(Some((ka, _)), None) => {
out.push(Change {
key: (*ka).clone(),
kind: ChangeKind::Removed,
});
ia.next();
}
(None, Some((kb, _))) => {
out.push(Change {
key: (*kb).clone(),
kind: ChangeKind::Added,
});
ib.next();
}
(Some((ka, va)), Some((kb, vb))) => match ka.cmp(kb) {
core::cmp::Ordering::Less => {
out.push(Change {
key: (*ka).clone(),
kind: ChangeKind::Removed,
});
ia.next();
}
core::cmp::Ordering::Greater => {
out.push(Change {
key: (*kb).clone(),
kind: ChangeKind::Added,
});
ib.next();
}
core::cmp::Ordering::Equal => {
if !va.content_eq(vb) {
out.push(Change {
key: (*ka).clone(),
kind: ChangeKind::Modified,
});
}
ia.next();
ib.next();
}
},
}
}
out
}
pub fn validate_branch_name(name: &str) -> Result<()> {
let ok = !name.is_empty()
&& name.len() <= 255
&& !name.chars().any(|c| c.is_whitespace() || c.is_control());
if ok {
Ok(())
} else {
Err(Error::BadBranchName(name.to_owned()))
}
}