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}