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::hash::{Hash, Hasher};
38
39use crate::{
40    subtree_path_builder::{SubtreePathBuilder, SubtreePathRelative},
41    util::CowLike,
42    SubtreePathIter,
43};
44
45/// Path to a GroveDB's subtree with no owned data and cheap to clone.
46#[derive(Debug)]
47pub struct SubtreePath<'b, B> {
48    pub(crate) ref_variant: SubtreePathInner<'b, B>,
49}
50
51/// Wrapped inner representation of subtree path ref.
52#[derive(Debug)]
53pub(crate) enum SubtreePathInner<'b, B> {
54    /// The referred path is a slice, might a provided by user or a subslice
55    /// when deriving a parent.
56    Slice(&'b [B]),
57    /// Links to an existing subtree path that became a derivation point.
58    SubtreePath(&'b SubtreePathBuilder<'b, B>),
59    /// Links to an existing subtree path with owned segments using it's
60    /// iterator to support parent derivations.
61    /// This may sound tricky, but `SubtreePathIter` fits there nicely because
62    /// like the other variants of [SubtreePathInner] it points to some segments
63    /// data, but because of parent derivations on packed path segments we need
64    /// to keep track where are we, that's exactly what iterator does + holds a
65    /// link to the next part of our subtree path chain.
66    SubtreePathIter(SubtreePathIter<'b, B>),
67}
68
69impl<'bl, 'br, BL, BR> PartialEq<SubtreePath<'br, BR>> for SubtreePath<'bl, BL>
70where
71    BL: AsRef<[u8]>,
72    BR: AsRef<[u8]>,
73{
74    fn eq(&self, other: &SubtreePath<'br, BR>) -> bool {
75        self.clone()
76            .into_reverse_iter()
77            .eq(other.clone().into_reverse_iter())
78    }
79}
80
81impl<'b, B: AsRef<[u8]>> Eq for SubtreePath<'b, B> {}
82
83impl<'b, B> From<SubtreePathInner<'b, B>> for SubtreePath<'b, B> {
84    fn from(ref_variant: SubtreePathInner<'b, B>) -> Self {
85        Self { ref_variant }
86    }
87}
88
89impl<'b, B> From<&'b [B]> for SubtreePath<'b, B> {
90    fn from(value: &'b [B]) -> Self {
91        SubtreePathInner::Slice(value).into()
92    }
93}
94
95impl<'b, B, const N: usize> From<&'b [B; N]> for SubtreePath<'b, B> {
96    fn from(value: &'b [B; N]) -> Self {
97        SubtreePathInner::Slice(value).into()
98    }
99}
100
101/// Create a link to existing [SubtreePath] that cannot outlive it, because it
102/// possibly owns some of the path segments.
103impl<'s, 'b, B> From<&'s SubtreePathBuilder<'b, B>> for SubtreePath<'s, B> {
104    fn from(value: &'s SubtreePathBuilder<'b, B>) -> Self {
105        SubtreePathInner::SubtreePath(value).into()
106    }
107}
108
109/// Hash order is the same as iteration order: from most deep path segment up to
110/// root.
111impl<'b, B: AsRef<[u8]>> Hash for SubtreePath<'b, B> {
112    fn hash<H: Hasher>(&self, state: &mut H) {
113        match &self.ref_variant {
114            SubtreePathInner::Slice(slice) => slice
115                .iter()
116                .map(AsRef::as_ref)
117                .rev()
118                .for_each(|s| s.hash(state)),
119            SubtreePathInner::SubtreePath(path) => path.hash(state),
120            SubtreePathInner::SubtreePathIter(path_iter) => {
121                path_iter.clone().for_each(|s| s.hash(state))
122            }
123        }
124    }
125}
126
127/// For the same reason as for `Hash` implementation, derived impl requires
128/// generics to carry trait bounds that actually don't needed.
129impl<B> Clone for SubtreePath<'_, B> {
130    fn clone(&self) -> Self {
131        match &self.ref_variant {
132            SubtreePathInner::Slice(x) => SubtreePathInner::Slice(x),
133            SubtreePathInner::SubtreePath(x) => SubtreePathInner::SubtreePath(x),
134            SubtreePathInner::SubtreePathIter(x) => SubtreePathInner::SubtreePathIter(x.clone()),
135        }
136        .into()
137    }
138}
139
140impl SubtreePath<'static, [u8; 0]> {
141    /// Get empty subtree path (meaning it'll point to the root tree).
142    pub const fn empty() -> Self {
143        SubtreePath {
144            ref_variant: SubtreePathInner::Slice(&[]),
145        }
146    }
147}
148
149impl<B> SubtreePath<'_, B> {
150    /// Returns the length of the subtree path.
151    pub fn len(&self) -> usize {
152        match &self.ref_variant {
153            SubtreePathInner::Slice(s) => s.len(),
154            SubtreePathInner::SubtreePath(path) => path.len(),
155            SubtreePathInner::SubtreePathIter(path_iter) => path_iter.len(),
156        }
157    }
158
159    /// Returns whether the path is empty (the root tree).
160    pub fn is_empty(&self) -> bool {
161        match &self.ref_variant {
162            SubtreePathInner::Slice(s) => s.is_empty(),
163            SubtreePathInner::SubtreePath(path) => path.is_empty(),
164            SubtreePathInner::SubtreePathIter(path_iter) => path_iter.is_empty(),
165        }
166    }
167}
168
169impl<'b, B: AsRef<[u8]>> SubtreePath<'b, B> {
170    /// Get a derived path that will reuse this [Self] as it's base path and
171    /// capable of owning data.
172    pub fn derive_owned(&self) -> SubtreePathBuilder<'b, B> {
173        self.into()
174    }
175
176    /// Get a derived path with a child path segment added.
177    pub fn derive_owned_with_child<'s, S>(&'b self, segment: S) -> SubtreePathBuilder<'b, B>
178    where
179        S: Into<CowLike<'s>>,
180        's: 'b,
181    {
182        SubtreePathBuilder {
183            base: self.clone(),
184            relative: SubtreePathRelative::Single(segment.into()),
185        }
186    }
187
188    /// Get a derived subtree path for a parent with care for base path slice
189    /// case. The main difference from [SubtreePath::derive_parent] is that
190    /// lifetime of returned [Self] if not limited to the scope where this
191    /// function was called so it's possible to follow to ancestor paths
192    /// without keeping previous result as it still will link to `'b`
193    /// (latest [SubtreePath] or initial slice of data).
194    pub fn derive_parent(&self) -> Option<(SubtreePath<'b, B>, &'b [u8])> {
195        match &self.ref_variant {
196            SubtreePathInner::Slice(path) => path
197                .split_last()
198                .map(|(tail, rest)| (SubtreePathInner::Slice(rest).into(), tail.as_ref())),
199            SubtreePathInner::SubtreePath(path) => path.derive_parent(),
200            SubtreePathInner::SubtreePathIter(iter) => {
201                let mut derived_iter = iter.clone();
202                derived_iter.next().map(|segment| {
203                    (
204                        SubtreePathInner::SubtreePathIter(derived_iter).into(),
205                        segment,
206                    )
207                })
208            }
209        }
210    }
211
212    /// Get a reverse path segments iterator.
213    pub fn into_reverse_iter(self) -> SubtreePathIter<'b, B> {
214        match self.ref_variant {
215            SubtreePathInner::Slice(slice) => SubtreePathIter::new(slice.iter()),
216            SubtreePathInner::SubtreePath(path) => path.reverse_iter(),
217            SubtreePathInner::SubtreePathIter(iter) => iter,
218        }
219    }
220
221    /// Retuns `true` if the subtree path is empty, so it points to the root
222    /// tree.
223    pub fn is_root(&self) -> bool {
224        match &self.ref_variant {
225            SubtreePathInner::Slice(s) => s.is_empty(),
226            SubtreePathInner::SubtreePath(path) => path.is_root(),
227            SubtreePathInner::SubtreePathIter(iter) => iter.is_empty(),
228        }
229    }
230
231    /// Collect path as a vector of vectors, but this actually negates all the
232    /// benefits of this library.
233    pub fn to_vec(&self) -> Vec<Vec<u8>> {
234        match &self.ref_variant {
235            SubtreePathInner::Slice(slice) => slice.iter().map(|x| x.as_ref().to_vec()).collect(),
236            SubtreePathInner::SubtreePath(path) => path.to_vec(),
237            SubtreePathInner::SubtreePathIter(iter) => {
238                let mut path = iter
239                    .clone()
240                    .map(|x| x.as_ref().to_vec())
241                    .collect::<Vec<Vec<u8>>>();
242                path.reverse();
243                path
244            }
245        }
246    }
247}
248
249#[cfg(test)]
250mod tests {
251    use super::*;
252
253    #[test]
254    fn to_vec() {
255        let base: SubtreePath<_> = (&[b"one" as &[u8], b"two", b"three"]).into();
256        let mut builder = base.derive_owned_with_child(b"four");
257        builder.push_segment(b"five");
258        builder.push_segment(b"six");
259        builder.push_segment(b"seven");
260        builder.push_segment(b"eight");
261        let parent = builder.derive_parent().unwrap().0;
262
263        let as_vec = parent.to_vec();
264        let reference_vec = vec![
265            b"one".to_vec(),
266            b"two".to_vec(),
267            b"three".to_vec(),
268            b"four".to_vec(),
269            b"five".to_vec(),
270            b"six".to_vec(),
271            b"seven".to_vec(),
272        ];
273
274        assert_eq!(as_vec, reference_vec);
275        assert_eq!(parent.len(), reference_vec.len());
276    }
277}
grovedb_path/subtree_path.rs

grovedb_path/
subtree_path.rs
