crdt_richtext/
lib.rs

1//! Rust implementation of [Peritext](https://www.inkandswitch.com/peritext/) and
2//! [Fugue](https://arxiv.org/abs/2305.00583)
3//!
4//! This crate contains a subset of [Loro CRDT](https://loro.dev/)
5//!
6//! This Rust crate provides an implementation of Peritext that is optimized for
7//! performance. This crate uses a separate data structure to store the range
8//! annotation, decoupled from the underlying list CRDT. This implementation depends
9//! on `RangeMap` trait, which can be implemented efficiently to make the overall
10//! algorithm fast. But currently, this crate only provides a dumb implementation to
11//! provide a proof of concept.
12//!
13
14#![deny(unsafe_code)]
15
16use std::{
17    cmp::Ordering,
18    collections::{BTreeSet, HashMap},
19    fmt::Debug,
20    ops::{Bound, Range, RangeBounds},
21    sync::Arc,
22};
23
24use serde::{Deserialize, Serialize};
25use string_cache::DefaultAtom;
26
27pub mod legacy;
28pub mod rich_text;
29pub use rich_text::{vv::VersionVector, RichText};
30mod small_set;
31#[cfg(feature = "test")]
32mod test_utils;
33pub(crate) type InternalString = DefaultAtom;
34type Lamport = u32;
35type ClientID = u64;
36type Counter = u32;
37
38#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
39pub struct OpID {
40    client: ClientID,
41    counter: Counter,
42}
43
44impl OpID {
45    pub fn inc(&self, inc: Counter) -> Self {
46        Self {
47            client: self.client,
48            counter: self.counter + inc as Counter,
49        }
50    }
51
52    pub fn inc_i32(&self, inc: i32) -> Self {
53        if inc > 0 {
54            Self {
55                client: self.client,
56                counter: self.counter + inc as Counter,
57            }
58        } else {
59            let (mut counter, overflow) = self.counter.overflowing_sub((-inc) as Counter);
60            if overflow {
61                counter = Counter::MAX;
62            }
63
64            Self {
65                client: self.client,
66                counter,
67            }
68        }
69    }
70}
71
72pub(crate) struct IdSpan {
73    id: OpID,
74    len: Counter,
75}
76
77impl IdSpan {
78    pub fn new(id: OpID, len: usize) -> Self {
79        Self {
80            id,
81            len: len as Counter,
82        }
83    }
84
85    pub fn contains(&self, id: OpID) -> bool {
86        self.id.client == id.client
87            && self.id.counter <= id.counter
88            && id.counter < self.id.counter + self.len
89    }
90}
91
92#[derive(Debug, Clone)]
93pub enum RangeOp {
94    Patch(Patch),
95    Annotate(Annotation),
96}
97
98#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
99pub enum AnchorType {
100    Before,
101    After,
102}
103
104#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Deserialize, Serialize)]
105pub enum Behavior {
106    /// When calculating the final state, it will keep all the ranges even if they have the same type
107    ///
108    /// For example, we would like to keep both comments alive even if they have overlapped regions
109    Inclusive = 2,
110    /// When calculating the final state, it will merge the ranges that have overlapped regions and have the same type
111    ///
112    /// For example, [bold 2~5] can be merged with [bold 1~4] to produce [bold 1-5]
113    Merge = 0,
114    /// It will delete the overlapped range that has smaller lamport && has the same type.
115    /// But it will keep the `Inclusive` type unchanged
116    Delete = 1,
117}
118
119/// If both `move_start_to` and `move_end_to` equal to None, the target range will be deleted
120#[derive(Clone, Copy, Debug)]
121pub struct Patch {
122    pub id: OpID,
123    pub target_range_id: OpID,
124    pub move_start_to: Option<OpID>,
125    pub move_end_to: Option<OpID>,
126    pub lamport: Lamport,
127}
128
129#[derive(Clone, Debug, PartialOrd, Ord, PartialEq, Eq)]
130pub struct Annotation {
131    pub id: OpID,
132    /// lamport value of the current range (it may be updated by patch)
133    pub range_lamport: (Lamport, OpID),
134    pub range: AnchorRange,
135    pub behavior: Behavior,
136    /// "bold", "comment", "italic", etc.
137    pub type_: InternalString,
138    pub meta: Option<Vec<u8>>,
139}
140
141#[derive(Debug, Clone, PartialEq, Eq)]
142pub struct Style {
143    pub start_type: AnchorType,
144    pub end_type: AnchorType,
145    pub behavior: Behavior,
146    /// "bold", "comment", "italic", etc.
147    pub type_: InternalString,
148}
149
150#[derive(Debug, PartialEq, Eq, Clone, PartialOrd, Ord)]
151pub struct AnchorRange {
152    pub start: Anchor,
153    pub end: Anchor,
154}
155
156#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
157pub struct Anchor {
158    /// if id is None, it means the anchor is at the beginning or the end of the document
159    pub id: Option<OpID>,
160    pub type_: AnchorType,
161}
162
163impl RangeOp {
164    fn id(&self) -> OpID {
165        match self {
166            RangeOp::Patch(x) => x.id,
167            RangeOp::Annotate(x) => x.id,
168        }
169    }
170
171    #[allow(unused)]
172    fn set_id(&mut self, id: OpID) {
173        match self {
174            RangeOp::Patch(x) => x.id = id,
175            RangeOp::Annotate(x) => x.id = id,
176        }
177    }
178
179    #[allow(unused)]
180    fn lamport(&self) -> Lamport {
181        match self {
182            RangeOp::Patch(x) => x.lamport,
183            RangeOp::Annotate(x) => x.range_lamport.0,
184        }
185    }
186}
187
188impl Anchor {
189    pub fn before(id: OpID) -> Self {
190        Self {
191            id: Some(id),
192            type_: AnchorType::Before,
193        }
194    }
195
196    pub fn after(id: OpID) -> Self {
197        Self {
198            id: Some(id),
199            type_: AnchorType::After,
200        }
201    }
202
203    pub fn before_none() -> Self {
204        Self {
205            id: None,
206            type_: AnchorType::Before,
207        }
208    }
209
210    pub fn after_none() -> Self {
211        Self {
212            id: None,
213            type_: AnchorType::After,
214        }
215    }
216}
217
218impl<T: RangeBounds<OpID>> From<T> for AnchorRange {
219    fn from(range: T) -> Self {
220        let start = match range.start_bound() {
221            Bound::Included(x) => Anchor {
222                id: Some(*x),
223                type_: AnchorType::Before,
224            },
225            Bound::Excluded(x) => Anchor {
226                id: Some(*x),
227                type_: AnchorType::After,
228            },
229            Bound::Unbounded => Anchor {
230                id: None,
231                type_: AnchorType::After,
232            },
233        };
234        let end = match range.end_bound() {
235            Bound::Included(x) => Anchor {
236                id: Some(*x),
237                type_: AnchorType::After,
238            },
239            Bound::Excluded(x) => Anchor {
240                id: Some(*x),
241                type_: AnchorType::Before,
242            },
243            Bound::Unbounded => Anchor {
244                id: None,
245                type_: AnchorType::Before,
246            },
247        };
248        Self { start, end }
249    }
250}
251
252impl OpID {
253    pub fn new(client: u64, counter: Counter) -> Self {
254        Self { client, counter }
255    }
256}
crdt_richtext/lib.rs

crdt_richtext/
lib.rs
