1use std::hash::Hash;
2
3use ratatui::widgets::TableState;
4use rustc_hash::{FxBuildHasher, FxHashMap, FxHashSet};
5use smallvec::SmallVec;
6
7use crate::action::{TreeAction, TreeEvent};
8use crate::model::{TreeFilter, TreeFilterConfig, TreeModel};
9use crate::style::TreeScrollPolicy;
10
11#[cfg(feature = "serde")]
12use serde::{Deserialize, Serialize};
13
14#[cfg(feature = "edit")]
15use crate::edit::TreeEdit;
16
17#[cfg(feature = "keymap")]
18use crate::keymap::TreeKeyBindings;
19#[cfg(feature = "keymap")]
20use crossterm::event::KeyEvent;
21
22#[derive(Clone)]
23pub struct VisibleNode<Id> {
24 pub(crate) id: Id,
25 pub(crate) level: u16,
26 pub(crate) parent: Option<Id>,
27 pub(crate) is_tail_stack: SmallVec<[bool; 8]>,
28}
29
30pub struct TreeListViewState<Id> {
32 list_state: TableState,
33 expanded: FxHashSet<(Option<Id>, Id)>,
34 visible_nodes: Vec<VisibleNode<Id>>,
35 dirty: bool,
36 manual_marked: FxHashSet<Id>,
37 effective_marked: FxHashSet<Id>,
38 marks_dirty: bool,
39 draw_lines: bool,
40 #[cfg(feature = "keymap")]
41 keymap: TreeKeyBindings,
42}
43
44#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
45#[derive(Clone, Debug)]
46pub struct TreeListViewSnapshot<Id> {
48 pub expanded: Vec<(Option<Id>, Id)>,
49 pub manual_marked: Vec<Id>,
50 pub selected: Option<usize>,
51 pub selected_column: Option<usize>,
52 pub offset: usize,
53 pub draw_lines: bool,
54}
55
56impl<Id: Copy + Eq + Hash> Default for TreeListViewState<Id> {
57 fn default() -> Self {
58 Self::new()
59 }
60}
61
62impl<Id: Copy + Eq + Hash> TreeListViewState<Id> {
63 pub fn new() -> Self {
64 Self::with_capacity(0)
65 }
66
67 pub fn with_capacity(capacity: usize) -> Self {
68 Self {
69 list_state: TableState::default(),
70 expanded: FxHashSet::with_capacity_and_hasher(capacity, FxBuildHasher),
71 visible_nodes: Vec::with_capacity(capacity),
72 dirty: true,
73 manual_marked: FxHashSet::with_capacity_and_hasher(capacity, FxBuildHasher),
74 effective_marked: FxHashSet::with_capacity_and_hasher(capacity, FxBuildHasher),
75 marks_dirty: true,
76 draw_lines: true,
77 #[cfg(feature = "keymap")]
78 keymap: TreeKeyBindings::new(),
79 }
80 }
81
82 #[cfg(feature = "keymap")]
83 pub const fn keymap_mut(&mut self) -> &mut TreeKeyBindings {
84 &mut self.keymap
85 }
86
87 pub(crate) const fn list_state(&self) -> &TableState {
88 &self.list_state
89 }
90
91 pub(crate) const fn list_state_mut(&mut self) -> &mut TableState {
92 &mut self.list_state
93 }
94
95 pub(crate) fn visible_nodes(&self) -> &[VisibleNode<Id>] {
96 &self.visible_nodes
97 }
98
99 pub(crate) fn is_expanded(&self, parent: Option<Id>, id: Id) -> bool {
100 self.expanded.contains(&(parent, id))
101 }
102
103 pub fn snapshot(&self) -> TreeListViewSnapshot<Id> {
104 TreeListViewSnapshot {
105 expanded: self.expanded.iter().copied().collect(),
106 manual_marked: self.manual_marked.iter().copied().collect(),
107 selected: self.list_state.selected(),
108 selected_column: self.list_state.selected_column(),
109 offset: self.list_state.offset(),
110 draw_lines: self.draw_lines,
111 }
112 }
113
114 pub fn restore(&mut self, snapshot: TreeListViewSnapshot<Id>) {
115 self.expanded = snapshot.expanded.into_iter().collect();
116 self.manual_marked = snapshot.manual_marked.into_iter().collect();
117 self.draw_lines = snapshot.draw_lines;
118 *self.list_state.offset_mut() = snapshot.offset;
119 self.list_state.select(snapshot.selected);
120 *self.list_state.selected_column_mut() = snapshot.selected_column;
121 self.dirty = true;
122 self.marks_dirty = true;
123 }
124
125 pub const fn draw_lines(&self) -> bool {
126 self.draw_lines
127 }
128
129 pub const fn set_draw_lines(&mut self, draw: bool) {
130 self.draw_lines = draw;
131 }
132
133 pub const fn invalidate(&mut self) {
134 self.dirty = true;
135 }
136
137 pub const fn invalidate_all(&mut self) {
138 self.dirty = true;
139 self.marks_dirty = true;
140 }
141
142 pub const fn select_first(&mut self) {
143 self.list_state.select_first();
144 }
145
146 pub const fn select_last(&mut self) {
147 self.list_state.select_last();
148 }
149
150 pub fn scroll_down_by(&mut self, amount: u16) {
151 self.list_state.scroll_down_by(amount);
152 }
153
154 pub fn scroll_up_by(&mut self, amount: u16) {
155 self.list_state.scroll_up_by(amount);
156 }
157
158 pub fn select_prev(&mut self) {
159 if self.visible_nodes.is_empty() {
160 self.list_state.select(None);
161 return;
162 }
163 let selected = self.list_state.selected().unwrap_or(0);
164 self.list_state.select(Some(selected.saturating_sub(1)));
165 }
166
167 pub fn select_next(&mut self) {
168 if self.visible_nodes.is_empty() {
169 self.list_state.select(None);
170 return;
171 }
172 let selected = self.list_state.selected().unwrap_or(0);
173 let new_selected = (selected + 1).min(self.visible_nodes.len().saturating_sub(1));
174 self.list_state.select(Some(new_selected));
175 }
176
177 pub fn ensure_selection_visible(&mut self, viewport_height: usize) {
178 self.clamp_selection();
179 let Some(selected) = self.list_state.selected() else {
180 return;
181 };
182 let viewport_height = viewport_height.max(1);
183 let offset = self.list_state.offset();
184 if selected < offset {
185 *self.list_state.offset_mut() = selected;
186 } else if selected >= offset + viewport_height {
187 *self.list_state.offset_mut() = selected + 1 - viewport_height;
188 }
189 }
190
191 pub fn ensure_selection_visible_with_policy(
192 &mut self,
193 viewport_height: usize,
194 policy: TreeScrollPolicy,
195 ) {
196 match policy {
197 TreeScrollPolicy::KeepInView => self.ensure_selection_visible(viewport_height),
198 TreeScrollPolicy::CenterOnSelect => {
199 self.ensure_selection_visible_centered(viewport_height);
200 }
201 }
202 }
203
204 fn ensure_selection_visible_centered(&mut self, viewport_height: usize) {
205 self.clamp_selection();
206 let Some(selected) = self.list_state.selected() else {
207 return;
208 };
209 let viewport_height = viewport_height.max(1);
210 let total = self.visible_nodes.len();
211 if total <= viewport_height {
212 *self.list_state.offset_mut() = 0;
213 return;
214 }
215
216 let half = viewport_height / 2;
217 let mut offset = selected.saturating_sub(half);
218 let max_offset = total.saturating_sub(viewport_height);
219 if offset > max_offset {
220 offset = max_offset;
221 }
222 *self.list_state.offset_mut() = offset;
223 }
224
225 pub fn selected_id(&self) -> Option<Id> {
226 self.list_state
227 .selected()
228 .and_then(|idx| self.visible_nodes.get(idx).map(|node| node.id))
229 }
230
231 pub fn selected_parent_id(&self) -> Option<Id> {
232 self.list_state
233 .selected()
234 .and_then(|idx| self.visible_nodes.get(idx).and_then(|node| node.parent))
235 }
236
237 pub const fn visible_len(&self) -> usize {
238 self.visible_nodes.len()
239 }
240
241 pub fn selected_level(&self) -> Option<u16> {
242 self.list_state
243 .selected()
244 .and_then(|idx| self.visible_nodes.get(idx).map(|node| node.level))
245 }
246
247 pub fn selected_is_expanded<T: TreeModel<Id = Id>>(&self, model: &T) -> Option<bool> {
248 self.list_state.selected().and_then(|idx| {
249 self.visible_nodes.get(idx).map(|node| {
250 if model.children(node.id).is_empty() {
251 false
252 } else {
253 self.expanded.contains(&(node.parent, node.id))
254 }
255 })
256 })
257 }
258
259 pub fn select_by_id<T: TreeModel<Id = Id>>(&mut self, model: &T, id: Id) -> bool {
260 let _ = self.expand_to(model, id);
261 self.ensure_visible_nodes(model);
262 if let Some(idx) = self.visible_nodes.iter().position(|node| node.id == id) {
263 self.list_state.select(Some(idx));
264 true
265 } else {
266 false
267 }
268 }
269
270 pub fn ensure_visible_id<T: TreeModel<Id = Id>>(&mut self, model: &T, id: Id) -> bool {
271 let _ = self.expand_to(model, id);
272 self.ensure_visible_nodes(model);
273 self.visible_nodes.iter().any(|node| node.id == id)
274 }
275
276 pub fn expand_to<T: TreeModel<Id = Id>>(&mut self, model: &T, id: Id) -> bool {
277 let Some(path) = Self::find_path_to(model, id) else {
278 return false;
279 };
280 for (parent, node) in path {
281 if !model.children(node).is_empty() {
282 self.expanded.insert((parent, node));
283 }
284 }
285 self.dirty = true;
286 true
287 }
288
289 pub fn expand_all<T: TreeModel<Id = Id>>(&mut self, model: &T) {
290 self.expanded.clear();
291 if let Some(root) = model.root() {
292 let mut stack = vec![(None, root)];
293 while let Some((parent, node)) = stack.pop() {
294 let children = model.children(node);
295 if !children.is_empty() {
296 self.expanded.insert((parent, node));
297 for child in children.iter().copied() {
298 stack.push((Some(node), child));
299 }
300 }
301 }
302 }
303 self.dirty = true;
304 }
305
306 pub fn collapse_all(&mut self) {
307 self.expanded.clear();
308 self.dirty = true;
309 }
310
311 pub fn ensure_visible_nodes<T: TreeModel<Id = Id>>(&mut self, model: &T) {
312 if !self.dirty {
313 return;
314 }
315 self.update_visible_nodes(model);
316 }
317
318 pub fn ensure_visible_nodes_filtered<T, F>(
319 &mut self,
320 model: &T,
321 filter: &F,
322 config: TreeFilterConfig,
323 ) where
324 T: TreeModel<Id = Id>,
325 F: TreeFilter<T>,
326 {
327 if !self.dirty {
328 return;
329 }
330 if !config.enabled {
331 self.update_visible_nodes(model);
332 return;
333 }
334
335 self.visible_nodes.clear();
336 if let Some(root) = model.root() {
337 let mut is_tail_stack: SmallVec<[bool; 8]> = SmallVec::new();
338 let mut memo: FxHashMap<Id, bool> = FxHashMap::default();
339 self.build_visible_nodes_filtered(
340 model,
341 root,
342 0,
343 None,
344 &mut is_tail_stack,
345 filter,
346 config,
347 &mut memo,
348 );
349 }
350 self.dirty = false;
351 self.clamp_selection();
352 }
353
354 pub fn ensure_mark_cache<T: TreeModel<Id = Id>>(&mut self, model: &T) {
355 if !self.marks_dirty {
356 return;
357 }
358
359 let mut memo: FxHashMap<Id, bool> = FxHashMap::default();
360 let mut seeds = FxHashSet::with_capacity_and_hasher(
361 self.visible_nodes.len() + self.manual_marked.len() + 1,
362 FxBuildHasher,
363 );
364
365 for node in &self.visible_nodes {
366 seeds.insert(node.id);
367 }
368 if let Some(root_id) = model.root() {
369 seeds.insert(root_id);
370 }
371 seeds.extend(self.manual_marked.iter().copied());
372
373 for node_id in seeds {
374 self.compute_effective_mark(node_id, model, &mut memo);
375 }
376
377 self.effective_marked.clear();
378 self.effective_marked.extend(
379 memo.into_iter()
380 .filter_map(|(node_id, marked)| marked.then_some(node_id)),
381 );
382 self.marks_dirty = false;
383 }
384
385 pub fn node_is_marked(&self, node_id: Id) -> bool {
386 self.effective_marked.contains(&node_id)
387 }
388
389 pub fn prune_removed_marks<T: TreeModel<Id = Id>>(&mut self, model: &T) {
390 self.manual_marked
391 .retain(|node_id| model.contains(*node_id));
392 self.effective_marked
393 .retain(|node_id| model.contains(*node_id));
394 self.marks_dirty = true;
395 }
396
397 pub fn handle_action<T: TreeModel<Id = Id>, C>(
398 &mut self,
399 model: &T,
400 action: TreeAction<C>,
401 ) -> TreeEvent<C> {
402 self.ensure_visible_nodes(model);
403 self.handle_action_inner(model, action)
404 }
405
406 pub fn handle_action_filtered<T, F, C>(
407 &mut self,
408 model: &T,
409 filter: &F,
410 config: TreeFilterConfig,
411 action: TreeAction<C>,
412 ) -> TreeEvent<C>
413 where
414 T: TreeModel<Id = Id>,
415 F: TreeFilter<T>,
416 {
417 self.ensure_visible_nodes_filtered(model, filter, config);
418 self.handle_action_inner(model, action)
419 }
420
421 #[cfg(feature = "edit")]
422 pub fn handle_edit_action<T: TreeEdit<Id = Id>, C>(
423 &mut self,
424 model: &mut T,
425 action: TreeAction<C>,
426 clipboard: &mut Option<Id>,
427 ) -> bool {
428 self.ensure_visible_nodes(model);
429 match action {
430 TreeAction::ReorderUp => {
431 if let Some(node_id) = self.selected_id()
432 && let Some(parent_id) = self.selected_parent_id()
433 && model.move_child_up(parent_id, node_id)
434 {
435 self.invalidate();
436 self.ensure_visible_nodes(model);
437 if let Some(idx) = self
438 .visible_nodes
439 .iter()
440 .position(|node| node.id == node_id)
441 {
442 self.list_state.select(Some(idx));
443 }
444 return true;
445 }
446 false
447 }
448 TreeAction::ReorderDown => {
449 if let Some(node_id) = self.selected_id()
450 && let Some(parent_id) = self.selected_parent_id()
451 && model.move_child_down(parent_id, node_id)
452 {
453 self.invalidate();
454 self.ensure_visible_nodes(model);
455 if let Some(idx) = self
456 .visible_nodes
457 .iter()
458 .position(|node| node.id == node_id)
459 {
460 self.list_state.select(Some(idx));
461 }
462 return true;
463 }
464 false
465 }
466 TreeAction::DetachNode => {
467 if let Some(node_id) = self.selected_id() {
468 if model.is_root(node_id) {
469 return false;
470 }
471 if let Some(parent_id) = self.selected_parent_id() {
472 model.remove_child(parent_id, node_id);
473 self.prune_removed_marks(model);
474 self.invalidate_all();
475 return true;
476 }
477 }
478 false
479 }
480 TreeAction::DeleteNode => {
481 if let Some(node_id) = self.selected_id() {
482 if model.is_root(node_id) {
483 return false;
484 }
485 model.delete_node(node_id);
486 self.prune_removed_marks(model);
487 self.invalidate_all();
488 return true;
489 }
490 false
491 }
492 TreeAction::YankNode => {
493 if let Some(node_id) = self.selected_id() {
494 if model.is_root(node_id) {
495 return false;
496 }
497 *clipboard = Some(node_id);
498 return true;
499 }
500 false
501 }
502 TreeAction::PasteNode => {
503 if let Some(node_id) = *clipboard
504 && let Some(parent_id) = self.selected_id()
505 {
506 model.add_child(parent_id, node_id);
507 self.invalidate_all();
508 return true;
509 }
510 false
511 }
512 TreeAction::Custom(_) => false,
513 _ => false,
514 }
515 }
516
517 #[cfg(feature = "keymap")]
518 pub fn handle_key<T: TreeModel<Id = Id>>(&mut self, model: &T, key: KeyEvent) -> TreeEvent<()> {
519 self.ensure_visible_nodes(model);
520 let Some(action) = self.keymap.resolve(key) else {
521 return TreeEvent::Unhandled;
522 };
523 self.handle_action_inner(model, action)
524 }
525
526 #[cfg(feature = "keymap")]
527 pub fn handle_key_with<T, C, F>(&mut self, model: &T, key: KeyEvent, custom: F) -> TreeEvent<C>
528 where
529 T: TreeModel<Id = Id>,
530 F: Fn(KeyEvent) -> Option<C>,
531 {
532 self.ensure_visible_nodes(model);
533 let Some(action) = self.keymap.resolve_with(key, custom) else {
534 return TreeEvent::Unhandled;
535 };
536 self.handle_action_inner(model, action)
537 }
538
539 #[cfg(feature = "keymap")]
540 pub fn handle_key_filtered<T, F>(
541 &mut self,
542 model: &T,
543 filter: &F,
544 config: TreeFilterConfig,
545 key: KeyEvent,
546 ) -> TreeEvent<()>
547 where
548 T: TreeModel<Id = Id>,
549 F: TreeFilter<T>,
550 {
551 self.ensure_visible_nodes_filtered(model, filter, config);
552 let Some(action) = self.keymap.resolve(key) else {
553 return TreeEvent::Unhandled;
554 };
555 self.handle_action_inner(model, action)
556 }
557
558 #[cfg(feature = "keymap")]
559 pub fn handle_key_filtered_with<T, F, C, R>(
560 &mut self,
561 model: &T,
562 filter: &F,
563 config: TreeFilterConfig,
564 key: KeyEvent,
565 custom: R,
566 ) -> TreeEvent<C>
567 where
568 T: TreeModel<Id = Id>,
569 F: TreeFilter<T>,
570 R: Fn(KeyEvent) -> Option<C>,
571 {
572 self.ensure_visible_nodes_filtered(model, filter, config);
573 let Some(action) = self.keymap.resolve_with(key, custom) else {
574 return TreeEvent::Unhandled;
575 };
576 self.handle_action_inner(model, action)
577 }
578
579 fn handle_action_inner<T: TreeModel<Id = Id>, C>(
580 &mut self,
581 model: &T,
582 action: TreeAction<C>,
583 ) -> TreeEvent<C> {
584 if matches!(&action, TreeAction::Custom(_)) {
585 return TreeEvent::Action(action);
586 }
587
588 if self.visible_nodes.is_empty() {
589 return TreeEvent::Unhandled;
590 }
591
592 match action {
593 TreeAction::SelectPrev => {
594 self.select_prev();
595 TreeEvent::Handled
596 }
597 TreeAction::SelectNext => {
598 self.select_next();
599 TreeEvent::Handled
600 }
601 TreeAction::SelectParent => {
602 self.select_parent();
603 TreeEvent::Handled
604 }
605 TreeAction::SelectChild => {
606 self.select_child_with_descendants(model);
607 TreeEvent::Handled
608 }
609 TreeAction::ToggleRecursive => {
610 if let Some(node_id) = self.selected_id()
611 && self.has_children(model, node_id)
612 {
613 let parent = self.selected_parent_id();
614 let should_expand = !self.expanded.contains(&(parent, node_id));
615 self.set_expanded_recursive(model, node_id, parent, should_expand);
616 self.dirty = true;
617 return TreeEvent::Handled;
618 }
619 TreeEvent::Unhandled
620 }
621 TreeAction::ToggleNode => {
622 if let Some(node_id) = self.selected_id()
623 && self.has_children(model, node_id)
624 {
625 let parent = self.selected_parent_id();
626 self.toggle(node_id, parent);
627 return TreeEvent::Handled;
628 }
629 TreeEvent::Unhandled
630 }
631 TreeAction::ToggleGuides => {
632 self.draw_lines = !self.draw_lines;
633 TreeEvent::Handled
634 }
635 TreeAction::ToggleMark => {
636 if let Some(node_id) = self.selected_id() {
637 self.toggle_node_mark(node_id);
638 return TreeEvent::Handled;
639 }
640 TreeEvent::Unhandled
641 }
642 TreeAction::SelectFirst => {
643 self.select_first();
644 TreeEvent::Handled
645 }
646 TreeAction::SelectLast => {
647 self.select_last();
648 TreeEvent::Handled
649 }
650 TreeAction::ReorderUp
651 | TreeAction::ReorderDown
652 | TreeAction::AddChild
653 | TreeAction::EditNode
654 | TreeAction::DetachNode
655 | TreeAction::DeleteNode
656 | TreeAction::YankNode
657 | TreeAction::PasteNode => TreeEvent::Action(action),
658 TreeAction::Custom(_) => TreeEvent::Action(action),
659 }
660 }
661
662 pub fn toggle(&mut self, node_id: Id, parent: Option<Id>) {
663 let key = (parent, node_id);
664 if self.expanded.contains(&key) {
665 self.expanded.remove(&key);
666 } else {
667 self.expanded.insert(key);
668 }
669 self.dirty = true;
670 }
671
672 pub fn set_expanded(&mut self, node_id: Id, parent: Option<Id>, expand: bool) {
673 let key = (parent, node_id);
674 if expand {
675 self.expanded.insert(key);
676 } else {
677 self.expanded.remove(&key);
678 }
679 self.dirty = true;
680 }
681
682 fn has_children<T: TreeModel<Id = Id>>(&self, model: &T, node_id: Id) -> bool {
683 !model.children(node_id).is_empty()
684 }
685
686 fn update_visible_nodes<T: TreeModel<Id = Id>>(&mut self, model: &T) {
687 self.visible_nodes.clear();
688 if let Some(root) = model.root() {
689 let mut is_tail_stack: SmallVec<[bool; 8]> = SmallVec::new();
690 self.build_visible_nodes(model, root, 0, None, &mut is_tail_stack);
691 }
692 self.dirty = false;
693 self.clamp_selection();
694 }
695
696 fn find_path_to<T: TreeModel<Id = Id>>(model: &T, target: Id) -> Option<Vec<(Option<Id>, Id)>> {
697 let root = model.root()?;
698 let mut path: Vec<(Option<Id>, Id)> = Vec::new();
699 if Self::dfs_find_path(model, root, None, target, &mut path) {
700 Some(path)
701 } else {
702 None
703 }
704 }
705
706 fn dfs_find_path<T: TreeModel<Id = Id>>(
707 model: &T,
708 node: Id,
709 parent: Option<Id>,
710 target: Id,
711 path: &mut Vec<(Option<Id>, Id)>,
712 ) -> bool {
713 path.push((parent, node));
714 if node == target {
715 return true;
716 }
717 for child in model.children(node).iter().copied() {
718 if Self::dfs_find_path(model, child, Some(node), target, path) {
719 return true;
720 }
721 }
722 path.pop();
723 false
724 }
725
726 fn build_visible_nodes<T: TreeModel<Id = Id>>(
727 &mut self,
728 model: &T,
729 node_id: Id,
730 level: u16,
731 parent: Option<Id>,
732 is_tail_stack: &mut SmallVec<[bool; 8]>,
733 ) {
734 self.visible_nodes.push(VisibleNode {
735 id: node_id,
736 level,
737 parent,
738 is_tail_stack: is_tail_stack.clone(),
739 });
740
741 let is_expanded = self.expanded.contains(&(parent, node_id));
742 if !is_expanded {
743 return;
744 }
745
746 let children = model.children(node_id);
747 for (i, child) in children.iter().copied().enumerate() {
748 let is_last = i == children.len().saturating_sub(1);
749 is_tail_stack.push(is_last);
750 self.build_visible_nodes(model, child, level + 1, Some(node_id), is_tail_stack);
751 is_tail_stack.pop();
752 }
753 }
754
755 fn subtree_has_match<T, F>(
756 &self,
757 model: &T,
758 node_id: Id,
759 filter: &F,
760 memo: &mut FxHashMap<Id, bool>,
761 ) -> bool
762 where
763 T: TreeModel<Id = Id>,
764 F: TreeFilter<T>,
765 {
766 if let Some(&cached) = memo.get(&node_id) {
767 return cached;
768 }
769
770 let mut matched = filter.is_match(model, node_id);
771 if !matched {
772 for child in model.children(node_id).iter().copied() {
773 if self.subtree_has_match(model, child, filter, memo) {
774 matched = true;
775 break;
776 }
777 }
778 }
779
780 memo.insert(node_id, matched);
781 matched
782 }
783
784 fn build_visible_nodes_filtered<T, F>(
785 &mut self,
786 model: &T,
787 node_id: Id,
788 level: u16,
789 parent: Option<Id>,
790 is_tail_stack: &mut SmallVec<[bool; 8]>,
791 filter: &F,
792 config: TreeFilterConfig,
793 memo: &mut FxHashMap<Id, bool>,
794 ) -> bool
795 where
796 T: TreeModel<Id = Id>,
797 F: TreeFilter<T>,
798 {
799 let self_match = filter.is_match(model, node_id);
800 let children = model.children(node_id);
801
802 let mut visible_children: SmallVec<[Id; 8]> = SmallVec::new();
803 for child in children.iter().copied() {
804 if self.subtree_has_match(model, child, filter, memo) {
805 visible_children.push(child);
806 }
807 }
808
809 let include_self = self_match || !visible_children.is_empty();
810 if !include_self {
811 return false;
812 }
813
814 self.visible_nodes.push(VisibleNode {
815 id: node_id,
816 level,
817 parent,
818 is_tail_stack: is_tail_stack.clone(),
819 });
820
821 let expand_children = config.auto_expand || self.expanded.contains(&(parent, node_id));
822 if expand_children && !visible_children.is_empty() {
823 let last_idx = visible_children.len().saturating_sub(1);
824 for (idx, child) in visible_children.iter().copied().enumerate() {
825 let is_last = idx == last_idx;
826 is_tail_stack.push(is_last);
827 self.build_visible_nodes_filtered(
828 model,
829 child,
830 level + 1,
831 Some(node_id),
832 is_tail_stack,
833 filter,
834 config,
835 memo,
836 );
837 is_tail_stack.pop();
838 }
839 }
840
841 true
842 }
843
844 const fn clamp_selection(&mut self) {
845 if self.visible_nodes.is_empty() {
846 self.list_state.select(None);
847 return;
848 }
849
850 if let Some(selected) = self.list_state.selected()
851 && selected >= self.visible_nodes.len()
852 {
853 self.list_state
854 .select(Some(self.visible_nodes.len().saturating_sub(1)));
855 }
856 }
857
858 fn toggle_node_mark(&mut self, node_id: Id) {
859 if !self.manual_marked.insert(node_id) {
860 self.manual_marked.remove(&node_id);
861 }
862 self.marks_dirty = true;
863 }
864
865 fn compute_effective_mark<T: TreeModel<Id = Id>>(
866 &self,
867 node_id: Id,
868 model: &T,
869 memo: &mut FxHashMap<Id, bool>,
870 ) -> bool {
871 if let Some(&cached) = memo.get(&node_id) {
872 return cached;
873 }
874
875 let result = if self.manual_marked.contains(&node_id) {
876 true
877 } else {
878 let children = model.children(node_id);
879 if children.is_empty() {
880 false
881 } else {
882 children
883 .iter()
884 .copied()
885 .all(|child| self.compute_effective_mark(child, model, memo))
886 }
887 };
888
889 memo.insert(node_id, result);
890 result
891 }
892
893 fn select_parent(&mut self) {
894 let Some(selected_idx) = self.list_state.selected() else {
895 return;
896 };
897
898 let Some(parent_id) = self
899 .visible_nodes
900 .get(selected_idx)
901 .and_then(|node| node.parent)
902 else {
903 return;
904 };
905
906 if let Some(parent_idx) = self
907 .visible_nodes
908 .iter()
909 .position(|node| node.id == parent_id)
910 {
911 self.list_state.select(Some(parent_idx));
912 }
913 }
914
915 fn select_child_with_descendants<T: TreeModel<Id = Id>>(&mut self, model: &T) {
916 let Some(mut selected_idx) = self.list_state.selected() else {
917 return;
918 };
919 let Some(selected_node) = self.visible_nodes.get(selected_idx) else {
920 return;
921 };
922 let node_id = selected_node.id;
923 let mut level = selected_node.level;
924 let parent_id = selected_node.parent;
925
926 if self.has_children(model, node_id) {
927 let expand_key = (parent_id, node_id);
928 if self.expanded.insert(expand_key) {
929 self.dirty = true;
930 self.update_visible_nodes(model);
931
932 if let Some(current_idx) = self
933 .visible_nodes
934 .iter()
935 .position(|node| node.id == node_id)
936 {
937 selected_idx = current_idx;
938 if let Some(node) = self.visible_nodes.get(current_idx) {
939 level = node.level;
940 }
941 self.list_state.select(Some(current_idx));
942 } else {
943 return;
944 }
945 }
946
947 for idx in selected_idx + 1..self.visible_nodes.len() {
948 let candidate = &self.visible_nodes[idx];
949 let candidate_level = candidate.level;
950 if candidate_level <= level {
951 break;
952 }
953 if candidate_level == level + 1 && self.has_children(model, candidate.id) {
954 self.list_state.select(Some(idx));
955 return;
956 }
957 }
958 }
959
960 for idx in selected_idx + 1..self.visible_nodes.len() {
961 let candidate = &self.visible_nodes[idx];
962 if candidate.level < level {
963 break;
964 }
965 if self.has_children(model, candidate.id) {
966 self.list_state.select(Some(idx));
967 return;
968 }
969 }
970 }
971
972 fn set_expanded_recursive<T: TreeModel<Id = Id>>(
973 &mut self,
974 model: &T,
975 node_id: Id,
976 parent: Option<Id>,
977 expand: bool,
978 ) {
979 let children = model.children(node_id);
980 let key = (parent, node_id);
981 if expand {
982 if !children.is_empty() {
983 self.expanded.insert(key);
984 }
985 } else {
986 self.expanded.remove(&key);
987 }
988
989 if children.is_empty() {
990 return;
991 }
992
993 for child in children.iter().copied() {
994 self.set_expanded_recursive(model, child, Some(node_id), expand);
995 }
996 }
997}
998
999#[cfg(test)]
1000mod tests {
1001 use super::*;
1002
1003 struct TestTree {
1004 children: Vec<Vec<usize>>,
1005 }
1006
1007 impl TestTree {
1008 fn new() -> Self {
1009 Self {
1010 children: vec![
1011 vec![1, 2], vec![3, 4], vec![], vec![], vec![], ],
1017 }
1018 }
1019 }
1020
1021 impl TreeModel for TestTree {
1022 type Id = usize;
1023
1024 fn root(&self) -> Option<Self::Id> {
1025 Some(0)
1026 }
1027
1028 fn children(&self, id: Self::Id) -> &[Self::Id] {
1029 &self.children[id]
1030 }
1031
1032 fn contains(&self, id: Self::Id) -> bool {
1033 id < self.children.len()
1034 }
1035 }
1036
1037 #[test]
1038 fn builds_visible_nodes_with_expansion() {
1039 let tree = TestTree::new();
1040 let mut state = TreeListViewState::<usize>::new();
1041
1042 state.set_expanded(0, None, true);
1043 state.set_expanded(1, Some(0), true);
1044 state.ensure_visible_nodes(&tree);
1045
1046 let ids: Vec<_> = state.visible_nodes.iter().map(|n| n.id).collect();
1047 let levels: Vec<_> = state.visible_nodes.iter().map(|n| n.level).collect();
1048
1049 assert_eq!(ids, vec![0, 1, 3, 4, 2]);
1050 assert_eq!(levels, vec![0, 1, 2, 2, 1]);
1051 }
1052
1053 #[test]
1054 fn filtered_view_keeps_matching_path() {
1055 let tree = TestTree::new();
1056 let mut state = TreeListViewState::<usize>::new();
1057 let filter = |_: &TestTree, id: usize| id == 4;
1058
1059 state.ensure_visible_nodes_filtered(&tree, &filter, TreeFilterConfig::enabled());
1060
1061 let ids: Vec<_> = state.visible_nodes.iter().map(|n| n.id).collect();
1062 assert_eq!(ids, vec![0, 1, 4]);
1063 }
1064
1065 #[test]
1066 fn select_prev_clears_selection_when_empty() {
1067 let mut state = TreeListViewState::<usize>::new();
1068 state.list_state.select(Some(0));
1069
1070 state.select_prev();
1071
1072 assert_eq!(state.list_state.selected(), None);
1073 }
1074
1075 #[test]
1076 fn filtered_view_without_matches_clears_selection() {
1077 let tree = TestTree::new();
1078 let mut state = TreeListViewState::<usize>::new();
1079 let filter = |_: &TestTree, _: usize| false;
1080
1081 state.list_state.select(Some(0));
1082 state.ensure_visible_nodes_filtered(&tree, &filter, TreeFilterConfig::enabled());
1083
1084 assert!(state.visible_nodes.is_empty());
1085 assert_eq!(state.list_state.selected(), None);
1086 }
1087}