willow_data_model/grouping/
area.rs

1#[cfg(feature = "dev")]
2use arbitrary::{size_hint::and_all, Arbitrary};
3
4use crate::{
5    entry::{Entry, Timestamp},
6    parameters::{NamespaceId, PayloadDigest, SubspaceId},
7    path::Path,
8};
9
10use super::range::Range;
11
12/// The possible values of an [`Area`]'s `subspace`.
13#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
14pub enum AreaSubspace<S: SubspaceId> {
15    /// A value that signals that an [`Area`] includes Entries with arbitrary subspace_ids.
16    Any,
17    /// A concrete [`SubspaceId`].
18    Id(S),
19}
20
21impl<S: SubspaceId> AreaSubspace<S> {
22    /// Return whether this [`AreaSubspace`] includes a given [`SubspaceId`].
23    pub fn includes(&self, sub: &S) -> bool {
24        match self {
25            AreaSubspace::Any => true,
26            AreaSubspace::Id(id) => sub == id,
27        }
28    }
29
30    /// Return the intersection between two [`AreaSubspace`].
31    fn intersection(&self, other: &Self) -> Option<Self> {
32        match (self, other) {
33            (Self::Any, Self::Any) => Some(Self::Any),
34            (Self::Id(a), Self::Any) => Some(Self::Id(a.clone())),
35            (Self::Any, Self::Id(b)) => Some(Self::Id(b.clone())),
36            (Self::Id(a), Self::Id(b)) if a == b => Some(Self::Id(a.clone())),
37            (Self::Id(_a), Self::Id(_b)) => None,
38        }
39    }
40
41    /// Return whether this [`AreaSubspace`] includes Entries with arbitrary subspace_ids.
42    pub fn is_any(&self) -> bool {
43        matches!(self, AreaSubspace::Any)
44    }
45}
46
47#[cfg(feature = "dev")]
48impl<'a, S> Arbitrary<'a> for AreaSubspace<S>
49where
50    S: SubspaceId + Arbitrary<'a>,
51{
52    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
53        let is_any: bool = Arbitrary::arbitrary(u)?;
54
55        if !is_any {
56            let subspace: S = Arbitrary::arbitrary(u)?;
57
58            return Ok(Self::Id(subspace));
59        }
60
61        Ok(Self::Any)
62    }
63}
64
65/// A grouping of entries.
66/// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#areas).
67#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
68pub struct Area<const MCL: usize, const MCC: usize, const MPL: usize, S: SubspaceId> {
69    /// To be included in this [`Area`], an [`Entry`]’s `subspace_id` must be equal to the subspace_id, unless it is any.
70    subspace: AreaSubspace<S>,
71    /// To be included in this [`Area`], an [`Entry`]’s `path` must be prefixed by the path.
72    path: Path<MCL, MCC, MPL>,
73    /// To be included in this [`Area`], an [`Entry`]’s `timestamp` must be included in the times.
74    times: Range<Timestamp>,
75}
76
77impl<const MCL: usize, const MCC: usize, const MPL: usize, S: SubspaceId> Area<MCL, MCC, MPL, S> {
78    /// Create a new [`Area`].
79    pub fn new(
80        subspace: AreaSubspace<S>,
81        path: Path<MCL, MCC, MPL>,
82        times: Range<Timestamp>,
83    ) -> Self {
84        Area {
85            subspace,
86            path,
87            times,
88        }
89    }
90
91    /// Return a reference to the [`AreaSubspace`].
92    ///
93    /// To be included in this [`Area`], an [`Entry`]’s `subspace_id` must be equal to the subspace_id, unless it is any.
94    pub fn subspace(&self) -> &AreaSubspace<S> {
95        &self.subspace
96    }
97
98    /// Return a reference to the [`Path`].
99    ///
100    /// To be included in this [`Area`], an [`Entry`]’s `path` must be prefixed by the path.
101    pub fn path(&self) -> &Path<MCL, MCC, MPL> {
102        &self.path
103    }
104
105    /// Return a reference to the range of [`Timestamp`]s.
106    ///
107    /// To be included in this [`Area`], an [`Entry`]’s `timestamp` must be included in the times.
108    pub fn times(&self) -> &Range<Timestamp> {
109        &self.times
110    }
111
112    /// Return an [`Area`] which includes all entries.
113    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#full_area).
114    pub fn new_full() -> Self {
115        Self {
116            subspace: AreaSubspace::Any,
117            path: Path::new_empty(),
118            times: Range::new_open(0),
119        }
120    }
121
122    /// Return an [`Area`] which includes all entries within a [subspace](https://willowprotocol.org/specs/data-model/index.html#subspace).
123    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#subspace_area).
124    pub fn new_subspace(sub: S) -> Self {
125        Self {
126            subspace: AreaSubspace::Id(sub),
127            path: Path::new_empty(),
128            times: Range::new_open(0),
129        }
130    }
131
132    /// Return whether an [`Area`] [includes](https://willowprotocol.org/specs/grouping-entries/index.html#area_include) an [`Entry`].
133    pub fn includes_entry<N: NamespaceId, PD: PayloadDigest>(
134        &self,
135        entry: &Entry<MCL, MCC, MPL, N, S, PD>,
136    ) -> bool {
137        self.subspace.includes(entry.subspace_id())
138            && self.path.is_prefix_of(entry.path())
139            && self.times.includes(&entry.timestamp())
140    }
141
142    /// Return whether an [`Area`] fully [includes](https://willowprotocol.org/specs/grouping-entries/index.html#area_include_area) another [`Area`].
143    pub fn includes_area(&self, area: &Self) -> bool {
144        match (&self.subspace, &area.subspace) {
145            (AreaSubspace::Any, AreaSubspace::Any) => {
146                self.path.is_prefix_of(&area.path) && self.times.includes_range(&area.times)
147            }
148            (AreaSubspace::Any, AreaSubspace::Id(_)) => {
149                self.path.is_prefix_of(&area.path) && self.times.includes_range(&area.times)
150            }
151            (AreaSubspace::Id(_), AreaSubspace::Any) => false,
152            (AreaSubspace::Id(subspace_a), AreaSubspace::Id(subspace_b)) => {
153                subspace_a == subspace_b
154                    && self.path.is_prefix_of(&area.path)
155                    && self.times.includes_range(&area.times)
156            }
157        }
158    }
159
160    /// Return the intersection of this [`Area`] with another.
161    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#area_intersection).
162    pub fn intersection(&self, other: &Area<MCL, MCC, MPL, S>) -> Option<Self> {
163        let subspace_id = self.subspace.intersection(&other.subspace)?;
164        let path = if self.path.is_prefix_of(&other.path) {
165            Some(other.path.clone())
166        } else if self.path.is_prefixed_by(&other.path) {
167            Some(self.path.clone())
168        } else {
169            None
170        }?;
171        let times = self.times.intersection(&other.times)?;
172        Some(Self {
173            subspace: subspace_id,
174            times,
175            path,
176        })
177    }
178}
179
180#[cfg(feature = "dev")]
181impl<'a, const MCL: usize, const MCC: usize, const MPL: usize, S> Arbitrary<'a>
182    for Area<MCL, MCC, MPL, S>
183where
184    S: SubspaceId + Arbitrary<'a>,
185{
186    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
187        let subspace: AreaSubspace<S> = Arbitrary::arbitrary(u)?;
188        let path: Path<MCL, MCC, MPL> = Arbitrary::arbitrary(u)?;
189        let times: Range<u64> = Arbitrary::arbitrary(u)?;
190
191        Ok(Self {
192            subspace,
193            path,
194            times,
195        })
196    }
197
198    fn size_hint(depth: usize) -> (usize, Option<usize>) {
199        and_all(&[
200            AreaSubspace::<S>::size_hint(depth),
201            Path::<MCL, MCC, MPL>::size_hint(depth),
202            Range::<u64>::size_hint(depth),
203        ])
204    }
205}
206
207#[cfg(test)]
208mod tests {
209
210    use crate::path::Component;
211
212    use super::*;
213
214    #[derive(Debug, Default, PartialEq, Eq, PartialOrd, Ord, Clone)]
215    struct FakeSubspaceId(usize);
216    impl SubspaceId for FakeSubspaceId {
217        fn successor(&self) -> Option<Self> {
218            Some(FakeSubspaceId(self.0 + 1))
219        }
220    }
221
222    const MCL: usize = 8;
223    const MCC: usize = 4;
224    const MPL: usize = 16;
225
226    #[test]
227    fn subspace_area_includes() {
228        assert!(AreaSubspace::<FakeSubspaceId>::Any.includes(&FakeSubspaceId(5)));
229        assert!(AreaSubspace::<FakeSubspaceId>::Id(FakeSubspaceId(5)).includes(&FakeSubspaceId(5)));
230        assert!(!AreaSubspace::<FakeSubspaceId>::Id(FakeSubspaceId(8)).includes(&FakeSubspaceId(5)));
231    }
232
233    #[test]
234    fn subspace_area_intersects() {
235        // Non-empty intersections
236        let any_any_intersection =
237            AreaSubspace::<FakeSubspaceId>::Any.intersection(&AreaSubspace::<FakeSubspaceId>::Any);
238
239        assert!(any_any_intersection.is_some());
240
241        assert!(any_any_intersection.unwrap() == AreaSubspace::<FakeSubspaceId>::Any);
242
243        let any_id_intersection = AreaSubspace::<FakeSubspaceId>::Any
244            .intersection(&AreaSubspace::<FakeSubspaceId>::Id(FakeSubspaceId(6)));
245
246        assert!(any_id_intersection.is_some());
247
248        assert!(
249            any_id_intersection.unwrap() == AreaSubspace::<FakeSubspaceId>::Id(FakeSubspaceId(6))
250        );
251
252        let id_id_intersection = AreaSubspace::<FakeSubspaceId>::Id(FakeSubspaceId(6))
253            .intersection(&AreaSubspace::<FakeSubspaceId>::Id(FakeSubspaceId(6)));
254
255        assert!(id_id_intersection.is_some());
256
257        assert!(
258            id_id_intersection.unwrap() == AreaSubspace::<FakeSubspaceId>::Id(FakeSubspaceId(6))
259        );
260
261        // Empty intersections
262
263        let empty_id_id_intersection = AreaSubspace::<FakeSubspaceId>::Id(FakeSubspaceId(7))
264            .intersection(&AreaSubspace::<FakeSubspaceId>::Id(FakeSubspaceId(6)));
265
266        assert!(empty_id_id_intersection.is_none())
267    }
268
269    #[test]
270    fn area_full() {
271        let full_area = Area::<MCL, MCC, MPL, FakeSubspaceId>::new_full();
272
273        assert_eq!(
274            full_area,
275            Area {
276                subspace: AreaSubspace::Any,
277                path: Path::new_empty(),
278                times: Range::new_open(0)
279            }
280        )
281    }
282
283    #[test]
284    fn area_subspace() {
285        let subspace_area = Area::<MCL, MCC, MPL, FakeSubspaceId>::new_subspace(FakeSubspaceId(7));
286
287        assert_eq!(
288            subspace_area,
289            Area {
290                subspace: AreaSubspace::Id(FakeSubspaceId(7)),
291                path: Path::new_empty(),
292                times: Range::new_open(0)
293            }
294        )
295    }
296
297    #[test]
298    fn area_intersects() {
299        let empty_intersection_subspace = Area::<MCL, MCC, MPL, FakeSubspaceId> {
300            subspace: AreaSubspace::Id(FakeSubspaceId(1)),
301            path: Path::new_empty(),
302            times: Range::new_open(0),
303        }
304        .intersection(&Area {
305            subspace: AreaSubspace::Id(FakeSubspaceId(2)),
306            path: Path::new_empty(),
307            times: Range::new_open(0),
308        });
309
310        assert!(empty_intersection_subspace.is_none());
311
312        let empty_intersection_path = Area::<MCL, MCC, MPL, FakeSubspaceId> {
313            subspace: AreaSubspace::Id(FakeSubspaceId(1)),
314            path: Path::new_from_slice(&[Component::new(b"0").unwrap()]).unwrap(),
315            times: Range::new_open(0),
316        }
317        .intersection(&Area {
318            subspace: AreaSubspace::Id(FakeSubspaceId(1)),
319            path: Path::new_from_slice(&[Component::new(b"1").unwrap()]).unwrap(),
320            times: Range::new_open(0),
321        });
322
323        assert!(empty_intersection_path.is_none());
324
325        let empty_intersection_time = Area::<MCL, MCC, MPL, FakeSubspaceId> {
326            subspace: AreaSubspace::Id(FakeSubspaceId(1)),
327            path: Path::new_empty(),
328            times: Range::new_closed(0, 1).unwrap(),
329        }
330        .intersection(&Area {
331            subspace: AreaSubspace::Id(FakeSubspaceId(1)),
332            path: Path::new_empty(),
333            times: Range::new_closed(2, 3).unwrap(),
334        });
335
336        assert!(empty_intersection_time.is_none());
337
338        let intersection = Area::<MCL, MCC, MPL, FakeSubspaceId> {
339            subspace: AreaSubspace::Any,
340            path: Path::new_from_slice(&[Component::new(b"1").unwrap()]).unwrap(),
341            times: Range::new_closed(0, 10).unwrap(),
342        }
343        .intersection(&Area {
344            subspace: AreaSubspace::Id(FakeSubspaceId(1)),
345            path: Path::new_from_slice(&[
346                Component::new(b"1").unwrap(),
347                Component::new(b"2").unwrap(),
348            ])
349            .unwrap(),
350            times: Range::new_closed(5, 15).unwrap(),
351        });
352
353        assert!(intersection.is_some());
354
355        assert_eq!(
356            intersection.unwrap(),
357            Area {
358                subspace: AreaSubspace::Id(FakeSubspaceId(1)),
359                path: Path::new_from_slice(&[
360                    Component::new(b"1").unwrap(),
361                    Component::new(b"2").unwrap(),
362                ])
363                .unwrap(),
364                times: Range::new_closed(5, 10).unwrap(),
365            }
366        )
367    }
368}
willow_data_model/grouping/area.rs

willow_data_model/grouping/
area.rs
