moduforge_model/
tree.rs

1use std::{ops::Index, sync::Arc, num::NonZeroUsize};
2use std::hash::{Hash, Hasher};
3use std::collections::hash_map::DefaultHasher;
4use im::Vector;
5use serde::{Deserialize, Serialize};
6use serde_json::Value;
7use once_cell::sync::Lazy;
8use parking_lot::RwLock;
9use lru::LruCache;
10use std::fmt::{self, Debug};
11use crate::error::PoolResult;
12use crate::node_type::NodeEnum;
13use crate::{
14    error::error_helpers,
15    mark::Mark,
16    node::Node,
17    ops::{AttrsRef, MarkRef, NodeRef},
18    types::NodeId,
19};
20
21// 全局LRU缓存用于存储NodeId到分片索引的映射
22static SHARD_INDEX_CACHE: Lazy<RwLock<LruCache<String, usize>>> =
23    Lazy::new(|| RwLock::new(LruCache::new(NonZeroUsize::new(10000).unwrap())));
24
25#[derive(Clone, PartialEq, Serialize, Deserialize)]
26pub struct Tree {
27    pub root_id: NodeId,
28    pub nodes: Vector<im::HashMap<NodeId, Arc<Node>>>, // 分片存储节点数据
29    pub parent_map: im::HashMap<NodeId, NodeId>,
30    #[serde(skip)]
31    num_shards: usize, // 缓存分片数量，避免重复计算
32}
33impl Debug for Tree {
34    fn fmt(
35        &self,
36        f: &mut fmt::Formatter<'_>,
37    ) -> fmt::Result {
38        //输出的时候 过滤掉空的 nodes 节点
39        let nodes = self
40            .nodes
41            .iter()
42            .filter(|node| !node.is_empty())
43            .collect::<Vec<_>>();
44        f.debug_struct("Tree")
45            .field("root_id", &self.root_id)
46            .field("nodes", &nodes)
47            .field("parent_map", &self.parent_map)
48            .field("num_shards", &self.num_shards)
49            .finish()
50    }
51}
52
53impl Tree {
54    #[inline]
55    pub fn get_shard_index(
56        &self,
57        id: &NodeId,
58    ) -> usize {
59        // 先检查缓存
60        {
61            let cache = SHARD_INDEX_CACHE.read();
62            if let Some(&index) = cache.peek(id) {
63                return index;
64            }
65        }
66
67        // 缓存未命中，计算哈希值
68        let mut hasher = DefaultHasher::new();
69        id.hash(&mut hasher);
70        let index = (hasher.finish() as usize) % self.num_shards;
71
72        // 更新缓存
73        {
74            let mut cache = SHARD_INDEX_CACHE.write();
75            cache.put(id.clone(), index);
76        }
77
78        index
79    }
80
81    #[inline]
82    pub fn get_shard_indices(
83        &self,
84        ids: &[&NodeId],
85    ) -> Vec<usize> {
86        ids.iter().map(|id| self.get_shard_index(id)).collect()
87    }
88
89    // 为批量操作提供优化的哈希计算
90    #[inline]
91    pub fn get_shard_index_batch<'a>(
92        &self,
93        ids: &'a [&'a NodeId],
94    ) -> Vec<(usize, &'a NodeId)> {
95        let mut results = Vec::with_capacity(ids.len());
96        let mut cache_misses = Vec::new();
97
98        // 批量检查缓存
99        {
100            let cache = SHARD_INDEX_CACHE.read();
101            for &id in ids {
102                if let Some(&index) = cache.peek(id) {
103                    results.push((index, id));
104                } else {
105                    cache_misses.push(id);
106                }
107            }
108        }
109
110        // 批量计算缓存未命中的项
111        if !cache_misses.is_empty() {
112            let mut cache = SHARD_INDEX_CACHE.write();
113            for &id in &cache_misses {
114                let mut hasher = DefaultHasher::new();
115                id.hash(&mut hasher);
116                let index = (hasher.finish() as usize) % self.num_shards;
117                cache.put(id.clone(), index);
118                results.push((index, id));
119            }
120        }
121
122        results
123    }
124
125    // 清理缓存的方法，用于内存管理
126    pub fn clear_shard_cache() {
127        let mut cache = SHARD_INDEX_CACHE.write();
128        cache.clear();
129    }
130
131    pub fn contains_node(
132        &self,
133        id: &NodeId,
134    ) -> bool {
135        let shard_index = self.get_shard_index(id);
136        self.nodes[shard_index].contains_key(id)
137    }
138
139    pub fn get_node(
140        &self,
141        id: &NodeId,
142    ) -> Option<Arc<Node>> {
143        let shard_index = self.get_shard_index(id);
144        self.nodes[shard_index].get(id).cloned()
145    }
146
147    pub fn get_parent_node(
148        &self,
149        id: &NodeId,
150    ) -> Option<Arc<Node>> {
151        self.parent_map.get(id).and_then(|parent_id| {
152            let shard_index = self.get_shard_index(parent_id);
153            self.nodes[shard_index].get(parent_id).cloned()
154        })
155    }
156    pub fn from(nodes: NodeEnum) -> Self {
157        let num_shards = std::cmp::max(
158            std::thread::available_parallelism()
159                .map(NonZeroUsize::get)
160                .unwrap_or(2),
161            2,
162        );
163        let mut shards = Vector::from(vec![im::HashMap::new(); num_shards]);
164        let mut parent_map = im::HashMap::new();
165        let (root_node, children) = nodes.into_parts();
166        let root_id = root_node.id.clone();
167
168        let mut hasher = DefaultHasher::new();
169        root_id.hash(&mut hasher);
170        let shard_index = (hasher.finish() as usize) % num_shards;
171        shards[shard_index] =
172            shards[shard_index].update(root_id.clone(), Arc::new(root_node));
173
174        fn process_children(
175            children: Vec<NodeEnum>,
176            parent_id: &NodeId,
177            shards: &mut Vector<im::HashMap<NodeId, Arc<Node>>>,
178            parent_map: &mut im::HashMap<NodeId, NodeId>,
179            num_shards: usize,
180        ) {
181            for child in children {
182                let (node, grand_children) = child.into_parts();
183                let node_id = node.id.clone();
184                let mut hasher = DefaultHasher::new();
185                node_id.hash(&mut hasher);
186                let shard_index = (hasher.finish() as usize) % num_shards;
187                shards[shard_index] =
188                    shards[shard_index].update(node_id.clone(), Arc::new(node));
189                parent_map.insert(node_id.clone(), parent_id.clone());
190
191                // Recursively process grand children
192                process_children(
193                    grand_children,
194                    &node_id,
195                    shards,
196                    parent_map,
197                    num_shards,
198                );
199            }
200        }
201
202        process_children(
203            children,
204            &root_id,
205            &mut shards,
206            &mut parent_map,
207            num_shards,
208        );
209
210        Self { root_id, nodes: shards, parent_map, num_shards }
211    }
212
213    pub fn new(root: Node) -> Self {
214        let num_shards = std::cmp::max(
215            std::thread::available_parallelism()
216                .map(NonZeroUsize::get)
217                .unwrap_or(2),
218            2,
219        );
220        let mut nodes = Vector::from(vec![im::HashMap::new(); num_shards]);
221        let root_id = root.id.clone();
222        let mut hasher = DefaultHasher::new();
223        root_id.hash(&mut hasher);
224        let shard_index = (hasher.finish() as usize) % num_shards;
225        nodes[shard_index] =
226            nodes[shard_index].update(root_id.clone(), Arc::new(root));
227        Self { root_id, nodes, parent_map: im::HashMap::new(), num_shards }
228    }
229
230    pub fn update_attr(
231        &mut self,
232        id: &NodeId,
233        new_values: im::HashMap<String, Value>,
234    ) -> PoolResult<()> {
235        let shard_index = self.get_shard_index(id);
236        let node = self.nodes[shard_index]
237            .get(id)
238            .ok_or(error_helpers::node_not_found(id.clone()))?;
239        let old_values = node.attrs.clone();
240        let mut new_node = node.as_ref().clone();
241        let new_attrs = old_values.update(new_values);
242        new_node.attrs = new_attrs.clone();
243        self.nodes[shard_index] =
244            self.nodes[shard_index].update(id.clone(), Arc::new(new_node));
245        Ok(())
246    }
247    pub fn update_node(
248        &mut self,
249        node: Node,
250    ) -> PoolResult<()> {
251        let shard_index = self.get_shard_index(&node.id);
252        self.nodes[shard_index] =
253            self.nodes[shard_index].update(node.id.clone(), Arc::new(node));
254        Ok(())
255    }
256
257    /// 向树中添加新的节点及其子节点
258    ///
259    /// # 参数
260    /// * `nodes` - 要添加的节点枚举，包含节点本身及其子节点
261    ///
262    /// # 返回值
263    /// * `Result<(), PoolError>` - 如果添加成功返回 Ok(()), 否则返回错误
264    ///
265    /// # 错误
266    /// * `PoolError::ParentNotFound` - 如果父节点不存在
267    pub fn add(
268        &mut self,
269        parent_id: &NodeId,
270        nodes: Vec<NodeEnum>,
271    ) -> PoolResult<()> {
272        // 检查父节点是否存在
273        let parent_shard_index = self.get_shard_index(&parent_id);
274        let parent_node = self.nodes[parent_shard_index]
275            .get(parent_id)
276            .ok_or(error_helpers::parent_not_found(parent_id.clone()))?;
277        let mut new_parent = parent_node.as_ref().clone();
278
279        // 收集所有子节点的ID并添加到当前节点的content中
280        let zenliang: Vector<String> =
281            nodes.iter().map(|n| n.0.id.clone()).collect();
282        // 需要判断 new_parent.content 中是否已经存在 zenliang 中的节点
283        let mut new_content = im::Vector::new();
284        for id in zenliang {
285            if !new_parent.content.contains(&id) {
286                new_content.push_back(id);
287            }
288        }
289        new_parent.content.extend(new_content);
290
291        // 更新当前节点
292        self.nodes[parent_shard_index] = self.nodes[parent_shard_index]
293            .update(parent_id.clone(), Arc::new(new_parent));
294
295        // 使用队列进行广度优先遍历，处理所有子节点
296        let mut node_queue = Vec::new();
297        node_queue.push((nodes, parent_id.clone()));
298        while let Some((current_children, current_parent_id)) = node_queue.pop()
299        {
300            for child in current_children {
301                // 处理每个子节点
302                let (mut child_node, grand_children) = child.into_parts();
303                let current_node_id = child_node.id.clone();
304
305                // 收集孙节点的ID并添加到子节点的content中
306                let grand_children_ids: Vector<String> =
307                    grand_children.iter().map(|n| n.0.id.clone()).collect();
308                let mut new_content = im::Vector::new();
309                for id in grand_children_ids {
310                    if !child_node.content.contains(&id) {
311                        new_content.push_back(id);
312                    }
313                }
314                child_node.content.extend(new_content);
315
316                // 将当前节点存储到对应的分片中
317                let shard_index = self.get_shard_index(&current_node_id);
318                self.nodes[shard_index] = self.nodes[shard_index]
319                    .update(current_node_id.clone(), Arc::new(child_node));
320
321                // 更新父子关系映射
322                self.parent_map
323                    .insert(current_node_id.clone(), current_parent_id.clone());
324
325                // 将孙节点加入队列，以便后续处理
326                node_queue.push((grand_children, current_node_id.clone()));
327            }
328        }
329        Ok(())
330    }
331    // 添加到下标
332    pub fn add_at_index(
333        &mut self,
334        parent_id: &NodeId,
335        index: usize,
336        node: &Node,
337    ) -> PoolResult<()> {
338        //添加到节点到 parent_id 的 content 中
339        let parent_shard_index = self.get_shard_index(parent_id);
340        let parent = self.nodes[parent_shard_index]
341            .get(parent_id)
342            .ok_or(error_helpers::parent_not_found(parent_id.clone()))?;
343        let mut new_parent = parent.as_ref().clone();
344        new_parent.content.insert(index, node.id.clone());
345        self.nodes[parent_shard_index] = self.nodes[parent_shard_index]
346            .update(parent_id.clone(), Arc::new(new_parent));
347        self.parent_map.insert(node.id.clone(), parent_id.clone());
348        Ok(())
349    }
350    pub fn add_node(
351        &mut self,
352        parent_id: &NodeId,
353        nodes: &Vec<Node>,
354    ) -> PoolResult<()> {
355        let parent_shard_index = self.get_shard_index(parent_id);
356        let parent = self.nodes[parent_shard_index]
357            .get(parent_id)
358            .ok_or(error_helpers::parent_not_found(parent_id.clone()))?;
359        let mut new_parent = parent.as_ref().clone();
360        new_parent.content.push_back(nodes[0].id.clone());
361        self.nodes[parent_shard_index] = self.nodes[parent_shard_index]
362            .update(parent_id.clone(), Arc::new(new_parent));
363        self.parent_map.insert(nodes[0].id.clone(), parent_id.clone());
364        for node in nodes {
365            let shard_index = self.get_shard_index(&node.id);
366            for child_id in &node.content {
367                self.parent_map.insert(child_id.clone(), node.id.clone());
368            }
369            self.nodes[shard_index] = self.nodes[shard_index]
370                .update(node.id.clone(), Arc::new(node.clone()));
371        }
372        Ok(())
373    }
374
375    pub fn node(
376        &mut self,
377        key: &str,
378    ) -> NodeRef<'_> {
379        NodeRef::new(self, key.to_string())
380    }
381    pub fn mark(
382        &mut self,
383        key: &str,
384    ) -> MarkRef<'_> {
385        MarkRef::new(self, key.to_string())
386    }
387    pub fn attrs(
388        &mut self,
389        key: &str,
390    ) -> AttrsRef<'_> {
391        AttrsRef::new(self, key.to_string())
392    }
393
394    pub fn children(
395        &self,
396        parent_id: &NodeId,
397    ) -> Option<im::Vector<NodeId>> {
398        self.get_node(parent_id).map(|n| n.content.clone())
399    }
400
401    pub fn children_node(
402        &self,
403        parent_id: &NodeId,
404    ) -> Option<im::Vector<Arc<Node>>> {
405        self.children(parent_id)
406            .map(|ids| ids.iter().filter_map(|id| self.get_node(id)).collect())
407    }
408    //递归获取所有子节点 封装成 NodeEnum 返回
409    pub fn all_children(
410        &self,
411        parent_id: &NodeId,
412        filter: Option<&dyn Fn(&Node) -> bool>,
413    ) -> Option<NodeEnum> {
414        if let Some(node) = self.get_node(parent_id) {
415            let mut child_enums = Vec::new();
416            for child_id in &node.content {
417                if let Some(child_node) = self.get_node(child_id) {
418                    // 检查子节点是否满足过滤条件
419                    if let Some(filter_fn) = filter {
420                        if !filter_fn(child_node.as_ref()) {
421                            continue; // 跳过不满足条件的子节点
422                        }
423                    }
424                    // 递归处理满足条件的子节点
425                    if let Some(child_enum) =
426                        self.all_children(child_id, filter)
427                    {
428                        child_enums.push(child_enum);
429                    }
430                }
431            }
432            Some(NodeEnum(node.as_ref().clone(), child_enums))
433        } else {
434            None
435        }
436    }
437
438    pub fn children_count(
439        &self,
440        parent_id: &NodeId,
441    ) -> usize {
442        self.get_node(parent_id).map(|n| n.content.len()).unwrap_or(0)
443    }
444    pub fn remove_mark_by_name(
445        &mut self,
446        id: &NodeId,
447        mark_name: &str,
448    ) -> PoolResult<()> {
449        let shard_index = self.get_shard_index(id);
450        let node = self.nodes[shard_index]
451            .get(id)
452            .ok_or(error_helpers::node_not_found(id.clone()))?;
453        let mut new_node = node.as_ref().clone();
454        new_node.marks = new_node
455            .marks
456            .iter()
457            .filter(|&m| m.r#type != mark_name)
458            .cloned()
459            .collect();
460        self.nodes[shard_index] =
461            self.nodes[shard_index].update(id.clone(), Arc::new(new_node));
462        Ok(())
463    }
464    pub fn get_marks(
465        &self,
466        id: &NodeId,
467    ) -> Option<im::Vector<Mark>> {
468        self.get_node(id).map(|n| n.marks.clone())
469    }
470
471    pub fn remove_mark(
472        &mut self,
473        id: &NodeId,
474        mark_types: &[String],
475    ) -> PoolResult<()> {
476        let shard_index = self.get_shard_index(id);
477        let node = self.nodes[shard_index]
478            .get(id)
479            .ok_or(error_helpers::node_not_found(id.clone()))?;
480        let mut new_node = node.as_ref().clone();
481        new_node.marks =
482            new_node.marks.iter().filter(|&m| !mark_types.contains(&m.r#type)).cloned().collect();
483        self.nodes[shard_index] =
484            self.nodes[shard_index].update(id.clone(), Arc::new(new_node));
485        Ok(())
486    }
487
488    pub fn add_mark(
489        &mut self,
490        id: &NodeId,
491        marks: &Vec<Mark>,
492    ) -> PoolResult<()> {
493        let shard_index = self.get_shard_index(id);
494        let node = self.nodes[shard_index]
495            .get(id)
496            .ok_or(error_helpers::node_not_found(id.clone()))?;
497        let mut new_node = node.as_ref().clone();
498        //如果存在相同类型的mark，则覆盖
499        let mark_types = marks.iter().map(|m| m.r#type.clone()).collect::<Vec<String>>();
500        new_node.marks = new_node.marks.iter().filter(|m| !mark_types.contains(&m.r#type)).cloned().collect();
501        new_node.marks.extend(marks.iter().map(|m| m.clone()));
502        self.nodes[shard_index] =
503            self.nodes[shard_index].update(id.clone(), Arc::new(new_node));
504        Ok(())
505    }
506
507    pub fn move_node(
508        &mut self,
509        source_parent_id: &NodeId,
510        target_parent_id: &NodeId,
511        node_id: &NodeId,
512        position: Option<usize>,
513    ) -> PoolResult<()> {
514        let source_shard_index = self.get_shard_index(source_parent_id);
515        let target_shard_index = self.get_shard_index(target_parent_id);
516        let node_shard_index = self.get_shard_index(node_id);
517        let source_parent = self.nodes[source_shard_index]
518            .get(source_parent_id)
519            .ok_or(error_helpers::parent_not_found(source_parent_id.clone()))?;
520        let target_parent = self.nodes[target_shard_index]
521            .get(target_parent_id)
522            .ok_or(error_helpers::parent_not_found(target_parent_id.clone()))?;
523        let _node = self.nodes[node_shard_index]
524            .get(node_id)
525            .ok_or(error_helpers::node_not_found(node_id.clone()))?;
526        if !source_parent.content.contains(node_id) {
527            return Err(error_helpers::invalid_parenting(
528                node_id.clone(),
529                source_parent_id.clone(),
530            ));
531        }
532        let mut new_source_parent = source_parent.as_ref().clone();
533        new_source_parent.content = new_source_parent
534            .content
535            .iter()
536            .filter(|&id| id != node_id)
537            .cloned()
538            .collect();
539        let mut new_target_parent = target_parent.as_ref().clone();
540        if let Some(pos) = position {
541            // 确保position不超过当前content的长度
542            let insert_pos = pos.min(new_target_parent.content.len());
543
544            if insert_pos == new_target_parent.content.len() {
545                // 在末尾插入
546                new_target_parent.content.push_back(node_id.clone());
547            } else {
548                // 在指定位置插入
549                let mut new_content = im::Vector::new();
550
551                // 添加position之前的所有元素
552                for (i, child_id) in
553                    new_target_parent.content.iter().enumerate()
554                {
555                    if i == insert_pos {
556                        // 在这个位置插入新节点
557                        new_content.push_back(node_id.clone());
558                    }
559                    new_content.push_back(child_id.clone());
560                }
561
562                new_target_parent.content = new_content;
563            }
564        } else {
565            // 没有指定位置，添加到末尾
566            new_target_parent.content.push_back(node_id.clone());
567        }
568        self.nodes[source_shard_index] = self.nodes[source_shard_index]
569            .update(source_parent_id.clone(), Arc::new(new_source_parent));
570        self.nodes[target_shard_index] = self.nodes[target_shard_index]
571            .update(target_parent_id.clone(), Arc::new(new_target_parent));
572        self.parent_map.insert(node_id.clone(), target_parent_id.clone());
573        Ok(())
574    }
575
576    pub fn remove_node(
577        &mut self,
578        parent_id: &NodeId,
579        nodes: Vec<NodeId>,
580    ) -> PoolResult<()> {
581        let parent_shard_index = self.get_shard_index(parent_id);
582        let parent = self.nodes[parent_shard_index]
583            .get(parent_id)
584            .ok_or(error_helpers::parent_not_found(parent_id.clone()))?;
585        if nodes.contains(&self.root_id) {
586            return Err(error_helpers::cannot_remove_root());
587        }
588        for node_id in &nodes {
589            if !parent.content.contains(node_id) {
590                return Err(error_helpers::invalid_parenting(
591                    node_id.clone(),
592                    parent_id.clone(),
593                ));
594            }
595        }
596        let nodes_to_remove: std::collections::HashSet<_> =
597            nodes.iter().collect();
598        let filtered_children: im::Vector<NodeId> = parent
599            .as_ref()
600            .content
601            .iter()
602            .filter(|&id| !nodes_to_remove.contains(id))
603            .cloned()
604            .collect();
605        let mut parent_node = parent.as_ref().clone();
606        parent_node.content = filtered_children;
607        self.nodes[parent_shard_index] = self.nodes[parent_shard_index]
608            .update(parent_id.clone(), Arc::new(parent_node));
609        let mut remove_nodes = Vec::new();
610        for node_id in nodes {
611            self.remove_subtree(&node_id, &mut remove_nodes)?;
612        }
613        Ok(())
614    }
615    //=删除节点
616    pub fn remove_node_by_id(
617        &mut self,
618        node_id: &NodeId,
619    ) -> PoolResult<()> {
620        // 检查是否试图删除根节点
621        if node_id == &self.root_id {
622            return Err(error_helpers::cannot_remove_root());
623        }
624
625        let shard_index = self.get_shard_index(node_id);
626        let _ = self.nodes[shard_index]
627            .get(node_id)
628            .ok_or(error_helpers::node_not_found(node_id.clone()))?;
629
630        // 从父节点的content中移除该节点
631        if let Some(parent_id) = self.parent_map.get(node_id).cloned() {
632            let parent_shard_index = self.get_shard_index(&parent_id);
633            if let Some(parent_node) =
634                self.nodes[parent_shard_index].get(&parent_id)
635            {
636                let mut new_parent = parent_node.as_ref().clone();
637                new_parent.content = new_parent
638                    .content
639                    .iter()
640                    .filter(|&id| id != node_id)
641                    .cloned()
642                    .collect();
643                self.nodes[parent_shard_index] = self.nodes[parent_shard_index]
644                    .update(parent_id.clone(), Arc::new(new_parent));
645            }
646        }
647
648        // 删除子树（remove_subtree内部已经处理了节点的删除和parent_map的清理）
649        let mut remove_nodes = Vec::new();
650        self.remove_subtree(node_id, &mut remove_nodes)?;
651
652        // remove_subtree已经删除了所有节点，包括node_id本身，所以这里不需要再次删除
653        Ok(())
654    }
655
656    ///根据下标删除
657    pub fn remove_node_by_index(
658        &mut self,
659        parent_id: &NodeId,
660        index: usize,
661    ) -> PoolResult<()> {
662        let shard_index = self.get_shard_index(parent_id);
663        let parent = self.nodes[shard_index]
664            .get(parent_id)
665            .ok_or(error_helpers::parent_not_found(parent_id.clone()))?;
666        let mut new_parent = parent.as_ref().clone();
667        let remove_node_id = new_parent.content.remove(index);
668        self.nodes[shard_index] = self.nodes[shard_index]
669            .update(parent_id.clone(), Arc::new(new_parent));
670        let mut remove_nodes = Vec::new();
671        self.remove_subtree(&remove_node_id, &mut remove_nodes)?;
672        for node in remove_nodes {
673            let shard_index = self.get_shard_index(&node.id);
674            self.nodes[shard_index].remove(&node.id);
675            self.parent_map.remove(&node.id);
676        }
677        Ok(())
678    }
679
680    //删除子树
681    fn remove_subtree(
682        &mut self,
683        node_id: &NodeId,
684        remove_nodes: &mut Vec<Node>,
685    ) -> PoolResult<()> {
686        if node_id == &self.root_id {
687            return Err(error_helpers::cannot_remove_root());
688        }
689        let shard_index = self.get_shard_index(node_id);
690        let _ = self.nodes[shard_index]
691            .get(node_id)
692            .ok_or(error_helpers::node_not_found(node_id.clone()))?;
693        if let Some(children) = self.children(node_id) {
694            for child_id in children {
695                self.remove_subtree(&child_id, remove_nodes)?;
696            }
697        }
698        self.parent_map.remove(node_id);
699        if let Some(remove_node) = self.nodes[shard_index].remove(node_id) {
700            remove_nodes.push(remove_node.as_ref().clone());
701        }
702        Ok(())
703    }
704}
705
706impl Index<&NodeId> for Tree {
707    type Output = Arc<Node>;
708    fn index(
709        &self,
710        index: &NodeId,
711    ) -> &Self::Output {
712        let shard_index = self.get_shard_index(index);
713        self.nodes[shard_index].get(index).expect("Node not found")
714    }
715}
716
717impl Index<&str> for Tree {
718    type Output = Arc<Node>;
719    fn index(
720        &self,
721        index: &str,
722    ) -> &Self::Output {
723        let node_id = NodeId::from(index);
724        let shard_index = self.get_shard_index(&node_id);
725        self.nodes[shard_index].get(&node_id).expect("Node not found")
726    }
727}
728
729#[cfg(test)]
730mod tests {
731    use super::*;
732    use crate::node::Node;
733    use crate::node_type::NodeEnum;
734    use crate::types::NodeId;
735    use crate::attrs::Attrs;
736    use crate::mark::Mark;
737    use im::HashMap;
738    use serde_json::json;
739
740    fn create_test_node(id: &str) -> Node {
741        Node::new(id, "test".to_string(), Attrs::default(), vec![], vec![])
742    }
743
744    #[test]
745    fn test_tree_creation() {
746        let root = create_test_node("root");
747        let tree = Tree::new(root.clone());
748        assert_eq!(tree.root_id, root.id);
749        assert!(tree.contains_node(&root.id));
750    }
751
752    #[test]
753    fn test_add_node() {
754        let root = create_test_node("root");
755        let mut tree = Tree::new(root.clone());
756
757        let child = create_test_node("child");
758        let nodes = vec![child.clone()];
759
760        tree.add_node(&root.id, &nodes).unwrap();
761        dbg!(&tree);
762        assert!(tree.contains_node(&child.id));
763        assert_eq!(tree.children(&root.id).unwrap().len(), 1);
764    }
765
766    #[test]
767    fn test_remove_node() {
768        let root = create_test_node("root");
769        let mut tree = Tree::new(root.clone());
770
771        let child = create_test_node("child");
772        let nodes = vec![child.clone()];
773
774        tree.add_node(&root.id, &nodes).unwrap();
775        dbg!(&tree);
776        tree.remove_node(&root.id, vec![child.id.clone()]).unwrap();
777        dbg!(&tree);
778        assert!(!tree.contains_node(&child.id));
779        assert_eq!(tree.children(&root.id).unwrap().len(), 0);
780    }
781
782    #[test]
783    fn test_move_node() {
784        // 创建两个父节点
785        let parent1 = create_test_node("parent1");
786        let parent2 = create_test_node("parent2");
787        let mut tree = Tree::new(parent1.clone());
788
789        // 将 parent2 添加为 parent1 的子节点
790        tree.add_node(&parent1.id, &vec![parent2.clone()]).unwrap();
791
792        // 创建三个子节点
793        let child1 = create_test_node("child1");
794        let child2 = create_test_node("child2");
795        let child3 = create_test_node("child3");
796
797        // 将所有子节点添加到 parent1 下
798        tree.add_node(&parent1.id, &vec![child1.clone()]).unwrap();
799        tree.add_node(&parent1.id, &vec![child2.clone()]).unwrap();
800        tree.add_node(&parent1.id, &vec![child3.clone()]).unwrap();
801
802        // 验证初始状态
803        let parent1_children = tree.children(&parent1.id).unwrap();
804        assert_eq!(parent1_children.len(), 4); // parent2 + 3 children
805        assert_eq!(parent1_children[0], parent2.id);
806        assert_eq!(parent1_children[1], child1.id);
807        assert_eq!(parent1_children[2], child2.id);
808        assert_eq!(parent1_children[3], child3.id);
809
810        // 将 child1 移动到 parent2 下
811        tree.move_node(&parent1.id, &parent2.id, &child1.id, None).unwrap();
812
813        // 验证移动后的状态
814        let parent1_children = tree.children(&parent1.id).unwrap();
815        let parent2_children = tree.children(&parent2.id).unwrap();
816        assert_eq!(parent1_children.len(), 3); // parent2 + 2 children
817        assert_eq!(parent2_children.len(), 1); // child1
818        assert_eq!(parent2_children[0], child1.id);
819
820        // 将 child2 移动到 parent2 下，放在 child1 后面
821        tree.move_node(&parent1.id, &parent2.id, &child2.id, Some(1)).unwrap();
822
823        // 验证最终状态
824        let parent1_children = tree.children(&parent1.id).unwrap();
825        let parent2_children = tree.children(&parent2.id).unwrap();
826        assert_eq!(parent1_children.len(), 2); // parent2 + 1 child
827        assert_eq!(parent2_children.len(), 2); // child1 + child2
828        assert_eq!(parent2_children[0], child1.id);
829        assert_eq!(parent2_children[1], child2.id);
830
831        // 验证父节点关系
832        let child1_parent = tree.get_parent_node(&child1.id).unwrap();
833        let child2_parent = tree.get_parent_node(&child2.id).unwrap();
834        assert_eq!(child1_parent.id, parent2.id);
835        assert_eq!(child2_parent.id, parent2.id);
836    }
837
838    #[test]
839    fn test_update_attr() {
840        let root = create_test_node("root");
841        let mut tree = Tree::new(root.clone());
842
843        let mut attrs = HashMap::new();
844        attrs.insert("key".to_string(), json!("value"));
845
846        tree.update_attr(&root.id, attrs).unwrap();
847
848        let node = tree.get_node(&root.id).unwrap();
849        dbg!(&node);
850        assert_eq!(node.attrs.get("key").unwrap(), &json!("value"));
851    }
852
853    #[test]
854    fn test_add_mark() {
855        let root = create_test_node("root");
856        let mut tree = Tree::new(root.clone());
857
858        let mark = Mark { r#type: "test".to_string(), attrs: Attrs::default() };
859        tree.add_mark(&root.id, &vec![mark.clone()]).unwrap();
860        dbg!(&tree);
861        let node = tree.get_node(&root.id).unwrap();
862        assert!(node.marks.contains(&mark));
863    }
864
865    #[test]
866    fn test_remove_mark() {
867        let root = create_test_node("root");
868        let mut tree = Tree::new(root.clone());
869
870        let mark = Mark { r#type: "test".to_string(), attrs: Attrs::default() };
871        tree.add_mark(&root.id, &vec![mark.clone()]).unwrap();
872        dbg!(&tree);
873        tree.remove_mark(&root.id, &[mark.r#type.clone()]).unwrap();
874        dbg!(&tree);
875        let node = tree.get_node(&root.id).unwrap();
876        assert!(!node.marks.iter().any(|m| m.r#type == mark.r#type));
877    }
878
879    #[test]
880    fn test_all_children() {
881        let root = create_test_node("root");
882        let mut tree = Tree::new(root.clone());
883
884        let child1 = create_test_node("child1");
885        let child2 = create_test_node("child2");
886
887        tree.add_node(&root.id, &vec![child1.clone()]).unwrap();
888        tree.add_node(&root.id, &vec![child2.clone()]).unwrap();
889        dbg!(&tree);
890        let all_children = tree.all_children(&root.id, None).unwrap();
891        assert_eq!(all_children.1.len(), 2);
892    }
893
894    #[test]
895    fn test_children_count() {
896        let root = create_test_node("root");
897        let mut tree = Tree::new(root.clone());
898
899        let child1 = create_test_node("child1");
900        let child2 = create_test_node("child2");
901
902        tree.add_node(&root.id, &vec![child1.clone()]).unwrap();
903        tree.add_node(&root.id, &vec![child2.clone()]).unwrap();
904
905        assert_eq!(tree.children_count(&root.id), 2);
906    }
907
908    #[test]
909    fn test_remove_node_by_id_updates_parent() {
910        let root = create_test_node("root");
911        let mut tree = Tree::new(root.clone());
912
913        let child = create_test_node("child");
914        tree.add_node(&root.id, &vec![child.clone()]).unwrap();
915
916        // 验证子节点被添加
917        assert_eq!(tree.children_count(&root.id), 1);
918        assert!(tree.contains_node(&child.id));
919
920        // 删除子节点
921        tree.remove_node_by_id(&child.id).unwrap();
922
923        // 验证子节点被删除且父节点的content被更新
924        assert_eq!(tree.children_count(&root.id), 0);
925        assert!(!tree.contains_node(&child.id));
926    }
927
928    #[test]
929    fn test_move_node_position_edge_cases() {
930        let root = create_test_node("root");
931        let mut tree = Tree::new(root.clone());
932
933        let container = create_test_node("container");
934        tree.add_node(&root.id, &vec![container.clone()]).unwrap();
935
936        let child1 = create_test_node("child1");
937        let child2 = create_test_node("child2");
938        let child3 = create_test_node("child3");
939
940        tree.add_node(&root.id, &vec![child1.clone()]).unwrap();
941        tree.add_node(&root.id, &vec![child2.clone()]).unwrap();
942        tree.add_node(&root.id, &vec![child3.clone()]).unwrap();
943
944        // 测试移动到超出范围的位置（应该插入到末尾）
945        tree.move_node(&root.id, &container.id, &child1.id, Some(100)).unwrap();
946
947        let container_children = tree.children(&container.id).unwrap();
948        assert_eq!(container_children.len(), 1);
949        assert_eq!(container_children[0], child1.id);
950
951        // 测试移动到位置0
952        tree.move_node(&root.id, &container.id, &child2.id, Some(0)).unwrap();
953
954        let container_children = tree.children(&container.id).unwrap();
955        assert_eq!(container_children.len(), 2);
956        assert_eq!(container_children[0], child2.id);
957        assert_eq!(container_children[1], child1.id);
958    }
959
960    #[test]
961    fn test_cannot_remove_root_node() {
962        let root = create_test_node("root");
963        let mut tree = Tree::new(root.clone());
964
965        // 尝试删除根节点应该失败
966        let result = tree.remove_node_by_id(&root.id);
967        assert!(result.is_err());
968    }
969
970    #[test]
971    fn test_get_parent_node() {
972        let root = create_test_node("root");
973        let mut tree = Tree::new(root.clone());
974
975        let child = create_test_node("child");
976        tree.add_node(&root.id, &vec![child.clone()]).unwrap();
977
978        let parent = tree.get_parent_node(&child.id).unwrap();
979        assert_eq!(parent.id, root.id);
980    }
981}
moduforge_model/tree.rs

moduforge_model/
tree.rs
