loro_common/
lib.rs

1use std::{fmt::Display, io::Write};
2
3use arbitrary::Arbitrary;
4use enum_as_inner::EnumAsInner;
5
6use nonmax::{NonMaxI32, NonMaxU32};
7use serde::{Deserialize, Serialize};
8
9mod error;
10mod id;
11mod internal_string;
12mod macros;
13mod span;
14mod value;
15
16pub use error::{LoroEncodeError, LoroError, LoroResult, LoroTreeError};
17#[doc(hidden)]
18pub use fxhash::FxHashMap;
19pub use internal_string::InternalString;
20pub use span::*;
21pub use value::{
22    to_value, LoroBinaryValue, LoroListValue, LoroMapValue, LoroStringValue, LoroValue,
23};
24
25/// Unique id for each peer. It's a random u64 by default.
26pub type PeerID = u64;
27/// If it's the nth Op of a peer, the counter will be n.
28pub type Counter = i32;
29/// It's the [Lamport clock](https://en.wikipedia.org/wiki/Lamport_timestamp)
30pub type Lamport = u32;
31
32/// It's the unique ID of an Op represented by [PeerID] and [Counter].
33#[derive(PartialEq, Eq, Hash, Clone, Copy, Serialize, Deserialize)]
34pub struct ID {
35    pub peer: PeerID,
36    pub counter: Counter,
37}
38
39impl ID {
40    pub fn to_bytes(&self) -> [u8; 12] {
41        let mut bytes = [0; 12];
42        bytes[..8].copy_from_slice(&self.peer.to_be_bytes());
43        bytes[8..].copy_from_slice(&self.counter.to_be_bytes());
44        bytes
45    }
46
47    pub fn from_bytes(bytes: &[u8]) -> Self {
48        if bytes.len() != 12 {
49            panic!(
50                "Invalid ID bytes. Expected 12 bytes but got {} bytes",
51                bytes.len()
52            );
53        }
54
55        Self {
56            peer: u64::from_be_bytes(bytes[..8].try_into().unwrap()),
57            counter: i32::from_be_bytes(bytes[8..].try_into().unwrap()),
58        }
59    }
60}
61
62/// It's the unique ID of an Op represented by [PeerID] and [Counter].
63#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
64pub struct CompactId {
65    pub peer: PeerID,
66    pub counter: NonMaxI32,
67}
68
69/// Return whether the given name is a valid root container name.
70pub fn check_root_container_name(name: &str) -> bool {
71    !name.is_empty() && name.char_indices().all(|(_, x)| x != '/' && x != '\0')
72}
73
74impl CompactId {
75    pub fn new(peer: PeerID, counter: Counter) -> Self {
76        Self {
77            peer,
78            counter: NonMaxI32::new(counter).unwrap(),
79        }
80    }
81
82    pub fn to_id(&self) -> ID {
83        ID {
84            peer: self.peer,
85            counter: self.counter.get(),
86        }
87    }
88
89    pub fn inc(&self, start: i32) -> CompactId {
90        Self {
91            peer: self.peer,
92            counter: NonMaxI32::new(start + self.counter.get()).unwrap(),
93        }
94    }
95}
96
97impl TryFrom<ID> for CompactId {
98    type Error = ID;
99
100    fn try_from(id: ID) -> Result<Self, ID> {
101        if id.counter == i32::MAX {
102            return Err(id);
103        }
104
105        Ok(Self::new(id.peer, id.counter))
106    }
107}
108
109/// It's the unique ID of an Op represented by [PeerID] and [Lamport] clock.
110/// It's used to define the total order of Ops.
111#[derive(PartialEq, Eq, Hash, Clone, Copy, Serialize, Deserialize, PartialOrd, Ord)]
112pub struct IdLp {
113    pub lamport: Lamport,
114    pub peer: PeerID,
115}
116
117impl IdLp {
118    pub fn compact(self) -> CompactIdLp {
119        CompactIdLp::new(self.peer, self.lamport)
120    }
121}
122
123/// It's the unique ID of an Op represented by [PeerID] and [Counter].
124#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
125pub struct CompactIdLp {
126    pub peer: PeerID,
127    pub lamport: NonMaxU32,
128}
129
130impl CompactIdLp {
131    pub fn new(peer: PeerID, lamport: Lamport) -> Self {
132        Self {
133            peer,
134            lamport: NonMaxU32::new(lamport).unwrap(),
135        }
136    }
137
138    pub fn to_id(&self) -> IdLp {
139        IdLp {
140            peer: self.peer,
141            lamport: self.lamport.get(),
142        }
143    }
144}
145
146impl TryFrom<IdLp> for CompactIdLp {
147    type Error = IdLp;
148
149    fn try_from(id: IdLp) -> Result<Self, IdLp> {
150        if id.lamport == u32::MAX {
151            return Err(id);
152        }
153
154        Ok(Self::new(id.peer, id.lamport))
155    }
156}
157
158/// It's the unique ID of an Op represented by [PeerID], [Lamport] clock and [Counter].
159#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy, Serialize, Deserialize)]
160pub struct IdFull {
161    pub peer: PeerID,
162    pub lamport: Lamport,
163    pub counter: Counter,
164}
165
166/// [ContainerID] includes the Op's [ID] and the type. So it's impossible to have
167/// the same [ContainerID] with conflict [ContainerType].
168///
169/// This structure is really cheap to clone.
170///
171/// String representation:
172///
173/// - Root Container: `/<name>:<type>`
174/// - Normal Container: `<counter>@<client>:<type>`
175///
176/// Note: It will be encoded into binary format, so the order of its fields should not be changed.
177#[derive(Hash, PartialEq, Eq, Clone, Serialize, Deserialize, EnumAsInner)]
178pub enum ContainerID {
179    /// Root container does not need an op to create. It can be created implicitly.
180    Root {
181        name: InternalString,
182        container_type: ContainerType,
183    },
184    Normal {
185        peer: PeerID,
186        counter: Counter,
187        container_type: ContainerType,
188    },
189}
190
191impl ContainerID {
192    pub fn encode<W: Write>(&self, writer: &mut W) -> Result<(), std::io::Error> {
193        match self {
194            Self::Root {
195                name,
196                container_type,
197            } => {
198                let first_byte = container_type.to_u8() | 0b10000000;
199                writer.write_all(&[first_byte])?;
200                leb128::write::unsigned(writer, name.len() as u64)?;
201                writer.write_all(name.as_bytes())?;
202            }
203            Self::Normal {
204                peer,
205                counter,
206                container_type,
207            } => {
208                let first_byte = container_type.to_u8();
209                writer.write_all(&[first_byte])?;
210                writer.write_all(&peer.to_le_bytes())?;
211                writer.write_all(&counter.to_le_bytes())?;
212            }
213        }
214
215        Ok(())
216    }
217
218    pub fn to_bytes(&self) -> Vec<u8> {
219        // normal need 13 bytes
220        let mut bytes = Vec::with_capacity(13);
221        self.encode(&mut bytes).unwrap();
222        bytes
223    }
224
225    pub fn from_bytes(bytes: &[u8]) -> Self {
226        let first_byte = bytes[0];
227        let container_type = ContainerType::try_from_u8(first_byte & 0b01111111).unwrap();
228        let is_root = (first_byte & 0b10000000) != 0;
229
230        let mut reader = &bytes[1..];
231        match is_root {
232            true => {
233                let name_len = leb128::read::unsigned(&mut reader).unwrap();
234                let name = InternalString::from(
235                    std::str::from_utf8(&reader[..name_len as usize]).unwrap(),
236                );
237                Self::Root {
238                    name,
239                    container_type,
240                }
241            }
242            false => {
243                let peer = PeerID::from_le_bytes(reader[..8].try_into().unwrap());
244                let counter = i32::from_le_bytes(reader[8..12].try_into().unwrap());
245                Self::Normal {
246                    peer,
247                    counter,
248                    container_type,
249                }
250            }
251        }
252    }
253
254    const LORO_CONTAINER_ID_PREFIX: &str = "🦜:";
255    pub fn to_loro_value_string(&self) -> String {
256        format!("{}{}", Self::LORO_CONTAINER_ID_PREFIX, self)
257    }
258
259    pub fn try_from_loro_value_string(s: &str) -> Option<Self> {
260        if let Some(s) = s.strip_prefix(Self::LORO_CONTAINER_ID_PREFIX) {
261            Self::try_from(s).ok()
262        } else {
263            None
264        }
265    }
266}
267
268impl std::fmt::Debug for ContainerID {
269    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
270        match self {
271            Self::Root {
272                name,
273                container_type,
274            } => {
275                write!(f, "Root(\"{}\" {:?})", &name, container_type)
276            }
277            Self::Normal {
278                peer,
279                counter,
280                container_type,
281            } => {
282                write!(f, "Normal({:?} {}@{})", container_type, counter, peer,)
283            }
284        }
285    }
286}
287
288// TODO: add non_exhausted
289// Note: It will be encoded into binary format, so the order of its fields should not be changed.
290#[derive(
291    Arbitrary, Debug, PartialEq, Eq, Hash, Clone, Copy, PartialOrd, Ord, Serialize, Deserialize,
292)]
293pub enum ContainerType {
294    Text,
295    Map,
296    List,
297    MovableList,
298    Tree,
299    #[cfg(feature = "counter")]
300    Counter,
301    Unknown(u8),
302}
303
304impl ContainerType {
305    #[cfg(feature = "counter")]
306    pub const ALL_TYPES: [ContainerType; 6] = [
307        ContainerType::Map,
308        ContainerType::List,
309        ContainerType::Text,
310        ContainerType::Tree,
311        ContainerType::MovableList,
312        ContainerType::Counter,
313    ];
314    #[cfg(not(feature = "counter"))]
315    pub const ALL_TYPES: [ContainerType; 5] = [
316        ContainerType::Map,
317        ContainerType::List,
318        ContainerType::Text,
319        ContainerType::Tree,
320        ContainerType::MovableList,
321    ];
322
323    pub fn default_value(&self) -> LoroValue {
324        match self {
325            ContainerType::Map => LoroValue::Map(Default::default()),
326            ContainerType::List => LoroValue::List(Default::default()),
327            ContainerType::Text => LoroValue::String(Default::default()),
328            ContainerType::Tree => LoroValue::List(Default::default()),
329            ContainerType::MovableList => LoroValue::List(Default::default()),
330            #[cfg(feature = "counter")]
331            ContainerType::Counter => LoroValue::Double(0.),
332            ContainerType::Unknown(_) => unreachable!(),
333        }
334    }
335
336    pub fn to_u8(self) -> u8 {
337        match self {
338            ContainerType::Map => 0,
339            ContainerType::List => 1,
340            ContainerType::Text => 2,
341            ContainerType::Tree => 3,
342            ContainerType::MovableList => 4,
343            #[cfg(feature = "counter")]
344            ContainerType::Counter => 5,
345            ContainerType::Unknown(k) => k,
346        }
347    }
348
349    pub fn try_from_u8(v: u8) -> LoroResult<Self> {
350        match v {
351            0 => Ok(ContainerType::Map),
352            1 => Ok(ContainerType::List),
353            2 => Ok(ContainerType::Text),
354            3 => Ok(ContainerType::Tree),
355            4 => Ok(ContainerType::MovableList),
356            #[cfg(feature = "counter")]
357            5 => Ok(ContainerType::Counter),
358            x => Ok(ContainerType::Unknown(x)),
359        }
360    }
361}
362
363pub type IdSpanVector = fxhash::FxHashMap<PeerID, CounterSpan>;
364
365mod container {
366    use super::*;
367
368    impl Display for ContainerType {
369        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
370            f.write_str(match self {
371                ContainerType::Map => "Map",
372                ContainerType::List => "List",
373                ContainerType::MovableList => "MovableList",
374                ContainerType::Text => "Text",
375                ContainerType::Tree => "Tree",
376                #[cfg(feature = "counter")]
377                ContainerType::Counter => "Counter",
378                ContainerType::Unknown(k) => return f.write_fmt(format_args!("Unknown({})", k)),
379            })
380        }
381    }
382
383    impl Display for ContainerID {
384        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
385            match self {
386                ContainerID::Root {
387                    name,
388                    container_type,
389                } => f.write_fmt(format_args!("cid:root-{}:{}", name, container_type))?,
390                ContainerID::Normal {
391                    peer,
392                    counter,
393                    container_type,
394                } => f.write_fmt(format_args!(
395                    "cid:{}:{}",
396                    ID::new(*peer, *counter),
397                    container_type
398                ))?,
399            };
400            Ok(())
401        }
402    }
403
404    impl TryFrom<&str> for ContainerID {
405        type Error = ();
406
407        fn try_from(mut s: &str) -> Result<Self, Self::Error> {
408            if !s.starts_with("cid:") {
409                return Err(());
410            }
411
412            s = &s[4..];
413            if s.starts_with("root-") {
414                // root container
415                s = &s[5..];
416                let split = s.rfind(':').ok_or(())?;
417                if split == 0 {
418                    return Err(());
419                }
420                let kind = ContainerType::try_from(&s[split + 1..]).map_err(|_| ())?;
421                let name = &s[..split];
422                Ok(ContainerID::Root {
423                    name: name.into(),
424                    container_type: kind,
425                })
426            } else {
427                let mut iter = s.split(':');
428                let id = iter.next().ok_or(())?;
429                let kind = iter.next().ok_or(())?;
430                if iter.next().is_some() {
431                    return Err(());
432                }
433
434                let id = ID::try_from(id).map_err(|_| ())?;
435                let kind = ContainerType::try_from(kind).map_err(|_| ())?;
436                Ok(ContainerID::Normal {
437                    peer: id.peer,
438                    counter: id.counter,
439                    container_type: kind,
440                })
441            }
442        }
443    }
444
445    impl ContainerID {
446        #[inline]
447        pub fn new_normal(id: ID, container_type: ContainerType) -> Self {
448            ContainerID::Normal {
449                peer: id.peer,
450                counter: id.counter,
451                container_type,
452            }
453        }
454
455        #[inline]
456        pub fn new_root(name: &str, container_type: ContainerType) -> Self {
457            if !check_root_container_name(name) {
458                panic!(
459                    "Invalid root container name, it should not be empty or contain '/' or '\\0'"
460                );
461            } else {
462                ContainerID::Root {
463                    name: name.into(),
464                    container_type,
465                }
466            }
467        }
468
469        #[inline]
470        pub fn name(&self) -> &InternalString {
471            match self {
472                ContainerID::Root { name, .. } => name,
473                ContainerID::Normal { .. } => unreachable!(),
474            }
475        }
476
477        #[inline]
478        pub fn container_type(&self) -> ContainerType {
479            match self {
480                ContainerID::Root { container_type, .. } => *container_type,
481                ContainerID::Normal { container_type, .. } => *container_type,
482            }
483        }
484
485        pub fn is_unknown(&self) -> bool {
486            matches!(self.container_type(), ContainerType::Unknown(_))
487        }
488    }
489
490    impl TryFrom<&str> for ContainerType {
491        type Error = LoroError;
492
493        fn try_from(value: &str) -> Result<Self, Self::Error> {
494            match value {
495                "Map" | "map" => Ok(ContainerType::Map),
496                "List" | "list" => Ok(ContainerType::List),
497                "Text" | "text" => Ok(ContainerType::Text),
498                "Tree" | "tree" => Ok(ContainerType::Tree),
499                "MovableList" | "movableList" => Ok(ContainerType::MovableList),
500                #[cfg(feature = "counter")]
501                "Counter" | "counter" => Ok(ContainerType::Counter),
502                a => {
503                    if a.ends_with(')') {
504                        let start = a.find('(').ok_or_else(|| {
505                            LoroError::DecodeError(
506                                format!("Invalid container type string \"{}\"", value).into(),
507                            )
508                        })?;
509                        let k = a[start+1..a.len() - 1].parse().map_err(|_| {
510                            LoroError::DecodeError(
511                    format!("Unknown container type \"{}\". The valid options are Map|List|Text|Tree|MovableList.", value).into(),
512                )
513                        })?;
514                        match ContainerType::try_from_u8(k) {
515                            Ok(k) => Ok(k),
516                            Err(_) => Ok(ContainerType::Unknown(k)),
517                        }
518                    } else {
519                        Err(LoroError::DecodeError(
520                    format!("Unknown container type \"{}\". The valid options are Map|List|Text|Tree|MovableList.", value).into(),
521                ))
522                    }
523                }
524            }
525        }
526    }
527}
528
529/// In movable tree, we use a specific [`TreeID`] to represent the root of **ALL** deleted tree node.
530///
531/// Deletion operation is equivalent to move target tree node to [`DELETED_TREE_ROOT`].
532pub const DELETED_TREE_ROOT: TreeID = TreeID {
533    peer: PeerID::MAX,
534    counter: Counter::MAX,
535};
536
537/// Each node of movable tree has a unique [`TreeID`] generated by Loro.
538///
539/// To further represent the metadata (a MapContainer) associated with each node,
540/// we also use [`TreeID`] as [`ID`] portion of [`ContainerID`].
541/// This not only allows for convenient association of metadata with each node,
542/// but also ensures the uniqueness of the MapContainer.
543///
544/// Special ID:
545/// - [`DELETED_TREE_ROOT`]: the root of all deleted nodes. To get it by [`TreeID::delete_root()`]
546#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
547
548pub struct TreeID {
549    pub peer: PeerID,
550    // TODO: can use a NonMax here
551    pub counter: Counter,
552}
553
554impl TreeID {
555    #[inline(always)]
556    pub fn new(peer: PeerID, counter: Counter) -> Self {
557        Self { peer, counter }
558    }
559
560    /// return [`DELETED_TREE_ROOT`]
561    pub const fn delete_root() -> Self {
562        DELETED_TREE_ROOT
563    }
564
565    /// return `true` if the `TreeID` is deleted root
566    pub fn is_deleted_root(&self) -> bool {
567        self == &DELETED_TREE_ROOT
568    }
569
570    pub fn from_id(id: ID) -> Self {
571        Self {
572            peer: id.peer,
573            counter: id.counter,
574        }
575    }
576
577    pub fn id(&self) -> ID {
578        ID {
579            peer: self.peer,
580            counter: self.counter,
581        }
582    }
583
584    pub fn associated_meta_container(&self) -> ContainerID {
585        ContainerID::new_normal(self.id(), ContainerType::Map)
586    }
587}
588
589impl Display for TreeID {
590    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
591        self.id().fmt(f)
592    }
593}
594
595impl TryFrom<&str> for TreeID {
596    type Error = LoroError;
597    fn try_from(value: &str) -> Result<Self, Self::Error> {
598        let id = ID::try_from(value)?;
599        Ok(TreeID {
600            peer: id.peer,
601            counter: id.counter,
602        })
603    }
604}
605
606#[cfg(feature = "wasm")]
607pub mod wasm {
608    use crate::{LoroError, TreeID};
609    use wasm_bindgen::JsValue;
610    impl From<TreeID> for JsValue {
611        fn from(value: TreeID) -> Self {
612            JsValue::from_str(&format!("{}", value.id()))
613        }
614    }
615
616    impl TryFrom<JsValue> for TreeID {
617        type Error = LoroError;
618        fn try_from(value: JsValue) -> Result<Self, Self::Error> {
619            let id = value.as_string().unwrap();
620            TreeID::try_from(id.as_str())
621        }
622    }
623}
624
625#[cfg(test)]
626mod test {
627    use crate::{ContainerID, ContainerType, ID};
628
629    #[test]
630    fn test_container_id_convert_to_and_from_str() {
631        let id = ContainerID::Root {
632            name: "name".into(),
633            container_type: crate::ContainerType::Map,
634        };
635        let id_str = id.to_string();
636        assert_eq!(id_str.as_str(), "cid:root-name:Map");
637        assert_eq!(ContainerID::try_from(id_str.as_str()).unwrap(), id);
638
639        let id = ContainerID::Normal {
640            counter: 10,
641            peer: 255,
642            container_type: crate::ContainerType::Map,
643        };
644        let id_str = id.to_string();
645        assert_eq!(id_str.as_str(), "cid:10@255:Map");
646        assert_eq!(ContainerID::try_from(id_str.as_str()).unwrap(), id);
647
648        let id = ContainerID::try_from("cid:root-a:b:c:Tree").unwrap();
649        assert_eq!(
650            id,
651            ContainerID::new_root("a:b:c", crate::ContainerType::Tree)
652        );
653    }
654
655    #[test]
656    fn test_convert_invalid_container_id_str() {
657        assert!(ContainerID::try_from("cid:root-:Map").is_err());
658        assert!(ContainerID::try_from("cid:0@:Map").is_err());
659        assert!(ContainerID::try_from("cid:@:Map").is_err());
660        assert!(ContainerID::try_from("cid:x@0:Map").is_err());
661        assert!(ContainerID::try_from("id:0@0:Map").is_err());
662        assert!(ContainerID::try_from("cid:0@0:Unknown(6)").is_ok());
663    }
664
665    #[test]
666    fn test_container_id_encode_and_decode() {
667        let id = ContainerID::new_normal(ID::new(1, 2), ContainerType::Map);
668        let bytes = id.to_bytes();
669        assert_eq!(ContainerID::from_bytes(&bytes), id);
670
671        let id = ContainerID::new_normal(ID::new(u64::MAX, i32::MAX), ContainerType::Text);
672        let bytes = id.to_bytes();
673        assert_eq!(ContainerID::from_bytes(&bytes), id);
674
675        let id = ContainerID::new_root("test_root", ContainerType::List);
676        let bytes = id.to_bytes();
677        assert_eq!(ContainerID::from_bytes(&bytes), id);
678
679        let id = ContainerID::new_normal(ID::new(0, 0), ContainerType::MovableList);
680        let bytes = id.to_bytes();
681        assert_eq!(ContainerID::from_bytes(&bytes), id);
682
683        let id = ContainerID::new_root(&"x".repeat(1024), ContainerType::Tree);
684        let bytes = id.to_bytes();
685        assert_eq!(ContainerID::from_bytes(&bytes), id);
686
687        #[cfg(feature = "counter")]
688        {
689            let id = ContainerID::new_normal(ID::new(42, 100), ContainerType::Counter);
690            let bytes = id.to_bytes();
691            assert_eq!(ContainerID::from_bytes(&bytes), id);
692        }
693
694        let id = ContainerID::new_normal(ID::new(1, 1), ContainerType::Unknown(100));
695        let bytes = id.to_bytes();
696        assert_eq!(ContainerID::from_bytes(&bytes), id);
697    }
698}
loro_common/lib.rs

loro_common/
lib.rs
