Skip to main content

memfork_core/
txn.rs

1//! Atomic multi-key transactions with real rollback (DESIGN §4.2, §4.3).
2
3use std::collections::BTreeMap;
4use std::sync::Arc;
5
6use smallvec::smallvec;
7
8use crate::db::{CommitDraft, Db};
9use crate::entry::{validate_key, Entry, Op, Value};
10use crate::error::{Error, Result};
11use crate::id::CommitId;
12use crate::store::Root;
13
14#[derive(Debug, Clone)]
15enum Staged {
16    Put(Value),
17    Delete,
18}
19
20/// A set of writes that become visible all at once, or not at all.
21///
22/// A transaction reads the branch head once, when it is opened, and stages its
23/// writes privately. [`Txn::commit`] swaps the branch head to a new commit in
24/// one step, and fails with [`Error::Conflict`] if another writer moved the
25/// head meanwhile; the caller then retries. Dropping a transaction without
26/// committing is a rollback that leaves no commit, no head movement and no
27/// change to any sequence counter.
28#[derive(Debug)]
29pub struct Txn {
30    db: Db,
31    branch: String,
32    base: CommitId,
33    base_root: Root,
34    base_seq: u64,
35    staged: BTreeMap<String, Staged>,
36}
37
38impl Txn {
39    pub(crate) fn open(db: Db, branch: &str) -> Result<Self> {
40        let base = db.head(branch)?;
41        let commit = db.commit(base)?;
42        Ok(Txn {
43            db,
44            branch: branch.to_owned(),
45            base,
46            base_root: commit.root.clone(),
47            base_seq: commit.seq,
48            staged: BTreeMap::new(),
49        })
50    }
51
52    /// The branch this transaction writes to.
53    pub fn branch(&self) -> &str {
54        &self.branch
55    }
56
57    /// The commit this transaction was opened against.
58    pub fn base(&self) -> CommitId {
59        self.base
60    }
61
62    /// Whether anything has been staged yet.
63    pub fn is_empty(&self) -> bool {
64        self.staged.is_empty()
65    }
66
67    /// Stage a write.
68    pub fn put(&mut self, key: &str, value: Value) -> Result<()> {
69        validate_key(key)?;
70        value.validate()?;
71        self.db.check_dim(value.embedding.as_ref())?;
72        self.staged.insert(key.to_owned(), Staged::Put(value));
73        Ok(())
74    }
75
76    /// Stage a delete.
77    pub fn delete(&mut self, key: &str) -> Result<()> {
78        validate_key(key)?;
79        self.staged.insert(key.to_owned(), Staged::Delete);
80        Ok(())
81    }
82
83    /// Read a key as this transaction sees it: staged writes first, then the
84    /// branch as it stood when the transaction was opened.
85    pub fn get(&self, key: &str) -> Option<Arc<Entry>> {
86        match self.staged.get(key) {
87            Some(Staged::Delete) => None,
88            Some(Staged::Put(v)) => {
89                let created = self
90                    .base_root
91                    .get(key)
92                    .map_or(self.base_seq + 1, |e| e.created_seq);
93                Some(Arc::new(v.clone().into_entry(self.base_seq + 1, created)))
94            }
95            None => self.base_root.get(key).cloned(),
96        }
97    }
98
99    /// Discard every staged write. Equivalent to dropping the transaction, and
100    /// spelled out for callers who want the intent on the page.
101    pub fn rollback(self) {
102        drop(self);
103    }
104
105    /// Apply every staged write as one commit and move the branch head.
106    ///
107    /// A transaction that stages nothing, or whose writes all turn out to be
108    /// no-ops, creates no commit and returns the unchanged head.
109    pub fn commit(self, message: Option<String>) -> Result<CommitId> {
110        let seq = self.base_seq + 1;
111        let mut ops: Vec<Op> = Vec::with_capacity(self.staged.len());
112        // `staged` is a BTreeMap, so operations are emitted in ascending key
113        // order. That ordering is part of what makes commit ids reproducible.
114        for (key, staged) in &self.staged {
115            match staged {
116                Staged::Put(value) => ops.push(Op::Put {
117                    key: key.clone(),
118                    value: value.clone(),
119                }),
120                Staged::Delete => {
121                    // Deleting a key that is not there is not an event.
122                    if self.base_root.get(key).is_some() {
123                        ops.push(Op::Delete { key: key.clone() });
124                    }
125                }
126            }
127        }
128        if ops.is_empty() {
129            return Ok(self.base);
130        }
131
132        let mut root = self.base_root.clone();
133        apply_ops(&mut root, &ops, seq);
134
135        self.db.commit_onto(
136            &self.branch,
137            self.base,
138            CommitDraft {
139                parents: smallvec![self.base],
140                root,
141                seq,
142                message,
143                ops,
144            },
145        )
146    }
147}
148
149/// Apply a change set to a root in place.
150///
151/// `created_seq` is preserved when a key is overwritten, so it keeps meaning
152/// "when this key first appeared on this branch".
153pub(crate) fn apply_ops(root: &mut Root, ops: &[Op], seq: u64) {
154    for op in ops {
155        match op {
156            Op::Put { key, value } => {
157                let created = root.get(key).map_or(seq, |e| e.created_seq);
158                root.insert_mut(
159                    key.clone(),
160                    Arc::new(value.clone().into_entry(seq, created)),
161                );
162            }
163            Op::Delete { key } | Op::Evict { key } => {
164                root.remove_mut(key);
165            }
166        }
167    }
168}
169
170impl Drop for Txn {
171    fn drop(&mut self) {
172        // Nothing to undo: a transaction never touches shared state until
173        // `commit` wins the head swap. The impl exists to make that explicit.
174    }
175}
176
177/// Convenience: run a closure in a transaction, retrying on optimistic
178/// conflicts, and commit it.
179pub fn with_txn<F>(
180    db: &Db,
181    branch: &str,
182    message: &str,
183    retries: usize,
184    mut f: F,
185) -> Result<CommitId>
186where
187    F: FnMut(&mut Txn) -> Result<()>,
188{
189    let mut last = None;
190    for _ in 0..retries.max(1) {
191        let mut txn = db.begin(branch)?;
192        f(&mut txn)?;
193        match txn.commit(Some(message.to_owned())) {
194            Ok(id) => return Ok(id),
195            Err(e @ Error::Conflict { .. }) => last = Some(e),
196            Err(e) => return Err(e),
197        }
198    }
199    Err(last.unwrap_or_else(|| Error::NoSuchBranch(branch.to_owned())))
200}