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

loro_common/
lib.rs
