devset_core/
digest.rs

1//! Content digests and file fingerprints.
2
3use derive_more::{Display, FromStr};
4use serde::{Deserialize, Serialize};
5use serde_with::{DeserializeFromStr, SerializeDisplay};
6
7/// Leading bytes git inspects to decide a file is binary.
8const BINARY_SNIFF: usize = 8000;
9
10/// UTF-8 byte order mark.
11pub(crate) const BOM: &[u8] = b"\xEF\xBB\xBF";
12
13/// A BLAKE3 digest, written and serialized as lowercase hex.
14#[derive(
15    Clone,
16    Copy,
17    PartialEq,
18    Eq,
19    Hash,
20    Display,
21    derive_more::Debug,
22    FromStr,
23    SerializeDisplay,
24    DeserializeFromStr,
25)]
26#[debug("{_0}")]
27pub struct Digest(blake3::Hash);
28
29impl Digest {
30    /// Digest of `bytes`.
31    #[must_use]
32    pub fn of(bytes: &[u8]) -> Self {
33        Self(blake3::hash(bytes))
34    }
35
36    /// Wraps a finished hash.
37    pub(crate) const fn new(hash: blake3::Hash) -> Self {
38        Self(hash)
39    }
40
41    /// Raw digest bytes.
42    #[must_use]
43    pub const fn as_bytes(&self) -> &[u8; 32] {
44        self.0.as_bytes()
45    }
46}
47
48/// Exact and canonical digests of one file; see [`Fingerprint::of`].
49#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
50pub struct Fingerprint {
51    /// Digest of the bytes as they are.
52    pub exact: Digest,
53    /// Digest of the canonical form.
54    pub canonical: Digest,
55}
56
57impl Fingerprint {
58    /// Fingerprints `bytes`, reading them once.
59    ///
60    /// The canonical form drops a UTF-8 BOM, strips trailing whitespace from every line, drops
61    /// trailing blank lines and ends in exactly one `\n`. Binary content, git's test of a NUL in
62    /// the first 8000 bytes, is its own canonical form.
63    #[must_use]
64    pub fn of(bytes: &[u8]) -> Self {
65        let exact = Digest::of(bytes);
66        let canonical = if is_binary(bytes) {
67            exact
68        } else {
69            let mut hasher = blake3::Hasher::new();
70            canonical(bytes, |part| {
71                hasher.update(part);
72            });
73            Digest(hasher.finalize())
74        };
75        Self { exact, canonical }
76    }
77
78    /// Whether `self` and `other` differ at most cosmetically.
79    #[must_use]
80    pub fn same_content(&self, other: &Self) -> bool {
81        self.canonical == other.canonical
82    }
83}
84
85/// Git's binary heuristic.
86pub(crate) fn is_binary(bytes: &[u8]) -> bool {
87    bytes.get(..BINARY_SNIFF).unwrap_or(bytes).contains(&0)
88}
89
90/// Feeds the canonical form of text `bytes` to `emit` as borrowed slices; nothing is copied.
91fn canonical<F: FnMut(&[u8])>(bytes: &[u8], mut emit: F) {
92    let text = bytes.strip_prefix(BOM).unwrap_or(bytes);
93    let mut blank = 0_usize;
94    let mut started = false;
95    for line in text.split(|&b| b == b'\n').map(<[u8]>::trim_ascii_end) {
96        if line.is_empty() {
97            blank = blank.saturating_add(1);
98            continue;
99        }
100        if started {
101            emit(b"\n");
102        }
103        for _ in 0..blank {
104            emit(b"\n");
105        }
106        emit(line);
107        started = true;
108        blank = 0;
109    }
110    if started {
111        emit(b"\n");
112    }
113}
114
115#[cfg(test)]
116mod tests {
117    use proptest::prelude::*;
118
119    use super::{Fingerprint, canonical};
120
121    fn canon(bytes: &[u8]) -> Vec<u8> {
122        let mut out = Vec::new();
123        canonical(bytes, |part| out.extend_from_slice(part));
124        out
125    }
126
127    #[test]
128    fn canonical_form() {
129        for (input, want) in [
130            (&b""[..], &b""[..]),
131            (b" \n\t\n", b""),
132            (b"a", b"a\n"),
133            (b"a\n\n\n", b"a\n"),
134            (b"a  \r\nb\t\r\n", b"a\nb\n"),
135            (b"\xEF\xBB\xBFa\n", b"a\n"),
136            (b"\n\na\n\n b\n", b"\n\na\n\n b\n"),
137            (b"a\rb\n", b"a\rb\n"),
138        ] {
139            assert_eq!(canon(input), want, "input {:?}", String::from_utf8_lossy(input));
140        }
141    }
142
143    #[test]
144    fn binary_is_exact() {
145        let bytes = b"a \0 b  \r\n";
146        let fp = Fingerprint::of(bytes);
147        assert_eq!(fp.exact, fp.canonical, "binary content must not be canonicalized");
148    }
149
150    proptest! {
151        #[test]
152        fn idempotent(text in "[a-z \t\r\n]{0,64}") {
153            let once = canon(text.as_bytes());
154            prop_assert_eq!(canon(&once), once);
155        }
156
157        #[test]
158        fn cosmetic_changes_keep_content(text in "[a-z]{1,8}(\n[a-z ]{0,8}){0,8}") {
159            let noisy = format!("\u{FEFF}{}  \r\n\n\n", text.replace('\n', " \t\r\n"));
160            let (a, b) = (Fingerprint::of(text.as_bytes()), Fingerprint::of(noisy.as_bytes()));
161            prop_assert!(a.same_content(&b), "{text:?} vs {noisy:?}");
162        }
163
164        #[test]
165        fn real_changes_are_seen(
166            (text, at) in "[a-z]{1,16}".prop_flat_map(|t| { let n = t.len(); (Just(t), 0..n) })
167        ) {
168            let mut edited = text.clone().into_bytes();
169            edited[at] = b'Z';
170            let (a, b) = (Fingerprint::of(text.as_bytes()), Fingerprint::of(&edited));
171            prop_assert!(!a.same_content(&b), "{text:?} vs {:?}", String::from_utf8_lossy(&edited));
172        }
173    }
174}
devset_core/digest.rs

devset_core/
digest.rs
