willow_data_model/entry/entrylike.rs
1use core::cmp::Ordering;
2
3use crate::prelude::*;
4
5/// A trait describing the metadata associated with each Willow [Payload](https://willowprotocol.org/specs/data-model/index.html#Payload) string.
6///
7/// [Entries](https://willowprotocol.org/specs/data-model/index.html#Entry) are the central concept in Willow. In order to make any bytestring of data accessible to Willow, you need to create an Entry describing its metadata. Specifically, an Entry consists of
8///
9/// - a [namespace_id](https://willowprotocol.org/specs/data-model/index.html#entry_namespace_id) (roughly, this addresses a universe of Willow data, fully independent from all data (i.e., Entries) of different namespace ids) of type `N`,
10/// - a [subspace_id](https://willowprotocol.org/specs/data-model/index.html#entry_subspace_id) (roughly, a fully indendent part of a namespace, typically subspaces correspond to individual users) of type `S`,
11/// - a [path](https://willowprotocol.org/specs/data-model/index.html#entry_path) (roughly, a file-system-like way of arranging payloads hierarchically within a subspace) of type [`Path`],
12/// - a [timestamp](https://willowprotocol.org/specs/data-model/index.html#entry_timestamp) (newer Entries can overwrite certain older Entries),
13/// - a [payload_length](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) (the length of the payload string), and
14/// - a [payload_digest](https://willowprotocol.org/specs/data-model/index.html#entry_payload_digest) (a secure hash of the payload string being inserted into Willow).
15///
16/// This trait can be implemented by all types which provide at least this information. We use this trait in order to be able to abstract over specific implementations of entries. If you want a concrete type for representing entries, use the [`Entry`] struct.
17pub trait Entrylike<const MCL: usize, const MCC: usize, const MPL: usize, N, S, PD>:
18 Coordinatelike<MCL, MCC, MPL, S>
19{
20 /// Returns the [namespace_id](https://willowprotocol.org/specs/data-model/index.html#entry_namespace_id) of `self`.
21 fn wdm_namespace_id(&self) -> &N;
22
23 /// Returns the [payload_length](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) of `self`.
24 fn wdm_payload_length(&self) -> u64;
25
26 /// Returns the [payload_digest](https://willowprotocol.org/specs/data-model/index.html#entry_payload_digest) of `self`.
27 fn wdm_payload_digest(&self) -> &PD;
28}
29
30/// Methods for working with [`Entrylikes`](Entrylike).
31///
32/// This trait is automatically implemented by all types implmenting [`Entrylike`].
33pub trait EntrylikeExt<const MCL: usize, const MCC: usize, const MPL: usize, N, S, PD>:
34 Entrylike<MCL, MCC, MPL, N, S, PD> + CoordinatelikeExt<MCL, MCC, MPL, S>
35{
36 /// Returns whether `self` and `other` describe equal entries.
37 ///
38 /// # Examples
39 ///
40 /// ```
41 /// use willow_data_model::prelude::*;
42 ///
43 /// let entry = Entry::builder()
44 /// .namespace_id("family")
45 /// .subspace_id("alfie")
46 /// .path(Path::<4, 4, 4>::new())
47 /// .timestamp(12345)
48 /// .payload_digest("b")
49 /// .payload_length(17)
50 /// .build().unwrap();
51 ///
52 /// assert!(entry.wdm_entry_eq(&entry));
53 ///
54 /// let changed = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
55 /// assert!(!entry.wdm_entry_eq(&changed));
56 ///
57 /// ```
58 fn wdm_entry_eq<OtherEntry>(&self, other: &OtherEntry) -> bool
59 where
60 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
61 N: PartialEq,
62 S: PartialEq,
63 PD: PartialEq,
64 {
65 self.wdm_namespace_id() == other.wdm_namespace_id()
66 && self.wdm_coordinate_eq(other)
67 && self.wdm_payload_digest() == other.wdm_payload_digest()
68 && self.wdm_payload_length() == other.wdm_payload_length()
69 }
70
71 /// Returns whether `self` and `other` describe non-equal entries.
72 ///
73 /// # Examples
74 ///
75 /// ```
76 /// use willow_data_model::prelude::*;
77 ///
78 /// let entry = Entry::builder()
79 /// .namespace_id("family")
80 /// .subspace_id("alfie")
81 /// .path(Path::<4, 4, 4>::new())
82 /// .timestamp(12345)
83 /// .payload_digest("b")
84 /// .payload_length(17)
85 /// .build().unwrap();
86 ///
87 /// assert!(!entry.wdm_entry_ne(&entry));
88 ///
89 /// let changed = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
90 /// assert!(entry.wdm_entry_ne(&changed));
91 ///
92 /// ```
93 fn wdm_entry_ne<OtherEntry>(&self, other: &OtherEntry) -> bool
94 where
95 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
96 N: PartialEq,
97 S: PartialEq,
98 PD: PartialEq,
99 {
100 self.wdm_namespace_id() != other.wdm_namespace_id()
101 || self.wdm_coordinate_ne(other)
102 || self.wdm_payload_digest() != other.wdm_payload_digest()
103 || self.wdm_payload_length() != other.wdm_payload_length()
104 }
105
106 /// Compares `self` to another entry by [timestamp](https://willowprotocol.org/specs/data-model/index.html#entry_timestamp), [payload_digest](https://willowprotocol.org/specs/data-model/index.html#entry_payload_digest) (in case of a tie), and [payload_length](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) third (in case of yet another tie). See also [`EntrylikeExt::wdm_is_newer_than`] and [`EntrylikeExt::wdm_is_older_than`].
107 ///
108 /// Comparing recency is primarily important to determine [which entries overwrite each other](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning); the [`EntrylikeExt::wdm_prunes`] method checks for that directly.
109 ///
110 /// # Examples
111 ///
112 /// ```
113 /// use core::cmp::Ordering;
114 /// use willow_data_model::prelude::*;
115 ///
116 /// let entry = Entry::builder()
117 /// .namespace_id("family")
118 /// .subspace_id("alfie")
119 /// .path(Path::<4, 4, 4>::new())
120 /// .timestamp(12345)
121 /// .payload_digest("b")
122 /// .payload_length(17)
123 /// .build().unwrap();
124 ///
125 /// assert_eq!(entry.wdm_cmp_recency(&entry), Ordering::Equal);
126 ///
127 /// let lesser_timestamp = Entry::prefilled_builder(&entry).timestamp(5).build().unwrap();
128 /// assert_eq!(entry.wdm_cmp_recency(&lesser_timestamp), Ordering::Greater);
129 ///
130 /// let lesser_digest = Entry::prefilled_builder(&entry).payload_digest("a").build().unwrap();
131 /// assert_eq!(entry.wdm_cmp_recency(&lesser_digest), Ordering::Greater);
132 ///
133 /// let lesser_length = Entry::prefilled_builder(&entry).payload_length(0).build().unwrap();
134 /// assert_eq!(entry.wdm_cmp_recency(&lesser_length), Ordering::Greater);
135 ///
136 /// let greater_timestamp = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
137 /// assert_eq!(entry.wdm_cmp_recency(&greater_timestamp), Ordering::Less);
138 ///
139 /// let greater_digest = Entry::prefilled_builder(&entry).payload_digest("c").build().unwrap();
140 /// assert_eq!(entry.wdm_cmp_recency(&greater_digest), Ordering::Less);
141 ///
142 /// let greater_length = Entry::prefilled_builder(&entry).payload_length(99).build().unwrap();
143 /// assert_eq!(entry.wdm_cmp_recency(&greater_length), Ordering::Less);
144 /// ```
145 ///
146 /// [Spec definition](https://willowprotocol.org/specs/data-model/index.html#entry_newer).
147 fn wdm_cmp_recency<OtherEntry>(&self, other: &OtherEntry) -> Ordering
148 where
149 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
150 PD: Ord,
151 {
152 self.wdm_timestamp()
153 .cmp(&other.wdm_timestamp())
154 .then_with(|| {
155 self.wdm_payload_digest()
156 .cmp(other.wdm_payload_digest())
157 .then_with(|| self.wdm_payload_length().cmp(&other.wdm_payload_length()))
158 })
159 }
160
161 /// Returns whether this entry is strictly [newer](https://willowprotocol.org/specs/data-model/index.html#entry_newer) than another entry. See also [`EntrylikeExt::wdm_cmp_recency`] and [`EntrylikeExt::wdm_is_older_than`].
162 ///
163 /// Comparing recency is primarily important to determine [which entries overwrite each other](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning); the [`EntrylikeExt::wdm_prunes`] method checks for that directly.
164 ///
165 /// # Examples
166 ///
167 /// ```
168 /// use willow_data_model::prelude::*;
169 ///
170 /// let entry = Entry::builder()
171 /// .namespace_id("family")
172 /// .subspace_id("alfie")
173 /// .path(Path::<4, 4, 4>::new())
174 /// .timestamp(12345)
175 /// .payload_digest("b")
176 /// .payload_length(17)
177 /// .build().unwrap();
178 ///
179 /// assert!(!entry.wdm_is_newer_than(&entry));
180 ///
181 /// let lesser_timestamp = Entry::prefilled_builder(&entry).timestamp(5).build().unwrap();
182 /// assert!(entry.wdm_is_newer_than(&lesser_timestamp));
183 ///
184 /// let lesser_digest = Entry::prefilled_builder(&entry).payload_digest("a").build().unwrap();
185 /// assert!(entry.wdm_is_newer_than(&lesser_digest));
186 ///
187 /// let lesser_length = Entry::prefilled_builder(&entry).payload_length(0).build().unwrap();
188 /// assert!(entry.wdm_is_newer_than(&lesser_length));
189 ///
190 /// let greater_timestamp = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
191 /// assert!(!entry.wdm_is_newer_than(&greater_timestamp));
192 ///
193 /// let greater_digest = Entry::prefilled_builder(&entry).payload_digest("c").build().unwrap();
194 /// assert!(!entry.wdm_is_newer_than(&greater_digest));
195 ///
196 /// let greater_length = Entry::prefilled_builder(&entry).payload_length(99).build().unwrap();
197 /// assert!(!entry.wdm_is_newer_than(&greater_length));
198 /// ```
199 fn wdm_is_newer_than<OtherEntry>(&self, other: &OtherEntry) -> bool
200 where
201 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
202 PD: Ord,
203 {
204 self.wdm_cmp_recency(other) == Ordering::Greater
205 }
206
207 /// Returns whether this entry is strictly [older](https://willowprotocol.org/specs/data-model/index.html#entry_newer) than another entry. See also [`EntrylikeExt::wdm_cmp_recency`] and [`EntrylikeExt::wdm_is_newer_than`].
208 ///
209 /// Comparing recency is primarily important to determine [which entries overwrite each other](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning); the [`EntrylikeExt::wdm_prunes`] method checks for that directly.
210 ///
211 /// # Examples
212 ///
213 /// ```
214 /// use willow_data_model::prelude::*;
215 ///
216 /// let entry = Entry::builder()
217 /// .namespace_id("family")
218 /// .subspace_id("alfie")
219 /// .path(Path::<4, 4, 4>::new())
220 /// .timestamp(12345)
221 /// .payload_digest("b")
222 /// .payload_length(17)
223 /// .build().unwrap();
224 ///
225 /// assert!(!entry.wdm_is_older_than(&entry));
226 ///
227 /// let lesser_timestamp = Entry::prefilled_builder(&entry).timestamp(5).build().unwrap();
228 /// assert!(!entry.wdm_is_older_than(&lesser_timestamp));
229 ///
230 /// let lesser_digest = Entry::prefilled_builder(&entry).payload_digest("a").build().unwrap();
231 /// assert!(!entry.wdm_is_older_than(&lesser_digest));
232 ///
233 /// let lesser_length = Entry::prefilled_builder(&entry).payload_length(0).build().unwrap();
234 /// assert!(!entry.wdm_is_older_than(&lesser_length));
235 ///
236 /// let greater_timestamp = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
237 /// assert!(entry.wdm_is_older_than(&greater_timestamp));
238 ///
239 /// let greater_digest = Entry::prefilled_builder(&entry).payload_digest("c").build().unwrap();
240 /// assert!(entry.wdm_is_older_than(&greater_digest));
241 ///
242 /// let greater_length = Entry::prefilled_builder(&entry).payload_length(99).build().unwrap();
243 /// assert!(entry.wdm_is_older_than(&greater_length));
244 /// ```
245 fn wdm_is_older_than<OtherEntry>(&self, other: &OtherEntry) -> bool
246 where
247 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
248 PD: Ord,
249 {
250 self.wdm_cmp_recency(other) == Ordering::Less
251 }
252
253 /// Returns whether this entry would [prefix prune](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning) another entry.
254 ///
255 /// Prefix pruning powers deletion in Willow: whenever a data store would contain two entries, one of which pruens the other, the other is removed from the data store (or never inserted in the first place). Informally speaking, newer entries remove older entries, but only if they are in the same namespace and subspace, and only if the path of the newer entry is a prefix of the path of the older entry.
256 ///
257 /// More precisely: an entry `e1` prunes an entry `e2` if and only if
258 ///
259 /// - `e1.namespace_id() == e2.namespace_id()`,
260 /// - `e1.subspace_id() == e2.subspace_id()`,
261 /// - `e1.path().is_prefix_of(e2.path())`, and
262 /// - `e1.wdm_is_newer_than(&e2)`.
263 ///
264 /// This method is the reciprocal of [`EntrylikeExt::wdm_is_pruned_by`].
265 ///
266 /// # Examples
267 ///
268 ///
269 /// ```
270 /// use willow_data_model::prelude::*;
271 ///
272 /// let entry = Entry::builder()
273 /// .namespace_id("family")
274 /// .subspace_id("alfie")
275 /// .path(Path::<4, 4, 4>::from_slices(&[b"a", b"b"])?)
276 /// .timestamp(12345)
277 /// .payload_digest("b")
278 /// .payload_length(17)
279 /// .build().unwrap();
280 ///
281 /// let newer = Entry::prefilled_builder(&entry).timestamp(99999).build().unwrap();
282 /// assert!(!entry.wdm_prunes(&newer));
283 /// assert!(newer.wdm_prunes(&entry));
284 ///
285 /// let newer_and_prefix = Entry::prefilled_builder(&newer)
286 /// .path(Path::<4, 4, 4>::from_slices(&[b"a"])?).build().unwrap();
287 /// assert!(!entry.wdm_prunes(&newer_and_prefix));
288 /// assert!(newer_and_prefix.wdm_prunes(&entry));
289 ///
290 /// let newer_and_extension = Entry::prefilled_builder(&newer)
291 /// .path(Path::<4, 4, 4>::from_slices(&[b"a", b"b", b"c"])?).build().unwrap();
292 /// assert!(!entry.wdm_prunes(&newer_and_extension));
293 /// assert!(!newer_and_extension.wdm_prunes(&entry));
294 ///
295 /// let newer_but_unrelated_namespace = Entry::prefilled_builder(&newer)
296 /// .namespace_id("bookclub").build().unwrap();
297 /// assert!(!entry.wdm_prunes(&newer_but_unrelated_namespace));
298 /// assert!(!newer_but_unrelated_namespace.wdm_prunes(&entry));
299 ///
300 /// let newer_but_unrelated_subspace = Entry::prefilled_builder(&newer)
301 /// .subspace_id("betty").build().unwrap();
302 /// assert!(!entry.wdm_prunes(&newer_but_unrelated_subspace));
303 /// assert!(!newer_but_unrelated_subspace.wdm_prunes(&entry));
304 /// # Ok::<(), PathError>(())
305 /// ```
306 ///
307 fn wdm_prunes<OtherEntry>(&self, other: &OtherEntry) -> bool
308 where
309 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
310 N: PartialEq,
311 S: PartialEq,
312 PD: Ord,
313 {
314 self.wdm_is_newer_than(other)
315 && self.wdm_namespace_id() == other.wdm_namespace_id()
316 && self.wdm_subspace_id() == other.wdm_subspace_id()
317 && self.wdm_path().is_prefix_of(other.wdm_path())
318 }
319
320 /// Returns whether this entry would be [prefix pruned](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning) by another entry.
321 ///
322 /// Prefix pruning powers deletion in Willow: whenever a data store would contain two entries, one of which pruens the other, the other is removed from the data store (or never inserted in the first place). Informally speaking, newer entries remove older entries, but only if they are in the same namespace and subspace, and only if the path of the newer entry is a prefix of the path of the older entry.
323 ///
324 /// More precisely: an entry `e1` prunes an entry `e2` if and only if
325 ///
326 /// - `e1.namespace_id() == e2.namespace_id()`,
327 /// - `e1.subspace_id() == e2.subspace_id()`,
328 /// - `e1.path().is_prefix_of(e2.path())`, and
329 /// - `e1.wdm_is_newer_than(&e2)`.
330 ///
331 /// This method is the reciprocal of [`EntrylikeExt::wdm_prunes`].
332 ///
333 /// # Examples
334 ///
335 ///
336 /// ```
337 /// use willow_data_model::prelude::*;
338 ///
339 /// let entry = Entry::builder()
340 /// .namespace_id("family")
341 /// .subspace_id("alfie")
342 /// .path(Path::<4, 4, 4>::from_slices(&[b"a", b"b"])?)
343 /// .timestamp(12345)
344 /// .payload_digest("b")
345 /// .payload_length(17)
346 /// .build().unwrap();
347 ///
348 /// let newer = Entry::prefilled_builder(&entry).timestamp(99999).build().unwrap();
349 /// assert!(entry.wdm_is_pruned_by(&newer));
350 /// assert!(!newer.wdm_is_pruned_by(&entry));
351 ///
352 /// let newer_and_prefix = Entry::prefilled_builder(&newer)
353 /// .path(Path::<4, 4, 4>::from_slices(&[b"a"])?).build().unwrap();
354 /// assert!(entry.wdm_is_pruned_by(&newer_and_prefix));
355 /// assert!(!newer_and_prefix.wdm_is_pruned_by(&entry));
356 ///
357 /// let newer_and_extension = Entry::prefilled_builder(&newer)
358 /// .path(Path::<4, 4, 4>::from_slices(&[b"a", b"b", b"c"])?).build().unwrap();
359 /// assert!(!entry.wdm_is_pruned_by(&newer_and_extension));
360 /// assert!(!newer_and_extension.wdm_is_pruned_by(&entry));
361 ///
362 /// let newer_but_unrelated_namespace = Entry::prefilled_builder(&newer)
363 /// .namespace_id("bookclub").build().unwrap();
364 /// assert!(!entry.wdm_is_pruned_by(&newer_but_unrelated_namespace));
365 /// assert!(!newer_but_unrelated_namespace.wdm_is_pruned_by(&entry));
366 ///
367 /// let newer_but_unrelated_subspace = Entry::prefilled_builder(&newer)
368 /// .subspace_id("betty").build().unwrap();
369 /// assert!(!entry.wdm_is_pruned_by(&newer_but_unrelated_subspace));
370 /// assert!(!newer_but_unrelated_subspace.wdm_is_pruned_by(&entry));
371 /// # Ok::<(), PathError>(())
372 /// ```
373 ///
374 fn wdm_is_pruned_by<OtherEntry>(&self, other: &OtherEntry) -> bool
375 where
376 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
377 N: PartialEq,
378 S: PartialEq,
379 PD: Ord,
380 Self: Sized,
381 {
382 other.wdm_prunes(self)
383 }
384}
385
386impl<const MCL: usize, const MCC: usize, const MPL: usize, N, S, PD, E>
387 EntrylikeExt<MCL, MCC, MPL, N, S, PD> for E
388where
389 E: Entrylike<MCL, MCC, MPL, N, S, PD>,
390{
391}