p2panda_rs/document/
document_view_id.rs

1// SPDX-License-Identifier: AGPL-3.0-or-later
2
3use std::convert::TryFrom;
4use std::fmt::{self, Display, Write};
5use std::hash::Hash as StdHash;
6use std::slice::Iter;
7use std::str::FromStr;
8
9use serde::de::Visitor;
10use serde::{Deserialize, Deserializer, Serialize};
11
12use crate::document::error::DocumentViewIdError;
13use crate::hash::{Hash, HashId};
14use crate::operation::error::OperationIdError;
15use crate::operation::OperationId;
16use crate::{Human, Validate};
17
18/// The identifier of a document view.
19///
20/// Contains the operation ids of the document graph tips, which is all the information we need
21/// to reliably reconstruct a specific version of a document.
22///
23/// Document view ids are considered equal if they contain the same set of operation ids,
24/// independent of their order. Serialised document view ids always contain sorted operation ids
25/// and deserialisation of a value will fail if this does not hold. This follows p2panda's
26/// requirement that all serialised arrays must be sorted and leads to deterministic serialisation.
27///
28/// ```text
29/// The document with the following operation graph has the id "2fa.." and six different document
30/// view ids, meaning that this document can be represented in six versions:
31///
32/// 1. ["2fa"]
33/// 2. ["de8"]
34/// 3. ["89c"]
35/// 4. ["eff"]
36/// 5. ["de8", "eff"]
37/// 6. ["89c", "eff"]
38///
39/// [CREATE] (Hash: "2fa..") <-- [UPDATE] (Hash: "de8..") <-- [UPDATE] (Hash: "89c..")
40///                         \
41///                          \__ [UPDATE] (Hash: "eff..")
42/// ```
43#[derive(Clone, Debug, Ord, PartialOrd, Eq, PartialEq, StdHash, Serialize)]
44pub struct DocumentViewId(Vec<OperationId>);
45
46impl DocumentViewId {
47    /// Create a new document view id.
48    ///
49    /// The given operation ids will automatically be sorted and de-duplicated.
50    pub fn new(graph_tips: &[OperationId]) -> Self {
51        let mut graph_tips = graph_tips.to_owned();
52
53        // Make sure all operations are sorted
54        graph_tips.sort();
55
56        // Make sure all operations are de-duplicated
57        graph_tips.dedup();
58
59        Self(graph_tips)
60    }
61
62    /// Create a new document view id from an untrusted source.
63    ///
64    /// This does _not_ automatically sort and de-duplicate the given operation ids but validates
65    /// them instead and returns an error if invalid.
66    ///
67    /// Use this method internally to ensure that document view ids from untrusted sources are
68    /// checked.
69    pub(crate) fn from_untrusted(
70        graph_tips: Vec<OperationId>,
71    ) -> Result<Self, DocumentViewIdError> {
72        // Create document view id with potentially invalid data
73        let document_view_id = Self(graph_tips);
74
75        // Make sure its sorted and does not contain any duplicates (#OP3)
76        document_view_id.validate()?;
77
78        Ok(document_view_id)
79    }
80
81    /// Get the operation ids of this view id.
82    pub fn graph_tips(&self) -> &[OperationId] {
83        self.0.as_slice()
84    }
85
86    /// Get the operation ids of this view id.
87    pub fn iter(&self) -> Iter<OperationId> {
88        self.graph_tips().iter()
89    }
90}
91
92impl Validate for DocumentViewId {
93    type Error = DocumentViewIdError;
94
95    /// Checks document view id against canonic format.
96    ///
97    /// This verifies if the document view id is not empty and constituting operation ids are
98    /// sorted, do not contain any duplicates and represent valid hashes (#OP3).
99    fn validate(&self) -> Result<(), Self::Error> {
100        // Check if at least one operation id is given
101        if self.0.is_empty() {
102            return Err(DocumentViewIdError::ZeroOperationIds);
103        };
104
105        let mut prev_operation_id: Option<&OperationId> = None;
106
107        for operation_id in &self.0 {
108            // Check if the given operation ids are correctly formatted
109            operation_id.validate()?;
110
111            // Check if it is sorted, this indirectly also checks against duplicates
112            if let Some(prev) = prev_operation_id {
113                if prev >= operation_id {
114                    return Err(DocumentViewIdError::UnsortedOperationIds);
115                }
116            }
117
118            prev_operation_id = Some(operation_id);
119        }
120
121        Ok(())
122    }
123}
124
125impl Display for DocumentViewId {
126    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
127        for (i, operation_id) in self.iter().enumerate() {
128            let separator = if i == 0 { "" } else { "_" };
129            let _ = write!(f, "{}{}", &separator, operation_id.as_str());
130        }
131
132        Ok(())
133    }
134}
135
136impl Human for DocumentViewId {
137    fn display(&self) -> String {
138        let mut result = String::new();
139        let offset = yasmf_hash::MAX_YAMF_HASH_SIZE * 2 - 6;
140
141        for (i, operation_id) in self.iter().enumerate() {
142            let separator = if i == 0 { "" } else { "_" };
143            write!(result, "{}{}", &separator, &operation_id.as_str()[offset..]).unwrap();
144        }
145
146        result
147    }
148}
149
150impl<'de> Deserialize<'de> for DocumentViewId {
151    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
152    where
153        D: Deserializer<'de>,
154    {
155        struct DocumentViewIdVisitor;
156
157        impl<'de> Visitor<'de> for DocumentViewIdVisitor {
158            type Value = DocumentViewId;
159
160            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
161                formatter.write_str("document view id as array or in string representation")
162            }
163
164            /// Document view ids can be represented as strings, using underscores as separators
165            /// between the operation ids. This is especially useful when using arrays is not
166            /// possible or unergonomic (for example in GraphQL)
167            fn visit_str<E>(self, value: &str) -> Result<Self::Value, E>
168            where
169                E: serde::de::Error,
170            {
171                DocumentViewId::from_str(value).map_err(serde::de::Error::custom)
172            }
173
174            /// Document view ids can be represented as arrays of operation ids.
175            fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
176            where
177                A: serde::de::SeqAccess<'de>,
178            {
179                let mut operation_ids = Vec::new();
180
181                while let Some(operation_id) = seq.next_element::<OperationId>()? {
182                    operation_ids.push(operation_id);
183                }
184
185                let view_id = DocumentViewId::from_untrusted(operation_ids)
186                    .map_err(serde::de::Error::custom)?;
187
188                Ok(view_id)
189            }
190        }
191
192        let view_id = deserializer.deserialize_any(DocumentViewIdVisitor)?;
193
194        Ok(view_id)
195    }
196}
197
198impl TryFrom<&[String]> for DocumentViewId {
199    type Error = DocumentViewIdError;
200
201    fn try_from(str_list: &[String]) -> Result<Self, Self::Error> {
202        let operation_ids: Result<Vec<OperationId>, OperationIdError> = str_list
203            .iter()
204            .map(|operation_id_str| operation_id_str.parse::<OperationId>())
205            .collect();
206
207        Self::from_untrusted(operation_ids?)
208    }
209}
210
211impl<T: HashId> TryFrom<&[T]> for DocumentViewId {
212    type Error = DocumentViewIdError;
213
214    fn try_from(str_list: &[T]) -> Result<Self, Self::Error> {
215        let operation_ids: Vec<OperationId> = str_list
216            .iter()
217            .map(|hash_id| hash_id.as_hash().clone().into())
218            .collect();
219
220        Self::from_untrusted(operation_ids)
221    }
222}
223
224impl TryFrom<&[Hash]> for DocumentViewId {
225    type Error = DocumentViewIdError;
226
227    fn try_from(str_list: &[Hash]) -> Result<Self, Self::Error> {
228        let operation_ids: Vec<OperationId> =
229            str_list.iter().map(|hash| hash.clone().into()).collect();
230
231        Self::from_untrusted(operation_ids)
232    }
233}
234
235impl From<DocumentViewId> for Vec<Hash> {
236    fn from(value: DocumentViewId) -> Self {
237        value.iter().map(HashId::as_hash).cloned().collect()
238    }
239}
240
241/// Convenience method converting a single [`OperationId`] into a document view id.
242///
243/// Converts an `OperationId` instance into a `DocumentViewId`, assuming that this document view
244/// only consists of one graph tip hash.
245impl From<OperationId> for DocumentViewId {
246    fn from(operation_id: OperationId) -> Self {
247        Self(vec![operation_id])
248    }
249}
250
251/// Convenience method converting a single hash into a document view id.
252///
253/// Converts a `Hash` instance into a `DocumentViewId`, assuming that this document view only
254/// consists of one graph tip hash.
255impl From<Hash> for DocumentViewId {
256    fn from(hash: Hash) -> Self {
257        Self(vec![hash.into()])
258    }
259}
260
261/// Convenience method converting a hash string into a document view id.
262///
263/// Converts a string formatted document view id into a `DocumentViewId`. Expects multi-hash ids to
264/// be hash strings separated by an `_` character.
265impl FromStr for DocumentViewId {
266    type Err = DocumentViewIdError;
267
268    fn from_str(s: &str) -> Result<Self, Self::Err> {
269        let mut operations: Vec<OperationId> = Vec::new();
270
271        s.split('_')
272            .try_for_each::<_, Result<(), Self::Err>>(|hash_str| {
273                let operation_id = OperationId::from_str(hash_str)?;
274                operations.push(operation_id);
275                Ok(())
276            })?;
277
278        Self::from_untrusted(operations)
279    }
280}
281
282#[cfg(test)]
283mod tests {
284    use std::collections::hash_map::DefaultHasher;
285    use std::hash::{Hash as StdHash, Hasher};
286    use std::str::FromStr;
287
288    use rstest::rstest;
289    use serde::{Deserialize, Serialize};
290
291    use crate::hash::Hash;
292    use crate::operation::OperationId;
293    use crate::serde::{hex_string_to_bytes, serialize_from};
294    use crate::test_utils::constants::HASH;
295    use crate::test_utils::fixtures::random_hash;
296    use crate::test_utils::fixtures::{document_view_id, random_operation_id};
297    use crate::{Human, Validate};
298
299    use super::DocumentViewId;
300
301    #[rstest]
302    fn constructor_converts_to_canonic_format() {
303        let operation_id_1: OperationId =
304            "00201413ae916e6745ab715c1f5ab49c47d6773c3c0febd970ecf1039beed203b472"
305                .parse()
306                .unwrap();
307        let operation_id_2: OperationId =
308            "0020266fe901ea7d3efa983f12d145089d29480064b0da7393a8c0779af7488c7f0d"
309                .parse()
310                .unwrap();
311        let operation_id_3: OperationId =
312            "0020387b96cfdc7ac155eff0a9941400dee4a21e7cf18dcccefbf0a46a7c0138bbf5"
313                .parse()
314                .unwrap();
315        let operation_id_4: OperationId =
316            "002047e8d17a2edb41621beec8c710ee71a1b2ea81d356f05cd466526b269a7b2493"
317                .parse()
318                .unwrap();
319
320        // Everything is in order
321        let document_view_id_1 = DocumentViewId::new(&[
322            operation_id_1.clone(),
323            operation_id_2.clone(),
324            operation_id_3.clone(),
325            operation_id_4.clone(),
326        ]);
327        assert!(document_view_id_1.validate().is_ok());
328
329        // Unordered operations will be sorted and deduplicated
330        let document_view_id_2 = DocumentViewId::new(&[
331            operation_id_3.clone(),
332            operation_id_3.clone(),
333            operation_id_2.clone(),
334            operation_id_4.clone(),
335            operation_id_1.clone(),
336            operation_id_4.clone(),
337        ]);
338        assert!(document_view_id_2.validate().is_ok());
339        assert_eq!(document_view_id_2.graph_tips().len(), 4);
340
341        assert!(DocumentViewId::from_untrusted(vec![
342            operation_id_3.clone(),
343            operation_id_3,
344            operation_id_2,
345            operation_id_4.clone(),
346            operation_id_1,
347            operation_id_4,
348        ])
349        .is_err());
350    }
351
352    #[rstest]
353    fn conversion(#[from(random_hash)] hash: Hash) {
354        // Converts a string to `DocumentViewId`
355        let hash_str = "0020d3235c8fe6f58608200851b83cd8482808eb81e4c6b4b17805bba57da9f16e79";
356        let document_id: DocumentViewId = hash_str.parse().unwrap();
357        assert_eq!(
358            document_id,
359            DocumentViewId::new(&[hash_str.parse::<OperationId>().unwrap()])
360        );
361
362        // Converts a `Hash` to `DocumentViewId`
363        let document_id: DocumentViewId = hash.clone().into();
364        assert_eq!(document_id, DocumentViewId::new(&[hash.clone().into()]));
365
366        // Converts an `OperationId` to `DocumentViewId`
367        let document_id: DocumentViewId = OperationId::new(&hash).into();
368        assert_eq!(document_id, DocumentViewId::new(&[hash.into()]));
369
370        // Fails when string is not a hash
371        assert!("This is not a hash".parse::<DocumentViewId>().is_err());
372    }
373
374    #[rstest]
375    fn iterates(document_view_id: DocumentViewId) {
376        for hash in document_view_id.graph_tips() {
377            assert!(hash.validate().is_ok());
378        }
379    }
380
381    #[test]
382    fn string_representation() {
383        let document_view_id = HASH.parse::<DocumentViewId>().unwrap();
384
385        assert_eq!(
386            document_view_id.to_string(),
387            "0020b177ec1bf26dfb3b7010d473e6d44713b29b765b99c6e60ecbfae742de496543"
388        );
389
390        assert_eq!(
391            format!("{}", document_view_id),
392            "0020b177ec1bf26dfb3b7010d473e6d44713b29b765b99c6e60ecbfae742de496543"
393        );
394
395        let operation_1 = "0020b177ec1bf26dfb3b7010d473e6d44713b29b765b99c6e60ecbfae742de496543"
396            .parse::<OperationId>()
397            .unwrap();
398        let operation_2 = "0020d3235c8fe6f58608200851b83cd8482808eb81e4c6b4b17805bba57da9f16e79"
399            .parse::<OperationId>()
400            .unwrap();
401
402        let document_view_id = DocumentViewId::new(&[operation_1, operation_2]);
403        assert_eq!(document_view_id.to_string(), "0020b177ec1bf26dfb3b7010d473e6d44713b29b765b99c6e60ecbfae742de496543_0020d3235c8fe6f58608200851b83cd8482808eb81e4c6b4b17805bba57da9f16e79");
404        assert_eq!("0020b177ec1bf26dfb3b7010d473e6d44713b29b765b99c6e60ecbfae742de496543_0020d3235c8fe6f58608200851b83cd8482808eb81e4c6b4b17805bba57da9f16e79".parse::<DocumentViewId>().unwrap(), document_view_id);
405    }
406
407    #[test]
408    fn short_representation() {
409        let operation_1 = "0020b177ec1bf26dfb3b7010d473e6d44713b29b765b99c6e60ecbfae742de496543"
410            .parse::<OperationId>()
411            .unwrap();
412        let operation_2 = "0020d3235c8fe6f58608200851b83cd8482808eb81e4c6b4b17805bba57da9f16e79"
413            .parse::<OperationId>()
414            .unwrap();
415
416        let view_id_unmerged = DocumentViewId::new(&[operation_1, operation_2]);
417        assert_eq!(view_id_unmerged.display(), "496543_f16e79");
418    }
419
420    #[rstest]
421    fn equality(
422        #[from(random_operation_id)] operation_id_1: OperationId,
423        #[from(random_operation_id)] operation_id_2: OperationId,
424    ) {
425        let view_id_1 = DocumentViewId::new(&[operation_id_1.clone(), operation_id_2.clone()]);
426        let view_id_2 = DocumentViewId::new(&[operation_id_2, operation_id_1]);
427        assert_eq!(view_id_1, view_id_2);
428    }
429
430    #[rstest]
431    fn hash_equality(
432        #[from(random_operation_id)] operation_id_1: OperationId,
433        #[from(random_operation_id)] operation_id_2: OperationId,
434    ) {
435        let mut hasher_1 = DefaultHasher::default();
436        let mut hasher_2 = DefaultHasher::default();
437        let view_id_1 = DocumentViewId::new(&[operation_id_1.clone(), operation_id_2.clone()]);
438        let view_id_2 = DocumentViewId::new(&[operation_id_2, operation_id_1]);
439        view_id_1.hash(&mut hasher_1);
440        view_id_2.hash(&mut hasher_2);
441        assert_eq!(hasher_1.finish(), hasher_2.finish());
442    }
443
444    #[rstest]
445    fn deserialize_unsorted_view_id(
446        #[from(random_operation_id)] operation_id_1: OperationId,
447        #[from(random_operation_id)] operation_id_2: OperationId,
448    ) {
449        // Unsorted operation ids in document view id array:
450        let unsorted_hashes = [
451            hex_string_to_bytes(
452                "0020c13cdc58dfc6f4ebd32992ff089db79980363144bdb2743693a019636fa72ec8",
453            ),
454            hex_string_to_bytes(
455                "00202dce4b32cd35d61cf54634b93a526df333c5ed3d93230c2f026f8d1ecabc0cd7",
456            ),
457        ];
458        let mut cbor_bytes = Vec::new();
459        ciborium::ser::into_writer(&unsorted_hashes, &mut cbor_bytes).unwrap();
460
461        // Construct document view id by deserialising CBOR data
462        let result: Result<DocumentViewId, ciborium::de::Error<std::io::Error>> =
463            ciborium::de::from_reader(&cbor_bytes[..]);
464
465        let expected_result = ciborium::de::Error::<std::io::Error>::Semantic(
466            None,
467            "expected sorted operation ids in document view id".to_string(),
468        );
469
470        assert_eq!(result.unwrap_err().to_string(), expected_result.to_string());
471
472        // However, unsorted values in an id are sorted during serialisation
473        let mut reversed_ids = vec![operation_id_1, operation_id_2];
474        reversed_ids.sort();
475        reversed_ids.reverse();
476        let view_id_unsorted = DocumentViewId::new(&reversed_ids);
477
478        let mut cbor_bytes = Vec::new();
479        ciborium::ser::into_writer(&view_id_unsorted, &mut cbor_bytes).unwrap();
480
481        let result: Result<DocumentViewId, ciborium::de::Error<std::io::Error>> =
482            ciborium::de::from_reader(&cbor_bytes[..]);
483        assert!(result.is_ok());
484        assert_eq!(result.unwrap(), view_id_unsorted);
485    }
486
487    #[test]
488    fn deserialize_invalid_view_id() {
489        // The second operation id is missing 4 characters
490        let invalid_hashes = [
491            hex_string_to_bytes(
492                "0020c13cdc58dfc6f4ebd32992ff089db79980363144bdb2743693a019636fa72ec8",
493            ),
494            hex_string_to_bytes("2dce4b32cd35d61cf54634b93a526df333c5ed3d93230c2f026f8d1ecabc0cd7"),
495        ];
496        let mut cbor_bytes = Vec::new();
497        ciborium::ser::into_writer(&invalid_hashes, &mut cbor_bytes).unwrap();
498        let invalid_id_encoded = hex::encode(cbor_bytes);
499
500        // Construct document view id by deserialising CBOR data
501        let result: Result<DocumentViewId, ciborium::de::Error<std::io::Error>> =
502            ciborium::de::from_reader(&hex::decode(invalid_id_encoded).unwrap()[..]);
503
504        let expected_result = ciborium::de::Error::<std::io::Error>::Semantic(
505            None,
506            "invalid hash length 32 bytes, expected 34 bytes".to_string(),
507        );
508
509        assert_eq!(result.unwrap_err().to_string(), expected_result.to_string());
510    }
511
512    #[test]
513    fn deserialize_human_readable() {
514        let hash_str = "0020cfb0fa37f36d082faad3886a9ffbcc2813b7afe90f0609a556d425f1a76ec805_0020cfb0fa37f36d082faad3886a9ffbcc2813b7afe90f0609a556d425f1a76ec808";
515
516        #[derive(Deserialize, Serialize, Debug, PartialEq)]
517        struct Test {
518            document_view_id: DocumentViewId,
519        }
520
521        // Deserialize from human-readable (hex-encoded) JSON string
522        let json = format!(
523            r#"
524            {{
525                "document_view_id": "{hash_str}"
526            }}
527        "#
528        );
529
530        let result: Test = serde_json::from_str(&json).unwrap();
531        assert_eq!(
532            Test {
533                document_view_id: DocumentViewId::from_str(hash_str).unwrap(),
534            },
535            result
536        );
537
538        // Serialize into non human-readable CBOR format (operation ids are encoded as bytes)
539        let bytes = serialize_from(result);
540        assert_eq!(
541            bytes,
542            [
543                // {"document_view_id":
544                // [h'0020CFB0FA37F36D082FAAD3886A9FFBCC2813B7AFE90F0609A556D425F1A76EC805',
545                // h'0020CFB0FA37F36D082FAAD3886A9FFBCC2813B7AFE90F0609A556D425F1A76EC808']}
546                161, 112, 100, 111, 99, 117, 109, 101, 110, 116, 95, 118, 105, 101, 119, 95, 105,
547                100, 130, 88, 34, 0, 32, 207, 176, 250, 55, 243, 109, 8, 47, 170, 211, 136, 106,
548                159, 251, 204, 40, 19, 183, 175, 233, 15, 6, 9, 165, 86, 212, 37, 241, 167, 110,
549                200, 5, 88, 34, 0, 32, 207, 176, 250, 55, 243, 109, 8, 47, 170, 211, 136, 106, 159,
550                251, 204, 40, 19, 183, 175, 233, 15, 6, 9, 165, 86, 212, 37, 241, 167, 110, 200, 8
551            ]
552        )
553    }
554}
p2panda_rs/document/document_view_id.rs

p2panda_rs/document/
document_view_id.rs
