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_or(node);
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 if let Some(observation) = observation.as_ref() {
923 observation.changed.track();
924 }
925 }
926 let mut included = vec![false; topology.entries.len()];
927 let mut pending = topology.roots_for(root, branch).to_vec();
928 while let Some(index) = pending.pop() {
929 if available.as_ref().is_some_and(|rows| !rows[index]) {
930 continue;
931 }
932 let entry = &topology.entries[index];
933 pending.extend_from_slice(&entry.children);
934 if !model
935 .project_row_untracked(entry.model_index, matches)
936 .unwrap_or(false)
937 {
938 continue;
939 }
940 let mut ancestor = Some(index);
941 while let Some(index) = ancestor {
942 if Some(index) == branch || included[index] {
943 break;
944 }
945 included[index] = true;
946 ancestor = topology.entries[index].parent;
947 }
948 }
949 self.build_snapshot(topology, root, available, Some(included))
950 }
951
952 fn track_source(&self) {
953 self.source
954 .get(|| unreachable!("tree source is initialized"));
955 }
956
957 fn topology<T>(
958 &self,
959 model: &VecModel<T>,
960 roles: impl Fn(&T) -> (i64, i64) + Clone + 'static,
961 ) -> Arc<Topology> {
962 self.topology.get(|| {
963 self.track_source();
964 let model_id = model.structure_stamp().0;
965 {
966 let mut observation = self.roles_changed.borrow_mut();
967 if let Some((_, signal)) = observation.as_ref().filter(|(id, _)| *id == model_id) {
968 signal.track();
969 } else {
970 let signal = model.observe_projection(MAX_ROWS, roles.clone());
971 signal.track();
972 *observation = Some((model_id, signal));
973 }
974 }
975 let topology = Arc::new(Topology::new(model, model_id, roles));
976 self.selection.borrow_mut().retain_live(&topology);
977 topology
978 })
979 }
980
981 fn build_snapshot(
982 &self,
983 topology: Arc<Topology>,
984 root: i64,
985 available: Option<Arc<[bool]>>,
986 included: Option<Vec<bool>>,
987 ) -> Arc<TreeSnapshot> {
988 Arc::new(TreeSnapshot::new(
989 topology,
990 self.expanded.get(|| Arc::new(BTreeMap::new())),
991 root,
992 available,
993 included,
994 ))
995 }
996
997 pub fn set_expanded(&self, tree: &TreeSnapshot, key: i64, row: RowKey, expanded: bool) -> bool {
998 if !tree
999 .visible_index(key)
1000 .and_then(|index| tree.rows().get(index))
1001 .is_some_and(|item| item.row == row && item.has_children && item.expanded != expanded)
1002 {
1003 return false;
1004 }
1005 let command = if expanded {
1006 TreeCommand::Expand(key)
1007 } else {
1008 TreeCommand::Collapse(key)
1009 };
1010 self.command(tree, command).is_some()
1011 }
1012
1013 pub fn command(
1014 &self,
1015 tree: &TreeSnapshot,
1016 command: TreeCommand,
1017 ) -> Option<TreeExpansionChange> {
1018 let (expanded, change) = self.prepare_command(tree, command)?;
1019 self.expanded.set(expanded);
1020 Some(change)
1021 }
1022
1023 #[doc(hidden)]
1025 pub fn try_apply_command<E>(
1026 &self,
1027 command: TreeCommand,
1028 live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1029 current: impl FnOnce() -> Result<i64, E>,
1030 ) -> Result<Option<(TreeExpansionChange, Option<i64>)>, E> {
1031 let prepared = crate::try_prepare_action_view(|| {
1032 let tree = live()?;
1033 let Some((expanded, change)) = self.prepare_command(&tree, command) else {
1034 return Ok(None);
1035 };
1036 let current = current()?;
1037 let next = tree
1038 .nearest_visible_after_expansion(current, &expanded)
1039 .filter(|key| *key != current);
1040 Ok(Some((expanded, change, next)))
1041 })?;
1042 Ok(prepared.map(|(expanded, change, next)| {
1043 self.expanded.set(expanded);
1044 (change, next)
1045 }))
1046 }
1047
1048 #[doc(hidden)]
1049 pub fn apply_command(
1050 &self,
1051 command: TreeCommand,
1052 live: impl FnOnce() -> Arc<TreeSnapshot>,
1053 current: impl FnOnce() -> i64,
1054 ) -> Option<(TreeExpansionChange, Option<i64>)> {
1055 self.try_apply_command(
1056 command,
1057 || Ok::<_, std::convert::Infallible>(live()),
1058 || Ok(current()),
1059 )
1060 .unwrap_or_else(|error| match error {})
1061 }
1062
1063 fn prepare_command(
1064 &self,
1065 tree: &TreeSnapshot,
1066 command: TreeCommand,
1067 ) -> Option<(Arc<BTreeMap<i64, RowKey>>, TreeExpansionChange)> {
1068 if tree.is_filtering()
1069 || !self
1070 .topology
1071 .matches_current(|current| Arc::ptr_eq(current, &tree.topology))
1072 || tree.available.as_ref().is_some_and(|shown| {
1073 !self
1074 .availability
1075 .matches_current(|current| Arc::ptr_eq(current, shown))
1076 })
1077 {
1078 return None;
1079 }
1080 let topology = &tree.topology;
1081 let mut state = self.expanded.get(|| Arc::new(BTreeMap::new()));
1082 let expanded = Arc::make_mut(&mut state);
1083 expanded.retain(|key, row| topology.row_key(*key) == Some(*row));
1084 let (key, expand, pending, depth_limit) = match command {
1085 TreeCommand::Expand(key)
1086 | TreeCommand::Collapse(key)
1087 | TreeCommand::ToggleExpanded(key) => {
1088 let index = tree.entry_index(key)?;
1089 let entry = &topology.entries[index];
1090 let expand = match command {
1091 TreeCommand::ToggleExpanded(_) => expanded.get(&key) != Some(&entry.row),
1092 TreeCommand::Expand(_) => true,
1093 _ => false,
1094 };
1095 (key, expand, vec![index], Some(1_usize))
1096 }
1097 TreeCommand::ExpandRecursively { key, depth } => {
1098 if depth < -1 || depth == 0 {
1099 return None;
1100 }
1101 let roots = if key == -1 {
1102 tree.root_entries().to_vec()
1103 } else {
1104 vec![tree.entry_index(key)?]
1105 };
1106 (key, true, roots, usize::try_from(depth).ok())
1107 }
1108 TreeCommand::CollapseRecursively(key) => {
1109 let roots = if key == -1 {
1110 tree.root_entries().to_vec()
1111 } else {
1112 vec![tree.entry_index(key)?]
1113 };
1114 (key, false, roots, None)
1115 }
1116 TreeCommand::ExpandTo(key) => {
1117 let mut index = tree.entry_index(key)?;
1118 let mut ancestors = Vec::new();
1119 while let Some(parent) = topology.entries[index]
1120 .parent
1121 .filter(|parent| Some(*parent) != tree.root)
1122 {
1123 ancestors.push(parent);
1124 index = parent;
1125 }
1126 (key, true, ancestors, Some(1))
1127 }
1128 };
1129 let mut pending: Vec<_> = pending.into_iter().map(|index| (index, 0_usize)).collect();
1130 let mut changed = false;
1131 while let Some((index, depth)) = pending.pop() {
1132 let entry = &topology.entries[index];
1133 if !tree.is_available(index) || !tree.has_available_children(index) {
1134 continue;
1135 }
1136 if expand {
1137 changed |= expanded.insert(entry.key, entry.row) != Some(entry.row);
1138 } else {
1139 changed |= expanded.remove(&entry.key).is_some();
1140 }
1141 if depth_limit.is_none_or(|limit| depth + 1 < limit) {
1142 pending.extend(entry.children.iter().map(|&child| (child, depth + 1)));
1143 }
1144 }
1145 if !changed {
1146 return None;
1147 }
1148 Some((
1149 state,
1150 TreeExpansionChange {
1151 key,
1152 expanded: expand,
1153 },
1154 ))
1155 }
1156
1157 pub fn selection(&self) -> Arc<BTreeMap<i64, RowKey>> {
1158 self.selection_changed.track();
1159 self.selection.borrow().keys.clone()
1160 }
1161
1162 #[doc(hidden)]
1163 pub fn selected_keys(&self, tree: &TreeSnapshot, single_current: Option<i64>) -> Vec<i64> {
1164 if let Some(current) = single_current {
1165 return tree
1166 .visible_index(current)
1167 .map(|_| current)
1168 .into_iter()
1169 .collect();
1170 }
1171 self.selection_changed.track();
1172 self.selection.borrow().keys.keys().copied().collect()
1173 }
1174
1175 #[doc(hidden)]
1177 pub fn try_replace_selection<E>(
1178 &self,
1179 keys: &[i64],
1180 live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1181 multiple: impl FnOnce() -> Result<bool, E>,
1182 ) -> Result<Option<TreeSelectionChange>, E> {
1183 let keys = crate::try_prepare_action_view(|| {
1184 if !multiple()? {
1185 return Ok(None);
1186 }
1187 let tree = live()?;
1188 Ok(keys
1189 .iter()
1190 .map(|&key| tree.topology.row_key(key).map(|row| (key, row)))
1191 .collect::<Option<BTreeMap<_, _>>>())
1192 })?;
1193 let Some(keys) = keys else {
1194 return Ok(None);
1195 };
1196 let selected_count = {
1197 let mut selection = self.selection.borrow_mut();
1198 selection.anchor = None;
1199 selection.replace_keys(Arc::new(keys))
1200 };
1201 if selected_count.is_some() {
1202 self.selection_changed.notify();
1203 }
1204 Ok(Some(TreeSelectionChange {
1205 current: None,
1206 selected_count,
1207 }))
1208 }
1209
1210 #[doc(hidden)]
1211 pub fn replace_selection(
1212 &self,
1213 keys: &[i64],
1214 live: impl FnOnce() -> Arc<TreeSnapshot>,
1215 multiple: impl FnOnce() -> bool,
1216 ) -> Option<TreeSelectionChange> {
1217 self.try_replace_selection(
1218 keys,
1219 || Ok::<_, std::convert::Infallible>(live()),
1220 || Ok(multiple()),
1221 )
1222 .unwrap_or_else(|error| match error {})
1223 }
1224
1225 #[doc(hidden)]
1226 pub fn selection_info(
1227 &self,
1228 tree: &TreeSnapshot,
1229 multiple: bool,
1230 current: i64,
1231 query: Option<TreeSelectionLookup>,
1232 ) -> (i64, bool) {
1233 let key = match query {
1234 Some(TreeSelectionLookup::Row(index)) => usize::try_from(index)
1235 .ok()
1236 .and_then(|index| tree.rows().get(index))
1237 .map(|item| item.key),
1238 Some(TreeSelectionLookup::Key(key)) => Some(key),
1239 None => None,
1240 };
1241 if multiple {
1242 self.selection_changed.track();
1243 let selection = self.selection.borrow();
1244 (
1245 selection.keys.len() as i64,
1246 key.is_some_and(|key| selection.keys.contains_key(&key)),
1247 )
1248 } else {
1249 let current = tree.visible_index(current).map(|_| current);
1250 (
1251 i64::from(current.is_some()),
1252 key.is_some() && key == current,
1253 )
1254 }
1255 }
1256
1257 #[doc(hidden)]
1259 pub fn populate_scene(&self, node: &mut Node, tree: Arc<TreeSnapshot>) {
1260 node.list = Some(ListMetrics {
1261 row_count: tree.rows().len(),
1262 first_row: 0,
1263 });
1264 node.properties
1265 .entry("current-key")
1266 .or_insert(Value::Int(-1));
1267 node.tree_selection = node
1268 .boolean("multi-select", false)
1269 .then(|| self.selection());
1270 node.tree = Some(tree);
1271 }
1272
1273 #[doc(hidden)]
1275 pub fn try_apply_control<E>(
1276 &self,
1277 node: &Node,
1278 input: crate::InputRoute<'_>,
1279 available: impl FnOnce() -> Result<bool, E>,
1280 multiple: impl FnOnce() -> Result<bool, E>,
1281 live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1282 current: impl FnOnce() -> Result<i64, E>,
1283 ) -> Result<Option<TreeControlChange>, E> {
1284 let crate::RoutedEvent::Control(action) = *input.event() else {
1285 return Ok(None);
1286 };
1287 let Some(snapshot) = &node.tree else {
1288 return Ok(None);
1289 };
1290 let snapshot_multiple = node.tree_selection.is_some();
1291 let action = match action {
1292 ControlAction::Select(index) => {
1293 let Some(item) = snapshot.rows().get(index) else {
1294 return Ok(None);
1295 };
1296 TreeAction::Selection(TreeSelectionAction::Row {
1297 key: item.key,
1298 row: item.row,
1299 operation: RowSelection::Replace,
1300 })
1301 }
1302 ControlAction::Tree(action @ TreeAction::SetExpanded { .. }) => action,
1303 ControlAction::Tree(action @ TreeAction::Selection(_)) if snapshot_multiple => action,
1304 _ => return Ok(None),
1305 };
1306 let prepared = crate::property::watch_reads(|reads| {
1307 if !available()? || reads.changed() {
1308 return Ok(None);
1309 }
1310 if matches!(action, TreeAction::Selection(_))
1311 && (multiple()? != snapshot_multiple || reads.changed())
1312 {
1313 return Ok(None);
1314 }
1315 let live = live()?;
1316 if reads.changed() {
1317 return Ok(None);
1318 }
1319 if let TreeAction::Selection(selection) = action
1320 && snapshot_multiple
1321 {
1322 let needs_order = matches!(
1323 selection,
1324 TreeSelectionAction::Row {
1325 operation: RowSelection::Extend | RowSelection::AddRange,
1326 ..
1327 }
1328 );
1329 if !snapshot.same_model(&live)
1330 || (needs_order && !snapshot.same_visible_rows(&live))
1331 {
1332 return Ok(None);
1333 }
1334 }
1335 let current = current()?;
1336 Ok((input.is_current() && !reads.changed()).then_some((live, current)))
1337 })?;
1338 let Some((live, current)) = prepared else {
1339 return Ok(None);
1340 };
1341 Ok(match action {
1342 TreeAction::Selection(selection) => self
1343 .select_in_mode(&live, current, snapshot_multiple, selection)
1344 .map(TreeControlChange::Selection),
1345 TreeAction::SetExpanded { key, row, expanded } => self
1346 .set_expanded(&live, key, row, expanded)
1347 .then(|| TreeControlChange::Expansion {
1348 change: TreeExpansionChange { key, expanded },
1349 current: (!expanded && live.is_descendant(current, key)).then_some(key),
1350 }),
1351 })
1352 }
1353
1354 #[doc(hidden)]
1355 pub fn apply_control(
1356 &self,
1357 node: &Node,
1358 input: crate::InputRoute<'_>,
1359 available: impl FnOnce() -> bool,
1360 multiple: impl FnOnce() -> bool,
1361 live: impl FnOnce() -> Arc<TreeSnapshot>,
1362 current: impl FnOnce() -> i64,
1363 ) -> Option<TreeControlChange> {
1364 self.try_apply_control(
1365 node,
1366 input,
1367 || Ok::<_, std::convert::Infallible>(available()),
1368 || Ok(multiple()),
1369 || Ok(live()),
1370 || Ok(current()),
1371 )
1372 .unwrap_or_else(|error| match error {})
1373 }
1374
1375 #[doc(hidden)]
1377 pub fn try_apply_selection<E>(
1378 &self,
1379 command: TreeSelectionCommand,
1380 live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1381 multiple: impl FnOnce() -> Result<bool, E>,
1382 current: impl FnOnce() -> Result<i64, E>,
1383 ) -> Result<Option<TreeSelectionChange>, E> {
1384 let prepared = crate::try_prepare_action_view(|| {
1385 let tree = live()?;
1386 let row = |index: usize, operation| {
1387 tree.rows().get(index).map(|item| TreeSelectionAction::Row {
1388 key: item.key,
1389 row: item.row,
1390 operation,
1391 })
1392 };
1393 let replace = |index| row(index, RowSelection::Replace);
1394 let action = match command {
1395 TreeSelectionCommand::Source(source) => {
1396 tree.visible_index_for_source(source).and_then(replace)
1397 }
1398 TreeSelectionCommand::Key(key) => tree.visible_index(key).and_then(replace),
1399 TreeSelectionCommand::Visual(TableSelectionAction::Row { index, operation }) => {
1400 row(index, operation)
1401 }
1402 TreeSelectionCommand::Visual(TableSelectionAction::All) => {
1403 Some(TreeSelectionAction::All)
1404 }
1405 TreeSelectionCommand::Visual(TableSelectionAction::Clear) => {
1406 Some(TreeSelectionAction::Clear)
1407 }
1408 TreeSelectionCommand::Visual(_) => None,
1409 };
1410 let Some(action) = action else {
1411 return Ok(None);
1412 };
1413 let multiple = multiple()?;
1414 if !multiple
1415 && !matches!(
1416 action,
1417 TreeSelectionAction::Row {
1418 operation: RowSelection::Replace,
1419 ..
1420 }
1421 )
1422 {
1423 return Ok(None);
1424 }
1425 let current = current()?;
1426 Ok(Some((tree, multiple, current, action)))
1427 })?;
1428 Ok(prepared.and_then(|(tree, multiple, current, action)| {
1429 self.select_in_mode(&tree, current, multiple, action)
1430 }))
1431 }
1432
1433 #[doc(hidden)]
1434 pub fn apply_selection(
1435 &self,
1436 command: TreeSelectionCommand,
1437 live: impl FnOnce() -> Arc<TreeSnapshot>,
1438 multiple: impl FnOnce() -> bool,
1439 current: impl FnOnce() -> i64,
1440 ) -> Option<TreeSelectionChange> {
1441 self.try_apply_selection(
1442 command,
1443 || Ok::<_, std::convert::Infallible>(live()),
1444 || Ok(multiple()),
1445 || Ok(current()),
1446 )
1447 .unwrap_or_else(|error| match error {})
1448 }
1449
1450 #[doc(hidden)]
1451 pub fn try_select_source<E>(
1452 &self,
1453 source: usize,
1454 live: impl FnOnce() -> Result<Arc<TreeSnapshot>, E>,
1455 multiple: impl FnOnce() -> Result<bool, E>,
1456 current: impl FnOnce() -> Result<i64, E>,
1457 ) -> Result<Option<TreeSelectionChange>, E> {
1458 self.try_apply_selection(
1459 TreeSelectionCommand::Source(source),
1460 live,
1461 multiple,
1462 current,
1463 )
1464 }
1465
1466 #[doc(hidden)]
1467 pub fn select_source(
1468 &self,
1469 source: usize,
1470 live: impl FnOnce() -> Arc<TreeSnapshot>,
1471 multiple: impl FnOnce() -> bool,
1472 current: impl FnOnce() -> i64,
1473 ) -> Option<TreeSelectionChange> {
1474 self.apply_selection(
1475 TreeSelectionCommand::Source(source),
1476 live,
1477 multiple,
1478 current,
1479 )
1480 }
1481
1482 #[doc(hidden)]
1483 pub fn select_in_mode(
1484 &self,
1485 tree: &TreeSnapshot,
1486 current: i64,
1487 multiple: bool,
1488 action: TreeSelectionAction,
1489 ) -> Option<TreeSelectionChange> {
1490 if !self
1491 .snapshot
1492 .matches_current(|live| std::ptr::eq(live.as_ref(), tree))
1493 {
1494 return None;
1495 }
1496 if multiple {
1497 return self.select(tree, current, action);
1498 }
1499 let TreeSelectionAction::Row { key, row, .. } = action else {
1500 return None;
1501 };
1502 let item = tree.rows().get(tree.visible_index(key)?)?;
1503 (item.row == row && key != current).then_some(TreeSelectionChange {
1504 current: Some(key),
1505 selected_count: None,
1506 })
1507 }
1508
1509 pub fn select(
1510 &self,
1511 tree: &TreeSnapshot,
1512 current: i64,
1513 action: TreeSelectionAction,
1514 ) -> Option<TreeSelectionChange> {
1515 let mut selection = self.selection.borrow_mut();
1516 let mut next = selection.keys.clone();
1517 let current = match action {
1518 TreeSelectionAction::Row {
1519 key,
1520 row,
1521 operation,
1522 } => {
1523 let index = tree.visible_index(key)?;
1524 if tree.rows()[index].row != row {
1525 return None;
1526 }
1527 match operation {
1528 RowSelection::Replace => {
1529 next = Arc::new(BTreeMap::from([(key, row)]));
1530 selection.anchor = Some((key, row));
1531 }
1532 RowSelection::Toggle => {
1533 let selected = Arc::make_mut(&mut next);
1534 if selected.remove(&key).is_none() {
1535 selected.insert(key, row);
1536 }
1537 selection.anchor = Some((key, row));
1538 }
1539 RowSelection::Extend | RowSelection::AddRange => {
1540 let start = selection
1541 .anchor
1542 .and_then(|(key, _)| tree.visible_index(key))
1543 .or_else(|| tree.visible_index(current))
1544 .unwrap_or(index);
1545 let anchor = &tree.rows()[start];
1546 selection.anchor = Some((anchor.key, anchor.row));
1547 let rows = tree.rows()[start.min(index)..=start.max(index)]
1548 .iter()
1549 .map(|item| (item.key, item.row));
1550 if operation == RowSelection::Extend {
1551 next = Arc::new(rows.collect());
1552 } else {
1553 Arc::make_mut(&mut next).extend(rows);
1554 }
1555 }
1556 RowSelection::Move => {}
1557 }
1558 (key != current).then_some(key)
1559 }
1560 TreeSelectionAction::All => {
1561 next = Arc::new(
1562 tree.rows()
1563 .iter()
1564 .map(|item| (item.key, item.row))
1565 .collect(),
1566 );
1567 selection.anchor = None;
1568 None
1569 }
1570 TreeSelectionAction::Clear => {
1571 next = Arc::new(BTreeMap::new());
1572 selection.anchor = None;
1573 None
1574 }
1575 };
1576 let selected_count = selection.replace_keys(next);
1577 drop(selection);
1578 if selected_count.is_some() {
1579 self.selection_changed.notify();
1580 }
1581 Some(TreeSelectionChange {
1582 current,
1583 selected_count,
1584 })
1585 }
1586}
1587
1588#[cfg(test)]
1589mod tests {
1590 use super::*;
1591 use std::cell::Cell;
1592
1593 #[test]
1594 fn projection_handles_cycles_orphans_and_duplicates_without_rebuilding_on_expand() {
1595 let model = Rc::new(VecModel::from(vec![
1596 (9, 8),
1597 (8, 9),
1598 (10, 9),
1599 (3, -1),
1600 (3, -1),
1601 (6, 3),
1602 (7, 7),
1603 ]));
1604 let state = TreeState::default();
1605 let reads = Rc::new(Cell::new(0));
1606 let role_reads = reads.clone();
1607 let roles = move |item: &(i64, i64)| {
1608 role_reads.set(role_reads.get() + 1);
1609 *item
1610 };
1611 let tree = state.snapshot(|| model.clone(), roles.clone());
1612 assert_eq!(
1613 tree.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
1614 [8, 6, 7]
1615 );
1616 assert!(tree.is_descendant(10, 8));
1617 assert!(!tree.is_descendant(8, 9));
1618 let root = tree.rows()[0];
1619 assert!(state.set_expanded(&tree, root.key, root.row, true));
1620 let expanded = state.snapshot(|| model.clone(), roles.clone());
1621 assert_eq!(reads.get(), 7);
1622 assert_eq!(
1623 expanded
1624 .rows()
1625 .iter()
1626 .map(|row| row.key)
1627 .collect::<Vec<_>>(),
1628 [8, 9, 6, 7]
1629 );
1630 assert!(model.set_row(2, (10, 6)));
1631 assert_eq!(reads.get(), 9);
1632 let reparented = state.snapshot(|| model.clone(), roles);
1633 assert_eq!(reads.get(), 16);
1634 assert!(!reparented.is_descendant(10, 8));
1635 assert!(reparented.is_descendant(10, 6));
1636 assert!(reparented.rows()[0].expanded);
1637 }
1638
1639 #[test]
1640 fn recursive_commands_clear_hidden_descendants_and_preserve_depth_limits() {
1641 let model = Rc::new(VecModel::from(vec![
1642 (1, -1),
1643 (2, 1),
1644 (3, 2),
1645 (4, 1),
1646 (9, -1),
1647 (10, 9),
1648 ]));
1649 let state = TreeState::default();
1650 let tree = || state.snapshot(|| model.clone(), |row| *row);
1651 let initial = tree();
1652 assert_eq!(initial.depth(3), Some(2));
1653 assert_eq!(initial.depth(99), None);
1654 assert!(
1655 state
1656 .command(
1657 &initial,
1658 TreeCommand::ExpandRecursively { key: 1, depth: 1 }
1659 )
1660 .is_some()
1661 );
1662 assert!(tree().is_expanded(1));
1663 assert!(!tree().is_expanded(2));
1664 assert_eq!(tree().visible_index(3), None);
1665
1666 assert!(state.command(&tree(), TreeCommand::ExpandTo(3)).is_some());
1667 assert_eq!(tree().visible_index(3), Some(2));
1668 assert!(state.command(&tree(), TreeCommand::Collapse(1)).is_some());
1669 assert!(tree().is_expanded(2));
1670 assert_eq!(tree().nearest_visible_ancestor(3), Some(1));
1671 assert!(
1672 state
1673 .command(&tree(), TreeCommand::CollapseRecursively(1))
1674 .is_some()
1675 );
1676 assert!(!tree().is_expanded(2));
1677 assert!(state.command(&tree(), TreeCommand::Expand(1)).is_some());
1678 assert_eq!(tree().visible_index(3), None);
1679
1680 let before = tree();
1681 for command in [
1682 TreeCommand::Expand(99),
1683 TreeCommand::ExpandRecursively { key: 1, depth: 0 },
1684 TreeCommand::ExpandRecursively { key: 1, depth: -2 },
1685 ] {
1686 assert!(state.command(&before, command).is_none());
1687 }
1688 assert!(Arc::ptr_eq(&before, &tree()));
1689 assert!(state.command(&tree(), TreeCommand::ExpandTo(3)).is_some());
1690 let prior_model = tree();
1691 assert_eq!(model.remove(1), Some((2, 1)));
1692 model.push((2, 1));
1693 assert!(
1694 state
1695 .command(&prior_model, TreeCommand::CollapseRecursively(-1))
1696 .is_none()
1697 );
1698 assert!(!tree().is_expanded(2));
1699 assert_eq!(tree().visible_index(3), None);
1700 }
1701
1702 #[test]
1703 fn changing_the_view_root_reuses_topology_and_limits_expansion_to_the_branch() {
1704 let model = Rc::new(VecModel::from(vec![
1705 (1, -1),
1706 (10, 1),
1707 (100, 10),
1708 (103, 100),
1709 (2, -1),
1710 (20, 2),
1711 ]));
1712 let state = TreeState::default();
1713 let requested = Property::default();
1714 let reads = Rc::new(Cell::new(0));
1715 let count = reads.clone();
1716 let roles = move |row: &(i64, i64)| {
1717 count.set(count.get() + 1);
1718 *row
1719 };
1720 let tree =
1721 || state.snapshot_with_root(|| model.clone(), roles.clone(), || requested.get(|| -1));
1722 assert!(
1723 state
1724 .command(
1725 &tree(),
1726 TreeCommand::ExpandRecursively { key: -1, depth: -1 }
1727 )
1728 .is_some()
1729 );
1730 let global = tree();
1731 assert_eq!(global.rows().len(), 6);
1732
1733 requested.set(10);
1734 let source = tree();
1735 assert!(Arc::ptr_eq(&global.topology, &source.topology));
1736 assert_eq!(
1737 source.rows().iter().map(|row| row.key).collect::<Vec<_>>(),
1738 [100, 103]
1739 );
1740 assert_eq!(source.rows()[0].parent, None);
1741 assert_eq!(source.depth(100), Some(0));
1742 assert_eq!(source.depth(103), Some(1));
1743 assert_eq!(source.depth(10), None);
1744 assert_eq!(source.depth(20), None);
1745 assert!(!source.is_descendant(103, 10));
1746 assert!(state.command(&source, TreeCommand::ExpandTo(20)).is_none());
1747 assert!(
1748 state
1749 .command(&source, TreeCommand::CollapseRecursively(-1))
1750 .is_some()
1751 );
1752
1753 requested.set(2);
1754 assert_eq!(tree().rows()[0].key, 20);
1755 assert_eq!(tree().rows()[0].depth, 0);
1756 requested.set(-1);
1757 let restored = tree();
1758 assert!(restored.is_expanded(1));
1759 assert!(restored.is_expanded(10));
1760 assert!(!restored.is_expanded(100));
1761 assert!(restored.is_expanded(2));
1762 assert_eq!(reads.get(), 6);
1763
1764 requested.set(999);
1765 let missing = tree();
1766 assert!(missing.rows().is_empty());
1767 assert!(
1768 state
1769 .command(&missing, TreeCommand::CollapseRecursively(-1))
1770 .is_none()
1771 );
1772 assert_eq!(missing.depth(100), None);
1773 assert_eq!(missing.root_key(), 999);
1774 }
1775
1776 #[test]
1777 fn filtering_uses_live_matches_and_preserves_the_saved_expansion() {
1778 type Row = (i64, i64, &'static str);
1779 let source = Property::default();
1780 let model = Rc::new(VecModel::from(vec![
1781 (1, -1, "project"),
1782 (2, 1, "src"),
1783 (3, 2, "Window.RS"),
1784 (4, 1, "notes"),
1785 (5, -1, "window outside"),
1786 ]));
1787 source.set(model.clone());
1788 let query = Property::default();
1789 query.set(" WINDOW ".to_owned());
1790 let state = TreeState::default();
1791 let read = || {
1792 state.snapshot_filtered(
1793 || source.get(|| unreachable!()),
1794 |row: &Row| (row.0, row.1),
1795 || 1,
1796 || query.get(String::new),
1797 |row| row.2,
1798 )
1799 };
1800 let filtered = read();
1801 assert!(filtered.is_filtering());
1802 assert_eq!(
1803 filtered
1804 .rows()
1805 .iter()
1806 .map(|row| row.key)
1807 .collect::<Vec<_>>(),
1808 [2, 3]
1809 );
1810 assert!(filtered.is_expanded(2));
1811 assert!(state.command(&filtered, TreeCommand::Collapse(2)).is_none());
1812 assert!(model.set_row(3, (4, 1, "README")));
1813 assert!(model.set_row(4, (5, -1, "outside rename")));
1814 assert!(Arc::ptr_eq(&filtered, &read()));
1815 assert!(model.set_row(3, (4, 1, "window docs")));
1816 assert_eq!(read().visible_index(4), Some(2));
1817
1818 query.set(String::new());
1819 let original = read();
1820 assert!(!original.is_filtering());
1821 assert!(!original.is_expanded(2));
1822 assert_eq!(original.visible_index(3), None);
1823
1824 query.set("window".to_owned());
1825 let before = read();
1826 source.set(Rc::new(VecModel::from(vec![
1827 (1, -1, "new project"),
1828 (9, 1, "window"),
1829 ])));
1830 let replaced = read();
1831 assert!(!before.same_model(&replaced));
1832 assert_eq!(replaced.rows()[0].key, 9);
1833 assert_eq!(replaced.rows().len(), 1);
1834 }
1835
1836 #[test]
1837 fn filtering_projects_the_model_after_reading_the_query() {
1838 let model = Rc::new(VecModel::from(vec![(1, -1, "one"), (2, 1, "two")]));
1839 let state = TreeState::default();
1840 let tree = state.snapshot_filtered(
1841 || model.clone(),
1842 |row| (row.0, row.1),
1843 || -1,
1844 || {
1845 assert_eq!(model.remove(0), Some((1, -1, "one")));
1846 "two".to_owned()
1847 },
1848 |row| row.2,
1849 );
1850 assert_eq!(tree.rows().len(), 1);
1851 assert_eq!((tree.rows()[0].key, tree.rows()[0].model_index), (2, 0));
1852 }
1853
1854 #[test]
1855 fn deep_ancestor_expansion_uses_the_topology_without_recursive_calls() {
1856 let model = Rc::new(VecModel::from(
1857 (0..4096).map(|key| (key, key - 1)).collect::<Vec<_>>(),
1858 ));
1859 let state = TreeState::default();
1860 let initial = state.snapshot(|| model.clone(), |row| *row);
1861 let topology = initial.topology.clone();
1862 assert!(
1863 state
1864 .command(&initial, TreeCommand::ExpandTo(4095))
1865 .is_some()
1866 );
1867 let expanded = state.snapshot(|| model.clone(), |row| *row);
1868 assert!(Arc::ptr_eq(&topology, &expanded.topology));
1869 assert_eq!(expanded.visible_index(4095), Some(4095));
1870 assert_eq!(expanded.depth(4095), Some(4095));
1871 assert!(
1872 state
1873 .command(&expanded, TreeCommand::CollapseRecursively(-1))
1874 .is_some()
1875 );
1876 let collapsed = state.snapshot(|| model.clone(), |row| *row);
1877 assert_eq!(collapsed.rows().len(), 1);
1878 assert!(!collapsed.is_expanded(4094));
1879 }
1880
1881 #[test]
1882 fn payload_changes_leave_independent_tree_projections_clean() {
1883 let model = Rc::new(VecModel::from(vec![(1, -1, -1, 0), (2, 1, -1, 0)]));
1884 let source = Property::default();
1885 source.set(model.clone());
1886 let primary = TreeState::default();
1887 let alternate = TreeState::default();
1888 let roles = |row: &(i64, i64, i64, i64)| (row.0, row.1);
1889 let other_roles = |row: &(i64, i64, i64, i64)| (row.0, row.2);
1890 let primary_tree = || primary.snapshot(|| source.get(|| unreachable!()), roles);
1891 let alternate_tree = || alternate.snapshot(|| model.clone(), other_roles);
1892 let first = primary_tree();
1893 let second = alternate_tree();
1894
1895 assert!(model.set_row(1, (2, 1, -1, 50)));
1896 assert!(Arc::ptr_eq(&first, &primary_tree()));
1897 assert!(Arc::ptr_eq(&second, &alternate_tree()));
1898 assert!(model.set_row(1, (2, 1, 1, 50)));
1899 assert!(Arc::ptr_eq(&first, &primary_tree()));
1900 let reparented = alternate_tree();
1901 assert!(!Arc::ptr_eq(&second, &reparented));
1902 assert!(reparented.is_descendant(2, 1));
1903
1904 source.set(Rc::new(VecModel::from(vec![(3, -1, -1, 0)])));
1905 let replacement = primary_tree();
1906 assert!(!replacement.same_model(&first));
1907 assert_eq!(replacement.rows()[0].key, 3);
1908 assert!(model.set_row(1, (2, -1, -1, 50)));
1909 assert!(Arc::ptr_eq(&replacement, &primary_tree()));
1910 assert!(!alternate_tree().is_descendant(2, 1));
1911 assert!(model.sort_by(|left, right| right.0.cmp(&left.0)));
1912 assert_eq!(alternate_tree().rows()[0].key, 2);
1913 assert!(Arc::ptr_eq(&replacement, &primary_tree()));
1914 }
1915
1916 #[test]
1917 fn visibility_masks_branches_without_rebuilding_topology_or_losing_expansion() {
1918 type Record = (i64, i64, bool, &'static str);
1919 let model = Rc::new(VecModel::from(vec![
1920 (1, -1, true, "root"),
1921 (2, 1, true, "branch"),
1922 (3, 2, true, "leaf"),
1923 (4, -1, true, "other"),
1924 ]));
1925 let root = Property::default();
1926 let query = Property::default();
1927 let state = TreeState::default();
1928 let snapshot = || {
1929 state.snapshot_projected(
1930 || model.clone(),
1931 |row| (row.0, row.1),
1932 || root.get(|| -1),
1933 Some(|row: &Record| row.2),
1934 Some(|row: &Record| row.3),
1935 || query.get(String::new),
1936 )
1937 };
1938 let keys =
1939 |tree: &TreeSnapshot| tree.rows().iter().map(|item| item.key).collect::<Vec<_>>();
1940 let first = snapshot();
1941 assert!(state.command(&first, TreeCommand::ExpandTo(3)).is_some());
1942 let expanded = snapshot();
1943 assert_eq!(keys(&expanded), [1, 2, 3, 4]);
1944 assert!(Arc::ptr_eq(
1945 first.available.as_ref().unwrap(),
1946 expanded.available.as_ref().unwrap()
1947 ));
1948 let leaf = model.row_key(2).unwrap();
1949 state
1950 .select(
1951 &expanded,
1952 -1,
1953 TreeSelectionAction::Row {
1954 key: 3,
1955 row: leaf,
1956 operation: RowSelection::Replace,
1957 },
1958 )
1959 .unwrap();
1960
1961 model.set_row(1, (2, 1, false, "branch"));
1962 assert!(state.command(&expanded, TreeCommand::Collapse(2)).is_none());
1963 let hidden = snapshot();
1964 assert!(Arc::ptr_eq(&expanded.topology, &hidden.topology));
1965 assert_eq!(keys(&hidden), [1, 4]);
1966 assert_eq!(hidden.depth(3), None);
1967 assert_eq!(hidden.nearest_visible_ancestor(3), Some(1));
1968 assert!(!hidden.is_expanded(1));
1969 assert!(!hidden.is_filtering());
1970 assert!(
1971 state
1972 .command(&hidden, TreeCommand::CollapseRecursively(-1))
1973 .is_none()
1974 );
1975 assert_eq!(state.selection().get(&3), Some(&leaf));
1976 model.set_row(2, (3, 2, false, "leaf"));
1977 assert!(Arc::ptr_eq(&hidden, &snapshot()));
1978
1979 query.set("needle".into());
1980 let filtered = snapshot();
1981 assert!(filtered.rows().is_empty());
1982 model.set_row(2, (3, 2, true, "needle"));
1983 assert!(Arc::ptr_eq(&filtered, &snapshot()));
1984 model.set_row(1, (2, 1, true, "branch"));
1985 assert_eq!(keys(&snapshot()), [1, 2, 3]);
1986 query.set(String::new());
1987 assert_eq!(keys(&snapshot()), [1, 2, 3, 4]);
1988
1989 root.set(2);
1990 assert_eq!(keys(&snapshot()), [3]);
1991 model.set_row(0, (1, -1, false, "root"));
1992 assert!(snapshot().rows().is_empty());
1993 model.set_row(0, (1, -1, true, "root"));
1994 assert_eq!(keys(&snapshot()), [3]);
1995 }
1996}