grovedb_path/
subtree_path_builder.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//! Difinitions of versatile type representing a path to a subtree that can own
30//! certain path segments.
31
32use std::hash::{Hash, Hasher};
33
34use crate::{
35    subtree_path::SubtreePathInner,
36    util::{CompactBytes, CowLike},
37    SubtreePath, SubtreePathIter,
38};
39
40/// Path to a GroveDB's subtree.
41#[derive(Debug)]
42pub struct SubtreePathBuilder<'b, B> {
43    /// Derivation starting point.
44    pub(crate) base: SubtreePath<'b, B>,
45    /// Path information relative to [base](Self::base).
46    pub(crate) relative: SubtreePathRelative<'b>,
47}
48
49impl<B> Clone for SubtreePathBuilder<'_, B> {
50    fn clone(&self) -> Self {
51        SubtreePathBuilder {
52            base: self.base.clone(),
53            relative: self.relative.clone(),
54        }
55    }
56}
57
58/// Hash order is the same as iteration order: from most deep path segment up to
59/// root.
60impl<B: AsRef<[u8]>> Hash for SubtreePathBuilder<'_, B> {
61    fn hash<H: Hasher>(&self, state: &mut H) {
62        self.relative.hash(state);
63        self.base.hash(state);
64    }
65}
66
67impl<'br, BL, BR> PartialEq<SubtreePathBuilder<'br, BR>> for SubtreePathBuilder<'_, BL>
68where
69    BL: AsRef<[u8]>,
70    BR: AsRef<[u8]>,
71{
72    fn eq(&self, other: &SubtreePathBuilder<'br, BR>) -> bool {
73        self.reverse_iter().eq(other.reverse_iter())
74    }
75}
76
77impl<'br, BL, BR> PartialEq<SubtreePathBuilder<'br, BR>> for SubtreePath<'_, BL>
78where
79    BL: AsRef<[u8]>,
80    BR: AsRef<[u8]>,
81{
82    fn eq(&self, other: &SubtreePathBuilder<'br, BR>) -> bool {
83        self.clone().into_reverse_iter().eq(other.reverse_iter())
84    }
85}
86
87impl<'br, BL, BR> PartialEq<SubtreePath<'br, BR>> for SubtreePathBuilder<'_, BL>
88where
89    BL: AsRef<[u8]>,
90    BR: AsRef<[u8]>,
91{
92    fn eq(&self, other: &SubtreePath<'br, BR>) -> bool {
93        self.reverse_iter().eq(other.clone().into_reverse_iter())
94    }
95}
96
97impl<B: AsRef<[u8]>> Eq for SubtreePathBuilder<'_, B> {}
98
99impl<'s, 'b, B> From<&'s SubtreePath<'b, B>> for SubtreePathBuilder<'b, B> {
100    fn from(value: &'s SubtreePath<'b, B>) -> Self {
101        SubtreePathBuilder {
102            base: value.clone(),
103            relative: SubtreePathRelative::Empty,
104        }
105    }
106}
107
108/// Derived subtree path on top of base path.
109#[derive(Debug, Clone)]
110pub(crate) enum SubtreePathRelative<'r> {
111    /// Equivalent to the base path.
112    Empty,
113    /// Added one child segment.
114    Single(CowLike<'r>),
115    /// Derivation with multiple owned path segments at once
116    Multi(CompactBytes),
117}
118
119impl SubtreePathRelative<'_> {
120    pub fn len(&self) -> usize {
121        match self {
122            SubtreePathRelative::Empty => 0,
123            SubtreePathRelative::Single(_) => 1,
124            SubtreePathRelative::Multi(cb) => cb.len(),
125        }
126    }
127
128    pub fn is_empty(&self) -> bool {
129        matches!(self, SubtreePathRelative::Empty)
130    }
131}
132
133impl Hash for SubtreePathRelative<'_> {
134    fn hash<H: Hasher>(&self, state: &mut H) {
135        match self {
136            SubtreePathRelative::Empty => {}
137            SubtreePathRelative::Single(segment) => segment.hash(state),
138            SubtreePathRelative::Multi(bytes) => {
139                bytes.reverse_iter().for_each(|segment| segment.hash(state))
140            }
141        }
142    }
143}
144
145impl SubtreePathBuilder<'static, [u8; 0]> {
146    /// Creates empty subtree path
147    pub fn new() -> Self {
148        SubtreePathBuilder {
149            base: [].as_ref().into(),
150            relative: SubtreePathRelative::Empty,
151        }
152    }
153}
154
155impl Default for SubtreePathBuilder<'static, [u8; 0]> {
156    fn default() -> Self {
157        Self::new()
158    }
159}
160
161impl<B> SubtreePathBuilder<'_, B> {
162    /// Makes an owned `SubtreePathBuilder` out of iterator.
163    pub fn owned_from_iter<S: AsRef<[u8]>>(iter: impl IntoIterator<Item = S>) -> Self {
164        let bytes = iter.into_iter().fold(CompactBytes::new(), |mut bytes, s| {
165            bytes.add_segment(s.as_ref());
166            bytes
167        });
168
169        SubtreePathBuilder {
170            base: SubtreePath {
171                ref_variant: SubtreePathInner::Slice(&[]),
172            },
173            relative: SubtreePathRelative::Multi(bytes),
174        }
175    }
176
177    /// Create an owned version of `SubtreePathBuilder` from `SubtreePath`.
178    pub fn owned_from_path<S: AsRef<[u8]>>(path: SubtreePath<S>) -> Self {
179        Self::owned_from_iter(path.to_vec())
180    }
181}
182
183impl<B> SubtreePathBuilder<'_, B> {
184    /// Returns the length of the subtree path.
185    pub fn len(&self) -> usize {
186        self.base.len() + self.relative.len()
187    }
188
189    /// Returns whether the path is empty (the root tree).
190    pub fn is_empty(&self) -> bool {
191        self.base.is_empty() && self.relative.is_empty()
192    }
193
194    /// Adds path segment in place.
195    pub fn push_segment(&mut self, segment: &[u8]) {
196        match &mut self.relative {
197            SubtreePathRelative::Empty => {
198                let mut bytes = CompactBytes::new();
199                bytes.add_segment(segment);
200                self.relative = SubtreePathRelative::Multi(bytes);
201            }
202            SubtreePathRelative::Single(old_segment) => {
203                let mut bytes = CompactBytes::new();
204                bytes.add_segment(old_segment);
205                bytes.add_segment(segment);
206                self.relative = SubtreePathRelative::Multi(bytes);
207            }
208            SubtreePathRelative::Multi(bytes) => bytes.add_segment(segment),
209        }
210    }
211}
212
213impl<'b, B: AsRef<[u8]>> SubtreePathBuilder<'b, B> {
214    /// Get a derived path that will use another subtree path (or reuse the base
215    /// slice) as it's base, then could be edited in place.
216    pub fn derive_owned(&'b self) -> SubtreePathBuilder<'b, B> {
217        match self.relative {
218            // If this derived path makes no difference, derive from base
219            SubtreePathRelative::Empty => self.base.derive_owned(),
220            // Otherwise a new derived subtree path must point to this one as it's base
221            _ => SubtreePathBuilder {
222                base: SubtreePathInner::SubtreePath(self).into(),
223                relative: SubtreePathRelative::Empty,
224            },
225        }
226    }
227
228    /// Get a derived path for a parent and a chopped segment. Returned
229    /// [SubtreePath] will be linked to this [SubtreePath] because it might
230    /// contain owned data and it has to outlive [SubtreePath].
231    pub fn derive_parent(&self) -> Option<(SubtreePath<B>, &[u8])> {
232        match &self.relative {
233            SubtreePathRelative::Empty => self.base.derive_parent(),
234            SubtreePathRelative::Single(relative) => Some((self.base.clone(), relative.as_ref())),
235            SubtreePathRelative::Multi(_) => {
236                let mut iter = self.reverse_iter();
237                iter.next()
238                    .map(|segment| (SubtreePathInner::SubtreePathIter(iter).into(), segment))
239            }
240        }
241    }
242
243    /// Get a derived path for a parent and a chopped segment. The lifetime of
244    /// returned path is constrained solely by the original slice that this
245    /// whole path hierarchy is based upon, and the point of derivation has
246    /// no effect on it.
247    pub fn derive_parent_owned(&self) -> Option<(SubtreePathBuilder<'b, B>, Vec<u8>)> {
248        match &self.relative {
249            SubtreePathRelative::Empty => self
250                .base
251                .derive_parent()
252                .map(|(path, key)| (path.derive_owned(), key.to_vec())),
253            SubtreePathRelative::Single(relative) => {
254                Some((self.base.derive_owned(), relative.to_vec()))
255            }
256            SubtreePathRelative::Multi(bytes) => {
257                let mut new_bytes = bytes.clone();
258                if let Some(key) = new_bytes.pop_segment() {
259                    Some((
260                        SubtreePathBuilder {
261                            base: self.base.clone(),
262                            relative: SubtreePathRelative::Multi(new_bytes),
263                        },
264                        key,
265                    ))
266                } else {
267                    self.base
268                        .derive_parent()
269                        .map(|(path, key)| (path.derive_owned(), key.to_vec()))
270                }
271            }
272        }
273    }
274
275    /// Get a derived path with a child path segment added.
276    pub fn derive_owned_with_child<'s, S>(&'b self, segment: S) -> SubtreePathBuilder<'b, B>
277    where
278        S: Into<CowLike<'s>>,
279        's: 'b,
280    {
281        SubtreePathBuilder {
282            base: SubtreePathInner::SubtreePath(self).into(),
283            relative: SubtreePathRelative::Single(segment.into()),
284        }
285    }
286
287    /// Returns an iterator for the subtree path by path segments.
288    pub fn reverse_iter(&'b self) -> SubtreePathIter<'b, B> {
289        match &self.relative {
290            SubtreePathRelative::Empty => self.base.clone().into_reverse_iter(),
291            SubtreePathRelative::Single(item) => {
292                SubtreePathIter::new_with_next(item.as_ref(), &self.base)
293            }
294            SubtreePathRelative::Multi(bytes) => {
295                SubtreePathIter::new_with_next(bytes.reverse_iter(), &self.base)
296            }
297        }
298    }
299
300    /// Collect path as a vector of vectors, but this actually negates all the
301    /// benefits of this library.
302    pub fn to_vec(&self) -> Vec<Vec<u8>> {
303        let mut result = Vec::new();
304
305        // Because of the nature of this library, the vector will be built
306        // from it's end
307        match &self.relative {
308            SubtreePathRelative::Empty => {}
309            SubtreePathRelative::Single(s) => result.push(s.to_vec()),
310            SubtreePathRelative::Multi(bytes) => {
311                bytes.reverse_iter().for_each(|s| result.push(s.to_vec()))
312            }
313        }
314
315        match &self.base.ref_variant {
316            SubtreePathInner::Slice(slice) => slice
317                .iter()
318                .rev()
319                .for_each(|x| result.push(x.as_ref().to_vec())),
320            SubtreePathInner::SubtreePath(path) => {
321                path.reverse_iter().for_each(|x| result.push(x.to_vec()))
322            }
323            SubtreePathInner::SubtreePathIter(iter) => {
324                iter.clone().for_each(|x| result.push(x.as_ref().to_vec()))
325            }
326        };
327
328        result.reverse();
329        result
330    }
331
332    /// Retuns `true` if the subtree path is empty, so it points to the root
333    /// tree.
334    pub fn is_root(&self) -> bool {
335        match self {
336            Self {
337                base,
338                relative: SubtreePathRelative::Empty,
339            } => base.is_root(),
340            _ => false,
341        }
342    }
343}
344
345#[cfg(test)]
346mod tests {
347    use super::*;
348
349    #[test]
350    fn to_vec() {
351        let base: SubtreePath<_> = (&[b"one" as &[u8], b"two", b"three"]).into();
352        let mut builder = base.derive_owned_with_child(b"four");
353        builder.push_segment(b"five");
354        builder.push_segment(b"six");
355        builder.push_segment(b"seven");
356
357        let as_vec = builder.to_vec();
358        let reference_vec = vec![
359            b"one".to_vec(),
360            b"two".to_vec(),
361            b"three".to_vec(),
362            b"four".to_vec(),
363            b"five".to_vec(),
364            b"six".to_vec(),
365            b"seven".to_vec(),
366        ];
367
368        assert_eq!(as_vec, reference_vec);
369        assert_eq!(builder.len(), reference_vec.len());
370    }
371}
grovedb_path/subtree_path_builder.rs

grovedb_path/
subtree_path_builder.rs
