1use crate::{
2 ChangeSignal, ControlAction, ListMetrics, Node, Property, RowKey, RowSelection, Value,
3 VecModel, list::MAX_ROWS,
4};
5use std::{
6 cell::RefCell,
7 collections::{BTreeMap, HashMap, HashSet},
8 ops::Range,
9 rc::Rc,
10 sync::{Arc, Weak},
11};
12
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub enum TreeAction {
15 SetExpanded {
16 key: i64,
17 row: RowKey,
18 expanded: bool,
19 },
20 Selection(TreeSelectionAction),
21}
22
23#[derive(Clone, Copy, Debug, PartialEq, Eq)]
25pub enum TreeCommand {
26 Expand(i64),
27 Collapse(i64),
28 ToggleExpanded(i64),
29 ExpandRecursively { key: i64, depth: i64 },
30 CollapseRecursively(i64),
31 ExpandTo(i64),
32}
33
34#[derive(Clone, Copy, Debug, PartialEq, Eq)]
35#[doc(hidden)]
36pub enum TreeCommandMethod {
37 Expand,
38 Collapse,
39 ToggleExpanded,
40 ExpandRecursively,
41 CollapseRecursively,
42 ExpandTo,
43}
44
45impl TreeCommandMethod {
46 pub fn parse(name: &str) -> Option<Self> {
47 Some(match name {
48 "expand" => Self::Expand,
49 "collapse" => Self::Collapse,
50 "toggle-expanded" => Self::ToggleExpanded,
51 "expand-recursively" => Self::ExpandRecursively,
52 "collapse-recursively" => Self::CollapseRecursively,
53 "expand-to" => Self::ExpandTo,
54 _ => return None,
55 })
56 }
57
58 pub fn requires_depth(self) -> bool {
59 self == Self::ExpandRecursively
60 }
61
62 pub fn action(self, key: i64, depth: Option<i64>) -> Option<TreeCommand> {
63 Some(match self {
64 Self::Expand => TreeCommand::Expand(key),
65 Self::Collapse => TreeCommand::Collapse(key),
66 Self::ToggleExpanded => TreeCommand::ToggleExpanded(key),
67 Self::ExpandRecursively => TreeCommand::ExpandRecursively { key, depth: depth? },
68 Self::CollapseRecursively => TreeCommand::CollapseRecursively(key),
69 Self::ExpandTo => TreeCommand::ExpandTo(key),
70 })
71 }
72}
73
74#[doc(hidden)]
75pub struct TreeExpansionChange {
76 pub key: i64,
77 pub expanded: bool,
78}
79
80#[derive(Clone, Copy, Debug, PartialEq, Eq)]
81pub enum TreeSelectionAction {
82 Row {
83 key: i64,
84 row: RowKey,
85 operation: RowSelection,
86 },
87 All,
88 Clear,
89}
90
91#[doc(hidden)]
92pub struct TreeSelectionChange {
93 pub current: Option<i64>,
94 pub selected_count: Option<usize>,
95}
96
97#[doc(hidden)]
98pub enum TreeControlChange {
99 Selection(TreeSelectionChange),
100 Expansion {
101 change: TreeExpansionChange,
102 current: Option<i64>,
103 },
104}
105
106#[doc(hidden)]
107pub enum TreeControlEvent {
108 CurrentKeyChanged(i64),
109 SelectionChanged(usize),
110 Expanded(i64),
111 Collapsed(i64),
112}
113
114impl TreeControlChange {
115 pub fn try_notify<E>(
117 self,
118 mut notify: impl FnMut(TreeControlEvent) -> Result<(), E>,
119 ) -> Result<bool, E> {
120 let (current, event) = match self {
121 Self::Selection(change) => (
122 change.current,
123 change
124 .selected_count
125 .map(TreeControlEvent::SelectionChanged),
126 ),
127 Self::Expansion { change, current } => (
128 current,
129 Some(if change.expanded {
130 TreeControlEvent::Expanded(change.key)
131 } else {
132 TreeControlEvent::Collapsed(change.key)
133 }),
134 ),
135 };
136 if let Some(key) = current {
137 notify(TreeControlEvent::CurrentKeyChanged(key))?;
138 }
139 if let Some(event) = event {
140 notify(event)?;
141 return Ok(true);
142 }
143 Ok(current.is_some())
144 }
145
146 pub fn notify(self, mut notify: impl FnMut(TreeControlEvent)) -> bool {
147 self.try_notify(|event| {
148 notify(event);
149 Ok::<_, std::convert::Infallible>(())
150 })
151 .unwrap_or_else(|error| match error {})
152 }
153}
154
155#[derive(Clone, Copy, Debug, PartialEq, Eq)]
156pub struct TreeItem {
157 pub key: i64,
158 pub row: RowKey,
159 pub model_index: usize,
160 pub parent: Option<i64>,
161 pub depth: usize,
162 pub has_children: bool,
163 pub expanded: bool,
164}
165
166#[derive(Debug, PartialEq, Eq)]
167struct Entry {
168 key: i64,
169 row: RowKey,
170 model_index: usize,
171 parent: Option<usize>,
172 children: Vec<usize>,
173 depth: usize,
174 preorder: usize,
175 subtree_end: usize,
176}
177
178#[derive(Debug, PartialEq, Eq)]
179struct Topology {
180 model: u64,
181 entries: Vec<Entry>,
182 index: HashMap<i64, usize>,
183 roots: Vec<usize>,
184}
185
186impl Topology {
187 fn new<T>(model: &VecModel<T>, model_id: u64, roles: impl Fn(&T) -> (i64, i64)) -> Self {
188 let mut candidates = Vec::new();
189 let mut seen = HashSet::new();
190 let mut duplicates = HashSet::new();
191 model.visit_rows_untracked(MAX_ROWS, |index, row, item| {
192 let (key, parent) = roles(item);
193 if key < 0 {
194 return;
195 }
196 if !seen.insert(key) {
197 duplicates.insert(key);
198 }
199 candidates.push((index, row, key, parent));
200 });
201 candidates.retain(|(_, _, key, _)| !duplicates.contains(key));
202 let index: HashMap<_, _> = candidates
203 .iter()
204 .enumerate()
205 .map(|(index, (_, _, key, _))| (*key, index))
206 .collect();
207 let mut entries: Vec<_> = candidates
208 .into_iter()
209 .map(|(model_index, row, key, parent)| Entry {
210 key,
211 row,
212 model_index,
213 parent: index.get(&parent).copied(),
214 children: Vec::new(),
215 depth: 0,
216 preorder: 0,
217 subtree_end: 0,
218 })
219 .collect();
220
221 let mut state = vec![0_u8; entries.len()];
223 let mut chain = Vec::new();
224 for start in 0..entries.len() {
225 let mut current = Some(start);
226 while let Some(node) = current {
227 if state[node] == 2 {
228 break;
229 }
230 if state[node] == 1 {
231 let cycle = chain
232 .iter()
233 .copied()
234 .rev()
235 .take_while(|&index| index != node);
236 let root = cycle
237 .chain(std::iter::once(node))
238 .min_by_key(|&index| entries[index].key)
239 .unwrap();
240 entries[root].parent = None;
241 break;
242 }
243 state[node] = 1;
244 chain.push(node);
245 current = entries[node].parent;
246 }
247 for node in chain.drain(..) {
248 state[node] = 2;
249 }
250 }
251 let mut roots = Vec::new();
252 for child in 0..entries.len() {
253 if let Some(parent) = entries[child].parent {
254 entries[parent].children.push(child);
255 } else {
256 roots.push(child);
257 }
258 }
259 let mut preorder = 0;
260 let mut pending: Vec<_> = roots.iter().rev().map(|&index| (index, false)).collect();
261 while let Some((index, exiting)) = pending.pop() {
262 if exiting {
263 entries[index].subtree_end = preorder;
264 continue;
265 }
266 entries[index].preorder = preorder;
267 entries[index].depth = entries[index]
268 .parent
269 .map_or(0, |parent| entries[parent].depth + 1);
270 preorder += 1;
271 pending.push((index, true));
272 pending.extend(
273 entries[index]
274 .children
275 .iter()
276 .rev()
277 .map(|&child| (child, false)),
278 );
279 }
280 Self {
281 model: model_id,
282 entries,
283 index,
284 roots,
285 }
286 }
287
288 fn contains_descendant(&self, root: usize, index: usize) -> bool {
289 let root = &self.entries[root];
290 let entry = &self.entries[index];
291 root.preorder < entry.preorder && entry.preorder < root.subtree_end
292 }
293
294 fn roots_for(&self, root_key: i64, root: Option<usize>) -> &[usize] {
295 if root_key == -1 {
296 &self.roots
297 } else {
298 root.map_or(&[], |index| self.entries[index].children.as_slice())
299 }
300 }
301
302 fn row_key(&self, key: i64) -> Option<RowKey> {
303 self.index.get(&key).map(|&index| self.entries[index].row)
304 }
305}
306
307#[derive(Debug, PartialEq, Eq)]
309pub struct TreeSnapshot {
310 topology: Arc<Topology>,
311 expanded: Arc<BTreeMap<i64, RowKey>>,
312 root_key: i64,
313 root: Option<usize>,
314 available: Option<Arc<[bool]>>,
315 filtering: bool,
316 visible: Vec<TreeItem>,
317 visible_indices: HashMap<i64, usize>,
318}
319
320impl TreeSnapshot {
321 #[doc(hidden)]
323 pub fn matches_scene_order(&self, scene: Option<&Node>) -> bool {
324 scene.is_none_or(|node| {
325 node.tree.as_deref().is_some_and(|old| {
326 std::ptr::eq(self, old) || (self.same_model(old) && self.rows() == old.rows())
327 })
328 })
329 }
330
331 fn new(
332 topology: Arc<Topology>,
333 expanded: Arc<BTreeMap<i64, RowKey>>,
334 root_key: i64,
335 available: Option<Arc<[bool]>>,
336 included: Option<Vec<bool>>,
337 ) -> Self {
338 let root = topology.index.get(&root_key).copied();
339 let roots = topology.roots_for(root_key, root);
340 let is_included = |index: usize| {
341 available.as_ref().is_none_or(|rows| rows[index])
342 && included.as_ref().is_none_or(|rows| rows[index])
343 };
344 let filtering = included.is_some();
345 let mut visible = Vec::new();
346 let mut pending: Vec<_> = roots
347 .iter()
348 .rev()
349 .copied()
350 .filter(|&index| is_included(index))
351 .map(|index| (index, 0))
352 .collect();
353 while let Some((index, depth)) = pending.pop() {
354 let node = &topology.entries[index];
355 let has_children = node.children.iter().copied().any(is_included);
356 let expanded =
357 has_children && (filtering || expanded.get(&node.key) == Some(&node.row));
358 visible.push(TreeItem {
359 key: node.key,
360 row: node.row,
361 model_index: node.model_index,
362 parent: node
363 .parent
364 .filter(|parent| Some(*parent) != root)
365 .map(|index| topology.entries[index].key),
366 depth,
367 has_children,
368 expanded,
369 });
370 if expanded {
371 pending.extend(
372 node.children
373 .iter()
374 .rev()
375 .copied()
376 .filter(|&index| is_included(index))
377 .map(|index| (index, depth + 1)),
378 );
379 }
380 }
381 let visible_indices = visible
382 .iter()
383 .enumerate()
384 .map(|(index, item)| (item.key, index))
385 .collect();
386 Self {
387 topology,
388 expanded,
389 root_key,
390 root,
391 available,
392 filtering,
393 visible,
394 visible_indices,
395 }
396 }
397
398 pub fn rows(&self) -> &[TreeItem] {
399 &self.visible
400 }
401
402 #[doc(hidden)]
403 pub fn rows_in_range(&self, range: Range<usize>) -> &[TreeItem] {
404 self.visible
405 .get(range.start..range.end.min(self.visible.len()))
406 .unwrap_or_default()
407 }
408
409 pub fn visible_index(&self, key: i64) -> Option<usize> {
410 self.visible_indices.get(&key).copied()
411 }
412
413 pub fn visible_index_for_source(&self, source: usize) -> Option<usize> {
414 self.visible_index(self.entry_for_source(source)?.key)
415 }
416
417 #[doc(hidden)]
418 pub fn view_index(&self, index: usize, direction: crate::ViewIndex) -> Option<usize> {
419 match direction {
420 crate::ViewIndex::FromSource => self.visible_index_for_source(index),
421 crate::ViewIndex::ToSource => self.rows().get(index).map(|row| row.model_index),
422 }
423 }
424
425 #[doc(hidden)]
427 pub fn event_source_index(&self, live: &Self, index: usize, row: RowKey) -> Option<usize> {
428 let item = self.rows().get(index).filter(|item| item.row == row)?;
429 let current = live.rows().get(live.visible_index(item.key)?)?;
430 (current.row == row && current.model_index == item.model_index).then_some(item.model_index)
431 }
432
433 fn entry_for_source(&self, source: usize) -> Option<&Entry> {
434 let index = self
435 .topology
436 .entries
437 .binary_search_by_key(&source, |entry| entry.model_index)
438 .ok()?;
439 self.topology.entries.get(index)
440 }
441
442 pub(crate) fn position_of_source_key(&self, key: RowKey, source_index: usize) -> Option<usize> {
443 if key.model != self.topology.model {
444 return None;
445 }
446 if let Some(entry) = self.entry_for_source(source_index)
447 && entry.row == key
448 {
449 return self.visible_index(entry.key);
450 }
451 self.visible.iter().position(|item| item.row == key)
452 }
453
454 pub fn root_key(&self) -> i64 {
455 self.root_key
456 }
457
458 #[doc(hidden)]
459 pub fn root_identity(&self) -> (i64, Option<RowKey>) {
460 (
461 self.root_key,
462 self.root.map(|index| self.topology.entries[index].row),
463 )
464 }
465
466 fn structural_index(&self, key: i64) -> Option<usize> {
467 let index = *self.topology.index.get(&key)?;
468 (self.root_key == -1
469 || self
470 .root
471 .is_some_and(|root| self.topology.contains_descendant(root, index)))
472 .then_some(index)
473 }
474
475 fn entry_index(&self, key: i64) -> Option<usize> {
476 self.structural_index(key)
477 .filter(|&index| self.is_available(index))
478 }
479
480 fn is_available(&self, index: usize) -> bool {
481 self.available.as_ref().is_none_or(|rows| rows[index])
482 }
483
484 fn has_available_children(&self, index: usize) -> bool {
485 self.topology.entries[index]
486 .children
487 .iter()
488 .any(|&child| self.is_available(child))
489 }
490
491 fn root_entries(&self) -> &[usize] {
492 self.topology.roots_for(self.root_key, self.root)
493 }
494
495 pub fn is_filtering(&self) -> bool {
496 self.filtering
497 }
498
499 pub fn is_expanded(&self, key: i64) -> bool {
500 if self.filtering {
501 return self
502 .visible_index(key)
503 .is_some_and(|index| self.visible[index].expanded);
504 }
505 self.entry_index(key).is_some_and(|index| {
506 let entry = &self.topology.entries[index];
507 self.has_available_children(index) && self.expanded.get(&key) == Some(&entry.row)
508 })
509 }
510
511 pub fn depth(&self, key: i64) -> Option<usize> {
512 let index = self.entry_index(key)?;
513 let base = self
514 .root
515 .map_or(0, |root| self.topology.entries[root].depth + 1);
516 Some(self.topology.entries[index].depth - base)
517 }
518
519 #[doc(hidden)]
520 pub fn query_depth(&self, key: i64) -> i64 {
521 self.depth(key).map_or(-1, |depth| depth as i64)
522 }
523
524 #[doc(hidden)]
525 pub fn query_row(&self, key: i64) -> i64 {
526 self.visible_index(key).map_or(-1, |index| index as i64)
527 }
528
529 pub fn nearest_visible_ancestor(&self, key: i64) -> Option<i64> {
530 let mut index = self.structural_index(key)?;
531 loop {
532 let entry = &self.topology.entries[index];
533 if self.visible_index(entry.key).is_some() {
534 return Some(entry.key);
535 }
536 index = entry.parent.filter(|index| Some(*index) != self.root)?;
537 }
538 }
539
540 fn nearest_visible_after_expansion(
541 &self,
542 key: i64,
543 expanded: &BTreeMap<i64, RowKey>,
544 ) -> Option<i64> {
545 let mut index = self.structural_index(key)?;
546 let mut path = vec![index];
547 while let Some(parent) = self.topology.entries[index]
548 .parent
549 .filter(|parent| Some(*parent) != self.root)
550 {
551 path.push(parent);
552 index = parent;
553 }
554 let mut visible = None;
555 for index in path.into_iter().rev() {
556 if !self.is_available(index) {
557 break;
558 }
559 let entry = &self.topology.entries[index];
560 visible = Some(entry.key);
561 if expanded.get(&entry.key) != Some(&entry.row) {
562 break;
563 }
564 }
565 visible
566 }
567
568 #[doc(hidden)]
569 pub fn same_model(&self, other: &Self) -> bool {
570 self.topology.model == other.topology.model
571 }
572
573 fn same_visible_rows(&self, other: &Self) -> bool {
574 let identity = |item: &TreeItem| (item.key, item.row);
575 std::ptr::eq(self, other)
576 || self
577 .rows()
578 .iter()
579 .map(identity)
580 .eq(other.rows().iter().map(identity))
581 }
582
583 pub fn is_descendant(&self, key: i64, ancestor: i64) -> bool {
584 let Some(index) = self.entry_index(key) else {
585 return false;
586 };
587 let Some(ancestor) = self.entry_index(ancestor) else {
588 return false;
589 };
590 self.topology.contains_descendant(ancestor, index)
591 }
592}
593
594#[derive(Default)]
595struct Selection {
596 keys: Arc<BTreeMap<i64, RowKey>>,
597 anchor: Option<(i64, RowKey)>,
598}
599
600impl Selection {
601 fn retain_live(&mut self, topology: &Topology) {
602 let live = |key, row| topology.row_key(key) == Some(row);
603 if self.keys.iter().any(|(&key, &row)| !live(key, row)) {
604 Arc::make_mut(&mut self.keys).retain(|&key, row| live(key, *row));
605 }
606 self.anchor = self.anchor.filter(|&(key, row)| live(key, row));
607 }
608}
609
610struct FilterObservation {
611 topology: Weak<Topology>,
612 available: Option<Arc<[bool]>>,
613 root: i64,
614 query: Rc<str>,
615 changed: Rc<ChangeSignal>,
616}
617
618#[doc(hidden)]
619#[derive(Default)]
620pub struct TreeState {
621 source: Property<u64>,
622 topology: Property<Arc<Topology>>,
623 roles_changed: RefCell<Option<(u64, Rc<ChangeSignal>)>>,
624 visibility_changed: RefCell<Option<Rc<ChangeSignal>>>,
625 availability: Property<Arc<[bool]>>,
626 filter_observation: RefCell<Option<FilterObservation>>,
627 snapshot: Property<Arc<TreeSnapshot>>,
628 expanded: Property<Arc<BTreeMap<i64, RowKey>>>,
629 selection: RefCell<Selection>,
630 selection_changed: ChangeSignal,
631}
632
633impl TreeState {
634 pub fn snapshot<T>(
636 &self,
637 model: impl FnOnce() -> Rc<VecModel<T>>,
638 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
639 ) -> Arc<TreeSnapshot> {
640 self.snapshot_with_root(model, roles, || -1)
641 }
642
643 pub fn snapshot_with_root<T>(
644 &self,
645 model: impl FnOnce() -> Rc<VecModel<T>>,
646 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
647 root: impl FnOnce() -> i64,
648 ) -> Arc<TreeSnapshot> {
649 self.try_snapshot_with_root(model(), roles, || Ok::<_, std::convert::Infallible>(root()))
650 .unwrap_or_else(|error| match error {})
651 }
652
653 #[doc(hidden)]
654 pub fn try_snapshot_with_root<T, E>(
655 &self,
656 model: Rc<VecModel<T>>,
657 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
658 root: impl FnOnce() -> Result<i64, E>,
659 ) -> Result<Arc<TreeSnapshot>, E> {
660 self.source.set_if_changed(model.edit_stamp().0);
661 self.snapshot.try_get(|| {
662 self.track_source();
663 let root = root()?;
664 Ok(self.build_snapshot(self.topology(&model, roles), root, None, None))
665 })
666 }
667
668 pub fn snapshot_filtered<T: 'static>(
669 &self,
670 model: impl FnOnce() -> Rc<VecModel<T>>,
671 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
672 root: impl FnOnce() -> i64,
673 query: impl FnOnce() -> String,
674 field: fn(&T) -> &str,
675 ) -> Arc<TreeSnapshot> {
676 self.snapshot_projected(model, roles, root, None, Some(field), query)
677 }
678
679 pub fn snapshot_projected<T: 'static>(
680 &self,
681 model: impl FnOnce() -> Rc<VecModel<T>>,
682 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
683 root: impl FnOnce() -> i64,
684 visible: Option<fn(&T) -> bool>,
685 field: Option<fn(&T) -> &str>,
686 query: impl FnOnce() -> String,
687 ) -> Arc<TreeSnapshot> {
688 self.snapshot_projected_by(model, roles, root, visible, field, query)
689 }
690
691 #[doc(hidden)]
693 pub fn snapshot_projected_by<T: 'static>(
694 &self,
695 model: impl FnOnce() -> Rc<VecModel<T>>,
696 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
697 root: impl FnOnce() -> i64,
698 visible: Option<impl Fn(&T) -> bool + Clone + 'static>,
699 field: Option<impl Fn(&T) -> &str + Clone + 'static>,
700 query: impl FnOnce() -> String,
701 ) -> Arc<TreeSnapshot> {
702 self.try_snapshot_projected_by(
703 model(),
704 roles,
705 || Ok::<_, std::convert::Infallible>(root()),
706 visible,
707 field,
708 || Ok(query()),
709 )
710 .unwrap_or_else(|error| match error {})
711 }
712
713 #[doc(hidden)]
715 pub fn try_snapshot_projected_by<T: 'static, E>(
716 &self,
717 model: Rc<VecModel<T>>,
718 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
719 root: impl FnOnce() -> Result<i64, E>,
720 visible: Option<impl Fn(&T) -> bool + Clone + 'static>,
721 field: Option<impl Fn(&T) -> &str + Clone + 'static>,
722 query: impl FnOnce() -> Result<String, E>,
723 ) -> Result<Arc<TreeSnapshot>, E> {
724 self.source.set_if_changed(model.edit_stamp().0);
725 self.snapshot.try_get(|| {
726 let root = root()?;
727 let query = Self::read_filter(field.is_some(), query)?;
728 Ok(self.project_snapshot(&model, roles, root, visible, field, query))
729 })
730 }
731
732 #[doc(hidden)]
735 pub fn try_project_model<T: 'static, M, E>(
736 &self,
737 resolve: impl Fn() -> Result<M, E>,
738 model: impl Fn(&M) -> &VecModel<T>,
739 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
740 root: impl FnOnce() -> Result<i64, E>,
741 visible: Option<impl Fn(&T) -> bool + Clone + 'static>,
742 field: Option<impl Fn(&T) -> &str + Clone + 'static>,
743 query: impl FnOnce() -> Result<String, E>,
744 ) -> Result<(Arc<TreeSnapshot>, M), E> {
745 let mut source = None;
746 let snapshot = self.snapshot.try_get(|| {
747 let root = root()?;
748 let query = Self::read_filter(field.is_some(), query)?;
749 let resolved = resolve()?;
750 let rows = model(&resolved);
751 self.source.set_if_changed(rows.edit_stamp().0);
752 let snapshot = self.project_snapshot(rows, roles, root, visible, field, query);
753 source = Some(resolved);
754 Ok(snapshot)
755 })?;
756 Ok((snapshot, source.map_or_else(resolve, Ok)?))
757 }
758
759 #[doc(hidden)]
760 pub fn project_model<T: 'static>(
761 &self,
762 model: impl Fn() -> Rc<VecModel<T>>,
763 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
764 root: impl FnOnce() -> i64,
765 visible: Option<fn(&T) -> bool>,
766 field: Option<fn(&T) -> &str>,
767 query: impl FnOnce() -> String,
768 ) -> (Arc<TreeSnapshot>, Rc<VecModel<T>>) {
769 self.try_project_model(
770 || Ok::<_, std::convert::Infallible>(model()),
771 |model| model.as_ref(),
772 roles,
773 || Ok(root()),
774 visible,
775 field,
776 || Ok(query()),
777 )
778 .unwrap_or_else(|error| match error {})
779 }
780
781 fn read_filter<E>(
782 has_field: bool,
783 query: impl FnOnce() -> Result<String, E>,
784 ) -> Result<Rc<str>, E> {
785 Ok(if has_field {
786 query()?.trim().to_lowercase().into()
787 } else {
788 Rc::from("")
789 })
790 }
791
792 fn project_snapshot<T: 'static>(
793 &self,
794 model: &VecModel<T>,
795 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
796 root: i64,
797 visible: Option<impl Fn(&T) -> bool + Clone + 'static>,
798 field: Option<impl Fn(&T) -> &str + Clone + 'static>,
799 query: Rc<str>,
800 ) -> Arc<TreeSnapshot> {
801 self.track_source();
802 let topology = self.topology(model, roles.clone());
803 let available = visible.map(|visible| {
804 self.availability.get(|| {
805 let topology = self.topology(model, roles);
806 let mut shown = vec![false; topology.entries.len()];
807 let mut pending = topology.roots.clone();
808 while let Some(index) = pending.pop() {
809 let entry = &topology.entries[index];
810 if model
811 .project_row_untracked(entry.model_index, &visible)
812 .unwrap_or(false)
813 {
814 shown[index] = true;
815 pending.extend_from_slice(&entry.children);
816 }
817 }
818 let shown: Arc<[bool]> = shown.into();
819 let observed = Arc::downgrade(&topology);
820 let reachable = shown.clone();
821 let signal = model.observe_projection_changes(
822 MAX_ROWS,
823 move |model_index, before, after| {
824 if visible(before) == visible(after) {
825 return false;
826 }
827 let Some(topology) = observed.upgrade() else {
828 return false;
829 };
830 topology
831 .entries
832 .binary_search_by_key(&model_index, |entry| entry.model_index)
833 .is_ok_and(|index| {
834 topology.entries[index]
835 .parent
836 .is_none_or(|parent| reachable[parent])
837 })
838 },
839 );
840 signal.track();
841 *self.visibility_changed.borrow_mut() = Some(signal);
842 shown
843 })
844 });
845 let Some(field) = field.filter(|_| !query.is_empty()) else {
846 self.filter_observation.borrow_mut().take();
847 return self.build_snapshot(topology, root, available, None);
848 };
849 let branch = topology.index.get(&root).copied();
850 let matches = |row: &T| field(row).to_lowercase().contains(query.as_ref());
851 {
852 let mut observation = self.filter_observation.borrow_mut();
853 let topology_ref = Arc::downgrade(&topology);
854 if observation.as_ref().is_none_or(|current| {
855 !Weak::ptr_eq(¤t.topology, &topology_ref)
856 || match (¤t.available, &available) {
857 (Some(a), Some(b)) => !Arc::ptr_eq(a, b),
858 (None, None) => false,
859 _ => true,
860 }
861 || current.root != root
862 || current.query != query
863 }) {
864 let needle = query.clone();
865 let observed = topology_ref.clone();
866 let shown = available.clone();
867 let field = field.clone();
868 *observation = Some(FilterObservation {
869 topology: topology_ref,
870 available: available.clone(),
871 root,
872 query: query.clone(),
873 changed: model.observe_projection_changes(
874 MAX_ROWS,
875 move |model_index, before, after| {
876 let Some(topology) = observed.upgrade() else {
877 return false;
878 };
879 let Ok(index) = topology
880 .entries
881 .binary_search_by_key(&model_index, |entry| entry.model_index)
882 else {
883 return false;
884 };
885 let in_scope = root == -1
886 || branch.is_some_and(|branch| {
887 topology.contains_descendant(branch, index)
888 });
889 let matches =
890 |row: &T| field(row).to_lowercase().contains(needle.as_ref());
891 in_scope
892 && shown.as_ref().is_none_or(|rows| rows[index])
893 && matches(before) != matches(after)
894 },
895 ),
896 });
897 }
898 observation.as_ref().unwrap().changed.track();
899 }
900 let mut included = vec![false; topology.entries.len()];
901 let mut pending = topology.roots_for(root, branch).to_vec();
902 while let Some(index) = pending.pop() {
903 if available.as_ref().is_some_and(|rows| !rows[index]) {
904 continue;
905 }
906 let entry = &topology.entries[index];
907 pending.extend_from_slice(&entry.children);
908 if !model
909 .project_row_untracked(entry.model_index, matches)
910 .unwrap_or(false)
911 {
912 continue;
913 }
914 let mut ancestor = Some(index);
915 while let Some(index) = ancestor {
916 if Some(index) == branch || included[index] {
917 break;
918 }
919 included[index] = true;
920 ancestor = topology.entries[index].parent;
921 }
922 }
923 self.build_snapshot(topology, root, available, Some(included))
924 }
925
926 fn track_source(&self) {
927 self.source
928 .get(|| unreachable!("tree source is initialized"));
929 }
930
931 fn topology<T>(
932 &self,
933 model: &VecModel<T>,
934 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
935 ) -> Arc<Topology> {
936 self.topology.get(|| {
937 self.track_source();
938 let model_id = model.structure_stamp().0;
939 {
940 let mut observation = self.roles_changed.borrow_mut();
941 if let Some((_, signal)) = observation.as_ref().filter(|(id, _)| *id == model_id) {
942 signal.track();
943 } else {
944 let signal = model.observe_projection(MAX_ROWS, roles.clone());
945 signal.track();
946 *observation = Some((model_id, signal));
947 }
948 }
949 let topology = Arc::new(Topology::new(model, model_id, roles));
950 self.selection.borrow_mut().retain_live(&topology);
951 topology
952 })
953 }
954
955 fn build_snapshot(
956 &self,
957 topology: Arc<Topology>,
958 root: i64,
959 available: Option<Arc<[bool]>>,
960 included: Option<Vec<bool>>,
961 ) -> Arc<TreeSnapshot> {
962 Arc::new(TreeSnapshot::new(
963 topology,
964 self.expanded.get(|| Arc::new(BTreeMap::new())),
965 root,
966 available,
967 included,
968 ))
969 }
970
971 pub fn set_expanded(&self, tree: &TreeSnapshot, key: i64, row: RowKey, expanded: bool) -> bool {
972 if !tree
973 .visible_index(key)
974 .and_then(|index| tree.rows().get(index))
975 .is_some_and(|item| item.row == row && item.has_children && item.expanded != expanded)
976 {
977 return false;
978 }
979 let command = if expanded {
980 TreeCommand::Expand(key)
981 } else {
982 TreeCommand::Collapse(key)
983 };
984 self.command(tree, command).is_some()
985 }
986
987 pub fn command(
988 &self,
989 tree: &TreeSnapshot,
990 command: TreeCommand,
991 ) -> Option<TreeExpansionChange> {
992 let (expanded, change) = self.prepare_command(tree, command)?;
993 self.expanded.set(expanded);
994 Some(change)
995 }
996
997 #[doc(hidden)]
999 pub fn try_apply_command<E>(
1000 &self,
1001 command: TreeCommand,
1002 live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1003 current: impl FnOnce() -> Result<i64, E>,
1004 ) -> Result<Option<(TreeExpansionChange, Option<i64>)>, E> {
1005 let prepared = crate::try_prepare_action_view(|| {
1006 let tree = live()?;
1007 let Some((expanded, change)) = self.prepare_command(&tree, command) else {
1008 return Ok(None);
1009 };
1010 let current = current()?;
1011 let next = tree
1012 .nearest_visible_after_expansion(current, &expanded)
1013 .filter(|key| *key != current);
1014 Ok(Some((expanded, change, next)))
1015 })?;
1016 Ok(prepared.map(|(expanded, change, next)| {
1017 self.expanded.set(expanded);
1018 (change, next)
1019 }))
1020 }
1021
1022 #[doc(hidden)]
1023 pub fn apply_command(
1024 &self,
1025 command: TreeCommand,
1026 live: impl FnOnce() -> Arc<TreeSnapshot>,
1027 current: impl FnOnce() -> i64,
1028 ) -> Option<(TreeExpansionChange, Option<i64>)> {
1029 self.try_apply_command(
1030 command,
1031 || Ok::<_, std::convert::Infallible>(live()),
1032 || Ok(current()),
1033 )
1034 .unwrap_or_else(|error| match error {})
1035 }
1036
1037 fn prepare_command(
1038 &self,
1039 tree: &TreeSnapshot,
1040 command: TreeCommand,
1041 ) -> Option<(Arc<BTreeMap<i64, RowKey>>, TreeExpansionChange)> {
1042 if tree.is_filtering()
1043 || !self
1044 .topology
1045 .matches_current(|current| Arc::ptr_eq(current, &tree.topology))
1046 || tree.available.as_ref().is_some_and(|shown| {
1047 !self
1048 .availability
1049 .matches_current(|current| Arc::ptr_eq(current, shown))
1050 })
1051 {
1052 return None;
1053 }
1054 let topology = &tree.topology;
1055 let mut state = self.expanded.get(|| Arc::new(BTreeMap::new()));
1056 let expanded = Arc::make_mut(&mut state);
1057 expanded.retain(|key, row| topology.row_key(*key) == Some(*row));
1058 let (key, expand, pending, depth_limit) = match command {
1059 TreeCommand::Expand(key)
1060 | TreeCommand::Collapse(key)
1061 | TreeCommand::ToggleExpanded(key) => {
1062 let index = tree.entry_index(key)?;
1063 let entry = &topology.entries[index];
1064 let expand = match command {
1065 TreeCommand::ToggleExpanded(_) => expanded.get(&key) != Some(&entry.row),
1066 TreeCommand::Expand(_) => true,
1067 _ => false,
1068 };
1069 (key, expand, vec![index], Some(1_usize))
1070 }
1071 TreeCommand::ExpandRecursively { key, depth } => {
1072 if depth < -1 || depth == 0 {
1073 return None;
1074 }
1075 let roots = if key == -1 {
1076 tree.root_entries().to_vec()
1077 } else {
1078 vec![tree.entry_index(key)?]
1079 };
1080 (key, true, roots, usize::try_from(depth).ok())
1081 }
1082 TreeCommand::CollapseRecursively(key) => {
1083 let roots = if key == -1 {
1084 tree.root_entries().to_vec()
1085 } else {
1086 vec![tree.entry_index(key)?]
1087 };
1088 (key, false, roots, None)
1089 }
1090 TreeCommand::ExpandTo(key) => {
1091 let mut index = tree.entry_index(key)?;
1092 let mut ancestors = Vec::new();
1093 while let Some(parent) = topology.entries[index]
1094 .parent
1095 .filter(|parent| Some(*parent) != tree.root)
1096 {
1097 ancestors.push(parent);
1098 index = parent;
1099 }
1100 (key, true, ancestors, Some(1))
1101 }
1102 };
1103 let mut pending: Vec<_> = pending.into_iter().map(|index| (index, 0_usize)).collect();
1104 let mut changed = false;
1105 while let Some((index, depth)) = pending.pop() {
1106 let entry = &topology.entries[index];
1107 if !tree.is_available(index) || !tree.has_available_children(index) {
1108 continue;
1109 }
1110 if expand {
1111 changed |= expanded.insert(entry.key, entry.row) != Some(entry.row);
1112 } else {
1113 changed |= expanded.remove(&entry.key).is_some();
1114 }
1115 if depth_limit.is_none_or(|limit| depth + 1 < limit) {
1116 pending.extend(entry.children.iter().map(|&child| (child, depth + 1)));
1117 }
1118 }
1119 if !changed {
1120 return None;
1121 }
1122 Some((
1123 state,
1124 TreeExpansionChange {
1125 key,
1126 expanded: expand,
1127 },
1128 ))
1129 }
1130
1131 pub fn selection(&self) -> Arc<BTreeMap<i64, RowKey>> {
1132 self.selection_changed.track();
1133 self.selection.borrow().keys.clone()
1134 }
1135
1136 #[doc(hidden)]
1138 pub fn populate_scene(&self, node: &mut Node, tree: Arc<TreeSnapshot>) {
1139 node.list = Some(ListMetrics {
1140 row_count: tree.rows().len(),
1141 first_row: 0,
1142 });
1143 node.properties
1144 .entry("current-key")
1145 .or_insert(Value::Int(-1));
1146 node.tree_selection = node
1147 .boolean("multi-select", false)
1148 .then(|| self.selection());
1149 node.tree = Some(tree);
1150 }
1151
1152 #[doc(hidden)]
1154 pub fn try_apply_control<E>(
1155 &self,
1156 node: &Node,
1157 input: crate::InputRoute<'_>,
1158 available: impl FnOnce() -> Result<bool, E>,
1159 multiple: impl FnOnce() -> Result<bool, E>,
1160 live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1161 current: impl FnOnce() -> Result<i64, E>,
1162 ) -> Result<Option<TreeControlChange>, E> {
1163 let crate::RoutedEvent::Control(action) = *input.event() else {
1164 return Ok(None);
1165 };
1166 let Some(snapshot) = &node.tree else {
1167 return Ok(None);
1168 };
1169 let snapshot_multiple = node.tree_selection.is_some();
1170 let action = match action {
1171 ControlAction::Select(index) => {
1172 let Some(item) = snapshot.rows().get(index) else {
1173 return Ok(None);
1174 };
1175 TreeAction::Selection(TreeSelectionAction::Row {
1176 key: item.key,
1177 row: item.row,
1178 operation: RowSelection::Replace,
1179 })
1180 }
1181 ControlAction::Tree(action @ TreeAction::SetExpanded { .. }) => action,
1182 ControlAction::Tree(action @ TreeAction::Selection(_)) if snapshot_multiple => action,
1183 _ => return Ok(None),
1184 };
1185 let prepared = crate::property::watch_reads(|reads| {
1186 if !available()? || reads.changed() {
1187 return Ok(None);
1188 }
1189 if matches!(action, TreeAction::Selection(_))
1190 && (multiple()? != snapshot_multiple || reads.changed())
1191 {
1192 return Ok(None);
1193 }
1194 let live = live()?;
1195 if reads.changed() {
1196 return Ok(None);
1197 }
1198 if let TreeAction::Selection(selection) = action
1199 && snapshot_multiple
1200 {
1201 let needs_order = matches!(
1202 selection,
1203 TreeSelectionAction::Row {
1204 operation: RowSelection::Extend | RowSelection::AddRange,
1205 ..
1206 }
1207 );
1208 if !snapshot.same_model(&live)
1209 || (needs_order && !snapshot.same_visible_rows(&live))
1210 {
1211 return Ok(None);
1212 }
1213 }
1214 let current = current()?;
1215 Ok((input.is_current() && !reads.changed()).then_some((live, current)))
1216 })?;
1217 let Some((live, current)) = prepared else {
1218 return Ok(None);
1219 };
1220 Ok(match action {
1221 TreeAction::Selection(selection) => self
1222 .select_in_mode(&live, current, snapshot_multiple, selection)
1223 .map(TreeControlChange::Selection),
1224 TreeAction::SetExpanded { key, row, expanded } => self
1225 .set_expanded(&live, key, row, expanded)
1226 .then(|| TreeControlChange::Expansion {
1227 change: TreeExpansionChange { key, expanded },
1228 current: (!expanded && live.is_descendant(current, key)).then_some(key),
1229 }),
1230 })
1231 }
1232
1233 #[doc(hidden)]
1234 pub fn apply_control(
1235 &self,
1236 node: &Node,
1237 input: crate::InputRoute<'_>,
1238 available: impl FnOnce() -> bool,
1239 multiple: impl FnOnce() -> bool,
1240 live: impl FnOnce() -> Arc<TreeSnapshot>,
1241 current: impl FnOnce() -> i64,
1242 ) -> Option<TreeControlChange> {
1243 self.try_apply_control(
1244 node,
1245 input,
1246 || Ok::<_, std::convert::Infallible>(available()),
1247 || Ok(multiple()),
1248 || Ok(live()),
1249 || Ok(current()),
1250 )
1251 .unwrap_or_else(|error| match error {})
1252 }
1253
1254 #[doc(hidden)]
1256 pub fn try_select_source<E>(
1257 &self,
1258 source: usize,
1259 live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1260 multiple: impl FnOnce() -> Result<bool, E>,
1261 current: impl FnOnce() -> Result<i64, E>,
1262 ) -> Result<Option<TreeSelectionChange>, E> {
1263 let prepared = crate::try_prepare_action_view(|| {
1264 let tree = live()?;
1265 let Some(item) = tree
1266 .visible_index_for_source(source)
1267 .and_then(|index| tree.rows().get(index))
1268 else {
1269 return Ok(None);
1270 };
1271 let action = TreeSelectionAction::Row {
1272 key: item.key,
1273 row: item.row,
1274 operation: RowSelection::Replace,
1275 };
1276 let multiple = multiple()?;
1277 let current = current()?;
1278 Ok(Some((tree, multiple, current, action)))
1279 })?;
1280 Ok(prepared.and_then(|(tree, multiple, current, action)| {
1281 self.select_in_mode(&tree, current, multiple, action)
1282 }))
1283 }
1284
1285 #[doc(hidden)]
1286 pub fn select_source(
1287 &self,
1288 source: usize,
1289 live: impl FnOnce() -> Arc<TreeSnapshot>,
1290 multiple: impl FnOnce() -> bool,
1291 current: impl FnOnce() -> i64,
1292 ) -> Option<TreeSelectionChange> {
1293 self.try_select_source(
1294 source,
1295 || Ok::<_, std::convert::Infallible>(live()),
1296 || Ok(multiple()),
1297 || Ok(current()),
1298 )
1299 .unwrap_or_else(|error| match error {})
1300 }
1301
1302 #[doc(hidden)]
1303 pub fn select_in_mode(
1304 &self,
1305 tree: &TreeSnapshot,
1306 current: i64,
1307 multiple: bool,
1308 action: TreeSelectionAction,
1309 ) -> Option<TreeSelectionChange> {
1310 if !self
1311 .snapshot
1312 .matches_current(|live| std::ptr::eq(live.as_ref(), tree))
1313 {
1314 return None;
1315 }
1316 if multiple {
1317 return self.select(tree, current, action);
1318 }
1319 let TreeSelectionAction::Row { key, row, .. } = action else {
1320 return None;
1321 };
1322 let item = tree.rows().get(tree.visible_index(key)?)?;
1323 (item.row == row && key != current).then_some(TreeSelectionChange {
1324 current: Some(key),
1325 selected_count: None,
1326 })
1327 }
1328
1329 pub fn select(
1330 &self,
1331 tree: &TreeSnapshot,
1332 current: i64,
1333 action: TreeSelectionAction,
1334 ) -> Option<TreeSelectionChange> {
1335 let mut selection = self.selection.borrow_mut();
1336 let mut next = selection.keys.clone();
1337 let current = match action {
1338 TreeSelectionAction::Row {
1339 key,
1340 row,
1341 operation,
1342 } => {
1343 let index = tree.visible_index(key)?;
1344 if tree.rows()[index].row != row {
1345 return None;
1346 }
1347 match operation {
1348 RowSelection::Replace => {
1349 next = Arc::new(BTreeMap::from([(key, row)]));
1350 selection.anchor = Some((key, row));
1351 }
1352 RowSelection::Toggle => {
1353 let selected = Arc::make_mut(&mut next);
1354 if selected.remove(&key).is_none() {
1355 selected.insert(key, row);
1356 }
1357 selection.anchor = Some((key, row));
1358 }
1359 RowSelection::Extend | RowSelection::AddRange => {
1360 let start = selection
1361 .anchor
1362 .and_then(|(key, _)| tree.visible_index(key))
1363 .or_else(|| tree.visible_index(current))
1364 .unwrap_or(index);
1365 let anchor = &tree.rows()[start];
1366 selection.anchor = Some((anchor.key, anchor.row));
1367 let rows = tree.rows()[start.min(index)..=start.max(index)]
1368 .iter()
1369 .map(|item| (item.key, item.row));
1370 if operation == RowSelection::Extend {
1371 next = Arc::new(rows.collect());
1372 } else {
1373 Arc::make_mut(&mut next).extend(rows);
1374 }
1375 }
1376 RowSelection::Move => {}
1377 }
1378 (key != current).then_some(key)
1379 }
1380 TreeSelectionAction::All => {
1381 next = Arc::new(
1382 tree.rows()
1383 .iter()
1384 .map(|item| (item.key, item.row))
1385 .collect(),
1386 );
1387 selection.anchor = None;
1388 None
1389 }
1390 TreeSelectionAction::Clear => {
1391 next = Arc::new(BTreeMap::new());
1392 selection.anchor = None;
1393 None
1394 }
1395 };
1396 let selected_count = (next != selection.keys).then_some(next.len());
1397 if selected_count.is_some() {
1398 selection.keys = next;
1399 self.selection_changed.notify();
1400 }
1401 Some(TreeSelectionChange {
1402 current,
1403 selected_count,
1404 })
1405 }
1406}
1407
1408#[cfg(test)]
1409mod tests {
1410 use super::*;
1411 use std::cell::Cell;
1412
1413 #[test]
1414 fn projection_handles_cycles_orphans_and_duplicates_without_rebuilding_on_expand() {
1415 let model = Rc::new(VecModel::from(vec![
1416 (9, 8),
1417 (8, 9),
1418 (10, 9),
1419 (3, -1),
1420 (3, -1),
1421 (6, 3),
1422 (7, 7),
1423 ]));
1424 let state = TreeState::default();
1425 let reads = Rc::new(Cell::new(0));
1426 let role_reads = reads.clone();
1427 let roles = move |item: &(i64, i64)| {
1428 role_reads.set(role_reads.get() + 1);
1429 *item
1430 };
1431 let tree = state.snapshot(|| model.clone(), roles.clone());
1432 assert_eq!(
1433 tree.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
1434 [8, 6, 7]
1435 );
1436 assert!(tree.is_descendant(10, 8));
1437 assert!(!tree.is_descendant(8, 9));
1438 let root = tree.rows()[0];
1439 assert!(state.set_expanded(&tree, root.key, root.row, true));
1440 let expanded = state.snapshot(|| model.clone(), roles.clone());
1441 assert_eq!(reads.get(), 7);
1442 assert_eq!(
1443 expanded
1444 .rows()
1445 .iter()
1446 .map(|row| row.key)
1447 .collect::<Vec<_>>(),
1448 [8, 9, 6, 7]
1449 );
1450 assert!(model.set_row(2, (10, 6)));
1451 assert_eq!(reads.get(), 9);
1452 let reparented = state.snapshot(|| model.clone(), roles);
1453 assert_eq!(reads.get(), 16);
1454 assert!(!reparented.is_descendant(10, 8));
1455 assert!(reparented.is_descendant(10, 6));
1456 assert!(reparented.rows()[0].expanded);
1457 }
1458
1459 #[test]
1460 fn recursive_commands_clear_hidden_descendants_and_preserve_depth_limits() {
1461 let model = Rc::new(VecModel::from(vec![
1462 (1, -1),
1463 (2, 1),
1464 (3, 2),
1465 (4, 1),
1466 (9, -1),
1467 (10, 9),
1468 ]));
1469 let state = TreeState::default();
1470 let tree = || state.snapshot(|| model.clone(), |row| *row);
1471 let initial = tree();
1472 assert_eq!(initial.depth(3), Some(2));
1473 assert_eq!(initial.depth(99), None);
1474 assert!(
1475 state
1476 .command(
1477 &initial,
1478 TreeCommand::ExpandRecursively { key: 1, depth: 1 }
1479 )
1480 .is_some()
1481 );
1482 assert!(tree().is_expanded(1));
1483 assert!(!tree().is_expanded(2));
1484 assert_eq!(tree().visible_index(3), None);
1485
1486 assert!(state.command(&tree(), TreeCommand::ExpandTo(3)).is_some());
1487 assert_eq!(tree().visible_index(3), Some(2));
1488 assert!(state.command(&tree(), TreeCommand::Collapse(1)).is_some());
1489 assert!(tree().is_expanded(2));
1490 assert_eq!(tree().nearest_visible_ancestor(3), Some(1));
1491 assert!(
1492 state
1493 .command(&tree(), TreeCommand::CollapseRecursively(1))
1494 .is_some()
1495 );
1496 assert!(!tree().is_expanded(2));
1497 assert!(state.command(&tree(), TreeCommand::Expand(1)).is_some());
1498 assert_eq!(tree().visible_index(3), None);
1499
1500 let before = tree();
1501 for command in [
1502 TreeCommand::Expand(99),
1503 TreeCommand::ExpandRecursively { key: 1, depth: 0 },
1504 TreeCommand::ExpandRecursively { key: 1, depth: -2 },
1505 ] {
1506 assert!(state.command(&before, command).is_none());
1507 }
1508 assert!(Arc::ptr_eq(&before, &tree()));
1509 assert!(state.command(&tree(), TreeCommand::ExpandTo(3)).is_some());
1510 let prior_model = tree();
1511 assert_eq!(model.remove(1), Some((2, 1)));
1512 model.push((2, 1));
1513 assert!(
1514 state
1515 .command(&prior_model, TreeCommand::CollapseRecursively(-1))
1516 .is_none()
1517 );
1518 assert!(!tree().is_expanded(2));
1519 assert_eq!(tree().visible_index(3), None);
1520 }
1521
1522 #[test]
1523 fn changing_the_view_root_reuses_topology_and_limits_expansion_to_the_branch() {
1524 let model = Rc::new(VecModel::from(vec![
1525 (1, -1),
1526 (10, 1),
1527 (100, 10),
1528 (103, 100),
1529 (2, -1),
1530 (20, 2),
1531 ]));
1532 let state = TreeState::default();
1533 let requested = Property::default();
1534 let reads = Rc::new(Cell::new(0));
1535 let count = reads.clone();
1536 let roles = move |row: &(i64, i64)| {
1537 count.set(count.get() + 1);
1538 *row
1539 };
1540 let tree =
1541 || state.snapshot_with_root(|| model.clone(), roles.clone(), || requested.get(|| -1));
1542 assert!(
1543 state
1544 .command(
1545 &tree(),
1546 TreeCommand::ExpandRecursively { key: -1, depth: -1 }
1547 )
1548 .is_some()
1549 );
1550 let global = tree();
1551 assert_eq!(global.rows().len(), 6);
1552
1553 requested.set(10);
1554 let source = tree();
1555 assert!(Arc::ptr_eq(&global.topology, &source.topology));
1556 assert_eq!(
1557 source.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
1558 [100, 103]
1559 );
1560 assert_eq!(source.rows()[0].parent, None);
1561 assert_eq!(source.depth(100), Some(0));
1562 assert_eq!(source.depth(103), Some(1));
1563 assert_eq!(source.depth(10), None);
1564 assert_eq!(source.depth(20), None);
1565 assert!(!source.is_descendant(103, 10));
1566 assert!(state.command(&source, TreeCommand::ExpandTo(20)).is_none());
1567 assert!(
1568 state
1569 .command(&source, TreeCommand::CollapseRecursively(-1))
1570 .is_some()
1571 );
1572
1573 requested.set(2);
1574 assert_eq!(tree().rows()[0].key, 20);
1575 assert_eq!(tree().rows()[0].depth, 0);
1576 requested.set(-1);
1577 let restored = tree();
1578 assert!(restored.is_expanded(1));
1579 assert!(restored.is_expanded(10));
1580 assert!(!restored.is_expanded(100));
1581 assert!(restored.is_expanded(2));
1582 assert_eq!(reads.get(), 6);
1583
1584 requested.set(999);
1585 let missing = tree();
1586 assert!(missing.rows().is_empty());
1587 assert!(
1588 state
1589 .command(&missing, TreeCommand::CollapseRecursively(-1))
1590 .is_none()
1591 );
1592 assert_eq!(missing.depth(100), None);
1593 assert_eq!(missing.root_key(), 999);
1594 }
1595
1596 #[test]
1597 fn filtering_uses_live_matches_and_preserves_the_saved_expansion() {
1598 type Row = (i64, i64, &'static str);
1599 let source = Property::default();
1600 let model = Rc::new(VecModel::from(vec![
1601 (1, -1, "project"),
1602 (2, 1, "src"),
1603 (3, 2, "Window.RS"),
1604 (4, 1, "notes"),
1605 (5, -1, "window outside"),
1606 ]));
1607 source.set(model.clone());
1608 let query = Property::default();
1609 query.set(" WINDOW ".to_owned());
1610 let state = TreeState::default();
1611 let read = || {
1612 state.snapshot_filtered(
1613 || source.get(|| unreachable!()),
1614 |row: &Row| (row.0, row.1),
1615 || 1,
1616 || query.get(String::new),
1617 |row| row.2,
1618 )
1619 };
1620 let filtered = read();
1621 assert!(filtered.is_filtering());
1622 assert_eq!(
1623 filtered
1624 .rows()
1625 .iter()
1626 .map(|row| row.key)
1627 .collect::<Vec<_>>(),
1628 [2, 3]
1629 );
1630 assert!(filtered.is_expanded(2));
1631 assert!(state.command(&filtered, TreeCommand::Collapse(2)).is_none());
1632 assert!(model.set_row(3, (4, 1, "README")));
1633 assert!(model.set_row(4, (5, -1, "outside rename")));
1634 assert!(Arc::ptr_eq(&filtered, &read()));
1635 assert!(model.set_row(3, (4, 1, "window docs")));
1636 assert_eq!(read().visible_index(4), Some(2));
1637
1638 query.set(String::new());
1639 let original = read();
1640 assert!(!original.is_filtering());
1641 assert!(!original.is_expanded(2));
1642 assert_eq!(original.visible_index(3), None);
1643
1644 query.set("window".to_owned());
1645 let before = read();
1646 source.set(Rc::new(VecModel::from(vec![
1647 (1, -1, "new project"),
1648 (9, 1, "window"),
1649 ])));
1650 let replaced = read();
1651 assert!(!before.same_model(&replaced));
1652 assert_eq!(replaced.rows()[0].key, 9);
1653 assert_eq!(replaced.rows().len(), 1);
1654 }
1655
1656 #[test]
1657 fn filtering_projects_the_model_after_reading_the_query() {
1658 let model = Rc::new(VecModel::from(vec![(1, -1, "one"), (2, 1, "two")]));
1659 let state = TreeState::default();
1660 let tree = state.snapshot_filtered(
1661 || model.clone(),
1662 |row| (row.0, row.1),
1663 || -1,
1664 || {
1665 assert_eq!(model.remove(0), Some((1, -1, "one")));
1666 "two".to_owned()
1667 },
1668 |row| row.2,
1669 );
1670 assert_eq!(tree.rows().len(), 1);
1671 assert_eq!((tree.rows()[0].key, tree.rows()[0].model_index), (2, 0));
1672 }
1673
1674 #[test]
1675 fn deep_ancestor_expansion_uses_the_topology_without_recursive_calls() {
1676 let model = Rc::new(VecModel::from(
1677 (0..4096).map(|key| (key, key - 1)).collect::<Vec<_>>(),
1678 ));
1679 let state = TreeState::default();
1680 let initial = state.snapshot(|| model.clone(), |row| *row);
1681 let topology = initial.topology.clone();
1682 assert!(
1683 state
1684 .command(&initial, TreeCommand::ExpandTo(4095))
1685 .is_some()
1686 );
1687 let expanded = state.snapshot(|| model.clone(), |row| *row);
1688 assert!(Arc::ptr_eq(&topology, &expanded.topology));
1689 assert_eq!(expanded.visible_index(4095), Some(4095));
1690 assert_eq!(expanded.depth(4095), Some(4095));
1691 assert!(
1692 state
1693 .command(&expanded, TreeCommand::CollapseRecursively(-1))
1694 .is_some()
1695 );
1696 let collapsed = state.snapshot(|| model.clone(), |row| *row);
1697 assert_eq!(collapsed.rows().len(), 1);
1698 assert!(!collapsed.is_expanded(4094));
1699 }
1700
1701 #[test]
1702 fn payload_changes_leave_independent_tree_projections_clean() {
1703 let model = Rc::new(VecModel::from(vec![(1, -1, -1, 0), (2, 1, -1, 0)]));
1704 let source = Property::default();
1705 source.set(model.clone());
1706 let primary = TreeState::default();
1707 let alternate = TreeState::default();
1708 let roles = |row: &(i64, i64, i64, i64)| (row.0, row.1);
1709 let other_roles = |row: &(i64, i64, i64, i64)| (row.0, row.2);
1710 let primary_tree = || primary.snapshot(|| source.get(|| unreachable!()), roles);
1711 let alternate_tree = || alternate.snapshot(|| model.clone(), other_roles);
1712 let first = primary_tree();
1713 let second = alternate_tree();
1714
1715 assert!(model.set_row(1, (2, 1, -1, 50)));
1716 assert!(Arc::ptr_eq(&first, &primary_tree()));
1717 assert!(Arc::ptr_eq(&second, &alternate_tree()));
1718 assert!(model.set_row(1, (2, 1, 1, 50)));
1719 assert!(Arc::ptr_eq(&first, &primary_tree()));
1720 let reparented = alternate_tree();
1721 assert!(!Arc::ptr_eq(&second, &reparented));
1722 assert!(reparented.is_descendant(2, 1));
1723
1724 source.set(Rc::new(VecModel::from(vec![(3, -1, -1, 0)])));
1725 let replacement = primary_tree();
1726 assert!(!replacement.same_model(&first));
1727 assert_eq!(replacement.rows()[0].key, 3);
1728 assert!(model.set_row(1, (2, -1, -1, 50)));
1729 assert!(Arc::ptr_eq(&replacement, &primary_tree()));
1730 assert!(!alternate_tree().is_descendant(2, 1));
1731 assert!(model.sort_by(|left, right| right.0.cmp(&left.0)));
1732 assert_eq!(alternate_tree().rows()[0].key, 2);
1733 assert!(Arc::ptr_eq(&replacement, &primary_tree()));
1734 }
1735
1736 #[test]
1737 fn visibility_masks_branches_without_rebuilding_topology_or_losing_expansion() {
1738 type Record = (i64, i64, bool, &'static str);
1739 let model = Rc::new(VecModel::from(vec![
1740 (1, -1, true, "root"),
1741 (2, 1, true, "branch"),
1742 (3, 2, true, "leaf"),
1743 (4, -1, true, "other"),
1744 ]));
1745 let root = Property::default();
1746 let query = Property::default();
1747 let state = TreeState::default();
1748 let snapshot = || {
1749 state.snapshot_projected(
1750 || model.clone(),
1751 |row| (row.0, row.1),
1752 || root.get(|| -1),
1753 Some(|row: &Record| row.2),
1754 Some(|row: &Record| row.3),
1755 || query.get(String::new),
1756 )
1757 };
1758 let keys =
1759 |tree: &TreeSnapshot| tree.rows().iter().map(|item| item.key).collect::<Vec<_>>();
1760 let first = snapshot();
1761 assert!(state.command(&first, TreeCommand::ExpandTo(3)).is_some());
1762 let expanded = snapshot();
1763 assert_eq!(keys(&expanded), [1, 2, 3, 4]);
1764 assert!(Arc::ptr_eq(
1765 first.available.as_ref().unwrap(),
1766 expanded.available.as_ref().unwrap()
1767 ));
1768 let leaf = model.row_key(2).unwrap();
1769 state
1770 .select(
1771 &expanded,
1772 -1,
1773 TreeSelectionAction::Row {
1774 key: 3,
1775 row: leaf,
1776 operation: RowSelection::Replace,
1777 },
1778 )
1779 .unwrap();
1780
1781 model.set_row(1, (2, 1, false, "branch"));
1782 assert!(state.command(&expanded, TreeCommand::Collapse(2)).is_none());
1783 let hidden = snapshot();
1784 assert!(Arc::ptr_eq(&expanded.topology, &hidden.topology));
1785 assert_eq!(keys(&hidden), [1, 4]);
1786 assert_eq!(hidden.depth(3), None);
1787 assert_eq!(hidden.nearest_visible_ancestor(3), Some(1));
1788 assert!(!hidden.is_expanded(1));
1789 assert!(!hidden.is_filtering());
1790 assert!(
1791 state
1792 .command(&hidden, TreeCommand::CollapseRecursively(-1))
1793 .is_none()
1794 );
1795 assert_eq!(state.selection().get(&3), Some(&leaf));
1796 model.set_row(2, (3, 2, false, "leaf"));
1797 assert!(Arc::ptr_eq(&hidden, &snapshot()));
1798
1799 query.set("needle".into());
1800 let filtered = snapshot();
1801 assert!(filtered.rows().is_empty());
1802 model.set_row(2, (3, 2, true, "needle"));
1803 assert!(Arc::ptr_eq(&filtered, &snapshot()));
1804 model.set_row(1, (2, 1, true, "branch"));
1805 assert_eq!(keys(&snapshot()), [1, 2, 3]);
1806 query.set(String::new());
1807 assert_eq!(keys(&snapshot()), [1, 2, 3, 4]);
1808
1809 root.set(2);
1810 assert_eq!(keys(&snapshot()), [3]);
1811 model.set_row(0, (1, -1, false, "root"));
1812 assert!(snapshot().rows().is_empty());
1813 model.set_row(0, (1, -1, true, "root"));
1814 assert_eq!(keys(&snapshot()), [3]);
1815 }
1816}