1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

use crate::{KeyLookup, Packed};

/// Metadata about a `TreeKey` namespace.
///
/// Metadata includes paths that may be [`crate::Traversal::Absent`] at runtime.
#[non_exhaustive]
#[derive(Default, Debug, Copy, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct Metadata {
    /// The maximum length of a path in bytes.
    ///
    /// This is the exact maximum of the length of the concatenation of the node names
    /// in a [`crate::Path`] excluding the separators. See [`Self::max_length()`] for
    /// the maximum length including separators.
    pub max_length: usize,

    /// The maximum key depth.
    ///
    /// This is equal to the exact maximum number of path hierarchy separators.
    /// It's the exact maximum number of key indices.
    pub max_depth: usize,

    /// The exact total number of keys.
    pub count: usize,

    /// The maximum number of bits (see [`crate::Packed`])
    pub max_bits: u32,
}

impl Metadata {
    /// Add separator length to the maximum path length.
    ///
    /// To obtain an upper bound on the maximum length of all paths
    /// including separators, this adds `max_depth*separator_length`.
    #[inline]
    pub fn max_length(&self, separator: &str) -> usize {
        self.max_length + self.max_depth * separator.len()
    }
}

/// Capability to be walked through a `TreeKey` using `traverse_all()`.
pub trait Walk: Sized {
    /// Error type for `merge()`
    type Error;

    /// Return the walk starting point for an an empty internal node
    fn internal() -> Self;

    /// Return the walk starting point for a single leaf node
    fn leaf() -> Self;

    /// Merge node metadata into self.
    ///
    /// # Args
    /// * `walk`: The walk of the node to merge.
    /// * `index`: Either the node index in case of a single node
    ///   or `None`, in case of `lookup.len` nodes of homogeneous type.
    /// * `lookup`: The namespace the node(s) are in.
    fn merge(
        self,
        walk: &Self,
        index: Option<usize>,
        lookup: &KeyLookup,
    ) -> Result<Self, Self::Error>;
}

impl Walk for Metadata {
    type Error = core::convert::Infallible;

    #[inline]
    fn internal() -> Self {
        Default::default()
    }

    #[inline]
    fn leaf() -> Self {
        Self {
            count: 1,
            ..Default::default()
        }
    }

    #[inline]
    fn merge(
        mut self,
        meta: &Self,
        index: Option<usize>,
        lookup: &KeyLookup,
    ) -> Result<Self, Self::Error> {
        let (ident_len, count) = match index {
            None => (
                // homogeneous [meta; len]
                match lookup.names {
                    Some(names) => names.iter().map(|n| n.len()).max().unwrap_or_default(),
                    None => lookup.len.ilog10() as usize + 1,
                },
                lookup.len.get(),
            ),
            Some(index) => (
                // one meta at index
                match lookup.names {
                    Some(names) => names[index].len(),
                    None => index.checked_ilog10().unwrap_or_default() as usize + 1,
                },
                1,
            ),
        };
        self.max_depth = self.max_depth.max(1 + meta.max_depth);
        self.max_length = self.max_length.max(ident_len + meta.max_length);
        debug_assert_ne!(meta.count, 0);
        self.count += count * meta.count;
        self.max_bits = self
            .max_bits
            .max(Packed::bits_for(lookup.len.get() - 1) + meta.max_bits);
        Ok(self)
    }
}