loro_internal/delta/
tree.rs

1use fractional_index::FractionalIndex;
2use rustc_hash::{FxHashMap, FxHashSet};
3use itertools::Itertools;
4use loro_common::{IdFull, TreeID};
5use std::fmt::Debug;
6use std::ops::{Deref, DerefMut};
7
8use crate::state::TreeParentId;
9
10#[derive(Debug, Clone, Default)]
11pub struct TreeDiff {
12    pub diff: Vec<TreeDiffItem>,
13}
14
15#[derive(Debug, Clone)]
16pub struct TreeDiffItem {
17    pub target: TreeID,
18    pub action: TreeExternalDiff,
19}
20
21#[derive(Debug, Clone, PartialEq)]
22pub enum TreeExternalDiff {
23    Create {
24        parent: TreeParentId,
25        index: usize,
26        position: FractionalIndex,
27    },
28    Move {
29        parent: TreeParentId,
30        index: usize,
31        position: FractionalIndex,
32        old_parent: TreeParentId,
33        old_index: usize,
34    },
35    Delete {
36        old_parent: TreeParentId,
37        old_index: usize,
38    },
39}
40
41impl TreeDiff {
42    pub(crate) fn compose(mut self, other: Self) -> Self {
43        self.diff.extend(other.diff);
44        // self = compose_tree_diff(&self);
45        self
46    }
47
48    pub(crate) fn extend<I: IntoIterator<Item = TreeDiffItem>>(mut self, other: I) -> Self {
49        self.diff.extend(other);
50        self
51    }
52
53    fn to_hash_map_mut(&mut self) -> FxHashMap<TreeID, usize> {
54        let mut ans = FxHashSet::default();
55        for index in (0..self.diff.len()).rev() {
56            let target = self.diff[index].target;
57            if ans.contains(&target) {
58                self.diff.remove(index);
59                continue;
60            }
61            ans.insert(target);
62        }
63        self.iter()
64            .map(|x| x.target)
65            .enumerate()
66            .map(|(i, x)| (x, i))
67            .collect()
68    }
69
70    pub(crate) fn transform(&mut self, b: &TreeDiff, left_prior: bool) {
71        // println!("\ntransform prior {:?} {:?} \nb {:?}", left_prior, self, b);
72        if b.is_empty() || self.is_empty() {
73            return;
74        }
75        if !left_prior {
76            let mut self_update = self.to_hash_map_mut();
77            for i in b
78                .iter()
79                .map(|x| x.target)
80                .filter_map(|x| self_update.remove(&x))
81                .sorted()
82                .rev()
83            {
84                self.remove(i);
85            }
86        }
87    }
88}
89
90/// Representation of differences in movable tree. It's an ordered list of [`TreeDiff`].
91#[derive(Clone, Default)]
92pub struct TreeDelta {
93    pub(crate) diff: Vec<TreeDeltaItem>,
94}
95
96impl Debug for TreeDelta {
97    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
98        f.write_str("TreeDelta{ diff: [\n")?;
99        for item in self.diff.iter() {
100            f.write_fmt(format_args!("\t{:?}, \n", item))?;
101        }
102        f.write_str("]}")
103    }
104}
105
106/// The semantic action in movable tree.
107#[derive(Debug, Clone)]
108pub struct TreeDeltaItem {
109    pub target: TreeID,
110    pub action: TreeInternalDiff,
111    pub last_effective_move_op_id: IdFull,
112}
113
114/// The action of [`TreeDiff`]. It's the same as  [`crate::container::tree::tree_op::TreeOp`], but semantic.
115#[derive(Debug, Clone)]
116pub enum TreeInternalDiff {
117    /// First create the node, have not seen it before
118    Create {
119        parent: TreeParentId,
120        position: FractionalIndex,
121    },
122    /// For retreating, if the node is only created, not move it to `DELETED_ROOT` but delete it directly
123    UnCreate,
124    /// Move the node to the parent, the node exists
125    Move {
126        parent: TreeParentId,
127        position: FractionalIndex,
128    },
129    /// move under a parent that is deleted
130    Delete {
131        parent: TreeParentId,
132        position: Option<FractionalIndex>,
133    },
134    /// old parent is deleted, new parent is deleted too
135    MoveInDelete {
136        parent: TreeParentId,
137        position: Option<FractionalIndex>,
138    },
139}
140
141impl TreeDeltaItem {
142    /// * `is_new_parent_deleted` and `is_old_parent_deleted`: we need to infer whether it's a `creation`.
143    ///   It's a creation if the old_parent is deleted but the new parent isn't.
144    ///   If it is a creation, we need to emit the `Create` event so that downstream event handler can
145    ///   handle the new containers easier.
146    pub(crate) fn new(
147        target: TreeID,
148        parent: TreeParentId,
149        old_parent: TreeParentId,
150        op_id: IdFull,
151        is_new_parent_deleted: bool,
152        is_old_parent_deleted: bool,
153        position: Option<FractionalIndex>,
154    ) -> Self {
155        let action = if matches!(parent, TreeParentId::Unexist) {
156            TreeInternalDiff::UnCreate
157        } else {
158            match (
159                is_new_parent_deleted,
160                is_old_parent_deleted || old_parent == TreeParentId::Unexist,
161            ) {
162                (true, true) => TreeInternalDiff::MoveInDelete { parent, position },
163                (true, false) => TreeInternalDiff::Delete { parent, position },
164                (false, true) => TreeInternalDiff::Create {
165                    parent,
166                    position: position.unwrap(),
167                },
168                (false, false) => TreeInternalDiff::Move {
169                    parent,
170                    position: position.unwrap(),
171                },
172            }
173        };
174
175        TreeDeltaItem {
176            target,
177            action,
178            last_effective_move_op_id: op_id,
179        }
180    }
181}
182
183impl Deref for TreeDelta {
184    type Target = Vec<TreeDeltaItem>;
185    fn deref(&self) -> &Self::Target {
186        &self.diff
187    }
188}
189
190impl TreeDelta {
191    // TODO: cannot handle this for now
192    pub(crate) fn compose(mut self, x: TreeDelta) -> TreeDelta {
193        self.diff.extend(x.diff);
194        self
195    }
196}
197
198impl Deref for TreeDiff {
199    type Target = Vec<TreeDiffItem>;
200    fn deref(&self) -> &Self::Target {
201        &self.diff
202    }
203}
204
205impl DerefMut for TreeDiff {
206    fn deref_mut(&mut self) -> &mut Self::Target {
207        &mut self.diff
208    }
209}
loro_internal/delta/tree.rs

loro_internal/delta/
tree.rs
