loro_internal/handler/
tree.rs

1use std::{collections::VecDeque, sync::Arc};
2
3use fractional_index::FractionalIndex;
4use fxhash::FxHashMap;
5use loro_common::{
6    ContainerID, ContainerType, Counter, IdLp, LoroError, LoroResult, LoroTreeError, LoroValue,
7    PeerID, TreeID, ID,
8};
9use smallvec::smallvec;
10
11use crate::{
12    container::tree::tree_op::TreeOp,
13    delta::{TreeDiffItem, TreeExternalDiff},
14    state::{
15        FiIfNotConfigured, FractionalIndexGenResult, NodePosition, TreeNode, TreeNodeWithChildren,
16        TreeParentId,
17    },
18    txn::{EventHint, Transaction},
19    BasicHandler, HandlerTrait, MapHandler,
20};
21
22use super::{create_handler, Handler, MaybeDetached};
23
24#[derive(Clone)]
25pub struct TreeHandler {
26    pub(super) inner: MaybeDetached<TreeInner>,
27}
28
29#[derive(Clone)]
30pub(super) struct TreeInner {
31    next_counter: Counter,
32    map: FxHashMap<TreeID, MapHandler>,
33    parent_links: FxHashMap<TreeID, Option<TreeID>>,
34    children_links: FxHashMap<Option<TreeID>, Vec<TreeID>>,
35}
36
37impl TreeInner {
38    fn new() -> Self {
39        TreeInner {
40            next_counter: 0,
41            map: FxHashMap::default(),
42            parent_links: FxHashMap::default(),
43            children_links: FxHashMap::default(),
44        }
45    }
46
47    fn create(&mut self, parent: Option<TreeID>, index: usize) -> TreeID {
48        let id = TreeID::new(PeerID::MAX, self.next_counter);
49        self.next_counter += 1;
50        self.map.insert(id, MapHandler::new_detached());
51        self.parent_links.insert(id, parent);
52        let children = self.children_links.entry(parent).or_default();
53        children.insert(index, id);
54        id
55    }
56
57    fn mov(&mut self, target: TreeID, new_parent: Option<TreeID>, index: usize) -> LoroResult<()> {
58        let old_parent = self
59            .parent_links
60            .get_mut(&target)
61            .ok_or(LoroTreeError::TreeNodeNotExist(target))?;
62        let children = self.children_links.get_mut(old_parent).unwrap();
63        children.retain(|x| x != &target);
64        self.parent_links.insert(target, new_parent);
65        let children = self.children_links.entry(new_parent).or_default();
66        children.insert(index, target);
67        Ok(())
68    }
69
70    fn delete(&mut self, id: TreeID) -> LoroResult<()> {
71        self.map.remove(&id);
72        let parent = self
73            .parent_links
74            .remove(&id)
75            .ok_or(LoroTreeError::TreeNodeNotExist(id))?;
76        let children = self.children_links.get_mut(&parent).unwrap();
77        children.retain(|x| x != &id);
78        self.children_links.remove(&Some(id));
79        Ok(())
80    }
81
82    fn get_id_by_index(&self, parent: &Option<TreeID>, index: usize) -> Option<TreeID> {
83        self.children_links
84            .get(parent)
85            .and_then(|x| x.get(index).cloned())
86    }
87
88    fn get_parent(&self, id: &TreeID) -> Option<Option<TreeID>> {
89        self.parent_links.get(id).cloned()
90    }
91
92    fn get_children(&self, parent: Option<TreeID>) -> Option<Vec<TreeID>> {
93        self.children_links.get(&parent).cloned()
94    }
95
96    fn children_num(&self, parent: Option<TreeID>) -> Option<usize> {
97        self.children_links.get(&parent).map(|x| x.len())
98    }
99
100    fn is_parent(&self, target: &TreeID, parent: &Option<TreeID>) -> bool {
101        self.parent_links.get(target) == Some(parent)
102    }
103
104    fn get_index_by_tree_id(&self, target: &TreeID) -> Option<usize> {
105        self.parent_links
106            .get(target)
107            .and_then(|parent| self.children_links.get(parent))
108            .and_then(|children| children.iter().position(|x| x == target))
109    }
110
111    fn get_value(&self, deep: bool) -> LoroValue {
112        let mut ans = vec![];
113
114        let mut q = VecDeque::from_iter(
115            self.children_links
116                .get(&None)
117                .unwrap()
118                .iter()
119                .enumerate()
120                .zip(std::iter::repeat(None::<TreeID>)),
121        );
122        while let Some(((idx, target), parent)) = q.pop_front() {
123            let map = self.map.get(target).unwrap();
124            let mut loro_map_value = FxHashMap::default();
125            loro_map_value.insert("id".to_string(), target.to_string().into());
126            let parent = parent
127                .map(|p| p.to_string().into())
128                .unwrap_or(LoroValue::Null);
129            loro_map_value.insert("parent".to_string(), parent);
130            loro_map_value.insert(
131                "meta".to_string(),
132                if deep {
133                    map.get_deep_value()
134                } else {
135                    String::from("UnResolved").into()
136                },
137            );
138            loro_map_value.insert("index".to_string(), (idx as i64).into());
139            ans.push(loro_map_value);
140            if let Some(children) = self.children_links.get(&Some(*target)) {
141                for (idx, child) in children.iter().enumerate() {
142                    q.push_back(((idx, child), Some(*target)));
143                }
144            }
145        }
146        ans.into()
147    }
148}
149
150impl HandlerTrait for TreeHandler {
151    fn to_handler(&self) -> Handler {
152        Handler::Tree(self.clone())
153    }
154
155    fn attach(
156        &self,
157        txn: &mut Transaction,
158        parent: &BasicHandler,
159        self_id: ContainerID,
160    ) -> LoroResult<Self> {
161        match &self.inner {
162            MaybeDetached::Detached(t) => {
163                let t = t.try_lock().unwrap();
164                let inner = create_handler(parent, self_id);
165                let tree = inner.into_tree().unwrap();
166
167                let children = t.value.children_links.get(&None);
168                let mut q = children
169                    .map(|c| {
170                        VecDeque::from_iter(
171                            c.iter()
172                                .enumerate()
173                                .zip(std::iter::repeat(TreeParentId::Root)),
174                        )
175                    })
176                    .unwrap_or_default();
177                while let Some(((idx, target), parent)) = q.pop_front() {
178                    let real_id =
179                        tree.create_with_txn(txn, parent, idx, FiIfNotConfigured::UseJitterZero)?;
180                    let map = t.value.map.get(target).unwrap();
181                    map.attach(
182                        txn,
183                        tree.inner.try_attached_state()?,
184                        real_id.associated_meta_container(),
185                    )?;
186
187                    if let Some(children) = t.value.children_links.get(&Some(*target)) {
188                        for (idx, child) in children.iter().enumerate() {
189                            q.push_back(((idx, child), TreeParentId::Node(real_id)));
190                        }
191                    }
192                }
193                Ok(tree)
194            }
195            MaybeDetached::Attached(a) => {
196                let new_inner = create_handler(a, self_id);
197                let ans = new_inner.into_tree().unwrap();
198                let tree_nodes = ans.with_state(|s| Ok(s.as_tree_state().unwrap().tree_nodes()))?;
199                for node in tree_nodes {
200                    let parent = node.parent;
201                    let index = node.index;
202                    let target = node.id;
203                    let real_id =
204                        ans.create_with_txn(txn, parent, index, FiIfNotConfigured::UseJitterZero)?;
205                    ans.get_meta(target)?
206                        .attach(txn, a, real_id.associated_meta_container())?;
207                }
208                Ok(ans)
209            }
210        }
211    }
212
213    fn is_attached(&self) -> bool {
214        self.inner.is_attached()
215    }
216
217    fn attached_handler(&self) -> Option<&BasicHandler> {
218        self.inner.attached_handler()
219    }
220
221    fn get_value(&self) -> LoroValue {
222        match &self.inner {
223            MaybeDetached::Detached(t) => {
224                let t = t.try_lock().unwrap();
225                t.value.get_value(false)
226            }
227            MaybeDetached::Attached(a) => a.get_value(),
228        }
229    }
230
231    fn get_deep_value(&self) -> LoroValue {
232        match &self.inner {
233            MaybeDetached::Detached(t) => {
234                let t = t.try_lock().unwrap();
235                t.value.get_value(true)
236            }
237            MaybeDetached::Attached(a) => a.get_deep_value(),
238        }
239    }
240
241    fn kind(&self) -> ContainerType {
242        ContainerType::Tree
243    }
244
245    fn get_attached(&self) -> Option<Self> {
246        match &self.inner {
247            MaybeDetached::Detached(d) => d.try_lock().unwrap().attached.clone().map(|x| Self {
248                inner: MaybeDetached::Attached(x),
249            }),
250            MaybeDetached::Attached(_a) => Some(self.clone()),
251        }
252    }
253
254    fn from_handler(h: Handler) -> Option<Self> {
255        match h {
256            Handler::Tree(x) => Some(x),
257            _ => None,
258        }
259    }
260
261    fn doc(&self) -> Option<crate::LoroDoc> {
262        match &self.inner {
263            MaybeDetached::Detached(_) => None,
264            MaybeDetached::Attached(a) => Some(a.doc()),
265        }
266    }
267}
268
269impl std::fmt::Debug for TreeHandler {
270    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
271        match &self.inner {
272            MaybeDetached::Detached(_) => write!(f, "TreeHandler Detached"),
273            MaybeDetached::Attached(a) => write!(f, "TreeHandler {}", a.id),
274        }
275    }
276}
277
278impl TreeHandler {
279    /// Create a new container that is detached from the document.
280    ///
281    /// The edits on a detached container will not be persisted/synced.
282    /// To attach the container to the document, please insert it into an attached
283    /// container.
284    pub fn new_detached() -> Self {
285        Self {
286            inner: MaybeDetached::new_detached(TreeInner::new()),
287        }
288    }
289
290    pub fn delete(&self, target: TreeID) -> LoroResult<()> {
291        match &self.inner {
292            MaybeDetached::Detached(t) => {
293                let mut t = t.try_lock().unwrap();
294                t.value.delete(target)?;
295                Ok(())
296            }
297            MaybeDetached::Attached(a) => a.with_txn(|txn| self.delete_with_txn(txn, target)),
298        }
299    }
300
301    pub(crate) fn delete_with_txn(&self, txn: &mut Transaction, target: TreeID) -> LoroResult<()> {
302        let inner = self.inner.try_attached_state()?;
303        let index = match self.get_index_by_tree_id(&target) {
304            Some(i) => i,
305            None => {
306                return Err(LoroTreeError::TreeNodeDeletedOrNotExist(target).into());
307            }
308        };
309        txn.apply_local_op(
310            inner.container_idx,
311            crate::op::RawOpContent::Tree(Arc::new(TreeOp::Delete { target })),
312            EventHint::Tree(smallvec![TreeDiffItem {
313                target,
314                action: TreeExternalDiff::Delete {
315                    old_parent: self.get_node_parent(&target).unwrap(),
316                    old_index: index
317                },
318            }]),
319            &inner.doc,
320        )
321    }
322
323    pub fn create(&self, parent: TreeParentId) -> LoroResult<TreeID> {
324        match parent {
325            TreeParentId::Deleted | TreeParentId::Unexist => {
326                return Err(LoroTreeError::InvalidParent.into());
327            }
328            _ => {}
329        }
330        let index: usize = self.children_num(&parent).unwrap_or(0);
331        match &self.inner {
332            MaybeDetached::Detached(t) => {
333                let t = &mut t.try_lock().unwrap().value;
334                Ok(t.create(parent.tree_id(), index))
335            }
336            MaybeDetached::Attached(a) => {
337                a.with_txn(|txn| self.create_with_txn(txn, parent, index, FiIfNotConfigured::Zero))
338            }
339        }
340    }
341
342    pub fn create_at(&self, parent: TreeParentId, index: usize) -> LoroResult<TreeID> {
343        match &self.inner {
344            MaybeDetached::Detached(t) => {
345                let t = &mut t.try_lock().unwrap().value;
346                Ok(t.create(parent.tree_id(), index))
347            }
348            MaybeDetached::Attached(a) => {
349                a.with_txn(|txn| self.create_with_txn(txn, parent, index, FiIfNotConfigured::Throw))
350            }
351        }
352    }
353
354    /// For undo/redo, Specify the TreeID of the created node
355    pub(crate) fn create_at_with_target_for_apply_diff(
356        &self,
357        parent: TreeParentId,
358        position: FractionalIndex,
359        target: TreeID,
360    ) -> LoroResult<bool> {
361        let MaybeDetached::Attached(a) = &self.inner else {
362            unreachable!();
363        };
364
365        if let Some(p) = self.get_node_parent(&target) {
366            if p == parent {
367                return Ok(false);
368                // If parent is deleted, we need to create the node, so this op from move_apply_diff
369            }
370            match p {
371                TreeParentId::Node(p) => {
372                    if !self.is_node_unexist(&target) && !self.is_node_deleted(&p)? {
373                        return self.move_at_with_target_for_apply_diff(parent, position, target);
374                    }
375                }
376                TreeParentId::Root => {
377                    return self.move_at_with_target_for_apply_diff(parent, position, target);
378                }
379                TreeParentId::Deleted | TreeParentId::Unexist => {}
380            }
381        }
382
383        let with_event = !parent
384            .tree_id()
385            .is_some_and(|p| self.is_node_deleted(&p).unwrap());
386        if !with_event {
387            return Ok(false);
388        }
389
390        // println!(
391        //     "create_at_with_target_for_apply_diff: {:?} {:?}",
392        //     target, parent
393        // );
394
395        let index = self
396            .get_index_by_fractional_index(
397                &parent,
398                &NodePosition {
399                    position: position.clone(),
400                    idlp: self.next_idlp(),
401                },
402            )
403            // TODO: parent has deleted？
404            .unwrap_or(0);
405
406        let children = a.with_txn(|txn| {
407            let inner = self.inner.try_attached_state()?;
408
409            txn.apply_local_op(
410                inner.container_idx,
411                crate::op::RawOpContent::Tree(Arc::new(TreeOp::Create {
412                    target,
413                    parent: parent.tree_id(),
414                    position: position.clone(),
415                })),
416                EventHint::Tree(smallvec![TreeDiffItem {
417                    target,
418                    action: TreeExternalDiff::Create {
419                        parent,
420                        index,
421                        position: position.clone(),
422                    },
423                }]),
424                &inner.doc,
425            )?;
426
427            Ok(self
428                .children(&TreeParentId::Node(target))
429                .unwrap_or_default())
430        })?;
431        for child in children {
432            let position = self.get_position_by_tree_id(&child).unwrap();
433            self.create_at_with_target_for_apply_diff(TreeParentId::Node(target), position, child)?;
434        }
435        Ok(true)
436    }
437
438    /// For undo/redo, Specify the TreeID of the created node
439    pub(crate) fn move_at_with_target_for_apply_diff(
440        &self,
441        parent: TreeParentId,
442        position: FractionalIndex,
443        target: TreeID,
444    ) -> LoroResult<bool> {
445        let MaybeDetached::Attached(a) = &self.inner else {
446            unreachable!();
447        };
448
449        // // the move node does not exist, create it
450        // if self.is_node_unexist(&target) || self.is_node_deleted(&target).unwrap() {
451        //     return self.create_at_with_target_for_apply_diff(parent, position, target);
452        // }
453
454        if let Some(p) = self.get_node_parent(&target) {
455            if p == parent {
456                return Ok(false);
457            }
458        }
459
460        let index = self
461            .get_index_by_fractional_index(
462                &parent,
463                &NodePosition {
464                    position: position.clone(),
465                    idlp: self.next_idlp(),
466                },
467            )
468            .unwrap_or(0);
469        let with_event = !parent
470            .tree_id()
471            .is_some_and(|p| self.is_node_deleted(&p).unwrap());
472
473        if !with_event {
474            return Ok(false);
475        }
476
477        // println!(
478        //     "move_at_with_target_for_apply_diff: {:?} {:?}",
479        //     target, parent
480        // );
481
482        a.with_txn(|txn| {
483            let inner = self.inner.try_attached_state()?;
484            txn.apply_local_op(
485                inner.container_idx,
486                crate::op::RawOpContent::Tree(Arc::new(TreeOp::Move {
487                    target,
488                    parent: parent.tree_id(),
489                    position: position.clone(),
490                })),
491                EventHint::Tree(smallvec![TreeDiffItem {
492                    target,
493                    action: TreeExternalDiff::Move {
494                        parent,
495                        index,
496                        position: position.clone(),
497                        // the old parent should be exist, so we can unwrap
498                        old_parent: self.get_node_parent(&target).unwrap(),
499                        old_index: self.get_index_by_tree_id(&target).unwrap(),
500                    },
501                }]),
502                &inner.doc,
503            )
504        })?;
505        Ok(true)
506    }
507
508    pub(crate) fn create_with_txn(
509        &self,
510        txn: &mut Transaction,
511        parent: TreeParentId,
512        index: usize,
513        cfg: FiIfNotConfigured,
514    ) -> LoroResult<TreeID> {
515        let inner = self.inner.try_attached_state()?;
516        let target = TreeID::from_id(txn.next_id());
517
518        match self.generate_position_at(&target, &parent, index, cfg) {
519            FractionalIndexGenResult::Ok(position) => {
520                self.create_with_position(inner, txn, target, parent, index, position)
521            }
522            FractionalIndexGenResult::Rearrange(ids) => {
523                for (i, (id, position)) in ids.into_iter().enumerate() {
524                    if i == 0 {
525                        self.create_with_position(inner, txn, id, parent, index, position)?;
526                        continue;
527                    }
528                    self.mov_with_position(inner, txn, id, parent, index + i, position, index + i)?;
529                }
530                Ok(target)
531            }
532            FractionalIndexGenResult::NotConfigured => {
533                Err(LoroTreeError::FractionalIndexNotEnabled.into())
534            }
535        }
536    }
537
538    pub fn mov(&self, target: TreeID, parent: TreeParentId) -> LoroResult<()> {
539        match &self.inner {
540            MaybeDetached::Detached(_) => {
541                let mut index: usize = self.children_num(&parent).unwrap_or(0);
542                if self.is_parent(&target, &parent) {
543                    index -= 1;
544                }
545                self.move_to(target, parent, index)
546            }
547            MaybeDetached::Attached(a) => {
548                let mut index: usize = self.children_num(&parent).unwrap_or(0);
549                if self.is_parent(&target, &parent) {
550                    index -= 1;
551                }
552                a.with_txn(|txn| {
553                    self.mov_with_txn(txn, target, parent, index, FiIfNotConfigured::Zero)
554                })
555            }
556        }
557    }
558
559    pub fn mov_after(&self, target: TreeID, other: TreeID) -> LoroResult<()> {
560        let parent = self
561            .get_node_parent(&other)
562            .ok_or(LoroTreeError::TreeNodeNotExist(other))?;
563        let mut index = self.get_index_by_tree_id(&other).unwrap() + 1;
564        if self.is_parent(&target, &parent) && self.get_index_by_tree_id(&target).unwrap() < index {
565            index -= 1;
566        }
567        self.move_to(target, parent, index)
568    }
569
570    pub fn mov_before(&self, target: TreeID, other: TreeID) -> LoroResult<()> {
571        let parent = self
572            .get_node_parent(&other)
573            .ok_or(LoroTreeError::TreeNodeNotExist(other))?;
574        let mut index = self.get_index_by_tree_id(&other).unwrap();
575        if self.is_parent(&target, &parent)
576            && index >= 1
577            && self.get_index_by_tree_id(&target).unwrap() < index
578        {
579            index -= 1;
580        }
581        self.move_to(target, parent, index)
582    }
583
584    pub fn move_to(&self, target: TreeID, parent: TreeParentId, index: usize) -> LoroResult<()> {
585        match &self.inner {
586            MaybeDetached::Detached(t) => {
587                let mut t = t.try_lock().unwrap();
588                t.value.mov(target, parent.tree_id(), index)
589            }
590            MaybeDetached::Attached(a) => a.with_txn(|txn| {
591                self.mov_with_txn(txn, target, parent, index, FiIfNotConfigured::Throw)
592            }),
593        }
594    }
595
596    pub(crate) fn mov_with_txn(
597        &self,
598        txn: &mut Transaction,
599        target: TreeID,
600        parent: TreeParentId,
601        index: usize,
602        cfg: FiIfNotConfigured,
603    ) -> LoroResult<()> {
604        let inner = self.inner.try_attached_state()?;
605        let mut children_len = self.children_num(&parent).unwrap_or(0);
606        let mut already_in_parent = false;
607        // check the input is valid
608        if self.is_parent(&target, &parent) {
609            // If the position after moving is same as the current position , do nothing
610            if let Some(current_index) = self.get_index_by_tree_id(&target) {
611                if current_index == index {
612                    return Ok(());
613                }
614                // move out first, we cannot delete the position here
615                // If throw error, the tree will be in a inconsistent state
616                children_len -= 1;
617                already_in_parent = true;
618            }
619        };
620        if index > children_len {
621            return Err(LoroTreeError::IndexOutOfBound {
622                len: children_len,
623                index,
624            }
625            .into());
626        }
627        let Some(old_index) = self.get_index_by_tree_id(&target) else {
628            return Err(LoroError::TreeError(
629                LoroTreeError::TreeNodeDeletedOrNotExist(target),
630            ));
631        };
632
633        if already_in_parent {
634            self.delete_position(&parent, &target);
635        }
636
637        match self.generate_position_at(&target, &parent, index, cfg) {
638            FractionalIndexGenResult::Ok(position) => {
639                self.mov_with_position(inner, txn, target, parent, index, position, old_index)
640            }
641            FractionalIndexGenResult::Rearrange(ids) => {
642                for (i, (id, position)) in ids.into_iter().enumerate() {
643                    self.mov_with_position(inner, txn, id, parent, index + i, position, old_index)?;
644                }
645                Ok(())
646            }
647            FractionalIndexGenResult::NotConfigured => {
648                Err(LoroTreeError::FractionalIndexNotEnabled.into())
649            }
650        }
651    }
652
653    #[allow(clippy::too_many_arguments)]
654    fn create_with_position(
655        &self,
656        inner: &BasicHandler,
657        txn: &mut Transaction,
658        tree_id: TreeID,
659        parent: TreeParentId,
660        index: usize,
661        position: FractionalIndex,
662    ) -> LoroResult<TreeID> {
663        txn.apply_local_op(
664            inner.container_idx,
665            crate::op::RawOpContent::Tree(Arc::new(TreeOp::Create {
666                target: tree_id,
667                parent: parent.tree_id(),
668                position: position.clone(),
669            })),
670            EventHint::Tree(smallvec![TreeDiffItem {
671                target: tree_id,
672                action: TreeExternalDiff::Create {
673                    parent,
674                    index,
675                    position,
676                },
677            }]),
678            &inner.doc,
679        )?;
680        Ok(tree_id)
681    }
682
683    #[allow(clippy::too_many_arguments)]
684    fn mov_with_position(
685        &self,
686        inner: &BasicHandler,
687        txn: &mut Transaction,
688        target: TreeID,
689        parent: TreeParentId,
690        index: usize,
691        position: FractionalIndex,
692        old_index: usize,
693    ) -> LoroResult<()> {
694        txn.apply_local_op(
695            inner.container_idx,
696            crate::op::RawOpContent::Tree(Arc::new(TreeOp::Move {
697                target,
698                parent: parent.tree_id(),
699                position: position.clone(),
700            })),
701            EventHint::Tree(smallvec![TreeDiffItem {
702                target,
703                action: TreeExternalDiff::Move {
704                    parent,
705                    index,
706                    position,
707                    old_parent: self.get_node_parent(&target).unwrap(),
708                    old_index,
709                },
710            }]),
711            &inner.doc,
712        )
713    }
714
715    pub fn get_meta(&self, target: TreeID) -> LoroResult<MapHandler> {
716        match &self.inner {
717            MaybeDetached::Detached(d) => {
718                let d = d.try_lock().unwrap();
719                d.value
720                    .map
721                    .get(&target)
722                    .cloned()
723                    .ok_or(LoroTreeError::TreeNodeNotExist(target).into())
724            }
725            MaybeDetached::Attached(a) => {
726                if self.is_node_unexist(&target) {
727                    return Err(LoroTreeError::TreeNodeNotExist(target).into());
728                }
729                let map_container_id = target.associated_meta_container();
730                let handler = create_handler(a, map_container_id);
731                Ok(handler.into_map().unwrap())
732            }
733        }
734    }
735
736    pub fn is_node_unexist(&self, target: &TreeID) -> bool {
737        match &self.inner {
738            MaybeDetached::Detached(d) => {
739                let d = d.try_lock().unwrap();
740                !d.value.map.contains_key(target)
741            }
742            MaybeDetached::Attached(a) => a.with_state(|state| {
743                let a = state.as_tree_state().unwrap();
744                a.is_node_unexist(target)
745            }),
746        }
747    }
748
749    pub fn is_node_deleted(&self, target: &TreeID) -> LoroResult<bool> {
750        match &self.inner {
751            MaybeDetached::Detached(t) => {
752                let t = t.try_lock().unwrap();
753                t.value
754                    .map
755                    .get(target)
756                    .and(Some(true))
757                    .ok_or(LoroTreeError::TreeNodeNotExist(*target).into())
758            }
759            MaybeDetached::Attached(a) => a.with_state(|state| {
760                let a = state.as_tree_state().unwrap();
761                a.is_node_deleted(target)
762                    .ok_or(LoroTreeError::TreeNodeNotExist(*target).into())
763            }),
764        }
765    }
766
767    /// Get the parent of the node, if the node does not exist, return None
768    pub fn get_node_parent(&self, target: &TreeID) -> Option<TreeParentId> {
769        match &self.inner {
770            MaybeDetached::Detached(t) => {
771                let t = t.try_lock().unwrap();
772                t.value.get_parent(target).map(TreeParentId::from)
773            }
774            MaybeDetached::Attached(a) => a.with_state(|state| {
775                let a = state.as_tree_state().unwrap();
776                a.parent(target)
777            }),
778        }
779    }
780
781    // TODO: iterator
782    pub fn children(&self, parent: &TreeParentId) -> Option<Vec<TreeID>> {
783        match &self.inner {
784            MaybeDetached::Detached(t) => {
785                let t = t.try_lock().unwrap();
786                t.value.get_children(parent.tree_id())
787            }
788            MaybeDetached::Attached(a) => a.with_state(|state| {
789                let a = state.as_tree_state().unwrap();
790                a.get_children(parent).map(|x| x.collect())
791            }),
792        }
793    }
794
795    pub fn children_num(&self, parent: &TreeParentId) -> Option<usize> {
796        match &self.inner {
797            MaybeDetached::Detached(t) => {
798                let t = t.try_lock().unwrap();
799                t.value.children_num(parent.tree_id())
800            }
801            MaybeDetached::Attached(a) => a.with_state(|state| {
802                let a = state.as_tree_state().unwrap();
803                a.children_num(parent)
804            }),
805        }
806    }
807
808    /// Check if the node is exist. include deleted node.
809    pub fn contains(&self, target: TreeID) -> bool {
810        match &self.inner {
811            MaybeDetached::Detached(t) => {
812                let t = t.try_lock().unwrap();
813                t.value.map.contains_key(&target)
814            }
815            MaybeDetached::Attached(a) => a.with_state(|state| {
816                let a = state.as_tree_state().unwrap();
817                !a.is_node_unexist(&target)
818            }),
819        }
820    }
821
822    pub fn get_child_at(&self, parent: &TreeParentId, index: usize) -> Option<TreeID> {
823        match &self.inner {
824            MaybeDetached::Detached(t) => {
825                let t = t.try_lock().unwrap();
826                t.value.get_id_by_index(&parent.tree_id(), index)
827            }
828            MaybeDetached::Attached(a) => a.with_state(|state| {
829                let a = state.as_tree_state().unwrap();
830                a.get_id_by_index(parent, index)
831            }),
832        }
833    }
834
835    pub fn is_parent(&self, target: &TreeID, parent: &TreeParentId) -> bool {
836        match &self.inner {
837            MaybeDetached::Detached(t) => {
838                let t = t.try_lock().unwrap();
839                t.value.is_parent(target, &parent.tree_id())
840            }
841            MaybeDetached::Attached(a) => a.with_state(|state| {
842                let a = state.as_tree_state().unwrap();
843                a.is_parent(target, parent)
844            }),
845        }
846    }
847
848    /// Get all nodes in the tree, including deleted nodes
849    pub fn nodes(&self) -> Vec<TreeID> {
850        match &self.inner {
851            MaybeDetached::Detached(t) => {
852                let t = t.try_lock().unwrap();
853                t.value.map.keys().cloned().collect()
854            }
855            MaybeDetached::Attached(a) => a.with_state(|state| {
856                let a = state.as_tree_state().unwrap();
857                a.nodes()
858            }),
859        }
860    }
861
862    pub fn get_nodes_under(&self, parent: TreeParentId) -> Vec<TreeNode> {
863        match &self.inner {
864            MaybeDetached::Detached(_t) => {
865                unreachable!()
866            }
867            MaybeDetached::Attached(a) => a.with_state(|state| {
868                let a = state.as_tree_state().unwrap();
869                a.get_all_tree_nodes_under(parent)
870            }),
871        }
872    }
873    pub fn roots(&self) -> Vec<TreeID> {
874        self.children(&TreeParentId::Root).unwrap_or_default()
875    }
876
877    pub fn get_all_hierarchy_nodes_under(&self, parent: TreeParentId) -> Vec<TreeNodeWithChildren> {
878        match &self.inner {
879            MaybeDetached::Detached(_t) => {
880                // TODO: implement
881                unimplemented!()
882            }
883            MaybeDetached::Attached(a) => a.with_state(|state| {
884                let a = state.as_tree_state().unwrap();
885                a.get_all_hierarchy_nodes_under(parent)
886            }),
887        }
888    }
889
890    #[allow(non_snake_case)]
891    pub fn __internal__next_tree_id(&self) -> TreeID {
892        match &self.inner {
893            MaybeDetached::Detached(d) => {
894                let d = d.try_lock().unwrap();
895                TreeID::new(PeerID::MAX, d.value.next_counter)
896            }
897            MaybeDetached::Attached(a) => a
898                .with_txn(|txn| Ok(TreeID::from_id(txn.next_id())))
899                .unwrap(),
900        }
901    }
902
903    fn generate_position_at(
904        &self,
905        target: &TreeID,
906        parent: &TreeParentId,
907        index: usize,
908        cfg: FiIfNotConfigured,
909    ) -> FractionalIndexGenResult {
910        let MaybeDetached::Attached(a) = &self.inner else {
911            unreachable!()
912        };
913        a.with_state(|state| {
914            let a = state.as_tree_state_mut().unwrap();
915            a.generate_position_at(target, parent, index, cfg)
916        })
917    }
918
919    /// Get the index of the target node in the parent node
920    ///
921    /// O(logN)
922    pub fn get_index_by_tree_id(&self, target: &TreeID) -> Option<usize> {
923        match &self.inner {
924            MaybeDetached::Detached(t) => {
925                let t = t.try_lock().unwrap();
926                t.value.get_index_by_tree_id(target)
927            }
928            MaybeDetached::Attached(a) => a.with_state(|state| {
929                let a = state.as_tree_state().unwrap();
930                a.get_index_by_tree_id(target)
931            }),
932        }
933    }
934
935    pub fn get_position_by_tree_id(&self, target: &TreeID) -> Option<FractionalIndex> {
936        match &self.inner {
937            MaybeDetached::Detached(_) => unreachable!(),
938            MaybeDetached::Attached(a) => a.with_state(|state| {
939                let a = state.as_tree_state().unwrap();
940                a.get_position(target)
941            }),
942        }
943    }
944
945    fn delete_position(&self, parent: &TreeParentId, target: &TreeID) {
946        let MaybeDetached::Attached(a) = &self.inner else {
947            unreachable!()
948        };
949        a.with_state(|state| {
950            let a = state.as_tree_state_mut().unwrap();
951            a.try_delete_position_cache(parent, target)
952        })
953    }
954
955    // use for apply diff
956    pub(crate) fn get_index_by_fractional_index(
957        &self,
958        parent: &TreeParentId,
959        node_position: &NodePosition,
960    ) -> Option<usize> {
961        match &self.inner {
962            MaybeDetached::Detached(_) => {
963                unreachable!();
964            }
965            MaybeDetached::Attached(a) => a.with_state(|state| {
966                let a = state.as_tree_state().unwrap();
967                a.get_index_by_position(parent, node_position)
968            }),
969        }
970    }
971
972    pub(crate) fn next_idlp(&self) -> IdLp {
973        match &self.inner {
974            MaybeDetached::Detached(_) => {
975                unreachable!()
976            }
977            MaybeDetached::Attached(a) => a.with_txn(|txn| Ok(txn.next_idlp())).unwrap(),
978        }
979    }
980
981    pub fn is_fractional_index_enabled(&self) -> bool {
982        match &self.inner {
983            MaybeDetached::Detached(_) => {
984                unreachable!()
985            }
986            MaybeDetached::Attached(a) => a.with_state(|state| {
987                let a = state.as_tree_state().unwrap();
988                a.is_fractional_index_enabled()
989            }),
990        }
991    }
992
993    /// Set whether to generate fractional index for Tree Position. The LoroDoc is set to use jitter 0 by default.
994    ///
995    /// The jitter is used to avoid conflicts when multiple users are creating the node at the same position.
996    /// value 0 is default, which means no jitter, any value larger than 0 will enable jitter.
997    ///
998    /// Generally speaking, jitter will affect the growth rate of document size.
999    /// [Read more about it](https://www.loro.dev/blog/movable-tree#implementation-and-encoding-size)
1000    pub fn enable_fractional_index(&self, jitter: u8) {
1001        match &self.inner {
1002            MaybeDetached::Detached(_) => {
1003                unreachable!()
1004            }
1005            MaybeDetached::Attached(a) => a.with_state(|state| {
1006                let a = state.as_tree_state_mut().unwrap();
1007                a.enable_generate_fractional_index(jitter);
1008            }),
1009        }
1010    }
1011
1012    /// Disable the fractional index generation for Tree Position when
1013    /// you don't need the Tree's siblings to be sorted. The fractional index will be always default.
1014    ///
1015    /// The LoroDoc is set to disable fractional index by default.
1016    pub fn disable_fractional_index(&self) {
1017        match &self.inner {
1018            MaybeDetached::Detached(_) => {
1019                unreachable!()
1020            }
1021            MaybeDetached::Attached(a) => a.with_state(|state| {
1022                let a = state.as_tree_state_mut().unwrap();
1023                a.disable_generate_fractional_index();
1024            }),
1025        }
1026    }
1027
1028    pub fn is_deleted(&self) -> bool {
1029        match &self.inner {
1030            MaybeDetached::Detached(_) => false,
1031            MaybeDetached::Attached(a) => a.is_deleted(),
1032        }
1033    }
1034
1035    pub fn is_empty(&self) -> bool {
1036        match &self.inner {
1037            MaybeDetached::Detached(t) => {
1038                let t = t.try_lock().unwrap();
1039                t.value.map.is_empty()
1040            }
1041            MaybeDetached::Attached(a) => a.with_state(|state| {
1042                let a = state.as_tree_state().unwrap();
1043                a.is_empty()
1044            }),
1045        }
1046    }
1047
1048    pub fn get_last_move_id(&self, target: &TreeID) -> Option<ID> {
1049        match &self.inner {
1050            MaybeDetached::Detached(_) => None,
1051            MaybeDetached::Attached(a) => a.with_state(|state| {
1052                let a = state.as_tree_state().unwrap();
1053                a.get_last_move_id(target)
1054            }),
1055        }
1056    }
1057}
loro_internal/handler/tree.rs

loro_internal/handler/
tree.rs
