willow-data-model 0.4.1

The core datatypes of Willow, an eventually consistent data store with improved distributed deletion.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

//! [Groupings](https://willowprotocol.org/specs/grouping-entries/) of entries in 3d space.
//!
//! This module implements the [groupings](https://willowprotocol.org/specs/grouping-entries/) used by the Willow specifications:
//!
//! - [ranges](https://willowprotocol.org/specs/grouping-entries/#ranges) ([`WillowRange`]),
//! - [3d ranges](https://willowprotocol.org/specs/grouping-entries/#D3Range) ([`Range3d`]),
//! - [areas](https://willowprotocol.org/specs/grouping-entries/#areas) ([`Area`]), and
//! - [areas of interest](https://willowprotocol.org/specs/grouping-entries/#aois) ([`AreaOfInterest`]).
//!
//! Our implementations center around two traits: [`Coordinatelike`] describes values which fall into some position in three-dimensional Willow space, and [`Grouping`] describes groupings of values based on their position in three-dimensional Willow space. The [`CoordinatelikeExt`] trait then provides convenient methods for checking which values are included in which groupings.
//!
//! ```
//! use willow_data_model::prelude::*;
//!
//! let entry = Entry::builder()
//!     .namespace_id("family")
//!     .subspace_id([5; 32])
//!     .path(Path::<4, 4, 4>::new())
//!     .timestamp(12345)
//!     .payload_digest("some_hash")
//!     .payload_length(17)
//!     .build().unwrap();
//!
//! assert!(entry.wdm_is_in(&Range3d::full()));
//! assert!(!entry.wdm_is_in(&Area::wdm_empty()));
//! ```

use crate::prelude::*;

mod willow_range;
use order_theory::BoundedLowerSemilattice;
pub use willow_range::*;

mod range_3d;
pub use range_3d::*;

mod area;
pub use area::*;

mod area_of_interest;
pub use area_of_interest::*;

mod keylike;
pub use keylike::*;

mod coordinatelike;
pub use coordinatelike::*;

/// A [`WillowRange`] of [SubspaceIds](https://willowprotocol.org/specs/data-model/index.html#SubspaceId).
///
/// [TODO example]
///
/// [Specification](https://willowprotocol.org/specs/grouping-entries/index.html#SubspaceRange)
pub type SubspaceRange<S> = WillowRange<S>;

/// A [`WillowRange`] of [Paths](https://willowprotocol.org/specs/data-model/index.html#Path).
///
/// [TODO example]
///
/// [Specification](https://willowprotocol.org/specs/grouping-entries/index.html#PathRange)
pub type PathRange<const MCL: usize, const MCC: usize, const MPL: usize> =
    WillowRange<Path<MCL, MCC, MPL>>;

/// A [`WillowRange`] of [Timestamps](https://willowprotocol.org/specs/data-model/index.html#Timestamp).
///
/// [TODO example]
///
/// [Specification](https://willowprotocol.org/specs/grouping-entries/index.html#TimeRange)
pub type TimeRange = WillowRange<Timestamp>;

/// A grouping of entries.
///
/// A grouping describes a set of [`Coordinatelike`] values, with [`Grouping::wdm_includes`] providing the membership test. Groupings must form a [`BoundedLowerSemilattice`], with the least element including no values at all, and the partial order corresponding to the subset relation of included values.
pub trait Grouping<const MCL: usize, const MCC: usize, const MPL: usize, S>:
    BoundedLowerSemilattice
{
    /// Returns `true` iff the given [`Coordinatelike`] value is included in this grouping.
    fn wdm_includes<Coord>(&self, coord: &Coord) -> bool
    where
        Coord: Coordinatelike<MCL, MCC, MPL, S> + ?Sized;

    /// Returns `true` iff every value [included](Grouping::wdm_includes) in `other` is also [included](Grouping::wdm_includes) in `self`.
    fn wdm_includes_grouping(&self, other: &Self) -> bool {
        self >= other
    }

    /// Returns `true` iff every value [included](Grouping::wdm_includes) in `other` is also [included](Grouping::wdm_includes) in `self` *and* `self` and `other` are not equal.
    fn wdm_strictly_includes_grouping(&self, other: &Self) -> bool {
        self > other
    }

    /// Returns `true` iff the given [`Coordinatelike`] value is [included](Grouping::wdm_includes) in the [intersection](Grouping::wdm_intersection) of `self` and `other`.
    fn wdm_includes_in_intersection<Coord>(&self, other: &Self, coord: &Coord) -> bool
    where
        Coord: Coordinatelike<MCL, MCC, MPL, S> + ?Sized,
    {
        self.wdm_includes(coord) && other.wdm_includes(coord)
    }

    /// Returns `true` iff `self` [includes](Grouping::wdm_includes) no values.
    fn wdm_is_empty(&self) -> bool {
        self.is_least()
    }

    /// Returns a grouping which [includes](Grouping::wdm_includes) no values.
    fn wdm_empty() -> Self {
        Self::least()
    }

    /// Returns a grouping which [includes](Grouping::wdm_includes) exactly those values [included](Grouping::wdm_includes) by both `self` and `other`.
    fn wdm_intersection(&self, other: &Self) -> Self {
        self.greatest_lower_bound(other)
    }
}