loro_internal/
container.rs

1//! CRDT [Container]. Each container may have different CRDT type [ContainerType].
2//! Each [Op] has an associated container. It's the [Container]'s responsibility to
3//! calculate the state from the [Op]s.
4//!
5//! Every [Container] can take a [Snapshot], which contains [crate::LoroValue] that describes the state.
6//!
7use crate::{arena::SharedArena, InternalString, ID};
8
9pub mod list;
10pub mod map;
11pub mod richtext;
12pub mod tree;
13pub mod idx {
14    use super::super::ContainerType;
15
16    /// Inner representation for ContainerID.
17    /// It contains the unique index for the container and the type of the container.
18    /// It uses top 4 bits to represent the type of the container.
19    ///
20    /// It's only used inside this crate and should not be exposed to the user.
21    ///
22    /// TODO: make this type private in this crate only
23    ///
24    ///
25    // During a transaction, we may create some containers which are deleted later. And these containers also need a unique ContainerIdx.
26    // So when we encode snapshot, we need to sort the containers by ContainerIdx and change the `container` of ops to the index of containers.
27    // An empty store decodes the snapshot, it will create these containers in a sequence of natural numbers so that containers and ops can correspond one-to-one
28    //
29    // TODO: PERF: use NonZeroU32 to save memory
30    #[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash)]
31    pub struct ContainerIdx(u32);
32
33    impl std::fmt::Debug for ContainerIdx {
34        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
35            write!(f, "ContainerIdx({} {})", self.get_type(), self.to_index())
36        }
37    }
38
39    impl std::fmt::Display for ContainerIdx {
40        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
41            write!(f, "ContainerIdx({} {})", self.get_type(), self.to_index())
42        }
43    }
44
45    impl ContainerIdx {
46        pub(crate) const TYPE_MASK: u32 = 0b11111 << 27;
47        pub(crate) const INDEX_MASK: u32 = !Self::TYPE_MASK;
48
49        #[allow(unused)]
50        pub(crate) fn get_type(self) -> ContainerType {
51            let a = (self.0 & Self::TYPE_MASK) >> 27;
52            if self.is_unknown() {
53                Self::parse_unknown_type(a)
54            } else {
55                ContainerType::try_from_u8(a as u8).unwrap()
56            }
57        }
58
59        #[allow(unused)]
60        pub(crate) fn to_index(self) -> u32 {
61            self.0 & Self::INDEX_MASK
62        }
63
64        pub(crate) fn from_index_and_type(index: u32, container_type: ContainerType) -> Self {
65            let prefix: u32 = if matches!(container_type, ContainerType::Unknown(_)) {
66                Self::unknown_to_prefix(container_type)
67            } else {
68                container_type.to_u8() as u32
69            } << 27;
70
71            Self(prefix | index)
72        }
73
74        pub(crate) fn is_unknown(&self) -> bool {
75            self.0 >> 31 == 1
76        }
77
78        // The type_value is >>27 first, so it's 5 bits.
79        // we want to get the last 4 bits. so we use 0b1111 to get the last 4 bits.
80        fn parse_unknown_type(type_value: u32) -> ContainerType {
81            ContainerType::Unknown((type_value & 0b1111) as u8)
82        }
83
84        // we use the top 5 bits to represent the type of the container.
85        // the first bit is whether it's an unknown type.
86        // So when we convert an unknown type to a prefix, we need to set the first bit to 1.
87        fn unknown_to_prefix(c: ContainerType) -> u32 {
88            if let ContainerType::Unknown(c) = c {
89                (0b10000 | c) as u32
90            } else {
91                unreachable!()
92            }
93        }
94    }
95}
96use idx::ContainerIdx;
97
98pub use loro_common::ContainerType;
99
100pub use loro_common::ContainerID;
101
102#[derive(Debug)]
103pub enum ContainerIdRaw {
104    Root { name: InternalString },
105    Normal { id: ID },
106}
107
108pub trait IntoContainerId {
109    fn into_container_id(self, arena: &SharedArena, kind: ContainerType) -> ContainerID;
110}
111
112impl IntoContainerId for String {
113    fn into_container_id(self, _arena: &SharedArena, kind: ContainerType) -> ContainerID {
114        ContainerID::Root {
115            name: InternalString::from(self.as_str()),
116            container_type: kind,
117        }
118    }
119}
120
121impl IntoContainerId for &str {
122    fn into_container_id(self, _arena: &SharedArena, kind: ContainerType) -> ContainerID {
123        ContainerID::Root {
124            name: InternalString::from(self),
125            container_type: kind,
126        }
127    }
128}
129
130impl IntoContainerId for ContainerID {
131    fn into_container_id(self, _arena: &SharedArena, _kind: ContainerType) -> ContainerID {
132        self
133    }
134}
135
136impl IntoContainerId for &ContainerID {
137    fn into_container_id(self, _arena: &SharedArena, _kind: ContainerType) -> ContainerID {
138        self.clone()
139    }
140}
141
142impl IntoContainerId for ContainerIdx {
143    fn into_container_id(self, arena: &SharedArena, kind: ContainerType) -> ContainerID {
144        assert_eq!(self.get_type(), kind);
145        arena.get_container_id(self).unwrap()
146    }
147}
148
149impl IntoContainerId for &ContainerIdx {
150    fn into_container_id(self, arena: &SharedArena, kind: ContainerType) -> ContainerID {
151        assert_eq!(self.get_type(), kind);
152        arena.get_container_id(*self).unwrap()
153    }
154}
155
156impl From<String> for ContainerIdRaw {
157    fn from(value: String) -> Self {
158        ContainerIdRaw::Root { name: value.into() }
159    }
160}
161
162impl<'a> From<&'a str> for ContainerIdRaw {
163    fn from(value: &'a str) -> Self {
164        ContainerIdRaw::Root { name: value.into() }
165    }
166}
167
168impl From<&ContainerID> for ContainerIdRaw {
169    fn from(id: &ContainerID) -> Self {
170        match id {
171            ContainerID::Root { name, .. } => ContainerIdRaw::Root { name: name.clone() },
172            ContainerID::Normal { peer, counter, .. } => ContainerIdRaw::Normal {
173                id: ID::new(*peer, *counter),
174            },
175        }
176    }
177}
178
179impl From<ContainerID> for ContainerIdRaw {
180    fn from(id: ContainerID) -> Self {
181        match id {
182            ContainerID::Root { name, .. } => ContainerIdRaw::Root { name },
183            ContainerID::Normal { peer, counter, .. } => ContainerIdRaw::Normal {
184                id: ID::new(peer, counter),
185            },
186        }
187    }
188}
189
190impl ContainerIdRaw {
191    pub fn with_type(self, container_type: ContainerType) -> ContainerID {
192        match self {
193            ContainerIdRaw::Root { name } => ContainerID::Root {
194                name,
195                container_type,
196            },
197            ContainerIdRaw::Normal { id } => ContainerID::Normal {
198                peer: id.peer,
199                counter: id.counter,
200                container_type,
201            },
202        }
203    }
204}
205
206#[cfg(test)]
207mod test {
208    use super::idx::ContainerIdx;
209    use super::*;
210
211    #[test]
212    fn container_id_convert() {
213        let container_id = ContainerID::new_normal(ID::new(12, 12), ContainerType::List);
214        let s = container_id.to_string();
215        assert_eq!(s, "cid:12@12:List");
216        let actual = ContainerID::try_from(s.as_str()).unwrap();
217        assert_eq!(actual, container_id);
218
219        let container_id = ContainerID::new_root("123", ContainerType::Map);
220        let s = container_id.to_string();
221        assert_eq!(s, "cid:root-123:Map");
222        let actual = ContainerID::try_from(s.as_str()).unwrap();
223        assert_eq!(actual, container_id);
224
225        let container_id = ContainerID::new_root("kkk", ContainerType::Text);
226        let s = container_id.to_string();
227        assert_eq!(s, "cid:root-kkk:Text");
228        let actual = ContainerID::try_from(s.as_str()).unwrap();
229        assert_eq!(actual, container_id);
230    }
231
232    #[test]
233    fn container_idx_preserves_type_bits_and_index_bits() {
234        let idx = ContainerIdx::from_index_and_type(42, ContainerType::Text);
235        assert_eq!(idx.get_type(), ContainerType::Text);
236        assert_eq!(idx.to_index(), 42);
237        assert!(!idx.is_unknown());
238        assert_eq!(idx.to_string(), "ContainerIdx(Text 42)");
239        assert_eq!(format!("{idx:?}"), "ContainerIdx(Text 42)");
240
241        let max_index =
242            ContainerIdx::from_index_and_type(ContainerIdx::INDEX_MASK, ContainerType::MovableList);
243        assert_eq!(max_index.get_type(), ContainerType::MovableList);
244        assert_eq!(max_index.to_index(), ContainerIdx::INDEX_MASK);
245
246        let unknown = ContainerIdx::from_index_and_type(7, ContainerType::Unknown(13));
247        assert!(unknown.is_unknown());
248        assert_eq!(unknown.get_type(), ContainerType::Unknown(13));
249        assert_eq!(unknown.to_index(), 7);
250        assert_eq!(unknown.to_string(), "ContainerIdx(Unknown(13) 7)");
251    }
252
253    #[test]
254    fn container_id_raw_reapplies_type_for_root_and_normal_ids() {
255        let root = ContainerIdRaw::from("notes").with_type(ContainerType::Map);
256        assert_eq!(root, ContainerID::new_root("notes", ContainerType::Map));
257
258        let normal_id = ID::new(7, 11);
259        let normal = ContainerIdRaw::from(ContainerID::new_normal(normal_id, ContainerType::List))
260            .with_type(ContainerType::Text);
261        assert_eq!(
262            normal,
263            ContainerID::new_normal(normal_id, ContainerType::Text)
264        );
265
266        let root_again = ContainerIdRaw::from(&root).with_type(ContainerType::Tree);
267        assert_eq!(
268            root_again,
269            ContainerID::new_root("notes", ContainerType::Tree)
270        );
271    }
272
273    #[test]
274    fn into_container_id_uses_root_names_ids_and_arena_indexes() {
275        let arena = SharedArena::new();
276        assert_eq!(
277            "workspace".into_container_id(&arena, ContainerType::Map),
278            ContainerID::new_root("workspace", ContainerType::Map)
279        );
280        assert_eq!(
281            String::from("text").into_container_id(&arena, ContainerType::Text),
282            ContainerID::new_root("text", ContainerType::Text)
283        );
284
285        let normal = ContainerID::new_normal(ID::new(1, 2), ContainerType::List);
286        assert_eq!(
287            (&normal).into_container_id(&arena, ContainerType::Map),
288            normal
289        );
290        assert_eq!(
291            normal
292                .clone()
293                .into_container_id(&arena, ContainerType::Text),
294            normal
295        );
296
297        let idx = arena.register_container(&normal);
298        assert_eq!(idx.into_container_id(&arena, ContainerType::List), normal);
299        assert_eq!(
300            (&idx).into_container_id(&arena, ContainerType::List),
301            normal
302        );
303    }
304
305    #[test]
306    #[should_panic(expected = "assertion `left == right` failed")]
307    fn into_container_id_rejects_mismatched_index_type() {
308        let arena = SharedArena::new();
309        let id = ContainerID::new_root("items", ContainerType::List);
310        let idx = arena.register_container(&id);
311
312        let _ = idx.into_container_id(&arena, ContainerType::Map);
313    }
314}
loro_internal/container.rs

loro_internal/
container.rs
