indigo_kernel/
crdt_vibed_not_length.rs

1//! FugueMax CRDT algorithm.
2//!
3//! ## References:
4//!
5//! - FugueMax paper: <https://arxiv.org/abs/2305.00583>
6//! - Joseph Gentle's simple FugueMax implementation: <https://github.com/josephg/crdt-from-scratch>
7
8#![expect(clippy::doc_markdown)] // Clippy thinks "FugueMax" is missing backticks
9
10use crate::IndigoBuildHasher;
11use std::{collections::HashMap, ops::Range};
12
13pub struct Document {
14    id: DocumentId,
15    content: Vec<Item>,
16    version: Version,
17}
18
19// Public API
20impl Document {
21    /// The id must be unique among documents that merge with each other.
22    #[must_use]
23    pub fn new(id: usize) -> Self {
24        Self {
25            id: DocumentId(id),
26            content: Vec::new(),
27            version: Version::default(),
28        }
29    }
30
31    #[must_use]
32    pub fn text(&self) -> String {
33        self.content
34            .iter()
35            .filter(|item| !item.deleted)
36            .map(|item| item.content)
37            .collect()
38    }
39
40    pub fn insert(&mut self, byte_index: usize, text: &str) -> anyhow::Result<()> {
41        // Even inserting nothing demands a valid byte index.
42        let index = self.insertion_index(byte_index)?;
43        for (index, char) in (index..).zip(text.chars()) {
44            self.insert_char_at(index, char);
45        }
46        Ok(())
47    }
48
49    pub fn delete(&mut self, byte_range: Range<usize>) -> anyhow::Result<()> {
50        let text = self.text();
51        if byte_range.start > byte_range.end
52            || byte_range.end > text.len()
53            || !text.is_char_boundary(byte_range.start)
54            || !text.is_char_boundary(byte_range.end)
55        {
56            anyhow::bail!("invalid byte range {byte_range:?}");
57        }
58        let mut byte_index = 0;
59        for item in &mut self.content {
60            if item.deleted {
61                continue;
62            }
63            if byte_range.contains(&byte_index) {
64                item.deleted = true;
65            }
66            byte_index += item.content.len_utf8();
67        }
68        Ok(())
69    }
70
71    pub fn merge(&mut self, other: &Self) {
72        // Integrate items we haven't seen, dependencies before dependents.
73        let mut pending = other
74            .content
75            .iter()
76            .filter(|item| !self.version.contains(item.id))
77            .cloned()
78            .collect::<Vec<Item>>();
79        while !pending.is_empty() {
80            let (ready, waiting): (Vec<Item>, Vec<Item>) = pending
81                .into_iter()
82                .partition(|item| self.can_integrate(item));
83            assert!(
84                !ready.is_empty(),
85                "documents are causally complete, so every pass integrates something",
86            );
87            for item in ready {
88                self.integrate(item);
89            }
90            pending = waiting;
91        }
92
93        // Propagate deletions. Note [Deletion propagation]
94        let mut content = self.content.iter_mut();
95        for item in other.content.iter().filter(|item| item.deleted) {
96            let ours = content
97                .by_ref()
98                .find(|ours| ours.id == item.id)
99                .expect("item exists");
100            ours.deleted = true;
101        }
102    }
103}
104
105// Private API
106impl Document {
107    /// Inserts a freshly authored character at the given index in `content`,
108    /// its physical neighbors becoming its origins.
109    fn insert_char_at(&mut self, index: usize, char: char) {
110        let item = Item {
111            id: ItemId {
112                document_id: self.id,
113                sequence_number: self.version.next_sequence_number(self.id),
114            },
115            content: char,
116            origin_left: index.checked_sub(1).map(|left| self.content[left].id),
117            origin_right: self.content.get(index).map(|right| right.id),
118            deleted: false,
119        };
120        self.integrate_between(item, index.checked_sub(1), index);
121    }
122
123    /// Where in `content` an insertion at the given byte index in the visible
124    /// text lands. When deleted items straddle the position, insert to their
125    /// left.
126    fn insertion_index(&self, byte_index: usize) -> anyhow::Result<usize> {
127        let mut remaining = byte_index;
128        for (index, item) in self.content.iter().enumerate() {
129            if remaining == 0 {
130                return Ok(index);
131            }
132            if item.deleted {
133                continue;
134            }
135            let Some(rest) = remaining.checked_sub(item.content.len_utf8()) else {
136                anyhow::bail!("byte index {byte_index} is not a char boundary");
137            };
138            remaining = rest;
139        }
140        if remaining == 0 {
141            Ok(self.content.len())
142        } else {
143            anyhow::bail!("byte index {byte_index} is past the end of the document");
144        }
145    }
146
147    fn index_of(&self, id: ItemId) -> usize {
148        self.content
149            .iter()
150            .position(|item| item.id == id)
151            .expect("item exists")
152    }
153
154    /// Whether all of an item's causal dependencies are in this document: the
155    /// previous item from its document of origin, and both origins.
156    fn can_integrate(&self, item: &Item) -> bool {
157        let previous = item
158            .id
159            .sequence_number
160            .checked_sub(1)
161            .map(|sequence_number| ItemId {
162                document_id: item.id.document_id,
163                sequence_number,
164            });
165        !self.version.contains(item.id)
166            && previous.is_none_or(|id| self.version.contains(id))
167            && item.origin_left.is_none_or(|id| self.version.contains(id))
168            && item.origin_right.is_none_or(|id| self.version.contains(id))
169    }
170
171    fn integrate(&mut self, item: Item) {
172        let left = item.origin_left.map(|id| self.index_of(id));
173        let right = item
174            .origin_right
175            .map_or(self.content.len(), |id| self.index_of(id));
176        self.integrate_between(item, left, right);
177    }
178
179    // Note [Integration scan]
180    fn integrate_between(&mut self, item: Item, left: Option<usize>, right: usize) {
181        self.version.record(item.id);
182
183        let mut destination = left.map_or(0, |index| index + 1);
184        let mut scanning = false;
185        for index in destination.. {
186            if !scanning {
187                destination = index;
188            }
189            if index == self.content.len() || index == right {
190                break;
191            }
192            let other = &self.content[index];
193            let other_left = other.origin_left.map(|id| self.index_of(id));
194            let other_right = other
195                .origin_right
196                .map_or(self.content.len(), |id| self.index_of(id));
197            if other_left < left
198                || (other_left == left
199                    && other_right == right
200                    && item.id.document_id < other.id.document_id)
201            {
202                break;
203            }
204            if other_left == left {
205                scanning = other_right < right;
206            }
207        }
208        self.content.insert(destination, item);
209    }
210}
211
212#[cfg(test)]
213impl Document {
214    /// Every item's author, sequence number, and tombstone flag, in document
215    /// order — for cross-implementation equivalence tests.
216    pub(crate) fn item_summaries(&self) -> Vec<(usize, usize, bool)> {
217        self.content
218            .iter()
219            .map(|item| (item.id.document_id.0, item.id.sequence_number, item.deleted))
220            .collect()
221    }
222}
223
224#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd)]
225struct DocumentId(usize);
226
227#[derive(Clone, Copy, PartialEq)]
228struct ItemId {
229    document_id: DocumentId,
230    sequence_number: usize,
231}
232
233#[derive(Clone)]
234struct Item {
235    id: ItemId,
236    content: char,
237    origin_left: Option<ItemId>,
238    origin_right: Option<ItemId>,
239    deleted: bool,
240}
241
242#[derive(Default)]
243struct Version(HashMap<DocumentId, usize, IndigoBuildHasher>);
244
245impl Version {
246    fn contains(&self, id: ItemId) -> bool {
247        self.0
248            .get(&id.document_id)
249            .is_some_and(|highest| *highest >= id.sequence_number)
250    }
251
252    /// Items from a document must be recorded in order, without gaps.
253    fn record(&mut self, id: ItemId) {
254        assert_eq!(
255            id.sequence_number,
256            self.next_sequence_number(id.document_id),
257            "items must be recorded in order",
258        );
259        self.0.insert(id.document_id, id.sequence_number);
260    }
261
262    fn next_sequence_number(&self, document_id: DocumentId) -> usize {
263        self.0.get(&document_id).map_or(0, |highest| highest + 1)
264    }
265}
266
267/*
268Note [Integration scan]
269-----------------------
270
271Claude: `integrate_between` places a new item among its rivals: items inserted
272concurrently into the same gap, between the same left and right origins. The
273scan starts just after the item's left origin and walks forward, stopping at
274the latest by its right origin (or the end of the document). `destination`
275trails the walk, marking where the item would be spliced if the scan stopped
276now.
277
278Each item passed is judged by its origins, mapped to indexes so they compare
279like document positions. A left origin of `None` is the virtual item before the
280document, and `Option`'s derived ordering conveniently puts `None` first, just
281like the reference implementation's `-1` sentinel. An item whose left origin is
282earlier than ours closes the gap we were inserted into: we belong before it. An
283item whose left origin is later sits inside an earlier rival's subtree: we skip
284past it. Items sharing our left origin are true siblings, ordered by their
285right origins (later first), with ties broken by document id, smaller first.
286
287A sibling whose right origin is earlier than ours might come before or after us
288depending on what the scan finds next, so the walk enters a "scanning" state
289that leaves `destination` pinned behind: if the scan later decides the item
290belongs before the ambiguous run, it splices at the pinned spot, and if it
291instead finds a sibling proving the item belongs after, `destination` catches
292back up.
293
294Remote items enter through `integrate`, which finds their origins' indexes by
295searching for the origins' ids. Local insertions skip that: a freshly authored
296item's origins are its physical neighbors, so `insert_char_at` already holds
297their indexes and calls `integrate_between` directly. With `right` immediately
298adjacent to the left origin, the scan stops before examining anyone, and the
299item lands exactly where the user put it.
300
301Note [Deletion propagation]
302---------------------------
303
304Claude: `merge` propagates the other document's deletions in a single forward
305pass, one cursor over each document, never backing up. That works because the
306algorithm defines one total order over all items, determined only by their
307origins and ids, and every document displays whichever items it holds in that
308order. After integration this document holds a superset of the other's items,
309so the other's items appear here in the same relative order, and each next
310deleted item can only lie ahead of the last one found.
311*/
312
313#[cfg(test)]
314mod tests {
315    use super::*;
316    use hegel::generators as gs;
317
318    #[test]
319    fn ties_broken_by_smaller_document_id() -> anyhow::Result<()> {
320        let mut doc1 = Document::new(1);
321        let mut doc2 = Document::new(2);
322
323        doc1.insert(0, "A")?;
324        doc2.insert(0, "B")?;
325
326        doc1.merge(&doc2);
327        doc2.merge(&doc1);
328
329        assert_eq!(doc1.text(), "AB");
330        assert_eq!(doc2.text(), "AB");
331        Ok(())
332    }
333
334    /// Draws a byte index in `[0, text.len()]` lying on a `char` boundary.
335    fn draw_boundary(tc: &hegel::TestCase, text: &str) -> usize {
336        let mut index = tc.draw(gs::integers::<usize>().max_value(text.len()));
337        while !text.is_char_boundary(index) {
338            index += 1;
339        }
340        index
341    }
342
343    /// Draws a random valid edit and applies it to both the document and a
344    /// plain `String` model of its visible text.
345    fn edit_both(tc: &hegel::TestCase, doc: &mut Document, model: &mut String) {
346        if model.is_empty() || tc.draw(gs::booleans()) {
347            let index = draw_boundary(tc, model);
348            let text: String = tc.draw(gs::text().max_size(8));
349            doc.insert(index, &text).unwrap();
350            model.insert_str(index, &text);
351        } else {
352            let one = draw_boundary(tc, model);
353            let two = draw_boundary(tc, model);
354            let range = one.min(two)..one.max(two);
355            doc.delete(range.clone()).unwrap();
356            model.replace_range(range, "");
357        }
358    }
359
360    /// Draws a few random edits and applies them to the document.
361    fn edit_randomly(tc: &hegel::TestCase, doc: &mut Document) {
362        let edits = tc.draw(gs::integers::<usize>().max_value(3));
363        for _ in 0..edits {
364            let mut model = doc.text();
365            edit_both(tc, doc, &mut model);
366        }
367    }
368
369    /// Every item's id, character, and tombstone flag, in order. Converged
370    /// documents must agree on this, not just on visible text: a hidden
371    /// disagreement about tombstone order only surfaces as divergence on some
372    /// later edit.
373    fn items(doc: &Document) -> Vec<(usize, usize, char, bool)> {
374        doc.content
375            .iter()
376            .map(|item| {
377                (
378                    item.id.document_id.0,
379                    item.id.sequence_number,
380                    item.content,
381                    item.deleted,
382                )
383            })
384            .collect()
385    }
386
387    /// Types `text` into the document one character at a time, either forward
388    /// ("abc" typed a, b, c after each other) or backward ("abc" built c, b, a
389    /// with every insert at the same position).
390    fn type_at(tc: &hegel::TestCase, doc: &mut Document, byte_index: usize, text: &str) {
391        if tc.draw(gs::booleans()) {
392            let mut byte_index = byte_index;
393            for char in text.chars() {
394                doc.insert(byte_index, &char.to_string()).unwrap();
395                byte_index += char.len_utf8();
396            }
397        } else {
398            for char in text.chars().rev() {
399                doc.insert(byte_index, &char.to_string()).unwrap();
400            }
401        }
402    }
403
404    /// `docs[into].merge(&docs[from])`, which the borrow checker only allows
405    /// through a split.
406    fn merge_pair(docs: &mut [Document], into: usize, from: usize) {
407        if into < from {
408            let (left, right) = docs.split_at_mut(from);
409            left[into].merge(&right[0]);
410        } else {
411            let (left, right) = docs.split_at_mut(into);
412            right[0].merge(&left[from]);
413        }
414    }
415
416    #[hegel::test(test_cases = 5_000)]
417    fn local_edits_match_string(tc: hegel::TestCase) {
418        let mut doc = Document::new(1);
419        let mut model = String::new();
420        let edits = tc.draw(gs::integers::<usize>().max_value(20));
421        for _ in 0..edits {
422            edit_both(&tc, &mut doc, &mut model);
423            assert_eq!(doc.text(), model);
424        }
425    }
426
427    #[hegel::test(test_cases = 1_500)]
428    fn concurrent_edits_converge(tc: hegel::TestCase) {
429        let count = tc.draw(gs::integers::<usize>().min_value(2).max_value(4));
430        let mut docs = (1..=count).map(Document::new).collect::<Vec<Document>>();
431
432        let rounds = tc.draw(gs::integers::<usize>().min_value(1).max_value(3));
433        for _ in 0..rounds {
434            // Everyone edits concurrently...
435            for doc in &mut docs {
436                edit_randomly(&tc, doc);
437            }
438            // ...then two documents gossip.
439            let into = tc.draw(gs::integers::<usize>().max_value(count - 1));
440            let from = tc.draw(gs::integers::<usize>().max_value(count - 1));
441            if into != from {
442                merge_pair(&mut docs, into, from);
443            }
444        }
445
446        // After merging all-to-all, every document has seen every edit.
447        for into in 0..count {
448            for from in 0..count {
449                if into != from {
450                    merge_pair(&mut docs, into, from);
451                }
452            }
453        }
454        for pair in docs.windows(2) {
455            assert_eq!(items(&pair[0]), items(&pair[1]));
456        }
457    }
458
459    /// FugueMax's defining guarantee: runs of text typed concurrently at the
460    /// same position never interleave. The disjoint alphabets make the
461    /// substring checks exact.
462    #[hegel::test(test_cases = 2_000)]
463    fn concurrent_typing_does_not_interleave(tc: hegel::TestCase) {
464        let base: String = tc.draw(gs::text().alphabet("xyz"));
465        let mut doc1 = Document::new(1);
466        doc1.insert(0, &base).unwrap();
467        let mut doc2 = Document::new(2);
468        doc2.merge(&doc1);
469
470        let byte_index = draw_boundary(&tc, &base);
471        let text1: String = tc.draw(gs::text().alphabet("ABC").min_size(1));
472        let text2: String = tc.draw(gs::text().alphabet("123").min_size(1));
473        type_at(&tc, &mut doc1, byte_index, &text1);
474        type_at(&tc, &mut doc2, byte_index, &text2);
475
476        doc1.merge(&doc2);
477        doc2.merge(&doc1);
478        assert_eq!(items(&doc1), items(&doc2));
479        assert!(doc1.text().contains(&text1));
480        assert!(doc1.text().contains(&text2));
481    }
482
483    #[hegel::test(test_cases = 2_000)]
484    fn merge_is_idempotent(tc: hegel::TestCase) {
485        let mut doc1 = Document::new(1);
486        let mut doc2 = Document::new(2);
487        edit_randomly(&tc, &mut doc1);
488        edit_randomly(&tc, &mut doc2);
489
490        // Share some history, then diverge again, so re-merging must skip
491        // partially overlapping versions rather than a wholly foreign document.
492        doc1.merge(&doc2);
493        doc2.merge(&doc1);
494        edit_randomly(&tc, &mut doc1);
495        edit_randomly(&tc, &mut doc2);
496
497        doc1.merge(&doc2);
498        let merged = items(&doc1);
499        doc1.merge(&doc2);
500        assert_eq!(items(&doc1), merged);
501    }
502
503    #[hegel::test(test_cases = 5_000)]
504    fn invalid_edits_error_and_change_nothing(tc: hegel::TestCase) {
505        let mut doc = Document::new(1);
506        let initial: String = tc.draw(gs::text());
507        doc.insert(0, &initial).unwrap();
508        let mut model = doc.text();
509
510        // Insert at an arbitrary byte index, valid or not.
511        let index = tc.draw(hegel::one_of!(
512            gs::integers::<usize>().max_value(model.len() + 1),
513            gs::integers::<usize>(),
514        ));
515        let text: String = tc.draw(gs::text());
516        if model.is_char_boundary(index) {
517            doc.insert(index, &text).unwrap();
518            model.insert_str(index, &text);
519        } else {
520            assert!(doc.insert(index, &text).is_err());
521        }
522        assert_eq!(doc.text(), model);
523
524        // Delete an arbitrary byte range, valid or not.
525        let start = tc.draw(hegel::one_of!(
526            gs::integers::<usize>().max_value(model.len() + 1),
527            gs::integers::<usize>(),
528        ));
529        let end = tc.draw(hegel::one_of!(
530            gs::integers::<usize>().max_value(model.len() + 1),
531            gs::integers::<usize>(),
532        ));
533        if start <= end && model.is_char_boundary(start) && model.is_char_boundary(end) {
534            doc.delete(start..end).unwrap();
535            model.replace_range(start..end, "");
536        } else {
537            assert!(doc.delete(start..end).is_err());
538        }
539        assert_eq!(doc.text(), model);
540    }
541}
indigo_kernel/crdt_vibed_not_length.rs

indigo_kernel/
crdt_vibed_not_length.rs
