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
31pub const DISCARDS_REMEMBERED: usize = 100;
33
34#[derive(Debug, Clone, PartialEq, Eq)]
43pub struct Discarded {
44 pub name: String,
46 pub forked_at: CommitId,
48 pub commits: u64,
50}
51
52#[derive(Debug)]
57pub(crate) struct BranchHandle {
58 pub(crate) head: Mutex<CommitId>,
61 pub(crate) writer: Mutex<()>,
70 pub(crate) forked_at: CommitId,
73}
74
75pub(crate) struct DbInner {
76 pub(crate) commits: RwLock<BTreeMap<CommitId, Arc<Commit>>>,
78 pub(crate) branches: RwLock<BTreeMap<String, Arc<BranchHandle>>>,
81 pub(crate) dim: RwLock<Option<usize>>,
83 pub(crate) default_branch: String,
84 pub(crate) journal: RwLock<Option<Arc<dyn Journal>>>,
86 pub(crate) eviction: RwLock<Option<EvictionConfig>>,
89 pub(crate) on_evict: RwLock<Option<OnEvict>>,
91 pub(crate) access: AccessLog,
93 pub(crate) discarded: Mutex<VecDeque<Discarded>>,
95}
96
97impl core::fmt::Debug for DbInner {
98 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#[derive(Debug, Clone)]
135pub struct Db {
136 pub(crate) inner: Arc<DbInner>,
137}
138
139#[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 pub fn new() -> Self {
160 Self::build(DEFAULT_BRANCH)
161 }
162
163 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 pub fn default_branch(&self) -> &str {
199 &self.inner.default_branch
200 }
201
202 pub fn set_journal(&self, journal: Option<Arc<dyn Journal>>) {
214 *self.inner.journal.write() = journal;
215 }
216
217 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 pub fn set_eviction(&self, config: Option<EvictionConfig>) {
237 *self.inner.eviction.write() = config;
238 }
239
240 pub fn eviction(&self) -> Option<EvictionConfig> {
242 *self.inner.eviction.read()
243 }
244
245 pub fn on_evict(&self, hook: Option<OnEvict>) {
248 *self.inner.on_evict.write() = hook;
249 }
250
251 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 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 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 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 pub fn embedding_dim(&self) -> Option<usize> {
318 *self.inner.dim.read()
319 }
320
321 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 pub fn head(&self, branch: &str) -> Result<CommitId> {
334 Ok(*self.branch_handle(branch)?.head.lock())
335 }
336
337 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 pub fn has_branch(&self, branch: &str) -> bool {
349 self.inner.branches.read().contains_key(branch)
350 }
351
352 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 pub fn read(&self, branch: &str) -> Result<ReadView> {
381 let head = self.head(branch)?;
382 Ok(ReadView::new(self.commit(head)?))
383 }
384
385 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 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 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 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 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 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 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 pub fn begin(&self, branch: &str) -> Result<Txn> {
505 Txn::open(self.clone(), branch)
506 }
507
508 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 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 pub fn apply_record(&self, record: &Record) -> Result<()> {
528 match record {
529 Record::BranchCreated { name, at } => {
530 if self.has_branch(name) {
531 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 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 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 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 self.inner.access.fork(from, new_branch);
629 Ok(head)
630 }
631
632 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 pub fn branch_from_commit(&self, new_branch: &str, at: CommitId) -> Result<CommitId> {
641 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 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 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 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 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 pub fn discarded(&self) -> Vec<Discarded> {
737 self.inner.discarded.lock().iter().cloned().collect()
738 }
739
740 pub fn all_commits(&self) -> Vec<Arc<Commit>> {
742 self.inner.commits.read().values().map(Arc::clone).collect()
743 }
744
745 pub fn commit_count(&self) -> usize {
748 self.inner.commits.read().len()
749 }
750
751 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 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 self.inner.commits.write().entry(id).or_insert(commit);
801 *head = id;
802 Ok(id)
803 }
804
805 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 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 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
890pub(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 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
944pub 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}