Skip to main content

decl_lang/
serialization_diagnostics.rs

1//! Feature-only census of the value graph that canonical serialization emits.
2//!
3//! [`census`] visits the values `Engine::serialize` would append, in the same
4//! order and under the same omission rules, and counts them. It evaluates
5//! nothing: a raw-document `PreVal` is counted and not entered, so whatever it
6//! would produce is absent from every other count. The census retains no
7//! value, scope or engine, and it is never called by the serializer itself.
8//!
9//! The module has its own `serialization-census` Cargo feature, which
10//! `runtime-diagnostics` implies. Enabled alone it compiles none of the
11//! evaluation hooks, whose recording allocates, so the engine whose text
12//! placement it observes is the ordinary one.
13//!
14//! For text it also records where the two allocations behind a [`SharedText`]
15//! live, because serialization reaches the characters through the descriptor:
16//! the distance from each descriptor to its characters, and the distances
17//! between the descriptors and between the characters of consecutively emitted
18//! text values. A descriptor shared by many values is counted once in
19//! [`TextCensus::distinct_descriptors`]; characters shared by several
20//! descriptors are counted once in [`TextCensus::distinct_characters`].
21//!
22//! Addresses are observations of this process's allocator at the time of the
23//! call. They are not stable across runs, they say nothing about cache or page
24//! state, and a distance is not a cost. Map keys, member names and raw-object
25//! keys are borrowed `String` text without a descriptor; they are counted in
26//! [`KeyCensus`] and carry no placement record. The census allocates two
27//! address sets proportional to the distinct text allocations it meets.
28
29use crate::semantics::{rec_members, MKind, SharedText, SlotState, Value};
30use serde::Serialize;
31use std::collections::HashSet;
32use std::rc::Rc;
33
34/// Upper bound of [`Distances::up_to_64`]: one cache line.
35pub const CACHE_LINE_BYTES: usize = 64;
36/// Upper bound of [`Distances::up_to_4_kib`].
37pub const SMALL_PAGE_BYTES: usize = 4 * 1024;
38/// Upper bound of [`Distances::up_to_16_kib`]: one page on Apple silicon.
39pub const LARGE_PAGE_BYTES: usize = 16 * 1024;
40/// Upper bound of [`Distances::up_to_2_mib`].
41pub const SEGMENT_BYTES: usize = 2 * 1024 * 1024;
42
43/// Absolute address distances, each counted in exactly one bucket.
44#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize)]
45pub struct Distances {
46    /// Distances recorded; the five buckets sum to this.
47    pub pairs: u64,
48    /// At most [`CACHE_LINE_BYTES`] apart, including zero.
49    pub up_to_64: u64,
50    /// Farther than a cache line and at most [`SMALL_PAGE_BYTES`] apart.
51    pub up_to_4_kib: u64,
52    /// Farther than that and at most [`LARGE_PAGE_BYTES`] apart.
53    pub up_to_16_kib: u64,
54    /// Farther than that and at most [`SEGMENT_BYTES`] apart.
55    pub up_to_2_mib: u64,
56    /// Farther than [`SEGMENT_BYTES`] apart.
57    pub beyond_2_mib: u64,
58    /// Saturating sum of every recorded distance.
59    pub total_bytes: u64,
60}
61
62impl Distances {
63    fn record(&mut self, a: usize, b: usize) {
64        let distance = a.abs_diff(b);
65        self.pairs += 1;
66        self.total_bytes = self.total_bytes.saturating_add(distance as u64);
67        let bucket = if distance <= CACHE_LINE_BYTES {
68            &mut self.up_to_64
69        } else if distance <= SMALL_PAGE_BYTES {
70            &mut self.up_to_4_kib
71        } else if distance <= LARGE_PAGE_BYTES {
72            &mut self.up_to_16_kib
73        } else if distance <= SEGMENT_BYTES {
74            &mut self.up_to_2_mib
75        } else {
76            &mut self.beyond_2_mib
77        };
78        *bucket += 1;
79    }
80}
81
82/// Text values in emission order, and the placement of their two allocations.
83#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize)]
84pub struct TextCensus {
85    /// Emitted `Value::Str` occurrences.
86    pub values: u64,
87    /// Their UTF-8 bytes before escaping, every occurrence counted.
88    pub bytes: u64,
89    /// Distinct descriptor allocations among those occurrences.
90    pub distinct_descriptors: u64,
91    /// Distinct character allocations among those occurrences.
92    pub distinct_characters: u64,
93    /// From each occurrence's descriptor to its characters.
94    pub descriptor_to_characters: Distances,
95    /// Between the descriptors of consecutively emitted occurrences.
96    pub consecutive_descriptors: Distances,
97    /// Between the characters of consecutively emitted occurrences.
98    pub consecutive_characters: Distances,
99}
100
101/// Emitted map keys, record member names and raw-object keys.
102#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize)]
103pub struct KeyCensus {
104    /// Keys written before an emitted value.
105    pub count: u64,
106    /// Their UTF-8 bytes before escaping.
107    pub bytes: u64,
108}
109
110/// Visited values by the form serialization gives them.
111#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize)]
112pub struct ValueCounts {
113    /// `null` values.
114    pub nulls: u64,
115    /// Boolean values.
116    pub booleans: u64,
117    /// Integer values.
118    pub integers: u64,
119    /// Float values.
120    pub floats: u64,
121    /// Text values; [`TextCensus`] describes them.
122    pub text: u64,
123    /// Quantities, each emitted as a value-and-unit object.
124    pub quantities: u64,
125    /// References, each emitted as freshly formatted path text.
126    pub references: u64,
127    /// Typed arrays.
128    pub arrays: u64,
129    /// Typed maps.
130    pub maps: u64,
131    /// Records.
132    pub records: u64,
133    /// Raw-document arrays.
134    pub raw_arrays: u64,
135    /// Raw-document objects.
136    pub raw_objects: u64,
137    /// Raw-document `PreVal` positions, counted and not evaluated or entered.
138    pub unevaluated_raw_values: u64,
139    /// Values that append nothing: absent, undefined or without a JSON form.
140    pub omitted: u64,
141    /// Omitted values in raw-document positions, which serialize as `null`.
142    pub raw_null_substitutions: u64,
143}
144
145/// What one canonical serialization of a value visits.
146#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize)]
147pub struct SerializationCensus {
148    /// Visited values by emitted form.
149    pub values: ValueCounts,
150    /// Emitted keys and member names.
151    pub keys: KeyCensus,
152    /// Emitted text values and their placement.
153    pub text: TextCensus,
154    /// Deepest container nesting; a scalar root is depth zero.
155    pub max_depth: u32,
156}
157
158/// Count what `Engine::serialize(value, _, settable_only)` would emit.
159///
160/// The traversal borrows each container exactly as the serializer does and
161/// evaluates nothing. It must not run while a container of `value` is mutably
162/// borrowed.
163pub fn census(value: &Value, settable_only: bool) -> SerializationCensus {
164    let mut walker = Walker::default();
165    walker.typed(value, settable_only);
166    walker.census.text.distinct_descriptors = walker.descriptors.len() as u64;
167    walker.census.text.distinct_characters = walker.characters.len() as u64;
168    walker.census
169}
170
171#[derive(Default)]
172struct Walker {
173    census: SerializationCensus,
174    descriptors: HashSet<usize>,
175    characters: HashSet<usize>,
176    previous: Option<(usize, usize)>,
177    depth: u32,
178}
179
180impl Walker {
181    fn text(&mut self, text: &SharedText) {
182        // `as_rc` borrows the character owner stored inside the descriptor
183        // allocation, so its address identifies that descriptor.
184        let descriptor = text.as_rc() as *const Rc<str> as usize;
185        let characters = text.as_ptr() as usize;
186        let record = &mut self.census.text;
187        record.values += 1;
188        record.bytes += text.len() as u64;
189        record
190            .descriptor_to_characters
191            .record(descriptor, characters);
192        if let Some((descriptor_before, characters_before)) = self.previous {
193            record
194                .consecutive_descriptors
195                .record(descriptor_before, descriptor);
196            record
197                .consecutive_characters
198                .record(characters_before, characters);
199        }
200        self.previous = Some((descriptor, characters));
201        self.descriptors.insert(descriptor);
202        self.characters.insert(characters);
203    }
204
205    fn key(&mut self, key: &str) {
206        self.census.keys.count += 1;
207        self.census.keys.bytes += key.len() as u64;
208    }
209
210    fn enter(&mut self) {
211        self.depth += 1;
212        self.census.max_depth = self.census.max_depth.max(self.depth);
213    }
214
215    // Mirrors `Engine::go`: false means the value appends nothing, so its
216    // container omits the member or item and writes no key for it.
217    fn typed(&mut self, value: &Value, settable_only: bool) -> bool {
218        let counts = &mut self.census.values;
219        match value {
220            Value::Null => counts.nulls += 1,
221            Value::Bool(_) => counts.booleans += 1,
222            Value::Int(_) => counts.integers += 1,
223            Value::Float(_) => counts.floats += 1,
224            Value::Str(text) => {
225                counts.text += 1;
226                self.text(text);
227            }
228            Value::Q(_) => counts.quantities += 1,
229            Value::Ref(_) => counts.references += 1,
230            Value::Arr(array) => {
231                counts.arrays += 1;
232                self.enter();
233                for item in &array.borrow().items {
234                    self.typed(item, settable_only);
235                }
236                self.depth -= 1;
237            }
238            Value::Map(map) => {
239                counts.maps += 1;
240                self.enter();
241                for (key, item) in &map.borrow().entries {
242                    if self.typed(item, settable_only) {
243                        self.key(key);
244                    }
245                }
246                self.depth -= 1;
247            }
248            Value::Rec(record) => {
249                counts.records += 1;
250                self.enter();
251                let record = record.borrow();
252                let mut done: HashSet<&str> = HashSet::new();
253                for name in record.entry_order.iter() {
254                    done.insert(name);
255                    if let Some(extra) = record.extra(name) {
256                        self.key(name);
257                        self.raw(extra);
258                        continue;
259                    }
260                    let Some(slot) = record.slot(name) else {
261                        continue;
262                    };
263                    if matches!(slot.state, SlotState::Invalid | SlotState::Absent)
264                        || slot.kind == MKind::Der
265                    {
266                        continue;
267                    }
268                    if self.typed(&slot.value, settable_only) {
269                        self.key(name);
270                    }
271                }
272                for member in rec_members(&record.rt).iter() {
273                    if done.contains(member.name.as_str()) && member.kind != MKind::Der {
274                        continue;
275                    }
276                    if settable_only && member.kind == MKind::Der {
277                        continue;
278                    }
279                    let Some(slot) = record.slot(&member.name) else {
280                        continue;
281                    };
282                    if slot.hidden
283                        || matches!(
284                            slot.state,
285                            SlotState::Invalid
286                                | SlotState::Absent
287                                | SlotState::Unforced
288                                | SlotState::Deferred
289                        )
290                    {
291                        continue;
292                    }
293                    if self.typed(&slot.value, settable_only) {
294                        self.key(&member.name);
295                    }
296                }
297                self.depth -= 1;
298            }
299            Value::JObj(_) | Value::JArr(_) => self.raw(value),
300            _ => {
301                counts.omitted += 1;
302                return false;
303            }
304        }
305        true
306    }
307
308    // Mirrors `Engine::raw_json`, except that a `PreVal` is never evaluated.
309    fn raw(&mut self, value: &Value) {
310        match value {
311            Value::JArr(items) => {
312                self.census.values.raw_arrays += 1;
313                self.enter();
314                for item in items.iter() {
315                    self.raw(item);
316                }
317                self.depth -= 1;
318            }
319            Value::JObj(entries) => {
320                self.census.values.raw_objects += 1;
321                self.enter();
322                for (key, item) in entries.iter() {
323                    self.key(key);
324                    self.raw(item);
325                }
326                self.depth -= 1;
327            }
328            Value::PreVal(_) => self.census.values.unevaluated_raw_values += 1,
329            other => {
330                if !self.typed(other, false) {
331                    self.census.values.raw_null_substitutions += 1;
332                }
333            }
334        }
335    }
336}
337
338#[cfg(test)]
339#[path = "../tests/private/serialization_diagnostics_test.rs"]
340mod tests;