markdown_compiler/
tree_digest.rs

1use std::{fmt, str::FromStr};
2
3use thiserror::Error;
4
5use super::{
6    DiscoveredAsset, DiscoveredContentTree, DiscoveredPost, PostCollection, transcript::Transcript,
7};
8
9const CONTENT_TREE_CONTEXT: &str = "maincopy content tree digest v1";
10const CONTENT_TREE_KIND: &[u8] = b"maincopy-content-tree";
11const CONTENT_TREE_VERSION: u16 = 1;
12const CONTENT_TREE_PREFIX: &str = "content-b3-v1-";
13
14const PUBLICATION_SECTION: u8 = 0;
15const POSTS_SECTION: u8 = 1;
16const ASSETS_SECTION: u8 = 2;
17// The v1 tree digest and candidate archive share these collection tags.
18pub(super) const POSTS_COLLECTION: u8 = 0;
19pub(super) const DRAFTS_COLLECTION: u8 = 1;
20
21/// Versioned identity of the exact managed inputs in one discovered content tree.
22#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
23pub struct ContentTreeDigest([u8; 32]);
24
25impl ContentTreeDigest {
26    pub const fn from_bytes(bytes: [u8; 32]) -> Self {
27        Self(bytes)
28    }
29
30    pub const fn as_bytes(&self) -> &[u8; 32] {
31        &self.0
32    }
33
34    pub fn parse(value: &str) -> Result<Self, ContentTreeDigestParseError> {
35        let encoded = value
36            .strip_prefix(CONTENT_TREE_PREFIX)
37            .ok_or(ContentTreeDigestParseError::InvalidPrefix)?;
38        if encoded.len() != 64 {
39            return Err(ContentTreeDigestParseError::InvalidLength);
40        }
41        let mut bytes = [0_u8; 32];
42        for (index, pair) in encoded.as_bytes().as_chunks::<2>().0.iter().enumerate() {
43            let high =
44                decode_nibble(pair[0]).ok_or(ContentTreeDigestParseError::InvalidEncoding)?;
45            let low = decode_nibble(pair[1]).ok_or(ContentTreeDigestParseError::InvalidEncoding)?;
46            bytes[index] = high << 4 | low;
47        }
48        Ok(Self(bytes))
49    }
50}
51
52impl FromStr for ContentTreeDigest {
53    type Err = ContentTreeDigestParseError;
54
55    fn from_str(value: &str) -> Result<Self, Self::Err> {
56        Self::parse(value)
57    }
58}
59
60#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
61pub enum ContentTreeDigestParseError {
62    #[error("content digest must start with content-b3-v1-")]
63    InvalidPrefix,
64    #[error("content digest must contain exactly 32 encoded bytes")]
65    InvalidLength,
66    #[error("content digest must use lowercase hexadecimal")]
67    InvalidEncoding,
68}
69
70impl fmt::Display for ContentTreeDigest {
71    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
72        write!(
73            formatter,
74            "{CONTENT_TREE_PREFIX}{}",
75            blake3::Hash::from_bytes(self.0).to_hex()
76        )
77    }
78}
79
80const fn decode_nibble(byte: u8) -> Option<u8> {
81    match byte {
82        b'0'..=b'9' => Some(byte - b'0'),
83        b'a'..=b'f' => Some(byte - b'a' + 10),
84        _ => None,
85    }
86}
87
88impl DiscoveredContentTree {
89    /// Computes a deterministic token for the exact managed tree already in memory.
90    pub fn digest(&self) -> ContentTreeDigest {
91        let mut transcript = Transcript::new(
92            CONTENT_TREE_CONTEXT,
93            CONTENT_TREE_KIND,
94            CONTENT_TREE_VERSION,
95        );
96
97        transcript.tag(PUBLICATION_SECTION);
98        transcript.string(self.publication.path.as_str());
99        transcript.bytes(self.publication.source.as_bytes());
100
101        transcript.tag(POSTS_SECTION);
102        let mut posts: Vec<_> = self.posts.iter().collect();
103        posts.sort_unstable_by(compare_posts);
104        transcript.sequence_len(posts.len());
105        for post in posts {
106            transcript.string(post.path.as_str());
107            transcript.tag(collection_tag(post.collection));
108            transcript.bytes(post.source.as_bytes());
109        }
110
111        transcript.tag(ASSETS_SECTION);
112        let mut assets: Vec<_> = self.assets.iter().collect();
113        assets.sort_unstable_by(compare_assets);
114        transcript.sequence_len(assets.len());
115        for asset in assets {
116            transcript.string(asset.path.as_str());
117            transcript.bytes(&asset.bytes);
118        }
119
120        ContentTreeDigest(*transcript.finish().as_bytes())
121    }
122}
123
124// Archives use the same canonical order as the tree identity they retain.
125pub(super) fn compare_posts(left: &&DiscoveredPost, right: &&DiscoveredPost) -> std::cmp::Ordering {
126    left.path
127        .cmp(&right.path)
128        .then_with(|| collection_tag(left.collection).cmp(&collection_tag(right.collection)))
129        .then_with(|| left.source.cmp(&right.source))
130}
131
132pub(super) fn compare_assets(
133    left: &&DiscoveredAsset,
134    right: &&DiscoveredAsset,
135) -> std::cmp::Ordering {
136    left.path
137        .cmp(&right.path)
138        .then_with(|| left.bytes.as_ref().cmp(right.bytes.as_ref()))
139}
140
141pub(super) const fn collection_tag(collection: PostCollection) -> u8 {
142    match collection {
143        PostCollection::Posts => POSTS_COLLECTION,
144        PostCollection::Drafts => DRAFTS_COLLECTION,
145    }
146}
147
148#[cfg(test)]
149mod tests {
150    use super::*;
151    use crate::tree::{asset, post, publication};
152    use crate::{LogicalAssetPath, LogicalContentPath};
153
154    fn fixture() -> DiscoveredContentTree {
155        let posts = vec![
156            post(
157                "posts/first.md",
158                PostCollection::Posts,
159                "first post".to_owned(),
160            ),
161            post(
162                "drafts/second.md",
163                PostCollection::Drafts,
164                "second post".to_owned(),
165            ),
166        ];
167        let assets = vec![
168            asset(
169                LogicalAssetPath::parse("assets/first.bin").unwrap(),
170                b"first asset".to_vec(),
171            ),
172            asset(
173                LogicalAssetPath::parse("assets/second.bin").unwrap(),
174                b"second asset".to_vec(),
175            ),
176        ];
177        DiscoveredContentTree::new(
178            publication("publication.toml", "publication settings".to_owned()),
179            posts,
180            assets,
181            64,
182        )
183    }
184
185    #[test]
186    fn identical_logical_trees_have_one_order_independent_digest() {
187        let first = fixture();
188        assert_eq!(
189            first.digest().to_string(),
190            "content-b3-v1-09af660c29bbee4fc3011605979181aac9b6733a37a275ddc3e5f222030186af"
191        );
192        let mut reordered = first.clone();
193        reordered.posts.reverse();
194        reordered.assets.reverse();
195        reordered.total_bytes = u64::MAX;
196
197        assert_eq!(first.digest(), first.clone().digest());
198        assert_eq!(first.digest(), reordered.digest());
199    }
200
201    #[test]
202    fn digest_binds_publication_path_and_exact_bytes() {
203        let original = fixture().digest();
204        let mut changed_path = fixture();
205        changed_path.publication.path = LogicalContentPath::new("settings/publication.toml");
206        let mut changed_bytes = fixture();
207        changed_bytes.publication.source = "publication settings\n".into();
208
209        assert_ne!(original, changed_path.digest());
210        assert_ne!(original, changed_bytes.digest());
211    }
212
213    #[test]
214    fn digest_binds_post_path_collection_exact_bytes_and_cardinality() {
215        let original = fixture().digest();
216        let mut changed_path = fixture();
217        changed_path.posts[0].path = LogicalContentPath::new("posts/renamed.md");
218        let mut changed_collection = fixture();
219        changed_collection.posts[0].collection = PostCollection::Drafts;
220        let mut changed_bytes = fixture();
221        changed_bytes.posts[0].source = "first post\n".into();
222        let mut removed = fixture();
223        removed.posts.pop();
224
225        for changed in [changed_path, changed_collection, changed_bytes, removed] {
226            assert_ne!(original, changed.digest());
227        }
228    }
229
230    #[test]
231    fn digest_binds_asset_path_exact_bytes_and_cardinality() {
232        let original = fixture().digest();
233        let mut changed_path = fixture();
234        changed_path.assets[0].path = LogicalAssetPath::parse("assets/renamed.bin").unwrap();
235        let mut changed_bytes = fixture();
236        changed_bytes.assets[0].bytes = std::sync::Arc::from(b"first asset\n".as_slice());
237        let mut removed = fixture();
238        removed.assets.pop();
239
240        for changed in [changed_path, changed_bytes, removed] {
241            assert_ne!(original, changed.digest());
242        }
243    }
244
245    #[test]
246    fn length_framing_prevents_adjacent_field_ambiguity() {
247        let first = DiscoveredContentTree::new(
248            publication("ab", "c".to_owned()),
249            Vec::new(),
250            Vec::new(),
251            3,
252        );
253        let second = DiscoveredContentTree::new(
254            publication("a", "bc".to_owned()),
255            Vec::new(),
256            Vec::new(),
257            3,
258        );
259
260        assert_ne!(first.digest(), second.digest());
261    }
262
263    #[test]
264    fn display_uses_the_versioned_content_digest_format() {
265        let digest = fixture().digest();
266        let encoded = digest.to_string();
267        let hex = encoded.strip_prefix(CONTENT_TREE_PREFIX).unwrap();
268
269        assert_eq!(digest.as_bytes().len(), 32);
270        assert_eq!(hex.len(), 64);
271        assert!(
272            hex.bytes()
273                .all(|byte| byte.is_ascii_digit() || (b'a'..=b'f').contains(&byte))
274        );
275        assert_eq!(ContentTreeDigest::parse(&encoded).unwrap(), digest);
276        assert_eq!(encoded.parse::<ContentTreeDigest>().unwrap(), digest);
277        assert_eq!(
278            ContentTreeDigest::parse(&encoded.to_uppercase()),
279            Err(ContentTreeDigestParseError::InvalidPrefix)
280        );
281        assert_eq!(
282            ContentTreeDigest::parse(&encoded[..encoded.len() - 1]),
283            Err(ContentTreeDigestParseError::InvalidLength)
284        );
285        assert_eq!(
286            ContentTreeDigest::parse(&format!("{CONTENT_TREE_PREFIX}{}", "gg".repeat(32))),
287            Err(ContentTreeDigestParseError::InvalidEncoding)
288        );
289    }
290}
markdown_compiler/tree_digest.rs

markdown_compiler/
tree_digest.rs
