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