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