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

loro_internal/handler/
tree.rs
