miniconf/
node.rs

1use core::{
2    fmt::Write,
3    ops::{Deref, DerefMut},
4};
5
6use serde::{Deserialize, Serialize};
7
8use crate::{Error, IntoKeys, KeysIter, Traversal, TreeKey};
9
10/// Type of a node: leaf or internal
11#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
12pub enum NodeType {
13    /// A leaf node
14    ///
15    /// There are no nodes below this node
16    Leaf,
17
18    /// An internal node
19    ///
20    /// A non-leaf node with one or more leaf nodes below this node
21    Internal,
22}
23
24impl NodeType {
25    /// Whether this node is a leaf
26    #[inline]
27    pub const fn is_leaf(&self) -> bool {
28        matches!(self, Self::Leaf)
29    }
30}
31
32/// Type and depth of a node in a `TreeKey`
33#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
34pub struct Node {
35    /// The node depth
36    ///
37    /// This is the length of the key required to identify it.
38    pub depth: usize,
39
40    /// Leaf or internal
41    pub typ: NodeType,
42}
43
44impl Node {
45    /// The depth
46    #[inline]
47    pub const fn depth(&self) -> usize {
48        self.depth
49    }
50
51    /// The node type
52    #[inline]
53    pub const fn typ(&self) -> NodeType {
54        self.typ
55    }
56
57    /// The node is a leaf node
58    #[inline]
59    pub const fn is_leaf(&self) -> bool {
60        self.typ.is_leaf()
61    }
62
63    /// Create a leaf node
64    #[inline]
65    pub const fn leaf(depth: usize) -> Self {
66        Self {
67            depth,
68            typ: NodeType::Leaf,
69        }
70    }
71
72    /// Create an inernal node
73    #[inline]
74    pub const fn internal(depth: usize) -> Self {
75        Self {
76            depth,
77            typ: NodeType::Internal,
78        }
79    }
80}
81
82impl From<Node> for usize {
83    #[inline]
84    fn from(value: Node) -> Self {
85        value.depth
86    }
87}
88
89/// Map a `TreeKey::traverse_by_key()` `Result` to a `Transcode::transcode()` `Result`.
90impl TryFrom<Result<usize, Error<()>>> for Node {
91    type Error = Traversal;
92
93    #[inline]
94    fn try_from(value: Result<usize, Error<()>>) -> Result<Self, Traversal> {
95        match value {
96            Ok(depth) => Ok(Node::leaf(depth)),
97            Err(Error::Traversal(Traversal::TooShort(depth))) => Ok(Node::internal(depth)),
98            Err(Error::Inner(depth, ())) => Err(Traversal::TooShort(depth)),
99            Err(Error::Traversal(err)) => Err(err),
100            Err(Error::Finalization(())) => unreachable!(),
101        }
102    }
103}
104
105/// Look up an `IntoKeys` in a `TreeKey` and transcode it.
106pub trait Transcode {
107    /// Perform a node lookup of a `K: IntoKeys` on a `M: TreeKey<Y>` and transcode it.
108    ///
109    /// This modifies `self` such that afterwards `Self: IntoKeys` can be used on `M` again.
110    /// It returns a `Node` with node type and depth information.
111    ///
112    /// Returning `Err(Traversal::TooShort(depth))` indicates that there was insufficient
113    /// capacity and a key could not be encoded at the given depth.
114    fn transcode<M, K>(&mut self, keys: K) -> Result<Node, Traversal>
115    where
116        M: TreeKey + ?Sized,
117        K: IntoKeys;
118}
119
120impl<T: Transcode + ?Sized> Transcode for &mut T {
121    fn transcode<M, K>(&mut self, keys: K) -> Result<Node, Traversal>
122    where
123        M: TreeKey + ?Sized,
124        K: IntoKeys,
125    {
126        T::transcode::<M, _>(self, keys)
127    }
128}
129
130/// Shim to provide the bare `Node` lookup without transcoding target
131impl Transcode for () {
132    fn transcode<M, K>(&mut self, keys: K) -> Result<Node, Traversal>
133    where
134        M: TreeKey + ?Sized,
135        K: IntoKeys,
136    {
137        M::traverse_by_key(keys.into_keys(), |_, _, _| Ok(())).try_into()
138    }
139}
140
141/// Path with named keys separated by a separator char
142///
143/// The path will either be empty or start with the separator.
144///
145/// * `path: T`: A `Write` to write the separators and node names into during `Transcode`.
146///   See also [TreeKey::traverse_all()] and `Metadata::max_length()` for upper bounds
147///   on path length. Can also be a `AsRef<str>` to implement `IntoKeys` (see [`KeysIter`]).
148/// * `const S: char`: The path hierarchy separator to be inserted before each name,
149///   e.g. `'/'`.
150#[derive(Debug, Default, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
151#[repr(transparent)]
152#[serde(transparent)]
153pub struct Path<T: ?Sized, const S: char>(pub T);
154
155impl<T: ?Sized, const S: char> Path<T, S> {
156    /// The path hierarchy separator
157    #[inline]
158    pub const fn separator(&self) -> char {
159        S
160    }
161}
162
163impl<T, const S: char> Path<T, S> {
164    /// Extract just the path
165    #[inline]
166    pub fn into_inner(self) -> T {
167        self.0
168    }
169}
170
171impl<T: ?Sized, const S: char> Deref for Path<T, S> {
172    type Target = T;
173    #[inline]
174    fn deref(&self) -> &Self::Target {
175        &self.0
176    }
177}
178
179impl<T: ?Sized, const S: char> DerefMut for Path<T, S> {
180    #[inline]
181    fn deref_mut(&mut self) -> &mut Self::Target {
182        &mut self.0
183    }
184}
185
186impl<T, const S: char> From<T> for Path<T, S> {
187    #[inline]
188    fn from(value: T) -> Self {
189        Path(value)
190    }
191}
192
193impl<T: core::fmt::Display, const S: char> core::fmt::Display for Path<T, S> {
194    #[inline]
195    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
196        self.0.fmt(f)
197    }
198}
199
200/// String split/skip wrapper, smaller/simpler than `.split(S).skip(1)`
201#[derive(Copy, Clone, Default, Debug, PartialEq, PartialOrd, Serialize, Deserialize)]
202#[repr(transparent)]
203pub struct PathIter<'a, const S: char>(Option<&'a str>);
204
205impl<'a, const S: char> PathIter<'a, S> {
206    /// Create a new `PathIter`
207    #[inline]
208    pub fn new(s: Option<&'a str>) -> Self {
209        Self(s)
210    }
211
212    /// Create a new `PathIter` starting at the root.
213    ///
214    /// This calls `next()` once to pop everything up to and including the first separator.
215    #[inline]
216    pub fn root(s: &'a str) -> Self {
217        let mut s = Self::new(Some(s));
218        // Skip the first part to disambiguate between
219        // the one-Key Keys `[""]` and the zero-Key Keys `[]`.
220        // This is relevant in the case of e.g. `Option` and newtypes.
221        // See the corresponding unittests (`just_option`).
222        // It implies that Paths start with the separator
223        // or are empty. Everything before the first separator is ignored.
224        s.next();
225        s
226    }
227}
228
229impl<'a, const S: char> Iterator for PathIter<'a, S> {
230    type Item = &'a str;
231
232    fn next(&mut self) -> Option<Self::Item> {
233        self.0.map(|s| {
234            let pos = s
235                .chars()
236                .map_while(|c| (c != S).then_some(c.len_utf8()))
237                .sum();
238            let (left, right) = s.split_at(pos);
239            self.0 = right.get(S.len_utf8()..);
240            left
241        })
242    }
243}
244
245impl<const S: char> core::iter::FusedIterator for PathIter<'_, S> {}
246
247impl<'a, T: AsRef<str> + ?Sized, const S: char> IntoKeys for Path<&'a T, S> {
248    type IntoKeys = KeysIter<PathIter<'a, S>>;
249
250    #[inline]
251    fn into_keys(self) -> Self::IntoKeys {
252        PathIter::<'a, S>::root(self.0.as_ref()).into_keys()
253    }
254}
255
256impl<'a, T: AsRef<str> + ?Sized, const S: char> IntoKeys for &'a Path<T, S> {
257    type IntoKeys = KeysIter<PathIter<'a, S>>;
258
259    #[inline]
260    fn into_keys(self) -> Self::IntoKeys {
261        Path(&self.0).into_keys()
262    }
263}
264
265impl<T: Write + ?Sized, const S: char> Transcode for Path<T, S> {
266    fn transcode<M, K>(&mut self, keys: K) -> Result<Node, Traversal>
267    where
268        M: TreeKey + ?Sized,
269        K: IntoKeys,
270    {
271        M::traverse_by_key(keys.into_keys(), |index, name, _len| {
272            self.0.write_char(S).or(Err(()))?;
273            let mut buf = itoa::Buffer::new();
274            let name = name.unwrap_or_else(|| buf.format(index));
275            debug_assert!(!name.contains(S));
276            self.0.write_str(name).or(Err(()))
277        })
278        .try_into()
279    }
280}
281
282/// Indices of `usize` to identify a node in a `TreeKey`
283#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
284#[repr(transparent)]
285#[serde(transparent)]
286pub struct Indices<T: ?Sized>(pub T);
287
288impl<T: ?Sized> Deref for Indices<T> {
289    type Target = T;
290    #[inline]
291    fn deref(&self) -> &Self::Target {
292        &self.0
293    }
294}
295
296impl<T: ?Sized> DerefMut for Indices<T> {
297    #[inline]
298    fn deref_mut(&mut self) -> &mut Self::Target {
299        &mut self.0
300    }
301}
302
303impl<T> Indices<T> {
304    /// Extract just the indices
305    #[inline]
306    pub fn into_inner(self) -> T {
307        self.0
308    }
309}
310
311impl<T> From<T> for Indices<T> {
312    #[inline]
313    fn from(value: T) -> Self {
314        Self(value)
315    }
316}
317
318impl<const D: usize, T: Copy + Default> Default for Indices<[T; D]> {
319    #[inline]
320    fn default() -> Self {
321        Self([Default::default(); D])
322    }
323}
324
325impl<const D: usize, T> From<Indices<[T; D]>> for [T; D] {
326    #[inline]
327    fn from(value: Indices<[T; D]>) -> Self {
328        value.0
329    }
330}
331
332impl<T: core::fmt::Display> core::fmt::Display for Indices<T> {
333    #[inline]
334    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
335        self.0.fmt(f)
336    }
337}
338
339impl<T: IntoKeys> IntoKeys for Indices<T> {
340    type IntoKeys = T::IntoKeys;
341    #[inline]
342    fn into_keys(self) -> Self::IntoKeys {
343        self.0.into_keys()
344    }
345}
346
347impl<T: AsMut<[usize]> + ?Sized> Transcode for Indices<T> {
348    #[inline]
349    fn transcode<M, K>(&mut self, keys: K) -> Result<Node, Traversal>
350    where
351        M: TreeKey + ?Sized,
352        K: IntoKeys,
353    {
354        self.0.as_mut().transcode::<M, _>(keys)
355    }
356}
357
358macro_rules! impl_transcode_slice {
359    ($($t:ty)+) => {$(
360        impl Transcode for [$t] {
361            fn transcode<M, K>(&mut self, keys: K) -> Result<Node, Traversal>
362            where
363                M: TreeKey + ?Sized,
364                K: IntoKeys,
365            {
366                let mut it = self.iter_mut();
367                M::traverse_by_key(keys.into_keys(), |index, _name, _len| {
368                    let idx = it.next().ok_or(())?;
369                    *idx = index.try_into().or(Err(()))?;
370                    Ok(())
371                })
372                .try_into()
373            }
374        }
375    )+};
376}
377impl_transcode_slice!(usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128);
378
379#[cfg(feature = "alloc")]
380impl<T> Transcode for Vec<T>
381where
382    usize: TryInto<T>,
383{
384    fn transcode<M, K>(&mut self, keys: K) -> Result<Node, Traversal>
385    where
386        M: TreeKey + ?Sized,
387        K: IntoKeys,
388    {
389        M::traverse_by_key(keys.into_keys(), |index, _name, _len| {
390            self.push(index.try_into().or(Err(()))?);
391            Ok(())
392        })
393        .try_into()
394    }
395}
396
397#[cfg(test)]
398mod test {
399    use super::*;
400
401    #[test]
402    fn strsplit() {
403        use heapless::Vec;
404        for p in ["/d/1", "/a/bccc//d/e/", "", "/", "a/b", "a"] {
405            let a: Vec<_, 10> = PathIter::<'_, '/'>::root(p).collect();
406            let b: Vec<_, 10> = p.split('/').skip(1).collect();
407            assert_eq!(a, b);
408        }
409    }
410}
miniconf/node.rs

miniconf/
node.rs
