Skip to main content

memfork_core/
commit.rs

1//! Commits: the immutable nodes of the history graph (DESIGN §4.1).
2
3use core::fmt;
4
5use smallvec::SmallVec;
6
7use crate::encode::Canonical;
8use crate::entry::Op;
9use crate::id::CommitId;
10use crate::store::Root;
11
12/// One immutable point in a branch's history.
13///
14/// A commit owns a whole root, but roots are structurally shared, so the
15/// marginal cost of a commit is the path it rewrote, not the database.
16#[derive(Clone)]
17pub struct Commit {
18    /// Content address: `blake3(parent ids ‖ message ‖ canonical-encoded ops)`.
19    pub id: CommitId,
20    /// Zero parents for the genesis commit, one normally, two for a merge.
21    pub parents: SmallVec<[CommitId; 2]>,
22    /// The state of the database after this commit.
23    pub root: Root,
24    /// Monotonic along the first-parent chain; the genesis commit is 0.
25    pub seq: u64,
26    /// Optional human-readable message. Not part of the content address.
27    pub message: Option<String>,
28    /// This commit's change set, sorted by key.
29    pub ops: Vec<Op>,
30}
31
32impl Commit {
33    /// Compute the content address of a commit from its parents, message and
34    /// change set.
35    ///
36    /// DESIGN §4.1 defines the id as `blake3(parent ids ‖ message ‖
37    /// canonical-encoded ops)`. `seq` and wall-clock time take no part, so the
38    /// same change with the same message applied to the same parents is the
39    /// same commit everywhere.
40    ///
41    /// The message is encoded as an optional length-prefixed string, so a
42    /// commit with no message, one with an empty message and one with a real
43    /// message are three different commits.
44    pub fn compute_id(parents: &[CommitId], message: Option<&str>, ops: &[Op]) -> CommitId {
45        let mut c = Canonical::new();
46        c.u64(parents.len() as u64);
47        for p in parents {
48            c.commit_id(p);
49        }
50        c.opt_str(message);
51        c.u64(ops.len() as u64);
52        for op in ops {
53            op.encode(&mut c);
54        }
55        c.finalize()
56    }
57
58    /// The first parent, i.e. the previous commit on this branch.
59    pub fn first_parent(&self) -> Option<CommitId> {
60        self.parents.first().copied()
61    }
62
63    /// The message every database's first commit carries.
64    pub(crate) const GENESIS_MESSAGE: &'static str = "genesis";
65
66    /// The genesis commit every database starts from. Identical in every
67    /// database on every platform, since it has no parents, no operations and
68    /// a fixed message.
69    pub(crate) fn genesis() -> Self {
70        let id = Commit::compute_id(&[], Some(Commit::GENESIS_MESSAGE), &[]);
71        Commit {
72            id,
73            parents: SmallVec::new(),
74            root: Root::new_sync(),
75            seq: 0,
76            message: Some(Commit::GENESIS_MESSAGE.to_owned()),
77            ops: Vec::new(),
78        }
79    }
80}
81
82impl fmt::Debug for Commit {
83    /// Summarizes rather than dumping the root, which may hold millions of keys.
84    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
85        f.debug_struct("Commit")
86            .field("id", &self.id.to_hex())
87            .field(
88                "parents",
89                &self.parents.iter().map(|p| p.to_hex()).collect::<Vec<_>>(),
90            )
91            .field("seq", &self.seq)
92            .field("message", &self.message)
93            .field("ops", &self.ops.len())
94            .field("keys", &rpds::RedBlackTreeMap::size(&self.root))
95            .finish()
96    }
97}
98
99/// One line of `log` output (DESIGN §4.2).
100#[derive(Debug, Clone)]
101pub struct LogEntry {
102    /// The commit's content address.
103    pub id: CommitId,
104    /// The commit's sequence number on this branch.
105    pub seq: u64,
106    /// The commit's parents.
107    pub parents: Vec<CommitId>,
108    /// The commit message, if one was given.
109    pub message: Option<String>,
110    /// How many operations the commit's change set holds.
111    pub op_count: usize,
112    /// How many keys the database held after this commit.
113    pub key_count: usize,
114}