willow_data_model/grouping/
area.rs

1#[cfg(feature = "dev")]
2use crate::{grouping::RangeEnd, parameters::SubspaceId, PathBuilder};
3#[cfg(feature = "dev")]
4use arbitrary::Arbitrary;
5
6use crate::{
7    entry::{Entry, Timestamp},
8    path::Path,
9};
10
11use super::range::Range;
12
13/// The possible values of an [`Area`]'s `subspace`.
14#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Hash)]
15#[cfg_attr(feature = "dev", derive(Arbitrary))]
16pub enum AreaSubspace<S> {
17    /// A value that signals that an [`Area`] includes Entries with arbitrary subspace_ids.
18    Any,
19    /// A concrete [`SubspaceId`].
20    Id(S),
21}
22
23impl<S> AreaSubspace<S> {
24    /// Returns whether this [`AreaSubspace`] includes Entries with arbitrary subspace_ids.
25    pub fn is_any(&self) -> bool {
26        matches!(self, AreaSubspace::Any)
27    }
28}
29
30impl<S> AreaSubspace<S>
31where
32    S: PartialEq,
33{
34    /// Returns whether this [`AreaSubspace`] includes a given [`SubspaceId`].
35    pub fn includes(&self, sub: &S) -> bool {
36        match self {
37            AreaSubspace::Any => true,
38            AreaSubspace::Id(id) => sub == id,
39        }
40    }
41}
42
43impl<S> AreaSubspace<S>
44where
45    S: PartialEq + Clone,
46{
47    /// Returns whether this [`AreaSubspace`] includes a given [`AreaSubspace`].
48    pub fn includes_area_subspace(&self, other: &Self) -> bool {
49        match (self, other) {
50            (AreaSubspace::Any, AreaSubspace::Any) => true,
51            (AreaSubspace::Any, AreaSubspace::Id(_)) => true,
52            (AreaSubspace::Id(_), AreaSubspace::Any) => false,
53            (AreaSubspace::Id(id), AreaSubspace::Id(id_other)) => id == id_other,
54        }
55    }
56
57    /// Returns the intersection between two [`AreaSubspace`].
58    fn intersection(&self, other: &Self) -> Option<Self> {
59        match (self, other) {
60            (Self::Any, Self::Any) => Some(Self::Any),
61            (Self::Id(a), Self::Any) => Some(Self::Id(a.clone())),
62            (Self::Any, Self::Id(b)) => Some(Self::Id(b.clone())),
63            (Self::Id(a), Self::Id(b)) if a == b => Some(Self::Id(a.clone())),
64            (Self::Id(_a), Self::Id(_b)) => None,
65        }
66    }
67}
68
69impl<S: PartialEq> PartialEq<S> for AreaSubspace<S> {
70    fn eq(&self, other: &S) -> bool {
71        match self {
72            AreaSubspace::Any => false,
73            AreaSubspace::Id(s) => s == other,
74        }
75    }
76}
77
78/// A grouping of entries.
79///
80/// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#areas).
81#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Hash)]
82#[cfg_attr(feature = "dev", derive(Arbitrary))]
83pub struct Area<const MCL: usize, const MCC: usize, const MPL: usize, S> {
84    /// To be included in this [`Area`], an [`Entry`]’s `subspace_id` must be equal to the subspace_id, unless it is any.
85    subspace: AreaSubspace<S>,
86    /// To be included in this [`Area`], an [`Entry`]’s `path` must be prefixed by the path.
87    path: Path<MCL, MCC, MPL>,
88    /// To be included in this [`Area`], an [`Entry`]’s `timestamp` must be included in the times.
89    times: Range<Timestamp>,
90}
91
92impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Area<MCL, MCC, MPL, S> {
93    /// Creates a new [`Area`].
94    pub fn new(
95        subspace: AreaSubspace<S>,
96        path: Path<MCL, MCC, MPL>,
97        times: Range<Timestamp>,
98    ) -> Self {
99        Area {
100            subspace,
101            path,
102            times,
103        }
104    }
105
106    /// Returns a reference to the [`AreaSubspace`].
107    ///
108    /// To be included in this [`Area`], an [`Entry`]’s `subspace_id` must be equal to the subspace_id, unless it is any.
109    pub fn subspace(&self) -> &AreaSubspace<S> {
110        &self.subspace
111    }
112
113    /// Returns a reference to the [`Path`].
114    ///
115    /// To be included in this [`Area`], an [`Entry`]’s `path` must be prefixed by the path.
116    pub fn path(&self) -> &Path<MCL, MCC, MPL> {
117        &self.path
118    }
119
120    /// Returns a reference to the range of [`Timestamp`]s.
121    ///
122    /// To be included in this [`Area`], an [`Entry`]’s `timestamp` must be included in the times.
123    pub fn times(&self) -> &Range<Timestamp> {
124        &self.times
125    }
126
127    /// Returns an [`Area`] which includes all entries.
128    ///
129    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#full_area).
130    pub fn new_full() -> Self {
131        Self {
132            subspace: AreaSubspace::Any,
133            path: Path::new_empty(),
134            times: Range::new_open(0),
135        }
136    }
137
138    /// Returns an [`Area`] which includes all entries within a given [subspace](https://willowprotocol.org/specs/data-model/index.html#subspace).
139    ///
140    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#subspace_area).
141    pub fn new_subspace(sub: S) -> Self {
142        Self {
143            subspace: AreaSubspace::Id(sub),
144            path: Path::new_empty(),
145            times: Range::new_open(0),
146        }
147    }
148}
149
150impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Area<MCL, MCC, MPL, S>
151where
152    S: PartialEq,
153{
154    /// Returns whether an [`Area`] [includes](https://willowprotocol.org/specs/grouping-entries/index.html#area_include) an [`Entry`].
155    pub fn includes_entry<N, PD>(&self, entry: &Entry<MCL, MCC, MPL, N, S, PD>) -> bool {
156        self.includes_triplet(entry.subspace_id(), entry.path(), entry.timestamp())
157    }
158
159    /// Returns whether an [`Area`] [includes](https://willowprotocol.org/specs/grouping-entries/index.html#area_include) includes an entry with a given subspace_id, path, and timestamp.
160    pub fn includes_triplet(
161        &self,
162        subspace_id: &S,
163        path: &Path<MCL, MCC, MPL>,
164        timestamp: Timestamp,
165    ) -> bool {
166        self.subspace.includes(subspace_id)
167            && self.path.is_prefix_of(path)
168            && self.times.includes(&timestamp)
169    }
170
171    /// Returns whether an [`Area`] fully [includes](https://willowprotocol.org/specs/grouping-entries/index.html#area_include_area) another [`Area`].
172    pub fn includes_area(&self, area: &Self) -> bool {
173        match (&self.subspace, &area.subspace) {
174            (AreaSubspace::Any, AreaSubspace::Any) => {
175                self.path.is_prefix_of(&area.path) && self.times.includes_range(&area.times)
176            }
177            (AreaSubspace::Any, AreaSubspace::Id(_)) => {
178                self.path.is_prefix_of(&area.path) && self.times.includes_range(&area.times)
179            }
180            (AreaSubspace::Id(_), AreaSubspace::Any) => false,
181            (AreaSubspace::Id(subspace_a), AreaSubspace::Id(subspace_b)) => {
182                subspace_a == subspace_b
183                    && self.path.is_prefix_of(&area.path)
184                    && self.times.includes_range(&area.times)
185            }
186        }
187    }
188
189    /// Returns whether an [`Entry`] can cause prefix-pruning in this [`Area`].
190    pub fn could_be_pruned_by<N, PD>(&self, entry: &Entry<MCL, MCC, MPL, N, S, PD>) -> bool {
191        self.could_be_pruned_by_triplet(entry.subspace_id(), entry.path(), entry.timestamp())
192    }
193
194    /// Returns whether an [`Entry`] of the given subspace_id, path, and timestamp can cause prefix-pruning in this [`Area`].
195    pub fn could_be_pruned_by_triplet(
196        &self,
197        subspace_id: &S,
198        path: &Path<MCL, MCC, MPL>,
199        timestamp: Timestamp,
200    ) -> bool {
201        if let AreaSubspace::Id(my_subspace_id) = self.subspace() {
202            if my_subspace_id != subspace_id {
203                return false;
204            }
205        }
206
207        if !(self.times().includes(&timestamp) || timestamp < self.times().start) {
208            return false;
209        }
210
211        path.is_prefix_of(&self.path) || path.is_prefixed_by(&self.path)
212    }
213}
214
215impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Area<MCL, MCC, MPL, S>
216where
217    S: PartialEq + Clone,
218{
219    /// Returns the intersection of this [`Area`] with another.
220    ///
221    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#area_intersection).
222    pub fn intersection(&self, other: &Area<MCL, MCC, MPL, S>) -> Option<Self> {
223        let subspace_id = self.subspace.intersection(&other.subspace)?;
224        let path = if self.path.is_prefix_of(&other.path) {
225            Some(other.path.clone())
226        } else if self.path.is_prefixed_by(&other.path) {
227            Some(self.path.clone())
228        } else {
229            None
230        }?;
231        let times = self.times.intersection(&other.times)?;
232        Some(Self {
233            subspace: subspace_id,
234            times,
235            path,
236        })
237    }
238
239    /// Returns whether an [`Area`] _almost includes_ another area, that is, if the other [`Area`] would be included by this if [`Area] if it had the same [`SubspaceId`].
240    pub fn almost_includes_area(&self, other: &Area<MCL, MCC, MPL, S>) -> bool {
241        let subspace_is_fine = match (self.subspace(), other.subspace()) {
242            (AreaSubspace::Id(self_id), AreaSubspace::Id(other_id)) => self_id == other_id,
243            _ => true,
244        };
245        subspace_is_fine
246            && self.path.is_prefix_of(&other.path)
247            && self.times.includes_range(&other.times)
248    }
249}
250
251#[cfg(feature = "dev")]
252pub fn arbitrary_included_area<'a, const MCL: usize, const MCC: usize, const MPL: usize, S>(
253    area: &Area<MCL, MCC, MPL, S>,
254    u: &mut arbitrary::Unstructured<'a>,
255) -> arbitrary::Result<Area<MCL, MCC, MPL, S>>
256where
257    S: SubspaceId + Arbitrary<'a>,
258{
259    let suffix: Path<MCL, MCC, MPL> = Arbitrary::arbitrary(u)?;
260
261    let total_length = area.path().path_length() + suffix.path_length();
262    let total_component_length = area.path().component_count() + suffix.component_count();
263
264    let included_path = if let Ok(mut builder) = PathBuilder::new_from_prefix(
265        total_length,
266        total_component_length,
267        area.path(),
268        area.path.component_count(),
269    ) {
270        for component in suffix.components() {
271            builder.append_component(component)
272        }
273
274        builder.build()
275    } else {
276        area.path().clone()
277    };
278
279    let subspace = match area.subspace() {
280        AreaSubspace::Any => {
281            let is_subspace: bool = Arbitrary::arbitrary(u)?;
282
283            if is_subspace {
284                let subspace: S = Arbitrary::arbitrary(u)?;
285                AreaSubspace::Id(subspace)
286            } else {
287                AreaSubspace::Any
288            }
289        }
290        AreaSubspace::Id(id) => AreaSubspace::Id(id.clone()),
291    };
292
293    let start_offset: u64 = Arbitrary::arbitrary(u)?;
294
295    let new_start = area
296        .times()
297        .start
298        .checked_add(start_offset)
299        .map_or(area.times().start, |res| res);
300
301    let end_offset: u64 = Arbitrary::arbitrary(u)?;
302
303    let new_end = match area.times().end {
304        crate::grouping::RangeEnd::Closed(end) => {
305            RangeEnd::Closed(end.checked_sub(end_offset).map_or(end, |res| res))
306        }
307        crate::grouping::RangeEnd::Open => {
308            let is_any: bool = Arbitrary::arbitrary(u)?;
309
310            if is_any {
311                RangeEnd::Open
312            } else {
313                RangeEnd::Closed(end_offset)
314            }
315        }
316    };
317
318    let times = if new_start <= new_end {
319        Range::new(new_start, new_end)
320    } else {
321        *area.times()
322    };
323
324    Ok(Area::new(subspace, included_path, times))
325}
326
327#[cfg(test)]
328mod tests {
329
330    use crate::path::Component;
331
332    use super::*;
333
334    const MCL: usize = 8;
335    const MCC: usize = 4;
336    const MPL: usize = 16;
337
338    #[test]
339    fn subspace_area_includes() {
340        assert!(AreaSubspace::<u64>::Any.includes(&5));
341        assert!(AreaSubspace::<u64>::Id(5).includes(&5));
342        assert!(!AreaSubspace::<u64>::Id(8).includes(&5));
343    }
344
345    #[test]
346    fn subspace_area_intersects() {
347        // Non-empty intersections
348        let any_any_intersection = AreaSubspace::<u64>::Any.intersection(&AreaSubspace::<u64>::Any);
349
350        assert!(any_any_intersection.is_some());
351
352        assert!(any_any_intersection.unwrap() == AreaSubspace::<u64>::Any);
353
354        let any_id_intersection =
355            AreaSubspace::<u64>::Any.intersection(&AreaSubspace::<u64>::Id(6));
356
357        assert!(any_id_intersection.is_some());
358
359        assert!(any_id_intersection.unwrap() == AreaSubspace::<u64>::Id(6));
360
361        let id_id_intersection =
362            AreaSubspace::<u64>::Id(6).intersection(&AreaSubspace::<u64>::Id(6));
363
364        assert!(id_id_intersection.is_some());
365
366        assert!(id_id_intersection.unwrap() == AreaSubspace::<u64>::Id(6));
367
368        // Empty intersections
369
370        let empty_id_id_intersection =
371            AreaSubspace::<u64>::Id(7).intersection(&AreaSubspace::<u64>::Id(6));
372
373        assert!(empty_id_id_intersection.is_none())
374    }
375
376    #[test]
377    fn area_full() {
378        let full_area = Area::<MCL, MCC, MPL, u64>::new_full();
379
380        assert_eq!(
381            full_area,
382            Area {
383                subspace: AreaSubspace::Any,
384                path: Path::new_empty(),
385                times: Range::new_open(0)
386            }
387        )
388    }
389
390    #[test]
391    fn area_subspace() {
392        let subspace_area = Area::<MCL, MCC, MPL, u64>::new_subspace(7);
393
394        assert_eq!(
395            subspace_area,
396            Area {
397                subspace: AreaSubspace::Id(7),
398                path: Path::new_empty(),
399                times: Range::new_open(0)
400            }
401        )
402    }
403
404    #[test]
405    fn area_intersects() {
406        let empty_intersection_subspace = Area::<MCL, MCC, MPL, u64> {
407            subspace: AreaSubspace::Id(1),
408            path: Path::new_empty(),
409            times: Range::new_open(0),
410        }
411        .intersection(&Area {
412            subspace: AreaSubspace::Id(2),
413            path: Path::new_empty(),
414            times: Range::new_open(0),
415        });
416
417        assert!(empty_intersection_subspace.is_none());
418
419        let empty_intersection_path = Area::<MCL, MCC, MPL, u64> {
420            subspace: AreaSubspace::Id(1),
421            path: Path::new_from_slice(&[Component::new(b"0").unwrap()]).unwrap(),
422            times: Range::new_open(0),
423        }
424        .intersection(&Area {
425            subspace: AreaSubspace::Id(1),
426            path: Path::new_from_slice(&[Component::new(b"1").unwrap()]).unwrap(),
427            times: Range::new_open(0),
428        });
429
430        assert!(empty_intersection_path.is_none());
431
432        let empty_intersection_time = Area::<MCL, MCC, MPL, u64> {
433            subspace: AreaSubspace::Id(1),
434            path: Path::new_empty(),
435            times: Range::new_closed(0, 1).unwrap(),
436        }
437        .intersection(&Area {
438            subspace: AreaSubspace::Id(1),
439            path: Path::new_empty(),
440            times: Range::new_closed(2, 3).unwrap(),
441        });
442
443        assert!(empty_intersection_time.is_none());
444
445        let intersection = Area::<MCL, MCC, MPL, u64> {
446            subspace: AreaSubspace::Any,
447            path: Path::new_from_slice(&[Component::new(b"1").unwrap()]).unwrap(),
448            times: Range::new_closed(0, 10).unwrap(),
449        }
450        .intersection(&Area {
451            subspace: AreaSubspace::Id(1),
452            path: Path::new_from_slice(&[
453                Component::new(b"1").unwrap(),
454                Component::new(b"2").unwrap(),
455            ])
456            .unwrap(),
457            times: Range::new_closed(5, 15).unwrap(),
458        });
459
460        assert!(intersection.is_some());
461
462        assert_eq!(
463            intersection.unwrap(),
464            Area {
465                subspace: AreaSubspace::Id(1),
466                path: Path::new_from_slice(&[
467                    Component::new(b"1").unwrap(),
468                    Component::new(b"2").unwrap(),
469                ])
470                .unwrap(),
471                times: Range::new_closed(5, 10).unwrap(),
472            }
473        )
474    }
475}
willow_data_model/grouping/area.rs

willow_data_model/grouping/
area.rs
