yrs 0.25.0

High performance implementation of the Yjs CRDT
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

use crate::block::{BlockCell, ClientID, GC};
use crate::{DeleteSet, Store, TransactionMut, ID};
use std::collections::HashMap;

#[derive(Default)]
pub(crate) struct GCCollector {
    marked: HashMap<ClientID, Vec<u32>>,
}

impl GCCollector {
    /// Garbage collect all blocks deleted within current transaction scope.
    pub fn collect(txn: &mut TransactionMut) {
        let mut gc = Self::default();
        gc.mark_in_scope(&mut txn.store, None, &txn.delete_set);
        gc.collect_marked(txn);
    }

    /// Garbage collect all deleted blocks from current transaction's document store.
    pub fn collect_all(txn: &mut TransactionMut, delete_set: Option<&DeleteSet>) {
        let mut gc = Self::default();
        match delete_set {
            None => gc.mark_all(txn),
            Some(ds) => gc.mark_in_scope(&mut txn.store, Some(&mut txn.merge_blocks), ds),
        }
        gc.collect_marked(txn);
    }

    /// Mark deleted items based on a provided delete set.
    fn mark_in_scope(
        &mut self,
        store: &mut Store,
        mut merge_blocks: Option<&mut Vec<ID>>,
        delete_set: &DeleteSet,
    ) {
        for (client, range) in delete_set.iter() {
            if let Some(blocks) = store.blocks.get_client_mut(client) {
                for delete_item in range.iter().rev() {
                    let mut start = delete_item.start;
                    if let Some(mut i) = blocks.find_pivot(start) {
                        while i < blocks.len() {
                            let block = &mut blocks[i];
                            let len = block.len();
                            start += len;
                            if start > delete_item.end {
                                break;
                            } else {
                                if let BlockCell::Block(item) = block {
                                    item.gc(self, false);
                                    if let Some(merge_blocks) = merge_blocks.as_deref_mut() {
                                        merge_blocks.push(item.id);
                                    }
                                }
                                i += 1;
                            }
                        }
                    }
                }
            }
        }
    }

    fn mark_all(&mut self, txn: &mut TransactionMut) {
        for (_, client_blocks) in txn.store.blocks.iter_mut() {
            for block in client_blocks.iter_mut() {
                if let BlockCell::Block(item) = block {
                    if item.is_deleted() {
                        item.gc(self, false);
                        txn.merge_blocks.push(item.id);
                    }
                }
            }
        }
    }

    /// Marks item with a given [ID] as a candidate for being GCed.
    pub(crate) fn mark(&mut self, id: &ID) {
        let client = self.marked.entry(id.client).or_default();
        client.push(id.clock);
    }

    /// Garbage collects all items marked for GC.
    fn collect_marked(self, txn: &mut TransactionMut) {
        for (client_id, clocks) in self.marked.into_iter() {
            let client = txn.store.blocks.get_client_blocks_mut(client_id);
            for clock in clocks {
                if let Some(index) = client.find_pivot(clock) {
                    let block = &mut client[index];
                    if let BlockCell::Block(item) = block {
                        if item.is_deleted() && !item.info.is_keep() {
                            let (start, end) = item.clock_range();
                            let gc = BlockCell::GC(GC::new(start, end));
                            *block = gc;
                        }
                    }
                }
            }
        }
    }
}