dataflow_rs/program/
fingerprint.rs

1//! Workflow fingerprints: FNV-1a 64 over the operator names and the data
2//! keys a workflow's expressions use.
3//!
4//! The classification is made by `Checks::expr`. Every single-key object is
5//! classified by its key: an operator when the key names an entry of the
6//! engine's vocabulary, data when it does not start with the escape, and
7//! nothing when it does. The encoding is, with `ops` and `data` sorted and
8//! deduplicated:
9//!
10//! ```text
11//! for name in ops:  (name.len() as u32).to_le_bytes() ++ name.as_bytes()
12//! 0xFFFF_FFFFu32.to_le_bytes()
13//! for key in data:  (key.len() as u32).to_le_bytes() ++ key.as_bytes()
14//! ```
15
16use std::collections::BTreeSet;
17use std::fmt;
18use std::str::FromStr;
19
20const OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
21const PRIME: u64 = 0x0000_0100_0000_01b3;
22const PREFIX: &str = "v1:";
23
24/// Feeds `bytes` into an FNV-1a 64 state `h`.
25fn fnv1a_step(h: u64, bytes: &[u8]) -> u64 {
26    bytes
27        .iter()
28        .fold(h, |h, b| (h ^ u64::from(*b)).wrapping_mul(PRIME))
29}
30
31#[cfg(test)]
32fn fnv1a(bytes: &[u8]) -> u64 {
33    fnv1a_step(OFFSET, bytes)
34}
35
36/// The bytes the hash is taken over.
37#[cfg(test)]
38fn encode(ops: &BTreeSet<String>, data: &BTreeSet<String>) -> Vec<u8> {
39    fn put(out: &mut Vec<u8>, s: &str) {
40        let len = u32::try_from(s.len()).expect("a key is shorter than 2^32 bytes");
41        out.extend_from_slice(&len.to_le_bytes());
42        out.extend_from_slice(s.as_bytes());
43    }
44    let mut out = Vec::new();
45    ops.iter().for_each(|s| put(&mut out, s));
46    out.extend_from_slice(&u32::MAX.to_le_bytes());
47    data.iter().for_each(|s| put(&mut out, s));
48    out
49}
50
51/// A workflow's fingerprint: which operators and data keys its expressions
52/// use, and nothing about values, order or ids. It shows as `v1:` and 16 hex
53/// digits, and the same workflow under the same vocabulary has the same one
54/// in every process and release.
55#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
56pub struct Fingerprint(u64);
57
58impl Fingerprint {
59    /// The fingerprint of the two sets.
60    pub(crate) fn of(ops: &BTreeSet<String>, data: &BTreeSet<String>) -> Self {
61        fn put(h: u64, s: &str) -> u64 {
62            let len = u32::try_from(s.len()).expect("a key is shorter than 2^32 bytes");
63            let h = fnv1a_step(h, &len.to_le_bytes());
64            fnv1a_step(h, s.as_bytes())
65        }
66        let h = ops.iter().fold(OFFSET, |h, s| put(h, s));
67        let h = fnv1a_step(h, &u32::MAX.to_le_bytes());
68        let h = data.iter().fold(h, |h, s| put(h, s));
69        Self(h)
70    }
71}
72
73impl fmt::Display for Fingerprint {
74    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
75        write!(f, "{PREFIX}{:016x}", self.0)
76    }
77}
78
79/// A string that is not a [`Fingerprint`].
80#[derive(Clone, Debug, PartialEq, Eq)]
81pub struct ParseFingerprintError(String);
82
83impl fmt::Display for ParseFingerprintError {
84    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
85        write!(
86            f,
87            "`{}` is not a fingerprint: expected `v1:` and 16 hex digits",
88            self.0
89        )
90    }
91}
92
93impl std::error::Error for ParseFingerprintError {}
94
95impl FromStr for Fingerprint {
96    type Err = ParseFingerprintError;
97
98    fn from_str(s: &str) -> Result<Self, Self::Err> {
99        let bad = || ParseFingerprintError(s.to_owned());
100        let hex = s.strip_prefix(PREFIX).ok_or_else(bad)?;
101        if hex.len() != 16 || !hex.bytes().all(|b| b.is_ascii_hexdigit()) {
102            return Err(bad());
103        }
104        u64::from_str_radix(hex, 16).map(Self).map_err(|_| bad())
105    }
106}
107
108#[cfg(test)]
109mod tests {
110    use super::*;
111
112    #[test]
113    fn fnv1a_matches_the_standard_vectors() {
114        assert_eq!(fnv1a(b""), 0xcbf2_9ce4_8422_2325);
115        assert_eq!(fnv1a(b"a"), 0xaf63_dc4c_8601_ec8c);
116        assert_eq!(fnv1a(b"foobar"), 0x8594_4171_f739_67e8);
117    }
118
119    #[test]
120    fn the_encoding_is_lengths_names_a_separator_and_keys() {
121        let set = |s: &str| BTreeSet::from([s.to_owned()]);
122        let mut want = vec![3, 0, 0, 0, b'v', b'a', b'r', 255, 255, 255, 255];
123        want.extend([3, 0, 0, 0, b'o', b'u', b't']);
124        assert_eq!(encode(&set("var"), &set("out")), want);
125    }
126}
dataflow_rs/program/fingerprint.rs

dataflow_rs/program/
fingerprint.rs
