grovedb_path/
subtree_path.rs

1// MIT LICENSE
2//
3// Copyright (c) 2023 Dash Core Group
4//
5// Permission is hereby granted, free of charge, to any
6// person obtaining a copy of this software and associated
7// documentation files (the "Software"), to deal in the
8// Software without restriction, including without
9// limitation the rights to use, copy, modify, merge,
10// publish, distribute, sublicense, and/or sell copies of
11// the Software, and to permit persons to whom the Software
12// is furnished to do so, subject to the following
13// conditions:
14//
15// The above copyright notice and this permission notice
16// shall be included in all copies or substantial portions
17// of the Software.
18//
19// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
20// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
21// TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
22// PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
23// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
24// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
25// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
26// IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
27// DEALINGS IN THE SOFTWARE.
28
29//! Definitions of type representing a path to a subtree made of borrowed data.
30//!
31//! Opposed to [SubtreePathBuilder] which is some kind of a builder,
32//! [SubtreePath] is a way to refer to path data which makes it a great
33//! candidate to use as a function argument where a subtree path is expected,
34//! combined with it's various `From` implementations it can cover slices, owned
35//! subtree paths and other path references if use as generic [Into].
36
37use std::{
38    cmp,
39    fmt::{self, Display},
40    hash::{Hash, Hasher},
41};
42
43use crate::{
44    subtree_path_builder::{SubtreePathBuilder, SubtreePathRelative},
45    util::CowLike,
46    SubtreePathIter,
47};
48
49/// Path to a GroveDB's subtree with no owned data and cheap to clone.
50#[derive(Debug)]
51pub struct SubtreePath<'b, B> {
52    pub(crate) ref_variant: SubtreePathInner<'b, B>,
53}
54
55impl<B: AsRef<[u8]>> Display for SubtreePath<'_, B> {
56    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> std::fmt::Result {
57        fn bytes_to_hex_or_ascii(bytes: &[u8]) -> String {
58            // Define the set of allowed characters
59            const ALLOWED_CHARS: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ\
60                                  abcdefghijklmnopqrstuvwxyz\
61                                  0123456789_-/\\[]@";
62
63            // Check if all characters in hex_value are allowed
64            if bytes.iter().all(|&c| ALLOWED_CHARS.contains(&c)) {
65                // Try to convert to UTF-8
66                String::from_utf8(bytes.to_vec())
67                    .unwrap_or_else(|_| format!("0x{}", hex::encode(bytes)))
68            } else {
69                // Hex encode and prepend "0x"
70                format!("0x{}", hex::encode(bytes))
71            }
72        }
73
74        match &self.ref_variant {
75            SubtreePathInner::Slice(slice) => {
76                let ascii_path = slice
77                    .iter()
78                    .map(|e| bytes_to_hex_or_ascii(e.as_ref()))
79                    .collect::<Vec<_>>()
80                    .join("/");
81                write!(f, "{}", ascii_path)
82            }
83            SubtreePathInner::SubtreePath(subtree_path) => {
84                let ascii_path = subtree_path
85                    .to_vec()
86                    .into_iter()
87                    .map(|a| bytes_to_hex_or_ascii(a.as_slice()))
88                    .collect::<Vec<_>>()
89                    .join("/");
90                write!(f, "{}", ascii_path)
91            }
92            SubtreePathInner::SubtreePathIter(iter) => {
93                let ascii_path = iter
94                    .clone()
95                    .map(bytes_to_hex_or_ascii)
96                    .collect::<Vec<_>>()
97                    .join("/");
98                write!(f, "{}", ascii_path)
99            }
100        }
101    }
102}
103
104/// Wrapped inner representation of subtree path ref.
105#[derive(Debug)]
106pub(crate) enum SubtreePathInner<'b, B> {
107    /// The referred path is a slice, might a provided by user or a subslice
108    /// when deriving a parent.
109    Slice(&'b [B]),
110    /// Links to an existing subtree path that became a derivation point.
111    SubtreePath(&'b SubtreePathBuilder<'b, B>),
112    /// Links to an existing subtree path with owned segments using it's
113    /// iterator to support parent derivations.
114    /// This may sound tricky, but `SubtreePathIter` fits there nicely because
115    /// like the other variants of [SubtreePathInner] it points to some segments
116    /// data, but because of parent derivations on packed path segments we need
117    /// to keep track where are we, that's exactly what iterator does + holds a
118    /// link to the next part of our subtree path chain.
119    SubtreePathIter(SubtreePathIter<'b, B>),
120}
121
122impl<'br, BL, BR> PartialEq<SubtreePath<'br, BR>> for SubtreePath<'_, BL>
123where
124    BL: AsRef<[u8]>,
125    BR: AsRef<[u8]>,
126{
127    fn eq(&self, other: &SubtreePath<'br, BR>) -> bool {
128        self.clone()
129            .into_reverse_iter()
130            .eq(other.clone().into_reverse_iter())
131    }
132}
133
134/// First and foremost, the order of subtree paths is dictated by their lengths.
135/// Therefore, those subtrees closer to the root will come first. The rest it
136/// can guarantee is to be free of false equality; however, seemingly unrelated
137/// subtrees can come one after another if they share the same length, which was
138/// (not) done for performance reasons.
139impl<'br, BL, BR> PartialOrd<SubtreePath<'br, BR>> for SubtreePath<'_, BL>
140where
141    BL: AsRef<[u8]>,
142    BR: AsRef<[u8]>,
143{
144    fn partial_cmp(&self, other: &SubtreePath<'br, BR>) -> Option<cmp::Ordering> {
145        let iter_a = self.clone().into_reverse_iter();
146        let iter_b = other.clone().into_reverse_iter();
147
148        Some(
149            iter_a
150                .len()
151                .cmp(&iter_b.len())
152                .reverse()
153                .then_with(|| iter_a.cmp(iter_b)),
154        )
155    }
156}
157
158impl<'br, BL, BR> PartialOrd<SubtreePathBuilder<'br, BR>> for SubtreePathBuilder<'_, BL>
159where
160    BL: AsRef<[u8]>,
161    BR: AsRef<[u8]>,
162{
163    fn partial_cmp(&self, other: &SubtreePathBuilder<'br, BR>) -> Option<cmp::Ordering> {
164        let iter_a = self.reverse_iter();
165        let iter_b = other.reverse_iter();
166
167        Some(
168            iter_a
169                .len()
170                .cmp(&iter_b.len())
171                .reverse()
172                .then_with(|| iter_a.cmp(iter_b)),
173        )
174    }
175}
176
177impl<'br, BL, BR> PartialOrd<SubtreePathBuilder<'br, BR>> for SubtreePath<'_, BL>
178where
179    BL: AsRef<[u8]>,
180    BR: AsRef<[u8]>,
181{
182    fn partial_cmp(&self, other: &SubtreePathBuilder<'br, BR>) -> Option<cmp::Ordering> {
183        self.partial_cmp(&SubtreePath::from(other))
184    }
185}
186
187impl<BL> Ord for SubtreePath<'_, BL>
188where
189    BL: AsRef<[u8]>,
190{
191    fn cmp(&self, other: &Self) -> cmp::Ordering {
192        self.partial_cmp(other).expect("order is totally defined")
193    }
194}
195
196impl<BL> Ord for SubtreePathBuilder<'_, BL>
197where
198    BL: AsRef<[u8]>,
199{
200    fn cmp(&self, other: &Self) -> cmp::Ordering {
201        self.partial_cmp(other).expect("order is totally defined")
202    }
203}
204
205impl<B: AsRef<[u8]>> Eq for SubtreePath<'_, B> {}
206
207impl<'b, B> From<SubtreePathInner<'b, B>> for SubtreePath<'b, B> {
208    fn from(ref_variant: SubtreePathInner<'b, B>) -> Self {
209        Self { ref_variant }
210    }
211}
212
213impl<'b, B> From<&'b [B]> for SubtreePath<'b, B> {
214    fn from(value: &'b [B]) -> Self {
215        SubtreePathInner::Slice(value).into()
216    }
217}
218
219impl<'b, B, const N: usize> From<&'b [B; N]> for SubtreePath<'b, B> {
220    fn from(value: &'b [B; N]) -> Self {
221        SubtreePathInner::Slice(value).into()
222    }
223}
224
225/// Create a link to existing [SubtreePath] that cannot outlive it, because it
226/// possibly owns some of the path segments.
227impl<'s, 'b, B> From<&'s SubtreePathBuilder<'b, B>> for SubtreePath<'s, B> {
228    fn from(value: &'s SubtreePathBuilder<'b, B>) -> Self {
229        SubtreePathInner::SubtreePath(value).into()
230    }
231}
232
233/// Hash order is the same as iteration order: from most deep path segment up to
234/// root.
235impl<B: AsRef<[u8]>> Hash for SubtreePath<'_, B> {
236    fn hash<H: Hasher>(&self, state: &mut H) {
237        match &self.ref_variant {
238            SubtreePathInner::Slice(slice) => slice
239                .iter()
240                .map(AsRef::as_ref)
241                .rev()
242                .for_each(|s| s.hash(state)),
243            SubtreePathInner::SubtreePath(path) => path.hash(state),
244            SubtreePathInner::SubtreePathIter(path_iter) => {
245                path_iter.clone().for_each(|s| s.hash(state))
246            }
247        }
248    }
249}
250
251/// For the same reason as for `Hash` implementation, derived impl requires
252/// generics to carry trait bounds that actually don't needed.
253impl<B> Clone for SubtreePath<'_, B> {
254    fn clone(&self) -> Self {
255        match &self.ref_variant {
256            SubtreePathInner::Slice(x) => SubtreePathInner::Slice(x),
257            SubtreePathInner::SubtreePath(x) => SubtreePathInner::SubtreePath(x),
258            SubtreePathInner::SubtreePathIter(x) => SubtreePathInner::SubtreePathIter(x.clone()),
259        }
260        .into()
261    }
262}
263
264impl SubtreePath<'static, [u8; 0]> {
265    /// Get empty subtree path (meaning it'll point to the root tree).
266    pub const fn empty() -> Self {
267        SubtreePath {
268            ref_variant: SubtreePathInner::Slice(&[]),
269        }
270    }
271}
272
273impl<B> SubtreePath<'_, B> {
274    /// Returns the length of the subtree path.
275    pub fn len(&self) -> usize {
276        match &self.ref_variant {
277            SubtreePathInner::Slice(s) => s.len(),
278            SubtreePathInner::SubtreePath(path) => path.len(),
279            SubtreePathInner::SubtreePathIter(path_iter) => path_iter.len(),
280        }
281    }
282
283    /// Returns whether the path is empty (the root tree).
284    pub fn is_empty(&self) -> bool {
285        match &self.ref_variant {
286            SubtreePathInner::Slice(s) => s.is_empty(),
287            SubtreePathInner::SubtreePath(path) => path.is_empty(),
288            SubtreePathInner::SubtreePathIter(path_iter) => path_iter.is_empty(),
289        }
290    }
291}
292
293impl<'b, B: AsRef<[u8]>> SubtreePath<'b, B> {
294    /// Get a derived path that will reuse this [Self] as it's base path and
295    /// capable of owning data.
296    pub fn derive_owned(&self) -> SubtreePathBuilder<'b, B> {
297        self.into()
298    }
299
300    /// Get a derived path with a child path segment added.
301    pub fn derive_owned_with_child<'s, S>(&self, segment: S) -> SubtreePathBuilder<'b, B>
302    where
303        S: Into<CowLike<'s>>,
304        's: 'b,
305    {
306        SubtreePathBuilder {
307            base: self.clone(),
308            relative: SubtreePathRelative::Single(segment.into()),
309        }
310    }
311
312    /// Get a derived subtree path for a parent with care for base path slice
313    /// case. The main difference from [SubtreePath::derive_parent] is that
314    /// lifetime of returned [Self] if not limited to the scope where this
315    /// function was called so it's possible to follow to ancestor paths
316    /// without keeping previous result as it still will link to `'b`
317    /// (latest [SubtreePath] or initial slice of data).
318    pub fn derive_parent(&self) -> Option<(SubtreePath<'b, B>, &'b [u8])> {
319        match &self.ref_variant {
320            SubtreePathInner::Slice(path) => path
321                .split_last()
322                .map(|(tail, rest)| (SubtreePathInner::Slice(rest).into(), tail.as_ref())),
323            SubtreePathInner::SubtreePath(path) => path.derive_parent(),
324            SubtreePathInner::SubtreePathIter(iter) => {
325                let mut derived_iter = iter.clone();
326                derived_iter.next().map(|segment| {
327                    (
328                        SubtreePathInner::SubtreePathIter(derived_iter).into(),
329                        segment,
330                    )
331                })
332            }
333        }
334    }
335
336    /// Get a reverse path segments iterator.
337    pub fn into_reverse_iter(self) -> SubtreePathIter<'b, B> {
338        match self.ref_variant {
339            SubtreePathInner::Slice(slice) => SubtreePathIter::new(slice.iter()),
340            SubtreePathInner::SubtreePath(path) => path.reverse_iter(),
341            SubtreePathInner::SubtreePathIter(iter) => iter,
342        }
343    }
344
345    /// Retuns `true` if the subtree path is empty, so it points to the root
346    /// tree.
347    pub fn is_root(&self) -> bool {
348        match &self.ref_variant {
349            SubtreePathInner::Slice(s) => s.is_empty(),
350            SubtreePathInner::SubtreePath(path) => path.is_root(),
351            SubtreePathInner::SubtreePathIter(iter) => iter.is_empty(),
352        }
353    }
354
355    /// Collect path as a vector of vectors, but this actually negates all the
356    /// benefits of this library.
357    pub fn to_vec(&self) -> Vec<Vec<u8>> {
358        match &self.ref_variant {
359            SubtreePathInner::Slice(slice) => slice.iter().map(|x| x.as_ref().to_vec()).collect(),
360            SubtreePathInner::SubtreePath(path) => path.to_vec(),
361            SubtreePathInner::SubtreePathIter(iter) => {
362                let mut path = iter
363                    .clone()
364                    .map(|x| x.as_ref().to_vec())
365                    .collect::<Vec<Vec<u8>>>();
366                path.reverse();
367                path
368            }
369        }
370    }
371}
372
373#[cfg(test)]
374mod tests {
375    use super::*;
376
377    #[test]
378    fn to_vec() {
379        let base: SubtreePath<_> = (&[b"one" as &[u8], b"two", b"three"]).into();
380        let mut builder = base.derive_owned_with_child(b"four");
381        builder.push_segment(b"five");
382        builder.push_segment(b"six");
383        builder.push_segment(b"seven");
384        builder.push_segment(b"eight");
385        let parent = builder.derive_parent().unwrap().0;
386
387        let as_vec = parent.to_vec();
388        let reference_vec = vec![
389            b"one".to_vec(),
390            b"two".to_vec(),
391            b"three".to_vec(),
392            b"four".to_vec(),
393            b"five".to_vec(),
394            b"six".to_vec(),
395            b"seven".to_vec(),
396        ];
397
398        assert_eq!(as_vec, reference_vec);
399        assert_eq!(parent.len(), reference_vec.len());
400    }
401
402    #[test]
403    fn ordering() {
404        let path_a: SubtreePath<_> = (&[b"one" as &[u8], b"two", b"three"]).into();
405        let path_b = path_a.derive_owned_with_child(b"four");
406        let path_c = path_a.derive_owned_with_child(b"notfour");
407        let (path_d_parent, _) = path_a.derive_parent().unwrap();
408        let path_d = path_d_parent.derive_owned_with_child(b"three");
409
410        // Same lengths for different paths don't make them equal:
411        assert!(!matches!(
412            SubtreePath::from(&path_b).cmp(&SubtreePath::from(&path_c)),
413            cmp::Ordering::Equal
414        ));
415
416        // Equal paths made the same way are equal:
417        assert!(matches!(
418            path_a.cmp(&SubtreePath::from(&path_d)),
419            cmp::Ordering::Equal
420        ));
421
422        // Longer paths come first
423        assert!(path_a > path_b);
424        assert!(path_a > path_c);
425    }
426}
grovedb_path/subtree_path.rs

grovedb_path/
subtree_path.rs
