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