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