willow_data_model/entry/entrylike.rs
1use core::cmp::Ordering;
2use core::fmt::Debug;
3
4use compact_u64::{cu64_encode_standalone, cu64_len_of_encoding};
5use ufotofu::codec_prelude::*;
6
7use crate::prelude::*;
8
9/// A trait describing the metadata associated with each Willow [Payload](https://willowprotocol.org/specs/data-model/index.html#Payload) string.
10///
11/// [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
12///
13/// - 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`,
14/// - 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`,
15/// - 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`],
16/// - a [timestamp](https://willowprotocol.org/specs/data-model/index.html#entry_timestamp) (newer Entries can overwrite certain older Entries),
17/// - a [payload_length](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) (the length of the payload string), and
18/// - 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).
19///
20/// 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.
21pub trait Entrylike<const MCL: usize, const MCC: usize, const MPL: usize, N, S, PD>:
22 Coordinatelike<MCL, MCC, MPL, S> + Namespaced<N>
23{
24 /// Returns the [payload_length](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) of `self`.
25 fn wdm_payload_length(&self) -> u64;
26
27 /// Returns the [payload_digest](https://willowprotocol.org/specs/data-model/index.html#entry_payload_digest) of `self`.
28 fn wdm_payload_digest(&self) -> &PD;
29}
30
31/// Methods for working with [`Entrylikes`](Entrylike).
32///
33/// This trait is automatically implemented by all types implmenting [`Entrylike`].
34pub trait EntrylikeExt<const MCL: usize, const MCC: usize, const MPL: usize, N, S, PD>:
35 Entrylike<MCL, MCC, MPL, N, S, PD> + CoordinatelikeExt<MCL, MCC, MPL, S>
36{
37 /// Returns whether `self` and `other` describe equal entries.
38 ///
39 /// # Examples
40 ///
41 /// ```
42 /// use willow_data_model::prelude::*;
43 ///
44 /// let entry = Entry::builder()
45 /// .namespace_id("family")
46 /// .subspace_id("alfie")
47 /// .path(Path::<4, 4, 4>::new())
48 /// .timestamp(12345)
49 /// .payload_digest("b")
50 /// .payload_length(17)
51 /// .build().unwrap();
52 ///
53 /// assert!(entry.wdm_entry_eq(&entry));
54 ///
55 /// let changed = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
56 /// assert!(!entry.wdm_entry_eq(&changed));
57 ///
58 /// ```
59 fn wdm_entry_eq<OtherEntry>(&self, other: &OtherEntry) -> bool
60 where
61 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
62 N: PartialEq,
63 S: PartialEq,
64 PD: PartialEq,
65 {
66 self.wdm_namespace_id() == other.wdm_namespace_id()
67 && self.wdm_coordinate_eq(other)
68 && self.wdm_payload_digest() == other.wdm_payload_digest()
69 && self.wdm_payload_length() == other.wdm_payload_length()
70 }
71
72 /// Returns whether `self` and `other` describe non-equal entries.
73 ///
74 /// # Examples
75 ///
76 /// ```
77 /// use willow_data_model::prelude::*;
78 ///
79 /// let entry = Entry::builder()
80 /// .namespace_id("family")
81 /// .subspace_id("alfie")
82 /// .path(Path::<4, 4, 4>::new())
83 /// .timestamp(12345)
84 /// .payload_digest("b")
85 /// .payload_length(17)
86 /// .build().unwrap();
87 ///
88 /// assert!(!entry.wdm_entry_ne(&entry));
89 ///
90 /// let changed = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
91 /// assert!(entry.wdm_entry_ne(&changed));
92 ///
93 /// ```
94 fn wdm_entry_ne<OtherEntry>(&self, other: &OtherEntry) -> bool
95 where
96 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
97 N: PartialEq,
98 S: PartialEq,
99 PD: PartialEq,
100 {
101 self.wdm_namespace_id() != other.wdm_namespace_id()
102 || self.wdm_coordinate_ne(other)
103 || self.wdm_payload_digest() != other.wdm_payload_digest()
104 || self.wdm_payload_length() != other.wdm_payload_length()
105 }
106
107 /// 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`].
108 ///
109 /// 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.
110 ///
111 /// # Examples
112 ///
113 /// ```
114 /// use core::cmp::Ordering;
115 /// use willow_data_model::prelude::*;
116 ///
117 /// let entry = Entry::builder()
118 /// .namespace_id("family")
119 /// .subspace_id("alfie")
120 /// .path(Path::<4, 4, 4>::new())
121 /// .timestamp(12345)
122 /// .payload_digest("b")
123 /// .payload_length(17)
124 /// .build().unwrap();
125 ///
126 /// assert_eq!(entry.wdm_cmp_recency(&entry), Ordering::Equal);
127 ///
128 /// let lesser_timestamp = Entry::prefilled_builder(&entry).timestamp(5).build().unwrap();
129 /// assert_eq!(entry.wdm_cmp_recency(&lesser_timestamp), Ordering::Greater);
130 ///
131 /// let lesser_digest = Entry::prefilled_builder(&entry).payload_digest("a").build().unwrap();
132 /// assert_eq!(entry.wdm_cmp_recency(&lesser_digest), Ordering::Greater);
133 ///
134 /// let lesser_length = Entry::prefilled_builder(&entry).payload_length(0).build().unwrap();
135 /// assert_eq!(entry.wdm_cmp_recency(&lesser_length), Ordering::Greater);
136 ///
137 /// let greater_timestamp = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
138 /// assert_eq!(entry.wdm_cmp_recency(&greater_timestamp), Ordering::Less);
139 ///
140 /// let greater_digest = Entry::prefilled_builder(&entry).payload_digest("c").build().unwrap();
141 /// assert_eq!(entry.wdm_cmp_recency(&greater_digest), Ordering::Less);
142 ///
143 /// let greater_length = Entry::prefilled_builder(&entry).payload_length(99).build().unwrap();
144 /// assert_eq!(entry.wdm_cmp_recency(&greater_length), Ordering::Less);
145 /// ```
146 ///
147 /// [Spec definition](https://willowprotocol.org/specs/data-model/index.html#entry_newer).
148 fn wdm_cmp_recency<OtherEntry>(&self, other: &OtherEntry) -> Ordering
149 where
150 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
151 PD: Ord,
152 {
153 self.wdm_timestamp()
154 .cmp(&other.wdm_timestamp())
155 .then_with(|| {
156 self.wdm_payload_digest()
157 .cmp(other.wdm_payload_digest())
158 .then_with(|| self.wdm_payload_length().cmp(&other.wdm_payload_length()))
159 })
160 }
161
162 /// 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`].
163 ///
164 /// 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.
165 ///
166 /// # Examples
167 ///
168 /// ```
169 /// use willow_data_model::prelude::*;
170 ///
171 /// let entry = Entry::builder()
172 /// .namespace_id("family")
173 /// .subspace_id("alfie")
174 /// .path(Path::<4, 4, 4>::new())
175 /// .timestamp(12345)
176 /// .payload_digest("b")
177 /// .payload_length(17)
178 /// .build().unwrap();
179 ///
180 /// assert!(!entry.wdm_is_newer_than(&entry));
181 ///
182 /// let lesser_timestamp = Entry::prefilled_builder(&entry).timestamp(5).build().unwrap();
183 /// assert!(entry.wdm_is_newer_than(&lesser_timestamp));
184 ///
185 /// let lesser_digest = Entry::prefilled_builder(&entry).payload_digest("a").build().unwrap();
186 /// assert!(entry.wdm_is_newer_than(&lesser_digest));
187 ///
188 /// let lesser_length = Entry::prefilled_builder(&entry).payload_length(0).build().unwrap();
189 /// assert!(entry.wdm_is_newer_than(&lesser_length));
190 ///
191 /// let greater_timestamp = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
192 /// assert!(!entry.wdm_is_newer_than(&greater_timestamp));
193 ///
194 /// let greater_digest = Entry::prefilled_builder(&entry).payload_digest("c").build().unwrap();
195 /// assert!(!entry.wdm_is_newer_than(&greater_digest));
196 ///
197 /// let greater_length = Entry::prefilled_builder(&entry).payload_length(99).build().unwrap();
198 /// assert!(!entry.wdm_is_newer_than(&greater_length));
199 /// ```
200 fn wdm_is_newer_than<OtherEntry>(&self, other: &OtherEntry) -> bool
201 where
202 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
203 PD: Ord,
204 {
205 self.wdm_cmp_recency(other) == Ordering::Greater
206 }
207
208 /// 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`].
209 ///
210 /// 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.
211 ///
212 /// # Examples
213 ///
214 /// ```
215 /// use willow_data_model::prelude::*;
216 ///
217 /// let entry = Entry::builder()
218 /// .namespace_id("family")
219 /// .subspace_id("alfie")
220 /// .path(Path::<4, 4, 4>::new())
221 /// .timestamp(12345)
222 /// .payload_digest("b")
223 /// .payload_length(17)
224 /// .build().unwrap();
225 ///
226 /// assert!(!entry.wdm_is_older_than(&entry));
227 ///
228 /// let lesser_timestamp = Entry::prefilled_builder(&entry).timestamp(5).build().unwrap();
229 /// assert!(!entry.wdm_is_older_than(&lesser_timestamp));
230 ///
231 /// let lesser_digest = Entry::prefilled_builder(&entry).payload_digest("a").build().unwrap();
232 /// assert!(!entry.wdm_is_older_than(&lesser_digest));
233 ///
234 /// let lesser_length = Entry::prefilled_builder(&entry).payload_length(0).build().unwrap();
235 /// assert!(!entry.wdm_is_older_than(&lesser_length));
236 ///
237 /// let greater_timestamp = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
238 /// assert!(entry.wdm_is_older_than(&greater_timestamp));
239 ///
240 /// let greater_digest = Entry::prefilled_builder(&entry).payload_digest("c").build().unwrap();
241 /// assert!(entry.wdm_is_older_than(&greater_digest));
242 ///
243 /// let greater_length = Entry::prefilled_builder(&entry).payload_length(99).build().unwrap();
244 /// assert!(entry.wdm_is_older_than(&greater_length));
245 /// ```
246 fn wdm_is_older_than<OtherEntry>(&self, other: &OtherEntry) -> bool
247 where
248 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
249 PD: Ord,
250 {
251 self.wdm_cmp_recency(other) == Ordering::Less
252 }
253
254 /// Returns whether this entry would [prefix prune](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning) another entry.
255 ///
256 /// 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.
257 ///
258 /// More precisely: an entry `e1` prunes an entry `e2` if and only if
259 ///
260 /// - `e1.namespace_id() == e2.namespace_id()`,
261 /// - `e1.subspace_id() == e2.subspace_id()`,
262 /// - `e1.path().is_prefix_of(e2.path())`, and
263 /// - `e1.wdm_is_newer_than(&e2)`.
264 ///
265 /// This method is the reciprocal of [`EntrylikeExt::wdm_is_pruned_by`].
266 ///
267 /// # Examples
268 ///
269 ///
270 /// ```
271 /// use willow_data_model::prelude::*;
272 ///
273 /// let entry = Entry::builder()
274 /// .namespace_id("family")
275 /// .subspace_id("alfie")
276 /// .path(Path::<4, 4, 4>::from_slices(&[b"a", b"b"])?)
277 /// .timestamp(12345)
278 /// .payload_digest("b")
279 /// .payload_length(17)
280 /// .build().unwrap();
281 ///
282 /// let newer = Entry::prefilled_builder(&entry).timestamp(99999).build().unwrap();
283 /// assert!(!entry.wdm_prunes(&newer));
284 /// assert!(newer.wdm_prunes(&entry));
285 ///
286 /// let newer_and_prefix = Entry::prefilled_builder(&newer)
287 /// .path(Path::<4, 4, 4>::from_slices(&[b"a"])?).build().unwrap();
288 /// assert!(!entry.wdm_prunes(&newer_and_prefix));
289 /// assert!(newer_and_prefix.wdm_prunes(&entry));
290 ///
291 /// let newer_and_extension = Entry::prefilled_builder(&newer)
292 /// .path(Path::<4, 4, 4>::from_slices(&[b"a", b"b", b"c"])?).build().unwrap();
293 /// assert!(!entry.wdm_prunes(&newer_and_extension));
294 /// assert!(!newer_and_extension.wdm_prunes(&entry));
295 ///
296 /// let newer_but_unrelated_namespace = Entry::prefilled_builder(&newer)
297 /// .namespace_id("bookclub").build().unwrap();
298 /// assert!(!entry.wdm_prunes(&newer_but_unrelated_namespace));
299 /// assert!(!newer_but_unrelated_namespace.wdm_prunes(&entry));
300 ///
301 /// let newer_but_unrelated_subspace = Entry::prefilled_builder(&newer)
302 /// .subspace_id("betty").build().unwrap();
303 /// assert!(!entry.wdm_prunes(&newer_but_unrelated_subspace));
304 /// assert!(!newer_but_unrelated_subspace.wdm_prunes(&entry));
305 /// # Ok::<(), PathError>(())
306 /// ```
307 ///
308 fn wdm_prunes<OtherEntry>(&self, other: &OtherEntry) -> bool
309 where
310 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
311 N: PartialEq,
312 S: PartialEq,
313 PD: Ord,
314 {
315 self.wdm_is_newer_than(other)
316 && self.wdm_namespace_id() == other.wdm_namespace_id()
317 && self.wdm_subspace_id() == other.wdm_subspace_id()
318 && self.wdm_path().is_prefix_of(other.wdm_path())
319 }
320
321 /// Returns whether this entry would be [prefix pruned](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning) by another entry.
322 ///
323 /// 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.
324 ///
325 /// More precisely: an entry `e1` prunes an entry `e2` if and only if
326 ///
327 /// - `e1.namespace_id() == e2.namespace_id()`,
328 /// - `e1.subspace_id() == e2.subspace_id()`,
329 /// - `e1.path().is_prefix_of(e2.path())`, and
330 /// - `e1.wdm_is_newer_than(&e2)`.
331 ///
332 /// This method is the reciprocal of [`EntrylikeExt::wdm_prunes`].
333 ///
334 /// # Examples
335 ///
336 ///
337 /// ```
338 /// use willow_data_model::prelude::*;
339 ///
340 /// let entry = Entry::builder()
341 /// .namespace_id("family")
342 /// .subspace_id("alfie")
343 /// .path(Path::<4, 4, 4>::from_slices(&[b"a", b"b"])?)
344 /// .timestamp(12345)
345 /// .payload_digest("b")
346 /// .payload_length(17)
347 /// .build().unwrap();
348 ///
349 /// let newer = Entry::prefilled_builder(&entry).timestamp(99999).build().unwrap();
350 /// assert!(entry.wdm_is_pruned_by(&newer));
351 /// assert!(!newer.wdm_is_pruned_by(&entry));
352 ///
353 /// let newer_and_prefix = Entry::prefilled_builder(&newer)
354 /// .path(Path::<4, 4, 4>::from_slices(&[b"a"])?).build().unwrap();
355 /// assert!(entry.wdm_is_pruned_by(&newer_and_prefix));
356 /// assert!(!newer_and_prefix.wdm_is_pruned_by(&entry));
357 ///
358 /// let newer_and_extension = Entry::prefilled_builder(&newer)
359 /// .path(Path::<4, 4, 4>::from_slices(&[b"a", b"b", b"c"])?).build().unwrap();
360 /// assert!(!entry.wdm_is_pruned_by(&newer_and_extension));
361 /// assert!(!newer_and_extension.wdm_is_pruned_by(&entry));
362 ///
363 /// let newer_but_unrelated_namespace = Entry::prefilled_builder(&newer)
364 /// .namespace_id("bookclub").build().unwrap();
365 /// assert!(!entry.wdm_is_pruned_by(&newer_but_unrelated_namespace));
366 /// assert!(!newer_but_unrelated_namespace.wdm_is_pruned_by(&entry));
367 ///
368 /// let newer_but_unrelated_subspace = Entry::prefilled_builder(&newer)
369 /// .subspace_id("betty").build().unwrap();
370 /// assert!(!entry.wdm_is_pruned_by(&newer_but_unrelated_subspace));
371 /// assert!(!newer_but_unrelated_subspace.wdm_is_pruned_by(&entry));
372 /// # Ok::<(), PathError>(())
373 /// ```
374 ///
375 fn wdm_is_pruned_by<OtherEntry>(&self, other: &OtherEntry) -> bool
376 where
377 OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
378 N: PartialEq,
379 S: PartialEq,
380 PD: Ord,
381 Self: Sized,
382 {
383 other.wdm_prunes(self)
384 }
385
386 /// Turns `self` into an [`AuthorisedEntry`] by creating an authorisation token for it.
387 ///
388 /// ```
389 /// # #[cfg(feature = "dev")] {
390 /// use willow_data_model::prelude::*;
391 /// use willow_data_model::test_parameters::*;
392 ///
393 /// let entry = Entry::builder()
394 /// .namespace_id(Family)
395 /// .subspace_id(Alfie)
396 /// .path(Path::<4, 4, 4>::new())
397 /// .timestamp(12345)
398 /// .payload_digest(Spades)
399 /// .payload_length(2)
400 /// .build().unwrap();
401 ///
402 /// let authed = entry.wdm_authorise::<TestSubspaceSignature>(&AlfieSecret).unwrap();
403 /// assert_eq!(authed.as_entry(), &entry);
404 /// assert_eq!(authed.as_authorisation_token(), &AlfieSignature);
405 /// # }
406 /// ```
407 fn wdm_authorise<AT>(
408 &self,
409 ingredients: &AT::Ingredients,
410 ) -> Result<AuthorisedEntry<MCL, MCC, MPL, N, S, PD, AT>, AT::CreationError>
411 where
412 AT: AuthorisationToken<MCL, MCC, MPL, N, S, PD> + Debug,
413 N: Clone + Debug,
414 S: Clone + Debug,
415 PD: Clone + Debug,
416 {
417 let authorisation_token = AuthorisationToken::new_for_entry(self, ingredients)?;
418
419 Ok(PossiblyAuthorisedEntry {
420 entry: Entry::from_entrylike(self),
421 authorisation_token,
422 }
423 .into_authorised_entry().expect("AuthorisationToken::new_for_entry must produce an authorisation token that authorises the entry"))
424 }
425
426 /// Encodes `self` according to the [encode_entry](https://willowprotocol.org/specs/encodings/index.html#encode_entry) encoding function.
427 async fn wdm_encode_entry<C>(&self, consumer: &mut C) -> Result<(), C::Error>
428 where
429 C: BulkConsumer<Item = u8> + ?Sized,
430 N: Encodable,
431 S: Encodable,
432 PD: Encodable,
433 {
434 consumer.consume_encoded(self.wdm_namespace_id()).await?;
435 consumer.consume_encoded(self.wdm_subspace_id()).await?;
436 consumer.consume_encoded(self.wdm_path()).await?;
437 cu64_encode_standalone(u64::from(self.wdm_timestamp()), consumer).await?;
438 cu64_encode_standalone(self.wdm_payload_length(), consumer).await?;
439 consumer.consume_encoded(self.wdm_payload_digest()).await?;
440 Ok(())
441 }
442
443 /// Computes the length of the encoding of `self` according to the [encode_entry](https://willowprotocol.org/specs/encodings/index.html#encode_entry) encoding function.
444 fn wdm_length_of_entry_encoding(&self) -> usize
445 where
446 N: EncodableKnownLength,
447 S: EncodableKnownLength,
448 PD: EncodableKnownLength,
449 {
450 self.wdm_namespace_id().len_of_encoding()
451 + self.wdm_subspace_id().len_of_encoding()
452 + self.wdm_path().len_of_encoding()
453 + 1
454 + cu64_len_of_encoding(8, u64::from(self.wdm_timestamp()))
455 + 1
456 + cu64_len_of_encoding(8, self.wdm_payload_length())
457 + self.wdm_payload_digest().len_of_encoding()
458 }
459}
460
461impl<const MCL: usize, const MCC: usize, const MPL: usize, N, S, PD, E>
462 EntrylikeExt<MCL, MCC, MPL, N, S, PD> for E
463where
464 E: Entrylike<MCL, MCC, MPL, N, S, PD>,
465{
466}