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;