willow_data_model/paths/mod.rs
1//! Functionality around Willow [Paths](https://willowprotocol.org/specs/data-model/index.html#Path).
2//!
3//! The central type of this module is the [`Path`] struct, which represents a single willow Path. [`Paths`](Path) are *immutable*, which means any operation that would traditionally mutate paths (for example, appending a new component) returns a new, independent value instead.
4//!
5//! The [`Path`] struct is generic over three const generic parameters, corresponding to the Willow parameters which limit the size of paths:
6//!
7//! - the `MCL` parameter gives the ([max\_component\_length](https://willowprotocol.org/specs/data-model/index.html#max_component_length)),
8//! - the `MCC` parameter gives the ([max\_component\_count](https://willowprotocol.org/specs/data-model/index.html#max_component_count)), and
9//! - the `MPL` parameter gives the ([max\_path\_length](https://willowprotocol.org/specs/data-model/index.html#max_path_length)).
10//!
11//! All (safely created) [`Paths`](Path)respect those parameters. The functions in this module return [`PathErrors`](PathError) or [`PathFromComponentsErrors`](PathFromComponentsError) when those invariants would be violated.
12//!
13//! The type-level docs of [`Path`] list all the ways in which you can build up paths dynamically.
14//!
15//! The [`Path`] struct provides methods for checking various properties of paths: from simple properties ("[how many components does this have](Path::component_count)") to various comparisons ("[is this path a prefix of some other](Path::is_prefix_of)"), the methods should have you covered.
16//!
17//! Because [path prefixes](https://willowprotocol.org/specs/data-model/index.html#path_prefix) play such a [central role for deletion](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning) in Willow, the functionality around prefixes is optimised. [Creating a prefix](Path::create_prefix) or even iterating over [all prefixes](Path::all_prefixes) performs no memory allocations.
18//!
19//! The [`Component`] type represents individual path [Components](https://willowprotocol.org/specs/data-model/index.html#Component). This type is a thin wrapper around `[u8]` (enforcing a maximal length of `MCL` bytes); like `[u8]` it must always be used as part of a pointer type — for example, `&Component<MCL>`. Alternatively, the [`OwnedComponent`] type can be used by itself — keeping an [`OwnedComponent`] alive will also keep around the heap allocation for the full [`Path`] from which it was constructed, though. Generally speaking, the more lightweight [`Component`] should be preferred over [`OwnedComponent`] where possible.
20
21#[cfg(feature = "dev")]
22use arbitrary::{Arbitrary, Error as ArbitraryError, Unstructured, size_hint::and_all};
23use derive_more::{Display, Error};
24use order_theory::{
25 GreatestElement, LeastElement, LowerSemilattice, PredecessorExceptForLeast,
26 SuccessorExceptForGreatest, TryPredecessor, TrySuccessor, UpperSemilattice,
27};
28
29// The `Path` struct is tested in `fuzz/path.rs`, `fuzz/path2.rs`, `fuzz/path3.rs`, `fuzz/path3.rs` by comparing against a non-optimised reference implementation.
30// Further, the `successor` and `greater_but_not_prefixed` methods of that reference implementation are tested in `fuzz/path_successor.rs` and friends, and `fuzz/path_successor_of_prefix.rs` and friends.
31
32use core::cmp::Ordering;
33use core::fmt::Debug;
34use core::hash::Hash;
35use core::mem::size_of;
36use core::ops::RangeBounds;
37use core::{convert::AsRef, fmt};
38
39use bytes::{BufMut, Bytes, BytesMut};
40
41mod builder;
42pub use builder::PathBuilder;
43
44mod representation;
45use representation::Representation;
46
47mod component;
48pub use component::*;
49
50mod codec;
51pub use codec::*;
52
53pub mod private;
54
55/// An error arising from trying to construct an invalid [`Path`] from valid [`Component`]s.
56///
57/// #### Examples
58///
59/// ```
60/// use willow_data_model::prelude::*;
61/// assert_eq!(
62/// Path::<4, 4, 2>::from_component(Component::new(b"oops").unwrap()),
63/// Err(PathFromComponentsError::PathTooLong),
64/// );
65/// assert_eq!(
66/// Path::<4, 1, 9>::from_components(&[
67/// Component::new(b"").unwrap(),
68/// Component::new(b"").unwrap()
69/// ]),
70/// Err(PathFromComponentsError::TooManyComponents),
71/// );
72/// ```
73#[derive(Debug, Display, Error, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
74pub enum PathFromComponentsError {
75 /// The [`Path`]'s total length in bytes would have been greater than the [max\_path\_length](https://willowprotocol.org/specs/data-model/index.html#max_path_length).
76 #[display("total path length exceeded maximum")]
77 PathTooLong,
78 /// The [`Path`] would have had more [`Component`] than the [max\_component\_count](https://willowprotocol.org/specs/data-model/index.html#max_component_count).
79 #[display("number of components exceeded maximum")]
80 TooManyComponents,
81}
82
83/// An error arising from trying to construct an invalid [`Path`].
84///
85/// #### Examples
86///
87/// ```
88/// use willow_data_model::prelude::*;
89/// assert_eq!(Path::<4, 4, 2>::from_slice(b"oops"), Err(PathError::PathTooLong));
90/// assert_eq!(Path::<2, 2, 9>::from_slices(&[b"", b"", b""]), Err(PathError::TooManyComponents));
91/// assert_eq!(Path::<4, 4, 9>::from_slice(b"oopsie"), Err(PathError::ComponentTooLong));
92/// ```
93#[derive(Debug, Display, Error, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
94pub enum PathError {
95 /// The [`Path`]'s total length in bytes would have been greater than the [max\_path\_length](https://willowprotocol.org/specs/data-model/index.html#max_path_length).
96 #[display("total path length exceeded maximum")]
97 PathTooLong,
98 /// The [`Path`] would have had more [`Component`] than the [max\_component\_count](https://willowprotocol.org/specs/data-model/index.html#max_component_count).
99 #[display("number of components exceeded maximum")]
100 TooManyComponents,
101 /// The [`Path`] would have contained a [`Component`] of length greater than the [max\_component\_length](https://willowprotocol.org/specs/data-model/index.html#max_component_length)
102 #[display("length of a component exceeded maximum")]
103 ComponentTooLong,
104}
105
106impl From<PathFromComponentsError> for PathError {
107 fn from(value: PathFromComponentsError) -> Self {
108 match value {
109 PathFromComponentsError::PathTooLong => Self::PathTooLong,
110 PathFromComponentsError::TooManyComponents => Self::TooManyComponents,
111 }
112 }
113}
114
115impl From<InvalidComponentError> for PathError {
116 fn from(_value: InvalidComponentError) -> Self {
117 Self::ComponentTooLong
118 }
119}
120
121/// An immutable Willow [Path](https://willowprotocol.org/specs/data-model/index.html#Path). Thread-safe, cheap to clone, cheap to take prefixes of, expensive to append to (linear time complexity).
122///
123/// A Willow Path is any sequence of bytestrings — called [Components](https://willowprotocol.org/specs/data-model/index.html#Component) — fulfilling certain constraints:
124///
125/// - each [`Component`] has a length of at most `MCL` ([max\_component\_length](https://willowprotocol.org/specs/data-model/index.html#max_component_length)),
126/// - each [`Path`] has at most `MCC` ([max\_component\_count](https://willowprotocol.org/specs/data-model/index.html#max_component_count)) components, and
127/// - the total size in bytes of all [`Component`]s is at most `MPL` ([max\_path\_length](https://willowprotocol.org/specs/data-model/index.html#max_path_length)).
128///
129/// This type statically enforces these invariants for all (safely) created instances.
130///
131/// Because appending [`Component`]s takes time linear in the length of the full [`Path`], you should not build up [`Path`]s this way. Instead, use [`Path::from_components`], [`Path::from_slices`], [`Path::from_components_iter`], [`Path::from_slices_iter`], or a [`PathBuilder`].
132///
133/// ```
134/// use willow_data_model::prelude::*;
135/// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
136///
137/// assert_eq!(p.component_count(), 2);
138/// assert_eq!(p.component(1), Some(Component::new(b"ho")?));
139/// assert_eq!(p.total_length(), 4);
140/// assert!(p.is_prefixed_by(&Path::from_slice(b"hi")?));
141/// assert_eq!(
142/// p.longest_common_prefix(&Path::from_slices(&[b"hi", b"he"])?),
143/// Path::from_slice(b"hi")?
144/// );
145/// # Ok::<(), PathError>(())
146/// ```
147#[derive(Clone)]
148pub struct Path<const MCL: usize, const MCC: usize, const MPL: usize> {
149 /// The data of the underlying path.
150 data: Bytes,
151 /// The first component of the `data` to consider for this particular path. Must be less than or equal to the total number of components in `data`.
152 /// This field, with `component_count`, enables cheap slicing and suffix creation by cloning the heap data.
153 first_component: usize,
154 /// Number of components of the `data` to consider for this particular path (starting from the `first_component`). Must be less than or equal to the total number of components minus the `first_component` offset.
155 /// This field enables cheap prefix creation by cloning the heap data (which is reference counted) and adjusting the `component_count`.
156 component_count: usize,
157}
158
159/// The default [`Path`] is the empty [`Path`].
160impl<const MCL: usize, const MCC: usize, const MPL: usize> Default for Path<MCL, MCC, MPL> {
161 /// Returns an empty [`Path`].
162 ///
163 /// #### Examples
164 ///
165 /// ```
166 /// use willow_data_model::prelude::*;
167 /// assert_eq!(Path::<4, 4, 4>::default().component_count(), 0);
168 /// assert_eq!(Path::<4, 4, 4>::default(), Path::<4, 4, 4>::new());
169 /// ```
170 fn default() -> Self {
171 Self::new()
172 }
173}
174
175impl<const MCL: usize, const MCC: usize, const MPL: usize> Path<MCL, MCC, MPL> {
176 /// Returns an empty [`Path`], i.e., a [`Path`] of zero [`Component`]s.
177 ///
178 /// #### Complexity
179 ///
180 /// Runs in `O(1)`.
181 ///
182 /// #### Examples
183 ///
184 /// ```
185 /// use willow_data_model::prelude::*;
186 /// assert_eq!(Path::<4, 4, 4>::new().component_count(), 0);
187 /// assert_eq!(Path::<4, 4, 4>::new(), Path::<4, 4, 4>::default());
188 /// ```
189 pub fn new() -> Self {
190 PathBuilder::new(0, 0)
191 .expect("empty path is legal for every choice of of MCL, MCC, and MPL")
192 .build()
193 }
194
195 /// Creates a singleton [`Path`], consisting of exactly one [`Component`].
196 ///
197 /// Copies the bytes of the [`Component`] into an owned allocation on the heap.
198 ///
199 /// #### Complexity
200 ///
201 /// Runs in `O(n)`, where `n` is the length of the [`Component`]. Performs a single allocation of `O(n)` bytes.
202 ///
203 /// #### Examples
204 ///
205 /// ```
206 /// use willow_data_model::prelude::*;
207 /// let p = Path::<4, 4, 4>::from_component(Component::new(b"hi!")?)?;
208 /// assert_eq!(p.component_count(), 1);
209 ///
210 /// assert_eq!(
211 /// Path::<4, 4, 2>::from_component(Component::new(b"hi!")?),
212 /// Err(PathFromComponentsError::PathTooLong),
213 /// );
214 /// # Ok::<(), PathError>(())
215 /// ```
216 pub fn from_component(comp: &Component<MCL>) -> Result<Self, PathFromComponentsError> {
217 let mut builder = PathBuilder::new(comp.as_ref().len(), 1)?;
218 builder.append_component(comp);
219 Ok(builder.build())
220 }
221
222 /// Creates a singleton [`Path`], consisting of exactly one [`Component`], from a raw slice of bytes.
223 ///
224 /// Copies the bytes into an owned allocation on the heap.
225 ///
226 /// #### Complexity
227 ///
228 /// Runs in `O(n)`, where `n` is the length of the [`Component`]. Performs a single allocation of `O(n)` bytes.
229 ///
230 /// #### Examples
231 ///
232 /// ```
233 /// use willow_data_model::prelude::*;
234 /// let p = Path::<4, 4, 4>::from_slice(b"hi!")?;
235 /// assert_eq!(p.component_count(), 1);
236 ///
237 /// assert_eq!(
238 /// Path::<4, 4, 4>::from_slice(b"too_long_for_single_component"),
239 /// Err(PathError::ComponentTooLong),
240 /// );
241 /// assert_eq!(
242 /// Path::<4, 3, 1>::from_slice(b"nope"),
243 /// Err(PathError::PathTooLong),
244 /// );
245 /// # Ok::<(), PathError>(())
246 /// ```
247 pub fn from_slice(comp: &[u8]) -> Result<Self, PathError> {
248 Ok(Self::from_component(Component::new(comp)?)?)
249 }
250
251 /// Creates a [`Path`] from a slice of [`Component`]s.
252 ///
253 /// Copies the bytes of the [`Component`]s into an owned allocation on the heap.
254 ///
255 /// #### Complexity
256 ///
257 /// Runs in `O(n + m)`, where `n` is the total length of the created [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
258 ///
259 /// #### Examples
260 ///
261 /// ```
262 /// use willow_data_model::prelude::*;
263 /// let components: Vec<&Component<4>> = vec![
264 /// &Component::new(b"hi")?,
265 /// &Component::new(b"!")?,
266 /// ];
267 ///
268 /// assert!(Path::<4, 4, 4>::from_components(&components[..]).is_ok());
269 /// # Ok::<(), PathError>(())
270 /// ```
271 pub fn from_components(
272 components: &[&Component<MCL>],
273 ) -> Result<Self, PathFromComponentsError> {
274 let mut total_length = 0;
275 for comp in components {
276 total_length += comp.as_ref().len();
277 }
278
279 Self::from_components_iter(total_length, &mut components.iter().cloned())
280 }
281
282 /// Create a new [`Path`] from a slice of byte slices.
283 ///
284 /// #### Complexity
285 ///
286 /// Runs in `O(n + m)`, where `n` is the total length of the created [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
287 ///
288 /// # Example
289 ///
290 /// ```
291 /// use willow_data_model::prelude::*;
292 /// // Ok
293 /// let path = Path::<12, 3, 30>::from_slices(&[b"alfie", b"notes"]).unwrap();
294 ///
295 /// // Err
296 /// let result1 = Path::<12, 3, 30>::from_slices(&[b"themaxpath", b"lengthis30", b"thisislonger"]);
297 /// assert_eq!(result1, Err(PathError::PathTooLong));
298 ///
299 /// // Err
300 /// let result2 = Path::<12, 3, 30>::from_slices(&[b"too", b"many", b"components", b"error"]);
301 /// assert_eq!(result2, Err(PathError::TooManyComponents));
302 ///
303 /// // Err
304 /// let result3 = Path::<12, 3, 30>::from_slices(&[b"overencumbered"]);
305 /// assert_eq!(result3, Err(PathError::ComponentTooLong));
306 /// ```
307 pub fn from_slices(slices: &[&[u8]]) -> Result<Self, PathError> {
308 let total_length = slices.iter().map(|it| it.as_ref().len()).sum();
309 let mut builder = PathBuilder::new(total_length, slices.len())?;
310
311 for component_slice in slices {
312 builder.append_slice(component_slice.as_ref())?;
313 }
314
315 Ok(builder.build())
316 }
317
318 /// Creates a [`Path`] of known total length from an [`ExactSizeIterator`] of [`Component`]s.
319 ///
320 /// Copies the bytes of the [`Component`]s into an owned allocation on the heap.
321 ///
322 /// Panics if the claimed `total_length` does not match the sum of the lengths of all the [`Component`]s.
323 ///
324 /// #### Complexity
325 ///
326 /// Runs in `O(n + m)`, where `n` is the total length of the created [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
327 ///
328 /// #### Examples
329 ///
330 /// ```
331 /// use willow_data_model::prelude::*;
332 /// let components: Vec<&Component<4>> = vec![
333 /// &Component::new(b"hi")?,
334 /// &Component::new(b"!")?,
335 /// ];
336 ///
337 /// assert!(Path::<4, 4, 4>::from_components_iter(3, &mut components.into_iter()).is_ok());
338 /// # Ok::<(), PathError>(())
339 /// ```
340 pub fn from_components_iter<'c, I>(
341 total_length: usize,
342 iter: &mut I,
343 ) -> Result<Self, PathFromComponentsError>
344 where
345 I: ExactSizeIterator<Item = &'c Component<MCL>>,
346 {
347 let mut builder = PathBuilder::new(total_length, iter.len())?;
348
349 for component in iter {
350 builder.append_component(component);
351 }
352
353 Ok(builder.build())
354 }
355
356 /// Creates a [`Path`] of known total length from an [`ExactSizeIterator`] of byte slices.
357 ///
358 /// Copies the bytes of the [`Component`]s into an owned allocation on the heap.
359 ///
360 /// Panics if the claimed `total_length` does not match the sum of the lengths of all the [`Component`]s.
361 ///
362 /// #### Complexity
363 ///
364 /// Runs in `O(n + m)`, where `n` is the total length of the created [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
365 ///
366 /// #### Examples
367 ///
368 /// ```
369 /// use willow_data_model::prelude::*;
370 /// let components: Vec<&[u8]> = vec![b"hi", b"!"];
371 /// assert!(Path::<4, 4, 4>::from_slices_iter(3, &mut components.into_iter()).is_ok());
372 /// # Ok::<(), PathError>(())
373 /// ```
374 pub fn from_slices_iter<'a, I>(total_length: usize, iter: &mut I) -> Result<Self, PathError>
375 where
376 I: ExactSizeIterator<Item = &'a [u8]>,
377 {
378 let mut builder = PathBuilder::new(total_length, iter.len())?;
379
380 for slice in iter {
381 builder.append_slice(slice.as_ref())?;
382 }
383
384 Ok(builder.build())
385 }
386
387 /// Creates a new [`Path`] by appending a [`Component`] to `&self`.
388 ///
389 /// Creates a fully separate copy of the new data on the heap; which includes cloning all data in `&self`. To efficiently construct [`Path`]s, use [`Path::from_components`], [`Path::from_slices`], [`Path::from_components_iter`], [`Path::from_slices_iter`], or a [`PathBuilder`].
390 ///
391 /// #### Complexity
392 ///
393 /// Runs in `O(n + m)`, where `n` is the total length of the resulting [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
394 ///
395 /// #### Examples
396 ///
397 /// ```
398 /// use willow_data_model::prelude::*;
399 /// let p0: Path<4, 4, 4> = Path::new();
400 /// let p1 = p0.append_component(Component::new(b"hi")?)?;
401 /// let p2 = p1.append_component(Component::new(b"!")?)?;
402 /// assert_eq!(
403 /// p2.append_component(Component::new(b"no!")?),
404 /// Err(PathFromComponentsError::PathTooLong),
405 /// );
406 /// # Ok::<(), PathError>(())
407 /// ```
408 pub fn append_component(&self, comp: &Component<MCL>) -> Result<Self, PathFromComponentsError> {
409 let mut builder = PathBuilder::new(
410 self.total_length() + comp.as_ref().len(),
411 self.component_count() + 1,
412 )?;
413
414 for component in self.components() {
415 builder.append_component(component);
416 }
417 builder.append_component(comp);
418
419 Ok(builder.build())
420 }
421
422 /// Creates a new [`Path`] by appending a [`Component`] to `&self`.
423 ///
424 /// Creates a fully separate copy of the new data on the heap; which includes cloning all data in `&self`. To efficiently construct [`Path`]s, use [`Path::from_components`], [`Path::from_slices`], [`Path::from_components_iter`], [`Path::from_slices_iter`], or a [`PathBuilder`].
425 ///
426 /// #### Complexity
427 ///
428 /// Runs in `O(n + m)`, where `n` is the total length of the resulting [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
429 ///
430 /// #### Examples
431 ///
432 /// ```
433 /// use willow_data_model::prelude::*;
434 /// let p0: Path<4, 4, 4> = Path::new();
435 /// let p1 = p0.append_slice(b"hi")?;
436 /// let p2 = p1.append_slice(b"!")?;
437 /// assert_eq!(
438 /// p2.append_slice(b"no!"),
439 /// Err(PathError::PathTooLong),
440 /// );
441 /// # Ok::<(), PathError>(())
442 /// ```
443 pub fn append_slice(&self, comp: &[u8]) -> Result<Self, PathError> {
444 Ok(self.append_component(Component::new(comp)?)?)
445 }
446
447 /// Creates a new [`Path`] by appending a slice of [`Component`]s to `&self`.
448 ///
449 /// Creates a fully separate copy of the new data on the heap; which includes cloning all data in `&self`. To efficiently construct [`Path`]s, use [`Path::from_components`], [`Path::from_slices`], [`Path::from_components_iter`], [`Path::from_slices_iter`], or a [`PathBuilder`].
450 ///
451 /// #### Complexity
452 ///
453 /// Runs in `O(n + m)`, where `n` is the total length of the resulting [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
454 ///
455 /// #### Examples
456 ///
457 /// ```
458 /// use willow_data_model::prelude::*;
459 /// let p0: Path<4, 4, 4> = Path::new();
460 /// let p1 = p0.append_components(&[Component::new(b"hi")?, Component::new(b"!")?])?;
461 /// assert_eq!(
462 /// p1.append_components(&[Component::new(b"no!")?]),
463 /// Err(PathFromComponentsError::PathTooLong),
464 /// );
465 /// # Ok::<(), PathError>(())
466 /// ```
467 pub fn append_components(
468 &self,
469 components: &[&Component<MCL>],
470 ) -> Result<Self, PathFromComponentsError> {
471 let mut total_length = self.total_length();
472 for comp in components {
473 total_length += comp.as_ref().len();
474 }
475
476 let mut builder = PathBuilder::new_from_prefix(
477 total_length,
478 self.component_count() + components.len(),
479 self,
480 self.component_count(),
481 )?;
482
483 for additional_component in components {
484 builder.append_component(*additional_component);
485 }
486
487 Ok(builder.build())
488 }
489
490 /// Creates a new [`Path`] by appending a slice of [`Component`]s to `&self`.
491 ///
492 /// Creates a fully separate copy of the new data on the heap; which includes cloning all data in `&self`. To efficiently construct [`Path`]s, use [`Path::from_components`], [`Path::from_slices`], [`Path::from_components_iter`], [`Path::from_slices_iter`], or a [`PathBuilder`].
493 ///
494 /// #### Complexity
495 ///
496 /// Runs in `O(n + m)`, where `n` is the total length of the resulting [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
497 ///
498 /// #### Examples
499 ///
500 /// ```
501 /// use willow_data_model::prelude::*;
502 /// let p0: Path<4, 4, 4> = Path::new();
503 /// let p1 = p0.append_slices(&[b"hi", b"ho"])?;
504 /// assert_eq!(
505 /// p1.append_slices(&[b"no!"]),
506 /// Err(PathError::PathTooLong),
507 /// );
508 /// # Ok::<(), PathError>(())
509 /// ```
510 pub fn append_slices(&self, components: &[&[u8]]) -> Result<Self, PathError> {
511 let mut total_length = self.total_length();
512 for comp in components {
513 total_length += comp.as_ref().len();
514 }
515
516 let mut builder = PathBuilder::new_from_prefix(
517 total_length,
518 self.component_count() + components.len(),
519 self,
520 self.component_count(),
521 )?;
522
523 for additional_component in components {
524 builder.append_slice(additional_component.as_ref())?;
525 }
526
527 Ok(builder.build())
528 }
529
530 /// Creates a new [`Path`] by appending another [`Path`] to `&self`.
531 ///
532 /// Creates a fully separate copy of the new data on the heap; which includes cloning all data in `&self` and in `&other`.
533 ///
534 /// #### Complexity
535 ///
536 /// Runs in `O(n + m)`, where `n` is the total length of the resulting [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
537 ///
538 /// #### Examples
539 ///
540 /// ```
541 /// use willow_data_model::prelude::*;
542 /// let p0: Path<4, 4, 4> = Path::new();
543 /// let p1 = p0.append_path(&Path::from_slices(&[b"hi", b"ho"])?)?;
544 /// assert_eq!(
545 /// p1.append_path(&Path::from_slice(b"no!")?),
546 /// Err(PathFromComponentsError::PathTooLong),
547 /// );
548 /// # Ok::<(), PathError>(())
549 /// ```
550 pub fn append_path(
551 &self,
552 other: &Path<MCL, MCC, MPL>,
553 ) -> Result<Self, PathFromComponentsError> {
554 let total_length = self.total_length() + other.total_length();
555
556 let mut builder = PathBuilder::new_from_prefix(
557 total_length,
558 self.component_count() + other.component_count(),
559 self,
560 self.component_count(),
561 )?;
562
563 for additional_component in other.components() {
564 builder.append_component(additional_component);
565 }
566
567 Ok(builder.build())
568 }
569
570 /// Returns the least [`Path`] which is strictly greater (lexicographically) than `self` and which is not [prefixed by](https://willowprotocol.org/specs/data-model/index.html#path_prefix) `self`; or [`None`] if no such [`Path`] exists.
571 ///
572 /// #### Complexity
573 ///
574 /// Runs in `O(n + m)`, where `n` is the total length of the [`Path`] in bytes, and `m` is the number of [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
575 pub fn greater_but_not_prefixed(&self) -> Option<Self> {
576 // We iterate through all components in reverse order. For each component, we check whether we can replace it by another cmponent that is strictly greater but not prefixed by the original component. If that is possible, we do replace it with the least such component and drop all later components. If that is impossible, we try again with the previous component. If this impossible for all components, then this function returns `None`.
577
578 for (i, component) in self.components().enumerate().rev() {
579 // If it is possible to append a zero byte to a component, then doing so yields its successor.
580
581 let prefix_length = Representation::sum_of_lengths_for_component(
582 self.data.as_ref(),
583 i + self.first_component,
584 ) - match self.first_component {
585 0 => 0,
586 offset => {
587 Representation::sum_of_lengths_for_component(self.data.as_ref(), offset - 1)
588 }
589 };
590
591 if component.len() < MCL && prefix_length < MPL {
592 let mut buf = clone_prefix_and_lengthen_final_component(
593 &self.data,
594 i,
595 1,
596 self.first_component,
597 );
598 buf.put_u8(0);
599
600 return Some(Path {
601 data: buf.freeze(),
602 component_count: i + 1,
603 first_component: 0,
604 });
605 }
606
607 // Next, we check whether the i-th component can be changed into the least component that is greater but not prefixed by the original. If so, do that and cut off all later components.
608 let mut next_component_length = None;
609 for (j, comp_byte) in component.iter().enumerate().rev() {
610 if *comp_byte < 255 {
611 next_component_length = Some(j + 1);
612 break;
613 }
614 }
615
616 if let Some(next_component_length) = next_component_length {
617 // Yay, we can replace the i-th comopnent and then we are done.
618
619 let mut buf = clone_prefix_and_lengthen_final_component(
620 &self.data,
621 i,
622 0,
623 self.first_component,
624 );
625 let length_of_prefix = Representation::sum_of_lengths_for_component(&buf, i);
626
627 // Update the length of the final component.
628 buf_set_final_component_length(
629 buf.as_mut(),
630 i,
631 length_of_prefix - (component.len() - next_component_length),
632 );
633
634 // Increment the byte at position `next_component_length` of the final component.
635 let offset = Representation::start_offset_of_component(buf.as_ref(), i)
636 + next_component_length
637 - 1;
638 let byte = buf.as_ref()[offset]; // guaranteed < 255...
639 buf.as_mut()[offset] = byte + 1; // ... hence no overflow here.
640
641 return Some(Path {
642 data: buf.freeze(),
643 component_count: i + 1,
644 first_component: 0,
645 });
646 }
647 }
648
649 None
650 }
651
652 /// Returns the number of [`Component`]s in `&self`.
653 ///
654 /// Guaranteed to be at most `MCC`.
655 ///
656 /// #### Complexity
657 ///
658 /// Runs in `O(1)`, performs no allocations.
659 ///
660 /// #### Examples
661 ///
662 /// ```
663 /// use willow_data_model::prelude::*;
664 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
665 /// assert_eq!(p.component_count(), 2);
666 /// # Ok::<(), PathError>(())
667 /// ```
668 pub fn component_count(&self) -> usize {
669 self.component_count
670 }
671
672 /// Returns whether `&self` has zero [`Component`]s.
673 ///
674 /// #### Complexity
675 ///
676 /// Runs in `O(1)`, performs no allocations.
677 ///
678 /// #### Examples
679 ///
680 /// ```
681 /// use willow_data_model::prelude::*;
682 /// assert_eq!(Path::<4, 4, 4>::new().is_empty(), true);
683 ///
684 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
685 /// assert_eq!(p.is_empty(), false);
686 /// # Ok::<(), PathError>(())
687 /// ```
688 pub fn is_empty(&self) -> bool {
689 self.component_count() == 0
690 }
691
692 /// Returns the sum of the lengths of all [`Component`]s in `&self`.
693 ///
694 /// Guaranteed to be at most `MCC`.
695 ///
696 /// #### Complexity
697 ///
698 /// Runs in `O(1)`, performs no allocations.
699 ///
700 /// #### Examples
701 ///
702 /// ```
703 /// use willow_data_model::prelude::*;
704 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
705 /// assert_eq!(p.total_length(), 4);
706 /// # Ok::<(), PathError>(())
707 /// ```
708 pub fn total_length(&self) -> usize {
709 self.total_length_of_prefix(self.component_count())
710 }
711
712 /// Returns the sum of the lengths of the first `i` [`Component`]s in `&self`; panics if `i >= self.component_count()`. More efficient than `path.create_prefix(i).path_length()`.
713 ///
714 /// Guaranteed to be at most `MCC`.
715 ///
716 /// #### Complexity
717 ///
718 /// Runs in `O(1)`, performs no allocations.
719 ///
720 /// #### Examples
721 ///
722 /// ```
723 /// use willow_data_model::prelude::*;
724 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
725 /// assert_eq!(p.total_length_of_prefix(0), 0);
726 /// assert_eq!(p.total_length_of_prefix(1), 2);
727 /// assert_eq!(p.total_length_of_prefix(2), 4);
728 /// # Ok::<(), PathError>(())
729 /// ```
730 pub fn total_length_of_prefix(&self, i: usize) -> usize {
731 let size_offset = Representation::total_length(&self.data, self.first_component);
732
733 Representation::total_length(&self.data, i + self.first_component) - size_offset
734 }
735
736 /// Tests whether `&self` is a [prefix](https://willowprotocol.org/specs/data-model/index.html#path_prefix) of the given [`Path`].
737 /// [`Path`]s are always a prefix of themselves, and the empty [`Path`] is a prefix of every [`Path`].
738 ///
739 /// #### Complexity
740 ///
741 /// Runs in `O(n + m)`, where `n` is the total length of the longer [`Path`] in bytes, and `m` is the greatest number of [`Component`]s.
742 ///
743 /// #### Examples
744 ///
745 /// ```
746 /// use willow_data_model::prelude::*;
747 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
748 /// assert!(Path::new().is_prefix_of(&p));
749 /// assert!(Path::from_slice(b"hi")?.is_prefix_of(&p));
750 /// assert!(Path::from_slices(&[b"hi", b"ho"])?.is_prefix_of(&p));
751 /// assert!(!Path::from_slices(&[b"hi", b"gh"])?.is_prefix_of(&p));
752 /// # Ok::<(), PathError>(())
753 /// ```
754 pub fn is_prefix_of(&self, other: &Self) -> bool {
755 self.prefix_cmp(other)
756 .map(|ord| ord.is_le())
757 .unwrap_or(false)
758 }
759
760 /// Tests whether `&self` is [prefixed by](https://willowprotocol.org/specs/data-model/index.html#path_prefix) the given [`Path`].
761 /// [`Path`]s are always prefixed by themselves, and by the empty [`Path`].
762 ///
763 /// #### Complexity
764 ///
765 /// Runs in `O(n + m)`, where `n` is the total length of the longer [`Path`] in bytes, and `m` is the greatest number of [`Component`]s.
766 ///
767 /// #### Examples
768 ///
769 /// ```
770 /// use willow_data_model::prelude::*;
771 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
772 /// assert!(p.is_prefixed_by(&Path::new()));
773 /// assert!(p.is_prefixed_by(&Path::from_slice(b"hi")?));
774 /// assert!(p.is_prefixed_by(&Path::from_slices(&[b"hi", b"ho"])?));
775 /// assert!(!p.is_prefixed_by(&Path::from_slices(&[b"hi", b"gh"])?));
776 /// # Ok::<(), PathError>(())
777 /// ```
778 pub fn is_prefixed_by(&self, other: &Self) -> bool {
779 other.is_prefix_of(self)
780 }
781
782 /// Tests whether `&self` is [related](https://willowprotocol.org/specs/data-model/index.html#path_related) to the given [`Path`], that is, whether either one is a [prefix](https://willowprotocol.org/specs/data-model/index.html#path_prefix) of the other.
783 ///
784 /// #### Complexity
785 ///
786 /// Runs in `O(n + m)`, where `n` is the total length of the longer [`Path`] in bytes, and `m` is the greatest number of [`Component`]s.
787 ///
788 /// #### Examples
789 ///
790 /// ```
791 /// use willow_data_model::prelude::*;
792 /// let p: Path<4, 4, 4> = Path::from_slice(b"hi")?;
793 /// assert!(p.is_related_to(&Path::new()));
794 /// assert!(p.is_related_to(&Path::from_slice(b"hi")?));
795 /// assert!(p.is_related_to(&Path::from_slices(&[b"hi", b"ho"])?));
796 /// assert!(!p.is_related_to(&Path::from_slices(&[b"no"])?));
797 /// # Ok::<(), PathError>(())
798 /// ```
799 pub fn is_related_to(&self, other: &Self) -> bool {
800 self.prefix_cmp(other).is_some()
801 }
802
803 /// Returns the [`Ordering`] describing the prefix relation between `self` and `other`.
804 ///
805 /// #### Complexity
806 ///
807 /// Runs in `O(n + m)`, where `n` is the total length of the longer [`Path`] in bytes, and `m` is the greatest number of [`Component`]s.
808 ///
809 /// #### Examples
810 ///
811 /// ```
812 /// use core::cmp::Ordering;
813 /// use willow_data_model::prelude::*;
814 /// let p: Path<4, 4, 4> = Path::from_slice(b"hi")?;
815 /// assert_eq!(p.prefix_cmp(&Path::new()), Some(Ordering::Greater));
816 /// assert_eq!(p.prefix_cmp(&Path::from_slice(b"hi")?), Some(Ordering::Equal));
817 /// assert_eq!(p.prefix_cmp(&Path::from_slices(&[b"hi", b"ho"])?), Some(Ordering::Less));
818 /// assert_eq!(p.prefix_cmp(&Path::from_slice(b"no")?), None);
819 /// # Ok::<(), PathError>(())
820 /// ```
821 pub fn prefix_cmp(&self, other: &Self) -> Option<Ordering> {
822 for (comp_a, comp_b) in self.components().zip(other.components()) {
823 if comp_a != comp_b {
824 return None;
825 }
826 }
827
828 self.component_count().partial_cmp(&other.component_count())
829 }
830
831 /// Returns the `i`-th [`Component`] of `&self`.
832 ///
833 /// #### Complexity
834 ///
835 /// Runs in `O(1)`, performs no allocations.
836 ///
837 /// #### Examples
838 ///
839 /// ```
840 /// use willow_data_model::prelude::*;
841 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
842 /// assert_eq!(p.component(0), Some(Component::new(b"hi")?));
843 /// assert_eq!(p.component(1), Some(Component::new(b"ho")?));
844 /// assert_eq!(p.component(2), None);
845 /// # Ok::<(), PathError>(())
846 /// ```
847 pub fn component(&self, i: usize) -> Option<&Component<MCL>> {
848 if i < self.component_count {
849 Some(Representation::component(
850 &self.data,
851 i + self.first_component,
852 ))
853 } else {
854 None
855 }
856 }
857
858 /// Returns the `i`-th [`Component`] of `&self`, without checking whether `i < self.component_count()`.
859 ///
860 /// #### Safety
861 ///
862 /// Undefined behaviour if `i >= self.component_count()`.
863 ///
864 /// #### Complexity
865 ///
866 /// Runs in `O(1)`, performs no allocations.
867 ///
868 /// #### Examples
869 ///
870 /// ```
871 /// use willow_data_model::prelude::*;
872 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
873 /// assert_eq!(unsafe { p.component_unchecked(0) }, Component::new(b"hi")?);
874 /// assert_eq!(unsafe { p.component_unchecked(1) }, Component::new(b"ho")?);
875 /// # Ok::<(), PathError>(())
876 /// ```
877 pub unsafe fn component_unchecked(&self, i: usize) -> &Component<MCL> {
878 Representation::component(&self.data, i + self.first_component)
879 }
880
881 /// Returns an [owned handle](OwnedComponent) to the `i`-th component of `&self`.
882 ///
883 /// #### Complexity
884 ///
885 /// Runs in `O(1)`, performs no allocations.
886 ///
887 /// #### Examples
888 ///
889 /// ```
890 /// use willow_data_model::prelude::*;
891 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
892 /// assert_eq!(p.owned_component(0), Some(OwnedComponent::new(b"hi")?));
893 /// assert_eq!(p.owned_component(1), Some(OwnedComponent::new(b"ho")?));
894 /// assert_eq!(p.owned_component(2), None);
895 /// # Ok::<(), PathError>(())
896 /// ```
897 pub fn owned_component(&self, i: usize) -> Option<OwnedComponent<MCL>> {
898 if i < self.component_count {
899 let start =
900 Representation::start_offset_of_component(&self.data, i + self.first_component);
901 let end = Representation::end_offset_of_component(&self.data, i + self.first_component);
902 Some(OwnedComponent(self.data.slice(start..end)))
903 } else {
904 None
905 }
906 }
907
908 /// Returns an [owned handle](OwnedComponent) to the `i`-th component of `&self`, without checking whether `i < self.component_count()`.
909 ///
910 /// #### Safety
911 ///
912 /// Undefined behaviour if `i >= self.component_count()`.
913 ///
914 /// #### Complexity
915 ///
916 /// Runs in `O(1)`, performs no allocations.
917 ///
918 /// #### Examples
919 ///
920 /// ```
921 /// use willow_data_model::prelude::*;
922 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
923 /// assert_eq!(p.owned_component(0), Some(OwnedComponent::new(b"hi")?));
924 /// assert_eq!(p.owned_component(1), Some(OwnedComponent::new(b"ho")?));
925 /// assert_eq!(p.owned_component(2), None);
926 /// # Ok::<(), PathError>(())
927 /// ```
928 pub unsafe fn owned_component_unchecked(&self, i: usize) -> OwnedComponent<MCL> {
929 debug_assert!(
930 i < self.component_count(),
931 "Component index {} is out of range for path {} with {} components",
932 i,
933 self,
934 self.component_count()
935 );
936 let start = Representation::start_offset_of_component(&self.data, i + self.first_component);
937 let end = Representation::end_offset_of_component(&self.data, i + self.first_component);
938 OwnedComponent(self.data.slice(start..end))
939 }
940
941 /// Creates an iterator over the [`Component`]s of `&self`.
942 ///
943 /// Stepping the iterator takes `O(1)` time and performs no memory allocations.
944 ///
945 /// #### Complexity
946 ///
947 /// Runs in `O(1)`, performs no allocations.
948 ///
949 /// #### Examples
950 ///
951 /// ```
952 /// use willow_data_model::prelude::*;
953 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
954 /// let mut comps = p.components();
955 /// assert_eq!(comps.next(), Some(Component::new(b"hi")?));
956 /// assert_eq!(comps.next(), Some(Component::new(b"ho")?));
957 /// assert_eq!(comps.next(), None);
958 /// # Ok::<(), PathError>(())
959 /// ```
960 pub fn components(
961 &self,
962 ) -> impl DoubleEndedIterator<Item = &Component<MCL>> + ExactSizeIterator<Item = &Component<MCL>>
963 {
964 self.suffix_components(0)
965 }
966
967 /// Creates an iterator over the [`Component`]s of `&self`, starting at the `i`-th [`Component`]. If `i` is greater than or equal to the number of [`Component`]s, the iterator yields zero items.
968 ///
969 /// Stepping the iterator takes `O(1)` time and performs no memory allocations.
970 ///
971 /// #### Complexity
972 ///
973 /// Runs in `O(1)`, performs no allocations.
974 ///
975 /// #### Examples
976 ///
977 /// ```
978 /// use willow_data_model::prelude::*;
979 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
980 /// let mut comps = p.suffix_components(1);
981 /// assert_eq!(comps.next(), Some(Component::new(b"ho")?));
982 /// assert_eq!(comps.next(), None);
983 /// # Ok::<(), PathError>(())
984 /// ```
985 pub fn suffix_components(
986 &'_ self,
987 i: usize,
988 ) -> impl DoubleEndedIterator<Item = &Component<MCL>> + ExactSizeIterator<Item = &Component<MCL>>
989 {
990 (i..self.component_count()).map(|i| {
991 self.component(i).unwrap() // Only `None` if `i >= self.component_count()`
992 })
993 }
994
995 /// Creates an iterator over [owned handles](OwnedComponent) to the components of `&self`.
996 ///
997 /// Stepping the iterator takes `O(1)` time and performs no memory allocations.
998 ///
999 /// #### Complexity
1000 ///
1001 /// Runs in `O(1)`, performs no allocations.
1002 ///
1003 /// #### Examples
1004 ///
1005 /// ```
1006 /// use willow_data_model::prelude::*;
1007 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
1008 /// let mut comps = p.owned_components();
1009 /// assert_eq!(comps.next(), Some(OwnedComponent::new(b"hi")?));
1010 /// assert_eq!(comps.next(), Some(OwnedComponent::new(b"ho")?));
1011 /// assert_eq!(comps.next(), None);
1012 /// # Ok::<(), PathError>(())
1013 /// ```
1014 pub fn owned_components(
1015 &self,
1016 ) -> impl DoubleEndedIterator<Item = OwnedComponent<MCL>>
1017 + ExactSizeIterator<Item = OwnedComponent<MCL>>
1018 + '_ {
1019 self.suffix_owned_components(0)
1020 }
1021
1022 /// Creates an iterator over [owned handles](OwnedComponent) to the components of `&self`, starting at the `i`-th [`OwnedComponent`]. If `i` is greater than or equal to the number of [`OwnedComponent`], the iterator yields zero items.
1023 ///
1024 /// Stepping the iterator takes `O(1)` time and performs no memory allocations.
1025 ///
1026 /// #### Complexity
1027 ///
1028 /// Runs in `O(1)`, performs no allocations.
1029 ///
1030 /// #### Examples
1031 ///
1032 /// ```
1033 /// use willow_data_model::prelude::*;
1034 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
1035 /// let mut comps = p.suffix_owned_components(1);
1036 /// assert_eq!(comps.next(), Some(OwnedComponent::new(b"ho")?));
1037 /// assert_eq!(comps.next(), None);
1038 /// # Ok::<(), PathError>(())
1039 /// ```
1040 pub fn suffix_owned_components(
1041 &self,
1042 i: usize,
1043 ) -> impl DoubleEndedIterator<Item = OwnedComponent<MCL>>
1044 + ExactSizeIterator<Item = OwnedComponent<MCL>>
1045 + '_ {
1046 (i..self.component_count()).map(|i| {
1047 self.owned_component(i).unwrap() // Only `None` if `i >= self.component_count()`
1048 })
1049 }
1050
1051 /// Creates a new [`Path`] that consists of the first `component_count` [`Component`]s of `&self`. More efficient than creating a new [`Path`] from scratch.
1052 ///
1053 /// Returns [`None`] if `component_count` is greater than `self.get_component_count()`.
1054 ///
1055 /// #### Complexity
1056 ///
1057 /// Runs in `O(1)`, performs no allocations.
1058 ///
1059 /// #### Examples
1060 ///
1061 /// ```
1062 /// use willow_data_model::prelude::*;
1063 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
1064 /// assert_eq!(p.create_prefix(0), Some(Path::new()));
1065 /// assert_eq!(p.create_prefix(1), Some(Path::from_slice(b"hi")?));
1066 /// assert_eq!(p.create_prefix(2), Some(Path::from_slices(&[b"hi", b"ho"])?));
1067 /// assert_eq!(p.create_prefix(3), None);
1068 /// # Ok::<(), PathError>(())
1069 /// ```
1070 pub fn create_prefix(&self, component_count: usize) -> Option<Self> {
1071 if component_count > self.component_count() {
1072 None
1073 } else {
1074 Some(unsafe { self.create_prefix_unchecked(component_count) })
1075 }
1076 }
1077
1078 /// Creates a new [`Path`] that consists of the first `component_count` [`Component`]s of `&self`. More efficient than creating a new [`Path`] from scratch.
1079 ///
1080 /// #### Safety
1081 ///
1082 /// Undefined behaviour if `component_count` is greater than `self.component_count()`. May manifest directly, or at any later
1083 /// function invocation that operates on the resulting [`Path`].
1084 ///
1085 /// #### Complexity
1086 ///
1087 /// Runs in `O(1)`, performs no allocations.
1088 ///
1089 /// #### Examples
1090 ///
1091 /// ```
1092 /// use willow_data_model::prelude::*;
1093 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
1094 /// assert_eq!(unsafe { p.create_prefix_unchecked(0) }, Path::new());
1095 /// assert_eq!(unsafe { p.create_prefix_unchecked(1) }, Path::from_slice(b"hi")?);
1096 /// assert_eq!(unsafe { p.create_prefix_unchecked(2) }, Path::from_slices(&[b"hi", b"ho"])?);
1097 /// # Ok::<(), PathError>(())
1098 /// ```
1099 pub unsafe fn create_prefix_unchecked(&self, component_count: usize) -> Self {
1100 // #### Safety
1101 //
1102 // Safety guarantees for RangeTo for create_slice_unchecked are the same as those for component_count to create_prefix_unchecked
1103 unsafe { self.create_slice_unchecked(..component_count) }
1104 }
1105
1106 /// Creates an iterator over all [prefixes](https://willowprotocol.org/specs/data-model/index.html#path_prefix) of `&self` (including the empty [`Path`] and `&self` itself).
1107 ///
1108 /// Stepping the iterator takes `O(1)` time and performs no memory allocations.
1109 ///
1110 /// #### Complexity
1111 ///
1112 /// Runs in `O(1)`, performs no allocations.
1113 ///
1114 /// #### Examples
1115 ///
1116 /// ```
1117 /// use willow_data_model::prelude::*;
1118 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
1119 /// let mut prefixes = p.all_prefixes();
1120 /// assert_eq!(prefixes.next(), Some(Path::new()));
1121 /// assert_eq!(prefixes.next(), Some(Path::from_slice(b"hi")?));
1122 /// assert_eq!(prefixes.next(), Some(Path::from_slices(&[b"hi", b"ho"])?));
1123 /// assert_eq!(prefixes.next(), None);
1124 /// # Ok::<(), PathError>(())
1125 /// ```
1126 pub fn all_prefixes(&self) -> impl DoubleEndedIterator<Item = Self> + '_ {
1127 (0..=self.component_count()).map(|i| {
1128 unsafe {
1129 self.create_prefix_unchecked(i) // safe to call for i <= self.component_count()
1130 }
1131 })
1132 }
1133
1134 /// Returns the longest common [prefix](https://willowprotocol.org/specs/data-model/index.html#path_prefix) of `&self` and the given [`Path`].
1135 ///
1136 /// #### Complexity
1137 ///
1138 /// Runs in `O(n + m)`, where `n` is the total length of the shorter of the two [`Path`]s, and `m` is the lesser number of [`Component`]s. Performs a single allocation of `O(n + m)` bytes to create the return value.
1139 ///
1140 /// #### Examples
1141 ///
1142 /// ```
1143 /// use willow_data_model::prelude::*;
1144 /// let p1: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
1145 /// let p2: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"he"])?;
1146 /// assert_eq!(p1.longest_common_prefix(&p2), Path::from_slice(b"hi")?);
1147 /// # Ok::<(), PathError>(())
1148 /// ```
1149 pub fn longest_common_prefix(&self, other: &Self) -> Self {
1150 let mut lcp_len = 0;
1151
1152 for (comp_a, comp_b) in self.components().zip(other.components()) {
1153 if comp_a != comp_b {
1154 break;
1155 }
1156
1157 lcp_len += 1
1158 }
1159
1160 self.create_prefix(lcp_len).unwrap() // zip ensures that lcp_len <= self.component_count()
1161 }
1162
1163 /// Creates a [`Path`] whose [`Component`]s are those of `&self` indexed by the given `range`, without checking that those components exist.
1164 ///
1165 /// #### Safety
1166 ///
1167 /// Undefined behaviour if either the start or the end of `range` are explicitly greater than `self.component_count()`, or if `range` is decreasing.
1168 ///
1169 /// #### Complexity
1170 ///
1171 /// Runs in `O(1)` and performs no allocations.
1172 ///
1173 /// #### Examples
1174 ///
1175 /// ```
1176 /// use willow_data_model::prelude::*;
1177 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
1178 /// assert_eq!(unsafe{p.create_slice_unchecked(..)}, p);
1179 /// assert_eq!(unsafe{p.create_slice_unchecked(..1)}, Path::from_slices(&[b"hi"])?);
1180 /// assert_eq!(unsafe{p.create_slice_unchecked(1..)}, Path::from_slices(&[b"ho"])?);
1181 /// assert_eq!(unsafe{p.create_slice_unchecked(1..1)}, Path::new());
1182 /// # Ok::<(), PathError>(())
1183 /// ```
1184 pub unsafe fn create_slice_unchecked<R>(&self, range: R) -> Self
1185 where
1186 R: RangeBounds<usize>,
1187 {
1188 let n = match range.start_bound() {
1189 core::ops::Bound::Included(&n) => n,
1190 core::ops::Bound::Excluded(&n) => n + 1,
1191 core::ops::Bound::Unbounded => 0,
1192 };
1193
1194 let m = match range.end_bound() {
1195 core::ops::Bound::Included(&m) => m + 1,
1196 core::ops::Bound::Excluded(&m) => m,
1197 core::ops::Bound::Unbounded => self.component_count(),
1198 };
1199
1200 debug_assert!(
1201 m.max(n) <= self.component_count,
1202 "Path slice indexes component {}, which is out of range for path {} with {} components",
1203 m.max(n),
1204 self,
1205 self.component_count()
1206 );
1207 debug_assert!(
1208 m >= n,
1209 "Path slice end index {m} is before path slice start index {n}"
1210 );
1211 Path {
1212 data: self.data.clone(),
1213 first_component: n + self.first_component,
1214 component_count: m - n,
1215 }
1216 }
1217
1218 /// Creates a [`Path`] whose [`Component`]s are those of `&self` indexed by the given `range`.
1219 /// Returns [`None`] if either the start or end of `range` are explicitly greater than `&self.component_count()` or if `range` is decreasing.
1220 ///
1221 /// #### Complexity
1222 ///
1223 /// Runs in `O(1)` and performs no allocations.
1224 ///
1225 /// #### Examples
1226 ///
1227 /// ```
1228 /// use willow_data_model::prelude::*;
1229 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
1230 /// assert_eq!(p.create_slice(..), Some(p.clone()));
1231 /// assert_eq!(p.create_slice(1..2), Some(Path::from_slices(&[b"ho"])?));
1232 /// assert_eq!(p.create_slice(1..3), None);
1233 /// assert_eq!(p.create_slice(2..1), None);
1234 /// # Ok::<(), PathError>(())
1235 /// ```
1236 pub fn create_slice<R>(&self, range: R) -> Option<Self>
1237 where
1238 R: RangeBounds<usize>,
1239 {
1240 let n = match range.start_bound() {
1241 core::ops::Bound::Included(&n) => Some(n),
1242 core::ops::Bound::Excluded(&n) => n.checked_add(1),
1243 core::ops::Bound::Unbounded => Some(0),
1244 };
1245
1246 let m = match range.end_bound() {
1247 core::ops::Bound::Included(&m) => m.checked_add(1),
1248 core::ops::Bound::Excluded(&m) => Some(m),
1249 core::ops::Bound::Unbounded => Some(self.component_count),
1250 };
1251
1252 let (n, m) = match (n, m) {
1253 (Some(n), Some(m)) if n > m || m > self.component_count || n > self.component_count => {
1254 return None;
1255 }
1256 (Some(n), Some(m)) => (n, m),
1257 _ => return None,
1258 };
1259
1260 Some(Path {
1261 data: self.data.clone(),
1262 first_component: n + self.first_component,
1263 component_count: m - n,
1264 })
1265 }
1266
1267 /// Creates a [`Path`] whose [`Component`]s are the last `component_count` components of `&self`, without checking that `&self` has at least `component_count` components.
1268 ///
1269 /// #### Safety
1270 ///
1271 /// Undefined behaviour if `component_count > self.component_count()`.
1272 ///
1273 /// #### Complexity
1274 ///
1275 /// Runs in `O(1)` and performs no allocations.
1276 ///
1277 /// #### Examples
1278 ///
1279 /// ```
1280 /// use willow_data_model::prelude::*;
1281 /// let p: Path<4, 4, 4> = Path::from_slices(&[b"a", b"b", b"c", b"d"])?;
1282 /// assert_eq!(unsafe{p.create_suffix_unchecked(2)}, Path::from_slices(&[b"c", b"d"])?);
1283 /// assert_eq!(unsafe{p.create_suffix_unchecked(0)}, Path::new());
1284 /// # Ok::<(), PathError>(())
1285 /// ```
1286 pub unsafe fn create_suffix_unchecked(&self, component_count: usize) -> Self {
1287 debug_assert!(
1288 component_count <= self.component_count(),
1289 "Tried to create a suffix from {} components of path {} which has only {} components",
1290 component_count,
1291 self,
1292 self.component_count()
1293 );
1294
1295 // #### Safety
1296 //
1297 // Safety guarantees for RangeFrom argument to create_slice_unchecked are the same as those for component_count in create_suffix_unchecked
1298 unsafe { self.create_slice_unchecked(self.component_count() - component_count..) }
1299 }
1300
1301 /// Creates a [`Path`] whose [`Component`]s are the last `component_count` components of `&self`.
1302 /// Returns [`None`] if `&self` does not have at least `component_count` components.
1303 ///
1304 /// #### Complexity
1305 ///
1306 /// Runs in `O(1)` and performs no allocations.
1307 ///
1308 /// #### Examples
1309 ///
1310 /// ```
1311 /// use willow_data_model::prelude::*;
1312 ///
1313 /// let p: Path<4,4,4> = Path::from_slices(&[b"hi", b"ho"])?;
1314 /// assert_eq!(p.create_suffix(0), Some(Path::new()));
1315 /// assert_eq!(p.create_suffix(1), Some(Path::from_slices(&[b"ho"])?));
1316 /// assert_eq!(p.create_suffix(2), Some(Path::from_slices(&[b"hi", b"ho"])?));
1317 /// assert_eq!(p.create_suffix(3), None);
1318 ///
1319 /// # Ok::<(), PathError>(())
1320 /// ```
1321 pub fn create_suffix(&self, component_count: usize) -> Option<Self> {
1322 if component_count > self.component_count() {
1323 None
1324 } else {
1325 unsafe { Some(self.create_suffix_unchecked(component_count)) }
1326 }
1327 }
1328}
1329
1330impl<const MCL: usize, const MCC: usize, const MPL: usize> PartialEq for Path<MCL, MCC, MPL> {
1331 fn eq(&self, other: &Self) -> bool {
1332 if self.component_count != other.component_count {
1333 false
1334 } else {
1335 self.components().eq(other.components())
1336 }
1337 }
1338}
1339
1340impl<const MCL: usize, const MCC: usize, const MPL: usize> Eq for Path<MCL, MCC, MPL> {}
1341
1342impl<const MCL: usize, const MCC: usize, const MPL: usize> Hash for Path<MCL, MCC, MPL> {
1343 fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
1344 self.component_count.hash(state);
1345
1346 for comp in self.components() {
1347 comp.hash(state);
1348 }
1349 }
1350}
1351
1352impl<const MCL: usize, const MCC: usize, const MPL: usize> PartialOrd for Path<MCL, MCC, MPL> {
1353 fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
1354 Some(self.cmp(other))
1355 }
1356}
1357
1358/// Compares paths lexicographically, since that is the path ordering that the Willow spec always uses.
1359impl<const MCL: usize, const MCC: usize, const MPL: usize> Ord for Path<MCL, MCC, MPL> {
1360 fn cmp(&self, other: &Self) -> core::cmp::Ordering {
1361 self.components().cmp(other.components())
1362 }
1363}
1364
1365/// The least path is the empty path.
1366impl<const MCL: usize, const MCC: usize, const MPL: usize> LeastElement for Path<MCL, MCC, MPL> {
1367 /// Returns the least path.
1368 fn least() -> Self {
1369 Self::new()
1370 }
1371}
1372
1373impl<const MCL: usize, const MCC: usize, const MPL: usize> GreatestElement for Path<MCL, MCC, MPL> {
1374 /// Creates the greatest possible [`Path`] (with respect to lexicographical ordering, which is also the [`Ord`] implementation of [`Path`]).
1375 ///
1376 /// #### Complexity
1377 ///
1378 /// Runs in `O(MCC + MPL)`. Performs a single allocation of `O(MPL)` bytes.
1379 ///
1380 /// #### Examples
1381 ///
1382 /// ```
1383 /// use willow_data_model::prelude::*;
1384 /// use order_theory::GreatestElement;
1385 ///
1386 /// let p = Path::<4, 4, 4>::greatest();
1387 /// assert_eq!(p.component_count(), 4);
1388 /// assert_eq!(p.component(0).unwrap().as_ref(), &[255, 255, 255, 255]);
1389 /// assert!(p.component(1).unwrap().is_empty());
1390 /// assert!(p.component(2).unwrap().is_empty());
1391 /// assert!(p.component(3).unwrap().is_empty());
1392 /// ```
1393 fn greatest() -> Self {
1394 let max_comp_bytes = [255; MCL];
1395
1396 let mut num_comps = if MCL == 0 {
1397 MCC
1398 } else {
1399 core::cmp::min(MCC, MPL.div_ceil(MCL))
1400 };
1401 let mut path_builder = PathBuilder::new(MPL, MCC).unwrap();
1402
1403 let mut len_so_far = 0;
1404
1405 for _ in 0..num_comps {
1406 let comp_len = core::cmp::min(MCL, MPL - len_so_far);
1407 let component = unsafe { Component::new_unchecked(&max_comp_bytes[..comp_len]) };
1408 path_builder.append_component(component);
1409
1410 len_so_far += comp_len;
1411 }
1412
1413 while num_comps < MCC {
1414 path_builder.append_component(Component::new_empty());
1415 num_comps += 1;
1416 }
1417
1418 path_builder.build()
1419 }
1420}
1421
1422impl<const MCL: usize, const MCC: usize, const MPL: usize> LowerSemilattice
1423 for Path<MCL, MCC, MPL>
1424{
1425 fn greatest_lower_bound(&self, other: &Self) -> Self {
1426 if self <= other {
1427 self.clone()
1428 } else {
1429 other.clone()
1430 }
1431 }
1432}
1433
1434impl<const MCL: usize, const MCC: usize, const MPL: usize> UpperSemilattice
1435 for Path<MCL, MCC, MPL>
1436{
1437 fn least_upper_bound(&self, other: &Self) -> Self {
1438 if self >= other {
1439 self.clone()
1440 } else {
1441 other.clone()
1442 }
1443 }
1444}
1445
1446impl<const MCL: usize, const MCC: usize, const MPL: usize> TryPredecessor for Path<MCL, MCC, MPL> {
1447 fn try_predecessor(&self) -> Option<Self> {
1448 if self.component_count() == 0 {
1449 // We are the empty path, so we do not have a predecessor.
1450 None
1451 } else {
1452 let final_component = self.component(self.component_count() - 1).unwrap();
1453
1454 // We have a component. Our predecessor depends only on the final component, with several options depending on the final byte:
1455 if final_component.as_bytes().is_empty() {
1456 // If the final component is empty, we simply remove it to obtain the predecessor.
1457 Some(unsafe { self.create_prefix_unchecked(self.component_count() - 1) })
1458 } else {
1459 let final_byte = final_component.as_bytes()[final_component.len() - 1];
1460
1461 // The final component was non-empty. We now decrement the final component, and then fill up the path with maximally many maximal components.
1462
1463 // Create a builder for the new component, which will be of maximal length, maximal component count, and starting with `self` sans the final_component.
1464 let predecessor_total_len = core::cmp::min(
1465 MPL,
1466 self.total_length_of_prefix(self.component_count() - 1) // unchanged components
1467 + if final_byte == 0 { final_component.len() - 1 } else { MCL } // replacement of self.final_comp
1468 + ((MCC - self.component_count()) * MCL), // padding 255 bytes
1469 );
1470 let mut builder = PathBuilder::new_from_prefix(
1471 predecessor_total_len,
1472 MCC,
1473 self,
1474 self.component_count() - 1,
1475 )
1476 .unwrap();
1477
1478 // The meaning of "decrement the final component" depends on the final byte.
1479 // In either case we do not actually construct a coponent, but merely apend the decremented component to the builder.
1480 if final_byte == 0 {
1481 // If the final byte is zero, we simply remove it from the component.
1482 builder.append_component(unsafe {
1483 Component::<MCL>::new_unchecked(
1484 &final_component[..final_component.len() - 1],
1485 )
1486 });
1487 } else {
1488 // If the final byte is not zero, we decrement the final byte by one and then append 255 bytes until hitting the MCL or the MPL, whichever happens first..
1489
1490 // The way we actually implement this is by creating a mutable array of MCL many 255 bytes, overwriting the start of it, and then feeding the correct prefix into the builder.
1491 let mut arr = [255; MCL];
1492
1493 arr[0..final_component.len()].copy_from_slice(final_component);
1494 arr[final_component.len() - 1] = final_byte - 1;
1495
1496 builder.append_component(unsafe {
1497 Component::<MCL>::new_unchecked(
1498 &arr[..core::cmp::min(
1499 MCL,
1500 MPL - self.total_length_of_prefix(self.component_count() - 1),
1501 )],
1502 )
1503 });
1504 }
1505
1506 while builder.component_count() < MCC {
1507 // We have decremented the final component. Now we append maximal components while we can.
1508 let comp_len = core::cmp::min(MCL, MPL - builder.total_length());
1509
1510 let arr = [255; MCL];
1511 builder.append_component(unsafe {
1512 Component::<MCL>::new_unchecked(&arr[..comp_len])
1513 });
1514 }
1515
1516 Some(builder.build())
1517 }
1518 }
1519 }
1520}
1521
1522impl<const MCL: usize, const MCC: usize, const MPL: usize> PredecessorExceptForLeast
1523 for Path<MCL, MCC, MPL>
1524{
1525}
1526
1527impl<const MCL: usize, const MCC: usize, const MPL: usize> TrySuccessor for Path<MCL, MCC, MPL> {
1528 /// Returns the least path which is strictly greater than `self`, or return `None` if `self` is the greatest possible path.
1529 ///
1530 /// #### Complexity
1531 ///
1532 /// Runs in `O(n + m)`, where `n` is the total length of the [`Path`] in bytes, and `m` is the number of [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
1533 ///
1534 /// #### Examples
1535 ///
1536 /// ```
1537 /// use willow_data_model::prelude::*;
1538 /// use order_theory::TrySuccessor;
1539 ///
1540 /// let p: Path<3, 3, 3> = Path::from_slices(&[
1541 /// [255].as_slice(),
1542 /// [9, 255].as_slice(),
1543 /// [].as_slice(),
1544 /// ])?;
1545 /// assert_eq!(p.try_successor(), Some(Path::from_slices(&[
1546 /// [255].as_slice(),
1547 /// [10].as_slice(),
1548 /// ])?));
1549 /// # Ok::<(), PathError>(())
1550 /// ```
1551 fn try_successor(&self) -> Option<Self> {
1552 // If it is possible to append an empty component, then doing so yields the successor.
1553 if let Ok(path) = self.append_component(Component::new_empty()) {
1554 return Some(path);
1555 }
1556
1557 // Otherwise, we try incrementing the final component. If that fails,
1558 // we try to increment the second-to-final component, and so on.
1559 // All components that come after the incremented component are discarded.
1560 // If *no* component can be incremented, `self` is the maximal path and we return `None`.
1561
1562 for (i, component) in self.components().enumerate().rev() {
1563 // It would be nice to call a `try_increment_component` function, but in order to avoid
1564 // memory allocations, we write some lower-level but more efficient code.
1565
1566 // If it is possible to append a zero byte to a component, then doing so yields its successor.
1567 let mut length_offset = 0;
1568 if self.first_component > 0 {
1569 length_offset = Representation::sum_of_lengths_for_component(
1570 self.data.as_ref(),
1571 self.first_component - 1,
1572 );
1573 }
1574 let length_offset = length_offset;
1575 if component.len() < MCL
1576 && Representation::sum_of_lengths_for_component(
1577 self.data.as_ref(),
1578 i + self.first_component,
1579 ) - length_offset
1580 < MPL
1581 {
1582 // We now know how to construct the path successor of `self`:
1583 // Take the first `i` components (this *excludes* the current `component`),
1584 // then append `component` with an additional zero byte at the end.
1585 let mut buf = clone_prefix_and_lengthen_final_component(
1586 &self.data,
1587 i,
1588 1,
1589 self.first_component,
1590 );
1591 buf.put_u8(0);
1592
1593 return Some(Path {
1594 data: buf.freeze(),
1595 component_count: i + 1,
1596 first_component: 0,
1597 });
1598 }
1599
1600 // We **cannot** append a zero byte, so instead we check whether we can treat the component as a fixed-width integer and increment it. The only failure case is if that component consists of 255-bytes only.
1601 let can_increment = !component.iter().all(|byte| *byte == 255);
1602
1603 // If we cannot increment, we go to the next iteration of the loop. But if we can, we can create a copy of the
1604 // prefix on the first `i + 1` components, and mutate its backing memory in-place.
1605 if can_increment {
1606 let mut buf = clone_prefix_and_lengthen_final_component(
1607 &self.data,
1608 i,
1609 0,
1610 self.first_component,
1611 );
1612
1613 let start_component_offset =
1614 Representation::start_offset_of_component(buf.as_ref(), i);
1615 let end_component_offset = Representation::end_offset_of_component(buf.as_ref(), i);
1616
1617 let overflows = fixed_width_increment_reporting_overflows(
1618 &mut buf.as_mut()[start_component_offset..end_component_offset],
1619 );
1620 let new_sum_of_lengths =
1621 Representation::sum_of_lengths_for_component(buf.as_ref(), i) - overflows;
1622 buf_set_final_component_length(buf.as_mut(), i, new_sum_of_lengths);
1623
1624 return Some(Path {
1625 data: buf.freeze(),
1626 component_count: i + 1,
1627 first_component: 0,
1628 });
1629 }
1630 }
1631
1632 // Failed to increment any component, so `self` is the maximal path.
1633 None
1634 }
1635}
1636
1637impl<const MCL: usize, const MCC: usize, const MPL: usize> SuccessorExceptForGreatest
1638 for Path<MCL, MCC, MPL>
1639{
1640}
1641
1642impl<const MCL: usize, const MCC: usize, const MPL: usize> Debug for Path<MCL, MCC, MPL> {
1643 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1644 f.debug_tuple("Path").field(&FmtHelper(self)).finish()
1645 }
1646}
1647
1648struct FmtHelper<'a, const MCL: usize, const MCC: usize, const MPL: usize>(&'a Path<MCL, MCC, MPL>);
1649
1650impl<'a, const MCL: usize, const MCC: usize, const MPL: usize> fmt::Debug
1651 for FmtHelper<'a, MCL, MCC, MPL>
1652{
1653 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1654 if self.0.is_empty() {
1655 write!(f, "<empty>")
1656 } else {
1657 for comp in self.0.components() {
1658 write!(f, "/")?;
1659 write!(f, "{:?}", ComponentFmtHelper::new(&comp, false))?;
1660 }
1661
1662 Ok(())
1663 }
1664 }
1665}
1666
1667impl<const MCL: usize, const MCC: usize, const MPL: usize> fmt::Display for Path<MCL, MCC, MPL> {
1668 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1669 write!(f, "{:?}", FmtHelper(self))
1670 }
1671}
1672
1673#[cfg(feature = "dev")]
1674impl<'a, const MCL: usize, const MCC: usize, const MPL: usize> Arbitrary<'a>
1675 for Path<MCL, MCC, MPL>
1676{
1677 fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self, ArbitraryError> {
1678 let mut total_length_in_bytes: usize = Arbitrary::arbitrary(u)?;
1679 total_length_in_bytes %= MPL + 1;
1680
1681 let data: Box<[u8]> = Arbitrary::arbitrary(u)?;
1682 total_length_in_bytes = core::cmp::min(total_length_in_bytes, data.len());
1683
1684 let mut num_components: usize = Arbitrary::arbitrary(u)?;
1685 num_components %= MCC + 1;
1686
1687 if num_components == 0 {
1688 total_length_in_bytes = 0;
1689 }
1690
1691 let mut builder = PathBuilder::new(total_length_in_bytes, num_components).unwrap();
1692
1693 let mut length_total_so_far = 0;
1694 for i in 0..num_components {
1695 // Determine the length of the i-th component: randomly within some constraints for all but the final one. The final length is chosen to match the total_length_in_bytes.
1696 let length_of_ith_component = if i + 1 == num_components {
1697 if total_length_in_bytes - length_total_so_far > MCL {
1698 return Err(ArbitraryError::IncorrectFormat);
1699 } else {
1700 total_length_in_bytes - length_total_so_far
1701 }
1702 } else {
1703 // Any non-final component can take on a random length, ...
1704 let mut component_length: usize = Arbitrary::arbitrary(u)?;
1705 // ... except it must be at most the MCL, and...
1706 component_length %= MCL + 1;
1707 // ... the total length of all components must not exceed the total path length.
1708 component_length = core::cmp::min(
1709 component_length,
1710 total_length_in_bytes - length_total_so_far,
1711 );
1712 component_length
1713 };
1714
1715 builder.append_component(
1716 Component::new(
1717 &data[length_total_so_far..length_total_so_far + length_of_ith_component],
1718 )
1719 .unwrap(),
1720 );
1721 length_total_so_far += length_of_ith_component;
1722 }
1723
1724 Ok(builder.build())
1725 }
1726
1727 #[inline]
1728 fn size_hint(depth: usize) -> (usize, Option<usize>) {
1729 (
1730 and_all(&[
1731 usize::size_hint(depth),
1732 usize::size_hint(depth),
1733 Box::<[u8]>::size_hint(depth),
1734 ])
1735 .0,
1736 None,
1737 )
1738 }
1739}
1740
1741/////////////////////////////////////////////////////////////////////
1742// Helpers for efficiently creating successors. //
1743// Efficiency warrants some low-level fiddling around here, sorry. //
1744/////////////////////////////////////////////////////////////////////
1745
1746/// Creates a new BufMut that stores the heap encoding of the first i components of `original`, but increasing the length of the final component by `extra_capacity`. No data to fill that extra capacity is written into the buffer.
1747fn clone_prefix_and_lengthen_final_component(
1748 representation: &[u8],
1749 i: usize,
1750 extra_capacity: usize,
1751 first_component_offset: usize,
1752) -> BytesMut {
1753 let mut successor_path_length =
1754 Representation::sum_of_lengths_for_component(representation, i + first_component_offset)
1755 + extra_capacity;
1756
1757 let mut size_offset = 0;
1758
1759 if first_component_offset > 0 {
1760 size_offset = Representation::sum_of_lengths_for_component(
1761 representation,
1762 first_component_offset - 1,
1763 );
1764 successor_path_length -= size_offset;
1765 }
1766
1767 let size_offset = size_offset;
1768 let successor_path_length = successor_path_length;
1769
1770 let buf_capacity = size_of::<usize>() * (i + 2) + successor_path_length;
1771 let mut buf = BytesMut::with_capacity(buf_capacity);
1772
1773 // Write the length of the successor path as the first usize.
1774 buf.extend_from_slice(&(i + 1).to_ne_bytes());
1775
1776 // Next, copy the total path lengths for the first i prefixes.
1777 if first_component_offset > 0 {
1778 // We have to adjust each path length if we are working with an offset first component
1779 for component_offset in first_component_offset..first_component_offset + i + 1 {
1780 buf.extend_from_slice(
1781 &(Representation::sum_of_lengths_for_component(representation, component_offset)
1782 - size_offset)
1783 .to_ne_bytes(),
1784 );
1785 }
1786 } else {
1787 // Otherwise we can copy all the path length bytes more cheaply
1788 buf.extend_from_slice(
1789 &representation[Representation::start_offset_of_sum_of_lengths_for_component(0)
1790 ..Representation::start_offset_of_sum_of_lengths_for_component(i + 1)],
1791 );
1792 }
1793
1794 // Now, write the length of the final component, which is one greater than before.
1795 buf_set_final_component_length(buf.as_mut(), i, successor_path_length);
1796
1797 // Finally, copy the raw bytes of the first i+1 components.
1798 buf.extend_from_slice(
1799 &representation[Representation::start_offset_of_component(
1800 representation,
1801 first_component_offset,
1802 )
1803 ..Representation::start_offset_of_component(
1804 representation,
1805 first_component_offset + i + 1,
1806 )],
1807 );
1808
1809 buf
1810}
1811
1812// In a buffer that stores a path on the heap, set the sum of all component lengths for the i-th component, which must be the final component.
1813fn buf_set_final_component_length(buf: &mut [u8], i: usize, new_sum_of_lengths: usize) {
1814 let comp_len_start = Representation::start_offset_of_sum_of_lengths_for_component(i);
1815 let comp_len_end = comp_len_start + size_of::<usize>();
1816 buf[comp_len_start..comp_len_end].copy_from_slice(&new_sum_of_lengths.to_ne_bytes()[..]);
1817}
1818
1819// Overflows to all zeroes if all bytes are 255. Returns the number of overflowing bytes.
1820fn fixed_width_increment_reporting_overflows(buf: &mut [u8]) -> usize {
1821 let mut overflows = 0;
1822 for byte_ref in buf.iter_mut().rev() {
1823 if *byte_ref == 255 {
1824 *byte_ref = 0;
1825 overflows += 1;
1826 } else {
1827 *byte_ref += 1;
1828 return overflows;
1829 }
1830 }
1831
1832 overflows
1833}
1834
1835#[test]
1836fn greatest() {
1837 let path1 = Path::<3, 3, 6>::greatest();
1838
1839 assert!(path1.try_successor().is_none());
1840
1841 let path2 = Path::<4, 4, 16>::greatest();
1842 assert!(path2.try_successor().is_none());
1843
1844 let path3 = Path::<0, 4, 0>::greatest();
1845 assert!(path3.try_successor().is_none());
1846
1847 let path4 = Path::<4, 2, 6>::greatest();
1848 assert!(path4.try_successor().is_none())
1849}