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