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