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