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    pub const fn max_length(&self, separator: &str) -> usize {
47        self.max_length + self.max_depth * separator.len()
48    }
49
50    /// Recursively compute Shape for a Schema.
51    pub const fn new(schema: &Schema) -> Self {
52        let mut m = Self {
53            max_depth: 0,
54            max_length: 0,
55            count: NonZero::<usize>::MIN,
56            max_bits: 0,
57        };
58        if let Some(internal) = schema.internal.as_ref() {
59            match internal {
60                Internal::Named(nameds) => {
61                    let bits = Packed::bits_for(nameds.len() - 1);
62                    let mut index = 0;
63                    let mut count = 0;
64                    while index < nameds.len() {
65                        let named = &nameds[index];
66                        let child = Self::new(named.schema);
67                        assign_max!(m.max_depth, 1 + child.max_depth);
68                        assign_max!(m.max_length, named.name.len() + child.max_length);
69                        assign_max!(m.max_bits, bits + child.max_bits);
70                        count += child.count.get();
71                        index += 1;
72                    }
73                    m.count = NonZero::new(count).unwrap();
74                }
75                Internal::Numbered(numbereds) => {
76                    let bits = Packed::bits_for(numbereds.len() - 1);
77                    let mut index = 0;
78                    let mut count = 0;
79                    while index < numbereds.len() {
80                        let numbered = &numbereds[index];
81                        let len = 1 + match index.checked_ilog10() {
82                            None => 0,
83                            Some(len) => len as usize,
84                        };
85                        let child = Self::new(numbered.schema);
86                        assign_max!(m.max_depth, 1 + child.max_depth);
87                        assign_max!(m.max_length, len + child.max_length);
88                        assign_max!(m.max_bits, bits + child.max_bits);
89                        count += child.count.get();
90                        index += 1;
91                    }
92                    m.count = NonZero::new(count).unwrap();
93                }
94                Internal::Homogeneous(homogeneous) => {
95                    m = Self::new(homogeneous.schema);
96                    m.max_depth += 1;
97                    m.max_length += 1 + homogeneous.len.ilog10() as usize;
98                    m.max_bits += Packed::bits_for(homogeneous.len.get() - 1);
99                    m.count = m.count.checked_mul(homogeneous.len).unwrap();
100                }
101            }
102        }
103        m
104    }
105}
miniconf/shape.rs

miniconf/
shape.rs
