grovedb_path/
lib.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//! GroveDB subtree path manipulation library.
30
31#![deny(missing_docs)]
32
33mod subtree_path;
34mod subtree_path_builder;
35mod subtree_path_iter;
36mod util;
37
38pub use subtree_path::SubtreePath;
39pub use subtree_path_builder::SubtreePathBuilder;
40pub use subtree_path_iter::SubtreePathIter;
41
42#[cfg(test)]
43mod tests {
44    use super::*;
45    use crate::util::calculate_hash;
46
47    fn assert_path_properties<B>(path: SubtreePath<'_, B>, reference: Vec<Vec<u8>>)
48    where
49        B: AsRef<[u8]> + std::fmt::Debug,
50    {
51        // Assert `to_vec`
52        assert_eq!(path.to_vec(), reference);
53
54        // Assert `into_reverse_iter`
55        assert!(path.clone().into_reverse_iter().eq(reference.iter().rev()));
56
57        // Assert equality
58        assert_eq!(path, SubtreePath::from(reference.as_slice()));
59
60        // Assert hashing done properly
61        let subtree_path_ref = SubtreePath::from(reference.as_slice());
62        let subtree_path_builder = subtree_path_ref.derive_owned();
63        assert_eq!(calculate_hash(&path), calculate_hash(&subtree_path_ref));
64        assert_eq!(calculate_hash(&path), calculate_hash(&subtree_path_builder));
65        assert_eq!(path.len(), reference.len());
66    }
67
68    #[test]
69    fn test_root_and_roots_child_derivation_slice() {
70        // Go two levels down just to complicate our test a bit:
71        let path_array = [b"one", b"two"];
72        let path = SubtreePath::from(path_array.as_ref());
73
74        let (root, child) = path.derive_parent().unwrap().0.derive_parent().unwrap();
75
76        assert_eq!(child, b"one");
77        assert_eq!(root.to_vec(), Vec::<&[u8]>::new());
78
79        assert_eq!(root.derive_parent(), None);
80    }
81
82    #[test]
83    fn test_root_and_roots_child_derivation_builder() {
84        let mut builder = SubtreePathBuilder::new();
85        builder.push_segment(b"one");
86        builder.push_segment(b"two");
87        let path: SubtreePath<[u8; 0]> = (&builder).into();
88
89        let (root, child) = path.derive_parent().unwrap().0.derive_parent().unwrap();
90
91        assert_eq!(child, b"one");
92        assert_eq!(root.to_vec(), Vec::<&[u8]>::new());
93
94        assert_eq!(root.derive_parent(), None);
95    }
96
97    #[test]
98    fn test_hashes_are_equal() {
99        let path_array = [
100            b"one".to_vec(),
101            b"two".to_vec(),
102            b"three".to_vec(),
103            b"four".to_vec(),
104            b"five".to_vec(),
105        ];
106        let path_array_refs = [
107            b"one".as_ref(),
108            b"two".as_ref(),
109            b"three".as_ref(),
110            b"four".as_ref(),
111            b"five".as_ref(),
112        ];
113        let path_base_slice_slices = SubtreePath::from(path_array_refs.as_ref());
114
115        let path_array_refs_six = [
116            b"one".as_ref(),
117            b"two".as_ref(),
118            b"three".as_ref(),
119            b"four".as_ref(),
120            b"five".as_ref(),
121            b"six".as_ref(),
122        ];
123        let path_base_slice_too_much = SubtreePath::from(path_array_refs_six.as_ref());
124        let path_base_unfinished = SubtreePath::from([b"one", b"two"].as_ref());
125        let path_empty = SubtreePathBuilder::new();
126
127        let path_derived_11 = path_empty.derive_owned_with_child(b"one".as_ref());
128        let path_derived_12 = path_derived_11.derive_owned_with_child(b"two".as_ref());
129        let path_derived_13 = path_derived_12.derive_owned_with_child(b"three".as_ref());
130        let path_derived_14 = path_derived_13.derive_owned_with_child(b"four".to_vec());
131        let path_derived_1 = path_derived_14.derive_owned_with_child(b"five".as_ref());
132
133        let (path_derived_2, _) = path_base_slice_too_much.derive_parent().unwrap();
134
135        let path_derived_31 = path_base_unfinished.derive_owned_with_child(b"three".to_vec());
136        let path_derived_32 = path_derived_31.derive_owned_with_child(b"four".as_ref());
137        let path_derived_3 = path_derived_32.derive_owned_with_child(b"five".as_ref());
138
139        assert_path_properties(path_base_slice_slices, path_array.to_vec());
140        assert_path_properties(SubtreePath::from(&path_derived_1), path_array.to_vec());
141        assert_path_properties(path_derived_2, path_array.to_vec());
142        assert_path_properties(SubtreePath::from(&path_derived_3), path_array.to_vec());
143    }
144
145    #[test]
146    fn test_is_root() {
147        let path_empty = SubtreePathBuilder::new();
148        assert!(path_empty.is_root());
149
150        let path_derived = path_empty.derive_owned_with_child(b"two".as_ref());
151        assert!(!path_derived.is_root());
152        assert!(path_derived.derive_parent().unwrap().0.is_root());
153
154        let path_not_empty = SubtreePath::from([b"one"].as_ref());
155        assert!(!path_not_empty.is_root());
156        assert!(path_not_empty.derive_parent().unwrap().0.is_root());
157    }
158
159    #[test]
160    fn test_complex_derivation() {
161        // Append only operations:
162        let base = SubtreePath::from([b"one", b"two"].as_ref());
163        let with_child_1 = base.derive_owned_with_child(b"three".to_vec());
164        let mut with_child_inplace = with_child_1.derive_owned_with_child(b"four");
165        with_child_inplace.push_segment(b"five");
166        with_child_inplace.push_segment(b"six");
167        with_child_inplace.push_segment(b"seven");
168        with_child_inplace.push_segment(b"eight");
169
170        // `with_child_inplace` should be like (substituted for digits for short):
171        // [1, 2] -> 3 -> [4, 5, 6, 7, 8]
172        assert_eq!(
173            with_child_inplace.reverse_iter().fold(0, |acc, _| acc + 1),
174            8
175        );
176        assert_path_properties(
177            (&with_child_inplace).into(),
178            vec![
179                b"one".to_vec(),
180                b"two".to_vec(),
181                b"three".to_vec(),
182                b"four".to_vec(),
183                b"five".to_vec(),
184                b"six".to_vec(),
185                b"seven".to_vec(),
186                b"eight".to_vec(),
187            ],
188        );
189
190        // Now go to ancestors (note that intermediate derivations are dropped and
191        // is still compiles, as [SubtreePath]s are intended for):
192        let points_five = with_child_inplace
193            .derive_parent()
194            .unwrap()
195            .0
196            .derive_parent()
197            .unwrap()
198            .0
199            .derive_parent()
200            .unwrap()
201            .0;
202
203        assert_path_properties(
204            points_five.clone(),
205            vec![
206                b"one".to_vec(),
207                b"two".to_vec(),
208                b"three".to_vec(),
209                b"four".to_vec(),
210                b"five".to_vec(),
211            ],
212        );
213
214        // And add a couple of other derivations
215        let after_five_1 = points_five.derive_owned_with_child(b"four");
216        let after_five_2 = after_five_1.derive_owned_with_child(b"twenty");
217        let mut after_five_3 = after_five_2.derive_owned();
218        after_five_3.push_segment(b"thirteen");
219        after_five_3.push_segment(b"thirtyseven");
220
221        // `after_five_3` should be like this:
222        // [1, 2] -> 3 -> [4, 5, 6, 7, 8]
223        //                    ^-> 4 -> 20 -> [13, 37]
224        assert_path_properties(
225            (&after_five_3).into(),
226            vec![
227                b"one".to_vec(),
228                b"two".to_vec(),
229                b"three".to_vec(),
230                b"four".to_vec(),
231                b"five".to_vec(),
232                b"four".to_vec(),
233                b"twenty".to_vec(),
234                b"thirteen".to_vec(),
235                b"thirtyseven".to_vec(),
236            ],
237        );
238    }
239}
grovedb_path/lib.rs

grovedb_path/
lib.rs
