1use std::cell::RefCell;
40use std::rc::Rc;
41
42use slotmap::SlotMap;
43
44use teksilo_core::ObserverHandle;
45
46use crate::tree_change::{NodeId, TreeChange};
47
48struct TreeNode<T> {
49 data: T,
50 parent: Option<NodeId>,
51 children: Vec<NodeId>,
52}
53
54struct TreeObserverEntry {
55 id: u64,
56 callback: Rc<dyn Fn(&TreeChange)>,
57}
58
59struct TreeModelInner<T> {
60 arena: SlotMap<slotmap::DefaultKey, TreeNode<T>>,
61 roots: Vec<NodeId>,
62 observers: Vec<TreeObserverEntry>,
63 next_observer_id: u64,
64 #[cfg(debug_assertions)]
70 debug_adapter: Option<Rc<dyn crate::debug_registry::ModelDebug>>,
71}
72
73pub struct TreeModel<T: 'static> {
81 inner: Rc<RefCell<TreeModelInner<T>>>,
82}
83
84impl<T: 'static> TreeModel<T> {
85 pub fn new() -> Self {
87 Self {
88 inner: Rc::new(RefCell::new(TreeModelInner {
89 arena: SlotMap::new(),
90 roots: Vec::new(),
91 observers: Vec::new(),
92 next_observer_id: 1,
93 #[cfg(debug_assertions)]
94 debug_adapter: None,
95 })),
96 }
97 }
98
99 pub fn root_count(&self) -> usize {
103 self.inner.borrow().roots.len()
104 }
105
106 pub fn root(&self, index: usize) -> NodeId {
111 self.inner.borrow().roots[index]
112 }
113
114 pub fn child_count(&self, parent: NodeId) -> usize {
116 let guard = self.inner.borrow();
117 guard
118 .arena
119 .get(parent.key())
120 .map(|n| n.children.len())
121 .unwrap_or(0)
122 }
123
124 pub fn child(&self, parent: NodeId, index: usize) -> NodeId {
129 let guard = self.inner.borrow();
130 guard.arena[parent.key()].children[index]
131 }
132
133 pub fn parent(&self, node: NodeId) -> Option<NodeId> {
135 let guard = self.inner.borrow();
136 guard.arena.get(node.key()).and_then(|n| n.parent)
137 }
138
139 pub fn depth(&self, node: NodeId) -> usize {
141 let guard = self.inner.borrow();
142 let mut depth = 0;
143 let mut current = guard.arena.get(node.key()).and_then(|n| n.parent);
144 while let Some(pid) = current {
145 depth += 1;
146 current = guard.arena.get(pid.key()).and_then(|n| n.parent);
147 }
148 depth
149 }
150
151 pub fn has_children(&self, node: NodeId) -> bool {
153 self.child_count(node) > 0
154 }
155
156 pub fn children(&self, node: NodeId) -> Vec<NodeId> {
158 let guard = self.inner.borrow();
159 guard
160 .arena
161 .get(node.key())
162 .map(|n| n.children.clone())
163 .unwrap_or_default()
164 }
165
166 pub fn with_item<R>(&self, node: NodeId, f: impl FnOnce(&T) -> R) -> Option<R> {
168 let guard = self.inner.borrow();
169 guard.arena.get(node.key()).map(|n| f(&n.data))
170 }
171
172 pub fn find_by(&self, predicate: impl Fn(&T) -> bool) -> Option<NodeId> {
174 let guard = self.inner.borrow();
175 let mut stack: Vec<NodeId> = guard.roots.iter().rev().copied().collect();
176 while let Some(nid) = stack.pop() {
177 if let Some(node) = guard.arena.get(nid.key()) {
178 if predicate(&node.data) {
179 return Some(nid);
180 }
181 for &child_id in node.children.iter().rev() {
182 stack.push(child_id);
183 }
184 }
185 }
186 None
187 }
188
189 pub fn insert_root(&self, index: usize, item: T) -> NodeId {
196 let node_id = {
197 let mut guard = self.inner.borrow_mut();
198 let key = guard.arena.insert(TreeNode {
199 data: item,
200 parent: None,
201 children: Vec::new(),
202 });
203 let node_id = NodeId::from_key(key);
204 guard.roots.insert(index, node_id);
205 node_id
206 };
207 self.notify(TreeChange::NodeInserted {
208 parent: None,
209 index,
210 node: node_id,
211 });
212 node_id
213 }
214
215 pub fn insert_child(&self, parent: NodeId, index: usize, item: T) -> NodeId {
220 let node_id = {
221 let mut guard = self.inner.borrow_mut();
222 let key = guard.arena.insert(TreeNode {
223 data: item,
224 parent: Some(parent),
225 children: Vec::new(),
226 });
227 let node_id = NodeId::from_key(key);
228 guard.arena[parent.key()].children.insert(index, node_id);
229 node_id
230 };
231 self.notify(TreeChange::NodeInserted {
232 parent: Some(parent),
233 index,
234 node: node_id,
235 });
236 node_id
237 }
238
239 pub fn remove(&self, node: NodeId) {
244 let parent = {
245 let mut guard = self.inner.borrow_mut();
246 let parent = guard.arena[node.key()].parent;
247 if let Some(pid) = parent {
249 guard.arena[pid.key()].children.retain(|&c| c != node);
250 } else {
251 guard.roots.retain(|&r| r != node);
252 }
253 Self::remove_subtree(&mut guard.arena, node);
255 parent
256 };
257 self.notify(TreeChange::NodeRemoved { parent, node });
258 }
259
260 pub fn move_node(&self, node: NodeId, new_parent: NodeId, new_index: usize) {
266 let old_parent = {
267 let mut guard = self.inner.borrow_mut();
268 assert!(
270 !Self::is_descendant_of(&guard.arena, new_parent, node),
271 "cannot move a node into its own subtree"
272 );
273
274 let old_parent = guard.arena[node.key()].parent;
275
276 if let Some(pid) = old_parent {
278 guard.arena[pid.key()].children.retain(|&c| c != node);
279 } else {
280 guard.roots.retain(|&r| r != node);
281 }
282
283 guard.arena[node.key()].parent = Some(new_parent);
285 guard.arena[new_parent.key()]
286 .children
287 .insert(new_index, node);
288
289 old_parent
290 };
291 self.notify(TreeChange::NodeMoved {
292 node,
293 old_parent,
294 new_parent: Some(new_parent),
295 new_index,
296 });
297 }
298
299 pub fn move_to_root(&self, node: NodeId, new_index: usize) {
301 let old_parent = {
302 let mut guard = self.inner.borrow_mut();
303 let old_parent = guard.arena[node.key()].parent;
304
305 if let Some(pid) = old_parent {
307 guard.arena[pid.key()].children.retain(|&c| c != node);
308 } else {
309 guard.roots.retain(|&r| r != node);
310 }
311
312 guard.arena[node.key()].parent = None;
314 guard.roots.insert(new_index, node);
315
316 old_parent
317 };
318 self.notify(TreeChange::NodeMoved {
319 node,
320 old_parent,
321 new_parent: None,
322 new_index,
323 });
324 }
325
326 pub fn update(&self, node: NodeId, item: T) {
331 {
332 let mut guard = self.inner.borrow_mut();
333 guard.arena[node.key()].data = item;
334 }
335 self.notify(TreeChange::NodeUpdated { node });
336 }
337
338 pub fn observe_changes(&self, f: impl Fn(&TreeChange) + 'static) -> ObserverHandle {
343 let mut guard = self.inner.borrow_mut();
344 let id = guard.next_observer_id;
345 guard.next_observer_id += 1;
346 guard.observers.push(TreeObserverEntry {
347 id,
348 callback: Rc::new(f),
349 });
350 let inner = self.inner.clone();
351 ObserverHandle::new(
352 self.inner.clone(),
353 id,
354 Rc::new(move |observer_id| {
355 let removed = {
358 let mut guard = inner.borrow_mut();
359 let index = guard.observers.iter().position(|e| e.id == observer_id);
360 index.map(|i| guard.observers.remove(i))
361 };
362 drop(removed);
363 }),
364 )
365 }
366
367 fn notify(&self, change: TreeChange) {
370 let callbacks: Vec<Rc<dyn Fn(&TreeChange)>> = self
371 .inner
372 .borrow()
373 .observers
374 .iter()
375 .map(|e| e.callback.clone())
376 .collect();
377 for cb in &callbacks {
378 cb(&change);
379 }
380 }
381
382 fn remove_subtree(arena: &mut SlotMap<slotmap::DefaultKey, TreeNode<T>>, node: NodeId) {
388 let mut stack = vec![node];
389 let mut to_remove = Vec::new();
390 while let Some(current) = stack.pop() {
391 if let Some(n) = arena.get(current.key()) {
392 stack.extend(n.children.iter().copied());
393 }
394 to_remove.push(current);
395 }
396 for id in to_remove {
397 arena.remove(id.key());
398 }
399 }
400
401 fn is_descendant_of(
402 arena: &SlotMap<slotmap::DefaultKey, TreeNode<T>>,
403 candidate: NodeId,
404 ancestor: NodeId,
405 ) -> bool {
406 let mut current = Some(candidate);
407 while let Some(nid) = current {
408 if nid == ancestor {
409 return true;
410 }
411 current = arena.get(nid.key()).and_then(|n| n.parent);
412 }
413 false
414 }
415}
416
417impl<T: std::fmt::Debug + 'static> TreeModel<T> {
418 pub fn debug_named(self, _name: impl Into<String>) -> Self {
426 #[cfg(debug_assertions)]
427 {
428 let weak = Rc::downgrade(&self.inner);
429 let adapter: Rc<dyn crate::debug_registry::ModelDebug> =
430 Rc::new(TreeModelDebug::<T> { weak });
431 let name = _name.into();
432 crate::debug_registry::register(name, Rc::downgrade(&adapter));
433 self.inner.borrow_mut().debug_adapter = Some(adapter);
434 }
435 self
436 }
437}
438
439#[cfg(debug_assertions)]
440struct TreeModelDebug<T> {
441 weak: std::rc::Weak<RefCell<TreeModelInner<T>>>,
442}
443
444#[cfg(debug_assertions)]
445impl<T: std::fmt::Debug + 'static> crate::debug_registry::ModelDebug for TreeModelDebug<T> {
446 fn kind(&self) -> &'static str {
447 "TreeModel"
448 }
449 fn len(&self) -> usize {
450 self.weak
451 .upgrade()
452 .map(|inner| inner.borrow().arena.len())
453 .unwrap_or(0)
454 }
455 fn debug_dump(&self, out: &mut dyn std::fmt::Write) {
456 let Some(inner) = self.weak.upgrade() else {
457 return;
458 };
459 let guard = inner.borrow();
460 let roots: Vec<NodeId> = guard.roots.clone();
462 for root in roots {
463 dump_subtree(&guard, root, 0, out);
464 }
465 }
466}
467
468#[cfg(debug_assertions)]
469fn dump_subtree<T: std::fmt::Debug>(
470 guard: &TreeModelInner<T>,
471 node: NodeId,
472 depth: usize,
473 out: &mut dyn std::fmt::Write,
474) {
475 let Some(n) = guard.arena.get(node.key()) else {
476 return;
477 };
478 let _ = writeln!(out, "{:indent$}{:?}", "", n.data, indent = depth * 2);
479 let children = n.children.clone();
480 for child in children {
481 dump_subtree(guard, child, depth + 1, out);
482 }
483}
484
485impl<T: 'static> Default for TreeModel<T> {
486 fn default() -> Self {
487 Self::new()
488 }
489}
490
491impl<T: 'static> Clone for TreeModel<T> {
492 fn clone(&self) -> Self {
493 Self {
494 inner: self.inner.clone(),
495 }
496 }
497}
498
499impl<T: std::fmt::Debug + 'static> std::fmt::Debug for TreeModel<T> {
500 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
501 let guard = self.inner.borrow();
502 f.debug_struct("TreeModel")
503 .field("root_count", &guard.roots.len())
504 .field("total_nodes", &guard.arena.len())
505 .finish()
506 }
507}
508
509#[cfg(test)]
510mod tests {
511 use std::cell::Cell;
512
513 use super::*;
514
515 fn sample_tree() -> (TreeModel<&'static str>, NodeId, NodeId, NodeId, NodeId) {
516 let tree = TreeModel::new();
517 let a = tree.insert_root(0, "A");
518 let b = tree.insert_root(1, "B");
519 let a1 = tree.insert_child(a, 0, "A1");
520 let a2 = tree.insert_child(a, 1, "A2");
521 (tree, a, b, a1, a2)
522 }
523
524 #[test]
525 fn empty_tree() {
526 let tree: TreeModel<i32> = TreeModel::new();
527 assert_eq!(tree.root_count(), 0);
528 }
529
530 #[test]
531 fn insert_roots() {
532 let tree = TreeModel::new();
533 let a = tree.insert_root(0, "A");
534 let b = tree.insert_root(1, "B");
535 assert_eq!(tree.root_count(), 2);
536 assert_eq!(tree.root(0), a);
537 assert_eq!(tree.root(1), b);
538 }
539
540 #[test]
541 fn insert_children() {
542 let (tree, a, _, a1, a2) = sample_tree();
543 assert_eq!(tree.child_count(a), 2);
544 assert_eq!(tree.child(a, 0), a1);
545 assert_eq!(tree.child(a, 1), a2);
546 }
547
548 #[test]
549 fn parent_and_depth() {
550 let (tree, a, _, a1, _) = sample_tree();
551 assert_eq!(tree.parent(a), None);
552 assert_eq!(tree.parent(a1), Some(a));
553 assert_eq!(tree.depth(a), 0);
554 assert_eq!(tree.depth(a1), 1);
555 }
556
557 #[test]
558 fn has_children_query() {
559 let (tree, a, b, _, _) = sample_tree();
560 assert!(tree.has_children(a));
561 assert!(!tree.has_children(b));
562 }
563
564 #[test]
565 fn with_item() {
566 let (tree, a, _, _, _) = sample_tree();
567 assert_eq!(tree.with_item(a, |v| *v), Some("A"));
568 }
569
570 #[test]
571 fn find_by() {
572 let (tree, _, _, a1, _) = sample_tree();
573 let found = tree.find_by(|v| *v == "A1");
574 assert_eq!(found, Some(a1));
575
576 let not_found = tree.find_by(|v| *v == "Z");
577 assert_eq!(not_found, None);
578 }
579
580 #[test]
581 fn insert_root_emits_change() {
582 let tree = TreeModel::new();
583 let changes: Rc<RefCell<Vec<TreeChange>>> = Rc::new(RefCell::new(Vec::new()));
584 let c = changes.clone();
585 let _handle = tree.observe_changes(move |change| {
586 c.borrow_mut().push(change.clone());
587 });
588
589 let a = tree.insert_root(0, "A");
590 let log = changes.borrow();
591 assert_eq!(
592 log[0],
593 TreeChange::NodeInserted {
594 parent: None,
595 index: 0,
596 node: a
597 }
598 );
599 }
600
601 #[test]
602 fn insert_child_emits_change() {
603 let tree = TreeModel::new();
604 let a = tree.insert_root(0, "A");
605
606 let changes: Rc<RefCell<Vec<TreeChange>>> = Rc::new(RefCell::new(Vec::new()));
607 let c = changes.clone();
608 let _handle = tree.observe_changes(move |change| {
609 c.borrow_mut().push(change.clone());
610 });
611
612 let a1 = tree.insert_child(a, 0, "A1");
613 let log = changes.borrow();
614 assert_eq!(log.len(), 1, "insert_child should emit exactly one change");
615 assert_eq!(
616 log[0],
617 TreeChange::NodeInserted {
618 parent: Some(a),
619 index: 0,
620 node: a1
621 }
622 );
623 }
624
625 #[test]
626 fn remove_emits_change() {
627 let (tree, a, _, a1, _) = sample_tree();
628 let changes: Rc<RefCell<Vec<TreeChange>>> = Rc::new(RefCell::new(Vec::new()));
629 let c = changes.clone();
630 let _handle = tree.observe_changes(move |change| {
631 c.borrow_mut().push(change.clone());
632 });
633
634 tree.remove(a1);
635 assert_eq!(tree.child_count(a), 1);
636 let log = changes.borrow();
637 assert_eq!(log.len(), 1, "remove should emit exactly one change");
638 assert_eq!(
639 log[0],
640 TreeChange::NodeRemoved {
641 parent: Some(a),
642 node: a1
643 }
644 );
645 }
646
647 #[test]
648 fn remove_subtree() {
649 let tree = TreeModel::new();
650 let a = tree.insert_root(0, "A");
651 let a1 = tree.insert_child(a, 0, "A1");
652 let a1a = tree.insert_child(a1, 0, "A1a");
653
654 tree.remove(a1);
655 assert_eq!(tree.child_count(a), 0);
656 assert_eq!(tree.with_item(a1, |_| ()), None, "a1 should be removed");
658 assert_eq!(
659 tree.with_item(a1a, |_| ()),
660 None,
661 "a1a (grandchild) should also be removed"
662 );
663 }
664
665 #[test]
666 fn remove_root() {
667 let (tree, a, b, _, _) = sample_tree();
668 tree.remove(a);
669 assert_eq!(tree.root_count(), 1);
670 assert_eq!(tree.root(0), b);
671 }
672
673 #[test]
674 fn move_node() {
675 let (tree, a, b, a1, _) = sample_tree();
676 let changes: Rc<RefCell<Vec<TreeChange>>> = Rc::new(RefCell::new(Vec::new()));
677 let c = changes.clone();
678 let _handle = tree.observe_changes(move |change| {
679 c.borrow_mut().push(change.clone());
680 });
681
682 tree.move_node(a1, b, 0);
683
684 assert_eq!(tree.child_count(a), 1); assert_eq!(tree.child_count(b), 1); assert_eq!(tree.child(b, 0), a1);
687 assert_eq!(tree.parent(a1), Some(b));
688
689 let log = changes.borrow();
690 assert_eq!(
691 log[0],
692 TreeChange::NodeMoved {
693 node: a1,
694 old_parent: Some(a),
695 new_parent: Some(b),
696 new_index: 0,
697 }
698 );
699 }
700
701 #[test]
702 fn move_to_root() {
703 let (tree, a, _, a1, _) = sample_tree();
704 tree.move_to_root(a1, 0);
705
706 assert_eq!(tree.root_count(), 3); assert_eq!(tree.root(0), a1);
708 assert_eq!(tree.parent(a1), None);
709 assert_eq!(tree.child_count(a), 1); }
711
712 #[test]
713 #[should_panic(expected = "cannot move a node into its own subtree")]
714 fn move_into_own_subtree_panics() {
715 let (tree, a, _, a1, _) = sample_tree();
716 tree.move_node(a, a1, 0); }
718
719 #[test]
720 fn update_emits_change() {
721 let (tree, a, _, _, _) = sample_tree();
722 let changes: Rc<RefCell<Vec<TreeChange>>> = Rc::new(RefCell::new(Vec::new()));
723 let c = changes.clone();
724 let _handle = tree.observe_changes(move |change| {
725 c.borrow_mut().push(change.clone());
726 });
727
728 tree.update(a, "A-updated");
729 assert_eq!(tree.with_item(a, |v| *v), Some("A-updated"));
730 let log = changes.borrow();
731 assert_eq!(log[0], TreeChange::NodeUpdated { node: a });
732 }
733
734 #[test]
735 fn observer_removed_on_handle_drop() {
736 let tree = TreeModel::new();
737 let count = Rc::new(Cell::new(0));
738 let c = count.clone();
739 let handle = tree.observe_changes(move |_| c.set(c.get() + 1));
740
741 tree.insert_root(0, "A");
742 assert_eq!(count.get(), 1);
743
744 drop(handle);
745 tree.insert_root(1, "B");
746 assert_eq!(count.get(), 1); }
748
749 #[test]
750 fn clone_shares_data() {
751 let tree = TreeModel::new();
752 let a = tree.insert_root(0, "A");
753
754 let clone = tree.clone();
755 assert_eq!(clone.root_count(), 1);
756 assert_eq!(clone.with_item(a, |v| *v), Some("A"));
757
758 clone.insert_root(1, "B");
759 assert_eq!(tree.root_count(), 2);
760 }
761
762 #[test]
763 fn deep_tree_depth() {
764 let tree = TreeModel::new();
765 let r = tree.insert_root(0, "r");
766 let c1 = tree.insert_child(r, 0, "c1");
767 let c2 = tree.insert_child(c1, 0, "c2");
768 let c3 = tree.insert_child(c2, 0, "c3");
769 assert_eq!(tree.depth(r), 0);
770 assert_eq!(tree.depth(c1), 1);
771 assert_eq!(tree.depth(c2), 2);
772 assert_eq!(tree.depth(c3), 3);
773 }
774
775 #[test]
776 fn children_returns_correct_ids() {
777 let (tree, a, _, a1, a2) = sample_tree();
778 let children = tree.children(a);
779 assert_eq!(children, vec![a1, a2]);
780 }
781
782 #[test]
786 fn remove_deep_chain_does_not_overflow() {
787 const DEPTH: usize = 50_000;
788 let tree = TreeModel::new();
789 let root = tree.insert_root(0, 0usize);
790 let mut leaf = root;
791 for i in 1..DEPTH {
792 leaf = tree.insert_child(leaf, 0, i);
793 }
794 tree.remove(root);
795 assert_eq!(tree.root_count(), 0);
796 assert_eq!(tree.with_item(leaf, |_| ()), None);
797 }
798}