supercov_engine/
interned.rs

1//! Ids a coverage report names over and over, stored once.
2//!
3//! A report says, for every obligation and line, which tests and phases
4//! reached it, and for every test and phase, what it reached. On a
5//! 3,900-test run that is some twenty million names drawn from a few tens of
6//! thousands of distinct ones -- test ids, phase ids, obligation ids and file
7//! paths. Held as owned strings each was its own allocation of about a
8//! hundred bytes, and analysing that run peaked above 4 GB. An `Id` is a
9//! shared pointer to one copy: sixteen bytes in a list, and a clone is a
10//! count. It serializes as the string it holds, so nothing a report writes
11//! changes.
12
13use std::{
14    borrow::Borrow,
15    collections::{HashMap, HashSet},
16    fmt,
17    hash::{BuildHasherDefault, Hash, Hasher},
18    ops::Deref,
19    sync::Arc,
20};
21
22/// The hash an analysis's own maps of ids use: Fx, the multiply-rotate hash
23/// rustc uses for its tables. The standard SipHash resists keys chosen to
24/// collide, which costs a run's millions of lookups of its own ids -- test,
25/// phase and obligation names it made itself -- and buys them nothing.
26#[derive(Default, Clone, Copy)]
27pub struct FxHasher {
28    hash: u64,
29}
30
31const FX_SEED: u64 = 0x51_7c_c1_b7_27_22_0a_95;
32
33impl FxHasher {
34    fn add(&mut self, word: u64) {
35        self.hash = (self.hash.rotate_left(5) ^ word).wrapping_mul(FX_SEED);
36    }
37}
38
39impl Hasher for FxHasher {
40    fn write(&mut self, bytes: &[u8]) {
41        let mut chunks = bytes.chunks_exact(8);
42        for chunk in &mut chunks {
43            self.add(u64::from_le_bytes(chunk.try_into().expect("eight bytes")));
44        }
45        let rest = chunks.remainder();
46        if !rest.is_empty() {
47            let mut word = [0_u8; 8];
48            word[..rest.len()].copy_from_slice(rest);
49            self.add(u64::from_le_bytes(word) ^ ((rest.len() as u64) << 56));
50        }
51    }
52
53    fn write_u8(&mut self, value: u8) {
54        self.add(u64::from(value));
55    }
56
57    fn write_u32(&mut self, value: u32) {
58        self.add(u64::from(value));
59    }
60
61    fn write_u64(&mut self, value: u64) {
62        self.add(value);
63    }
64
65    fn write_usize(&mut self, value: usize) {
66        self.add(value as u64);
67    }
68
69    fn finish(&self) -> u64 {
70        self.hash
71    }
72}
73
74pub type FastHash = BuildHasherDefault<FxHasher>;
75pub type FastMap<K, V> = HashMap<K, V, FastHash>;
76pub type FastSet<T> = HashSet<T, FastHash>;
77
78use serde::{Serialize, Serializer};
79
80#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
81pub struct Id(Arc<str>);
82
83impl Id {
84    pub fn as_str(&self) -> &str {
85        &self.0
86    }
87}
88
89impl Deref for Id {
90    type Target = str;
91    fn deref(&self) -> &str {
92        &self.0
93    }
94}
95
96impl Borrow<str> for Id {
97    fn borrow(&self) -> &str {
98        &self.0
99    }
100}
101
102impl AsRef<str> for Id {
103    fn as_ref(&self) -> &str {
104        &self.0
105    }
106}
107
108// Hashes as the text it holds, so a set of ids can be searched with a `&str`.
109impl Hash for Id {
110    fn hash<H: Hasher>(&self, state: &mut H) {
111        (*self.0).hash(state);
112    }
113}
114
115impl fmt::Debug for Id {
116    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
117        fmt::Debug::fmt(&*self.0, formatter)
118    }
119}
120
121impl fmt::Display for Id {
122    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
123        fmt::Display::fmt(&*self.0, formatter)
124    }
125}
126
127impl Serialize for Id {
128    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
129        serializer.serialize_str(&self.0)
130    }
131}
132
133impl From<&str> for Id {
134    fn from(value: &str) -> Self {
135        Self(Arc::from(value))
136    }
137}
138
139impl From<String> for Id {
140    fn from(value: String) -> Self {
141        Self(Arc::from(value))
142    }
143}
144
145impl From<&String> for Id {
146    fn from(value: &String) -> Self {
147        Self(Arc::from(value.as_str()))
148    }
149}
150
151impl From<Id> for String {
152    fn from(value: Id) -> Self {
153        value.0.to_string()
154    }
155}
156
157impl PartialEq<str> for Id {
158    fn eq(&self, other: &str) -> bool {
159        &*self.0 == other
160    }
161}
162
163impl PartialEq<&str> for Id {
164    fn eq(&self, other: &&str) -> bool {
165        &*self.0 == *other
166    }
167}
168
169impl PartialEq<String> for Id {
170    fn eq(&self, other: &String) -> bool {
171        &*self.0 == other.as_str()
172    }
173}
174
175impl PartialEq<Id> for String {
176    fn eq(&self, other: &Id) -> bool {
177        self.as_str() == &*other.0
178    }
179}
180
181impl PartialEq<Id> for str {
182    fn eq(&self, other: &Id) -> bool {
183        self == &*other.0
184    }
185}
186
187impl PartialEq<Id> for &str {
188    fn eq(&self, other: &Id) -> bool {
189        *self == &*other.0
190    }
191}
192
193#[cfg(test)]
194impl Id {
195    /// Whether two ids hold one copy of their text, which is the point of them.
196    pub(crate) fn same_allocation(&self, other: &Id) -> bool {
197        Arc::ptr_eq(&self.0, &other.0)
198    }
199}
200
201/// One `Id` per distinct text, for the life of one view.
202#[derive(Default)]
203pub struct Interner {
204    ids: FastSet<Id>,
205}
206
207impl Interner {
208    pub fn id(&mut self, text: &str) -> Id {
209        if let Some(id) = self.ids.get(text) {
210            return id.clone();
211        }
212        let id = Id::from(text);
213        self.ids.insert(id.clone());
214        id
215    }
216}
217
218#[cfg(test)]
219mod tests {
220    use super::*;
221
222    /// Texts a report holds, including the awkward ones: shared prefixes,
223    /// case, the empty string, escapes JSON must write, and text outside ASCII.
224    const TEXTS: [&str; 14] = [
225        "",
226        "a",
227        "A",
228        "ab",
229        "a/b",
230        "h11/tests/test_x.py::test_b[2-50]",
231        "h11/tests/test_x.py::test_b[10-50]",
232        "h11/tests/test_x.py::test_b",
233        "python-phase:9",
234        "python-phase:10",
235        "quote \" and backslash \\",
236        "tab\tnewline\ncontrol\u{1}",
237        "unicodé ✓ 名前",
238        "z",
239    ];
240
241    #[test]
242    fn ids_order_hash_and_serialize_exactly_as_their_strings() {
243        use std::collections::{BTreeSet, HashSet};
244        let mut interner = Interner::default();
245        let ids = TEXTS
246            .iter()
247            .map(|text| interner.id(text))
248            .collect::<Vec<_>>();
249        // Ordering: every pair compares as its strings do, so a set of ids
250        // iterates in the order a set of strings did.
251        for (left, left_text) in ids.iter().zip(TEXTS) {
252            for (right, right_text) in ids.iter().zip(TEXTS) {
253                assert_eq!(
254                    left.cmp(right),
255                    left_text.cmp(right_text),
256                    "{left_text:?} vs {right_text:?}"
257                );
258            }
259        }
260        let by_id = ids.iter().cloned().collect::<BTreeSet<_>>();
261        let by_text = TEXTS
262            .iter()
263            .map(|text| text.to_string())
264            .collect::<BTreeSet<_>>();
265        assert_eq!(
266            by_id.iter().map(|id| id.as_str()).collect::<Vec<_>>(),
267            by_text.iter().map(String::as_str).collect::<Vec<_>>()
268        );
269        // Lookup by text, in hashed and ordered sets alike.
270        let hashed = ids.iter().cloned().collect::<HashSet<_>>();
271        for text in TEXTS {
272            assert!(hashed.contains(text), "{text:?}");
273            assert!(by_id.contains(text), "{text:?}");
274        }
275        assert!(!hashed.contains("absent"));
276        // Serialization, alone and in a list, is the string's own.
277        for (id, text) in ids.iter().zip(TEXTS) {
278            assert_eq!(
279                serde_json::to_string(id).unwrap(),
280                serde_json::to_string(text).unwrap()
281            );
282            assert_eq!(id.to_string(), text);
283            assert_eq!(format!("{id:?}"), format!("{text:?}"));
284            let owned = String::from(text);
285            assert_eq!(*id, text);
286            assert_eq!(*id, owned);
287            assert_eq!(owned, *id);
288            assert_eq!(text, *id);
289        }
290        assert_eq!(
291            serde_json::to_string(&ids).unwrap(),
292            serde_json::to_string(&TEXTS).unwrap()
293        );
294    }
295
296    #[test]
297    fn an_id_is_the_text_it_holds_everywhere_it_is_seen() {
298        let mut interner = Interner::default();
299        let first = interner.id("h11/tests/test_x.py::test_a");
300        let again = interner.id("h11/tests/test_x.py::test_a");
301        assert!(
302            Arc::ptr_eq(&first.0, &again.0),
303            "one copy per distinct text"
304        );
305        assert_eq!(first, "h11/tests/test_x.py::test_a");
306        assert_eq!(
307            serde_json::to_string(&vec![first.clone()]).unwrap(),
308            r#"["h11/tests/test_x.py::test_a"]"#
309        );
310        let mut set = std::collections::BTreeSet::new();
311        set.insert(interner.id("b"));
312        set.insert(interner.id("a"));
313        assert!(set.contains("a"), "found by text");
314        assert_eq!(
315            set.into_iter().map(String::from).collect::<Vec<_>>(),
316            ["a", "b"]
317        );
318    }
319}
supercov_engine/interned.rs

supercov_engine/
interned.rs
