1use 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
21pub const DEFAULT_BRANCH: &str = "main";
23
24const AUTO_COMMIT_RETRIES: usize = 1024;
30
31#[derive(Debug)]
36pub(crate) struct BranchHandle {
37 pub(crate) head: Mutex<CommitId>,
40 pub(crate) writer: Mutex<()>,
49}
50
51pub(crate) struct DbInner {
52 pub(crate) commits: RwLock<BTreeMap<CommitId, Arc<Commit>>>,
54 pub(crate) branches: RwLock<BTreeMap<String, Arc<BranchHandle>>>,
57 pub(crate) dim: RwLock<Option<usize>>,
59 pub(crate) default_branch: String,
60 pub(crate) journal: RwLock<Option<Arc<dyn Journal>>>,
62 pub(crate) eviction: RwLock<Option<EvictionConfig>>,
65 pub(crate) on_evict: RwLock<Option<OnEvict>>,
67 pub(crate) access: AccessLog,
69}
70
71impl core::fmt::Debug for DbInner {
72 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#[derive(Debug, Clone)]
109pub struct Db {
110 pub(crate) inner: Arc<DbInner>,
111}
112
113#[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 pub fn new() -> Self {
134 Self::build(DEFAULT_BRANCH)
135 }
136
137 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 pub fn default_branch(&self) -> &str {
171 &self.inner.default_branch
172 }
173
174 pub fn set_journal(&self, journal: Option<Arc<dyn Journal>>) {
186 *self.inner.journal.write() = journal;
187 }
188
189 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 pub fn set_eviction(&self, config: Option<EvictionConfig>) {
209 *self.inner.eviction.write() = config;
210 }
211
212 pub fn eviction(&self) -> Option<EvictionConfig> {
214 *self.inner.eviction.read()
215 }
216
217 pub fn on_evict(&self, hook: Option<OnEvict>) {
220 *self.inner.on_evict.write() = hook;
221 }
222
223 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 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 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 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 pub fn embedding_dim(&self) -> Option<usize> {
290 *self.inner.dim.read()
291 }
292
293 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 pub fn head(&self, branch: &str) -> Result<CommitId> {
306 Ok(*self.branch_handle(branch)?.head.lock())
307 }
308
309 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 pub fn has_branch(&self, branch: &str) -> bool {
321 self.inner.branches.read().contains_key(branch)
322 }
323
324 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 pub fn read(&self, branch: &str) -> Result<ReadView> {
352 let head = self.head(branch)?;
353 Ok(ReadView::new(self.commit(head)?))
354 }
355
356 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 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 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 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 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 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 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 pub fn begin(&self, branch: &str) -> Result<Txn> {
476 Txn::open(self.clone(), branch)
477 }
478
479 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 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 pub fn apply_record(&self, record: &Record) -> Result<()> {
499 match record {
500 Record::BranchCreated { name, at } => {
501 if self.has_branch(name) {
502 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 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 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 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 self.inner.access.fork(from, new_branch);
600 Ok(head)
601 }
602
603 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 pub fn branch_from_commit(&self, new_branch: &str, at: CommitId) -> Result<CommitId> {
612 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 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 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 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 pub fn commit_count(&self) -> usize {
692 self.inner.commits.read().len()
693 }
694
695 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 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 self.inner.commits.write().entry(id).or_insert(commit);
745 *head = id;
746 Ok(id)
747 }
748
749 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 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 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
834pub(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 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
888pub 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}