1use crate::{ChangeSignal, Property, RowKey, RowSelection, VecModel, list::MAX_ROWS};
2use std::{
3 cell::RefCell,
4 collections::{BTreeMap, HashMap, HashSet},
5 rc::Rc,
6 sync::{Arc, Weak},
7};
8
9#[derive(Clone, Copy, Debug, PartialEq, Eq)]
10pub enum TreeAction {
11 SetExpanded {
12 key: i64,
13 row: RowKey,
14 expanded: bool,
15 },
16 Selection(TreeSelectionAction),
17}
18
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub enum TreeCommand {
22 Expand(i64),
23 Collapse(i64),
24 ToggleExpanded(i64),
25 ExpandRecursively { key: i64, depth: i64 },
26 CollapseRecursively(i64),
27 ExpandTo(i64),
28}
29
30#[doc(hidden)]
31pub struct TreeExpansionChange {
32 pub key: i64,
33 pub expanded: bool,
34}
35
36#[derive(Clone, Copy, Debug, PartialEq, Eq)]
37pub enum TreeSelectionAction {
38 Row {
39 key: i64,
40 row: RowKey,
41 operation: RowSelection,
42 },
43 All,
44 Clear,
45}
46
47#[doc(hidden)]
48pub struct TreeSelectionChange {
49 pub current: Option<i64>,
50 pub selected_count: Option<usize>,
51}
52
53#[derive(Clone, Copy, Debug, PartialEq, Eq)]
54pub struct TreeItem {
55 pub key: i64,
56 pub row: RowKey,
57 pub model_index: usize,
58 pub parent: Option<i64>,
59 pub depth: usize,
60 pub has_children: bool,
61 pub expanded: bool,
62}
63
64#[derive(Debug, PartialEq, Eq)]
65struct Entry {
66 key: i64,
67 row: RowKey,
68 model_index: usize,
69 parent: Option<usize>,
70 children: Vec<usize>,
71 depth: usize,
72 preorder: usize,
73 subtree_end: usize,
74}
75
76#[derive(Debug, PartialEq, Eq)]
77struct Topology {
78 model: u64,
79 entries: Vec<Entry>,
80 index: HashMap<i64, usize>,
81 roots: Vec<usize>,
82}
83
84impl Topology {
85 fn new<T>(model: &VecModel<T>, model_id: u64, roles: impl Fn(&T) -> (i64, i64)) -> Self {
86 let mut candidates = Vec::new();
87 let mut seen = HashSet::new();
88 let mut duplicates = HashSet::new();
89 model.visit_rows_untracked(MAX_ROWS, |index, row, item| {
90 let (key, parent) = roles(item);
91 if key < 0 {
92 return;
93 }
94 if !seen.insert(key) {
95 duplicates.insert(key);
96 }
97 candidates.push((index, row, key, parent));
98 });
99 candidates.retain(|(_, _, key, _)| !duplicates.contains(key));
100 let index: HashMap<_, _> = candidates
101 .iter()
102 .enumerate()
103 .map(|(index, (_, _, key, _))| (*key, index))
104 .collect();
105 let mut entries: Vec<_> = candidates
106 .into_iter()
107 .map(|(model_index, row, key, parent)| Entry {
108 key,
109 row,
110 model_index,
111 parent: index.get(&parent).copied(),
112 children: Vec::new(),
113 depth: 0,
114 preorder: 0,
115 subtree_end: 0,
116 })
117 .collect();
118
119 let mut state = vec![0_u8; entries.len()];
121 let mut chain = Vec::new();
122 for start in 0..entries.len() {
123 let mut current = Some(start);
124 while let Some(node) = current {
125 if state[node] == 2 {
126 break;
127 }
128 if state[node] == 1 {
129 let cycle = chain
130 .iter()
131 .copied()
132 .rev()
133 .take_while(|&index| index != node);
134 let root = cycle
135 .chain(std::iter::once(node))
136 .min_by_key(|&index| entries[index].key)
137 .unwrap();
138 entries[root].parent = None;
139 break;
140 }
141 state[node] = 1;
142 chain.push(node);
143 current = entries[node].parent;
144 }
145 for node in chain.drain(..) {
146 state[node] = 2;
147 }
148 }
149 let mut roots = Vec::new();
150 for child in 0..entries.len() {
151 if let Some(parent) = entries[child].parent {
152 entries[parent].children.push(child);
153 } else {
154 roots.push(child);
155 }
156 }
157 let mut preorder = 0;
158 let mut pending: Vec<_> = roots.iter().rev().map(|&index| (index, false)).collect();
159 while let Some((index, exiting)) = pending.pop() {
160 if exiting {
161 entries[index].subtree_end = preorder;
162 continue;
163 }
164 entries[index].preorder = preorder;
165 entries[index].depth = entries[index]
166 .parent
167 .map_or(0, |parent| entries[parent].depth + 1);
168 preorder += 1;
169 pending.push((index, true));
170 pending.extend(
171 entries[index]
172 .children
173 .iter()
174 .rev()
175 .map(|&child| (child, false)),
176 );
177 }
178 Self {
179 model: model_id,
180 entries,
181 index,
182 roots,
183 }
184 }
185
186 fn contains_descendant(&self, root: usize, index: usize) -> bool {
187 let root = &self.entries[root];
188 let entry = &self.entries[index];
189 root.preorder < entry.preorder && entry.preorder < root.subtree_end
190 }
191
192 fn roots_for(&self, root_key: i64, root: Option<usize>) -> &[usize] {
193 if root_key == -1 {
194 &self.roots
195 } else {
196 root.map_or(&[], |index| self.entries[index].children.as_slice())
197 }
198 }
199
200 fn row_key(&self, key: i64) -> Option<RowKey> {
201 self.index.get(&key).map(|&index| self.entries[index].row)
202 }
203}
204
205#[derive(Debug, PartialEq, Eq)]
207pub struct TreeSnapshot {
208 topology: Arc<Topology>,
209 expanded: Arc<BTreeMap<i64, RowKey>>,
210 root_key: i64,
211 root: Option<usize>,
212 available: Option<Arc<[bool]>>,
213 filtering: bool,
214 visible: Vec<TreeItem>,
215 visible_indices: HashMap<i64, usize>,
216}
217
218impl TreeSnapshot {
219 fn new(
220 topology: Arc<Topology>,
221 expanded: Arc<BTreeMap<i64, RowKey>>,
222 root_key: i64,
223 available: Option<Arc<[bool]>>,
224 included: Option<Vec<bool>>,
225 ) -> Self {
226 let root = topology.index.get(&root_key).copied();
227 let roots = topology.roots_for(root_key, root);
228 let is_included = |index: usize| {
229 available.as_ref().is_none_or(|rows| rows[index])
230 && included.as_ref().is_none_or(|rows| rows[index])
231 };
232 let filtering = included.is_some();
233 let mut visible = Vec::new();
234 let mut pending: Vec<_> = roots
235 .iter()
236 .rev()
237 .copied()
238 .filter(|&index| is_included(index))
239 .map(|index| (index, 0))
240 .collect();
241 while let Some((index, depth)) = pending.pop() {
242 let node = &topology.entries[index];
243 let has_children = node.children.iter().copied().any(is_included);
244 let expanded =
245 has_children && (filtering || expanded.get(&node.key) == Some(&node.row));
246 visible.push(TreeItem {
247 key: node.key,
248 row: node.row,
249 model_index: node.model_index,
250 parent: node
251 .parent
252 .filter(|parent| Some(*parent) != root)
253 .map(|index| topology.entries[index].key),
254 depth,
255 has_children,
256 expanded,
257 });
258 if expanded {
259 pending.extend(
260 node.children
261 .iter()
262 .rev()
263 .copied()
264 .filter(|&index| is_included(index))
265 .map(|index| (index, depth + 1)),
266 );
267 }
268 }
269 let visible_indices = visible
270 .iter()
271 .enumerate()
272 .map(|(index, item)| (item.key, index))
273 .collect();
274 Self {
275 topology,
276 expanded,
277 root_key,
278 root,
279 available,
280 filtering,
281 visible,
282 visible_indices,
283 }
284 }
285
286 pub fn rows(&self) -> &[TreeItem] {
287 &self.visible
288 }
289
290 pub fn visible_index(&self, key: i64) -> Option<usize> {
291 self.visible_indices.get(&key).copied()
292 }
293
294 pub fn visible_index_for_source(&self, source: usize) -> Option<usize> {
295 self.visible_index(self.entry_for_source(source)?.key)
296 }
297
298 fn entry_for_source(&self, source: usize) -> Option<&Entry> {
299 let index = self
300 .topology
301 .entries
302 .binary_search_by_key(&source, |entry| entry.model_index)
303 .ok()?;
304 self.topology.entries.get(index)
305 }
306
307 pub(crate) fn position_of_source_key(&self, key: RowKey, source_index: usize) -> Option<usize> {
308 if key.model != self.topology.model {
309 return None;
310 }
311 if let Some(entry) = self.entry_for_source(source_index)
312 && entry.row == key
313 {
314 return self.visible_index(entry.key);
315 }
316 self.visible.iter().position(|item| item.row == key)
317 }
318
319 pub fn root_key(&self) -> i64 {
320 self.root_key
321 }
322
323 #[doc(hidden)]
324 pub fn root_identity(&self) -> (i64, Option<RowKey>) {
325 (
326 self.root_key,
327 self.root.map(|index| self.topology.entries[index].row),
328 )
329 }
330
331 fn structural_index(&self, key: i64) -> Option<usize> {
332 let index = *self.topology.index.get(&key)?;
333 (self.root_key == -1
334 || self
335 .root
336 .is_some_and(|root| self.topology.contains_descendant(root, index)))
337 .then_some(index)
338 }
339
340 fn entry_index(&self, key: i64) -> Option<usize> {
341 self.structural_index(key)
342 .filter(|&index| self.is_available(index))
343 }
344
345 fn is_available(&self, index: usize) -> bool {
346 self.available.as_ref().is_none_or(|rows| rows[index])
347 }
348
349 fn has_available_children(&self, index: usize) -> bool {
350 self.topology.entries[index]
351 .children
352 .iter()
353 .any(|&child| self.is_available(child))
354 }
355
356 fn root_entries(&self) -> &[usize] {
357 self.topology.roots_for(self.root_key, self.root)
358 }
359
360 pub fn is_filtering(&self) -> bool {
361 self.filtering
362 }
363
364 pub fn is_expanded(&self, key: i64) -> bool {
365 if self.filtering {
366 return self
367 .visible_index(key)
368 .is_some_and(|index| self.visible[index].expanded);
369 }
370 self.entry_index(key).is_some_and(|index| {
371 let entry = &self.topology.entries[index];
372 self.has_available_children(index) && self.expanded.get(&key) == Some(&entry.row)
373 })
374 }
375
376 pub fn depth(&self, key: i64) -> Option<usize> {
377 let index = self.entry_index(key)?;
378 let base = self
379 .root
380 .map_or(0, |root| self.topology.entries[root].depth + 1);
381 Some(self.topology.entries[index].depth - base)
382 }
383
384 pub fn nearest_visible_ancestor(&self, key: i64) -> Option<i64> {
385 let mut index = self.structural_index(key)?;
386 loop {
387 let entry = &self.topology.entries[index];
388 if self.visible_index(entry.key).is_some() {
389 return Some(entry.key);
390 }
391 index = entry.parent.filter(|index| Some(*index) != self.root)?;
392 }
393 }
394
395 #[doc(hidden)]
396 pub fn same_model(&self, other: &Self) -> bool {
397 self.topology.model == other.topology.model
398 }
399
400 pub fn is_descendant(&self, key: i64, ancestor: i64) -> bool {
401 let Some(index) = self.entry_index(key) else {
402 return false;
403 };
404 let Some(ancestor) = self.entry_index(ancestor) else {
405 return false;
406 };
407 self.topology.contains_descendant(ancestor, index)
408 }
409}
410
411#[derive(Default)]
412struct Selection {
413 keys: Arc<BTreeMap<i64, RowKey>>,
414 anchor: Option<(i64, RowKey)>,
415}
416
417impl Selection {
418 fn retain_live(&mut self, topology: &Topology) {
419 let live = |key, row| topology.row_key(key) == Some(row);
420 if self.keys.iter().any(|(&key, &row)| !live(key, row)) {
421 Arc::make_mut(&mut self.keys).retain(|&key, row| live(key, *row));
422 }
423 self.anchor = self.anchor.filter(|&(key, row)| live(key, row));
424 }
425}
426
427struct FilterObservation {
428 topology: Weak<Topology>,
429 available: Option<Arc<[bool]>>,
430 root: i64,
431 query: Rc<str>,
432 changed: Rc<ChangeSignal>,
433}
434
435#[doc(hidden)]
436#[derive(Default)]
437pub struct TreeState {
438 topology: Property<Arc<Topology>>,
439 roles_changed: RefCell<Option<(u64, Rc<ChangeSignal>)>>,
440 visibility_changed: RefCell<Option<Rc<ChangeSignal>>>,
441 availability: Property<Arc<[bool]>>,
442 filter_observation: RefCell<Option<FilterObservation>>,
443 snapshot: Property<Arc<TreeSnapshot>>,
444 expanded: Property<Arc<BTreeMap<i64, RowKey>>>,
445 selection: RefCell<Selection>,
446 selection_changed: ChangeSignal,
447}
448
449impl TreeState {
450 pub fn snapshot<T>(
452 &self,
453 model: impl FnOnce() -> Rc<VecModel<T>>,
454 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
455 ) -> Arc<TreeSnapshot> {
456 self.snapshot_with_root(model, roles, || -1)
457 }
458
459 pub fn snapshot_with_root<T>(
460 &self,
461 model: impl FnOnce() -> Rc<VecModel<T>>,
462 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
463 root: impl FnOnce() -> i64,
464 ) -> Arc<TreeSnapshot> {
465 self.snapshot
466 .get(|| self.build_snapshot(self.topology(model, roles), root(), None, None))
467 }
468
469 pub fn snapshot_filtered<T: 'static>(
470 &self,
471 model: impl FnOnce() -> Rc<VecModel<T>>,
472 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
473 root: impl FnOnce() -> i64,
474 query: impl FnOnce() -> String,
475 field: fn(&T) -> &str,
476 ) -> Arc<TreeSnapshot> {
477 self.snapshot_projected(model, roles, root, None, Some(field), query)
478 }
479
480 pub fn snapshot_projected<T: 'static>(
481 &self,
482 model: impl FnOnce() -> Rc<VecModel<T>>,
483 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
484 root: impl FnOnce() -> i64,
485 visible: Option<fn(&T) -> bool>,
486 field: Option<fn(&T) -> &str>,
487 query: impl FnOnce() -> String,
488 ) -> Arc<TreeSnapshot> {
489 self.snapshot.get(|| {
490 let root = root();
491 let model = std::cell::LazyCell::new(model);
492 let topology = self.topology(|| Rc::clone(&model), roles.clone());
493 let available = visible.map(|visible| {
494 self.availability.get(|| {
495 let topology = self.topology(|| Rc::clone(&model), roles);
496 let mut shown = vec![false; topology.entries.len()];
497 let mut pending = topology.roots.clone();
498 while let Some(index) = pending.pop() {
499 let entry = &topology.entries[index];
500 if model
501 .project_row_untracked(entry.model_index, visible)
502 .unwrap_or(false)
503 {
504 shown[index] = true;
505 pending.extend_from_slice(&entry.children);
506 }
507 }
508 let shown: Arc<[bool]> = shown.into();
509 let observed = Arc::downgrade(&topology);
510 let reachable = shown.clone();
511 let signal = model.observe_projection_changes(
512 MAX_ROWS,
513 move |model_index, before, after| {
514 if visible(before) == visible(after) {
515 return false;
516 }
517 let Some(topology) = observed.upgrade() else {
518 return false;
519 };
520 topology
521 .entries
522 .binary_search_by_key(&model_index, |entry| entry.model_index)
523 .is_ok_and(|index| {
524 topology.entries[index]
525 .parent
526 .is_none_or(|parent| reachable[parent])
527 })
528 },
529 );
530 signal.track();
531 *self.visibility_changed.borrow_mut() = Some(signal);
532 shown
533 })
534 });
535 let query: Rc<str> = field
536 .map_or_else(String::new, |_| query().trim().to_lowercase())
537 .into();
538 let Some(field) = field.filter(|_| !query.is_empty()) else {
539 self.filter_observation.borrow_mut().take();
540 return self.build_snapshot(topology, root, available, None);
541 };
542 let branch = topology.index.get(&root).copied();
543 let matches = |row: &T| field(row).to_lowercase().contains(query.as_ref());
544 {
545 let mut observation = self.filter_observation.borrow_mut();
546 let topology_ref = Arc::downgrade(&topology);
547 if observation.as_ref().is_none_or(|current| {
548 !Weak::ptr_eq(¤t.topology, &topology_ref)
549 || match (¤t.available, &available) {
550 (Some(a), Some(b)) => !Arc::ptr_eq(a, b),
551 (None, None) => false,
552 _ => true,
553 }
554 || current.root != root
555 || current.query != query
556 }) {
557 let needle = query.clone();
558 let observed = topology_ref.clone();
559 let shown = available.clone();
560 *observation = Some(FilterObservation {
561 topology: topology_ref,
562 available: available.clone(),
563 root,
564 query: query.clone(),
565 changed: model.observe_projection_changes(
566 MAX_ROWS,
567 move |model_index, before, after| {
568 let Some(topology) = observed.upgrade() else {
569 return false;
570 };
571 let Ok(index) = topology
572 .entries
573 .binary_search_by_key(&model_index, |entry| entry.model_index)
574 else {
575 return false;
576 };
577 let in_scope = root == -1
578 || branch.is_some_and(|branch| {
579 topology.contains_descendant(branch, index)
580 });
581 let matches =
582 |row: &T| field(row).to_lowercase().contains(needle.as_ref());
583 in_scope
584 && shown.as_ref().is_none_or(|rows| rows[index])
585 && matches(before) != matches(after)
586 },
587 ),
588 });
589 }
590 observation.as_ref().unwrap().changed.track();
591 }
592 let mut included = vec![false; topology.entries.len()];
593 let mut pending = topology.roots_for(root, branch).to_vec();
594 while let Some(index) = pending.pop() {
595 if available.as_ref().is_some_and(|rows| !rows[index]) {
596 continue;
597 }
598 let entry = &topology.entries[index];
599 pending.extend_from_slice(&entry.children);
600 if !model
601 .project_row_untracked(entry.model_index, matches)
602 .unwrap_or(false)
603 {
604 continue;
605 }
606 let mut ancestor = Some(index);
607 while let Some(index) = ancestor {
608 if Some(index) == branch || included[index] {
609 break;
610 }
611 included[index] = true;
612 ancestor = topology.entries[index].parent;
613 }
614 }
615 self.build_snapshot(topology, root, available, Some(included))
616 })
617 }
618
619 fn topology<T>(
620 &self,
621 model: impl FnOnce() -> Rc<VecModel<T>>,
622 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
623 ) -> Arc<Topology> {
624 self.topology.get(|| {
625 let model = model();
626 let model_id = model.structure_stamp().0;
627 {
628 let mut observation = self.roles_changed.borrow_mut();
629 if let Some((_, signal)) = observation.as_ref().filter(|(id, _)| *id == model_id) {
630 signal.track();
631 } else {
632 let signal = model.observe_projection(MAX_ROWS, roles.clone());
633 signal.track();
634 *observation = Some((model_id, signal));
635 }
636 }
637 let topology = Arc::new(Topology::new(&model, model_id, roles));
638 self.selection.borrow_mut().retain_live(&topology);
639 topology
640 })
641 }
642
643 fn build_snapshot(
644 &self,
645 topology: Arc<Topology>,
646 root: i64,
647 available: Option<Arc<[bool]>>,
648 included: Option<Vec<bool>>,
649 ) -> Arc<TreeSnapshot> {
650 Arc::new(TreeSnapshot::new(
651 topology,
652 self.expanded.get(|| Arc::new(BTreeMap::new())),
653 root,
654 available,
655 included,
656 ))
657 }
658
659 pub fn set_expanded(&self, tree: &TreeSnapshot, key: i64, row: RowKey, expanded: bool) -> bool {
660 if !tree
661 .visible_index(key)
662 .and_then(|index| tree.rows().get(index))
663 .is_some_and(|item| item.row == row && item.has_children && item.expanded != expanded)
664 {
665 return false;
666 }
667 let command = if expanded {
668 TreeCommand::Expand(key)
669 } else {
670 TreeCommand::Collapse(key)
671 };
672 self.command(tree, command).is_some()
673 }
674
675 pub fn command(
676 &self,
677 tree: &TreeSnapshot,
678 command: TreeCommand,
679 ) -> Option<TreeExpansionChange> {
680 if tree.is_filtering()
681 || !self
682 .topology
683 .matches_current(|current| Arc::ptr_eq(current, &tree.topology))
684 || tree.available.as_ref().is_some_and(|shown| {
685 !self
686 .availability
687 .matches_current(|current| Arc::ptr_eq(current, shown))
688 })
689 {
690 return None;
691 }
692 let topology = &tree.topology;
693 let mut state = self.expanded.get(|| Arc::new(BTreeMap::new()));
694 let expanded = Arc::make_mut(&mut state);
695 expanded.retain(|key, row| topology.row_key(*key) == Some(*row));
696 let (key, expand, pending, depth_limit) = match command {
697 TreeCommand::Expand(key)
698 | TreeCommand::Collapse(key)
699 | TreeCommand::ToggleExpanded(key) => {
700 let index = tree.entry_index(key)?;
701 let entry = &topology.entries[index];
702 let expand = match command {
703 TreeCommand::ToggleExpanded(_) => expanded.get(&key) != Some(&entry.row),
704 TreeCommand::Expand(_) => true,
705 _ => false,
706 };
707 (key, expand, vec![index], Some(1_usize))
708 }
709 TreeCommand::ExpandRecursively { key, depth } => {
710 if depth < -1 || depth == 0 {
711 return None;
712 }
713 let roots = if key == -1 {
714 tree.root_entries().to_vec()
715 } else {
716 vec![tree.entry_index(key)?]
717 };
718 (key, true, roots, usize::try_from(depth).ok())
719 }
720 TreeCommand::CollapseRecursively(key) => {
721 let roots = if key == -1 {
722 tree.root_entries().to_vec()
723 } else {
724 vec![tree.entry_index(key)?]
725 };
726 (key, false, roots, None)
727 }
728 TreeCommand::ExpandTo(key) => {
729 let mut index = tree.entry_index(key)?;
730 let mut ancestors = Vec::new();
731 while let Some(parent) = topology.entries[index]
732 .parent
733 .filter(|parent| Some(*parent) != tree.root)
734 {
735 ancestors.push(parent);
736 index = parent;
737 }
738 (key, true, ancestors, Some(1))
739 }
740 };
741 let mut pending: Vec<_> = pending.into_iter().map(|index| (index, 0_usize)).collect();
742 let mut changed = false;
743 while let Some((index, depth)) = pending.pop() {
744 let entry = &topology.entries[index];
745 if !tree.is_available(index) || !tree.has_available_children(index) {
746 continue;
747 }
748 if expand {
749 changed |= expanded.insert(entry.key, entry.row) != Some(entry.row);
750 } else {
751 changed |= expanded.remove(&entry.key).is_some();
752 }
753 if depth_limit.is_none_or(|limit| depth + 1 < limit) {
754 pending.extend(entry.children.iter().map(|&child| (child, depth + 1)));
755 }
756 }
757 if !changed {
758 return None;
759 }
760 self.expanded.set(state);
761 Some(TreeExpansionChange {
762 key,
763 expanded: expand,
764 })
765 }
766
767 pub fn selection(&self) -> Arc<BTreeMap<i64, RowKey>> {
768 self.selection_changed.track();
769 self.selection.borrow().keys.clone()
770 }
771
772 pub fn select(
773 &self,
774 tree: &TreeSnapshot,
775 current: i64,
776 action: TreeSelectionAction,
777 ) -> Option<TreeSelectionChange> {
778 let mut selection = self.selection.borrow_mut();
779 let mut next = selection.keys.clone();
780 let current = match action {
781 TreeSelectionAction::Row {
782 key,
783 row,
784 operation,
785 } => {
786 let index = tree.visible_index(key)?;
787 if tree.rows()[index].row != row {
788 return None;
789 }
790 match operation {
791 RowSelection::Replace => {
792 next = Arc::new(BTreeMap::from([(key, row)]));
793 selection.anchor = Some((key, row));
794 }
795 RowSelection::Toggle => {
796 let selected = Arc::make_mut(&mut next);
797 if selected.remove(&key).is_none() {
798 selected.insert(key, row);
799 }
800 selection.anchor = Some((key, row));
801 }
802 RowSelection::Extend | RowSelection::AddRange => {
803 let start = selection
804 .anchor
805 .and_then(|(key, _)| tree.visible_index(key))
806 .or_else(|| tree.visible_index(current))
807 .unwrap_or(index);
808 let anchor = &tree.rows()[start];
809 selection.anchor = Some((anchor.key, anchor.row));
810 let rows = tree.rows()[start.min(index)..=start.max(index)]
811 .iter()
812 .map(|item| (item.key, item.row));
813 if operation == RowSelection::Extend {
814 next = Arc::new(rows.collect());
815 } else {
816 Arc::make_mut(&mut next).extend(rows);
817 }
818 }
819 RowSelection::Move => {}
820 }
821 (key != current).then_some(key)
822 }
823 TreeSelectionAction::All => {
824 next = Arc::new(
825 tree.rows()
826 .iter()
827 .map(|item| (item.key, item.row))
828 .collect(),
829 );
830 selection.anchor = None;
831 None
832 }
833 TreeSelectionAction::Clear => {
834 next = Arc::new(BTreeMap::new());
835 selection.anchor = None;
836 None
837 }
838 };
839 let selected_count = (next != selection.keys).then_some(next.len());
840 if selected_count.is_some() {
841 selection.keys = next;
842 self.selection_changed.notify();
843 }
844 Some(TreeSelectionChange {
845 current,
846 selected_count,
847 })
848 }
849}
850
851#[cfg(test)]
852mod tests {
853 use super::*;
854 use std::cell::Cell;
855
856 #[test]
857 fn projection_handles_cycles_orphans_and_duplicates_without_rebuilding_on_expand() {
858 let model = Rc::new(VecModel::from(vec![
859 (9, 8),
860 (8, 9),
861 (10, 9),
862 (3, -1),
863 (3, -1),
864 (6, 3),
865 (7, 7),
866 ]));
867 let state = TreeState::default();
868 let reads = Rc::new(Cell::new(0));
869 let role_reads = reads.clone();
870 let roles = move |item: &(i64, i64)| {
871 role_reads.set(role_reads.get() + 1);
872 *item
873 };
874 let tree = state.snapshot(|| model.clone(), roles.clone());
875 assert_eq!(
876 tree.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
877 [8, 6, 7]
878 );
879 assert!(tree.is_descendant(10, 8));
880 assert!(!tree.is_descendant(8, 9));
881 let root = tree.rows()[0];
882 assert!(state.set_expanded(&tree, root.key, root.row, true));
883 let expanded = state.snapshot(|| model.clone(), roles.clone());
884 assert_eq!(reads.get(), 7);
885 assert_eq!(
886 expanded
887 .rows()
888 .iter()
889 .map(|row| row.key)
890 .collect::<Vec<_>>(),
891 [8, 9, 6, 7]
892 );
893 assert!(model.set_row(2, (10, 6)));
894 assert_eq!(reads.get(), 9);
895 let reparented = state.snapshot(|| model.clone(), roles);
896 assert_eq!(reads.get(), 16);
897 assert!(!reparented.is_descendant(10, 8));
898 assert!(reparented.is_descendant(10, 6));
899 assert!(reparented.rows()[0].expanded);
900 }
901
902 #[test]
903 fn recursive_commands_clear_hidden_descendants_and_preserve_depth_limits() {
904 let model = Rc::new(VecModel::from(vec![
905 (1, -1),
906 (2, 1),
907 (3, 2),
908 (4, 1),
909 (9, -1),
910 (10, 9),
911 ]));
912 let state = TreeState::default();
913 let tree = || state.snapshot(|| model.clone(), |row| *row);
914 let initial = tree();
915 assert_eq!(initial.depth(3), Some(2));
916 assert_eq!(initial.depth(99), None);
917 assert!(
918 state
919 .command(
920 &initial,
921 TreeCommand::ExpandRecursively { key: 1, depth: 1 }
922 )
923 .is_some()
924 );
925 assert!(tree().is_expanded(1));
926 assert!(!tree().is_expanded(2));
927 assert_eq!(tree().visible_index(3), None);
928
929 assert!(state.command(&tree(), TreeCommand::ExpandTo(3)).is_some());
930 assert_eq!(tree().visible_index(3), Some(2));
931 assert!(state.command(&tree(), TreeCommand::Collapse(1)).is_some());
932 assert!(tree().is_expanded(2));
933 assert_eq!(tree().nearest_visible_ancestor(3), Some(1));
934 assert!(
935 state
936 .command(&tree(), TreeCommand::CollapseRecursively(1))
937 .is_some()
938 );
939 assert!(!tree().is_expanded(2));
940 assert!(state.command(&tree(), TreeCommand::Expand(1)).is_some());
941 assert_eq!(tree().visible_index(3), None);
942
943 let before = tree();
944 for command in [
945 TreeCommand::Expand(99),
946 TreeCommand::ExpandRecursively { key: 1, depth: 0 },
947 TreeCommand::ExpandRecursively { key: 1, depth: -2 },
948 ] {
949 assert!(state.command(&before, command).is_none());
950 }
951 assert!(Arc::ptr_eq(&before, &tree()));
952 assert!(state.command(&tree(), TreeCommand::ExpandTo(3)).is_some());
953 let prior_model = tree();
954 assert_eq!(model.remove(1), Some((2, 1)));
955 model.push((2, 1));
956 assert!(
957 state
958 .command(&prior_model, TreeCommand::CollapseRecursively(-1))
959 .is_none()
960 );
961 assert!(!tree().is_expanded(2));
962 assert_eq!(tree().visible_index(3), None);
963 }
964
965 #[test]
966 fn changing_the_view_root_reuses_topology_and_limits_expansion_to_the_branch() {
967 let model = Rc::new(VecModel::from(vec![
968 (1, -1),
969 (10, 1),
970 (100, 10),
971 (103, 100),
972 (2, -1),
973 (20, 2),
974 ]));
975 let state = TreeState::default();
976 let requested = Property::default();
977 let reads = Rc::new(Cell::new(0));
978 let count = reads.clone();
979 let roles = move |row: &(i64, i64)| {
980 count.set(count.get() + 1);
981 *row
982 };
983 let tree =
984 || state.snapshot_with_root(|| model.clone(), roles.clone(), || requested.get(|| -1));
985 assert!(
986 state
987 .command(
988 &tree(),
989 TreeCommand::ExpandRecursively { key: -1, depth: -1 }
990 )
991 .is_some()
992 );
993 let global = tree();
994 assert_eq!(global.rows().len(), 6);
995
996 requested.set(10);
997 let source = tree();
998 assert!(Arc::ptr_eq(&global.topology, &source.topology));
999 assert_eq!(
1000 source.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
1001 [100, 103]
1002 );
1003 assert_eq!(source.rows()[0].parent, None);
1004 assert_eq!(source.depth(100), Some(0));
1005 assert_eq!(source.depth(103), Some(1));
1006 assert_eq!(source.depth(10), None);
1007 assert_eq!(source.depth(20), None);
1008 assert!(!source.is_descendant(103, 10));
1009 assert!(state.command(&source, TreeCommand::ExpandTo(20)).is_none());
1010 assert!(
1011 state
1012 .command(&source, TreeCommand::CollapseRecursively(-1))
1013 .is_some()
1014 );
1015
1016 requested.set(2);
1017 assert_eq!(tree().rows()[0].key, 20);
1018 assert_eq!(tree().rows()[0].depth, 0);
1019 requested.set(-1);
1020 let restored = tree();
1021 assert!(restored.is_expanded(1));
1022 assert!(restored.is_expanded(10));
1023 assert!(!restored.is_expanded(100));
1024 assert!(restored.is_expanded(2));
1025 assert_eq!(reads.get(), 6);
1026
1027 requested.set(999);
1028 let missing = tree();
1029 assert!(missing.rows().is_empty());
1030 assert!(
1031 state
1032 .command(&missing, TreeCommand::CollapseRecursively(-1))
1033 .is_none()
1034 );
1035 assert_eq!(missing.depth(100), None);
1036 assert_eq!(missing.root_key(), 999);
1037 }
1038
1039 #[test]
1040 fn filtering_uses_live_matches_and_preserves_the_saved_expansion() {
1041 type Row = (i64, i64, &'static str);
1042 let source = Property::default();
1043 let model = Rc::new(VecModel::from(vec![
1044 (1, -1, "project"),
1045 (2, 1, "src"),
1046 (3, 2, "Window.RS"),
1047 (4, 1, "notes"),
1048 (5, -1, "window outside"),
1049 ]));
1050 source.set(model.clone());
1051 let query = Property::default();
1052 query.set(" WINDOW ".to_owned());
1053 let state = TreeState::default();
1054 let read = || {
1055 state.snapshot_filtered(
1056 || source.get(|| unreachable!()),
1057 |row: &Row| (row.0, row.1),
1058 || 1,
1059 || query.get(String::new),
1060 |row| row.2,
1061 )
1062 };
1063 let filtered = read();
1064 assert!(filtered.is_filtering());
1065 assert_eq!(
1066 filtered
1067 .rows()
1068 .iter()
1069 .map(|row| row.key)
1070 .collect::<Vec<_>>(),
1071 [2, 3]
1072 );
1073 assert!(filtered.is_expanded(2));
1074 assert!(state.command(&filtered, TreeCommand::Collapse(2)).is_none());
1075 assert!(model.set_row(3, (4, 1, "README")));
1076 assert!(model.set_row(4, (5, -1, "outside rename")));
1077 assert!(Arc::ptr_eq(&filtered, &read()));
1078 assert!(model.set_row(3, (4, 1, "window docs")));
1079 assert_eq!(read().visible_index(4), Some(2));
1080
1081 query.set(String::new());
1082 let original = read();
1083 assert!(!original.is_filtering());
1084 assert!(!original.is_expanded(2));
1085 assert_eq!(original.visible_index(3), None);
1086
1087 query.set("window".to_owned());
1088 let before = read();
1089 source.set(Rc::new(VecModel::from(vec![
1090 (1, -1, "new project"),
1091 (9, 1, "window"),
1092 ])));
1093 let replaced = read();
1094 assert!(!before.same_model(&replaced));
1095 assert_eq!(replaced.rows()[0].key, 9);
1096 assert_eq!(replaced.rows().len(), 1);
1097 }
1098
1099 #[test]
1100 fn deep_ancestor_expansion_uses_the_topology_without_recursive_calls() {
1101 let model = Rc::new(VecModel::from(
1102 (0..4096).map(|key| (key, key - 1)).collect::<Vec<_>>(),
1103 ));
1104 let state = TreeState::default();
1105 let initial = state.snapshot(|| model.clone(), |row| *row);
1106 let topology = initial.topology.clone();
1107 assert!(
1108 state
1109 .command(&initial, TreeCommand::ExpandTo(4095))
1110 .is_some()
1111 );
1112 let expanded = state.snapshot(|| model.clone(), |row| *row);
1113 assert!(Arc::ptr_eq(&topology, &expanded.topology));
1114 assert_eq!(expanded.visible_index(4095), Some(4095));
1115 assert_eq!(expanded.depth(4095), Some(4095));
1116 assert!(
1117 state
1118 .command(&expanded, TreeCommand::CollapseRecursively(-1))
1119 .is_some()
1120 );
1121 let collapsed = state.snapshot(|| model.clone(), |row| *row);
1122 assert_eq!(collapsed.rows().len(), 1);
1123 assert!(!collapsed.is_expanded(4094));
1124 }
1125
1126 #[test]
1127 fn payload_changes_leave_independent_tree_projections_clean() {
1128 let model = Rc::new(VecModel::from(vec![(1, -1, -1, 0), (2, 1, -1, 0)]));
1129 let source = Property::default();
1130 source.set(model.clone());
1131 let primary = TreeState::default();
1132 let alternate = TreeState::default();
1133 let roles = |row: &(i64, i64, i64, i64)| (row.0, row.1);
1134 let other_roles = |row: &(i64, i64, i64, i64)| (row.0, row.2);
1135 let primary_tree = || primary.snapshot(|| source.get(|| unreachable!()), roles);
1136 let alternate_tree = || alternate.snapshot(|| model.clone(), other_roles);
1137 let first = primary_tree();
1138 let second = alternate_tree();
1139
1140 assert!(model.set_row(1, (2, 1, -1, 50)));
1141 assert!(Arc::ptr_eq(&first, &primary_tree()));
1142 assert!(Arc::ptr_eq(&second, &alternate_tree()));
1143 assert!(model.set_row(1, (2, 1, 1, 50)));
1144 assert!(Arc::ptr_eq(&first, &primary_tree()));
1145 let reparented = alternate_tree();
1146 assert!(!Arc::ptr_eq(&second, &reparented));
1147 assert!(reparented.is_descendant(2, 1));
1148
1149 source.set(Rc::new(VecModel::from(vec![(3, -1, -1, 0)])));
1150 let replacement = primary_tree();
1151 assert!(!replacement.same_model(&first));
1152 assert_eq!(replacement.rows()[0].key, 3);
1153 assert!(model.set_row(1, (2, -1, -1, 50)));
1154 assert!(Arc::ptr_eq(&replacement, &primary_tree()));
1155 assert!(!alternate_tree().is_descendant(2, 1));
1156 assert!(model.sort_by(|left, right| right.0.cmp(&left.0)));
1157 assert_eq!(alternate_tree().rows()[0].key, 2);
1158 assert!(Arc::ptr_eq(&replacement, &primary_tree()));
1159 }
1160
1161 #[test]
1162 fn visibility_masks_branches_without_rebuilding_topology_or_losing_expansion() {
1163 type Record = (i64, i64, bool, &'static str);
1164 let model = Rc::new(VecModel::from(vec![
1165 (1, -1, true, "root"),
1166 (2, 1, true, "branch"),
1167 (3, 2, true, "leaf"),
1168 (4, -1, true, "other"),
1169 ]));
1170 let root = Property::default();
1171 let query = Property::default();
1172 let state = TreeState::default();
1173 let snapshot = || {
1174 state.snapshot_projected(
1175 || model.clone(),
1176 |row| (row.0, row.1),
1177 || root.get(|| -1),
1178 Some(|row: &Record| row.2),
1179 Some(|row: &Record| row.3),
1180 || query.get(String::new),
1181 )
1182 };
1183 let keys =
1184 |tree: &TreeSnapshot| tree.rows().iter().map(|item| item.key).collect::<Vec<_>>();
1185 let first = snapshot();
1186 assert!(state.command(&first, TreeCommand::ExpandTo(3)).is_some());
1187 let expanded = snapshot();
1188 assert_eq!(keys(&expanded), [1, 2, 3, 4]);
1189 assert!(Arc::ptr_eq(
1190 first.available.as_ref().unwrap(),
1191 expanded.available.as_ref().unwrap()
1192 ));
1193 let leaf = model.row_key(2).unwrap();
1194 state
1195 .select(
1196 &expanded,
1197 -1,
1198 TreeSelectionAction::Row {
1199 key: 3,
1200 row: leaf,
1201 operation: RowSelection::Replace,
1202 },
1203 )
1204 .unwrap();
1205
1206 model.set_row(1, (2, 1, false, "branch"));
1207 assert!(state.command(&expanded, TreeCommand::Collapse(2)).is_none());
1208 let hidden = snapshot();
1209 assert!(Arc::ptr_eq(&expanded.topology, &hidden.topology));
1210 assert_eq!(keys(&hidden), [1, 4]);
1211 assert_eq!(hidden.depth(3), None);
1212 assert_eq!(hidden.nearest_visible_ancestor(3), Some(1));
1213 assert!(!hidden.is_expanded(1));
1214 assert!(!hidden.is_filtering());
1215 assert!(
1216 state
1217 .command(&hidden, TreeCommand::CollapseRecursively(-1))
1218 .is_none()
1219 );
1220 assert_eq!(state.selection().get(&3), Some(&leaf));
1221 model.set_row(2, (3, 2, false, "leaf"));
1222 assert!(Arc::ptr_eq(&hidden, &snapshot()));
1223
1224 query.set("needle".into());
1225 let filtered = snapshot();
1226 assert!(filtered.rows().is_empty());
1227 model.set_row(2, (3, 2, true, "needle"));
1228 assert!(Arc::ptr_eq(&filtered, &snapshot()));
1229 model.set_row(1, (2, 1, true, "branch"));
1230 assert_eq!(keys(&snapshot()), [1, 2, 3]);
1231 query.set(String::new());
1232 assert_eq!(keys(&snapshot()), [1, 2, 3, 4]);
1233
1234 root.set(2);
1235 assert_eq!(keys(&snapshot()), [3]);
1236 model.set_row(0, (1, -1, false, "root"));
1237 assert!(snapshot().rows().is_empty());
1238 model.set_row(0, (1, -1, true, "root"));
1239 assert_eq!(keys(&snapshot()), [3]);
1240 }
1241}