miniconf/
shape.rs

1use core::num::NonZero;
2
3use crate::{Internal, Packed, Schema};
4
5/// Metadata about a `TreeSchema` namespace.
6///
7/// Metadata includes paths that may be [`crate::ValueError::Absent`] at runtime.
8#[non_exhaustive]
9#[derive(Debug, Copy, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
10pub struct Shape {
11    /// The maximum length of a path in bytes.
12    ///
13    /// This is the exact maximum of the length of the concatenation of the node names
14    /// in a [`crate::Path`] excluding the separators. See [`Self::max_length()`] for
15    /// the maximum length including separators.
16    pub max_length: usize,
17
18    /// The maximum node depth.
19    ///
20    /// This is equal to the exact maximum number of path hierarchy separators.
21    /// It's the exact maximum number of key indices.
22    pub max_depth: usize,
23
24    /// The exact total number of leaf nodes.
25    pub count: NonZero<usize>,
26
27    /// The maximum number of bits (see [`crate::Packed`])
28    pub max_bits: u32,
29}
30
31// const a = a.max(b)
32macro_rules! assign_max {
33    ($a:expr, $b:expr) => {{
34        let b = $b;
35        if $a < b {
36            $a = b;
37        }
38    }};
39}
40
41impl Shape {
42    /// Add separator length to the maximum path length.
43    ///
44    /// To obtain an upper bound on the maximum length of all paths
45    /// including separators, this adds `max_depth*separator_length`.
46    #[inline]
47    pub const fn max_length(&self, separator: &str) -> usize {
48        self.max_length + self.max_depth * separator.len()
49    }
50
51    /// Recursively compute Shape for a Schema.
52    pub const fn new(schema: &Schema) -> Self {
53        let mut m = Self {
54            max_depth: 0,
55            max_length: 0,
56            count: NonZero::<usize>::MIN,
57            max_bits: 0,
58        };
59        if let Some(internal) = schema.internal.as_ref() {
60            match internal {
61                Internal::Named(nameds) => {
62                    let bits = Packed::bits_for(nameds.len() - 1);
63                    let mut index = 0;
64                    let mut count = 0;
65                    while index < nameds.len() {
66                        let named = &nameds[index];
67                        let child = Self::new(named.schema);
68                        assign_max!(m.max_depth, 1 + child.max_depth);
69                        assign_max!(m.max_length, named.name.len() + child.max_length);
70                        assign_max!(m.max_bits, bits + child.max_bits);
71                        count += child.count.get();
72                        index += 1;
73                    }
74                    m.count = NonZero::new(count).unwrap();
75                }
76                Internal::Numbered(numbereds) => {
77                    let bits = Packed::bits_for(numbereds.len() - 1);
78                    let mut index = 0;
79                    let mut count = 0;
80                    while index < numbereds.len() {
81                        let numbered = &numbereds[index];
82                        let len = 1 + match index.checked_ilog10() {
83                            None => 0,
84                            Some(len) => len as usize,
85                        };
86                        let child = Self::new(numbered.schema);
87                        assign_max!(m.max_depth, 1 + child.max_depth);
88                        assign_max!(m.max_length, len + child.max_length);
89                        assign_max!(m.max_bits, bits + child.max_bits);
90                        count += child.count.get();
91                        index += 1;
92                    }
93                    m.count = NonZero::new(count).unwrap();
94                }
95                Internal::Homogeneous(homogeneous) => {
96                    m = Self::new(homogeneous.schema);
97                    m.max_depth += 1;
98                    m.max_length += 1 + homogeneous.len.ilog10() as usize;
99                    m.max_bits += Packed::bits_for(homogeneous.len.get() - 1);
100                    m.count = m.count.checked_mul(homogeneous.len).unwrap();
101                }
102            }
103        }
104        m
105    }
106}
miniconf/shape.rs

miniconf/
shape.rs
